harvey/sys/src/cmd/grep/sub.c

/*
 * This file is part of the UCB release of Plan 9. It is subject to the license
 * terms in the LICENSE file found in the top-level directory of this
 * distribution and at http://akaros.cs.berkeley.edu/files/Plan9License. No
 * part of the UCB release of Plan 9, including this file, may be copied,
 * modified, propagated, or distributed except according to the terms contained
 * in the LICENSE file.
 */

#include	"grep.h"

void *
mal(int n)
{
	static char *s;
	static int m = 0;
	void *v;

	n = (n + 3) & ~3;
	if (m < n) {
		if (n > Nhunk) {
			v = sbrk(n);
			memset(v, 0, n);
			return v;
		}
		s = sbrk(Nhunk);
		m = Nhunk;
	}
	v = s;
	s += n;
	m -= n;
	memset(v, 0, n);
	return v;
}

State *
sal(int n)
{
	State *s;

	s = mal(sizeof(*s));
//  s->next = mal(256*sizeof(*s->next));
	s->count = n;
	s->re = mal(n * sizeof(*state0->re));
	return s;
}

Re *
ral(int type)
{
	Re *r;

	r = mal(sizeof(*r));
	r->type = type;
	maxfollow++;
	return r;
}

void
error(char *s)
{
	fprint(2, "grep: internal error: %s\n", s);
	exits(s);
}

int
countor(Re * r)
{
	int n;

	n = 0;
loop:
	switch (r->type) {
		case Tor:
			n += countor(r->alt);
			r = r->next;
			goto loop;
		case Tclass:
			return n + r->hi - r->lo + 1;
	}
	return n;
}

Re *
oralloc(int t, Re * r, Re * b)
{
	Re *a;

	if (b == 0)
		return r;
	a = ral(t);
	a->alt = r;
	a->next = b;
	return a;
}

void
case1(Re * c, Re * r)
{
	int n;

loop:
	switch (r->type) {
		case Tor:
			case1(c, r->alt);
			r = r->next;
			goto loop;

		case Tclass:	/* add to character */
			for (n = r->lo; n <= r->hi; n++)
				c->cases[n] = oralloc(Tor, r->next, c->cases[n]);
			break;

		default:	/* add everything unknown to next */
			c->next = oralloc(Talt, r, c->next);
			break;
	}
}

Re *
addcase(Re * r)
{
	int i, n;
	Re *a;

	if (r->gen == gen)
		return r;
	r->gen = gen;
	switch (r->type) {
		default:
			error("addcase");

		case Tor:
			n = countor(r);
			if (n >= Caselim) {
				a = ral(Tcase);
				a->cases = mal(256 * sizeof(*a->cases));
				case1(a, r);
				for (i = 0; i < 256; i++)
					if (a->cases[i]) {
						r = a->cases[i];
						if (countor(r) < n)
							a->cases[i] = addcase(r);
					}
				return a;
			}
			return r;

		case Talt:
			r->next = addcase(r->next);
			r->alt = addcase(r->alt);
			return r;

		case Tbegin:
		case Tend:
		case Tclass:
			return r;
	}
}

void
str2top(char *p)
{
	Re2 oldtop;

	oldtop = topre;
	input = p;
	if (*p == '\0')
		yyerror("empty pattern");	/* can't be a file name here */
	if (!flags['f'])
		pattern = p;
	topre.beg = 0;
	topre.end = 0;
	yyparse();
	gen++;
	if (topre.beg == 0)
		yyerror("syntax");
	if (oldtop.beg)
		topre = re2or(oldtop, topre);
}

void
appendnext(Re * a, Re * b)
{
	Re *n;

	while (n = a->next)
		a = n;
	a->next = b;
}

void
patchnext(Re * a, Re * b)
{
	Re *n;

	while (a) {
		n = a->next;
		a->next = b;
		a = n;
	}
}

int
getrec(void)
{
	int c;

	if (flags['f']) {
		c = Bgetc(rein);
		if (c <= 0)
			return 0;
	} else
		c = *input++ & 0xff;
	if (flags['i'] && c >= 'A' && c <= 'Z')
		c += 'a' - 'A';
	if (c == '\n')
		lineno++;
	return c;
}

Re2
re2cat(Re2 a, Re2 b)
{
	Re2 c;

	c.beg = a.beg;
	c.end = b.end;
	patchnext(a.end, b.beg);
	return c;
}

Re2
re2star(Re2 a)
{
	Re2 c;

	c.beg = ral(Talt);
	c.beg->alt = a.beg;
	patchnext(a.end, c.beg);
	c.end = c.beg;
	return c;
}

Re2
re2or(Re2 a, Re2 b)
{
	Re2 c;

	c.beg = ral(Tor);
	c.beg->alt = b.beg;
	c.beg->next = a.beg;
	c.end = b.end;
	appendnext(c.end, a.end);
	return c;
}

Re2
re2char(int c0, int c1)
{
	Re2 c;

	c.beg = ral(Tclass);
	c.beg->lo = c0 & 0xff;
	c.beg->hi = c1 & 0xff;
	c.end = c.beg;
	return c;
}

void
reprint1(Re * a)
{
	int i, j;

loop:
	if (a == 0)
		return;
	if (a->gen == gen)
		return;
	a->gen = gen;
	print("%p: ", a);
	switch (a->type) {
		default:
			print("type %d\n", a->type);
			error("print1 type");

		case Tcase:
			print("case ->%p\n", a->next);
			for (i = 0; i < 256; i++)
				if (a->cases[i]) {
					for (j = i + 1; j < 256; j++)
						if (a->cases[i] != a->cases[j])
							break;
					print("	[%.2x-%.2x] ->%p\n", i, j - 1, a->cases[i]);
					i = j - 1;
				}
			for (i = 0; i < 256; i++)
				reprint1(a->cases[i]);
			break;

		case Tbegin:
			print("^ ->%p\n", a->next);
			break;

		case Tend:
			print("$ ->%p\n", a->next);
			break;

		case Tclass:
			print("[%.2x-%.2x] ->%p\n", a->lo, a->hi, a->next);
			break;

		case Tor:
		case Talt:
			print("| %p ->%p\n", a->alt, a->next);
			reprint1(a->alt);
			break;
	}
	a = a->next;
	goto loop;
}

void
reprint(char *s, Re * r)
{
	print("%s:\n", s);
	gen++;
	reprint1(r);
	print("\n\n");
}