Library Cycle invalidation

pkg/analyzer/lib/src/generated/element.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.
 
 library engine.element;
 
 import 'dart:collection';
 import 'dart:math' show min;
 
 import 'package:analyzer/src/generated/utilities_general.dart';
@@ skipping 7500 matching lines @@
     for (ImportElement importElement in imports) {
       (importElement as ImportElementImpl).enclosingElement = this;
       PrefixElementImpl prefix = importElement.prefix as PrefixElementImpl;
       if (prefix != null) {
         prefix.enclosingElement = this;
       }
     }
     this._imports = imports;
   }
 
+  /** Given an update to this library which may have added or deleted edges
+   * in the import/export graph originating from this node only, remove any
+   * cached library cycles in the element model which may have been invalidated.
+   */
+  void invalidateLibraryCycles() {
+    if (_libraryCycle == null) {
+      // We have already invalidated this node, or we have never computed
+      // library cycle information for it.  In the former case, we're done. In
+      // the latter case, this node cannot be reachable from any node for which
+      // we have computed library cycle information.  Therefore, any edges added
+      // or deleted in the update causing this invalidation can only be edges to
+      // nodes which either have no library cycle information (and hence do not
+      // need invalidation), or which do not reach this node by any path.
+      // In either case, no further invalidation is needed.
+      return;
+    }
+    // If we have pre-computed library cycle information, then we must
+    // invalidate the information both on this element, and on certain
+    // other elements.  Edges originating at this node may have been
+    // added or deleted.  A deleted edge that points outside of this cycle
+    // cannot change the cycle information for anything outside of this cycle,
+    // and so it is sufficient to delete the cached library information on this
+    // cycle.  An added edge which points to another node within the cycle
+    // induces no invalidation.  An added edge which points to a node earlier
+    // in the topological sort of cycles induces no invalidation (since there
+    // are by definition no back edges from earlier cycles in the topological
+    // order, and hence no possible cycle can have been introduced.  The only
+    // remaining case is that we have added an edge to a node which is later
+    // in the topological sort of cycles.  This can induce cycles, since it
+    // represents a new back edge.  It would be sufficient to invalidate the
+    // cycle information for all nodes that are between the target and the
+    // node in the topological order.  For simplicity, we simply invalidate
+    // all nodes which are reachable from the the source node.
+    // Note that in the invalidation phase, we do not cut off when we encounter
+    // a node with no library cycle information, since we do not know whether
+    // we are in the case where invalidation has already been performed, or we
+    // are in the case where library cycles have simply never been computed from
+    // a newly reachable node.
+    Set<LibraryElementImpl> active = new HashSet();
+    void invalidate(LibraryElementImpl library) {
+      if (!active.add(library)) return;
+      if (library._libraryCycle != null) {
+        library._libraryCycle.forEach(invalidate);
+        library._libraryCycle = null;
+      }
+      library.exportedLibraries.forEach(invalidate);
+      library.importedLibraries.forEach(invalidate);
+    }
+    invalidate(this);
+  }
+
   @override
   bool get isBrowserApplication =>
       entryPoint != null && isOrImportsBrowserLibrary;
 
   @override
   bool get isDartCore => name == "dart.core";
 
   @override
   bool get isInSdk =>
       StringUtilities.startsWith5(name, 0, 0x64, 0x61, 0x72, 0x74, 0x2E);
@@ skipping 3399 matching lines @@
 
   @override
   void visitElement(Element element) {
     int offset = element.nameOffset;
     if (offset != -1) {
       map[offset] = element;
     }
     super.visitElement(element);
   }
 }