src/main/java/com/android/tools/r8/cf/code/CfFrameVerificationHelper.java - r8 - Git at Google

 // 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.CfAssignability.AssignabilityResult;
 import com.android.tools.r8.cf.code.CfFrame.FrameType;
 import com.android.tools.r8.graph.AppView;
 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.utils.collections.ImmutableDeque;
 import com.google.common.collect.Sets;
 import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMap;
 import java.util.ArrayDeque;
 import java.util.Deque;
 import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.function.BiPredicate;

 public class CfFrameVerificationHelper {

   private static final CfFrame NO_FRAME = new CfFrame();

   private final AppView<?> appView;
   private final DexItemFactory factory;

   private CfFrame currentFrame = NO_FRAME;
   private final DexType context;
   private final Map<CfLabel, CfFrame> stateMap;
   private final List<CfTryCatch> tryCatchRanges;
   private final int maxStackHeight;

   private final Deque<CfTryCatch> currentCatchRanges = new ArrayDeque<>();
   private final Set<CfLabel> tryCatchRangeLabels;

   public CfFrameVerificationHelper(
       AppView<?> appView,
       DexType context,
       Map<CfLabel, CfFrame> stateMap,
       List<CfTryCatch> tryCatchRanges,
       int maxStackHeight) {
     this.appView = appView;
     this.context = context;
     this.stateMap = stateMap;
     this.tryCatchRanges = tryCatchRanges;
     this.factory = appView.dexItemFactory();
     this.maxStackHeight = maxStackHeight;
     // 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 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 expectedType) {
     checkFrameIsSet();
     popInitialized(expectedType);
     return this;
   }

   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);
         }
       }
       currentCatchRanges.removeIf(currentRange -> currentRange.end == label);
     }
     return this;
   }

   public void checkTryCatchRange(CfTryCatch tryCatchRange) {
     // According to the spec:
     // https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1
     // saying ` and the handler's target (the initial instruction of the handler code) is type
     // safe assuming an incoming type state T. The type state T is derived from ExcStackFrame
     // by replacing the operand stack with a stack whose sole element is the handler's
     // exception class.
     tryCatchRange.targets.forEach(
         target -> {
           CfFrame destinationFrame = stateMap.get(target);
           if (destinationFrame == null) {
             throw CfCodeStackMapValidatingException.error("No frame for target catch range target");
           }
           // From the spec: the handler's exception class is assignable to the class Throwable.
           tryCatchRange.guards.forEach(
               guard -> {
                 if (!CfAssignability.isAssignable(guard, factory.throwableType, appView)) {
                   throw CfCodeStackMapValidatingException.error(
                       "Could not assign '" + guard.toSourceString() + "' to throwable.");
                 }
                 checkStackIsAssignable(
                     ImmutableDeque.of(FrameType.initialized(guard)), destinationFrame.getStack());
               });
         });
   }

   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 = frame.mutableCopy();
   }

   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");
         }
         checkLocalsIsAssignable(currentFrame.getLocals(), destinationFrame.getLocals());
       }
     }
   }

   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(Int2ObjectSortedMap<FrameType> locals, Deque<FrameType> stack) {
     checkIsAssignable(currentFrame.getLocals(), currentFrame.getStack(), locals, stack);
   }

   public void setNoFrame() {
     currentFrame = NO_FRAME;
   }

   public boolean isUninitializedThisAndTarget(FrameType source, DexType target) {
     if (!source.isUninitializedThis()) {
       return false;
     }
     return target == factory.objectType || target == context;
   }

   public boolean isUninitializedNewAndTarget(FrameType source, DexType target) {
     if (!source.isUninitializedNew()) {
       return false;
     }
     return target == factory.objectType || target == context;
   }

   public boolean isAssignableAndInitialized(FrameType source, DexType target) {
     if (!source.isInitialized()) {
       return false;
     }
     return CfAssignability.isAssignable(source.getInitializedType(factory), target, appView);
   }

   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 (!CfAssignability.isFrameTypeAssignable(source, target, appView)) {
       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.
   private void checkIsAssignable(
       Int2ObjectSortedMap<FrameType> sourceLocals,
       Deque<FrameType> sourceStack,
       Int2ObjectSortedMap<FrameType> destLocals,
       Deque<FrameType> destStack) {
     checkLocalsIsAssignable(sourceLocals, destLocals);
     checkStackIsAssignable(sourceStack, destStack);
   }

   private void checkLocalsIsAssignable(
       Int2ObjectSortedMap<FrameType> sourceLocals, Int2ObjectSortedMap<FrameType> destLocals) {
     AssignabilityResult result =
         CfAssignability.isLocalsAssignable(sourceLocals, destLocals, appView);
     if (result.isFailed()) {
       throw CfCodeStackMapValidatingException.error(result.asFailed().getMessage());
     }
   }

   private void checkStackIsAssignable(Deque<FrameType> sourceStack, Deque<FrameType> destStack) {
     AssignabilityResult result = CfAssignability.isStackAssignable(sourceStack, destStack, appView);
     if (result.isFailed()) {
       throw CfCodeStackMapValidatingException.error(result.asFailed().getMessage());
     }
   }
 }
	// 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.CfAssignability.AssignabilityResult;
	import com.android.tools.r8.cf.code.CfFrame.FrameType;
	import com.android.tools.r8.graph.AppView;
	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.utils.collections.ImmutableDeque;
	import com.google.common.collect.Sets;
	import it.unimi.dsi.fastutil.ints.Int2ObjectSortedMap;
	import java.util.ArrayDeque;
	import java.util.Deque;
	import java.util.List;
	import java.util.Map;
	import java.util.Set;
	import java.util.function.BiPredicate;

	public class CfFrameVerificationHelper {

	private static final CfFrame NO_FRAME = new CfFrame();

	private final AppView<?> appView;
	private final DexItemFactory factory;

	private CfFrame currentFrame = NO_FRAME;
	private final DexType context;
	private final Map<CfLabel, CfFrame> stateMap;
	private final List<CfTryCatch> tryCatchRanges;
	private final int maxStackHeight;

	private final Deque<CfTryCatch> currentCatchRanges = new ArrayDeque<>();
	private final Set<CfLabel> tryCatchRangeLabels;

	public CfFrameVerificationHelper(
	AppView<?> appView,
	DexType context,
	Map<CfLabel, CfFrame> stateMap,
	List<CfTryCatch> tryCatchRanges,
	int maxStackHeight) {
	this.appView = appView;
	this.context = context;
	this.stateMap = stateMap;
	this.tryCatchRanges = tryCatchRanges;
	this.factory = appView.dexItemFactory();
	this.maxStackHeight = maxStackHeight;
	// 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 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 expectedType) {
	checkFrameIsSet();
	popInitialized(expectedType);
	return this;
	}

	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);
	}
	}
	currentCatchRanges.removeIf(currentRange -> currentRange.end == label);
	}
	return this;
	}

	public void checkTryCatchRange(CfTryCatch tryCatchRange) {
	// According to the spec:
	// https://docs.oracle.com/javase/specs/jvms/se8/html/jvms-4.html#jvms-4.10.1
	// saying ` and the handler's target (the initial instruction of the handler code) is type
	// safe assuming an incoming type state T. The type state T is derived from ExcStackFrame
	// by replacing the operand stack with a stack whose sole element is the handler's
	// exception class.
	tryCatchRange.targets.forEach(
	target -> {
	CfFrame destinationFrame = stateMap.get(target);
	if (destinationFrame == null) {
	throw CfCodeStackMapValidatingException.error("No frame for target catch range target");
	}
	// From the spec: the handler's exception class is assignable to the class Throwable.
	tryCatchRange.guards.forEach(
	guard -> {
	if (!CfAssignability.isAssignable(guard, factory.throwableType, appView)) {
	throw CfCodeStackMapValidatingException.error(
	"Could not assign '" + guard.toSourceString() + "' to throwable.");
	}
	checkStackIsAssignable(
	ImmutableDeque.of(FrameType.initialized(guard)), destinationFrame.getStack());
	});
	});
	}

	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 = frame.mutableCopy();
	}

	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");
	}
	checkLocalsIsAssignable(currentFrame.getLocals(), destinationFrame.getLocals());
	}
	}
	}

	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(Int2ObjectSortedMap<FrameType> locals, Deque<FrameType> stack) {
	checkIsAssignable(currentFrame.getLocals(), currentFrame.getStack(), locals, stack);
	}

	public void setNoFrame() {
	currentFrame = NO_FRAME;
	}

	public boolean isUninitializedThisAndTarget(FrameType source, DexType target) {
	if (!source.isUninitializedThis()) {
	return false;
	}
	return target == factory.objectType \|\| target == context;
	}

	public boolean isUninitializedNewAndTarget(FrameType source, DexType target) {
	if (!source.isUninitializedNew()) {
	return false;
	}
	return target == factory.objectType \|\| target == context;
	}

	public boolean isAssignableAndInitialized(FrameType source, DexType target) {
	if (!source.isInitialized()) {
	return false;
	}
	return CfAssignability.isAssignable(source.getInitializedType(factory), target, appView);
	}

	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 (!CfAssignability.isFrameTypeAssignable(source, target, appView)) {
	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.
	private void checkIsAssignable(
	Int2ObjectSortedMap<FrameType> sourceLocals,
	Deque<FrameType> sourceStack,
	Int2ObjectSortedMap<FrameType> destLocals,
	Deque<FrameType> destStack) {
	checkLocalsIsAssignable(sourceLocals, destLocals);
	checkStackIsAssignable(sourceStack, destStack);
	}

	private void checkLocalsIsAssignable(
	Int2ObjectSortedMap<FrameType> sourceLocals, Int2ObjectSortedMap<FrameType> destLocals) {
	AssignabilityResult result =
	CfAssignability.isLocalsAssignable(sourceLocals, destLocals, appView);
	if (result.isFailed()) {
	throw CfCodeStackMapValidatingException.error(result.asFailed().getMessage());
	}
	}

	private void checkStackIsAssignable(Deque<FrameType> sourceStack, Deque<FrameType> destStack) {
	AssignabilityResult result = CfAssignability.isStackAssignable(sourceStack, destStack, appView);
	if (result.isFailed()) {
	throw CfCodeStackMapValidatingException.error(result.asFailed().getMessage());
	}
	}
	}