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