From ac525dc59de1ae195c40f8e21b09485d0e5d9330 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Sat, 24 Oct 2026 09:38:56 -0700 Subject: module split --- chapter-construction/README.ja.md | 14 +++-- chapter-construction/README.md | 63 +++++++++++++++++++--- .../main/java/com/seaofnodes/simple/Parser.java | 48 +++++++++++++++-- .../java/com/seaofnodes/simple/node/ScopeNode.java | 27 +++++++--- .../java/com/seaofnodes/simple/type/Field.java | 6 +-- .../seaofnodes/simple/FinalConstructionTest.java | 63 ++++++++++++++++++++++ 6 files changed, 196 insertions(+), 25 deletions(-) create mode 100644 chapter-construction/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java (limited to 'chapter-construction') diff --git a/chapter-construction/README.ja.md b/chapter-construction/README.ja.md index 86104de0..2fa83280 100644 --- a/chapter-construction/README.ja.md +++ b/chapter-construction/README.ja.md @@ -11,10 +11,18 @@ フィールドごとの非公開メモリを次の関数に渡します。構築が完了した時点で、 `EscapeNode` が初期化済みのフィールドを公開メモリに合流させます。 -全ての実行経路で必須フィールドが初期化されていることを確認します。 +パーサーはコンストラクタの出口で、必須フィールドが初期化されていることを確認します。 +この検査は SCCP より前なので、後の解析で安全と分かる呼び出しでも拒否する場合があります。 構築中の `self` を通常の関数に渡したり、オブジェクトに格納したりする -ことは、この章では禁止します。別名や呼び出しを通じた公開の追跡は、 -次のエスケープ解析の章で扱います。この境界は引き続き検討します。 +ことは、この章では禁止します。次のエスケープ解析の章でもこの制限は残ります。 +インライン化後に安全性を確認してヘルパー呼び出しを許す案は、まだ実装していません。 + +未完成のオブジェクトをコンストラクタ内で読むことはできますが、読むフィールドは +すでに初期化されている必要があります。他のフィールドはまだ未設定でも構いません。 +final フィールドも構築中はローカル値として再代入でき、ループでは通常の Phi を使います。 +Store はヘルパーの出口で生成します。構築後の書き換え、通常のローカル `val` への再代入、 +共有する関数宣言の置き換えは禁止します。 +詳細と提案中の規則は [英語版](README.md#helper-calls-and-final-fields-during-construction) を参照してください。 モジュール、クラスの遅延初期化、分割コンパイルはまだ導入しません。 詳しい説明、制限、実行例は [英語版](README.md) を参照してください。 diff --git a/chapter-construction/README.md b/chapter-construction/README.md index c61bd7b7..f0ea4222 100644 --- a/chapter-construction/README.md +++ b/chapter-construction/README.md @@ -75,7 +75,7 @@ including their existing integer range widening. For example: ```simple struct Counter { - int x; + val x = 0; new Counter = { int n -> while (x < n) x++; }; }; return new Counter(arg).x; @@ -86,6 +86,17 @@ performs no field Store on each trip. At the constructor exit, the compiler stores the final value into the new object. This is the result scalar replacement would give us, built directly from the construction rules. +Even final data fields can change during construction; they become final when +the constructor finishes. `x = 1; x = 2;` leaves the local value 2 for the exit +Store. In the loop above, `x++` updates a local Phi, not memory. No sequence of +final field Stores needs cleaning up inside the loop. + +A constant default does not make a field shared by every instance: a later +constructor may change it. Inferred field types therefore describe the value's +family, not just its initial constant. Ordinary local `val` bindings remain +final. Shared function declarations are also fixed; a constructor cannot replace +one of those functions. + Private memory is still useful at the helper boundaries. `NewNode` produces the pointer and its initial private memory. The hidden initializer computes defaults as local values and emits ordinary initializing Stores at exit. The @@ -109,18 +120,17 @@ initialized length are published before the array is returned. Required non-null fields have no legal zero default. Reading one before it is written is an error. - ## Publish only after completion `EscapeNode` publishes one field. It consumes control, public memory, private memory, and `self`; its result joins the field's value into the public alias. Publication has no machine instruction, but its memory edges keep initializing -Stores before later Loads and Stores. Every field is published independently, +Stores before later Loads and Stores. Every field is published independently, and scheduling may well interleave the initializing writes from many unrelated allocations and public memory updates. Before publication, every required field must be initialized on every live -path. This is rejected when `arg` can be zero: +path. This constructor is rejected: ```simple struct Box { @@ -130,10 +140,44 @@ struct Box { return new Box(arg); ``` -This is rejected because `int[] data` requires a non-null initial value, and if -`arg` is null, `data` is never set not-null. This check is based on the type -of every field at the constructor exit; if type analysis (e.g. SCCP) determines -the field is set, the code is good; if not then not. +`int[] data` requires a non-null initial value. If `n` is zero, `data` is never +set. The current parser follows explicit missing-initialization values through +the constructor's merges and checks its exit. This happens before SCCP: even +calling this constructor only with `new Box(1)` does not rescue it. Allowing +later type analysis to prove completion would require deferring this check. + + +## Helper calls and *final* fields during construction + +Constructor code may read the unfinished object, but never an uninitialized +field. Ordinary code must not observe it before construction finishes. + +We would like to allow helper calls when optimization proves they do not expose +the unfinished object. Inlining could turn a helper's field accesses into local +values. After optimization reaches a fixed point, each final field would have +a final Store: before that line, accesses use local values; after it, the field +can be read but never written. Mutable fields can still be written later. + +This is a proposed relaxation, not implemented in this snapshot. The parser +currently rejects passing `self` to an ordinary method before inlining can +prove it safe. For example, we would like this constructor to work: + +```simple +struct Vec { + int _max; + u8[~] !_buf; // Not-null, must be set before reading + + new Vec = { -> + _buf = new u8[1]; + clear(); // Would be safe after inlining; currently rejected + }; + val clear = { -> + // Keep at most 1K of storage in a cleared Vec + if( _buf# > 1024 ) _buf = new u8[1024]; + _max=0; + }; +}; +``` ## Build and check @@ -153,3 +197,6 @@ make tests CHAPTERS=chapter-construction CTAGS= defaults, completion errors, forward fields and methods, private loops, native execution, and ARM/RISC-V execution. The inherited language, memory, lattice, and backend suites run alongside it. +`FinalConstructionTest` checks repeated assignments and loops over final fields, +reads through methods, rejection of later writes, and native execution. It also +checks that the loop's field Stores are outside the loop. diff --git a/chapter-construction/src/main/java/com/seaofnodes/simple/Parser.java b/chapter-construction/src/main/java/com/seaofnodes/simple/Parser.java index 5ce7c410..dabfb6a2 100644 --- a/chapter-construction/src/main/java/com/seaofnodes/simple/Parser.java +++ b/chapter-construction/src/main/java/com/seaofnodes/simple/Parser.java @@ -267,7 +267,7 @@ public class Parser { // Pre-call the function from Start, with worse-case arguments. This // represents all the future, yet-to-be-parsed functions calls and // external calls. - _scope.push(new Kind.Func()); + _scope.push(new Kind.Func(_privateFun!=null)); ctrl(fun); // Scope control from function // Unknown callers supply whole memory; field aliases are discovered lazily. _scope.mem(new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).peephole()); @@ -768,6 +768,7 @@ public class Parser { // The alloc() call added the allocation scope !_scope.canInit(def) ) throw error("Cannot reassign final '"+name+"'"); + checkSharedField(def); // Parse assignment expression checkCaptureWrite(def); @@ -869,6 +870,14 @@ public class Parser { throw error("a not-null/non-zero expression"); t = expr._type; if( !xfinal ) t = inferredType(t); // Widen if not final + // A final field is still a local variable during construction. + // Its constant default is a value, not a one-value declaration + // type: later assignments and loop Phis may change it. + else if( _scope.inConstructor() && !(t instanceof TypeFunPtr) ) { + Type wide=inferredType(t); + t = t instanceof TypeMemPtr ptr && ptr.notNull() + ? TypeMemPtr.make((byte)2,((TypeMemPtr)wide)._obj,false).withAccess(ptr._ro) : wide; + } } // expr is a constant function if( t instanceof TypeFunPtr && expr._type instanceof TypeFunPtr tfp && tfp.isConstant() ) { @@ -948,7 +957,10 @@ public class Parser { Var v = _scope.var(index++); if( v.isFRef() ) continue; Node value = _scope.in(v); - boolean constant = v._final && v._init && value._type.isConstant(); + // Only function declarations are shared across instances. A final + // data field can change in a named or inline constructor, so a + // constant default does not justify folding every future read. + boolean constant = v._final && v._init && value._type instanceof TypeFunPtr && value._type.isConstant(); Field field = Field.make(v._name,v.type(),_code.getALIAS(),v._final,constant); shape=shape.add(field); TYPES.put(_nestedType,TypeMemPtr.make(shape)); @@ -1452,8 +1464,9 @@ public class Parser { if( name!=null ) { Var n = _scope.lookup(name); if( n != null && !(n.type() instanceof TypeMemPtr) ) { - if( n._final ) + if( n._final && !_scope.canInit(n) ) throw error("Cannot reassign final '"+n._name+"'"); + checkSharedField(n); Node expr = liftExpr(peep(new AddNode(_scope.in(n),con(delta))),n.type(),true); _scope.update(n,expr); return expr; @@ -1545,8 +1558,9 @@ public class Parser { if( ch==0 ) // Normal primary, check for postfix updates return parsePostfix(rvalue); // Assign-update direct into Scope - if( var._final ) + if( var._final && !_scope.canInit(var) ) throw error("Cannot reassign final '"+var._name+"'"); + checkSharedField(var); checkCaptureWrite(var); Node op = opAssign(ch,rvalue, var.type() ); _scope.update(var,op); @@ -1600,6 +1614,24 @@ public class Parser { throw error("Cannot assign captured variable '"+var._name+"' in an initializer"); } + // Inline constructors have local field slots too, but shared function + // declarations have no instance slot to publish. Do not silently discard + // an assignment to one of those declarations. + private void checkSharedField(Var var) { + if( !_scope.canInit(var) ) return; + if( _scope.kind(var) instanceof Kind.Define ) { + checkPrivateWrite(var._name); + return; + } + for( int i=_scope.depth()-1; i>0; i-- ) + if( _scope._kinds.at(i) instanceof Kind.Alloc alloc ) { + Field field=alloc._tmp._obj.field(var._name); + if( field!=null && field._one ) + throw error("Cannot reassign shared function '"+var._name+"'"); + return; + } + } + // Check for assign-update, "x += e0". // Returns "x + e0"; the caller assigns value. // if ch is postfix, then lhs is kept and caller will unkeep and return it. @@ -1980,6 +2012,7 @@ public class Parser { if( v.type() instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) throw error("A constructor is only called by new"); if( matchOpx('=','=') ) { + checkPrivateWrite(name); Node value=parseAsgn().keep(); checkPublication(value); _scope.update(v,liftExpr(value,v.type(),false)); @@ -1990,6 +2023,7 @@ public class Parser { throw error("Cannot read uninitialized field '"+name+"'"); char ch=_lexer.matchOperAssign(); if( ch!=0 ) { + checkPrivateWrite(name); Node op=opAssign(ch,value,v.type()); checkPublication(op); _scope.update(v,op); @@ -2000,6 +2034,12 @@ public class Parser { return parsePostfix(value); } + private void checkPrivateWrite(String name) { + Field field=((TypeMemPtr)TYPES.get(_nestedType))._obj.field(name); + if( field!=null && field._one ) + throw error("Cannot reassign shared function '"+name+"'"); + } + // zero/sign extend. "i" is limited to either classic unsigned (min==0) or // classic signed (min=minus-power-of-2); max=power-of-2-minus-1. private Node zsMask(Node val, Type t ) { diff --git a/chapter-construction/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/chapter-construction/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 3c1e9776..f65a822d 100644 --- a/chapter-construction/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/chapter-construction/src/main/java/com/seaofnodes/simple/node/ScopeNode.java @@ -39,7 +39,10 @@ public class ScopeNode extends Node { // Basic block scoping public static class Block extends Kind { } // Function scope - public static class Func extends Kind { } + public static class Func extends Kind { + public final boolean _constructor; + public Func(boolean constructor) { _constructor=constructor; } + } // Struct definition, mapping types to fields public static class Define extends Kind { public Define(TypeMemPtr tmp) { _tmp=tmp; } public final TypeMemPtr _tmp; } // Struct allocation, mapping values to fields @@ -137,15 +140,25 @@ public class ScopeNode extends Node { } - // Allocation fields live in the scope immediately outside the constructor - // block. Nested blocks retain that permission; surrounding bindings do not. + // Fields are writable local values until construction ends, even when the + // published field is final. Ordinary methods and final local variables do + // not inherit that permission. This also decides which loop Phis we need. public boolean canInit(Var v) { - for( int i=_kinds._len-1; i>0; i-- ) - if( _kinds.at(i) instanceof Kind.Alloc ) + for( int i=_kinds._len-1; i>=0; i-- ) { + Kind k=_kinds.at(i); + if( k instanceof Kind.Alloc ) return v._idx >= _kinds.at(i-1)._lexSize && v._idx < _kinds.at(i)._lexSize; + if( k instanceof Kind.Define ) return kind(v)==k; + if( k instanceof Kind.Func fun ) + return fun._constructor && i>0 && _kinds.at(i-1) instanceof Kind.Define def && kind(v)==def; + } return false; } + private boolean loopVar(Var v) { + return !v._final || (canInit(v) && !v.type().isHighOrConst()); + } + public boolean inConstructor() { return _kinds.last() instanceof Kind.Define; } public boolean inAllocation () { return _kinds.last() instanceof Kind.Alloc ; } public boolean inFunction () { return _kinds.last() instanceof Kind.Func ; } @@ -294,7 +307,7 @@ public class ScopeNode extends Node { // Memory is one binding, with the same lazy loop Phi as scalar names. for( int i=1; i FREE = new Ary<>(Field.class); diff --git a/chapter-construction/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java b/chapter-construction/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java new file mode 100644 index 00000000..e91dc384 --- /dev/null +++ b/chapter-construction/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java @@ -0,0 +1,63 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.simple.node.StoreNode; +import org.junit.Test; +import static org.junit.Assert.*; + +public class FinalConstructionTest { + private static final String LOOP = """ + val step={int x -> x*2+1;}; + struct C { + val x=1; + new C={int n -> + x=0; x=1; + for(int i=0; ix;}; + }; + return new C(arg).get(); + """; + + @Test public void testFinalConstructorLocals() throws java.io.IOException { + var code=new CodeGen(LOOP).driver(CodeGen.Phase.LocalSched); + assertEquals("1",Eval2.eval(code,0)); + assertEquals("15",Eval2.eval(code,3)); + assertEquals("63",Eval2.eval(code,5)); + code._stop.walk(n -> { + if( n instanceof StoreNode st && st._name.equals("x") ) + assertEquals("Final field writes belong after the loop",0,st.cfg0().loopDepth()); + return null; + }); + String[] sources={ + "struct C { val x=1; new C={->x=1; x=2;}; }; return new C().x;", + "struct C { int ~x; new C={int n -> self.x=1; for(int i=0;i for(int i=0;ix=2.5;}; }; return new C().x;", + "struct C { val x=\"a\"; new C={int n -> for(int i=0;ix=new int[2]; x=new int[3];}; }; return new C().x#;" + }; + String[] results={"2","8","4","2.5","98","3"}; + for( int i=0; ival x=1; x=2;}; }; return new C();", + "struct C { val f={->1;}; new C={->f={->2;};}; }; return new C().f();" + }; + for( String src : rejected ) { + try { new CodeGen(src).driver(CodeGen.Phase.TypeCheck); fail(src); } + catch( Parser.ParseException e ) { assertTrue(e.getMessage(),e.getMessage().startsWith("Cannot")); } + } + + var dir=java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("finalConstruction.smp"),"val buildFinal={int arg ->"+LOOP+"};"); + java.nio.file.Files.writeString(dir.resolve("finalConstruction.c"),""" + extern long long buildFinal(long long); + int main(void) { return buildFinal(0)!=1 || buildFinal(3)!=15 || buildFinal(5)!=63; } + """); + TestC.run("build/objs","finalConstruction","",-1); + } +} -- cgit v1.2.3