regcomp.c revision 17141
1/*- 2 * Copyright (c) 1992, 1993, 1994 Henry Spencer. 3 * Copyright (c) 1992, 1993, 1994 4 * The Regents of the University of California. All rights reserved. 5 * 6 * This code is derived from software contributed to Berkeley by 7 * Henry Spencer. 8 * 9 * Redistribution and use in source and binary forms, with or without 10 * modification, are permitted provided that the following conditions 11 * are met: 12 * 1. Redistributions of source code must retain the above copyright 13 * notice, this list of conditions and the following disclaimer. 14 * 2. Redistributions in binary form must reproduce the above copyright 15 * notice, this list of conditions and the following disclaimer in the 16 * documentation and/or other materials provided with the distribution. 17 * 3. All advertising materials mentioning features or use of this software 18 * must display the following acknowledgement: 19 * This product includes software developed by the University of 20 * California, Berkeley and its contributors. 21 * 4. Neither the name of the University nor the names of its contributors 22 * may be used to endorse or promote products derived from this software 23 * without specific prior written permission. 24 * 25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND 26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE 29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 35 * SUCH DAMAGE. 36 * 37 * @(#)regcomp.c 8.5 (Berkeley) 3/20/94 38 */ 39 40#if defined(LIBC_SCCS) && !defined(lint) 41static char sccsid[] = "@(#)regcomp.c 8.5 (Berkeley) 3/20/94"; 42#endif /* LIBC_SCCS and not lint */ 43 44#include <sys/types.h> 45#include <stdio.h> 46#include <string.h> 47#include <ctype.h> 48#include <limits.h> 49#include <stdlib.h> 50#include <regex.h> 51 52#include "utils.h" 53#include "regex2.h" 54 55#include "cclass.h" 56#include "cname.h" 57 58/* 59 * parse structure, passed up and down to avoid global variables and 60 * other clumsinesses 61 */ 62struct parse { 63 char *next; /* next character in RE */ 64 char *end; /* end of string (-> NUL normally) */ 65 int error; /* has an error been seen? */ 66 sop *strip; /* malloced strip */ 67 sopno ssize; /* malloced strip size (allocated) */ 68 sopno slen; /* malloced strip length (used) */ 69 int ncsalloc; /* number of csets allocated */ 70 struct re_guts *g; 71# define NPAREN 10 /* we need to remember () 1-9 for back refs */ 72 sopno pbegin[NPAREN]; /* -> ( ([0] unused) */ 73 sopno pend[NPAREN]; /* -> ) ([0] unused) */ 74}; 75 76/* ========= begin header generated by ./mkh ========= */ 77#ifdef __cplusplus 78extern "C" { 79#endif 80 81/* === regcomp.c === */ 82static void p_ere __P((struct parse *p, int stop)); 83static void p_ere_exp __P((struct parse *p)); 84static void p_str __P((struct parse *p)); 85static void p_bre __P((struct parse *p, int end1, int end2)); 86static int p_simp_re __P((struct parse *p, int starordinary)); 87static int p_count __P((struct parse *p)); 88static void p_bracket __P((struct parse *p)); 89static void p_b_term __P((struct parse *p, cset *cs)); 90static void p_b_cclass __P((struct parse *p, cset *cs)); 91static void p_b_eclass __P((struct parse *p, cset *cs)); 92static char p_b_symbol __P((struct parse *p)); 93static char p_b_coll_elem __P((struct parse *p, int endc)); 94static char othercase __P((int ch)); 95static void bothcases __P((struct parse *p, int ch)); 96static void ordinary __P((struct parse *p, int ch)); 97static void nonnewline __P((struct parse *p)); 98static void repeat __P((struct parse *p, sopno start, int from, int to)); 99static int seterr __P((struct parse *p, int e)); 100static cset *allocset __P((struct parse *p)); 101static void freeset __P((struct parse *p, cset *cs)); 102static int freezeset __P((struct parse *p, cset *cs)); 103static int firstch __P((struct parse *p, cset *cs)); 104static int nch __P((struct parse *p, cset *cs)); 105static void mcadd __P((struct parse *p, cset *cs, char *cp)); 106#if used 107static void mcsub __P((cset *cs, char *cp)); 108static int mcin __P((cset *cs, char *cp)); 109static char *mcfind __P((cset *cs, char *cp)); 110#endif 111static void mcinvert __P((struct parse *p, cset *cs)); 112static void mccase __P((struct parse *p, cset *cs)); 113static int isinsets __P((struct re_guts *g, int c)); 114static int samesets __P((struct re_guts *g, int c1, int c2)); 115static void categorize __P((struct parse *p, struct re_guts *g)); 116static sopno dupl __P((struct parse *p, sopno start, sopno finish)); 117static void doemit __P((struct parse *p, sop op, size_t opnd)); 118static void doinsert __P((struct parse *p, sop op, size_t opnd, sopno pos)); 119static void dofwd __P((struct parse *p, sopno pos, sop value)); 120static void enlarge __P((struct parse *p, sopno size)); 121static void stripsnug __P((struct parse *p, struct re_guts *g)); 122static void findmust __P((struct parse *p, struct re_guts *g)); 123static sopno pluscount __P((struct parse *p, struct re_guts *g)); 124 125#ifdef __cplusplus 126} 127#endif 128/* ========= end header generated by ./mkh ========= */ 129 130static char nuls[10]; /* place to point scanner in event of error */ 131 132/* 133 * macros for use with parse structure 134 * BEWARE: these know that the parse structure is named `p' !!! 135 */ 136#define PEEK() (*p->next) 137#define PEEK2() (*(p->next+1)) 138#define MORE() (p->next < p->end) 139#define MORE2() (p->next+1 < p->end) 140#define SEE(c) (MORE() && PEEK() == (c)) 141#define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b)) 142#define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0) 143#define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0) 144#define NEXT() (p->next++) 145#define NEXT2() (p->next += 2) 146#define NEXTn(n) (p->next += (n)) 147#define GETNEXT() (*p->next++) 148#define SETERROR(e) seterr(p, (e)) 149#define REQUIRE(co, e) ((co) || SETERROR(e)) 150#define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e)) 151#define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e)) 152#define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e)) 153#define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd)) 154#define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos) 155#define AHEAD(pos) dofwd(p, pos, HERE()-(pos)) 156#define ASTERN(sop, pos) EMIT(sop, HERE()-pos) 157#define HERE() (p->slen) 158#define THERE() (p->slen - 1) 159#define THERETHERE() (p->slen - 2) 160#define DROP(n) (p->slen -= (n)) 161 162#ifndef NDEBUG 163static int never = 0; /* for use in asserts; shuts lint up */ 164#else 165#define never 0 /* some <assert.h>s have bugs too */ 166#endif 167 168/* 169 - regcomp - interface for parser and compilation 170 = extern int regcomp(regex_t *, const char *, int); 171 = #define REG_BASIC 0000 172 = #define REG_EXTENDED 0001 173 = #define REG_ICASE 0002 174 = #define REG_NOSUB 0004 175 = #define REG_NEWLINE 0010 176 = #define REG_NOSPEC 0020 177 = #define REG_PEND 0040 178 = #define REG_DUMP 0200 179 */ 180int /* 0 success, otherwise REG_something */ 181regcomp(preg, pattern, cflags) 182regex_t *preg; 183const char *pattern; 184int cflags; 185{ 186 struct parse pa; 187 register struct re_guts *g; 188 register struct parse *p = &pa; 189 register int i; 190 register size_t len; 191#ifdef REDEBUG 192# define GOODFLAGS(f) (f) 193#else 194# define GOODFLAGS(f) ((f)&~REG_DUMP) 195#endif 196 197 cflags = GOODFLAGS(cflags); 198 if ((cflags®_EXTENDED) && (cflags®_NOSPEC)) 199 return(REG_INVARG); 200 201 if (cflags®_PEND) { 202 if (preg->re_endp < pattern) 203 return(REG_INVARG); 204 len = preg->re_endp - pattern; 205 } else 206 len = strlen((char *)pattern); 207 208 /* do the mallocs early so failure handling is easy */ 209 g = (struct re_guts *)malloc(sizeof(struct re_guts) + 210 (NC-1)*sizeof(cat_t)); 211 if (g == NULL) 212 return(REG_ESPACE); 213 p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */ 214 p->strip = (sop *)malloc(p->ssize * sizeof(sop)); 215 p->slen = 0; 216 if (p->strip == NULL) { 217 free((char *)g); 218 return(REG_ESPACE); 219 } 220 221 /* set things up */ 222 p->g = g; 223 p->next = (char *)pattern; /* convenience; we do not modify it */ 224 p->end = p->next + len; 225 p->error = 0; 226 p->ncsalloc = 0; 227 for (i = 0; i < NPAREN; i++) { 228 p->pbegin[i] = 0; 229 p->pend[i] = 0; 230 } 231 g->csetsize = NC; 232 g->sets = NULL; 233 g->setbits = NULL; 234 g->ncsets = 0; 235 g->cflags = cflags; 236 g->iflags = 0; 237 g->nbol = 0; 238 g->neol = 0; 239 g->must = NULL; 240 g->mlen = 0; 241 g->nsub = 0; 242 g->ncategories = 1; /* category 0 is "everything else" */ 243 g->categories = &g->catspace[-(CHAR_MIN)]; 244 (void) memset((char *)g->catspace, 0, NC*sizeof(cat_t)); 245 g->backrefs = 0; 246 247 /* do it */ 248 EMIT(OEND, 0); 249 g->firststate = THERE(); 250 if (cflags®_EXTENDED) 251 p_ere(p, OUT); 252 else if (cflags®_NOSPEC) 253 p_str(p); 254 else 255 p_bre(p, OUT, OUT); 256 EMIT(OEND, 0); 257 g->laststate = THERE(); 258 259 /* tidy up loose ends and fill things in */ 260 categorize(p, g); 261 stripsnug(p, g); 262 findmust(p, g); 263 g->nplus = pluscount(p, g); 264 g->magic = MAGIC2; 265 preg->re_nsub = g->nsub; 266 preg->re_g = g; 267 preg->re_magic = MAGIC1; 268#ifndef REDEBUG 269 /* not debugging, so can't rely on the assert() in regexec() */ 270 if (g->iflags&BAD) 271 SETERROR(REG_ASSERT); 272#endif 273 274 /* win or lose, we're done */ 275 if (p->error != 0) /* lose */ 276 regfree(preg); 277 return(p->error); 278} 279 280/* 281 - p_ere - ERE parser top level, concatenation and alternation 282 == static void p_ere(register struct parse *p, int stop); 283 */ 284static void 285p_ere(p, stop) 286register struct parse *p; 287int stop; /* character this ERE should end at */ 288{ 289 register char c; 290 register sopno prevback; 291 register sopno prevfwd; 292 register sopno conc; 293 register int first = 1; /* is this the first alternative? */ 294 295 for (;;) { 296 /* do a bunch of concatenated expressions */ 297 conc = HERE(); 298 while (MORE() && (c = PEEK()) != '|' && c != stop) 299 p_ere_exp(p); 300 (void)REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */ 301 302 if (!EAT('|')) 303 break; /* NOTE BREAK OUT */ 304 305 if (first) { 306 INSERT(OCH_, conc); /* offset is wrong */ 307 prevfwd = conc; 308 prevback = conc; 309 first = 0; 310 } 311 ASTERN(OOR1, prevback); 312 prevback = THERE(); 313 AHEAD(prevfwd); /* fix previous offset */ 314 prevfwd = HERE(); 315 EMIT(OOR2, 0); /* offset is very wrong */ 316 } 317 318 if (!first) { /* tail-end fixups */ 319 AHEAD(prevfwd); 320 ASTERN(O_CH, prevback); 321 } 322 323 assert(!MORE() || SEE(stop)); 324} 325 326/* 327 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op 328 == static void p_ere_exp(register struct parse *p); 329 */ 330static void 331p_ere_exp(p) 332register struct parse *p; 333{ 334 register char c; 335 register sopno pos; 336 register int count; 337 register int count2; 338 register sopno subno; 339 int wascaret = 0; 340 341 assert(MORE()); /* caller should have ensured this */ 342 c = GETNEXT(); 343 344 pos = HERE(); 345 switch (c) { 346 case '(': 347 (void)REQUIRE(MORE(), REG_EPAREN); 348 p->g->nsub++; 349 subno = p->g->nsub; 350 if (subno < NPAREN) 351 p->pbegin[subno] = HERE(); 352 EMIT(OLPAREN, subno); 353 if (!SEE(')')) 354 p_ere(p, ')'); 355 if (subno < NPAREN) { 356 p->pend[subno] = HERE(); 357 assert(p->pend[subno] != 0); 358 } 359 EMIT(ORPAREN, subno); 360 (void)MUSTEAT(')', REG_EPAREN); 361 break; 362#ifndef POSIX_MISTAKE 363 case ')': /* happens only if no current unmatched ( */ 364 /* 365 * You may ask, why the ifndef? Because I didn't notice 366 * this until slightly too late for 1003.2, and none of the 367 * other 1003.2 regular-expression reviewers noticed it at 368 * all. So an unmatched ) is legal POSIX, at least until 369 * we can get it fixed. 370 */ 371 SETERROR(REG_EPAREN); 372 break; 373#endif 374 case '^': 375 EMIT(OBOL, 0); 376 p->g->iflags |= USEBOL; 377 p->g->nbol++; 378 wascaret = 1; 379 break; 380 case '$': 381 EMIT(OEOL, 0); 382 p->g->iflags |= USEEOL; 383 p->g->neol++; 384 break; 385 case '|': 386 SETERROR(REG_EMPTY); 387 break; 388 case '*': 389 case '+': 390 case '?': 391 SETERROR(REG_BADRPT); 392 break; 393 case '.': 394 if (p->g->cflags®_NEWLINE) 395 nonnewline(p); 396 else 397 EMIT(OANY, 0); 398 break; 399 case '[': 400 p_bracket(p); 401 break; 402 case '\\': 403 (void)REQUIRE(MORE(), REG_EESCAPE); 404 c = GETNEXT(); 405 ordinary(p, c); 406 break; 407 case '{': /* okay as ordinary except if digit follows */ 408 (void)REQUIRE(!MORE() || !isdigit(PEEK()), REG_BADRPT); 409 /* FALLTHROUGH */ 410 default: 411 ordinary(p, c); 412 break; 413 } 414 415 if (!MORE()) 416 return; 417 c = PEEK(); 418 /* we call { a repetition if followed by a digit */ 419 if (!( c == '*' || c == '+' || c == '?' || 420 (c == '{' && MORE2() && isdigit(PEEK2())) )) 421 return; /* no repetition, we're done */ 422 NEXT(); 423 424 (void)REQUIRE(!wascaret, REG_BADRPT); 425 switch (c) { 426 case '*': /* implemented as +? */ 427 /* this case does not require the (y|) trick, noKLUDGE */ 428 INSERT(OPLUS_, pos); 429 ASTERN(O_PLUS, pos); 430 INSERT(OQUEST_, pos); 431 ASTERN(O_QUEST, pos); 432 break; 433 case '+': 434 INSERT(OPLUS_, pos); 435 ASTERN(O_PLUS, pos); 436 break; 437 case '?': 438 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 439 INSERT(OCH_, pos); /* offset slightly wrong */ 440 ASTERN(OOR1, pos); /* this one's right */ 441 AHEAD(pos); /* fix the OCH_ */ 442 EMIT(OOR2, 0); /* offset very wrong... */ 443 AHEAD(THERE()); /* ...so fix it */ 444 ASTERN(O_CH, THERETHERE()); 445 break; 446 case '{': 447 count = p_count(p); 448 if (EAT(',')) { 449 if (isdigit(PEEK())) { 450 count2 = p_count(p); 451 (void)REQUIRE(count <= count2, REG_BADBR); 452 } else /* single number with comma */ 453 count2 = INFINITY; 454 } else /* just a single number */ 455 count2 = count; 456 repeat(p, pos, count, count2); 457 if (!EAT('}')) { /* error heuristics */ 458 while (MORE() && PEEK() != '}') 459 NEXT(); 460 (void)REQUIRE(MORE(), REG_EBRACE); 461 SETERROR(REG_BADBR); 462 } 463 break; 464 } 465 466 if (!MORE()) 467 return; 468 c = PEEK(); 469 if (!( c == '*' || c == '+' || c == '?' || 470 (c == '{' && MORE2() && isdigit(PEEK2())) ) ) 471 return; 472 SETERROR(REG_BADRPT); 473} 474 475/* 476 - p_str - string (no metacharacters) "parser" 477 == static void p_str(register struct parse *p); 478 */ 479static void 480p_str(p) 481register struct parse *p; 482{ 483 (void)REQUIRE(MORE(), REG_EMPTY); 484 while (MORE()) 485 ordinary(p, GETNEXT()); 486} 487 488/* 489 - p_bre - BRE parser top level, anchoring and concatenation 490 == static void p_bre(register struct parse *p, register int end1, \ 491 == register int end2); 492 * Giving end1 as OUT essentially eliminates the end1/end2 check. 493 * 494 * This implementation is a bit of a kludge, in that a trailing $ is first 495 * taken as an ordinary character and then revised to be an anchor. The 496 * only undesirable side effect is that '$' gets included as a character 497 * category in such cases. This is fairly harmless; not worth fixing. 498 * The amount of lookahead needed to avoid this kludge is excessive. 499 */ 500static void 501p_bre(p, end1, end2) 502register struct parse *p; 503register int end1; /* first terminating character */ 504register int end2; /* second terminating character */ 505{ 506 register sopno start = HERE(); 507 register int first = 1; /* first subexpression? */ 508 register int wasdollar = 0; 509 510 if (EAT('^')) { 511 EMIT(OBOL, 0); 512 p->g->iflags |= USEBOL; 513 p->g->nbol++; 514 } 515 while (MORE() && !SEETWO(end1, end2)) { 516 wasdollar = p_simp_re(p, first); 517 first = 0; 518 } 519 if (wasdollar) { /* oops, that was a trailing anchor */ 520 DROP(1); 521 EMIT(OEOL, 0); 522 p->g->iflags |= USEEOL; 523 p->g->neol++; 524 } 525 526 (void)REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */ 527} 528 529/* 530 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition 531 == static int p_simp_re(register struct parse *p, int starordinary); 532 */ 533static int /* was the simple RE an unbackslashed $? */ 534p_simp_re(p, starordinary) 535register struct parse *p; 536int starordinary; /* is a leading * an ordinary character? */ 537{ 538 register int c; 539 register int count; 540 register int count2; 541 register sopno pos; 542 register int i; 543 register sopno subno; 544# define BACKSL (1<<CHAR_BIT) 545 546 pos = HERE(); /* repetion op, if any, covers from here */ 547 548 assert(MORE()); /* caller should have ensured this */ 549 c = GETNEXT(); 550 if (c == '\\') { 551 (void)REQUIRE(MORE(), REG_EESCAPE); 552 c = BACKSL | (unsigned char)GETNEXT(); 553 } 554 switch (c) { 555 case '.': 556 if (p->g->cflags®_NEWLINE) 557 nonnewline(p); 558 else 559 EMIT(OANY, 0); 560 break; 561 case '[': 562 p_bracket(p); 563 break; 564 case BACKSL|'{': 565 SETERROR(REG_BADRPT); 566 break; 567 case BACKSL|'(': 568 p->g->nsub++; 569 subno = p->g->nsub; 570 if (subno < NPAREN) 571 p->pbegin[subno] = HERE(); 572 EMIT(OLPAREN, subno); 573 /* the MORE here is an error heuristic */ 574 if (MORE() && !SEETWO('\\', ')')) 575 p_bre(p, '\\', ')'); 576 if (subno < NPAREN) { 577 p->pend[subno] = HERE(); 578 assert(p->pend[subno] != 0); 579 } 580 EMIT(ORPAREN, subno); 581 (void)REQUIRE(EATTWO('\\', ')'), REG_EPAREN); 582 break; 583 case BACKSL|')': /* should not get here -- must be user */ 584 case BACKSL|'}': 585 SETERROR(REG_EPAREN); 586 break; 587 case BACKSL|'1': 588 case BACKSL|'2': 589 case BACKSL|'3': 590 case BACKSL|'4': 591 case BACKSL|'5': 592 case BACKSL|'6': 593 case BACKSL|'7': 594 case BACKSL|'8': 595 case BACKSL|'9': 596 i = (c&~BACKSL) - '0'; 597 assert(i < NPAREN); 598 if (p->pend[i] != 0) { 599 assert(i <= p->g->nsub); 600 EMIT(OBACK_, i); 601 assert(p->pbegin[i] != 0); 602 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN); 603 assert(OP(p->strip[p->pend[i]]) == ORPAREN); 604 (void) dupl(p, p->pbegin[i]+1, p->pend[i]); 605 EMIT(O_BACK, i); 606 } else 607 SETERROR(REG_ESUBREG); 608 p->g->backrefs = 1; 609 break; 610 case '*': 611 (void)REQUIRE(starordinary, REG_BADRPT); 612 /* FALLTHROUGH */ 613 default: 614 ordinary(p, c &~ BACKSL); 615 break; 616 } 617 618 if (EAT('*')) { /* implemented as +? */ 619 /* this case does not require the (y|) trick, noKLUDGE */ 620 INSERT(OPLUS_, pos); 621 ASTERN(O_PLUS, pos); 622 INSERT(OQUEST_, pos); 623 ASTERN(O_QUEST, pos); 624 } else if (EATTWO('\\', '{')) { 625 count = p_count(p); 626 if (EAT(',')) { 627 if (MORE() && isdigit(PEEK())) { 628 count2 = p_count(p); 629 (void)REQUIRE(count <= count2, REG_BADBR); 630 } else /* single number with comma */ 631 count2 = INFINITY; 632 } else /* just a single number */ 633 count2 = count; 634 repeat(p, pos, count, count2); 635 if (!EATTWO('\\', '}')) { /* error heuristics */ 636 while (MORE() && !SEETWO('\\', '}')) 637 NEXT(); 638 (void)REQUIRE(MORE(), REG_EBRACE); 639 SETERROR(REG_BADBR); 640 } 641 } else if (c == (unsigned char)'$') /* $ (but not \$) ends it */ 642 return(1); 643 644 return(0); 645} 646 647/* 648 - p_count - parse a repetition count 649 == static int p_count(register struct parse *p); 650 */ 651static int /* the value */ 652p_count(p) 653register struct parse *p; 654{ 655 register int count = 0; 656 register int ndigits = 0; 657 658 while (MORE() && isdigit(PEEK()) && count <= DUPMAX) { 659 count = count*10 + (GETNEXT() - '0'); 660 ndigits++; 661 } 662 663 (void)REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR); 664 return(count); 665} 666 667/* 668 - p_bracket - parse a bracketed character list 669 == static void p_bracket(register struct parse *p); 670 * 671 * Note a significant property of this code: if the allocset() did SETERROR, 672 * no set operations are done. 673 */ 674static void 675p_bracket(p) 676register struct parse *p; 677{ 678 register cset *cs = allocset(p); 679 register int invert = 0; 680 681 /* Dept of Truly Sickening Special-Case Kludges */ 682 if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) { 683 EMIT(OBOW, 0); 684 NEXTn(6); 685 return; 686 } 687 if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) { 688 EMIT(OEOW, 0); 689 NEXTn(6); 690 return; 691 } 692 693 if (EAT('^')) 694 invert++; /* make note to invert set at end */ 695 if (EAT(']')) 696 CHadd(cs, ']'); 697 else if (EAT('-')) 698 CHadd(cs, '-'); 699 while (MORE() && PEEK() != ']' && !SEETWO('-', ']')) 700 p_b_term(p, cs); 701 if (EAT('-')) 702 CHadd(cs, '-'); 703 (void)MUSTEAT(']', REG_EBRACK); 704 705 if (p->error != 0) /* don't mess things up further */ 706 return; 707 708 if (p->g->cflags®_ICASE) { 709 register int i; 710 register int ci; 711 712 for (i = p->g->csetsize - 1; i >= 0; i--) 713 if (CHIN(cs, i) && isalpha(i)) { 714 ci = othercase(i); 715 if (ci != i) 716 CHadd(cs, ci); 717 } 718 if (cs->multis != NULL) 719 mccase(p, cs); 720 } 721 if (invert) { 722 register int i; 723 724 for (i = p->g->csetsize - 1; i >= 0; i--) 725 if (CHIN(cs, i)) 726 CHsub(cs, i); 727 else 728 CHadd(cs, i); 729 if (p->g->cflags®_NEWLINE) 730 CHsub(cs, '\n'); 731 if (cs->multis != NULL) 732 mcinvert(p, cs); 733 } 734 735 assert(cs->multis == NULL); /* xxx */ 736 737 if (nch(p, cs) == 1) { /* optimize singleton sets */ 738 ordinary(p, firstch(p, cs)); 739 freeset(p, cs); 740 } else 741 EMIT(OANYOF, freezeset(p, cs)); 742} 743 744/* 745 - p_b_term - parse one term of a bracketed character list 746 == static void p_b_term(register struct parse *p, register cset *cs); 747 */ 748static void 749p_b_term(p, cs) 750register struct parse *p; 751register cset *cs; 752{ 753 register char c; 754 register char start, finish; 755 register int i; 756 757 /* classify what we've got */ 758 switch ((MORE()) ? PEEK() : '\0') { 759 case '[': 760 c = (MORE2()) ? PEEK2() : '\0'; 761 break; 762 case '-': 763 SETERROR(REG_ERANGE); 764 return; /* NOTE RETURN */ 765 break; 766 default: 767 c = '\0'; 768 break; 769 } 770 771 switch (c) { 772 case ':': /* character class */ 773 NEXT2(); 774 (void)REQUIRE(MORE(), REG_EBRACK); 775 c = PEEK(); 776 (void)REQUIRE(c != '-' && c != ']', REG_ECTYPE); 777 p_b_cclass(p, cs); 778 (void)REQUIRE(MORE(), REG_EBRACK); 779 (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE); 780 break; 781 case '=': /* equivalence class */ 782 NEXT2(); 783 (void)REQUIRE(MORE(), REG_EBRACK); 784 c = PEEK(); 785 (void)REQUIRE(c != '-' && c != ']', REG_ECOLLATE); 786 p_b_eclass(p, cs); 787 (void)REQUIRE(MORE(), REG_EBRACK); 788 (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE); 789 break; 790 default: /* symbol, ordinary character, or range */ 791/* xxx revision needed for multichar stuff */ 792 start = p_b_symbol(p); 793 if (SEE('-') && MORE2() && PEEK2() != ']') { 794 /* range */ 795 NEXT(); 796 if (EAT('-')) 797 finish = '-'; 798 else 799 finish = p_b_symbol(p); 800 } else 801 finish = start; 802/* xxx what about signed chars here... */ 803 (void)REQUIRE(start <= finish, REG_ERANGE); 804 for (i = start; i <= finish; i++) 805 CHadd(cs, i); 806 break; 807 } 808} 809 810/* 811 - p_b_cclass - parse a character-class name and deal with it 812 == static void p_b_cclass(register struct parse *p, register cset *cs); 813 */ 814static void 815p_b_cclass(p, cs) 816register struct parse *p; 817register cset *cs; 818{ 819 register char *sp = p->next; 820 register struct cclass *cp; 821 register size_t len; 822 register char *u; 823 register char c; 824 825 while (MORE() && isalpha((unsigned char)PEEK())) 826 NEXT(); 827 len = p->next - sp; 828 for (cp = cclasses; cp->name != NULL; cp++) 829 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') 830 break; 831 if (cp->name == NULL) { 832 /* oops, didn't find it */ 833 SETERROR(REG_ECTYPE); 834 return; 835 } 836 837 u = cp->chars; 838 while ((c = *u++) != '\0') 839 CHadd(cs, c); 840 for (u = cp->multis; *u != '\0'; u += strlen(u) + 1) 841 MCadd(p, cs, u); 842} 843 844/* 845 - p_b_eclass - parse an equivalence-class name and deal with it 846 == static void p_b_eclass(register struct parse *p, register cset *cs); 847 * 848 * This implementation is incomplete. xxx 849 */ 850static void 851p_b_eclass(p, cs) 852register struct parse *p; 853register cset *cs; 854{ 855 register char c; 856 857 c = p_b_coll_elem(p, '='); 858 CHadd(cs, c); 859} 860 861/* 862 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol 863 == static char p_b_symbol(register struct parse *p); 864 */ 865static char /* value of symbol */ 866p_b_symbol(p) 867register struct parse *p; 868{ 869 register char value; 870 871 (void)REQUIRE(MORE(), REG_EBRACK); 872 if (!EATTWO('[', '.')) 873 return(GETNEXT()); 874 875 /* collating symbol */ 876 value = p_b_coll_elem(p, '.'); 877 (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE); 878 return(value); 879} 880 881/* 882 - p_b_coll_elem - parse a collating-element name and look it up 883 == static char p_b_coll_elem(register struct parse *p, int endc); 884 */ 885static char /* value of collating element */ 886p_b_coll_elem(p, endc) 887register struct parse *p; 888int endc; /* name ended by endc,']' */ 889{ 890 register char *sp = p->next; 891 register struct cname *cp; 892 register int len; 893 894 while (MORE() && !SEETWO(endc, ']')) 895 NEXT(); 896 if (!MORE()) { 897 SETERROR(REG_EBRACK); 898 return(0); 899 } 900 len = p->next - sp; 901 for (cp = cnames; cp->name != NULL; cp++) 902 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0') 903 return(cp->code); /* known name */ 904 if (len == 1) 905 return(*sp); /* single character */ 906 SETERROR(REG_ECOLLATE); /* neither */ 907 return(0); 908} 909 910/* 911 - othercase - return the case counterpart of an alphabetic 912 == static char othercase(int ch); 913 */ 914static char /* if no counterpart, return ch */ 915othercase(ch) 916int ch; 917{ 918 ch = (unsigned char)ch; 919 assert(isalpha(ch)); 920 if (isupper(ch)) 921 return(tolower(ch)); 922 else if (islower(ch)) 923 return(toupper(ch)); 924 else /* peculiar, but could happen */ 925 return(ch); 926} 927 928/* 929 - bothcases - emit a dualcase version of a two-case character 930 == static void bothcases(register struct parse *p, int ch); 931 * 932 * Boy, is this implementation ever a kludge... 933 */ 934static void 935bothcases(p, ch) 936register struct parse *p; 937int ch; 938{ 939 register char *oldnext = p->next; 940 register char *oldend = p->end; 941 char bracket[3]; 942 943 ch = (unsigned char)ch; 944 assert(othercase(ch) != ch); /* p_bracket() would recurse */ 945 p->next = bracket; 946 p->end = bracket+2; 947 bracket[0] = ch; 948 bracket[1] = ']'; 949 bracket[2] = '\0'; 950 p_bracket(p); 951 assert(p->next == bracket+2); 952 p->next = oldnext; 953 p->end = oldend; 954} 955 956/* 957 - ordinary - emit an ordinary character 958 == static void ordinary(register struct parse *p, register int ch); 959 */ 960static void 961ordinary(p, ch) 962register struct parse *p; 963register int ch; 964{ 965 register cat_t *cap = p->g->categories; 966 967 if ((p->g->cflags®_ICASE) && isalpha((unsigned char)ch) && othercase(ch) != ch) 968 bothcases(p, ch); 969 else { 970 EMIT(OCHAR, (unsigned char)ch); 971 if (cap[ch] == 0) 972 cap[ch] = p->g->ncategories++; 973 } 974} 975 976/* 977 - nonnewline - emit REG_NEWLINE version of OANY 978 == static void nonnewline(register struct parse *p); 979 * 980 * Boy, is this implementation ever a kludge... 981 */ 982static void 983nonnewline(p) 984register struct parse *p; 985{ 986 register char *oldnext = p->next; 987 register char *oldend = p->end; 988 char bracket[4]; 989 990 p->next = bracket; 991 p->end = bracket+3; 992 bracket[0] = '^'; 993 bracket[1] = '\n'; 994 bracket[2] = ']'; 995 bracket[3] = '\0'; 996 p_bracket(p); 997 assert(p->next == bracket+3); 998 p->next = oldnext; 999 p->end = oldend; 1000} 1001 1002/* 1003 - repeat - generate code for a bounded repetition, recursively if needed 1004 == static void repeat(register struct parse *p, sopno start, int from, int to); 1005 */ 1006static void 1007repeat(p, start, from, to) 1008register struct parse *p; 1009sopno start; /* operand from here to end of strip */ 1010int from; /* repeated from this number */ 1011int to; /* to this number of times (maybe INFINITY) */ 1012{ 1013 register sopno finish = HERE(); 1014# define N 2 1015# define INF 3 1016# define REP(f, t) ((f)*8 + (t)) 1017# define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N) 1018 register sopno copy; 1019 1020 if (p->error != 0) /* head off possible runaway recursion */ 1021 return; 1022 1023 assert(from <= to); 1024 1025 switch (REP(MAP(from), MAP(to))) { 1026 case REP(0, 0): /* must be user doing this */ 1027 DROP(finish-start); /* drop the operand */ 1028 break; 1029 case REP(0, 1): /* as x{1,1}? */ 1030 case REP(0, N): /* as x{1,n}? */ 1031 case REP(0, INF): /* as x{1,}? */ 1032 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 1033 INSERT(OCH_, start); /* offset is wrong... */ 1034 repeat(p, start+1, 1, to); 1035 ASTERN(OOR1, start); 1036 AHEAD(start); /* ... fix it */ 1037 EMIT(OOR2, 0); 1038 AHEAD(THERE()); 1039 ASTERN(O_CH, THERETHERE()); 1040 break; 1041 case REP(1, 1): /* trivial case */ 1042 /* done */ 1043 break; 1044 case REP(1, N): /* as x?x{1,n-1} */ 1045 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */ 1046 INSERT(OCH_, start); 1047 ASTERN(OOR1, start); 1048 AHEAD(start); 1049 EMIT(OOR2, 0); /* offset very wrong... */ 1050 AHEAD(THERE()); /* ...so fix it */ 1051 ASTERN(O_CH, THERETHERE()); 1052 copy = dupl(p, start+1, finish+1); 1053 assert(copy == finish+4); 1054 repeat(p, copy, 1, to-1); 1055 break; 1056 case REP(1, INF): /* as x+ */ 1057 INSERT(OPLUS_, start); 1058 ASTERN(O_PLUS, start); 1059 break; 1060 case REP(N, N): /* as xx{m-1,n-1} */ 1061 copy = dupl(p, start, finish); 1062 repeat(p, copy, from-1, to-1); 1063 break; 1064 case REP(N, INF): /* as xx{n-1,INF} */ 1065 copy = dupl(p, start, finish); 1066 repeat(p, copy, from-1, to); 1067 break; 1068 default: /* "can't happen" */ 1069 SETERROR(REG_ASSERT); /* just in case */ 1070 break; 1071 } 1072} 1073 1074/* 1075 - seterr - set an error condition 1076 == static int seterr(register struct parse *p, int e); 1077 */ 1078static int /* useless but makes type checking happy */ 1079seterr(p, e) 1080register struct parse *p; 1081int e; 1082{ 1083 if (p->error == 0) /* keep earliest error condition */ 1084 p->error = e; 1085 p->next = nuls; /* try to bring things to a halt */ 1086 p->end = nuls; 1087 return(0); /* make the return value well-defined */ 1088} 1089 1090/* 1091 - allocset - allocate a set of characters for [] 1092 == static cset *allocset(register struct parse *p); 1093 */ 1094static cset * 1095allocset(p) 1096register struct parse *p; 1097{ 1098 register int no = p->g->ncsets++; 1099 register size_t nc; 1100 register size_t nbytes; 1101 register cset *cs; 1102 register size_t css = (size_t)p->g->csetsize; 1103 register int i; 1104 1105 if (no >= p->ncsalloc) { /* need another column of space */ 1106 p->ncsalloc += CHAR_BIT; 1107 nc = p->ncsalloc; 1108 assert(nc % CHAR_BIT == 0); 1109 nbytes = nc / CHAR_BIT * css; 1110 if (p->g->sets == NULL) 1111 p->g->sets = (cset *)malloc(nc * sizeof(cset)); 1112 else 1113 p->g->sets = (cset *)realloc((char *)p->g->sets, 1114 nc * sizeof(cset)); 1115 if (p->g->setbits == NULL) 1116 p->g->setbits = (uch *)malloc(nbytes); 1117 else { 1118 p->g->setbits = (uch *)realloc((char *)p->g->setbits, 1119 nbytes); 1120 /* xxx this isn't right if setbits is now NULL */ 1121 for (i = 0; i < no; i++) 1122 p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT); 1123 } 1124 if (p->g->sets != NULL && p->g->setbits != NULL) 1125 (void) memset((char *)p->g->setbits + (nbytes - css), 1126 0, css); 1127 else { 1128 no = 0; 1129 SETERROR(REG_ESPACE); 1130 /* caller's responsibility not to do set ops */ 1131 } 1132 } 1133 1134 assert(p->g->sets != NULL); /* xxx */ 1135 cs = &p->g->sets[no]; 1136 cs->ptr = p->g->setbits + css*((no)/CHAR_BIT); 1137 cs->mask = 1 << ((no) % CHAR_BIT); 1138 cs->hash = 0; 1139 cs->smultis = 0; 1140 cs->multis = NULL; 1141 1142 return(cs); 1143} 1144 1145/* 1146 - freeset - free a now-unused set 1147 == static void freeset(register struct parse *p, register cset *cs); 1148 */ 1149static void 1150freeset(p, cs) 1151register struct parse *p; 1152register cset *cs; 1153{ 1154 register int i; 1155 register cset *top = &p->g->sets[p->g->ncsets]; 1156 register size_t css = (size_t)p->g->csetsize; 1157 1158 for (i = 0; i < css; i++) 1159 CHsub(cs, i); 1160 if (cs == top-1) /* recover only the easy case */ 1161 p->g->ncsets--; 1162} 1163 1164/* 1165 - freezeset - final processing on a set of characters 1166 == static int freezeset(register struct parse *p, register cset *cs); 1167 * 1168 * The main task here is merging identical sets. This is usually a waste 1169 * of time (although the hash code minimizes the overhead), but can win 1170 * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash 1171 * is done using addition rather than xor -- all ASCII [aA] sets xor to 1172 * the same value! 1173 */ 1174static int /* set number */ 1175freezeset(p, cs) 1176register struct parse *p; 1177register cset *cs; 1178{ 1179 register uch h = cs->hash; 1180 register int i; 1181 register cset *top = &p->g->sets[p->g->ncsets]; 1182 register cset *cs2; 1183 register size_t css = (size_t)p->g->csetsize; 1184 1185 /* look for an earlier one which is the same */ 1186 for (cs2 = &p->g->sets[0]; cs2 < top; cs2++) 1187 if (cs2->hash == h && cs2 != cs) { 1188 /* maybe */ 1189 for (i = 0; i < css; i++) 1190 if (!!CHIN(cs2, i) != !!CHIN(cs, i)) 1191 break; /* no */ 1192 if (i == css) 1193 break; /* yes */ 1194 } 1195 1196 if (cs2 < top) { /* found one */ 1197 freeset(p, cs); 1198 cs = cs2; 1199 } 1200 1201 return((int)(cs - p->g->sets)); 1202} 1203 1204/* 1205 - firstch - return first character in a set (which must have at least one) 1206 == static int firstch(register struct parse *p, register cset *cs); 1207 */ 1208static int /* character; there is no "none" value */ 1209firstch(p, cs) 1210register struct parse *p; 1211register cset *cs; 1212{ 1213 register int i; 1214 register size_t css = (size_t)p->g->csetsize; 1215 1216 for (i = 0; i < css; i++) 1217 if (CHIN(cs, i)) 1218 return((unsigned char)i); 1219 assert(never); 1220 return(0); /* arbitrary */ 1221} 1222 1223/* 1224 - nch - number of characters in a set 1225 == static int nch(register struct parse *p, register cset *cs); 1226 */ 1227static int 1228nch(p, cs) 1229register struct parse *p; 1230register cset *cs; 1231{ 1232 register int i; 1233 register size_t css = (size_t)p->g->csetsize; 1234 register int n = 0; 1235 1236 for (i = 0; i < css; i++) 1237 if (CHIN(cs, i)) 1238 n++; 1239 return(n); 1240} 1241 1242/* 1243 - mcadd - add a collating element to a cset 1244 == static void mcadd(register struct parse *p, register cset *cs, \ 1245 == register char *cp); 1246 */ 1247static void 1248mcadd(p, cs, cp) 1249register struct parse *p; 1250register cset *cs; 1251register char *cp; 1252{ 1253 register size_t oldend = cs->smultis; 1254 1255 cs->smultis += strlen(cp) + 1; 1256 if (cs->multis == NULL) 1257 cs->multis = malloc(cs->smultis); 1258 else 1259 cs->multis = realloc(cs->multis, cs->smultis); 1260 if (cs->multis == NULL) { 1261 SETERROR(REG_ESPACE); 1262 return; 1263 } 1264 1265 (void) strcpy(cs->multis + oldend - 1, cp); 1266 cs->multis[cs->smultis - 1] = '\0'; 1267} 1268 1269#if used 1270/* 1271 - mcsub - subtract a collating element from a cset 1272 == static void mcsub(register cset *cs, register char *cp); 1273 */ 1274static void 1275mcsub(cs, cp) 1276register cset *cs; 1277register char *cp; 1278{ 1279 register char *fp = mcfind(cs, cp); 1280 register size_t len = strlen(fp); 1281 1282 assert(fp != NULL); 1283 (void) memmove(fp, fp + len + 1, 1284 cs->smultis - (fp + len + 1 - cs->multis)); 1285 cs->smultis -= len; 1286 1287 if (cs->smultis == 0) { 1288 free(cs->multis); 1289 cs->multis = NULL; 1290 return; 1291 } 1292 1293 cs->multis = realloc(cs->multis, cs->smultis); 1294 assert(cs->multis != NULL); 1295} 1296 1297/* 1298 - mcin - is a collating element in a cset? 1299 == static int mcin(register cset *cs, register char *cp); 1300 */ 1301static int 1302mcin(cs, cp) 1303register cset *cs; 1304register char *cp; 1305{ 1306 return(mcfind(cs, cp) != NULL); 1307} 1308 1309/* 1310 - mcfind - find a collating element in a cset 1311 == static char *mcfind(register cset *cs, register char *cp); 1312 */ 1313static char * 1314mcfind(cs, cp) 1315register cset *cs; 1316register char *cp; 1317{ 1318 register char *p; 1319 1320 if (cs->multis == NULL) 1321 return(NULL); 1322 for (p = cs->multis; *p != '\0'; p += strlen(p) + 1) 1323 if (strcmp(cp, p) == 0) 1324 return(p); 1325 return(NULL); 1326} 1327#endif 1328 1329/* 1330 - mcinvert - invert the list of collating elements in a cset 1331 == static void mcinvert(register struct parse *p, register cset *cs); 1332 * 1333 * This would have to know the set of possibilities. Implementation 1334 * is deferred. 1335 */ 1336static void 1337mcinvert(p, cs) 1338register struct parse *p; 1339register cset *cs; 1340{ 1341 assert(cs->multis == NULL); /* xxx */ 1342} 1343 1344/* 1345 - mccase - add case counterparts of the list of collating elements in a cset 1346 == static void mccase(register struct parse *p, register cset *cs); 1347 * 1348 * This would have to know the set of possibilities. Implementation 1349 * is deferred. 1350 */ 1351static void 1352mccase(p, cs) 1353register struct parse *p; 1354register cset *cs; 1355{ 1356 assert(cs->multis == NULL); /* xxx */ 1357} 1358 1359/* 1360 - isinsets - is this character in any sets? 1361 == static int isinsets(register struct re_guts *g, int c); 1362 */ 1363static int /* predicate */ 1364isinsets(g, c) 1365register struct re_guts *g; 1366int c; 1367{ 1368 register uch *col; 1369 register int i; 1370 register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; 1371 register unsigned uc = (unsigned char)c; 1372 1373 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) 1374 if (col[uc] != 0) 1375 return(1); 1376 return(0); 1377} 1378 1379/* 1380 - samesets - are these two characters in exactly the same sets? 1381 == static int samesets(register struct re_guts *g, int c1, int c2); 1382 */ 1383static int /* predicate */ 1384samesets(g, c1, c2) 1385register struct re_guts *g; 1386int c1; 1387int c2; 1388{ 1389 register uch *col; 1390 register int i; 1391 register int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT; 1392 register unsigned uc1 = (unsigned char)c1; 1393 register unsigned uc2 = (unsigned char)c2; 1394 1395 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize) 1396 if (col[uc1] != col[uc2]) 1397 return(0); 1398 return(1); 1399} 1400 1401/* 1402 - categorize - sort out character categories 1403 == static void categorize(struct parse *p, register struct re_guts *g); 1404 */ 1405static void 1406categorize(p, g) 1407struct parse *p; 1408register struct re_guts *g; 1409{ 1410 register cat_t *cats = g->categories; 1411 register int c; 1412 register int c2; 1413 register cat_t cat; 1414 1415 /* avoid making error situations worse */ 1416 if (p->error != 0) 1417 return; 1418 1419 for (c = CHAR_MIN; c <= CHAR_MAX; c++) 1420 if (cats[c] == 0 && isinsets(g, c)) { 1421 cat = g->ncategories++; 1422 cats[c] = cat; 1423 for (c2 = c+1; c2 <= CHAR_MAX; c2++) 1424 if (cats[c2] == 0 && samesets(g, c, c2)) 1425 cats[c2] = cat; 1426 } 1427} 1428 1429/* 1430 - dupl - emit a duplicate of a bunch of sops 1431 == static sopno dupl(register struct parse *p, sopno start, sopno finish); 1432 */ 1433static sopno /* start of duplicate */ 1434dupl(p, start, finish) 1435register struct parse *p; 1436sopno start; /* from here */ 1437sopno finish; /* to this less one */ 1438{ 1439 register sopno ret = HERE(); 1440 register sopno len = finish - start; 1441 1442 assert(finish >= start); 1443 if (len == 0) 1444 return(ret); 1445 enlarge(p, p->ssize + len); /* this many unexpected additions */ 1446 assert(p->ssize >= p->slen + len); 1447 (void) memcpy((char *)(p->strip + p->slen), 1448 (char *)(p->strip + start), (size_t)len*sizeof(sop)); 1449 p->slen += len; 1450 return(ret); 1451} 1452 1453/* 1454 - doemit - emit a strip operator 1455 == static void doemit(register struct parse *p, sop op, size_t opnd); 1456 * 1457 * It might seem better to implement this as a macro with a function as 1458 * hard-case backup, but it's just too big and messy unless there are 1459 * some changes to the data structures. Maybe later. 1460 */ 1461static void 1462doemit(p, op, opnd) 1463register struct parse *p; 1464sop op; 1465size_t opnd; 1466{ 1467 /* avoid making error situations worse */ 1468 if (p->error != 0) 1469 return; 1470 1471 /* deal with oversize operands ("can't happen", more or less) */ 1472 assert(opnd < 1<<OPSHIFT); 1473 1474 /* deal with undersized strip */ 1475 if (p->slen >= p->ssize) 1476 enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */ 1477 assert(p->slen < p->ssize); 1478 1479 /* finally, it's all reduced to the easy case */ 1480 p->strip[p->slen++] = SOP(op, opnd); 1481} 1482 1483/* 1484 - doinsert - insert a sop into the strip 1485 == static void doinsert(register struct parse *p, sop op, size_t opnd, sopno pos); 1486 */ 1487static void 1488doinsert(p, op, opnd, pos) 1489register struct parse *p; 1490sop op; 1491size_t opnd; 1492sopno pos; 1493{ 1494 register sopno sn; 1495 register sop s; 1496 register int i; 1497 1498 /* avoid making error situations worse */ 1499 if (p->error != 0) 1500 return; 1501 1502 sn = HERE(); 1503 EMIT(op, opnd); /* do checks, ensure space */ 1504 assert(HERE() == sn+1); 1505 s = p->strip[sn]; 1506 1507 /* adjust paren pointers */ 1508 assert(pos > 0); 1509 for (i = 1; i < NPAREN; i++) { 1510 if (p->pbegin[i] >= pos) { 1511 p->pbegin[i]++; 1512 } 1513 if (p->pend[i] >= pos) { 1514 p->pend[i]++; 1515 } 1516 } 1517 1518 memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos], 1519 (HERE()-pos-1)*sizeof(sop)); 1520 p->strip[pos] = s; 1521} 1522 1523/* 1524 - dofwd - complete a forward reference 1525 == static void dofwd(register struct parse *p, sopno pos, sop value); 1526 */ 1527static void 1528dofwd(p, pos, value) 1529register struct parse *p; 1530register sopno pos; 1531sop value; 1532{ 1533 /* avoid making error situations worse */ 1534 if (p->error != 0) 1535 return; 1536 1537 assert(value < 1<<OPSHIFT); 1538 p->strip[pos] = OP(p->strip[pos]) | value; 1539} 1540 1541/* 1542 - enlarge - enlarge the strip 1543 == static void enlarge(register struct parse *p, sopno size); 1544 */ 1545static void 1546enlarge(p, size) 1547register struct parse *p; 1548register sopno size; 1549{ 1550 register sop *sp; 1551 1552 if (p->ssize >= size) 1553 return; 1554 1555 sp = (sop *)realloc(p->strip, size*sizeof(sop)); 1556 if (sp == NULL) { 1557 SETERROR(REG_ESPACE); 1558 return; 1559 } 1560 p->strip = sp; 1561 p->ssize = size; 1562} 1563 1564/* 1565 - stripsnug - compact the strip 1566 == static void stripsnug(register struct parse *p, register struct re_guts *g); 1567 */ 1568static void 1569stripsnug(p, g) 1570register struct parse *p; 1571register struct re_guts *g; 1572{ 1573 g->nstates = p->slen; 1574 g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop)); 1575 if (g->strip == NULL) { 1576 SETERROR(REG_ESPACE); 1577 g->strip = p->strip; 1578 } 1579} 1580 1581/* 1582 - findmust - fill in must and mlen with longest mandatory literal string 1583 == static void findmust(register struct parse *p, register struct re_guts *g); 1584 * 1585 * This algorithm could do fancy things like analyzing the operands of | 1586 * for common subsequences. Someday. This code is simple and finds most 1587 * of the interesting cases. 1588 * 1589 * Note that must and mlen got initialized during setup. 1590 */ 1591static void 1592findmust(p, g) 1593struct parse *p; 1594register struct re_guts *g; 1595{ 1596 register sop *scan; 1597 sop *start; 1598 register sop *newstart; 1599 register sopno newlen; 1600 register sop s; 1601 register char *cp; 1602 register sopno i; 1603 1604 /* avoid making error situations worse */ 1605 if (p->error != 0) 1606 return; 1607 1608 /* find the longest OCHAR sequence in strip */ 1609 newlen = 0; 1610 scan = g->strip + 1; 1611 do { 1612 s = *scan++; 1613 switch (OP(s)) { 1614 case OCHAR: /* sequence member */ 1615 if (newlen == 0) /* new sequence */ 1616 newstart = scan - 1; 1617 newlen++; 1618 break; 1619 case OPLUS_: /* things that don't break one */ 1620 case OLPAREN: 1621 case ORPAREN: 1622 break; 1623 case OQUEST_: /* things that must be skipped */ 1624 case OCH_: 1625 scan--; 1626 do { 1627 scan += OPND(s); 1628 s = *scan; 1629 /* assert() interferes w debug printouts */ 1630 if (OP(s) != O_QUEST && OP(s) != O_CH && 1631 OP(s) != OOR2) { 1632 g->iflags |= BAD; 1633 return; 1634 } 1635 } while (OP(s) != O_QUEST && OP(s) != O_CH); 1636 /* fallthrough */ 1637 default: /* things that break a sequence */ 1638 if (newlen > g->mlen) { /* ends one */ 1639 start = newstart; 1640 g->mlen = newlen; 1641 } 1642 newlen = 0; 1643 break; 1644 } 1645 } while (OP(s) != OEND); 1646 1647 if (g->mlen == 0) /* there isn't one */ 1648 return; 1649 1650 /* turn it into a character string */ 1651 g->must = malloc((size_t)g->mlen + 1); 1652 if (g->must == NULL) { /* argh; just forget it */ 1653 g->mlen = 0; 1654 return; 1655 } 1656 cp = g->must; 1657 scan = start; 1658 for (i = g->mlen; i > 0; i--) { 1659 while (OP(s = *scan++) != OCHAR) 1660 continue; 1661 assert(cp < g->must + g->mlen); 1662 *cp++ = (char)OPND(s); 1663 } 1664 assert(cp == g->must + g->mlen); 1665 *cp++ = '\0'; /* just on general principles */ 1666} 1667 1668/* 1669 - pluscount - count + nesting 1670 == static sopno pluscount(register struct parse *p, register struct re_guts *g); 1671 */ 1672static sopno /* nesting depth */ 1673pluscount(p, g) 1674struct parse *p; 1675register struct re_guts *g; 1676{ 1677 register sop *scan; 1678 register sop s; 1679 register sopno plusnest = 0; 1680 register sopno maxnest = 0; 1681 1682 if (p->error != 0) 1683 return(0); /* there may not be an OEND */ 1684 1685 scan = g->strip + 1; 1686 do { 1687 s = *scan++; 1688 switch (OP(s)) { 1689 case OPLUS_: 1690 plusnest++; 1691 break; 1692 case O_PLUS: 1693 if (plusnest > maxnest) 1694 maxnest = plusnest; 1695 plusnest--; 1696 break; 1697 } 1698 } while (OP(s) != OEND); 1699 if (plusnest != 0) 1700 g->iflags |= BAD; 1701 return(maxnest); 1702} 1703