Support for observable models, fixes #259

lib/observe.dart

Index: lib/observe.dart
diff --git a/lib/observe.dart b/lib/observe.dart
new file mode 100644
index 0000000000000000000000000000000000000000..3e02805c5cdc666905acf20d3b96845ed56502e2
--- /dev/null
+++ b/lib/observe.dart
@@ -0,0 +1,449 @@
+// Copyright (c) 2012, 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.
+
+/**
+ * A library for observing changes to observable Dart objects.
+ * Similar in spirit to EcmaScript 6

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

6 => 7
(and below)

[Jennifer Messerly, 2013/02/13 05:43:15]

yeah. Or maybe "EcmaScript Harmony"--to match the wiki? I dunno how "committed"
ECMAScript is to shipping it in any particular version. I kind of don't trust ES
to stick to a particular version until something actually shows up in the draft
spec, especially since it changed already since I wrote this :)

+ * [Object.observe](http://wiki.ecmascript.org/doku.php?id=harmony:observe), but
+ * able to observe expressions and not just objects, so long as the expressions
+ * are computed from observable objects.
+ *
+ * See the [observable] annotation and the [observe] function.
+ */
+// Note: one intentional difference from ES6 Object.observe is that our change
+// batches are tracked on a per-observed expression basis, instead of per-observer basis.

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

long line

[Jennifer Messerly, 2013/02/13 05:43:15]

Done.

+// We do this because there is no cheap way to store a pointer on a Dart
+// function (Expando uses linear search on the VM: http://dartbug.com/7558).
+// This difference means that a given observer will be called with one batch of
+// changes for each object it is observing.
+library observe;
+
+import 'dart:collection';
+import 'src/utils.dart' show setImmediate;

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

funny, I never considered using 'src/utils.dart' for the runtime apps (only for
the compiler) =)

FYI - not necessarily for this change, but we should get rid of setImmediate and
use Future.immedate instead. Future.immediate is already asynchronous, but I
think right now it is doing setTimout(0) instead of setImmediate. Once that's
fixed, we should switch to it.

See: 
https://groups.google.com/a/dartlang.org/forum/?hl=en&fromgroups=#!searchin/m...

[Jennifer Messerly, 2013/02/13 05:43:15]

Agreed, I hope our version goes away soon. Added TODO!

+
+// TODO(jmesserly): support detailed change records on our collections, such as
+// INSERT/REMOVE, so we can use them from templates. Unlike normal objects,
+// list/map/set can add or remove new observable things at runtime, so it's
+// important to provide a way to listen for that.
+export 'observe/list.dart';
+export 'observe/map.dart';
+export 'observe/reference.dart';
+export 'observe/set.dart';
+
+// TODO(jmesserly): notifyRead/notifyWrite are only used by people
+// implementating advanced observable functionality. The need to be public, but

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

The => they

[Jennifer Messerly, 2013/02/13 05:43:15]

Done. Good catch!

