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