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