xref: /titanic_50/usr/src/cmd/awk/b.c (revision 174bc6499d233e329ecd3d98a880a7b07df16bfa)
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 }
865