/*  * 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	"mk.h" static Node *applyrules(char *, char *);static void togo(Node *);static int vacuous(Node *);static Node *newnode(char *);static void trace(char *, Arc *);static void cyclechk(Node *);static void ambiguous(Node *);static void attribute(Node *); Node *graph(char *target){	Node *node;	char *cnt; 	cnt = rulecnt();	node = applyrules(target, cnt);	free(cnt);	cyclechk(node);	node->flags |= PROBABLE;	/* make sure it doesn't get deleted */	vacuous(node);	ambiguous(node);	attribute(node);	return(node);} static Node *applyrules(char *target, char *cnt){	Symtab *sym;	Node *node;	Rule *r;	Arc head, *a = &head;	Word *w;	char stem[NAMEBLOCK], buf[NAMEBLOCK];	Resub rmatch[NREGEXP]; /*	print("applyrules(%lux='%s')\n", target, target);/**/	sym = symlook(target, S_NODE, 0);	if(sym)		return sym->u.ptr;	target = strdup(target);	node = newnode(target);	head.n = 0;	head.next = 0;	sym = symlook(target, S_TARGET, 0);	memset((char*)rmatch, 0, sizeof(rmatch));	for(r = sym? sym->u.ptr:0; r; r = r->chain){		if(r->attr&META) continue;		if(strcmp(target, r->target)) continue;		if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue;	/* no effect; ignore */		if(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 || !r->tail->s || !*r->tail->s) {			a->next = newarc((Node *)0, r, "", rmatch);			a = a->next;		} else			for(w = r->tail; w; w = w->next){				a->next = newarc(applyrules(w->s, cnt), r, "", rmatch);				a = a->next;		}		cnt[r->rule]--;		head.n = node;	}	for(r = metarules; r; r = r->next){		if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue;	/* no effect; ignore */		if ((r->attr&NOVIRT) && a != &head && (a->r->attr&VIR))			continue;		if(r->attr&REGEXP){			stem[0] = 0;			patrule = r;			memset((char*)rmatch, 0, sizeof(rmatch));			if(regexec(r->pat, node->name, rmatch, NREGEXP) == 0)				continue;		} else {			if(!match(node->name, r->target, stem)) continue;		}		if(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 || !r->tail->s || !*r->tail->s) {			a->next = newarc((Node *)0, r, stem, rmatch);			a = a->next;		} else			for(w = r->tail; w; w = w->next){				if(r->attr&REGEXP)					regsub(w->s, buf, sizeof(buf), rmatch, NREGEXP);				else					subst(stem, w->s, buf, sizeof(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);} static voidtogo(Node *node){	Arc *la, *a; 	/* delete them now */	la = 0;	for(a = node->prereqs; a; la = a, a = a->next)		if(a->flag&TOGO){			if(a == node->prereqs)				node->prereqs = a->next;			else				la->next = a->next, a = la;		}} staticvacuous(Node *node){	Arc *la, *a;	int vac = !(node->flags&PROBABLE); 	if(node->flags&READY)		return(node->flags&VACUOUS);	node->flags |= READY;	for(a = node->prereqs; a; a = a->next)		if(a->n && 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; a = a->next)		if((a->flag&TOGO) == 0)			for(la = node->prereqs; la; la = la->next)				if((la->flag&TOGO) && (la->r == a->r)){					la->flag &= ~TOGO;				}	togo(node);	if(vac)		node->flags |= VACUOUS;	return(vac);} static Node *newnode(char *name){	register Node *node; 	node = (Node *)Malloc(sizeof(Node));	symlook(name, S_NODE, (void *)node);	node->name = name;	node->time = timeof(name, 0);	node->prereqs = 0;	node->flags = node->time? PROBABLE : 0;	node->next = 0;	return(node);} voiddumpn(char *s, Node *n){	char buf[1024];	Arc *a; 	Bprint(&bout, "%s%s@%p: time=%ld flags=0x%x next=%p\n",		s, n->name, n, n->time, n->flags, n->next);	for(a = n->prereqs; a; a = a->next){		snprint(buf, sizeof buf, "%s   ", (*s == ' ')? s:"");		dumpa(buf, a);	}} static voidtrace(char *s, Arc *a){	fprint(2, "\t%s", s);	while(a){		fprint(2, " <-(%s:%d)- %s", a->r->file, a->r->line,			a->n? a->n->name:"");		if(a->n){			for(a = a->n->prereqs; a; a = a->next)				if(*a->r->recipe) break;		} else			a = 0;	}	fprint(2, "\n");} static voidcyclechk(Node *n){	Arc *a; 	if((n->flags&CYCLE) && n->prereqs){		fprint(2, "mk: cycle in graph detected at target %s\n", n->name);		Exit();	}	n->flags |= CYCLE;	for(a = n->prereqs; a; a = a->next)		if(a->n)			cyclechk(a->n);	n->flags &= ~CYCLE;} static voidambiguous(Node *n){	Arc *a;	Rule *r = 0;	Arc *la;	int bad = 0; 	la = 0;	for(a = n->prereqs; a; a = a->next){		if(a->n)			ambiguous(a->n);		if(*a->r->recipe == 0) continue;		if(r == 0)			r = a->r, la = a;		else{			if(r->recipe != a->r->recipe){				if((r->attr&META) && !(a->r->attr&META)){					la->flag |= TOGO;					r = a->r, la = a;				} else if(!(r->attr&META) && (a->r->attr&META)){					a->flag |= TOGO;					continue;				}			}			if(r->recipe != a->r->recipe){				if(bad == 0){					fprint(2, "mk: ambiguous recipes for %s:\n", n->name);					bad = 1;					trace(n->name, la);				}				trace(n->name, a);			}		}	}	if(bad)		Exit();	togo(n);} static voidattribute(Node *n){	register Arc *a; 	for(a = n->prereqs; a; 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)			attribute(a->n);	}	if(n->flags&VIRTUAL)		n->time = 0;}