home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gnurx.zip / rx / rxanal.c < prev    next >
C/C++ Source or Header  |  1995-12-31  |  18KB  |  780 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. #include "rxall.h"
  28. #include "rxanal.h"
  29. #include "rxbitset.h"
  30.  
  31.  
  32.  
  33.  
  34. #ifdef __STDC__
  35. int
  36. rx_posix_analyze_rexp (struct rexp_node *** subexps,
  37.                int * n_subexps,
  38.                struct rexp_node * node,
  39.                int id)
  40. #else
  41. int
  42. rx_posix_analyze_rexp (subexps, n_subexps, node, id)
  43.      struct rexp_node *** subexps;
  44.      int * n_subexps;
  45.      struct rexp_node * node;
  46.      int id;
  47. #endif
  48. {
  49.   if (node)
  50.     {
  51.       int this_subexp;
  52.       if (node->type == r_parens)
  53.     {
  54.       this_subexp = *n_subexps;
  55.       ++*n_subexps;
  56.       if (!*subexps)
  57.         *subexps = (struct rexp_node **)malloc (sizeof (struct rexp_node *) * *n_subexps);
  58.       else
  59.         *subexps = (struct rexp_node **)realloc (*subexps,
  60.                              sizeof (struct rexp_node *) * *n_subexps);
  61.     }
  62.       if (node->params.pair.left)
  63.     id = rx_posix_analyze_rexp (subexps, n_subexps, node->params.pair.left, id);
  64.       if (node->params.pair.right)
  65.     id = rx_posix_analyze_rexp (subexps, n_subexps, node->params.pair.right, id);
  66.       switch (node->type)
  67.     {
  68.     case r_cset:
  69.       node->len = 1;
  70.       node->observed = 0;
  71.       break;
  72.     case r_concat:
  73.     case r_alternate:
  74.       {
  75.         int lob, rob;
  76.         int llen, rlen;
  77.         lob = (!node->params.pair.left ? 0 : node->params.pair.left->observed);
  78.         rob = (!node->params.pair.right ? 0 : node->params.pair.right->observed);
  79.         llen = (!node->params.pair.left ? 0 : node->params.pair.left->len);
  80.         rlen = (!node->params.pair.right ? 0 : node->params.pair.right->len);
  81.         node->len = ((llen >= 0) && (rlen >= 0)
  82.              ? ((node->type == r_concat)
  83.                 ? llen + rlen
  84.                 : ((llen == rlen) ? llen : -1))
  85.              : -1);
  86.         node->observed = lob || rob;
  87.         break;
  88.       }
  89.     case r_opt:
  90.     case r_star:
  91.     case r_plus:
  92.     case  r_interval:
  93.       node->len = -1;
  94.       node->observed = (node->params.pair.left
  95.                 ? node->params.pair.left->observed
  96.                 : 0);
  97.       break;
  98.     case r_parens:
  99.       node->observed = 1;
  100.       node->len = (node->params.pair.left
  101.                ? node->params.pair.left->len
  102.                : 0);
  103.       (*subexps)[this_subexp] = node;
  104.       break;
  105.     case r_context:
  106.       switch (node->params.intval)
  107.         {
  108.         default:
  109.           node->observed = 1;
  110.           node->len = -1;
  111.           break;
  112.         case '$':
  113.         case '=':
  114.         case '<':
  115.         case '>':
  116.         case 'b':
  117.         case 'B':
  118.         case '`':
  119.         case '\'':
  120.           node->observed = 1;
  121.           node->len = 0;
  122.           break;
  123.         }
  124.       break;
  125.     }
  126.       if (node->observed)
  127.     node->id = id++;
  128.       return id;
  129.     }
  130. }
  131.  
  132. /* Returns 0 unless the pattern can match the empty string. */
  133. #ifdef __STDC__
  134. int
  135. rx_fill_in_fastmap (int cset_size, unsigned char * map, struct rexp_node * exp)
  136. #else
  137. int
  138. rx_fill_in_fastmap (cset_size, map, exp)
  139.      int cset_size;
  140.      unsigned char * map;
  141.      struct rexp_node * exp;
  142. #endif
  143. {
  144.   if (!exp)
  145.     {
  146.     can_match_empty:
  147.       {
  148.     int x;
  149.     for (x = 0; x < cset_size; ++x)
  150.       map[x] = 1;
  151.       }
  152.       return 1;
  153.     }
  154.   
  155.   switch (exp->type)
  156.     {
  157.     case r_cset:
  158.       {
  159.     int x;
  160.     int most;
  161.     
  162.     most = exp->params.cset_size;
  163.     for (x = 0; x < most; ++x)
  164.       if (RX_bitset_member (exp->params.cset, x))
  165.         map[x] = 1;
  166.       }
  167.       return 0;
  168.  
  169.     case r_concat:
  170.       return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
  171.  
  172.       /* Why not the right branch?  If the left branch
  173.        * can't be empty it doesn't matter.  If it can, then
  174.        * the fastmap is already saturated, and again, the
  175.        * right branch doesn't matter.
  176.        */
  177.  
  178.  
  179.     case r_alternate:
  180.       return (  rx_fill_in_fastmap (cset_size, map, exp->params.pair.left)
  181.           | rx_fill_in_fastmap (cset_size, map, exp->params.pair.right));
  182.  
  183.     case r_parens:
  184.     case r_plus:
  185.       return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
  186.  
  187.     case r_opt:
  188.     case r_star:
  189.       goto can_match_empty;
  190.       /* Why not the subtree?  These operators already saturate
  191.        * the fastmap. 
  192.        */
  193.  
  194.     case r_interval:
  195.       if (exp->params.intval == 0)
  196.     goto can_match_empty;
  197.       else
  198.     return rx_fill_in_fastmap (cset_size, map, exp->params.pair.left);
  199.       
  200.     case r_context:
  201.       goto can_match_empty;
  202.     }
  203.  
  204.   /* this should never happen but gcc seems to like it */
  205.   return 0;
  206.   
  207. }
  208.  
  209.  
  210. #ifdef __STDC__
  211. int
  212. rx_is_anchored_p (struct rexp_node * exp)
  213. #else
  214. int
  215. rx_is_anchored_p (exp)
  216.      struct rexp_node * exp;
  217. #endif
  218. {
  219.   if (!exp)
  220.     return 0;
  221.  
  222.   switch (exp->type)
  223.     {
  224.     case r_opt:
  225.     case r_star:
  226.     case r_cset:
  227.       return 0;
  228.  
  229.     case r_parens:
  230.     case r_plus:
  231.     case r_concat:
  232.       return rx_is_anchored_p (exp->params.pair.left);
  233.  
  234.     case r_alternate:
  235.       return (   rx_is_anchored_p (exp->params.pair.left)
  236.           && rx_is_anchored_p (exp->params.pair.right));
  237.  
  238.  
  239.     case r_interval:
  240.       if (exp->params.intval == 0)
  241.     return 0;
  242.       else
  243.     return rx_is_anchored_p (exp->params.pair.left);
  244.       
  245.     case r_context:
  246.       return (exp->params.intval == '^');
  247.     }
  248.  
  249.   /* this should never happen but gcc seems to like it */
  250.   return 0;
  251. }
  252.  
  253.  
  254.  
  255. #ifdef __STDC__
  256. enum rx_answers
  257. rx_start_superstate (struct rx_classical_system * frame)
  258. #else
  259. enum rx_answers
  260. rx_start_superstate (frame)
  261.      struct rx_classical_system * frame;
  262. #endif
  263. {
  264.   struct rx_superset * start_contents;
  265.   struct rx_nfa_state_set * start_nfa_set;
  266.  
  267.   if (frame->state)
  268.     {
  269.       rx_unlock_superstate (frame->rx, frame->state);
  270.       frame->state = 0;
  271.     }
  272.  
  273.   if (   frame->rx->start_set
  274.       && (frame->rx->start_set->starts_for == frame->rx)
  275.       && (frame->rx->start_set->id == frame->rx->rx_id))
  276.     start_contents = frame->rx->start_set;
  277.   else
  278.     {
  279.       {
  280.     struct rx_possible_future * futures;
  281.     futures = rx_state_possible_futures (frame->rx, frame->rx->start_nfa_states);
  282.  
  283.     if (!futures)
  284.       return rx_bogus;
  285.  
  286.     if (futures->next)
  287.       return rx_start_state_with_too_many_futures;
  288.  
  289.     start_nfa_set = futures->destset;
  290.       }
  291.       
  292.       start_contents =
  293.     rx_superstate_eclosure_union (frame->rx,
  294.                       rx_superset_cons (frame->rx, 0, 0),
  295.                       start_nfa_set);
  296.       
  297.       if (!start_contents)
  298.     return rx_bogus;
  299.         
  300.       start_contents->starts_for = frame->rx;
  301.       frame->rx->start_set = start_contents;
  302.     }
  303.  
  304.   if (   start_contents->superstate
  305.       && (start_contents->superstate->rx_id == frame->rx->rx_id))
  306.     {
  307.       frame->state = start_contents->superstate;
  308.       rx_lock_superstate (frame->rx, frame->state);
  309.       return rx_yes;
  310.     }
  311.   else
  312.     {
  313.       rx_protect_superset (frame->rx, start_contents);
  314.       frame->state = rx_superstate (frame->rx, start_contents);
  315.       rx_release_superset (frame->rx, start_contents);
  316.       if (!frame->state)
  317.     return rx_bogus;
  318.       rx_lock_superstate (frame->rx, frame->state);
  319.       return rx_yes;
  320.     }
  321. }
  322.  
  323.  
  324.       
  325.  
  326.  
  327. #ifdef __STDC__
  328. enum rx_answers
  329. rx_match_here_p (struct rx_classical_system * frame,
  330.          unsigned char * burst,
  331.          int len)
  332. #else
  333. enum rx_answers
  334. rx_match_here_p (frame, burst, len)
  335.      struct rx_classical_system * frame;
  336.      unsigned char * burst;
  337.      int len;
  338. #endif
  339. {
  340.   struct rx_inx * inx_table;
  341.  
  342.   if (!frame->state)
  343.     return rx_bogus;
  344.  
  345.   if (!len)
  346.     {
  347.       return (frame->state->contents->is_final
  348.           ? rx_yes
  349.           : rx_maybe);
  350.     }
  351.  
  352.   inx_table = frame->state->transitions;
  353.   rx_unlock_superstate (frame->rx, frame->state);
  354.  
  355.   while (len--)
  356.     {
  357.       struct rx_inx * inx;
  358.       struct rx_inx * next_table;
  359.  
  360.       inx = inx_table + *burst;
  361.       next_table = (struct rx_inx *)inx->data;
  362.       while (!next_table)
  363.     {
  364.       struct rx_superstate * state;
  365.       state = ((struct rx_superstate *)
  366.            ((char *)inx_table
  367.             - ((unsigned long)
  368.                ((struct rx_superstate *)0)->transitions)));
  369.  
  370.       switch ((int)inx->inx)
  371.         {
  372.         case rx_backtrack:
  373.           /* RX_BACKTRACK means that we've reached the empty
  374.            * superstate, indicating that match can't succeed
  375.            * from this point.
  376.            */
  377.           frame->state = 0;
  378.           return rx_no;
  379.         
  380.         case rx_cache_miss:
  381.           /* Because the superstate NFA is lazily constructed,
  382.            * and in fact may erode from underneath us, we sometimes
  383.            * have to construct the next instruction from the hard way.
  384.            * This invokes one step in the lazy-conversion.
  385.            */
  386.           inx = 
  387.         rx_handle_cache_miss
  388.           (frame->rx, state, *burst, inx->data_2);
  389.  
  390.           if (!inx)
  391.         {
  392.           frame->state = 0;
  393.           return rx_bogus;
  394.         }
  395.           next_table = (struct rx_inx *)inx->data;
  396.           continue;
  397.         
  398.  
  399.           /* No other instructions are legal here.
  400.            * (In particular, this function does not handle backtracking
  401.            * or the related instructions.)
  402.            */
  403.         default:
  404.           frame->state = 0;
  405.           return rx_bogus;
  406.       }
  407.     }
  408.       if (inx->data_2)        /* indicates a final superstate */
  409.     {
  410.       frame->state = ((struct rx_superstate *)
  411.               ((char *)inx_table
  412.                - ((unsigned long)
  413.                   ((struct rx_superstate *)0)->transitions)));
  414.       rx_lock_superstate (frame->rx, frame->state);
  415.       return rx_yes;
  416.     }
  417.       inx_table = next_table;
  418.       ++burst;
  419.     }
  420.  
  421.   frame->state = ((struct rx_superstate *)
  422.           ((char *)inx_table
  423.            - ((unsigned long)
  424.               ((struct rx_superstate *)0)->transitions)));
  425.   rx_lock_superstate (frame->rx, frame->state);
  426.   return rx_maybe;
  427. }
  428.  
  429.  
  430.  
  431.  
  432.  
  433. #ifdef __STDC__
  434. enum rx_answers
  435. rx_fit_p (struct rx_classical_system * frame,
  436.          unsigned char * burst,
  437.          int len)
  438. #else
  439. enum rx_answers
  440. rx_fit_p (frame, burst, len)
  441.      struct rx_classical_system * frame;
  442.      unsigned char * burst;
  443.      int len;
  444. #endif
  445. {
  446.   struct rx_inx * inx_table;
  447.   struct rx_inx * inx;
  448.  
  449.   if (!frame->state)
  450.     return rx_bogus;
  451.  
  452.   if (!len)
  453.     {
  454.       return (frame->state->contents->is_final
  455.           ? rx_yes
  456.           : rx_maybe);
  457.     }
  458.  
  459.   inx_table = frame->state->transitions;
  460.   rx_unlock_superstate (frame->rx, frame->state);
  461.  
  462.   while (len--)
  463.     {
  464.       struct rx_inx * next_table;
  465.  
  466.       inx = inx_table + *burst;
  467.       next_table = (struct rx_inx *)inx->data;
  468.       while (!next_table)
  469.     {
  470.       struct rx_superstate * state;
  471.       state = ((struct rx_superstate *)
  472.            ((char *)inx_table
  473.             - ((unsigned long)
  474.                ((struct rx_superstate *)0)->transitions)));
  475.  
  476.       switch ((int)inx->inx)
  477.         {
  478.         case rx_backtrack:
  479.           /* RX_BACKTRACK means that we've reached the empty
  480.            * superstate, indicating that match can't succeed
  481.            * from this point.
  482.            */
  483.           frame->state = 0;
  484.           return rx_no;
  485.         
  486.         case rx_cache_miss:
  487.           /* Because the superstate NFA is lazily constructed,
  488.            * and in fact may erode from underneath us, we sometimes
  489.            * have to construct the next instruction from the hard way.
  490.            * This invokes one step in the lazy-conversion.
  491.            */
  492.           inx = 
  493.         rx_handle_cache_miss
  494.           (frame->rx, state, *burst, inx->data_2);
  495.  
  496.           if (!inx)
  497.         {
  498.           frame->state = 0;
  499.           return rx_bogus;
  500.         }
  501.           next_table = (struct rx_inx *)inx->data;
  502.           continue;
  503.         
  504.  
  505.           /* No other instructions are legal here.
  506.            * (In particular, this function does not handle backtracking
  507.            * or the related instructions.)
  508.            */
  509.         default:
  510.           frame->state = 0;
  511.           return rx_bogus;
  512.       }
  513.     }
  514.       inx_table = next_table;
  515.       ++burst;
  516.     }
  517.  
  518.   if (inx->data_2)        /* indicates a final superstate */
  519.     {
  520.       frame->state = ((struct rx_superstate *)
  521.               ((char *)inx_table
  522.                - ((unsigned long)
  523.               ((struct rx_superstate *)0)->transitions)));
  524.       rx_lock_superstate (frame->rx, frame->state);
  525.       return rx_yes;
  526.     }
  527.   frame->state = ((struct rx_superstate *)
  528.           ((char *)inx_table
  529.            - ((unsigned long)
  530.               ((struct rx_superstate *)0)->transitions)));
  531.   rx_lock_superstate (frame->rx, frame->state);
  532.   return rx_maybe;
  533. }
  534.  
  535.  
  536.  
  537.  
  538.  
  539. #ifdef __STDC__
  540. enum rx_answers
  541. rx_longest (int * last_matched,
  542.         int base_addr,
  543.         struct rx_classical_system * frame,
  544.         unsigned char * burst,
  545.         int len)
  546. #else
  547. enum rx_answers
  548. rx_longest (last_matched, base_addr, frame, burst, len)
  549.      int * last_matched;
  550.      int base_addr;
  551.      struct rx_classical_system * frame;
  552.      unsigned char * burst;
  553.      int len;
  554. #endif
  555. {
  556.   struct rx_inx * inx_table;
  557.   int len_in;
  558.  
  559.   if (!frame->state)
  560.     return rx_bogus;
  561.  
  562.   if (!len)
  563.     {
  564.       if (frame->state->contents->is_final)
  565.     {
  566.       *last_matched = base_addr;
  567.       return rx_yes;
  568.     }
  569.       else
  570.     {
  571.       return rx_maybe;
  572.     }
  573.     }
  574.  
  575.   len_in = len;
  576.   inx_table = frame->state->transitions;
  577.   rx_unlock_superstate (frame->rx, frame->state);
  578.  
  579.   while (len--)
  580.     {
  581.       struct rx_inx * inx;
  582.       struct rx_inx * next_table;
  583.  
  584.       inx = inx_table + *burst;
  585.       next_table = (struct rx_inx *)inx->data;
  586.       while (!next_table)
  587.     {
  588.       struct rx_superstate * state;
  589.       state = ((struct rx_superstate *)
  590.            ((char *)inx_table
  591.             - ((unsigned long)
  592.                ((struct rx_superstate *)0)->transitions)));
  593.  
  594.       switch ((int)inx->inx)
  595.         {
  596.         case rx_backtrack:
  597.           /* RX_BACKTRACK means that we've reached the empty
  598.            * superstate, indicating that match can't succeed
  599.            * from this point.
  600.            */
  601.           frame->state = 0;
  602.           return rx_no;
  603.         
  604.         case rx_cache_miss:
  605.           /* Because the superstate NFA is lazily constructed,
  606.            * and in fact may erode from underneath us, we sometimes
  607.            * have to construct the next instruction from the hard way.
  608.            * This invokes one step in the lazy-conversion.
  609.            */
  610.           inx = 
  611.         rx_handle_cache_miss
  612.           (frame->rx, state, *burst, inx->data_2);
  613.  
  614.           if (!inx)
  615.         {
  616.           frame->state = 0;
  617.           return rx_bogus;
  618.         }
  619.           next_table = (struct rx_inx *)inx->data;
  620.           continue;
  621.         
  622.  
  623.           /* No other instructions are legal here.
  624.            * (In particular, this function does not handle backtracking
  625.            * or the related instructions.)
  626.            */
  627.         default:
  628.           frame->state = 0;
  629.           return rx_bogus;
  630.       }
  631.     }
  632.       if (inx->data_2)        /* indicates a final superstate */
  633.     *last_matched = base_addr + len_in - len;
  634.       inx_table = next_table;
  635.       ++burst;
  636.     }
  637.   
  638.   frame->state = ((struct rx_superstate *)
  639.           ((char *)inx_table
  640.            - ((unsigned long)
  641.               ((struct rx_superstate *)0)->transitions)));
  642.   rx_lock_superstate (frame->rx, frame->state);
  643.   return rx_maybe;
  644. }
  645.  
  646.  
  647.  
  648.  
  649. #ifdef __STDC__
  650. enum rx_answers
  651. rx_advance (struct rx_classical_system * frame,
  652.         unsigned char * burst, int len)
  653. #else
  654. enum rx_answers
  655. rx_advance (frame, burst, len)
  656.      struct rx_classical_system * frame;
  657.      unsigned char * burst;
  658.      int len;
  659. #endif
  660. {
  661.   struct rx_inx * inx_table;
  662.   int len_in;
  663.  
  664.   if (!frame->state)
  665.     return rx_bogus;
  666.  
  667.   if (!len)
  668.     return rx_yes;
  669.  
  670.   inx_table = frame->state->transitions;
  671.   rx_unlock_superstate (frame->rx, frame->state);
  672.  
  673.   while (len--)
  674.     {
  675.       struct rx_inx * inx;
  676.       struct rx_inx * next_table;
  677.  
  678.       inx = inx_table + *burst;
  679.       next_table = (struct rx_inx *)inx->data;
  680.       while (!next_table)
  681.     {
  682.       struct rx_superstate * state;
  683.       state = ((struct rx_superstate *)
  684.            ((char *)inx_table
  685.             - ((unsigned long)
  686.                ((struct rx_superstate *)0)->transitions)));
  687.  
  688.       switch ((int)inx->inx)
  689.         {
  690.         case rx_backtrack:
  691.           /* RX_BACKTRACK means that we've reached the empty
  692.            * superstate, indicating that match can't succeed
  693.            * from this point.
  694.            */
  695.           frame->state = 0;
  696.           return rx_no;
  697.         
  698.         case rx_cache_miss:
  699.           /* Because the superstate NFA is lazily constructed,
  700.            * and in fact may erode from underneath us, we sometimes
  701.            * have to construct the next instruction from the hard way.
  702.            * This invokes one step in the lazy-conversion.
  703.            */
  704.           inx = 
  705.         rx_handle_cache_miss
  706.           (frame->rx, state, *burst, inx->data_2);
  707.  
  708.           if (!inx)
  709.         {
  710.           frame->state = 0;
  711.           return rx_bogus;
  712.         }
  713.           next_table = (struct rx_inx *)inx->data;
  714.           continue;
  715.         
  716.  
  717.           /* No other instructions are legal here.
  718.            * (In particular, this function does not handle backtracking
  719.            * or the related instructions.)
  720.            */
  721.         default:
  722.           frame->state = 0;
  723.           return rx_bogus;
  724.       }
  725.     }
  726.       inx_table = next_table;
  727.       ++burst;
  728.     }
  729.   
  730.   frame->state = ((struct rx_superstate *)
  731.           ((char *)inx_table
  732.            - ((unsigned long)
  733.               ((struct rx_superstate *)0)->transitions)));
  734.   rx_lock_superstate (frame->rx, frame->state);
  735.   return rx_yes;
  736. }
  737.  
  738.  
  739.  
  740. #ifdef __STDC__
  741. void
  742. rx_terminate_system (struct rx_classical_system * frame)
  743. #else
  744. void
  745. rx_terminate_system (frame)
  746.      struct rx_classical_system * frame;
  747. #endif
  748. {
  749.   if (frame->state)
  750.     {
  751.       rx_unlock_superstate (frame->rx, frame->state);
  752.       frame->state = 0;
  753.     }
  754. }
  755.  
  756.  
  757.  
  758.  
  759.  
  760.  
  761.  
  762.  
  763.  
  764. #ifdef __STDC__
  765. void
  766. rx_init_system (struct rx_classical_system * frame, struct rx * rx)
  767. #else
  768. void
  769. rx_init_system (frame, rx)
  770.      struct rx_classical_system * frame;
  771.      struct rx * rx;
  772. #endif
  773. {
  774.   frame->rx = rx;
  775.   frame->state = 0;
  776. }
  777.  
  778.  
  779.  
  780.