1 /*
2 * CDDL HEADER START
3 *
4 * The contents of this file are subject to the terms of the
5 * Common Development and Distribution License, Version 1.0 only
6 * (the "License"). You may not use this file except in compliance
7 * with the License.
8 *
9 * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
10 * or http://www.opensolaris.org/os/licensing.
11 * See the License for the specific language governing permissions
12 * and limitations under the License.
13 *
14 * When distributing Covered Code, include this CDDL HEADER in each
15 * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
16 * If applicable, add the following below this CDDL HEADER, with the
17 * fields enclosed by brackets "[]" replaced with your own identifying
18 * information: Portions Copyright [yyyy] [name of copyright owner]
19 *
20 * CDDL HEADER END
21 */
22
23 /*
24 * Copyright 2005 Sun Microsystems, Inc. All rights reserved.
25 * Use is subject to license terms.
26 */
27
28 /* Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T */
29 /* All Rights Reserved */
30
31 #pragma ident "%Z%%M% %I% %E% SMI"
32
33 #define DEBUG
34
35 #include "awk.h"
36 #include "y.tab.h"
37
38 #define HAT (NCHARS-1) /* matches ^ in regular expr */
39 /* NCHARS is 2**n */
40 #define MAXLIN (3 * LINE_MAX)
41
42 #define type(v) (v)->nobj
43 #define left(v) (v)->narg[0]
44 #define right(v) (v)->narg[1]
45 #define parent(v) (v)->nnext
46
47 #define LEAF case CCL: case NCCL: case CHAR: case DOT: case FINAL: case ALL:
48 #define UNARY case STAR: case PLUS: case QUEST:
49
50 /*
51 * encoding in tree Nodes:
52 * leaf (CCL, NCCL, CHAR, DOT, FINAL, ALL):
53 * left is index, right contains value or pointer to value
54 * unary (STAR, PLUS, QUEST): left is child, right is null
55 * binary (CAT, OR): left and right are children
56 * parent contains pointer to parent
57 */
58
59 int setvec[MAXLIN];
60 int tmpset[MAXLIN];
61 Node *point[MAXLIN];
62
63 int rtok; /* next token in current re */
64 int rlxval;
65 uchar *rlxstr;
66 uchar *prestr; /* current position in current re */
67 uchar *lastre; /* origin of last re */
68
69 static int setcnt;
70 static int poscnt;
71
72 uchar *patbeg;
73 int patlen;
74
75 #define NFA 20 /* cache this many dynamic fa's */
76 fa *fatab[NFA];
77 int nfatab = 0; /* entries in fatab */
78
79 static fa *mkdfa(uchar *, int);
80 static int makeinit(fa *, int);
81 static void penter(Node *);
82 static void freetr(Node *);
83 static void overflo(char *);
84 static void cfoll(fa *, Node *);
85 static void follow(Node *);
86 static Node *reparse(uchar *);
87 static int relex(void);
88 static void freefa(fa *);
89 static int cgoto(fa *, int, int);
90
91 fa *
92 makedfa(uchar *s, int anchor) /* returns dfa for reg expr s */
93 {
94 int i, use, nuse;
95 fa *pfa;
96
97 if (compile_time) /* a constant for sure */
98 return (mkdfa(s, anchor));
99 for (i = 0; i < nfatab; i++) { /* is it there already? */
100 if (fatab[i]->anchor == anchor &&
101 strcmp((char *)fatab[i]->restr, (char *)s) == 0) {
102 fatab[i]->use++;
103 return (fatab[i]);
104 }
105 }
106 pfa = mkdfa(s, anchor);
107 if (nfatab < NFA) { /* room for another */
108 fatab[nfatab] = pfa;
109 fatab[nfatab]->use = 1;
110 nfatab++;
111 return (pfa);
112 }
113 use = fatab[0]->use; /* replace least-recently used */
114 nuse = 0;
115 for (i = 1; i < nfatab; i++)
116 if (fatab[i]->use < use) {
117 use = fatab[i]->use;
118 nuse = i;
119 }
120 freefa(fatab[nuse]);
121 fatab[nuse] = pfa;
122 pfa->use = 1;
123 return (pfa);
124 }
125
126 fa *
127 mkdfa(uchar *s, int anchor) /* does the real work of making a dfa */
128 /* anchor = 1 for anchored matches, else 0 */
129 {
130 Node *p, *p1;
131 fa *f;
132
133 p = reparse(s);
134 p1 = op2(CAT, op2(STAR, op2(ALL, NIL, NIL), NIL), p);
135 /* put ALL STAR in front of reg. exp. */
136 p1 = op2(CAT, p1, op2(FINAL, NIL, NIL));
137 /* put FINAL after reg. exp. */
138
139 poscnt = 0;
140 penter(p1); /* enter parent pointers and leaf indices */
141 if ((f = (fa *)calloc(1, sizeof (fa) + poscnt * sizeof (rrow))) == NULL)
142 overflo("no room for fa");
143 /* penter has computed number of positions in re */
144 f->accept = poscnt-1;
145 cfoll(f, p1); /* set up follow sets */
146 freetr(p1);
147 if ((f->posns[0] =
148 (int *)calloc(1, *(f->re[0].lfollow) * sizeof (int))) == NULL) {
149 overflo("out of space in makedfa");
150 }
151 if ((f->posns[1] = (int *)calloc(1, sizeof (int))) == NULL)
152 overflo("out of space in makedfa");
153 *f->posns[1] = 0;
154 f->initstat = makeinit(f, anchor);
155 f->anchor = anchor;
156 f->restr = tostring(s);
157 return (f);
158 }
159
160 static int
161 makeinit(fa *f, int anchor)
162 {
163 register int i, k;
164
165 f->curstat = 2;
166 f->out[2] = 0;
167 f->reset = 0;
168 k = *(f->re[0].lfollow);
169 xfree(f->posns[2]);
170 if ((f->posns[2] = (int *)calloc(1, (k+1) * sizeof (int))) == NULL)
171 overflo("out of space in makeinit");
172 for (i = 0; i <= k; i++) {
173 (f->posns[2])[i] = (f->re[0].lfollow)[i];
174 }
175 if ((f->posns[2])[1] == f->accept)
176 f->out[2] = 1;
177 for (i = 0; i < NCHARS; i++)
178 f->gototab[2][i] = 0;
179 f->curstat = cgoto(f, 2, HAT);
180 if (anchor) {
181 *f->posns[2] = k-1; /* leave out position 0 */
182 for (i = 0; i < k; i++) {
183 (f->posns[0])[i] = (f->posns[2])[i];
184 }
185
186 f->out[0] = f->out[2];
187 if (f->curstat != 2)
188 --(*f->posns[f->curstat]);
189 }
190 return (f->curstat);
191 }
192
193 void
194 penter(Node *p) /* set up parent pointers and leaf indices */
195 {
196 switch (type(p)) {
197 LEAF
198 left(p) = (Node *) poscnt;
199 point[poscnt++] = p;
200 break;
201 UNARY
202 penter(left(p));
203 parent(left(p)) = p;
204 break;
205 case CAT:
206 case OR:
207 penter(left(p));
208 penter(right(p));
209 parent(left(p)) = p;
210 parent(right(p)) = p;
211 break;
212 default:
213 ERROR "unknown type %d in penter", type(p) FATAL;
214 break;
215 }
216 }
217
218 static void
219 freetr(Node *p) /* free parse tree */
220 {
221 switch (type(p)) {
222 LEAF
223 xfree(p);
224 break;
225 UNARY
226 freetr(left(p));
227 xfree(p);
228 break;
229 case CAT:
230 case OR:
231 freetr(left(p));
232 freetr(right(p));
233 xfree(p);
234 break;
235 default:
236 ERROR "unknown type %d in freetr", type(p) FATAL;
237 break;
238 }
239 }
240
241 uchar *
242 cclenter(uchar *p)
243 {
244 register int i, c;
245 uchar *op, *chars, *ret;
246 size_t bsize;
247
248 init_buf(&chars, &bsize, LINE_INCR);
249 op = p;
250 i = 0;
251 while ((c = *p++) != 0) {
252 if (c == '\\') {
253 if ((c = *p++) == 't')
254 c = '\t';
255 else if (c == 'n')
256 c = '\n';
257 else if (c == 'f')
258 c = '\f';
259 else if (c == 'r')
260 c = '\r';
261 else if (c == 'b')
262 c = '\b';
263 else if (c == '\\')
264 c = '\\';
265 else if (isdigit(c)) {
266 int n = c - '0';
267 if (isdigit(*p)) {
268 n = 8 * n + *p++ - '0';
269 if (isdigit(*p))
270 n = 8 * n + *p++ - '0';
271 }
272 c = n;
273 } /* else */
274 /* c = c; */
275 } else if (c == '-' && i > 0 && chars[i-1] != 0) {
276 if (*p != 0) {
277 c = chars[i-1];
278 while ((uchar)c < *p) { /* fails if *p is \\ */
279 expand_buf(&chars, &bsize, i);
280 chars[i++] = ++c;
281 }
282 p++;
283 continue;
284 }
285 }
286 expand_buf(&chars, &bsize, i);
287 chars[i++] = c;
288 }
289 chars[i++] = '\0';
290 dprintf(("cclenter: in = |%s|, out = |%s|\n", op, chars));
291 xfree(op);
292 ret = tostring(chars);
293 free(chars);
294 return (ret);
295 }
296
297 static void
298 overflo(char *s)
299 {
300 ERROR "regular expression too big: %s", gettext((char *)s) FATAL;
301 }
302
303 /* enter follow set of each leaf of vertex v into lfollow[leaf] */
304 static void
305 cfoll(fa *f, Node *v)
306 {
307 register int i;
308 register int *p;
309
310 switch (type(v)) {
311 LEAF
312 f->re[(int)left(v)].ltype = type(v);
313 f->re[(int)left(v)].lval = (int)right(v);
314 for (i = 0; i <= f->accept; i++)
315 setvec[i] = 0;
316 setcnt = 0;
317 follow(v); /* computes setvec and setcnt */
318 if ((p = (int *)calloc(1, (setcnt+1) * sizeof (int))) == NULL)
319 overflo("follow set overflow");
320 f->re[(int)left(v)].lfollow = p;
321 *p = setcnt;
322 for (i = f->accept; i >= 0; i--) {
323 if (setvec[i] == 1)
324 *++p = i;
325 }
326 break;
327 UNARY
328 cfoll(f, left(v));
329 break;
330 case CAT:
331 case OR:
332 cfoll(f, left(v));
333 cfoll(f, right(v));
334 break;
335 default:
336 ERROR "unknown type %d in cfoll", type(v) FATAL;
337 }
338 }
339
340 /*
341 * collects initially active leaves of p into setvec
342 * returns 0 or 1 depending on whether p matches empty string
343 */
344 static int
345 first(Node *p)
346 {
347 register int b;
348
349 switch (type(p)) {
350 LEAF
351 if (setvec[(int)left(p)] != 1) {
352 setvec[(int)left(p)] = 1;
353 setcnt++;
354 }
355 if (type(p) == CCL && (*(uchar *)right(p)) == '\0')
356 return (0); /* empty CCL */
357 else
358 return (1);
359 case PLUS:
360 if (first(left(p)) == 0)
361 return (0);
362 return (1);
363 case STAR:
364 case QUEST:
365 (void) first(left(p));
366 return (0);
367 case CAT:
368 if (first(left(p)) == 0 && first(right(p)) == 0)
369 return (0);
370 return (1);
371 case OR:
372 b = first(right(p));
373 if (first(left(p)) == 0 || b == 0)
374 return (0);
375 return (1);
376 }
377 ERROR "unknown type %d in first", type(p) FATAL;
378 return (-1);
379 }
380
381 /* collects leaves that can follow v into setvec */
382 static void
383 follow(Node *v)
384 {
385 Node *p;
386
387 if (type(v) == FINAL)
388 return;
389 p = parent(v);
390 switch (type(p)) {
391 case STAR:
392 case PLUS:
393 (void) first(v);
394 follow(p);
395 return;
396
397 case OR:
398 case QUEST:
399 follow(p);
400 return;
401
402 case CAT:
403 if (v == left(p)) { /* v is left child of p */
404 if (first(right(p)) == 0) {
405 follow(p);
406 return;
407 }
408 } else /* v is right child */
409 follow(p);
410 return;
411 default:
412 ERROR "unknown type %d in follow", type(p) FATAL;
413 break;
414 }
415 }
416
417 static int
418 member(uchar c, uchar *s) /* is c in s? */
419 {
420 while (*s)
421 if (c == *s++)
422 return (1);
423 return (0);
424 }
425
426
427 int
428 match(fa *f, uchar *p)
429 {
430 register int s, ns;
431
432 s = f->reset ? makeinit(f, 0) : f->initstat;
433 if (f->out[s])
434 return (1);
435 do {
436 if ((ns = f->gototab[s][*p]) != 0)
437 s = ns;
438 else
439 s = cgoto(f, s, *p);
440 if (f->out[s])
441 return (1);
442 } while (*p++ != 0);
443 return (0);
444 }
445
446 int
447 pmatch(fa *f, uchar *p)
448 {
449 register int s, ns;
450 register uchar *q;
451 int i, k;
452
453 if (f->reset) {
454 f->initstat = s = makeinit(f, 1);
455 } else {
456 s = f->initstat;
457 }
458 patbeg = p;
459 patlen = -1;
460 do {
461 q = p;
462 do {
463 if (f->out[s]) /* final state */
464 patlen = q-p;
465 if ((ns = f->gototab[s][*q]) != 0)
466 s = ns;
467 else
468 s = cgoto(f, s, *q);
469 if (s == 1) { /* no transition */
470 if (patlen >= 0) {
471 patbeg = p;
472 return (1);
473 } else
474 goto nextin; /* no match */
475 }
476 } while (*q++ != 0);
477 if (f->out[s])
478 patlen = q - p - 1; /* don't count $ */
479 if (patlen >= 0) {
480 patbeg = p;
481 return (1);
482 }
483 nextin:
484 s = 2;
485 if (f->reset) {
486 for (i = 2; i <= f->curstat; i++)
487 xfree(f->posns[i]);
488 k = *f->posns[0];
489 if ((f->posns[2] =
490 (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) {
491 overflo("out of space in pmatch");
492 }
493 for (i = 0; i <= k; i++)
494 (f->posns[2])[i] = (f->posns[0])[i];
495 f->initstat = f->curstat = 2;
496 f->out[2] = f->out[0];
497 for (i = 0; i < NCHARS; i++)
498 f->gototab[2][i] = 0;
499 }
500 } while (*p++ != 0);
501 return (0);
502 }
503
504 int
505 nematch(fa *f, uchar *p)
506 {
507 register int s, ns;
508 register uchar *q;
509 int i, k;
510
511 if (f->reset) {
512 f->initstat = s = makeinit(f, 1);
513 } else {
514 s = f->initstat;
515 }
516 patlen = -1;
517 while (*p) {
518 q = p;
519 do {
520 if (f->out[s]) /* final state */
521 patlen = q-p;
522 if ((ns = f->gototab[s][*q]) != 0)
523 s = ns;
524 else
525 s = cgoto(f, s, *q);
526 if (s == 1) { /* no transition */
527 if (patlen > 0) {
528 patbeg = p;
529 return (1);
530 } else
531 goto nnextin; /* no nonempty match */
532 }
533 } while (*q++ != 0);
534 if (f->out[s])
535 patlen = q - p - 1; /* don't count $ */
536 if (patlen > 0) {
537 patbeg = p;
538 return (1);
539 }
540 nnextin:
541 s = 2;
542 if (f->reset) {
543 for (i = 2; i <= f->curstat; i++)
544 xfree(f->posns[i]);
545 k = *f->posns[0];
546 if ((f->posns[2] =
547 (int *)calloc(1, (k + 1) * sizeof (int))) == NULL) {
548 overflo("out of state space");
549 }
550 for (i = 0; i <= k; i++)
551 (f->posns[2])[i] = (f->posns[0])[i];
552 f->initstat = f->curstat = 2;
553 f->out[2] = f->out[0];
554 for (i = 0; i < NCHARS; i++)
555 f->gototab[2][i] = 0;
556 }
557 p++;
558 }
559 return (0);
560 }
561
562 static Node *regexp(void), *primary(void), *concat(Node *);
563 static Node *alt(Node *), *unary(Node *);
564
565 static Node *
566 reparse(uchar *p)
567 {
568 /* parses regular expression pointed to by p */
569 /* uses relex() to scan regular expression */
570 Node *np;
571
572 dprintf(("reparse <%s>\n", p));
573 lastre = prestr = p; /* prestr points to string to be parsed */
574 rtok = relex();
575 if (rtok == '\0')
576 ERROR "empty regular expression" FATAL;
577 np = regexp();
578 if (rtok == '\0') {
579 return (np);
580 } else {
581 ERROR "syntax error in regular expression %s at %s",
582 lastre, prestr FATAL;
583 }
584 /*NOTREACHED*/
585 return (NULL);
586 }
587
588 static Node *
589 regexp(void)
590 {
591 return (alt(concat(primary())));
592 }
593
594 static Node *
595 primary(void)
596 {
597 Node *np;
598
599 switch (rtok) {
600 case CHAR:
601 np = op2(CHAR, NIL, (Node *)rlxval);
602 rtok = relex();
603 return (unary(np));
604 case ALL:
605 rtok = relex();
606 return (unary(op2(ALL, NIL, NIL)));
607 case DOT:
608 rtok = relex();
609 return (unary(op2(DOT, NIL, NIL)));
610 case CCL:
611 /*LINTED align*/
612 np = op2(CCL, NIL, (Node *)cclenter(rlxstr));
613 rtok = relex();
614 return (unary(np));
615 case NCCL:
616 /*LINTED align*/
617 np = op2(NCCL, NIL, (Node *)cclenter(rlxstr));
618 rtok = relex();
619 return (unary(np));
620 case '^':
621 rtok = relex();
622 return (unary(op2(CHAR, NIL, (Node *)HAT)));
623 case '$':
624 rtok = relex();
625 return (unary(op2(CHAR, NIL, NIL)));
626 case '(':
627 rtok = relex();
628 if (rtok == ')') { /* special pleading for () */
629 rtok = relex();
630 return (unary(op2(CCL, NIL,
631 /*LINTED align*/
632 (Node *)tostring((uchar *)""))));
633 }
634 np = regexp();
635 if (rtok == ')') {
636 rtok = relex();
637 return (unary(np));
638 } else {
639 ERROR "syntax error in regular expression %s at %s",
640 lastre, prestr FATAL;
641 }
642 default:
643 ERROR "illegal primary in regular expression %s at %s",
644 lastre, prestr FATAL;
645 }
646 /*NOTREACHED*/
647 return (NULL);
648 }
649
650 static Node *
651 concat(Node *np)
652 {
653 switch (rtok) {
654 case CHAR: case DOT: case ALL: case CCL: case NCCL: case '$': case '(':
655 return (concat(op2(CAT, np, primary())));
656 default:
657 return (np);
658 }
659 }
660
661 static Node *
662 alt(Node *np)
663 {
664 if (rtok == OR) {
665 rtok = relex();
666 return (alt(op2(OR, np, concat(primary()))));
667 }
668 return (np);
669 }
670
671 static Node *
672 unary(Node *np)
673 {
674 switch (rtok) {
675 case STAR:
676 rtok = relex();
677 return (unary(op2(STAR, np, NIL)));
678 case PLUS:
679 rtok = relex();
680 return (unary(op2(PLUS, np, NIL)));
681 case QUEST:
682 rtok = relex();
683 return (unary(op2(QUEST, np, NIL)));
684 default:
685 return (np);
686 }
687 }
688
689 static int
690 relex(void) /* lexical analyzer for reparse */
691 {
692 register int c;
693 uchar *cbuf;
694 int clen, cflag;
695
696 switch (c = *prestr++) {
697 case '|': return OR;
698 case '*': return STAR;
699 case '+': return PLUS;
700 case '?': return QUEST;
701 case '.': return DOT;
702 case '\0': prestr--; return '\0';
703 case '^':
704 case '$':
705 case '(':
706 case ')':
707 return (c);
708 case '\\':
709 if ((c = *prestr++) == 't')
710 c = '\t';
711 else if (c == 'n')
712 c = '\n';
713 else if (c == 'f')
714 c = '\f';
715 else if (c == 'r')
716 c = '\r';
717 else if (c == 'b')
718 c = '\b';
719 else if (c == '\\')
720 c = '\\';
721 else if (isdigit(c)) {
722 int n = c - '0';
723 if (isdigit(*prestr)) {
724 n = 8 * n + *prestr++ - '0';
725 if (isdigit(*prestr))
726 n = 8 * n + *prestr++ - '0';
727 }
728 c = n;
729 } /* else it's now in c */
730 rlxval = c;
731 return (CHAR);
732 default:
733 rlxval = c;
734 return (CHAR);
735 case '[':
736 clen = 0;
737 if (*prestr == '^') {
738 cflag = 1;
739 prestr++;
740 } else
741 cflag = 0;
742 init_buf(&cbuf, NULL, strlen((char *)prestr) * 2 + 1);
743 for (;;) {
744 if ((c = *prestr++) == '\\') {
745 cbuf[clen++] = '\\';
746 if ((c = *prestr++) == '\0') {
747 ERROR
748 "nonterminated character class %s", lastre FATAL;
749 }
750 cbuf[clen++] = c;
751 } else if (c == ']') {
752 cbuf[clen] = 0;
753 rlxstr = tostring(cbuf);
754 free(cbuf);
755 if (cflag == 0)
756 return (CCL);
757 else
758 return (NCCL);
759 } else if (c == '\n') {
760 ERROR "newline in character class %s...",
761 lastre FATAL;
762 } else if (c == '\0') {
763 ERROR "nonterminated character class %s",
764 lastre FATAL;
765 } else
766 cbuf[clen++] = c;
767 }
768 /*NOTREACHED*/
769 }
770 return (0);
771 }
772
773 static int
774 cgoto(fa *f, int s, int c)
775 {
776 register int i, j, k;
777 register int *p, *q;
778
779 for (i = 0; i <= f->accept; i++)
780 setvec[i] = 0;
781 setcnt = 0;
782 /* compute positions of gototab[s,c] into setvec */
783 p = f->posns[s];
784 for (i = 1; i <= *p; i++) {
785 if ((k = f->re[p[i]].ltype) != FINAL) {
786 if (k == CHAR && c == f->re[p[i]].lval ||
787 k == DOT && c != 0 && c != HAT ||
788 k == ALL && c != 0 ||
789 k == CCL &&
790 member(c, (uchar *)f->re[p[i]].lval) ||
791 k == NCCL &&
792 !member(c, (uchar *)f->re[p[i]].lval) &&
793 c != 0 && c != HAT) {
794 q = f->re[p[i]].lfollow;
795 for (j = 1; j <= *q; j++) {
796 if (setvec[q[j]] == 0) {
797 setcnt++;
798 setvec[q[j]] = 1;
799 }
800 }
801 }
802 }
803 }
804 /* determine if setvec is a previous state */
805 tmpset[0] = setcnt;
806 j = 1;
807 for (i = f->accept; i >= 0; i--)
808 if (setvec[i]) {
809 tmpset[j++] = i;
810 }
811 /* tmpset == previous state? */
812 for (i = 1; i <= f->curstat; i++) {
813 p = f->posns[i];
814 if ((k = tmpset[0]) != p[0])
815 goto different;
816 for (j = 1; j <= k; j++)
817 if (tmpset[j] != p[j])
818 goto different;
819 /* setvec is state i */
820 f->gototab[s][c] = i;
821 return (i);
822 different:;
823 }
824
825 /* add tmpset to current set of states */
826 if (f->curstat >= NSTATES-1) {
827 f->curstat = 2;
828 f->reset = 1;
829 for (i = 2; i < NSTATES; i++)
830 xfree(f->posns[i]);
831 } else
832 ++(f->curstat);
833 for (i = 0; i < NCHARS; i++)
834 f->gototab[f->curstat][i] = 0;
835 xfree(f->posns[f->curstat]);
836 if ((p = (int *)calloc(1, (setcnt + 1) * sizeof (int))) == NULL)
837 overflo("out of space in cgoto");
838
839 f->posns[f->curstat] = p;
840 f->gototab[s][c] = f->curstat;
841 for (i = 0; i <= setcnt; i++)
842 p[i] = tmpset[i];
843 if (setvec[f->accept])
844 f->out[f->curstat] = 1;
845 else
846 f->out[f->curstat] = 0;
847 return (f->curstat);
848 }
849
850 static void
851 freefa(fa *f)
852 {
853
854 register int i;
855
856 if (f == NULL)
857 return;
858 for (i = 0; i <= f->curstat; i++)
859 xfree(f->posns[i]);
860 for (i = 0; i <= f->accept; i++)
861 xfree(f->re[i].lfollow);
862 xfree(f->restr);
863 xfree(f);
864 }