?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
sys/vfs/hammer2: Fix multiple "radii" -> "radix"
[dragonfly.git] / contrib / awk / b.c
blob6fb734359ae5c256d1db98d283346d2a7c418601
1 /****************************************************************
2 Copyright (C) Lucent Technologies 1997
3 All Rights Reserved
4
5 Permission to use, copy, modify, and distribute this software and
6 its documentation for any purpose and without fee is hereby
7 granted, provided that the above copyright notice appear in all
8 copies and that both that the copyright notice and this
9 permission notice and warranty disclaimer appear in supporting
10 documentation, and that the name Lucent Technologies or any of
11 its entities not be used in advertising or publicity pertaining
12 to distribution of the software without specific, written prior
13 permission.
14
15 LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16 INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
17 IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY
18 SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
19 WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
20 IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
21 ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
22 THIS SOFTWARE.
23 ****************************************************************/
24
25 /* lasciate ogne speranza, voi ch'intrate. */
26
27 #define DEBUG
28
29 #include <ctype.h>
30 #include <limits.h>
31 #include <stdio.h>
32 #include <string.h>
33 #include <stdlib.h>
34 #include "awk.h"
35 #include "awkgram.tab.h"
36
37 #define MAXLIN 22
38
39 #define type(v) (v)->nobj /* badly overloaded here */
40 #define info(v) (v)->ntype /* badly overloaded here */
41 #define left(v) (v)->narg[0]
42 #define right(v) (v)->narg[1]
43 #define parent(v) (v)->nnext
44
45 #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
46 #define ELEAF case EMPTYRE: /* empty string in regexp */
47 #define UNARY case STAR: case PLUS: case QUEST:
48
49 /* encoding in tree Nodes:
50 leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL, EMPTYRE):
51 left is index, right contains value or pointer to value
52 unary (STAR, PLUS, QUEST): left is child, right is null
53 binary (CAT, OR): left and right are children
54 parent contains pointer to parent
55 */
56
57
58 int *setvec;
59 int *tmpset;
60 int maxsetvec = 0;
61
62 int rtok; /* next token in current re */
63 int rlxval;
64 static const uschar *rlxstr;
65 static const uschar *prestr; /* current position in current re */
66 static const uschar *lastre; /* origin of last re */
67 static const uschar *lastatom; /* origin of last Atom */
68 static const uschar *starttok;
69 static const uschar *basestr; /* starts with original, replaced during
70 repetition processing */
71 static const uschar *firstbasestr;
72
73 static int setcnt;
74 static int poscnt;
75
76 const char *patbeg;
77 int patlen;
78
79 #define NFA 128 /* cache this many dynamic fa's */
80 fa *fatab[NFA];
81 int nfatab = 0; /* entries in fatab */
82
83 static int *
84 intalloc(size_t n, const char *f)
85 {
86 int *p = (int *) calloc(n, sizeof(int));
87 if (p == NULL)
88 overflo(f);
89 return p;
90 }
91
92 static void
93 resizesetvec(const char *f)
94 {
95 if (maxsetvec == 0)
96 maxsetvec = MAXLIN;
97 else
98 maxsetvec *= 4;
99 setvec = (int *) realloc(setvec, maxsetvec * sizeof(*setvec));
100 tmpset = (int *) realloc(tmpset, maxsetvec * sizeof(*tmpset));
101 if (setvec == NULL || tmpset == NULL)
102 overflo(f);
103 }
104
105 static void
106 resize_state(fa *f, int state)
107 {
108 unsigned int **p;
109 uschar *p2;
110 int **p3;
111 int i, new_count;
112
113 if (++state < f->state_count)
114 return;
115
116 new_count = state + 10; /* needs to be tuned */
117
118 p = (unsigned int **) realloc(f->gototab, new_count * sizeof(f->gototab[0]));
119 if (p == NULL)
120 goto out;
121 f->gototab = p;
122
123 p2 = (uschar *) realloc(f->out, new_count * sizeof(f->out[0]));
124 if (p2 == NULL)
125 goto out;
126 f->out = p2;
127
128 p3 = (int **) realloc(f->posns, new_count * sizeof(f->posns[0]));
129 if (p3 == NULL)
130 goto out;
131 f->posns = p3;
132
133 for (i = f->state_count; i < new_count; ++i) {
134 f->gototab[i] = (unsigned int *) calloc(NCHARS, sizeof(**f->gototab));
135 if (f->gototab[i] == NULL)
136 goto out;
137 f->out[i] = 0;
138 f->posns[i] = NULL;
139 }
140 f->state_count = new_count;
141 return;
142 out:
143 overflo(__func__);
144 }
145
146 fa *makedfa(const char *s, bool anchor) /* returns dfa for reg expr s */
147 {
148 int i, use, nuse;
149 fa *pfa;
150 static int now = 1;
151
152 if (setvec == NULL) { /* first time through any RE */
153 resizesetvec(__func__);
154 }
155
156 if (compile_time != RUNNING) /* a constant for sure */
157 return mkdfa(s, anchor);
158 for (i = 0; i < nfatab; i++) /* is it there already? */
159 if (fatab[i]->anchor == anchor
160 && strcmp((const char *) fatab[i]->restr, s) == 0) {
161 fatab[i]->use = now++;
162 return fatab[i];
163 }
164 pfa = mkdfa(s, anchor);
165 if (nfatab < NFA) { /* room for another */
166 fatab[nfatab] = pfa;
167 fatab[nfatab]->use = now++;
168 nfatab++;
169 return pfa;
170 }
171 use = fatab[0]->use; /* replace least-recently used */
172 nuse = 0;
173 for (i = 1; i < nfatab; i++)
174 if (fatab[i]->use < use) {
175 use = fatab[i]->use;
176 nuse = i;
177 }
178 freefa(fatab[nuse]);
179 fatab[nuse] = pfa;
180 pfa->use = now++;
181 return pfa;
182 }
183
184 fa *mkdfa(const char *s, bool anchor) /* does the real work of making a dfa */
185 /* anchor = true for anchored matches, else false */
186 {
187 Node *p, *p1;
188 fa *f;
189
190 firstbasestr = (const uschar *) s;
191 basestr = firstbasestr;
192 p = reparse(s);
193 p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
194 /* put ALL STAR in front of reg. exp. */
195 p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
196 /* put FINAL after reg. exp. */
197
198 poscnt = 0;
199 penter(p1); /* enter parent pointers and leaf indices */
200 if ((f = (fa *) calloc(1, sizeof(fa) + poscnt * sizeof(rrow))) == NULL)
201 overflo(__func__);
202 f->accept = poscnt-1; /* penter has computed number of positions in re */
203 cfoll(f, p1); /* set up follow sets */
204 freetr(p1);
205 resize_state(f, 1);
206 f->posns[0] = intalloc(*(f->re[0].lfollow), __func__);
207 f->posns[1] = intalloc(1, __func__);
208 *f->posns[1] = 0;
209 f->initstat = makeinit(f, anchor);
210 f->anchor = anchor;
211 f->restr = (uschar *) tostring(s);
212 if (firstbasestr != basestr) {
213 if (basestr)
214 xfree(basestr);
215 }
216 return f;
217 }
218
219 int makeinit(fa *f, bool anchor)
220 {
221 int i, k;
222
223 f->curstat = 2;
224 f->out[2] = 0;
225 k = *(f->re[0].lfollow);
226 xfree(f->posns[2]);
227 f->posns[2] = intalloc(k + 1, __func__);
228 for (i = 0; i <= k; i++) {
229 (f->posns[2])[i] = (f->re[0].lfollow)[i];
230 }
231 if ((f->posns[2])[1] == f->accept)
232 f->out[2] = 1;
233 for (i = 0; i < NCHARS; i++)
234 f->gototab[2][i] = 0;
235 f->curstat = cgoto(f, 2, HAT);
236 if (anchor) {
237 *f->posns[2] = k-1; /* leave out position 0 */
238 for (i = 0; i < k; i++) {
239 (f->posns[0])[i] = (f->posns[2])[i];
240 }
241
242 f->out[0] = f->out[2];
243 if (f->curstat != 2)
244 --(*f->posns[f->curstat]);
245 }
246 return f->curstat;
247 }
248
249 void penter(Node *p) /* set up parent pointers and leaf indices */
250 {
251 switch (type(p)) {
252 ELEAF
253 LEAF
254 info(p) = poscnt;
255 poscnt++;
256 break;
257 UNARY
258 penter(left(p));
259 parent(left(p)) = p;
260 break;
261 case CAT:
262 case OR:
263 penter(left(p));
264 penter(right(p));
265 parent(left(p)) = p;
266 parent(right(p)) = p;
267 break;
268 case ZERO:
269 break;
270 default: /* can't happen */
271 FATAL("can't happen: unknown type %d in penter", type(p));
272 break;
273 }
274 }
275
276 void freetr(Node *p) /* free parse tree */
277 {
278 switch (type(p)) {
279 ELEAF
280 LEAF
281 xfree(p);
282 break;
283 UNARY
284 case ZERO:
285 freetr(left(p));
286 xfree(p);
287 break;
288 case CAT:
289 case OR:
290 freetr(left(p));
291 freetr(right(p));
292 xfree(p);
293 break;
294 default: /* can't happen */
295 FATAL("can't happen: unknown type %d in freetr", type(p));
296 break;
297 }
298 }
299
300 /* in the parsing of regular expressions, metacharacters like . have */
301 /* to be seen literally; \056 is not a metacharacter. */
302
303 int hexstr(const uschar **pp) /* find and eval hex string at pp, return new p */
304 { /* only pick up one 8-bit byte (2 chars) */
305 const uschar *p;
306 int n = 0;
307 int i;
308
309 for (i = 0, p = *pp; i < 2 && isxdigit(*p); i++, p++) {
310 if (isdigit(*p))
311 n = 16 * n + *p - '0';
312 else if (*p >= 'a' && *p <= 'f')
313 n = 16 * n + *p - 'a' + 10;
314 else if (*p >= 'A' && *p <= 'F')
315 n = 16 * n + *p - 'A' + 10;
316 }
317 *pp = p;
318 return n;
319 }
320
321 #define isoctdigit(c) ((c) >= '0' && (c) <= '7') /* multiple use of arg */
322
323 int quoted(const uschar **pp) /* pick up next thing after a \\ */
324 /* and increment *pp */
325 {
326 const uschar *p = *pp;
327 int c;
328
329 if ((c = *p++) == 't')
330 c = '\t';
331 else if (c == 'n')
332 c = '\n';
333 else if (c == 'f')
334 c = '\f';
335 else if (c == 'r')
336 c = '\r';
337 else if (c == 'b')
338 c = '\b';
339 else if (c == 'v')
340 c = '\v';
341 else if (c == 'a')
342 c = '\a';
343 else if (c == '\\')
344 c = '\\';
345 else if (c == 'x') { /* hexadecimal goo follows */
346 c = hexstr(&p); /* this adds a null if number is invalid */
347 } else if (isoctdigit(c)) { /* \d \dd \ddd */
348 int n = c - '0';
349 if (isoctdigit(*p)) {
350 n = 8 * n + *p++ - '0';
351 if (isoctdigit(*p))
352 n = 8 * n + *p++ - '0';
353 }
354 c = n;
355 } /* else */
356 /* c = c; */
357 *pp = p;
358 return c;
359 }
360
361 char *cclenter(const char *argp) /* add a character class */
362 {
363 int i, c, c2;
364 const uschar *op, *p = (const uschar *) argp;
365 uschar *bp;
366 static uschar *buf = NULL;
367 static int bufsz = 100;
368
369 op = p;
370 if (buf == NULL && (buf = (uschar *) malloc(bufsz)) == NULL)
371 FATAL("out of space for character class [%.10s...] 1", p);
372 bp = buf;
373 for (i = 0; (c = *p++) != 0; ) {
374 if (c == '\\') {
375 c = quoted(&p);
376 } else if (c == '-' && i > 0 && bp[-1] != 0) {
377 if (*p != 0) {
378 c = bp[-1];
379 c2 = *p++;
380 if (c2 == '\\')
381 c2 = quoted(&p);
382 if (c > c2) { /* empty; ignore */
383 bp--;
384 i--;
385 continue;
386 }
387 while (c < c2) {
388 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter1"))
389 FATAL("out of space for character class [%.10s...] 2", p);
390 *bp++ = ++c;
391 i++;
392 }
393 continue;
394 }
395 }
396 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "cclenter2"))
397 FATAL("out of space for character class [%.10s...] 3", p);
398 *bp++ = c;
399 i++;
400 }
401 *bp = 0;
402 DPRINTF("cclenter: in = |%s|, out = |%s|\n", op, buf);
403 xfree(op);
404 return (char *) tostring((char *) buf);
405 }
406
407 void overflo(const char *s)
408 {
409 FATAL("regular expression too big: out of space in %.30s...", s);
410 }
411
412 void cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into lfollow[leaf] */
413 {
414 int i;
415 int *p;
416
417 switch (type(v)) {
418 ELEAF
419 LEAF
420 f->re[info(v)].ltype = type(v);
421 f->re[info(v)].lval.np = right(v);
422 while (f->accept >= maxsetvec) { /* guessing here! */
423 resizesetvec(__func__);
424 }
425 for (i = 0; i <= f->accept; i++)
426 setvec[i] = 0;
427 setcnt = 0;
428 follow(v); /* computes setvec and setcnt */
429 p = intalloc(setcnt + 1, __func__);
430 f->re[info(v)].lfollow = p;
431 *p = setcnt;
432 for (i = f->accept; i >= 0; i--)
433 if (setvec[i] == 1)
434 *++p = i;
435 break;
436 UNARY
437 cfoll(f,left(v));
438 break;
439 case CAT:
440 case OR:
441 cfoll(f,left(v));
442 cfoll(f,right(v));
443 break;
444 case ZERO:
445 break;
446 default: /* can't happen */
447 FATAL("can't happen: unknown type %d in cfoll", type(v));
448 }
449 }
450
451 int first(Node *p) /* collects initially active leaves of p into setvec */
452 /* returns 0 if p matches empty string */
453 {
454 int b, lp;
455
456 switch (type(p)) {
457 ELEAF
458 LEAF
459 lp = info(p); /* look for high-water mark of subscripts */
460 while (setcnt >= maxsetvec || lp >= maxsetvec) { /* guessing here! */
461 resizesetvec(__func__);
462 }
463 if (type(p) == EMPTYRE) {
464 setvec[lp] = 0;
465 return(0);
466 }
467 if (setvec[lp] != 1) {
468 setvec[lp] = 1;
469 setcnt++;
470 }
471 if (type(p) == CCL && (*(char *) right(p)) == '\0')
472 return(0); /* empty CCL */
473 return(1);
474 case PLUS:
475 if (first(left(p)) == 0)
476 return(0);
477 return(1);
478 case STAR:
479 case QUEST:
480 first(left(p));
481 return(0);
482 case CAT:
483 if (first(left(p)) == 0 && first(right(p)) == 0) return(0);
484 return(1);
485 case OR:
486 b = first(right(p));
487 if (first(left(p)) == 0 || b == 0) return(0);
488 return(1);
489 case ZERO:
490 return 0;
491 }
492 FATAL("can't happen: unknown type %d in first", type(p)); /* can't happen */
493 return(-1);
494 }
495
496 void follow(Node *v) /* collects leaves that can follow v into setvec */
497 {
498 Node *p;
499
500 if (type(v) == FINAL)
501 return;
502 p = parent(v);
503 switch (type(p)) {
504 case STAR:
505 case PLUS:
506 first(v);
507 follow(p);
508 return;
509
510 case OR:
511 case QUEST:
512 follow(p);
513 return;
514
515 case CAT:
516 if (v == left(p)) { /* v is left child of p */
517 if (first(right(p)) == 0) {
518 follow(p);
519 return;
520 }
521 } else /* v is right child */
522 follow(p);
523 return;
524 }
525 }
526
527 int member(int c, const char *sarg) /* is c in s? */
528 {
529 const uschar *s = (const uschar *) sarg;
530
531 while (*s)
532 if (c == *s++)
533 return(1);
534 return(0);
535 }
536
537 int match(fa *f, const char *p0) /* shortest match ? */
538 {
539 int s, ns;
540 const uschar *p = (const uschar *) p0;
541
542 s = f->initstat;
543 assert (s < f->state_count);
544
545 if (f->out[s])
546 return(1);
547 do {
548 /* assert(*p < NCHARS); */
549 if ((ns = f->gototab[s][*p]) != 0)
550 s = ns;
551 else
552 s = cgoto(f, s, *p);
553 if (f->out[s])
554 return(1);
555 } while (*p++ != 0);
556 return(0);
557 }
558
559 int pmatch(fa *f, const char *p0) /* longest match, for sub */
560 {
561 int s, ns;
562 const uschar *p = (const uschar *) p0;
563 const uschar *q;
564
565 s = f->initstat;
566 assert(s < f->state_count);
567
568 patbeg = (const char *)p;
569 patlen = -1;
570 do {
571 q = p;
572 do {
573 if (f->out[s]) /* final state */
574 patlen = q-p;
575 /* assert(*q < NCHARS); */
576 if ((ns = f->gototab[s][*q]) != 0)
577 s = ns;
578 else
579 s = cgoto(f, s, *q);
580
581 assert(s < f->state_count);
582
583 if (s == 1) { /* no transition */
584 if (patlen >= 0) {
585 patbeg = (const char *) p;
586 return(1);
587 }
588 else
589 goto nextin; /* no match */
590 }
591 } while (*q++ != 0);
592 if (f->out[s])
593 patlen = q-p-1; /* don't count $ */
594 if (patlen >= 0) {
595 patbeg = (const char *) p;
596 return(1);
597 }
598 nextin:
599 s = 2;
600 } while (*p++);
601 return (0);
602 }
603
604 int nematch(fa *f, const char *p0) /* non-empty match, for sub */
605 {
606 int s, ns;
607 const uschar *p = (const uschar *) p0;
608 const uschar *q;
609
610 s = f->initstat;
611 assert(s < f->state_count);
612
613 patbeg = (const char *)p;
614 patlen = -1;
615 while (*p) {
616 q = p;
617 do {
618 if (f->out[s]) /* final state */
619 patlen = q-p;
620 /* assert(*q < NCHARS); */
621 if ((ns = f->gototab[s][*q]) != 0)
622 s = ns;
623 else
624 s = cgoto(f, s, *q);
625 if (s == 1) { /* no transition */
626 if (patlen > 0) {
627 patbeg = (const char *) p;
628 return(1);
629 } else
630 goto nnextin; /* no nonempty match */
631 }
632 } while (*q++ != 0);
633 if (f->out[s])
634 patlen = q-p-1; /* don't count $ */
635 if (patlen > 0 ) {
636 patbeg = (const char *) p;
637 return(1);
638 }
639 nnextin:
640 s = 2;
641 p++;
642 }
643 return (0);
644 }
645
646
647 /*
648 * NAME
649 * fnematch
650 *
651 * DESCRIPTION
652 * A stream-fed version of nematch which transfers characters to a
653 * null-terminated buffer. All characters up to and including the last
654 * character of the matching text or EOF are placed in the buffer. If
655 * a match is found, patbeg and patlen are set appropriately.
656 *
657 * RETURN VALUES
658 * false No match found.
659 * true Match found.
660 */
661
662 bool fnematch(fa *pfa, FILE *f, char **pbuf, int *pbufsize, int quantum)
663 {
664 char *buf = *pbuf;
665 int bufsize = *pbufsize;
666 int c, i, j, k, ns, s;
667
668 s = pfa->initstat;
669 patlen = 0;
670
671 /*
672 * All indices relative to buf.
673 * i <= j <= k <= bufsize
674 *
675 * i: origin of active substring
676 * j: current character
677 * k: destination of next getc()
678 */
679 i = -1, k = 0;
680 do {
681 j = i++;
682 do {
683 if (++j == k) {
684 if (k == bufsize)
685 if (!adjbuf((char **) &buf, &bufsize, bufsize+1, quantum, 0, "fnematch"))
686 FATAL("stream '%.30s...' too long", buf);
687 buf[k++] = (c = getc(f)) != EOF ? c : 0;
688 }
689 c = (uschar)buf[j];
690 /* assert(c < NCHARS); */
691
692 if ((ns = pfa->gototab[s][c]) != 0)
693 s = ns;
694 else
695 s = cgoto(pfa, s, c);
696
697 if (pfa->out[s]) { /* final state */
698 patlen = j - i + 1;
699 if (c == 0) /* don't count $ */
700 patlen--;
701 }
702 } while (buf[j] && s != 1);
703 s = 2;
704 } while (buf[i] && !patlen);
705
706 /* adjbuf() may have relocated a resized buffer. Inform the world. */
707 *pbuf = buf;
708 *pbufsize = bufsize;
709
710 if (patlen) {
711 patbeg = (char *) buf + i;
712 /*
713 * Under no circumstances is the last character fed to
714 * the automaton part of the match. It is EOF's nullbyte,
715 * or it sent the automaton into a state with no further
716 * transitions available (s==1), or both. Room for a
717 * terminating nullbyte is guaranteed.
718 *
719 * ungetc any chars after the end of matching text
720 * (except for EOF's nullbyte, if present) and null
721 * terminate the buffer.
722 */
723 do
724 if (buf[--k] && ungetc(buf[k], f) == EOF)
725 FATAL("unable to ungetc '%c'", buf[k]);
726 while (k > i + patlen);
727 buf[k] = '\0';
728 return true;
729 }
730 else
731 return false;
732 }
733
734 Node *reparse(const char *p) /* parses regular expression pointed to by p */
735 { /* uses relex() to scan regular expression */
736 Node *np;
737
738 DPRINTF("reparse <%s>\n", p);
739 lastre = prestr = (const uschar *) p; /* prestr points to string to be parsed */
740 rtok = relex();
741 /* GNU compatibility: an empty regexp matches anything */
742 if (rtok == '\0') {
743 /* FATAL("empty regular expression"); previous */
744 return(op2(EMPTYRE, NIL, NIL));
745 }
746 np = regexp();
747 if (rtok != '\0')
748 FATAL("syntax error in regular expression %s at %s", lastre, prestr);
749 return(np);
750 }
751
752 Node *regexp(void) /* top-level parse of reg expr */
753 {
754 return (alt(concat(primary())));
755 }
756
757 Node *primary(void)
758 {
759 Node *np;
760 int savelastatom;
761
762 switch (rtok) {
763 case CHAR:
764 lastatom = starttok;
765 np = op2(CHAR, NIL, itonp(rlxval));
766 rtok = relex();
767 return (unary(np));
768 case ALL:
769 rtok = relex();
770 return (unary(op2(ALL, NIL, NIL)));
771 case EMPTYRE:
772 rtok = relex();
773 return (unary(op2(EMPTYRE, NIL, NIL)));
774 case DOT:
775 lastatom = starttok;
776 rtok = relex();
777 return (unary(op2(DOT, NIL, NIL)));
778 case CCL:
779 np = op2(CCL, NIL, (Node*) cclenter((const char *) rlxstr));
780 lastatom = starttok;
781 rtok = relex();
782 return (unary(np));
783 case NCCL:
784 np = op2(NCCL, NIL, (Node *) cclenter((const char *) rlxstr));
785 lastatom = starttok;
786 rtok = relex();
787 return (unary(np));
788 case '^':
789 rtok = relex();
790 return (unary(op2(CHAR, NIL, itonp(HAT))));
791 case '$':
792 rtok = relex();
793 return (unary(op2(CHAR, NIL, NIL)));
794 case '(':
795 lastatom = starttok;
796 savelastatom = starttok - basestr; /* Retain over recursion */
797 rtok = relex();
798 if (rtok == ')') { /* special pleading for () */
799 rtok = relex();
800 return unary(op2(CCL, NIL, (Node *) tostring("")));
801 }
802 np = regexp();
803 if (rtok == ')') {
804 lastatom = basestr + savelastatom; /* Restore */
805 rtok = relex();
806 return (unary(np));
807 }
808 else
809 FATAL("syntax error in regular expression %s at %s", lastre, prestr);
810 default:
811 FATAL("illegal primary in regular expression %s at %s", lastre, prestr);
812 }
813 return 0; /*NOTREACHED*/
814 }
815
816 Node *concat(Node *np)
817 {
818 switch (rtok) {
819 case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
820 return (concat(op2(CAT, np, primary())));
821 case EMPTYRE:
822 rtok = relex();
823 return (concat(op2(CAT, op2(CCL, NIL, (Node *) tostring("")),
824 primary())));
825 }
826 return (np);
827 }
828
829 Node *alt(Node *np)
830 {
831 if (rtok == OR) {
832 rtok = relex();
833 return (alt(op2(OR, np, concat(primary()))));
834 }
835 return (np);
836 }
837
838 Node *unary(Node *np)
839 {
840 switch (rtok) {
841 case STAR:
842 rtok = relex();
843 return (unary(op2(STAR, np, NIL)));
844 case PLUS:
845 rtok = relex();
846 return (unary(op2(PLUS, np, NIL)));
847 case QUEST:
848 rtok = relex();
849 return (unary(op2(QUEST, np, NIL)));
850 case ZERO:
851 rtok = relex();
852 return (unary(op2(ZERO, np, NIL)));
853 default:
854 return (np);
855 }
856 }
857
858 /*
859 * Character class definitions conformant to the POSIX locale as
860 * defined in IEEE P1003.1 draft 7 of June 2001, assuming the source
861 * and operating character sets are both ASCII (ISO646) or supersets
862 * thereof.
863 *
864 * Note that to avoid overflowing the temporary buffer used in
865 * relex(), the expanded character class (prior to range expansion)
866 * must be less than twice the size of their full name.
867 */
868
869 /* Because isblank doesn't show up in any of the header files on any
870 * system i use, it's defined here. if some other locale has a richer
871 * definition of "blank", define HAS_ISBLANK and provide your own
872 * version.
873 * the parentheses here are an attempt to find a path through the maze
874 * of macro definition and/or function and/or version provided. thanks
875 * to nelson beebe for the suggestion; let's see if it works everywhere.
876 */
877
878 /* #define HAS_ISBLANK */
879 #ifndef HAS_ISBLANK
880
881 int (xisblank)(int c)
882 {
883 return c==' ' || c=='\t';
884 }
885
886 #endif
887
888 static const struct charclass {
889 const char *cc_name;
890 int cc_namelen;
891 int (*cc_func)(int);
892 } charclasses[] = {
893 { "alnum", 5, isalnum },
894 { "alpha", 5, isalpha },
895 #ifndef HAS_ISBLANK
896 { "blank", 5, xisblank },
897 #else
898 { "blank", 5, isblank },
899 #endif
900 { "cntrl", 5, iscntrl },
901 { "digit", 5, isdigit },
902 { "graph", 5, isgraph },
903 { "lower", 5, islower },
904 { "print", 5, isprint },
905 { "punct", 5, ispunct },
906 { "space", 5, isspace },
907 { "upper", 5, isupper },
908 { "xdigit", 6, isxdigit },
909 { NULL, 0, NULL },
910 };
911
912 #define REPEAT_SIMPLE 0
913 #define REPEAT_PLUS_APPENDED 1
914 #define REPEAT_WITH_Q 2
915 #define REPEAT_ZERO 3
916
917 static int
918 replace_repeat(const uschar *reptok, int reptoklen, const uschar *atom,
919 int atomlen, int firstnum, int secondnum, int special_case)
920 {
921 int i, j;
922 uschar *buf = 0;
923 int ret = 1;
924 int init_q = (firstnum == 0); /* first added char will be ? */
925 int n_q_reps = secondnum-firstnum; /* m>n, so reduce until {1,m-n} left */
926 int prefix_length = reptok - basestr; /* prefix includes first rep */
927 int suffix_length = strlen((const char *) reptok) - reptoklen; /* string after rep specifier */
928 int size = prefix_length + suffix_length;
929
930 if (firstnum > 1) { /* add room for reps 2 through firstnum */
931 size += atomlen*(firstnum-1);
932 }
933
934 /* Adjust size of buffer for special cases */
935 if (special_case == REPEAT_PLUS_APPENDED) {
936 size++; /* for the final + */
937 } else if (special_case == REPEAT_WITH_Q) {
938 size += init_q + (atomlen+1)* (n_q_reps-init_q);
939 } else if (special_case == REPEAT_ZERO) {
940 size += 2; /* just a null ERE: () */
941 }
942 if ((buf = (uschar *) malloc(size + 1)) == NULL)
943 FATAL("out of space in reg expr %.10s..", lastre);
944 memcpy(buf, basestr, prefix_length); /* copy prefix */
945 j = prefix_length;
946 if (special_case == REPEAT_ZERO) {
947 j -= atomlen;
948 buf[j++] = '(';
949 buf[j++] = ')';
950 }
951 for (i = 1; i < firstnum; i++) { /* copy x reps */
952 memcpy(&buf[j], atom, atomlen);
953 j += atomlen;
954 }
955 if (special_case == REPEAT_PLUS_APPENDED) {
956 buf[j++] = '+';
957 } else if (special_case == REPEAT_WITH_Q) {
958 if (init_q)
959 buf[j++] = '?';
960 for (i = init_q; i < n_q_reps; i++) { /* copy x? reps */
961 memcpy(&buf[j], atom, atomlen);
962 j += atomlen;
963 buf[j++] = '?';
964 }
965 }
966 memcpy(&buf[j], reptok+reptoklen, suffix_length);
967 j += suffix_length;
968 buf[j] = '\0';
969 /* free old basestr */
970 if (firstbasestr != basestr) {
971 if (basestr)
972 xfree(basestr);
973 }
974 basestr = buf;
975 prestr = buf + prefix_length;
976 if (special_case == REPEAT_ZERO) {
977 prestr -= atomlen;
978 ret++;
979 }
980 return ret;
981 }
982
983 static int repeat(const uschar *reptok, int reptoklen, const uschar *atom,
984 int atomlen, int firstnum, int secondnum)
985 {
986 /*
987 In general, the repetition specifier or "bound" is replaced here
988 by an equivalent ERE string, repeating the immediately previous atom
989 and appending ? and + as needed. Note that the first copy of the
990 atom is left in place, except in the special_case of a zero-repeat
991 (i.e., {0}).
992 */
993 if (secondnum < 0) { /* means {n,} -> repeat n-1 times followed by PLUS */
994 if (firstnum < 2) {
995 /* 0 or 1: should be handled before you get here */
996 FATAL("internal error");
997 } else {
998 return replace_repeat(reptok, reptoklen, atom, atomlen,
999 firstnum, secondnum, REPEAT_PLUS_APPENDED);
1000 }
1001 } else if (firstnum == secondnum) { /* {n} or {n,n} -> simply repeat n-1 times */
1002 if (firstnum == 0) { /* {0} or {0,0} */
1003 /* This case is unusual because the resulting
1004 replacement string might actually be SMALLER than
1005 the original ERE */
1006 return replace_repeat(reptok, reptoklen, atom, atomlen,
1007 firstnum, secondnum, REPEAT_ZERO);
1008 } else { /* (firstnum >= 1) */
1009 return replace_repeat(reptok, reptoklen, atom, atomlen,
1010 firstnum, secondnum, REPEAT_SIMPLE);
1011 }
1012 } else if (firstnum < secondnum) { /* {n,m} -> repeat n-1 times then alternate */
1013 /* x{n,m} => xx...x{1, m-n+1} => xx...x?x?x?..x? */
1014 return replace_repeat(reptok, reptoklen, atom, atomlen,
1015 firstnum, secondnum, REPEAT_WITH_Q);
1016 } else { /* Error - shouldn't be here (n>m) */
1017 FATAL("internal error");
1018 }
1019 return 0;
1020 }
1021
1022 int relex(void) /* lexical analyzer for reparse */
1023 {
1024 int c, n;
1025 int cflag;
1026 static uschar *buf = NULL;
1027 static int bufsz = 100;
1028 uschar *bp;
1029 const struct charclass *cc;
1030 int i;
1031 int num, m;
1032 bool commafound, digitfound;
1033 const uschar *startreptok;
1034 static int parens = 0;
1035
1036 rescan:
1037 starttok = prestr;
1038
1039 switch (c = *prestr++) {
1040 case '|': return OR;
1041 case '*': return STAR;
1042 case '+': return PLUS;
1043 case '?': return QUEST;
1044 case '.': return DOT;
1045 case '\0': prestr--; return '\0';
1046 case '^':
1047 case '$':
1048 return c;
1049 case '(':
1050 parens++;
1051 return c;
1052 case ')':
1053 if (parens) {
1054 parens--;
1055 return c;
1056 }
1057 /* unmatched close parenthesis; per POSIX, treat as literal */
1058 rlxval = c;
1059 return CHAR;
1060 case '\\':
1061 rlxval = quoted(&prestr);
1062 return CHAR;
1063 default:
1064 rlxval = c;
1065 return CHAR;
1066 case '[':
1067 if (buf == NULL && (buf = (uschar *) malloc(bufsz)) == NULL)
1068 FATAL("out of space in reg expr %.10s..", lastre);
1069 bp = buf;
1070 if (*prestr == '^') {
1071 cflag = 1;
1072 prestr++;
1073 }
1074 else
1075 cflag = 0;
1076 n = 2 * strlen((const char *) prestr)+1;
1077 if (!adjbuf((char **) &buf, &bufsz, n, n, (char **) &bp, "relex1"))
1078 FATAL("out of space for reg expr %.10s...", lastre);
1079 for (; ; ) {
1080 if ((c = *prestr++) == '\\') {
1081 *bp++ = '\\';
1082 if ((c = *prestr++) == '\0')
1083 FATAL("nonterminated character class %.20s...", lastre);
1084 *bp++ = c;
1085 /* } else if (c == '\n') { */
1086 /* FATAL("newline in character class %.20s...", lastre); */
1087 } else if (c == '[' && *prestr == ':') {
1088 /* POSIX char class names, Dag-Erling Smorgrav, des@ofug.org */
1089 for (cc = charclasses; cc->cc_name; cc++)
1090 if (strncmp((const char *) prestr + 1, (const char *) cc->cc_name, cc->cc_namelen) == 0)
1091 break;
1092 if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':' &&
1093 prestr[2 + cc->cc_namelen] == ']') {
1094 prestr += cc->cc_namelen + 3;
1095 /*
1096 * BUG: We begin at 1, instead of 0, since we
1097 * would otherwise prematurely terminate the
1098 * string for classes like [[:cntrl:]]. This
1099 * means that we can't match the NUL character,
1100 * not without first adapting the entire
1101 * program to track each string's length.
1102 */
1103 for (i = 1; i <= UCHAR_MAX; i++) {
1104 if (!adjbuf((char **) &buf, &bufsz, bp-buf+2, 100, (char **) &bp, "relex2"))
1105 FATAL("out of space for reg expr %.10s...", lastre);
1106 if (cc->cc_func(i)) {
1107 /* escape backslash */
1108 if (i == '\\') {
1109 *bp++ = '\\';
1110 n++;
1111 }
1112
1113 *bp++ = i;
1114 n++;
1115 }
1116 }
1117 } else
1118 *bp++ = c;
1119 } else if (c == '[' && *prestr == '.') {
1120 char collate_char;
1121 prestr++;
1122 collate_char = *prestr++;
1123 if (*prestr == '.' && prestr[1] == ']') {
1124 prestr += 2;
1125 /* Found it: map via locale TBD: for
1126 now, simply return this char. This
1127 is sufficient to pass conformance
1128 test awk.ex 156
1129 */
1130 if (*prestr == ']') {
1131 prestr++;
1132 rlxval = collate_char;
1133 return CHAR;
1134 }
1135 }
1136 } else if (c == '[' && *prestr == '=') {
1137 char equiv_char;
1138 prestr++;
1139 equiv_char = *prestr++;
1140 if (*prestr == '=' && prestr[1] == ']') {
1141 prestr += 2;
1142 /* Found it: map via locale TBD: for now
1143 simply return this char. This is
1144 sufficient to pass conformance test
1145 awk.ex 156
1146 */
1147 if (*prestr == ']') {
1148 prestr++;
1149 rlxval = equiv_char;
1150 return CHAR;
1151 }
1152 }
1153 } else if (c == '\0') {
1154 FATAL("nonterminated character class %.20s", lastre);
1155 } else if (bp == buf) { /* 1st char is special */
1156 *bp++ = c;
1157 } else if (c == ']') {
1158 *bp++ = 0;
1159 rlxstr = (uschar *) tostring((char *) buf);
1160 if (cflag == 0)
1161 return CCL;
1162 else
1163 return NCCL;
1164 } else
1165 *bp++ = c;
1166 }
1167 break;
1168 case '{':
1169 if (isdigit(*(prestr))) {
1170 num = 0; /* Process as a repetition */
1171 n = -1; m = -1;
1172 commafound = false;
1173 digitfound = false;
1174 startreptok = prestr-1;
1175 /* Remember start of previous atom here ? */
1176 } else { /* just a { char, not a repetition */
1177 rlxval = c;
1178 return CHAR;
1179 }
1180 for (; ; ) {
1181 if ((c = *prestr++) == '}') {
1182 if (commafound) {
1183 if (digitfound) { /* {n,m} */
1184 m = num;
1185 if (m < n)
1186 FATAL("illegal repetition expression: class %.20s",
1187 lastre);
1188 if (n == 0 && m == 1) {
1189 return QUEST;
1190 }
1191 } else { /* {n,} */
1192 if (n == 0)
1193 return STAR;
1194 else if (n == 1)
1195 return PLUS;
1196 }
1197 } else {
1198 if (digitfound) { /* {n} same as {n,n} */
1199 n = num;
1200 m = num;
1201 } else { /* {} */
1202 FATAL("illegal repetition expression: class %.20s",
1203 lastre);
1204 }
1205 }
1206 if (repeat(starttok, prestr-starttok, lastatom,
1207 startreptok - lastatom, n, m) > 0) {
1208 if (n == 0 && m == 0) {
1209 return ZERO;
1210 }
1211 /* must rescan input for next token */
1212 goto rescan;
1213 }
1214 /* Failed to replace: eat up {...} characters
1215 and treat like just PLUS */
1216 return PLUS;
1217 } else if (c == '\0') {
1218 FATAL("nonterminated character class %.20s",
1219 lastre);
1220 } else if (isdigit(c)) {
1221 num = 10 * num + c - '0';
1222 digitfound = true;
1223 } else if (c == ',') {
1224 if (commafound)
1225 FATAL("illegal repetition expression: class %.20s",
1226 lastre);
1227 /* looking for {n,} or {n,m} */
1228 commafound = true;
1229 n = num;
1230 digitfound = false; /* reset */
1231 num = 0;
1232 } else {
1233 FATAL("illegal repetition expression: class %.20s",
1234 lastre);
1235 }
1236 }
1237 break;
1238 }
1239 }
1240
1241 int cgoto(fa *f, int s, int c)
1242 {
1243 int *p, *q;
1244 int i, j, k;
1245
1246 assert(c == HAT || c < NCHARS);
1247 while (f->accept >= maxsetvec) { /* guessing here! */
1248 resizesetvec(__func__);
1249 }
1250 for (i = 0; i <= f->accept; i++)
1251 setvec[i] = 0;
1252 setcnt = 0;
1253 resize_state(f, s);
1254 /* compute positions of gototab[s,c] into setvec */
1255 p = f->posns[s];
1256 for (i = 1; i <= *p; i++) {
1257 if ((k = f->re[p[i]].ltype) != FINAL) {
1258 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np))
1259 || (k == DOT && c != 0 && c != HAT)
1260 || (k == ALL && c != 0)
1261 || (k == EMPTYRE && c != 0)
1262 || (k == CCL && member(c, (char *) f->re[p[i]].lval.up))
1263 || (k == NCCL && !member(c, (char *) f->re[p[i]].lval.up) && c != 0 && c != HAT)) {
1264 q = f->re[p[i]].lfollow;
1265 for (j = 1; j <= *q; j++) {
1266 if (q[j] >= maxsetvec) {
1267 resizesetvec(__func__);
1268 }
1269 if (setvec[q[j]] == 0) {
1270 setcnt++;
1271 setvec[q[j]] = 1;
1272 }
1273 }
1274 }
1275 }
1276 }
1277 /* determine if setvec is a previous state */
1278 tmpset[0] = setcnt;
1279 j = 1;
1280 for (i = f->accept; i >= 0; i--)
1281 if (setvec[i]) {
1282 tmpset[j++] = i;
1283 }
1284 resize_state(f, f->curstat > s ? f->curstat : s);
1285 /* tmpset == previous state? */
1286 for (i = 1; i <= f->curstat; i++) {
1287 p = f->posns[i];
1288 if ((k = tmpset[0]) != p[0])
1289 goto different;
1290 for (j = 1; j <= k; j++)
1291 if (tmpset[j] != p[j])
1292 goto different;
1293 /* setvec is state i */
1294 if (c != HAT)
1295 f->gototab[s][c] = i;
1296 return i;
1297 different:;
1298 }
1299
1300 /* add tmpset to current set of states */
1301 ++(f->curstat);
1302 resize_state(f, f->curstat);
1303 for (i = 0; i < NCHARS; i++)
1304 f->gototab[f->curstat][i] = 0;
1305 xfree(f->posns[f->curstat]);
1306 p = intalloc(setcnt + 1, __func__);
1307
1308 f->posns[f->curstat] = p;
1309 if (c != HAT)
1310 f->gototab[s][c] = f->curstat;
1311 for (i = 0; i <= setcnt; i++)
1312 p[i] = tmpset[i];
1313 if (setvec[f->accept])
1314 f->out[f->curstat] = 1;
1315 else
1316 f->out[f->curstat] = 0;
1317 return f->curstat;
1318 }
1319
1320
1321 void freefa(fa *f) /* free a finite automaton */
1322 {
1323 int i;
1324
1325 if (f == NULL)
1326 return;
1327 for (i = 0; i < f->state_count; i++)
1328 xfree(f->gototab[i])
1329 for (i = 0; i <= f->curstat; i++)
1330 xfree(f->posns[i]);
1331 for (i = 0; i <= f->accept; i++) {
1332 xfree(f->re[i].lfollow);
1333 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL)
1334 xfree(f->re[i].lval.np);
1335 }
1336 xfree(f->restr);
1337 xfree(f->out);
1338 xfree(f->posns);
1339 xfree(f->gototab);
1340 xfree(f);
1341 }
DragonFly BSD