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 *
graph(char * target)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 *
applyrules(char * target,char * cnt)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®EXP){
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)) 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 if(!r->tail || !r->tail->s || !*r->tail->s) {
100 a->next = newarc((Node *)0, r, stem, rmatch);
101 a = a->next;
102 } else
103 for(w = r->tail; w; w = w->next){
104 if(r->attr®EXP)
105 regsub(w->s, buf, sizeof(buf), rmatch, NREGEXP);
106 else
107 subst(stem, w->s, buf, sizeof(buf));
108 a->next = newarc(applyrules(buf, cnt), r, stem, rmatch);
109 a = a->next;
110 }
111 cnt[r->rule]--;
112 }
113 a->next = node->prereqs;
114 node->prereqs = head.next;
115 return(node);
116 }
117
118 static void
togo(Node * node)119 togo(Node *node)
120 {
121 Arc *la, *a;
122
123 /* delete them now */
124 la = 0;
125 for(a = node->prereqs; a; la = a, a = a->next)
126 if(a->flag&TOGO){
127 if(a == node->prereqs)
128 node->prereqs = a->next;
129 else
130 la->next = a->next, a = la;
131 }
132 }
133
134 static
vacuous(Node * node)135 vacuous(Node *node)
136 {
137 Arc *la, *a;
138 int vac = !(node->flags&PROBABLE);
139
140 if(node->flags&READY)
141 return(node->flags&VACUOUS);
142 node->flags |= READY;
143 for(a = node->prereqs; a; a = a->next)
144 if(a->n && vacuous(a->n) && (a->r->attr&META))
145 a->flag |= TOGO;
146 else
147 vac = 0;
148 /* if a rule generated arcs that DON'T go; no others from that rule go */
149 for(a = node->prereqs; a; a = a->next)
150 if((a->flag&TOGO) == 0)
151 for(la = node->prereqs; la; la = la->next)
152 if((la->flag&TOGO) && (la->r == a->r)){
153 la->flag &= ~TOGO;
154 }
155 togo(node);
156 if(vac)
157 node->flags |= VACUOUS;
158 return(vac);
159 }
160
161 static Node *
newnode(char * name)162 newnode(char *name)
163 {
164 register Node *node;
165
166 node = (Node *)Malloc(sizeof(Node));
167 symlook(name, S_NODE, (void *)node);
168 node->name = name;
169 node->time = timeof(name, 0);
170 node->prereqs = 0;
171 node->flags = node->time? PROBABLE : 0;
172 node->next = 0;
173 return(node);
174 }
175
176 void
dumpn(char * s,Node * n)177 dumpn(char *s, Node *n)
178 {
179 char buf[1024];
180 Arc *a;
181
182 Bprint(&bout, "%s%s@%p: time=%ld flags=0x%x next=%p\n",
183 s, n->name, n, n->time, n->flags, n->next);
184 for(a = n->prereqs; a; a = a->next){
185 snprint(buf, sizeof buf, "%s ", (*s == ' ')? s:"");
186 dumpa(buf, a);
187 }
188 }
189
190 static void
trace(char * s,Arc * a)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
cyclechk(Node * n)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
ambiguous(Node * n)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
attribute(Node * n)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 }
280