[mdv] Avoid observing placeholder arrays in TemplateIterator

pkg/mdv/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 mdv.src.list_diff;
+
+import 'dart:math' as math;
+import 'package:observe/observe.dart' show ListChangeRecord;
+
+/**
+ * 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 {
+  /** The index of the change. */
+  final int index;
+
+  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;
+
+  String toString() => '#<$runtimeType 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,
+    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 (identical(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) {
+  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 (!identical(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])) {
+    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,
+    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);
+    while (oldStart < oldEnd) {
+      splice.removed.add(old[oldStart++]);
+    }
+
+    return [splice ];
+  } else if (oldStart == oldEnd)
+    return [new ListChangeDelta(currentStart,
+        addedCount: currentEnd - currentStart)];
+
+  var ops = _spliceOperationsFromEditDistances(
+      _calcEditDistances(current, currentStart, currentEnd, old, oldStart,
+          oldEnd));
+
+  ListChangeDelta splice = null;
+  var splices = <ListChangeDelta>[];
+  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);
+
+        splice._addedCount++;
+        index++;
+
+        splice.removed.add(old[oldIndex]);
+        oldIndex++;
+        break;
+      case _EDIT_ADD:
+        if (splice == null) splice = new ListChangeDelta(index);
+
+        splice._addedCount++;
+        index++;
+        break;
+      case _EDIT_DELETE:
+        if (splice == null) splice = new ListChangeDelta(index);
+
+        splice.removed.add(old[oldIndex]);
+        oldIndex++;
+        break;
+    }
+  }
+
+  if (splice != null) {
+    splices.add(splice);
+  }
+  return splices;
+}