2.11BSD#431 - /usr/src/lib/libc/gen/regex.c

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

Defined functions

Defined variables

Defined macros