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