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

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

 // Copyright (c) 2014, 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.
 
 // This code was auto-generated, is not intended to be edited, and is subject to
 // significant change. Please see the README file for more information.
 
 library engine;
 
 import "dart:math" as math;
@@ skipping 15 matching lines @@
 import 'java_engine.dart';
 import 'parser.dart' show Parser, IncrementalParser;
 import 'resolver.dart';
 import 'scanner.dart';
 import 'sdk.dart' show DartSdk;
 import 'source.dart';
 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.
  */
 class AnalysisCache {
   /**
    * A flag used to control whether trace information should be produced when the content of the
    * cache is modified.
    */
   static bool _TRACE_CHANGES = false;
 
@@ skipping 628 matching lines @@
    * Return the element model corresponding to the library defined by the given source, or
    * `null` if the element model does not currently exist or if the library cannot be analyzed
    * for some reason.
    *
    * @param source the source defining the library whose element model is to be returned
    * @return the element model corresponding to the library defined by the given source
    */
   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.
    *
    * @param source the source whose line information is to be returned
    * @return the line information for the given source
    * See [computeLineInfo].
    */
   LineInfo getLineInfo(Source source);
 
@@ skipping 31 matching lines @@
    * @param unitSource the source of the compilation unit
    * @param librarySource the source of the defining compilation unit of the library containing the
    *          compilation unit
    * @return a fully resolved AST for the compilation unit
    * See [resolveCompilationUnit].
    */
   CompilationUnit getResolvedCompilationUnit2(Source unitSource,
       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.
    *
    * @param htmlSource the source of the HTML unit
    * @return a fully resolved HTML unit
    * See [resolveHtmlUnit].
    */
   ht.HtmlUnit getResolvedHtmlUnit(Source htmlSource);
 
   /**
@@ skipping 198 matching lines @@
    * A table mapping the sources known to the context to the information known about the source.
    */
   AnalysisCache _cache;
 
   /**
    * An array containing sources for which data should not be flushed.
    */
   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.
    */
   HashSet<Source> _neededForResolution = null;
 
   /**
    * A table mapping sources to the change notices that are waiting to be returned related to that
    * source.
    */
   HashMap<Source, ChangeNoticeImpl> _pendingNotices =
@@ skipping 189 matching lines @@
     // Look for incremental analysis
     //
     if (_incrementalAnalysisCache != null &&
         _incrementalAnalysisCache.hasWork) {
       AnalysisTask task =
           new IncrementalAnalysisTask(this, _incrementalAnalysisCache);
       _incrementalAnalysisCache = null;
       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;
     for (int i = 0; i < priorityCount; i++) {
       Source source = _priorityOrder[i];
       AnalysisContextImpl_TaskData taskData =
           _getNextAnalysisTaskForSource(source, _cache.get(source), true, hintsEnabled);
       AnalysisTask task = taskData.task;
       if (task != null) {
         return task;
@@ skipping 728 matching lines @@
   @override
   LibraryElement getLibraryElement(Source source) {
     SourceEntry sourceEntry = getReadableSourceEntryOrNull(source);
     if (sourceEntry is DartEntry) {
       return sourceEntry.getValue(DartEntry.ELEMENT);
     }
     return null;
   }
 
   @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) {
       return sourceEntry.getValue(SourceEntry.LINE_INFO);
     }
     return null;
   }
 
   @override
   int getModificationStamp(Source source) {
@@ skipping 59 matching lines @@
     SourceEntry sourceEntry = getReadableSourceEntryOrNull(unitSource);
     if (sourceEntry is DartEntry) {
       return sourceEntry.getValueInLibrary(
           DartEntry.RESOLVED_UNIT,
           librarySource);
     }
     return null;
   }
 
   @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) {
       HtmlEntry htmlEntry = sourceEntry;
       return htmlEntry.getValue(HtmlEntry.RESOLVED_UNIT);
     }
     return null;
   }
 
   @override
@@ skipping 1513 matching lines @@
    *           resolved
    */
   Object _getDartVerificationData(Source unitSource, Source librarySource,
       DartEntry dartEntry, DataDescriptor descriptor) {
     dartEntry =
         _cacheDartVerificationData(unitSource, librarySource, dartEntry, descriptor);
     return dartEntry.getValueInLibrary(descriptor, librarySource);
   }
 
   /**
+   * 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.
    *
    * <b>Note:</b> This method cannot be used in an async environment.
    *
    * @param source the source representing the Dart file
    * @param descriptor the descriptor representing the data to be returned
    * @param defaultValue the value to be returned if the source is not an HTML file
    * @return the requested data about the given source
@@ skipping 2739 matching lines @@
    * Reports that the given HTML source was resolved in the given context.
    *
    * @param context the context in which the source was resolved
    * @param source the source that was resolved
    * @param unit the result of resolving the source in the given context
    */
   void resolvedHtml(AnalysisContext context, Source source, ht.HtmlUnit unit);
 }
 
 /**
+ * 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.
  */
 abstract class AnalysisOptions {
   /**
    * Return `true` if analysis is to analyze Angular.
    *
    * @return `true` if analysis is to analyze Angular
    */
   bool get analyzeAngular;
@@ skipping 3188 matching lines @@
   /**
    * Initialize a newly created descriptor to have the given [name] and
    * [defaultValue].
    */
   DataDescriptor(this._name, [this.defaultValue = null]);
 
   @override
   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
  * the computation is dependent on having the AST.
  */
 class DefaultRetentionPolicy implements CacheRetentionPolicy {
   /**
    * An instance of this class that can be shared.
    */
   static DefaultRetentionPolicy POLICY = new DefaultRetentionPolicy();
@@ skipping 15 matching lines @@
     if (sourceEntry is DartEntry) {
       DartEntry dartEntry = sourceEntry;
       if (astIsNeeded(dartEntry)) {
         return RetentionPriority.MEDIUM;
       }
     }
     return RetentionPriority.LOW;
   }
 }
 
-
 /**
  * Recursively visits [HtmlUnit] and every embedded [Expression].
  */
 abstract class ExpressionVisitor extends ht.RecursiveXmlVisitor<Object> {
   /**
    * Visits the given [Expression]s embedded into tag or attribute.
    *
    * @param expression the [Expression] to visit, not `null`
    */
   void visitExpression(Expression expression);
@@ skipping 1950 matching lines @@
     SdkCachePartition partition = _sdkPartitions[sdk];
     if (partition == null) {
       partition = new SdkCachePartition(sdkContext, _DEFAULT_SDK_CACHE_SIZE);
       _sdkPartitions[sdk] = partition;
     }
     return partition;
   }
 }
 
 /**
+ * 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 {
   /**
    * The [TimeCounter] for time spent in reading files.
    */
   static TimeCounter io = new TimeCounter();
 
   /**
    * The [TimeCounter] for time spent in scanning.
@@ skipping 2621 matching lines @@
 
   @override
   Object visitPolymerTagDartElement(PolymerTagDartElement element) {
     if (element.name == PolymerHtmlUnitBuilder_this._elementName) {
       throw new PolymerHtmlUnitBuilder_FoundTagDartElementError(
           element as PolymerTagDartElementImpl);
     }
     return null;
   }
 }