IndexedAnswers.cs 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385
  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. using System;
  31. using System.Collections;
  32. using System.Collections.Generic;
  33. namespace OpenSim.Region.ScriptEngine.Shared.YieldProlog
  34. {
  35. /// <summary>
  36. /// An IndexedAnswers holds answers to a query based on the values of index arguments.
  37. /// </summary>
  38. public class IndexedAnswers : YP.IClause
  39. {
  40. private int _arity;
  41. // addAnswer adds the answer here and indexes it later.
  42. private List<object[]> _allAnswers = new List<object[]>();
  43. // The key has the arity of answers with non-null values for each indexed arg. The value
  44. // is a list of the matching answers. The signature is implicit in the pattern on non-null index args.
  45. private Dictionary<HashedList, List<object[]>> _indexedAnswers =
  46. new Dictionary<HashedList, List<object[]>>();
  47. // Keeps track of whether we have started adding entries to _indexedAnswers for the signature.
  48. private Dictionary<int, object> _gotAnswersForSignature = new Dictionary<int, object>();
  49. private const int MAX_INDEX_ARGS = 31;
  50. public IndexedAnswers(int arity)
  51. {
  52. _arity = arity;
  53. }
  54. /// <summary>
  55. /// Append the answer to the list and update the indexes, if any.
  56. /// Elements of answer must be ground, since arguments with unbound variables make this
  57. /// into a dynamic rule which we don't index.
  58. /// </summary>
  59. /// <param name="answer"></param>
  60. public void addAnswer(object[] answer)
  61. {
  62. addOrPrependAnswer(answer, false);
  63. }
  64. /// <summary>
  65. /// Prepend the answer to the list and clear the indexes so that they must be re-computed
  66. /// on the next call to match. (Only addAnswer will maintain the indexes while adding answers.)
  67. /// Elements of answer must be ground, since arguments with unbound variables make this
  68. /// into a dynamic rule which we don't index.
  69. /// </summary>
  70. /// <param name="answer"></param>
  71. public void prependAnswer(object[] answer)
  72. {
  73. addOrPrependAnswer(answer, true);
  74. }
  75. /// <summary>
  76. /// Do the work of addAnswer or prependAnswer.
  77. /// </summary>
  78. /// <param name="answer"></param>
  79. private void addOrPrependAnswer(object[] answer, bool prepend)
  80. {
  81. if (answer.Length != _arity)
  82. return;
  83. // Store a copy of the answer array.
  84. object[] answerCopy = new object[answer.Length];
  85. Variable.CopyStore copyStore = new Variable.CopyStore();
  86. for (int i = 0; i < answer.Length; ++i)
  87. answerCopy[i] = YP.makeCopy(answer[i], copyStore);
  88. if (copyStore.getNUniqueVariables() > 0)
  89. throw new InvalidOperationException
  90. ("Elements of answer must be ground, but found " + copyStore.getNUniqueVariables() +
  91. " unbound variables");
  92. if (prepend)
  93. {
  94. _allAnswers.Insert(0, answerCopy);
  95. clearIndexes();
  96. }
  97. else
  98. {
  99. _allAnswers.Add(answerCopy);
  100. // If match has already indexed answers for a signature, we need to add
  101. // this to the existing indexed answers.
  102. foreach (int signature in _gotAnswersForSignature.Keys)
  103. indexAnswerForSignature(answerCopy, signature);
  104. }
  105. }
  106. private void indexAnswerForSignature(object[] answer, int signature)
  107. {
  108. // First find out which of the answer values can be used as an index.
  109. object[] indexValues = new object[answer.Length];
  110. for (int i = 0; i < answer.Length; ++i)
  111. {
  112. // We limit the number of indexed args in a 32-bit signature.
  113. if (i >= MAX_INDEX_ARGS)
  114. indexValues[i] = null;
  115. else
  116. indexValues[i] = getIndexValue(YP.getValue(answer[i]));
  117. }
  118. // We need an entry in indexArgs from indexValues for each 1 bit in signature.
  119. HashedList indexArgs = new HashedList(indexValues.Length);
  120. for (int i = 0; i < indexValues.Length; ++i)
  121. {
  122. if ((signature & (1 << i)) == 0)
  123. indexArgs.Add(null);
  124. else
  125. {
  126. if (indexValues[i] == null)
  127. // The signature wants an index value here, but we don't have one so
  128. // we can't add it as an answer for this signature.
  129. return;
  130. else
  131. indexArgs.Add(indexValues[i]);
  132. }
  133. }
  134. // Add the answer to the answers list for indexArgs, creating the entry if needed.
  135. List<object[]> answers;
  136. if (!_indexedAnswers.TryGetValue(indexArgs, out answers))
  137. {
  138. answers = new List<object[]>();
  139. _indexedAnswers[indexArgs] = answers;
  140. }
  141. answers.Add(answer);
  142. }
  143. public IEnumerable<bool> match(object[] arguments)
  144. {
  145. if (arguments.Length != _arity)
  146. yield break;
  147. // Set up indexArgs, up to arg position MAX_INDEX_ARGS. The signature has a 1 bit for
  148. // each non-null index arg.
  149. HashedList indexArgs = new HashedList(arguments.Length);
  150. bool gotAllIndexArgs = true;
  151. int signature = 0;
  152. for (int i = 0; i < arguments.Length; ++i)
  153. {
  154. object indexValue = null;
  155. if (i < MAX_INDEX_ARGS)
  156. {
  157. // We limit the number of args in a 32-bit signature.
  158. indexValue = getIndexValue(YP.getValue(arguments[i]));
  159. if (indexValue != null)
  160. signature += (1 << i);
  161. }
  162. if (indexValue == null)
  163. gotAllIndexArgs = false;
  164. indexArgs.Add(indexValue);
  165. }
  166. List<object[]> answers;
  167. if (signature == 0)
  168. // No index args, so we have to match from _allAnswers.
  169. answers = _allAnswers;
  170. else
  171. {
  172. if (!_gotAnswersForSignature.ContainsKey(signature))
  173. {
  174. // We need to create the entry in _indexedAnswers.
  175. foreach (object[] answer in _allAnswers)
  176. indexAnswerForSignature(answer, signature);
  177. // Mark that we did this signature.
  178. _gotAnswersForSignature[signature] = null;
  179. }
  180. if (!_indexedAnswers.TryGetValue(indexArgs, out answers))
  181. yield break;
  182. }
  183. if (gotAllIndexArgs)
  184. {
  185. // All the arguments were already bound, so we don't need to do bindings.
  186. yield return false;
  187. yield break;
  188. }
  189. // Find matches in answers.
  190. IEnumerator<bool>[] iterators = new IEnumerator<bool>[arguments.Length];
  191. // Debug: If the caller asserts another answer into this same predicate during yield, the iterator
  192. // over clauses will be corrupted. Should we take the time to copy answers?
  193. foreach (object[] answer in answers)
  194. {
  195. bool gotMatch = true;
  196. int nIterators = 0;
  197. // Try to bind all the arguments.
  198. for (int i = 0; i < arguments.Length; ++i)
  199. {
  200. if (indexArgs[i] != null)
  201. // We already matched this argument by looking up _indexedAnswers.
  202. continue;
  203. IEnumerator<bool> iterator = YP.unify(arguments[i], answer[i]).GetEnumerator();
  204. iterators[nIterators++] = iterator;
  205. // MoveNext() is true if YP.unify succeeds.
  206. if (!iterator.MoveNext())
  207. {
  208. gotMatch = false;
  209. break;
  210. }
  211. }
  212. try
  213. {
  214. if (gotMatch)
  215. yield return false;
  216. }
  217. finally
  218. {
  219. // Manually finalize all the iterators.
  220. for (int i = 0; i < nIterators; ++i)
  221. iterators[i].Dispose();
  222. }
  223. }
  224. }
  225. public IEnumerable<bool> clause(object Head, object Body)
  226. {
  227. Head = YP.getValue(Head);
  228. if (Head is Variable)
  229. throw new PrologException("instantiation_error", "Head is an unbound variable");
  230. object[] arguments = YP.getFunctorArgs(Head);
  231. // We always match Head from _allAnswers, and the Body is Atom.a("true").
  232. #pragma warning disable 0168, 0219
  233. foreach (bool l1 in YP.unify(Body, Atom.a("true")))
  234. {
  235. // The caller can assert another answer into this same predicate during yield, so we have to
  236. // make a copy of the answers.
  237. foreach (object[] answer in _allAnswers.ToArray())
  238. {
  239. foreach (bool l2 in YP.unifyArrays(arguments, answer))
  240. yield return false;
  241. }
  242. }
  243. #pragma warning restore 0168, 0219
  244. }
  245. public IEnumerable<bool> retract(object Head, object Body)
  246. {
  247. Head = YP.getValue(Head);
  248. if (Head is Variable)
  249. throw new PrologException("instantiation_error", "Head is an unbound variable");
  250. object[] arguments = YP.getFunctorArgs(Head);
  251. // We always match Head from _allAnswers, and the Body is Atom.a("true").
  252. #pragma warning disable 0168, 0219
  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. {
  261. _allAnswers.Remove(answer);
  262. clearIndexes();
  263. yield return false;
  264. }
  265. }
  266. }
  267. #pragma warning restore 0168, 0219
  268. }
  269. /// <summary>
  270. /// After retracting or prepending an answer in _allAnswers, the indexes are invalid, so clear them.
  271. /// </summary>
  272. private void clearIndexes()
  273. {
  274. _indexedAnswers.Clear();
  275. _gotAnswersForSignature.Clear();
  276. }
  277. /// <summary>
  278. /// A HashedList extends an ArrayList with methods to get a hash and to check equality
  279. /// based on the elements of the list.
  280. /// </summary>
  281. public class HashedList : ArrayList
  282. {
  283. private bool _gotHashCode = false;
  284. private int _hashCode;
  285. public HashedList()
  286. : base()
  287. {
  288. }
  289. public HashedList(int capacity)
  290. : base(capacity)
  291. {
  292. }
  293. public HashedList(ICollection c)
  294. : base(c)
  295. {
  296. }
  297. // Debug: Should override all the other methods that change this.
  298. public override int Add(object value)
  299. {
  300. _gotHashCode = false;
  301. return base.Add(value);
  302. }
  303. public override int GetHashCode()
  304. {
  305. if (!_gotHashCode)
  306. {
  307. int hashCode = 1;
  308. foreach (object obj in this)
  309. hashCode = 31 * hashCode + (obj == null ? 0 : obj.GetHashCode());
  310. _hashCode = hashCode;
  311. _gotHashCode = true;
  312. }
  313. return _hashCode;
  314. }
  315. public override bool Equals(object obj)
  316. {
  317. if (!(obj is ArrayList))
  318. return false;
  319. ArrayList objList = (ArrayList)obj;
  320. if (objList.Count != Count)
  321. return false;
  322. for (int i = 0; i < Count; ++i)
  323. {
  324. object value = objList[i];
  325. if (value == null)
  326. {
  327. if (this[i] != null)
  328. return false;
  329. }
  330. else
  331. {
  332. if (!value.Equals(this[i]))
  333. return false;
  334. }
  335. }
  336. return true;
  337. }
  338. }
  339. /// <summary>
  340. /// If we keep an index on value, return the value, or null if we don't index it.
  341. /// </summary>
  342. /// <param name="value">the term to examine. Assume you already called YP.getValue(value)</param>
  343. /// <returns></returns>
  344. public static object getIndexValue(object value)
  345. {
  346. if (value is Atom || value is string || value is Int32 || value is DateTime)
  347. return value;
  348. else
  349. return null;
  350. }
  351. }
  352. }