lib/rx.c

   1 /*      Copyright (C) 1992, 1993, 1994, 1995 Free Software Foundation, Inc.
   2
   3 This file is part of the librx library.
   4
   5 Librx is free software; you can redistribute it and/or modify it under
   6 the terms of the GNU Library General Public License as published by
   7 the Free Software Foundation; either version 2, or (at your option)
   8 any later version.
   9
  10 Librx is distributed in the hope that it will be useful, but WITHOUT
  11 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  12 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  13 for more details.
  14
  15 You should have received a copy of the GNU Library General Public
  16 License along with this software; see the file COPYING.LIB.  If not,
  17 write to the Free Software Foundation, 675 Mass Ave, Cambridge, MA
  18 02139, USA.  */
  19
  20 /* NOTE!!!  AIX is so losing it requires this to be the first thing in the
  21  * file.
  22  * Do not put ANYTHING before it!
  23  */
  24 #if !defined (__GNUC__) && defined (_AIX)
  25  #pragma alloca
  26 #endif
  27
  28 /* To make linux happy? */
  29 #ifndef _GNU_SOURCE
  30 #define _GNU_SOURCE
  31 #endif
  32
  33 #if HAVE_CONFIG_H
  34 #include <config.h>
  35 #endif
  36 \f
  37 const char *rx_version_string = "GNU Rx version 0.07.2";
  38
  39                         /* ``Too hard!''
  40                          *          -- anon.
  41                          */
  42
  43 \f
  44 #include <stdio.h>
  45 #include <ctype.h>
  46 #ifndef isgraph
  47 #define isgraph(c) (isprint (c) && !isspace (c))
  48 #endif
  49 #ifndef isblank
  50 #define isblank(c) ((c) == ' ' || (c) == '\t')
  51 #endif
  52
  53 #include <sys/types.h>
  54
  55 #undef MAX
  56 #undef MIN
  57 #define MAX(a, b) ((a) > (b) ? (a) : (b))
  58 #define MIN(a, b) ((a) < (b) ? (a) : (b))
  59
  60 typedef char boolean;
  61 #define false 0
  62 #define true 1
  63
  64 #ifndef __GCC__
  65 #undef __inline__
  66 #define __inline__
  67 #endif
  68
  69 /* Emacs already defines alloca, sometimes.  */
  70 #ifndef alloca
  71
  72 /* Make alloca work the best possible way.  */
  73 #ifdef __GNUC__
  74 #define alloca __builtin_alloca
  75 #else /* not __GNUC__ */
  76 #if HAVE_ALLOCA_H
  77 #include <alloca.h>
  78 #else /* not __GNUC__ or HAVE_ALLOCA_H */
  79 #ifndef _AIX /* Already did AIX, up at the top.  */
  80 char *alloca ();
  81 #endif /* not _AIX */
  82 #endif /* not HAVE_ALLOCA_H */
  83 #endif /* not __GNUC__ */
  84
  85 #endif /* not alloca */
  86
  87 /* Memory management and stuff for emacs. */
  88
  89 #define CHARBITS 8
  90 #define remalloc(M, S) (M ? realloc (M, S) : malloc (S))
  91
  92
  93 /* Should we use malloc or alloca?  If REGEX_MALLOC is not defined, we
  94  * use `alloca' instead of `malloc' for the backtracking stack.
  95  *
  96  * Emacs will die miserably if we don't do this.
  97  */
  98
  99 #ifdef REGEX_MALLOC
 100 #define REGEX_ALLOCATE malloc
 101 #else /* not REGEX_MALLOC  */
 102 #define REGEX_ALLOCATE alloca
 103 #endif /* not REGEX_MALLOC */
 104
 105
 106 #ifdef RX_WANT_RX_DEFS
 107 #define RX_DECL extern
 108 #define RX_DEF_QUAL
 109 #else
 110 #define RX_WANT_RX_DEFS
 111 #define RX_DECL static
 112 #define RX_DEF_QUAL static
 113 #endif
 114 #include "rx.h"
 115 #undef RX_DECL
 116 #define RX_DECL RX_DEF_QUAL
 117
 118
 119 #ifndef emacs
 120
 121 #ifdef SYNTAX_TABLE
 122 extern char *re_syntax_table;
 123 #else /* not SYNTAX_TABLE */
 124
 125 RX_DECL char re_syntax_table[CHAR_SET_SIZE];
 126
 127 #ifdef __STDC__
 128 static void
 129 init_syntax_once (void)
 130 #else
 131 static void
 132 init_syntax_once ()
 133 #endif
 134 {
 135    register int c;
 136    static int done = 0;
 137
 138    if (done)
 139      return;
 140
 141    bzero (re_syntax_table, sizeof re_syntax_table);
 142
 143    for (c = 'a'; c <= 'z'; c++)
 144      re_syntax_table[c] = Sword;
 145
 146    for (c = 'A'; c <= 'Z'; c++)
 147      re_syntax_table[c] = Sword;
 148
 149    for (c = '0'; c <= '9'; c++)
 150      re_syntax_table[c] = Sword;
 151
 152    re_syntax_table['_'] = Sword;
 153
 154    done = 1;
 155 }
 156 #endif /* not SYNTAX_TABLE */
 157 #endif /* not emacs */
 158 \f
 159 /* Compile with `-DRX_DEBUG' and use the following flags.
 160  *
 161  * Debugging flags:
 162  *      rx_debug - print information as a regexp is compiled
 163  *      rx_debug_trace - print information as a regexp is executed
 164  */
 165
 166 #ifdef RX_DEBUG
 167
 168 int rx_debug_compile = 0;
 169 int rx_debug_trace = 0;
 170 static struct re_pattern_buffer * dbug_rxb = 0;
 171
 172 #ifdef __STDC__
 173 typedef void (*side_effect_printer) (struct rx *, void *, FILE *);
 174 #else
 175 typedef void (*side_effect_printer) ();
 176 #endif
 177
 178 #ifdef __STDC__
 179 static void print_cset (struct rx *rx, rx_Bitset cset, FILE * fp);
 180 #else
 181 static void print_cset ();
 182 #endif
 183
 184 #ifdef __STDC__
 185 static void
 186 print_rexp (struct rx *rx,
 187             struct rexp_node *node, int depth,
 188             side_effect_printer seprint, FILE * fp)
 189 #else
 190 static void
 191 print_rexp (rx, node, depth, seprint, fp)
 192      struct rx *rx;
 193      struct rexp_node *node;
 194      int depth;
 195      side_effect_printer seprint;
 196      FILE * fp;
 197 #endif
 198 {
 199   if (!node)
 200     return;
 201   else
 202     {
 203       switch (node->type)
 204         {
 205         case r_cset:
 206           {
 207             fprintf (fp, "%*s", depth, "");
 208             print_cset (rx, node->params.cset, fp);
 209             fputc ('\n', fp);
 210             break;
 211           }
 212
 213         case r_opt:
 214         case r_star:
 215           fprintf (fp, "%*s%s\n", depth, "",
 216                    node->type == r_opt ? "opt" : "star");
 217           print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp);
 218           break;
 219
 220         case r_2phase_star:
 221           fprintf (fp, "%*s2phase star\n", depth, "");
 222           print_rexp (rx, node->params.pair.right, depth + 3, seprint, fp);
 223           print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp);
 224           break;
 225
 226
 227         case r_alternate:
 228         case r_concat:
 229           fprintf (fp, "%*s%s\n", depth, "",
 230                    node->type == r_alternate ? "alt" : "concat");
 231           print_rexp (rx, node->params.pair.left, depth + 3, seprint, fp);
 232           print_rexp (rx, node->params.pair.right, depth + 3, seprint, fp);
 233           break;
 234         case r_side_effect:
 235           fprintf (fp, "%*sSide effect: ", depth, "");
 236           seprint (rx, node->params.side_effect, fp);
 237           fputc ('\n', fp);
 238         }
 239     }
 240 }
 241
 242 #ifdef __STDC__
 243 static void
 244 print_nfa (struct rx * rx,
 245            struct rx_nfa_state * n,
 246            side_effect_printer seprint, FILE * fp)
 247 #else
 248 static void
 249 print_nfa (rx, n, seprint, fp)
 250      struct rx * rx;
 251      struct rx_nfa_state * n;
 252      side_effect_printer seprint;
 253      FILE * fp;
 254 #endif
 255 {
 256   while (n)
 257     {
 258       struct rx_nfa_edge *e = n->edges;
 259       struct rx_possible_future *ec = n->futures;
 260       fprintf (fp, "node %d %s\n", n->id,
 261                n->is_final ? "final" : (n->is_start ? "start" : ""));
 262       while (e)
 263         {
 264           fprintf (fp, "   edge to %d, ", e->dest->id);
 265           switch (e->type)
 266             {
 267             case ne_epsilon:
 268               fprintf (fp, "epsilon\n");
 269               break;
 270             case ne_side_effect:
 271               fprintf (fp, "side effect ");
 272               seprint (rx, e->params.side_effect, fp);
 273               fputc ('\n', fp);
 274               break;
 275             case ne_cset:
 276               fprintf (fp, "cset ");
 277               print_cset (rx, e->params.cset, fp);
 278               fputc ('\n', fp);
 279               break;
 280             }
 281           e = e->next;
 282         }
 283
 284       while (ec)
 285         {
 286           int x;
 287           struct rx_nfa_state_set * s;
 288           struct rx_se_list * l;
 289           fprintf (fp, "   eclosure to {");
 290           for (s = ec->destset; s; s = s->cdr)
 291             fprintf (fp, "%d ", s->car->id);
 292           fprintf (fp, "} (");
 293           for (l = ec->effects; l; l = l->cdr)
 294             {
 295               seprint (rx, l->car, fp);
 296               fputc (' ', fp);
 297             }
 298           fprintf (fp, ")\n");
 299           ec = ec->next;
 300         }
 301       n = n->next;
 302     }
 303 }
 304
 305 static char * efnames [] =
 306 {
 307   "bogon",
 308   "re_se_try",
 309   "re_se_pushback",
 310   "re_se_push0",
 311   "re_se_pushpos",
 312   "re_se_chkpos",
 313   "re_se_poppos",
 314   "re_se_at_dot",
 315   "re_se_syntax",
 316   "re_se_not_syntax",
 317   "re_se_begbuf",
 318   "re_se_hat",
 319   "re_se_wordbeg",
 320   "re_se_wordbound",
 321   "re_se_notwordbound",
 322   "re_se_wordend",
 323   "re_se_endbuf",
 324   "re_se_dollar",
 325   "re_se_fail",
 326 };
 327
 328 static char * efnames2[] =
 329 {
 330   "re_se_win",
 331   "re_se_lparen",
 332   "re_se_rparen",
 333   "re_se_backref",
 334   "re_se_iter",
 335   "re_se_end_iter",
 336   "re_se_tv"
 337 };
 338
 339 static char * inx_names[] =
 340 {
 341   "rx_backtrack_point",
 342   "rx_do_side_effects",
 343   "rx_cache_miss",
 344   "rx_next_char",
 345   "rx_backtrack",
 346   "rx_error_inx",
 347   "rx_num_instructions"
 348 };
 349
 350
 351 #ifdef __STDC__
 352 static void
 353 re_seprint (struct rx * rx, void * effect, FILE * fp)
 354 #else
 355 static void
 356 re_seprint (rx, effect, fp)
 357      struct rx * rx;
 358      void * effect;
 359      FILE * fp;
 360 #endif
 361 {
 362   if ((int)effect < 0)
 363     fputs (efnames[-(int)effect], fp);
 364   else if (dbug_rxb)
 365     {
 366       struct re_se_params * p = &dbug_rxb->se_params[(int)effect];
 367       fprintf (fp, "%s(%d,%d)", efnames2[p->se], p->op1, p->op2);
 368     }
 369   else
 370     fprintf (fp, "[complex op # %d]", (int)effect);
 371 }
 372
 373
 374 /* These are so the regex.c regression tests will compile. */
 375 void
 376 print_compiled_pattern (rxb)
 377      struct re_pattern_buffer * rxb;
 378 {
 379 }
 380
 381 void
 382 print_fastmap (fm)
 383      char * fm;
 384 {
 385 }
 386
 387 #endif /* RX_DEBUG */
 388
 389 \f
 390
 391 /* This page: Bitsets.  Completely unintersting. */
 392
 393 #ifdef __STDC__
 394 RX_DECL int
 395 rx_bitset_is_equal (int size, rx_Bitset a, rx_Bitset b)
 396 #else
 397 RX_DECL int
 398 rx_bitset_is_equal (size, a, b)
 399      int size;
 400      rx_Bitset a;
 401      rx_Bitset b;
 402 #endif
 403 {
 404   int x;
 405   RX_subset s = b[0];
 406   b[0] = ~a[0];
 407
 408   for (x = rx_bitset_numb_subsets(size) - 1; a[x] == b[x]; --x)
 409     ;
 410
 411   b[0] = s;
 412   return !x && s == a[0];
 413 }
 414
 415 #ifdef __STDC__
 416 RX_DECL int
 417 rx_bitset_is_subset (int size, rx_Bitset a, rx_Bitset b)
 418 #else
 419 RX_DECL int
 420 rx_bitset_is_subset (size, a, b)
 421      int size;
 422      rx_Bitset a;
 423      rx_Bitset b;
 424 #endif
 425 {
 426   int x = rx_bitset_numb_subsets(size) - 1;
 427   while (x-- && (a[x] & b[x]) == a[x]);
 428   return x == -1;
 429 }
 430
 431
 432 #ifdef __STDC__
 433 RX_DECL int
 434 rx_bitset_empty (int size, rx_Bitset set)
 435 #else
 436 RX_DECL int
 437 rx_bitset_empty (size, set)
 438      int size;
 439      rx_Bitset set;
 440 #endif
 441 {
 442   int x;
 443   RX_subset s = set[0];
 444   set[0] = 1;
 445   for (x = rx_bitset_numb_subsets(size) - 1; !set[x]; --x)
 446     ;
 447   set[0] = s;
 448   return !s;
 449 }
 450
 451 #ifdef __STDC__
 452 RX_DECL void
 453 rx_bitset_null (int size, rx_Bitset b)
 454 #else
 455 RX_DECL void
 456 rx_bitset_null (size, b)
 457      int size;
 458      rx_Bitset b;
 459 #endif
 460 {
 461   bzero (b, rx_sizeof_bitset(size));
 462 }
 463
 464
 465 #ifdef __STDC__
 466 RX_DECL void
 467 rx_bitset_universe (int size, rx_Bitset b)
 468 #else
 469 RX_DECL void
 470 rx_bitset_universe (size, b)
 471      int size;
 472      rx_Bitset b;
 473 #endif
 474 {
 475   int x = rx_bitset_numb_subsets (size);
 476   while (x--)
 477     *b++ = ~(RX_subset)0;
 478 }
 479
 480
 481 #ifdef __STDC__
 482 RX_DECL void
 483 rx_bitset_complement (int size, rx_Bitset b)
 484 #else
 485 RX_DECL void
 486 rx_bitset_complement (size, b)
 487      int size;
 488      rx_Bitset b;
 489 #endif
 490 {
 491   int x = rx_bitset_numb_subsets (size);
 492   while (x--)
 493     {
 494       *b = ~*b;
 495       ++b;
 496     }
 497 }
 498
 499
 500 #ifdef __STDC__
 501 RX_DECL void
 502 rx_bitset_assign (int size, rx_Bitset a, rx_Bitset b)
 503 #else
 504 RX_DECL void
 505 rx_bitset_assign (size, a, b)
 506      int size;
 507      rx_Bitset a;
 508      rx_Bitset b;
 509 #endif
 510 {
 511   int x;
 512   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 513     a[x] = b[x];
 514 }
 515
 516
 517 #ifdef __STDC__
 518 RX_DECL void
 519 rx_bitset_union (int size, rx_Bitset a, rx_Bitset b)
 520 #else
 521 RX_DECL void
 522 rx_bitset_union (size, a, b)
 523      int size;
 524      rx_Bitset a;
 525      rx_Bitset b;
 526 #endif
 527 {
 528   int x;
 529   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 530     a[x] |= b[x];
 531 }
 532
 533
 534 #ifdef __STDC__
 535 RX_DECL void
 536 rx_bitset_intersection (int size,
 537                         rx_Bitset a, rx_Bitset b)
 538 #else
 539 RX_DECL void
 540 rx_bitset_intersection (size, a, b)
 541      int size;
 542      rx_Bitset a;
 543      rx_Bitset b;
 544 #endif
 545 {
 546   int x;
 547   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 548     a[x] &= b[x];
 549 }
 550
 551
 552 #ifdef __STDC__
 553 RX_DECL void
 554 rx_bitset_difference (int size, rx_Bitset a, rx_Bitset b)
 555 #else
 556 RX_DECL void
 557 rx_bitset_difference (size, a, b)
 558      int size;
 559      rx_Bitset a;
 560      rx_Bitset b;
 561 #endif
 562 {
 563   int x;
 564   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 565     a[x] &=  ~ b[x];
 566 }
 567
 568
 569 #ifdef __STDC__
 570 RX_DECL void
 571 rx_bitset_revdifference (int size,
 572                          rx_Bitset a, rx_Bitset b)
 573 #else
 574 RX_DECL void
 575 rx_bitset_revdifference (size, a, b)
 576      int size;
 577      rx_Bitset a;
 578      rx_Bitset b;
 579 #endif
 580 {
 581   int x;
 582   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 583     a[x] = ~a[x] & b[x];
 584 }
 585
 586 #ifdef __STDC__
 587 RX_DECL void
 588 rx_bitset_xor (int size, rx_Bitset a, rx_Bitset b)
 589 #else
 590 RX_DECL void
 591 rx_bitset_xor (size, a, b)
 592      int size;
 593      rx_Bitset a;
 594      rx_Bitset b;
 595 #endif
 596 {
 597   int x;
 598   for (x = rx_bitset_numb_subsets(size) - 1; x >=0; --x)
 599     a[x] ^= b[x];
 600 }
 601
 602
 603 #ifdef __STDC__
 604 RX_DECL unsigned long
 605 rx_bitset_hash (int size, rx_Bitset b)
 606 #else
 607 RX_DECL unsigned long
 608 rx_bitset_hash (size, b)
 609      int size;
 610      rx_Bitset b;
 611 #endif
 612 {
 613   int x;
 614   unsigned long hash = (unsigned long)rx_bitset_hash;
 615
 616   for (x = rx_bitset_numb_subsets(size) - 1; x >= 0; --x)
 617     hash ^= rx_bitset_subset_val(b, x);
 618
 619   return hash;
 620 }
 621
 622
 623 RX_DECL RX_subset rx_subset_singletons [RX_subset_bits] =
 624 {
 625   0x1,
 626   0x2,
 627   0x4,
 628   0x8,
 629   0x10,
 630   0x20,
 631   0x40,
 632   0x80,
 633   0x100,
 634   0x200,
 635   0x400,
 636   0x800,
 637   0x1000,
 638   0x2000,
 639   0x4000,
 640   0x8000,
 641   0x10000,
 642   0x20000,
 643   0x40000,
 644   0x80000,
 645   0x100000,
 646   0x200000,
 647   0x400000,
 648   0x800000,
 649   0x1000000,
 650   0x2000000,
 651   0x4000000,
 652   0x8000000,
 653   0x10000000,
 654   0x20000000,
 655   0x40000000,
 656   0x80000000
 657 };
 658
 659 #ifdef RX_DEBUG
 660
 661 #ifdef __STDC__
 662 static void
 663 print_cset (struct rx *rx, rx_Bitset cset, FILE * fp)
 664 #else
 665 static void
 666 print_cset (rx, cset, fp)
 667      struct rx *rx;
 668      rx_Bitset cset;
 669      FILE * fp;
 670 #endif
 671 {
 672   int x;
 673   fputc ('[', fp);
 674   for (x = 0; x < rx->local_cset_size; ++x)
 675     if (RX_bitset_member (cset, x))
 676       {
 677         if (isprint(x))
 678           fputc (x, fp);
 679         else
 680           fprintf (fp, "\\0%o ", x);
 681       }
 682   fputc (']', fp);
 683 }
 684
 685 #endif /*  RX_DEBUG */
 686
 687 \f
 688
 689 static unsigned long rx_hash_masks[4] =
 690 {
 691   0x12488421,
 692   0x96699669,
 693   0xbe7dd7eb,
 694   0xffffffff
 695 };
 696
 697
 698 /* Hash tables */
 699 #ifdef __STDC__
 700 RX_DECL struct rx_hash_item *
 701 rx_hash_find (struct rx_hash * table,
 702               unsigned long hash,
 703               void * value,
 704               struct rx_hash_rules * rules)
 705 #else
 706 RX_DECL struct rx_hash_item *
 707 rx_hash_find (table, hash, value, rules)
 708      struct rx_hash * table;
 709      unsigned long hash;
 710      void * value;
 711      struct rx_hash_rules * rules;
 712 #endif
 713 {
 714   rx_hash_eq eq = rules->eq;
 715   int maskc = 0;
 716   long mask = rx_hash_masks [0];
 717   int bucket = (hash & mask) % 13;
 718
 719   while (table->children [bucket])
 720     {
 721       table = table->children [bucket];
 722       ++maskc;
 723       mask = rx_hash_masks[maskc];
 724       bucket = (hash & mask) % 13;
 725     }
 726
 727   {
 728     struct rx_hash_item * it = table->buckets[bucket];
 729     while (it)
 730       if (eq (it->data, value))
 731         return it;
 732       else
 733         it = it->next_same_hash;
 734   }
 735
 736   return 0;
 737 }
 738
 739
 740 #ifdef __STDC__
 741 RX_DECL struct rx_hash_item *
 742 rx_hash_store (struct rx_hash * table,
 743                unsigned long hash,
 744                void * value,
 745                struct rx_hash_rules * rules)
 746 #else
 747 RX_DECL struct rx_hash_item *
 748 rx_hash_store (table, hash, value, rules)
 749      struct rx_hash * table;
 750      unsigned long hash;
 751      void * value;
 752      struct rx_hash_rules * rules;
 753 #endif
 754 {
 755   rx_hash_eq eq = rules->eq;
 756   int maskc = 0;
 757   long mask = rx_hash_masks[0];
 758   int bucket = (hash & mask) % 13;
 759   int depth = 0;
 760
 761   while (table->children [bucket])
 762     {
 763       table = table->children [bucket];
 764       ++maskc;
 765       mask = rx_hash_masks[maskc];
 766       bucket = (hash & mask) % 13;
 767       ++depth;
 768     }
 769
 770   {
 771     struct rx_hash_item * it = table->buckets[bucket];
 772     while (it)
 773       if (eq (it->data, value))
 774         return it;
 775       else
 776         it = it->next_same_hash;
 777   }
 778
 779   {
 780     if (   (depth < 3)
 781         && (table->bucket_size [bucket] >= 4))
 782       {
 783         struct rx_hash * newtab = ((struct rx_hash *)
 784                                    rules->hash_alloc (rules));
 785         if (!newtab)
 786           goto add_to_bucket;
 787         bzero (newtab, sizeof (*newtab));
 788         newtab->parent = table;
 789         {
 790           struct rx_hash_item * them = table->buckets[bucket];
 791           unsigned long newmask = rx_hash_masks[maskc + 1];
 792           while (them)
 793             {
 794               struct rx_hash_item * save = them->next_same_hash;
 795               int new_buck = (them->hash & newmask) % 13;
 796               them->next_same_hash = newtab->buckets[new_buck];
 797               newtab->buckets[new_buck] = them;
 798               them->table = newtab;
 799               them = save;
 800               ++newtab->bucket_size[new_buck];
 801               ++newtab->refs;
 802             }
 803           table->refs = (table->refs - table->bucket_size[bucket] + 1);
 804           table->bucket_size[bucket] = 0;
 805           table->buckets[bucket] = 0;
 806           table->children[bucket] = newtab;
 807           table = newtab;
 808           bucket = (hash & newmask) % 13;
 809         }
 810       }
 811   }
 812  add_to_bucket:
 813   {
 814     struct rx_hash_item  * it = ((struct rx_hash_item *)
 815                                  rules->hash_item_alloc (rules, value));
 816     if (!it)
 817       return 0;
 818     it->hash = hash;
 819     it->table = table;
 820     /* DATA and BINDING are to be set in hash_item_alloc */
 821     it->next_same_hash = table->buckets [bucket];
 822     table->buckets[bucket] = it;
 823     ++table->bucket_size [bucket];
 824     ++table->refs;
 825     return it;
 826   }
 827 }
 828
 829
 830 #ifdef __STDC__
 831 RX_DECL void
 832 rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules)
 833 #else
 834 RX_DECL void
 835 rx_hash_free (it, rules)
 836      struct rx_hash_item * it;
 837      struct rx_hash_rules * rules;
 838 #endif
 839 {
 840   if (it)
 841     {
 842       struct rx_hash * table = it->table;
 843       unsigned long hash = it->hash;
 844       int depth = (table->parent
 845                    ? (table->parent->parent
 846                       ? (table->parent->parent->parent
 847                          ? 3
 848                          : 2)
 849                       : 1)
 850                    : 0);
 851       int bucket = (hash & rx_hash_masks [depth]) % 13;
 852       struct rx_hash_item ** pos = &table->buckets [bucket];
 853
 854       while (*pos != it)
 855         pos = &(*pos)->next_same_hash;
 856       *pos = it->next_same_hash;
 857       rules->free_hash_item (it, rules);
 858       --table->bucket_size[bucket];
 859       --table->refs;
 860       while (!table->refs && depth)
 861         {
 862           struct rx_hash * save = table;
 863           table = table->parent;
 864           --depth;
 865           bucket = (hash & rx_hash_masks [depth]) % 13;
 866           --table->refs;
 867           table->children[bucket] = 0;
 868           rules->free_hash (save, rules);
 869         }
 870     }
 871 }
 872
 873 #ifdef __STDC__
 874 RX_DECL void
 875 rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn,
 876                     struct rx_hash_rules * rules)
 877 #else
 878 RX_DECL void
 879 rx_free_hash_table (tab, freefn, rules)
 880      struct rx_hash * tab;
 881      rx_hash_freefn freefn;
 882      struct rx_hash_rules * rules;
 883 #endif
 884 {
 885   int x;
 886
 887   for (x = 0; x < 13; ++x)
 888     if (tab->children[x])
 889       {
 890         rx_free_hash_table (tab->children[x], freefn, rules);
 891         rules->free_hash (tab->children[x], rules);
 892       }
 893     else
 894       {
 895         struct rx_hash_item * them = tab->buckets[x];
 896         while (them)
 897           {
 898             struct rx_hash_item * that = them;
 899             them = that->next_same_hash;
 900             freefn (that);
 901             rules->free_hash_item (that, rules);
 902           }
 903       }
 904 }
 905
 906
 907 \f
 908 /* Utilities for manipulating bitset represntations of characters sets. */
 909
 910 #ifdef __STDC__
 911 RX_DECL rx_Bitset
 912 rx_cset (struct rx *rx)
 913 #else
 914 RX_DECL rx_Bitset
 915 rx_cset (rx)
 916      struct rx *rx;
 917 #endif
 918 {
 919   rx_Bitset b = (rx_Bitset) malloc (rx_sizeof_bitset (rx->local_cset_size));
 920   if (b)
 921     rx_bitset_null (rx->local_cset_size, b);
 922   return b;
 923 }
 924
 925
 926 #ifdef __STDC__
 927 RX_DECL rx_Bitset
 928 rx_copy_cset (struct rx *rx, rx_Bitset a)
 929 #else
 930 RX_DECL rx_Bitset
 931 rx_copy_cset (rx, a)
 932      struct rx *rx;
 933      rx_Bitset a;
 934 #endif
 935 {
 936   rx_Bitset cs = rx_cset (rx);
 937
 938   if (cs)
 939     rx_bitset_union (rx->local_cset_size, cs, a);
 940
 941   return cs;
 942 }
 943
 944
 945 #ifdef __STDC__
 946 RX_DECL void
 947 rx_free_cset (struct rx * rx, rx_Bitset c)
 948 #else
 949 RX_DECL void
 950 rx_free_cset (rx, c)
 951      struct rx * rx;
 952      rx_Bitset c;
 953 #endif
 954 {
 955   if (c)
 956     free ((char *)c);
 957 }
 958
 959 \f
 960 /* Hash table memory allocation policy for the regexp compiler */
 961
 962 #ifdef __STDC__
 963 static struct rx_hash *
 964 compiler_hash_alloc (struct rx_hash_rules * rules)
 965 #else
 966 static struct rx_hash *
 967 compiler_hash_alloc (rules)
 968      struct rx_hash_rules * rules;
 969 #endif
 970 {
 971   return (struct rx_hash *)malloc (sizeof (struct rx_hash));
 972 }
 973
 974
 975 #ifdef __STDC__
 976 static struct rx_hash_item *
 977 compiler_hash_item_alloc (struct rx_hash_rules * rules, void * value)
 978 #else
 979 static struct rx_hash_item *
 980 compiler_hash_item_alloc (rules, value)
 981      struct rx_hash_rules * rules;
 982      void * value;
 983 #endif
 984 {
 985   struct rx_hash_item * it;
 986   it = (struct rx_hash_item *)malloc (sizeof (*it));
 987   if (it)
 988     {
 989       it->data = value;
 990       it->binding = 0;
 991     }
 992   return it;
 993 }
 994
 995
 996 #ifdef __STDC__
 997 static void
 998 compiler_free_hash (struct rx_hash * tab,
 999                     struct rx_hash_rules * rules)
