Roll Observatory packages and add a roll script

packages/analyzer/lib/src/context/cache.dart

 // Copyright (c) 2015, 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 analyzer.src.context.cache;
 
 import 'dart:async';
 import 'dart:collection';
 
 import 'package:analyzer/src/generated/engine.dart'
     show AnalysisEngine, CacheState, InternalAnalysisContext, RetentionPriority;
 import 'package:analyzer/src/generated/java_engine.dart';
 import 'package:analyzer/src/generated/source.dart';
 import 'package:analyzer/src/generated/utilities_collection.dart';
-import 'package:analyzer/src/generated/utilities_general.dart';
 import 'package:analyzer/src/task/model.dart';
 import 'package:analyzer/task/model.dart';
 
 /**
  * Return `true` if the given [target] is a priority one.
  */
 typedef bool IsPriorityAnalysisTarget(AnalysisTarget target);
 
 /**
  * An LRU cache of results produced by 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;
 
   /**
    * An array containing the partitions of which this cache is comprised.
    */
   final List<CachePartition> _partitions;
 
   /**
    * The [StreamController] reporting [InvalidatedResult]s.
    */
-  final StreamController<InvalidatedResult> _onResultInvalidated =
-      new StreamController<InvalidatedResult>.broadcast(sync: true);
+  final ReentrantSynchronousStream<InvalidatedResult> onResultInvalidated =
+      new ReentrantSynchronousStream<InvalidatedResult>();
 
   /**
    * Initialize a newly created cache to have the given [partitions]. The
    * partitions will be searched in the order in which they appear in the array,
    * so the most specific partition (usually an [SdkCachePartition]) should be
    * first and the most general (usually a [UniversalCachePartition]) last.
    */
   AnalysisCache(this._partitions) {
     for (CachePartition partition in _partitions) {
       partition.onResultInvalidated.listen((InvalidatedResult event) {
-        _onResultInvalidated.add(event);
+        onResultInvalidated.add(event);
       });
     }
   }
 
-  /**
-   * Return the stream that is notified when a value is invalidated.
-   */
-  Stream<InvalidatedResult> get onResultInvalidated =>
-      _onResultInvalidated.stream;
-
   // TODO(brianwilkerson) Implement or delete this.
 //  /**
 //   * Return information about each of the partitions in this cache.
 //   */
 //  List<AnalysisContextStatistics_PartitionData> get partitionData {
 //    int count = _partitions.length;
 //    List<AnalysisContextStatistics_PartitionData> data =
 //        new List<AnalysisContextStatistics_PartitionData>(count);
 //    for (int i = 0; i < count; i++) {
 //      CachePartition partition = _partitions[i];
@@ skipping 91 matching lines @@
   Object getValue(AnalysisTarget target, ResultDescriptor result) {
     CacheEntry entry = get(target);
     if (entry == null) {
       return result.defaultValue;
     }
     return entry.getValue(result);
   }
 
   /**
    * Return an iterator returning all of the map entries mapping targets to
-   * cache entries.
+   * cache entries. If the [context] is not `null`, then only entries that are
+   * owned by the given context will be returned.
    */
-  MapIterator<AnalysisTarget, CacheEntry> iterator() {
-    int count = _partitions.length;
+  MapIterator<AnalysisTarget, CacheEntry> iterator(
+      {InternalAnalysisContext context: null}) {
     List<Map<AnalysisTarget, CacheEntry>> maps =
-        new List<Map<AnalysisTarget, CacheEntry>>(count);
-    for (int i = 0; i < count; i++) {
-      maps[i] = _partitions[i].map;
+        <Map<AnalysisTarget, CacheEntry>>[];
+    for (CachePartition partition in _partitions) {
+      if (context == null || partition.context == context) {
+        maps.add(partition.map);
+      }
     }
     return new MultipleMapIterator<AnalysisTarget, CacheEntry>(maps);
   }
 
   /**
    * Puts the given [entry] into the cache.
    */
   void put(CacheEntry entry) {
     AnalysisTarget target = entry.target;
     entry.fixExceptionState();
@@ skipping 15 matching lines @@
         partition.put(entry);
         return;
       }
     }
     // TODO(brianwilkerson) Handle the case where no partition was found,
     // possibly by throwing an exception.
   }
 
   /**
    * Remove all information related to the given [target] from this cache.
+   * Return the entry associated with the target, or `null` if there was cache
+   * entry for the target.
    */
