Add set tracing.
Change-Id: I889c5ac8d6207c9a25721d939b0f01b4e945a940
Reviewed-on: https://dart-review.googlesource.com/c/92149
Commit-Queue: Mayank Patke <fishythefish@google.com>
Reviewed-by: Sigmund Cherem <sigmund@google.com>
diff --git a/pkg/compiler/lib/src/inferrer/inferrer_engine.dart b/pkg/compiler/lib/src/inferrer/inferrer_engine.dart
index 021979d..4a0ad05 100644
--- a/pkg/compiler/lib/src/inferrer/inferrer_engine.dart
+++ b/pkg/compiler/lib/src/inferrer/inferrer_engine.dart
@@ -33,6 +33,7 @@
import 'locals_handler.dart';
import 'list_tracer.dart';
import 'map_tracer.dart';
+import 'set_tracer.dart';
import 'type_graph_dump.dart';
import 'type_graph_inferrer.dart';
import 'type_graph_nodes.dart';
@@ -78,6 +79,7 @@
void analyze(MemberEntity member);
void analyzeListAndEnqueue(ListTypeInformation info);
+ void analyzeSetAndEnqueue(SetTypeInformation info);
void analyzeMapAndEnqueue(MapTypeInformation info);
/// Notifies to the inferrer that [analyzedElement] can have return type
@@ -441,6 +443,23 @@
workQueue.add(info.elementType);
}
+ void analyzeSetAndEnqueue(SetTypeInformation info) {
+ if (info.analyzed) return;
+ info.analyzed = true;
+
+ SetTracerVisitor tracer = new SetTracerVisitor(info, this);
+ bool succeeded = tracer.run();
+ if (!succeeded) return;
+
+ info.bailedOut = false;
+ info.elementType.inferred = true;
+
+ tracer.assignments.forEach(info.elementType.addAssignment);
+ // Enqueue the set for later refinement.
+ workQueue.add(info);
+ workQueue.add(info.elementType);
+ }
+
void analyzeMapAndEnqueue(MapTypeInformation info) {
if (info.analyzed) return;
info.analyzed = true;
@@ -480,6 +499,11 @@
analyzeListAndEnqueue(info);
});
+ // Try to infer element types of sets and compute their escape information.
+ types.allocatedSets.values.forEach((TypeInformation info) {
+ analyzeSetAndEnqueue(info);
+ });
+
// Try to infer the key and value types for maps and compute the values'
// escape information.
types.allocatedMaps.values.forEach((TypeInformation info) {
@@ -587,6 +611,13 @@
'at ${abstractValueDomain.getAllocationElement(info.originalType)}'
'after ${info.refineCount}');
});
+ types.allocatedSets.values.forEach((_info) {
+ SetTypeInformation info = _info;
+ print('${info.type} '
+ 'for ${abstractValueDomain.getAllocationNode(info.originalType)} '
+ 'at ${abstractValueDomain.getAllocationElement(info.originalType)} '
+ 'after ${info.refineCount}');
+ });
types.allocatedMaps.values.forEach((_info) {
MapTypeInformation info = _info;
print('${info.type} '
@@ -1176,6 +1207,7 @@
generativeConstructorsExposingThis.clear();
types.allocatedMaps.values.forEach(cleanup);
+ types.allocatedSets.values.forEach(cleanup);
types.allocatedLists.values.forEach(cleanup);
_memberData.clear();
diff --git a/pkg/compiler/lib/src/inferrer/node_tracer.dart b/pkg/compiler/lib/src/inferrer/node_tracer.dart
index 81b343f2..0a3d2ee 100644
--- a/pkg/compiler/lib/src/inferrer/node_tracer.dart
+++ b/pkg/compiler/lib/src/inferrer/node_tracer.dart
@@ -51,6 +51,31 @@
'checkGrowable',
]);
+Set<String> doesNotEscapeSetSet = new Set<String>.from(const <String>[
+ // From Object.
+ '==',
+ 'hashCode',
+ 'toString',
+ 'noSuchMethod',
+ 'runtimeType',
+
+ // From Iterable.
+ 'isEmpty',
+ 'isNotEmpty',
+ 'length',
+ 'contains',
+ 'join',
+
+ // From Set.
+ 'add',
+ 'addAll',
+ 'clear',
+ 'containsAll',
+ 'remove',
+ 'removeAll',
+ 'retainAll',
+]);
+
Set<String> doesNotEscapeMapSet = new Set<String>.from(const <String>[
// From Object.
'==',
@@ -142,6 +167,9 @@
while (!listsToAnalyze.isEmpty) {
analyzeStoredIntoList(listsToAnalyze.removeLast());
}
+ while (setsToAnalyze.isNotEmpty) {
+ analyzeStoredIntoSet(setsToAnalyze.removeLast());
+ }
while (!mapsToAnalyze.isEmpty) {
analyzeStoredIntoMap(mapsToAnalyze.removeLast());
}
@@ -244,6 +272,24 @@
}
}
+ void analyzeStoredIntoSet(SetTypeInformation set) {
+ inferrer.analyzeSetAndEnqueue(set);
+ if (set.bailedOut) {
+ bailout('Stored in a set that bailed out');
+ } else {
+ set.flowsInto.forEach((flow) {
+ flow.users.forEach((dynamic user) {
+ if (user.receiver != flow) return;
+ if (user.selector.isIndex) {
+ addNewEscapeInformation(user);
+ } else if (!doesNotEscapeSetSet.contains(user.selector.name)) {
+ bailout('Escape from a set via [${user.selector.name}]');
+ }
+ });
+ });
+ }
+ }
+
void analyzeStoredIntoMap(MapTypeInformation map) {
inferrer.analyzeMapAndEnqueue(map);
if (map.bailedOut) {
diff --git a/pkg/compiler/lib/src/inferrer/set_tracer.dart b/pkg/compiler/lib/src/inferrer/set_tracer.dart
new file mode 100644
index 0000000..6c809ad
--- /dev/null
+++ b/pkg/compiler/lib/src/inferrer/set_tracer.dart
@@ -0,0 +1,131 @@
+// Copyright (c) 2019, 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.
+
+library compiler.src.inferrer.set_tracer;
+
+import '../elements/entities.dart';
+import '../js_backend/backend.dart' show JavaScriptBackend;
+import '../universe/selector.dart' show Selector;
+import 'node_tracer.dart';
+import 'type_graph_nodes.dart';
+
+/// A set of selector names that [Set] implements and which we know do not
+/// change the element type of the set or let the set escape to code that might
+/// change the element type.
+Set<String> okSetSelectorSet = new Set<String>.from(const <String>[
+ // From Object.
+ '==',
+ 'hashCode',
+ 'toString',
+ 'noSuchMethod',
+ 'runtimeType',
+
+ // From Iterable.
+ 'iterator',
+ 'map',
+ 'where',
+ 'expand',
+ 'contains',
+ 'forEach',
+ 'reduce',
+ 'fold',
+ 'every',
+ 'join',
+ 'any',
+ 'toList',
+ 'toSet',
+ 'length',
+ 'isEmpty',
+ 'isNotEmpty',
+ 'take',
+ 'takeWhile',
+ 'skip',
+ 'skipWhile',
+ 'first',
+ 'last',
+ 'single',
+ 'firstWhere',
+ 'lastWhere',
+ 'singleWhere',
+ 'elementAt',
+
+ // From Set.
+ 'clear',
+ 'containsAll',
+ 'difference',
+ 'intersection',
+ 'lookup',
+ 'remove',
+ 'removeAll',
+ 'removeWhere',
+ 'retainAll',
+ 'retainWhere',
+ 'union',
+]);
+
+class SetTracerVisitor extends TracerVisitor {
+ List<TypeInformation> assignments = <TypeInformation>[];
+
+ SetTracerVisitor(tracedType, inferrer) : super(tracedType, inferrer);
+
+ /// Returns [true] if the analysis completed successfully, [false] if it
+ /// bailed out. In the former case, [assignments] holds a list of
+ /// [TypeInformation] nodes that flow into the element type of this set.
+ bool run() {
+ analyze();
+ SetTypeInformation set = tracedType;
+ if (continueAnalyzing) {
+ set.addFlowsIntoTargets(flowsInto);
+ return true;
+ }
+ assignments = null;
+ return false;
+ }
+
+ @override
+ visitClosureCallSiteTypeInformation(ClosureCallSiteTypeInformation info) {
+ bailout('Passed to a closure');
+ }
+
+ @override
+ visitStaticCallSiteTypeInformation(StaticCallSiteTypeInformation info) {
+ super.visitStaticCallSiteTypeInformation(info);
+ MemberEntity called = info.calledElement;
+ if (inferrer.closedWorld.commonElements.isForeign(called) &&
+ called.name == JavaScriptBackend.JS) {
+ bailout('Used in JS ${info.debugName}');
+ }
+ }
+
+ @override
+ visitDynamicCallSiteTypeInformation(DynamicCallSiteTypeInformation info) {
+ super.visitDynamicCallSiteTypeInformation(info);
+ Selector selector = info.selector;
+ String selectorName = selector.name;
+ if (currentUser == info.receiver) {
+ if (!okSetSelectorSet.contains(selectorName)) {
+ if (selector.isCall) {
+ switch (selectorName) {
+ case 'add':
+ assignments.add(info.arguments.positional[0]);
+ break;
+ case 'addAll':
+ // TODO(fishythefish): Extract type argument from type
+ // information.
+ bailout('Adding iterable with unknown typeinfo to current set');
+ break;
+ default:
+ bailout('Set used in a not-ok selector [$selectorName]');
+ }
+ return;
+ }
+ }
+ } else if (selector.isCall &&
+ (info.hasClosureCallTargets ||
+ info.concreteTargets.any((element) => !element.isFunction))) {
+ bailout('Passed to a closure');
+ return;
+ }
+ }
+}
diff --git a/tests/compiler/dart2js/analyses/dart2js_allowed.json b/tests/compiler/dart2js/analyses/dart2js_allowed.json
index 8ebdcf1..e42f240 100644
--- a/tests/compiler/dart2js/analyses/dart2js_allowed.json
+++ b/tests/compiler/dart2js/analyses/dart2js_allowed.json
@@ -271,6 +271,12 @@
"pkg/compiler/lib/src/ssa/value_set.dart": {
"Dynamic invocation of 'add'.": 2
},
+ "pkg/compiler/lib/src/inferrer/node_tracer.dart": {
+ "Dynamic access of 'receiver'.": 1,
+ "Dynamic access of 'selector'.": 3,
+ "Dynamic access of 'isIndex'.": 1,
+ "Dynamic access of 'name'.": 2
+ },
"pkg/compiler/lib/src/js_emitter/program_builder/program_builder.dart": {
"Dynamic access of 'keys'.": 1,
"Dynamic invocation of 'toSet'.": 1,
