From d22a54a19568f8d5e9b6dab1f76f9c5c58682aa5 Mon Sep 17 00:00:00 2001 From: Jeff Ames Date: Sun, 1 Jun 2008 03:01:33 +0000 Subject: Update svn properties. --- .../Compiler/YieldProlog/IndexedAnswers.cs | 576 ++++++++++----------- 1 file changed, 288 insertions(+), 288 deletions(-) (limited to 'OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs') diff --git a/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs b/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs index 3eac5fa..05b0a01 100644 --- a/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs +++ b/OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs @@ -1,288 +1,288 @@ -/* - * Copyright (C) 2007-2008, Jeff Thompson - * - * All rights reserved. - * - * Redistribution and use in source and binary forms, with or without - * modification, are permitted provided that the following conditions are met: - * - * * Redistributions of source code must retain the above copyright - * notice, this list of conditions and the following disclaimer. - * * Redistributions in binary form must reproduce the above copyright - * notice, this list of conditions and the following disclaimer in the - * documentation and/or other materials provided with the distribution. - * * Neither the name of the copyright holder nor the names of its contributors - * may be used to endorse or promote products derived from this software - * without specific prior written permission. - * - * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS - * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT - * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR - * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR - * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, - * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, - * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR - * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF - * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING - * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS - * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. - */ - -using System; -using System.Collections; -using System.Collections.Generic; - -namespace OpenSim.Region.ScriptEngine.DotNetEngine.Compiler.YieldProlog -{ - /// - /// An IndexedAnswers holds answers to a query based on the values of index arguments. - /// - public class IndexedAnswers : YP.IClause - { - // addAnswer adds the answer here and indexes it later. - private List _allAnswers = new List(); - // The key has the arity of answers with non-null values for each indexed arg. The value - // is a list of the matching answers. The signature is implicit in the pattern on non-null index args. - private Dictionary> _indexedAnswers = - new Dictionary>(); - // Keeps track of whether we have started adding entries to _indexedAnswers for the signature. - private Dictionary _gotAnswersForSignature = new Dictionary(); - private const int MAX_INDEX_ARGS = 31; - - public IndexedAnswers() - { - } - - /// - /// Elements of answer must be ground, since arguments with unbound variables make this - /// into a dynamic rule which we don't index. - /// - /// - public void addAnswer(object[] answer) - { - // Store a copy of the answer array. - object[] answerCopy = new object[answer.Length]; - Variable.CopyStore copyStore = new Variable.CopyStore(); - for (int i = 0; i < answer.Length; ++i) - answerCopy[i] = YP.makeCopy(answer[i], copyStore); - if (copyStore.getNUniqueVariables() > 0) - throw new InvalidOperationException - ("Elements of answer must be ground, but found " + copyStore.getNUniqueVariables() + - " unbound variables"); - _allAnswers.Add(answerCopy); - - // If match has already indexed answers for a signature, we need to add - // this to the existing indexed answers. - foreach(int signature in _gotAnswersForSignature.Keys) - indexAnswerForSignature(answerCopy, signature); - } - - private void indexAnswerForSignature(object[] answer, int signature) - { - // First find out which of the answer values can be used as an index. - object[] indexValues = new object[answer.Length]; - for (int i = 0; i < answer.Length; ++i) - { - // We limit the number of indexed args in a 32-bit signature. - if (i >= MAX_INDEX_ARGS) - indexValues[i] = null; - else - indexValues[i] = getIndexValue(YP.getValue(answer[i])); - } - - // We need an entry in indexArgs from indexValues for each 1 bit in signature. - HashedList indexArgs = new HashedList(indexValues.Length); - for (int i = 0; i < indexValues.Length; ++i) - { - if ((signature & (1 << i)) == 0) - indexArgs.Add(null); - else - { - if (indexValues[i] == null) - // The signature wants an index value here, but we don't have one so - // we can't add it as an answer for this signature. - return; - else - indexArgs.Add(indexValues[i]); - } - } - - // Add the answer to the answers list for indexArgs, creating the entry if needed. - List answers; - if (!_indexedAnswers.TryGetValue(indexArgs, out answers)) - { - answers = new List(); - _indexedAnswers[indexArgs] = answers; - } - answers.Add(answer); - } - - public IEnumerable match(object[] arguments) - { - // Set up indexArgs, up to arg position MAX_INDEX_ARGS. The signature has a 1 bit for - // each non-null index arg. - HashedList indexArgs = new HashedList(arguments.Length); - bool gotAllIndexArgs = true; - int signature = 0; - for (int i = 0; i < arguments.Length; ++i) - { - object indexValue = null; - if (i < MAX_INDEX_ARGS) - { - // We limit the number of args in a 32-bit signature. - indexValue = getIndexValue(YP.getValue(arguments[i])); - if (indexValue != null) - signature += (1 << i); - } - if (indexValue == null) - gotAllIndexArgs = false; - indexArgs.Add(indexValue); - } - - List answers; - if (signature == 0) - // No index args, so we have to match from _allAnswers. - answers = _allAnswers; - else - { - if (!_gotAnswersForSignature.ContainsKey(signature)) - { - // We need to create the entry in _indexedAnswers. - foreach (object[] answer in _allAnswers) - indexAnswerForSignature(answer, signature); - // Mark that we did this signature. - _gotAnswersForSignature[signature] = null; - } - if (!_indexedAnswers.TryGetValue(indexArgs, out answers)) - yield break; - } - - if (gotAllIndexArgs) - { - // All the arguments were already bound, so we don't need to do bindings. - yield return false; - yield break; - } - - // Find matches in answers. - IEnumerator[] iterators = new IEnumerator[arguments.Length]; - foreach (object[] answer in answers) - { - bool gotMatch = true; - int nIterators = 0; - // Try to bind all the arguments. - for (int i = 0; i < arguments.Length; ++i) - { - if (indexArgs[i] != null) - // We already matched this argument by looking up _indexedAnswers. - continue; - - IEnumerator iterator = YP.unify(arguments[i], answer[i]).GetEnumerator(); - iterators[nIterators++] = iterator; - // MoveNext() is true if YP.unify succeeds. - if (!iterator.MoveNext()) - { - gotMatch = false; - break; - } - } - - try - { - if (gotMatch) - yield return false; - } - finally - { - // Manually finalize all the iterators. - for (int i = 0; i < nIterators; ++i) - iterators[i].Dispose(); - } - } - } - - /// - /// A HashedList extends an ArrayList with methods to get a hash and to check equality - /// based on the elements of the list. - /// - public class HashedList : ArrayList - { - private bool _gotHashCode = false; - private int _hashCode; - - public HashedList() - : base() - { - } - - public HashedList(int capacity) - : base(capacity) - { - } - - public HashedList(ICollection c) - : base(c) - { - } - - // Debug: Should override all the other methods that change this. - public override int Add(object value) - { - _gotHashCode = false; - return base.Add(value); - } - - public override int GetHashCode() - { - if (!_gotHashCode) - { - int hashCode = 1; - foreach (object obj in this) - hashCode = 31 * hashCode + (obj == null ? 0 : obj.GetHashCode()); - _hashCode = hashCode; - _gotHashCode = true; - } - return _hashCode; - } - - public override bool Equals(object obj) - { - if (!(obj is ArrayList)) - return false; - - ArrayList objList = (ArrayList)obj; - if (objList.Count != Count) - return false; - - for (int i = 0; i < Count; ++i) - { - object value = objList[i]; - if (value == null) - { - if (this[i] != null) - return false; - } - else - { - if (!value.Equals(this[i])) - return false; - } - } - return true; - } - } - - /// - /// If we keep an index on value, return the value, or null if we don't index it. - /// - /// the term to examine. Assume you already called YP.getValue(value) - /// - public static object getIndexValue(object value) - { - if (value is Atom || value is string || value is Int32 || value is DateTime) - return value; - else - return null; - } - } -} +/* + * Copyright (C) 2007-2008, Jeff Thompson + * + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * * Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * * Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * * Neither the name of the copyright holder nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR + * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, + * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, + * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR + * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF + * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING + * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +using System; +using System.Collections; +using System.Collections.Generic; + +namespace OpenSim.Region.ScriptEngine.DotNetEngine.Compiler.YieldProlog +{ + /// + /// An IndexedAnswers holds answers to a query based on the values of index arguments. + /// + public class IndexedAnswers : YP.IClause + { + // addAnswer adds the answer here and indexes it later. + private List _allAnswers = new List(); + // The key has the arity of answers with non-null values for each indexed arg. The value + // is a list of the matching answers. The signature is implicit in the pattern on non-null index args. + private Dictionary> _indexedAnswers = + new Dictionary>(); + // Keeps track of whether we have started adding entries to _indexedAnswers for the signature. + private Dictionary _gotAnswersForSignature = new Dictionary(); + private const int MAX_INDEX_ARGS = 31; + + public IndexedAnswers() + { + } + + /// + /// Elements of answer must be ground, since arguments with unbound variables make this + /// into a dynamic rule which we don't index. + /// + /// + public void addAnswer(object[] answer) + { + // Store a copy of the answer array. + object[] answerCopy = new object[answer.Length]; + Variable.CopyStore copyStore = new Variable.CopyStore(); + for (int i = 0; i < answer.Length; ++i) + answerCopy[i] = YP.makeCopy(answer[i], copyStore); + if (copyStore.getNUniqueVariables() > 0) + throw new InvalidOperationException + ("Elements of answer must be ground, but found " + copyStore.getNUniqueVariables() + + " unbound variables"); + _allAnswers.Add(answerCopy); + + // If match has already indexed answers for a signature, we need to add + // this to the existing indexed answers. + foreach(int signature in _gotAnswersForSignature.Keys) + indexAnswerForSignature(answerCopy, signature); + } + + private void indexAnswerForSignature(object[] answer, int signature) + { + // First find out which of the answer values can be used as an index. + object[] indexValues = new object[answer.Length]; + for (int i = 0; i < answer.Length; ++i) + { + // We limit the number of indexed args in a 32-bit signature. + if (i >= MAX_INDEX_ARGS) + indexValues[i] = null; + else + indexValues[i] = getIndexValue(YP.getValue(answer[i])); + } + + // We need an entry in indexArgs from indexValues for each 1 bit in signature. + HashedList indexArgs = new HashedList(indexValues.Length); + for (int i = 0; i < indexValues.Length; ++i) + { + if ((signature & (1 << i)) == 0) + indexArgs.Add(null); + else + { + if (indexValues[i] == null) + // The signature wants an index value here, but we don't have one so + // we can't add it as an answer for this signature. + return; + else + indexArgs.Add(indexValues[i]); + } + } + + // Add the answer to the answers list for indexArgs, creating the entry if needed. + List answers; + if (!_indexedAnswers.TryGetValue(indexArgs, out answers)) + { + answers = new List(); + _indexedAnswers[indexArgs] = answers; + } + answers.Add(answer); + } + + public IEnumerable match(object[] arguments) + { + // Set up indexArgs, up to arg position MAX_INDEX_ARGS. The signature has a 1 bit for + // each non-null index arg. + HashedList indexArgs = new HashedList(arguments.Length); + bool gotAllIndexArgs = true; + int signature = 0; + for (int i = 0; i < arguments.Length; ++i) + { + object indexValue = null; + if (i < MAX_INDEX_ARGS) + { + // We limit the number of args in a 32-bit signature. + indexValue = getIndexValue(YP.getValue(arguments[i])); + if (indexValue != null) + signature += (1 << i); + } + if (indexValue == null) + gotAllIndexArgs = false; + indexArgs.Add(indexValue); + } + + List answers; + if (signature == 0) + // No index args, so we have to match from _allAnswers. + answers = _allAnswers; + else + { + if (!_gotAnswersForSignature.ContainsKey(signature)) + { + // We need to create the entry in _indexedAnswers. + foreach (object[] answer in _allAnswers) + indexAnswerForSignature(answer, signature); + // Mark that we did this signature. + _gotAnswersForSignature[signature] = null; + } + if (!_indexedAnswers.TryGetValue(indexArgs, out answers)) + yield break; + } + + if (gotAllIndexArgs) + { + // All the arguments were already bound, so we don't need to do bindings. + yield return false; + yield break; + } + + // Find matches in answers. + IEnumerator[] iterators = new IEnumerator[arguments.Length]; + foreach (object[] answer in answers) + { + bool gotMatch = true; + int nIterators = 0; + // Try to bind all the arguments. + for (int i = 0; i < arguments.Length; ++i) + { + if (indexArgs[i] != null) + // We already matched this argument by looking up _indexedAnswers. + continue; + + IEnumerator iterator = YP.unify(arguments[i], answer[i]).GetEnumerator(); + iterators[nIterators++] = iterator; + // MoveNext() is true if YP.unify succeeds. + if (!iterator.MoveNext()) + { + gotMatch = false; + break; + } + } + + try + { + if (gotMatch) + yield return false; + } + finally + { + // Manually finalize all the iterators. + for (int i = 0; i < nIterators; ++i) + iterators[i].Dispose(); + } + } + } + + /// + /// A HashedList extends an ArrayList with methods to get a hash and to check equality + /// based on the elements of the list. + /// + public class HashedList : ArrayList + { + private bool _gotHashCode = false; + private int _hashCode; + + public HashedList() + : base() + { + } + + public HashedList(int capacity) + : base(capacity) + { + } + + public HashedList(ICollection c) + : base(c) + { + } + + // Debug: Should override all the other methods that change this. + public override int Add(object value) + { + _gotHashCode = false; + return base.Add(value); + } + + public override int GetHashCode() + { + if (!_gotHashCode) + { + int hashCode = 1; + foreach (object obj in this) + hashCode = 31 * hashCode + (obj == null ? 0 : obj.GetHashCode()); + _hashCode = hashCode; + _gotHashCode = true; + } + return _hashCode; + } + + public override bool Equals(object obj) + { + if (!(obj is ArrayList)) + return false; + + ArrayList objList = (ArrayList)obj; + if (objList.Count != Count) + return false; + + for (int i = 0; i < Count; ++i) + { + object value = objList[i]; + if (value == null) + { + if (this[i] != null) + return false; + } + else + { + if (!value.Equals(this[i])) + return false; + } + } + return true; + } + } + + /// + /// If we keep an index on value, return the value, or null if we don't index it. + /// + /// the term to examine. Assume you already called YP.getValue(value) + /// + public static object getIndexValue(object value) + { + if (value is Atom || value is string || value is Int32 || value is DateTime) + return value; + else + return null; + } + } +} -- cgit v1.1