From c54580d2b2685829dab0976ed8c2bcae59322f69 Mon Sep 17 00:00:00 2001 From: Cliff Click Date: Wed, 17 Jul 2024 18:11:56 +0100 Subject: Chapter 12: References MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Co-authored-by: Hsiang-Ying Fu <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: Dibyendu Majumdar Co-authored-by: Thalia Archibald Co-authored-by: tannal Co-authored-by: hadha Co-authored-by: fuhsnn <66062782+fuhsnn@users.noreply.github.com> Co-authored-by: XmiliaH <45106915+XmiliaH@users.noreply.github.com> Co-authored-by: Tamás Hadházy <85063808+Hels15@users.noreply.github.com> Co-authored-by: Symious <14933944+symious@users.noreply.github.com> Co-authored-by: RobertObkircher Co-authored-by: Robert Obkircher Co-authored-by: Jun Kawasaki Co-authored-by: Claude Opus 5 --- README.ja.md | 2 +- README.md | 2 +- chapter11.iml | 28 --- chapter12.iml | 28 +++ docs/chapter12/12-grammar.ja.md | 136 ++++++++++++++ docs/chapter12/12-grammar.md | 132 ++++++++++++++ docs/chapter12/Makefile | 12 ++ docs/chapter12/README.ja.md | 101 +++++++++++ docs/chapter12/README.md | 150 ++++++++++++++++ src/main/java/com/seaofnodes/simple/Parser.java | 127 +++++++------ .../java/com/seaofnodes/simple/node/AddNode.java | 5 + .../java/com/seaofnodes/simple/node/LoadNode.java | 6 +- .../java/com/seaofnodes/simple/node/MemOpNode.java | 9 +- .../java/com/seaofnodes/simple/node/MulNode.java | 5 + src/main/java/com/seaofnodes/simple/node/Node.java | 1 + .../java/com/seaofnodes/simple/node/StoreNode.java | 27 ++- .../simple/print/SimpleGraphObserver.java | 2 +- .../java/com/seaofnodes/simple/type/Field.java | 5 +- .../java/com/seaofnodes/simple/type/TypeMem.java | 7 +- .../com/seaofnodes/simple/type/TypeMemPtr.java | 27 +-- .../com/seaofnodes/simple/type/TypeStruct.java | 45 +++-- .../java/com/seaofnodes/simple/Chapter05Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter06Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter08Test.java | 6 +- .../java/com/seaofnodes/simple/Chapter09Test.java | 10 +- .../java/com/seaofnodes/simple/Chapter10Test.java | 17 +- .../java/com/seaofnodes/simple/Chapter12Test.java | 200 +++++++++++++++++++++ src/test/java/com/seaofnodes/simple/TypeTest.java | 4 +- .../seaofnodes/simple/fuzzer/ScriptGenerator.java | 149 ++++++++++----- 29 files changed, 1041 insertions(+), 214 deletions(-) delete mode 100644 chapter11.iml create mode 100644 chapter12.iml create mode 100644 docs/chapter12/12-grammar.ja.md create mode 100644 docs/chapter12/12-grammar.md create mode 100644 docs/chapter12/Makefile create mode 100644 docs/chapter12/README.ja.md create mode 100644 docs/chapter12/README.md create mode 100644 src/test/java/com/seaofnodes/simple/Chapter12Test.java diff --git a/README.ja.md b/README.ja.md index faa963f4..7d45a807 100644 --- a/README.ja.md +++ b/README.ja.md @@ -48,7 +48,7 @@ Simple 言語のスタイルは、C または Java のサブセットに倣っ * [第9章](docs/chapter09/README.ja.md)：大域的値番号付け。不動点に達するまでのピープホール最適化の反復。ワークリスト。 * [第10章](docs/chapter10/README.ja.md)：ユーザー定義の構造体、ポインタ、null 解析。SSA で表す単一のメモリ値。ロード、ストア、実行可能な評価器。 * [第11章](docs/chapter11/README.ja.md)：同値類によるエイリアス解析。`MemMerge`、`MemPhi`、`BulkMemPhi` による必要時のメモリ分割。 -* 第12章：参照フィールド、前方参照、再帰的な構造体。 +* [第12章](docs/chapter12/README.ja.md)：参照フィールド、前方参照、再帰的な構造体。 * 第13章：大域的コード移動とスケジューリング。 * 第14章：数値型。浮動小数点数、狭い整数型、範囲、`f32` への丸め。 * 第15章：静的な長さを持つ一次元配列型。配列のロードとストア。 diff --git a/README.md b/README.md index 3ca676ee..6aca0c35 100644 --- a/README.md +++ b/README.md @@ -57,7 +57,7 @@ The Simple language is styled after a subset of C or Java. analysis. One memory value in SSA. Loads, stores, and an executable evaluator. * [Chapter 11](docs/chapter11/README.md): Equivalence class aliasing. Lazy memory partitioning with `MemMerge`, `MemPhi`, and `BulkMemPhi`. -* Chapter 12: Reference fields, forward references and recursive structs. +* [Chapter 12](docs/chapter12/README.md): Reference fields, forward references and recursive structs. * Chapter 13: Global Code Motion - Scheduling. * Chapter 14: Numeric types: floats, narrow integers, ranges and rounding to `f32`. * Chapter 15: One dimensional static length array type, with array loads and stores. diff --git a/chapter11.iml b/chapter11.iml deleted file mode 100644 index 92b9e5ca..00000000 --- a/chapter11.iml +++ /dev/null @@ -1,28 +0,0 @@ - - - - - - - - - - - - - - - - - - - - - - - - - - - - diff --git a/chapter12.iml b/chapter12.iml new file mode 100644 index 00000000..28f6886a --- /dev/null +++ b/chapter12.iml @@ -0,0 +1,28 @@ + + + + + + + + + + + + + + + + + + + + + + + + + + + + diff --git a/docs/chapter12/12-grammar.ja.md b/docs/chapter12/12-grammar.ja.md new file mode 100644 index 00000000..827e7478 --- /dev/null +++ b/docs/chapter12/12-grammar.ja.md @@ -0,0 +1,136 @@ +# 第12章の文法 + +[English](12-grammar.md) | 日本語 + +この文書は [原文](12-grammar.md) の日本語訳です。 + +[第12章に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatement + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + ; + +PRIMTYPE + : 'int' + ; + +field + : PRIMTYPE IDENTIFIER ';' + | structName ('?')? IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : PRIMTYPE IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpression '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DEC_DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter12/12-grammar.md b/docs/chapter12/12-grammar.md new file mode 100644 index 00000000..41a7e24e --- /dev/null +++ b/docs/chapter12/12-grammar.md @@ -0,0 +1,132 @@ +# Grammar for Chapter 12 + +English | [日本語](12-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement+ EOF + ; + +statement + : returnStatement + | structDeclaration + | declStatement + | blockStatement + | expressionStatement + | ifStatement + | whileStatement + | breakStatement + | continueStatement + ; + +PRIMTYPE + : 'int' + ; + +field + : PRIMTYPE IDENTIFIER ';' + | structName ('?')? IDENTIFIER ';' + ; + +fields + : field+ + ; + +structDeclaration + : 'struct' IDENTIFIER '{' fields '}' + ; + +whileStatement + : 'while' '(' expression ')' statement + ; + +breakStatement + : 'break' ';' + ; + +continueStatement + : 'continue' ';' + ; + +ifStatement + : 'if' '(' expression ')' statement ('else' statement)? + ; + + +expressionStatement + : IDENTIFIER '=' expression ';' + | fieldExpression '=' expression ';' + ; + +blockStatement + : '{' statement+ '}' + ; + +structName + : IDENTIFIER + ; + +declStatement + : PRIMTYPE IDENTIFIER '=' expression ';' + | structName ('?')? IDENTIFIER '=' expression ';' + ; + +returnStatement + : 'return' expression ';' + ; + +expression + : comparisonExpression + ; + +comparisonExpression + : additiveExpression (('==' | '!='| '>'| '<'| '>='| '<=') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-') unaryExpression + | '!' unaryExpression + | primaryExpression + ; + +newExpression + : 'new' IDENTIFIER + ; + +fieldExpression + : primaryExpression '.' IDENTIFIER + ; + +primaryExpression + : IDENTIFIER + | INTEGER_LITERAL + | 'true' + | 'false' + | 'null' + | newExpression + | '(' expression ')' + | fieldExpression + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; + +IDENTIFIER + : NON_DIGIT (NON_DIGIT | DEC_DIGIT)* + ; + +NON_DIGIT: [a-zA-Z_]; +DEC_DIGIT: [0-9]; +``` diff --git a/docs/chapter12/Makefile b/docs/chapter12/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter12/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/chapter12/README.ja.md b/docs/chapter12/README.ja.md new file mode 100644 index 00000000..2b0f19dc --- /dev/null +++ b/docs/chapter12/README.ja.md @@ -0,0 +1,101 @@ +# 第12章: 参照 + +[English](README.md) | 日本語 + +[前: 第11章](../chapter11/README.ja.md) | +[次: 第13章](../chapter13/README.ja.md) + +この文書は [原文](README.md) の日本語訳です。 + +第10章と第11章では、構造体に整数フィールドを追加し、そのメモリへの作用を SSA で表しました。この章では、まだ定義が現れていない構造体も含め、フィールドにほかの構造体への参照を格納できるようにします。メモリグラフを変更せずに、連結リストや互いを参照するオブジェクトを扱えます。 + +線形の Git 履歴で[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12)を読むことや、[第11章との差分](https://github.com/SeaOfNodes/Simple/compare/linear-chapter11...linear-chapter12)を見ることもできます。 + +## 型付きフィールドと前方参照 + +```java +struct Person { + int age; + FamilyTree? tree; +} +struct FamilyTree { + Person? father; + Person? mother; +} +``` + +パーサーの `TYPES` テーブルは名前を型に対応付けます。初期状態では `int`（およびほかのプリミティブ型。後の章でさらに登場します）が入っています。`type()` が未知の名前を使う宣言を認識すると、`_fields == null` の、名前だけの `TypeStruct` を登録します。これは構造体名だけがわかっていて、ほかの情報はない構造体です。その構造体へのポインタがあれば、参照フィールドを記述するには十分で、`?` によってポインタが null であることを許容します。 + +`parseStruct()` は、すべてのフィールドを収集してから完全な構造体を `TYPES` に登録します。テーブルのエントリを置き換えるのであって、古い型を変更したり、フィールドリストの途中までを順次公開したりはしません。フィールドのエイリアスは、これまでと同じく宣言が完成した時点で割り当てます。 + +[パーサー](../../src/main/java/com/seaofnodes/simple/Parser.java)、特に `type()`、`parseField()`、`parseStruct()` と、[文法](12-grammar.ja.md)を参照してください。 + +## 再帰構造体: `L0` と `L1` + +```java +struct LLI { LLI? next; int i; } +``` + +コンパイラが実際に何を構築するかを覚えておくには、次の2つの記述が役立ちます。 + +```text +L0 = TypeStruct("LLI", fields = null) +L1 = TypeStruct("LLI", fields = { next: pointer-to-L0?, i: int }) +TYPES["LLI"] = L1 +``` + +`L0` は `LLI? next` フィールドをパースするときに作られます。閉じ波括弧の後で、名前テーブル内の `L0` を `L1` が置き換えます。`L1` 内の `next` フィールドは引き続き `L0` を指します。`L1` に戻るように書き換えません。 + +この設計は、**不変で浅い参照を、必要に応じて名前で解決する**ものです。実行時のオブジェクトはサイクルを形成しても、コンパイラの型記述は有限で非循環のままです。これは、**再帰的な型の展開を止める**意図的な決定です。すべての参照に完成した定義を再帰的に代入すると、無限に展開するか、循環する型のインターン化、等価性、ハッシュ、束の操作が必要になります（実際に、束を扱う章で登場します）。 + +[`TypeStruct`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) は、代わりに名前だけの記述で止めます。`dual()` と `glb()` はその記述をそのままにします。同じ構造体の完全な記述と名前だけの記述の meet は、名前だけの記述になります。これによってフィールドの詳細は失われますが、構造体の識別情報は失われません。`L0` をますます深い `L1`、`L2` などの列へと展開しようとするパスはありません。 + +## 浅い参照の解決 + +`head.next` のパース時、`parsePostfix()` はポインタの構造体名を取り出し、`TYPES` で現在の宣言を検索します。ポインタ自身の型にまだ `L0` が含まれていても、その宣言からフィールドの配置とエイリアスを得ます。`head.next.next.i` のような連鎖には、次のフィールドアクセスでも検索を繰り返せば十分です。 + +局所宣言や代入では、`parseExpressionStatement()` も、代入の互換性を確認する前に名前だけのポインタを解決します。この「深める」処理はチェックに使う一時的な型を変更するだけで、式ノードの型を書き換えたり、グラフ内の古い参照をすべて置き換えたりはしません。 + +```java +struct LLI { LLI? next; int i; } +LLI? head = null; +while (arg) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg - 1; +} +if (!head) return 0; +LLI? next = head.next; +if (next == null) return 1; +return next.i; +``` + +null チェックは、生き残る制御経路でポインタの型を絞り込みます。特に、明示的な `else` がなくても、`if` の false 経路はその絞り込みを記録しなければなりません。名前の解決はフィールドの定義を与えますが、ポインタが null でないことを証明するわけではありません。 + +## 初期化と不完全な定義 + +`newStruct()` は、各フィールドをその型の `makeInit()` で初期化します。整数はゼロ、参照は null です。Load と Store は第11章と同じエイリアスとメモリ最適化を使います。したがって、初期化 Store からの Load は null に畳み込めます。 + +使われない前方参照は、最後まで定義する必要がありません。 + +```java +struct Holder { Missing? ref; } +Holder h = new Holder; +return h.ref; // null; no definition of Missing is needed +``` + +ここでは、完全な定義なしに null でない `Missing` を構築する方法はありません。`new Missing` は拒否されます。そのフィールドにアクセスするにも、null でないポインタに加えて定義が必要です。null を許容する参照型に言及するだけでは、プログラムの終わりまでに定義する義務は生じません。 + +この章には、初期化に関する一時的な許容事項が1つあります。 + +```java +struct N { N next; int i; } +N n = new N; +return n.next; // null, despite the non-null field declaration +``` + +初期化 Store は、null を許容しない参照フィールドにも null を書き込めます。通常の `n.next = null` は拒否されます。第16章ではコンストラクタを追加して初期化をチェックします。この章では、この区別を [`StoreNode`](../../src/main/java/com/seaofnodes/simple/node/StoreNode.java) に明示的に保持します。 + +[参照のテスト](../../src/test/java/com/seaofnodes/simple/Chapter12Test.java)は、連結リスト、相互参照、null チェック、不完全な型を検証します。`make tests` で実行でき、`make view` は同じ未スケジュールのグラフを表示します。これで第13章には、ロード/ストアの反依存も含めた大域的コード移動の導入に必要な、メモリと参照の意味論がそろいました。 diff --git a/docs/chapter12/README.md b/docs/chapter12/README.md new file mode 100644 index 00000000..5087ee21 --- /dev/null +++ b/docs/chapter12/README.md @@ -0,0 +1,150 @@ +# Chapter 12: References + +English | [日本語](README.ja.md) + +[Previous: Chapter 11](../chapter11/README.md) | +[Next: Chapter 13](../chapter13/README.md) + +Chapters 10 and 11 gave structs integer fields and represented their memory +effects in SSA. This chapter lets fields contain references to other structs, +including structs whose definitions have not yet appeared. Linked lists and +mutually referring objects become possible without changing the memory graph. + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter12) +in the linear Git history and [compare it with Chapter 11](https://github.com/SeaOfNodes/Simple/compare/linear-chapter11...linear-chapter12). + +## Typed fields and forward references + +```java +struct Person { + int age; + FamilyTree? tree; +} +struct FamilyTree { + Person? father; + Person? mother; +} +``` + +The parser's `TYPES` table maps names to types. It initially contains `int` +(and any other primitive types, more are showing up in later chapters). When +`type()` recognizes a declaration using an unknown name, it installs a +name-only `TypeStruct`, with `_fields == null` - this a struct where we only +know the struct name, and no other information. A pointer to that struct is +enough to describe a reference field,`?` allows the pointer to be null. + +`parseStruct()` collects all fields before installing the complete struct in +`TYPES`. It replaces the table entry; it does not mutate the old type or +publish successive prefixes of the field list. Field aliases are allocated +with the completed declaration, as before. + +See [the parser](../../src/main/java/com/seaofnodes/simple/Parser.java), particularly +`type()`, `parseField()`, and `parseStruct()`, and the +[grammar](12-grammar.md). + +## Recursive structs: `L0` and `L1` + +```java +struct LLI { LLI? next; int i; } +``` + +Two descriptions are useful for remembering what the compiler actually builds: + +```text +L0 = TypeStruct("LLI", fields = null) +L1 = TypeStruct("LLI", fields = { next: pointer-to-L0?, i: int }) +TYPES["LLI"] = L1 +``` + +`L0` is created when parsing the `LLI? next` field. After the closing brace, +`L1` replaces it in the name table. The `next` field inside `L1` still points +to `L0`; it is not patched to point back to `L1`. + +The design is **immutable shallow references, resolved by name when needed**. +The runtime objects may form a cycle; their compiler type descriptions remain +finite and acyclic. This is an intentional decision to **stop recursive type +expansion**. Recursively substituting the completed definition into every +reference would either expand forever or require cyclic type interning, +equality, hashing, and lattice operations (which indeed show up in a lattice +chapter). + +[`TypeStruct`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +instead stops at the name-only description. Its `dual()` and `glb()` leave that +description alone. Meeting a complete description with a name-only description +of the same struct yields the name-only description. That loses field detail +without losing the struct's identity. There is no pass trying to expand `L0` +into an ever deeper sequence of `L1`, `L2`, and so on. + +## Resolving a shallow reference + +When parsing `head.next`, `parsePostfix()` takes the pointer's struct name and +looks up the current declaration in `TYPES`. It gets the field layout and alias +from that declaration, even if the pointer's own type still contains `L0`. +Doing the lookup again for the next field access is sufficient for a chain +such as `head.next.next.i`. + +For a local declaration or assignment, `parseExpressionStatement()` also +resolves a name-only pointer before checking assignment compatibility. This +"deepening" changes the temporary type used for the check; it does not rewrite +the expression node's type or replace all old references in the graph. + +```java +struct LLI { LLI? next; int i; } +LLI? head = null; +while (arg) { + LLI x = new LLI; + x.next = head; + x.i = arg; + head = x; + arg = arg - 1; +} +if (!head) return 0; +LLI? next = head.next; +if (next == null) return 1; +return next.i; +``` + +The null checks refine the pointer on the surviving control path. In +particular, the false path of an `if` must record its refinement even when +there is no explicit `else`. Resolving a name supplies the field definition; +it does not prove that the pointer is non-null. + +## Initialization and incomplete definitions + +`newStruct()` initializes each field using its type's `makeInit()`: zero for +integers and null for references. Loads and Stores use the same aliases and +memory optimizations as Chapter 11. A Load from an initializing Store can +therefore fold to null. + +An unused forward reference need not ever be defined: + +```java +struct Holder { Missing? ref; } +Holder h = new Holder; +return h.ref; // null; no definition of Missing is needed +``` + +There is no way here to construct a non-null `Missing` without its complete +definition: `new Missing` is rejected. Accessing one of its fields also needs +a definition, as well as a non-null pointer. Simply mentioning a nullable +reference type does not impose a requirement to define it before the end of +the program. + +There is one temporary initialization allowance in this chapter: + +```java +struct N { N next; int i; } +N n = new N; +return n.next; // null, despite the non-null field declaration +``` + +The initializing Store may write null even into a non-null reference field. +An ordinary `n.next = null` is rejected. Chapter 16 adds constructors and +checks initialization; this chapter keeps the distinction explicit in +[`StoreNode`](../../src/main/java/com/seaofnodes/simple/node/StoreNode.java). + +The [reference tests](../../src/test/java/com/seaofnodes/simple/Chapter12Test.java) +exercise linked lists, mutual references, null checks, and incomplete types. +Run them with `make tests`; `make view` displays the same unscheduled graph. +Chapter 13 now has the memory and reference semantics it needs to introduce +global code motion, including load/store anti-dependencies. diff --git a/src/main/java/com/seaofnodes/simple/Parser.java b/src/main/java/com/seaofnodes/simple/Parser.java index df8d0b1c..a25edeb1 100644 --- a/src/main/java/com/seaofnodes/simple/Parser.java +++ b/src/main/java/com/seaofnodes/simple/Parser.java @@ -82,14 +82,15 @@ public class Parser { ScopeNode _continueScope; ScopeNode _breakScope; - // Mapping from a Struct name to a Struct. - public static Map OBJS = new HashMap<>(); + // Authoritative declarations, indexed by type name. + public static HashMap TYPES = new HashMap<>(); public Parser(String source, TypeInteger arg) { PARSER = this; Node.reset(); IterPeeps.reset(); - OBJS.clear(); + TYPES.clear(); + TYPES.put("int",TypeInteger.BOT); _lexer = new Lexer(source); _scope = new ScopeNode(); _continueScope = _breakScope = null; @@ -121,6 +122,8 @@ public class Parser { _scope.define(ScopeNode.ARG0, TypeInteger.BOT, new ProjNode(START, 2, ScopeNode.ARG0).peephole()); _scope.define("$mem", TypeMem.BOT, new ProjNode(START, 1, "$mem").peephole()); parseBlock(); + if( ctrl()._type==Type.CONTROL ) + STOP.addReturn(new ReturnNode(ctrl(), new ConstantNode(TypeInteger.constant(0)).peephole(), _scope).peephole()); _scope.pop(); _xScopes.pop(); if (!_lexer.isEOF()) throw error("Syntax error, unexpected " + _lexer.getAnyNextToken()); @@ -158,7 +161,6 @@ public class Parser { private Node parseStatement() { if( false ) return null; else if (matchx("return") ) return parseReturn(); - else if (matchx("int") ) return parseDecl(TypeInteger.BOT); else if (match ("{") ) return require(parseBlock(),"}"); else if (matchx("if") ) return parseIf(); else if (matchx("while") ) return parseWhile(); @@ -174,40 +176,42 @@ public class Parser { /** * Parse a struct field. * 
-     *     int IDENTIFIER ;
+     *     type IDENTIFIER ;
      *
