jdk/src/share/classes/com/sun/java/util/jar/pack/Fixups.java

/*
 * Copyright 2003 Sun Microsystems, Inc.  All Rights Reserved.
 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
 *
 * This code is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License version 2 only, as
 * published by the Free Software Foundation.  Sun designates this
 * particular file as subject to the "Classpath" exception as provided
 * by Sun in the LICENSE file that accompanied this code.
 *
 * This code is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * version 2 for more details (a copy is included in the LICENSE file that
 * accompanied this code).
 *
 * You should have received a copy of the GNU General Public License version
 * 2 along with this work; if not, write to the Free Software Foundation,
 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
 *
 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
 * CA 95054 USA or visit www.sun.com if you need additional information or
 * have any questions.
 */

package com.sun.java.util.jar.pack;

import java.io.*;
import java.util.*;
import com.sun.java.util.jar.pack.ConstantPool.*;

/**
 * Collection of relocatable constant pool references.
 * It operates with respect to a particular byte array,
 * and stores some of its state in the bytes themselves.
 * <p>
 * As a Collection, it can be iterated over, but it is not a List,
 * since it does not natively support indexed access.
 * <p>
 *
 * @author John Rose
 */
class Fixups extends AbstractCollection implements Constants {
    byte[] bytes;    // the subject of the relocations
    int head;        // desc locating first reloc
    int tail;        // desc locating last reloc
    int size;        // number of relocations
    Entry[] entries; // [0..size-1] relocations
    int[] bigDescs;  // descs which cannot be stored in the bytes

    // A "desc" (descriptor) is a bit-encoded pair of a location
    // and format.  Every fixup occurs at a "desc".  Until final
    // patching, bytes addressed by descs may also be used to
    // link this data structure together.  If the bytes are missing,
    // or if the "desc" is too large to encode in the bytes,
    // it is kept in the bigDescs array.

    Fixups(byte[] bytes) {
        this.bytes = bytes;
        entries = new Entry[3];
        bigDescs = noBigDescs;
    }
    Fixups() {
        // If there are no bytes, all descs are kept in bigDescs.
        this((byte[])null);
    }
    Fixups(byte[] bytes, Collection fixups) {
        this(bytes);
        addAll(fixups);
    }
    Fixups(Collection fixups) {
        this((byte[])null);
        addAll(fixups);
    }

    private static final int MINBIGSIZE = 1;
    // cleverly share empty bigDescs:
    private static int[] noBigDescs = {MINBIGSIZE};

    public int size() {
        return size;
    }

    public void trimToSize() {
        if (size != entries.length) {
            Entry[] oldEntries = entries;
            entries = new Entry[size];
            System.arraycopy(oldEntries, 0, entries, 0, size);
        }
        int bigSize = bigDescs[BIGSIZE];
        if (bigSize == MINBIGSIZE) {
            bigDescs = noBigDescs;
        } else if (bigSize != bigDescs.length) {
            int[] oldBigDescs = bigDescs;
            bigDescs = new int[bigSize];
            System.arraycopy(oldBigDescs, 0, bigDescs, 0, bigSize);
        }
    }

    public void visitRefs(Collection refs) {
        for (int i = 0; i < size; i++) {
            refs.add(entries[i]);
        }
    }

    public void clear() {
        if (bytes != null) {
            // Clean the bytes:
            for (Iterator i = iterator(); i.hasNext(); ) {
                Fixup fx = (Fixup) i.next();
                //System.out.println("clean "+fx);
                storeIndex(fx.location(), fx.format(), 0);
            }
        }
        size = 0;
        if (bigDescs != noBigDescs)
            bigDescs[BIGSIZE] = MINBIGSIZE;
        // do not trim to size, however
    }

    public byte[] getBytes() {
        return bytes;
    }

    public void setBytes(byte[] newBytes) {
        if (bytes == newBytes)  return;
        ArrayList old = null;
        assert((old = new ArrayList(this)) != null);
        if (bytes == null || newBytes == null) {
            // One or the other representations is deficient.
            // Construct a checkpoint.
            ArrayList save = new ArrayList(this);
            clear();
            bytes = newBytes;
            addAll(save);
        } else {
            // assume newBytes is some sort of bitwise copy of the old bytes
            bytes = newBytes;
        }
        assert(old.equals(new ArrayList(this)));
    }

    static final int LOC_SHIFT = 1;
    static final int FMT_MASK = 0x1;
    static final byte UNUSED_BYTE = 0;
    static final byte OVERFLOW_BYTE = -1;
    // fill pointer of bigDescs array is in element [0]
    static final int BIGSIZE = 0;

    // Format values:
    public static final int U2_FORMAT = 0;
    public static final int U1_FORMAT = 1;

