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