Update defer loading algorithm:

pkg/compiler/lib/src/deferred_load.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 deferred_load;
 
+import 'dart:collection' show Queue;
+
 import 'common/tasks.dart' show CompilerTask;
 import 'common.dart';
 import 'compiler.dart' show Compiler;
 import 'constants/expressions.dart' show ConstantExpression;
 import 'constants/values.dart'
     show
         ConstantValue,
         ConstructedConstantValue,
         DeferredConstantValue,
         StringConstantValue;
@@ skipping 30 matching lines @@
 
 /// A "hunk" of the program that will be loaded whenever one of its [imports]
 /// are loaded.
 ///
 /// Elements that are only used in one deferred import, is in an OutputUnit with
 /// the deferred import as single element in the [imports] set.
 ///
 /// Whenever a deferred Element is shared between several deferred imports it is
 /// in an output unit with those imports in the [imports] Set.
 ///
-/// OutputUnits are equal if their [imports] are equal.
-class OutputUnit {
-  /// The deferred imports that will load this output unit when one of them is
-  /// loaded.
-  final Setlet<_DeferredImport> imports = new Setlet<_DeferredImport>();
-
+/// We never create two OutputUnits sharing the same set of [imports].
+abstract class OutputUnit {
   /// `true` if this output unit is for the main output file.
-  final bool isMainOutput;
+  bool get isMainOutput;
 
   /// A unique name representing this [OutputUnit].
-  String name;
-
-  OutputUnit({this.isMainOutput: false});
-
-  String toString() => "OutputUnit($name)";
-
-  bool operator ==(other) {
-    return other is OutputUnit &&
-        imports.length == other.imports.length &&
-        imports.containsAll(other.imports);
-  }
-
-  int get hashCode {
-    int sum = 0;
-    for (_DeferredImport import in imports) {
-      sum = (sum + import.hashCode) & 0x3FFFFFFF; // Stay in 30 bit range.
-    }
-    return sum;
-  }
+  String get name;
 }
 
 /// For each deferred import, find elements and constants to be loaded when that
 /// import is loaded. Elements that are used by several deferred imports are in
 /// shared OutputUnits.
 class DeferredLoadTask extends CompilerTask {
   /// The name of this task.
   String get name => 'Deferred Loading';
 
   /// DeferredLibrary from dart:async
   ClassElement get deferredLibraryClass =>
       compiler.resolution.commonElements.deferredLibraryClass;
 
-  /// A synthetic import representing the loading of the main program.
-  final _DeferredImport _fakeMainImport = const _DeferredImport();
-
   /// The OutputUnit that will be loaded when the program starts.
-  final OutputUnit mainOutputUnit = new OutputUnit(isMainOutput: true);
+  OutputUnit get mainOutputUnit => importSets.emptySet;
 
   /// A set containing (eventually) all output units that will result from the
   /// program.
-  final Set<OutputUnit> allOutputUnits = new Set<OutputUnit>();
+  final Set<ImportSet> allOutputUnits = new Set<ImportSet>();
 
   /// Will be `true` if the program contains deferred libraries.
   bool isProgramSplit = false;
 
   static const ImpactUseCase IMPACT_USE = const ImpactUseCase('Deferred load');
 
   /// A mapping from the name of a defer import to all the output units it
   /// depends on in a list of lists to be loaded in the order they appear.
   ///
   /// For example {"lib1": [[lib1_lib2_lib3], [lib1_lib2, lib1_lib3],
   /// [lib1]]} would mean that in order to load "lib1" first the hunk
   /// lib1_lib2_lib2 should be loaded, then the hunks lib1_lib2 and lib1_lib3
   /// can be loaded in parallel. And finally lib1 can be loaded.
   final Map<String, List<OutputUnit>> hunksToLoad =
       new Map<String, List<OutputUnit>>();
 
   /// A cache of the result of calling `computeImportDeferName` on the keys of
   /// this map.
-  final Map<_DeferredImport, String> importDeferName =
-      <_DeferredImport, String>{};
+  final Map<ImportElement, String> _importDeferName = <ImportElement, String>{};
 
   /// A mapping from elements and constants to their output unit. Query this via
   /// [outputUnitForElement]
-  final Map<Element, OutputUnit> _elementToOutputUnit =
-      new Map<Element, OutputUnit>();
+  final Map<Entity, ImportSet> _elementToOutputUnit =
+      new Map<Entity, ImportSet>();
 
   /// A mapping from constants to their output unit. Query this via
   /// [outputUnitForConstant]
-  final Map<ConstantValue, OutputUnit> _constantToOutputUnit =
-      new Map<ConstantValue, OutputUnit>();
-
-  /// All the imports with a [DeferredLibrary] annotation, mapped to the
-  /// [LibraryElement] they import.
-  /// The main library is included in this set for convenience.
-  final Map<_DeferredImport, LibraryElement> _allDeferredImports =
-      new Map<_DeferredImport, LibraryElement>();
+  final Map<ConstantValue, ImportSet> _constantToOutputUnit =
+      new Map<ConstantValue, ImportSet>();
 
   /// Because the token-stream is forgotten later in the program, we cache a
   /// description of each deferred import.
-  final Map<_DeferredImport, ImportDescription> _deferredImportDescriptions =
-      <_DeferredImport, ImportDescription>{};
+  final Map<ImportElement, ImportDescription> _deferredImportDescriptions =
+      <ImportElement, ImportDescription>{};
 
-  // For each deferred import we want to know exactly what elements have to
-  // be loaded.
-  Map<_DeferredImport, Set<Element>> _importedDeferredBy = null;
-  Map<_DeferredImport, Set<ConstantValue>> _constantsDeferredBy = null;
-
-  Set<Element> _mainElements = new Set<Element>();
+  /// A lattice to compactly represent multiple subsets of imports.
+  final ImportSetLattice importSets = new ImportSetLattice();
 
   final Compiler compiler;
   DeferredLoadTask(Compiler compiler)
       : compiler = compiler,
         super(compiler.measurer) {
-    mainOutputUnit.imports.add(_fakeMainImport);
+    allOutputUnits.add(mainOutputUnit);
   }
 
   JavaScriptBackend get backend => compiler.backend;
   DiagnosticReporter get reporter => compiler.reporter;
 
   /// Returns the [OutputUnit] where [element] belongs.
   OutputUnit outputUnitForElement(Entity entity) {
     // TODO(johnniwinther): Support use of entities by splitting maps by
     // entity kind.
     if (!isProgramSplit) return mainOutputUnit;
     Element element = entity;
     element = element.implementation;
     while (!_elementToOutputUnit.containsKey(element)) {
       // TODO(21051): workaround: it looks like we output annotation constants
       // for classes that we don't include in the output. This seems to happen
       // when we have reflection but can see that some classes are not needed.
       // We still add the annotation but don't run through it below (where we
       // assign every element to its output unit).
       if (element.enclosingElement == null) {
         _elementToOutputUnit[element] = mainOutputUnit;
         break;
       }
       element = element.enclosingElement.implementation;
     }
     return _elementToOutputUnit[element];
   }
 
   /// Returns the [OutputUnit] where [element] belongs.
-  OutputUnit outputUnitForClass(ClassEntity element) {
+  OutputUnit outputUnitForClass(ClassElement element) {
     return outputUnitForElement(element);
   }
 
   /// Returns the [OutputUnit] where [element] belongs.
   OutputUnit outputUnitForMember(MemberEntity element) {
     return outputUnitForElement(element);
   }
 
   /// Direct access to the output-unit to element relation used for testing.
-  OutputUnit getOutputUnitForElementForTesting(Element element) {
+  OutputUnit getOutputUnitForElementForTesting(Entity element) {
     return _elementToOutputUnit[element];
   }
 
   /// Returns the [OutputUnit] where [constant] belongs.
   OutputUnit outputUnitForConstant(ConstantValue constant) {
     if (!isProgramSplit) return mainOutputUnit;
     return _constantToOutputUnit[constant];
   }
 
   /// Direct access to the output-unit to constants map used for testing.
   Map<ConstantValue, OutputUnit> get outputUnitForConstantsForTesting {
     return _constantToOutputUnit;
   }
 
   bool isDeferred(Entity element) {
     return outputUnitForElement(element) != mainOutputUnit;
   }
 
   bool isDeferredClass(ClassEntity element) {
     return outputUnitForElement(element) != mainOutputUnit;
   }
 
   /// Returns the unique name for the deferred import of [prefix].
   String getImportDeferName(Spannable node, PrefixElement prefix) {
-    String name =
-        importDeferName[new _DeclaredDeferredImport(prefix.deferredImport)];
+    String name = _importDeferName[prefix.deferredImport];
     if (name == null) {
       reporter.internalError(node, "No deferred name for $prefix.");
     }
     return name;
   }
 
+  /// Returns the names associated with each deferred import in [unit].
+  Iterable<String> getImportNames(OutputUnit unit) {
+    ImportSet importSet = unit;
+    return importSet._imports.map((i) => _importDeferName[i]);
+  }
+
   /// Returns `true` if element [to] is reachable from element [from] without
   /// crossing a deferred import.
   ///
   /// For example, if we have two deferred libraries `A` and `B` that both
   /// import a library `C`, then even though elements from `A` and `C` end up in
   /// different output units, there is a non-deferred path between `A` and `C`.
-  bool hasOnlyNonDeferredImportPaths(Element from, Element to) {
-    OutputUnit outputUnitFrom = outputUnitForElement(from);
-    OutputUnit outputUnitTo = outputUnitForElement(to);
-    return outputUnitTo.imports.containsAll(outputUnitFrom.imports);
-  }
-
-  // TODO(het): use a union-find to canonicalize output units
-  OutputUnit _getCanonicalUnit(OutputUnit outputUnit) {
-    OutputUnit representative = allOutputUnits.lookup(outputUnit);
-    if (representative == null) {
-      representative = outputUnit;
-      allOutputUnits.add(representative);
-    }
-    return representative;
+  bool hasOnlyNonDeferredImportPaths(Entity from, Entity to) {
+    ImportSet outputUnitFrom = outputUnitForElement(from);
+    ImportSet outputUnitTo = outputUnitForElement(to);
+    return outputUnitTo._imports.containsAll(outputUnitFrom._imports);
   }
 
   void registerConstantDeferredUse(
       DeferredConstantValue constant, PrefixElement prefix) {
-    OutputUnit outputUnit = new OutputUnit();
-    outputUnit.imports.add(new _DeclaredDeferredImport(prefix.deferredImport));
-
-    // Check to see if there is already a canonical output unit registered.
-    _constantToOutputUnit[constant] = _getCanonicalUnit(outputUnit);
+    var importSet = importSets.singleton(prefix.deferredImport);
+    assert(_constantToOutputUnit[constant] == null ||
+        _constantToOutputUnit[constant] == importSet);
+    _constantToOutputUnit[constant] = importSet;
   }
 
   /// Given [imports] that refer to an element from a library, determine whether
   /// the element is explicitly deferred.
   static bool _isExplicitlyDeferred(Iterable<ImportElement> imports) {
     // If the element is not imported explicitly, it is implicitly imported
     // not deferred.
     if (imports.isEmpty) return false;
     // An element could potentially be loaded by several imports. If all of them
     // is explicitly deferred, we say the element is explicitly deferred.
@@ skipping 65 matching lines @@
       } else {
         // TODO(sigurdm): We want to be more specific about this - need a better
         // way to query "liveness".
         MemberElement analyzableElement = element.analyzableElement.declaration;
         if (!compiler.resolutionWorldBuilder.isMemberUsed(analyzableElement)) {
           return;
         }
 
         WorldImpact worldImpact =
             compiler.resolution.getWorldImpact(analyzableElement);
+
         compiler.impactStrategy.visitImpact(
             analyzableElement,
             worldImpact,
             new WorldImpactVisitorImpl(visitStaticUse: (StaticUse staticUse) {
               elements.add(staticUse.element);
               switch (staticUse.kind) {
                 case StaticUseKind.CONSTRUCTOR_INVOKE:
                 case StaticUseKind.CONST_CONSTRUCTOR_INVOKE:
                   collectTypeDependencies(staticUse.type);
                   break;
@@ skipping 146 matching lines @@
       if (library.isPatched) {
         iterateTags(library.implementation);
       }
     }
 
     traverseLibrary(root);
     result.add(compiler.resolution.commonElements.coreLibrary);
     return result;
   }
 
-  /// Add all dependencies of [constant] to the mapping of [import].
-  void _mapConstantDependencies(
-      ConstantValue constant, _DeferredImport import) {
-    Set<ConstantValue> constants = _constantsDeferredBy.putIfAbsent(
-        import, () => new Set<ConstantValue>());
-    if (constants.contains(constant)) return;
-    constants.add(constant);
-    if (constant is ConstructedConstantValue) {
-      ClassElement cls = constant.type.element;
-      _mapDependencies(element: cls, import: import);
+  /// Update the import set of all constants reachable from [constant], as long
+  /// as they had the [oldSet]. As soon as we see a constant with a different
+  /// import set, we stop and enqueue a new recursive update in [queue].
+  ///
+  /// Invariants: oldSet is either null or a subset of newSet.
+  void _updateConstantRecursive(ConstantValue constant, ImportSet oldSet,
+      ImportSet newSet, WorkQueue queue) {
+    if (constant == null) return;
+    var importSet = _constantToOutputUnit[constant];
+
+    // Already visited.
+    if (importSet == newSet) return;
+
+    // Elements in the main output unit always remain there.
+    if (importSet == importSets.emptySet) return;
+
+    if (importSet == oldSet) {
+      _constantToOutputUnit[constant] = newSet;
+      if (constant is ConstructedConstantValue) {
+        ClassElement cls = constant.type.element;
+        _updateElementRecursive(cls, oldSet, newSet, queue);
+      }
+      constant.getDependencies().forEach((ConstantValue dependency) {
+        if (dependency is DeferredConstantValue) {
+          /// New deferred-imports are only discovered when we are visiting the
+          /// main output unit (size == 0) or code reachable from a deferred
+          /// import (size == 1). After that, we are rediscovering the
+          /// same nodes we have already seen.
+          if (newSet.size <= 1) {
+            PrefixElement prefix = dependency.prefix;
+            queue.addConstant(
+                dependency, importSets.singleton(prefix.deferredImport));
+          }
+        } else {
+          _updateConstantRecursive(dependency, oldSet, newSet, queue);
+        }
+      });
+    } else {
+      assert(
+          newSet != importSets.emptySet || oldSet != null,
+          failedAt(
+              NO_LOCATION_SPANNABLE,
+              "Tried to assign ${constant.toDartText()} to the main output "
+              "unit, but it was assigned to $importSet."));
+      queue.addConstant(constant, newSet);
     }
-    constant.getDependencies().forEach((ConstantValue dependency) {
-      _mapConstantDependencies(dependency, import);
-    });
   }
 
-  /// Recursively traverses the graph of dependencies from [element], mapping
-  /// deferred imports to each dependency it needs in the sets
-  /// [_importedDeferredBy] and [_constantsDeferredBy].
-  void _mapDependencies(
-      {Element element, _DeferredImport import, isMirrorUsage: false}) {
-    Set<Element> elements = _importedDeferredBy[import] ??= new Set<Element>();
+  /// Update the import set of all elements reachable from [element], as long as
+  /// they had the [oldSet]. As soon as we see an element with a different
+  /// import set, we stop and enqueue a new recursive update in [queue].
+  void _updateElementRecursive(
+      Element element, ImportSet oldSet, ImportSet newSet, WorkQueue queue,
+      {bool isMirrorUsage: false}) {
+    if (element == null) return;
+    var importSet = _elementToOutputUnit[element];
 
-    Set<Element> dependentElements = new Set<Element>();
-    Set<ConstantValue> dependentConstants = new Set<ConstantValue>();
+    // Already visited. We may visit some root nodes a second time with
+    // [isMirrorUsage] so we embed static members as well.
+    if (importSet == newSet && !isMirrorUsage) return;
 
-    LibraryElement library;
+    // Elements in the main output unit always remain there.
+    if (importSet == importSets.emptySet) return;
 
-    if (element != null) {
-      // Only process elements once, unless we are doing dependencies due to
-      // mirrors, which are added in additional traversals.
-      if (!isMirrorUsage && elements.contains(element)) return;
-      // Anything used directly by main will be loaded from the start
-      // We do not need to traverse it again.
-      if (import != _fakeMainImport && _mainElements.contains(element)) return;
-      // This adds [element] to [_mainElements] because [_mainElements] is
-      // aliased with `_importedDeferredBy[_fakeMainImport]]`.
-      elements.add(element);
+    if (importSet == oldSet) {
+      // Continue recursively updating from [oldSet] to [newSet].
+      _elementToOutputUnit[element] = newSet;
 
-      // This call can modify [dependentElements] and [dependentConstants].
+      Set<Element> dependentElements = new Set<Element>();
+      Set<ConstantValue> dependentConstants = new Set<ConstantValue>();
       _collectAllElementsAndConstantsResolvedFrom(
           element, dependentElements, dependentConstants, isMirrorUsage);
 
-      library = element.library;
-    }
+      LibraryElement library = element.library;
+      for (Element dependency in dependentElements) {
+        Iterable<ImportElement> imports = _getImports(dependency, library);
+        if (_isExplicitlyDeferred(imports)) {
+          /// New deferred-imports are only discovered when we are visiting the
+          /// main output unit (size == 0) or code reachable from a deferred
+          /// import (size == 1). After that, we are rediscovering the
+          /// same nodes we have already seen.
+          if (newSet.size <= 1) {
+            for (ImportElement deferredImport in imports) {
+              queue.addElement(
+                  dependency, importSets.singleton(deferredImport));
+            }
+          }
+        } else {
+          _updateElementRecursive(dependency, oldSet, newSet, queue);
+        }
+      }
 
-    for (Element dependency in dependentElements) {
-      Iterable<ImportElement> imports = _getImports(dependency, library);
-      if (_isExplicitlyDeferred(imports)) {
-        for (ImportElement deferredImport in imports) {
-          _mapDependencies(
-              element: dependency,
-              import: new _DeclaredDeferredImport(deferredImport));
+      for (ConstantValue dependency in dependentConstants) {
+        if (dependency is DeferredConstantValue) {
+          if (newSet.size <= 1) {
+            PrefixElement prefix = dependency.prefix;
+            queue.addConstant(
+                dependency, importSets.singleton(prefix.deferredImport));
+          }
+        } else {
+          _updateConstantRecursive(dependency, oldSet, newSet, queue);
         }
-      } else {
-        _mapDependencies(element: dependency, import: import);
       }
-    }
-
-    for (ConstantValue dependency in dependentConstants) {
-      if (dependency is DeferredConstantValue) {
-        PrefixElement prefix = dependency.prefix;
-        _mapConstantDependencies(
-            dependency, new _DeclaredDeferredImport(prefix.deferredImport));
-      } else {
-        _mapConstantDependencies(dependency, import);
-      }
+    } else {
+      // elements in the emptySet will never be updated, so we don't
+      // enqueue any work on them.
+      queue.addElement(element, newSet);
     }
   }
 
   /// Adds extra dependencies coming from mirror usage.
-  ///
-  /// The elements are added with [_mapDependencies].
-  void _addMirrorElements() {
-    void mapDependenciesIfResolved(
-        Element element, _DeferredImport deferredImport) {
+  void _addDeferredMirrorElements(WorkQueue queue) {
+    for (ImportElement deferredImport in importSets._allDeferredImports) {
+      _addMirrorElementsForLibrary(queue, deferredImport.importedLibrary,
+          importSets.singleton(deferredImport));
+    }
+  }
+
+  void _addMirrorElementsForLibrary(
+      WorkQueue queue, LibraryElement root, ImportSet importSet) {
+    void handleElementIfResolved(Element element, ImportSet importSet) {
       // If an element is the target of a MirrorsUsed annotation but never used
       // It will not be resolved, and we should not call isNeededForReflection.
       // TODO(sigurdm): Unresolved elements should just answer false when
       // asked isNeededForReflection. Instead an internal error is triggered.
       // So we have to filter them out here.
       if (element is AnalyzableElementX && !element.hasTreeElements) return;
 
       bool isAccessibleByReflection(Element element) {
         if (element.isLibrary) {
           return false;
         } else if (element.isClass) {
           ClassElement cls = element;
           return compiler.backend.mirrorsData
               .isClassAccessibleByReflection(cls);
         } else if (element.isTypedef) {
           TypedefElement typedef = element;
           return compiler.backend.mirrorsData
               .isTypedefAccessibleByReflection(typedef);
         } else {
           MemberElement member = element;
           return compiler.backend.mirrorsData
               .isMemberAccessibleByReflection(member);
         }
       }
 
       if (isAccessibleByReflection(element)) {
-        _mapDependencies(
-            element: element, import: deferredImport, isMirrorUsage: true);
+        queue.addElement(element, importSet, isMirrorsUsage: true);
       }
     }
 
     // For each deferred import we analyze all elements reachable from the
     // imported library through non-deferred imports.
-    void handleLibrary(LibraryElement library, _DeferredImport deferredImport) {
+    void handleLibrary(LibraryElement library, ImportSet importSet) {
       library.implementation.forEachLocalMember((Element element) {
-        mapDependenciesIfResolved(element, deferredImport);
+        handleElementIfResolved(element, importSet);
       });
 
       void processMetadata(Element element) {
         for (MetadataAnnotation metadata in element.metadata) {
           ConstantValue constant =
               backend.constants.getConstantValueForMetadata(metadata);
           if (constant != null) {
-            _mapConstantDependencies(constant, deferredImport);
+            queue.addConstant(constant, importSet);
           }
         }
       }
 
       processMetadata(library);
       library.imports.forEach(processMetadata);
       library.exports.forEach(processMetadata);
     }
 
-    for (_DeferredImport deferredImport in _allDeferredImports.keys) {
-      LibraryElement deferredLibrary = _allDeferredImports[deferredImport];
-      for (LibraryElement library
-          in _nonDeferredReachableLibraries(deferredLibrary)) {
-        handleLibrary(library, deferredImport);
-      }
+    for (LibraryElement library in _nonDeferredReachableLibraries(root)) {
+      handleLibrary(library, importSet);
     }
   }
 
   /// Computes a unique string for the name field for each outputUnit.
   ///
   /// Also sets up the [hunksToLoad] mapping.
-  void _assignNamesToOutputUnits(Set<OutputUnit> allOutputUnits) {
+  void _assignNamesToOutputUnits() {
     Set<String> usedImportNames = new Set<String>();
 
-    void computeImportDeferName(_DeferredImport import) {
-      String result = import.computeImportDeferName(compiler);
+    void computeImportDeferName(ImportElement import) {
+      String result = _computeImportDeferName(import, compiler);
       assert(result != null);
-      importDeferName[import] = makeUnique(result, usedImportNames);
+      _importDeferName[import] = makeUnique(result, usedImportNames);
     }
 
     int counter = 1;
 
-    for (_DeferredImport import in _allDeferredImports.keys) {
+    for (ImportElement import in _deferredImportDescriptions.keys) {
       computeImportDeferName(import);
     }
 
-    for (OutputUnit outputUnit in allOutputUnits) {
+    for (ImportSet outputUnit in allOutputUnits) {
       if (outputUnit == mainOutputUnit) {
         outputUnit.name = "main";
       } else {
         outputUnit.name = "$counter";
         ++counter;
       }
     }
 
     List sortedOutputUnits = new List.from(allOutputUnits);
     // Sort the output units in descending order of the number of imports they
     // include.
 
     // The loading of the output units must be ordered because a superclass
     // needs to be initialized before its subclass.
     // But a class can only depend on another class in an output unit shared by
     // a strict superset of the imports:
     // By contradiction: Assume a class C in output unit shared by imports in
     // the set S1 = (lib1,.., lib_n) depends on a class D in an output unit
     // shared by S2 such that S2 not a superset of S1. Let lib_s be a library in
     // S1 not in S2. lib_s must depend on C, and then in turn on D. Therefore D
     // is not in the right output unit.
-    sortedOutputUnits.sort((a, b) => b.imports.length - a.imports.length);
+    sortedOutputUnits.sort((a, b) => b.size - a.size);
 
     // For each deferred import we find out which outputUnits to load.
-    for (_DeferredImport import in _allDeferredImports.keys) {
-      if (import == _fakeMainImport) continue;
-      hunksToLoad[importDeferName[import]] = new List<OutputUnit>();
-      for (OutputUnit outputUnit in sortedOutputUnits) {
+    for (ImportElement import in importSets._allDeferredImports) {
+      hunksToLoad[_importDeferName[import]] = new List<OutputUnit>();
+      for (ImportSet outputUnit in sortedOutputUnits) {
         if (outputUnit == mainOutputUnit) continue;
-        if (outputUnit.imports.contains(import)) {
-          hunksToLoad[importDeferName[import]].add(outputUnit);
+        if (outputUnit._imports.contains(import)) {
+          hunksToLoad[_importDeferName[import]].add(outputUnit);
         }
       }
     }
   }
 
+  /// Performs the deferred loading algorithm.
+  ///
+  /// The deferred loading algorithm maps elements and constants to an output
+  /// unit. Each output unit is identified by a subset of deferred imports (an
+  /// [ImportSet]), and they will contain the elements that are inheretly used
+  /// by all those deferred imports. An element is used by a deferred import if
+  /// it is either loaded by that import or transitively accessed by an element
+  /// that the import loads.  An empty set represents the main output unit,
+  /// which contains any elements that are accessed directly and are not
+  /// deferred.
+  ///
+  /// The algorithm traverses the element model recursively looking for
+  /// dependencies between elements. These dependencies may be deferred or
+  /// non-deferred. Deferred dependencies are mainly used to discover the root
+  /// elements that are loaded from deferred imports, while non-deferred
+  /// dependencies are used to recursively associate more elements to output
+  /// units.
+  ///
+  /// Naively, the algorithm traverses each root of a deferred import and marks
+  /// everything it can reach as being used by that import. To reduce how many
+  /// times we visit an element, we use an algorithm that works in segments: it
+  /// marks elements with a subset of deferred imports at a time, until it
+  /// detects a merge point where more deferred imports could be considered at
+  /// once.
+  ///
+  /// For example, consider this dependency graph (ignoring elements in the main
+  /// output unit):
+  ///
+  ///   deferred import A: a1 ---> s1 ---> s2  -> s3
+  ///                              ^       ^
+  ///                              |       |
+  ///   deferred import B: b1 -----+       |
+  ///                                      |
+  ///   deferred import C: c1 ---> c2 ---> c3
+  ///
+  /// The algorithm will compute a result with 5 deferred output units:
+  //
+  ///   * unit {A}:        contains a1
+  ///   * unit {B}:        contains b1
+  ///   * unit {C}:        contains c1, c2, and c3
+  ///   * unit {A, B}:     contains s1
+  ///   * unit {A, B, C}:  contains s2, and s3
+  ///
+  /// After marking everything reachable from main as part of the main output
+  /// unit, our algorithm will work as follows:
+  ///
+  ///   * Initially all deferred elements have no mapping.
+  ///   * We make note of work to do, initially to mark the root of each
+  ///     deferred import:
+  ///        * a1 with A, and recurse from there.
+  ///        * b1 with B, and recurse from there.
+  ///        * c1 with C, and recurse from there.
+  ///   * we update a1, s1, s2, s3 from no mapping to {A}
+  ///   * we update b1 from no mapping to {B}, and when we find s1 we notice
+  ///     that s1 is already associated with another import set {A}, so we make
+  ///     note of additional work for later to mark s1 with {A, B}
+  ///   * we update c1, c2, c3 to {C}, and make a note to update s2 with {A, C}
+  ///   * we update s1 to {A, B}, and update the existing note to update s2, now
+  ///     with {A, B, C}
+  ///   * finally we update s2 and s3 with {A, B, C} in one go, without ever
+  ///     updating them to the intermediate state {A, C}.
+  ///
+  /// The implementation below does atomic updates from one import-set to
+  /// another.  At first we add one deferred import at a time, but as the
+  /// algorithm progesses it may update a small import-set with a larger
+  /// import-set in one go. The key of this algorithm is to detect when sharing
+  /// begins, so we can update those elements more efficently.
+  ///
+  /// To detect these merge points where sharing begins, the implementation
+  /// below uses `a swap operation`: we first compare what the old import-set
+  /// is, and if it matches our expectation, the swap is done and we recurse,
+  /// otherwise a merge root was detected and we enqueue a new segment of
+  /// updates for later.
+  ///
+  /// TODO(sigmund): investigate different heuristics for how to select the next
+  /// work item (e.g. we might converge faster if we pick first the update that
+  /// contains a bigger delta.)
   void onResolutionComplete(FunctionEntity main, ClosedWorld closedWorld) {
-    if (!isProgramSplit) {
-      allOutputUnits.add(mainOutputUnit);
-      return;
-    }
+    if (!isProgramSplit) return;
     if (main == null) return;
-    MethodElement mainMethod = main;
-    LibraryElement mainLibrary = mainMethod.library;
-    _importedDeferredBy = new Map<_DeferredImport, Set<Element>>();
-    _constantsDeferredBy = new Map<_DeferredImport, Set<ConstantValue>>();
-    _importedDeferredBy[_fakeMainImport] = _mainElements;
+    work() {
+      var queue = new WorkQueue(this.importSets);
 
-    work() {
-      // Starting from main, traverse the program and find all dependencies.
-      _mapDependencies(element: mainMethod, import: _fakeMainImport);
+      // Add `main` and their recursive dependencies to the main output unit.

[sra1, 2017/08/18 23:42:28]

Explain somewhere why the main unit is completely explored before any other.

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Done.

+      queue.addElement(main, importSets.emptySet);
 
-      // Also add "global" dependencies to the main OutputUnit.  These are
+      // Also add "global" dependencies to the main output unit.  These are
       // things that the backend needs but cannot associate with a particular
       // element, for example, startRootIsolate.  This set also contains
       // elements for which we lack precise information.
       for (MethodElement element
           in closedWorld.backendUsage.globalFunctionDependencies) {
-        _mapDependencies(
-            element: element.implementation, import: _fakeMainImport);
+        queue.addElement(element.implementation, importSets.emptySet);
       }
       for (ClassElement element
           in closedWorld.backendUsage.globalClassDependencies) {
-        _mapDependencies(
-            element: element.implementation, import: _fakeMainImport);
+        queue.addElement(element.implementation, importSets.emptySet);
+      }
+      if (closedWorld.backendUsage.isMirrorsUsed) {
+        _addMirrorElementsForLibrary(queue, main.library, importSets.emptySet);
       }
 
-      // Now check to see if we have to add more elements due to mirrors.
-      if (closedWorld.backendUsage.isMirrorsUsed) {
-        _addMirrorElements();
-      }
-
-      // Build the OutputUnits using these two maps.
-      Map<Element, OutputUnit> elementToOutputUnitBuilder =
-          new Map<Element, OutputUnit>();
-      Map<ConstantValue, OutputUnit> constantToOutputUnitBuilder =
-          new Map<ConstantValue, OutputUnit>();
-
-      // Add all constants that may have been registered during resolution with
-      // [registerConstantDeferredUse].
-      constantToOutputUnitBuilder.addAll(_constantToOutputUnit);
-      _constantToOutputUnit.clear();
-
-      // Reverse the mappings. For each element record an OutputUnit collecting
-      // all deferred imports mapped to this element. Same for constants.
-      for (_DeferredImport import in _importedDeferredBy.keys) {
-        for (Element element in _importedDeferredBy[import]) {
-          // Only one file should be loaded when the program starts, so make
-          // sure that only one OutputUnit is created for [fakeMainImport].
-          if (import == _fakeMainImport) {
-            elementToOutputUnitBuilder[element] = mainOutputUnit;
-          } else {
-            elementToOutputUnitBuilder
-                .putIfAbsent(element, () => new OutputUnit())
-                .imports
-                .add(import);
-          }
-        }
-      }
-      for (_DeferredImport import in _constantsDeferredBy.keys) {
-        for (ConstantValue constant in _constantsDeferredBy[import]) {
-          // Only one file should be loaded when the program starts, so make
-          // sure that only one OutputUnit is created for [fakeMainImport].
-          if (import == _fakeMainImport) {
-            constantToOutputUnitBuilder[constant] = mainOutputUnit;
-          } else {
-            constantToOutputUnitBuilder
-                .putIfAbsent(constant, () => new OutputUnit())
-                .imports
-                .add(import);
+      void emptyQueue() {
+        while (!queue.isEmpty) {

[sra1, 2017/08/18 23:42:28]

nit:  queue.isNotEmpty

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Done.

+          var item = queue.nextItem();
+          if (item.element != null) {
+            var oldSet = _elementToOutputUnit[item.element];
+            var newSet = importSets.union(oldSet, item.newSet);
+            _updateElementRecursive(item.element, oldSet, newSet, queue);
+          } else if (item.value != null) {
+            var oldSet = _constantToOutputUnit[item.value];
+            var newSet = importSets.union(oldSet, item.newSet);
+            _updateConstantRecursive(item.value, oldSet, newSet, queue);
           }
         }
       }
 
-      // Release maps;
-      _importedDeferredBy = null;
-      _constantsDeferredBy = null;
+      emptyQueue();
+      if (closedWorld.backendUsage.isMirrorsUsed) {
+        _addDeferredMirrorElements(queue);
+        emptyQueue();
+      }
 
-      // Find all the output units elements/constants have been mapped
-      // to, and canonicalize them.
-      elementToOutputUnitBuilder
-          .forEach((Element element, OutputUnit outputUnit) {
-        _elementToOutputUnit[element] = _getCanonicalUnit(outputUnit);
-      });
-      constantToOutputUnitBuilder
-          .forEach((ConstantValue constant, OutputUnit outputUnit) {
-        _constantToOutputUnit[constant] = _getCanonicalUnit(outputUnit);
-      });
+      allOutputUnits.addAll(_elementToOutputUnit.values);
+      allOutputUnits.addAll(_constantToOutputUnit.values);
+
+      /// We generate an output unit for each defer import, even if all their
+      /// elements are shared with other deferred imports.
+      allOutputUnits
+          .addAll(_deferredImportDescriptions.keys.map(importSets.singleton));
 
       // Generate a unique name for each OutputUnit.
-      _assignNamesToOutputUnits(allOutputUnits);
+      _assignNamesToOutputUnits();
     }
 
-    reporter.withCurrentElement(mainLibrary, () => measure(work));
+    reporter.withCurrentElement(main.library, () => measure(work));
 
-    // Notify the impact strategy impacts are no longer needed for deferred
-    // load.
+    // Notify that we no longer need impacts for deferred load, so they can be
+    // discarded at this time.
     compiler.impactStrategy.onImpactUsed(IMPACT_USE);
   }
 
   void beforeResolution(LibraryEntity mainLibrary) {
     if (mainLibrary == null) return;
     // TODO(johnniwinther): Support deferred load for kernel based elements.
     if (compiler.options.useKernel) return;
-    _allDeferredImports[_fakeMainImport] = mainLibrary;
     var lastDeferred;
     // When detecting duplicate prefixes of deferred libraries there are 4
     // cases of duplicate prefixes:
     // 1.
     // import "lib.dart" deferred as a;
     // import "lib2.dart" deferred as a;
     // 2.
     // import "lib.dart" deferred as a;
     // import "lib2.dart" as a;
     // 3.
@@ skipping 30 matching lines @@
                 reporter.reportErrorMessage(
                     import, MessageKind.DEFERRED_OLD_SYNTAX);
               }
             }
           }
 
           String prefix = (import.prefix != null) ? import.prefix.name : null;
           // The last import we saw with the same prefix.
           ImportElement previousDeferredImport = prefixDeferredImport[prefix];
           if (import.isDeferred) {
-            _DeferredImport key = new _DeclaredDeferredImport(import);
-            LibraryElement importedLibrary = import.importedLibrary;
-            _allDeferredImports[key] = importedLibrary;
-
             if (prefix == null) {
               reporter.reportErrorMessage(
                   import, MessageKind.DEFERRED_LIBRARY_WITHOUT_PREFIX);
             } else {
               prefixDeferredImport[prefix] = import;
               Uri mainLibraryUri = compiler.mainLibraryUri;
-              _deferredImportDescriptions[key] =
+              _deferredImportDescriptions[import] =
                   new ImportDescription(import, library, mainLibraryUri);
             }
             isProgramSplit = true;
             lastDeferred = import;
           }
           if (prefix != null) {
             if (previousDeferredImport != null ||
                 (import.isDeferred && usedPrefixes.contains(prefix))) {
               ImportElement failingImport = (previousDeferredImport != null)
                   ? previousDeferredImport
@@ skipping 78 matching lines @@
   /// - <library uri> is the relative uri of the library making a deferred
   ///   import.
   /// - <library name> is the name of the library, and "<unnamed>" if it is
   ///   unnamed.
   /// - <prefix> is the `as` prefix used for a given deferred import.
   /// - <list of files> is a list of the filenames the must be loaded when that
   ///   import is loaded.
   Map<String, Map<String, dynamic>> computeDeferredMap() {
     Map<String, Map<String, dynamic>> mapping =
         new Map<String, Map<String, dynamic>>();
-    _deferredImportDescriptions.keys.forEach((_DeferredImport import) {
-      List<OutputUnit> outputUnits = hunksToLoad[importDeferName[import]];
+    _deferredImportDescriptions.keys.forEach((ImportElement import) {
+      List<OutputUnit> outputUnits = hunksToLoad[_importDeferName[import]];
       ImportDescription description = _deferredImportDescriptions[import];
       Map<String, dynamic> libraryMap = mapping.putIfAbsent(
           description.importingUri,
           () => <String, dynamic>{
                 "name": description.importingLibraryName,
                 "imports": <String, List<String>>{}
               });
 
-      libraryMap["imports"][importDeferName[import]] =
+      libraryMap["imports"][_importDeferName[import]] =
           outputUnits.map((OutputUnit outputUnit) {
         return deferredPartFileName(outputUnit.name);
       }).toList();
     });
     return mapping;
   }
 
   /// Returns the filename for the output-unit named [name].
   ///
   /// The filename is of the form "<main output file>_<name>.part.js".
@@ skipping 13 matching lines @@
     Map<OutputUnit, List<String>> elementMap = <OutputUnit, List<String>>{};
     Map<OutputUnit, List<String>> constantMap = <OutputUnit, List<String>>{};
     _elementToOutputUnit.forEach((Element element, OutputUnit output) {
       elementMap.putIfAbsent(output, () => <String>[]).add('$element');
     });
     _constantToOutputUnit.forEach((ConstantValue value, OutputUnit output) {
       constantMap
           .putIfAbsent(output, () => <String>[])
           .add(value.toStructuredText());
     });
+    elementMap.forEach((k, v) => v.sort());
+    constantMap.forEach((k, v) => v.sort());
 
     StringBuffer sb = new StringBuffer();
-    for (OutputUnit outputUnit in allOutputUnits) {
+    var list = allOutputUnits.toList();
+    list.sort((a, b) {
+      if (elementMap[a] != null && elementMap[b] == null) return -1;
+      if (elementMap[a] == null && elementMap[b] != null) return 1;
+      if (elementMap[a] == null && elementMap[b] == null) {
+        if (constantMap[a] != null && constantMap[b] == null) return -1;
+        if (constantMap[a] == null && constantMap[b] != null) return 1;
+        for (int i = 0; i < constantMap[a].length; i++) {
+          if (i >= constantMap[b].length) return 1;
+          var fa = constantMap[a][i];
+          var fb = constantMap[b][i];
+          if (fa != fb) return fa.compareTo(fb);
+        }
+        return -1;
+      }
+      for (int i = 0; i < elementMap[a].length; i++) {
+        if (i >= elementMap[b].length) return 1;
+        var fa = elementMap[a][i];
+        var fb = elementMap[b][i];
+        if (fa != fb) return fa.compareTo(fb);
+      }
+      return -1;
+    });
+    for (OutputUnit outputUnit in list) {
       sb.write('\n-------------------------------\n');
       sb.write('Output unit: ${outputUnit.name}');
       List<String> elements = elementMap[outputUnit];
       if (elements != null) {
         sb.write('\n elements:');
         for (String element in elements..sort()) {
           sb.write('\n  $element');
         }
       }
       List<String> constants = constantMap[outputUnit];
@@ skipping 23 matching lines @@
         prefix = import.prefix.name,
         _importingLibrary = importingLibrary;
 
   String get importingLibraryName {
     return _importingLibrary.hasLibraryName
         ? _importingLibrary.libraryName
         : "<unnamed>";
   }
 }
 
-/// A node in the deferred import graph.
+/// A compact lattice representation of import sets and subsets.
 ///
-/// This class serves as the root node; the 'import' of the main library.
-class _DeferredImport {
-  const _DeferredImport();
-
-  /// Computes a suggestive name for this import.
-  String computeImportDeferName(Compiler compiler) => 'main';
-
-  ImportElement get declaration => null;
-
-  String toString() => 'main';
-}
-
-/// A node in the deferred import graph defined by a deferred import directive.
-class _DeclaredDeferredImport implements _DeferredImport {
-  final ImportElement declaration;
-
-  _DeclaredDeferredImport(this.declaration);
+/// We use a graph of nodes to represent elements of the lattice, but only
+/// create new nodes on-demand as they are needed by the deferred loading
+/// algorithm.
+///
+/// The constructions of nodes is carefully done by storing imports in a
+/// specific order. This ensures that we have a unique and canonical
+/// representation for each subset.
+class ImportSetLattice {
+  /// The set of all deferred imports seen in the program, in a canonical order.
+  List<ImportElement> _allDeferredImports = [];
+
+  /// The index corresponding to a deferred import according to the canonical
+  /// order.
+  /// Invariant: `_allDeferredImports[_importIndex[i]] == i`.
+  Map<ImportElement, int> _importIndex = {};
+
+  /// The empty import set. This corresponds to the main output unit.
+  ImportSet emptySet = new ImportSet();
+
+  /// Get the singleton import set that only contains [import].
+  ImportSet singleton(ImportElement import) => _add(emptySet, import);
+
+  /// Get the import set that includes all imports in [importSet] and [import].
+  ImportSet _add(ImportSet importSet, ImportElement import) {
+    if (importSet._imports.contains(import)) return importSet;
+    var index = _indexOf(import);
+    var otherImportAdded = false;
+    var result = emptySet;
+    for (var existing in importSet._imports) {

[sra1, 2017/08/18 23:42:28]

This loop inside the merge loop in union makes union O(N^2)

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Doh! - and good catch!

I meant to use result._add in `union`, and not this function. Funny enough even
with this the implementation was faster than the old one. Now, it's way better!
Large up completes in under 6s

+      if (!otherImportAdded && _indexOf(existing) > index) {
+        result = result._add(import);
+        otherImportAdded = true;
+      }
+      result = result._add(existing);
+    }
+    if (!otherImportAdded) {
+      result = result._add(import);
+    }
+    // TODO(sigmund): use _neighbors to cache transitions
+    // importSet._neighbors[import] = result;
+    return result;
+  }
+
+  /// Get the import set that includes the union of [a] and [b].
+  ImportSet union(ImportSet a, ImportSet b) {
+    if (a == null || a == emptySet) return b;
+    if (b == null || b == emptySet) return a;
+
+    // We create the union by merging the imports in canonical order first, and
+    // then getting (or creating) the canonical sets by adding an import at a
+    // time.
+    List<ImportElement> aImports = a._imports.toList();

[sra1, 2017/08/18 23:42:28]

Could also use iterators over the sets.

[Siggi Cherem (dart-lang), 2017/08/28 16:57:15]

thanks nice idea. After splitting import-set and output unit, I realized I could
simply use a List in the representation of importSets. As a result, I decided to
continue with the indexing approach here.

+    List<ImportElement> bImports = b._imports.toList();
+    int i = 0, j = 0;
+    int lastAIndex = 0, lastBIndex = 0;
+    var result = emptySet;
+    while (i < aImports.length && j < bImports.length) {
+      var importA = aImports[i];
+      var importB = bImports[j];
+      var aIndex = _indexOf(importA);
+      var bIndex = _indexOf(importB);
+      assert(lastAIndex <= aIndex);
+      assert(lastBIndex <= bIndex);
+      if (aIndex == bIndex) {

[sra1, 2017/08/18 23:42:29]

This case can be avoided with a self-edge (see below)

[Siggi Cherem (dart-lang), 2017/08/28 16:57:15]

Done.

+        result = _add(result, importA);
+        i++;
+        j++;
+      } else if (aIndex < bIndex) {
+        result = _add(result, importA);

[sra1, 2017/08/18 23:42:29]

Why is this not the following?

   result = result._add(importA);

We are merging ordered items (and removing duplicates explicitly or via a
self-edge), so this should work directly.

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

yes! indeed. good catch

+        i++;
+      } else {
+        result = _add(result, importB);
+        j++;
+      }
+    }
+    for (; i < aImports.length; i++) {
+      result = _add(result, aImports[i]);
+    }
+    for (; j < bImports.length; j++) {
+      result = _add(result, bImports[j]);
+    }
+    return result;
+  }
+
+  /// Get the index for an [import] according to the canonical order.
+  int _indexOf(ImportElement import) {
+    var index = _importIndex[import];

[sra1, 2017/08/18 23:42:29]

I think is is worth keeping _DeferredImport as a place to store the index.
This might be advantageous if the Kernel representation is a little more tricky
between multiple .dill files.

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Thanks, I like how this simplified things.

I changed it to wrap when we create the singleton sets. Afterwards the sets
directly operate over the wrapped imports, so there is no lookup in a map
anymore.

Another idea I was thinking about was to just store the index in the set
directly, and use a list (_allDeferredImports) to do the reverse lookup after
the algorithm is done. I believe they should be similar in perf, so I went with
your suggestion because I believe it makes the code easier to follow.

+    if (index == null) {
+      index = _importIndex[import] = _allDeferredImports.length;
+      _allDeferredImports.add(import);
+    }
+    return index;
+  }
+}
+
+/// A canonical set of deferred imports.
+class ImportSet implements OutputUnit {

[sra1, 2017/08/18 23:42:29]

I'd rather ImportSet and OutputUnit be separate, with the output unit
referencing the set.
Not all ImportSets are OutputUnits.
We will want to merge OutputUnits which breaks the 1-1 correspondence.

Maybe a TODO.

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Done.

However, I don't have the edge from OutputUnit to ImportSet, but the opposite at
this time. OutputUnit contains the actual set of imports, ImportSet.unit is used
to indirectly map the result of the algorithm to an output unit.

I did this to avoid coping again the results of the algorithm, but the
alternative here would be to create a new Map<Entity, OutputUnit> (and ditch the
existing Map<Entity, ImportSet>).

Let me know if you prefer that we do the latter.

+  /// Imports that are part of this set.
+  ///
+  /// Invariant: this is a LinkedHashSet and the order in which elements are
+  /// added must respect the canonical order.
+  final Set<ImportElement> _imports = new Set();

[sra1, 2017/08/18 23:42:28]

<ImportElement>

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Done.

+  final Map<ImportElement, ImportSet> _neighbors = {};
 
   @override
-  String computeImportDeferName(Compiler compiler) {
-    String result;
-    if (declaration.isDeferred) {
-      if (declaration.prefix != null) {
-        result = declaration.prefix.name;
-      } else {
-        // This happens when the deferred import isn't declared with a prefix.
-        assert(compiler.compilationFailed);
-        result = '';
+  bool get isMainOutput => _imports.isEmpty;

[sra1, 2017/08/18 23:42:28]

This is called a lot.
I wonder if the old way of having a final bool field would be more efficient.

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Done with the split of ImportSet and output unit

+
+  @override
+  String name;
+
+  int get size => _imports.length;

[sra1, 2017/08/18 23:42:28]

This name (or 'length') makes sense for an ImportSet but not an OutputUnit where
'size' could be the number of elements or the estimated size of all the
elements.

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Done.

+
+  /// Create an import set that adds [import] to all the imports on this set.
+  /// This assumes that import's canonical order comes after all imports in
+  /// this current set. This should only be called from [ImportSetLattice],
+  /// since it is where we preserve this invariant.
+  ImportSet _add(ImportElement import) {
+    return _neighbors.putIfAbsent(import, () {
+      var result = new ImportSet();
+      result._imports.addAll(_imports);
+      result._imports.add(import);

[sra1, 2017/08/18 23:42:28]

Adding a self edge allows the 'already-a-member' case to be simplified.

    result._neighbors[import] = result;

If you do this, rename _neighbors to _transitions

[Siggi Cherem (dart-lang), 2017/08/28 16:57:15]

Done.

+      return result;
+    });
+  }
+
+  String toString() {
+    StringBuffer sb = new StringBuffer();
+    sb.write('ImportSet(size: $size, ');
+    for (var import in _imports) {
+      sb.write('${import.prefix} ');
+    }
+    sb.write(')');
+    return '$sb';
+  }
+}
+
+/// The algorithm work queue.
+class WorkQueue {
+  Map<Entity, WorkItem> pendingElements = {};

[sra1, 2017/08/18 23:42:29]

Types on map literals.

[sra1, 2017/08/18 23:42:29]

final?

[Siggi Cherem (dart-lang), 2017/08/28 16:57:14]

Added, but note they are not needed in the short future (they'll be inferred in
strong mode)

[Siggi Cherem (dart-lang), 2017/08/28 16:57:15]

Done.

+  Map<ConstantValue, WorkItem> pendingConstants = {};
+  Queue<WorkItem> queue = new Queue<WorkItem>();
+
+  ImportSetLattice importSets;
+
+  WorkQueue(this.importSets);
+
+  bool get isEmpty => queue.isEmpty;
+
+  WorkItem nextItem() {
+    var item = queue.removeFirst();
+    if (item.element != null) pendingElements.remove(item.element);
+    if (item.value != null) pendingConstants.remove(item.value);
+    return item;
+  }
+
+  addElement(Entity element, ImportSet importSet, {isMirrorsUsage: false}) {
+    var item = pendingElements[element];
+    if (item == null) {
+      item = new WorkItem(element, importSet);
+      pendingElements[element] = item;
+      queue.add(item);
+    } else {
+      item.newSet = importSets.union(item.newSet, importSet);
+    }
+    if (isMirrorsUsage) item.isMirrorsUsage = true;
+  }
+
+  addConstant(ConstantValue constant, ImportSet importSet) {
+    var item = pendingConstants[constant];
+    if (item == null) {
+      item = new WorkItem.constant(constant, importSet);
+      pendingConstants[constant] = item;
+      queue.add(item);
+    } else {
+      item.newSet = importSets.union(item.newSet, importSet);
+    }
+  }
+}
+
+class WorkItem {
+  final Entity element;
+  final ConstantValue value;
+
+  ImportSet newSet;
+  bool isMirrorsUsage = false;
+
+  WorkItem(this.element, this.newSet) : value = null;
+  WorkItem.constant(this.value, this.newSet) : element = null;
+}
+
+/// Returns a name for a deferred import.
+// TODO(sigmund): delete support for the old annotation-style syntax.
+String _computeImportDeferName(ImportElement declaration, Compiler compiler) {
+  String result;
+  if (declaration.isDeferred) {
+    if (declaration.prefix != null) {
+      result = declaration.prefix.name;
+    } else {
+      // This happens when the deferred import isn't declared with a prefix.
+      assert(compiler.compilationFailed);
+      result = '';
+    }
+  } else {
+    // Finds the first argument to the [DeferredLibrary] annotation
+    List<MetadataAnnotation> metadatas = declaration.metadata;
+    assert(metadatas != null);
+    for (MetadataAnnotation metadata in metadatas) {
+      metadata.ensureResolved(compiler.resolution);
+      ConstantValue value =
+          compiler.constants.getConstantValue(metadata.constant);
+      ResolutionDartType type =
+          value.getType(compiler.resolution.commonElements);
+      Element element = type.element;
+      if (element == compiler.resolution.commonElements.deferredLibraryClass) {
+        ConstructedConstantValue constant = value;
+        StringConstantValue s = constant.fields.values.single;
+        result = s.primitiveValue;
+        break;
       }
-    } else {
-      // Finds the first argument to the [DeferredLibrary] annotation
-      List<MetadataAnnotation> metadatas = declaration.metadata;
-      assert(metadatas != null);
-      for (MetadataAnnotation metadata in metadatas) {
-        metadata.ensureResolved(compiler.resolution);
-        ConstantValue value =
-            compiler.constants.getConstantValue(metadata.constant);
-        ResolutionDartType type =
-            value.getType(compiler.resolution.commonElements);
-        Element element = type.element;
-        if (element ==
-            compiler.resolution.commonElements.deferredLibraryClass) {
-          ConstructedConstantValue constant = value;
-          StringConstantValue s = constant.fields.values.single;
-          result = s.primitiveValue;
-          break;
-        }
-      }
-    }
-    assert(result != null);
-    return result;
-  }
-
-  bool operator ==(other) {
-    if (other is! _DeclaredDeferredImport) return false;
-    return declaration == other.declaration;
-  }
-
-  int get hashCode => declaration.hashCode * 17;
-
-  String toString() => '$declaration';
-}
+    }
+  }
+  assert(result != null);
+  return result;
+}