diff options
Diffstat (limited to 'docs/chapter23')
| -rw-r--r-- | docs/chapter23/23-grammar.ja.md | 163 | ||||
| -rw-r--r-- | docs/chapter23/23-grammar.md | 163 | ||||
| -rw-r--r-- | docs/chapter23/Makefile | 12 | ||||
| -rw-r--r-- | docs/chapter23/README.ja.md | 345 | ||||
| -rw-r--r-- | docs/chapter23/README.md | 463 | ||||
| -rw-r--r-- | docs/chapter23/examples/A_helloWorld.smp | 3 | ||||
| -rw-r--r-- | docs/chapter23/examples/BubbleSort.smp | 37 | ||||
| -rw-r--r-- | docs/chapter23/font-awesome-4.7.0.zip | bin | 0 -> 669808 bytes | |||
| -rw-r--r-- | docs/chapter23/ifg_trim.pdf | bin | 0 -> 155190 bytes | |||
| -rw-r--r-- | docs/chapter23/lattice.gv | 203 | ||||
| -rw-r--r-- | docs/chapter23/lattice.svg | 691 | ||||
| -rw-r--r-- | docs/chapter23/lattice2.gv | 85 | ||||
| -rw-r--r-- | docs/chapter23/lattice2.svg | 260 | ||||
| -rw-r--r-- | docs/chapter23/pardoe.docx | bin | 0 -> 22583 bytes | |||
| -rw-r--r-- | docs/chapter23/webtcp.min.js | 65 |
15 files changed, 2490 insertions, 0 deletions
diff --git a/docs/chapter23/23-grammar.ja.md b/docs/chapter23/23-grammar.ja.md new file mode 100644 index 00000000..ff7b5d56 --- /dev/null +++ b/docs/chapter23/23-grammar.ja.md @@ -0,0 +1,163 @@ +# 第23章の文法 + +[English](23-grammar.md) | 日本語 + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : methodDeclaration | statement ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// The general declaration rule also admits explicitly typed function fields. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol. Ordinary strings elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!=' | '<' | '<=' | '>' | '>=') shiftExpression)* + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter23/23-grammar.md b/docs/chapter23/23-grammar.md new file mode 100644 index 00000000..1d52d5a6 --- /dev/null +++ b/docs/chapter23/23-grammar.md @@ -0,0 +1,163 @@ +# Grammar for Chapter 23 + +English | [日本語](23-grammar.ja.md) + +```antlrv4 +grammar SimpleLanguage; + +// Name lookup, assignable operands, type compatibility, and access permissions +// are checked by the compiler in addition to these syntax rules. +program : statement* EOF ; + +block : '{' statement* '}' ; + +statement + : block + | returnStatement + | ifStatement + | whileStatement + | forStatement + | breakStatement + | continueStatement + | structDeclaration + | declaration ';' + | assignment ';' + | ';' + ; + +returnStatement : 'return' assignment ';' ; +ifStatement : 'if' '(' assignment ')' statement ('else' statement)? ; +whileStatement : 'while' '(' assignment ')' statement ; +breakStatement : 'break' ';' ; +continueStatement : 'continue' ';' ; + +forStatement + : 'for' '(' (declaration | assignment)? ';' assignment? ';' assignment? ')' statement + ; + +structDeclaration : 'struct' IDENTIFIER '{' structMember* '}' ';' ; +structMember : methodDeclaration | statement ; + +// A method is an ordinary fixed function binding in a struct definition. +// The compiler supplies self; it is not written in parameterList. +// The general declaration rule also admits explicitly typed function fields. +methodDeclaration : 'val' bindingModifier? IDENTIFIER '=' functionExpression ';' ; + +declaration : declarationType binding (',' binding)* ; +declarationType : type | 'var' | 'val' ; +binding : bindingModifier? IDENTIFIER ('=' initializer)? ; +bindingModifier : '!' | '~' ; +// A declaration initializer consisting of the string "C" declares an extern +// symbol. Ordinary strings elsewhere are array-valued expressions. +initializer : assignment ; + +// The prefix qualifies the named struct reference, not an enclosing array. +// Each [] / [~] suffix qualifies its own array layer. ? requires a reference. +type + : functionType + | primitiveType typeSuffix* + | accessModifier? typeName typeSuffix* + ; +accessModifier : '!' | '~' ; +typeSuffix : '?' | '[]' | '[~]' ; +typeName : IDENTIFIER ('.' IDENTIFIER)* ; + +primitiveType + : 'int' | 'i8' | 'i16' | 'i32' | 'i64' + | 'u1' | 'u8' | 'u16' | 'u32' | 'byte' | 'bool' + | 'flt' | 'f32' | 'f64' + ; + +assignment : expression (assignmentOperator assignment)? ; +assignmentOperator + : '=' | '+=' | '-=' | '*=' | '/=' | '&=' | '|=' | '^=' + | '<<=' | '>>=' | '>>>=' + ; + +expression : logicalExpression ('?' assignment (':' assignment)?)? ; + +// Both logical operators short-circuit and associate to the right here. +logicalExpression : bitwiseExpression (('&&' | '||') logicalExpression)? ; + +bitwiseExpression + : comparisonExpression (('&' | '|' | '^') comparisonExpression)* + ; + +comparisonExpression + : shiftExpression (('==' | '!=' | '<' | '<=' | '>' | '>=') shiftExpression)* + ; + +shiftExpression + : additiveExpression (('<<' | '>>' | '>>>') additiveExpression)* + ; + +additiveExpression + : multiplicativeExpression (('+' | '-') multiplicativeExpression)* + ; + +multiplicativeExpression + : unaryExpression (('*' | '/') unaryExpression)* + ; + +unaryExpression + : ('-' | '!') unaryExpression + | updateOperator IDENTIFIER + | postfixExpression + ; + +// Prefix updates require a local name; postfix updates also allow fields +// and array elements. All updates require an assignable operand. +updateOperator : '++' | '--' ; +postfixExpression : primaryExpression postfixSuffix* updateOperator? ; +postfixSuffix : '.' IDENTIFIER | '[' assignment ']' | '#' | callSuffix | methodCallSuffix ; + +// For a fixed function-valued member, object.name(args) passes object as self. +// This overlaps ordinary field selection followed by a call syntactically; +// name/type resolution determines which call form applies. +methodCallSuffix : '.' IDENTIFIER callSuffix ; + +primaryExpression + : INTEGER_LITERAL + | FLOAT_LITERAL + | STRING_LITERAL + | CHARACTER_LITERAL + | 'true' + | 'false' + | 'null' + | IDENTIFIER + | '(' assignment ')' + | newExpression + | functionExpression + ; + +// A function is an expression bound with an ordinary declaration. +// Its last statement supplies the implicit result; return can exit earlier. +functionExpression : '{' parameterList? '->' statement* '}' ; +parameterList : (parameter ','?)+ ; +parameter : type bindingModifier? IDENTIFIER ; + +// Function types have unnamed, space-separated argument types. +// {int} is the zero-argument type; its function expression still uses ->. +functionType + : '{' type+ '->' type '}' '?'? + | '{' type '}' '?'? + ; + +callSuffix : '(' argumentList? ')' ; +argumentList : assignment (',' assignment)* ','? ; + +// Struct initialization uses a block; array allocation supplies a length. +newExpression : 'new' type ('[' assignment ']' | block)? ; + +INTEGER_LITERAL : '0' | [1-9] DIGIT* ; +FLOAT_LITERAL : DIGIT+ ('.' DIGIT* ('e' DIGIT+)? | 'e' '-'? DIGIT+) ; +STRING_LITERAL : '"' (ESCAPE | ~["\\])* '"' ; +CHARACTER_LITERAL : '\'' (ESCAPE | ~['\\]) '\'' ; +fragment ESCAPE : '\\' [0ntr\\'"] ; +IDENTIFIER : NON_DIGIT (NON_DIGIT | DIGIT)* ; +fragment NON_DIGIT : [a-zA-Z_] ; +fragment DIGIT : [0-9] ; +WHITESPACE : [ \t\r\n]+ -> skip ; +LINE_COMMENT : '//' ~[\r\n]* -> skip ; +BLOCK_COMMENT : '/*' .*? '*/' -> skip ; +``` diff --git a/docs/chapter23/Makefile b/docs/chapter23/Makefile new file mode 100644 index 00000000..12659b8f --- /dev/null +++ b/docs/chapter23/Makefile @@ -0,0 +1,12 @@ +GV := $(wildcard *.gv) +SVG := $(patsubst %.gv,%.svg,$(GV)) + +.PHONY: all +all: $(SVG) + +%.svg: %.gv + dot -Tsvg $< > $@ + +.PHONY: clean +clean: + @rm -f $(SVG) diff --git a/docs/chapter23/README.ja.md b/docs/chapter23/README.ja.md new file mode 100644 index 00000000..5c5427f5 --- /dev/null +++ b/docs/chapter23/README.ja.md @@ -0,0 +1,345 @@ +# 第23章: メソッドと型の再検討 + +[English](README.md) | 日本語 + +この文書は [原文](README.md) の日本語訳です。 + +[前の章: 第22章](../chapter22/README.ja.md) | +[次の章: 第24章](../chapter24/README.ja.md) + +この章では *メソッド* を追加します。構造体内で定義し、隠れた `self` 引数を取り、構造体のフィールドへアクセスできる関数です。文字列のようなクラスの `indexOf` メソッドを示します。 + +```java +// A String-like class, with methods +struct String { + u8[~] buf; // Buffer of read-only characters + + // Return the index of the first character 'c' or -1 + val indexOf = { u8 c -> // Hidden 'self' argument + for( int i=0; i<buf#; i++ ) // Direct access to `buf` field + if( buf[i]==c ) + return i; + return -1; // 'c' not in 'self' + }; +}; +``` + +この章では型も再検討し、大きく変更します。 + +- 型は *循環* するようになります。型は間接的に自身を指せます。 +- 型は引き続き [*インターン*](https://en.wikipedia.org/wiki/Interning_(computer_science)) または [*ハッシュコンシング*](https://en.wikipedia.org/wiki/Hash_consing) されます。 +- 型オブジェクトはオブジェクトプールで管理します。 +- 新しく作った型はインターン表を検索し、見つかれば元のものを使い、新しい型をプールへ返します。 +- インターン表のヒット率は99.9%ほどです。作られる型のほとんどは、すでに作られたことがあるものです。この点は興味深い性能向上につながります。最適化コンパイラの作業の多くは型の操作なので、型の数を小さく保ち、高速な階層のキャッシュに収めることには大きな見返りがあります。 +- インターン処理の多くは、何らかの「訪問ビット」で循環を扱う必要があります。簡単な方法の1つは、各型に *一意な ID*（UID）を追加することです。小さな密な整数をビット集合で使い、同じ型を複数回訪問しないようにします。UID が小さければビット集合も小さくなり、これも高速なキャッシュ階層に収まります。 +- 結果として、型は循環し（これが目標です）、**高速** になり、実装は複雑になります。型の **使い方** は同じです。作成、MEET、読み取り専用化、表示などでは同じ Type API を使い、実装の詳細だけが変わります。 + +第11章の遅延メモリモデルは、新しい型システムでも続きます。BulkMemPhi/MemPhi が最適化中にエイリアスを発見します。各 New はインスタンスフィールドだけを覆い、クラス全体の（`_one`）フィールドは部分メモリから除外します。フィールドオフセットは配置まで記号的なままであり、Load は正確なエイリアスの内容を問い合わせながら、循環するフィールド型と深い final 情報を保持します。 + +[linear](https://github.com/SeaOfNodes/Simple/tree/linear) ブランチ上の直線的な Git リビジョン履歴で [この章](https://github.com/SeaOfNodes/Simple/tree/linear-chapter23) を読み、前の章と [比較](https://github.com/SeaOfNodes/Simple/compare/linear-chapter22...linear-chapter23) することもできます。 + +この章の[完全な言語文法](23-grammar.ja.md)はこちらです。 + +## なぜ循環する型なのか + +循環する型は代替手法より精密な解析を可能にし、より多くのプログラムや、よりよい最適化、あるいは両方を許します。Simple では型を型検査にも使うので、より精密な型により、より多くの正しいプログラムを許容します。 + +**なぜ今、循環する型なのか**。構造体を引数に取る関数定義を構造体内で許すとすぐ、循環が現れるからです。つまり *self* 引数を取る *メソッド* です。 + +上の `String.indexOf` の例を見ましょう。ここでは `indexOf` メソッドを持つ `String` を定義します。隠れた文字列引数 `self` が渡され、検索されます。`struct String` の型は何でしょうか。 + +`struct String { u8[~] buf; { !String !self, u8 c -> int } indexOf; }` + +これは `String` という名前の型で、フィールド `u8[~] buf` と、final で代入済みの定数フィールド `indexOf` を持ちます。後者自身の型は `{ !String !self, u8 c -> int }` です。つまり `String` の型は、`indexOf` の型の内側に自分自身への参照を持ちます。`String` の型は *循環* しています。 + +## 循環の少ない型 + +循環する型の問題は古くからあり、対処のための実績ある方法がいくつもあります。簡単なものの1つは、型の *定義* と、それとは別の型の *参照* を持つ方法です。参照は何らかの検索で型を参照します。たとえば型名とパーサーのシンボル表を使う、ハッシュ表検索です。 + +このモデルでは循環を実質的に回避します。型の循環内の「後退辺」は、すべて参照辺、場合によってはハッシュ表検索で実現します。 + +では、なぜこの方法を採用しないのでしょうか。 + +すべての型参照が同じ型定義へ戻るためです。型情報を特化しても失われます。*すべての* 参照が同じ定義へ戻るため、*すべての* 経路の MEET を取ることになるのです。 + +Java の `Object`、または C の `void*` をデータとして持つ連結リストの例を示します。 + +```java +struct List { + !List !next; + Object payload; // equivalently for C: void* +} +// Then walk a collection of ints and build a List: +List nums = null; +for( int x : ary_ints ) + nums = new List{next=nums; payload=x; } + +// Again for strings: +List strs = null; +for( String x : ary_strs ) + strs = new List{next=strs; payload=x; } +``` + +`nums` の型は何でしょうか。`*List`、つまり次の型です。 + +``` +struct List { List *next; Object payload } +``` + +`Object` を `int` や `String` に精密化できません。すべての List オブジェクトのデータ型は `Object` で、`Object` MEET `int` は `Object` に戻るためです。 + +真に循環する型を許せば、このような場面で `*List<int> { *List<int> next, int payload }` という精密な型を発見、あるいは推論できます。基本的に最適化器内で *ジェネリクス* を構築するのです。言語のジェネリクスや型変数そのものではありませんが、それにかなり近づきます。 + +## 循環する型の扱い + +この章で Simple は循環する型を直接扱います。子の型が元の型へ戻る `Type` オブジェクトを持つため、型に対して [*再帰下降*](https://en.wikipedia.org/wiki/Recursive_descent_parser) がそのままでは使えなくなります。 + +これまでは型構築に再帰下降を使ってきました。子の型を先に作ってインターンし、インターン済みの子で次の階層を構築します。各階層がインターンされ、再帰下降がインターン済みの型で止まるので、共有する型での重複作業を避けられます。このため現在の型に対する演算は、旧型と新型の *差分* に対して線形となり、増分的で高速です。 + +新たな循環する型では、循環全体を見るまでインターンできない問題に直面します。またハッシュ表は等値検査を必要としますが、循環を等値比較するのに通常の再帰下降は使えません。 + +グラフの循環を扱う標準的な方法は、「以前ここに来た」ことを示す *訪問済み* の概念です。一意な型 ID をキーにするハッシュ表を使います。「訪問済み」は、一意な ID が表のキーにあるという意味です。各 Type は大域カウンタから一意な ID を得ます。型をインターンするので、必要な一意 ID 数は一意な型の数と、循環を構築・インターンするためのわずかな予備だけです。過去の経験では通常数千程度が最大なので、小さな整数で十分です。 + +もう1つ、既存の基盤をできる限り残したいので、既存の再帰下降による巡回を少しだけ修正してすべて保持します。 + +すべての型循環には `TypeStruct` が存在します。ただし関数が *自身* を引数に取る純粋な関数型の循環は例外です。それは奇妙なので、どう扱うかはそれほど気にしません。各 `TypeStruct` 生成器の中核で大域 `VISIT` ハッシュ表に要素を設定し、循環型作成の開始を示します。そしてその要素を検査し、循環を止めます。 + +例を見ましょう。 + +異なるデータ型の循環を持つかもしれない連結リストを使います。ただし、ここでは文字列だけです。連結リストは、簡単な代替と比べてひどく非効率なので、ほぼどんな仕事でも間違った構造であることが多いのですが、教材用のデータ構造としては優れています。 + +```java +struct List { + !List? !next; // Next pointer or null + str !name; // Payload +}; +``` + +この構造体の型は宣言に一致します。 + +`struct List { List*? next, str !name };` + +これで文字列リストを構築できます。 + +```java +var list = new List{ name="Hello"; }; +list = new List { list, name="World"; }; +``` + +### 循環する型の読み取り専用／final の検査 + +どこかで読み取り専用の不変な版を作りたいとします。 + +```java +val hello = list; // Make a read-only version +print(hello); // Pass along the read-only version +``` + +`hello` の型は何でしょうか。`List` の読み取り専用型です。しかし `List` は循環する型です。`Type.makeRO` を見ましょう。 + +> 訳注：原文では上の `val hello = list` を読み取り専用版の作成と説明しています。一方、第17b章では `val` は束縛を固定し、初期化式のアクセス権限を保持すると説明しています。この訳では、原文の例と説明を保持しています。 + +```java +public final Type makeRO() { + if( isFinal() ) return this; // First check if already read-only + return recurOpen()._makeRO().recurClose(); +} +``` + +そして `isFinal()`: + +```java +// Are all reachable struct Fields are final? +public final boolean isFinal() { return recurClose(recurOpen()._isFinal()); } +boolean _isFinal() { assert _type < TCYCLIC; return true; } +``` + +`recurOpen()` を呼んで再帰走査を開始／開き、`_isFinal()` を呼びながら再帰し、走査を終了／閉じて、真偽値を返します。`_isFinal()` は Java の final ではなく、Type のサブクラスでオーバーライドします。大半のサブクラスは単に問題を転送します。 + +`@Override boolean _isFinal() { return _obj._isFinal(); }` + +そして `TypeStruct` に到達します。 + +```java +@Override boolean _isFinal() { + if( _open ) return false; // May have more non-final fields + if( VISIT.containsKey(_uid) ) // Test: been here before? + return true; // Cycles assume final + VISIT.put(_uid,this); // Set: don't do this again + for( Field fld : _fields ) + if( !fld._isFinal() ) + return false; + return true; +} +``` + +ここには循環処理の共通パターン、**test-and-set** があります。まず確定できる答えを調べます。開いた構造体は部分的にしか定義されず、未解析の non-final フィールドが現れる可能性があるので、決して読み取り専用ではありません。次に以前訪問したかを **検査** し、そうなら再帰を止めて何らかの答えを返します。`isFinal` では、循環のほかのものもすべて final なら「final である」を返します。 + +まだこの型を調べていなければ、ここを訪れたことを示す訪問ビットを **設定** し、通常の再帰下降でフィールドに同じ質問をします。 + +この例では、`VISIT` に番兵を置いて再帰を開き、`struct List` に `makeRO` を呼びます。それが `_isFinal` を呼び、`_open`（開いていない）、`VISIT`（未訪問）を確認し、UID を `VISIT` に設定してフィールドを走査します。フィールドの検査は次のとおりです。 + +`@Override boolean _isFinal() { return _final && _t._isFinal(); }` + +最初のフィールド `List*? !next` は non-final なので、すぐ `false` を返します。これで `List` の `_isFinal` が止まり、`isFinal()` 全体が `false` を返して再帰を終了／閉じます。`VISIT` もクリアします。 + +### 循環する読み取り専用／final 型の作成 + +構築してからインターンする手順を明確にするため、すべての型に一意 ID を付けましょう。一意な型の後ろに UID の例を付けた `List` 型を示します。フィールドも型なので UID を持ちます。 + +``` +struct List#2 { // struct List has UID#2 + List#2*?#3 !next#4, // Field next has UID#3, type ptr-or-null#3 to List#2 + str#1 !name#5 // Field name has UID#5, type str#1 +}; +``` + +同じ UID が繰り返されることから、`List#2` が2回現れています。List が循環しているためです。 + +今度は実際に循環する型を作る必要があり、`makeRO()` は次の行に進みます。 + +`return recurOpen()._makeRO().recurClose();`. + +再び `recurOpen` が再帰走査を開始／開き、それから子の Type クラスそれぞれでオーバーライドする `_makeRO()` を呼びます。`TypeStruct` 版を見ます。 + +```java +// Make a read-only version +@Override TypeStruct _makeRO() { + // Check for already visited + TypeStruct ts = (TypeStruct)VISIT.get(_name); + if( ts!=null ) return ts; // Already visited + ts = recurPre(_name,_open); // Make a new type with blank fields + Field[] flds = ts._fields; + for( Field fld : flds ) fld._final = true; + + // Now start the recursion + for( int i=0; i<flds.length; i++ ) + flds[i].setType(_fields[i]._t._makeRO()); + + return ts; +} +``` + +最初は **test-and-set** です。**検査** は型名に基づきます。`VISIT` から `List` TypeStruct の取得を試し、成功したら再帰せず早期に返します。つまり読み取り専用の型循環内では `List` オブジェクトは1つだけです。「整数の List」や「List の List の……」を含む複数の入れ子循環の絡み合いも考えられますが、ここでは簡単さのため、`List` のインスタンスを1つだけに近似します。 + +この例で初めて `List` を訪問すると `VISIT` に見つかりません。次の `ts = recurPre(_name,_open)` は共通の再帰前処理です。新しい `TypeStruct` を作り、`VISIT` 表に **設定** します。新しいものは、すべてのフィールドを備え、まだその型が接続されていない、空の `List` 版です。すぐにフィールドを final にしますが、型はまだありません。 + +> 訳注：原文の「all !fields !attached」は、続く説明と図に合わせて、フィールドの型が未設定である状態として訳しています。 + +``` +struct List#12 { + ____ next#14, + ____ name#15 +} +``` + +最後にすべてのフィールド型で `_makeRO` を再帰呼び出しし、設定します。`TypeMemPtr` に `_fields[i]._t._makeRO()` を呼ぶと、再帰する `List` の `_makeRO()` を呼んだ後に、新しい TMP を作ります。 + +この再帰は `TypeStruct._makeRO()` へ戻り、同じ型名で `VISIT` 表にヒットします。最初のフィールド設定を巻き戻すと、次になります。 + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + ____ name#15 +} +``` + +すべての型が新しい UID になっていることに注目してください。まだインターンできないので、以前の型にはできません。2番目のフィールド `str name` はすでに存在するため、次になります。 + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + str#2 name#15 // Reuse the interned type str#2 +} +``` + +ここで再帰を巻き戻し、複雑な `Type.recurClose()` に入ります。いくつかの例でコードを1ステップずつ実行してみるとよいでしょう。`TypeTest.testList` がこれらの型を構築します。高水準での概要は次のとおりです。 + +管理を容易にするため、訪問したすべての型を `VISIT` からコピーします。すでにインターン済みのものを発見したら後続の処理から除去しますが、HashMap 内にない方が簡単です。 + +**走査 #1:** 循環に属さない既存のインターン済み部分を探し、置き換えます。新しい型循環から古いインターン済み型へポインタが出ているのに、そのコピーを作ってしまっている場合があります。この段階の後も新しい循環は残りますが、出力辺は可能なら以前の型を指します。置き換えた型は、遅延した `FREES` リストへ入ります。 + +**走査 #2:** すべての型は *双対* を事前計算して直接使えるようにしています。ここで再帰的な循環する双対を作ります。 + +**走査 #3:** 新しい型を登録します。新しくインターンされた型への共通ポインタをここで発見する *可能性がある* ので、進みながら再び検査・置換し、使わない型を再度遅延 `FREES` リストへ入れます。この段階はハッシュ表検索を必要とし、それには循環ハッシュと循環 equals が必要です。 + +**走査 #4:** 遅延解放するすべての型をここで解放し、将来の型生成で再利用します。 + +最終的に、新しい `List` の循環型は完全にインターンされます。読み書き可能版 `List#2` は同じ読み書き可能版 `List#2` を指し、読み取り専用版 `List#12` は同じ読み取り専用版 `List#12` を指します。 + +### 循環する HashCode と Equals + +循環する `hashCode` と `equals` はさらに説明が必要です。2つの循環を等価比較するとき、比較の開始位置に関係なく等価であってほしいのです。つまり循環 `A<->B` は循環 `B<->A` と等しいべきです。両方のハッシュコードは同じでなければならず、順序で変化するハッシュは使えません。 + +たとえば A の静的ハッシュ値が1で、さらに B のハッシュから再帰的な成分があり、逆に B の静的値が3で A からの再帰成分があるとします。`parent.hash*7 + child.hash` で計算すると、A からは `A.hash * 7 + B.hash`、つまり `1 * 7 + 3 == 10` です。後で B から始めると `B.hash * 7 + A.hash`、つまり `3 * 7 + 1 == 22` になります。ハッシュが異なるため、ハッシュ表が等価性を見逃す可能性があります。また循環で単純に再帰下降すれば、スタックオーバーフローまで再帰してクラッシュします。 + +`TypeStruct.hash()` が再帰しないようにして解決します。そのためハッシュ関数はやや弱く、フィールド名とエイリアスだけに依存します。 + +*循環 equals* は `VISIT` 表が空でないことにより発動し、`VISIT` と関心を分離するため、別の訪問表 `CEQUALS` を使います。循環 equals 検査は通常の `eq` と同様、構成部分を再帰下降し、最初に確定的な静的検査を行い、再帰前にはおなじみの **test-and-set** を使います。 + +同じ2型を再び循環 equals で比較したら、ほかがすべて等しい限り、循環についても等しいと仮定します。 + +## メソッド、final フィールド、クラス + +メソッドは、構造体内で宣言され、暗黙の `self` 引数を取る、単なる関数値（final フィールド）です。 + +元の構造体定義で宣言した final フィールドは *値* であり、変化できません。すべてのインスタンスで同じです。構造体のメモリ占有部分から、final フィールドの値の集まりである *クラス* へ移動します。クラスは単なる名前空間で具体的な実装を持たず、実体化されません。 + +```java +struct vecInt { + u32 !len; // Actual number of elements + int[] !buf; // Array of integers. + + // Since "add" is declared with `val` in the original struct definition, + // it is a final field and is moved out of here to the class. + + // Method: Internal: copy buf to a new size + val _grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i<len; i++ ) + buf2[i] = buf[i]; + buf = buf2; + }; + + // Method: Add an element, growing the backing array when needed. + val add = { int e -> + if( len >= buf# ) _grow(buf#*2); + buf[len++] = e; + return self; + }; + + +}; + +val primes = new vecInt{buf = new int[4];}.add(2).add(3).add(5).add(7).add(11); +``` + +ここで `val add` フィールドは、定数関数値である *値* フィールドです。基本的な `vecInt` オブジェクトから `vecInt` の *クラス* へ移り、オブジェクト内で記憶領域を占めません。`_grow` も同様です。そのため `vecInt` インスタンスのサイズは、`u32` の長さと配列ポインタに、配置調整のパディングを加えたものです。配列ヘッダと要素は別の割り当てを占めます。拡張後の古いバッファの回収は、この例の範囲外です。`return primes.len*100+primes.buf[4];` を追加すると、RISC-V と ARM の両方で511になります。 + +## RegAlloc の改良: 多数の使用のグループ化 + +第22章では色の優先度と安いスピルの順序を改善しました。この章では、使用が互換性のないレジスタを要求する、よく使う値を分割する方法を追加します。たとえば複数のシフトが同じカウントレジスタを必要とし、別の使用が異なるレジスタを必要とする場合です。互換グループごとに1コピーを共有すると、使用ごとに別のコピーを挿入するのを避けられます。 + +割り当て器は、空のレジスタマスクと、2つより多い固定レジスタ使用を持つ、単一定義の区間にこれを適用します。重なる使用マスクの共通部分を取り、グループ化します。グループを狭めても以前の使用と互換なので、1走査で十分です。交わらないマスクは別グループにします。入力を接続し直す前に異なる使用側のスナップショットを取り、スケジューリング専用辺は無視し、値が複数引数を供給しても呼び出しを1回だけ数えます。 + +複数の呼び出しで使う値は、レジスタ破壊が共有コピーの利点を打ち消しがちなので、グループ化しません。すべての使用のループ深さが同じ場合に既存コピーを分割することも含め、通常のループ境界分割を代替として保持します。低頻度側を先にするループ分割は第24章、面積／コストのスピル順位付けは第25章に残します。 + +第21章の隣接コピー転送も引き継ぎます。彩色後、次の命令に唯一の使用がある場合、オペランドマスクが許し、2アドレスの結び付きを壊さなければコピー元レジスタを読めます。以下の表は、この整理と遅延メモリの前方移植を含みます。第22章の群には、以前の監査後に追加した移動0の C 戻り値 ABI 確認2件も含むようになりました（24ではなく26項目）。 + +このディレクトリで `make spill-stats` を実行してください。以下の全行は **この章のコンパイラ**、シード123、各群の固定されたソース／対象の組み合わせを使います。Windows 実行は x86 SystemV/Win64 と RISC-V/ARM SystemV を合わせます。診断マシングラフは別に確認し、数には寄与しません。 + +| プログラム群 | コンパイル数 | 残存する移動 | ループ重み付き移動 | +|---|---:|---:|---:| +| 第20章 | 39 | 323 | 442 | +| 第21章 | 52 | 433 | 965 | +| 第22章 | 26 | 67 | 67 | +| 第23章 | 30 | 78 | 225 | +| **合計** | **147** | **901** | **1,699** | + +`_spills` はレジスタ移動を含む残存 SplitNode を数え、`_spillScaled` は `8^loopDepth` で重み付けします。生成移動のコンパイラによる推定であり、実行時メモリアクセスではありません。報告器は個々のコンパイルと CPU/ABI 合計を表示し、スピル期待値や実行確認が失敗すれば、依然として失敗を報告します。 + +以前の監査では、隣接コピー転送前にグループ化を無効にしても、**同じ933移動／1,745重み付き移動** でした。元のグループ化コードも同じ合計です。したがってこのスイートには、グループ化によるスピル改善は見られません。縮小したマシングラフの回帰テストは、旧実装の null マスクによるクラッシュも含め、互換性と呼び出しの規則を検証します。もっともらしい割り当て器のヒューリスティックであっても、効果を主張するには、それが実際に適用される処理対象での測定が必要です。 + +以前の群だけでは、第22章コンパイラは838移動／1,496重み付き移動で、このコンパイラは849／1,514でした。この比較は割り当て以外の変更を含みます。特に第20章の固定した String 入力は、ここでは最適化後も残り16重み付き移動を要しますが、第22章はこのシードで除去しました。その差をグループ化に帰するのは誤解を招きます。 + +元の64ビット `person21` とガード付き `stringHash21` 入力は、第21章の群を維持します。改訂した String 入力とこの章で有効にした2つのエンコーディングテストは第23章の群に属します。群を固定することで、言語とテストが成長しても、以後の比較に意味が保たれます。 diff --git a/docs/chapter23/README.md b/docs/chapter23/README.md new file mode 100644 index 00000000..747b37e3 --- /dev/null +++ b/docs/chapter23/README.md @@ -0,0 +1,463 @@ +# Chapter 23: Methods and Revisiting Types + +English | [日本語](README.ja.md) + +[Previous: Chapter 22](../chapter22/README.md) | +[Next: Chapter 24](../chapter24/README.md) + +In this chapter we add *methods*, functions defined in structs which take a +hidden `self` argument and can access the struct fields. Here is an +`indexOf` method in a String-like class: + +```java +// A String-like class, with methods +struct String { + u8[~] buf; // Buffer of read-only characters + + // Return the index of the first character 'c' or -1 + val indexOf = { u8 c -> // Hidden 'self' argument + for( int i=0; i<buf#; i++ ) // Direct access to `buf` field + if( buf[i]==c ) + return i; + return -1; // 'c' not in 'self' + }; +}; +``` + +Also in this chapter we revisit our Types and make some major changes: +- Types are now *cyclic*: a Type can (indirectly) point to itself. +- Types remain + [*interned*](https://en.wikipedia.org/wiki/Interning_(computer_science)) or + [*hash-consed*](https://en.wikipedia.org/wiki/Hash_consing). +- Type objects are managed via an object pool. +- Newly created types probe the interning table, and if a hit is found, the + original is used, and the new type is returned to the object pool. +- The intern table hit rate is something like 99.9%; nearly all types created + have already been created! This last point turns into an interesting + performance win; much of the work in an optimizing compiler deals with + manipulating Types, keeping the count of Types small and fitting in the + faster levels of cache is a nice payoff. +- Many of the interning algorithms require cycle-handling via some kind of + "visit bit". One easy way to do this is add a *unique id* UID to every type, + a small dense integer that is used in bit-sets to avoid visiting a type more + than once. Smaller UIDs use smaller bit-sets, which again fit in the faster + cache levels. +- As a consequence, our types are cyclic (the goal!), and **faster** and have a + more complex implementation. **Using** the types remains the same; the same + Type API is used when creating them, MEETing, making Read-Only, printing, + etc; only the implementation details change. + + +You can also read [this chapter](https://github.com/SeaOfNodes/Simple/tree/linear-chapter23) in a linear Git revision history on the [linear](https://github.com/SeaOfNodes/Simple/tree/linear) branch and [compare](https://github.com/SeaOfNodes/Simple/compare/linear-chapter22...linear-chapter23) it to the previous chapter. + + +Here is the [complete language grammar](23-grammar.md) for this chapter. + +## Why Cyclic Types? + +Cyclic types give us a sharper analysis than the alternative, and thus admit +more programs or better optimizations or both. In Simple's case Types are also +used for type-checking, so sharper types means we allow more valid programs. + +**Why Cyclic Types Now**? Because we hit them as soon as we allow a +function definition inside of a struct which takes the struct as an argument, +i.e. *methods* taking a *self* argument. + +Let's look at our `String.indexOf` example above. Here we define a `String` +with an `indexOf` method; a hidden argument string `self` is passed in +and searched. What is the type of `struct String`? + +`struct String { u8[~] buf; { !String !self, u8 c -> int } indexOf; }` + +It is the type named `String` with a field `u8[~] buf` and a final assigned +constant field `indexOf`, itself with type `{ !String !self, u8 c -> int }`. +i.e., the type of `String` has a reference to itself, nested inside the type of +`indexOf`.... i.e. `String`'s type is *cyclic*. + + +## Less Cyclic Types + +This problem of cyclic types has been around for a long time, and there are a +number of tried and true methods for dealing with them. One easy one is to +have a type *definition* and a separate type *reference*. The reference refers +to the type by doing some kind of lookup; an easy one is via the type name and +the parser's symbol table i.e., some kind of hash table lookup. + +In this model the cycle is effectively avoided; all "back edges" in the type +cycle are really done by the reference edge (itself possibly a hash table +lookup). + +So why not go down this route? + +Because all type references lead back to the same type definition - which +means any specialization of type information is lost, because *all* type +references lead back to the same definition and you end up taking the MEET +over *all* paths. + +Here's an example, a Linked List with a Java `Object` or a C `void*` payload: + +```java +struct List { + !List !next; + Object payload; // equivalently for C: void* +} +// Then walk a collection of ints and build a List: +List nums = null; +for( int x : ary_ints ) + nums = new List{next=nums; payload=x; } + +// Again for strings: +List strs = null; +for( String x : ary_strs ) + strs = new List{next=strs; payload=x; } +``` + +What is the type of `nums`? It's `*List`... which is: + +``` +struct List { List *next; Object payload } +``` + +No sharpening of `Object` to `int` nor `String` because every List object +has a payload of `Object` and `Object` MEET `int` is back to `Object`. + +If we allow truly cyclic types then in these kinds of places we can discover +(or infer) a sharper type: `*List<int> { *List<int> next, int payload }` +basically building up *generics* in the optimizer. This is not generics in the +language nor type-variables per-se, but it goes a long way towards them. + + +## Handling cyclic types + +In this Chapter Simple handles cyclic types directly. This means we have +`Type` objects whose child types can point back to the original - and that +means +[*recursive descent*](https://en.wikipedia.org/wiki/Recursive_descent_parser) +no longer works on Types. + +Up till now we've used recursive descent when building up Types: child types +are built first, then interned, then the interned children are used to build up +the next layer. Because each layer is interned and because recursive descent +stops at interned Types we avoid repeating work at shared Types. This makes +operations on the current Types linear in the *delta* between the old and new +Types, i.e. incremental and fast. + +With the new cyclic types we now run into the problem that we cannot intern a +cycle until we see the whole cycle. Also hash tables require an equality +check and we cannot use recursive descent to compare a cycle for equality. + +The standard way to deal with cycles in a graph is with some kind of *visited* +notion, a "I have been here before" indicator. We will use a hashtable keyed +from a unique type ID; "visited" just means your unique ID is a key in the +table. Every Type thus picks up a unique ID from a global counter. Since we +will be interning Types we only need as many unique IDs as we have unique Types +(plus a few spare to build and intern cycles). From prior history I know this +number typically maxes out in the low thousands so a small integer will do. + +Another thing - we want to keep as much of our existing infrastructure as +we can, so we are going to keep all our existing recursive descent visitations +with some small modifications. + +`TypeStructs` exist in every Type cycle (except pure function type cycles, +where a function takes *itself* as an argument, which are weird and we kinda +don't care how they get handled). So in the core part of every `TypeStruct` +generator we'll set an element in a global `VISIT` hashtable to signal the +start of a cyclic Type creation - and we'll check for those elements to stop +cycling. + + + + +Time for an example! + +Let's go with a linked list, where we might have cycles of unrelated payloads +(but here only strings). Mind you, a linked list is almost always the wrong +structure for any given job (being wildly inefficient compared to easy +alternatives) but it is a great tutorial data structure. + + +```java +struct List { + !List? !next; // Next pointer or null + str !name; // Payload +}; +``` + +And the type of this struct matches its declaration: + +`struct List { List*? next, str !name };` + +We can use this to build up a list of strings: + +```java +var list = new List{ name="Hello"; }; +list = new List { list, name="World"; }; +``` + + +### Checking a cyclic type for Read-Only / Final + +Suppose at some point we want to make a read-only immutable version: +```java +val hello = list; // Make a read-only version +print(hello); // Pass along the read-only version +``` + +What is the type of `hello`? It is the read-only type of `List`... and `List` is +a cyclic type. Follow the implementation of +[`Type.makeRO`, `isFinal`, and `_isFinal`](../../src/main/java/com/seaofnodes/simple/type/Type.java). + +We call `recurOpen()` to start/open the recursive walk, do the recursion +calling `_isFinal()` and end/close the recursive walk, and return a boolean +answer. `_isFinal()` is NOT Java final, and is overridden in the Type subclasses. +Subclasses implement the check for their own representation. For example, +[`TypeMemPtr._isFinal`](../../src/main/java/com/seaofnodes/simple/type/TypeMemPtr.java) +reads the pointer's access permission, while +[`TypeStruct._isFinal`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +walks the fields and handles cycles. + +Here we see a common pattern in dealing with cycles: the **test-and-set**. We +check for any hard and fast answers (open structs are never read-only; they are +only partially defined and as-yet-unparsed non-final fields may appear), then +we **test** if we have been here before, and if so stop the recursion and +return some kind of answer. For "isFinal" the returned answer is "yes final" +as long as everything else in the cycle is also final. + +If we have not already checked this Type, we **set** the "visit" bit indicating +we've been here before, and then proceed to do normal recursive-descent on the +fields asking the same question recursively. + +For our example, we open the recursion (set a sentinel in `VISIT`), call +`makeRO` on `struct List`, which then calls `_isFinal` which then checks +the `_open` flag (not open), checks the `VISIT` (not visited), sets the +UID in `VISIT` and starts walking the fields. +[`Field._isFinal`](../../src/main/java/com/seaofnodes/simple/type/Field.java) +checks both the field's binding and its type. + +The first field is `List*? !next`, which is not-final, so immediately returns +`false`, which stops `_isFinal` on `List` and the whole `isFinal()` call returns +`false`, and ends/closes the recursion (clears `VISIT`). + + +### Making a cyclic type for Read-Only / Final + +To make the build-then-intern more obvious, let's put unique IDs on all our +Types. Here is the Type of `List` with sample UIDs following each unique type. +Fields are also just types so also get UIDs. + +``` +struct List#2 { // struct List has UID#2 + List#2*?#3 !next#4, // Field next has UID#3, type ptr-or-null#3 to List#2 + str#1 !name#5 // Field name has UID#5, type str#1 +}; +``` + +You can see from the repeated UIDs that `List#2` happens twice... because List +is cyclic. + +Now we do really need to make a cyclic type, and so our `makeRO()` call falls +into the recursive path in +[`Type.makeRO`](../../src/main/java/com/seaofnodes/simple/type/Type.java). + +Once again `recurOpen` starts/opens our recursive walk, and then we call +`_makeRO()` which is overridden in the child Type classes. Follow +[`TypeStruct._makeRO` and `recurPre`](../../src/main/java/com/seaofnodes/simple/type/TypeStruct.java) +for the implementation. + +First up is the **test-and-set**. The **test** is by type name; we attempt to +get a `List` TypeStruct from `VISIT`, and if successful we return early - +without recursion. This means we can only have one `List` object in a R/O +cycle of types. You can imagine a tangle of multiple nested cyclic types where +some are "List-of-int" and some are "List-of-Lists-of-", but here in the name +of simplicity we choose to approximate our types to only a single instance of +`List`. + +In this example on first visit of `List` we will miss in `VISIT`. The next call +to `ts = recurPre(_name,_open)` does common shared pre-recursive work: we make +a new `TypeStruct` and **set** it in the `VISIT` table. The new `TypeStruct` +is a blank version of `List` with all !fields !attached; we force these fields to +be final right away but they are missing their types: + +``` +struct List#12 { + ____ next#14, + ____ name#15 +} +``` + + +Finally, we recursively call `_makeRO` on all the field types and set them in. +We call `_fields[i]._t._makeRO()` on a `TypeMemPtr` which makes a new +TMP after calling `_makeRO()` on the recursive `List`. + +This recursion comes right back to `TypeStruct._makeRO()`, and hits in the +`VISIT` table on the same type name. Unwinding the first field set, we have: + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + ____ name#15 +} +``` + +You should notice all new UIDs for all the Types. Since we cannot intern yet, +we cannot end up with prior types. The second field `str name` does already +exist, so we end up with: + +``` +struct List#12 { + List#12 *? #13 next#14, // Recursive next field makes a cycle + str#2 name#15 // Reuse the interned type str#2 +} +``` + +At this point the recursion unwinds and we head into the complex +[`Type.recurClose()`](../../src/main/java/com/seaofnodes/simple/type/Type.java). +You might try single-stepping through +[`TypeTest.testList`](../../src/test/java/com/seaofnodes/simple/TypeTest.java), +which builds these types. Here is a high +level summary: + +Copy all the visited types out of `VISIT` for easier management; we might find +some of these types already interned, and then we'll remove them from further +processing; this is easier if they are not in a HashMap. + +**Pass#1:** look for pre-existing interned parts not in any cycle, and just +replace them. We could have a new cycle of Types with pointers off to older +interned types... that we made copies of. After this step, we'll still have +new cycles but the output edges will point to prior types if possible. +Replaced types hit the delayed `FREES` list. + +**Pass#2:** All types have their *duals* pre-computed and directly available. +Make the recursive cyclic duals now. + +**Pass#3:** Install the new types. It *is* possible to now discover common +pointers to newly interned types, and so again we need to test and replace as +we go (and put the unused types on the delayed `FREES` list again). This step +requires hash table probe - which requires a cyclic hash and cyclic equals. + +**Pass#4:** Free up all the delayed-free Types now, to be recycled in future +Type productions. + +In the end, the new `List` cyclic type is wholly interned - with a R/W version +of `List#2` pointing back to the R/W `List#2` and the R/O version `List#12` +pointing back to the same R/O `List#12`. + + + +### Cyclic HashCode and Equals + +Cyclic `hashCodes` and `equals` deserve more discussion. When comparing two +cycles for equivalence we want to be equivalent regardless of where the +comparison starts. i.e. cycle `A<->B` should be equal to cycle `B<->A`. This +means they both need the same hashcode, and this means we cannot use +order-varying hashes! + +E.g. Suppose A has static hash value 1 (plus something recursively from B's +hash), and vice-versa B has static hash value 3 (and something recursive from +A), and we compute hashes as `parent.hash*7 + child.hash`. If we compute A's +hash as `A.hash * 7 + B.hash` we get `1 * 7 + 3 == 10`, and then later we start +from B we get: `B.hash * 7 + A.hash` and which then becomes `3 * 7 + 1 == +22`... and their hashes differ so the hash table might miss the equivalence. +Also, if we simply use recursive descent in the cycle we'll +recurse until stack overflow and crash. + +We fix this by having `TypeStruct.hash()` *not* recurse - thus its hash +function is somewhat weak, depending only on the field names and aliases. + +*Cyclic-equals* is triggered by the `VISIT` table being not-empty, and uses +another unrelated *visit* table, the `CEQUALS` table, to separate concerns from +`VISIT`. The cycle-equals check proceeds like the normal `eq` with recursive +descent on the parts, and some up-front hard-and-fast static checks - and the +ubiquitous **test-and-set** pattern before the recursion. + +If we ever compare the same two types for cycle-equals again, we assume they +will be cycle-equals (all other things being equals). + + + +## Methods and Final Fields and Classes + +Methods are simply function values (final fields) declared inside a struct that +take an implicit `self` argument. + +Final fields declared in the original struct definition are *values* and cannot +change; they are the same for all instances. They get moved out of the +struct's memory footprint and into a *class* - a collection of values from the +final fields. Classes are just plain namespaces and have no concrete +implementation; they are not reified. + +```java +struct vecInt { + u32 !len; // Actual number of elements + int[] !buf; // Array of integers. + + // Since "add" is declared with `val` in the original struct definition, + // it is a final field and is moved out of here to the class. + + // Method: Internal: copy buf to a new size + val _grow = { int sz -> + var buf2 = new int[sz]; + for( int i=0; i<len; i++ ) + buf2[i] = buf[i]; + buf = buf2; + }; + + // Method: Add an element, growing the backing array when needed. + val add = { int e -> + if( len >= buf# ) _grow(buf#*2); + buf[len++] = e; + return self; + }; + + +}; + +val primes = new vecInt{buf = new int[4];}.add(2).add(3).add(5).add(7).add(11); +``` + +Here the `val add` field is a *value* field, a constant function value. It is +moved out of the basic `vecInt` object into `vecInt`'s *class*, and takes no +storage space in `vecInt` objects. The same happens for `_grow`. The size of +a `vecInt` instance is thus its `u32` length and array pointer, plus alignment +padding. The array header and elements occupy a separate allocation. Reclaiming +the old buffer after growth is outside this example. Appending +`return primes.len*100+primes.buf[4];` produces 511 on both RISC-V and ARM. + +## RegAlloc improvements: grouping popular uses + +Chapter 22 improved color preferences and cheap-spill ordering. This chapter +adds a way to split a popular value whose uses demand incompatible registers. +For example, several shifts may need the same count register while another use +needs a different register. Sharing one copy for each compatible group can +avoid inserting a separate copy at every use. + +The allocator applies this to a single-definition live range with an empty +register mask and more than two fixed-register uses. It intersects overlapping +use masks into groups; narrowing a group keeps it compatible with its earlier +users, so one pass suffices. Disjoint masks start separate groups. It snapshots +distinct users before rewiring their inputs, ignores scheduling-only edges, +and counts a call once even when the value supplies several arguments. + +Grouping declines values used by multiple calls, whose register kills tend to +undo the benefit of a shared copy. The usual loop-boundary splitting remains +the fallback, including splitting an existing copy when all uses have the same +loop depth. Cold-first loop splitting is left for Chapter 24; area/cost spill +ranking remains for Chapter 25. + +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 20 | 22 / 13 | — / — / 161 | 55,173 / 5,407 / 174 | 58,751 / 9,099 / 175 | 58,736 / 9,084 / 184 | +| Ch 21 | 20 / 18 | | 6,207 / 261 / 461 | 6,324 / 379 / 475 | 6,326 / 381 / 475 | +| Ch 22 | 14 / 8 | | | 198 / 60 / 7 | 194 / 56 / 7 | +| Ch 23 | 14 / 8 | | | | 630 / 160 / 36 | +<!-- spill-matrix:end --> diff --git a/docs/chapter23/examples/A_helloWorld.smp b/docs/chapter23/examples/A_helloWorld.smp new file mode 100644 index 00000000..07ff935f --- /dev/null +++ b/docs/chapter23/examples/A_helloWorld.smp @@ -0,0 +1,3 @@ +// -*- mode: java; -*- +sys.io.p("Hello, World!"); +return 0; diff --git a/docs/chapter23/examples/BubbleSort.smp b/docs/chapter23/examples/BubbleSort.smp new file mode 100644 index 00000000..938e3181 --- /dev/null +++ b/docs/chapter23/examples/BubbleSort.smp @@ -0,0 +1,37 @@ +// -*- mode: java; -*- + +// An implementation of +// https://sampleprograms.io/projects/bubble-sort/ +// +// Bubble sort, with reading (parsing) and writing (formatting) the data. + +val sort = { !sys.aryi64 nums -> + var done = false; + while( !done ) { + done = true; + for( var i = 0; i < nums.len-1; i++ ) + if( nums.buf[i] > nums.buf[i+1] ) { + int tmp = nums.buf[i]; + nums.buf[i] = nums.buf[i+1]; + nums.buf[i+1] = tmp; // Swap + done = false; + } + } +}; + +// Read from stdin a line of the form "[ 4, 3, 2, 1]" and print it sorted. +val main = { -> + // Parse array of numbers from stdin + var nums = sys.parseAryI64( sys.io.stdin() ); + if( !nums ) { + sys.io.p("stdin must look like [4, 3, 2, 1]"); + return 1; + } + + // Bubble sort array of integers + sort(nums); + + // Print a list of numbers to stdout + nums.str().write(1); + return 0; +}; diff --git a/docs/chapter23/font-awesome-4.7.0.zip b/docs/chapter23/font-awesome-4.7.0.zip Binary files differnew file mode 100644 index 00000000..b6bdb4bd --- /dev/null +++ b/docs/chapter23/font-awesome-4.7.0.zip diff --git a/docs/chapter23/ifg_trim.pdf b/docs/chapter23/ifg_trim.pdf Binary files differnew file mode 100644 index 00000000..d952fd4f --- /dev/null +++ b/docs/chapter23/ifg_trim.pdf diff --git a/docs/chapter23/lattice.gv b/docs/chapter23/lattice.gv new file mode 100644 index 00000000..8661082d --- /dev/null +++ b/docs/chapter23/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/chapter23/lattice.svg b/docs/chapter23/lattice.svg new file mode 100644 index 00000000..e72b473b --- /dev/null +++ b/docs/chapter23/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/chapter23/lattice2.gv b/docs/chapter23/lattice2.gv new file mode 100644 index 00000000..6aa37fa0 --- /dev/null +++ b/docs/chapter23/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/chapter23/lattice2.svg b/docs/chapter23/lattice2.svg new file mode 100644 index 00000000..8b682aa7 --- /dev/null +++ b/docs/chapter23/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/chapter23/pardoe.docx b/docs/chapter23/pardoe.docx Binary files differnew file mode 100644 index 00000000..24fde921 --- /dev/null +++ b/docs/chapter23/pardoe.docx diff --git a/docs/chapter23/webtcp.min.js b/docs/chapter23/webtcp.min.js new file mode 100644 index 00000000..bf23ee5a --- /dev/null +++ b/docs/chapter23/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 |
