blob: 15c4b7c9adea5172aa658d893f64da83fa0dd016 [file] [log] [blame]
// Copyright (c) 2016, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
import 'package:analyzer/src/generated/utilities_dart.dart';
import 'package:analyzer/src/summary/format.dart';
import 'package:analyzer/src/summary/idl.dart';
import 'package:analyzer/src/summary/name_filter.dart';
/**
* Create a [LinkedLibraryBuilder] corresponding to the given [definingUnitUri]
* and [definingUnit], which should be the defining compilation unit for a
* library. Compilation units referenced by the defining compilation unit via
* `part` declarations will be retrieved using [getPart]. Public namespaces
* for libraries referenced by the defining compilation unit via `import`
* declarations (and files reachable from them via `part` and `export`
* declarations) will be retrieved using [getImport].
*/
LinkedLibraryBuilder prelink(
String definingUnitUri,
UnlinkedUnit definingUnit,
GetPartCallback getPart,
GetImportCallback getImport,
GetDeclaredVariable getDeclaredVariable) {
return new _Prelinker(definingUnitUri, definingUnit, getPart, getImport,
getDeclaredVariable)
.prelink();
}
/**
* Return the raw string value of the variable with the given [name],
* or `null` of the variable is not defined.
*/
typedef String GetDeclaredVariable(String name);
/**
* Type of the callback used by the prelinker to obtain public namespace
* information about libraries with the given [absoluteUri] imported by the
* library to be prelinked (and the transitive closure of parts and exports
* reachable from those libraries).
*
* If no file exists at the given uri, `null` should be returned.
*/
typedef UnlinkedPublicNamespace GetImportCallback(String absoluteUri);
/**
* Type of the callback used by the prelinker to obtain unlinked summaries of
* part files of the library to be prelinked.
*
* If no file exists at the given uri, `null` should be returned.
*/
typedef UnlinkedUnit GetPartCallback(String absoluteUri);
/**
* A [_Meaning] representing a class.
*/
class _ClassMeaning extends _Meaning {
final _Namespace namespace;
_ClassMeaning(int unit, int dependency, int numTypeParameters, this.namespace)
: super(unit, ReferenceKind.classOrEnum, dependency, numTypeParameters);
}
/**
* A node in computing exported namespaces.
*/
class _ExportNamespace {
static int nextId = 0;
/**
* The export namespace, full (with all exports included), or partial (with
* public namespace, and only some of the exports included).
*/
final _Namespace namespace;
/**
* This field is set to non-zero when we start computing the export namespace
* for the corresponding library, and is set back to zero when we finish
* computation.
*/
int id = 0;
/**
* Whether the [namespace] is full, so we don't need chasing exports.
*/
bool isFull = false;
_ExportNamespace(this.namespace);
}
/**
* A [_Meaning] stores all the information necessary to find the declaration
* referred to by a name in a namespace.
*/
class _Meaning {
/**
* Which unit in the dependent library contains the declared entity.
*/
final int unit;
/**
* The kind of entity being referred to.
*/
final ReferenceKind kind;
/**
* Which of the dependencies of the library being prelinked contains the
* declared entity.
*/
final int dependency;
/**
* If the entity being referred to is generic, the number of type parameters
* it accepts. Otherwise zero.
*/
final int numTypeParameters;
_Meaning(this.unit, this.kind, this.dependency, this.numTypeParameters);
/**
* Encode this [_Meaning] as a [LinkedExportName], using the given [name].
*/
LinkedExportName encodeExportName(String name) {
return new LinkedExportNameBuilder(
name: name, dependency: dependency, unit: unit, kind: kind);
}
/**
* Encode this [_Meaning] as a [LinkedReference].
*/
LinkedReferenceBuilder encodeReference() {
return new LinkedReferenceBuilder(
unit: unit,
kind: kind,
dependency: dependency,
numTypeParameters: numTypeParameters);
}
}
/**
* Mapping from names to corresponding unique [_Meaning]s.
*/
class _Namespace {
final Set<String> namesWithConflictingDefinitions = new Set<String>();
final Set<String> libraryNames = new Set<String>();
final Map<String, _Meaning> map = <String, _Meaning>{};
/**
* Return the [_Meaning] of the name, or `null` is not defined.
*/
_Meaning operator [](String name) {
return map[name];
}
/**
* Define that the [name] has the given [value]. If the [name] already been
* defined with a different value, then it becomes undefined.
*/
void add(String name, _Meaning value) {
// Already determined to be a conflict.
if (namesWithConflictingDefinitions.contains(name)) {
return;
}
_Meaning currentValue = map[name];
if (currentValue == null) {
map[name] = value;
} else if (currentValue == value) {
// The same value, ignore.
} else {
// A conflict, remember it, and un-define the name.
namesWithConflictingDefinitions.add(name);
map.remove(name);
}
}
/**
* Return `true` if the [name] was defined before [rememberLibraryNames]
* invocation.
*/
bool definesLibraryName(String name) => libraryNames.contains(name);
/**
* Return `true` if the [name] is already defined.
*/
bool definesName(String name) => map.containsKey(name);
/**
* Apply [f] to each name-meaning pair.
*/
void forEach(void f(String key, _Meaning value)) {
map.forEach(f);
}
/**
* This method should be invoked after defining all names that are defined
* in a library, before defining imported names.
*/
void rememberLibraryNames() {
libraryNames.addAll(map.keys);
}
}
/**
* A [_Meaning] representing a prefix introduced by an import directive.
*/
class _PrefixMeaning extends _Meaning {
final _Namespace namespace = new _Namespace();
_PrefixMeaning() : super(0, ReferenceKind.prefix, 0, 0);
}
/**
* Helper class containing temporary data structures needed to prelink a single
* library.
*/
class _Prelinker {
final String definingUnitUri;
final UnlinkedUnit definingUnit;
final GetPartCallback getPart;
final GetImportCallback getImport;
final GetDeclaredVariable getDeclaredVariable;
/**
* Cache of values returned by [getImport].
*/
final Map<String, UnlinkedPublicNamespace> importCache =
<String, UnlinkedPublicNamespace>{};
/**
* Cache of values returned by [getPart].
*/
final Map<String, UnlinkedUnit> partCache = <String, UnlinkedUnit>{};
/**
* Names defined inside the library being prelinked.
*/
final _Namespace privateNamespace = new _Namespace()
..add('dynamic', new _Meaning(0, ReferenceKind.classOrEnum, 0, 0))
..add('void', new _Meaning(0, ReferenceKind.classOrEnum, 0, 0));
/**
* List of dependencies of the library being prelinked. This will be output
* to [LinkedLibrary.dependencies].
*/
final List<LinkedDependencyBuilder> dependencies =
<LinkedDependencyBuilder>[];
/**
* Map from the absolute URI of a dependent library to the index of the
* corresponding entry in [dependencies].
*/
final Map<String, int> uriToDependency = <String, int>{};
/**
* List of public namespaces corresponding to each entry in [dependencies].
*/
final List<_Namespace> dependencyToPublicNamespace = <_Namespace>[];
/**
* Map from absolute URI of a library to its export namespace.
*/
final Map<String, _ExportNamespace> exportNamespaces = {};
_Prelinker(this.definingUnitUri, this.definingUnit, this.getPart,
this.getImport, this.getDeclaredVariable) {
partCache[definingUnitUri] = definingUnit;
importCache[definingUnitUri] = definingUnit.publicNamespace;
}
/**
* Compute the public namespace for the library whose URI is reachable from
* [definingUnit] via [absoluteUri], by aggregating together public namespace
* information from all of its parts.
*/
_Namespace aggregatePublicNamespace(String absoluteUri) {
if (uriToDependency.containsKey(absoluteUri)) {
return dependencyToPublicNamespace[uriToDependency[absoluteUri]];
}
assert(dependencies.length == dependencyToPublicNamespace.length);
int dependency = dependencies.length;
uriToDependency[absoluteUri] = dependency;
List<String> unitUris = getUnitUris(absoluteUri);
LinkedDependencyBuilder linkedDependency = new LinkedDependencyBuilder(
uri: absoluteUri,
parts: unitUris.skip(1).map((uri) => uri ?? '').toList());
dependencies.add(linkedDependency);
_Namespace aggregated = new _Namespace();
for (int unitNum = 0; unitNum < unitUris.length; unitNum++) {
String unitUri = unitUris[unitNum];
UnlinkedPublicNamespace importedNamespace = getImportCached(unitUri);
if (importedNamespace == null) {
continue;
}
for (UnlinkedPublicName name in importedNamespace.names) {
if (name.kind == ReferenceKind.classOrEnum) {
_Namespace namespace = new _Namespace();
name.members.forEach((executable) {
namespace.add(
executable.name,
new _Meaning(
unitNum, executable.kind, 0, executable.numTypeParameters));
});
aggregated.add(
name.name,
new _ClassMeaning(
unitNum, dependency, name.numTypeParameters, namespace));
} else {
aggregated.add(
name.name,
new _Meaning(
unitNum, name.kind, dependency, name.numTypeParameters));
}
}
}
aggregated.rememberLibraryNames();
dependencyToPublicNamespace.add(aggregated);
return aggregated;
}
/**
* Compute the export namespace for the library whose URI is reachable from
* [definingUnit] via [absoluteUri], by aggregating together public namespace
* information from the library and the transitive closure of its exports.
*/
_Namespace computeExportNamespace(String absoluteUri) {
int firstCycleIdOfLastCall = 0;
_Namespace chaseExports(String absoluteUri) {
_ExportNamespace exportNamespace = getExportNamespace(absoluteUri);
// If the export namespace is ready, return it.
if (exportNamespace.isFull) {
firstCycleIdOfLastCall = 0;
return exportNamespace.namespace;
}
// If we are computing the export namespace for this library, and we
// reached here, then we found a cycle.
if (exportNamespace.id != 0) {
firstCycleIdOfLastCall = exportNamespace.id;
return null;
}
// Give each library a unique identifier.
exportNamespace.id = _ExportNamespace.nextId++;
// Append from exports.
int firstCycleId = 0;
UnlinkedPublicNamespace publicNamespace = getImportCached(absoluteUri);
if (publicNamespace != null) {
for (UnlinkedExportPublic export in publicNamespace.exports) {
String unlinkedExportUri =
_selectUri(export.uri, export.configurations);
String exportUri = resolveUri(absoluteUri, unlinkedExportUri);
if (exportUri != null) {
NameFilter filter =
new NameFilter.forUnlinkedCombinators(export.combinators);
_Namespace exported = chaseExports(exportUri);
exported?.forEach((String name, _Meaning meaning) {
if (filter.accepts(name) &&
!exportNamespace.namespace.definesLibraryName(name)) {
exportNamespace.namespace.add(name, meaning);
}
});
if (firstCycleIdOfLastCall != 0) {
if (firstCycleId == 0 || firstCycleId > firstCycleIdOfLastCall) {
firstCycleId = firstCycleIdOfLastCall;
}
}
}
}
}
// If this library is the first component of the cycle, then we are at
// the beginning of this cycle, and combination of partial export
// namespaces of other exported libraries and declarations of this
// library is the full export namespace of this library.
if (firstCycleId != 0 && firstCycleId == exportNamespace.id) {
firstCycleId = 0;
}
// We're done with this library, successfully or not.
exportNamespace.id = 0;
// If no cycle detected in exports, mark the export namespace as full.
if (firstCycleId == 0) {
exportNamespace.isFull = true;
}
// Return the full or partial result.
firstCycleIdOfLastCall = firstCycleId;
return exportNamespace.namespace;
}
_ExportNamespace.nextId = 1;
return chaseExports(absoluteUri);
}
/**
* Extract all the names defined in [unit] (which is the [unitNum]th unit in
* the library being prelinked) and store them in [privateNamespace].
* Excludes names introduced by `import` statements.
*/
void extractPrivateNames(UnlinkedUnit unit, int unitNum) {
for (UnlinkedClass cls in unit.classes) {
_Namespace namespace = new _Namespace();
cls.fields.forEach((field) {
if (field.isStatic && field.isConst) {
namespace.add(field.name,
new _Meaning(unitNum, ReferenceKind.propertyAccessor, 0, 0));
}
});
cls.executables.forEach((executable) {
ReferenceKind kind = null;
if (executable.kind == UnlinkedExecutableKind.constructor) {
kind = ReferenceKind.constructor;
} else if (executable.kind == UnlinkedExecutableKind.functionOrMethod &&
executable.isStatic) {
kind = ReferenceKind.method;
} else if (executable.kind == UnlinkedExecutableKind.getter &&
executable.isStatic) {
kind = ReferenceKind.propertyAccessor;
}
if (kind != null && executable.name.isNotEmpty) {
namespace.add(executable.name,
new _Meaning(unitNum, kind, 0, executable.typeParameters.length));
}
});
privateNamespace.add(cls.name,
new _ClassMeaning(unitNum, 0, cls.typeParameters.length, namespace));
}
for (UnlinkedEnum enm in unit.enums) {
_Namespace namespace = new _Namespace();
enm.values.forEach((UnlinkedEnumValue value) {
namespace.add(value.name,
new _Meaning(unitNum, ReferenceKind.propertyAccessor, 0, 0));
});
namespace.add('values',
new _Meaning(unitNum, ReferenceKind.propertyAccessor, 0, 0));
privateNamespace.add(
enm.name, new _ClassMeaning(unitNum, 0, 0, namespace));
}
for (UnlinkedExecutable executable in unit.executables) {
privateNamespace.add(
executable.name,
new _Meaning(
unitNum,
executable.kind == UnlinkedExecutableKind.functionOrMethod
? ReferenceKind.topLevelFunction
: ReferenceKind.topLevelPropertyAccessor,
0,
executable.typeParameters.length));
}
for (UnlinkedTypedef typedef in unit.typedefs) {
ReferenceKind kind;
switch (typedef.style) {
case TypedefStyle.functionType:
kind = ReferenceKind.typedef;
break;
case TypedefStyle.genericFunctionType:
kind = ReferenceKind.genericFunctionTypedef;
break;
}
assert(kind != null);
privateNamespace.add(typedef.name,
new _Meaning(unitNum, kind, 0, typedef.typeParameters.length));
}
for (UnlinkedVariable variable in unit.variables) {
privateNamespace.add(variable.name,
new _Meaning(unitNum, ReferenceKind.topLevelPropertyAccessor, 0, 0));
if (!(variable.isConst || variable.isFinal)) {
privateNamespace.add(
variable.name + '=',
new _Meaning(
unitNum, ReferenceKind.topLevelPropertyAccessor, 0, 0));
}
}
}
/**
* Filter the export namespace for the library whose URI is reachable the
* given [absoluteUri], retaining only those names accepted by
* [combinators], and store the resulting names in [result]. Names that
* already exist in [result] are not overwritten.
*/
void filterExportNamespace(String absoluteUri,
List<UnlinkedCombinator> combinators, _Namespace result) {
_Namespace exportNamespace = computeExportNamespace(absoluteUri);
if (result == null) {
// This can happen if the import prefix was shadowed by a local name, so
// the imported symbols are inaccessible.
return;
}
NameFilter filter = new NameFilter.forUnlinkedCombinators(combinators);
exportNamespace.forEach((String name, _Meaning meaning) {
if (filter.accepts(name) && !result.definesLibraryName(name)) {
result.add(name, meaning);
}
});
}
/**
* Return the [_ExportNamespace] for the library with the given [absoluteUri].
* The export namespace might be full (will all exports included), or
* partial (with public namespace, and only some of the exports included).
*/
_ExportNamespace getExportNamespace(String absoluteUri) {
_ExportNamespace exportNamespace = exportNamespaces[absoluteUri];
if (exportNamespace == null) {
_Namespace publicNamespace = aggregatePublicNamespace(absoluteUri);
exportNamespace = new _ExportNamespace(publicNamespace);
exportNamespaces[absoluteUri] = exportNamespace;
}
return exportNamespace;
}
/**
* Wrapper around [getImport] that caches the return value in [importCache].
*/
UnlinkedPublicNamespace getImportCached(String absoluteUri) {
return importCache.putIfAbsent(absoluteUri, () => getImport(absoluteUri));
}
/**
* Wrapper around [getPart] that caches the return value in [partCache] and
* updates [importCache] appropriately.
*/
UnlinkedUnit getPartCached(String absoluteUri) {
return partCache.putIfAbsent(absoluteUri, () {
UnlinkedUnit unit = getPart(absoluteUri);
importCache[absoluteUri] = unit?.publicNamespace;
return unit;
});
}
/**
* Compute the set of absolute URIs of all the compilation units in the
* library whose URI is reachable from [definingUnit] via [absoluteUri].
*/
List<String> getUnitUris(String absoluteUri) {
List<String> result = <String>[absoluteUri];
UnlinkedPublicNamespace publicNamespace = getImportCached(absoluteUri);
if (publicNamespace != null) {
result.addAll(publicNamespace.parts.map((String uri) {
return resolveUri(absoluteUri, uri);
}));
}
return result;
}
/**
* Process a single `import` declaration in the library being prelinked. The
* return value is the index of the imported library in [dependencies].
*/
int handleImport(UnlinkedImport import) {
String unlinkedUri = import.isImplicit
? 'dart:core'
: _selectUri(import.uri, import.configurations);
String absoluteUri = resolveUri(definingUnitUri, unlinkedUri);
_Namespace targetNamespace = null;
if (import.prefixReference != 0) {
// The name introduced by an import declaration can't have a prefix of
// its own.
assert(
definingUnit.references[import.prefixReference].prefixReference == 0);
String prefix = definingUnit.references[import.prefixReference].name;
_Meaning prefixMeaning = privateNamespace[prefix];
if (prefixMeaning is _PrefixMeaning) {
targetNamespace = prefixMeaning.namespace;
}
} else {
targetNamespace = privateNamespace;
}
filterExportNamespace(absoluteUri, import.combinators, targetNamespace);
return uriToDependency[absoluteUri];
}
/**
* Produce a [LinkedUnit] for the given [unit], by resolving every one of
* its references.
*/
LinkedUnitBuilder linkUnit(UnlinkedUnit unit) {
if (unit == null) {
return new LinkedUnitBuilder();
}
Map<int, _Namespace> prefixNamespaces = <int, _Namespace>{};
List<LinkedReferenceBuilder> references = <LinkedReferenceBuilder>[];
for (int i = 0; i < unit.references.length; i++) {
UnlinkedReference reference = unit.references[i];
_Namespace namespace;
if (reference.prefixReference == 0) {
namespace = privateNamespace;
} else {
// Prefix references must always point backward.
assert(reference.prefixReference < i);
namespace = prefixNamespaces[reference.prefixReference];
// Expressions like 'a.b.c.d' cannot be prelinked.
namespace ??= new _Namespace();
}
_Meaning meaning = namespace[reference.name];
if (meaning != null) {
if (meaning is _PrefixMeaning) {
prefixNamespaces[i] = meaning.namespace;
} else if (meaning is _ClassMeaning) {
prefixNamespaces[i] = meaning.namespace;
}
references.add(meaning.encodeReference());
} else {
references
.add(new LinkedReferenceBuilder(kind: ReferenceKind.unresolved));
}
}
return new LinkedUnitBuilder(references: references);
}
/**
* Form the [LinkedLibrary] for the [definingUnit] that was passed to the
* constructor.
*/
LinkedLibraryBuilder prelink() {
aggregatePublicNamespace(definingUnitUri);
// Gather up the unlinked summaries for all the compilation units in the
// library.
List<String> unitUris = getUnitUris(definingUnitUri);
List<UnlinkedUnit> units = unitUris.map(getPartCached).toList();
// Create the private namespace for the library by gathering all the names
// defined in its compilation units.
for (int unitNum = 0; unitNum < units.length; unitNum++) {
UnlinkedUnit unit = units[unitNum];
if (unit != null) {
extractPrivateNames(unit, unitNum);
}
}
// Fill in exported names. This must be done before filling in prefixes
// defined in import declarations, because prefixes shouldn't shadow
// exports.
List<LinkedExportNameBuilder> exportNames = <LinkedExportNameBuilder>[];
computeExportNamespace(definingUnitUri)
.forEach((String name, _Meaning meaning) {
if (!privateNamespace.definesName(name)) {
exportNames.add(meaning.encodeExportName(name));
}
});
// Fill in prefixes defined in import declarations.
for (UnlinkedImport import in units[0].imports) {
if (import.prefixReference != 0) {
String name = units[0].references[import.prefixReference].name;
if (!privateNamespace.definesName(name)) {
privateNamespace.add(name, new _PrefixMeaning());
}
}
}
// All the names defined so far are library local, they take precedence
// over anything imported from other libraries.
privateNamespace.rememberLibraryNames();
// Fill in imported and exported names.
List<int> importDependencies =
definingUnit.imports.map(handleImport).toList();
List<int> exportDependencies = definingUnit.publicNamespace.exports
.map((UnlinkedExportPublic exp) {
String unlinkedUri = _selectUri(exp.uri, exp.configurations);
String absoluteUri = resolveUri(definingUnitUri, unlinkedUri);
return uriToDependency[absoluteUri];
})
.where((dependency) => dependency != null)
.toList();
// Link each compilation unit.
List<LinkedUnitBuilder> linkedUnits = units.map(linkUnit).toList();
return new LinkedLibraryBuilder(
units: linkedUnits,
dependencies: dependencies,
importDependencies: importDependencies,
exportDependencies: exportDependencies,
exportNames: exportNames,
numPrelinkedDependencies: dependencies.length);
}
/**
* Resolve [relativeUri] relative to [containingUri]. Return `null` if
* [relativeUri] is invalid or empty, so cannot be resolved.
*/
String resolveUri(String containingUri, String relativeUri) {
if (relativeUri == '') {
return null;
}
try {
Uri containingUriObj = Uri.parse(containingUri);
Uri relativeUriObj = Uri.parse(relativeUri);
return resolveRelativeUri(containingUriObj, relativeUriObj).toString();
} on FormatException {
return null;
}
}
/**
* Return the URI of the first configuration from the given [configurations]
* which condition is satisfied, or the [defaultUri].
*/
String _selectUri(
String defaultUri, List<UnlinkedConfiguration> configurations) {
for (UnlinkedConfiguration configuration in configurations) {
if (getDeclaredVariable(configuration.name) == configuration.value) {
return configuration.uri;
}
}
return defaultUri;
}
}