?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Cygwin: (mostly) drop NT4 and Samba < 3.0 support
[newlib-cygwin.git] / winsup / cygwin / regex / regcomp.c
blob7899ae7fce3c1143277c5133940bfe7d8339e567
1 /*-
2 * SPDX-License-Identifier: BSD-3-Clause
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 * Copyright (c) 2011 The FreeBSD Foundation
9 *
10 * Portions of this software were developed by David Chisnall
11 * under sponsorship from the FreeBSD Foundation.
12 *
13 * This code is derived from software contributed to Berkeley by
14 * Henry Spencer.
15 *
16 * Redistribution and use in source and binary forms, with or without
17 * modification, are permitted provided that the following conditions
18 * are met:
19 * 1. Redistributions of source code must retain the above copyright
20 * notice, this list of conditions and the following disclaimer.
21 * 2. Redistributions in binary form must reproduce the above copyright
22 * notice, this list of conditions and the following disclaimer in the
23 * documentation and/or other materials provided with the distribution.
24 * 3. Neither the name of the University nor the names of its contributors
25 * may be used to endorse or promote products derived from this software
26 * without specific prior written permission.
27 *
28 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
29 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
30 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
31 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
32 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
36 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
37 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
38 * SUCH DAMAGE.
39 *
40 * @(#)regcomp.c 8.5 (Berkeley) 3/20/94
41 */
42
43 #if defined(LIBC_SCCS) && !defined(lint)
44 static char sccsid[] = "@(#)regcomp.c 8.5 (Berkeley) 3/20/94";
45 #endif /* LIBC_SCCS and not lint */
46 #include <sys/cdefs.h>
47 __FBSDID("$FreeBSD$");
48
49 #include <sys/types.h>
50 #include <stdio.h>
51 #include <string.h>
52 #include <ctype.h>
53 #include <limits.h>
54 #include <stdlib.h>
55 #include <regex.h>
56 #include <stdbool.h>
57 #include <wchar.h>
58 #include <wctype.h>
59
60 /* We want the extensions implemented with LIBREGEX... */
61 #ifdef __CYGWIN__
62 #define LIBREGEX
63 #endif
64
65 /* ...but we also want to use the collation functions from nlsfuncs.cc. */
66 #if 1//ndef LIBREGEX
67 #include "collate.h"
68 #endif
69
70 #include "winsup.h"
71 #include "utils.h"
72 #include "regex2.h"
73
74 #include "cname.h"
75
76 /*
77 * Branching context, used to keep track of branch state for all of the branch-
78 * aware functions. In addition to keeping track of branch positions for the
79 * p_branch_* functions, we use this to simplify some clumsiness in BREs for
80 * detection of whether ^ is acting as an anchor or being used erroneously and
81 * also for whether we're in a sub-expression or not.
82 */
83 struct branchc {
84 sopno start;
85 sopno back;
86 sopno fwd;
87
88 int nbranch;
89 int nchain;
90 bool outer;
91 bool terminate;
92 };
93
94 /*
95 * parse structure, passed up and down to avoid global variables and
96 * other clumsinesses
97 */
98 struct parse {
99 const char *next; /* next character in RE */
100 const char *end; /* end of string (-> NUL normally) */
101 int error; /* has an error been seen? */
102 int gnuext;
103 sop *strip; /* malloced strip */
104 sopno ssize; /* malloced strip size (allocated) */
105 sopno slen; /* malloced strip length (used) */
106 int ncsalloc; /* number of csets allocated */
107 struct re_guts *g;
108 # define NPAREN 10 /* we need to remember () 1-9 for back refs */
109 sopno pbegin[NPAREN]; /* -> ( ([0] unused) */
110 sopno pend[NPAREN]; /* -> ) ([0] unused) */
111 bool allowbranch; /* can this expression branch? */
112 bool bre; /* convenience; is this a BRE? */
113 int pflags; /* other parsing flags -- legacy escapes? */
114 bool (*parse_expr)(struct parse *, struct branchc *);
115 void (*pre_parse)(struct parse *, struct branchc *);
116 void (*post_parse)(struct parse *, struct branchc *);
117 };
118
119 #define PFLAG_LEGACY_ESC 0x00000001
120
121 /* ========= begin header generated by ./mkh ========= */
122 #ifdef __cplusplus
123 extern "C" {
124 #endif
125
126 /* === regcomp.c === */
127 static bool p_ere_exp(struct parse *p, struct branchc *bc);
128 static void p_str(struct parse *p);
129 static int p_branch_eat_delim(struct parse *p, struct branchc *bc);
130 static void p_branch_ins_offset(struct parse *p, struct branchc *bc);
131 static void p_branch_fix_tail(struct parse *p, struct branchc *bc);
132 static bool p_branch_empty(struct parse *p, struct branchc *bc);
133 static bool p_branch_do(struct parse *p, struct branchc *bc);
134 static void p_bre_pre_parse(struct parse *p, struct branchc *bc);
135 static void p_bre_post_parse(struct parse *p, struct branchc *bc);
136 static void p_re(struct parse *p, int end1, int end2);
137 static bool p_simp_re(struct parse *p, struct branchc *bc);
138 static int p_count(struct parse *p);
139 static void p_bracket(struct parse *p);
140 static int p_range_cmp(wint_t c1, wint_t c2);
141 static void p_b_term(struct parse *p, cset *cs);
142 static int p_b_pseudoclass(struct parse *p, char c);
143 static void p_b_cclass(struct parse *p, cset *cs);
144 static void p_b_cclass_named(struct parse *p, cset *cs, const char[]);
145 static void p_b_eclass(struct parse *p, cset *cs);
146 static wint_t p_b_symbol(struct parse *p);
147 static wint_t p_b_coll_elem(struct parse *p, wint_t endc);
148 static bool may_escape(struct parse *p, const wint_t ch);
149 static wint_t othercase(wint_t ch);
150 static void bothcases(struct parse *p, wint_t ch);
151 static void ordinary(struct parse *p, wint_t ch);
152 static void nonnewline(struct parse *p);
153 static void repeat(struct parse *p, sopno start, int from, int to);
154 static int seterr(struct parse *p, int e);
155 static cset *allocset(struct parse *p);
156 static void freeset(struct parse *p, cset *cs);
157 static void CHadd(struct parse *p, cset *cs, wint_t ch);
158 static void CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max);
159 static void CHaddtype(struct parse *p, cset *cs, wctype_t wct);
160 static wint_t singleton(cset *cs);
161 static sopno dupl(struct parse *p, sopno start, sopno finish);
162 static void doemit(struct parse *p, sop op, size_t opnd);
163 static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
164 static void dofwd(struct parse *p, sopno pos, sop value);
165 static int enlarge(struct parse *p, sopno size);
166 static void stripsnug(struct parse *p, struct re_guts *g);
167 static void findmust(struct parse *p, struct re_guts *g);
168 static int altoffset(sop *scan, int offset);
169 static void computejumps(struct parse *p, struct re_guts *g);
170 static void computematchjumps(struct parse *p, struct re_guts *g);
171 static sopno pluscount(struct parse *p, struct re_guts *g);
172 static wint_t wgetnext(struct parse *p);
173
174 #ifdef __cplusplus
175 }
176 #endif
177 /* ========= end header generated by ./mkh ========= */
178
179 static char nuls[10]; /* place to point scanner in event of error */
180
181 /*
182 * macros for use with parse structure
183 * BEWARE: these know that the parse structure is named `p' !!!
184 */
185 #define PEEK() (*p->next)
186 #define PEEK2() (*(p->next+1))
187 #define MORE() (p->end - p->next > 0)
188 #define MORE2() (p->end - p->next > 1)
189 #define SEE(c) (MORE() && PEEK() == (c))
190 #define SEETWO(a, b) (MORE2() && PEEK() == (a) && PEEK2() == (b))
191 #define SEESPEC(a) (p->bre ? SEETWO('\\', a) : SEE(a))
192 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
193 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
194 #define EATSPEC(a) (p->bre ? EATTWO('\\', a) : EAT(a))
195 #define NEXT() (p->next++)
196 #define NEXT2() (p->next += 2)
197 #define NEXTn(n) (p->next += (n))
198 #define GETNEXT() (*p->next++)
199 #define WGETNEXT() wgetnext(p)
200 #define SETERROR(e) seterr(p, (e))
201 #define REQUIRE(co, e) ((co) || SETERROR(e))
202 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
203 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
204 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
205 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
206 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
207 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
208 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
209 #define HERE() (p->slen)
210 #define THERE() (p->slen - 1)
211 #define THERETHERE() (p->slen - 2)
212 #define DROP(n) (p->slen -= (n))
213
214 /* Macro used by computejump()/computematchjump() */
215 #define MIN(a,b) ((a)<(b)?(a):(b))
216
217 static int /* 0 success, otherwise REG_something */
218 regcomp_internal(regex_t * __restrict preg,
219 const char * __restrict pattern,
220 int cflags, int pflags)
221 {
222 struct parse pa;
223 struct re_guts *g;
224 struct parse *p = &pa;
225 int i;
226 size_t len;
227 size_t maxlen;
228 #ifdef REDEBUG
229 # define GOODFLAGS(f) (f)
230 #else
231 # define GOODFLAGS(f) ((f)&~REG_DUMP)
232 #endif
233
234 cflags = GOODFLAGS(cflags);
235 if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
236 return(REG_INVARG);
237
238 if (cflags&REG_PEND) {
239 if (preg->re_endp < pattern)
240 return(REG_INVARG);
241 len = preg->re_endp - pattern;
242 } else
243 len = strlen(pattern);
244
245 /* do the mallocs early so failure handling is easy */
246 g = (struct re_guts *)malloc(sizeof(struct re_guts));
247 if (g == NULL)
248 return(REG_ESPACE);
249 /*
250 * Limit the pattern space to avoid a 32-bit overflow on buffer
251 * extension. Also avoid any signed overflow in case of conversion
252 * so make the real limit based on a 31-bit overflow.
253 *
254 * Likely not applicable on 64-bit systems but handle the case
255 * generically (who are we to stop people from using ~715MB+
256 * patterns?).
257 */
258 maxlen = ((size_t)-1 >> 1) / sizeof(sop) * 2 / 3;
259 if (len >= maxlen) {
260 free((char *)g);
261 return(REG_ESPACE);
262 }
263 p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */
264 assert(p->ssize >= len);
265
266 p->strip = (sop *)malloc(p->ssize * sizeof(sop));
267 p->slen = 0;
268 if (p->strip == NULL) {
269 free((char *)g);
270 return(REG_ESPACE);
271 }
272
273 /* set things up */
274 p->g = g;
275 p->next = pattern; /* convenience; we do not modify it */
276 p->end = p->next + len;
277 p->error = 0;
278 p->ncsalloc = 0;
279 p->pflags = pflags;
280 for (i = 0; i < NPAREN; i++) {
281 p->pbegin[i] = 0;
282 p->pend[i] = 0;
283 }
284 #ifdef LIBREGEX
285 if (cflags&REG_POSIX) {
286 p->gnuext = false;
287 p->allowbranch = (cflags & REG_EXTENDED) != 0;
288 } else
289 p->gnuext = p->allowbranch = true;
290 #else
291 p->gnuext = false;
292 p->allowbranch = (cflags & REG_EXTENDED) != 0;
293 #endif
294 if (cflags & REG_EXTENDED) {
295 p->bre = false;
296 p->parse_expr = p_ere_exp;
297 p->pre_parse = NULL;
298 p->post_parse = NULL;
299 } else {
300 p->bre = true;
301 p->parse_expr = p_simp_re;
302 p->pre_parse = p_bre_pre_parse;
303 p->post_parse = p_bre_post_parse;
304 }
305 g->sets = NULL;
306 g->ncsets = 0;
307 g->cflags = cflags;
308 g->iflags = 0;
309 g->nbol = 0;
310 g->neol = 0;
311 g->must = NULL;
312 g->moffset = -1;
313 g->charjump = NULL;
314 g->matchjump = NULL;
315 g->mlen = 0;
316 g->nsub = 0;
317 g->backrefs = 0;
318
319 /* do it */
320 EMIT(OEND, 0);
321 g->firststate = THERE();
322 if (cflags & REG_NOSPEC)
323 p_str(p);
324 else
325 p_re(p, OUT, OUT);
326 EMIT(OEND, 0);
327 g->laststate = THERE();
328
329 /* tidy up loose ends and fill things in */
330 stripsnug(p, g);
331 findmust(p, g);
332 /* only use Boyer-Moore algorithm if the pattern is bigger
333 * than three characters
334 */
335 if(g->mlen > 3) {
336 computejumps(p, g);
337 computematchjumps(p, g);
338 if(g->matchjump == NULL && g->charjump != NULL) {
339 free(&g->charjump[CHAR_MIN]);
340 g->charjump = NULL;
341 }
342 }
343 g->nplus = pluscount(p, g);
344 g->magic = MAGIC2;
345 preg->re_nsub = g->nsub;
346 preg->re_g = g;
347 preg->re_magic = MAGIC1;
348 #ifndef REDEBUG
349 /* not debugging, so can't rely on the assert() in regexec() */
350 if (g->iflags&BAD)
351 SETERROR(REG_ASSERT);
352 #endif
353
354 /* win or lose, we're done */
355 if (p->error != 0) /* lose */
356 regfree(preg);
357 return(p->error);
358 }
359
360 /*
361 - regcomp - interface for parser and compilation
362 = extern int regcomp(regex_t *, const char *, int);
363 = #define REG_BASIC 0000
364 = #define REG_EXTENDED 0001
365 = #define REG_ICASE 0002
366 = #define REG_NOSUB 0004
367 = #define REG_NEWLINE 0010
368 = #define REG_NOSPEC 0020
369 = #define REG_PEND 0040
370 = #define REG_DUMP 0200
371 */
372 int /* 0 success, otherwise REG_something */
373 regcomp(regex_t * __restrict preg,
374 const char * __restrict pattern,
375 int cflags)
376 {
377
378 return (regcomp_internal(preg, pattern, cflags, 0));
379 }
380
381 #ifndef LIBREGEX
382 /*
383 * Legacy interface that requires more lax escaping behavior.
384 */
385 int
386 freebsd12_regcomp(regex_t * __restrict preg,
387 const char * __restrict pattern,
388 int cflags, int pflags)
389 {
390
391 return (regcomp_internal(preg, pattern, cflags, PFLAG_LEGACY_ESC));
392 }
393
394 __sym_compat(regcomp, freebsd12_regcomp, FBSD_1.0);
395 #endif /* !LIBREGEX */
396
397 /*
398 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op,
399 - return whether we should terminate or not
400 == static bool p_ere_exp(struct parse *p);
401 */
402 static bool
403 p_ere_exp(struct parse *p, struct branchc *bc)
404 {
405 char c;
406 wint_t wc;
407 sopno pos;
408 int count;
409 int count2;
410 #ifdef LIBREGEX
411 int i;
412 int handled;
413 #endif
414 sopno subno;
415 int wascaret = 0;
416
417 (void)bc;
418 assert(MORE()); /* caller should have ensured this */
419 c = GETNEXT();
420
421 #ifdef LIBREGEX
422 handled = 0;
423 #endif
424 pos = HERE();
425 switch (c) {
426 case '(':
427 (void)REQUIRE(MORE(), REG_EPAREN);
428 p->g->nsub++;
429 subno = p->g->nsub;
430 if (subno < NPAREN)
431 p->pbegin[subno] = HERE();
432 EMIT(OLPAREN, subno);
433 if (!SEE(')'))
434 p_re(p, ')', IGN);
435 if (subno < NPAREN) {
436 p->pend[subno] = HERE();
437 assert(p->pend[subno] != 0);
438 }
439 EMIT(ORPAREN, subno);
440 (void)MUSTEAT(')', REG_EPAREN);
441 break;
442 #ifndef POSIX_MISTAKE
443 case ')': /* happens only if no current unmatched ( */
444 /*
445 * You may ask, why the ifndef? Because I didn't notice
446 * this until slightly too late for 1003.2, and none of the
447 * other 1003.2 regular-expression reviewers noticed it at
448 * all. So an unmatched ) is legal POSIX, at least until
449 * we can get it fixed.
450 */
451 SETERROR(REG_EPAREN);
452 break;
453 #endif
454 case '^':
455 EMIT(OBOL, 0);
456 p->g->iflags |= USEBOL;
457 p->g->nbol++;
458 wascaret = 1;
459 break;
460 case '$':
461 EMIT(OEOL, 0);
462 p->g->iflags |= USEEOL;
463 p->g->neol++;
464 break;
465 case '|':
466 SETERROR(REG_EMPTY);
467 break;
468 case '*':
469 case '+':
470 case '?':
471 case '{':
472 SETERROR(REG_BADRPT);
473 break;
474 case '.':
475 if (p->g->cflags&REG_NEWLINE)
476 nonnewline(p);
477 else
478 EMIT(OANY, 0);
479 break;
480 case '[':
481 p_bracket(p);
482 break;
483 case '\\':
484 (void)REQUIRE(MORE(), REG_EESCAPE);
485 wc = WGETNEXT();
486 #ifdef LIBREGEX
487 if (p->gnuext) {
488 handled = 1;
489 switch (wc) {
490 case '`':
491 EMIT(OBOS, 0);
492 break;
493 case '\'':
494 EMIT(OEOS, 0);
495 break;
496 case 'B':
497 EMIT(ONWBND, 0);
498 break;
499 case 'b':
500 EMIT(OWBND, 0);
501 break;
502 case 'W':
503 case 'w':
504 case 'S':
505 case 's':
506 p_b_pseudoclass(p, wc);
507 break;
508 case '1':
509 case '2':
510 case '3':
511 case '4':
512 case '5':
513 case '6':
514 case '7':
515 case '8':
516 case '9':
517 i = wc - '0';
518 assert(i < NPAREN);
519 if (p->pend[i] != 0) {
520 assert(i <= p->g->nsub);
521 EMIT(OBACK_, i);
522 assert(p->pbegin[i] != 0);
523 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
524 assert(OP(p->strip[p->pend[i]]) == ORPAREN);
525 (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
526 EMIT(O_BACK, i);
527 } else
528 SETERROR(REG_ESUBREG);
529 p->g->backrefs = 1;
530 break;
531 default:
532 handled = 0;
533 }
534 /* Don't proceed to the POSIX bits if we've already handled it */
535 if (handled)
536 break;
537 }
538 #endif
539 switch (wc) {
540 case '<':
541 EMIT(OBOW, 0);
542 break;
543 case '>':
544 EMIT(OEOW, 0);
545 break;
546 default:
547 if (may_escape(p, wc))
548 ordinary(p, wc);
549 else
550 SETERROR(REG_EESCAPE);
551 break;
552 }
553 break;
554 default:
555 if (p->error != 0)
556 return (false);
557 p->next--;
558 wc = WGETNEXT();
559 ordinary(p, wc);
560 break;
561 }
562
563 if (!MORE())
564 return (false);
565 c = PEEK();
566 /* we call { a repetition if followed by a digit */
567 if (!( c == '*' || c == '+' || c == '?' || c == '{'))
568 return (false); /* no repetition, we're done */
569 else if (c == '{')
570 (void)REQUIRE(MORE2() && \
571 (isdigit((uch)PEEK2()) || PEEK2() == ','), REG_BADRPT);
572 NEXT();
573
574 (void)REQUIRE(!wascaret, REG_BADRPT);
575 switch (c) {
576 case '*': /* implemented as +? */
577 /* this case does not require the (y|) trick, noKLUDGE */
578 INSERT(OPLUS_, pos);
579 ASTERN(O_PLUS, pos);
580 INSERT(OQUEST_, pos);
581 ASTERN(O_QUEST, pos);
582 break;
583 case '+':
584 INSERT(OPLUS_, pos);
585 ASTERN(O_PLUS, pos);
586 break;
587 case '?':
588 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
589 INSERT(OCH_, pos); /* offset slightly wrong */
590 ASTERN(OOR1, pos); /* this one's right */
591 AHEAD(pos); /* fix the OCH_ */
592 EMIT(OOR2, 0); /* offset very wrong... */
593 AHEAD(THERE()); /* ...so fix it */
594 ASTERN(O_CH, THERETHERE());
595 break;
596 case '{':
597 count = p_count(p);
598 if (EAT(',')) {
599 if (isdigit((uch)PEEK())) {
600 count2 = p_count(p);
601 (void)REQUIRE(count <= count2, REG_BADBR);
602 } else /* single number with comma */
603 count2 = INFINITY;
604 } else /* just a single number */
605 count2 = count;
606 repeat(p, pos, count, count2);
607 if (!EAT('}')) { /* error heuristics */
608 while (MORE() && PEEK() != '}')
609 NEXT();
610 (void)REQUIRE(MORE(), REG_EBRACE);
611 SETERROR(REG_BADBR);
612 }
613 break;
614 }
615
616 if (!MORE())
617 return (false);
618 c = PEEK();
619 if (!( c == '*' || c == '+' || c == '?' ||
620 (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) )
621 return (false);
622 SETERROR(REG_BADRPT);
623 return (false);
624 }
625
626 /*
627 - p_str - string (no metacharacters) "parser"
628 == static void p_str(struct parse *p);
629 */
630 static void
631 p_str(struct parse *p)
632 {
633 (void)REQUIRE(MORE(), REG_EMPTY);
634 while (MORE())
635 ordinary(p, WGETNEXT());
636 }
637
638 /*
639 * Eat consecutive branch delimiters for the kind of expression that we are
640 * parsing, return the number of delimiters that we ate.
641 */
642 static int
643 p_branch_eat_delim(struct parse *p, struct branchc *bc)
644 {
645 int nskip;
646
647 (void)bc;
648 nskip = 0;
649 while (EATSPEC('|'))
650 ++nskip;
651 return (nskip);
652 }
653
654 /*
655 * Insert necessary branch book-keeping operations. This emits a
656 * bogus 'next' offset, since we still have more to parse
657 */
658 static void
659 p_branch_ins_offset(struct parse *p, struct branchc *bc)
660 {
661
662 if (bc->nbranch == 0) {
663 INSERT(OCH_, bc->start); /* offset is wrong */
664 bc->fwd = bc->start;
665 bc->back = bc->start;
666 }
667
668 ASTERN(OOR1, bc->back);
669 bc->back = THERE();
670 AHEAD(bc->fwd); /* fix previous offset */
671 bc->fwd = HERE();
672 EMIT(OOR2, 0); /* offset is very wrong */
673 ++bc->nbranch;
674 }
675
676 /*
677 * Fix the offset of the tail branch, if we actually had any branches.
678 * This is to correct the bogus placeholder offset that we use.
679 */
680 static void
681 p_branch_fix_tail(struct parse *p, struct branchc *bc)
682 {
683
684 /* Fix bogus offset at the tail if we actually have branches */
685 if (bc->nbranch > 0) {
686 AHEAD(bc->fwd);
687 ASTERN(O_CH, bc->back);
688 }
689 }
690
691 /*
692 * Signal to the parser that an empty branch has been encountered; this will,
693 * in the future, be used to allow for more permissive behavior with empty
694 * branches. The return value should indicate whether parsing may continue
695 * or not.
696 */
697 static bool
698 p_branch_empty(struct parse *p, struct branchc *bc)
699 {
700
701 (void)bc;
702 SETERROR(REG_EMPTY);
703 return (false);
704 }
705
706 /*
707 * Take care of any branching requirements. This includes inserting the
708 * appropriate branching instructions as well as eating all of the branch
709 * delimiters until we either run out of pattern or need to parse more pattern.
710 */
711 static bool
712 p_branch_do(struct parse *p, struct branchc *bc)
713 {
714 int ate = 0;
715
716 ate = p_branch_eat_delim(p, bc);
717 if (ate == 0)
718 return (false);
719 else if ((ate > 1 || (bc->outer && !MORE())) && !p_branch_empty(p, bc))
720 /*
721 * Halt parsing only if we have an empty branch and p_branch_empty
722 * indicates that we must not continue. In the future, this will not
723 * necessarily be an error.
724 */
725 return (false);
726 p_branch_ins_offset(p, bc);
727
728 return (true);
729 }
730
731 static void
732 p_bre_pre_parse(struct parse *p, struct branchc *bc)
733 {
734
735 (void) bc;
736 /*
737 * Does not move cleanly into expression parser because of
738 * ordinary interpration of * at the beginning position of
739 * an expression.
740 */
741 if (EAT('^')) {
742 EMIT(OBOL, 0);
743 p->g->iflags |= USEBOL;
744 p->g->nbol++;
745 }
746 }
747
748 static void
749 p_bre_post_parse(struct parse *p, struct branchc *bc)
750 {
751
752 /* Expression is terminating due to EOL token */
753 if (bc->terminate) {
754 DROP(1);
755 EMIT(OEOL, 0);
756 p->g->iflags |= USEEOL;
757 p->g->neol++;
758 }
759 }
760
761 /*
762 - p_re - Top level parser, concatenation and BRE anchoring
763 == static void p_re(struct parse *p, int end1, int end2);
764 * Giving end1 as OUT essentially eliminates the end1/end2 check.
765 *
766 * This implementation is a bit of a kludge, in that a trailing $ is first
767 * taken as an ordinary character and then revised to be an anchor.
768 * The amount of lookahead needed to avoid this kludge is excessive.
769 */
770 static void
771 p_re(struct parse *p,
772 int end1, /* first terminating character */
773 int end2) /* second terminating character; ignored for EREs */
774 {
775 struct branchc bc;
776
777 bc.nbranch = 0;
778 if (end1 == OUT && end2 == OUT)
779 bc.outer = true;
780 else
781 bc.outer = false;
782 #define SEEEND() (!p->bre ? SEE(end1) : SEETWO(end1, end2))
783 for (;;) {
784 bc.start = HERE();
785 bc.nchain = 0;
786 bc.terminate = false;
787 if (p->pre_parse != NULL)
788 p->pre_parse(p, &bc);
789 while (MORE() && (!p->allowbranch || !SEESPEC('|')) && !SEEEND()) {
790 bc.terminate = p->parse_expr(p, &bc);
791 ++bc.nchain;
792 }
793 if (p->post_parse != NULL)
794 p->post_parse(p, &bc);
795 (void) REQUIRE(p->gnuext || HERE() != bc.start, REG_EMPTY);
796 #ifdef LIBREGEX
797 if (HERE() == bc.start && !p_branch_empty(p, &bc))
798 break;
799 #endif
800 if (!p->allowbranch)
801 break;
802 /*
803 * p_branch_do's return value indicates whether we should
804 * continue parsing or not. This is both for correctness and
805 * a slight optimization, because it will check if we've
806 * encountered an empty branch or the end of the string
807 * immediately following a branch delimiter.
808 */
809 if (!p_branch_do(p, &bc))
810 break;
811 }
812 #undef SEE_END
813 if (p->allowbranch)
814 p_branch_fix_tail(p, &bc);
815 assert(!MORE() || SEE(end1));
816 }
817
818 /*
819 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
820 == static bool p_simp_re(struct parse *p, struct branchc *bc);
821 */
822 static bool /* was the simple RE an unbackslashed $? */
823 p_simp_re(struct parse *p, struct branchc *bc)
824 {
825 int c;
826 int cc; /* convenient/control character */
827 int count;
828 int count2;
829 sopno pos;
830 bool handled;
831 int i;
832 wint_t wc;
833 sopno subno;
834 # define BACKSL (1<<CHAR_BIT)
835
836 pos = HERE(); /* repetition op, if any, covers from here */
837 handled = false;
838
839 assert(MORE()); /* caller should have ensured this */
840 c = GETNEXT();
841 if (c == '\\') {
842 (void)REQUIRE(MORE(), REG_EESCAPE);
843 cc = GETNEXT();
844 c = BACKSL | cc;
845 #ifdef LIBREGEX
846 if (p->gnuext) {
847 handled = true;
848 switch (c) {
849 case BACKSL|'`':
850 EMIT(OBOS, 0);
851 break;
852 case BACKSL|'\'':
853 EMIT(OEOS, 0);
854 break;
855 case BACKSL|'B':
856 EMIT(ONWBND, 0);
857 break;
858 case BACKSL|'b':
859 EMIT(OWBND, 0);
860 break;
861 case BACKSL|'W':
862 case BACKSL|'w':
863 case BACKSL|'S':
864 case BACKSL|'s':
865 p_b_pseudoclass(p, cc);
866 break;
867 default:
868 handled = false;
869 }
870 }
871 #endif
872 }
873 if (!handled) {
874 switch (c) {
875 case '.':
876 if (p->g->cflags&REG_NEWLINE)
877 nonnewline(p);
878 else
879 EMIT(OANY, 0);
880 break;
881 case '[':
882 p_bracket(p);
883 break;
884 case BACKSL|'<':
885 EMIT(OBOW, 0);
886 break;
887 case BACKSL|'>':
888 EMIT(OEOW, 0);
889 break;
890 case BACKSL|'{':
891 SETERROR(REG_BADRPT);
892 break;
893 case BACKSL|'(':
894 p->g->nsub++;
895 subno = p->g->nsub;
896 if (subno < NPAREN)
897 p->pbegin[subno] = HERE();
898 EMIT(OLPAREN, subno);
899 /* the MORE here is an error heuristic */
900 if (MORE() && !SEETWO('\\', ')'))
901 p_re(p, '\\', ')');
902 if (subno < NPAREN) {
903 p->pend[subno] = HERE();
904 assert(p->pend[subno] != 0);
905 }
906 EMIT(ORPAREN, subno);
907 (void)REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
908 break;
909 case BACKSL|')': /* should not get here -- must be user */
910 SETERROR(REG_EPAREN);
911 break;
912 case BACKSL|'1':
913 case BACKSL|'2':
914 case BACKSL|'3':
915 case BACKSL|'4':
916 case BACKSL|'5':
917 case BACKSL|'6':
918 case BACKSL|'7':
919 case BACKSL|'8':
920 case BACKSL|'9':
921 i = (c&~BACKSL) - '0';
922 assert(i < NPAREN);
923 if (p->pend[i] != 0) {
924 assert(i <= p->g->nsub);
925 EMIT(OBACK_, i);
926 assert(p->pbegin[i] != 0);
927 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
928 assert(OP(p->strip[p->pend[i]]) == ORPAREN);
929 (void) dupl(p, p->pbegin[i]+1, p->pend[i]);
930 EMIT(O_BACK, i);
931 } else
932 SETERROR(REG_ESUBREG);
933 p->g->backrefs = 1;
934 break;
935 case '*':
936 /*
937 * Ordinary if used as the first character beyond BOL anchor of
938 * a (sub-)expression, counts as a bad repetition operator if it
939 * appears otherwise.
940 */
941 (void)REQUIRE(bc->nchain == 0, REG_BADRPT);
942 fallthrough;
943 default:
944 if (p->error != 0)
945 return (false); /* Definitely not $... */
946 p->next--;
947 wc = WGETNEXT();
948 if ((c & BACKSL) == 0 || may_escape(p, wc))
949 ordinary(p, wc);
950 else
951 SETERROR(REG_EESCAPE);
952 break;
953 }
954 }
955
956 if (EAT('*')) { /* implemented as +? */
957 /* this case does not require the (y|) trick, noKLUDGE */
958 INSERT(OPLUS_, pos);
959 ASTERN(O_PLUS, pos);
960 INSERT(OQUEST_, pos);
961 ASTERN(O_QUEST, pos);
962 #ifdef LIBREGEX
963 } else if (p->gnuext && EATTWO('\\', '?')) {
964 INSERT(OQUEST_, pos);
965 ASTERN(O_QUEST, pos);
966 } else if (p->gnuext && EATTWO('\\', '+')) {
967 INSERT(OPLUS_, pos);
968 ASTERN(O_PLUS, pos);
969 #endif
970 } else if (EATTWO('\\', '{')) {
971 count = p_count(p);
972 if (EAT(',')) {
973 if (MORE() && isdigit((uch)PEEK())) {
974 count2 = p_count(p);
975 (void)REQUIRE(count <= count2, REG_BADBR);
976 } else /* single number with comma */
977 count2 = INFINITY;
978 } else /* just a single number */
979 count2 = count;
980 repeat(p, pos, count, count2);
981 if (!EATTWO('\\', '}')) { /* error heuristics */
982 while (MORE() && !SEETWO('\\', '}'))
983 NEXT();
984 (void)REQUIRE(MORE(), REG_EBRACE);
985 SETERROR(REG_BADBR);
986 }
987 } else if (c == '$') /* $ (but not \$) ends it */
988 return (true);
989
990 return (false);
991 }
992
993 /*
994 - p_count - parse a repetition count
995 == static int p_count(struct parse *p);
996 */
997 static int /* the value */
998 p_count(struct parse *p)
999 {
1000 int count = 0;
1001 int ndigits = 0;
1002
1003 while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) {
1004 count = count*10 + (GETNEXT() - '0');
1005 ndigits++;
1006 }
1007
1008 (void)REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
1009 return(count);
1010 }
1011
1012 /*
1013 - p_bracket - parse a bracketed character list
1014 == static void p_bracket(struct parse *p);
1015 */
1016 static void
1017 p_bracket(struct parse *p)
1018 {
1019 cset *cs;
1020 wint_t ch;
1021
1022 /* Dept of Truly Sickening Special-Case Kludges */
1023 if (p->end - p->next > 5) {
1024 if (strncmp(p->next, "[:<:]]", 6) == 0) {
1025 EMIT(OBOW, 0);
1026 NEXTn(6);
1027 return;
1028 }
1029 if (strncmp(p->next, "[:>:]]", 6) == 0) {
1030 EMIT(OEOW, 0);
1031 NEXTn(6);
1032 return;
1033 }
1034 }
1035
1036 if ((cs = allocset(p)) == NULL)
1037 return;
1038
1039 if (p->g->cflags&REG_ICASE)
1040 cs->icase = 1;
1041 if (EAT('^'))
1042 cs->invert = 1;
1043 if (EAT(']'))
1044 CHadd(p, cs, ']');
1045 else if (EAT('-'))
1046 CHadd(p, cs, '-');
1047 while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
1048 p_b_term(p, cs);
1049 if (EAT('-'))
1050 CHadd(p, cs, '-');
1051 (void)MUSTEAT(']', REG_EBRACK);
1052
1053 if (p->error != 0) /* don't mess things up further */
1054 return;
1055
1056 if (cs->invert && p->g->cflags&REG_NEWLINE)
1057 cs->bmp['\n' >> 3] |= 1 << ('\n' & 7);
1058
1059 if ((ch = singleton(cs)) != OUT) { /* optimize singleton sets */
1060 ordinary(p, ch);
1061 freeset(p, cs);
1062 } else
1063 EMIT(OANYOF, (int)(cs - p->g->sets));
1064 }
1065
1066 static int
1067 p_range_cmp(wint_t c1, wint_t c2)
1068 {
1069 #if 1//ndef LIBREGEX
1070 return __wcollate_range_cmp(c1, c2);
1071 #else
1072 /* Copied from libc/collate __wcollate_range_cmp */
1073 wint_t s1[2], s2[2];
1074
1075 s1[0] = c1;
1076 s1[1] = L'\0';
1077 s2[0] = c2;
1078 s2[1] = L'\0';
1079 return (wcscoll(s1, s2));
1080 #endif
1081 }
1082
1083 /*
1084 - p_b_term - parse one term of a bracketed character list
1085 == static void p_b_term(struct parse *p, cset *cs);
1086 */
1087 static void
1088 p_b_term(struct parse *p, cset *cs)
1089 {
1090 char c;
1091 wint_t start, finish;
1092 wint_t i;
1093 #ifndef LIBREGEX
1094 struct xlocale_collate *table =
1095 (struct xlocale_collate*)__get_locale()->components[XLC_COLLATE];
1096 #endif
1097 /* classify what we've got */
1098 switch ((MORE()) ? PEEK() : '\0') {
1099 case '[':
1100 c = (MORE2()) ? PEEK2() : '\0';
1101 break;
1102 case '-':
1103 SETERROR(REG_ERANGE);
1104 return; /* NOTE RETURN */
1105 default:
1106 c = '\0';
1107 break;
1108 }
1109
1110 switch (c) {
1111 case ':': /* character class */
1112 NEXT2();
1113 (void)REQUIRE(MORE(), REG_EBRACK);
1114 c = PEEK();
1115 (void)REQUIRE(c != '-' && c != ']', REG_ECTYPE);
1116 p_b_cclass(p, cs);
1117 (void)REQUIRE(MORE(), REG_EBRACK);
1118 (void)REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
1119 break;
1120 case '=': /* equivalence class */
1121 NEXT2();
1122 (void)REQUIRE(MORE(), REG_EBRACK);
1123 c = PEEK();
1124 (void)REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
1125 p_b_eclass(p, cs);
1126 (void)REQUIRE(MORE(), REG_EBRACK);
1127 (void)REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
1128 break;
1129 default: /* symbol, ordinary character, or range */
1130 start = p_b_symbol(p);
1131 if (SEE('-') && MORE2() && PEEK2() != ']') {
1132 /* range */
1133 NEXT();
1134 if (EAT('-'))
1135 finish = '-';
1136 else
1137 finish = p_b_symbol(p);
1138 } else
1139 finish = start;
1140 if (start == finish)
1141 CHadd(p, cs, start);
1142 else {
1143 #ifndef LIBREGEX
1144 if (table->__collate_load_error || MB_CUR_MAX > 1) {
1145 #else
1146 if (MB_CUR_MAX > 1) {
1147 #endif
1148 (void)REQUIRE(p_range_cmp(start, finish) <= 0, REG_ERANGE);
1149 CHaddrange(p, cs, start, finish);
1150 } else {
1151 (void)REQUIRE(p_range_cmp(start, finish) <= 0, REG_ERANGE);
1152 for (i = 0; i <= UCHAR_MAX; i++) {
1153 if (p_range_cmp(start, i) <= 0 &&
1154 p_range_cmp(i, finish) <= 0 )
1155 CHadd(p, cs, i);
1156 }
1157 }
1158 }
1159 break;
1160 }
1161 }
1162
1163 /*
1164 - p_b_pseudoclass - parse a pseudo-class (\w, \W, \s, \S)
1165 == static int p_b_pseudoclass(struct parse *p, char c)
1166 */
1167 static int
1168 p_b_pseudoclass(struct parse *p, char c) {
1169 cset *cs;
1170
1171 if ((cs = allocset(p)) == NULL)
1172 return(0);
1173
1174 if (p->g->cflags&REG_ICASE)
1175 cs->icase = 1;
1176
1177 switch (c) {
1178 case 'W':
1179 cs->invert = 1;
1180 fallthrough;
1181 case 'w':
1182 p_b_cclass_named(p, cs, "alnum");
1183 break;
1184 case 'S':
1185 cs->invert = 1;
1186 fallthrough;
1187 case 's':
1188 p_b_cclass_named(p, cs, "space");
1189 break;
1190 default:
1191 return(0);
1192 }
1193
1194 EMIT(OANYOF, (int)(cs - p->g->sets));
1195 return(1);
1196 }
1197
1198 /*
1199 - p_b_cclass - parse a character-class name and deal with it
1200 == static void p_b_cclass(struct parse *p, cset *cs);
1201 */
1202 static void
1203 p_b_cclass(struct parse *p, cset *cs)
1204 {
1205 const char *sp = p->next;
1206 size_t len;
1207 char clname[16];
1208
1209 while (MORE() && isalpha((uch)PEEK()))
1210 NEXT();
1211 len = p->next - sp;
1212 if (len >= sizeof(clname) - 1) {
1213 SETERROR(REG_ECTYPE);
1214 return;
1215 }
1216 memcpy(clname, sp, len);
1217 clname[len] = '\0';
1218
1219 p_b_cclass_named(p, cs, clname);
1220 }
1221 /*
1222 - p_b_cclass_named - deal with a named character class
1223 == static void p_b_cclass_named(struct parse *p, cset *cs, const char []);
1224 */
1225 static void
1226 p_b_cclass_named(struct parse *p, cset *cs, const char clname[]) {
1227 wctype_t wct;
1228
1229 if ((wct = wctype(clname)) == 0) {
1230 SETERROR(REG_ECTYPE);
1231 return;
1232 }
1233 CHaddtype(p, cs, wct);
1234 }
1235
1236 /*
1237 - p_b_eclass - parse an equivalence-class name and deal with it
1238 == static void p_b_eclass(struct parse *p, cset *cs);
1239 *
1240 * This implementation is incomplete. xxx
1241 */
1242 static void
1243 p_b_eclass(struct parse *p, cset *cs)
1244 {
1245 wint_t c;
1246
1247 c = p_b_coll_elem(p, '=');
1248 CHadd(p, cs, c);
1249 }
1250
1251 /*
1252 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
1253 == static wint_t p_b_symbol(struct parse *p);
1254 */
1255 static wint_t /* value of symbol */
1256 p_b_symbol(struct parse *p)
1257 {
1258 wint_t value;
1259
1260 (void)REQUIRE(MORE(), REG_EBRACK);
1261 if (!EATTWO('[', '.'))
1262 return(WGETNEXT());
1263
1264 /* collating symbol */
1265 value = p_b_coll_elem(p, '.');
1266 (void)REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
1267 return(value);
1268 }
1269
1270 /*
1271 - p_b_coll_elem - parse a collating-element name and look it up
1272 == static wint_t p_b_coll_elem(struct parse *p, wint_t endc);
1273 */
1274 static wint_t /* value of collating element */
1275 p_b_coll_elem(struct parse *p,
1276 wint_t endc) /* name ended by endc,']' */
1277 {
1278 const char *sp = p->next;
1279 struct cname *cp;
1280 mbstate_t mbs;
1281 wint_t wc;
1282 size_t clen, len;
1283
1284 while (MORE() && !SEETWO(endc, ']'))
1285 NEXT();
1286 if (!MORE()) {
1287 SETERROR(REG_EBRACK);
1288 return(0);
1289 }
1290 len = p->next - sp;
1291 for (cp = cnames; cp->name != NULL; cp++)
1292 if (strncmp(cp->name, sp, len) == 0 && strlen(cp->name) == len)
1293 return(cp->code); /* known name */
1294 memset(&mbs, 0, sizeof(mbs));
1295 if ((clen = mbrtowi(&wc, sp, len, &mbs)) == len)
1296 return (wc); /* single character */
1297 else if (clen == (size_t)-1 || clen == (size_t)-2)
1298 SETERROR(REG_ILLSEQ);
1299 else
1300 SETERROR(REG_ECOLLATE); /* neither */
1301 return(0);
1302 }
1303
1304 /*
1305 - may_escape - determine whether 'ch' is escape-able in the current context
1306 == static int may_escape(struct parse *p, const wint_t ch)
1307 */
1308 static bool
1309 may_escape(struct parse *p, const wint_t ch)
1310 {
1311
1312 if ((p->pflags & PFLAG_LEGACY_ESC) != 0)
1313 return (true);
1314 if (isalpha(ch) || ch == '\'' || ch == '`')
1315 return (false);
1316 return (true);
1317 #ifdef NOTYET
1318 /*
1319 * Build a whitelist of characters that may be escaped to produce an
1320 * ordinary in the current context. This assumes that these have not
1321 * been otherwise interpreted as a special character. Escaping an
1322 * ordinary character yields undefined results according to
1323 * IEEE 1003.1-2008. Some extensions (notably, some GNU extensions) take
1324 * advantage of this and use escaped ordinary characters to provide
1325 * special meaning, e.g. \b, \B, \w, \W, \s, \S.
1326 */
1327 switch(ch) {
1328 case '|':
1329 case '+':
1330 case '?':
1331 /* The above characters may not be escaped in BREs */
1332 if (!(p->g->cflags&REG_EXTENDED))
1333 return (false);
1334 /* Fallthrough */
1335 case '(':
1336 case ')':
1337 case '{':
1338 case '}':
1339 case '.':
1340 case '[':
1341 case ']':
1342 case '\\':
1343 case '*':
1344 case '^':
1345 case '$':
1346 return (true);
1347 default:
1348 return (false);
1349 }
1350 #endif
1351 }
1352
1353 /*
1354 - othercase - return the case counterpart of an alphabetic
1355 == static wint_t othercase(wint_t ch);
1356 */
1357 static wint_t /* if no counterpart, return ch */
1358 othercase(wint_t ch)
1359 {
1360 assert(iswalpha(ch));
1361 if (iswupper(ch))
1362 return(towlower(ch));
1363 else if (iswlower(ch))
1364 return(towupper(ch));
1365 else /* peculiar, but could happen */
1366 return(ch);
1367 }
1368
1369 /*
1370 - bothcases - emit a dualcase version of a two-case character
1371 == static void bothcases(struct parse *p, wint_t ch);
1372 *
1373 * Boy, is this implementation ever a kludge...
1374 */
1375 static void
1376 bothcases(struct parse *p, wint_t ch)
1377 {
1378 const char *oldnext = p->next;
1379 const char *oldend = p->end;
1380 char bracket[3 + MB_LEN_MAX];
1381 size_t n;
1382 mbstate_t mbs;
1383
1384 assert(othercase(ch) != ch); /* p_bracket() would recurse */
1385 p->next = bracket;
1386 memset(&mbs, 0, sizeof(mbs));
1387 n = wirtomb(bracket, ch, &mbs);
1388 assert(n != (size_t)-1);
1389 bracket[n] = ']';
1390 bracket[n + 1] = '\0';
1391 p->end = bracket+n+1;
1392 p_bracket(p);
1393 assert(p->next == p->end);
1394 p->next = oldnext;
1395 p->end = oldend;
1396 }
1397
1398 /*
1399 - ordinary - emit an ordinary character
1400 == static void ordinary(struct parse *p, wint_t ch);
1401 */
1402 static void
1403 ordinary(struct parse *p, wint_t ch)
1404 {
1405 cset *cs;
1406
1407 if ((p->g->cflags&REG_ICASE) && iswalpha(ch) && othercase(ch) != ch)
1408 bothcases(p, ch);
1409 else if ((ch & OPDMASK) == ch)
1410 EMIT(OCHAR, ch);
1411 else {
1412 /*
1413 * Kludge: character is too big to fit into an OCHAR operand.
1414 * Emit a singleton set.
1415 */
1416 if ((cs = allocset(p)) == NULL)
1417 return;
1418 CHadd(p, cs, ch);
1419 EMIT(OANYOF, (int)(cs - p->g->sets));
1420 }
1421 }
1422
1423 /*
1424 - nonnewline - emit REG_NEWLINE version of OANY
1425 == static void nonnewline(struct parse *p);
1426 *
1427 * Boy, is this implementation ever a kludge...
1428 */
1429 static void
1430 nonnewline(struct parse *p)
1431 {
1432 const char *oldnext = p->next;
1433 const char *oldend = p->end;
1434 char bracket[4];
1435
1436 p->next = bracket;
1437 p->end = bracket+3;
1438 bracket[0] = '^';
1439 bracket[1] = '\n';
1440 bracket[2] = ']';
1441 bracket[3] = '\0';
1442 p_bracket(p);
1443 assert(p->next == bracket+3);
1444 p->next = oldnext;
1445 p->end = oldend;
1446 }
1447
1448 /*
1449 - repeat - generate code for a bounded repetition, recursively if needed
1450 == static void repeat(struct parse *p, sopno start, int from, int to);
1451 */
1452 static void
1453 repeat(struct parse *p,
1454 sopno start, /* operand from here to end of strip */
1455 int from, /* repeated from this number */
1456 int to) /* to this number of times (maybe INFINITY) */
1457 {
1458 sopno finish = HERE();
1459 # define N 2
1460 # define INF 3
1461 # define REP(f, t) ((f)*8 + (t))
1462 # define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1463 sopno copy;
1464
1465 if (p->error != 0) /* head off possible runaway recursion */
1466 return;
1467
1468 assert(from <= to);
1469
1470 switch (REP(MAP(from), MAP(to))) {
1471 case REP(0, 0): /* must be user doing this */
1472 DROP(finish-start); /* drop the operand */
1473 break;
1474 case REP(0, 1): /* as x{1,1}? */
1475 case REP(0, N): /* as x{1,n}? */
1476 case REP(0, INF): /* as x{1,}? */
1477 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1478 INSERT(OCH_, start); /* offset is wrong... */
1479 repeat(p, start+1, 1, to);
1480 ASTERN(OOR1, start);
1481 AHEAD(start); /* ... fix it */
1482 EMIT(OOR2, 0);
1483 AHEAD(THERE());
1484 ASTERN(O_CH, THERETHERE());
1485 break;
1486 case REP(1, 1): /* trivial case */
1487 /* done */
1488 break;
1489 case REP(1, N): /* as x?x{1,n-1} */
1490 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1491 INSERT(OCH_, start);
1492 ASTERN(OOR1, start);
1493 AHEAD(start);
1494 EMIT(OOR2, 0); /* offset very wrong... */
1495 AHEAD(THERE()); /* ...so fix it */
1496 ASTERN(O_CH, THERETHERE());
1497 copy = dupl(p, start+1, finish+1);
1498 assert(copy == finish+4);
1499 repeat(p, copy, 1, to-1);
1500 break;
1501 case REP(1, INF): /* as x+ */
1502 INSERT(OPLUS_, start);
1503 ASTERN(O_PLUS, start);
1504 break;
1505 case REP(N, N): /* as xx{m-1,n-1} */
1506 copy = dupl(p, start, finish);
1507 repeat(p, copy, from-1, to-1);
1508 break;
1509 case REP(N, INF): /* as xx{n-1,INF} */
1510 copy = dupl(p, start, finish);
1511 repeat(p, copy, from-1, to);
1512 break;
1513 default: /* "can't happen" */
1514 SETERROR(REG_ASSERT); /* just in case */
1515 break;
1516 }
1517 }
1518
1519 /*
1520 - wgetnext - helper function for WGETNEXT() macro. Gets the next wide
1521 - character from the parse struct, signals a REG_ILLSEQ error if the
1522 - character can't be converted. Returns the number of bytes consumed.
1523 */
1524 static wint_t
1525 wgetnext(struct parse *p)
1526 {
1527 mbstate_t mbs;
1528 wint_t wc;
1529 size_t n;
1530
1531 #ifdef __CYGWIN__
1532 /* Kludge for more glibc compatibility. On Cygwin as well as on
1533 Linux, mbrtowc returns -1 if the current local's codeset is ASCII
1534 and the character is >= 0x80. Nevertheless, glibc's regcomp allows
1535 any char value, even stuff like [\xc0-\xff], if the locale's codeset
1536 is ASCII, so in regcomp it ignores the fact that chars >= 0x80 are
1537 invalid ASCII chars. To be more Linux-compatible, we align the
1538 behaviour to glibc here. Allow any character value if the current
1539 local's codeset is ASCII. */
1540 if (*__current_locale_charset () == 'A') /* SCII */
1541 return (wint_t) (unsigned char) *p->next++;
1542 #endif
1543 memset(&mbs, 0, sizeof(mbs));
1544 n = mbrtowi(&wc, p->next, p->end - p->next, &mbs);
1545 if (n == (size_t)-1 || n == (size_t)-2) {
1546 SETERROR(REG_ILLSEQ);
1547 return (0);
1548 }
1549 if (n == 0)
1550 n = 1;
1551 p->next += n;
1552 return (wc);
1553 }
1554
1555 /*
1556 - seterr - set an error condition
1557 == static int seterr(struct parse *p, int e);
1558 */
1559 static int /* useless but makes type checking happy */
1560 seterr(struct parse *p, int e)
1561 {
1562 if (p->error == 0) /* keep earliest error condition */
1563 p->error = e;
1564 p->next = nuls; /* try to bring things to a halt */
1565 p->end = nuls;
1566 return(0); /* make the return value well-defined */
1567 }
1568
1569 /*
1570 - allocset - allocate a set of characters for []
1571 == static cset *allocset(struct parse *p);
1572 */
1573 static cset *
1574 allocset(struct parse *p)
1575 {
1576 cset *cs, *ncs;
1577
1578 ncs = reallocarray(p->g->sets, p->g->ncsets + 1, sizeof(*ncs));
1579 if (ncs == NULL) {
1580 SETERROR(REG_ESPACE);
1581 return (NULL);
1582 }
1583 p->g->sets = ncs;
1584 cs = &p->g->sets[p->g->ncsets++];
1585 memset(cs, 0, sizeof(*cs));
1586
1587 return(cs);
1588 }
1589
1590 /*
1591 - freeset - free a now-unused set
1592 == static void freeset(struct parse *p, cset *cs);
1593 */
1594 static void
1595 freeset(struct parse *p, cset *cs)
1596 {
1597 cset *top = &p->g->sets[p->g->ncsets];
1598
1599 free(cs->wides);
1600 free(cs->ranges);
1601 free(cs->types);
1602 memset(cs, 0, sizeof(*cs));
1603 if (cs == top-1) /* recover only the easy case */
1604 p->g->ncsets--;
1605 }
1606
1607 /*
1608 - singleton - Determine whether a set contains only one character,
1609 - returning it if so, otherwise returning OUT.
1610 */
1611 static wint_t
1612 singleton(cset *cs)
1613 {
1614 wint_t i, s, n;
1615
1616 for (i = n = 0; i < NC; i++)
1617 if (CHIN(cs, i)) {
1618 n++;
1619 s = i;
1620 }
1621 if (n == 1)
1622 return (s);
1623 if (cs->nwides == 1 && cs->nranges == 0 && cs->ntypes == 0 &&
1624 cs->icase == 0)
1625 return (cs->wides[0]);
1626 /* Don't bother handling the other cases. */
1627 return (OUT);
1628 }
1629
1630 /*
1631 - CHadd - add character to character set.
1632 */
1633 static void
1634 CHadd(struct parse *p, cset *cs, wint_t ch)
1635 {
1636 wint_t nch, *newwides;
1637 assert(ch >= 0);
1638 if (ch < NC)
1639 cs->bmp[ch >> 3] |= 1 << (ch & 7);
1640 else {
1641 newwides = reallocarray(cs->wides, cs->nwides + 1,
1642 sizeof(*cs->wides));
1643 if (newwides == NULL) {
1644 SETERROR(REG_ESPACE);
1645 return;
1646 }
1647 cs->wides = newwides;
1648 cs->wides[cs->nwides++] = ch;
1649 }
1650 if (cs->icase) {
1651 if ((nch = towlower(ch)) < NC)
1652 cs->bmp[nch >> 3] |= 1 << (nch & 7);
1653 if ((nch = towupper(ch)) < NC)
1654 cs->bmp[nch >> 3] |= 1 << (nch & 7);
1655 }
1656 }
1657
1658 /*
1659 - CHaddrange - add all characters in the range [min,max] to a character set.
1660 */
1661 static void
1662 CHaddrange(struct parse *p, cset *cs, wint_t min, wint_t max)
1663 {
1664 crange *newranges;
1665
1666 for (; min < NC && min <= max; min++)
1667 CHadd(p, cs, min);
1668 newranges = reallocarray(cs->ranges, cs->nranges + 1,
1669 sizeof(*cs->ranges));
1670 if (newranges == NULL) {
1671 SETERROR(REG_ESPACE);
1672 return;
1673 }
1674 cs->ranges = newranges;
1675 cs->ranges[cs->nranges].min = min;
1676 cs->ranges[cs->nranges].max = max;
1677 cs->nranges++;
1678 }
1679
1680 /*
1681 - CHaddtype - add all characters of a certain type to a character set.
1682 */
1683 static void
1684 CHaddtype(struct parse *p, cset *cs, wctype_t wct)
1685 {
1686 wint_t i;
1687 wctype_t *newtypes;
1688
1689 for (i = 0; i < NC; i++)
1690 if (iswctype(i, wct))
1691 CHadd(p, cs, i);
1692 newtypes = reallocarray(cs->types, cs->ntypes + 1,
1693 sizeof(*cs->types));
1694 if (newtypes == NULL) {
1695 SETERROR(REG_ESPACE);
1696 return;
1697 }
1698 cs->types = newtypes;
1699 cs->types[cs->ntypes++] = wct;
1700 }
1701
1702 /*
1703 - dupl - emit a duplicate of a bunch of sops
1704 == static sopno dupl(struct parse *p, sopno start, sopno finish);
1705 */
1706 static sopno /* start of duplicate */
1707 dupl(struct parse *p,
1708 sopno start, /* from here */
1709 sopno finish) /* to this less one */
1710 {
1711 sopno ret = HERE();
1712 sopno len = finish - start;
1713
1714 assert(finish >= start);
1715 if (len == 0)
1716 return(ret);
1717 if (!enlarge(p, p->ssize + len)) /* this many unexpected additions */
1718 return(ret);
1719 (void) memcpy((char *)(p->strip + p->slen),
1720 (char *)(p->strip + start), (size_t)len*sizeof(sop));
1721 p->slen += len;
1722 return(ret);
1723 }
1724
1725 /*
1726 - doemit - emit a strip operator
1727 == static void doemit(struct parse *p, sop op, size_t opnd);
1728 *
1729 * It might seem better to implement this as a macro with a function as
1730 * hard-case backup, but it's just too big and messy unless there are
1731 * some changes to the data structures. Maybe later.
1732 */
1733 static void
1734 doemit(struct parse *p, sop op, size_t opnd)
1735 {
1736 /* avoid making error situations worse */
1737 if (p->error != 0)
1738 return;
1739
1740 /* deal with oversize operands ("can't happen", more or less) */
1741 assert(opnd < 1<<OPSHIFT);
1742
1743 /* deal with undersized strip */
1744 if (p->slen >= p->ssize)
1745 if (!enlarge(p, (p->ssize+1) / 2 * 3)) /* +50% */
1746 return;
1747
1748 /* finally, it's all reduced to the easy case */
1749 p->strip[p->slen++] = SOP(op, opnd);
1750 }
1751
1752 /*
1753 - doinsert - insert a sop into the strip
1754 == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
1755 */
1756 static void
1757 doinsert(struct parse *p, sop op, size_t opnd, sopno pos)
1758 {
1759 sopno sn;
1760 sop s;
1761 int i;
1762
1763 /* avoid making error situations worse */
1764 if (p->error != 0)
1765 return;
1766
1767 sn = HERE();
1768 EMIT(op, opnd); /* do checks, ensure space */
1769 assert(HERE() == sn+1);
1770 s = p->strip[sn];
1771
1772 /* adjust paren pointers */
1773 assert(pos > 0);
1774 for (i = 1; i < NPAREN; i++) {
1775 if (p->pbegin[i] >= pos) {
1776 p->pbegin[i]++;
1777 }
1778 if (p->pend[i] >= pos) {
1779 p->pend[i]++;
1780 }
1781 }
1782
1783 memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
1784 (HERE()-pos-1)*sizeof(sop));
1785 p->strip[pos] = s;
1786 }
1787
1788 /*
1789 - dofwd - complete a forward reference
1790 == static void dofwd(struct parse *p, sopno pos, sop value);
1791 */
1792 static void
1793 dofwd(struct parse *p, sopno pos, sop value)
1794 {
1795 /* avoid making error situations worse */
1796 if (p->error != 0)
1797 return;
1798
1799 assert(value < 1<<OPSHIFT);
1800 p->strip[pos] = OP(p->strip[pos]) | value;
1801 }
1802
1803 /*
1804 - enlarge - enlarge the strip
1805 == static int enlarge(struct parse *p, sopno size);
1806 */
1807 static int
1808 enlarge(struct parse *p, sopno size)
1809 {
1810 sop *sp;
1811
1812 if (p->ssize >= size)
1813 return 1;
1814
1815 sp = reallocarray(p->strip, size, sizeof(sop));
1816 if (sp == NULL) {
1817 SETERROR(REG_ESPACE);
1818 return 0;
1819 }
1820 p->strip = sp;
1821 p->ssize = size;
1822 return 1;
1823 }
1824
1825 /*
1826 - stripsnug - compact the strip
1827 == static void stripsnug(struct parse *p, struct re_guts *g);
1828 */
1829 static void
1830 stripsnug(struct parse *p, struct re_guts *g)
1831 {
1832 g->nstates = p->slen;
1833 g->strip = reallocarray((char *)p->strip, p->slen, sizeof(sop));
1834 if (g->strip == NULL) {
1835 SETERROR(REG_ESPACE);
1836 g->strip = p->strip;
1837 }
1838 }
1839
1840 /*
1841 - findmust - fill in must and mlen with longest mandatory literal string
1842 == static void findmust(struct parse *p, struct re_guts *g);
1843 *
1844 * This algorithm could do fancy things like analyzing the operands of |
1845 * for common subsequences. Someday. This code is simple and finds most
1846 * of the interesting cases.
1847 *
1848 * Note that must and mlen got initialized during setup.
1849 */
1850 static void
1851 findmust(struct parse *p, struct re_guts *g)
1852 {
1853 sop *scan;
1854 sop *start = NULL;
1855 sop *newstart = NULL;
1856 sopno newlen;
1857 sop s;
1858 char *cp;
1859 int offset;
1860 char buf[MB_LEN_MAX];
1861 size_t clen;
1862 mbstate_t mbs;
1863
1864 /* avoid making error situations worse */
1865 if (p->error != 0)
1866 return;
1867
1868 /*
1869 * It's not generally safe to do a ``char'' substring search on
1870 * multibyte character strings, but it's safe for at least
1871 * UTF-8 (see RFC 3629).
1872 */
1873 if (MB_CUR_MAX > 1 &&
1874 strcmp(__current_locale_charset (), "UTF-8") != 0)
1875 return;
1876
1877 /* find the longest OCHAR sequence in strip */
1878 newlen = 0;
1879 offset = 0;
1880 g->moffset = 0;
1881 scan = g->strip + 1;
1882 do {
1883 s = *scan++;
1884 switch (OP(s)) {
1885 case OCHAR: /* sequence member */
1886 if (newlen == 0) { /* new sequence */
1887 memset(&mbs, 0, sizeof(mbs));
1888 newstart = scan - 1;
1889 }
1890 clen = wirtomb(buf, OPND(s), &mbs);
1891 if (clen == (size_t)-1)
1892 goto toohard;
1893 newlen += clen;
1894 break;
1895 case OPLUS_: /* things that don't break one */
1896 case OLPAREN:
1897 case ORPAREN:
1898 break;
1899 case OQUEST_: /* things that must be skipped */
1900 case OCH_:
1901 offset = altoffset(scan, offset);
1902 scan--;
1903 do {
1904 scan += OPND(s);
1905 s = *scan;
1906 /* assert() interferes w debug printouts */
1907 if (OP(s) != (sop)O_QUEST &&
1908 OP(s) != (sop)O_CH && OP(s) != (sop)OOR2) {
1909 g->iflags |= BAD;
1910 return;
1911 }
1912 } while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH);
1913 fallthrough;
1914 case OBOW: /* things that break a sequence */
1915 case OEOW:
1916 case OBOL:
1917 case OEOL:
1918 case OBOS:
1919 case OEOS:
1920 case OWBND:
1921 case ONWBND:
1922 case O_QUEST:
1923 case O_CH:
1924 case OEND:
1925 if (newlen > (sopno)g->mlen) { /* ends one */
1926 start = newstart;
1927 g->mlen = newlen;
1928 if (offset > -1) {
1929 g->moffset += offset;
1930 offset = newlen;
1931 } else
1932 g->moffset = offset;
1933 } else {
1934 if (offset > -1)
1935 offset += newlen;
1936 }
1937 newlen = 0;
1938 break;
1939 case OANY:
1940 if (newlen > (sopno)g->mlen) { /* ends one */
1941 start = newstart;
1942 g->mlen = newlen;
1943 if (offset > -1) {
1944 g->moffset += offset;
1945 offset = newlen;
1946 } else
1947 g->moffset = offset;
1948 } else {
1949 if (offset > -1)
1950 offset += newlen;
1951 }
1952 if (offset > -1)
1953 offset++;
1954 newlen = 0;
1955 break;
1956 case OANYOF: /* may or may not invalidate offset */
1957 /* First, everything as OANY */
1958 if (newlen > (sopno)g->mlen) { /* ends one */
1959 start = newstart;
1960 g->mlen = newlen;
1961 if (offset > -1) {
1962 g->moffset += offset;
1963 offset = newlen;
1964 } else
1965 g->moffset = offset;
1966 } else {
1967 if (offset > -1)
1968 offset += newlen;
1969 }
1970 if (offset > -1)
1971 offset++;
1972 newlen = 0;
1973 break;
1974 toohard:
1975 default:
1976 /* Anything here makes it impossible or too hard
1977 * to calculate the offset -- so we give up;
1978 * save the last known good offset, in case the
1979 * must sequence doesn't occur later.
1980 */
1981 if (newlen > (sopno)g->mlen) { /* ends one */
1982 start = newstart;
1983 g->mlen = newlen;
1984 if (offset > -1)
1985 g->moffset += offset;
1986 else
1987 g->moffset = offset;
1988 }
1989 offset = -1;
1990 newlen = 0;
1991 break;
1992 }
1993 } while (OP(s) != OEND);
1994
1995 if (g->mlen == 0) { /* there isn't one */
1996 g->moffset = -1;
1997 return;
1998 }
1999
2000 /* turn it into a character string */
2001 g->must = malloc((size_t)g->mlen + 1);
2002 if (g->must == NULL) { /* argh; just forget it */
2003 g->mlen = 0;
2004 g->moffset = -1;
2005 return;
2006 }
2007 cp = g->must;
2008 scan = start;
2009 memset(&mbs, 0, sizeof(mbs));
2010 while (cp < g->must + g->mlen) {
2011 while (OP(s = *scan++) != OCHAR)
2012 continue;
2013 clen = wirtomb(cp, OPND(s), &mbs);
2014 assert(clen != (size_t)-1);
2015 cp += clen;
2016 }
2017 assert(cp == g->must + g->mlen);
2018 *cp++ = '\0'; /* just on general principles */
2019 }
2020
2021 /*
2022 - altoffset - choose biggest offset among multiple choices
2023 == static int altoffset(sop *scan, int offset);
2024 *
2025 * Compute, recursively if necessary, the largest offset among multiple
2026 * re paths.
2027 */
2028 static int
2029 altoffset(sop *scan, int offset)
2030 {
2031 int largest;
2032 int try;
2033 sop s;
2034
2035 /* If we gave up already on offsets, return */
2036 if (offset == -1)
2037 return -1;
2038
2039 largest = 0;
2040 try = 0;
2041 s = *scan++;
2042 while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH) {
2043 switch (OP(s)) {
2044 case OOR1:
2045 if (try > largest)
2046 largest = try;
2047 try = 0;
2048 break;
2049 case OQUEST_:
2050 case OCH_:
2051 try = altoffset(scan, try);
2052 if (try == -1)
2053 return -1;
2054 scan--;
2055 do {
2056 scan += OPND(s);
2057 s = *scan;
2058 if (OP(s) != (sop)O_QUEST &&
2059 OP(s) != (sop)O_CH && OP(s) != (sop)OOR2)
2060 return -1;
2061 } while (OP(s) != (sop)O_QUEST && OP(s) != (sop)O_CH);
2062 /* We must skip to the next position, or we'll
2063 * leave altoffset() too early.
2064 */
2065 scan++;
2066 break;
2067 case OANYOF:
2068 case OCHAR:
2069 case OANY:
2070 try++;
2071 case OBOW:
2072 case OEOW:
2073 case OWBND:
2074 case ONWBND:
2075 case OLPAREN:
2076 case ORPAREN:
2077 case OOR2:
2078 break;
2079 default:
2080 try = -1;
2081 break;
2082 }
2083 if (try == -1)
2084 return -1;
2085 s = *scan++;
2086 }
2087
2088 if (try > largest)
2089 largest = try;
2090
2091 return largest+offset;
2092 }
2093
2094 /*
2095 - computejumps - compute char jumps for BM scan
2096 == static void computejumps(struct parse *p, struct re_guts *g);
2097 *
2098 * This algorithm assumes g->must exists and is has size greater than
2099 * zero. It's based on the algorithm found on Computer Algorithms by
2100 * Sara Baase.
2101 *
2102 * A char jump is the number of characters one needs to jump based on
2103 * the value of the character from the text that was mismatched.
2104 */
2105 static void
2106 computejumps(struct parse *p, struct re_guts *g)
2107 {
2108 int ch;
2109 int mindex;
2110
2111 /* Avoid making errors worse */
2112 if (p->error != 0)
2113 return;
2114
2115 g->charjump = (int *)malloc((NC_MAX + 1) * sizeof(int));
2116 if (g->charjump == NULL) /* Not a fatal error */
2117 return;
2118 /* Adjust for signed chars, if necessary */
2119 g->charjump = &g->charjump[-(CHAR_MIN)];
2120
2121 /* If the character does not exist in the pattern, the jump
2122 * is equal to the number of characters in the pattern.
2123 */
2124 for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++)
2125 g->charjump[ch] = g->mlen;
2126
2127 /* If the character does exist, compute the jump that would
2128 * take us to the last character in the pattern equal to it
2129 * (notice that we match right to left, so that last character
2130 * is the first one that would be matched).
2131 */
2132 for (mindex = 0; mindex < g->mlen; mindex++)
2133 g->charjump[(int)g->must[mindex]] = g->mlen - mindex - 1;
2134 }
2135
2136 /*
2137 - computematchjumps - compute match jumps for BM scan
2138 == static void computematchjumps(struct parse *p, struct re_guts *g);
2139 *
2140 * This algorithm assumes g->must exists and is has size greater than
2141 * zero. It's based on the algorithm found on Computer Algorithms by
2142 * Sara Baase.
2143 *
2144 * A match jump is the number of characters one needs to advance based
2145 * on the already-matched suffix.
2146 * Notice that all values here are minus (g->mlen-1), because of the way
2147 * the search algorithm works.
2148 */
2149 static void
2150 computematchjumps(struct parse *p, struct re_guts *g)
2151 {
2152 int mindex; /* General "must" iterator */
2153 int suffix; /* Keeps track of matching suffix */
2154 int ssuffix; /* Keeps track of suffixes' suffix */
2155 int* pmatches; /* pmatches[k] points to the next i
2156 * such that i+1...mlen is a substring
2157 * of k+1...k+mlen-i-1
2158 */
2159
2160 /* Avoid making errors worse */
2161 if (p->error != 0)
2162 return;
2163
2164 pmatches = (int*) malloc(g->mlen * sizeof(int));
2165 if (pmatches == NULL) {
2166 g->matchjump = NULL;
2167 return;
2168 }
2169
2170 g->matchjump = (int*) malloc(g->mlen * sizeof(int));
2171 if (g->matchjump == NULL) { /* Not a fatal error */
2172 free(pmatches);
2173 return;
2174 }
2175
2176 /* Set maximum possible jump for each character in the pattern */
2177 for (mindex = 0; mindex < g->mlen; mindex++)
2178 g->matchjump[mindex] = 2*g->mlen - mindex - 1;
2179
2180 /* Compute pmatches[] */
2181 for (mindex = g->mlen - 1, suffix = g->mlen; mindex >= 0;
2182 mindex--, suffix--) {
2183 pmatches[mindex] = suffix;
2184
2185 /* If a mismatch is found, interrupting the substring,
2186 * compute the matchjump for that position. If no
2187 * mismatch is found, then a text substring mismatched
2188 * against the suffix will also mismatch against the
2189 * substring.
2190 */
2191 while (suffix < g->mlen
2192 && g->must[mindex] != g->must[suffix]) {
2193 g->matchjump[suffix] = MIN(g->matchjump[suffix],
2194 g->mlen - mindex - 1);
2195 suffix = pmatches[suffix];
2196 }
2197 }
2198
2199 /* Compute the matchjump up to the last substring found to jump
2200 * to the beginning of the largest must pattern prefix matching
2201 * it's own suffix.
2202 */
2203 for (mindex = 0; mindex <= suffix; mindex++)
2204 g->matchjump[mindex] = MIN(g->matchjump[mindex],
2205 g->mlen + suffix - mindex);
2206
2207 ssuffix = pmatches[suffix];
2208 while (suffix < g->mlen) {
2209 while (suffix <= ssuffix && suffix < g->mlen) {
2210 g->matchjump[suffix] = MIN(g->matchjump[suffix],
2211 g->mlen + ssuffix - suffix);
2212 suffix++;
2213 }
2214 if (suffix < g->mlen)
2215 ssuffix = pmatches[ssuffix];
2216 }
2217
2218 free(pmatches);
2219 }
2220
2221 /*
2222 - pluscount - count + nesting
2223 == static sopno pluscount(struct parse *p, struct re_guts *g);
2224 */
2225 static sopno /* nesting depth */
2226 pluscount(struct parse *p, struct re_guts *g)
2227 {
2228 sop *scan;
2229 sop s;
2230 sopno plusnest = 0;
2231 sopno maxnest = 0;
2232
2233 if (p->error != 0)
2234 return(0); /* there may not be an OEND */
2235
2236 scan = g->strip + 1;
2237 do {
2238 s = *scan++;
2239 switch (OP(s)) {
2240 case OPLUS_:
2241 plusnest++;
2242 break;
2243 case O_PLUS:
2244 if (plusnest > maxnest)
2245 maxnest = plusnest;
2246 plusnest--;
2247 break;
2248 }
2249 } while (OP(s) != OEND);
2250 if (plusnest != 0)
2251 g->iflags |= BAD;
2252 return(maxnest);
2253 }