1 #ifdef _WIN32
2 #include <windows.h>
3 #include <io.h>
4 #endif
5 #include <stdlib.h>
6 #include <string.h>
7 #include <ctype.h>
8 #include "tools/re2c/substr.h"
9 #include "tools/re2c/globals.h"
10 #include "tools/re2c/dfa.h"
11 #include "tools/re2c/parse.h"
12
13 #ifdef _WIN32
14 /* tmpfile() replacment for Windows.
15 *
16 * On Windows tmpfile() creates the file in the root directory. This
17 * may fail due to unsufficient privileges.
18 */
19 static FILE *
win32_tmpfile(void)20 win32_tmpfile (void)
21 {
22 DWORD path_len;
23 WCHAR path_name[MAX_PATH + 1];
24 WCHAR file_name[MAX_PATH + 1];
25 HANDLE handle;
26 int fd;
27 FILE *fp;
28
29 path_len = GetTempPathW (MAX_PATH, path_name);
30 if (path_len <= 0 || path_len >= MAX_PATH)
31 return NULL;
32
33 if (GetTempFileNameW (path_name, L"ps_", 0, file_name) == 0)
34 return NULL;
35
36 handle = CreateFileW (file_name,
37 GENERIC_READ | GENERIC_WRITE,
38 0,
39 NULL,
40 CREATE_ALWAYS,
41 FILE_ATTRIBUTE_NORMAL | FILE_FLAG_DELETE_ON_CLOSE,
42 NULL);
43 if (handle == INVALID_HANDLE_VALUE) {
44 DeleteFileW (file_name);
45 return NULL;
46 }
47
48 fd = _open_osfhandle((intptr_t) handle, 0);
49 if (fd < 0) {
50 CloseHandle (handle);
51 return NULL;
52 }
53
54 fp = fdopen(fd, "w+b");
55 if (fp == NULL) {
56 _close(fd);
57 return NULL;
58 }
59
60 return fp;
61 }
62 #endif
63
useLabel(size_t value)64 static void useLabel(size_t value) {
65 while (value >= vUsedLabelAlloc) {
66 vUsedLabels = realloc(vUsedLabels, vUsedLabelAlloc * 2);
67 if (!vUsedLabels) {
68 fputs("Out of memory.\n", stderr);
69 exit(EXIT_FAILURE);
70 }
71 memset(vUsedLabels + vUsedLabelAlloc, 0, vUsedLabelAlloc);
72 vUsedLabelAlloc *= 2;
73 }
74 vUsedLabels[value] = 1;
75 }
76
77 /* there must be at least one span in list; all spans must cover
78 * same range
79 */
80
Go_compact(Go * g)81 void Go_compact(Go *g){
82 /* arrange so that adjacent spans have different targets */
83 unsigned int i = 0, j;
84 for(j = 1; j < g->nSpans; ++j){
85 if(g->span[j].to != g->span[i].to){
86 ++i; g->span[i].to = g->span[j].to;
87 }
88 g->span[i].ub = g->span[j].ub;
89 }
90 g->nSpans = i + 1;
91 }
92
Go_unmap(Go * g,Go * base,State * x)93 void Go_unmap(Go *g, Go *base, State *x){
94 Span *s = g->span, *b = base->span, *e = &b[base->nSpans];
95 unsigned int lb = 0;
96 s->ub = 0;
97 s->to = NULL;
98 for(; b != e; ++b){
99 if(b->to == x){
100 if((s->ub - lb) > 1)
101 s->ub = b->ub;
102 } else {
103 if(b->to != s->to){
104 if(s->ub){
105 lb = s->ub; ++s;
106 }
107 s->to = b->to;
108 }
109 s->ub = b->ub;
110 }
111 }
112 s->ub = e[-1].ub; ++s;
113 g->nSpans = s - g->span;
114 }
115
doGen(Go * g,State * s,unsigned char * bm,unsigned char m)116 static void doGen(Go *g, State *s, unsigned char *bm, unsigned char m){
117 Span *b = g->span, *e = &b[g->nSpans];
118 unsigned int lb = 0;
119 for(; b < e; ++b){
120 if(b->to == s)
121 for(; lb < b->ub; ++lb) bm[lb] |= m;
122 lb = b->ub;
123 }
124 }
125 #if 0
126 static void prt(FILE *o, Go *g, State *s){
127 Span *b = g->span, *e = &b[g->nSpans];
128 unsigned int lb = 0;
129 for(; b < e; ++b){
130 if(b->to == s)
131 printSpan(o, lb, b->ub);
132 lb = b->ub;
133 }
134 }
135 #endif
matches(Go * g1,State * s1,Go * g2,State * s2)136 static int matches(Go *g1, State *s1, Go *g2, State *s2){
137 Span *b1 = g1->span, *e1 = &b1[g1->nSpans];
138 unsigned int lb1 = 0;
139 Span *b2 = g2->span, *e2 = &b2[g2->nSpans];
140 unsigned int lb2 = 0;
141 for(;;){
142 for(; b1 < e1 && b1->to != s1; ++b1) lb1 = b1->ub;
143 for(; b2 < e2 && b2->to != s2; ++b2) lb2 = b2->ub;
144 if(b1 == e1) return b2 == e2;
145 if(b2 == e2) return 0;
146 if(lb1 != lb2 || b1->ub != b2->ub) return 0;
147 ++b1; ++b2;
148 }
149 }
150
151 typedef struct BitMap {
152 Go *go;
153 State *on;
154 struct BitMap *next;
155 unsigned int i;
156 unsigned char m;
157 } BitMap;
158
159 static BitMap *BitMap_find_go(Go*, State*);
160 static BitMap *BitMap_find(State*);
161 static void BitMap_gen(FILE *, unsigned int, unsigned int);
162 /* static void BitMap_stats(void);*/
163 static BitMap *BitMap_new(Go*, State*);
164
165 static BitMap *BitMap_first = NULL;
166
167 BitMap *
BitMap_new(Go * g,State * x)168 BitMap_new(Go *g, State *x)
169 {
170 BitMap *b = malloc(sizeof(BitMap));
171 b->go = g;
172 b->on = x;
173 b->next = BitMap_first;
174 BitMap_first = b;
175 return b;
176 }
177
178 BitMap *
BitMap_find_go(Go * g,State * x)179 BitMap_find_go(Go *g, State *x){
180 BitMap *b;
181 for(b = BitMap_first; b; b = b->next){
182 if(matches(b->go, b->on, g, x))
183 return b;
184 }
185 return BitMap_new(g, x);
186 }
187
188 BitMap *
BitMap_find(State * x)189 BitMap_find(State *x){
190 BitMap *b;
191 for(b = BitMap_first; b; b = b->next){
192 if(b->on == x)
193 return b;
194 }
195 return NULL;
196 }
197
BitMap_gen(FILE * o,unsigned int lb,unsigned int ub)198 void BitMap_gen(FILE *o, unsigned int lb, unsigned int ub){
199 BitMap *b = BitMap_first;
200 if(b){
201 unsigned int n = ub - lb;
202 unsigned int i;
203 unsigned char *bm = malloc(sizeof(unsigned char)*n);
204 fputs("\tstatic unsigned char yybm[] = {", o);
205 for(i = 0; b; i += n){
206 unsigned char m;
207 unsigned int j;
208 memset(bm, 0, n);
209 for(m = 0x80; b && m; b = b->next, m >>= 1){
210 b->i = i; b->m = m;
211 doGen(b->go, b->on, bm-lb, m);
212 }
213 for(j = 0; j < n; ++j){
214 if(j%8 == 0) {fputs("\n\t", o); oline++;}
215 fprintf(o, "%3u, ", (unsigned int) bm[j]);
216 }
217 }
218 fputs("\n\t};\n", o); oline+=2;
219 free(bm);
220 }
221 }
222
223 #if 0
224 void BitMap_stats(void){
225 unsigned int n = 0;
226 BitMap *b;
227 for(b = BitMap_first; b; b = b->next){
228 prt(stderr, b->go, b->on); fputs("\n", stderr);
229 ++n;
230 }
231 fprintf(stderr, "%u bitmaps\n", n);
232 BitMap_first = NULL;
233 }
234 #endif
235
genGoTo(FILE * o,State * from,State * to,int * readCh,const char * indent)236 static void genGoTo(FILE *o, State *from, State *to, int *readCh,
237 const char *indent)
238 {
239 #if 0
240 if (*readCh && from->label + 1 != to->label)
241 {
242 fputs("%syych = *YYCURSOR;\n", indent, o); oline++;
243 *readCh = 0;
244 }
245 #endif
246 fprintf(o, "%sgoto yy%u;\n", indent, to->label); oline++;
247 useLabel(to->label);
248 }
249
genIf(FILE * o,const char * cmp,unsigned int v,int * readCh)250 static void genIf(FILE *o, const char *cmp, unsigned int v, int *readCh)
251 {
252 #if 0
253 if (*readCh)
254 {
255 fputs("\tif((yych = *YYCURSOR) ", o);
256 *readCh = 0;
257 } else {
258 #endif
259 fputs("\tif(yych ", o);
260 #if 0
261 }
262 #endif
263 fprintf(o, "%s '", cmp);
264 prtCh(o, v);
265 fputs("')", o);
266 }
267
indent(FILE * o,unsigned int i)268 static void indent(FILE *o, unsigned int i){
269 while(i-- > 0)
270 fputc('\t', o);
271 }
272
need(FILE * o,unsigned int n,int * readCh)273 static void need(FILE *o, unsigned int n, int *readCh)
274 {
275 unsigned int fillIndex;
276 int hasFillIndex = (0<=vFillIndexes);
277 if (hasFillIndex) {
278 fillIndex = vFillIndexes++;
279 fprintf(o, "\tYYSETSTATE(%u);\n", fillIndex);
280 ++oline;
281 }
282
283 if(n == 1) {
284 fputs("\tif(YYLIMIT == YYCURSOR) YYFILL(1);\n", o); oline++;
285 } else {
286 fprintf(o, "\tif((YYLIMIT - YYCURSOR) < %u) YYFILL(%u);\n", n, n);
287 oline++;
288 }
289
290 if (hasFillIndex) {
291 fprintf(o, "yyFillLabel%u:\n", fillIndex);
292 ++oline;
293 }
294
295 fputs("\tyych = *YYCURSOR;\n", o); oline++;
296 *readCh = 0;
297 }
298
299 void
Action_emit(Action * a,FILE * o,int * readCh)300 Action_emit(Action *a, FILE *o, int *readCh)
301 {
302 int first = 1;
303 unsigned int i;
304 unsigned int back;
305
306 switch (a->type) {
307 case MATCHACT:
308 if(a->state->link){
309 fputs("\t++YYCURSOR;\n", o);
310 need(o, a->state->depth, readCh);
311 #if 0
312 } else if (!Action_readAhead(a)) {
313 /* do not read next char if match */
314 fputs("\t++YYCURSOR;\n", o);
315 *readCh = 1;
316 #endif
317 } else {
318 fputs("\tyych = *++YYCURSOR;\n", o);
319 *readCh = 0;
320 }
321 oline++;
322 break;
323 case ENTERACT:
324 if(a->state->link){
325 fputs("\t++YYCURSOR;\n", o);
326 fprintf(o, "yy%u:\n", a->d.label); oline+=2;
327 need(o, a->state->depth, readCh);
328 } else {
329 /* we shouldn't need 'rule-following' protection here */
330 fputs("\tyych = *++YYCURSOR;\n", o);
331 fprintf(o, "yy%u:\n", a->d.label); oline+=2;
332 *readCh = 0;
333 }
334 break;
335 case SAVEMATCHACT:
336 if (bUsedYYAccept) {
337 fprintf(o, "\tyyaccept = %u;\n", a->d.selector);
338 oline++;
339 }
340 if(a->state->link){
341 fputs("\tYYMARKER = ++YYCURSOR;\n", o); oline++;
342 need(o, a->state->depth, readCh);
343 } else {
344 fputs("\tyych = *(YYMARKER = ++YYCURSOR);\n", o); oline++;
345 *readCh = 0;
346 }
347 break;
348 case MOVEACT:
349 break;
350 case ACCEPTACT:
351 for(i = 0; i < a->d.Accept.nRules; ++i)
352 if(a->d.Accept.saves[i] != ~0u){
353 if(first){
354 first = 0;
355 bUsedYYAccept = 1;
356 fputs("\tYYCURSOR = YYMARKER;\n", o);
357 fputs("\tswitch(yyaccept){\n", o); oline+=2;
358 }
359 fprintf(o, "\tcase %u:", a->d.Accept.saves[i]);
360 genGoTo(o, a->state, a->d.Accept.rules[i], readCh, "\t");
361 }
362 if(!first) {
363 fputs("\t}\n", o); oline++;
364 }
365 break;
366 case RULEACT:
367 back = RegExp_fixedLength(a->d.rule->d.RuleOp.ctx);
368 if(back != ~0u && back > 0u)
369 fprintf(o, "\tYYCURSOR -= %u;", back);
370 fprintf(o, "\n"); oline++;
371 line_source(o, a->d.rule->d.RuleOp.code->line);
372 SubStr_out(&a->d.rule->d.RuleOp.code->text, o);
373 fprintf(o, "\n"); oline++;
374 if (!iFlag)
375 fprintf(o, "#line %u \"%s\"\n", oline++, outputFileName);
376 break;
377 }
378 }
379
380 Action *
Action_new_Accept(State * x,unsigned int n,unsigned int * s,State ** r)381 Action_new_Accept(State *x, unsigned int n, unsigned int *s, State **r)
382 {
383 Action *a = malloc(sizeof(Action));
384 a->type = ACCEPTACT;
385 a->state = x;
386 a->d.Accept.nRules = n;
387 a->d.Accept.saves = s;
388 a->d.Accept.rules = r;
389 x->action = a;
390 return a;
391 }
392
doLinear(FILE * o,unsigned int i,Span * s,unsigned int n,State * from,State * next,int * readCh)393 static void doLinear(FILE *o, unsigned int i, Span *s, unsigned int n,
394 State *from, State *next, int *readCh){
395 for(;;){
396 State *bg = s[0].to;
397 while(n >= 3 && s[2].to == bg && (s[1].ub - s[0].ub) == 1){
398 if(s[1].to == next && n == 3){
399 indent(o, i);
400 genIf(o, "!=", s[0].ub, readCh);
401 genGoTo(o, from, bg, readCh, "\t");
402 indent(o, i);
403 genGoTo(o, from, next, readCh, "\t");
404 return;
405 } else {
406 indent(o, i);
407 genIf(o, "==", s[0].ub, readCh);
408 genGoTo(o, from, s[1].to, readCh, "\t");
409 }
410 n -= 2; s += 2;
411 }
412 if(n == 1){
413 indent(o, i);
414 genGoTo(o, from, s[0].to, readCh, "\t");
415 return;
416 } else if(n == 2 && bg == next){
417 indent(o, i);
418 genIf(o, ">=", s[0].ub, readCh);
419 genGoTo(o, from, s[1].to, readCh, "\t");
420 indent(o, i);
421 genGoTo(o, from, next, readCh, "\t");
422 return;
423 } else {
424 indent(o, i);
425 genIf(o, "<=", s[0].ub - 1, readCh);
426 genGoTo(o, from, bg, readCh, "\t");
427 n -= 1; s += 1;
428 }
429 }
430 indent(o, i);
431 genGoTo(o, from, next, readCh, "\t");
432 }
433
434 void
Go_genLinear(Go * g,FILE * o,State * from,State * next,int * readCh)435 Go_genLinear(Go *g, FILE *o, State *from, State *next, int *readCh){
436 doLinear(o, 0, g->span, g->nSpans, from, next, readCh);
437 }
438
genCases(FILE * o,unsigned int lb,Span * s)439 static void genCases(FILE *o, unsigned int lb, Span *s){
440 if(lb < s->ub){
441 for(;;){
442 fputs("\tcase '", o); prtCh(o, lb); fputs("':", o);
443 if(++lb == s->ub)
444 break;
445 fputs("\n", o); oline++;
446 }
447 }
448 }
449
450 void
Go_genSwitch(Go * g,FILE * o,State * from,State * next,int * readCh)451 Go_genSwitch(Go *g, FILE *o, State *from, State *next, int *readCh){
452 if(g->nSpans <= 2){
453 Go_genLinear(g, o, from, next, readCh);
454 } else {
455 State *def = g->span[g->nSpans-1].to;
456 Span **sP = malloc(sizeof(Span*)*(g->nSpans-1)), **r, **s, **t;
457 unsigned int i;
458
459 t = &sP[0];
460 for(i = 0; i < g->nSpans; ++i)
461 if(g->span[i].to != def)
462 *(t++) = &g->span[i];
463
464 if (dFlag)
465 fputs("\tYYDEBUG(-1, yych);\n", o);
466
467 #if 0
468 if (*readCh) {
469 fputs("\tswitch((yych = *YYCURSOR)) {\n", o);
470 *readCh = 0;
471 } else
472 #endif
473 fputs("\tswitch(yych){\n", o);
474 oline++;
475 while(t != &sP[0]){
476 State *to;
477 r = s = &sP[0];
478 if(*s == &g->span[0])
479 genCases(o, 0, *s);
480 else
481 genCases(o, (*s)[-1].ub, *s);
482 to = (*s)->to;
483 while(++s < t){
484 if((*s)->to == to)
485 genCases(o, (*s)[-1].ub, *s);
486 else
487 *(r++) = *s;
488 }
489 genGoTo(o, from, to, readCh, "\t");
490 t = r;
491 }
492 fputs("\tdefault:", o);
493 genGoTo(o, from, def, readCh, "\t");
494 fputs("\t}\n", o); oline++;
495
496 free(sP);
497 }
498 }
499
doBinary(FILE * o,unsigned int i,Span * s,unsigned int n,State * from,State * next,int * readCh)500 static void doBinary(FILE *o, unsigned int i, Span *s, unsigned int n,
501 State *from, State *next, int *readCh){
502 if(n <= 4){
503 doLinear(o, i, s, n, from, next, readCh);
504 } else {
505 unsigned int h = n/2;
506 indent(o, i);
507 genIf(o, "<=", s[h-1].ub - 1, readCh);
508 fputs("{\n", o); oline++;
509 doBinary(o, i+1, &s[0], h, from, next, readCh);
510 indent(o, i); fputs("\t} else {\n", o); oline++;
511 doBinary(o, i+1, &s[h], n - h, from, next, readCh);
512 indent(o, i); fputs("\t}\n", o); oline++;
513 }
514 }
515
516 void
Go_genBinary(Go * g,FILE * o,State * from,State * next,int * readCh)517 Go_genBinary(Go *g, FILE *o, State *from, State *next, int *readCh){
518 doBinary(o, 0, g->span, g->nSpans, from, next, readCh);
519 }
520
521 void
Go_genBase(Go * g,FILE * o,State * from,State * next,int * readCh)522 Go_genBase(Go *g, FILE *o, State *from, State *next, int *readCh){
523 if(g->nSpans == 0)
524 return;
525 if(!sFlag){
526 Go_genSwitch(g, o, from, next, readCh);
527 return;
528 }
529 if(g->nSpans > 8){
530 Span *bot = &g->span[0], *top = &g->span[g->nSpans-1];
531 unsigned int util;
532 if(bot[0].to == top[0].to){
533 util = (top[-1].ub - bot[0].ub)/(g->nSpans - 2);
534 } else {
535 if(bot[0].ub > (top[0].ub - top[-1].ub)){
536 util = (top[0].ub - bot[0].ub)/(g->nSpans - 1);
537 } else {
538 util = top[-1].ub/(g->nSpans - 1);
539 }
540 }
541 if(util <= 2){
542 Go_genSwitch(g, o, from, next, readCh);
543 return;
544 }
545 }
546 if(g->nSpans > 5){
547 Go_genBinary(g, o, from, next, readCh);
548 } else {
549 Go_genLinear(g, o, from, next, readCh);
550 }
551 }
552
553 void
Go_genGoto(Go * g,FILE * o,State * from,State * next,int * readCh)554 Go_genGoto(Go *g, FILE *o, State *from, State *next, int *readCh){
555 unsigned int i;
556 if(bFlag){
557 for(i = 0; i < g->nSpans; ++i){
558 State *to = g->span[i].to;
559 if(to && to->isBase){
560 BitMap *b = BitMap_find(to);
561 if(b && matches(b->go, b->on, g, to)){
562 Go go;
563 go.span = malloc(sizeof(Span)*g->nSpans);
564 Go_unmap(&go, g, to);
565 fprintf(o, "\tif(yybm[%u+", b->i);
566 #if 0
567 if (*readCh)
568 fputs("(yych = *YYCURSOR)", o);
569 else
570 #endif
571 fputs("yych", o);
572 fprintf(o, "] & %u) {\n", (unsigned int) b->m); oline++;
573 genGoTo(o, from, to, readCh, "\t\t");
574 fputs("\t}\n", o); oline++;
575 Go_genBase(&go, o, from, next, readCh);
576 free(go.span);
577 return;
578 }
579 }
580 }
581 }
582 Go_genBase(g, o, from, next, readCh);
583 }
584
State_emit(State * s,FILE * o,int * readCh)585 void State_emit(State *s, FILE *o, int *readCh){
586 if (vUsedLabels[s->label])
587 fprintf(o, "yy%u:", s->label);
588 if (dFlag)
589 fprintf(o, "\n\tYYDEBUG(%u, *YYCURSOR);\n", s->label);
590 Action_emit(s->action, o, readCh);
591 }
592
merge(Span * x0,State * fg,State * bg)593 static unsigned int merge(Span *x0, State *fg, State *bg){
594 Span *x = x0, *f = fg->go.span, *b = bg->go.span;
595 unsigned int nf = fg->go.nSpans, nb = bg->go.nSpans;
596 State *prev = NULL, *to;
597 /* NB: we assume both spans are for same range */
598 for(;;){
599 if(f->ub == b->ub){
600 to = f->to == b->to? bg : f->to;
601 if(to == prev){
602 --x;
603 } else {
604 x->to = prev = to;
605 }
606 x->ub = f->ub;
607 ++x; ++f; --nf; ++b; --nb;
608 if(nf == 0 && nb == 0)
609 return x - x0;
610 }
611 while(f->ub < b->ub){
612 to = f->to == b->to? bg : f->to;
613 if(to == prev){
614 --x;
615 } else {
616 x->to = prev = to;
617 }
618 x->ub = f->ub;
619 ++x; ++f; --nf;
620 }
621 while(b->ub < f->ub){
622 to = b->to == f->to? bg : f->to;
623 if(to == prev){
624 --x;
625 } else {
626 x->to = prev = to;
627 }
628 x->ub = b->ub;
629 ++x; ++b; --nb;
630 }
631 }
632 }
633
634 const unsigned int cInfinity = ~0;
635
636 typedef struct SCC {
637 State **top, **stk;
638 } SCC;
639
640 static void SCC_init(SCC*, unsigned int);
641 static SCC *SCC_new(unsigned int);
642 static void SCC_destroy(SCC*);
643 static void SCC_delete(SCC*);
644 static void SCC_traverse(SCC*, State*);
645
646 static void
SCC_init(SCC * s,unsigned int size)647 SCC_init(SCC *s, unsigned int size)
648 {
649 s->top = s->stk = malloc(sizeof(State*)*size);
650 }
651
652 static SCC *
SCC_new(unsigned int size)653 SCC_new(unsigned int size){
654 SCC *s = malloc(sizeof(SCC));
655 s->top = s->stk = malloc(sizeof(State*)*size);
656 return s;
657 }
658
659 static void
SCC_destroy(SCC * s)660 SCC_destroy(SCC *s){
661 free(s->stk);
662 }
663
664 static void
SCC_delete(SCC * s)665 SCC_delete(SCC *s){
666 free(s->stk);
667 free(s);
668 }
669
SCC_traverse(SCC * s,State * x)670 static void SCC_traverse(SCC *s, State *x){
671 unsigned int k, i;
672
673 *s->top = x;
674 k = ++s->top - s->stk;
675 x->depth = k;
676 for(i = 0; i < x->go.nSpans; ++i){
677 State *y = x->go.span[i].to;
678 if(y){
679 if(y->depth == 0)
680 SCC_traverse(s, y);
681 if(y->depth < x->depth)
682 x->depth = y->depth;
683 }
684 }
685 if(x->depth == k)
686 do {
687 (*--s->top)->depth = cInfinity;
688 (*s->top)->link = x;
689 } while(*s->top != x);
690 }
691
maxDist(State * s)692 static unsigned int maxDist(State *s){
693 unsigned int mm = 0, i;
694 for(i = 0; i < s->go.nSpans; ++i){
695 State *t = s->go.span[i].to;
696 if(t){
697 unsigned int m = 1;
698 if(!t->link) {
699 if (t->depth == -1)
700 t->depth = maxDist(t);
701 m += t->depth;
702 }
703 if(m > mm)
704 mm = m;
705 }
706 }
707 return mm;
708 }
709
calcDepth(State * head)710 static void calcDepth(State *head){
711 State *t, *s;
712 for(s = head; s; s = s->next){
713 if(s->link == s){
714 unsigned int i;
715 for(i = 0; i < s->go.nSpans; ++i){
716 t = s->go.span[i].to;
717 if(t && t->link == s)
718 goto inSCC;
719 }
720 s->link = NULL;
721 } else {
722 inSCC:
723 s->depth = maxDist(s);
724 }
725 }
726 }
727
DFA_findSCCs(DFA * d)728 void DFA_findSCCs(DFA *d){
729 SCC scc;
730 State *s;
731
732 SCC_init(&scc, d->nStates);
733 for(s = d->head; s; s = s->next){
734 s->depth = 0;
735 s->link = NULL;
736 }
737
738 for(s = d->head; s; s = s->next)
739 if(!s->depth)
740 SCC_traverse(&scc, s);
741
742 calcDepth(d->head);
743
744 SCC_destroy(&scc);
745 }
746
DFA_split(DFA * d,State * s)747 void DFA_split(DFA *d, State *s){
748 State *move = State_new();
749 Action_new_Move(move);
750 DFA_addState(d, &s->next, move);
751 move->link = s->link;
752 move->rule = s->rule;
753 move->go = s->go;
754 s->rule = NULL;
755 s->go.nSpans = 1;
756 s->go.span = malloc(sizeof(Span));
757 s->go.span[0].ub = d->ubChar;
758 s->go.span[0].to = move;
759 }
760
DFA_emit(DFA * d,FILE * o)761 void DFA_emit(DFA *d, FILE *o){
762 static unsigned int label = 0;
763 State *s;
764 unsigned int i, bitmap_brace = 0;
765 unsigned int nRules = 0;
766 unsigned int nSaves = 0;
767 unsigned int *saves;
768 unsigned int nOrgOline;
769 State **rules;
770 State *accept = NULL;
771 Span *span;
772 FILE *tmpo;
773 int hasFillLabels;
774 int maxFillIndexes, orgVFillIndexes;
775 unsigned int start_label;
776
777 hasFillLabels = (0<=vFillIndexes);
778 if (hasFillLabels && label!=0) {
779 fputs("re2c : error : multiple /*!re2c blocks aren't supported when -f is specified\n", stderr);
780 exit(1);
781 }
782
783 DFA_findSCCs(d);
784 d->head->link = d->head;
785
786 maxFill = 1;
787 for(s = d->head; s; s = s->next) {
788 s->depth = maxDist(s);
789 if (maxFill < s->depth)
790 maxFill = s->depth;
791 if(s->rule && s->rule->d.RuleOp.accept >= nRules)
792 nRules = s->rule->d.RuleOp.accept + 1;
793 }
794
795 saves = malloc(sizeof(unsigned int)*nRules);
796 memset(saves, ~0, (nRules)*sizeof(unsigned int));
797
798 /* mark backtracking points */
799 for(s = d->head; s; s = s->next){
800 RegExp *ignore = NULL;/*RuleOp*/
801 if(s->rule){
802 for(i = 0; i < s->go.nSpans; ++i)
803 if(s->go.span[i].to && !s->go.span[i].to->rule){
804 free(s->action);
805 if(saves[s->rule->d.RuleOp.accept] == ~0u)
806 saves[s->rule->d.RuleOp.accept] = nSaves++;
807 Action_new_Save(s, saves[s->rule->d.RuleOp.accept]);
808 continue;
809 }
810 ignore = s->rule;
811 }
812 }
813
814 /* insert actions */
815 rules = malloc(sizeof(State*)*nRules);
816 memset(rules, 0, (nRules)*sizeof(State*));
817 for(s = d->head; s; s = s->next){
818 State *ow;
819 if(!s->rule){
820 ow = accept;
821 } else {
822 if(!rules[s->rule->d.RuleOp.accept]){
823 State *n = State_new();
824 Action_new_Rule(n, s->rule);
825 rules[s->rule->d.RuleOp.accept] = n;
826 DFA_addState(d, &s->next, n);
827 }
828 ow = rules[s->rule->d.RuleOp.accept];
829 }
830 for(i = 0; i < s->go.nSpans; ++i)
831 if(!s->go.span[i].to){
832 if(!ow){
833 ow = accept = State_new();
834 Action_new_Accept(accept, nRules, saves, rules);
835 DFA_addState(d, &s->next, accept);
836 }
837 s->go.span[i].to = ow;
838 }
839 }
840
841 /* split ``base'' states into two parts */
842 for(s = d->head; s; s = s->next){
843 s->isBase = 0;
844 if(s->link){
845 for(i = 0; i < s->go.nSpans; ++i){
846 if(s->go.span[i].to == s){
847 s->isBase = 1;
848 DFA_split(d, s);
849 if(bFlag)
850 BitMap_find_go(&s->next->go, s);
851 s = s->next;
852 break;
853 }
854 }
855 }
856 }
857
858 /* find ``base'' state, if possible */
859 span = malloc(sizeof(Span)*(d->ubChar - d->lbChar));
860 for(s = d->head; s; s = s->next){
861 if(!s->link){
862 for(i = 0; i < s->go.nSpans; ++i){
863 State *to = s->go.span[i].to;
864 if(to && to->isBase){
865 unsigned int nSpans;
866 to = to->go.span[0].to;
867 nSpans = merge(span, s, to);
868 if(nSpans < s->go.nSpans){
869 free(s->go.span);
870 s->go.nSpans = nSpans;
871 s->go.span = malloc(sizeof(Span)*nSpans);
872 memcpy(s->go.span, span, nSpans*sizeof(Span));
873 }
874 break;
875 }
876 }
877 }
878 }
879 free(span);
880
881 free(d->head->action);
882
883 if(bFlag) {
884 fputs("{\n", o);
885 oline++;
886 bitmap_brace = 1;
887 BitMap_gen(o, d->lbChar, d->ubChar);
888 }
889
890 bUsedYYAccept = 0;
891
892 start_label = label;
893
894 Action_new_Enter(d->head, label++);
895
896 for(s = d->head; s; s = s->next)
897 s->label = label++;
898
899 nOrgOline = oline;
900 maxFillIndexes = vFillIndexes;
901 orgVFillIndexes = vFillIndexes;
902 #ifdef _WIN32
903 tmpo = win32_tmpfile();
904 #else
905 tmpo = tmpfile();
906 #endif
907 for(s = d->head; s; s = s->next){
908 int readCh = 0;
909 State_emit(s, tmpo, &readCh);
910 Go_genGoto(&s->go, tmpo, s, s->next, &readCh);
911 }
912 fclose(tmpo);
913 maxFillIndexes = vFillIndexes;
914 vFillIndexes = orgVFillIndexes;
915 oline = nOrgOline;
916
917 fputs("\n", o);
918 oline++;
919 if (!iFlag)
920 fprintf(o, "#line %u \"%s\"\n", oline++, outputFileName);
921
922 if (!hasFillLabels) {
923 fputs("{\n\tYYCTYPE yych;\n", o);
924 oline += 2;
925 if (bUsedYYAccept) {
926 fputs("\tunsigned int yyaccept;\n", o);
927 oline++;
928 }
929 } else {
930 fputs("{\n\n", o);
931 oline += 2;
932 }
933
934 if (!hasFillLabels) {
935 fprintf(o, "\tgoto yy%u;\n", start_label);
936 oline++;
937 useLabel(label);
938 } else {
939 int i;
940 fputs("\tswitch(YYGETSTATE()) {\n", o);
941 fputs("\t\tcase -1: goto yy0;\n", o);
942
943 for (i=0; i<maxFillIndexes; ++i)
944 fprintf(o, "\t\tcase %u: goto yyFillLabel%u;\n", i, i);
945
946 fputs("\t\tdefault: /* abort() */;\n", o);
947 fputs("\t}\n", o);
948 fputs("yyNext:\n", o);
949
950 oline += maxFillIndexes;
951 oline += 5;
952 }
953
954 for(s = d->head; s; s = s->next){
955 int readCh = 0;
956 State_emit(s, o, &readCh);
957 Go_genGoto(&s->go, o, s, s->next, &readCh);
958 }
959 fputs("}\n", o); oline++;
960 if (bitmap_brace) {
961 fputs("}\n", o);
962 oline++;
963 }
964
965 BitMap_first = NULL;
966
967 free(saves);
968 free(rules);
969 }
970