+// ideally they would not be in the top level "observe" library.
+
+/**
+ * Use `@observable` to make a class observable. All fields in the class will
+ * be transformed to track changes. The overhead will be minimal unless they are
+ * actually being observed.
+ */
+const observable = const Object();
+
+/** Callback fired when an expression changes. */
+typedef void ChangeObserver(ChangeNotification e);
+
+/** A function that unregisters the [ChangeObserver]. */
+typedef void ChangeUnobserver();
+
+/** A function that computes a value. */
+typedef Object ObservableExpression();
+
+/**
+ * A function that handles an [error] given the [stackTrace] and [callback] that
+ * caused the error.
+ */
+typedef void ObserverErrorHandler(error, stackTrace, Function callback);
+
+/**
+ * Test for equality of two objects. For example [Object.==] and [identical]
+ * are two kinds of equality tests.
+ */
+typedef bool EqualityTest(Object a, Object b);
+
+/**
+ * A notification of a change to an [ObservableExpression] that is passed to a
+ * [ChangeObserver].
+ */
+class ChangeNotification {
+
+  /** Previous value seen on the watched expression. */
+  final oldValue;
+
+  /** New value seen on the watched expression. */
+  final newValue;
+
+  ChangeNotification(this.oldValue, this.newValue);
+
+  // Note: these two methods are here mainly to make testing easier.
+  bool operator ==(other) {
+    return other is ChangeNotification && oldValue == other.oldValue &&
+        newValue == other.newValue;
+  }
+
+  String toString() => 'change from $oldValue to $newValue';
+}
+
+/**
+ * Observes the [expression] and delivers asynchronous notifications of changes
+ * to the [callback].
+ *
+ * The expression is considered to have changed if the values no longer compare
+ * equal via the equality operator. You can perform additional comparisons in
+ * the [callback] if desired.
+ *
+ * Returns a function that can be used to stop observation.
+ * Calling this makes it possible for the garbage collector to reclaim memory
+ * associated with the observation and prevents further calls to [callback].
+ *
+ * Because notifications are delivered asynchronously and batched, only a single
+ * notification is provided for all changes that were made prior to running
+ * callback. Intermediate values of the expression are not saved. Instead,
+ * [ChangeNotification.oldValue] represents the value before any changes, and
+ * [ChangeNotification.newValue] represents the current value of [expression]
+ * at the time that [callback] is called.
+ *
+ * You can force a synchronous change delivery at any time by calling
+ * [deliverChangesSync]. Calling this method if there are no changes has no
+ * effect. If changes are delivered by deliverChangesSync, they will not be
+ * delivered again asynchronously, unless the value is changed again.
+ *
+ * Any errors thrown by [expression] and [callback] will be caught and sent to
+ * [onObserveUnhandledError]

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

add '.' at the end of the line

[Jennifer Messerly, 2013/02/13 05:43:15]

Done.

+ */
+// TODO(jmesserly): debugName is here to workaround http://dartbug.com/8419.
+ChangeUnobserver observe(ObservableExpression expression,
+    ChangeObserver callback, [String debugName]) {
+
+  var observer = new _ExpressionObserver(expression, callback, debugName);
+  if (!observer._observe()) {
+    // If we didn't actually read anything, return a pointer to a no-op
+    // function so the observer can be reclaimed immediately.
+    return _doNothing;
+  }
+
+  return observer._unobserve;
+}
+
+// Optimizations to avoid extra work if observing const/final data.
+void _doNothing() {}
+
+/**
+ * The current observer that is tracking reads, or null if we aren't tracking
+ * reads. Reads are tracked when executing [_ExpressionObserver._observe].
+ */
+_ExpressionObserver _activeObserver;
+
+/**
+ * True if we are observing reads. This should be checked before calling
+ * [notifyRead].
+ *
+ * Note: this type is used by objects implementing observability.
+ * You should not need it if your type is marked `@observable`.
+ */
+bool get observeReads => _activeObserver != null;
+
+/**
+ * Notify the system of a new read. This will add the current change observer
+ * to the set of observers for this field.  This should *only* be called when
+ * [observeReads] is true, and it will initialize [observers] if it is null.
+ * For example:
+ *
+ *     get foo {
+ *       if (observeReads) _fooObservers = notifyRead(_fooObservers);
+ *       return _foo;
+ *     }
+ *
+ * Note: this function is used to implement observability.
+ * You should not need it if your type is marked `@observable`.
+ *
+ * See also: [notifyWrite]
+ */
+Object notifyRead(fieldObservers) {

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

maybe document the possible types for fieldObservers?
(_ExpressionObserver, and List?)

[Jennifer Messerly, 2013/02/13 05:43:15]

Added comment inside the method. I intentionally don't want to say anything in
the public API.

Hoping this all gets replaced with detailed change records though.

+  _activeObserver._wasRead = true;
+
+  // Note: there's some optimization here to avoid allocating an observer list
+  // unless we really need it.
+  if (fieldObservers == null) {
+    return _activeObserver;
+  }
+  if (fieldObservers is _ExpressionObserver) {
+    if (identical(fieldObservers, _activeObserver) || fieldObservers._dead) {
+      return _activeObserver;
+    }
+    return [fieldObservers, _activeObserver];
+  }

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

maybe assert (fieldObservers is List)?

[Jennifer Messerly, 2013/02/13 05:43:15]

Trying to avoid anything here that will make this code slower. VM should throw a
NoSuchMethod error if "add" doesn't work. The idea is notifyRead/notifyWrite are
very much internal use-at-your-own-risk APIs.

(That's why I don't like them and want to replace with something more friendly)

+  return fieldObservers..add(_activeObserver);
+}
+
+/**
+ * Notify the system of a new write. This will deliver a change notification
+ * to the set of observers for this field. This should *only* be called for a
+ * non-null list of [observers]. For example:

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

would it be sensible to accept a null list and return immediately?

[Jennifer Messerly, 2013/02/13 05:43:15]

It's faster to avoid the call in the common case where you aren't observing
anything. (Also avoids the equality compare).

+ *
+ *     set foo(value) {
+ *       if (_fooObservers != null && _foo != value) {
+ *         _fooObservers = notifyWrite(_fooObservers);
+ *       }
+ *       _foo = value;
+ *     }
+ *
+ * Note: this function is used to implement observability.
+ * You should not need it if your type is marked `@observable`.
+ *
+ * See also: [notifyRead]
+ */
+Object notifyWrite(Object fieldObservers) {
+  if (_pendingWrites == null) {
+    _pendingWrites = [];
+    setImmediate(deliverChangesSync);
+  }
+  _pendingWrites.add(fieldObservers);
+
+  // Clear fieldObservers. This will prevent a second notification for this
+  // same set of observers on the current event loop. It also frees associated
+  // memory. If the item needs to be observed again, that will happen in
+  // _ExpressionObserver._deliver.
+
+  // NOTE: ObservableMap depends on this returning null.
+  return null;
+}
+
+List _pendingWrites;
+
+/**
+ * The limit of times we will attempt to deliver a set of pending changes.
+ *
+ * [deliverChangesSync] will attempt to deliver pending changes until there are
+ * no more. If one of the pending changes causes another batch of changes, it
+ * will iterate again and increment the iteration counter. Once it reaches
+ * this limit it will throw [CircularChangeNotifyError].
+ *
+ * Note that there is no limit to the number of changes per batch, only to the
+ * number of iterations.
+ */
+int circularNotificationLimit = 100;

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

