introduce ObservableList.listChanges to keep list changes separate from property changes

pkg/observe/lib/src/list_diff.dart

 // Copyright (c) 2013, 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.
 
-library template_binding.src.list_diff;
+library observe.src.list_diff;
 
 import 'dart:math' as math;
-import 'package:observe/observe.dart' show ListChangeRecord;
+import 'dart:collection' show UnmodifiableListView;
 
 /**
  * A summary of an individual change to a [List].
  *
  * Each delta represents that at the [index], [removed] sequence of items were
  * removed, and counting forward from [index], [addedCount] items were added.
- *
- * See also: [summarizeListChanges].
  */
-class ListChangeDelta implements ListChangeRecord {
+class ListChangeRecord {
+  /** The list that changed. */
+  final List object;
+
   /** The index of the change. */
-  final int index;
+  int get index => _index;
 
+  /** The items removed, if any. Otherwise this will be an empty list. */
+  List get removed => _unmodifiableRemoved;
+  UnmodifiableListView _unmodifiableRemoved;
+
+  /**
+   * Mutable version of [removed], used during the algorithms as they are
+   * constructing the object.
+   */
   List _removed;
 
-  // Note: conceptually final, but for convenience we increment it as we build
-  // the object. It will be "frozen" by the time it is returned the the user.
-  int _addedCount = 0;
-
-  ListChangeDelta(this.index, {List removed, int addedCount: 0})
-      : _removed = removed != null ? removed : [],
-        _addedCount = addedCount;
-
-  // TODO(jmesserly): freeze remove list before handing it out?
-  /** The items removed, if any. Otherwise this will be an empty list. */
-  List get removed => _removed;
-
   /** The number of items added. */
   int get addedCount => _addedCount;
 
-  int get removedCount => _removed.length;
+  // Note: conceptually these are final, but for convenience we increment it as
+  // we build the object. It will be "frozen" by the time it is returned the the
+  // user.
+  int _index, _addedCount;
+
+  ListChangeRecord._(this.object, this._index, removed, this._addedCount)
+      : _removed = removed,
+        _unmodifiableRemoved = new UnmodifiableListView(removed);
+
+  factory ListChangeRecord(List object, int index,
+      {List removed, int addedCount}) {
+
+    if (removed == null) removed = [];
+    if (addedCount == null) addedCount = 0;
+    return new ListChangeRecord._(object, index, removed, addedCount);
+  }
 
   /** Returns true if the provided index was changed by this operation. */
   bool indexChanged(key) {
     // If key isn't an int, or before the index, then it wasn't changed.
     if (key is! int || key < index) return false;
 
     // If this was a shift operation, anything after index is changed.
-    if (addedCount != removedCount) return true;
+    if (addedCount != removed.length) return true;
 
     // Otherwise, anything in the update range was changed.
     return key < index + addedCount;
   }
 
-  String toString() => '#<$runtimeType index: $index, '
+  String toString() => '#<ListChangeRecord index: $index, '
       'removed: $removed, addedCount: $addedCount>';
 }
 
 // Note: This function is *based* on the computation of the Levenshtein
 // "edit" distance. The one change is that "updates" are treated as two
 // edits - not one. With List splices, an update is really a delete
 // followed by an add. By retaining this, we optimize for "keeping" the
 // maximum array items in the original array. For example:
 //
 //   'xxxx123' -> '123yyyy'
@@ skipping 14 matching lines @@
     distances[i][0] = i;
   }
 
   // Initialize null row
   for (var j = 0; j < columnCount; j++) {
     distances[0][j] = j;
   }
 
   for (var i = 1; i < rowCount; i++) {
     for (var j = 1; j < columnCount; j++) {
-      if (identical(old[oldStart + i - 1], current[currentStart + j - 1])) {
+      if (old[oldStart + i - 1] == current[currentStart + j - 1]) {
         distances[i][j] = distances[i - 1][j - 1];
       } else {
         var north = distances[i - 1][j] + 1;
         var west = distances[i][j - 1] + 1;
         distances[i][j] = math.min(north, west);
       }
     }
   }
 
   return distances;
@@ skipping 47 matching lines @@
       j--;
       current = north;
     }
   }
 
   return edits.reversed.toList();
 }
 
 int _sharedPrefix(List arr1, List arr2, int searchLength) {
   for (var i = 0; i < searchLength; i++) {
-    if (!identical(arr1[i], arr2[i])) {
+    if (arr1[i] != arr2[i]) {
       return i;
     }
   }
   return searchLength;
 }
 
 int _sharedSuffix(List arr1, List arr2, int searchLength) {
   var index1 = arr1.length;
   var index2 = arr2.length;
   var count = 0;
-  while (count < searchLength && identical(arr1[--index1], arr2[--index2])) {
+  while (count < searchLength && arr1[--index1] == arr2[--index2]) {
     count++;
   }
   return count;
 }
 
 /**
  * Lacking individual splice mutation information, the minimal set of
  * splices can be synthesized given the previous state and final state of an
  * array. The basic approach is to calculate the edit distance matrix and
  * choose the shortest path through it.
  *
  * Complexity: O(l * p)
  *   l: The length of the current array
  *   p: The length of the old array
  */
-List<ListChangeDelta> calculateSplices(List current, List previous) =>
-    _calcSplices(current, 0, current.length, previous, 0, previous.length);
-
-List<ListChangeDelta> _calcSplices(List current, int currentStart,
+List<ListChangeRecord> calcSplices(List current, int currentStart,
     int currentEnd, List old, int oldStart, int oldEnd) {
 
   var prefixCount = 0;
   var suffixCount = 0;
 
   var minLength = math.min(currentEnd - currentStart, oldEnd - oldStart);
   if (currentStart == 0 && oldStart == 0) {
     prefixCount = _sharedPrefix(current, old, minLength);
   }
 
   if (currentEnd == current.length && oldEnd == old.length) {
     suffixCount = _sharedSuffix(current, old, minLength - prefixCount);
   }
 
   currentStart += prefixCount;
   oldStart += prefixCount;
   currentEnd -= suffixCount;
   oldEnd -= suffixCount;
 
   if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0) {
     return const [];
   }
 
   if (currentStart == currentEnd) {
-    var splice = new ListChangeDelta(currentStart);
+    var splice = new ListChangeRecord(current, currentStart);
     while (oldStart < oldEnd) {
-      splice.removed.add(old[oldStart++]);
+      splice._removed.add(old[oldStart++]);
     }
 
     return [splice ];
   } else if (oldStart == oldEnd)
-    return [new ListChangeDelta(currentStart,
+    return [new ListChangeRecord(current, currentStart,
         addedCount: currentEnd - currentStart)];
 
   var ops = _spliceOperationsFromEditDistances(
       _calcEditDistances(current, currentStart, currentEnd, old, oldStart,
           oldEnd));
 
-  ListChangeDelta splice = null;
-  var splices = <ListChangeDelta>[];
+  ListChangeRecord splice = null;
+  var splices = <ListChangeRecord>[];
   var index = currentStart;
   var oldIndex = oldStart;
   for (var i = 0; i < ops.length; i++) {
     switch(ops[i]) {
       case _EDIT_LEAVE:
         if (splice != null) {
           splices.add(splice);
           splice = null;
         }
 
         index++;
         oldIndex++;
         break;
       case _EDIT_UPDATE:
-        if (splice == null) splice = new ListChangeDelta(index);
+        if (splice == null) splice = new ListChangeRecord(current, index);
 
         splice._addedCount++;
         index++;
 
-        splice.removed.add(old[oldIndex]);
+        splice._removed.add(old[oldIndex]);
         oldIndex++;
         break;
       case _EDIT_ADD:
-        if (splice == null) splice = new ListChangeDelta(index);
+        if (splice == null) splice = new ListChangeRecord(current, index);
 
         splice._addedCount++;
         index++;
         break;
       case _EDIT_DELETE:
-        if (splice == null) splice = new ListChangeDelta(index);
+        if (splice == null) splice = new ListChangeRecord(current, index);
 
-        splice.removed.add(old[oldIndex]);
+        splice._removed.add(old[oldIndex]);
         oldIndex++;
         break;
     }
   }
 
-  if (splice != null) {
-    splices.add(splice);
+  if (splice != null) splices.add(splice);
+  return splices;
+}
+
+int _intersect(int start1, int end1, int start2, int end2) =>
+    math.min(end1, end2) - math.max(start1, start2);
+
+void _mergeSplice(List<ListChangeRecord> splices, ListChangeRecord record) {
+  var splice = new ListChangeRecord(record.object, record.index,
+      removed: record._removed.toList(), addedCount: record.addedCount);
+
+  var inserted = false;
+  var insertionOffset = 0;
+
+  // I think the way this works is:
+  // - the loop finds where the merge should happen
+  // - it applies the merge in a particular splice
+  // - then continues and updates the subsequent splices with any offset diff.
+  for (var i = 0; i < splices.length; i++) {
+    final current = splices[i];
+    current._index += insertionOffset;
+
+    if (inserted) continue;
+
+    var intersectCount = _intersect(
+        splice.index, splice.index + splice.removed.length,
+        current.index, current.index + current.addedCount);
+
+    if (intersectCount >= 0) {
+      // Merge the two splices
+
+      splices.removeAt(i);
+      i--;
+
+      insertionOffset -= current.addedCount - current.removed.length;
+
+      splice._addedCount += current.addedCount - intersectCount;
+      var deleteCount = splice.removed.length +
+                        current.removed.length - intersectCount;
+
+      if (splice.addedCount == 0 && deleteCount == 0) {
+        // merged splice is a noop. discard.
+        inserted = true;
+      } else {
+        var removed = current._removed;
+
+        if (splice.index < current.index) {
+          // some prefix of splice.removed is prepended to current.removed.
+          removed.insertAll(0,
+              splice.removed.getRange(0, current.index - splice.index));
+        }
+
+        if (splice.index + splice.removed.length >
+            current.index + current.addedCount) {
+          // some suffix of splice.removed is appended to current.removed.
+          removed.addAll(splice.removed.getRange(
+              current.index + current.addedCount - splice.index,
+              splice.removed.length));
+        }
+
+        splice._removed = removed;
+        splice._unmodifiableRemoved = current._unmodifiableRemoved;
+        if (current.index < splice.index) {
+          splice._index = current.index;
+        }
+      }
+    } else if (splice.index < current.index) {
+      // Insert splice here.
+
+      inserted = true;
+
+      splices.insert(i, splice);
+      i++;
+
+      var offset = splice.addedCount - splice.removed.length;
+      current._index += offset;
+      insertionOffset += offset;
+    }
+  }
+
+  if (!inserted) splices.add(splice);
+}
+
+List<ListChangeRecord> _createInitialSplices(List<Object> list,
+    List<ListChangeRecord> records) {
+
+  var splices = <ListChangeRecord>[];
+  for (var record in records) {
+    _mergeSplice(splices, record);
   }
   return splices;
 }
+
+/**
+ * We need to summarize change records. Consumers of these records want to
+ * apply the batch sequentially, and ensure that they can find inserted
+ * items by looking at that position in the list. This property does not
+ * hold in our record-as-you-go records. Consider:
+ *
+ *     var model = toObservable(['a', 'b']);
+ *     model.removeAt(1);
+ *     model.insertAll(0, ['c', 'd', 'e']);
+ *     model.removeRange(1, 3);
+ *     model.insert(1, 'f');
+ *
+ * Here, we inserted some records and then removed some of them.
+ * If someone processed these records naively, they would "play back" the
+ * insert incorrectly, because those items will be shifted.
+ */
+List<ListChangeRecord> projectListSplices(List list,
+    List<ListChangeRecord> records) {
+  if (records.length == 1) return records;
+
+  var splices = [];
+  for (var splice in _createInitialSplices(list, records)) {
+    if (splice.addedCount == 1 && splice.removed.length == 1) {
+      if (splice.removed[0] != list[splice.index]) splices.add(splice);
+      continue;
+    }
+
+    splices.addAll(calcSplices(list, splice.index,
+        splice.index + splice.addedCount, splice._removed, 0,
+        splice.removed.length));
+  }
+
+  return splices;
+}