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®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 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 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 * 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 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 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 } 280