10 * parse structure, passed up and down to avoid global variables and
14 char *next; /* next character in RE */
15 char *end; /* end of string (-> NUL normally) */
16 int error; /* has an error been seen? */
17 sop *strip; /* malloced strip */
18 size_t ssize; /* malloced strip size (allocated) */
19 size_t slen; /* malloced strip length (used) */
20 int ncsalloc; /* number of csets allocated */
22 # define NPAREN 10 /* we need to remember () 1-9 for back refs */
23 sopno pbegin[NPAREN]; /* -> ( ([0] unused) */
24 sopno pend[NPAREN]; /* -> ) ([0] unused) */
29 static char nuls[10]; /* place to point scanner in event of error */
32 * macros for use with parse structure
33 * BEWARE: these know that the parse structure is named `p' !!!
35 #define PEEK() (*p->next)
36 #define PEEK2() (*(p->next+1))
37 #define MORE() (p->next < p->end)
38 #define MORE2() (p->next+1 < p->end)
39 #define SEE(c) (MORE() && PEEK() == (c))
40 #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
41 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
42 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
43 #define NEXT() (p->next++)
44 #define NEXT2() (p->next += 2)
45 #define NEXTn(n) (p->next += (n))
46 #define GETNEXT() (*p->next++)
47 #define SETERROR(e) seterr(p, (e))
48 #define REQUIRE(co, e) ((co) || SETERROR(e))
49 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
50 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
51 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
52 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
53 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(size_t)(pos)+1, (size_t)pos)
54 #define AHEAD(pos) dofwd(p, (size_t)pos, HERE()-(size_t)(pos))
55 #define ASTERN(sop, pos) EMIT(sop, HERE()-(size_t)(pos))
56 #define HERE() (size_t)(p->slen)
57 #define THERE() (size_t)(p->slen - 1)
58 #define THERETHERE() (size_t)(p->slen - 2)
59 #define DROP(n) (p->slen = p->slen - (size_t)(n))
62 static int never = 0; /* for use in asserts; shuts lint up */
64 #define never 0 /* some <assert.h>s have bugs too */
67 static void p_ere(struct parse *p, int stop);
68 static void p_ere_exp(struct parse *p);
69 static void p_str(struct parse *p);
70 static void p_bre(struct parse *p, int end1, int end2);
71 static int p_simp_re(struct parse *p, int starordinary);
72 static int p_count(struct parse *p);
73 static void p_bracket(struct parse *p);
74 static void p_b_term(struct parse *p, cset *cs);
75 static void p_b_cclass(struct parse *p, cset *cs);
76 static void p_b_eclass(struct parse *p, cset *cs);
77 static char p_b_symbol(struct parse *p);
78 static char p_b_coll_elem(struct parse *p, int endc);
79 static char othercase(int ch);
80 static void bothcases(struct parse *p, int ch);
81 static void ordinary(struct parse *p, int ch);
82 static void nonnewline(struct parse *p);
83 static void repeat(struct parse *p, sopno start, int from, int to);
84 static int seterr(struct parse *p, int e);
85 static cset * allocset(struct parse *p);
86 static void freeset(struct parse *p, cset *cs);
87 static int freezeset(struct parse *p, cset *cs);
88 static int firstch(struct parse *p, cset *cs);
89 static int nch(struct parse *p, cset *cs);
90 static void mcadd(struct parse *p, cset *cs, char *cp);
91 static void mcinvert(struct parse *p, cset *cs);
92 static void mccase(struct parse *p, cset *cs);
93 static int isinsets(struct re_guts *g, int c);
94 static int samesets(struct re_guts *g, int c1, int c2);
95 static void categorize(struct parse *p, struct re_guts *g);
96 static sopno dupl(struct parse *p, sopno start, sopno finish);
97 static void doemit(struct parse *p, sop op, size_t opnd);
98 static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
99 static void dofwd(struct parse *p, sopno pos, sop value);
100 static void enlarge(struct parse *p, sopno size);
101 static void stripsnug(struct parse *p, struct re_guts *g);
102 static void findmust(struct parse *p, struct re_guts *g);
103 static sopno pluscount(struct parse *p, struct re_guts *g);
107 - regcomp - interface for parser and compilation
108 = extern int regcomp(regex_t *, const char *, int);
109 = #define REG_BASIC 0000
110 = #define REG_EXTENDED 0001
111 = #define REG_ICASE 0002
112 = #define REG_NOSUB 0004
113 = #define REG_NEWLINE 0010
114 = #define REG_NOSPEC 0020
115 = #define REG_PEND 0040
116 = #define REG_DUMP 0200
118 int /* 0 success, otherwise REG_something */
126 struct parse *p = &pa;
130 # define GOODFLAGS(f) (f)
132 # define GOODFLAGS(f) ((f)&~REG_DUMP)
135 cflags = GOODFLAGS(cflags);
136 #if !defined(__lint) /* Lint global check knows nobody calls with this combo */
137 if ((cflags®_EXTENDED) && (cflags®_NOSPEC))
140 if (cflags & REG_PEND) {
142 if (preg->re_endp < pattern)
144 len = (size_t)(preg->re_endp - pattern);
148 len = strlen((char *)pattern);
150 /* do the mallocs early so failure handling is easy */
151 g = (struct re_guts *)malloc(SIZEOF(struct re_guts) +
152 (NC-1)*SIZEOF(cat_t));
155 p->ssize = (sopno)(((len / (size_t)2) * (size_t)3) + (size_t)1);
156 p->strip = (sop *)malloc((size_t)p->ssize * SIZEOF(sop));
158 if (p->strip == NULL) {
165 p->next = (char *)pattern; /* convenience; we do not modify it */
166 p->end = p->next + len;
169 for (i = 0; i < NPAREN; i++) {
184 g->ncategories = 1; /* category 0 is "everything else" */
185 g->categories = &g->catspace[-(CHAR_MIN)];
186 (void) memset((char *)g->catspace, 0, NC*SIZEOF(cat_t));
191 g->firststate = (sopno)THERE();
192 if (cflags & REG_EXTENDED)
194 else if (cflags & REG_NOSPEC)
199 g->laststate = THERE();
201 /* tidy up loose ends and fill things in */
205 g->nplus = pluscount(p, g);
208 preg->re_nsub = g->nsub;
210 preg->re_magic = MAGIC1;
213 /* not debugging, so can't rely on the assert() in regexec() */
215 SETERROR(REG_ASSERT);
218 /* win or lose, we're done */
219 if (p->error != 0) /* lose */
225 - p_ere - ERE parser top level, concatenation and alternation
226 == static void p_ere(struct parse *p, int stop);
231 int stop) /* character this ERE should end at */
237 int first = 1; /* is this the first alternative? */
240 /* do a bunch of concatenated expressions */
242 while (MORE() && (c = PEEK()) != '|' && c != stop)
244 (void)REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */
247 break; /* NOTE BREAK OUT */
250 INSERT(OCH_, conc); /* offset is wrong */
255 ASTERN(OOR1, prevback);
257 AHEAD(prevfwd); /* fix previous offset */
259 EMIT(OOR2, 0); /* offset is very wrong */
262 if (!first) { /* tail-end fixups */
264 ASTERN(O_CH, prevback);
267 assert(!MORE() || SEE(stop));
271 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
272 == static void p_ere_exp(struct parse *p);
285 assert(MORE()); /* caller should have ensured this */
291 (void)REQUIRE(MORE(), REG_EPAREN);
295 p->pbegin[subno] = HERE();
296 EMIT(OLPAREN, subno);
299 if (subno < NPAREN) {
300 p->pend[subno] = HERE();
301 assert(p->pend[subno] != 0);
303 EMIT(ORPAREN, subno);
304 (void)MUSTEAT(')', REG_EPAREN);
306 #ifndef POSIX_MISTAKE
307 case ')': /* happens only if no current unmatched ( */
309 * You may ask, why the ifndef? Because I didn't notice
310 * this until slightly too late for 1003.2, and none of the
311 * other 1003.2 regular-expression reviewers noticed it at
312 * all. So an unmatched ) is legal POSIX, at least until
313 * we can get it fixed.
315 SETERROR(REG_EPAREN);
320 p->g->iflags |= USEBOL;
326 p->g->iflags |= USEEOL;
335 SETERROR(REG_BADRPT);
338 if (p->g->cflags®_NEWLINE)
347 (void)REQUIRE(MORE(), REG_EESCAPE);
351 case '{': /* okay as ordinary except if digit follows */
352 (void)REQUIRE(!MORE() || !isdigit(PEEK()), REG_BADRPT);
362 /* we call { a repetition if followed by a digit */
363 if (!( c == '*' || c == '+' || c == '?' ||
364 (c == '{' && MORE2() && isdigit(PEEK2())) ))
365 return; /* no repetition, we're done */
368 (void)REQUIRE(!wascaret, REG_BADRPT);
370 case '*': /* implemented as +? */
371 /* this case does not require the (y|) trick, noKLUDGE */
374 INSERT(OQUEST_, pos);
375 ASTERN(O_QUEST, pos);
382 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
383 INSERT(OCH_, pos); /* offset slightly wrong */
384 ASTERN(OOR1, pos); /* this one's right */
385 AHEAD(pos); /* fix the OCH_ */
386 EMIT(OOR2, 0); /* offset very wrong... */
387 AHEAD(THERE()); /* ...so fix it */
388 ASTERN(O_CH, THERETHERE());
393 if (isdigit(PEEK())) {
395 (void)REQUIRE(count <= count2, REG_BADBR);
396 } else /* single number with comma */
397 count2 = (int)REINFINITY;
398 } else /* just a single number */
400 repeat(p, pos, count, count2);
401 if (!EAT('}')) { /* error heuristics */
402 while (MORE() && PEEK() != '}')
404 (void)REQUIRE(MORE(), REG_EBRACE);
413 if (!( c == '*' || c == '+' || c == '?' ||
414 (c == '{' && MORE2() && isdigit(PEEK2())) ) )
416 SETERROR(REG_BADRPT);
420 - p_str - string (no metacharacters) "parser"
421 == static void p_str(struct parse *p);
427 (void)REQUIRE(MORE(), REG_EMPTY);
429 ordinary(p, GETNEXT());
433 - p_bre - BRE parser top level, anchoring and concatenation
434 == static void p_bre(struct parse *p, register int end1, \
436 * Giving end1 as OUT essentially eliminates the end1/end2 check.
438 * This implementation is a bit of a kludge, in that a trailing $ is first
439 * taken as an ordinary character and then revised to be an anchor. The
440 * only undesirable side effect is that '$' gets included as a character
441 * category in such cases. This is fairly harmless; not worth fixing.
442 * The amount of lookahead needed to avoid this kludge is excessive.
447 int end1, /* first terminating character */
448 int end2) /* second terminating character */
450 sopno start = HERE();
451 int first = 1; /* first subexpression? */
456 p->g->iflags |= USEBOL;
459 while (MORE() && !SEETWO(end1, end2)) {
460 wasdollar = p_simp_re(p, first);
463 if (wasdollar) { /* oops, that was a trailing anchor */
466 p->g->iflags |= USEEOL;
470 (void)REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */
474 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
475 == static int p_simp_re(struct parse *p, int starordinary);
477 static int /* was the simple RE an unbackslashed $? */
480 int starordinary)/* is a leading * an ordinary character? */
488 # define BACKSL (1<<CHAR_BIT)
490 pos = HERE(); /* repetion op, if any, covers from here */
492 assert(MORE()); /* caller should have ensured this */
495 (void)REQUIRE(MORE(), REG_EESCAPE);
496 c = BACKSL | (unsigned char)GETNEXT();
500 if (p->g->cflags®_NEWLINE)
509 SETERROR(REG_BADRPT);
515 p->pbegin[subno] = HERE();
516 EMIT(OLPAREN, subno);
517 /* the MORE here is an error heuristic */
518 if (MORE() && !SEETWO('\\', ')'))
520 if (subno < NPAREN) {
521 p->pend[subno] = HERE();
522 assert(p->pend[subno] != 0);
524 EMIT(ORPAREN, subno);
525 (void)REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
527 case BACKSL|')': /* should not get here -- must be user */
529 SETERROR(REG_EPAREN);
540 i = (c&~BACKSL) - '0';
542 if (p->pend[i] != 0) {
543 assert(i <= (int)p->g->nsub);
545 assert(p->pbegin[i] != 0);
546 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
547 assert(OP(p->strip[p->pend[i]]) == ORPAREN);
548 (void)dupl(p, p->pbegin[i]+1, p->pend[i]);
551 SETERROR(REG_ESUBREG);
555 (void)REQUIRE(starordinary, REG_BADRPT);
558 ordinary(p, c &~ BACKSL);
562 if (EAT('*')) { /* implemented as +? */
563 /* this case does not require the (y|) trick, noKLUDGE */
566 INSERT(OQUEST_, pos);
567 ASTERN(O_QUEST, pos);
568 } else if (EATTWO('\\', '{')) {
571 if (MORE() && isdigit(PEEK())) {
573 (void)REQUIRE(count <= count2, REG_BADBR);
574 } else /* single number with comma */
576 } else /* just a single number */
578 repeat(p, pos, count, count2);
579 if (!EATTWO('\\', '}')) { /* error heuristics */
580 while (MORE() && !SEETWO('\\', '}'))
582 (void)REQUIRE(MORE(), REG_EBRACE);
585 } else if (c == (unsigned char)'$') /* $ (but not \$) ends it */
592 - p_count - parse a repetition count
593 == static int p_count(struct parse *p);
595 static int /* the value */
602 while (MORE() && isdigit(PEEK()) && count <= DUPMAX) {
603 count = count*10 + (GETNEXT() - '0');
607 (void)REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
612 - p_bracket - parse a bracketed character list
613 == static void p_bracket(struct parse *p);
615 * Note a significant property of this code: if the allocset() did SETERROR,
616 * no set operations are done.
622 cset *cs = allocset(p);
625 /* Dept of Truly Sickening Special-Case Kludges */
626 if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
631 if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
638 invert++; /* make note to invert set at end */
643 while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
647 (void)MUSTEAT(']', REG_EBRACK);
649 if (p->error != 0) /* don't mess things up further */
652 if (p->g->cflags®_ICASE) {
656 for (i = p->g->csetsize - 1; i >= 0; i--)
657 if (CHIN(cs, i) && isalpha(i)) {
662 if (cs->multis != NULL)
668 for (i = p->g->csetsize - 1; i >= 0; i--)
673 if (p->g->cflags®_NEWLINE)
675 if (cs->multis != NULL)
679 assert(cs->multis == NULL); /* xxx */
681 if (nch(p, cs) == 1) { /* optimize singleton sets */
682 ordinary(p, firstch(p, cs));
685 EMIT(OANYOF, freezeset(p, cs));
689 - p_b_term - parse one term of a bracketed character list
690 == static void p_b_term(struct parse *p, register cset *cs);
701 /* classify what we've got */
702 switch ((MORE()) ? PEEK() : '\0') {
704 c = (char)((MORE2()) ? PEEK2() : '\0');
707 SETERROR(REG_ERANGE);
708 return; /* NOTE RETURN */
716 case ':': /* character class */
718 (void)REQUIRE(MORE(), REG_EBRACK);
720 (void)REQUIRE(c != '-' && c != ']', REG_ECTYPE);
722 (void)REQUIRE(MORE(), REG_EBRACK);
723 (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
725 case '=': /* equivalence class */
727 (void)REQUIRE(MORE(), REG_EBRACK);
729 (void)REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
731 (void)REQUIRE(MORE(), REG_EBRACK);
732 (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
734 default: /* symbol, ordinary character, or range */
735 /* xxx revision needed for multichar stuff */
736 start = (char)p_b_symbol(p);
737 if (SEE('-') && MORE2() && PEEK2() != ']') {
743 finish = (char)p_b_symbol(p);
746 /* xxx what about signed chars here... */
747 (void)REQUIRE(start <= finish, REG_ERANGE);
748 for (i = start; i <= finish; i++)
755 - p_b_cclass - parse a character-class name and deal with it
756 == static void p_b_cclass(struct parse *p, register cset *cs);
769 while (MORE() && isalpha(PEEK()))
771 len = (size_t)(p->next - sp);
772 for (cp = cclasses; cp->name != NULL; cp++)
773 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
775 if (cp->name == NULL) {
776 /* oops, didn't find it */
777 SETERROR(REG_ECTYPE);
782 while ((c = *u++) != '\0')
784 for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
789 - p_b_eclass - parse an equivalence-class name and deal with it
790 == static void p_b_eclass(struct parse *p, register cset *cs);
792 * This implementation is incomplete. xxx
801 c = (char)p_b_coll_elem(p, '=');
806 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
807 == static char p_b_symbol(struct parse *p);
809 static char /* value of symbol */
815 (void)REQUIRE(MORE(), REG_EBRACK);
816 if (!EATTWO('[', '.'))
819 /* collating symbol */
820 value = (char)p_b_coll_elem(p, '.');
821 (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
826 - p_b_coll_elem - parse a collating-element name and look it up
827 == static char p_b_coll_elem(struct parse *p, int endc);
829 static char /* value of collating element */
832 int endc) /* name ended by endc,']' */
838 while (MORE() && !SEETWO(endc, ']'))
841 SETERROR(REG_EBRACK);
844 len = (size_t)(p->next - sp);
845 for (cp = cnames; cp->name != NULL; cp++)
846 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
847 return(cp->code); /* known name */
849 return(*sp); /* single character */
850 SETERROR(REG_ECOLLATE); /* neither */
855 - othercase - return the case counterpart of an alphabetic
856 == static char othercase(int ch);
858 static char /* if no counterpart, return ch */
865 else if (islower(ch))
867 else /* peculiar, but could happen */
872 - bothcases - emit a dualcase version of a two-case character
873 == static void bothcases(struct parse *p, int ch);
875 * Boy, is this implementation ever a kludge...
882 char *oldnext = p->next;
883 char *oldend = p->end;
884 static char bracket[3];
886 assert(othercase(ch) != ch); /* p_bracket() would recurse */
889 bracket[0] = (char)ch;
893 assert(p->next == bracket+2);
899 - ordinary - emit an ordinary character
900 == static void ordinary(struct parse *p, register int ch);
907 cat_t *cap = p->g->categories;
909 if ((p->g->cflags®_ICASE) && isalpha(ch) && othercase(ch) != ch)
912 EMIT(OCHAR, (unsigned char)ch);
914 cap[ch] = (cat_t)(p->g->ncategories++);
919 - nonnewline - emit REG_NEWLINE version of OANY
920 == static void nonnewline(struct parse *p);
922 * Boy, is this implementation ever a kludge...
928 char *oldnext = p->next;
929 char *oldend = p->end;
930 static char bracket[4];
939 assert(p->next == bracket+3);
945 - repeat - generate code for a bounded repetition, recursively if needed
946 == static void repeat(struct parse *p, sopno start, int from, int to);
951 sopno start, /* operand from here to end of strip */
952 int from, /* repeated from this number */
953 int to) /* to this number of times (maybe REINFINITY) */
955 sopno finish = HERE();
958 # define REP(f, t) ((f)*8 + (t))
959 # define MAP(n) (((n) <= 1) ? (n) : ((n) == REINFINITY) ? INF : N)
962 if (p->error != 0) /* head off possible runaway recursion */
967 switch (REP(MAP(from), MAP(to))) {
968 case REP(0, 0): /* must be user doing this */
969 DROP(finish-start); /* drop the operand */
971 case REP(0, 1): /* as x{1,1}? */
972 case REP(0, N): /* as x{1,n}? */
973 case REP(0, INF): /* as x{1,}? */
974 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
975 INSERT(OCH_, start); /* offset is wrong... */
976 repeat(p, start+1, 1, to);
978 AHEAD(start); /* ... fix it */
981 ASTERN(O_CH, THERETHERE());
983 case REP(1, 1): /* trivial case */
986 case REP(1, N): /* as x?x{1,n-1} */
987 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
991 EMIT(OOR2, 0); /* offset very wrong... */
992 AHEAD(THERE()); /* ...so fix it */
993 ASTERN(O_CH, THERETHERE());
994 copy = dupl(p, start+1, finish+1);
995 assert(copy == finish+4);
996 repeat(p, copy, 1, to-1);
998 case REP(1, INF): /* as x+ */
999 INSERT(OPLUS_, start);
1000 ASTERN(O_PLUS, start);
1002 case REP(N, N): /* as xx{m-1,n-1} */
1003 copy = dupl(p, start, finish);
1004 repeat(p, copy, from-1, to-1);
1006 case REP(N, INF): /* as xx{n-1,INF} */
1007 copy = dupl(p, start, finish);
1008 repeat(p, copy, from-1, to);
1010 default: /* "can't happen" */
1011 SETERROR(REG_ASSERT); /* just in case */
1017 - seterr - set an error condition
1018 == static int seterr(struct parse *p, int e);
1020 static int /* useless but makes type checking happy */
1025 if (p->error == 0) /* keep earliest error condition */
1027 p->next = nuls; /* try to bring things to a halt */
1029 return(0); /* make the return value well-defined */
1033 - allocset - allocate a set of characters for []
1034 == static cset *allocset(struct parse *p);
1040 int no = p->g->ncsets++;
1044 size_t css = (size_t)p->g->csetsize;
1047 if (no >= p->ncsalloc) { /* need another column of space */
1048 p->ncsalloc += CHAR_BIT;
1050 assert(nc % CHAR_BIT == 0);
1051 nbytes = nc / CHAR_BIT * css;
1052 if (p->g->sets == NULL)
1053 p->g->sets = (cset *)malloc(nc * SIZEOF(cset));
1055 p->g->sets = (cset *)realloc((char *)p->g->sets,
1056 (size_t)nc * SIZEOF(cset));
1057 if (p->g->setbits == NULL)
1058 p->g->setbits = (uch *)malloc(nbytes);
1060 p->g->setbits = (uch *)realloc((char *)p->g->setbits,
1062 /* xxx this isn't right if setbits is now NULL */
1063 if (p->g->sets && p->g->setbits)
1064 for (i = 0; i < no; i++)
1065 p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
1067 if (p->g->sets != NULL && p->g->setbits != NULL)
1068 (void) memset((char *)p->g->setbits + (nbytes - css),
1072 SETERROR(REG_ESPACE);
1073 /* caller's responsibility not to do set ops */
1077 assert(p->g->sets != NULL); /* xxx */
1078 cs = &p->g->sets[no];
1079 cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
1080 cs->mask = (uch)(1 << ((no) % CHAR_BIT));
1089 - freeset - free a now-unused set
1090 == static void freeset(struct parse *p, register cset *cs);
1098 cset *top = &p->g->sets[p->g->ncsets];
1099 int css = p->g->csetsize;
1101 for (i = 0; i < css; i++)
1103 if (cs == top-1) /* recover only the easy case */
1108 - freezeset - final processing on a set of characters
1109 == static int freezeset(struct parse *p, register cset *cs);
1111 * The main task here is merging identical sets. This is usually a waste
1112 * of time (although the hash code minimizes the overhead), but can win
1113 * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash
1114 * is done using addition rather than xor -- all ASCII [aA] sets xor to
1117 static int /* set number */
1124 cset *top = &p->g->sets[p->g->ncsets];
1126 int css = p->g->csetsize;
1128 /* look for an earlier one which is the same */
1129 for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
1130 if (cs2->hash == h && cs2 != cs) {
1132 for (i = 0; i < css; i++)
1133 if (!!CHIN(cs2, i) != !!CHIN(cs, i))
1139 if (cs2 < top) { /* found one */
1144 return((int)(cs - p->g->sets));
1148 - firstch - return first character in a set (which must have at least one)
1149 == static int firstch(struct parse *p, register cset *cs);
1151 static int /* character; there is no "none" value */
1157 int css = p->g->csetsize;
1159 for (i = 0; i < css; i++)
1163 return(0); /* arbitrary */
1167 - nch - number of characters in a set
1168 == static int nch(struct parse *p, register cset *cs);
1176 int css = p->g->csetsize;
1179 for (i = 0; i < css; i++)
1186 - mcadd - add a collating element to a cset
1187 == static void mcadd(struct parse *p, register cset *cs, \
1196 size_t oldend = cs->smultis;
1198 cs->smultis += strlen(cp) + 1;
1199 if (cs->multis == NULL)
1200 cs->multis = malloc(cs->smultis);
1202 cs->multis = realloc(cs->multis, (size_t)cs->smultis);
1203 if (cs->multis == NULL) {
1204 SETERROR(REG_ESPACE);
1208 (void) strncpy(cs->multis + oldend - 1, cp, cs->smultis - (oldend - 1));
1209 cs->multis[cs->smultis - 1] = '\0';
1214 - mcinvert - invert the list of collating elements in a cset
1215 == static void mcinvert(struct parse *p, register cset *cs);
1217 * This would have to know the set of possibilities. Implementation
1225 (void)p; /* Quiet unused parameter warning */
1226 (void)cs; /* Quiet unused parameter warning */
1227 assert(cs->multis == NULL); /* xxx */
1231 - mccase - add case counterparts of the list of collating elements in a cset
1232 == static void mccase(struct parse *p, register cset *cs);
1234 * This would have to know the set of possibilities. Implementation
1242 (void)p; /* Quiet unused parameter warning */
1243 (void)cs; /* Quiet unused parameter warning */
1244 assert(cs->multis == NULL); /* xxx */
1248 - isinsets - is this character in any sets?
1249 == static int isinsets(struct re_guts *g, int c);
1251 static int /* predicate */
1258 int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1259 unsigned uc = (unsigned char)c;
1261 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1268 - samesets - are these two characters in exactly the same sets?
1269 == static int samesets(struct re_guts *g, int c1, int c2);
1271 static int /* predicate */
1279 int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1280 unsigned uc1 = (unsigned char)c1;
1281 unsigned uc2 = (unsigned char)c2;
1283 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1284 if (col[uc1] != col[uc2])
1290 - categorize - sort out character categories
1291 == static void categorize(struct parse *p, struct re_guts *g);
1298 cat_t *cats = g->categories;
1303 /* avoid making error situations worse */
1307 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
1308 if (cats[c] == 0 && isinsets(g, c)) {
1309 cat = (cat_t)g->ncategories++;
1311 for (c2 = c+1; c2 <= CHAR_MAX; c2++)
1312 if (cats[c2] == 0 && samesets(g, c, c2))
1318 - dupl - emit a duplicate of a bunch of sops
1319 == static sopno dupl(struct parse *p, sopno start, sopno finish);
1321 static sopno /* start of duplicate */
1324 sopno start, /* from here */
1325 sopno finish) /* to this less one */
1328 size_t len = (size_t)(finish - start);
1330 assert(finish >= start);
1333 enlarge(p, p->ssize + len); /* this many unexpected additions */
1334 assert(p->ssize >= (p->slen + len));
1335 (void) memcpy((char *)(p->strip + p->slen),
1336 (char *)(p->strip + start), ((size_t)len * SIZEOF(sop)));
1342 - doemit - emit a strip operator
1343 == static void doemit(struct parse *p, sop op, size_t opnd);
1345 * It might seem better to implement this as a macro with a function as
1346 * hard-case backup, but it's just too big and messy unless there are
1347 * some changes to the data structures. Maybe later.
1355 /* avoid making error situations worse */
1359 /* deal with oversize operands ("can't happen", more or less) */
1360 assert(opnd < (1 << OPSHIFT));
1362 /* deal with undersized strip */
1363 if (p->slen >= p->ssize)
1364 enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */
1365 assert(p->slen < p->ssize);
1367 /* finally, it's all reduced to the easy case */
1368 p->strip[p->slen++] = SOP(op, opnd);
1372 - doinsert - insert a sop into the strip
1373 == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
1386 /* avoid making error situations worse */
1391 EMIT(op, opnd); /* do checks, ensure space */
1392 assert(HERE() == sn+1);
1395 /* adjust paren pointers */
1397 for (i = 1; i < NPAREN; i++) {
1398 if (p->pbegin[i] >= pos) {
1401 if (p->pend[i] >= pos) {
1406 memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
1407 (HERE() - (size_t)pos - 1) * SIZEOF(sop));
1412 - dofwd - complete a forward reference
1413 == static void dofwd(struct parse *p, sopno pos, sop value);
1421 /* avoid making error situations worse */
1425 assert(value < 1<<OPSHIFT);
1426 p->strip[pos] = OP(p->strip[pos]) | value;
1429 - enlarge - enlarge the strip
1430 == static void enlarge(struct parse *p, sopno size);
1439 assert(size <= (sopno)SSIZE_MAX);
1440 if (p->ssize >= (size_t)size)
1443 sp = (sop *)realloc(p->strip, (size_t)size * SIZEOF(sop));
1445 SETERROR(REG_ESPACE);
1449 p->ssize = (size_t)size;
1453 - stripsnug - compact the strip
1454 == static void stripsnug(struct parse *p, register struct re_guts *g);
1458 /*@keep@*/ struct parse * p,
1459 /*@keep@*/ struct re_guts *g)
1461 g->nstates = p->slen;
1462 g->strip = (sop *)realloc((char *)p->strip,
1463 (size_t)p->slen * SIZEOF(sop));
1464 if (g->strip == NULL) {
1465 SETERROR(REG_ESPACE);
1466 g->strip = p->strip;
1471 - findmust - fill in must and mlen with longest mandatory literal string
1472 == static void findmust(struct parse *p, register struct re_guts *g);
1474 * This algorithm could do fancy things like analyzing the operands of |
1475 * for common subsequences. Someday. This code is simple and finds most
1476 * of the interesting cases.
1478 * Note that must and mlen got initialized during setup.
1487 sop *newstart = NULL;
1493 /* avoid making error situations worse */
1497 /* find the longest OCHAR sequence in strip */
1499 start = scan = g->strip + 1;
1503 case OCHAR: /* sequence member */
1504 if (newlen == 0) /* new sequence */
1505 newstart = scan - 1;
1508 case OPLUS_: /* things that don't break one */
1512 case OQUEST_: /* things that must be skipped */
1518 /* assert() interferes w debug printouts */
1519 if (OP(s) != O_QUEST && OP(s) != O_CH &&
1524 } while (OP(s) != O_QUEST && OP(s) != O_CH);
1526 default: /* things that break a sequence */
1527 if (newlen > g->mlen) { /* ends one */
1534 } while (OP(s) != OEND);
1536 if (g->mlen == 0) /* there isn't one */
1539 /* turn it into a character string */
1540 g->must = malloc((size_t)g->mlen + 1);
1541 if (g->must == NULL) { /* argh; just forget it */
1547 for (i = g->mlen; i > 0; i--) {
1549 while (OP(s) != OCHAR)
1551 assert(cp < g->must + g->mlen);
1552 *cp++ = (char)OPND(s);
1554 assert(cp == g->must + g->mlen);
1555 *cp++ = '\0'; /* just on general principles */
1559 - pluscount - count + nesting
1560 == static sopno pluscount(struct parse *p, register struct re_guts *g);
1562 static sopno /* nesting depth */
1573 return(0); /* there may not be an OEND */
1575 scan = g->strip + 1;
1583 if (plusnest > maxnest)
1588 } while (OP(s) != OEND);