xref: /titanic_51/usr/src/cmd/egrep/egrep.y (revision 356f72340a69936724c69f2f87fffa6f5887f885) 
1 %{
2 /*
3  * CDDL HEADER START
4  *
5  * The contents of this file are subject to the terms of the
6  * Common Development and Distribution License, Version 1.0 only
7  * (the "License").  You may not use this file except in compliance
8  * with the License.
9  *
10  * You can obtain a copy of the license at usr/src/OPENSOLARIS.LICENSE
11  * or http://www.opensolaris.org/os/licensing.
12  * See the License for the specific language governing permissions
13  * and limitations under the License.
14  *
15  * When distributing Covered Code, include this CDDL HEADER in each
16  * file and include the License file at usr/src/OPENSOLARIS.LICENSE.
17  * If applicable, add the following below this CDDL HEADER, with the
18  * fields enclosed by brackets "[]" replaced with your own identifying
19  * information: Portions Copyright [yyyy] [name of copyright owner]
20  *
21  * CDDL HEADER END
22  */
23 %}
24 /*
25  * Copyright 2005 Sun Microsystems, Inc.  All rights reserved.
26  * Use is subject to license terms.
27  */
28 
29 /*	Copyright (c) 1984, 1986, 1987, 1988, 1989 AT&T	*/
30 /*	  All Rights Reserved  	*/
31 
32 /*	Copyright (c) 1987, 1988 Microsoft Corporation	*/
33 /*	  All Rights Reserved	*/
34 
35 /*
36  * Copyright 2013 Damian Bogel. All rights reserved.
37  */
38 
39 /*
40  * egrep -- print lines containing (or not containing) a regular expression
41  *
42  *	status returns:
43  *		0 - ok, and some matches
44  *		1 - ok, but no matches
45  *		2 - some error; matches irrelevant
46  */
47 %token CHAR MCHAR DOT MDOT CCL NCCL MCCL NMCCL OR CAT STAR PLUS QUEST
48 %left OR
49 %left CHAR MCHAR DOT CCL NCCL MCCL NMCCL '('
50 %left CAT
51 %left STAR PLUS QUEST
52 
53 %{
54 #include <stdio.h>
55 #include <ctype.h>
56 #include <memory.h>
57 #include <wchar.h>
58 #include <wctype.h>
59 #include <widec.h>
60 #include <stdlib.h>
61 #include <limits.h>
62 #include <locale.h>
63 
64 #define STDIN_FILENAME gettext("(standard input)")
65 
66 #define BLKSIZE 512	/* size of reported disk blocks */
67 #define EBUFSIZ 8192
68 #define MAXLIN 350
69 #define NCHARS 256
70 #define MAXPOS 4000
71 #define NSTATES 64
72 #define FINAL -1
73 #define RIGHT '\n'	/* serves as record separator and as $ */
74 #define LEFT '\n'	/* beginning of line */
75 int gotofn[NSTATES][NCHARS];
76 int state[NSTATES];
77 int out[NSTATES];
78 int line  = 1;
79 int *name;
80 int *left;
81 int *right;
82 int *parent;
83 int *foll;
84 int *positions;
85 char *chars;
86 wchar_t *lower;
87 wchar_t *upper;
88 int maxlin, maxclin, maxwclin, maxpos;
89 int nxtpos = 0;
90 int inxtpos;
91 int nxtchar = 0;
92 int *tmpstat;
93 int *initstat;
94 int istat;
95 int nstate = 1;
96 int xstate;
97 int count;
98 int icount;
99 char *input;
100 
101 
102 wchar_t lyylval;
103 wchar_t nextch();
104 wchar_t maxmin();
105 int compare();
106 void overflo();
107 
108 char reinit = 0;
109 
110 long long lnum;
111 int	bflag;
112 int	cflag;
113 int	eflag;
114 int	fflag;
115 int	Hflag;
116 int	hflag;
117 int	iflag;
118 int	lflag;
119 int	nflag;
120 int	qflag;
121 int	vflag;
122 int	nfile;
123 long long blkno;
124 long long tln;
125 int	nsucc;
126 int	badbotch;
127 extern 	char *optarg;
128 extern 	int optind;
129 
130 int	f;
131 FILE	*expfile;
132 %}
133 
134 %%
135 s:	t
136 		{
137 		  unary(FINAL, $1);
138 		  line--;
139 		}
140 	;
141 t:	b r
142 		{ $$ = node(CAT, $1, $2); }
143 	| OR b r OR
144 		{ $$ = node(CAT, $2, $3); }
145 	| OR b r
146 		{ $$ = node(CAT, $2, $3); }
147 	| b r OR
148 		{ $$ = node(CAT, $1, $2); }
149 	;
150 b:
151 		{ /* if(multibyte)
152 			$$ = mdotenter();
153 		  else */
154 			$$ = enter(DOT);
155 		  $$ = unary(STAR, $$);
156 		}
157 	;
158 r:	CHAR
159 		{ $$ = iflag && isalpha($1) ?
160 		node(OR, enter(tolower($1)), enter(toupper($1))) : enter($1); }
161 	| MCHAR
162 		{ $$ = (iflag && iswalpha(lyylval)) ?
163 		node(OR, mchar(towlower(lyylval)), mchar(towupper(lyylval))) :
164 		mchar(lyylval); }
165 	| DOT
166 		{ if(multibyte)
167 			$$ = mdotenter();
168 		  else
169 			$$ = enter(DOT);
170 		}
171 	| CCL
172 		{ $$ = cclenter(CCL); }
173 	| NCCL
174 		{ $$ = cclenter(NCCL); }
175 	| MCCL
176 		{ $$ = ccl(CCL); }
177 	| NMCCL
178 		{ $$ = ccl(NCCL); }
179 	;
180 
181 r:	r OR r
182 		{ $$ = node(OR, $1, $3); }
183 	| r r %prec CAT
184 		{ $$ = node(CAT, $1, $2); }
185 	| r STAR
186 		{ $$ = unary(STAR, $1); }
187 	| r PLUS
188 		{ $$ = unary(PLUS, $1); }
189 	| r QUEST
190 		{ $$ = unary(QUEST, $1); }
191 	| '(' r ')'
192 		{ $$ = $2; }
193 	| error
194 	;
195 
196 %%
197 void	add(int *, int);
198 void	clearg(void);
199 void	execute(char *);
200 void	follow(int);
201 int	mgetc(void);
202 void	synerror(void);
203 
204 
205 void
206 yyerror(char *s)
207 {
208 	fprintf(stderr, "egrep: %s\n", s);
209 	exit(2);
210 }
211 
212 int
213 yylex(void)
214 {
215 	extern int yylval;
216 	int cclcnt, x, ccount, oldccount;
217 	wchar_t c, lc;
218 
219 	c = nextch();
220 	switch(c) {
221 		case '^':
222 			yylval = LEFT;
223 			return(CHAR);
224 		case '$':
225 			c = RIGHT;
226 			goto defchar;
227 		case '|': return (OR);
228 		case '*': return (STAR);
229 		case '+': return (PLUS);
230 		case '?': return (QUEST);
231 		case '(': return (c);
232 		case ')': return (c);
233 		case '.': return(DOT);
234 		case '\0': return (0);
235 		case RIGHT: return (OR);
236 		case '[':
237 			x = (multibyte ? MCCL : CCL);
238 			cclcnt = 0;
239 			count = nxtchar++;
240 			if ((c = nextch()) == '^') {
241 				x = (multibyte ? NMCCL : NCCL);
242 				c = nextch();
243 			}
244 			lc = 0;
245 			do {
246 				if (iflag && iswalpha(c))
247 					c = towlower(c);
248 				if (c == '\0') synerror();
249 				if (c == '-' && cclcnt > 0 && lc != 0) {
250 					if ((c = nextch()) != 0) {
251 						if(c == ']') {
252 							chars[nxtchar++] = '-';
253 							cclcnt++;
254 							break;
255 						}
256 						if (iflag && iswalpha(c))
257 							c = towlower(c);
258 						if (!multibyte ||
259 						(c & WCHAR_CSMASK) == (lc & WCHAR_CSMASK) &&
260 						lc < c &&
261 						!iswcntrl(c) && !iswcntrl(lc)) {
262 							if (nxtchar >= maxclin)
263 								if (allocchars() == 0)
264 									overflo();
265 							chars[nxtchar++] = '-';
266 							cclcnt++;
267 						}
268 					}
269 				}
270 				ccount = oldccount = nxtchar;
271 				if(ccount + MB_LEN_MAX >= maxclin)
272 					if(allocchars() == 0)
273 						overflo();
274 				ccount += wctomb(&chars[ccount], c);
275 				cclcnt += ccount - oldccount;
276 				nxtchar += ccount - oldccount;
277 				lc = c;
278 			} while ((c = nextch()) != ']');
279 			chars[count] = cclcnt;
280 			return(x);
281 
282 		case '\\':
283 			if ((c = nextch()) == '\0') synerror();
284 		defchar:
285 		default:
286 			if (c <= 0177) {
287 				yylval = c;
288 				return (CHAR);
289 			} else {
290 				lyylval = c;
291 				return (MCHAR);
292 			}
293 	}
294 }
295 
296 wchar_t
297 nextch(void)
298 {
299 	wchar_t lc;
300 	char multic[MB_LEN_MAX];
301 	int length, d;
302 	if (fflag) {
303 		if ((length = _mbftowc(multic, &lc, mgetc, &d)) < 0)
304 			synerror();
305 		if(length == 0)
306 			lc = '\0';
307 	}
308 	else  {
309 		if((length = mbtowc(&lc, input, MB_LEN_MAX)) == -1)
310 			synerror();
311 		if(length == 0)
312 			return(0);
313 		input += length;
314 	}
315 	return(lc);
316 }
317 
318 int
319 mgetc(void)
320 {
321 	return(getc(expfile));
322 }
323 
324 void
325 synerror(void)
326 {
327 	fprintf(stderr, gettext("egrep: syntax error\n"));
328 	exit(2);
329 }
330 
331 int
332 enter(int x)
333 {
334 	if(line >= maxlin)
335 		if(alloctree() == 0)
336 			overflo();
337 	name[line] = x;
338 	left[line] = 0;
339 	right[line] = 0;
340 	return(line++);
341 }
342 
343 int
344 cclenter(int x)
345 {
346 	int linno;
347 	linno = enter(x);
348 	right[linno] = count;
349 	return (linno);
350 }
351 
352 int
353 node(int x, int l, int r)
354 {
355 	if(line >= maxlin)
356 		if(alloctree() == 0)
357 			overflo();
358 	name[line] = x;
359 	left[line] = l;
360 	right[line] = r;
361 	parent[l] = line;
362 	parent[r] = line;
363 	return(line++);
364 }
365 
366 int
367 unary(int x, int d)
368 {
369 	if(line >= maxlin)
370 		if(alloctree() == 0)
371 			overflo();
372 	name[line] = x;
373 	left[line] = d;
374 	right[line] = 0;
375 	parent[d] = line;
376 	return(line++);
377 }
378 
379 int
380 allocchars(void)
381 {
382 	maxclin += MAXLIN;
383 	if((chars = realloc(chars, maxclin)) == (char *)0)
384 		return 0;
385 	return 1;
386 }
387 
388 int
389 alloctree(void)
390 {
391 	maxlin += MAXLIN;
392 	if((name = (int *)realloc(name, maxlin*sizeof(int))) == (int *)0)
393 		return 0;
394 	if((left = (int *)realloc(left, maxlin*sizeof(int))) == (int *)0)
395 		return 0;
396 	if((right = (int *)realloc(right, maxlin*sizeof(int))) == (int *)0)
397 		return 0;
398 	if((parent = (int *)realloc(parent, maxlin*sizeof(int))) == (int *)0)
399 		return 0;
400 	if((foll = (int *)realloc(foll, maxlin*sizeof(int))) == (int *)0)
401 		return 0;
402 	if((tmpstat = (int *)realloc(tmpstat, maxlin*sizeof(int))) == (int *)0)
403 		return 0;
404 	if((initstat = (int *)realloc(initstat, maxlin*sizeof(int))) == (int *)0)
405 		return 0;
406 	return 1;
407 }
408 
409 void
410 overflo(void)
411 {
412 	fprintf(stderr, gettext("egrep: regular expression too long\n"));
413 	exit(2);
414 }
415 
416 void
417 cfoll(int v)
418 {
419 	int i;
420 	if (left[v] == 0) {
421 		count = 0;
422 		for (i=1; i<=line; i++) tmpstat[i] = 0;
423 		follow(v);
424 		add(foll, v);
425 	}
426 	else if (right[v] == 0) cfoll(left[v]);
427 	else {
428 		cfoll(left[v]);
429 		cfoll(right[v]);
430 	}
431 }
432 
433 void
434 cgotofn(void)
435 {
436 	int i;
437 	count = 0;
438 	inxtpos = nxtpos;
439 	for (i=3; i<=line; i++) tmpstat[i] = 0;
440 	if (cstate(line-1)==0) {
441 		tmpstat[line] = 1;
442 		count++;
443 		out[1] = 1;
444 	}
445 	for (i=3; i<=line; i++) initstat[i] = tmpstat[i];
446 	count--;		/*leave out position 1 */
447 	icount = count;
448 	tmpstat[1] = 0;
449 	add(state, 1);
450 	istat = nxtst(1, LEFT);
451 }
452 
453 int
454 nxtst(int s, int c)
455 {
456 	int i, num, k;
457 	int pos, curpos, number, newpos;
458 	num = positions[state[s]];
459 	count = icount;
460 	for (i=3; i<=line; i++) tmpstat[i] = initstat[i];
461 	pos = state[s] + 1;
462 	for (i=0; i<num; i++) {
463 		curpos = positions[pos];
464 		k = name[curpos];
465 		if (k >= 0)
466 			if (
467 				(k == c)
468 				|| (k == DOT && dot(c))
469 				|| (k == MDOT && mdot(c))
470 				|| (k == CCL && dot(c) && member(c, right[curpos], 1))
471 				|| (k == NCCL && dot(c) && member(c, right[curpos], 0))
472 				|| (k == MCCL && mdot(c) && member(c, right[curpos], 1))
473 			) {
474 				number = positions[foll[curpos]];
475 				newpos = foll[curpos] + 1;
476 				for (k=0; k<number; k++) {
477 					if (tmpstat[positions[newpos]] != 1) {
478 						tmpstat[positions[newpos]] = 1;
479 						count++;
480 					}
481 					newpos++;
482 				}
483 			}
484 		pos++;
485 	}
486 	if (notin(nstate)) {
487 		if (++nstate >= NSTATES) {
488 			for (i=1; i<NSTATES; i++)
489 				out[i] = 0;
490 			for (i=1; i<NSTATES; i++)
491 				for (k=0; k<NCHARS; k++)
492 					gotofn[i][k] = 0;
493 			nstate = 1;
494 			nxtpos = inxtpos;
495 			reinit = 1;
496 			add(state, nstate);
497 			if (tmpstat[line] == 1) out[nstate] = 1;
498 			return nstate;
499 		}
500 		add(state, nstate);
501 		if (tmpstat[line] == 1) out[nstate] = 1;
502 		gotofn[s][c] = nstate;
503 		return nstate;
504 	}
505 	else {
506 		gotofn[s][c] = xstate;
507 		return xstate;
508 	}
509 }
510 
511 
512 int
513 cstate(int v)
514 {
515 	int b;
516 	if (left[v] == 0) {
517 		if (tmpstat[v] != 1) {
518 			tmpstat[v] = 1;
519 			count++;
520 		}
521 		return(1);
522 	}
523 	else if (right[v] == 0) {
524 		if (cstate(left[v]) == 0) return (0);
525 		else if (name[v] == PLUS) return (1);
526 		else return (0);
527 	}
528 	else if (name[v] == CAT) {
529 		if (cstate(left[v]) == 0 && cstate(right[v]) == 0) return (0);
530 		else return (1);
531 	}
532 	else { /* name[v] == OR */
533 		b = cstate(right[v]);
534 		if (cstate(left[v]) == 0 || b == 0) return (0);
535 		else return (1);
536 	}
537 }
538 
539 
540 int
541 dot(int c)
542 {
543 	if(multibyte && c >= 0200 && (!iscntrl(c) || c == SS2 && eucw2 || c == SS3 && eucw3))
544 		return(0);
545 	if(c == RIGHT || c == LEFT)
546 		return(0);
547 	return(1);
548 }
549 
550 int
551 mdot(int c)
552 {
553 	if(c >= 0200 && !iscntrl(c))
554 		return(1);
555 	return(0);
556 }
557 
558 int
559 member(int symb, int set, int torf)
560 {
561 	int i, num, pos, c, lc;
562 	if(symb == RIGHT || symb == LEFT)
563 		return(0);
564 	num = chars[set];
565 	pos = set + 1;
566 	lc = 0;
567 	if(iflag)
568 		symb = tolower(symb);
569 	for (i=0; i<num; i++) {
570 		c = (unsigned char)chars[pos++];
571 		if(c == '-' && lc != 0 && ++i < num) {
572 			c = (unsigned char)chars[pos++];
573 			if(lc <= symb && symb <= c)
574 				return(torf);
575 		}
576 		if (symb == c)
577 			return (torf);
578 		lc = c;
579 	}
580 	return(!torf);
581 }
582 
583 int
584 notin(int n)
585 {
586 	int i, j, pos;
587 	for (i=1; i<=n; i++) {
588 		if (positions[state[i]] == count) {
589 			pos = state[i] + 1;
590 			for (j=0; j < count; j++)
591 				if (tmpstat[positions[pos++]] != 1) goto nxt;
592 			xstate = i;
593 			return (0);
594 		}
595 		nxt: ;
596 	}
597 	return (1);
598 }
599 
600 void
601 add(int *array, int n)
602 {
603 	int i;
604 	if (nxtpos + count >= maxpos) {
605 		maxpos += MAXPOS + count;
606 		if((positions = (int *)realloc(positions, maxpos *sizeof(int))) == (int *)0)
607 			overflo();
608 	}
609 	array[n] = nxtpos;
610 	positions[nxtpos++] = count;
611 	for (i=3; i <= line; i++) {
612 		if (tmpstat[i] == 1) {
613 			positions[nxtpos++] = i;
614 		}
615 	}
616 }
617 
618 void
619 follow(int v)
620 {
621 	int p;
622 	if (v == line) return;
623 	p = parent[v];
624 	switch(name[p]) {
625 		case STAR:
626 		case PLUS:	cstate(v);
627 				follow(p);
628 				return;
629 
630 		case OR:
631 		case QUEST:	follow(p);
632 				return;
633 
634 		case CAT:	if (v == left[p]) {
635 					if (cstate(right[p]) == 0) {
636 						follow(p);
637 						return;
638 					}
639 				}
640 				else follow(p);
641 				return;
642 		case FINAL:	if (tmpstat[line] != 1) {
643 					tmpstat[line] = 1;
644 					count++;
645 				}
646 				return;
647 	}
648 }
649 
650 #define USAGE "[ -bchHilnsqv ] [ -e exp ] [ -f file ] [ strings ] [ file ] ..."
651 
652 int
653 main(int argc, char **argv)
654 {
655 	char c;
656 	char nl = '\n';
657 	int errflag = 0;
658 
659 	(void)setlocale(LC_ALL, "");
660 
661 #if !defined(TEXT_DOMAIN)		/* Should be defined by cc -D */
662 	#define TEXT_DOMAIN "SYS_TEST"  /* Use this only if it weren't. */
663 #endif
664 	(void) textdomain(TEXT_DOMAIN);
665 
666 	while((c = getopt(argc, argv, "ybcie:f:Hhlnvsq")) != -1)
667 		switch(c) {
668 
669 		case 'b':
670 			bflag++;
671 			continue;
672 
673 		case 'c':
674 			cflag++;
675 			continue;
676 
677 		case 'e':
678 			eflag++;
679 			input = optarg;
680 			continue;
681 
682 		case 'f':
683 			fflag++;
684 			expfile = fopen(optarg, "r");
685 			if(expfile == NULL) {
686 				fprintf(stderr,
687 				  gettext("egrep: can't open %s\n"), optarg);
688 				exit(2);
689 			}
690 			continue;
691 
692 		case 'H':
693 			if (!lflag) /* H is excluded by l as in GNU grep */
694 				Hflag++;
695 			hflag = 0; /* H excludes h */
696 			continue;
697 
698 		case 'h':
699 			hflag++;
700 			Hflag = 0; /* h excludes H */
701 			continue;
702 
703 		case 'y':
704 		case 'i':
705 			iflag++;
706 			continue;
707 
708 		case 'l':
709 			lflag++;
710 			Hflag = 0; /* l excludes H */
711 			continue;
712 
713 		case 'n':
714 			nflag++;
715 			continue;
716 
717 		case 'q':
718 		case 's': /* Solaris: legacy option */
719 			qflag++;
720 			continue;
721 
722 		case 'v':
723 			vflag++;
724 			continue;
725 
726 		case '?':
727 			errflag++;
728 		}
729 	if (errflag || ((argc <= 0) && !fflag && !eflag)) {
730 		fprintf(stderr, gettext("usage: egrep %s\n"), gettext(USAGE));
731 		exit(2);
732 	}
733 	if(!eflag && !fflag) {
734 		input = argv[optind];
735 		optind++;
736 	}
737 
738 	argc -= optind;
739 	argv = &argv[optind];
740 
741 	/* allocate initial space for arrays */
742 	if((name = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
743 		overflo();
744 	if((left = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
745 		overflo();
746 	if((right = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
747 		overflo();
748 	if((parent = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
749 		overflo();
750 	if((foll = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
751 		overflo();
752 	if((tmpstat = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
753 		overflo();
754 	if((initstat = (int *)malloc(MAXLIN*sizeof(int))) == (int *)0)
755 		overflo();
756 	if((chars = (char *)malloc(MAXLIN)) == (char *)0)
757 		overflo();
758 	if((lower = (wchar_t *)malloc(MAXLIN*sizeof(wchar_t))) == (wchar_t *)0)
759 		overflo();
760 	if((upper = (wchar_t *)malloc(MAXLIN*sizeof(wchar_t))) == (wchar_t *)0)
761 		overflo();
762 	if((positions = (int *)malloc(MAXPOS*sizeof(int))) == (int *)0)
763 		overflo();
764 	maxlin = MAXLIN;
765 	maxclin = MAXLIN;
766 	maxwclin = MAXLIN;
767 	maxpos = MAXPOS;
768 
769 	yyparse();
770 
771 	cfoll(line-1);
772 	cgotofn();
773 	nfile = argc;
774 	if (argc<=0) {
775 		execute(0);
776 	}
777 	else while (--argc >= 0) {
778 		if (reinit == 1) clearg();
779 		execute(*argv++);
780 	}
781 	return (badbotch ? 2 : nsucc==0);
782 }
783 
784 void
785 execute(char *file)
786 {
787 	char *p;
788 	int cstat;
789 	wchar_t c;
790 	int t;
791 	long count;
792 	long count1, count2;
793 	long nchars;
794 	int succ;
795 	char *ptr, *ptrend, *lastptr;
796 	char *buf;
797 	long lBufSiz;
798 	FILE *f;
799 	int nlflag;
800 
801 	lBufSiz = EBUFSIZ;
802 	if ((buf = malloc (lBufSiz + EBUFSIZ)) == NULL) {
803 		exit (2); /* out of memory - BAIL */
804 	}
805 
806 	if (file) {
807 		if ((f = fopen(file, "r")) == NULL) {
808 			fprintf(stderr,
809 				gettext("egrep: can't open %s\n"), file);
810 			badbotch=1;
811 			return;
812 		}
813 	} else {
814 		f = stdin;
815 		file = STDIN_FILENAME;
816 	}
817 	lnum = 1;
818 	tln = 0;
819 	if((count = read(fileno(f), buf, EBUFSIZ)) <= 0) {
820 		fclose(f);
821 
822 		if (cflag && !qflag) {
823 			if (Hflag || (nfile > 1 && !hflag))
824 				fprintf(stdout, "%s:", file);
825 			fprintf(stdout, "%lld\n", tln);
826 		}
827 		return;
828 	}
829 
830 	blkno = count;
831 	ptr = buf;
832 	for(;;) {
833 		if((ptrend = memchr(ptr, '\n', buf + count - ptr)) == NULL) {
834 			/*
835 				move the unused partial record to the head of the buffer
836 			*/
837 			if (ptr > buf) {
838 				count = buf + count - ptr;
839 				memmove (buf, ptr, count);
840 				ptr = buf;
841 			}
842 
843 			/*
844 				Get a bigger buffer if this one is full
845 			*/
846 			if(count > lBufSiz) {
847 				/*
848 					expand the buffer
849 				*/
850 				lBufSiz += EBUFSIZ;
851 				if ((buf = realloc (buf, lBufSiz + EBUFSIZ)) == NULL) {
852 					exit (2); /* out of memory - BAIL */
853 				}
854 
855 				ptr = buf;
856 			}
857 
858 			p = buf + count;
859 			if((count1 = read(fileno(f), p, EBUFSIZ)) > 0) {
860 				count += count1;
861 				blkno += count1;
862 				continue;
863 			}
864 			ptrend = ptr + count;
865 			nlflag = 0;
866 		} else
867 			nlflag = 1;
868 		*ptrend = '\n';
869 		p = ptr;
870 		lastptr = ptr;
871 		cstat = istat;
872 		succ = 0;
873 		for(;;) {
874 			if(out[cstat]) {
875 				if(multibyte && p > ptr) {
876 					wchar_t wchar;
877 					int length;
878 					char *endptr = p;
879 					p = lastptr;
880 					while(p < endptr) {
881 						length = mbtowc(&wchar, p, MB_LEN_MAX);
882 						if(length <= 1)
883 							p++;
884 						else
885 							p += length;
886 					}
887 					if(p == endptr) {
888 						succ = !vflag;
889 						break;
890 					}
891 					cstat = 1;
892 					length = mbtowc(&wchar, lastptr, MB_LEN_MAX);
893 					if(length <= 1)
894 						lastptr++;
895 					else
896 						lastptr += length;
897 					p = lastptr;
898 					continue;
899 				}
900 				succ = !vflag;
901 				break;
902 			}
903 			c = (unsigned char)*p++;
904 			if ((t = gotofn[cstat][c]) == 0)
905 				cstat = nxtst(cstat, c);
906 			else
907 				cstat = t;
908 			if(c == RIGHT) {
909 				if(out[cstat]) {
910 					succ = !vflag;
911 					break;
912 				}
913 				succ = vflag;
914 				break;
915 			}
916 		}
917 		if (succ) {
918 			nsucc = 1;
919 			if (lflag || qflag) {
920 				if (!qflag)
921 					(void) printf("%s\n", file);
922 				fclose(f);
923 				return;
924 			}
925 			if (cflag) {
926 				tln++;
927 			} else {
928 				if (Hflag || (nfile > 1 && !hflag))
929 					printf("%s:", file);
930 				if (bflag) {
931 					nchars = blkno - (buf + count - ptrend) - 2;
932 					if(nlflag)
933 						nchars++;
934 					printf("%lld:", nchars/BLKSIZE);
935 				}
936 				if (nflag)
937 					printf("%lld:", lnum);
938 				if(nlflag)
939 					nchars = ptrend - ptr + 1;
940 				else
941 					nchars = ptrend - ptr;
942 				fwrite(ptr, (size_t)1, (size_t)nchars, stdout);
943 			}
944 		}
945 		if(!nlflag)
946 			break;
947 		ptr = ptrend + 1;
948 		if(ptr >= buf + count) {
949 			ptr = buf;
950 			if((count = read(fileno(f), buf, EBUFSIZ)) <= 0)
951 				break;
952 			blkno += count;
953 		}
954 		lnum++;
955 		if (reinit == 1)
956 			clearg();
957 	}
958 	fclose(f);
959 	if (cflag && !qflag) {
960 		if (Hflag || (nfile > 1 && !hflag))
961 			printf("%s:", file);
962 		printf("%lld\n", tln);
963 	}
964 }
965 
966 void
967 clearg(void)
968 {
969 	int i, k;
970 	for (i=1; i<=nstate; i++)
971 		out[i] = 0;
972 	for (i=1; i<=nstate; i++)
973 		for (k=0; k<NCHARS; k++)
974 			gotofn[i][k] = 0;
975 	nstate = 1;
976 	nxtpos = inxtpos;
977 	reinit = 0;
978 	count = 0;
979 	for (i=3; i<=line; i++) tmpstat[i] = 0;
980 	if (cstate(line-1)==0) {
981 		tmpstat[line] = 1;
982 		count++;
983 		out[1] = 1;
984 	}
985 	for (i=3; i<=line; i++) initstat[i] = tmpstat[i];
986 	count--;		/*leave out position 1 */
987 	icount = count;
988 	tmpstat[1] = 0;
989 	add(state, 1);
990 	istat = nxtst(1, LEFT);
991 }
992 
993 int
994 mdotenter(void)
995 {
996 	int i, x1, x2;
997 	x1 = enter(DOT);
998 	x2 = enter(MDOT);
999 	for(i = 1; i < (int) eucw1; i++)
1000 		x2 = node(CAT, x2, enter(MDOT));
1001 	x1 = node(OR, x1, x2);
1002 	if(eucw2) {
1003 		x2 = enter('\216');
1004 		for(i = 1; i <= (int) eucw2; i++)
1005 			x2 = node(CAT, x2, enter(MDOT));
1006 		x1 = node(OR, x1, x2);
1007 	}
1008 	if(eucw3) {
1009 		x2 = enter('\217');
1010 		for(i = 1; i <= (int) eucw3; i++)
1011 			x2 = node(CAT, x2, enter(MDOT));
1012 		x1 = node(OR, x1, x2);
1013 	}
1014 	return(x1);
1015 }
1016 
1017 int
1018 mchar(wchar_t c)
1019 {
1020 	char multichar[MB_LEN_MAX+1];
1021 	char *p;
1022 	int x1, lc, length;
1023 
1024 	length = wctomb(multichar, c);
1025 	p = multichar;
1026 	*(p + length) = '\0';
1027 	x1 = enter((unsigned char)*p++);
1028 	while(lc = (unsigned char)*p++)
1029 		x1 = node(CAT, x1, enter(lc));
1030 	return(x1);
1031 }
1032 
1033 int
1034 ccl(int type)
1035 {
1036 	wchar_t c, lc;
1037 	char multic1[MB_LEN_MAX];
1038 	char multic2[MB_LEN_MAX];
1039 	int x1, x2, length, current, last, cclcnt;
1040 	x2 = 0;
1041 	current = 0;
1042 	last = genrange(type);
1043 	nxtchar = count + 1;
1044 	cclcnt = 0;
1045 	/* create usual character class for single byte characters */
1046 	while(current <= last && (isascii(c = lower[current]) || c <= 0377 && iscntrl(c))) {
1047 		cclcnt++;
1048 		chars[nxtchar++] = c;
1049 		if(lower[current] != upper[current]) {
1050 			chars[nxtchar++] = '-';
1051 			chars[nxtchar++] = upper[current];
1052 			cclcnt += 2;
1053 		}
1054 		current++;
1055 	}
1056 
1057 	if(cclcnt)
1058 		chars[count] = cclcnt;
1059 	else
1060 		nxtchar = count;
1061 	if(current > 0)
1062 		/* single byte part of character class */
1063 		x2 = cclenter(type);
1064 	else if(type == NCCL)
1065 		/* all single byte characters match */
1066 		x2 = enter(DOT);
1067 	while(current <= last) {
1068 		if(upper[current] == lower[current])
1069 			x1 = mchar(lower[current]);
1070 		else {
1071 			length = wctomb(multic1, lower[current]);
1072 			wctomb(multic2, upper[current]);
1073 			x1 = range((unsigned char *)multic1,
1074 			    (unsigned char *)multic2, length);
1075 		}
1076 		if(x2)
1077 			x2 = node(OR, x2, x1);
1078 		else
1079 			x2 = x1;
1080 		current++;
1081 	}
1082 	return x2;
1083 }
1084 
1085 int
1086 range(unsigned char *p1, unsigned char *p2, int length)
1087 {
1088 	char multic[MB_LEN_MAX+1];
1089 	char *p;
1090 	int i, x1, x2;
1091 	if(length == 1)
1092 		return(classenter(*p1, *p2));
1093 	if(p1[0] == p2[0])
1094 		return(node(CAT, enter(p1[0]), range(p1+1, p2+1, length - 1)));
1095 	p = multic;
1096 	for(i = 1; i < length; i++)
1097 		*p++ = 0377;
1098 	x1 = node(CAT, enter(p1[0]),
1099 	    range(p1+1, (unsigned char *)multic, length - 1));
1100 	if((unsigned char)(p1[0] + 1) < p2[0]) {
1101 		x2 = classenter(p1[0] + 1, p2[0] - 1);
1102 		for(i = 1; i < length; i++)
1103 			x2 = node(CAT, x2, enter(MDOT));
1104 		x1 = node(OR, x1, x2);
1105 	}
1106 	p = multic;
1107 	for(i = 1; i < length; i++)
1108 		*p++ = 0200;
1109 	x2 = node(CAT, enter(p2[0]),
1110 	    range((unsigned char *)multic, p2+1, length - 1));
1111 	return node(OR, x1, x2);
1112 }
1113 
1114 int
1115 classenter(int x1, int x2)
1116 {
1117 	static int max, min;
1118 	if(!max) {
1119 		int i;
1120 		for(i = 0200; i <= 0377; i++)
1121 			if(!iscntrl(i))
1122 				break;
1123 		min = i;
1124 		for(i = 0377; i >= 0200; i--)
1125 			if(!iscntrl(i))
1126 				break;
1127 		max = i;
1128 	}
1129 	if(x1 <= min && x2 >= max)
1130 		return enter(MDOT);
1131 	if(nxtchar + 4 >= maxclin)
1132 		if(allocchars() == 0)
1133 			overflo();
1134 	count = nxtchar++;
1135 	chars[nxtchar++] = x1;
1136 	chars[nxtchar++] = '-';
1137 	chars[nxtchar++] = x2;
1138 	chars[count] = 3;
1139 	return cclenter(MCCL);
1140 }
1141 
1142 int
1143 genrange(int type)
1144 {
1145 	char *p, *endp;
1146 	int current, nel, i, last, length;
1147 	wchar_t c, lc;
1148 
1149 	current = 0;
1150 	p = &chars[count+1];
1151 	endp = &chars[count+1] + chars[count];
1152 	lc = 0;
1153 
1154 	/* convert character class into union of ranges */
1155 	while(p < endp) {
1156 		length = mbtowc(&c, p, MB_LEN_MAX);
1157 		p += length;
1158 		if(c == '-' && lc != 0) {
1159 			length = mbtowc(&c, p, MB_LEN_MAX);
1160 			upper[current-1] = c;
1161 			p += length;
1162 		} else {
1163 			lower[current] = c;
1164 			upper[current++] = c;
1165 		}
1166 		lc = c;
1167 	}
1168 	nel = current;
1169 	/* sort lower and upper bounds of ranges */
1170 	qsort((char *)lower, nel, sizeof(wchar_t), compare);
1171 	qsort((char *)upper, nel, sizeof(wchar_t), compare);
1172 	last = current - 1;
1173 	current = 0;
1174 	/* combine overlapping or adjacent ranges */
1175 	for(i = 0; i < last; i++)
1176 		if(upper[i] >= lower[i+1] - 1)
1177 			upper[current] = upper[i+1];
1178 		else {
1179 			lower[++current] = lower[i+1];
1180 			upper[current] = upper[i+1];
1181 		}
1182 	if(type == NCCL) {
1183 		/* find complement of character class */
1184 		int j, next;
1185 		i = 0;
1186 		while(i <= current && isascii(c=lower[i]) || c <= 0377 && iscntrl(c))
1187 			i++;
1188 		if(i > current) {
1189 			/* match all multibyte characters */
1190 			if(eucw2) {
1191 				lower[i] = maxmin(WCHAR_CS2, 0);
1192 				upper[i++] = maxmin(WCHAR_CS2, 1);
1193 			}
1194 			if(eucw3) {
1195 				lower[i] = maxmin(WCHAR_CS3, 0);
1196 				upper[i++] = maxmin(WCHAR_CS3, 1);
1197 			}
1198 			lower[i] = maxmin(WCHAR_CS1, 0);
1199 			upper[i++] = maxmin(WCHAR_CS1, 1);
1200 			return i - 1;
1201 		}
1202 		next = current + 1;
1203 		if(next + current + 2 >= maxwclin) {
1204 			maxwclin += MAXLIN + next + current + 2;
1205 			if((lower = (wchar_t *)realloc(lower, maxwclin *sizeof(wchar_t))) == (wchar_t *)0 ||
1206 			   (upper = (wchar_t *)realloc(upper, maxwclin * sizeof(wchar_t))) == (wchar_t *)0)
1207 				overflo();
1208 		}
1209 		if(eucw2 && lower[i] > maxmin(WCHAR_CS2, 0)) {
1210 			lower[next] = maxmin(WCHAR_CS2, 0);
1211 			if((lower[i] & WCHAR_CSMASK) != WCHAR_CS2) {
1212 				upper[next++] = maxmin(WCHAR_CS2, 1);
1213 				if((lower[i] & WCHAR_CSMASK) == WCHAR_CS1 && eucw3) {
1214 					lower[next] = maxmin(WCHAR_CS3, 0);
1215 					upper[next++] = maxmin(WCHAR_CS3, 1);
1216 				}
1217 				if(lower[i] > maxmin(lower[i] & WCHAR_CSMASK, 0)) {
1218 					lower[next] = maxmin(lower[i] & WCHAR_CSMASK, 0);
1219 					upper[next++] = lower[i] - 1;
1220 				}
1221 			} else
1222 				upper[next++] = lower[i] - 1;
1223 		} else if(lower[i] > maxmin(lower[i] & WCHAR_CSMASK, 0)) {
1224 			lower[next] = maxmin(lower[i] & WCHAR_CSMASK, 0);
1225 			upper[next++] = lower[i] - 1;
1226 		}
1227 		for(j = i; j < current; j++) {
1228 			if(upper[j] < maxmin(upper[j] & WCHAR_CSMASK, 1)) {
1229 				lower[next] = upper[j] + 1;
1230 				if((upper[j] & WCHAR_CSMASK) != (lower[j+1] & WCHAR_CSMASK)) {
1231 					upper[next++] = maxmin(upper[j] & WCHAR_CSMASK, 1);
1232 					if(eucw3 && (upper[j] & WCHAR_CSMASK) == WCHAR_CS2 && (lower[j+1] & WCHAR_CSMASK) == WCHAR_CS1) {
1233 						lower[next] = maxmin(WCHAR_CS3, 0);
1234 						upper[next++] = maxmin(WCHAR_CS3, 1);
1235 					}
1236 					if(lower[j+1] > maxmin(lower[j+1] & WCHAR_CSMASK, 0)) {
1237 						lower[next] = maxmin(lower[j+1] & WCHAR_CSMASK, 0);
1238 						upper[next++] = lower[j+1] - 1;
1239 					}
1240 				} else
1241 					upper[next++] = lower[j+1] - 1;
1242 			} else if(lower[j+1] > maxmin(lower[j+1], 0)) {
1243 				lower[next] = maxmin(lower[j+1], 0);
1244 				upper[next++] = lower[j+1] - 1;
1245 			}
1246 		}
1247 		if(upper[current] < maxmin(upper[current] & WCHAR_CSMASK, 1)) {
1248 			lower[next] = upper[current] + 1;
1249 			upper[next++] = maxmin(upper[current] & WCHAR_CSMASK, 1);
1250 		}
1251 		if((upper[current] & WCHAR_CSMASK) != WCHAR_CS1) {
1252 			if((upper[current] & WCHAR_CSMASK) == WCHAR_CS2 && eucw3) {
1253 				lower[next] = maxmin(WCHAR_CS3, 0);
1254 				upper[next++] = maxmin(WCHAR_CS3, 1);
1255 			}
1256 			lower[next] = maxmin(WCHAR_CS1, 0);
1257 			upper[next++] = maxmin(WCHAR_CS1, 1);
1258 		}
1259 		for(j = current + 1; j < next; j++) {
1260 			lower[i] = lower[j];
1261 			upper[i++] = upper[j];
1262 		}
1263 		current = i - 1;
1264 	}
1265 	return(current);
1266 }
1267 
1268 int
1269 compare(wchar_t *c, wchar_t *d)
1270 {
1271 	if(*c < *d)
1272 		return -1;
1273 	if(*c == *d)
1274 		return 0;
1275 	return 1;
1276 }
1277 
1278 wchar_t
1279 maxmin(wchar_t c, int flag)
1280 {
1281 	static wchar_t minmax1[2], minmax2[2], minmax3[2];
1282 
1283 	if(!minmax1[0]) {
1284 		/* compute min and max process codes for all code sets */
1285 		int length, i;
1286 		char multic[MB_LEN_MAX], minmax[2];
1287 		for(i = 0377; i >= 0200; i--)
1288 			if(!iscntrl(i))
1289 				break;
1290 		minmax[1] = i;
1291 		for(i = 0240; i <= 0377; i++)
1292 			if(!iscntrl(i))
1293 				break;
1294 		minmax[0] = i;
1295 		for(i = 0; i <= 1; i++) {
1296 			length = MB_LEN_MAX;
1297 			while(length--)
1298 				multic[length] = minmax[i];
1299 			mbtowc(&minmax1[i], multic, MB_LEN_MAX);
1300 			if(eucw2) {
1301 				multic[0] = SS2;
1302 				mbtowc(&minmax2[i], multic, MB_LEN_MAX);
1303 			}
1304 			if(eucw3) {
1305 				multic[0] = SS3;
1306 				mbtowc(&minmax3[i], multic, MB_LEN_MAX);
1307 			}
1308 		}
1309 	}
1310 	switch(c) {
1311 		case WCHAR_CS1: return minmax1[flag];
1312 		case WCHAR_CS2: return minmax2[flag];
1313 		case WCHAR_CS3: return minmax3[flag];
1314 	}
1315 
1316 	/* NOTREACHED */
1317 	return (0);
1318 }
1319