-  void remove(AnalysisTarget target) {
+  CacheEntry remove(AnalysisTarget target) {
     int count = _partitions.length;
     for (int i = 0; i < count; i++) {
       CachePartition partition = _partitions[i];
       if (partition.isResponsibleFor(target)) {
         if (_TRACE_CHANGES) {
           AnalysisEngine.instance.logger
               .logInformation('Removed the cache entry for $target.');
         }
-        partition.remove(target);
-        return;
+        return partition.remove(target);
       }
     }
+    return null;
   }
 
   /**
    * Return the number of targets that are mapped to cache entries.
    */
   int size() {
     int size = 0;
     int count = _partitions.length;
     for (int i = 0; i < count; i++) {
       size += _partitions[i].size();
     }
     return size;
   }
 }
 
 /**
  * The information cached by an analysis context about an individual target.
  */
 class CacheEntry {
   /**
    * The index of the flag indicating whether the source was explicitly added to
    * the context or whether the source was implicitly added because it was
    * referenced by another source.
    */
   static int _EXPLICITLY_ADDED_FLAG = 0;
 
   /**
+   * The next invalidation process identifier.
+   */
+  static int nextInvalidateId = 0;
+
+  /**
    * The target this entry is about.
    */
   final AnalysisTarget target;
 
   /**
    * The partition that is responsible for this entry.
    */
   CachePartition _partition;
 
   /**
@@ skipping 168 matching lines @@
     if (state == CacheState.ERROR) {
       throw new ArgumentError('use setErrorState() to set the state to ERROR');
     }
     if (state == CacheState.VALID) {
       throw new ArgumentError('use setValue() to set the state to VALID');
     }
     _validateStateChange(descriptor, state);
     if (state == CacheState.INVALID) {
       ResultData data = _resultMap[descriptor];
       if (data != null) {
-        _invalidate(descriptor, delta);
+        _invalidate(nextInvalidateId++, descriptor, delta, 0);
       }
     } else {
       ResultData data = getResultData(descriptor);
       data.state = state;
       if (state != CacheState.IN_PROCESS) {
         //
         // If the state is in-process, we can leave the current value in the
         // cache for any 'get' methods to access.
         //
         data.value = descriptor.defaultValue;
       }
     }
   }
 
   /**
    * Set the value of the result represented by the given [descriptor] to the
    * given [value].
    */
-  /*<V>*/ void setValue(ResultDescriptor /*<V>*/ descriptor, dynamic /*V*/
-      value, List<TargetedResult> dependedOn) {
+  /*<V>*/ void setValue(
+      ResultDescriptor /*<V>*/ descriptor,
+      dynamic /*V*/
+      value,
+      List<TargetedResult> dependedOn) {
 //    {
 //      String valueStr = '$value';
 //      if (valueStr.length > 20) {
 //        valueStr = valueStr.substring(0, 20) + '...';
 //      }
 //      valueStr = valueStr.replaceAll('\n', '\\n');
 //      print(
 //          'setValue $descriptor for $target value=$valueStr deps=$dependedOn');
 //    }
     _validateStateChange(descriptor, CacheState.VALID);
     TargetedResult thisResult = new TargetedResult(target, descriptor);
     if (_partition != null) {
       _partition.resultStored(thisResult, value);
     }
     ResultData data = getResultData(descriptor);
     _setDependedOnResults(data, thisResult, dependedOn);
     data.state = CacheState.VALID;
     data.value = value == null ? descriptor.defaultValue : value;
   }
 
   /**
    * Set the value of the result represented by the given [descriptor] to the
    * given [value], keep its dependency, invalidate all the dependent result.
    */
-  void setValueIncremental(ResultDescriptor descriptor, dynamic value) {
+  void setValueIncremental(
+      ResultDescriptor descriptor, dynamic value, bool invalidateDependent) {
     ResultData data = getResultData(descriptor);
-    List<TargetedResult> dependedOn = data.dependedOnResults;
-    _invalidate(descriptor, null);
-    setValue(descriptor, value, dependedOn);
+    data.state = CacheState.VALID;
+    data.value = value;
+    if (invalidateDependent) {
+      _invalidateDependentResults(nextInvalidateId++, data, null, 0);
+    }
   }
 
   @override
   String toString() {
     StringBuffer buffer = new StringBuffer();
     _writeOn(buffer);
     return buffer.toString();
   }
 
   /**
    * Return the value of the flag with the given [index].
    */
   bool _getFlag(int index) => BooleanArray.get(_flags, index);
 
   /**
    * Invalidate the result represented by the given [descriptor] and propagate
    * invalidation to other results that depend on it.
    */
-  void _invalidate(ResultDescriptor descriptor, Delta delta) {
+  void _invalidate(
+      int id, ResultDescriptor descriptor, Delta delta, int level) {
+    ResultData thisData = _resultMap[descriptor];
+    if (thisData == null) {
+      return;
+    }
+    // Stop if already validated.
+    if (delta != null) {
+      if (thisData.invalidateId == id) {
+        return;
+      }
+      thisData.invalidateId = id;
+    }
+    // Ask the delta to validate.
     DeltaResult deltaResult = null;
     if (delta != null) {
       deltaResult = delta.validate(_partition.context, target, descriptor);
       if (deltaResult == DeltaResult.STOP) {
-//        print('not-invalidate $descriptor for $target');
         return;
       }
     }
-//    print('invalidate $descriptor for $target');
-    ResultData thisData;
-    if (deltaResult == null || deltaResult == DeltaResult.INVALIDATE) {
-      thisData = _resultMap.remove(descriptor);
+    if (deltaResult == DeltaResult.INVALIDATE_NO_DELTA) {
+      delta = null;
     }
-    if (deltaResult == DeltaResult.KEEP_CONTINUE) {
-      thisData = _resultMap[descriptor];
-    }
-    if (thisData == null) {
-      return;
+    if (deltaResult == null ||
+        deltaResult == DeltaResult.INVALIDATE ||
+        deltaResult == DeltaResult.INVALIDATE_NO_DELTA) {
+      _resultMap.remove(descriptor);
+//      {
+//        String indent = '  ' * level;
+//        print('[$id]$indent invalidate $descriptor for $target');
+//      }
     }
     // Stop depending on other results.
     TargetedResult thisResult = new TargetedResult(target, descriptor);
     for (TargetedResult dependedOnResult in thisData.dependedOnResults) {
       ResultData data = _partition._getDataFor(dependedOnResult);
-      if (data != null) {
+      if (data != null && deltaResult != DeltaResult.KEEP_CONTINUE) {
         data.dependentResults.remove(thisResult);
       }
     }
     // Invalidate results that depend on this result.
-    List<TargetedResult> dependentResults = thisData.dependentResults.toList();
-    for (TargetedResult dependentResult in dependentResults) {
-      CacheEntry entry = _partition.get(dependentResult.target);
-      if (entry != null) {
-        entry._invalidate(dependentResult.result, delta);
-      }
-    }
+    _invalidateDependentResults(id, thisData, delta, level + 1);
     // If empty, remove the entry altogether.
     if (_resultMap.isEmpty) {
       _partition._targetMap.remove(target);
       _partition._removeIfSource(target);
     }
     // Notify controller.
-    _partition._onResultInvalidated
-        .add(new InvalidatedResult(this, descriptor));
+    _partition.onResultInvalidated
+        .add(new InvalidatedResult(this, descriptor, thisData.value));
   }
 
   /**
    * Invalidates all the results of this entry, with propagation.
    */
   void _invalidateAll() {
     List<ResultDescriptor> results = _resultMap.keys.toList();
     for (ResultDescriptor result in results) {
-      _invalidate(result, null);
+      _invalidate(nextInvalidateId++, result, null, 0);
     }
   }
 
+  /**
+   * Invalidate results that depend on [thisData].
+   */
+  void _invalidateDependentResults(
+      int id, ResultData thisData, Delta delta, int level) {
+    List<TargetedResult> dependentResults = thisData.dependentResults.toList();
+    for (TargetedResult dependentResult in dependentResults) {
+      CacheEntry entry = _partition.get(dependentResult.target);
+      if (entry != null) {
+        entry._invalidate(id, dependentResult.result, delta, level);
+      }
+    }
+  }
+
   /**
    * Set the [dependedOn] on which this result depends.
    */
   void _setDependedOnResults(ResultData thisData, TargetedResult thisResult,
       List<TargetedResult> dependedOn) {
     thisData.dependedOnResults.forEach((TargetedResult dependedOnResult) {
       ResultData data = _partition._getDataFor(dependedOnResult);
       if (data != null) {
         data.dependentResults.remove(thisResult);
       }
@@ skipping 214 matching lines @@
 
   /**
    * A table mapping caching policies to the cache flush managers.
    */
   final HashMap<ResultCachingPolicy, CacheFlushManager> _flushManagerMap =
       new HashMap<ResultCachingPolicy, CacheFlushManager>();
 
   /**
    * The [StreamController] reporting [InvalidatedResult]s.
    */
-  final StreamController<InvalidatedResult> _onResultInvalidated =
-      new StreamController<InvalidatedResult>.broadcast(sync: true);
+  final ReentrantSynchronousStream<InvalidatedResult> onResultInvalidated =
+      new ReentrantSynchronousStream<InvalidatedResult>();
 
   /**
    * A table mapping the targets belonging to this partition to the information
    * known about those targets.
    */
   HashMap<AnalysisTarget, CacheEntry> _targetMap =
       new HashMap<AnalysisTarget, CacheEntry>();
 
   /**
    * A set of the [Source] targets.
@@ skipping 14 matching lines @@
   /**
    * Return a table mapping the targets known to the context to the information
    * known about the target.
    *
    * <b>Note:</b> This method is only visible for use by [AnalysisCache] and
    * should not be used for any other purpose.
    */
   Map<AnalysisTarget, CacheEntry> get map => _targetMap;
 
   /**
-   * Return the stream that is notified when a value is invalidated.
-   */
-  Stream<InvalidatedResult> get onResultInvalidated =>
-      _onResultInvalidated.stream;
-
-  /**
    * Notifies the partition that the client is going to stop using it.
    */
   void dispose() {
     for (CacheEntry entry in _targetMap.values) {
       entry.dispose();
     }
     _targetMap.clear();
   }
 
   /**
@@ skipping 31 matching lines @@
       throw new StateError(
           'The entry for $target is already in ${entry._partition}');
     }
     entry._partition = this;
     entry.fixExceptionState();
     _targetMap[target] = entry;
     _addIfSource(target);
   }
 
   /**
-   * Remove all information related to the given [target] from this cache.
+   * Remove all information related to the given [target] from this partition.
+   * Return the entry associated with the target, or `null` if there was cache
+   * entry for the target.
    */
-  void remove(AnalysisTarget target) {
+  CacheEntry remove(AnalysisTarget target) {
     for (CacheFlushManager flushManager in _flushManagerMap.values) {
       flushManager.targetRemoved(target);
     }
     CacheEntry entry = _targetMap.remove(target);
     if (entry != null) {
       entry._invalidateAll();
     }
     _removeIfSource(target);
+    return entry;
   }
 
   /**
    * Records that a value of the result described by the given [descriptor]
    * for the given [target] was just read from the cache.
    */
   void resultAccessed(AnalysisTarget target, ResultDescriptor descriptor) {
     CacheFlushManager flushManager = _getFlushManager(descriptor);
     TargetedResult result = new TargetedResult(target, descriptor);
     flushManager.resultAccessed(result);
@@ skipping 21 matching lines @@
    * Return the number of targets that are mapped to cache entries.
    */
   int size() => _targetMap.length;
 
   /**
    * If the given [target] is a [Source], adds it to [_sources].
    */
   void _addIfSource(AnalysisTarget target) {
     if (target is Source) {
       _sources.add(target);
-      {
-        String fullName = target.fullName;
-        _pathToSources.putIfAbsent(fullName, () => <Source>[]).add(target);
-      }
+      String fullName = target.fullName;
+      _pathToSources.putIfAbsent(fullName, () => <Source>[]).add(target);
     }
   }
 
   ResultData _getDataFor(TargetedResult result) {
     CacheEntry entry = context.analysisCache.get(result.target);
     return entry != null ? entry._resultMap[result.result] : null;
   }
 
   /**
    * Return the [CacheFlushManager] for the given [descriptor], not `null`.
    */
   CacheFlushManager _getFlushManager(ResultDescriptor descriptor) {
     ResultCachingPolicy policy = descriptor.cachingPolicy;
     if (identical(policy, DEFAULT_CACHING_POLICY)) {
       return UnlimitedCacheFlushManager.INSTANCE;
     }
     CacheFlushManager manager = _flushManagerMap[policy];
     if (manager == null) {
       manager = new CacheFlushManager(policy, _isPriorityAnalysisTarget);
       _flushManagerMap[policy] = manager;
     }
     return manager;
   }
 
   bool _isPriorityAnalysisTarget(AnalysisTarget target) {
     return context.priorityTargets.contains(target);
   }
 
   /**
-   * If the given [target] is a [Source], removes it from [_sources].
+   * If the given [target] is a [Source], remove it from the list of [_sources].
    */
   void _removeIfSource(AnalysisTarget target) {
     if (target is Source) {
       _sources.remove(target);
-      {
-        String fullName = target.fullName;
-        List<Source> sources = _pathToSources[fullName];
-        if (sources != null) {
-          sources.remove(target);
-          if (sources.isEmpty) {
-            _pathToSources.remove(fullName);
-          }
+      String fullName = target.fullName;
+      List<Source> sources = _pathToSources[fullName];
+      if (sources != null) {
+        sources.remove(target);
+        if (sources.isEmpty) {
+          _pathToSources.remove(fullName);
         }
       }
     }
   }
 }
 
 /**
  * The description for a change.
  */
 class Delta {
   final Source source;
 
   Delta(this.source);
 
   /**
    * Check whether this delta affects the result described by the given
    * [descriptor] and [target].
    */
   DeltaResult validate(InternalAnalysisContext context, AnalysisTarget target,
       ResultDescriptor descriptor) {
     return DeltaResult.INVALIDATE;
   }
 }
 
 /**
  * The possible results of validating analysis results againt a [Delta].
  */
-enum DeltaResult { INVALIDATE, KEEP_CONTINUE, STOP }
+enum DeltaResult {
+  /**
+   * Invalidate this result and continue visiting dependent results
+   * with this [Delta].
+   */
+  INVALIDATE,
+
+  /**
+   * Invalidate this result and stop using this [Delta], so unconditionally
+   * invalidate all the dependent results.
+   */
+  INVALIDATE_NO_DELTA,
+
+  /**
+   * Keep this result and continue validating dependent results
+   * with this [Delta].
+   */
+  KEEP_CONTINUE,
+
+  /**
+   * Keep this result and stop visiting results that depend on this one.
+   */
+  STOP
+}
 
 /**
  * [InvalidatedResult] describes an invalidated result.
  */
 class InvalidatedResult {
   /**
    * The target in which the result was invalidated.
    */
   final CacheEntry entry;
 
   /**
    * The descriptor of the result which was invalidated.
    */
   final ResultDescriptor descriptor;
 
-  InvalidatedResult(this.entry, this.descriptor);
+  /**
+   * The value of the result which was invalidated.
+   */
+  final Object value;
+
+  InvalidatedResult(this.entry, this.descriptor, this.value);
 
   @override
   String toString() => '$descriptor of ${entry.target}';
 }
 
 /**
+ * A Stream-like interface, which broadcasts events synchronously.
+ * If a second event is fired while delivering a first event, then the second
+ * event will be delivered first, and then delivering of the first will be
+ * continued.
+ */
+class ReentrantSynchronousStream<T> {
+  final List<Function> listeners = <Function>[];
+
+  /**
+   * Send the given [event] to the stream.
+   */
+  void add(T event) {
+    List<Function> listeners = this.listeners.toList();
+    for (Function listener in listeners) {
+      listener(event);
+    }
+  }
+
+  /**
+   * Listen for the events in this stream.
+   * Note that if the [listener] fires a new event, then the [listener] will be
+   * invoked again before returning from the [add] invocation.
+   */
+  void listen(void listener(T event)) {
+    listeners.add(listener);
+  }
+}
+
+/**
  * The data about a single analysis result that is stored in a [CacheEntry].
  */
 // TODO(brianwilkerson) Consider making this a generic class so that the value
 // can be typed.
 class ResultData {
   /**
    * The [ResultDescriptor] this result is for.
    */
   final ResultDescriptor descriptor;
 
   /**
    * The state of the cached value.
    */
   CacheState state;
 
   /**
    * The value being cached, or the default value for the result if there is no
    * value (for example, when the [state] is [CacheState.INVALID]).
    */
   Object value;
 
   /**
+   * The identifier of the invalidation process that most recently checked
+   * this value. If it is the same as the current invalidation identifier,
+   * then there is no reason to check it (and its subtree again).
+   */
+  int invalidateId = -1;
+
+  /**
    * A list of the results on which this result depends.
    */
   List<TargetedResult> dependedOnResults = <TargetedResult>[];
 
   /**
    * A list of the results that depend on this result.
    */
   Set<TargetedResult> dependentResults = new Set<TargetedResult>();
 
   /**
@@ skipping 28 matching lines @@
   bool isResponsibleFor(AnalysisTarget target) {
     if (target is AnalysisContextTarget) {
       return true;
     }
     Source source = target.source;
     return source != null && source.isInSystemLibrary;
   }
 }
 
 /**
- * A specification of a specific result computed for a specific target.
- */
-class TargetedResult {
-  /**
-   * An empty list of results.
-   */
-  static final List<TargetedResult> EMPTY_LIST = const <TargetedResult>[];
-
-  /**
-   * The target with which the result is associated.
-   */
-  final AnalysisTarget target;
-
-  /**
-   * The result associated with the target.
-   */
-  final ResultDescriptor result;
-
-  /**
-   * Initialize a new targeted result.
-   */
-  TargetedResult(this.target, this.result);
-
-  @override
-  int get hashCode {
-    return JenkinsSmiHash.combine(target.hashCode, result.hashCode);
-  }
-
-  @override
-  bool operator ==(other) {
-    return other is TargetedResult &&
-        other.target == target &&
-        other.result == result;
-  }
-
-  @override
-  String toString() => '$result for $target';
-}
-
-/**
  * A cache partition that contains all targets not contained in other partitions.
  */
 class UniversalCachePartition extends CachePartition {
   /**
    * Initialize a newly created cache partition, belonging to the given
    * [context].
    */
   UniversalCachePartition(InternalAnalysisContext context) : super(context);
 
   @override
@@ skipping 12 matching lines @@
   void resultAccessed(TargetedResult result) {}
 
   @override
   List<TargetedResult> resultStored(TargetedResult newResult, newValue) {
     return TargetedResult.EMPTY_LIST;
   }
 
   @override
   void targetRemoved(AnalysisTarget target) {}
 }