epsilon.soag.visitseq source code

1 module epsilon.soag.visitseq;
2 
3 import EAG = epsilon.eag;
4 import runtime;
5 import hash = epsilon.soag.hash;
6 import SOAG = epsilon.soag.soag;
7 import std.range;
8 
9 const noVisit = -1;
10 int[] InDeg;
11 
12 /**
13  * IN:  -
14  * OUT: -
15  * SEM: Berechnung der maximalen Visits in Sym[X].MaxPart
16  *      und der Visit-Nummer der Affixpositionen in PartNum[AffPos].
17  */
18 void ComputeVisitNo()
19 {
20     import std.conv : to;
21     import std.exception : enforce;
22     import std.format: format;
23 
24     int AP;
25     int MaxPart;
26     int PartNum;
27 
28     foreach (S; EAG.All.bitsSet)
29         if (!EAG.Pred[S])
30         {
31             MaxPart = DIV(SOAG.Sym[S].MaxPart + 1, 2).to!int;
32             SOAG.Sym[S].MaxPart = MaxPart;
33             for (AP = SOAG.Sym[S].AffPos.Beg; AP <= SOAG.Sym[S].AffPos.End; ++AP)
34             {
35                 enforce(SOAG.PartNum[AP] >= 0,
36                         format!"partition number for affix position %d at symbol %s not determined"
37                             (AP, EAG.HNontRepr(S)));
38 
39                 PartNum = DIV(SOAG.PartNum[AP] + 1, 2).to!int;
40                 SOAG.PartNum[AP] = MaxPart - PartNum + 1;
41             }
42         }
43 }
44 
45 /**
46  * IN:  Affixparameter
47  * OUT: Visit-Nummer des Affixparameters
48  * SEM: Auslesen der Visit-Nummer des Affixparameters, Schnittstellenprozedur
49  */
50 int GetVisitNo(int AP) @nogc nothrow @safe
51 {
52     const S = SOAG.SymOcc[SOAG.AffOcc[AP].SymOccInd].SymInd;
53 
54     return SOAG.PartNum[SOAG.Sym[S].AffPos.Beg + SOAG.AffOcc[AP].AffOccNum.InSym];
55 }
56 
57 /**
58  * IN:  Symbolvorkommen, die keine Prädikate sind
59  * OUT: die maximale Visit-Nummer dieses Symbols
60  * SEM: Auslesen der maximalen Visit-Nummer des Symbolvorkommens, Schnittstellenprozedur
61  */
62 int GetMaxVisitNo(int SO) @nogc nothrow @safe
63 {
64     return SOAG.Sym[SOAG.SymOcc[SO].SymInd].MaxPart;
65 }
66 
67 /**
68  * IN:  aktueller Visit, Regel, aktuller Visit, Symbolvorkommen, Visitnummer
69  * OUT: Nummer des Eintrages in der Visitsequenz der Regel
70  * SEM: Durchsucht die Visitsequenz nach dem Visit des Symbolvorkommens mit entsprechender Besuchsnummer.
71  */
72 int GetNextVisit(int V, int R, int SO, int VN) @nogc nothrow @safe
73 {
74     while (V <= SOAG.Rule[R].VS.End)
75     {
76         if (auto visit = cast(SOAG.Visit) SOAG.VS[V])
77         {
78             if (visit.SymOcc == SO && visit.VisitNo == VN)
79                 return V;
80         }
81         else if (auto call = cast(SOAG.Call) SOAG.VS[V])
82         {
83             if (call.SymOcc == SO)
84                 return V;
85         }
86         else if (auto leave = cast(SOAG.Leave) SOAG.VS[V])
87         {
88             if (leave.VisitNo == VN && SOAG.Rule[R].SymOcc.Beg == SO)
89                 return V;
90         }
91         ++V;
92     }
93     return noVisit;
94 }
95 
96 /**
97  * IN:  Regel, Symbolvorkommen, Visitnummer
98  * OUT: Nummer des Eintrages in der Visitsequenz der Regel
99  * SEM: Durchsucht die Visitsequenz nach dem Visit des Symbolvorkommens mit entsprechender Besuchsnummer.
100  */
101 int GetVisit(int R, int SO, int VN) @nogc nothrow @safe
102 {
103     return GetNextVisit(SOAG.Rule[R].VS.Beg, R, SO, VN);
104 }
105 
106 /**
107  * IN:  Affixparameter
108  * OUT: Instruktion oder NIL für NOP
109  * SEM: Erzeugung einer Instruktion in Abhäengigkeit vom übergebenen Affixparameter
110  */
111 SOAG.Instruction MapVS(int AO) nothrow
112 {
113     if (!EAG.ParamBuf[SOAG.AffOcc[AO].ParamBufInd].isDef)
114         return null;
115 
116     const SO = SOAG.AffOcc[AO].SymOccInd;
117 
118     if (SOAG.IsPredNont(SO))
119     {
120         SOAG.Call Call = new SOAG.Call;
121 
122         Call.SymOcc = SO;
123         return Call;
124     }
125 
126     const R = SOAG.SymOcc[SO].RuleInd;
127 
128     if (SOAG.Rule[R].SymOcc.Beg == SO)
129     {
130         if (GetVisitNo(AO) - 1 > 0)
131         {
132             SOAG.Leave Leave = new SOAG.Leave;
133 
134             Leave.VisitNo = GetVisitNo(AO) - 1;
135             return Leave;
136         }
137         return null;
138     }
139     else
140     {
141         SOAG.Visit Visit = new SOAG.Visit;
142 
143         Visit.SymOcc = SO;
144         Visit.VisitNo = GetVisitNo(AO);
145         return Visit;
146     }
147 }
148 
149 /**
150  * IN:  Symbolvorkommen
151  * OUT: Instruktion
152  * SEM: Berechnung der abschliessenden Instruktionen für ein Symbolvorkommen
153  */
154 SOAG.Instruction CompleteTraversal(int SO) nothrow
155 {
156     if (SOAG.IsPredNont(SO))
157     {
158         SOAG.Call Call = new SOAG.Call;
159 
160         Call.SymOcc = SO;
161         return Call;
162     }
163 
164     const R = SOAG.SymOcc[SO].RuleInd;
165 
166     if (SOAG.Rule[R].SymOcc.Beg == SO)
167     {
168         SOAG.Leave Leave = new SOAG.Leave;
169 
170         Leave.VisitNo = GetMaxVisitNo(SO);
171         return Leave;
172     }
173 
174     SOAG.Visit Visit = new SOAG.Visit;
175 
176     Visit.SymOcc = SO;
177     Visit.VisitNo = GetMaxVisitNo(SO);
178     return Visit;
179 }
180 
181 /**
182  * IN:  Regel
183  * OUT: -
184  * SEM: topologische Sortierung der Affixparameter anhand ihrer Abhängigkeiten
185  */
186 void TopSort(int R)
187 {
188     int AO;
189     int AN;
190     int BO;
191     int BN;
192     SOAG.Instruction Instr;
193     int[] ZeroInDeg;
194 
195     for (BO = SOAG.Rule[R].AffOcc.End; BO >= SOAG.Rule[R].AffOcc.Beg; --BO)
196     {
197         BN = SOAG.AffOcc[BO].AffOccNum.InRule;
198         InDeg[BN] = 0;
199         for (AO = SOAG.Rule[R].AffOcc.Beg; AO <= SOAG.Rule[R].AffOcc.End; ++AO)
200         {
201             AN = SOAG.AffOcc[AO].AffOccNum.InRule;
202             if (SOAG.Rule[R].TDP[AN][BN])
203                 ++InDeg[BN];
204         }
205         if (InDeg[BN] == 0)
206             ZeroInDeg ~= BO;
207     }
208     while (!ZeroInDeg.empty)
209     {
210         AO = ZeroInDeg.back;
211         ZeroInDeg.popBack;
212         Instr = MapVS(AO);
213         AN = SOAG.AffOcc[AO].AffOccNum.InRule;
214         if (!hash.IsIn(Instr))
215         {
216             hash.Enter(Instr);
217             SOAG.AppVS(Instr);
218         }
219         for (BO = SOAG.Rule[R].AffOcc.End; BO >= SOAG.Rule[R].AffOcc.Beg; --BO)
220         {
221             BN = SOAG.AffOcc[BO].AffOccNum.InRule;
222             if (SOAG.Rule[R].TDP[AN][BN])
223             {
224                 --InDeg[BN];
225                 if (InDeg[BN] == 0)
226                     ZeroInDeg ~= BO;
227             }
228         }
229     }
230 }
231 
232 /**
233  * SEM: Generierung der Visit-Sequenzen
234  */
235 void Generate()
236 {
237     int SO;
238     SOAG.Instruction Instr;
239 
240     ComputeVisitNo;
241     // hash.Init(SOAG.MaxAffNumInRule); // does not work if (MaxAffNumInRule == 0)
242     hash.Init(SOAG.MaxAffNumInRule + 1);
243     InDeg = new int[SOAG.MaxAffNumInRule + 1];
244     for (int R = SOAG.firstRule; R < SOAG.NextRule; ++R)
245     {
246         SOAG.Rule[R].VS.Beg = SOAG.NextVS;
247         if (SOAG.IsEvaluatorRule(R))
248         {
249             hash.Reset;
250             TopSort(R);
251             for (SO = SOAG.Rule[R].SymOcc.Beg + 1; SO <= SOAG.Rule[R].SymOcc.End; ++SO)
252             {
253                 Instr = CompleteTraversal(SO);
254                 if (!hash.IsIn(Instr))
255                     SOAG.AppVS(Instr);
256             }
257             Instr = CompleteTraversal(SOAG.Rule[R].SymOcc.Beg);
258             if (!hash.IsIn(Instr))
259                 SOAG.AppVS(Instr);
260         }
261         SOAG.Rule[R].VS.End = SOAG.NextVS - 1;
262     }
263 }