#
#	initially generated by c2l
#


graph(target: array of byte): ref Node
{
	node: ref Node;
	cnt: array of byte;

	cnt = rulecnt();
	node = applyrules(target, cnt);
	cnt = nil;
	cyclechk(node);
	node.flags |= PROBABLE;	#  make sure it doesn't get deleted 
	vacuous(node);
	ambiguous(node);
	attribute(node);
	return node;
}

applyrules(target: array of byte, cnt: array of byte): ref Node
{
	sym: ref Symtab;
	node: ref Node;
	r: ref Rule;
	head := ref Arc;
	a: ref Arc = head;
	w: ref Word;
	stem := array[NAMEBLOCK] of byte;
	buf := array[NAMEBLOCK] of byte;
	rmatch := array[NREGEXP] of Resub;

	# 	print("applyrules(%lux='%s')\n", target, target);/*
	sym = symlooki(target, S_NODE, 0);
	if(sym != nil)
		return sym.nvalue;
	target = libc0->strdup(target);
	node = newnode(target);
	head.n = nil;
	head.next = nil;
	sym = symlooki(target, S_TARGET, 0);
	for(i := 0; i < NREGEXP; i++)
		rmatch[i].sp = rmatch[i].ep = nil;
	if(sym != nil)
		tmp_1 := sym.rvalue;
	else
		tmp_1 = nil;
	for(r = tmp_1; r != nil; r = r.chain){
		if(r.attr&META)
			continue;
		if(libc0->strcmp(target, r.target))
			continue;
		if((r.recipe == nil || !int r.recipe[0]) && (r.tail == nil || r.tail.s == nil || !int r.tail.s[0]))	#  no effect; ignore 
			continue;
		if(int cnt[r.rule] >= nreps)
			continue;
		cnt[r.rule]++;
		node.flags |= PROBABLE;
		# 		if(r->attr&VIR)
		#  *			node->flags |= VIRTUAL;
		#  *		if(r->attr&NOREC)
		#  *			node->flags |= NORECIPE;
		#  *		if(r->attr&DEL)
		#  *			node->flags |= DELETE;
		#  
		if(r.tail == nil || r.tail.s == nil || !int r.tail.s[0]){
			a.next = newarc(nil, r, libc0->s2ab(""), rmatch);
			a = a.next;
		}
		else
			for(w = r.tail; w != nil; w = w.next){
				a.next = newarc(applyrules(w.s, cnt), r, libc0->s2ab(""), rmatch);
				a = a.next;
			}
		cnt[r.rule]--;
		head.n = node;
	}
	for(r = metarules; r != nil; r = r.next){
		if((r.recipe == nil || !int r.recipe[0]) && (r.tail == nil || r.tail.s == nil || !int r.tail.s[0]))	#  no effect; ignore 
			continue;
		if(r.attr&NOVIRT && a != head && a.r.attr&VIR)
			continue;
		if(r.attr&REGEXP){
			stem[0] = byte 0;
			patrule = r;
			for(i = 0; i < NREGEXP; i++)
				rmatch[i].sp = rmatch[i].ep = nil;
			m := regex->execute(r.pat, libc0->ab2s(node.name));
			if(m == nil)
				continue;
			regadd(node.name, m, rmatch, NREGEXP);
		}
		else{
			if(!match(node.name, r.target, stem))
				continue;
		}
		if(int cnt[r.rule] >= nreps)
			continue;
		cnt[r.rule]++;
		# 		if(r->attr&VIR)
		#  *			node->flags |= VIRTUAL;
		#  *		if(r->attr&NOREC)
		#  *			node->flags |= NORECIPE;
		#  *		if(r->attr&DEL)
		#  *			node->flags |= DELETE;
		#  
		if(r.tail == nil || r.tail.s == nil || !int r.tail.s[0]){
			a.next = newarc(nil, r, stem, rmatch);
			a = a.next;
		}
		else
			for(w = r.tail; w != nil; w = w.next){
				if(r.attr&REGEXP)
					regsub(w.s, buf, rmatch, NREGEXP);
				else
					subst(stem, w.s, buf);
				a.next = newarc(applyrules(buf, cnt), r, stem, rmatch);
				a = a.next;
			}
		cnt[r.rule]--;
	}
	a.next = node.prereqs;
	node.prereqs = head.next;
	return node;
}

togo(node: ref Node)
{
	la, a: ref Arc;

	#  delete them now 
	la = nil;
	for(a = node.prereqs; a != nil; (la, a) = (a, a.next))
		if(a.flag&TOGO){
			if(a == node.prereqs)
				node.prereqs = a.next;
			else
				(la.next, a) = (a.next, la);
		}
}

