blob: a109325a4246b589a46ebb384af0219d9f4311cb [file] [log] [blame]
// Copyright (c) 2017, 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 'dart:collection';
import 'package:collection/collection.dart';
import 'package:kernel/core_types.dart';
import 'package:kernel/kernel.dart' hide Pattern;
import 'constants.dart';
Never throwUnsupportedInvalidType(InvalidType type) => throw UnsupportedError(
'Unsupported invalid type $type (${type.runtimeType}).');
Never throwUnsupportedAuxiliaryType(AuxiliaryType type) =>
throw UnsupportedError(
'Unsupported auxiliary type $type (${type.runtimeType}).');
Constructor? unnamedConstructor(Class c) =>
c.constructors.firstWhereOrNull((c) => c.name.text == '');
/// Returns the enclosing library for reference [node].
Library getLibrary(NamedNode node) {
for (TreeNode? n = node; n != null; n = n.parent) {
if (n is Library) return n;
}
throw UnsupportedError('Could not find a containing library for $node');
}
final Pattern _syntheticTypeCharacters = RegExp('[&^#.|]');
String escapeIdentifier(String identifier) {
// Remove the special characters used to encode mixin application class names
// and extension method / parameter names which are legal in Kernel, but not
// in JavaScript.
//
// Note, there is an implicit assumption here that we won't have
// collisions since everything is mapped to \$. That may work out fine given
// how these are synthesized, but may need to revisit.
return identifier.replaceAll(_syntheticTypeCharacters, r'$');
}
/// Returns the escaped name for class [node].
///
/// The caller of this function has to make sure that this name is unique in
/// the current scope.
///
/// In the current encoding, generic classes are generated in a function scope
/// which avoids name clashes of the escaped class name.
String getLocalClassName(Class node) => escapeIdentifier(node.name);
/// Returns the escaped name for the type parameter [node].
///
/// In the current encoding, generic classes are generated in a function scope
/// which avoids name clashes of the escaped parameter name.
String getTypeParameterName(
/* TypeParameter | StructuralParameter */ Object node) {
assert(node is TypeParameter || node is StructuralParameter);
if (node is TypeParameter) {
return escapeIdentifier(node.name!);
} else {
node as StructuralParameter;
return escapeIdentifier(node.name!);
}
}
String getTopLevelName(NamedNode n) {
if (n is Procedure) return n.name.text;
if (n is Class) return n.name;
if (n is Typedef) return n.name;
if (n is Field) return n.name.text;
return n.reference.canonicalName!.name;
}
/// Given an annotated [node] and a [test] function, returns the first matching
/// constant valued annotation.
///
/// For example if we had the ClassDeclaration node for `FontElement`:
///
/// @js.JS('HTMLFontElement')
/// @deprecated
/// class FontElement { ... }
///
/// We could match `@deprecated` with a test function like:
///
/// (v) => v.type.name == 'Deprecated' && v.type.element.library.isDartCore
///
Expression? findAnnotation(TreeNode node, bool Function(Expression) test) {
List<Expression> annotations;
if (node is Class) {
annotations = node.annotations;
} else if (node is Typedef) {
annotations = node.annotations;
} else if (node is Procedure) {
annotations = node.annotations;
} else if (node is Member) {
annotations = node.annotations;
} else if (node is Library) {
annotations = node.annotations;
} else {
return null;
}
return annotations.firstWhereOrNull(test);
}
/// Returns true if [value] represents an annotation for class [className] in
/// "dart:" library [libraryName].
bool isBuiltinAnnotation(
Expression value, String libraryName, String className) {
var c = getAnnotationClass(value);
if (c != null && c.name == className) {
var uri = c.enclosingLibrary.importUri;
return uri.isScheme('dart') && uri.path == libraryName;
}
return false;
}
/// Gets the class of the instance referred to by metadata annotation [node].
///
/// For example:
///
/// - `@JS()` would return the "JS" class in "dart:_js_annotations".
/// - `@anonymous` would return the "_Anonymous" class in
/// "dart:_js_annotations".
///
/// This function works regardless of whether the CFE is evaluating constants,
/// or whether the constant is a field reference (such as "anonymous" above).
Class? getAnnotationClass(Expression node) {
if (node is ConstantExpression) {
var constant = node.constant;
if (constant is InstanceConstant) return constant.classNode;
} else if (node is ConstructorInvocation) {
return node.target.enclosingClass;
} else if (node is StaticGet) {
var type = node.target.getterType;
if (type is InterfaceType) return type.classNode;
}
return null;
}
/// Returns true if [name] is an operator method that is available on primitive
/// types (`int`, `double`, `num`, `String`, `bool`).
///
/// This does not include logical operators that cannot be user-defined
/// (`!`, `&&` and `||`).
bool isOperatorMethodName(String name) {
switch (name) {
case '==':
case '~':
case '^':
case '|':
case '&':
case '>>':
case '<<':
case '>>>':
case '+':
case 'unary-':
case '-':
case '*':
case '/':
case '~/':
case '>':
case '<':
case '>=':
case '<=':
case '%':
return true;
}
return false;
}
bool isFromEnvironmentInvocation(CoreTypes coreTypes, StaticInvocation node) {
var target = node.target;
return node.isConst &&
target.name.text == 'fromEnvironment' &&
target.enclosingLibrary == coreTypes.coreLibrary;
}
List<Class> getSuperclasses(Class? c) {
var result = <Class>[];
var visited = HashSet<Class>();
while (c != null && visited.add(c)) {
for (var m = c.mixedInClass; m != null; m = m.mixedInClass) {
result.add(m);
}
var superclass = c.superclass;
if (superclass == null) break;
result.add(superclass);
c = superclass;
}
return result;
}
List<Class> getImmediateSuperclasses(Class c) {
var result = <Class>[];
var m = c.mixedInClass;
if (m != null) result.add(m);
var s = c.superclass;
if (s != null) result.add(s);
return result;
}
Expression? getInvocationReceiver(InvocationExpression node) {
if (node is InstanceInvocation) {
return node.receiver;
} else if (node is DynamicInvocation) {
return node.receiver;
} else if (node is FunctionInvocation) {
return node.receiver;
} else if (node is LocalFunctionInvocation) {
return VariableGet(node.variable);
}
return null;
}
bool isInlineJS(Member e) =>
e is Procedure && _isProcedureFromForeignHelper('JS', e);
/// Returns `true` if [p] is the procedure named [name] from the
/// 'dart:_foreign_helper' library.
bool _isProcedureFromForeignHelper(String name, Procedure p) =>
p.name.text == name &&
p.enclosingLibrary.importUri.toString() == 'dart:_foreign_helper';
/// Whether the parameter [p] is covariant (either explicitly `covariant` or
/// implicitly due to generics) and needs a check for soundness.
bool isCovariantParameter(VariableDeclaration p) {
return p.isCovariantByDeclaration || p.isCovariantByClass;
}
/// Whether the field [p] is covariant (either explicitly `covariant` or
/// implicitly due to generics) and needs a check for soundness.
bool isCovariantField(Field f) {
return f.isCovariantByDeclaration || f.isCovariantByClass;
}
/// Returns true iff this factory constructor just throws [UnsupportedError]/
///
/// `dart:html` has many of these.
bool isUnsupportedFactoryConstructor(Procedure node) {
if (node.name.isPrivate && node.enclosingLibrary.importUri.isScheme('dart')) {
var body = node.function.body;
if (body is Block) {
var statements = body.statements;
if (statements.length == 1) {
var statement = statements[0];
if (statement is ExpressionStatement) {
var expr = statement.expression;
if (expr is Throw) {
var error = expr.expression;
// HTML adds a lot of private constructors that are unreachable.
// Skip these.
return isBuiltinAnnotation(error, 'core', 'UnsupportedError');
}
}
}
}
}
return false;
}
/// Gets the real supertype of [c] and the list of [mixins] in reverse
/// application order (mixins will appear before ones they override).
///
/// This is used to ignore synthetic mixin application classes.
///
// TODO(jmesserly): consider replacing this with Kernel's mixin unrolling
Class getSuperclassAndMixins(Class c, List<Class> mixins) {
assert(mixins.isEmpty);
assert(c.superclass != null);
var mixedInClass = c.mixedInClass;
if (mixedInClass != null) mixins.add(mixedInClass);
var sc = c.superclass!;
for (; sc.isAnonymousMixin; sc = sc.superclass!) {
mixedInClass = sc.mixedInClass;
if (mixedInClass != null) mixins.add(sc.mixedInClass!);
}
return sc;
}
/// Returns true if a switch statement contains any continues with a label.
bool hasLabeledContinue(SwitchStatement node) {
var visitor = LabelContinueFinder();
node.accept(visitor);
return visitor.found;
}
class LabelContinueFinder extends RecursiveVisitor {
var found = false;
void visit(Statement? s) {
if (!found && s != null) s.accept(this);
}
@override
void visitContinueSwitchStatement(ContinueSwitchStatement node) =>
found = true;
}
/// Returns `true` if any of [n]s children are a [FunctionExpression] node.
bool containsFunctionExpression(Node n) {
var visitor = _FunctionExpressionFinder.instance;
visitor.found = false;
n.accept(visitor);
return visitor.found;
}
class _FunctionExpressionFinder extends RecursiveVisitor {
var found = false;
static final instance = _FunctionExpressionFinder();
@override
void visitFunctionExpression(FunctionExpression node) => found = true;
}
/// Whether [member] is declared native, as in:
///
/// void foo() native;
///
/// This syntax is only allowed in sdk libraries and native tests.
bool isNative(Member member) =>
// The CFE represents `native` members with the `external` bit and with an
// internal @ExternalName annotation as a marker.
member.isExternal && member.annotations.any(_isNativeMarkerAnnotation);
bool _isNativeMarkerAnnotation(Expression annotation) {
if (annotation is ConstantExpression) {
var constant = annotation.constant;
if (constant is InstanceConstant &&
constant.classNode.name == 'ExternalName' &&
_isDartInternal(constant.classNode.enclosingLibrary.importUri)) {
return true;
}
}
return false;
}
bool _isDartInternal(Uri uri) =>
uri.isScheme('dart') && uri.path == '_internal';
/// Collects all `TypeParameter`s from the `TypeParameterType`s present in the
/// visited `DartType`.
class TypeParameterFinder extends RecursiveVisitor {
final _found = <TypeParameter>{};
static TypeParameterFinder? _instance;
TypeParameterFinder._();
factory TypeParameterFinder.instance() {
if (_instance != null) return _instance!;
return TypeParameterFinder._();
}
Set<TypeParameter> find(DartType type) {
_found.clear();
type.accept(this);
return _found;
}
@override
void visitTypeParameterType(TypeParameterType node) =>
_found.add(node.parameter);
}
/// Collects [InterfaceType] nodes that appear in in a DartType.
class InterfaceTypeExtractor extends RecursiveVisitor {
final Set<InterfaceType> _found = {};
@override
void visitInterfaceType(InterfaceType node) {
_found.add(node);
node.visitChildren(this);
}
/// Returns all [InterfaceType]s that appear in [type].
Iterable<InterfaceType> extract(DartType type) {
type.accept(this);
return _found;
}
}
/// Replaces [VariableGet] nodes with a different expression defined by a
/// replacement map.
class VariableGetReplacer extends Transformer {
final Map<VariableDeclaration, Expression> _replacements;
VariableGetReplacer(this._replacements);
@override
TreeNode visitVariableGet(VariableGet node) {
var replacement = _replacements[node.variable];
return replacement ?? node;
}
}
/// Tests a [StaticInvocation] node to determine if it would be safe to inline.
///
/// Each static invocation should be inspected individually as this class only
/// inspects the body of a given invocation target, and does not recurse
/// transitively into the bodies of other invocations it finds.
///
/// The determination of what is safe to inline is specifically targeting simple
/// methods in the dart:_rti library and has not been validated to use as an
/// inliner for static methods from any other libraries. Instead of inlining by
/// introducing let variables that preserve the evaluation order of the call,
/// only code where it is safe to replace the argument of the call at the
/// place where it used is considered suitable.
///
/// The body of the target method may only contain simple expressions known to
/// have no side-effects like null, bool or string literals, constants, enum
/// values, and variable accesses. Additionally some static invocations from the
/// runtime libraries are permitted in the body when they have been manually
/// inspected for side effects and annotated as safe with
/// `@pragma('ddc:trust-inline`). After the last method argument has been used,
/// this restriction is weakened to allow any static invocations to appear.
class BasicInlineTester extends TreeVisitorDefault<bool> {
/// The constants used to access constant evaluation for annotations.
final DevCompilerConstants _constants;
/// The order that the arguments are expected to used in the body of the
/// function for it to be considered safe for inlining.
///
/// This is essential to preserve the execution order of the expressions
/// passed as arguments.
List<VariableDeclaration>? _expectedArgumentOrder;
/// The position in [_expectedArgumentOrder] to begin looking for the next
/// used argument.
int _nextArgIndex = 0;
/// Returns `true` if uses of all the expected arguments have already been
/// seen by the visitor.
bool get _allArgumentsUsed => _nextArgIndex >= _expectedArgumentOrder!.length;
BasicInlineTester(this._constants);
/// Returns `true` when [possibleInline] is considered simple enough to
/// be safe to inline.
///
/// The considerations for inlining are designed specifically to target select
/// invocations in the dart:_rti library.
bool canInline(FunctionNode possibleInline) {
if (possibleInline.namedParameters.isNotEmpty ||
possibleInline.typeParameters.isNotEmpty ||
possibleInline.positionalParameters.length !=
possibleInline.requiredParameterCount) {
// Only consider functions with required positional arguments.
return false;
}
final body = possibleInline.body;
// No code available here to inline.
if (body == null) return false;
_expectedArgumentOrder = possibleInline.positionalParameters;
_nextArgIndex = 0;
// Important to note that the static invocation being considered for inline
// is not visited. Instead the body of the target function being invoked is
// visited to determine if inlining is feasible. Any other static
// invocations appearing within that body *will* be visited.
final result = body.accept(this);
// Avoid retaining any of the arguments after returning.
_expectedArgumentOrder = null;
return result;
}
/// Returns `true` when [node] is annotated with
/// `@pragma('ddc:trust-inline`)`.
bool _hasTrustInlinePragma(NamedNode node) {
var annotation = findAnnotation(node, (e) {
if (!isBuiltinAnnotation(e, 'core', 'pragma')) return false;
var name = _constants.getFieldValueFromAnnotation(e, 'name') as String?;
return name == 'ddc:trust-inline';
});
return annotation != null;
}
@override
bool defaultTreeNode(Node _) => false;
@override
bool visitReturnStatement(ReturnStatement node) {
var returnExpression = node.expression;
return returnExpression == null ? false : returnExpression.accept(this);
}
@override
bool visitBlock(Block node) {
if (node.statements.length != 1) return false;
return node.statements.single.accept(this);
}
@override
bool visitStaticInvocation(StaticInvocation node) {
// Reaching this visitor means that a static invocation appears in the body
// of the function being evaluated for inlining.
var positionalArgs = node.arguments.positional;
if (isInlineJS(node.target)) {
// Ensure JS expressions do not span multiple statements. Since these are
// inlined elsewhere we don't want to accidentally combine multiple
// Javascript statements into a position where they don't belong. Instead
// of inspecting if it is valid, just reject any source templates that
// contain ';' characters.
var codeLiteral = positionalArgs[1];
String? code;
if (codeLiteral is StringLiteral) {
code = codeLiteral.value;
} else if (codeLiteral is ConstantExpression) {
var constant = codeLiteral.constant;
if (constant is StringConstant) {
code = constant.value;
}
}
if (code == null || code.contains(';')) return false;
}
// Inspect the arguments.
for (var argument in positionalArgs) {
if (!argument.accept(this)) return false;
}
// While all of the uses of the arguments are still being discovered,
// only allow additional static invocations explicitly annotated as
// trusted. This prevents inlining a static invocation that could
// change the evaluation order of the expressions passed as arguments.
// Example:
// ```
// echo(s) {
// print(s);
// return s;
// }
//
// dangerous(arg1, arg2) {
// return fn(arg1, echo('third'), arg2);
// }
// ```
// Calls to `dangerous()` should not be inlined without let variables
// because the expression evaluation order would be disrupted:
// ```
// dangerous(echo('first'), echo('second'));
// | |
// V V
// fn(echo('first'), echo('third'), echo('second')) // INVALID!
return _allArgumentsUsed || _hasTrustInlinePragma(node.target);
}
@override
bool visitBoolLiteral(BoolLiteral _) => true;
@override
bool visitNullLiteral(NullLiteral _) => true;
@override
bool visitStringLiteral(StringLiteral _) => true;
@override
bool visitConstantExpression(ConstantExpression _) => true;
@override
bool visitVariableGet(VariableGet node) {
// The variable is an argument of the function to be inlined. Verify it
// appears in an order consistent with the order the arguments appeared
// in the call.
final location =
_expectedArgumentOrder!.indexOf(node.variable, _nextArgIndex);
// Either the variable isn't one of the expected arguments at all, or it is
// appearing out of the expected order.
if (location == -1) return false;
// Advance the start of the expected range past the variable just found to
// ensure the variable can only be used once.
_nextArgIndex = location + 1;
return true;
}
@override
bool visitField(Field node) => node.isEnumElement;
@override
bool visitStaticGet(StaticGet node) {
return node.target.accept(this);
}
}