Updated footer comment
[idzebra-moved-to-github.git] / dfa / dfa.c
1 /* This file is part of the Zebra server.
2    Copyright (C) 1994-2009 Index Data
3
4 Zebra is free software; you can redistribute it and/or modify it under
5 the terms of the GNU General Public License as published by the Free
6 Software Foundation; either version 2, or (at your option) any later
7 version.
8
9 Zebra is distributed in the hope that it will be useful, but WITHOUT ANY
10 WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
12 for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software
16 Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
17
18 */
19
20
21 #include <stdio.h>
22 #include <assert.h>
23
24 #include <stdlib.h>
25 #include <string.h>
26 #include <ctype.h>
27
28 #include <idzebra/util.h>
29 #include "dfap.h"
30 #include "imalloc.h"
31
32 #define CAT     16000
33 #define OR      16001
34 #define STAR    16002
35 #define PLUS    16003
36 #define EPSILON 16004
37
38 struct Tnode {
39     union  {
40         struct Tnode *p[2];   /* CAT,OR,STAR,PLUS (left,right) */
41         short ch[2];          /* if ch[0] >= 0 then this Tnode represents */
42                               /*   a character in range [ch[0]..ch[1]]    */
43                               /* otherwise ch[0] represents */
44                               /*   accepting no (-acceptno) */
45     } u;
46     unsigned pos : 15;        /* CAT/OR/STAR/EPSILON or non-neg. position */
47     unsigned nullable : 1;
48     DFASet firstpos;             /* first positions */
49     DFASet lastpos;              /* last positions */
50 };
51
52 struct Tblock {               /* Tnode bucket (block) */
53     struct Tblock *next;      /* pointer to next bucket */
54     struct Tnode *tarray;     /* array of nodes in bucket */
55 };
56
57 #define TADD 64
58 #define STATE_HASH 199
59 #define POSET_CHUNK 100
60
61 int debug_dfa_trav  = 0;
62 int debug_dfa_tran  = 0;
63 int debug_dfa_followpos = 0;
64 int dfa_verbose = 0;
65
66 static struct Tnode *mk_Tnode      (struct DFA_parse *parse_info);
67 static struct Tnode *mk_Tnode_cset (struct DFA_parse *parse_info,
68                                     BSet charset);
69 static void        term_Tnode      (struct DFA_parse *parse_info);
70
71 static void 
72     del_followpos  (struct DFA_parse *parse_info), 
73     init_pos       (struct DFA_parse *parse_info), 
74     del_pos        (struct DFA_parse *parse_info),
75     mk_dfa_tran    (struct DFA_parse *parse_info, struct DFA_states *dfas),
76     add_follow     (struct DFA_parse *parse_info, DFASet lastpos, DFASet firstpos),
77     dfa_trav       (struct DFA_parse *parse_info, struct Tnode *n),
78     init_followpos (struct DFA_parse *parse_info),
79     pr_tran        (struct DFA_parse *parse_info, struct DFA_states *dfas),
80     pr_verbose     (struct DFA_parse *parse_info, struct DFA_states *dfas),
81     pr_followpos   (struct DFA_parse *parse_info),
82     out_char       (int c),
83     lex            (struct DFA_parse *parse_info);
84
85 static int
86     nextchar       (struct DFA_parse *parse_info, int *esc),
87     read_charset   (struct DFA_parse *parse_info);
88
89 static const char 
90     *str_char      (unsigned c);
91
92 #define L_LP 1
93 #define L_RP 2
94 #define L_CHAR 3
95 #define L_CHARS 4
96 #define L_ANY 5
97 #define L_ALT 6
98 #define L_ANYZ 7
99 #define L_WILD 8
100 #define L_QUEST 9
101 #define L_CLOS1 10
102 #define L_CLOS0 11
103 #define L_END 12
104 #define L_START 13
105
106
107 static struct Tnode *expr_1 (struct DFA_parse *parse_info),
108                     *expr_2 (struct DFA_parse *parse_info),
109                     *expr_3 (struct DFA_parse *parse_info),
110                     *expr_4 (struct DFA_parse *parse_info);
111
112 static struct Tnode *expr_1 (struct DFA_parse *parse_info)
113
114     struct Tnode *t1, *t2, *tn;
115
116     if (!(t1 = expr_2 (parse_info)))
117         return t1;
118     while (parse_info->lookahead == L_ALT)
119     {
120         lex (parse_info);
121         if (!(t2 = expr_2 (parse_info)))
122             return t2;
123         
124         tn = mk_Tnode (parse_info);
125         tn->pos = OR;
126         tn->u.p[0] = t1;
127         tn->u.p[1] = t2;
128         t1 = tn;
129     }
130     return t1;
131 }
132
133 static struct Tnode *expr_2 (struct DFA_parse *parse_info)
134 {
135     struct Tnode *t1, *t2, *tn;
136     
137     if (!(t1 = expr_3 (parse_info)))
138         return t1;
139     while (parse_info->lookahead == L_WILD ||
140            parse_info->lookahead == L_ANYZ ||
141            parse_info->lookahead == L_ANY ||
142            parse_info->lookahead == L_LP ||
143            parse_info->lookahead == L_CHAR ||
144            parse_info->lookahead == L_CHARS)
145     {
146         if (!(t2 = expr_3 (parse_info)))
147             return t2;
148         
149         tn = mk_Tnode (parse_info);
150         tn->pos = CAT;
151         tn->u.p[0] = t1;
152         tn->u.p[1] = t2;
153         t1 = tn;
154     }
155     return t1;
156 }
157
158 static struct Tnode *expr_3 (struct DFA_parse *parse_info)
159 {
160     struct Tnode *t1, *tn;
161
162     if (!(t1 = expr_4 (parse_info)))
163         return t1;
164     if (parse_info->lookahead == L_CLOS0)
165     {
166         lex (parse_info);
167         tn = mk_Tnode (parse_info);
168         tn->pos = STAR;
169         tn->u.p[0] = t1;
170         t1 = tn;
171     }
172     else if (parse_info->lookahead == L_CLOS1)
173     {
174         lex (parse_info);
175         tn = mk_Tnode (parse_info);
176         tn->pos = PLUS;
177         tn->u.p[0] = t1;
178         t1 = tn;
179     }
180     else if (parse_info->lookahead == L_QUEST)
181     {
182         lex (parse_info);
183         tn = mk_Tnode(parse_info);
184         tn->pos = OR;
185         tn->u.p[0] = t1;
186         tn->u.p[1] = mk_Tnode(parse_info);
187         tn->u.p[1]->pos = EPSILON;
188         t1 = tn;
189     }
190     return t1;
191 }
192
193 static struct Tnode *expr_4 (struct DFA_parse *parse_info)
194 {
195     struct Tnode *t1;
196
197     switch (parse_info->lookahead)
198     {
199     case L_LP:
200         lex (parse_info);
201         if (!(t1 = expr_1 (parse_info)))
202             return t1;
203         if (parse_info->lookahead == L_RP)
204             lex (parse_info);
205         else
206             return NULL;
207         break;
208     case L_CHAR:
209         t1 = mk_Tnode(parse_info);
210         t1->pos = ++parse_info->position;
211         t1->u.ch[1] = t1->u.ch[0] = parse_info->look_ch;
212         lex (parse_info);
213         break;
214     case L_CHARS:
215         t1 = mk_Tnode_cset (parse_info, parse_info->look_chars);
216         lex (parse_info);
217         break;
218     case L_ANY:
219         t1 = mk_Tnode_cset (parse_info, parse_info->anyset);
220         lex (parse_info);
221         break;
222     case L_ANYZ:
223         t1 = mk_Tnode(parse_info);
224         t1->pos = OR;
225         t1->u.p[0] = mk_Tnode_cset (parse_info, parse_info->anyset);
226         t1->u.p[1] = mk_Tnode(parse_info);
227         t1->u.p[1]->pos = EPSILON;
228         lex (parse_info);
229         break;
230     case L_WILD:
231         t1 = mk_Tnode(parse_info);
232         t1->pos = STAR;
233         t1->u.p[0] = mk_Tnode_cset (parse_info, parse_info->anyset);
234         lex (parse_info);
235     default:
236         t1 = NULL;
237     }
238     return t1;
239 }
240
241 static void do_parse (struct DFA_parse *parse_info, const char **s,
242                       struct Tnode **tnp)
243 {
244     int start_anchor_flag = 0;
245     struct Tnode *t1, *t2, *tn;
246
247     parse_info->err_code = 0;
248     parse_info->expr_ptr =  * (const unsigned char **) s;
249
250     parse_info->inside_string = 0;
251     lex (parse_info);
252     if (parse_info->lookahead == L_START)
253     {
254         start_anchor_flag = 1;
255         lex (parse_info);
256     }
257     if (parse_info->lookahead == L_END)
258     {
259         t1 = mk_Tnode (parse_info);
260         t1->pos = ++parse_info->position;
261         t1->u.ch[1] = t1->u.ch[0] = '\n';
262         lex (parse_info);
263     }
264     else
265     {
266         t1 = expr_1 (parse_info);
267         if (t1 && parse_info->lookahead == L_END)
268         {
269             t2 = mk_Tnode (parse_info);
270             t2->pos = ++parse_info->position;
271             t2->u.ch[1] = t2->u.ch[0] = '\n';
272             
273             tn = mk_Tnode (parse_info);
274             tn->pos = CAT;
275             tn->u.p[0] = t1;
276             tn->u.p[1] = t2;
277             t1 = tn;
278             
279             lex (parse_info);
280         }
281     }
282     if (t1 && parse_info->lookahead == 0)
283     {
284         t2 = mk_Tnode(parse_info);
285         t2->pos = ++parse_info->position;
286         t2->u.ch[0] = -(++parse_info->rule);
287         t2->u.ch[1] = start_anchor_flag ? 0 : -(parse_info->rule);
288         
289         *tnp = mk_Tnode(parse_info);
290         (*tnp)->pos = CAT;
291         (*tnp)->u.p[0] = t1;
292         (*tnp)->u.p[1] = t2;
293     }
294     else
295     {
296         if (!parse_info->err_code)
297         {
298             if (parse_info->lookahead == L_RP)
299                 parse_info->err_code = DFA_ERR_RP;
300             else if (parse_info->lookahead == L_LP)
301                 parse_info->err_code = DFA_ERR_LP;
302             else
303                 parse_info->err_code = DFA_ERR_SYNTAX;
304         }
305     }
306     *s = (const char *) parse_info->expr_ptr;
307 }
308
309 static int nextchar (struct DFA_parse *parse_info, int *esc)
310 {
311     *esc = 0;
312     if (*parse_info->expr_ptr == '\0')
313         return 0;
314     else if (*parse_info->expr_ptr != '\\')
315         return *parse_info->expr_ptr++;
316     *esc = 1;
317     switch (*++parse_info->expr_ptr)
318     {
319     case '\r':
320     case '\n':
321     case '\0':
322         return '\\';
323     case '\t':
324         ++parse_info->expr_ptr;
325         return ' ';
326     case 'n':
327         ++parse_info->expr_ptr;
328         return '\n';
329     case 't':
330         ++parse_info->expr_ptr;
331         return '\t';
332     case 'r':
333         ++parse_info->expr_ptr;
334         return '\r';
335     case 'f':
336         ++parse_info->expr_ptr;
337         return '\f';
338     default:
339         return *parse_info->expr_ptr++;
340     }
341 }
342
343 static int nextchar_set (struct DFA_parse *parse_info, int *esc)
344 {
345     if (*parse_info->expr_ptr == ' ')
346     {
347         *esc = 0;
348         return *parse_info->expr_ptr++;
349     }
350     return nextchar (parse_info, esc);
351 }
352
353 static int read_charset (struct DFA_parse *parse_info)
354 {
355     int i, ch0, esc0, cc = 0;
356     parse_info->look_chars = mk_BSet (&parse_info->charset);
357     res_BSet (parse_info->charset, parse_info->look_chars);
358
359     ch0 = nextchar_set (parse_info, &esc0);
360     if (!esc0 && ch0 == '^')
361     {
362         cc = 1;
363         ch0 = nextchar_set (parse_info, &esc0);
364     }
365     /**
366        ch0 is last met character 
367        ch1 is "next" char 
368     */
369     while (ch0 != 0)
370     {
371         int ch1, esc1;
372         if (!esc0 && ch0 == ']')
373             break;
374         if (!esc0 && ch0 == '-')
375         {
376             ch1 = ch0;
377             esc1 = esc0;
378             ch0 = 1;
379             add_BSet (parse_info->charset, parse_info->look_chars, ch0);
380         }
381         else
382         {
383             if (ch0 == 1)
384             {
385                 ch0 = nextchar(parse_info, &esc0);
386             }
387             else
388             {
389                 if (parse_info->cmap)
390                 {
391                     const char **mapto;
392                     char mapfrom[2];
393                     const char *mcp = mapfrom;
394                     mapfrom[0] = ch0;
395                     mapto = parse_info->cmap(parse_info->cmap_data, &mcp, 1);
396                     assert (mapto);
397                     ch0 = mapto[0][0];
398                 }
399             }
400             add_BSet (parse_info->charset, parse_info->look_chars, ch0);
401             ch1 = nextchar_set (parse_info, &esc1);
402         }
403         if (!esc1 && ch1 == '-')
404         {
405             int open_range = 0;
406             if ((ch1 = nextchar_set (parse_info, &esc1)) == 0)
407                 break;
408             if (!esc1 && ch1 == ']')
409             {
410                 ch1 = 255;
411                 open_range = 1;
412             }
413             else if (ch1 == 1)
414             {
415                 ch1 = nextchar(parse_info, &esc1);
416             }
417             else if (parse_info->cmap)
418             {
419                 const char **mapto;
420                 char mapfrom[2];
421                 const char *mcp = mapfrom;
422                 mapfrom[0] = ch1;
423                 mapto = (*parse_info->cmap) (parse_info->cmap_data, &mcp, 1);
424                 assert (mapto);
425                 ch1 = mapto[0][0];
426             }
427             for (i = ch0; ++i <= ch1;)
428                 add_BSet (parse_info->charset, parse_info->look_chars, i);
429
430             if (open_range)
431                 break;
432             ch0 = nextchar_set (parse_info, &esc0);
433         }
434         else
435         {
436             esc0 = esc1;
437             ch0 = ch1;
438         }
439     }
440     if (cc)
441         com_BSet (parse_info->charset, parse_info->look_chars);
442     return L_CHARS;
443 }
444
445 static int map_l_char (struct DFA_parse *parse_info)
446 {
447     const char **mapto;
448     const char *cp0 = (const char *) (parse_info->expr_ptr-1);
449     int i = 0, len = strlen(cp0);
450
451     if (cp0[0] == 1 && cp0[1])
452     {
453         parse_info->expr_ptr++;
454         parse_info->look_ch = ((unsigned char *) cp0)[1];
455         return L_CHAR;
456     }
457     if (!parse_info->cmap)
458         return L_CHAR;
459
460     mapto = (*parse_info->cmap) (parse_info->cmap_data, &cp0, len);
461     assert (mapto);
462     
463     parse_info->expr_ptr = (const unsigned char *) cp0;
464     parse_info->look_ch = ((unsigned char **) mapto)[i][0];
465     yaz_log (YLOG_DEBUG, "map from %c to %d", parse_info->expr_ptr[-1], parse_info->look_ch);
466     return L_CHAR;
467 }
468
469 static int lex_sub(struct DFA_parse *parse_info)
470 {
471     int esc;
472     while ((parse_info->look_ch = nextchar (parse_info, &esc)) != 0)
473         if (parse_info->look_ch == '\"')
474         {
475             if (esc)
476                 return map_l_char (parse_info);
477             parse_info->inside_string = !parse_info->inside_string;
478         }
479         else if (esc || parse_info->inside_string)
480             return map_l_char (parse_info);
481         else if (parse_info->look_ch == '[')
482             return read_charset(parse_info);
483         else 
484         {
485             const int *cc;
486             for (cc = parse_info->charMap; *cc; cc += 2)
487                 if (*cc == (int) (parse_info->look_ch))
488                 {
489                     if (!cc[1])
490                         --parse_info->expr_ptr;
491                     return cc[1];
492                 }
493             return map_l_char (parse_info);
494         }
495     return 0;
496 }
497
498 static void lex (struct DFA_parse *parse_info)
499 {
500     parse_info->lookahead = lex_sub (parse_info);
501 }
502
503 static const char *str_char (unsigned c)
504 {
505     static char s[6];
506     s[0] = '\\';
507     if (c < 32 || c >= 127)
508         switch (c)
509         {
510         case '\r':
511             strcpy (s+1, "r");
512             break;
513         case '\n':
514             strcpy (s+1, "n");
515             break;
516         case '\t':
517             strcpy (s+1, "t");
518             break;
519         default:
520             sprintf (s+1, "x%02x", c);
521             break;
522         }
523     else
524         switch (c)
525         {
526         case '\"':
527             strcpy (s+1, "\"");
528             break;
529         case '\'':
530             strcpy (s+1, "\'");
531             break;
532         case '\\':
533             strcpy (s+1, "\\");
534             break;
535         default:
536             s[0] = c;
537             s[1] = '\0';
538         }
539     return s;
540 }
541
542 static void out_char (int c)
543 {
544     printf ("%s", str_char (c));
545 }
546
547 static void term_Tnode (struct DFA_parse *parse_info)
548 {
549     struct Tblock *t, *t1;
550     for (t = parse_info->start; (t1 = t);)
551     {
552         t=t->next;
553         ifree (t1->tarray);
554         ifree (t1);
555     }
556 }
557
558 static struct Tnode *mk_Tnode (struct DFA_parse *parse_info)
559 {
560     struct Tblock *tnew;
561
562     if (parse_info->use_Tnode == parse_info->max_Tnode)
563     {
564         tnew = (struct Tblock *) imalloc (sizeof(struct Tblock));
565         tnew->tarray = (struct Tnode *) imalloc (TADD*sizeof(struct Tnode));
566         if (!tnew->tarray)
567             return NULL;
568         if (parse_info->use_Tnode == 0)
569             parse_info->start = tnew;
570         else
571             parse_info->end->next = tnew;
572         parse_info->end = tnew;
573         tnew->next = NULL;
574         parse_info->max_Tnode += TADD;
575     }
576     return parse_info->end->tarray+(parse_info->use_Tnode++ % TADD);
577 }
578
579 struct Tnode *mk_Tnode_cset (struct DFA_parse *parse_info, BSet charset)
580 {
581     struct Tnode *tn1, *tn0 = mk_Tnode(parse_info);
582     int ch1, ch0 = trav_BSet (parse_info->charset, charset, 0);
583     if (ch0 == -1)
584         tn0->pos = EPSILON;
585     else
586     {
587         tn0->u.ch[0] = ch0;
588         tn0->pos = ++parse_info->position;
589         ch1 = travi_BSet (parse_info->charset, charset, ch0+1) ;
590         if (ch1 == -1)
591             tn0->u.ch[1] = parse_info->charset->size;
592         else
593         {
594             tn0->u.ch[1] = ch1-1;
595             while ((ch0=trav_BSet (parse_info->charset, charset, ch1)) != -1)
596             {
597                 tn1 = mk_Tnode(parse_info);
598                 tn1->pos = OR;
599                 tn1->u.p[0] = tn0;
600                 tn0 = tn1;
601                 tn1 = tn0->u.p[1] = mk_Tnode(parse_info);
602                 tn1->u.ch[0] = ch0;
603                 tn1->pos = ++(parse_info->position);
604                 if ((ch1 = travi_BSet (parse_info->charset, charset,
605                                        ch0+1)) == -1)
606                 {
607                     tn1->u.ch[1] = parse_info->charset->size;
608                     break;
609                 }
610                 tn1->u.ch[1] = ch1-1;
611             }
612         }
613     }
614     return tn0;
615 }
616
617 static void del_followpos (struct DFA_parse *parse_info)
618 {
619     ifree (parse_info->followpos);
620 }
621
622 static void init_pos (struct DFA_parse *parse_info)
623 {
624     parse_info->posar = (struct Tnode **) imalloc (sizeof(struct Tnode*) 
625                                        * (1+parse_info->position));
626 }
627
628 static void del_pos (struct DFA_parse *parse_info)
629 {
630     ifree (parse_info->posar);
631 }
632
633 static void add_follow (struct DFA_parse *parse_info,
634                         DFASet lastpos, DFASet firstpos)
635 {
636     while (lastpos)
637     {
638         parse_info->followpos[lastpos->value] = 
639             union_DFASet (parse_info->poset,
640                        parse_info->followpos[lastpos->value], firstpos);
641         lastpos = lastpos->next;
642     }                                                            
643 }
644
645 static void dfa_trav (struct DFA_parse *parse_info, struct Tnode *n)
646 {
647     struct Tnode **posar = parse_info->posar;
648     DFASetType poset = parse_info->poset;
649     
650     switch (n->pos)
651     {
652     case CAT:
653         dfa_trav (parse_info, n->u.p[0]);
654         dfa_trav (parse_info, n->u.p[1]);
655         n->nullable = n->u.p[0]->nullable & n->u.p[1]->nullable;
656         n->firstpos = mk_DFASet (poset);
657         n->firstpos = union_DFASet (poset, n->firstpos, n->u.p[0]->firstpos);
658         if (n->u.p[0]->nullable)
659             n->firstpos = union_DFASet (poset, n->firstpos, n->u.p[1]->firstpos);
660         n->lastpos = mk_DFASet (poset);
661         n->lastpos = union_DFASet (poset, n->lastpos, n->u.p[1]->lastpos);
662         if (n->u.p[1]->nullable)
663             n->lastpos = union_DFASet (poset, n->lastpos, n->u.p[0]->lastpos);
664
665         add_follow (parse_info, n->u.p[0]->lastpos, n->u.p[1]->firstpos);
666
667         n->u.p[0]->firstpos = rm_DFASet (poset, n->u.p[0]->firstpos);
668         n->u.p[0]->lastpos = rm_DFASet (poset, n->u.p[0]->lastpos);
669         n->u.p[1]->firstpos = rm_DFASet (poset, n->u.p[1]->firstpos);
670         n->u.p[1]->lastpos = rm_DFASet (poset, n->u.p[1]->lastpos);
671         if (debug_dfa_trav)
672             printf ("CAT");
673         break;
674     case OR:
675         dfa_trav (parse_info, n->u.p[0]);
676         dfa_trav (parse_info, n->u.p[1]);
677         n->nullable = n->u.p[0]->nullable | n->u.p[1]->nullable;
678
679         n->firstpos = merge_DFASet (poset, n->u.p[0]->firstpos,
680                                  n->u.p[1]->firstpos);
681         n->lastpos = merge_DFASet (poset, n->u.p[0]->lastpos,
682                                 n->u.p[1]->lastpos);
683         n->u.p[0]->firstpos = rm_DFASet (poset, n->u.p[0]->firstpos);
684         n->u.p[0]->lastpos = rm_DFASet (poset, n->u.p[0]->lastpos);
685         n->u.p[1]->firstpos = rm_DFASet (poset, n->u.p[1]->firstpos);
686         n->u.p[1]->lastpos = rm_DFASet (poset, n->u.p[1]->lastpos);
687         if (debug_dfa_trav)
688             printf ("OR");
689         break;
690     case PLUS:
691         dfa_trav (parse_info, n->u.p[0]);
692         n->nullable = n->u.p[0]->nullable;
693         n->firstpos = n->u.p[0]->firstpos;
694         n->lastpos = n->u.p[0]->lastpos;
695         add_follow (parse_info, n->lastpos, n->firstpos);
696         if (debug_dfa_trav)
697             printf ("PLUS");
698         break;
699     case STAR:
700         dfa_trav (parse_info, n->u.p[0]);
701         n->nullable = 1;
702         n->firstpos = n->u.p[0]->firstpos;
703         n->lastpos = n->u.p[0]->lastpos;
704         add_follow (parse_info, n->lastpos, n->firstpos);
705         if (debug_dfa_trav)
706             printf ("STAR");
707         break;
708     case EPSILON:
709         n->nullable = 1;
710         n->lastpos = mk_DFASet (poset);
711         n->firstpos = mk_DFASet (poset);
712         if (debug_dfa_trav)
713             printf ("EPSILON");
714         break;
715     default:
716         posar[n->pos] = n;
717         n->nullable = 0;
718         n->firstpos = mk_DFASet (poset);
719         n->firstpos = add_DFASet (poset, n->firstpos, n->pos);
720         n->lastpos = mk_DFASet (poset);
721         n->lastpos = add_DFASet (poset, n->lastpos, n->pos);
722         if (debug_dfa_trav)
723         {
724             if (n->u.ch[0] < 0)
725                 printf ("#%d (n#%d)", -n->u.ch[0], -n->u.ch[1]);
726             else if (n->u.ch[1] > n->u.ch[0])
727             {
728                 putchar ('[');
729                 out_char (n->u.ch[0]);
730                 if (n->u.ch[1] > n->u.ch[0]+1)
731                     putchar ('-');
732                 out_char (n->u.ch[1]);
733                 putchar (']');
734             }
735             else
736                 out_char (n->u.ch[0]);
737         }
738     }
739     if (debug_dfa_trav)
740     {
741         printf ("\n nullable : %c\n", n->nullable ? '1' : '0');
742         printf (" firstpos :");
743         pr_DFASet (poset, n->firstpos);
744         printf (" lastpos  :");
745         pr_DFASet (poset, n->lastpos);
746     }
747 }
748
749 static void init_followpos (struct DFA_parse *parse_info)
750 {
751     DFASet *fa;
752     int i;
753     parse_info->followpos = fa =
754         (DFASet *) imalloc (sizeof(DFASet) * (1+parse_info->position));
755     for (i = parse_info->position+1; --i >= 0; fa++)
756         *fa = mk_DFASet (parse_info->poset);
757 }
758
759 static void mk_dfa_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
760 {
761     int i, j, c;
762     int max_char;
763     short *pos, *pos_i;
764     DFASet tran_set;
765     int char_0, char_1;
766     struct DFA_state *dfa_from, *dfa_to;
767     struct Tnode **posar;
768     DFASetType poset;
769     DFASet *followpos;
770
771     assert (parse_info);
772
773     posar = parse_info->posar;
774     max_char = parse_info->charset->size;
775     pos = (short *) imalloc (sizeof(*pos) * (parse_info->position+1));
776
777     tran_set = cp_DFASet (parse_info->poset, parse_info->root->firstpos);
778     i = add_DFA_state (dfas, &tran_set, &dfa_from);
779     assert (i);
780     dfa_from->rule_no = 0;
781     poset = parse_info->poset;
782     followpos = parse_info->followpos;
783     while ((dfa_from = get_DFA_state (dfas)))
784     {
785         pos_i = pos;
786         j = i = 0;
787         for (tran_set = dfa_from->set; tran_set; tran_set = tran_set->next)
788             if ((c = posar[tran_set->value]->u.ch[0]) >= 0 && c <= max_char) 
789                 *pos_i++ = tran_set->value;
790             else if (c < 0)
791             {
792                 if (i == 0 || c > i)
793                     i = c;
794                 c = posar[tran_set->value]->u.ch[1];
795                 if (j == 0 || c > j)
796                     j = c;
797             }
798         *pos_i = -1;
799         dfa_from->rule_no = -i;
800         dfa_from->rule_nno = -j;
801
802         for (char_1 = 0; char_1 <= max_char; char_1++)
803         {
804             char_0 = max_char+1;
805             for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
806                 if (posar[i]->u.ch[1] >= char_1 
807                     && (c=posar[i]->u.ch[0]) < char_0)
808                 {
809                     if (c < char_1)
810                         char_0 = char_1;
811                     else
812                         char_0 = c;
813                 }
814
815             if (char_0 > max_char)
816                 break;
817
818             char_1 = max_char;
819                 
820             tran_set = mk_DFASet (poset);
821             for (pos_i = pos; (i = *pos_i) != -1; ++pos_i)
822             {
823                 if ((c=posar[i]->u.ch[0]) > char_0 && c <= char_1)
824                     char_1 = c - 1;                /* forward chunk */
825                 else if ((c=posar[i]->u.ch[1]) >= char_0 && c < char_1)
826                     char_1 = c;                    /* backward chunk */
827                 if (posar[i]->u.ch[1] >= char_0 && posar[i]->u.ch[0] <= char_0)
828                     tran_set = union_DFASet (poset, tran_set, followpos[i]);
829             }
830             if (tran_set)
831             {
832                 add_DFA_state (dfas, &tran_set, &dfa_to);
833                 add_DFA_tran (dfas, dfa_from, char_0, char_1, dfa_to->no);
834             }
835         }
836     }
837     ifree (pos);
838     sort_DFA_states (dfas);
839 }
840
841 static void pr_tran (struct DFA_parse *parse_info, struct DFA_states *dfas)
842 {
843     struct DFA_state *s;
844     struct DFA_tran *tran;
845     int prev_no, i, c, no;
846
847     for (no=0; no < dfas->no; ++no)
848     {
849         s = dfas->sortarray[no];
850         assert (s->no == no);
851         printf ("DFA state %d", no);
852         if (s->rule_no)
853             printf ("#%d", s->rule_no);
854         if (s->rule_nno)
855             printf (" #%d", s->rule_nno);
856
857         putchar (':');
858         pr_DFASet (parse_info->poset, s->set);
859         prev_no = -1;
860         for (i=s->tran_no, tran=s->trans; --i >= 0; tran++)
861         {
862             if (prev_no != tran->to)
863             {
864                 if (prev_no != -1)
865                     printf ("]\n");
866                 printf (" goto %d on [", tran->to);
867                 prev_no = tran->to;
868             }
869             for (c = tran->ch[0]; c <= tran->ch[1]; c++)
870                 printf ("%s", str_char(c));
871         }
872         if (prev_no != -1)
873             printf ("]\n");
874         putchar ('\n');
875     }
876 }
877
878 static void pr_verbose (struct DFA_parse *parse_info, struct DFA_states *dfas)
879 {
880     long i, j;
881     int k;
882     printf ("%d/%d tree nodes used, %ld bytes each\n",
883         parse_info->use_Tnode, parse_info->max_Tnode, (long) sizeof (struct Tnode));
884     k = inf_BSetHandle (parse_info->charset, &i, &j);
885     printf ("%ld/%ld character sets, %ld bytes each\n",
886             i/k, j/k, (long) k*sizeof(BSetWord));
887     k = inf_DFASetType (parse_info->poset, &i, &j);
888     printf ("%ld/%ld poset items, %d bytes each\n", i, j, k);
889     printf ("%d DFA states\n", dfas->no);
890 }
891
892 static void pr_followpos (struct DFA_parse *parse_info)
893 {
894     struct Tnode **posar = parse_info->posar;
895     int i;
896     printf ("\nfollowsets:\n");
897     for (i=1; i <= parse_info->position; i++)
898     {
899         printf ("%3d:", i);
900         pr_DFASet (parse_info->poset, parse_info->followpos[i]);
901         putchar ('\t');
902
903         if (posar[i]->u.ch[0] < 0)
904             printf ("#%d", -posar[i]->u.ch[0]);
905         else if (posar[i]->u.ch[1] > posar[i]->u.ch[0])
906         {
907             putchar ('[');
908             out_char (posar[i]->u.ch[0]);
909             if (posar[i]->u.ch[1] > posar[i]->u.ch[0]+1)
910                 putchar ('-');
911             out_char (posar[i]->u.ch[1]);
912             putchar (']');
913         }
914         else
915             out_char (posar[i]->u.ch[0]);
916         putchar ('\n');
917     }
918     putchar ('\n');
919 }
920
921 void dfa_parse_cmap_clean (struct DFA *d)
922 {
923     struct DFA_parse *dfa = d->parse_info;
924
925     assert (dfa);
926     if (!dfa->charMap)
927     {
928         dfa->charMapSize = 7;
929         dfa->charMap = (int *)
930             imalloc (dfa->charMapSize * sizeof(*dfa->charMap));
931     }
932     dfa->charMap[0] = 0;
933 }
934
935 void dfa_parse_cmap_new (struct DFA *d, const int *cmap)
936 {
937     struct DFA_parse *dfa = d->parse_info;
938     const int *cp;
939     int size;
940
941     assert (dfa);
942     for (cp = cmap; *cp; cp += 2)
943         ;
944     size = cp - cmap + 1;
945     if (size > dfa->charMapSize)
946     {
947         if (dfa->charMap)
948             ifree (dfa->charMap);
949         dfa->charMapSize = size;
950         dfa->charMap = (int *) imalloc (size * sizeof(*dfa->charMap));
951     }
952     memcpy (dfa->charMap, cmap, size * sizeof(*dfa->charMap));
953 }
954
955 void dfa_parse_cmap_del (struct DFA *d, int from)
956 {
957     struct DFA_parse *dfa = d->parse_info;
958     int *cc;
959
960     assert (dfa);
961     for (cc = dfa->charMap; *cc; cc += 2)
962         if (*cc == from)
963         {
964             while ((cc[0] = cc[2]))
965             {
966                 cc[1] = cc[3]; 
967                 cc += 2;
968             }
969             break;
970         }
971 }
972
973 void dfa_parse_cmap_add (struct DFA *d, int from, int to)
974 {
975     struct DFA_parse *dfa = d->parse_info;
976     int *cc;
977     int indx, size;
978
979     assert (dfa);
980     for (cc = dfa->charMap; *cc; cc += 2)
981         if (*cc == from)
982         {
983             cc[1] = to;
984             return ;
985         }
986     indx = cc - dfa->charMap;
987     size = dfa->charMapSize;
988     if (indx >= size)
989     {
990         int *cn = (int *) imalloc ((size+16) * sizeof(*dfa->charMap));
991         memcpy (cn, dfa->charMap, indx*sizeof(*dfa->charMap));
992         ifree (dfa->charMap);
993         dfa->charMap = cn;
994         dfa->charMapSize = size+16;
995     }
996     dfa->charMap[indx] = from;
997     dfa->charMap[indx+1] = to;
998     dfa->charMap[indx+2] = 0;
999 }
1000
1001 void dfa_parse_cmap_thompson (struct DFA *d)
1002 {
1003     static int thompson_chars[] =
1004     {
1005         '*',  L_CLOS0,
1006         '+',  L_CLOS1,
1007         '|',  L_ALT,
1008         '^',  L_START,
1009         '$',  L_END,
1010         '?',  L_QUEST,
1011         '.',  L_ANY,
1012         '(',  L_LP,
1013         ')',  L_RP,
1014         ' ',  0,
1015         '\t', 0,
1016         '\n', 0,
1017         0
1018     };
1019     dfa_parse_cmap_new (d, thompson_chars);
1020 }
1021
1022 static struct DFA_parse *dfa_parse_init (void)
1023 {
1024     struct DFA_parse *parse_info = 
1025         (struct DFA_parse *) imalloc (sizeof (struct DFA_parse));
1026
1027     parse_info->charset = mk_BSetHandle (255, 20);
1028     parse_info->position = 0;
1029     parse_info->rule = 0;
1030     parse_info->root = NULL;
1031
1032     /* initialize the anyset which by default does not include \n */
1033     parse_info->anyset = mk_BSet (&parse_info->charset);
1034     res_BSet (parse_info->charset, parse_info->anyset);
1035     add_BSet (parse_info->charset, parse_info->anyset, '\n');
1036     com_BSet (parse_info->charset, parse_info->anyset);
1037
1038     parse_info->use_Tnode = parse_info->max_Tnode = 0;
1039     parse_info->start = parse_info->end = NULL;
1040     parse_info->charMap = NULL;
1041     parse_info->charMapSize = 0;
1042     parse_info->cmap = NULL;
1043     return parse_info;
1044 }
1045
1046 static void rm_dfa_parse (struct DFA_parse **dfap)
1047 {
1048     struct DFA_parse *parse_info = *dfap;
1049     assert (parse_info);
1050     term_Tnode(parse_info);
1051     rm_BSetHandle (&parse_info->charset);
1052     ifree (parse_info->charMap);
1053     ifree (parse_info);
1054     *dfap = NULL;
1055 }
1056
1057 static struct DFA_states *mk_dfas (struct DFA_parse *dfap, int poset_chunk)
1058 {
1059     struct DFA_states *dfas;
1060     struct DFA_parse *parse_info = dfap;
1061
1062     assert (poset_chunk > 10);
1063     assert (dfap);
1064
1065     parse_info->poset = mk_DFASetType (poset_chunk);
1066     init_pos(parse_info);
1067     init_followpos(parse_info);
1068     assert (parse_info->root);
1069     dfa_trav (parse_info, parse_info->root);
1070
1071     if (debug_dfa_followpos)
1072         pr_followpos(parse_info);
1073     init_DFA_states (&dfas, parse_info->poset, (int) (STATE_HASH));
1074     mk_dfa_tran (parse_info, dfas);
1075     if (debug_dfa_tran)
1076     {
1077         pr_tran (parse_info, dfas);
1078     }
1079     if (dfa_verbose)
1080         pr_verbose (parse_info, dfas);
1081     del_pos(parse_info);
1082     del_followpos(parse_info);
1083     rm_DFASetType (parse_info->poset);
1084     return dfas;
1085 }
1086
1087 struct DFA *dfa_init (void)
1088 {
1089     struct DFA *dfa;
1090
1091     dfa = (struct DFA *) imalloc (sizeof(*dfa));
1092     dfa->parse_info = dfa_parse_init ();
1093     dfa->state_info = NULL;
1094     dfa->states = NULL;
1095     dfa_parse_cmap_thompson (dfa);
1096     return dfa;
1097 }
1098
1099 void dfa_anyset_includes_nl(struct DFA *dfa)
1100 {
1101     add_BSet (dfa->parse_info->charset, dfa->parse_info->anyset, '\n');
1102 }
1103
1104 void dfa_set_cmap (struct DFA *dfa, void *vp,
1105                    const char **(*cmap)(void *vp, const char **from, int len))
1106 {
1107     dfa->parse_info->cmap = cmap;
1108     dfa->parse_info->cmap_data = vp;
1109 }
1110
1111 int dfa_get_last_rule (struct DFA *dfa)
1112 {
1113     return dfa->parse_info->rule;
1114 }
1115
1116 int dfa_parse (struct DFA *dfa, const char **pattern)
1117 {
1118     struct Tnode *top;
1119     struct DFA_parse *parse_info;
1120
1121     assert (dfa);
1122     assert (dfa->parse_info);
1123     parse_info = dfa->parse_info;
1124
1125     do_parse (parse_info, pattern, &top);
1126     if (parse_info->err_code)
1127         return parse_info->err_code;
1128     if ( !dfa->parse_info->root )
1129         dfa->parse_info->root = top;
1130     else
1131     {
1132         struct Tnode *n;
1133
1134         n = mk_Tnode (parse_info);
1135         n->pos = OR;
1136         n->u.p[0] = dfa->parse_info->root;
1137         n->u.p[1] = top;
1138         dfa->parse_info->root = n;
1139     }
1140     return 0;
1141 }
1142
1143 void dfa_mkstate (struct DFA *dfa)
1144 {
1145     assert (dfa);
1146
1147     dfa->state_info = mk_dfas (dfa->parse_info, POSET_CHUNK);
1148     dfa->no_states = dfa->state_info->no;
1149     dfa->states = dfa->state_info->sortarray;
1150     rm_dfa_parse (&dfa->parse_info);
1151 }
1152
1153 void dfa_delete (struct DFA **dfap)
1154 {
1155     assert (dfap);
1156     assert (*dfap);
1157     if ((*dfap)->parse_info)
1158         rm_dfa_parse (&(*dfap)->parse_info);
1159     if ((*dfap)->state_info)
1160         rm_DFA_states (&(*dfap)->state_info);
1161     ifree (*dfap);
1162     *dfap = NULL;
1163 }
1164 /*
1165  * Local variables:
1166  * c-basic-offset: 4
1167  * c-file-style: "Stroustrup"
1168  * indent-tabs-mode: nil
1169  * End:
1170  * vim: shiftwidth=4 tabstop=8 expandtab
1171  */
1172