Revert "remove serialization. it's moved to github"

pkg/serialization/lib/src/format.dart

Index: pkg/serialization/lib/src/format.dart
diff --git a/pkg/serialization/lib/src/format.dart b/pkg/serialization/lib/src/format.dart
new file mode 100644
index 0000000000000000000000000000000000000000..791cc83404d64bb227c4cd3c8e42e226f9330595
--- /dev/null
+++ b/pkg/serialization/lib/src/format.dart
@@ -0,0 +1,561 @@
+part of serialization;
+
+/**
+ * An abstract class for serialization formats. Subclasses define how data
+ * is read or written to a particular output mechanism.
+ */
+abstract class Format {
+
+  const Format();
+
+  /**
+   * Return true if this format stores primitives in their own area and uses
+   * references to them (e.g. [SimpleFlatFormat]) and false if primitives
+   * are stored directly (e.g. [SimpleJsonFormat], [SimpleMapFormat]).
+   */
+  bool get shouldUseReferencesForPrimitives => false;
+
+  /**
+   * Generate output for [w] and return it. The particular form of the output
+   * will depend on the format. The format can assume that [w] has data
+   * generated by rules in a series of lists, and that each list will contain
+   * either primitives (null, bool, num, String), Lists or Maps. The Lists or
+   * Maps may contain any of the same things recursively, or may contain
+   * Reference objects. For lists and maps the rule will tell us if they can
+   * be of variable length or not. The format is allowed to operate
+   * destructively on the rule data.
+   */
+  generateOutput(Writer w);
+
+  /**
+   * Read the data from [input] in the context of [reader] and return it as a
+   * Map with entries for "roots", "data" and "rules", which the reader knows
+   * how to interpret. The type of [input] will depend on the particular format.
+   */
+  Map<String, dynamic> read(input, Reader reader);
+}
+
+/**
+ * This is the most basic format, which provides the internal representation
+ * of the serialization, exposing the Reference objects.
+ */
+class InternalMapFormat extends Format {
+  const InternalMapFormat();
+
+  /**
+   * Generate output for this format from [w] and return it as a nested Map
+   * structure. The top level has
+   * 3 fields, "rules" which may hold a definition of the rules used,
+   * "data" which holds the serialized data, and "roots", which holds
+   * [Reference] objects indicating the root objects. Note that roots are
+   * necessary because the data is not organized in the same way as the object
+   * structure, it's a list of lists holding self-contained maps which only
+   * refer to other parts via [Reference] objects.
+   */
+  Map<String, dynamic> generateOutput(Writer w) {
+    var result = {
+      "rules" : w.serializedRules(),
+      "data" : w.states,
+      "roots" : w._rootReferences()
+    };
+    return result;
+  }
+
+  /**
+   * Read serialized data written from this format
+   * and return the nested Map representation described in [generateOutput]. If
+   * the data also includes rule definitions, then these will replace the rules
+   * in the [Serialization] for [reader].
+   */
+  Map<String, dynamic> read(Map<String, dynamic> topLevel, Reader reader) {
+    var ruleString = topLevel["rules"];
+    reader.readRules(ruleString);
+    reader._data = topLevel["data"];
+    topLevel["roots"] = topLevel["roots"];
+    return topLevel;
+  }
+}
+
+/**
+ * A format that stores the data in maps which can be converted into a JSON
+ * string or passed through an isolate. Note that this consists of maps, but
+ * that they don't follow the original object structure or look like the nested
+ * maps of a [json] representation. They are flat, and [Reference] objects
+ * are converted into a map form that will not make sense to
+ * anything but this format. For simple acyclic JSON that other programs
+ * can read, use [SimpleJsonFormat]. This is the default format, and is
+ * easier to read than the more efficient [SimpleFlatFormat].
+ */
+class SimpleMapFormat extends InternalMapFormat {
+
+  const SimpleMapFormat();
+
+  /**
+   * Generate output for this format from [w] and return it as a String which
+   * is the [json] representation of a nested Map structure. The top level has
+   * 3 fields, "rules" which may hold a definition of the rules used,
+   * "data" which holds the serialized data, and "roots", which holds
+   * [Reference] objects indicating the root objects. Note that roots are
+   * necessary because the data is not organized in the same way as the object
+   * structure, it's a list of lists holding self-contained maps which only
+   * refer to other parts via [Reference] objects.
+   * This effectively defines a custom JSON serialization format, although
+   * the details of the format vary depending which rules were used.
+   */
+  Map<String, dynamic> generateOutput(Writer w) {
+    forAllStates(w, (x) => x is Reference, referenceToMap);
+    var result = super.generateOutput(w);
+    result["roots"] = result["roots"].map(
+        (x) => x is Reference ? referenceToMap(x) : x).toList();
+    return result;
+  }
+
+  /**
+   * Convert the data generated by the rules to have maps with the fields
+   * of [Reference] objects instead of the [Reference] so that the structure
+   * can be serialized between isolates and json easily.
+   */
+  void forAllStates(ReaderOrWriter w, bool predicate(value),
+               void transform(value)) {
+    for (var eachRule in w.rules) {
+      var ruleData = w.states[eachRule.number];
+      for (var data in ruleData) {
+        keysAndValues(data).forEach((key, value) {
+          if (predicate(value)) {
+            data[key] = transform(value);
+          }
+        });
+      }
+    }
+  }
+
+  /** Convert the reference to a [json] serializable form. */
+  Map<String, int> referenceToMap(Reference ref) => ref == null ? null :
+    {
+      "__Ref" : 0,
+      "rule" : ref.ruleNumber,
+      "object" : ref.objectNumber
+    };
+
+  /**
+   * Convert the [referenceToMap] form for a reference back to a [Reference]
+   * object.
+   */
+  Reference mapToReference(ReaderOrWriter parent, Map<String, int> ref) =>
+      ref == null ? null : new Reference(parent, ref["rule"], ref["object"]);
+
+  /**
+   * Read serialized data written in this format
+   * and return the nested Map representation described in [generateOutput]. If
+   * the data also includes rule definitions, then these will replace the rules
+   * in the [Serialization] for [reader].
+   */
+  Map<String, dynamic> read(Map<String, dynamic> topLevel, Reader reader) {
+    super.read(topLevel, reader);
+    forAllStates(reader,
+        (ref) => ref is Map && ref["__Ref"] != null,
+        (ref) => mapToReference(reader, ref));
+    topLevel["roots"] = topLevel["roots"]
+        .map((x) => x is Map<String, int> ? mapToReference(reader, x) : x)
+        .toList();
+    return topLevel;
+  }
+}
+
+/**
+ * A format for "normal" [json] representation of objects. It stores
+ * the fields of the objects as nested maps, and doesn't allow cycles. This can
+ * be useful in talking to existing APIs that expect [json] format data. The
+ * output will be either a simple object (string, num, bool), a List, or a Map,
+ * with nesting of those.
+ * Note that since the classes of objects aren't normally stored, this isn't
+ * enough information to read back the objects. However, if the
+ * If the [storeRoundTripInfo] field of the format is set to true, then this
+ * will store the rule number along with the data, allowing reconstruction.
+ */
+class SimpleJsonFormat extends SimpleMapFormat {
+
+  /**
+   * Indicate if we should store rule numbers with map/list data so that we
+   * will know how to reconstruct it with a read operation. If we don't, this
+   * will be more compliant with things that expect known format JSON as input,
+   * but we won't be able to read back the objects.
+   */
+  final bool storeRoundTripInfo;
+
+  /**
+   * If we store the rule numbers, what key should we use to store them.
+   */
+  static const String RULE = "_rule";
+  static const String RULES = "_rules";
+  static const String DATA = "_data";
+  static const String ROOTS = "_root";
+
+  const SimpleJsonFormat({this.storeRoundTripInfo : false});
+
+  /**
+   * Generate output for this format from [w] and return it as
+   * the [json] representation of a nested Map structure.
+   */
+  generateOutput(Writer w) {
+    jsonify(w);
+    var root = w._rootReferences().first;
+    if (root is Reference) root = w.stateForReference(root);
+    if (w.selfDescribing && storeRoundTripInfo) {
+      root = new Map()
+          ..[RULES] = w.serializedRules()
+          ..[DATA] = root;
+    }
+    return root;
+  }
+
+  /**
+   * Convert the data generated by the rules to have nested maps instead
+   * of Reference objects and to add rule numbers if [storeRoundTripInfo]
+   * is true.
+   */
+  void jsonify(Writer w) {
+    for (var eachRule in w.rules) {
+      var ruleData = w.states[eachRule.number];
+      jsonifyForRule(ruleData, w, eachRule);
+    }
+  }
+
+  /**
+   * For a particular [rule] modify the [ruleData] to conform to this format.
+   */
+  void jsonifyForRule(List ruleData, Writer w, SerializationRule rule) {
+    for (var i = 0; i < ruleData.length; i++) {
+      var each = ruleData[i];
+      if (each is List) {
+        jsonifyEntry(each, w);
+        if (storeRoundTripInfo) ruleData[i].add(rule.number);
+      } else if (each is Map) {
+        jsonifyEntry(each, w);
+        if (storeRoundTripInfo) each[RULE] = rule.number;
+      }
+    }
+  }
+
+  /**
+   * For one particular entry, which is either a Map or a List, update it
+   * to turn References into a nested List/Map.
+   */
+  void jsonifyEntry(map, Writer w) {
+    // Note, if this is a Map, and the key might be a reference, we need to
+    // bend over backwards to avoid concurrent modifications. Non-string keys
+    // won't actually work if we try to write this to json, but might happen
+    // if e.g. sending between isolates.
+    var updates = new Map();
+    keysAndValues(map).forEach((key, value) {
+      if (value is Reference) updates[key] = w.stateForReference(value);
+    });
+    updates.forEach((k, v) => map[k] = v);
+  }
+
+  /**
+   * Read serialized data saved in this format, which should look like
+   * either a simple type, a List or a Map and return the Map
+   * representation that the reader expects, with top-level
+   * entries for "rules", "data", and "roots". Nested lists/maps will be
+   * converted into Reference objects. Note that if the data was not written
+   * with [storeRoundTripInfo] true this will fail.
+   */
+  Map<String, dynamic> read(data, Reader reader) {
+    var result = new Map();
+    // Check the case of having been written without additional data and
+    // read as if it had been written with storeRoundTripData set.
+    if (reader.selfDescribing && !(data.containsKey(DATA))) {
+      throw new SerializationException("Missing $DATA entry, "
+          "may mean this was written and read with different values "
+          "of selfDescribing.");
+    }
+    // If we are self-describing, we should have separate rule and data
+    // sections. If not, we assume that we have just the data at the top level.
+    var rules = reader.selfDescribing ? data[RULES] : null;
+    var actualData = reader.selfDescribing ? data[DATA] : data;
+    reader.readRules(rules);
+    var ruleData = new List.generate(reader.rules.length, (_) => []);
+    var top = recursivelyFixUp(actualData, reader, ruleData);
+    result["data"] = ruleData;
+    result["roots"] = [top];
+    return result;
+  }
+
+  /**
+   * Convert nested references in [input] into [Reference] objects.
+   */
+  recursivelyFixUp(input, Reader r, List result) {
+    var data = input;
+    if (isPrimitive(data)) {
+      result[r._primitiveRule().number].add(data);
+      return data;
+    }
+    var ruleNumber;
+    // If we've added the rule number on as the last item in a list we have
+    // to get rid of it or it will be interpreted as extra data. For a map
+    // the library will be ok, but we need to get rid of the extra key before
+    // the data is shown to the user, so we destructively modify.
+    if (data is List) {
+      ruleNumber = data.last;
+      data = data.take(data.length - 1).toList();
+    } else if (data is Map) {
+      ruleNumber = data.remove(RULE);
+    } else {
+      throw new SerializationException("Invalid data format");
+    }
+    // Do not use map or other lazy operations for this. They do not play
+    // well with a function that destructively modifies its arguments.
+    var newData = mapValues(data, (each) => recursivelyFixUp(each, r, result));
+    result[ruleNumber].add(newData);
+    return new Reference(r, ruleNumber, result[ruleNumber].length - 1);
+  }
+}
+
+/**
+ * Writes to a simple mostly-flat format. Details are subject to change.
+ * Right now this produces a List containing null, num, and String. This is
+ * more space-efficient than the map formats, but much less human-readable.
+ * Simple usage is to turn this into JSON for transmission.
+ */
+class SimpleFlatFormat extends Format {
+  bool get shouldUseReferencesForPrimitives => true;
+
+  /**
+   * For each rule we store data to indicate whether it will be reconstructed
+   * as a primitive, a list or a map.
+   */
+  static const int STORED_AS_LIST = 1;
+  static const int STORED_AS_MAP = 2;
+  static const int STORED_AS_PRIMITIVE = 3;
+
+  const SimpleFlatFormat();
+
+  /**
+   * Generate output for this format from [w]. This will return a List with
+   * three entries, corresponding to the "rules", "data", and "roots" from
+   * [SimpleMapFormat]. The data is stored as a single List containing
+   * primitives.
+   */
+  List generateOutput(Writer w) {
+    var result = new List(3);
+    var flatData = [];
+    for (var eachRule in w.rules) {
+      var ruleData = w.states[eachRule.number];
+      flatData.add(ruleData.length);
+      writeStateInto(eachRule, ruleData, flatData);
+    }
+    result[0] = w.serializedRules();
+    result[1] = flatData;
+    result[2] = [];
+    w._rootReferences().forEach((x) => x.writeToList(result[2]));
+    return result;
+  }
+
+  /**
+   * Writes the data from [rule] into the [target] list.
+   */
+  void writeStateInto(SerializationRule rule, List ruleData, List target) {
+    if (!ruleData.isEmpty) {
+      var sample = ruleData.first;
+      if (rule.storesStateAsLists || sample is List) {
+        writeLists(rule, ruleData, target);
+      } else if (rule.storesStateAsMaps || sample is Map) {
+        writeMaps(rule, ruleData, target);
+      } else if (rule.storesStateAsPrimitives || isPrimitive(sample)) {
+        writeObjects(ruleData, target);
+      } else {
+        throw new SerializationException("Invalid data format");
+      }
+    } else {
+      // If there is no data, write a zero for the length.
+      target.add(0);
+    }
+  }
+
+  /**
+   * Write [entries], which contains Lists. Either the lists are variable
+   * length, in which case we add a length field, or they are fixed length, in
+   * which case we don't, and assume the [rule] will know how to read the
+   * right length when we read it back. We expect everything in the list to be
+   * a reference, which is stored as two numbers.
+   */
+  void writeLists(SerializationRule rule, List<List> entries, List target) {
+    target.add(STORED_AS_LIST);
+    for (var eachEntry in entries) {
+      if (rule.hasVariableLengthEntries) {
+        target.add(eachEntry.length);
+      }
+      for (var eachReference in eachEntry) {
+        writeReference(eachReference, target);
+      }
+    }
+  }
+
+  /**
+   * Write [entries], which contains Maps. Either the Maps are variable
+   * length, in which case we add a length field, or they are fixed length, in
+   * which case we don't, and assume the [rule] will know how to read the
+   * right length when we read it back. Then we write alternating keys and
+   * values. We expect the values to be references, which we store as
+   * two numbers.
+   */
+  void writeMaps(SerializationRule rule, List<Map> entries, List target) {
+    target.add(STORED_AS_MAP);
+    for (var eachEntry in entries) {
+      if (rule.hasVariableLengthEntries) {
+        target.add(eachEntry.length);
+      }
+      eachEntry.forEach((key, value) {
+        writeReference(key, target);
+        writeReference(value, target);
+      });
+    }
+  }
+
+  /**
+   * Write [entries], which contains simple objects which we can put directly
+   * into [target].
+   */
+  void writeObjects(List entries, List target) {
+    target.add(STORED_AS_PRIMITIVE);
+    for (var each in entries) {
+      if (!isPrimitive(each)) throw new SerializationException("Invalid data");
+    }
+    target.addAll(entries);
+  }
+
+  /**
+   * Write [eachRef] to [target]. It will be written as two ints. If [eachRef]
+   * is null it will be written as two nulls.
+   */
+  void writeReference(Reference eachRef, List target) {
+    // TODO(alanknight): Writing nulls is problematic in a real flat format.
+    if (eachRef == null) {
+      target..add(null)..add(null);
+    } else {
+      eachRef.writeToList(target);
+    }
+  }
+
+  /**
+   * Read the data from [rawInput] in the context of [r] and return it as a
+   * Map with entries for "roots", "data" and "rules", which the reader knows
+   * how to interpret. We expect [rawInput] to have been generated from this
+   * format.
+   */
+  Map<String, dynamic> read(List rawInput, Reader r) {
+    // TODO(alanknight): It's annoying to have to pass the reader around so
+    // much, consider having the format be specific to a particular
+    // serialization operation along with the reader and having it as a field.
+    var input = {};
+    input["rules"] = rawInput[0];
+    r.readRules(input["rules"]);
+
+    var flatData = rawInput[1];
+    var stream = flatData.iterator;
+    var tempData = new List(r.rules.length);
+    for (var eachRule in r.rules) {
+       tempData[eachRule.number] = readRuleDataFrom(stream, eachRule, r);
+    }
+    input["data"] = tempData;
+
+    var roots = [];
+    var rootsAsInts = rawInput[2].iterator;
+    do {
+      roots.add(nextReferenceFrom(rootsAsInts, r));
+    } while (rootsAsInts.current != null);
+
+    input["roots"] = roots;
+    return input;
+  }
+
+  /**
+   * Read the data for [rule] from [input] and return it.
+   */
+  readRuleDataFrom(Iterator input, SerializationRule rule, Reader r) {
+    var numberOfEntries = _next(input);
+    var entryType = _next(input);
+    if (entryType == STORED_AS_LIST) {
+      return readLists(input, rule, numberOfEntries, r);
+    }
+    if (entryType == STORED_AS_MAP) {
+      return readMaps(input, rule, numberOfEntries, r);
+    }
+    if (entryType == STORED_AS_PRIMITIVE) {
+      return readPrimitives(input, rule, numberOfEntries);
+    }
+    if (numberOfEntries == 0) {
+      return [];
+    } else {
+      throw new SerializationException("Invalid data in serialization");
+    }
+  }
+
+  /**
+   * Read data for [rule] from [input] with [length] number of entries,
+   * creating lists from the results.
+   */
+  List readLists(Iterator input, SerializationRule rule, int length, Reader r) {
+    var ruleData = [];
+    for (var i = 0; i < length; i++) {
+      var subLength =
+          rule.hasVariableLengthEntries ? _next(input) : rule.dataLength;
+      var subList = [];
+      ruleData.add(subList);
+      for (var j = 0; j < subLength; j++) {
+        subList.add(nextReferenceFrom(input, r));
+      }
+    }
+    return ruleData;
+  }
+
+  /**
+   * Read data for [rule] from [input] with [length] number of entries,
+   * creating maps from the results.
+   */
+  List readMaps(Iterator input, SerializationRule rule, int length, Reader r) {
+    var ruleData = [];
+    for (var i = 0; i < length; i++) {
+      var subLength =
+          rule.hasVariableLengthEntries ? _next(input) : rule.dataLength;
+      var map = new Map();
+      ruleData.add(map);
+      for (var j = 0; j < subLength; j++) {
+        var key = nextReferenceFrom(input, r);
+        var value = nextReferenceFrom(input, r);
+        map[key] = value;
+      }
+    }
+    return ruleData;
+  }
+
+  /**
+   * Read data for [rule] from [input] with [length] number of entries,
+   * treating the data as primitives that can be returned directly.
+   */
+  List readPrimitives(Iterator input, SerializationRule rule, int length) {
+    var ruleData = [];
+    for (var i = 0; i < length; i++) {
+      ruleData.add(_next(input));
+    }
+    return ruleData;
+  }
+
+  /** Read the next Reference from the input. */
+  Reference nextReferenceFrom(Iterator input, Reader r) {
+    var a = _next(input);
+    var b = _next(input);
+    if (a == null) {
+      return null;
+    } else {
+      return new Reference(r, a, b);
+    }
+  }
+
+  /** Return the next element from the input. */
+  _next(Iterator input) {
+    input.moveNext();
+    return input.current;
+  }
+}