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