/*
 * grep.
 */
#include <stdio.h>

#define	LMAX	128
#define PMAX	128

#define	END	0
#define CHAR	1
#define BOL	2
#define EOL	3
#define	ANY	4
#define CLASS	5
#define	NCLASS	6
#define CLOSURE	7

int	cflag;
int	fflag;
int	nflag;
int	vflag;
char	*pp;

char	lbuf[LMAX];
char	pbuf[PMAX];

main(argc, argv)
char *argv[];
{
	register char *p;
	register int c, i;
	int nf, gp;
	FILE *f;

	nf = argc-1;
	gp = 0;
	for(i=1; i<argc; ++i) {
		p = argv[i];
		if(*p == '-') {
			++p;
			while(c = *p++)
				switch(lower(c)) {

				case 'c':
					++cflag;
					break;

				case 'f':
					++fflag;
					break;

				case 'n':
					++nflag;
					break;

				case 'v':
					++vflag;
					break;

				default:
					usage();
				}
			argv[i] = 0;
			--nf;
		} else if(!gp) {
			compile(p);
			argv[i] = 0;
			++gp;
			--nf;
		}
	}
	if(!gp)
		usage();
	if(nf == 0)
		grep(stdin, 0);
	else
		for(i=1; i<argc; ++i)
			if(p = argv[i]) {
				if((f=fopen(p, "r")) == NULL)
					cant(p);
				else {
					grep(f, p);
					fclose(f);
				}
			}
}

grep(fp, fn)
FILE *fp;
char *fn;
{
	register int lno, count, m;

	lno = 0;
	count = 0;
	while(fgets(lbuf, fp)) {
		++lno;
		m = match();
		if((m && !vflag) || (!m && vflag)) {
			++count;
			if(!cflag) {
				if(fflag && fn) {
					file(fn);
					fn = 0;
				}
				if(nflag)
					printf("%d\t", lno);
				printf("%s\n", lbuf);
			}
		}
	}
	if(cflag) {
		if(fflag && fn)
			file(fn);
		printf("%d\n", count);
	}
}

compile(s)
register char *s;
{
	register char *lp;
	register int c;
	int o;
	char *spp, *cclass();

	pp = pbuf;
	while(c = *s++) {
		/*
		 * Closure is special.
		 */
		if(c == '*') {
			if(pp==pbuf || (o=pp[-1])==BOL || o==EOL || o==CLOSURE)
				badpat();
			store(END);
			store(END);
			spp = pp;
			while(--pp > lp)
				*pp = pp[-1];
			*pp = CLOSURE;
			pp = spp;
			continue;
		}
		/*
		 * All the rest.
		 */
		lp = pp;
		switch(c) {

		case '^':
			store(BOL);
			break;

		case '$':
			store(EOL);
			break;

		case '.':
			store(ANY);
			break;

		case '[':
			s = cclass(s);
			break;

		case '\\':
			if(*s)
				c = *s++;

		default:
			store(CHAR);
			store(lower(c));
		}
	}
	store(END);
}

char *
cclass(s)
register char *s;
{
	register char *cp;
	register int c;
	int o;

	o = CLASS;
	if(*s == '^') {
		++s;
		o = NCLASS;
	}
	store(o);
	cp = pp;
	store(0);  /* Byte count */
	while((c=*s++) && c!=']') {
		if(c == '\\')
			if((c=*s++) == '\0')
				badpat();
		store(lower(c));
		if(++*cp == 0)
			error("Class too complex\n");
	}
	if(c != ']')
		badpat();
	return(s);
}

store(op)
{
	if(pp >= &pbuf[PMAX])
		error("Pattern too complex\n");
	*pp++ = op;
}

match()
{
	register char *l;
	char *pmatch();

	l = lbuf;
	while(*l) {
		if(pmatch(l, pbuf))
			return(1);
		++l;
	}
	return(0);
}

char *
pmatch(l, p)
register char *l, *p;
{
	register char *e;
	int op, c, n;
	char *are;

	while((op=*p++) != END)
		switch(op) {

		case CHAR:
			if(lower(*l++) != *p++)
				return(0);
			break;

		case BOL:
			if(l != lbuf)
				return(0);
			break;

		case EOL:
			if(*l != '\0')
				return(0);
			break;

		case ANY:
			if(*l++ == '\0')
				return(0);
			break;

		case CLASS:
			c = lower(*l++);
			if((n=*p++&0377) == 0)
				return(0);
			do {
				if(c == *p++)
					break;
			} while(--n);
			if(n == 0)
				return(0);
			p += n-1;
			break;

		case NCLASS:
			c = lower(*l++);
			if((n=*p++&0377) == 0)
				break;
			do {
				if(c == *p++)
					break;
			} while(--n);
			if(n)
				return(0);
			break;

		case CLOSURE:
			are = l;
			while(e = pmatch(l, p))
				l = e;
			while(*p++ != END)
				;
			while(l >= are) {
				if(e = pmatch(l, p))
					return(e);
				--l;
			}
			return(0);

		default:
			error("Cannot happen -- match\n");
		}
	return(l);
}

lower(c)
register int c;
{
	if(c>='A' && c<='Z')
		c += 'a'-'A';
	return(c);
}

badpat()
{
	error("Bad pattern\n");
}

file(s)
char *s;
{
	printf("File %s:\n", s);
}

cant(s)
char *s;
{
	fprintf(stderr, "%s: cannot open\n", s);
}

usage()
{
	error("Usage: grep [-cfnv] pattern [file ...]\n");
}
