home *** CD-ROM | disk | FTP | other *** search
/ Acorn User 11 / AUCD11B.iso / LANGUAGES / WraithSet / AwkStuff / MawkSrc / rexp / c / rexp3 < prev    next >
Text File  |  1993-07-24  |  7KB  |  340 lines
  1.  
  2. /********************************************
  3. rexp3.c
  4. copyright 1991, Michael D. Brennan
  5.  
  6. This is a source file for mawk, an implementation of
  7. the AWK programming language.
  8.  
  9. Mawk is distributed without warranty under the terms of
  10. the GNU General Public License, version 2, 1991.
  11. ********************************************/
  12.  
  13. /*$Log: rexp3.c,v $
  14.  * Revision 1.3  1993/07/24  17:55:15  mike
  15.  * more cleanup
  16.  *
  17.  * Revision 1.2     1993/07/23  13:21:48  mike
  18.  * cleanup rexp code
  19.  *
  20.  * Revision 1.1.1.1  1993/07/03     18:58:28  mike
  21.  * move source to cvs
  22.  *
  23.  * Revision 3.6     1992/12/24  00:44:53  mike
  24.  * fixed potential LMDOS bozo with M_STR+U_ON+END_ON
  25.  * fixed minor bug in M_CLASS+U_ON+END_ON
  26.  *
  27.  * Revision 3.5     1992/01/21  17:33:20  brennan
  28.  * added some casts so that character classes work with signed chars
  29.  *
  30.  * Revision 3.4     91/10/29  10:54:09  brennan
  31.  * SIZE_T
  32.  *
  33.  * Revision 3.3     91/08/13  09:10:18  brennan
  34.  * VERSION .9994
  35.  *
  36.  * Revision 3.2     91/06/10  16:18:17  brennan
  37.  * changes for V7
  38.  *
  39.  * Revision 3.1     91/06/07  10:33:28  brennan
  40.  * VERSION 0.995
  41.  *
  42.  * Revision 1.4     91/05/31  10:56:32  brennan
  43.  * stack_empty hack for DOS large model
  44.  *
  45. */
  46.  
  47. /*  match a string against a machine   */
  48.  
  49. #include "rexp.h"
  50.  
  51.  
  52.  
  53. extern RT_STATE *RE_run_stack_base ;
  54. extern RT_STATE *RE_run_stack_limit ;
  55. extern RT_STATE *RE_run_stack_empty ;
  56.  
  57. RT_STATE *RE_new_run_stack() ;
  58.  
  59.  
  60. #define     push(mx,sx,ssx,ux)   if (++stackp == RE_run_stack_limit)\
  61.                 stackp = RE_new_run_stack() ;\
  62. stackp->m=(mx);stackp->s=(sx);stackp->ss=(ssx);\
  63. stackp->u = (ux)
  64.  
  65.  
  66. #define      CASE_UANY(x)    case  x + U_OFF :  case     x + U_ON
  67.  
  68. /* returns start of first longest match and the length by
  69.    reference.  If no match returns NULL and length zero */
  70.  
  71.    char *REmatch(str, machine, lenp)
  72.    char *str ;
  73.    PTR machine ;
  74.    unsigned *lenp ;
  75. {
  76.    register STATE *m = (STATE *) machine ;
  77.    register char *s = str ;
  78.    char *ss ;
  79.    register RT_STATE *stackp ;
  80.    int u_flag, t ;
  81.    char *str_end, *ts ;
  82.  
  83.    /* state of current best match stored here */
  84.    char *cb_ss ;         /* the start */
  85.    char *cb_e ;             /* the end , pts at first char not matched */
  86.  
  87.    *lenp = 0 ;
  88.  
  89.    /* check for the easy case */
  90.    if ((m + 1)->type == M_ACCEPT && m->type == M_STR)
  91.    {
  92.       if (ts = str_str(s, m->data.str, m->len))     *lenp = m->len ;
  93.       return ts ;
  94.    }
  95.  
  96.    u_flag = U_ON ; cb_ss = ss = str_end = (char *) 0 ;
  97.    stackp = RE_run_stack_empty ;
  98.    goto reswitch ;
  99.  
  100. refill :
  101.    if (stackp == RE_run_stack_empty)
  102.    {
  103.       if (cb_ss)  *lenp = cb_e - cb_ss ;
  104.       return cb_ss ;
  105.    }
  106.    ss = stackp->ss ;
  107.    s = stackp--->s ;
  108.    if (cb_ss)            /* does new state start too late ? */
  109.    {
  110.       if (ss)
  111.       {
  112.      if (cb_ss < ss)  goto refill ;
  113.       }
  114.       else if (cb_ss < s)  goto refill ;
  115.    }
  116.  
  117.    m = (stackp + 1)->m ;
  118.    u_flag = (stackp + 1)->u ;
  119.  
  120.  
  121. reswitch  :
  122.  
  123.    switch (m->type + u_flag)
  124.    {
  125.       case M_STR + U_OFF + END_OFF:
  126.      if (strncmp(s, m->data.str, m->len))  goto refill ;
  127.      if (!ss)
  128.      {
  129.         if (cb_ss && s > cb_ss)  goto refill ;
  130.         else  ss = s ;
  131.      }
  132.      s += m->len ;    m++ ;
  133.      goto reswitch ;
  134.  
  135.       case M_STR + U_OFF + END_ON:
  136.      if (strcmp(s, m->data.str))  goto refill ;
  137.      if (!ss)
  138.      {
  139.         if (cb_ss && s > cb_ss)  goto refill ;
  140.         else  ss = s ;
  141.      }
  142.      s += m->len ;    m++ ;
  143.      goto reswitch ;
  144.  
  145.       case M_STR + U_ON + END_OFF:
  146.      if (!(s = str_str(s, m->data.str, m->len)))  goto refill ;
  147.      push(m, s + 1, ss, U_ON) ;
  148.      if (!ss)
  149.      {
  150.         if (cb_ss && s > cb_ss)  goto refill ;
  151.         else  ss = s ;
  152.      }
  153.      s += m->len ; m++ ; u_flag = U_OFF ;
  154.      goto reswitch ;
  155.  
  156.       case M_STR + U_ON + END_ON:
  157.      if (!str_end)    str_end = s + strlen(s) ;
  158.      t = (str_end - s) - m->len ;
  159.      if (t < 0 || memcmp(ts = s + t, m->data.str, m->len))
  160.         goto refill ;
  161.      if (!ss)
  162.      {
  163.         if (cb_ss && ts > cb_ss)  goto refill ;
  164.         else  ss = ts ;
  165.      }
  166.      s = str_end ; m++ ; u_flag = U_OFF ;
  167.      goto reswitch ;
  168.  
  169.       case M_CLASS + U_OFF + END_OFF:
  170.      if (!ison(*m->data.bvp, s[0]))     goto refill ;
  171.      if (!ss)
  172.      {
  173.         if (cb_ss && s > cb_ss)  goto refill ;
  174.         else  ss = s ;
  175.      }
  176.      s++ ; m++ ;
  177.      goto reswitch ;
  178.  
  179.       case M_CLASS + U_OFF + END_ON:
  180.      if (s[1] || !ison(*m->data.bvp, s[0]))     goto refill ;
  181.      if (!ss)
  182.      {
  183.         if (cb_ss && s > cb_ss)  goto refill ;
  184.         else  ss = s ;
  185.      }
  186.      s++ ; m++ ;
  187.      goto reswitch ;
  188.  
  189.       case M_CLASS + U_ON + END_OFF:
  190.      while (!ison(*m->data.bvp, s[0]))
  191.      {
  192.         if (s[0] == 0)  goto refill ;
  193.         else  s++ ;
  194.      }
  195.      s++ ;
  196.      push(m, s, ss, U_ON) ;
  197.      if (!ss)
  198.      {
  199.         if (cb_ss && s - 1 > cb_ss)     goto refill ;
  200.         else  ss = s - 1 ;
  201.      }
  202.      m++ ; u_flag = U_OFF ;
  203.      goto reswitch ;
  204.  
  205.       case M_CLASS + U_ON + END_ON:
  206.      if (!str_end)    str_end = s + strlen(s) ;
  207.      if (s[0] == 0 || !ison(*m->data.bvp, str_end[-1]))
  208.         goto refill ;
  209.      if (!ss)
  210.      {
  211.         if (cb_ss && str_end - 1 > cb_ss)  goto refill ;
  212.         else  ss = str_end - 1 ;
  213.      }
  214.      s = str_end ; m++ ; u_flag = U_OFF ;
  215.      goto reswitch ;
  216.  
  217.       case M_ANY + U_OFF + END_OFF:
  218.      if (s[0] == 0)     goto refill ;
  219.      if (!ss)
  220.      {
  221.         if (cb_ss && s > cb_ss)  goto refill ;
  222.         else  ss = s ;
  223.      }
  224.      s++ ; m++ ;
  225.      goto reswitch ;
  226.  
  227.       case M_ANY + U_OFF + END_ON:
  228.      if (s[0] == 0 || s[1] != 0)  goto refill ;
  229.      if (!ss)
  230.      {
  231.         if (cb_ss && s > cb_ss)  goto refill ;
  232.         else  ss = s ;
  233.      }
  234.      s++ ; m++ ;
  235.      goto reswitch ;
  236.  
  237.       case M_ANY + U_ON + END_OFF:
  238.      if (s[0] == 0)     goto refill ;
  239.      s++ ;
  240.      push(m, s, ss, U_ON) ;
  241.      if (!ss)
  242.      {
  243.         if (cb_ss && s - 1 > cb_ss)     goto refill ;
  244.         else  ss = s - 1 ;
  245.      }
  246.      m++ ; u_flag = U_OFF ;
  247.      goto reswitch ;
  248.  
  249.       case M_ANY + U_ON + END_ON:
  250.      if (s[0] == 0)     goto refill ;
  251.      if (!str_end)    str_end = s + strlen(s) ;
  252.      if (!ss)
  253.      {
  254.         if (cb_ss && str_end - 1 > cb_ss)  goto refill ;
  255.         else  ss = str_end - 1 ;
  256.      }
  257.      s = str_end ; m++ ; u_flag = U_OFF ;
  258.      goto reswitch ;
  259.  
  260.       case M_START + U_OFF + END_OFF:
  261.       case M_START + U_ON + END_OFF:
  262.      if (s != str)    goto refill ;
  263.      ss = s ;
  264.      m++ ;    u_flag = U_OFF ;
  265.      goto reswitch ;
  266.  
  267.       case M_START + U_OFF + END_ON:
  268.       case M_START + U_ON + END_ON:
  269.      if (s != str || s[0] != 0)  goto refill ;
  270.      ss = s ;
  271.      m++ ; u_flag = U_OFF ;
  272.      goto reswitch ;
  273.  
  274.       case M_END + U_OFF:
  275.      if (s[0] != 0)     goto refill ;
  276.      if (!ss)
  277.      {
  278.         if (cb_ss && s > cb_ss)  goto refill ;
  279.         else  ss = s ;
  280.      }
  281.      m++ ; goto reswitch ;
  282.  
  283.       case M_END + U_ON:
  284.      s = str_end ? str_end : (str_end = s + strlen(s)) ;
  285.      if (!ss)
  286.      {
  287.         if (cb_ss && s > cb_ss)  goto refill ;
  288.         else  ss = s ;
  289.      }
  290.      m++ ; u_flag = U_OFF ;
  291.      goto reswitch ;
  292.  
  293.        CASE_UANY(M_U):
  294.      if (!ss)
  295.      {
  296.         if (cb_ss && s > cb_ss)  goto refill ;
  297.         else  ss = s ;
  298.      }
  299.      u_flag = U_ON ; m++ ;
  300.      goto reswitch ;
  301.  
  302.        CASE_UANY(M_1J):
  303.      m += m->data.jump ;
  304.      goto reswitch ;
  305.  
  306.        CASE_UANY(M_2JA):    /* take the non jump branch */
  307.      push(m + m->data.jump, s, ss, u_flag) ;
  308.      m++ ;
  309.      goto reswitch ;
  310.  
  311.        CASE_UANY(M_2JB):    /* take the jump branch */
  312.      push(m + 1, s, ss, u_flag) ;
  313.      m += m->data.jump ;
  314.      goto reswitch ;
  315.  
  316.       case M_ACCEPT + U_OFF:
  317.      if (!ss)  ss = s ;
  318.      if (!cb_ss || ss < cb_ss || ss == cb_ss && s > cb_e)
  319.      {
  320.         /* we have a new current best */
  321.         cb_ss = ss ; cb_e = s ;
  322.      }
  323.      goto refill ;
  324.  
  325.       case M_ACCEPT + U_ON:
  326.      if (!ss)  ss = s ;
  327.      else  s = str_end ? str_end : (str_end = s + strlen(s)) ;
  328.  
  329.      if (!cb_ss || ss < cb_ss || ss == cb_ss && s > cb_e)
  330.      {
  331.         /* we have a new current best */
  332.         cb_ss = ss ; cb_e = s ;
  333.      }
  334.      goto refill ;
  335.  
  336.       default:
  337.      RE_panic("unexpected case in REmatch") ;
  338.    }
  339. }
  340.