Unofficial Dub Package Documentation 
1 module epsilon.sweep;
2 
3 import EAG = epsilon.eag;
4 import EmitGen = epsilon.emitgen;
5 import EvalGen = epsilon.slaggen;
6 import epsilon.settings;
7 import io : Input, read, UndefPos;
8 import log;
9 import runtime;
10 import std.bitmanip : BitArray;
11 import std.stdio;
12 import std.typecons;
13 
14 private const nil = 0;
15 private const indexOfFirstAlt = 1;
16 private int[] FactorOffset;
17 private BitArray GenNonts;
18 private BitArray GenFactors;
19 private bool Error;
20 
21 public void Test(Settings settings)
22 in (EAG.Performed(EAG.analysed | EAG.predicates))
23 {
24     info!"single-sweep testing %s"(EAG.BaseName);
25     EAG.History &= ~EAG.isSweep;
26     Init;
27     scope (exit)
28         Finit;
29 
30     const SaveHistory = EAG.History;
31 
32     EAG.History = 0;
33     GenerateMod(No.createMod, settings);
34     EAG.History = SaveHistory;
35     if (!Error)
36     {
37         info!"%s grammar is single sweep"(EAG.BaseName);
38         EAG.History |= EAG.isSweep;
39     }
40 }
41 
42 public string Generate(Settings settings)
43 in (EAG.Performed(EAG.analysed | EAG.predicates))
44 {
45     info!"single-sweep writing %s"(EAG.BaseName);
46     EAG.History &= ~EAG.isSweep;
47     Init;
48     scope (exit)
49         Finit;
50 
51     const SaveHistory = EAG.History;
52 
53     EAG.History = 0;
54 
55     const fileName = GenerateMod(Yes.createMod, settings);
56 
57     EAG.History = SaveHistory;
58     if (!Error)
59     {
60         EAG.History |= EAG.isSweep;
61         EAG.History |= EAG.hasEvaluator;
62     }
63     return fileName;
64 }
65 
66 private void Init() nothrow
67 {
68     FactorOffset = new int[EAG.NextHFactor + EAG.NextHAlt + 1];
69     GenFactors = EAG.Prod & EAG.Reach;
70     GenNonts = GenFactors - EAG.Pred;
71     Error = false;
72 }
73 
74 private void Finit() @nogc nothrow @safe
75 {
76     FactorOffset = null;
77 }
78 
79 private string GenerateMod(Flag!"createMod" createMod, Settings settings)
80 {
81     const firstEdge = 1;
82     const firstStack = 0;
83 
84     struct EdgeRecord
85     {
86         int Dest;
87         int Next;
88     }
89 
90     struct FactorRecord
91     {
92         int Vars;
93         int CountAppl;
94         int Prio;
95         EAG.Factor F;
96     }
97 
98     struct VarRecord
99     {
100         int Factors;
101     }
102 
103     int V;
104     File output;
105     Input Fix;
106     EAG.Rule SavedNontDef;
107     int SavedNextHFactor;
108     int SavedNextHAlt;
109     FactorRecord[] Factor;
110     VarRecord[] Var;
111     EdgeRecord[] Edge;
112     int NextEdge;
113     int[] Stack;
114     int NextStack;
115     BitArray DefVars;
116 
117     void Expand()
118     {
119         if (NextEdge >= Edge.length)
120         {
121             auto Edge1 = new EdgeRecord[2 * Edge.length];
122 
123             for (size_t i = firstEdge; i < Edge.length; ++i)
124             {
125                 Edge1[i] = Edge[i];
126             }
127             Edge = Edge1;
128         }
129     }
130 
131     void InclFix(char Term)
132     {
133         import std.conv : to;
134         import std.exception : enforce;
135 
136         char c = Fix.front.to!char;
137 
138         while (c != Term)
139         {
140             enforce(c != 0,
141                     "error: unexpected end of eSSweep.fix.d");
142 
143             output.write(c);
144             Fix.popFront;
145             c = Fix.front.to!char;
146         }
147         Fix.popFront;
148     }
149 
150     int HyperArity()
151     {
152         const Nonts = EAG.All - EAG.Pred;
153         int Max = 0;
154         int i;
155 
156         foreach (N; Nonts.bitsSet)
157         {
158             EAG.Alt A = EAG.HNont[N].Def.Sub;
159 
160             i = 0;
161             do
162             {
163                 ++i;
164                 A = A.Next;
165             }
166             while (A !is null);
167             if (cast(EAG.Opt) EAG.HNont[N].Def || cast(EAG.Rep) EAG.HNont[N].Def)
168                 ++i;
169             if (i > Max)
170                 Max = i;
171         }
172         i = 1;
173         while (i <= Max)
174             i = i * 2;
175         return i;
176     }
177 
178     void SaveAndPatchNont(size_t N)
179     {
180         import std.conv : to;
181 
182         EAG.Alt A;
183         EAG.Alt A1;
184         EAG.Alt A2;
185         EAG.Factor F;
186         EAG.Nont F1;
187         EAG.Nont F2;
188 
189         SavedNontDef = EAG.HNont[N].Def;
190         SavedNextHFactor = EAG.NextHFactor;
191         SavedNextHAlt = EAG.NextHAlt;
192 
193         EAG.Grp Def = new EAG.Grp;
194 
195         A = EAG.HNont[N].Def.Sub;
196         A2 = null;
197         do
198         {
199             A1 = new EAG.Alt;
200             EAG.assign(A1, A);
201             A1.Sub = null;
202             A1.Last = null;
203             A1.Next = null;
204             if (A2 !is null)
205                 A2.Next = A1;
206             else
207                 Def.Sub = A1;
208             A2 = A1;
209             F = A.Sub;
210             F2 = null;
211             while (F !is null)
212             {
213                 if (auto nont = cast(EAG.Nont) F)
214                     if (GenFactors[nont.Sym])
215                     {
216                         F1 = new EAG.Nont;
217                         EAG.assign(F1, nont);
218                         F1.Prev = F2;
219                         F1.Next = null;
220                         A1.Last = F1;
221                         if (F2 !is null)
222                             F2.Next = F1;
223                         else
224                             A1.Sub = F1;
225                         F2 = F1;
226                     }
227                 F = F.Next;
228             }
229             if (cast(EAG.Rep) EAG.HNont[N].Def)
230             {
231                 F1 = new EAG.Nont;
232                 F1.Ind = EAG.NextHFactor;
233                 ++EAG.NextHFactor;
234                 F1.Prev = A1.Last;
235                 A1.Last = F1;
236                 if (A1.Sub is null)
237                     A1.Sub = F1;
238                 if (F1.Prev !is null)
239                     F1.Prev.Next = F1;
240                 F1.Next = null;
241                 F1.Sym = N.to!int;
242                 F1.Pos = A1.Actual.Pos;
243                 F1.Actual = A1.Actual;
244                 A1.Actual.Pos = UndefPos;
245                 A1.Actual.Params = EAG.empty;
246             }
247             A = A.Next;
248         }
249         while (A !is null);
250         if (cast(EAG.Opt) EAG.HNont[N].Def || cast(EAG.Rep) EAG.HNont[N].Def)
251         {
252             A1 = new EAG.Alt;
253             A1.Ind = EAG.NextHAlt;
254             ++EAG.NextHAlt;
255             A1.Up = N.to!int;
256             A1.Next = null;
257             A1.Sub = null;
258             A1.Last = null;
259             if (auto opt = cast(EAG.Opt) EAG.HNont[N].Def)
260             {
261                 A1.Scope = opt.Scope;
262                 A1.Formal = opt.Formal;
263                 A1.Pos = opt.EmptyAltPos;
264             }
265             else if (auto rep = cast(EAG.Rep) EAG.HNont[N].Def)
266             {
267                 A1.Scope = rep.Scope;
268                 A1.Formal = rep.Formal;
269                 A1.Pos = rep.EmptyAltPos;
270             }
271             A1.Actual.Params = EAG.empty;
272             A1.Actual.Pos = UndefPos;
273             A2.Next = A1;
274         }
275         EAG.HNont[N].Def = Def;
276     }
277 
278     void RestoreNont(size_t N)
279     {
280         EAG.HNont[N].Def = SavedNontDef;
281         EAG.NextHFactor = SavedNextHFactor;
282         EAG.NextHAlt = SavedNextHAlt;
283     }
284 
285     void ComputePermutation(size_t N)
286     {
287         const def = 0;
288         const right = 1;
289         const appl = 2;
290         EAG.Alt A;
291         EAG.Factor F;
292         EAG.Factor F1;
293         int Prio;
294         int Index;
295         int Offset;
296         int NE;
297         int VE;
298         int V;
299 
300         void TravParams(int op, int P, EAG.Factor F)
301         {
302             bool Def;
303 
304             void NewEdge(ref int From, int To)
305             {
306                 if (NextEdge >= Edge.length)
307                 {
308                     Expand;
309                 }
310                 Edge[NextEdge].Dest = To;
311                 Edge[NextEdge].Next = From;
312                 From = NextEdge;
313                 ++NextEdge;
314             }
315 
316             void Tree(int Node)
317             {
318                 int n;
319                 if (Node < 0)
320                 {
321                     switch (op)
322                     {
323                     case def:
324                         if (Def)
325                             DefVars[-Node] = true;
326                         break;
327                     case right:
328                         if (!DefVars[-Node])
329                         {
330                             if (Def)
331                             {
332                                 NewEdge(Factor[F.Ind].Vars, -Node);
333                             }
334                             else
335                             {
336                                 NewEdge(Var[-Node].Factors, F.Ind);
337                                 ++Factor[F.Ind].CountAppl;
338                             }
339                         }
340                         break;
341                     case appl:
342                         if (!Def && !DefVars[-Node])
343                         {
344                             error!"variable %s is not defined\n%s"(EAG.VarRepr(-Node), EAG.ParamBuf[P].Pos);
345                             Error = true;
346                         }
347                         break;
348                     default:
349                         assert(0);
350                     }
351                 }
352                 else
353                 {
354                     for (n = 1; n <= EAG.MAlt[EAG.NodeBuf[Node]].Arity; ++n)
355                         Tree(EAG.NodeBuf[Node + n]);
356                 }
357             }
358 
359             while (EAG.ParamBuf[P].Affixform != EAG.nil)
360             {
361                 Def = EAG.ParamBuf[P].isDef;
362                 Tree(EAG.ParamBuf[P].Affixform);
363                 ++P;
364             }
365         }
366 
367         void Pop(ref EAG.Factor F)
368         {
369             int i;
370             int MinPrio;
371             int MinIndex;
372 
373             MinPrio = int.max;
374             for (i = firstStack; i < NextStack; ++i)
375             {
376                 if (Factor[Stack[i]].Prio < MinPrio)
377                 {
378                     MinPrio = Factor[Stack[i]].Prio;
379                     MinIndex = i;
380                 }
381             }
382             F = Factor[Stack[MinIndex]].F;
383             Stack[MinIndex] = Stack[NextStack - 1];
384             --NextStack;
385         }
386 
387         A = EAG.HNont[N].Def.Sub;
388         do
389         {
390             DefVars[] = false;
391             NextEdge = firstEdge;
392             NextStack = firstStack;
393             TravParams(def, A.Formal.Params, null);
394             F = A.Sub;
395             Prio = 0;
396             Offset = 1;
397             while (F !is null)
398             {
399                 Factor[F.Ind].Vars = nil;
400                 Factor[F.Ind].CountAppl = 0;
401                 Factor[F.Ind].Prio = Prio;
402                 ++Prio;
403                 Factor[F.Ind].F = F;
404                 if (!EAG.Pred[(cast(EAG.Nont) F).Sym])
405                 {
406                     FactorOffset[F.Ind] = Offset;
407                     ++Offset;
408                 }
409                 TravParams(right, (cast(EAG.Nont) F).Actual.Params, F);
410                 if (Factor[F.Ind].CountAppl == 0)
411                 {
412                     Stack[NextStack] = F.Ind;
413                     ++NextStack;
414                 }
415                 F = F.Next;
416             }
417             A.Sub = null;
418             A.Last = null;
419             F1 = null;
420             Index = 0;
421             while (NextStack > firstStack)
422             {
423                 Pop(F);
424                 F.Prev = F1;
425                 F.Next = null;
426                 A.Last = F;
427                 if (F1 !is null)
428                     F1.Next = F;
429                 else
430                     A.Sub = F;
431                 F1 = F;
432                 ++Index;
433                 VE = Factor[F.Ind].Vars;
434                 while (VE != nil)
435                 {
436                     V = Edge[VE].Dest;
437                     if (!DefVars[V])
438                     {
439                         NE = Var[V].Factors;
440                         while (NE != nil)
441                         {
442                             --Factor[Edge[NE].Dest].CountAppl;
443                             if (Factor[Edge[NE].Dest].CountAppl == 0)
444                             {
445                                 Stack[NextStack] = Edge[NE].Dest;
446                                 ++NextStack;
447                             }
448                             NE = Edge[NE].Next;
449                         }
450                         DefVars[V] = true;
451                     }
452                     VE = Edge[VE].Next;
453                 }
454             }
455             if (Index == Prio)
456             {
457                 TravParams(appl, A.Formal.Params, null);
458             }
459             else
460             {
461                 error!"alternative is not single sweep\n%s"(A.Pos);
462                 Error = true;
463             }
464             A = A.Next;
465         }
466         while (A !is null);
467     }
468 
469     void GenerateNont(size_t N)
470     {
471         EAG.Alt A;
472         EAG.Factor F;
473         EAG.Factor F1;
474         int AltIndex;
475         EvalGen.ComputeVarNames(N, No.embed);
476         output.write("void P", N, "(TreeType Adr");
477         EvalGen.GenFormalParams(N, No.parNeeded);
478         output.write(") // ", EAG.HNontRepr(N));
479         if (EAG.HNont[N].anonymous)
480             output.write(" in ", EAG.NamedHNontRepr(N));
481         output.writeln;
482         output.writeln("{");
483         EvalGen.GenVarDecl(N);
484         output.writeln("switch (MOD(Tree[Adr], hyperArityConst))");
485         output.writeln("{");
486         A = EAG.HNont[N].Def.Sub;
487         AltIndex = indexOfFirstAlt;
488         do
489         {
490             output.writeln("case ", AltIndex, ":");
491             EvalGen.InitScope(A.Scope);
492             if (EvalGen.PosNeeded(A.Formal.Params))
493                 output.writeln("Pos = PosTree[Adr];");
494             EvalGen.GenAnalPred(N, A.Formal.Params);
495             F = A.Sub;
496             while (F !is null)
497             {
498                 if (auto nont = cast(EAG.Nont) F)
499                 {
500                     if (!EAG.Pred[nont.Sym])
501                     {
502                         EvalGen.GenSynPred(N, nont.Actual.Params);
503                         output.write("P", nont.Sym, "(Tree[Adr + ", FactorOffset[F.Ind], "]");
504                         EvalGen.GenActualParams(nont.Actual.Params, false);
505                         output.write("); // ", EAG.HNontRepr(nont.Sym));
506                         if (EAG.HNont[nont.Sym].anonymous)
507                             output.write(" in ", EAG.NamedHNontRepr(nont.Sym));
508                         output.writeln;
509                         if (EvalGen.PosNeeded(nont.Actual.Params))
510                             output.writeln("Pos = PosTree[Adr + ", FactorOffset[F.Ind], "];");
511                         EvalGen.GenAnalPred(N, nont.Actual.Params);
512                     }
513                     else
514                     {
515                         EvalGen.GenSynPred(N, nont.Actual.Params);
516                         output.write("Pos = PosTree[Adr");
517                         F1 = F.Prev;
518                         while (F1 !is null && EAG.Pred[(cast(EAG.Nont) F1).Sym])
519                             F1 = F1.Prev;
520                         if (F1 !is null)
521                             output.write(" + ", FactorOffset[F1.Ind]);
522                         output.writeln("];");
523                         EvalGen.GenPredCall(nont.Sym, nont.Actual.Params);
524                         EvalGen.GenAnalPred(N, nont.Actual.Params);
525                     }
526                 }
527                 F = F.Next;
528             }
529             EvalGen.GenSynPred(N, A.Formal.Params);
530             output.writeln("break;");
531             A = A.Next;
532             ++AltIndex;
533         }
534         while (A !is null);
535         output.writeln("default:");
536         output.writeln("assert(0);");
537         output.writeln("}");
538         output.writeln("}");
539         output.writeln;
540     }
541 
542     enum fixName = "sweep.fix.d";
543     const name = EAG.BaseName ~ "Eval";
544     const fileName = settings.path(name ~ ".d");
545 
546     EvalGen.InitTest;
547     Error = Error || !EvalGen.PredsOK();
548     if (createMod)
549     {
550         Fix = Input(fixName, import(fixName));
551         output = File(fileName, "w");
552         if (!Error)
553         {
554             EvalGen.InitGen(output, EvalGen.sweepPass, settings);
555             InclFix('$');
556             output.write(name);
557             InclFix('$');
558             output.write(HyperArity());
559             InclFix('$');
560             EvalGen.GenDeclarations(settings);
561             EvalGen.GenPredProcs;
562             output.writeln;
563         }
564     }
565     Factor = new FactorRecord[EAG.NextHFactor + EAG.NextHAlt + 1];
566     Var = new VarRecord[EAG.NextVar + 1];
567     Edge = new EdgeRecord[127];
568     Stack = new int[EAG.NextHFactor + 1];
569     DefVars = BitArray();
570     DefVars.length = EAG.NextVar + 1;
571     for (V = EAG.firstVar; V < EAG.NextVar; ++V)
572         Var[V].Factors = nil;
573     foreach (N; GenNonts.bitsSet)
574     {
575         SaveAndPatchNont(N);
576         ComputePermutation(N);
577         if (!Error)
578         {
579             Error = !EvalGen.IsLAG(N);
580             if (!Error && createMod)
581                 GenerateNont(N);
582         }
583         RestoreNont(N);
584     }
585     if (createMod)
586     {
587         if (!Error)
588         {
589             EmitGen.GenEmitProc(output, settings);
590             InclFix('$');
591             output.write("P", EAG.StartSym);
592             InclFix('$');
593             EmitGen.GenEmitCall(output, settings);
594             InclFix('$');
595             EmitGen.GenShowHeap(output);
596             InclFix('$');
597             output.write(EAG.BaseName, "Eval");
598             InclFix('$');
599             output.close;
600         }
601         EvalGen.FinitGen;
602     }
603     EvalGen.FinitTest;
604     return fileName;
605 }

Page generated by adrdox