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