dalvik/dx/src/com/android/dx/cf/code/Frame.java

   1 /*
   2  * Copyright (C) 2007 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 package com.android.dx.cf.code;
  18
  19 import com.android.dx.rop.cst.CstType;
  20 import com.android.dx.rop.type.StdTypeList;
  21 import com.android.dx.rop.type.Type;
  22 import com.android.dx.util.ExceptionWithContext;
  23 import com.android.dx.util.IntList;
  24
  25 /**
  26  * Representation of a Java method execution frame. A frame consists
  27  * of a set of locals and a value stack, and it can be told to act on
  28  * them to load and store values between them and an "arguments /
  29  * results" area.
  30  */
  31 public final class Frame {
  32     /** {@code non-null;} the locals */
  33     private final LocalsArray locals;
  34
  35     /** {@code non-null;} the stack */
  36     private final ExecutionStack stack;
  37
  38     /** {@code null-ok;} stack of labels of subroutines that this block is nested in */
  39     private final IntList subroutines;
  40
  41     /**
  42      * Constructs an instance.
  43      *
  44      * @param locals {@code non-null;} the locals array to use
  45      * @param stack {@code non-null;} the execution stack to use
  46      */
  47     private Frame(LocalsArray locals, ExecutionStack stack) {
  48         this(locals, stack, IntList.EMPTY);
  49     }
  50
  51     /**
  52      * Constructs an instance.
  53      *
  54      * @param locals {@code non-null;} the locals array to use
  55      * @param stack {@code non-null;} the execution stack to use
  56      * @param subroutines {@code non-null;} list of subroutine start labels for
  57      * subroutines this frame is nested in
  58      */
  59     private Frame(LocalsArray locals,
  60             ExecutionStack stack, IntList subroutines) {
  61         if (locals == null) {
  62             throw new NullPointerException("locals == null");
  63         }
  64
  65         if (stack == null) {
  66             throw new NullPointerException("stack == null");
  67         }
  68
  69         subroutines.throwIfMutable();
  70
  71         this.locals = locals;
  72         this.stack = stack;
  73         this.subroutines = subroutines;
  74     }
  75
  76     /**
  77      * Constructs an instance. The locals array initially consists of
  78      * all-uninitialized values (represented as {@code null}s) and
  79      * the stack starts out empty.
  80      *
  81      * @param maxLocals {@code >= 0;} the maximum number of locals this instance
  82      * can refer to
  83      * @param maxStack {@code >= 0;} the maximum size of the stack for this
  84      * instance
  85      */
  86     public Frame(int maxLocals, int maxStack) {
  87         this(new OneLocalsArray(maxLocals), new ExecutionStack(maxStack));
  88     }
  89
  90     /**
  91      * Makes and returns a mutable copy of this instance. The copy
  92      * contains copies of the locals and stack (that is, it doesn't
  93      * share them with the original).
  94      *
  95      * @return {@code non-null;} the copy
  96      */
  97     public Frame copy() {
  98         return new Frame(locals.copy(), stack.copy(), subroutines);
  99     }
 100
 101     /**
 102      * Makes this instance immutable.
 103      */
 104     public void setImmutable() {
 105         locals.setImmutable();
 106         stack.setImmutable();
 107         // "subroutines" is always immutable
 108     }
 109
 110     /**
 111      * Replaces all the occurrences of the given uninitialized type in
 112      * this frame with its initialized equivalent.
 113      *
 114      * @param type {@code non-null;} type to replace
 115      */
 116     public void makeInitialized(Type type) {
 117         locals.makeInitialized(type);
 118         stack.makeInitialized(type);
 119     }
 120
 121     /**
 122      * Gets the locals array for this instance.
 123      *
 124      * @return {@code non-null;} the locals array
 125      */
 126     public LocalsArray getLocals() {
 127         return locals;
 128     }
 129
 130     /**
 131      * Gets the execution stack for this instance.
 132      *
 133      * @return {@code non-null;} the execution stack
 134      */
 135     public ExecutionStack getStack() {
 136         return stack;
 137     }
 138
 139     /**
 140      * Returns the largest subroutine nesting this block may be in. An
 141      * empty list is returned if this block is not in any subroutine.
 142      * Subroutines are identified by the label of their start block. The
 143      * list is ordered such that the deepest nesting (the actual subroutine
 144      * this block is in) is the last label in the list.
 145      *
 146      * @return {@code non-null;} list as noted above
 147      */
 148     public IntList getSubroutines() {
 149         return subroutines;
 150     }
 151
 152     /**
 153      * Initialize this frame with the method's parameters. Used for the first
 154      * frame.
 155      *
 156      * @param params Type list of method parameters.
 157      */
 158     public void initializeWithParameters(StdTypeList params) {
 159         int at = 0;
 160         int sz = params.size();
 161
 162         for (int i = 0; i < sz; i++) {
 163              Type one = params.get(i);
 164              locals.set(at, one);
 165              at += one.getCategory();
 166         }
 167     }
 168
 169     /**
 170      * Returns a Frame instance representing the frame state that should
 171      * be used when returning from a subroutine. The stack state of all
 172      * subroutine invocations is identical, but the locals state may differ.
 173      *
 174      * @param startLabel {@code >=0;} The label of the returning subroutine's
 175      * start block
 176      * @param subLabel {@code >=0;} A calling label of a subroutine
 177      * @return {@code null-ok;} an appropriatly-constructed instance, or null
 178      * if label is not in the set
 179      */
 180     public Frame subFrameForLabel(int startLabel, int subLabel) {
 181         LocalsArray subLocals = null;
 182
 183         if (locals instanceof LocalsArraySet) {
 184             subLocals = ((LocalsArraySet)locals).subArrayForLabel(subLabel);
 185         }
 186
 187         IntList newSubroutines;
 188         try {
 189             newSubroutines = subroutines.mutableCopy();
 190
 191             if (newSubroutines.pop() != startLabel) {
 192                 throw new RuntimeException("returning from invalid subroutine");
 193             }
 194             newSubroutines.setImmutable();
 195         } catch (IndexOutOfBoundsException ex) {
 196             throw new RuntimeException("returning from invalid subroutine");
 197         } catch (NullPointerException ex) {
 198             throw new NullPointerException("can't return from non-subroutine");
 199         }
 200
 201         return (subLocals == null) ? null
 202                 : new Frame(subLocals, stack, newSubroutines);
 203     }
 204
 205     /**
 206      * Merges two frames. If the merged result is the same as this frame,
 207      * then this instance is returned.
 208      *
 209      * @param other {@code non-null;} another frame
 210      * @return {@code non-null;} the result of merging the two frames
 211      */
 212     public Frame mergeWith(Frame other) {
 213         LocalsArray resultLocals;
 214         ExecutionStack resultStack;
 215         IntList resultSubroutines;
 216
 217         resultLocals = getLocals().merge(other.getLocals());
 218         resultStack = getStack().merge(other.getStack());
 219         resultSubroutines = mergeSubroutineLists(other.subroutines);
 220
 221         resultLocals = adjustLocalsForSubroutines(
 222                 resultLocals, resultSubroutines);
 223
 224         if ((resultLocals == getLocals())
 225                 && (resultStack == getStack())
 226                 && subroutines == resultSubroutines) {
 227             return this;
 228         }
 229
 230         return new Frame(resultLocals, resultStack, resultSubroutines);
 231     }
 232
 233     /**
 234      * Merges this frame's subroutine lists with another. The result
 235      * is the deepest common nesting (effectively, the common prefix of the
 236      * two lists).
 237      *
 238      * @param otherSubroutines label list of subroutine start blocks, from
 239      * least-nested to most-nested.
 240      * @return {@code non-null;} merged subroutine nest list as described above
 241      */
 242     private IntList mergeSubroutineLists(IntList otherSubroutines) {
 243         if (subroutines.equals(otherSubroutines)) {
 244             return subroutines;
 245         }
 246
 247         IntList resultSubroutines = new IntList();
 248
 249         int szSubroutines = subroutines.size();
 250         int szOthers = otherSubroutines.size();
 251         for (int i = 0; i < szSubroutines && i < szOthers
 252                 && (subroutines.get(i) == otherSubroutines.get(i)); i++) {
 253             resultSubroutines.add(i);
 254         }
 255
 256         resultSubroutines.setImmutable();
 257
 258         return resultSubroutines;
 259     }
 260
 261     /**
 262      * Adjusts a locals array to account for a merged subroutines list.
 263      * If a frame merge results in, effectively, a subroutine return through
 264      * a throw then the current locals will be a LocalsArraySet that will
 265      * need to be trimmed of all OneLocalsArray elements that relevent to
 266      * the subroutine that is returning.
 267      *
 268      * @param locals {@code non-null;} LocalsArray from before a merge
 269      * @param subroutines {@code non-null;} a label list of subroutine start blocks
 270      * representing the subroutine nesting of the block being merged into.
 271      * @return {@code non-null;} locals set appropriate for merge
 272      */
 273     private static LocalsArray adjustLocalsForSubroutines(
 274             LocalsArray locals, IntList subroutines) {
 275         if (! (locals instanceof LocalsArraySet)) {
 276             // nothing to see here
 277             return locals;
 278         }
 279
 280         LocalsArraySet laSet = (LocalsArraySet)locals;
 281
 282         if (subroutines.size() == 0) {
 283             /*
 284              * We've merged from a subroutine context to a non-subroutine
 285              * context, likely via a throw. Our successor will only need
 286              * to consider the primary locals state, not the state of
 287              * all possible subroutine paths.
 288              */
 289
 290             return laSet.getPrimary();
 291         }
 292
 293         /*
 294          * It's unclear to me if the locals set needs to be trimmed here.
 295          * If it does, then I believe it is all of the calling blocks
 296          * in the subroutine at the end of "subroutines" passed into
 297          * this method that should be removed.
 298          */
 299         return laSet;
 300     }
 301
 302     /**
 303      * Merges this frame with the frame of a subroutine caller at
 304      * {@code predLabel}. Only called on the frame at the first
 305      * block of a subroutine.
 306      *
 307      * @param other {@code non-null;} another frame
 308      * @param subLabel label of subroutine start block
 309      * @param predLabel label of calling block
 310      * @return {@code non-null;} the result of merging the two frames
 311      */
 312     public Frame mergeWithSubroutineCaller(Frame other, int subLabel,
 313             int predLabel) {
 314         LocalsArray resultLocals;
 315         ExecutionStack resultStack;
 316
 317         resultLocals = getLocals().mergeWithSubroutineCaller(
 318                 other.getLocals(), predLabel);
 319         resultStack = getStack().merge(other.getStack());
 320
 321         IntList newOtherSubroutines = other.subroutines.mutableCopy();
 322         newOtherSubroutines.add(subLabel);
 323         newOtherSubroutines.setImmutable();
 324
 325         if ((resultLocals == getLocals())
 326                 && (resultStack == getStack())
 327                 && subroutines.equals(newOtherSubroutines)) {
 328             return this;
 329         }
 330
 331         IntList resultSubroutines;
 332
 333         if (subroutines.equals(newOtherSubroutines)) {
 334             resultSubroutines = subroutines;
 335         } else {
 336             /*
 337              * The new subroutines list should be the deepest of the two
 338              * lists being merged, but the postfix of the resultant list
 339              * must be equal to the shorter list.
 340              */
 341             IntList nonResultSubroutines;
 342
 343             if (subroutines.size() > newOtherSubroutines.size()) {
 344                 resultSubroutines = subroutines;
 345                 nonResultSubroutines = newOtherSubroutines;
 346             } else {
 347                 resultSubroutines = newOtherSubroutines;
 348                 nonResultSubroutines = subroutines;
 349             }
 350
 351             int szResult = resultSubroutines.size();
 352             int szNonResult = nonResultSubroutines.size();
 353
 354             for (int i = szNonResult - 1; i >=0; i-- ) {
 355                 if (nonResultSubroutines.get(i)
 356                         != resultSubroutines.get(
 357                         i + (szResult - szNonResult))) {
 358                     throw new
 359                             RuntimeException("Incompatible merged subroutines");
 360                 }
 361             }
 362
 363         }
 364
 365         return new Frame(resultLocals, resultStack, resultSubroutines);
 366     }
 367
 368     /**
 369      * Makes a frame for a subroutine start block, given that this is the
 370      * ending frame of one of the subroutine's calling blocks. Subroutine
 371      * calls may be nested and thus may have nested locals state, so we
 372      * start with an initial state as seen by the subroutine, but keep track
 373      * of the individual locals states that will be expected when the individual
 374      * subroutine calls return.
 375      *
 376      * @param subLabel label of subroutine start block
 377      * @param callerLabel {@code >=0;} label of the caller block where this frame
 378      * came from.
 379      * @return a new instance to begin a called subroutine.
 380      */
 381     public Frame makeNewSubroutineStartFrame(int subLabel, int callerLabel) {
 382         IntList newSubroutines = subroutines.mutableCopy();
 383         newSubroutines.add(subLabel);
 384         Frame newFrame = new Frame(locals.getPrimary(), stack,
 385                 IntList.makeImmutable(subLabel));
 386         return newFrame.mergeWithSubroutineCaller(this, subLabel, callerLabel);
 387     }
 388
 389     /**
 390      * Makes a new frame for an exception handler block invoked from this
 391      * frame.
 392      *
 393      * @param exceptionClass exception that the handler block will handle
 394      * @return new frame
 395      */
 396     public Frame makeExceptionHandlerStartFrame(CstType exceptionClass) {
 397         ExecutionStack newStack = getStack().copy();
 398
 399         newStack.clear();
 400         newStack.push(exceptionClass);
 401
 402         return new Frame(getLocals(), newStack, subroutines);
 403     }
 404
 405     /**
 406      * Annotates (adds context to) the given exception with information
 407      * about this frame.
 408      *
 409      * @param ex {@code non-null;} the exception to annotate
 410      */
 411     public void annotate(ExceptionWithContext ex) {
 412         locals.annotate(ex);
 413         stack.annotate(ex);
 414     }
 415 }