diff options
| author | Cliff Click <cliffc@acm.org> | 2026-08-10 11:11:18 -0700 |
|---|---|---|
| committer | Cliff Click <cliffc@acm.org> | 2026-10-25 10:24:58 -0700 |
| commit | afb9714e9668c12cdd5559d78b38665175f99e9c (patch) | |
| tree | de10c282f4c0c610761d231659b099daaa87e277 | |
| parent | 4d89ad19e0d660aa1c4ff076e0ca44807d989077 (diff) | |
| download | Simple-afb9714e9668c12cdd5559d78b38665175f99e9c.tar.gz Simple-afb9714e9668c12cdd5559d78b38665175f99e9c.zip | |
Chapter 26: Construction and Private Memory
Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com>
Co-authored-by: Symious <14933944+symious@users.noreply.github.com>
Co-authored-by: Jun Kawasaki <jun784@gmail.com>
Co-authored-by: Claude Opus 5 <noreply@anthropic.com>
57 files changed, 3205 insertions, 247 deletions
diff --git a/README.ja.md b/README.ja.md index bd16eb1a..eb67c878 100644 --- a/README.ja.md +++ b/README.ja.md @@ -64,7 +64,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第24a章](docs/chapter24a/README.ja.md)：関数内の SCCP * [第24b章](docs/chapter24b/README.ja.md)：関数間の SCCP * [第25章](docs/chapter25/README.ja.md)：型が決まる前の SSA -* 第26章：構築とプライベートメモリ +* [第26章](docs/chapter26/README.ja.md)：構築とプライベートメモリ * 第27章：エスケープ解析と未知の呼び出し元 * 第28a章：モジュールと遅延クラス初期化 * 第28b章：分離コンパイル @@ -73,7 +73,7 @@ The Simple language is styled after a subset of C or Java. * [Chapter 24a](docs/chapter24a/README.md): SCCP Within a Function * [Chapter 24b](docs/chapter24b/README.md): SCCP Across Functions * [Chapter 25](docs/chapter25/README.md): SSA Before Types Are Known -* Chapter 26: Construction and Private Memory +* [Chapter 26](docs/chapter26/README.md): Construction and Private Memory * Chapter 27: Escape Analysis and Unknown Callers * Chapter 28a: Modules and Lazy Class Initialization * Chapter 28b: Separate Compilation diff --git a/chapter25.iml b/chapter26.iml index fc9e2e3d..6d87ad07 100644 --- a/chapter25.iml +++ b/chapter26.iml @@ -1,8 +1,8 @@ <?xml version="1.0" encoding="UTF-8"?> <module type="JAVA_MODULE" version="4"> <component name="NewModuleRootManager" inherit-compiler-output="false"> - <output url="file://$MODULE_DIR$/../build/idea/production/chapter25" /> - <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter25" /> + <output url="file://$MODULE_DIR$/../build/idea/production/chapter26" /> + <output-test url="file://$MODULE_DIR$/../build/idea/test/chapter26" /> <exclude-output /> <content url="file://$MODULE_DIR$"> <sourceFolder url="file://$MODULE_DIR$/src/main/java" isTestSource="false" /> diff --git a/docs/chapter26/24-grammar.ja.md b/docs/chapter26/24-grammar.ja.md new file mode 100644 index 00000000..fd3fa232 --- /dev/null +++ b/docs/chapter26/24-grammar.ja.md @@ -0,0 +1,168 @@ +# 第24章の文法 + +[English](24-grammar.md) | 日本語 + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : methodDeclaration | statement ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// The general declaration rule also admits explicitly typed function fields. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol. Ordinary strings elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : equalityExpression (('&' | '|' | '^') equalityExpression)* + ; + +equalityExpression : comparisonExpression (('==' | '!=') comparisonExpression)* ; + +// Chained comparisons test adjacent operands and short-circuit. A chain must +// keep its direction; equality has lower precedence and does not join a chain. +comparisonExpression + : shiftExpression + ( (('<' | '<=') shiftExpression)+ | (('>' | '>=') shiftExpression)+ )? + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter26/24-grammar.md b/docs/chapter26/24-grammar.md new file mode 100644 index 00000000..22867355 --- /dev/null +++ b/docs/chapter26/24-grammar.md @@ -0,0 +1,168 @@ +# Grammar for Chapter 24 + +English | [日本語](24-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : methodDeclaration | statement ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// The general declaration rule also admits explicitly typed function fields. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol. Ordinary strings elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : equalityExpression (('&' | '|' | '^') equalityExpression)* + ; + +equalityExpression : comparisonExpression (('==' | '!=') comparisonExpression)* ; + +// Chained comparisons test adjacent operands and short-circuit. A chain must +// keep its direction; equality has lower precedence and does not join a chain. +comparisonExpression + : shiftExpression + ( (('<' | '<=') shiftExpression)+ | (('>' | '>=') shiftExpression)+ )? + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter26/Makefile b/docs/chapter26/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter26/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter26/README.ja.md b/docs/chapter26/README.ja.md new file mode 100644 index 00000000..3318ebfd --- /dev/null +++ b/docs/chapter26/README.ja.md @@ -0,0 +1,30 @@ +# 第26章: オブジェクトの構築と非公開メモリ + +[English](README.md) | 日本語 + +[Previous: Chapter 25](../chapter25/README.ja.md) | +[Next: Chapter 27](../chapter27/README.ja.md) + +この章では、フィールドの初期化とコンストラクタを関数として扱います。 +構築中のフィールドはローカルな SSA 値として扱い、分岐やループでは +通常の Phi で合流させます。各初期化関数の出口で通常の Store を生成し、 +フィールドごとの非公開メモリを次の関数に渡します。構築が完了した時点で、 +`EscapeNode` が初期化済みのフィールドを公開メモリに合流させます。 + +パーサーはコンストラクタの出口で、必須フィールドが初期化されていることを確認します。 +この検査は SCCP より前なので、後の解析で安全と分かる呼び出しでも拒否する場合があります。 +構築中の `self` を通常の関数に渡したり、オブジェクトに格納したりする +ことは、この章では禁止します。次のエスケープ解析の章でもこの制限は残ります。 +インライン化後に安全性を確認してヘルパー呼び出しを許す案は、まだ実装していません。 + +未完成のオブジェクトをコンストラクタ内で読むことはできますが、読むフィールドは +すでに初期化されている必要があります。他のフィールドはまだ未設定でも構いません。 +final フィールドも構築中はローカル値として再代入でき、ループでは通常の Phi を使います。 +Store はヘルパーの出口で生成します。構築後の書き換え、通常のローカル `val` への再代入、 +共有する関数宣言の置き換えは禁止します。 +詳細と提案中の規則は [英語版](README.md#helper-calls-and-final-fields-during-construction) を参照してください。 + +モジュール、クラスの遅延初期化、分割コンパイルはまだ導入しません。 +詳しい説明、制限、実行例は [英語版](README.md) を参照してください。 + +このディレクトリで `make lib tests CTAGS=` を実行できます。 diff --git a/docs/chapter26/README.md b/docs/chapter26/README.md new file mode 100644 index 00000000..e4f7310a --- /dev/null +++ b/docs/chapter26/README.md @@ -0,0 +1,202 @@ +# Chapter 26: Construction and Private Memory + +English | [日本語](README.ja.md) + +[Previous: Chapter 25](../chapter25/README.md) | +[Next: Chapter 27](../chapter27/README.md) + + +The previous chapter built SSA before it knew all the types. This chapter uses +that freedom to move object initialization into functions. The new problem is +memory: a constructor must remember what it has written to this object without +mixing those values with every older object of the same type. + +We keep the object private while it is built, then publish its initialized +fields to public memory. No partially-built instance can ever escape (unlike +some languages where the `this` object can escape before final fields are +actually set and final). Finding all the ways an object can escape comes next. + + +## Constructors are calls + +```simple +struct Box { + int x = 7; + int[] data; + new Box = { int n -> + data = new int[2]; + x = n; + data[0] = x + 1; + }; + val get = { -> x + data[0]; }; +}; +val a = new Box(arg); +val b = new Box(arg + 10); +return a.get() * 100 + b.get(); +``` + +For `arg == 2`, this returns `525`. Each call allocates its own `Box` and array. +The declaration `new Box = { ... };` supplies the constructor body. The body +still parses as an anonymous function; `new` marks its role as a constructor. +The expression `new Box(...)` allocates an object and calls it. A constructor +returns *private memory*, not a source-level value. + +The parser creates two helpers for each struct: + +* `Box.<init>` runs the field initializers, in declaration order. +* `Box.<new>` allocates the object, calls `<init>`, calls the user constructor + if there is one, publishes the fields, and returns the pointer. + +The initializer and user constructor receive hidden `self` and `#selfMem` +arguments. *Public* memory still travels through input 1 of calls and returns; +the *private* memory is a separate argument and result. A constructor can allocate +a public array or update an already public object without losing its own field state. + +The old `new Box { ... }` syntax remains an inline construction block. It runs +the field initializers, then its block, then publishes; it does not also call +the named user constructor. Ordinary methods still use public memory. + + +## Fields are local values during construction + +Public memory describes all objects with a given field alias. A public Store +therefore combines the new value with values already in that alias. +E.g. writing `a.x = 3` cannot prove that `b.x` is also 3, so the general `.x` +field alias is usually some form of `BOTTOM`. + +During construction we already know which object each field belongs to, and +the language prevents its partial state from becoming visible. The parser can +therefore keep its fields as local SSA values. Both `x` and `self.x` refer to +the same local slot, although an argument named `x` can shadow the bare name. +An assignment updates that slot; it does not emit a Store. + +Branches merge the values with ordinary Phis. Loops use ordinary loop Phis, +including their existing integer range widening. For example: + +```simple +struct Counter { + val x = 0; + new Counter = { int n -> while (x < n) x++; }; +}; +return new Counter(arg).x; +``` + +The constructor loop carries the value of `x`. It needs no memory Phi and +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 +user constructor loads those fields into local slots, computes their final +values, and emits its own exit Stores. Each Store produces one precise alias; +`MemMergeNode` packages the slices for the helper result. `TypeMem` records the +field values across the call, without joining them with older objects. + +```text +New -> <init>: local defaults -> field Stores + -> constructor: local values and Phis -> field Stores + -> publication -> public field aliases +``` + +Constructor signatures are bound at their declarations. Their bodies are +parsed after the struct's field list closes, so even a later-declared field +has a local slot before a branch or loop is built. + +Arrays use the same publication boundary: zero-filled elements and an +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, +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 constructor is rejected: + +```simple +struct Box { + int[] data; + new Box = { int n -> if (n) data = new int[2]; }; +}; +return new Box(arg); +``` + +`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 + +From this directory: + +```bash +make lib tests CTAGS= +``` + +Or from the repository root: + +```bash +make tests CHAPTERS=chapter26 CTAGS= +``` + +`ConstructionTest` exercises constructor calls, independent instances, dynamic +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/docs/chapter26/examples/A_helloWorld.smp b/docs/chapter26/examples/A_helloWorld.smp new file mode 100644 index 00000000..07ff935f --- /dev/null +++ b/docs/chapter26/examples/A_helloWorld.smp @@ -0,0 +1,3 @@ +// -*- mode: java; -*- +sys.io.p("Hello, World!"); +return 0; diff --git a/docs/chapter26/examples/BubbleSort.smp b/docs/chapter26/examples/BubbleSort.smp new file mode 100644 index 00000000..938e3181 --- /dev/null +++ b/docs/chapter26/examples/BubbleSort.smp @@ -0,0 +1,37 @@ +// -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + +val sort = { !sys.aryi64 nums -> + var done = false; + while( !done ) { + done = true; + for( var i = 0; i < nums.len-1; i++ ) + if( nums.buf[i] > nums.buf[i+1] ) { + int tmp = nums.buf[i]; + nums.buf[i] = nums.buf[i+1]; + nums.buf[i+1] = tmp; // Swap + done = false; + } + } +}; + +// Read from stdin a line of the form "[ 4, 3, 2, 1]" and print it sorted. +val main = { -> + // Parse array of numbers from stdin + var nums = sys.parseAryI64( sys.io.stdin() ); + if( !nums ) { + sys.io.p("stdin must look like [4, 3, 2, 1]"); + return 1; + } + + // Bubble sort array of integers + sort(nums); + + // Print a list of numbers to stdout + nums.str().write(1); + return 0; +}; diff --git a/docs/chapter26/font-awesome-4.7.0.zip b/docs/chapter26/font-awesome-4.7.0.zip Binary files differnew file mode 100644 index 00000000..b6bdb4bd --- /dev/null +++ b/docs/chapter26/font-awesome-4.7.0.zip diff --git a/docs/chapter26/ifg_trim.pdf b/docs/chapter26/ifg_trim.pdf Binary files differnew file mode 100644 index 00000000..d952fd4f --- /dev/null +++ b/docs/chapter26/ifg_trim.pdf diff --git a/docs/chapter26/lattice.gv b/docs/chapter26/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter26/lattice.gv @@ -0,0 +1,203 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=circle, style=filled]; + nodesep=0.2; + ranksep=0.2; + + TOP [label=<<B>⊤</B >>, fillcolor=black, fontcolor=white]; + BOT [label=<<B>⊥</B>>, fillcolor=black, fontcolor=white]; + + // ---------------------- + // Control + XCTRL [label=<<B>⊤</B >:ctrl>, fillcolor=yellow, shape=oval]; + CTRL [label=<<B>⊥</B>:ctrl>, fillcolor=yellow, shape=oval]; + + TOP -> XCTRL; + XCTRL -> CTRL; + CTRL -> BOT; + + // ---------------------- + // Integers + INT_TOP [label=<<B>⊤</B >:int>, fillcolor=lightblue, shape=oval]; + INT_BOT [label=<<B>⊥</B>:int>, fillcolor=lightblue, shape=oval]; + + INT_HI [label="[min>max]" , fillcolor=lightblue, shape=oval]; + INT_XBOOL [label="[1...0]", fillcolor=lightblue, shape=oval]; + INT_CON [label="constants", fillcolor=lightblue, shape=oval]; + INT_CON0 [label="0", fillcolor=lightblue]; + INT_CON1 [label="1", fillcolor=lightblue]; + INT_BOOL [label="[0...1]", fillcolor=lightblue,shape=oval]; + INT_LO [label="[min<max]" , fillcolor=lightblue, shape=oval]; + + TOP -> INT_TOP; + INT_TOP -> INT_HI; + INT_HI -> INT_XBOOL; + INT_XBOOL -> INT_CON0; + INT_XBOOL -> INT_CON1; + INT_HI -> INT_CON; + INT_CON0 -> INT_BOOL; + INT_CON1 -> INT_BOOL; + INT_BOOL -> INT_LO; + INT_CON -> INT_LO; + INT_LO -> INT_BOT; + INT_BOT -> BOT; + + INT_CON0 -> INT_CON1 -> INT_CON [style=invis]; + + // ---------------------- + // Floats + FLT_TOP [label=<<B>⊤</B >:flt>, fillcolor=aqua, shape=oval]; + FLT_BOT [label=<<B>⊥</B>:flt>, fillcolor=aqua, shape=oval]; + + FLT_CON64 [label="64b consts\n[excludes\n32b consts]" , fillcolor=aqua, shape=oval]; + FLT_CON32 [label="32b consts", fillcolor=aqua, shape=oval]; + FLT_CONPI [label="3.14159...", fillcolor=aqua, shape=oval]; + FLT_X32 [label="~f32", fillcolor=aqua]; + FLT_CON0 [label="0." , fillcolor=aqua]; + FLT_32 [label="f32" , fillcolor=aqua]; + + TOP -> FLT_TOP; + FLT_TOP -> FLT_CON64 + FLT_TOP -> FLT_CONPI + FLT_CON64 -> FLT_BOT + FLT_CONPI -> FLT_BOT + + FLT_TOP -> FLT_X32; + FLT_X32 -> FLT_CON0; + FLT_X32 -> FLT_CON32; + FLT_CON0 -> FLT_32; + FLT_CON32 -> FLT_32; + FLT_32 -> FLT_BOT + + FLT_BOT -> BOT; + + FLT_CON0 -> FLT_CON32 -> FLT_CONPI -> FLT_CON64 [style=invis]; + + + // ---------------------- + // Pointers, just a boolean nil/not and a struct + PTR [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="green"><FONT color="white">*ptr</FONT></TD></TR> + <TR><TD BGCOLOR="lightgreen">struct</TD></TR> + </TABLE> + >]; + PTR0 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="green"><FONT color="white">*ptr?</FONT></TD></TR> + <TR><TD BGCOLOR="lightgreen">struct</TD></TR> + </TABLE> + >]; + + TOP -> PTR; + PTR -> PTR0; + PTR0 -> BOT; + + // ---------------------- + // Structs + STRUCT_TOP [label=<<B>⊤</B >:struct>, fillcolor=lightgreen, shape=oval]; + STRUCT_BOT [label=<<B>⊥</B>:struct>, fillcolor=lightgreen, shape=oval]; + + STRUCT_S1 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + </TABLE> + >]; + STRUCT_S2 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + </TABLE> + >]; + STRUCT_SN [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + <TR><TD BGCOLOR="lightgreen">... </TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + <TR><TD BGCOLOR="lightgreen">field</TD><TD BGCOLOR="lightblue:green" gradientangle="315">int/ptr</TD></TR> + </TABLE> + >]; + + + TOP -> STRUCT_TOP; + STRUCT_TOP -> STRUCT_S1; + STRUCT_TOP -> STRUCT_S2; + STRUCT_TOP -> STRUCT_SN; + STRUCT_S1 -> STRUCT_BOT; + STRUCT_S2 -> STRUCT_BOT; + STRUCT_SN -> STRUCT_BOT; + STRUCT_BOT -> BOT; + + STRUCT_S1 -> STRUCT_S2 -> STRUCT_SN [style=invis]; + + // ---------------------- + // Memory + MEM_TOP [label=<<B>⊤</B >:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_BOT [label=<<B>⊥</B>:mem>, fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIAS1 [label="#1" , fillcolor=blue, fontcolor=white]; + MEM_ALIASDOTS [label="..." , fillcolor=blue, fontcolor=white, shape=oval]; + MEM_ALIASN [label="#n" , fillcolor=blue, fontcolor=white]; + + TOP -> MEM_TOP; + MEM_TOP -> MEM_ALIAS1; + MEM_TOP -> MEM_ALIASDOTS; + MEM_TOP -> MEM_ALIASN; + MEM_ALIAS1 -> MEM_BOT; + MEM_ALIASDOTS -> MEM_BOT; + MEM_ALIASN -> MEM_BOT; + MEM_BOT -> BOT; + + MEM_ALIAS1 -> MEM_ALIASDOTS -> MEM_ALIASN [style=invis]; + + // ---------------------- + // Tuples + + TUPLE_TOP [label=<<B>⊤</B >:tuple>, fillcolor=pink, shape=oval]; + TUPLE_BOT [label=<<B>⊥</B>:tuple>, fillcolor=pink, shape=oval]; + + TUPLE1 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">Tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLE2 [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">Tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + TUPLEN [shape=none, fillcolor=none, label=< + <TABLE BORDER="0" CELLBORDER="1" CELLSPACING="0"> + <TH><TD BGCOLOR="pink">Tuple</TD></TH> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">...</FONT></TD></TR> + <TR><TD BGCOLOR="black" ><FONT color="white">type</FONT></TD></TR> + </TABLE> + >]; + + + TOP -> TUPLE_TOP; + TUPLE_TOP -> TUPLE1; + TUPLE_TOP -> TUPLE2; + TUPLE_TOP -> TUPLEN; + TUPLE1 -> TUPLE_BOT; + TUPLE2 -> TUPLE_BOT; + TUPLEN -> TUPLE_BOT; + TUPLE_BOT -> BOT; + + // ---------------------- + // Additional customization + {rank=same; TOP;} + {rank=same; INT_TOP; FLT_TOP; XCTRL; PTR; STRUCT_TOP; MEM_TOP; TUPLE_TOP} + {rank=same; INT_CON; INT_CON0; INT_CON1; + FLT_CON32; FLT_CON64; FLT_CON0; FLT_CONPI; + STRUCT_S1; STRUCT_S2; STRUCT_SN; + MEM_ALIAS1; MEM_ALIASDOTS; MEM_ALIASN; + TUPLE1; TUPLE2; TUPLEN; + } + {rank=same; INT_BOT; FLT_BOT; CTRL; PTR0; STRUCT_BOT; MEM_BOT; TUPLE_BOT} + {rank=same; BOT;} +} diff --git a/docs/chapter26/lattice.svg b/docs/chapter26/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/chapter26/lattice.svg @@ -0,0 +1,691 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 12.2.0 (20241103.1931) + --> +<!-- Title: Lattice Pages: 1 --> +<svg width="1330pt" height="584pt" + viewBox="0.00 0.00 1329.51 583.54" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 579.54)"> +<title>Lattice</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-579.54 1325.51,-579.54 1325.51,4 -4,4"/> +<!-- TOP --> +<g id="node1" class="node"> +<title>TOP</title> +<ellipse fill="black" stroke="black" cx="641.51" cy="-554.42" rx="21.12" ry="21.12"/> +<text text-anchor="start" x="633.63" y="-549.99" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text> +</g> +<!-- XCTRL --> +<g id="node3" class="node"> +<title>XCTRL</title> +<ellipse fill="yellow" stroke="black" cx="36.51" cy="-492.79" rx="36.51" ry="18"/> +<text text-anchor="start" x="17.76" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text> +<text text-anchor="start" x="33.51" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text> +</g> +<!-- TOP->XCTRL --> +<g id="edge1" class="edge"> +<title>TOP->XCTRL</title> +<path fill="none" stroke="black" d="M620.33,-551.33C533.82,-542.8 206.01,-510.5 83.28,-498.4"/> +<polygon fill="black" stroke="black" points="83.86,-494.94 73.56,-497.44 83.17,-501.91 83.86,-494.94"/> +</g> +<!-- INT_TOP --> +<g id="node5" class="node"> +<title>INT_TOP</title> +<ellipse fill="lightblue" stroke="black" cx="316.51" cy="-492.79" rx="33.95" ry="18"/> +<text text-anchor="start" x="299.63" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text> +<text text-anchor="start" x="315.38" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:int</text> +</g> +<!-- TOP->INT_TOP --> +<g id="edge4" class="edge"> +<title>TOP->INT_TOP</title> +<path fill="none" stroke="black" d="M620.68,-549.6C568.33,-539.99 430.36,-514.68 359.64,-501.71"/> +<polygon fill="black" stroke="black" points="360.44,-498.29 349.97,-499.93 359.18,-505.18 360.44,-498.29"/> +</g> +<!-- FLT_TOP --> +<g id="node14" class="node"> +<title>FLT_TOP</title> +<ellipse fill="aqua" stroke="black" cx="494.51" cy="-492.79" rx="32.41" ry="18"/> +<text text-anchor="start" x="478.76" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text> +<text text-anchor="start" x="494.51" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:flt</text> +</g> +<!-- TOP->FLT_TOP --> +<g id="edge18" class="edge"> +<title>TOP->FLT_TOP</title> +<path fill="none" stroke="black" d="M621.99,-545.5C598.79,-536.09 559.6,-520.19 530.78,-508.5"/> +<polygon fill="black" stroke="black" points="532.29,-505.34 521.7,-504.82 529.65,-511.82 532.29,-505.34"/> +</g> +<!-- PTR --> +<g id="node22" class="node"> +<title>PTR</title> +<polygon fill="none" stroke="none" points="668.51,-519.29 614.51,-519.29 614.51,-466.29 668.51,-466.29 668.51,-519.29"/> +<polygon fill="green" stroke="none" points="623.51,-492.79 623.51,-515.29 659.51,-515.29 659.51,-492.79 623.51,-492.79"/> +<polygon fill="none" stroke="black" points="623.51,-492.79 623.51,-515.29 659.51,-515.29 659.51,-492.79 623.51,-492.79"/> +<text text-anchor="start" x="630.63" y="-498.99" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr</text> +<polygon fill="lightgreen" stroke="none" points="623.51,-470.29 623.51,-492.79 659.51,-492.79 659.51,-470.29 623.51,-470.29"/> +<polygon fill="none" stroke="black" points="623.51,-470.29 623.51,-492.79 659.51,-492.79 659.51,-470.29 623.51,-470.29"/> +<text text-anchor="start" x="626.51" y="-476.49" font-family="Times New Roman,serif" font-size="14.00">struct</text> +</g> +<!-- TOP->PTR --> +<g id="edge33" class="edge"> +<title>TOP->PTR</title> +<path fill="none" stroke="black" d="M641.51,-532.9C641.51,-532.06 641.51,-531.22 641.51,-530.37"/> +<polygon fill="black" stroke="black" points="645.01,-530.61 641.51,-520.61 638.01,-530.61 645.01,-530.61"/> +</g> +<!-- STRUCT_TOP --> +<g id="node24" class="node"> +<title>STRUCT_TOP</title> +<ellipse fill="lightgreen" stroke="black" cx="746.51" cy="-492.79" rx="44.7" ry="18"/> +<text text-anchor="start" x="721.76" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text> +<text text-anchor="start" x="737.51" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:struct</text> +</g> +<!-- TOP->STRUCT_TOP --> +<g id="edge36" class="edge"> +<title>TOP->STRUCT_TOP</title> +<path fill="none" stroke="black" d="M659.8,-543.03C674.04,-534.94 694.24,-523.47 711.55,-513.64"/> +<polygon fill="black" stroke="black" points="713.07,-516.81 720.03,-508.83 709.61,-510.72 713.07,-516.81"/> +</g> +<!-- MEM_TOP --> +<g id="node29" class="node"> +<title>MEM_TOP</title> +<ellipse fill="blue" stroke="black" cx="998.51" cy="-492.79" rx="43.67" ry="18"/> +<text text-anchor="start" x="974.51" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊤</text> +<text text-anchor="start" x="990.26" y="-488.74" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text> +</g> +<!-- TOP->MEM_TOP --> +<g id="edge46" class="edge"> +<title>TOP->MEM_TOP</title> +<path fill="none" stroke="black" d="M662.51,-549.91C717.64,-540.7 867.72,-515.64 947.33,-502.34"/> +<polygon fill="black" stroke="black" points="947.77,-505.82 957.06,-500.72 946.62,-498.91 947.77,-505.82"/> +</g> +<!-- TUPLE_TOP --> +<g id="node34" class="node"> +<title>TUPLE_TOP</title> +<ellipse fill="pink" stroke="black" cx="1182.51" cy="-492.79" rx="42.65" ry="18"/> +<text text-anchor="start" x="1159.26" y="-488.74" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊤</text> +<text text-anchor="start" x="1175.01" y="-488.74" font-family="Times New Roman,serif" font-size="14.00">:tuple</text> +</g> +<!-- TOP->TUPLE_TOP --> +<g id="edge56" class="edge"> +<title>TOP->TUPLE_TOP</title> +<path fill="none" stroke="black" d="M662.72,-551.08C740.91,-542.46 1014.51,-512.31 1130.21,-499.56"/> +<polygon fill="black" stroke="black" points="1130.5,-503.05 1140.05,-498.47 1129.73,-496.09 1130.5,-503.05"/> +</g> +<!-- BOT --> +<g id="node2" class="node"> +<title>BOT</title> +<ellipse fill="black" stroke="black" cx="641.51" cy="-21.12" rx="21.12" ry="21.12"/> +<text text-anchor="start" x="633.63" y="-16.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text> +</g> +<!-- CTRL --> +<g id="node4" class="node"> +<title>CTRL</title> +<ellipse fill="yellow" stroke="black" cx="49.51" cy="-82.75" rx="36.51" ry="18"/> +<text text-anchor="start" x="30.76" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text> +<text text-anchor="start" x="46.51" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:ctrl</text> +</g> +<!-- XCTRL->CTRL --> +<g id="edge2" class="edge"> +<title>XCTRL->CTRL</title> +<path fill="none" stroke="black" d="M37.09,-474.38C39.15,-409.6 46.05,-191.88 48.57,-112.25"/> +<polygon fill="black" stroke="black" points="52.06,-112.73 48.88,-102.63 45.06,-112.51 52.06,-112.73"/> +</g> +<!-- CTRL->BOT --> +<g id="edge3" class="edge"> +<title>CTRL->BOT</title> +<path fill="none" stroke="black" d="M85.21,-78.15C191.74,-67.42 506.36,-35.74 608.84,-25.41"/> +<polygon fill="black" stroke="black" points="609.15,-28.9 618.75,-24.42 608.45,-21.94 609.15,-28.9"/> +</g> +<!-- INT_HI --> +<g id="node7" class="node"> +<title>INT_HI</title> +<ellipse fill="lightblue" stroke="black" cx="174.51" cy="-434.29" rx="53.91" ry="18"/> +<text text-anchor="middle" x="174.51" y="-429.24" font-family="Times New Roman,serif" font-size="14.00">[min>max]</text> +</g> +<!-- INT_TOP->INT_HI --> +<g id="edge5" class="edge"> +<title>INT_TOP->INT_HI</title> +<path fill="none" stroke="black" d="M289.8,-481.17C269.89,-473.25 242.26,-462.25 219.03,-453.01"/> +<polygon fill="black" stroke="black" points="220.37,-449.77 209.78,-449.33 217.78,-456.28 220.37,-449.77"/> +</g> +<!-- INT_BOT --> +<g id="node6" class="node"> +<title>INT_BOT</title> +<ellipse fill="lightblue" stroke="black" cx="329.51" cy="-82.75" rx="33.95" ry="18"/> +<text text-anchor="start" x="312.63" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text> +<text text-anchor="start" x="328.38" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:int</text> +</g> +<!-- INT_BOT->BOT --> +<g id="edge15" class="edge"> +<title>INT_BOT->BOT</title> +<path fill="none" stroke="black" d="M361.14,-75.7C420.84,-64.3 549.47,-39.71 609.47,-28.25"/> +<polygon fill="black" stroke="black" points="609.86,-31.73 619.03,-26.42 608.55,-24.86 609.86,-31.73"/> +</g> +<!-- INT_XBOOL --> +<g id="node8" class="node"> +<title>INT_XBOOL</title> +<ellipse fill="lightblue" stroke="black" cx="97.51" cy="-373.97" rx="33.95" ry="18"/> +<text text-anchor="middle" x="97.51" y="-368.92" font-family="Times New Roman,serif" font-size="14.00">[1...0]</text> +</g> +<!-- INT_HI->INT_XBOOL --> +<g id="edge6" class="edge"> +<title>INT_HI->INT_XBOOL</title> +<path fill="none" stroke="black" d="M153.47,-417.36C144.79,-410.78 134.6,-403.06 125.31,-396.03"/> +<polygon fill="black" stroke="black" points="127.71,-393.46 117.63,-390.21 123.48,-399.04 127.71,-393.46"/> +</g> +<!-- INT_CON --> +<g id="node9" class="node"> +<title>INT_CON</title> +<ellipse fill="lightblue" stroke="black" cx="174.51" cy="-282.65" rx="45.21" ry="18"/> +<text text-anchor="middle" x="174.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">constants</text> +</g> +<!-- INT_HI->INT_CON --> +<g id="edge9" class="edge"> +<title>INT_HI->INT_CON</title> +<path fill="none" stroke="black" d="M174.51,-416C174.51,-390.27 174.51,-343.1 174.51,-312.31"/> +<polygon fill="black" stroke="black" points="178.01,-312.52 174.51,-302.52 171.01,-312.52 178.01,-312.52"/> +</g> +<!-- INT_CON0 --> +<g id="node10" class="node"> +<title>INT_CON0</title> +<ellipse fill="lightblue" stroke="black" cx="47.51" cy="-282.65" rx="18" ry="18"/> +<text text-anchor="middle" x="47.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">0</text> +</g> +<!-- INT_XBOOL->INT_CON0 --> +<g id="edge7" class="edge"> +<title>INT_XBOOL->INT_CON0</title> +<path fill="none" stroke="black" d="M88.34,-356.59C80.82,-343.17 70.07,-323.96 61.49,-308.62"/> +<polygon fill="black" stroke="black" points="64.63,-307.08 56.69,-300.06 58.53,-310.5 64.63,-307.08"/> +</g> +<!-- INT_CON1 --> +<g id="node11" class="node"> +<title>INT_CON1</title> +<ellipse fill="lightblue" stroke="black" cx="97.51" cy="-282.65" rx="18" ry="18"/> +<text text-anchor="middle" x="97.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">1</text> +</g> +<!-- INT_XBOOL->INT_CON1 --> +<g id="edge8" class="edge"> +<title>INT_XBOOL->INT_CON1</title> +<path fill="none" stroke="black" d="M97.51,-355.75C97.51,-343.47 97.51,-326.68 97.51,-312.39"/> +<polygon fill="black" stroke="black" points="101.01,-312.64 97.51,-302.64 94.01,-312.64 101.01,-312.64"/> +</g> +<!-- INT_LO --> +<g id="node13" class="node"> +<title>INT_LO</title> +<ellipse fill="lightblue" stroke="black" cx="174.51" cy="-141.25" rx="53.91" ry="18"/> +<text text-anchor="middle" x="174.51" y="-136.2" font-family="Times New Roman,serif" font-size="14.00">[min<max]</text> +</g> +<!-- INT_CON->INT_LO --> +<g id="edge13" class="edge"> +<title>INT_CON->INT_LO</title> +<path fill="none" stroke="black" d="M174.51,-264.17C174.51,-240.45 174.51,-199.04 174.51,-170.9"/> +<polygon fill="black" stroke="black" points="178.01,-171.25 174.51,-161.25 171.01,-171.25 178.01,-171.25"/> +</g> +<!-- INT_CON0->INT_CON1 --> +<!-- INT_BOOL --> +<g id="node12" class="node"> +<title>INT_BOOL</title> +<ellipse fill="lightblue" stroke="black" cx="97.51" cy="-196.45" rx="33.95" ry="18"/> +<text text-anchor="middle" x="97.51" y="-191.4" font-family="Times New Roman,serif" font-size="14.00">[0...1]</text> +</g> +<!-- INT_CON0->INT_BOOL --> +<g id="edge10" class="edge"> +<title>INT_CON0->INT_BOOL</title> +<path fill="none" stroke="black" d="M56.45,-266.6C63.5,-254.72 73.51,-237.87 81.88,-223.77"/> +<polygon fill="black" stroke="black" points="84.75,-225.79 86.85,-215.41 78.73,-222.22 84.75,-225.79"/> +</g> +<!-- INT_CON1->INT_CON --> +<!-- INT_CON1->INT_BOOL --> +<g id="edge11" class="edge"> +<title>INT_CON1->INT_BOOL</title> +<path fill="none" stroke="black" d="M97.51,-264.21C97.51,-253.25 97.51,-238.87 97.51,-226.25"/> +<polygon fill="black" stroke="black" points="101.01,-226.39 97.51,-216.39 94.01,-226.39 101.01,-226.39"/> +</g> +<!-- INT_BOOL->INT_LO --> +<g id="edge12" class="edge"> +<title>INT_BOOL->INT_LO</title> +<path fill="none" stroke="black" d="M117.34,-181.75C124.98,-176.47 133.91,-170.3 142.42,-164.42"/> +<polygon fill="black" stroke="black" points="144.27,-167.4 150.5,-158.83 140.29,-161.64 144.27,-167.4"/> +</g> +<!-- INT_LO->INT_BOT --> +<g id="edge14" class="edge"> +<title>INT_LO->INT_BOT</title> +<path fill="none" stroke="black" d="M210.07,-127.29C234.52,-118.37 266.93,-106.56 291.82,-97.49"/> +<polygon fill="black" stroke="black" points="292.71,-100.89 300.91,-94.17 290.31,-94.31 292.71,-100.89"/> +</g> +<!-- FLT_CON64 --> +<g id="node16" class="node"> +<title>FLT_CON64</title> +<ellipse fill="aqua" stroke="black" cx="564.51" cy="-282.65" rx="55.33" ry="40.66"/> +<text text-anchor="middle" x="564.51" y="-294.1" font-family="Times New Roman,serif" font-size="14.00">64b consts</text> +<text text-anchor="middle" x="564.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">[excludes</text> +<text text-anchor="middle" x="564.51" y="-261.1" font-family="Times New Roman,serif" font-size="14.00">32b consts]</text> +</g> +<!-- FLT_TOP->FLT_CON64 --> +<g id="edge19" class="edge"> +<title>FLT_TOP->FLT_CON64</title> +<path fill="none" stroke="black" d="M500.48,-474.88C510.8,-443.88 532.35,-379.2 547.59,-333.44"/> +<polygon fill="black" stroke="black" points="550.9,-334.57 550.74,-323.98 544.26,-332.36 550.9,-334.57"/> +</g> +<!-- FLT_CONPI --> +<g id="node18" class="node"> +<title>FLT_CONPI</title> +<ellipse fill="aqua" stroke="black" cx="446.51" cy="-282.65" rx="48.79" ry="18"/> +<text text-anchor="middle" x="446.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">3.14159...</text> +</g> +<!-- FLT_TOP->FLT_CONPI --> +<g id="edge20" class="edge"> +<title>FLT_TOP->FLT_CONPI</title> +<path fill="none" stroke="black" d="M490.33,-474.51C482.02,-438.11 463.32,-356.27 453.25,-312.16"/> +<polygon fill="black" stroke="black" points="456.69,-311.49 451.05,-302.52 449.86,-313.04 456.69,-311.49"/> +</g> +<!-- FLT_X32 --> +<g id="node19" class="node"> +<title>FLT_X32</title> +<ellipse fill="aqua" stroke="black" cx="333.51" cy="-373.97" rx="28.32" ry="28.32"/> +<text text-anchor="middle" x="333.51" y="-368.92" font-family="Times New Roman,serif" font-size="14.00">~f32</text> +</g> +<!-- FLT_TOP->FLT_X32 --> +<g id="edge23" class="edge"> +<title>FLT_TOP->FLT_X32</title> +<path fill="none" stroke="black" d="M474.77,-478.22C447.56,-458.14 398.22,-421.73 365.65,-397.69"/> +<polygon fill="black" stroke="black" points="367.88,-394.99 357.75,-391.86 363.72,-400.62 367.88,-394.99"/> +</g> +<!-- FLT_BOT --> +<g id="node15" class="node"> +<title>FLT_BOT</title> +<ellipse fill="aqua" stroke="black" cx="507.51" cy="-82.75" rx="32.41" ry="18"/> +<text text-anchor="start" x="491.76" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text> +<text text-anchor="start" x="507.51" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:flt</text> +</g> +<!-- FLT_BOT->BOT --> +<g id="edge29" class="edge"> +<title>FLT_BOT->BOT</title> +<path fill="none" stroke="black" d="M532.4,-70.67C554.98,-60.63 588.29,-45.81 612.16,-35.19"/> +<polygon fill="black" stroke="black" points="613.29,-38.51 621,-31.25 610.44,-32.12 613.29,-38.51"/> +</g> +<!-- FLT_CON64->FLT_BOT --> +<g id="edge21" class="edge"> +<title>FLT_CON64->FLT_BOT</title> +<path fill="none" stroke="black" d="M553.11,-242.68C542.05,-203.88 525.53,-145.95 515.71,-111.5"/> +<polygon fill="black" stroke="black" points="519.17,-110.89 513.06,-102.23 512.44,-112.81 519.17,-110.89"/> +</g> +<!-- FLT_CON32 --> +<g id="node17" class="node"> +<title>FLT_CON32</title> +<ellipse fill="aqua" stroke="black" cx="333.51" cy="-282.65" rx="50.33" ry="18"/> +<text text-anchor="middle" x="333.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">32b consts</text> +</g> +<!-- FLT_CON32->FLT_CONPI --> +<!-- FLT_32 --> +<g id="node21" class="node"> +<title>FLT_32</title> +<ellipse fill="aqua" stroke="black" cx="333.51" cy="-196.45" rx="23.2" ry="23.2"/> +<text text-anchor="middle" x="333.51" y="-191.4" font-family="Times New Roman,serif" font-size="14.00">f32</text> +</g> +<!-- FLT_CON32->FLT_32 --> +<g id="edge27" class="edge"> +<title>FLT_CON32->FLT_32</title> +<path fill="none" stroke="black" d="M333.51,-264.21C333.51,-254.7 333.51,-242.59 333.51,-231.31"/> +<polygon fill="black" stroke="black" points="337.01,-231.51 333.51,-221.51 330.01,-231.51 337.01,-231.51"/> +</g> +<!-- FLT_CONPI->FLT_BOT --> +<g id="edge22" class="edge"> +<title>FLT_CONPI->FLT_BOT</title> +<path fill="none" stroke="black" d="M452.03,-264.56C462.62,-229.86 485.86,-153.69 498.65,-111.79"/> +<polygon fill="black" stroke="black" points="501.94,-112.98 501.51,-102.39 495.25,-110.93 501.94,-112.98"/> +</g> +<!-- FLT_CONPI->FLT_CON64 --> +<!-- FLT_X32->FLT_CON32 --> +<g id="edge25" class="edge"> +<title>FLT_X32->FLT_CON32</title> +<path fill="none" stroke="black" d="M333.51,-345.2C333.51,-334.71 333.51,-322.76 333.51,-312.19"/> +<polygon fill="black" stroke="black" points="337.01,-312.52 333.51,-302.52 330.01,-312.53 337.01,-312.52"/> +</g> +<!-- FLT_CON0 --> +<g id="node20" class="node"> +<title>FLT_CON0</title> +<ellipse fill="aqua" stroke="black" cx="251.51" cy="-282.65" rx="18.08" ry="18.08"/> +<text text-anchor="middle" x="251.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">0.</text> +</g> +<!-- FLT_X32->FLT_CON0 --> +<g id="edge24" class="edge"> +<title>FLT_X32->FLT_CON0</title> +<path fill="none" stroke="black" d="M314.9,-352.7C301.83,-338.47 284.38,-319.46 271.1,-304.99"/> +<polygon fill="black" stroke="black" points="273.81,-302.77 264.47,-297.77 268.65,-307.5 273.81,-302.77"/> +</g> +<!-- FLT_CON0->FLT_CON32 --> +<!-- FLT_CON0->FLT_32 --> +<g id="edge26" class="edge"> +<title>FLT_CON0->FLT_32</title> +<path fill="none" stroke="black" d="M263.96,-268.86C276.06,-256.44 294.74,-237.26 309.69,-221.91"/> +<polygon fill="black" stroke="black" points="312.03,-224.53 316.5,-214.92 307.01,-219.64 312.03,-224.53"/> +</g> +<!-- FLT_32->FLT_BOT --> +<g id="edge28" class="edge"> +<title>FLT_32->FLT_BOT</title> +<path fill="none" stroke="black" d="M353.13,-183.63C383.19,-163.99 440.9,-126.28 476.61,-102.94"/> +<polygon fill="black" stroke="black" points="478.34,-105.99 484.79,-97.59 474.51,-100.13 478.34,-105.99"/> +</g> +<!-- PTR0 --> +<g id="node23" class="node"> +<title>PTR0</title> +<polygon fill="none" stroke="none" points="668.51,-109.25 614.51,-109.25 614.51,-56.25 668.51,-56.25 668.51,-109.25"/> +<polygon fill="green" stroke="none" points="623.51,-82.75 623.51,-105.25 659.51,-105.25 659.51,-82.75 623.51,-82.75"/> +<polygon fill="none" stroke="black" points="623.51,-82.75 623.51,-105.25 659.51,-105.25 659.51,-82.75 623.51,-82.75"/> +<text text-anchor="start" x="627.63" y="-88.95" font-family="Times New Roman,serif" font-size="14.00" fill="white">*ptr?</text> +<polygon fill="lightgreen" stroke="none" points="623.51,-60.25 623.51,-82.75 659.51,-82.75 659.51,-60.25 623.51,-60.25"/> +<polygon fill="none" stroke="black" points="623.51,-60.25 623.51,-82.75 659.51,-82.75 659.51,-60.25 623.51,-60.25"/> +<text text-anchor="start" x="626.51" y="-66.45" font-family="Times New Roman,serif" font-size="14.00">struct</text> +</g> +<!-- PTR->PTR0 --> +<g id="edge34" class="edge"> +<title>PTR->PTR0</title> +<path fill="none" stroke="black" d="M641.51,-466.52C641.51,-396.01 641.51,-202.44 641.51,-120.34"/> +<polygon fill="black" stroke="black" points="645.01,-120.58 641.51,-110.58 638.01,-120.58 645.01,-120.58"/> +</g> +<!-- PTR0->BOT --> +<g id="edge35" class="edge"> +<title>PTR0->BOT</title> +<path fill="none" stroke="black" d="M641.51,-56.46C641.51,-55.58 641.51,-54.7 641.51,-53.81"/> +<polygon fill="black" stroke="black" points="645.01,-53.9 641.51,-43.9 638.01,-53.9 645.01,-53.9"/> +</g> +<!-- STRUCT_S1 --> +<g id="node26" class="node"> +<title>STRUCT_S1</title> +<polygon fill="none" stroke="none" points="741.38,-300.65 663.63,-300.65 663.63,-264.65 741.38,-264.65 741.38,-300.65"/> +<polygon fill="lightgreen" stroke="none" points="671.63,-273.4 671.63,-291.9 698.38,-291.9 698.38,-273.4 671.63,-273.4"/> +<polygon fill="none" stroke="black" points="671.63,-273.4 671.63,-291.9 698.38,-291.9 698.38,-273.4 671.63,-273.4"/> +<text text-anchor="start" x="672.63" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">field</text> +<defs> +<linearGradient id="l_0" gradientUnits="userSpaceOnUse" x1="703.51" y1="-289.19" x2="728.26" y2="-276.11" > +<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/> +<stop offset="1" style="stop-color:green;stop-opacity:1.;"/> +</linearGradient> +</defs> +<polygon fill="url(#l_0)" stroke="none" points="698.38,-273.4 698.38,-291.9 733.38,-291.9 733.38,-273.4 698.38,-273.4"/> +<polygon fill="none" stroke="black" points="698.38,-273.4 698.38,-291.9 733.38,-291.9 733.38,-273.4 698.38,-273.4"/> +<text text-anchor="start" x="699.38" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text> +</g> +<!-- STRUCT_TOP->STRUCT_S1 --> +<g id="edge37" class="edge"> +<title>STRUCT_TOP->STRUCT_S1</title> +<path fill="none" stroke="black" d="M742.68,-474.51C735.02,-437.92 717.75,-355.45 708.55,-311.5"/> +<polygon fill="black" stroke="black" points="712.02,-311 706.54,-301.93 705.17,-312.43 712.02,-311"/> +</g> +<!-- STRUCT_S2 --> +<g id="node27" class="node"> +<title>STRUCT_S2</title> +<polygon fill="none" stroke="none" points="841.38,-309.15 755.63,-309.15 755.63,-256.15 841.38,-256.15 841.38,-309.15"/> +<polygon fill="lightgreen" stroke="none" points="763.63,-282.65 763.63,-305.15 794.38,-305.15 794.38,-282.65 763.63,-282.65"/> +<polygon fill="none" stroke="black" points="763.63,-282.65 763.63,-305.15 794.38,-305.15 794.38,-282.65 763.63,-282.65"/> +<text text-anchor="start" x="766.63" y="-288.85" font-family="Times New Roman,serif" font-size="14.00">field</text> +<defs> +<linearGradient id="l_1" gradientUnits="userSpaceOnUse" x1="800.1" y1="-301.86" x2="827.67" y2="-285.95" > +<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/> +<stop offset="1" style="stop-color:green;stop-opacity:1.;"/> +</linearGradient> +</defs> +<polygon fill="url(#l_1)" stroke="none" points="794.38,-282.65 794.38,-305.15 833.38,-305.15 833.38,-282.65 794.38,-282.65"/> +<polygon fill="none" stroke="black" points="794.38,-282.65 794.38,-305.15 833.38,-305.15 833.38,-282.65 794.38,-282.65"/> +<text text-anchor="start" x="797.38" y="-288.85" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text> +<polygon fill="lightgreen" stroke="none" points="763.63,-260.15 763.63,-282.65 794.38,-282.65 794.38,-260.15 763.63,-260.15"/> +<polygon fill="none" stroke="black" points="763.63,-260.15 763.63,-282.65 794.38,-282.65 794.38,-260.15 763.63,-260.15"/> +<text text-anchor="start" x="766.63" y="-266.35" font-family="Times New Roman,serif" font-size="14.00">field</text> +<defs> +<linearGradient id="l_2" gradientUnits="userSpaceOnUse" x1="800.1" y1="-279.36" x2="827.67" y2="-263.45" > +<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/> +<stop offset="1" style="stop-color:green;stop-opacity:1.;"/> +</linearGradient> +</defs> +<polygon fill="url(#l_2)" stroke="none" points="794.38,-260.15 794.38,-282.65 833.38,-282.65 833.38,-260.15 794.38,-260.15"/> +<polygon fill="none" stroke="black" points="794.38,-260.15 794.38,-282.65 833.38,-282.65 833.38,-260.15 794.38,-260.15"/> +<text text-anchor="start" x="797.38" y="-266.35" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text> +</g> +<!-- STRUCT_TOP->STRUCT_S2 --> +<g id="edge38" class="edge"> +<title>STRUCT_TOP->STRUCT_S2</title> +<path fill="none" stroke="black" d="M751.03,-474.51C759.53,-440.16 778.05,-365.34 789.28,-319.95"/> +<polygon fill="black" stroke="black" points="792.67,-320.83 791.67,-310.28 785.87,-319.15 792.67,-320.83"/> +</g> +<!-- STRUCT_SN --> +<g id="node28" class="node"> +<title>STRUCT_SN</title> +<polygon fill="none" stroke="none" points="941.38,-320.4 855.63,-320.4 855.63,-244.9 941.38,-244.9 941.38,-320.4"/> +<polygon fill="lightgreen" stroke="none" points="863.63,-293.9 863.63,-316.4 894.38,-316.4 894.38,-293.9 863.63,-293.9"/> +<polygon fill="none" stroke="black" points="863.63,-293.9 863.63,-316.4 894.38,-316.4 894.38,-293.9 863.63,-293.9"/> +<text text-anchor="start" x="866.63" y="-300.1" font-family="Times New Roman,serif" font-size="14.00">field</text> +<defs> +<linearGradient id="l_3" gradientUnits="userSpaceOnUse" x1="900.1" y1="-313.11" x2="927.67" y2="-297.2" > +<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/> +<stop offset="1" style="stop-color:green;stop-opacity:1.;"/> +</linearGradient> +</defs> +<polygon fill="url(#l_3)" stroke="none" points="894.38,-293.9 894.38,-316.4 933.38,-316.4 933.38,-293.9 894.38,-293.9"/> +<polygon fill="none" stroke="black" points="894.38,-293.9 894.38,-316.4 933.38,-316.4 933.38,-293.9 894.38,-293.9"/> +<text text-anchor="start" x="897.38" y="-300.1" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text> +<polygon fill="lightgreen" stroke="none" points="863.63,-271.4 863.63,-293.9 894.38,-293.9 894.38,-271.4 863.63,-271.4"/> +<polygon fill="none" stroke="black" points="863.63,-271.4 863.63,-293.9 894.38,-293.9 894.38,-271.4 863.63,-271.4"/> +<text text-anchor="start" x="869.63" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">...  </text> +<defs> +<linearGradient id="l_4" gradientUnits="userSpaceOnUse" x1="900.1" y1="-290.61" x2="927.67" y2="-274.7" > +<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/> +<stop offset="1" style="stop-color:green;stop-opacity:1.;"/> +</linearGradient> +</defs> +<polygon fill="url(#l_4)" stroke="none" points="894.38,-271.4 894.38,-293.9 933.38,-293.9 933.38,-271.4 894.38,-271.4"/> +<polygon fill="none" stroke="black" points="894.38,-271.4 894.38,-293.9 933.38,-293.9 933.38,-271.4 894.38,-271.4"/> +<text text-anchor="start" x="897.38" y="-277.6" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text> +<polygon fill="lightgreen" stroke="none" points="863.63,-248.9 863.63,-271.4 894.38,-271.4 894.38,-248.9 863.63,-248.9"/> +<polygon fill="none" stroke="black" points="863.63,-248.9 863.63,-271.4 894.38,-271.4 894.38,-248.9 863.63,-248.9"/> +<text text-anchor="start" x="866.63" y="-255.1" font-family="Times New Roman,serif" font-size="14.00">field</text> +<defs> +<linearGradient id="l_5" gradientUnits="userSpaceOnUse" x1="900.1" y1="-268.11" x2="927.67" y2="-252.2" > +<stop offset="0" style="stop-color:lightblue;stop-opacity:1.;"/> +<stop offset="1" style="stop-color:green;stop-opacity:1.;"/> +</linearGradient> +</defs> +<polygon fill="url(#l_5)" stroke="none" points="894.38,-248.9 894.38,-271.4 933.38,-271.4 933.38,-248.9 894.38,-248.9"/> +<polygon fill="none" stroke="black" points="894.38,-248.9 894.38,-271.4 933.38,-271.4 933.38,-248.9 894.38,-248.9"/> +<text text-anchor="start" x="897.38" y="-255.1" font-family="Times New Roman,serif" font-size="14.00">int/ptr</text> +</g> +<!-- STRUCT_TOP->STRUCT_SN --> +<g id="edge39" class="edge"> +<title>STRUCT_TOP->STRUCT_SN</title> +<path fill="none" stroke="black" d="M759.21,-475.24C782.17,-443.49 831.3,-375.56 864.63,-329.48"/> +<polygon fill="black" stroke="black" points="867.37,-331.67 870.4,-321.52 861.7,-327.57 867.37,-331.67"/> +</g> +<!-- STRUCT_BOT --> +<g id="node25" class="node"> +<title>STRUCT_BOT</title> +<ellipse fill="lightgreen" stroke="black" cx="751.51" cy="-82.75" rx="44.7" ry="18"/> +<text text-anchor="start" x="726.76" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text> +<text text-anchor="start" x="742.51" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:struct</text> +</g> +<!-- STRUCT_BOT->BOT --> +<g id="edge43" class="edge"> +<title>STRUCT_BOT->BOT</title> +<path fill="none" stroke="black" d="M725.72,-67.77C709,-58.7 687.2,-46.89 669.97,-37.55"/> +<polygon fill="black" stroke="black" points="671.71,-34.51 661.25,-32.82 668.37,-40.67 671.71,-34.51"/> +</g> +<!-- STRUCT_S1->STRUCT_BOT --> +<g id="edge40" class="edge"> +<title>STRUCT_S1->STRUCT_BOT</title> +<path fill="none" stroke="black" d="M706.86,-264.91C715.3,-230.49 733.97,-154.31 744.29,-112.19"/> +<polygon fill="black" stroke="black" points="747.69,-113.04 746.67,-102.5 740.89,-111.37 747.69,-113.04"/> +</g> +<!-- STRUCT_S1->STRUCT_S2 --> +<!-- STRUCT_S2->STRUCT_BOT --> +<g id="edge41" class="edge"> +<title>STRUCT_S2->STRUCT_BOT</title> +<path fill="none" stroke="black" d="M792.36,-256.52C783.62,-219.3 767.61,-151.25 758.45,-112.26"/> +<polygon fill="black" stroke="black" points="761.88,-111.57 756.18,-102.64 755.07,-113.17 761.88,-111.57"/> +</g> +<!-- STRUCT_S2->STRUCT_SN --> +<!-- STRUCT_SN->STRUCT_BOT --> +<g id="edge42" class="edge"> +<title>STRUCT_SN->STRUCT_BOT</title> +<path fill="none" stroke="black" d="M870.86,-245.05C841.74,-205.46 796.64,-144.13 771.03,-109.3"/> +<polygon fill="black" stroke="black" points="773.99,-107.42 765.25,-101.44 768.36,-111.57 773.99,-107.42"/> +</g> +<!-- MEM_ALIAS1 --> +<g id="node31" class="node"> +<title>MEM_ALIAS1</title> +<ellipse fill="blue" stroke="black" cx="975.51" cy="-282.65" rx="20.13" ry="20.13"/> +<text text-anchor="middle" x="975.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">#1</text> +</g> +<!-- MEM_TOP->MEM_ALIAS1 --> +<g id="edge47" class="edge"> +<title>MEM_TOP->MEM_ALIAS1</title> +<path fill="none" stroke="black" d="M996.51,-474.51C992.58,-438.66 983.84,-358.73 978.96,-314.18"/> +<polygon fill="black" stroke="black" points="982.45,-313.94 977.89,-304.38 975.5,-314.7 982.45,-313.94"/> +</g> +<!-- MEM_ALIASDOTS --> +<g id="node32" class="node"> +<title>MEM_ALIASDOTS</title> +<ellipse fill="blue" stroke="black" cx="1036.51" cy="-282.65" rx="27" ry="18"/> +<text text-anchor="middle" x="1036.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text> +</g> +<!-- MEM_TOP->MEM_ALIASDOTS --> +<g id="edge48" class="edge"> +<title>MEM_TOP->MEM_ALIASDOTS</title> +<path fill="none" stroke="black" d="M1001.81,-474.51C1008.41,-438.02 1023.27,-355.86 1031.23,-311.83"/> +<polygon fill="black" stroke="black" points="1034.63,-312.69 1032.97,-302.23 1027.74,-311.45 1034.63,-312.69"/> +</g> +<!-- MEM_ALIASN --> +<g id="node33" class="node"> +<title>MEM_ALIASN</title> +<ellipse fill="blue" stroke="black" cx="1097.51" cy="-282.65" rx="20.13" ry="20.13"/> +<text text-anchor="middle" x="1097.51" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">#n</text> +</g> +<!-- MEM_TOP->MEM_ALIASN --> +<g id="edge49" class="edge"> +<title>MEM_TOP->MEM_ALIASN</title> +<path fill="none" stroke="black" d="M1006.95,-474.88C1024.11,-438.46 1063.18,-355.52 1083.95,-311.44"/> +<polygon fill="black" stroke="black" points="1087.07,-313.03 1088.16,-302.49 1080.73,-310.05 1087.07,-313.03"/> +</g> +<!-- MEM_BOT --> +<g id="node30" class="node"> +<title>MEM_BOT</title> +<ellipse fill="blue" stroke="black" cx="998.51" cy="-82.75" rx="43.67" ry="18"/> +<text text-anchor="start" x="974.51" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00" fill="white">⊥</text> +<text text-anchor="start" x="990.26" y="-78.7" font-family="Times New Roman,serif" font-size="14.00" fill="white">:mem</text> +</g> +<!-- MEM_BOT->BOT --> +<g id="edge53" class="edge"> +<title>MEM_BOT->BOT</title> +<path fill="none" stroke="black" d="M958.6,-75.08C887.17,-63.15 738.86,-38.38 673.56,-27.48"/> +<polygon fill="black" stroke="black" points="674.3,-24.05 663.86,-25.86 673.15,-30.96 674.3,-24.05"/> +</g> +<!-- MEM_ALIAS1->MEM_BOT --> +<g id="edge50" class="edge"> +<title>MEM_ALIAS1->MEM_BOT</title> +<path fill="none" stroke="black" d="M977.84,-262.38C981.92,-226.96 990.35,-153.62 995.09,-112.45"/> +<polygon fill="black" stroke="black" points="998.57,-112.87 996.23,-102.53 991.61,-112.07 998.57,-112.87"/> +</g> +<!-- MEM_ALIAS1->MEM_ALIASDOTS --> +<!-- MEM_ALIASDOTS->MEM_BOT --> +<g id="edge51" class="edge"> +<title>MEM_ALIASDOTS->MEM_BOT</title> +<path fill="none" stroke="black" d="M1033.07,-264.56C1026.49,-229.93 1012.06,-154.01 1004.08,-112.06"/> +<polygon fill="black" stroke="black" points="1007.56,-111.6 1002.25,-102.43 1000.68,-112.91 1007.56,-111.6"/> +</g> +<!-- MEM_ALIASDOTS->MEM_ALIASN --> +<!-- MEM_ALIASN->MEM_BOT --> +<g id="edge52" class="edge"> +<title>MEM_ALIASN->MEM_BOT</title> +<path fill="none" stroke="black" d="M1088.37,-264.2C1070.97,-229.07 1032.98,-152.35 1012.41,-110.82"/> +<polygon fill="black" stroke="black" points="1015.58,-109.34 1008.01,-101.93 1009.31,-112.45 1015.58,-109.34"/> +</g> +<!-- TUPLE1 --> +<g id="node36" class="node"> +<title>TUPLE1</title> +<polygon fill="none" stroke="none" points="1185.51,-309.15 1131.51,-309.15 1131.51,-256.15 1185.51,-256.15 1185.51,-309.15"/> +<polygon fill="pink" stroke="none" points="1139.76,-282.65 1139.76,-305.15 1177.26,-305.15 1177.26,-282.65 1139.76,-282.65"/> +<polygon fill="none" stroke="black" points="1139.76,-282.65 1139.76,-305.15 1177.26,-305.15 1177.26,-282.65 1139.76,-282.65"/> +<text text-anchor="start" x="1142.76" y="-288.85" font-family="Times New Roman,serif" font-size="14.00">Tuple</text> +<polygon fill="black" stroke="none" points="1139.76,-260.15 1139.76,-282.65 1177.26,-282.65 1177.26,-260.15 1139.76,-260.15"/> +<polygon fill="none" stroke="black" points="1139.76,-260.15 1139.76,-282.65 1177.26,-282.65 1177.26,-260.15 1139.76,-260.15"/> +<text text-anchor="start" x="1146.88" y="-266.35" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLE1 --> +<g id="edge57" class="edge"> +<title>TUPLE_TOP->TUPLE1</title> +<path fill="none" stroke="black" d="M1180.42,-474.51C1176.51,-440.23 1167.99,-365.66 1162.8,-320.24"/> +<polygon fill="black" stroke="black" points="1166.28,-319.86 1161.67,-310.32 1159.33,-320.65 1166.28,-319.86"/> +</g> +<!-- TUPLE2 --> +<g id="node37" class="node"> +<title>TUPLE2</title> +<polygon fill="none" stroke="none" points="1253.51,-320.4 1199.51,-320.4 1199.51,-244.9 1253.51,-244.9 1253.51,-320.4"/> +<polygon fill="pink" stroke="none" points="1207.76,-293.9 1207.76,-316.4 1245.26,-316.4 1245.26,-293.9 1207.76,-293.9"/> +<polygon fill="none" stroke="black" points="1207.76,-293.9 1207.76,-316.4 1245.26,-316.4 1245.26,-293.9 1207.76,-293.9"/> +<text text-anchor="start" x="1210.76" y="-300.1" font-family="Times New Roman,serif" font-size="14.00">Tuple</text> +<polygon fill="black" stroke="none" points="1207.76,-271.4 1207.76,-293.9 1245.26,-293.9 1245.26,-271.4 1207.76,-271.4"/> +<polygon fill="none" stroke="black" points="1207.76,-271.4 1207.76,-293.9 1245.26,-293.9 1245.26,-271.4 1207.76,-271.4"/> +<text text-anchor="start" x="1214.88" y="-277.6" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text> +<polygon fill="black" stroke="none" points="1207.76,-248.9 1207.76,-271.4 1245.26,-271.4 1245.26,-248.9 1207.76,-248.9"/> +<polygon fill="none" stroke="black" points="1207.76,-248.9 1207.76,-271.4 1245.26,-271.4 1245.26,-248.9 1207.76,-248.9"/> +<text text-anchor="start" x="1214.88" y="-255.1" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLE2 --> +<g id="edge58" class="edge"> +<title>TUPLE_TOP->TUPLE2</title> +<path fill="none" stroke="black" d="M1186.34,-474.51C1192.95,-442.94 1206.72,-377.19 1216.28,-331.51"/> +<polygon fill="black" stroke="black" points="1219.68,-332.35 1218.3,-321.85 1212.83,-330.92 1219.68,-332.35"/> +</g> +<!-- TUPLEN --> +<g id="node38" class="node"> +<title>TUPLEN</title> +<polygon fill="none" stroke="none" points="1321.51,-331.65 1267.51,-331.65 1267.51,-233.65 1321.51,-233.65 1321.51,-331.65"/> +<polygon fill="pink" stroke="none" points="1275.76,-305.15 1275.76,-327.65 1313.26,-327.65 1313.26,-305.15 1275.76,-305.15"/> +<polygon fill="none" stroke="black" points="1275.76,-305.15 1275.76,-327.65 1313.26,-327.65 1313.26,-305.15 1275.76,-305.15"/> +<text text-anchor="start" x="1278.76" y="-311.35" font-family="Times New Roman,serif" font-size="14.00">Tuple</text> +<polygon fill="black" stroke="none" points="1275.76,-282.65 1275.76,-305.15 1313.26,-305.15 1313.26,-282.65 1275.76,-282.65"/> +<polygon fill="none" stroke="black" points="1275.76,-282.65 1275.76,-305.15 1313.26,-305.15 1313.26,-282.65 1275.76,-282.65"/> +<text text-anchor="start" x="1282.88" y="-288.85" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text> +<polygon fill="black" stroke="none" points="1275.76,-260.15 1275.76,-282.65 1313.26,-282.65 1313.26,-260.15 1275.76,-260.15"/> +<polygon fill="none" stroke="black" points="1275.76,-260.15 1275.76,-282.65 1313.26,-282.65 1313.26,-260.15 1275.76,-260.15"/> +<text text-anchor="start" x="1288.88" y="-266.35" font-family="Times New Roman,serif" font-size="14.00" fill="white">...</text> +<polygon fill="black" stroke="none" points="1275.76,-237.65 1275.76,-260.15 1313.26,-260.15 1313.26,-237.65 1275.76,-237.65"/> +<polygon fill="none" stroke="black" points="1275.76,-237.65 1275.76,-260.15 1313.26,-260.15 1313.26,-237.65 1275.76,-237.65"/> +<text text-anchor="start" x="1282.88" y="-243.85" font-family="Times New Roman,serif" font-size="14.00" fill="white">type</text> +</g> +<!-- TUPLE_TOP->TUPLEN --> +<g id="edge59" class="edge"> +<title>TUPLE_TOP->TUPLEN</title> +<path fill="none" stroke="black" d="M1192.06,-474.88C1207.65,-445.62 1239.24,-386.36 1263.24,-341.32"/> +<polygon fill="black" stroke="black" points="1266.22,-343.18 1267.83,-332.71 1260.04,-339.88 1266.22,-343.18"/> +</g> +<!-- TUPLE_BOT --> +<g id="node35" class="node"> +<title>TUPLE_BOT</title> +<ellipse fill="pink" stroke="black" cx="1192.51" cy="-82.75" rx="42.65" ry="18"/> +<text text-anchor="start" x="1169.26" y="-78.7" font-family="Times New Roman,serif" font-weight="bold" font-size="14.00">⊥</text> +<text text-anchor="start" x="1185.01" y="-78.7" font-family="Times New Roman,serif" font-size="14.00">:tuple</text> +</g> +<!-- TUPLE_BOT->BOT --> +<g id="edge63" class="edge"> +<title>TUPLE_BOT->BOT</title> +<path fill="none" stroke="black" d="M1151.54,-77.32C1046.53,-65.95 769.32,-35.95 674.14,-25.65"/> +<polygon fill="black" stroke="black" points="674.52,-22.18 664.2,-24.58 673.77,-29.14 674.52,-22.18"/> +</g> +<!-- TUPLE1->TUPLE_BOT --> +<g id="edge60" class="edge"> +<title>TUPLE1->TUPLE_BOT</title> +<path fill="none" stroke="black" d="M1162.95,-256.52C1169.28,-219.3 1180.86,-151.25 1187.49,-112.26"/> +<polygon fill="black" stroke="black" points="1190.9,-113.1 1189.12,-102.66 1184,-111.93 1190.9,-113.1"/> +</g> +<!-- TUPLE2->TUPLE_BOT --> +<g id="edge61" class="edge"> +<title>TUPLE2->TUPLE_BOT</title> +<path fill="none" stroke="black" d="M1220.11,-245.05C1213.55,-206.44 1203.46,-147.16 1197.47,-111.94"/> +<polygon fill="black" stroke="black" points="1200.99,-111.74 1195.86,-102.47 1194.09,-112.92 1200.99,-111.74"/> +</g> +<!-- TUPLEN->TUPLE_BOT --> +<g id="edge62" class="edge"> +<title>TUPLEN->TUPLE_BOT</title> +<path fill="none" stroke="black" d="M1269.56,-233.75C1249.85,-195.12 1223.04,-142.58 1206.8,-110.75"/> +<polygon fill="black" stroke="black" points="1210.07,-109.46 1202.41,-102.15 1203.83,-112.65 1210.07,-109.46"/> +</g> +</g> +</svg> diff --git a/docs/chapter26/lattice2.gv b/docs/chapter26/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter26/lattice2.gv @@ -0,0 +1,85 @@ +digraph Lattice { + compound = true; + // Define nodes + splines=false; + node [shape=oval, style=filled]; + nodesep=0.2; + ranksep=0.4; + + TOP [label="~scalar\n+int+tmp+0", fillcolor=black, fontcolor=white, group=center]; + + // ------------------------ + PTRHQ [label="~tmp\n+tmp+0", fillcolor=green, fontcolor=white, group=left]; + TOP -> PTRHQ + + VALH_ [label="~nscalar\n+int+tmp", fillcolor=white, group=center]; + TOP -> VALH_ + + INTHQ [label="~int\n+int+0", fillcolor=lightblue, group=right]; + TOP -> INTHQ + + LEFTHI [label="junk", style=invis, group=junkleft] + + + PTRHQ -> LEFTHI-> VALH_ -> INTHQ [style=invis]; + { rank=same; PTRHQ; LEFTHI; VALH_; INTHQ } + + // ------------------------ + PTRH_ [label="~ntmp\n+tmp", fillcolor=green, fontcolor=white, group=left]; + VALH_ -> PTRH_ + PTRHQ -> PTRH_ + + INTH_ [label="~nint\n+int", fillcolor=lightblue, group=right]; + VALH_ -> INTH_ + INTHQ -> INTH_ + { rank=same; PTRH_; INTH_ } + + // ------------------------ + NILX_ [label="~nil\n[int,tmp]+0", fillcolor=aqua, group=junkleft]; + INTHQ -> NILX_ + PTRHQ -> NILX_ + + NIL__ [label="nil\n[+int+tmp],0", fillcolor=pink]; + VALH_ -> NIL__; + + NILX_ -> NIL__ [style=invis]; + { rank=same; NIL__; NILX_ } + + // ------------------------ + PTRL_ [label="ntmp\ntmp", fillcolor=green, fontcolor=white, group=left]; + PTRH_ -> PTRL_ + + INTL_ [label="nint\nint", fillcolor=lightblue, group=right]; + INTH_ -> INTL_ + { rank=same; PTRL_; INTL_ } + + // ------------------------ + PTRL0 [label="tmp\ntmp,0", fillcolor=green, fontcolor=white, group=left]; + PTRL_ -> PTRL0 + NIL__ -> PTRL0 + + VALL_ [label="nscalar\nint,tmp", fillcolor=white, group=center]; + PTRL_ -> VALL_ + INTL_ -> VALL_ + NILX_ -> VALL_ + + INTL0 [label="int\nint,0", fillcolor=lightblue, group=right]; + INTL_ -> INTL0 + NIL__ -> INTL0 + + PTRL0 -> VALL_ -> INTL0 [style=invis]; + { rank=same; PTRL0; VALL_; INTL0 } + + // ------------------------ + BOT [label="scalar\nint,tmp,0", fillcolor=black, fontcolor=white, group=center]; + PTRL0 -> BOT + INTL0 -> BOT + VALL_ -> BOT + + // ------------------------ + // Verticle alignment + TOP -> VALH_ -> VALL_ -> BOT [style=invis]; + PTRHQ -> PTRH_ -> PTRL_ -> PTRL0 [style=invis]; + INTHQ -> INTH_ -> INTL_ -> INTL0 [style=invis]; + LEFTHI -> NILX_ [style=invis] +} diff --git a/docs/chapter26/lattice2.svg b/docs/chapter26/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/chapter26/lattice2.svg @@ -0,0 +1,260 @@ +<?xml version="1.0" encoding="UTF-8" standalone="no"?> +<!DOCTYPE svg PUBLIC "-//W3C//DTD SVG 1.1//EN" + "http://www.w3.org/Graphics/SVG/1.1/DTD/svg11.dtd"> +<!-- Generated by graphviz version 12.2.0 (20241103.1931) + --> +<!-- Title: Lattice Pages: 1 --> +<svg width="478pt" height="501pt" + viewBox="0.00 0.00 477.96 500.90" xmlns="http://www.w3.org/2000/svg" xmlns:xlink="http://www.w3.org/1999/xlink"> +<g id="graph0" class="graph" transform="scale(1 1) rotate(0) translate(4 496.9)"> +<title>Lattice</title> +<polygon fill="white" stroke="none" points="-4,4 -4,-496.9 473.96,-496.9 473.96,4 -4,4"/> +<!-- TOP --> +<g id="node1" class="node"> +<title>TOP</title> +<ellipse fill="black" stroke="black" cx="240.13" cy="-463.91" rx="59.04" ry="28.99"/> +<text text-anchor="middle" x="240.13" y="-467.11" font-family="Times New Roman,serif" font-size="14.00" fill="white">~scalar</text> +<text text-anchor="middle" x="240.13" y="-450.61" font-family="Times New Roman,serif" font-size="14.00" fill="white">+int+tmp+0</text> +</g> +<!-- PTRHQ --> +<g id="node2" class="node"> +<title>PTRHQ</title> +<ellipse fill="green" stroke="black" cx="43.13" cy="-376.92" rx="43.13" ry="28.99"/> +<text text-anchor="middle" x="43.13" y="-380.12" font-family="Times New Roman,serif" font-size="14.00" fill="white">~tmp</text> +<text text-anchor="middle" x="43.13" y="-363.62" font-family="Times New Roman,serif" font-size="14.00" fill="white">+tmp+0</text> +</g> +<!-- TOP->PTRHQ --> +<g id="edge1" class="edge"> +<title>TOP->PTRHQ</title> +<path fill="none" stroke="black" d="M196.41,-444.04C164.74,-430.38 121.99,-411.94 89.68,-398"/> +<polygon fill="black" stroke="black" points="91.11,-394.81 80.55,-394.06 88.34,-401.24 91.11,-394.81"/> +</g> +<!-- VALH_ --> +<g id="node3" class="node"> +<title>VALH_</title> +<ellipse fill="white" stroke="black" cx="240.13" cy="-376.92" rx="48.44" ry="28.99"/> +<text text-anchor="middle" x="240.13" y="-380.12" font-family="Times New Roman,serif" font-size="14.00">~nscalar</text> +<text text-anchor="middle" x="240.13" y="-363.62" font-family="Times New Roman,serif" font-size="14.00">+int+tmp</text> +</g> +<!-- TOP->VALH_ --> +<g id="edge2" class="edge"> +<title>TOP->VALH_</title> +<path fill="none" stroke="black" d="M235.15,-434.61C234.93,-429.02 234.85,-423.06 234.9,-417.18"/> +<polygon fill="black" stroke="black" points="238.39,-417.69 235.12,-407.61 231.39,-417.52 238.39,-417.69"/> +</g> +<!-- TOP->VALH_ --> +<!-- INTHQ --> +<g id="node4" class="node"> +<title>INTHQ</title> +<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-376.92" rx="37.83" ry="28.99"/> +<text text-anchor="middle" x="432.13" y="-380.12" font-family="Times New Roman,serif" font-size="14.00">~int</text> +<text text-anchor="middle" x="432.13" y="-363.62" font-family="Times New Roman,serif" font-size="14.00">+int+0</text> +</g> +<!-- TOP->INTHQ --> +<g id="edge3" class="edge"> +<title>TOP->INTHQ</title> +<path fill="none" stroke="black" d="M283.22,-443.83C314.91,-429.81 357.78,-410.83 389.39,-396.84"/> +<polygon fill="black" stroke="black" points="390.53,-400.16 398.26,-392.92 387.7,-393.76 390.53,-400.16"/> +</g> +<!-- LEFTHI --> +<!-- PTRHQ->LEFTHI --> +<!-- PTRH_ --> +<g id="node6" class="node"> +<title>PTRH_</title> +<ellipse fill="green" stroke="black" cx="43.13" cy="-289.94" rx="36.77" ry="28.99"/> +<text text-anchor="middle" x="43.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00" fill="white">~ntmp</text> +<text text-anchor="middle" x="43.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00" fill="white">+tmp</text> +</g> +<!-- PTRHQ->PTRH_ --> +<g id="edge8" class="edge"> +<title>PTRHQ->PTRH_</title> +<path fill="none" stroke="black" d="M38.15,-347.62C37.93,-342.03 37.85,-336.07 37.9,-330.2"/> +<polygon fill="black" stroke="black" points="41.39,-330.71 38.12,-320.63 34.39,-330.54 41.39,-330.71"/> +</g> +<!-- PTRHQ->PTRH_ --> +<!-- NILX_ --> +<g id="node8" class="node"> +<title>NILX_</title> +<ellipse fill="aqua" stroke="black" cx="150.13" cy="-289.94" rx="56.39" ry="28.99"/> +<text text-anchor="middle" x="150.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00">~nil</text> +<text text-anchor="middle" x="150.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00">[int,tmp]+0</text> +</g> +<!-- PTRHQ->NILX_ --> +<g id="edge12" class="edge"> +<title>PTRHQ->NILX_</title> +<path fill="none" stroke="black" d="M70.41,-354.26C82.91,-344.33 97.94,-332.4 111.56,-321.58"/> +<polygon fill="black" stroke="black" points="113.43,-324.56 119.09,-315.6 109.08,-319.08 113.43,-324.56"/> +</g> +<!-- VALH_->INTHQ --> +<!-- VALH_->PTRH_ --> +<g id="edge7" class="edge"> +<title>VALH_->PTRH_</title> +<path fill="none" stroke="black" d="M201.21,-359.13C167.78,-344.71 119.68,-323.96 85.33,-309.14"/> +<polygon fill="black" stroke="black" points="87.1,-306.09 76.53,-305.35 84.33,-312.52 87.1,-306.09"/> +</g> +<!-- INTH_ --> +<g id="node7" class="node"> +<title>INTH_</title> +<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-289.94" rx="31.47" ry="28.99"/> +<text text-anchor="middle" x="432.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00">~nint</text> +<text text-anchor="middle" x="432.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00">+int</text> +</g> +<!-- VALH_->INTH_ --> +<g id="edge9" class="edge"> +<title>VALH_->INTH_</title> +<path fill="none" stroke="black" d="M278.53,-358.93C311.9,-344.16 360.02,-322.86 393.48,-308.05"/> +<polygon fill="black" stroke="black" points="394.67,-311.35 402.4,-304.1 391.84,-304.95 394.67,-311.35"/> +</g> +<!-- NIL__ --> +<g id="node9" class="node"> +<title>NIL__</title> +<ellipse fill="pink" stroke="black" cx="324.13" cy="-289.94" rx="62.23" ry="28.99"/> +<text text-anchor="middle" x="324.13" y="-293.14" font-family="Times New Roman,serif" font-size="14.00">nil</text> +<text text-anchor="middle" x="324.13" y="-276.64" font-family="Times New Roman,serif" font-size="14.00">[+int+tmp],0</text> +</g> +<!-- VALH_->NIL__ --> +<g id="edge13" class="edge"> +<title>VALH_->NIL__</title> +<path fill="none" stroke="black" d="M264.43,-351.34C272.67,-343.01 282.01,-333.55 290.83,-324.64"/> +<polygon fill="black" stroke="black" points="293.12,-327.3 297.66,-317.72 288.14,-322.38 293.12,-327.3"/> +</g> +<!-- VALL_ --> +<g id="node13" class="node"> +<title>VALL_</title> +<ellipse fill="white" stroke="black" cx="240.13" cy="-115.97" rx="39.42" ry="28.99"/> +<text text-anchor="middle" x="240.13" y="-119.17" font-family="Times New Roman,serif" font-size="14.00">nscalar</text> +<text text-anchor="middle" x="240.13" y="-102.67" font-family="Times New Roman,serif" font-size="14.00">int,tmp</text> +</g> +<!-- VALH_->VALL_ --> +<!-- INTHQ->INTH_ --> +<g id="edge10" class="edge"> +<title>INTHQ->INTH_</title> +<path fill="none" stroke="black" d="M427.17,-348.1C426.94,-342.37 426.85,-336.25 426.9,-330.21"/> +<polygon fill="black" stroke="black" points="430.39,-330.42 427.13,-320.34 423.39,-330.26 430.39,-330.42"/> +</g> +<!-- INTHQ->INTH_ --> +<!-- INTHQ->NILX_ --> +<g id="edge11" class="edge"> +<title>INTHQ->NILX_</title> +<path fill="none" stroke="black" d="M396.99,-365.33C350,-351.17 266.03,-325.87 209.23,-308.75"/> +<polygon fill="black" stroke="black" points="210.28,-305.41 199.69,-305.88 208.26,-312.11 210.28,-305.41"/> +</g> +<!-- LEFTHI->VALH_ --> +<!-- LEFTHI->NILX_ --> +<!-- PTRL_ --> +<g id="node10" class="node"> +<title>PTRL_</title> +<ellipse fill="green" stroke="black" cx="43.13" cy="-202.96" rx="31.47" ry="28.99"/> +<text text-anchor="middle" x="43.13" y="-206.16" font-family="Times New Roman,serif" font-size="14.00" fill="white">ntmp</text> +<text text-anchor="middle" x="43.13" y="-189.66" font-family="Times New Roman,serif" font-size="14.00" fill="white">tmp</text> +</g> +<!-- PTRH_->PTRL_ --> +<g id="edge15" class="edge"> +<title>PTRH_->PTRL_</title> +<path fill="none" stroke="black" d="M38.17,-261.11C37.94,-255.39 37.85,-249.26 37.9,-243.22"/> +<polygon fill="black" stroke="black" points="41.39,-243.44 38.13,-233.36 34.39,-243.27 41.39,-243.44"/> +</g> +<!-- PTRH_->PTRL_ --> +<!-- INTL_ --> +<g id="node11" class="node"> +<title>INTL_</title> +<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-202.96" rx="27" ry="28.99"/> +<text text-anchor="middle" x="432.13" y="-206.16" font-family="Times New Roman,serif" font-size="14.00">nint</text> +<text text-anchor="middle" x="432.13" y="-189.66" font-family="Times New Roman,serif" font-size="14.00">int</text> +</g> +<!-- INTH_->INTL_ --> +<g id="edge16" class="edge"> +<title>INTH_->INTL_</title> +<path fill="none" stroke="black" d="M427.17,-261.11C426.94,-255.39 426.85,-249.26 426.9,-243.22"/> +<polygon fill="black" stroke="black" points="430.39,-243.44 427.13,-233.36 423.39,-243.27 430.39,-243.44"/> +</g> +<!-- INTH_->INTL_ --> +<!-- NILX_->NIL__ --> +<!-- NILX_->VALL_ --> +<g id="edge21" class="edge"> +<title>NILX_->VALL_</title> +<path fill="none" stroke="black" d="M164.79,-261.6C180.03,-232.15 203.95,-185.91 220.74,-153.45"/> +<polygon fill="black" stroke="black" points="223.74,-155.27 225.23,-144.78 217.53,-152.06 223.74,-155.27"/> +</g> +<!-- PTRL0 --> +<g id="node12" class="node"> +<title>PTRL0</title> +<ellipse fill="green" stroke="black" cx="43.13" cy="-115.97" rx="34.12" ry="28.99"/> +<text text-anchor="middle" x="43.13" y="-119.17" font-family="Times New Roman,serif" font-size="14.00" fill="white">tmp</text> +<text text-anchor="middle" x="43.13" y="-102.67" font-family="Times New Roman,serif" font-size="14.00" fill="white">tmp,0</text> +</g> +<!-- NIL__->PTRL0 --> +<g id="edge18" class="edge"> +<title>NIL__->PTRL0</title> +<path fill="none" stroke="black" d="M286.24,-266.48C232.36,-233.13 134.24,-172.38 80.6,-139.17"/> +<polygon fill="black" stroke="black" points="82.76,-136.39 72.41,-134.1 79.07,-142.34 82.76,-136.39"/> +</g> +<!-- INTL0 --> +<g id="node14" class="node"> +<title>INTL0</title> +<ellipse fill="lightblue" stroke="black" cx="432.13" cy="-115.97" rx="28.81" ry="28.99"/> +<text text-anchor="middle" x="432.13" y="-119.17" font-family="Times New Roman,serif" font-size="14.00">int</text> +<text text-anchor="middle" x="432.13" y="-102.67" font-family="Times New Roman,serif" font-size="14.00">int,0</text> +</g> +<!-- NIL__->INTL0 --> +<g id="edge23" class="edge"> +<title>NIL__->INTL0</title> +<path fill="none" stroke="black" d="M341.49,-261.99C360.34,-231.61 390.49,-183.05 410.79,-150.35"/> +<polygon fill="black" stroke="black" points="413.65,-152.38 415.95,-142.04 407.7,-148.69 413.65,-152.38"/> +</g> +<!-- PTRL_->PTRL0 --> +<g id="edge17" class="edge"> +<title>PTRL_->PTRL0</title> +<path fill="none" stroke="black" d="M38.17,-174.13C37.94,-168.47 37.85,-162.41 37.9,-156.43"/> +<polygon fill="black" stroke="black" points="41.39,-156.75 38.12,-146.67 34.39,-156.58 41.39,-156.75"/> +</g> +<!-- PTRL_->PTRL0 --> +<!-- PTRL_->VALL_ --> +<g id="edge19" class="edge"> +<title>PTRL_->VALL_</title> +<path fill="none" stroke="black" d="M71.36,-189.78C103.94,-175.73 157.92,-152.44 196.04,-135.99"/> +<polygon fill="black" stroke="black" points="197.16,-139.32 204.96,-132.15 194.39,-132.9 197.16,-139.32"/> +</g> +<!-- INTL_->VALL_ --> +<g id="edge20" class="edge"> +<title>INTL_->VALL_</title> +<path fill="none" stroke="black" d="M407.43,-191.02C376.23,-177.21 322.01,-153.22 283.77,-136.29"/> +<polygon fill="black" stroke="black" points="285.39,-133.18 274.83,-132.33 282.55,-139.58 285.39,-133.18"/> +</g> +<!-- INTL_->INTL0 --> +<g id="edge22" class="edge"> +<title>INTL_->INTL0</title> +<path fill="none" stroke="black" d="M427.17,-174.13C426.94,-168.41 426.85,-162.28 426.9,-156.24"/> +<polygon fill="black" stroke="black" points="430.39,-156.46 427.13,-146.38 423.39,-156.29 430.39,-156.46"/> +</g> +<!-- INTL_->INTL0 --> +<!-- PTRL0->VALL_ --> +<!-- BOT --> +<g id="node15" class="node"> +<title>BOT</title> +<ellipse fill="black" stroke="black" cx="240.13" cy="-28.99" rx="46.85" ry="28.99"/> +<text text-anchor="middle" x="240.13" y="-32.19" font-family="Times New Roman,serif" font-size="14.00" fill="white">scalar</text> +<text text-anchor="middle" x="240.13" y="-15.69" font-family="Times New Roman,serif" font-size="14.00" fill="white">int,tmp,0</text> +</g> +<!-- PTRL0->BOT --> +<g id="edge26" class="edge"> +<title>PTRL0->BOT</title> +<path fill="none" stroke="black" d="M73.48,-101.88C105.02,-88.28 154.83,-66.79 191.79,-50.85"/> +<polygon fill="black" stroke="black" points="193.14,-54.08 200.94,-46.9 190.37,-47.65 193.14,-54.08"/> +</g> +<!-- VALL_->INTL0 --> +<!-- VALL_->BOT --> +<g id="edge28" class="edge"> +<title>VALL_->BOT</title> +<path fill="none" stroke="black" d="M235.17,-87.15C234.94,-81.48 234.85,-75.42 234.9,-69.44"/> +<polygon fill="black" stroke="black" points="238.39,-69.76 235.12,-59.68 231.39,-69.6 238.39,-69.76"/> +</g> +<!-- VALL_->BOT --> +<!-- INTL0->BOT --> +<g id="edge27" class="edge"> +<title>INTL0->BOT</title> +<path fill="none" stroke="black" d="M405.84,-103.34C375.52,-89.91 325.06,-67.58 287.78,-51.08"/> +<polygon fill="black" stroke="black" points="289.59,-48.05 279.03,-47.21 286.75,-54.45 289.59,-48.05"/> +</g> +</g> +</svg> diff --git a/docs/chapter26/pardoe.docx b/docs/chapter26/pardoe.docx Binary files differnew file mode 100644 index 00000000..24fde921 --- /dev/null +++ b/docs/chapter26/pardoe.docx diff --git a/docs/chapter26/webtcp.min.js b/docs/chapter26/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter26/webtcp.min.js @@ -0,0 +1,65 @@ +function Http(j){this.cID=Math.random().toString(36).substr(2);this.webtcp=j;this.webtcp.httpClients[this.cID]=this;this.createPacket=function(){return{cID:this.cID,type:"http",host:this.remoteAddress,port:this.remotePort,method:null,data:null}};this.ondata=function(){};this.get=function(g,c){this.on("data",c);this.rpc("httpGet",[g])};this.post=function(g,c,j){this.on("data",j);this.rpc("httpPost",[g,c])}}Http.prototype=new WebTCPIO;function Socket(j,g,c,p){this.sID=Math.random().toString(36).substr(2);this.webtcp=j;this.closed=this.ready=!1;this.options=p;this.sockOpts={_updating:!1};this.remoteAddress=g;this.remotePort=c;this.webtcp.sockets[this.sID]=this;this.createPacket=function(){return{id:Math.random().toString(36).substr(2),sID:this.sID,type:"tcp",options:this.options,host:this.remoteAddress,port:this.remotePort,data:null}};this.onconnect=function(){this.webtcp.sockets[sID].ready=!0;this.webtcp.sockets[sID].closed=!1}; +this.ondata=function(){};this.onend=function(){};this.ontimeout=function(){};this.ondrain=function(){};this.onclose=function(){this.webtcp.sockets[sID].ready=!1;this.webtcp.sockets[sID].closed=!0};this.getSockOpts=function(){this.sockOpts._updating=!0;this.rpc("getSockOpts")};this.onSockOptsRcv=function(c){this.sockOpts=c;this.sockOpts._updating=!1}}Socket.prototype=new WebTCPIO;var JSON;JSON||(JSON={}); +(function(){function j(c,p){var q,t,n,x,i=k,e,l=p[c];l&&"object"==typeof l&&"function"==typeof l.toJSON&&(l=l.toJSON(c));"function"==typeof r&&(l=r.call(p,c,l));switch(typeof l){case "string":return g(l);case "number":return isFinite(l)?String(l):"null";case "boolean":case "null":return String(l);case "object":if(!l)return"null";k+=v;e=[];if("[object Array]"===Object.prototype.toString.apply(l)){x=l.length;for(q=0;q<x;q+=1)e[q]=j(q,l)||"null";n=0===e.length?"[]":k?"[\n"+k+e.join(",\n"+k)+"\n"+i+"]": +"["+e.join(",")+"]";k=i;return n}if(r&&"object"==typeof r){x=r.length;for(q=0;q<x;q+=1)"string"==typeof r[q]&&(t=r[q],n=j(t,l),n&&e.push(g(t)+(k?": ":":")+n))}else for(t in l)Object.prototype.hasOwnProperty.call(l,t)&&(n=j(t,l),n&&e.push(g(t)+(k?": ":":")+n));n=0===e.length?"{}":k?"{\n"+k+e.join(",\n"+k)+"\n"+i+"}":"{"+e.join(",")+"}";k=i;return n}}function g(c){n.lastIndex=0;return n.test(c)?'"'+c.replace(n,function(c){var g=D[c];return"string"==typeof g?g:"\\u"+("0000"+c.charCodeAt(0).toString(16)).slice(-4)})+ +'"':'"'+c+'"'}function c(c){return 10>c?"0"+c:c}"use strict";"function"!=typeof Date.prototype.toJSON&&(Date.prototype.toJSON=function(){return isFinite(this.valueOf())?this.getUTCFullYear()+"-"+c(this.getUTCMonth()+1)+"-"+c(this.getUTCDate())+"T"+c(this.getUTCHours())+":"+c(this.getUTCMinutes())+":"+c(this.getUTCSeconds())+"Z":null},String.prototype.toJSON=Number.prototype.toJSON=Boolean.prototype.toJSON=function(){return this.valueOf()});var p=/[\u0000\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g, +n=/[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,k,v,D={"\b":"\\b","\t":"\\t","\n":"\\n","\f":"\\f","\r":"\\r",'"':'\\"',"\\":"\\\\"},r;"function"!=typeof JSON.stringify&&(JSON.stringify=function(c,g,p){var n;v=k="";if("number"==typeof p)for(n=0;n<p;n+=1)v+=" ";else"string"==typeof p&&(v=p);r=g;if(!g||"function"==typeof g||"object"==typeof g&&"number"==typeof g.length)return j("",{"":c});throw Error("JSON.stringify");});"function"!= +typeof JSON.parse&&(JSON.parse=function(c,g){function j(c,k){var i,e,l=c[k];if(l&&"object"==typeof l)for(i in l)Object.prototype.hasOwnProperty.call(l,i)&&(e=j(l,i),void 0!==e?l[i]=e:delete l[i]);return g.call(c,k,l)}var k,c=String(c);p.lastIndex=0;p.test(c)&&(c=c.replace(p,function(c){return"\\u"+("0000"+c.charCodeAt(0).toString(16)).slice(-4)}));if(/^[\],:{}\s]*$/.test(c.replace(/\\(?:["\\\/bfnrt]|u[0-9a-fA-F]{4})/g,"@").replace(/"[^"\\\n\r]*"|true|false|null|-?\d+(?:\.\d*)?(?:[eE][+\-]?\d+)?/g, +"]").replace(/(?:^|:|,)(?:\s*\[)+/g,"")))return k=eval("("+c+")"),"function"==typeof g?j({"":k},""):k;throw new SyntaxError("JSON.parse");})})(); +SockJS=function(){var j=document,g=window,c={},p=function(){};p.prototype.addEventListener=function(a,b){this._listeners||(this._listeners={});a in this._listeners||(this._listeners[a]=[]);var f=this._listeners[a];-1===c.arrIndexOf(f,b)&&f.push(b)};p.prototype.removeEventListener=function(a,b){if(this._listeners&&a in this._listeners){var f=this._listeners[a],d=c.arrIndexOf(f,b);-1!==d&&(1<f.length?this._listeners[a]=f.slice(0,d).concat(f.slice(d+1)):delete this._listeners[a])}};p.prototype.dispatchEvent= +function(a){var b=a.type,c=Array.prototype.slice.call(arguments,0);this["on"+b]&&this["on"+b].apply(this,c);if(this._listeners&&b in this._listeners)for(var d=0;d<this._listeners[b].length;d++)this._listeners[b][d].apply(this,c)};var n=function(a,b){this.type=a;if("undefined"!=typeof b)for(var c in b)b.hasOwnProperty(c)&&(this[c]=b[c])};n.prototype.toString=function(){var a=[],b;for(b in this)if(this.hasOwnProperty(b)){var c=this[b];"function"==typeof c&&(c="[function]");a.push(b+"="+c)}return"SimpleEvent("+ +a.join(", ")+")"};var k=function(a){this.events=a||[]};k.prototype.emit=function(a){var b=Array.prototype.slice.call(arguments,1);!this.nuked&&this["on"+a]&&this["on"+a].apply(this,b);-1===c.arrIndexOf(this.events,a)&&c.log("Event "+JSON.stringify(a)+" not listed "+JSON.stringify(this.events)+" in "+this)};k.prototype.nuke=function(){this.nuked=!0;for(var a=0;a<this.events.length;a++)delete this[this.events[a]]};c.random_string=function(a,b){var b=b||37,c,d=[];for(c=0;c<a;c++)d.push("abcdefghijklmnopqrstuvwxyz0123456789_".substr(Math.floor(Math.random()* +b),1));return d.join("")};c.random_number=function(a){return Math.floor(Math.random()*a)};c.random_number_string=function(a){var b=(""+(a-1)).length;return(Array(b+1).join("0")+c.random_number(a)).slice(-b)};c.getOrigin=function(a){return(a+"/").split("/").slice(0,3).join("/")};c.isSameOriginUrl=function(a,b){return b||(b=g.location.href),a.split("/").slice(0,3).join("/")===b.split("/").slice(0,3).join("/")};c.getParentDomain=function(a){return/^[0-9.]*$/.test(a)||/^\[/.test(a)||!/[.]/.test(a)?a: +a.split(".").slice(1).join(".")};c.objectExtend=function(a,b){for(var c in b)b.hasOwnProperty(c)&&(a[c]=b[c]);return a};c.polluteGlobalNamespace=function(){"_jp"in g||(g._jp={})};c.closeFrame=function(a,b){return"c"+JSON.stringify([a,b])};c.userSetCode=function(a){return 1E3===a||3E3<=a&&4999>=a};c.countRTO=function(a){var b;return 100<a?b=3*a:b=a+200,b};c.log=function(){g.console&&console.log&&console.log.apply&&console.log.apply(console,arguments)};c.bind=function(a,b){return a.bind?a.bind(b):function(){return a.apply(b, +arguments)}};c.flatUrl=function(a){return-1===a.indexOf("?")&&-1===a.indexOf("#")};c.amendUrl=function(a){var b=j.location;if(!a)throw Error("Wrong url for SockJS");if(!c.flatUrl(a))throw Error("Only basic urls are supported in SockJS");return 0===a.indexOf("//")&&(a=b.protocol+a),0===a.indexOf("/")&&(a=b.protocol+"//"+b.host+a),a=a.replace(/[/]+$/,""),a};c.arrIndexOf=function(a,b){for(var c=0;c<a.length;c++)if(a[c]===b)return c;return-1};c.arrSkip=function(a,b){var f=c.arrIndexOf(a,b);return-1=== +f?a.slice():a.slice(0,f).concat(a.slice(f+1))};c.isArray=Array.isArray||function(a){return 0<={}.toString.call(a).indexOf("Array")};c.delay=function(a,b){return"function"==typeof a&&(b=a,a=0),setTimeout(b,a)};var v=/[\\\"\x00-\x1f\x7f-\x9f\u00ad\u0600-\u0604\u070f\u17b4\u17b5\u200c-\u200f\u2028-\u202f\u2060-\u206f\ufeff\ufff0-\uffff]/g,D={"\x00":"\\u0000","\u0001":"\\u0001","\u0002":"\\u0002","\u0003":"\\u0003","\u0004":"\\u0004","\u0005":"\\u0005","\u0006":"\\u0006","\u0007":"\\u0007","\b":"\\b", +"\t":"\\t","\n":"\\n","\x0B":"\\u000b","\f":"\\f","\r":"\\r","\u000e":"\\u000e","\u000f":"\\u000f","\u0010":"\\u0010","\u0011":"\\u0011","\u0012":"\\u0012","\u0013":"\\u0013","\u0014":"\\u0014","\u0015":"\\u0015","\u0016":"\\u0016","\u0017":"\\u0017","\u0018":"\\u0018","\u0019":"\\u0019","\u001a":"\\u001a","\u001b":"\\u001b","\u001c":"\\u001c","\u001d":"\\u001d","\u001e":"\\u001e","\u001f":"\\u001f",'"':'\\"',"\\":"\\\\","\u007f":"\\u007f","\u0080":"\\u0080","\u0081":"\\u0081","\u0082":"\\u0082", +"\u0083":"\\u0083","\u0084":"\\u0084","\u0085":"\\u0085","\u0086":"\\u0086","\u0087":"\\u0087","\u0088":"\\u0088","\u0089":"\\u0089","\u008a":"\\u008a","\u008b":"\\u008b","\u008c":"\\u008c","\u008d":"\\u008d","\u008e":"\\u008e","\u008f":"\\u008f","\u0090":"\\u0090","\u0091":"\\u0091","\u0092":"\\u0092","\u0093":"\\u0093","\u0094":"\\u0094","\u0095":"\\u0095","\u0096":"\\u0096","\u0097":"\\u0097","\u0098":"\\u0098","\u0099":"\\u0099","\u009a":"\\u009a","\u009b":"\\u009b","\u009c":"\\u009c","\u009d":"\\u009d", +"\u009e":"\\u009e","\u009f":"\\u009f","\u00ad":"\\u00ad","\u0600":"\\u0600","\u0601":"\\u0601","\u0602":"\\u0602","\u0603":"\\u0603","\u0604":"\\u0604","\u070f":"\\u070f","\u17b4":"\\u17b4","\u17b5":"\\u17b5","\u200c":"\\u200c","\u200d":"\\u200d","\u200e":"\\u200e","\u200f":"\\u200f","\u2028":"\\u2028","\u2029":"\\u2029","\u202a":"\\u202a","\u202b":"\\u202b","\u202c":"\\u202c","\u202d":"\\u202d","\u202e":"\\u202e","\u202f":"\\u202f","\u2060":"\\u2060","\u2061":"\\u2061","\u2062":"\\u2062","\u2063":"\\u2063", +"\u2064":"\\u2064","\u2065":"\\u2065","\u2066":"\\u2066","\u2067":"\\u2067","\u2068":"\\u2068","\u2069":"\\u2069","\u206a":"\\u206a","\u206b":"\\u206b","\u206c":"\\u206c","\u206d":"\\u206d","\u206e":"\\u206e","\u206f":"\\u206f","\ufeff":"\\ufeff","\ufff0":"\\ufff0","\ufff1":"\\ufff1","\ufff2":"\\ufff2","\ufff3":"\\ufff3","\ufff4":"\\ufff4","\ufff5":"\\ufff5","\ufff6":"\\ufff6","\ufff7":"\\ufff7","\ufff8":"\\ufff8","\ufff9":"\\ufff9","\ufffa":"\\ufffa","\ufffb":"\\ufffb","\ufffc":"\\ufffc","\ufffd":"\\ufffd", +"\ufffe":"\\ufffe","\uffff":"\\uffff"},r=/[\x00-\x1f\ud800-\udfff\ufffe\uffff\u0300-\u0333\u033d-\u0346\u034a-\u034c\u0350-\u0352\u0357-\u0358\u035c-\u0362\u0374\u037e\u0387\u0591-\u05af\u05c4\u0610-\u0617\u0653-\u0654\u0657-\u065b\u065d-\u065e\u06df-\u06e2\u06eb-\u06ec\u0730\u0732-\u0733\u0735-\u0736\u073a\u073d\u073f-\u0741\u0743\u0745\u0747\u07eb-\u07f1\u0951\u0958-\u095f\u09dc-\u09dd\u09df\u0a33\u0a36\u0a59-\u0a5b\u0a5e\u0b5c-\u0b5d\u0e38-\u0e39\u0f43\u0f4d\u0f52\u0f57\u0f5c\u0f69\u0f72-\u0f76\u0f78\u0f80-\u0f83\u0f93\u0f9d\u0fa2\u0fa7\u0fac\u0fb9\u1939-\u193a\u1a17\u1b6b\u1cda-\u1cdb\u1dc0-\u1dcf\u1dfc\u1dfe\u1f71\u1f73\u1f75\u1f77\u1f79\u1f7b\u1f7d\u1fbb\u1fbe\u1fc9\u1fcb\u1fd3\u1fdb\u1fe3\u1feb\u1fee-\u1fef\u1ff9\u1ffb\u1ffd\u2000-\u2001\u20d0-\u20d1\u20d4-\u20d7\u20e7-\u20e9\u2126\u212a-\u212b\u2329-\u232a\u2adc\u302b-\u302c\uaab2-\uaab3\uf900-\ufa0d\ufa10\ufa12\ufa15-\ufa1e\ufa20\ufa22\ufa25-\ufa26\ufa2a-\ufa2d\ufa30-\ufa6d\ufa70-\ufad9\ufb1d\ufb1f\ufb2a-\ufb36\ufb38-\ufb3c\ufb3e\ufb40-\ufb41\ufb43-\ufb44\ufb46-\ufb4e\ufff0-\uffff]/g, +B,M=JSON&&JSON.stringify||function(a){return v.lastIndex=0,v.test(a)&&(a=a.replace(v,function(a){return D[a]})),'"'+a+'"'};c.quote=function(a){a=M(a);r.lastIndex=0;if(r.test(a)){if(!B){var b,c={},d=[];for(b=0;65536>b;b++)d.push(String.fromCharCode(b));B=(r.lastIndex=0,d.join("").replace(r,function(a){return c[a]="\\u"+("0000"+a.charCodeAt(0).toString(16)).slice(-4),""}),r.lastIndex=0,c)}a=a.replace(r,function(a){return B[a]})}return a};var q="websocket xdr-streaming xhr-streaming iframe-eventsource iframe-htmlfile xdr-polling xhr-polling iframe-xhr-polling jsonp-polling".split(" "); +c.probeProtocols=function(){for(var a={},b=0;b<q.length;b++){var c=q[b];a[c]=e[c]&&e[c].enabled()}return a};c.detectProtocols=function(a,b,c){var d={},h=[];b||(b=q);for(var m=0;m<b.length;m++){var g=b[m];d[g]=a[g]}var e=function(a){var b=a.shift();d[b]?h.push(b):0<a.length&&e(a)};return!1!==c.websocket&&e(["websocket"]),d["xhr-streaming"]&&!c.null_origin?h.push("xhr-streaming"):d["xdr-streaming"]&&!c.cookie_needed&&!c.null_origin?h.push("xdr-streaming"):e(["iframe-eventsource","iframe-htmlfile"]), +d["xhr-polling"]&&!c.null_origin?h.push("xhr-polling"):d["xdr-polling"]&&!c.cookie_needed&&!c.null_origin?h.push("xdr-polling"):e(["iframe-xhr-polling","jsonp-polling"]),h};c.createHook=function(){var a="a"+c.random_string(8);if(!("_sockjs_global"in g)){var b={};g._sockjs_global=function(a){return a in b||(b[a]={id:a,del:function(){delete b[a]}}),b[a]}}return g._sockjs_global(a)};c.attachMessage=function(a){c.attachEvent("message",a)};c.attachEvent=function(a,b){"undefined"!=typeof g.addEventListener? +g.addEventListener(a,b,!1):(j.attachEvent("on"+a,b),g.attachEvent("on"+a,b))};c.detachMessage=function(a){c.detachEvent("message",a)};c.detachEvent=function(a,b){"undefined"!=typeof g.addEventListener?g.removeEventListener(a,b,!1):(j.detachEvent("on"+a,b),g.detachEvent("on"+a,b))};var t={},C=!1,x=function(){for(var a in t)t[a](),delete t[a]},i=function(){C||(C=!0,x())};c.attachEvent("beforeunload",i);c.attachEvent("unload",i);c.unload_add=function(a){var b=c.random_string(8);return t[b]=a,C&&c.delay(x), +b};c.unload_del=function(a){a in t&&delete t[a]};c.createIframe=function(a,b){var f=j.createElement("iframe"),d,h,m=function(){clearTimeout(d);try{f.onload=null}catch(a){}f.onerror=null},g=function(){f&&(m(),setTimeout(function(){f&&f.parentNode.removeChild(f);f=null},0),c.unload_del(h))};return f.src=a,f.style.display="none",f.style.position="absolute",f.onerror=function(){f&&(g(),b("onerror"))},f.onload=function(){clearTimeout(d);d=setTimeout(function(){f&&(g(),b("onload timeout"))},2E3)},j.body.appendChild(f), +d=setTimeout(function(){f&&(g(),b("timeout"))},15E3),h=c.unload_add(g),{post:function(a,b){try{f&&f.contentWindow&&f.contentWindow.postMessage(a,b)}catch(c){}},cleanup:g,loaded:m}};c.createHtmlfile=function(a,b){var f=new ActiveXObject("htmlfile"),d,h,m,e=function(){clearTimeout(d)},j=function(){f&&(e(),c.unload_del(h),m.parentNode.removeChild(m),m=f=null,CollectGarbage())};f.open();f.write('<html><script>document.domain="'+document.domain+'";<\/script></html>');f.close();f.parentWindow._jp=g._jp; +var i=f.createElement("div");return f.body.appendChild(i),m=f.createElement("iframe"),i.appendChild(m),m.src=a,d=setTimeout(function(){f&&(j(),b("timeout"))},15E3),h=c.unload_add(j),{post:function(a,b){try{m&&m.contentWindow&&m.contentWindow.postMessage(a,b)}catch(c){}},cleanup:j,loaded:e}};i=function(){};i.prototype=new k(["chunk","finish"]);i.prototype._start=function(a,b,f,d){var h=this;try{h.xhr=new XMLHttpRequest}catch(m){}if(!h.xhr)try{h.xhr=new g.ActiveXObject("Microsoft.XMLHTTP")}catch(e){}if(g.ActiveXObject|| +g.XDomainRequest)b+=(-1===b.indexOf("?")?"?":"&")+"t="+ +new Date;h.unload_ref=c.unload_add(function(){h._cleanup(!0)});try{h.xhr.open(a,b,!0)}catch(j){h.emit("finish",0,"");h._cleanup();return}if(!d||!d.no_credentials)h.xhr.withCredentials="true";if(d&&d.headers)for(var i in d.headers)h.xhr.setRequestHeader(i,d.headers[i]);h.xhr.onreadystatechange=function(){if(h.xhr){var a=h.xhr;switch(a.readyState){case 3:try{var b=a.status,c=a.responseText}catch(d){}c&&0<c.length&&h.emit("chunk",b,c);break;case 4:h.emit("finish", +a.status,a.responseText),h._cleanup(!1)}}};h.xhr.send(f)};i.prototype._cleanup=function(a){if(this.xhr){c.unload_del(this.unload_ref);this.xhr.onreadystatechange=function(){};if(a)try{this.xhr.abort()}catch(b){}this.unload_ref=this.xhr=null}};i.prototype.close=function(){this.nuke();this._cleanup(!0)};(c.XHRCorsObject=function(){var a=this,b=arguments;c.delay(function(){a._start.apply(a,b)})}).prototype=new i;(c.XHRLocalObject=function(a,b,f){var d=this;c.delay(function(){d._start(a,b,f,{no_credentials:!0})})}).prototype= +new i;i=c.XDRObject=function(a,b,f){var d=this;c.delay(function(){d._start(a,b,f)})};i.prototype=new k(["chunk","finish"]);i.prototype._start=function(a,b,f){var d=this,h=new XDomainRequest,b=b+((-1===b.indexOf("?")?"?":"&")+"t="+ +new Date),g=h.ontimeout=h.onerror=function(){d.emit("finish",0,"");d._cleanup(!1)};h.onprogress=function(){d.emit("chunk",200,h.responseText)};h.onload=function(){d.emit("finish",200,h.responseText);d._cleanup(!1)};d.xdr=h;d.unload_ref=c.unload_add(function(){d._cleanup(!0)}); +try{d.xdr.open(a,b),d.xdr.send(f)}catch(e){g()}};i.prototype._cleanup=function(a){if(this.xdr){c.unload_del(this.unload_ref);this.xdr.ontimeout=this.xdr.onerror=this.xdr.onprogress=this.xdr.onload=null;if(a)try{this.xdr.abort()}catch(b){}this.unload_ref=this.xdr=null}};i.prototype.close=function(){this.nuke();this._cleanup(!0)};c.isXHRCorsCapable=function(){return g.XMLHttpRequest&&"withCredentials"in new XMLHttpRequest?1:g.XDomainRequest&&j.domain?2:s.enabled()?3:4};var e=function(a,b,f){var d=this, +h;d._options={devel:!1,debug:!1,protocols_whitelist:[],info:void 0,rtt:void 0};f&&c.objectExtend(d._options,f);d._base_url=c.amendUrl(a);d._server=d._options.server||c.random_number_string(1E3);d._options.protocols_whitelist&&d._options.protocols_whitelist.length?h=d._options.protocols_whitelist:("string"==typeof b&&0<b.length?h=[b]:c.isArray(b)?h=b:h=null,h&&d._debug('Deprecated API: Use "protocols_whitelist" option instead of supplying protocol list as a second parameter to SockJS constructor.')); +d._protocols=[];d.protocol=null;d.readyState=e.CONNECTING;d._ir=N(d._base_url);d._ir.onfinish=function(a,b){d._ir=null;a?(d._options.info&&(a=c.objectExtend(a,d._options.info)),d._options.rtt&&(b=d._options.rtt),d._applyInfo(a,b,h),d._didClose()):d._didClose(1002,"Can't connect to server",!0)}};e.prototype=new p;e.version="0.3.2";e.CONNECTING=0;e.OPEN=1;e.CLOSING=2;e.CLOSED=3;e.prototype._debug=function(){this._options.debug&&c.log.apply(c,arguments)};e.prototype._dispatchOpen=function(){this.readyState=== +e.CONNECTING?(this._transport_tref&&(clearTimeout(this._transport_tref),this._transport_tref=null),this.readyState=e.OPEN,this.dispatchEvent(new n("open"))):this._didClose(1006,"Server lost session")};e.prototype._dispatchMessage=function(a){this.readyState===e.OPEN&&this.dispatchEvent(new n("message",{data:a}))};e.prototype._dispatchHeartbeat=function(){this.readyState===e.OPEN&&this.dispatchEvent(new n("heartbeat",{}))};e.prototype._didClose=function(a,b,f){var d=this;if(d.readyState!==e.CONNECTING&& +d.readyState!==e.OPEN&&d.readyState!==e.CLOSING)throw Error("INVALID_STATE_ERR");d._ir&&(d._ir.nuke(),d._ir=null);d._transport&&(d._transport.doCleanup(),d._transport=null);var h=new n("close",{code:a,reason:b,wasClean:c.userSetCode(a)});if(!c.userSetCode(a)&&d.readyState===e.CONNECTING&&!f){if(d._try_next_protocol(h))return;h=new n("close",{code:2E3,reason:"All transports failed",wasClean:!1,last_event:h})}d.readyState=e.CLOSED;c.delay(function(){d.dispatchEvent(h)})};e.prototype._didMessage=function(a){switch(a.slice(0, +1)){case "o":this._dispatchOpen();break;case "a":for(var a=JSON.parse(a.slice(1)||"[]"),b=0;b<a.length;b++)this._dispatchMessage(a[b]);break;case "m":a=JSON.parse(a.slice(1)||"null");this._dispatchMessage(a);break;case "c":a=JSON.parse(a.slice(1)||"[]");this._didClose(a[0],a[1]);break;case "h":this._dispatchHeartbeat()}};e.prototype._try_next_protocol=function(a){var b=this;b.protocol&&(b._debug("Closed transport:",b.protocol,""+a),b.protocol=null);for(b._transport_tref&&(clearTimeout(b._transport_tref), +b._transport_tref=null);;){a=b.protocol=b._protocols.shift();if(!a)return!1;if(e[a]&&!0===e[a].need_body&&(!j.body||"undefined"!=typeof j.readyState&&"complete"!==j.readyState))return b._protocols.unshift(a),b.protocol="waiting-for-load",c.attachEvent("load",function(){b._try_next_protocol()}),!0;if(e[a]&&e[a].enabled(b._options)){b._transport_tref=c.delay((b._options.rto||0)*(e[a].roundTrips||1)||5E3,function(){b.readyState===e.CONNECTING&&b._didClose(2007,"Transport timeouted")});var f=c.random_string(8), +f=b._base_url+"/"+b._server+"/"+f;return b._debug("Opening transport:",a," url:"+f," RTO:"+b._options.rto),b._transport=new e[a](b,f,b._base_url),!0}b._debug("Skipping transport:",a)}};e.prototype.close=function(a,b){if(a&&!c.userSetCode(a))throw Error("INVALID_ACCESS_ERR");return this.readyState!==e.CONNECTING&&this.readyState!==e.OPEN?!1:(this.readyState=e.CLOSING,this._didClose(a||1E3,b||"Normal closure"),!0)};e.prototype.send=function(a){if(this.readyState===e.CONNECTING)throw Error("INVALID_STATE_ERR"); +return this.readyState===e.OPEN&&this._transport.doSend(c.quote(""+a)),!0};e.prototype._applyInfo=function(a,b,f){this._options.info=a;this._options.rtt=b;this._options.rto=c.countRTO(b);this._options.info.null_origin=!j.domain;b=c.probeProtocols();this._protocols=c.detectProtocols(b,f,a)};i=e.websocket=function(a,b){var f=this,d=b+"/websocket";"https"===d.slice(0,5)?d="wss"+d.slice(5):d="ws"+d.slice(4);f.ri=a;f.url=d;f.ws=new (g.WebSocket||g.MozWebSocket)(f.url);f.ws.onmessage=function(a){f.ri._didMessage(a.data)}; +f.unload_ref=c.unload_add(function(){f.ws.close()});f.ws.onclose=function(){f.ri._didMessage(c.closeFrame(1006,"WebSocket connection broken"))}};i.prototype.doSend=function(a){this.ws.send("["+a+"]")};i.prototype.doCleanup=function(){var a=this.ws;a&&(a.onmessage=a.onclose=null,a.close(),c.unload_del(this.unload_ref),this.unload_ref=this.ri=this.ws=null)};i.enabled=function(){return!!g.WebSocket||!!g.MozWebSocket};i.roundTrips=2;var l=function(){};l.prototype.send_constructor=function(a){this.send_buffer= +[];this.sender=a};l.prototype.doSend=function(a){this.send_buffer.push(a);this.send_stop||this.send_schedule()};l.prototype.send_schedule_wait=function(){var a=this,b;a.send_stop=function(){a.send_stop=null;clearTimeout(b)};b=c.delay(25,function(){a.send_stop=null;a.send_schedule()})};l.prototype.send_schedule=function(){var a=this;if(0<a.send_buffer.length){var b="["+a.send_buffer.join(",")+"]";a.send_stop=a.sender(a.trans_url,b,function(){a.send_stop=null;a.send_schedule_wait()});a.send_buffer= +[]}};l.prototype.send_destructor=function(){this._send_stop&&this._send_stop();this._send_stop=null};var O=function(a,b,f){if(!("_send_form"in this)){var d=this._send_form=j.createElement("form"),h=this._send_area=j.createElement("textarea");h.name="d";d.style.display="none";d.style.position="absolute";d.method="POST";d.enctype="application/x-www-form-urlencoded";d.acceptCharset="UTF-8";d.appendChild(h);j.body.appendChild(d)}var d=this._send_form,h=this._send_area,g="a"+c.random_string(8);d.target= +g;d.action=a+"/jsonp_send?i="+g;var e;try{e=j.createElement('<iframe name="'+g+'">')}catch(i){e=j.createElement("iframe"),e.name=g}e.id=g;d.appendChild(e);e.style.display="none";try{h.value=b}catch(k){c.log("Your browser is seriously broken. Go home! "+k.message)}d.submit();var l=function(){e.onerror&&(e.onreadystatechange=e.onerror=e.onload=null,c.delay(500,function(){e.parentNode.removeChild(e);e=null}),h.value="",f())};return e.onerror=e.onload=l,e.onreadystatechange=function(){"complete"==e.readyState&& +l()},l},P=function(a){return function(b,c,d){return(new a("POST",b+"/xhr_send",c)).onfinish=function(a){d(a)},function(a){d(0,a)}}},i=e["jsonp-polling"]=function(a,b){c.polluteGlobalNamespace();this.ri=a;this.trans_url=b;this.send_constructor(O);this._schedule_recv()};i.prototype=new l;i.prototype._schedule_recv=function(){var a=this,b=a.trans_url+"/jsonp",f="a"+c.random_string(6),b=b+"?c="+escape("_jp."+f),d=function(b){delete g._jp[f];a._recv_stop=null;b&&(a._is_closing||a.ri._didMessage(b));a._is_closing|| +a._schedule_recv()},e,m=j.createElement("script"),i,k=function(a){i&&(i.parentNode.removeChild(i),i=null);m&&(clearTimeout(e),m.parentNode.removeChild(m),m.onreadystatechange=m.onerror=m.onload=m.onclick=null,m=null,d(a),d=null)},l=!1,p=null;m.id="a"+c.random_string(8);m.src=b;m.type="text/javascript";m.charset="UTF-8";m.onerror=function(){p||(p=setTimeout(function(){l||k(c.closeFrame(1006,"JSONP script loaded abnormally (onerror)"))},1E3))};m.onload=function(){k(c.closeFrame(1006,"JSONP script loaded abnormally (onload)"))}; +m.onreadystatechange=function(){if(/loaded|closed/.test(m.readyState)){if(m&&m.htmlFor&&m.onclick){l=!0;try{m.onclick()}catch(a){}}m&&k(c.closeFrame(1006,"JSONP script loaded abnormally (onreadystatechange)"))}};if("undefined"==typeof m.async&&j.attachEvent)if(/opera/i.test(navigator.userAgent))i=j.createElement("script"),i.text="try{var a = document.getElementById('"+m.id+"'); if(a)a.onerror();}catch(x){};",m.async=i.async=!1;else{try{m.htmlFor=m.id,m.event="onclick"}catch(n){}m.async=!0}"undefined"!= +typeof m.async&&(m.async=!0);e=setTimeout(function(){k(c.closeFrame(1006,"JSONP script loaded abnormally (timeout)"))},35E3);b=j.getElementsByTagName("head")[0];b=(b.insertBefore(m,b.firstChild),i&&b.insertBefore(i,b.firstChild),k);g._jp[f]=b;a._recv_stop=function(){g._jp[f]&&g._jp[f](c.closeFrame(1E3,"JSONP user aborted read"))}};i.enabled=function(){return!0};i.need_body=!0;i.prototype.doCleanup=function(){this._is_closing=!0;this._recv_stop&&this._recv_stop();this.ri=this._recv_stop=null;this.send_destructor()}; +i=function(){};i.prototype=new l;i.prototype.run=function(a,b,c,d,e){this.ri=a;this.trans_url=b;this.send_constructor(P(e));this.poll=new E(a,d,b+c,e)};i.prototype.doCleanup=function(){this.poll&&(this.poll.abort(),this.poll=null)};var w=e["xhr-streaming"]=function(a,b){this.run(a,b,"/xhr_streaming",y,c.XHRCorsObject)};w.prototype=new i;w.enabled=function(){return g.XMLHttpRequest&&"withCredentials"in new XMLHttpRequest&&!/opera/i.test(navigator.userAgent)};w.roundTrips=2;w.need_body=!0;l=e["xdr-streaming"]= +function(a,b){this.run(a,b,"/xhr_streaming",y,c.XDRObject)};l.prototype=new i;l.enabled=function(){return!!g.XDomainRequest};l.roundTrips=2;var F=e["xhr-polling"]=function(a,b){this.run(a,b,"/xhr",y,c.XHRCorsObject)};F.prototype=new i;F.enabled=w.enabled;F.roundTrips=2;w=e["xdr-polling"]=function(a,b){this.run(a,b,"/xhr",y,c.XDRObject)};w.prototype=new i;w.enabled=l.enabled;w.roundTrips=2;var s=function(){};s.prototype.i_constructor=function(a,b,f){var d=this;d.ri=a;d.origin=c.getOrigin(f);d.base_url= +f;d.trans_url=b;a=f+"/iframe.html";d.ri._options.devel&&(a+="?t="+ +new Date);d.window_id=c.random_string(8);a+="#"+d.window_id;d.iframeObj=c.createIframe(a,function(a){d.ri._didClose(1006,"Unable to load an iframe ("+a+")")});d.onmessage_cb=c.bind(d.onmessage,d);c.attachMessage(d.onmessage_cb)};s.prototype.doCleanup=function(){if(this.iframeObj){c.detachMessage(this.onmessage_cb);try{this.iframeObj.iframe.contentWindow&&this.postMessage("c")}catch(a){}this.iframeObj.cleanup();this.onmessage_cb=this.iframeObj= +this.iframeObj=null}};s.prototype.onmessage=function(a){if(a.origin===this.origin){var b=a.data.slice(0,8),c=a.data.slice(8,9),a=a.data.slice(9);if(b===this.window_id)switch(c){case "s":this.iframeObj.loaded();this.postMessage("s",JSON.stringify([e.version,this.protocol,this.trans_url,this.base_url]));break;case "t":this.ri._didMessage(a)}}};s.prototype.postMessage=function(a,b){this.iframeObj.post(this.window_id+a+(b||""),this.origin)};s.prototype.doSend=function(a){this.postMessage("m",a)};s.enabled= +function(){var a=navigator&&navigator.userAgent&&-1!==navigator.userAgent.indexOf("Konqueror");return("function"==typeof g.postMessage||"object"==typeof g.postMessage)&&!a};var G,H=function(a,b){parent!==g?parent.postMessage(G+a+(b||""),"*"):c.log("Can't postMessage, no parent window.",a,b)},u=function(){};u.prototype._didClose=function(a,b){H("t",c.closeFrame(a,b))};u.prototype._didMessage=function(a){H("t",a)};u.prototype._doSend=function(a){this._transport.doSend(a)};u.prototype._doCleanup=function(){this._transport.doCleanup()}; +c.parent_origin=void 0;e.bootstrap_iframe=function(){var a;G=j.location.hash.slice(1);c.attachMessage(function(b){if(b.source===parent&&("undefined"==typeof c.parent_origin&&(c.parent_origin=b.origin),b.origin===c.parent_origin)){var f=b.data.slice(0,8),d=b.data.slice(8,9),b=b.data.slice(9);if(f===G)switch(d){case "s":var h=JSON.parse(b),f=h[0],d=h[1],b=h[2],h=h[3];f!==e.version&&c.log('Incompatibile SockJS! Main site uses: "'+f+'", the iframe: "'+e.version+'".');if(!c.flatUrl(b)||!c.flatUrl(h)){c.log("Only basic urls are supported in SockJS"); +break}if(!c.isSameOriginUrl(b)||!c.isSameOriginUrl(h)){c.log("Can't connect to different domain from within an iframe. ("+JSON.stringify([g.location.href,b,h])+")");break}a=new u;a._transport=new u[d](a,b,h);break;case "m":a._doSend(b);break;case "c":a&&a._doCleanup(),a=null}}});H("s")};var z=function(a,b){var f=this;c.delay(function(){f.doXhr(a,b)})};z.prototype=new k(["finish"]);z.prototype.doXhr=function(a,b){var f=this,d=(new Date).getTime(),e=new b("GET",a+"/info"),g=c.delay(8E3,function(){e.ontimeout()}); +e.onfinish=function(a,b){clearTimeout(g);g=null;if(200===a){var c=(new Date).getTime()-d,e=JSON.parse(b);"object"!=typeof e&&(e={});f.emit("finish",e,c)}else f.emit("finish")};e.ontimeout=function(){e.close();f.emit("finish")}};var K=function(a){var b=this,f=function(){var c=new s;c.protocol="w-iframe-info-receiver";var f=function(a){"string"==typeof a&&"m"===a.substr(0,1)?(a=JSON.parse(a.substr(1)),b.emit("finish",a[0],a[1])):b.emit("finish");c.doCleanup();c=null};c.i_constructor({_options:{},_didClose:f, +_didMessage:f},a,a)};j.body?f():c.attachEvent("load",f)};K.prototype=new k(["finish"]);var L=function(){var a=this;c.delay(function(){a.emit("finish",{},2E3)})};L.prototype=new k(["finish"]);var N=function(a){if(c.isSameOriginUrl(a))return new z(a,c.XHRLocalObject);switch(c.isXHRCorsCapable()){case 1:return new z(a,c.XHRLocalObject);case 2:return new z(a,c.XDRObject);case 3:return new K(a);default:return new L}};(u["w-iframe-info-receiver"]=function(a,b,f){(new z(f,c.XHRLocalObject)).onfinish=function(b, +c){a._didMessage("m"+JSON.stringify([b,c]));a._didClose()}}).prototype.doCleanup=function(){};k=e["iframe-eventsource"]=function(){this.protocol="w-iframe-eventsource";this.i_constructor.apply(this,arguments)};k.prototype=new s;k.enabled=function(){return"EventSource"in g&&s.enabled()};k.need_body=!0;k.roundTrips=3;(u["w-iframe-eventsource"]=function(a,b){this.run(a,b,"/eventsource",I,c.XHRLocalObject)}).prototype=new i;k=e["iframe-xhr-polling"]=function(){this.protocol="w-iframe-xhr-polling";this.i_constructor.apply(this, +arguments)};k.prototype=new s;k.enabled=function(){return g.XMLHttpRequest&&s.enabled()};k.need_body=!0;k.roundTrips=3;(u["w-iframe-xhr-polling"]=function(a,b){this.run(a,b,"/xhr",y,c.XHRLocalObject)}).prototype=new i;k=e["iframe-htmlfile"]=function(){this.protocol="w-iframe-htmlfile";this.i_constructor.apply(this,arguments)};k.prototype=new s;k.enabled=function(){return s.enabled()};k.need_body=!0;k.roundTrips=3;(u["w-iframe-htmlfile"]=function(a,b){this.run(a,b,"/htmlfile",J,c.XHRLocalObject)}).prototype= +new i;var E=function(a,b,c,d){this.ri=a;this.Receiver=b;this.recv_url=c;this.AjaxObject=d;this._scheduleRecv()};E.prototype._scheduleRecv=function(){var a=this,b=a.poll=new a.Receiver(a.recv_url,a.AjaxObject);b.onmessage=function(b){a.ri._didMessage(b.data)};b.onclose=function(c){a.poll=b=b.onmessage=b.onclose=null;a.poll_is_closing||("permanent"===c.reason?a.ri._didClose(1006,"Polling error ("+c.reason+")"):a._scheduleRecv())}};E.prototype.abort=function(){this.poll_is_closing=!0;this.poll&&this.poll.abort()}; +var I=function(a){var b=this,f=new EventSource(a);f.onmessage=function(a){b.dispatchEvent(new n("message",{data:unescape(a.data)}))};b.es_close=f.onerror=function(a,e){var g=e?"user":2!==f.readyState?"network":"permanent";b.es_close=f.onmessage=f.onerror=null;f.close();f=null;c.delay(200,function(){b.dispatchEvent(new n("close",{reason:g}))})}};I.prototype=new p;I.prototype.abort=function(){this.es_close&&this.es_close({},!0)};var A,J=function(a){var b=this;c.polluteGlobalNamespace();b.id="a"+c.random_string(6, +26);a+=(-1===a.indexOf("?")?"?":"&")+"c="+escape("_jp."+b.id);if(void 0===A)if("ActiveXObject"in g)try{A=!!new ActiveXObject("htmlfile")}catch(f){}else A=!1;var d=A?c.createHtmlfile:c.createIframe,e;g._jp[b.id]={start:function(){e.loaded()},message:function(a){b.dispatchEvent(new n("message",{data:a}))},stop:function(){b.iframe_close({},"network")}};b.iframe_close=function(a,c){e.cleanup();b.iframe_close=e=null;delete g._jp[b.id];b.dispatchEvent(new n("close",{reason:c}))};e=d(a,function(){b.iframe_close({}, +"permanent")})};J.prototype=new p;J.prototype.abort=function(){this.iframe_close&&this.iframe_close({},"user")};var y=function(a,b){var c=this,d=0;c.xo=new b("POST",a,null);c.xo.onchunk=function(a,b){if(200===a)for(;;){var e=b.slice(d),g=e.indexOf("\n");if(-1===g)break;d+=g+1;e=e.slice(0,g);c.dispatchEvent(new n("message",{data:e}))}};c.xo.onfinish=function(a,b){c.xo.onchunk(a,b);c.xo=null;c.dispatchEvent(new n("close",{reason:200===a?"network":"permanent"}))}};return y.prototype=new p,y.prototype.abort= +function(){this.xo&&(this.xo.close(),this.dispatchEvent(new n("close",{reason:"user"})),this.xo=null)},e.getUtils=function(){return c},e.getIframeTransport=function(){return s},e}();"_sockjs_onload"in window&&setTimeout(_sockjs_onload,1);"function"==typeof define&&define.amd&&define("sockjs",[],function(){return SockJS});function WebTCP(j,g){this.sockets={};this.httpClients={};this.sock=new SockJS("http://"+j+":"+g+"/bridge");this.ready=!1;this.outputBuffer=[];var c=this;this.sock.onopen=function(){c.ready=!0;c.processBuffer()};this.processBuffer=function(){if(0<this.outputBuffer.length&&this.ready)for(var c in this.outputBuffer)this.sock.send(this.outputBuffer[c])};this.sock.onmessage=function(g){g.data=JSON.parse(g.data);g.data.sID?(sID=g.data.sID,c.sockets[sID].onEvent(g.data.eventName,g.data.data)):g.data.cID&& +(cID=g.data.cID,c.httpClients[cID].onEvent(g.data.eventName,g.data.data))};this.sock.onclose=function(){console.log("close")};this.createSocket=function(c,g,j){return new Socket(this,c,g,j)};this.createHTTPClient=function(){return new Http(this)}};function WebTCPIO(){this.onEvent=function(j,g){this["on"+j](g);if(this["on"+j+"Custom"])this["on"+j+"Custom"](g)};this.on=function(j,g){this["on"+j+"Custom"]=g};this.rpc=function(j,g){var c=this.createPacket();c.command=j;c.args=g;this.send(JSON.stringify(c));return c.id};this.write=function(j){var g=this.createPacket();g.data=j;this.send(JSON.stringify(g));return g.id};this.send=function(j){if(this.webtcp.ready)this.webtcp.sock.send(j);else{if(this.webtcp.outputBuffer>this.webtcp.BUFF_SIZE)throw"Output buffer is already full, but sockJS connection is not ready yet"; +this.webtcp.outputBuffer.push(j)}};this.onerror=function(j){throw j;}};
\ No newline at end of file diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index 727b1c61..520d7e3a 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -191,7 +191,13 @@ public class Parser { for( StructNode init : INITS.values() ) init.unkeep().kill(); INITS.clear(); + for( Ary<Node> captures : CAPTURES.values() ) + for( Node value : captures ) value.unkill(); + CAPTURES.clear(); stop.peephole(); + // Helpers are built with init(), so their complete call graph exists + // before any inlining. Seed those nodes now along with the parsed body. + _code._start.walk(n -> { _code.add(n); return null; }); } /** @@ -201,7 +207,20 @@ public class Parser { return parseFunctionBody(sig, loc, null, ids); } - private ReturnNode parseFunctionBody( TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String... ids) { + private FunNode _privateFun; + private HashMap<String,Var> _fieldVars; + private record Constructor(TypeFunPtr sig, Lexer loc, int body, String[] ids, java.util.BitSet finals) {} + private Constructor _constructor; + private final HashMap<String,TypeFunPtr> ALLOCS = new HashMap<>(); + private final HashMap<String,ReturnNode> INITIALIZERS = new HashMap<>(); + private final HashMap<String,Ary<Node>> CAPTURES = new HashMap<>(); + private Ary<Node> _captures; + + private ReturnNode parseFunctionBody(TypeFunPtr sig, Lexer loc, java.util.BitSet finals, String... ids) { + return parseFunctionBody(sig,loc,finals,false,ids); + } + + private ReturnNode parseFunctionBody(TypeFunPtr sig, Lexer loc, java.util.BitSet finals, boolean initializer, String... ids) { // If this is a method, record & restore the existing struct fields, // which are also the struct initializers. The method might update // mutable fields, so when the function parse is done reset back to @@ -212,6 +231,13 @@ public class Parser { // Stack parser state on the local Java stack, and unstack it later FunNode oldfun = _fun; + FunNode oldPrivate = _privateFun; + HashMap<String,Var> oldFields = _fieldVars; + Constructor oldConstructor = _constructor; + _fieldVars = new HashMap<>(); + _constructor = null; + Ary<Node> oldCaptures = _captures; + _captures = initializer ? new Ary<>(Node.class) : null; ScopeNode breakScope = _breakScope; _breakScope = null; ScopeNode continueScope = _continueScope; _continueScope = null; @@ -221,6 +247,8 @@ public class Parser { // exact fidx, and ignores the return (because the fidx will only match // the exact single function). _code.link(fun); + _privateFun = sig.ret() instanceof TypeMem ? fun : null; + fun._constructor = _privateFun!=null; Node rpc = new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).peephole(); @@ -228,7 +256,8 @@ public class Parser { RegionNode r = new RegionNode( null,null,null).init(); assert r.inProgress(); PhiNode rmem = new BulkMemPhiNode(ScopeNode.MEM0,r,null).init(); - PhiNode rrez = new PhiNode(ScopeNode.ARG0,r,null).init(); + PhiNode rrez = (sig.ret() instanceof TypeMem + ? new BulkMemPhiNode("#selfMem",r,null) : new PhiNode(ScopeNode.ARG0,r,null)).init(); ReturnNode ret = new ReturnNode(r, rmem, rrez, rpc, fun).init(); fun.setRet(ret); assert ret.inProgress(); @@ -238,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()); @@ -248,10 +277,46 @@ public class Parser { _scope.define(ids[i], t, finals==null ? t instanceof TypeNil : finals.get(i), new ParmNode(ids[i],i+2,t,fun,con(t)).peephole(), loc); } - // Parse the body + // Fields stay in Scope as ordinary SSA values throughout the body. + // Private memory is read at helper entry and written once at exit. + int fields = _scope.nIns(); + if( initializer ) + _scope.push(new Kind.Define((TypeMemPtr)TYPES.get(_nestedType))); + else if( _privateFun==fun ) { + TypeStruct shape=((TypeMemPtr)TYPES.get(_nestedType))._obj; + StructNode defaults=INITS.get(_nestedType); + for( int i=0; i<shape._fields.length; i++ ) { + Field f=shape._fields[i]; + Var v=null; + for( int j=preParse.length-1; j>=0; j-- ) + if( _scope.var(j)._name.equals(f._fname) ) { v=_scope.var(j); break; } + assert v!=null; + _fieldVars.put(f._fname,v); + if( !f._one ) { + Node value=missingInit(defaults.in(i),new java.util.BitSet()) ? con(Type.BOTTOM) + : new LoadNode(loc(),f._fname,f._alias,privateMem(),self(),off(shape,f._fname),true).peephole(); + _scope.update(v,value); + } + } + } Node last=ZERO; - while (!peek('}') && !_lexer.isEOF()) + while (!peek('}') && !_lexer.isEOF()) { last = parseStatement(); + if( initializer ) fields = initFields(fields); + } + if( initializer ) { + finishFields(); + CAPTURES.put(_nestedType,_captures); + if( _constructor!=null ) { + Constructor ctor=_constructor; + int end=pos(ctor.body()); + ReturnNode body=parseFunctionBody(ctor.sig(),ctor.loc(),ctor.finals(),ctor.ids()); + body.fun().setName(shortName(_nestedType)); + require("}"); + pos(end); + } + } + if( _privateFun==fun ) last = storeFields(initializer); // Last expression is the return except for the top-level main if( ctrl()._type==Type.CONTROL ) @@ -277,8 +342,13 @@ public class Parser { ret = (ReturnNode)ret.peephole(); // Function scope ends + if( initializer ) _scope.pop(); _scope.pop(); _fun = oldfun; + _privateFun = oldPrivate; + _fieldVars = oldFields; + _constructor = oldConstructor; + _captures = oldCaptures; _breakScope = breakScope; _continueScope = continueScope; @@ -326,6 +396,7 @@ public class Parser { else if (matchx("break") ) return parseBreak(); else if (matchx("continue")) return parseContinue(); else if (matchx("struct") ) return parseStruct(); + else if (_scope.inConstructor() && matchx("new")) return parseConstructorDeclaration(); else if (matchx(";") ) return null; // Empty statement // Break ambiguity around leading function types and starting a block else if (peek('{') && !isTypeFun() ) { @@ -336,6 +407,24 @@ public class Parser { else return parseDeclarationStatement(); } + // In a struct declaration, new names the constructor. Its body still + // parses as a function; in expressions, new allocates and calls it. + private Node parseConstructorDeclaration() { + Lexer loc=loc(); + String name=requireId(); + String expect=shortName(_nestedType); + if( !name.equals(expect) ) + throw error("Constructor name '"+name+"' must match type name '"+expect+"'"); + require("="); + Node ctor=constructorFunc(); + TypeFunPtr sig=(TypeFunPtr)ctor._type; + Node lift=liftExpr(ctor,sig,true); + if( !_scope.define(name,sig,true,lift,loc) ) + throw error("Redefining constructor '"+name+"'"); + _scope.lookup(name)._init=true; + return require(lift,";"); + } + /** * Parses a while statement * @@ -637,6 +726,8 @@ public class Parser { private Node parseReturn() { var expr = require(parseAsgn(), ";"); // Force the lazy whole-memory Phi before closing this exit. + if( _privateFun==_fun ) + throw error("A constructor cannot return a value"); _fun.addReturn(ctrl(), _scope.mem(), expr); ctrl(XCTRL); // Kill control return expr; @@ -677,8 +768,10 @@ 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); Node expr = parseAsgn(); // Lift expression, based on type @@ -768,20 +861,28 @@ public class Parser { boolean initialized = match("="); Node expr; if( initialized ) { - expr = isExternDecl() - ? externDecl(name,t) - : parseAsgn(); + expr = isExternDecl() ? externDecl(name,t) + : _scope.inConstructor() && name.equals(shortName(_nestedType)) + ? constructorFunc() : parseAsgn(); // var/val, then type comes from expression if( inferType ) { if( expr._type==Type.NIL ) 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() ) { if( expr instanceof ExternNode ) t = expr._type; // Upgrade declared type to exact function - else _code.link(tfp).setName(name); // Assign debug name to Simple function + else if( _code._link(tfp)!=null ) _code.link(tfp).setName(name); // Assign debug name to Simple function } } else { @@ -828,60 +929,206 @@ public class Parser { * @return zero */ private String _nestedType; + private static String shortName(String name) { return name.substring(name.lastIndexOf('.')+1); } + private Node parseStruct() { - // "struct" already parsed, so expect the struct name next. String old = _nestedType; - String typeName = requireId(); - if( old!=null ) typeName = old+"."+typeName; - _nestedType = typeName; - // New declared or forward-ref type - TypeStruct ts = TYPES.get(typeName) instanceof TypeMemPtr tmp ? tmp._obj : TypeStruct.open(typeName); - TYPES.put(typeName,TypeMemPtr.make(ts)); - - // A Block scope parse, and inspect the scope afterward for fields. - _scope.push(new Kind.Define(TypeMemPtr.make(ts))); + String name = requireId(); + if( old!=null ) name=old+"."+name; + _nestedType=name; + TypeMemPtr ptr = TYPES.get(name) instanceof TypeMemPtr p ? p : TypeMemPtr.make(TypeStruct.open(name)); + TYPES.put(name,ptr); require("{"); - int lexlen = _scope._kinds.last()._lexSize, nvar=lexlen; - while (!peek('}') && !_lexer.isEOF()) { - parseStatement().isKill(); - while( nvar < _scope._vars._len ) { - Var v = _scope.var(nvar++); - if( !v.isFRef() ) { - ts = ts.add( Field.make( v._name, v.type(), _code.getALIAS(), v._final, v._final && v._init && _scope.in( v._idx )._type != Type.TOP ) ); - TYPES.put( typeName, TypeMemPtr.make( ts ) ); - } - } - } - - // Count struct declarations - int varlen = _scope._vars._len; - ts = ts.close(); - TYPES.put(typeName,TypeMemPtr.make(ts)); - - // Generate an initializing struct - StructNode s = new StructNode(ts); - for( int i=lexlen; i<varlen; i++ ) - if( !_scope.var(i).isFRef() ) // Promote to outer scope, not defined here - s.addDef(_scope.in(i)); // Keep the program code to generate instance - - // Save instance default constructor - s.setType(s.compute()); // Do not call peephole, in case the entire struct is a big plain constant - INITS.put(typeName,s.keep()); - - // Having finalized the struct, upgrade all the 'self' pointers - for( Node n : s._inputs ) - if( n._type instanceof TypeFunPtr tfp && _code.link(tfp) instanceof FunNode fun ) - _code.addAll( fun._outputs ); - - - // Done with struct/block scope - _nestedType = old; + TypeFunPtr sig = _code.makeFun(TypeFunPtr.make(false,false,new Type[]{ptr,TypeMem.BOT},TypeMem.BOT)); + ReturnNode init = parseFunctionBody(sig,loc(),null,true,"self","#selfMem"); + init.fun()._name=name+".<init>"; + INITIALIZERS.put(name,init); + TypeStruct shape = ((TypeMemPtr)TYPES.get(name))._obj; + ALLOCS.put(name,makeAllocator(shape,init)); + _nestedType=old; require("}"); require(";"); - _scope.pop(); return ZERO; } + private int initFields(int index) { + TypeStruct shape = ((TypeMemPtr)TYPES.get(_nestedType))._obj; + while( index<_scope.nIns() ) { + Var v = _scope.var(index++); + if( v.isFRef() ) continue; + Node value = _scope.in(v); + // 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)); + _fieldVars.put(v._name,v); + } + return index; + } + + private void finishFields() { + TypeStruct shape = ((TypeMemPtr)TYPES.get(_nestedType))._obj.close(); + TYPES.put(_nestedType,TypeMemPtr.make(shape)); + StructNode constants = new StructNode(shape); + int first = _scope._kinds.last()._lexSize; + for( int i=first; i<_scope.nIns(); i++ ) + if( !_scope.var(i).isFRef() ) constants.addDef(_scope.in(i)); + constants.setType(constants.compute()); + INITS.put(_nestedType,constants.keep()); + } + + private Node self() { return _scope.in(_scope.lookup("self")); } + private Node privateMem() { return _scope.in(_scope.lookup("#selfMem")); } + + private boolean privateSelf(Node ptr) { + if( _privateFun!=_fun || _privateFun==null ) return false; + while( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) ptr=ptr.in(1); + Node self=self(); + while( self instanceof ConvertNode || self instanceof ReadOnlyNode || self instanceof GuardNode ) self=self.in(1); + return ptr==self; + } + private boolean mayBeSelf(Node ptr, java.util.BitSet seen) { + if( _privateFun==null || _privateFun!=_fun || seen.get(ptr._nid) ) return false; + seen.set(ptr._nid); + if( privateSelf(ptr) ) return true; + if( ptr instanceof ConvertNode || ptr instanceof ReadOnlyNode || ptr instanceof GuardNode ) + return mayBeSelf(ptr.in(1),seen); + if( ptr instanceof PhiNode && !(ptr instanceof ParmNode) ) + for( int i=1; i<ptr.nIns(); i++ ) + if( ptr.in(i)!=null && mayBeSelf(ptr.in(i),seen) ) return true; + return false; + } + private void checkPublication(Node value) { + // Private stores can replace a field only while no public alias can + // observe it. Early publication needs the next chapter's escape state. + if( mayBeSelf(value,new java.util.BitSet()) ) + throw error("Cannot publish self before the constructor finishes"); + } + // The only writes to the new object's fields are at helper exits. Branches + // and loops above this point merge values, not private-memory snapshots. + private Node storeFields(boolean initializer) { + TypeStruct shape=((TypeMemPtr)TYPES.get(_nestedType))._obj; + Node priv=privateMem().keep(); + for( Field f : shape._fields ) { + if( f._one ) continue; + Var v=_fieldVars.get(f._fname); + Node value=_scope.in(_scope.update(v,null)); // Force a lazy value Phi. + if( initializer && missingInit(value,new java.util.BitSet()) ) continue; + if( !initializer && ctrl()._type!=Type.XCONTROL && missingInit(value,new java.util.BitSet()) ) + throw error("'"+shape._name+"' is not fully initialized, field '"+f._fname+"' needs to be set in a constructor"); + checkPublication(value); + Node next=fieldStore(f,ctrl(),priv,self(),off(shape,f._fname),value); + priv.unkeep(); priv=next.keep(); + } + return priv.unkeep(); + } + + private Node fieldStore(Field f, Node ctrl, Node priv, Node ptr, Node off, Node value) { + Node st=new StoreNode(loc(),f._fname,f._alias,f._t,priv,ptr,off,value,true); + st.setDef(0,ctrl); + return new MemMergeNode(priv,f._alias,st.peephole()).peephole(); + } + + private Node constructorFunc() { + require("{"); + Ary<Type> types = new Ary<>(Type.class); + Ary<String> names = new Ary<>(String.class); + types.add(TYPES.get(_nestedType)); names.add("self"); + types.add(TypeMem.BOT); names.add("#selfMem"); + java.util.BitSet finals = new java.util.BitSet(); + finals.set(0); // Rebinding self would detach the pointer from its private memory. + while( true ) { + Type t=type(); + if( t==null ) break; + finals.set(names.size(),bindingFinal(t)); + types.add(t); names.add(requireId()); + match(","); + } + require("->"); + TypeFunPtr sig = _code.makeFun(TypeFunPtr.make(false,false,types.asAry(),TypeMem.BOT)); + // Bind the signature now, but parse the body after the field list is + // closed. Then even a later field has a local SSA slot before branches + // and loops are parsed. Strings/comments must not affect brace depth. + _constructor=new Constructor(sig,loc(),pos(),names.asAry(),finals); + int depth=1; + while( depth>0 ) { + if( peek('"') ) { parseString(); continue; } + if( match("'") ) { parseChar(); continue; } + char ch=_lexer.nextXChar(); + if( ch==Character.MAX_VALUE ) throw errorSyntax("}"); + if( ch=='{' ) depth++; + if( ch=='}' ) depth--; + } + return con(sig); + } + + private CallEndNode rawCall(Node ctrl, Node pub, ReturnNode target, Node... args) { + Node[] inputs = new Node[args.length+3]; + inputs[0]=ctrl; inputs[1]=pub; + System.arraycopy(args,0,inputs,2,args.length); + inputs[inputs.length-1]=new FunPtrNode(target.fun().sig(),target).peephole(); + // Keep the complete declaration-side caller set before any inlining. + CallNode call = new CallNode(loc(),inputs).init(); + CallEndNode end = new CallEndNode(call).init(); + call.link(target.fun()); + return end; + } + + private Node publish(TypeStruct shape, Node ctrl, Node pub, Node priv, Node ptr) { + priv.keep(); ptr.keep(); + for( Field f : shape._fields ) if( !f._one ) { + pub.keep(); + Node esc = new EscapeNode(loc(),f,ctrl,pub,priv,ptr).peephole(); + Node next = new MemMergeNode(pub,f._alias,esc).peephole(); + pub.unkeep(); pub=next; + } + ptr.unkeep(); priv.unkill(); + return pub; + } + + private TypeFunPtr makeAllocator(TypeStruct shape, ReturnNode init) { + Field cf=shape.field(shortName(shape._name)); + TypeFunPtr ctor=cf!=null && cf._t instanceof TypeFunPtr f ? f : null; + int nargs=ctor==null ? 0 : ctor.nargs()-2; + Ary<Node> captures=CAPTURES.get(shape._name); + Type[] types=new Type[nargs+captures.size()]; + for( int i=0; i<nargs; i++ ) types[i]=ctor.arg(i+2); + for( int i=0; i<captures.size(); i++ ) types[nargs+i]=captures.at(i)._type; + TypeMemPtr ptr=TypeMemPtr.make(shape); + TypeFunPtr sig=_code.makeFun(TypeFunPtr.make(false,false,types,ptr)); + FunNode fun=new FunNode(loc(),sig,shape._name,null,_code._start).init(); + fun._name=shape._name+".<new>"; fun._constructor=true; + _code.link(fun); + Node rpc=new ParmNode("$rpc",0,TypeRPC.BOT,fun,con(TypeRPC.BOT)).init(); + Node pub=new ParmNode(ScopeNode.MEM0,1,TypeMem.BOT,fun,con(TypeMem.BOT)).init(); + Node[] args=new Node[nargs+2]; + for( int i=0; i<nargs; i++ ) args[i+2]=new ParmNode("arg"+i,i+2,types[i],fun,con(types[i])).init(); + Node alloc=new NewNode(ptr,fun,null,off(shape," len")).init(); + Node self=new ProjNode(alloc,0,shape._name).init(); + Node priv=new ProjNode(alloc,1,"#selfMem").init(); + Node[] initArgs=new Node[captures.size()+2]; + initArgs[0]=self; initArgs[1]=priv; + for( int i=0; i<captures.size(); i++ ) + initArgs[i+2]=new ParmNode("capture"+i,nargs+i+2,types[nargs+i],fun,con(types[nargs+i])).init(); + CallEndNode end=rawCall(fun,pub,init,initArgs); + Node ctl=new CProjNode(end,0,ScopeNode.CTRL).init(); + pub=new ProjNode(end,1,ScopeNode.MEM0).init(); + priv=new ProjNode(end,2,"#selfMem").init(); + if( ctor!=null ) { + args[0]=self; args[1]=priv; + end=rawCall(ctl,pub,_code.link(ctor).ret(),args); + ctl=new CProjNode(end,0,ScopeNode.CTRL).init(); + pub=new ProjNode(end,1,ScopeNode.MEM0).init(); + priv=new ProjNode(end,2,"#selfMem").init(); + } + pub=publish(shape,ctl,pub,priv,self); + ReturnNode ret=new ReturnNode(ctl,pub,self,rpc,fun).init(); + fun.setRet(ret); _code._stop.addDef(ret); + return sig; + } // Parse and return a type or null. Valid types always are followed by an // 'id' which the caller must parse. This lets us distinguish forward ref @@ -1233,7 +1480,7 @@ public class Parser { String name = _lexer.matchId(); Var var = name==null ? null : _scope.lookup(name); if( var!=null && !(var.type() instanceof TypeMemPtr) ) { - if( var._final ) + if( var._final && !_scope.canInit(var) ) throw error("Cannot reassign final '"+var._name+"'"); // Resolve fields just as a read or postfix update does. Updating // their declaration's local slot would silently lose the Store. @@ -1329,8 +1576,10 @@ 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); if( postfix(ch) ) rvalue.unkeep(); @@ -1343,6 +1592,8 @@ public class Parser { // If a method var, allow nested blocks and methods, but not fcns or other structs Kind kind = _scope.kind(var); if( kind instanceof Kind.Define ) { + if( var.isFRef() ) return false; // Promote an unresolved lexical name, not self.name. + if( _privateFun==_fun && _privateFun!=null ) return true; for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- ) { Kind xkind = _scope._kinds.at(i); if( xkind instanceof Kind.Block ) continue; @@ -1356,6 +1607,17 @@ public class Parser { // If a normal var, allow any nested blocks, and a last fcn - // but not functions further out (which involves capture). Node def = _scope.in(var._idx); + if( _captures!=null && _scope.kind(var) instanceof Kind.Func && + !(var._final && def._type.isConstant()) && !(def instanceof FRefNode) ) { + if( !(def instanceof ParmNode parm && parm.fun()==_fun) ) { + _captures.add(def.keep()); + Type type=def._type; + int index=_fun.sig().nargs(); + _fun.addParseArg(type); + _scope.update(var,new ParmNode(var._name,index+2,type,_fun,con(type)).init()); + } + return false; + } for( int i = _scope.depth()-1; i>=0 && var._idx < _scope._kinds.at(i)._lexSize; i-- ) if( _scope._kinds.at(i) instanceof Kind.Func && !(def instanceof FRefNode) && !(var._final && def._type.isConstant()) ) @@ -1364,6 +1626,31 @@ public class Parser { return false; } + private void checkCaptureWrite(Var var) { + if( _captures==null ) return; + for( int i=_scope.depth()-1; i>=0 && var._idx<_scope._kinds.at(i)._lexSize; i-- ) + if( _scope._kinds.at(i) instanceof Kind.Func ) + 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. @@ -1421,38 +1708,85 @@ public class Parser { if( !(t instanceof TypeMemPtr tmp) ) throw error("Cannot allocate a "+t.str()); - // Parse new struct { default_initialization } - StructNode s = INITS.get(tmp._obj._name); - if( s==null ) throw error("Unknown struct type '" + tmp._obj._name + "'"); - - Field[] fs = s._ts._fields; - // if the object is fully initialized, we can skip a block here. - // Check for constructor block: - boolean hasConstructor = match("{"); - Ary<Node> init=s._inputs; int idx=0; - if( hasConstructor ) { - idx = _scope.nIns(); - // Push a scope, and pre-assign all struct fields. - _scope.push(new Kind.Block()); - Lexer loc = loc(); - for( int i=0; i<fs.length; i++ ) - // An initial TOP means the field needs to be initialized. We - // store a BOT initially; any partial init will fall to BOT - // (merge BOT and the partial) and be obviously only a partial - // init. To be initialized the field needs a full clobber. - _scope.define(fs[i]._fname, fs[i]._t, fs[i]._final, s.in(i)._type==Type.TOP ? con(Type.BOTTOM) : s.in(i), loc); - // Parse the constructor body - require(parseBlock(new Kind.Alloc(tmp)),"}"); - init = _scope._inputs; - } - // Check that all fields are initialized - for( int i=idx; i<init.size(); i++ ) - if( missingInit(init.at(i),new java.util.BitSet()) ) - throw error("'"+tmp._obj._name+"' is not fully initialized, field '" + fs[i-idx]._fname + "' needs to be set in a constructor"); - Node ptr = newStruct(tmp._obj, off(tmp._obj, " len"), idx, init ); - if( hasConstructor ) - _scope.pop(); - return ptr; + TypeStruct shape=tmp._obj; + TypeFunPtr sig=ALLOCS.get(shape._name); + if( sig==null ) throw error("Unknown struct type '"+shape._name+"'"); + if( !peek('{') ) { + // Obvious missing defaults can still be diagnosed here. A user + // constructor or a merge needs the later publication check. + if( shape.field(shortName(shape._name))==null ) { + StructNode defaults=INITS.get(shape._name); + Type initial=INITIALIZERS.get(shape._name).expr()._type; + for( int i=0; i<shape._fields.length; i++ ) { + Field f=shape._fields[i]; + Field written=initial instanceof TypeMem m && m._t instanceof TypeStruct ts ? ts.field(f._fname) : null; + if( missingInit(defaults.in(i),new java.util.BitSet()) && (written==null || written._t==Type.BOTTOM) ) + throw error("'"+shape._name+"' is not fully initialized, field '"+f._fname+"' needs to be set in a constructor"); + } + } + Node fptr=new FunPtrNode(sig,_code.link(sig).ret()).peephole(); + Ary<Node> args=new Ary<>(Node.class); + if( match("(") ) { + while( !peek(')') ) { + Node arg=parseAsgn(); + checkPublication(arg); + args.add(arg.keep()); + if( !match(",") ) break; + } + require(")"); + } + for( Node capture : CAPTURES.get(shape._name) ) { + checkPublication(capture); + args.add(capture.keep()); + } + if( args.size()!=sig.nargs() ) throw error("Wrong number of constructor arguments for '"+shape._name+"'"); + for( Node arg : args ) arg.unkeep(); + return callWithArgs(fptr,args.asAry()); + } + require("{"); + Node alloc=new NewNode(TypeMemPtr.make(shape),ctrl(),null,off(shape," len")).init(); + Node ptr=new ProjNode(alloc,0,shape._name).init().keep(); + Node priv=new ProjNode(alloc,1,"#selfMem").init(); + Ary<Node> captures=CAPTURES.get(shape._name); + Node[] args=new Node[captures.size()+2]; + args[0]=ptr; args[1]=priv; + for( int i=0; i<captures.size(); i++ ) { + checkPublication(captures.at(i)); + args[i+2]=captures.at(i); + } + CallEndNode end=rawCall(ctrl(),mem(),INITIALIZERS.get(shape._name),args).keep(); + ctrl(new CProjNode(end,0,ScopeNode.CTRL).peephole()); + mem(new ProjNode(end,1,ScopeNode.MEM0).peephole()); + priv=new ProjNode(end,2,"#selfMem").peephole().keep(); + end.unkeep(); + int first=_scope.nIns(); + _scope.push(new Kind.Block()); + StructNode constants=INITS.get(shape._name); + for( int i=0; i<shape._fields.length; i++ ) { + Field f=shape._fields[i]; + Type initial=INITIALIZERS.get(shape._name).expr()._type; + Field written=initial instanceof TypeMem m && m._t instanceof TypeStruct ts ? ts.field(f._fname) : null; + boolean missing=missingInit(constants.in(i),new java.util.BitSet()) && + (written==null || written._t==Type.BOTTOM); + Node value=f._one ? constants.in(i) + : missing ? con(Type.BOTTOM) + : new LoadNode(loc(),f._fname,f._alias,priv,ptr,off(shape,f._fname),true).peephole(); + _scope.define(f._fname,f._t,f._final,value,loc()); + } + require(parseBlock(new Kind.Alloc(tmp)),"}"); + for( int i=0; i<shape._fields.length; i++ ) { + Field f=shape._fields[i]; + if( f._one ) continue; + Node value=_scope.in(first+i); + checkPublication(value); + if( ctrl()._type!=Type.XCONTROL && missingInit(value,new java.util.BitSet()) ) + throw error("'"+shape._name+"' is not fully initialized, field '"+f._fname+"' needs to be set in a constructor"); + Node next=fieldStore(f,ctrl(),priv,ptr,off(shape,f._fname),value); + priv.unkeep(); priv=next.keep(); + } + _scope.pop(); + mem(publish(shape,ctrl(),mem(),priv.unkeep(),ptr)); + return ptr.unkeep(); } // The old constructor model requires each field on every path. An @@ -1470,50 +1804,18 @@ public class Parser { } - /** - * Return a NewNode initialized memory. - * @param obj is the declared type, with GLB fields - * @param init is a collection of initialized fields - */ - private Node newStruct( TypeStruct obj, Node size, int idx, Ary<Node> init ) { - Field[] fs = obj._fields; - if( fs==null ) - throw error("Unknown struct type '" + obj._name + "'"); - Node prior = mem().keep(); - MemMergeNode input = new MemMergeNode((Node)null); - for( Field f : fs ) if( !f._one ) input.alias(f._alias,prior); - // Allocation zeroes its fields; nonzero initializers become explicit Stores. - Node[] ns = new Node[3]; - ns[0] = ctrl(); - ns[1] = input.peephole(); - ns[2] = size; - Node nnn = new NewNode(TypeMemPtr.make(obj),ns).peephole().keep(); - Node ptr = new ProjNode(nnn,0,obj._name).peephole().keep(); - Node out = new ProjNode(nnn,1,"$mem").peephole().keep(); - MemMergeNode after = new MemMergeNode(prior); - for( Field f : fs ) if( !f._one ) after.alias(f._alias,out); - mem(after.peephole()); - out.unkeep(); - nnn.unkeep(); - prior.unkill(); - for( int i=0; i<fs.length; i++ ) { - Node val = init.get(idx+i); - if( !fs[i]._one && val._type != val._type.makeZero() ) { - Field f = fs[i]; - Node st = new StoreNode(loc(),f._fname,f._alias,f._t,mem(),ptr,off(obj,f._fname),val,true).peephole(); - mem(new MemMergeNode(mem(),f._alias,st).peephole()); - } - } - return ptr.unkeep(); - } - - private static final Ary<Node> ALTMP = new Ary<>(Node.class); private Node newArray(TypeStruct ary, Node len) { - ConFldOffNode base = off(ary, "[]"); - int scale= ary.aryScale(); - Node size = peep(new AddNode(base,peep(new ShlNode(null,len.keep(),con(scale))))); - ALTMP.clear(); ALTMP.add(len.unkeep()); ALTMP.add(con(ary._fields[1]._t.makeZero())); - return newStruct(ary,size,0,ALTMP); + ConFldOffNode base=off(ary,"[]"); + Node size=peep(new AddNode(base,peep(new ShlNode(null,len.keep(),con(ary.aryScale()))))); + Node alloc=new NewNode(TypeMemPtr.make(ary),ctrl(),null,size).init(); + Node ptr=new ProjNode(alloc,0,ary._name).init().keep(); + Node priv=new ProjNode(alloc,1,"#selfMem").init(); + // calloc supplied the zero elements; initialize the length before + // either alias becomes visible to the public heap. + Field length=ary.field("#"); + priv=fieldStore(length,ctrl(),priv,ptr,off(ary,"#"),len.unkeep()); + mem(publish(ary,ctrl(),mem(),priv,ptr)); + return ptr.unkeep(); } private Node newString(String s) { TypeMemPtr tmp = typeAry(TypeInteger.U8,true); @@ -1536,6 +1838,7 @@ public class Parser { private void store(String name, int alias, Type glb, Node ptr, Node off, Node val, boolean init, Node ctrl) { if( !init && ptr._type instanceof TypeMemPtr view && view._ro && ctrl()._type!=Type.XCONTROL ) throw error("Cannot modify final field '"+name+"'"); + checkPublication(val); Node prior = mem().keep(); Node st = new StoreNode(loc(),name,alias,glb,prior,ptr,off,val,init); st.setDef(0,ctrl); @@ -1580,6 +1883,9 @@ public class Parser { private Node parsePostfixName(Node expr, String name) { return parsePostfixName(expr,name,0); } private Node parsePostfixName(Node expr, String name, int pre) { + if( privateSelf(expr) ) return parsePrivateField(name,pre); + if( !privateSelf(expr) && mayBeSelf(expr,new java.util.BitSet()) ) + throw error("Cannot access self through a merged alias during construction"); if( expr._type==Type.NIL ) throw error("Accessing unknown field '" + name + "' from 'null'"); @@ -1601,6 +1907,8 @@ public class Parser { // Get field type and layout offset from base type and field index fidx Field f = base._fields[fidx]; // Field from field index Type tf = f._t; + if( tf instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) + throw error("A constructor is only called by new"); if( tf instanceof TypeMemPtr ftmp && ftmp.isFRef() ) tf = ftmp.makeFrom(((TypeMemPtr)(TYPES.get(ftmp._obj._name)))._obj); if( base.isAry() && tf instanceof TypeConAry con ) @@ -1679,9 +1987,7 @@ public class Parser { off.keep(); if( pre==0 && matchOpx('=','=') ) { Node value = parseAsgn().keep(); - Node st = new StoreNode(loc(),name,1,Type.BOTTOM,mem(),expr,off,value,false); - st.setDef(0,ctrl()); - mem(st.peephole()); + unknownStore(name,expr,off,value); expr.unkill(); off.unkill(); return value.unkeep(); @@ -1692,9 +1998,7 @@ public class Parser { char ch = pre==0 ? _lexer.matchOperAssign() : (char)pre; if( ch!=0 ) { Node op = opAssign(ch,load,Type.BOTTOM).keep(); - Node st = new StoreNode(loc(),name,1,Type.BOTTOM,mem(),expr,off,op,false); - st.setDef(0,ctrl()); - mem(st.peephole()); + unknownStore(name,expr,off,op); // The field width is not known yet. A compound assignment returns // the stored value after conversion; postfix returns the old load. // Reading our own Store folds once its alias and width are known. @@ -1706,12 +2010,60 @@ public class Parser { } load.keep(); op.unkill(); + } else if( !name.equals("[]") && match("(") ) { + Node result=functionCall(load,expr,name); + off.unkill(); + return parsePostfix(require(result,")")); } else load.keep(); expr.unkill(); off.unkill(); return pre==0 ? parsePostfix(load.unkeep()) : load.unkeep(); } + private void unknownStore(String name, Node ptr, Node off, Node value) { + checkPublication(value); + Node st=new StoreNode(loc(),name,1,Type.BOTTOM,mem(),ptr,off,value,false); + st.setDef(0,ctrl()); + mem(st.peephole()); + } + + // Explicit self.x and an unqualified field name use the same local slot. + // The map also keeps self.x distinct from a parameter/local named x. + private Node parsePrivateField(String name, int pre) { + Var v=_fieldVars.get(name); + if( v==null ) throw error("Cannot resolve field '"+name+"'"); + if( v.type() instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) + throw error("A constructor is only called by new"); + if( pre==0 && matchOpx('=','=') ) { + checkPrivateWrite(name); + Node value=parseAsgn().keep(); + checkPublication(value); + _scope.update(v,liftExpr(value,v.type(),false)); + return value.unkeep(); + } + Node value=_scope.in(_scope.update(v,null)); + if( value instanceof ConstantNode && (value._type==Type.BOTTOM || value._type==Type.TOP) ) + throw error("Cannot read uninitialized field '"+name+"'"); + char ch=pre==0 ? _lexer.matchOperAssign() : (char)pre; + if( ch!=0 ) { + checkPrivateWrite(name); + Node op=opAssign(ch,value,v.type()); + checkPublication(op); + _scope.update(v,op); + if( postfix(ch) ) value.unkeep(); + return pre==0 && postfix(ch) ? value : op; + } + if( value._type instanceof TypeFunPtr && match("(") ) + return parsePostfix(require(functionCall(value,self()),")")); + 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 ) { @@ -1781,6 +2133,9 @@ public class Parser { * </pre> */ private Node functionCall(Node fcn, Node self) { + return functionCall(fcn,self,null); + } + private Node functionCall(Node fcn, Node self, String method) { if( fcn._type == Type.NIL ) throw error("Calling a null function pointer"); if( !(fcn instanceof FRefNode) && fcn._type!=Type.BOTTOM && fcn._type!=TypeScalar.BOT && !fcn._type.isa(TypeFunPtr.BOT) ) @@ -1790,11 +2145,13 @@ public class Parser { Ary<Node> args = new Ary<>( Node.class ); args.push(null); // Space for ctrl,mem args.push(null); + if( self != null ) checkPublication(self); if( self != null ) // Method call has a self args.push(self); while( !peek(')') ) { Node arg = parseAsgn(); if( arg==null ) break; + checkPublication(arg); args.push(arg.keep()); if( !match(",") ) break; } @@ -1814,7 +2171,9 @@ public class Parser { } // Into the call - CallNode call = (CallNode)new CallNode(loc(), args.asAry()).peephole(); + CallNode call = new CallNode(loc(), args.asAry()); + call._method=method; + call=(CallNode)call.peephole(); // Post-call setup CallEndNode cend = (CallEndNode)new CallEndNode(call).peephole(); call.peephole(); // Rerun peeps after CallEnd, allows early inlining @@ -1826,6 +2185,21 @@ public class Parser { return new ProjNode(cend,2,"#2").peephole(); } + private Node callWithArgs(Node fptr, Node[] args) { + Node[] inputs=new Node[args.length+3]; + inputs[0]=ctrl(); inputs[1]=mem(); + System.arraycopy(args,0,inputs,2,args.length); + inputs[inputs.length-1]=fptr; + CallNode call=new CallNode(loc(),inputs).init(); + CallEndNode end=new CallEndNode(call).init().keep(); + if( fptr._type instanceof TypeFunPtr sig && _code.link(sig)!=null ) call.link(_code.link(sig)); + ctrl(new CProjNode(end,0,ScopeNode.CTRL).peephole()); + mem(new ProjNode(end,1,ScopeNode.MEM0).peephole()); + Node result=new ProjNode(end,2,"#2").peephole(); + end.unkeep(); + return result; + } + // Just after parsing "type foo = " can parse `"C"` private boolean isExternDecl( ) { int old = pos(); diff --git a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java index b79eb73d..a49299e1 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java +++ b/src/main/java/com/seaofnodes/simple/codegen/CodeGen.java @@ -154,7 +154,6 @@ public class CodeGen { private int _fidx =0; public TypeFunPtr makeFun( TypeFunPtr fun ) { int fidx = _fidx++; - assert fidx<64; // TODO: need a larger FIDX space return fun.makeFrom(fidx); } // Signature for MAIN diff --git a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java index da45db4f..9be662e8 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java +++ b/src/main/java/com/seaofnodes/simple/codegen/GlobalCodeMotion.java @@ -251,7 +251,7 @@ public abstract class GlobalCodeMotion { visit.set(def._nid); for( Node out : def._outputs ) if( out instanceof MemOpNode ld && ld._isLoad && late[ld._nid]==null ) work.push(ld); - if( def instanceof MemMergeNode ) + if( def instanceof MemMergeNode || def instanceof EscapeNode ) for( int i=1; i<def.nIns(); i++ ) if( def.in(i)!=null ) wakeLoads(def.in(i),late,work,visit); } diff --git a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java index 5a91cf9f..b0351c98 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java +++ b/src/main/java/com/seaofnodes/simple/codegen/InstSelect.java @@ -89,6 +89,7 @@ class InstSelect { private Node select(Node n) { + if( n instanceof EscapeNode esc ) return new EscapeMach(esc); if( n instanceof GuardNode guard ) return new GuardMach(guard); if( n instanceof PtrToIntNode ptr ) return new PtrToIntMach(ptr); Node op = n; diff --git a/src/main/java/com/seaofnodes/simple/codegen/Opto.java b/src/main/java/com/seaofnodes/simple/codegen/Opto.java index c78e732e..82646a25 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/Opto.java +++ b/src/main/java/com/seaofnodes/simple/codegen/Opto.java @@ -101,6 +101,7 @@ abstract public class Opto { // Always true for main if( fun.sig().fidx() == code._main.fidx() ) return true; // No escape analysis yet: a surviving address may be called from outside. + if( fun._constructor ) return false; if( fun.hasPtr() ) return true; // Never true for stdlib or anonymous functions if( fun._name == null || fun._name.startsWith("sys.") ) @@ -113,8 +114,7 @@ abstract public class Opto { // into a Call, link the Call and Fun. private static void linkCG(CodeGen code, TypeFunPtr tfp, CallNode call) { if( tfp.nargs() != call.nargs() ) return; // Error calls hit this - for( long fidxs=tfp.fidxs(); fidxs!=0; fidxs=TypeFunPtr.nextFIDX(fidxs) ) { - int fidx = Long.numberOfTrailingZeros(fidxs); + for( int fidx=XInt.next(tfp.fidxs(),-1); fidx>=0; fidx=XInt.next(tfp.fidxs(),fidx) ) { FunNode fun = code.link(fidx); // null here means an external function; i.e. this Call // calls to an outside library and all its arguments escape. diff --git a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java index bc698e19..7dadb4d2 100644 --- a/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java +++ b/src/main/java/com/seaofnodes/simple/codegen/TypeCheck.java @@ -14,6 +14,11 @@ abstract class TypeCheck { }); if( errs.isEmpty() ) return; + // Publication is a producer check. Report an incomplete object before + // its users complain about values or permissions inherited from it. + for( Node n : errs ) + if( n instanceof EscapeNode ) throw n.err(); + // A bad Load now produces BOTTOM. Report the bad access before a // Convert or arithmetic use that merely received its failed result. Node first = errs.at(0); diff --git a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java index 8399ed09..e6f70c64 100644 --- a/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java +++ b/src/main/java/com/seaofnodes/simple/node/BulkMemPhiNode.java @@ -101,6 +101,7 @@ public class BulkMemPhiNode extends PhiNode { case ConstantNode con -> 0; case MemMergeNode mmm -> missingAlias(mmm); case MemOpNode mem -> unsplit(mem._alias); + case EscapeNode esc -> unsplit(esc._field._alias); case BulkMemPhiNode bulk -> missingAlias(bulk); default -> throw new AssertionError("Unexpected memory input "+n); }; @@ -118,6 +119,7 @@ public class BulkMemPhiNode extends PhiNode { case MemMergeNode mmm -> missingAlias(mmm); case BulkMemPhiNode bulk -> missingAlias(bulk); case MemOpNode mem -> unsplit(mem._alias); + case EscapeNode esc -> unsplit(esc._field._alias); case MemPhiNode phi -> unsplit(phi._alias); default -> { assert use instanceof ReturnNode || use instanceof CallNode || use instanceof ParmNode diff --git a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java index aa586b17..604bb9da 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallEndNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallEndNode.java @@ -163,7 +163,8 @@ public class CallEndNode extends CFGNode implements MultiNode { } for( int i=0; i<len; i++ ) { Node n = TINYBODY[i]; - if( n instanceof StoreNode || n instanceof MemMergeNode ) { + if( n instanceof StoreNode || n instanceof MemMergeNode || + n instanceof NewNode || n instanceof ProjNode || n instanceof EscapeNode ) { for( Node in : n._inputs ) copy[i].addDef(mapped(in,copy)); CodeGen.CODE.add(copy[i]); } @@ -211,7 +212,8 @@ public class CallEndNode extends CFGNode implements MultiNode { if( n==ret ) continue; if( n instanceof ParmNode parm && parm.region()!=fun ) return 0; if( n!=fun && !(n instanceof ParmNode) && - !(n instanceof StoreNode) && !(n instanceof MemMergeNode) ) + !(n instanceof StoreNode) && !(n instanceof MemMergeNode) && + !(n instanceof NewNode) && !(n instanceof ProjNode) && !(n instanceof EscapeNode) ) return 0; if( n.nOuts()>TINYBODY.length ) return 0; for( Node use : n._outputs ) { diff --git a/src/main/java/com/seaofnodes/simple/node/CallNode.java b/src/main/java/com/seaofnodes/simple/node/CallNode.java index b2708531..21f438da 100644 --- a/src/main/java/com/seaofnodes/simple/node/CallNode.java +++ b/src/main/java/com/seaofnodes/simple/node/CallNode.java @@ -6,6 +6,7 @@ import com.seaofnodes.simple.IterPeeps; import com.seaofnodes.simple.Parser; import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.XInt; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.util.Utils; @@ -16,9 +17,12 @@ public class CallNode extends CFGNode { // Source location for late reported errors public final Parser.Lexer _loc; + // A forward field call records its receiver before its declaration tells + // us whether this is a method or an ordinary function stored in a field. + public String _method; public CallNode(Parser.Lexer loc, Node... nodes) { super(nodes); _loc = loc; } - public CallNode(CallNode call) { super(call); _loc = call._loc; } + public CallNode(CallNode call) { super(call); _loc = call._loc; _method=call._method; } @Override public String label() { return "Call"; } @@ -90,6 +94,15 @@ public class CallNode extends CFGNode { public Node idealize() { CallEndNode cend = cend(); if( cend==null ) return null; // Still building + if( _method!=null ) { + if( !(arg(2)._type instanceof com.seaofnodes.simple.type.TypeMemPtr ptr) ) return null; + var field=ptr._obj.field(_method); + if( field==null ) return null; + if( !(fptr()._type instanceof TypeFunPtr sig) ) return null; + if( !field._final || CodeGen.CODE.externFunc(sig)!=null ) delDef(2); + _method=null; + return this; + } // Link: call calls target function. Linking makes the target FunNode // point to this Call, and all his Parms point to the call arguments; @@ -97,12 +110,11 @@ public class CallNode extends CFGNode { Node progress = null; if( fptr()._type instanceof TypeFunPtr tfp && tfp.nargs() == nargs() ) { // If fidxs is negative, then infinite unknown functions - long fidxs = tfp.fidxs(); - if( fidxs > 0 ) { + int[] fidxs = tfp.fidxs(); + if( !XInt.isHigh(fidxs) ) { // Wipe out the return which matching in the linker table - // Walk the (63 max) bits and link - for( ; fidxs!=0; fidxs = TypeFunPtr.nextFIDX(fidxs) ) { - int fidx = Long.numberOfTrailingZeros(fidxs); + // Walk the function identities and link each possible callee. + for( int fidx=XInt.next(fidxs,-1); fidx>=0; fidx=XInt.next(fidxs,fidx) ) { TypeFunPtr tfp0 = tfp.makeFrom(fidx); FunNode fun = CodeGen.CODE.link(tfp0); if( fun!=null && !fun._folding && !linked(fun) ) @@ -166,7 +178,7 @@ public class CallNode extends CFGNode { return Parser.error( "Argument #" + i + " isa " + arg(i+2)._type + ", but must be a " + tfp.arg(i), _loc ); } - if( tfp.fidxs() < 0 ) + if( XInt.isHigh(tfp.fidxs()) ) throw Utils.TODO(); // Infinite unknown TFPs? Should be fairly precise CG return null; diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeMach.java b/src/main/java/com/seaofnodes/simple/node/EscapeMach.java new file mode 100644 index 00000000..b6ec04e9 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/EscapeMach.java @@ -0,0 +1,12 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.codegen.*; + +/** Publication orders memory; it needs no runtime instruction or register. */ +public class EscapeMach extends EscapeNode implements MachNode { + public EscapeMach(EscapeNode esc) { super(esc); _inputs.set(3,null); } + @Override public String op() { return label(); } + @Override public RegMask regmap(int i) { return null; } + @Override public RegMask outregmap() { return null; } + @Override public void encoding(Encoding enc) { } +} diff --git a/src/main/java/com/seaofnodes/simple/node/EscapeNode.java b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java new file mode 100644 index 00000000..75ecce64 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/node/EscapeNode.java @@ -0,0 +1,58 @@ +package com.seaofnodes.simple.node; + +import com.seaofnodes.simple.Parser; +import com.seaofnodes.simple.type.*; + +/** Publish one initialized field: {control, public memory, private memory, self}. + * This is an explicit construction boundary, not escape discovery. The next + * chapter will discover which objects and functions unknown code can reach. + */ +public class EscapeNode extends Node { + public Field _field; + private final Parser.Lexer _loc; + public EscapeNode(Parser.Lexer loc, Field field, Node ctrl, Node pub, Node priv, Node self) { + super(ctrl,pub,priv,self); + _field=field; + _loc=loc; + } + public EscapeNode(EscapeNode esc) { super(esc); _field=esc._field; _loc=esc._loc; } + public Node pub() { return in(1); } + public Node priv() { return in(2); } + public Node self() { return in(3); } + @Override public boolean isMem() { return true; } + @Override public String label() { return "Escape_"+_field._fname; } + + private Type value() { + return MemMergeNode.contents(priv(),_field._alias,this); + } + @Override public Type compute() { + if( in(0)._type.isHigh() || priv()._type.isHigh() || pub()._type.isHigh() ) return TypeMem.TOP; + return TypeMem.make(_field._alias,value().meet(MemMergeNode.contents(pub(),_field._alias,this)).join(_field._t)); + } + @Override public Node idealize() { + if( priv() instanceof MemMergeNode merge ) { + setDef(2,merge.alias(_field._alias)); + return this; + } + if( pub() instanceof MemMergeNode merge ) { + setDef(1,merge.alias(_field._alias)); + return this; + } + return null; + } + @Override public Parser.ParseException err() { + if( in(0)._type.isHigh() ) return null; + if( value()==Type.BOTTOM ) { + String name = self()._type instanceof TypeMemPtr p ? p._obj._name : "Object"; + return Parser.error("'"+name+"' is not fully initialized, field '"+_field._fname+"' needs to be set in a constructor",_loc); + } + return null; + } + @Override boolean _upgradeType(java.util.HashMap<String,Type> types) { + Field next = (Field)_field.upgradeType(types); + if( next==_field ) return false; + unlock(); _field=next; return true; + } + @Override public boolean eq(Node n) { return _field==((EscapeNode)n)._field; } + @Override int hash() { return _field.hashCode(); } +} diff --git a/src/main/java/com/seaofnodes/simple/node/FunNode.java b/src/main/java/com/seaofnodes/simple/node/FunNode.java index 1ba57e85..2850ba92 100644 --- a/src/main/java/com/seaofnodes/simple/node/FunNode.java +++ b/src/main/java/com/seaofnodes/simple/node/FunNode.java @@ -5,6 +5,7 @@ import com.seaofnodes.simple.codegen.CodeGen; import com.seaofnodes.simple.codegen.Encoding; import com.seaofnodes.simple.codegen.RegMask; import com.seaofnodes.simple.type.Type; +import com.seaofnodes.simple.type.TypeMem; import com.seaofnodes.simple.type.TypeFunPtr; import com.seaofnodes.simple.type.TypeTuple; import com.seaofnodes.simple.util.SB; @@ -13,6 +14,9 @@ import java.util.BitSet; import static com.seaofnodes.simple.codegen.CodeGen.CODE; public class FunNode extends RegionNode { + // Generated allocation/initializer entry points cannot be called by users. + public boolean _constructor; + // When set true, this Call/CallEnd/Fun/Return is being trivially inlined boolean _folding; @@ -29,6 +33,7 @@ public class FunNode extends RegionNode { if( fun!=null ) { _sig = fun.sig(); _name = fun._name; + _constructor = fun._constructor; } else { _sig = TypeFunPtr.BOT; _name = ""; @@ -73,6 +78,13 @@ public class FunNode extends RegionNode { // Signature can improve over time public TypeFunPtr sig() { return _sig; } + // Hidden initializer captures are discovered while parsing its body, + // before any call or function address has been made for this function. + public void addParseArg(Type type) { + Type[] args=java.util.Arrays.copyOf(_sig._sig,_sig.nargs()+1); + args[args.length-1]=type; + _sig=TypeFunPtr.make((byte)2,false,args,_sig.ret(),_sig.fidxs()); + } public void setSig( TypeFunPtr sig ) { assert sig.isa(_sig); if( _sig != sig ) { @@ -114,7 +126,8 @@ public class FunNode extends RegionNode { } // Upgrade inferred or user-written return type to actual - if( _ret!=null && _ret._type instanceof TypeTuple tt && tt.ret() != _sig.ret() ) { + if( _ret!=null && _ret._type instanceof TypeTuple tt && + !(tt.ret() instanceof TypeMem) && tt.ret() != _sig.ret() ) { setSig(_sig.makeFrom(tt.ret())); return this; } diff --git a/src/main/java/com/seaofnodes/simple/node/IfNode.java b/src/main/java/com/seaofnodes/simple/node/IfNode.java index 3f21417e..f1b76dc2 100644 --- a/src/main/java/com/seaofnodes/simple/node/IfNode.java +++ b/src/main/java/com/seaofnodes/simple/node/IfNode.java @@ -46,7 +46,7 @@ public class IfNode extends CFGNode implements MultiNode { // If constant is 0 then false branch is reachable // Else true branch is reachable if( t.isConstant() ) - return (t==Type.NIL || t==TypeInteger.ZERO || (t instanceof TypeFunPtr tfp && tfp._fidxs==0) ) ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; + return (t==Type.NIL || t==TypeInteger.ZERO || (t instanceof TypeFunPtr tfp && tfp._fidxs==com.seaofnodes.simple.type.XInt.EMPTY) ) ? TypeTuple.IF_FALSE : TypeTuple.IF_TRUE; // If adding a zero makes a difference, the predicate must not have a zero/null if( !t.makeZero().isa(t) ) return TypeTuple.IF_TRUE; diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index ff2d1138..736d91a2 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -13,6 +13,7 @@ import java.util.BitSet; * in chapter 10 this means Struct fields. */ public class LoadNode extends MemOpNode { + private final boolean _private; /** * Load a value from a ptr.field. @@ -23,9 +24,13 @@ public class LoadNode extends MemOpNode { * @param off The offset inside the struct base */ public LoadNode(Parser.Lexer loc, String name, int alias, Node mem, Node ptr, Node off) { + this(loc,name,alias,mem,ptr,off,false); + } + public LoadNode(Parser.Lexer loc, String name, int alias, Node mem, Node ptr, Node off, boolean priv) { // The field declaration will supply storage width once the receiver // is known. A parser guess must not bound the value of this Load. super(loc, name, alias, true, Type.BOTTOM, mem, ptr, off); + _private=priv; } @Override boolean canDrop(MemOpNode other, Node dep) { @@ -62,9 +67,18 @@ public class LoadNode extends MemOpNode { if( ptr.nullable() ) return Type.BOTTOM; Field field = ptr._obj.field(_name); if( field==null ) return TypeScalar.BOT; + if( field._t instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) return TypeScalar.BOT; Type t = field._t; if( t instanceof TypeConAry ary ) t=ary.elem(); if( _alias!=1 ) t=t.join(MemMergeNode.contents(mem(),_alias,this)); + // An unknown helper result does not mean the field is unwritten. + // Keep its declared bound until private memory proves otherwise; + // this Load can be forwarded into an ordinary typed value Phi. + if( uninitialized() ) t=Type.BOTTOM; + if( m instanceof TypeMem pm && pm._t instanceof TypeStruct shape ) { + Field value = shape.field(_name); + t = value==null ? Type.BOTTOM : value._t; + } if( ptr.isFinal() ) t=t.makeRO(); return t==Type.TOP ? TypeScalar.TOP : t==Type.BOTTOM ? TypeScalar.BOT : t; } @@ -87,6 +101,9 @@ public class LoadNode extends MemOpNode { } } if( _alias==1 ) return null; + // A required field has no value yet. In particular, do not turn a + // read of its calloc bytes into a legal null/zero value. + if( uninitialized() ) return null; if( mem() instanceof CastNode cast ) { setDef(1,cast.in(1)); @@ -146,6 +163,24 @@ public class LoadNode extends MemOpNode { return null; } + private boolean uninitialized() { + if( !_private || _alias==1 ) return false; + Node mem=mem(); + if( mem instanceof MemMergeNode merge ) mem=merge.alias(_alias); + return mem._type instanceof TypeMem m && + ((m._alias==_alias && m._t==Type.BOTTOM) || + (m._t instanceof TypeStruct s && s.field(_name)!=null && s.field(_name)._t==Type.BOTTOM)); + } + + @Override public Parser.ParseException err() { + if( ptr()._type instanceof TypeMemPtr ptr ) { + Field f=ptr._obj.field(_name); + if( f!=null && f._t instanceof TypeFunPtr ctor && ctor.ret() instanceof TypeMem ) + return Parser.error("A constructor is only called by new",_loc); + } + return uninitialized() ? Parser.error("Cannot read uninitialized field '"+_name+"'",_loc) : super.err(); + } + // Load a flavored zero from a New private Node zero(NewNode nnn) { TypeStruct ts = nnn._ptr._obj; @@ -165,6 +200,9 @@ public class LoadNode extends MemOpNode { switch( mem ) { case MemMergeNode merge: mem=merge.alias(_alias); break; case CastNode cast: mem=cast.in(1); break; + case EscapeNode esc: + mem = ptr==address(esc.self()) ? esc.priv() : esc.pub(); + break; case StoreNode st: // A symbolic Store may write this field. Wait for its alias; // skipping it can make a compound assignment read the old value. @@ -182,7 +220,11 @@ public class LoadNode extends MemOpNode { break; case ProjNode proj: if( !(proj.in(0) instanceof NewNode nnn) ) return null; - if( ptr instanceof ProjNode p && p.in(0)==nnn ) return nnn; + if( ptr instanceof ProjNode p && p.in(0)==nnn ) { + if( nnn.mem()==null && proj._type instanceof TypeMem m && + m._t instanceof TypeStruct shape && shape.field(_name)._t==Type.BOTTOM ) return null; + return nnn; + } if( !(ptr instanceof ProjNode p && p.in(0) instanceof NewNode) ) return null; mem=nnn.mem(); // Distinct allocations cannot overlap. break; @@ -227,7 +269,7 @@ public class LoadNode extends MemOpNode { } return folded(win).peephole(); } - LoadNode ld=new LoadNode(_loc,_name,_alias,mem,ptr,off()); + LoadNode ld=new LoadNode(_loc,_name,_alias,mem,ptr,off(),_private); ld.setDef(0,in(0)); return ld.peephole(); } @@ -260,11 +302,13 @@ public class LoadNode extends MemOpNode { // Read-Only is a deep property, and cannot be cast-away private Node castRO(Node rez) { - if( (ptr()._type.isFinal() || _declaredType.isFinal()) && !rez._type.isFinal() ) + if( (ptr()._type.isFinal() || (_declaredType instanceof TypeMemPtr p && p._ro)) && !rez._type.isFinal() ) return new ReadOnlyNode(rez).peephole(); return rez; } + @Override public boolean eq(Node n) { return _private==((LoadNode)n)._private && super.eq(n); } + // When a load bypasses a store, the store might truncate bits - and the // load will need to zero/sign-extend. private Node extend(Node val) { diff --git a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java index 7a329117..e405d152 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemMergeNode.java @@ -42,6 +42,10 @@ public class MemMergeNode extends Node { if( mem instanceof CastNode cast ) return contents(cast.in(1),alias,dep); if( mem instanceof MemMergeNode merge ) return contents(merge.alias(alias),alias,dep); + if( mem._type instanceof TypeMem mt && mt._t instanceof TypeStruct shape ) { + int index = shape.findAlias(alias); + return index==-1 ? Type.BOTTOM : shape._fields[index]._t; + } if( mem instanceof ProjNode proj && proj.in(0) instanceof NewNode nnn ) { assert proj._idx==1 && nnn.field(alias)!=null; dep.addDep(nnn); @@ -69,6 +73,17 @@ public class MemMergeNode extends Node { @Override public Type compute() { + if( in(1)!=null && in(1)._type instanceof TypeMem base && base._t instanceof TypeStruct shape ) { + // At a helper boundary, package the independent field slices for + // the call result. Constructor loops themselves carry local values. + Field[] fields=shape._fields.clone(); + for( int i=0; i<fields.length; i++ ) { + Field f=fields[i]; + Node slice=f._alias<nIns() ? in(f._alias) : null; + if( slice!=null ) fields[i]=f.makeFrom(contents(slice,f._alias,this)); + } + return TypeMem.makePrivate(TypeStruct.make(shape._name,shape._open,fields)); + } for( Node n : _inputs ) if( n != null && !n._type.isHigh() ) return TypeMem.BOT; diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 1f0fc4d3..df1585ff 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -130,7 +130,9 @@ public abstract class MemOpNode extends Node { if( visit.get(mem._nid) ) return; visit.set(mem._nid); for( Node use : mem._outputs ) { - if( use instanceof MemMergeNode merge ) { + if( use instanceof EscapeNode esc && esc._field._alias==_alias ) { + antiDeps(esc,deps,visit); + } else if( use instanceof MemMergeNode merge ) { Node slice = _alias<merge.nIns() ? merge.in(_alias) : null; if( (slice==mem) || (slice==null && merge.in(1)==mem) ) antiDeps(merge,deps,visit); diff --git a/src/main/java/com/seaofnodes/simple/node/NewNode.java b/src/main/java/com/seaofnodes/simple/node/NewNode.java index bdcdfdfc..a43efba2 100644 --- a/src/main/java/com/seaofnodes/simple/node/NewNode.java +++ b/src/main/java/com/seaofnodes/simple/node/NewNode.java @@ -8,9 +8,10 @@ import com.seaofnodes.simple.util.SB; import com.seaofnodes.simple.util.Utils; -/** Allocate a zeroed object. Inputs {ctrl, $mem, size}; - * results {ptr, $mem}. - * The memory input and result cover only the aliases in the allocated struct. +/** Allocate a zeroed object. Inputs {ctrl, null, size}; results {ptr, private memory}. + * It starts outside the public heap. Helper exits store the field values, and + * Escape publishes the completed fields. Slot 1 remains reserved for memory; + * a non-null input supports the preceding chapter's graph fixtures. */ public class NewNode extends Node implements MultiNode { @@ -22,7 +23,7 @@ public class NewNode extends Node implements MultiNode { _ptr = ptr; assert nodes.length==3; assert nodes[0]._type==Type.CONTROL || nodes[0]._type==Type.XCONTROL; - assert nodes[1]._type instanceof TypeMem; + assert nodes[1]==null || nodes[1]._type instanceof TypeMem; assert nodes[2]._type instanceof TypeInteger || nodes[2]._type==Type.NIL; } @@ -56,7 +57,7 @@ public class NewNode extends Node implements MultiNode { public TypeTuple compute() { return in(0)._type.isHigh() ? TypeTuple.make(_ptr.makeHigh(),TypeMem.TOP) - : TypeTuple.make(_ptr,TypeMem.BOT); + : TypeTuple.make(_ptr,mem()==null ? TypeMem.makePrivate(TypeMem.zeroed(_ptr._obj)) : TypeMem.BOT); } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java index 8fea803d..ce3feef2 100644 --- a/src/main/java/com/seaofnodes/simple/node/ReturnNode.java +++ b/src/main/java/com/seaofnodes/simple/node/ReturnNode.java @@ -55,7 +55,10 @@ public class ReturnNode extends CFGNode { // Upgrade signature based on return type Type ret = expr()._type; TypeFunPtr fcn = _fun.sig(); - if( ret != fcn.ret() && ret.isa(fcn.ret()) ) + // Private field contents flow on the linked Return/CallEnd edges. + // Keep the helper's interface at MemBot; a current memory snapshot + // is not a new declaration for its self type or its methods. + if( !(ret instanceof TypeMem) && ret != fcn.ret() && ret.isa(fcn.ret()) ) _fun.setSig(fcn.makeFrom(ret)); // If dead (cannot be reached; infinite loop), kill the exit values @@ -92,7 +95,7 @@ public class ReturnNode extends CFGNode { RegionNode r = (RegionNode)ctrl(); // Assert that the Phis are in particular outputs; not reordered or shuffled PhiNode mem = (PhiNode)r.out(0); assert mem.isMem(); - PhiNode rez = (PhiNode)r.out(1); assert !rez.isMem(); + PhiNode rez = (PhiNode)r.out(1); assert !rez.isMem() || fun().sig().ret() instanceof TypeMem; // Pop "inProgress" null off r ._inputs.pop(); mem._inputs.pop(); @@ -108,6 +111,7 @@ public class ReturnNode extends CFGNode { } @Override public Parser.ParseException err() { + if( expr()._type instanceof TypeMem ) return null; // Hidden initializer result. if( ctrl()._type != Type.CONTROL ) return null; // Exit path is dead if( expr()._type==TypeScalar.BOT ) { int kinds = returnKinds(expr(),new java.util.BitSet()); diff --git a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java b/src/main/java/com/seaofnodes/simple/node/ScopeNode.java index 3c1e9776..f65a822d 100644 --- a/src/main/java/com/seaofnodes/simple/node/ScopeNode.java +++ b/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<nIns(); i++ ) - dup.addDef(loop && !_vars.at(i)._final ? this : in(i)); + dup.addDef(loop && loopVar(var(i)) ? this : in(i)); return dup; } @@ -356,7 +369,7 @@ public class ScopeNode extends Node { // Fill in the backedge of any inserted Phis void _endLoop( ScopeNode scope, Node back, Node exit ) { for( int i=1; i<nIns(); i++ ) { - if( _vars.at(i)._final ) continue; // Final vars did not get modified in the loop + if( !loopVar(var(i)) ) continue; if( _vars.at(i).type().isHighOrConst() ) continue; // Cannot lift higher than a constant, so no Phi if( back.in(i) != scope ) { PhiNode phi = (PhiNode)in(i); diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index a4abaa1d..caba7bdd 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -45,6 +45,10 @@ public class StoreNode extends MemOpNode { public Type compute() { if( _alias==1 ) return TypeMem.BOT; Type val = val()._type; + // Initializing Stores are emitted at helper exits for a fresh object. + // They replace this private field; Escape later joins it with public + // memory. Keep an unwritten BOTTOM visible to the completion check. + if( _init ) return TypeMem.make(_alias,val); assert !_declaredType.isFRef(); Type t = val.join(_declaredType).meet(MemMergeNode.contents(mem(),_alias,this)); return TypeMem.make(_alias,t); @@ -72,6 +76,10 @@ public class StoreNode extends MemOpNode { return this; } + if( _init && mem() instanceof ProjNode p && p.in(0) instanceof NewNode && + val()._type.isConstant() && MemMergeNode.contents(mem(),_alias,this)==val()._type ) + return mem(); // calloc already supplied this legal default. + // Simple store-after-store on same address. Should pick up the // required init-store being stomped by a first user store. if( mem() instanceof StoreNode st && @@ -87,7 +95,9 @@ public class StoreNode extends MemOpNode { } // Value is automatically truncated by narrow store - if( val() instanceof AndNode and && and.in(2)._type.isConstant() ) { + // Private summaries describe the converted field value, so retain + // its conversion here. Public memory only needs the declared bound. + if( !_init && val() instanceof AndNode and && and.in(2)._type.isConstant() ) { int log = _declaredType.log_size(); if( log<3 ) { // And-mask vs narrow store long mask = ((TypeInteger)and.in(2)._type).value(); @@ -100,7 +110,7 @@ public class StoreNode extends MemOpNode { } // Store will chop high order bits off; math to change those bits can be dropped. - if( val() instanceof SarNode shr && + if( !_init && val() instanceof SarNode shr && shr.in(1) instanceof ShlNode shl && shr.in(2)._type.isConstant() && shl.in(2)._type.isConstant() ) { diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java index 0d5b5440..f004b0b8 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/arm/arm.java @@ -225,6 +225,7 @@ public class arm extends Machine { if( idx==1 ) return null; // Count floats in signature up to index if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence + if( tfp.arg(idx-2) instanceof TypeMem ) return null; // Hidden private memory // Count floats in signature up to index int fcnt=0; for( int i=2; i<idx; i++ ) @@ -266,7 +267,7 @@ public class arm extends Machine { @Override public long callerSave() { return CALLER_SAVE; } @Override public long neverSave() { return 1L<<RSP; } @Override public RegMask retMask( TypeFunPtr tfp ) { - return tfp.ret() instanceof TypeFloat ? D0_MASK : X0_MASK; + return tfp.ret() instanceof TypeMem ? null : tfp.ret() instanceof TypeFloat ? D0_MASK : X0_MASK; } @Override public int rpc() { return X30; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java index 7c994624..0309bfcd 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/riscv/riscv.java @@ -138,6 +138,7 @@ public class riscv extends Machine { if( idx==0 ) return RPC_MASK; if( idx==1 ) return null; if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence + if( tfp.arg(idx-2) instanceof TypeMem ) return null; // Hidden private memory // Count floats in signature up to index int fcnt=0; for( int i=2; i<idx; i++ ) @@ -178,7 +179,7 @@ public class riscv extends Machine { @Override public long callerSave() { return CALLER_SAVE; } @Override public long neverSave() { return (1L<<RSP) | (1L<<ZERO); } @Override public RegMask retMask( TypeFunPtr tfp ) { - return tfp.ret() instanceof TypeFloat ? FA0_MASK : A0_MASK; + return tfp.ret() instanceof TypeMem ? null : tfp.ret() instanceof TypeFloat ? FA0_MASK : A0_MASK; } @Override public int rpc() { return RPC; } diff --git a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java index f0598422..c854dd9d 100644 --- a/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java +++ b/src/main/java/com/seaofnodes/simple/node/cpus/x86_64_v2/x86_64_v2.java @@ -101,6 +101,7 @@ public class x86_64_v2 extends Machine { if( idx==0 ) return RPC_MASK; if( idx==1 ) return null; if( idx-2 >= tfp.nargs() ) return null; // Anti-dependence + if( tfp.arg(idx-2) instanceof TypeMem ) return null; // Hidden private memory return switch( CodeGen.CODE._callingConv ) { case "SystemV" -> callSys5 (tfp,idx,maxArgSlot); case "Win64" -> callWin64(tfp,idx,maxArgSlot); @@ -231,7 +232,7 @@ public class x86_64_v2 extends Machine { } @Override public long neverSave() { return 1L<<RSP; } @Override public RegMask retMask( TypeFunPtr tfp ) { - return tfp.ret() instanceof TypeFloat ? XMM0_MASK : RAX_MASK; + return tfp.ret() instanceof TypeMem ? null : tfp.ret() instanceof TypeFloat ? XMM0_MASK : RAX_MASK; } @Override public int rpc() { return RPC; } diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index 1396f1de..9bd85ba6 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -17,10 +17,10 @@ public class Field extends Type { public Type _t; // Unique memory alias, not sensibly part of a "type" but very convenient here. public int _alias; - // Field must be written to exactly once, no more, no less + // Field is immutable after construction; constructor locals may change public boolean _final; - // Field is final in the declaration; value is the same for all instances - // and will be moved to the class object + // Shared function declaration, with the same value for every instance. + // A final data field is still per-instance, even with a constant default. public boolean _one; private static final Ary<Field> FREE = new Ary<>(Field.class); @@ -133,4 +133,8 @@ public class Field extends Type { } @Override public String str() { return (_final?"":"!")+(_one?"$":"")+_fname; } + + @Override Type _upgradeType(java.util.HashMap<String,Type> types) { + return makeFrom(_t._upgradeType(types)); + } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java index 602aaaae..9acf5c9f 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeFunPtr.java @@ -23,24 +23,23 @@ public class TypeFunPtr extends TypeNil { public Type _ret; // TODO: boolean _open; // Extra args are true:BOTTOM, false:TOP - // Cheesy easy implementation for a small set; 1 bit per unique function - // within the same Type[]. Can be upgraded to a BitSet for larger classes - // of functions. Negative means "these 63 concrete bits plus infinite - // unknown more" - public long _fidxs; // 63 unique functions per signature + // Hidden initializers and allocators can exceed a machine word's worth + // of functions. Use the expandable sets from the later chapters, without + // adding their escape summaries or cross-file identity remapping. + public int[] _fidxs; private static final Ary<TypeFunPtr> FREE = new Ary<>(TypeFunPtr.class); - private TypeFunPtr(byte nil, boolean open, Type[] sig, Type ret, long fidxs) { super(TFUNPTR,nil); init(nil,open,sig,ret,fidxs); } - private TypeFunPtr init(byte nil, boolean open, Type[] sig, Type ret, long fidxs ) { + private TypeFunPtr(byte nil, boolean open, Type[] sig, Type ret, int[] fidxs) { super(TFUNPTR,nil); init(nil,open,sig,ret,fidxs); } + private TypeFunPtr init(byte nil, boolean open, Type[] sig, Type ret, int[] fidxs ) { assert sig != null; _nil = nil; _open = open; _sig = sig; _ret = ret; - _fidxs= fidxs; + _fidxs= XInt.intern(fidxs); return this; } - static TypeFunPtr malloc( byte nil, boolean open, Type[] sig, Type ret, long fidxs ) { + static TypeFunPtr malloc( byte nil, boolean open, Type[] sig, Type ret, int[] fidxs ) { return FREE.isEmpty() ? new TypeFunPtr(nil,open,sig,ret,fidxs) : FREE.pop().init(nil,open,sig,ret,fidxs); } @Override TypeFunPtr free(Type t) { @@ -56,7 +55,13 @@ public class TypeFunPtr extends TypeNil { @Override boolean isFree() { return _sig==null; } // All fields directly listed - public static TypeFunPtr make( byte nil, boolean open, Type[] sig, Type ret, long fidxs ) { + public static TypeFunPtr make(byte nil, boolean open, Type[] sig, Type ret, long bits) { + int[] set=bits<0 ? XInt.FULL : XInt.EMPTY; + if( bits>=0 ) for( int bit=0; bit<63; bit++ ) + if( (bits&(1L<<bit))!=0 ) set=XInt.make(set,bit); + return make(nil,open,sig,ret,set); + } + public static TypeFunPtr make( byte nil, boolean open, Type[] sig, Type ret, int[] fidxs ) { // Trim trailing args which match the implicit default. Type def = open ? Type.BOTTOM : Type.TOP; int nargs = sig.length; @@ -74,7 +79,7 @@ public class TypeFunPtr extends TypeNil { @Override TypeFunPtr makeFrom( byte nil ) { return nil ==_nil ? this : make( nil,_open,_sig,_ret, _fidxs); } public TypeFunPtr makeFrom( Type ret ) { return ret ==_ret ? this : make( _nil,_open,_sig, ret, _fidxs); } - public TypeFunPtr makeFrom( int fidx ) { return make((byte)2, _open, _sig,_ret,1L<<fidx ); } + public TypeFunPtr makeFrom( int fidx ) { return make((byte)2, _open, _sig,_ret,XInt.make(fidx) ); } public static final Type[] TEMPTY = new Type[0]; @@ -114,7 +119,7 @@ public class TypeFunPtr extends TypeNil { // Handle extra args for( int i=min._sig.length; i<_sig.length; i++ ) args[i] = _sig[i]; - return make(xmeet0(that),_open | that._open, args, _ret.meet(that._ret), _fidxs | that._fidxs); + return make(xmeet0(that),_open | that._open, args, _ret.meet(that._ret), XInt.meet(_fidxs,that._fidxs)); } static Type[] xmeet( Type[] ts0, Type[] ts1) { if( ts0==ts1 ) return ts0; @@ -125,7 +130,7 @@ public class TypeFunPtr extends TypeNil { return ts; } - @Override TypeFunPtr xdual() { return malloc(dual0(), !_open, xdual(_sig), _ret.dual(), ~_fidxs); } + @Override TypeFunPtr xdual() { return malloc(dual0(), !_open, xdual(_sig), _ret.dual(), XInt.dual(_fidxs)); } static Type[] xdual(Type[] ts) { Type[] dual = new Type[ts.length]; for( int i=0; i<ts.length; i++ ) @@ -137,7 +142,7 @@ public class TypeFunPtr extends TypeNil { if( _dual!=null ) return dual(); assert !_terned; Type[] sigs = new Type[_sig.length]; - TypeFunPtr d = malloc(dual0(),!_open,sigs,null,~_fidxs); + TypeFunPtr d = malloc(dual0(),!_open,sigs,null,XInt.dual(_fidxs)); (_dual = d)._dual = this; // Cross link duals // Return rdual d._ret = _ret._terned ? _ret.dual() : _ret.rdual(); @@ -150,9 +155,9 @@ public class TypeFunPtr extends TypeNil { // RHS is NIL; do not deep-dual when crossing the centerline @Override public Type meet0() { return _nil==3 ? this : make((byte)3,_open,_sig,_ret,_fidxs); } - @Override public boolean isHigh() { return _nil <= 1 || (_nil==2 && _fidxs==0); } + @Override public boolean isHigh() { return _nil <= 1 || (_nil==2 && _fidxs==XInt.EMPTY); } - @Override public boolean _isConstant() { return (_nil==2 && Long.bitCount(_fidxs)==1) || (_nil==3 && _fidxs==0); } + @Override public boolean _isConstant() { return (_nil==2 && XInt.isConstant(_fidxs)) || (_nil==3 && _fidxs==XInt.EMPTY); } @Override boolean _isFinal() { return true; } @Override boolean _isGLB(boolean mem) { return true; } @@ -171,13 +176,13 @@ public class TypeFunPtr extends TypeNil { @Override public int log_size() { return 2; } // (1<<2)==4-byte pointers public Type arg(int i) { return _sig[i]; } - public long fidxs() { return _fidxs; } + public int[] fidxs() { return _fidxs; } public Type ret() { return _ret; } public int nargs() { return _sig.length; } - public int fidx() { assert Long.bitCount(_fidxs)==1; return Long.numberOfTrailingZeros(_fidxs); } + public int fidx() { assert XInt.isConstant(_fidxs); return XInt.onlyBit(_fidxs); } public int nfcns() { - if( _fidxs < 0 ) return Integer.MAX_VALUE; // Infinite choices - return Long.bitCount(_fidxs); + if( XInt.isHigh(_fidxs) ) return Integer.MAX_VALUE; // Infinite choices + return XInt.bitCount(_fidxs); } @@ -193,7 +198,7 @@ public class TypeFunPtr extends TypeNil { @Override int hash() { - long hash = _ret.hashCode() ^ _fidxs ^ super.hash(); + long hash = _ret.hashCode() ^ XInt.hash(_fidxs) ^ super.hash(); for( Type arg : _sig ) hash = hash*19 ^ arg.hashCode(); return Utils.fold(hash); @@ -255,16 +260,13 @@ public class TypeFunPtr extends TypeNil { } String printFIDX() { String tilde = isHigh() ? "~" : ""; - long fidxs = isHigh() ? ~_fidxs : _fidxs; - String fidx = fidxs==0 ? "" - : Long.bitCount(fidxs) == 1 ? ""+Long.numberOfTrailingZeros(fidxs) - : fidxs == -1 ? "ALL" - : "b"+Long.toBinaryString(fidxs); // Just some function bits + int[] fidxs = isHigh() ? XInt.dual(_fidxs) : _fidxs; + String fidx = fidxs==XInt.EMPTY ? "" : XInt.isConstant(fidxs) ? ""+XInt.onlyBit(fidxs) + : fidxs==XInt.FULL ? "ALL" : XInt.str(fidxs); return tilde+fidx; } - // Usage: for( long fidxs=fidxs(); fidxs!=0; fidxs=nextFIDX(fidxs) ) { int fidx = Long.numberOfTrailingZeros(fidxs); ... } - public static long nextFIDX(long fidxs) { return fidxs & (fidxs-1); } + @Override Type _upgradeType(java.util.HashMap<String,Type> types) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index 02cfc57b..5539e1cf 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -8,21 +8,22 @@ import java.util.BitSet; /** - * Represents a slice of memory corresponding to a set of aliases + * Public memory holds one field alias; private memory holds one whole object. */ public class TypeMem extends Type { // Which slice of memory? // 1 and TOP means no slice. // 1 and BOT means all memory. + // 1 and TypeStruct means current fields of the private allocation. // N means alias slice#N. public int _alias; - public Type _t; // Memory contents, some scalar type + public Type _t; // Scalar public contents, or private field values. private static final Ary<TypeMem> FREE = new Ary<>(TypeMem.class); private TypeMem(int alias, Type t) { super(TMEM); init(alias,t); } private TypeMem init(int alias, Type t) { - assert alias>1 || (t==Type.TOP || t==Type.BOTTOM); + assert alias>1 || (t==null || t==Type.TOP || t==Type.BOTTOM || t instanceof TypeStruct); _alias = alias; _t = t; return this; @@ -47,10 +48,34 @@ public class TypeMem extends Type { return VISIT.isEmpty() ? f2.free(f) : f2.delayFree(f); } + // Private memory describes one allocation. It is passed explicitly to + // initializers; it never joins the public heap until EscapeNode. + public static TypeMem makePrivate(TypeStruct shape) { return make(1,shape); } + + public static TypeStruct empty(TypeStruct shape) { + Field[] fields = new Field[shape._fields.length]; + for( int i=0; i<fields.length; i++ ) + fields[i] = shape._fields[i].makeFrom(Type.BOTTOM); + return TypeStruct.make(shape._name,shape._open,fields); + } + + public static TypeStruct zeroed(TypeStruct shape) { + Field[] fields=new Field[shape._fields.length]; + for( int i=0; i<fields.length; i++ ) { + Field f=shape._fields[i]; + Type zero=f._t.makeZero(); + fields[i]=f.makeFrom(!f._final && f._t!=Type.BOTTOM && zero.isa(f._t) ? zero : Type.BOTTOM); + } + return TypeStruct.make(shape._name,shape._open,fields); + } + public static final TypeMem TOP = make(1, Type.TOP ); public static final TypeMem BOT = make(1, Type.BOTTOM); - public static void gather(ArrayList<Type> ts) { ts.add(make(2,Type.NIL)); ts.add(make(2,TypeInteger.ZERO)); ts.add(BOT); } + public static void gather(ArrayList<Type> ts) { + ts.add(make(2,Type.NIL)); ts.add(make(2,TypeInteger.ZERO)); ts.add(BOT); + ts.add(makePrivate(TypeStruct.TEST)); ts.add(makePrivate(empty(TypeStruct.TEST))); + } @Override TypeMem xmeet(Type t) { @@ -82,8 +107,8 @@ public class TypeMem extends Type { @Override public boolean isHigh() { return _t.isHigh(); } @Override public int log_size() { throw Utils.TODO(); } @Override boolean _isFinal() { return _t._isFinal(); } - @Override boolean _isGLB(boolean mem) { return _t._isGLB(true); } - @Override public Type _glb(boolean mem) { return make(_alias,_t._glb(true)); } + @Override boolean _isGLB(boolean mem) { return _t instanceof TypeStruct s ? s.isGLB2() : _t._isGLB(true); } + @Override public Type _glb(boolean mem) { return make(_alias,_t instanceof TypeStruct s ? s.glb2() : _t._glb(true)); } @Override int hash() { return 9876543 + _alias + _t.hashCode(); } @@ -112,6 +137,18 @@ public class TypeMem extends Type { @Override public String str() { return toString(); } @Override Type _upgradeType(java.util.HashMap<String,Type> types) { + if( _t instanceof TypeStruct old && types.get(old._name) instanceof TypeMemPtr ptr ) { + // This struct records current contents, not a forward declaration. + // Complete its field list without replacing writes with declared + // types (or turning an unwritten field into an initialized one). + TypeStruct shape=old.isAry() ? old : ptr._obj; + Field[] fields=new Field[shape._fields.length]; + for( int i=0; i<fields.length; i++ ) { + Field field=shape._fields[i], value=old.field(field._fname); + fields[i]=field.makeFrom(value==null ? Type.BOTTOM : value._t._upgradeType(types)); + } + return makePrivate(TypeStruct.make(shape._name,shape._open,fields)); + } return make(_alias,_t._upgradeType(types)); } } diff --git a/src/main/java/com/seaofnodes/simple/type/XInt.java b/src/main/java/com/seaofnodes/simple/type/XInt.java new file mode 100644 index 00000000..17fc4bd3 --- /dev/null +++ b/src/main/java/com/seaofnodes/simple/type/XInt.java @@ -0,0 +1,241 @@ +package com.seaofnodes.simple.type; + +import com.seaofnodes.simple.util.*; +import java.lang.Integer; +import java.util.Arrays; + +// Stupidly overkill interned immutable int[]'s +public abstract class XInt { + private static final Ary<Ary<int[]>> FREES = new Ary(Ary.class); + private static final Ary<Ary<int[]>> INTERNS = new Ary(Ary.class); + private static int PROBES, HITS, NEWS; + + public static final int[] EMPTY = intern(new int[]{0, 0}); + public static final int[] FULL = intern(new int[]{0,-1}); + public static final int[] SET1 = make(1); + public static final int[] SET3 = make(SET1, 2); + + static int idx(int x) { return (x>>5)+1; } + static int mask(int x) { return 1<<(x&31); } + + // No hash set, still mutable + public static boolean isMutable(int[] xs) { return xs[0]==0; } + // Return hash code; must be set hence frozen + public static int hash(int[] xs) { return xs[0]; } + + // High bit set (infinite 1's extension) + public static boolean isHigh(int[] xs) { return xs[xs.length-1] < 0; } + + // Check for a bit + public static boolean bit(int[] xs, int x) { + int idx = idx(x); + if( idx >= xs.length ) + return isHigh(xs); + return (xs[idx] & mask(x))!=0; + } + + // Number of bits set + public static int bitCount(int[] xs) { + assert !isHigh(xs); // Dont ask if infinite + int cnt=0; + for( int i=1; i<xs.length; i++ ) + cnt += Integer.bitCount(xs[i]); + return cnt; + } + + // Largest bit + public static int max(int[] xs) { + assert !isHigh(xs); + return Integer.numberOfTrailingZeros(xs[xs.length-1])+((xs.length-1-1)<<5); + } + + // Has 1 bit set + public static boolean isConstant(int[] xs) { return !isHigh(xs) && bitCount(xs)==1; } + // Return the 1 set bit or assert + public static int onlyBit(int[] xs) { + assert isConstant(xs); + for( int i=1; i<xs.length; i++ ) + if( xs[i] != 0 ) + return Integer.numberOfTrailingZeros(xs[i]) + ((i-1)<<5); + throw Utils.TODO("Should not reach here"); + } + + // Subset check: ys is a subset of xs + public static boolean subset(int[] xs, int[] ys) { + assert !isMutable(ys); + if( xs==ys ) return true; + if( xs==FULL ) return true; + if( ys==EMPTY ) return true; + int min = Math.min(xs.length,ys.length); + for( int i=1; i<min; i++ ) + if( (xs[i] | ys[i])!=xs[i] ) + return false; + if( xs.length == ys.length ) + return true; + if( ys.length < xs.length ) + return !isHigh(ys); // If ys is infinite, it'll hit one of the xs extra zeros + return isHigh(xs); + } + + + // Construct a set with 1 bit set + public static int[] make(int x ) { return make(EMPTY,x); } + + // Add a bit + public static int[] make(int[] xs, int x ) { + assert !isMutable(xs); + int idx = idx(x); + if( idx >= xs.length && isHigh(xs) ) + return xs; // Set in the default infinite + if( idx < xs.length && (mask(x) & xs[idx])!=0 ) + return xs; // Already set + int len = Math.max(xs.length,idx+1); + if( (x&31)==31 && idx+1==len ) + len++; + int[] ys = free(len); + System.arraycopy(xs,1,ys,1,xs.length-1); + ys[idx] |= mask(x); + return intern(ys); + } + + // Interning, and life-cycle management + // Intern the array + public static int[] intern(int[] xs) { + if( !isMutable(xs) ) return xs; // Already interned + PROBES++; + + // Trim trailing 0s or -1s, use the infinite extend bit + int len = xs.length; + while( len > 2 && + ((xs[len-1]== 0 && xs[len-2]>=0) || + (xs[len-1]== -1 && xs[len-2]< 0) ) ) + len--; + // Replace with trimmed + if( len < xs.length ) { + var ys = free(len); + System.arraycopy(xs,1,ys,1,len-1); + xs = _free(xs,ys); + } + + // Compute lame hash code + int hash = 0; + for( int i=1; i<len; i++ ) + hash += xs[i]; + if( hash == 0 ) hash = 0xCAFEBABE; + xs[0] = hash; // Set lame hashcode, and mark immutable + + // Get length-specific INTERN table + var xss = INTERNS.atX(len); + if( xss==null ) + INTERNS.setX( xs.length, xss = new Ary<>(int[].class)); + + // Probe for a hit + for( int[] ys : xss ) + if( Arrays.equals(xs,ys) ) // Hit! + // Free new array and return old array + { HITS++; return _free(xs,ys); } + + // Intern new array and return + return xss.push(xs); + } + + // Return Ary of free int[]s of fixed size + private static Ary<int[]> _xss(int len) { + Ary<int[]> xss = FREES.atX(len); + if( xss==null ) + FREES.setX(len, xss = new Ary<>(int[].class)); + return xss; + } + // Pull free array from free list + static int[] free(int len) { + int[] xs = _xss(len).pop(); + if( xs==null ) + { NEWS++; xs = new int[len]; } + assert isMutable(xs); + return xs; + } + // Return ys. Put xs on free list + static int[] _free(int[] xs, int[] ys) { + Arrays.fill(xs,0); // Mutable again + _xss(xs.length).push(xs); + return ys; + } + + // Meet: Set union + public static int[] meet(int[] xs, int[] ys) { + if( xs==ys ) return xs; + boolean isX=true, isY=true; + int min = Math.min(xs.length,ys.length); + int max = Math.max(xs.length,ys.length); + for( int i=1; i<max; i++ ) { + int x = i < xs.length ? xs[i] : isHigh(xs) ? -1 : 0; + int y = i < ys.length ? ys[i] : isHigh(ys) ? -1 : 0; + if( (x | y)!=x ) isX=false; + if( (x | y)!=y ) isY=false; + } + if( isX ) return xs; + if( isY ) return ys; + // Get a free one + int[] ms = free(max); + for( int i=1; i<min; i++ ) + ms[i] = xs[i] | ys[i]; + for( int i=min; i<ms.length; i++ ) { + int x = i < xs.length ? xs[i] : isHigh(xs) ? -1 : 0; + int y = i < ys.length ? ys[i] : isHigh(ys) ? -1 : 0; + ms[i] = x | y; + } + return intern(ms); + } + + // Dual: flip all the bits + public static int[] dual(int[] xs) { + int[] ds = free(xs.length); + for( int i=1; i<xs.length; i++ ) + ds[i] = ~xs[i]; + return intern(ds); + } + + + // Next set bit, or -1 + // for( int bit = XInt.next(bits,-1); bit >=0; bit = XInt.next(bits,bit) ) {...bit...} + public static int next(int[] xs, int x) { + assert !isHigh(xs); // No iterating infinite bitsets + x++; // Skip current + for( ; !bit(xs,x); x++ ) + if( idx(x)>=xs.length ) + return -1; + return x; + } + + public static String str(int[] xs) { return str(new SB(),xs).toString(); } + public static SB str(SB sb, int[] xs) { + sb.p("[ "); + // Printing ranges; + // 1,2,3 prints 1-3 + // 1,2,4 prints 1,2,4 + // + int max = (xs.length-1)<<5; + int low = -1; // No low range; function identity 0 is main here. + for( int i=0; i<max; i++ ) { + if( bit(xs,i) ) { // Set bit, start or extend range + if( low==-1 ) low=i; // No range, start one + } else { // Break in sequence, ending a range + range(sb,low,i-1); // Print prior range, and start new one + low=-1; // Reset range + } + } + // Print any partial range + range(sb,low,max-1).unchar(); + if( isHigh(xs) ) + sb.p(",..."); + return sb.p("]"); + } + + private static SB range( SB sb, int low, int mid ) { + if( low==-1 ) ; + else if( low==mid ) sb.p(low).p(','); + else if( low==mid-1 ) sb.p(low).p(',').p(mid).p(','); + else sb.p(low).p('-').p(mid).p(','); + return sb; + } +} diff --git a/src/test/java/com/seaofnodes/simple/Chapter09Test.java b/src/test/java/com/seaofnodes/simple/Chapter09Test.java index 50410618..f24d96eb 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter09Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter09Test.java @@ -255,7 +255,7 @@ return 0!=0; int v0=0; while(0==1) while(v0) v0=1+v0; -return 0; +return 0; """); code.driver(CodeGen.Phase.FinalizeIR); assertEquals("return 0;", code.print()); diff --git a/src/test/java/com/seaofnodes/simple/Chapter17aTest.java b/src/test/java/com/seaofnodes/simple/Chapter17aTest.java index d03248c2..64ecb235 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter17aTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter17aTest.java @@ -73,7 +73,7 @@ return p; public void testStructFinal3() { for( String fields : new String[] { "var x; var y;", "int[] !x;", "int[] !x;" } ) { String src = "struct Point { "+fields+" }; Point p = new Point; p.x++; return p;"; - try { new CodeGen(src).driver(CodeGen.Phase.FinalizeIR); fail(fields); } + try { new CodeGen(src).driver(CodeGen.Phase.TypeCheck); fail(fields); } catch( Exception e ) { assertEquals("'Point' is not fully initialized, field 'x' needs to be set in a constructor",e.getMessage()); } } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java index d2fa40f3..3fbf0daa 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter17bTest.java +++ b/src/test/java/com/seaofnodes/simple/Chapter17bTest.java @@ -289,7 +289,7 @@ A x = new A { b = new B; }; """); - try { code.driver(CodeGen.Phase.FinalizeIR); fail(); } + try { code.driver(CodeGen.Phase.TypeCheck); fail(); } catch( Exception e ) { assertEquals("Cannot read uninitialized field 'b'",e.getMessage()); } } @@ -302,7 +302,7 @@ return new A { if (arg) b = new B; // Constructor ends with partial init of b }.b; """); - try { code.parse(); fail(); } + try { code.driver(CodeGen.Phase.TypeCheck); fail(); } catch( Exception e ) { assertEquals("'A' is not fully initialized, field 'b' needs to be set in a constructor",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter18Test.java b/src/test/java/com/seaofnodes/simple/Chapter18Test.java index 4927f7e2..a8cf3f11 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter18Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter18Test.java @@ -223,7 +223,7 @@ var fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(3); """); code.driver(CodeGen.Phase.FinalizeIR); - assertEquals("Stop[ return #2; return (Parm_x($fun21,i64)*x); return (Parm_x($fun22,i64)<<1); ]", code._stop.toString()); + assertEquals("Stop[ return #2; return (Parm_x($fun35,i64)*x); return (Parm_x($fun36,i64)<<1); ]", code._stop.toString()); assertEquals("6", Eval2.eval(code, 0)); assertEquals("9", Eval2.eval(code, 1)); } @@ -359,7 +359,7 @@ for(;;) { return 0; """); try { code.driver(CodeGen.Phase.TypeCheck); fail(); } - catch( Exception e ) { assertEquals("Might be null calling { i64 -> i64 #21}?",e.getMessage()); } + catch( Exception e ) { assertEquals("Might be null calling { i64 -> i64 #35}?",e.getMessage()); } } diff --git a/src/test/java/com/seaofnodes/simple/Chapter19Test.java b/src/test/java/com/seaofnodes/simple/Chapter19Test.java index 41ec6cef..88155e5b 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter19Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter19Test.java @@ -15,7 +15,7 @@ import static org.junit.Assert.*; public class Chapter19Test { @Test public void testPrintingFunctionLookup() { var code = new CodeGen("return 0;").parse(); - var tfp = TypeFunPtr.make((byte)2,false,new Type[]{TypeInteger.constant(987654)},TypeInteger.constant(123456),1L<<30); + var tfp = TypeFunPtr.make((byte)2,false,new Type[]{TypeInteger.constant(987654)},TypeInteger.constant(123456),XInt.make(1000)); var con = new ConstantNode(tfp); var call = new CallNode(null,code._start,con,con); // Diagnostic lookup may construct/intern the return-erased linker key. @@ -415,7 +415,7 @@ val fcn = arg ? { int x -> x*x; } : { int x -> x+x; }; return fcn(2)*10 + fcn(3); """); code.driver(Phase.LocalSched,"x86_64_v2", "SystemV"); - assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun21,i64),x); return (shli,Parm_x($fun22,i64)); ]", code.print()); + assertEquals("Stop[ return (add,#2,(muli,#2)); return (mul,Parm_x($fun35,i64),x); return (shli,Parm_x($fun36,i64)); ]", code.print()); } @Test @@ -443,8 +443,7 @@ return sq(arg) + sq(3); assertTrue(n.in(0) instanceof CFGNode); if( n instanceof NewNode nn ) { assertEquals(2,((TypeTuple)nn._type)._types.length); - assertTrue(nn.mem() instanceof MemMergeNode); - assertNull(nn.mem().in(1)); // Partial allocation input. + assertNull(nn.mem()); // The allocation starts with private memory. nn.cacheRegs(code); MachNode mach = (MachNode)nn; assertNull(mach.regmap(1)); diff --git a/src/test/java/com/seaofnodes/simple/Chapter20Test.java b/src/test/java/com/seaofnodes/simple/Chapter20Test.java index fe69e5ad..4800b180 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter20Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter20Test.java @@ -199,7 +199,8 @@ for( int i=0; i<ary#-1; i++ ) ary[i+1] += ary[i]; return ary[1] * 1000 + ary[3]; // 1 * 1000 + 6 """; - testTarget(src,"x86_64_v2", "SystemV",5,"return .[];"); + // Array publication changes memory scheduling and the live ranges. + testTarget(src,"x86_64_v2", "SystemV",7,"return .[];"); testTarget(src,"riscv" , "SystemV",7,"return (add,.[],(mul,.[],1000));"); testTarget(src,"arm" , "SystemV",5,"return (add,.[],(mul,.[],1000));"); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter23Test.java b/src/test/java/com/seaofnodes/simple/Chapter23Test.java index 1dd21d08..22be3af1 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter23Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter23Test.java @@ -115,7 +115,7 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 0; - + if(a++ || b++ ) { if(b == 0 && a == 2) { sys.io.p("Or"); @@ -149,7 +149,7 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 1; - + if(a && b) { sys.io.p("And"); } else { @@ -186,14 +186,14 @@ var apply = { i64 x, { i64 -> u32 } fcn -> String src2 = """ struct S { !S? !fld; }; - + val ptr = arg == 1 ? null : new S{fld = arg==1 ? null : new S{fld = null;};}; if( ptr && ptr.fld ) { sys.io.p("true"); } else { sys.io.p("false"); } - + return 0; """; CodeGen code = new CodeGen(src).driver(CodeGen.Phase.TypeCheck); @@ -221,13 +221,13 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 1; - + int x=1; int y=1; int z=0; - + int g = x++ && y++ && z++; - + if(x == 2 && y == 2 && z == 1 && g == 0) { sys.io.p("Effected"); } else { @@ -259,13 +259,13 @@ var apply = { i64 x, { i64 -> u32 } fcn -> """ int a = 1; int b = 1; - + int x = -1; int y=1; int z= -1; - + int g = x++ || y++ || z++; - + int switch = 0; if(x == 4 || y == 4 || z == 4) { switch = -1; @@ -305,11 +305,11 @@ var apply = { i64 x, { i64 -> u32 } fcn -> // -*- mode: java; -*- int a = 1; int b = 1; - + var sq = { int x -> x*x; }; - + if(a && sq(0)) { sys.io.p("And"); } else { diff --git a/src/test/java/com/seaofnodes/simple/ConstructionTest.java b/src/test/java/com/seaofnodes/simple/ConstructionTest.java new file mode 100644 index 00000000..a3317d09 --- /dev/null +++ b/src/test/java/com/seaofnodes/simple/ConstructionTest.java @@ -0,0 +1,115 @@ +package com.seaofnodes.simple; + +import com.seaofnodes.simple.codegen.CodeGen; +import com.seaofnodes.isa.eval.EvalArm64; +import com.seaofnodes.isa.eval.EvalRisc5; +import org.junit.Test; +import static org.junit.Assert.*; + +public class ConstructionTest { + @Test public void testConditionalConstructorLoop() { + String[] bodies = { + "while(n--) if(n) x=1;", + "for(int i=0;i<n;i++) { if(i==1) continue; if(i==3) break; x+=i+1; }" + }; + int[][] expected = {{0,0,1,1,1,1}, {0,1,1,4,4,4}}; + for( int i=0; i<bodies.length; i++ ) + for( long seed : new long[]{123,456,789} ) { + String src = "struct C { int x; new C={int n -> "+bodies[i]+"}; }; return new C(arg).x;"; + var code = new CodeGen(src,com.seaofnodes.simple.type.TypeInteger.BOT,seed,true) + .driver(CodeGen.Phase.TypeCheck); + for( int arg=0; arg<expected[i].length; arg++ ) + assertEquals("case="+i+" seed="+seed+" arg="+arg, + Integer.toString(expected[i][arg]),Eval2.eval(code,arg)); + } + } + + private static final String CONSTRUCT = """ + struct Box { + int x=7; + int[] data; + new Box = { int n -> + data=new int[2]; + x=n; + data[0]=x+1; + }; + val get = { -> x+data[0]; }; + }; + val a=new Box(arg); + val b=new Box(arg+10); + return a.get()*100+b.get(); + """; + + @Test public void testConstructorCalls() throws java.io.IOException { + var code=new CodeGen(CONSTRUCT).driver(CodeGen.Phase.FinalizeIR); + assertEquals("525",Eval2.eval(code,2)); + for( String cpu : new String[]{"arm","riscv"} ) { + code=new CodeGen(CONSTRUCT).driver(cpu,"SystemV",null); + byte[] memory=new byte[1<<20]; + byte[] bits=code._encoding.bits(); + System.arraycopy(bits,0,memory,0,bits.length); + if( cpu.equals("arm") ) { + EvalArm64 eval=new EvalArm64(memory,1<<16); + eval.regs[0]=2; + assertEquals(0,eval.step(10000)); + assertEquals(525,eval.regs[0]); + } else { + EvalRisc5 eval=new EvalRisc5(memory,1<<16); + eval.regs[10]=2; + assertEquals(0,eval.step(10000)); + assertEquals(525,eval.regs[10]); + } + } + // Field updates are local SSA values, including the old x used after + // updating y and x. Only constructor exits should write these fields. + String counter="struct Counter { int x; int y; int z; new Counter={int n -> while(x<n) { int old=x; y=x+1; x=y+1; z=old; }}; }; val c=new Counter(arg); return c.x*100+c.z;"; + var loop=new CodeGen(counter) + .driver(CodeGen.Phase.LocalSched); + assertEquals("0",Eval2.eval(loop,0)); + assertEquals("2018",Eval2.eval(loop,19)); + loop._stop.walk(n -> { + if( n instanceof com.seaofnodes.simple.node.StoreNode st ) + assertEquals("Constructor Stores belong outside the loop",0,st.cfg0().loopDepth()); + return null; + }); + var defaults=new CodeGen("struct Buffer { int[] data=new int[1]; }; val a=new Buffer; val b=new Buffer; a.data[0]=7; return b.data[0];") + .driver(CodeGen.Phase.TypeCheck); + assertEquals("0",Eval2.eval(defaults,0)); + java.nio.file.Path dir=java.nio.file.Path.of("build/objs"); + java.nio.file.Files.createDirectories(dir); + java.nio.file.Files.writeString(dir.resolve("construction.smp"),"val construct={int arg ->"+CONSTRUCT+"}; val count={int arg ->"+counter+"};"); + java.nio.file.Files.writeString(dir.resolve("construction.c"),""" + extern long long construct(long long); + extern long long count(long long); + int main(void) { return construct(2)!=525 || construct(0)!=121 || count(19)!=2018 || count(0)!=0; } + """); + TestC.run("build/objs","construction","",-1); + } + + @Test public void testCompletionBeforePublication() { + String src="struct Box { int[] data; new Box={int n -> if(n) data=new int[2];}; }; return new Box(arg);"; + try { new CodeGen(src).driver(CodeGen.Phase.TypeCheck); fail(); } + catch( Parser.ParseException e ) { + assertEquals("'Box' is not fully initialized, field 'data' needs to be set in a constructor",e.getMessage()); + } + for( String early : new String[]{ + "val use={!Box b -> b.x;}; struct Box { int x; new Box={->use(self);}; }; return new Box;", + "struct Box { Box? next; new Box={->next=self;}; }; return new Box;", + "struct Wrap { Box? item; }; struct Box { new Box={->new Wrap { item=self; };}; }; return new Box;" + } ) { + try { new CodeGen(early).driver(CodeGen.Phase.TypeCheck); fail(); } + catch( Parser.ParseException e ) { + assertEquals("Cannot publish self before the constructor finishes",e.getMessage()); + } + } + } + + @Test public void testForwardMethod() { + var code=new CodeGen("val run={!Box b -> b.get();}; struct Box { int x=7; val get={->x;}; }; return run(new Box);") + .driver(CodeGen.Phase.FinalizeIR); + assertEquals("7",Eval2.eval(code,0)); + code=new CodeGen("struct Byte { new Byte={int n -> self.x=n; self.x+=3;}; u8 x; }; return new Byte(255).x;") + .driver(CodeGen.Phase.FinalizeIR); + assertEquals("2",Eval2.eval(code,0)); + } +} diff --git a/src/test/java/com/seaofnodes/simple/Eval2.java b/src/test/java/com/seaofnodes/simple/Eval2.java index 58b3b74e..b32a5175 100644 --- a/src/test/java/com/seaofnodes/simple/Eval2.java +++ b/src/test/java/com/seaofnodes/simple/Eval2.java @@ -278,7 +278,8 @@ public abstract class Eval2 { case ProjNode proj -> proj._type instanceof TypeMem ? "$mem" : val(proj.in(0)); case ReadOnlyNode read -> val(read.in(1)); case SarNode sar -> x(sar.in(1)) >> x(sar.in(2)); - case MemMergeNode merge-> "$mem"; + case EscapeNode esc -> "$mem"; + case MemMergeNode merge-> "$mem"; case ShlNode shl -> x(shl.in(1)) << x(shl.in(2)); case ShrNode shr -> x(shr.in(1)) >>>x(shr.in(2)); case StoreNode st -> store(st); diff --git a/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java b/src/test/java/com/seaofnodes/simple/FinalConstructionTest.java new file mode 100644 index 00000000..e91dc384 --- /dev/null +++ b/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; i<n; i++) x=step(x); + }; + val get={->x;}; + }; + 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<n;i++) self.x*=2;}; }; return new C(arg).x;", + "struct C { val x=1; new C={int n -> for(int i=0;i<n;i++) ++x;}; }; return new C(arg).x;", + "struct C { val x=1.5; new C={->x=2.5;}; }; return new C().x;", + "struct C { val x=\"a\"; new C={int n -> for(int i=0;i<n;i++) x=\"b\";}; }; return new C(arg).x[0];", + "struct C { val x=new int[1]; new C={->x=new int[2]; x=new int[3];}; }; return new C().x#;" + }; + String[] results={"2","8","4","2.5","98","3"}; + for( int i=0; i<sources.length; i++ ) + assertEquals(results[i],Eval2.eval(new CodeGen(sources[i]).driver(CodeGen.Phase.TypeCheck),3)); + + String[] rejected={ + "struct C { val x=1; }; val c=new C(); c.x=2; return c.x;", + "struct C { new C={->val 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); + } +} diff --git a/src/test/java/com/seaofnodes/simple/MergeSortTest.java b/src/test/java/com/seaofnodes/simple/MergeSortTest.java index 324790a0..453bd35c 100644 --- a/src/test/java/com/seaofnodes/simple/MergeSortTest.java +++ b/src/test/java/com/seaofnodes/simple/MergeSortTest.java @@ -17,13 +17,13 @@ public class MergeSortTest { @Test public void testMergeSort0() throws IOException { // Test merge sort on a small array of primes String src = -""" +""" val merge_sort = { int[] a -> int[] !b = new int[a#]; copy_array (a, 0, a#, b); split_merge(a, 0, a#, b); }; - + val split_merge = { int[] !b, int begin, int end, int[] a -> if (end - begin <= 1) return 0; @@ -33,10 +33,10 @@ public class MergeSortTest { merge(b, begin, middle, end, a); return 0; }; - + val merge = { int[] !b, int begin, int middle, int end, int[] a -> int i = begin, j = middle; - + for (int k = begin; k < end; k++) { // && and || bool cond = false; @@ -48,7 +48,7 @@ public class MergeSortTest { else b[k] = a[j++]; } }; - + val copy_array = { int[] !a, int begin, int end, int[] b -> for (int k = begin; k < end; k++) b[k] = a[k]; diff --git a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java index 20aac367..3f4613ff 100644 --- a/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java +++ b/src/test/java/com/seaofnodes/simple/evaluator/Evaluator.java @@ -306,6 +306,7 @@ public class Evaluator { case NewNode alloc -> alloc(alloc); case CProjNode cproj -> ((Object[])val(cproj.ctrl()))[cproj._idx]; case ProjNode proj -> ((Object[])val( proj.in(0) ))[ proj._idx]; + case EscapeNode esc -> null; case MemMergeNode mem -> null; case ReadOnlyNode ro -> val(ro.in(1)); case CallNode call -> Utils.TODO(); // should not reach here, go the IfNode route |