100 feels big, but maybe because in watchers 10 felt big? What's the longest
number you have reached in some common samples (e.g. in jacob's app?)

[Jennifer Messerly, 2013/02/13 05:43:15]

Watchers are very different :). It meant you're computing every watched
expression in your entire program 10 times. It was 10x10000 == slow.

With observers, it can be more like 100x2 == very fast. 500 times faster than
the watcher limit :)

Also keep in mind Object.observe has no limit ("Object.deliverChangeRecords now
calls [[DeliverChangeRecords]] repeatedly until there no pending records to
deliver")

Apidoc is a simple read-only data viewer, I doubt it gets anywhere past 2, but
haven't measured. It couldn't be going by 10 -- because of our old limit :)

I actually suspect 100 is far too small to build anything like a spreadsheet in
it, which is why it's configurable. But maybe it should be a lot higher. It's
only intended as a way of breaking you out of your circular loop so you can
debug what went wrong.

+
+/**
+ * Delivers observed changes immediately. Normally you should not call this
+ * directly, but it can be used to force synchronous delivery, which helps in
+ * certain cases like testing.
+ */
+void deliverChangesSync() {
+  int iterations = 0;
+  while (_pendingWrites != null) {
+    var pendingWrites = _pendingWrites;
+    _pendingWrites = null;
+
+    // Sort pending observers by order added.
+    // TODO(jmesserly): this is here to help our template system, which relies
+    // on earlier observers removing later ones to prevent them from firing.
+    // See if we can find a better solution at the template level.
+    var pendingObservers = new SplayTreeMap<int, _ExpressionObserver>();
+    for (var pending in pendingWrites) {
+      if (pending is _ExpressionObserver) {
+        pendingObservers[pending._id] = pending;
+      } else {
+        for (var observer in pending) {
+          pendingObservers[observer._id] = observer;
+        }
+      }
+    }
+
+    if (iterations++ == circularNotificationLimit) {
+      _diagnoseCircularLimit(pendingObservers);
+    }
+
+    // TODO(jmesserly): we are avoiding SplayTreeMap.values because it performs
+    // an unnecessary copy. If that gets fixed we can use .values here.

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

should we file a bug?

[Jennifer Messerly, 2013/02/13 05:43:15]

Done.

+    pendingObservers.forEach((id, obs) { obs._deliver(); });
+  }
+}
+
+/**
+ * Attempt to provide diagnostics about what change is causing a loop in
+ * observers. Unfortunately it is hard to help the programmer unless they have
+ * provided a `debugName` to [observe], as callbacks are hard to debug
+ * because of <http://dartbug.com/8419>. However we can print the records that
+ * changed which has proved helpful.
+ */
+void _diagnoseCircularLimit(Map<int, _ExpressionObserver> pendingObservers) {

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

would it also be possible to detect circularity during notifyRead (possible
future TODO)?

I think we briefly chatted about this last week, but basically I'm thinking
that, if the user turns on a flag, we can detect if there are any writes while
doing the read-barriers. If we detect that, we could throw an exception, which
will point the user to the violating write.

[Jennifer Messerly, 2013/02/13 05:43:15]

Interesting idea. Essentially, a runtime check for purity in observed
expressions, like this?

notifyWrite(...) {
  if (observeReads) throw PurityError('your code is impure and must be purged.
Deleting it in 5..4..3..2..1..Gone!');
  ...
}

I think it's the write barrier, though, not the read barrier where we have a
problem.

It seems doable--I'll add a TODO. I think we saw at least one example where it
was a problem.

However circular references are usually not caused by violating purity, it's
more common that it's caused by the change notification callback. And callbacks
definitely need to be able to run imperative code.

I'm not sure how we can really detect that. If A -> B, then next batch B -> C,
then next back B -> A, is it a cycle? Maybe. Or maybe it stabilizes. Unless you
can solve the halting problem :), the only choice is to restrict the
computations people can do with observers. That's what we're doing with the
arbitrary 100 limit.

Spreadsheets have an advantage here -- they can statically determine there is a
cycle between cells. No such luck for us.

[Siggi Cherem (dart-lang), 2013/02/13 19:28:54]

Yeah - basically I think of it as a combination of the two: a write barrier
while our read barriers are on (when we are observing reads). I'd then suggest
that it's ok to have impure expressions, as long as the writes are not affecting
the same expressions that you are reading. (You might want some side-effects for
logging and other purposes).
Good point, that's more likely the case...

[Jennifer Messerly, 2013/02/13 20:21:20]

Yeah, I think the challenge is the cycles don't necessarily happen in one
iteration. It can be A -> B -> C -> D. So you'd have to run it some number of
iterations before you knew what happened.

FWIW, with detailed change records, I think you wouldn't need to use read
barriers, your observable expressions track the list of Observable objects and
which fields/indexes they depend on. We might be able to use that info for more
debugging.

+  var trace = new StringBuffer('exceeded notifiction limit of '
+      '${circularNotificationLimit}, possible '
+      'circular reference in observers: ');
+
+  int i = 0;
+  pendingObservers.forEach((id, obs) {
+    if (i < 10) {
+      if (i != 0) trace.add(', ');
+      var change = obs._deliver();
+      trace.add('$obs ${change != null ? change : "no change"}');
+    } else {
+      obs._deliver();
+    }
+
+    i++;

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

consider only incrementing and printing the top-10 observers that actually
changed? 

[Jennifer Messerly, 2013/02/13 05:43:15]

Great idea. Done.

+  });
+
+  // Throw away pending changes to prevent repeating this error.
+  _pendingWrites = null;
+
+  // TODO(jmesserly): should we print or log this instead?
+  // We throw an error because it probably means a bug in the program structure.

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

In watchers it was nice that we kept going - a bug in one part of the app will
not make the entire app stop.

Alternatively, report it to the onObserverUnhandledError?

[Jennifer Messerly, 2013/02/13 05:43:15]

Not sure you really want the application to keep going, though. After you throw
away the pending writes you're in an inconsistent state. If you do want your app
to keep going, it seems like turning off the limit by default might be the way
to go.

This all gets to what is the right policy for Dart to deal with unhandled errors
in events. In JS it handles them somewhat gracefully, whereas in Dartium it's
catastrophic. But that seems like more of a Dartium problem.

onObserverUnhandledError feels wrong here, but I implemented a related idea --
another callback for the diagnostic. Does it look better this way?

+  throw new CircularChangeNotifyError(trace.toString());
+}
+
+
+/**
+ * Error thrown when change notifications get stuck in a circular loop, which
+ * can happen if one [ChangeObserver] causes another change to happen, and that
+ * change causes another, etc.
+ *
+ * This is thrown when [circularNotificationLimit] is reached by
+ * [deliverChangesSync]. Circular references are commonly the result of not
+ * correctly implementing equality for objects.
+ */
+class CircularChangeNotifyError implements Error {
+  final String message;
+  CircularChangeNotifyError(this.message);
+  String toString() => message;
+}
+
+
+class _ExpressionObserver {
+  static int _nextId = 0;
+
+  /**
+   * The ID indicating creation order. We will call observers in ID order.
+   * See the TODO in [deliverChangesSync].
+   */
+  final int _id = ++_ExpressionObserver._nextId;
+
+  // Note: fields in this class are private because instances of this class are
+  // exposed via notifyRead.
+  ObservableExpression _expression;
+
+  ChangeObserver _callback;
+
+  // TODO(jmesserly): should we provide the old value? This will keep it
+  // alive until we have a new value. Watchers needed to keep it alive anyway,
+  // but we don't need it in observers, except to pass it to the ChangeObserver.

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

In that case, wouldn't an event get trigger as soon as you nullify the
expression? in which case the reference will be gone very soon afterwards (on
the next event cycle?)

[Jennifer Messerly, 2013/02/13 05:43:15]

Good point. Removed comment!

+  Object _value;
+
+  bool _wasRead;
+
+  String _debugName;
+
+  _ExpressionObserver(this._expression, this._callback, this._debugName);
+
+  /** True if this observer has been unobserved. */
+  // Note: any time we call out to user-provided code, they might call
+  // unobserve, so we need to guard against that.
+  bool get _dead => _callback == null;
+
+  String toString() =>
+      _debugName != null ? '<observer $_id: $_debugName>' : '<observer $_id>';
+
+  bool _observe() {
+    // If an observe call starts another observation, we need to make sure that
+    // the outer observe is tracked correctly.
+    var parent = _activeObserver;
+    _activeObserver = this;
+
+    _wasRead = false;
+    try {
+      _value = _expression();
+    } catch (e, trace) {
+      onObserveUnhandledError(e, trace, _expression);
+      _value = null;
+    }
+
+    // TODO(jmesserly): should the parent also observe us?
+    assert(_activeObserver == this);
+    _activeObserver = parent;
+
+    return _wasRead;
+  }
+
+  void _unobserve() {
+    if (_dead) return;
+
+    // Note: we don't remove ourselves from objects that we are observing.
+    // That will happen automatically when those fields are written.
+    // Instead, we release our own memory and wait for notifyWrite and
+    // deliverChangesSync to do the rest.
+    // TODO(jmesserly): this is probably too over-optimized. We'll need to
+    // revisit this to provide detailed change records.
+    _expression = null;
+    _callback = null;
+    _value = null;
+    _wasRead = null;
+    _debugName = null;
+  }
+
+  /**
+   * _deliver does two things:
+   * 1. Evaluate the expression to compute the new value.
+   * 2. Invoke observer for this expression.
+   *
+   * Note: if you mutate a shared value from one observer, future
+   * observers will see the updated value. Essentially, we collapse
+   * the two change notifications into one.
+   *
+   * We could split _deliver into two methods, one to compute the new value
+   * and another to call observers. But the current order has benefits too: it
+   * preserves the invariant that ChangeNotification.newValue equals the current
+   * value of the expression.
+   */
+  ChangeNotification _deliver() {
+    if (_dead) return null;
+
+    // Call the expression again to compute the new value, and to get the new
+    // list of dependencies.
+    var oldValue = _value;
+    _observe();
+
+    if (_dead) return null;

[Siggi Cherem (dart-lang), 2013/02/13 01:43:24]

can _dead change in _observe?, can _dead change in ==? I guess it could if the
user has side-effects in their expression or operator==... is that the purpose
for these extra checks? and the try-catch block in line 411?

[Jennifer Messerly, 2013/02/13 05:43:15]

added comment:

    // Note: whenever we run code we don't control, we need to check _dead again
    // in case they have unobserved this object. This means `_observe`, `==`,
    // need to check.

(This is another optimization I'll need to remove to make detailed change
records work).

+
+    bool equal;
+    try {
+      equal = oldValue == _value;
+    } catch (e, trace) {
+      onObserveUnhandledError(e, trace, null);
+      return;
+    }
+
+    if (equal || _dead) return null;
+
+    var change = new ChangeNotification(oldValue, _value);
+    try {
+      _callback(change);
+    } catch (e, trace) {
+      onObserveUnhandledError(e, trace, _callback);
+    }
+    return change;
+  }
+
+  // TODO(jmesserly): workaround for terrible VM hash code performance.
+  int get hashCode => _id;
+}
+
+
+/**
+ * Callback to intercept unhandled errors in evaluating an observable.
+ * Includes the error, stack trace, and the callback that caused the error.
+ * By default it will use [defaultObserveUnhandledError], which prints the
+ * error.
+ */
+ObserverErrorHandler onObserveUnhandledError = defaultObserveUnhandledError;
+
+/** The default handler for [onObserveUnhandledError]. Prints the error. */
+void defaultObserveUnhandledError(error, trace, callback) {
+  // TODO(jmesserly): using Logger seems better, but by default it doesn't do
+  // anything, which leads to unobserved errors.
+  // Ideally we could make this show up as an error in the browser's console.
+  print('web_ui.observe: unhandled error in callback $callback.\n'
+      'error:\n$error\n\nstack trace:\n$trace');
+}