src/util/regex.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 /*
  11  * regex.c -- regular expression patter matching functions
  12  *
  13  */
  14
  15 #include <afsconfig.h>
  16 #include <afs/param.h>
  17
  18
  19 /*
  20  * routines to do regular expression matching
  21  *
  22  * Entry points:
  23  *
  24  *      re_comp(s)
  25  *              char *s;
  26  *       ... returns 0 if the string s was compiled successfully,
  27  *                   a pointer to an error message otherwise.
  28  *           If passed 0 or a null string returns without changing
  29  *           the currently compiled re (see note 11 below).
  30  *
  31  *      re_exec(s)
  32  *              char *s;
  33  *       ... returns 1 if the string s matches the last compiled regular
  34  *                     expression,
  35  *                   0 if the string s failed to match the last compiled
  36  *                     regular expression, and
  37  *                  -1 if the compiled regular expression was invalid
  38  *                     (indicating an internal error).
  39  *
  40  * The strings passed to both re_comp and re_exec may have trailing or
  41  * embedded newline characters; they are terminated by nulls.
  42  *
  43  * The identity of the author of these routines is lost in antiquity;
  44  * this is essentially the same as the re code in the original V6 ed.
  45  *
  46  * The regular expressions recognized are described below. This description
  47  * is essentially the same as that for ed.
  48  *
  49  *      A regular expression specifies a set of strings of characters.
  50  *      A member of this set of strings is said to be matched by
  51  *      the regular expression.  In the following specification for
  52  *      regular expressions the word `character' means any character but NUL.
  53  *
  54  *      1.  Any character except a special character matches itself.
  55  *          Special characters are the regular expression delimiter plus
  56  *          \ [ . and sometimes ^ * $.
  57  *      2.  A . matches any character.
  58  *      3.  A \ followed by any character except a digit or ( )
  59  *          matches that character.
  60  *      4.  A nonempty string s bracketed [s] (or [^s]) matches any
  61  *          character in (or not in) s. In s, \ has no special meaning,
  62  *          and ] may only appear as the first letter. A substring
  63  *          a-b, with a and b in ascending ASCII order, stands for
  64  *          the inclusive range of ASCII characters.
  65  *      5.  A regular expression of form 1-4 followed by * matches a
  66  *          sequence of 0 or more matches of the regular expression.
  67  *      6.  A regular expression, x, of form 1-8, bracketed \(x\)
  68  *          matches what x matches.
  69  *      7.  A \ followed by a digit n matches a copy of the string that the
  70  *          bracketed regular expression beginning with the nth \( matched.
  71  *      8.  A regular expression of form 1-8, x, followed by a regular
  72  *          expression of form 1-7, y matches a match for x followed by
  73  *          a match for y, with the x match being as long as possible
  74  *          while still permitting a y match.
  75  *      9.  A regular expression of form 1-8 preceded by ^ (or followed
  76  *          by $), is constrained to matches that begin at the left
  77  *          (or end at the right) end of a line.
  78  *      10. A regular expression of form 1-9 picks out the longest among
  79  *          the leftmost matches in a line.
  80  *      11. An empty regular expression stands for a copy of the last
  81  *          regular expression encountered.
  82  */
  83
  84 /*
  85  * constants for re's
  86  */
  87 #define CBRA    1
  88 #define CCHR    2
  89 #define CDOT    4
  90 #define CCL     6
  91 #define NCCL    8
  92 #define CDOL    10
  93 #define CEOF    11
  94 #define CKET    12
  95 #define CBACK   18
  96
  97 #define CSTAR   01
  98
  99 #define ESIZE   512
 100 #define NBRA    9
 101
 102 static char expbuf[ESIZE], *braslist[NBRA], *braelist[NBRA];
 103 static char circf;
 104
 105 /* forward defs
 106 */
 107
 108 static int advance(register char *lp, register char *ep);
 109 static int backref(register int i, register char *lp);
 110 static int cclass(register char *set, register char c, int af);
 111
 112
 113 /*
 114  * compile the regular expression argument into a dfa
 115  */
 116 char *
 117 re_comp(register char *sp)
 118 {
 119     register int c;
 120     register char *ep = expbuf;
 121     int cclcnt, numbra = 0;
 122     char *lastep = 0;
 123     char bracket[NBRA];
 124     char *bracketp = &bracket[0];
 125     static char *retoolong = "Regular expression too long";
 126
 127 #define comperr(msg) {expbuf[0] = 0; numbra = 0; return(msg); }
 128
 129     if (sp == 0 || *sp == '\0') {
 130         if (*ep == 0)
 131             return ("No previous regular expression");
 132         return (0);
 133     }
 134     if (*sp == '^') {
 135         circf = 1;
 136         sp++;
 137     } else
 138         circf = 0;
 139     for (;;) {
 140         if (ep >= &expbuf[ESIZE - 10 /* fudge factor */])
 141             comperr(retoolong);
 142         if ((c = *sp++) == '\0') {
 143             if (bracketp != bracket)
 144                 comperr("unmatched \\(");
 145             *ep++ = CEOF;
 146             *ep++ = 0;
 147             return (0);
 148         }
 149         if (c != '*')
 150             lastep = ep;
 151         switch (c) {
 152
 153         case '.':
 154             *ep++ = CDOT;
 155             continue;
 156
 157         case '*':
 158             if (lastep == 0 || *lastep == CBRA || *lastep == CKET)
 159                 goto defchar;
 160             *lastep |= CSTAR;
 161             continue;
 162
 163         case '$':
 164             if (*sp != '\0')
 165                 goto defchar;
 166             *ep++ = CDOL;
 167             continue;
 168
 169         case '[':
 170             *ep++ = CCL;
 171             *ep++ = 0;
 172             cclcnt = 1;
 173             if ((c = *sp++) == '^') {
 174                 c = *sp++;
 175                 ep[-2] = NCCL;
 176             }
 177             do {
 178                 if (c == '\0')
 179                     comperr("missing ]");
 180                 if (c == '-' && ep[-1] != 0) {
 181                     if ((c = *sp++) == ']') {
 182                         *ep++ = '-';
 183                         cclcnt++;
 184                         break;
 185                     }
 186                     while (ep[-1] < c) {
 187                         *ep = ep[-1] + 1;
 188                         ep++;
 189                         cclcnt++;
 190                         if (ep >= &expbuf[ESIZE - 10 /* fudge factor */])
 191                             comperr(retoolong);
 192                     }
 193                 }
 194                 *ep++ = c;
 195                 cclcnt++;
 196                 if (ep >= &expbuf[ESIZE - 10 /* fudge factor */])
 197                     comperr(retoolong);
 198             } while ((c = *sp++) != ']');
 199             lastep[1] = cclcnt;
 200             continue;
 201
 202         case '\\':
 203             if ((c = *sp++) == '(') {
 204                 if (numbra >= NBRA)
 205                     comperr("too many \\(\\) pairs");
 206                 *bracketp++ = numbra;
 207                 *ep++ = CBRA;
 208                 *ep++ = numbra++;
 209                 continue;
 210             }
 211             if (c == ')') {
 212                 if (bracketp <= bracket)
 213                     comperr("unmatched \\)");
 214                 *ep++ = CKET;
 215                 *ep++ = *--bracketp;
 216                 continue;
 217             }
 218             if (c >= '1' && c < ('1' + NBRA)) {
 219                 *ep++ = CBACK;
 220                 *ep++ = c - '1';
 221                 continue;
 222             }
 223             *ep++ = CCHR;
 224             *ep++ = c;
 225             continue;
 226
 227           defchar:
 228         default:
 229             *ep++ = CCHR;
 230             *ep++ = c;
 231         }
 232     }
 233 }
 234
 235 /*
 236  * match the argument string against the compiled re
 237  */
 238 int
 239 re_exec(register char *p1)
 240 {
 241     register char *p2 = expbuf;
 242     register int c;
 243     int rv;
 244
 245     for (c = 0; c < NBRA; c++) {
 246         braslist[c] = 0;
 247         braelist[c] = 0;
 248     }
 249     if (circf)
 250         return ((advance(p1, p2)));
 251     /*
 252      * fast check for first character
 253      */
 254     if (*p2 == CCHR) {
 255         c = p2[1];
 256         do {
 257             if (*p1 != c)
 258                 continue;
 259             if ((rv = advance(p1, p2)))
 260                 return (rv);
 261         } while (*p1++);
 262         return (0);
 263     }
 264     /*
 265      * regular algorithm
 266      */
 267     do
 268         if ((rv = advance(p1, p2)))
 269             return (rv);
 270     while (*p1++);
 271     return (0);
 272 }
 273
 274 /*
 275  * try to match the next thing in the dfa
 276  */
 277 static int
 278 advance(register char *lp, register char *ep)
 279 {
 280     register char *curlp;
 281     int ct, i;
 282     int rv;
 283
 284     for (;;)
 285         switch (*ep++) {
 286
 287         case CCHR:
 288             if (*ep++ == *lp++)
 289                 continue;
 290             return (0);
 291
 292         case CDOT:
 293             if (*lp++)
 294                 continue;
 295             return (0);
 296
 297         case CDOL:
 298             if (*lp == '\0')
 299                 continue;
 300             return (0);
 301
 302         case CEOF:
 303             return (1);
 304
 305         case CCL:
 306             if (cclass(ep, *lp++, 1)) {
 307                 ep += *ep;
 308                 continue;
 309             }
 310             return (0);
 311
 312         case NCCL:
 313             if (cclass(ep, *lp++, 0)) {
 314                 ep += *ep;
 315                 continue;
 316             }
 317             return (0);
 318
 319         case CBRA:
 320             braslist[*ep++] = lp;
 321             continue;
 322
 323         case CKET:
 324             braelist[*ep++] = lp;
 325             continue;
 326
 327         case CBACK:
 328             if (braelist[i = *ep++] == 0)
 329                 return (-1);
 330             if (backref(i, lp)) {
 331                 lp += braelist[i] - braslist[i];
 332                 continue;
 333             }
 334             return (0);
 335
 336         case CBACK | CSTAR:
 337             if (braelist[i = *ep++] == 0)
 338                 return (-1);
 339             curlp = lp;
 340             ct = (int)(braelist[i] - braslist[i]);
 341             while (backref(i, lp))
 342                 lp += ct;
 343             while (lp >= curlp) {
 344                 if ((rv = advance(lp, ep)))
 345                     return (rv);
 346                 lp -= ct;
 347             }
 348             continue;
 349
 350         case CDOT | CSTAR:
 351             curlp = lp;
 352             while (*lp++);
 353             goto star;
 354
 355         case CCHR | CSTAR:
 356             curlp = lp;
 357             while (*lp++ == *ep);
 358             ep++;
 359             goto star;
 360
 361         case CCL | CSTAR:
 362         case NCCL | CSTAR:
 363             curlp = lp;
 364             while (cclass(ep, *lp++, ep[-1] == (CCL | CSTAR)));
 365             ep += *ep;
 366             goto star;
 367
 368           star:
 369             do {
 370                 lp--;
 371                 if ((rv = advance(lp, ep)))
 372                     return (rv);
 373             } while (lp > curlp);
 374             return (0);
 375
 376         default:
 377             return (-1);
 378         }
 379 }
 380
 381 static int
 382 backref(register int i, register char *lp)
 383 {
 384     register char *bp;
 385
 386     bp = braslist[i];
 387     while (*bp++ == *lp++)
 388         if (bp >= braelist[i])
 389             return (1);
 390     return (0);
 391 }
 392
 393 static int
 394 cclass(register char *set, register char c, int af)
 395 {
 396     register int n;
 397
 398     if (c == 0)
 399         return (0);
 400     n = *set++;
 401     while (--n)
 402         if (*set++ == c)
 403             return (af);
 404     return (!af);
 405 }