    // Special values for the static methods.
    private static final int SPECIAL_LOC = 0;
    private static final int SPECIAL_FMT = U2_FORMAT;

    static int fmtLen(int fmt) { return 1+(fmt-U1_FORMAT)/(U2_FORMAT-U1_FORMAT); }
    static int descLoc(int desc) { return desc >>> LOC_SHIFT; }
    static int descFmt(int desc) { return desc  &  FMT_MASK; }
    static int descEnd(int desc) { return descLoc(desc) + fmtLen(descFmt(desc)); }
    static int makeDesc(int loc, int fmt) {
        int desc = (loc << LOC_SHIFT) | fmt;
        assert(descLoc(desc) == loc);
        assert(descFmt(desc) == fmt);
        return desc;
    }
    int fetchDesc(int loc, int fmt) {
        byte b1 = bytes[loc];
        assert(b1 != OVERFLOW_BYTE);
        int value;
        if (fmt == U2_FORMAT) {
            byte b2 = bytes[loc+1];
            value = ((b1 & 0xFF) << 8) + (b2 & 0xFF);
        } else {
            value = (b1 & 0xFF);
        }
        // Stored loc field is difference between its own loc and next loc.
        return value + (loc << LOC_SHIFT);
    }
    boolean storeDesc(int loc, int fmt, int desc) {
        if (bytes == null)
            return false;
        int value = desc - (loc << LOC_SHIFT);
        byte b1, b2;
        switch (fmt) {
        case U2_FORMAT:
            assert(bytes[loc+0] == UNUSED_BYTE);
            assert(bytes[loc+1] == UNUSED_BYTE);
            b1 = (byte)(value >> 8);
            b2 = (byte)(value >> 0);
            if (value == (value & 0xFFFF) && b1 != OVERFLOW_BYTE) {
                bytes[loc+0] = b1;
                bytes[loc+1] = b2;
                assert(fetchDesc(loc, fmt) == desc);
                return true;
            }
            break;
        case U1_FORMAT:
            assert(bytes[loc] == UNUSED_BYTE);
            b1 = (byte)value;
            if (value == (value & 0xFF) && b1 != OVERFLOW_BYTE) {
                bytes[loc] = b1;
                assert(fetchDesc(loc, fmt) == desc);
                return true;
            }
            break;
        default: assert(false);
        }
        // Failure.  Caller must allocate a bigDesc.
        bytes[loc] = OVERFLOW_BYTE;
        assert(fmt==U1_FORMAT || (bytes[loc+1]=(byte)bigDescs[BIGSIZE])!=999);
        return false;
    }
    void storeIndex(int loc, int fmt, int value) {
        storeIndex(bytes, loc, fmt, value);
    }
    static
    void storeIndex(byte[] bytes, int loc, int fmt, int value) {
        switch (fmt) {
        case U2_FORMAT:
            assert(value == (value & 0xFFFF)) : (value);
            bytes[loc+0] = (byte)(value >> 8);
            bytes[loc+1] = (byte)(value >> 0);
            break;
        case U1_FORMAT:
            assert(value == (value & 0xFF)) : (value);
            bytes[loc] = (byte)value;
            break;
        default: assert(false);
        }
    }

    /** Simple and necessary tuple to present each fixup. */
    public static
    class Fixup implements Comparable {
        int desc;         // location and format of reloc
        Entry entry;      // which entry to plug into the bytes
        Fixup(int desc, Entry entry) {
            this.desc = desc;
            this.entry = entry;
        }
        public Fixup(int loc, int fmt, Entry entry) {
            this.desc = makeDesc(loc, fmt);
            this.entry = entry;
        }
        public int location() { return descLoc(desc); }
        public int format() { return descFmt(desc); }
        public Entry entry() { return entry; }
        public int compareTo(Fixup that) {
            // Ordering depends only on location.
            return this.location() - that.location();
        }
        public int compareTo(Object that) {
            return compareTo((Fixup)that);
        }
        public boolean equals(Object x) {
            if (!(x instanceof Fixup))  return false;
            Fixup that = (Fixup) x;
            return this.desc == that.desc && this.entry == that.entry;
        }
        public String toString() {
            return "@"+location()+(format()==U1_FORMAT?".1":"")+"="+entry;
        }
    }

