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