xref: /plan9/sys/src/cmd/grep/sub.c (revision 82bf8890d63412a131475350a21c237cc4c556db)
17dd7cddfSDavid du Colombier #include	"grep.h"
27dd7cddfSDavid du Colombier 
37dd7cddfSDavid du Colombier void*
mal(int n)47dd7cddfSDavid du Colombier mal(int n)
57dd7cddfSDavid du Colombier {
67dd7cddfSDavid du Colombier 	static char *s;
77dd7cddfSDavid du Colombier 	static int m = 0;
87dd7cddfSDavid du Colombier 	void *v;
97dd7cddfSDavid du Colombier 
107dd7cddfSDavid du Colombier 	n = (n+3) & ~3;
117dd7cddfSDavid du Colombier 	if(m < n) {
127dd7cddfSDavid du Colombier 		if(n > Nhunk) {
137dd7cddfSDavid du Colombier 			v = sbrk(n);
147dd7cddfSDavid du Colombier 			memset(v, 0, n);
157dd7cddfSDavid du Colombier 			return v;
167dd7cddfSDavid du Colombier 		}
177dd7cddfSDavid du Colombier 		s = sbrk(Nhunk);
187dd7cddfSDavid du Colombier 		m = Nhunk;
197dd7cddfSDavid du Colombier 	}
207dd7cddfSDavid du Colombier 	v = s;
217dd7cddfSDavid du Colombier 	s += n;
227dd7cddfSDavid du Colombier 	m -= n;
237dd7cddfSDavid du Colombier 	memset(v, 0, n);
247dd7cddfSDavid du Colombier 	return v;
257dd7cddfSDavid du Colombier }
267dd7cddfSDavid du Colombier 
277dd7cddfSDavid du Colombier State*
sal(int n)287dd7cddfSDavid du Colombier sal(int n)
297dd7cddfSDavid du Colombier {
307dd7cddfSDavid du Colombier 	State *s;
317dd7cddfSDavid du Colombier 
327dd7cddfSDavid du Colombier 	s = mal(sizeof(*s));
3380ee5cbfSDavid du Colombier //	s->next = mal(256*sizeof(*s->next));
347dd7cddfSDavid du Colombier 	s->count = n;
357dd7cddfSDavid du Colombier 	s->re = mal(n*sizeof(*state0->re));
367dd7cddfSDavid du Colombier 	return s;
377dd7cddfSDavid du Colombier }
387dd7cddfSDavid du Colombier 
397dd7cddfSDavid du Colombier Re*
ral(int type)407dd7cddfSDavid du Colombier ral(int type)
417dd7cddfSDavid du Colombier {
427dd7cddfSDavid du Colombier 	Re *r;
437dd7cddfSDavid du Colombier 
447dd7cddfSDavid du Colombier 	r = mal(sizeof(*r));
457dd7cddfSDavid du Colombier 	r->type = type;
467dd7cddfSDavid du Colombier 	maxfollow++;
477dd7cddfSDavid du Colombier 	return r;
487dd7cddfSDavid du Colombier }
497dd7cddfSDavid du Colombier 
507dd7cddfSDavid du Colombier void
error(char * s)517dd7cddfSDavid du Colombier error(char *s)
527dd7cddfSDavid du Colombier {
537dd7cddfSDavid du Colombier 	fprint(2, "grep: internal error: %s\n", s);
547dd7cddfSDavid du Colombier 	exits(s);
557dd7cddfSDavid du Colombier }
567dd7cddfSDavid du Colombier 
577dd7cddfSDavid du Colombier int
countor(Re * r)587dd7cddfSDavid du Colombier countor(Re *r)
597dd7cddfSDavid du Colombier {
607dd7cddfSDavid du Colombier 	int n;
617dd7cddfSDavid du Colombier 
627dd7cddfSDavid du Colombier 	n = 0;
637dd7cddfSDavid du Colombier loop:
647dd7cddfSDavid du Colombier 	switch(r->type) {
657dd7cddfSDavid du Colombier 	case Tor:
667dd7cddfSDavid du Colombier 		n += countor(r->alt);
677dd7cddfSDavid du Colombier 		r = r->next;
687dd7cddfSDavid du Colombier 		goto loop;
697dd7cddfSDavid du Colombier 	case Tclass:
707dd7cddfSDavid du Colombier 		return n + r->hi - r->lo + 1;
717dd7cddfSDavid du Colombier 	}
727dd7cddfSDavid du Colombier 	return n;
737dd7cddfSDavid du Colombier }
747dd7cddfSDavid du Colombier 
757dd7cddfSDavid du Colombier Re*
oralloc(int t,Re * r,Re * b)767dd7cddfSDavid du Colombier oralloc(int t, Re *r, Re *b)
777dd7cddfSDavid du Colombier {
787dd7cddfSDavid du Colombier 	Re *a;
797dd7cddfSDavid du Colombier 
807dd7cddfSDavid du Colombier 	if(b == 0)
817dd7cddfSDavid du Colombier 		return r;
827dd7cddfSDavid du Colombier 	a = ral(t);
837dd7cddfSDavid du Colombier 	a->alt = r;
847dd7cddfSDavid du Colombier 	a->next = b;
857dd7cddfSDavid du Colombier 	return a;
867dd7cddfSDavid du Colombier }
877dd7cddfSDavid du Colombier 
887dd7cddfSDavid du Colombier void
case1(Re * c,Re * r)897dd7cddfSDavid du Colombier case1(Re *c, Re *r)
907dd7cddfSDavid du Colombier {
917dd7cddfSDavid du Colombier 	int n;
927dd7cddfSDavid du Colombier 
937dd7cddfSDavid du Colombier loop:
947dd7cddfSDavid du Colombier 	switch(r->type) {
957dd7cddfSDavid du Colombier 	case Tor:
967dd7cddfSDavid du Colombier 		case1(c, r->alt);
977dd7cddfSDavid du Colombier 		r = r->next;
987dd7cddfSDavid du Colombier 		goto loop;
997dd7cddfSDavid du Colombier 
1007dd7cddfSDavid du Colombier 	case Tclass:	/* add to character */
1017dd7cddfSDavid du Colombier 		for(n=r->lo; n<=r->hi; n++)
1027dd7cddfSDavid du Colombier 			c->cases[n] = oralloc(Tor, r->next, c->cases[n]);
1037dd7cddfSDavid du Colombier 		break;
1047dd7cddfSDavid du Colombier 
1057dd7cddfSDavid du Colombier 	default:	/* add everything unknown to next */
1067dd7cddfSDavid du Colombier 		c->next = oralloc(Talt, r, c->next);
1077dd7cddfSDavid du Colombier 		break;
1087dd7cddfSDavid du Colombier 	}
1097dd7cddfSDavid du Colombier }
1107dd7cddfSDavid du Colombier 
1117dd7cddfSDavid du Colombier Re*
addcase(Re * r)1127dd7cddfSDavid du Colombier addcase(Re *r)
1137dd7cddfSDavid du Colombier {
1147dd7cddfSDavid du Colombier 	int i, n;
1157dd7cddfSDavid du Colombier 	Re *a;
1167dd7cddfSDavid du Colombier 
1177dd7cddfSDavid du Colombier 	if(r->gen == gen)
1187dd7cddfSDavid du Colombier 		return r;
1197dd7cddfSDavid du Colombier 	r->gen = gen;
1207dd7cddfSDavid du Colombier 	switch(r->type) {
1217dd7cddfSDavid du Colombier 	default:
1227dd7cddfSDavid du Colombier 		error("addcase");
1237dd7cddfSDavid du Colombier 
1247dd7cddfSDavid du Colombier 	case Tor:
1257dd7cddfSDavid du Colombier 		n = countor(r);
1267dd7cddfSDavid du Colombier 		if(n >= Caselim) {
1277dd7cddfSDavid du Colombier 			a = ral(Tcase);
1287dd7cddfSDavid du Colombier 			a->cases = mal(256*sizeof(*a->cases));
1297dd7cddfSDavid du Colombier 			case1(a, r);
1307dd7cddfSDavid du Colombier 			for(i=0; i<256; i++)
1317dd7cddfSDavid du Colombier 				if(a->cases[i]) {
1327dd7cddfSDavid du Colombier 					r = a->cases[i];
1337dd7cddfSDavid du Colombier 					if(countor(r) < n)
1347dd7cddfSDavid du Colombier 						a->cases[i] = addcase(r);
1357dd7cddfSDavid du Colombier 				}
1367dd7cddfSDavid du Colombier 			return a;
1377dd7cddfSDavid du Colombier 		}
1387dd7cddfSDavid du Colombier 		return r;
1397dd7cddfSDavid du Colombier 
1407dd7cddfSDavid du Colombier 	case Talt:
1417dd7cddfSDavid du Colombier 		r->next = addcase(r->next);
1427dd7cddfSDavid du Colombier 		r->alt = addcase(r->alt);
1437dd7cddfSDavid du Colombier 		return r;
1447dd7cddfSDavid du Colombier 
1457dd7cddfSDavid du Colombier 	case Tbegin:
1467dd7cddfSDavid du Colombier 	case Tend:
1477dd7cddfSDavid du Colombier 	case Tclass:
1487dd7cddfSDavid du Colombier 		return r;
1497dd7cddfSDavid du Colombier 	}
1507dd7cddfSDavid du Colombier }
1517dd7cddfSDavid du Colombier 
1527dd7cddfSDavid du Colombier void
str2top(char * p)1537dd7cddfSDavid du Colombier str2top(char *p)
1547dd7cddfSDavid du Colombier {
1557dd7cddfSDavid du Colombier 	Re2 oldtop;
1567dd7cddfSDavid du Colombier 
1577dd7cddfSDavid du Colombier 	oldtop = topre;
1587dd7cddfSDavid du Colombier 	input = p;
1591052a86aSDavid du Colombier 	if (*p == '\0')
160*82bf8890SDavid du Colombier 		yyerror("empty pattern");	/* can't be a file name here */
161*82bf8890SDavid du Colombier 	if (!flags['f'])
162*82bf8890SDavid du Colombier 		pattern = p;
1637dd7cddfSDavid du Colombier 	topre.beg = 0;
1647dd7cddfSDavid du Colombier 	topre.end = 0;
1657dd7cddfSDavid du Colombier 	yyparse();
1667dd7cddfSDavid du Colombier 	gen++;
1677dd7cddfSDavid du Colombier 	if(topre.beg == 0)
1687dd7cddfSDavid du Colombier 		yyerror("syntax");
1697dd7cddfSDavid du Colombier 	if(oldtop.beg)
1707dd7cddfSDavid du Colombier 		topre = re2or(oldtop, topre);
1717dd7cddfSDavid du Colombier }
1727dd7cddfSDavid du Colombier 
1737dd7cddfSDavid du Colombier void
appendnext(Re * a,Re * b)1747dd7cddfSDavid du Colombier appendnext(Re *a, Re *b)
1757dd7cddfSDavid du Colombier {
1767dd7cddfSDavid du Colombier 	Re *n;
1777dd7cddfSDavid du Colombier 
1787dd7cddfSDavid du Colombier 	while(n = a->next)
1797dd7cddfSDavid du Colombier 		a = n;
1807dd7cddfSDavid du Colombier 	a->next = b;
1817dd7cddfSDavid du Colombier }
1827dd7cddfSDavid du Colombier 
1837dd7cddfSDavid du Colombier void
patchnext(Re * a,Re * b)1847dd7cddfSDavid du Colombier patchnext(Re *a, Re *b)
1857dd7cddfSDavid du Colombier {
1867dd7cddfSDavid du Colombier 	Re *n;
1877dd7cddfSDavid du Colombier 
1887dd7cddfSDavid du Colombier 	while(a) {
1897dd7cddfSDavid du Colombier 		n = a->next;
1907dd7cddfSDavid du Colombier 		a->next = b;
1917dd7cddfSDavid du Colombier 		a = n;
1927dd7cddfSDavid du Colombier 	}
1937dd7cddfSDavid du Colombier }
1947dd7cddfSDavid du Colombier 
1957dd7cddfSDavid du Colombier int
getrec(void)1967dd7cddfSDavid du Colombier getrec(void)
1977dd7cddfSDavid du Colombier {
1987dd7cddfSDavid du Colombier 	int c;
1997dd7cddfSDavid du Colombier 
2007dd7cddfSDavid du Colombier 	if(flags['f']) {
2017dd7cddfSDavid du Colombier 		c = Bgetc(rein);
2027dd7cddfSDavid du Colombier 		if(c <= 0)
2037dd7cddfSDavid du Colombier 			return 0;
2047dd7cddfSDavid du Colombier 	} else
2057dd7cddfSDavid du Colombier 		c = *input++ & 0xff;
2067dd7cddfSDavid du Colombier 	if(flags['i'] && c >= 'A' && c <= 'Z')
2077dd7cddfSDavid du Colombier 		c += 'a'-'A';
2087dd7cddfSDavid du Colombier 	if(c == '\n')
2097dd7cddfSDavid du Colombier 		lineno++;
2107dd7cddfSDavid du Colombier 	return c;
2117dd7cddfSDavid du Colombier }
2127dd7cddfSDavid du Colombier 
2137dd7cddfSDavid du Colombier Re2
re2cat(Re2 a,Re2 b)2147dd7cddfSDavid du Colombier re2cat(Re2 a, Re2 b)
2157dd7cddfSDavid du Colombier {
2167dd7cddfSDavid du Colombier 	Re2 c;
2177dd7cddfSDavid du Colombier 
2187dd7cddfSDavid du Colombier 	c.beg = a.beg;
2197dd7cddfSDavid du Colombier 	c.end = b.end;
2207dd7cddfSDavid du Colombier 	patchnext(a.end, b.beg);
2217dd7cddfSDavid du Colombier 	return c;
2227dd7cddfSDavid du Colombier }
2237dd7cddfSDavid du Colombier 
2247dd7cddfSDavid du Colombier Re2
re2star(Re2 a)2257dd7cddfSDavid du Colombier re2star(Re2 a)
2267dd7cddfSDavid du Colombier {
2277dd7cddfSDavid du Colombier 	Re2 c;
2287dd7cddfSDavid du Colombier 
2297dd7cddfSDavid du Colombier 	c.beg = ral(Talt);
2307dd7cddfSDavid du Colombier 	c.beg->alt = a.beg;
2317dd7cddfSDavid du Colombier 	patchnext(a.end, c.beg);
2327dd7cddfSDavid du Colombier 	c.end = c.beg;
2337dd7cddfSDavid du Colombier 	return c;
2347dd7cddfSDavid du Colombier }
2357dd7cddfSDavid du Colombier 
2367dd7cddfSDavid du Colombier Re2
re2or(Re2 a,Re2 b)2377dd7cddfSDavid du Colombier re2or(Re2 a, Re2 b)
2387dd7cddfSDavid du Colombier {
2397dd7cddfSDavid du Colombier 	Re2 c;
2407dd7cddfSDavid du Colombier 
2417dd7cddfSDavid du Colombier 	c.beg = ral(Tor);
2427dd7cddfSDavid du Colombier 	c.beg->alt = b.beg;
2437dd7cddfSDavid du Colombier 	c.beg->next = a.beg;
2447dd7cddfSDavid du Colombier 	c.end = b.end;
2457dd7cddfSDavid du Colombier 	appendnext(c.end,  a.end);
2467dd7cddfSDavid du Colombier 	return c;
2477dd7cddfSDavid du Colombier }
2487dd7cddfSDavid du Colombier 
2497dd7cddfSDavid du Colombier Re2
re2char(int c0,int c1)2507dd7cddfSDavid du Colombier re2char(int c0, int c1)
2517dd7cddfSDavid du Colombier {
2527dd7cddfSDavid du Colombier 	Re2 c;
2537dd7cddfSDavid du Colombier 
2547dd7cddfSDavid du Colombier 	c.beg = ral(Tclass);
2557dd7cddfSDavid du Colombier 	c.beg->lo = c0 & 0xff;
2567dd7cddfSDavid du Colombier 	c.beg->hi = c1 & 0xff;
2577dd7cddfSDavid du Colombier 	c.end = c.beg;
2587dd7cddfSDavid du Colombier 	return c;
2597dd7cddfSDavid du Colombier }
2607dd7cddfSDavid du Colombier 
2617dd7cddfSDavid du Colombier void
reprint1(Re * a)2627dd7cddfSDavid du Colombier reprint1(Re *a)
2637dd7cddfSDavid du Colombier {
2647dd7cddfSDavid du Colombier 	int i, j;
2657dd7cddfSDavid du Colombier 
2667dd7cddfSDavid du Colombier loop:
2677dd7cddfSDavid du Colombier 	if(a == 0)
2687dd7cddfSDavid du Colombier 		return;
2697dd7cddfSDavid du Colombier 	if(a->gen == gen)
2707dd7cddfSDavid du Colombier 		return;
2717dd7cddfSDavid du Colombier 	a->gen = gen;
2727dd7cddfSDavid du Colombier 	print("%p: ", a);
2737dd7cddfSDavid du Colombier 	switch(a->type) {
2747dd7cddfSDavid du Colombier 	default:
2757dd7cddfSDavid du Colombier 		print("type %d\n", a->type);
2767dd7cddfSDavid du Colombier 		error("print1 type");
2777dd7cddfSDavid du Colombier 
2787dd7cddfSDavid du Colombier 	case Tcase:
2797dd7cddfSDavid du Colombier 		print("case ->%p\n", a->next);
2807dd7cddfSDavid du Colombier 		for(i=0; i<256; i++)
2817dd7cddfSDavid du Colombier 			if(a->cases[i]) {
2827dd7cddfSDavid du Colombier 				for(j=i+1; j<256; j++)
2837dd7cddfSDavid du Colombier 					if(a->cases[i] != a->cases[j])
2847dd7cddfSDavid du Colombier 						break;
2857dd7cddfSDavid du Colombier 				print("	[%.2x-%.2x] ->%p\n", i, j-1, a->cases[i]);
2867dd7cddfSDavid du Colombier 				i = j-1;
2877dd7cddfSDavid du Colombier 			}
2887dd7cddfSDavid du Colombier 		for(i=0; i<256; i++)
2897dd7cddfSDavid du Colombier 			reprint1(a->cases[i]);
2907dd7cddfSDavid du Colombier 		break;
2917dd7cddfSDavid du Colombier 
2927dd7cddfSDavid du Colombier 	case Tbegin:
2937dd7cddfSDavid du Colombier 		print("^ ->%p\n", a->next);
2947dd7cddfSDavid du Colombier 		break;
2957dd7cddfSDavid du Colombier 
2967dd7cddfSDavid du Colombier 	case Tend:
2977dd7cddfSDavid du Colombier 		print("$ ->%p\n", a->next);
2987dd7cddfSDavid du Colombier 		break;
2997dd7cddfSDavid du Colombier 
3007dd7cddfSDavid du Colombier 	case Tclass:
3017dd7cddfSDavid du Colombier 		print("[%.2x-%.2x] ->%p\n", a->lo, a->hi, a->next);
3027dd7cddfSDavid du Colombier 		break;
3037dd7cddfSDavid du Colombier 
3047dd7cddfSDavid du Colombier 	case Tor:
3057dd7cddfSDavid du Colombier 	case Talt:
3067dd7cddfSDavid du Colombier 		print("| %p ->%p\n", a->alt, a->next);
3077dd7cddfSDavid du Colombier 		reprint1(a->alt);
3087dd7cddfSDavid du Colombier 		break;
3097dd7cddfSDavid du Colombier 	}
3107dd7cddfSDavid du Colombier 	a = a->next;
3117dd7cddfSDavid du Colombier 	goto loop;
3127dd7cddfSDavid du Colombier }
3137dd7cddfSDavid du Colombier 
3147dd7cddfSDavid du Colombier void
reprint(char * s,Re * r)3157dd7cddfSDavid du Colombier reprint(char *s, Re *r)
3167dd7cddfSDavid du Colombier {
3177dd7cddfSDavid du Colombier 	print("%s:\n", s);
3187dd7cddfSDavid du Colombier 	gen++;
3197dd7cddfSDavid du Colombier 	reprint1(r);
3207dd7cddfSDavid du Colombier 	print("\n\n");
3217dd7cddfSDavid du Colombier }
322