blob: 9272226dd69c74f368ed16a1c834238e62b90ba3 [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.cf.code;
import static com.android.tools.r8.utils.BiPredicateUtils.or;
import com.android.tools.r8.cf.code.CfFrame.FrameType;
import com.android.tools.r8.graph.CfCodeStackMapValidatingException;
import com.android.tools.r8.graph.DexItemFactory;
import com.android.tools.r8.graph.DexType;
import com.android.tools.r8.graph.GraphLens;
import com.android.tools.r8.utils.MapUtils;
import com.android.tools.r8.utils.collections.ImmutableDeque;
import com.android.tools.r8.utils.collections.ImmutableInt2ReferenceSortedMap;
import com.google.common.collect.Sets;
import it.unimi.dsi.fastutil.ints.Int2ReferenceAVLTreeMap;
import it.unimi.dsi.fastutil.ints.Int2ReferenceSortedMap;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.function.BiPredicate;
public class CfFrameVerificationHelper {
private final CfFrame NO_FRAME =
new CfFrame(
ImmutableInt2ReferenceSortedMap.<FrameType>builder().build(), ImmutableDeque.of());
private final Deque<FrameType> throwStack;
private CfFrame currentFrame = NO_FRAME;
private final DexType context;
private final Map<CfLabel, CfFrame> stateMap;
private final BiPredicate<DexType, DexType> isJavaAssignable;
private final DexItemFactory factory;
private final List<CfTryCatch> tryCatchRanges;
private final GraphLens graphLens;
private final int maxStackHeight;
private final Deque<CfTryCatch> currentCatchRanges = new ArrayDeque<>();
private final Set<CfLabel> tryCatchRangeLabels;
public CfFrameVerificationHelper(
DexType context,
Map<CfLabel, CfFrame> stateMap,
List<CfTryCatch> tryCatchRanges,
BiPredicate<DexType, DexType> isJavaAssignable,
DexItemFactory factory,
GraphLens graphLens,
int maxStackHeight) {
this.context = context;
this.stateMap = stateMap;
this.tryCatchRanges = tryCatchRanges;
this.isJavaAssignable = isJavaAssignable;
this.factory = factory;
this.graphLens = graphLens;
this.maxStackHeight = maxStackHeight;
throwStack = ImmutableDeque.of(FrameType.initialized(factory.throwableType));
// Compute all labels that marks a start or end to catch ranges.
tryCatchRangeLabels = Sets.newIdentityHashSet();
for (CfTryCatch tryCatchRange : tryCatchRanges) {
tryCatchRangeLabels.add(tryCatchRange.start);
tryCatchRangeLabels.add(tryCatchRange.end);
}
}
public DexItemFactory factory() {
return factory;
}
public FrameType readLocal(int index, DexType expectedType) {
checkFrameIsSet();
FrameType frameType = currentFrame.getLocals().get(index);
if (frameType == null) {
throw CfCodeStackMapValidatingException.error("No local at index " + index);
}
checkIsAssignable(
frameType,
expectedType,
or(
this::isUninitializedThisAndTarget,
this::isUninitializedNewAndTarget,
this::isAssignableAndInitialized));
return frameType;
}
public void storeLocal(int index, FrameType frameType) {
checkFrameIsSet();
currentFrame.getLocals().put(index, frameType);
}
public FrameType pop() {
checkFrameIsSet();
if (currentFrame.getStack().isEmpty()) {
throw CfCodeStackMapValidatingException.error("Cannot pop() from an empty stack");
}
return currentFrame.getStack().removeLast();
}
public FrameType popInitialized(DexType expectedType) {
return pop(expectedType, this::isAssignableAndInitialized);
}
public FrameType pop(DexType expectedType, BiPredicate<FrameType, DexType> isAssignable) {
FrameType frameType = pop();
checkIsAssignable(frameType, expectedType, isAssignable);
return frameType;
}
public CfFrameVerificationHelper popAndDiscardInitialized(DexType... expectedTypes) {
checkFrameIsSet();
for (int i = expectedTypes.length - 1; i >= 0; i--) {
popInitialized(expectedTypes[i]);
}
return this;
}
public FrameType pop(FrameType expectedType) {
FrameType frameType = pop();
checkIsAssignable(frameType, expectedType);
return frameType;
}
public CfFrameVerificationHelper popAndDiscard(FrameType... expectedTypes) {
checkFrameIsSet();
for (int i = expectedTypes.length - 1; i >= 0; i--) {
pop(expectedTypes[i]);
}
return this;
}
public void popAndInitialize(DexType context, DexType methodHolder) {
checkFrameIsSet();
FrameType objectRef =
pop(
factory.objectType,
or(this::isUninitializedThisAndTarget, this::isUninitializedNewAndTarget));
CfFrame newFrame =
currentFrame.markInstantiated(
objectRef, objectRef.isUninitializedNew() ? methodHolder : context);
setNoFrame();
checkFrameAndSet(newFrame);
}
public CfFrameVerificationHelper push(FrameType type) {
checkFrameIsSet();
currentFrame.getStack().addLast(type);
if (currentFrame.computeStackSize() > maxStackHeight) {
throw CfCodeStackMapValidatingException.error(
"The max stack height of "
+ maxStackHeight
+ " is violated when pushing type "
+ type
+ " to existing stack of size "
+ currentFrame.getStack().size());
}
return this;
}
public CfFrameVerificationHelper push(DexType type) {
return push(FrameType.initialized(type));
}
public CfFrameVerificationHelper seenLabel(CfLabel label) {
if (tryCatchRangeLabels.contains(label)) {
for (CfTryCatch tryCatchRange : tryCatchRanges) {
if (tryCatchRange.start == label) {
currentCatchRanges.add(tryCatchRange);
// We can have fall-through into this range requiring the current frame being
// assignable to the handler frame. This is handled for locals when we see a throwing
// instruction, but we can validate here that the stack will be a single element stack
// [throwable].
CfFrame destinationFrame = stateMap.get(tryCatchRange.start);
if (destinationFrame == null) {
throw CfCodeStackMapValidatingException.error("No frame for target catch range target");
}
checkStackIsAssignable(
destinationFrame.getStack(), throwStack, factory, isJavaAssignable);
}
}
currentCatchRanges.removeIf(currentRange -> currentRange.end == label);
}
return this;
}
private void checkFrameIsSet() {
if (currentFrame == NO_FRAME) {
throw CfCodeStackMapValidatingException.error("Unexpected state change");
}
}
public void checkFrameAndSet(CfFrame newFrame) {
if (currentFrame != NO_FRAME) {
checkFrame(newFrame);
}
setFrame(newFrame);
}
private void setFrame(CfFrame frame) {
assert frame != NO_FRAME;
currentFrame =
new CfFrame(
new Int2ReferenceAVLTreeMap<>(frame.getLocals()), new ArrayDeque<>(frame.getStack()));
}
public void checkExceptionEdges() {
for (CfTryCatch currentCatchRange : currentCatchRanges) {
for (CfLabel target : currentCatchRange.targets) {
CfFrame destinationFrame = stateMap.get(target);
if (destinationFrame == null) {
throw CfCodeStackMapValidatingException.error("No frame for target catch range target");
}
// We have to check all current handler targets have assignable locals and a 1-element
// stack assignable to throwable. It is not required that the the thrown error is
// handled.
checkLocalsIsAssignable(
currentFrame.getLocals(), destinationFrame.getLocals(), factory, isJavaAssignable);
}
}
}
public CfFrame getFrame() {
return currentFrame;
}
public void checkTarget(CfLabel label) {
checkFrame(stateMap.get(label));
}
public void checkFrame(CfFrame destinationFrame) {
if (destinationFrame == null) {
throw CfCodeStackMapValidatingException.error("No destination frame");
}
checkFrame(destinationFrame.getLocals(), destinationFrame.getStack());
}
public void checkFrame(Int2ReferenceSortedMap<FrameType> locals, Deque<FrameType> stack) {
checkIsAssignable(
currentFrame.getLocals(),
currentFrame.getStack(),
locals,
stack,
factory,
isJavaAssignable);
}
public void setNoFrame() {
currentFrame = NO_FRAME;
}
public boolean isUninitializedThisAndTarget(FrameType source, DexType target) {
if (!source.isUninitializedThis()) {
return false;
}
return target == factory.objectType || graphLens.lookupClassType(target) == context;
}
public boolean isUninitializedNewAndTarget(FrameType source, DexType target) {
if (!source.isUninitializedNew()) {
return false;
}
return target == factory.objectType || graphLens.lookupClassType(target) == context;
}
public boolean isAssignableAndInitialized(FrameType source, DexType target) {
if (!source.isInitialized()) {
return false;
}
return isJavaAssignable.test(source.getInitializedType(), target);
}
public void checkIsAssignable(
FrameType source, DexType target, BiPredicate<FrameType, DexType> predicate) {
if (predicate.test(source, target)) {
return;
}
throw CfCodeStackMapValidatingException.error(
"The expected type " + source + " is not assignable to " + target.toSourceString());
}
public void checkIsAssignable(FrameType source, FrameType target) {
if (!canBeAssigned(source, target, factory, isJavaAssignable)) {
throw CfCodeStackMapValidatingException.error(
"The expected type " + source + " is not assignable to " + target);
}
}
// Based on https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1.4.
public static void checkIsAssignable(
Int2ReferenceSortedMap<FrameType> sourceLocals,
Deque<FrameType> sourceStack,
Int2ReferenceSortedMap<FrameType> destLocals,
Deque<FrameType> destStack,
DexItemFactory factory,
BiPredicate<DexType, DexType> isJavaAssignable) {
checkLocalsIsAssignable(sourceLocals, destLocals, factory, isJavaAssignable);
checkStackIsAssignable(sourceStack, destStack, factory, isJavaAssignable);
}
private static void checkLocalsIsAssignable(
Int2ReferenceSortedMap<FrameType> sourceLocals,
Int2ReferenceSortedMap<FrameType> destLocals,
DexItemFactory factory,
BiPredicate<DexType, DexType> isJavaAssignable) {
final int localsLastKey = sourceLocals.isEmpty() ? -1 : sourceLocals.lastIntKey();
final int otherLocalsLastKey = destLocals.isEmpty() ? -1 : destLocals.lastIntKey();
if (localsLastKey < otherLocalsLastKey) {
throw CfCodeStackMapValidatingException.error(
"Source locals "
+ MapUtils.toString(sourceLocals)
+ " have different local indices than "
+ MapUtils.toString(destLocals));
}
for (int i = 0; i < otherLocalsLastKey; i++) {
final FrameType sourceType =
sourceLocals.containsKey(i) ? sourceLocals.get(i) : FrameType.top();
final FrameType destinationType =
destLocals.containsKey(i) ? destLocals.get(i) : FrameType.top();
if (!canBeAssigned(sourceType, destinationType, factory, isJavaAssignable)) {
throw CfCodeStackMapValidatingException.error(
"Could not assign '"
+ MapUtils.toString(sourceLocals)
+ "' to '"
+ MapUtils.toString(destLocals)
+ "'. The local at index "
+ i
+ " with '"
+ sourceType
+ "' not being assignable to '"
+ destinationType
+ "'");
}
}
}
private static void checkStackIsAssignable(
Deque<FrameType> sourceStack,
Deque<FrameType> destStack,
DexItemFactory factory,
BiPredicate<DexType, DexType> isJavaAssignable) {
if (sourceStack.size() != destStack.size()) {
throw CfCodeStackMapValidatingException.error(
"Source stack "
+ Arrays.toString(sourceStack.toArray())
+ " and destination stack "
+ Arrays.toString(destStack.toArray())
+ " is not the same size");
}
final Iterator<FrameType> otherIterator = destStack.iterator();
int i = 0;
for (FrameType sourceType : sourceStack) {
final FrameType destinationType = otherIterator.next();
if (!canBeAssigned(sourceType, destinationType, factory, isJavaAssignable)) {
throw CfCodeStackMapValidatingException.error(
"Could not assign '"
+ Arrays.toString(sourceStack.toArray())
+ "' to '"
+ Arrays.toString(destStack.toArray())
+ "'. The stack value at index "
+ i
+ " (from bottom) with '"
+ sourceType
+ "' not being assignable to '"
+ destinationType
+ "'");
}
i++;
}
}
// Based on https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1.2.
public static boolean canBeAssigned(
FrameType source,
FrameType target,
DexItemFactory factory,
BiPredicate<DexType, DexType> isJavaAssignable) {
if (target.isTop()) {
return true;
}
if (source.isTop()) {
return false;
}
if (source.isWide() != target.isWide()) {
return false;
}
if (target.isOneWord() || target.isTwoWord()) {
return true;
}
if (source.isUninitializedThis() && target.isUninitializedThis()) {
return true;
}
if (source.isUninitializedNew() && target.isUninitializedNew()) {
// TODO(b/168190134): Allow for picking the offset from the target if not set.
DexType uninitializedNewTypeSource = source.getUninitializedNewType();
DexType uninitializedNewTypeTarget = target.getUninitializedNewType();
return uninitializedNewTypeSource == null
|| uninitializedNewTypeTarget == null
|| uninitializedNewTypeSource == uninitializedNewTypeTarget;
}
// TODO(b/168190267): Clean-up the lattice.
if (!source.isInitialized()
&& target.isInitialized()
&& target.getInitializedType() == factory.objectType) {
return true;
}
if (source.isInitialized() && target.isInitialized()) {
// Both are instantiated types and we resort to primitive tyoe/java type hierarchy checking.
return isJavaAssignable.test(source.getInitializedType(), target.getInitializedType());
}
return false;
}
}