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 observe.src.list_diff;

[Jennifer Messerly, 2013/10/30 23:45:26]

hmmm; git totally failed to recognize the move. I'll comment on unchanged
methods

+
+import 'dart:math' as math;
+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.
+ */
+class ListChangeRecord {

[Jennifer Messerly, 2013/10/30 23:45:26]

some changes here to this class:

* merged ListChangeRecord/ListChangeDelta
* .removed returns unmodifiable list.
* added "object" property

+  /** The list that changed. */
+  final List object;
+
+  /** The index of the change. */
+  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;
+
+  /** The number of items added. */
+  int get addedCount => _addedCount;
+
+  // 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 != removed.length) return true;
+
+    // Otherwise, anything in the update range was changed.
+    return key < index + addedCount;
+  }
+
+  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'
+//
+// With 1-edit updates, the shortest path would be just to update all seven
+// characters. With 2-edit updates, we delete 4, leave 3, and add 4. This
+// leaves the substring '123' intact.
+List<List<int>> _calcEditDistances(List current, int currentStart,

[Jennifer Messerly, 2013/10/30 23:45:26]

unchanged

+    int currentEnd, List old, int oldStart, int oldEnd) {
+  // "Deletion" columns
+  var rowCount = oldEnd - oldStart + 1;
+  var columnCount = currentEnd - currentStart + 1;
+  var distances = new List(rowCount);
+
+  // "Addition" rows. Initialize null column.
+  for (var i = 0; i < rowCount; i++) {
+    distances[i] = new List(columnCount);
+    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 (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;
+}
+
+const _EDIT_LEAVE = 0;
+const _EDIT_UPDATE = 1;
+const _EDIT_ADD = 2;
+const _EDIT_DELETE = 3;
+
+// This starts at the final weight, and walks "backward" by finding
+// the minimum previous weight recursively until the origin of the weight
+// matrix.
+List<int> _spliceOperationsFromEditDistances(List<List<int>> distances) {

[Jennifer Messerly, 2013/10/30 23:45:26]

unchanged

+  var i = distances.length - 1;
+  var j = distances[0].length - 1;
+  var current = distances[i][j];
+  var edits = [];
+  while (i > 0 || j > 0) {
+    if (i == 0) {
+      edits.add(_EDIT_ADD);
+      j--;
+      continue;
+    }
+    if (j == 0) {
+      edits.add(_EDIT_DELETE);
+      i--;
+      continue;
+    }
+    var northWest = distances[i - 1][j - 1];
+    var west = distances[i - 1][j];
+    var north = distances[i][j - 1];
+
+    var min = math.min(math.min(west, north), northWest);
+
+    if (min == northWest) {
+      if (northWest == current) {
+        edits.add(_EDIT_LEAVE);
+      } else {
+        edits.add(_EDIT_UPDATE);
+        current = northWest;
+      }
+      i--;
+      j--;
+    } else if (min == west) {
+      edits.add(_EDIT_DELETE);
+      i--;
+      current = west;
+    } else {
+      edits.add(_EDIT_ADD);
+      j--;
+      current = north;
+    }
+  }
+
+  return edits.reversed.toList();
+}
+
+int _sharedPrefix(List arr1, List arr2, int searchLength) {
+  for (var i = 0; i < searchLength; 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 && 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<ListChangeRecord> calcSplices(List current, int currentStart,

[Jennifer Messerly, 2013/10/30 23:45:26]

unchanged

+    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 ListChangeRecord(current, currentStart);
+    while (oldStart < oldEnd) {
+      splice._removed.add(old[oldStart++]);
+    }
+
+    return [splice ];
+  } else if (oldStart == oldEnd)
+    return [new ListChangeRecord(current, currentStart,
+        addedCount: currentEnd - currentStart)];
+
+  var ops = _spliceOperationsFromEditDistances(
+      _calcEditDistances(current, currentStart, currentEnd, old, oldStart,
+          oldEnd));
+
+  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 ListChangeRecord(current, index);
+
+        splice._addedCount++;
+        index++;
+
+        splice._removed.add(old[oldIndex]);
+        oldIndex++;
+        break;
+      case _EDIT_ADD:
+        if (splice == null) splice = new ListChangeRecord(current, index);
+
+        splice._addedCount++;
+        index++;
+        break;
+      case _EDIT_DELETE:
+        if (splice == null) splice = new ListChangeRecord(current, index);
+
+        splice._removed.add(old[oldIndex]);
+        oldIndex++;
+        break;
+    }
+  }
+
+  if (splice != null) splices.add(splice);
+  return splices;
+}
+
+int _intersect(int start1, int end1, int start2, int end2) {

[Jennifer Messerly, 2013/10/30 23:45:26]

newly ported from observe-js

+  // Disjoint
+  if (end1 < start2 || end2 < start1) return -1;
+
+  // Adjacent
+  if (end1 == start2 || end2 == start1) return 0;
+
+  // Non-zero intersect, span1 first
+  if (start1 < start2) {
+    if (end1 < end2) return end1 - start2; // Overlap
+    return end2 - start2; // Contained
+  } else {
+    // Non-zero intersect, span2 first
+    if (end2 < end1) return end2 - start1; // Overlap
+    return end1 - start1; // Contained
+  }

[Siggi Cherem (dart-lang), 2013/10/31 00:38:45]

maybe not worth it, but this whole function could be written as:

  var overlap = min(end1, end2) - max(start1, start2);
  return overlap < 0 ? -1 : overlap;

actually, it seems you don't care about -1 below, just whether or not it's
negative. so maybe just:

  return min(end1, end2) - max(start1, start2);

[Jennifer Messerly, 2013/10/31 02:19:34]

nice. done. hmm. maybe I should send them a pull request :)

+}
+
+void _mergeSplice(List<ListChangeRecord> splices, ListChangeRecord record) {

[Jennifer Messerly, 2013/10/30 23:45:26]

newly ported from observe-js

+  var splice = new ListChangeRecord(record.object, record.index,
+      removed: record._removed.toList(), addedCount: record.addedCount);
+
+  var inserted = false;
+  var insertionOffset = 0;
+
+  for (var i = 0; i < splices.length; i++) {
+    final current = splices[i];
+    current._index += insertionOffset;
+
+    if (inserted) continue;

[Siggi Cherem (dart-lang), 2013/10/31 00:38:45]

It took me a while to get why this code works. This almost looked like if you
are breaking out of the loop because inserted is never set back to false.
Reading this more closely, 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.

Is that right? Maybe we should add some comments about it?

[Jennifer Messerly, 2013/10/31 02:19:34]

hey, not my code ;-)
uh, sure. :)

+
+    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,

[Jennifer Messerly, 2013/10/30 23:45:26]

newly ported from observe-js

+    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,

[Jennifer Messerly, 2013/10/30 23:45:26]

newly ported from observe-js

+    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;
+}