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