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.cs288
1 files changed, 288 insertions, 0 deletions
diff --git a/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs b/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs
new file mode 100644
index 0000000..3eac5fa
--- /dev/null
+++ b/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs
@@ -0,0 +1,288 @@
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 // addAnswer adds the answer here and indexes it later.
43 private List<object[]> _allAnswers = new List<object[]>();
44 // The key has the arity of answers with non-null values for each indexed arg. The value
45 // is a list of the matching answers. The signature is implicit in the pattern on non-null index args.
46 private Dictionary<HashedList, List<object[]>> _indexedAnswers =
47 new Dictionary<HashedList, List<object[]>>();
48 // Keeps track of whether we have started adding entries to _indexedAnswers for the signature.
49 private Dictionary<int, object> _gotAnswersForSignature = new Dictionary<int, object>();
50 private const int MAX_INDEX_ARGS = 31;
51
52 public IndexedAnswers()
53 {
54 }
55
56 /// <summary>
57 /// Elements of answer must be ground, since arguments with unbound variables make this
58 /// into a dynamic rule which we don't index.
59 /// </summary>
60 /// <param name="answer"></param>
61 public void addAnswer(object[] answer)
62 {
63 // Store a copy of the answer array.
64 object[] answerCopy = new object[answer.Length];
65 Variable.CopyStore copyStore = new Variable.CopyStore();
66 for (int i = 0; i < answer.Length; ++i)
67 answerCopy[i] = YP.makeCopy(answer[i], copyStore);
68 if (copyStore.getNUniqueVariables() > 0)
69 throw new InvalidOperationException
70 ("Elements of answer must be ground, but found " + copyStore.getNUniqueVariables() +
71 " unbound variables");
72 _allAnswers.Add(answerCopy);
73
74 // If match has already indexed answers for a signature, we need to add
75 // this to the existing indexed answers.
76 foreach(int signature in _gotAnswersForSignature.Keys)
77 indexAnswerForSignature(answerCopy, signature);
78 }
79
80 private void indexAnswerForSignature(object[] answer, int signature)
81 {
82 // First find out which of the answer values can be used as an index.
83 object[] indexValues = new object[answer.Length];
84 for (int i = 0; i < answer.Length; ++i)
85 {
86 // We limit the number of indexed args in a 32-bit signature.
87 if (i >= MAX_INDEX_ARGS)
88 indexValues[i] = null;
89 else
90 indexValues[i] = getIndexValue(YP.getValue(answer[i]));
91 }
92
93 // We need an entry in indexArgs from indexValues for each 1 bit in signature.
94 HashedList indexArgs = new HashedList(indexValues.Length);
95 for (int i = 0; i < indexValues.Length; ++i)
96 {
97 if ((signature & (1 << i)) == 0)
98 indexArgs.Add(null);
99 else
100 {
101 if (indexValues[i] == null)
102 // The signature wants an index value here, but we don't have one so
103 // we can't add it as an answer for this signature.
104 return;
105 else
106 indexArgs.Add(indexValues[i]);
107 }
108 }
109
110 // Add the answer to the answers list for indexArgs, creating the entry if needed.
111 List<object[]> answers;
112 if (!_indexedAnswers.TryGetValue(indexArgs, out answers))
113 {
114 answers = new List<object[]>();
115 _indexedAnswers[indexArgs] = answers;
116 }
117 answers.Add(answer);
118 }
119
120 public IEnumerable<bool> match(object[] arguments)
121 {
122 // Set up indexArgs, up to arg position MAX_INDEX_ARGS. The signature has a 1 bit for
123 // each non-null index arg.
124 HashedList indexArgs = new HashedList(arguments.Length);
125 bool gotAllIndexArgs = true;
126 int signature = 0;
127 for (int i = 0; i < arguments.Length; ++i)
128 {
129 object indexValue = null;
130 if (i < MAX_INDEX_ARGS)
131 {
132 // We limit the number of args in a 32-bit signature.
133 indexValue = getIndexValue(YP.getValue(arguments[i]));
134 if (indexValue != null)
135 signature += (1 << i);
136 }
137 if (indexValue == null)
138 gotAllIndexArgs = false;
139 indexArgs.Add(indexValue);
140 }
141
142 List<object[]> answers;
143 if (signature == 0)
144 // No index args, so we have to match from _allAnswers.
145 answers = _allAnswers;
146 else
147 {
148 if (!_gotAnswersForSignature.ContainsKey(signature))
149 {
150 // We need to create the entry in _indexedAnswers.
151 foreach (object[] answer in _allAnswers)
152 indexAnswerForSignature(answer, signature);
153 // Mark that we did this signature.
154 _gotAnswersForSignature[signature] = null;
155 }
156 if (!_indexedAnswers.TryGetValue(indexArgs, out answers))
157 yield break;
158 }
159
160 if (gotAllIndexArgs)
161 {
162 // All the arguments were already bound, so we don't need to do bindings.
163 yield return false;
164 yield break;
165 }
166
167 // Find matches in answers.
168 IEnumerator<bool>[] iterators = new IEnumerator<bool>[arguments.Length];
169 foreach (object[] answer in answers)
170 {
171 bool gotMatch = true;
172 int nIterators = 0;
173 // Try to bind all the arguments.
174 for (int i = 0; i < arguments.Length; ++i)
175 {
176 if (indexArgs[i] != null)
177 // We already matched this argument by looking up _indexedAnswers.
178 continue;
179
180 IEnumerator<bool> iterator = YP.unify(arguments[i], answer[i]).GetEnumerator();
181 iterators[nIterators++] = iterator;
182 // MoveNext() is true if YP.unify succeeds.
183 if (!iterator.MoveNext())
184 {
185 gotMatch = false;
186 break;
187 }
188 }
189
190 try
191 {
192 if (gotMatch)
193 yield return false;
194 }
195 finally
196 {
197 // Manually finalize all the iterators.
198 for (int i = 0; i < nIterators; ++i)
199 iterators[i].Dispose();
200 }
201 }
202 }
203
204 /// <summary>
205 /// A HashedList extends an ArrayList with methods to get a hash and to check equality
206 /// based on the elements of the list.
207 /// </summary>
208 public class HashedList : ArrayList
209 {
210 private bool _gotHashCode = false;
211 private int _hashCode;
212
213 public HashedList()
214 : base()
215 {
216 }
217
218 public HashedList(int capacity)
219 : base(capacity)
220 {
221 }
222
223 public HashedList(ICollection c)
224 : base(c)
225 {
226 }
227
228 // Debug: Should override all the other methods that change this.
229 public override int Add(object value)
230 {
231 _gotHashCode = false;
232 return base.Add(value);
233 }
234
235 public override int GetHashCode()
236 {
237 if (!_gotHashCode)
238 {
239 int hashCode = 1;
240 foreach (object obj in this)
241 hashCode = 31 * hashCode + (obj == null ? 0 : obj.GetHashCode());
242 _hashCode = hashCode;
243 _gotHashCode = true;
244 }
245 return _hashCode;
246 }
247
248 public override bool Equals(object obj)
249 {
250 if (!(obj is ArrayList))
251 return false;
252
253 ArrayList objList = (ArrayList)obj;
254 if (objList.Count != Count)
255 return false;
256
257 for (int i = 0; i < Count; ++i)
258 {
259 object value = objList[i];
260 if (value == null)
261 {
262 if (this[i] != null)
263 return false;
264 }
265 else
266 {
267 if (!value.Equals(this[i]))
268 return false;
269 }
270 }
271 return true;
272 }
273 }
274
275 /// <summary>
276 /// If we keep an index on value, return the value, or null if we don't index it.
277 /// </summary>
278 /// <param name="value">the term to examine. Assume you already called YP.getValue(value)</param>
279 /// <returns></returns>
280 public static object getIndexValue(object value)
281 {
282 if (value is Atom || value is string || value is Int32 || value is DateTime)
283 return value;
284 else
285 return null;
286 }
287 }
288}
generated by cgit v1.1 at 2024-11-16 20:29:19 +0000