XMRArray.cs 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572
  1. /*
  2. * Copyright (c) Contributors, http://opensimulator.org/
  3. * See CONTRIBUTORS.TXT for a full list of copyright holders.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. * * Redistributions of source code must retain the above copyright
  8. * notice, this list of conditions and the following disclaimer.
  9. * * Redistributions in binary form must reproduce the above copyright
  10. * notice, this list of conditions and the following disclaimer in the
  11. * documentation and/or other materials provided with the distribution.
  12. * * Neither the name of the OpenSimulator Project nor the
  13. * names of its contributors may be used to endorse or promote products
  14. * derived from this software without specific prior written permission.
  15. *
  16. * THIS SOFTWARE IS PROVIDED BY THE DEVELOPERS ``AS IS'' AND ANY
  17. * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
  18. * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  19. * DISCLAIMED. IN NO EVENT SHALL THE CONTRIBUTORS BE LIABLE FOR ANY
  20. * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
  21. * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  22. * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
  23. * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  24. * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
  25. * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  26. */
  27. using System;
  28. using System.Collections.Generic;
  29. using System.IO;
  30. using System.Text;
  31. using LSL_Float = OpenSim.Region.ScriptEngine.Shared.LSL_Types.LSLFloat;
  32. using LSL_Integer = OpenSim.Region.ScriptEngine.Shared.LSL_Types.LSLInteger;
  33. using LSL_Key = OpenSim.Region.ScriptEngine.Shared.LSL_Types.LSLString;
  34. using LSL_List = OpenSim.Region.ScriptEngine.Shared.LSL_Types.list;
  35. using LSL_Rotation = OpenSim.Region.ScriptEngine.Shared.LSL_Types.Quaternion;
  36. using LSL_String = OpenSim.Region.ScriptEngine.Shared.LSL_Types.LSLString;
  37. using LSL_Vector = OpenSim.Region.ScriptEngine.Shared.LSL_Types.Vector3;
  38. // This class exists in the main app domain
  39. //
  40. namespace OpenSim.Region.ScriptEngine.Yengine
  41. {
  42. /**
  43. * @brief Array objects.
  44. */
  45. public class XMR_Array
  46. {
  47. private const int EMPTYHEAP = 64;
  48. private const int ENTRYHEAP = 24;
  49. private bool enumrValid; // true: enumr set to return array[arrayValid]
  50. // false: array[0..arrayValid-1] is all there is
  51. private SortedDictionary<object, object> dnary;
  52. private SortedDictionary<object, object>.Enumerator enumr;
  53. // enumerator used to fill 'array' past arrayValid to end of dictionary
  54. private int arrayValid; // number of elements in 'array' that have been filled in
  55. private KeyValuePair<object, object>[] array; // list of kvp's that have been returned by ForEach() since last modification
  56. private XMRInstAbstract inst; // script instance debited with heap use
  57. private int heapUse; // current heap use debit amount
  58. public static TokenTypeSDTypeDelegate countDelegate = new TokenTypeSDTypeDelegate(new TokenTypeInt(null), new TokenType[0]);
  59. public static TokenTypeSDTypeDelegate clearDelegate = new TokenTypeSDTypeDelegate(new TokenTypeVoid(null), new TokenType[0]);
  60. public static TokenTypeSDTypeDelegate indexDelegate = new TokenTypeSDTypeDelegate(new TokenTypeObject(null), new TokenType[] { new TokenTypeInt(null) });
  61. public static TokenTypeSDTypeDelegate valueDelegate = new TokenTypeSDTypeDelegate(new TokenTypeObject(null), new TokenType[] { new TokenTypeInt(null) });
  62. public XMR_Array(XMRInstAbstract inst)
  63. {
  64. this.inst = inst;
  65. dnary = new SortedDictionary<object, object>(XMRArrayKeyComparer.singleton);
  66. heapUse = inst.UpdateArraysHeapUse(0, EMPTYHEAP);
  67. }
  68. ~XMR_Array()
  69. {
  70. heapUse = inst.UpdateLocalsHeapUse(heapUse, 0);
  71. }
  72. public static TokenType GetRValType(TokenName name)
  73. {
  74. if(name.val == "count")
  75. return new TokenTypeInt(name);
  76. if(name.val == "clear")
  77. return clearDelegate;
  78. if(name.val == "index")
  79. return indexDelegate;
  80. if(name.val == "value")
  81. return valueDelegate;
  82. return new TokenTypeVoid(name);
  83. }
  84. /**
  85. * @brief Handle 'array[index]' syntax to get or set an element of the dictionary.
  86. * Get returns null if element not defined, script sees type 'undef'.
  87. * Setting an element to null removes it.
  88. */
  89. public object GetByKey(object key)
  90. {
  91. object val;
  92. key = FixKey(key);
  93. if(!dnary.TryGetValue(key, out val))
  94. val = null;
  95. return val;
  96. }
  97. public void SetByKey(object key, object value)
  98. {
  99. key = FixKey(key);
  100. // Update heap use throwing an exception on failure
  101. // before making any changes to the array.
  102. int keysize = HeapTrackerObject.Size(key);
  103. int newheapuse = heapUse;
  104. object oldval;
  105. if(dnary.TryGetValue(key, out oldval))
  106. {
  107. newheapuse -= keysize + HeapTrackerObject.Size(oldval);
  108. }
  109. if(value != null)
  110. {
  111. newheapuse += keysize + HeapTrackerObject.Size(value);
  112. }
  113. heapUse = inst.UpdateArraysHeapUse(heapUse, newheapuse);
  114. // Save new value in array, replacing one of same key if there.
  115. // null means remove the value, ie, script did array[key] = undef.
  116. if (value != null)
  117. {
  118. dnary[key] = value;
  119. }
  120. else
  121. {
  122. dnary.Remove(key);
  123. // Shrink the enumeration array, but always leave at least one element.
  124. if((array != null) && (dnary.Count < array.Length / 2))
  125. {
  126. Array.Resize<KeyValuePair<object, object>>(ref array, array.Length / 2);
  127. }
  128. }
  129. // The enumeration array is invalid because the dictionary has been modified.
  130. // Next time a ForEach() call happens, it will repopulate 'array' as elements are retrieved.
  131. arrayValid = 0;
  132. }
  133. /**
  134. * @brief Converts an 'object' type to array, key, list, string, but disallows null,
  135. * as our language doesn't allow types other than 'object' to be null.
  136. * Value types (float, rotation, etc) don't need explicit check for null as
  137. * the C# runtime can't convert a null to a value type, and throws an exception.
  138. * But for any reference type (array, key, etc) we must manually check for null.
  139. */
  140. public static XMR_Array Obj2Array(object obj)
  141. {
  142. if(obj == null)
  143. throw new NullReferenceException();
  144. return (XMR_Array)obj;
  145. }
  146. public static LSL_Key Obj2Key(object obj)
  147. {
  148. if(obj == null)
  149. throw new NullReferenceException();
  150. return (LSL_Key)obj;
  151. }
  152. public static LSL_List Obj2List(object obj)
  153. {
  154. if(obj == null)
  155. throw new NullReferenceException();
  156. return (LSL_List)obj;
  157. }
  158. public static LSL_String Obj2String(object obj)
  159. {
  160. if(obj == null)
  161. throw new NullReferenceException();
  162. return obj.ToString();
  163. }
  164. /**
  165. * @brief remove all elements from the array.
  166. * sets everything to its 'just constructed' state.
  167. */
  168. public void __pub_clear()
  169. {
  170. heapUse = inst.UpdateArraysHeapUse(heapUse, EMPTYHEAP);
  171. dnary.Clear();
  172. enumrValid = false;
  173. arrayValid = 0;
  174. array = null;
  175. }
  176. /**
  177. * @brief return number of elements in the array.
  178. */
  179. public int __pub_count()
  180. {
  181. return dnary.Count;
  182. }
  183. /**
  184. * @brief Retrieve index (key) of an arbitrary element.
  185. * @param number = number of the element (0 based)
  186. * @returns null: array doesn't have that many elements
  187. * else: index (key) for that element
  188. */
  189. public object __pub_index(int number)
  190. {
  191. return ForEach(number) ? UnfixKey(array[number].Key) : null;
  192. }
  193. /**
  194. * @brief Retrieve value of an arbitrary element.
  195. * @param number = number of the element (0 based)
  196. * @returns null: array doesn't have that many elements
  197. * else: value for that element
  198. */
  199. public object __pub_value(int number)
  200. {
  201. return ForEach(number) ? array[number].Value : null;
  202. }
  203. /**
  204. * @brief Called in each iteration of a 'foreach' statement.
  205. * @param number = index of element to retrieve (0 = first one)
  206. * @returns false: element does not exist
  207. * true: element exists
  208. */
  209. private bool ForEach(int number)
  210. {
  211. // If we don't have any array, we can't have ever done
  212. // any calls here before, so allocate an array big enough
  213. // and set everything else to the beginning.
  214. if(array == null)
  215. {
  216. array = new KeyValuePair<object, object>[dnary.Count];
  217. arrayValid = 0;
  218. }
  219. // If dictionary modified since last enumeration, get a new enumerator.
  220. if(arrayValid == 0)
  221. {
  222. enumr = dnary.GetEnumerator();
  223. enumrValid = true;
  224. }
  225. // Make sure we have filled the array up enough for requested element.
  226. while((arrayValid <= number) && enumrValid && enumr.MoveNext())
  227. {
  228. if(arrayValid >= array.Length)
  229. {
  230. Array.Resize<KeyValuePair<object, object>>(ref array, dnary.Count);
  231. }
  232. array[arrayValid++] = enumr.Current;
  233. }
  234. // If we don't have that many elements, return end-of-array status.
  235. return number < arrayValid;
  236. }
  237. /**
  238. * @brief Transmit array out in such a way that it can be reconstructed,
  239. * including any in-progress ForEach() enumerations.
  240. */
  241. public delegate void SendArrayObjDelegate(object graph);
  242. public void SendArrayObj(SendArrayObjDelegate sendObj)
  243. {
  244. // Set the count then the elements themselves.
  245. // UnfixKey() because sendObj doesn't handle XMRArrayListKeys.
  246. sendObj(dnary.Count);
  247. foreach(KeyValuePair<object, object> kvp in dnary)
  248. {
  249. sendObj(UnfixKey(kvp.Key));
  250. sendObj(kvp.Value);
  251. }
  252. }
  253. /**
  254. * @brief Receive array in. Any previous contents are erased.
  255. * Set up such that any enumeration in progress will resume
  256. * at the exact spot and in the exact same order as they
  257. * were in on the sending side.
  258. */
  259. public delegate object RecvArrayObjDelegate();
  260. public void RecvArrayObj(RecvArrayObjDelegate recvObj)
  261. {
  262. heapUse = inst.UpdateArraysHeapUse(heapUse, EMPTYHEAP);
  263. // Cause any enumeration to refill the array from the sorted dictionary.
  264. // Since it is a sorted dictionary, any enumerations will be in the same
  265. // order as on the sending side.
  266. arrayValid = 0;
  267. enumrValid = false;
  268. // Fill dictionary.
  269. dnary.Clear();
  270. int count = (int)recvObj();
  271. while(--count >= 0)
  272. {
  273. object key = FixKey(recvObj());
  274. object val = recvObj();
  275. int htuse = HeapTrackerObject.Size(key) + HeapTrackerObject.Size(val);
  276. heapUse = inst.UpdateArraysHeapUse(heapUse, heapUse + htuse);
  277. dnary.Add(key, val);
  278. }
  279. }
  280. /**
  281. * We want our index values to be of consistent type, otherwise we get things like (LSL_Integer)1 != (int)1.
  282. * So strip off any LSL-ness from the types.
  283. * We also deep-strip any given lists used as keys (multi-dimensional arrays).
  284. */
  285. public static object FixKey(object key)
  286. {
  287. if(key is LSL_Integer)
  288. return (int)(LSL_Integer)key;
  289. if(key is LSL_Float)
  290. return (double)(LSL_Float)key;
  291. if(key is LSL_Key)
  292. return (string)(LSL_Key)key;
  293. if(key is LSL_String)
  294. return (string)(LSL_String)key;
  295. if(key is LSL_List)
  296. {
  297. object[] data = ((LSL_List)key).Data;
  298. if(data.Length == 1)
  299. return FixKey(data[0]);
  300. return new XMRArrayListKey((LSL_List)key);
  301. }
  302. return key; // int, double, string, LSL_Vector, LSL_Rotation, etc are ok as is
  303. }
  304. /**
  305. * @brief When returning a key, such as for array.index(), we want to return the original
  306. * LSL_List, not the sanitized one, as the script compiler expects an LSL_List.
  307. * Any other sanitized types can remain as is (int, string, etc).
  308. */
  309. private static object UnfixKey(object key)
  310. {
  311. if(key is XMRArrayListKey)
  312. key = ((XMRArrayListKey)key).GetOriginal();
  313. return key;
  314. }
  315. }
  316. public class XMRArrayKeyComparer: IComparer<object>
  317. {
  318. public static XMRArrayKeyComparer singleton = new XMRArrayKeyComparer();
  319. /**
  320. * @brief Compare two keys
  321. */
  322. public int Compare(object x, object y) // IComparer<object>
  323. {
  324. // Use short type name (eg, String, Int32, XMRArrayListKey) as most significant part of key.
  325. string xtn = x.GetType().Name;
  326. string ytn = y.GetType().Name;
  327. int ctn = String.CompareOrdinal(xtn, ytn);
  328. if(ctn != 0)
  329. return ctn;
  330. ComparerDelegate cd;
  331. if(!comparers.TryGetValue(xtn, out cd))
  332. {
  333. throw new Exception("unsupported key type " + xtn);
  334. }
  335. return cd(x, y);
  336. }
  337. private delegate int ComparerDelegate(object a, object b);
  338. private static Dictionary<string, ComparerDelegate> comparers = BuildComparers();
  339. private static Dictionary<string, ComparerDelegate> BuildComparers()
  340. {
  341. Dictionary<string, ComparerDelegate> cmps = new Dictionary<string, ComparerDelegate>();
  342. cmps.Add(typeof(double).Name, MyFloatComparer);
  343. cmps.Add(typeof(int).Name, MyIntComparer);
  344. cmps.Add(typeof(XMRArrayListKey).Name, MyListKeyComparer);
  345. cmps.Add(typeof(LSL_Rotation).Name, MyRotationComparer);
  346. cmps.Add(typeof(string).Name, MyStringComparer);
  347. cmps.Add(typeof(LSL_Vector).Name, MyVectorComparer);
  348. return cmps;
  349. }
  350. private static int MyFloatComparer(object a, object b)
  351. {
  352. double af = (double)a;
  353. double bf = (double)b;
  354. if(af < bf)
  355. return -1;
  356. if(af > bf)
  357. return 1;
  358. return 0;
  359. }
  360. private static int MyIntComparer(object a, object b)
  361. {
  362. return (int)a - (int)b;
  363. }
  364. private static int MyListKeyComparer(object a, object b)
  365. {
  366. XMRArrayListKey alk = (XMRArrayListKey)a;
  367. XMRArrayListKey blk = (XMRArrayListKey)b;
  368. return XMRArrayListKey.Compare(alk, blk);
  369. }
  370. private static int MyRotationComparer(object a, object b)
  371. {
  372. LSL_Rotation ar = (LSL_Rotation)a;
  373. LSL_Rotation br = (LSL_Rotation)b;
  374. if(ar.x < br.x)
  375. return -1;
  376. if(ar.x > br.x)
  377. return 1;
  378. if(ar.y < br.y)
  379. return -1;
  380. if(ar.y > br.y)
  381. return 1;
  382. if(ar.z < br.z)
  383. return -1;
  384. if(ar.z > br.z)
  385. return 1;
  386. if(ar.s < br.s)
  387. return -1;
  388. if(ar.s > br.s)
  389. return 1;
  390. return 0;
  391. }
  392. private static int MyStringComparer(object a, object b)
  393. {
  394. return String.CompareOrdinal((string)a, (string)b);
  395. }
  396. private static int MyVectorComparer(object a, object b)
  397. {
  398. LSL_Vector av = (LSL_Vector)a;
  399. LSL_Vector bv = (LSL_Vector)b;
  400. if(av.x < bv.x)
  401. return -1;
  402. if(av.x > bv.x)
  403. return 1;
  404. if(av.y < bv.y)
  405. return -1;
  406. if(av.y > bv.y)
  407. return 1;
  408. if(av.z < bv.z)
  409. return -1;
  410. if(av.z > bv.z)
  411. return 1;
  412. return 0;
  413. }
  414. }
  415. /**
  416. * @brief Lists used as keys must be sanitized first.
  417. * List gets converted to an object[] and each element is converted from LSL_ types to system types where possible.
  418. * And we also need an equality operator that compares the values of all elements of the list, not just the lengths.
  419. * Note that just like LSL_Lists, we consider these objects to be immutable, so they can be directly used as keys in
  420. * the dictionary as they don't ever change.
  421. */
  422. public class XMRArrayListKey
  423. {
  424. private LSL_List original;
  425. private object[] cleaned;
  426. private int length;
  427. private int hashCode;
  428. /**
  429. * @brief Construct a sanitized object[] from a list.
  430. * Also save the original list in case we need it later.
  431. */
  432. public XMRArrayListKey(LSL_List key)
  433. {
  434. original = key;
  435. object[] given = key.Data;
  436. int len = given.Length;
  437. length = len;
  438. cleaned = new object[len];
  439. int hc = len;
  440. for(int i = 0; i < len; i++)
  441. {
  442. object v = XMR_Array.FixKey(given[i]);
  443. hc += hc + ((hc < 0) ? 1 : 0);
  444. hc ^= v.GetHashCode();
  445. cleaned[i] = v;
  446. }
  447. hashCode = hc;
  448. }
  449. /**
  450. * @brief Get heap tracking size.
  451. */
  452. public int Size
  453. {
  454. get
  455. {
  456. return original.Size;
  457. }
  458. }
  459. /**
  460. * @brief See if the given object is an XMRArrayListKey and every value is equal to our own.
  461. */
  462. public override bool Equals(object o)
  463. {
  464. if(!(o is XMRArrayListKey))
  465. return false;
  466. XMRArrayListKey a = (XMRArrayListKey)o;
  467. int len = a.length;
  468. if(len != length)
  469. return false;
  470. if(a.hashCode != hashCode)
  471. return false;
  472. for(int i = 0; i < len; i++)
  473. {
  474. if(!cleaned[i].Equals(a.cleaned[i]))
  475. return false;
  476. }
  477. return true;
  478. }
  479. /**
  480. * @brief Get an hash code.
  481. */
  482. public override int GetHashCode()
  483. {
  484. return hashCode;
  485. }
  486. /**
  487. * @brief Compare for key sorting.
  488. */
  489. public static int Compare(XMRArrayListKey x, XMRArrayListKey y)
  490. {
  491. int j = x.length - y.length;
  492. if(j == 0)
  493. {
  494. for(int i = 0; i < x.length; i++)
  495. {
  496. object xo = x.cleaned[i];
  497. object yo = y.cleaned[i];
  498. j = XMRArrayKeyComparer.singleton.Compare(xo, yo);
  499. if(j != 0)
  500. break;
  501. }
  502. }
  503. return j;
  504. }
  505. /**
  506. * @brief Get the original LSL_List we were built from.
  507. */
  508. public LSL_List GetOriginal()
  509. {
  510. return original;
  511. }
  512. /**
  513. * @brief Debugging
  514. */
  515. public override string ToString()
  516. {
  517. StringBuilder sb = new StringBuilder();
  518. for(int i = 0; i < length; i++)
  519. {
  520. if(i > 0)
  521. sb.Append(',');
  522. sb.Append(cleaned[i].ToString());
  523. }
  524. return sb.ToString();
  525. }
  526. }
  527. }