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 */
19static FILE *
20win32_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
64static 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
81void 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
93void 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
116static 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
126static 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
136static 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
151typedef struct BitMap {
152    Go			*go;
153    State		*on;
154    struct BitMap	*next;
155    unsigned int	i;
156    unsigned char	m;
157} BitMap;
158
159static BitMap *BitMap_find_go(Go*, State*);
160static BitMap *BitMap_find(State*);
161static void BitMap_gen(FILE *, unsigned int, unsigned int);
162/* static void BitMap_stats(void);*/
163static BitMap *BitMap_new(Go*, State*);
164
165static BitMap *BitMap_first = NULL;
166
167BitMap *
168BitMap_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
178BitMap *
179BitMap_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
188BitMap *
189BitMap_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
198void 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
224void 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
236static 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
250static 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
268static void indent(FILE *o, unsigned int i){
269    while(i-- > 0)
270	fputc('\t', o);
271}
272
273static 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
299void
300Action_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
380Action *
381Action_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
393static 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
434void
435Go_genLinear(Go *g, FILE *o, State *from, State *next, int *readCh){
436    doLinear(o, 0, g->span, g->nSpans, from, next, readCh);
437}
438
439static 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
450void
451Go_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
500static 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
516void
517Go_genBinary(Go *g, FILE *o, State *from, State *next, int *readCh){
518    doBinary(o, 0, g->span, g->nSpans, from, next, readCh);
519}
520
521void
522Go_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
553void
554Go_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
585void 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
593static 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
634const unsigned int cInfinity = ~0;
635
636typedef struct SCC {
637    State	**top, **stk;
638} SCC;
639
640static void SCC_init(SCC*, unsigned int);
641static SCC *SCC_new(unsigned int);
642static void SCC_destroy(SCC*);
643static void SCC_delete(SCC*);
644static void SCC_traverse(SCC*, State*);
645
646static void
647SCC_init(SCC *s, unsigned int size)
648{
649    s->top = s->stk = malloc(sizeof(State*)*size);
650}
651
652static SCC *
653SCC_new(unsigned int size){
654    SCC *s = malloc(sizeof(SCC));
655    s->top = s->stk = malloc(sizeof(State*)*size);
656    return s;
657}
658
659static void
660SCC_destroy(SCC *s){
661    free(s->stk);
662}
663
664static void
665SCC_delete(SCC *s){
666    free(s->stk);
667    free(s);
668}
669
670static 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
692static 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
710static 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
728void 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
747void 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
761void 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