X-Git-Url: http://git.megacz.com/?p=org.ibex.classgen.git;a=blobdiff_plain;f=src%2Forg%2Fibex%2Fclassgen%2FCPGen.java;h=652781680d308edc4f264cb9e7c6abe35e41e105;hp=56d51497461d15afb094c7c0061c625191d1ae83;hb=30a333241756f2eb395336ffbdb0038000b0bb56;hpb=0087af3d283954bbeeaaa857914ce9e06c39fcc7

diff --git a/src/org/ibex/classgen/CPGen.java b/src/org/ibex/classgen/CPGen.java
index 56d5149..6527816 100644
--- a/src/org/ibex/classgen/CPGen.java
+++ b/src/org/ibex/classgen/CPGen.java
@@ -5,13 +5,12 @@ import java.io.*;
 
 import org.ibex.classgen.util.*;
 
-// FEATURE: Add a "hit count" to each entry and optimize the table
-
 class CPGen {
-    private Hashtable entries = new Hashtable();
-    private int nextIndex = 1; // 0 is reserved
-    private int count;
-    private int state;
+    private final Hashtable entries = new Hashtable();
+    private Ent[] entriesByIndex; // only valid when stable
+    
+    private int usedSlots = 1; // 0 is reserved
+    private int state = OPEN;
     private static final int OPEN = 0;
     private static final int STABLE = 1; // existing entries won't change
     private static final int SEALED = 2; // no new entries
@@ -21,157 +20,376 @@ class CPGen {
     /*
      * Entries 
      */
-    abstract static class Ent {
-        int index;
+    public abstract static class Ent {
+        CPGen owner; // don't need this yet, but we will to implement ref() and unref()
+        int n; // this is the refcount if state == OPEN, index if >= STABLE
         int tag;
         
-        Ent(int tag) { this.tag = tag; }
-        
-        int getIndex() { return index; }
+        Ent(CPGen owner, int tag) { this.owner = owner; this.tag = tag; }
         
         void dump(DataOutput o) throws IOException { o.writeByte(tag); }
+        String debugToString() { return toString(); } // so we can remove this method when not debugging
+        abstract Object key() throws ClassGen.ClassReadExn; // be careful using this, it drags in a bunch of code
     }
     
-    static class OneU4Ent extends Ent {
+    // INVARIANTS: tag == 3 || tag == 4
+    static class IntEnt extends Ent {
         int i;
-        OneU4Ent(int tag) { super(tag); }
+        IntEnt(CPGen owner, int tag) { super(owner,tag); }
         void dump(DataOutput o) throws IOException { super.dump(o); o.writeInt(i);  }
+        Object key() {
+            switch(tag) {
+                case 3: return new Integer(i);
+                case 4: return new Float(Float.intBitsToFloat(i));
+                default: throw new Error("should never happen");
+            }
+        }
     }
     
+    // INVARIANTS: tag == 5 || tag == 6
     static class LongEnt extends Ent {
         long l;
-        LongEnt(int tag) { super(tag); }
+        LongEnt(CPGen owner, int tag) { super(owner,tag); }
         void dump(DataOutput o) throws IOException { super.dump(o); o.writeLong(l); }
+        Object key() {
+            switch(tag) {
+                case 5: return new Long(l);
+                case 6: return new Double(Double.longBitsToDouble(l));
+                default: throw new Error("should never happen");
+            }
+        }
     }
     
+    /* INVARIANTS:
+        tag >= 7 && tag <= 12
+        if(tag == 7 || tag == 8) e0 instanceof Utf8Ent
+        if(tag == 9 || tag == 10 || tag == 11) {
+            e0 instanceof CPRefEnt && e0.tag == 7
+            e1 instanceof CPRefEnt && e0.tag == 12
+        }
+        if(tag == 12) {
+            e0 instanceof Utf8Ent
+        }
+    */
     static class CPRefEnt extends Ent {
         Ent e1;
         Ent e2;
-        CPRefEnt(int tag) { super(tag); }
+        CPRefEnt(CPGen owner, int tag) { super(owner,tag); }
+        
+        String debugToString() { return "[" + e1.n + ":" + e1.debugToString() + (e2 == null ? "" : " + " + e2.n + ":" + e2.debugToString()) + "]"; }
+        
         void dump(DataOutput o) throws IOException {
             super.dump(o);
-            o.writeShort(e1.index);
-            if(e2 != null) o.writeShort(e2.index);
+            o.writeShort(e1.n);
+            if(e2 != null) o.writeShort(e2.n);
+        }
+        
+        Object key() throws ClassGen.ClassReadExn {
+            switch(tag) {
+                case 7: return new Type.Object(((Utf8Ent)e0).s);
+                case 8: return (((Utf8Ent)e1).s);
+                case 9:
+                    NameAndTypeKey nt = (NameAndTypeKey) e2.key();
+                    Type t = Type.fromDescriptor(nt.type);
+                    if(t == null) throw new ClassGen.ClassReadExn("invalid type descriptor");
+                    return FieldRef((Type.Object)e1.key(), nt.name, t);
+                case 10:
+                    NameAndTypeKey nt = (NameAndTypeKey) e2.key();
+                    return MethodRef((Type.Object)e1.key(),throw new Error("fixme"));
+            }
         }
     }
         
     static class Utf8Ent extends Ent {
         String s;
-        Utf8Ent() { super(1); }
+        Utf8Ent(CPGen owner) { super(owner,1); }
+        String debugToString() { return s; }
         void dump(DataOutput o) throws IOException { super.dump(o); o.writeUTF(s); }
     }
     
     /*
      * Cache Keys
      */
-    static class Utf8Key {
+    public static class Utf8Key {
         String s;
         public Utf8Key(String s) { this.s = s; }
         public boolean equals(Object o) { return o instanceof Utf8Key && ((Utf8Key)o).s.equals(s); }
         public int hashCode() { return ~s.hashCode(); }
     }
         
+    public static class NameAndTypeKey {
+        String name;
+        String type;
+        NameAndTypeKey(String name, String type) { this.name = name; this.type = type; }
+        public boolean equals(Object o_) {
+            if(!(o_ instanceof NameAndTypeKey)) return false;
+            NameAndTypeKey o = (NameAndTypeKey) o_;
+            return o.name.equals(name) && o.type.equals(type);
+        }
+        public int hashCode() { return name.hashCode() ^ type.hashCode(); }
+    }
+    
     /*
      * Methods
      */
-    public void seal() { if(state >= SEALED) throw new IllegalStateException(); state = SEALED; }
-    public void stable() { if(state >= STABLE) throw new IllegalStateException(); state = STABLE; }
     
     public final Ent get(Object o) { return (Ent) entries.get(o); }
     public final Ent getUtf8(String s) { return get(new Utf8Key(s)); }
     public final int getIndex(Object o) {
         Ent e = get(o);
         if(e == null) throw new IllegalStateException("entry not found");
-        return e.getIndex();
+        return getIndex(e);
     }
     public final int getUtf8Index(String s) {
         Ent e = getUtf8(s);
         if(e == null) throw new IllegalStateException("entry not found");
-        return e.getIndex();
+        return getIndex(e);
+    }
+    public final int getIndex(Ent ent) {
+        if(state < STABLE) throw new IllegalStateException("constant pool is not stable");
+        return ent.n;
+    }
+
+    public final Ent getByIndex(int index) {
+        if(state < STABLE) throw new IllegalStateException("constant pool is not stable");
+        Ent e;
+        if(index >= 65536 || index >= entriesByIndex.length || (e = entriesByIndex[index]) == null) 
+            throw new IllegalStateException("invalid cp index");
+        return e;
     }
     
-    public final Ent addNameAndType(String name, String descriptor) { return add(new ClassGen.NameAndType(name,descriptor)); }
+    public final Ent addNameAndType(String name, String descriptor) { return add(new NameAndTypeKey(name,descriptor)); }
     public final Ent addUtf8(String s) { return add(new Utf8Key(s)); }
     
     public final Ent add(Object o) {
         if(state == SEALED) throw new IllegalStateException("constant pool is sealed");
             
         Ent ent = get(o);
-        if(ent != null) return ent;
-        
-        if(nextIndex == 65536) throw new ClassGen.Exn("constant pool full");
+        if(ent != null) {
+            if(state == OPEN) ent.n++;
+            return ent;
+        }
         
         if(o instanceof Type.Object) {
-            CPRefEnt ce = new CPRefEnt(7);
+            CPRefEnt ce = new CPRefEnt(this,7);
             ce.e1 = addUtf8(((Type.Object)o).internalForm());
             ent = ce;
         } else if(o instanceof String) {
-            CPRefEnt ce = new CPRefEnt(8);
+            CPRefEnt ce = new CPRefEnt(this,8);
             ce.e1 = addUtf8((String)o);
             ent = ce;
         } else if(o instanceof Integer) {
-            OneU4Ent ue = new OneU4Ent(3);
+            IntEnt ue = new IntEnt(this,3);
             ue.i = ((Integer)o).intValue();
             ent = ue;
         } else if(o instanceof Float) {
-            OneU4Ent ue = new OneU4Ent(4);
+            IntEnt ue = new IntEnt(this,4);
             ue.i = Float.floatToIntBits(((Float)o).floatValue());
             ent = ue;
         } else if(o instanceof Long) {
-            LongEnt le = new LongEnt(5);
+            LongEnt le = new LongEnt(this,5);
             le.l = ((Long)o).longValue();
             ent = le;
         } else if(o instanceof Double) {
-            LongEnt le = new LongEnt(6);
+            LongEnt le = new LongEnt(this,6);
             le.l = Double.doubleToLongBits(((Double)o).doubleValue());
             ent = le;
         } else if(o instanceof Utf8Key) {
-            Utf8Ent ue = new Utf8Ent();
+            Utf8Ent ue = new Utf8Ent(this);
             ue.s = ((Utf8Key)o).s;
             ent = ue;
-        } else if(o instanceof ClassGen.NameAndType) {
-            CPRefEnt ce = new CPRefEnt(12);
-            ClassGen.NameAndType key = (ClassGen.NameAndType) o;
+        } else if(o instanceof NameAndTypeKey) {
+            CPRefEnt ce = new CPRefEnt(this,12);
+            NameAndTypeKey key = (NameAndTypeKey) o;
             ce.e1 = addUtf8(key.name);
             ce.e2 = addUtf8(key.type);
             ent = ce;
-        } else if(o instanceof ClassGen.FieldMethodRef) {
-            ClassGen.FieldMethodRef key = (ClassGen.FieldMethodRef) o;
-            int tag = o instanceof FieldRef ? 9 : o instanceof MethodRef ? 10 : o instanceof ClassGen.InterfaceMethodRef ? 11 : 0;
+        } else if(o instanceof ClassGen.FieldOrMethodRef) {
+            ClassGen.FieldOrMethodRef key = (ClassGen.FieldOrMethodRef) o;
+            int tag = o instanceof FieldRef ? 9 : o instanceof MethodRef ? 10 : o instanceof MethodRef.I ? 11 : 0;
             if(tag == 0) throw new Error("should never happen");
-            CPRefEnt ce = new CPRefEnt(tag);
+            CPRefEnt ce = new CPRefEnt(this,tag);
             ce.e1 = add(key.klass);
-            ce.e2 = add(key.nameAndType);
+            ce.e2 = addNameAndType(key.name,key.descriptor);
             ent = ce;
         } else {
             throw new IllegalArgumentException("Unknown type passed to add");
         }
         
-        ent.index = nextIndex++;
-        if(ent instanceof LongEnt) nextIndex++;
-        count++;
+        int spaces = ent instanceof LongEnt ? 2 : 1;        
+        if(usedSlots + spaces > 65536) throw new ClassGen.Exn("constant pool full");
+        
+        ent.n = state == OPEN ? 1 : usedSlots; // refcount or index
+
+        usedSlots += spaces;        
 
         entries.put(o,ent);
         return ent;
     }
     
-    public int size() { return nextIndex; }
+    public int slots() { return usedSlots; }
+
+    public void seal() { state = SEALED; }
     
-    private static final Sort.CompareFunc compareFunc = new Sort.CompareFunc() {
-        public int compare(Object a_, Object b_) {
-            return ((Ent)a_).index - ((Ent)b_).index;
-        }
-    };
-    public void dump(DataOutput o) throws IOException {
+    private Ent[] asArray() {
+        int count = entries.size();
         Ent[] ents = new Ent[count];
         int i=0;
         Enumeration e = entries.keys();
         while(e.hasMoreElements()) ents[i++] = (Ent) entries.get(e.nextElement());
         if(i != count) throw new Error("should never happen");
+        return ents;
+    }
+    
+    private void assignIndex(Ent[] ents) {
+        int index = 1;
+        entriesByIndex = new Ent[ents.length*2];
+        for(int i=0;i<ents.length;i++) {
+            Ent ent = ents[i];
+            ent.n = index;
+            entriesByIndex[index] = ent;
+            index += ent instanceof LongEnt ? 2 : 1;
+        }
+    }
+        
+    public void stable() {
+        if(state != OPEN) return;
+        state = STABLE;
+        assignIndex(asArray());
+    } 
+
+    private static final Sort.CompareFunc compareFunc = new Sort.CompareFunc() {
+        public int compare(Object a_, Object b_) {
+            return ((Ent)a_).n - ((Ent)b_).n;
+        }
+    };
+    
+    private static final Sort.CompareFunc reverseCompareFunc = new Sort.CompareFunc() {
+        public int compare(Object a_, Object b_) {
+            return ((Ent)b_).n - ((Ent)a_).n;
+        }
+    };
+    
+    public void optimize() {
+        if(state != OPEN) throw new IllegalStateException("can't optimize a stable constant pool");
+        Ent[] ents = asArray();
+        Sort.sort(ents,reverseCompareFunc);
+        state = STABLE;
+        assignIndex(ents);
+    }
+    
+    public void unsafeReopen() {
+        if(state == OPEN) return;
+        for(int i=1;i<entriesByIndex.length;i++) {
+            Ent e = entriesByIndex[i];
+            if(e == null) continue;
+            e.n = 0;
+        }
+        entriesByIndex = null;
+        state = OPEN;
+    }
+    
+    public void dump(DataOutput o) throws IOException {
+        Ent[] ents = asArray();
         Sort.sort(ents,compareFunc);
-        for(i=0;i<ents.length;i++) {
-            //System.err.println("" + (i+1) + ": " + ents[i]);
+        o.writeShort(usedSlots);
+        for(int i=0;i<ents.length;i++) {
+            //System.err.println("" + ents[i].n + ": " + ents[i].debugToString());
             ents[i].dump(o);
         }
     }
+    
+    CPGen(DataInput in) throws ClassGen.ClassReadExn {
+        usedSlots = i.readUnsignedShort();
+        if(usedSlots==0) throw new ClassGen.ClassReadExn("invalid used slots");
+        
+        // these are to remember the CPRefEnt e0 and e1s we have to fix up
+        int[] e1s = new int[usedSlots];
+        int[] e2s = new int[usedSlots];
+        
+        entriesByIndex = new Ent[usedSlots];
+        
+        for(int index=1;index<usedSlots;index++) {
+            byte tag = i.readByte();
+            Ent e;
+            switch(tag) {
+                case 7: // Object Type
+                case 8: // String
+                case 9: // FieldRef
+                case 10: // MethodRef
+                case 11: // Instance Method Ref
+                case 12: // NameAndType
+                {
+                    e = new CPRefEnt(this,tag);
+                    e1s[index] = i.readUnsignedShort();;
+                    if(tag != 7 && tag != 8) e2s[index] = i.readUnsignedShort();
+                    break;
+                }
+                case 3: // Integer
+                case 4: // Float
+                {
+                    IntEnt ie;
+                    e = ie = new IntEnt(this,tag);
+                    ie.i = i.readInt();
+                    break;
+                }
+                case 5: // Long
+                case 6: // Double
+                {
+                    LongEnt le;
+                    e = le = new LongEnt(this,tag);
+                    le.l = i.readLong();
+                    index++;
+                    break;
+                }
+                case 1: // Utf8
+                {
+                    Utf8Ent ue;
+                    e = ue = new Utf8Ent(this);
+                    ue.s = i.readUTF();
+                    break;
+                }
+                default:
+                    throw new ClassGen.ClassReadExn("invalid cp ent tag");
+            }
+            entriesByIndex[index] = e;
+        }
+        
+        for(int index=1;index<usedSlots;index++) {
+            Ent e = entriesByIndex[index];
+            if(e == null) throw new Error("should never happen");
+            if(e instanceof CPRefEnt) {
+                CPRefEnt ce = (CPRefEnt) e;
+                if(e0s[i] == 0 || e0s[i] >= usedSlots) throw new ClassGen.ClassReadExn("invalid cp index");
+                ce.e0 = entriesByIndex[e0s[i]];
+                if(ce.e0 == null)  throw new ClassGen.ClassReadExn("invalid cp index");
+                if(ce.tag != 7 && ce.tag != 8) {
+                    if(e1s[i] == 0 || e1s[i] >= usedSlots) throw new ClassGen.ClassReadExn("invalid cp index");
+                    ce.e1 = entriesByIndex[e1s[i]];
+                    if(ce.e1 == null)  throw new ClassGen.ClassReadExn("invalid cp index");
+                }
+                switch(ce.tag) {
+                    case 7:
+                    case 8:
+                        if(!(ce.e0 instanceof Utf8Ent)) throw new ClassGen.ClassReadExn("expected a utf8 ent");
+                        break;
+                    case 9:
+                    case 10:
+                    case 11:
+                        if(!(ce.e1 instanceof CPRefEnt) || ((CPRefEnt)ce.e1).tag != 7)
+                            throw new ClassGen.ClassReadExn("expected a type ent");
+                        if(!(ce.e2 instanceof CPRefEnt) || ((CPRefEnt)ce.e2).tag != 12)
+                            throw new ClassGen.ClassReadExn("expected a name and type ent");
+                        break;
+                    case 12:
+                        if(!(ce.e1 instanceof Utf8Ent)) throw new ClassGen.ClassReadExn("expected a utf8 ent");
+                        if(!(ce.e2 instanceof Utf8Ent)) throw new ClassGen.ClassReadExn("expected a utf8 ent");
+                }
+            } else if(e instanceof LongEnt) {
+                index++;
+            }
+            entries.put(e.key(),e);
+        }
+        state = STABLE;
+    }
 }