WIP: performance improvements

2 files changed, 253 insertions, 241 deletions

diff --git a/elymas/lib/parser.ey b/elymas/lib/parser.ey
index 90456bf..da562e3 100644
--- a/elymas/lib/parser.ey
+++ b/elymas/lib/parser.ey
@@ -10,8 +10,9 @@
     { time keys { _ dump _ time -01 . txt .produce .u " μs" cat dump count -01 . txt .produce .u " calls" cat dump } each }
   > -- /perfstats deffd "τ" defq
 
-  { =*body { 0 ==again { 1 =again } body again } { } loop } /redoing deffd
+  { =*body { 0 ==again { 1 =again }' body again } { }" loop } /redoing deffd
   { =*wasNew ==m ==k k m .has not { 1 k m =[] wasNew } rep } /enlarge deffd
+
 #  { ==a a len 1 gt {
 #      0 ==i 0 ==j
 #      a dom { =i
@@ -36,253 +37,264 @@
   > -- /children deffd
   0 10 range { _ { { 0 -01* } rep 2 -01* }_ -01 txt .produce .u deffd }' each
 
-  {
-    [ ] ==rules 0 ==nextNonTerminalName
-    { ==nt ==t --e sys .typed .type 1 eq t nt ? * } ":?" deffd
-    { nextNonTerminalName _ 1 add =nextNonTerminalName txt .produce .u ==name scope } /nt deffst
-    { ==name scope } /nonterminal deffst
-    { ==action ==expansion ==nonterminal
-      rules [ [ nonterminal expansion action ] ] cat =rules
-    } /rule deffst
-    { ==start
-      rules [ [ < "" ==name > [ start "" ] { } ] ] cat ==rules
-      map ==itemsets
-      map ==transitions # itemsetId -> label -> itemsetId
-
-      { ==nt rules { ==r 0 r * .name nt eq } grep } /findRules deffst
-      { ==itemset --rules
-        { [ 0 ] cat _ itemId itemset =[] } each
-        itemset
-      } /addRuleStartToItemSet deffst
-      { _ ==e { "t" e } { "n" e .name } :? cat } /tId deffst
-      { ==r
-        [
-          0 r * .name " "
-          1 r * |tId each " "
-          3 r * txt .produce .u "  "
-        ] |cat fold
-      } τitemId /itemId deffst
-      { --itemset dom { sort } τsort * |cat fold } τitemsestId /itemsetId deffst
-      { --itemset _ itemsetId itemsets =[] } τaddItemSet /addItemSet deffst
-      { ==itemset
-        "------" dump
-        itemset { ==r
-          3 r * ==pos
-          [
-            0 r * .name " -> "
-            1 r * dom { ==i
-              i pos eq { " . " } rep
-              i 1 r * * tId " "
-            } each
-            pos 1 r * len eq { " . " } rep
-          ] |cat fold dump
-        } each
-      } /dumpItemSet deffst
+  <
+    sys .typed .|type =*:SYSTYPEDTYPE
+    { ==nt ==t SYSTYPEDTYPE 1 eq t nt ? * } ":?" deffd
+    { _ ==e { "t" e } { "n" e .name } :? cat } /tId deffd
+    { ==r
+      [
+        0 r * .name " "
+        1 r * |tId each " "
+        3 r * txt .produce .u "  "
+      ] |cat fold
+    } /itemId deffd
+    { ==itemset --rules
+      { [ 0 ] cat _ itemId itemset =[] } each
+      itemset
+    } /addRuleStartToItemSet deffd
+    { --itemset dom _ len 1 gt { sort |cat fold }" { 0 -01* }" ? * }' /itemsetId deffd
+    { ==name scope } /nonterminal deffd
+    [ ] ==shiftActions # target state index -> shift action function
+    { ==target                 # lookahead consumed, quit statemachine loop --v
+      { target shiftActions len ge } { shiftActions _ len ==i [ { [ i -1302 ] 0 }' ] cat =shiftActions } loop
+      target shiftActions *
+    } /makeShiftAction deffd
+    { =*r 3 r 1 r len eq } /ruleAtEnd deffd
 
-      { =*r 3 r 1 r len eq } /ruleAtEnd deffst
-      { ==rulesToExpand
-        map ==expanded
+    {
+      [ ] ==rules 0 ==nextNonTerminalName
+      { nextNonTerminalName _ 1 add =nextNonTerminalName txt .produce .u ==name scope } /nt deffst
+      { ==action ==expansion ==nonterminal
+        rules [ [ nonterminal expansion action ] ] cat =rules
+      } /rule deffst
 
-        [
-          { rulesToExpand # into the result array
+      { ==start
+        rules [ [ < "" ==name > [ start "" ] { } ] ] cat ==rules
+        map ==itemsets
+        map ==transitions # itemsetId -> label -> itemsetId
+
+        { ==nt rules { ==r 0 r * .name nt eq } grep } /findRules deffst
+        { ==itemset
+          "------" dump
+          itemset { ==r
+            3 r * ==pos
             [
-            rulesToExpand { ==r
-              3 r * 1 r * * ==t
-              t { } {
-                t .name expanded .has not {
-                  1 t .name expanded =[]
-                  t .name findRules { [ 0 ] cat } each
-                } rep
-              } :?
-            } each
-          ] _ =rulesToExpand len } { } loop
-        ] |cat fold
-      } τnonterminalExpansion /nonterminalExpansions deffst
-      { ==itemset
-        itemset itemsetId ==fromId
-        itemset { ruleAtEnd not }' grep ==steppingRules
-
-        steppingRules nonterminalExpansions =steppingRules
-
-        map ==rulesByStep # tId -> [ rule ... ]
-        steppingRules { ==r
-          3 r * 1 r * * tId ==eId
-          eId rulesByStep .has { eId rulesByStep * } { [ ] } ? *
-          [ r ] cat eId rulesByStep =[]
-        } each
-
-        rulesByStep dom { ==eId
-          map ==nextItemSet
+              0 r * .name " -> "
+              1 r * dom { ==i
+                i pos eq { " . " } rep
+                i 1 r * * tId " "
+              } each
+              pos 1 r * len eq { " . " } rep
+            ] |cat fold dump
+          } each
+        } /dumpItemSet deffst
+
+        { ==rulesToExpand
+          map ==expanded
+
+          [
+            { rulesToExpand # into the result array
+              [
+              rulesToExpand { ==r
+                3 r * 1 r * * ==t
+                t { } {
+                  t .name expanded .has not {
+                    1 t .name expanded =[]
+                    t .name findRules { [ 0 ] cat } each
+                  } rep
+                } :?
+              } each
+            ] _ =rulesToExpand len } { } loop
+          ] |cat fold ==steppingRules
+
+          map ==rulesByStep # tId -> [ rule ... ]
+          steppingRules { ==r
+            3 r * 1 r * * tId ==eId
+            eId rulesByStep .has { eId rulesByStep * } { [ ] } ? *
+            [ r ] cat eId rulesByStep =[]
+          } each
+
+          rulesByStep
+        } /nonterminalExpansions deffst
+        { ==itemset
+          itemset itemsetId ==fromId
+          itemset { ruleAtEnd not }' grep ==steppingRules
+
+          steppingRules nonterminalExpansions ==rulesByStep # tId -> [ rule ... ]
+
+          rulesByStep dom { ==eId
+            map ==nextItemSet
+
+            eId rulesByStep * {
+              [ -01 4 dearray 1 add ] _ itemId nextItemSet =[]
+            }' each
+
+            nextItemSet itemsetId ==toId
+            toId itemsets .has not {
+              nextItemSet toId itemsets =[] # add new itemset
+              # nextItemSet dumpItemSet perfstats
+              nextItemSet stepItemSet
+            }' rep
+
+            fromId transitions .has not { map fromId transitions =[] }' rep
+            toId eId fromId transitions * =[]
+          } each
+        } /stepItemSet deffst
+        { ==lookahead ==rulesAtEnd
           [ ] ==r
+          rulesAtEnd { =r lookahead 0 r * .name followSets .has }' grep
+          _ len _ ==l 1 gt { /reduce_reduce_conflict die }' rep
+            l dearray l
+        } /canReduce deffst
+        map ==reduceActions # itemid -> reduce action function
+        { _ ==item itemId ==id
+          id reduceActions .has not {
+            0 item * .name ==nt
+            1 item * len ==tokill
+            2 item * =*reduceAction
+            { -- ==states # value dropped
+              states reduceAction ==value
+              tokill { 0 states * =states }' rep
+              states len 0 gt {
+                nt 1 states * nonterminalActions * * ==target
+                target 0 lt |unexpectedNonterminal {
+                  [ states target value ] =states
+                }' ? *
 
-          eId rulesByStep * { =r
-            [ r 4 dearray 1 add ] _ itemId nextItemSet =[]
-          }' each
-
-          nextItemSet itemsetId ==toId
-          toId itemsets .has not {
-            nextItemSet toId itemsets =[] # add new itemset
-            nextItemSet dumpItemSet perfstats
-            nextItemSet stepItemSet
-          }' rep
-
-          fromId transitions .has not { map fromId transitions =[] } rep
-          toId eId fromId transitions * =[]
-        } each
-      } /stepItemSet deffst
-      { ==lookahead ==itemset
-        0 ==can [ ] ==rule
-        itemset |ruleAtEnd grep { ==r
-          lookahead 0 r * .name followSets .has {
-            can { /reduce_reduce_conflict die } rep
-            1 =can r =rule
+                # states len 0 gt { # DEBUG
+                #   1 states * theItemSets * dumpItemSet
+                # } rep
+              } rep
+              states 1 # lookahead not consumed, repeat loop
+            } id reduceActions =[]
           } rep
-        } each
-        can { rule } rep can
-      } /canReduce deffst
-      
-      map ==allNonTerminals
-      rules { 0 -01 * 1 -01 .name allNonTerminals =[] } each
-      map ==allTerminals
-      rules { 1 -01* { ==e e { 1 e allTerminals =[] } { } :? } each } each
-
-      map ==nullableNonTerminals
-      { [ -01 { _ ==e { 0 } { e .name nullableNonTerminals .has } :? }
-        each ] all } /isNullable deffst
-      { ==redo
-        rules { 1 -01* isNullable } grep {
-          0 -01* .name nullableNonTerminals |redo enlarge
-        } each
-      } redoing
-
-      allNonTerminals { -- map } '*0.0 =*firstSets # nonterminal -> terminal -> 1
-      { map ==result 0 ==finished { ==e
-        finished not {
-          e {
-            1 e result =[] 1 =finished
-          } {
-            e .name _ firstSets dom { 1 -01 result =[] } each
-                      nullableNonTerminals .has =finished
-          } :?
-        } rep
-      } each result } /firstSet deffst
-      { ==redo
-        rules { ==r 0 r * .name firstSets ==lhsSet 1 r * ==rhs
-          0 ==i
-          { { i 1 add =i } ; ==lookAtNextElement
-            i rhs len ge { 0 } {
-              i rhs * _ {
-                lhsSet |redo enlarge
-              } {
-                _ .name firstSets dom { lhsSet |redo enlarge } each
-                  [ -01 ] isNullable lookAtNextElement rep
-              } :?
-            } ? *
-          } redoing
-        } each
-      } redoing
-      
-      allNonTerminals { -- map } '*0.0 =*followSets # nonterminal -> terminal -> 1
-      { ==redo
-        rules { ==r 0 r * .name followSets ==lhsSet 1 r * ==rhs
-          rhs dom { _ ==i rhs *
-            _ { -- } {
-              .name followSets { |redo enlarge }_ ==put
-              i 1 add rhs len range rhs *
-              _ firstSet dom put each
-                isNullable { lhsSet dom put each } rep
+
+          id reduceActions *
+        } /makeReduceAction deffst
+
+        map ==allNonTerminals
+        rules { 0 -01 * 1 -01 .name allNonTerminals =[] } each
+        map ==allTerminals
+        rules { 1 -01* { ==e e { 1 e allTerminals =[] } { } :? } each } each
+
+        map ==nullableNonTerminals
+        { [ -01 { _ ==e { 0 } { e .name nullableNonTerminals .has } :? }
+          each ] all } /isNullable deffst
+        { ==redo
+          rules { 1 -01* isNullable } grep {
+            0 -01* .name nullableNonTerminals |redo enlarge
+          } each
+        } redoing
+
+        allNonTerminals { -- map } '*0.0 =*firstSets # nonterminal -> terminal -> 1
+        { map ==result 0 ==finished { ==e
+          finished not {
+            e {
+              1 e result =[] 1 =finished
+            } {
+              e .name _ firstSets dom { 1 -01 result =[] } each
+                        nullableNonTerminals .has =finished
             } :?
+          } rep
+        } each result } /firstSet deffst
+        { ==redo
+          rules { ==r 0 r * .name firstSets ==lhsSet 1 r * ==rhs
+            0 ==i
+            { { i 1 add =i } ; ==lookAtNextElement
+              i rhs len ge { 0 } {
+                i rhs * _ {
+                  lhsSet |redo enlarge
+                } {
+                  _ .name firstSets dom { lhsSet |redo enlarge } each
+                    [ -01 ] isNullable lookAtNextElement rep
+                } :?
+              } ? *
+            } redoing
           } each
-        } each
-      } redoing
-
-      # "" findRules map addRuleStartToItemSet closeItemSet _ addItemSet
-      "" findRules map addRuleStartToItemSet _ addItemSet ==initialItemSet
-      initialItemSet { stepItemSet } τstepItemSet *
-      "=====" dump itemsets |dumpItemSet each perfstats # DEBUG
-      
-      {
-      map ==itemsetIndices
-      0 ==i
-      [
-        itemsets { _ itemsetId i _ 1 add =i -01 itemsetIndices =[] } each
-      ] ==theItemSets
+        } redoing
+        
+        allNonTerminals { -- map } '*0.0 =*followSets # nonterminal -> terminal -> 1
+        { ==redo
+          rules { ==r 0 r * .name followSets ==lhsSet 1 r * ==rhs
+            rhs dom { _ ==i rhs *
+              _ { -- } {
+                .name followSets { |redo enlarge }_ ==put
+                i 1 add rhs len range rhs *
+                _ firstSet dom put each
+                  isNullable { lhsSet dom put each } rep
+              } :?
+            } each
+          } each
+        } redoing
 
-      { "unexpected nonterminal" die } /unexpectedNonterminal deffst
-      { "unexpected terminal" die } /unexpectedTerminal deffst
+        "" findRules map addRuleStartToItemSet _  ==initialItemSet _ itemsetId itemsets =[]
+        initialItemSet stepItemSet
+        # "=====" dump itemsets |dumpItemSet each perfstats # DEBUG
+        
+        map ==itemsetIndices
+        0 ==i
+        itemsets dom ==itemsetsDom
+        [
+          itemsetsDom { ==id id itemsets * id i _ 1 add =i -01 itemsetIndices =[] }' each
+        ] ==theItemSets
 
-      [
-        itemsets { ==itemset
-          map _ ==actions # left in array
-          itemset itemsetId ==isId
-          isId transitions .has {
-            allNonTerminals dom { ==nt
-              isId transitions * ==outgoing
-              "n" nt cat ==label
-              label outgoing .has {
-                label outgoing * itemsetIndices * ==target
-                { [ target -1302 ] }
-              } { |unexpectedNonterminal } ? * nt actions =[]
-            } each
-          } rep
-        } each
-      ] ==nonterminalActions # stateIndex -> nonterminal .name -> { ... }
+        { "unexpected nonterminal" die }' /unexpectedNonterminal deffst
+        { "unexpected terminal" die }' /unexpectedTerminal deffst
 
-      [
-        itemsets { ==itemset
-          map _ ==actions # left in array
+        [
+          itemsetsDom { ==itemsetId
+            map _ ==actions # left in array
+            itemsetId transitions .has {
+              allNonTerminals dom { ==nt
+                itemsetId transitions * ==outgoing
+                "n" nt cat ==label
+                label outgoing .has {
+                  label outgoing * itemsetIndices *
+                }" { 1 neg }" ? * nt actions =[]
+              } each
+            } rep
+          } each
+        ] ==nonterminalActions # stateIndex -> nonterminal .name -> { ... }
+
+        allTerminals dom ==allTerminalsDom
+        [
+          itemsetsDom { _ ==itemsetId itemsets * ==itemset
+            map _ ==actions # left in array
 
-          itemset itemsetId ==isId
-          isId transitions .has { isId transitions * } { map } ? * ==outgoing
+            itemsetId transitions .has { itemsetId transitions * } { map } ? * ==outgoing
+            itemset |ruleAtEnd grep ==rulesAtEnd
 
-          allTerminals dom { ==t
-            [
-              { "t" t cat outgoing .has } {
-                "t" t cat outgoing * itemsetIndices * ==target
-                { [ target -1302 ] 0 } t actions =[]
-                # 0 => lookahead consumed, quit statemachine loop
-              }
-              { itemset t canReduce } { ==rule
-                0 rule * .name ==nt
-                1 rule * len ==tokill
-                2 rule * =*reduceAction
-                { -- ==states # value dropped
-                  states reduceAction ==value
-                  tokill { 0 states * =states }' rep
-                  states len 0 gt {
-                    nt 1 states * nonterminalActions * * =*action
-                    states value action =states
-
-                    # states len 0 gt { # DEBUG
-                    #   1 states * theItemSets * dumpItemSet
-                    # } rep
-                  } rep
-                  states 1 # lookahead not consumed, repeat loop
-                } t actions =[]
-              }
-              { 1 } { |unexpectedTerminal t actions =[] }
-            ] conds
+            "" ==t allTerminalsDom { =t
+              "t" t cat outgoing .has {
+                "t" t cat outgoing * itemsetIndices * makeShiftAction t actions =[] }' {
+              rulesAtEnd t canReduce {
+                makeReduceAction t actions =[] }'
+              # else
+                { |unexpectedTerminal t actions =[]
+              }' ? * }' ? *
+            }' each
           } each
-        } each
-      ] ==terminalActions # stateIndex -> lookahead -> { ... }
-      }' τfinalization *
-
-      <
-        {
-          [ [ ] 0 0 ] ==states
-          { ==lookahead ==value
-            1 states * theItemSets * dumpItemSet # DEBUG
-            [ "received: " lookahead ] |cat fold dump # DEBUG
-
-            { states value
-              lookahead 1 states * terminalActions * * *
-              -01 =states states len and
-            } { } loop
-          }
-        } /run deffst
-      >
-    } /automaton deffst
-  scope } /lalr1 deffd
+        ] ==terminalActions # stateIndex -> lookahead -> { ... }
+
+        <
+          {
+            [ [ ] 0 0 ] ==states
+            { ==lookahead ==value
+              1 states * theItemSets * dumpItemSet # DEBUG
+              [ "received: " lookahead ] |cat fold dump # DEBUG
+
+              { states value
+                lookahead 1 states * terminalActions * * *
+                -01 =states states len and
+              } { } loop
+            }
+          } /run deffst
+        >
+
+        perfstats
+      } /automaton deffst
+    scope }
+  > -- /lalr1 deffd
 > /parser defvd
 
 # vim: syn=elymas
diff --git a/elymas/lib/sort.ey b/elymas/lib/sort.ey
index 6692cf2..60e1b9b 100644
--- a/elymas/lib/sort.ey
+++ b/elymas/lib/sort.ey
@@ -1,17 +1,17 @@
 { /cmp deff _ /a deff dom /d deff
   { ==e ==s
-    s e eq { [ s d ] } {
+    s e eq { [ s d ] }' {
       s e add 2 div ==m
       s       m mergeSort =*x 0 ==i
       m 1 add e mergeSort =*y 0 ==j
-      { i _ x -01 1 add =i } ==l
-      { j _ y -01 1 add =j } ==r
+      { i _ x -01 1 add =i }' ==l
+      { j _ y -01 1 add =j }' ==r
       [
-        { i |x len lt j |y len lt and } {
+        { i |x len lt j |y len lt and }' {
           i x a j y a cmp l r ? *
-        } loop
-        { i |x len lt } l loop
-        { j |y len lt } r loop
+        }' loop
+        { i |x len lt }' l loop
+        { j |y len lt }' r loop
       ]
     } ? *
   } /mergeSort deffst