Refactor List diffing/change records, add diffing interface (#5)
* Refactor our a differ/list differ.
* Fix bugs in mergeSplice
* More fixes to the list differ.
* Some debugging.
* More fixes.
* Fix remaining edge case missed.
* Slight cleanups before PR
* Update README
* Add license headers.
diff --git a/.analysis_options b/.analysis_options
index dbb6342..6f04432 100644
--- a/.analysis_options
+++ b/.analysis_options
@@ -2,48 +2,27 @@
strong-mode: true
linter:
rules:
- #- always_declare_return_types
- #- always_specify_types
- #- annotate_overrides
- #- avoid_as
+ # Errors
- avoid_empty_else
+ - control_flow_in_finally
+ - empty_statements
+ - test_types_in_equals
+ - throw_in_finally
+ - valid_regexps
+
+ # Style
+ - annotate_overrides
- avoid_init_to_null
- avoid_return_types_on_setters
- await_only_futures
- camel_case_types
- - cancel_subscriptions
- #- close_sinks
- #- comment_references
- - constant_identifier_names
- - control_flow_in_finally
+ - comment_references
- empty_catches
- empty_constructor_bodies
- - empty_statements
- hash_and_equals
- - implementation_imports
- - iterable_contains_unrelated_type
- - library_names
- library_prefixes
- - list_remove_unrelated_type
- non_constant_identifier_names
- - one_member_abstracts
- - only_throw_errors
- - overridden_fields
- - package_api_docs
- - package_names
- - package_prefixed_library_names
- prefer_is_not_empty
- #- public_member_api_docs
- #- slash_for_doc_comments
- #- sort_constructors_first
- #- sort_unnamed_constructors_first
- - super_goes_last
- - test_types_in_equals
- - throw_in_finally
- #- type_annotate_public_apis
+ - slash_for_doc_comments
- type_init_formals
- #- unawaited_futures
- - unnecessary_brace_in_string_interp
- - unnecessary_getters_setters
- unrelated_type_equality_checks
- - valid_regexps
diff --git a/CHANGELOG.md b/CHANGELOG.md
index aca61a5..bfcf1b6 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -1,3 +1,15 @@
+## 0.15.0
+
+* Added the `Differ` interface, as well as `EqualityDiffer`
+* Refactored list diffing into a `ListDiffer`
+* Added concept of `ChangeRecord.ANY` and `ChangeRecord.NONE`
+ * Low-GC ways to expression "something/nothing" changed
+* Refactored `ListChangeRecord`
+ * Added named constructors for common use cases
+ * Added equality and hashCode checks
+ * Added `ListChangeRecord.apply` to apply a change record
+* Added missing `@override` annotations to satisfy `annotate_overrides`
+
## 0.14.0+1
* Add a missing dependency on `pkg/meta`.
diff --git a/README.md b/README.md
index 3965a6f..c688514 100644
--- a/README.md
+++ b/README.md
@@ -1,5 +1,6 @@
-Support for marking objects as observable, and getting notifications when those
-objects are mutated.
+Support for detecting and being notified when an object is mutated.
-This library is used to observe changes to observable types. It also
-has helpers to make implementing and using observable objects easy.
+There are two general ways to detect changes:
+
+* Listen to `Observable.changes` and be notified when an object changes
+* Use `Differ.diff` to determine changes between two objects
diff --git a/lib/observable.dart b/lib/observable.dart
index ce82061..179a938 100644
--- a/lib/observable.dart
+++ b/lib/observable.dart
@@ -4,8 +4,8 @@
library observable;
-export 'src/change_record.dart';
-export 'src/list_diff.dart' show ListChangeRecord;
+export 'src/differs.dart' show Differ, EqualityDiffer, ListDiffer;
+export 'src/records.dart' show ChangeRecord, ListChangeRecord;
export 'src/observable.dart';
export 'src/observable_list.dart';
export 'src/observable_map.dart';
diff --git a/lib/src/change_record.dart b/lib/src/change_record.dart
deleted file mode 100644
index b4c4f24..0000000
--- a/lib/src/change_record.dart
+++ /dev/null
@@ -1,9 +0,0 @@
-// Copyright (c) 2016, 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 observable.src.change_record;
-
-/// Records a change to an [Observable].
-// TODO(jmesserly): remove this type
-abstract class ChangeRecord {}
diff --git a/lib/src/differs.dart b/lib/src/differs.dart
new file mode 100644
index 0000000..41f8a89
--- /dev/null
+++ b/lib/src/differs.dart
@@ -0,0 +1,35 @@
+// Copyright (c) 2016, 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 observable.src.differs;
+
+import 'dart:math' as math;
+
+import 'package:collection/collection.dart';
+
+import 'records.dart';
+
+part 'differs/list_differ.dart';
+
+/// Generic comparisons between two comparable objects.
+abstract class Differ<E> {
+ /// Returns a list of change records between [e1] and [e2].
+ ///
+ /// A return value of an empty [ChangeRecord.NONE] means no changes found.
+ List<ChangeRecord> diff(E e1, E e2);
+}
+
+/// Uses [Equality] to determine a simple [ChangeRecord.ANY] response.
+class EqualityDiffer<E> implements Differ<E> {
+ final Equality<E> _equality;
+
+ const EqualityDiffer([this._equality = const DefaultEquality()]);
+
+ const EqualityDiffer.identity() : this._equality = const IdentityEquality();
+
+ @override
+ List<ChangeRecord> diff(E e1, E e2) {
+ return _equality.equals(e1, e2) ? ChangeRecord.NONE : ChangeRecord.ANY;
+ }
+}
diff --git a/lib/src/differs/list_differ.dart b/lib/src/differs/list_differ.dart
new file mode 100644
index 0000000..2ca0c09
--- /dev/null
+++ b/lib/src/differs/list_differ.dart
@@ -0,0 +1,470 @@
+// Copyright (c) 2016, 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.
+
+part of observable.src.differs;
+
+/// Determines differences between two lists, returning [ListChangeRecord]s.
+///
+/// While [ListChangeRecord] has more information and can be replayed they carry
+/// a more significant cost to calculate and create and should only be used when
+/// the details in the record will actually be used.
+///
+/// See also [EqualityDiffer] for a simpler comparison.
+class ListDiffer<E> implements Differ<List<E>> {
+ final Equality<E> _equality;
+
+ const ListDiffer([this._equality = const DefaultEquality<E>()]);
+
+ @override
+ List<ListChangeRecord<E>> diff(List<E> e1, List<E> e2) {
+ return _calcSplices/*<E>*/(
+ e2,
+ _equality,
+ 0,
+ e2.length,
+ e1,
+ 0,
+ e1.length,
+ );
+ }
+}
+
+enum _Edit {
+ leave,
+ update,
+ add,
+ delete,
+}
+
+// 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>> _calcEditDistance/*<E>*/(
+ List/*<E>*/ current,
+ int currentStart,
+ int currentEnd,
+ List/*<E>*/ old,
+ int oldStart,
+ int oldEnd,
+) {
+ // 'Deletion' columns.
+ final rowCount = oldEnd - oldStart + 1;
+ final columnCount = currentEnd - currentStart + 1;
+ final distances = new List<List<int>>(rowCount);
+
+ // 'Addition' rows. Initialize null column.
+ for (var i = 0; i < rowCount; i++) {
+ distances[i] = new List<int>(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 {
+ final north = distances[i - 1][j] + 1;
+ final west = distances[i][j - 1] + 1;
+ distances[i][j] = math.min(north, west);
+ }
+ }
+ }
+
+ return distances;
+}
+
+// This starts at the final weight, and walks "backward" by finding
+// the minimum previous weight recursively until the origin of the weight
+// matrix.
+Iterable<_Edit> _spliceOperationsFromEditDistances(List<List<int>> distances) {
+ var i = distances.length - 1;
+ var j = distances[0].length - 1;
+ var current = distances[i][j];
+ final edits = <_Edit>[];
+ while (i > 0 || j > 0) {
+ if (i == 0) {
+ edits.add(_Edit.add);
+ j--;
+ continue;
+ }
+ if (j == 0) {
+ edits.add(_Edit.delete);
+ i--;
+ continue;
+ }
+ final northWest = distances[i - 1][j - 1];
+ final west = distances[i - 1][j];
+ final north = distances[i][j - 1];
+
+ final 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;
+}
+
+int _sharedPrefix/*<E>*/(
+ Equality/*<E>*/ equality,
+ List/*<E>*/ e1,
+ List/*<E>*/ e2,
+ int searchLength,
+) {
+ for (var i = 0; i < searchLength; i++) {
+ if (!equality.equals(e1[i], e2[i])) {
+ return i;
+ }
+ }
+ return searchLength;
+}
+
+int _sharedSuffix/*<E>*/(
+ Equality/*<E>*/ equality,
+ List/*<E>*/ e1,
+ List/*<E>*/ e2,
+ int searchLength,
+) {
+ var index1 = e1.length;
+ var index2 = e2.length;
+ var count = 0;
+ while (count < searchLength && equality.equals(e1[--index1], e2[--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/*<E>*/ > _calcSplices/*<E>*/(
+ List/*<E>*/ current,
+ Equality/*<E>*/ equality,
+ int currentStart,
+ int currentEnd,
+ List/*<E>*/ old,
+ int oldStart,
+ int oldEnd,
+) {
+ var prefixCount = 0;
+ var suffixCount = 0;
+ final minLength = math.min(currentEnd - currentStart, oldEnd - oldStart);
+ if (currentStart == 0 && oldStart == 0) {
+ prefixCount = _sharedPrefix(
+ equality,
+ current,
+ old,
+ minLength,
+ );
+ }
+ if (currentEnd == current.length && oldEnd == old.length) {
+ suffixCount = _sharedSuffix(
+ equality,
+ current,
+ old,
+ minLength - prefixCount,
+ );
+ }
+
+ currentStart += prefixCount;
+ oldStart += prefixCount;
+ currentEnd -= suffixCount;
+ oldEnd -= suffixCount;
+
+ if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0) {
+ return ChangeRecord.NONE;
+ }
+
+ if (currentStart == currentEnd) {
+ final spliceRemoved = old.sublist(oldStart, oldStart + oldEnd);
+ return [
+ new ListChangeRecord/*<E>*/ .remove(
+ current,
+ currentStart,
+ spliceRemoved,
+ ),
+ ];
+ }
+ if (oldStart == oldEnd) {
+ return [
+ new ListChangeRecord/*<E>*/ .add(
+ current,
+ currentStart,
+ currentEnd - currentStart,
+ ),
+ ];
+ }
+
+ final ops = _spliceOperationsFromEditDistances(
+ _calcEditDistance(
+ current,
+ currentStart,
+ currentEnd,
+ old,
+ oldStart,
+ oldEnd,
+ ),
+ );
+
+ var spliceIndex = -1;
+ var spliceRemovals = /*<E>*/ [];
+ var spliceAddedCount = 0;
+
+ bool hasSplice() => spliceIndex != -1;
+ void resetSplice() {
+ spliceIndex = -1;
+ spliceRemovals = /*<E>*/ [];
+ spliceAddedCount = 0;
+ }
+
+ var splices = <ListChangeRecord/*<E>*/ >[];
+
+ var index = currentStart;
+ var oldIndex = oldStart;
+ for (final op in ops) {
+ switch (op) {
+ case _Edit.leave:
+ if (hasSplice()) {
+ splices.add(new ListChangeRecord/*<E>*/(
+ current,
+ spliceIndex,
+ removed: spliceRemovals,
+ addedCount: spliceAddedCount,
+ ));
+ resetSplice();
+ }
+ index++;
+ oldIndex++;
+ break;
+ case _Edit.update:
+ if (!hasSplice()) {
+ spliceIndex = index;
+ }
+ spliceAddedCount++;
+ index++;
+ spliceRemovals.add(old[oldIndex]);
+ oldIndex++;
+ break;
+ case _Edit.add:
+ if (!hasSplice()) {
+ spliceIndex = index;
+ }
+ spliceAddedCount++;
+ index++;
+ break;
+ case _Edit.delete:
+ if (!hasSplice()) {
+ spliceIndex = index;
+ }
+ spliceRemovals.add(old[oldIndex]);
+ oldIndex++;
+ break;
+ }
+ }
+ if (hasSplice()) {
+ splices.add(new ListChangeRecord<E>(
+ current,
+ spliceIndex,
+ removed: spliceRemovals,
+ addedCount: spliceAddedCount,
+ ));
+ }
+ assert(() {
+ splices = new List<ListChangeRecord/*<E>*/ >.unmodifiable(splices);
+ return true;
+ });
+ return splices;
+}
+
+int _intersect(int start1, int end1, int start2, int end2) {
+ return math.min(end1, end2) - math.max(start1, start2);
+}
+
+void _mergeSplices/*<E>*/(
+ List<ListChangeRecord/*<E>*/ > splices,
+ ListChangeRecord/*<E>*/ record,
+) {
+ var spliceIndex = record.index;
+ var spliceRemoved = record.removed;
+ var spliceAdded = 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++) {
+ var current = splices[i];
+ current = splices[i] = new ListChangeRecord<E>(
+ current.object,
+ current.index + insertionOffset,
+ removed: current.removed,
+ addedCount: current.addedCount,
+ );
+
+ if (inserted) continue;
+
+ var intersectCount = _intersect(
+ spliceIndex,
+ spliceIndex + spliceRemoved.length,
+ current.index,
+ current.index + current.addedCount,
+ );
+ if (intersectCount >= 0) {
+ // Merge the two splices.
+ splices.removeAt(i);
+ i--;
+
+ insertionOffset -= current.addedCount - current.removed.length;
+ spliceAdded += current.addedCount - intersectCount;
+
+ final deleteCount =
+ spliceRemoved.length + current.removed.length - intersectCount;
+ if (spliceAdded == 0 && deleteCount == 0) {
+ // Merged splice is a no-op, discard.
+ inserted = true;
+ } else {
+ final removed = current.removed.toList();
+ if (spliceIndex < current.index) {
+ // Some prefix of splice.removed is prepended to current.removed.
+ removed.insertAll(
+ 0,
+ spliceRemoved.getRange(0, current.index - spliceIndex),
+ );
+ }
+ if (spliceIndex + spliceRemoved.length >
+ current.index + current.addedCount) {
+ // Some suffix of splice.removed is appended to current.removed.
+ removed.addAll(spliceRemoved.getRange(
+ current.index + current.addedCount - spliceIndex,
+ spliceRemoved.length,
+ ));
+ }
+ spliceRemoved = removed;
+ if (current.index < spliceIndex) {
+ spliceIndex = current.index;
+ }
+ }
+ } else if (spliceIndex < current.index) {
+ // Insert splice here.
+ inserted = true;
+ splices.insert(
+ i,
+ new ListChangeRecord/*<E>*/(
+ record.object,
+ spliceIndex,
+ removed: spliceRemoved,
+ addedCount: spliceAdded,
+ ),
+ );
+ i++;
+ final offset = spliceAdded - spliceRemoved.length;
+ current = splices[i] = new ListChangeRecord<E>(
+ current.object,
+ current.index + offset,
+ removed: current.removed,
+ addedCount: current.addedCount,
+ );
+ insertionOffset += offset;
+ }
+ }
+ if (!inserted) {
+ splices.add(new ListChangeRecord/*<E>*/(
+ record.object,
+ spliceIndex,
+ removed: spliceRemoved,
+ addedCount: spliceAdded,
+ ));
+ }
+}
+
+List<ListChangeRecord/*<E>*/ > _createInitialSplices/*<E>*/(
+ List/*<E>*/ list,
+ List<ListChangeRecord/*<E>*/ > records,
+) {
+ final splices = <ListChangeRecord/*<E>*/ >[];
+ for (var i = 0; i < records.length; i++) {
+ _mergeSplices(splices, records[i]);
+ }
+ 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/*<E>*/ > projectListSplices/*<E>*/(
+ List/*<E>*/ list,
+ List<ListChangeRecord/*<E>*/ > records, [
+ Equality/*<E>*/ equality = const DefaultEquality/*<E>*/(),
+]) {
+ if (records.length <= 1) return records;
+ final splices = <ListChangeRecord/*<E>*/ >[];
+ final initialSplices = _createInitialSplices(list, records);
+ for (final splice in initialSplices) {
+ if (splice.addedCount == 1 && splice.removed.length == 1) {
+ if (splice.removed[0] != list[splice.index]) {
+ splices.add(splice);
+ }
+ continue;
+ }
+ splices.addAll(
+ _calcSplices(
+ list,
+ equality,
+ splice.index,
+ splice.index + splice.addedCount,
+ splice.removed,
+ 0,
+ splice.removed.length,
+ ),
+ );
+ }
+ return splices;
+}
diff --git a/lib/src/list_diff.dart b/lib/src/list_diff.dart
deleted file mode 100644
index c16a613..0000000
--- a/lib/src/list_diff.dart
+++ /dev/null
@@ -1,398 +0,0 @@
-// Copyright (c) 2016, 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 observable.src.list_diff;
-
-import 'dart:collection' show UnmodifiableListView;
-import 'dart:math' as math;
-
-import 'change_record.dart' show ChangeRecord;
-
-/// 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 /* TODO(tvolkert): remove */ extends ChangeRecord {
- /// 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, List 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 [ref] index was changed by this operation.
- bool indexChanged(int ref) {
- // If ref is before the index, then it wasn't changed.
- if (ref < 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 ref < 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,
- int currentEnd, List old, int oldStart, int oldEnd) {
- // "Deletion" columns
- int rowCount = oldEnd - oldStart + 1;
- int columnCount = currentEnd - currentStart + 1;
- List<List<int>> distances = new List<List<int>>(rowCount);
-
- // "Addition" rows. Initialize null column.
- for (int i = 0; i < rowCount; i++) {
- distances[i] = new List(columnCount);
- distances[i][0] = i;
- }
-
- // Initialize null row
- for (int j = 0; j < columnCount; j++) {
- distances[0][j] = j;
- }
-
- for (int i = 1; i < rowCount; i++) {
- for (int j = 1; j < columnCount; j++) {
- if (old[oldStart + i - 1] == current[currentStart + j - 1]) {
- distances[i][j] = distances[i - 1][j - 1];
- } else {
- int north = distances[i - 1][j] + 1;
- int west = distances[i][j - 1] + 1;
- distances[i][j] = math.min(north, west);
- }
- }
- }
-
- return distances;
-}
-
-const _kEditLeave = 0;
-const _kEditUpdate = 1;
-const _kEditAdd = 2;
-const _kEditDelete = 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) {
- int i = distances.length - 1;
- int j = distances[0].length - 1;
- int current = distances[i][j];
- List<int> edits = <int>[];
- while (i > 0 || j > 0) {
- if (i == 0) {
- edits.add(_kEditAdd);
- j--;
- continue;
- }
- if (j == 0) {
- edits.add(_kEditDelete);
- i--;
- continue;
- }
- int northWest = distances[i - 1][j - 1];
- int west = distances[i - 1][j];
- int north = distances[i][j - 1];
-
- int min = math.min(math.min(west, north), northWest);
-
- if (min == northWest) {
- if (northWest == current) {
- edits.add(_kEditLeave);
- } else {
- edits.add(_kEditUpdate);
- current = northWest;
- }
- i--;
- j--;
- } else if (min == west) {
- edits.add(_kEditDelete);
- i--;
- current = west;
- } else {
- edits.add(_kEditAdd);
- j--;
- current = north;
- }
- }
-
- return edits.reversed.toList();
-}
-
-int _sharedPrefix(List arr1, List arr2, int searchLength) {
- for (int i = 0; i < searchLength; i++) {
- if (arr1[i] != arr2[i]) {
- return i;
- }
- }
- return searchLength;
-}
-
-int _sharedSuffix(List arr1, List arr2, int searchLength) {
- int index1 = arr1.length;
- int index2 = arr2.length;
- int 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,
- int currentEnd, List old, int oldStart, int oldEnd) {
- int prefixCount = 0;
- int suffixCount = 0;
-
- int 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) {
- ListChangeRecord 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)
- ];
- }
-
- List<int> ops = _spliceOperationsFromEditDistances(_calcEditDistances(
- current, currentStart, currentEnd, old, oldStart, oldEnd));
-
- ListChangeRecord splice;
- List<ListChangeRecord> splices = <ListChangeRecord>[];
- int index = currentStart;
- int oldIndex = oldStart;
- for (int i = 0; i < ops.length; i++) {
- switch (ops[i]) {
- case _kEditLeave:
- if (splice != null) {
- splices.add(splice);
- splice = null;
- }
-
- index++;
- oldIndex++;
- break;
- case _kEditUpdate:
- if (splice == null) splice = new ListChangeRecord(current, index);
-
- splice._addedCount++;
- index++;
-
- splice._removed.add(old[oldIndex]);
- oldIndex++;
- break;
- case _kEditAdd:
- if (splice == null) splice = new ListChangeRecord(current, index);
-
- splice._addedCount++;
- index++;
- break;
- case _kEditDelete:
- 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) =>
- math.min(end1, end2) - math.max(start1, start2);
-
-void _mergeSplice(List<ListChangeRecord> splices, ListChangeRecord record) {
- ListChangeRecord splice = new ListChangeRecord(record.object, record.index,
- removed: record._removed.toList(), addedCount: record.addedCount);
-
- bool inserted = false;
- int 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 (int i = 0; i < splices.length; i++) {
- final ListChangeRecord current = splices[i];
- current._index += insertionOffset;
-
- if (inserted) continue;
-
- int 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;
- int deleteCount =
- splice.removed.length + current.removed.length - intersectCount;
-
- if (splice.addedCount == 0 && deleteCount == 0) {
- // merged splice is a noop. discard.
- inserted = true;
- } else {
- List 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++;
-
- int 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) {
- List<ListChangeRecord> splices = [];
- for (ListChangeRecord 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<Object> list, List<ListChangeRecord> records) {
- if (records.length <= 1) return records;
-
- List<ListChangeRecord> splices = <ListChangeRecord>[];
- for (ListChangeRecord 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;
-}
diff --git a/lib/src/observable.dart b/lib/src/observable.dart
index 7d1ec6f..b76b13f 100644
--- a/lib/src/observable.dart
+++ b/lib/src/observable.dart
@@ -9,8 +9,9 @@
import 'package:meta/meta.dart';
-import 'change_record.dart' show ChangeRecord;
+import 'observable_map.dart';
import 'property_change_record.dart' show PropertyChangeRecord;
+import 'records.dart' show ChangeRecord;
/// Represents an object with observable properties. This is used by data in
/// model-view architectures to notify interested parties of [changes] to the
diff --git a/lib/src/observable_list.dart b/lib/src/observable_list.dart
index 16c49f5..9e3481b 100644
--- a/lib/src/observable_list.dart
+++ b/lib/src/observable_list.dart
@@ -7,7 +7,8 @@
import 'dart:async';
import 'dart:collection' show ListBase, UnmodifiableListView;
-import 'list_diff.dart' show ListChangeRecord, projectListSplices, calcSplices;
+import 'differs.dart';
+import 'records.dart';
import 'observable.dart' show Observable;
/// Represents an observable list of model values. If any items are added,
@@ -79,8 +80,10 @@
bool get hasListObservers => _listChanges != null && _listChanges.hasListener;
+ @override
int get length => _list.length;
+ @override
set length(int value) {
int len = _list.length;
if (len == value) return;
@@ -98,8 +101,10 @@
_list.length = value;
}
+ @override
E operator [](int index) => _list[index];
+ @override
void operator []=(int index, E value) {
E oldValue = _list[index];
if (hasListObservers && oldValue != value) {
@@ -109,7 +114,10 @@
}
// Forwarders so we can reflect on the properties.
+ @override
bool get isEmpty => super.isEmpty;
+
+ @override
bool get isNotEmpty => super.isNotEmpty;
// TODO(jmesserly): should we support first/last/single? They're kind of
@@ -118,7 +126,7 @@
// existing list notifications.
// The following methods are here so that we can provide nice change events.
-
+ @override
void setAll(int index, Iterable<E> iterable) {
if (iterable is! List && iterable is! Set) {
iterable = iterable.toList();
@@ -131,6 +139,7 @@
_list.setAll(index, iterable);
}
+ @override
void add(E value) {
int len = _list.length;
_notifyChangeLength(len, len + 1);
@@ -141,6 +150,7 @@
_list.add(value);
}
+ @override
void addAll(Iterable<E> iterable) {
int len = _list.length;
_list.addAll(iterable);
@@ -153,6 +163,7 @@
}
}
+ @override
bool remove(Object element) {
for (int i = 0; i < this.length; i++) {
if (this[i] == element) {
@@ -163,6 +174,7 @@
return false;
}
+ @override
void removeRange(int start, int end) {
_rangeCheck(start, end);
int rangeLength = end - start;
@@ -176,6 +188,7 @@
_list.removeRange(start, end);
}
+ @override
void insertAll(int index, Iterable<E> iterable) {
if (index < 0 || index > length) {
throw new RangeError.range(index, 0, length);
@@ -201,6 +214,7 @@
}
}
+ @override
void insert(int index, E element) {
if (index < 0 || index > length) {
throw new RangeError.range(index, 0, length);
@@ -223,6 +237,7 @@
_list[index] = element;
}
+ @override
E removeAt(int index) {
E result = this[index];
removeRange(index, index + 1);
@@ -238,14 +253,22 @@
}
}
- void _notifyListChange(int index, {List removed, int addedCount}) {
+ void _notifyListChange(
+ int index, {
+ List removed: const [],
+ int addedCount: 0,
+ }) {
if (!hasListObservers) return;
if (_listRecords == null) {
_listRecords = [];
scheduleMicrotask(deliverListChanges);
}
- _listRecords.add(new ListChangeRecord(this, index,
- removed: removed, addedCount: addedCount));
+ _listRecords.add(new ListChangeRecord(
+ this,
+ index,
+ removed: removed,
+ addedCount: addedCount,
+ ));
}
void _notifyChangeLength(int oldValue, int newValue) {
@@ -261,7 +284,8 @@
bool deliverListChanges() {
if (_listRecords == null) return false;
- List<ListChangeRecord> records = projectListSplices(this, _listRecords);
+ List<ListChangeRecord> records =
+ projectListSplices/*<E>*/(this, _listRecords);
_listRecords = null;
if (hasListObservers && records.isNotEmpty) {
@@ -283,9 +307,12 @@
///
/// Complexity is `O(l * p)` where `l` is the length of the current list and
/// `p` is the length of the old list.
- static List<ListChangeRecord> calculateChangeRecords(
- List<Object> oldValue, List<Object> newValue) =>
- calcSplices(newValue, 0, newValue.length, oldValue, 0, oldValue.length);
+ static List<ListChangeRecord/*<E>*/ > calculateChangeRecords/*<E>*/(
+ List/*<E>*/ oldValue,
+ List/*<E>*/ newValue,
+ ) {
+ return const ListDiffer<E>().diff(oldValue, newValue);
+ }
/// Updates the [previous] list using the [changeRecords]. For added items,
/// the [current] list is used to find the current value.
diff --git a/lib/src/observable_map.dart b/lib/src/observable_map.dart
index 23a7f11..c1e2c90 100644
--- a/lib/src/observable_map.dart
+++ b/lib/src/observable_map.dart
@@ -6,9 +6,10 @@
import 'dart:collection';
-import 'change_record.dart' show ChangeRecord;
import 'observable.dart' show Observable;
import 'property_change_record.dart' show PropertyChangeRecord;
+import 'records.dart' show ChangeRecord;
+import 'to_observable.dart';
// TODO(jmesserly): this needs to be faster. We currently require multiple
// lookups per key to get the old value.
@@ -50,6 +51,7 @@
isRemove = true,
newValue = null;
+ @override
String toString() {
var kind = isInsert ? 'insert' : isRemove ? 'remove' : 'set';
return '#<MapChangeRecord $kind $key from: $oldValue to: $newValue>';
@@ -95,22 +97,31 @@
return result;
}
+ @override
Iterable<K> get keys => _map.keys;
+ @override
Iterable<V> get values => _map.values;
+ @override
int get length => _map.length;
+ @override
bool get isEmpty => length == 0;
+ @override
bool get isNotEmpty => !isEmpty;
+ @override
bool containsValue(Object value) => _map.containsValue(value);
+ @override
bool containsKey(Object key) => _map.containsKey(key);
+ @override
V operator [](Object key) => _map[key];
+ @override
void operator []=(K key, V value) {
if (!hasObservers) {
_map[key] = value;
@@ -132,12 +143,14 @@
}
}
+ @override
void addAll(Map<K, V> other) {
other.forEach((K key, V value) {
this[key] = value;
});
}
+ @override
V putIfAbsent(K key, V ifAbsent()) {
int len = _map.length;
V result = _map.putIfAbsent(key, ifAbsent);
@@ -149,6 +162,7 @@
return result;
}
+ @override
V remove(Object key) {
int len = _map.length;
V result = _map.remove(key);
@@ -160,6 +174,7 @@
return result;
}
+ @override
void clear() {
int len = _map.length;
if (hasObservers && len > 0) {
@@ -172,8 +187,10 @@
_map.clear();
}
+ @override
void forEach(void f(K key, V value)) => _map.forEach(f);
+ @override
String toString() => Maps.mapToString(this);
// Note: we don't really have a reasonable old/new value to use here.
diff --git a/lib/src/property_change_record.dart b/lib/src/property_change_record.dart
index a09c196..153cb5d 100644
--- a/lib/src/property_change_record.dart
+++ b/lib/src/property_change_record.dart
@@ -4,7 +4,8 @@
library observable.src.property_change_record;
-import 'change_record.dart';
+import 'observable.dart';
+import 'records.dart' show ChangeRecord;
/// A change record to a field of an [Observable] object.
class PropertyChangeRecord<T> extends ChangeRecord {
@@ -22,6 +23,7 @@
PropertyChangeRecord(this.object, this.name, this.oldValue, this.newValue);
+ @override
String toString() =>
'#<PropertyChangeRecord $name from: $oldValue to: $newValue>';
}
diff --git a/lib/src/records.dart b/lib/src/records.dart
new file mode 100644
index 0000000..a04ae9e
--- /dev/null
+++ b/lib/src/records.dart
@@ -0,0 +1,24 @@
+// Copyright (c) 2016, 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 observable.src.records;
+
+import 'package:collection/collection.dart';
+import 'package:quiver/core.dart';
+
+part 'records/list_change_record.dart';
+
+/// Result of a change to an observed object.
+class ChangeRecord {
+ /// Signifies a change occurred, but without details of the specific change.
+ ///
+ /// May be used to produce lower-GC-pressure records where more verbose change
+ /// records will not be used directly.
+ static const List<ChangeRecord> ANY = const [const ChangeRecord()];
+
+ /// Signifies no changes occurred.
+ static const List<ChangeRecord> NONE = const [];
+
+ const ChangeRecord();
+}
diff --git a/lib/src/records/list_change_record.dart b/lib/src/records/list_change_record.dart
new file mode 100644
index 0000000..aeb77d6
--- /dev/null
+++ b/lib/src/records/list_change_record.dart
@@ -0,0 +1,140 @@
+// Copyright (c) 2016, 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.
+
+part of observable.src.records;
+
+List/*<E>*/ _freezeInDevMode/*<E>*/(List/*<E>*/ list) {
+ if (list == null) return const [];
+ assert(() {
+ list = new List/*<E>*/ .unmodifiable(list);
+ return true;
+ });
+ return list;
+}
+
+/// A [ChangeRecord] that denotes adding or removing nodes at [index].
+///
+/// It should be assumed that elements are [removed] *before* being added.
+///
+/// A [List<ListChangeRecord>] can be "played back" against the [List] using
+/// the final list positions to figure out which item was added - this removes
+/// the need to incur costly GC on the most common operation (adding).
+class ListChangeRecord<E> implements ChangeRecord {
+ /// How many elements were added at [index] (after removing elements).
+ final int addedCount;
+
+ /// Index of where the change occurred.
+ final int index;
+
+ /// List that changed.
+ final List<E> object;
+
+ /// Elements that were removed starting at [index] (before adding elements).
+ final List<E> removed;
+
+ factory ListChangeRecord(
+ List<E> object,
+ int index, {
+ List<E> removed: const [],
+ int addedCount: 0,
+ }) {
+ return new ListChangeRecord._(object, index, removed, addedCount);
+ }
+
+ /// Records an `add` operation at `object[index]` of [addedCount] elements.
+ ListChangeRecord.add(this.object, this.index, this.addedCount)
+ : removed = const [] {
+ _assertValidState();
+ }
+
+ /// Records a `remove` operation at `object[index]` of [removed] elements.
+ ListChangeRecord.remove(this.object, this.index, List<E> removed)
+ : this.removed = _freezeInDevMode/*<E>*/(removed),
+ this.addedCount = 0 {
+ _assertValidState();
+ }
+
+ /// Records a `replace` operation at `object[index]` of [removed] elements.
+ ///
+ /// If [addedCount] is not specified it defaults to `removed.length`.
+ ListChangeRecord.replace(this.object, this.index, List<E> removed,
+ [int addedCount])
+ : this.removed = _freezeInDevMode/*<E>*/(removed),
+ this.addedCount = addedCount ?? removed.length {
+ _assertValidState();
+ }
+
+ ListChangeRecord._(
+ this.object,
+ this.index,
+ this.removed,
+ this.addedCount,
+ ) {
+ _assertValidState();
+ }
+
+ /// What elements were added to [object].
+ Iterable<E> get added {
+ return addedCount == 0 ? const [] : object.getRange(index, addedCount);
+ }
+
+ /// Apply this change record to [list].
+ void apply(List<E> list) {
+ list
+ ..removeRange(index, index + removed.length)
+ ..insertAll(index, object.getRange(index, index + addedCount));
+ }
+
+ void _assertValidState() {
+ assert(() {
+ if (object == null) {
+ throw new ArgumentError.notNull('object');
+ }
+ if (index == null) {
+ throw new ArgumentError.notNull('index');
+ }
+ if (removed == null) {
+ throw new ArgumentError.notNull('removed');
+ }
+ if (addedCount == null || addedCount < 0) {
+ throw new ArgumentError('Invalid `addedCount`: $addedCount');
+ }
+ return true;
+ });
+ }
+
+ /// Returns whether [reference] index was changed in this operation.
+ bool indexChanged(int reference) {
+ // If reference was before the change then it wasn't changed.
+ if (reference < 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 reference < index + addedCount;
+ }
+
+ @override
+ bool operator ==(Object o) {
+ if (o is ListChangeRecord<E>) {
+ return identical(object, o.object) &&
+ index == o.index &&
+ addedCount == o.addedCount &&
+ const ListEquality().equals(removed, o.removed);
+ }
+ return false;
+ }
+
+ @override
+ int get hashCode {
+ return hash4(object, index, addedCount, const ListEquality().hash(removed));
+ }
+
+ @override
+ String toString() => ''
+ '#<$ListChangeRecord index: $index, '
+ 'removed: $removed, '
+ 'addedCount: $addedCount>';
+}
diff --git a/lib/src/to_observable.dart b/lib/src/to_observable.dart
index 0a0f316..3bf24b6 100644
--- a/lib/src/to_observable.dart
+++ b/lib/src/to_observable.dart
@@ -4,6 +4,8 @@
library observable.src.to_observable;
+import 'dart:collection';
+
import 'observable.dart' show Observable;
import 'observable_list.dart' show ObservableList;
import 'observable_map.dart' show ObservableMap;
diff --git a/pubspec.yaml b/pubspec.yaml
index b030500..edb5d55 100644
--- a/pubspec.yaml
+++ b/pubspec.yaml
@@ -1,11 +1,13 @@
name: observable
-version: 0.14.0+1
+version: 0.15.0
author: Dart Team <misc@dartlang.org>
description: Support for marking objects as observable
homepage: https://github.com/dart-lang/observable
environment:
sdk: '>=1.19.0 <2.0.0'
dependencies:
+ collection: '^1.11.0'
meta: '^1.0.4'
+ quiver: '^0.24.0'
dev_dependencies:
test: '^0.12.0'
diff --git a/test/list_change_test.dart b/test/list_change_test.dart
index b07c0b8..2c7446e 100644
--- a/test/list_change_test.dart
+++ b/test/list_change_test.dart
@@ -20,7 +20,7 @@
var model;
tearDown(() {
- sub.cancel();
+ sub?.cancel();
model = null;
});
@@ -47,7 +47,6 @@
sub = model.listChanges.listen((r) => summary = r);
model.length = 2;
-
return new Future(() {
expectChanges(summary, [
_delta(2, ['c', 'd', 'e'], 0)
@@ -62,14 +61,10 @@
group('List deltas can be applied', () {
applyAndCheckDeltas(model, copy, changes) => changes.then((summary) {
// apply deltas to the copy
- for (var delta in summary) {
- copy.removeRange(delta.index, delta.index + delta.removed.length);
- for (int i = delta.addedCount - 1; i >= 0; i--) {
- copy.insert(delta.index, model[delta.index + i]);
- }
+ for (ListChangeRecord delta in summary) {
+ delta.apply(copy);
}
- // Note: compare strings for easier debugging.
expect('$copy', '$model', reason: 'summary $summary');
});
diff --git a/test/observable_test.dart b/test/observable_test.dart
index b89d654..eb824c7 100644
--- a/test/observable_test.dart
+++ b/test/observable_test.dart
@@ -218,5 +218,6 @@
T _value;
+ @override
String toString() => '#<$runtimeType value: $value>';
}
diff --git a/test/observable_test_utils.dart b/test/observable_test_utils.dart
index 91d4d8f..990cc86 100644
--- a/test/observable_test_utils.dart
+++ b/test/observable_test_utils.dart
@@ -13,8 +13,6 @@
/// to happen in the next microtask:
///
/// future.then(newMicrotask).then(...)
-///
-/// Uses [mu].
newMicrotask(_) => new Future.value();
// TODO(jmesserly): use matchers when we have a way to compare ChangeRecords.
