dparsergen.generator.glrparsercodegen source code

1 
2 //          Copyright Tim Schendekehl 2023.
3 // Distributed under the Boost Software License, Version 1.0.
4 //    (See accompanying file LICENSE_1_0.txt or copy at
5 //          https://www.boost.org/LICENSE_1_0.txt)
6 
7 module dparsergen.generator.glrparsercodegen;
8 import dparsergen.core.utils;
9 import dparsergen.generator.codewriter;
10 import dparsergen.generator.grammar;
11 import dparsergen.generator.parser;
12 import dparsergen.generator.parsercodegencommon;
13 import dparsergen.generator.production;
14 import std.algorithm;
15 import std.conv;
16 import std.range;
17 import std.typecons;
18 
19 bool needsExtraStateData(LRGraph graph, size_t stateNr, const LRGraphNode node)
20 {
21     auto grammar = graph.grammar;
22     foreach (e; node.elements)
23     {
24         if (e.isNextValid(grammar) && e.next(grammar).negLookaheads.length > 0)
25             return true;
26     }
27     return false;
28 }
29 
30 void createExtraStateData(ref CodeWriter code, LRGraph graph, size_t stateNr, const LRGraphNode node)
31 {
32     auto grammar = graph.grammar;
33     bool[Symbol] usedNegLookahead;
34     mixin(genCode("code", q{
35         static struct $(parseFunctionName(graph, stateNr, "StateData"))
36         {
37             $$foreach (e; node.elements) {
38                 $$if (e.isNextValid(grammar)) {
39                     $$foreach (n; e.next(grammar).negLookaheads) {
40                         $$if (n !in usedNegLookahead) {
41                             bool disallow$(symbolNameCode(grammar, n));
42                             $$usedNegLookahead[n] = true;
43                         $$}
44                     $$}
45                 $$}
46             $$}
47         }
48         }));
49 }
50 
51 bool isSingleReduceState(LRGraph graph, size_t stateNr)
52 {
53     auto grammar = graph.grammar;
54     const LRGraphNode node = graph.states[stateNr];
55     return node.elements.length == 1 && node.elements[0].isFinished(grammar)
56         && !node.elements[0].isStartElement;
57 }
58 
59 void createParseFunction(ref CodeWriter code, LRGraph graph, size_t stateNr, const LRGraphNode node)
60 {
61     auto grammar = graph.grammar;
62     immutable endTok = grammar.tokens.getID("$end");
63 
64     createParseStateComments(code, graph, stateNr, node);
65 
66     if (node.hasSetStackSymbols && !graph.globalOptions.directUnwrap)
67     {
68         code.writeln("// hasSetStackSymbols => skipped ", parseFunctionName(graph, stateNr));
69         code.writeln();
70         return;
71     }
72 
73     ActionTable actionTable = genActionTable(graph, node);
74 
75     void actionCode(Action bestAction)
76     {
77         assert(bestAction.type != ActionType.none);
78 
79         code.writeln("// ", bestAction.type);
80 
81         if (bestAction.type == ActionType.shift)
82         {
83             //code.writeln("writeln(\"shift token \", input.front);");
84 
85             if (!isSingleReduceState(graph, bestAction.newState))
86             {
87                 code.writeln("StackNode *nextNode = shift!true(stackNode, start, ",
88                         bestAction.newState, ", tokenContent);");
89             }
90             else
91             {
92                 code.writeln("StackNode *nextNode = shift!false(stackNode, start, ",
93                         bestAction.newState, ", tokenContent);");
94             }
95 
96             auto nextNode = graph.states[bestAction.newState];
97             if (isSingleReduceState(graph, bestAction.newState))
98             {
99                 foreach (e; nextNode.elements)
100                 {
101                     if (e.isFinished(grammar) && !e.isStartElement)
102                     {
103                         code.writeln("{").incIndent;
104                         code.writeln("// early reduce ", grammar.productionString(e.production));
105                         code.writeln(reduceFunctionName(graph, e.production),
106                                 "(nextNode, start, end, end, true);");
107                         code.decIndent.writeln("}");
108                     }
109                 }
110             }
111         }
112         else if (bestAction.type == ActionType.reduce)
113         {
114             code.writeln(reduceFunctionName(graph, bestAction.production),
115                     "(stackNode, start, end, lastTokenEnd, false);");
116         }
117         else if (bestAction.type == ActionType.delayedReduce)
118         {
119             assert(false);
120         }
121         else if (bestAction.type == ActionType.accept)
122         {
123             code.writeln("acceptedStackTops.addOnce(stackNode);");
124         }
125         else if (bestAction.type == ActionType.descent)
126         {
127             assert(false);
128         }
129         else if (bestAction.type == ActionType.conflict)
130         {
131             mixin(genCode("code", q{
132             bool anyGood = false;
133             ParseException[] exceptions;
134             $$foreach (a2; bestAction.conflictActions) {
135                 try
136                 {
137                     $$actionCode(a2);
138                     anyGood = true;
139                 }
140                 catch(ParseException e)
141                 {
142                     exceptions ~= e;
143                 }
144             $$}
145             if (!anyGood)
146             {
147                 if (exceptions.length == 1)
148                     throw exceptions[0];
149                 else
150                     throw new MultiParseException("", exceptions);
151             }
152             }));
153         }
154         else
155             assert(false);
156     }
157 
158     static struct ActionX
159     {
160         Action action;
161         Tuple!(TokenID, string)[] conditions;
162     }
163 
164     ActionX[] actions;
165     size_t[Action] actionsMap;
166 
167     foreach (t; actionTable.actions.sortedKeys)
168     {
169         auto a = actionTable.actions[t];
170         foreach (subToken; a.sortedKeys)
171         {
172             auto a2 = a[subToken];
173             auto x = tuple!(TokenID, string)(t, subToken);
174             if (a2 !in actionsMap)
175             {
176                 actionsMap[a2] = actions.length;
177                 actions ~= ActionX(a2);
178             }
179             actions[actionsMap[a2]].conditions ~= x;
180         }
181     }
182 
183     bool[Symbol] usedNegLookahead;
184     foreach (e; node.elements)
185     {
186         if (e.isNextValid(grammar))
187             foreach (n; e.next(grammar).negLookaheads)
188                 if (n !in usedNegLookahead)
189                 {
190                     usedNegLookahead[n] = true;
191                 }
192     }
193 
194     mixin(genCode("code", q{
195         private void $(parseFunctionName(graph, stateNr, "pushTokenState"))(  _
196         StackNode *stackNode, size_t tokenId, Token tokenContent, Location start, Location end)
197         {
198             $$if (node.elements.simpleLLState) {
199                 assert(false, "Not used for GLR parser");
200             $$} else if (node.type == LRGraphNodeType.backtrack) {
201                 assert(false, "Not used for GLR parser");
202             $$} else if (node.type == LRGraphNodeType.lookahead) {
203                 assert(false, "Not used for GLR parser");
204             $$} else {
205                 $$string ifPrefix="";
206                 $$foreach (l; usedNegLookahead.sortedKeys) {
207                     $$if (l.isToken) {
208                         if (tokenId == getTokenID!$(grammar.tokens[l.toTokenID].tokenDCode))
209                             stackNode.$(parseFunctionName(graph, stateNr, "stateData")).disallow$(symbolNameCode(grammar, l)) = true;
210                     $$}
211                 $$}
212                 $$foreach (a; actions) {
213                     $(ifPrefix)if (  _
214                     $$CommaGen orCode = CommaGen(" || ");
215                     $$foreach (c; a.conditions) {
216                         $$if (c[1] == "") {
217                             $(orCode())tokenId == getTokenID!$(grammar.tokens[c[0]].tokenDCode)  _
218                         $$} else {
219                             $(orCode())(tokenId == getTokenID!$(grammar.tokens[c[0]].tokenDCode) && tokenContent == $(c[1]))  _
220                         $$}
221                     $$}
222                     )
223                     {
224                         $$actionCode(a.action);
225                     }
226                     $$ifPrefix = "else ";
227                 $$}
228                 $$if (actionTable.defaultReduceAction.type != ActionType.none) {
229                     $(ifPrefix == "else " ? "else" : ifPrefix)
230                     {
231                         $$actionCode(actionTable.defaultReduceAction);
232                     }
233                 $$} else if (endTok in actionTable.actions) {
234                     $(ifPrefix == "else " ? "else" : ifPrefix)
235                     {
236                         $$actionCode(actionTable.actions[endTok][""]);
237                     }
238                 $$} else {
239                     $(ifPrefix == "else " ? "else" : ifPrefix)
240                     {
241                         $$if (endTok in actionTable.actions) {
242                             throw new SingleParseException!Location(text("unexpected Token \"", tokenContent, "\"  \"", getTokenName(tokenId), "\""),
243                                 start, end);
244                         $$} else {
245                             if (tokenId == getTokenID!$(grammar.tokens[endTok].tokenDCode))
246                                 throw new SingleParseException!Location("EOF",
247                                     start, end);
248                             else
249                                 throw new SingleParseException!Location(text("unexpected Token \"", tokenContent, "\"  \"", getTokenName(tokenId), "\""),
250                                     start, end);
251                         $$}
252                         assert(0);
253                     }
254                 $$}
255             $$}
256         }
257         }));
258 
259     if (!needsJumps(graph, stateNr, node, actionTable))
260         return;
261 
262     mixin(genCode("code", q{
263         private void $(parseFunctionName(graph, stateNr, "pushTokenState"))(  _
264         StackNode *stackNode, PendingReduce pendingReduce, Location tokenStart, Location tokenEnd, bool alreadyShifted$(grammar.tags.vals.length ? ", Tag tags" : ""))
265         {
266             size_t newState;
267             bool setStackTops = true;
268             switch (pendingReduce.nonterminalID)
269             {
270                 $$foreach (nonterminalID; actionTable.jumps.sortedKeys) {
271                     $$auto jumps2 = actionTable.jumps[nonterminalID];
272                     case $(grammar.nonterminalIDCode(nonterminalID)):
273                         $$if (nonterminalID in usedNegLookahead) {
274                             stackNode.$(parseFunctionName(graph, stateNr, "stateData")).disallow$(symbolNameCode(grammar, nonterminalID)) = true;
275                         $$}
276                         $$CommaGen elseCode = CommaGen("else ");
277                         $$bool hasDisallowCheck;
278                         $$foreach (checkDisallowedSymbols; jumps2.sortedKeys) {
279                             $$auto newState = jumps2[checkDisallowedSymbols];
280                             $$if (checkDisallowedSymbols.length == 0) {
281                                 $$if (newState == size_t.max) {
282                                     $$assert(false);
283                                 $$} else {
284                                     $$auto nextNode = graph.states[newState];
285                                     $$if (isSingleReduceState(graph, newState)) {
286                                         newState = $(newState);
287                                         setStackTops = !alreadyShifted;
288                                     $$} else {
289                                         newState = $(newState);
290                                     $$}
291                                     $$if (isSingleReduceState(graph, newState)) {
292                                         setStackTops = false;
293                                     $$}
294                                 $$}
295                             $$} else {
296                                 $$CommaGen and = CommaGen(" && ");
297                                 $$hasDisallowCheck = true;
298                                 $(elseCode())if (  _
299                                 $$foreach (x; checkDisallowedSymbols) {
300                                     $(and())stackNode.$(parseFunctionName(graph, stateNr, "stateData")).disallow$(symbolNameCode(grammar, x[0])) == $(x[1])  _
301                                 $$}
302                                 )
303                                 {
304                                     $$if (newState == size_t.max) {
305                                         $$assert(false);
306                                     $$} else {
307                                         $$auto nextNode = graph.states[newState];
308                                         $$if (isSingleReduceState(graph, newState)) {
309                                             newState = $(newState);
310                                             setStackTops = !alreadyShifted;
311                                         $$} else {
312                                             newState = $(newState);
313                                         $$}
314                                         $$if (isSingleReduceState(graph, newState)) {
315                                             setStackTops = false;
316                                         $$}
317                                     $$}
318                                 }
319                             $$}
320                         $$}
321                         $$if (hasDisallowCheck) {
322                             else assert(false);
323                         $$}
324                     break;
325                 $$}
326                 default:
327                     assert(0, text("no jump ", pendingReduce.nonterminalID));
328             }
329             StackNode* stackNodeNew = shift(stackNode, newState, pendingReduce, alreadyShifted, setStackTops$(grammar.tags.vals.length ? ", tags" : ""));
330         }
331         }));
332 }
333 
334 void createReduceFunction(ref CodeWriter code, LRGraph graph, const Production* production)
335 {
336     auto grammar = graph.grammar;
337     const RewriteRule[] rewriteRules = grammar.getRewriteRules(production);
338     assert(rewriteRules.length > 0);
339 
340     string[] rewriteParameters;
341     foreach (k; 0 .. production.symbols.length)
342     {
343         if (!production.symbols[k].dropNode)
344             rewriteParameters ~= text("stack", k);
345         else
346             rewriteParameters ~= "undefinedIdentifier/*error*/";
347     }
348 
349     size_t[] prevStateSet(const size_t[] states)
350     {
351         size_t[] r;
352         foreach (s; states)
353             foreach (edge; graph.states[s].reverseEdges)
354                 r.addOnce(edge.next);
355         r.sort();
356         return r;
357     }
358 
359     mixin(genCode("code", q{
360         private static StackEdgeData* $(reduceFunctionName(graph, production, "reduceImpl"))(ref PushParser this_,   _
361         StackEdge*[] parameterEdges, Location lastTokenEnd)
362         {
363             assert(parameterEdges.length == $(production.symbols.length));
364             StackEdgeData*[] parameterEdgesData;
365             parameterEdgesData.length = $(production.symbols.length);
366             $$foreach (k; 0 .. production.symbols.length) {
367                 parameterEdgesData[$(k)] = parameterEdges[$(k)].data;
368             $$}
369             StackEdgeData* r = new StackEdgeData(false);
370             $$foreach (k; 1 .. production.symbols.length + 1) {
371                 StackEdgeData *stackEdge$(k) = parameterEdges[$ - $(k)].data; // $(grammar.symbolInstanceToString(production.symbols[$ - k]))
372             $$}
373             $$foreach (k; 1 .. production.symbols.length + 2) {
374                 $$if (k <= production.symbols.length) {
375                     $$if (production.symbols[$ - k].isToken) {
376                         assert(stackEdge$(k).isToken);
377                     $$} else if (graph.globalOptions.directUnwrap) {
378                         assert(!stackEdge$(k).isToken && stackEdge$(k).nonterminal.nonterminalID.among(  _
379                         $$foreach (n; grammar.directUnwrapClosure(production.symbols[$ - k])) {
380                             $(grammar.nonterminalIDCode(n.nonterminalID)),   _
381                         $$}
382                         ), text(stackEdge$(k).isToken, "  ", stackEdge$(k).nonterminal.nonterminalID, "  ", cast(void*) stackEdge$(k)));
383                     $$} else {
384                         assert(!stackEdge$(k).isToken && stackEdge$(k).nonterminal.nonterminalID == $(grammar.nonterminalIDCode(production.symbols[$ - k].toNonterminalID)));
385                     $$}
386                     assert(stackEdge$(k).start.bytePos != size_t.max);
387                 $$}
388             $$}
389             $$if (grammar.isSimpleProduction(*production) && !grammar.nonterminals[production.nonterminalID].annotations.contains!"array"()) {
390                 $$size_t nrNotDropped=size_t.max;
391                 $$foreach (k, s; production.symbols) {
392                     $$if (!s.dropNode) {
393                         $$nrNotDropped = k;
394                     $$}
395                 $$}
396                 NonterminalType!($(grammar.nonterminalIDCode(nonterminalOutForProduction(production)))) pt;
397                 $$if (nrNotDropped != size_t.max) {
398                     $$if (production.symbols[nrNotDropped].isToken) {
399                         pt = stackEdge$(production.symbols.length - nrNotDropped).token;
400                     $$} else if (graph.globalOptions.directUnwrap) {
401                         pt = stackEdge$(production.symbols.length - nrNotDropped).nonterminal.get!(  _
402                         $$foreach (n; grammar.directUnwrapClosure(production.symbols[nrNotDropped])) {
403                             $(grammar.nonterminalIDCode(n.nonterminalID)),   _
404                         $$}
405                         );
406                     $$} else {
407                         pt = stackEdge$(production.symbols.length - nrNotDropped).nonterminal.get!$(grammar.nonterminalIDCode(production.symbols[nrNotDropped].toNonterminalID));
408                     $$}
409                     Location newTreeStart = stackEdge$(production.symbols.length - nrNotDropped).start;
410                 $$} else {
411                     pt = typeof(pt).init;
412                     Location newTreeStart = Location.invalid;
413                 $$}
414 
415                 r.nonterminal = Creator.NonterminalUnionAny.create($(grammar.nonterminalIDCode(nonterminalOutForProduction(production))), pt);
416                 r.start = newTreeStart;
417             $$} else {
418                 $$if (production.symbols.length > 0) {
419                     Location newTreeStart = stackEdge$(production.symbols.length).start;
420                     $$for (size_t i=production.symbols.length - 1; i > 0; i--) {
421                         if (!newTreeStart.isValid)
422                             newTreeStart = stackEdge$(i).start;
423                     $$}
424                 $$} else {
425                     Location newTreeStart = Location.invalid;
426                 $$}
427                 $$string stackStartExpr = "newTreeStart";
428                 Location reduceEnd = lastTokenEnd;
429                 if (reduceEnd < newTreeStart)
430                     reduceEnd = newTreeStart;
431                 $$foreach (k; 0 .. production.symbols.length) {
432                     $$if (production.symbols[k].isToken) {
433                         ParseStackElem!(Location, Token) stack$(k)
434                             = ParseStackElem!(Location, Token)  _
435                             (stackEdge$(production.symbols.length - k).start, stackEdge$(production.symbols.length - k).token);
436                     $$} else if (graph.globalOptions.directUnwrap) {
437                         ParseStackElem!(Location, NonterminalType!$(grammar.nonterminalIDCode(production.symbols[k].toNonterminalID))) stack$(k)
438                             = ParseStackElem!(Location, NonterminalType!$(grammar.nonterminalIDCode(production.symbols[k].toNonterminalID)))  _
439                             (stackEdge$(production.symbols.length - k).start, stackEdge$(production.symbols.length - k).nonterminal.get!(  _
440                             $$foreach (n; grammar.directUnwrapClosure(production.symbols[k])) {
441                                 $(grammar.nonterminalIDCode(n.nonterminalID)),   _
442                             $$}
443                             ));
444                     $$} else {
445                         ParseStackElem!(Location, NonterminalType!$(grammar.nonterminalIDCode(production.symbols[k].toNonterminalID))) stack$(k)
446                             = ParseStackElem!(Location, NonterminalType!$(grammar.nonterminalIDCode(production.symbols[k].toNonterminalID)))  _
447                             (stackEdge$(production.symbols.length - k).start, stackEdge$(production.symbols.length - k).nonterminal.get!$(grammar.nonterminalIDCode(production.symbols[k].toNonterminalID)));
448                     $$}
449                 $$}
450 
451                 NonterminalType!($(grammar.nonterminalIDCode(nonterminalOutForProduction(rewriteRules[$ - 1].applyProduction)))) pt  _
452                 = this_.creator.createParseTree!($(rewriteRules[$ - 1].applyProduction.productionID + grammar.startProductionID))  _
453                 (newTreeStart, reduceEnd  _
454                 $$size_t iParam;
455                 $$foreach (k; 0 .. rewriteRules[$ - 1].applyProduction.symbols.length) {
456                     $$if (!rewriteRules[$ - 1].applyProduction.symbols[k].dropNode) {
457                         $$if (rewriteRules[$ - 1].parameters[iParam] == size_t.max) {
458                             , ParseStackElem!(Location, NonterminalType!$(rewriteRules[$ - 1].applyProduction.symbols[k].id + grammar.startNonterminalID))(Location.invalid, NonterminalType!$(rewriteRules[$ - 1].applyProduction.symbols[k].id + grammar.startNonterminalID).init/*null*/)  _
459                             $$iParam++;
460                         $$} else {
461                             , $(rewriteParameters[rewriteRules[$ - 1].parameters[iParam]])  _
462                             $$stackStartExpr = text("Location.init/*stackEdge", production.symbols.length - k, ".end*/");
463                             $$iParam++;
464                         $$}
465                     $$} else {
466                     $$}
467                 $$}
468                 );
469 
470                 r.nonterminal = Creator.NonterminalUnionAny.create($(grammar.nonterminalIDCode(nonterminalOutForProduction(rewriteRules[$ - 1].applyProduction))), pt);
471                 r.start = newTreeStart;
472             $$}
473             return r;
474         }
475         $$if (tuple!(size_t, size_t)(production.productionID, production.symbols.length) in graph.statesWithProduction) {
476             private   _
477             void   _
478             $(reduceFunctionName(graph, production))(  _
479             StackNode *stackNode, Location tokenStart, Location tokenEnd, Location lastTokenEnd, bool alreadyShifted  _
480             )
481             {
482                 ParseException[] exceptions;
483                 bool anyGood;
484                 // $(grammar.productionString(production))   $(production.tags)
485                 $$string currentStackNode = "stackNode";
486                 $$const(size_t)[] possibleStates;
487                 $$possibleStates = graph.statesWithProduction[tuple!(size_t, size_t)(production.productionID, production.symbols.length)];
488                 $$foreach (k; 1 .. production.symbols.length + 1) {
489                     assert($(currentStackNode).previous.length > 0);
490                     assert($(currentStackNode).state.among(  _
491                     $$foreach (prevState; possibleStates) {
492                         $(prevState),   _
493                     $$}
494                     ), text("state = ", $(currentStackNode).state));
495                     foreach (StackEdge* stackEdge$(k); $(currentStackNode).previous) // $(grammar.symbolInstanceToString(production.symbols[$ - k]))
496                     {
497                     $$code.incIndent;
498                     $$foreach (t; production.symbols[$ - k].tags) {
499                     $$}
500                     $$currentStackNode = text("stackEdge", k, ".node");
501                     $$possibleStates = prevStateSet(possibleStates);
502                 $$}
503                 $$if (grammar.tags.vals.length) {
504                     Tag tags = $(reduceTagsCode!((k) => text("stackEdge", k, ".tags"))(grammar, production));
505                     $$if (checkTagsCode!((k) => text("stackEdge", k, ".tags"))(code, grammar, production)) {
506                             continue;
507                     $$}
508                 $$}
509                 try
510                 {
511                     StackEdge*[] parameterEdges = tmpData.stackEdgePointerAllocator.allocate(null, $(production.symbols.length));
512                     $$foreach (k; iota(production.symbols.length, 0, -1)) {
513                         parameterEdges[$(production.symbols.length - k)] = stackEdge$(k);
514                     $$}
515                     pushToken(  _
516                     $$if (production.symbols.length == 0) {
517                         stackNode,   _
518                     $$} else {
519                         stackEdge$(production.symbols.length).node,   _
520                     $$}
521                     PendingReduce($(grammar.nonterminalIDCode(nonterminalOutForProduction(rewriteRules[$ - 1].applyProduction))),   _
522                     parameterEdges, $(production.productionID), &$(reduceFunctionName(graph, production, "reduceImpl"))), tokenStart, tokenEnd, alreadyShifted$(grammar.tags.vals.length ? ", tags" : ""));
523                     anyGood = true;
524                 }
525                 catch(ParseException e)
526                 {
527                     exceptions ~= e;
528                 }
529                 $$foreach (k; 1 .. production.symbols.length + 1) {
530                     $$code.decIndent;
531                     }
532                 $$}
533                 if (!anyGood)
534                 {
535                     if (exceptions.length == 1)
536                         throw exceptions[0];
537                     else if (exceptions.length == 0)
538                         throw new SingleParseException!Location("no reduce", tokenStart, tokenEnd);
539                     else
540                         throw new MultiParseException("", exceptions);
541                 }
542             }
543         $$}
544         }));
545 }
546 
547 void createStartParseFunction(ref CodeWriter code, LRGraph graph, size_t stateNr,
548         const LRGraphNode node)
549 {
550     auto grammar = graph.grammar;
551     immutable endTok = grammar.tokens.getID("$end");
552 
553     assert(node.stackSymbols.length == 0);
554 
555     mixin(genCode("code", q{
556         /*private*/   _
557         void   _
558         $(parseFunctionName(graph, stateNr, "startParse"))(  _
559         )
560         {
561             lastTokenEnd = Location.init;
562             stackTops = [new StackNode($(stateNr))];
563             acceptedStackTops = [];
564             clearTmpData();
565             pushToken(getTokenID!"$flushreduces", Token.init, lastTokenEnd, lastTokenEnd);
566         }
567         }));
568 }
569 
570 void createWrapperParseFunction(ref CodeWriter code, LRGraph graph, size_t stateNr,
571         const LRGraphNode node)
572 {
573     auto grammar = graph.grammar;
574 
575     assert(node.stackSymbols.length == 0);
576 
577     mixin(genCode("code", q{
578         /*private*/   _
579         ParseStackElem!(Location, NonterminalType!($(node.elements[0].production.symbols[0].id + grammar.startNonterminalID)))[]   _
580         $(parseFunctionName(graph, stateNr, "multiParse"))(  _
581         )
582         {
583             scope(failure)
584             {
585                 stackTops = [];
586                 acceptedStackTops = [];
587             }
588 
589             alias ThisParseResult = typeof(return);
590             pushParser.$(parseFunctionName(graph, stateNr, "startParse"))();
591             while (!lexer.empty)
592             {
593                 pushParser.pushToken(translateTokenIdFromLexer!Lexer(lexer.front.symbol), lexer.front.content, lexer.front.currentLocation, lexer.front.currentTokenEnd);
594                 if (acceptedStackTops.length)
595                 {
596                     if (stackTops.length == 0)
597                         break;
598                     else
599                         acceptedStackTops = [];
600                 }
601                 lexer.popFront();
602             }
603             if (acceptedStackTops.length == 0)
604             {
605                 pushParser.pushEnd();
606             }
607             assert(stackTops.length == 0);
608             ParseStackElem!(Location, NonterminalType!($(node.elements[0].production.symbols[0].id + grammar.startNonterminalID)))[] r;
609             assert(acceptedStackTops.length >= 1);
610             foreach (t; acceptedStackTops)
611             {
612                 foreach (prev; t.previous)
613                 {
614                     assert(prev.node.previous.length == 0);
615                     NonterminalType!($(node.elements[0].production.symbols[0].id + grammar.startNonterminalID)) pt;
616                     switch (prev.data.nonterminal.nonterminalID)
617                     {
618                         $$foreach (n; grammar.directUnwrapClosure(node.elements[0].production.symbols[0].toNonterminalID, [], [])) {
619                             case $(grammar.nonterminalIDCode(n.nonterminalID)):
620                                 pt = prev.data.nonterminal.get!($(grammar.nonterminalIDCode(n.nonterminalID)));
621                                 break;
622                         $$}
623                         default:
624                             assert(false);
625                     }
626                     r ~= ParseStackElem!(Location, NonterminalType!($(grammar.nonterminalIDCode(node.elements[0].production.symbols[0].toNonterminalID))))(prev.data.start, pt);
627                 }
628             }
629             stackTops = [];
630             acceptedStackTops = [];
631             return r;
632         }
633 
634         /*private*/   _
635         ParseStackElem!(Location, NonterminalType!($(node.elements[0].production.symbols[0].id + grammar.startNonterminalID)))   _
636         $(parseFunctionName(graph, stateNr))(  _
637         )
638         do
639         {
640             auto r = $(parseFunctionName(graph, stateNr, "multiParse"))();
641 
642             if (r.length == 0)
643             {
644                 return ParseStackElem!(Location, NonterminalType!($(grammar.nonterminalIDCode(node.elements[0].production.symbols[0].toNonterminalID)))).init;
645             }
646 
647             static if (pushParser.canMerge!($(grammar.nonterminalIDCode(node.elements[0].production.symbols[0].toNonterminalID))))
648             if (r.length != 1)
649             {
650                 NonterminalType!($(grammar.nonterminalIDCode(node.elements[0].production.symbols[0].toNonterminalID))) pt = creator.mergeParseTrees!($(grammar.nonterminalIDCode(node.elements[0].production.symbols[0].toNonterminalID)))(Location.init, lastTokenEnd, r);
651                 return ParseStackElem!(Location, NonterminalType!($(grammar.nonterminalIDCode(node.elements[0].production.symbols[0].toNonterminalID))))(Location.init, pt);
652             }
653 
654             assert(r.length == 1, "Root node $(grammar.getSymbolName(node.elements[0].production.symbols[0])) is not mergeable.");
655             return r[0];
656         }
657         }));
658 }
659 
660 void createShiftFunctions(ref CodeWriter code, LRGraph graph)
661 {
662     EBNFGrammar grammar = graph.grammar;
663 
664     mixin(genCode("code", q{
665         StackNode *shift(bool onStack)(StackNode *stackNode, Location start, size_t state, Token token)
666         {
667             StackNode* n = null;
668             n = tmpData.stackNodeByState[state];
669             if (n is null)
670             {
671                 n = new StackNode(state);
672                 tmpData.stackNodeByState[state] = n;
673                 static if (onStack)
674                     stackTops ~= n;
675             }
676             foreach (ref edge; n.previous)
677             {
678                 if (edge.node is stackNode)
679                 {
680                     assert(edge.data.isToken);
681                     assert(edge.data.token == token);
682                     return n;
683                 }
684             }
685             StackEdgeData* data = new StackEdgeData(true, start);
686             data.token = token;
687             n.previous ~= new StackEdge(stackNode, data);
688             return n;
689         }
690 
691         StackNode* shift(StackNode *stackNode, size_t state, PendingReduce pendingReduce, bool alreadyShifted, bool setStackTops$(grammar.tags.vals.length?", Tag tags":""))
692         {
693             assert(pendingReduce.next is null);
694 
695             bool allowEdgeReduce = true;
696 
697             switch (pendingReduce.nonterminalID)
698             {
699                 static foreach (nonterminalID; startNonterminalID .. endNonterminalID)
700                     static if (!canMerge!nonterminalID)
701                     {
702                         case nonterminalID:
703                     }
704                 allowEdgeReduce = false;
705                 break;
706                 default:
707             }
708 
709             size_t stateHash = (state + stackNode.state * 31) % tmpData.pendingReduceIds.length;
710 
711             size_t count;
712             for (size_t k = tmpData.pendingReduceIds[stateHash]; k != size_t.max; k = tmpData.pendingReduces.data[k].nextPendingReduce2)
713             {
714                 auto pendingReduce2 = &tmpData.pendingReduces.data[k];
715                 count++;
716                 if (pendingReduce2.stackNode.state == state && pendingReduce2.stackEdge.node is stackNode && pendingReduce2.alreadyShifted == alreadyShifted)
717                 {
718                     for (PendingReduce *pendingReduce2x = pendingReduce2.pendingReduces; pendingReduce2x !is null; pendingReduce2x = pendingReduce2x.next)
719                     {
720                         if (pendingReduce2x.nonterminalID == pendingReduce.nonterminalID
721                             && pendingReduce2x.productionID is pendingReduce.productionID
722                             && pendingReduce2x.parameterEdges.length == pendingReduce.parameterEdges.length)
723                         {
724                             bool eq = true;
725                             foreach (i, p; pendingReduce2x.parameterEdges)
726                                 if (p !is pendingReduce.parameterEdges[i])
727                                     eq = false;
728                             if (eq)
729                             {
730                                 return pendingReduce2.stackNode;
731                             }
732                         }
733                     }
734                 }
735             }
736 
737             PendingReduce *pendingReducePtr = tmpData.pendingReduceAllocator.allocate(pendingReduce, 1).ptr;
738 
739             if (allowEdgeReduce)
740             {
741                 for (size_t k = tmpData.pendingReduceIds[stateHash]; k != size_t.max; k = tmpData.pendingReduces.data[k].nextPendingReduce2)
742                 {
743                     auto pendingReduce2 = &tmpData.pendingReduces.data[k];
744                     if (pendingReduce2.stackNode.state == state
745                         $$if (grammar.tags.vals.length) {
746                             && pendingReduce2.stackEdge.tags == tags
747                         $$}
748                         && pendingReduce2.stackEdge.node is stackNode
749                         && pendingReduce2.alreadyShifted == alreadyShifted)
750                     {
751                         pendingReducePtr.next = pendingReduce2.pendingReduces;
752                         pendingReduce2.pendingReduces = pendingReducePtr;
753                         hasAddedPendingReduce = true;
754                         return pendingReduce2.stackNode;
755                     }
756                 }
757             }
758 
759             if (tmpData.stackNodeByState[state + (!alreadyShifted) * $(graph.states.length)] !is null)
760             {
761                 StackNode* n = tmpData.stackNodeByState[state + (!alreadyShifted) * $(graph.states.length)];
762                 n.previous ~= new StackEdge(stackNode);
763                 $$if (grammar.tags.vals.length) {
764                     n.previous[$ - 1].tags = tags;
765                 $$}
766                 tmpData.pendingReduces.put(PendingReduce2(n, n.previous[$ - 1], alreadyShifted, pendingReducePtr, tmpData.pendingReduceIds[stateHash]));
767                 tmpData.pendingReduceIds[stateHash] = tmpData.pendingReduces.data.length - 1;
768                 hasAddedPendingReduce = true;
769                 return n;
770             }
771 
772             StackNode* n = new StackNode(state);
773             n.previous ~= new StackEdge(stackNode, null);
774             $$if (grammar.tags.vals.length) {
775                 n.previous[$ - 1].tags = tags;
776             $$}
777             tmpData.stackNodeByState[state + (!alreadyShifted) * $(graph.states.length)] = n;
778 
779             hasAddedPendingReduce = true;
780             tmpData.pendingReduces.put(PendingReduce2(n, n.previous[$ - 1], alreadyShifted, pendingReducePtr, tmpData.pendingReduceIds[stateHash]));
781             tmpData.pendingReduceIds[stateHash] = tmpData.pendingReduces.data.length - 1;
782 
783             if (alreadyShifted && setStackTops)
784                 stackTops ~= n;
785 
786             return n;
787         }
788     }));
789 }
790 
791 void createParseFunctions(ref CodeWriter code, LRGraph graph)
792 {
793     EBNFGrammar grammar = graph.grammar;
794 
795     mixin(genCode("code", q{
796         private void pushToken(StackNode *stackNode, size_t tokenId, Token tokenContent, Location start, Location end)
797         {
798             switch (stackNode.state)
799             {
800                 $$foreach (i, n; graph.states) {
801                     $$if (!n.hasSetStackSymbols || graph.globalOptions.directUnwrap) {
802                         case $(i): $(parseFunctionName(graph, i, "pushTokenState"))  _
803                         (stackNode, tokenId, tokenContent, start, end); break;
804                     $$}
805                 $$}
806                 default: assert(false, text("state=", stackNode.state));
807             }
808         }
809         void pushToken(size_t tokenId, Token tokenContent, Location start, Location end)
810         in
811         {
812             assert(start.isValid);
813             assert(end.isValid);
814             assert(lastTokenEnd.isValid);
815         }
816         do
817         {
818             if (stackTops.length == 0)
819             {
820                 if (acceptedStackTops.length == 0)
821                     throw new SingleParseException!Location("no more stackTops",
822                                 start, end);
823                 else
824                     throw new SingleParseException!Location("no more stackTops (but acceptedStackTops)",
825                                 start, end);
826             }
827             StackNode*[] savedStackTops = stackTops;
828             assert(savedStackTops);
829             stackTops = [];
830             acceptedStackTops = [];
831             ParseException[] exceptions;
832             assert(tmpData.pendingReduces.data.length == 0);
833 
834             assert(!tmpData.inUse);
835             tmpData.inUse = true;
836 
837             scope(exit)
838             {
839                 clearTmpData();
840                 tmpData.inUse = false;
841             }
842 
843             if (tokenId == getTokenID!"$flushreduces")
844             {
845                 foreach (stackNode; savedStackTops)
846                 {
847                     switch (stackNode.state)
848                     {
849                         $$foreach (i, n; graph.states) {
850                             $$if (!isSingleReduceState(graph, i)) {
851                                 case $(i): stackTops ~= stackNode; break;
852                             $$}
853                         $$}
854                         default: break;
855                     }
856                 }
857                 foreach (stackNode; savedStackTops)
858                 {
859                     switch (stackNode.state)
860                     {
861                         $$foreach (i, n; graph.states) {
862                             $$if (isSingleReduceState(graph, i)) {
863                                 case $(i):
864                                     $$foreach (e; n.elements) {
865                                         $$if (e.isFinished(grammar) && !e.isStartElement) {
866                                             $$if (e.production.symbols.length && e.production.symbols[$ - 1].isToken) {
867                                                 // Nothing to do for token
868                                             $$} else {
869                                                 $(reduceFunctionName(graph, e.production))(stackNode, start, end, end, true);
870                                             $$}
871                                         $$}
872                                     $$}
873                                     break;
874                             $$}
875                         $$}
876                         default: break;
877                     }
878                 }
879             }
880             else
881             {
882                 foreach (stackNode; savedStackTops)
883                 {
884                     try
885                     {
886                         pushToken(stackNode, tokenId, tokenContent, start, end);
887                     }
888                     catch(ParseException e)
889                     {
890                         exceptions ~= e;
891                     }
892                 }
893             }
894 
895             do
896             {
897                 hasAddedPendingReduce = false;
898                 for (size_t i=0; i < tmpData.pendingReduces.data.length; i++)
899                 {
900                     if (tmpData.pendingReduces.data[i].alreadyShifted)
901                     {
902                         try
903                         {
904                             switch (tmpData.pendingReduces.data[i].stackNode.state)
905                             {
906                                 $$foreach (i, n; graph.states) {
907                                     $$if (isSingleReduceState(graph, i)) {
908                                         case $(i):
909                                             $$foreach (e; n.elements) {
910                                                 $$if (e.isFinished(grammar) && !e.isStartElement) {
911                                                     $$if (e.production.symbols.length && e.production.symbols[$ - 1].isToken) {
912                                                         // Nothing to do for token
913                                                     $$} else {
914                                                         $(reduceFunctionName(graph, e.production))(tmpData.pendingReduces.data[i].stackNode, start, end, end, true);
915                                                     $$}
916                                                 $$}
917                                             $$}
918                                             break;
919                                     $$}
920                                 $$}
921                                 default: break;
922                             }
923                         }
924                         catch(ParseException e)
925                         {
926                             exceptions ~= e;
927                         }
928 
929                         continue;
930                     }
931 
932                     try
933                     {
934                         pushToken(tmpData.pendingReduces.data[i].stackNode, tokenId, tokenContent, start, end);
935                     }
936                     catch(ParseException e)
937                     {
938                         exceptions ~= e;
939                     }
940                 }
941             } while (hasAddedPendingReduce);
942 
943             foreach (ref pendingReduce; tmpData.pendingReduces.data)
944             {
945                 onPendingReduce(pendingReduce, end);
946             }
947 
948             lastTokenEnd = end;
949             if (stackTops.length == 0 && acceptedStackTops.length == 0)
950             {
951                 if (exceptions.length > 0)
952                     if (exceptions.length == 1)
953                         throw exceptions[0];
954                     else
955                         throw new MultiParseException("", exceptions);
956                 else
957                     throw new SingleParseException!Location(text("no stackTops ", tmpData.pendingReduces.data.length),
958                                 start, end);
959             }
960         }
961     }));
962 
963     mixin(genCode("code", q{
964         void onPendingReduce(ref PendingReduce2 pendingReduce, Location end)
965         {
966             assert(pendingReduce.stackEdge.data is null || !pendingReduce.stackEdge.data.isToken);
967             if (pendingReduce.stackEdge.reduceDone)
968                 return;
969             pendingReduce.stackEdge.reduceDone = true;
970             for (PendingReduce *pendingReducex = pendingReduce.pendingReduces; pendingReducex !is null; pendingReducex = pendingReducex.next)
971                 foreach (edge; pendingReducex.parameterEdges)
972                     foreach (ref pendingReduce2x; tmpData.pendingReduces.data)
973                         if (pendingReduce2x.stackEdge is edge)
974                             onPendingReduce(pendingReduce2x, end);
975             Location reduceEnd = pendingReduce.alreadyShifted ? end : lastTokenEnd;
976             size_t num;
977             for (PendingReduce *pendingReducePtr = pendingReduce.pendingReduces; pendingReducePtr !is null; pendingReducePtr = pendingReducePtr.next)
978                 num++;
979             if (num == 1)
980             {
981                 pendingReduce.stackEdge.data = pendingReduce.pendingReduces[0].dg(this, pendingReduce.pendingReduces.parameterEdges, reduceEnd);
982                 assert(pendingReduce.stackEdge.data.nonterminal.nonterminalID == pendingReduce.pendingReduces.nonterminalID);
983             }
984             else
985             {
986                 static Appender!(PendingReduce*[]) appPendingReduce;
987                 scope(exit)
988                     appPendingReduce.clear;
989                 for (PendingReduce *pendingReducePtr = pendingReduce.pendingReduces; pendingReducePtr !is null; pendingReducePtr = pendingReducePtr.next)
990                     appPendingReduce.put(pendingReducePtr);
991                 PendingReduce*[] pendingReducesHere = appPendingReduce.data;
992                 foreach (i; 0 .. pendingReducesHere.length/2)
993                 {
994                     auto tmp = pendingReducesHere[i];
995                     pendingReducesHere[i] = pendingReducesHere[$ - 1-i];
996                     pendingReducesHere[$ - 1-i] = tmp;
997                 }
998                 pendingReducesHere.sort!((a, b) => a.productionID < b.productionID);
999 
1000                 Creator.NonterminalUnionAny[] nonterminals;
1001                 Location[] nonterminalStarts;
1002                 nonterminals.length = pendingReducesHere.length;
1003                 nonterminalStarts.length = pendingReducesHere.length;
1004                 foreach (i; 0 .. pendingReducesHere.length)
1005                 {
1006                     StackEdgeData* data = pendingReducesHere[i].dg(this, pendingReducesHere[i].parameterEdges, reduceEnd);
1007                     nonterminals[i] = data.nonterminal;
1008                     nonterminalStarts[i] = data.start;
1009                     assert(nonterminals[i].nonterminalID == pendingReducesHere[i].nonterminalID);
1010                 }
1011                 Location nonterminalStart = nonterminalStarts[0];
1012                 foreach (i; 1 .. pendingReducesHere.length)
1013                     if (nonterminalStarts[i] < nonterminalStart)
1014                         nonterminalStart = nonterminalStarts[i];
1015 
1016                 $$if (graph.globalOptions.directUnwrap) {
1017                     switch (pendingReduce.stackNode.state)
1018                     {
1019                         $$foreach (i, n; graph.states) {
1020                             $$if (n.stackSize() >= 0) {
1021                                 $$NonterminalID[] possible = n.directUnwrapNonterminalsOnStack(graph.grammar, 1);
1022                                 $$if (possible.length) {
1023                                     static if (canMerge!($(grammar.nonterminalIDCode(possible[0]))))
1024                                     {
1025                                         case $(i):
1026                                         {
1027                                             onPendingReduce$(i)(pendingReduce, end, nonterminals, nonterminalStarts, nonterminalStart);
1028                                         }
1029                                         break;
1030                                     }
1031                                 $$}
1032                             $$}
1033                         $$}
1034                         default: assert(false);
1035                     }
1036 
1037                 $$} else {
1038                     switchlabel: switch (pendingReducesHere[0].nonterminalID)
1039                     {
1040                         static foreach (nonterminalID; startNonterminalID .. endNonterminalID)
1041                         {
1042                             static if (canMerge!nonterminalID)
1043                             {
1044                                 case nonterminalID:
1045                                 {
1046                                     ParseStackElem!(Location, NonterminalType!nonterminalID)[] pts;
1047                                     pts.length = nonterminals.length;
1048                                     foreach (i; 0 .. nonterminals.length)
1049                                         $$if (graph.globalOptions.directUnwrap) {
1050                                             pts[i] = ParseStackElem!(Location, NonterminalType!nonterminalID)(nonterminalStarts[i], nonterminals[i].get!(arrayToAliasSeq!(NonterminalClosures[nonterminalID])));
1051                                         $$} else {
1052                                             pts[i] = ParseStackElem!(Location, NonterminalType!nonterminalID)(nonterminalStarts[i], nonterminals[i].get!nonterminalID);
1053                                         $$}
1054                                     NonterminalType!nonterminalID pt = creator.mergeParseTrees!nonterminalID(nonterminalStart, pendingReduce.alreadyShifted?end:lastTokenEnd, pts);
1055                                     pendingReduce.stackEdge.data = new StackEdgeData(false);
1056                                     pendingReduce.stackEdge.data.start = nonterminalStart;
1057                                     pendingReduce.stackEdge.data.nonterminal =
1058                                         Creator.NonterminalUnionAny.create(nonterminalID, pt);
1059                                 }
1060                                 break switchlabel;
1061                             }
1062                         }
1063                         default:
1064                             assert(0);
1065                     }
1066                 $$}
1067             }
1068         }
1069 
1070         $$if (graph.globalOptions.directUnwrap) {
1071             $$foreach (i, n; graph.states) {
1072                 $$if (n.stackSize() >= 0) {
1073                     $$NonterminalID[] possible = n.directUnwrapNonterminalsOnStack(graph.grammar, 1);
1074                     $$if (possible.length) {
1075                         void onPendingReduce$(i)(ref PendingReduce2 pendingReduce, Location end, Creator.NonterminalUnionAny[] nonterminals, Location[] nonterminalStarts, Location nonterminalStart)
1076                         {
1077                             static if (canMerge!($(grammar.nonterminalIDCode(possible[0]))))
1078                             {
1079                                 ParseStackElem!(Location, NonterminalType!$(grammar.nonterminalIDCode(possible[0])))[] pts;
1080                                 pts.length = nonterminals.length;
1081                                 foreach (i; 0 .. nonterminals.length)
1082                                 {
1083                                     bool found;
1084                                     static foreach (nonterminalID; [  _
1085                                         $$foreach (nonterminal; possible) {
1086                                             $(grammar.nonterminalIDCode(nonterminal)),   _
1087                                         $$}
1088                                     ])
1089                                     {
1090                                         if (nonterminals[i].nonterminalID == nonterminalID)
1091                                         {
1092                                             pts[i] = ParseStackElem!(Location, NonterminalType!nonterminalID)(nonterminalStarts[i], nonterminals[i].get!(nonterminalID));
1093                                             found = true;
1094                                         }
1095                                     }
1096                                     assert(found);
1097                                 }
1098                                 NonterminalType!$(grammar.nonterminalIDCode(possible[0])) pt = creator.mergeParseTrees!$(grammar.nonterminalIDCode(possible[0]))(nonterminalStart, pendingReduce.alreadyShifted?end:lastTokenEnd, pts);
1099                                 pendingReduce.stackEdge.data = new StackEdgeData(false);
1100                                 pendingReduce.stackEdge.data.start = nonterminalStart;
1101                                 pendingReduce.stackEdge.data.nonterminal =
1102                                     Creator.NonterminalUnionAny.create($(grammar.nonterminalIDCode(possible[0])), pt);
1103                             }
1104                         }
1105                     $$}
1106                 $$}
1107             $$}
1108         $$}
1109 
1110         void pushToken(StackNode *stackNode, PendingReduce pendingReduce, Location tokenStart, Location tokenEnd, bool alreadyShifted$(grammar.tags.vals.length?", Tag tags":""))
1111         in
1112         {
1113             assert(lastTokenEnd.isValid);
1114         }
1115         do
1116         {
1117             switch (stackNode.state)
1118             {
1119                 $$foreach (i, n; graph.states) {
1120                     $$if (!trivialState(n) && needsJumps(graph, i, n, genActionTable(graph, n))) {
1121                         $$if (!n.hasSetStackSymbols || graph.globalOptions.directUnwrap) {
1122                             case $(i): $(parseFunctionName(graph, i, "pushTokenState"))  _
1123                             (stackNode, pendingReduce, tokenStart, tokenEnd, alreadyShifted$(grammar.tags.vals.length?", tags":"")); break;
1124                         $$}
1125                     $$}
1126                 $$}
1127                 default: assert(false);
1128             }
1129         }
1130 
1131         void pushEnd()
1132         in
1133         {
1134             assert(lastTokenEnd.bytePos != size_t.max);
1135         }
1136         do
1137         {
1138             pushToken(getTokenID!"$end", Token.init, lastTokenEnd, lastTokenEnd);
1139         }
1140     }));
1141 }
1142 
1143 const(char)[] createParserModule(LRGraph graph, string modulename)
1144 {
1145     EBNFGrammar grammar = graph.grammar;
1146 
1147     if (graph.states.length == 0)
1148         return "// no states\n";
1149 
1150     CodeWriter code;
1151     code.indentStr = "    ";
1152 
1153     string nonterminalNameCode(const Nonterminal n)
1154     {
1155         return n.name.escapeD;
1156     }
1157 
1158     string allTokensCode = createAllTokensCode(grammar);
1159     string allNonterminalsCode = createAllNonterminalsCode(grammar);
1160 
1161     bool needsDelayedParseTreeConstructor;
1162     foreach (node; graph.states)
1163     {
1164         if (node.hasSetStackSymbols && graph.globalOptions.delayedReduce)
1165             needsDelayedParseTreeConstructor = true;
1166     }
1167 
1168     mixin(genCode("code", q{
1169         // Generated with DParserGen.
1170         module $(modulename);
1171         import dparsergen.core.grammarinfo;
1172         import dparsergen.core.parseexception;
1173         import dparsergen.core.parsestackelem;
1174         import dparsergen.core.utils;
1175         import std.algorithm;
1176         import std.array;
1177         import std.conv;
1178         import std.meta;
1179         import std.stdio;
1180 
1181         enum SymbolID startTokenID = $(grammar.startTokenID);
1182         static assert(allTokens.length < SymbolID.max - startTokenID);
1183         enum SymbolID endTokenID = startTokenID + allTokens.length;
1184 
1185         enum SymbolID startNonterminalID = $(grammar.startNonterminalID);
1186         static assert(allNonterminals.length < SymbolID.max - startNonterminalID);
1187         enum SymbolID endNonterminalID = startNonterminalID + allNonterminals.length;
1188 
1189         enum ProductionID startProductionID = $(grammar.startProductionID);
1190         static assert(allProductions.length < ProductionID.max - startProductionID);
1191         enum ProductionID endProductionID = startProductionID + allProductions.length;
1192 
1193         enum nonterminalIDFor(string name) = startNonterminalID + staticIndexOf!(name,
1194             $$foreach (i, n; grammar.nonterminals.vals) {
1195                 "$(nonterminalNameCode(n))",
1196             $$}
1197             );
1198 
1199         size_t getTokenIDImpl(string tok)
1200         {
1201             auto r = allTokens.countUntil!(t=>t.name == tok);
1202             assert(r >= 0 && r < allTokens.length, "token not found " ~ tok);
1203             return r + startTokenID;
1204         }
1205         enum size_t getTokenID(string tok) = getTokenIDImpl(tok);
1206         string getTokenName(size_t id)
1207         {
1208             if (id == size_t.max)
1209                 return text("???");
1210             if (id < startTokenID)
1211                 return text("???:", id);
1212             if (id >= endTokenID)
1213                 return text("???:", id);
1214             return allTokens[id - startTokenID].name;
1215         }
1216         string getNonterminalName(size_t id)
1217         {
1218             if (id == size_t.max)
1219                 return text("???");
1220             if (id < startNonterminalID || id > endNonterminalID)
1221                 return text("???:", id);
1222             return allNonterminals[id - startNonterminalID].name;
1223         }
1224         $$if (needsDelayedParseTreeConstructor) {
1225             class DelayedParseTreeConstructor(alias Creator)
1226             {
1227                 alias Location = Creator.Location;
1228                 alias LocationDiff = typeof(Location.init - Location.init);
1229 
1230                 immutable size_t[] nonterminalIDs;
1231                 LocationDiff inputLength;
1232                 this(immutable size_t[] nonterminalIDs, LocationDiff inputLength)
1233                 {
1234                     this.nonterminalIDs = nonterminalIDs;
1235                     this.inputLength = inputLength;
1236                 }
1237             }
1238         $$}
1239         $$if (grammar.tags.vals.length) {
1240             enum Tag
1241             {
1242                 none = 0,
1243                 $$foreach (i, t; grammar.tags.vals) {
1244                     $(t.name) = 1 << $(i),
1245                 $$}
1246             }
1247         $$}
1248 
1249         struct PushParser(alias Creator, Token)
1250         {
1251             alias Location = Creator.Location;
1252             Creator creator;
1253 
1254             alias LocationDiff = typeof(Location.init - Location.init);
1255 
1256             $$foreach (i, n; graph.states) {
1257                 $$if (needsExtraStateData(graph, i, n)) {
1258                     $$createExtraStateData(code, graph, i, n);
1259 
1260                 $$}
1261             $$}
1262             static struct StackNode
1263             {
1264                 size_t state;
1265                 StackEdge*[] previous;
1266                 union
1267                 {
1268                     $$foreach (i, n; graph.states) {
1269                         $$if (needsExtraStateData(graph, i, n)) {
1270                             $(parseFunctionName(graph, i, "StateData")) $(parseFunctionName(graph, i, "stateData"));
1271                         $$}
1272                     $$}
1273                 }
1274             }
1275             static struct StackEdgeData
1276             {
1277                 bool isToken;
1278                 Location start;
1279                 union
1280                 {
1281                     Creator.NonterminalUnionAny nonterminal;
1282                     Token token;
1283                 }
1284             }
1285             static struct StackEdge
1286             {
1287                 StackNode *node;
1288                 StackEdgeData *data;
1289                 bool reduceDone;
1290                 $$if (grammar.tags.vals.length) {
1291                     Tag tags;
1292                 $$}
1293             }
1294 
1295             static struct PendingReduce
1296             {
1297                 SymbolID nonterminalID;
1298                 StackEdge*[] parameterEdges;
1299                 ProductionID productionID;
1300                 StackEdgeData* function(ref PushParser this_, StackEdge*[] parameterEdges, Location lastTokenEnd) dg;
1301                 PendingReduce* next;
1302             }
1303             static struct PendingReduce2
1304             {
1305                 StackNode* stackNode;
1306                 StackEdge* stackEdge;
1307                 bool alreadyShifted;
1308                 PendingReduce* pendingReduces;
1309                 size_t nextPendingReduce2;
1310             }
1311 
1312             static struct TmpData
1313             {
1314                 bool inUse;
1315                 StackNode*[$(graph.states.length * 2)] stackNodeByState;
1316                 size_t[$(graph.states.length * 2)] pendingReduceIds;
1317                 SimpleArrayAllocator!(PendingReduce, 4 * 1024 - 32) pendingReduceAllocator;
1318                 SimpleArrayAllocator!(StackEdge*, 4 * 1024 - 32) stackEdgePointerAllocator;
1319                 Appender!(PendingReduce2[]) pendingReduces;
1320             }
1321             TmpData tmpData;
1322 
1323             void clearTmpData()
1324             {
1325                 tmpData.stackNodeByState[] = null;
1326                 tmpData.pendingReduceIds[] = size_t.max;
1327                 tmpData.pendingReduceAllocator.clearAll();
1328                 tmpData.stackEdgePointerAllocator.clearAll();
1329                 tmpData.pendingReduces.clear();
1330             }
1331 
1332             StackNode*[] stackTops;
1333             StackNode*[] acceptedStackTops;
1334 
1335             Location lastTokenEnd;
1336             bool hasAddedPendingReduce;
1337 
1338             $$createShiftFunctions(code, graph);
1339 
1340             void dumpStates(string indent="")
1341             {
1342                 write(indent, "stackTops:");
1343                 foreach (stackNode; stackTops)
1344                 {
1345                     write(" ", stackNode.state);
1346                 }
1347                 writeln();
1348                 write(indent, "acceptedStackTops:");
1349                 foreach (stackNode; acceptedStackTops)
1350                 {
1351                     write(" ", stackNode.state);
1352                 }
1353                 writeln();
1354             }
1355 
1356             alias NonterminalType(size_t nonterminalID) = Creator.NonterminalType!nonterminalID;
1357             enum canMerge(size_t nonterminalID) = Creator.canMerge!nonterminalID;
1358 
1359             $$foreach (production; graph.grammar.productions) {
1360                 $$createReduceFunction(code, graph, production);
1361 
1362             $$}
1363 
1364             $$foreach (i, n; graph.states) {
1365                 $$if (true || !trivialState(n)) {
1366                     $$createParseFunction(code, graph, i, n);
1367 
1368                 $$}
1369             $$}
1370 
1371             $$foreach (i, n; graph.states) {
1372                 $$if (n.isStartNode) {
1373                     $$createStartParseFunction(code, graph, i, n);
1374 
1375                 $$}
1376             $$}
1377 
1378             $$createParseFunctions(code, graph);
1379 
1380             Creator.Type getParseTree(string startNonterminal = "$(graph.grammar.getSymbolName(graph.grammar.startNonterminals[0].nonterminal).escapeD)")()
1381             {
1382                 assert(stackTops.length == 0, text(stackTops));
1383                 assert(acceptedStackTops.length <= 1, text(acceptedStackTops));
1384                 if (acceptedStackTops.length)
1385                 {
1386                     assert(acceptedStackTops[0].previous.length == 1);
1387                     assert(acceptedStackTops[0].previous[0].node.previous.length == 0);
1388                     return acceptedStackTops[0].previous[0].data.nonterminal.get!(nonterminalIDFor!startNonterminal);
1389                 }
1390                 return Creator.Type.init;
1391             }
1392         }
1393     }));
1394     mixin(genCode("code", q{
1395         SymbolID translateTokenIdFromLexer(alias Lexer)(SymbolID t)
1396         {
1397             $$foreach (t2; grammar.tokens.allIDs) {
1398                 if (t == Lexer.tokenID!$(tokenDCode(grammar.tokens[t2])))
1399                     return $(t2.id + grammar.startTokenID);
1400             $$}
1401             return SymbolID.max;
1402         }
1403 
1404         struct Parser(alias Creator, alias L)
1405         {
1406             alias Lexer = L;
1407             alias Location = typeof(Lexer.init.front.currentLocation);
1408             alias LocationDiff = typeof(Location.init - Location.init);
1409 
1410             Lexer *lexer;
1411 
1412             PushParser!(Creator, typeof(Lexer.init.front.content)) pushParser;
1413 
1414             alias pushParser this;
1415 
1416             template NonterminalType(size_t nonterminalID) if (nonterminalID >= startNonterminalID && nonterminalID < endNonterminalID)
1417             {
1418                 alias NonterminalType = Creator.NonterminalType!nonterminalID;
1419             }
1420 
1421                 this(Creator creator, Lexer *lexer)
1422                 {
1423                     pushParser.creator = creator;
1424                     this.lexer = lexer;
1425                 }
1426 
1427             $$foreach (i, n; graph.states) {
1428                 $$if (n.isStartNode) {
1429                     $$createWrapperParseFunction(code, graph, i, n);
1430                 $$}
1431             $$}
1432         }
1433 
1434         immutable allTokens = [
1435         $(allTokensCode)];
1436 
1437         immutable allNonterminals = [
1438         $(allNonterminalsCode)];
1439 
1440         immutable allProductions = [
1441         $(createAllProductionsCode(grammar))];
1442 
1443         $$if (graph.globalOptions.directUnwrap) {
1444             immutable nonterminalClosures = [
1445                 $$foreach (i, n; grammar.nonterminals.vals) {
1446                     /*$(i) $(grammar.getSymbolName(NonterminalID(i.to!SymbolID)))*/ [  _
1447                     $$foreach (m2; grammar.directUnwrapClosure(NonterminalID(i.to!SymbolID), [], [])) {
1448                         $(grammar.nonterminalIDCode(m2.nonterminalID)),   _
1449                     $$}
1450                     ],
1451                 $$}
1452             ];
1453 
1454         $$}
1455         immutable GrammarInfo grammarInfo = immutable(GrammarInfo)(
1456                 startTokenID, startNonterminalID, startProductionID,
1457                 allTokens, allNonterminals, allProductions);
1458 
1459         Creator.Type parse(Creator, alias Lexer, string startNonterminal = "$(graph.grammar.getSymbolName(graph.grammar.startNonterminals[0].nonterminal).escapeD)")(ref Lexer lexer, Creator creator)
1460         {
1461             alias Location = typeof(Lexer.init.front.currentLocation);
1462             auto parser = Parser!(Creator, Lexer)(
1463                     creator,
1464                     &lexer);
1465             auto parseResult = parser.$(parseFunctionName(graph, 0))();
1466             Creator.Type result = parseResult.val;
1467             creator.adjustStart(result, parseResult.start);
1468             return result;
1469         }
1470 
1471         Creator.Type parse(Creator, alias Lexer, string startNonterminal = "$(graph.grammar.getSymbolName(graph.grammar.startNonterminals[0].nonterminal).escapeD)")(string input, Creator creator, typeof(Lexer.init.front.currentLocation) startLocation = typeof(Lexer.init.front.currentLocation).init)
1472         {
1473             alias Location = typeof(Lexer.init.front.currentLocation);
1474             Lexer lexer = Lexer(input, startLocation);
1475             auto result = parse!(Creator, Lexer, startNonterminal)(lexer, creator);
1476             if (!lexer.empty)
1477             {
1478                 throw new SingleParseException!Location("input left after parse",
1479                         lexer.front.currentLocation, lexer.front.currentTokenEnd);
1480             }
1481             return result;
1482         }
1483         }));
1484 
1485     return code.data;
1486 }