1000 #else
1001 static void
1002 compiler_free_hash (tab, rules)
1003      struct rx_hash * tab;
1004      struct rx_hash_rules * rules;
1005 #endif
1006 {
1007   free ((char *)tab);
1008 }
1009
1010
1011 #ifdef __STDC__
1012 static void
1013 compiler_free_hash_item (struct rx_hash_item * item,
1014                          struct rx_hash_rules * rules)
1015 #else
1016 static void
1017 compiler_free_hash_item (item, rules)
1018      struct rx_hash_item * item;
1019      struct rx_hash_rules * rules;
1020 #endif
1021 {
1022   free ((char *)item);
1023 }
1024
1025 \f
1026 /* This page: REXP_NODE (expression tree) structures. */
1027
1028 #ifdef __STDC__
1029 RX_DECL struct rexp_node *
1030 rexp_node (struct rx *rx,
1031            enum rexp_node_type type)
1032 #else
1033 RX_DECL struct rexp_node *
1034 rexp_node (rx, type)
1035      struct rx *rx;
1036      enum rexp_node_type type;
1037 #endif
1038 {
1039   struct rexp_node *n;
1040
1041   n = (struct rexp_node *)malloc (sizeof (*n));
1042   bzero (n, sizeof (*n));
1043   if (n)
1044     n->type = type;
1045   return n;
1046 }
1047
1048
1049 /* free_rexp_node assumes that the bitset passed to rx_mk_r_cset
1050  * can be freed using rx_free_cset.
1051  */
1052 #ifdef __STDC__
1053 RX_DECL struct rexp_node *
1054 rx_mk_r_cset (struct rx * rx,
1055               rx_Bitset b)
1056 #else
1057 RX_DECL struct rexp_node *
1058 rx_mk_r_cset (rx, b)
1059      struct rx * rx;
1060      rx_Bitset b;
1061 #endif
1062 {
1063   struct rexp_node * n = rexp_node (rx, r_cset);
1064   if (n)
1065     n->params.cset = b;
1066   return n;
1067 }
1068
1069
1070 #ifdef __STDC__
1071 RX_DECL struct rexp_node *
1072 rx_mk_r_concat (struct rx * rx,
1073                 struct rexp_node * a,
1074                 struct rexp_node * b)
1075 #else
1076 RX_DECL struct rexp_node *
1077 rx_mk_r_concat (rx, a, b)
1078      struct rx * rx;
1079      struct rexp_node * a;
1080      struct rexp_node * b;
1081 #endif
1082 {
1083   struct rexp_node * n = rexp_node (rx, r_concat);
1084   if (n)
1085     {
1086       n->params.pair.left = a;
1087       n->params.pair.right = b;
1088     }
1089   return n;
1090 }
1091
1092
1093 #ifdef __STDC__
1094 RX_DECL struct rexp_node *
1095 rx_mk_r_alternate (struct rx * rx,
1096                    struct rexp_node * a,
1097                    struct rexp_node * b)
1098 #else
1099 RX_DECL struct rexp_node *
1100 rx_mk_r_alternate (rx, a, b)
1101      struct rx * rx;
1102      struct rexp_node * a;
1103      struct rexp_node * b;
1104 #endif
1105 {
1106   struct rexp_node * n = rexp_node (rx, r_alternate);
1107   if (n)
1108     {
1109       n->params.pair.left = a;
1110       n->params.pair.right = b;
1111     }
1112   return n;
1113 }
1114
1115
1116 #ifdef __STDC__
1117 RX_DECL struct rexp_node *
1118 rx_mk_r_opt (struct rx * rx,
1119              struct rexp_node * a)
1120 #else
1121 RX_DECL struct rexp_node *
1122 rx_mk_r_opt (rx, a)
1123      struct rx * rx;
1124      struct rexp_node * a;
1125 #endif
1126 {
1127   struct rexp_node * n = rexp_node (rx, r_opt);
1128   if (n)
1129     {
1130       n->params.pair.left = a;
1131       n->params.pair.right = 0;
1132     }
1133   return n;
1134 }
1135
1136
1137 #ifdef __STDC__
1138 RX_DECL struct rexp_node *
1139 rx_mk_r_star (struct rx * rx,
1140               struct rexp_node * a)
1141 #else
1142 RX_DECL struct rexp_node *
1143 rx_mk_r_star (rx, a)
1144      struct rx * rx;
1145      struct rexp_node * a;
1146 #endif
1147 {
1148   struct rexp_node * n = rexp_node (rx, r_star);
1149   if (n)
1150     {
1151       n->params.pair.left = a;
1152       n->params.pair.right = 0;
1153     }
1154   return n;
1155 }
1156
1157
1158 #ifdef __STDC__
1159 RX_DECL struct rexp_node *
1160 rx_mk_r_2phase_star (struct rx * rx,
1161                      struct rexp_node * a,
1162                      struct rexp_node * b)
1163 #else
1164 RX_DECL struct rexp_node *
1165 rx_mk_r_2phase_star (rx, a, b)
1166      struct rx * rx;
1167      struct rexp_node * a;
1168      struct rexp_node * b;
1169 #endif
1170 {
1171   struct rexp_node * n = rexp_node (rx, r_2phase_star);
1172   if (n)
1173     {
1174       n->params.pair.left = a;
1175       n->params.pair.right = b;
1176     }
1177   return n;
1178 }
1179
1180
1181 #ifdef __STDC__
1182 RX_DECL struct rexp_node *
1183 rx_mk_r_side_effect (struct rx * rx,
1184                      rx_side_effect a)
1185 #else
1186 RX_DECL struct rexp_node *
1187 rx_mk_r_side_effect (rx, a)
1188      struct rx * rx;
1189      rx_side_effect a;
1190 #endif
1191 {
1192   struct rexp_node * n = rexp_node (rx, r_side_effect);
1193   if (n)
1194     {
1195       n->params.side_effect = a;
1196       n->params.pair.right = 0;
1197     }
1198   return n;
1199 }
1200
1201
1202 #ifdef __STDC__
1203 RX_DECL struct rexp_node *
1204 rx_mk_r_data  (struct rx * rx,
1205                void * a)
1206 #else
1207 RX_DECL struct rexp_node *
1208 rx_mk_r_data  (rx, a)
1209      struct rx * rx;
1210      void * a;
1211 #endif
1212 {
1213   struct rexp_node * n = rexp_node (rx, r_data);
1214   if (n)
1215     {
1216       n->params.pair.left = a;
1217       n->params.pair.right = 0;
1218     }
1219   return n;
1220 }
1221
1222
1223 #ifdef __STDC__
1224 RX_DECL void
1225 rx_free_rexp (struct rx * rx, struct rexp_node * node)
1226 #else
1227 RX_DECL void
1228 rx_free_rexp (rx, node)
1229      struct rx * rx;
1230      struct rexp_node * node;
1231 #endif
1232 {
1233   if (node)
1234     {
1235       switch (node->type)
1236         {
1237         case r_cset:
1238           if (node->params.cset)
1239             rx_free_cset (rx, node->params.cset);
1240
1241         case r_side_effect:
1242           break;
1243
1244         case r_concat:
1245         case r_alternate:
1246         case r_2phase_star:
1247         case r_opt:
1248         case r_star:
1249           rx_free_rexp (rx, node->params.pair.left);
1250           rx_free_rexp (rx, node->params.pair.right);
1251           break;
1252
1253         case r_data:
1254           /* This shouldn't occur. */
1255           break;
1256         }
1257       free ((char *)node);
1258     }
1259 }
1260
1261
1262 #ifdef __STDC__
1263 RX_DECL struct rexp_node *
1264 rx_copy_rexp (struct rx *rx,
1265            struct rexp_node *node)
1266 #else
1267 RX_DECL struct rexp_node *
1268 rx_copy_rexp (rx, node)
1269      struct rx *rx;
1270      struct rexp_node *node;
1271 #endif
1272 {
1273   if (!node)
1274     return 0;
1275   else
1276     {
1277       struct rexp_node *n = rexp_node (rx, node->type);
1278       if (!n)
1279         return 0;
1280       switch (node->type)
1281         {
1282         case r_cset:
1283           n->params.cset = rx_copy_cset (rx, node->params.cset);
1284           if (!n->params.cset)
1285             {
1286               rx_free_rexp (rx, n);
1287               return 0;
1288             }
1289           break;
1290
1291         case r_side_effect:
1292           n->params.side_effect = node->params.side_effect;
1293           break;
1294
1295         case r_concat:
1296         case r_alternate:
1297         case r_opt:
1298         case r_2phase_star:
1299         case r_star:
1300           n->params.pair.left =
1301             rx_copy_rexp (rx, node->params.pair.left);
1302           n->params.pair.right =
1303             rx_copy_rexp (rx, node->params.pair.right);
1304           if (   (node->params.pair.left && !n->params.pair.left)
1305               || (node->params.pair.right && !n->params.pair.right))
1306             {
1307               rx_free_rexp  (rx, n);
1308               return 0;
1309             }
1310           break;
1311         case r_data:
1312           /* shouldn't happen */
1313           break;
1314         }
1315       return n;
1316     }
1317 }
1318
1319
1320 \f
1321 /* This page: functions to build and destroy graphs that describe nfa's */
1322
1323 /* Constructs a new nfa node. */
1324 #ifdef __STDC__
1325 RX_DECL struct rx_nfa_state *
1326 rx_nfa_state (struct rx *rx)
1327 #else
1328 RX_DECL struct rx_nfa_state *
1329 rx_nfa_state (rx)
1330      struct rx *rx;
1331 #endif
1332 {
1333   struct rx_nfa_state * n = (struct rx_nfa_state *)malloc (sizeof (*n));
1334   if (!n)
1335     return 0;
1336   bzero (n, sizeof (*n));
1337   n->next = rx->nfa_states;
1338   rx->nfa_states = n;
1339   return n;
1340 }
1341
1342
1343 #ifdef __STDC__
1344 RX_DECL void
1345 rx_free_nfa_state (struct rx_nfa_state * n)
1346 #else
1347 RX_DECL void
1348 rx_free_nfa_state (n)
1349   struct rx_nfa_state * n;
1350 #endif
1351 {
1352   free ((char *)n);
1353 }
1354
1355
1356 /* This looks up an nfa node, given a numeric id.  Numeric id's are
1357  * assigned after the nfa has been built.
1358  */
1359 #ifdef __STDC__
1360 RX_DECL struct rx_nfa_state *
1361 rx_id_to_nfa_state (struct rx * rx,
1362                     int id)
1363 #else
1364 RX_DECL struct rx_nfa_state *
1365 rx_id_to_nfa_state (rx, id)
1366      struct rx * rx;
1367      int id;
1368 #endif
1369 {
1370   struct rx_nfa_state * n;
1371   for (n = rx->nfa_states; n; n = n->next)
1372     if (n->id == id)
1373       return n;
1374   return 0;
1375 }
1376
1377
1378 /* This adds an edge between two nodes, but doesn't initialize the
1379  * edge label.
1380  */
1381
1382 #ifdef __STDC__
1383 RX_DECL struct rx_nfa_edge *
1384 rx_nfa_edge (struct rx *rx,
1385              enum rx_nfa_etype type,
1386              struct rx_nfa_state *start,
1387              struct rx_nfa_state *dest)
1388 #else
1389 RX_DECL struct rx_nfa_edge *
1390 rx_nfa_edge (rx, type, start, dest)
1391      struct rx *rx;
1392      enum rx_nfa_etype type;
1393      struct rx_nfa_state *start;
1394      struct rx_nfa_state *dest;
1395 #endif
1396 {
1397   struct rx_nfa_edge *e;
1398   e = (struct rx_nfa_edge *)malloc (sizeof (*e));
1399   if (!e)
1400     return 0;
1401   e->next = start->edges;
1402   start->edges = e;
1403   e->type = type;
1404   e->dest = dest;
1405   return e;
1406 }
1407
1408
1409 #ifdef __STDC__
1410 RX_DECL void
1411 rx_free_nfa_edge (struct rx_nfa_edge * e)
1412 #else
1413 RX_DECL void
1414 rx_free_nfa_edge (e)
1415      struct rx_nfa_edge * e;
1416 #endif
1417 {
1418   free ((char *)e);
1419 }
1420
1421
1422 /* This constructs a POSSIBLE_FUTURE, which is a kind epsilon-closure
1423  * of an NFA.  These are added to an nfa automaticly by eclose_nfa.
1424  */
1425
1426 #ifdef __STDC__
1427 static struct rx_possible_future *
1428 rx_possible_future (struct rx * rx,
1429                  struct rx_se_list * effects)
1430 #else
1431 static struct rx_possible_future *
1432 rx_possible_future (rx, effects)
1433      struct rx * rx;
1434      struct rx_se_list * effects;
1435 #endif
1436 {
1437   struct rx_possible_future *ec;
1438   ec = (struct rx_possible_future *) malloc (sizeof (*ec));
1439   if (!ec)
1440     return 0;
1441   ec->destset = 0;
1442   ec->next = 0;
1443   ec->effects = effects;
1444   return ec;
1445 }
1446
1447
1448 #ifdef __STDC__
1449 static void
1450 rx_free_possible_future (struct rx_possible_future * pf)
1451 #else
1452 static void
1453 rx_free_possible_future (pf)
1454      struct rx_possible_future * pf;
1455 #endif
1456 {
1457   free ((char *)pf);
1458 }
1459
1460
1461 #ifdef __STDC__
1462 RX_DECL void
1463 rx_free_nfa (struct rx *rx)
1464 #else
1465 RX_DECL void
1466 rx_free_nfa (rx)
1467      struct rx *rx;
1468 #endif
1469 {
1470   while (rx->nfa_states)
1471     {
1472       while (rx->nfa_states->edges)
1473         {
1474           switch (rx->nfa_states->edges->type)
1475             {
1476             case ne_cset:
1477               rx_free_cset (rx, rx->nfa_states->edges->params.cset);
1478               break;
1479             default:
1480               break;
1481             }
1482           {
1483             struct rx_nfa_edge * e;
1484             e = rx->nfa_states->edges;
1485             rx->nfa_states->edges = rx->nfa_states->edges->next;
1486             rx_free_nfa_edge (e);
1487           }
1488         } /* while (rx->nfa_states->edges) */
1489       {
1490         /* Iterate over the partial epsilon closures of rx->nfa_states */
1491         struct rx_possible_future * pf = rx->nfa_states->futures;
1492         while (pf)
1493           {
1494             struct rx_possible_future * pft = pf;
1495             pf = pf->next;
1496             rx_free_possible_future (pft);
1497           }
1498       }
1499       {
1500         struct rx_nfa_state *n;
1501         n = rx->nfa_states;
1502         rx->nfa_states = rx->nfa_states->next;
1503         rx_free_nfa_state (n);
1504       }
1505     }
1506 }
1507
1508
1509 \f
1510 /* This page: translating a pattern expression into an nfa and doing the
1511  * static part of the nfa->super-nfa translation.
1512  */
1513
1514 /* This is the thompson regexp->nfa algorithm.
1515  * It is modified to allow for `side-effect epsilons.'  Those are
1516  * edges that are taken whenever a similar epsilon edge would be,
1517  * but which imply that some side effect occurs when the edge
1518  * is taken.
1519  *
1520  * Side effects are used to model parts of the pattern langauge
1521  * that are not regular (in the formal sense).
1522  */
1523
1524 #ifdef __STDC__
1525 RX_DECL int
1526 rx_build_nfa (struct rx *rx,
1527               struct rexp_node *rexp,
1528               struct rx_nfa_state **start,
1529               struct rx_nfa_state **end)
1530 #else
1531 RX_DECL int
1532 rx_build_nfa (rx, rexp, start, end)
1533      struct rx *rx;
1534      struct rexp_node *rexp;
1535      struct rx_nfa_state **start;
1536      struct rx_nfa_state **end;
1537 #endif
1538 {
1539   struct rx_nfa_edge *edge;
1540
1541   /* Start & end nodes may have been allocated by the caller. */
1542   *start = *start ? *start : rx_nfa_state (rx);
1543
1544   if (!*start)
1545     return 0;
1546
1547   if (!rexp)
1548     {
1549       *end = *start;
1550       return 1;
1551     }
1552
1553   *end = *end ? *end : rx_nfa_state (rx);
1554
1555   if (!*end)
1556     {
1557       rx_free_nfa_state (*start);
1558       return 0;
1559     }
1560
1561   switch (rexp->type)
1562     {
1563     case r_data:
1564       return 0;
1565
1566     case r_cset:
1567       edge = rx_nfa_edge (rx, ne_cset, *start, *end);
1568       if (!edge)
1569         return 0;
1570       edge->params.cset = rx_copy_cset (rx, rexp->params.cset);
1571       if (!edge->params.cset)
1572         {
1573           rx_free_nfa_edge (edge);
1574           return 0;
1575         }
1576       return 1;
1577
1578     case r_opt:
1579       return (rx_build_nfa (rx, rexp->params.pair.left, start, end)
1580               && rx_nfa_edge (rx, ne_epsilon, *start, *end));
1581
1582     case r_star:
1583       {
1584         struct rx_nfa_state * star_start = 0;
1585         struct rx_nfa_state * star_end = 0;
1586         return (rx_build_nfa (rx, rexp->params.pair.left,
1587                               &star_start, &star_end)
1588                 && star_start
1589                 && star_end
1590                 && rx_nfa_edge (rx, ne_epsilon, star_start, star_end)
1591                 && rx_nfa_edge (rx, ne_epsilon, *start, star_start)
1592                 && rx_nfa_edge (rx, ne_epsilon, star_end, *end)
1593
1594                 && rx_nfa_edge (rx, ne_epsilon, star_end, star_start));
1595       }
1596
1597     case r_2phase_star:
1598       {
1599         struct rx_nfa_state * star_start = 0;
1600         struct rx_nfa_state * star_end = 0;
1601         struct rx_nfa_state * loop_exp_start = 0;
1602         struct rx_nfa_state * loop_exp_end = 0;
1603
1604         return (rx_build_nfa (rx, rexp->params.pair.left,
1605                               &star_start, &star_end)
1606                 && rx_build_nfa (rx, rexp->params.pair.right,
1607                                  &loop_exp_start, &loop_exp_end)
1608                 && star_start
1609                 && star_end
1610                 && loop_exp_end
1611                 && loop_exp_start
1612                 && rx_nfa_edge (rx, ne_epsilon, star_start, *end)
1613                 && rx_nfa_edge (rx, ne_epsilon, *start, star_start)
1614                 && rx_nfa_edge (rx, ne_epsilon, star_end, *end)
1615
1616                 && rx_nfa_edge (rx, ne_epsilon, star_end, loop_exp_start)
1617                 && rx_nfa_edge (rx, ne_epsilon, loop_exp_end, star_start));
1618       }
1619
1620
1621     case r_concat:
1622       {
1623         struct rx_nfa_state *shared = 0;
1624         return
1625           (rx_build_nfa (rx, rexp->params.pair.left, start, &shared)
1626            && rx_build_nfa (rx, rexp->params.pair.right, &shared, end));
1627       }
1628
1629     case r_alternate:
1630       {
1631         struct rx_nfa_state *ls = 0;
1632         struct rx_nfa_state *le = 0;
1633         struct rx_nfa_state *rs = 0;
1634         struct rx_nfa_state *re = 0;
1635         return (rx_build_nfa (rx, rexp->params.pair.left, &ls, &le)
1636                 && rx_build_nfa (rx, rexp->params.pair.right, &rs, &re)
1637                 && rx_nfa_edge (rx, ne_epsilon, *start, ls)
1638                 && rx_nfa_edge (rx, ne_epsilon, *start, rs)
1639                 && rx_nfa_edge (rx, ne_epsilon, le, *end)
1640                 && rx_nfa_edge (rx, ne_epsilon, re, *end));
1641       }
1642
1643     case r_side_effect:
1644       edge = rx_nfa_edge (rx, ne_side_effect, *start, *end);
1645       if (!edge)
1646         return 0;
1647       edge->params.side_effect = rexp->params.side_effect;
1648       return 1;
1649     }
1650
1651   /* this should never happen */
1652   return 0;
1653 }
1654
1655
1656 /* RX_NAME_NFA_STATES identifies all nodes with outgoing non-epsilon
1657  * transitions.  Only these nodes can occur in super-states.
1658  * All nodes are given an integer id.
1659  * The id is non-negative if the node has non-epsilon out-transitions, negative
1660  * otherwise (this is because we want the non-negative ids to be used as
1661  * array indexes in a few places).
1662  */
1663
1664 #ifdef __STDC__
1665 RX_DECL void
1666 rx_name_nfa_states (struct rx *rx)
1667 #else
1668 RX_DECL void
1669 rx_name_nfa_states (rx)
1670      struct rx *rx;
1671 #endif
1672 {
1673   struct rx_nfa_state *n = rx->nfa_states;
1674
1675   rx->nodec = 0;
1676   rx->epsnodec = -1;
1677
1678   while (n)
1679     {
1680       struct rx_nfa_edge *e = n->edges;
1681
1682       if (n->is_start)
1683         n->eclosure_needed = 1;
1684
1685       while (e)
1686         {
1687           switch (e->type)
1688             {
1689             case ne_epsilon:
1690             case ne_side_effect:
1691               break;
1692
1693             case ne_cset:
1694               n->id = rx->nodec++;
1695               {
1696                 struct rx_nfa_edge *from_n = n->edges;
1697                 while (from_n)
1698                   {
1699                     from_n->dest->eclosure_needed = 1;
1700                     from_n = from_n->next;
1701                   }
1702               }
1703               goto cont;
1704             }
1705           e = e->next;
1706         }
1707       n->id = rx->epsnodec--;
1708     cont:
1709       n = n->next;
1710     }
1711   rx->epsnodec = -rx->epsnodec;
1712 }
1713
1714 \f
1715 /* This page: data structures for the static part of the nfa->supernfa
1716  * translation.
1717  *
1718  * There are side effect lists -- lists of side effects occuring
1719  * along an uninterrupted, acyclic path of side-effect epsilon edges.
1720  * Such paths are collapsed to single edges in the course of computing
1721  * epsilon closures.  Such single edges are labled with a list of all
1722  * the side effects entailed in crossing them.  Like lists of side
1723  * effects are made == by the constructors below.
1724  *
1725  * There are also nfa state sets.  These are used to hold a list of all
1726  * states reachable from a starting state for a given type of transition
1727  * and side effect list.   These are also hash-consed.
1728  */
1729
1730 /* The next several functions compare, construct, etc. lists of side
1731  * effects.  See ECLOSE_NFA (below) for details.
1732  */
1733
1734 /* Ordering of rx_se_list
1735  * (-1, 0, 1 return value convention).
1736  */
1737
1738 #ifdef __STDC__
1739 static int
1740 se_list_cmp (void * va, void * vb)
1741 #else
1742 static int
1743 se_list_cmp (va, vb)
1744      void * va;
1745      void * vb;
1746 #endif
1747 {
1748   struct rx_se_list * a = (struct rx_se_list *)va;
1749   struct rx_se_list * b = (struct rx_se_list *)vb;
1750
1751   return ((va == vb)
1752           ? 0
1753           : (!va
1754              ? -1
1755              : (!vb
1756                 ? 1
1757                 : ((long)a->car < (long)b->car
1758                    ? 1
1759                    : ((long)a->car > (long)b->car
1760                       ? -1
1761                       : se_list_cmp ((void *)a->cdr, (void *)b->cdr))))));
1762 }
1763
1764
1765 #ifdef __STDC__
1766 static int
1767 se_list_equal (void * va, void * vb)
1768 #else
1769 static int
1770 se_list_equal (va, vb)
1771      void * va;
1772      void * vb;
1773 #endif
1774 {
1775   return !(se_list_cmp (va, vb));
1776 }
1777
1778 static struct rx_hash_rules se_list_hash_rules =
1779 {
1780   se_list_equal,
1781   compiler_hash_alloc,
1782   compiler_free_hash,
1783   compiler_hash_item_alloc,
1784   compiler_free_hash_item
1785 };
1786
1787
1788 #ifdef __STDC__
1789 static struct rx_se_list *
1790 side_effect_cons (struct rx * rx,
1791                   void * se, struct rx_se_list * list)
1792 #else
1793 static struct rx_se_list *
1794 side_effect_cons (rx, se, list)
1795      struct rx * rx;
1796      void * se;
1797      struct rx_se_list * list;
1798 #endif
1799 {
1800   struct rx_se_list * l;
1801   l = ((struct rx_se_list *) malloc (sizeof (*l)));
1802   if (!l)
1803     return 0;
1804   l->car = se;
1805   l->cdr = list;
1806   return l;
1807 }
1808
1809
1810 #ifdef __STDC__
1811 static struct rx_se_list *
1812 hash_cons_se_prog (struct rx * rx,
1813                    struct rx_hash * memo,
1814                    void * car, struct rx_se_list * cdr)
1815 #else
1816 static struct rx_se_list *
1817 hash_cons_se_prog (rx, memo, car, cdr)
1818      struct rx * rx;
1819      struct rx_hash * memo;
1820      void * car;
1821      struct rx_se_list * cdr;
1822 #endif
1823 {
1824   long hash = (long)car ^ (long)cdr;
1825   struct rx_se_list template;
1826
1827   template.car = car;
1828   template.cdr = cdr;
1829   {
1830     struct rx_hash_item * it = rx_hash_store (memo, hash,
1831                                               (void *)&template,
1832                                               &se_list_hash_rules);
1833     if (!it)
1834       return 0;
1835     if (it->data == (void *)&template)
1836       {
1837         struct rx_se_list * consed;
1838         consed = (struct rx_se_list *) malloc (sizeof (*consed));
1839         *consed = template;
1840         it->data = (void *)consed;
1841       }
1842     return (struct rx_se_list *)it->data;
1843   }
1844 }
1845
1846
1847 #ifdef __STDC__
1848 static struct rx_se_list *
1849 hash_se_prog (struct rx * rx, struct rx_hash * memo, struct rx_se_list * prog)
1850 #else
1851 static struct rx_se_list *
1852 hash_se_prog (rx, memo, prog)
1853      struct rx * rx;
1854      struct rx_hash * memo;
1855      struct rx_se_list * prog;
1856 #endif
1857 {
1858   struct rx_se_list * answer = 0;
1859   while (prog)
1860     {
1861       answer = hash_cons_se_prog (rx, memo, prog->car, answer);
1862       if (!answer)
1863         return 0;
1864       prog = prog->cdr;
1865     }
1866   return answer;
1867 }
1868
1869 #ifdef __STDC__
1870 static int
1871 nfa_set_cmp (void * va, void * vb)
1872 #else
1873 static int
1874 nfa_set_cmp (va, vb)
1875      void * va;
1876      void * vb;
1877 #endif
1878 {
1879   struct rx_nfa_state_set * a = (struct rx_nfa_state_set *)va;
1880   struct rx_nfa_state_set * b = (struct rx_nfa_state_set *)vb;
1881
1882   return ((va == vb)
1883           ? 0
1884           : (!va
1885              ? -1
1886              : (!vb
1887                 ? 1
1888                 : (a->car->id < b->car->id
1889                    ? 1
1890                    : (a->car->id > b->car->id
1891                       ? -1
1892                       : nfa_set_cmp ((void *)a->cdr, (void *)b->cdr))))));
1893 }
1894
1895 #ifdef __STDC__
1896 static int
1897 nfa_set_equal (void * va, void * vb)
1898 #else
1899 static int
1900 nfa_set_equal (va, vb)
1901      void * va;
1902      void * vb;
1903 #endif
1904 {
1905   return !nfa_set_cmp (va, vb);
1906 }
1907
1908 static struct rx_hash_rules nfa_set_hash_rules =
1909 {
1910   nfa_set_equal,
1911   compiler_hash_alloc,
1912   compiler_free_hash,
1913   compiler_hash_item_alloc,
1914   compiler_free_hash_item
1915 };
1916
1917
1918 #ifdef __STDC__
1919 static struct rx_nfa_state_set *
1920 nfa_set_cons (struct rx * rx,
1921               struct rx_hash * memo, struct rx_nfa_state * state,
1922               struct rx_nfa_state_set * set)
1923 #else
1924 static struct rx_nfa_state_set *
1925 nfa_set_cons (rx, memo, state, set)
1926      struct rx * rx;
1927      struct rx_hash * memo;
1928      struct rx_nfa_state * state;
1929      struct rx_nfa_state_set * set;
1930 #endif
1931 {
1932   struct rx_nfa_state_set template;
1933   struct rx_hash_item * node;
1934   template.car = state;
1935   template.cdr = set;
1936   node = rx_hash_store (memo,
1937                         (((long)state) >> 8) ^ (long)set,
1938                         &template, &nfa_set_hash_rules);
1939   if (!node)
1940     return 0;
1941   if (node->data == &template)
1942     {
1943       struct rx_nfa_state_set * l;
1944       l = (struct rx_nfa_state_set *) malloc (sizeof (*l));
1945       node->data = (void *) l;
1946       if (!l)
1947         return 0;
1948       *l = template;
1949     }
1950   return (struct rx_nfa_state_set *)node->data;
1951 }
1952
1953
1954 #ifdef __STDC__
1955 static struct rx_nfa_state_set *
1956 nfa_set_enjoin (struct rx * rx,
1957                 struct rx_hash * memo, struct rx_nfa_state * state,
1958                 struct rx_nfa_state_set * set)
1959 #else
1960 static struct rx_nfa_state_set *
1961 nfa_set_enjoin (rx, memo, state, set)
1962      struct rx * rx;
1963      struct rx_hash * memo;
1964      struct rx_nfa_state * state;
1965      struct rx_nfa_state_set * set;
1966 #endif
1967 {
1968   if (!set || state->id < set->car->id)
1969     return nfa_set_cons (rx, memo, state, set);
1970   if (state->id == set->car->id)
1971     return set;
1972   else
1973     {
1974       struct rx_nfa_state_set * newcdr
1975         = nfa_set_enjoin (rx, memo, state, set->cdr);
1976       if (newcdr != set->cdr)
1977         set = nfa_set_cons (rx, memo, set->car, newcdr);
1978       return set;
1979     }
1980 }
1981
1982
1983 \f
1984 /* This page: computing epsilon closures.  The closures aren't total.
1985  * Each node's closures are partitioned according to the side effects entailed
1986  * along the epsilon edges.  Return true on success.
1987  */
1988
1989 struct eclose_frame
1990 {
1991   struct rx_se_list *prog_backwards;
1992 };
1993
1994
1995 #ifdef __STDC__
1996 static int
1997 eclose_node (struct rx *rx, struct rx_nfa_state *outnode,
1998              struct rx_nfa_state *node, struct eclose_frame *frame)
1999 #else
2000 static int
2001 eclose_node (rx, outnode, node, frame)
2002      struct rx *rx;
2003      struct rx_nfa_state *outnode;
2004      struct rx_nfa_state *node;
2005      struct eclose_frame *frame;
2006 #endif
2007 {
2008   struct rx_nfa_edge *e = node->edges;
2009
2010   /* For each node, we follow all epsilon paths to build the closure.
2011    * The closure omits nodes that have only epsilon edges.
2012    * The closure is split into partial closures -- all the states in
2013    * a partial closure are reached by crossing the same list of
2014    * of side effects (though not necessarily the same path).
2015    */
2016   if (node->mark)
2017     return 1;
2018   node->mark = 1;
2019
2020   if (node->id >= 0 || node->is_final)
2021     {
2022       struct rx_possible_future **ec;
2023       struct rx_se_list * prog_in_order
2024         = ((struct rx_se_list *)hash_se_prog (rx,
2025                                               &rx->se_list_memo,
2026                                               frame->prog_backwards));
2027       int cmp;
2028
2029       ec = &outnode->futures;
2030
2031       while (*ec)
2032         {
2033           cmp = se_list_cmp ((void *)(*ec)->effects, (void *)prog_in_order);
2034           if (cmp <= 0)
2035             break;
2036           ec = &(*ec)->next;
2037         }
2038       if (!*ec || (cmp < 0))
2039         {
2040           struct rx_possible_future * saved = *ec;
2041           *ec = rx_possible_future (rx, prog_in_order);
2042           (*ec)->next = saved;
2043           if (!*ec)
2044             return 0;
2045         }
2046       if (node->id >= 0)
2047         {
2048           (*ec)->destset = nfa_set_enjoin (rx, &rx->set_list_memo,
2049                                            node, (*ec)->destset);
2050           if (!(*ec)->destset)
2051             return 0;
2052         }
2053     }
2054
2055   while (e)
2056     {
2057       switch (e->type)
2058         {
2059         case ne_epsilon:
2060           if (!eclose_node (rx, outnode, e->dest, frame))
2061             return 0;
2062           break;
2063         case ne_side_effect:
2064           {
2065             frame->prog_backwards = side_effect_cons (rx,
2066                                                       e->params.side_effect,
2067                                                       frame->prog_backwards);
2068             if (!frame->prog_backwards)
2069               return 0;
2070             if (!eclose_node (rx, outnode, e->dest, frame))
2071               return 0;
2072             {
2073               struct rx_se_list * dying = frame->prog_backwards;
2074               frame->prog_backwards = frame->prog_backwards->cdr;
2075               free ((char *)dying);
2076             }
2077             break;
2078           }
2079         default:
2080           break;
2081         }
2082       e = e->next;
2083     }
2084   node->mark = 0;
2085   return 1;
2086 }
2087
2088
2089 #ifdef __STDC__
2090 RX_DECL int
2091 rx_eclose_nfa (struct rx *rx)
2092 #else
2093 RX_DECL int
2094 rx_eclose_nfa (rx)
2095      struct rx *rx;
2096 #endif
2097 {
2098   struct rx_nfa_state *n = rx->nfa_states;
2099   struct eclose_frame frame;
2100   static int rx_id = 0;
2101
2102   frame.prog_backwards = 0;
2103   rx->rx_id = rx_id++;
2104   bzero (&rx->se_list_memo, sizeof (rx->se_list_memo));
2105   bzero (&rx->set_list_memo, sizeof (rx->set_list_memo));
2106   while (n)
2107     {
2108       n->futures = 0;
2109       if (n->eclosure_needed && !eclose_node (rx, n, n, &frame))
2110         return 0;
2111       /* clear_marks (rx); */
2112       n = n->next;
2113     }
2114   return 1;
2115 }
2116
2117
2118 /* This deletes epsilon edges from an NFA.  After running eclose_node,
2119  * we have no more need for these edges.  They are removed to simplify
2120  * further operations on the NFA.
2121  */
2122
2123 #ifdef __STDC__
2124 RX_DECL void
2125 rx_delete_epsilon_transitions (struct rx *rx)
2126 #else
2127 RX_DECL void
2128 rx_delete_epsilon_transitions (rx)
2129      struct rx *rx;
2130 #endif
2131 {
2132   struct rx_nfa_state *n = rx->nfa_states;
2133   struct rx_nfa_edge **e;
2134
2135   while (n)
2136     {
2137       e = &n->edges;
2138       while (*e)
2139         {
2140           struct rx_nfa_edge *t;
2141           switch ((*e)->type)
2142             {
2143             case ne_epsilon:
2144             case ne_side_effect:
2145               t = *e;
2146               *e = t->next;
2147               rx_free_nfa_edge (t);
2148               break;
2149
2150             default:
2151               e = &(*e)->next;
2152               break;
2153             }
2154         }
2155       n = n->next;
2156     }
2157 }
2158
2159 \f
2160 /* This page: storing the nfa in a contiguous region of memory for
2161  * subsequent conversion to a super-nfa.
2162  */
2163
2164 /* This is for qsort on an array of nfa_states. The order
2165  * is based on state ids and goes
2166  *              [0...MAX][MIN..-1] where (MAX>=0) and (MIN<0)
2167  * This way, positive ids double as array indices.
2168  */
2169
2170 #ifdef __STDC__
2171 static int
2172 nfacmp (void * va, void * vb)
2173 #else
2174 static int
2175 nfacmp (va, vb)
2176      void * va;
2177      void * vb;
2178 #endif
2179 {
2180   struct rx_nfa_state **a = (struct rx_nfa_state **)va;
2181   struct rx_nfa_state **b = (struct rx_nfa_state **)vb;
2182   return (*a == *b              /* &&&& 3.18 */
2183           ? 0
2184           : (((*a)->id < 0) == ((*b)->id < 0)
2185              ? (((*a)->id  < (*b)->id) ? -1 : 1)
2186              : (((*a)->id < 0)
2187                 ? 1 : -1)));
2188 }
2189
2190 #ifdef __STDC__
2191 static int
2192 count_hash_nodes (struct rx_hash * st)
2193 #else
2194 static int
2195 count_hash_nodes (st)
2196      struct rx_hash * st;
2197 #endif
2198 {
2199   int x;
2200   int count = 0;
2201   for (x = 0; x < 13; ++x)
2202     count += ((st->children[x])
2203               ? count_hash_nodes (st->children[x])
2204               : st->bucket_size[x]);
2205
2206   return count;
2207 }
2208
2209
2210 #ifdef __STDC__
2211 static void
2212 se_memo_freer (struct rx_hash_item * node)
2213 #else
2214 static void
2215 se_memo_freer (node)
2216      struct rx_hash_item * node;
2217 #endif
2218 {
2219   free ((char *)node->data);
2220 }
2221
2222
2223 #ifdef __STDC__
2224 static void
2225 nfa_set_freer (struct rx_hash_item * node)
2226 #else
2227 static void
2228 nfa_set_freer (node)
2229      struct rx_hash_item * node;
2230 #endif
2231 {
2232   free ((char *)node->data);
2233 }
2234
2235
2236 /* This copies an entire NFA into a single malloced block of memory.
2237  * Mostly this is for compatability with regex.c, though it is convenient
2238  * to have the nfa nodes in an array.
2239  */
2240
2241 #ifdef __STDC__
2242 RX_DECL int
2243 rx_compactify_nfa (struct rx *rx,
2244                    void **mem, unsigned long *size)
2245 #else
2246 RX_DECL int
2247 rx_compactify_nfa (rx, mem, size)
2248      struct rx *rx;
2249      void **mem;
2250      unsigned long *size;
2251 #endif
2252 {
2253   int total_nodec;
2254   struct rx_nfa_state *n;
2255   int edgec = 0;
2256   int eclosec = 0;
2257   int se_list_consc = count_hash_nodes (&rx->se_list_memo);
2258   int nfa_setc = count_hash_nodes (&rx->set_list_memo);
2259   unsigned long total_size;
2260
2261   /* This takes place in two stages.   First, the total size of the
2262    * nfa is computed, then structures are copied.
2263    */
2264   n = rx->nfa_states;
2265   total_nodec = 0;
2266   while (n)
2267     {
2268       struct rx_nfa_edge *e = n->edges;
2269       struct rx_possible_future *ec = n->futures;
2270       ++total_nodec;
2271       while (e)
2272         {
2273           ++edgec;
2274           e = e->next;
2275         }
2276       while (ec)
2277         {
2278           ++eclosec;
2279           ec = ec->next;
2280         }
2281       n = n->next;
2282     }
2283
2284   total_size = (total_nodec * sizeof (struct rx_nfa_state)
2285                 + edgec * rx_sizeof_bitset (rx->local_cset_size)
2286                 + edgec * sizeof (struct rx_nfa_edge)
2287                 + nfa_setc * sizeof (struct rx_nfa_state_set)
2288                 + eclosec * sizeof (struct rx_possible_future)
2289                 + se_list_consc * sizeof (struct rx_se_list)
2290                 + rx->reserved);
2291
2292   if (total_size > *size)
2293     {
2294       *mem = remalloc (*mem, total_size);
2295       if (*mem)
2296         *size = total_size;
2297       else
2298         return 0;
2299     }
2300   /* Now we've allocated the memory; this copies the NFA. */
2301   {
2302     static struct rx_nfa_state **scratch = 0;
2303     static int scratch_alloc = 0;
2304     struct rx_nfa_state *state_base = (struct rx_nfa_state *) * mem;
2305     struct rx_nfa_state *new_state = state_base;
2306     struct rx_nfa_edge *new_edge =
2307       (struct rx_nfa_edge *)
2308         ((char *) state_base + total_nodec * sizeof (struct rx_nfa_state));
2309     struct rx_se_list * new_se_list =
2310       (struct rx_se_list *)
2311         ((char *)new_edge + edgec * sizeof (struct rx_nfa_edge));
2312     struct rx_possible_future *new_close =
2313       ((struct rx_possible_future *)
2314        ((char *) new_se_list
2315         + se_list_consc * sizeof (struct rx_se_list)));
2316     struct rx_nfa_state_set * new_nfa_set =
2317       ((struct rx_nfa_state_set *)
2318        ((char *)new_close + eclosec * sizeof (struct rx_possible_future)));
2319     char *new_bitset =
2320       ((char *) new_nfa_set + nfa_setc * sizeof (struct rx_nfa_state_set));
2321     int x;
2322     struct rx_nfa_state *n;
2323
2324     if (scratch_alloc < total_nodec)
2325       {
2326         scratch = ((struct rx_nfa_state **)
2327                    remalloc (scratch, total_nodec * sizeof (*scratch)));
2328         if (scratch)
2329           scratch_alloc = total_nodec;
2330         else
2331           {
2332             scratch_alloc = 0;
2333             return 0;
2334           }
2335       }
2336
2337     for (x = 0, n = rx->nfa_states; n; n = n->next)
2338       scratch[x++] = n;
2339
2340     qsort (scratch, total_nodec,
2341            sizeof (struct rx_nfa_state *), (int (*)())nfacmp);
2342
2343     for (x = 0; x < total_nodec; ++x)
2344       {
2345         struct rx_possible_future *eclose = scratch[x]->futures;
2346         struct rx_nfa_edge *edge = scratch[x]->edges;
2347         struct rx_nfa_state *cn = new_state++;
2348         cn->futures = 0;
2349         cn->edges = 0;
2350         cn->next = (x == total_nodec - 1) ? 0 : (cn + 1);
2351         cn->id = scratch[x]->id;
2352         cn->is_final = scratch[x]->is_final;
2353         cn->is_start = scratch[x]->is_start;
2354         cn->mark = 0;
2355         while (edge)
2356           {
2357             int indx = (edge->dest->id < 0
2358                          ? (total_nodec + edge->dest->id)
2359                          : edge->dest->id);
2360             struct rx_nfa_edge *e = new_edge++;
2361             rx_Bitset cset = (rx_Bitset) new_bitset;
2362             new_bitset += rx_sizeof_bitset (rx->local_cset_size);
2363             rx_bitset_null (rx->local_cset_size, cset);
2364             rx_bitset_union (rx->local_cset_size, cset, edge->params.cset);
2365             e->next = cn->edges;
2366             cn->edges = e;
2367             e->type = edge->type;
2368             e->dest = state_base + indx;
2369             e->params.cset = cset;
2370             edge = edge->next;
2371           }
2372         while (eclose)
2373           {
2374             struct rx_possible_future *ec = new_close++;
2375             struct rx_hash_item * sp;
2376             struct rx_se_list ** sepos;
2377             struct rx_se_list * sesrc;
2378             struct rx_nfa_state_set * destlst;
2379             struct rx_nfa_state_set ** destpos;
2380             ec->next = cn->futures;
2381             cn->futures = ec;
2382             for (sepos = &ec->effects, sesrc = eclose->effects;
2383                  sesrc;
2384                  sesrc = sesrc->cdr, sepos = &(*sepos)->cdr)
2385               {
2386                 sp = rx_hash_find (&rx->se_list_memo,
2387                                    (long)sesrc->car ^ (long)sesrc->cdr,
2388                                    sesrc, &se_list_hash_rules);
2389                 if (sp->binding)
2390                   {
2391                     sesrc = (struct rx_se_list *)sp->binding;
2392                     break;
2393                   }
2394                 *new_se_list = *sesrc;
2395                 sp->binding = (void *)new_se_list;
2396                 *sepos = new_se_list;
2397                 ++new_se_list;
2398               }
2399             *sepos = sesrc;
2400             for (destpos = &ec->destset, destlst = eclose->destset;
2401                  destlst;
2402                  destpos = &(*destpos)->cdr, destlst = destlst->cdr)
2403               {
2404                 sp = rx_hash_find (&rx->set_list_memo,
2405                                    ((((long)destlst->car) >> 8)
2406                                     ^ (long)destlst->cdr),
2407                                    destlst, &nfa_set_hash_rules);
2408                 if (sp->binding)
2409                   {
2410                     destlst = (struct rx_nfa_state_set *)sp->binding;
2411                     break;
2412                   }
2413                 *new_nfa_set = *destlst;
2414                 new_nfa_set->car = state_base + destlst->car->id;
2415                 sp->binding = (void *)new_nfa_set;
2416                 *destpos = new_nfa_set;
2417                 ++new_nfa_set;
2418               }
2419             *destpos = destlst;
2420             eclose = eclose->next;
2421           }
2422       }
2423   }
2424   rx_free_hash_table (&rx->se_list_memo, se_memo_freer, &se_list_hash_rules);
2425   bzero (&rx->se_list_memo, sizeof (rx->se_list_memo));
2426   rx_free_hash_table (&rx->set_list_memo, nfa_set_freer, &nfa_set_hash_rules);
2427   bzero (&rx->set_list_memo, sizeof (rx->set_list_memo));
2428
2429   rx_free_nfa (rx);
2430   rx->nfa_states = (struct rx_nfa_state *)*mem;
2431   return 1;
2432 }
2433
2434 \f
2435 /* The functions in the next several pages define the lazy-NFA-conversion used
2436  * by matchers.  The input to this construction is an NFA such as
2437  * is built by compactify_nfa (rx.c).  The output is the superNFA.
2438  */
2439
2440 /* Match engines can use arbitrary values for opcodes.  So, the parse tree
2441  * is built using instructions names (enum rx_opcode), but the superstate
2442  * nfa is populated with mystery opcodes (void *).
2443  *
2444  * For convenience, here is an id table.  The opcodes are == to their inxs
2445  *
2446  * The lables in re_search_2 would make good values for instructions.
2447  */
2448
2449 void * rx_id_instruction_table[rx_num_instructions] =
2450 {
2451   (void *) rx_backtrack_point,
2452   (void *) rx_do_side_effects,
2453   (void *) rx_cache_miss,
2454   (void *) rx_next_char,
2455   (void *) rx_backtrack,
2456   (void *) rx_error_inx
2457 };
2458
2459 \f
2460
2461 /* Memory mgt. for superstate graphs. */
2462
2463 #ifdef __STDC__
2464 static char *
2465 rx_cache_malloc (struct rx_cache * cache, int bytes)
2466 #else
2467 static char *
2468 rx_cache_malloc (cache, bytes)
2469      struct rx_cache * cache;
2470      int bytes;
2471 #endif
2472 {
2473   while (cache->bytes_left < bytes)
2474     {
2475       if (cache->memory_pos)
2476         cache->memory_pos = cache->memory_pos->next;
2477       if (!cache->memory_pos)
2478         {
2479           cache->morecore (cache);
2480           if (!cache->memory_pos)
2481             return 0;
2482         }
2483       cache->bytes_left = cache->memory_pos->bytes;
2484       cache->memory_addr = ((char *)cache->memory_pos
2485                             + sizeof (struct rx_blocklist));
2486     }
2487   cache->bytes_left -= bytes;
2488   {
2489     char * addr = cache->memory_addr;
2490     cache->memory_addr += bytes;
2491     return addr;
2492   }
2493 }
2494
2495 #ifdef __STDC__
2496 static void
2497 rx_cache_free (struct rx_cache * cache,
2498                struct rx_freelist ** freelist, char * mem)
2499 #else
2500 static void
2501 rx_cache_free (cache, freelist, mem)
2502      struct rx_cache * cache;
2503      struct rx_freelist ** freelist;
2504      char * mem;
2505 #endif
2506 {
2507   struct rx_freelist * it = (struct rx_freelist *)mem;
2508   it->next = *freelist;
2509   *freelist = it;
2510 }
2511
2512
2513 /* The partially instantiated superstate graph has a transition
2514  * table at every node.  There is one entry for every character.
2515  * This fills in the transition for a set.
2516  */
2517 #ifdef __STDC__
2518 static void
2519 install_transition (struct rx_superstate *super,
2520                     struct rx_inx *answer, rx_Bitset trcset)
2521 #else
2522 static void
2523 install_transition (super, answer, trcset)
2524      struct rx_superstate *super;
2525      struct rx_inx *answer;
2526      rx_Bitset trcset;
2527 #endif
2528 {
2529   struct rx_inx * transitions = super->transitions;
2530   int chr;
2531   for (chr = 0; chr < 256; )
2532     if (!*trcset)
2533       {
2534         ++trcset;
2535         chr += 32;
2536       }
2537     else
2538       {
2539         RX_subset sub = *trcset;
2540         RX_subset mask = 1;
2541         int bound = chr + 32;
2542         while (chr < bound)
2543           {
2544             if (sub & mask)
2545               transitions [chr] = *answer;
2546             ++chr;
2547             mask <<= 1;
2548           }
2549         ++trcset;
2550       }
2551 }
2552
2553
2554 #ifdef __STDC__
2555 static int
2556 qlen (struct rx_superstate * q)
2557 #else
2558 static int
2559 qlen (q)
2560      struct rx_superstate * q;
2561 #endif
2562 {
2563   int count = 1;
2564   struct rx_superstate * it;
2565   if (!q)
2566     return 0;
2567   for (it = q->next_recyclable; it != q; it = it->next_recyclable)
2568     ++count;
2569   return count;
2570 }
2571
2572 #ifdef __STDC__
2573 static void
2574 check_cache (struct rx_cache * cache)
2575 #else
2576 static void
2577 check_cache (cache)
2578      struct rx_cache * cache;
2579 #endif
2580 {
2581   struct rx_cache * you_fucked_up = 0;
2582   int total = cache->superstates;
2583   int semi = cache->semifree_superstates;
2584   if (semi != qlen (cache->semifree_superstate))
2585     check_cache (you_fucked_up);
2586   if ((total - semi) != qlen (cache->lru_superstate))
2587     check_cache (you_fucked_up);
2588 }
2589
2590 /* When a superstate is old and neglected, it can enter a
2591  * semi-free state.  A semi-free state is slated to die.
2592  * Incoming transitions to a semi-free state are re-written
2593  * to cause an (interpreted) fault when they are taken.
2594  * The fault handler revives the semi-free state, patches
2595  * incoming transitions back to normal, and continues.
2596  *
2597  * The idea is basicly to free in two stages, aborting
2598  * between the two if the state turns out to be useful again.
2599  * When a free is aborted, the rescued superstate is placed
2600  * in the most-favored slot to maximize the time until it
2601  * is next semi-freed.
2602  */
2603
2604 #ifdef __STDC__
2605 static void
2606 semifree_superstate (struct rx_cache * cache)
2607 #else
2608 static void
2609 semifree_superstate (cache)
2610      struct rx_cache * cache;
2611 #endif
2612 {
2613   int disqualified = cache->semifree_superstates;
2614   if (disqualified == cache->superstates)
2615     return;
2616   while (cache->lru_superstate->locks)
2617     {
2618       cache->lru_superstate = cache->lru_superstate->next_recyclable;
2619       ++disqualified;
2620       if (disqualified == cache->superstates)
2621         return;
2622     }
2623   {
2624     struct rx_superstate * it = cache->lru_superstate;
2625     it->next_recyclable->prev_recyclable = it->prev_recyclable;
2626     it->prev_recyclable->next_recyclable = it->next_recyclable;
2627     cache->lru_superstate = (it == it->next_recyclable
2628                              ? 0
2629                              : it->next_recyclable);
2630     if (!cache->semifree_superstate)
2631       {
2632         cache->semifree_superstate = it;
2633         it->next_recyclable = it;
2634         it->prev_recyclable = it;
2635       }
2636     else
2637       {
2638         it->prev_recyclable = cache->semifree_superstate->prev_recyclable;
2639         it->next_recyclable = cache->semifree_superstate;
2640         it->prev_recyclable->next_recyclable = it;
2641         it->next_recyclable->prev_recyclable = it;
2642       }
2643     {
2644       struct rx_distinct_future *df;
2645       it->is_semifree = 1;
2646       ++cache->semifree_superstates;
2647       df = it->transition_refs;
2648       if (df)
2649         {
2650           df->prev_same_dest->next_same_dest = 0;
2651           for (df = it->transition_refs; df; df = df->next_same_dest)
2652             {
2653               df->future_frame.inx = cache->instruction_table[rx_cache_miss];
2654               df->future_frame.data = 0;
2655               df->future_frame.data_2 = (void *) df;
2656               /* If there are any NEXT-CHAR instruction frames that
2657                * refer to this state, we convert them to CACHE-MISS frames.
2658                */
2659               if (!df->effects
2660                   && (df->edge->options->next_same_super_edge[0]
2661                       == df->edge->options))
2662                 install_transition (df->present, &df->future_frame,
2663                                     df->edge->cset);
2664             }
2665           df = it->transition_refs;
2666           df->prev_same_dest->next_same_dest = df;
2667         }
2668     }
2669   }
2670 }
2671
2672
2673 #ifdef __STDC__
2674 static void
2675 refresh_semifree_superstate (struct rx_cache * cache,
2676                              struct rx_superstate * super)
2677 #else
2678 static void
2679 refresh_semifree_superstate (cache, super)
2680      struct rx_cache * cache;
2681      struct rx_superstate * super;
2682 #endif
2683 {
2684   struct rx_distinct_future *df;
2685
2686   if (super->transition_refs)
2687     {
2688       super->transition_refs->prev_same_dest->next_same_dest = 0;
2689       for (df = super->transition_refs; df; df = df->next_same_dest)
2690         {
2691           df->future_frame.inx = cache->instruction_table[rx_next_char];
2692           df->future_frame.data = (void *) super->transitions;
2693           /* CACHE-MISS instruction frames that refer to this state,
2694            * must be converted to NEXT-CHAR frames.
2695            */
2696           if (!df->effects
2697               && (df->edge->options->next_same_super_edge[0]
2698                   == df->edge->options))
2699             install_transition (df->present, &df->future_frame,
2700                                 df->edge->cset);
2701         }
2702       super->transition_refs->prev_same_dest->next_same_dest
2703         = super->transition_refs;
2704     }
2705   if (cache->semifree_superstate == super)
2706     cache->semifree_superstate = (super->prev_recyclable == super
2707                                   ? 0
2708                                   : super->prev_recyclable);
2709   super->next_recyclable->prev_recyclable = super->prev_recyclable;
2710   super->prev_recyclable->next_recyclable = super->next_recyclable;
2711
2712   if (!cache->lru_superstate)
2713     (cache->lru_superstate
2714      = super->next_recyclable
2715      = super->prev_recyclable
2716      = super);
2717   else
2718     {
2719       super->next_recyclable = cache->lru_superstate;
2720       super->prev_recyclable = cache->lru_superstate->prev_recyclable;
2721       super->next_recyclable->prev_recyclable = super;
2722       super->prev_recyclable->next_recyclable = super;
2723     }
2724   super->is_semifree = 0;
2725   --cache->semifree_superstates;
2726 }
2727
2728 #ifdef __STDC__
2729 static void
2730 rx_refresh_this_superstate (struct rx_cache * cache, struct rx_superstate * superstate)
2731 #else
2732 static void
2733 rx_refresh_this_superstate (cache, superstate)
2734      struct rx_cache * cache;
2735      struct rx_superstate * superstate;
2736 #endif
2737 {
2738   if (superstate->is_semifree)
2739     refresh_semifree_superstate (cache, superstate);
2740   else if (cache->lru_superstate == superstate)
2741     cache->lru_superstate = superstate->next_recyclable;
2742   else if (superstate != cache->lru_superstate->prev_recyclable)
2743     {
2744       superstate->next_recyclable->prev_recyclable
2745         = superstate->prev_recyclable;
2746       superstate->prev_recyclable->next_recyclable
2747         = superstate->next_recyclable;
2748       superstate->next_recyclable = cache->lru_superstate;
2749       superstate->prev_recyclable = cache->lru_superstate->prev_recyclable;
2750       superstate->next_recyclable->prev_recyclable = superstate;
2751       superstate->prev_recyclable->next_recyclable = superstate;
2752     }
2753 }
2754
2755 #ifdef __STDC__
2756 static void
2757 release_superset_low (struct rx_cache * cache,
2758                      struct rx_superset *set)
2759 #else
2760 static void
2761 release_superset_low (cache, set)
2762      struct rx_cache * cache;
2763      struct rx_superset *set;
2764 #endif
2765 {
2766   if (!--set->refs)
2767     {
2768       if (set->cdr)
2769         release_superset_low (cache, set->cdr);
2770
2771       set->starts_for = 0;
2772
2773       rx_hash_free
2774         (rx_hash_find
2775          (&cache->superset_table,
2776           (unsigned long)set->car ^ set->id ^ (unsigned long)set->cdr,
2777           (void *)set,
2778           &cache->superset_hash_rules),
2779          &cache->superset_hash_rules);
2780       rx_cache_free (cache, &cache->free_supersets, (char *)set);
2781     }
2782 }
2783
2784 #ifdef __STDC__
2785 RX_DECL void
2786 rx_release_superset (struct rx *rx,
2787                      struct rx_superset *set)
2788 #else
2789 RX_DECL void
2790 rx_release_superset (rx, set)
2791      struct rx *rx;
2792      struct rx_superset *set;
2793 #endif
2794 {
2795   release_superset_low (rx->cache, set);
2796 }
2797
2798 /* This tries to add a new superstate to the superstate freelist.
2799  * It might, as a result, free some edge pieces or hash tables.
2800  * If nothing can be freed because too many locks are being held, fail.
2801  */
2802
2803 #ifdef __STDC__
2804 static int
2805 rx_really_free_superstate (struct rx_cache * cache)
2806 #else
2807 static int
2808 rx_really_free_superstate (cache)
2809      struct rx_cache * cache;
2810 #endif
2811 {
2812   int locked_superstates = 0;
2813   struct rx_superstate * it;
2814
2815   if (!cache->superstates)
2816     return 0;
2817
2818   {
2819     /* This is a total guess.  The idea is that we should expect as
2820      * many misses as we've recently experienced.  I.e., cache->misses
2821      * should be the same as cache->semifree_superstates.
2822      */
2823     while ((cache->hits + cache->misses) > cache->superstates_allowed)
2824       {
2825         cache->hits >>= 1;
2826         cache->misses >>= 1;
2827       }
2828     if (  ((cache->hits + cache->misses) * cache->semifree_superstates)
2829         < (cache->superstates            * cache->misses))
2830       {
2831         semifree_superstate (cache);
2832         semifree_superstate (cache);
2833       }
2834   }
2835
2836   while (cache->semifree_superstate && cache->semifree_superstate->locks)
2837     {
2838       refresh_semifree_superstate (cache, cache->semifree_superstate);
2839       ++locked_superstates;
2840       if (locked_superstates == cache->superstates)
2841         return 0;
2842     }
2843
2844   if (cache->semifree_superstate)
2845     {
2846       it = cache->semifree_superstate;
2847       it->next_recyclable->prev_recyclable = it->prev_recyclable;
2848       it->prev_recyclable->next_recyclable = it->next_recyclable;
2849       cache->semifree_superstate = ((it == it->next_recyclable)
2850                                     ? 0
2851                                     : it->next_recyclable);
2852       --cache->semifree_superstates;
2853     }
2854   else
2855     {
2856       while (cache->lru_superstate->locks)
2857         {
2858           cache->lru_superstate = cache->lru_superstate->next_recyclable;
2859           ++locked_superstates;
2860           if (locked_superstates == cache->superstates)
2861             return 0;
2862         }
2863       it = cache->lru_superstate;
2864       it->next_recyclable->prev_recyclable = it->prev_recyclable;
2865       it->prev_recyclable->next_recyclable = it->next_recyclable;
2866       cache->lru_superstate = ((it == it->next_recyclable)
2867                                     ? 0
2868                                     : it->next_recyclable);
2869     }
2870
2871   if (it->transition_refs)
2872     {
2873       struct rx_distinct_future *df;
2874       for (df = it->transition_refs,
2875            df->prev_same_dest->next_same_dest = 0;
2876            df;
2877            df = df->next_same_dest)
2878         {
2879           df->future_frame.inx = cache->instruction_table[rx_cache_miss];
2880           df->future_frame.data = 0;
2881           df->future_frame.data_2 = (void *) df;
2882           df->future = 0;
2883         }
2884       it->transition_refs->prev_same_dest->next_same_dest =
2885         it->transition_refs;
2886     }
2887   {
2888     struct rx_super_edge *tc = it->edges;
2889     while (tc)
2890       {
2891         struct rx_distinct_future * df;
2892         struct rx_super_edge *tct = tc->next;
2893         df = tc->options;
2894         df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
2895         while (df)
2896           {
2897             struct rx_distinct_future *dft = df;
2898             df = df->next_same_super_edge[0];
2899
2900
2901             if (dft->future && dft->future->transition_refs == dft)
2902               {
2903                 dft->future->transition_refs = dft->next_same_dest;
2904                 if (dft->future->transition_refs == dft)
2905                   dft->future->transition_refs = 0;
2906               }
2907             dft->next_same_dest->prev_same_dest = dft->prev_same_dest;
2908             dft->prev_same_dest->next_same_dest = dft->next_same_dest;
2909             rx_cache_free (cache, &cache->free_discernable_futures,
2910                            (char *)dft);
2911           }
2912         rx_cache_free (cache, &cache->free_transition_classes, (char *)tc);
2913         tc = tct;
2914       }
2915   }
2916
2917   if (it->contents->superstate == it)
2918     it->contents->superstate = 0;
2919   release_superset_low (cache, it->contents);
2920   rx_cache_free (cache, &cache->free_superstates, (char *)it);
2921   --cache->superstates;
2922   return 1;
2923 }
2924
2925 #ifdef __STDC__
2926 static char *
2927 rx_cache_get (struct rx_cache * cache,
2928               struct rx_freelist ** freelist)
2929 #else
2930 static char *
2931 rx_cache_get (cache, freelist)
2932      struct rx_cache * cache;
2933      struct rx_freelist ** freelist;
2934 #endif
2935 {
2936   while (!*freelist && rx_really_free_superstate (cache))
2937     ;
2938   if (!*freelist)
2939     return 0;
2940   {
2941     struct rx_freelist * it = *freelist;
2942     *freelist = it->next;
2943     return (char *)it;
2944   }
2945 }
2946
2947 #ifdef __STDC__
2948 static char *
2949 rx_cache_malloc_or_get (struct rx_cache * cache,
2950                         struct rx_freelist ** freelist, int bytes)
2951 #else
2952 static char *
2953 rx_cache_malloc_or_get (cache, freelist, bytes)
2954      struct rx_cache * cache;
2955      struct rx_freelist ** freelist;
2956      int bytes;
2957 #endif
2958 {
2959   if (!*freelist)
2960     {
2961       char * answer = rx_cache_malloc (cache, bytes);
2962       if (answer)
2963         return answer;
2964     }
2965
2966   return rx_cache_get (cache, freelist);
2967 }
2968
2969 #ifdef __STDC__
2970 static char *
2971 rx_cache_get_superstate (struct rx_cache * cache)
2972 #else
2973 static char *
2974 rx_cache_get_superstate (cache)
2975           struct rx_cache * cache;
2976 #endif
2977 {
2978   char * answer;
2979   int bytes = (   sizeof (struct rx_superstate)
2980                +  cache->local_cset_size * sizeof (struct rx_inx));
2981   if (!cache->free_superstates
2982       && (cache->superstates < cache->superstates_allowed))
2983     {
2984       answer = rx_cache_malloc (cache, bytes);
2985       if (answer)
2986         {
2987           ++cache->superstates;
2988           return answer;
2989         }
2990     }
2991   answer = rx_cache_get (cache, &cache->free_superstates);
2992   if (!answer)
2993     {
2994       answer = rx_cache_malloc (cache, bytes);
2995       if (answer)
2996         ++cache->superstates_allowed;
2997     }
2998   ++cache->superstates;
2999   return answer;
3000 }
3001
3002 \f
3003
3004 #ifdef __STDC__
3005 static int
3006 supersetcmp (void * va, void * vb)
3007 #else
3008 static int
3009 supersetcmp (va, vb)
3010      void * va;
3011      void * vb;
3012 #endif
3013 {
3014   struct rx_superset * a = (struct rx_superset *)va;
3015   struct rx_superset * b = (struct rx_superset *)vb;
3016   return (   (a == b)
3017           || (a && b && (a->car == b->car) && (a->cdr == b->cdr)));
3018 }
3019
3020 #ifdef __STDC__
3021 static struct rx_hash_item *
3022 superset_allocator (struct rx_hash_rules * rules, void * val)
3023 #else
3024 static struct rx_hash_item *
3025 superset_allocator (rules, val)
3026      struct rx_hash_rules * rules;
3027      void * val;
3028 #endif
3029 {
3030   struct rx_cache * cache
3031     = ((struct rx_cache *)
3032        ((char *)rules
3033         - (unsigned long)(&((struct rx_cache *)0)->superset_hash_rules)));
3034   struct rx_superset * template = (struct rx_superset *)val;
3035   struct rx_superset * newset
3036     = ((struct rx_superset *)
3037        rx_cache_malloc_or_get (cache,
3038                                &cache->free_supersets,
3039                                sizeof (*template)));
3040   if (!newset)
3041     return 0;
3042   newset->refs = 0;
3043   newset->car = template->car;
3044   newset->id = template->car->id;
3045   newset->cdr = template->cdr;
3046   newset->superstate = 0;
3047   rx_protect_superset (rx, template->cdr);
3048   newset->hash_item.data = (void *)newset;
3049   newset->hash_item.binding = 0;
3050   return &newset->hash_item;
3051 }
3052
3053 #ifdef __STDC__
3054 static struct rx_hash *
3055 super_hash_allocator (struct rx_hash_rules * rules)
3056 #else
3057 static struct rx_hash *
3058 super_hash_allocator (rules)
3059      struct rx_hash_rules * rules;
3060 #endif
3061 {
3062   struct rx_cache * cache
3063     = ((struct rx_cache *)
3064        ((char *)rules
3065         - (unsigned long)(&((struct rx_cache *)0)->superset_hash_rules)));
3066   return ((struct rx_hash *)
3067           rx_cache_malloc_or_get (cache,
3068                                   &cache->free_hash, sizeof (struct rx_hash)));
3069 }
3070
3071
3072 #ifdef __STDC__
3073 static void
3074 super_hash_liberator (struct rx_hash * hash, struct rx_hash_rules * rules)
3075 #else
3076 static void
3077 super_hash_liberator (hash, rules)
3078      struct rx_hash * hash;
3079      struct rx_hash_rules * rules;
3080 #endif
3081 {
3082   struct rx_cache * cache
3083     = ((struct rx_cache *)
3084        (char *)rules - (long)(&((struct rx_cache *)0)->superset_hash_rules));
3085   rx_cache_free (cache, &cache->free_hash, (char *)hash);
3086 }
3087
3088 #ifdef __STDC__
3089 static void
3090 superset_hash_item_liberator (struct rx_hash_item * it,
3091                               struct rx_hash_rules * rules)
3092 #else
3093 static void
3094 superset_hash_item_liberator (it, rules) /* Well, it does ya know. */
3095      struct rx_hash_item * it;
3096      struct rx_hash_rules * rules;
3097 #endif
3098 {
3099 }
3100
3101 int rx_cache_bound = 128;
3102 static int rx_default_cache_got = 0;
3103
3104 #ifdef __STDC__
3105 static int
3106 bytes_for_cache_size (int supers, int cset_size)
3107 #else
3108 static int
3109 bytes_for_cache_size (supers, cset_size)
3110      int supers;
3111      int cset_size;
3112 #endif
3113 {
3114   /* What the hell is this? !!!*/
3115   return (int)
3116     ((float)supers *
3117      (  (1.03 * (float) (  rx_sizeof_bitset (cset_size)
3118                          + sizeof (struct rx_super_edge)))
3119       + (1.80 * (float) sizeof (struct rx_possible_future))
3120       + (float) (  sizeof (struct rx_superstate)
3121                  + cset_size * sizeof (struct rx_inx))));
3122 }
3123
3124 #ifdef __STDC__
3125 static void
3126 rx_morecore (struct rx_cache * cache)
3127 #else
3128 static void
3129 rx_morecore (cache)
3130      struct rx_cache * cache;
3131 #endif
3132 {
3133   if (rx_default_cache_got >= rx_cache_bound)
3134     return;
3135
3136   rx_default_cache_got += 16;
3137   cache->superstates_allowed = rx_cache_bound;
3138   {
3139     struct rx_blocklist ** pos = &cache->memory;
3140     int size = bytes_for_cache_size (16, cache->local_cset_size);
3141     while (*pos)
3142       pos = &(*pos)->next;
3143     *pos = ((struct rx_blocklist *)
3144             malloc (size + sizeof (struct rx_blocklist)));
3145     if (!*pos)
3146       return;
3147
3148     (*pos)->next = 0;
3149     (*pos)->bytes = size;
3150     cache->memory_pos = *pos;
3151     cache->memory_addr = (char *)*pos + sizeof (**pos);
3152     cache->bytes_left = size;
3153   }
3154 }
3155
3156 static struct rx_cache default_cache =
3157 {
3158   {
3159     supersetcmp,
3160     super_hash_allocator,
3161     super_hash_liberator,
3162     superset_allocator,
3163     superset_hash_item_liberator,
3164   },
3165   0,
3166   0,
3167   0,
3168   0,
3169   rx_morecore,
3170
3171   0,
3172   0,
3173   0,
3174   0,
3175   0,
3176
3177   0,
3178   0,
3179
3180   0,
3181
3182   0,
3183   0,
3184   0,
3185   0,
3186   128,
3187
3188   256,
3189   rx_id_instruction_table,
3190
3191   {
3192     0,
3193     0,
3194     {0},
3195     {0},
3196     {0}
3197   }
3198 };
3199
3200 /* This adds an element to a superstate set.  These sets are lists, such
3201  * that lists with == elements are ==.  The empty set is returned by
3202  * superset_cons (rx, 0, 0) and is NOT equivelent to
3203  * (struct rx_superset)0.
3204  */
3205
3206 #ifdef __STDC__
3207 RX_DECL struct rx_superset *
3208 rx_superset_cons (struct rx * rx,
3209                   struct rx_nfa_state *car, struct rx_superset *cdr)
3210 #else
3211 RX_DECL struct rx_superset *
3212 rx_superset_cons (rx, car, cdr)
3213      struct rx * rx;
3214      struct rx_nfa_state *car;
3215      struct rx_superset *cdr;
3216 #endif
3217 {
3218   struct rx_cache * cache = rx->cache;
3219   if (!car && !cdr)
3220     {
3221       if (!cache->empty_superset)
3222         {
3223           cache->empty_superset
3224             = ((struct rx_superset *)
3225                rx_cache_malloc_or_get (cache, &cache->free_supersets,
3226                                        sizeof (struct rx_superset)));
3227           if (!cache->empty_superset)
3228             return 0;
3229           bzero (cache->empty_superset, sizeof (struct rx_superset));
3230           cache->empty_superset->refs = 1000;
3231         }
3232       return cache->empty_superset;
3233     }
3234   {
3235     struct rx_superset template;
3236     struct rx_hash_item * hit;
3237     template.car = car;
3238     template.cdr = cdr;
3239     template.id = car->id;
3240     hit = rx_hash_store (&cache->superset_table,
3241                          (unsigned long)car ^ car->id ^ (unsigned long)cdr,
3242                          (void *)&template,
3243                          &cache->superset_hash_rules);
3244     return (hit
3245             ?  (struct rx_superset *)hit->data
3246             : 0);
3247   }
3248 }
3249
3250 /* This computes a union of two NFA state sets.  The sets do not have the
3251  * same representation though.  One is a RX_SUPERSET structure (part
3252  * of the superstate NFA) and the other is an NFA_STATE_SET (part of the NFA).
3253  */
3254
3255 #ifdef __STDC__
3256 RX_DECL struct rx_superset *
3257 rx_superstate_eclosure_union
3258   (struct rx * rx, struct rx_superset *set, struct rx_nfa_state_set *ecl)
3259 #else
3260 RX_DECL struct rx_superset *
3261 rx_superstate_eclosure_union (rx, set, ecl)
3262      struct rx * rx;
3263      struct rx_superset *set;
3264      struct rx_nfa_state_set *ecl;
3265 #endif
3266 {
3267   if (!ecl)
3268     return set;
3269
3270   if (!set->car)
3271     return rx_superset_cons (rx, ecl->car,
3272                              rx_superstate_eclosure_union (rx, set, ecl->cdr));
3273   if (set->car == ecl->car)
3274     return rx_superstate_eclosure_union (rx, set, ecl->cdr);
3275
3276   {
3277     struct rx_superset * tail;
3278     struct rx_nfa_state * first;
3279
3280     if (set->car > ecl->car)
3281       {
3282         tail = rx_superstate_eclosure_union (rx, set->cdr, ecl);
3283         first = set->car;
3284       }
3285     else
3286       {
3287         tail = rx_superstate_eclosure_union (rx, set, ecl->cdr);
3288         first = ecl->car;
3289       }
3290     if (!tail)
3291       return 0;
3292     else
3293       {
3294         struct rx_superset * answer;
3295         answer = rx_superset_cons (rx, first, tail);
3296         if (!answer)
3297           {
3298             rx_protect_superset (rx, tail);
3299             rx_release_superset (rx, tail);
3300             return 0;
3301           }
3302         else
3303           return answer;
3304       }
3305   }
3306 }
3307
3308
3309 \f
3310
3311 /*
3312  * This makes sure that a list of rx_distinct_futures contains
3313  * a future for each possible set of side effects in the eclosure
3314  * of a given state.  This is some of the work of filling in a
3315  * superstate transition.
3316  */
3317
3318 #ifdef __STDC__
3319 static struct rx_distinct_future *
3320 include_futures (struct rx *rx,
3321                  struct rx_distinct_future *df, struct rx_nfa_state
3322                  *state, struct rx_superstate *superstate)
3323 #else
3324 static struct rx_distinct_future *
3325 include_futures (rx, df, state, superstate)
3326      struct rx *rx;
3327      struct rx_distinct_future *df;
3328      struct rx_nfa_state *state;
3329      struct rx_superstate *superstate;
3330 #endif
3331 {
3332   struct rx_possible_future *future;
3333   struct rx_cache * cache = rx->cache;
3334   for (future = state->futures; future; future = future->next)
3335     {
3336       struct rx_distinct_future *dfp;
3337       struct rx_distinct_future *insert_before = 0;
3338       if (df)
3339         df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
3340       for (dfp = df; dfp; dfp = dfp->next_same_super_edge[0])
3341         if (dfp->effects == future->effects)
3342           break;
3343         else
3344           {
3345             int order = rx->se_list_cmp (rx, dfp->effects, future->effects);
3346             if (order > 0)
3347               {
3348                 insert_before = dfp;
3349                 dfp = 0;
3350                 break;
3351               }
3352           }
3353       if (df)
3354         df->next_same_super_edge[1]->next_same_super_edge[0] = df;
3355       if (!dfp)
3356         {
3357           dfp
3358             = ((struct rx_distinct_future *)
3359                rx_cache_malloc_or_get (cache, &cache->free_discernable_futures,
3360                                        sizeof (struct rx_distinct_future)));
3361           if (!dfp)
3362             return 0;
3363           if (!df)
3364             {
3365               df = insert_before = dfp;
3366               df->next_same_super_edge[0] = df->next_same_super_edge[1] = df;
3367             }
3368           else if (!insert_before)
3369             insert_before = df;
3370           else if (insert_before == df)
3371             df = dfp;
3372
3373           dfp->next_same_super_edge[0] = insert_before;
3374           dfp->next_same_super_edge[1]
3375             = insert_before->next_same_super_edge[1];
3376           dfp->next_same_super_edge[1]->next_same_super_edge[0] = dfp;
3377           dfp->next_same_super_edge[0]->next_same_super_edge[1] = dfp;
3378           dfp->next_same_dest = dfp->prev_same_dest = dfp;
3379           dfp->future = 0;
3380           dfp->present = superstate;
3381           dfp->future_frame.inx = rx->instruction_table[rx_cache_miss];
3382           dfp->future_frame.data = 0;
3383           dfp->future_frame.data_2 = (void *) dfp;
3384           dfp->side_effects_frame.inx
3385             = rx->instruction_table[rx_do_side_effects];
3386           dfp->side_effects_frame.data = 0;
3387           dfp->side_effects_frame.data_2 = (void *) dfp;
3388           dfp->effects = future->effects;
3389         }
3390     }
3391   return df;
3392 }
3393 \f
3394
3395
3396 /* This constructs a new superstate from its state set.  The only
3397  * complexity here is memory management.
3398  */
3399 #ifdef __STDC__
3400 RX_DECL struct rx_superstate *
3401 rx_superstate (struct rx *rx,
3402                struct rx_superset *set)
3403 #else
3404 RX_DECL struct rx_superstate *
3405 rx_superstate (rx, set)
3406      struct rx *rx;
3407      struct rx_superset *set;
3408 #endif
3409 {
3410   struct rx_cache * cache = rx->cache;
3411   struct rx_superstate * superstate = 0;
3412
3413   /* Does the superstate already exist in the cache? */
3414   if (set->superstate)
3415     {
3416       if (set->superstate->rx_id != rx->rx_id)
3417         {
3418           /* Aha.  It is in the cache, but belongs to a superstate
3419            * that refers to an NFA that no longer exists.
3420            * (We know it no longer exists because it was evidently
3421            *  stored in the same region of memory as the current nfa
3422            *  yet it has a different id.)
3423            */
3424           superstate = set->superstate;
3425           if (!superstate->is_semifree)
3426             {
3427               if (cache->lru_superstate == superstate)
3428                 {
3429                   cache->lru_superstate = superstate->next_recyclable;
3430                   if (cache->lru_superstate == superstate)
3431                     cache->lru_superstate = 0;
3432                 }
3433               {
3434                 superstate->next_recyclable->prev_recyclable
3435                   = superstate->prev_recyclable;
3436                 superstate->prev_recyclable->next_recyclable
3437                   = superstate->next_recyclable;
3438                 if (!cache->semifree_superstate)
3439                   {
3440                     (cache->semifree_superstate
3441                      = superstate->next_recyclable
3442                      = superstate->prev_recyclable
3443                      = superstate);
3444                   }
3445                 else
3446                   {
3447                     superstate->next_recyclable = cache->semifree_superstate;
3448                     superstate->prev_recyclable
3449                       = cache->semifree_superstate->prev_recyclable;
3450                     superstate->next_recyclable->prev_recyclable
3451                       = superstate;
3452                     superstate->prev_recyclable->next_recyclable
3453                       = superstate;
3454                     cache->semifree_superstate = superstate;
3455                   }
3456                 ++cache->semifree_superstates;
3457               }
3458             }
3459           set->superstate = 0;
3460           goto handle_cache_miss;
3461         }
3462       ++cache->hits;
3463       superstate = set->superstate;
3464
3465       rx_refresh_this_superstate (cache, superstate);
3466       return superstate;
3467     }
3468
3469  handle_cache_miss:
3470
3471   /* This point reached only for cache misses. */
3472   ++cache->misses;
3473 #if RX_DEBUG
3474   if (rx_debug_trace > 1)
3475     {
3476       struct rx_superset * setp = set;
3477       fprintf (stderr, "Building a superstet %d(%d): ", rx->rx_id, set);
3478       while (setp)
3479         {
3480           fprintf (stderr, "%d ", setp->id);
3481           setp = setp->cdr;
3482         }
3483       fprintf (stderr, "(%d)\n", set);
3484     }
3485 #endif
3486   superstate = (struct rx_superstate *)rx_cache_get_superstate (cache);
3487   if (!superstate)
3488     return 0;
3489
3490   if (!cache->lru_superstate)
3491     (cache->lru_superstate
3492      = superstate->next_recyclable
3493      = superstate->prev_recyclable
3494      = superstate);
3495   else
3496     {
3497       superstate->next_recyclable = cache->lru_superstate;
3498       superstate->prev_recyclable = cache->lru_superstate->prev_recyclable;
3499       (  superstate->prev_recyclable->next_recyclable
3500        = superstate->next_recyclable->prev_recyclable
3501        = superstate);
3502     }
3503   superstate->rx_id = rx->rx_id;
3504   superstate->transition_refs = 0;
3505   superstate->locks = 0;
3506   superstate->is_semifree = 0;
3507   set->superstate = superstate;
3508   superstate->contents = set;
3509   rx_protect_superset (rx, set);
3510   superstate->edges = 0;
3511   {
3512     int x;
3513     /* None of the transitions from this superstate are known yet. */
3514     for (x = 0; x < rx->local_cset_size; ++x) /* &&&&& 3.8 % */
3515       {
3516         struct rx_inx * ifr = &superstate->transitions[x];
3517         ifr->inx = rx->instruction_table [rx_cache_miss];
3518         ifr->data = ifr->data_2 = 0;
3519       }
3520   }
3521   return superstate;
3522 }
3523 \f
3524
3525 /* This computes the destination set of one edge of the superstate NFA.
3526  * Note that a RX_DISTINCT_FUTURE is a superstate edge.
3527  * Returns 0 on an allocation failure.
3528  */
3529
3530 #ifdef __STDC__
3531 static int
3532 solve_destination (struct rx *rx, struct rx_distinct_future *df)
3533 #else
3534 static int
3535 solve_destination (rx, df)
3536      struct rx *rx;
3537      struct rx_distinct_future *df;
3538 #endif
3539 {
3540   struct rx_super_edge *tc = df->edge;
3541   struct rx_superset *nfa_state;
3542   struct rx_superset *nil_set = rx_superset_cons (rx, 0, 0);
3543   struct rx_superset *solution = nil_set;
3544   struct rx_superstate *dest;
3545
3546   rx_protect_superset (rx, solution);
3547   /* Iterate over all NFA states in the state set of this superstate. */
3548   for (nfa_state = df->present->contents;
3549        nfa_state->car;
3550        nfa_state = nfa_state->cdr)
3551     {
3552       struct rx_nfa_edge *e;
3553       /* Iterate over all edges of each NFA state. */
3554       for (e = nfa_state->car->edges; e; e = e->next)
3555         /* If we find an edge that is labeled with
3556          * the characters we are solving for.....
3557          */
3558         if (rx_bitset_is_subset (rx->local_cset_size,
3559                                  tc->cset, e->params.cset))
3560           {
3561             struct rx_nfa_state *n = e->dest;
3562             struct rx_possible_future *pf;
3563             /* ....search the partial epsilon closures of the destination
3564              * of that edge for a path that involves the same set of
3565              * side effects we are solving for.
3566              * If we find such a RX_POSSIBLE_FUTURE, we add members to the
3567              * stateset we are computing.
3568              */
3569             for (pf = n->futures; pf; pf = pf->next)
3570               if (pf->effects == df->effects)
3571                 {
3572                   struct rx_superset * old_sol;
3573                   old_sol = solution;
3574                   solution = rx_superstate_eclosure_union (rx, solution,
3575                                                            pf->destset);
3576                   if (!solution)
3577                     return 0;
3578                   rx_protect_superset (rx, solution);
3579                   rx_release_superset (rx, old_sol);
3580                 }
3581           }
3582     }
3583   /* It is possible that the RX_DISTINCT_FUTURE we are working on has
3584    * the empty set of NFA states as its definition.  In that case, this
3585    * is a failure point.
3586    */
3587   if (solution == nil_set)
3588     {
3589       df->future_frame.inx = (void *) rx_backtrack;
3590       df->future_frame.data = 0;
3591       df->future_frame.data_2 = 0;
3592       return 1;
3593     }
3594   dest = rx_superstate (rx, solution);
3595   rx_release_superset (rx, solution);
3596   if (!dest)
3597     return 0;
3598
3599   {
3600     struct rx_distinct_future *dft;
3601     dft = df;
3602     df->prev_same_dest->next_same_dest = 0;
3603     while (dft)
3604       {
3605         dft->future = dest;
3606         dft->future_frame.inx = rx->instruction_table[rx_next_char];
3607         dft->future_frame.data = (void *) dest->transitions;
3608         dft = dft->next_same_dest;
3609       }
3610     df->prev_same_dest->next_same_dest = df;
3611   }
3612   if (!dest->transition_refs)
3613     dest->transition_refs = df;
3614   else
3615     {
3616       struct rx_distinct_future *dft = dest->transition_refs->next_same_dest;
3617       dest->transition_refs->next_same_dest = df->next_same_dest;
3618       df->next_same_dest->prev_same_dest = dest->transition_refs;
3619       df->next_same_dest = dft;
3620       dft->prev_same_dest = df;
3621     }
3622   return 1;
3623 }
3624
3625
3626 /* This takes a superstate and a character, and computes some edges
3627  * from the superstate NFA.  In particular, this computes all edges
3628  * that lead from SUPERSTATE given CHR.   This function also
3629  * computes the set of characters that share this edge set.
3630  * This returns 0 on allocation error.
3631  * The character set and list of edges are returned through
3632  * the paramters CSETOUT and DFOUT.
3633 } */
3634
3635 #ifdef __STDC__
3636 static int
3637 compute_super_edge (struct rx *rx, struct rx_distinct_future **dfout,
3638                           rx_Bitset csetout, struct rx_superstate *superstate,
3639                           unsigned char chr)
3640 #else
3641 static int
3642 compute_super_edge (rx, dfout, csetout, superstate, chr)
3643      struct rx *rx;
3644      struct rx_distinct_future **dfout;
3645      rx_Bitset csetout;
3646      struct rx_superstate *superstate;
3647      unsigned char chr;
3648 #endif
3649 {
3650   struct rx_superset *stateset = superstate->contents;
3651
3652   /* To compute the set of characters that share edges with CHR,
3653    * we start with the full character set, and subtract.
3654    */
3655   rx_bitset_universe (rx->local_cset_size, csetout);
3656   *dfout = 0;
3657
3658   /* Iterate over the NFA states in the superstate state-set. */
3659   while (stateset->car)
3660     {
3661       struct rx_nfa_edge *e;
3662       for (e = stateset->car->edges; e; e = e->next)
3663         if (RX_bitset_member (e->params.cset, chr))
3664           {
3665             /* If we find an NFA edge that applies, we make sure there
3666              * are corresponding edges in the superstate NFA.
3667              */
3668             {
3669               struct rx_distinct_future * saved;
3670               saved = *dfout;
3671               *dfout = include_futures (rx, *dfout, e->dest, superstate);
3672               if (!*dfout)
3673                 {
3674                   struct rx_distinct_future * df;
3675                   df = saved;
3676                   if (df)
3677                     df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
3678                   while (df)
3679                     {
3680                       struct rx_distinct_future *dft;
3681                       dft = df;
3682                       df = df->next_same_super_edge[0];
3683
3684                       if (dft->future && dft->future->transition_refs == dft)
3685                         {
3686                           dft->future->transition_refs = dft->next_same_dest;
3687                           if (dft->future->transition_refs == dft)
3688                             dft->future->transition_refs = 0;
3689                         }
3690                       dft->next_same_dest->prev_same_dest = dft->prev_same_dest;
3691                       dft->prev_same_dest->next_same_dest = dft->next_same_dest;
3692                       rx_cache_free (rx->cache,
3693                                      &rx->cache->free_discernable_futures,
3694                                      (char *)dft);
3695                     }
3696                   return 0;
3697                 }
3698             }
3699             /* We also trim the character set a bit. */
3700             rx_bitset_intersection (rx->local_cset_size,
3701                                     csetout, e->params.cset);
3702           }
3703         else
3704           /* An edge that doesn't apply at least tells us some characters
3705            * that don't share the same edge set as CHR.
3706            */
3707           rx_bitset_difference (rx->local_cset_size, csetout, e->params.cset);
3708       stateset = stateset->cdr;
3709     }
3710   return 1;
3711 }
3712 \f
3713
3714 /* This is a constructor for RX_SUPER_EDGE structures.  These are
3715  * wrappers for lists of superstate NFA edges that share character sets labels.
3716  * If a transition class contains more than one rx_distinct_future (superstate
3717  * edge), then it represents a non-determinism in the superstate NFA.
3718  */
3719
3720 #ifdef __STDC__
3721 static struct rx_super_edge *
3722 rx_super_edge (struct rx *rx,
3723                struct rx_superstate *super, rx_Bitset cset,
3724                struct rx_distinct_future *df)
3725 #else
3726 static struct rx_super_edge *
3727 rx_super_edge (rx, super, cset, df)
3728      struct rx *rx;
3729      struct rx_superstate *super;
3730      rx_Bitset cset;
3731      struct rx_distinct_future *df;
3732 #endif
3733 {
3734   struct rx_super_edge *tc =
3735     (struct rx_super_edge *)rx_cache_malloc_or_get
3736       (rx->cache, &rx->cache->free_transition_classes,
3737        sizeof (struct rx_super_edge) + rx_sizeof_bitset (rx->local_cset_size));
3738
3739   if (!tc)
3740     return 0;
3741   tc->next = super->edges;
3742   super->edges = tc;
3743   tc->rx_backtrack_frame.inx = rx->instruction_table[rx_backtrack_point];
3744   tc->rx_backtrack_frame.data = 0;
3745   tc->rx_backtrack_frame.data_2 = (void *) tc;
3746   tc->options = df;
3747   tc->cset = (rx_Bitset) ((char *) tc + sizeof (*tc));
3748   rx_bitset_assign (rx->local_cset_size, tc->cset, cset);
3749   if (df)
3750     {
3751       struct rx_distinct_future * dfp = df;
3752       df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
3753       while (dfp)
3754         {
3755           dfp->edge = tc;
3756           dfp = dfp->next_same_super_edge[0];
3757         }
3758       df->next_same_super_edge[1]->next_same_super_edge[0] = df;
3759     }
3760   return tc;
3761 }
3762
3763
3764 /* There are three kinds of cache miss.  The first occurs when a
3765  * transition is taken that has never been computed during the
3766  * lifetime of the source superstate.  That cache miss is handled by
3767  * calling COMPUTE_SUPER_EDGE.  The second kind of cache miss
3768  * occurs when the destination superstate of a transition doesn't
3769  * exist.  SOLVE_DESTINATION is used to construct the destination superstate.
3770  * Finally, the third kind of cache miss occurs when the destination
3771  * superstate of a transition is in a `semi-free state'.  That case is
3772  * handled by UNFREE_SUPERSTATE.
3773  *
3774  * The function of HANDLE_CACHE_MISS is to figure out which of these
3775  * cases applies.
3776  */
3777
3778 #ifdef __STDC__
3779 static void
3780 install_partial_transition  (struct rx_superstate *super,
3781                              struct rx_inx *answer,
3782                              RX_subset set, int offset)
3783 #else
3784 static void
3785 install_partial_transition  (super, answer, set, offset)
3786      struct rx_superstate *super;
3787      struct rx_inx *answer;
3788      RX_subset set;
3789      int offset;
3790 #endif
3791 {
3792   int start = offset;
3793   int end = start + 32;
3794   RX_subset pos = 1;
3795   struct rx_inx * transitions = super->transitions;
3796
3797   while (start < end)
3798     {
3799       if (set & pos)
3800         transitions[start] = *answer;
3801       pos <<= 1;
3802       ++start;
3803     }
3804 }
3805
3806
3807 #ifdef __STDC__
3808 RX_DECL struct rx_inx *
3809 rx_handle_cache_miss
3810   (struct rx *rx, struct rx_superstate *super, unsigned char chr, void *data)
3811 #else
3812 RX_DECL struct rx_inx *
3813 rx_handle_cache_miss (rx, super, chr, data)
3814      struct rx *rx;
3815      struct rx_superstate *super;
3816      unsigned char chr;
3817      void *data;
3818 #endif
3819 {
3820   int offset = chr / RX_subset_bits;
3821   struct rx_distinct_future *df = data;
3822
3823   if (!df)                      /* must be the shared_cache_miss_frame */
3824     {
3825       /* Perhaps this is just a transition waiting to be filled. */
3826       struct rx_super_edge *tc;
3827       RX_subset mask = rx_subset_singletons [chr % RX_subset_bits];
3828
3829       for (tc = super->edges; tc; tc = tc->next)
3830         if (tc->cset[offset] & mask)
3831           {
3832             struct rx_inx * answer;
3833             df = tc->options;
3834             answer = ((tc->options->next_same_super_edge[0] != tc->options)
3835                       ? &tc->rx_backtrack_frame
3836                       : (df->effects
3837                          ? &df->side_effects_frame
3838                          : &df->future_frame));
3839             install_partial_transition (super, answer,
3840                                         tc->cset [offset], offset * 32);
3841             return answer;
3842           }
3843       /* Otherwise, it's a flushed or  newly encountered edge. */
3844       {
3845         char cset_space[1024];  /* this limit is far from unreasonable */
3846         rx_Bitset trcset;
3847         struct rx_inx *answer;
3848
3849         if (rx_sizeof_bitset (rx->local_cset_size) > sizeof (cset_space))
3850           return 0;             /* If the arbitrary limit is hit, always fail */
3851                                 /* cleanly. */
3852         trcset = (rx_Bitset)cset_space;
3853         rx_lock_superstate (rx, super);
3854         if (!compute_super_edge (rx, &df, trcset, super, chr))
3855           {
3856             rx_unlock_superstate (rx, super);
3857             return 0;
3858           }
3859         if (!df)                /* We just computed the fail transition. */
3860           {
3861             static struct rx_inx
3862               shared_fail_frame = { 0, 0, (void *)rx_backtrack, 0 };
3863             answer = &shared_fail_frame;
3864           }
3865         else
3866           {
3867             tc = rx_super_edge (rx, super, trcset, df);
3868             if (!tc)
3869               {
3870                 rx_unlock_superstate (rx, super);
3871                 return 0;
3872               }
3873             answer = ((tc->options->next_same_super_edge[0] != tc->options)
3874                       ? &tc->rx_backtrack_frame
3875                       : (df->effects
3876                          ? &df->side_effects_frame
3877                          : &df->future_frame));
3878           }
3879         install_partial_transition (super, answer,
3880                                     trcset[offset], offset * 32);
3881         rx_unlock_superstate (rx, super);
3882         return answer;
3883       }
3884     }
3885   else if (df->future) /* A cache miss on an edge with a future? Must be
3886                         * a semi-free destination. */
3887     {
3888       if (df->future->is_semifree)
3889         refresh_semifree_superstate (rx->cache, df->future);
3890       return &df->future_frame;
3891     }
3892   else
3893     /* no future superstate on an existing edge */
3894     {
3895       rx_lock_superstate (rx, super);
3896       if (!solve_destination (rx, df))
3897         {
3898           rx_unlock_superstate (rx, super);
3899           return 0;
3900         }
3901       if (!df->effects
3902           && (df->edge->options->next_same_super_edge[0] == df->edge->options))
3903         install_partial_transition (super, &df->future_frame,
3904                                     df->edge->cset[offset], offset * 32);
3905       rx_unlock_superstate (rx, super);
3906       return &df->future_frame;
3907     }
3908 }
3909
3910
3911 \f
3912
3913 /* The rest of the code provides a regex.c compatable interface. */
3914
3915
3916 __const__ char *re_error_msg[] =
3917 {
3918   0,                                            /* REG_NOUT */
3919   "No match",                                   /* REG_NOMATCH */
3920   "Invalid regular expression",                 /* REG_BADPAT */
3921   "Invalid collation character",                /* REG_ECOLLATE */
3922   "Invalid character class name",               /* REG_ECTYPE */
3923   "Trailing backslash",                         /* REG_EESCAPE */
3924   "Invalid back reference",                     /* REG_ESUBREG */
3925   "Unmatched [ or [^",                          /* REG_EBRACK */
3926   "Unmatched ( or \\(",                         /* REG_EPAREN */
3927   "Unmatched \\{",                              /* REG_EBRACE */
3928   "Invalid content of \\{\\}",                  /* REG_BADBR */
3929   "Invalid range end",                          /* REG_ERANGE */
3930   "Memory exhausted",                           /* REG_ESPACE */
3931   "Invalid preceding regular expression",       /* REG_BADRPT */
3932   "Premature end of regular expression",        /* REG_EEND */
3933   "Regular expression too big",                 /* REG_ESIZE */
3934   "Unmatched ) or \\)",                         /* REG_ERPAREN */
3935 };
3936
3937
3938 \f
3939 /*
3940  * Macros used while compiling patterns.
3941  *
3942  * By convention, PEND points just past the end of the uncompiled pattern,
3943  * P points to the read position in the pattern.  `translate' is the name
3944  * of the translation table (`TRANSLATE' is the name of a macro that looks
3945  * things up in `translate').
3946  */
3947
3948
3949 /*
3950  * Fetch the next character in the uncompiled pattern---translating it
3951  * if necessary. *Also cast from a signed character in the constant
3952  * string passed to us by the user to an unsigned char that we can use
3953  * as an array index (in, e.g., `translate').
3954  */
3955 #define PATFETCH(c)                                                     \
3956  do {if (p == pend) return REG_EEND;                                    \
3957     c = (unsigned char) *p++;                                           \
3958     c = translate[c];                                                   \
3959  } while (0)
3960
3961 /*
3962  * Fetch the next character in the uncompiled pattern, with no
3963  * translation.
3964  */
3965 #define PATFETCH_RAW(c)                                                 \
3966   do {if (p == pend) return REG_EEND;                                   \
3967     c = (unsigned char) *p++;                                           \
3968   } while (0)
3969
3970 /* Go backwards one character in the pattern.  */
3971 #define PATUNFETCH p--
3972
3973
3974 #define TRANSLATE(d) translate[(unsigned char) (d)]
3975
3976 typedef unsigned regnum_t;
3977
3978 /* Since offsets can go either forwards or backwards, this type needs to
3979  * be able to hold values from -(MAX_BUF_SIZE - 1) to MAX_BUF_SIZE - 1.
3980  */
3981 typedef int pattern_offset_t;
3982
3983 typedef struct
3984 {
3985   struct rexp_node ** top_expression; /* was begalt */
3986   struct rexp_node ** last_expression; /* was laststart */
3987   pattern_offset_t inner_group_offset;
3988   regnum_t regnum;
3989 } compile_stack_elt_t;
3990
3991 typedef struct
3992 {
3993   compile_stack_elt_t *stack;
3994   unsigned size;
3995   unsigned avail;                       /* Offset of next open position.  */
3996 } compile_stack_type;
3997
3998
3999 #define INIT_COMPILE_STACK_SIZE 32
4000
4001 #define COMPILE_STACK_EMPTY  (compile_stack.avail == 0)
4002 #define COMPILE_STACK_FULL  (compile_stack.avail == compile_stack.size)
4003
4004 /* The next available element.  */
4005 #define COMPILE_STACK_TOP (compile_stack.stack[compile_stack.avail])
4006
4007
4008 /* Set the bit for character C in a list.  */
4009 #define SET_LIST_BIT(c)                               \
4010   (b[((unsigned char) (c)) / CHARBITS]               \
4011    |= 1 << (((unsigned char) c) % CHARBITS))
4012
4013 /* Get the next unsigned number in the uncompiled pattern.  */
4014 #define GET_UNSIGNED_NUMBER(num)                                        \
4015   { if (p != pend)                                                      \
4016      {                                                                  \
4017        PATFETCH (c);                                                    \
4018        while (isdigit (c))                                              \
4019          {                                                              \
4020            if (num < 0)                                                 \
4021               num = 0;                                                  \
4022            num = num * 10 + c - '0';                                    \
4023            if (p == pend)                                               \
4024               break;                                                    \
4025            PATFETCH (c);                                                \
4026          }                                                              \
4027        }                                                                \
4028     }
4029
4030 #define CHAR_CLASS_MAX_LENGTH  6 /* Namely, `xdigit'.  */
4031
4032 #define IS_CHAR_CLASS(string)                                           \
4033    (!strcmp (string, "alpha") || !strcmp (string, "upper")              \
4034     || !strcmp (string, "lower") || !strcmp (string, "digit")           \
4035     || !strcmp (string, "alnum") || !strcmp (string, "xdigit")          \
4036     || !strcmp (string, "space") || !strcmp (string, "print")           \
4037     || !strcmp (string, "punct") || !strcmp (string, "graph")           \
4038     || !strcmp (string, "cntrl") || !strcmp (string, "blank"))
4039
4040 \f
4041 /* These predicates are used in regex_compile. */
4042
4043 /* P points to just after a ^ in PATTERN.  Return true if that ^ comes
4044  * after an alternative or a begin-subexpression.  We assume there is at
4045  * least one character before the ^.
4046  */
4047
4048 #ifdef __STDC__
4049 static boolean
4050 at_begline_loc_p (__const__ char *pattern, __const__ char * p, reg_syntax_t syntax)
4051 #else
4052 static boolean
4053 at_begline_loc_p (pattern, p, syntax)
4054      __const__ char *pattern;
4055      __const__ char * p;
4056      reg_syntax_t syntax;
4057 #endif
4058 {
4059   __const__ char *prev = p - 2;
4060   boolean prev_prev_backslash = ((prev > pattern) && (prev[-1] == '\\'));
4061
4062     return
4063
4064       (/* After a subexpression?  */
4065        ((*prev == '(') && ((syntax & RE_NO_BK_PARENS) || prev_prev_backslash))
4066        ||
4067        /* After an alternative?  */
4068        ((*prev == '|') && ((syntax & RE_NO_BK_VBAR) || prev_prev_backslash))
4069        );
4070 }
4071
4072 /* The dual of at_begline_loc_p.  This one is for $.  We assume there is
4073  * at least one character after the $, i.e., `P < PEND'.
4074  */
4075
4076 #ifdef __STDC__
4077 static boolean
4078 at_endline_loc_p (__const__ char *p, __const__ char *pend, int syntax)
4079 #else
4080 static boolean
4081 at_endline_loc_p (p, pend, syntax)
4082      __const__ char *p;
4083      __const__ char *pend;
4084      int syntax;
4085 #endif
4086 {
4087   __const__ char *next = p;
4088   boolean next_backslash = (*next == '\\');
4089   __const__ char *next_next = (p + 1 < pend) ? (p + 1) : 0;
4090
4091   return
4092     (
4093      /* Before a subexpression?  */
4094      ((syntax & RE_NO_BK_PARENS)
4095       ? (*next == ')')
4096       : (next_backslash && next_next && (*next_next == ')')))
4097     ||
4098      /* Before an alternative?  */
4099      ((syntax & RE_NO_BK_VBAR)
4100       ? (*next == '|')
4101       : (next_backslash && next_next && (*next_next == '|')))
4102      );
4103 }
4104 \f
4105
4106 unsigned char rx_id_translation[256] =
4107 {
4108   0,  1,  2,  3,  4,  5,  6,  7,  8,  9,
4109  10, 11, 12, 13, 14, 15, 16, 17, 18, 19,
4110  20, 21, 22, 23, 24, 25, 26, 27, 28, 29,
4111  30, 31, 32, 33, 34, 35, 36, 37, 38, 39,
4112  40, 41, 42, 43, 44, 45, 46, 47, 48, 49,
4113  50, 51, 52, 53, 54, 55, 56, 57, 58, 59,
4114  60, 61, 62, 63, 64, 65, 66, 67, 68, 69,
4115  70, 71, 72, 73, 74, 75, 76, 77, 78, 79,
4116  80, 81, 82, 83, 84, 85, 86, 87, 88, 89,
4117  90, 91, 92, 93, 94, 95, 96, 97, 98, 99,
4118
4119  100, 101, 102, 103, 104, 105, 106, 107, 108, 109,
4120  110, 111, 112, 113, 114, 115, 116, 117, 118, 119,
4121  120, 121, 122, 123, 124, 125, 126, 127, 128, 129,
4122  130, 131, 132, 133, 134, 135, 136, 137, 138, 139,
4123  140, 141, 142, 143, 144, 145, 146, 147, 148, 149,
4124  150, 151, 152, 153, 154, 155, 156, 157, 158, 159,
4125  160, 161, 162, 163, 164, 165, 166, 167, 168, 169,
4126  170, 171, 172, 173, 174, 175, 176, 177, 178, 179,
4127  180, 181, 182, 183, 184, 185, 186, 187, 188, 189,
4128  190, 191, 192, 193, 194, 195, 196, 197, 198, 199,
4129
4130  200, 201, 202, 203, 204, 205, 206, 207, 208, 209,
4131  210, 211, 212, 213, 214, 215, 216, 217, 218, 219,
4132  220, 221, 222, 223, 224, 225, 226, 227, 228, 229,
4133  230, 231, 232, 233, 234, 235, 236, 237, 238, 239,
4134  240, 241, 242, 243, 244, 245, 246, 247, 248, 249,
4135  250, 251, 252, 253, 254, 255
4136 };
4137
4138 /* The compiler keeps an inverted translation table.
4139  * This looks up/inititalize elements.
4140  * VALID is an array of booleans that validate CACHE.
4141  */
4142
4143 #ifdef __STDC__
4144 static rx_Bitset
4145 inverse_translation (struct re_pattern_buffer * rxb,
4146                      char * valid, rx_Bitset cache,
4147                      unsigned char * translate, int c)
4148 #else
4149 static rx_Bitset
4150 inverse_translation (rxb, valid, cache, translate, c)
4151      struct re_pattern_buffer * rxb;
4152      char * valid;
4153      rx_Bitset cache;
4154      unsigned char * translate;
4155      int c;
4156 #endif
4157 {
4158   rx_Bitset cs
4159     = cache + c * rx_bitset_numb_subsets (rxb->rx.local_cset_size);
4160
4161   if (!valid[c])
4162     {
4163       int x;
4164       int c_tr = TRANSLATE(c);
4165       rx_bitset_null (rxb->rx.local_cset_size, cs);
4166       for (x = 0; x < 256; ++x) /* &&&& 13.37 */
4167         if (TRANSLATE(x) == c_tr)
4168           RX_bitset_enjoin (cs, x);
4169       valid[c] = 1;
4170     }
4171   return cs;
4172 }
4173
4174 \f
4175
4176
4177 /* More subroutine declarations and macros for regex_compile.  */
4178
4179 /* Returns true if REGNUM is in one of COMPILE_STACK's elements and
4180    false if it's not.  */
4181
4182 #ifdef __STDC__
4183 static boolean
4184 group_in_compile_stack (compile_stack_type compile_stack, regnum_t regnum)
4185 #else
4186 static boolean
4187 group_in_compile_stack (compile_stack, regnum)
4188     compile_stack_type compile_stack;
4189     regnum_t regnum;
4190 #endif
4191 {
4192   int this_element;
4193
4194   for (this_element = compile_stack.avail - 1;
4195        this_element >= 0;
4196        this_element--)
4197     if (compile_stack.stack[this_element].regnum == regnum)
4198       return true;
4199
4200   return false;
4201 }
4202
4203
4204 /*
4205  * Read the ending character of a range (in a bracket expression) from the
4206  * uncompiled pattern *P_PTR (which ends at PEND).  We assume the
4207  * starting character is in `P[-2]'.  (`P[-1]' is the character `-'.)
4208  * Then we set the translation of all bits between the starting and
4209  * ending characters (inclusive) in the compiled pattern B.
4210  *
4211  * Return an error code.
4212  *
4213  * We use these short variable names so we can use the same macros as
4214  * `regex_compile' itself.
4215  */
4216
4217 #ifdef __STDC__
4218 static reg_errcode_t
4219 compile_range (struct re_pattern_buffer * rxb, rx_Bitset cs,
4220                __const__ char ** p_ptr, __const__ char * pend,
4221                unsigned char * translate, reg_syntax_t syntax,
4222                rx_Bitset inv_tr,  char * valid_inv_tr)
4223 #else
4224 static reg_errcode_t
4225 compile_range (rxb, cs, p_ptr, pend, translate, syntax, inv_tr, valid_inv_tr)
4226      struct re_pattern_buffer * rxb;
4227      rx_Bitset cs;
4228      __const__ char ** p_ptr;
4229      __const__ char * pend;
4230      unsigned char * translate;
4231      reg_syntax_t syntax;
4232      rx_Bitset inv_tr;
4233      char * valid_inv_tr;
4234 #endif
4235 {
4236   unsigned this_char;
4237
4238   __const__ char *p = *p_ptr;
4239
4240   unsigned char range_end;
4241   unsigned char range_start = TRANSLATE(p[-2]);
4242
4243   if (p == pend)
4244     return REG_ERANGE;
4245
4246   PATFETCH (range_end);
4247
4248   (*p_ptr)++;
4249
4250   if (range_start > range_end)
4251     return syntax & RE_NO_EMPTY_RANGES ? REG_ERANGE : REG_NOERROR;
4252
4253   for (this_char = range_start; this_char <= range_end; this_char++)
4254     {
4255       rx_Bitset it =
4256         inverse_translation (rxb, valid_inv_tr, inv_tr, translate, this_char);
4257       rx_bitset_union (rxb->rx.local_cset_size, cs, it);
4258     }
4259
4260   return REG_NOERROR;
4261 }
4262 \f
4263
4264 /* This searches a regexp for backreference side effects.
4265  * It fills in the array OUT with 1 at the index of every register pair
4266  * referenced by a backreference.
4267  *
4268  * This is used to help optimize patterns for searching.  The information is
4269  * useful because, if the caller doesn't want register values, backreferenced
4270  * registers are the only registers for which we need rx_backtrack.
4271  */
4272
4273 #ifdef __STDC__
4274 static void
4275 find_backrefs (char * out, struct rexp_node * rexp,
4276                struct re_se_params * params)
4277 #else
4278 static void
4279 find_backrefs (out, rexp, params)
4280      char * out;
4281      struct rexp_node * rexp;
4282      struct re_se_params * params;
4283 #endif
4284 {
4285   if (rexp)
4286     switch (rexp->type)
4287       {
4288       case r_cset:
4289       case r_data:
4290         return;
4291       case r_alternate:
4292       case r_concat:
4293       case r_opt:
4294       case r_star:
4295       case r_2phase_star:
4296         find_backrefs (out, rexp->params.pair.left, params);
4297         find_backrefs (out, rexp->params.pair.right, params);
4298         return;
4299       case r_side_effect:
4300         if (   ((long)rexp->params.side_effect >= 0)
4301             && (params [(long)rexp->params.side_effect].se == re_se_backref))
4302           out[ params [(long)rexp->params.side_effect].op1] = 1;
4303         return;
4304       }
4305 }
4306
4307 \f
4308
4309 /* Returns 0 unless the pattern can match the empty string. */
4310
4311 #ifdef __STDC__
4312 static int
4313 compute_fastset (struct re_pattern_buffer * rxb, struct rexp_node * rexp)
4314 #else
4315 static int
4316 compute_fastset (rxb, rexp)
4317      struct re_pattern_buffer * rxb;
4318      struct rexp_node * rexp;
4319 #endif
4320 {
4321   if (!rexp)
4322     return 1;
4323   switch (rexp->type)
4324     {
4325     case r_data:
4326       return 1;
4327     case r_cset:
4328       {
4329         rx_bitset_union (rxb->rx.local_cset_size,
4330                          rxb->fastset, rexp->params.cset);
4331       }
4332       return 0;
4333     case r_concat:
4334       return (compute_fastset (rxb, rexp->params.pair.left)
4335               && compute_fastset (rxb, rexp->params.pair.right));
4336     case r_2phase_star:
4337       compute_fastset (rxb, rexp->params.pair.left);
4338       /* compute_fastset (rxb, rexp->params.pair.right);  nope... */
4339       return 1;
4340     case r_alternate:
4341       return !!(compute_fastset (rxb, rexp->params.pair.left)
4342                 + compute_fastset (rxb, rexp->params.pair.right));
4343     case r_opt:
4344     case r_star:
4345       compute_fastset (rxb, rexp->params.pair.left);
4346       return 1;
4347     case r_side_effect:
4348       return 1;
4349     }
4350
4351   /* this should never happen */
4352   return 0;
4353 }
4354 \f
4355
4356 /* returns
4357  *  1 -- yes, definately anchored by the given side effect.
4358  *  2 -- maybe anchored, maybe the empty string.
4359  *  0 -- definately not anchored
4360  *  There is simply no other possibility.
4361  */
4362
4363 #ifdef __STDC__
4364 static int
4365 is_anchored (struct rexp_node * rexp, rx_side_effect se)
4366 #else
4367 static int
4368 is_anchored (rexp, se)
4369      struct rexp_node * rexp;
4370      rx_side_effect se;
4371 #endif
4372 {
4373   if (!rexp)
4374     return 2;
4375   switch (rexp->type)
4376     {
4377     case r_cset:
4378     case r_data:
4379       return 0;
4380     case r_concat:
4381     case r_2phase_star:
4382       {
4383         int l = is_anchored (rexp->params.pair.left, se);
4384         return (l == 2 ? is_anchored (rexp->params.pair.right, se) : l);
4385       }
4386     case r_alternate:
4387       {
4388         int l = is_anchored (rexp->params.pair.left, se);
4389         int r = l ? is_anchored (rexp->params.pair.right, se) : 0;
4390
4391         if (l == r)
4392           return l;
4393         else if ((l == 0) || (r == 0))
4394           return 0;
4395         else
4396           return 2;
4397       }
4398     case r_opt:
4399     case r_star:
4400       return is_anchored (rexp->params.pair.left, se) ? 2 : 0;
4401
4402     case r_side_effect:
4403       return ((rexp->params.side_effect == se)
4404               ? 1 : 2);
4405     }
4406
4407   /* this should never happen */
4408   return 0;
4409 }
4410
4411 \f
4412 /* This removes register assignments that aren't required by backreferencing.
4413  * This can speed up explore_future, especially if it eliminates
4414  * non-determinism in the superstate NFA.
4415  *
4416  * NEEDED is an array of characters, presumably filled in by FIND_BACKREFS.
4417  * The non-zero elements of the array indicate which register assignments
4418  * can NOT be removed from the expression.
4419  */
4420
4421 #ifdef __STDC__
4422 static struct rexp_node *
4423 remove_unecessary_side_effects (struct rx * rx, char * needed,
4424                                 struct rexp_node * rexp,
4425                                 struct re_se_params * params)
4426 #else
4427 static struct rexp_node *
4428 remove_unecessary_side_effects (rx, needed, rexp, params)
4429      struct rx * rx;
4430      char * needed;
4431      struct rexp_node * rexp;
4432      struct re_se_params * params;
4433 #endif
4434 {
4435   struct rexp_node * l;
4436   struct rexp_node * r;
4437   if (!rexp)
4438     return 0;
4439   else
4440     switch (rexp->type)
4441       {
4442       case r_cset:
4443       case r_data:
4444         return rexp;
4445       case r_alternate:
4446       case r_concat:
4447       case r_2phase_star:
4448         l = remove_unecessary_side_effects (rx, needed,
4449                                             rexp->params.pair.left, params);
4450         r = remove_unecessary_side_effects (rx, needed,
4451                                             rexp->params.pair.right, params);
4452         if ((l && r) || (rexp->type != r_concat))
4453           {
4454             rexp->params.pair.left = l;
4455             rexp->params.pair.right = r;
4456             return rexp;
4457           }
4458         else
4459           {
4460             rexp->params.pair.left = rexp->params.pair.right = 0;
4461             rx_free_rexp (rx, rexp);
4462             return l ? l : r;
4463           }
4464       case r_opt:
4465       case r_star:
4466         l = remove_unecessary_side_effects (rx, needed,
4467                                             rexp->params.pair.left, params);
4468         if (l)
4469           {
4470             rexp->params.pair.left = l;
4471             return rexp;
4472           }
4473         else
4474           {
4475             rexp->params.pair.left = 0;
4476             rx_free_rexp (rx, rexp);
4477             return 0;
4478           }
4479       case r_side_effect:
4480         {
4481           int se = (long)rexp->params.side_effect;
4482           if (   (se >= 0)
4483               && (   ((enum re_side_effects)params[se].se == re_se_lparen)
4484                   || ((enum re_side_effects)params[se].se == re_se_rparen))
4485               && (params [se].op1 > 0)
4486               && (!needed [params [se].op1]))
4487             {
4488               rx_free_rexp (rx, rexp);
4489               return 0;
4490             }
4491           else
4492             return rexp;
4493         }
4494       }
4495
4496   /* this should never happen */
4497   return 0;
4498 }
4499
4500 \f
4501
4502 #ifdef __STDC__
4503 static int
4504 pointless_if_repeated (struct rexp_node * node, struct re_se_params * params)
4505 #else
4506 static int
4507 pointless_if_repeated (node, params)
4508      struct rexp_node * node;
4509      struct re_se_params * params;
4510 #endif
4511 {
4512   if (!node)
4513     return 1;
4514   switch (node->type)
4515     {
4516     case r_cset:
4517       return 0;
4518     case r_alternate:
4519     case r_concat:
4520     case r_2phase_star:
4521       return (pointless_if_repeated (node->params.pair.left, params)
4522               && pointless_if_repeated (node->params.pair.right, params));
4523     case r_opt:
4524     case r_star:
4525       return pointless_if_repeated (node->params.pair.left, params);
4526     case r_side_effect:
4527       switch (((long)node->params.side_effect < 0)
4528               ? (enum re_side_effects)node->params.side_effect
4529               : (enum re_side_effects)params[(long)node->params.side_effect].se)
4530         {
4531         case re_se_try:
4532         case re_se_at_dot:
4533         case re_se_begbuf:
4534         case re_se_hat:
4535         case re_se_wordbeg:
4536         case re_se_wordbound:
4537         case re_se_notwordbound:
4538         case re_se_wordend:
4539         case re_se_endbuf:
4540         case re_se_dollar:
4541         case re_se_fail:
4542         case re_se_win:
4543           return 1;
4544         case re_se_lparen:
4545         case re_se_rparen:
4546         case re_se_iter:
4547         case re_se_end_iter:
4548         case re_se_syntax:
4549         case re_se_not_syntax:
4550         case re_se_backref:
4551           return 0;
4552         }
4553     case r_data:
4554     default:
4555       return 0;
4556     }
4557 }
4558
4559 \f
4560
4561 #ifdef __STDC__
4562 static int
4563 registers_on_stack (struct re_pattern_buffer * rxb,
4564                     struct rexp_node * rexp, int in_danger,
4565                     struct re_se_params * params)
4566 #else
4567 static int
4568 registers_on_stack (rxb, rexp, in_danger, params)
4569      struct re_pattern_buffer * rxb;
4570      struct rexp_node * rexp;
4571      int in_danger;
4572      struct re_se_params * params;
4573 #endif
4574 {
4575   if (!rexp)
4576     return 0;
4577   else
4578     switch (rexp->type)
4579       {
4580       case r_cset:
4581       case r_data:
4582         return 0;
4583       case r_alternate:
4584       case r_concat:
4585         return (   registers_on_stack (rxb, rexp->params.pair.left,
4586                                        in_danger, params)
4587                 || (registers_on_stack
4588                     (rxb, rexp->params.pair.right,
4589                      in_danger, params)));
4590       case r_opt:
4591         return registers_on_stack (rxb, rexp->params.pair.left, 0, params);
4592       case r_star:
4593         return registers_on_stack (rxb, rexp->params.pair.left, 1, params);
4594       case r_2phase_star:
4595         return
4596           (   registers_on_stack (rxb, rexp->params.pair.left, 1, params)
4597            || registers_on_stack (rxb, rexp->params.pair.right, 1, params));
4598       case r_side_effect:
4599         {
4600           int se = (long)rexp->params.side_effect;
4601           if (   in_danger
4602               && (se >= 0)
4603               && (params [se].op1 > 0)
4604               && (   ((enum re_side_effects)params[se].se == re_se_lparen)
4605                   || ((enum re_side_effects)params[se].se == re_se_rparen)))
4606             return 1;
4607           else
4608             return 0;
4609         }
4610       }
4611
4612   /* this should never happen */
4613   return 0;
4614 }
4615
4616 \f
4617
4618 static char idempotent_complex_se[] =
4619 {
4620 #define RX_WANT_SE_DEFS 1
4621 #undef RX_DEF_SE
4622 #undef RX_DEF_CPLX_SE
4623 #define RX_DEF_SE(IDEM, NAME, VALUE)
4624 #define RX_DEF_CPLX_SE(IDEM, NAME, VALUE)     IDEM,
4625 #include "rx.h"
4626 #undef RX_DEF_SE
4627 #undef RX_DEF_CPLX_SE
4628 #undef RX_WANT_SE_DEFS
4629   23
4630 };
4631
4632 static char idempotent_se[] =
4633 {
4634   13,
4635 #define RX_WANT_SE_DEFS 1
4636 #undef RX_DEF_SE
4637 #undef RX_DEF_CPLX_SE
4638 #define RX_DEF_SE(IDEM, NAME, VALUE)          IDEM,
4639 #define RX_DEF_CPLX_SE(IDEM, NAME, VALUE)
4640 #include "rx.h"
4641 #undef RX_DEF_SE
4642 #undef RX_DEF_CPLX_SE
4643 #undef RX_WANT_SE_DEFS
4644   42
4645 };
4646
4647 \f
4648
4649
4650 #ifdef __STDC__
4651 static int
4652 has_any_se (struct rx * rx,
4653             struct rexp_node * rexp)
4654 #else
4655 static int
4656 has_any_se (rx, rexp)
4657      struct rx * rx;
4658      struct rexp_node * rexp;
4659 #endif
4660 {
4661   if (!rexp)
4662     return 0;
4663
4664   switch (rexp->type)
4665     {
4666     case r_cset:
4667     case r_data:
4668       return 0;
4669
4670     case r_side_effect:
4671       return 1;
4672
4673     case r_2phase_star:
4674     case r_concat:
4675     case r_alternate:
4676       return
4677         (   has_any_se (rx, rexp->params.pair.left)
4678          || has_any_se (rx, rexp->params.pair.right));
4679
4680     case r_opt:
4681     case r_star:
4682       return has_any_se (rx, rexp->params.pair.left);
4683     }
4684
4685   /* this should never happen */
4686   return 0;
4687 }
4688
4689 \f
4690
4691 /* This must be called AFTER `convert_hard_loops' for a given REXP. */
4692 #ifdef __STDC__
4693 static int
4694 has_non_idempotent_epsilon_path (struct rx * rx,
4695                                  struct rexp_node * rexp,
4696                                  struct re_se_params * params)
4697 #else
4698 static int
4699 has_non_idempotent_epsilon_path (rx, rexp, params)
4700      struct rx * rx;
4701      struct rexp_node * rexp;
4702      struct re_se_params * params;
4703 #endif
4704 {
4705   if (!rexp)
4706     return 0;
4707
4708   switch (rexp->type)
4709     {
4710     case r_cset:
4711     case r_data:
4712     case r_star:
4713       return 0;
4714
4715     case r_side_effect:
4716       return
4717         !((long)rexp->params.side_effect > 0
4718           ? idempotent_complex_se [ params [(long)rexp->params.side_effect].se ]
4719           : idempotent_se [-(long)rexp->params.side_effect]);
4720
4721     case r_alternate:
4722       return
4723         (   has_non_idempotent_epsilon_path (rx,
4724                                              rexp->params.pair.left, params)
4725          || has_non_idempotent_epsilon_path (rx,
4726                                              rexp->params.pair.right, params));
4727
4728     case r_2phase_star:
4729     case r_concat:
4730       return
4731         (   has_non_idempotent_epsilon_path (rx,
4732                                              rexp->params.pair.left, params)
4733          && has_non_idempotent_epsilon_path (rx,
4734                                              rexp->params.pair.right, params));
4735
4736     case r_opt:
4737       return has_non_idempotent_epsilon_path (rx,
4738                                               rexp->params.pair.left, params);
4739     }
4740
4741   /* this should never happen */
4742   return 0;
4743 }
4744
4745 \f
4746
4747 /* This computes rougly what it's name suggests.   It can (and does) go wrong
4748  * in the direction of returning spurious 0 without causing disasters.
4749  */
4750 #ifdef __STDC__
4751 static int
4752 begins_with_complex_se (struct rx * rx, struct rexp_node * rexp)
4753 #else
4754 static int
4755 begins_with_complex_se (rx, rexp)
4756      struct rx * rx;
4757      struct rexp_node * rexp;
4758 #endif
4759 {
4760   if (!rexp)
4761     return 0;
4762
4763   switch (rexp->type)
4764     {
4765     case r_cset:
4766     case r_data:
4767       return 0;
4768
4769     case r_side_effect:
4770       return ((long)rexp->params.side_effect >= 0);
4771
4772     case r_alternate:
4773       return
4774         (   begins_with_complex_se (rx, rexp->params.pair.left)
4775          && begins_with_complex_se (rx, rexp->params.pair.right));
4776
4777
4778     case r_concat:
4779       return has_any_se (rx, rexp->params.pair.left);
4780     case r_opt:
4781     case r_star:
4782     case r_2phase_star:
4783       return 0;
4784     }
4785
4786   /* this should never happen */
4787   return 0;
4788 }
4789
4790 \f
4791 /* This destructively removes some of the re_se_tv side effects from
4792  * a rexp tree.  In particular, during parsing re_se_tv was inserted on the
4793  * right half of every | to guarantee that posix path preference could be
4794  * honored.  This function removes some which it can be determined aren't
4795  * needed.
4796  */
4797
4798 #ifdef __STDC__
4799 static void
4800 speed_up_alt (struct rx * rx,
4801               struct rexp_node * rexp,
4802               int unposix)
4803 #else
4804 static void
4805 speed_up_alt (rx, rexp, unposix)
4806      struct rx * rx;
4807      struct rexp_node * rexp;
4808      int unposix;
4809 #endif
4810 {
4811   if (!rexp)
4812     return;
4813
4814   switch (rexp->type)
4815     {
4816     case r_cset:
4817     case r_data:
4818     case r_side_effect:
4819       return;
4820
4821     case r_opt:
4822     case r_star:
4823       speed_up_alt (rx, rexp->params.pair.left, unposix);
4824       return;
4825
4826     case r_2phase_star:
4827     case r_concat:
4828       speed_up_alt (rx, rexp->params.pair.left, unposix);
4829       speed_up_alt (rx, rexp->params.pair.right, unposix);
4830       return;
4831
4832     case r_alternate:
4833       /* the right child is guaranteed to be (concat re_se_tv <subexp>) */
4834
4835       speed_up_alt (rx, rexp->params.pair.left, unposix);
4836       speed_up_alt (rx, rexp->params.pair.right->params.pair.right, unposix);
4837
4838       if (   unposix
4839           || (begins_with_complex_se
4840               (rx, rexp->params.pair.right->params.pair.right))
4841           || !(   has_any_se (rx, rexp->params.pair.right->params.pair.right)
4842                || has_any_se (rx, rexp->params.pair.left)))
4843         {
4844           struct rexp_node * conc = rexp->params.pair.right;
4845           rexp->params.pair.right = conc->params.pair.right;
4846           conc->params.pair.right = 0;
4847           rx_free_rexp (rx, conc);
4848         }
4849     }
4850 }
4851
4852
4853 \f
4854
4855
4856 /* `regex_compile' compiles PATTERN (of length SIZE) according to SYNTAX.
4857    Returns one of error codes defined in `regex.h', or zero for success.
4858
4859    Assumes the `allocated' (and perhaps `buffer') and `translate'
4860    fields are set in BUFP on entry.
4861
4862    If it succeeds, results are put in BUFP (if it returns an error, the
4863    contents of BUFP are undefined):
4864      `buffer' is the compiled pattern;
4865      `syntax' is set to SYNTAX;
4866      `used' is set to the length of the compiled pattern;
4867      `fastmap_accurate' is set to zero;
4868      `re_nsub' is set to the number of groups in PATTERN;
4869      `not_bol' and `not_eol' are set to zero.
4870
4871    The `fastmap' and `newline_anchor' fields are neither
4872    examined nor set.  */
4873
4874
4875
4876 #ifdef __STDC__
4877 RX_DECL reg_errcode_t
4878 rx_compile (__const__ char *pattern, int size,
4879             reg_syntax_t syntax,
4880             struct re_pattern_buffer * rxb)
4881 #else
4882 RX_DECL reg_errcode_t
4883 rx_compile (pattern, size, syntax, rxb)
4884      __const__ char *pattern;
4885      int size;
4886      reg_syntax_t syntax;
4887      struct re_pattern_buffer * rxb;
4888 #endif
4889 {
4890   RX_subset
4891     inverse_translate [CHAR_SET_SIZE * rx_bitset_numb_subsets(CHAR_SET_SIZE)];
4892   char
4893     validate_inv_tr [CHAR_SET_SIZE * rx_bitset_numb_subsets(CHAR_SET_SIZE)];
4894
4895   /* We fetch characters from PATTERN here.  Even though PATTERN is
4896      `char *' (i.e., signed), we declare these variables as unsigned, so
4897      they can be reliably used as array indices.  */
4898   register unsigned char c, c1;
4899
4900   /* A random tempory spot in PATTERN.  */
4901   __const__ char *p1;
4902
4903   /* Keeps track of unclosed groups.  */
4904   compile_stack_type compile_stack;
4905
4906   /* Points to the current (ending) position in the pattern.  */
4907   __const__ char *p = pattern;
4908   __const__ char *pend = pattern + size;
4909
4910   /* How to translate the characters in the pattern.  */
4911   unsigned char *translate = (rxb->translate
4912                               ? rxb->translate
4913                               : rx_id_translation);
4914
4915   /* When parsing is done, this will hold the expression tree. */
4916   struct rexp_node * rexp = 0;
4917
4918   /* In the midst of compilation, this holds onto the regexp
4919    * first parst while rexp goes on to aquire additional constructs.
4920    */
4921   struct rexp_node * orig_rexp = 0;
4922   struct rexp_node * fewer_side_effects = 0;
4923
4924   /* This and top_expression are saved on the compile stack. */
4925   struct rexp_node ** top_expression = &rexp;
4926   struct rexp_node ** last_expression = top_expression;
4927
4928   /* Parameter to `goto append_node' */
4929   struct rexp_node * append;
4930
4931   /* Counts open-groups as they are encountered.  This is the index of the
4932    * innermost group being compiled.
4933    */
4934   regnum_t regnum = 0;
4935
4936   /* Place in the uncompiled pattern (i.e., the {) to
4937    * which to go back if the interval is invalid.
4938    */
4939   __const__ char *beg_interval;
4940
4941   struct re_se_params * params = 0;
4942   int paramc = 0;               /* How many complex side effects so far? */
4943
4944   rx_side_effect side;          /* param to `goto add_side_effect' */
4945
4946   bzero (validate_inv_tr, sizeof (validate_inv_tr));
4947
4948   rxb->rx.instruction_table = rx_id_instruction_table;
4949
4950
4951   /* Initialize the compile stack.  */
4952   compile_stack.stack =  (( compile_stack_elt_t *) malloc ((INIT_COMPILE_STACK_SIZE) * sizeof ( compile_stack_elt_t)));
4953   if (compile_stack.stack == 0)
4954     return REG_ESPACE;
4955
4956   compile_stack.size = INIT_COMPILE_STACK_SIZE;
4957   compile_stack.avail = 0;
4958
4959   /* Initialize the pattern buffer.  */
4960   rxb->rx.cache = &default_cache;
4961   rxb->syntax = syntax;
4962   rxb->fastmap_accurate = 0;
4963   rxb->not_bol = rxb->not_eol = 0;
4964   rxb->least_subs = 0;
4965
4966   /* Always count groups, whether or not rxb->no_sub is set.
4967    * The whole pattern is implicitly group 0, so counting begins
4968    * with 1.
4969    */
4970   rxb->re_nsub = 0;
4971
4972 #if !defined (emacs) && !defined (SYNTAX_TABLE)
4973   /* Initialize the syntax table.  */
4974    init_syntax_once ();
4975 #endif
4976
4977   /* Loop through the uncompiled pattern until we're at the end.  */
4978   while (p != pend)
4979     {
4980       PATFETCH (c);
4981
4982       switch (c)
4983         {
4984         case '^':
4985           {
4986             if (   /* If at start of pattern, it's an operator.  */
4987                    p == pattern + 1
4988                    /* If context independent, it's an operator.  */
4989                 || syntax & RE_CONTEXT_INDEP_ANCHORS
4990                    /* Otherwise, depends on what's come before.  */
4991                 || at_begline_loc_p (pattern, p, syntax))
4992               {
4993                 struct rexp_node * n
4994                   = rx_mk_r_side_effect (&rxb->rx, (rx_side_effect)re_se_hat);
4995                 if (!n)
4996                   return REG_ESPACE;
4997                 append = n;
4998                 goto append_node;
4999               }
5000             else
5001               goto normal_char;
5002           }
5003           break;
5004
5005
5006         case '$':
5007           {
5008             if (   /* If at end of pattern, it's an operator.  */
5009                    p == pend
5010                    /* If context independent, it's an operator.  */
5011                 || syntax & RE_CONTEXT_INDEP_ANCHORS
5012                    /* Otherwise, depends on what's next.  */
5013                 || at_endline_loc_p (p, pend, syntax))
5014               {
5015                 struct rexp_node * n
5016                   = rx_mk_r_side_effect (&rxb->rx, (rx_side_effect)re_se_dollar);
5017                 if (!n)
5018                   return REG_ESPACE;
5019                 append = n;
5020                 goto append_node;
5021               }
5022              else
5023                goto normal_char;
5024            }
5025            break;
5026
5027
5028         case '+':
5029         case '?':
5030           if ((syntax & RE_BK_PLUS_QM)
5031               || (syntax & RE_LIMITED_OPS))
5032             goto normal_char;
5033
5034         handle_plus:
5035         case '*':
5036           /* If there is no previous pattern... */
5037           if (pointless_if_repeated (*last_expression, params))
5038             {
5039               if (syntax & RE_CONTEXT_INVALID_OPS)
5040                 return REG_BADRPT;
5041               else if (!(syntax & RE_CONTEXT_INDEP_OPS))
5042                 goto normal_char;
5043             }
5044
5045           {
5046             /* 1 means zero (many) matches is allowed.  */
5047             char zero_times_ok = 0, many_times_ok = 0;
5048
5049             /* If there is a sequence of repetition chars, collapse it
5050                down to just one (the right one).  We can't combine
5051                interval operators with these because of, e.g., `a{2}*',
5052                which should only match an even number of `a's.  */
5053
5054             for (;;)
5055               {
5056                 zero_times_ok |= c != '+';
5057                 many_times_ok |= c != '?';
5058
5059                 if (p == pend)
5060                   break;
5061
5062                 PATFETCH (c);
5063
5064                 if (c == '*'
5065                     || (!(syntax & RE_BK_PLUS_QM) && (c == '+' || c == '?')))
5066                   ;
5067
5068                 else if (syntax & RE_BK_PLUS_QM  &&  c == '\\')
5069                   {
5070                     if (p == pend) return REG_EESCAPE;
5071
5072                     PATFETCH (c1);
5073                     if (!(c1 == '+' || c1 == '?'))
5074                       {
5075                         PATUNFETCH;
5076                         PATUNFETCH;
5077                         break;
5078                       }
5079
5080                     c = c1;
5081                   }
5082                 else
5083                   {
5084                     PATUNFETCH;
5085                     break;
5086                   }
5087
5088                 /* If we get here, we found another repeat character.  */
5089                }
5090
5091             /* Star, etc. applied to an empty pattern is equivalent
5092                to an empty pattern.  */
5093             if (!last_expression)
5094               break;
5095
5096             /* Now we know whether or not zero matches is allowed
5097              * and also whether or not two or more matches is allowed.
5098              */
5099
5100             {
5101               struct rexp_node * inner_exp = *last_expression;
5102               int need_sync = 0;
5103
5104               if (many_times_ok
5105                   && has_non_idempotent_epsilon_path (&rxb->rx,
5106                                                       inner_exp, params))
5107                 {
5108                   struct rexp_node * pusher
5109                     = rx_mk_r_side_effect (&rxb->rx,
5110                                            (rx_side_effect)re_se_pushpos);
5111                   struct rexp_node * checker
5112                     = rx_mk_r_side_effect (&rxb->rx,
5113                                            (rx_side_effect)re_se_chkpos);
5114                   struct rexp_node * pushback
5115                     = rx_mk_r_side_effect (&rxb->rx,
5116                                            (rx_side_effect)re_se_pushback);
5117                   rx_Bitset cs = rx_cset (&rxb->rx);
5118                   struct rexp_node * lit_t = rx_mk_r_cset (&rxb->rx, cs);
5119                   struct rexp_node * fake_state
5120                     = rx_mk_r_concat (&rxb->rx, pushback, lit_t);
5121                   struct rexp_node * phase2
5122                     = rx_mk_r_concat (&rxb->rx, checker, fake_state);
5123                   struct rexp_node * popper
5124                     = rx_mk_r_side_effect (&rxb->rx,
5125                                            (rx_side_effect)re_se_poppos);
5126                   struct rexp_node * star
5127                     = rx_mk_r_2phase_star (&rxb->rx, inner_exp, phase2);
5128                   struct rexp_node * a
5129                     = rx_mk_r_concat (&rxb->rx, pusher, star);
5130                   struct rexp_node * whole_thing
5131                     = rx_mk_r_concat (&rxb->rx, a, popper);
5132                   if (!(pusher && star && pushback && lit_t && fake_state
5133                         && lit_t && phase2 && checker && popper
5134                         && a && whole_thing))
5135                     return REG_ESPACE;
5136                   RX_bitset_enjoin (cs, 't');
5137                   *last_expression = whole_thing;
5138                 }
5139               else
5140                 {
5141                   struct rexp_node * star =
5142                     (many_times_ok ? rx_mk_r_star : rx_mk_r_opt)
5143                       (&rxb->rx, *last_expression);
5144                   if (!star)
5145                     return REG_ESPACE;
5146                   *last_expression = star;
5147                   need_sync = has_any_se (&rxb->rx, *last_expression);
5148                 }
5149               if (!zero_times_ok)
5150                 {
5151                   struct rexp_node * concat
5152                     = rx_mk_r_concat (&rxb->rx, inner_exp,
5153                                       rx_copy_rexp (&rxb->rx,
5154                                                     *last_expression));
5155                   if (!concat)
5156                     return REG_ESPACE;
5157                   *last_expression = concat;
5158                 }
5159               if (need_sync)
5160                 {
5161                   int sync_se = paramc;
5162                   params = (params
5163                             ? ((struct re_se_params *)
5164                                realloc (params,
5165                                         sizeof (*params) * (1 + paramc)))
5166                             : ((struct re_se_params *)
5167                                malloc (sizeof (*params))));
5168                   if (!params)
5169                     return REG_ESPACE;
5170                   ++paramc;
5171                   params [sync_se].se = re_se_tv;
5172                   side = (rx_side_effect)sync_se;
5173                   goto add_side_effect;
5174                 }
5175             }
5176             /* The old regex.c used to optimize `.*\n'.
5177              * Maybe rx should too?
5178              */
5179           }
5180           break;
5181
5182
5183         case '.':
5184           {
5185             rx_Bitset cs = rx_cset (&rxb->rx);
5186             struct rexp_node * n = rx_mk_r_cset (&rxb->rx, cs);
5187             if (!(cs && n))
5188               return REG_ESPACE;
5189
5190             rx_bitset_universe (rxb->rx.local_cset_size, cs);
5191             if (!(rxb->syntax & RE_DOT_NEWLINE))
5192               RX_bitset_remove (cs, '\n');
5193             if (!(rxb->syntax & RE_DOT_NOT_NULL))
5194               RX_bitset_remove (cs, 0);
5195
5196             append = n;
5197             goto append_node;
5198             break;
5199           }
5200
5201
5202         case '[':
5203           if (p == pend) return REG_EBRACK;
5204           {
5205             boolean had_char_class = false;
5206             rx_Bitset cs = rx_cset (&rxb->rx);
5207             struct rexp_node * node = rx_mk_r_cset (&rxb->rx, cs);
5208             int is_inverted = *p == '^';
5209
5210             if (!(node && cs))
5211               return REG_ESPACE;
5212
5213             /* This branch of the switch is normally exited with
5214              *`goto append_node'
5215              */
5216             append = node;
5217
5218             if (is_inverted)
5219               p++;
5220
5221             /* Remember the first position in the bracket expression.  */
5222             p1 = p;
5223
5224             /* Read in characters and ranges, setting map bits.  */
5225             for (;;)
5226               {
5227                 if (p == pend) return REG_EBRACK;
5228
5229                 PATFETCH (c);
5230
5231                 /* \ might escape characters inside [...] and [^...].  */
5232                 if ((syntax & RE_BACKSLASH_ESCAPE_IN_LISTS) && c == '\\')
5233                   {
5234                     if (p == pend) return REG_EESCAPE;
5235
5236                     PATFETCH (c1);
5237                     {
5238                       rx_Bitset it = inverse_translation (rxb,
5239                                                           validate_inv_tr,
5240                                                           inverse_translate,
5241                                                           translate,
5242                                                           c1);
5243                       rx_bitset_union (rxb->rx.local_cset_size, cs, it);
5244                     }
5245                     continue;
5246                   }
5247
5248                 /* Could be the end of the bracket expression.  If it's
5249                    not (i.e., when the bracket expression is `[]' so
5250                    far), the ']' character bit gets set way below.  */
5251                 if (c == ']' && p != p1 + 1)
5252                   goto finalize_class_and_append;
5253
5254                 /* Look ahead to see if it's a range when the last thing
5255                    was a character class.  */
5256                 if (had_char_class && c == '-' && *p != ']')
5257                   return REG_ERANGE;
5258
5259                 /* Look ahead to see if it's a range when the last thing
5260                    was a character: if this is a hyphen not at the
5261                    beginning or the end of a list, then it's the range
5262                    operator.  */
5263                 if (c == '-'
5264                     && !(p - 2 >= pattern && p[-2] == '[')
5265                     && !(p - 3 >= pattern && p[-3] == '[' && p[-2] == '^')
5266                     && *p != ']')
5267                   {
5268                     reg_errcode_t ret
5269                       = compile_range (rxb, cs, &p, pend, translate, syntax,
5270                                        inverse_translate, validate_inv_tr);
5271                     if (ret != REG_NOERROR) return ret;
5272                   }
5273
5274                 else if (p[0] == '-' && p[1] != ']')
5275                   { /* This handles ranges made up of characters only.  */
5276                     reg_errcode_t ret;
5277
5278                     /* Move past the `-'.  */
5279                     PATFETCH (c1);
5280
5281                     ret = compile_range (rxb, cs, &p, pend, translate, syntax,
5282                                          inverse_translate, validate_inv_tr);
5283                     if (ret != REG_NOERROR) return ret;
5284                   }
5285
5286                 /* See if we're at the beginning of a possible character
5287                    class.  */
5288
5289                 else if ((syntax & RE_CHAR_CLASSES)
5290                          && (c == '[') && (*p == ':'))
5291                   {
5292                     char str[CHAR_CLASS_MAX_LENGTH + 1];
5293
5294                     PATFETCH (c);
5295                     c1 = 0;
5296
5297                     /* If pattern is `[[:'.  */
5298                     if (p == pend) return REG_EBRACK;
5299
5300                     for (;;)
5301                       {
5302                         PATFETCH (c);
5303                         if (c == ':' || c == ']' || p == pend
5304                             || c1 == CHAR_CLASS_MAX_LENGTH)
5305                           break;
5306                         str[c1++] = c;
5307                       }
5308                     str[c1] = '\0';
5309
5310                     /* If isn't a word bracketed by `[:' and:`]':
5311                        undo the ending character, the letters, and leave
5312                        the leading `:' and `[' (but set bits for them).  */
5313                     if (c == ':' && *p == ']')
5314                       {
5315                         int ch;
5316                         boolean is_alnum = !strcmp (str, "alnum");
5317                         boolean is_alpha = !strcmp (str, "alpha");
5318                         boolean is_blank = !strcmp (str, "blank");
5319                         boolean is_cntrl = !strcmp (str, "cntrl");
5320                         boolean is_digit = !strcmp (str, "digit");
5321                         boolean is_graph = !strcmp (str, "graph");
5322                         boolean is_lower = !strcmp (str, "lower");
5323                         boolean is_print = !strcmp (str, "print");
5324                         boolean is_punct = !strcmp (str, "punct");
5325                         boolean is_space = !strcmp (str, "space");
5326                         boolean is_upper = !strcmp (str, "upper");
5327                         boolean is_xdigit = !strcmp (str, "xdigit");
5328
5329                         if (!IS_CHAR_CLASS (str)) return REG_ECTYPE;
5330
5331                         /* Throw away the ] at the end of the character
5332                            class.  */
5333                         PATFETCH (c);
5334
5335                         if (p == pend) return REG_EBRACK;
5336
5337                         for (ch = 0; ch < 1 << CHARBITS; ch++)
5338                           {
5339                             if (   (is_alnum  && isalnum (ch))
5340                                 || (is_alpha  && isalpha (ch))
5341                                 || (is_blank  && isblank (ch))
5342                                 || (is_cntrl  && iscntrl (ch))
5343                                 || (is_digit  && isdigit (ch))
5344                                 || (is_graph  && isgraph (ch))
5345                                 || (is_lower  && islower (ch))
5346                                 || (is_print  && isprint (ch))
5347                                 || (is_punct  && ispunct (ch))
5348                                 || (is_space  && isspace (ch))
5349                                 || (is_upper  && isupper (ch))
5350                                 || (is_xdigit && isxdigit (ch)))
5351                               {
5352                                 rx_Bitset it =
5353                                   inverse_translation (rxb,
5354                                                        validate_inv_tr,
5355                                                        inverse_translate,
5356                                                        translate,
5357                                                        ch);
5358                                 rx_bitset_union (rxb->rx.local_cset_size,
5359                                                  cs, it);
5360                               }
5361                           }
5362                         had_char_class = true;
5363                       }
5364                     else
5365                       {
5366                         c1++;
5367                         while (c1--)
5368                           PATUNFETCH;
5369                         {
5370                           rx_Bitset it =
5371                             inverse_translation (rxb,
5372                                                  validate_inv_tr,
5373                                                  inverse_translate,
5374                                                  translate,
5375                                                  '[');
5376                           rx_bitset_union (rxb->rx.local_cset_size,
5377                                            cs, it);
5378                         }
5379                         {
5380                           rx_Bitset it =
5381                             inverse_translation (rxb,
5382                                                  validate_inv_tr,
5383                                                  inverse_translate,
5384                                                  translate,
5385                                                  ':');
5386                           rx_bitset_union (rxb->rx.local_cset_size,
5387                                            cs, it);
5388                         }
5389                         had_char_class = false;
5390                       }
5391                   }
5392                 else
5393                   {
5394                     had_char_class = false;
5395                     {
5396                       rx_Bitset it = inverse_translation (rxb,
5397                                                           validate_inv_tr,
5398                                                           inverse_translate,
5399                                                           translate,
5400                                                           c);
5401                       rx_bitset_union (rxb->rx.local_cset_size, cs, it);
5402                     }
5403                   }
5404               }
5405
5406           finalize_class_and_append:
5407             if (is_inverted)
5408               {
5409                 rx_bitset_complement (rxb->rx.local_cset_size, cs);
5410                 if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
5411                   RX_bitset_remove (cs, '\n');
5412               }
5413             goto append_node;
5414           }
5415           break;
5416
5417
5418         case '(':
5419           if (syntax & RE_NO_BK_PARENS)
5420             goto handle_open;
5421           else
5422             goto normal_char;
5423
5424
5425         case ')':
5426           if (syntax & RE_NO_BK_PARENS)
5427             goto handle_close;
5428           else
5429             goto normal_char;
5430
5431
5432         case '\n':
5433           if (syntax & RE_NEWLINE_ALT)
5434             goto handle_alt;
5435           else
5436             goto normal_char;
5437
5438
5439         case '|':
5440           if (syntax & RE_NO_BK_VBAR)
5441             goto handle_alt;
5442           else
5443             goto normal_char;
5444
5445
5446         case '{':
5447           if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
5448             goto handle_interval;
5449           else
5450             goto normal_char;
5451
5452
5453         case '\\':
5454           if (p == pend) return REG_EESCAPE;
5455
5456           /* Do not translate the character after the \, so that we can
5457              distinguish, e.g., \B from \b, even if we normally would
5458              translate, e.g., B to b.  */
5459           PATFETCH_RAW (c);
5460
5461           switch (c)
5462             {
5463             case '(':
5464               if (syntax & RE_NO_BK_PARENS)
5465                 goto normal_backslash;
5466
5467             handle_open:
5468               rxb->re_nsub++;
5469               regnum++;
5470               if (COMPILE_STACK_FULL)
5471                 {
5472                   ((compile_stack.stack) =
5473                    (compile_stack_elt_t *) realloc (compile_stack.stack, ( compile_stack.size << 1) * sizeof (
5474                                                                                                               compile_stack_elt_t)));
5475                   if (compile_stack.stack == 0) return REG_ESPACE;
5476
5477                   compile_stack.size <<= 1;
5478                 }
5479
5480               if (*last_expression)
5481                 {
5482                   struct rexp_node * concat
5483                     = rx_mk_r_concat (&rxb->rx, *last_expression, 0);
5484                   if (!concat)
5485                     return REG_ESPACE;
5486                   *last_expression = concat;
5487                   last_expression = &concat->params.pair.right;
5488                 }
5489
5490               /*
5491                * These are the values to restore when we hit end of this
5492                * group.
5493                */
5494               COMPILE_STACK_TOP.top_expression = top_expression;
5495               COMPILE_STACK_TOP.last_expression = last_expression;
5496               COMPILE_STACK_TOP.regnum = regnum;
5497
5498               compile_stack.avail++;
5499
5500               top_expression = last_expression;
5501               break;
5502
5503
5504             case ')':
5505               if (syntax & RE_NO_BK_PARENS) goto normal_backslash;
5506
5507             handle_close:
5508               /* See similar code for backslashed left paren above.  */
5509               if (COMPILE_STACK_EMPTY)
5510                 if (syntax & RE_UNMATCHED_RIGHT_PAREN_ORD)
5511                   goto normal_char;
5512                 else
5513                   return REG_ERPAREN;
5514
5515               /* Since we just checked for an empty stack above, this
5516                  ``can't happen''.  */
5517
5518               {
5519                 /* We don't just want to restore into `regnum', because
5520                    later groups should continue to be numbered higher,
5521                    as in `(ab)c(de)' -- the second group is #2.  */
5522                 regnum_t this_group_regnum;
5523                 struct rexp_node ** inner = top_expression;
5524
5525                 compile_stack.avail--;
5526                 top_expression = COMPILE_STACK_TOP.top_expression;
5527                 last_expression = COMPILE_STACK_TOP.last_expression;
5528                 this_group_regnum = COMPILE_STACK_TOP.regnum;
5529                 {
5530                   int left_se = paramc;
5531                   int right_se = paramc + 1;
5532
5533                   params = (params
5534                             ? ((struct re_se_params *)
5535                                realloc (params,
5536                                         (paramc + 2) * sizeof (params[0])))
5537                             : ((struct re_se_params *)
5538                                malloc (2 * sizeof (params[0]))));
5539                   if (!params)
5540                     return REG_ESPACE;
5541                   paramc += 2;
5542
5543                   params[left_se].se = re_se_lparen;
5544                   params[left_se].op1 = this_group_regnum;
5545                   params[right_se].se = re_se_rparen;
5546                   params[right_se].op1 = this_group_regnum;
5547                   {
5548                     struct rexp_node * left
5549                       = rx_mk_r_side_effect (&rxb->rx,
5550                                              (rx_side_effect)left_se);
5551                     struct rexp_node * right
5552                       = rx_mk_r_side_effect (&rxb->rx,
5553                                              (rx_side_effect)right_se);
5554                     struct rexp_node * c1
5555                       = (*inner
5556                          ? rx_mk_r_concat (&rxb->rx, left, *inner) : left);
5557                     struct rexp_node * c2
5558                       = rx_mk_r_concat (&rxb->rx, c1, right);
5559                     if (!(left && right && c1 && c2))
5560                       return REG_ESPACE;
5561                     *inner = c2;
5562                   }
5563                 }
5564                 break;
5565               }
5566
5567             case '|':                                   /* `\|'.  */
5568               if ((syntax & RE_LIMITED_OPS) || (syntax & RE_NO_BK_VBAR))
5569                 goto normal_backslash;
5570             handle_alt:
5571               if (syntax & RE_LIMITED_OPS)
5572                 goto normal_char;
5573
5574               {
5575                 struct rexp_node * alt
5576                   = rx_mk_r_alternate (&rxb->rx, *top_expression, 0);
5577                 if (!alt)
5578                   return REG_ESPACE;
5579                 *top_expression = alt;
5580                 last_expression = &alt->params.pair.right;
5581                 {
5582                   int sync_se = paramc;
5583
5584                   params = (params
5585                             ? ((struct re_se_params *)
5586                                realloc (params,
5587                                         (paramc + 1) * sizeof (params[0])))
5588                             : ((struct re_se_params *)
5589                                malloc (sizeof (params[0]))));
5590                   if (!params)
5591                     return REG_ESPACE;
5592                   ++paramc;
5593
5594                   params[sync_se].se = re_se_tv;
5595                   {
5596                     struct rexp_node * sync
5597                       = rx_mk_r_side_effect (&rxb->rx,
5598                                              (rx_side_effect)sync_se);
5599                     struct rexp_node * conc
5600                       = rx_mk_r_concat (&rxb->rx, sync, 0);
5601
5602                     if (!sync || !conc)
5603                       return REG_ESPACE;
5604
5605                     *last_expression = conc;
5606                     last_expression = &conc->params.pair.right;
5607                   }
5608                 }
5609               }
5610               break;
5611
5612
5613             case '{':
5614               /* If \{ is a literal.  */
5615               if (!(syntax & RE_INTERVALS)
5616                      /* If we're at `\{' and it's not the open-interval
5617                         operator.  */
5618                   || ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
5619                   || (p - 2 == pattern  &&  p == pend))
5620                 goto normal_backslash;
5621
5622             handle_interval:
5623               {
5624                 /* If got here, then the syntax allows intervals.  */
5625
5626                 /* At least (most) this many matches must be made.  */
5627                 int lower_bound = -1, upper_bound = -1;
5628
5629                 beg_interval = p - 1;
5630
5631                 if (p == pend)
5632                   {
5633                     if (syntax & RE_NO_BK_BRACES)
5634                       goto unfetch_interval;
5635                     else
5636                       return REG_EBRACE;
5637                   }
5638
5639                 GET_UNSIGNED_NUMBER (lower_bound);
5640
5641                 if (c == ',')
5642                   {
5643                     GET_UNSIGNED_NUMBER (upper_bound);
5644                     if (upper_bound < 0) upper_bound = RE_DUP_MAX;
5645                   }
5646                 else
5647                   /* Interval such as `{1}' => match exactly once. */
5648                   upper_bound = lower_bound;
5649
5650                 if (lower_bound < 0 || upper_bound > RE_DUP_MAX
5651                     || lower_bound > upper_bound)
5652                   {
5653                     if (syntax & RE_NO_BK_BRACES)
5654                       goto unfetch_interval;
5655                     else
5656                       return REG_BADBR;
5657                   }
5658
5659                 if (!(syntax & RE_NO_BK_BRACES))
5660                   {
5661                     if (c != '\\') return REG_EBRACE;
5662                     PATFETCH (c);
5663                   }
5664
5665                 if (c != '}')
5666                   {
5667                     if (syntax & RE_NO_BK_BRACES)
5668                       goto unfetch_interval;
5669                     else
5670                       return REG_BADBR;
5671                   }
5672
5673                 /* We just parsed a valid interval.  */
5674
5675                 /* If it's invalid to have no preceding re.  */
5676                 if (pointless_if_repeated (*last_expression, params))
5677                   {
5678                     if (syntax & RE_CONTEXT_INVALID_OPS)
5679                       return REG_BADRPT;
5680                     else if (!(syntax & RE_CONTEXT_INDEP_OPS))
5681                       goto unfetch_interval;
5682                     /* was: else laststart = b; */
5683                   }
5684
5685                 /* If the upper bound is zero, don't want to iterate
5686                  * at all.
5687                  */
5688                  if (upper_bound == 0)
5689                    {
5690                      if (*last_expression)
5691                        {
5692                          rx_free_rexp (&rxb->rx, *last_expression);
5693                          *last_expression = 0;
5694                        }
5695                    }
5696                 else
5697                   /* Otherwise, we have a nontrivial interval. */
5698                   {
5699                     int iter_se = paramc;
5700                     int end_se = paramc + 1;
5701                     params = (params
5702                               ? ((struct re_se_params *)
5703                                  realloc (params,
5704                                           sizeof (*params) * (2 + paramc)))
5705                               : ((struct re_se_params *)
5706                                  malloc (2 * sizeof (*params))));
5707                     if (!params)
5708                       return REG_ESPACE;
5709                     paramc += 2;
5710                     params [iter_se].se = re_se_iter;
5711                     params [iter_se].op1 = lower_bound;
5712                     params[iter_se].op2 = upper_bound;
5713
5714                     params[end_se].se = re_se_end_iter;
5715                     params[end_se].op1 = lower_bound;
5716                     params[end_se].op2 = upper_bound;
5717                     {
5718                       struct rexp_node * push0
5719                         = rx_mk_r_side_effect (&rxb->rx,
5720                                                (rx_side_effect)re_se_push0);
5721                       struct rexp_node * start_one_iter
5722                         = rx_mk_r_side_effect (&rxb->rx,
5723                                                (rx_side_effect)iter_se);
5724                       struct rexp_node * phase1
5725                         = rx_mk_r_concat (&rxb->rx, start_one_iter,
5726                                           *last_expression);
5727                       struct rexp_node * pushback
5728                         = rx_mk_r_side_effect (&rxb->rx,
5729                                                (rx_side_effect)re_se_pushback);
5730                       rx_Bitset cs = rx_cset (&rxb->rx);
5731                       struct rexp_node * lit_t
5732                         = rx_mk_r_cset (&rxb->rx, cs);
5733                       struct rexp_node * phase2
5734                         = rx_mk_r_concat (&rxb->rx, pushback, lit_t);
5735                       struct rexp_node * loop
5736                         = rx_mk_r_2phase_star (&rxb->rx, phase1, phase2);
5737                       struct rexp_node * push_n_loop
5738                         = rx_mk_r_concat (&rxb->rx, push0, loop);
5739                       struct rexp_node * final_test
5740                         = rx_mk_r_side_effect (&rxb->rx,
5741                                                (rx_side_effect)end_se);
5742                       struct rexp_node * full_exp
5743                         = rx_mk_r_concat (&rxb->rx, push_n_loop, final_test);
5744
5745                       if (!(push0 && start_one_iter && phase1
5746                             && pushback && lit_t && phase2
5747                             && loop && push_n_loop && final_test && full_exp))
5748                         return REG_ESPACE;
5749
5750                       RX_bitset_enjoin(cs, 't');
5751
5752                       *last_expression = full_exp;
5753                     }
5754                   }
5755                 beg_interval = 0;
5756               }
5757               break;
5758
5759             unfetch_interval:
5760               /* If an invalid interval, match the characters as literals.  */
5761                p = beg_interval;
5762                beg_interval = 0;
5763
5764                /* normal_char and normal_backslash need `c'.  */
5765                PATFETCH (c);
5766
5767                if (!(syntax & RE_NO_BK_BRACES))
5768                  {
5769                    if (p > pattern  &&  p[-1] == '\\')
5770                      goto normal_backslash;
5771                  }
5772                goto normal_char;
5773
5774 #ifdef emacs
5775             /* There is no way to specify the before_dot and after_dot
5776                operators.  rms says this is ok.  --karl  */
5777             case '=':
5778               side = (rx_side_effect)rx_se_at_dot;
5779               goto add_side_effect;
5780               break;
5781
5782             case 's':
5783             case 'S':
5784               {
5785                 rx_Bitset cs = rx_cset (&rxb->rx);
5786                 struct rexp_node * set = rx_mk_r_cset (&rxb->rx, cs);
5787                 if (!(cs && set))
5788                   return REG_ESPACE;
5789                 if (c == 'S')
5790                   rx_bitset_universe (rxb->rx.local_cset_size, cs);
5791
5792                 PATFETCH (c);
5793                 {
5794                   int x;
5795                   enum syntaxcode code = syntax_spec_code [c];
5796                   for (x = 0; x < 256; ++x)
5797                     {
5798
5799                       if (SYNTAX (x) == code)
5800                         {
5801                           rx_Bitset it =
5802                             inverse_translation (rxb, validate_inv_tr,
5803                                                  inverse_translate,
5804                                                  translate, x);
5805                           rx_bitset_xor (rxb->rx.local_cset_size, cs, it);
5806                         }
5807                     }
5808                 }
5809                 append = set;
5810                 goto append_node;
5811               }
5812               break;
5813 #endif /* emacs */
5814
5815
5816             case 'w':
5817             case 'W':
5818               {
5819                 rx_Bitset cs = rx_cset (&rxb->rx);
5820                 struct rexp_node * n = (cs ? rx_mk_r_cset (&rxb->rx, cs) : 0);
5821                 if (!(cs && n))
5822                   return REG_ESPACE;
5823                 if (c == 'W')
5824                   rx_bitset_universe (rxb->rx.local_cset_size ,cs);
5825                 {
5826                   int x;
5827                   for (x = rxb->rx.local_cset_size - 1; x > 0; --x)
5828                     if (SYNTAX(x) & Sword)
5829                       RX_bitset_toggle (cs, x);
5830                 }
5831                 append = n;
5832                 goto append_node;
5833               }
5834               break;
5835
5836 /* With a little extra work, some of these side effects could be optimized
5837  * away (basicly by looking at what we already know about the surrounding
5838  * chars).
5839  */
5840             case '<':
5841               side = (rx_side_effect)re_se_wordbeg;
5842               goto add_side_effect;
5843               break;
5844
5845             case '>':
5846               side = (rx_side_effect)re_se_wordend;
5847               goto add_side_effect;
5848               break;
5849
5850             case 'b':
5851               side = (rx_side_effect)re_se_wordbound;
5852               goto add_side_effect;
5853               break;
5854
5855             case 'B':
5856               side = (rx_side_effect)re_se_notwordbound;
5857               goto add_side_effect;
5858               break;
5859
5860             case '`':
5861               side = (rx_side_effect)re_se_begbuf;
5862               goto add_side_effect;
5863               break;
5864
5865             case '\'':
5866               side = (rx_side_effect)re_se_endbuf;
5867               goto add_side_effect;
5868               break;
5869
5870             add_side_effect:
5871               {
5872                 struct rexp_node * se
5873                   = rx_mk_r_side_effect (&rxb->rx, side);
5874                 if (!se)
5875                   return REG_ESPACE;
5876                 append = se;
5877                 goto append_node;
5878               }
5879               break;
5880
5881             case '1': case '2': case '3': case '4': case '5':
5882             case '6': case '7': case '8': case '9':
5883               if (syntax & RE_NO_BK_REFS)
5884                 goto normal_char;
5885
5886               c1 = c - '0';
5887
5888               if (c1 > regnum)
5889                 return REG_ESUBREG;
5890
5891               /* Can't back reference to a subexpression if inside of it.  */
5892               if (group_in_compile_stack (compile_stack, c1))
5893                 return REG_ESUBREG;
5894
5895               {
5896                 int backref_se = paramc;
5897                 params = (params
5898                           ? ((struct re_se_params *)
5899                              realloc (params,
5900                                       sizeof (*params) * (1 + paramc)))
5901                           : ((struct re_se_params *)
5902                              malloc (sizeof (*params))));
5903                 if (!params)
5904                   return REG_ESPACE;
5905                 ++paramc;
5906                 params[backref_se].se = re_se_backref;
5907                 params[backref_se].op1 = c1;
5908                 side = (rx_side_effect)backref_se;
5909                 goto add_side_effect;
5910               }
5911               break;
5912
5913             case '+':
5914             case '?':
5915               if (syntax & RE_BK_PLUS_QM)
5916                 goto handle_plus;
5917               else
5918                 goto normal_backslash;
5919
5920             default:
5921             normal_backslash:
5922               /* You might think it would be useful for \ to mean
5923                  not to translate; but if we don't translate it
5924                  it will never match anything.  */
5925               c = TRANSLATE (c);
5926               goto normal_char;
5927             }
5928           break;
5929
5930
5931         default:
5932         /* Expects the character in `c'.  */
5933         normal_char:
5934             {
5935               rx_Bitset cs = rx_cset(&rxb->rx);
5936               struct rexp_node * match = rx_mk_r_cset (&rxb->rx, cs);
5937               rx_Bitset it;
5938               if (!(cs && match))
5939                 return REG_ESPACE;
5940               it = inverse_translation (rxb, validate_inv_tr,
5941                                         inverse_translate, translate, c);
5942               rx_bitset_union (CHAR_SET_SIZE, cs, it);
5943               append = match;
5944
5945             append_node:
5946               /* This genericly appends the rexp APPEND to *LAST_EXPRESSION
5947                * and then parses the next character normally.
5948                */
5949               if (*last_expression)
5950                 {
5951                   struct rexp_node * concat
5952                     = rx_mk_r_concat (&rxb->rx, *last_expression, append);
5953                   if (!concat)
5954                     return REG_ESPACE;
5955                   *last_expression = concat;
5956                   last_expression = &concat->params.pair.right;
5957                 }
5958               else
5959                 *last_expression = append;
5960             }
5961         } /* switch (c) */
5962     } /* while p != pend */
5963
5964
5965   {
5966     int win_se = paramc;
5967     params = (params
5968               ? ((struct re_se_params *)
5969                  realloc (params,
5970                           sizeof (*params) * (1 + paramc)))
5971               : ((struct re_se_params *)
5972                  malloc (sizeof (*params))));
5973     if (!params)
5974       return REG_ESPACE;
5975     ++paramc;
5976     params[win_se].se = re_se_win;
5977     {
5978       struct rexp_node * se
5979         = rx_mk_r_side_effect (&rxb->rx, (rx_side_effect)win_se);
5980       struct rexp_node * concat
5981         = rx_mk_r_concat (&rxb->rx, rexp, se);
5982       if (!(se && concat))
5983         return REG_ESPACE;
5984       rexp = concat;
5985     }
5986   }
5987
5988
5989   /* Through the pattern now.  */
5990
5991   if (!COMPILE_STACK_EMPTY)
5992     return REG_EPAREN;
5993
5994       free (compile_stack.stack);
5995
5996   orig_rexp = rexp;
5997 #ifdef RX_DEBUG
5998   if (rx_debug_compile)
5999     {
6000       dbug_rxb = rxb;
6001       fputs ("\n\nCompiling ", stdout);
6002       fwrite (pattern, 1, size, stdout);
6003       fputs (":\n", stdout);
6004       rxb->se_params = params;
6005       print_rexp (&rxb->rx, orig_rexp, 2, re_seprint, stdout);
6006     }
6007 #endif
6008   {
6009     rx_Bitset cs = rx_cset(&rxb->rx);
6010     rx_Bitset cs2 = rx_cset(&rxb->rx);
6011     char * se_map = (char *) alloca (paramc);
6012     struct rexp_node * new_rexp = 0;
6013
6014
6015     bzero (se_map, paramc);
6016     find_backrefs (se_map, rexp, params);
6017     fewer_side_effects =
6018       remove_unecessary_side_effects (&rxb->rx, se_map,
6019                                       rx_copy_rexp (&rxb->rx, rexp), params);
6020
6021     speed_up_alt (&rxb->rx, rexp, 0);
6022     speed_up_alt (&rxb->rx, fewer_side_effects, 1);
6023
6024     {
6025       char * syntax_parens = rxb->syntax_parens;
6026       if (syntax_parens == (char *)0x1)
6027         rexp = remove_unecessary_side_effects
6028           (&rxb->rx, se_map, rexp, params);
6029       else if (syntax_parens)
6030         {
6031           int x;
6032           for (x = 0; x < paramc; ++x)
6033             if ((   (params[x].se == re_se_lparen)
6034                  || (params[x].se == re_se_rparen))
6035                 && (!syntax_parens [params[x].op1]))
6036               se_map [x] = 1;
6037           rexp = remove_unecessary_side_effects
6038             (&rxb->rx, se_map, rexp, params);
6039         }
6040     }
6041
6042     /* At least one more optimization would be nice to have here but i ran out
6043      * of time.  The idea would be to delay side effects.
6044      * For examle, `(abc)' is the same thing as `abc()' except that the
6045      * left paren is offset by 3 (which we know at compile time).
6046      * (In this comment, write that second pattern `abc(:3:)'
6047      * where `(:3:' is a syntactic unit.)
6048      *
6049      * Trickier:  `(abc|defg)'  is the same as `(abc(:3:|defg(:4:))'
6050      * (The paren nesting may be hard to follow -- that's an alternation
6051      *  of `abc(:3:' and `defg(:4:' inside (purely syntactic) parens
6052      *  followed by the closing paren from the original expression.)
6053      *
6054      * Neither the expression tree representation nor the the nfa make
6055      * this very easy to write. :(
6056      */
6057
6058   /* What we compile is different than what the parser returns.
6059    * Suppose the parser returns expression R.
6060    * Let R' be R with unnecessary register assignments removed
6061    * (see REMOVE_UNECESSARY_SIDE_EFFECTS, above).
6062    *
6063    * What we will compile is the expression:
6064    *
6065    *    m{try}R{win}\|s{try}R'{win}
6066    *
6067    * {try} and {win} denote side effect epsilons (see EXPLORE_FUTURE).
6068    *
6069    * When trying a match, we insert an `m' at the beginning of the
6070    * string if the user wants registers to be filled, `s' if not.
6071    */
6072     new_rexp =
6073       rx_mk_r_alternate
6074         (&rxb->rx,
6075          rx_mk_r_concat (&rxb->rx, rx_mk_r_cset (&rxb->rx, cs2), rexp),
6076          rx_mk_r_concat (&rxb->rx,
6077                          rx_mk_r_cset (&rxb->rx, cs), fewer_side_effects));
6078
6079     if (!(new_rexp && cs && cs2))
6080       return REG_ESPACE;
6081     RX_bitset_enjoin (cs2, '\0'); /* prefixed to the rexp used for matching. */
6082     RX_bitset_enjoin (cs, '\1'); /* prefixed to the rexp used for searching. */
6083     rexp = new_rexp;
6084   }
6085
6086 #ifdef RX_DEBUG
6087   if (rx_debug_compile)
6088     {
6089       fputs ("\n...which is compiled as:\n", stdout);
6090       print_rexp (&rxb->rx, rexp, 2, re_seprint, stdout);
6091     }
6092 #endif
6093   {
6094     struct rx_nfa_state *start = 0;
6095     struct rx_nfa_state *end = 0;
6096
6097     if (!rx_build_nfa (&rxb->rx, rexp, &start, &end))
6098       return REG_ESPACE;        /*  */
6099     else
6100       {
6101         void * mem = (void *)rxb->buffer;
6102         unsigned long size = rxb->allocated;
6103         int start_id;
6104         char * perm_mem;
6105         int iterator_size = paramc * sizeof (params[0]);
6106
6107         end->is_final = 1;
6108         start->is_start = 1;
6109         rx_name_nfa_states (&rxb->rx);
6110         start_id = start->id;
6111 #ifdef RX_DEBUG
6112         if (rx_debug_compile)
6113           {
6114             fputs ("...giving the NFA: \n", stdout);
6115             dbug_rxb = rxb;
6116             print_nfa (&rxb->rx, rxb->rx.nfa_states, re_seprint, stdout);
6117           }
6118 #endif
6119         if (!rx_eclose_nfa (&rxb->rx))
6120           return REG_ESPACE;
6121         else
6122           {
6123             rx_delete_epsilon_transitions (&rxb->rx);
6124
6125             /* For compatability reasons, we need to shove the
6126              * compiled nfa into one chunk of malloced memory.
6127              */
6128             rxb->rx.reserved = (   sizeof (params[0]) * paramc
6129                                 +  rx_sizeof_bitset (rxb->rx.local_cset_size));
6130 #ifdef RX_DEBUG
6131             if (rx_debug_compile)
6132               {
6133                 dbug_rxb = rxb;
6134                 fputs ("...which cooks down (uncompactified) to: \n", stdout);
6135                 print_nfa (&rxb->rx, rxb->rx.nfa_states, re_seprint, stdout);
6136               }
6137 #endif
6138             if (!rx_compactify_nfa (&rxb->rx, &mem, &size))
6139               return REG_ESPACE;
6140             rxb->buffer = mem;
6141             rxb->allocated = size;
6142             rxb->rx.buffer = mem;
6143             rxb->rx.allocated = size;
6144             perm_mem = ((char *)rxb->rx.buffer
6145                         + rxb->rx.allocated - rxb->rx.reserved);
6146             rxb->se_params = ((struct re_se_params *)perm_mem);
6147             bcopy (params, rxb->se_params, iterator_size);
6148             perm_mem += iterator_size;
6149             rxb->fastset = (rx_Bitset) perm_mem;
6150             rxb->start = rx_id_to_nfa_state (&rxb->rx, start_id);
6151           }
6152         rx_bitset_null (rxb->rx.local_cset_size, rxb->fastset);
6153         rxb->can_match_empty = compute_fastset (rxb, orig_rexp);
6154         rxb->match_regs_on_stack =
6155           registers_on_stack (rxb, orig_rexp, 0, params);
6156         rxb->search_regs_on_stack =
6157           registers_on_stack (rxb, fewer_side_effects, 0, params);
6158         if (rxb->can_match_empty)
6159           rx_bitset_universe (rxb->rx.local_cset_size, rxb->fastset);
6160         rxb->is_anchored = is_anchored (orig_rexp, (rx_side_effect) re_se_hat);
6161         rxb->begbuf_only = is_anchored (orig_rexp,
6162                                         (rx_side_effect) re_se_begbuf);
6163       }
6164     rx_free_rexp (&rxb->rx, rexp);
6165     if (params)
6166       free (params);
6167 #ifdef RX_DEBUG
6168     if (rx_debug_compile)
6169       {
6170         dbug_rxb = rxb;
6171         fputs ("...which cooks down to: \n", stdout);
6172         print_nfa (&rxb->rx, rxb->rx.nfa_states, re_seprint, stdout);
6173       }
6174 #endif
6175   }
6176   return REG_NOERROR;
6177 }
6178
6179 \f
6180
6181 /* This table gives an error message for each of the error codes listed
6182    in regex.h.  Obviously the order here has to be same as there.  */
6183
6184 __const__ char * rx_error_msg[] =
6185 { 0,                                            /* REG_NOERROR */
6186     "No match",                                 /* REG_NOMATCH */
6187     "Invalid regular expression",               /* REG_BADPAT */
6188     "Invalid collation character",              /* REG_ECOLLATE */
6189     "Invalid character class name",             /* REG_ECTYPE */
6190     "Trailing backslash",                       /* REG_EESCAPE */
6191     "Invalid back reference",                   /* REG_ESUBREG */
6192     "Unmatched [ or [^",                        /* REG_EBRACK */
6193     "Unmatched ( or \\(",                       /* REG_EPAREN */
6194     "Unmatched \\{",                            /* REG_EBRACE */
6195     "Invalid content of \\{\\}",                /* REG_BADBR */
6196     "Invalid range end",                        /* REG_ERANGE */
6197     "Memory exhausted",                         /* REG_ESPACE */
6198     "Invalid preceding regular expression",     /* REG_BADRPT */
6199     "Premature end of regular expression",      /* REG_EEND */
6200     "Regular expression too big",               /* REG_ESIZE */
6201     "Unmatched ) or \\)",                       /* REG_ERPAREN */
6202 };
6203
6204 \f
6205
6206
6207 char rx_slowmap [256] =
6208 {
6209   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6210   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6211   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6212   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6213   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6214   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6215   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6216   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6217   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6218   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6219   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6220   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6221   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6222   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6223   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6224   1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
6225 };
6226
6227 #ifdef __STDC__
6228 RX_DECL void
6229 rx_blow_up_fastmap (struct re_pattern_buffer * rxb)
6230 #else
6231 RX_DECL void
6232 rx_blow_up_fastmap (rxb)
6233      struct re_pattern_buffer * rxb;
6234 #endif
6235 {
6236   int x;
6237   for (x = 0; x < 256; ++x)     /* &&&& 3.6 % */
6238     rxb->fastmap [x] = !!RX_bitset_member (rxb->fastset, x);
6239   rxb->fastmap_accurate = 1;
6240 }
6241
6242
6243 \f
6244
6245 #if !defined(REGEX_MALLOC) && !defined(__GNUC__)
6246 #define RE_SEARCH_2_FN  inner_re_search_2
6247 #define RE_S2_QUAL static
6248 #else
6249 #define RE_SEARCH_2_FN  re_search_2
6250 #define RE_S2_QUAL
6251 #endif
6252
6253 struct re_search_2_closure
6254 {
6255   __const__ unsigned char * string1;
6256   int size1;
6257   __const__ unsigned char * string2;
6258   int size2;
6259 };
6260
6261
6262 static __inline__ enum rx_get_burst_return
6263 re_search_2_get_burst (pos, vclosure, stop)
6264      struct rx_string_position * pos;
6265      void * vclosure;
6266      int stop;
6267 {
6268   struct re_search_2_closure * closure;
6269   closure = (struct re_search_2_closure *)vclosure;
6270   if (!closure->string2)
6271     {
6272       int inset;
6273
6274       inset = pos->pos - pos->string;
6275       if ((inset < -1) || (inset > closure->size1))
6276         return rx_get_burst_no_more;
6277       else
6278         {
6279           pos->pos = (__const__ unsigned char *) closure->string1 + inset;
6280           pos->string = (__const__ unsigned char *) closure->string1;
6281           pos->size = closure->size1;
6282           pos->end = ((__const__ unsigned char *)
6283                       MIN(closure->string1 + closure->size1,
6284                           closure->string1 + stop));
6285           pos->offset = 0;
6286           return ((pos->pos < pos->end)
6287                   ? rx_get_burst_ok
6288                   :  rx_get_burst_no_more);
6289         }
6290     }
6291   else if (!closure->string1)
6292     {
6293       int inset;
6294
6295       inset = pos->pos - pos->string;
6296       pos->pos = (__const__ unsigned char *) closure->string2 + inset;
6297       pos->string = (__const__ unsigned char *) closure->string2;
6298       pos->size = closure->size2;
6299       pos->end = ((__const__ unsigned char *)
6300                   MIN(closure->string2 + closure->size2,
6301                       closure->string2 + stop));
6302       pos->offset = 0;
6303       return ((pos->pos < pos->end)
6304               ? rx_get_burst_ok
6305               :  rx_get_burst_no_more);
6306     }
6307   else
6308     {
6309       int inset;
6310
6311       inset = pos->pos - pos->string + pos->offset;
6312       if (inset < closure->size1)
6313         {
6314           pos->pos = (__const__ unsigned char *) closure->string1 + inset;
6315           pos->string = (__const__ unsigned char *) closure->string1;
6316           pos->size = closure->size1;
6317           pos->end = ((__const__ unsigned char *)
6318                       MIN(closure->string1 + closure->size1,
6319                           closure->string1 + stop));
6320           pos->offset = 0;
6321           return rx_get_burst_ok;
6322         }
6323       else
6324         {
6325           pos->pos = ((__const__ unsigned char *)
6326                       closure->string2 + inset - closure->size1);
6327           pos->string = (__const__ unsigned char *) closure->string2;
6328           pos->size = closure->size2;
6329           pos->end = ((__const__ unsigned char *)
6330                       MIN(closure->string2 + closure->size2,
6331                           closure->string2 + stop - closure->size1));
6332           pos->offset = closure->size1;
6333           return ((pos->pos < pos->end)
6334                   ? rx_get_burst_ok
6335                   :  rx_get_burst_no_more);
6336         }
6337     }
6338 }
6339
6340
6341 static __inline__ enum rx_back_check_return
6342 re_search_2_back_check (pos, lparen, rparen, translate, vclosure, stop)
6343      struct rx_string_position * pos;
6344      int lparen;
6345      int rparen;
6346      unsigned char * translate;
6347      void * vclosure;
6348      int stop;
6349 {
6350   struct rx_string_position there;
6351   struct rx_string_position past;
6352
6353   there = *pos;
6354   there.pos = there.string + lparen - there.offset;
6355   re_search_2_get_burst (&there, vclosure, stop);
6356
6357   past = *pos;
6358   past.pos = past.string + rparen - there.offset;
6359   re_search_2_get_burst (&past, vclosure, stop);
6360
6361   ++pos->pos;
6362   re_search_2_get_burst (pos, vclosure, stop);
6363
6364   while (   (there.pos != past.pos)
6365          && (pos->pos != pos->end))
6366     if (TRANSLATE(*there.pos) != TRANSLATE(*pos->pos))
6367       return rx_back_check_fail;
6368     else
6369       {
6370         ++there.pos;
6371         ++pos->pos;
6372         if (there.pos == there.end)
6373           re_search_2_get_burst (&there, vclosure, stop);
6374         if (pos->pos == pos->end)
6375           re_search_2_get_burst (pos, vclosure, stop);
6376       }
6377
6378   if (there.pos != past.pos)
6379     return rx_back_check_fail;
6380   --pos->pos;
6381   re_search_2_get_burst (pos, vclosure, stop);
6382   return rx_back_check_pass;
6383 }
6384
6385 static __inline__ int
6386 re_search_2_fetch_char (pos, offset, app_closure, stop)
6387      struct rx_string_position * pos;
6388      int offset;
6389      void * app_closure;
6390      int stop;
6391 {
6392   struct re_search_2_closure * closure;
6393   closure = (struct re_search_2_closure *)app_closure;
6394   if (offset == 0)
6395     {
6396       if (pos->pos >= pos->string)
6397         return *pos->pos;
6398       else
6399         {
6400           if (   (pos->string == closure->string2)
6401               && (closure->string1)
6402               && (closure->size1))
6403             return closure->string1[closure->size1 - 1];
6404           else
6405             return 0;           /* sure, why not. */
6406         }
6407     }
6408   if (pos->pos == pos->end)
6409     return *closure->string2;
6410   else
6411     return pos->pos[1];
6412 }
6413
6414
6415 #ifdef __STDC__
6416 RE_S2_QUAL int
6417 RE_SEARCH_2_FN (struct re_pattern_buffer *rxb,
6418                 __const__ char * string1, int size1,
6419                 __const__ char * string2, int size2,
6420                 int startpos, int range,
6421                 struct re_registers *regs,
6422                 int stop)
6423 #else
6424 RE_S2_QUAL int
6425 RE_SEARCH_2_FN (rxb,
6426                 string1, size1, string2, size2, startpos, range, regs, stop)
6427      struct re_pattern_buffer *rxb;
6428      __const__ char * string1;
6429      int size1;
6430      __const__ char * string2;
6431      int size2;
6432      int startpos;
6433      int range;
6434      struct re_registers *regs;
6435      int stop;
6436 #endif
6437 {
6438   int answer;
6439   struct re_search_2_closure closure;
6440   closure.string1 = string1;
6441   closure.size1 = size1;
6442   closure.string2 = string2;
6443   closure.size2 = size2;
6444   answer = rx_search (rxb, startpos, range, stop, size1 + size2,
6445                       re_search_2_get_burst,
6446                       re_search_2_back_check,
6447                       re_search_2_fetch_char,
6448                       (void *)&closure,
6449                       regs,
6450                       0,
6451                       0);
6452   switch (answer)
6453     {
6454     case rx_search_continuation:
6455       abort ();
6456     case rx_search_error:
6457       return -2;
6458     case rx_search_soft_fail:
6459     case rx_search_fail:
6460       return -1;
6461     default:
6462       return answer;
6463     }
6464 }
6465
6466 /* Export rx_search to callers outside this file.  */
6467
6468 int
6469 re_rx_search (rxb, startpos, range, stop, total_size,
6470               get_burst, back_check, fetch_char,
6471               app_closure, regs, resume_state, save_state)
6472      struct re_pattern_buffer * rxb;
6473      int startpos;
6474      int range;
6475      int stop;
6476      int total_size;
6477      rx_get_burst_fn get_burst;
6478      rx_back_check_fn back_check;
6479      rx_fetch_char_fn fetch_char;
6480      void * app_closure;
6481      struct re_registers * regs;
6482      struct rx_search_state * resume_state;
6483      struct rx_search_state * save_state;
6484 {
6485   return rx_search (rxb, startpos, range, stop, total_size,
6486                     get_burst, back_check, fetch_char, app_closure,
6487                     regs, resume_state, save_state);
6488 }
6489
6490 #if !defined(REGEX_MALLOC) && !defined(__GNUC__)
6491 #ifdef __STDC__
6492 int
6493 re_search_2 (struct re_pattern_buffer *rxb,
6494              __const__ char * string1, int size1,
6495              __const__ char * string2, int size2,
6496              int startpos, int range,
6497              struct re_registers *regs,
6498              int stop)
6499 #else
6500 int
6501 re_search_2 (rxb, string1, size1, string2, size2, startpos, range, regs, stop)
6502      struct re_pattern_buffer *rxb;
6503      __const__ char * string1;
6504      int size1;
6505      __const__ char * string2;
6506      int size2;
6507      int startpos;
6508      int range;
6509      struct re_registers *regs;
6510      int stop;
6511 #endif
6512 {
6513   int ret;
6514   ret = inner_re_search_2 (rxb, string1, size1, string2, size2, startpos,
6515                            range, regs, stop);
6516   alloca (0);
6517   return ret;
6518 }
6519 #endif
6520
6521
6522 /* Like re_search_2, above, but only one string is specified, and
6523  * doesn't let you say where to stop matching.
6524  */
6525
6526 #ifdef __STDC__
6527 int
6528 re_search (struct re_pattern_buffer * rxb, __const__ char *string,
6529            int size, int startpos, int range,
6530            struct re_registers *regs)
6531 #else
6532 int
6533 re_search (rxb, string, size, startpos, range, regs)
6534      struct re_pattern_buffer * rxb;
6535      __const__ char * string;
6536      int size;
6537      int startpos;
6538      int range;
6539      struct re_registers *regs;
6540 #endif
6541 {
6542   return re_search_2 (rxb, 0, 0, string, size, startpos, range, regs, size);
6543 }
6544
6545 #ifdef __STDC__
6546 int
6547 re_match_2 (struct re_pattern_buffer * rxb,
6548             __const__ char * string1, int size1,
6549             __const__ char * string2, int size2,
6550             int pos, struct re_registers *regs, int stop)
6551 #else
6552 int
6553 re_match_2 (rxb, string1, size1, string2, size2, pos, regs, stop)
6554      struct re_pattern_buffer * rxb;
6555      __const__ char * string1;
6556      int size1;
6557      __const__ char * string2;
6558      int size2;
6559      int pos;
6560      struct re_registers *regs;
6561      int stop;
6562 #endif
6563 {
6564   struct re_registers some_regs;
6565   regoff_t start;
6566   regoff_t end;
6567   int srch;
6568   int save = rxb->regs_allocated;
6569   struct re_registers * regs_to_pass = regs;
6570
6571   if (!regs)
6572     {
6573       some_regs.start = &start;
6574       some_regs.end = &end;
6575       some_regs.num_regs = 1;
6576       regs_to_pass = &some_regs;
6577       rxb->regs_allocated = REGS_FIXED;
6578     }
6579
6580   srch = re_search_2 (rxb, string1, size1, string2, size2,
6581                       pos, 1, regs_to_pass, stop);
6582   if (regs_to_pass != regs)
6583     rxb->regs_allocated = save;
6584   if (srch < 0)
6585     return srch;
6586   return regs_to_pass->end[0] - regs_to_pass->start[0];
6587 }
6588
6589 /* re_match is like re_match_2 except it takes only a single string.  */
6590
6591 #ifdef __STDC__
6592 int
6593 re_match (struct re_pattern_buffer * rxb,
6594           __const__ char * string,
6595           int size, int pos,
6596           struct re_registers *regs)
6597 #else
6598 int
6599 re_match (rxb, string, size, pos, regs)
6600      struct re_pattern_buffer * rxb;
6601      __const__ char *string;
6602      int size;
6603      int pos;
6604      struct re_registers *regs;
6605 #endif
6606 {
6607   return re_match_2 (rxb, string, size, 0, 0, pos, regs, size);
6608 }
6609
6610
6611 \f
6612 /* Set by `re_set_syntax' to the current regexp syntax to recognize.  Can
6613    also be assigned to arbitrarily: each pattern buffer stores its own
6614    syntax, so it can be changed between regex compilations.  */
6615 reg_syntax_t re_syntax_options = RE_SYNTAX_EMACS;
6616
6617
6618 /* Specify the precise syntax of regexps for compilation.  This provides
6619    for compatibility for various utilities which historically have
6620    different, incompatible syntaxes.
6621
6622    The argument SYNTAX is a bit mask comprised of the various bits
6623    defined in regex.h.  We return the old syntax.  */
6624
6625 #ifdef __STDC__
6626 reg_syntax_t
6627 re_set_syntax (reg_syntax_t syntax)
6628 #else
6629 reg_syntax_t
6630 re_set_syntax (syntax)
6631     reg_syntax_t syntax;
6632 #endif
6633 {
6634   reg_syntax_t ret = re_syntax_options;
6635
6636   re_syntax_options = syntax;
6637   return ret;
6638 }
6639 \f
6640
6641 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
6642    ENDS.  Subsequent matches using PATTERN_BUFFER and REGS will use
6643    this memory for recording register information.  STARTS and ENDS
6644    must be allocated using the malloc library routine, and must each
6645    be at least NUM_REGS * sizeof (regoff_t) bytes long.
6646
6647    If NUM_REGS == 0, then subsequent matches should allocate their own
6648    register data.
6649
6650    Unless this function is called, the first search or match using
6651    PATTERN_BUFFER will allocate its own register data, without
6652    freeing the old data.  */
6653
6654 #ifdef __STDC__
6655 void
6656 re_set_registers (struct re_pattern_buffer *bufp,
6657                   struct re_registers *regs,
6658                   unsigned num_regs,
6659                   regoff_t * starts, regoff_t * ends)
6660 #else
6661 void
6662 re_set_registers (bufp, regs, num_regs, starts, ends)
6663      struct re_pattern_buffer *bufp;
6664      struct re_registers *regs;
6665      unsigned num_regs;
6666      regoff_t * starts;
6667      regoff_t * ends;
6668 #endif
6669 {
6670   if (num_regs)
6671     {
6672       bufp->regs_allocated = REGS_REALLOCATE;
6673       regs->num_regs = num_regs;
6674       regs->start = starts;
6675       regs->end = ends;
6676     }
6677   else
6678     {
6679       bufp->regs_allocated = REGS_UNALLOCATED;
6680       regs->num_regs = 0;
6681       regs->start = regs->end = (regoff_t) 0;
6682     }
6683 }
6684
6685
6686 \f
6687
6688 #ifdef __STDC__
6689 static int
6690 cplx_se_sublist_len (struct rx_se_list * list)
6691 #else
6692 static int
6693 cplx_se_sublist_len (list)
6694      struct rx_se_list * list;
6695 #endif
6696 {
6697   int x = 0;
6698   while (list)
6699     {
6700       if ((long)list->car >= 0)
6701         ++x;
6702       list = list->cdr;
6703     }
6704   return x;
6705 }
6706
6707
6708 /* For rx->se_list_cmp */
6709
6710 #ifdef __STDC__
6711 static int
6712 posix_se_list_order (struct rx * rx,
6713                      struct rx_se_list * a, struct rx_se_list * b)
6714 #else
6715 static int
6716 posix_se_list_order (rx, a, b)
6717      struct rx * rx;
6718      struct rx_se_list * a;
6719      struct rx_se_list * b;
6720 #endif
6721 {
6722   int al = cplx_se_sublist_len (a);
6723   int bl = cplx_se_sublist_len (b);
6724
6725   if (!al && !bl)
6726     return ((a == b)
6727             ? 0
6728             : ((a < b) ? -1 : 1));
6729
6730   else if (!al)
6731     return -1;
6732
6733   else if (!bl)
6734     return 1;
6735
6736   else
6737     {
6738       rx_side_effect * av = ((rx_side_effect *)
6739                              alloca (sizeof (rx_side_effect) * (al + 1)));
6740       rx_side_effect * bv = ((rx_side_effect *)
6741                              alloca (sizeof (rx_side_effect) * (bl + 1)));
6742       struct rx_se_list * ap = a;
6743       struct rx_se_list * bp = b;
6744       int ai, bi;
6745
6746       for (ai = al - 1; ai >= 0; --ai)
6747         {
6748           while ((long)ap->car < 0)
6749             ap = ap->cdr;
6750           av[ai] = ap->car;
6751           ap = ap->cdr;
6752         }
6753       av[al] = (rx_side_effect)-2;
6754       for (bi = bl - 1; bi >= 0; --bi)
6755         {
6756           while ((long)bp->car < 0)
6757             bp = bp->cdr;
6758           bv[bi] = bp->car;
6759           bp = bp->cdr;
6760         }
6761       bv[bl] = (rx_side_effect)-1;
6762
6763       {
6764         int ret;
6765         int x = 0;
6766         while (av[x] == bv[x])
6767           ++x;
6768         ret = (((unsigned *)(av[x]) < (unsigned *)(bv[x])) ? -1 : 1);
6769         return ret;
6770       }
6771     }
6772 }
6773
6774
6775
6776 \f
6777 /* re_compile_pattern is the GNU regular expression compiler: it
6778    compiles PATTERN (of length SIZE) and puts the result in RXB.
6779    Returns 0 if the pattern was valid, otherwise an error string.
6780
6781    Assumes the `allocated' (and perhaps `buffer') and `translate' fields
6782    are set in RXB on entry.
6783
6784    We call rx_compile to do the actual compilation.  */
6785
6786 #ifdef __STDC__
6787 __const__ char *
6788 re_compile_pattern (__const__ char *pattern,
6789                     int length,
6790                     struct re_pattern_buffer * rxb)
6791 #else
6792 __const__ char *
6793 re_compile_pattern (pattern, length, rxb)
6794      __const__ char *pattern;
6795      int length;
6796      struct re_pattern_buffer * rxb;
6797 #endif
6798 {
6799   reg_errcode_t ret;
6800
6801   /* GNU code is written to assume at least RE_NREGS registers will be set
6802      (and at least one extra will be -1).  */
6803   rxb->regs_allocated = REGS_UNALLOCATED;
6804
6805   /* And GNU code determines whether or not to get register information
6806      by passing null for the REGS argument to re_match, etc., not by
6807      setting no_sub.  */
6808   rxb->no_sub = 0;
6809
6810   rxb->rx.local_cset_size = 256;
6811
6812   /* Match anchors at newline.  */
6813   rxb->newline_anchor = 1;
6814
6815   rxb->re_nsub = 0;
6816   rxb->start = 0;
6817   rxb->se_params = 0;
6818   rxb->rx.nodec = 0;
6819   rxb->rx.epsnodec = 0;
6820   rxb->rx.instruction_table = 0;
6821   rxb->rx.nfa_states = 0;
6822   rxb->rx.se_list_cmp = posix_se_list_order;
6823   rxb->rx.start_set = 0;
6824
6825   ret = rx_compile (pattern, length, re_syntax_options, rxb);
6826   alloca (0);
6827   return rx_error_msg[(int) ret];
6828 }
6829
6830
6831
6832 #ifdef __STDC__
6833 int
6834 re_compile_fastmap (struct re_pattern_buffer * rxb)
6835 #else
6836 int
6837 re_compile_fastmap (rxb)
6838      struct re_pattern_buffer * rxb;
6839 #endif
6840 {
6841   rx_blow_up_fastmap (rxb);
6842   return 0;
6843 }
6844
6845
6846
6847 \f
6848 /* Entry points compatible with 4.2 BSD regex library.  We don't define
6849    them if this is an Emacs or POSIX compilation.  */
6850
6851 #if (!defined (emacs) && !defined (_POSIX_SOURCE)) || defined(USE_BSD_REGEX)
6852
6853 /* BSD has one and only one pattern buffer.  */
6854 static struct re_pattern_buffer rx_comp_buf;
6855
6856 #ifdef __STDC__
6857 char *
6858 re_comp (__const__ char *s)
6859 #else
6860 char *
6861 re_comp (s)
6862     __const__ char *s;
6863 #endif
6864 {
6865   reg_errcode_t ret;
6866
6867   if (!s || (*s == '\0'))
6868     {
6869       if (!rx_comp_buf.buffer)
6870         return "No previous regular expression";
6871       return 0;
6872     }
6873
6874   if (!rx_comp_buf.fastmap)
6875     {
6876       rx_comp_buf.fastmap = (char *) malloc (1 << CHARBITS);
6877       if (!rx_comp_buf.fastmap)
6878         return "Memory exhausted";
6879     }
6880
6881   /* Since `rx_exec' always passes NULL for the `regs' argument, we
6882      don't need to initialize the pattern buffer fields which affect it.  */
6883
6884   /* Match anchors at newlines.  */
6885   rx_comp_buf.newline_anchor = 1;
6886
6887   rx_comp_buf.fastmap_accurate = 0;
6888   rx_comp_buf.re_nsub = 0;
6889   rx_comp_buf.start = 0;
6890   rx_comp_buf.se_params = 0;
6891   rx_comp_buf.rx.nodec = 0;
6892   rx_comp_buf.rx.epsnodec = 0;
6893   rx_comp_buf.rx.instruction_table = 0;
6894   rx_comp_buf.rx.nfa_states = 0;
6895   rx_comp_buf.rx.start = 0;
6896   rx_comp_buf.rx.se_list_cmp = posix_se_list_order;
6897   rx_comp_buf.rx.start_set = 0;
6898   rx_comp_buf.rx.local_cset_size = 256;
6899
6900   ret = rx_compile (s, strlen (s), re_syntax_options, &rx_comp_buf);
6901   alloca (0);
6902
6903   /* Yes, we're discarding `__const__' here.  */
6904   return (char *) rx_error_msg[(int) ret];
6905 }
6906
6907
6908 #ifdef __STDC__
6909 int
6910 re_exec (__const__ char *s)
6911 #else
6912 int
6913 re_exec (s)
6914     __const__ char *s;
6915 #endif
6916 {
6917   __const__ int len = strlen (s);
6918   return
6919     0 <= re_search (&rx_comp_buf, s, len, 0, len, (struct re_registers *) 0);
6920 }
6921 #endif /* not emacs and not _POSIX_SOURCE */
6922
6923 \f
6924
6925 /* POSIX.2 functions.  Don't define these for Emacs.  */
6926
6927 #if !defined(emacs)
6928
6929 /* regcomp takes a regular expression as a string and compiles it.
6930
6931    PREG is a regex_t *.  We do not expect any fields to be initialized,
6932    since POSIX says we shouldn't.  Thus, we set
6933
6934      `buffer' to the compiled pattern;
6935      `used' to the length of the compiled pattern;
6936      `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
6937        REG_EXTENDED bit in CFLAGS is set; otherwise, to
6938        RE_SYNTAX_POSIX_BASIC;
6939      `newline_anchor' to REG_NEWLINE being set in CFLAGS;
6940      `fastmap' and `fastmap_accurate' to zero;
6941      `re_nsub' to the number of subexpressions in PATTERN.
6942
6943    PATTERN is the address of the pattern string.
6944
6945    CFLAGS is a series of bits which affect compilation.
6946
6947      If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
6948      use POSIX basic syntax.
6949
6950      If REG_NEWLINE is set, then . and [^...] don't match newline.
6951      Also, regexec will try a match beginning after every newline.
6952
6953      If REG_ICASE is set, then we considers upper- and lowercase
6954      versions of letters to be equivalent when matching.
6955
6956      If REG_NOSUB is set, then when PREG is passed to regexec, that
6957      routine will report only success or failure, and nothing about the
6958      registers.
6959
6960    It returns 0 if it succeeds, nonzero if it doesn't.  (See regex.h for
6961    the return codes and their meanings.)  */
6962
6963
6964 #ifdef __STDC__
6965 int
6966 regcomp (regex_t * preg, __const__ char * pattern, int cflags)
6967 #else
6968 int
6969 regcomp (preg, pattern, cflags)
6970     regex_t * preg;
6971     __const__ char * pattern;
6972     int cflags;
6973 #endif
6974 {
6975   reg_errcode_t ret;
6976   unsigned syntax
6977     = cflags & REG_EXTENDED ? RE_SYNTAX_POSIX_EXTENDED : RE_SYNTAX_POSIX_BASIC;
6978
6979   /* regex_compile will allocate the space for the compiled pattern.  */
6980   preg->buffer = 0;
6981   preg->allocated = 0;
6982   preg->fastmap = malloc (256);
6983   if (!preg->fastmap)
6984     return REG_ESPACE;
6985   preg->fastmap_accurate = 0;
6986
6987   if (cflags & REG_ICASE)
6988     {
6989       unsigned i;
6990
6991       preg->translate = (unsigned char *) malloc (256);
6992       if (!preg->translate)
6993         return (int) REG_ESPACE;
6994
6995       /* Map uppercase characters to corresponding lowercase ones.  */
6996       for (i = 0; i < CHAR_SET_SIZE; i++)
6997         preg->translate[i] = isupper (i) ? tolower (i) : i;
6998     }
6999   else
7000     preg->translate = 0;
7001
7002   /* If REG_NEWLINE is set, newlines are treated differently.  */
7003   if (cflags & REG_NEWLINE)
7004     { /* REG_NEWLINE implies neither . nor [^...] match newline.  */
7005       syntax &= ~RE_DOT_NEWLINE;
7006       syntax |= RE_HAT_LISTS_NOT_NEWLINE;
7007       /* It also changes the matching behavior.  */
7008       preg->newline_anchor = 1;
7009     }
7010   else
7011     preg->newline_anchor = 0;
7012
7013   preg->no_sub = !!(cflags & REG_NOSUB);
7014
7015   /* POSIX says a null character in the pattern terminates it, so we
7016      can use strlen here in compiling the pattern.  */
7017   preg->re_nsub = 0;
7018   preg->start = 0;
7019   preg->se_params = 0;
7020   preg->syntax_parens = 0;
7021   preg->rx.nodec = 0;
7022   preg->rx.epsnodec = 0;
7023   preg->rx.instruction_table = 0;
7024   preg->rx.nfa_states = 0;
7025   preg->rx.local_cset_size = 256;
7026   preg->rx.start = 0;
7027   preg->rx.se_list_cmp = posix_se_list_order;
7028   preg->rx.start_set = 0;
7029   ret = rx_compile (pattern, strlen (pattern), syntax, preg);
7030   alloca (0);
7031
7032   /* POSIX doesn't distinguish between an unmatched open-group and an
7033      unmatched close-group: both are REG_EPAREN.  */
7034   if (ret == REG_ERPAREN) ret = REG_EPAREN;
7035
7036   return (int) ret;
7037 }
7038
7039
7040 /* regexec searches for a given pattern, specified by PREG, in the
7041    string STRING.
7042
7043    If NMATCH is zero or REG_NOSUB was set in the cflags argument to
7044    `regcomp', we ignore PMATCH.  Otherwise, we assume PMATCH has at
7045    least NMATCH elements, and we set them to the offsets of the
7046    corresponding matched substrings.
7047
7048    EFLAGS specifies `execution flags' which affect matching: if
7049    REG_NOTBOL is set, then ^ does not match at the beginning of the
7050    string; if REG_NOTEOL is set, then $ does not match at the end.
7051
7052    We return 0 if we find a match and REG_NOMATCH if not.  */
7053
7054 #ifdef __STDC__
7055 int
7056 regexec (__const__ regex_t *preg, __const__ char *string,
7057          size_t nmatch, regmatch_t pmatch[],
7058          int eflags)
7059 #else
7060 int
7061 regexec (preg, string, nmatch, pmatch, eflags)
7062     __const__ regex_t *preg;
7063     __const__ char *string;
7064     size_t nmatch;
7065     regmatch_t pmatch[];
7066     int eflags;
7067 #endif
7068 {
7069   int ret;
7070   struct re_registers regs;
7071   regex_t private_preg;
7072   int len = strlen (string);
7073   boolean want_reg_info = !preg->no_sub && nmatch > 0;
7074
7075   private_preg = *preg;
7076
7077   private_preg.not_bol = !!(eflags & REG_NOTBOL);
7078   private_preg.not_eol = !!(eflags & REG_NOTEOL);
7079
7080   /* The user has told us exactly how many registers to return
7081    * information about, via `nmatch'.  We have to pass that on to the
7082    * matching routines.
7083    */
7084   private_preg.regs_allocated = REGS_FIXED;
7085
7086   if (want_reg_info)
7087     {
7088       regs.num_regs = nmatch;
7089       regs.start =  (( regoff_t *) malloc ((nmatch) * sizeof ( regoff_t)));
7090       regs.end =  (( regoff_t *) malloc ((nmatch) * sizeof ( regoff_t)));
7091       if (regs.start == 0 || regs.end == 0)
7092         return (int) REG_NOMATCH;
7093     }
7094
7095   /* Perform the searching operation.  */
7096   ret = re_search (&private_preg,
7097                    string, len,
7098                    /* start: */ 0,
7099                    /* range: */ len,
7100                    want_reg_info ? &regs : (struct re_registers *) 0);
7101
7102   /* Copy the register information to the POSIX structure.  */
7103   if (want_reg_info)
7104     {
7105       if (ret >= 0)
7106         {
7107           unsigned r;
7108
7109           for (r = 0; r < nmatch; r++)
7110             {
7111               pmatch[r].rm_so = regs.start[r];
7112               pmatch[r].rm_eo = regs.end[r];
7113             }
7114         }
7115
7116       /* If we needed the temporary register info, free the space now.  */
7117       free (regs.start);
7118       free (regs.end);
7119     }
7120
7121   /* We want zero return to mean success, unlike `re_search'.  */
7122   return ret >= 0 ? (int) REG_NOERROR : (int) REG_NOMATCH;
7123 }
7124
7125
7126 /* Returns a message corresponding to an error code, ERRCODE, returned
7127    from either regcomp or regexec.   */
7128
7129 #ifdef __STDC__
7130 size_t
7131 regerror (int errcode, __const__ regex_t *preg,
7132           char *errbuf, size_t errbuf_size)
7133 #else
7134 size_t
7135 regerror (errcode, preg, errbuf, errbuf_size)
7136     int errcode;
7137     __const__ regex_t *preg;
7138     char *errbuf;
7139     size_t errbuf_size;
7140 #endif
7141 {
7142   __const__ char *msg
7143     = rx_error_msg[errcode] == 0 ? "Success" : rx_error_msg[errcode];
7144   size_t msg_size = strlen (msg) + 1; /* Includes the 0.  */
7145
7146   if (errbuf_size != 0)
7147     {
7148       if (msg_size > errbuf_size)
7149         {
7150           strncpy (errbuf, msg, errbuf_size - 1);
7151           errbuf[errbuf_size - 1] = 0;
7152         }
7153       else
7154         strcpy (errbuf, msg);
7155     }
7156
7157   return msg_size;
7158 }
7159
7160
7161 /* Free dynamically allocated space used by PREG.  */
7162
7163 #ifdef __STDC__
7164 void
7165 regfree (regex_t *preg)
7166 #else
7167 void
7168 regfree (preg)
7169     regex_t *preg;
7170 #endif
7171 {
7172   if (preg->buffer != 0)
7173     free (preg->buffer);
7174   preg->buffer = 0;
7175   preg->allocated = 0;
7176
7177   if (preg->fastmap != 0)
7178     free (preg->fastmap);
7179   preg->fastmap = 0;
7180   preg->fastmap_accurate = 0;
7181
7182   if (preg->translate != 0)
7183     free (preg->translate);
7184   preg->translate = 0;
7185 }
7186
7187 #endif /* not emacs  */
7188
7189
7190
7191
7192