Introduce bottom up class hierarchy traversal
Change-Id: I48069d622131cd2bf4b43c998015af74cfbd003c
diff --git a/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
new file mode 100644
index 0000000..80f3d93
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/BottomUpClassHierarchyTraversal.java
@@ -0,0 +1,54 @@
+// Copyright (c) 2019, the R8 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.
+
+package com.android.tools.r8.graph;
+
+public class BottomUpClassHierarchyTraversal<T extends DexClass>
+ extends ClassHierarchyTraversal<T> {
+
+ private BottomUpClassHierarchyTraversal(
+ AppView<? extends AppInfoWithSubtyping> appView, Scope scope) {
+ super(appView, scope);
+ }
+
+ /**
+ * Returns a visitor that can be used to visit all the classes (including class path and library
+ * classes) that are reachable from a given set of sources.
+ */
+ public static BottomUpClassHierarchyTraversal<DexClass> forAllClasses(
+ AppView<? extends AppInfoWithSubtyping> appView) {
+ return new BottomUpClassHierarchyTraversal<>(appView, Scope.ALL_CLASSES);
+ }
+
+ /**
+ * Returns a visitor that can be used to visit all the program classes that are reachable from a
+ * given set of sources.
+ */
+ public static BottomUpClassHierarchyTraversal<DexProgramClass> forProgramClasses(
+ AppView<? extends AppInfoWithSubtyping> appView) {
+ return new BottomUpClassHierarchyTraversal<>(appView, Scope.ONLY_PROGRAM_CLASSES);
+ }
+
+ @Override
+ void addDependentsToWorklist(DexClass clazz) {
+ @SuppressWarnings("unchecked")
+ T clazzWithTypeT = (T) clazz;
+
+ if (visited.contains(clazzWithTypeT)) {
+ return;
+ }
+
+ worklist.addFirst(clazzWithTypeT);
+
+ // Add subtypes to worklist.
+ for (DexType subtype : appView.appInfo().allImmediateSubtypes(clazz.type)) {
+ DexClass definition = appView.definitionFor(subtype);
+ if (definition != null) {
+ if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
+ addDependentsToWorklist(definition);
+ }
+ }
+ }
+ }
+}
diff --git a/src/main/java/com/android/tools/r8/graph/ClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/graph/ClassHierarchyTraversal.java
new file mode 100644
index 0000000..eb21910
--- /dev/null
+++ b/src/main/java/com/android/tools/r8/graph/ClassHierarchyTraversal.java
@@ -0,0 +1,62 @@
+// Copyright (c) 2019, the R8 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.
+
+package com.android.tools.r8.graph;
+
+import java.util.ArrayDeque;
+import java.util.Deque;
+import java.util.HashSet;
+import java.util.Iterator;
+import java.util.Set;
+import java.util.function.Consumer;
+
+abstract class ClassHierarchyTraversal<T extends DexClass> {
+
+ enum Scope {
+ ALL_CLASSES,
+ ONLY_PROGRAM_CLASSES
+ }
+
+ final AppView<? extends AppInfoWithSubtyping> appView;
+ final Scope scope;
+
+ final Set<T> visited = new HashSet<>();
+ final Deque<T> worklist = new ArrayDeque<>();
+
+ ClassHierarchyTraversal(AppView<? extends AppInfoWithSubtyping> appView, Scope scope) {
+ this.appView = appView;
+ this.scope = scope;
+ }
+
+ public void visit(Iterable<DexProgramClass> sources, Consumer<T> visitor) {
+ Iterator<DexProgramClass> sourceIterator = sources.iterator();
+
+ // Visit the program classes in the order that is implemented by addDependentsToWorklist().
+ while (sourceIterator.hasNext() || !worklist.isEmpty()) {
+ if (worklist.isEmpty()) {
+ // Add the dependents of the next source (including the source itself) to the worklist.
+ // The order in which the dependents are added to the worklist is used to determine the
+ // traversal order (e.g., top-down, bottom-up).
+ addDependentsToWorklist(sourceIterator.next());
+ if (worklist.isEmpty()) {
+ continue;
+ }
+ }
+
+ T clazz = worklist.removeFirst();
+ if (visited.add(clazz)) {
+ assert scope != Scope.ONLY_PROGRAM_CLASSES || clazz.isProgramClass();
+ visitor.accept(clazz);
+ }
+ }
+
+ visited.clear();
+ }
+
+ // The traversal order is dependent on the order in which addDependentsToWorklist() enqueues
+ // classes into the worklist. For example, to implement a top-down class hierarchy, this method
+ // should add all super types of `clazz` to the worklist before adding `clazz` itself to the
+ // worklist.
+ abstract void addDependentsToWorklist(DexClass clazz);
+}
diff --git a/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java b/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
index 14c98e4..9e7fbe4 100644
--- a/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
+++ b/src/main/java/com/android/tools/r8/graph/TopDownClassHierarchyTraversal.java
@@ -4,29 +4,11 @@
package com.android.tools.r8.graph;
-import java.util.ArrayDeque;
-import java.util.Deque;
-import java.util.HashSet;
-import java.util.Iterator;
-import java.util.Set;
-import java.util.function.Consumer;
+public class TopDownClassHierarchyTraversal<T extends DexClass> extends ClassHierarchyTraversal<T> {
-public class TopDownClassHierarchyTraversal<T extends DexClass> {
-
- private enum Scope {
- ALL_CLASSES,
- ONLY_PROGRAM_CLASSES
- }
-
- private final DexDefinitionSupplier definitions;
- private final Scope scope;
-
- private final Set<T> visited = new HashSet<>();
- private final Deque<T> worklist = new ArrayDeque<>();
-
- private TopDownClassHierarchyTraversal(DexDefinitionSupplier definitions, Scope scope) {
- this.definitions = definitions;
- this.scope = scope;
+ private TopDownClassHierarchyTraversal(
+ AppView<? extends AppInfoWithSubtyping> appView, Scope scope) {
+ super(appView, scope);
}
/**
@@ -34,8 +16,8 @@
* classes) that are reachable from a given set of sources.
*/
public static TopDownClassHierarchyTraversal<DexClass> forAllClasses(
- DexDefinitionSupplier definitions) {
- return new TopDownClassHierarchyTraversal<>(definitions, Scope.ALL_CLASSES);
+ AppView<? extends AppInfoWithSubtyping> appView) {
+ return new TopDownClassHierarchyTraversal<>(appView, Scope.ALL_CLASSES);
}
/**
@@ -43,35 +25,12 @@
* given set of sources.
*/
public static TopDownClassHierarchyTraversal<DexProgramClass> forProgramClasses(
- DexDefinitionSupplier definitions) {
- return new TopDownClassHierarchyTraversal<>(definitions, Scope.ONLY_PROGRAM_CLASSES);
+ AppView<? extends AppInfoWithSubtyping> appView) {
+ return new TopDownClassHierarchyTraversal<>(appView, Scope.ONLY_PROGRAM_CLASSES);
}
- public void visit(Iterable<DexProgramClass> sources, Consumer<T> visitor) {
- Iterator<DexProgramClass> sourceIterator = sources.iterator();
-
- // Visit the program classes in a top-down order according to the class hierarchy.
- while (sourceIterator.hasNext() || !worklist.isEmpty()) {
- if (worklist.isEmpty()) {
- // Add the ancestors of the next source (including the source itself) to the worklist in
- // such a way that all super types of the source class come before the class itself.
- addAncestorsToWorklist(sourceIterator.next());
- if (worklist.isEmpty()) {
- continue;
- }
- }
-
- T clazz = worklist.removeFirst();
- if (visited.add(clazz)) {
- assert scope != Scope.ONLY_PROGRAM_CLASSES || clazz.isProgramClass();
- visitor.accept(clazz);
- }
- }
-
- visited.clear();
- }
-
- private void addAncestorsToWorklist(DexClass clazz) {
+ @Override
+ void addDependentsToWorklist(DexClass clazz) {
@SuppressWarnings("unchecked")
T clazzWithTypeT = (T) clazz;
@@ -83,20 +42,20 @@
// Add super classes to worklist.
if (clazz.superType != null) {
- DexClass definition = definitions.definitionFor(clazz.superType);
+ DexClass definition = appView.definitionFor(clazz.superType);
if (definition != null) {
if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
- addAncestorsToWorklist(definition);
+ addDependentsToWorklist(definition);
}
}
}
// Add super interfaces to worklist.
for (DexType interfaceType : clazz.interfaces.values) {
- DexClass definition = definitions.definitionFor(interfaceType);
+ DexClass definition = appView.definitionFor(interfaceType);
if (definition != null) {
if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) {
- addAncestorsToWorklist(definition);
+ addDependentsToWorklist(definition);
}
}
}
