From 69249d4c8d043e6348ecf797a2afa391726ab6d7 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Tue, 26 Nov 2024 12:17:29 -0800 Subject: First cut function ptr type --- .../main/java/com/seaofnodes/simple/type/Type.java | 2 + .../com/seaofnodes/simple/type/TypeFunPtr.java | 96 ++++++++++++++++++++++ .../java/com/seaofnodes/simple/type/TypeTuple.java | 11 ++- .../java/com/seaofnodes/simple/Chapter18Test.java | 36 ++++++++ 4 files changed, 142 insertions(+), 3 deletions(-) create mode 100644 chapter18/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java create mode 100644 chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java (limited to 'chapter18/src') 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 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 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 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(); diff --git a/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java new file mode 100644 index 00000000..2c6cca8c --- /dev/null +++ b/chapter18/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -0,0 +1,36 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.evaluator.Evaluator; +import com.seaofnodes.simple.node.StopNode; +import org.junit.Test; +import org.junit.Ignore; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.fail; + +public class Chapter18Test { + + @Test + public void testJig() { + Parser parser = new Parser(""" +return 3.14; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return 3.14;", stop.toString()); + assertEquals(3.14, Evaluator.evaluate(stop, 0)); + } + + + // --------------------------------------------------------------- + @Test + public void testType0() { + Parser parser = new Parser(""" +{int -> int}? x2 = null; // null function ptr +return x2; +"""); + StopNode stop = parser.parse().iterate(); + assertEquals("return arg;", stop.toString()); + assertEquals(0L, Evaluator.evaluate(stop, 0)); + } + + +} -- cgit v1.2.3