1 76193d7c 2003-09-30 devnull #include	"mk.h"
  2 76193d7c 2003-09-30 devnull 
  3 76193d7c 2003-09-30 devnull static Node *applyrules(char *, char *);
  4 76193d7c 2003-09-30 devnull static void togo(Node *);
  5 76193d7c 2003-09-30 devnull static int vacuous(Node *);
  6 76193d7c 2003-09-30 devnull static Node *newnode(char *);
  7 76193d7c 2003-09-30 devnull static void trace(char *, Arc *);
  8 76193d7c 2003-09-30 devnull static void cyclechk(Node *);
  9 76193d7c 2003-09-30 devnull static void ambiguous(Node *);
 10 76193d7c 2003-09-30 devnull static void attribute(Node *);
 11 76193d7c 2003-09-30 devnull 
 12 76193d7c 2003-09-30 devnull Node *
 13 76193d7c 2003-09-30 devnull graph(char *target)
 14 76193d7c 2003-09-30 devnull {
 15 76193d7c 2003-09-30 devnull 	Node *node;
 16 76193d7c 2003-09-30 devnull 	char *cnt;
 17 76193d7c 2003-09-30 devnull 
 18 76193d7c 2003-09-30 devnull 	cnt = rulecnt();
 19 76193d7c 2003-09-30 devnull 	node = applyrules(target, cnt);
 20 76193d7c 2003-09-30 devnull 	free(cnt);
 21 76193d7c 2003-09-30 devnull 	cyclechk(node);
 22 76193d7c 2003-09-30 devnull 	node->flags |= PROBABLE;	/* make sure it doesn't get deleted */
 23 76193d7c 2003-09-30 devnull 	vacuous(node);
 24 76193d7c 2003-09-30 devnull 	ambiguous(node);
 25 76193d7c 2003-09-30 devnull 	attribute(node);
 26 76193d7c 2003-09-30 devnull 	return(node);
 27 76193d7c 2003-09-30 devnull }
 28 76193d7c 2003-09-30 devnull 
 29 76193d7c 2003-09-30 devnull static Node *
 30 76193d7c 2003-09-30 devnull applyrules(char *target, char *cnt)
 31 76193d7c 2003-09-30 devnull {
 32 76193d7c 2003-09-30 devnull 	Symtab *sym;
 33 76193d7c 2003-09-30 devnull 	Node *node;
 34 76193d7c 2003-09-30 devnull 	Rule *r;
 35 76193d7c 2003-09-30 devnull 	Arc head, *a = &head;
 36 76193d7c 2003-09-30 devnull 	Word *w;
 37 76193d7c 2003-09-30 devnull 	char stem[NAMEBLOCK], buf[NAMEBLOCK];
 38 76193d7c 2003-09-30 devnull 	Resub rmatch[NREGEXP];
 39 76193d7c 2003-09-30 devnull 
 40 cbeb0b26 2006-04-01 devnull /*	print("applyrules(%lux='%s')\n", target, target); */
 41 76193d7c 2003-09-30 devnull 	sym = symlook(target, S_NODE, 0);
 42 76193d7c 2003-09-30 devnull 	if(sym)
 43 3fe9465a 2006-04-20 devnull 		return sym->u.ptr;
 44 76193d7c 2003-09-30 devnull 	target = strdup(target);
 45 76193d7c 2003-09-30 devnull 	node = newnode(target);
 46 76193d7c 2003-09-30 devnull 	head.n = 0;
 47 76193d7c 2003-09-30 devnull 	head.next = 0;
 48 76193d7c 2003-09-30 devnull 	sym = symlook(target, S_TARGET, 0);
 49 76193d7c 2003-09-30 devnull 	memset((char*)rmatch, 0, sizeof(rmatch));
 50 3fe9465a 2006-04-20 devnull 	for(r = sym? sym->u.ptr:0; r; r = r->chain){
 51 76193d7c 2003-09-30 devnull 		if(r->attr&META) continue;
 52 76193d7c 2003-09-30 devnull 		if(strcmp(target, r->target)) continue;
 53 76193d7c 2003-09-30 devnull 		if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue;	/* no effect; ignore */
 54 76193d7c 2003-09-30 devnull 		if(cnt[r->rule] >= nreps) continue;
 55 76193d7c 2003-09-30 devnull 		cnt[r->rule]++;
 56 76193d7c 2003-09-30 devnull 		node->flags |= PROBABLE;
 57 76193d7c 2003-09-30 devnull 
 58 76193d7c 2003-09-30 devnull /*		if(r->attr&VIR)
 59 76193d7c 2003-09-30 devnull  *			node->flags |= VIRTUAL;
 60 76193d7c 2003-09-30 devnull  *		if(r->attr&NOREC)
 61 76193d7c 2003-09-30 devnull  *			node->flags |= NORECIPE;
 62 76193d7c 2003-09-30 devnull  *		if(r->attr&DEL)
 63 76193d7c 2003-09-30 devnull  *			node->flags |= DELETE;
 64 76193d7c 2003-09-30 devnull  */
 65 76193d7c 2003-09-30 devnull 		if(!r->tail || !r->tail->s || !*r->tail->s) {
 66 76193d7c 2003-09-30 devnull 			a->next = newarc((Node *)0, r, "", rmatch);
 67 76193d7c 2003-09-30 devnull 			a = a->next;
 68 76193d7c 2003-09-30 devnull 		} else
 69 76193d7c 2003-09-30 devnull 			for(w = r->tail; w; w = w->next){
 70 76193d7c 2003-09-30 devnull 				a->next = newarc(applyrules(w->s, cnt), r, "", rmatch);
 71 76193d7c 2003-09-30 devnull 				a = a->next;
 72 76193d7c 2003-09-30 devnull 		}
 73 76193d7c 2003-09-30 devnull 		cnt[r->rule]--;
 74 76193d7c 2003-09-30 devnull 		head.n = node;
 75 76193d7c 2003-09-30 devnull 	}
 76 76193d7c 2003-09-30 devnull 	for(r = metarules; r; r = r->next){
 77 76193d7c 2003-09-30 devnull 		if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue;	/* no effect; ignore */
 78 76193d7c 2003-09-30 devnull 		if ((r->attr&NOVIRT) && a != &head && (a->r->attr&VIR))
 79 76193d7c 2003-09-30 devnull 			continue;
 80 76193d7c 2003-09-30 devnull 		if(r->attr&REGEXP){
 81 76193d7c 2003-09-30 devnull 			stem[0] = 0;
 82 76193d7c 2003-09-30 devnull 			patrule = r;
 83 76193d7c 2003-09-30 devnull 			memset((char*)rmatch, 0, sizeof(rmatch));
 84 76193d7c 2003-09-30 devnull 			if(regexec(r->pat, node->name, rmatch, NREGEXP) == 0)
 85 76193d7c 2003-09-30 devnull 				continue;
 86 76193d7c 2003-09-30 devnull 		} else {
 87 9aa1c92f 2005-01-04 devnull 			if(!match(node->name, r->target, stem, r->shellt)) continue;
 88 76193d7c 2003-09-30 devnull 		}
 89 76193d7c 2003-09-30 devnull 		if(cnt[r->rule] >= nreps) continue;
 90 76193d7c 2003-09-30 devnull 		cnt[r->rule]++;
 91 76193d7c 2003-09-30 devnull 
 92 76193d7c 2003-09-30 devnull /*		if(r->attr&VIR)
 93 76193d7c 2003-09-30 devnull  *			node->flags |= VIRTUAL;
 94 76193d7c 2003-09-30 devnull  *		if(r->attr&NOREC)
 95 76193d7c 2003-09-30 devnull  *			node->flags |= NORECIPE;
 96 76193d7c 2003-09-30 devnull  *		if(r->attr&DEL)
 97 76193d7c 2003-09-30 devnull  *			node->flags |= DELETE;
 98 76193d7c 2003-09-30 devnull  */
 99 76193d7c 2003-09-30 devnull 
100 76193d7c 2003-09-30 devnull 		if(!r->tail || !r->tail->s || !*r->tail->s) {
101 76193d7c 2003-09-30 devnull 			a->next = newarc((Node *)0, r, stem, rmatch);
102 76193d7c 2003-09-30 devnull 			a = a->next;
103 76193d7c 2003-09-30 devnull 		} else
104 76193d7c 2003-09-30 devnull 			for(w = r->tail; w; w = w->next){
105 76193d7c 2003-09-30 devnull 				if(r->attr&REGEXP)
106 76193d7c 2003-09-30 devnull 					regsub(w->s, buf, sizeof buf, rmatch, NREGEXP);
107 76193d7c 2003-09-30 devnull 				else
108 76193d7c 2003-09-30 devnull 					subst(stem, w->s, buf);
109 76193d7c 2003-09-30 devnull 				a->next = newarc(applyrules(buf, cnt), r, stem, rmatch);
110 76193d7c 2003-09-30 devnull 				a = a->next;
111 76193d7c 2003-09-30 devnull 			}
112 76193d7c 2003-09-30 devnull 		cnt[r->rule]--;
113 76193d7c 2003-09-30 devnull 	}
114 76193d7c 2003-09-30 devnull 	a->next = node->prereqs;
115 76193d7c 2003-09-30 devnull 	node->prereqs = head.next;
116 76193d7c 2003-09-30 devnull 	return(node);
117 76193d7c 2003-09-30 devnull }
118 76193d7c 2003-09-30 devnull 
119 76193d7c 2003-09-30 devnull static void
120 76193d7c 2003-09-30 devnull togo(Node *node)
121 76193d7c 2003-09-30 devnull {
122 76193d7c 2003-09-30 devnull 	Arc *la, *a;
123 76193d7c 2003-09-30 devnull 
124 76193d7c 2003-09-30 devnull 	/* delete them now */
125 76193d7c 2003-09-30 devnull 	la = 0;
126 76193d7c 2003-09-30 devnull 	for(a = node->prereqs; a; la = a, a = a->next)
127 76193d7c 2003-09-30 devnull 		if(a->flag&TOGO){
128 76193d7c 2003-09-30 devnull 			if(a == node->prereqs)
129 76193d7c 2003-09-30 devnull 				node->prereqs = a->next;
130 76193d7c 2003-09-30 devnull 			else
131 76193d7c 2003-09-30 devnull 				la->next = a->next, a = la;
132 76193d7c 2003-09-30 devnull 		}
133 76193d7c 2003-09-30 devnull }
134 76193d7c 2003-09-30 devnull 
135 76193d7c 2003-09-30 devnull static int
136 76193d7c 2003-09-30 devnull vacuous(Node *node)
137 76193d7c 2003-09-30 devnull {
138 76193d7c 2003-09-30 devnull 	Arc *la, *a;
139 76193d7c 2003-09-30 devnull 	int vac = !(node->flags&PROBABLE);
140 76193d7c 2003-09-30 devnull 
141 76193d7c 2003-09-30 devnull 	if(node->flags&READY)
142 76193d7c 2003-09-30 devnull 		return(node->flags&VACUOUS);
143 76193d7c 2003-09-30 devnull 	node->flags |= READY;
144 76193d7c 2003-09-30 devnull 	for(a = node->prereqs; a; a = a->next)
145 76193d7c 2003-09-30 devnull 		if(a->n && vacuous(a->n) && (a->r->attr&META))
146 76193d7c 2003-09-30 devnull 			a->flag |= TOGO;
147 76193d7c 2003-09-30 devnull 		else
148 76193d7c 2003-09-30 devnull 			vac = 0;
149 76193d7c 2003-09-30 devnull 	/* if a rule generated arcs that DON'T go; no others from that rule go */
150 76193d7c 2003-09-30 devnull 	for(a = node->prereqs; a; a = a->next)
151 76193d7c 2003-09-30 devnull 		if((a->flag&TOGO) == 0)
152 76193d7c 2003-09-30 devnull 			for(la = node->prereqs; la; la = la->next)
153 76193d7c 2003-09-30 devnull 				if((la->flag&TOGO) && (la->r == a->r)){
154 76193d7c 2003-09-30 devnull 					la->flag &= ~TOGO;
155 76193d7c 2003-09-30 devnull 				}
156 76193d7c 2003-09-30 devnull 	togo(node);
157 76193d7c 2003-09-30 devnull 	if(vac)
158 76193d7c 2003-09-30 devnull 		node->flags |= VACUOUS;
159 76193d7c 2003-09-30 devnull 	return(vac);
160 76193d7c 2003-09-30 devnull }
161 76193d7c 2003-09-30 devnull 
162 76193d7c 2003-09-30 devnull static Node *
163 76193d7c 2003-09-30 devnull newnode(char *name)
164 76193d7c 2003-09-30 devnull {
165 76193d7c 2003-09-30 devnull 	register Node *node;
166 76193d7c 2003-09-30 devnull 
167 76193d7c 2003-09-30 devnull 	node = (Node *)Malloc(sizeof(Node));
168 76193d7c 2003-09-30 devnull 	symlook(name, S_NODE, (void *)node);
169 76193d7c 2003-09-30 devnull 	node->name = name;
170 76193d7c 2003-09-30 devnull 	node->time = timeof(name, 0);
171 76193d7c 2003-09-30 devnull 	node->prereqs = 0;
172 76193d7c 2003-09-30 devnull 	node->flags = node->time? PROBABLE : 0;
173 76193d7c 2003-09-30 devnull 	node->next = 0;
174 76193d7c 2003-09-30 devnull 	return(node);
175 76193d7c 2003-09-30 devnull }
176 76193d7c 2003-09-30 devnull 
177 76193d7c 2003-09-30 devnull void
178 76193d7c 2003-09-30 devnull dumpn(char *s, Node *n)
179 76193d7c 2003-09-30 devnull {
180 76193d7c 2003-09-30 devnull 	char buf[1024];
181 76193d7c 2003-09-30 devnull 	Arc *a;
182 76193d7c 2003-09-30 devnull 
183 92a0a8b6 2004-04-21 devnull 	snprint(buf, sizeof buf, "%s   ", (*s == ' ')? s:"");
184 76193d7c 2003-09-30 devnull 	Bprint(&bout, "%s%s@%ld: time=%ld flags=0x%x next=%ld\n",
185 76193d7c 2003-09-30 devnull 		s, n->name, n, n->time, n->flags, n->next);
186 76193d7c 2003-09-30 devnull 	for(a = n->prereqs; a; a = a->next)
187 76193d7c 2003-09-30 devnull 		dumpa(buf, a);
188 76193d7c 2003-09-30 devnull }
189 76193d7c 2003-09-30 devnull 
190 76193d7c 2003-09-30 devnull static void
191 76193d7c 2003-09-30 devnull trace(char *s, Arc *a)
192 76193d7c 2003-09-30 devnull {
193 76193d7c 2003-09-30 devnull 	fprint(2, "\t%s", s);
194 76193d7c 2003-09-30 devnull 	while(a){
195 76193d7c 2003-09-30 devnull 		fprint(2, " <-(%s:%d)- %s", a->r->file, a->r->line,
196 76193d7c 2003-09-30 devnull 			a->n? a->n->name:"");
197 76193d7c 2003-09-30 devnull 		if(a->n){
198 76193d7c 2003-09-30 devnull 			for(a = a->n->prereqs; a; a = a->next)
199 76193d7c 2003-09-30 devnull 				if(*a->r->recipe) break;
200 76193d7c 2003-09-30 devnull 		} else
201 76193d7c 2003-09-30 devnull 			a = 0;
202 76193d7c 2003-09-30 devnull 	}
203 76193d7c 2003-09-30 devnull 	fprint(2, "\n");
204 76193d7c 2003-09-30 devnull }
205 76193d7c 2003-09-30 devnull 
206 76193d7c 2003-09-30 devnull static void
207 76193d7c 2003-09-30 devnull cyclechk(Node *n)
208 76193d7c 2003-09-30 devnull {
209 76193d7c 2003-09-30 devnull 	Arc *a;
210 76193d7c 2003-09-30 devnull 
211 76193d7c 2003-09-30 devnull 	if((n->flags&CYCLE) && n->prereqs){
212 76193d7c 2003-09-30 devnull 		fprint(2, "mk: cycle in graph detected at target %s\n", n->name);
213 76193d7c 2003-09-30 devnull 		Exit();
214 76193d7c 2003-09-30 devnull 	}
215 76193d7c 2003-09-30 devnull 	n->flags |= CYCLE;
216 76193d7c 2003-09-30 devnull 	for(a = n->prereqs; a; a = a->next)
217 76193d7c 2003-09-30 devnull 		if(a->n)
218 76193d7c 2003-09-30 devnull 			cyclechk(a->n);
219 76193d7c 2003-09-30 devnull 	n->flags &= ~CYCLE;
220 76193d7c 2003-09-30 devnull }
221 76193d7c 2003-09-30 devnull 
222 76193d7c 2003-09-30 devnull static void
223 76193d7c 2003-09-30 devnull ambiguous(Node *n)
224 76193d7c 2003-09-30 devnull {
225 76193d7c 2003-09-30 devnull 	Arc *a;
226 76193d7c 2003-09-30 devnull 	Rule *r = 0;
227 76193d7c 2003-09-30 devnull 	Arc *la;
228 76193d7c 2003-09-30 devnull 	int bad = 0;
229 76193d7c 2003-09-30 devnull 
230 76193d7c 2003-09-30 devnull 	la = 0;
231 76193d7c 2003-09-30 devnull 	for(a = n->prereqs; a; a = a->next){
232 76193d7c 2003-09-30 devnull 		if(a->n)
233 76193d7c 2003-09-30 devnull 			ambiguous(a->n);
234 76193d7c 2003-09-30 devnull 		if(*a->r->recipe == 0) continue;
235 76193d7c 2003-09-30 devnull 		if(r == 0)
236 76193d7c 2003-09-30 devnull 			r = a->r, la = a;
237 76193d7c 2003-09-30 devnull 		else{
238 76193d7c 2003-09-30 devnull 			if(r->recipe != a->r->recipe){
239 76193d7c 2003-09-30 devnull 				if((r->attr&META) && !(a->r->attr&META)){
240 76193d7c 2003-09-30 devnull 					la->flag |= TOGO;
241 76193d7c 2003-09-30 devnull 					r = a->r, la = a;
242 76193d7c 2003-09-30 devnull 				} else if(!(r->attr&META) && (a->r->attr&META)){
243 76193d7c 2003-09-30 devnull 					a->flag |= TOGO;
244 76193d7c 2003-09-30 devnull 					continue;
245 76193d7c 2003-09-30 devnull 				}
246 76193d7c 2003-09-30 devnull 			}
247 76193d7c 2003-09-30 devnull 			if(r->recipe != a->r->recipe){
248 76193d7c 2003-09-30 devnull 				if(bad == 0){
249 76193d7c 2003-09-30 devnull 					fprint(2, "mk: ambiguous recipes for %s:\n", n->name);
250 76193d7c 2003-09-30 devnull 					bad = 1;
251 76193d7c 2003-09-30 devnull 					trace(n->name, la);
252 76193d7c 2003-09-30 devnull 				}
253 76193d7c 2003-09-30 devnull 				trace(n->name, a);
254 76193d7c 2003-09-30 devnull 			}
255 76193d7c 2003-09-30 devnull 		}
256 76193d7c 2003-09-30 devnull 	}
257 76193d7c 2003-09-30 devnull 	if(bad)
258 76193d7c 2003-09-30 devnull 		Exit();
259 76193d7c 2003-09-30 devnull 	togo(n);
260 76193d7c 2003-09-30 devnull }
261 76193d7c 2003-09-30 devnull 
262 76193d7c 2003-09-30 devnull static void
263 76193d7c 2003-09-30 devnull attribute(Node *n)
264 76193d7c 2003-09-30 devnull {
265 76193d7c 2003-09-30 devnull 	register Arc *a;
266 76193d7c 2003-09-30 devnull 
267 76193d7c 2003-09-30 devnull 	for(a = n->prereqs; a; a = a->next){
268 76193d7c 2003-09-30 devnull 		if(a->r->attr&VIR)
269 76193d7c 2003-09-30 devnull 			n->flags |= VIRTUAL;
270 76193d7c 2003-09-30 devnull 		if(a->r->attr&NOREC)
271 76193d7c 2003-09-30 devnull 			n->flags |= NORECIPE;
272 76193d7c 2003-09-30 devnull 		if(a->r->attr&DEL)
273 76193d7c 2003-09-30 devnull 			n->flags |= DELETE;
274 76193d7c 2003-09-30 devnull 		if(a->n)
275 76193d7c 2003-09-30 devnull 			attribute(a->n);
276 76193d7c 2003-09-30 devnull 	}
277 76193d7c 2003-09-30 devnull 	if(n->flags&VIRTUAL)
278 76193d7c 2003-09-30 devnull 		n->time = 0;
279 76193d7c 2003-09-30 devnull }