dfa/dfa.c

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