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