vacuous(node: ref Node): int
{
	la, a: ref Arc;
	vac: int = !(node.flags&PROBABLE);

	if(node.flags&READY)
		return node.flags&VACUOUS;
	node.flags |= READY;
	for(a = node.prereqs; a != nil; a = a.next)
		if(a.n != nil && vacuous(a.n) && a.r.attr&META)
			a.flag |= TOGO;
		else
			vac = 0;
	#  if a rule generated arcs that DON'T go; no others from that rule go 
	for(a = node.prereqs; a != nil; a = a.next)
		if((a.flag&TOGO) == 0)
			for(la = node.prereqs; la != nil; la = la.next)
				if(la.flag&TOGO && la.r == a.r){
					la.flag &= ~TOGO;
				}
	togo(node);
	if(vac)
		node.flags |= VACUOUS;
	return vac;
}

newnode(name: array of byte): ref Node
{
	node: ref Node;

	node = ref Node;
	symlookn(name, S_NODE, node);
	node.name = name;
	node.time = timeof(name, 0);
	node.prereqs = nil;
	if(node.time)
		node.flags = PROBABLE;
	else
		node.flags = 0;
	node.next = nil;
	return node;
}

dumpn(s: array of byte, n: ref Node)
{
	buf := array[1024] of byte;
	a: ref Arc;

	if(s[0] == byte ' ')
		stob(buf, sys->sprint("%s   ", libc0->ab2s(s)));
	else
		stob(buf, sys->sprint("%s   ", ""));
	bout.puts(sys->sprint("%s%s@%x: time=%d flags=0x%x next=%x\n", libc0->ab2s(s), libc0->ab2s(n.name), n, n.time, n.flags, n.next));
	for(a = n.prereqs; a != nil; a = a.next)
		dumpa(buf, a);
}

trace(s: array of byte, a: ref Arc)
{
	sys->fprint(sys->fildes(2), "\t%s", libc0->ab2s(s));
	while(a != nil){
		if(a.n != nil)
			sys->fprint(sys->fildes(2), " <-(%s:%d)- %s", libc0->ab2s(a.r.file), a.r.line, libc0->ab2s(a.n.name));
		else
			sys->fprint(sys->fildes(2), " <-(%s:%d)- %s", libc0->ab2s(a.r.file), a.r.line, "");
		if(a.n != nil){
			for(a = a.n.prereqs; a != nil; a = a.next)
				if(int a.r.recipe[0])
					break;
		}
		else
			a = nil;
	}
	sys->fprint(sys->fildes(2), "\n");
}

cyclechk(n: ref Node)
{
	a: ref Arc;

	if(n.flags&CYCLE && n.prereqs != nil){
		sys->fprint(sys->fildes(2), "mk: cycle in graph detected at target %s\n", libc0->ab2s(n.name));
		Exit();
	}
	n.flags |= CYCLE;
	for(a = n.prereqs; a != nil; a = a.next)
		if(a.n != nil)
			cyclechk(a.n);
	n.flags &= ~CYCLE;
}

ambiguous(n: ref Node)
{
	a: ref Arc;
	r: ref Rule = nil;
	la: ref Arc;
	bad: int = 0;

	la = nil;
	for(a = n.prereqs; a != nil; a = a.next){
		if(a.n != nil)
			ambiguous(a.n);
		if(a.r.recipe[0] == byte 0)
			continue;
		if(r == nil)
			(r, la) = (a.r, a);
		else{
			if(r.recipe != a.r.recipe){
				if(r.attr&META && !(a.r.attr&META)){
					la.flag |= TOGO;
					(r, la) = (a.r, a);
				}
				else if(!(r.attr&META) && a.r.attr&META){
					a.flag |= TOGO;
					continue;
				}
			}
			if(r.recipe != a.r.recipe){
				if(bad == 0){
					sys->fprint(sys->fildes(2), "mk: ambiguous recipes for %s:\n", libc0->ab2s(n.name));
					bad = 1;
					trace(n.name, la);
				}
				trace(n.name, a);
			}
		}
	}
	if(bad)
		Exit();
	togo(n);
}

attribute(n: ref Node)
{
	a: ref Arc;

	for(a = n.prereqs; a != nil; a = a.next){
		if(a.r.attr&VIR)
			n.flags |= VIRTUAL;
		if(a.r.attr&NOREC)
			n.flags |= NORECIPE;
		if(a.r.attr&DEL)
			n.flags |= DELETE;
		if(a.n != nil)
			attribute(a.n);
	}
	if(n.flags&VIRTUAL)
		n.time = 0;
}