001 package edu.rice.cs.cunit.classFile.code;
002
003 import edu.rice.cs.cunit.classFile.attributes.CodeAttributeInfo;
004 import edu.rice.cs.cunit.classFile.code.instructions.AInstruction;
005 import edu.rice.cs.cunit.classFile.code.instructions.LineNumberTable;
006 import edu.rice.cs.cunit.classFile.constantPool.ConstantPool;
007
008 import java.io.ByteArrayOutputStream;
009 import java.io.IOException;
010 import java.util.LinkedList;
011 import java.util.ArrayList;
012
013 /**
014 * Represents a list of Java instructions.
015 *
016 * @author Mathias Ricken
017 */
018 public class InstructionList {
019 LinkedList<AInstruction> _instructionList = new LinkedList<AInstruction>();
020 protected int _index;
021 LineNumberTable _lnt;
022
023 /**
024 * Constructor.
025 *
026 * @param code bytecode
027 */
028 public InstructionList(byte[] code) {
029 setCode(code);
030 _index = 0;
031 }
032
033 /**
034 * Copy constructor.
035 *
036 * @param original original
037 */
038 public InstructionList(InstructionList original) {
039 _instructionList.addAll(original._instructionList);
040 _index = original._index;
041 _lnt = original._lnt;
042 }
043
044 /**
045 * Constructor.
046 *
047 * @param code bytecode
048 * @param index program index.
049 *
050 * @throws IndexOutOfBoundsException
051 */
052 public InstructionList(byte[] code, int index) throws IndexOutOfBoundsException {
053 this(code);
054 setIndex(index);
055 }
056
057 /**
058 * Return a human-readable version of the code.
059 *
060 * @return mnemonics
061 */
062 public String toString() {
063 return toString(true, true, null);
064 }
065
066 /**
067 * Return a human-readable version of the code.
068 * @param cp constant pool
069 * @return mnemonics
070 */
071 public String toString(ConstantPool cp) {
072 return toString(true, true, cp);
073 }
074
075 /**
076 * Return a human-readable version of the code.
077 *
078 * @param lineNumbers print line numbers
079 * @param PCs print PC values
080 * @param cp constant pool, or null if not verbose
081 * @return mnemonics
082 */
083 public String toString(boolean lineNumbers, boolean PCs, ConstantPool cp) {
084 StringBuilder x = new StringBuilder();
085
086 int index = 0;
087 int pc = 0;
088 for(AInstruction instr : _instructionList) {
089 if (lineNumbers) {
090 x.append(String.format("%5d", new Object[]{new Integer(index)}));
091 if (PCs) {
092 x.append(' ');
093 }
094 else {
095 x.append(": ");
096 }
097 }
098 if (PCs) {
099 x.append(String.format("(pc %5d): ", new Object[]{new Integer(pc)}));
100 }
101 if ((!lineNumbers) && (!PCs)) {
102 x.append(" ");
103 }
104 if (cp!=null) {
105 x.append(instr.toStringVerbose(cp));
106 }
107 else {
108 x.append(instr.toString());
109 }
110 x.append("\n");
111 pc += instr.getBytecodeLength(pc);
112 ++index;
113 }
114
115 return x.toString();
116 }
117
118 /**
119 * Accessor for the bytecode.
120 *
121 * @return bytecode
122 *
123 * @throws IllegalStateException
124 */
125 public byte[] getCode() throws IllegalStateException {
126 ByteArrayOutputStream baos = new ByteArrayOutputStream();
127 int pc = 0;
128 for(AInstruction instr : _instructionList) {
129 byte[] b = instr.getBytecode(pc, _lnt);
130 try {
131 baos.write(b);
132 }
133 catch(IOException e) {
134 throw new IllegalStateException("Could not generate bytecode", e);
135 }
136
137 pc += b.length;
138 }
139
140 return baos.toByteArray();
141 }
142
143 /**
144 * Mutator for the bytecode. This also resets the program counter to 0.
145 *
146 * @param code bytecode
147 */
148 public void setCode(byte[] code) {
149 _lnt = new LineNumberTable(code);
150
151 int pc = 0;
152 _instructionList = new LinkedList<AInstruction>();
153 while(pc < code.length) {
154 // make instruction and add it
155 _instructionList.addLast(AInstruction.makeInstruction(code, pc, pc, _lnt));
156
157 pc += Opcode.getInstrSize(code, pc);
158 }
159 if (pc != code.length) {
160 throw new IllegalArgumentException("Invalid bytecode length");
161 }
162 _index = 0;
163 }
164
165 /**
166 * Accessor for the program index.
167 *
168 * @return program index
169 */
170 public int getIndex() {
171 return _index;
172 }
173
174 /**
175 * Calculate the PC for an index.
176 *
177 * @param index index
178 *
179 * @return PC
180 */
181 public int getPCFromIndex(int index) {
182 int pc = 0;
183 for(int i = 0; i < index; ++i) {
184 pc += _instructionList.get(i).getBytecodeLength(pc);
185 }
186
187 return pc;
188 }
189
190 /**
191 * Get the length of the instruction list.
192 *
193 * @return length
194 */
195 public int getLength() {
196 return _instructionList.size();
197 }
198
199 /**
200 * Mutator for the program index.
201 *
202 * @param index new program index
203 *
204 * @throws IndexOutOfBoundsException
205 */
206 public void setIndex(int index) throws IndexOutOfBoundsException, IllegalArgumentException {
207 if ((index < 0) || (index >= _instructionList.size())) {
208 throw new IndexOutOfBoundsException(
209 "The program index (" + index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
210 }
211
212 _index = index;
213 }
214
215 /**
216 * Advance the program index by multiple instructions.
217 * @param count number of instructions
218 * @return true while the end of the instruction list has not been reached
219 */
220 public boolean advanceIndex(int count) {
221 while(count>0) {
222 if (!advanceIndex()) {
223 return false;
224 }
225 --count;
226 }
227 return true;
228 }
229
230 /**
231 * Advance the program index to the next instruction.
232 *
233 * @return true while the end of the instruction list has not been reached
234 */
235 public boolean advanceIndex() {
236 if (_index < 0) {
237 throw new IndexOutOfBoundsException(
238 "The program index (" + _index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
239 }
240 if (_index < _instructionList.size()) {
241 ++_index;
242 }
243 return (_index < _instructionList.size());
244 }
245
246 /**
247 * Rewind the program index by multiple instructions.
248 * @param count number of instructions
249 * @return true while the beginning of the instruction list has not been reached
250 */
251 public boolean rewindIndex(int count) {
252 while(count>0) {
253 if (!rewindIndex()) {
254 return false;
255 }
256 --count;
257 }
258 return true;
259 }
260
261 /**
262 * Rewind the program index to the previous instruction.
263 *
264 * @return true while the beginning of the instruction list has not been reached
265 */
266 public boolean rewindIndex() {
267 if (_index < 0) {
268 throw new IndexOutOfBoundsException(
269 "The program index (" + _index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
270 }
271 if (_index > 0) {
272 --_index;
273 }
274 return (_index > 0);
275 }
276
277 /**
278 * Return the opcode at the program index.
279 *
280 * @return opcode at program index
281 */
282 public byte getOpcode() {
283 if ((_index < 0) || (_index >= _instructionList.size())) {
284 throw new IndexOutOfBoundsException(
285 "The program index (" + _index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
286 }
287 return _instructionList.get(_index).getOpcode();
288 }
289
290 /**
291 * Return the instruction at the program index. This includes the code and the operands.
292 *
293 * @return instruction at program index
294 */
295 public AInstruction getInstr() {
296 if ((_index < 0) || (_index >= _instructionList.size())) {
297 throw new IndexOutOfBoundsException(
298 "The program index (" + _index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
299 }
300
301 return _instructionList.get(_index);
302 }
303
304 /**
305 * This method deletes the instruction at the program index. It also relocates all jumps. All jumps to places after
306 * the deletion point will be changed so that they still point to the same instruction. Jumps to the deletion point
307 * or to places before it are not changed. The index will remain unchanged. In case the program counter is past the
308 * end of the code block, false will be returned. If codeAttribute is non-null, the PCs in the CodeAttribute will be
309 * adjusted.
310 *
311 * @param codeAttribute CodeAttribute that contains this code block, or null if none
312 *
313 * @return true while the end of the code block has not been reached
314 */
315 public boolean deleteInstr(CodeAttributeInfo codeAttribute) {
316 if ((_index < 0) || (_index >= _instructionList.size())) {
317 throw new IndexOutOfBoundsException(
318 "The program index (" + _index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
319 }
320
321 byte[] oldCode = getCode();
322 int deletionPoint = _index;
323
324 // walk through all instructions and relocate jumps
325 InstructionList oldCodeBlock = new InstructionList(oldCode);
326 do {
327 if (Opcode.isBranch(oldCodeBlock.getOpcode())) {
328 // this is a branch, so we might have to relocate
329 int[] branchTargets = oldCodeBlock.getInstr().getBranchTargets();
330 for(int i = 0; i < branchTargets.length; ++i) {
331 // Debug.out.println("insertInstr: DP = "+deletionPoint+", PC="+oldCodeBlock.getPC()+", BT="+branchTargets[i]);
332 if ((branchTargets[i] > deletionPoint) || (branchTargets[i] == oldCodeBlock.getLength() - 1)) {
333 // the target of this instruction was the insertion point or somewhere past it
334 // we need to relocate
335 --branchTargets[i];
336
337 // Debug.out.println("\tnew BT="+branchTargets[i]);
338 }
339 }
340 oldCodeBlock.getInstr().setBranchTargets(branchTargets);
341 }
342 } while(oldCodeBlock.advanceIndex());
343
344 oldCodeBlock._instructionList.remove(deletionPoint);
345 oldCodeBlock._lnt = new LineNumberTable(oldCodeBlock);
346 byte[] newCode = oldCodeBlock.getCode();
347
348 if (codeAttribute != null) {
349 // adjust CodeAttribute PCs
350 codeAttribute.translatePC(deletionPoint, -1, _lnt, oldCodeBlock._lnt);
351 }
352
353 // transfer the code
354 setCode(newCode);
355
356 if (deletionPoint == getLength()) {
357 _index = getLength();
358 return false;
359 }
360 else {
361 setIndex(deletionPoint);
362 return true;
363 }
364 }
365
366
367 /**
368 * This method inserts the instruction at the program counter. The instruction currently at the program counter will
369 * be pushed towards the end of the bytecode array. It also relocates all jumps. Jumps to the insertion point or to
370 * places before it are not changed. Jumps to all other places will be changed so that they still point to the same
371 * instruction. That means that jumps to the instruction previously at the insertion point will now jump to the
372 * newly inserted instruction. If codeAttribute is non-null, the PCs in the CodeAttribute will be adjusted. The
373 * program counter will remain unchanged. If the inserted instruction itself contains jump targets, these will be
374 * relocated as well. Notice, though, that if the instruction contains a jump exactly to the insertion point, this
375 * jump will be relocated so that it points to the old instruction (this is the behavior of insertBeforeInstr).
376 * <p/>
377 * Assume the following code:
378 * 1. a
379 * 2. b
380 * 3. c
381 * 4. goto 1 // jump to place before insertion point
382 * 5. goto 2 // jump to insertion point
383 * 6. goto 3 // junp to place after insertion point
384 * The program counter is currently at 2, and the instruction x is inserted using insertInstr. The result is:
385 * 1. a
386 * 2. x // inserted
387 * 3. b
388 * 4. c
389 * 5. goto 1 // not changed
390 * 6. goto 2 // not changed
391 * 7. goto 4 // changed
392 * <p/>
393 * Relocation of branches in the instruction inserted.
394 * Type : jump to place before insertion point
395 * Action : not changed
396 * Example; goto 1 --> goto 1
397 *
398 * Type : jump to insertion point
399 * Action : changed
400 * Example; goto 2 --> goto 3
401
402 * Type : jump to place after instruction point
403 * Action : changed
404 * Example; goto 3 --> goto 4
405 *
406 * @param codeAttribute CodeAttribute that contains this code block, or null if none
407 * @param instr instruction to be inserted
408 */
409 public void insertInstr(AInstruction instr, CodeAttributeInfo codeAttribute) {
410 byte[] oldCode = getCode();
411 int insertionPoint = _index;
412
413 // walk through all instructions and relocate jumps
414 InstructionList oldCodeBlock = new InstructionList(oldCode);
415 do {
416 if (Opcode.isBranch(oldCodeBlock.getOpcode())) {
417 // this is a branch, so we might have to relocate
418 AInstruction relocInstr = oldCodeBlock.getInstr();
419 int ip = insertionPoint;
420 relocateBranches(relocInstr, ip);
421 }
422 } while(oldCodeBlock.advanceIndex());
423
424 // relocate instruction to be inserted
425 if (Opcode.isBranch(instr.getOpcode())) {
426 // this is a branch, so we might have to relocate
427 relocateBranches(instr, insertionPoint-1);
428 }
429
430 oldCodeBlock._instructionList.add(insertionPoint, instr);
431 oldCodeBlock._lnt = new LineNumberTable(oldCodeBlock);
432 byte[] newCode = oldCodeBlock.getCode();
433
434 if (codeAttribute != null) {
435 // adjust CodeAttribute PCs
436 codeAttribute.translatePC(insertionPoint, 1, _lnt, oldCodeBlock._lnt);
437 }
438
439 // transfer the code
440 setCode(newCode);
441 setIndex(insertionPoint);
442 }
443
444 /**
445 * Relocate branches in the instruction. If a branch target is to somewhere past the insertion point, it is
446 * increased by one.
447 * @param relocInstr instruction whose branches should be relocated
448 * @param ip insertion point
449 */
450 protected void relocateBranches(AInstruction relocInstr, int ip) {
451 int[] branchTargets = relocInstr.getBranchTargets();
452 for(int i = 0; i < branchTargets.length; ++i) {
453 // Debug.out.println("insertInstr: DP = "+deletionPoint+", PC="+oldCodeBlock.getPC()+", BT="+branchTargets[i]);
454 if (branchTargets[i] > ip) {
455 // the target of this instruction was somewhere past the insertion point
456 // we need to relocate
457 ++branchTargets[i];
458
459 // Debug.out.println("\tnew BT="+branchTargets[i]);
460 }
461 }
462 relocInstr.setBranchTargets(branchTargets);
463 }
464
465 /**
466 * This method inserts the instruction before the program counter. The instruction currently at the program counter
467 * will be pushed towards the end of the bytecode array. It also relocates all jumps. Jumps to places before the
468 * insertion point are not changed. Jumps to all other places will be changed so that they still point to the same
469 * instruction. That means that jumps to the instruction previously at the insertion point will still jump to the
470 * old instruction. If codeAttribute is non-null, the PCs in the CodeAttribute will be adjusted. The
471 * program counter will remain unchanged. If the inserted instruction itself contains jump targets, these will be
472 * relocated as well.
473 * <p/>
474 * Assume the following code:
475 * 1. a
476 * 2. b
477 * 3. c
478 * 4. goto 1 // jump to place before insertion point
479 * 5. goto 2 // jump to insertion point
480 * 6. goto 3 // junp to place after insertion point
481 * The program counter is currently at 2, and the instruction x is inserted using insertBeforeInstr. The result is:
482 * 1. a
483 * 2. x // inserted
484 * 3. b
485 * 4. c
486 * 5. goto 1 // not changed
487 * 6. goto 3 // changed
488 * 7. goto 4 // changed
489 * <p/>
490 * Relocation of branches in the instruction inserted.
491 * Type : jump to place before insertion point
492 * Action : not changed
493 * Example; goto 1 --> goto 1
494 *
495 * Type : jump to insertion point
496 * Action : changed
497 * Example; goto 2 --> goto 3
498
499 * Type : jump to place after instruction point
500 * Action : changed
501 * Example; goto 3 --> goto 4
502 *
503 * @param codeAttribute CodeAttribute that contains this code block, or null if none
504 * @param instr instruction to be inserted
505 */
506 public void insertBeforeInstr(AInstruction instr, CodeAttributeInfo codeAttribute) {
507 byte[] oldCode = getCode();
508 int insertionPoint = _index;
509
510 // walk through all instructions and relocate jumps
511 InstructionList oldCodeBlock = new InstructionList(oldCode);
512 do {
513 if (Opcode.isBranch(oldCodeBlock.getOpcode())) {
514 // this is a branch, so we might have to relocate
515 AInstruction relocInstr = oldCodeBlock.getInstr();
516 relocateBranches(relocInstr, insertionPoint-1);
517 }
518 } while(oldCodeBlock.advanceIndex());
519
520 // relocate instruction to be inserted
521 if (Opcode.isBranch(instr.getOpcode())) {
522 // this is a branch, so we might have to relocate
523 relocateBranches(instr, insertionPoint-1);
524 }
525
526 oldCodeBlock._instructionList.add(insertionPoint, instr);
527 oldCodeBlock._lnt = new LineNumberTable(oldCodeBlock);
528 byte[] newCode = oldCodeBlock.getCode();
529
530 if (codeAttribute != null) {
531 // adjust CodeAttribute PCs
532 codeAttribute.translatePC(insertionPoint-1, 1, _lnt, oldCodeBlock._lnt);
533 }
534
535 // transfer the code
536 setCode(newCode);
537 setIndex(insertionPoint);
538 }
539
540 /**
541 * Finds the next instruction with the specified opcode and moves the program counter there. If the current
542 * instruction matches the opcode, the program counter will not be changed. This means that the caller is
543 * responsible for advancing the program counter after a match has been found!
544 *
545 * @param opcode opcode to find
546 *
547 * @return true while the end of the code block has not been reached
548 */
549 public boolean findOpcode(byte opcode) {
550 return findOpcode(new byte[] {opcode});
551 }
552
553 /**
554 * Finds the next instruction with one of the specified opcodes and moves the program counter there. If the current
555 * instruction matches one of the opcodes, the program counter will not be changed. This means that the caller is
556 * responsible for advancing the program counter after a match has been found!
557 *
558 * @param opcodes array of opcodes to find
559 *
560 * @return true while the end of the code block has not been reached
561 */
562 public boolean findOpcode(byte[] opcodes) {
563 if (_index < 0) {
564 throw new IndexOutOfBoundsException(
565 "The program index (" + _index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
566 }
567 if (_index == _instructionList.size()) {
568 // past end already
569 return false;
570 }
571 ArrayList<Byte> opcodeList = new ArrayList<Byte>(opcodes.length);
572 for(byte o: opcodes) {
573 opcodeList.add(o);
574 }
575 do {
576 if (opcodeList.contains(getOpcode())) {
577 return true;
578 }
579 } while(advanceIndex());
580 return false;
581 }
582
583 /**
584 * Finds the next instruction that matches the specified instruction completely and moves the program counter there.
585 * A complete match requires that both the opcode and all the operands are identical. If the current instruction
586 * matches already, the program counter will not be changed. This means that the caller is responsible for advancing
587 * the program counter after a match has been found!
588 *
589 * @param instr instruction to find
590 *
591 * @return true while the end of the code block has not been reached
592 */
593 public boolean findInstruction(AInstruction instr) {
594 return findInstruction(new AInstruction[] {instr});
595 }
596 /**
597 * Finds the next instruction that matches one of the specified instructions completely and moves the program counter there.
598 * A complete match requires that both the opcode and all the operands are identical. If the current instruction
599 * matches already, the program counter will not be changed. This means that the caller is responsible for advancing
600 * the program counter after a match has been found!
601 *
602 * @param instrs instructions to find
603 *
604 * @return true while the end of the code block has not been reached
605 */
606 public boolean findInstruction(AInstruction[] instrs) {
607 if (_index < 0) {
608 throw new IndexOutOfBoundsException(
609 "The program index (" + _index + ") is not within the instruction list (length=" + _instructionList.size() + ")");
610 }
611 if (_index == _instructionList.size()) {
612 // past end already
613 return false;
614 }
615 ArrayList<AInstruction> instrList = new ArrayList<AInstruction>(instrs.length);
616 for(AInstruction o: instrs) {
617 instrList.add(o);
618 }
619 do {
620 if (instrList.contains(getInstr())) {
621 return true;
622 }
623 } while(advanceIndex());
624 return false;
625 }
626
627 /**
628 * Return true if this instruction list and the other object are equal.
629 *
630 * @param o other object
631 *
632 * @return true if equal
633 */
634 public boolean equals(Object o) {
635 if (this == o) {
636 return true;
637 }
638 if (!(o instanceof InstructionList)) {
639 return false;
640 }
641
642 final InstructionList instructionList = (InstructionList)o;
643
644 if (!_instructionList.equals(instructionList._instructionList)) {
645 return false;
646 }
647
648 return true;
649 }
650
651 /**
652 * Return hash code.
653 *
654 * @return hash code
655 */
656 public int hashCode() {
657 return _instructionList.hashCode();
658 }
659 }