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 "awk.h"
30#include "awkgram.tab.h"
31#include <ctype.h>
32#include <limits.h>
33#include <stdio.h>
34#include <stdlib.h>
35#include <string.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 \
46 case CCL: \
47 case NCCL: \
48 case CHAR: \
49 case DOT: \
50 case FINAL: \
51 case ALL:
52#define ELEAF case EMPTYRE: /* empty string in regexp */
53#define UNARY \
54 case STAR: \
55 case PLUS: \
56 case QUEST:
57
58/* encoding in tree nodes:
59 * leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL, EMPTYRE):
60 * left is index, right contains value or pointer to value
61 * unary (STAR, PLUS, QUEST): left is child, right is null
62 * binary (CAT, OR): left and right are children
63 * parent contains pointer to parent
64 */
65
66int *setvec;
67int *tmpset;
68int maxsetvec = 0;
69
70int rtok; /* next token in current re */
71int rlxval;
72static const uschar *rlxstr;
73static const uschar *prestr; /* current position in current re */
74static const uschar *lastre; /* origin of last re */
75static const uschar *lastatom; /* origin of last atom */
76static const uschar *starttok;
77static const uschar *basestr; /* starts with original, replaced during
78 * repetition processing */
79static const uschar *firstbasestr;
80
81static int setcnt;
82static int poscnt;
83
84const char *patbeg;
85int patlen;
86
87#define NFA 128 /* cache this many dynamic fa's */
88fa *fatab[NFA];
89int nfatab = 0; /* entries in fatab */
90
91extern int u8_nextlen(const char *s);
92
93/* utf-8 mechanism:
94 *
95 * for most of awk, utf-8 strings just "work", since they look like
96 * null-terminated sequences of 8-bit bytes
97 *
98 * functions like length(), index(), and substr() have to operate
99 * in units of utf-8 characters. the u8_* functions in run.c
100 * handle this
101 *
102 * regular expressions are more complicated, since the basic
103 * mechanism of the goto table used 8-bit byte indices into the
104 * gototab entries to compute the next state. unicode is a lot
105 * bigger, so the gototab entries are now structs with a character
106 * and a next state. these are sorted by code point and binary
107 * searched
108 *
109 * throughout the RE mechanism in b.c, utf-8 characters are
110 * converted to their utf-32 value. this mostly shows up in
111 * cclenter, which expands character class ranges like a-z and now
112 * alpha-omega. the size of a gototab array is still about 256
113 * this should be dynamic, but for now things work ok for a single
114 * code page of unicode, which is the most likely case
115 *
116 * the code changes are localized in run.c and b.c. i have added a
117 * handful of functions to somewhat better hide the implementation,
118 * but a lot more could be done
119 *
120 */
121
122static int entry_cmp(const void *l, const void *r);
123static int get_gototab(fa *, int, int);
124static int set_gototab(fa *, int, int, int);
125static void clear_gototab(fa *, int);
126extern int u8_rune(int *, const char *);
127
128static int *
129intalloc(size_t n, const char *f)
130{
131 int *p = (int *)calloc(n, sizeof(int));
132 if (p == NULL)
133 overflo(f);
134 return p;
135}
136
137static void
138resizesetvec(const char *f)
139{
140 if (maxsetvec == 0)
141 maxsetvec = MAXLIN;
142 else
143 maxsetvec *= 4;
144 setvec = (int *)realloc(setvec, maxsetvec * sizeof(*setvec));
145 tmpset = (int *)realloc(tmpset, maxsetvec * sizeof(*tmpset));
146 if (setvec == NULL || tmpset == NULL)
147 overflo(f);
148}
149
150static void
151resize_state(fa *f, int state)
152{
153 gtt *p;
154 uschar *p2;
155 int **p3;
156 int i, new_count;
157
158 if (++state < f->state_count)
159 return;
160
161 new_count = state + 10; /* needs to be tuned */
162
163 p = (gtt *)realloc(f->gototab, new_count * sizeof(gtt));
164 if (p == NULL)
165 goto out;
166 f->gototab = p;
167
168 p2 = (uschar *)realloc(f->out, new_count * sizeof(f->out[0]));
169 if (p2 == NULL)
170 goto out;
171 f->out = p2;
172
173 p3 = (int **)realloc(f->posns, new_count * sizeof(f->posns[0]));
174 if (p3 == NULL)
175 goto out;
176 f->posns = p3;
177
178 for (i = f->state_count; i < new_count; ++i) {
179 memset(f->gototab[i].direct, 0, sizeof(f->gototab[i].direct));
180 f->gototab[i].entries = (gtte *)calloc(NCHARS, sizeof(gtte));
181 if (f->gototab[i].entries == NULL)
182 goto out;
183 f->gototab[i].allocated = NCHARS;
184 f->gototab[i].inuse = 0;
185 f->out[i] = 0;
186 f->posns[i] = NULL;
187 }
188 f->state_count = new_count;
189 return;
190out:
191 overflo(__func__);
192}
193
194fa *
195makedfa(const char *s, bool anchor) /* returns dfa for reg expr s */
196{
197 int i, use, nuse;
198 fa *pfa;
199 static int now = 1;
200
201 if (setvec == NULL) { /* first time through any RE */
202 resizesetvec(__func__);
203 }
204
205 if (compile_time != RUNNING) /* a constant for sure */
206 return mkdfa(s, anchor);
207 for (i = 0; i < nfatab; i++) /* is it there already? */
208 if (fatab[i]->anchor == anchor && strcmp((const char *)fatab[i]->restr, s) == 0) {
209 fatab[i]->use = now++;
210 return fatab[i];
211 }
212 pfa = mkdfa(s, anchor);
213 if (nfatab < NFA) { /* room for another */
214 fatab[nfatab] = pfa;
215 fatab[nfatab]->use = now++;
216 nfatab++;
217 return pfa;
218 }
219 use = fatab[0]->use; /* replace least-recently used */
220 nuse = 0;
221 for (i = 1; i < nfatab; i++)
222 if (fatab[i]->use < use) {
223 use = fatab[i]->use;
224 nuse = i;
225 }
226 freefa(fatab[nuse]);
227 fatab[nuse] = pfa;
228 pfa->use = now++;
229 return pfa;
230}
231
232fa *
233mkdfa(const char *s, bool anchor) /* does the real work of making a dfa */
234/* anchor = true for anchored matches, else false */
235{
236 Node *p, *p1;
237 fa *f;
238
239 firstbasestr = (const uschar *)s;
240 basestr = firstbasestr;
241 p = reparse(s);
242 p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
243 /* put ALL STAR in front of reg. exp */
244 p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
245 /* put FINAL after reg. exp */
246
247 poscnt = 0;
248 penter(p1); /* enter parent pointers and leaf indices */
249 if ((f = (fa *)calloc(1, sizeof(fa) + poscnt * sizeof(rrow))) == NULL)
250 overflo(__func__);
251 f->accept = poscnt - 1; /* penter has computed number of positions in re */
252 cfoll(f, p1); /* set up follow sets */
253 freetr(p1);
254 resize_state(f, 1);
255 f->posns[0] = intalloc(*(f->re[0].lfollow), __func__);
256 f->posns[1] = intalloc(1, __func__);
257 *f->posns[1] = 0;
258 f->initstat = makeinit(f, anchor);
259 f->anchor = anchor;
260 f->restr = (uschar *)tostring(s);
261 if (firstbasestr != basestr) {
262 if (basestr)
263 xfree(basestr);
264 }
265 return f;
266}
267
268int
269makeinit(fa *f, bool anchor)
270{
271 int i, k;
272
273 f->curstat = 2;
274 f->out[2] = 0;
275 k = *(f->re[0].lfollow);
276 xfree(f->posns[2]);
277 f->posns[2] = intalloc(k + 1, __func__);
278 for (i = 0; i <= k; i++) {
279 (f->posns[2])[i] = (f->re[0].lfollow)[i];
280 }
281 if ((f->posns[2])[1] == f->accept)
282 f->out[2] = 1;
283 clear_gototab(f, 2);
284 f->curstat = cgoto(f, 2, HAT);
285 if (anchor) {
286 *f->posns[2] = k - 1; /* leave out position 0 */
287 for (i = 0; i < k; i++) {
288 (f->posns[0])[i] = (f->posns[2])[i];
289 }
290
291 f->out[0] = f->out[2];
292 if (f->curstat != 2)
293 --(*f->posns[f->curstat]);
294 }
295 return f->curstat;
296}
297
298void
299penter(Node *p) /* set up parent pointers and leaf indices */
300{
301 switch (type(p)) {
302 ELEAF
303 LEAF info(p) = poscnt;
304 poscnt++;
305 break;
306 UNARY
307 penter(left(p));
308 parent(left(p)) = p;
309 break;
310 case CAT:
311 case OR:
312 penter(left(p));
313 penter(right(p));
314 parent(left(p)) = p;
315 parent(right(p)) = p;
316 break;
317 case ZERO:
318 break;
319 default: /* cant happen */
320 FATAL("can't happen: unknown type %d in penter", type(p));
321 break;
322 }
323}
324
325void
326freetr(Node *p) /* free parse tree */
327{
328 switch (type(p)) {
329 ELEAF
330 LEAF xfree(p);
331 break;
332 UNARY
333 case ZERO:
334 freetr(left(p));
335 xfree(p);
336 break;
337 case CAT:
338 case OR:
339 freetr(left(p));
340 freetr(right(p));
341 xfree(p);
342 break;
343 default: /* cant happen */
344 FATAL("can't happen: unknown type %d in freetr", type(p));
345 break;
346 }
347}
348
349/* in the parsing of regular expressions, metacharacters like . have */
350/* to be seen literally; \056 is not a metacharacter */
351
352int
353hexstr(const uschar **pp, int max) /* find and eval hex string at pp, return new p */
354{ /* only pick up one 8-bit byte (2 chars) */
355 const uschar *p;
356 int n = 0;
357 int i;
358
359 for (i = 0, p = *pp; i < max && isxdigit(*p); i++, p++) {
360 if (isdigit((int)*p))
361 n = 16 * n + *p - '0';
362 else if (*p >= 'a' && *p <= 'f')
363 n = 16 * n + *p - 'a' + 10;
364 else if (*p >= 'A' && *p <= 'F')
365 n = 16 * n + *p - 'A' + 10;
366 }
367 *pp = p;
368 return n;
369}
370
371#define isoctdigit(c) ((c) >= '0' && (c) <= '7') /* multiple use of arg */
372
373int
374quoted(const uschar **pp) /* pick up next thing after a \\ */
375 /* and increment *pp */
376{
377 const uschar *p = *pp;
378 int c;
379
380 /* BUG: should advance by utf-8 char even if makes no sense */
381
382 switch ((c = *p++)) {
383 case 't':
384 c = '\t';
385 break;
386 case 'n':
387 c = '\n';
388 break;
389 case 'f':
390 c = '\f';
391 break;
392 case 'r':
393 c = '\r';
394 break;
395 case 'b':
396 c = '\b';
397 break;
398 case 'v':
399 c = '\v';
400 break;
401 case 'a':
402 c = '\a';
403 break;
404 case '\\':
405 c = '\\';
406 break;
407 case 'x': /* 2 hex digits follow */
408 c = hexstr(&p, 2); /* this adds a null if number is invalid */
409 break;
410 case 'u': /* unicode char number up to 8 hex digits */
411 c = hexstr(&p, 8);
412 break;
413 default:
414 if (isoctdigit(c)) { /* \d \dd \ddd */
415 int n = c - '0';
416 if (isoctdigit(*p)) {
417 n = 8 * n + *p++ - '0';
418 if (isoctdigit(*p))
419 n = 8 * n + *p++ - '0';
420 }
421 c = n;
422 }
423 }
424
425 *pp = p;
426 return c;
427}
428
429int *
430cclenter(const char *argp) /* add a character class */
431{
432 int i, c, c2;
433 int n;
434 const uschar *p = (const uschar *)argp;
435 int *bp, *retp;
436 static int *buf = NULL;
437 static int bufsz = 100;
438
439 if (buf == NULL && (buf = (int *)calloc(bufsz, sizeof(int))) == NULL)
440 FATAL("out of space for character class [%.10s...] 1", p);
441 bp = buf;
442 for (i = 0; *p != 0;) {
443 n = u8_rune(&c, (const char *)p);
444 p += n;
445 if (c == '\\') {
446 c = quoted(&p);
447 } else if (c == '-' && i > 0 && bp[-1] != 0) {
448 if (*p != 0) {
449 c = bp[-1];
450 /* c2 = *p++; */
451 n = u8_rune(&c2, (const char *)p);
452 p += n;
453 if (c2 == '\\')
454 c2 = quoted(&p); /* BUG: sets p, has to
455 * be u8 size */
456 if (c > c2) { /* empty; ignore */
457 bp--;
458 i--;
459 continue;
460 }
461 while (c < c2) {
462 if (i >= bufsz) {
463 bufsz *= 2;
464 buf = (int *)realloc(buf, bufsz * sizeof(int));
465 if (buf == NULL)
466 FATAL(
467 "out of space "
468 "for character "
469 "class "
470 "[%.10s...] 2",
471 p
472 );
473 bp = buf + i;
474 }
475 *bp++ = ++c;
476 i++;
477 }
478 continue;
479 }
480 }
481 if (i >= bufsz) {
482 bufsz *= 2;
483 buf = (int *)realloc(buf, bufsz * sizeof(int));
484 if (buf == NULL)
485 FATAL(
486 "out of space for character class "
487 "[%.10s...] 2",
488 p
489 );
490 bp = buf + i;
491 }
492 *bp++ = c;
493 i++;
494 }
495 *bp = 0;
496 /* dprintf("cclenter: in = |%s|, out = |%s|\n", op, buf); BUG: cant
497 * print array of int */
498 /* xfree(op); BUG: what are we freeing here? */
499 retp = (int *)calloc(bp - buf + 1, sizeof(int));
500 for (i = 0; i < bp - buf + 1; i++)
501 retp[i] = buf[i];
502 return retp;
503}
504
505void
506overflo(const char *s)
507{
508 FATAL("regular expression too big: out of space in %.30s...", s);
509}
510
511void
512cfoll(fa *f, Node *v) /* enter follow set of each leaf of vertex v into
513 * lfollow[leaf] */
514{
515 int i;
516 int *p;
517
518 switch (type(v)) {
519 ELEAF
520 LEAF f->re[info(v)].ltype = type(v);
521 f->re[info(v)].lval.np = right(v);
522 while (f->accept >= maxsetvec) { /* guessing here! */
523 resizesetvec(__func__);
524 }
525 for (i = 0; i <= f->accept; i++)
526 setvec[i] = 0;
527 setcnt = 0;
528 follow(v); /* computes setvec and setcnt */
529 p = intalloc(setcnt + 1, __func__);
530 f->re[info(v)].lfollow = p;
531 *p = setcnt;
532 for (i = f->accept; i >= 0; i--)
533 if (setvec[i] == 1)
534 *++p = i;
535 break;
536 UNARY
537 cfoll(f, left(v));
538 break;
539 case CAT:
540 case OR:
541 cfoll(f, left(v));
542 cfoll(f, right(v));
543 break;
544 case ZERO:
545 break;
546 default: /* cant happen */
547 FATAL("can't happen: unknown type %d in cfoll", type(v));
548 }
549}
550
551int
552first(Node *p) /* collects initially active leaves of p into setvec */
553 /* returns 0 if p matches empty string */
554{
555 int b, lp;
556
557 switch (type(p)) {
558 ELEAF
559 LEAF lp = info(p); /* look for high-water mark of subscripts */
560 while (setcnt >= maxsetvec || lp >= maxsetvec) { /* guessing here! */
561 resizesetvec(__func__);
562 }
563 if (type(p) == EMPTYRE) {
564 setvec[lp] = 0;
565 return (0);
566 }
567 if (setvec[lp] != 1) {
568 setvec[lp] = 1;
569 setcnt++;
570 }
571 if (type(p) == CCL && (*(int *)right(p)) == 0)
572 return (0); /* empty CCL */
573 return (1);
574 case PLUS:
575 if (first(left(p)) == 0)
576 return (0);
577 return (1);
578 case STAR:
579 case QUEST:
580 first(left(p));
581 return (0);
582 case CAT:
583 if (first(left(p)) == 0 && first(right(p)) == 0)
584 return (0);
585 return (1);
586 case OR:
587 b = first(right(p));
588 if (first(left(p)) == 0 || b == 0)
589 return (0);
590 return (1);
591 case ZERO:
592 return 0;
593 }
594 FATAL("can't happen: unknown type %d in first", type(p)); /* cant happen */
595 return (-1);
596}
597
598void
599follow(Node *v) /* collects leaves that can follow v into setvec */
600{
601 Node *p;
602
603 if (type(v) == FINAL)
604 return;
605 p = parent(v);
606 switch (type(p)) {
607 case STAR:
608 case PLUS:
609 first(v);
610 follow(p);
611 return;
612
613 case OR:
614 case QUEST:
615 follow(p);
616 return;
617
618 case CAT:
619 if (v == left(p)) { /* v is left child of p */
620 if (first(right(p)) == 0) {
621 follow(p);
622 return;
623 }
624 } else /* v is right child */
625 follow(p);
626 return;
627 }
628}
629
630int
631member(int c, int *sarg) /* is c in s? */
632{
633 int *s = (int *)sarg;
634
635 while (*s)
636 if (c == *s++)
637 return (1);
638 return (0);
639}
640
641static void
642resize_gototab(fa *f, int state)
643{
644 size_t new_size = f->gototab[state].allocated * 2;
645 gtte *p = (gtte *)realloc(f->gototab[state].entries, new_size * sizeof(gtte));
646 if (p == NULL)
647 overflo(__func__);
648
649 /* need to initialize the new memory to zero */
650 size_t orig_size = f->gototab[state].allocated; /* 2nd half of new mem is this size */
651 memset(p + orig_size, 0, orig_size * sizeof(gtte)); /* clean it out */
652
653 f->gototab[state].allocated = new_size; /* update gototab info */
654 f->gototab[state].entries = p;
655}
656
657static int
658get_gototab(fa *f, int state, int ch) /* hide gototab implementation */
659{
660 gtte key;
661 gtte *item;
662
663 if ((unsigned)ch < GOTO_DIRECT)
664 return f->gototab[state].direct[ch];
665
666 key.ch = ch;
667 key.state = 0; /* irrelevant */
668 item = (gtte *)bsearch(
669 &key, f->gototab[state].entries, f->gototab[state].inuse, sizeof(gtte), entry_cmp
670 );
671
672 if (item == NULL)
673 return 0;
674 else
675 return item->state;
676}
677
678static int
679entry_cmp(const void *l, const void *r)
680{
681 const gtte *left, *right;
682
683 left = (const gtte *)l;
684 right = (const gtte *)r;
685
686 return left->ch - right->ch;
687}
688
689static int
690set_gototab(fa *f, int state, int ch, int val) /* hide gototab implementation */
691{
692 if ((unsigned)ch < GOTO_DIRECT) {
693 f->gototab[state].direct[ch] = val;
694 return val;
695 }
696
697 if (f->gototab[state].inuse == 0) {
698 f->gototab[state].entries[0].ch = ch;
699 f->gototab[state].entries[0].state = val;
700 f->gototab[state].inuse++;
701 return val;
702 } else if ((unsigned)ch > f->gototab[state].entries[f->gototab[state].inuse - 1].ch) {
703 /* not seen yet, insert and return */
704 gtt *tab = &f->gototab[state];
705 if (tab->inuse + 1 >= tab->allocated)
706 resize_gototab(f, state);
707
708 f->gototab[state].entries[f->gototab[state].inuse].ch = ch;
709 f->gototab[state].entries[f->gototab[state].inuse].state = val;
710 f->gototab[state].inuse++;
711 return val;
712 } else {
713 /* maybe we have it, maybe we dont */
714 gtte key;
715 gtte *item;
716
717 key.ch = ch;
718 key.state = 0; /* irrelevant */
719 item = (gtte *)bsearch(
720 &key, f->gototab[state].entries, f->gototab[state].inuse, sizeof(gtte), entry_cmp
721 );
722
723 if (item != NULL) {
724 /* we have it, update state and return */
725 item->state = val;
726 return item->state;
727 }
728 /* otherwise, fall through to insert and reallocate */
729 }
730
731 gtt *tab = &f->gototab[state];
732 if (tab->inuse + 1 >= tab->allocated)
733 resize_gototab(f, state);
734 f->gototab[state].entries[tab->inuse].ch = ch;
735 f->gototab[state].entries[tab->inuse].state = val;
736 ++tab->inuse;
737
738 qsort(f->gototab[state].entries, f->gototab[state].inuse, sizeof(gtte), entry_cmp);
739
740 return val; /* not used anywhere at the moment */
741}
742
743static void
744clear_gototab(fa *f, int state)
745{
746 memset(f->gototab[state].direct, 0, sizeof(f->gototab[state].direct));
747 memset(f->gototab[state].entries, 0, f->gototab[state].allocated * sizeof(gtte));
748 f->gototab[state].inuse = 0;
749}
750
751int
752match(fa *f, const char *p0) /* shortest match ? */
753{
754 int s, ns;
755 int n;
756 int rune;
757 const uschar *p = (const uschar *)p0;
758
759 /* return pmatch(f, p0); does it matter whether longest or shortest? */
760
761 s = f->initstat;
762 assert(s < f->state_count);
763
764 if (f->out[s])
765 return (1);
766 do {
767 /* assert(*p < NCHARS); */
768 n = u8_rune(&rune, (const char *)p);
769 if ((ns = get_gototab(f, s, rune)) != 0)
770 s = ns;
771 else
772 s = cgoto(f, s, rune);
773 if (f->out[s])
774 return (1);
775 if (*p == 0)
776 break;
777 p += n;
778 } while (1); /* was *p++ != 0 */
779 return (0);
780}
781
782int
783pmatch(fa *f, const char *p0) /* longest match, for sub */
784{
785 int s, ns;
786 int n;
787 int rune;
788 const uschar *p = (const uschar *)p0;
789 const uschar *q;
790
791 s = f->initstat;
792 assert(s < f->state_count);
793
794 patbeg = (const char *)p;
795 patlen = -1;
796 do {
797 q = p;
798 do {
799 if (f->out[s]) /* final state */
800 patlen = q - p;
801 /* assert(*q < NCHARS); */
802 n = u8_rune(&rune, (const char *)q);
803 if ((ns = get_gototab(f, s, rune)) != 0)
804 s = ns;
805 else
806 s = cgoto(f, s, rune);
807
808 assert(s < f->state_count);
809
810 if (s == 1) { /* no transition */
811 if (patlen >= 0) {
812 patbeg = (const char *)p;
813 return (1);
814 } else
815 goto nextin; /* no match */
816 }
817 if (*q == 0)
818 break;
819 q += n;
820 } while (1);
821 q++; /* was *q++ */
822 if (f->out[s])
823 patlen = q - p - 1; /* dont count $ */
824 if (patlen >= 0) {
825 patbeg = (const char *)p;
826 return (1);
827 }
828 nextin:
829 s = 2;
830 if (*p == 0)
831 break;
832 n = u8_rune(&rune, (const char *)p);
833 p += n;
834 } while (1); /* was *p++ */
835 return (0);
836}
837
838int
839nematch(fa *f, const char *p0) /* non-empty match, for sub */
840{
841 int s, ns;
842 int n;
843 int rune;
844 const uschar *p = (const uschar *)p0;
845 const uschar *q;
846
847 s = f->initstat;
848 assert(s < f->state_count);
849
850 patbeg = (const char *)p;
851 patlen = -1;
852 while (*p) {
853 q = p;
854 do {
855 if (f->out[s]) /* final state */
856 patlen = q - p;
857 /* assert(*q < NCHARS); */
858 n = u8_rune(&rune, (const char *)q);
859 if ((ns = get_gototab(f, s, rune)) != 0)
860 s = ns;
861 else
862 s = cgoto(f, s, rune);
863 if (s == 1) { /* no transition */
864 if (patlen > 0) {
865 patbeg = (const char *)p;
866 return (1);
867 } else
868 goto nnextin; /* no nonempty match */
869 }
870 if (*q == 0)
871 break;
872 q += n;
873 } while (1);
874 q++;
875 if (f->out[s])
876 patlen = q - p - 1; /* dont count $ */
877 if (patlen > 0) {
878 patbeg = (const char *)p;
879 return (1);
880 }
881 nnextin:
882 s = 2;
883 p++;
884 }
885 return (0);
886}
887
888/*
889 * NAME
890 * fnematch
891 *
892 * DESCRIPTION
893 * a stream-fed version of nematch which transfers characters to a
894 * null-terminated buffer. all characters up to and including the last
895 * character of the matching text or EOF are placed in the buffer. if
896 * a match is found, patbeg and patlen are set appropriately
897 *
898 * RETURN VALUES
899 * false no match found
900 * true match found
901 */
902
903bool
904fnematch(fa *pfa, FILE *f, char **pbuf, int *pbufsize, int quantum)
905{
906 char *i, *j, *k, *buf = *pbuf;
907 int bufsize = *pbufsize;
908 int c, n, ns, s;
909
910 s = pfa->initstat;
911 patlen = 0;
912
913 /*
914 * buf <= i <= j <= k <= buf+bufsize
915 *
916 * i: origin of active substring
917 * j: current character
918 * k: destination of the next getc
919 */
920
921 i = j = k = buf;
922
923 do {
924 /*
925 * call u8_rune with at least awk_mb_cur_max ahead in
926 * the buffer until EOF interferes
927 */
928 if (k - j < (int)awk_mb_cur_max) {
929 if (k + awk_mb_cur_max > buf + bufsize) {
930 char *obuf = buf;
931 adjbuf((char **)&buf, &bufsize, bufsize + awk_mb_cur_max, quantum, 0, "fnematch");
932
933 /* buf resized, maybe moved. update pointers */
934 *pbufsize = bufsize;
935 if (obuf != buf) {
936 i = buf + (i - obuf);
937 j = buf + (j - obuf);
938 k = buf + (k - obuf);
939 *pbuf = buf;
940 if (patlen)
941 patbeg = buf + (patbeg - obuf);
942 }
943 }
944 for (n = awk_mb_cur_max; n > 0; n--) {
945 *k++ = (c = getc(f)) != EOF ? c : 0;
946 if (c == EOF) {
947 if (ferror(f))
948 FATAL("fnematch: getc error");
949 break;
950 }
951 }
952 }
953
954 j += u8_rune(&c, j);
955
956 if ((ns = get_gototab(pfa, s, c)) != 0)
957 s = ns;
958 else
959 s = cgoto(pfa, s, c);
960
961 if (pfa->out[s]) { /* final state */
962 patbeg = i;
963 patlen = j - i;
964 if (c == 0) /* dont count $ */
965 patlen--;
966 }
967
968 if (c && s != 1)
969 continue; /* origin i still viable, next j */
970 if (patlen)
971 break; /* best match found */
972
973 /* no match at origin i, next i and start over */
974 i += u8_rune(&c, i);
975 if (c == 0)
976 break; /* no match */
977 j = i;
978 s = 2;
979 } while (1);
980
981 if (patlen) {
982 /*
983 * under no circumstances is the last character fed to
984 * the automaton part of the match. it is eof's nullbyte,
985 * or it sent the automaton into a state with no further
986 * transitions available (s==1), or both. room for a
987 * terminating nullbyte is guaranteed
988 *
989 * ungetc any chars after the end of matching text
990 * (except for eof's nullbyte, if present) and null
991 * terminate the buffer
992 */
993 do
994 if (*--k && ungetc(*k, f) == EOF)
995 FATAL("unable to ungetc '%c'", *k);
996 while (k > patbeg + patlen);
997 *k = '\0';
998 return true;
999 } else
1000 return false;
1001}
1002
1003Node *
1004reparse(const char *p) /* parses regular expression pointed to by p */
1005{ /* uses relex() to scan regular expression */
1006 Node *np;
1007
1008 DPRINTF("reparse <%s>\n", p);
1009 lastre = prestr = (const uschar *)p; /* prestr points to string to be parsed */
1010 rtok = relex();
1011 /* GNU compatibility: an empty regexp matches anything */
1012 if (rtok == '\0') {
1013 /* fatal("empty regular expression"); previous */
1014 return (op2(EMPTYRE, NIL, NIL));
1015 }
1016 np = regexp();
1017 if (rtok != '\0')
1018 FATAL("syntax error in regular expression %s at %s", lastre, prestr);
1019 return (np);
1020}
1021
1022Node *
1023regexp(void) /* top-level parse of reg expr */
1024{
1025 return (alt(concat(primary())));
1026}
1027
1028Node *
1029primary(void)
1030{
1031 Node *np;
1032 int savelastatom;
1033
1034 switch (rtok) {
1035 case CHAR:
1036 lastatom = starttok;
1037 np = op2(CHAR, NIL, itonp(rlxval));
1038 rtok = relex();
1039 return (unary(np));
1040 case ALL:
1041 rtok = relex();
1042 return (unary(op2(ALL, NIL, NIL)));
1043 case EMPTYRE:
1044 rtok = relex();
1045 return (unary(op2(EMPTYRE, NIL, NIL)));
1046 case DOT:
1047 lastatom = starttok;
1048 rtok = relex();
1049 return (unary(op2(DOT, NIL, NIL)));
1050 case CCL:
1051 np = op2(CCL, NIL, (Node *)cclenter((const char *)rlxstr));
1052 lastatom = starttok;
1053 rtok = relex();
1054 return (unary(np));
1055 case NCCL:
1056 np = op2(NCCL, NIL, (Node *)cclenter((const char *)rlxstr));
1057 lastatom = starttok;
1058 rtok = relex();
1059 return (unary(np));
1060 case '^':
1061 rtok = relex();
1062 return (unary(op2(CHAR, NIL, itonp(HAT))));
1063 case '$':
1064 rtok = relex();
1065 return (unary(op2(CHAR, NIL, NIL)));
1066 case '(':
1067 lastatom = starttok;
1068 savelastatom = starttok - basestr; /* retain over recursion */
1069 rtok = relex();
1070 if (rtok == ')') { /* special pleading for () */
1071 rtok = relex();
1072 return unary(op2(CCL, NIL, (Node *)cclenter("")));
1073 }
1074 np = regexp();
1075 if (rtok == ')') {
1076 lastatom = basestr + savelastatom; /* restore */
1077 rtok = relex();
1078 return (unary(np));
1079 } else {
1080 FATAL("syntax error in regular expression %s at %s", lastre, prestr);
1081 break;
1082 }
1083 default:
1084 FATAL("illegal primary in regular expression %s at %s", lastre, prestr);
1085 }
1086 return 0; /* NOTREACHED */
1087}
1088
1089Node *
1090concat(Node *np)
1091{
1092 switch (rtok) {
1093 case CHAR:
1094 case DOT:
1095 case ALL:
1096 case CCL:
1097 case NCCL:
1098 case '$':
1099 case '(':
1100 return (concat(op2(CAT, np, primary())));
1101 case EMPTYRE:
1102 rtok = relex();
1103 return (concat(op2(CAT, op2(CCL, NIL, (Node *)cclenter("")), primary())));
1104 }
1105 return (np);
1106}
1107
1108Node *
1109alt(Node *np)
1110{
1111 if (rtok == OR) {
1112 rtok = relex();
1113 return (alt(op2(OR, np, concat(primary()))));
1114 }
1115 return (np);
1116}
1117
1118Node *
1119unary(Node *np)
1120{
1121 switch (rtok) {
1122 case STAR:
1123 rtok = relex();
1124 return (unary(op2(STAR, np, NIL)));
1125 case PLUS:
1126 rtok = relex();
1127 return (unary(op2(PLUS, np, NIL)));
1128 case QUEST:
1129 rtok = relex();
1130 return (unary(op2(QUEST, np, NIL)));
1131 case ZERO:
1132 rtok = relex();
1133 return (unary(op2(ZERO, np, NIL)));
1134 default:
1135 return (np);
1136 }
1137}
1138
1139/*
1140 * character class definitions conformant to the POSIX locale as
1141 * defined in IEEE P1003.1 draft 7 of june 2001, assuming the source
1142 * and operating character sets are both ASCII (ISO646) or supersets
1143 * thereof
1144 *
1145 * note that to avoid overflowing the temporary buffer used in
1146 * relex(), the expanded character class (prior to range expansion)
1147 * must be less than twice the size of their full name
1148 */
1149
1150/* because isblank doesnt show up in any of the header files on any
1151 * system i use, its defined here. if some other locale has a richer
1152 * definition of "blank", define HAS_ISBLANK and provide your own
1153 * version
1154 * the parentheses here are an attempt to find a path through the maze
1155 * of macro definition and/or function and/or version provided. thanks
1156 * to nelson beebe for the suggestion; let's see if it works everywhere
1157 */
1158
1159/* #define HAS_ISBLANK */
1160#ifndef HAS_ISBLANK
1161
1162int(xisblank)(int c)
1163{
1164 return c == ' ' || c == '\t';
1165}
1166
1167#endif
1168
1169static const struct charclass {
1170 const char *cc_name;
1171 int cc_namelen;
1172 int (*cc_func)(int);
1173} charclasses[] = {
1174 {"alnum", 5, isalnum},
1175 {"alpha", 5, isalpha},
1176#ifndef HAS_ISBLANK
1177 {"blank", 5, xisblank},
1178#else
1179 {"blank", 5, isblank},
1180#endif
1181 {"cntrl", 5, iscntrl},
1182 {"digit", 5, isdigit},
1183 {"graph", 5, isgraph},
1184 {"lower", 5, islower},
1185 {"print", 5, isprint},
1186 {"punct", 5, ispunct},
1187 {"space", 5, isspace},
1188 {"upper", 5, isupper},
1189 {"xdigit", 6, isxdigit},
1190 {NULL, 0, NULL},
1191};
1192
1193#define REPEAT_SIMPLE 0
1194#define REPEAT_PLUS_APPENDED 1
1195#define REPEAT_WITH_Q 2
1196#define REPEAT_ZERO 3
1197
1198static int
1199replace_repeat(
1200 const uschar *reptok,
1201 int reptoklen,
1202 const uschar *atom,
1203 int atomlen,
1204 int firstnum,
1205 int secondnum,
1206 int special_case
1207)
1208{
1209 int i, j;
1210 uschar *buf = 0;
1211 int ret = 1;
1212 int init_q = (firstnum == 0); /* first added char will be ? */
1213 int n_q_reps = secondnum - firstnum; /* m>n, so reduce until {1,m-n} left */
1214 int prefix_length = reptok - basestr; /* prefix includes first rep
1215 */
1216 int suffix_length = strlen((const char *)reptok) - reptoklen; /* string after rep specifier */
1217 int size = prefix_length + suffix_length;
1218
1219 if (firstnum > 1) { /* add room for reps 2 through firstnum */
1220 size += atomlen * (firstnum - 1);
1221 }
1222
1223 /* adjust size of buffer for special cases */
1224 if (special_case == REPEAT_PLUS_APPENDED) {
1225 size++; /* for the final + */
1226 } else if (special_case == REPEAT_WITH_Q) {
1227 size += init_q + (atomlen + 1) * (n_q_reps - init_q);
1228 } else if (special_case == REPEAT_ZERO) {
1229 size += 2; /* just a null ERE: () */
1230 }
1231 if ((buf = (uschar *)malloc(size + 1)) == NULL)
1232 FATAL("out of space in reg expr %.10s..", lastre);
1233 memcpy(buf, basestr, prefix_length); /* copy prefix */
1234 j = prefix_length;
1235 if (special_case == REPEAT_ZERO) {
1236 j -= atomlen;
1237 buf[j++] = '(';
1238 buf[j++] = ')';
1239 }
1240 for (i = 1; i < firstnum; i++) { /* copy x reps */
1241 memcpy(&buf[j], atom, atomlen);
1242 j += atomlen;
1243 }
1244 if (special_case == REPEAT_PLUS_APPENDED) {
1245 buf[j++] = '+';
1246 } else if (special_case == REPEAT_WITH_Q) {
1247 if (init_q)
1248 buf[j++] = '?';
1249 for (i = init_q; i < n_q_reps; i++) { /* copy x? reps */
1250 memcpy(&buf[j], atom, atomlen);
1251 j += atomlen;
1252 buf[j++] = '?';
1253 }
1254 }
1255 memcpy(&buf[j], reptok + reptoklen, suffix_length);
1256 j += suffix_length;
1257 buf[j] = '\0';
1258 /* free old basestr */
1259 if (firstbasestr != basestr) {
1260 if (basestr)
1261 xfree(basestr);
1262 }
1263 basestr = buf;
1264 prestr = buf + prefix_length;
1265 if (special_case == REPEAT_ZERO) {
1266 prestr -= atomlen;
1267 ret++;
1268 }
1269 return ret;
1270}
1271
1272static int
1273repeat(
1274 const uschar *reptok,
1275 int reptoklen,
1276 const uschar *atom,
1277 int atomlen,
1278 int firstnum,
1279 int secondnum
1280)
1281{
1282 if (atom == NULL)
1283 return 0;
1284
1285 /*
1286 * in general, the repetition specifier or "bound" is replaced here
1287 * by an equivalent ERE string, repeating the immediately previous atom
1288 * and appending ? and + as needed. note that the first copy of the
1289 * atom is left in place, except in the special_case of a zero-repeat
1290 * (i.e., {0})
1291 */
1292 if (secondnum < 0) { /* means {n,} -> repeat n-1 times followed by PLUS */
1293 if (firstnum < 2) {
1294 /* 0 or 1: should be handled before you get here */
1295 FATAL("internal error");
1296 } else {
1297 return replace_repeat(
1298 reptok, reptoklen, atom, atomlen, firstnum, secondnum, REPEAT_PLUS_APPENDED
1299 );
1300 }
1301 } else if (firstnum == secondnum) { /* {n} or {n,n} -> simply repeat n-1 times */
1302 if (firstnum == 0) { /* {0} or {0,0} */
1303 /* this case is unusual because the resulting
1304 * replacement string might actually be SMALLER than
1305 * the original ERE */
1306 return replace_repeat(reptok, reptoklen, atom, atomlen, firstnum, secondnum, REPEAT_ZERO);
1307 } else { /* (firstnum >= 1) */
1308 return replace_repeat(reptok, reptoklen, atom, atomlen, firstnum, secondnum, REPEAT_SIMPLE);
1309 }
1310 } else if (firstnum < secondnum) { /* {n,m} -> repeat n-1 times then alternate */
1311 /* x{n,m} => xx...x{1, m-n+1} => xx...x?x?x?..x? */
1312 return replace_repeat(reptok, reptoklen, atom, atomlen, firstnum, secondnum, REPEAT_WITH_Q);
1313 } else { /* error - shouldnt be here (n>m) */
1314 FATAL("internal error");
1315 }
1316 return 0;
1317}
1318
1319int
1320relex(void) /* lexical analyzer for reparse */
1321{
1322 int c, n;
1323 int cflag;
1324 static uschar *buf = NULL;
1325 static int bufsz = 100;
1326 uschar *bp;
1327 const struct charclass *cc;
1328 int i;
1329 int num, m;
1330 bool commafound, digitfound;
1331 const uschar *startreptok;
1332 static int parens = 0;
1333
1334rescan:
1335 starttok = prestr;
1336
1337 if ((n = u8_rune(&rlxval, (const char *)prestr)) > 1) {
1338 prestr += n;
1339 starttok = prestr;
1340 return CHAR;
1341 }
1342
1343 switch (c = *prestr++) {
1344 case '|':
1345 return OR;
1346 case '*':
1347 return STAR;
1348 case '+':
1349 return PLUS;
1350 case '?':
1351 return QUEST;
1352 case '.':
1353 return DOT;
1354 case '\0':
1355 prestr--;
1356 return '\0';
1357 case '^':
1358 case '$':
1359 return c;
1360 case '(':
1361 parens++;
1362 return c;
1363 case ')':
1364 if (parens) {
1365 parens--;
1366 return c;
1367 }
1368 /* unmatched close parenthesis; per POSIX, treat as literal */
1369 rlxval = c;
1370 return CHAR;
1371 case '\\':
1372 rlxval = quoted(&prestr);
1373 return CHAR;
1374 default:
1375 rlxval = c;
1376 return CHAR;
1377 case '[':
1378 if (buf == NULL && (buf = (uschar *)malloc(bufsz)) == NULL)
1379 FATAL("out of space in reg expr %.10s..", lastre);
1380 bp = buf;
1381 if (*prestr == '^') {
1382 cflag = 1;
1383 prestr++;
1384 } else
1385 cflag = 0;
1386 n = 5 * strlen((const char *)prestr) + 1; /* BUG: was 2. what value? */
1387 if (!adjbuf((char **)&buf, &bufsz, n, n, (char **)&bp, "relex1"))
1388 FATAL("out of space for reg expr %.10s...", lastre);
1389 for (;;) {
1390 if ((n = u8_rune(&rlxval, (const char *)prestr)) > 1) {
1391 for (i = 0; i < n; i++)
1392 *bp++ = *prestr++;
1393 continue;
1394 }
1395 if ((c = *prestr++) == '\\') {
1396 *bp++ = '\\';
1397 if ((c = *prestr++) == '\0')
1398 FATAL(
1399 "nonterminated character class "
1400 "%.20s...",
1401 lastre
1402 );
1403 *bp++ = c;
1404 /* } else if (c == '\n') { */
1405 /* fatal("newline in character class
1406 * %.20s...", lastre); */
1407 } else if (c == '[' && *prestr == ':') {
1408 /* POSIX char class names, dag-erling smorgrav,
1409 * des@ofug.org */
1410 for (cc = charclasses; cc->cc_name; cc++)
1411 if (strncmp((const char *)prestr + 1, (const char *)cc->cc_name, cc->cc_namelen) == 0)
1412 break;
1413 if (cc->cc_name != NULL && prestr[1 + cc->cc_namelen] == ':'
1414 && prestr[2 + cc->cc_namelen] == ']') {
1415 prestr += cc->cc_namelen + 3;
1416 /*
1417 * BUG: we begin at 1, instead of 0,
1418 * since we would otherwise prematurely
1419 * terminate the string for classes like
1420 * [[:cntrl:]]. this means that we cant
1421 * match the NUL character, not without
1422 * first adapting the entire program to
1423 * track each string's length
1424 */
1425 for (i = 1; i <= UCHAR_MAX; i++) {
1426 if (!adjbuf((char **)&buf, &bufsz, bp - buf + 2, 100, (char **)&bp, "relex2"))
1427 FATAL(
1428 "out of space "
1429 "for reg expr "
1430 "%.10s...",
1431 lastre
1432 );
1433 if (cc->cc_func(i)) {
1434 /* escape backslash */
1435 if (i == '\\') {
1436 *bp++ = '\\';
1437 n++;
1438 }
1439
1440 *bp++ = i;
1441 n++;
1442 }
1443 }
1444 } else
1445 *bp++ = c;
1446 } else if (c == '[' && *prestr == '.') {
1447 char collate_char;
1448 prestr++;
1449 collate_char = *prestr++;
1450 if (*prestr == '.' && prestr[1] == ']') {
1451 prestr += 2;
1452 /* found it: map via locale TBD: for
1453 * now, simply return this char. this
1454 * is sufficient to pass conformance
1455 * test awk.ex 156
1456 */
1457 if (*prestr == ']') {
1458 prestr++;
1459 rlxval = collate_char;
1460 return CHAR;
1461 }
1462 }
1463 } else if (c == '[' && *prestr == '=') {
1464 char equiv_char;
1465 prestr++;
1466 equiv_char = *prestr++;
1467 if (*prestr == '=' && prestr[1] == ']') {
1468 prestr += 2;
1469 /* found it: map via locale TBD: for now
1470 * simply return this char. this is
1471 * sufficient to pass conformance test
1472 * awk.ex 156
1473 */
1474 if (*prestr == ']') {
1475 prestr++;
1476 rlxval = equiv_char;
1477 return CHAR;
1478 }
1479 }
1480 } else if (c == '\0') {
1481 FATAL("nonterminated character class %.20s", lastre);
1482 } else if (bp == buf) { /* 1st char is special */
1483 *bp++ = c;
1484 } else if (c == ']') {
1485 *bp++ = 0;
1486 rlxstr = (uschar *)tostring((char *)buf);
1487 if (cflag == 0)
1488 return CCL;
1489 else
1490 return NCCL;
1491 } else
1492 *bp++ = c;
1493 }
1494 break;
1495 case '{':
1496 if (isdigit((int)*(prestr))) {
1497 num = 0; /* process as a repetition */
1498 n = -1;
1499 m = -1;
1500 commafound = false;
1501 digitfound = false;
1502 startreptok = prestr - 1;
1503 /* remember start of previous atom here ? */
1504 } else { /* just a { char, not a repetition */
1505 rlxval = c;
1506 return CHAR;
1507 }
1508 for (;;) {
1509 if ((c = *prestr++) == '}') {
1510 if (commafound) {
1511 if (digitfound) { /* {n,m} */
1512 m = num;
1513 if (m < n)
1514 FATAL(
1515 "illegal "
1516 "repetition "
1517 "expression: "
1518 "class %.20s",
1519 lastre
1520 );
1521 if (n == 0 && m == 1) {
1522 return QUEST;
1523 }
1524 } else { /* {n,} */
1525 if (n == 0)
1526 return STAR;
1527 else if (n == 1)
1528 return PLUS;
1529 }
1530 } else {
1531 if (digitfound) { /* {n} same as {n,n}
1532 */
1533 n = num;
1534 m = num;
1535 } else { /* {} */
1536 FATAL(
1537 "illegal repetition "
1538 "expression: class %.20s",
1539 lastre
1540 );
1541 }
1542 }
1543 if (repeat(starttok, prestr - starttok, lastatom, startreptok - lastatom, n, m) > 0) {
1544 if (n == 0 && m == 0) {
1545 return ZERO;
1546 }
1547 /* must rescan input for next token */
1548 goto rescan;
1549 }
1550 /* failed to replace: eat up {...} characters
1551 * and treat like just PLUS */
1552 return PLUS;
1553 } else if (c == '\0') {
1554 FATAL("nonterminated character class %.20s", lastre);
1555 } else if (isdigit(c)) {
1556 num = 10 * num + c - '0';
1557 if (num > 255)
1558 FATAL(
1559 "repetition count %.20s too "
1560 "large",
1561 lastre
1562 );
1563 digitfound = true;
1564 } else if (c == ',') {
1565 if (commafound)
1566 FATAL(
1567 "illegal repetition expression: "
1568 "class %.20s",
1569 lastre
1570 );
1571 /* looking for {n,} or {n,m} */
1572 commafound = true;
1573 n = num;
1574 digitfound = false; /* reset */
1575 num = 0;
1576 } else {
1577 FATAL(
1578 "illegal repetition expression: class "
1579 "%.20s",
1580 lastre
1581 );
1582 }
1583 }
1584 break;
1585 }
1586}
1587
1588int
1589cgoto(fa *f, int s, int c)
1590{
1591 int *p, *q;
1592 int i, j, k;
1593
1594 /* assert(c == HAT || c < NCHARS); BUG: seg fault if disable test */
1595 while (f->accept >= maxsetvec) { /* guessing here! */
1596 resizesetvec(__func__);
1597 }
1598 for (i = 0; i <= f->accept; i++)
1599 setvec[i] = 0;
1600 setcnt = 0;
1601 resize_state(f, s);
1602 /* compute positions of gototab[s,c] into setvec */
1603 p = f->posns[s];
1604 for (i = 1; i <= *p; i++) {
1605 if ((k = f->re[p[i]].ltype) != FINAL) {
1606 if ((k == CHAR && c == ptoi(f->re[p[i]].lval.np)) || (k == DOT && c != 0 && c != HAT)
1607 || (k == ALL && c != 0) || (k == EMPTYRE && c != 0)
1608 || (k == CCL && member(c, (int *)f->re[p[i]].lval.rp))
1609 || (k == NCCL && !member(c, (int *)f->re[p[i]].lval.rp) && c != 0 && c != HAT)) {
1610 q = f->re[p[i]].lfollow;
1611 for (j = 1; j <= *q; j++) {
1612 if (q[j] >= maxsetvec) {
1613 resizesetvec(__func__);
1614 }
1615 if (setvec[q[j]] == 0) {
1616 setcnt++;
1617 setvec[q[j]] = 1;
1618 }
1619 }
1620 }
1621 }
1622 }
1623 /* determine if setvec is a previous state */
1624 tmpset[0] = setcnt;
1625 j = 1;
1626 for (i = f->accept; i >= 0; i--)
1627 if (setvec[i]) {
1628 tmpset[j++] = i;
1629 }
1630 resize_state(f, f->curstat > s ? f->curstat : s);
1631 /* tmpset == previous state? */
1632 for (i = 1; i <= f->curstat; i++) {
1633 p = f->posns[i];
1634 if ((k = tmpset[0]) != p[0])
1635 goto different;
1636 for (j = 1; j <= k; j++)
1637 if (tmpset[j] != p[j])
1638 goto different;
1639 /* setvec is state i */
1640 if (c != HAT)
1641 set_gototab(f, s, c, i);
1642 return i;
1643 different:;
1644 }
1645
1646 /* add tmpset to current set of states */
1647 ++(f->curstat);
1648 resize_state(f, f->curstat);
1649 clear_gototab(f, f->curstat);
1650 xfree(f->posns[f->curstat]);
1651 p = intalloc(setcnt + 1, __func__);
1652
1653 f->posns[f->curstat] = p;
1654 if (c != HAT)
1655 set_gototab(f, s, c, f->curstat);
1656 for (i = 0; i <= setcnt; i++)
1657 p[i] = tmpset[i];
1658 if (setvec[f->accept])
1659 f->out[f->curstat] = 1;
1660 else
1661 f->out[f->curstat] = 0;
1662 return f->curstat;
1663}
1664
1665void
1666freefa(fa *f) /* free a finite automaton */
1667{
1668 int i;
1669
1670 if (f == NULL)
1671 return;
1672 for (i = 0; i < f->state_count; i++)
1673 xfree(f->gototab[i].entries);
1674 xfree(f->gototab);
1675 for (i = 0; i <= f->curstat; i++)
1676 xfree(f->posns[i]);
1677 for (i = 0; i <= f->accept; i++) {
1678 xfree(f->re[i].lfollow);
1679 if (f->re[i].ltype == CCL || f->re[i].ltype == NCCL)
1680 xfree(f->re[i].lval.np);
1681 }
1682 xfree(f->restr);
1683 xfree(f->out);
1684 xfree(f->posns);
1685 xfree(f->gototab);
1686 xfree(f);
1687}