    private
    class Itr implements Iterator {
        int index = 0;               // index into entries
        int bigIndex = BIGSIZE+1;    // index into bigDescs
        int next = head;             // desc pointing to next fixup
        public boolean hasNext() { return index < size; }
        public void remove() { throw new UnsupportedOperationException(); }
        public Object next() {
            int thisIndex = index;
            return new Fixup(nextDesc(), entries[thisIndex]);
        }
        int nextDesc() {
            int thisIndex = index++;
            int thisDesc = next;
            if (index < size) {
                // Fetch next desc eagerly, in case this fixup gets finalized.
                int loc = descLoc(thisDesc);
                int fmt = descFmt(thisDesc);
                if (bytes != null && bytes[loc] != OVERFLOW_BYTE) {
                    next = fetchDesc(loc, fmt);
                } else {
                    // The unused extra byte is "asserted" to be equal to BI.
                    // This helps keep the overflow descs in sync.
                    assert(fmt==U1_FORMAT || bytes == null || bytes[loc+1]==(byte)bigIndex);
                    next = bigDescs[bigIndex++];
                }
            }
            return thisDesc;
        }
    }

    public Iterator iterator() {
        return new Itr();
    }
    public void add(int location, int format, Entry entry) {
        addDesc(makeDesc(location, format), entry);
    }
    public boolean add(Fixup f) {
        addDesc(f.desc, f.entry);
        return true;
    }
    public boolean add(Object fixup) {
        return add((Fixup) fixup);
    }
    public boolean addAll(Collection c) {
        if (c instanceof Fixups) {
            // Use knowledge of Itr structure to avoid building little structs.
            Fixups that = (Fixups) c;
            if (that.size == 0)  return false;
            if (this.size == 0 && entries.length < that.size)
                growEntries(that.size);  // presize exactly
            Entry[] thatEntries = that.entries;
            for (Itr i = that.new Itr(); i.hasNext(); ) {
                int ni = i.index;
                addDesc(i.nextDesc(), thatEntries[ni]);
            }
            return true;
        } else {
            return super.addAll(c);
        }
    }
    // Here is how things get added:
    private void addDesc(int thisDesc, Entry entry) {
        if (entries.length == size)
            growEntries(size * 2);
        entries[size] = entry;
        if (size == 0) {
            head = tail = thisDesc;
        } else {
            int prevDesc = tail;
            // Store new desc in previous tail.
            int prevLoc = descLoc(prevDesc);
            int prevFmt = descFmt(prevDesc);
            int prevLen = fmtLen(prevFmt);
            int thisLoc = descLoc(thisDesc);
            // The collection must go in ascending order, and not overlap.
            if (thisLoc < prevLoc + prevLen)
                badOverlap(thisLoc);
            tail = thisDesc;
            if (!storeDesc(prevLoc, prevFmt, thisDesc)) {
                // overflow
                int bigSize = bigDescs[BIGSIZE];
                if (bigDescs.length == bigSize)
                    growBigDescs();
                //System.out.println("bigDescs["+bigSize+"] = "+thisDesc);
                bigDescs[bigSize++] = thisDesc;
                bigDescs[BIGSIZE] = bigSize;
            }
        }
        size += 1;
    }
    private void badOverlap(int thisLoc) {
        throw new IllegalArgumentException("locs must be ascending and must not overlap:  "+thisLoc+" >> "+this);
    }

    private void growEntries(int newSize) {
        Entry[] oldEntries = entries;
        entries = new Entry[Math.max(3, newSize)];
        System.arraycopy(oldEntries, 0, entries, 0, oldEntries.length);
    }
    private void growBigDescs() {
        int[] oldBigDescs = bigDescs;
        bigDescs = new int[oldBigDescs.length * 2];
        System.arraycopy(oldBigDescs, 0, bigDescs, 0, oldBigDescs.length);
    }

    /// Static methods that optimize the use of this class.
    public static
    Object add(Object prevFixups,
               byte[] bytes, int loc, int fmt,
               Entry e) {
        Fixups f;
        if (prevFixups == null) {
            if (loc == SPECIAL_LOC && fmt == SPECIAL_FMT) {
                // Special convention:  If the attribute has a
                // U2 relocation at position zero, store the Entry
                // rather than building a Fixups structure.
                return e;
            }
            f = new Fixups(bytes);
        } else if (!(prevFixups instanceof Fixups)) {
            // Recognize the special convention:
            Entry firstEntry = (Entry) prevFixups;
            f = new Fixups(bytes);
            f.add(SPECIAL_LOC, SPECIAL_FMT, firstEntry);
        } else {
            f = (Fixups) prevFixups;
            assert(f.bytes == bytes);
        }
        f.add(loc, fmt, e);
        return f;
    }

    public static
    void setBytes(Object fixups, byte[] bytes) {
        if (fixups instanceof Fixups) {
            Fixups f = (Fixups) fixups;
            f.setBytes(bytes);
        }
    }

    public static
    Object trimToSize(Object fixups) {
        if (fixups instanceof Fixups) {
            Fixups f = (Fixups) fixups;
            f.trimToSize();
            if (f.size() == 0)
                fixups = null;
        }
        return fixups;
    }

