rexp/rexp0.c

   1
   2 /********************************************
   3 rexp0.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: rexp0.c,v $
  14  *Revision 1.5  1996/11/08 15:39:27  mike
  15  *While cleaning up block_on, I introduced a bug. Now fixed.
  16  *
  17  *Revision 1.4  1996/09/02 18:47:09  mike
  18  *Allow []...] and [^]...] to put ] in a class.
  19  *Make ^* and ^+ syntax errors.
  20  *
  21  * Revision 1.3  1994/12/26  16:37:52  mike
  22  * 1.1.2 fix to do_str was incomplete -- fix it
  23  *
  24  * Revision 1.2  1993/07/23  13:21:38  mike
  25  * cleanup rexp code
  26  *
  27  * Revision 1.1.1.1  1993/07/03  18:58:27  mike
  28  * move source to cvs
  29  *
  30  * Revision 3.8  1992/04/21  20:22:38  brennan
  31  * 1.1 patch2
  32  * [c1-c2] now works if c2 is an escaped character
  33  *
  34  * Revision 3.7  1992/03/24  09:33:12  brennan
  35  * 1.1 patch2
  36  * When backing up in do_str, check if last character was escaped
  37  *
  38  * Revision 3.6  92/01/21  17:32:51  brennan
  39  * added some casts so that character classes work with signed chars
  40  *
  41  * Revision 3.5  91/10/29  10:53:57  brennan
  42  * SIZE_T
  43  *
  44  * Revision 3.4  91/08/13  09:10:05  brennan
  45  * VERSION .9994
  46  *
  47  * Revision 3.3  91/07/19  07:29:24  brennan
  48  * backslash at end of regular expression now stands for backslash
  49  *
  50  * Revision 3.2  91/07/19  06:58:23  brennan
  51  * removed small bozo in processing of escape characters
  52  *
  53  * Revision 3.1  91/06/07  10:33:20  brennan
  54  * VERSION 0.995
  55  *
  56  * Revision 1.2  91/06/05  08:59:36  brennan
  57  * changed RE_free to free
  58  *
  59  * Revision 1.1  91/06/03  07:10:15  brennan
  60  * Initial revision
  61  *
  62 */
  63
  64 /*  lexical scanner  */
  65
  66 #include  "rexp.h"
  67
  68 /* static functions */
  69 static int PROTO(do_str, (int, char **, MACHINE *)) ;
  70 static int PROTO(do_class, (char **, MACHINE *)) ;
  71 static int PROTO(escape, (char **)) ;
  72 static BV *PROTO(store_bvp, (BV *)) ;
  73 static int PROTO(ctohex, (int)) ;
  74
  75
  76 #ifndef  EG
  77 /* make next array visible */
  78 static
  79 #endif
  80 char  RE_char2token[ '|' + 1 ] = {
  81 0,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  82 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,9,13,13,13,
  83 6,7,3,4,13,13,10,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  84 13,13,5,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  85 13,13,13,13,13,13,13,13,13,13,11,12,13,8,13,13,13,13,13,13,
  86 13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,
  87 13,13,13,13,1} ;
  88
  89 #define  char2token(x) \
  90 ( (unsigned char)(x) > '|' ? T_CHAR : RE_char2token[x] )
  91
  92 #define NOT_STARTED    (-1)
  93
  94 static int prev ;
  95 static char *lp ;                /*  ptr to reg exp string  */
  96 static unsigned re_len ;
  97
  98
  99 void
 100 RE_lex_init(re)
 101    char *re ;
 102 {
 103    lp = re ;
 104    re_len = strlen(re) + 1 ;
 105    prev = NOT_STARTED ;
 106    RE_run_stack_init() ;
 107 }
 108
 109
 110 int
 111 RE_lex(mp)
 112    MACHINE *mp ;
 113 {
 114    register int c ;
 115
 116    switch (c = char2token(*lp))
 117    {
 118       case T_PLUS:
 119       case T_STAR:
 120          if (prev == T_START) RE_error_trap(6) ;
 121          /* fall thru */
 122
 123       case T_OR:
 124       case T_Q:
 125       case T_RP:
 126          lp++ ;  return  prev = c ;
 127
 128       case T_SLASH:
 129          break ;
 130
 131       case 0:
 132          return 0 ;
 133
 134       case T_LP:
 135          switch (prev)
 136          {
 137             case T_CHAR:
 138             case T_STR:
 139             case T_ANY:
 140             case T_CLASS:
 141             case T_START:
 142             case T_RP:
 143             case T_PLUS:
 144             case T_STAR:
 145             case T_Q:
 146             case T_U:
 147                return prev = T_CAT ;
 148
 149             default:
 150                lp++ ;
 151                return prev = T_LP ;
 152          }
 153    }
 154
 155    /*  *lp  is  an operand, but implicit cat op is possible   */
 156    switch (prev)
 157    {
 158       case NOT_STARTED:
 159       case T_OR:
 160       case T_LP:
 161       case T_CAT:
 162
 163          switch (c)
 164          {
 165             case T_ANY:
 166                {
 167                   static int plus_is_star_flag = 0 ;
 168
 169                   if (*++lp == '*')
 170                   {
 171                      lp++ ;
 172                      *mp = RE_u() ;
 173                      return prev = T_U ;
 174                   }
 175                   else if (*lp == '+')
 176                   {
 177                      if (plus_is_star_flag)
 178                      {
 179                         lp++ ;
 180                         *mp = RE_u() ;
 181                         plus_is_star_flag = 0 ;
 182                         return prev = T_U ;
 183                      }
 184                      else
 185                      {
 186                         plus_is_star_flag = 1 ;
 187                         lp-- ;
 188                         *mp = RE_any() ;
 189                         return prev = T_ANY ;
 190                      }
 191                   }
 192                   else
 193                   {
 194                      *mp = RE_any() ;
 195                      prev = T_ANY ;
 196                   }
 197                }
 198                break ;
 199
 200             case T_SLASH:
 201                lp++ ;
 202                c = escape(&lp) ;
 203                prev = do_str(c, &lp, mp) ;
 204                break ;
 205
 206             case T_CHAR:
 207                c = *lp++ ;
 208                prev = do_str(c, &lp, mp) ;
 209                break ;
 210
 211             case T_CLASS:
 212                prev = do_class(&lp, mp) ;
 213                break ;
 214
 215             case T_START:
 216                *mp = RE_start() ;
 217                lp++ ;
 218                prev = T_START ;
 219                break ;
 220
 221             case T_END:
 222                lp++ ;
 223                *mp = RE_end() ;
 224                return prev = T_END ;
 225
 226             default:
 227                RE_panic("bad switch in RE_lex") ;
 228          }
 229          break ;
 230
 231       default:
 232          /* don't advance the pointer */
 233          return prev = T_CAT ;
 234    }
 235
 236    /* check for end character */
 237    if (*lp == '$')
 238    {
 239       mp->start->type += END_ON ;
 240       lp++ ;
 241    }
 242
 243    return prev ;
 244 }
 245
 246 /*
 247   Collect a run of characters into a string machine.
 248   If the run ends at *,+, or ?, then don't take the last
 249   character unless the string has length one.
 250 */
 251
 252 static int
 253 do_str(c, pp, mp)
 254    int c ;                       /* the first character */
 255    char **pp ;                   /* where to put the re_char pointer on exit */
 256    MACHINE *mp ;                 /* where to put the string machine */
 257 {
 258    register char *p ;            /* runs thru the input */
 259    char *pt ;                    /* trails p by one */
 260    char *str ;                   /* collect it here */
 261    register char *s ;            /* runs thru the output */
 262    unsigned len ;                /* length collected */
 263
 264
 265    p = *pp ;
 266    s = str = RE_malloc(re_len) ;
 267    *s++ = c ;  len = 1 ;
 268
 269    while (1)
 270    {
 271       char *save ;
 272
 273       switch (char2token(*p))
 274       {
 275          case T_CHAR:
 276             pt = p ;
 277             *s++ = *p++ ;
 278             break ;
 279
 280          case T_SLASH:
 281             pt = p ;
 282             save = p+1 ;   /* keep p in a register */
 283             *s++ = escape(&save) ;
 284             p = save ;
 285             break ;
 286
 287          default:
 288             goto out ;
 289       }
 290       len++ ;
 291    }
 292
 293 out:
 294    /* if len > 1 and we stopped on a ? + or * , need to back up */
 295    if (len > 1 && (*p == '*' || *p == '+' || *p == '?'))
 296    {
 297       len-- ;
 298       p = pt ;
 299       s-- ;
 300    }
 301
 302    *s = 0 ;
 303    *pp = p ;
 304    *mp = RE_str((char *) RE_realloc(str, len + 1), len) ;
 305    return T_STR ;
 306 }
 307
 308
 309 /*--------------------------------------------
 310   BUILD A CHARACTER CLASS
 311  *---------------------------*/
 312
 313 #define  on( b, x)  ((b)[(x)>>3] |= ( 1 << ((x)&7) ))
 314
 315 static void PROTO(block_on, (BV, int, int)) ;
 316
 317 static void
 318 block_on(b, x, y)
 319    BV b ;
 320    int x, y ;
 321    /* caller makes sure x<=y and x>0 y>0 */
 322 {
 323    int lo = x >> 3 ;
 324    int hi = y >> 3 ;
 325    int r_lo = x&7 ;
 326    int r_hi = y&7 ;
 327
 328    if (lo == hi)
 329    {
 330       b[lo] |= (1<<(r_hi+1)) - (1<<r_lo) ;
 331    }
 332    else
 333    {
 334       int i ;
 335       for (i = lo + 1; i <  hi ; i++)  b[i] = 0xff ;
 336       b[lo] |= (0xff << r_lo) ;
 337       b[hi] |= ~(0xff << (r_hi+1)) ;
 338    }
 339 }
 340
 341 /* build a BV for a character class.
 342    *start points at the '['
 343    on exit:   *start points at the character after ']'
 344               mp points at a machine that recognizes the class
 345 */
 346
 347 static int
 348 do_class(start, mp)  char **start ;
 349    MACHINE *mp ;
 350 {
 351    register char *p ;
 352    register BV *bvp ;
 353    int prev ;
 354    char *q, *t ;
 355    int cnt ;
 356    int comp_flag ;
 357
 358    p = t = (*start) + 1 ;
 359
 360    /* []...]  puts ] in a class
 361       [^]..]  negates a class with ]
 362    */
 363    if (*p == ']') p++ ;
 364    else if (*p == '^' && *(p + 1) == ']')  p += 2 ;
 365
 366    while (1)                    /* find the back of the class */
 367    {
 368       if (!(q = strchr(p, ']')))
 369       {
 370          /* no closing bracket */
 371          RE_error_trap(-E3) ;
 372       }
 373       p = q - 1 ;
 374       cnt = 0 ;
 375       while (*p == '\\')
 376       {
 377          cnt++ ; p-- ;
 378       }
 379       if ((cnt & 1) == 0)
 380       {
 381          /* even number of \ */
 382          break ;
 383       }
 384       p = q + 1 ;
 385    }
 386
 387    /*  q  now  pts at the back of the class   */
 388    p = t ;
 389    *start = q + 1 ;
 390
 391    bvp = (BV *) RE_malloc(sizeof(BV)) ;
 392    memset(bvp, 0, sizeof(BV)) ;
 393
 394    if (*p == '^')
 395    {
 396       comp_flag = 1 ; p++ ;
 397    }
 398    else  comp_flag = 0 ;
 399
 400    prev = -1 ;                   /* indicates  -  cannot be part of a range  */
 401
 402    while (p < q)
 403    {
 404       switch (*p)
 405       {
 406          case '\\':
 407
 408             t = p + 1 ;
 409             prev = escape(&t) ;
 410             on(*bvp, prev) ;
 411             p = t ;
 412             break ;
 413
 414          case '-':
 415
 416             if (prev == -1 || p + 1 == q)
 417             {
 418                prev = '-' ;
 419                on(*bvp, '-') ;
 420                p++ ;
 421             }
 422             else
 423             {
 424                int c ;
 425                char *mark = ++p ;
 426
 427                if (*p != '\\')  c = *(unsigned char *) p++ ;
 428                else
 429                {
 430                   t = p + 1 ;
 431                   c = escape(&t) ;
 432                   p = t ;
 433                }
 434
 435                if (prev <= c)
 436                {
 437                   block_on(*bvp, prev, c) ;
 438                   prev = -1 ;
 439                }
 440                else  /* back up */
 441                {
 442                   p = mark ;
 443                   prev = '-' ;
 444                   on(*bvp, '-') ;
 445                }
 446             }
 447             break ;
 448
 449          default:
 450             prev = *(unsigned char *) p++ ;
 451             on(*bvp, prev) ;
 452             break ;
 453       }
 454    }
 455
 456    if (comp_flag)
 457    {
 458       for (p = (char *) bvp; p < (char *) bvp + sizeof(BV); p++)
 459       {
 460          *p = ~*p ;
 461       }
 462    }
 463
 464    /* make sure zero is off */
 465    (*bvp)[0] &= ~1 ;
 466
 467    *mp = RE_class(store_bvp(bvp)) ;
 468    return T_CLASS ;
 469 }
 470
 471
 472 /* storage for bit vectors so they can be reused ,
 473    stored in an unsorted linear array
 474    the array grows as needed
 475 */
 476
 477 #define         BV_GROWTH       6
 478
 479 static BV *
 480 store_bvp(bvp)
 481    BV *bvp ;
 482 {
 483    static BV **bv_base, **bv_limit ;
 484    static BV **bv_next ;         /* next empty slot in the array */
 485
 486    register BV **p ;
 487    unsigned t ;
 488
 489
 490    if (bv_next == bv_limit)
 491    {
 492       /* need to grow */
 493       if (!bv_base)
 494       {
 495          /* first growth */
 496          t = 0 ;
 497          bv_base = (BV **) RE_malloc(BV_GROWTH * sizeof(BV *)) ;
 498       }
 499       else
 500       {
 501          t = bv_next - bv_base ;
 502          bv_base = (BV **) RE_realloc(bv_base, (t + BV_GROWTH) * sizeof(BV *)) ;
 503       }
 504
 505       bv_next = bv_base + t ;
 506       bv_limit = bv_next + BV_GROWTH ;
 507    }
 508
 509    /* put bvp in bv_next as a sentinal */
 510    *bv_next = bvp ;
 511    p = bv_base ;
 512    while (memcmp(*p, bvp, sizeof(BV)))  p++ ;
 513
 514    if (p == bv_next)
 515    {
 516       /* it is new */
 517       bv_next++ ;
 518    }
 519    else
 520    {
 521       /* we already have it */
 522       free(bvp) ;
 523    }
 524
 525    return *p ;
 526 }
 527
 528
 529 /* ----------   convert escape sequences  -------------*/
 530
 531 #define isoctal(x)  ((x)>='0'&&(x)<='7')
 532
 533 #define  NOT_HEX        16
 534 static char hex_val['f' - 'A' + 1] =
 535 {
 536    10, 11, 12, 13, 14, 15, 0, 0,
 537    0, 0, 0, 0, 0, 0, 0, 0,
 538    0, 0, 0, 0, 0, 0, 0, 0,
 539    0, 0, 0, 0, 0, 0, 0, 0,
 540    10, 11, 12, 13, 14, 15} ;
 541
 542 /* interpret 1 character as hex */
 543 static int
 544 ctohex(c)
 545    register int c ;
 546 {
 547    int t ;
 548
 549    if (c >= '0' && c <= '9')  return c - '0' ;
 550    if (c >= 'A' && c <= 'f' && (t = hex_val[c - 'A']))  return t ;
 551    return NOT_HEX ;
 552 }
 553
 554 #define  ET_END     7
 555
 556 static struct
 557 {
 558    char in, out ;
 559 }
 560 escape_test[ET_END + 1] =
 561 {
 562    {'n', '\n'},
 563    {'t', '\t'},
 564    {'f', '\f'},
 565    {'b', '\b'},
 566    {'r', '\r'},
 567    {'a', '\07'},
 568    {'v', '\013'},
 569    {0, 0}
 570 } ;
 571
 572
 573 /*-----------------
 574   return the char
 575   and move the pointer forward
 576   on entry *s -> at the character after the slash
 577  *-------------------*/
 578
 579 static int
 580 escape(start_p)
 581    char **start_p ;
 582 {
 583    register char *p = *start_p ;
 584    register unsigned x ;
 585    unsigned xx ;
 586    int i ;
 587
 588
 589    escape_test[ET_END].in = *p ;
 590    i = 0 ;
 591    while (escape_test[i].in != *p)  i++ ;
 592    if (i != ET_END)
 593    {
 594       /* in escape_test table */
 595       *start_p = p + 1 ;
 596       return escape_test[i].out ;
 597    }
 598
 599    if (isoctal(*p))
 600    {
 601       x = *p++ - '0' ;
 602       if (isoctal(*p))
 603       {
 604          x = (x << 3) + *p++ - '0' ;
 605          if (isoctal(*p))  x = (x << 3) + *p++ - '0' ;
 606       }
 607       *start_p = p ;
 608       return x & 0xff ;
 609    }
 610
 611    if (*p == 0)  return '\\' ;
 612
 613    if (*p++ == 'x')
 614    {
 615       if ((x = ctohex(*p)) == NOT_HEX)
 616       {
 617          *start_p  = p ;  return 'x' ;
 618       }
 619
 620       /* look for another hex digit */
 621       if ((xx = ctohex(*++p)) != NOT_HEX)
 622       {
 623          x = (x<<4) + xx ; p++ ;
 624       }
 625
 626       *start_p = p ; return x ;
 627    }
 628
 629    /* anything else \c -> c */
 630    *start_p = p ;
 631    return *(unsigned char *) (p - 1) ;
 632 }
 633