Update defer loading algorithm:

pkg/compiler/lib/src/deferred_load.dart

Index: pkg/compiler/lib/src/deferred_load.dart
diff --git a/pkg/compiler/lib/src/deferred_load.dart b/pkg/compiler/lib/src/deferred_load.dart
index 43ad9971fae26dd65f4555cb0f57186685f3d02e..80e00e224de5a95fb2f487a7130ec71f9a58310e 100644
--- a/pkg/compiler/lib/src/deferred_load.dart
+++ b/pkg/compiler/lib/src/deferred_load.dart
@@ -4,6 +4,8 @@
 
 library deferred_load;
 
+import 'dart:collection' show Queue;
+
 import 'common/tasks.dart' show CompilerTask;
 import 'common.dart';
 import 'compiler.dart' show Compiler;
@@ -54,35 +56,13 @@ import 'world.dart' show ClosedWorld;
 /// 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
@@ -96,15 +76,12 @@ class DeferredLoadTask extends CompilerTask {
   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;
@@ -123,42 +100,31 @@ class DeferredLoadTask extends CompilerTask {
 
   /// 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>{};
-
-  // 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;
+  final Map<ImportElement, ImportDescription> _deferredImportDescriptions =
+      <ImportElement, ImportDescription>{};
 
-  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;
@@ -187,7 +153,7 @@ class DeferredLoadTask extends CompilerTask {
   }
 
   /// Returns the [OutputUnit] where [element] belongs.
-  OutputUnit outputUnitForClass(ClassEntity element) {
+  OutputUnit outputUnitForClass(ClassElement element) {
     return outputUnitForElement(element);
   }
 
@@ -197,7 +163,7 @@ class DeferredLoadTask extends CompilerTask {
   }
 
   /// Direct access to the output-unit to element relation used for testing.
-  OutputUnit getOutputUnitForElementForTesting(Element element) {
+  OutputUnit getOutputUnitForElementForTesting(Entity element) {
     return _elementToOutputUnit[element];
   }
 
@@ -222,43 +188,37 @@ class DeferredLoadTask extends CompilerTask {
 
   /// 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
@@ -344,6 +304,7 @@ class DeferredLoadTask extends CompilerTask {
 
         WorldImpact worldImpact =
             compiler.resolution.getWorldImpact(analyzableElement);
+
         compiler.impactStrategy.visitImpact(
             analyzableElement,
             worldImpact,
@@ -510,82 +471,127 @@ class DeferredLoadTask extends CompilerTask {
     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>();
-
-    Set<Element> dependentElements = new Set<Element>();
-    Set<ConstantValue> dependentConstants = new Set<ConstantValue>();
-
-    LibraryElement library;
-
-    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);
+  /// 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];
 
-      // This call can modify [dependentElements] and [dependentConstants].
+    // 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;
+
+    // Elements in the main output unit always remain there.
+    if (importSet == importSets.emptySet) return;
+
+    if (importSet == oldSet) {
+      // Continue recursively updating from [oldSet] to [newSet].
+      _elementToOutputUnit[element] = newSet;
+
+      Set<Element> dependentElements = new Set<Element>();
+      Set<ConstantValue> dependentConstants = new Set<ConstantValue>();
       _collectAllElementsAndConstantsResolvedFrom(
           element, dependentElements, dependentConstants, isMirrorUsage);
 
-      library = element.library;
-    }
-
-    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));
+      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);
         }
-      } 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);
+      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 {
+      // 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
@@ -612,16 +618,15 @@ class DeferredLoadTask extends CompilerTask {
       }
 
       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) {
@@ -629,7 +634,7 @@ class DeferredLoadTask extends CompilerTask {
           ConstantValue constant =
               backend.constants.getConstantValueForMetadata(metadata);
           if (constant != null) {
-            _mapConstantDependencies(constant, deferredImport);
+            queue.addConstant(constant, importSet);
           }
         }
       }
@@ -639,34 +644,30 @@ class DeferredLoadTask extends CompilerTask {
       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 {
@@ -688,122 +689,159 @@ class DeferredLoadTask extends CompilerTask {
     // 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() {
-      // Starting from main, traverse the program and find all dependencies.
-      _mapDependencies(element: mainMethod, import: _fakeMainImport);
+      var queue = new WorkQueue(this.importSets);
 
-      // Also add "global" dependencies to the main OutputUnit.  These are
+      // 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 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);
       }
-
-      // Now check to see if we have to add more elements due to mirrors.
       if (closedWorld.backendUsage.isMirrorsUsed) {
-        _addMirrorElements();
+        _addMirrorElementsForLibrary(queue, main.library, importSets.emptySet);
       }
 
-      // 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);
+      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);
           }
         }
       }
-      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);
-          }
-        }
+
+      emptyQueue();
+      if (closedWorld.backendUsage.isMirrorsUsed) {
+        _addDeferredMirrorElements(queue);
+        emptyQueue();
       }
 
-      // Release maps;
-      _importedDeferredBy = null;
-      _constantsDeferredBy = null;
+      allOutputUnits.addAll(_elementToOutputUnit.values);
+      allOutputUnits.addAll(_constantToOutputUnit.values);
 
-      // 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);
-      });
+      /// 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);
   }
 
@@ -811,7 +849,6 @@ class DeferredLoadTask extends CompilerTask {
     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:
@@ -862,17 +899,13 @@ class DeferredLoadTask extends CompilerTask {
           // 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;
@@ -971,8 +1004,8 @@ class DeferredLoadTask extends CompilerTask {
   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,
@@ -981,7 +1014,7 @@ class DeferredLoadTask extends CompilerTask {
                 "imports": <String, List<String>>{}
               });
 
-      libraryMap["imports"][importDeferName[import]] =
+      libraryMap["imports"][_importDeferName[import]] =
           outputUnits.map((OutputUnit outputUnit) {
         return deferredPartFileName(outputUnit.name);
       }).toList();
@@ -1015,9 +1048,34 @@ class DeferredLoadTask extends CompilerTask {
           .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];
@@ -1061,67 +1119,229 @@ class ImportDescription {
   }
 }
 
-/// 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';
+/// 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;
+  }
 
-  ImportElement get declaration => null;
+  /// 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;
+  }
 
-  String toString() => 'main';
+  /// 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 node in the deferred import graph defined by a deferred import directive.
-class _DeclaredDeferredImport implements _DeferredImport {
-  final ImportElement declaration;
+/// 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 = {};
 
-  _DeclaredDeferredImport(this.declaration);
+  @override
+  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 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 = '';
-      }
+  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 {
-      // 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;
-        }
-      }
+      item.newSet = importSets.union(item.newSet, importSet);
     }
-    assert(result != null);
-    return result;
+    if (isMirrorsUsage) item.isMirrorsUsage = true;
   }
 
-  bool operator ==(other) {
-    if (other is! _DeclaredDeferredImport) return false;
-    return declaration == other.declaration;
+  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;
 
-  int get hashCode => declaration.hashCode * 17;
+  ImportSet newSet;
+  bool isMirrorsUsage = false;
 
-  String toString() => '$declaration';
+  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;
+      }
+    }
+  }
+  assert(result != null);
+  return result;
 }