First cut function ptr type

3 files changed, 106 insertions, 3 deletions

diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java
index 4ebb2b6d..57eb1e98 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/type/Type.java
@@ -40,6 +40,7 @@ public class Type {
     static final byte TSTRUCT =10; // Structs; tuples with named fields
     static final byte TFLD    =11; // Fields into struct
     static final byte TARRAY  =12; // Array
+    static final byte TFUNPTR =13; // Function
 
     public final byte _type;
 
@@ -62,6 +63,7 @@ public class Type {
         TypeMemPtr.gather(ts);
         TypeStruct.gather(ts);
         TypeTuple.gather(ts);
+        TypeFunPtr.gather(ts);
         int sz = ts.size();
         for( int i = 0; i < sz; i++ )
             ts.add(ts.get(i).dual());
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
new file mode 100644
index 00000000..63ca2763
--- /dev/null
+++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java
@@ -0,0 +1,96 @@
+package com.seaofnodes.simple.type;
+
+import com.seaofnodes.simple.Utils;
+import java.util.ArrayList;
+
+/**
+ * Represents a Pointer to a function.
+ *
+ * Functions have argument types and a return type, making a function
+ * signature.  Within a signature there can be many instances of functions, and
+ * each function is labeled with a small integer constant.  A TFP can represent
+ * a single signature and a set of functions; the set might contain only 1
+ * function or the zeroth function (the null ptr).
+ *
+ * Functions with different signatures cannot be mixed, and will result in a
+ * bottom function type, which can only be null-checked.
+ */
+public class TypeFunPtr extends Type {
+    // A TypeFunPtr is Signature and a set of functions.
+    public final TypeTuple _sig;
+    // Cheesy easy implementation for a small set; 1 bit per unique function
+    // within the TypeTuple.  Can be upgraded to a BitSet for larger classes of
+    // functions.
+    private final long _fidxs; // 0 bit for null, and up to 63 unique functions per signature
+
+    private TypeFunPtr(TypeTuple sig, long fidxs) {
+        super(TFUNPTR);
+        assert sig != null;
+        _sig = sig;
+        _fidxs = fidxs;
+    }
+
+    public static TypeFunPtr make( TypeTuple sig, long fidxs ) { return new TypeFunPtr(sig,fidxs).intern(); }
+
+    public static TypeFunPtr BOT     = make(TypeTuple.SIGBOT,-1);
+    public static TypeFunPtr TOP     = BOT.dual();
+    public static TypeFunPtr TEST    = make(TypeTuple.SIGTEST,2);
+    public static TypeFunPtr TEST0   = make(TypeTuple.SIGTEST,3);
+    public static TypeFunPtr NULLPTR = make(TypeTuple.SIGTOP,1);
+    public static TypeFunPtr VOIDPTR = NULLPTR.dual();
+    public static void gather(ArrayList<Type> ts) { ts.add(TEST); ts.add(TEST0); ts.add(NULLPTR); ts.add(BOT); }
+
+    @Override
+    Type xmeet(Type t) {
+        TypeFunPtr that = (TypeFunPtr) t;
+        return TypeFunPtr.make((TypeTuple)_sig.meet(that._sig), _fidxs | that._fidxs);
+    }
+
+    @Override
+    public TypeFunPtr dual() { return TypeFunPtr.make(_sig.dual(), ~_fidxs); }
+
+    @Override public TypeFunPtr glb() { throw Utils.TODO(); }
+    @Override public TypeFunPtr lub() { throw Utils.TODO(); }
+    // Is forward-reference
+    @Override public boolean isFRef() { return false; }
+    @Override public Type makeInit() { return (_fidxs&1)==1 ? NULLPTR : Type.TOP; }
+    @Override public Type makeZero() { return NULLPTR; }
+    @Override public Type  nonZero() { return VOIDPTR; }
+
+    @Override public boolean isHigh() { return this==TOP; }
+    @Override public boolean isConstant() { return Long.bitCount(_fidxs)==1; }
+    @Override public boolean isHighOrConst() { return Long.bitCount(_fidxs)<=1; }
+
+    @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers
+
+    @Override
+    int hash() { return Utils.fold(_sig.hashCode() ^ _fidxs); }
+
+    @Override
+    boolean eq(Type t) {
+        TypeFunPtr ptr = (TypeFunPtr)t; // Invariant
+        return _sig == ptr._sig  && _fidxs == ptr._fidxs;
+    }
+
+    // [void,name,MANY]*[,?]
+    @Override
+    public StringBuilder print(StringBuilder sb) {
+        if( this== NULLPTR) return sb.append("null");
+        if( this== VOIDPTR) return sb.append("*void");
+        sb.append("{ ");
+        for( int i=1; i<_sig._types.length; i++ )
+            _sig._types[i].print(sb).append(" ");
+        _sig._types[0].print(sb.append("-> "));
+        sb.append(String.format(" #%X",_fidxs));
+        sb.append("}");
+        if( (_fidxs&1)==1 ) sb.append("?");
+        return sb;
+    }
+
+    @Override public String str() {
+        if( this== NULLPTR) return "null";
+        if( this== VOIDPTR) return "*void";
+        return print(new StringBuilder()).toString();
+    }
+
+}
diff --git a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeTuple.java b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
index a34c64db..8a98952c 100644
--- a/chapter18/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
+++ b/chapter18/src/main/java/com/seaofnodes/simple/type/TypeTuple.java
@@ -11,20 +11,25 @@ public class TypeTuple extends Type {
 
     private static final TypeTuple TEST = make(TypeInteger.BOT,TypeMemPtr.TEST);
     public  static final TypeTuple START = make(Type.CONTROL,TypeMem.TOP,TypeInteger.BOT);
-    public  static void gather(ArrayList<Type> ts) {  ts.add(TEST); ts.add(START); }
+    public  static final TypeTuple SIGTEST = make(TypeInteger.BOT,TypeInteger.BOT);
+    public  static final TypeTuple SIGBOT = make(Type.BOTTOM);
+    public  static final TypeTuple SIGTOP = SIGBOT.dual();
+    public  static void gather(ArrayList<Type> ts) {  ts.add(TEST); ts.add(START); ts.add(SIGTEST); }
 
     @Override
     Type xmeet(Type other) {
         TypeTuple tt = (TypeTuple)other;     // contract from xmeet
+        if( this==SIGTOP ) return other;
+        if( tt  ==SIGTOP ) return this ;
         if( _types.length != tt._types.length )
-            return BOTTOM;
+            return SIGBOT;
         Type[] ts = new Type[_types.length];
         for( int i=0; i<_types.length; i++ )
             ts[i] = _types[i].meet(tt._types[i]);
         return make(ts);
     }
 
-    @Override public Type dual() {
+    @Override public TypeTuple dual() {
         Type[] ts = new Type[_types.length];
         for( int i=0; i<_types.length; i++ )
             ts[i] = _types[i].dual();