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
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 uni
Siggi Cherem (dart-lang)
2017/08/28 16:57:14
Doh! - and good catch!
I meant to use result._add
|
+ 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 o
|
+ 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 bel
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
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 p
Siggi Cherem (dart-lang)
2017/08/28 16:57:14
Thanks, I like how this simplified things.
I chan
|
+ 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, w
Siggi Cherem (dart-lang)
2017/08/28 16:57:14
Done.
However, I don't have the edge from OutputU
|
+ /// 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 h
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 ImportS
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' c
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 f
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; |
} |