001/*
002 * Licensed to the Apache Software Foundation (ASF) under one or more
003 * contributor license agreements.  See the NOTICE file distributed with
004 * this work for additional information regarding copyright ownership.
005 * The ASF licenses this file to You under the Apache License, Version 2.0
006 * (the "License"); you may not use this file except in compliance with
007 * the License.  You may obtain a copy of the License at
008 *
009 *      http://www.apache.org/licenses/LICENSE-2.0
010 *
011 *  Unless required by applicable law or agreed to in writing, software
012 *  distributed under the License is distributed on an "AS IS" BASIS,
013 *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014 *  See the License for the specific language governing permissions and
015 *  limitations under the License.
016 *
017 */
018package org.apache.bcel.generic;
019
020import java.io.ByteArrayOutputStream;
021import java.io.DataOutputStream;
022import java.io.IOException;
023import java.util.ArrayList;
024import java.util.HashMap;
025import java.util.Iterator;
026import java.util.List;
027import java.util.Map;
028import java.util.NoSuchElementException;
029
030import org.apache.bcel.Const;
031import org.apache.bcel.classfile.Constant;
032import org.apache.bcel.util.ByteSequence;
033import org.apache.commons.lang3.ArrayUtils;
034
035/**
036 * This class is a container for a list of <a href="Instruction.html">Instruction</a> objects. Instructions can be
037 * appended, inserted, moved, deleted, etc.. Instructions are being wrapped into
038 * <a href="InstructionHandle.html">InstructionHandles</a> objects that are returned upon append/insert operations. They
039 * give the user (read only) access to the list structure, such that it can be traversed and manipulated in a controlled
040 * way.
041 *
042 * A list is finally dumped to a byte code array with <a href="#getByteCode()">getByteCode</a>.
043 *
044 * @see Instruction
045 * @see InstructionHandle
046 * @see BranchHandle
047 */
048public class InstructionList implements Iterable<InstructionHandle> {
049
050    /**
051     * Find the target instruction (handle) that corresponds to the given target position (byte code offset).
052     *
053     * @param ihs array of instruction handles, i.e. il.getInstructionHandles()
054     * @param pos array of positions corresponding to ihs, i.e. il.getInstructionPositions()
055     * @param count length of arrays
056     * @param target target position to search for
057     * @return target position's instruction handle if available
058     */
059    public static InstructionHandle findHandle(final InstructionHandle[] ihs, final int[] pos, final int count, final int target) {
060        int l = 0;
061        int r = count - 1;
062        /*
063         * Do a binary search since the pos array is orderd.
064         */
065        do {
066            final int i = l + r >>> 1;
067            final int j = pos[i];
068            if (j == target) {
069                return ihs[i];
070            }
071            if (target < j) {
072                r = i - 1;
073            } else {
074                l = i + 1;
075            }
076        } while (l <= r);
077        return null;
078    }
079
080    private InstructionHandle start;
081    private InstructionHandle end;
082    private int length; // number of elements in list
083
084    private int[] bytePositions; // byte code offsets corresponding to instructions
085
086    private List<InstructionListObserver> observers;
087
088    /**
089     * Create (empty) instruction list.
090     */
091    public InstructionList() {
092    }
093
094    /**
095     * Create instruction list containing one instruction.
096     *
097     * @param i initial instruction
098     */
099    public InstructionList(final BranchInstruction i) {
100        append(i);
101    }
102
103    /**
104     * Initialize instruction list from byte array.
105     *
106     * @param code byte array containing the instructions
107     */
108    public InstructionList(final byte[] code) {
109        int count = 0; // Contains actual length
110        int[] pos;
111        InstructionHandle[] ihs;
112        try (ByteSequence bytes = new ByteSequence(code)) {
113            ihs = new InstructionHandle[code.length];
114            pos = new int[code.length]; // Can't be more than that
115            /*
116             * Pass 1: Create an object for each byte code and append them to the list.
117             */
118            while (bytes.available() > 0) {
119                // Remember byte offset and associate it with the instruction
120                final int off = bytes.getIndex();
121                pos[count] = off;
122                /*
123                 * Read one instruction from the byte stream, the byte position is set accordingly.
124                 */
125                final Instruction i = Instruction.readInstruction(bytes);
126                InstructionHandle ih;
127                if (i instanceof BranchInstruction) {
128                    ih = append((BranchInstruction) i);
129                } else {
130                    ih = append(i);
131                }
132                ih.setPosition(off);
133                ihs[count] = ih;
134                count++;
135            }
136        } catch (final IOException e) {
137            throw new ClassGenException(e.toString(), e);
138        }
139        bytePositions = new int[count]; // Trim to proper size
140        System.arraycopy(pos, 0, bytePositions, 0, count);
141        /*
142         * Pass 2: Look for BranchInstruction and update their targets, i.e., convert offsets to instruction handles.
143         */
144        for (int i = 0; i < count; i++) {
145            if (ihs[i] instanceof BranchHandle) {
146                final BranchInstruction bi = (BranchInstruction) ihs[i].getInstruction();
147                int target = bi.getPosition() + bi.getIndex(); /*
148                                                                * Byte code position: relative -> absolute.
149                                                                */
150                // Search for target position
151                InstructionHandle ih = findHandle(ihs, pos, count, target);
152                if (ih == null) {
153                    throw new ClassGenException("Couldn't find target for branch: " + bi);
154                }
155                bi.setTarget(ih); // Update target
156                // If it is a Select instruction, update all branch targets
157                if (bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
158                    final Select s = (Select) bi;
159                    final int[] indices = s.getIndices();
160                    for (int j = 0; j < indices.length; j++) {
161                        target = bi.getPosition() + indices[j];
162                        ih = findHandle(ihs, pos, count, target);
163                        if (ih == null) {
164                            throw new ClassGenException("Couldn't find target for switch: " + bi);
165                        }
166                        s.setTarget(j, ih); // Update target
167                    }
168                }
169            }
170        }
171    }
172
173    /**
174     * Initialize list with (nonnull) compound instruction. Consumes argument list, i.e., it becomes empty.
175     *
176     * @param c compound instruction (list)
177     */
178    public InstructionList(final CompoundInstruction c) {
179        append(c.getInstructionList());
180    }
181
182    /**
183     * Create instruction list containing one instruction.
184     *
185     * @param i initial instruction
186     */
187    public InstructionList(final Instruction i) {
188        append(i);
189    }
190
191    /**
192     * Add observer for this object.
193     */
194    public void addObserver(final InstructionListObserver o) {
195        if (observers == null) {
196            observers = new ArrayList<>();
197        }
198        observers.add(o);
199    }
200
201    /**
202     * Append a branch instruction to the end of this list.
203     *
204     * @param i branch instruction to append
205     * @return branch instruction handle of the appended instruction
206     */
207    public BranchHandle append(final BranchInstruction i) {
208        final BranchHandle ih = BranchHandle.getBranchHandle(i);
209        append(ih);
210        return ih;
211    }
212
213    /**
214     * Append a compound instruction.
215     *
216     * @param c The composite instruction (containing an InstructionList)
217     * @return instruction handle of the first appended instruction
218     */
219    public InstructionHandle append(final CompoundInstruction c) {
220        return append(c.getInstructionList());
221    }
222
223    /**
224     * Append an instruction to the end of this list.
225     *
226     * @param i instruction to append
227     * @return instruction handle of the appended instruction
228     */
229    public InstructionHandle append(final Instruction i) {
230        final InstructionHandle ih = InstructionHandle.getInstructionHandle(i);
231        append(ih);
232        return ih;
233    }
234
235    /**
236     * Append a compound instruction, after instruction i.
237     *
238     * @param i Instruction in list
239     * @param c The composite instruction (containing an InstructionList)
240     * @return instruction handle of the first appended instruction
241     */
242    public InstructionHandle append(final Instruction i, final CompoundInstruction c) {
243        return append(i, c.getInstructionList());
244    }
245
246    /**
247     * Append a single instruction j after another instruction i, which must be in this list of course!
248     *
249     * @param i Instruction in list
250     * @param j Instruction to append after i in list
251     * @return instruction handle of the first appended instruction
252     */
253    public InstructionHandle append(final Instruction i, final Instruction j) {
254        return append(i, new InstructionList(j));
255    }
256
257    /**
258     * Append another list after instruction i contained in this list. Consumes argument list, i.e., it becomes empty.
259     *
260     * @param i where to append the instruction list
261     * @param il Instruction list to append to this one
262     * @return instruction handle pointing to the <B>first</B> appended instruction
263     */
264    public InstructionHandle append(final Instruction i, final InstructionList il) {
265        InstructionHandle ih;
266        if ((ih = findInstruction2(i)) == null) {
267            throw new ClassGenException("Instruction " + i + " is not contained in this list.");
268        }
269        return append(ih, il);
270    }
271
272    /**
273     * Append an instruction to the end of this list.
274     *
275     * @param ih instruction to append
276     */
277    private void append(final InstructionHandle ih) {
278        if (isEmpty()) {
279            start = end = ih;
280            ih.setNext(ih.setPrev(null));
281        } else {
282            end.setNext(ih);
283            ih.setPrev(end);
284            ih.setNext(null);
285            end = ih;
286        }
287        length++; // Update length
288    }
289
290    /**
291     * Append an instruction after instruction (handle) ih contained in this list.
292     *
293     * @param ih where to append the instruction list
294     * @param i Instruction to append
295     * @return instruction handle pointing to the <B>first</B> appended instruction
296     */
297    public BranchHandle append(final InstructionHandle ih, final BranchInstruction i) {
298        final BranchHandle bh = BranchHandle.getBranchHandle(i);
299        final InstructionList il = new InstructionList();
300        il.append(bh);
301        append(ih, il);
302        return bh;
303    }
304
305    /**
306     * Append a compound instruction.
307     *
308     * @param ih where to append the instruction list
309     * @param c The composite instruction (containing an InstructionList)
310     * @return instruction handle of the first appended instruction
311     */
312    public InstructionHandle append(final InstructionHandle ih, final CompoundInstruction c) {
313        return append(ih, c.getInstructionList());
314    }
315
316    /**
317     * Append an instruction after instruction (handle) ih contained in this list.
318     *
319     * @param ih where to append the instruction list
320     * @param i Instruction to append
321     * @return instruction handle pointing to the <B>first</B> appended instruction
322     */
323    public InstructionHandle append(final InstructionHandle ih, final Instruction i) {
324        return append(ih, new InstructionList(i));
325    }
326
327    /**
328     * Append another list after instruction (handle) ih contained in this list. Consumes argument list, i.e., it becomes
329     * empty.
330     *
331     * @param ih where to append the instruction list
332     * @param il Instruction list to append to this one
333     * @return instruction handle pointing to the <B>first</B> appended instruction
334     */
335    public InstructionHandle append(final InstructionHandle ih, final InstructionList il) {
336        if (il == null) {
337            throw new ClassGenException("Appending null InstructionList");
338        }
339        if (il.isEmpty()) {
340            return ih;
341        }
342        final InstructionHandle next = ih.getNext();
343        final InstructionHandle ret = il.start;
344        ih.setNext(il.start);
345        il.start.setPrev(ih);
346        il.end.setNext(next);
347        if (next != null) {
348            next.setPrev(il.end);
349        } else {
350            end = il.end; // Update end ...
351        }
352        length += il.length; // Update length
353        il.clear();
354        return ret;
355    }
356
357    /**
358     * Append another list to this one. Consumes argument list, i.e., it becomes empty.
359     *
360     * @param il list to append to end of this list
361     * @return instruction handle of the <B>first</B> appended instruction
362     */
363    public InstructionHandle append(final InstructionList il) {
364        if (il == null) {
365            throw new ClassGenException("Appending null InstructionList");
366        }
367        if (il.isEmpty()) {
368            return null;
369        }
370        if (isEmpty()) {
371            start = il.start;
372            end = il.end;
373            length = il.length;
374            il.clear();
375            return start;
376        }
377        return append(end, il); // was end.instruction
378    }
379
380    private void clear() {
381        start = end = null;
382        length = 0;
383    }
384
385    public boolean contains(final Instruction i) {
386        return findInstruction1(i) != null;
387    }
388
389    public boolean contains(final InstructionHandle i) {
390        if (i == null) {
391            return false;
392        }
393        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
394            if (ih == i) {
395                return true;
396            }
397        }
398        return false;
399    }
400
401    /**
402     * @return complete, i.e., deep copy of this list
403     */
404    public InstructionList copy() {
405        final Map<InstructionHandle, InstructionHandle> map = new HashMap<>();
406        final InstructionList il = new InstructionList();
407        /*
408         * Pass 1: Make copies of all instructions, append them to the new list and associate old instruction references with
409         * the new ones, i.e., a 1:1 mapping.
410         */
411        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
412            final Instruction i = ih.getInstruction();
413            final Instruction c = i.copy(); // Use clone for shallow copy
414            if (c instanceof BranchInstruction) {
415                map.put(ih, il.append((BranchInstruction) c));
416            } else {
417                map.put(ih, il.append(c));
418            }
419        }
420        /*
421         * Pass 2: Update branch targets.
422         */
423        InstructionHandle ih = start;
424        InstructionHandle ch = il.start;
425        while (ih != null) {
426            final Instruction i = ih.getInstruction();
427            final Instruction c = ch.getInstruction();
428            if (i instanceof BranchInstruction) {
429                final BranchInstruction bi = (BranchInstruction) i;
430                final BranchInstruction bc = (BranchInstruction) c;
431                final InstructionHandle itarget = bi.getTarget(); // old target
432                // New target is in hash map
433                bc.setTarget(map.get(itarget));
434                if (bi instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
435                    final InstructionHandle[] itargets = ((Select) bi).getTargets();
436                    final InstructionHandle[] ctargets = ((Select) bc).getTargets();
437                    for (int j = 0; j < itargets.length; j++) { // Update all targets
438                        ctargets[j] = map.get(itargets[j]);
439                    }
440                }
441            }
442            ih = ih.getNext();
443            ch = ch.getNext();
444        }
445        return il;
446    }
447
448    /**
449     * Remove instruction from this list. The corresponding Instruction handles must not be reused!
450     *
451     * @param i instruction to remove
452     */
453    public void delete(final Instruction i) throws TargetLostException {
454        InstructionHandle ih;
455        if ((ih = findInstruction1(i)) == null) {
456            throw new ClassGenException("Instruction " + i + " is not contained in this list.");
457        }
458        delete(ih);
459    }
460
461    /**
462     * Remove instructions from instruction `from' to instruction `to' contained in this list. The user must ensure that
463     * `from' is an instruction before `to', or risk havoc. The corresponding Instruction handles must not be reused!
464     *
465     * @param from where to start deleting (inclusive)
466     * @param to where to end deleting (inclusive)
467     */
468    public void delete(final Instruction from, final Instruction to) throws TargetLostException {
469        InstructionHandle from_ih;
470        InstructionHandle to_ih;
471        if ((from_ih = findInstruction1(from)) == null) {
472            throw new ClassGenException("Instruction " + from + " is not contained in this list.");
473        }
474        if ((to_ih = findInstruction2(to)) == null) {
475            throw new ClassGenException("Instruction " + to + " is not contained in this list.");
476        }
477        delete(from_ih, to_ih);
478    }
479
480    /**
481     * Remove instruction from this list. The corresponding Instruction handles must not be reused!
482     *
483     * @param ih instruction (handle) to remove
484     */
485    public void delete(final InstructionHandle ih) throws TargetLostException {
486        remove(ih.getPrev(), ih.getNext());
487    }
488
489    /**
490     * Remove instructions from instruction `from' to instruction `to' contained in this list. The user must ensure that
491     * `from' is an instruction before `to', or risk havoc. The corresponding Instruction handles must not be reused!
492     *
493     * @param from where to start deleting (inclusive)
494     * @param to where to end deleting (inclusive)
495     */
496    public void delete(final InstructionHandle from, final InstructionHandle to) throws TargetLostException {
497        remove(from.getPrev(), to.getNext());
498    }
499
500    /**
501     * Delete contents of list. Provides better memory utilization, because the system then may reuse the instruction
502     * handles. This method is typically called right after {@link MethodGen#getMethod()}.
503     */
504    public void dispose() {
505        // Traverse in reverse order, because ih.next is overwritten
506        for (InstructionHandle ih = end; ih != null; ih = ih.getPrev()) {
507            /*
508             * Causes BranchInstructions to release target and targeters, because it calls dispose() on the contained instruction.
509             */
510            ih.dispose();
511        }
512        clear();
513    }
514
515    /**
516     * Get instruction handle for instruction at byte code position pos. This only works properly, if the list is freshly
517     * initialized from a byte array or setPositions() has been called before this method.
518     *
519     * @param pos byte code position to search for
520     * @return target position's instruction handle if available
521     */
522    public InstructionHandle findHandle(final int pos) {
523        final int[] positions = bytePositions;
524        InstructionHandle ih = start;
525        for (int i = 0; i < length; i++) {
526            if (positions[i] == pos) {
527                return ih;
528            }
529            ih = ih.getNext();
530        }
531        return null;
532    }
533
534    /**
535     * Search for given Instruction reference, start at beginning of list.
536     *
537     * @param i instruction to search for
538     * @return instruction found on success, null otherwise
539     */
540    private InstructionHandle findInstruction1(final Instruction i) {
541        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
542            if (ih.getInstruction() == i) {
543                return ih;
544            }
545        }
546        return null;
547    }
548
549    /**
550     * Search for given Instruction reference, start at end of list
551     *
552     * @param i instruction to search for
553     * @return instruction found on success, null otherwise
554     */
555    private InstructionHandle findInstruction2(final Instruction i) {
556        for (InstructionHandle ih = end; ih != null; ih = ih.getPrev()) {
557            if (ih.getInstruction() == i) {
558                return ih;
559            }
560        }
561        return null;
562    }
563
564    /**
565     * When everything is finished, use this method to convert the instruction list into an array of bytes.
566     *
567     * @return the byte code ready to be dumped
568     */
569    public byte[] getByteCode() {
570        // Update position indices of instructions
571        setPositions();
572        final ByteArrayOutputStream b = new ByteArrayOutputStream();
573        final DataOutputStream out = new DataOutputStream(b);
574        try {
575            for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
576                final Instruction i = ih.getInstruction();
577                i.dump(out); // Traverse list
578            }
579            out.flush();
580        } catch (final IOException e) {
581            System.err.println(e);
582            return ArrayUtils.EMPTY_BYTE_ARRAY;
583        }
584        return b.toByteArray();
585    }
586
587    /**
588     * @return end of list
589     */
590    public InstructionHandle getEnd() {
591        return end;
592    }
593
594    /**
595     * @return array containing all instructions (handles)
596     */
597    public InstructionHandle[] getInstructionHandles() {
598        final InstructionHandle[] ihs = new InstructionHandle[length];
599        InstructionHandle ih = start;
600        for (int i = 0; i < length; i++) {
601            ihs[i] = ih;
602            ih = ih.getNext();
603        }
604        return ihs;
605    }
606
607    /**
608     * Get positions (offsets) of all instructions in the list. This relies on that the list has been freshly created from
609     * an byte code array, or that setPositions() has been called. Otherwise this may be inaccurate.
610     *
611     * @return array containing all instruction's offset in byte code
612     */
613    public int[] getInstructionPositions() {
614        return bytePositions;
615    }
616
617    /**
618     * @return an array of instructions without target information for branch instructions.
619     */
620    public Instruction[] getInstructions() {
621        final List<Instruction> instructions = new ArrayList<>();
622        try (ByteSequence bytes = new ByteSequence(getByteCode())) {
623            while (bytes.available() > 0) {
624                instructions.add(Instruction.readInstruction(bytes));
625            }
626        } catch (final IOException e) {
627            throw new ClassGenException(e.toString(), e);
628        }
629        return instructions.toArray(Instruction.EMPTY_ARRAY);
630    }
631
632    /**
633     * @return length of list (Number of instructions, not bytes)
634     */
635    public int getLength() {
636        return length;
637    }
638
639    /**
640     * @return start of list
641     */
642    public InstructionHandle getStart() {
643        return start;
644    }
645
646    /**
647     * Insert a branch instruction at start of this list.
648     *
649     * @param i branch instruction to insert
650     * @return branch instruction handle of the appended instruction
651     */
652    public BranchHandle insert(final BranchInstruction i) {
653        final BranchHandle ih = BranchHandle.getBranchHandle(i);
654        insert(ih);
655        return ih;
656    }
657
658    /**
659     * Insert a compound instruction.
660     *
661     * @param c The composite instruction (containing an InstructionList)
662     * @return instruction handle of the first inserted instruction
663     */
664    public InstructionHandle insert(final CompoundInstruction c) {
665        return insert(c.getInstructionList());
666    }
667
668    /**
669     * Insert an instruction at start of this list.
670     *
671     * @param i instruction to insert
672     * @return instruction handle of the inserted instruction
673     */
674    public InstructionHandle insert(final Instruction i) {
675        final InstructionHandle ih = InstructionHandle.getInstructionHandle(i);
676        insert(ih);
677        return ih;
678    }
679
680    /**
681     * Insert a compound instruction before instruction i.
682     *
683     * @param i Instruction in list
684     * @param c The composite instruction (containing an InstructionList)
685     * @return instruction handle of the first inserted instruction
686     */
687    public InstructionHandle insert(final Instruction i, final CompoundInstruction c) {
688        return insert(i, c.getInstructionList());
689    }
690
691    /**
692     * Insert a single instruction j before another instruction i, which must be in this list of course!
693     *
694     * @param i Instruction in list
695     * @param j Instruction to insert before i in list
696     * @return instruction handle of the first inserted instruction
697     */
698    public InstructionHandle insert(final Instruction i, final Instruction j) {
699        return insert(i, new InstructionList(j));
700    }
701
702    /**
703     * Insert another list before Instruction i contained in this list. Consumes argument list, i.e., it becomes empty.
704     *
705     * @param i where to append the instruction list
706     * @param il Instruction list to insert
707     * @return instruction handle pointing to the first inserted instruction, i.e., il.getStart()
708     */
709    public InstructionHandle insert(final Instruction i, final InstructionList il) {
710        InstructionHandle ih;
711        if ((ih = findInstruction1(i)) == null) {
712            throw new ClassGenException("Instruction " + i + " is not contained in this list.");
713        }
714        return insert(ih, il);
715    }
716
717    /**
718     * Insert an instruction at start of this list.
719     *
720     * @param ih instruction to insert
721     */
722    private void insert(final InstructionHandle ih) {
723        if (isEmpty()) {
724            start = end = ih;
725            ih.setNext(ih.setPrev(null));
726        } else {
727            start.setPrev(ih);
728            ih.setNext(start);
729            ih.setPrev(null);
730            start = ih;
731        }
732        length++;
733    }
734
735    /**
736     * Insert an instruction before instruction (handle) ih contained in this list.
737     *
738     * @param ih where to insert to the instruction list
739     * @param i Instruction to insert
740     * @return instruction handle of the first inserted instruction
741     */
742    public BranchHandle insert(final InstructionHandle ih, final BranchInstruction i) {
743        final BranchHandle bh = BranchHandle.getBranchHandle(i);
744        final InstructionList il = new InstructionList();
745        il.append(bh);
746        insert(ih, il);
747        return bh;
748    }
749
750    /**
751     * Insert a compound instruction.
752     *
753     * @param ih where to insert the instruction list
754     * @param c The composite instruction (containing an InstructionList)
755     * @return instruction handle of the first inserted instruction
756     */
757    public InstructionHandle insert(final InstructionHandle ih, final CompoundInstruction c) {
758        return insert(ih, c.getInstructionList());
759    }
760
761    /**
762     * Insert an instruction before instruction (handle) ih contained in this list.
763     *
764     * @param ih where to insert to the instruction list
765     * @param i Instruction to insert
766     * @return instruction handle of the first inserted instruction
767     */
768    public InstructionHandle insert(final InstructionHandle ih, final Instruction i) {
769        return insert(ih, new InstructionList(i));
770    }
771
772    /**
773     * Insert another list before Instruction handle ih contained in this list. Consumes argument list, i.e., it becomes
774     * empty.
775     *
776     * @param ih where to append the instruction list
777     * @param il Instruction list to insert
778     * @return instruction handle of the first inserted instruction
779     */
780    public InstructionHandle insert(final InstructionHandle ih, final InstructionList il) {
781        if (il == null) {
782            throw new ClassGenException("Inserting null InstructionList");
783        }
784        if (il.isEmpty()) {
785            return ih;
786        }
787        final InstructionHandle prev = ih.getPrev();
788        final InstructionHandle ret = il.start;
789        ih.setPrev(il.end);
790        il.end.setNext(ih);
791        il.start.setPrev(prev);
792        if (prev != null) {
793            prev.setNext(il.start);
794        } else {
795            start = il.start; // Update start ...
796        }
797        length += il.length; // Update length
798        il.clear();
799        return ret;
800    }
801
802    /**
803     * Insert another list.
804     *
805     * @param il list to insert before start of this list
806     * @return instruction handle of the first inserted instruction
807     */
808    public InstructionHandle insert(final InstructionList il) {
809        if (isEmpty()) {
810            append(il); // Code is identical for this case
811            return start;
812        }
813        return insert(start, il);
814    }
815
816    /**
817     * Test for empty list.
818     */
819    public boolean isEmpty() {
820        return start == null;
821    } // && end == null
822
823    /**
824     * @return iterator that lists all instructions (handles)
825     */
826    @Override
827    public Iterator<InstructionHandle> iterator() {
828        return new Iterator<InstructionHandle>() {
829
830            private InstructionHandle ih = start;
831
832            @Override
833            public boolean hasNext() {
834                return ih != null;
835            }
836
837            @Override
838            public InstructionHandle next() throws NoSuchElementException {
839                if (ih == null) {
840                    throw new NoSuchElementException();
841                }
842                final InstructionHandle i = ih;
843                ih = ih.getNext();
844                return i;
845            }
846
847            @Override
848            public void remove() {
849                throw new UnsupportedOperationException();
850            }
851        };
852    }
853
854    /**
855     * Move a single instruction (handle) to a new location.
856     *
857     * @param ih moved instruction
858     * @param target new location of moved instruction
859     */
860    public void move(final InstructionHandle ih, final InstructionHandle target) {
861        move(ih, ih, target);
862    }
863
864    /**
865     * Take all instructions (handles) from "start" to "end" and append them after the new location "target". Of course,
866     * "end" must be after "start" and target must not be located withing this range. If you want to move something to the
867     * start of the list use null as value for target.
868     * <p>
869     * Any instruction targeters pointing to handles within the block, keep their targets.
870     * </p>
871     *
872     * @param start of moved block
873     * @param end of moved block
874     * @param target of moved block
875     */
876    public void move(final InstructionHandle start, final InstructionHandle end, final InstructionHandle target) {
877        // Step 1: Check constraints
878        if (start == null || end == null) {
879            throw new ClassGenException("Invalid null handle: From " + start + " to " + end);
880        }
881        if (target == start || target == end) {
882            throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target);
883        }
884        for (InstructionHandle ih = start; ih != end.getNext(); ih = ih.getNext()) {
885            if (ih == null) {
886                throw new ClassGenException("Invalid range: From " + start + " to " + end);
887            }
888            if (ih == target) {
889                throw new ClassGenException("Invalid range: From " + start + " to " + end + " contains target " + target);
890            }
891        }
892        // Step 2: Temporarily remove the given instructions from the list
893        final InstructionHandle prev = start.getPrev();
894        InstructionHandle next = end.getNext();
895        if (prev != null) {
896            prev.setNext(next);
897        } else {
898            this.start = next;
899        }
900        if (next != null) {
901            next.setPrev(prev);
902        } else {
903            this.end = prev;
904        }
905        start.setPrev(end.setNext(null));
906        // Step 3: append after target
907        if (target == null) { // append to start of list
908            if (this.start != null) {
909                this.start.setPrev(end);
910            }
911            end.setNext(this.start);
912            this.start = start;
913        } else {
914            next = target.getNext();
915            target.setNext(start);
916            start.setPrev(target);
917            end.setNext(next);
918            if (next != null) {
919                next.setPrev(end);
920            } else {
921                this.end = end;
922            }
923        }
924    }
925
926    /**
927     * Redirect all references from old_target to new_target, i.e., update targets of branch instructions.
928     *
929     * @param old_target the old target instruction handle
930     * @param new_target the new target instruction handle
931     */
932    public void redirectBranches(final InstructionHandle old_target, final InstructionHandle new_target) {
933        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
934            final Instruction i = ih.getInstruction();
935            if (i instanceof BranchInstruction) {
936                final BranchInstruction b = (BranchInstruction) i;
937                final InstructionHandle target = b.getTarget();
938                if (target == old_target) {
939                    b.setTarget(new_target);
940                }
941                if (b instanceof Select) { // Either LOOKUPSWITCH or TABLESWITCH
942                    final InstructionHandle[] targets = ((Select) b).getTargets();
943                    for (int j = 0; j < targets.length; j++) {
944                        if (targets[j] == old_target) {
945                            ((Select) b).setTarget(j, new_target);
946                        }
947                    }
948                }
949            }
950        }
951    }
952
953    /**
954     * Redirect all references of exception handlers from old_target to new_target.
955     *
956     * @param exceptions array of exception handlers
957     * @param old_target the old target instruction handle
958     * @param new_target the new target instruction handle
959     * @see MethodGen
960     */
961    public void redirectExceptionHandlers(final CodeExceptionGen[] exceptions, final InstructionHandle old_target, final InstructionHandle new_target) {
962        for (final CodeExceptionGen exception : exceptions) {
963            if (exception.getStartPC() == old_target) {
964                exception.setStartPC(new_target);
965            }
966            if (exception.getEndPC() == old_target) {
967                exception.setEndPC(new_target);
968            }
969            if (exception.getHandlerPC() == old_target) {
970                exception.setHandlerPC(new_target);
971            }
972        }
973    }
974
975    /**
976     * Redirect all references of local variables from old_target to new_target.
977     *
978     * @param lg array of local variables
979     * @param old_target the old target instruction handle
980     * @param new_target the new target instruction handle
981     * @see MethodGen
982     */
983    public void redirectLocalVariables(final LocalVariableGen[] lg, final InstructionHandle old_target, final InstructionHandle new_target) {
984        for (final LocalVariableGen element : lg) {
985            final InstructionHandle start = element.getStart();
986            final InstructionHandle end = element.getEnd();
987            if (start == old_target) {
988                element.setStart(new_target);
989            }
990            if (end == old_target) {
991                element.setEnd(new_target);
992            }
993        }
994    }
995
996    /**
997     * Remove from instruction `prev' to instruction `next' both contained in this list. Throws TargetLostException when one
998     * of the removed instruction handles is still being targeted.
999     *
1000     * @param prev where to start deleting (predecessor, exclusive)
1001     * @param next where to end deleting (successor, exclusive)
1002     */
1003    private void remove(final InstructionHandle prev, InstructionHandle next) throws TargetLostException {
1004        InstructionHandle first;
1005        InstructionHandle last; // First and last deleted instruction
1006        if (prev == null && next == null) {
1007            first = start;
1008            last = end;
1009            start = end = null;
1010        } else {
1011            if (prev == null) { // At start of list
1012                first = start;
1013                start = next;
1014            } else {
1015                first = prev.getNext();
1016                prev.setNext(next);
1017            }
1018            if (next == null) { // At end of list
1019                last = end;
1020                end = prev;
1021            } else {
1022                last = next.getPrev();
1023                next.setPrev(prev);
1024            }
1025        }
1026        first.setPrev(null); // Completely separated from rest of list
1027        last.setNext(null);
1028        final List<InstructionHandle> target_vec = new ArrayList<>();
1029        for (InstructionHandle ih = first; ih != null; ih = ih.getNext()) {
1030            ih.getInstruction().dispose(); // e.g. BranchInstructions release their targets
1031        }
1032        final StringBuilder buf = new StringBuilder("{ ");
1033        for (InstructionHandle ih = first; ih != null; ih = next) {
1034            next = ih.getNext();
1035            length--;
1036            if (ih.hasTargeters()) { // Still got targeters?
1037                target_vec.add(ih);
1038                buf.append(ih.toString(true)).append(" ");
1039                ih.setNext(ih.setPrev(null));
1040            } else {
1041                ih.dispose();
1042            }
1043        }
1044        buf.append("}");
1045        if (!target_vec.isEmpty()) {
1046            throw new TargetLostException(target_vec.toArray(InstructionHandle.EMPTY_ARRAY), buf.toString());
1047        }
1048    }
1049
1050    /**
1051     * Remove observer for this object.
1052     */
1053    public void removeObserver(final InstructionListObserver o) {
1054        if (observers != null) {
1055            observers.remove(o);
1056        }
1057    }
1058
1059    /**
1060     * Replace all references to the old constant pool with references to the new constant pool
1061     */
1062    public void replaceConstantPool(final ConstantPoolGen old_cp, final ConstantPoolGen new_cp) {
1063        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
1064            final Instruction i = ih.getInstruction();
1065            if (i instanceof CPInstruction) {
1066                final CPInstruction ci = (CPInstruction) i;
1067                final Constant c = old_cp.getConstant(ci.getIndex());
1068                ci.setIndex(new_cp.addConstant(c, old_cp));
1069            }
1070        }
1071    }
1072
1073    public void setPositions() { // TODO could be package-protected? (some test code would need to be repackaged)
1074        setPositions(false);
1075    }
1076
1077    /**
1078     * Give all instructions their position number (offset in byte stream), i.e., make the list ready to be dumped.
1079     *
1080     * @param check Perform sanity checks, e.g. if all targeted instructions really belong to this list
1081     */
1082    public void setPositions(final boolean check) { // called by code in other packages
1083        int max_additional_bytes = 0;
1084        int additional_bytes = 0;
1085        int index = 0;
1086        int count = 0;
1087        final int[] pos = new int[length];
1088        /*
1089         * Pass 0: Sanity checks
1090         */
1091        if (check) {
1092            for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
1093                final Instruction i = ih.getInstruction();
1094                if (i instanceof BranchInstruction) { // target instruction within list?
1095                    Instruction inst = ((BranchInstruction) i).getTarget().getInstruction();
1096                    if (!contains(inst)) {
1097                        throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list");
1098                    }
1099                    if (i instanceof Select) {
1100                        final InstructionHandle[] targets = ((Select) i).getTargets();
1101                        for (final InstructionHandle target : targets) {
1102                            inst = target.getInstruction();
1103                            if (!contains(inst)) {
1104                                throw new ClassGenException("Branch target of " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not in instruction list");
1105                            }
1106                        }
1107                    }
1108                    if (!(ih instanceof BranchHandle)) {
1109                        throw new ClassGenException(
1110                            "Branch instruction " + Const.getOpcodeName(i.getOpcode()) + ":" + inst + " not contained in BranchHandle.");
1111                    }
1112                }
1113            }
1114        }
1115        /*
1116         * Pass 1: Set position numbers and sum up the maximum number of bytes an instruction may be shifted.
1117         */
1118        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
1119            final Instruction i = ih.getInstruction();
1120            ih.setPosition(index);
1121            pos[count++] = index;
1122            /*
1123             * Get an estimate about how many additional bytes may be added, because BranchInstructions may have variable length
1124             * depending on the target offset (short vs. int) or alignment issues (TABLESWITCH and LOOKUPSWITCH).
1125             */
1126            switch (i.getOpcode()) {
1127            case Const.JSR:
1128            case Const.GOTO:
1129                max_additional_bytes += 2;
1130                break;
1131            case Const.TABLESWITCH:
1132            case Const.LOOKUPSWITCH:
1133                max_additional_bytes += 3;
1134                break;
1135            }
1136            index += i.getLength();
1137        }
1138        /*
1139         * Pass 2: Expand the variable-length (Branch)Instructions depending on the target offset (short or int) and ensure that
1140         * branch targets are within this list.
1141         */
1142        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
1143            additional_bytes += ih.updatePosition(additional_bytes, max_additional_bytes);
1144        }
1145        /*
1146         * Pass 3: Update position numbers (which may have changed due to the preceding expansions), like pass 1.
1147         */
1148        index = count = 0;
1149        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
1150            final Instruction i = ih.getInstruction();
1151            ih.setPosition(index);
1152            pos[count++] = index;
1153            index += i.getLength();
1154        }
1155        bytePositions = new int[count]; // Trim to proper size
1156        System.arraycopy(pos, 0, bytePositions, 0, count);
1157    }
1158
1159    /**
1160     * @return length of list (Number of instructions, not bytes)
1161     */
1162    public int size() {
1163        return length;
1164    }
1165
1166    @Override
1167    public String toString() {
1168        return toString(true);
1169    }
1170
1171    /**
1172     * @param verbose toggle output format
1173     * @return String containing all instructions in this list.
1174     */
1175    public String toString(final boolean verbose) {
1176        final StringBuilder buf = new StringBuilder();
1177        for (InstructionHandle ih = start; ih != null; ih = ih.getNext()) {
1178            buf.append(ih.toString(verbose)).append("\n");
1179        }
1180        return buf.toString();
1181    }
1182
1183    /**
1184     * Call notify() method on all observers. This method is not called automatically whenever the state has changed, but
1185     * has to be called by the user after he has finished editing the object.
1186     */
1187    public void update() {
1188        if (observers != null) {
1189            for (final InstructionListObserver observer : observers) {
1190                observer.notify(this);
1191            }
1192        }
1193    }
1194}