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