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