From 22df891893d30e9906d0b14fc3ae5d8e67d500b2 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 3 Oct 2026 14:03:48 -0700 Subject: Chapter renumber, and split ch 17 Renumber chapters 10a, 10b, 11, 12, 13, 14 -> 10, 11, 13, 12, [11,14]. Split ch 17 into a 17a and 17b; shuffle around im/mutable syntax to be consistent, and present it more slowly. THe new immutable syntax is pushed through all later chapters --- chapter25/Makefile | 2 +- chapter25/README.md | 4 + chapter25/ROADMAP.md | 16 +- chapter25/docs/examples/BubbleSort.smp | 2 +- chapter25/docs/examples/Dijkstra.smp | 2 +- .../main/java/com/seaofnodes/simple/Parser.java | 95 ++-- .../com/seaofnodes/simple/codegen/Serialize.java | 11 +- .../com/seaofnodes/simple/node/CallEndNode.java | 2 +- .../java/com/seaofnodes/simple/node/CallNode.java | 2 +- .../com/seaofnodes/simple/node/ConvertNode.java | 4 +- .../java/com/seaofnodes/simple/node/LoadNode.java | 5 +- .../java/com/seaofnodes/simple/node/StoreNode.java | 2 +- .../main/java/com/seaofnodes/simple/type/Type.java | 4 + .../com/seaofnodes/simple/type/TypeMemPtr.java | 68 ++- chapter25/src/main/smp/sys/aryi64.smp | 2 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 36 +- .../java/com/seaofnodes/simple/Chapter11Test.java | 284 ---------- .../java/com/seaofnodes/simple/Chapter12Test.java | 280 ++++++++-- .../java/com/seaofnodes/simple/Chapter13Test.java | 377 ++++++------- .../com/seaofnodes/simple/Chapter14FloatTest.java | 83 +++ .../java/com/seaofnodes/simple/Chapter14Test.java | 2 +- .../java/com/seaofnodes/simple/Chapter15Test.java | 32 +- .../java/com/seaofnodes/simple/Chapter16Test.java | 120 +---- .../java/com/seaofnodes/simple/Chapter17Test.java | 593 --------------------- .../java/com/seaofnodes/simple/Chapter17aTest.java | 109 ++++ .../java/com/seaofnodes/simple/Chapter17bTest.java | 593 +++++++++++++++++++++ .../java/com/seaofnodes/simple/Chapter18Test.java | 12 +- .../java/com/seaofnodes/simple/Chapter19Test.java | 16 +- .../java/com/seaofnodes/simple/Chapter20Test.java | 18 +- .../java/com/seaofnodes/simple/Chapter21Test.java | 26 +- .../java/com/seaofnodes/simple/Chapter22Test.java | 20 +- .../java/com/seaofnodes/simple/Chapter23Test.java | 16 +- .../java/com/seaofnodes/simple/Chapter25Test.java | 23 +- .../seaofnodes/simple/CompoundAssignmentTest.java | 2 +- .../com/seaofnodes/simple/MemoryEncodingTest.java | 14 +- .../java/com/seaofnodes/simple/MergeSortTest.java | 6 +- .../java/com/seaofnodes/simple/MutabilityTest.java | 67 +++ .../test/java/com/seaofnodes/simple/TypeTest.java | 4 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 14 +- .../simple/spill/Chapter20Test-testString.smp | 8 +- .../simple/spill/Chapter21AllocTest-testString.smp | 6 +- .../simple/spill/Chapter21Test-testAntiDeps1.smp | 2 +- .../simple/spill/Chapter21Test-testInfinite.smp | 2 +- .../simple/spill/Chapter21Test-testPerson.smp | 2 +- .../spill/Chapter21Test-testStringExport.smp | 6 +- .../spill/Chapter22Test-testInfiniteReturn.smp | 2 +- .../simple/spill/Chapter22Test-testPerson.smp | 2 +- .../simple/spill/Chapter22Test-testSextFail.smp | 2 +- .../simple/spill/Chapter22Test-testSextFail2.smp | 2 +- .../simple/spill/Chapter22Test-testSextSuccess.smp | 2 +- .../simple/spill/Chapter23AllocTest-testString.smp | 6 +- .../simple/spill/Chapter23Test-testAndPtr.smp | 2 +- .../simple/spill/Chapter23Test-testFRefFields.smp | 2 +- .../simple/spill/Chapter23Test-testMethod.smp | 2 +- .../spill/Chapter23Test-testOrRhsLoopLocal.smp | 2 +- .../spill/Chapter23Test-testOrRhsLoopMemory.smp | 4 +- .../spill/Chapter24AllocTest-testBubbleSort.smp | 4 +- 57 files changed, 1575 insertions(+), 1451 deletions(-) delete mode 100644 chapter25/src/test/java/com/seaofnodes/simple/Chapter11Test.java create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/Chapter14FloatTest.java delete mode 100644 chapter25/src/test/java/com/seaofnodes/simple/Chapter17Test.java create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/Chapter17aTest.java create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/Chapter17bTest.java create mode 100644 chapter25/src/test/java/com/seaofnodes/simple/MutabilityTest.java (limited to 'chapter25') diff --git a/chapter25/Makefile b/chapter25/Makefile index 980342c8..aa7f0a17 100644 --- a/chapter25/Makefile +++ b/chapter25/Makefile @@ -71,7 +71,7 @@ include $(firstword $(wildcard ../isa/isa.mk isa/isa.mk)) test_classes := $(patsubst $(TST)/%java,$(CLZDIR)/test/%class,$(test_javas)) # These tests do not rely on the stdlib test_alone := com.seaofnodes.simple.BrainFuckTest com.seaofnodes.simple.MergeSortTest com.seaofnodes.simple.TypeTest -test_raw_nums0 := 01 02 03 04 05 06 07 08 09 10 11 12 13 14 15 16 17 18 19 20 21 +test_raw_nums0 := 01 02 03 04 05 06 07 08 09 10 12 13 14Float 14 15 16 17a 17b 18 19 20 21 test_raw_nums1 := 22 23 24 # These tests DO rely on the stdlib test_raw_sys := 25 diff --git a/chapter25/README.md b/chapter25/README.md index 3261637c..7ab7c89e 100644 --- a/chapter25/README.md +++ b/chapter25/README.md @@ -156,6 +156,10 @@ regressions. `make release` builds the compiler jar and native library artifacts `make tags` builds editor tags. Native tools and the selected CPU/ABI must match the environment; the Makefile currently defaults to x86-64/win64. +Serialized IR now uses the `C0D2` header: pointer types include an independent +read-only access bit. Older object files must be rebuilt; the reader rejects +their old header rather than interpreting their types with the new layout. + Compiler changes can invalidate both serialized IR and native code in `sys.o`. Rebuild it before interpreting linked-program test results. A source-only subset is not equivalent to this chapter's full `make tests`. diff --git a/chapter25/ROADMAP.md b/chapter25/ROADMAP.md index 981f65e3..30495a69 100644 --- a/chapter25/ROADMAP.md +++ b/chapter25/ROADMAP.md @@ -120,11 +120,11 @@ Any number of named fields are allowed: ```java struct Class { - str className; - str professor; + !str !className; + !str !professor; int time; int credits; - Class prerequisite; + !Class !prerequisite; u16 #; // Limit of 65535 students per class Student []; }; @@ -195,7 +195,7 @@ new object, only growing as needed. ```java val vec1 = new vecInt[0].add(2); // len=1, capacity=1 -val vec2 = vec1.add(3); // NEW vecInt returned, only is deleted; len=2; capacity=2; +val vec2 = vec1.add(3); // NEW !vecInt !returned, only is deleted; len=2; capacity=2; vec1[0]; // ERROR, vec1 has been freed by call to `vec1.add(3)` vec2[0]; // OK vec2[1]; // OK @@ -284,7 +284,7 @@ extra indirection with each usage. ```java struct xstr { - str !_str; // The extra indirection is here + !str !_str; // The extra indirection is here val add = { str str -> _str = str.add2(str); }; val write = { int fd -> _str.write(fd); }; }; @@ -355,7 +355,7 @@ struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; // Current Simple rules: always by-reference struct ByRef { - Complex c; // 4-byte pointer to a Complex + !Complex !c; // 4-byte pointer to a Complex }; print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c @@ -363,7 +363,7 @@ print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c // The '*' syntax indicator can be something else, e.g. a keyword "inline" // I am pronouncing '*' as "contents of" struct ByValue { - *Complex c; // c is inlined, full 16 bytes into ByValue + *!Complex !c; // c is inlined, full 16 bytes into ByValue }; print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load @@ -382,7 +382,7 @@ val *c = val.c; // Error, cannot take "contents of" a value ref.c = val.*c; // Assign into ref.c the "contents of" val.c // Arrays of inlined structures -var ary = new *Complex[99]; // Array of 99 Complex objects, inlined +var ary = new *Complex[99]; // Array of 99 !Complex !objects, inlined // Calling methods has the same syntax ref.c.len(); diff --git a/chapter25/docs/examples/BubbleSort.smp b/chapter25/docs/examples/BubbleSort.smp index 1b3b83e6..ca6906b5 100644 --- a/chapter25/docs/examples/BubbleSort.smp +++ b/chapter25/docs/examples/BubbleSort.smp @@ -4,7 +4,7 @@ // // Bubble sort, with reading (parsing) and writing (formatting) the data. -val sort = { sys.aryi64 nums -> +val sort = { !sys.aryi64 nums -> sys.aryi64?! more = nums; while( more ) { more = null; diff --git a/chapter25/docs/examples/Dijkstra.smp b/chapter25/docs/examples/Dijkstra.smp index d2f1dc4f..fd595eb5 100644 --- a/chapter25/docs/examples/Dijkstra.smp +++ b/chapter25/docs/examples/Dijkstra.smp @@ -2,7 +2,7 @@ // An implementation of // https://sampleprograms.io/projects/dijkstra/ -val shortestPath = { sys.aryi64 matrix, int nodes, int src, int dst -> +val shortestPath = { !sys.aryi64 matrix, int nodes, int src, int dst -> i64 infinity = (1 << 63)-1; var dist = new i64[nodes]; var visited = new sys.adt.bitset(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java index 19894357..42c83f93 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/Parser.java @@ -217,13 +217,17 @@ public class Parser { * Parses a function body, assuming the header is parsed. */ private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, String[] ids) { + return parseFunctionBody(sig, loc, null, ids); + } + + private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String[] ids) { // Record & restore the existing scope vars. The function parse might // update fields, so when the parse is done reset back to the pre-parse // state. Node[] preParse = _scope.save(); // Parse function body normally - ReturnNode ret = _parseFunctionBody(null, sig,loc,ids); + ReturnNode ret = _parseFunctionBody(null, sig,loc,finals,ids); // Reset all fields to pre-parse days _scope.restore(preParse); @@ -246,6 +250,10 @@ public class Parser { // Unstack the {break,continue,return} scopes. private ReturnNode _parseFunctionBody( String funName, TypeFunPtr sig, Lexer loc, String[] ids) { + return _parseFunctionBody(funName, sig, loc, null, ids); + } + + private ReturnNode _parseFunctionBody( String funName, TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String[] ids) { boolean isInit = FunNode.isInit(funName); boolean isCtor = isInit || isExplicitConstructorName(funName); String typeName = isCtor ? ((TypeMemPtr)sig._sig[0])._obj._name : null; @@ -278,7 +286,7 @@ public class Parser { for( int i=0; i tn.nullable() ? con(Type.NIL) : con(t.meet(Type.NIL)); - case TypeInteger ti -> _code.ZERO; - case TypeFloat tf -> con(TypeFloat.FZERO); + case TypeInteger ti -> xfinal ? con(Type.BOTTOM) : _code.ZERO; + case TypeFloat tf -> con(xfinal ? Type.BOTTOM : TypeFloat.FZERO); // Bottom signals type inference: they must be initialized in // the constructor and that's when we'll discover the type. case Type tt -> { assert tt==Type.BOTTOM; yield con(tt); } @@ -1177,9 +1182,9 @@ public class Parser { // Every non-null pointer without a default is constructor-required. // Without `!` it is also shallow-final; mutability and definite // initialization are independent properties. - if( t instanceof TypeNil tn && !tn.nullable() ) { + if( (xfinal && !(t instanceof TypeNil)) || (t instanceof TypeNil tn && !tn.nullable()) ) { uninit = true; - if( !hasBang ) fld_final = true; + if( xfinal ) fld_final = true; } } @@ -1430,8 +1435,10 @@ public class Parser { // Otherwise you get a type name int old1 = pos(); + boolean writable = match("!"); + boolean readonly = !writable && match("~"); String tname = _lexer.matchId(); - if( tname==null ) return null; + if( tname==null ) return posT(old1); // Convert the type name to a type. Type t0 = TYPES.get(tname), t1 = t0; @@ -1544,6 +1551,13 @@ public class Parser { if( t1 instanceof TypeStruct ts1 ) t1 = TypeMemPtr.make(ts1); + // A qualifier before the name applies to the struct reference, not + // to an enclosing array. Arrays have their own [] / [~] qualifier. + if( t1 instanceof TypeMemPtr tmp ) { + if( readonly || !writable ) t1 = tmp.makeRO(); + } else if( writable || readonly ) + return posT(old1); + // Nest arrays and '?' as needed Type t2 = t1; while( true ) { @@ -1554,7 +1568,7 @@ public class Parser { } else throw error("Type "+t0+" cannot be null"); } else if( match("[~]") ) { - t2 = TypeMemPtr.make(typeAry(t2,true)); + t2 = TypeMemPtr.make(typeAry(t2,true)).makeRO(); } else if( match("[]") ) { t2 = TypeMemPtr.make(typeAry(t2,false)); } else @@ -1566,7 +1580,7 @@ public class Parser { // Check valid forward ref, after parsing all the type extra bits. // Cannot check earlier, because cannot find required 'id' until after "[]?" syntax int old2 = pos(); - match("!"); + if( !match("!") ) match("~"); String id = _lexer.matchId(); if( !(peek(',') || peek(';') || peek('=') || match("->")) || id==null ) return posT(old1); // Reset lexer to reparse @@ -1616,9 +1630,8 @@ public class Parser { ta = TypeStruct.makeAry(tname,TypeInteger.U32,_code.alias(rcname),t,_code.alias(rcname), false ); TYPES.put(tname,ta); } - if( !efinal ) return ta; // Already have the aliases, just efinal is wrong - return TypeStruct.makeAry(tname,TypeInteger.U32,ta._fields[0]._alias,t,ta._fields[1]._alias,true ); + return TypeStruct.makeAry(tname,TypeInteger.U32,ta._fields[0]._alias,t,ta._fields[1]._alias,efinal ); } private Type implicitSelfType() { @@ -2187,7 +2200,7 @@ public class Parser { // array body. TypeMemPtr str = TypeMemPtr.make((byte)2,TypeStruct.makeAry("[]u8", slen, lenAlias, body, elemAlias, true),true); assert str.isConstant(); - return con(str); + return con(str.makeRO()); } /** @@ -2305,6 +2318,8 @@ public class Parser { Node mem = mem(); // Store to field mem.keep(); + if( expr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) + throw error("Cannot modify final field '"+name+"'"); Node st = new StoreNode(loc(), name, alias, decl, ctrl(), mem, expr.unkeep(), off.unkeep(), lift, false).peephole().keep(); storeMem(st,alias,mem); st.unkeep(); @@ -2330,6 +2345,8 @@ public class Parser { throw error( "'" + ts._name + "' is not fully initialized, field '" + fld._fname + "' needs to be set in a constructor" ); Node op = opAssign(ch,load, decl ).keep(); mem.keep(); + if( expr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) + throw error("Cannot modify final field '"+name+"'"); Node st = new StoreNode(loc(), name, alias, decl, ctrl(), mem, expr.unkeep(), off.unkeep(), op, false).peephole().keep(); storeMem(st,alias,mem); st.unkeep(); @@ -2375,6 +2392,7 @@ public class Parser { private Node func() { Ary ts = new Ary<>(Type.class); Ary ids = new Ary<>(String.class); + java.util.BitSet finals = new java.util.BitSet(); Type self = implicitSelfType(); ts.push(self); ids.push(self == TypePtr.PTR ? "#self" : "self"); @@ -2385,6 +2403,7 @@ public class Parser { while( true ) { Type t = type(); // Arg type if( t==null ) break; + finals.set(ids.size(),bindingFinal(t)); String id = requireId(); ts .push(t ); // Push type/arg pairs ids.push(id); @@ -2393,7 +2412,7 @@ public class Parser { require("->"); // Make a concrete function type, with a fidx TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),Type.BOTTOM,_code.fidx(_ref._cname)); - ReturnNode ret = parseFunctionBody(tfp,loc,ids.asAry()); + ReturnNode ret = parseFunctionBody(tfp,loc,finals,ids.asAry()); return new FunPtrNode(tfp,_code._start,ret).peephole(); } @@ -2401,6 +2420,7 @@ public class Parser { require("{"); Ary ts = new Ary<>(Type.class); Ary ids = new Ary<>(String.class); + java.util.BitSet finals = new java.util.BitSet(); TypeStruct self = _scope.constructorSelf(); assert self != null; ts.push(TypeMemPtr.make(constructorRecv(self))); @@ -2416,6 +2436,7 @@ public class Parser { while( true ) { Type t = type(); if( t==null ) break; + finals.set(ids.size(),bindingFinal(t)); String id = requireId(); ts .push(t ); ids.push(id); @@ -2424,7 +2445,7 @@ public class Parser { require("->"); TypeFunPtr tfp = TypeFunPtr.make1((byte)2,true,ts.asAry(),TypeMem.makePrivate(self),_code.fidx(_ref._cname)); Node[] preParse = _scope.save(); - ReturnNode ret = _parseFunctionBody((self._name+"."+name).intern(),tfp,loc,ids.asAry()); + ReturnNode ret = _parseFunctionBody((self._name+"."+name).intern(),tfp,loc,finals,ids.asAry()); _scope.restore(preParse); require("}"); return new FunPtrNode(tfp,_code._start,ret).peephole(); diff --git a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java index ee5c48df..a8cd315f 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/codegen/Serialize.java @@ -63,8 +63,9 @@ abstract public class Serialize { Type.TAGOFFS(); BAOS baos = new BAOS(); + // C0D2 adds independent pointer access permissions to serialized types. // A - Print a header - baos.write('C').write('0').write('D').write('E'); + baos.write('C').write('0').write('D').write('2'); // Count unique Types var types = new HashMap(); @@ -217,8 +218,8 @@ abstract public class Serialize { Type.TAGOFFS(); // A - Read a header - if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='E' ) - throw new IllegalArgumentException("Missing magic word"); + if( bais.read()!='C' || bais.read()!='0' || bais.read()!='D' || bais.read()!='2' ) + throw new IllegalArgumentException("Unsupported serialized IR format; rebuild the object file"); // B - Packed read of #strings, then strings int ndependents = bais.packed4(); // Number of dependent object files @@ -246,8 +247,8 @@ abstract public class Serialize { String[] strs = elf._strs; if( strs == null ) { // A - Read a header - if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != 'E' ) - throw new IllegalArgumentException( "Missing magic word" ); + if( bais.read() != 'C' || bais.read() != '0' || bais.read() != 'D' || bais.read() != '2' ) + throw new IllegalArgumentException( "Unsupported serialized IR format; rebuild the object file" ); // B - Packed read of #strings, then strings int ndependents = bais.packed4(); // Number of dependent object files diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index 2e921301..162f9c24 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -227,7 +227,7 @@ public class CallEndNode extends CFGNode implements MultiNode { // references here. Compare against its recursively upgraded form, // so deep mutability requirements participate before inlining. Type formal = tfp.arg(i).upgradeType(Parser.TYPES); - if( !arg._type.isa(formal) ) + if( !arg._type.isa(formal) || !arg._type.accessISA(formal) ) { addDep(arg); return false; } } return true; diff --git a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java index 84f1e705..4372e2d5 100644 --- a/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/chapter25/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -187,7 +187,7 @@ public class CallNode extends CFGNode { // Check for args for( int i=0; i