Allow completions to wait for analysis without requiring a busy wait loop.

pkg/analyzer/lib/src/generated/engine.dart

Index: pkg/analyzer/lib/src/generated/engine.dart
diff --git a/pkg/analyzer/lib/src/generated/engine.dart b/pkg/analyzer/lib/src/generated/engine.dart
index 4b27d6e9f1e75318e23b2528254191010eefe216..103af2c83b796e1588eace057ee8c6e3da5e22a8 100644
--- a/pkg/analyzer/lib/src/generated/engine.dart
+++ b/pkg/analyzer/lib/src/generated/engine.dart
@@ -33,6 +33,17 @@ import 'utilities_collection.dart';
 import 'utilities_general.dart';
 
 /**
+ * Type of callback functions used by PendingFuture.  Functions of this type
+ * should perform a computation based on the data in [sourceEntry] and return
+ * it.  If the computation can't be performed yet because more analysis is
+ * needed, null should be returned.
+ *
+ * The function may also throw an exception, in which case the corresponding
+ * future will be completed with failure.
+ */
+typedef T PendingFutureComputer<T>(SourceEntry sourceEntry);
+
+/**
  * Instances of the class `AnalysisCache` implement an LRU cache of information related to
  * analysis.
  */
@@ -681,6 +692,20 @@ abstract class AnalysisContext {
   LibraryElement getLibraryElement(Source source);
 
   /**
+   * Return a future which will be completed with the element model for the
+   * given source once that element model is up to date.
+   *
+   * If the element model for the source can't be computed for some reason, the
+   * future will be completed with an error.  One possible error is
+   * AnalysisNotScheduledError, which means that the element model can't be
+   * computed because the given source file is not scheduled to be analyzed.
+   * (This could happen, for example, because the source file is not known to
+   * the context, or because it's a part file for which there is no
+   * corresponding library).
+   */
+  Future<LibraryElement> getLibraryElementFuture(Source source);
+
+  /**
    * Return the line information for the given source, or `null` if the line information is
    * not known. The line information is used to map offsets from the beginning of the source to line
    * and column pairs.
@@ -732,6 +757,20 @@ abstract class AnalysisContext {
       Source librarySource);
 
   /**
+   * Return a future which will be completed with the fully resolved AST for a
+   * single compilation unit within the given library, once that AST is up to
+   * date.
+   *
+   * If the resolved AST can't be computed for some reason, the future will be
+   * completed with an error.  One possible error is AnalysisNotScheduledError,
+   * which means that the resolved AST can't be computed because the given
+   * source file is not scheduled to be analyzed within the context of the
+   * given library.
+   */
+  Future<CompilationUnit> getResolvedCompilationUnitFuture(Source source,

[danrubel, 2014/12/12 16:06:15]

How do I cancel waiting for this when I realize that the user has switched to
editing a different file?

[Paul Berry, 2014/12/12 17:36:38]

As discussed over VC, I'll make a follow-up CL that changes this Future into a
CancelableFuture (a new class which implements Future and provides a cancel()
method).  Assuming people like it, we may eventually want to try to get
CancelableFuture folded in to dart:async.

+      LibraryElement library);

[scheglov, 2014/12/12 03:41:56]

It would be slightly easier for clients to get library Source instead of
LibraryElement.

[Brian Wilkerson, 2014/12/12 15:13:12]

In some cases, yes, in some cases no. And it's more efficient to pass the
element when the client already has it. That's why we have both variants for the
immediate case (getResolvedCompilationUnit and getResolvedCompilationUnit2).

[scheglov, 2014/12/12 15:25:09]

It's much easier and cheaper for the client to go from LibraryElement to Source
when the other way around.
And implementation uses just Source anyway.

[Brian Wilkerson, 2014/12/12 15:31:42]

Right. I'd forgotten that.

[Paul Berry, 2014/12/12 17:36:38]

Good point.  Also, in this case, the client already had the source, and was
going through the pointless exercise of converting it to a LibraryElement just
so that it could pass it in to getResolvedCompilationUnitFuture.  I've reworked
the API to follow Konstantin's suggestion, and now the function
getLibraryElementFuture isn't needed at all.

+
+  /**
    * Return a fully resolved HTML unit, or `null` if the resolved unit is not already
    * computed.
    *
@@ -950,6 +989,21 @@ class AnalysisContextImpl implements InternalAnalysisContext {
   List<Source> _priorityOrder = Source.EMPTY_ARRAY;
 
   /**
+   * A map from all sources for which there are futures pending to a list of
+   * the corresponding PendingFuture objects.  These sources will be analyzed
+   * in the same way as priority sources, except with higher priority.
+   *
+   * TODO(paulberry): since the size of this map is not constrained (as it is
+   * for _priorityOrder), we run the risk of creating an analysis loop if
+   * re-caching one AST structure causes the AST structure for another source
+   * with pending futures to be flushed.  However, this is unlikely to happen
+   * in practice since sources are removed from this hash set as soon as their
+   * futures have completed.
+   */
+  HashMap<Source, List<PendingFuture>> _pendingFutureSources =
+      new HashMap<Source, List<PendingFuture>>();
+
+  /**
    * An array containing sources whose AST structure is needed in order to resolve the next library
    * to be resolved.
    */
@@ -1159,6 +1213,50 @@ class AnalysisContextImpl implements InternalAnalysisContext {
       return task;
     }
     //
+    // Look for a source that needs to be analyzed because it has futures
+    // pending.
+    //
+    if (_pendingFutureSources.isNotEmpty) {
+      List<Source> sourcesToRemove = <Source>[];
+      AnalysisTask task;
+      for (Source source in _pendingFutureSources.keys) {
+        SourceEntry sourceEntry = _cache.get(source);
+        List<PendingFuture> pendingFutures = _pendingFutureSources[source];
+        for (int i = 0; i < pendingFutures.length; ) {
+          if (pendingFutures[i].evaluate(sourceEntry)) {

[Brian Wilkerson, 2014/12/12 15:13:12]

Could the evaluation of the pending future ever cause a change to the list of
pendingFutures? (My limited understanding is that it could if the computation of
the value being waited for depended on some other value from the same source,
but perhaps that doesn't happen.)

Could the evaluation of the pending future ever cause a change to
_pendingFutureSources? Would that cause problems for the outer 'for' loop?
(Subtleties of Dart collections that I haven't learned yet.)

[Paul Berry, 2014/12/12 17:36:38]

You are right in general that it's not safe to modify a collection while you're
iterating through it with a 'for' loop (you'll get a ConcurrentModificationError
in most circumstances).  However, my design intent here was that the evaluate()
call should be free of side effects (except for the side effect of completing
the future), so that shouldn't be a problem.  Note that there's no danger of
reentrancy from the client code which is waiting on the future, because that
code is deferred to a microtask, so it won't be executed until after the loops
complete.

I've updated some comments to clarify that evaluate() (and the closure it
invokes) should be side effect free.

+            pendingFutures.removeAt(i);
+          } else {
+            i++;
+          }
+        }
+        if (pendingFutures.isEmpty) {
+          sourcesToRemove.add(source);
+          continue;
+        }
+        AnalysisContextImpl_TaskData taskData =
+            _getNextAnalysisTaskForSource(source, sourceEntry, true, hintsEnabled);
+        task = taskData.task;
+        if (task != null) {
+          break;
+        } else if (taskData.isBlocked) {
+          hasBlockedTask = true;
+        } else {
+          // There is no more work to do for this task, so forcibly complete
+          // all its pending futures.
+          for (PendingFuture pendingFuture in pendingFutures) {
+            pendingFuture.forciblyComplete();
+          }
+          sourcesToRemove.add(source);
+        }
+      }
+      for (Source source in sourcesToRemove) {
+        _pendingFutureSources.remove(source);

[Brian Wilkerson, 2014/12/12 15:13:12]

Could the evaluation of a pending future (on line 1226) ever cause a pending
future to be added to a source *after* the source had already been added to
sourcesToRemove?

[Paul Berry, 2014/12/12 17:36:38]

No, for the same reasons stated above.

+      }
+      if (task != null) {
+        return task;
+      }
+    }
+    //
     // Look for a priority source that needs to be analyzed.
     //
     int priorityCount = _priorityOrder.length;
@@ -1907,6 +2005,19 @@ class AnalysisContextImpl implements InternalAnalysisContext {
   }
 
   @override
+  Future<LibraryElement> getLibraryElementFuture(Source source) {
+    return _getFuture(source, (SourceEntry sourceEntry) {
+      if (sourceEntry is DartEntry) {
+        if (sourceEntry.hasErrorState()) {

[Brian Wilkerson, 2014/12/12 15:13:12]

I think that this should be checking explicitly for an error state related to
DartEntry.ELEMENT. If, for example, there were an exception while trying to
compute hints, then the element would be valid but the source entry would still
have an error state. (And if there is an exception while trying to parse the
file, then the element will also be marked as being in an error state.)

[Paul Berry, 2014/12/12 17:36:38]

Fair enough.  This code is gone now as a result of Konstantin's suggestion
above, but if it ever needs to be re-introduced I'll keep this in mind.

+          throw sourceEntry.exception;
+        }
+        return sourceEntry.getValue(DartEntry.ELEMENT);
+      }
+      throw new AnalysisNotScheduledError();
+    });
+  }
+
+  @override
   LineInfo getLineInfo(Source source) {
     SourceEntry sourceEntry = getReadableSourceEntryOrNull(source);
     if (sourceEntry != null) {
@@ -1986,6 +2097,23 @@ class AnalysisContextImpl implements InternalAnalysisContext {
   }
 
   @override
+  Future<CompilationUnit> getResolvedCompilationUnitFuture(Source unitSource,
+      LibraryElement library) {
+    Source librarySource = library.source;
+    return _getFuture(unitSource, (SourceEntry sourceEntry) {
+      if (sourceEntry is DartEntry) {
+        if (sourceEntry.hasErrorState()) {

[Brian Wilkerson, 2014/12/12 15:13:12]

Ditto

[Paul Berry, 2014/12/12 17:36:38]

Done.

+          throw sourceEntry.exception;
+        }
+        return sourceEntry.getValueInLibrary(
+            DartEntry.RESOLVED_UNIT,
+            librarySource);
+      }
+      throw new AnalysisNotScheduledError();
+    });
+  }
+
+  @override
   ht.HtmlUnit getResolvedHtmlUnit(Source htmlSource) {
     SourceEntry sourceEntry = getReadableSourceEntryOrNull(htmlSource);
     if (sourceEntry is HtmlEntry) {
@@ -3519,6 +3647,33 @@ class AnalysisContextImpl implements InternalAnalysisContext {
   }
 
   /**
+   * Return a future that will be completed with the result of calling
+   * [computeValue].  If [computeValue] returns non-null, the future will be
+   * completed immediately with the resulting value.  If it returns null, then
+   * it will be re-executed in the future, after the next time the cached
+   * information for [source] has changed.  If [computeValue] throws an
+   * exception, the future will fail with that exception.
+   *
+   * If the [computeValue] still returns null after there is no further
+   * analysis to be done for [source], then the future will be completed with
+   * the error AnalysisNotScheduledError.
+   */
+  Future /*<T>*/ _getFuture(Source source, /*T*/
+  computeValue(SourceEntry sourceEntry)) {
+    SourceEntry sourceEntry = getReadableSourceEntryOrNull(source);
+    if (sourceEntry == null) {
+      return new Future.error(new AnalysisNotScheduledError());
+    }
+    PendingFuture pendingFuture = new PendingFuture(computeValue);
+    if (!pendingFuture.evaluate(sourceEntry)) {
+      _pendingFutureSources.putIfAbsent(
+          source,
+          () => <PendingFuture>[]).add(pendingFuture);
+    }
+    return pendingFuture.future;
+  }
+
+  /**
    * Given a source for an HTML file, return the data represented by the given descriptor that is
    * associated with that source, or the given default value if the source is not an HTML file. This
    * method assumes that the data can be produced by parsing the source if it is not already cached.
@@ -6278,6 +6433,16 @@ abstract class AnalysisListener {
 }
 
 /**
+ * Futures returned by [AnalysisContext] for pending analysis results will
+ * complete with this error if it is determined that analysis results will
+ * never become available (e.g. because the requested source is not subject to
+ * analysis, or because the requested source is a part file which is not a part
+ * of any known library).
+ */
+class AnalysisNotScheduledError implements Exception {
+}
+
+/**
  * The interface `AnalysisOptions` defines the behavior of objects that provide access to a
  * set of analysis options used to control the behavior of an analysis context.
  */
@@ -9486,6 +9651,7 @@ class DataDescriptor<E> {
   String toString() => _name;
 }
 
+
 /**
  * Instances of the class `DefaultRetentionPolicy` implement a retention policy that will keep
  * AST's in the cache if there is analysis information that needs to be computed for a source, where
@@ -9521,7 +9687,6 @@ class DefaultRetentionPolicy implements CacheRetentionPolicy {
   }
 }
 
-
 /**
  * Recursively visits [HtmlUnit] and every embedded [Expression].
  */
@@ -11492,6 +11657,62 @@ class PartitionManager {
 }
 
 /**
+ * Representation of a pending computation which is based on the results of
+ * analysis that may or may not have been completed.
+ */
+class PendingFuture<T> {
+  /**
+   * The function which implements the computation.
+   */
+  final PendingFutureComputer<T> _computeValue;
+
+  /**
+   * The completer that should be completed once the computation has succeeded.
+   */
+  final Completer<T> _completer = new Completer<T>();
+
+  PendingFuture(this._computeValue);
+
+  /**
+   * Retrieve the future which will be completed when this object is
+   * successfully evaluated.
+   */
+  Future<T> get future => _completer.future;
+
+  /**
+   * Execute [_computeValue], passing it the given [sourceEntry], and complete
+   * the pending future if it's appropriate to do so.  If the pending future is
+   * completed by this call, true is returned; otherwise false is returned.
+   *
+   * Once this function has returned true, it should not be called again.
+   */
+  bool evaluate(SourceEntry sourceEntry) {
+    assert(!_completer.isCompleted);
+    try {
+      T result = _computeValue(sourceEntry);
+      if (result == null) {
+        return false;
+      } else {
+        _completer.complete(result);
+        return true;
+      }
+    } catch (exception, stackTrace) {
+      _completer.completeError(exception, stackTrace);
+      return true;
+    }
+  }
+
+  /**
+   * No further analysis updates are expected which affect this future, so
+   * complete it with an AnalysisNotScheduledError in order to avoid
+   * deadlocking the client.
+   */
+  void forciblyComplete() {
+    _completer.completeError(new AnalysisNotScheduledError());

[Brian Wilkerson, 2014/12/12 15:13:12]

Should this be

try {
  throw new AnalysisNotScheduledError();
} catch (exception, stackTrace) {
  _completer.completeError(exception, stackTrace);
}

so that we always get a stack trace for debugging purposes?

[Paul Berry, 2014/12/12 17:36:38]

Good point.  Done.

+  }
+}
+
+/**
  * Container with global [AnalysisContext] performance statistics.
  */
 class PerformanceStatistics {