Wrote functions to convert collections and maps to strings and invoked

tests/corelib/src/CollectionToStringTest.dart

Index: tests/corelib/src/CollectionToStringTest.dart
===================================================================
--- tests/corelib/src/CollectionToStringTest.dart	(revision 0)
+++ tests/corelib/src/CollectionToStringTest.dart	(revision 0)
@@ -0,0 +1,254 @@
+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
+// for details. All rights reserved. Use of this source code is governed by a
+// BSD-style license that can be found in the LICENSE file.
+
+/**
+ * Tests for the toString methods on collections (including maps).
+ */
+
+// todo(jjb): seed random number generator when API allows it

[Ivan Posva, 2012/02/15 09:54:10]

Allcaps TODO. Here and maybe other places.

+
+final int NUM_TESTS = 3000;
+final int MAX_COLLECTION_SIZE = 6;
+
+main() {
+  exactTest();

[sra1, 2012/02/15 03:11:10]

The tests are large and require careful reading.
It would be nice to see a few simpler tests that give confidence that the
algorithmic tests are testing what we expect, e.g

Expect.equals('[]', [].toString);

Expect.equals('[1,two]', [1, 'two'].toString());
Expect.equals('[1,two]', <String>['1', 'two'].toString());

[Ivan Posva, 2012/02/15 09:54:10]

Adding a couple of these before starting the more involved tests would really
help with smoke testing this. It has the additional benefit of checking the
literals, so you should also include a couple of "const [1, 2]" style literals.

+  inexactTest();
+}
+
+/**
+ * Generate a bunch of random collections (including Maps), and test that
+ * there string form is as expected. The collections include collections
+ * as elements, keys, and values, and include recursive references.
+ *
+ * This test restricts itself to collections with well-defined iteration
+ * orders (i.e., no HashSet, HashMap).
+ */
+void exactTest() {
+  for (int i = 0; i < NUM_TESTS; i++) {
+    // Choose a size from 0 to MAX_COLLECTION_SIZE, favoring larger sizes
+    float sqrtSize = Math.sqrt(Math.random() * (MAX_COLLECTION_SIZE + 1));
+    int size = (sqrtSize * sqrtSize).toInt();
+  
+    StringBuffer stringRep = new StringBuffer();
+    Object o = randomCollection(size, stringRep, exact:true);
+    Expect.equals(o.toString(), stringRep.toString());
+  }
+}
+
+/**
+ * Generate a bunch of random collections (including Maps), and test that
+ * there string form is as expected. The collections include collections
+ * as elements, keys, and values, and include recursive references.
+ *
+ * This test includes collections with ill-defined iteration orders (i.e.,
+ * HashSet, HashMap). As a consequence, it can't use equality tests on the
+ * string form. Instead, it performs equality tests on their "alphagrams."
+ * This might allow false positives, but it does give a fair amount of
+ * confidence.
+ */
+void inexactTest() {
+  for (int i = 0; i < NUM_TESTS; i++) {
+    // Choose a size from 0 to MAX_COLLECTION_SIZE, favoring larger sizes
+    float sqrtSize = Math.sqrt(Math.random() * (MAX_COLLECTION_SIZE + 1));
+    int size = (sqrtSize * sqrtSize).toInt();
+  
+    StringBuffer stringRep = new StringBuffer();
+    Object o = randomCollection(size, stringRep, exact:false);
+    Expect.equals(alphagram(o.toString()), alphagram(stringRep.toString()));
+  }
+}
+
+/**
+ * Return a random collection (or Map) of the specified size, placing its
+ * string representation into the given string buffer.
+ *
+ * If exact is true, the returned collections will not be, and will not contain
+ * a collection with ill-defined iteration order (i.e., a HashSet or HashMap).
+ */
+Object randomCollection(int size, StringBuffer stringRep, [bool exact]) {
+  return randomCollectionHelper(size, exact, stringRep, []);
+}
+
+/**
+ * Return a random collection (or map) of the specified size, placing its
+ * string representation into the given string buffer. The beingMade
+ * parameter is a list of collections currently under construction, i.e., 
+ * candidates for recursive references.
+ *
+ * If exact is true, the returned collections will not be, and will not contain
+ * a collection with ill-defined iteration order (i.e., a HashSet or HashMap).
+ */
+Object randomCollectionHelper(int size, bool exact, StringBuffer stringRep,
+    List beingMade) {
+  double interfaceFrac = Math.random();
+
+  if (exact) {
+    if (interfaceFrac < 1/3) {
+      return randomList(size, exact, stringRep, beingMade);
+    } else if (interfaceFrac < 2/3) {
+      return randomQueue(size, exact, stringRep, beingMade);
+    } else {
+      return randomMap(size, exact, stringRep, beingMade);
+    }
+  } else {
+    if (interfaceFrac < 1/4) {
+      return randomList(size, exact, stringRep, beingMade);
+    } else if (interfaceFrac < 2/4) {
+      return randomQueue(size, exact, stringRep, beingMade);
+    } else if (interfaceFrac < 3/4) {
+      return randomSet(size, exact, stringRep, beingMade);
+    } else {
+      return randomMap(size, exact, stringRep, beingMade);
+    }
+  }
+}
+
+/**
+ * Return a random List of the specified size, placing its string
+ * representation into the given string buffer. The beingMade
+ * parameter is a list of collections currently under construction, i.e., 
+ * candidates for recursive references.
+ *
+ * If exact is true, the returned collections will not be, and will not contain
+ * a collection with ill-defined iteration order (i.e., a HashSet or HashMap).
+ */
+List randomList(int size, bool exact, StringBuffer stringRep, List beingMade) {
+  return populateRandomCollection(size, exact, stringRep, beingMade, []);
+}
+
+/**
+ * Like randomList, but returns a queue.
+ */
+Queue randomQueue(int size, bool exact, StringBuffer stringRep, List beingMade){
+  return populateRandomCollection(size, exact, stringRep, beingMade, new Queue());
+}
+
+/**
+ * Like randomList, but returns a Set.
+ */
+Set randomSet(int size, bool exact, StringBuffer stringRep, List beingMade) {
+  // Until we have LinkedHashSet, method will only be called with exact==true
+  return populateRandomSet(size, exact, stringRep, beingMade, new Set());
+}
+
+/**
+ * Like randomList, but returns a map.
+ */
+Map randomMap(int size, bool exact, StringBuffer stringRep, List beingMade) {
+  if (exact) {
+    return populateRandomMap(size, exact, stringRep, beingMade,
+        new LinkedHashMap());
+  } else {
+    return populateRandomMap(size, exact, stringRep, beingMade,
+        randomBool() ? new Map() : new LinkedHashMap());
+  }
+}
+
+/**
+ * Populates the given empty collection with elements, emitting the string
+ * representation of the collection to stringRep.  The beingMade parameter is
+ * a list of collections currently under construction, i.e., candidates for
+ * recursive references.
+ *
+ * If exact is true, the elements of the returned collections will not be,
+ * and will not contain a collection with ill-defined iteration order
+ * (i.e., a HashSet or HashMap).
+ */
+Collection populateRandomCollection(int size, bool exact,
+    StringBuffer stringRep, List beingMade, Collection coll) {
+  beingMade.add(coll);
+  stringRep.add(coll is List ? '[' : '{');
+
+  for (int i = 0; i < size; i++) {
+    if (i != 0) stringRep.add(', ');
+    coll.add(randomElement(random(size), exact, stringRep, beingMade));
+  }
+
+  stringRep.add(coll is List ? ']' : '}');
+  beingMade.removeLast();
+  return coll;
+}
+
+/** Like populateRandomCollection, but for sets (elements must be hashable) */
+Set populateRandomSet(int size, bool exact, StringBuffer stringRep,
+    List beingMade, Set set) {
+  stringRep.add('{');
+
+  for (int i = 0; i < size; i++) {
+    if (i != 0) stringRep.add(', ');
+    set.add(i);
+    stringRep.add(i);
+  }
+
+  stringRep.add('}');
+  return set;
+}
+
+
+/** Like populateRandomCollection, but for maps. */
+Map populateRandomMap(int size, bool exact, StringBuffer stringRep,
+    List beingMade, Map map) {
+  beingMade.add(map);
+  stringRep.add('{');
+
+  for (int i = 0; i < size; i++) {
+    if (i != 0) stringRep.add(', ');
+
+    int key = i; // Ensures no duplicates
+    stringRep.add(key);
+    stringRep.add(': ');
+    Object val = randomElement(random(size), exact, stringRep, beingMade);
+    map[key] = val;
+  }
+
+  stringRep.add('}');
+  beingMade.removeLast();
+  return map;
+}
+
+/**
+ * Generates a random element which can be an int, a collection, or a map,
+ * and emits it to StringRep. The beingMade parameter is a list of collections
+ * currently under construction, i.e., candidates for recursive references.
+ *
+ * If exact is true, the returned element will not be, and will not contain
+ * a collection with ill-defined iteration order (i.e., a HashSet or HashMap).
+ */
+void randomElement(int size, bool exact, StringBuffer stringRep,
+    List beingMade) {
+  Object result;
+  double elementTypeFrac = Math.random();
+  if (elementTypeFrac < 1/3) {
+    result = random(1000);
+    stringRep.add(result);
+  } else if (elementTypeFrac < 2/3) {
+    // Element Is a random (new) collection
+    result = randomCollectionHelper(size, exact, stringRep, beingMade);
+  } else {
+    // Element Is a random recursive ref
+    result = beingMade[random(beingMade.length)];
+    if (result is List)
+      stringRep.add('[...]');
+    else
+      stringRep.add('{...}');
+  }
+  return result;
+}
+
+/** Returns a random int on [0, max) */
+int random(int max) {
+  return (Math.random() * max).toInt();
+}
+
+/** Returns a random boolean value. */
+bool randomBool() {
+  return Math.random() < .5;
+}
+
+/** Returns the alphabetized characters in a string. */
+String alphagram(String s) {
+  List<int> chars = s.charCodes();
+  chars.sort((int a, int b) => a - b);
+  return new String.fromCharCodes(chars);
+}