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(%ld='%s')\n", target, target);/**/ 41 sym = symlook(target, S_NODE, (char *)0); 42 if(sym) 43 return (Node *)(sym->value); 44 target = strdup(target); 45 node = newnode(target); 46 head.n = 0; 47 head.next = 0; 48 sym = symlook(target, S_TARGET, (char *)0); 49 for(r = sym? (Rule *)(sym->value):0; r; r = r->chain){ 50 if(r->attr&META) continue; 51 if(strcmp(target, r->target)) continue; 52 if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue; /* no effect; ignore */ 53 if(cnt[r->rule] >= nreps) continue; 54 cnt[r->rule]++; 55 node->flags |= PROBABLE; 56 57 /* if(r->attr&VIR) 58 * node->flags |= VIRTUAL; 59 * if(r->attr&NOREC) 60 * node->flags |= NORECIPE; 61 * if(r->attr&DEL) 62 * node->flags |= DELETE; 63 */ 64 if(!r->tail || !r->tail->s || !*r->tail->s) { 65 a->next = newarc((Node *)0, r, "", rmatch); 66 a = a->next; 67 } else 68 for(w = r->tail; w; w = w->next){ 69 a->next = newarc(applyrules(w->s, cnt), r, "", rmatch); 70 a = a->next; 71 } 72 cnt[r->rule]--; 73 head.n = node; 74 } 75 for(r = metarules; r; r = r->next){ 76 if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue; /* no effect; ignore */ 77 if ((r->attr&NOVIRT) && a != &head && (a->r->attr&VIR)) 78 continue; 79 if(r->attr®EXP){ 80 stem[0] = 0; 81 patrule = r; 82 rmatch[0].sp = rmatch[0].ep = 0; 83 if(regexec(r->pat, node->name, rmatch, NREGEXP) == 0) 84 continue; 85 } else { 86 if(!match(node->name, r->target, stem)) continue; 87 } 88 if(cnt[r->rule] >= nreps) continue; 89 cnt[r->rule]++; 90 91 /* if(r->attr&VIR) 92 * node->flags |= VIRTUAL; 93 * if(r->attr&NOREC) 94 * node->flags |= NORECIPE; 95 * if(r->attr&DEL) 96 * node->flags |= DELETE; 97 */ 98 99 if(!r->tail || !r->tail->s || !*r->tail->s) { 100 a->next = newarc((Node *)0, r, strdup(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, rmatch, NREGEXP); 106 else 107 subst(stem, w->s, buf); 108 a->next = newarc(applyrules(buf, cnt), r, strdup(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, (char *)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 sprint(buf, "%s ", (*s == ' ')? s:""); 183 Bprint(&stdout, "%s%s@%ld: time=%ld flags=0x%x next=%ld\n", 184 s, n->name, n, n->time, n->flags, n->next); 185 for(a = n->prereqs; a; a = a->next) 186 dumpa(buf, a); 187 } 188 189 static void 190 trace(char *s, Arc *a) 191 { 192 fprint(2, "\t%s", s); 193 while(a){ 194 fprint(2, " <-(%s:%d)- %s", a->r->file, a->r->line, 195 a->n? a->n->name:""); 196 if(a->n){ 197 for(a = a->n->prereqs; a; a = a->next) 198 if(*a->r->recipe) break; 199 } else 200 a = 0; 201 } 202 fprint(2, "\n"); 203 } 204 205 static void 206 cyclechk(Node *n) 207 { 208 Arc *a; 209 210 if((n->flags&CYCLE) && n->prereqs){ 211 fprint(2, "mk: cycle in graph detected at target %s\n", n->name); 212 Exit(); 213 } 214 n->flags |= CYCLE; 215 for(a = n->prereqs; a; a = a->next) 216 if(a->n) 217 cyclechk(a->n); 218 n->flags &= ~CYCLE; 219 } 220 221 static void 222 ambiguous(Node *n) 223 { 224 Arc *a; 225 Rule *r = 0; 226 Arc *la; 227 int bad = 0; 228 229 la = 0; 230 for(a = n->prereqs; a; a = a->next){ 231 if(a->n) 232 ambiguous(a->n); 233 if(*a->r->recipe == 0) continue; 234 if(r == 0) 235 r = a->r, la = a; 236 else{ 237 if(r->recipe != a->r->recipe){ 238 if((r->attr&META) && !(a->r->attr&META)){ 239 la->flag |= TOGO; 240 r = a->r, la = a; 241 } else if(!(r->attr&META) && (a->r->attr&META)){ 242 a->flag |= TOGO; 243 continue; 244 } 245 } 246 if(r->recipe != a->r->recipe){ 247 if(bad == 0){ 248 fprint(2, "mk: ambiguous recipes for %s:\n", n->name); 249 bad = 1; 250 trace(n->name, la); 251 } 252 trace(n->name, a); 253 } 254 } 255 } 256 if(bad) 257 Exit(); 258 togo(n); 259 } 260 261 static void 262 attribute(Node *n) 263 { 264 register Arc *a; 265 266 for(a = n->prereqs; a; a = a->next){ 267 if(a->r->attr&VIR) 268 n->flags |= VIRTUAL; 269 if(a->r->attr&NOREC) 270 n->flags |= NORECIPE; 271 if(a->r->attr&DEL) 272 n->flags |= DELETE; 273 if(a->n) 274 attribute(a->n); 275 } 276 if(n->flags&VIRTUAL) 277 n->time = 0; 278 } 279