dfa/dfa.c

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