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