1 module epsilon.soag.soag;
2 
3 import EAG = epsilon.eag;
4 import Predicates = epsilon.predicates;
5 import runtime;
6 import std.bitmanip : BitArray;
7 import std.stdio;
8 
9 const firstSym = EAG.firstHNont;
10 const firstRule = 0;
11 const firstSymOcc = 0;
12 const firstAffOcc = 0;
13 const firstPartNum = 0;
14 const firstAffOccNum = 0;
15 const firstVS = 1;
16 const firstDefAffOcc = EAG.firstVar;
17 const firstStorageName = 0;
18 const firstAffixApplCnt = EAG.firstVar;
19 const nil = -1;
20 
21 struct SymDesc
22 {
23     int FirstOcc;
24     int MaxPart;
25     EAG.ScopeDesc AffPos;
26 
27     public string toString() const pure @safe
28     {
29         import std.format : format;
30 
31         string[] items;
32 
33         items ~= format!"FirstOcc=%s"(FirstOcc);
34         items ~= format!"MaxPart=%s"(MaxPart);
35         items ~= format!"AffPos=%s"(AffPos);
36         return format!"Sym(%-(%s, %))"(items);
37     }
38 }
39 
40 class RuleDesc
41 {
42     EAG.ScopeDesc SymOcc;
43     EAG.ScopeDesc AffOcc;
44     BitArray[] TDP;
45     BitArray[] DP;
46     EAG.ScopeDesc VS;
47 }
48 
49 alias RuleBase = RuleDesc;
50 
51 class EmptyRule : RuleDesc
52 {
53     EAG.Rule Rule;
54 }
55 
56 class OrdRule : RuleDesc
57 {
58     EAG.Alt Alt;
59 }
60 
61 struct SymOccDesc
62 {
63     int SymInd;
64     int RuleInd;
65     EAG.Nont Nont;
66     EAG.ScopeDesc AffOcc;
67     int Next;
68 
69     public string toString() const @safe
70     {
71         import std.format : format;
72 
73         string[] items;
74 
75         items ~= EAG.HNontRepr(SymInd);
76         items ~= format!"RuleInd=%s"(RuleInd);
77         items ~= format!"Nont=%s"(Nont);
78         items ~= format!"AffOcc=%s"(AffOcc);
79         items ~= format!"Next=%s"(Next);
80         return format!"SymOcc(%-(%s, %))"(items);
81     }
82 }
83 
84 struct AffOccNumRecord
85 {
86     int InRule;
87     int InSym;
88 
89     public string toString() const pure @safe
90     {
91         import std.format : format;
92 
93         string[] items;
94 
95         items ~= format!"InRule=%s"(InRule);
96         items ~= format!"InSym=%s"(InSym);
97         return format!"AffOccNum(%-(%s, %))"(items);
98     }
99 }
100 
101 struct AffOccDesc
102 {
103     int ParamBufInd;
104     int SymOccInd;
105     AffOccNumRecord AffOccNum;
106 
107     public string toString() const pure @safe
108     {
109         import std.format : format;
110 
111         string[] items;
112 
113         items ~= format!"ParamBufInd=%s"(ParamBufInd);
114         items ~= format!"SymOccInd=%s"(SymOccInd);
115         items ~= AffOccNum.toString;
116         return format!"AffOcc(%-(%s, %))"(items);
117     }
118 }
119 
120 class Instruction
121 {
122 }
123 
124 class Visit : Instruction
125 {
126     int SymOcc;
127     int VisitNo;
128 }
129 
130 class Leave : Instruction
131 {
132     int VisitNo;
133 }
134 
135 class Call : Instruction
136 {
137     int SymOcc;
138 }
139 
140 SymDesc[] Sym;
141 int[] PartNum;
142 RuleBase[] Rule;
143 SymOccDesc[] SymOcc;
144 AffOccDesc[] AffOcc;
145 Instruction[] VS;
146 int[] DefAffOcc;
147 int[] StorageName;
148 int[] AffixApplCnt;
149 int NextSym;
150 int NextPartNum;
151 int NextRule;
152 int NextSymOcc;
153 int NextAffOcc;
154 int NextVS;
155 int NextDefAffOcc;
156 int NextStorageName;
157 int NextAffixApplCnt;
158 int MaxAffNumInRule;
159 int MaxAffNumInSym;
160 int MaxPart;
161 const abnormalError = 1;
162 const cyclicTDP = 2;
163 const notLeftDefined = 3;
164 const notEnoughMemory = 99;
165 
166 void Error(T)(int ErrorType, T Proc)
167 {
168     stdout.write("ERROR: ");
169     switch (ErrorType)
170     {
171     case abnormalError:
172         stdout.write("abnormal error ");
173         break;
174     case notEnoughMemory:
175         stdout.write("memory allocation failed ");
176         break;
177     case cyclicTDP:
178         stdout.write("TDP is cyclic...aborted\n");
179         break;
180     case notLeftDefined:
181         stdout.write("Grammar are not left defined\n");
182         break;
183     default:
184         assert(0);
185     }
186     if (ErrorType == abnormalError || ErrorType == notEnoughMemory)
187     {
188         stdout.write("in procedure ");
189         stdout.writeln(Proc);
190     }
191     throw new Exception("TODO");
192 }
193 
194 void Expand() nothrow @safe
195 {
196     size_t NewLen(size_t ArrayLen)
197     {
198         assert(ArrayLen < DIV(size_t.max, 2));
199 
200         return 2 * ArrayLen + 1;
201     }
202 
203     if (NextAffOcc >= AffOcc.length)
204     {
205         auto AffOcc1 = new AffOccDesc[NewLen(AffOcc.length)];
206 
207         for (size_t i = firstAffOcc; i < AffOcc.length; ++i)
208             AffOcc1[i] = AffOcc[i];
209         AffOcc = AffOcc1;
210     }
211     if (NextSymOcc >= SymOcc.length)
212     {
213         auto SymOcc1 = new SymOccDesc[NewLen(SymOcc.length)];
214 
215         for (size_t i = firstSymOcc; i < SymOcc.length; ++i)
216             SymOcc1[i] = SymOcc[i];
217         SymOcc = SymOcc1;
218     }
219     if (NextRule >= Rule.length)
220     {
221         auto Rule1 = new RuleBase[NewLen(Rule.length)];
222 
223         for (size_t i = firstRule; i < Rule.length; ++i)
224             Rule1[i] = Rule[i];
225         Rule = Rule1;
226     }
227     if (NextVS >= VS.length)
228     {
229         auto VS1 = new Instruction[NewLen(VS.length)];
230 
231         for (size_t i = firstVS; i < VS.length; ++i)
232             VS1[i] = VS[i];
233         VS = VS1;
234     }
235 }
236 
237 void AppAffOcc(int Params) nothrow @safe
238 {
239     if (Params != EAG.empty)
240     {
241         while (EAG.ParamBuf[Params].Affixform != EAG.nil)
242         {
243             AffOcc[NextAffOcc].ParamBufInd = Params;
244             AffOcc[NextAffOcc].SymOccInd = NextSymOcc;
245             AffOcc[NextAffOcc].AffOccNum.InRule = NextAffOcc - Rule[NextRule].AffOcc.Beg;
246             AffOcc[NextAffOcc].AffOccNum.InSym = NextAffOcc - SymOcc[NextSymOcc].AffOcc.Beg;
247             ++NextAffOcc;
248             if (NextAffOcc >= AffOcc.length)
249                 Expand;
250             ++Params;
251         }
252     }
253 }
254 
255 void AppSymOccs(EAG.Factor Factor) nothrow @safe
256 {
257     while (Factor !is null)
258     {
259         if (auto nont = cast(EAG.Nont) Factor)
260         {
261             SymOcc[NextSymOcc].SymInd = nont.Sym;
262             SymOcc[NextSymOcc].RuleInd = NextRule;
263             SymOcc[NextSymOcc].Nont = nont;
264             SymOcc[NextSymOcc].AffOcc.Beg = NextAffOcc;
265             AppAffOcc(nont.Actual.Params);
266             SymOcc[NextSymOcc].AffOcc.End = NextAffOcc - 1;
267             SymOcc[NextSymOcc].Next = Sym[nont.Sym].FirstOcc;
268             Sym[nont.Sym].FirstOcc = NextSymOcc;
269             ++NextSymOcc;
270             if (NextSymOcc >= SymOcc.length)
271                 Expand;
272         }
273         Factor = Factor.Next;
274     }
275 }
276 
277 void AppLeftSymOcc(size_t leftSym, int Params) @safe
278 {
279     import std.conv : to;
280 
281     SymOcc[NextSymOcc].SymInd = leftSym.to!int;
282     SymOcc[NextSymOcc].RuleInd = NextRule;
283     SymOcc[NextSymOcc].Nont = null;
284     SymOcc[NextSymOcc].AffOcc.Beg = NextAffOcc;
285     AppAffOcc(Params);
286     SymOcc[NextSymOcc].AffOcc.End = NextAffOcc - 1;
287     SymOcc[NextSymOcc].Next = Sym[leftSym].FirstOcc;
288     Sym[leftSym].FirstOcc = NextSymOcc;
289     ++NextSymOcc;
290     if (NextSymOcc >= SymOcc.length)
291         Expand;
292 }
293 
294 void AppEmptyRule(size_t leftSym, EAG.Rule EAGRule) @safe
295 {
296     EmptyRule A = new EmptyRule;
297 
298     Rule[NextRule] = A;
299     A.Rule = EAGRule;
300     A.SymOcc.Beg = NextSymOcc;
301     A.AffOcc.Beg = NextAffOcc;
302     if (auto opt = cast(EAG.Opt) EAGRule)
303         AppLeftSymOcc(leftSym, opt.Formal.Params);
304     else if (auto rep = cast(EAG.Rep) EAGRule)
305         AppLeftSymOcc(leftSym, rep.Formal.Params);
306     A.SymOcc.End = NextSymOcc - 1;
307     A.AffOcc.End = NextAffOcc - 1;
308     ++NextRule;
309     if (NextRule >= Rule.length)
310         Expand;
311 }
312 
313 void AppRule(EAG.Alt EAGAlt) @safe
314 {
315     OrdRule A = new OrdRule;
316 
317     Rule[NextRule] = A;
318     A.Alt = EAGAlt;
319     A.SymOcc.Beg = NextSymOcc;
320     A.AffOcc.Beg = NextAffOcc;
321     AppLeftSymOcc(EAGAlt.Up, EAGAlt.Formal.Params);
322     AppSymOccs(EAGAlt.Sub);
323     A.SymOcc.End = NextSymOcc - 1;
324     A.AffOcc.End = NextAffOcc - 1;
325     ++NextRule;
326     if (NextRule >= Rule.length)
327         Expand;
328 }
329 
330 void AppRepRule(EAG.Alt EAGAlt) @safe
331 {
332     OrdRule A = new OrdRule;
333 
334     Rule[NextRule] = A;
335     A.Alt = EAGAlt;
336     A.SymOcc.Beg = NextSymOcc;
337     A.AffOcc.Beg = NextAffOcc;
338     AppLeftSymOcc(EAGAlt.Up, EAGAlt.Formal.Params);
339     AppSymOccs(EAGAlt.Sub);
340     AppLeftSymOcc(EAGAlt.Up, EAGAlt.Actual.Params);
341     A.SymOcc.End = NextSymOcc - 1;
342     A.AffOcc.End = NextAffOcc - 1;
343     ++NextRule;
344     if (NextRule >= Rule.length)
345         Expand;
346 }
347 /**
348  * IN:  Instruktion
349  * OUT: -
350  * SEM: fügt eine Instruktion in die Datenstruktur VS ein
351  */
352 void AppVS(ref Instruction I) nothrow @safe
353 {
354     VS[NextVS] = I;
355     ++NextVS;
356     if (NextVS >= VS.length)
357         Expand;
358 }
359 
360 /**
361  * IN:  Symbol, Nummer des Affixposition
362  * OUT: boolscher Wert
363  * SEM: Test, ob Affixposition inherited ist
364  */
365 bool IsInherited(int S, int AffOccNum) @nogc nothrow @safe
366 {
367     return EAG.DomBuf[EAG.HNont[S].Sig + AffOccNum] < 0;
368 }
369 
370 /**
371  * IN:  Symbol, Nummer des Affixposition
372  * OUT: boolscher Wert
373  * SEM: Test, ob Affixposition synthesized ist
374  */
375 bool IsSynthesized(size_t S, int AffOccNum) @nogc nothrow @safe
376 {
377     return EAG.DomBuf[EAG.HNont[S].Sig + AffOccNum] > 0;
378 }
379 
380 /**
381  * IN:  Symbol, Nummern zweier Affixpositionen zum Symbol
382  * OUT: boolscher Wert
383  * SEM: Test, ob die beiden Affixpositionen orientierbar sind
384  */
385 bool IsOrientable(int S, int AffOccNum1, int AffOccNum2) @nogc nothrow @safe
386 {
387     return IsInherited(S, AffOccNum1) && IsSynthesized(S, AffOccNum2)
388         || IsInherited(S, AffOccNum2) && IsSynthesized(S, AffOccNum1);
389 }
390 
391 /**
392  * IN:  Regel
393  * OUT: boolscher Wert
394  * SEM: Test, ob eine Evaluatorregel vorliegt
395  * PRECOND: Predicates.Check muss vorher ausgewertet sein
396  */
397 bool IsEvaluatorRule(size_t R) @nogc nothrow
398 {
399     return !EAG.Pred[SymOcc[Rule[R].SymOcc.Beg].SymInd];
400 }
401 
402 /**
403  * IN:  Symbolvorkommen
404  * OUT: boolscher Wert
405  * SEM: Test, ob ein Prädikat vorliegt
406  * PRECOND: Predicates.Check muss vorher ausgewertet sein
407  */
408 bool IsPredNont(int SO) @nogc nothrow
409 {
410     return EAG.Pred[SymOcc[SO].SymInd];
411 }
412 
413 /**
414  * IN:  zwei Instruktionen aus der Visit-Sequenz
415  * OUT: boolscher Wert
416  * SEM: Test, ob zwei Instruktionnen gleich sind;
417  *      etwas optimiert für den Fall, dass einer oder beide Parameter nil ist
418  */
419 bool isEqual(Instruction I1, Instruction I2) @nogc nothrow pure @safe
420 {
421     if (I1 is null && I2 is null)
422         return true;
423     else if (I1 is null || I2 is null)
424         return false;
425     else if (cast(Visit) I1 !is null && cast(Visit) I2 !is null)
426         return (cast(Visit) I1).SymOcc == (cast(Visit) I2).SymOcc
427             && (cast(Visit) I1).VisitNo == (cast(Visit) I2).VisitNo;
428     else if (cast(Leave) I1 !is null && cast(Leave) I2 !is null)
429         return (cast(Leave) I1).VisitNo == (cast(Leave) I2).VisitNo;
430     else if (cast(Call) I1 !is null && cast(Call) I2 !is null)
431         return (cast(Call) I1).SymOcc == (cast(Call) I2).SymOcc;
432     else
433         return false;
434 }
435 
436 /**
437  * SEM: Initialisierung der SOAG-Datenstruktur; Transformation der EAG-Datenstruktur
438  */
439 void Init()
440 {
441     EAG.Alt A;
442     int a;
443     int Max;
444 
445     Sym = new SymDesc[EAG.NextHNont];
446     Rule = new RuleBase[128];
447     SymOcc = new SymOccDesc[256];
448     AffOcc = new AffOccDesc[512];
449     VS = new Instruction[512];
450     DefAffOcc = new int[EAG.NextVar];
451     AffixApplCnt = new int[EAG.NextVar];
452     StorageName = null;
453     NextSym = EAG.NextHNont;
454     NextRule = firstRule;
455     NextSymOcc = firstSymOcc;
456     NextAffOcc = firstAffOcc;
457     NextVS = firstVS;
458     NextDefAffOcc = EAG.NextVar;
459     NextStorageName = nil;
460     NextAffixApplCnt = EAG.NextVar;
461     Predicates.Check;
462     for (size_t i = EAG.firstHNont; i < EAG.NextHNont; ++i)
463         Sym[i].FirstOcc = nil;
464     foreach (i; EAG.All.bitsSet)
465     {
466         if (cast(EAG.Rep) EAG.HNont[i].Def)
467         {
468             A = EAG.HNont[i].Def.Sub;
469             while (A !is null)
470             {
471                 AppRepRule(A);
472                 A = A.Next;
473             }
474         }
475         else
476         {
477             A = EAG.HNont[i].Def.Sub;
478             while (A !is null)
479             {
480                 AppRule(A);
481                 A = A.Next;
482             }
483         }
484         if (cast(EAG.Rep) EAG.HNont[i].Def || cast(EAG.Opt) EAG.HNont[i].Def)
485             AppEmptyRule(i, EAG.HNont[i].Def);
486     }
487     MaxAffNumInRule = 0;
488     for (size_t i = firstRule; i < NextRule; ++i)
489     {
490         Max = Rule[i].AffOcc.End - Rule[i].AffOcc.Beg;
491         if (Max > MaxAffNumInRule)
492             MaxAffNumInRule = Max;
493         if (IsEvaluatorRule(i) && Max >= 0)
494         {
495             Rule[i].TDP = new BitArray[Max + 1];
496             Rule[i].DP = new BitArray[Max + 1];
497             for (a = firstAffOccNum; a <= Max; ++a)
498             {
499                 Rule[i].TDP[a] = BitArray();
500                 Rule[i].TDP[a].length = Max + 1 + 1;
501                 Rule[i].DP[a] = BitArray();
502                 Rule[i].DP[a].length = Max + 1 + 1;
503             }
504         }
505     }
506     MaxAffNumInSym = 0;
507     NextPartNum = firstPartNum;
508     foreach (i; EAG.All.bitsSet)
509     {
510         Max = SymOcc[Sym[i].FirstOcc].AffOcc.End - SymOcc[Sym[i].FirstOcc].AffOcc.Beg;
511         Sym[i].AffPos.Beg = NextPartNum;
512         NextPartNum = NextPartNum + Max;
513         Sym[i].AffPos.End = NextPartNum;
514         ++NextPartNum;
515         if (Max > MaxAffNumInSym)
516             MaxAffNumInSym = Max;
517         Sym[i].MaxPart = 0;
518     }
519     PartNum = new int[NextPartNum];
520     MaxPart = 0;
521     for (size_t i = EAG.firstVar; i < EAG.NextVar; ++i)
522     {
523         DefAffOcc[i] = -1;
524         AffixApplCnt[i] = 0;
525     }
526 }
527 
528 static this() @safe
529 {
530     import log : info;
531 
532     info!"SOAG-Evaluatorgenerator 1.06 dk 14.03.98";
533 }