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