blob: afb02cd050755f1877957cf0f8cfb5443b89e784 [file] [log] [blame]
// Copyright (c) 2020, 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.horizontalclassmerging;
import com.android.tools.r8.graph.AppInfoWithClassHierarchy;
import com.android.tools.r8.graph.AppView;
import com.android.tools.r8.graph.DexProgramClass;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.IdentityHashMap;
import java.util.List;
import java.util.Map;
import java.util.function.BiFunction;
/**
* Calculates the subtyping forrest for all classes. Unlike {@link
* com.android.tools.r8.graph.SubtypingInfo}, interfaces are not included in this subtyping
* information and only the immediate parents are stored (i.e. the transitive parents are not
* calculated). In the following example graph, the roots are A, E and G, and each edge indicates an
* entry in {@link SubtypingForrestForClasses#subtypeMap} going from the parent to an entry in the
* collection of children. <code>
* A E G
* / \ |
* B C F
* |
* D
* </code>
*/
public class SubtypingForrestForClasses {
private final AppView<? extends AppInfoWithClassHierarchy> appView;
private final Collection<DexProgramClass> roots = new ArrayList<>();
private final Map<DexProgramClass, List<DexProgramClass>> subtypeMap = new IdentityHashMap<>();
public SubtypingForrestForClasses(AppView<? extends AppInfoWithClassHierarchy> appView) {
this.appView = appView;
calculateSubtyping(appView.appInfo().classes());
}
private DexProgramClass superClass(DexProgramClass clazz) {
return appView.programDefinitionFor(clazz.superType, clazz);
}
private void calculateSubtyping(Iterable<DexProgramClass> classes) {
classes.forEach(this::calculateSubtyping);
}
private void calculateSubtyping(DexProgramClass clazz) {
if (clazz.isInterface()) {
return;
}
DexProgramClass superClass = superClass(clazz);
if (superClass == null) {
roots.add(clazz);
} else {
subtypeMap.computeIfAbsent(superClass, ignore -> new ArrayList<>()).add(clazz);
}
}
public Collection<DexProgramClass> getProgramRoots() {
return roots;
}
public Collection<DexProgramClass> getSubtypesFor(DexProgramClass clazz) {
return subtypeMap.getOrDefault(clazz, Collections.emptyList());
}
public <T> T traverseNodeDepthFirst(
DexProgramClass clazz, T state, BiFunction<DexProgramClass, T, T> consumer) {
T newState = consumer.apply(clazz, state);
getSubtypesFor(clazz).forEach(subClazz -> traverseNodeDepthFirst(subClazz, newState, consumer));
return newState;
}
}