1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/src/clojure/asm/Label.java	Sat Aug 21 06:25:44 2010 -0400
     1.3 @@ -0,0 +1,437 @@
     1.4 +/***
     1.5 + * ASM: a very small and fast Java bytecode manipulation framework
     1.6 + * Copyright (c) 2000-2005 INRIA, France Telecom
     1.7 + * All rights reserved.
     1.8 + *
     1.9 + * Redistribution and use in source and binary forms, with or without
    1.10 + * modification, are permitted provided that the following conditions
    1.11 + * are met:
    1.12 + * 1. Redistributions of source code must retain the above copyright
    1.13 + *    notice, this list of conditions and the following disclaimer.
    1.14 + * 2. Redistributions in binary form must reproduce the above copyright
    1.15 + *    notice, this list of conditions and the following disclaimer in the
    1.16 + *    documentation and/or other materials provided with the distribution.
    1.17 + * 3. Neither the name of the copyright holders nor the names of its
    1.18 + *    contributors may be used to endorse or promote products derived from
    1.19 + *    this software without specific prior written permission.
    1.20 + *
    1.21 + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
    1.22 + * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
    1.23 + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
    1.24 + * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
    1.25 + * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    1.26 + * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
    1.27 + * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
    1.28 + * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
    1.29 + * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
    1.30 + * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
    1.31 + * THE POSSIBILITY OF SUCH DAMAGE.
    1.32 + */
    1.33 +package clojure.asm;
    1.34 +
    1.35 +/**
    1.36 + * A label represents a position in the bytecode of a method. Labels are used
    1.37 + * for jump, goto, and switch instructions, and for try catch blocks.
    1.38 + *
    1.39 + * @author Eric Bruneton
    1.40 + */
    1.41 +public class Label{
    1.42 +
    1.43 +/**
    1.44 + * Indicates if this label is only used for debug attributes. Such a label
    1.45 + * is not the start of a basic block, the target of a jump instruction, or
    1.46 + * an exception handler. It can be safely ignored in control flow graph
    1.47 + * analysis algorithms (for optimization purposes).
    1.48 + */
    1.49 +final static int DEBUG = 1;
    1.50 +
    1.51 +/**
    1.52 + * Indicates if the position of this label is known.
    1.53 + */
    1.54 +final static int RESOLVED = 2;
    1.55 +
    1.56 +/**
    1.57 + * Indicates if this label has been updated, after instruction resizing.
    1.58 + */
    1.59 +final static int RESIZED = 4;
    1.60 +
    1.61 +/**
    1.62 + * Indicates if this basic block has been pushed in the basic block stack.
    1.63 + * See {@link MethodWriter#visitMaxs visitMaxs}.
    1.64 + */
    1.65 +final static int PUSHED = 8;
    1.66 +
    1.67 +/**
    1.68 + * Indicates if this label is the target of a jump instruction, or the start
    1.69 + * of an exception handler.
    1.70 + */
    1.71 +final static int TARGET = 16;
    1.72 +
    1.73 +/**
    1.74 + * Indicates if a stack map frame must be stored for this label.
    1.75 + */
    1.76 +final static int STORE = 32;
    1.77 +
    1.78 +/**
    1.79 + * Indicates if this label corresponds to a reachable basic block.
    1.80 + */
    1.81 +final static int REACHABLE = 64;
    1.82 +
    1.83 +/**
    1.84 + * Indicates if this basic block ends with a JSR instruction.
    1.85 + */
    1.86 +final static int JSR = 128;
    1.87 +
    1.88 +/**
    1.89 + * Indicates if this basic block ends with a RET instruction.
    1.90 + */
    1.91 +final static int RET = 256;
    1.92 +
    1.93 +/**
    1.94 + * Field used to associate user information to a label.
    1.95 + */
    1.96 +public Object info;
    1.97 +
    1.98 +/**
    1.99 + * Flags that indicate the status of this label.
   1.100 + *
   1.101 + * @see #DEBUG
   1.102 + * @see #RESOLVED
   1.103 + * @see #RESIZED
   1.104 + * @see #PUSHED
   1.105 + * @see #TARGET
   1.106 + * @see #STORE
   1.107 + * @see #REACHABLE
   1.108 + * @see #JSR
   1.109 + * @see #RET
   1.110 + */
   1.111 +int status;
   1.112 +
   1.113 +/**
   1.114 + * The line number corresponding to this label, if known.
   1.115 + */
   1.116 +int line;
   1.117 +
   1.118 +/**
   1.119 + * The position of this label in the code, if known.
   1.120 + */
   1.121 +int position;
   1.122 +
   1.123 +/**
   1.124 + * Number of forward references to this label, times two.
   1.125 + */
   1.126 +private int referenceCount;
   1.127 +
   1.128 +/**
   1.129 + * Informations about forward references. Each forward reference is
   1.130 + * described by two consecutive integers in this array: the first one is the
   1.131 + * position of the first byte of the bytecode instruction that contains the
   1.132 + * forward reference, while the second is the position of the first byte of
   1.133 + * the forward reference itself. In fact the sign of the first integer
   1.134 + * indicates if this reference uses 2 or 4 bytes, and its absolute value
   1.135 + * gives the position of the bytecode instruction.
   1.136 + */
   1.137 +private int[] srcAndRefPositions;
   1.138 +
   1.139 +// ------------------------------------------------------------------------
   1.140 +
   1.141 +/*
   1.142 +	 * Fields for the control flow and data flow graph analysis algorithms (used
   1.143 +	 * to compute the maximum stack size or the stack map frames). A control
   1.144 +	 * flow graph contains one node per "basic block", and one edge per "jump"
   1.145 +	 * from one basic block to another. Each node (i.e., each basic block) is
   1.146 +	 * represented by the Label object that corresponds to the first instruction
   1.147 +	 * of this basic block. Each node also stores the list of its successors in
   1.148 +	 * the graph, as a linked list of Edge objects.
   1.149 +	 *
   1.150 +	 * The control flow analysis algorithms used to compute the maximum stack
   1.151 +	 * size or the stack map frames are similar and use two steps. The first
   1.152 +	 * step, during the visit of each instruction, builds information about the
   1.153 +	 * state of the local variables and the operand stack at the end of each
   1.154 +	 * basic block, called the "output frame", <i>relatively</i> to the frame
   1.155 +	 * state at the beginning of the basic block, which is called the "input
   1.156 +	 * frame", and which is <i>unknown</i> during this step. The second step,
   1.157 +	 * in {@link MethodWriter#visitMaxs}, is a fix point algorithm that
   1.158 +	 * computes information about the input frame of each basic block, from the
   1.159 +	 * input state of the first basic block (known from the method signature),
   1.160 +	 * and by the using the previously computed relative output frames.
   1.161 +	 *
   1.162 +	 * The algorithm used to compute the maximum stack size only computes the
   1.163 +	 * relative output and absolute input stack heights, while the algorithm
   1.164 +	 * used to compute stack map frames computes relative output frames and
   1.165 +	 * absolute input frames.
   1.166 +	 */
   1.167 +
   1.168 +/**
   1.169 + * Start of the output stack relatively to the input stack. The exact
   1.170 + * semantics of this field depends on the algorithm that is used.
   1.171 + * <p/>
   1.172 + * When only the maximum stack size is computed, this field is the number of
   1.173 + * elements in the input stack.
   1.174 + * <p/>
   1.175 + * When the stack map frames are completely computed, this field is the
   1.176 + * offset of the first output stack element relatively to the top of the
   1.177 + * input stack. This offset is always negative or null. A null offset means
   1.178 + * that the output stack must be appended to the input stack. A -n offset
   1.179 + * means that the first n output stack elements must replace the top n input
   1.180 + * stack elements, and that the other elements must be appended to the input
   1.181 + * stack.
   1.182 + */
   1.183 +int inputStackTop;
   1.184 +
   1.185 +/**
   1.186 + * Maximum height reached by the output stack, relatively to the top of the
   1.187 + * input stack. This maximum is always positive or null.
   1.188 + */
   1.189 +int outputStackMax;
   1.190 +
   1.191 +/**
   1.192 + * Information about the input and output stack map frames of this basic
   1.193 + * block. This field is only used when {@link ClassWriter#COMPUTE_FRAMES}
   1.194 + * option is used.
   1.195 + */
   1.196 +Frame frame;
   1.197 +
   1.198 +/**
   1.199 + * The successor of this label, in the order they are visited. This linked
   1.200 + * list does not include labels used for debug info only. If
   1.201 + * {@link ClassWriter#COMPUTE_FRAMES} option is used then, in addition, it
   1.202 + * does not contain successive labels that denote the same bytecode position
   1.203 + * (in this case only the first label appears in this list).
   1.204 + */
   1.205 +Label successor;
   1.206 +
   1.207 +/**
   1.208 + * The successors of this node in the control flow graph. These successors
   1.209 + * are stored in a linked list of {@link Edge Edge} objects, linked to each
   1.210 + * other by their {@link Edge#next} field.
   1.211 + */
   1.212 +Edge successors;
   1.213 +
   1.214 +/**
   1.215 + * The next basic block in the basic block stack. This stack is used in the
   1.216 + * main loop of the fix point algorithm used in the second step of the
   1.217 + * control flow analysis algorithms.
   1.218 + *
   1.219 + * @see MethodWriter#visitMaxs
   1.220 + */
   1.221 +Label next;
   1.222 +
   1.223 +// ------------------------------------------------------------------------
   1.224 +// Constructor
   1.225 +// ------------------------------------------------------------------------
   1.226 +
   1.227 +/**
   1.228 + * Constructs a new label.
   1.229 + */
   1.230 +public Label(){
   1.231 +}
   1.232 +
   1.233 +/**
   1.234 + * Constructs a new label.
   1.235 + *
   1.236 + * @param debug if this label is only used for debug attributes.
   1.237 + */
   1.238 +Label(final boolean debug){
   1.239 +	this.status = debug ? DEBUG : 0;
   1.240 +}
   1.241 +
   1.242 +// ------------------------------------------------------------------------
   1.243 +// Methods to compute offsets and to manage forward references
   1.244 +// ------------------------------------------------------------------------
   1.245 +
   1.246 +/**
   1.247 + * Returns the offset corresponding to this label. This offset is computed
   1.248 + * from the start of the method's bytecode. <i>This method is intended for
   1.249 + * {@link Attribute} sub classes, and is normally not needed by class
   1.250 + * generators or adapters.</i>
   1.251 + *
   1.252 + * @return the offset corresponding to this label.
   1.253 + * @throws IllegalStateException if this label is not resolved yet.
   1.254 + */
   1.255 +public int getOffset(){
   1.256 +	if((status & RESOLVED) == 0)
   1.257 +		{
   1.258 +		throw new IllegalStateException("Label offset position has not been resolved yet");
   1.259 +		}
   1.260 +	return position;
   1.261 +}
   1.262 +
   1.263 +/**
   1.264 + * Puts a reference to this label in the bytecode of a method. If the
   1.265 + * position of the label is known, the offset is computed and written
   1.266 + * directly. Otherwise, a null offset is written and a new forward reference
   1.267 + * is declared for this label.
   1.268 + *
   1.269 + * @param owner      the code writer that calls this method.
   1.270 + * @param out        the bytecode of the method.
   1.271 + * @param source     the position of first byte of the bytecode instruction that
   1.272 + *                   contains this label.
   1.273 + * @param wideOffset <tt>true</tt> if the reference must be stored in 4
   1.274 + *                   bytes, or <tt>false</tt> if it must be stored with 2 bytes.
   1.275 + * @throws IllegalArgumentException if this label has not been created by
   1.276 + *                                  the given code writer.
   1.277 + */
   1.278 +void put(
   1.279 +		final MethodWriter owner,
   1.280 +		final ByteVector out,
   1.281 +		final int source,
   1.282 +		final boolean wideOffset){
   1.283 +	if((status & RESOLVED) != 0)
   1.284 +		{
   1.285 +		if(wideOffset)
   1.286 +			{
   1.287 +			out.putInt(position - source);
   1.288 +			}
   1.289 +		else
   1.290 +			{
   1.291 +			out.putShort(position - source);
   1.292 +			}
   1.293 +		}
   1.294 +	else
   1.295 +		{
   1.296 +		if(wideOffset)
   1.297 +			{
   1.298 +			addReference(-1 - source, out.length);
   1.299 +			out.putInt(-1);
   1.300 +			}
   1.301 +		else
   1.302 +			{
   1.303 +			addReference(source, out.length);
   1.304 +			out.putShort(-1);
   1.305 +			}
   1.306 +		}
   1.307 +}
   1.308 +
   1.309 +/**
   1.310 + * Adds a forward reference to this label. This method must be called only
   1.311 + * for a true forward reference, i.e. only if this label is not resolved
   1.312 + * yet. For backward references, the offset of the reference can be, and
   1.313 + * must be, computed and stored directly.
   1.314 + *
   1.315 + * @param sourcePosition    the position of the referencing instruction. This
   1.316 + *                          position will be used to compute the offset of this forward
   1.317 + *                          reference.
   1.318 + * @param referencePosition the position where the offset for this forward
   1.319 + *                          reference must be stored.
   1.320 + */
   1.321 +private void addReference(
   1.322 +		final int sourcePosition,
   1.323 +		final int referencePosition){
   1.324 +	if(srcAndRefPositions == null)
   1.325 +		{
   1.326 +		srcAndRefPositions = new int[6];
   1.327 +		}
   1.328 +	if(referenceCount >= srcAndRefPositions.length)
   1.329 +		{
   1.330 +		int[] a = new int[srcAndRefPositions.length + 6];
   1.331 +		System.arraycopy(srcAndRefPositions,
   1.332 +		                 0,
   1.333 +		                 a,
   1.334 +		                 0,
   1.335 +		                 srcAndRefPositions.length);
   1.336 +		srcAndRefPositions = a;
   1.337 +		}
   1.338 +	srcAndRefPositions[referenceCount++] = sourcePosition;
   1.339 +	srcAndRefPositions[referenceCount++] = referencePosition;
   1.340 +}
   1.341 +
   1.342 +/**
   1.343 + * Resolves all forward references to this label. This method must be called
   1.344 + * when this label is added to the bytecode of the method, i.e. when its
   1.345 + * position becomes known. This method fills in the blanks that where left
   1.346 + * in the bytecode by each forward reference previously added to this label.
   1.347 + *
   1.348 + * @param owner    the code writer that calls this method.
   1.349 + * @param position the position of this label in the bytecode.
   1.350 + * @param data     the bytecode of the method.
   1.351 + * @return <tt>true</tt> if a blank that was left for this label was to
   1.352 + *         small to store the offset. In such a case the corresponding jump
   1.353 + *         instruction is replaced with a pseudo instruction (using unused
   1.354 + *         opcodes) using an unsigned two bytes offset. These pseudo
   1.355 + *         instructions will need to be replaced with true instructions with
   1.356 + *         wider offsets (4 bytes instead of 2). This is done in
   1.357 + *         {@link MethodWriter#resizeInstructions}.
   1.358 + * @throws IllegalArgumentException if this label has already been resolved,
   1.359 + *                                  or if it has not been created by the given code writer.
   1.360 + */
   1.361 +boolean resolve(
   1.362 +		final MethodWriter owner,
   1.363 +		final int position,
   1.364 +		final byte[] data){
   1.365 +	boolean needUpdate = false;
   1.366 +	this.status |= RESOLVED;
   1.367 +	this.position = position;
   1.368 +	int i = 0;
   1.369 +	while(i < referenceCount)
   1.370 +		{
   1.371 +		int source = srcAndRefPositions[i++];
   1.372 +		int reference = srcAndRefPositions[i++];
   1.373 +		int offset;
   1.374 +		if(source >= 0)
   1.375 +			{
   1.376 +			offset = position - source;
   1.377 +			if(offset < Short.MIN_VALUE || offset > Short.MAX_VALUE)
   1.378 +				{
   1.379 +				/*
   1.380 +									 * changes the opcode of the jump instruction, in order to
   1.381 +									 * be able to find it later (see resizeInstructions in
   1.382 +									 * MethodWriter). These temporary opcodes are similar to
   1.383 +									 * jump instruction opcodes, except that the 2 bytes offset
   1.384 +									 * is unsigned (and can therefore represent values from 0 to
   1.385 +									 * 65535, which is sufficient since the size of a method is
   1.386 +									 * limited to 65535 bytes).
   1.387 +									 */
   1.388 +				int opcode = data[reference - 1] & 0xFF;
   1.389 +				if(opcode <= Opcodes.JSR)
   1.390 +					{
   1.391 +					// changes IFEQ ... JSR to opcodes 202 to 217
   1.392 +					data[reference - 1] = (byte) (opcode + 49);
   1.393 +					}
   1.394 +				else
   1.395 +					{
   1.396 +					// changes IFNULL and IFNONNULL to opcodes 218 and 219
   1.397 +					data[reference - 1] = (byte) (opcode + 20);
   1.398 +					}
   1.399 +				needUpdate = true;
   1.400 +				}
   1.401 +			data[reference++] = (byte) (offset >>> 8);
   1.402 +			data[reference] = (byte) offset;
   1.403 +			}
   1.404 +		else
   1.405 +			{
   1.406 +			offset = position + source + 1;
   1.407 +			data[reference++] = (byte) (offset >>> 24);
   1.408 +			data[reference++] = (byte) (offset >>> 16);
   1.409 +			data[reference++] = (byte) (offset >>> 8);
   1.410 +			data[reference] = (byte) offset;
   1.411 +			}
   1.412 +		}
   1.413 +	return needUpdate;
   1.414 +}
   1.415 +
   1.416 +/**
   1.417 + * Returns the first label of the series to which this label belongs. For an
   1.418 + * isolated label or for the first label in a series of successive labels,
   1.419 + * this method returns the label itself. For other labels it returns the
   1.420 + * first label of the series.
   1.421 + *
   1.422 + * @return the first label of the series to which this label belongs.
   1.423 + */
   1.424 +Label getFirst(){
   1.425 +	return frame == null ? this : frame.owner;
   1.426 +}
   1.427 +
   1.428 +// ------------------------------------------------------------------------
   1.429 +// Overriden Object methods
   1.430 +// ------------------------------------------------------------------------
   1.431 +
   1.432 +/**
   1.433 + * Returns a string representation of this label.
   1.434 + *
   1.435 + * @return a string representation of this label.
   1.436 + */
   1.437 +public String toString(){
   1.438 +	return "L" + System.identityHashCode(this);
   1.439 +}
   1.440 +}