1/****************************************************************
2Copyright (C) Lucent Technologies 1997
3All Rights Reserved
4
5Permission to use, copy, modify, and distribute this software and
6its documentation for any purpose and without fee is hereby
7granted, provided that the above copyright notice appear in all
8copies and that both that the copyright notice and this
9permission notice and warranty disclaimer appear in supporting
10documentation, and that the name Lucent Technologies or any of
11its entities not be used in advertising or publicity pertaining
12to distribution of the software without specific, written prior
13permission.
14
15LUCENT DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
16INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS.
17IN NO EVENT SHALL LUCENT OR ANY OF ITS ENTITIES BE LIABLE FOR ANY
18SPECIAL, INDIRECT OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
19WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER
20IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION,
21ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE OF
22THIS 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: /* can't 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: /* can't 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: can't
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: /* can't 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)); /* can't 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 don't
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; /* don't 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; /* don't 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) /* don't 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 doesn't show up in any of the header files on any
1151 * system i use, it's 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 - shouldn't 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 can't
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}
