WIP: performance improvements

1 files changed, 69 insertions, 58 deletions

diff --git a/elymas/lib/parser.ey b/elymas/lib/parser.ey
index f4bafc9..6ba0c49 100644
--- a/elymas/lib/parser.ey
+++ b/elymas/lib/parser.ey
@@ -1,14 +1,14 @@
 <
-  <
-    { sys .linux .gettimeofday -- 1000000 mul add } /t deffd
-    < { == }' > ==time =*setTime
-    < { == }' > ==count =*setCount
-    { ==l 0 l setTime 0 l setCount
-      { =*f { t ==start f t start sub time l . add l setTime count l . 1 add l setCount } }
-      quoted not { * } rep
-    }
-    { time keys { _ dump _ time -01 . txt .produce .u " μs" cat dump count -01 . txt .produce .u " calls" cat dump } each }
-  > -- /perfstats deffd "τ" defq
+  # <
+  #   { sys .linux .gettimeofday -- 1000000 mul add } /t deffd
+  #   < { == }' > ==time =*setTime
+  #   < { == }' > ==count =*setCount
+  #   { ==l 0 l setTime 0 l setCount
+  #     { =*f { t ==start f t start sub time l . add l setTime count l . 1 add l setCount } }
+  #     quoted not { * } rep
+  #   }
+  #   { 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
   { =*wasNew ==m ==k k m .has not { 1 k m =[] wasNew } rep } /enlarge deffd
@@ -75,7 +75,7 @@
       } /rule deffst
 
       { ==start
-        rules [ [ < "" ==name > [ start "" ] { } ] ] cat ==rules
+        rules [ [ < "" ==name > [ start "" ] { /never_executed die } ] ] cat ==rules
         map ==itemsets
         map ==transitions # itemsetId -> label -> itemsetId
 
@@ -98,15 +98,6 @@
         { ==rulesToExpand
           map ==expanded
 
-          0 ==debug
-          rulesToExpand len 4 gt {
-            1 3 rulesToExpand * * len 5 eq {
-              2 1 3 rulesToExpand * * * "/\\" eq {
-                1 =debug
-              } rep
-            } rep
-          } rep
-
           [
             { rulesToExpand # into the result array
               [
@@ -128,13 +119,13 @@
             [ r ] cat eId rulesByStep =[]
           } each
 
-          rulesByStep debug
+          rulesByStep
         } /nonterminalExpansions deffst
         { ==itemset
           itemset itemsetId ==fromId
           itemset { ruleAtEnd not }' grep ==steppingRules
 
-          steppingRules nonterminalExpansions ==debug ==rulesByStep # tId -> [ rule ... ]
+          steppingRules nonterminalExpansions ==rulesByStep # tId -> [ rule ... ]
 
           rulesByStep dom { ==eId
             map ==nextItemSet
@@ -143,12 +134,6 @@
               [ -01 4 dearray 1 add ] _ itemId nextItemSet =[]
             }' each
 
-            debug {
-              eId /nset eq {
-                nextItemSet dumpItemSet
-              } rep
-            } rep
-
             nextItemSet itemsetId ==toId
             toId itemsets .has not {
               nextItemSet toId itemsets =[] # add new itemset
@@ -163,8 +148,6 @@
         { ==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
@@ -181,9 +164,9 @@
                   [ states target value ] =states
                 }' ? *
 
-                states len 0 gt { # DEBUG
-                  1 states * theItemSets * dumpItemSet
-                } rep
+                # states len 0 gt { # DEBUG
+                #   1 states * theItemSets * dumpItemSet
+                # } rep
               } rep
               states 1 # lookahead not consumed, repeat loop
             } id reduceActions =[]
@@ -258,8 +241,6 @@
           itemsetsDom { ==id id itemsets * id i _ 1 add =i -01 itemsetIndices =[] }' each
         ] ==theItemSets
 
-        { "unexpected terminal" die }' /unexpectedTerminalHandler deffst
-
         [
           itemsetsDom { ==itemsetId
             map _ ==actions # left in array
@@ -284,42 +265,72 @@
             itemset |ruleAtEnd grep ==rulesAtEnd
 
             "" ==t allTerminalsDom { =t
-              "t" t cat outgoing .has {
-                "t" t cat outgoing * itemsetIndices * makeShiftAction t actions =[] }' {
-              rulesAtEnd t canReduce {
-                makeReduceAction t actions =[] }'
-              # else
-                { { unexpectedTerminalHandler }' t actions =[]
-              }' ? * }' ? *
+              [
+                "t" t cat outgoing .has { "t" t cat outgoing * itemsetIndices * makeShiftAction }' rep
+                rulesAtEnd t canReduce { makeReduceAction }' each
+              ] t actions =[]
             }' each
           } each
         ] ==terminalActions # stateIndex -> lookahead -> { ... }
 
         <
-          # expects { ==value ==states ... states continue-stateloop[0/1] }
-          { =unexpectedTerminalHandler } /unexpectedTerminal deffst
-
           {
-            [ [ ] 0 0 ] ==states
+            [
+              [ [ ] 0 0 ] # (currently empty) stack of states
+            ] ==states # all states of the GLR
+
             { ==lookahead ==value
-              1 states * theItemSets * dumpItemSet # DEBUG
-              [ "received: " lookahead ] |cat fold dump # DEBUG
-
-              { states value
-                1 states * terminalActions * ==actionMap
-                lookahead actionMap .has {
-                  lookahead actionMap * *
-                } { unexpectedTerminalHandler } ? *
-                -01 =states states len and
-              } { } loop
+              # ">>>>>>>" dump
+              # states { ==state # DEBUG
+              #   1 state * theItemSets * dumpItemSet
+              # } each
+              # "<<<<<<<" dump
+              # [ "received: " lookahead ] |cat fold dump
+
+              [ ] ==waitingStates
+              states ==executingStates
+
+              {
+                [ executingStates { ==state
+                  [
+                    1 state * terminalActions * ==actionMap
+                    lookahead actionMap .has {
+                      lookahead actionMap * { # --action
+                        state value -102 *
+                      }' each
+                    }' rep
+                  ] _ ==results len ==i
+
+                  { i }' {
+                    i 2 sub =i
+                    i 1 add results * {
+                      i results * # collected outside the loop
+                    }' {
+                      [ i results * ] waitingStates cat =waitingStates
+                    }' ? *
+                  }' loop
+                } each ] _ =executingStates len
+
+                # ">>>---" dump
+                # executingStates { ==state # DEBUG
+                #   1 state * theItemSets * dumpItemSet
+                # } each
+                # "<<<---" dump
+              }' { }" loop
+              
+              waitingStates _ =states
             }
           } /run deffst
         >
 
-        perfstats
+        # perfstats # DEBUG
       } /automaton deffst
+
+      { ==states
+        [ states { 0 -01* 2 -01* } each ] 
+      } /result deffst
     scope }
-  > -- /lalr1 deffd
+  > -- /glr deffd
 > /parser defvd
 
 # vim: syn=elymas