| // 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 { |
| |
| public static void visit( |
| AppView<? extends AppInfo> appView, |
| Iterable<DexProgramClass> classes, |
| Consumer<DexProgramClass> visitor) { |
| Deque<DexProgramClass> worklist = new ArrayDeque<>(); |
| Set<DexProgramClass> visited = new HashSet<>(); |
| |
| Iterator<DexProgramClass> classIterator = classes.iterator(); |
| |
| // Visit the program classes in a top-down order according to the class hierarchy. |
| while (classIterator.hasNext() || !worklist.isEmpty()) { |
| if (worklist.isEmpty()) { |
| // Add the ancestors of this class (including the class itself) to the worklist in such a |
| // way that all super types of the class come before the class itself. |
| addAncestorsToWorklist(classIterator.next(), worklist, visited, appView); |
| if (worklist.isEmpty()) { |
| continue; |
| } |
| } |
| |
| DexProgramClass clazz = worklist.removeFirst(); |
| if (visited.add(clazz)) { |
| visitor.accept(clazz); |
| } |
| } |
| } |
| |
| private static void addAncestorsToWorklist( |
| DexProgramClass clazz, |
| Deque<DexProgramClass> worklist, |
| Set<DexProgramClass> visited, |
| AppView<? extends AppInfo> appView) { |
| if (visited.contains(clazz)) { |
| return; |
| } |
| |
| worklist.addFirst(clazz); |
| |
| // Add super classes to worklist. |
| if (clazz.superType != null) { |
| DexClass definition = appView.appInfo().definitionFor(clazz.superType); |
| if (definition != null && definition.isProgramClass()) { |
| addAncestorsToWorklist(definition.asProgramClass(), worklist, visited, appView); |
| } |
| } |
| |
| // Add super interfaces to worklist. |
| for (DexType interfaceType : clazz.interfaces.values) { |
| DexClass definition = appView.appInfo().definitionFor(interfaceType); |
| if (definition != null && definition.isProgramClass()) { |
| addAncestorsToWorklist(definition.asProgramClass(), worklist, visited, appView); |
| } |
| } |
| } |
| } |