diff options
Diffstat (limited to 'docs')
33 files changed, 3929 insertions, 0 deletions
diff --git a/docs/appendices/README.md b/docs/appendices/README.md new file mode 100644 index 00000000..d7803c97 --- /dev/null +++ b/docs/appendices/README.md @@ -0,0 +1,15 @@ +# Appendices + +These notes supplement the numbered compiler snapshots; they do not introduce +another compiler directory. + +- [Native library construction](native-libraries.md): bundled `sys`, native + symbols and thunks, runtime support, and executable examples in Chapter 28b. +- [Optimizer and backend tuning](optimizer-tuning.md): spill ranking, + rematerialization, inlining, and historical measurements from the split's + original snapshots. [Measurement methods](../regalloc-spills.md) describe + what those numbers include. + +The [roadmap](../roadmap.md), [incremental build design](../incremental-builds.md), +and [review queue](../chapter-backports.md) distinguish future work from current +behavior. The [stage audit](../stage-audit.md) records known limits and cleanup. diff --git a/docs/appendices/current-spill-matrix.md b/docs/appendices/current-spill-matrix.md new file mode 100644 index 00000000..df253a46 --- /dev/null +++ b/docs/appendices/current-spill-matrix.md @@ -0,0 +1,14 @@ +# Current allocator comparison + +`make spill-stats` measures Chapters 20, 21, 22, 23, 24b, and 28b against the +historical test cohorts. Cohort IDs and test names retain their old numbers; +column headings identify the current compiler directories. + +These are separate from the dated [pre-split measurements](../regalloc-spills.md). +After a successful run, `python build-support/spill-matrix.py --reuse --update-docs` +updates only this table. Fresh logs use 24b/28b names so old 24/25 results cannot +silently become measurements of new compiler snapshots. + +<!-- spill-matrix:start --> +No post-split measurement has been published yet. +<!-- spill-matrix:end --> diff --git a/docs/appendices/native-libraries.md b/docs/appendices/native-libraries.md new file mode 100644 index 00000000..012b8137 --- /dev/null +++ b/docs/appendices/native-libraries.md @@ -0,0 +1,67 @@ +# Native library construction + +The complete compiler is [Chapter 28b](../chapter28b/README.md). This appendix +collects the library and native support that accompanied the old combined +Chapter 25. The split preserves that functionality in Chapter 28b. + +## Building the library + +From `chapter28b`, run: + +```sh +make lib release +``` + +Make builds `build/release/Simple.jar` and, under the selected CPU/ABI directory, +`sys.o` and `simple_crt.o`. The default CPU is x86-64; the default calling +convention is win64 on Windows and SystemV elsewhere. Rebuild serialized +objects after changing the compiler or object format. + +`src/main/smp/sys.smp` exposes child units for native libc bindings, I/O, +characters, scanners, arrays, growable buffers, and bitsets. These compile into +one `sys.o`. Clients import its declarations and ideal IR and link calls that +remain out of line. Currently selecting that object loads all its saved IR; +member-selective loading and reliable incremental rebuilding remain future work. + +The `simple.sh`, `simple.ps1`, and `simple.bat` launchers set `SIMPLE_HOME` so +the compiler can find the release library. The CLI accepts `-L` for additional +Simple objects or search directories. The chapter README gives an explicit +library/client example that needs no library source in the client root. + +## Native symbols and pointer sizes + +Native function calls and numeric native data symbols have ELF relocations. +The historical `Chapter25Test.testExternDataEncoding` and `testExternDataImports` +exercise native data; `StaticDataTest` covers addresses +and static images. A data symbol names storage, whereas a function symbol names +callable code; loading the former and calling the latter require different IR. + +Simple function pointers currently occupy four bytes. On AMD64, a native +function address names a low-address tail-jump thunk, which can reach native +code outside that range. A weak symbol gives static fields and computed +addresses the same entry across objects; direct calls can still use the native +PLT. This preserves constant initialization of function fields without storing +an eight-byte native address in a four-byte slot. The native linker must place +these Simple entries in the representable address range. + +Data pointers still occupy eight bytes. Compact code/data arenas and distinct +full-width native pointer types are [future designs](../roadmap.md#compact-code-and-data-arenas). + +## Runtime and examples + +`src/main/c/simple_crt.c` supplies the errno accessor and converts native process +arguments to Simple byte arrays for an exported `simple_main` function. This +explicit function entry is distinct from the language's class initializer: +the selected initializer still receives the integer `arg`. General class +initializer argument arrays remain a roadmap item. + +The executable examples live in +[`src/test/smp/examples`](../../src/test/smp/examples): Hello World, +Bubble Sort, Capitalize, Dijkstra, and FileIO. The existing Chapter25Test tests +compile and link them through the native harness. `make tests` builds the +library/runtime prerequisites and runs those checks; a Java-only build does +not produce the native prerequisites. + +The compiler's in-memory evaluator and the native driver have different entry +interfaces. Use the matching harness when comparing their results, especially +for programs taking an argument array or performing I/O. diff --git a/docs/appendices/optimizer-tuning.ja.md b/docs/appendices/optimizer-tuning.ja.md new file mode 100644 index 00000000..c3bbd2fa --- /dev/null +++ b/docs/appendices/optimizer-tuning.ja.md @@ -0,0 +1,26 @@ +# 最適化とバックエンドの調整 + +These measurements are from the numbered snapshots before the 2026-10 split. +In this historical table, Ch 24 means the retired combined SCCP snapshot and +Ch 25 means the retired combined modules/constructor/import snapshot. +They are not new measurements of the extracted chapters. The implementation +continues in [Separate Compilation](../chapter28b/README.md). + +## RegAlloc の改良: 生存区間の面積と分割コスト + +第24章はループ Phi の高頻度辺を分割する前に、低頻度のコピーを試しました。この章ではさらに、スピルがスケジュール済みコードのどれだけをレジスタ圧力から解放するかを推定し、新しいコピーの推定コストで割ります。callee-save 区間は関数全体を覆います。複製可能な定数は使用の近くで再構築できます。ループ内のコピーは高コストなので、`8^loopDepth` で重み付けします。特に多数の使用を持つ値については、低コストな近似です。 + +複数の固定レジスタ使用を直接分割する規則や、一部の複数定義区間をより深く分割する規則など、第25章のほかの衝突処理はここに残します。サイズのしきい値はヒューリスティックであり、最初の割り当て器へバックポートすべき一般的不変条件ではありません。共有される合法性修正は、引き続き最も早い該当章から始めます。最終監査は第20〜25章の固定隣接ノードの色バイアス、第20〜21章の狭いストアマスク、第21〜25章の ARM レジスタバンク／浮動小数点メモリエンコーディングを修正しました。 + +第21章の隣接コピー転送も引き継ぎます。次の命令だけで使うコピーは、オペランドがコピー元レジスタを受け入れ、命令の結果に結び付けられていなければ除去します。 + +現在の比較は、固定したテスト群を行、コンパイラの章を列にした +[英語版の測定表](optimizer-tuning.md#regalloc-improvements-live-range-area-and-split-cost) を参照してください。 +各セルは ARM/RISC-V の実行命令数、そのうち割り当て器が生成したコピーなどの命令数、 +x86 のループ重み付き移動数を示します。これらは異なる指標です。 +対象、入力、除外項目は [測定方法](../regalloc-spills.md) にあります。 +古い測定群の集計値と混ぜて比較しないでください。 + +クラス初期化、インライン化、エスケープ解析、ライブラリの変更もグラフを変えます。 +章をまたぐ差を割り当て器だけの品質差と解釈せず、同じ入力とコンパイラで +ヒューリスティックを比較してください。 diff --git a/docs/appendices/optimizer-tuning.md b/docs/appendices/optimizer-tuning.md new file mode 100644 index 00000000..88428df3 --- /dev/null +++ b/docs/appendices/optimizer-tuning.md @@ -0,0 +1,65 @@ +# Optimizer and backend tuning + +These measurements are from the numbered snapshots before the 2026-10 split. +In this historical table, Ch 24 means the retired combined SCCP snapshot and +Ch 25 means the retired combined modules/constructor/import snapshot. +They are not new measurements of the extracted chapters. The implementation +continues in [Separate Compilation](../chapter28b/README.md). + +## RegAlloc improvements: try cold loop splits first + +A loop Phi and its backedge can belong to one live range even though their +values must coexist at some instruction. This self-conflict requires splitting +the range. Chapter 23 split the Phi's definition and incoming values right away. +This chapter first leaves the hot definition/backedge alone and tries the +outside-loop copies. If coloring succeeds, it avoids moves on every iteration. +Other conflicts, including two-address operations, keep their existing handling. + +The allocator remembers which Phis have had this chance. If the same Phi +self-conflicts again, the next attempt uses the ordinary aggressive splitting. +The record uses Phi identity because live ranges are rebuilt each round. It +also covers a backedge-only conflict where the first attempt inserts no copy: +that attempt must still consume the one permitted delay. A regression checks +both the cheaper first attempt and the mandatory fallback. + +## RegAlloc improvements: live-range area and split cost + +Chapter 24 tried cold copies before splitting a loop Phi's hot edges. This +chapter also estimates how much scheduled code a spill frees from register +pressure, divided by the estimated cost of the new copies. Callee-save ranges +cover a whole function. Cloneable constants can be rebuilt nearer their uses. +Copies inside loops cost more: the estimate weights them by `8^loopDepth`. +These are inexpensive approximations, especially for values with many uses. + +A single-use function address in the same block gets priority for +rematerialization when it is separated from its use. Moving that address +calculation next to the use adds no instruction and avoids preserving a +callee-save register merely to hold the constant. Adjacent uses and multi-use +addresses retain the area/cost ranking. + +Rows are fixed test cohorts; columns are compiler chapters. Each cell gives +**Ops / RA / X**: executed ARM+RISC-V instructions, the subset emitted for +allocator copies/rematerializations, and x86's loop-weighted split-move estimate. +**Cases D / X** counts measured dynamic program/target cases and x86 compilations; +membership and inputs stay fixed across columns. Native-library work is excluded. +Chapter 20 has no encoder, hence no dynamic counts. Lower is better within each +metric; see the [measurement details](../regalloc-spills.md) for coverage. + +<!-- spill-matrix:start --> +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | Ch 25: Ops / RA / X | +|---|---:|---:|---:|---:|---:|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 58,965 / 9,076 / 208 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,196 / 219 / 534 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 252 / 92 / 11 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | 864 / 358 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | 4,646 / 1,335 / 609 | +| Ch 25 | 2 / 12 | | | | | | 20 / 0 / 1,856 | +<!-- spill-matrix:end --> + + +Chapter 25 introduces several features, which when run on the older tests +generate a lot more code, which in turn generates more spills. + +Class initialization, inlining, escape analysis, and library adaptations +all change the graphs. To help with this, we adjust the inlining +heuristics to try to inline and optimize the boilerplate. diff --git a/docs/appendices/reference-assets/font-awesome-4.7.0.zip b/docs/appendices/reference-assets/font-awesome-4.7.0.zip Binary files differnew file mode 100644 index 00000000..b6bdb4bd --- /dev/null +++ b/docs/appendices/reference-assets/font-awesome-4.7.0.zip diff --git a/docs/appendices/reference-assets/ifg_trim.pdf b/docs/appendices/reference-assets/ifg_trim.pdf Binary files differnew file mode 100644 index 00000000..d952fd4f --- /dev/null +++ b/docs/appendices/reference-assets/ifg_trim.pdf diff --git a/docs/appendices/reference-assets/lattice.gv b/docs/appendices/reference-assets/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/appendices/reference-assets/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/appendices/reference-assets/lattice.svg b/docs/appendices/reference-assets/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/appendices/reference-assets/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/appendices/reference-assets/lattice2.gv b/docs/appendices/reference-assets/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/appendices/reference-assets/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/appendices/reference-assets/lattice2.svg b/docs/appendices/reference-assets/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/appendices/reference-assets/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/appendices/reference-assets/pardoe.docx b/docs/appendices/reference-assets/pardoe.docx Binary files differnew file mode 100644 index 00000000..24fde921 --- /dev/null +++ b/docs/appendices/reference-assets/pardoe.docx diff --git a/docs/appendices/reference-assets/webtcp.min.js b/docs/appendices/reference-assets/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/appendices/reference-assets/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/docs/chapter-backports.md b/docs/chapter-backports.md new file mode 100644 index 00000000..1d5680f9 --- /dev/null +++ b/docs/chapter-backports.md @@ -0,0 +1,283 @@ +# Chapter backport queue + +This file tracks pending backports and deferred work. Completed work and old +validation results belong in Git history. Reusable implementation constraints +live in the [AI notes](../skills/chapter25-codex-notes.md). + +The [completed split](chapter-split.md) places local/interprocedural SCCP in +24a/24b, incomplete types in 25, construction in 26, escape in 27, and +modules/separate compilation in 28a/28b. The combined old 24/25 snapshots are +retired. Do not backport fixes into those retired copies; their replacements +already retain the constructor, alias, native-exposure and import fixes. + +Native library construction and tuning material live in [appendices](appendices/README.md). +Future incremental builds are specified in [incremental-builds.md](incremental-builds.md). + +## Four README intentions to review + +Keep these four issues visible while reviewing the named chapters. Decisions +may change the construction/escape boundary or later chapter splits. + +1. **Construction (active):** final fields should be local SSA values during + construction, including repeated assignments and loops, with field Stores + at helper exits. Silent loss of writes is a bug; reject unsupported cases. + Also decide whether to allow helpers after inlining and defer completion + checks until SCCP. Those are separate from local field updates. + The local-value implementation now supports final data fields in construction, + escape, and modules, including constant defaults and loop Phis. Shared + function declarations remain fixed. Validate this frontier before adjusting + the broader constructor rules. +2. **Privacy:** underscore names select the public interface, but sibling access + to private fields is not yet rejected. Confirm and enforce the intended + source access rules. The proposed chapter boundary and library changes are + recorded below; Cliff reviews that proposal before implementation. +3. **Class initialization:** review the corrected rule: A may start, initialize + B, then resume. Passive references may cycle; active dependencies may not. + Parents finish before children start. The README now matches this behavior; + further semantic changes need an explicit decision. +4. **Escape summaries and ELF visibility:** analysis tracks unknown callers, + while the current ELF writer exports retained named functions. Decide which + symbols should be public and how that boundary relates to separate compilation. + +### Privacy proposal for review + +Introduce enforced underscore privacy in **Modules and Lazy Class +Initialization** (`chapter28a`). This is a visible language change: +earlier snapshots allow underscore field access; from Modules onward, access +must obey the declaring class's boundary. The teaching outline already places +privacy here, alongside class names, ownership, and the public interface. +The earlier escape snapshot does not filter fields by underscore spelling. +Its private construction memory is a different concept. + +Review follow-up: preserve the distinction between export filtering and access +checks. Before the 2026-10-24 cleanup, the first underscore helper in the +numbered snapshots' tests was Chapter 19's `Chapter19Test.testString`, +`_hashCodeString`. Renaming it to +`hashCodeString` produces the identical LocalSched graph there: single-use +inlining removes it regardless of spelling. In Chapter 25's copy of that test, +the same rename retains an extra function Return. Underscore export filtering +currently starts in Chapter 25 (and its Modules extraction), not Chapter 19. +Old test class names inside newer snapshots do not identify when their current +underscore behavior was introduced. Any access-check change must preserve the +existing ability to hide helpers and classes from the public interface. +Chapter 19's example now uses `hashCodeString` and field `hashCode`; all 42 +Chapter19Test tests pass with the existing expected graph unchanged. + +Proposed rules: + +- A field or method beginning with `_` is accessible only from code in its + declaring class, including its constructors and method bodies. Enclosing, + nested, and sibling classes do not gain access to that field. A same-class + method may access another instance's private fields; the receiver need not + be exactly `self`. +- A private class name is available in its declaring scope and within the + class itself. For example, `App` may name its child `_Cache`, but that does + not grant `App` access to `_Cache._data`. Code outside that declaring scope + cannot bypass the restriction with a dotted path. Private ancestors also + keep their descendants out of the public interface. Check both type names + and class-value references, and distinguish naming a private class from + using a public value returned by a factory. +- Reads, writes, updates, and method references follow the same rule. + Preserve the source owner and location when receiver types are unresolved; + inlining must not change who has access. An unused result or a folded Load + must not erase an illegal source access. +- Native declarations obey the same source rules. A public wrapper or alias + may deliberately expose a private native binding; no exception for `sys`. + +Source audit: + +- `sys/io.smp` calls `libc._exit` twice. Keep the native `_exit` declaration + private in `sys/libc.smp`, add `val exit = { i32 status -> _exit(status); };`, + and use `libc.exit` in IO. This preserves the native symbol and behavior. +- Bitset's `_bits` and `_grow`, including `_grow(bit)._bits`, are used within + the declaring struct and remain legal. Array helpers call their own `_grow`. + These are the other underscore names in the bundled module library. +- Several retained String spill fixtures use free functions outside `_String` + to access `_hashCode`. They will need an explicit adaptation in this snapshot + (for example, making that fixture field public), with any changed allocation + expectations measured. Do not silently grant file-wide access to pass them. +- The numbered Chapter 25 library has the same `_exit` accesses, and its + `docs/examples/FileIO.smp` also calls `sys.libc._exit`. + +After approval, implement and test in Modules, update its English/Japanese +READMEs with the explicit language boundary, and run the full module suite +including bundled `sys` and native execution. Cover allowed same-class access, +rejected cross-class access, private class lookup, and forward receiver types. +Carry the rule and library adaptations into Chapter 28b, with import tests +preserving the original source owner. Do not backport the new +language restriction into Chapters 10-24 or the named pre-module snapshots. + +## Investigate next + +Establish an earlier-chapter failure before changing compiler behavior. + +### Prefix update of an enclosing class field + +The following returns 11 instead of 21 in numbered Chapter 25, Modules, and +Separate Compilation: + +```simple +int calls=0; +val next_noInline={ -> ++calls; }; +return next_noInline()+10*next_noInline(); +``` + +The prefix path updates an enclosing parser slot instead of class memory. +Postfix `calls++; return calls;` works and is used in the new chapter example. +This is independent of importing IR. The stage audit also reproduced the +instance-method form in Chapter 23, where methods first appear: + +```simple +struct C { int x=0; val inc={ -> ++x; }; }; +var c=new C; +return c.inc()+10*c.inc(); +``` + +It returns 11 instead of 21 in Chapters 23 and 26. Prefix lookup bypasses the +ordinary field-access path. A fix should share name resolution with other +reads/updates while preserving constructor locals, and propagate from 23 +through 28b. No fix is included in the numbering change. + +### Constructor loop with break/continue: worklist assertion + +This fails in construction and in the unchanged escape compiler before the +final-field fix, even with a mutable field: + +```simple +struct C { + int x=0; + new C={int n -> + for(int i=0;i<n;i++) { + if(i==1) continue; + if(i==3) break; + x+=i+1; + } + }; +}; +return new C(arg).x; +``` + +`IterPeeps.progressOnList` asserts during Iter with seed 123. The expected value +for arg 3 is 4. This is independent of final-field mutability; retain the +reproducer while reviewing constructor coverage. Scratch probe: +`build/readme-review/mutable_break.smp`. + +### SCCP function revival: Chapter 24 + +`Opto.linkCG` uses `code.link(fidx)`, which clears a linker entry when its +function is structurally dead. Chapter 25 uses the non-cleaning `_link(fidx)` +while discovering calls, so temporarily disconnected functions can be revived. +Chapter 24 already has `_link`; the question is whether its own unlinking and +SCCP sequence can expose the same failure. + +Trace a function from removal of its unknown-caller edge through discovery of +a real call. Preserve the distinction between unreachable control and a +structurally deleted node. No earlier-chapter failure is established yet. +Dependency propagation already exists in Chapter 24's SCCP; only port a +specific missing dependency with a reproducer. Keep Chapter 25's escape and +external-caller machinery out of this investigation. + +Investigation on 2026-10-19 found no cleanup loss. A shadow Opto checked the +linker entry before and after every `linkCG` lookup while running all 513 +Chapter 24 tests: 787 SCCP runs, 297 lookups, 74 links to functions with only +their null input remaining, and zero structurally dead targets or removed +entries. All tests passed. The remaining null lookups are not evidence of a +cleanup loss: their entries were already null before the lookup. + +The factorial trace shows the distinction: FunNode#1309 loses Start and has +one input, four uses, and type TOP; it then reaches XCONTROL before a real +call links it. `isDead()` stays false, since it requires no inputs, no uses, +and a null type. Thus the observed temporary lack of callers does not trigger +`link()` cleanup. Keep this candidate unconfirmed rather than backporting the +Chapter 25 lookup change on textual differences alone. + +## Future compiler work + +### Deterministic inlining + +The parse-size cutoff can reject a function whose optimized body is small. +After shrinking rewrites converge, choose one growing inline using current +body sizes and a deterministic ranking. Cache sizes per convergence round; +use stable call-site provenance to break ties, not worklist order or newly +allocated node IDs. Avoid per-node dependencies and repeated whole-body scans +while a large function gradually shrinks. + +The bounded boilerplate-inlining heuristic is already in Chapters 20-24. +This item is the larger Chapter 25 redesign. + +### Conversion and BOTTOM-on-error contracts + +Coordinate these changes with the incomplete-type/conversion split: + +- Chapter 24 Loads supply a typed result even when they report an error. + Changing that result to BOTTOM alone breaks incomplete loop typing and can + obscure the intended diagnostic. Chapter 25's Convert nodes provide the + surrounding typed result. Relevant existing cases include + `testBrainFuck`, `testWhileWithNullInside`, `testNullGuardErrors`, and + `testLinkedList0`. +- Chapter 24 arithmetic also needs its typed fallback while forward references + are unresolved. Returning BOTTOM confuses unresolved expressions with + uninitialized fields (`testCoRecur`) and loses arithmetic diagnostics. + +Preserve the current contracts until the parser, conversions, loop bounds, +and diagnostics can move together. Do not weaken narrowing assertions or +expected errors to make an isolated backport pass. + +### Representation changes + +The approved split keeps incomplete types, numeric modes, conversions, guards, +and symbolic fields together, then introduces private constructor memory in +the construction chapter. They are not independent fixes to copy into earlier +snapshots. + +Serialization, global identity remapping, and imported escape summaries belong +with separate compilation. Escape analysis now has its own earlier snapshot after +construction; keep its boundary open to review. + +### Selective loading of library IR + +Reliable incremental rebuilding is separate future work; see the +[incremental build design](incremental-builds.md) for the stale-dependency +example, required input tracking, rebuild propagation, and validation plan. + +The Separate Compilation README review found that importing only `sys.io.p` +still loads all ten units in the bundled `sys.o`, including `aryu8`, `aryi64`, +`scan`, and `adt.bitset`. All remain loaded through TypeCheck. Loading only +needed library members is a desired improvement, not current behavior. + +Selection works between independent objects: a client of `Counters.o` leaves +an unrelated `Unused.o` unloaded. Once selected, an object's entire saved IR +is reconstructed, and `ParseAll.loadDeps` follows its recorded dependencies. +Splitting the object alone is insufficient while the root's reexports and +unused function bodies still pull in those dependencies. Design member-level +IR loading and dependency discovery together; preserve type identity, +initialization rules, and imported escape summaries. This is separate from +whether imported code is initialized or emitted in the client's object. + +## Modules and separate compilation + +Class-cycle checking and CLInit runtime lowering belong in 28a/28b. The +[module README](chapter28a/README.md) explains their semantics; remaining +argument, initialization and pointer plans live in the [roadmap](roadmap.md). +Native code cannot receive classes; a native-startup/class-handoff policy is +not planned. Current data pointers remain eight bytes. + +## Backport validation + +Introduce an independent fix in the earliest applicable chapter and propagate +it through every affected snapshot. For correctness fixes, first reproduce the +failure in the destination compiler. Preserve each chapter's representation +and tutorial boundary. + +Run focused checks and the existing full Make suites for the affected compiler +directories, for example: + +```sh +make -k tests CHAPTERS="chapter20 chapter21" +``` + +Chapter 25's inherited tests do not validate earlier compiler implementations. +Force rebuilds when older Makefiles miss dependencies, and rebuild serialized +libraries when their compiler or object format changes. Keep execution and +register-legality checks independent of spill expectations. Preserve unrelated +edits, keep text LF-only, and run `git diff --check`. diff --git a/docs/chapter-split.md b/docs/chapter-split.md new file mode 100644 index 00000000..7b2ffdf2 --- /dev/null +++ b/docs/chapter-split.md @@ -0,0 +1,220 @@ +# Approved chapter split + +Cliff approved the seven-part split on 2026-10-19 and the final numbering on +2026-10-24. The old combined Chapters 24 and 25 are retired; their history is +available in Git. Every new directory is a complete compiler snapshot. + +| Previous directory | Final chapter | +|---|---| +| chapter-sccp | 24a: SCCP within a function | +| chapter-interprocedural-sccp | 24b: SCCP across functions | +| chapter-incomplete-types | 25: SSA before types are known | +| chapter-construction | 26: Construction and private memory | +| chapter-escape | 27: Escape analysis and unknown callers | +| chapter-modules | 28a: Modules and lazy class initialization | +| chapter-separate-compilation | 28b: Separate compilation | + +Keep 17a/17b. The other paired chapters extend one idea: 24a/24b goes from +local to interprocedural SCCP; 28a/28b goes from compiling modules together to +compiling them independently. Construction and escape remain separate topics; +neither is presented as requiring the other. + +Inherited Java test names such as `Chapter24Test` and `Chapter25Test` retain +their historical identities across snapshots. They are regression cohorts, +not an index of the current teaching sequence. Historical allocator tables +also retain their original labels and dates. + +Native library construction and optimizer tuning are now [appendices](appendices/README.md). +The [roadmap](roadmap.md) and [backport queue](chapter-backports.md) own future work. + +The teaching pattern is to introduce a difficult idea, then show how to make +it useful in a larger setting. Each chapter must remain a complete, runnable +compiler snapshot that preserves the language supported by its predecessor. + +## Teaching sequence + +| Topic | Main idea | Endpoint | +|---|---|---| +| SCCP within a function | Optimistic types, reachable control, Phi inputs, worklists, fixed points, and loop widening. Keep calls conservative at their interfaces. | Fold loop-carried values and eliminate branches that pessimistic iteration cannot resolve. | +| SCCP across functions | Discover call edges during analysis; merge arguments and returns; account for unknown callers and function pointers. | Specialize parameters, resolve call targets, handle recursion, and remove unreachable functions. | +| SSA before types are known | Syntax and lexical binding choose graph shape. Keep scalar types, deferred numeric modes, conversions, guards, incomplete objects, symbolic fields, and removal of parser-supplied Load/Phi bounds together. | Compile forward definitions without provisional types determining graph topology; settle types and layouts afterward. | +| Construction and private memory | Allocation helpers, hidden initializers, user constructors, private self-memory, field-completion checks, and explicit publication. | Preserve initialization and memory facts through constructor calls and publish a completed object. | +| Escape analysis and unknown callers | Discover which aliases and functions can reach code outside the known graph. | Preserve exposed memory and callable functions while specializing private code. | +| Modules and lazy class initialization | Multiple source files, namespaces, privacy, ownership, singleton storage, first-use initialization, parent order, cycle diagnostics, and lowering. | Compile sources together with defined class-initialization behavior. | +| Separate compilation | Preserve types, ideal IR, and identities across independent compilations. | Build a library and client separately, optimize imported bodies, link remaining calls, and check initialization dependencies across imports. | + +The first incomplete-type chapter stays together. Its unresolved memory accesses +must work before construction introduces private memory; defer the private +construction protocol, not the machinery required to represent an unknown access. + +## SCCP boundary + +The first SCCP snapshot keeps unknown-caller Start inputs and disconnects call +edges during the optimistic solve. Parameters retain their declared types; +call results retain facts from the preceding pessimistic pass, which can be +sharper than the written signature. Calls still have whole-memory effects. +After SCCP, peepholes relink calls and FinalizeIR removes uncalled bodies while +preserving named exports. This is an intermediate compiler design, not a +textual division of Opto.java. + +Ordinary loop widening belongs in the first chapter. The second adds argument +and result widening for recursion. Use `f(x-1)+1` to explain why these are +separate data cycles: the recursive return value never crosses Parm(x). + +Chained comparisons do not need their own chapter. Their home is +beside Chapter 23 short-circuit expressions: evaluate each operand +once and evaluate later operands only when earlier comparisons succeed. +The current Chapter 24 cold-loop-split allocator improvement belongs with the +tuning appendix. + +## Construction and escape boundary to establish + +Separate an explicit memory-publication operation from the analysis that +discovers exposure to unknown code. + +| Construction chapter | Escape-analysis chapter | +|---|---| +| Tracks private memory while an object is built. | Tracks aliases and functions exposed through memory, calls, and returns. | +| Publishes initialized memory at an explicit boundary. | Propagates exposure through the reachable graph. | +| Conservatively preserves unknown callers for surviving function addresses, following the current Chapter 24 policy. | Uses escape facts to determine which functions need unknown callers. | +| Explains EscapeNode as a publication operation. | Explains the Start/Stop feedback cycle between known code and the external world. | + +Verify this split against constructor calls and memory summaries. The earlier +snapshot can publish conservatively; the later one refines that behavior. +The name EscapeNode does not require teaching the full escape analysis at +the point where publication is introduced. + +`chapter26` now implements that explicit boundary. Hidden initializer +and allocator functions carry whole private object memory; completion publishes +fields into public aliases. The new constructor functions reject early passing +or storing of `self`, including self-links, and access through a merged alias. +These are deliberate limits for review with the next escape snapshot. Normal +function addresses retain conservative unknown callers. Initializers capture +enclosing values as hidden arguments; writing back to captures is rejected. +Arrays follow the same construction/publication protocol. There are no modules +or class singletons in this snapshot. + +Review on 2026-10-22 removed an unnecessary representation detour. Constructor +fields now stay in local SSA values and ordinary Phis; helpers emit ordinary +Stores at exit, with precise aliases gathered in MemMerge. Private memory is +only the handoff between helpers and publication. No global escape discovery +is needed to build that representation. + +Construction and escape discovery need not be taught in this order. Keep the +current order provisionally, without inventing a constructor example to claim +that dependency. The callback example now lives in the EA chapter. + +## Modules before separate compilation + +Teach module semantics with all source files compiled in one invocation. +Include lazy initialization, parent requirements, and cycle checking there. +Separate compilation then adds serialized ideal IR and types, GlobalBits +identity remapping, imported type reconstruction and analysis, and Unlink +before machine compilation. Extend initialization checks across imported +bodies, preserving opaque CLInit nodes until lowering. + +Keep code ownership distinct from unknown-caller edges in both chapters. +Keeping a function for emission must not imply arbitrary callers can reach it. + +## Appendices and future work + +- Native library construction: numeric C data symbols, address handling, + modular sys, runtime and driver support, and larger examples. Preserve the + native functionality already taught in earlier chapters. +- Optimizer and backend tuning: existing cloning/inlining choices, spill + ranking by live-range area and copy cost, rematerialization, and splitting + policies. Compare equivalent programs when explaining costs. + +This split organizes implemented behavior. Deterministic inlining, argument +arrays, static pre-initialization of classes, CFG frequency estimates, and +constant instance-field storage remain future work. See the +[backport queue](chapter-backports.md) and [roadmap](roadmap.md). + +## Renumbering and validation + +The first runnable extractions are +[SCCP Within a Function](chapter24a/README.md) and +[SCCP Across Functions](chapter24b/README.md), followed by +[SSA Before Types Are Known](chapter25/README.md), +[Construction and Private Memory](chapter26/README.md) and +[Escape Analysis and Unknown Callers](chapter27/README.md), and +[Modules and Lazy Class Initialization](chapter28a/README.md), and +[Separate Compilation](chapter28b/README.md). +All seven main snapshots are extracted and numbered. Chained comparisons now +start in Chapter 23 beside short-circuit expressions. The linear-history +publisher follows the numbered directories, including lettered pairs. + +Validate each intermediate compiler with its own Make suite, including execution +checks. Keep declarations, conversions, diagnostics, and type bounds consistent; +do not weaken checks to make an intermediate snapshot pass. Rebuild serialized +libraries when their compiler or object format changes. + +## Escape snapshot ready for boundary review + +`chapter27` adds function/alias exposure sets to TypeMem and closes the +Start/Stop feedback cycle during SCCP. Known calls propagate memory summaries; +exposed returns, fields, external arguments and native calls discover further +addresses. Native calls contribute even on paths with no live Return. Function +addresses kept entirely in known code no longer imply unknown callers. + +The [recursive callback example](chapter27/README.md) now belongs in +that chapter. Its base parameter becomes 2 while recursive calls remain. +Returning the callback or a containing object, or handing it to native code, +restores conservative arguments. FinalizeIR separates those analysis facts +from the roots needed to emit code. + +Construction still keeps local field values and rejects early exposure of self. +Both runnable snapshots are available for Cliff's promised review/play session. +This extraction does not choose broader rules for partially initialized objects. +No modules, class singletons, serialized IR or identity remapping are included. + +## Modules snapshot ready for review + +`chapter28a` compiles all discovered source files together. It adds class +singletons, namespaces and export filtering, parent initialization, CLInit memory effects, +cycle diagnostics, runtime lowering, and shared native class storage. Source +discovery reads parents as well as referenced children. The bundled modular sys +is supplied as source; building reusable libraries remains appendix material. + +There is no Serialize phase, object reader, GlobalBits remapping, or imported +IR. LocalIds assigns dense IDs within the invocation. FinishCalls detaches +analysis call edges after loop analysis, before scheduling or instruction +selection. ELF emits all discovered live bodies in the selected entry object. + +The preceding construction representation remains: field values and loop Phis +stay local, with Stores at helper exits. Constructor reads may see an unfinished +object, but may never read an uninitialized field. The module snapshot checks +this separately from completion and publication. Escape analysis still restores +unknown callers when a private callback reaches native code, including on paths +with no Return. + +The README's lazy lookup-table example is executable. Existing tests also cover +source/type cycles, rejected initialization cycles, parent order, native cold/hot +calls, shared storage, and ARM/RISC-V encoding. The construction/escape border +remains open to Cliff's review; this extraction does not settle broader rules for +publishing unfinished objects. + +## Separate compilation snapshot ready for review + +`chapter28b` adds saved types and ideal IR, `GlobalBits` +identity remapping, object discovery, imported bodies, and `Unlink`. It carries +Modules' deferred constructor parsing, local final-field values and loop Phis, +converted private memory summaries, native callback exposure, and source-parent +initialization order. Source privacy enforcement remains a separate review. + +The runnable example compiles a library and a client from separate source roots. +The client allocates an imported struct whose constructor updates a final field +in a loop, then calls a retained library function that updates shared state. +The regression checks evaluation under three seeds and native cold/repeated +calls. A second import test preserves unknown callers for a callback passed to +native code. Existing import tests retain initialization-cycle diagnostics, +shared class data, public type reconstruction, and native function thunks. + +Serialization now saves the class declarations of owned nested structs even +when they are absent from the optimized graph's type closure. Otherwise a +client can load the instance type but cannot find its allocation signature. +An explicit source input is always recompiled; dependency objects may still +be reused. The old incremental-rebuild experiment remains ignored. + +All seven main teaching boundaries now have numbered snapshots. Broader +language choices and compiler improvements remain in the review queue. diff --git a/docs/chapter01/01-grammar.ja.md b/docs/chapter01/01-grammar.ja.md new file mode 100644 index 00000000..f0a91ee1 --- /dev/null +++ b/docs/chapter01/01-grammar.ja.md @@ -0,0 +1,32 @@ +# 第1章の文法 + +[English](01-grammar.md) | 日本語 + +この文書は [第1章の文法定義](01-grammar.md) の日本語版です。文法定義そのものは原文と同一です。 + +[第1章：導入に戻る](README.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement EOF + ; + +statement + : 'return' expression ';' + ; + +expression + : primaryExpression + ; + +primaryExpression + : INTEGER_LITERAL + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; +``` diff --git a/docs/chapter01/01-grammar.md b/docs/chapter01/01-grammar.md new file mode 100644 index 00000000..1fe965cb --- /dev/null +++ b/docs/chapter01/01-grammar.md @@ -0,0 +1,28 @@ +# Grammar for Chapter 1 + +English | [日本語](01-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +program + : statement EOF + ; + +statement + : 'return' expression ';' + ; + +expression + : primaryExpression + ; + +primaryExpression + : INTEGER_LITERAL + ; + +INTEGER_LITERAL + : [1-9][0-9]* + | [0] + ; +``` diff --git a/docs/chapter01/01-graph.gv b/docs/chapter01/01-graph.gv new file mode 100644 index 00000000..df256f52 --- /dev/null +++ b/docs/chapter01/01-graph.gv @@ -0,0 +1,17 @@ +digraph chapter01 { +/* +return 1; +*/ + rankdir=BT; + ordering="in"; + concentrate="true"; + subgraph cluster_Nodes { + Start1 [ shape=box style=filled fillcolor=yellow label="Start" ]; + Con_2 [ label="#1" ]; + Return3 [ shape=box style=filled fillcolor=yellow label="Return" ]; + } + edge [ fontname=Helvetica, fontsize=8 ]; + Con_2 -> Start1[taillabel=0 style=dotted]; + Return3 -> Start1[taillabel=0 color=red]; + Return3 -> Con_2[taillabel=1]; +} diff --git a/docs/chapter01/01-graph.json b/docs/chapter01/01-graph.json new file mode 100644 index 00000000..f489c4fe --- /dev/null +++ b/docs/chapter01/01-graph.json @@ -0,0 +1,14 @@ +{ + "ver": 1, + "comp": "chapter01/docs/01-graph.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "Start", "type": null, "kind": "CTRL", "edges": [], "proj": null}, + {"id": 2, "label": "#1", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 1, "role": "ASSOC", "label": null}], "proj": null}, + {"id": 3, "label": "Return", "type": null, "kind": "CTRL", "edges": [{"idx": 0, "def": 1, "role": "CTRL", "label": null}, {"idx": 1, "def": 2, "role": "DATA", "label": null}], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter01/01-graph.svg b/docs/chapter01/01-graph.svg new file mode 100644 index 00000000..6f1d8204 --- /dev/null +++ b/docs/chapter01/01-graph.svg @@ -0,0 +1,73 @@ +<svg aria-label="Compiler graph" width="320" height="208" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 320 208" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge ASSOC" id="e2i0" d="M84,77 C84,101 236,3 236,27" stroke="#9396a3" marker-start="url(#arrow-ASSOC)" style="opacity: 1;"><title>#2[0] → #1 · ASSOC</title></path><path class="edge CTRL" id="e3i0" d="M84,80 L84,128" stroke="#b63838" marker-start="url(#arrow-CTRL)" style="opacity: 1;"><title>#3[0] → #1 · CTRL</title></path><path class="edge DATA" id="e3i1" d="M236,80 L236,85 Q236,90 231,90 L132,90 Q124,90 124,98 L124,128" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#3[1] → #2 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,30)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Start</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 Start +Type not computed + +</title></g><g class="node" id="n2" data-id="2" transform="translate(176,30)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>#1</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 #1 +Type not computed + +[0] → #1 ASSOC</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n3" data-id="3" transform="translate(44,134)" style="opacity: 1;"><path class="box" d="M0,0H120V44H0Z" fill="#fff1c4"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>Return</tspan><tspan class="node-id"> #3</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#3 Return +Type not computed + +[0] → #1 CTRL +[1] → #2 DATA</title><circle class="port" cx="40" cy="-3" r="3" fill="#536477"/><circle class="port" cx="80" cy="-3" r="3" fill="#536477"/><text class="slot" x="40" y="-10" text-anchor="middle">0</text><text class="slot" x="80" y="-10" text-anchor="middle">1</text></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter01/01-use-def.gv b/docs/chapter01/01-use-def.gv new file mode 100644 index 00000000..d0e84ecb --- /dev/null +++ b/docs/chapter01/01-use-def.gv @@ -0,0 +1,7 @@ +digraph chapter01 { + rankdir=BT; + subgraph cluster_Nodes { + A, B; + } + A -> B; +} diff --git a/docs/chapter01/01-use-def.json b/docs/chapter01/01-use-def.json new file mode 100644 index 00000000..5e6f2df6 --- /dev/null +++ b/docs/chapter01/01-use-def.json @@ -0,0 +1,13 @@ +{ + "ver": 1, + "comp": "chapter01/docs/01-use-def.svg", + "step": 1, + "roots": [], + "scope": 0, + "nodes": [ + {"id": 1, "label": "A", "type": null, "kind": "DATA", "edges": [{"idx": 0, "def": 2, "role": "DATA", "label": null}], "proj": null}, + {"id": 2, "label": "B", "type": null, "kind": "DATA", "edges": [], "proj": null} + ], + "groups": [ + ] +} diff --git a/docs/chapter01/01-use-def.svg b/docs/chapter01/01-use-def.svg new file mode 100644 index 00000000..b0ecd3da --- /dev/null +++ b/docs/chapter01/01-use-def.svg @@ -0,0 +1,69 @@ +<svg aria-label="Compiler graph" width="168" height="202" xmlns="http://www.w3.org/2000/svg" viewBox="0 0 168 202" style="font-family: sans-serif;"><style> + html, body { height:100%; margin:0; font-family:sans-serif; } + .viewer { height:100%; display:grid; grid-template-rows:auto minmax(0,1fr) auto; } + .source { padding:8px; border-bottom:1px solid #ccc; } + #program { width:min(600px,80vw); vertical-align:middle; } + #status { margin-top:4px; } + #graph { min-height:0; overflow:hidden; position:relative; background:#fafbfc; } + #elk { width:100%; height:100%; } + #graph svg { display:block; } + .tools { display:flex; flex-wrap:wrap; align-items:center; gap:14px; margin-top:8px; font-size:12px; } + .hint { color:#616c78; } + .ctrl { color:#b63838; } .mem { color:#2867b2; } .data { color:#536477; } + .edge { fill:none; stroke-width:1.5; } + .edge.CTRL { stroke-width:2; } + .edge.ASSOC { stroke-dasharray:4 4; } + .edge.PARSER { stroke-dasharray:5 4; } + .parser rect { fill:#f6f0ff; stroke:#7956a5; stroke-width:1.5; stroke-dasharray:5 4; } + .edge.selected { stroke-width:3.5; } + .edge.bundle { stroke-width:4; } + .edge.bundle.selected { stroke-width:6; } + .edge-hit { fill:none; stroke:transparent; stroke-width:12; vector-effect:non-scaling-stroke; pointer-events:stroke; cursor:pointer; } + .edge-jump { fill:transparent; pointer-events:all; cursor:pointer; } + .node { cursor:pointer; } + .box { stroke:#758191; stroke-width:1; } + .node.held .box { stroke-dasharray:5 3; } + .node.near .box { stroke:#c18221; stroke-width:2; } + .node.focus .box { stroke:#9c4900; stroke-width:3; } + .node.selected .box { stroke:#1569b9; stroke-width:3; } + .node.folded .box { stroke-width:4; } + .node.folding .box { fill:#f4ccd7; } + .fold-tag { font-size:9px; font-weight:700; fill:#963751; } + .peep-area { fill:#fff3d9; fill-opacity:.8; stroke:#c18221; stroke-width:2; pointer-events:none; } + .node.peep-edit .box { stroke:#9c4900; stroke-width:3; } + .node.error .box { stroke:#b42318; stroke-width:4; } + #event.error { color:#b42318; font-weight:600; white-space:pre-wrap; overflow-wrap:anywhere; } + .peep-ghosts { pointer-events:none; } + .region-box { stroke:#9da9b8; stroke-width:1.5; } + .fold-btn { cursor:pointer; } + .fold-btn rect { fill:white; stroke:#596674; } + .fold-btn text { font-size:14px; fill:#152330; } + .fold-btn:focus rect { stroke:#1569b9; stroke-width:2; } + .shortcut { cursor:pointer; } + .shortcut path { fill:none; stroke-width:1.5; } + .shortcut rect { fill:#fff8ec; stroke:#b63838; stroke-dasharray:3 2; } + .shortcut text { font-size:11px; fill:#783030; } + .shortcut.selected rect, .shortcut:focus rect { stroke-width:2.5; } + .label { font-size:12px; fill:#152330; font-weight:600; } + .node-id { font-size:10px; fill:#596674; font-weight:400; } + .type { font-size:11px; fill:#455768; } + .port { stroke:#536477; stroke-width:1; } + .row { stroke:#b6afcf; stroke-width:1; } + .bind { font-size:12px; fill:#152330; } + .slot { font-size:10px; fill:#364352; paint-order:stroke; stroke:#fafbfc; stroke-width:3; } + #detail { position:absolute; top:8px; right:8px; margin:0; padding:12px; max-width:320px; + max-height:45%; overflow:auto; white-space:pre-wrap; overflow-wrap:anywhere; + background:#fffffff2; border:1px solid #bac5d0; border-radius:4px; font-size:12px; } + .controls { display:flex; flex-wrap:wrap; justify-content:center; align-items:center; gap:6px; padding:6px; } + .button { color:white; background:black; font-size:20px; min-width:30px; } + .button:disabled { background:grey; } + .count { font-size:20px; min-width:35px; text-align:center; } + #N { width:6ch; } + #scrub { width:clamp(120px,35vw,600px); } + </style><defs><marker id="arrow-CTRL" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#b63838"/></marker><marker id="arrow-DATA" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#536477"/></marker><marker id="arrow-MEM" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#2867b2"/></marker><marker id="arrow-ASSOC" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#9396a3"/></marker><marker id="arrow-PARSER" viewBox="0 -4 8 8" refX="8" refY="0" markerWidth="7" markerHeight="7" orient="auto-start-reverse"><path d="M0,-4L8,0L0,4Z" fill="#7956a5"/></marker></defs><rect width="100%" height="100%" fill="rgb(250, 251, 252)"/><g><g class="regions" style="opacity: 1;"/><rect class="peep-area" rx="36" style="opacity: 0;"/><g class="edges"><path class="edge DATA" id="e1i0" d="M84,74 L84,122" stroke="#536477" marker-start="url(#arrow-DATA)" style="opacity: 1;"><title>#1[0] → #2 · DATA</title></path></g><g class="edge-hits"/><g class="parser" style="opacity: 1;"/><g class="nodes"><g class="node" id="n1" data-id="1" transform="translate(24,128)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>A</tspan><tspan class="node-id"> #1</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#1 A +Type not computed + +[0] → #2 DATA</title><circle class="port" cx="60" cy="-3" r="3" fill="#536477"/><text class="slot" x="60" y="-10" text-anchor="middle">0</text></g><g class="node" id="n2" data-id="2" transform="translate(24,24)" style="opacity: 1;"><path class="box" d="M14,0H106Q120,0 120,14V30Q120,44 106,44H14Q0,44 0,30V14Q0,0 14,0Z" fill="#edf3f7"/><text class="label" text-anchor="middle" x="60" y="18"><tspan>B</tspan><tspan class="node-id"> #2</tspan></text><text class="type" text-anchor="middle" y="35" x="60"/><title>#2 B +Type not computed + +</title></g></g><g class="region-heads" style="opacity: 1;"/><g class="shortcuts" style="opacity: 1;"/><g class="peep-ghosts" pointer-events="none"/></g></svg> diff --git a/docs/chapter01/Makefile b/docs/chapter01/Makefile new file mode 100644 index 00000000..6fa0f057 --- /dev/null +++ b/docs/chapter01/Makefile @@ -0,0 +1 @@ +include ../../graph/docs.mk diff --git a/docs/chapter01/README.ja.md b/docs/chapter01/README.ja.md new file mode 100644 index 00000000..43a1027f --- /dev/null +++ b/docs/chapter01/README.ja.md @@ -0,0 +1,197 @@ +# 第1章：導入 + +[English](README.md) | 日本語 + +この文書は [Chapter 1: Introduction](README.md) の日本語訳です。 + +[はじめに](../../README.ja.md) | +[次の章：第2章](../chapter02/README.ja.md) + +# 目次 + +1. [実装言語](#実装言語) +2. [前提](#前提) +3. [アーキテクチャ](#アーキテクチャ) +4. [ノードのグラフとしての中間表現](#ノードのグラフとしての中間表現) +5. [ノードはグラフを構成する](#ノードはグラフを構成する) +6. [ノードの種類](#ノードの種類) +7. [一意なノード ID](#一意なノード-id) +8. [Start ノード](#start-ノード) +9. [Constant ノード](#constant-ノード) +10. [Return ノード](#return-ノード) +11. [表現](#表現) +12. [参考文献](#参考文献) + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチの直線的な Git の変更履歴をたどって +[この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter01)を読むこともできます。 + +この章では、次のような単純なスクリプトをコンパイルすることを目指します。 + +``` +return 1; +``` + +`return` 文を実装します。`return` 文は引数として `expression` を受け取ります。 +上の例のように、扱える `expression` の種類は整数リテラルだけです。 + +この単純な言語を実装するために、いくつかの主要な構成要素とデータ構造を導入します。 + +この章の[言語の文法全体](01-grammar.ja.md)はこちらです。 + +## 実装言語 + +実装言語は Java です。広く利用でき、多くの人に知られているため、Java を選びました。 + +## 前提 + +読者が従来の線形な中間表現を理解し、基本ブロック（Basic Block）や +制御フローグラフ（Control Flow Graph）などの用語に馴染みがあることを前提としています。 +ここではこれらの話題を説明しません。必要であれば、標準的なコンパイラの教科書を参照してください。 + +## アーキテクチャ + +言語を解析しながら、Sea of Nodes（SoN）の中間表現を直接構築します。 +抽象構文木（AST）による表現は作りません。これは SoN IR の大きな利点の1つ、 +つまり言語の解析中にさまざまな悲観的ピープホール最適化を行えることを示すためです。 +この点は[第2章](../chapter02/README.ja.md)以降でさらに詳しく説明します。 +最終的には、型解析のパスを必要とせずに、プログラム全体の型付けができるようになります。 + +### ノードのグラフとしての中間表現 + +中間表現は Node オブジェクトのグラフです。`Node` クラスは、IR グラフ内のオブジェクトの基底型です。 +`Node` クラスは、すべてのサブタイプに継承される共通機能を提供します。 +サブタイプは、それぞれに対応する意味を実装します。たとえば、AddNode は加算し、MulNode は乗算します。 + +各 `Node` は、従来の IR に現れるような「命令」を表します。 + +### ノードはグラフを構成する + +Sea of Nodes IR の中心的な考え方は、各ノードが定義と使用（def-use）の依存関係によって +ほかのノードと結ばれていることです。これは IR の非常に重要で基本的な側面なので、 +その実装方法と、グラフ図での表し方を理解することが重要です。 + +基底クラス `Node` は、そのノードへの入力となるノードのリストを保持します。 +入力とは、「使用（use）」から「定義（def）」へのエッジです。 +つまり、`B` が定義で、`A` が `B` を使用する場合、`B` には `B` から `A` への def→use エッジがあり、 +それに対応して `A` には `A` から `B` への入力の use→def エッジがあります。 + +図では、「使用」から「定義」への矢印を描きます。次はその例です。 + + + +実装では、`Node` 型は両方向のリンクを保持します。上の例では、次のようになります。 + +* `A` は `B` の「使用」なので、`B` は `A` の入力リストに含まれます。 +* 逆に、`B` は出力リストを保持し、そのリストには `A` が含まれます。 +* これらのエッジが常に対応していることが、重要な不変条件です。 + +`Node` クラスでは、次のようになっています。 + +```java +public abstract class Node { + + /** + * Inputs to the node. These are use-def references to Nodes. + * <p> + * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * Ordering is required because e.g. "a/b" is different from "b/a". + * The first input (offset 0) is often a Control node. + */ + public final ArrayList<Node> _inputs; + + /** + * Outputs reference Nodes that are not null and have this Node as an + * input. These nodes are users of this node, thus these are def-use + * references to Nodes. + * <p> + * Outputs directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantic meaning. + */ + public final ArrayList<Node> _outputs; +} +``` + +### ノードの種類 + +中間表現には、2種類のノードがあります。 + +* **制御ノード**：コンパイルしたプログラムの制御フローグラフ（CFG）を表します。 +* **データノード**：データの意味を表します。 + +この章には、次の制御ノードとデータノードが登場します。 + +| ノード名 | 種類 | 説明 | 入力 | 値 | +|----------|------|------|------|----| +| Start | 制御 | 関数の開始 | なし | まだ関数の引数がないため、現時点ではなし | +| Return | 制御 | 関数の終了を表す | 先行する制御ノードと、値を供給するデータノード | 関数の戻り値 | +| Constant | データ | 整数リテラルなどの定数を表す | なし。ただし、グラフをたどれるように Start ノードを入力に設定する | 定数の値 | + +従来の基本ブロックでは、命令は順番に実行されます。Sea of Nodes モデルでは、 +グラフのエッジとして明示されているノード間の依存関係（制御依存関係を含む）だけに基づく +スケジューリングアルゴリズムが、命令の正しい順序を決めます。 +すべての依存関係を常に参照できるため、非常に低いコスト +（ほぼ常に小さな定数時間）で多くの最適化を行えます。 + +### 一意なノード ID + +各ノードには、作成時に一意な、密に割り当てられた整数のノード ID を付けます。 +この ID はデバッグや効率的な等価性の判定、たとえばビットベクトルへの添字として役立ちます。 +ビットベクトルを使うと、循環を含む可能性のあるグラフを効率的に訪問できます。 +ノードの等価性については[第9章](../chapter09/README.ja.md)で説明します。 + +### Start ノード + +Start ノードは、関数の開始を表します。関数がまだパラメータを受け取らないため、現時点では Start に入力はありません。 +パラメータを追加すると、Start の値はタプルになり、その値を取り出すために射影（Projection）が必要になります。 +これについては[第4章](../chapter04/README.ja.md)で詳しく説明します。 + +### Constant ノード + +Constant ノードは定数値を表します。現時点で許す定数は整数リテラルだけなので、Constant は整数値を保持します。 +ほかの種類の定数を追加する際には、Constant の表現方法をリファクタリングします。 + +定数には意味上の入力はありません。ただし、グラフを順方向にたどれるようにするために、 +Start を Constant の入力に設定します。このエッジには意味上の役割はなく、 +ノードを訪問できるようにするため*だけ*に存在します。 + +Constant の値は、そこに格納されている値です。 + +### Return ノード + +Return ノードには2つの入力があります。第1の入力は制御ノードで、 +第2の入力は戻り値を供給するデータノードです。 + +この章では複数の `return` 文を使えないため、Return がプログラムを終了します。 +Stop ノードは、`if` 文を実装する[第5章](../chapter05/README.ja.md)で導入します。 + +Return の出力は、データノードから得られる値です。 + +### 表現 + +次のプログラムを可視化します。 + +``` +return 1; +``` + + + +* 制御ノードは、背景が薄い黄色の長方形で示しています。 +* 制御エッジは赤色で、データエッジより太く描いています。 +* Constant から Start へのエッジは、本当の制御エッジではないため、灰色の破線で示しています。 +* 各エッジには、`_inputs` 配列内での位置をラベルとして付けています。したがって `0` は、そのエッジが `_inputs[0]` であることを意味します。 + +## 参考文献 + +データ構造は、次の論文で説明されている内容に基づいています。 + +* [From Quads to Graphs: An Intermediate Representation's Journey](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR93366-S.pdf) +* [Combining Analyses, Combining Optimizations](https://dl.acm.org/doi/pdf/10.1145/201059.201061) +* [A Simple Graph-Based Intermediate Representation](https://www.oracle.com/technetwork/java/javase/tech/c2-ir95-150110.pdf) +* [Global Code Motion Global Value Numbering](https://courses.cs.washington.edu/courses/cse501/06wi/reading/click-pldi95.pdf) +* [EasySSA](https://www.dropbox.com/scl/fi/0ww4sgl3ynep9hhe3i4xn/EasySSA.pdf?rlkey=2cp78hzxke62flkmyneiebzoz&dl=0) +* [SeaOfNodes](https://www.dropbox.com/scl/fi/cxykfvlzsmlcatyg6rlbt/SeaOfNodes.pdf?rlkey=z6o7y3rwr6atrejilcze6r8x0&e=1&dl=0) + +これらに倣い、中間表現をオブジェクト指向のデータモデルで表します。 +以降で、この表現の詳細を説明します。 diff --git a/docs/chapter01/README.md b/docs/chapter01/README.md new file mode 100644 index 00000000..13a4216b --- /dev/null +++ b/docs/chapter01/README.md @@ -0,0 +1,206 @@ +# Chapter 1: Introduction + +English | [日本語](README.ja.md) + +[Introduction](../../README.md) | +[Next: Chapter 2](../chapter02/README.md) + +# Table of Contents + +1. [Implementation Language](#implementation-language) +2. [Assumptions](#assumptions) +3. [Architecture](#architecture) +4. [Data Structures](#data-structures) +5. [Intermediate Representation as a Graph of Nodes](#intermediate-representation-as-a-graph-of-nodes) +6. [Nodes are in a Graph](#nodes-are-in-a-graph) +7. [Types of Nodes](#types-of-nodes) +8. [Unique Node ID](#unique-node-id) +9. [Start Node](#start-node) +10. [Constant Node](#constant-node) +11. [Return Node](#return-node) +12. [Representation](#representation) + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter01) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch. + + +In this chapter we aim to compile simple scripts such as: + +``` +return 1; +``` + +We implement the `return` statement. +The `return` statement accepts an `expression` as an argument. +The only `expression` type is an integer literal, as shown in the example above. + +To implement this simple language, we introduce a few key components and data structures. + +Here is the [complete language grammar](01-grammar.md) for this chapter. + + +## Implementation Language + +Our implementation language is Java. We chose Java as it is widely available and understood. + +## Assumptions + +We assume that the reader is familiar with traditional linear intermediate representations, and is familiar with terms such as Basic Block, Control Flow Graph, etc. No attempt is made to explain these topics. +If necessary the reader can consult a standard compiler textbook. + +## Architecture + +We construct the intermediate Sea of Nodes (SoN) representation directly as we +parse the language. There is no Abstract Syntax Tree representation. The reason +for this is to demonstrate a key benefit of the SoN IR: a number of pessimistic +peephole optimizations can be performed while parsing a language. This aspect +is more fully explored from [Chapter 2](../chapter02/README.md) onwards, and +eventually leads to a full-fledged program typing without needing any +type-analysis passes. + +### Intermediate Representation as a Graph of Nodes + +The intermediate representation is a graph of Node objects. The `Node` class is the base type for objects in the IR graph. +The `Node` class provides common capabilities that are inherited by all subtypes. +Subtypes implements semantics relevant to that subtype, e.g. AddNodes add and MulNodes multiply. + +Each `Node` represents an "instruction" as it may appear in traditional IRs. + +### Nodes are in a Graph + +The key idea of the Sea of Nodes IR is that each Node is linked to other Nodes +by def-use dependencies. As this is such an important and fundamental aspect +of the IR, it is important to understand how we implement this, and depict this +in graph visuals. + +The base `Node` class maintains a list of Nodes that are inputs to it. An +input is an edge from a "use" to a "def". What this means is that if `B` is a +definition, and `A` uses `B`, then `B` has a def->use edge from `B` to `A` and +correspondingly A has an input use->def edge from `A` to `B`. + +Visually we show an arrow from the "use" to the "def". Here is an example: + + + +From an implementation point of view, our `Node` type also maintains a both links. +This means that in the above scenario: + +* Since `A` is a "use" of `B`, then `B` will appear in `A`'s list of inputs. +* Conversely, `B` maintains a list of outputs, and `A` will appear in this list. +* A key invariant is that these edges must be in sync at all times. + +Here is how this looks in the `Node` class: + +```java +public abstract class Node { + + /** + * Inputs to the node. These are use-def references to Nodes. + * <p> + * Generally fixed length, ordered, nulls allowed, no unused trailing space. + * Ordering is required because e.g. "a/b" is different from "b/a". + * The first input (offset 0) is often a Control node. + */ + public final ArrayList<Node> _inputs; + + /** + * Outputs reference Nodes that are not null and have this Node as an + * input. These nodes are users of this node, thus these are def-use + * references to Nodes. + * <p> + * Outputs directly match inputs, making a directed graph that can be + * walked in either direction. These outputs are typically used for + * efficient optimizations but otherwise have no semantic meaning. + */ + public final ArrayList<Node> _outputs; +} +``` + +### Types of Nodes + +There are two categories of Nodes in the intermediate representation. + +* **Control Nodes** - these represent the Control Flow Graph (CFG) of the compiled program +* **Data Nodes** - these capture the data semantics + +The following control and data nodes appear in this chapter. + +| Node Name | Type | Description | Inputs | Value | +|-----------|---------|-----------------------------------------------|------------------------------------------------------------------|-------------------------------------------------------| +| Start | Control | Start of function | None | None for now as we do not have function arguments yet | +| Return | Control | Represents the termination of a function | Predecessor control node, Data node value | Return value of the function | +| Constant | Data | Represents constants such as integer literals | None, however Start node is set as input to enable graph walking | Value of the constant | + +Within a traditional basic block, instructions are executed in sequence. In the +Sea of Nodes model, the correct sequence of instructions is determined by a +scheduling algorithm that depends only on dependencies between nodes (including +control dependencies) that are explicit as edges in the graph. This enables a +number of optimizations at very little cost (nearly always small constant time) +because all dependencies are always available. + +### Unique Node ID + +Each node is assigned a unique dense integer Node ID when created. This ID is +useful for debugging, efficiently computing equality and e.g. as an index into +a bit vector, which in turn is used to efficiently visit a (possibly cyclic) +graph. We discuss Node equality in [Chapter 9](../chapter09/README.md). + +### Start Node + +The Start node represents the start of the function. For now, we do not have any inputs to Start because our function does not +yet accept parameters. When we add parameters the value of Start will be a tuple, and will require Projections to extract the values. +We discuss this in detail in [Chapter 4](../chapter04/README.md). + +### Constant Node + +A Constant node represents a constant value. At present, the only constants +that we allow are integer literals; therefore Constants contain an integer +value. As we add other types of constants, we will refactor how we represent +Constants. + +Constants have no semantic inputs. However, we set Start as an input to +Constants to enable a forward graph walk. This edge carries no semantic +meaning, and it is present _solely_ to allow visitation. + +The Constant's value is the value stored in it. + +### Return Node + +The Return node has two inputs. The first input is a control node and the +second is the data node that supplies the return value. + +In this presentation, Return ends the program, since multiple `return` statements are not possible. +The Stop node will be introduced in [Chapter 5](../chapter05/README.md) when we implement `if` statements. + +The Return's output is the value from the data node. + +### Representation + +Here is a visualization of the program: + +``` +return 1; +``` + + + +* Control nodes appear as rectangular boxes with pale yellow backgrounds +* Control edges are red and thicker than data edges +* The edges from Constants to Start are shown as dashed gray lines as these are not true control edges +* We label each edge with its position in the `_inputs` array, thus `0` means the edge is `_inputs[0]`. + + + +## Reading Material + +Our data structures are based upon the descriptions provided in the following papers: + +* [From Quads to Graphs: An Intermediate Representation's Journey](http://softlib.rice.edu/pub/CRPC-TRs/reports/CRPC-TR93366-S.pdf) +* [Combining Analyses, Combining Optimizations](https://dl.acm.org/doi/pdf/10.1145/201059.201061) +* [A Simple Graph-Based Intermediate Representation](https://www.oracle.com/technetwork/java/javase/tech/c2-ir95-150110.pdf) +* [Global Code Motion Global Value Numbering](https://courses.cs.washington.edu/courses/cse501/06wi/reading/click-pldi95.pdf) +* [EasySSA](https://www.dropbox.com/scl/fi/0ww4sgl3ynep9hhe3i4xn/EasySSA.pdf?rlkey=2cp78hzxke62flkmyneiebzoz&dl=0) +* [SeaOfNodes](https://www.dropbox.com/scl/fi/cxykfvlzsmlcatyg6rlbt/SeaOfNodes.pdf?rlkey=z6o7y3rwr6atrejilcze6r8x0&e=1&dl=0) + +Following the lead from above, we represent our intermediate representation using an object oriented data model. Details of the +representation follow. + diff --git a/docs/incremental-builds.md b/docs/incremental-builds.md new file mode 100644 index 00000000..201922a0 --- /dev/null +++ b/docs/incremental-builds.md @@ -0,0 +1,63 @@ +# Incremental builds: future work + +Recorded after the Separate Compilation README review, 2026-10-24. This is a +design outline, not a description of implemented incremental builds. + +## Current gap + +`CompUnit` decides whether to reuse an object when the unit is discovered. It +checks its source timestamp and its dependencies' existing object timestamps. +It does not settle the whole dependency graph before accepting saved IR. + +For example: + +1. A depends on B and has inlined some of B. +2. B's source changes, leaving B's object unchanged. +3. A client discovers A. A's check sees the old B object and accepts A's object. +4. Later discovery notices that B needs rebuilding, without reconsidering A. + +The compiler can therefore reuse code based on stale bodies or constants. +An unchanged public signature is insufficient: Simple imports implementation +details for optimization as well as declarations for type checking. + +## Required pieces + +- Discover dependencies, mark changed units, and propagate that decision to + dependents until it settles. Handle cycles as groups. Do this before loading + IR that may be stale; newly discovered dependencies must also join the plan. +- Record actual inputs. An object can own several source units, so track all + of their sources and the objects resolved through library search paths. + The current check assumes `buildDir/name.o`; a missing file has timestamp + zero and does not trigger rebuilding. Missing inputs must invalidate or + produce a useful error rather than silently accepting an old result. +- Record compiler and serialization versions, target, ABI, and relevant + options. Content hashes would also detect changes with preserved timestamps. + Specify which changes require rebuilding source and which reject an + incompatible source-free library. +- Make build targets match output ownership. The old ignored `testModule0` + expects separate A.o and A/B.o, while the current compiler can bundle several + units into one object. The target must identify the complete set it owns. +- Provide an "ensure current" build operation. Explicit source compilation + currently always recompiles. An unchanged build should do no compilation or + linking; a changed object or link input should trigger relinking. +- Publish successful outputs without leaving a partial object accepted after + failure, and keep the recorded inputs consistent with those outputs. + +Initially, rebuilding every dependent of a changed object is a reasonable +conservative rule. Fine-grained interface/body fingerprints can come later. + +## Suggested first implementation + +Put a small build driver around the compiler with explicit object targets, +recorded inputs, and dependency propagation. Keep individual compilation +requests straightforward. A clean build and an incremental build must produce +the same observable program behavior. + +Cover unchanged builds, direct and transitive source edits, inlined constants +and bodies, cyclic dependencies, bundled sources, removed inputs, library-path +changes, compiler/target changes, and failed builds. Use controlled timestamps +or hashes instead of sleeps. Replace the ignored historical experiment with +tests matching the chosen object ownership model. + +Selective library IR loading is separate future work. It can reduce compile +cost, but is not required to make conservative incremental rebuilding correct. diff --git a/docs/japanese-translation.md b/docs/japanese-translation.md new file mode 100644 index 00000000..39383345 --- /dev/null +++ b/docs/japanese-translation.md @@ -0,0 +1,22 @@ +# Japanese translation / 翻訳の保守方針 + +English is authoritative. The contributed Japanese translation is maintained on +a best-effort basis; English edits and chapter reorganizations never wait for +translation updates. Move Japanese files and update navigation when renumbering +chapters; prose updates can follow separately. Contributions are welcome, without +an ongoing maintenance obligation for the original translator. + +[英語版](../README.md)が正式な文書です。この日本語訳は寄贈されたもので、可能な範囲で保守されますが、 +英語版より更新が遅れることがあります。英語版の編集や章の再構成を、翻訳の更新待ちにすることはありません。 +章を移動・改番する際は、日本語ファイルも一緒に移動して章の見出しやリンクを更新し、本文の翻訳は後から更新できます。 +翻訳の改善は歓迎しますが、元の寄贈者に継続的な保守を義務付けるものではありません。 + +初回の翻訳は英語版のコミット +[`81b654d7`](https://github.com/SeaOfNodes/Simple/tree/81b654d76444d747fdf1d053760e507b50f26e18) +を基にしています。2026年10月の目次・文法見出し・コード例・命令エンコーディング・ +`C0DE` ヘッダに関する文書修正も反映しています。 +各文書の English リンクは現在の英語版を指します。更新されていない箇所の原文を確認するには、 +上記コミットの対応するファイルを参照してください。新しい章が未翻訳の場合は、その旨を示して英語版にリンクできます。 + + +[日本語の紹介に戻る](../README.ja.md) diff --git a/docs/regalloc-spills.md b/docs/regalloc-spills.md new file mode 100644 index 00000000..aa377ba1 --- /dev/null +++ b/docs/regalloc-spills.md @@ -0,0 +1,118 @@ +# Register allocation across chapters + +This is the dated **pre-split** comparison. Its Ch 24/25 columns describe the +retired combined snapshots, not today's Chapter 25 (incomplete types). Current +measurement tools target 24b/28b and publish a +[separate table](appendices/current-spill-matrix.md). The historical numbers +below remain unchanged. + +Read a row left to right to follow a fixed cohort through successive compilers. +Each cell gives **Ops / RA / X**: + +- **Ops:** executed ARM + RISC-V machine instructions, with fixed inputs. +- **RA:** executed instructions belonging to allocator-created copies, + spills/reloads and rematerializations; a subset of Ops. A replacement constant + materialization counts even when it adds no instruction relative to the + original program. This measures allocator-generated code, not a net overhead. +- **X:** x86-only `_spillScaled`, counting retained split moves (including + register copies) with weight `8^loopDepth`. It is a static estimate and does + not count rematerializations. + +**Cases D / X** counts dynamic program/target cases and x86 compilations. +Repeated historical compilation entries remain repeated. These are independent +coverage counts, not a sum; dynamic cases may use several inputs. Membership, +inputs and returned values are checked across compiler columns. Chapter 20 has +no encoder, so its dynamic cells are unavailable. There is no cross-cohort total. + +<!-- spill-matrix:start --> +| Test cohort | Cases D / X | Ch 20: Ops / RA / X | Ch 21: Ops / RA / X | Ch 22: Ops / RA / X | Ch 23: Ops / RA / X | Ch 24: Ops / RA / X | Ch 25: Ops / RA / X | +|---|---:|---:|---:|---:|---:|---:|---:| +| Ch 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | 58,720 / 9,068 / 183 | 58,965 / 9,076 / 208 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | 6,325 / 380 / 470 | 6,196 / 219 / 534 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | 194 / 56 / 7 | 252 / 92 / 11 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | 630 / 160 / 36 | 864 / 358 / 36 | +| Ch 24 | 36 / 20 | | | | | 4,923 / 1,341 / 790 | 4,646 / 1,335 / 609 | +| Ch 25 | 2 / 12 | | | | | | 20 / 0 / 1,856 | +<!-- spill-matrix:end --> + +Measured on Windows, 2026-10-07, using optimizer seed 123 for the historical +cohorts. The x86 Chapter 25 cohort retains its native-test seeds and the fresh +system-library compilation at seed 456. Dynamic counts include generated class +initializers and calls, but exclude the bodies of native `calloc`, `read` and +`write`. Their deterministic emulator stubs provide allocation and fixed I/O. +No clock timings, native-library instruction counts or code-size metric are mixed in. + +## Inputs and coverage + +| Cohort | Dynamic cases | Executions per compiler | x86 compilations | +|---|---:|---:|---:| +| Ch 20 | 22 | 44 | 13 | +| Ch 21 | 20 | 20 | 18 | +| Ch 22 | 14 | 14 | 8 | +| Ch 23 | 14 | 26 | 8 | +| Ch 24 | 36 | 48 | 20 | +| Ch 25 | 2 | 2 | 12 | + +Newton, array-fill and Merge Sort use argument 16; allocation-index tests use +0, 1 and 2. Branch/short-circuit and nested-equality cases use 0-3, Fibonacci uses 9, and Sieve uses +100. Bubble Sort reads `[4, 3, 2, 1]`; BrainFuck runs its embedded Hello World +program. Other measured cases use argument 0. The Chapter 25 dynamic row is only +the two existing external-data emulator cases, with `counter` initialized to -7; +it does not represent execution of the whole system library or native suite. + +String/Person APIs, the returned mixed-argument function, exported Merge Sort +and BrainFuck, and mixed/stack-argument API tests still need explicit emulator +drivers. Deliberately infinite programs remain compilation-only. The original +allocation cohorts are preserved; these cases are not silently measured as zero. +The previously excluded equality, ARM Newton and ARM Bubble Sort cases now run +in every applicable compiler column. The measurement harness checks their +answers, including nested equality at arguments 0-3, finite Newton results and +Bubble Sort's complete output. The shared ISA tests and full Chapter 21-25 +Make suites pass after the backend/evaluator corrections. + +## Remaining initialization costs + +Chapter 25 now places declared constant final fields directly in static data, +including function addresses, and omits their initialization stores. The same +fixed inputs and test cases give: + +| Cohort | Ch 24 Ops | Ch 25 Ops | Change | +|---|---:|---:|---:| +| Ch 20 | 58,720 | 58,965 | +0.4% | +| Ch 21 | 6,325 | 6,196 | -2.0% | +| Ch 22 | 194 | 252 | +29.9% | +| Ch 23 | 630 | 864 | +37.1% | +| Ch 24 | 4,923 | 4,646 | -5.6% | + +Chapter 25 retains top-level bindings in its class object; earlier chapters can +eliminate them as locals. Mutable fields and final fields whose declarations +do not identify their exact constant still need runtime initialization. This +fixed cost remains visible in small programs even after helper calls inline. + +For cohort 23, the RA subset is 160 in Chapter 24 and 358 in Chapter 25. It +includes allocator-created constant/address rematerialization as well as copies +and stack traffic; it must not be read as a count of spills alone. These tables +compare whole chapter compilers, including frontend and inlining changes. + +## Reproduce + +Run `make spill-stats` at the repository root to compile/run the static cohorts, +capture their historical sources, execute the dynamic cases and validate the +comparison. Capture uses temporary instrumented copies of the existing +SpillStats listeners under `build/dynamic-stats`; it does not edit chapter code. +The measured machine graph is stopped before allocation to identify subsequently +inserted copies/cloned constants. After encoding, their instruction ranges are +matched against the emulator's executed PCs, including multi-instruction expansions. + +After a successful run, publish the current compiler table (leaving these +historical tables unchanged) with: + +```sh +python build-support/spill-matrix.py --reuse --update-docs +``` + +Per-program inputs, results and dynamic counts are written to +`build/spill-stats/dynamic-counts.csv`; emulator logs and explicit skips live +under `build/dynamic-stats/{21,22,23,24b,28b}/dynamic.log`. The x86 records use +`build/spill-stats/spill-matrix-{20,21,22,23,24b,28b}.log`. The source adaptations for old Chapter +25 are documented in the [replay README](../src/test/java/com/seaofnodes/simple/spill/README.md). diff --git a/docs/roadmap.ja.md b/docs/roadmap.ja.md new file mode 100644 index 00000000..0af228a5 --- /dev/null +++ b/docs/roadmap.ja.md @@ -0,0 +1,455 @@ +# ロードマップ + +この設計ノートは旧第25章から移したものです。初期の節には、現在の第25〜28b章で +実装済みの機能について検討した案も含みます。すべてが未実装という意味ではありません。 +現状と残る課題は[監査記録](stage-audit.md)、増分ビルドは[設計メモ](incremental-builds.md)を参照してください。 + +[English](roadmap.md) | 日本語 + +この文書は [ROADMAP.md](roadmap.md) の日本語訳です。原文の設計案と未解決の問いを、そのまま設計案として記しています。 + +## 分割コンパイル + +未知の前方参照をどう扱うか？ H-M は使わないので、単一化も行わない。 +関数以外の前方参照を認めないことにする……関数なら、定義した時点ですぐにシグネチャを提供できる。 + +案 A：FRefNode を削除し、すべてのバグを直す。 +案 A の問題：相互再帰を使えるようにしたい。 +例：`val even = { int x -> x ? odd(x-1) : true; }; val odd = { int x -> x ? even(x-1) : false; };` + +案 B：型は順序どおりに定義する必要があるが、それ以外の関数には順序を要求しない。 +`new T` ならエラーにできるが、`fref.field`、`fref()`、`fref op fref`、`fref[]` ではできない。 + +あらゆる場所で Type.BOTTOM をパーサーの要件に合わせて「引き上げる」必要がある。 +FRef からフィールドをロードするには、FREF を FIELD のある TSTRUCT への TMP に引き上げる必要がある……。 +実際には、FREF が正しくなると局所的に仮定するだけだ。型は任意のコードから来るので、 +アクセスできず、引き上げられない。TMP は nullable かもしれない（後でエラーにすべき）。 +TSTRUCT は無名にでき、無名になるだろう。これは、すべての TSTRUCT を無名にすることを意味する。 + +問題は、未知・遠隔・外部・前方の参照にある。 + +FRef を*少しでも*認めると、すべての処理が FRef 型に遭遇することを考慮しなければならない。 +同じスコープの関数で認めると、上の odd/even の例が使える。 +同じスコープの構造体で認めると、相互再帰的な構造体が使える。 +スコープの外へ昇格させる際には外部の検索を試み、見つからなければ失敗する。 + +任意の使い方の例：`sys.fld`。`sys` の検索に失敗したら、次のどちらかを推測しなければならない。 +前方参照で問題なく、間もなく定義されるのか……それとも今すぐ外部を検索するのか。 +さらに、使い方によっては問題の発覚が遅れる。 +```java +// Extern or Future `sys` being returned. +val foo { -> return sys; } + +// foo() returns FRef, so Bottom, so the `.bar` has no type +// to do field lookups +val main { arg -> foo().bar } + +// HERE: Parser finds `sys` OR NOT?!?!?! +val sys??? = user_stuff....; + +``` + +行き着く先は、パーサーが一切エラーを出さず、盲目的な AST のように SSA を構築し、 +不適切な型だらけのグラフを結線するだけになることだ。 +必要なこと：パーサーを導く型をなくす！ 構文だけを使う！ + +（明らかな小さな問題：浮動小数点数へ拡張するかどうか。） +修正：たとえば整数演算を挿入する。両方の入力が isa-Int であり、isa-Float に引き上げられなくなるまでは、 +戻り値の型を Int と Float の MEET とする。 + +メソッド呼び出しで起こり得る問題： +`UNKNOWN_STRUCT_BOT.UNKNOWN_FIELD ( ARGS ); // Insert SELF OR NOT?` +— SELF を挿入するか？ +修正案：常に SELF 引数があると仮定し、静的と証明できる場合は null にする。 +最適化：定数パラメータをシグネチャから削除するか？ *定数*パラメータは、 +*パーサー*の時点で定数でなければならない。そうでなければ未知の呼び出し元がないことが必要になる +（したがって局所的な最適化になる）。 +修正案：SELF 引数を*最初*ではなく*最後*に置くと、不要になった場合に削除しやすいか？ + +Load は ConFldOff を捨て、名前を保持する。 +Load はスケーリング前の添字を保持し、添字入力を持つ。構造体ではこの入力は null。 +Ptr Base が*確定*した後で基底の配置を行い、添字の計算を畳み込める。 + +- `Load(ctrl, base, null );` — フィールド名は内部に持つ。 +- `Load(ctrl, base, index_math );` — フィールド名は `[]`。 +- `Store(ctrl, base, null , val);` + +問題：エイリアス情報がない！ + +案 C：直接呼び出し `odd()` と型では FRef を認める。それ以外はすべて*引き上げ*が必要。 + +## 構造体と配列の統合 + +構造体のフィールドは名前で索引付けされ、配列の要素は数値で索引付けされる。 +この2つの考え方は両立する、という発想です。 +C 言語では古くからこの考え方を使っています。通常の C の構造体の後に配列を続け、 +通常の配列構文で索引アクセスできます。 + +別の方法として、配列へのポインタをフィールドに保持すると、間接参照が1つ増える代わりに柔軟性が得られます。 +特に、配列を（通常はより大きな配列に）交換できます。 +これは、広く使われる汎用コンテナ `Vector` や `ArrayList` の基礎です。 + +```java +struct str { + int hash; // A cache of the strings hash code + u32 #; // The array length + u8 []; // Array of bytes +}; + +str X = "abc"; +print(X.hash); // Read the hash field +X[0]=='a'; // Read array element 0 +X#; // Length of the array + +``` + +ここでは、`#` というフィールドが配列の長さを保持し、`[]` というフィールドが実際の配列です。 +メモリ内では、この配列がほかのフィールドの直後に続きます。 +可変長配列の別の例を示します。 + +```java +struct vecInt { + u32 size; // Actual number of elements + u32 #; // The array length or capacity + int []; // Array of integers. +}; +``` + +明らかな制約として、配列のサイズを直接変更することはできません。 +先頭のフィールドと同じメモリブロックに実際に配置されているからです。 +このような `vecInt` を、より大きい新しい `vecInt` に*再割り当て*することはできますが、 +元の `vecInt` は解放されます。同じ `vecInt` の参照を永遠に使い続けることはできません。 + +名前付きフィールドはいくつあってもかまいません。 + +```java +struct Class { + !str !className; + !str !professor; + int time; + int credits; + !Class !prerequisite; + u16 #; // Limit of 65535 students per class + Student []; +}; +``` + +自己参照も使えます。 + +```java +struct NTree { + Some val; + u8 #; // Length is 0-255 + NTree []; // More NTrees +}; +``` + +構文規則は次のとおりです。 + +- 最後のフィールドの名前は `[]` で、どの型でもよい。 +- 最後から2番目のフィールドの名前は `#` で、配列の最大長を表す符号なし整数型でなければならない。 +- ` []` の前に空白が必要になるかもしれない。 + +### コンストラクタと配列 + +割り当てには配列の長さを含め、コンストラクタも含められます。 +`new NTree{val=17;}[2];` + +コンストラクタは省略できますが、配列の長さは省略できません。 + +配列を初期化するための任意の関数を使うと、一度だけ書き込む final 配列を作れます。 +`new u8[buffer#,{ u32 idx -> buffer[idx].toUpperCase() }]` + +### 配列の最大長の変更 + +範囲チェックのある小さな配列を大量に使う場合、配列の長さのために丸々4バイトを確保すると、 +配列のオーバーヘッドが大きく増えることが問題になります。 +Simple では最大長を小さくできます。ただし、最大長が異なる配列は別の型として扱います。 + +```java +struct x0 { u8 #; u8[]; }; // Array limited to 0-255 length +struct x1 { u16 #; u8[]; }; // Array limited to 0-65535 length +struct x2 { u32 #; u8[]; }; // +struct x3 { u64 #; u8[]; }; // + +x0 x = "abc"; // 4 bytes total: [3, 'a', 'b', 'c'] +x1 y = "def"; // 6 bytes total: [3, 0 , 'd', 'e', 'f', 0,]; 1 pad byte to acheieve 2-byte alignment +x = y; // ERROR, "x1 is not x0", no auto-widening +x += y; // OK, 7 bytes total: [6, 'a', 'b', 'c', 'd', 'e', 'f'] +y += x; // OK, 8 bytes total: [6, 0 , 'd', 'e', 'f', 'a', 'b', 'c'] + +x += "VeryLongString.... ....255_chars"; // Runtime RangeCheck + +// Explicit conversion to widen string +y = "" + x; +``` + +### 拡張可能な配列・文字列の2つの形：間接参照を増やすかどうか + +間接参照を1つ増やすと、Java の `ArrayList` や C++ の `Vector` のようになります。 + +増やさない場合、拡張可能な配列を伸ばす呼び出しは、新しいオブジェクトを返す可能性があります。 +拡張は必要な場合だけ行います。 + +```java +val vec1 = new vecInt[0].add(2); // len=1, capacity=1 +val vec2 = vec1.add(3); // NEW !vecInt !returned, only is deleted; len=2; capacity=2; +vec1[0]; // ERROR, vec1 has been freed by call to `vec1.add(3)` +vec2[0]; // OK +vec2[1]; // OK +vec2[2]; // Runtime error, AIOOBE +``` + +## 文字列の実装 + +既定の文字列は「str」「cstr」「ustr」などの名前を持ちます。 + +常に unicode8 を使い、u8 を明示的に操作します。 +Unicode の「文字」は、基礎となる実装の上に関数呼び出しとして提供します。 +おそらく別の文字列クラスで実装することになります。 + +## 既定の文字列 + +連結によって効率的に拡張でき、さまざまな IO/printf 関数をサポートします。 +明示的に要求すれば、基礎となる配列を可変な状態で共有できます。 +既定では常に、非共有時は可変、共有時は読み取り専用です。 + +```java +struct str { + + // Add a string to the string, possibly growing + val add = { str str -> + val self = this; + for( int i=0; i<str#; i++ ) + self = self.add(str[i]); + return self; + }; + + // Add an char to the string, possibly growing + val add = { u8 e -> + if( len >= # ) return copy(# ? #*2 : 1).add(e); + [size++] = e; + return this; + }; + + // Copy 'this' to a new larger size + val copy = { int sz2 -> + val v2 = new str[sz2]; + for( int i=0; i<len; i++ ) + v2[i] = [i]; + v2.len = len; + sys.libc.free(this); // Needs a better Mem Management solution + return v2; + }; + + val print { -> sys.libc.write(1/*stdout*/,[]/*array base as argument to C*/,len); return this; } + + u32 len; // In-use size + u32 #; // Max length is 4Gig, although variants can request smaller lengths + u8 []; // Character data +}; +``` + +### Final な文字列 + +**不変**な文字列を意図しており、**安全な**文字列の基礎にも使えるかもしれません。 +一度に全体を作成する必要があり、おそらく防御的コピーも必要になります。 + +```java +struct sstr { + // Possible static call syntax; no references to "this" + val make { str str -> new sstr[str#,str.at] }; + + // Array contents are immutable. + // Still figuring out good syntax for this. + u8 #; + u8 [~]; // Middlin '~'? Makes primitive array contents *immutable* and requires constructor syntax +}; + +// Construction requires a function that produces the array contents. +// Here we are defining a defensive copy over `buf`. +sstr safe = new sstr[buf.len,{ int idx -> buf[idx]; }]; +sstr safe = sstr.make("abc"); // Defensive copy is made +``` + +### 拡張可能な文字列（StringBuilder または StringBuffer） + +この API は `StringBuilder` スタイルの代替としてそのまま使えることを意図しており、 +使うたびに間接参照が1つ増えます。 + +```java +struct xstr { + !str !_str; // The extra indirection is here + val add = { str str -> _str = str.add2(str); }; + val write = { int fd -> _str.write(fd); }; +}; +``` + +### Unicode 文字列 + +この API は、通常の `str` の上で Unicode の文字を操作できるようにすることを意図しています。 + +```java +struct ustr { + // Assuming idx is at the start of a character, return the character + // as a 32b integer. Returns junk integer if not at a character start. + // For all ASCII strings this will amount to a simple byte load. + // For bytes with high order bits set, this may read 1-4 characters. + val at = { int idx -> ... }; +}; +// Unicode character iterator +struct ucharator { +// Return successive unicode character codes +}; +``` + +### 「C」文字列 + +ゼロ終端の文字列ですが、長さを直接取得できる必要があります。 + +```java +struct cstr { + u8 #; // length including the trailing zero + u8[]; // always ends in a zero byte; suitable for direct passing to C string functions +}; +``` + +### 「german string」：レジスタに格納できる非常に短い文字列 + +メモリ内では、長さを表す1バイト（3ビット？）に続いて0〜7文字を格納し、最大8文字です。 +64ビットのレジスタに収まります。 + +```java +struct gstr { // aka germanString, or blend string and register "streg" + u3 #; // Size is 0-7 bytes??? + u8 []; // Up to 7 bytes +} +// Using inlined object (see below). All these strings are short and are +// represented as packed integers in a 64b register. +*gstr prize1 = "gold"; +*gstr prize2 = "silver"; +*gstr prize3 = "bronze"; + +``` + +### Main は `val main = { str[] args -> ...}` になる + +## 構造体のインライン化 + +構造体は通常、参照として扱いますが、「内容（contents of）」と読む `*` 演算子を使って +値として扱う形へ変換できます（この名前は、たとえば `inline` に変えるかもしれません）。 + +これは名前空間の変更だけです。内部の構造体の寿命を完全に消費しない限り、そのアドレスは取得できません。 +「外部への流出」は認めません。 + +```java +// 2 64-bit words, no other overheads +struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; + +// Current Simple rules: always by-reference +struct ByRef { + !Complex !c; // 4-byte pointer to a Complex +}; +print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c + +// New behavior: by value (inlining a struct) +// The '*' syntax indicator can be something else, e.g. a keyword "inline" +// I am pronouncing '*' as "contents of" +struct ByValue { + *!Complex !c; // c is inlined, full 16 bytes into ByValue +}; +print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load + +// Mixing Refs and Struct Values. Basically, a ref can be converted +// to a value by taking the "contents of" the ref, and values cannot +// be *converted* to a ref, although they can be copied over a ref. +ref. c = val.c; // Error, mixing refs and values +ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null +val. c = ref.c; // Error, mixing refs and values +val. c = *ref.c; // Allowed, whole structure copy +ref. c = ref.c; // Allowed, pointer copy +val. c = val.c; // Allowed, whole structure copy. +val *c = val.c; // Error, cannot take "contents of" a value + +// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS: +ref.c = val.*c; // Assign into ref.c the "contents of" val.c + +// Arrays of inlined structures +var ary = new *Complex[99]; // Array of 99 !Complex !objects, inlined + +// Calling methods has the same syntax +ref.c.len(); +val.c.len(); + +// Function arguments use the same typing, so can pass-by-value +val math.sin = { *Complex c -> ... }; // Passes a complex by value +math.sin(ref.*c); // Requires de-reference to pass by value +math.sin(val. c); // Pass by value + +``` + +## ほかの章のロードマップ + +`&&` と `||`。 +`int` を `i32` に縮小する。 +`TypeMemPtr` を4バイトに縮小する。`mmap` を使い、ヒープを下位4Gの領域に置く。 +パーサーの既定の for ループ構築、または部分的なループ剥離。 +`for( init; test; next ) body` は、次のようになる。 +```java +{ init; // Normal scope entry to bound lifetime of index variable +if( !test ) { // Zero-trip count test + do { + body; + next; + } while( test ); // Exit test at loop bottom by default +} }; +``` + +## `&&` と `||` + +論理演算子 &&（AND）と ||（OR）は短絡評価を行います。 +最初の条件だけで結果が決まるときは、第2の条件の評価を省略できます。 + +- `&&` は最初のオペランドが偽なら評価を止めます。 +- `||` は最初のオペランドが真なら評価を止めます。 + +これらは制御フローを読みやすくする糖衣構文であり、実行モデルに新しいノードを作りません。 + +`&&` と `||` の構文は、制御フローだけを変える単純な糖衣構文であり、新しいノードを導入しません。 + +次の例を考えます。 +```java +int a = 1; +int b = 0; + +if(a++ || b++ ) { + if(b == 0 && a == 2) { + sys.io.p("Or"); + } +} else{ + sys.io.p("And"); +} +return 0; +``` + +- `a++` は1（真）と評価されるので、`b++` は評価されません。 +- その結果、`b` は0のままで、`a` は2になり、「Or」が表示されます。 + +```java +int a = 1; +int b = 1; + +int x=1; +int y=1; +int z=0; + +int g = x++ && y++ && z++; +... +``` + +この例では、次のようになります。 + +- `x++` は真（1）なので、`y++` を評価します。それも真です。 +- 続いて `z++` を評価します。これは偽（0）です。 +- `&&` はすべての条件が真であることを要求するため、最終結果 `g` は0になります。 +- 偽になるオペランドまでのすべてのオペランドを評価するため、`x`、`y`、`z` はすべてインクリメントされます。 diff --git a/docs/roadmap.md b/docs/roadmap.md new file mode 100644 index 00000000..aad2d9ca --- /dev/null +++ b/docs/roadmap.md @@ -0,0 +1,533 @@ +# Compiler roadmap and design notebook + +This notebook preserves the design discussion from the former combined Chapter +25. Early sections include alternatives considered while implementing features +now taught in Chapters 25–28b; they are not all pending tasks. The +[stage audit](stage-audit.md) distinguishes current behavior from remaining gaps. +The [incremental-build design](incremental-builds.md) is a separate future item. +The final section records the outstanding class-initialization and compiler +follow-ups. Keep speculative language/library designs as proposals. + +## Separate Compilation + +English | [日本語](roadmap.ja.md) + + +How to handle unknown forward ref? +No H-M, so no unification. +Demand no forward refs beyond functions... which will provide immediate signatures when def'd. + +Plan A: Remove FRefNode; fix all my bugs. +Fail A: I want mutual co-recurusion to work +Example: `val even = { int x -> x ? odd(x-1) : true; }; val odd = { int x -> x ? even(x-1) : false; };` + +Plan B: Require types ordered, but not any other fcn. `new T` can complain, +but not `fref.field` or `fref()` or `fref op fref` or `fref[]` + +Requires "lifting" Type.BOTTOM to the parser requirements everywhere. +So loading a field from an FRef requires: lift the FREF to a +TMP-to-TSTRUCT-with-FIELD... actually, just locally assume FREF will become +correct. Can't Lift it, no access, since type comes from random code. +TMP might be nullable (should error later). +TSTRUCT can/will be unnamed. Implies ALL TSTRUCT is unnamed. + +Issue is some unknown/remote/external/forward-ref. + +Allowing an FRef *at all* means everybody has to deal with seeing an FRef Type. +Allowing it for functions in same scope allow the above odd/even case . +Allowing it for structs in the same scope allows for co-recursive structs. +Promoting out-of-scope attempts the external lookup, then fails. + +Random junk usage: `sys.fld`. Looking up `sys` fails, now has to +guess: fref is ok, will be defined shortly... OR extern lookup now. +Then some usage delays trouble: +```java +// Extern or Future `sys` being returned. +val foo { -> return sys; } + +// foo() returns FRef, so Bottom, so the `.bar` has no type +// to do field lookups +val main { arg -> foo().bar } + +// HERE: Parser finds `sys` OR NOT?!?!?! +val sys??? = user_stuff....; + +``` + +Which gets to: parser never complains, builds SSA like a blind AST, +just wires up a graph with bad types all around. Requires: No Types +to guide parser! Just Syntax! + + (Obvious minor fail: widen floats- or-not) Fix: insert e.g. int-oper, return + type is MEET of Int,Float until both inputs are isa-Int and cannot lift to be + isa-Float + + Possible method call fail: + UNKNOWN_STRUCT_BOT.UNKNOWN_FIELD ( ARGS ); // Insert SELF OR NOT? + Possible fix: always assume a SELF arg, which is null for provable statics. + Optimization: constant parms get dropped from sig? *Constant* parms + must be constant from *Parser*, or else no unknown callers (so local opts). + Possible fix: SELF arg is *last* not *first*, easier to drop if dead? + + Load drops ConFldOff, keeps name. + Load keeps index unscaled, has index input, which is null for structs. + After Ptr Base is *closed*, base layout can happen, can fold index math. + - Load(ctrl, base, null ); // field name internal + - Load(ctrl, base, index_math ); // field name=='[]' + - Store(ctrl, base, null , val); + + FAIL: No Alias Info! + + +Plan C: + FRefs allowed for direct calls `odd()`, and for Types. + All other cases must *lift*. + + +## Unifying Structs and Arrays + +The idea is that structs have fields indexed by names, and arrays have fields +indexed by numbers, and these ideas are compatible with each other. This idea +has been used by the C language for a long time - an array can follow a normal +struct C and can index it with the usual array syntax. + +The alternative, using a field to hold a pointer to an array, exchanges some +flexibility for an extra indirection. The obvious flexibility allows swapping +the array out (generally for a larger one) and this is the basis of very common +`Vector` or `ArrayList` generic containers. + + +```java +struct str { + int hash; // A cache of the strings hash code + u32 #; // The array length + u8 []; // Array of bytes +}; + +str X = "abc"; +print(X.hash); // Read the hash field +X[0]=='a'; // Read array element 0 +X#; // Length of the array + +``` + +Here, the field named `#` holds the array length and the field named `[]` is +the actual array, which follows the other fields directly in memory. +Here is another example for variable length array: + +```java +struct vecInt { + u32 size; // Actual number of elements + u32 #; // The array length or capacity + int []; // Array of integers. +}; +``` + +The obvious limit here is that the array cannot be directly resized; it is +literally in the same memory block as the leading fields. Such a `vecInt` can +be *re-allocated* to a new larger `vecInt`, but the original `vecInt` will be +reclaimed - you cannot use the same `vecInt` reference forever. + +Any number of named fields are allowed: + +```java +struct Class { + !str !className; + !str !professor; + int time; + int credits; + !Class !prerequisite; + u16 #; // Limit of 65535 students per class + Student []; +}; +``` + +Or self-reference: + +```java +struct NTree { + Some val; + u8 #; // Length is 0-255 + NTree []; // More NTrees +}; +``` + +The syntax rules are: +- the last field is named `[]` and can be of any type. +- the second-to-last field is named `#` and must be some unsigned integer type + representing the maximum array length. +- may require a leading space in front of ` []` + + + +### Constructors and Arrays + +The allocation includes the array length, and can include a constructor: +`new NTree{val=17;}[2];` + +The constructor is optional, the array length is not. + +Optional function for initializing arrays, allows for write-once final arrays: +`new u8[buffer#,{ u32 idx -> buffer[idx].toUpperCase() }]` + + + +### Changing array max length + +An issue for large numbers of range-checked small arrays is that reserving a +full 4 bytes for array length can substantially increase the array overhead. +Simple allows for arrays to have smaller max lengths, although these are +treated as a different type than arrays with different max lengths. + +```java +struct x0 { u8 #; u8[]; }; // Array limited to 0-255 length +struct x1 { u16 #; u8[]; }; // Array limited to 0-65535 length +struct x2 { u32 #; u8[]; }; // +struct x3 { u64 #; u8[]; }; // + +x0 x = "abc"; // 4 bytes total: [3, 'a', 'b', 'c'] +x1 y = "def"; // 6 bytes total: [3, 0 , 'd', 'e', 'f', 0,]; 1 pad byte to acheieve 2-byte alignment +x = y; // ERROR, "x1 is not x0", no auto-widening +x += y; // OK, 7 bytes total: [6, 'a', 'b', 'c', 'd', 'e', 'f'] +y += x; // OK, 8 bytes total: [6, 0 , 'd', 'e', 'f', 'a', 'b', 'c'] + +x += "VeryLongString.... ....255_chars"; // Runtime RangeCheck + +// Explicit conversion to widen string +y = "" + x; +``` + + +### Two flavors of extendable arrays/strings: an extra indirection or not + +With an extra indirection you get e.g. Java `ArrayList` or C++ `Vector`. + +Without, then any call which extends the extendable array return a potentially +new object, only growing as needed. + +```java +val vec1 = new vecInt[0].add(2); // len=1, capacity=1 +val vec2 = vec1.add(3); // NEW !vecInt !returned, only is deleted; len=2; capacity=2; +vec1[0]; // ERROR, vec1 has been freed by call to `vec1.add(3)` +vec2[0]; // OK +vec2[1]; // OK +vec2[2]; // Runtime error, AIOOBE +``` + + +## A String Implementation + +Default strings have names like "str", "cstr", "ustr" or such. + +Always unicode8 with explicit u8 manipulations. Unicode "characters" will come +as function calls over the base implementation, probably in another string class. + +## Default string + +Efficiently growable via concantenation. Supports a variety of IO/printf functions. +The underlying array can be shared mutable if you ask for this. +The defaults will always be private mutable and read-only shared. + +```java +struct str { + + // Add a string to the string, possibly growing + val add = { str str -> + val self = this; + for( int i=0; i<str#; i++ ) + self = self.add(str[i]); + return self; + }; + + // Add an char to the string, possibly growing + val add = { u8 e -> + if( len >= # ) return copy(# ? #*2 : 1).add(e); + [size++] = e; + return this; + }; + + // Copy 'this' to a new larger size + val copy = { int sz2 -> + val v2 = new str[sz2]; + for( int i=0; i<len; i++ ) + v2[i] = [i]; + v2.len = len; + sys.libc.free(this); // Needs a better Mem Management solution + return v2; + }; + + val print { -> sys.libc.write(1/*stdout*/,[]/*array base as argument to C*/,len); return this; } + + u32 len; // In-use size + u32 #; // Max length is 4Gig, although variants can request smaller lengths + u8 []; // Character data +}; +``` + + +### A Final String + +Intended to be a **immutable** string, possibly used as a base for a **secure** +string. This needs to be created all at once, and probably requires a +defensive copy. + +```java +struct sstr { + // Possible static call syntax; no references to "this" + val make { str str -> new sstr[str#,str.at] }; + + // Array contents are immutable. + // Still figuring out good syntax for this. + u8 #; + u8 [~]; // Middlin '~'? Makes primitive array contents *immutable* and requires constructor syntax +}; + +// Construction requires a function that produces the array contents. +// Here we are defining a defensive copy over `buf`. +sstr safe = new sstr[buf.len,{ int idx -> buf[idx]; }]; +sstr safe = sstr.make("abc"); // Defensive copy is made +``` + + +### A Extendable String (aka StringBuilder or StringBuffer) + +This API is intended to be a drop-in for a `StringBuilder` style, and takes an +extra indirection with each usage. + +```java +struct xstr { + !str !_str; // The extra indirection is here + val add = { str str -> _str = str.add2(str); }; + val write = { int fd -> _str.write(fd); }; +}; +``` + +### A Unicode String + +This API is intended to support unicode character manipulation over a plain `str` + +```java +struct ustr { + // Assuming idx is at the start of a character, return the character + // as a 32b integer. Returns junk integer if not at a character start. + // For all ASCII strings this will amount to a simple byte load. + // For bytes with high order bits set, this may read 1-4 characters. + val at = { int idx -> ... }; +}; +// Unicode character iterator +struct ucharator { +// Return successive unicode character codes +}; +``` + +### A "C" string + +A zero-terminated string, but the length has to be available directly + +```java +struct cstr { + u8 #; // length including the trailing zero + u8[]; // always ends in a zero byte; suitable for direct passing to C string functions +}; +``` + +### A "german string": a very short string that can exist in a register + +Length in memory is 1 byte (3 bits?) of length, then 0-7 chars; max 8 chars. +Fits in a 64 bit register. + +```java +struct gstr { // aka germanString, or blend string and register "streg" + u3 #; // Size is 0-7 bytes??? + u8 []; // Up to 7 bytes +} +// Using inlined object (see below). All these strings are short and are +// represented as packed integers in a 64b register. +*gstr prize1 = "gold"; +*gstr prize2 = "silver"; +*gstr prize3 = "bronze"; + +``` + +### Main becomes `val main = { str[] args -> ...}` + + +## Structs can be inlined + +Structs are normally by-reference, but can be converted to by-value by using +the `*` operator, pronounced "contents of" (this name might be changed to +e.g. `inline`). + +This is a name-space change only, you cannot take the address of the internal +struct without entirely consuming its lifetime. No "escaping". + +```java +// 2 64-bit words, no other overheads +struct Complex { f64 x,y; val len = { ->Math.sqrt(x*x+y*y); }; }; + +// Current Simple rules: always by-reference +struct ByRef { + !Complex !c; // 4-byte pointer to a Complex +}; +print(new ByRef.c.y); // Lookup requires 1 extra memory load from ref to c + +// New behavior: by value (inlining a struct) +// The '*' syntax indicator can be something else, e.g. a keyword "inline" +// I am pronouncing '*' as "contents of" +struct ByValue { + *!Complex !c; // c is inlined, full 16 bytes into ByValue +}; +print(new ByValue.c.y); // x,y inlined into ByValue, no extra memory load + +// Mixing Refs and Struct Values. Basically, a ref can be converted +// to a value by taking the "contents of" the ref, and values cannot +// be *converted* to a ref, although they can be copied over a ref. +ref. c = val.c; // Error, mixing refs and values +ref.*c = val.c; // Allowed, whole structure copy. Does not allocate, requires ref.c not-null +val. c = ref.c; // Error, mixing refs and values +val. c = *ref.c; // Allowed, whole structure copy +ref. c = ref.c; // Allowed, pointer copy +val. c = val.c; // Allowed, whole structure copy. +val *c = val.c; // Error, cannot take "contents of" a value + +// Alternative syntax, to avoid the "contents of" being on LHS and field applying to being on RHS: +ref.c = val.*c; // Assign into ref.c the "contents of" val.c + +// Arrays of inlined structures +var ary = new *Complex[99]; // Array of 99 !Complex !objects, inlined + +// Calling methods has the same syntax +ref.c.len(); +val.c.len(); + +// Function arguments use the same typing, so can pass-by-value +val math.sin = { *Complex c -> ... }; // Passes a complex by value +math.sin(ref.*c); // Requires de-reference to pass by value +math.sin(val. c); // Pass by value + +``` + + + +## RoadMap for other chapters + +`&&` and `||` +Drop `int` to `i32`. +Drop `TypeMemPtr` to 4 bytes; using `mmap` to make heap in low 4G. +Default parser for-loop construction, or partial peel. + `for( init; test; next ) body` +becomes: +```java +{ init; // Normal scope entry to bound lifetime of index variable +if( !test ) { // Zero-trip count test + do { + body; + next; + } while( test ); // Exit test at loop bottom by default +} }; +``` + +## `&&` and `||` + +The logical operators && (AND) and || (OR) are short-circuiting, meaning they may skip evaluating the second condition if the first one already determines the result: + +- `&&` stops if the first operand is false. +- `||` stops if the first operand is true. + +They are syntactic sugar—used for cleaner control flow—but they don't create new nodes in the execution model. + +The `&&` and `||` constructs are simple syntactic sugars that only modify the control flow and do not +introduce new nodes. + +Consider this example: +```java +int a = 1; +int b = 0; + +if(a++ || b++ ) { + if(b == 0 && a == 2) { + sys.io.p("Or"); + } +} else{ + sys.io.p("And"); +} +return 0; +``` +- `a++` evaluates to 1 (true), so `b++` is not evaluated. +- As a result, `b` stays 0, `a` becomes 2, and "Or" is printed. + +```java +int a = 1; +int b = 1; + +int x=1; +int y=1; +int z=0; + +int g = x++ && y++ && z++; +... +``` +Here: +- `x++` is true (1), so it evaluates `y++`, which is also true. +- Then it evaluates `z++`, which is false (0). +- Since `&&` requires all conditions to be true, the final result `g` is 0. +- All operands up to the false one are evaluated, so `x`, `y`, and `z` are all incremented. + +## Class initialization and compiler follow-ups + +### Entry arguments + +Replace the integer initializer argument with an argument array. The selected +entry class receives a non-null array, empty when there are no arguments; +other class initializers receive null. Coordinate the parser, entry signature, +runtime driver, and separately compiled interfaces. + +### Pre-initialize classes from ELF data + +Prove when a class's entire initialization can be represented by ELF static +data and relocations, with no remaining runtime effects. Emit its initial +contents and start its `$init` flag as true, so no initializer call is needed. +Carry that fact through separate compilation so importing compilers can remove +checks too. A constant field alone is not proof that the whole class can be +pre-initialized; I/O, argument-dependent work, and other observable effects +still require execution. Preserve any dynamic parent requirement, and do not +let cyclic dependencies justify their own pre-initialization. + +Mutable fields may have static initial contents without becoming constants. +Choose read-only storage only when no runtime writes remain. Static reference +cycles can use relocations without requiring a dynamic initialization cycle. + +For a wholly immutable, pre-initialized class, eliminate the mutable `$init` +state as well as the checks so the class image can reside in ROM. The native +function thunks preserve static initialization of function fields. + +### Compact code and data arenas + +Keep four-byte Simple references into bounded code and data arenas; the arenas +need not overlap or live near zero. Choose absolute addresses versus offsets +from an arena base when implementing placement and indirect calls. Native +function thunks can occupy the code arena while native libraries live elsewhere. +The current thunk implementation uses the existing low-address executable; +ordinary data pointers still occupy eight bytes. + +Give full-width native pointers separate types and foreign lifetime contracts. +Opaque device addresses may need to be passed through without CPU dereference. +Simple object lifetimes should be managed automatically without a GC; +ownership, borrowing, cycles, and native retention still need design. Compact +storage alone does not establish those rules. Preserve static class images and +explicit native boundary conversions when choosing the arena representation. + +### CFG frequency estimates + +After lowering and loop-tree construction, estimate block frequencies for GCM +and code layout. Treat initialization and known-failure paths as rare; use +bounded loop-trip estimates and branch probabilities when no profile is +available. Keep estimates consistent with control flow and shared between +scheduling and layout. These are backend estimates, not ideal-IR types. + +### Constant instance-field storage + +When a final instance field has the same constant value in every instance, +fold accesses or store the value on the class object and omit the instance +slot. Preserve field-access semantics and public function reachability: +externally accessible function fields remain callable regardless of storage. diff --git a/docs/stage-audit.md b/docs/stage-audit.md new file mode 100644 index 00000000..c375d159 --- /dev/null +++ b/docs/stage-audit.md @@ -0,0 +1,82 @@ +# Chapter split cleanup audit + +This record distinguishes checked behavior, existing gaps, and future designs +while retiring the old combined Chapters 24/25. The final mapping is in the +[split record](chapter-split.md). Historical Java test names are retained as +regression identities; they do not identify current chapter boundaries. + +## Corrections in this cleanup + +- Chained comparisons now begin in Chapter 23. The early SCCP implementations + incorrectly compared a boolean intermediate with the third operand: + `10 < 30 < 20` returned true. Later implementations preserved the middle + operand but reused the first operator, making `0 < 2 <= 2` false. All current + snapshots from 23 onward now compare adjacent values using each written + operator. Regression cases cover both directions, strict/non-strict mixtures, + single evaluation, side effects, short-circuiting, and mixed-direction errors. +- Chapter 23's inherited, explicitly described fuzzer scratch contains many + comparisons using the former left-associative grammar. It is retained as an + ignored `testJigFuzzer`, consistent with the scratch-test policy; its mixed + directions are no longer valid source. Later snapshots already omitted it. +- Native-library and tuning material is preserved in [appendices](appendices/README.md), + and the former roadmap is now [docs/roadmap.md](roadmap.md). +- The recursive-return diagnostic already passed. It remains enabled in the + earlier snapshots and is enabled again in 28a/28b. The mutual-recursion test had an obsolete graph-string + expectation; it now checks its existing four execution results in 24b–28b. + In 24a, local SCCP cannot infer the recursive return type; the same example + checks that conservative diagnostic instead. This makes the boundary explicit. +- Allocation/runtime measurement runs passed after the comparison correction; + the changed spill goldens record the resulting smaller graphs. Historical + published tables retain their original compiler labels and dates. + +## Implemented, with narrower limits than earlier prose suggested + +- Separate compilation imports types and optimized IR without source parsing; + it reruns analysis and type checking with the new callers. +- Loading is by object and recorded dependencies, not individual used members. + A call to `sys.io.p` loads all ten bundled sys units. Independent, unrelated + objects can remain unloaded. Loading does not imply class initialization. +- Timestamp checks do not yet provide a reliable incremental build system. + The [design note](incremental-builds.md) records the missing pieces. +- Underscores select exports in modules; source privacy checks are still a + proposal awaiting review. Do not treat hidden exports as inaccessible source. +- Constructor-local final fields use SSA values and exit Stores. Reads of an + unfinished object are allowed only for initialized fields. Passing unfinished + self to arbitrary helpers and accepting completion only after SCCP are not + promised by the current chapter boundary. + +## Existing failures and deferred validation + +- Prefix update of a field from a method can lose the write, starting in + Chapter 23 (confirmed by two calls to `inc={ -> ++x; }`). The enclosing + module-field reproducer and the worklist failure below are retained in the + [queue](chapter-backports.md), rather than hidden by the split. +- A constructor loop with both break and continue still reproduces a worklist + assertion in Chapter 26. It is not caused by final-field mutability. +- `testModule0` is an ignored historical incremental-build experiment. It + assumes per-source output objects and unchanged explicit-input builds, neither + of which matches the present compiler's contract. +- Serialization's expensive byte-for-byte round-trip assertion remains disabled. + Ordinary import tests do not establish that stronger property. +- Direct probes of the remaining ignored tests found a stale forward-method + graph expectation and a missing `progs/sieve.smp` fixture in 28b. These and + the interactive stdin test remain ignored. Ignored Jig and + random-fuzzer entry points are intentional scratch/long-running tools. + Audit these separately before advertising their behavior as tested. + +Selective loading, full incremental builds, source privacy, compact pointers, +argument arrays, deterministic inlining, and broader constructor rules remain +future work. They are not prerequisites for completing the chapter numbering. + +## Validation + +The affected snapshots (23, 24a, 24b, 25, 26, 27, 28a, 28b) were checked with +their full Make suites on Windows and Linux, plus focused reruns after updating +test expectations. The final Windows coverage is 4,143 tests plus eight fuzzer +regression runs, with the shared printer and ISA tests also passing. The +native library/client cases and final Chapter 28b release build pass on both OSes. + +A local linear-history dry run produced all 31 tags in teaching order. The +final source snapshot, chapter navigation, Maven module IDs, and reviewed local +documentation links were checked. Measurement capture in 24b and dynamic +measurements in 24b/28b pass; the historical published tables were not rewritten. diff --git a/docs/type-float.svg b/docs/type-float.svg new file mode 100644 index 00000000..8d83b0bc --- /dev/null +++ b/docs/type-float.svg @@ -0,0 +1,5 @@ +<svg xmlns="http://www.w3.org/2000/svg" width="44" height="20" viewBox="0 0 44 20" role="img" aria-labelledby="title"> + <title id="title">Float</title> + <rect width="44" height="20" rx="2" fill="#00ffff"/> + <text x="22" y="14" text-anchor="middle" font-family="Arial, sans-serif" font-size="13" fill="#000000">Float</text> +</svg> |
