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