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