Add an AST-to-IR conversion stage to the Wolf analysis prototype.
This CL continues pulling a steel thread through the design of Wolf
analysis, by adding a stage that converts from analyzer ASTs to the
Wolf analysis IR. The set of supported instructions is still quite
minimal, so pretty much the only functions that can be handled take
the form `functionName() => literalValue;`. I plan to start adding
more instructions next.
A simple IR interpreter is included, solely for use in unit tests, so
that in the unit tests for AST-to-IR conversion, we can actually
verify that the IR properly reflects the intended semantics.
Includes a minor bug fix to the validator and improved validator
testing.
Also, a README.md file is added, giving an overview of the design of
Wolf analysis and noting that the code as currently experimental.
Change-Id: I1df724a9987c9eed205591cf5f3b8a3ec59cb864
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/335402
Commit-Queue: Paul Berry <paulberry@google.com>
Reviewed-by: Phil Quitslund <pquitslund@google.com>
diff --git a/pkg/analyzer/lib/src/wolf/README.md b/pkg/analyzer/lib/src/wolf/README.md
new file mode 100644
index 0000000..ace37de
--- /dev/null
+++ b/pkg/analyzer/lib/src/wolf/README.md
@@ -0,0 +1,81 @@
+# Wolf Analysis
+
+The code in this directory is __experimental__ and not yet ready for public
+consumption. This file briefly describes its design and intended use.
+
+## Intention
+
+Wolf analysis is intended as a broader, more extensible version of flow analysis
+for use in the analyzer package and the linter. If it proves useful, we may
+expand it to be usable by clients of the analyzer such as code generators.
+
+The reason for making a new type of analysis, rather than extending flow
+analysis, is because the design of flow analysis is heavily constrained in ways
+that make it expensive to modify, maintain, and extend:
+
+- It has to operate in parallel with type inference. This means that it can only
+ make a single pass through the source code, and any time it "looks ahead", the
+ code it is looking at doesn't yet have types. This forces it to make some
+ conservative assumptions when analyzing loops and closures--for example, on
+ entry to a loop, flow analysis knows which variables are written inside the
+ loop body, but it doesn't know the types of the values that are written to
+ those variables; so it has to discard type promotions for all of them. If
+ later analysis shows that the values that were written are compatible with the
+ promoted type, it's too late to go back and update the analysis.
+
+- It can't be improved without bumping the language version (or it will break
+ existing programs).
+
+- All of its analyses must be 100% sound, because they are relied on by later
+ compilation stages. This severly limits its ability to account for human
+ intent, which we would sometimes like to do in lints.
+
+- It has to be shared between the analyzer and the common front end, which means
+ that all of the data structures it acts on must be abstract.
+
+Additionally, flow analysis doesn't understand special behavioral guarantees of
+methods and types declared outside the SDK, and it never looks outside of a
+single method body.
+
+## Design
+
+The design consists of multiple analysis stages:
+
+- AST-to-IR. The analyzer's AST is converted to a stack-based IR (intermediate
+ representation). The proposed IR and the approach for converting to it are
+ described in http://flutter.dev/go/dart-static-analysis-ir.
+
+- Scope analysis. A pass is made through the IR, identifying all the state
+ variables of interest. This includes local variables as well as any other
+ pieces of state that are needed for whatever lints are enabled. This stage
+ records the set of state variables that could potentially be changed inside
+ each loop, block, closure, etc., for use in later analysis stages.
+
+- SSA (single static assignment) analysis. A pass is made through the IR to
+ assign SSA node ids to each state variable and stack value. Queries are
+ generated at points that are of interest to whatever lints are enabled (e.g. a
+ lint that verifies that certain kinds of values are never null will generate
+ queries that ask "is the value represented by this SSA node null?").
+
+- Query solver. Each query generated by SSA analysis is resolved by working
+ backwards through the IR, rewriting it in terms of previous SSA nodes, until a
+ point in the code is reached where the query either can or can't be
+ definitively answered. The mechanism for rewriting queries is inspired by
+ Prolog. Depending on the result of the query, a lint output might be
+ generated.
+
+Other analysis stages might be added in the future. For example, if we find that
+some lints can't be easily expressed in terms of queries, but can still benefit
+from the SSA representation, we may add other analysis stages after SSA
+analysis, to support those lints.
+
+## Support structure
+
+In addition to the pieces above, there is a simple interpreter that executes the
+IR. The interpreter is not intended for production use; it is just sophisticated
+enough to serve as the basis for unit testing the other stages. For example, we
+use it in the unit tests of the AST-to-IR conversion stage, to make sure that
+the output of this stage properly reflects Dart semantics. (If, instead, our
+unit tests simply compared the output of AST-to-IR conversion to an expected
+sequence of instructions, the unit tests would be much more brittle, and there
+would be a much greater risk of human error in reviewing them.)
diff --git a/pkg/analyzer/lib/src/wolf/ir/ast_to_ir.dart b/pkg/analyzer/lib/src/wolf/ir/ast_to_ir.dart
new file mode 100644
index 0000000..beac249
--- /dev/null
+++ b/pkg/analyzer/lib/src/wolf/ir/ast_to_ir.dart
@@ -0,0 +1,141 @@
+// Copyright (c) 2023, 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/dart/ast/ast.dart';
+import 'package:analyzer/dart/ast/visitor.dart';
+import 'package:analyzer/dart/element/element.dart';
+import 'package:analyzer/dart/element/type_provider.dart';
+import 'package:analyzer/dart/element/type_system.dart';
+import 'package:analyzer/src/wolf/ir/coded_ir.dart';
+import 'package:analyzer/src/wolf/ir/ir.dart';
+
+/// Converts [functionBody] to a sequence of IR instructions.
+///
+/// Caller should pass in the [executableElement] for the method or function to
+/// be converted (this is used as a source of type information).
+///
+/// During conversion, progress information will be reported to [eventListener]
+/// (if provided). This should provide enough information to allow the caller to
+/// map individual instructions to the AST nodes that spawned them.
+CodedIRContainer astToIR(
+ ExecutableElement executableElement, FunctionBody functionBody,
+ {required TypeProvider typeProvider,
+ required TypeSystem typeSystem,
+ AstToIREventListener? eventListener}) {
+ eventListener ??= AstToIREventListener();
+ var visitor = _AstToIRVisitor(
+ typeSystem: typeSystem,
+ typeProvider: typeProvider,
+ eventListener: eventListener);
+ eventListener._visitor = visitor;
+ visitor.visitFunctionBody(executableElement, functionBody,
+ isInstanceMember: !executableElement.isStatic);
+ var result = visitor.finish();
+ eventListener._visitor = null;
+ return result;
+}
+
+/// Event listener used by [astToIR] to report progress information.
+///
+/// By itself this class does nothing; the caller of [astToIR] should make a
+/// derived class that overrides one or more of the `on...` methods.
+base class AstToIREventListener {
+ late _AstToIRVisitor? _visitor;
+
+ /// The address of the next instruction that [astToIR] will generate.
+ int get nextInstructionAddress => _visitor!.ir.nextInstructionAddress;
+
+ /// Called when [astToIR] is about to visit an AST node.
+ void onEnterNode(AstNode node) {}
+
+ /// Called after [astToIR] has finished vising an AST node.
+ void onExitNode() {}
+
+ /// Called when [astToIR] has completely finished IR generation.
+ void onFinished(CodedIRContainer ir) {}
+}
+
+class _AstToIRVisitor extends ThrowingAstVisitor<void> {
+ final TypeSystem typeSystem;
+ final TypeProvider typeProvider;
+ final AstToIREventListener eventListener;
+ final ir = CodedIRWriter();
+ late final null_ = ir.encodeLiteral(null);
+
+ _AstToIRVisitor(
+ {required this.typeSystem,
+ required this.typeProvider,
+ required this.eventListener});
+
+ /// Visits [node], reporting progress to [eventListener].
+ void dispatchNode(AstNode node) {
+ eventListener.onEnterNode(node);
+ node.accept(this);
+ eventListener.onExitNode();
+ }
+
+ /// Called by [astToIR] after visiting the code to be analyzed.
+ CodedIRContainer finish() {
+ var result = CodedIRContainer(ir);
+ eventListener.onFinished(result);
+ return result;
+ }
+
+ @override
+ void visitBooleanLiteral(BooleanLiteral node) {
+ ir.literal(ir.encodeLiteral(node.value));
+ // Stack: value
+ }
+
+ @override
+ void visitDoubleLiteral(DoubleLiteral node) {
+ ir.literal(ir.encodeLiteral(node.value));
+ // Stack: value
+ }
+
+ @override
+ void visitExpressionFunctionBody(ExpressionFunctionBody node) {
+ dispatchNode(node.expression);
+ // Stack: expression
+ }
+
+ void visitFunctionBody(ExecutableElement element, FunctionBody body,
+ {required bool isInstanceMember}) {
+ if (isInstanceMember) {
+ throw UnimplementedError('TODO(paulberry): handle instance members');
+ }
+ if (element.parameters.isNotEmpty) {
+ throw UnimplementedError('TODO(paulberry): handle parameters');
+ }
+ var flags = FunctionFlags(
+ async: body.isAsynchronous,
+ generator: body.isGenerator,
+ instance: isInstanceMember);
+ ir.function(ir.encodeType(element.type), flags);
+ // Stack: FUNCTION(flags)
+ dispatchNode(body);
+ // Stack: FUNCTION(flags) returnValue
+ ir.end();
+ // Stack: (empty)
+ }
+
+ @override
+ void visitIntegerLiteral(IntegerLiteral node) {
+ // TODO(paulberry): do we need to handle out of range integers?
+ ir.literal(ir.encodeLiteral(node.value!));
+ // Stack: value
+ }
+
+ @override
+ void visitNullLiteral(NullLiteral node) {
+ ir.literal(null_);
+ // Stack: null
+ }
+
+ @override
+ void visitSimpleStringLiteral(SimpleStringLiteral node) {
+ ir.literal(ir.encodeLiteral(node.value));
+ // Stack: value
+ }
+}
diff --git a/pkg/analyzer/lib/src/wolf/ir/coded_ir.dart b/pkg/analyzer/lib/src/wolf/ir/coded_ir.dart
new file mode 100644
index 0000000..6f4d2db
--- /dev/null
+++ b/pkg/analyzer/lib/src/wolf/ir/coded_ir.dart
@@ -0,0 +1,65 @@
+// Copyright (c) 2023, 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:convert';
+
+import 'package:analyzer/dart/element/type.dart';
+import 'package:analyzer/src/wolf/ir/ir.dart';
+
+/// Container for a sequence of IR instructions, along with auxiliary tables
+/// representing types, literal values, etc. that those instructions refer to.
+///
+/// See [BaseIRContainer] for additional information.
+///
+/// To construct a sequence of IR instructions, see [CodedIRWriter].
+class CodedIRContainer extends BaseIRContainer {
+ final List<Object?> _literalTable;
+ final List<DartType> _typeTable;
+
+ CodedIRContainer(CodedIRWriter super.writer)
+ : _literalTable = writer._literalTable,
+ _typeTable = writer._typeTable;
+
+ @override
+ int countParameters(TypeRef type) =>
+ (decodeType(type) as FunctionType).parameters.length;
+
+ Object? decodeLiteral(LiteralRef literal) => _literalTable[literal.index];
+
+ DartType decodeType(TypeRef type) => _typeTable[type.index];
+
+ @override
+ String literalRefToString(LiteralRef value) =>
+ json.encode(decodeLiteral(value));
+
+ @override
+ String typeRefToString(TypeRef type) => decodeType(type).toString();
+}
+
+/// Writer of an IR instruction stream, which can encode types, literal values,
+/// etc. into auxiliary tables.
+///
+/// See [RawIRWriter] for more information.
+class CodedIRWriter extends RawIRWriter {
+ final _literalTable = <Object?>[];
+ final _typeTable = <DartType>[];
+ final _literalToRef = <Object?, LiteralRef>{};
+ final _typeToRef = <DartType, TypeRef>{};
+
+ LiteralRef encodeLiteral(Object? value) =>
+ // TODO(paulberry): is `putIfAbsent` the best-performing way to do this?
+ _literalToRef.putIfAbsent(value, () {
+ var encoding = LiteralRef(_literalTable.length);
+ _literalTable.add(value);
+ return encoding;
+ });
+
+ TypeRef encodeType(DartType type) =>
+ // TODO(paulberry): is `putIfAbsent` the best-performing way to do this?
+ _typeToRef.putIfAbsent(type, () {
+ var encoding = TypeRef(_typeTable.length);
+ _typeTable.add(type);
+ return encoding;
+ });
+}
diff --git a/pkg/analyzer/lib/src/wolf/ir/interpreter.dart b/pkg/analyzer/lib/src/wolf/ir/interpreter.dart
new file mode 100644
index 0000000..6f7b5d4
--- /dev/null
+++ b/pkg/analyzer/lib/src/wolf/ir/interpreter.dart
@@ -0,0 +1,48 @@
+// Copyright (c) 2023, 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/wolf/ir/coded_ir.dart';
+import 'package:analyzer/src/wolf/ir/ir.dart';
+import 'package:meta/meta.dart';
+
+/// Evaluates [ir], passing in [args], and returns the result.
+///
+/// This interpreter is neither efficient nor full-featured, so it shouldn't be
+/// used in production code. It is solely intended to allow unit tests to verify
+/// that an instruction sequence behaves as it's expected to.
+@visibleForTesting
+Object? interpret(CodedIRContainer ir, List<Object?> args) =>
+ _IRInterpreter(ir).run(args);
+
+class _IRInterpreter {
+ final CodedIRContainer ir;
+ final stack = <Object?>[];
+
+ _IRInterpreter(this.ir);
+
+ Object? run(List<Object?> args) {
+ var functionType = Opcode.function.decodeType(ir, 0);
+ var parameterCount = ir.countParameters(functionType);
+ if (args.length != parameterCount) {
+ throw StateError('Parameter count mismatch');
+ }
+ stack.addAll(args);
+ var address = 1;
+ while (true) {
+ switch (ir.opcodeAt(address)) {
+ case Opcode.end:
+ assert(stack.length == 1);
+ return stack.last;
+ case Opcode.literal:
+ var value = Opcode.literal.decodeValue(ir, address);
+ stack.add(ir.decodeLiteral(value));
+ case var opcode:
+ throw UnimplementedError(
+ 'TODO(paulberry): implement ${opcode.describe()} in '
+ '_IRInterpreter');
+ }
+ address++;
+ }
+ }
+}
diff --git a/pkg/analyzer/lib/src/wolf/ir/validator.dart b/pkg/analyzer/lib/src/wolf/ir/validator.dart
index e88a2bf..f1ad47b 100644
--- a/pkg/analyzer/lib/src/wolf/ir/validator.dart
+++ b/pkg/analyzer/lib/src/wolf/ir/validator.dart
@@ -7,8 +7,15 @@
/// Checks that [ir] is well-formed.
///
/// Throws [ValidationError] if it's not.
-void validate(BaseIRContainer ir) {
- _Validator(ir).run();
+///
+/// During validation, progress information will be reported to [eventListener]
+/// (if provided).
+void validate(BaseIRContainer ir, {ValidationEventListener? eventListener}) {
+ eventListener ??= ValidationEventListener();
+ var validator = _Validator(ir, eventListener: eventListener);
+ eventListener._validator = validator;
+ validator.run();
+ eventListener._validator = null;
}
class ValidationError extends Error {
@@ -26,11 +33,28 @@
'Validation error at $address ($instructionString): $message';
}
+/// Event listener used by [validate] to report progress information.
+///
+/// By itself this class does nothing; the caller of [validate] should make a
+/// derived class that overrides one or more of the `on...` methods.
+base class ValidationEventListener {
+ late _Validator? _validator;
+
+ int get valueStackDepth => _validator!.valueStackDepth;
+
+ /// Called for every iteration in the validation loop, just before visiting an
+ /// instruction.
+ ///
+ /// Also called at the end of the validation loop (with [address] equal to the
+ /// instruction count).
+ void onAddress(int address) {}
+}
+
/// Used by [_Validator] to track a control flow instruction (`block`, `loop`,
/// `tryCatch`, `tryFinally`, or `function` instruction) whose `matching `end`
/// instruction has not yet been encountered.
class _ControlFlowElement {
- /// The state of [_Validator._functionFlags] before the control flow
+ /// The state of [_Validator.functionFlags] before the control flow
/// instruction was encountered.
final FunctionFlags functionFlagsBefore;
@@ -54,81 +78,84 @@
class _Validator {
final BaseIRContainer ir;
- final _controlFlowStack = <_ControlFlowElement>[];
- var _address = 0;
+ final ValidationEventListener eventListener;
+ final controlFlowStack = <_ControlFlowElement>[];
+ var address = 0;
/// Flags from the most recent `function` instruction whose corresponding
/// `end` instruction has not yet been encountered.
- var _functionFlags = FunctionFlags();
+ var functionFlags = FunctionFlags();
- var _valueStackDepth = 0;
+ var valueStackDepth = 0;
- _Validator(this.ir);
-
- void run() {
- _check(ir.endAddress > 0, 'No instructions');
- for (_address = 0; _address < ir.endAddress; _address++) {
- var opcode = ir.opcodeAt(_address);
- _check(_address != 0 || opcode == Opcode.function,
- 'First instruction must be function');
- switch (opcode) {
- case Opcode.drop:
- _popValues(1);
- case Opcode.end:
- _check(_controlFlowStack.isNotEmpty, 'unmatched end');
- var controlFlowElement = _controlFlowStack.removeLast();
- _popValues(controlFlowElement.branchValueCount);
- _check(_valueStackDepth == 0,
- '$_valueStackDepth superfluous value(s) remaining');
- _pushValues(controlFlowElement.valueStackDepthAfter);
- _functionFlags = controlFlowElement.functionFlagsBefore;
- case Opcode.function:
- var type = Opcode.function.decodeType(ir, _address);
- var kind = Opcode.function.decodeFlags(ir, _address);
- _check(!kind.isInstance || _address == 0,
- 'Instance function may only be used at instruction address 0');
- _controlFlowStack.add(_ControlFlowElement(
- functionFlagsBefore: _functionFlags,
- valueStackDepthAfter: _valueStackDepth + 1,
- branchValueCount: 1,
- isFunction: true));
- _functionFlags = kind;
- _valueStackDepth = 0;
- _pushValues(ir.countParameters(type) + (kind.isInstance ? 1 : 0));
- case Opcode.literal:
- _pushValues(1);
- default:
- _fail('Unexpected opcode $opcode');
- }
- }
- _check(_controlFlowStack.isEmpty, 'Missing end');
- }
+ _Validator(this.ir, {required this.eventListener});
/// Reports a validation error if [condition] is `false`.
- void _check(bool condition, String message) {
+ void check(bool condition, String message) {
if (!condition) {
- _fail(message);
+ fail(message);
}
}
/// Unconditionally reports a validation error.
- Never _fail(String message) {
+ Never fail(String message) {
throw ValidationError(
- address: _address,
- instructionString: _address < ir.endAddress
- ? ir.instructionToString(_address)
+ address: address,
+ instructionString: address < ir.endAddress
+ ? ir.instructionToString(address)
: 'after last instruction',
message: message);
}
- void _popValues(int count) {
+ void popValues(int count) {
assert(count >= 0);
- _check(_valueStackDepth >= count, 'Value stack underflow');
- _valueStackDepth -= count;
+ check(valueStackDepth >= count, 'Value stack underflow');
+ valueStackDepth -= count;
}
- void _pushValues(int count) {
+ void pushValues(int count) {
assert(count >= 0);
- _valueStackDepth += count;
+ valueStackDepth += count;
+ }
+
+ void run() {
+ check(ir.endAddress > 0, 'No instructions');
+ for (address = 0; address < ir.endAddress; address++) {
+ eventListener.onAddress(address);
+ var opcode = ir.opcodeAt(address);
+ check(address != 0 || opcode == Opcode.function,
+ 'First instruction must be function');
+ switch (opcode) {
+ case Opcode.drop:
+ popValues(1);
+ case Opcode.end:
+ check(controlFlowStack.isNotEmpty, 'Unmatched end');
+ var controlFlowElement = controlFlowStack.removeLast();
+ popValues(controlFlowElement.branchValueCount);
+ check(valueStackDepth == 0,
+ '$valueStackDepth superfluous value(s) remaining');
+ valueStackDepth = controlFlowElement.valueStackDepthAfter;
+ functionFlags = controlFlowElement.functionFlagsBefore;
+ case Opcode.function:
+ var type = Opcode.function.decodeType(ir, address);
+ var kind = Opcode.function.decodeFlags(ir, address);
+ check(!kind.isInstance || address == 0,
+ 'Instance function may only be used at instruction address 0');
+ controlFlowStack.add(_ControlFlowElement(
+ functionFlagsBefore: functionFlags,
+ valueStackDepthAfter: valueStackDepth + 1,
+ branchValueCount: 1,
+ isFunction: true));
+ functionFlags = kind;
+ valueStackDepth =
+ ir.countParameters(type) + (kind.isInstance ? 1 : 0);
+ case Opcode.literal:
+ pushValues(1);
+ default:
+ fail('Unexpected opcode ${opcode.describe()}');
+ }
+ }
+ eventListener.onAddress(address);
+ check(controlFlowStack.isEmpty, 'Missing end');
}
}
diff --git a/pkg/analyzer/test/src/wolf/ir/ast_to_ir_test.dart b/pkg/analyzer/test/src/wolf/ir/ast_to_ir_test.dart
new file mode 100644
index 0000000..66f8745
--- /dev/null
+++ b/pkg/analyzer/test/src/wolf/ir/ast_to_ir_test.dart
@@ -0,0 +1,93 @@
+// Copyright (c) 2023, 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/dart/ast/ast.dart';
+import 'package:analyzer/src/wolf/ir/ast_to_ir.dart';
+import 'package:analyzer/src/wolf/ir/coded_ir.dart';
+import 'package:analyzer/src/wolf/ir/interpreter.dart';
+import 'package:analyzer/src/wolf/ir/validator.dart';
+import 'package:checks/checks.dart';
+import 'package:test_reflective_loader/test_reflective_loader.dart';
+
+import '../../dart/resolution/context_collection_resolution.dart';
+import 'utils.dart';
+
+main() {
+ defineReflectiveSuite(() {
+ defineReflectiveTests(AstToIRTest);
+ });
+}
+
+@reflectiveTest
+class AstToIRTest extends AstToIRTestBase {
+ Object? runInterpreter(List<Object?> args) => interpret(ir, args);
+
+ test_booleanLiteral() async {
+ await assertNoErrorsInCode('''
+test() => true;
+''');
+ analyze(findNode.singleFunctionDeclaration);
+ check(astNodes).containsNode(findNode.booleanLiteral('true'));
+ check(runInterpreter([])).equals(true);
+ }
+
+ test_doubleLiteral() async {
+ await assertNoErrorsInCode('''
+test() => 1.5;
+''');
+ analyze(findNode.singleFunctionDeclaration);
+ check(astNodes).containsNode(findNode.doubleLiteral('1.5'));
+ check(runInterpreter([])).equals(1.5);
+ }
+
+ test_expressionFunctionBody() async {
+ await assertNoErrorsInCode('''
+test() => 0;
+''');
+ analyze(findNode.singleFunctionDeclaration);
+ check(astNodes)[findNode.expressionFunctionBody('0')]
+ .containsSubrange(astNodes[findNode.integerLiteral('0')]!);
+ }
+
+ test_integerLiteral() async {
+ await assertNoErrorsInCode('''
+test() => 123;
+''');
+ analyze(findNode.singleFunctionDeclaration);
+ check(astNodes).containsNode(findNode.integerLiteral('123'));
+ check(runInterpreter([])).equals(123);
+ }
+
+ test_nullLiteral() async {
+ await assertNoErrorsInCode('''
+test() => null;
+''');
+ analyze(findNode.singleFunctionDeclaration);
+ check(astNodes).containsNode(findNode.nullLiteral('null'));
+ check(runInterpreter([])).equals(null);
+ }
+
+ test_stringLiteral() async {
+ await assertNoErrorsInCode(r'''
+test() => 'foo';
+''');
+ analyze(findNode.singleFunctionDeclaration);
+ check(astNodes).containsNode(findNode.stringLiteral('foo'));
+ check(runInterpreter([])).equals('foo');
+ }
+}
+
+class AstToIRTestBase extends PubPackageResolutionTest {
+ final astNodes = AstNodes();
+ late final CodedIRContainer ir;
+
+ void analyze(FunctionDeclaration functionDeclaration) {
+ ir = astToIR(functionDeclaration.declaredElement!,
+ functionDeclaration.functionExpression.body,
+ typeProvider: typeProvider,
+ typeSystem: typeSystem,
+ eventListener: astNodes);
+ validate(ir);
+ }
+}
diff --git a/pkg/analyzer/test/src/wolf/ir/test_all.dart b/pkg/analyzer/test/src/wolf/ir/test_all.dart
index c6ba790..7c5b7c0 100644
--- a/pkg/analyzer/test/src/wolf/ir/test_all.dart
+++ b/pkg/analyzer/test/src/wolf/ir/test_all.dart
@@ -4,10 +4,12 @@
import 'package:test_reflective_loader/test_reflective_loader.dart';
+import 'ast_to_ir_test.dart' as ast_to_ir;
import 'validator_test.dart' as validator;
main() {
defineReflectiveSuite(() {
+ ast_to_ir.main();
validator.main();
}, name: 'ir');
}
diff --git a/pkg/analyzer/test/src/wolf/ir/utils.dart b/pkg/analyzer/test/src/wolf/ir/utils.dart
index b0cb2c6..c75adaf 100644
--- a/pkg/analyzer/test/src/wolf/ir/utils.dart
+++ b/pkg/analyzer/test/src/wolf/ir/utils.dart
@@ -2,7 +2,109 @@
// 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/dart/ast/ast.dart';
+import 'package:analyzer/src/wolf/ir/ast_to_ir.dart';
+import 'package:analyzer/src/wolf/ir/coded_ir.dart';
import 'package:analyzer/src/wolf/ir/ir.dart';
+import 'package:checks/checks.dart';
+import 'package:checks/context.dart';
+import 'package:meta/meta.dart' as meta;
+
+/// Event listener for [astToIR] that records the range of IR instructions
+/// associated with each AST node.
+///
+/// These ranges can be queried using the `[]` operator after [astToIR]
+/// completes.
+base class AstNodes extends AstToIREventListener {
+ /// Outstanding [AstNodes] which have been entered but not exited.
+ final _nodeStack = <AstNode>[];
+
+ /// For each entry in [_nodeStack], the value returned by
+ /// [nextInstructionAddress] at the time [onEnterNode] was called.
+ ///
+ /// In other words, the address of the first instruction that was output (or
+ /// that will be output) while visiting the corresponding to the AST node.
+ final _nodeStartStack = <int>[];
+
+ final _nodeMap = <AstNode, ({int start, int end})>{};
+
+ /// The full IR.
+ ///
+ /// Only available after [onFinished] has been called.
+ late final CodedIRContainer ir;
+
+ /// Gets the [InstructionRange] for [node].
+ ///
+ /// Only available after [onFinished] has been called.
+ InstructionRange? operator [](AstNode node) => switch (_nodeMap[node]) {
+ null => null,
+ (:var start, :var end) =>
+ InstructionRange(ir: ir, start: start, end: end)
+ };
+
+ @override
+ void onEnterNode(AstNode node) {
+ _nodeStack.add(node);
+ _nodeStartStack.add(nextInstructionAddress);
+ super.onEnterNode(node);
+ }
+
+ @override
+ void onExitNode() {
+ _nodeMap[_nodeStack.removeLast()] =
+ (start: _nodeStartStack.removeLast(), end: nextInstructionAddress);
+ super.onExitNode();
+ }
+
+ @override
+ void onFinished(CodedIRContainer ir) {
+ check(_nodeStack).isEmpty();
+ check(_nodeStartStack).isEmpty();
+ this.ir = ir;
+ super.onFinished(ir);
+ }
+
+ @override
+ String toString() {
+ if (_nodeMap.isEmpty) return 'AstNodes(<empty>)';
+ return [
+ 'AstNodes(',
+ for (var MapEntry(:key, :value) in _nodeMap.entries)
+ ' ${key.runtimeType} $key => $value',
+ ')'
+ ].join('\n');
+ }
+}
+
+/// Reference to a single instruction in a [CodedIRContainer].
+class Instruction {
+ final CodedIRContainer ir;
+ final int address;
+
+ Instruction(this.ir, this.address);
+}
+
+/// Reference to a range of instructions in a [CodedIRContainer].
+class InstructionRange {
+ final CodedIRContainer ir;
+
+ /// Start address of the range (i.e., the address of the first instruction in
+ /// the range).
+ final int start;
+
+ /// "Past the end" address of the range (i.e., one more than the address of
+ /// the last instruction in the range).
+ ///
+ /// If [start] is equal to [end], the range is empty.
+ final int end;
+
+ InstructionRange({required this.ir, required this.start, required this.end});
+
+ bool containsAddress(int address) => start <= address && address < end;
+
+ @override
+ String toString() => '[$start, $end)';
+}
/// Minimal representation of a function type in unit tests that use
/// [TestIRContainer].
@@ -20,14 +122,22 @@
///
/// To construct a sequence of IR instructions, see [TestIRWriter].
class TestIRContainer extends BaseIRContainer {
+ final Map<int, String> _addressToLabel;
final List<TestFunctionType> _functionTypes;
+ final Map<String, int> _labelToAddress;
TestIRContainer(TestIRWriter super.writer)
- : _functionTypes = writer._functionTypes;
+ : _addressToLabel = writer._addressToLabel,
+ _functionTypes = writer._functionTypes,
+ _labelToAddress = writer._labelToAddress;
+
+ String? addressToLabel(int address) => _addressToLabel[address];
@override
int countParameters(TypeRef type) =>
_functionTypes[type.index].parameterCount;
+
+ int? labelToAddress(String label) => _labelToAddress[label];
}
/// Writer of an IR instruction stream that's not connected to an analyzer AST
@@ -36,7 +146,9 @@
/// Suitable for use in unit tests that test the IR instructions directly rather
/// than generate them from a Dart AST.
class TestIRWriter extends RawIRWriter {
+ final _addressToLabel = <int, String>{};
final _functionTypes = <TestFunctionType>[];
+ final _labelToAddress = <String, int>{};
final _literalTable = <Object?>[];
final _literalToRef = <Object?, LiteralRef>{};
final _parameterCountToFunctionTypeMap = <int, TypeRef>{};
@@ -55,8 +167,81 @@
return encoding;
});
+ void label(String name) {
+ assert(!_labelToAddress.containsKey(name), 'Duplicate label $name');
+ _labelToAddress[name] = nextInstructionAddress;
+ _addressToLabel[nextInstructionAddress] = name;
+ }
+
/// Convenience method for creating an ordinary function (not a method, not
/// async, not a generator).
void ordinaryFunction({int parameterCount = 0}) => function(
encodeFunctionType(parameterCount: parameterCount), FunctionFlags());
}
+
+/// Testing methods for [AstNodes].
+extension SubjectAstNodes on Subject<AstNodes> {
+ /// Verifies that an entry exists for [node], and returns a [Subject] that
+ /// allows its properties to be tested.
+ @meta.useResult
+ Subject<InstructionRange> operator [](AstNode node) {
+ return context
+ .nest(() => prefixFirst('contains ${node.runtimeType} ', literal(node)),
+ (astNodes) {
+ if (astNodes[node] case var range?) return Extracted.value(range);
+ return Extracted.rejection(
+ which: prefixFirst(
+ 'does not contain ${node.runtimeType} ', literal(node)));
+ });
+ }
+
+ /// Verifies that an entry exists for [node].
+ void containsNode(AstNode node) {
+ context.expect(
+ () => prefixFirst('contains ${node.runtimeType} ', literal(node)),
+ (astNodes) {
+ if (astNodes[node] != null) return null;
+ return Rejection(
+ which: prefixFirst(
+ 'does not contain ${node.runtimeType} ', literal(node)));
+ });
+ }
+}
+
+/// Testing methods for [Instruction].
+extension SubjectInstruction on Subject<Instruction> {
+ @meta.useResult
+ Subject<Opcode> get opcode => has(
+ (instruction) => instruction.ir.opcodeAt(instruction.address), 'opcode');
+}
+
+/// Testing methods for [InstructionRange].
+extension SubjectInstructionRange on Subject<InstructionRange> {
+ @meta.useResult
+ Subject<int> get end => has((range) => range.end, 'end');
+
+ @meta.useResult
+ Subject<List<Instruction>> get instructions => has(
+ (range) => [
+ for (var address = range.start; address < range.end; address++)
+ Instruction(range.ir, address)
+ ],
+ 'instructions');
+
+ @meta.useResult
+ Subject<int> get start => has((range) => range.start, 'start');
+
+ /// Verifies that [subrange] is contained within the subject range.
+ ///
+ /// The check passes if [subrange] is the same as the subject range.
+ void containsSubrange(InstructionRange subrange) {
+ context.expect(() => prefixFirst('contains subrange ', literal(subrange)),
+ (range) {
+ if (range.start <= subrange.start && subrange.end <= range.end) {
+ return null;
+ }
+ return Rejection(
+ which: prefixFirst('does not contain subrange ', literal(subrange)));
+ });
+ }
+}
diff --git a/pkg/analyzer/test/src/wolf/ir/validator_test.dart b/pkg/analyzer/test/src/wolf/ir/validator_test.dart
index 9b45228..4e75baa 100644
--- a/pkg/analyzer/test/src/wolf/ir/validator_test.dart
+++ b/pkg/analyzer/test/src/wolf/ir/validator_test.dart
@@ -17,126 +17,208 @@
@reflectiveTest
class ValidatorTest {
+ final _addressToOnValidateCallbacks =
+ <int, List<void Function(ValidationEventListener)>>{};
late TestIRContainer ir;
- test_drop() {
+ test_drop_ok() {
_analyze((ir) => ir
- ..ordinaryFunction(parameterCount: 1)
- ..drop() // Pop parameter
- ..drop() // UNDERFLOW
+ ..ordinaryFunction(parameterCount: 2)
+ ..onValidate((v) => check(v.valueStackDepth).equals(2))
+ ..drop()
+ ..onValidate((v) => check(v.valueStackDepth).equals(1))
..end());
- check(_validate).throws<ValidationError>()
- ..address.equals(2)
- ..message.equals('Value stack underflow');
+ _validate();
}
- test_firstInstruction_function() {
+ test_drop_underflow() {
+ _analyze((ir) => ir
+ ..ordinaryFunction()
+ ..label('bad')
+ ..drop()
+ ..end());
+ _checkInvalidMessageAt('bad').equals('Value stack underflow');
+ }
+
+ test_end_function_pushesOneValue() {
+ _analyze((ir) => ir
+ ..ordinaryFunction(parameterCount: 1)
+ ..onValidate((v) => check(v.valueStackDepth).equals(1))
+ ..ordinaryFunction(parameterCount: 1)
+ ..end()
+ ..onValidate((v) => check(v.valueStackDepth).equals(2))
+ ..drop()
+ ..end());
+ _validate();
+ }
+
+ test_end_function_superfluousValues() {
+ _analyze((ir) => ir
+ ..ordinaryFunction(parameterCount: 2)
+ ..label('bad')
+ ..end());
+ _checkInvalidMessageAt('bad').equals('1 superfluous value(s) remaining');
+ }
+
+ test_end_function_valueStackUnderflow() {
+ _analyze((ir) => ir
+ ..ordinaryFunction()
+ ..label('bad')
+ ..end());
+ _checkInvalidMessageAt('bad').equals('Value stack underflow');
+ }
+
+ test_end_unmatched() {
+ _analyze((ir) => ir
+ ..ordinaryFunction(parameterCount: 1)
+ ..end()
+ ..label('bad')
+ ..end());
+ _checkInvalidMessageAt('bad').equals('Unmatched end');
+ }
+
+ test_firstInstruction_function_ok() {
_analyze((ir) => ir
..ordinaryFunction()
..literal(ir.encodeLiteral(null))
..end());
- check(_validate).returnsNormally();
+ _validate();
}
- test_firstInstruction_instanceFunction() {
+ test_firstInstruction_instanceFunction_ok() {
_analyze((ir) => ir
..function(ir.encodeFunctionType(parameterCount: 0),
FunctionFlags(instance: true))
..end());
- check(_validate).returnsNormally();
+ _validate();
}
test_firstInstruction_notFunction() {
- _analyze((ir) => ir..literal(ir.encodeLiteral(null)));
- check(_validate).throws<ValidationError>()
- ..address.equals(0)
- ..message.equals('First instruction must be function');
+ _analyze((ir) => ir
+ ..label('bad')
+ ..literal(ir.encodeLiteral(null)));
+ _checkInvalidMessageAt('bad').equals('First instruction must be function');
}
test_function_nested_instanceFunction() {
_analyze((ir) => ir
..ordinaryFunction()
+ ..label('bad')
..function(ir.encodeFunctionType(parameterCount: 0),
FunctionFlags(instance: true))
..end()
..end());
- check(_validate).throws<ValidationError>()
- ..address.equals(1)
- ..message.equals(
- 'Instance function may only be used at instruction address 0');
+ _checkInvalidMessageAt('bad')
+ .equals('Instance function may only be used at instruction address 0');
}
- test_function_nested_notInstanceFunction() {
+ test_function_nested_notInstanceFunction_ok() {
_analyze((ir) => ir
..ordinaryFunction()
..ordinaryFunction()
..literal(ir.encodeLiteral(null))
..end()
..end());
- check(_validate).returnsNormally();
+ _validate();
}
test_function_parameterCount_instanceFunction() {
_analyze((ir) => ir
..function(ir.encodeFunctionType(parameterCount: 2),
FunctionFlags(instance: true))
- ..drop() // Pop second parameter
- ..drop() // Pop first parameter
- ..drop() // Pop `this`
- ..drop() // UNDERFLOW
+ ..onValidate((v) => check(v.valueStackDepth).equals(3))
+ ..drop()
+ ..drop()
..end());
- check(_validate).throws<ValidationError>()
- ..address.equals(4)
- ..message.equals('Value stack underflow');
+ _validate();
}
test_function_parameterCount_notInstanceFunction() {
_analyze((ir) => ir
..ordinaryFunction(parameterCount: 2)
- ..drop() // Pop second parameter
- ..drop() // Pop first parameter
- ..drop() // UNDERFLOW
+ ..onValidate((v) => check(v.valueStackDepth).equals(2))
+ ..drop()
..end());
- check(_validate).throws<ValidationError>()
- ..address.equals(3)
- ..message.equals('Value stack underflow');
+ _validate();
}
- test_literal() {
+ test_literal_ok() {
_analyze((ir) => ir
..ordinaryFunction()
+ ..onValidate((v) => check(v.valueStackDepth).equals(0))
..literal(ir.encodeLiteral(null)) // Push `null`
- ..drop() // Pop `null`
- ..drop() // UNDERFLOW
+ ..onValidate((v) => check(v.valueStackDepth).equals(1))
..end());
- check(_validate).throws<ValidationError>()
- ..address.equals(3)
- ..message.equals('Value stack underflow');
+ _validate();
}
test_missingEnd() {
_analyze((ir) => ir
..ordinaryFunction()
- ..literal(ir.encodeLiteral(null)));
- check(_validate).throws<ValidationError>()
- ..address.equals(2)
- ..message.equals('Missing end');
+ ..literal(ir.encodeLiteral(null))
+ ..label('bad'));
+ _checkInvalidMessageAt('bad').equals('Missing end');
}
test_noInstructions() {
- _analyze((ir) => ir);
- check(_validate).throws<ValidationError>()
- ..address.equals(0)
- ..message.equals('No instructions');
+ _analyze((ir) => ir..label('bad'));
+ _checkInvalidMessageAt('bad').equals('No instructions');
}
- void _analyze(void Function(TestIRWriter) writeIR) {
- var writer = TestIRWriter();
+ void _analyze(void Function(_ValidationTestIRWriter) writeIR) {
+ var writer = _ValidationTestIRWriter(_addressToOnValidateCallbacks);
writeIR(writer);
ir = TestIRContainer(writer);
}
- void _validate() => validate(ir);
+ Subject<String> _checkInvalidMessageAt(String label) =>
+ (check(_validate).throws<ValidationError>()
+ ..address.equals(ir.labelToAddress('bad')!))
+ .message;
+
+ void _validate() {
+ validate(ir,
+ eventListener: _ValidationEventListener(_addressToOnValidateCallbacks));
+ check(
+ because: 'make sure all callbacks got invoked',
+ _addressToOnValidateCallbacks)
+ .isEmpty();
+ }
+}
+
+/// Validation event listener that executes callbacks installed by
+/// [_ValidationTestIRWriter].
+base class _ValidationEventListener extends ValidationEventListener {
+ final Map<int, List<void Function(ValidationEventListener)>>
+ _addressToOnValidateCallbacks;
+
+ _ValidationEventListener(this._addressToOnValidateCallbacks);
+
+ @override
+ void onAddress(int address) {
+ if (_addressToOnValidateCallbacks.remove(address) case var callbacks?) {
+ for (var callback in callbacks) {
+ callback(this);
+ }
+ }
+ }
+}
+
+/// IR writer that can record callbacks to be executed during validation.
+///
+/// These callbacks will have access to the [ValidationEventListener] so they
+/// can query some internal validator state.
+class _ValidationTestIRWriter extends TestIRWriter {
+ final Map<int, List<void Function(ValidationEventListener)>>
+ _addressToOnValidateCallbacks;
+
+ _ValidationTestIRWriter(this._addressToOnValidateCallbacks);
+
+ void onValidate(void Function(ValidationEventListener) callback) {
+ _addressToOnValidateCallbacks
+ .putIfAbsent(nextInstructionAddress, () => [])
+ .add(callback);
+ }
}
extension on Subject<ValidationError> {
