rexp/rexp2.c

   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 */