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