1 /* 2 * CDDL HEADER START 3 * 4 * The contents of this file are subject to the terms of the 5 * Common Development and Distribution License (the "License"). 6 * You may not use this file except in compliance with the License. 7 * 8 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE 9 * or http://www.opensolaris.org/os/licensing. 10 * See the License for the specific language governing permissions 11 * and limitations under the License. 12 * 13 * When distributing Covered Code, include this CDDL HEADER in each 14 * file and include the License file at usr/src/OPENSOLARIS.LICENSE. 15 * If applicable, add the following below this CDDL HEADER, with the 16 * fields enclosed by brackets "[]" replaced with your own identifying 17 * information: Portions Copyright [yyyy] [name of copyright owner] 18 * 19 * CDDL HEADER END 20 */ 21 /* Copyright (c) 1988 AT&T */ 22 /* All Rights Reserved */ 23 24 /* 25 * Copyright 2014 Garrett D'Amore <garrett@damore.org> 26 * 27 * Copyright 2006 Sun Microsystems, Inc. All rights reserved. 28 * Use is subject to license terms. 29 */ 30 31 #ifndef _REGEXP_H 32 #define _REGEXP_H 33 34 #include <string.h> 35 36 #ifdef __cplusplus 37 extern "C" { 38 #endif 39 40 #define CBRA 2 41 #define CCHR 4 42 #define CDOT 8 43 #define CCL 12 44 #define CXCL 16 45 #define CDOL 20 46 #define CCEOF 22 47 #define CKET 24 48 #define CBACK 36 49 #define NCCL 40 50 51 #define STAR 01 52 #define RNGE 03 53 54 #define NBRA 9 55 56 #define PLACE(c) ep[c >> 3] |= bittab[c & 07] 57 #define ISTHERE(c) (ep[c >> 3] & bittab[c & 07]) 58 #define ecmp(s1, s2, n) (strncmp(s1, s2, n) == 0) 59 60 static char *braslist[NBRA]; 61 static char *braelist[NBRA]; 62 int sed, nbra; 63 char *loc1, *loc2, *locs; 64 static int nodelim; 65 66 int circf; 67 static int low; 68 static int size; 69 70 static unsigned char bittab[] = { 1, 2, 4, 8, 16, 32, 64, 128 }; 71 72 int advance(const char *lp, const char *ep); 73 static void getrnge(const char *str); 74 75 char * 76 compile(char *instring, char *ep, const char *endbuf, int seof) 77 { 78 INIT /* Dependent declarations and initializations */ 79 register int c; 80 register int eof = seof; 81 char *lastep; 82 int cclcnt; 83 char bracket[NBRA], *bracketp; 84 int closed; 85 int neg; 86 int lc; 87 int i, cflg; 88 int iflag; /* used for non-ascii characters in brackets */ 89 90 #ifdef __lint 91 /* make lint happy */ 92 c = nodelim; 93 #endif 94 95 lastep = NULL; 96 if ((c = GETC()) == eof || c == '\n') { 97 if (c == '\n') { 98 UNGETC(c); 99 nodelim = 1; 100 } 101 if (*ep == 0 && !sed) 102 ERROR(41); 103 RETURN(ep); 104 } 105 bracketp = bracket; 106 circf = closed = nbra = 0; 107 if (c == '^') 108 circf++; 109 else 110 UNGETC(c); 111 for (;;) { 112 if (ep >= endbuf) 113 ERROR(50); 114 c = GETC(); 115 if (c != '*' && ((c != '\\') || (PEEKC() != '{'))) 116 lastep = ep; 117 if (c == eof) { 118 *ep++ = CCEOF; 119 if (bracketp != bracket) 120 ERROR(42); 121 RETURN(ep); 122 } 123 switch (c) { 124 125 case '.': 126 *ep++ = CDOT; 127 continue; 128 129 case '\n': 130 if (!sed) { 131 UNGETC(c); 132 *ep++ = CCEOF; 133 nodelim = 1; 134 if (bracketp != bracket) 135 ERROR(42); 136 RETURN(ep); 137 } else ERROR(36); 138 case '*': 139 if (lastep == NULL || *lastep == CBRA || 140 *lastep == CKET) 141 goto defchar; 142 *lastep |= STAR; 143 continue; 144 145 case '$': 146 if (PEEKC() != eof && PEEKC() != '\n') 147 goto defchar; 148 *ep++ = CDOL; 149 continue; 150 151 case '[': 152 if (&ep[17] >= endbuf) 153 ERROR(50); 154 155 *ep++ = CCL; 156 lc = 0; 157 for (i = 0; i < 16; i++) 158 ep[i] = 0; 159 160 neg = 0; 161 if ((c = GETC()) == '^') { 162 neg = 1; 163 c = GETC(); 164 } 165 iflag = 1; 166 do { 167 c &= 0377; 168 if (c == '\0' || c == '\n') 169 ERROR(49); 170 if ((c & 0200) && iflag) { 171 iflag = 0; 172 if (&ep[32] >= endbuf) 173 ERROR(50); 174 ep[-1] = CXCL; 175 for (i = 16; i < 32; i++) 176 ep[i] = 0; 177 } 178 if (c == '-' && lc != 0) { 179 if ((c = GETC()) == ']') { 180 PLACE('-'); 181 break; 182 } 183 if ((c & 0200) && iflag) { 184 iflag = 0; 185 if (&ep[32] >= endbuf) 186 ERROR(50); 187 ep[-1] = CXCL; 188 for (i = 16; i < 32; i++) 189 ep[i] = 0; 190 } 191 while (lc < c) { 192 PLACE(lc); 193 lc++; 194 } 195 } 196 lc = c; 197 PLACE(c); 198 } while ((c = GETC()) != ']'); 199 200 if (iflag) 201 iflag = 16; 202 else 203 iflag = 32; 204 205 if (neg) { 206 if (iflag == 32) { 207 for (cclcnt = 0; cclcnt < iflag; 208 cclcnt++) 209 ep[cclcnt] ^= 0377; 210 ep[0] &= 0376; 211 } else { 212 ep[-1] = NCCL; 213 /* make nulls match so test fails */ 214 ep[0] |= 01; 215 } 216 } 217 218 ep += iflag; 219 220 continue; 221 222 case '\\': 223 switch (c = GETC()) { 224 225 case '(': 226 if (nbra >= NBRA) 227 ERROR(43); 228 *bracketp++ = (char)nbra; 229 *ep++ = CBRA; 230 *ep++ = (char)nbra++; 231 continue; 232 233 case ')': 234 if (bracketp <= bracket) 235 ERROR(42); 236 *ep++ = CKET; 237 *ep++ = *--bracketp; 238 closed++; 239 continue; 240 241 case '{': 242 if (lastep == NULL) 243 goto defchar; 244 *lastep |= RNGE; 245 cflg = 0; 246 nlim: 247 c = GETC(); 248 i = 0; 249 do { 250 if ('0' <= c && c <= '9') 251 i = 10 * i + c - '0'; 252 else 253 ERROR(16); 254 } while (((c = GETC()) != '\\') && (c != ',')); 255 if (i >= 255) 256 ERROR(11); 257 *ep++ = (char)i; 258 if (c == ',') { 259 if (cflg++) 260 ERROR(44); 261 if ((c = GETC()) == '\\') 262 *ep++ = (char)255; 263 else { 264 UNGETC(c); 265 goto nlim; 266 /* get 2'nd number */ 267 } 268 } 269 if (GETC() != '}') 270 ERROR(45); 271 if (!cflg) /* one number */ 272 *ep++ = (char)i; 273 else if ((ep[-1] & 0377) < (ep[-2] & 0377)) 274 ERROR(46); 275 continue; 276 277 case '\n': 278 ERROR(36); 279 280 case 'n': 281 c = '\n'; 282 goto defchar; 283 284 default: 285 if (c >= '1' && c <= '9') { 286 if ((c -= '1') >= closed) 287 ERROR(25); 288 *ep++ = CBACK; 289 *ep++ = (char)c; 290 continue; 291 } 292 } 293 /* Drop through to default to use \ to turn off special chars */ 294 295 defchar: 296 default: 297 lastep = ep; 298 *ep++ = CCHR; 299 *ep++ = (char)c; 300 } 301 } 302 /*NOTREACHED*/ 303 } 304 305 int 306 step(const char *p1, const char *p2) 307 { 308 char c; 309 310 311 if (circf) { 312 loc1 = (char *)p1; 313 return (advance(p1, p2)); 314 } 315 /* fast check for first character */ 316 if (*p2 == CCHR) { 317 c = p2[1]; 318 do { 319 if (*p1 != c) 320 continue; 321 if (advance(p1, p2)) { 322 loc1 = (char *)p1; 323 return (1); 324 } 325 } while (*p1++); 326 return (0); 327 } 328 /* regular algorithm */ 329 do { 330 if (advance(p1, p2)) { 331 loc1 = (char *)p1; 332 return (1); 333 } 334 } while (*p1++); 335 return (0); 336 } 337 338 int 339 advance(const char *lp, const char *ep) 340 { 341 const char *curlp; 342 int c; 343 char *bbeg; 344 register char neg; 345 size_t ct; 346 347 for (;;) { 348 neg = 0; 349 switch (*ep++) { 350 351 case CCHR: 352 if (*ep++ == *lp++) 353 continue; 354 return (0); 355 /*FALLTHRU*/ 356 357 case CDOT: 358 if (*lp++) 359 continue; 360 return (0); 361 /*FALLTHRU*/ 362 363 case CDOL: 364 if (*lp == 0) 365 continue; 366 return (0); 367 /*FALLTHRU*/ 368 369 case CCEOF: 370 loc2 = (char *)lp; 371 return (1); 372 /*FALLTHRU*/ 373 374 case CXCL: 375 c = (unsigned char)*lp++; 376 if (ISTHERE(c)) { 377 ep += 32; 378 continue; 379 } 380 return (0); 381 /*FALLTHRU*/ 382 383 case NCCL: 384 neg = 1; 385 /*FALLTHRU*/ 386 387 case CCL: 388 c = *lp++; 389 if (((c & 0200) == 0 && ISTHERE(c)) ^ neg) { 390 ep += 16; 391 continue; 392 } 393 return (0); 394 /*FALLTHRU*/ 395 396 case CBRA: 397 braslist[*ep++] = (char *)lp; 398 continue; 399 /*FALLTHRU*/ 400 401 case CKET: 402 braelist[*ep++] = (char *)lp; 403 continue; 404 /*FALLTHRU*/ 405 406 case CCHR | RNGE: 407 c = *ep++; 408 getrnge(ep); 409 while (low--) 410 if (*lp++ != c) 411 return (0); 412 curlp = lp; 413 while (size--) 414 if (*lp++ != c) 415 break; 416 if (size < 0) 417 lp++; 418 ep += 2; 419 goto star; 420 /*FALLTHRU*/ 421 422 case CDOT | RNGE: 423 getrnge(ep); 424 while (low--) 425 if (*lp++ == '\0') 426 return (0); 427 curlp = lp; 428 while (size--) 429 if (*lp++ == '\0') 430 break; 431 if (size < 0) 432 lp++; 433 ep += 2; 434 goto star; 435 /*FALLTHRU*/ 436 437 case CXCL | RNGE: 438 getrnge(ep + 32); 439 while (low--) { 440 c = (unsigned char)*lp++; 441 if (!ISTHERE(c)) 442 return (0); 443 } 444 curlp = lp; 445 while (size--) { 446 c = (unsigned char)*lp++; 447 if (!ISTHERE(c)) 448 break; 449 } 450 if (size < 0) 451 lp++; 452 ep += 34; /* 32 + 2 */ 453 goto star; 454 /*FALLTHRU*/ 455 456 case NCCL | RNGE: 457 neg = 1; 458 /*FALLTHRU*/ 459 460 case CCL | RNGE: 461 getrnge(ep + 16); 462 while (low--) { 463 c = *lp++; 464 if (((c & 0200) || !ISTHERE(c)) ^ neg) 465 return (0); 466 } 467 curlp = lp; 468 while (size--) { 469 c = *lp++; 470 if (((c & 0200) || !ISTHERE(c)) ^ neg) 471 break; 472 } 473 if (size < 0) 474 lp++; 475 ep += 18; /* 16 + 2 */ 476 goto star; 477 /*FALLTHRU*/ 478 479 case CBACK: 480 bbeg = braslist[*ep]; 481 ct = braelist[*ep++] - bbeg; 482 483 if (ecmp(bbeg, lp, ct)) { 484 lp += ct; 485 continue; 486 } 487 return (0); 488 /*FALLTHRU*/ 489 490 case CBACK | STAR: 491 bbeg = braslist[*ep]; 492 ct = braelist[*ep++] - bbeg; 493 curlp = lp; 494 while (ecmp(bbeg, lp, ct)) 495 lp += ct; 496 497 while (lp >= curlp) { 498 if (advance(lp, ep)) 499 return (1); 500 lp -= ct; 501 } 502 return (0); 503 /*FALLTHRU*/ 504 505 case CDOT | STAR: 506 curlp = lp; 507 while (*lp++); 508 goto star; 509 /*FALLTHRU*/ 510 511 case CCHR | STAR: 512 curlp = lp; 513 while (*lp++ == *ep); 514 ep++; 515 goto star; 516 /*FALLTHRU*/ 517 518 case CXCL | STAR: 519 curlp = lp; 520 do { 521 c = (unsigned char)*lp++; 522 } while (ISTHERE(c)); 523 ep += 32; 524 goto star; 525 /*FALLTHRU*/ 526 527 case NCCL | STAR: 528 neg = 1; 529 /*FALLTHRU*/ 530 531 case CCL | STAR: 532 curlp = lp; 533 do { 534 c = *lp++; 535 } while (((c & 0200) == 0 && ISTHERE(c)) ^ neg); 536 ep += 16; 537 goto star; 538 /*FALLTHRU*/ 539 540 star: 541 do { 542 if (--lp == locs) 543 break; 544 if (advance(lp, ep)) 545 return (1); 546 } while (lp > curlp); 547 return (0); 548 549 } 550 } 551 /*NOTREACHED*/ 552 } 553 554 static void 555 getrnge(const char *str) 556 { 557 low = *str++ & 0377; 558 size = ((*str & 0377) == 255)? 20000: (*str &0377) - low; 559 } 560 561 #ifdef __cplusplus 562 } 563 #endif 564 565 #endif /* _REGEXP_H */ 566