    // Iterate over all the references in this set of fixups.
    public static
    void visitRefs(Object fixups, Collection refs) {
        if (fixups == null) {
        } else if (!(fixups instanceof Fixups)) {
            // Special convention; see above.
            refs.add((Entry) fixups);
        } else {
            Fixups f = (Fixups) fixups;
            f.visitRefs(refs);
        }
    }

    // Clear out this set of fixups by replacing each reference
    // by a hardcoded coding of its reference, drawn from ix.
    public static
    void finishRefs(Object fixups, byte[] bytes, ConstantPool.Index ix) {
        if (fixups == null)
            return;
        if (!(fixups instanceof Fixups)) {
            // Special convention; see above.
            int index = ix.indexOf((Entry) fixups);
            storeIndex(bytes, SPECIAL_LOC, SPECIAL_FMT, index);
            return;
        }
        Fixups f = (Fixups) fixups;
        assert(f.bytes == bytes);
        f.finishRefs(ix);
    }

    void finishRefs(ConstantPool.Index ix) {
        if (isEmpty())
            return;
        for (Iterator i = iterator(); i.hasNext(); ) {
            Fixup fx = (Fixup) i.next();
            int index = ix.indexOf(fx.entry);
            //System.out.println("finish "+fx+" = "+index);
            // Note that the iterator has already fetched the
            // bytes we are about to overwrite.
            storeIndex(fx.location(), fx.format(), index);
        }
        // Further iterations should do nothing:
        bytes = null;  // do not clean them
        clear();
    }

/*
    /// Testing.
    public static void main(String[] av) {
        byte[] bytes = new byte[1 << 20];
        ConstantPool cp = new ConstantPool();
        Fixups f = new Fixups(bytes);
        boolean isU1 = false;
        int span = 3;
        int nextLoc = 0;
        int[] locs = new int[100];
        final int[] indexes = new int[100];
        int iptr = 1;
        for (int loc = 0; loc < bytes.length; loc++) {
            if (loc == nextLoc && loc+1 < bytes.length) {
                int fmt = (isU1 ? U1_FORMAT : U2_FORMAT);
                Entry e = ConstantPool.getUtf8Entry("L"+loc);
                f.add(loc, fmt, e);
                isU1 ^= true;
                if (iptr < 10) {
                    // Make it close in.
                    nextLoc += fmtLen(fmt) + (iptr < 5 ? 0 : 1);
                } else {
                    nextLoc += span;
                    span = (int)(span * 1.77);
                }
                // Here are the bytes that would have gone here:
                locs[iptr] = loc;
                if (fmt == U1_FORMAT) {
                    indexes[iptr++] = (loc & 0xFF);
                } else {
                    indexes[iptr++] = ((loc & 0xFF) << 8) | ((loc+1) & 0xFF);
                    ++loc;  // skip a byte
                }
                continue;
            }
            bytes[loc] = (byte)loc;
        }
        System.out.println("size="+f.size()
                           +" overflow="+(f.bigDescs[BIGSIZE]-1));
        System.out.println("Fixups: "+f);
        // Test collection contents.
        assert(iptr == 1+f.size());
        List l = new ArrayList(f);
        Collections.sort(l);  // should not change the order
        if (!l.equals(new ArrayList(f)))  System.out.println("** disordered");
        f.setBytes(null);
        if (!l.equals(new ArrayList(f)))  System.out.println("** bad set 1");
        f.setBytes(bytes);
        if (!l.equals(new ArrayList(f)))  System.out.println("** bad set 2");
        Fixups f3 = new Fixups(f);
        if (!l.equals(new ArrayList(f3))) System.out.println("** bad set 3");
        Iterator fi = f.iterator();
        for (int i = 1; i < iptr; i++) {
            Fixup fx = (Fixup) fi.next();
            if (fx.location() != locs[i]) {
                System.out.println("** "+fx+" != "+locs[i]);
            }
            if (fx.format() == U1_FORMAT)
                System.out.println(fx+" -> "+bytes[locs[i]]);
            else
                System.out.println(fx+" -> "+bytes[locs[i]]+" "+bytes[locs[i]+1]);
        }
        assert(!fi.hasNext());
        indexes[0] = 1;  // like iptr
        Index ix = new Index("ix") {
            public int indexOf(Entry e) {
                return indexes[indexes[0]++];
            }
        };
        f.finishRefs(ix);
        for (int loc = 0; loc < bytes.length; loc++) {
            if (bytes[loc] != (byte)loc) {
                System.out.println("** ["+loc+"] = "+bytes[loc]+" != "+(byte)loc);
            }
        }
    }
//*/
}