dfa/dfa.c

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