home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 11 Util / 11-Util.zip / MAWK113.ZIP / mawk113 / rexp / rexp2.c < prev    next >
C/C++ Source or Header  |  1992-12-23  |  9KB  |  341 lines
  1.  
  2. /********************************************
  3. rexp2.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: rexp2.c,v $
  14.  * Revision 3.8  1992/12/24  00:36:44  mike
  15.  * fixed major bozo for LMDOS when growing stack
  16.  * fixed potential LMDOS bozo with M_STR+U_ON+END_ON
  17.  * fixed minor bug in M_CLASS+U_ON+END_ON
  18.  *
  19.  * Revision 3.7  92/01/21  17:33:15  brennan
  20.  * added some casts so that character classes work with signed chars
  21.  * 
  22.  * Revision 3.6  91/10/29  10:54:03  brennan
  23.  * SIZE_T
  24.  * 
  25.  * Revision 3.5  91/08/13  09:10:15  brennan
  26.  * VERSION .9994
  27.  * 
  28.  * Revision 3.4  91/08/08  07:53:34  brennan
  29.  * work around for turboC realloc() bug
  30.  * 
  31.  * Revision 3.4  91/08/07  07:10:47  brennan
  32.  * work around for TurboC realloc() bug
  33.  * 
  34.  * Revision 3.3  91/08/04  15:45:57  brennan
  35.  * minor change for large model dos
  36.  * 
  37.  * Revision 3.2  91/06/10  16:18:14  brennan
  38.  * changes for V7
  39.  * 
  40.  * Revision 3.1  91/06/07  10:33:25  brennan
  41.  * VERSION 0.995
  42.  * 
  43.  * Revision 1.8  91/06/05  09:01:33  brennan
  44.  * changes to RE_new_run_stack
  45.  * 
  46.  * Revision 1.7  91/05/31  10:56:02  brennan
  47.  * stack_empty hack for DOS large model
  48.  * 
  49. */
  50.  
  51.  
  52.  
  53. /*  test a string against a machine   */
  54.  
  55. #include "rexp.h"
  56.  
  57. #define  STACKGROWTH    16
  58.  
  59. #ifdef  DEBUG
  60. static RT_STATE *PROTO(slow_push,(RT_STATE *,STATE*,char*,int)); 
  61. #endif
  62.  
  63.  
  64. RT_STATE *RE_run_stack_base; 
  65. RT_STATE *RE_run_stack_limit ;
  66.  
  67. /* Large model DOS segment arithemetic breaks the current stack.
  68.    This hack fixes it without rewriting the whole thing, 5/31/91 */
  69. RT_STATE *RE_run_stack_empty ;
  70.  
  71. void RE_run_stack_init()
  72. { 
  73.   if ( !RE_run_stack_base )
  74.   {
  75.     RE_run_stack_base = (RT_STATE *)
  76.                  RE_malloc(sizeof(RT_STATE) * STACKGROWTH ) ;
  77.     RE_run_stack_limit = RE_run_stack_base + STACKGROWTH ;
  78.     RE_run_stack_empty = RE_run_stack_base-1 ;
  79.   }
  80. }
  81.  
  82. /* sometimes during REmatch(), this stack can grow pretty large.
  83.    In real life cases, the back tracking usually fails. Some
  84.    work is needed here to improve the algorithm.
  85.    I.e., figure out how not to stack useless paths.
  86. */
  87.  
  88. RT_STATE  *RE_new_run_stack()
  89. { 
  90.   int oldsize = RE_run_stack_limit - RE_run_stack_base ;
  91.   int newsize = oldsize + STACKGROWTH ;
  92.  
  93. #ifdef  LMDOS   /* large model DOS */
  94.   /* have to worry about overflow on multiplication (ugh) */
  95.   if ( newsize >= 4096 ) RE_run_stack_base = (RT_STATE*) 0 ;
  96.   else
  97. #endif
  98.  
  99.   RE_run_stack_base = (RT_STATE *) realloc( RE_run_stack_base ,
  100.           SIZE_T(newsize * sizeof(RT_STATE)) ) ;
  101.  
  102.   if ( ! RE_run_stack_base )
  103.   { fprintf(stderr, "out of memory for RE run time stack\n") ;
  104.     /* this is pretty unusual, I've only seen it happen on
  105.        weird input to REmatch() under 16bit DOS , the same
  106.        situation worked easily on 32bit machine.  */
  107.     exit(100) ;
  108.   }
  109.  
  110.   RE_run_stack_limit = RE_run_stack_base + newsize ;
  111.   RE_run_stack_empty = RE_run_stack_base - 1 ;
  112.  
  113.   /* return the new stackp */
  114.   return  RE_run_stack_base + oldsize ;
  115. }
  116.  
  117. #ifdef  DEBUG
  118. static RT_STATE *slow_push(sp, m, s, u)
  119.   RT_STATE *sp ;
  120.   STATE *m ;
  121.   char *s ;
  122.   int   u ;
  123. { 
  124.   if ( sp == RE_run_stack_limit ) sp = RE_new_run_stack() ;
  125.   sp->m = m ; sp->s = s ; sp->u = u ;
  126.   return sp ;
  127. }
  128. #endif
  129.  
  130. #ifdef   DEBUG
  131. #define  push(mx,sx,ux)   stackp = slow_push(++stackp, mx, sx, ux)
  132. #else
  133. #define  push(mx,sx,ux)   if (++stackp == RE_run_stack_limit)\
  134.                                 stackp = RE_new_run_stack() ;\
  135.                           stackp->m=(mx);stackp->s=(sx);stackp->u=(ux)
  136. #endif
  137.  
  138.  
  139. #define   CASE_UANY(x)  case  x + U_OFF :  case  x + U_ON
  140.  
  141. /* test if str ~ /machine/
  142. */
  143.  
  144. int  REtest( str, machine)
  145.   char *str ;
  146.   VOID *machine ;
  147. { register STATE *m = (STATE *) machine ;
  148.   register char *s = str ;
  149.   register RT_STATE *stackp ;
  150.   int u_flag ;
  151.   char *str_end ;
  152.   int t ; /*convenient temps */
  153.   STATE *tm ;
  154.  
  155.   /* handle the easy case quickly */
  156.   if ( (m+1)->type == M_ACCEPT && m->type == M_STR )
  157.         return  str_str(s, m->data.str, m->len) != (char *) 0 ;
  158.   else
  159.   { u_flag = U_ON ; str_end = (char *) 0 ;
  160.     stackp = RE_run_stack_empty ;
  161.     goto  reswitch ;
  162.   }
  163.  
  164. refill :
  165.   if ( stackp == RE_run_stack_empty )  return  0 ;
  166.   m = stackp->m ;
  167.   s = stackp->s ;
  168.   u_flag  = stackp-- -> u ;
  169.  
  170.  
  171. reswitch  :
  172.  
  173.   switch( m->type + u_flag )
  174.   {
  175.     case M_STR + U_OFF + END_OFF :
  176.             if ( strncmp(s, m->data.str, SIZE_T(m->len)) ) goto refill ;
  177.             s += m->len ;  m++ ;
  178.             goto reswitch ;
  179.  
  180.     case M_STR + U_OFF + END_ON :
  181.             if ( strcmp(s, m->data.str) ) goto refill ;
  182.             s += m->len ;  m++ ;
  183.             goto reswitch ;
  184.  
  185.     case M_STR + U_ON + END_OFF :
  186.             if ( !(s = str_str(s, m->data.str, m->len)) ) goto refill ;
  187.             push(m, s+1, U_ON) ;
  188.             s += m->len ; m++ ; u_flag = U_OFF ;
  189.             goto reswitch ;
  190.  
  191.     case M_STR + U_ON + END_ON :
  192.             if ( !str_end )  str_end = s + strlen(s) ;
  193.         t = (str_end - s) - m->len ;
  194.             if (t < 0 || memcmp(s+t,m->data.str,SIZE_T(m->len)))
  195.             goto refill ;
  196.             s = str_end ; m++ ; u_flag = U_OFF ;
  197.             goto reswitch ;
  198.  
  199.     case M_CLASS + U_OFF + END_OFF :
  200.             if ( !ison(*m->data.bvp, s[0] ) )  goto refill ;
  201.             s++ ; m++ ;
  202.             goto reswitch ;
  203.  
  204.     case M_CLASS + U_OFF + END_ON :
  205.             if ( s[1] || !ison(*m->data.bvp,s[0]) )  goto refill ;
  206.             s++ ; m++ ;
  207.             goto reswitch ;
  208.     case M_CLASS + U_ON + END_OFF :
  209.             while ( !ison(*m->data.bvp,s[0]) )
  210.                 if ( s[0] == 0 )  goto refill ;
  211.                 else  s++ ;
  212.             s++ ;
  213.             push(m, s, U_ON) ;
  214.             m++ ; u_flag = U_OFF ;
  215.             goto reswitch ;
  216.  
  217.     case M_CLASS + U_ON + END_ON :
  218.             if ( ! str_end )  str_end = s + strlen(s) ;
  219.             if ( s[0] == 0 || ! ison(*m->data.bvp, str_end[-1]) )
  220.                 goto refill ;
  221.             s = str_end ; m++ ; u_flag = U_OFF ;
  222.             goto reswitch ;
  223.  
  224.     case M_ANY + U_OFF + END_OFF :
  225.             if ( s[0] == 0 )  goto refill ;
  226.             s++ ; m++ ;
  227.             goto  reswitch ;
  228.  
  229.     case M_ANY + U_OFF + END_ON :
  230.             if ( s[0] == 0 || s[1] != 0 )  goto refill ;
  231.             s++ ; m++ ;
  232.             goto reswitch ;
  233.  
  234.     case M_ANY + U_ON + END_OFF :
  235.             if ( s[0] == 0 )  goto refill ;
  236.             s++ ; 
  237.             push(m, s, U_ON) ;
  238.             m++ ; u_flag = U_OFF ;
  239.             goto  reswitch ;
  240.  
  241.     case M_ANY + U_ON + END_ON :
  242.             if ( s[0] == 0 )  goto refill ;
  243.             if ( ! str_end )  str_end = s + strlen(s) ;
  244.             s = str_end ; m++ ; u_flag = U_OFF ;
  245.             goto reswitch ;
  246.  
  247.     case  M_START + U_OFF + END_OFF :
  248.     case  M_START + U_ON  + END_OFF :
  249.             if ( s != str )  goto  refill ;
  250.             m++ ;  u_flag = U_OFF ;
  251.             goto  reswitch ;
  252.  
  253.     case  M_START + U_OFF + END_ON :
  254.     case  M_START + U_ON  + END_ON :
  255.             if ( s != str || s[0] != 0 )  goto  refill ;
  256.             m++ ; u_flag = U_OFF ;
  257.             goto  reswitch ;
  258.  
  259.     case  M_END + U_OFF  :
  260.             if ( s[0]  != 0 )  goto  refill ;
  261.             m++ ; goto reswitch ;
  262.  
  263.     case  M_END + U_ON :
  264.             s += strlen(s) ;
  265.             m++ ; u_flag = U_OFF ;
  266.             goto reswitch ;
  267.  
  268.     CASE_UANY(M_U) :
  269.             u_flag = U_ON ; m++ ;
  270.             goto reswitch ;
  271.  
  272.     CASE_UANY(M_1J) :
  273.             m += m->data.jump ;
  274.             goto reswitch ;
  275.  
  276.     CASE_UANY(M_2JA) : /* take the non jump branch */
  277.             /* don't stack an ACCEPT */
  278.             if ( (tm = m + m->data.jump)->type == M_ACCEPT ) return 1 ;
  279.             push(tm, s, u_flag) ;
  280.             m++ ;
  281.             goto reswitch ;
  282.  
  283.     CASE_UANY(M_2JB) : /* take the jump branch */
  284.             /* don't stack an ACCEPT */
  285.             if ( (tm = m + 1)->type == M_ACCEPT ) return 1 ;
  286.             push(tm, s, u_flag) ;
  287.             m += m->data.jump ;
  288.             goto reswitch ;
  289.  
  290.     CASE_UANY(M_ACCEPT) :
  291.             return 1 ;
  292.  
  293.     default :
  294.             RE_panic("unexpected case in REtest") ;
  295.   }
  296. }
  297.  
  298.   
  299.  
  300. #ifdef  MAWK
  301.  
  302. char *is_string_split( p, lenp )
  303.   register STATE *p ;
  304.   unsigned *lenp ;
  305. {
  306.   if ( p[0].type == M_STR && p[1].type == M_ACCEPT )
  307.   { *lenp = p->len ;
  308.     return  p->data.str ;
  309.   }
  310.   else   return  (char *) 0 ;
  311. }
  312. #else /* mawk provides its own str_str */
  313.  
  314. char *str_str(target, key, klen)
  315.   register char *target ;
  316.   register char *key ;
  317.   unsigned klen ;
  318. { int c = key[0] ;
  319.  
  320.   switch( klen )
  321.   { case 0 :  return (char *) 0 ;
  322.     case 1 :  return strchr(target, c) ;
  323.     case 2 :  
  324.               while ( target = strchr(target, c) )
  325.                     if ( target[1] == key[1] ) return target ;
  326.                     else target++ ;
  327.               break ;
  328.  
  329.     default :
  330.               klen-- ; key++ ;
  331.               while ( target = strchr(target, c) )
  332.                     if (memcmp(target+1,key,SIZE_T(klen)) == 0) return target ;
  333.                     else target++ ;
  334.               break ;
  335.   }
  336.   return (char *) 0 ;
  337. }
  338.               
  339.  
  340. #endif  /* MAWK */
  341.