graph.c (5833B)
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, 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®EXP) 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 }