aboutsummaryrefslogtreecommitdiffstatshomepage
path: root/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs
diff options
context:
space:
mode:
Diffstat (limited to 'OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs')
-rw-r--r--OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs385
1 files changed, 0 insertions, 385 deletions
diff --git a/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs b/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs
deleted file mode 100644
index 415c646..0000000
--- a/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs
+++ /dev/null
@@ -1,385 +0,0 @@
1/*
2 * Copyright (C) 2007-2008, Jeff Thompson
3 *
4 * All rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions are met:
8 *
9 * * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 * * Redistributions in binary form must reproduce the above copyright
12 * notice, this list of conditions and the following disclaimer in the
13 * documentation and/or other materials provided with the distribution.
14 * * Neither the name of the copyright holder nor the names of its contributors
15 * may be used to endorse or promote products derived from this software
16 * without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
22 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
23 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
24 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
25 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
26 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
27 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
28 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31using System;
32using System.Collections;
33using System.Collections.Generic;
34
35namespace OpenSim.Region.ScriptEngine.DotNetEngine.Compiler.YieldProlog
36{
37 /// <summary>
38 /// An IndexedAnswers holds answers to a query based on the values of index arguments.
39 /// </summary>
40 public class IndexedAnswers : YP.IClause
41 {
42 private int _arity;
43 // addAnswer adds the answer here and indexes it later.
44 private List<object[]> _allAnswers = new List<object[]>();
45 // The key has the arity of answers with non-null values for each indexed arg. The value
46 // is a list of the matching answers. The signature is implicit in the pattern on non-null index args.
47 private Dictionary<HashedList, List<object[]>> _indexedAnswers =
48 new Dictionary<HashedList, List<object[]>>();
49 // Keeps track of whether we have started adding entries to _indexedAnswers for the signature.
50 private Dictionary<int, object> _gotAnswersForSignature = new Dictionary<int, object>();
51 private const int MAX_INDEX_ARGS = 31;
52
53 public IndexedAnswers(int arity)
54 {
55 _arity = arity;
56 }
57
58 /// <summary>
59 /// Append the answer to the list and update the indexes, if any.
60 /// Elements of answer must be ground, since arguments with unbound variables make this
61 /// into a dynamic rule which we don't index.
62 /// </summary>
63 /// <param name="answer"></param>
64 public void addAnswer(object[] answer)
65 {
66 addOrPrependAnswer(answer, false);
67 }
68
69 /// <summary>
70 /// Prepend the answer to the list and clear the indexes so that they must be re-computed
71 /// on the next call to match. (Only addAnswer will maintain the indexes while adding answers.)
72 /// Elements of answer must be ground, since arguments with unbound variables make this
73 /// into a dynamic rule which we don't index.
74 /// </summary>
75 /// <param name="answer"></param>
76 public void prependAnswer(object[] answer)
77 {
78 addOrPrependAnswer(answer, true);
79 }
80
81 /// <summary>
82 /// Do the work of addAnswer or prependAnswer.
83 /// </summary>
84 /// <param name="answer"></param>
85 private void addOrPrependAnswer(object[] answer, bool prepend)
86 {
87 if (answer.Length != _arity)
88 return;
89
90 // Store a copy of the answer array.
91 object[] answerCopy = new object[answer.Length];
92 Variable.CopyStore copyStore = new Variable.CopyStore();
93 for (int i = 0; i < answer.Length; ++i)
94 answerCopy[i] = YP.makeCopy(answer[i], copyStore);
95 if (copyStore.getNUniqueVariables() > 0)
96 throw new InvalidOperationException
97 ("Elements of answer must be ground, but found " + copyStore.getNUniqueVariables() +
98 " unbound variables");
99
100 if (prepend)
101 {
102 _allAnswers.Insert(0, answerCopy);
103 clearIndexes();
104 }
105 else
106 {
107 _allAnswers.Add(answerCopy);
108 // If match has already indexed answers for a signature, we need to add
109 // this to the existing indexed answers.
110 foreach (int signature in _gotAnswersForSignature.Keys)
111 indexAnswerForSignature(answerCopy, signature);
112 }
113 }
114
115 private void indexAnswerForSignature(object[] answer, int signature)
116 {
117 // First find out which of the answer values can be used as an index.
118 object[] indexValues = new object[answer.Length];
119 for (int i = 0; i < answer.Length; ++i)
120 {
121 // We limit the number of indexed args in a 32-bit signature.
122 if (i >= MAX_INDEX_ARGS)
123 indexValues[i] = null;
124 else
125 indexValues[i] = getIndexValue(YP.getValue(answer[i]));
126 }
127
128 // We need an entry in indexArgs from indexValues for each 1 bit in signature.
129 HashedList indexArgs = new HashedList(indexValues.Length);
130 for (int i = 0; i < indexValues.Length; ++i)
131 {
132 if ((signature & (1 << i)) == 0)
133 indexArgs.Add(null);
134 else
135 {
136 if (indexValues[i] == null)
137 // The signature wants an index value here, but we don't have one so
138 // we can't add it as an answer for this signature.
139 return;
140 else
141 indexArgs.Add(indexValues[i]);
142 }
143 }
144
145 // Add the answer to the answers list for indexArgs, creating the entry if needed.
146 List<object[]> answers;
147 if (!_indexedAnswers.TryGetValue(indexArgs, out answers))
148 {
149 answers = new List<object[]>();
150 _indexedAnswers[indexArgs] = answers;
151 }
152 answers.Add(answer);
153 }
154
155 public IEnumerable<bool> match(object[] arguments)
156 {
157 if (arguments.Length != _arity)
158 yield break;
159
160 // Set up indexArgs, up to arg position MAX_INDEX_ARGS. The signature has a 1 bit for
161 // each non-null index arg.
162 HashedList indexArgs = new HashedList(arguments.Length);
163 bool gotAllIndexArgs = true;
164 int signature = 0;
165 for (int i = 0; i < arguments.Length; ++i)
166 {
167 object indexValue = null;
168 if (i < MAX_INDEX_ARGS)
169 {
170 // We limit the number of args in a 32-bit signature.
171 indexValue = getIndexValue(YP.getValue(arguments[i]));
172 if (indexValue != null)
173 signature += (1 << i);
174 }
175 if (indexValue == null)
176 gotAllIndexArgs = false;
177 indexArgs.Add(indexValue);
178 }
179
180 List<object[]> answers;
181 if (signature == 0)
182 // No index args, so we have to match from _allAnswers.
183 answers = _allAnswers;
184 else
185 {
186 if (!_gotAnswersForSignature.ContainsKey(signature))
187 {
188 // We need to create the entry in _indexedAnswers.
189 foreach (object[] answer in _allAnswers)
190 indexAnswerForSignature(answer, signature);
191 // Mark that we did this signature.
192 _gotAnswersForSignature[signature] = null;
193 }
194 if (!_indexedAnswers.TryGetValue(indexArgs, out answers))
195 yield break;
196 }
197
198 if (gotAllIndexArgs)
199 {
200 // All the arguments were already bound, so we don't need to do bindings.
201 yield return false;
202 yield break;
203 }
204
205 // Find matches in answers.
206 IEnumerator<bool>[] iterators = new IEnumerator<bool>[arguments.Length];
207 // Debug: If the caller asserts another answer into this same predicate during yield, the iterator
208 // over clauses will be corrupted. Should we take the time to copy answers?
209 foreach (object[] answer in answers)
210 {
211 bool gotMatch = true;
212 int nIterators = 0;
213 // Try to bind all the arguments.
214 for (int i = 0; i < arguments.Length; ++i)
215 {
216 if (indexArgs[i] != null)
217 // We already matched this argument by looking up _indexedAnswers.
218 continue;
219
220 IEnumerator<bool> iterator = YP.unify(arguments[i], answer[i]).GetEnumerator();
221 iterators[nIterators++] = iterator;
222 // MoveNext() is true if YP.unify succeeds.
223 if (!iterator.MoveNext())
224 {
225 gotMatch = false;
226 break;
227 }
228 }
229
230 try
231 {
232 if (gotMatch)
233 yield return false;
234 }
235 finally
236 {
237 // Manually finalize all the iterators.
238 for (int i = 0; i < nIterators; ++i)
239 iterators[i].Dispose();
240 }
241 }
242 }
243
244 public IEnumerable<bool> clause(object Head, object Body)
245 {
246 Head = YP.getValue(Head);
247 if (Head is Variable)
248 throw new PrologException("instantiation_error", "Head is an unbound variable");
249 object[] arguments = YP.getFunctorArgs(Head);
250
251 // We always match Head from _allAnswers, and the Body is Atom.a("true").
252 #pragma warning disable 0168
253 foreach (bool l1 in YP.unify(Body, Atom.a("true")))
254 {
255 // The caller can assert another answer into this same predicate during yield, so we have to
256 // make a copy of the answers.
257 foreach (object[] answer in _allAnswers.ToArray())
258 {
259 foreach (bool l2 in YP.unifyArrays(arguments, answer))
260 yield return false;
261 }
262 }
263 #pragma warning restore 0168
264 }
265
266 public IEnumerable<bool> retract(object Head, object Body)
267 {
268 Head = YP.getValue(Head);
269 if (Head is Variable)
270 throw new PrologException("instantiation_error", "Head is an unbound variable");
271 object[] arguments = YP.getFunctorArgs(Head);
272
273 // We always match Head from _allAnswers, and the Body is Atom.a("true").
274 #pragma warning disable 0168
275 foreach (bool l1 in YP.unify(Body, Atom.a("true")))
276 {
277 // The caller can assert another answer into this same predicate during yield, so we have to
278 // make a copy of the answers.
279 foreach (object[] answer in _allAnswers.ToArray())
280 {
281 foreach (bool l2 in YP.unifyArrays(arguments, answer))
282 {
283 _allAnswers.Remove(answer);
284 clearIndexes();
285 yield return false;
286 }
287 }
288 }
289 #pragma warning restore 0168
290 }
291
292 /// <summary>
293 /// After retracting or prepending an answer in _allAnswers, the indexes are invalid, so clear them.
294 /// </summary>
295 private void clearIndexes()
296 {
297 _indexedAnswers.Clear();
298 _gotAnswersForSignature.Clear();
299 }
300
301 /// <summary>
302 /// A HashedList extends an ArrayList with methods to get a hash and to check equality
303 /// based on the elements of the list.
304 /// </summary>
305 public class HashedList : ArrayList
306 {
307 private bool _gotHashCode = false;
308 private int _hashCode;
309
310 public HashedList()
311 : base()
312 {
313 }
314
315 public HashedList(int capacity)
316 : base(capacity)
317 {
318 }
319
320 public HashedList(ICollection c)
321 : base(c)
322 {
323 }
324
325 // Debug: Should override all the other methods that change this.
326 public override int Add(object value)
327 {
328 _gotHashCode = false;
329 return base.Add(value);
330 }
331
332 public override int GetHashCode()
333 {
334 if (!_gotHashCode)
335 {
336 int hashCode = 1;
337 foreach (object obj in this)
338 hashCode = 31 * hashCode + (obj == null ? 0 : obj.GetHashCode());
339 _hashCode = hashCode;
340 _gotHashCode = true;
341 }
342 return _hashCode;
343 }
344
345 public override bool Equals(object obj)
346 {
347 if (!(obj is ArrayList))
348 return false;
349
350 ArrayList objList = (ArrayList)obj;
351 if (objList.Count != Count)
352 return false;
353
354 for (int i = 0; i < Count; ++i)
355 {
356 object value = objList[i];
357 if (value == null)
358 {
359 if (this[i] != null)
360 return false;
361 }
362 else
363 {
364 if (!value.Equals(this[i]))
365 return false;
366 }
367 }
368 return true;
369 }
370 }
371
372 /// <summary>
373 /// If we keep an index on value, return the value, or null if we don't index it.
374 /// </summary>
375 /// <param name="value">the term to examine. Assume you already called YP.getValue(value)</param>
376 /// <returns></returns>
377 public static object getIndexValue(object value)
378 {
379 if (value is Atom || value is string || value is Int32 || value is DateTime)
380 return value;
381 else
382 return null;
383 }
384 }
385}
generated by cgit v1.1 at 2025-03-05 14:41:13 +0000