dfa/dfa.c

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