*/ - private Field parseField(String sname) { - if( matchx("int") ) // Currently only parsing "int" type fields - return require(Field.make(requireId().intern(),TypeInteger.BOT),";"); - throw errorSyntax("A field type is expected, only type 'int' is supported at present"); + private Field parseField() { + Type t = type(); + if( t==null ) + throw errorSyntax("Requires a field type, found '"+_lexer.getAnyNextToken()+"'"); + return require(Field.make(requireId().intern(),t),";"); } /** - * Parse a struct declaration, and return the following statement. + * Parse a complete struct declaration. * Only allowed in top level scope. * Structs cannot be redefined. * - * @return The statement following the struct + * @return null */ private Node parseStruct() { if (_xScopes.size() > 1) throw errorSyntax("struct declarations can only appear in top level scope"); String typeName = requireId(); - if ( OBJS.containsKey(typeName)) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); + Type t = TYPES.get(typeName); + if( t!=null && !(t instanceof TypeStruct ts && ts._fields==null) ) throw errorSyntax("struct '" + typeName + "' cannot be redefined"); ArrayList fields = new ArrayList<>(); require("{"); while (!peek('}') && !_lexer.isEOF()) { - Field field = parseField(typeName); + Field field = parseField(); if (fields.contains(field)) throw errorSyntax("Field '" + field + "' already defined in struct '" + typeName + "'"); fields.add(field); } require("}"); // Build and install the TypeStruct TypeStruct ts = TypeStruct.make(typeName, fields); + TYPES.put(typeName, ts); // Insert the struct name in the collection of all struct names _aliases.put(typeName,_alias); _alias += ts._fields.length; - OBJS.put(typeName, ts); // Insert the struct name in the collection of all struct names - return parseStatement(); + return null; } /** @@ -349,8 +353,8 @@ public class Parser { // Parse the false side _scope = fScope; // Restore scope, then parse else block if any ifF.unkeep(); // fScope already owns the false control + _scope.upcast(ifF,pred,true); // Up-cast predicate, also without an else if (matchx("else")) { - _scope.upcast(ifF,pred,true); // Up-cast predicate parseStatement(); fScope = _scope; } @@ -418,15 +422,18 @@ public class Parser { if( _scope.define(name,t,expr) == null ) throw error("Redefining name '" + name + "'"); } else { - Node n = _scope.lookup(name); - t = _scope.lookupDeclaredType(name); - if( n==null ) + if( _scope.lookup(name)==null ) throw error("Undefined name '" + name + "'"); - _scope.update(name,expr); + t = _scope.lookupDeclaredType(name); } - if( !expr._type.isa(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); - return expr; + // Auto-deepen forward ref types + Type e = expr._type; + if( e instanceof TypeMemPtr tmp && tmp._obj._fields==null ) + e = tmp.make_from((TypeStruct)TYPES.get(tmp._obj._name)); + // Type is sane + if( !e.isa(t) ) + throw error("Type " + e.str() + " is not of declared type " + t.str()); + return _scope.update(name,expr); } // Parse a type-or-null @@ -434,38 +441,22 @@ public class Parser { int old = _lexer._position; String tname = _lexer.matchId(); if( tname==null ) return null; - if( tname.equals("int") ) return TypeInteger.BOT; - TypeStruct obj = OBJS.get(tname); - if( obj != null ) - return TypeMemPtr.make(obj,match("?")); - // Not a type; unwind the parse - _lexer._position = old; - return null; - } - - /** - * Parses a declStatement - * - * 
-     *     type name = expression ';'
-     *
- * @return an expression {@link Node} - */ - private Node parseDecl(Type t) { - var name = requireId(); - var expr = match(";") - // Assign a null value - ? new ConstantNode(t.makeInit()).peephole() - // Assign "= expr;" - : require(require("=").parseExpression(), ";"); - if( !expr._type.isa(t) ) - throw error("Type " + expr._type.str() + " is not of declared type " + t.str()); - if( _scope.define(name,t,expr) == null ) - throw error("Redefining name '" + name + "'"); - return expr; + boolean nullable = match("?"); + Type t = TYPES.get(tname); + // Assume a forward-reference type + if( t == null ) { + int old2 = _lexer._position; + String id = _lexer.matchId(); + if( id==null ) { + _lexer._position = old; + return null; + } + TYPES.put(tname,t = TypeStruct.make(tname)); + _lexer._position = old2; // Reparse ID in caller + } + return t instanceof TypeStruct obj ? TypeMemPtr.make(obj,nullable) : t; } - /** * Parse an expression of the form: * @@ -571,15 +562,16 @@ public class Parser { * @return a primary {@link Node}, never {@code null} */ private Node parsePrimary() { - if( _lexer.isNumber() ) return parseIntegerLiteral(); + if( _lexer.isNumber(_lexer.peek()) ) return parseIntegerLiteral(); if( match("(") ) return require(parseExpression(), ")"); if( matchx("true" ) ) return new ConstantNode(TypeInteger.constant(1)).peephole(); - if( matchx("false") ) return new ConstantNode(TypeInteger.constant(0)).peephole(); + if( matchx("false") ) return new ConstantNode(TypeInteger.ZERO).peephole(); if( matchx("null" ) ) return new ConstantNode(TypeMemPtr.NULLPTR).peephole(); if( matchx("new") ) { String structName = requireId(); - TypeStruct obj = OBJS.get(structName); - if( obj == null) throw errorSyntax("Unknown struct type '" + structName + "'"); + Type t = TYPES.get(structName); + if( !(t instanceof TypeStruct obj) || obj._fields==null ) + throw error("Unknown struct type '" + structName + "'"); return newStruct(obj); } String name = _lexer.matchId(); @@ -592,12 +584,11 @@ public class Parser { /** * Return a NewNode but also generate instructions to initialize it. */ - private Node newStruct( TypeStruct obj ) { + private Node newStruct(TypeStruct obj) { Node n = new NewNode(TypeMemPtr.make(obj), ctrl()).peephole().keep(); - Node initValue = new ConstantNode(TypeInteger.constant(0)).peephole(); int alias = _aliases.get(obj._name); for( Field field : obj._fields ) { - store(field._fname,alias,n,initValue); + store(field._fname,alias,field._type,n,new ConstantNode(field._type.makeInit()).peephole(),true); alias++; } return n.unkeep(); @@ -607,9 +598,9 @@ public class Parser { private Node mem() { return _scope.lookup("$mem"); } private Node mem(Node n) { return _scope.update("$mem",n); } - private void store(String name, int alias, Node ptr, Node val) { + private void store(String name, int alias, Type glb, Node ptr, Node val, boolean init) { Node prior = mem().keep(); - Node st = new StoreNode(name,alias,prior,ptr,val).peephole(); + Node st = new StoreNode(name,alias,glb,null,prior,ptr,val,init).peephole(); mem(new MemMergeNode(prior,alias,st).peephole()); if( prior.unkeep().isUnused() ) prior.kill(); } @@ -629,7 +620,10 @@ public class Parser { throw error("Expected struct reference but got " + expr._type.str()); String name = requireId().intern(); - int idx = ptr._obj==null ? -1 : ptr._obj.find(name); + if( expr._type == TypeMemPtr.TOP ) throw error("Accessing field '" + name + "' from null"); + if( ptr._obj == null ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); + TypeStruct base = (TypeStruct)TYPES.get(ptr._obj._name); + int idx = base==null ? -1 : base.find(name); if( idx == -1 ) throw error("Accessing unknown field '" + name + "' from '" + ptr.str() + "'"); int alias = _aliases.get(ptr._obj._name)+idx; @@ -638,13 +632,14 @@ public class Parser { if( peek('=') ) _lexer._position--; else { Node val = parseExpression(); - store(name,alias,expr,val); + Type glb = base._fields[idx]._type; + store(name,alias,glb,expr,val,false); return expr; // "obj.a = expr" returns the expression while updating memory } } - Type declaredType = ptr._obj._fields[idx]._type; - return parsePostfix(new LoadNode(name, alias, declaredType, mem(), expr).peephole()); + Type declaredType = base._fields[idx]._type; + return parsePostfix(new LoadNode(name, alias, declaredType.glb(), mem(), expr).peephole()); } /** diff --git a/src/main/java/com/seaofnodes/simple/node/AddNode.java b/src/main/java/com/seaofnodes/simple/node/AddNode.java index e235d288..e993a20e 100644 --- a/src/main/java/com/seaofnodes/simple/node/AddNode.java +++ b/src/main/java/com/seaofnodes/simple/node/AddNode.java @@ -168,4 +168,9 @@ public class AddNode extends Node { } @Override Node copy(Node lhs, Node rhs) { return new AddNode(lhs,rhs); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/LoadNode.java b/src/main/java/com/seaofnodes/simple/node/LoadNode.java index 9bf36459..b2ee6939 100644 --- a/src/main/java/com/seaofnodes/simple/node/LoadNode.java +++ b/src/main/java/com/seaofnodes/simple/node/LoadNode.java @@ -14,7 +14,6 @@ import com.seaofnodes.simple.type.Field; */ public class LoadNode extends MemOpNode { - Type _declaredType; /** * Load a value from a ptr.field. * @@ -23,12 +22,11 @@ public class LoadNode extends MemOpNode { * @param memPtr The ptr to the struct from where we load a field */ public LoadNode(String name, int alias, Type glb, Node memSlice, Node memPtr) { - super(name, alias, memSlice, memPtr, null); - _declaredType = glb; + super(name, alias, glb, null, memSlice, memPtr); } @Override boolean canDrop(MemOpNode other, Node dep) { - return super.canDrop(other,dep) && _declaredType==((LoadNode)other)._declaredType && !clobbered(dep); + return super.canDrop(other,dep) && !clobbered(dep); } // Check only immediate memory users. Stores clobber memory; Phis and diff --git a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java index 44304bcb..7c6afb0c 100644 --- a/src/main/java/com/seaofnodes/simple/node/MemOpNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MemOpNode.java @@ -11,11 +11,14 @@ public abstract class MemOpNode extends Node { public final String _name; public final int _alias; + public final Type _declaredType; - public MemOpNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(null, memSlice, memPtr, value); + + public MemOpNode(String name, int alias, Type glb, Node... nodes ) { + super(nodes); _name = name; _alias = alias; + _declaredType = glb; } public Node mem() { return in(1); } @@ -25,7 +28,7 @@ public abstract class MemOpNode extends Node { // The caller has already checked the opcode, input shape and control. boolean canDrop(MemOpNode other, Node dep) { ptr().addDep(dep); - return _alias==other._alias && err()==null; + return _alias==other._alias && _declaredType==other._declaredType && err()==null; } @Override diff --git a/src/main/java/com/seaofnodes/simple/node/MulNode.java b/src/main/java/com/seaofnodes/simple/node/MulNode.java index 5592c52d..b0359a52 100644 --- a/src/main/java/com/seaofnodes/simple/node/MulNode.java +++ b/src/main/java/com/seaofnodes/simple/node/MulNode.java @@ -51,4 +51,9 @@ public class MulNode extends Node { return null; } @Override Node copy(Node lhs, Node rhs) { return new MulNode(lhs,rhs); } + @Override public String err() { + if( !(in(1)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(1)._type; + if( !(in(2)._type instanceof TypeInteger) ) return "Cannot '"+label()+"' " + in(2)._type; + return null; + } } diff --git a/src/main/java/com/seaofnodes/simple/node/Node.java b/src/main/java/com/seaofnodes/simple/node/Node.java index 1d8e23f8..999e38fd 100644 --- a/src/main/java/com/seaofnodes/simple/node/Node.java +++ b/src/main/java/com/seaofnodes/simple/node/Node.java @@ -190,6 +190,7 @@ public abstract class Node extends BaseNode implements Cloneable { */ public void kill( ) { unlock(); + moveDepsToWorklist(); assert isUnused(); // Has no uses, so it is dead _type=null; // Flag as dead while( nIns()>0 ) { // Set all inputs to null, recursively killing unused Nodes diff --git a/src/main/java/com/seaofnodes/simple/node/StoreNode.java b/src/main/java/com/seaofnodes/simple/node/StoreNode.java index 026d5c50..e9eaaf2e 100644 --- a/src/main/java/com/seaofnodes/simple/node/StoreNode.java +++ b/src/main/java/com/seaofnodes/simple/node/StoreNode.java @@ -13,20 +13,26 @@ import com.seaofnodes.simple.type.*; */ public class StoreNode extends MemOpNode { + private final boolean _init; // Initializing writes are allowed to write null + /** * @param name The struct field we are assigning to * @param memSlice The memory alias node - this is updated after a Store * @param memPtr The ptr to the struct where we will store a value * @param value Value to be stored */ - public StoreNode(String name, int alias, Node memSlice, Node memPtr, Node value) { - super(name, alias, memSlice, memPtr, value); + public StoreNode(String name, int alias, Type glb, Node ctrl, Node memSlice, Node memPtr, Node value, boolean init) { + super(name, alias, glb, ctrl, memSlice, memPtr, value); + _init = init; } - @Override - public String label() { return "Store"; } - @Override - public boolean isMem() { return true; } + @Override boolean canDrop(MemOpNode other, Node dep) { + return super.canDrop(other,dep) && _init==((StoreNode)other)._init; + } + + @Override public String label() { return "." +_name+"="; } + @Override public boolean isMem() { return true; } + public Node val() { return in(3); } @Override @@ -53,7 +59,7 @@ public class StoreNode extends MemOpNode { // Must have exactly one use of "this" or you get weird // non-serializable memory effects in the worse case. st.checkNoUseBeyond(this) ) { - assert Utils.eq(_name,st._name); // Equiv class aliasing is perfect + assert _name.equals(st._name); // Equiv class aliasing is perfect setDef(1,st.mem()); return this; } @@ -72,4 +78,11 @@ public class StoreNode extends MemOpNode { return false; } + @Override + String err() { + String err = super.err(); + if( err != null ) return err; + Type ptr = val()._type; + return _init || ptr.isa(_declaredType) ? null : "Cannot store "+ptr+" into field "+_declaredType+" "+_name; + } } diff --git a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java index feb9e90f..5c852f94 100644 --- a/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java +++ b/src/main/java/com/seaofnodes/simple/print/SimpleGraphObserver.java @@ -7,7 +7,7 @@ import com.seaofnodes.simple.node.Node; import java.util.ArrayList; import java.io.IOException; -/** Chapter 11's compilation context; capture and event bookkeeping are shared. */ +/** Chapter 12's compilation context; capture and event bookkeeping are shared. */ public class SimpleGraphObserver extends GraphCapture { private Parser _parser; private Node _ret; diff --git a/src/main/java/com/seaofnodes/simple/type/Field.java b/src/main/java/com/seaofnodes/simple/type/Field.java index cdc58215..b2c006dd 100644 --- a/src/main/java/com/seaofnodes/simple/type/Field.java +++ b/src/main/java/com/seaofnodes/simple/type/Field.java @@ -20,6 +20,7 @@ public class Field extends Type { _fname = fname; _type = type; } + // Make with existing alias public static Field make( String fname, Type type ) { return new Field(fname,type).intern(); } @@ -46,13 +47,13 @@ public class Field extends Type { boolean eq(Type t) { Field f = (Field)t; - return Utils.eq(_fname,f._fname) && _type==f._type; + return _fname.equals(f._fname) && _type==f._type; } @Override public StringBuilder print( StringBuilder sb ) { - return _type.print(sb.append(_fname).append(":")); + return _type.print(sb.append(_fname).append(" :")); } @Override public String str() { return _fname; } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMem.java b/src/main/java/com/seaofnodes/simple/type/TypeMem.java index b6fc8824..38b3635a 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMem.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMem.java @@ -15,7 +15,7 @@ public class TypeMem extends Type { // 0 means TOP, no slice. // -1 means BOT, all memory. // N means slice#N. - private final int _alias; + public final int _alias; private TypeMem(int alias) { super(TMEM); _alias = alias; } @@ -23,7 +23,6 @@ public class TypeMem extends Type { public static final TypeMem TOP = make( 0); public static final TypeMem BOT = make(-1); - public static void gather(ArrayList ts) { ts.add(make(1)); ts.add(BOT); } @Override @@ -40,7 +39,7 @@ public class TypeMem extends Type { } @Override - public Type glb() { return TypeMem.BOT; } + public Type glb() { return make(_alias); } @Override int hash() { return 9876543 + _alias; } @@ -62,5 +61,5 @@ public class TypeMem extends Type { }); } - @Override public String str() { return print(new StringBuilder()).toString(); } + @Override public String str() { return toString(); } } diff --git a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java index 6c874a93..5caa816d 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java @@ -13,21 +13,27 @@ import java.util.ArrayList; */ public class TypeMemPtr extends Type { // A TypeMemPtr is pair (obj,nil) - // where obj is one of - // (null,TypeStruct). - // where nil is one of - // (true,false) meaning an explicit null is allowed or not + // where obj is a TypeStruct, possibly TypeStruct.BOT + // where nil is an explicit null is allowed or not - public final TypeStruct _obj; // null, a TypeStruct, or sentinel TypeStruct.MANY + // Examples: + // (Person,false) - a not-nil Person + // (Person,true ) - a Person or a nil + // (BOT ,false) - a not-nil void* (unspecified struct) + // (TOP ,true ) - a nil + + public final TypeStruct _obj; public final boolean _nil; private TypeMemPtr(TypeStruct obj, boolean nil) { super(TMEMPTR); + assert obj!=null; _obj = obj; _nil = nil; } public static TypeMemPtr make(TypeStruct obj, boolean nil) { return new TypeMemPtr(obj, nil).intern(); } - public static TypeMemPtr make(TypeStruct obj) { return TypeMemPtr.make(obj, false); } + public static TypeMemPtr make(TypeStruct obj) { return make(obj, false); } + public TypeMemPtr make_from(TypeStruct obj) { return make(obj, _nil); } public static final TypeMemPtr BOT = make(TypeStruct.BOT,true); public static final TypeMemPtr TOP = BOT.dual(); @@ -43,17 +49,14 @@ public class TypeMemPtr extends Type { } @Override - public TypeMemPtr dual() { return TypeMemPtr.make(_obj==null ? null : _obj.dual(), !_nil); } + public TypeMemPtr dual() { return TypeMemPtr.make(_obj.dual(), !_nil); } @Override - public Type glb() { - if( _obj==null ) return BOT; - return make(_obj.glb(),true); - } + public Type glb() { return make(_obj.glb(),true); } @Override public TypeMemPtr makeInit() { return NULLPTR; } @Override - int hash() { return (_obj==null ? 0xDEADBEEF : _obj.hashCode()) ^ (_nil ? 1024 : 0); } + int hash() { return _obj.hashCode() ^ (_nil ? 1024 : 0); } @Override boolean eq(Type t) { diff --git a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java index 44741def..02de7cc8 100644 --- a/src/main/java/com/seaofnodes/simple/type/TypeStruct.java +++ b/src/main/java/com/seaofnodes/simple/type/TypeStruct.java @@ -8,9 +8,12 @@ import java.util.ArrayList; */ public class TypeStruct extends Type { - // For now in terms of the lattice - // a struct type just stays as is - + // Immutable shallow references, resolved by name in Parser.TYPES when needed. + // A name-only struct has _fields == null, even after its definition is known. + // For LLI { LLI? next; int i; }, L0 is name-only and L1.next points to L0; + // TYPES["LLI"] holds L1. We deliberately stop recursive type expansion here, + // keeping interning and lattice operations finite and acyclic. Never patch + // L0 into L1: field access looks up the complete declaration by name instead. public final String _name; public final Field[] _fields; @@ -20,13 +23,23 @@ public class TypeStruct extends Type { _fields = fields; } + // Forward-ref version + public static TypeStruct make(String name) { return new TypeStruct(name, null).intern(); } + // All fields directly listed public static TypeStruct make(String name, Field[] fields) { return new TypeStruct(name, fields).intern(); } + // Parser uses an ArrayList to gather the fields public static TypeStruct make(String name, ArrayList fields) { return make(name,fields.toArray(new Field[fields.size()])); } public static final TypeStruct TOP = make("$TOP",new Field [0]); public static final TypeStruct BOT = make("$BOT",new Field [0]); public static final TypeStruct TEST = make("test",new Field[]{Field.TEST}); - public static void gather(ArrayList ts) { ts.add(TEST); ts.add(BOT); } + + // A pair of self-cyclic types + private static final TypeStruct S1F = make("S1"); + private static final TypeStruct S2F = make("S2"); + public static final TypeStruct S1 = make("S1", new Field[]{ Field.make("a", TypeInteger.BOT), Field.make("s2",TypeMemPtr.make(S2F,false)) }); + private static final TypeStruct S2 = make("S2", new Field[]{ Field.make("b", TypeInteger.BOT), Field.make("s1",TypeMemPtr.make(S1F,false)) }); + public static void gather(ArrayList ts) { ts.add(TEST); ts.add(BOT); ts.add(S1); ts.add(S2); } public int find(String fname) { for( int i=0; i<_fields.length; i++ ) @@ -51,6 +64,8 @@ public class TypeStruct extends Type { // And the answer is: "don't ask". if( !_name.equals(that._name) ) return BOT; // It's a struct; that's about all we know + if( this._fields==null ) return this; + if( that._fields==null ) return that; // Now all fields should be the same, so just do field meets assert _fields.length == that._fields.length; Field[] flds = new Field[_fields.length]; @@ -63,6 +78,7 @@ public class TypeStruct extends Type { public TypeStruct dual() { if( this==TOP ) return BOT; if( this==BOT ) return TOP; + if( _fields == null ) return this; Field[] flds = new Field[_fields.length]; for( int i=0; i<_fields.length; i++ ) flds[i] = _fields[i].dual(); @@ -80,9 +96,10 @@ public class TypeStruct extends Type { return make(_name,flds); } private boolean _glb() { - for( Field f : _fields ) - if( f.glb() != f ) - return false; + if( _fields!=null ) + for( Field f : _fields ) + if( f.glb() != f ) + return false; return true; } @@ -91,6 +108,7 @@ public class TypeStruct extends Type { TypeStruct ts = (TypeStruct)t; // Invariant if( !_name.equals(ts._name) ) return false; + if( _fields == ts._fields ) return true; if( _fields.length!=ts._fields.length ) return false; for( int i = 0; i < _fields.length; i++ ) @@ -102,7 +120,9 @@ public class TypeStruct extends Type { @Override int hash() { long hash = _name.hashCode(); - for( Field f : _fields ) hash = Utils.rot(hash,13) ^ f.hashCode(); + if( _fields != null ) + for( Field f : _fields ) + hash = Utils.rot(hash,13) ^ f.hashCode(); return Utils.fold(hash); } @@ -110,11 +130,12 @@ public class TypeStruct extends Type { public StringBuilder print(StringBuilder sb) { if( this==BOT ) return sb.append("StructBot"); if( this==TOP ) return sb.append("StructTop"); - sb.append(_name).append(" {\n"); + sb.append(_name); + if( _fields == null ) return sb; // Forward reference struct, just print the name + sb.append(" {\n"); for( Field f : _fields ) { - sb.append(" ").append(f._fname).append(":"); - f._type.print(sb); - sb.append(";\n"); + sb.append(" ").append(f._fname).append(" :"); + f._type.print(sb).append(";\n"); } return sb.append("}"); } diff --git a/src/test/java/com/seaofnodes/simple/Chapter05Test.java b/src/test/java/com/seaofnodes/simple/Chapter05Test.java index cf7bd6cf..97cd9940 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter05Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter05Test.java @@ -37,7 +37,7 @@ if (arg == 1) { } return c;""", TypeInteger.BOT); StopNode ret = parser.parse().iterate(); - assertEquals("return Phi(Region17,4,3);", ret.toString()); + assertEquals("return Phi(Region18,4,3);", ret.toString()); } @Test @@ -116,7 +116,7 @@ if( arg==0 ) return arg+a+b; """, TypeInteger.BOT); StopNode stop = parser.parse(); - assertEquals("return ((arg+Phi(Region14,1,0))+Phi(Region29,2,0));", stop.toString()); + assertEquals("return ((arg+Phi(Region16,1,0))+Phi(Region32,2,0));", stop.toString()); } @Test @@ -130,7 +130,7 @@ if( arg==1 ) } return a;"""); StopNode ret = parser.parse().iterate(); - assertEquals("return (arg==Phi(Region17,3,2));", ret.toString()); + assertEquals("return (arg==Phi(Region18,3,2));", ret.toString()); } @Test diff --git a/src/test/java/com/seaofnodes/simple/Chapter06Test.java b/src/test/java/com/seaofnodes/simple/Chapter06Test.java index 920e26e3..9af11b68 100644 --- a/src/test/java/com/seaofnodes/simple/Chapter06Test.java +++ b/src/test/java/com/seaofnodes/simple/Chapter06Test.java @@ -30,7 +30,7 @@ if (arg) return (arg < a) < 3; """); StopNode stop = parser.parse().iterate(); - assertEquals("return ((arg structs = new ArrayList<>(); + /** + * All forward declared structs + */ + private final ArrayList forwardStructs = new ArrayList<>(); /** * Allow to declare structs. */ @@ -286,6 +288,7 @@ public class ScriptGenerator { for (var s:structs) { if (s.name.equals(name)) return s; } + for (var s:forwardStructs) if (s.name.equals(name)) return s; return null; } @@ -318,12 +321,18 @@ public class ScriptGenerator { return v; } + private T randFromList(List list) { + return list.get(random.nextInt(list.size())); + } + /** * Get a random structure name * @return A random structure name */ private String getStructName() { - if (!structs.isEmpty() && generateInvalid()) return structs.get(random.nextInt(structs.size())).name; + if (!structs.isEmpty() && generateInvalid()) return randFromList(structs).name; + if (!forwardStructs.isEmpty() && generateInvalid()) return randFromList(forwardStructs).name; + // Generate a new random struct name StringBuilder sb = getRandomName(); var v = sb.toString(); @@ -342,14 +351,26 @@ public class ScriptGenerator { * Get a random type * @return A random type */ - private Type getType() { - if (structs.isEmpty() || random.nextBoolean()) return TYPE_INT; - var idx = random.nextInt(structs.size()); - TypeStruct struct = structs.get(idx); + private Type getType(boolean allowForward) { + int t = random.nextInt(10); + if( t<5 || structs.isEmpty() ) return TYPE_INT; + if (allowForward && random.nextInt(10)==0) { + int i=random.nextInt(forwardStructs.size()+1); + if (i>0) return forwardStructs.get(i-1).nullable; + var name = getStructName(); + var struct = new TypeStruct(name); + forwardStructs.add(struct); + return struct.nullable; + } + TypeStruct struct = randFromList(structs); if (random.nextBoolean()) return struct.nullable; return struct; } + private Type getType() { + return getType(false); + } + /** * Generates a program and writes it into the string builder supplied in the constructor. * @return If the program is allowed to be invalid returns if something potentially invalid was generated. @@ -409,19 +430,29 @@ public class ScriptGenerator { * @return 0 */ public int genStruct() { - var name = getStructName(); + int idx = random.nextInt(forwardStructs.size()+10); + TypeStruct struct; + if (idx < 10) { + var name = getStructName(); + struct = new TypeStruct(name); + forwardStructs.add(struct); + } else { + struct = forwardStructs.get(idx-10); + } var fields = new TypeStruct.Field[generateInvalid() ? 0 : random.nextInt(10)]; - sb.append("struct ").append(name).append(" {\n"); + sb.append("struct ").append(struct.name).append(" {\n"); indentation += INDENTATION; for (int i=0; i 3) { @@ -561,7 +592,7 @@ public class ScriptGenerator { */ public int genWhile() { sb.append("while("); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(") "); loopDepth++; genStatementBlock(); @@ -587,17 +618,17 @@ public class ScriptGenerator { indentation += INDENTATION; String name = getVarName(); printIndentation().append("int ").append(name).append("="); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(";\n"); addVariable(name, TYPE_INT); printIndentation().append("while(").append(name).append("<"); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(") {\n"); indentation += INDENTATION; depth--; loopDepth++; printIndentation().append(name).append("=").append(name).append("+"); - genExpression(TYPE_INT); + genExpression(TYPE_INT, true); sb.append(";\n"); genStatements(); loopDepth--; @@ -621,7 +652,7 @@ public class ScriptGenerator { sb.append(generateInvalid() ? getRandomName() : type.name).append(" ").append(name); if (!(type instanceof TypeNullable) || random.nextBoolean()) { sb.append("="); - genExpression(type); + genExpression(type, true); } sb.append(";"); addVariable(name, type); @@ -656,7 +687,7 @@ public class ScriptGenerator { declared = field.type; } sb.append("="); - genExpression(declared); + genExpression(declared, true); sb.append(";"); return 0; } @@ -668,7 +699,7 @@ public class ScriptGenerator { public int genReturn() { var type = getType(); sb.append("return "); - genExpression(type); + genExpression(type, true); sb.append(";"); return FLAG_STOP; } @@ -677,70 +708,91 @@ public class ScriptGenerator { * Generate a binary expression. * This method does not care about operator precedence. */ - public void genExpression(Type type) { - if (generateInvalid()) type = getType(); + public void genExpression(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); if (type != TYPE_INT) { - genUnary(type); + genUnary(type, false); return; } var num = randLog(MAX_BINARY_EXPRESSIONS_PER_EXPRESSION); while(num-->0) { - genUnary(TYPE_INT); + genUnary(type, false); sb.append(BINARY_OP[random.nextInt(BINARY_OP.length)]); } - genUnary(TYPE_INT); + genUnary(type, false); } /** * Generate a unary expression. */ - public void genUnary(Type type) { - if (generateInvalid()) type = getType(); + public void genUnary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); if (type != TYPE_INT) { - genSuffix(type); + genSuffix(type, false); return; } var num = randLog(MAX_UNARY_EXPRESSIONS_PER_EXPRESSION); while(num-->0) { sb.append(UNARY_OP[random.nextInt(UNARY_OP.length)]); } - genSuffix(TYPE_INT); + genSuffix(type, false); + } + + public TypeStruct.Field getField(Type type) { + int n=0; + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) n++; + } + } + if (n==0) return null; + n = random.nextInt(n); + for (var s: structs) { + for (var f: s.fields) { + if (f.type.isa(type)) if (n--==0) return f; + } + } + throw new AssertionError(); } /** * Generate */ - public void genSuffix(Type type) { - if (generateInvalid()) type = getType(); - if (type == TYPE_INT && random.nextBoolean()) { - var t = getType(); + public void genSuffix(Type type, boolean change) { + genSuffixRecursive(type, change, MAX_SUFFIX_RECURSIVE_DEPTH); + } + + public void genSuffixRecursive(Type type, boolean change, int depth) { + if (change && generateInvalid()) type = getType(); + if (depth > 0 && random.nextBoolean()) { if (generateInvalid()) { var field = getRandomName(); - genPrimary(t); + var t = getType(); + genSuffixRecursive(t, true, depth-1); sb.append(".").append(field); return; - } else if (t instanceof TypeStruct s && s.fields.length > 0) { - var field = s.fields[random.nextInt(s.fields.length)]; - if (field.type == TYPE_INT) { - genPrimary(t); + } else { + var field = getField(type); + if (field != null) { + genSuffixRecursive(field.struct, true, depth-1); sb.append(".").append(field.name); return; } } } - genPrimary(type); + genPrimary(type, false); } /** * Generate a primary expression. */ - public void genPrimary(Type type) { - if (generateInvalid()) type = getType(); + public void genPrimary(Type type, boolean change) { + if (change && generateInvalid()) type = getType(); var rand = random.nextInt(10); if (rand == 0 && exprDepth != 0) { sb.append("("); exprDepth--; - genExpression(type); + genExpression(type, false); exprDepth++; sb.append(")"); } else if (rand < 6) { @@ -762,8 +814,9 @@ public class ScriptGenerator { case 1 -> sb.append("false"); default -> sb.append(random.nextInt(1<<(rand-2))); } + } else if (type instanceof TypeNullable n) { - if (random.nextBoolean()) { + if ((n.base instanceof TypeStruct s && s.fields == null) || random.nextBoolean()) { sb.append("null"); } else { sb.append("new ").append(generateInvalid() ? getRandomName() : n.base.name); -- cgit v1.2.3