| // Copyright (c) 2018, 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; |
| |
| 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; |
| } |
| |
| /** |
| * 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 TopDownClassHierarchyTraversal<DexClass> forAllClasses( |
| DexDefinitionSupplier definitions) { |
| return new TopDownClassHierarchyTraversal<>(definitions, 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 TopDownClassHierarchyTraversal<DexProgramClass> forProgramClasses( |
| DexDefinitionSupplier definitions) { |
| return new TopDownClassHierarchyTraversal<>(definitions, 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) { |
| @SuppressWarnings("unchecked") |
| T clazzWithTypeT = (T) clazz; |
| |
| if (visited.contains(clazzWithTypeT)) { |
| return; |
| } |
| |
| worklist.addFirst(clazzWithTypeT); |
| |
| // Add super classes to worklist. |
| if (clazz.superType != null) { |
| DexClass definition = definitions.definitionFor(clazz.superType); |
| if (definition != null) { |
| if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) { |
| addAncestorsToWorklist(definition); |
| } |
| } |
| } |
| |
| // Add super interfaces to worklist. |
| for (DexType interfaceType : clazz.interfaces.values) { |
| DexClass definition = definitions.definitionFor(interfaceType); |
| if (definition != null) { |
| if (scope != Scope.ONLY_PROGRAM_CLASSES || definition.isProgramClass()) { |
| addAncestorsToWorklist(definition); |
| } |
| } |
| } |
| } |
| } |