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