blob: 83b09c3a0142d6fcfc368a5d5f01e592ad46b454 [file] [log] [blame]
// 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 com.android.tools.r8.errors.Unreachable;
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, CHT extends ClassHierarchyTraversal<T, CHT>> {
enum Scope {
ALL_CLASSES,
ONLY_LIBRARY_CLASSES,
ONLY_LIBRARY_AND_CLASSPATH_CLASSES,
ONLY_PROGRAM_CLASSES;
public boolean shouldBePassedToVisitor(DexClass clazz) {
switch (this) {
case ALL_CLASSES:
return true;
case ONLY_LIBRARY_CLASSES:
return clazz.isLibraryClass();
case ONLY_LIBRARY_AND_CLASSPATH_CLASSES:
return clazz.isLibraryClass() || clazz.isClasspathClass();
case ONLY_PROGRAM_CLASSES:
return clazz.isProgramClass();
default:
throw new Unreachable();
}
}
}
final AppView<? extends AppInfoWithClassHierarchy> appView;
final Scope scope;
final Set<DexClass> visited = new HashSet<>();
final Deque<T> worklist = new ArrayDeque<>();
boolean excludeInterfaces = false;
ClassHierarchyTraversal(AppView<? extends AppInfoWithClassHierarchy> appView, Scope scope) {
this.appView = appView;
this.scope = scope;
}
abstract CHT self();
public CHT excludeInterfaces() {
this.excludeInterfaces = true;
return self();
}
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);
}