Mantis#1314. Thank you kindly, Kinoc for YieldProlog.

I have added everything *except* the patch to .../LSL/Compiler.cs. The Compiler.cs patch has a namespace issue. Lets make a second patch to close the gap.
author: Charles Krinke 2008-05-31 17:52:44 +0000
committer: Charles Krinke 2008-05-31 17:52:44 +0000
commit: 25b7d9944d5875e1887eed156f31dd5779761265 (patch)
tree: 2c4f6f066ef2b5f60d399ab4862ed7b9dbe0c78f /OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs
parent: * Implements UserServer logoff in a few situations (diff)
download: opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.zip
opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.tar.gz
opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.tar.bz2
opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.tar.xz
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 @@
+/*
+ * 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
+{
+    /// <summary>
+    /// An IndexedAnswers holds answers to a query based on the values of index arguments.
+    /// </summary>
+    public class IndexedAnswers : YP.IClause
+    {
+        // addAnswer adds the answer here and indexes it later.
+        private List<object[]> _allAnswers = new List<object[]>();
+        // 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<HashedList, List<object[]>> _indexedAnswers =
+            new Dictionary<HashedList, List<object[]>>();
+        // Keeps track of whether we have started adding entries to _indexedAnswers for the signature.
+        private Dictionary<int, object> _gotAnswersForSignature = new Dictionary<int, object>();
+        private const int MAX_INDEX_ARGS = 31;
+        public IndexedAnswers()
+        {
+        }
+        /// <summary>
+        /// Elements of answer must be ground, since arguments with unbound variables make this
+        /// into a dynamic rule which we don't index.
+        /// </summary>
+        /// <param name="answer"></param>
+        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<object[]> answers;
+            if (!_indexedAnswers.TryGetValue(indexArgs, out answers))
+            {
+                answers = new List<object[]>();
+                _indexedAnswers[indexArgs] = answers;
+            }
+            answers.Add(answer);
+        }
+        public IEnumerable<bool> 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<object[]> 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<bool>[] iterators = new IEnumerator<bool>[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<bool> 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();
+                }
+            }
+        }
+        /// <summary>
+        /// A HashedList extends an ArrayList with methods to get a hash and to check equality
+        /// based on the elements of the list.
+        /// </summary>
+        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;
+            }
+        }
+        /// <summary>
+        /// If we keep an index on value, return the value, or null if we don't index it.
+        /// </summary>
+        /// <param name="value">the term to examine.  Assume you already called YP.getValue(value)</param>
+        /// <returns></returns>
+        public static object getIndexValue(object value)
+        {
+            if (value is Atom || value is string || value is Int32 || value is DateTime)
+                return value;
+            else
+                return null;
+        }
+    }
+}
author	Charles Krinke	2008-05-31 17:52:44 +0000
committer	Charles Krinke	2008-05-31 17:52:44 +0000
commit	25b7d9944d5875e1887eed156f31dd5779761265 (patch)
tree	2c4f6f066ef2b5f60d399ab4862ed7b9dbe0c78f /OpenSim/Region/ScriptEngine/DotNetEngine/Compiler/YieldProlog/IndexedAnswers.cs
parent	* Implements UserServer logoff in a few situations (diff)
download	opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.zip opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.tar.gz opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.tar.bz2 opensim-SC_OLD-25b7d9944d5875e1887eed156f31dd5779761265.tar.xz

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
	31	using System;
	32	using System.Collections;
	33	using System.Collections.Generic;
	34
	35	namespace 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	}