home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / rx / rxsuper.c < prev    next >
C/C++ Source or Header  |  1995-12-31  |  38KB  |  1,404 lines
  1. /***********************************************************
  2.  
  3. Copyright 1995 by Tom Lord
  4.  
  5.                         All Rights Reserved
  6.  
  7. Permission to use, copy, modify, and distribute this software and its 
  8. documentation for any purpose and without fee is hereby granted, 
  9. provided that the above copyright notice appear in all copies and that
  10. both that copyright notice and this permission notice appear in 
  11. supporting documentation, and that the name of the copyright holder not be
  12. used in advertising or publicity pertaining to distribution of the
  13. software without specific, written prior permission.  
  14.  
  15. Tom Lord DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
  16. INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
  17. EVENT SHALL TOM LORD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
  18. CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF
  19. USE, DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR
  20. OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
  21. PERFORMANCE OF THIS SOFTWARE.
  22.  
  23. ******************************************************************/
  24.  
  25.  
  26. /*
  27.  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  28.  */
  29.  
  30.  
  31. #include "rxall.h"
  32. #include "rxsuper.h"
  33.  
  34.  
  35.  
  36.  
  37. /* The functions in the next several pages define the lazy-NFA-conversion used
  38.  * by matchers.  The input to this construction is an NFA such as 
  39.  * is built by compactify_nfa (rx.c).  The output is the superNFA.
  40.  */
  41.  
  42. /* Match engines can use arbitrary values for opcodes.  So, the parse tree 
  43.  * is built using instructions names (enum rx_opcode), but the superstate
  44.  * nfa is populated with mystery opcodes (void *).
  45.  *
  46.  * For convenience, here is an id table.  The opcodes are == to their inxs
  47.  *
  48.  * The lables in re_search_2 would make good values for instructions.
  49.  */
  50.  
  51. void * rx_id_instruction_table[rx_num_instructions] =
  52. {
  53.   (void *) rx_backtrack_point,
  54.   (void *) rx_do_side_effects,
  55.   (void *) rx_cache_miss,
  56.   (void *) rx_next_char,
  57.   (void *) rx_backtrack,
  58.   (void *) rx_error_inx
  59. };
  60.  
  61.  
  62.  
  63.  
  64. /* The partially instantiated superstate graph has a transition 
  65.  * table at every node.  There is one entry for every character.
  66.  * This fills in the transition for a set.
  67.  */
  68. #ifdef __STDC__
  69. static void 
  70. install_transition (struct rx_superstate *super,
  71.             struct rx_inx *answer, rx_Bitset trcset) 
  72. #else
  73. static void 
  74. install_transition (super, answer, trcset)
  75.      struct rx_superstate *super;
  76.      struct rx_inx *answer;
  77.      rx_Bitset trcset;
  78. #endif
  79. {
  80.   struct rx_inx * transitions = super->transitions;
  81.   int chr;
  82.   for (chr = 0; chr < 256; )
  83.     if (!*trcset)
  84.       {
  85.     ++trcset;
  86.     chr += 32;
  87.       }
  88.     else
  89.       {
  90.     RX_subset sub = *trcset;
  91.     RX_subset mask = 1;
  92.     int bound = chr + 32;
  93.     while (chr < bound)
  94.       {
  95.         if (sub & mask)
  96.           transitions [chr] = *answer;
  97.         ++chr;
  98.         mask <<= 1;
  99.       }
  100.     ++trcset;
  101.       }
  102. }
  103.  
  104.  
  105. #ifdef __STDC__
  106. static int
  107. qlen (struct rx_superstate * q)
  108. #else
  109. static int
  110. qlen (q)
  111.      struct rx_superstate * q;
  112. #endif
  113. {
  114.   int count = 1;
  115.   struct rx_superstate * it;
  116.   if (!q)
  117.     return 0;
  118.   for (it = q->next_recyclable; it != q; it = it->next_recyclable)
  119.     ++count;
  120.   return count;
  121. }
  122.  
  123. #ifdef __STDC__
  124. static void
  125. check_cache (struct rx_cache * cache)
  126. #else
  127. static void
  128. check_cache (cache)
  129.      struct rx_cache * cache;
  130. #endif
  131. {
  132.   struct rx_cache * you_fucked_up = 0;
  133.   int total = cache->superstates;
  134.   int semi = cache->semifree_superstates;
  135.   if (semi != qlen (cache->semifree_superstate))
  136.     check_cache (you_fucked_up);
  137.   if ((total - semi) != qlen (cache->lru_superstate))
  138.     check_cache (you_fucked_up);
  139. }
  140. #ifdef __STDC__
  141. char *
  142. rx_cache_malloc (struct rx_cache * cache, int size)
  143. #else
  144. char *
  145. rx_cache_malloc (cache, size)
  146.      struct rx_cache * cache;
  147.      int size;
  148. #endif
  149. {
  150.   char * answer;
  151.   answer = (char *)malloc (size);
  152.   if (answer)
  153.     cache->bytes_used += size;
  154.   return answer;
  155. }
  156.  
  157.  
  158. #ifdef __STDC__
  159. void
  160. rx_cache_free (struct rx_cache * cache, int size, char * mem)
  161. #else
  162. void
  163. rx_cache_free (cache, size, mem)
  164.      struct rx_cache * cache;
  165.      int size;
  166.      char * mem;
  167. #endif
  168. {
  169.   free (mem);
  170.   cache->bytes_used -= size;
  171. }
  172.  
  173.  
  174.  
  175. /* When a superstate is old and neglected, it can enter a 
  176.  * semi-free state.  A semi-free state is slated to die.
  177.  * Incoming transitions to a semi-free state are re-written
  178.  * to cause an (interpreted) fault when they are taken.
  179.  * The fault handler revives the semi-free state, patches
  180.  * incoming transitions back to normal, and continues.
  181.  *
  182.  * The idea is basicly to free in two stages, aborting 
  183.  * between the two if the state turns out to be useful again.
  184.  * When a free is aborted, the rescued superstate is placed
  185.  * in the most-favored slot to maximize the time until it
  186.  * is next semi-freed.
  187.  */
  188.  
  189. #ifdef __STDC__
  190. static void
  191. semifree_superstate (struct rx_cache * cache)
  192. #else
  193. static void
  194. semifree_superstate (cache)
  195.      struct rx_cache * cache;
  196. #endif
  197. {
  198.   int disqualified = cache->semifree_superstates;
  199.   if (disqualified == cache->superstates)
  200.     return;
  201.   while (cache->lru_superstate->locks)
  202.     {
  203.       cache->lru_superstate = cache->lru_superstate->next_recyclable;
  204.       ++disqualified;
  205.       if (disqualified == cache->superstates)
  206.     return;
  207.     }
  208.   {
  209.     struct rx_superstate * it = cache->lru_superstate;
  210.     it->next_recyclable->prev_recyclable = it->prev_recyclable;
  211.     it->prev_recyclable->next_recyclable = it->next_recyclable;
  212.     cache->lru_superstate = (it == it->next_recyclable
  213.                  ? 0
  214.                  : it->next_recyclable);
  215.     if (!cache->semifree_superstate)
  216.       {
  217.     cache->semifree_superstate = it;
  218.     it->next_recyclable = it;
  219.     it->prev_recyclable = it;
  220.       }
  221.     else
  222.       {
  223.     it->prev_recyclable = cache->semifree_superstate->prev_recyclable;
  224.     it->next_recyclable = cache->semifree_superstate;
  225.     it->prev_recyclable->next_recyclable = it;
  226.     it->next_recyclable->prev_recyclable = it;
  227.       }
  228.     {
  229.       struct rx_distinct_future *df;
  230.       it->is_semifree = 1;
  231.       ++cache->semifree_superstates;
  232.       df = it->transition_refs;
  233.       if (df)
  234.     {
  235.       df->prev_same_dest->next_same_dest = 0;
  236.       for (df = it->transition_refs; df; df = df->next_same_dest)
  237.         {
  238.           df->future_frame.inx = cache->instruction_table[rx_cache_miss];
  239.           df->future_frame.data = 0;
  240.           df->future_frame.data_2 = (void *) df;
  241.           /* If there are any NEXT-CHAR instruction frames that
  242.            * refer to this state, we convert them to CACHE-MISS frames.
  243.            */
  244.           if (!df->effects
  245.           && (df->edge->options->next_same_super_edge[0]
  246.               == df->edge->options))
  247.         install_transition (df->present, &df->future_frame,
  248.                     df->edge->cset);
  249.         }
  250.       df = it->transition_refs;
  251.       df->prev_same_dest->next_same_dest = df;
  252.     }
  253.     }
  254.   }
  255. }
  256.  
  257.  
  258. #ifdef __STDC__
  259. static void 
  260. refresh_semifree_superstate (struct rx_cache * cache,
  261.                  struct rx_superstate * super)
  262. #else
  263. static void 
  264. refresh_semifree_superstate (cache, super)
  265.      struct rx_cache * cache;
  266.      struct rx_superstate * super;
  267. #endif
  268. {
  269.   struct rx_distinct_future *df;
  270.  
  271.   if (super->transition_refs)
  272.     {
  273.       super->transition_refs->prev_same_dest->next_same_dest = 0; 
  274.       for (df = super->transition_refs; df; df = df->next_same_dest)
  275.     {
  276.       df->future_frame.inx = cache->instruction_table[rx_next_char];
  277.       df->future_frame.data = (void *) super->transitions;
  278.       df->future_frame.data_2 = (void *)(super->contents->is_final);
  279.       /* CACHE-MISS instruction frames that refer to this state,
  280.        * must be converted to NEXT-CHAR frames.
  281.        */
  282.       if (!df->effects
  283.           && (df->edge->options->next_same_super_edge[0]
  284.           == df->edge->options))
  285.         install_transition (df->present, &df->future_frame,
  286.                 df->edge->cset);
  287.     }
  288.       super->transition_refs->prev_same_dest->next_same_dest
  289.     = super->transition_refs;
  290.     }
  291.   if (cache->semifree_superstate == super)
  292.     cache->semifree_superstate = (super->prev_recyclable == super
  293.                   ? 0
  294.                   : super->prev_recyclable);
  295.   super->next_recyclable->prev_recyclable = super->prev_recyclable;
  296.   super->prev_recyclable->next_recyclable = super->next_recyclable;
  297.  
  298.   if (!cache->lru_superstate)
  299.     (cache->lru_superstate
  300.      = super->next_recyclable
  301.      = super->prev_recyclable
  302.      = super);
  303.   else
  304.     {
  305.       super->next_recyclable = cache->lru_superstate;
  306.       super->prev_recyclable = cache->lru_superstate->prev_recyclable;
  307.       super->next_recyclable->prev_recyclable = super;
  308.       super->prev_recyclable->next_recyclable = super;
  309.     }
  310.   super->is_semifree = 0;
  311.   --cache->semifree_superstates;
  312. }
  313.  
  314. #ifdef __STDC__
  315. static void
  316. rx_refresh_this_superstate (struct rx_cache * cache,
  317.                 struct rx_superstate * superstate)
  318. #else
  319. static void
  320. rx_refresh_this_superstate (cache, superstate)
  321.      struct rx_cache * cache;
  322.      struct rx_superstate * superstate;
  323. #endif
  324. {
  325.   if (superstate->is_semifree)
  326.     refresh_semifree_superstate (cache, superstate);
  327.   else if (cache->lru_superstate == superstate)
  328.     cache->lru_superstate = superstate->next_recyclable;
  329.   else if (superstate != cache->lru_superstate->prev_recyclable)
  330.     {
  331.       superstate->next_recyclable->prev_recyclable
  332.     = superstate->prev_recyclable;
  333.       superstate->prev_recyclable->next_recyclable
  334.     = superstate->next_recyclable;
  335.       superstate->next_recyclable = cache->lru_superstate;
  336.       superstate->prev_recyclable = cache->lru_superstate->prev_recyclable;
  337.       superstate->next_recyclable->prev_recyclable = superstate;
  338.       superstate->prev_recyclable->next_recyclable = superstate;
  339.     }
  340. }
  341.  
  342. #ifdef __STDC__
  343. static void 
  344. release_superset_low (struct rx_cache * cache,
  345.              struct rx_superset *set)
  346. #else
  347. static void 
  348. release_superset_low (cache, set)
  349.      struct rx_cache * cache;
  350.      struct rx_superset *set;
  351. #endif
  352. {
  353.   if (!--set->refs)
  354.     {
  355.       if (set->cdr)
  356.     release_superset_low (cache, set->cdr);
  357.  
  358.       set->starts_for = 0;
  359.  
  360.       rx_hash_free (&set->hash_item, &cache->superset_hash_rules);
  361.       rx_cache_free (cache,
  362.              sizeof (struct rx_superset),
  363.              (char *)set);
  364.     }
  365. }
  366.  
  367. #ifdef __STDC__
  368. void 
  369. rx_release_superset (struct rx *rx,
  370.              struct rx_superset *set)
  371. #else
  372. void 
  373. rx_release_superset (rx, set)
  374.      struct rx *rx;
  375.      struct rx_superset *set;
  376. #endif
  377. {
  378.   release_superset_low (rx->cache, set);
  379. }
  380.  
  381. /* This tries to add a new superstate to the superstate freelist.
  382.  * It might, as a result, free some edge pieces or hash tables.
  383.  * If nothing can be freed because too many locks are being held, fail.
  384.  */
  385.  
  386. #ifdef __STDC__
  387. static int
  388. rx_really_free_superstate (struct rx_cache * cache)
  389. #else
  390. static int
  391. rx_really_free_superstate (cache)
  392.      struct rx_cache * cache;
  393. #endif
  394. {
  395.   int locked_superstates = 0;
  396.   struct rx_superstate * it;
  397.  
  398.   if (!cache->superstates)
  399.     return 0;
  400.  
  401.   /* scale these */
  402.   while ((cache->hits + cache->misses) > cache->superstates)
  403.     {
  404.       cache->hits >>= 1;
  405.       cache->misses >>= 1;
  406.     }
  407.  
  408.   /* semifree superstates twice as fast as they are freed
  409.    * so popular states can be rescued.
  410.    */
  411.   semifree_superstate (cache);
  412.   semifree_superstate (cache);
  413.   semifree_superstate (cache);
  414.  
  415. #if 0
  416.   Redundant because semifree_superstate already 
  417.     makes this check;
  418.  
  419.  
  420.   while (cache->semifree_superstate && cache->semifree_superstate->locks)
  421.     {
  422.       refresh_semifree_superstate (cache, cache->semifree_superstate);
  423.       ++locked_superstates;
  424.       if (locked_superstates == cache->superstates)
  425.     return 0;
  426.     }
  427.  
  428.  
  429.   if (cache->semifree_superstate)
  430.     insert the "it =" block which follows this "if 0" code;
  431.   else
  432.     {
  433.       while (cache->lru_superstate->locks)
  434.     {
  435.       cache->lru_superstate = cache->lru_superstate->next_recyclable;
  436.       ++locked_superstates;
  437.       if (locked_superstates == cache->superstates)
  438.         return 0;
  439.     }
  440.       it = cache->lru_superstate;
  441.       it->next_recyclable->prev_recyclable = it->prev_recyclable;
  442.       it->prev_recyclable->next_recyclable = it->next_recyclable;
  443.       cache->lru_superstate = ((it == it->next_recyclable)
  444.                     ? 0
  445.                     : it->next_recyclable);
  446.     }
  447. #endif
  448.  
  449.     if (!cache->semifree_superstate)
  450.       return 0;
  451.  
  452.     {
  453.       it = cache->semifree_superstate;
  454.       it->next_recyclable->prev_recyclable = it->prev_recyclable;
  455.       it->prev_recyclable->next_recyclable = it->next_recyclable;
  456.       cache->semifree_superstate = ((it == it->next_recyclable)
  457.                     ? 0
  458.                     : it->next_recyclable);
  459.       --cache->semifree_superstates;
  460.     }
  461.  
  462.  
  463.   if (it->transition_refs)
  464.     {
  465.       struct rx_distinct_future *df;
  466.       for (df = it->transition_refs,
  467.        df->prev_same_dest->next_same_dest = 0;
  468.        df;
  469.        df = df->next_same_dest)
  470.     {
  471.       df->future_frame.inx = cache->instruction_table[rx_cache_miss];
  472.       df->future_frame.data = 0;
  473.       df->future_frame.data_2 = (void *) df;
  474.       df->future = 0;
  475.     }
  476.       it->transition_refs->prev_same_dest->next_same_dest =
  477.     it->transition_refs;
  478.     }
  479.   {
  480.     struct rx_super_edge *tc = it->edges;
  481.     while (tc)
  482.       {
  483.     struct rx_distinct_future * df;
  484.     struct rx_super_edge *tct = tc->next;
  485.     df = tc->options;
  486.     df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
  487.     while (df)
  488.       {
  489.         struct rx_distinct_future *dft = df;
  490.         df = df->next_same_super_edge[0];
  491.         
  492.         
  493.         if (dft->future && dft->future->transition_refs == dft)
  494.           {
  495.         dft->future->transition_refs = dft->next_same_dest;
  496.         if (dft->future->transition_refs == dft)
  497.           dft->future->transition_refs = 0;
  498.           }
  499.         dft->next_same_dest->prev_same_dest = dft->prev_same_dest;
  500.         dft->prev_same_dest->next_same_dest = dft->next_same_dest;
  501.         rx_cache_free (cache,
  502.                sizeof (struct rx_distinct_future),
  503.                (char *)dft);
  504.       }
  505.     rx_cache_free (cache,
  506.                sizeof (struct rx_super_edge),
  507.                (char *)tc);
  508.     tc = tct;
  509.       }
  510.   }
  511.   
  512.   if (it->contents->superstate == it)
  513.     it->contents->superstate = 0;
  514.   release_superset_low (cache, it->contents);
  515.   rx_cache_free (cache,
  516.          (sizeof (struct rx_superstate)
  517.           + cache->local_cset_size * sizeof (struct rx_inx)),
  518.          (char *)it);
  519.   --cache->superstates;
  520.   return 1;
  521. }
  522.  
  523.  
  524. #ifdef __STDC__
  525. static char *
  526. rx_cache_malloc_or_get (struct rx_cache * cache, int size)
  527. #else
  528. static char *
  529. rx_cache_malloc_or_get (cache, size)
  530.      struct rx_cache * cache;
  531.      int size;
  532. #endif
  533. {
  534.   while (   (cache->bytes_used + size > cache->bytes_allowed)
  535.      && rx_really_free_superstate (cache))
  536.     ;
  537.  
  538.   return rx_cache_malloc (cache, size);
  539. }
  540.  
  541.  
  542.  
  543. #ifdef __STDC__
  544. static int
  545. supersetcmp (void * va, void * vb)
  546. #else
  547. static int
  548. supersetcmp (va, vb)
  549.      void * va;
  550.      void * vb;
  551. #endif
  552. {
  553.   struct rx_superset * a = (struct rx_superset *)va;
  554.   struct rx_superset * b = (struct rx_superset *)vb;
  555.   return (   (a == b)
  556.       || (a && b && (a->id == b->id) && (a->car == b->car) && (a->cdr == b->cdr)));
  557. }
  558.  
  559. #ifdef __STDC__
  560. static struct rx_hash_item *
  561. superset_allocator (struct rx_hash_rules * rules, void * val)
  562. #else
  563. static struct rx_hash_item *
  564. superset_allocator (rules, val)
  565.      struct rx_hash_rules * rules;
  566.      void * val;
  567. #endif
  568. {
  569.   struct rx_cache * cache;
  570.   struct rx_superset * template;
  571.   struct rx_superset * newset;
  572.  
  573.   cache = ((struct rx_cache *)
  574.        ((char *)rules
  575.         - (unsigned long)(&((struct rx_cache *)0)->superset_hash_rules)));
  576.   template = (struct rx_superset *)val;
  577.   newset = ((struct rx_superset *)
  578.         rx_cache_malloc (cache, sizeof (*template)));
  579.   if (!newset)
  580.     return 0;
  581.   newset->refs = 0;
  582.   newset->car = template->car;
  583.   newset->id = template->id;
  584.   newset->cdr = template->cdr;
  585.   newset->is_final = (   template->car->is_final
  586.               || (   template->cdr
  587.               && template->cdr->is_final));
  588.   newset->superstate = 0;
  589.   rx_protect_superset (rx, template->cdr);
  590.   newset->hash_item.data = (void *)newset;
  591.   newset->hash_item.binding = 0;
  592.   return &newset->hash_item;
  593. }
  594.  
  595. #ifdef __STDC__
  596. static struct rx_hash * 
  597. super_hash_allocator (struct rx_hash_rules * rules)
  598. #else
  599. static struct rx_hash * 
  600. super_hash_allocator (rules)
  601.      struct rx_hash_rules * rules;
  602. #endif
  603. {
  604.   struct rx_cache * cache;
  605.   cache = ((struct rx_cache *)
  606.        ((char *)rules
  607.         - (unsigned long)(&((struct rx_cache *)0)->superset_hash_rules)));
  608.   return ((struct rx_hash *)
  609.       rx_cache_malloc (cache, sizeof (struct rx_hash)));
  610. }
  611.  
  612.  
  613. #ifdef __STDC__
  614. static void
  615. super_hash_liberator (struct rx_hash * hash, struct rx_hash_rules * rules)
  616. #else
  617. static void
  618. super_hash_liberator (hash, rules)
  619.      struct rx_hash * hash;
  620.      struct rx_hash_rules * rules;
  621. #endif
  622. {
  623.   struct rx_cache * cache
  624.     = ((struct rx_cache *)
  625.        (char *)rules - (long)(&((struct rx_cache *)0)->superset_hash_rules));
  626.   rx_cache_free (cache, sizeof (struct rx_hash), (char *)hash);
  627. }
  628.  
  629. #ifdef __STDC__
  630. static void
  631. superset_hash_item_liberator (struct rx_hash_item * it,
  632.                   struct rx_hash_rules * rules)
  633. #else
  634. static void
  635. superset_hash_item_liberator (it, rules)
  636.      struct rx_hash_item * it;
  637.      struct rx_hash_rules * rules;
  638. #endif
  639. {
  640. }
  641.  
  642. int rx_cache_bound = 3;
  643. static int rx_default_cache_got = 0;
  644.  
  645. static struct rx_cache default_cache = 
  646. {
  647.   {
  648.     supersetcmp,
  649.     super_hash_allocator,
  650.     super_hash_liberator,
  651.     superset_allocator,
  652.     superset_hash_item_liberator,
  653.   },
  654.   0,
  655.   0,
  656.   0,
  657.   0,
  658.   0,
  659.   0,
  660.   0,
  661.   524288,
  662.   0,
  663.   256,
  664.   rx_id_instruction_table,
  665.   {
  666.     0,
  667.     0,
  668.     0,
  669.     0,
  670.     0
  671.   }
  672. };
  673. struct rx_cache * rx_default_cache = &default_cache;
  674.  
  675. /* This adds an element to a superstate set.  These sets are lists, such
  676.  * that lists with == elements are ==.  The empty set is returned by
  677.  * superset_cons (rx, 0, 0) and is NOT equivelent to 
  678.  * (struct rx_superset)0.
  679.  */
  680.  
  681. #ifdef __STDC__
  682. struct rx_superset *
  683. rx_superset_cons (struct rx * rx,
  684.           struct rx_nfa_state *car, struct rx_superset *cdr)
  685. #else
  686. struct rx_superset *
  687. rx_superset_cons (rx, car, cdr)
  688.      struct rx * rx;
  689.      struct rx_nfa_state *car;
  690.      struct rx_superset *cdr;
  691. #endif
  692. {
  693.   struct rx_cache * cache = rx->cache;
  694.   if (!car && !cdr)
  695.     {
  696.       if (!cache->empty_superset)
  697.     {
  698.       cache->empty_superset
  699.         = ((struct rx_superset *)
  700.            rx_cache_malloc (cache, sizeof (struct rx_superset)));
  701.       if (!cache->empty_superset)
  702.         return 0;
  703.       bzero (cache->empty_superset, sizeof (struct rx_superset));
  704.       cache->empty_superset->refs = 1000;
  705.     }
  706.       return cache->empty_superset;
  707.     }
  708.   {
  709.     struct rx_superset template;
  710.     struct rx_hash_item * hit;
  711.     template.car = car;
  712.     template.cdr = cdr;
  713.     template.id = rx->rx_id;
  714.     hit = rx_hash_store (&cache->superset_table,
  715.              (unsigned long)car ^ car->id ^ (unsigned long)cdr,
  716.              (void *)&template,
  717.              &cache->superset_hash_rules);
  718.     return (hit
  719.         ?  (struct rx_superset *)hit->data
  720.         : 0);
  721.   }
  722. }
  723.  
  724. /* This computes a union of two NFA state sets.  The sets do not have the
  725.  * same representation though.  One is a RX_SUPERSET structure (part
  726.  * of the superstate NFA) and the other is an NFA_STATE_SET (part of the NFA).
  727.  */
  728.  
  729. #ifdef __STDC__
  730. struct rx_superset *
  731. rx_superstate_eclosure_union
  732.   (struct rx * rx, struct rx_superset *set, struct rx_nfa_state_set *ecl) 
  733. #else
  734. struct rx_superset *
  735. rx_superstate_eclosure_union (rx, set, ecl)
  736.      struct rx * rx;
  737.      struct rx_superset *set;
  738.      struct rx_nfa_state_set *ecl;
  739. #endif
  740. {
  741.   if (!ecl)
  742.     return set;
  743.  
  744.   if (!set->car)
  745.     return rx_superset_cons (rx, ecl->car,
  746.                  rx_superstate_eclosure_union (rx, set, ecl->cdr));
  747.   if (set->car == ecl->car)
  748.     return rx_superstate_eclosure_union (rx, set, ecl->cdr);
  749.  
  750.   {
  751.     struct rx_superset * tail;
  752.     struct rx_nfa_state * first;
  753.  
  754.     if (set->car > ecl->car)
  755.       {
  756.     tail = rx_superstate_eclosure_union (rx, set->cdr, ecl);
  757.     first = set->car;
  758.       }
  759.     else
  760.       {
  761.     tail = rx_superstate_eclosure_union (rx, set, ecl->cdr);
  762.     first = ecl->car;
  763.       }
  764.     if (!tail)
  765.       return 0;
  766.     else
  767.       {
  768.     struct rx_superset * answer;
  769.     answer = rx_superset_cons (rx, first, tail);
  770.     if (!answer)
  771.       {
  772.         rx_protect_superset (rx, tail);
  773.         rx_release_superset (rx, tail);
  774.         return 0;
  775.       }
  776.     else
  777.       return answer;
  778.       }
  779.   }
  780. }
  781.  
  782.  
  783.  
  784.  
  785. /*
  786.  * This makes sure that a list of rx_distinct_futures contains
  787.  * a future for each possible set of side effects in the eclosure
  788.  * of a given state.  This is some of the work of filling in a
  789.  * superstate transition. 
  790.  */
  791.  
  792. #ifdef __STDC__
  793. static struct rx_distinct_future *
  794. include_futures (struct rx *rx,
  795.          struct rx_distinct_future *df, struct rx_nfa_state
  796.          *state, struct rx_superstate *superstate) 
  797. #else
  798. static struct rx_distinct_future *
  799. include_futures (rx, df, state, superstate)
  800.      struct rx *rx;
  801.      struct rx_distinct_future *df;
  802.      struct rx_nfa_state *state;
  803.      struct rx_superstate *superstate;
  804. #endif
  805. {
  806.   struct rx_possible_future *future;
  807.   struct rx_cache * cache = rx->cache;
  808.   for (future = rx_state_possible_futures (rx, state); future; future = future->next)
  809.     {
  810.       struct rx_distinct_future *dfp;
  811.       struct rx_distinct_future *insert_before = 0;
  812.       if (df)
  813.     df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
  814.       for (dfp = df; dfp; dfp = dfp->next_same_super_edge[0])
  815.     if (dfp->effects == future->effects)
  816.       break;
  817.     else
  818.       {
  819.         int order = rx->se_list_cmp (rx, dfp->effects, future->effects);
  820.         if (order > 0)
  821.           {
  822.         insert_before = dfp;
  823.         dfp = 0;
  824.         break;
  825.           }
  826.       }
  827.       if (df)
  828.     df->next_same_super_edge[1]->next_same_super_edge[0] = df;
  829.       if (!dfp)
  830.     {
  831.       dfp
  832.         = ((struct rx_distinct_future *)
  833.            rx_cache_malloc (cache,
  834.                 sizeof (struct rx_distinct_future)));
  835.       if (!dfp)
  836.         return 0;
  837.       if (!df)
  838.         {
  839.           df = insert_before = dfp;
  840.           df->next_same_super_edge[0] = df->next_same_super_edge[1] = df;
  841.         }
  842.       else if (!insert_before)
  843.         insert_before = df;
  844.       else if (insert_before == df)
  845.         df = dfp;
  846.  
  847.       dfp->next_same_super_edge[0] = insert_before;
  848.       dfp->next_same_super_edge[1]
  849.         = insert_before->next_same_super_edge[1];
  850.       dfp->next_same_super_edge[1]->next_same_super_edge[0] = dfp;
  851.       dfp->next_same_super_edge[0]->next_same_super_edge[1] = dfp;
  852.       dfp->next_same_dest = dfp->prev_same_dest = dfp;
  853.       dfp->future = 0;
  854.       dfp->present = superstate;
  855.       dfp->future_frame.inx = rx->instruction_table[rx_cache_miss];
  856.       dfp->future_frame.data = 0;
  857.       dfp->future_frame.data_2 = (void *) dfp;
  858.       dfp->side_effects_frame.inx
  859.         = rx->instruction_table[rx_do_side_effects];
  860.       dfp->side_effects_frame.data = 0;
  861.       dfp->side_effects_frame.data_2 = (void *) dfp;
  862.       dfp->effects = future->effects;
  863.     }
  864.     }
  865.   return df;
  866. }
  867.  
  868.  
  869.  
  870. /* This constructs a new superstate from its state set.  The only 
  871.  * complexity here is memory management.
  872.  */
  873. #ifdef __STDC__
  874. struct rx_superstate *
  875. rx_superstate (struct rx *rx,
  876.            struct rx_superset *set)
  877. #else
  878. struct rx_superstate *
  879. rx_superstate (rx, set)
  880.      struct rx *rx;
  881.      struct rx_superset *set;
  882. #endif
  883. {
  884.   struct rx_cache * cache = rx->cache;
  885.   struct rx_superstate * superstate = 0;
  886.  
  887.   /* Does the superstate already exist in the cache? */
  888.   if (set->superstate)
  889.     {
  890.       if (set->superstate->rx_id != rx->rx_id)
  891.     {
  892.       /* Aha.  It is in the cache, but belongs to a superstate
  893.        * that refers to an NFA that no longer exists.
  894.        * (We know it no longer exists because it was evidently
  895.        *  stored in the same region of memory as the current nfa
  896.        *  yet it has a different id.)
  897.        */
  898.       superstate = set->superstate;
  899.       if (!superstate->is_semifree)
  900.         {
  901.           if (cache->lru_superstate == superstate)
  902.         {
  903.           cache->lru_superstate = superstate->next_recyclable;
  904.           if (cache->lru_superstate == superstate)
  905.             cache->lru_superstate = 0;
  906.         }
  907.           {
  908.         superstate->next_recyclable->prev_recyclable
  909.           = superstate->prev_recyclable;
  910.         superstate->prev_recyclable->next_recyclable
  911.           = superstate->next_recyclable;
  912.         if (!cache->semifree_superstate)
  913.           {
  914.             (cache->semifree_superstate
  915.              = superstate->next_recyclable
  916.              = superstate->prev_recyclable
  917.              = superstate);
  918.           }
  919.         else
  920.           {
  921.             superstate->next_recyclable = cache->semifree_superstate;
  922.             superstate->prev_recyclable
  923.               = cache->semifree_superstate->prev_recyclable;
  924.             superstate->next_recyclable->prev_recyclable
  925.               = superstate;
  926.             superstate->prev_recyclable->next_recyclable
  927.               = superstate;
  928.             cache->semifree_superstate = superstate;
  929.           }
  930.         ++cache->semifree_superstates;
  931.           }
  932.         }
  933.       set->superstate = 0;
  934.       goto handle_cache_miss;
  935.     }
  936.       ++cache->hits;
  937.       superstate = set->superstate;
  938.  
  939.       rx_refresh_this_superstate (cache, superstate);
  940.       return superstate;
  941.     }
  942.  
  943.  handle_cache_miss:
  944.  
  945.   /* This point reached only for cache misses. */
  946.   ++cache->misses;
  947. #if RX_DEBUG
  948.   if (rx_debug_trace > 1)
  949.     {
  950.       struct rx_superset * setp = set;
  951.       fprintf (stderr, "Building a superstet %d(%d): ", rx->rx_id, set);
  952.       while (setp)
  953.     {
  954.       fprintf (stderr, "%d ", setp->id);
  955.       setp = setp->cdr;
  956.     }
  957.       fprintf (stderr, "(%d)\n", set);
  958.     }
  959. #endif
  960.  
  961.   {
  962.     int superstate_size;
  963.     superstate_size = (  sizeof (*superstate)
  964.                + (  sizeof (struct rx_inx)
  965.               * rx->local_cset_size));
  966.     superstate = ((struct rx_superstate *)
  967.           rx_cache_malloc_or_get (cache, superstate_size));
  968.     ++cache->superstates;
  969.   }                                   
  970.  
  971.   if (!superstate)
  972.     return 0;
  973.  
  974.   if (!cache->lru_superstate)
  975.     (cache->lru_superstate
  976.      = superstate->next_recyclable
  977.      = superstate->prev_recyclable
  978.      = superstate);
  979.   else
  980.     {
  981.       superstate->next_recyclable = cache->lru_superstate;
  982.       superstate->prev_recyclable = cache->lru_superstate->prev_recyclable;
  983.       (  superstate->prev_recyclable->next_recyclable
  984.        = superstate->next_recyclable->prev_recyclable
  985.        = superstate);
  986.     }
  987.   superstate->rx_id = rx->rx_id;
  988.   superstate->transition_refs = 0;
  989.   superstate->locks = 0;
  990.   superstate->is_semifree = 0;
  991.   set->superstate = superstate;
  992.   superstate->contents = set;
  993.   rx_protect_superset (rx, set);
  994.   superstate->edges = 0;
  995.   {
  996.     int x;
  997.     /* None of the transitions from this superstate are known yet. */
  998.     for (x = 0; x < rx->local_cset_size; ++x) /* &&&&& 3.8 % */
  999.       {
  1000.     struct rx_inx * ifr = &superstate->transitions[x];
  1001.     ifr->inx = rx->instruction_table [rx_cache_miss];
  1002.     ifr->data = ifr->data_2 = 0;
  1003.       }
  1004.   }
  1005.   return superstate;
  1006. }
  1007.  
  1008.  
  1009. /* This computes the destination set of one edge of the superstate NFA.
  1010.  * Note that a RX_DISTINCT_FUTURE is a superstate edge.
  1011.  * Returns 0 on an allocation failure.
  1012.  */
  1013.  
  1014. #ifdef __STDC__
  1015. static int 
  1016. solve_destination (struct rx *rx, struct rx_distinct_future *df)
  1017. #else
  1018. static int 
  1019. solve_destination (rx, df)
  1020.      struct rx *rx;
  1021.      struct rx_distinct_future *df;
  1022. #endif
  1023. {
  1024.   struct rx_super_edge *tc = df->edge;
  1025.   struct rx_superset *nfa_state;
  1026.   struct rx_superset *nil_set = rx_superset_cons (rx, 0, 0);
  1027.   struct rx_superset *solution = nil_set;
  1028.   struct rx_superstate *dest;
  1029.  
  1030.   rx_protect_superset (rx, solution);
  1031.   /* Iterate over all NFA states in the state set of this superstate. */
  1032.   for (nfa_state = df->present->contents;
  1033.        nfa_state->car;
  1034.        nfa_state = nfa_state->cdr)
  1035.     {
  1036.       struct rx_nfa_edge *e;
  1037.       /* Iterate over all edges of each NFA state. */
  1038.       for (e = nfa_state->car->edges; e; e = e->next)
  1039.         /* If we find an edge that is labeled with 
  1040.      * the characters we are solving for.....
  1041.      */
  1042.     if ((e->type == ne_cset)
  1043.         && rx_bitset_is_subset (rx->local_cset_size,
  1044.                     tc->cset,
  1045.                     e->params.cset))
  1046.       {
  1047.         struct rx_nfa_state *n = e->dest;
  1048.         struct rx_possible_future *pf;
  1049.         /* ....search the partial epsilon closures of the destination
  1050.          * of that edge for a path that involves the same set of
  1051.          * side effects we are solving for.
  1052.          * If we find such a RX_POSSIBLE_FUTURE, we add members to the
  1053.          * stateset we are computing.
  1054.          */
  1055.         for (pf = rx_state_possible_futures (rx, n); pf; pf = pf->next)
  1056.           if (pf->effects == df->effects)
  1057.         {
  1058.           struct rx_superset * old_sol;
  1059.           old_sol = solution;
  1060.           solution = rx_superstate_eclosure_union (rx, solution,
  1061.                                pf->destset);
  1062.           if (!solution)
  1063.             return 0;
  1064.           rx_protect_superset (rx, solution);
  1065.           rx_release_superset (rx, old_sol);
  1066.         }
  1067.       }
  1068.     }
  1069.   /* It is possible that the RX_DISTINCT_FUTURE we are working on has 
  1070.    * the empty set of NFA states as its definition.  In that case, this
  1071.    * is a failure point.
  1072.    */
  1073.   if (solution == nil_set)
  1074.     {
  1075.       df->future_frame.inx = (void *) rx_backtrack;
  1076.       df->future_frame.data = 0;
  1077.       df->future_frame.data_2 = 0;
  1078.       return 1;
  1079.     }
  1080.   dest = rx_superstate (rx, solution);
  1081.   rx_release_superset (rx, solution);
  1082.   if (!dest)
  1083.     return 0;
  1084.  
  1085.   {
  1086.     struct rx_distinct_future *dft;
  1087.     dft = df;
  1088.     df->prev_same_dest->next_same_dest = 0;
  1089.     while (dft)
  1090.       {
  1091.     dft->future = dest;
  1092.     dft->future_frame.inx = rx->instruction_table[rx_next_char];
  1093.     dft->future_frame.data = (void *) dest->transitions;
  1094.     dft->future_frame.data_2 = (void *) dest->contents->is_final;
  1095.     dft = dft->next_same_dest;
  1096.       }
  1097.     df->prev_same_dest->next_same_dest = df;
  1098.   }
  1099.   if (!dest->transition_refs)
  1100.     dest->transition_refs = df;
  1101.   else
  1102.     {
  1103.       struct rx_distinct_future *dft = dest->transition_refs->next_same_dest;
  1104.       dest->transition_refs->next_same_dest = df->next_same_dest;
  1105.       df->next_same_dest->prev_same_dest = dest->transition_refs;
  1106.       df->next_same_dest = dft;
  1107.       dft->prev_same_dest = df;
  1108.     }
  1109.   return 1;
  1110. }
  1111.  
  1112.  
  1113. /* This takes a superstate and a character, and computes some edges
  1114.  * from the superstate NFA.  In particular, this computes all edges
  1115.  * that lead from SUPERSTATE given CHR.   This function also 
  1116.  * computes the set of characters that share this edge set.
  1117.  * This returns 0 on allocation error.
  1118.  * The character set and list of edges are returned through 
  1119.  * the paramters CSETOUT and DFOUT.
  1120. } */
  1121.  
  1122. #ifdef __STDC__
  1123. static int 
  1124. compute_super_edge (struct rx *rx, struct rx_distinct_future **dfout,
  1125.               rx_Bitset csetout, struct rx_superstate *superstate,
  1126.               unsigned char chr)  
  1127. #else
  1128. static int 
  1129. compute_super_edge (rx, dfout, csetout, superstate, chr)
  1130.      struct rx *rx;
  1131.      struct rx_distinct_future **dfout;
  1132.      rx_Bitset csetout;
  1133.      struct rx_superstate *superstate;
  1134.      unsigned char chr;
  1135. #endif
  1136. {
  1137.   struct rx_superset *stateset = superstate->contents;
  1138.  
  1139.   /* To compute the set of characters that share edges with CHR, 
  1140.    * we start with the full character set, and subtract.
  1141.    */
  1142.   rx_bitset_universe (rx->local_cset_size, csetout);
  1143.   *dfout = 0;
  1144.  
  1145.   /* Iterate over the NFA states in the superstate state-set. */
  1146.   while (stateset->car)
  1147.     {
  1148.       struct rx_nfa_edge *e;
  1149.       for (e = stateset->car->edges; e; e = e->next)
  1150.     if (e->type == ne_cset)
  1151.       {
  1152.         if (!RX_bitset_member (e->params.cset, chr))
  1153.           /* An edge that doesn't apply at least tells us some characters
  1154.            * that don't share the same edge set as CHR.
  1155.            */
  1156.           rx_bitset_difference (rx->local_cset_size, csetout, e->params.cset);
  1157.         else
  1158.           {
  1159.         /* If we find an NFA edge that applies, we make sure there
  1160.          * are corresponding edges in the superstate NFA.
  1161.          */
  1162.         {
  1163.           struct rx_distinct_future * saved;
  1164.           saved = *dfout;
  1165.           *dfout = include_futures (rx, *dfout, e->dest, superstate);
  1166.           if (!*dfout)
  1167.             {
  1168.               struct rx_distinct_future * df;
  1169.               df = saved;
  1170.               if (df)
  1171.             df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
  1172.               while (df)
  1173.             {
  1174.               struct rx_distinct_future *dft;
  1175.               dft = df;
  1176.               df = df->next_same_super_edge[0];
  1177.  
  1178.               if (dft->future && dft->future->transition_refs == dft)
  1179.                 {
  1180.                   dft->future->transition_refs = dft->next_same_dest;
  1181.                   if (dft->future->transition_refs == dft)
  1182.                 dft->future->transition_refs = 0;
  1183.                 }
  1184.               dft->next_same_dest->prev_same_dest = dft->prev_same_dest;
  1185.               dft->prev_same_dest->next_same_dest = dft->next_same_dest;
  1186.               rx_cache_free (rx->cache, sizeof (*dft), (char *)dft);
  1187.             }
  1188.               return 0;
  1189.             }
  1190.         }
  1191.         /* We also trim the character set a bit. */
  1192.         rx_bitset_intersection (rx->local_cset_size,
  1193.                     csetout, e->params.cset);
  1194.           }
  1195.       }
  1196.       stateset = stateset->cdr;
  1197.     }
  1198.   return 1;
  1199. }
  1200.  
  1201.  
  1202. /* This is a constructor for RX_SUPER_EDGE structures.  These are
  1203.  * wrappers for lists of superstate NFA edges that share character sets labels.
  1204.  * If a transition class contains more than one rx_distinct_future (superstate
  1205.  * edge), then it represents a non-determinism in the superstate NFA.
  1206.  */
  1207.  
  1208. #ifdef __STDC__
  1209. static struct rx_super_edge *
  1210. rx_super_edge (struct rx *rx,
  1211.            struct rx_superstate *super, rx_Bitset cset,
  1212.            struct rx_distinct_future *df) 
  1213. #else
  1214. static struct rx_super_edge *
  1215. rx_super_edge (rx, super, cset, df)
  1216.      struct rx *rx;
  1217.      struct rx_superstate *super;
  1218.      rx_Bitset cset;
  1219.      struct rx_distinct_future *df;
  1220. #endif
  1221. {
  1222.   struct rx_super_edge *tc;
  1223.   int tc_size;
  1224.  
  1225.   tc_size = (  sizeof (struct rx_super_edge)
  1226.          + rx_sizeof_bitset (rx->local_cset_size));
  1227.  
  1228.   tc = ((struct rx_super_edge *)
  1229.     rx_cache_malloc (rx->cache, tc_size));
  1230.  
  1231.   if (!tc)
  1232.     return 0;
  1233.  
  1234.   tc->next = super->edges;
  1235.   super->edges = tc;
  1236.   tc->rx_backtrack_frame.inx = rx->instruction_table[rx_backtrack_point];
  1237.   tc->rx_backtrack_frame.data = 0;
  1238.   tc->rx_backtrack_frame.data_2 = (void *) tc;
  1239.   tc->options = df;
  1240.   tc->cset = (rx_Bitset) ((char *) tc + sizeof (*tc));
  1241.   rx_bitset_assign (rx->local_cset_size, tc->cset, cset);
  1242.   if (df)
  1243.     {
  1244.       struct rx_distinct_future * dfp = df;
  1245.       df->next_same_super_edge[1]->next_same_super_edge[0] = 0;
  1246.       while (dfp)
  1247.     {
  1248.       dfp->edge = tc;
  1249.       dfp = dfp->next_same_super_edge[0];
  1250.     }
  1251.       df->next_same_super_edge[1]->next_same_super_edge[0] = df;
  1252.     }
  1253.   return tc;
  1254. }
  1255.  
  1256.  
  1257. /* There are three kinds of cache miss.  The first occurs when a
  1258.  * transition is taken that has never been computed during the
  1259.  * lifetime of the source superstate.  That cache miss is handled by
  1260.  * calling COMPUTE_SUPER_EDGE.  The second kind of cache miss
  1261.  * occurs when the destination superstate of a transition doesn't
  1262.  * exist.  SOLVE_DESTINATION is used to construct the destination superstate.
  1263.  * Finally, the third kind of cache miss occurs when the destination
  1264.  * superstate of a transition is in a `semi-free state'.  That case is
  1265.  * handled by UNFREE_SUPERSTATE.
  1266.  *
  1267.  * The function of HANDLE_CACHE_MISS is to figure out which of these
  1268.  * cases applies.
  1269.  */
  1270.  
  1271. #ifdef __STDC__
  1272. static void
  1273. install_partial_transition  (struct rx_superstate *super,
  1274.                  struct rx_inx *answer,
  1275.                  RX_subset set, int offset)
  1276. #else
  1277. static void
  1278. install_partial_transition  (super, answer, set, offset)
  1279.      struct rx_superstate *super;
  1280.      struct rx_inx *answer;
  1281.      RX_subset set;
  1282.      int offset;
  1283. #endif
  1284. {
  1285.   int start = offset;
  1286.   int end = start + 32;
  1287.   RX_subset pos = 1;
  1288.   struct rx_inx * transitions = super->transitions;
  1289.   
  1290.   while (start < end)
  1291.     {
  1292.       if (set & pos)
  1293.     transitions[start] = *answer;
  1294.       pos <<= 1;
  1295.       ++start;
  1296.     }
  1297. }
  1298.  
  1299.  
  1300. #ifdef __STDC__
  1301. struct rx_inx *
  1302. rx_handle_cache_miss
  1303.   (struct rx *rx, struct rx_superstate *super, unsigned char chr, void *data) 
  1304. #else
  1305. struct rx_inx *
  1306. rx_handle_cache_miss (rx, super, chr, data)
  1307.      struct rx *rx;
  1308.      struct rx_superstate *super;
  1309.      unsigned char chr;
  1310.      void *data;
  1311. #endif
  1312. {
  1313.   int offset = chr / RX_subset_bits;
  1314.   struct rx_distinct_future *df = data;
  1315.  
  1316.   if (!df)            /* must be the shared_cache_miss_frame */
  1317.     {
  1318.       /* Perhaps this is just a transition waiting to be filled. */
  1319.       struct rx_super_edge *tc;
  1320.       RX_subset mask = rx_subset_singletons [chr % RX_subset_bits];
  1321.  
  1322.       for (tc = super->edges; tc; tc = tc->next)
  1323.     if (tc->cset[offset] & mask)
  1324.       {
  1325.         struct rx_inx * answer;
  1326.         df = tc->options;
  1327.         answer = ((tc->options->next_same_super_edge[0] != tc->options)
  1328.               ? &tc->rx_backtrack_frame
  1329.               : (df->effects
  1330.              ? &df->side_effects_frame
  1331.              : &df->future_frame));
  1332.         install_partial_transition (super, answer,
  1333.                     tc->cset [offset], offset * 32);
  1334.         return answer;
  1335.       }
  1336.       /* Otherwise, it's a flushed or  newly encountered edge. */
  1337.       {
  1338.     char cset_space[1024];    /* this limit is far from unreasonable */
  1339.     rx_Bitset trcset;
  1340.     struct rx_inx *answer;
  1341.  
  1342.     if (rx_sizeof_bitset (rx->local_cset_size) > sizeof (cset_space))
  1343.       return 0;        /* If the arbitrary limit is hit, always fail */
  1344.                 /* cleanly. */
  1345.     trcset = (rx_Bitset)cset_space;
  1346.     rx_lock_superstate (rx, super);
  1347.     if (!compute_super_edge (rx, &df, trcset, super, chr))
  1348.       {
  1349.         rx_unlock_superstate (rx, super);
  1350.         return 0;
  1351.       }
  1352.     if (!df)        /* We just computed the fail transition. */
  1353.       {
  1354.         static struct rx_inx
  1355.           shared_fail_frame = { 0, 0, (void *)rx_backtrack, 0 };
  1356.         answer = &shared_fail_frame;
  1357.       }
  1358.     else
  1359.       {
  1360.         tc = rx_super_edge (rx, super, trcset, df);
  1361.         if (!tc)
  1362.           {
  1363.         rx_unlock_superstate (rx, super);
  1364.         return 0;
  1365.           }
  1366.         answer = ((tc->options->next_same_super_edge[0] != tc->options)
  1367.               ? &tc->rx_backtrack_frame
  1368.               : (df->effects
  1369.              ? &df->side_effects_frame
  1370.              : &df->future_frame));
  1371.       }
  1372.     install_partial_transition (super, answer,
  1373.                     trcset[offset], offset * 32);
  1374.     rx_unlock_superstate (rx, super);
  1375.     return answer;
  1376.       }
  1377.     }
  1378.   else if (df->future) /* A cache miss on an edge with a future? Must be
  1379.             * a semi-free destination. */
  1380.     {                
  1381.       if (df->future->is_semifree)
  1382.     refresh_semifree_superstate (rx->cache, df->future);
  1383.       return &df->future_frame;
  1384.     }
  1385.   else
  1386.     /* no future superstate on an existing edge */
  1387.     {
  1388.       rx_lock_superstate (rx, super);
  1389.       if (!solve_destination (rx, df))
  1390.     {
  1391.       rx_unlock_superstate (rx, super);
  1392.       return 0;
  1393.     }
  1394.       if (!df->effects
  1395.       && (df->edge->options->next_same_super_edge[0] == df->edge->options))
  1396.     install_partial_transition (super, &df->future_frame,
  1397.                     df->edge->cset[offset], offset * 32);
  1398.       rx_unlock_superstate (rx, super);
  1399.       return &df->future_frame;
  1400.     }
  1401. }
  1402.  
  1403.  
  1404.