Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1355)

Unified Diff: pkg/compiler/lib/src/deferred_load.dart

Issue 2997233002: Update defer loading algorithm: (Closed)
Patch Set: Created 3 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « no previous file | pkg/compiler/lib/src/dump_info.dart » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
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;
}
« no previous file with comments | « no previous file | pkg/compiler/lib/src/dump_info.dart » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698