epsilon.soag.partition source code

1 module epsilon.soag.partition;
2 
3 import EAG = epsilon.eag;
4 import log;
5 import runtime;
6 import ALists = epsilon.soag.alists;
7 import Protocol = epsilon.soag.protocol;
8 import SOAG = epsilon.soag.soag;
9 import std.bitmanip : BitArray;
10 import std.stdio;
11 
12 const unor = -1;
13 const nil = 0;
14 const element = 1;
15 const computeDPandIDP = 1;
16 const dynTopSort = 2;
17 const firstVarBuf = 0;
18 const firstChangeBuf = 0;
19 
20 struct VarBufDesc
21 {
22     int AffOcc;
23     int Sym;
24     int Num;
25     int VarInd;
26 }
27 
28 struct ChangeBufDesc
29 {
30     int RuleInd;
31     int AffOccInd1;
32     int AffOccInd2;
33 }
34 
35 VarBufDesc[] VarBuf;
36 int NextVarBuf;
37 ChangeBufDesc[] ChangeBuf;
38 int NextChangeBuf;
39 int[][] DS;
40 int[] Deg;
41 int Phase;
42 bool CyclicTDP;
43 bool OAG;
44 ALists.AList NUV;
45 ALists.AList MarkedEdges;
46 ALists.AList LastCur;
47 BitArray Cur;
48 BitArray Leave;
49 BitArray New;
50 int Seperator;
51 
52 void Expand() nothrow @safe
53 {
54     size_t NewLen(size_t ArrayLen)
55     {
56         assert(ArrayLen < DIV(size_t.max, 2));
57 
58         return 2 * ArrayLen + 1;
59     }
60 
61     if (NextVarBuf >= VarBuf.length)
62     {
63         auto VarBuf1 = new VarBufDesc[NewLen(VarBuf.length)];
64 
65         for (size_t i = firstVarBuf; i < VarBuf.length; ++i)
66             VarBuf1[i] = VarBuf[i];
67         VarBuf = VarBuf1;
68     }
69     if (NextChangeBuf >= ChangeBuf.length)
70     {
71         auto ChangeBuf1 = new ChangeBufDesc[NewLen(ChangeBuf.length)];
72 
73         for (size_t i = firstChangeBuf; i < ChangeBuf.length; ++i)
74             ChangeBuf1[i] = ChangeBuf[i];
75         ChangeBuf = ChangeBuf1;
76     }
77 }
78 
79 void Push(ref ALists.AList Stack, int S, int A1, int A2) nothrow pure @safe
80 {
81     ALists.Append(Stack, S);
82     ALists.Append(Stack, A1);
83     ALists.Append(Stack, A2);
84 }
85 
86 /**
87  * IN:  Regel, zwei Affixparameter
88  * OUT: boolscher Wert
89  * SEM: Test, ob eine Abhängigkeit zwischen den beiden Affixparametern besteht
90  */
91 bool EdgeInTDP(int R, int A1, int A2) @nogc nothrow
92 {
93     return SOAG.Rule[R].TDP[SOAG.AffOcc[A1].AffOccNum.InRule][SOAG.AffOcc[A2].AffOccNum.InRule];
94 }
95 
96 /**
97  * IN:  Regel, 2 Affixparameter
98  * OUT: -
99  * SEM: Fügt ein Tripel in das Feld ChangeBuf ein - Speicherung einer in TDP eingefügten Abhängigkeit.
100  */
101 void AddTDPChange(int R, int AO1, int AO2) nothrow @safe
102 {
103     ChangeBuf[NextChangeBuf].RuleInd = R;
104     ChangeBuf[NextChangeBuf].AffOccInd1 = AO1;
105     ChangeBuf[NextChangeBuf].AffOccInd2 = AO2;
106     ++NextChangeBuf;
107     if (NextChangeBuf >= ChangeBuf.length)
108         Expand;
109 }
110 
111 /**
112  * IN:  Index in ChangeBuf
113  * OUT: -
114  * SEM: Rücksetzen,der in ChangeBuf gespeicherten Abhängigkeiten in den TDP's
115  */
116 void ResetTDPChanges(int End) @nogc nothrow
117 {
118     for (int i = firstChangeBuf; i <= End; ++i)
119     {
120         SOAG.Rule[ChangeBuf[i].RuleInd].TDP[SOAG.AffOcc[ChangeBuf[i].AffOccInd1].AffOccNum.InRule]
121             [SOAG.AffOcc[ChangeBuf[i].AffOccInd2].AffOccNum.InRule] = false;
122     }
123 }
124 
125 /**
126  * IN:  Regel; zwei Affixparameter
127  * OUT: -
128  * SEM: fügt die Kante (AO1,AO2) in den TDP ein und bildet den transitiven Abschluss TDP+;
129  *      die eingefügte Abhängigkeit lautet: AO2 hängt ab von AO1, AO1->AO2 im Sinne des Datenflusses;
130  *      markiert alle neu eingefügten Kanten, indem sie auf einen Stack gelegt werden
131  * SEF: NUV: AList ist global
132  * MarkedEdges falls Phase = computeDPandIDP
133  * ChangeBuf, CyclicTDP falls Phase = dynTopSort
134  */
135 void AddTDPTrans(int R, int AO1, int AO2)
136 {
137     int AO3;
138     int AO4;
139     int AN1;
140     int AN2;
141     int AN3;
142     int AN4;
143 
144     ALists.Reset(NUV);
145     if (!EdgeInTDP(R, AO1, AO2))
146     {
147         AN1 = SOAG.AffOcc[AO1].AffOccNum.InRule;
148         AN2 = SOAG.AffOcc[AO2].AffOccNum.InRule;
149         for (AO4 = SOAG.Rule[R].AffOcc.Beg; AO4 <= SOAG.Rule[R].AffOcc.End; ++AO4)
150         {
151             AN4 = SOAG.AffOcc[AO4].AffOccNum.InRule;
152             if ((AN4 == AN2 || SOAG.Rule[R].TDP[AN2][AN4]) && !SOAG.Rule[R].TDP[AN1][AN4])
153                 ALists.Append(NUV, AO4);
154         }
155         for (AO3 = SOAG.Rule[R].AffOcc.Beg; AO3 <= SOAG.Rule[R].AffOcc.End; ++AO3)
156         {
157             AN3 = SOAG.AffOcc[AO3].AffOccNum.InRule;
158             if ((AN3 == AN1 || SOAG.Rule[R].TDP[AN3][AN1]) && !SOAG.Rule[R].TDP[AN3][AN2])
159             {
160                 for (size_t i = ALists.firstIndex; i <= NUV.Last; ++i)
161                 {
162                     AO4 = NUV.Elem[i];
163                     if (!EdgeInTDP(R, AO3, AO4))
164                     {
165                         SOAG.Rule[R].TDP[AN3][SOAG.AffOcc[AO4].AffOccNum.InRule] = true;
166                         if (SOAG.AffOcc[AO3].SymOccInd == SOAG.AffOcc[AO4].SymOccInd
167                                 && !SOAG.IsPredNont(SOAG.AffOcc[AO3].SymOccInd))
168                         {
169                             Push(MarkedEdges, SOAG.SymOcc[SOAG.AffOcc[AO3].SymOccInd].SymInd,
170                                     SOAG.AffOcc[AO3].AffOccNum.InSym,
171                                     SOAG.AffOcc[AO4].AffOccNum.InSym);
172                         }
173                         if (Phase == dynTopSort)
174                             AddTDPChange(R, AO3, AO4);
175                     }
176                 }
177             }
178             if (SOAG.Rule[R].TDP[AN3][AN3])
179             {
180                 if (Phase == computeDPandIDP)
181                 {
182                     Protocol.output.write("...a cyclic affix dependence was found!\n");
183                     Protocol.WriteRule(R);
184                     Protocol.output.writeln;
185                     Protocol.WriteAffOcc(AO3);
186                     Protocol.output.writeln;
187                     Protocol.output.write("Preorder  of ");
188                     Protocol.WriteAffOcc(AO1);
189                     Protocol.output.writeln;
190                     Protocol.output.write("Postorder of ");
191                     Protocol.WriteAffOcc(AO2);
192                     Protocol.output.writeln;
193                     Protocol.output.writeln;
194                     SOAG.Error(SOAG.cyclicTDP, "eSOAGVSGen.AddTDPTrans");
195                 }
196                 else if (Phase == dynTopSort)
197                 {
198                     CyclicTDP = true;
199                 }
200             }
201         }
202     }
203 }
204 
205 /**
206  * IN:  Affixparameter, Affixform, Affixparameter definierend oder applizierend ?
207  * OUT: -
208  * SEM: ordnet im Feld VarBuf[] jeder Variablen, die im Baum der Affixform gefunden wird,
209  *      den zugehörigen Affixparameter, sowie das Variablensymbol zu
210  * SEF: VarBuf[], NextVarBuf
211  */
212 void SetAffOccforVars(int AO, int Affixform, bool isDef) nothrow @safe
213 {
214     int MA;
215     if (Affixform < 0)
216     {
217         if (NextVarBuf + 1 >= VarBuf.length)
218             Expand;
219         VarBuf[NextVarBuf].AffOcc = AO;
220         if (isDef)
221             VarBuf[NextVarBuf].Sym = -EAG.Var[-Affixform].Sym;
222         else
223             VarBuf[NextVarBuf].Sym = EAG.Var[-Affixform].Sym;
224         VarBuf[NextVarBuf].Num = EAG.Var[-Affixform].Num;
225         VarBuf[NextVarBuf].VarInd = -Affixform;
226         ++NextVarBuf;
227     }
228     else if (EAG.MAlt[EAG.NodeBuf[Affixform]].Arity > 0)
229     {
230         for (MA = 1; MA <= EAG.MAlt[EAG.NodeBuf[Affixform]].Arity; ++MA)
231             SetAffOccforVars(AO, EAG.NodeBuf[Affixform + MA], isDef);
232     }
233 }
234 
235 /**
236  * IN:  Regel
237  * OUT: -
238  * SEM: berechnet für alle Affixvariablen einer Regel den Affixparameter des zugehörigen definierenden Affixes
239  *      und speichert  diesen in DefAffOcc[]
240  * SEF: Zugriffe auf VarBuf[]
241  */
242 void ComputeDefAffOcc(int R)
243 {
244     EAG.ScopeDesc Scope;
245 
246     if (auto ordRule = cast(SOAG.OrdRule) SOAG.Rule[R])
247     {
248         Scope = ordRule.Alt.Scope;
249     }
250     else if (auto emptyRule = cast(SOAG.EmptyRule) SOAG.Rule[R])
251     {
252         EAG.Rule EAGRule = emptyRule.Rule;
253 
254         if (auto opt = cast(EAG.Opt) EAGRule)
255             Scope = opt.Scope;
256         else if (auto rep = cast(EAG.Rep) EAGRule)
257             Scope = rep.Scope;
258     }
259     foreach (V; Scope.Beg .. Scope.End)
260     {
261         bool Found;
262         int i = firstVarBuf - 1;
263 
264         do
265         {
266             ++i;
267             Found = EAG.Var[V].Sym == -VarBuf[i].Sym && EAG.Var[V].Num == VarBuf[i].Num;
268         }
269         while (!Found && i < NextVarBuf - 1);
270         if (Found)
271         {
272             SOAG.DefAffOcc[V] = VarBuf[i].AffOcc;
273         }
274         else
275         {
276             writeln(EAG.Var[V].Pos);
277             SOAG.Error(SOAG.notLeftDefined, "epsilon.soag.partition.ComputeDefAffOcc");
278         }
279     }
280 }
281 
282 /**
283  * IN:  Regel
284  * OUT: -
285  * SEM: Berechnet in AffixApplCnt die Anzahl der Applikationen eines Affixes,
286  *      außerdem wird für jeden Vergleich eine Abhängigkeit in den DP aufgenommen
287  * PRE: DefAffOcc[] muss berechnet sein
288  */
289 void ComputeAffixApplCnt(int R) @nogc nothrow
290 {
291     EAG.ScopeDesc Scope;
292 
293     if (auto ordRule = cast(SOAG.OrdRule) SOAG.Rule[R])
294     {
295         Scope = ordRule.Alt.Scope;
296     }
297     else if (auto emptyRule = cast(SOAG.EmptyRule) SOAG.Rule[R])
298     {
299         EAG.Rule EAGRule = emptyRule.Rule;
300 
301         if (auto opt = cast(EAG.Opt) EAGRule)
302             Scope = opt.Scope;
303         else if (auto rep = cast(EAG.Rep) EAGRule)
304             Scope = rep.Scope;
305     }
306     foreach (A; Scope.Beg .. Scope.End)
307     {
308         int i = firstVarBuf;
309 
310         while (i < NextVarBuf)
311         {
312             if (EAG.Var[A].Sym == -VarBuf[i].Sym
313                     && (EAG.Var[A].Num == VarBuf[i].Num && SOAG.DefAffOcc[A] != VarBuf[i].AffOcc
314                         || EAG.Var[A].Num == -VarBuf[i].Num && SOAG.DefAffOcc[VarBuf[i].VarInd] == VarBuf[i].AffOcc))
315             {
316                 const AN = VarBuf[i].AffOcc - SOAG.Rule[R].AffOcc.Beg;
317                 const DAN = SOAG.DefAffOcc[A] - SOAG.Rule[R].AffOcc.Beg;
318 
319                 SOAG.Rule[R].DP[DAN][AN] = true;
320                 ++SOAG.AffixApplCnt[A];
321             }
322             else if (EAG.Var[A].Sym == VarBuf[i].Sym && EAG.Var[A].Num == VarBuf[i].Num)
323             {
324                 ++SOAG.AffixApplCnt[A];
325             }
326             ++i;
327         }
328     }
329 }
330 
331 /**
332  * SEM: Initialisierung des Abhängigkeitsgraphen für jeden Affixparamter
333  *      aller Regeln aus der Spezifikationsdatenstruktur
334  * SEF: auf alle globalen DSen
335  */
336 void ComputeDP()
337 {
338     int R;
339     int AO;
340     int SO;
341     int i;
342     int j;
343     int PBI;
344     int FirstSOVar;
345 
346     Phase = computeDPandIDP;
347     ALists.New(MarkedEdges, 256);
348     ALists.New(NUV, 56);
349     for (R = SOAG.firstRule; R < SOAG.NextRule; ++R)
350     {
351         if (SOAG.IsEvaluatorRule(R))
352         {
353             for (SO = SOAG.Rule[R].SymOcc.Beg; SO <= SOAG.Rule[R].SymOcc.End; ++SO)
354             {
355                 FirstSOVar = NextVarBuf;
356                 for (AO = SOAG.SymOcc[SO].AffOcc.Beg; AO <= SOAG.SymOcc[SO].AffOcc.End;
357                         ++AO)
358                 {
359                     PBI = SOAG.AffOcc[AO].ParamBufInd;
360                     SetAffOccforVars(AO, EAG.ParamBuf[PBI].Affixform, EAG.ParamBuf[PBI].isDef);
361                 }
362                 if (SOAG.IsPredNont(SO))
363                 {
364                     for (i = FirstSOVar; i < NextVarBuf; ++i)
365                     {
366                         for (j = FirstSOVar; j < NextVarBuf; ++j)
367                         {
368                             if (VarBuf[j].Sym < 0 && VarBuf[i].Sym > 0)
369                             {
370                                 AddTDPTrans(R, VarBuf[i].AffOcc, VarBuf[j].AffOcc);
371                                 SOAG.Rule[R].DP[SOAG.AffOcc[VarBuf[i].AffOcc].AffOccNum.InRule]
372                                     [SOAG.AffOcc[VarBuf[j].AffOcc].AffOccNum.InRule] = true;
373                             }
374                         }
375                     }
376                 }
377             }
378             ComputeDefAffOcc(R);
379             ComputeAffixApplCnt(R);
380             if (SOAG.Rule[R].AffOcc.End >= SOAG.Rule[R].AffOcc.Beg)
381             {
382                 for (i = firstVarBuf; i < NextVarBuf; ++i)
383                 {
384                     if (VarBuf[i].Sym > 0)
385                     {
386                         AddTDPTrans(R, SOAG.DefAffOcc[VarBuf[i].VarInd], VarBuf[i].AffOcc);
387                         SOAG.Rule[R].DP[SOAG.AffOcc[SOAG.DefAffOcc[VarBuf[i].VarInd]].AffOccNum.InRule]
388                             [SOAG.AffOcc[VarBuf[i].AffOcc].AffOccNum.InRule] = true;
389                     }
390                 }
391                 NextVarBuf = firstVarBuf;
392             }
393         }
394     }
395 }
396 
397 /**
398  * SEM: bildet in TDP alle induzierten Abhängigkeiten solange MarkedEdges nicht leer ist
399  *      und die Ausgabeinvariante TDP = ind(TDP) gilt.
400  * SEF: MarkedEdges, TDP
401  */
402 void ComputeInducedTDP()
403 {
404     int SO;
405     int AN1;
406     int AN2;
407     int AO1;
408     int AO2;
409     while (MarkedEdges.Last >= ALists.firstIndex)
410     {
411         AN2 = MarkedEdges.Elem[MarkedEdges.Last];
412         ALists.Delete(MarkedEdges, MarkedEdges.Last);
413         AN1 = MarkedEdges.Elem[MarkedEdges.Last];
414         ALists.Delete(MarkedEdges, MarkedEdges.Last);
415         SO = MarkedEdges.Elem[MarkedEdges.Last];
416         ALists.Delete(MarkedEdges, MarkedEdges.Last);
417         SO = SOAG.Sym[SO].FirstOcc;
418         while (SO != SOAG.nil)
419         {
420             AO1 = SOAG.SymOcc[SO].AffOcc.Beg + AN1;
421             AO2 = SOAG.SymOcc[SO].AffOcc.Beg + AN2;
422             AddTDPTrans(SOAG.SymOcc[SO].RuleInd, AO1, AO2);
423             SO = SOAG.SymOcc[SO].Next;
424         }
425     }
426 }
427 
428 /**
429  * SEM: bildet in TDP alle induzierten Abhängigkeiten solange MarkedEdges nicht leer ist
430  *      und die Ausgabeinvariante TDP = ind(TDP) gilt, damit ist dann TDP = IDP+
431  * SEF: -
432  */
433 void ComputeIDPTrans()
434 {
435     ComputeInducedTDP;
436 }
437 
438 /**
439  * IN:  Affixpositionsnummern a und b, Symbol
440  * OUT: Liste von Paaren von Affixpositionsnummern des Symbols X
441  * SEM: findet für zwei Affixpositionen eines Symbols eine Orientierung,
442  *      fügt diese in alle Regelabhängigkeitsgraphen ein und liefert die Liste
443  *      aller bei der transitiven Vervollständigung neu entstandenen Abhängigkeiten zurück
444  * SEF: auf ChangeBuf[]
445  */
446 void Orient(int a, int b, int X, ref BitArray New)
447 {
448     int SO;
449     int i;
450     int a1;
451     int b1;
452     int AO1;
453     int AO2;
454 
455     New[] = false;
456     CyclicTDP = false;
457     NextChangeBuf = firstChangeBuf;
458     SO = SOAG.Sym[X].FirstOcc;
459     AddTDPTrans(SOAG.SymOcc[SO].RuleInd, SOAG.SymOcc[SO].AffOcc.Beg + b,
460             SOAG.SymOcc[SO].AffOcc.Beg + a);
461     ComputeInducedTDP;
462     if (CyclicTDP)
463     {
464         CyclicTDP = false;
465         OAG = false;
466         ResetTDPChanges(NextChangeBuf - 1);
467         NextChangeBuf = firstChangeBuf;
468         AddTDPTrans(SOAG.SymOcc[SO].RuleInd, SOAG.SymOcc[SO].AffOcc.Beg + a,
469                 SOAG.SymOcc[SO].AffOcc.Beg + b);
470         ComputeInducedTDP;
471     }
472     if (CyclicTDP)
473     {
474         error!"grammar is not SOAG";
475         SOAG.Error(SOAG.cyclicTDP, "eSOAGVSGen.Orient");
476     }
477     for (i = firstChangeBuf; i < NextChangeBuf; ++i)
478     {
479         AO1 = ChangeBuf[i].AffOccInd1;
480         AO2 = ChangeBuf[i].AffOccInd2;
481         if (SOAG.AffOcc[AO1].SymOccInd == SOAG.AffOcc[AO2].SymOccInd
482                 && SOAG.SymOcc[SOAG.AffOcc[AO1].SymOccInd].SymInd == X)
483         {
484             a1 = SOAG.AffOcc[AO1].AffOccNum.InSym;
485             b1 = SOAG.AffOcc[AO2].AffOccNum.InSym;
486             if (SOAG.IsOrientable(X, a1, b1))
487                 New[a1 * Seperator + b1] = true;
488         }
489     }
490 }
491 
492 /**
493  * IN:  Symbol
494  * OUT: -
495  * SEM: dynamisches topologisches Sortieren der Affxipositionsabhängigkeiten
496  *      unter Heranführung an eine erfolgreiche bzw. unmittelbar erfolgreiche Orientierung
497  * SEF: DS[][]
498  */
499 void DynTopSortSym(int X)
500 {
501     import std.conv : to;
502 
503     int XmaxAff;
504     int AO1;
505     int AO2;
506     int SO;
507     int Part = 0;
508     int i;
509     int a1;
510     int a;
511     int b;
512     int c;
513     int d;
514 
515     XmaxAff = SOAG.SymOcc[SOAG.Sym[X].FirstOcc].AffOcc.End - SOAG.SymOcc[SOAG.Sym[X].FirstOcc].AffOcc.Beg;
516     for (a = 0; a <= XmaxAff; ++a)
517         for (b = 0; b <= XmaxAff; ++b)
518             DS[a][b] = nil;
519     SO = SOAG.Sym[X].FirstOcc;
520     while (SO != SOAG.nil)
521     {
522         for (AO1 = SOAG.SymOcc[SO].AffOcc.Beg; AO1 <= SOAG.SymOcc[SO].AffOcc.End; ++AO1)
523         {
524             for (AO2 = SOAG.SymOcc[SO].AffOcc.Beg; AO2 <= SOAG.SymOcc[SO].AffOcc.End; ++AO2)
525             {
526                 if (EdgeInTDP(SOAG.SymOcc[SO].RuleInd, AO1, AO2))
527                 {
528                     a = SOAG.AffOcc[AO1].AffOccNum.InSym;
529                     b = SOAG.AffOcc[AO2].AffOccNum.InSym;
530                     if (SOAG.IsOrientable(X, a, b))
531                         DS[a][b] = element;
532                 }
533             }
534         }
535         SO = SOAG.SymOcc[SO].Next;
536     }
537     for (a = 0; a <= XmaxAff; ++a)
538     {
539         Deg[a] = 0;
540         for (b = 0; b <= XmaxAff; ++b)
541         {
542             if (DS[a][b] == element)
543             {
544                 ++Deg[a];
545             }
546             else if (DS[b][a] == nil && SOAG.IsOrientable(X, a, b))
547             {
548                 DS[a][b] = unor;
549                 DS[b][a] = unor;
550             }
551         }
552     }
553     Cur[] = false;
554     Leave[] = false;
555     for (a = 0; a <= XmaxAff; ++a)
556     {
557         if (Deg[a] == 0)
558         {
559             if (SOAG.IsSynthesized(X, a))
560                 Cur[a] = true;
561             else if (SOAG.IsInherited(X, a))
562                 Leave[a] = true;
563         }
564     }
565     trace!"compute partition for symbol %s"(EAG.HNontRepr(X));
566     trace!"initially: Cur=%s, Leave=%s"(Cur, Leave);
567     do
568     {
569         ALists.Reset(LastCur);
570         foreach (size_t elem; Cur.bitsSet)
571             ALists.Append(LastCur, elem.to!int);
572         for (b = 0; b <= XmaxAff; ++b)
573         {
574             for (a1 = ALists.firstIndex; a1 <= LastCur.Last; ++a1)
575             {
576                 a = LastCur.Elem[a1];
577                 if (Cur[a] && DS[a][b] == unor)
578                 {
579                     Orient(a, b, X, New);
580                     foreach (size_t elem; New.bitsSet)
581                     {
582                         c = DIV(elem, Seperator).to!int;
583                         d = MOD(elem, Seperator).to!int;
584                         DS[c][d] = element;
585                         ++Deg[c];
586                         if (DS[d][c] == unor)
587                             DS[d][c] = nil;
588                         if (Cur[c])
589                             Cur[c] = false;
590                         else if (Deg[c] == 1)
591                             Leave[c] = false;
592                     }
593                 }
594             }
595         }
596         ++Part;
597         trace!"partition %s: Cur=%s, Leave=%s"(Part, Cur, Leave);
598         foreach (size_t elem; Cur.bitsSet)
599         {
600             SOAG.PartNum[SOAG.Sym[X].AffPos.Beg + elem] = Part;
601             for (b = 0; b <= XmaxAff; ++b)
602             {
603                 if (DS[b][elem] == element)
604                 {
605                     --Deg[b];
606                     if (Deg[b] == 0)
607                         Leave[b] = true;
608                 }
609             }
610         }
611         trace!"afterwards: Cur=%s, Leave=%s"(Cur, Leave);
612 
613         BitArray tmp = Cur;
614 
615         Cur = Leave;
616         Leave = tmp;
617         Leave[] = false;
618     }
619     while (Cur.count > 0);
620     if (SOAG.Sym[X].MaxPart < Part)
621         SOAG.Sym[X].MaxPart = Part;
622     if (SOAG.MaxPart < Part)
623         SOAG.MaxPart = Part;
624 }
625 
626 /**
627  * SEM: dynamisches topologisches Sortieren aller Symbole der Grammatik
628  */
629 void DynTopSort()
630 {
631     Cur = BitArray();
632     Cur.length = SOAG.MaxAffNumInSym + 1;
633     Leave = BitArray();
634     Leave.length = SOAG.MaxAffNumInSym + 1;
635     Deg = new int[SOAG.MaxAffNumInSym + 1];
636     DS = new int[][SOAG.MaxAffNumInSym + 1];
637     foreach (ref row; DS)
638         row = new int[SOAG.MaxAffNumInSym + 1];
639     New = BitArray();
640     New.length = (SOAG.MaxAffNumInSym + 1) * (SOAG.MaxAffNumInSym + 1) + 1;
641     Seperator = SOAG.MaxAffNumInSym + 1;
642     ALists.New(LastCur, 16);
643     for (int S = EAG.firstHNont; S < EAG.NextHNont; ++S)
644     {
645         if (!EAG.Pred[S] && EAG.All[S])
646             DynTopSortSym(S);
647     }
648 }
649 
650 /**
651  * SEM: Treiber
652  */
653 void Compute()
654 {
655     const undefined = -1;
656 
657     SOAG.Init;
658     // initialize partition number of each affix position to finally enforce that it's defined
659     SOAG.PartNum[SOAG.firstPartNum .. SOAG.NextPartNum] = undefined;
660     VarBuf = new VarBufDesc[50];
661     ChangeBuf = new ChangeBufDesc[64];
662     NextVarBuf = firstVarBuf;
663     NextChangeBuf = firstChangeBuf;
664     OAG = true;
665     Phase = computeDPandIDP;
666     ComputeDP;
667     ComputeIDPTrans;
668     Phase = dynTopSort;
669     DynTopSort;
670     if (OAG)
671         info!"grammar is SOAG";
672     else
673         info!"grammar is SOAG (backtracked)";
674 }