rx/rxspencer.c

   1 /*      Copyright (C) 1995, 1996 Tom Lord
   2  *
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU Library General Public License as published by
   5  * the Free Software Foundation; either version 2, or (at your option)
   6  * any later version.
   7  *
   8  * This program is distributed in the hope that it will be useful,
   9  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11  * GNU Library General Public License for more details.
  12  *
  13  * You should have received a copy of the GNU Library General Public License
  14  * along with this software; see the file COPYING.  If not, write to
  15  * the Free Software Foundation, 59 Temple Place - Suite 330,
  16  * Boston, MA 02111-1307, USA.
  17  */
  18
  19
  20 \f
  21 #include <stdio.h>
  22 #include "rxall.h"
  23 #include "rxspencer.h"
  24 #include "rxsimp.h"
  25
  26 \f
  27
  28 static char * silly_hack_2 = 0;
  29
  30 struct rx_solutions rx_no_solutions;
  31
  32 #ifdef __STDC__
  33 struct rx_solutions *
  34 rx_make_solutions (struct rx_registers * regs, struct rx_unfaniverse * verse, struct rexp_node * expression, struct rexp_node ** subexps, int cset_size, int start, int end, rx_vmfn vmfn, rx_contextfn contextfn, void * closure)
  35 #else
  36 struct rx_solutions *
  37 rx_make_solutions (regs, verse, expression, subexps, cset_size,
  38                    start, end, vmfn, contextfn, closure)
  39      struct rx_registers * regs;
  40      struct rx_unfaniverse * verse;
  41      struct rexp_node * expression;
  42      struct rexp_node ** subexps;
  43      int cset_size;
  44      int start;
  45      int end;
  46      rx_vmfn vmfn;
  47      rx_contextfn contextfn;
  48      void * closure;
  49 #endif
  50 {
  51   struct rx_solutions * solns;
  52
  53   if (   expression
  54       && (expression->len >= 0)
  55       && (expression->len != (end - start)))
  56     return &rx_no_solutions;
  57
  58   if (silly_hack_2)
  59     {
  60       solns = (struct rx_solutions *)silly_hack_2;
  61       silly_hack_2 = 0;
  62     }
  63   else
  64     solns = (struct rx_solutions *)malloc (sizeof (*solns));
  65   if (!solns)
  66     return 0;
  67   rx_bzero ((char *)solns, sizeof (*solns));
  68
  69   solns->step = 0;
  70   solns->cset_size = cset_size;
  71   solns->subexps = subexps;
  72   solns->exp = expression;
  73   rx_save_rexp (expression);
  74   solns->verse = verse;
  75   solns->regs = regs;
  76   solns->start = start;
  77   solns->end = end;
  78   solns->vmfn = vmfn;
  79   solns->contextfn = contextfn;
  80   solns->closure = closure;
  81
  82   if (!solns->exp || !solns->exp->observed)
  83     {
  84       solns->dfa = rx_unfa (verse, expression, cset_size);
  85       if (!solns->dfa)
  86         goto err_return;
  87       rx_init_system (&solns->match_engine, solns->dfa->nfa);
  88
  89       if (rx_yes != rx_start_superstate (&solns->match_engine))
  90         goto err_return;
  91     }
  92   else
  93     {
  94       struct rexp_node * simplified;
  95       int status;
  96       status = rx_simple_rexp (&simplified, cset_size, solns->exp, subexps);
  97       if (status)
  98         goto err_return;
  99       solns->dfa = rx_unfa (verse, simplified, cset_size);
 100       if (!solns->dfa)
 101         {
 102           rx_free_rexp (simplified);
 103           goto err_return;
 104         }
 105       rx_init_system (&solns->match_engine, solns->dfa->nfa);
 106       if (rx_yes != rx_start_superstate (&solns->match_engine))
 107         goto err_return;
 108       rx_free_rexp (simplified);
 109     }
 110
 111   if (expression && (   (expression->type == r_concat)
 112                      || (expression->type == r_plus)
 113                      || (expression->type == r_star)
 114                      || (expression->type == r_interval)))
 115     {
 116       struct rexp_node * subexp;
 117
 118       subexp = solns->exp->params.pair.left;
 119
 120       if (!subexp || !subexp->observed)
 121         {
 122           solns->left_dfa = rx_unfa (solns->verse, subexp, solns->cset_size);
 123         }
 124       else
 125         {
 126           struct rexp_node * simplified;
 127           int status;
 128           status = rx_simple_rexp (&simplified, solns->cset_size, subexp, solns->subexps);
 129           if (status)
 130             goto err_return;
 131           solns->left_dfa = rx_unfa (solns->verse, simplified, solns->cset_size);
 132           rx_free_rexp (simplified);
 133         }
 134
 135       if (!solns->left_dfa)
 136         goto err_return;
 137       rx_bzero ((char *)&solns->left_match_engine, sizeof (solns->left_match_engine));
 138       rx_init_system (&solns->left_match_engine, solns->left_dfa->nfa);
 139     }
 140
 141   return solns;
 142
 143  err_return:
 144   rx_free_rexp (solns->exp);
 145   free (solns);
 146   return 0;
 147 }
 148
 149
 150 \f
 151 #ifdef __STDC__
 152 void
 153 rx_free_solutions (struct rx_solutions * solns)
 154 #else
 155 void
 156 rx_free_solutions (solns)
 157      struct rx_solutions * solns;
 158 #endif
 159 {
 160   if (!solns)
 161     return;
 162
 163   if (solns == &rx_no_solutions)
 164     return;
 165
 166   if (solns->left)
 167     {
 168       rx_free_solutions (solns->left);
 169       solns->left = 0;
 170     }
 171
 172   if (solns->right)
 173     {
 174       rx_free_solutions (solns->right);
 175       solns->right = 0;
 176     }
 177
 178   if (solns->dfa)
 179     {
 180       rx_free_unfa (solns->dfa);
 181       solns->dfa = 0;
 182     }
 183   if (solns->left_dfa)
 184     {
 185       rx_terminate_system (&solns->left_match_engine);
 186       rx_free_unfa (solns->left_dfa);
 187       solns->left_dfa = 0;
 188     }
 189
 190   rx_terminate_system (&solns->match_engine);
 191
 192   if (solns->exp)
 193     {
 194       rx_free_rexp (solns->exp);
 195       solns->exp = 0;
 196     }
 197
 198   if (!silly_hack_2)
 199     silly_hack_2 = (char *)solns;
 200   else
 201     free (solns);
 202 }
 203
 204 \f
 205 #ifdef __STDC__
 206 static enum rx_answers
 207 rx_solution_fit_p (struct rx_solutions * solns)
 208 #else
 209 static enum rx_answers
 210 rx_solution_fit_p (solns)
 211      struct rx_solutions * solns;
 212 #endif
 213 {
 214   unsigned const char * burst;
 215   int burst_addr;
 216   int burst_len;
 217   int burst_end_addr;
 218   int rel_pos_in_burst;
 219   enum rx_answers vmstat;
 220   int current_pos;
 221
 222   current_pos = solns->start;
 223  next_burst:
 224   vmstat = solns->vmfn (solns->closure,
 225                         &burst, &burst_len, &burst_addr,
 226                         current_pos, solns->end,
 227                         current_pos);
 228
 229   if (vmstat != rx_yes)
 230     return vmstat;
 231
 232   rel_pos_in_burst = current_pos - burst_addr;
 233   burst_end_addr = burst_addr + burst_len;
 234
 235   if (burst_end_addr >= solns->end)
 236     {
 237       enum rx_answers fit_status;
 238       fit_status = rx_fit_p (&solns->match_engine,
 239                              burst + rel_pos_in_burst,
 240                              solns->end - current_pos);
 241       return fit_status;
 242     }
 243   else
 244     {
 245       enum rx_answers fit_status;
 246       fit_status = rx_advance (&solns->match_engine,
 247                                burst + rel_pos_in_burst,
 248                                burst_len - rel_pos_in_burst);
 249       if (fit_status != rx_yes)
 250         {
 251           return fit_status;
 252         }
 253       else
 254         {
 255           current_pos += burst_len - rel_pos_in_burst;
 256           goto next_burst;
 257         }
 258     }
 259 }
 260 \f
 261
 262 #ifdef __STDC__
 263 static enum rx_answers
 264 rx_solution_fit_str_p (struct rx_solutions * solns)
 265 #else
 266 static enum rx_answers
 267 rx_solution_fit_str_p (solns)
 268      struct rx_solutions * solns;
 269 #endif
 270 {
 271   int current_pos;
 272   unsigned const char * burst;
 273   int burst_addr;
 274   int burst_len;
 275   int burst_end_addr;
 276   int rel_pos_in_burst;
 277   enum rx_answers vmstat;
 278   int count;
 279   unsigned char * key;
 280
 281
 282   current_pos = solns->start;
 283   count = solns->exp->params.cstr.len;
 284   key = (unsigned char *)solns->exp->params.cstr.contents;
 285
 286  next_burst:
 287   vmstat = solns->vmfn (solns->closure,
 288                         &burst, &burst_len, &burst_addr,
 289                         current_pos, solns->end,
 290                         current_pos);
 291
 292   if (vmstat != rx_yes)
 293     return vmstat;
 294
 295   rel_pos_in_burst = current_pos - burst_addr;
 296   burst_end_addr = burst_addr + burst_len;
 297
 298   {
 299     unsigned const char * pos;
 300
 301     pos = burst + rel_pos_in_burst;
 302
 303     if (burst_end_addr >= solns->end)
 304       {
 305         while (count)
 306           {
 307             if (*pos != *key)
 308               return rx_no;
 309             ++pos;
 310             ++key;
 311             --count;
 312           }
 313         return rx_yes;
 314       }
 315     else
 316       {
 317         int part_count;
 318         int part_count_init;
 319
 320         part_count_init = burst_len - rel_pos_in_burst;
 321         part_count = part_count_init;
 322         while (part_count)
 323           {
 324             if (*pos != *key)
 325               return rx_no;
 326             ++pos;
 327             ++key;
 328             --part_count;
 329           }
 330         count -= part_count_init;
 331         current_pos += burst_len - rel_pos_in_burst;
 332         goto next_burst;
 333       }
 334   }
 335 }
 336
 337
 338 \f
 339
 340 #if 0
 341 #ifdef __STDC__
 342 int
 343 rx_best_end_guess (struct rx_solutions * solns, struct rexp_node *  exp, int bound)
 344 #else
 345 int
 346 rx_best_end_guess (solns, exp, bound)
 347      struct rx_solutions * solns;
 348      struct rexp_node *  exp;
 349      int bound;
 350 #endif
 351 {
 352   int current_pos;
 353   unsigned const char * burst;
 354   int burst_addr;
 355   int burst_len;
 356   int burst_end_addr;
 357   int rel_pos_in_burst;
 358   int best_guess;
 359   enum rx_answers vmstat;
 360
 361 #if 0
 362   unparse_print_rexp (256, solns->exp);
 363   printf ("\n");
 364   unparse_print_rexp (256, exp);
 365   printf ("\nbound %d \n", bound);
 366 #endif
 367
 368   if (rx_yes != rx_start_superstate (&solns->left_match_engine))
 369     {
 370       return bound - 1;
 371     }
 372   best_guess = current_pos = solns->start;
 373
 374  next_burst:
 375 #if 0
 376   printf ("  best_guess %d\n", best_guess);
 377 #endif
 378   vmstat = solns->vmfn (solns->closure,
 379                         &burst, &burst_len, &burst_addr,
 380                         current_pos, bound,
 381                         current_pos);
 382 #if 0
 383   printf ("  str>%s\n", burst);
 384 #endif
 385   if (vmstat != rx_yes)
 386     {
 387       return bound - 1;
 388     }
 389
 390   rel_pos_in_burst = current_pos - burst_addr;
 391   burst_end_addr = burst_addr + burst_len;
 392
 393   if (burst_end_addr > bound)
 394     {
 395       burst_end_addr = bound;
 396       burst_len = bound - burst_addr;
 397     }
 398
 399   {
 400     int amt_advanced;
 401
 402 #if 0
 403     printf ("  rel_pos_in_burst %d burst_len %d\n", rel_pos_in_burst, burst_len);
 404 #endif
 405     while (rel_pos_in_burst < burst_len)
 406       {
 407         amt_advanced= rx_advance_to_final (&solns->left_match_engine,
 408                                            burst + rel_pos_in_burst,
 409                                            burst_len - rel_pos_in_burst);
 410 #if 0
 411         printf ("  amt_advanced %d", amt_advanced);
 412 #endif
 413         if (amt_advanced < 0)
 414           {
 415             return bound - 1;
 416           }
 417         current_pos += amt_advanced;
 418         rel_pos_in_burst += amt_advanced;
 419         if (solns->left_match_engine.final_tag)
 420           best_guess = current_pos;
 421 #if 0
 422         printf ("  best_guess %d\n", best_guess);
 423         printf ("  current_pos %d\n", current_pos);
 424 #endif
 425         if (amt_advanced == 0)
 426           {
 427             return best_guess;
 428           }
 429       }
 430     if (current_pos == bound)
 431       {
 432         return best_guess;
 433       }
 434     goto next_burst;
 435   }
 436 }
 437 #endif
 438
 439
 440 \f
 441 #ifdef __STDC__
 442 enum rx_answers
 443 rx_next_solution (struct rx_solutions * solns)
 444 #else
 445 enum rx_answers
 446 rx_next_solution (solns)
 447      struct rx_solutions * solns;
 448 #endif
 449 {
 450   if (!solns)
 451     return rx_bogus;
 452
 453   if (solns == &rx_no_solutions)
 454     {
 455       return rx_no;
 456     }
 457
 458   if (!solns->exp)
 459     {
 460       if (solns->step != 0)
 461         {
 462           return rx_no;
 463         }
 464       else
 465         {
 466           solns->step = 1;
 467           solns->final_tag = 1;
 468           return (solns->start == solns->end
 469                   ? rx_yes
 470                   : rx_no);
 471         }
 472     }
 473   else if (   (solns->exp->len >= 0)
 474            && (solns->exp->len != (solns->end - solns->start)))
 475     {
 476       return rx_no;
 477     }
 478   else if (!solns->exp->observed)
 479     {
 480       if (solns->step != 0)
 481         {
 482           return rx_no;
 483         }
 484       else if (solns->exp->type == r_string)
 485         {
 486           enum rx_answers ans;
 487           ans = rx_solution_fit_str_p (solns);
 488           solns->final_tag = 1;
 489           solns->step = -1;
 490           return ans;
 491         }
 492       else
 493         {
 494           enum rx_answers ans;
 495           ans = rx_solution_fit_p (solns);
 496           solns->final_tag = solns->match_engine.final_tag;
 497           solns->step = -1;
 498           return ans;
 499         }
 500     }
 501   else if (solns->exp->observed)
 502     {
 503       enum rx_answers fit_p;
 504       switch (solns->step)
 505         {
 506         case -2:
 507           if (solns->exp->params.intval)
 508             {
 509               solns->regs[solns->exp->params.intval].rm_so = solns->saved_rm_so;
 510               solns->regs[solns->exp->params.intval].rm_eo = solns->saved_rm_eo;
 511             }
 512           return rx_no;
 513
 514         case -1:
 515           return rx_no;
 516
 517         case 0:
 518           fit_p = rx_solution_fit_p (solns);
 519           /* Set final_tag here because this rough fit test
 520            * may be all the matching that gets done.
 521            * For example, consider a paren node containing
 522            * a true regular expression ending with a cut
 523            * operator.
 524            */
 525           solns->final_tag = solns->match_engine.final_tag;
 526           switch (fit_p)
 527             {
 528             case rx_no:
 529               solns->step = -1;
 530               return rx_no;
 531             case rx_yes:
 532               solns->step = 1;
 533               goto resolve_fit;
 534             case rx_bogus:
 535             default:
 536               solns->step = -1;
 537               return fit_p;
 538             }
 539
 540         default:
 541         resolve_fit:
 542           switch (solns->exp->type)
 543             {
 544             case r_cset:
 545             case r_string:
 546             case r_cut:
 547               solns->step = -1;
 548               return rx_bogus;
 549
 550             case r_parens:
 551               {
 552                 enum rx_answers paren_stat;
 553                 switch (solns->step)
 554                   {
 555                   case 1:
 556                     if (solns->exp->params.intval)
 557                       {
 558                         solns->saved_rm_so = solns->regs[solns->exp->params.intval].rm_so;
 559                         solns->saved_rm_eo = solns->regs[solns->exp->params.intval].rm_eo;
 560                       }
 561
 562                     if (   !solns->exp->params.pair.left
 563                         || !solns->exp->params.pair.left->observed)
 564                       {
 565                         if (solns->exp->params.intval)
 566                           {
 567                             solns->regs[solns->exp->params.intval].rm_so = solns->start;
 568                             solns->regs[solns->exp->params.intval].rm_eo = solns->end;
 569                           }
 570                         solns->step = -2;
 571                         /* Keep the final_tag from the fit_p test. */
 572                         return rx_yes;
 573                       }
 574                     else
 575                       {
 576                         solns->left = rx_make_solutions (solns->regs,
 577                                                          solns->verse,
 578                                                          solns->exp->params.pair.left,
 579                                                          solns->subexps,
 580                                                          solns->cset_size,
 581                                                          solns->start,
 582                                                          solns->end,
 583                                                          solns->vmfn,
 584                                                          solns->contextfn,
 585                                                          solns->closure);
 586                         if (!solns->left)
 587                           {
 588                             solns->step = -1;
 589                             return rx_bogus;
 590                           }
 591                       }
 592                     solns->step = 2;
 593                     /* fall through */
 594
 595                   case 2:
 596                     if (solns->exp->params.intval)
 597                       {
 598                         solns->regs[solns->exp->params.intval].rm_so = solns->saved_rm_so;
 599                         solns->regs[solns->exp->params.intval].rm_eo = solns->saved_rm_eo;
 600                       }
 601
 602                     paren_stat = rx_next_solution (solns->left);
 603                     if (paren_stat == rx_yes)
 604                       {
 605                         if (solns->exp->params.intval)
 606                           {
 607                             solns->regs[solns->exp->params.intval].rm_so = solns->start;
 608                             solns->regs[solns->exp->params.intval].rm_eo = solns->end;
 609                           }
 610                         solns->final_tag = solns->left->final_tag;
 611                         return rx_yes;
 612                       }
 613                     else
 614                       {
 615                         solns->step = -1;
 616                         rx_free_solutions (solns->left);
 617                         solns->left = 0;
 618                         if (solns->exp->params.intval)
 619                           {
 620                             solns->regs[solns->exp->params.intval].rm_so = solns->saved_rm_so;
 621                             solns->regs[solns->exp->params.intval].rm_eo = solns->saved_rm_eo;
 622                           }
 623                         return paren_stat;
 624                       }
 625                   }
 626               }
 627
 628
 629             case r_opt:
 630               {
 631                 enum rx_answers opt_stat;
 632                 switch (solns->step)
 633                   {
 634                   case 1:
 635                     solns->left = rx_make_solutions (solns->regs,
 636                                                      solns->verse,
 637                                                      solns->exp->params.pair.left,
 638                                                      solns->subexps,
 639                                                      solns->cset_size,
 640                                                      solns->start,
 641                                                      solns->end,
 642                                                      solns->vmfn,
 643                                                      solns->contextfn,
 644                                                      solns->closure);
 645                     if (!solns->left)
 646                       {
 647                         solns->step = -1;
 648                         return rx_bogus;
 649                       }
 650                     solns->step = 2;
 651                     /* fall through */
 652
 653                   case 2:
 654                     opt_stat = rx_next_solution (solns->left);
 655                     if (opt_stat == rx_yes)
 656                       {
 657                         solns->final_tag = solns->left->final_tag;
 658                         return rx_yes;
 659                       }
 660                     else
 661                       {
 662                         solns->step = -1;
 663                         rx_free_solutions (solns->left);
 664                         solns->left = 0;
 665                         return ((solns->start == solns->end)
 666                                 ? rx_yes
 667                                 : rx_no);
 668                       }
 669
 670                   }
 671              }
 672
 673             case r_alternate:
 674               {
 675                 enum rx_answers alt_stat;
 676                 switch (solns->step)
 677                   {
 678                   case 1:
 679                     solns->left = rx_make_solutions (solns->regs,
 680                                                      solns->verse,
 681                                                      solns->exp->params.pair.left,
 682                                                      solns->subexps,
 683                                                      solns->cset_size,
 684                                                      solns->start,
 685                                                      solns->end,
 686                                                      solns->vmfn,
 687                                                      solns->contextfn,
 688                                                      solns->closure);
 689                     if (!solns->left)
 690                       {
 691                         solns->step = -1;
 692                         return rx_bogus;
 693                       }
 694                     solns->step = 2;
 695                     /* fall through */
 696
 697                   case 2:
 698                     alt_stat = rx_next_solution (solns->left);
 699
 700                     if (alt_stat == rx_yes)
 701                       {
 702                         solns->final_tag = solns->left->final_tag;
 703                         return alt_stat;
 704                       }
 705                     else
 706                       {
 707                         solns->step = 3;
 708                         rx_free_solutions (solns->left);
 709                         solns->left = 0;
 710                         /* fall through */
 711                       }
 712
 713                   case 3:
 714                     solns->right = rx_make_solutions (solns->regs,
 715                                                       solns->verse,
 716                                                       solns->exp->params.pair.right,
 717                                                       solns->subexps,
 718                                                       solns->cset_size,
 719                                                       solns->start,
 720                                                       solns->end,
 721                                                       solns->vmfn,
 722                                                       solns->contextfn,
 723                                                       solns->closure);
 724                     if (!solns->right)
 725                       {
 726                         solns->step = -1;
 727                         return rx_bogus;
 728                       }
 729                     solns->step = 4;
 730                     /* fall through */
 731
 732                   case 4:
 733                     alt_stat = rx_next_solution (solns->right);
 734
 735                     if (alt_stat == rx_yes)
 736                       {
 737                         solns->final_tag = solns->right->final_tag;
 738                         return alt_stat;
 739                       }
 740                     else
 741                       {
 742                         solns->step = -1;
 743                         rx_free_solutions (solns->right);
 744                         solns->right = 0;
 745                         return alt_stat;
 746                       }
 747                   }
 748              }
 749
 750             case r_concat:
 751               {
 752                 switch (solns->step)
 753                   {
 754                     enum rx_answers concat_stat;
 755                   case 1:
 756                     solns->split_guess = solns->end;
 757 #if 0
 758                     solns->split_guess = ((solns->end - solns->start) > RX_MANY_CASES
 759                                           ? rx_best_end_guess (solns,
 760                                                                solns->exp->params.pair.left, solns->end)
 761                                           : solns->end);
 762 #endif
 763
 764                   concat_split_guess_loop:
 765                     solns->left = rx_make_solutions (solns->regs,
 766                                                      solns->verse,
 767                                                      solns->exp->params.pair.left,
 768                                                      solns->subexps,
 769                                                      solns->cset_size,
 770                                                      solns->start,
 771                                                      solns->split_guess,
 772                                                      solns->vmfn,
 773                                                      solns->contextfn,
 774                                                      solns->closure);
 775                     if (!solns->left)
 776                       {
 777                         solns->step = -1;
 778                         return rx_bogus;
 779                       }
 780                     solns->step = 2;
 781
 782                   case 2:
 783                   concat_try_next_left_match:
 784
 785                     concat_stat = rx_next_solution (solns->left);
 786                     if (concat_stat != rx_yes)
 787                       {
 788                         rx_free_solutions (solns->left);
 789                         rx_free_solutions (solns->right);
 790                         solns->left = solns->right = 0;
 791                         solns->split_guess = solns->split_guess - 1;
 792 #if 0
 793                         solns->split_guess = ((solns->split_guess - solns->start) > RX_MANY_CASES
 794                                               ? rx_best_end_guess (solns,
 795                                                                    solns->exp->params.pair.left,
 796                                                                    solns->split_guess - 1)
 797                                               : solns->split_guess - 1);
 798 #endif
 799                         if (solns->split_guess >= solns->start)
 800                           goto concat_split_guess_loop;
 801                         else
 802                           {
 803                             solns->step = -1;
 804                             return concat_stat;
 805                           }
 806                       }
 807                     else
 808                       {
 809                         solns->step = 3;
 810                         /* fall through */
 811                       }
 812
 813                   case 3:
 814                     solns->right = rx_make_solutions (solns->regs,
 815                                                       solns->verse,
 816                                                       solns->exp->params.pair.right,
 817                                                       solns->subexps,
 818                                                       solns->cset_size,
 819                                                       solns->split_guess,
 820                                                       solns->end,
 821                                                       solns->vmfn,
 822                                                       solns->contextfn,
 823                                                       solns->closure);
 824                     if (!solns->right)
 825                       {
 826                         rx_free_solutions (solns->left);
 827                         solns->left = 0;
 828                         solns->step = -1;
 829                         return rx_bogus;
 830                       }
 831
 832                     solns->step = 4;
 833                     /* fall through */
 834
 835                   case 4:
 836                   /* concat_try_next_right_match: */
 837
 838                     concat_stat = rx_next_solution (solns->right);
 839                     if (concat_stat == rx_yes)
 840                       {
 841                         solns->final_tag = solns->right->final_tag;
 842                         return concat_stat;
 843                       }
 844                     else if (concat_stat == rx_no)
 845                       {
 846                         rx_free_solutions (solns->right);
 847                         solns->right = 0;
 848                         solns->step = 2;
 849                         goto concat_try_next_left_match;
 850                       }
 851                     else /*  concat_stat == rx_bogus */
 852                       {
 853                         rx_free_solutions (solns->left);
 854                         solns->left = 0;
 855                         rx_free_solutions (solns->right);
 856                         solns->right = 0;
 857                         solns->step = -1;
 858                         return concat_stat;
 859                       }
 860                   }
 861               }
 862
 863
 864             case r_plus:
 865             case r_star:
 866               {
 867                 switch (solns->step)
 868                   {
 869                     enum rx_answers star_stat;
 870                   case 1:
 871                     solns->split_guess = solns->end;
 872 #if 0
 873                     solns->split_guess = ((solns->end - solns->start) > RX_MANY_CASES
 874                                           ? rx_best_end_guess (solns,
 875                                                                solns->exp->params.pair.left, solns->end)
 876                                           : solns->end);
 877 #endif
 878
 879                   star_split_guess_loop:
 880                     solns->left = rx_make_solutions (solns->regs,
 881                                                      solns->verse,
 882                                                      solns->exp->params.pair.left,
 883                                                      solns->subexps,
 884                                                      solns->cset_size,
 885                                                      solns->start,
 886                                                      solns->split_guess,
 887                                                      solns->vmfn,
 888                                                      solns->contextfn,
 889                                                      solns->closure);
 890                     if (!solns->left)
 891                       {
 892                         solns->step = -1;
 893                         return rx_bogus;
 894                       }
 895                     solns->step = 2;
 896
 897                   case 2:
 898                   star_try_next_left_match:
 899
 900                     star_stat = rx_next_solution (solns->left);
 901                     if (star_stat != rx_yes)
 902                       {
 903                         rx_free_solutions (solns->left);
 904                         rx_free_solutions (solns->right);
 905                         solns->left = solns->right = 0;
 906                         solns->split_guess = solns->split_guess - 1;
 907 #if 0
 908                         solns->split_guess = ((solns->split_guess - solns->start) > RX_MANY_CASES
 909                                               ? rx_best_end_guess (solns,
 910                                                                    solns->exp->params.pair.left,
 911                                                                    solns->split_guess - 1)
 912                                               : solns->split_guess - 1);
 913 #endif
 914                         if (solns->split_guess >= solns->start)
 915                           goto star_split_guess_loop;
 916                         else
 917                           {
 918                             solns->step = -1;
 919
 920                             if (   (solns->exp->type == r_star)
 921                                 && (solns->start == solns->end)
 922                                 && (star_stat == rx_no))
 923                               {
 924                                 solns->final_tag = 1;
 925                                 return rx_yes;
 926                               }
 927                             else
 928                               return star_stat;
 929                           }
 930                       }
 931                     else
 932                       {
 933                         solns->step = 3;
 934                         /* fall through */
 935                       }
 936
 937
 938                     if (solns->split_guess == solns->end)
 939                       {
 940                         solns->final_tag = solns->left->final_tag;
 941                         return rx_yes;
 942                       }
 943
 944                   case 3:
 945                     solns->right = rx_make_solutions (solns->regs,
 946                                                       solns->verse,
 947                                                       solns->exp,
 948                                                       solns->subexps,
 949                                                       solns->cset_size,
 950                                                       solns->split_guess,
 951                                                       solns->end,
 952                                                       solns->vmfn,
 953                                                       solns->contextfn,
 954                                                       solns->closure);
 955                     if (!solns->right)
 956                       {
 957                         rx_free_solutions (solns->left);
 958                         solns->left = 0;
 959                         solns->step = -1;
 960                         return rx_bogus;
 961                       }
 962
 963                     solns->step = 4;
 964                     /* fall through */
 965
 966                   case 4:
 967                   /* star_try_next_right_match: */
 968
 969                     star_stat = rx_next_solution (solns->right);
 970                     if (star_stat == rx_yes)
 971                       {
 972                         solns->final_tag = solns->right->final_tag;
 973                         return star_stat;
 974                       }
 975                     else if (star_stat == rx_no)
 976                       {
 977                         rx_free_solutions (solns->right);
 978                         solns->right = 0;
 979                         solns->step = 2;
 980                         goto star_try_next_left_match;
 981                       }
 982                     else /*  star_stat == rx_bogus */
 983                       {
 984                         rx_free_solutions (solns->left);
 985                         solns->left = 0;
 986                         rx_free_solutions (solns->right);
 987                         solns->right = 0;
 988                         solns->step = -1;
 989                         return star_stat;
 990                       }
 991                   }
 992               }
 993
 994             case r_interval:
 995               {
 996                 switch (solns->step)
 997                   {
 998                     enum rx_answers interval_stat;
 999
1000                   case 1:
1001                     /* If the interval permits nothing,
1002                      * return immediately.
1003                      */
1004                     if (solns->exp->params.intval2 < solns->interval_x)
1005                       {
1006                         solns->step = -1;
1007                         return rx_no;
1008                       }
1009
1010                     /* If the interval permits only 0 iterations,
1011                      * return immediately.  Success depends on the
1012                      * emptiness of the match.
1013                      */
1014                     if (   (solns->exp->params.intval2 == solns->interval_x)
1015                         && (solns->exp->params.intval <= solns->interval_x))
1016                       {
1017                         solns->step = -1;
1018                         solns->final_tag = 1;
1019                         return ((solns->start == solns->end)
1020                                 ? rx_yes
1021                                 : rx_no);
1022                       }
1023
1024                     /* The interval permits at most 0 iterations,
1025                      * but also requires more.  A bug.
1026                      */
1027                     if (solns->exp->params.intval2 == solns->interval_x)
1028                       {
1029                         /* indicates a regexp compilation error, actually */
1030                         solns->step = -1;
1031                         return rx_bogus;
1032                       }
1033
1034                     solns->split_guess = solns->end;
1035 #if 0
1036                     solns->split_guess = ((solns->end - solns->start) > RX_MANY_CASES
1037                                           ? rx_best_end_guess (solns,
1038                                                                solns->exp->params.pair.left, solns->end)
1039                                           : solns->end);
1040 #endif
1041
1042                     /* The interval permits more than 0 iterations.
1043                      * If it permits 0 and the match is to be empty,
1044                      * the trivial match is the most preferred answer.
1045                      */
1046                     if (solns->exp->params.intval <= solns->interval_x)
1047                       {
1048                         solns->step = 2;
1049                         if (solns->start == solns->end)
1050                           {
1051                             solns->final_tag = 1;
1052                             return rx_yes;
1053                           }
1054                         /* If this isn't a trivial match, or if the trivial match
1055                          * is rejected, look harder.
1056                          */
1057                       }
1058
1059                   case 2:
1060                   interval_split_guess_loop:
1061                     /* The match requires at least one iteration, either because
1062                      * there are characters to match, or because the interval starts
1063                      * above 0.
1064                      *
1065                      * Look for the first iteration:
1066                      */
1067                     solns->left = rx_make_solutions (solns->regs,
1068                                                      solns->verse,
1069                                                      solns->exp->params.pair.left,
1070                                                      solns->subexps,
1071                                                      solns->cset_size,
1072                                                      solns->start,
1073                                                      solns->split_guess,
1074                                                      solns->vmfn,
1075                                                      solns->contextfn,
1076                                                      solns->closure);
1077                     if (!solns->left)
1078                       {
1079                         solns->step = -1;
1080                         return rx_bogus;
1081                       }
1082                     solns->step = 3;
1083
1084                   case 3:
1085                   interval_try_next_left_match:
1086
1087                     interval_stat = rx_next_solution (solns->left);
1088                     if (interval_stat != rx_yes)
1089                       {
1090                         rx_free_solutions (solns->left);
1091                         rx_free_solutions (solns->right);
1092                         solns->left = solns->right = 0;
1093                         solns->split_guess = solns->split_guess - 1;
1094 #if 0
1095                         solns->split_guess = ((solns->split_guess - solns->start) > RX_MANY_CASES
1096                                               ? rx_best_end_guess (solns,
1097                                                                    solns->exp->params.pair.left,
1098                                                                    solns->split_guess - 1)
1099                                               : solns->split_guess - 1);
1100 #endif
1101                         if (solns->split_guess >= solns->start)
1102                           goto interval_split_guess_loop;
1103                         else
1104                           {
1105                             solns->step = -1;
1106                             return interval_stat;
1107                           }
1108                       }
1109                     else
1110                       {
1111                         solns->step = 4;
1112                         /* fall through */
1113                       }
1114
1115                   case 4:
1116                     {
1117                       /* After matching one required iteration, construct a smaller
1118                        * interval and try to match that against the rest.
1119                        *
1120                        * To avoid thwarting unfa caching, instead of building a new
1121                        * rexp node with different interval extents, we keep interval_x
1122                        * in each solns structure to keep track of the number of
1123                        * iterations matched so far.
1124                        */
1125                       solns->right = rx_make_solutions (solns->regs,
1126                                                         solns->verse,
1127                                                         solns->exp,
1128                                                         solns->subexps,
1129                                                         solns->cset_size,
1130                                                         solns->split_guess,
1131                                                         solns->end,
1132                                                         solns->vmfn,
1133                                                         solns->contextfn,
1134                                                         solns->closure);
1135                       solns->right->interval_x = solns->interval_x + 1;
1136                     }
1137                     if (!solns->right)
1138                       {
1139                         rx_free_solutions (solns->left);
1140                         solns->left = 0;
1141                         solns->step = -1;
1142                         return rx_bogus;
1143                       }
1144
1145                     solns->step = 5;
1146                     /* fall through */
1147
1148                   case 5:
1149                   /* interval_try_next_right_match: */
1150
1151                     interval_stat = rx_next_solution (solns->right);
1152                     if (interval_stat == rx_yes)
1153                       {
1154                         solns->final_tag = solns->right->final_tag;
1155                         return interval_stat;
1156                       }
1157                     else if (interval_stat == rx_no)
1158                       {
1159                         rx_free_solutions (solns->right);
1160                         solns->right = 0;
1161                         solns->step = 2;
1162                         goto interval_try_next_left_match;
1163                       }
1164                     else /*  interval_stat == rx_bogus */
1165                       {
1166                         rx_free_solutions (solns->left);
1167                         solns->left = 0;
1168                         rx_free_solutions (solns->right);
1169                         solns->right = 0;
1170                         solns->step = -1;
1171                         return interval_stat;
1172                       }
1173                   }
1174               }
1175
1176             case r_context:
1177               {
1178                 solns->step = -1;
1179                 solns->final_tag = 1;
1180                 return solns->contextfn (solns->closure,
1181                                          solns->exp,
1182                                          solns->start, solns->end,
1183                                          solns->regs);
1184               }
1185
1186
1187             }
1188         }
1189       return rx_bogus;
1190     }
1191 }