?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Parallelize in_ifaddrhead operation
[dragonfly.git] / lib / libc / regex / regcomp.c
blob54c313476cdfdc0564413b6c6fe4d07286aa5939
1 /*-
2 * Copyright (c) 1992, 1993, 1994 Henry Spencer.
3 * Copyright (c) 1992, 1993, 1994
4 * The Regents of the University of California. All rights reserved.
5 *
6 * This code is derived from software contributed to Berkeley by
7 * Henry Spencer.
8 *
9 * Redistribution and use in source and binary forms, with or without
10 * modification, are permitted provided that the following conditions
11 * are met:
12 * 1. Redistributions of source code must retain the above copyright
13 * notice, this list of conditions and the following disclaimer.
14 * 2. Redistributions in binary form must reproduce the above copyright
15 * notice, this list of conditions and the following disclaimer in the
16 * documentation and/or other materials provided with the distribution.
17 * 3. All advertising materials mentioning features or use of this software
18 * must display the following acknowledgement:
19 * This product includes software developed by the University of
20 * California, Berkeley and its contributors.
21 * 4. Neither the name of the University nor the names of its contributors
22 * may be used to endorse or promote products derived from this software
23 * without specific prior written permission.
24 *
25 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35 * SUCH DAMAGE.
36 *
37 * @(#)regcomp.c 8.5 (Berkeley) 3/20/94
38 *
39 * $FreeBSD: src/lib/libc/regex/regcomp.c,v 1.13.2.2 2002/03/20 13:13:15 dcs Exp $
40 * $DragonFly: src/lib/libc/regex/regcomp.c,v 1.7 2005/11/20 09:18:37 swildner Exp $
41 *
42 * @(#)regcomp.c 8.5 (Berkeley) 3/20/94
43 */
44
45 #include <sys/types.h>
46 #include <stdio.h>
47 #include <string.h>
48 #include <ctype.h>
49 #include <limits.h>
50 #include <stdlib.h>
51 #include <regex.h>
52
53 #include "collate.h"
54
55 #include "utils.h"
56 #include "regex2.h"
57
58 #include "cclass.h"
59 #include "cname.h"
60
61 /*
62 * parse structure, passed up and down to avoid global variables and
63 * other clumsinesses
64 */
65 struct parse {
66 char *next; /* next character in RE */
67 char *end; /* end of string (-> NUL normally) */
68 int error; /* has an error been seen? */
69 sop *strip; /* malloced strip */
70 sopno ssize; /* malloced strip size (allocated) */
71 sopno slen; /* malloced strip length (used) */
72 int ncsalloc; /* number of csets allocated */
73 struct re_guts *g;
74 # define NPAREN 10 /* we need to remember () 1-9 for back refs */
75 sopno pbegin[NPAREN]; /* -> ( ([0] unused) */
76 sopno pend[NPAREN]; /* -> ) ([0] unused) */
77 };
78
79 /* ========= begin header generated by ./mkh ========= */
80 #ifdef __cplusplus
81 extern "C" {
82 #endif
83
84 /* === regcomp.c === */
85 static void p_ere(struct parse *p, int stop);
86 static void p_ere_exp(struct parse *p);
87 static void p_str(struct parse *p);
88 static void p_bre(struct parse *p, int end1, int end2);
89 static int p_simp_re(struct parse *p, int starordinary);
90 static int p_count(struct parse *p);
91 static void p_bracket(struct parse *p);
92 static void p_b_term(struct parse *p, cset *cs);
93 static void p_b_cclass(struct parse *p, cset *cs);
94 static void p_b_eclass(struct parse *p, cset *cs);
95 static char p_b_symbol(struct parse *p);
96 static char p_b_coll_elem(struct parse *p, int endc);
97 static char othercase(int ch);
98 static void bothcases(struct parse *p, int ch);
99 static void ordinary(struct parse *p, int ch);
100 static void nonnewline(struct parse *p);
101 static void repeat(struct parse *p, sopno start, int from, int to);
102 static int seterr(struct parse *p, int e);
103 static cset *allocset(struct parse *p);
104 static void freeset(struct parse *p, cset *cs);
105 static int freezeset(struct parse *p, cset *cs);
106 static int firstch(struct parse *p, cset *cs);
107 static int nch(struct parse *p, cset *cs);
108 static void mcadd(struct parse *p, cset *cs, char *cp);
109 #if used
110 static void mcsub(cset *cs, char *cp);
111 static int mcin(cset *cs, char *cp);
112 static char *mcfind(cset *cs, char *cp);
113 #endif
114 static void mcinvert(struct parse *p, cset *cs);
115 static void mccase(struct parse *p, cset *cs);
116 static int isinsets(struct re_guts *g, int c);
117 static int samesets(struct re_guts *g, int c1, int c2);
118 static void categorize(struct parse *p, struct re_guts *g);
119 static sopno dupl(struct parse *p, sopno start, sopno finish);
120 static void doemit(struct parse *p, sop op, size_t opnd);
121 static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
122 static void dofwd(struct parse *p, sopno pos, sop value);
123 static void enlarge(struct parse *p, sopno size);
124 static void stripsnug(struct parse *p, struct re_guts *g);
125 static void findmust(struct parse *p, struct re_guts *g);
126 static int altoffset(sop *scan, int offset, int mccs);
127 static void computejumps(struct parse *p, struct re_guts *g);
128 static void computematchjumps(struct parse *p, struct re_guts *g);
129 static sopno pluscount(struct parse *p, struct re_guts *g);
130
131 #ifdef __cplusplus
132 }
133 #endif
134 /* ========= end header generated by ./mkh ========= */
135
136 static char nuls[10]; /* place to point scanner in event of error */
137
138 /*
139 * macros for use with parse structure
140 * BEWARE: these know that the parse structure is named `p' !!!
141 */
142 #define PEEK() (*p->next)
143 #define PEEK2() (*(p->next+1))
144 #define MORE() (p->next < p->end)
145 #define MORE2() (p->next+1 < p->end)
146 #define SEE(c) (MORE() && PEEK() == (c))
147 #define SEETWO(a, b) (MORE() && MORE2() && PEEK() == (a) && PEEK2() == (b))
148 #define EAT(c) ((SEE(c)) ? (NEXT(), 1) : 0)
149 #define EATTWO(a, b) ((SEETWO(a, b)) ? (NEXT2(), 1) : 0)
150 #define NEXT() (p->next++)
151 #define NEXT2() (p->next += 2)
152 #define NEXTn(n) (p->next += (n))
153 #define GETNEXT() (*p->next++)
154 #define SETERROR(e) seterr(p, (e))
155 #define REQUIRE(co, e) ((co) || SETERROR(e))
156 #define MUSTSEE(c, e) (REQUIRE(MORE() && PEEK() == (c), e))
157 #define MUSTEAT(c, e) (REQUIRE(MORE() && GETNEXT() == (c), e))
158 #define MUSTNOTSEE(c, e) (REQUIRE(!MORE() || PEEK() != (c), e))
159 #define EMIT(op, sopnd) doemit(p, (sop)(op), (size_t)(sopnd))
160 #define INSERT(op, pos) doinsert(p, (sop)(op), HERE()-(pos)+1, pos)
161 #define AHEAD(pos) dofwd(p, pos, HERE()-(pos))
162 #define ASTERN(sop, pos) EMIT(sop, HERE()-pos)
163 #define HERE() (p->slen)
164 #define THERE() (p->slen - 1)
165 #define THERETHERE() (p->slen - 2)
166 #define DROP(n) (p->slen -= (n))
167
168 #ifndef NDEBUG
169 static int never = 0; /* for use in asserts; shuts lint up */
170 #else
171 #define never 0 /* some <assert.h>s have bugs too */
172 #endif
173
174 /* Macro used by computejump()/computematchjump() */
175 #define MIN(a,b) ((a)<(b)?(a):(b))
176
177 /*
178 - regcomp - interface for parser and compilation
179 = extern int regcomp(regex_t *, const char *, int);
180 = #define REG_BASIC 0000
181 = #define REG_EXTENDED 0001
182 = #define REG_ICASE 0002
183 = #define REG_NOSUB 0004
184 = #define REG_NEWLINE 0010
185 = #define REG_NOSPEC 0020
186 = #define REG_PEND 0040
187 = #define REG_DUMP 0200
188 */
189 int /* 0 success, otherwise REG_something */
190 regcomp(regex_t *preg, const char *pattern, int cflags)
191 {
192 struct parse pa;
193 struct re_guts *g;
194 struct parse *p = &pa;
195 int i;
196 size_t len;
197 #ifdef REDEBUG
198 # define GOODFLAGS(f) (f)
199 #else
200 # define GOODFLAGS(f) ((f)&~REG_DUMP)
201 #endif
202
203 cflags = GOODFLAGS(cflags);
204 if ((cflags&REG_EXTENDED) && (cflags&REG_NOSPEC))
205 return(REG_INVARG);
206
207 if (cflags&REG_PEND) {
208 if (preg->re_endp < pattern)
209 return(REG_INVARG);
210 len = preg->re_endp - pattern;
211 } else
212 len = strlen((char *)pattern);
213
214 /* do the mallocs early so failure handling is easy */
215 g = (struct re_guts *)malloc(sizeof(struct re_guts) +
216 (NC-1)*sizeof(cat_t));
217 if (g == NULL)
218 return(REG_ESPACE);
219 p->ssize = len/(size_t)2*(size_t)3 + (size_t)1; /* ugh */
220 p->strip = (sop *)malloc(p->ssize * sizeof(sop));
221 p->slen = 0;
222 if (p->strip == NULL) {
223 free((char *)g);
224 return(REG_ESPACE);
225 }
226
227 /* set things up */
228 p->g = g;
229 p->next = (char *)pattern; /* convenience; we do not modify it */
230 p->end = p->next + len;
231 p->error = 0;
232 p->ncsalloc = 0;
233 for (i = 0; i < NPAREN; i++) {
234 p->pbegin[i] = 0;
235 p->pend[i] = 0;
236 }
237 g->csetsize = NC;
238 g->sets = NULL;
239 g->setbits = NULL;
240 g->ncsets = 0;
241 g->cflags = cflags;
242 g->iflags = 0;
243 g->nbol = 0;
244 g->neol = 0;
245 g->must = NULL;
246 g->moffset = -1;
247 g->charjump = NULL;
248 g->matchjump = NULL;
249 g->mlen = 0;
250 g->nsub = 0;
251 g->ncategories = 1; /* category 0 is "everything else" */
252 g->categories = &g->catspace[-(CHAR_MIN)];
253 memset((char *)g->catspace, 0, NC*sizeof(cat_t));
254 g->backrefs = 0;
255
256 /* do it */
257 EMIT(OEND, 0);
258 g->firststate = THERE();
259 if (cflags&REG_EXTENDED)
260 p_ere(p, OUT);
261 else if (cflags&REG_NOSPEC)
262 p_str(p);
263 else
264 p_bre(p, OUT, OUT);
265 EMIT(OEND, 0);
266 g->laststate = THERE();
267
268 /* tidy up loose ends and fill things in */
269 categorize(p, g);
270 stripsnug(p, g);
271 findmust(p, g);
272 /* only use Boyer-Moore algorithm if the pattern is bigger
273 * than three characters
274 */
275 if(g->mlen > 3) {
276 computejumps(p, g);
277 computematchjumps(p, g);
278 if(g->matchjump == NULL && g->charjump != NULL) {
279 free(g->charjump);
280 g->charjump = NULL;
281 }
282 }
283 g->nplus = pluscount(p, g);
284 g->magic = MAGIC2;
285 preg->re_nsub = g->nsub;
286 preg->re_g = g;
287 preg->re_magic = MAGIC1;
288 #ifndef REDEBUG
289 /* not debugging, so can't rely on the assert() in regexec() */
290 if (g->iflags&BAD)
291 SETERROR(REG_ASSERT);
292 #endif
293
294 /* win or lose, we're done */
295 if (p->error != 0) /* lose */
296 regfree(preg);
297 return(p->error);
298 }
299
300 /*
301 - p_ere - ERE parser top level, concatenation and alternation
302 == static void p_ere(struct parse *p, int stop);
303 */
304 static void
305 p_ere(struct parse *p,
306 int stop) /* character this ERE should end at */
307 {
308 char c;
309 sopno prevback;
310 sopno prevfwd;
311 sopno conc;
312 int first = 1; /* is this the first alternative? */
313
314 prevback = 0;
315 prevfwd = 0;
316
317 for (;;) {
318 /* do a bunch of concatenated expressions */
319 conc = HERE();
320 while (MORE() && (c = PEEK()) != '|' && c != stop)
321 p_ere_exp(p);
322 REQUIRE(HERE() != conc, REG_EMPTY); /* require nonempty */
323
324 if (!EAT('|'))
325 break; /* NOTE BREAK OUT */
326
327 if (first) {
328 INSERT(OCH_, conc); /* offset is wrong */
329 prevfwd = conc;
330 prevback = conc;
331 first = 0;
332 }
333 ASTERN(OOR1, prevback);
334 prevback = THERE();
335 AHEAD(prevfwd); /* fix previous offset */
336 prevfwd = HERE();
337 EMIT(OOR2, 0); /* offset is very wrong */
338 }
339
340 if (!first) { /* tail-end fixups */
341 AHEAD(prevfwd);
342 ASTERN(O_CH, prevback);
343 }
344
345 assert(!MORE() || SEE(stop));
346 }
347
348 /*
349 - p_ere_exp - parse one subERE, an atom possibly followed by a repetition op
350 == static void p_ere_exp(struct parse *p);
351 */
352 static void
353 p_ere_exp(struct parse *p)
354 {
355 char c;
356 sopno pos;
357 int count;
358 int count2;
359 sopno subno;
360 int wascaret = 0;
361
362 assert(MORE()); /* caller should have ensured this */
363 c = GETNEXT();
364
365 pos = HERE();
366 switch (c) {
367 case '(':
368 REQUIRE(MORE(), REG_EPAREN);
369 p->g->nsub++;
370 subno = p->g->nsub;
371 if (subno < NPAREN)
372 p->pbegin[subno] = HERE();
373 EMIT(OLPAREN, subno);
374 if (!SEE(')'))
375 p_ere(p, ')');
376 if (subno < NPAREN) {
377 p->pend[subno] = HERE();
378 assert(p->pend[subno] != 0);
379 }
380 EMIT(ORPAREN, subno);
381 MUSTEAT(')', REG_EPAREN);
382 break;
383 #ifndef POSIX_MISTAKE
384 case ')': /* happens only if no current unmatched ( */
385 /*
386 * You may ask, why the ifndef? Because I didn't notice
387 * this until slightly too late for 1003.2, and none of the
388 * other 1003.2 regular-expression reviewers noticed it at
389 * all. So an unmatched ) is legal POSIX, at least until
390 * we can get it fixed.
391 */
392 SETERROR(REG_EPAREN);
393 break;
394 #endif
395 case '^':
396 EMIT(OBOL, 0);
397 p->g->iflags |= USEBOL;
398 p->g->nbol++;
399 wascaret = 1;
400 break;
401 case '$':
402 EMIT(OEOL, 0);
403 p->g->iflags |= USEEOL;
404 p->g->neol++;
405 break;
406 case '|':
407 SETERROR(REG_EMPTY);
408 break;
409 case '*':
410 case '+':
411 case '?':
412 SETERROR(REG_BADRPT);
413 break;
414 case '.':
415 if (p->g->cflags&REG_NEWLINE)
416 nonnewline(p);
417 else
418 EMIT(OANY, 0);
419 break;
420 case '[':
421 p_bracket(p);
422 break;
423 case '\\':
424 REQUIRE(MORE(), REG_EESCAPE);
425 c = GETNEXT();
426 ordinary(p, c);
427 break;
428 case '{': /* okay as ordinary except if digit follows */
429 REQUIRE(!MORE() || !isdigit((uch)PEEK()), REG_BADRPT);
430 /* FALLTHROUGH */
431 default:
432 ordinary(p, c);
433 break;
434 }
435
436 if (!MORE())
437 return;
438 c = PEEK();
439 /* we call { a repetition if followed by a digit */
440 if (!( c == '*' || c == '+' || c == '?' ||
441 (c == '{' && MORE2() && isdigit((uch)PEEK2())) ))
442 return; /* no repetition, we're done */
443 NEXT();
444
445 REQUIRE(!wascaret, REG_BADRPT);
446 switch (c) {
447 case '*': /* implemented as +? */
448 /* this case does not require the (y|) trick, noKLUDGE */
449 INSERT(OPLUS_, pos);
450 ASTERN(O_PLUS, pos);
451 INSERT(OQUEST_, pos);
452 ASTERN(O_QUEST, pos);
453 break;
454 case '+':
455 INSERT(OPLUS_, pos);
456 ASTERN(O_PLUS, pos);
457 break;
458 case '?':
459 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
460 INSERT(OCH_, pos); /* offset slightly wrong */
461 ASTERN(OOR1, pos); /* this one's right */
462 AHEAD(pos); /* fix the OCH_ */
463 EMIT(OOR2, 0); /* offset very wrong... */
464 AHEAD(THERE()); /* ...so fix it */
465 ASTERN(O_CH, THERETHERE());
466 break;
467 case '{':
468 count = p_count(p);
469 if (EAT(',')) {
470 if (isdigit((uch)PEEK())) {
471 count2 = p_count(p);
472 REQUIRE(count <= count2, REG_BADBR);
473 } else /* single number with comma */
474 count2 = INFINITY;
475 } else /* just a single number */
476 count2 = count;
477 repeat(p, pos, count, count2);
478 if (!EAT('}')) { /* error heuristics */
479 while (MORE() && PEEK() != '}')
480 NEXT();
481 REQUIRE(MORE(), REG_EBRACE);
482 SETERROR(REG_BADBR);
483 }
484 break;
485 }
486
487 if (!MORE())
488 return;
489 c = PEEK();
490 if (!( c == '*' || c == '+' || c == '?' ||
491 (c == '{' && MORE2() && isdigit((uch)PEEK2())) ) )
492 return;
493 SETERROR(REG_BADRPT);
494 }
495
496 /*
497 - p_str - string (no metacharacters) "parser"
498 == static void p_str(struct parse *p);
499 */
500 static void
501 p_str(struct parse *p)
502 {
503 REQUIRE(MORE(), REG_EMPTY);
504 while (MORE())
505 ordinary(p, GETNEXT());
506 }
507
508 /*
509 - p_bre - BRE parser top level, anchoring and concatenation
510 == static void p_bre(struct parse *p, int end1, \
511 == int end2);
512 * Giving end1 as OUT essentially eliminates the end1/end2 check.
513 *
514 * This implementation is a bit of a kludge, in that a trailing $ is first
515 * taken as an ordinary character and then revised to be an anchor. The
516 * only undesirable side effect is that '$' gets included as a character
517 * category in such cases. This is fairly harmless; not worth fixing.
518 * The amount of lookahead needed to avoid this kludge is excessive.
519 */
520 static void
521 p_bre(struct parse *p,
522 int end1, /* first terminating character */
523 int end2) /* second terminating character */
524 {
525 sopno start = HERE();
526 int first = 1; /* first subexpression? */
527 int wasdollar = 0;
528
529 if (EAT('^')) {
530 EMIT(OBOL, 0);
531 p->g->iflags |= USEBOL;
532 p->g->nbol++;
533 }
534 while (MORE() && !SEETWO(end1, end2)) {
535 wasdollar = p_simp_re(p, first);
536 first = 0;
537 }
538 if (wasdollar) { /* oops, that was a trailing anchor */
539 DROP(1);
540 EMIT(OEOL, 0);
541 p->g->iflags |= USEEOL;
542 p->g->neol++;
543 }
544
545 REQUIRE(HERE() != start, REG_EMPTY); /* require nonempty */
546 }
547
548 /*
549 - p_simp_re - parse a simple RE, an atom possibly followed by a repetition
550 == static int p_simp_re(struct parse *p, int starordinary);
551 */
552 static int /* was the simple RE an unbackslashed $? */
553 p_simp_re(struct parse *p,
554 int starordinary) /* is a leading * an ordinary character? */
555 {
556 int c;
557 int count;
558 int count2;
559 sopno pos;
560 int i;
561 sopno subno;
562 # define BACKSL (1<<CHAR_BIT)
563
564 pos = HERE(); /* repetion op, if any, covers from here */
565
566 assert(MORE()); /* caller should have ensured this */
567 c = GETNEXT();
568 if (c == '\\') {
569 REQUIRE(MORE(), REG_EESCAPE);
570 c = BACKSL | GETNEXT();
571 }
572 switch (c) {
573 case '.':
574 if (p->g->cflags&REG_NEWLINE)
575 nonnewline(p);
576 else
577 EMIT(OANY, 0);
578 break;
579 case '[':
580 p_bracket(p);
581 break;
582 case BACKSL|'{':
583 SETERROR(REG_BADRPT);
584 break;
585 case BACKSL|'(':
586 p->g->nsub++;
587 subno = p->g->nsub;
588 if (subno < NPAREN)
589 p->pbegin[subno] = HERE();
590 EMIT(OLPAREN, subno);
591 /* the MORE here is an error heuristic */
592 if (MORE() && !SEETWO('\\', ')'))
593 p_bre(p, '\\', ')');
594 if (subno < NPAREN) {
595 p->pend[subno] = HERE();
596 assert(p->pend[subno] != 0);
597 }
598 EMIT(ORPAREN, subno);
599 REQUIRE(EATTWO('\\', ')'), REG_EPAREN);
600 break;
601 case BACKSL|')': /* should not get here -- must be user */
602 case BACKSL|'}':
603 SETERROR(REG_EPAREN);
604 break;
605 case BACKSL|'1':
606 case BACKSL|'2':
607 case BACKSL|'3':
608 case BACKSL|'4':
609 case BACKSL|'5':
610 case BACKSL|'6':
611 case BACKSL|'7':
612 case BACKSL|'8':
613 case BACKSL|'9':
614 i = (c&~BACKSL) - '0';
615 assert(i < NPAREN);
616 if (p->pend[i] != 0) {
617 assert(i <= p->g->nsub);
618 EMIT(OBACK_, i);
619 assert(p->pbegin[i] != 0);
620 assert(OP(p->strip[p->pbegin[i]]) == OLPAREN);
621 assert(OP(p->strip[p->pend[i]]) == ORPAREN);
622 dupl(p, p->pbegin[i]+1, p->pend[i]);
623 EMIT(O_BACK, i);
624 } else
625 SETERROR(REG_ESUBREG);
626 p->g->backrefs = 1;
627 break;
628 case '*':
629 REQUIRE(starordinary, REG_BADRPT);
630 /* FALLTHROUGH */
631 default:
632 ordinary(p, (char)c);
633 break;
634 }
635
636 if (EAT('*')) { /* implemented as +? */
637 /* this case does not require the (y|) trick, noKLUDGE */
638 INSERT(OPLUS_, pos);
639 ASTERN(O_PLUS, pos);
640 INSERT(OQUEST_, pos);
641 ASTERN(O_QUEST, pos);
642 } else if (EATTWO('\\', '{')) {
643 count = p_count(p);
644 if (EAT(',')) {
645 if (MORE() && isdigit((uch)PEEK())) {
646 count2 = p_count(p);
647 REQUIRE(count <= count2, REG_BADBR);
648 } else /* single number with comma */
649 count2 = INFINITY;
650 } else /* just a single number */
651 count2 = count;
652 repeat(p, pos, count, count2);
653 if (!EATTWO('\\', '}')) { /* error heuristics */
654 while (MORE() && !SEETWO('\\', '}'))
655 NEXT();
656 REQUIRE(MORE(), REG_EBRACE);
657 SETERROR(REG_BADBR);
658 }
659 } else if (c == '$') /* $ (but not \$) ends it */
660 return(1);
661
662 return(0);
663 }
664
665 /*
666 - p_count - parse a repetition count
667 == static int p_count(struct parse *p);
668 */
669 static int /* the value */
670 p_count(struct parse *p)
671 {
672 int count = 0;
673 int ndigits = 0;
674
675 while (MORE() && isdigit((uch)PEEK()) && count <= DUPMAX) {
676 count = count*10 + (GETNEXT() - '0');
677 ndigits++;
678 }
679
680 REQUIRE(ndigits > 0 && count <= DUPMAX, REG_BADBR);
681 return(count);
682 }
683
684 /*
685 - p_bracket - parse a bracketed character list
686 == static void p_bracket(struct parse *p);
687 *
688 * Note a significant property of this code: if the allocset() did SETERROR,
689 * no set operations are done.
690 */
691 static void
692 p_bracket(struct parse *p)
693 {
694 cset *cs = allocset(p);
695 int invert = 0;
696
697 /* Dept of Truly Sickening Special-Case Kludges */
698 if (p->next + 5 < p->end && strncmp(p->next, "[:<:]]", 6) == 0) {
699 EMIT(OBOW, 0);
700 NEXTn(6);
701 return;
702 }
703 if (p->next + 5 < p->end && strncmp(p->next, "[:>:]]", 6) == 0) {
704 EMIT(OEOW, 0);
705 NEXTn(6);
706 return;
707 }
708
709 if (EAT('^'))
710 invert++; /* make note to invert set at end */
711 if (EAT(']'))
712 CHadd(cs, ']');
713 else if (EAT('-'))
714 CHadd(cs, '-');
715 while (MORE() && PEEK() != ']' && !SEETWO('-', ']'))
716 p_b_term(p, cs);
717 if (EAT('-'))
718 CHadd(cs, '-');
719 MUSTEAT(']', REG_EBRACK);
720
721 if (p->error != 0) /* don't mess things up further */
722 return;
723
724 if (p->g->cflags&REG_ICASE) {
725 int i;
726 int ci;
727
728 for (i = p->g->csetsize - 1; i >= 0; i--)
729 if (CHIN(cs, i) && isalpha(i)) {
730 ci = othercase(i);
731 if (ci != i)
732 CHadd(cs, ci);
733 }
734 if (cs->multis != NULL)
735 mccase(p, cs);
736 }
737 if (invert) {
738 int i;
739
740 for (i = p->g->csetsize - 1; i >= 0; i--)
741 if (CHIN(cs, i))
742 CHsub(cs, i);
743 else
744 CHadd(cs, i);
745 if (p->g->cflags&REG_NEWLINE)
746 CHsub(cs, '\n');
747 if (cs->multis != NULL)
748 mcinvert(p, cs);
749 }
750
751 assert(cs->multis == NULL); /* xxx */
752
753 if (nch(p, cs) == 1) { /* optimize singleton sets */
754 ordinary(p, firstch(p, cs));
755 freeset(p, cs);
756 } else
757 EMIT(OANYOF, freezeset(p, cs));
758 }
759
760 /*
761 - p_b_term - parse one term of a bracketed character list
762 == static void p_b_term(struct parse *p, cset *cs);
763 */
764 static void
765 p_b_term(struct parse *p, cset *cs)
766 {
767 char c;
768 char start, finish;
769 int i;
770
771 /* classify what we've got */
772 switch ((MORE()) ? PEEK() : '\0') {
773 case '[':
774 c = (MORE2()) ? PEEK2() : '\0';
775 break;
776 case '-':
777 SETERROR(REG_ERANGE);
778 return; /* NOTE RETURN */
779 break;
780 default:
781 c = '\0';
782 break;
783 }
784
785 switch (c) {
786 case ':': /* character class */
787 NEXT2();
788 REQUIRE(MORE(), REG_EBRACK);
789 c = PEEK();
790 REQUIRE(c != '-' && c != ']', REG_ECTYPE);
791 p_b_cclass(p, cs);
792 REQUIRE(MORE(), REG_EBRACK);
793 REQUIRE(EATTWO(':', ']'), REG_ECTYPE);
794 break;
795 case '=': /* equivalence class */
796 NEXT2();
797 REQUIRE(MORE(), REG_EBRACK);
798 c = PEEK();
799 REQUIRE(c != '-' && c != ']', REG_ECOLLATE);
800 p_b_eclass(p, cs);
801 REQUIRE(MORE(), REG_EBRACK);
802 REQUIRE(EATTWO('=', ']'), REG_ECOLLATE);
803 break;
804 default: /* symbol, ordinary character, or range */
805 /* xxx revision needed for multichar stuff */
806 start = p_b_symbol(p);
807 if (SEE('-') && MORE2() && PEEK2() != ']') {
808 /* range */
809 NEXT();
810 if (EAT('-'))
811 finish = '-';
812 else
813 finish = p_b_symbol(p);
814 } else
815 finish = start;
816 if (start == finish)
817 CHadd(cs, start);
818 else {
819 if (__collate_load_error) {
820 REQUIRE((uch)start <= (uch)finish, REG_ERANGE);
821 for (i = (uch)start; i <= (uch)finish; i++)
822 CHadd(cs, i);
823 } else {
824 REQUIRE(__collate_range_cmp(start, finish) <= 0, REG_ERANGE);
825 for (i = CHAR_MIN; i <= CHAR_MAX; i++) {
826 if ( __collate_range_cmp(start, i) <= 0
827 && __collate_range_cmp(i, finish) <= 0
828 )
829 CHadd(cs, i);
830 }
831 }
832 }
833 break;
834 }
835 }
836
837 /*
838 - p_b_cclass - parse a character-class name and deal with it
839 == static void p_b_cclass(struct parse *p, cset *cs);
840 */
841 static void
842 p_b_cclass(struct parse *p, cset *cs)
843 {
844 int c;
845 char *sp = p->next;
846 struct cclass *cp;
847 size_t len;
848
849 while (MORE() && isalpha((uch)PEEK()))
850 NEXT();
851 len = p->next - sp;
852 for (cp = cclasses; cp->name != NULL; cp++)
853 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
854 break;
855 if (cp->name == NULL) {
856 /* oops, didn't find it */
857 SETERROR(REG_ECTYPE);
858 return;
859 }
860
861 switch (cp->fidx) {
862 case CALNUM:
863 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
864 if (isalnum((uch)c))
865 CHadd(cs, c);
866 break;
867 case CALPHA:
868 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
869 if (isalpha((uch)c))
870 CHadd(cs, c);
871 break;
872 case CBLANK:
873 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
874 if (isblank((uch)c))
875 CHadd(cs, c);
876 break;
877 case CCNTRL:
878 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
879 if (iscntrl((uch)c))
880 CHadd(cs, c);
881 break;
882 case CDIGIT:
883 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
884 if (isdigit((uch)c))
885 CHadd(cs, c);
886 break;
887 case CGRAPH:
888 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
889 if (isgraph((uch)c))
890 CHadd(cs, c);
891 break;
892 case CLOWER:
893 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
894 if (islower((uch)c))
895 CHadd(cs, c);
896 break;
897 case CPRINT:
898 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
899 if (isprint((uch)c))
900 CHadd(cs, c);
901 break;
902 case CPUNCT:
903 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
904 if (ispunct((uch)c))
905 CHadd(cs, c);
906 break;
907 case CSPACE:
908 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
909 if (isspace((uch)c))
910 CHadd(cs, c);
911 break;
912 case CUPPER:
913 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
914 if (isupper((uch)c))
915 CHadd(cs, c);
916 break;
917 case CXDIGIT:
918 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
919 if (isxdigit((uch)c))
920 CHadd(cs, c);
921 break;
922 }
923 #if 0
924 for (u = cp->multis; *u != '\0'; u += strlen(u) + 1)
925 MCadd(p, cs, u);
926 #endif
927 }
928
929 /*
930 - p_b_eclass - parse an equivalence-class name and deal with it
931 == static void p_b_eclass(struct parse *p, cset *cs);
932 *
933 * This implementation is incomplete. xxx
934 */
935 static void
936 p_b_eclass(struct parse *p, cset *cs)
937 {
938 char c;
939
940 c = p_b_coll_elem(p, '=');
941 CHadd(cs, c);
942 }
943
944 /*
945 - p_b_symbol - parse a character or [..]ed multicharacter collating symbol
946 == static char p_b_symbol(struct parse *p);
947 */
948 static char /* value of symbol */
949 p_b_symbol(struct parse *p)
950 {
951 char value;
952
953 REQUIRE(MORE(), REG_EBRACK);
954 if (!EATTWO('[', '.'))
955 return(GETNEXT());
956
957 /* collating symbol */
958 value = p_b_coll_elem(p, '.');
959 REQUIRE(EATTWO('.', ']'), REG_ECOLLATE);
960 return(value);
961 }
962
963 /*
964 - p_b_coll_elem - parse a collating-element name and look it up
965 == static char p_b_coll_elem(struct parse *p, int endc);
966 */
967 static char /* value of collating element */
968 p_b_coll_elem(struct parse *p,
969 int endc) /* name ended by endc,']' */
970 {
971 char *sp = p->next;
972 struct cname *cp;
973 int len;
974
975 while (MORE() && !SEETWO(endc, ']'))
976 NEXT();
977 if (!MORE()) {
978 SETERROR(REG_EBRACK);
979 return(0);
980 }
981 len = p->next - sp;
982 for (cp = cnames; cp->name != NULL; cp++)
983 if (strncmp(cp->name, sp, len) == 0 && cp->name[len] == '\0')
984 return(cp->code); /* known name */
985 if (len == 1)
986 return(*sp); /* single character */
987 SETERROR(REG_ECOLLATE); /* neither */
988 return(0);
989 }
990
991 /*
992 - othercase - return the case counterpart of an alphabetic
993 == static char othercase(int ch);
994 */
995 static char /* if no counterpart, return ch */
996 othercase(int ch)
997 {
998 ch = (uch)ch;
999 assert(isalpha(ch));
1000 if (isupper(ch))
1001 return(tolower(ch));
1002 else if (islower(ch))
1003 return(toupper(ch));
1004 else /* peculiar, but could happen */
1005 return(ch);
1006 }
1007
1008 /*
1009 - bothcases - emit a dualcase version of a two-case character
1010 == static void bothcases(struct parse *p, int ch);
1011 *
1012 * Boy, is this implementation ever a kludge...
1013 */
1014 static void
1015 bothcases(struct parse *p, int ch)
1016 {
1017 char *oldnext = p->next;
1018 char *oldend = p->end;
1019 char bracket[3];
1020
1021 ch = (uch)ch;
1022 assert(othercase(ch) != ch); /* p_bracket() would recurse */
1023 p->next = bracket;
1024 p->end = bracket+2;
1025 bracket[0] = ch;
1026 bracket[1] = ']';
1027 bracket[2] = '\0';
1028 p_bracket(p);
1029 assert(p->next == bracket+2);
1030 p->next = oldnext;
1031 p->end = oldend;
1032 }
1033
1034 /*
1035 - ordinary - emit an ordinary character
1036 == static void ordinary(struct parse *p, int ch);
1037 */
1038 static void
1039 ordinary(struct parse *p, int ch)
1040 {
1041 cat_t *cap = p->g->categories;
1042
1043 if ((p->g->cflags&REG_ICASE) && isalpha((uch)ch) && othercase(ch) != ch)
1044 bothcases(p, ch);
1045 else {
1046 EMIT(OCHAR, (uch)ch);
1047 if (cap[ch] == 0)
1048 cap[ch] = p->g->ncategories++;
1049 }
1050 }
1051
1052 /*
1053 - nonnewline - emit REG_NEWLINE version of OANY
1054 == static void nonnewline(struct parse *p);
1055 *
1056 * Boy, is this implementation ever a kludge...
1057 */
1058 static void
1059 nonnewline(struct parse *p)
1060 {
1061 char *oldnext = p->next;
1062 char *oldend = p->end;
1063 char bracket[4];
1064
1065 p->next = bracket;
1066 p->end = bracket+3;
1067 bracket[0] = '^';
1068 bracket[1] = '\n';
1069 bracket[2] = ']';
1070 bracket[3] = '\0';
1071 p_bracket(p);
1072 assert(p->next == bracket+3);
1073 p->next = oldnext;
1074 p->end = oldend;
1075 }
1076
1077 /*
1078 - repeat - generate code for a bounded repetition, recursively if needed
1079 == static void repeat(struct parse *p, sopno start, int from, int to);
1080 */
1081 static void
1082 repeat(struct parse *p,
1083 sopno start, /* operand from here to end of strip */
1084 int from, /* repeated from this number */
1085 int to) /* to this number of times (maybe INFINITY) */
1086 {
1087 sopno finish = HERE();
1088 # define N 2
1089 # define INF 3
1090 # define REP(f, t) ((f)*8 + (t))
1091 # define MAP(n) (((n) <= 1) ? (n) : ((n) == INFINITY) ? INF : N)
1092 sopno copy;
1093
1094 if (p->error != 0) /* head off possible runaway recursion */
1095 return;
1096
1097 assert(from <= to);
1098
1099 switch (REP(MAP(from), MAP(to))) {
1100 case REP(0, 0): /* must be user doing this */
1101 DROP(finish-start); /* drop the operand */
1102 break;
1103 case REP(0, 1): /* as x{1,1}? */
1104 case REP(0, N): /* as x{1,n}? */
1105 case REP(0, INF): /* as x{1,}? */
1106 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1107 INSERT(OCH_, start); /* offset is wrong... */
1108 repeat(p, start+1, 1, to);
1109 ASTERN(OOR1, start);
1110 AHEAD(start); /* ... fix it */
1111 EMIT(OOR2, 0);
1112 AHEAD(THERE());
1113 ASTERN(O_CH, THERETHERE());
1114 break;
1115 case REP(1, 1): /* trivial case */
1116 /* done */
1117 break;
1118 case REP(1, N): /* as x?x{1,n-1} */
1119 /* KLUDGE: emit y? as (y|) until subtle bug gets fixed */
1120 INSERT(OCH_, start);
1121 ASTERN(OOR1, start);
1122 AHEAD(start);
1123 EMIT(OOR2, 0); /* offset very wrong... */
1124 AHEAD(THERE()); /* ...so fix it */
1125 ASTERN(O_CH, THERETHERE());
1126 copy = dupl(p, start+1, finish+1);
1127 assert(copy == finish+4);
1128 repeat(p, copy, 1, to-1);
1129 break;
1130 case REP(1, INF): /* as x+ */
1131 INSERT(OPLUS_, start);
1132 ASTERN(O_PLUS, start);
1133 break;
1134 case REP(N, N): /* as xx{m-1,n-1} */
1135 copy = dupl(p, start, finish);
1136 repeat(p, copy, from-1, to-1);
1137 break;
1138 case REP(N, INF): /* as xx{n-1,INF} */
1139 copy = dupl(p, start, finish);
1140 repeat(p, copy, from-1, to);
1141 break;
1142 default: /* "can't happen" */
1143 SETERROR(REG_ASSERT); /* just in case */
1144 break;
1145 }
1146 }
1147
1148 /*
1149 - seterr - set an error condition
1150 == static int seterr(struct parse *p, int e);
1151 */
1152 static int /* useless but makes type checking happy */
1153 seterr(struct parse *p, int e)
1154 {
1155 if (p->error == 0) /* keep earliest error condition */
1156 p->error = e;
1157 p->next = nuls; /* try to bring things to a halt */
1158 p->end = nuls;
1159 return(0); /* make the return value well-defined */
1160 }
1161
1162 /*
1163 - allocset - allocate a set of characters for []
1164 == static cset *allocset(struct parse *p);
1165 */
1166 static cset *
1167 allocset(struct parse *p)
1168 {
1169 int no = p->g->ncsets++;
1170 size_t nc;
1171 size_t nbytes;
1172 cset *cs;
1173 size_t css = (size_t)p->g->csetsize;
1174 int i;
1175
1176 if (no >= p->ncsalloc) { /* need another column of space */
1177 p->ncsalloc += CHAR_BIT;
1178 nc = p->ncsalloc;
1179 assert(nc % CHAR_BIT == 0);
1180 nbytes = nc / CHAR_BIT * css;
1181 if (p->g->sets == NULL)
1182 p->g->sets = (cset *)malloc(nc * sizeof(cset));
1183 else
1184 p->g->sets = (cset *)reallocf((char *)p->g->sets,
1185 nc * sizeof(cset));
1186 if (p->g->setbits == NULL)
1187 p->g->setbits = (uch *)malloc(nbytes);
1188 else {
1189 p->g->setbits = (uch *)reallocf((char *)p->g->setbits,
1190 nbytes);
1191 /* xxx this isn't right if setbits is now NULL */
1192 for (i = 0; i < no; i++)
1193 p->g->sets[i].ptr = p->g->setbits + css*(i/CHAR_BIT);
1194 }
1195 if (p->g->sets != NULL && p->g->setbits != NULL)
1196 memset((char *)p->g->setbits + (nbytes - css), 0, css);
1197 else {
1198 no = 0;
1199 SETERROR(REG_ESPACE);
1200 /* caller's responsibility not to do set ops */
1201 }
1202 }
1203
1204 assert(p->g->sets != NULL); /* xxx */
1205 cs = &p->g->sets[no];
1206 cs->ptr = p->g->setbits + css*((no)/CHAR_BIT);
1207 cs->mask = 1 << ((no) % CHAR_BIT);
1208 cs->hash = 0;
1209 cs->smultis = 0;
1210 cs->multis = NULL;
1211
1212 return(cs);
1213 }
1214
1215 /*
1216 - freeset - free a now-unused set
1217 == static void freeset(struct parse *p, cset *cs);
1218 */
1219 static void
1220 freeset(struct parse *p, cset *cs)
1221 {
1222 int i;
1223 cset *top = &p->g->sets[p->g->ncsets];
1224 size_t css = (size_t)p->g->csetsize;
1225
1226 for (i = 0; i < css; i++)
1227 CHsub(cs, i);
1228 if (cs == top-1) /* recover only the easy case */
1229 p->g->ncsets--;
1230 }
1231
1232 /*
1233 - freezeset - final processing on a set of characters
1234 == static int freezeset(struct parse *p, cset *cs);
1235 *
1236 * The main task here is merging identical sets. This is usually a waste
1237 * of time (although the hash code minimizes the overhead), but can win
1238 * big if REG_ICASE is being used. REG_ICASE, by the way, is why the hash
1239 * is done using addition rather than xor -- all ASCII [aA] sets xor to
1240 * the same value!
1241 */
1242 static int /* set number */
1243 freezeset(struct parse *p, cset *cs)
1244 {
1245 short h = cs->hash;
1246 int i;
1247 cset *top = &p->g->sets[p->g->ncsets];
1248 cset *cs2;
1249 size_t css = (size_t)p->g->csetsize;
1250
1251 /* look for an earlier one which is the same */
1252 for (cs2 = &p->g->sets[0]; cs2 < top; cs2++)
1253 if (cs2->hash == h && cs2 != cs) {
1254 /* maybe */
1255 for (i = 0; i < css; i++)
1256 if (!!CHIN(cs2, i) != !!CHIN(cs, i))
1257 break; /* no */
1258 if (i == css)
1259 break; /* yes */
1260 }
1261
1262 if (cs2 < top) { /* found one */
1263 freeset(p, cs);
1264 cs = cs2;
1265 }
1266
1267 return((int)(cs - p->g->sets));
1268 }
1269
1270 /*
1271 - firstch - return first character in a set (which must have at least one)
1272 == static int firstch(struct parse *p, cset *cs);
1273 */
1274 static int /* character; there is no "none" value */
1275 firstch(struct parse *p, cset *cs)
1276 {
1277 int i;
1278 size_t css = (size_t)p->g->csetsize;
1279
1280 for (i = 0; i < css; i++)
1281 if (CHIN(cs, i))
1282 return((char)i);
1283 assert(never);
1284 return(0); /* arbitrary */
1285 }
1286
1287 /*
1288 - nch - number of characters in a set
1289 == static int nch(struct parse *p, cset *cs);
1290 */
1291 static int
1292 nch(struct parse *p, cset *cs)
1293 {
1294 int i;
1295 size_t css = (size_t)p->g->csetsize;
1296 int n = 0;
1297
1298 for (i = 0; i < css; i++)
1299 if (CHIN(cs, i))
1300 n++;
1301 return(n);
1302 }
1303
1304 /*
1305 - mcadd - add a collating element to a cset
1306 == static void mcadd(struct parse *p, cset *cs, \
1307 == char *cp);
1308 */
1309 static void
1310 mcadd(struct parse *p, cset *cs, char *cp)
1311 {
1312 size_t oldend = cs->smultis;
1313
1314 cs->smultis += strlen(cp) + 1;
1315 if (cs->multis == NULL)
1316 cs->multis = malloc(cs->smultis);
1317 else
1318 cs->multis = reallocf(cs->multis, cs->smultis);
1319 if (cs->multis == NULL) {
1320 SETERROR(REG_ESPACE);
1321 return;
1322 }
1323
1324 strcpy(cs->multis + oldend - 1, cp);
1325 cs->multis[cs->smultis - 1] = '\0';
1326 }
1327
1328 #if used
1329 /*
1330 - mcsub - subtract a collating element from a cset
1331 == static void mcsub(cset *cs, char *cp);
1332 */
1333 static void
1334 mcsub(cset *cs, char *cp)
1335 {
1336 char *fp = mcfind(cs, cp);
1337 size_t len = strlen(fp);
1338
1339 assert(fp != NULL);
1340 memmove(fp, fp + len + 1, cs->smultis - (fp + len + 1 - cs->multis));
1341 cs->smultis -= len;
1342
1343 if (cs->smultis == 0) {
1344 free(cs->multis);
1345 cs->multis = NULL;
1346 return;
1347 }
1348
1349 cs->multis = reallocf(cs->multis, cs->smultis);
1350 assert(cs->multis != NULL);
1351 }
1352
1353 /*
1354 - mcin - is a collating element in a cset?
1355 == static int mcin(cset *cs, char *cp);
1356 */
1357 static int
1358 mcin(cset *cs, char *cp)
1359 {
1360 return(mcfind(cs, cp) != NULL);
1361 }
1362
1363 /*
1364 - mcfind - find a collating element in a cset
1365 == static char *mcfind(cset *cs, char *cp);
1366 */
1367 static char *
1368 mcfind(cset *cs, char *cp)
1369 {
1370 char *p;
1371
1372 if (cs->multis == NULL)
1373 return(NULL);
1374 for (p = cs->multis; *p != '\0'; p += strlen(p) + 1)
1375 if (strcmp(cp, p) == 0)
1376 return(p);
1377 return(NULL);
1378 }
1379 #endif
1380
1381 /*
1382 - mcinvert - invert the list of collating elements in a cset
1383 == static void mcinvert(struct parse *p, cset *cs);
1384 *
1385 * This would have to know the set of possibilities. Implementation
1386 * is deferred.
1387 */
1388 static void
1389 mcinvert(struct parse *p __unused, cset *cs)
1390 {
1391 assert(cs->multis == NULL); /* xxx */
1392 }
1393
1394 /*
1395 - mccase - add case counterparts of the list of collating elements in a cset
1396 == static void mccase(struct parse *p, cset *cs);
1397 *
1398 * This would have to know the set of possibilities. Implementation
1399 * is deferred.
1400 */
1401 static void
1402 mccase(struct parse *p __unused, cset *cs)
1403 {
1404 assert(cs->multis == NULL); /* xxx */
1405 }
1406
1407 /*
1408 - isinsets - is this character in any sets?
1409 == static int isinsets(struct re_guts *g, int c);
1410 */
1411 static int /* predicate */
1412 isinsets(struct re_guts *g, int c)
1413 {
1414 uch *col;
1415 int i;
1416 int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1417 unsigned uc = (uch)c;
1418
1419 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1420 if (col[uc] != 0)
1421 return(1);
1422 return(0);
1423 }
1424
1425 /*
1426 - samesets - are these two characters in exactly the same sets?
1427 == static int samesets(struct re_guts *g, int c1, int c2);
1428 */
1429 static int /* predicate */
1430 samesets(struct re_guts *g, int c1, int c2)
1431 {
1432 uch *col;
1433 int i;
1434 int ncols = (g->ncsets+(CHAR_BIT-1)) / CHAR_BIT;
1435 unsigned uc1 = (uch)c1;
1436 unsigned uc2 = (uch)c2;
1437
1438 for (i = 0, col = g->setbits; i < ncols; i++, col += g->csetsize)
1439 if (col[uc1] != col[uc2])
1440 return(0);
1441 return(1);
1442 }
1443
1444 /*
1445 - categorize - sort out character categories
1446 == static void categorize(struct parse *p, struct re_guts *g);
1447 */
1448 static void
1449 categorize(struct parse *p, struct re_guts *g)
1450 {
1451 cat_t *cats = g->categories;
1452 int c;
1453 int c2;
1454 cat_t cat;
1455
1456 /* avoid making error situations worse */
1457 if (p->error != 0)
1458 return;
1459
1460 for (c = CHAR_MIN; c <= CHAR_MAX; c++)
1461 if (cats[c] == 0 && isinsets(g, c)) {
1462 cat = g->ncategories++;
1463 cats[c] = cat;
1464 for (c2 = c+1; c2 <= CHAR_MAX; c2++)
1465 if (cats[c2] == 0 && samesets(g, c, c2))
1466 cats[c2] = cat;
1467 }
1468 }
1469
1470 /*
1471 - dupl - emit a duplicate of a bunch of sops
1472 == static sopno dupl(struct parse *p, sopno start, sopno finish);
1473 */
1474 static sopno /* start of duplicate */
1475 dupl(struct parse *p,
1476 sopno start, /* from here */
1477 sopno finish) /* to this less one */
1478 {
1479 sopno ret = HERE();
1480 sopno len = finish - start;
1481
1482 assert(finish >= start);
1483 if (len == 0)
1484 return(ret);
1485 enlarge(p, p->ssize + len); /* this many unexpected additions */
1486 assert(p->ssize >= p->slen + len);
1487 memcpy((char *)(p->strip + p->slen), (char *)(p->strip + start),
1488 (size_t)len*sizeof(sop));
1489 p->slen += len;
1490 return(ret);
1491 }
1492
1493 /*
1494 - doemit - emit a strip operator
1495 == static void doemit(struct parse *p, sop op, size_t opnd);
1496 *
1497 * It might seem better to implement this as a macro with a function as
1498 * hard-case backup, but it's just too big and messy unless there are
1499 * some changes to the data structures. Maybe later.
1500 */
1501 static void
1502 doemit(struct parse *p, sop op, size_t opnd)
1503 {
1504 /* avoid making error situations worse */
1505 if (p->error != 0)
1506 return;
1507
1508 /* deal with oversize operands ("can't happen", more or less) */
1509 assert(opnd < 1<<OPSHIFT);
1510
1511 /* deal with undersized strip */
1512 if (p->slen >= p->ssize)
1513 enlarge(p, (p->ssize+1) / 2 * 3); /* +50% */
1514 assert(p->slen < p->ssize);
1515
1516 /* finally, it's all reduced to the easy case */
1517 p->strip[p->slen++] = SOP(op, opnd);
1518 }
1519
1520 /*
1521 - doinsert - insert a sop into the strip
1522 == static void doinsert(struct parse *p, sop op, size_t opnd, sopno pos);
1523 */
1524 static void
1525 doinsert(struct parse *p, sop op, size_t opnd, sopno pos)
1526 {
1527 sopno sn;
1528 sop s;
1529 int i;
1530
1531 /* avoid making error situations worse */
1532 if (p->error != 0)
1533 return;
1534
1535 sn = HERE();
1536 EMIT(op, opnd); /* do checks, ensure space */
1537 assert(HERE() == sn+1);
1538 s = p->strip[sn];
1539
1540 /* adjust paren pointers */
1541 assert(pos > 0);
1542 for (i = 1; i < NPAREN; i++) {
1543 if (p->pbegin[i] >= pos) {
1544 p->pbegin[i]++;
1545 }
1546 if (p->pend[i] >= pos) {
1547 p->pend[i]++;
1548 }
1549 }
1550
1551 memmove((char *)&p->strip[pos+1], (char *)&p->strip[pos],
1552 (HERE()-pos-1)*sizeof(sop));
1553 p->strip[pos] = s;
1554 }
1555
1556 /*
1557 - dofwd - complete a forward reference
1558 == static void dofwd(struct parse *p, sopno pos, sop value);
1559 */
1560 static void
1561 dofwd(struct parse *p, sopno pos, sop value)
1562 {
1563 /* avoid making error situations worse */
1564 if (p->error != 0)
1565 return;
1566
1567 assert(value < 1<<OPSHIFT);
1568 p->strip[pos] = OP(p->strip[pos]) | value;
1569 }
1570
1571 /*
1572 - enlarge - enlarge the strip
1573 == static void enlarge(struct parse *p, sopno size);
1574 */
1575 static void
1576 enlarge(struct parse *p, sopno size)
1577 {
1578 sop *sp;
1579
1580 if (p->ssize >= size)
1581 return;
1582
1583 sp = (sop *)realloc(p->strip, size*sizeof(sop));
1584 if (sp == NULL) {
1585 SETERROR(REG_ESPACE);
1586 return;
1587 }
1588 p->strip = sp;
1589 p->ssize = size;
1590 }
1591
1592 /*
1593 - stripsnug - compact the strip
1594 == static void stripsnug(struct parse *p, struct re_guts *g);
1595 */
1596 static void
1597 stripsnug(struct parse *p, struct re_guts *g)
1598 {
1599 g->nstates = p->slen;
1600 g->strip = (sop *)realloc((char *)p->strip, p->slen * sizeof(sop));
1601 if (g->strip == NULL) {
1602 SETERROR(REG_ESPACE);
1603 g->strip = p->strip;
1604 }
1605 }
1606
1607 /*
1608 - findmust - fill in must and mlen with longest mandatory literal string
1609 == static void findmust(struct parse *p, struct re_guts *g);
1610 *
1611 * This algorithm could do fancy things like analyzing the operands of |
1612 * for common subsequences. Someday. This code is simple and finds most
1613 * of the interesting cases.
1614 *
1615 * Note that must and mlen got initialized during setup.
1616 */
1617 static void
1618 findmust(struct parse *p, struct re_guts *g)
1619 {
1620 sop *scan;
1621 sop *start;
1622 sop *newstart;
1623 sopno newlen;
1624 sop s;
1625 char *cp;
1626 sopno i;
1627 int offset;
1628 int cs, mccs;
1629
1630 start = NULL;
1631 newstart = NULL;
1632
1633 /* avoid making error situations worse */
1634 if (p->error != 0)
1635 return;
1636
1637 /* Find out if we can handle OANYOF or not */
1638 mccs = 0;
1639 for (cs = 0; cs < g->ncsets; cs++)
1640 if (g->sets[cs].multis != NULL)
1641 mccs = 1;
1642
1643 /* find the longest OCHAR sequence in strip */
1644 newlen = 0;
1645 offset = 0;
1646 g->moffset = 0;
1647 scan = g->strip + 1;
1648 do {
1649 s = *scan++;
1650 switch (OP(s)) {
1651 case OCHAR: /* sequence member */
1652 if (newlen == 0) /* new sequence */
1653 newstart = scan - 1;
1654 newlen++;
1655 break;
1656 case OPLUS_: /* things that don't break one */
1657 case OLPAREN:
1658 case ORPAREN:
1659 break;
1660 case OQUEST_: /* things that must be skipped */
1661 case OCH_:
1662 offset = altoffset(scan, offset, mccs);
1663 scan--;
1664 do {
1665 scan += OPND(s);
1666 s = *scan;
1667 /* assert() interferes w debug printouts */
1668 if (OP(s) != O_QUEST && OP(s) != O_CH &&
1669 OP(s) != OOR2) {
1670 g->iflags |= BAD;
1671 return;
1672 }
1673 } while (OP(s) != O_QUEST && OP(s) != O_CH);
1674 /* fallthrough */
1675 case OBOW: /* things that break a sequence */
1676 case OEOW:
1677 case OBOL:
1678 case OEOL:
1679 case O_QUEST:
1680 case O_CH:
1681 case OEND:
1682 if (newlen > g->mlen) { /* ends one */
1683 start = newstart;
1684 g->mlen = newlen;
1685 if (offset > -1) {
1686 g->moffset += offset;
1687 offset = newlen;
1688 } else
1689 g->moffset = offset;
1690 } else {
1691 if (offset > -1)
1692 offset += newlen;
1693 }
1694 newlen = 0;
1695 break;
1696 case OANY:
1697 if (newlen > g->mlen) { /* ends one */
1698 start = newstart;
1699 g->mlen = newlen;
1700 if (offset > -1) {
1701 g->moffset += offset;
1702 offset = newlen;
1703 } else
1704 g->moffset = offset;
1705 } else {
1706 if (offset > -1)
1707 offset += newlen;
1708 }
1709 if (offset > -1)
1710 offset++;
1711 newlen = 0;
1712 break;
1713 case OANYOF: /* may or may not invalidate offset */
1714 /* First, everything as OANY */
1715 if (newlen > g->mlen) { /* ends one */
1716 start = newstart;
1717 g->mlen = newlen;
1718 if (offset > -1) {
1719 g->moffset += offset;
1720 offset = newlen;
1721 } else
1722 g->moffset = offset;
1723 } else {
1724 if (offset > -1)
1725 offset += newlen;
1726 }
1727 if (offset > -1)
1728 offset++;
1729 newlen = 0;
1730 /* And, now, if we found out we can't deal with
1731 * it, make offset = -1.
1732 */
1733 if (mccs)
1734 offset = -1;
1735 break;
1736 default:
1737 /* Anything here makes it impossible or too hard
1738 * to calculate the offset -- so we give up;
1739 * save the last known good offset, in case the
1740 * must sequence doesn't occur later.
1741 */
1742 if (newlen > g->mlen) { /* ends one */
1743 start = newstart;
1744 g->mlen = newlen;
1745 if (offset > -1)
1746 g->moffset += offset;
1747 else
1748 g->moffset = offset;
1749 }
1750 offset = -1;
1751 newlen = 0;
1752 break;
1753 }
1754 } while (OP(s) != OEND);
1755
1756 if (g->mlen == 0) { /* there isn't one */
1757 g->moffset = -1;
1758 return;
1759 }
1760
1761 /* turn it into a character string */
1762 g->must = malloc((size_t)g->mlen + 1);
1763 if (g->must == NULL) { /* argh; just forget it */
1764 g->mlen = 0;
1765 g->moffset = -1;
1766 return;
1767 }
1768 cp = g->must;
1769 scan = start;
1770 for (i = g->mlen; i > 0; i--) {
1771 while (OP(s = *scan++) != OCHAR)
1772 continue;
1773 assert(cp < g->must + g->mlen);
1774 *cp++ = (char)OPND(s);
1775 }
1776 assert(cp == g->must + g->mlen);
1777 *cp++ = '\0'; /* just on general principles */
1778 }
1779
1780 /*
1781 - altoffset - choose biggest offset among multiple choices
1782 == static int altoffset(sop *scan, int offset, int mccs);
1783 *
1784 * Compute, recursively if necessary, the largest offset among multiple
1785 * re paths.
1786 */
1787 static int
1788 altoffset(sop *scan, int offset, int mccs)
1789 {
1790 int largest;
1791 int try;
1792 sop s;
1793
1794 /* If we gave up already on offsets, return */
1795 if (offset == -1)
1796 return -1;
1797
1798 largest = 0;
1799 try = 0;
1800 s = *scan++;
1801 while (OP(s) != O_QUEST && OP(s) != O_CH) {
1802 switch (OP(s)) {
1803 case OOR1:
1804 if (try > largest)
1805 largest = try;
1806 try = 0;
1807 break;
1808 case OQUEST_:
1809 case OCH_:
1810 try = altoffset(scan, try, mccs);
1811 if (try == -1)
1812 return -1;
1813 scan--;
1814 do {
1815 scan += OPND(s);
1816 s = *scan;
1817 if (OP(s) != O_QUEST && OP(s) != O_CH &&
1818 OP(s) != OOR2)
1819 return -1;
1820 } while (OP(s) != O_QUEST && OP(s) != O_CH);
1821 /* We must skip to the next position, or we'll
1822 * leave altoffset() too early.
1823 */
1824 scan++;
1825 break;
1826 case OANYOF:
1827 if (mccs)
1828 return -1;
1829 case OCHAR:
1830 case OANY:
1831 try++;
1832 case OBOW:
1833 case OEOW:
1834 case OLPAREN:
1835 case ORPAREN:
1836 case OOR2:
1837 break;
1838 default:
1839 try = -1;
1840 break;
1841 }
1842 if (try == -1)
1843 return -1;
1844 s = *scan++;
1845 }
1846
1847 if (try > largest)
1848 largest = try;
1849
1850 return largest+offset;
1851 }
1852
1853 /*
1854 - computejumps - compute char jumps for BM scan
1855 == static void computejumps(struct parse *p, struct re_guts *g);
1856 *
1857 * This algorithm assumes g->must exists and is has size greater than
1858 * zero. It's based on the algorithm found on Computer Algorithms by
1859 * Sara Baase.
1860 *
1861 * A char jump is the number of characters one needs to jump based on
1862 * the value of the character from the text that was mismatched.
1863 */
1864 static void
1865 computejumps(struct parse *p, struct re_guts *g)
1866 {
1867 int ch;
1868 int mindex;
1869
1870 /* Avoid making errors worse */
1871 if (p->error != 0)
1872 return;
1873
1874 g->charjump = (int*) malloc((NC + 1) * sizeof(int));
1875 if (g->charjump == NULL) /* Not a fatal error */
1876 return;
1877 /* Adjust for signed chars, if necessary */
1878 g->charjump = &g->charjump[-(CHAR_MIN)];
1879
1880 /* If the character does not exist in the pattern, the jump
1881 * is equal to the number of characters in the pattern.
1882 */
1883 for (ch = CHAR_MIN; ch < (CHAR_MAX + 1); ch++)
1884 g->charjump[ch] = g->mlen;
1885
1886 /* If the character does exist, compute the jump that would
1887 * take us to the last character in the pattern equal to it
1888 * (notice that we match right to left, so that last character
1889 * is the first one that would be matched).
1890 */
1891 for (mindex = 0; mindex < g->mlen; mindex++)
1892 g->charjump[g->must[mindex]] = g->mlen - mindex - 1;
1893 }
1894
1895 /*
1896 - computematchjumps - compute match jumps for BM scan
1897 == static void computematchjumps(struct parse *p, struct re_guts *g);
1898 *
1899 * This algorithm assumes g->must exists and is has size greater than
1900 * zero. It's based on the algorithm found on Computer Algorithms by
1901 * Sara Baase.
1902 *
1903 * A match jump is the number of characters one needs to advance based
1904 * on the already-matched suffix.
1905 * Notice that all values here are minus (g->mlen-1), because of the way
1906 * the search algorithm works.
1907 */
1908 static void
1909 computematchjumps(struct parse *p, struct re_guts *g)
1910 {
1911 int mindex; /* General "must" iterator */
1912 int suffix; /* Keeps track of matching suffix */
1913 int ssuffix; /* Keeps track of suffixes' suffix */
1914 int* pmatches; /* pmatches[k] points to the next i
1915 * such that i+1...mlen is a substring
1916 * of k+1...k+mlen-i-1
1917 */
1918
1919 /* Avoid making errors worse */
1920 if (p->error != 0)
1921 return;
1922
1923 pmatches = (int*) malloc(g->mlen * sizeof(unsigned int));
1924 if (pmatches == NULL) {
1925 g->matchjump = NULL;
1926 return;
1927 }
1928
1929 g->matchjump = (int*) malloc(g->mlen * sizeof(unsigned int));
1930 if (g->matchjump == NULL) /* Not a fatal error */
1931 return;
1932
1933 /* Set maximum possible jump for each character in the pattern */
1934 for (mindex = 0; mindex < g->mlen; mindex++)
1935 g->matchjump[mindex] = 2*g->mlen - mindex - 1;
1936
1937 /* Compute pmatches[] */
1938 for (mindex = g->mlen - 1, suffix = g->mlen; mindex >= 0;
1939 mindex--, suffix--) {
1940 pmatches[mindex] = suffix;
1941
1942 /* If a mismatch is found, interrupting the substring,
1943 * compute the matchjump for that position. If no
1944 * mismatch is found, then a text substring mismatched
1945 * against the suffix will also mismatch against the
1946 * substring.
1947 */
1948 while (suffix < g->mlen
1949 && g->must[mindex] != g->must[suffix]) {
1950 g->matchjump[suffix] = MIN(g->matchjump[suffix],
1951 g->mlen - mindex - 1);
1952 suffix = pmatches[suffix];
1953 }
1954 }
1955
1956 /* Compute the matchjump up to the last substring found to jump
1957 * to the beginning of the largest must pattern prefix matching
1958 * it's own suffix.
1959 */
1960 for (mindex = 0; mindex <= suffix; mindex++)
1961 g->matchjump[mindex] = MIN(g->matchjump[mindex],
1962 g->mlen + suffix - mindex);
1963
1964 ssuffix = pmatches[suffix];
1965 while (suffix < g->mlen) {
1966 while (suffix <= ssuffix && suffix < g->mlen) {
1967 g->matchjump[suffix] = MIN(g->matchjump[suffix],
1968 g->mlen + ssuffix - suffix);
1969 suffix++;
1970 }
1971 if (suffix < g->mlen)
1972 ssuffix = pmatches[ssuffix];
1973 }
1974
1975 free(pmatches);
1976 }
1977
1978 /*
1979 - pluscount - count + nesting
1980 == static sopno pluscount(struct parse *p, struct re_guts *g);
1981 */
1982 static sopno /* nesting depth */
1983 pluscount(struct parse *p, struct re_guts *g)
1984 {
1985 sop *scan;
1986 sop s;
1987 sopno plusnest = 0;
1988 sopno maxnest = 0;
1989
1990 if (p->error != 0)
1991 return(0); /* there may not be an OEND */
1992
1993 scan = g->strip + 1;
1994 do {
1995 s = *scan++;
1996 switch (OP(s)) {
1997 case OPLUS_:
1998 plusnest++;
1999 break;
2000 case O_PLUS:
2001 if (plusnest > maxnest)
2002 maxnest = plusnest;
2003 plusnest--;
2004 break;
2005 }
2006 } while (OP(s) != OEND);
2007 if (plusnest != 0)
2008 g->iflags |= BAD;
2009 return(maxnest);
2010 }
DragonFly BSD