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