dx/src/com/android/dx/cf/code/Frame.java - platform/dalvik-snapshot - Git at Google

 /*
  * Copyright (C) 2007 The Android Open Source Project
  *
  * Licensed under the Apache License, Version 2.0 (the "License");
  * you may not use this file except in compliance with the License.
  * You may obtain a copy of the License at
  *
  *      http://www.apache.org/licenses/LICENSE-2.0
  *
  * Unless required by applicable law or agreed to in writing, software
  * distributed under the License is distributed on an "AS IS" BASIS,
  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  * See the License for the specific language governing permissions and
  * limitations under the License.
  */

 package com.android.dx.cf.code;

 import com.android.dx.rop.cst.CstType;
 import com.android.dx.rop.type.StdTypeList;
 import com.android.dx.rop.type.Type;
 import com.android.dx.util.ExceptionWithContext;
 import com.android.dx.util.IntList;

 /**
  * Representation of a Java method execution frame. A frame consists
  * of a set of locals and a value stack, and it can be told to act on
  * them to load and store values between them and an "arguments /
  * results" area.
  */
 public final class Frame {
     /** {@code non-null;} the locals */
     private final LocalsArray locals;

     /** {@code non-null;} the stack */
     private final ExecutionStack stack;

     /** {@code null-ok;} stack of labels of subroutines that this block is nested in */
     private final IntList subroutines;

     /**
      * Constructs an instance.
      *
      * @param locals {@code non-null;} the locals array to use
      * @param stack {@code non-null;} the execution stack to use
      */
     private Frame(LocalsArray locals, ExecutionStack stack) {
         this(locals, stack, IntList.EMPTY);
     }

     /**
      * Constructs an instance.
      *
      * @param locals {@code non-null;} the locals array to use
      * @param stack {@code non-null;} the execution stack to use
      * @param subroutines {@code non-null;} list of subroutine start labels for
      * subroutines this frame is nested in
      */
     private Frame(LocalsArray locals,
             ExecutionStack stack, IntList subroutines) {
         if (locals == null) {
             throw new NullPointerException("locals == null");
         }

         if (stack == null) {
             throw new NullPointerException("stack == null");
         }

         subroutines.throwIfMutable();

         this.locals = locals;
         this.stack = stack;
         this.subroutines = subroutines;
     }

     /**
      * Constructs an instance. The locals array initially consists of
      * all-uninitialized values (represented as {@code null}s) and
      * the stack starts out empty.
      *
      * @param maxLocals {@code >= 0;} the maximum number of locals this instance
      * can refer to
      * @param maxStack {@code >= 0;} the maximum size of the stack for this
      * instance
      */
     public Frame(int maxLocals, int maxStack) {
         this(new OneLocalsArray(maxLocals), new ExecutionStack(maxStack));
     }

     /**
      * Makes and returns a mutable copy of this instance. The copy
      * contains copies of the locals and stack (that is, it doesn't
      * share them with the original).
      *
      * @return {@code non-null;} the copy
      */
     public Frame copy() {
         return new Frame(locals.copy(), stack.copy(), subroutines);
     }

     /**
      * Makes this instance immutable.
      */
     public void setImmutable() {
         locals.setImmutable();
         stack.setImmutable();
         // "subroutines" is always immutable
     }

     /**
      * Replaces all the occurrences of the given uninitialized type in
      * this frame with its initialized equivalent.
      *
      * @param type {@code non-null;} type to replace
      */
     public void makeInitialized(Type type) {
         locals.makeInitialized(type);
         stack.makeInitialized(type);
     }

     /**
      * Gets the locals array for this instance.
      *
      * @return {@code non-null;} the locals array
      */
     public LocalsArray getLocals() {
         return locals;
     }

     /**
      * Gets the execution stack for this instance.
      *
      * @return {@code non-null;} the execution stack
      */
     public ExecutionStack getStack() {
         return stack;
     }

     /**
      * Returns the largest subroutine nesting this block may be in. An
      * empty list is returned if this block is not in any subroutine.
      * Subroutines are identified by the label of their start block. The
      * list is ordered such that the deepest nesting (the actual subroutine
      * this block is in) is the last label in the list.
      *
      * @return {@code non-null;} list as noted above
      */
     public IntList getSubroutines() {
         return subroutines;
     }

     /**
      * Initialize this frame with the method's parameters. Used for the first
      * frame.
      *
      * @param params Type list of method parameters.
      */
     public void initializeWithParameters(StdTypeList params) {
         int at = 0;
         int sz = params.size();

         for (int i = 0; i < sz; i++) {
              Type one = params.get(i);
              locals.set(at, one);
              at += one.getCategory();
         }
     }

     /**
      * Returns a Frame instance representing the frame state that should
      * be used when returning from a subroutine. The stack state of all
      * subroutine invocations is identical, but the locals state may differ.
      *
      * @param startLabel {@code >=0;} The label of the returning subroutine's
      * start block
      * @param subLabel {@code >=0;} A calling label of a subroutine
      * @return {@code null-ok;} an appropriatly-constructed instance, or null
      * if label is not in the set
      */
     public Frame subFrameForLabel(int startLabel, int subLabel) {
         LocalsArray subLocals = null;

         if (locals instanceof LocalsArraySet) {
             subLocals = ((LocalsArraySet)locals).subArrayForLabel(subLabel);
         }

         IntList newSubroutines;
         try {
             newSubroutines = subroutines.mutableCopy();

             if (newSubroutines.pop() != startLabel) {
                 throw new RuntimeException("returning from invalid subroutine");
             }
             newSubroutines.setImmutable();
         } catch (IndexOutOfBoundsException ex) {
             throw new RuntimeException("returning from invalid subroutine");
         } catch (NullPointerException ex) {
             throw new NullPointerException("can't return from non-subroutine");
         }

         return (subLocals == null) ? null
                 : new Frame(subLocals, stack, newSubroutines);
     }

     /**
      * Merges two frames. If the merged result is the same as this frame,
      * then this instance is returned.
      *
      * @param other {@code non-null;} another frame
      * @return {@code non-null;} the result of merging the two frames
      */
     public Frame mergeWith(Frame other) {
         LocalsArray resultLocals;
         ExecutionStack resultStack;
         IntList resultSubroutines;

         resultLocals = getLocals().merge(other.getLocals());
         resultStack = getStack().merge(other.getStack());
         resultSubroutines = mergeSubroutineLists(other.subroutines);

         resultLocals = adjustLocalsForSubroutines(
                 resultLocals, resultSubroutines);

         if ((resultLocals == getLocals())
                 && (resultStack == getStack())
                 && subroutines == resultSubroutines) {
             return this;
         }

         return new Frame(resultLocals, resultStack, resultSubroutines);
     }

     /**
      * Merges this frame's subroutine lists with another. The result
      * is the deepest common nesting (effectively, the common prefix of the
      * two lists).
      *
      * @param otherSubroutines label list of subroutine start blocks, from
      * least-nested to most-nested.
      * @return {@code non-null;} merged subroutine nest list as described above
      */
     private IntList mergeSubroutineLists(IntList otherSubroutines) {
         if (subroutines.equals(otherSubroutines)) {
             return subroutines;
         }

         IntList resultSubroutines = new IntList();

         int szSubroutines = subroutines.size();
         int szOthers = otherSubroutines.size();
         for (int i = 0; i < szSubroutines && i < szOthers
                 && (subroutines.get(i) == otherSubroutines.get(i)); i++) {
             resultSubroutines.add(i);
         }

         resultSubroutines.setImmutable();

         return resultSubroutines;
     }

     /**
      * Adjusts a locals array to account for a merged subroutines list.
      * If a frame merge results in, effectively, a subroutine return through
      * a throw then the current locals will be a LocalsArraySet that will
      * need to be trimmed of all OneLocalsArray elements that relevent to
      * the subroutine that is returning.
      *
      * @param locals {@code non-null;} LocalsArray from before a merge
      * @param subroutines {@code non-null;} a label list of subroutine start blocks
      * representing the subroutine nesting of the block being merged into.
      * @return {@code non-null;} locals set appropriate for merge
      */
     private static LocalsArray adjustLocalsForSubroutines(
             LocalsArray locals, IntList subroutines) {
         if (! (locals instanceof LocalsArraySet)) {
             // nothing to see here
             return locals;
         }

         LocalsArraySet laSet = (LocalsArraySet)locals;

         if (subroutines.size() == 0) {
             /*
              * We've merged from a subroutine context to a non-subroutine
              * context, likely via a throw. Our successor will only need
              * to consider the primary locals state, not the state of
              * all possible subroutine paths.
              */

             return laSet.getPrimary();
         }

         /*
          * It's unclear to me if the locals set needs to be trimmed here.
          * If it does, then I believe it is all of the calling blocks
          * in the subroutine at the end of "subroutines" passed into
          * this method that should be removed.
          */
         return laSet;
     }

     /**
      * Merges this frame with the frame of a subroutine caller at
      * {@code predLabel}. Only called on the frame at the first
      * block of a subroutine.
      *
      * @param other {@code non-null;} another frame
      * @param subLabel label of subroutine start block
      * @param predLabel label of calling block
      * @return {@code non-null;} the result of merging the two frames
      */
     public Frame mergeWithSubroutineCaller(Frame other, int subLabel,
             int predLabel) {
         LocalsArray resultLocals;
         ExecutionStack resultStack;

         resultLocals = getLocals().mergeWithSubroutineCaller(
                 other.getLocals(), predLabel);
         resultStack = getStack().merge(other.getStack());

         IntList newOtherSubroutines = other.subroutines.mutableCopy();
         newOtherSubroutines.add(subLabel);
         newOtherSubroutines.setImmutable();

         if ((resultLocals == getLocals())
                 && (resultStack == getStack())
                 && subroutines.equals(newOtherSubroutines)) {
             return this;
         }

         IntList resultSubroutines;

         if (subroutines.equals(newOtherSubroutines)) {
             resultSubroutines = subroutines;
         } else {
             /*
              * The new subroutines list should be the deepest of the two
              * lists being merged, but the postfix of the resultant list
              * must be equal to the shorter list.
              */
             IntList nonResultSubroutines;

             if (subroutines.size() > newOtherSubroutines.size()) {
                 resultSubroutines = subroutines;
                 nonResultSubroutines = newOtherSubroutines;
             } else {
                 resultSubroutines = newOtherSubroutines;
                 nonResultSubroutines = subroutines;
             }

             int szResult = resultSubroutines.size();
             int szNonResult = nonResultSubroutines.size();

             for (int i = szNonResult - 1; i >=0; i-- ) {
                 if (nonResultSubroutines.get(i)
                         != resultSubroutines.get(
                         i + (szResult - szNonResult))) {
                     throw new
                             RuntimeException("Incompatible merged subroutines");
                 }
             }

         }

         return new Frame(resultLocals, resultStack, resultSubroutines);
     }

     /**
      * Makes a frame for a subroutine start block, given that this is the
      * ending frame of one of the subroutine's calling blocks. Subroutine
      * calls may be nested and thus may have nested locals state, so we
      * start with an initial state as seen by the subroutine, but keep track
      * of the individual locals states that will be expected when the individual
      * subroutine calls return.
      *
      * @param subLabel label of subroutine start block
      * @param callerLabel {@code >=0;} label of the caller block where this frame
      * came from.
      * @return a new instance to begin a called subroutine.
      */
     public Frame makeNewSubroutineStartFrame(int subLabel, int callerLabel) {
         IntList newSubroutines = subroutines.mutableCopy();
         newSubroutines.add(subLabel);
         Frame newFrame = new Frame(locals.getPrimary(), stack,
                 IntList.makeImmutable(subLabel));
         return newFrame.mergeWithSubroutineCaller(this, subLabel, callerLabel);
     }

     /**
      * Makes a new frame for an exception handler block invoked from this
      * frame.
      *
      * @param exceptionClass exception that the handler block will handle
      * @return new frame
      */
     public Frame makeExceptionHandlerStartFrame(CstType exceptionClass) {
         ExecutionStack newStack = getStack().copy();

         newStack.clear();
         newStack.push(exceptionClass);

         return new Frame(getLocals(), newStack, subroutines);
     }

     /**
      * Annotates (adds context to) the given exception with information
      * about this frame.
      *
      * @param ex {@code non-null;} the exception to annotate
      */
     public void annotate(ExceptionWithContext ex) {
         locals.annotate(ex);
         stack.annotate(ex);
     }
 }
	/*
	* Copyright (C) 2007 The Android Open Source Project
	*
	* Licensed under the Apache License, Version 2.0 (the "License");
	* you may not use this file except in compliance with the License.
	* You may obtain a copy of the License at
	*
	* http://www.apache.org/licenses/LICENSE-2.0
	*
	* Unless required by applicable law or agreed to in writing, software
	* distributed under the License is distributed on an "AS IS" BASIS,
	* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
	* See the License for the specific language governing permissions and
	* limitations under the License.
	*/

	package com.android.dx.cf.code;

	import com.android.dx.rop.cst.CstType;
	import com.android.dx.rop.type.StdTypeList;
	import com.android.dx.rop.type.Type;
	import com.android.dx.util.ExceptionWithContext;
	import com.android.dx.util.IntList;

	/**
	* Representation of a Java method execution frame. A frame consists
	* of a set of locals and a value stack, and it can be told to act on
	* them to load and store values between them and an "arguments /
	* results" area.
	*/
	public final class Frame {
	/** {@code non-null;} the locals */
	private final LocalsArray locals;

	/** {@code non-null;} the stack */
	private final ExecutionStack stack;

	/** {@code null-ok;} stack of labels of subroutines that this block is nested in */
	private final IntList subroutines;

	/**
	* Constructs an instance.
	*
	* @param locals {@code non-null;} the locals array to use
	* @param stack {@code non-null;} the execution stack to use
	*/
	private Frame(LocalsArray locals, ExecutionStack stack) {
	this(locals, stack, IntList.EMPTY);
	}

	/**
	* Constructs an instance.
	*
	* @param locals {@code non-null;} the locals array to use
	* @param stack {@code non-null;} the execution stack to use
	* @param subroutines {@code non-null;} list of subroutine start labels for
	* subroutines this frame is nested in
	*/
	private Frame(LocalsArray locals,
	ExecutionStack stack, IntList subroutines) {
	if (locals == null) {
	throw new NullPointerException("locals == null");
	}

	if (stack == null) {
	throw new NullPointerException("stack == null");
	}

	subroutines.throwIfMutable();

	this.locals = locals;
	this.stack = stack;
	this.subroutines = subroutines;
	}

	/**
	* Constructs an instance. The locals array initially consists of
	* all-uninitialized values (represented as {@code null}s) and
	* the stack starts out empty.
	*
	* @param maxLocals {@code >= 0;} the maximum number of locals this instance
	* can refer to
	* @param maxStack {@code >= 0;} the maximum size of the stack for this
	* instance
	*/
	public Frame(int maxLocals, int maxStack) {
	this(new OneLocalsArray(maxLocals), new ExecutionStack(maxStack));
	}

	/**
	* Makes and returns a mutable copy of this instance. The copy
	* contains copies of the locals and stack (that is, it doesn't
	* share them with the original).
	*
	* @return {@code non-null;} the copy
	*/
	public Frame copy() {
	return new Frame(locals.copy(), stack.copy(), subroutines);
	}

	/**
	* Makes this instance immutable.
	*/
	public void setImmutable() {
	locals.setImmutable();
	stack.setImmutable();
	// "subroutines" is always immutable
	}

	/**
	* Replaces all the occurrences of the given uninitialized type in
	* this frame with its initialized equivalent.
	*
	* @param type {@code non-null;} type to replace
	*/
	public void makeInitialized(Type type) {
	locals.makeInitialized(type);
	stack.makeInitialized(type);
	}

	/**
	* Gets the locals array for this instance.
	*
	* @return {@code non-null;} the locals array
	*/
	public LocalsArray getLocals() {
	return locals;
	}

	/**
	* Gets the execution stack for this instance.
	*
	* @return {@code non-null;} the execution stack
	*/
	public ExecutionStack getStack() {
	return stack;
	}

	/**
	* Returns the largest subroutine nesting this block may be in. An
	* empty list is returned if this block is not in any subroutine.
	* Subroutines are identified by the label of their start block. The
	* list is ordered such that the deepest nesting (the actual subroutine
	* this block is in) is the last label in the list.
	*
	* @return {@code non-null;} list as noted above
	*/
	public IntList getSubroutines() {
	return subroutines;
	}

	/**
	* Initialize this frame with the method's parameters. Used for the first
	* frame.
	*
	* @param params Type list of method parameters.
	*/
	public void initializeWithParameters(StdTypeList params) {
	int at = 0;
	int sz = params.size();

	for (int i = 0; i < sz; i++) {
	Type one = params.get(i);
	locals.set(at, one);
	at += one.getCategory();
	}
	}

	/**
	* Returns a Frame instance representing the frame state that should
	* be used when returning from a subroutine. The stack state of all
	* subroutine invocations is identical, but the locals state may differ.
	*
	* @param startLabel {@code >=0;} The label of the returning subroutine's
	* start block
	* @param subLabel {@code >=0;} A calling label of a subroutine
	* @return {@code null-ok;} an appropriatly-constructed instance, or null
	* if label is not in the set
	*/
	public Frame subFrameForLabel(int startLabel, int subLabel) {
	LocalsArray subLocals = null;

	if (locals instanceof LocalsArraySet) {
	subLocals = ((LocalsArraySet)locals).subArrayForLabel(subLabel);
	}

	IntList newSubroutines;
	try {
	newSubroutines = subroutines.mutableCopy();

	if (newSubroutines.pop() != startLabel) {
	throw new RuntimeException("returning from invalid subroutine");
	}
	newSubroutines.setImmutable();
	} catch (IndexOutOfBoundsException ex) {
	throw new RuntimeException("returning from invalid subroutine");
	} catch (NullPointerException ex) {
	throw new NullPointerException("can't return from non-subroutine");
	}

	return (subLocals == null) ? null
	: new Frame(subLocals, stack, newSubroutines);
	}

	/**
	* Merges two frames. If the merged result is the same as this frame,
	* then this instance is returned.
	*
	* @param other {@code non-null;} another frame
	* @return {@code non-null;} the result of merging the two frames
	*/
	public Frame mergeWith(Frame other) {
	LocalsArray resultLocals;
	ExecutionStack resultStack;
	IntList resultSubroutines;

	resultLocals = getLocals().merge(other.getLocals());
	resultStack = getStack().merge(other.getStack());
	resultSubroutines = mergeSubroutineLists(other.subroutines);

	resultLocals = adjustLocalsForSubroutines(
	resultLocals, resultSubroutines);

	if ((resultLocals == getLocals())
	&& (resultStack == getStack())
	&& subroutines == resultSubroutines) {
	return this;
	}

	return new Frame(resultLocals, resultStack, resultSubroutines);
	}

	/**
	* Merges this frame's subroutine lists with another. The result
	* is the deepest common nesting (effectively, the common prefix of the
	* two lists).
	*
	* @param otherSubroutines label list of subroutine start blocks, from
	* least-nested to most-nested.
	* @return {@code non-null;} merged subroutine nest list as described above
	*/
	private IntList mergeSubroutineLists(IntList otherSubroutines) {
	if (subroutines.equals(otherSubroutines)) {
	return subroutines;
	}

	IntList resultSubroutines = new IntList();

	int szSubroutines = subroutines.size();
	int szOthers = otherSubroutines.size();
	for (int i = 0; i < szSubroutines && i < szOthers
	&& (subroutines.get(i) == otherSubroutines.get(i)); i++) {
	resultSubroutines.add(i);
	}

	resultSubroutines.setImmutable();

	return resultSubroutines;
	}

	/**
	* Adjusts a locals array to account for a merged subroutines list.
	* If a frame merge results in, effectively, a subroutine return through
	* a throw then the current locals will be a LocalsArraySet that will
	* need to be trimmed of all OneLocalsArray elements that relevent to
	* the subroutine that is returning.
	*
	* @param locals {@code non-null;} LocalsArray from before a merge
	* @param subroutines {@code non-null;} a label list of subroutine start blocks
	* representing the subroutine nesting of the block being merged into.
	* @return {@code non-null;} locals set appropriate for merge
	*/
	private static LocalsArray adjustLocalsForSubroutines(
	LocalsArray locals, IntList subroutines) {
	if (! (locals instanceof LocalsArraySet)) {
	// nothing to see here
	return locals;
	}

	LocalsArraySet laSet = (LocalsArraySet)locals;

	if (subroutines.size() == 0) {
	/*
	* We've merged from a subroutine context to a non-subroutine
	* context, likely via a throw. Our successor will only need
	* to consider the primary locals state, not the state of
	* all possible subroutine paths.
	*/

	return laSet.getPrimary();
	}

	/*
	* It's unclear to me if the locals set needs to be trimmed here.
	* If it does, then I believe it is all of the calling blocks
	* in the subroutine at the end of "subroutines" passed into
	* this method that should be removed.
	*/
	return laSet;
	}

	/**
	* Merges this frame with the frame of a subroutine caller at
	* {@code predLabel}. Only called on the frame at the first
	* block of a subroutine.
	*
	* @param other {@code non-null;} another frame
	* @param subLabel label of subroutine start block
	* @param predLabel label of calling block
	* @return {@code non-null;} the result of merging the two frames
	*/
	public Frame mergeWithSubroutineCaller(Frame other, int subLabel,
	int predLabel) {
	LocalsArray resultLocals;
	ExecutionStack resultStack;

	resultLocals = getLocals().mergeWithSubroutineCaller(
	other.getLocals(), predLabel);
	resultStack = getStack().merge(other.getStack());

	IntList newOtherSubroutines = other.subroutines.mutableCopy();
	newOtherSubroutines.add(subLabel);
	newOtherSubroutines.setImmutable();

	if ((resultLocals == getLocals())
	&& (resultStack == getStack())
	&& subroutines.equals(newOtherSubroutines)) {
	return this;
	}

	IntList resultSubroutines;

	if (subroutines.equals(newOtherSubroutines)) {
	resultSubroutines = subroutines;
	} else {
	/*
	* The new subroutines list should be the deepest of the two
	* lists being merged, but the postfix of the resultant list
	* must be equal to the shorter list.
	*/
	IntList nonResultSubroutines;

	if (subroutines.size() > newOtherSubroutines.size()) {
	resultSubroutines = subroutines;
	nonResultSubroutines = newOtherSubroutines;
	} else {
	resultSubroutines = newOtherSubroutines;
	nonResultSubroutines = subroutines;
	}

	int szResult = resultSubroutines.size();
	int szNonResult = nonResultSubroutines.size();

	for (int i = szNonResult - 1; i >=0; i-- ) {
	if (nonResultSubroutines.get(i)
	!= resultSubroutines.get(
	i + (szResult - szNonResult))) {
	throw new
	RuntimeException("Incompatible merged subroutines");
	}
	}

	}

	return new Frame(resultLocals, resultStack, resultSubroutines);
	}

	/**
	* Makes a frame for a subroutine start block, given that this is the
	* ending frame of one of the subroutine's calling blocks. Subroutine
	* calls may be nested and thus may have nested locals state, so we
	* start with an initial state as seen by the subroutine, but keep track
	* of the individual locals states that will be expected when the individual
	* subroutine calls return.
	*
	* @param subLabel label of subroutine start block
	* @param callerLabel {@code >=0;} label of the caller block where this frame
	* came from.
	* @return a new instance to begin a called subroutine.
	*/
	public Frame makeNewSubroutineStartFrame(int subLabel, int callerLabel) {
	IntList newSubroutines = subroutines.mutableCopy();
	newSubroutines.add(subLabel);
	Frame newFrame = new Frame(locals.getPrimary(), stack,
	IntList.makeImmutable(subLabel));
	return newFrame.mergeWithSubroutineCaller(this, subLabel, callerLabel);
	}

	/**
	* Makes a new frame for an exception handler block invoked from this
	* frame.
	*
	* @param exceptionClass exception that the handler block will handle
	* @return new frame
	*/
	public Frame makeExceptionHandlerStartFrame(CstType exceptionClass) {
	ExecutionStack newStack = getStack().copy();

	newStack.clear();
	newStack.push(exceptionClass);

	return new Frame(getLocals(), newStack, subroutines);
	}

	/**
	* Annotates (adds context to) the given exception with information
	* about this frame.
	*
	* @param ex {@code non-null;} the exception to annotate
	*/
	public void annotate(ExceptionWithContext ex) {
	locals.annotate(ex);
	stack.annotate(ex);
	}
	}