ref: 12e226ac6798412271020d42645f69138715c519
dir: /utils/mk/graph.c/
#include "mk.h" static Node *applyrules(char *, char *); static void togo(Node *); static int vacuous(Node *); static Node *newnode(char *); static void trace(char *, Arc *); static void cyclechk(Node *); static void ambiguous(Node *); static void attribute(Node *); Node * graph(char *target) { Node *node; char *cnt; cnt = rulecnt(); node = applyrules(target, cnt); free(cnt); cyclechk(node); node->flags |= PROBABLE; /* make sure it doesn't get deleted */ vacuous(node); ambiguous(node); attribute(node); return(node); } static Node * applyrules(char *target, char *cnt) { Symtab *sym; Node *node; Rule *r; Arc head, *a = &head; Word *w; char stem[NAMEBLOCK], buf[NAMEBLOCK]; Resub rmatch[NREGEXP]; /* print("applyrules(%lux='%s')\n", target, target);/**/ sym = symlook(target, S_NODE, 0); if(sym) return (Node *)(sym->value); target = strdup(target); node = newnode(target); head.n = 0; head.next = 0; sym = symlook(target, S_TARGET, 0); memset((char*)rmatch, 0, sizeof(rmatch)); for(r = sym? (Rule *)(sym->value):0; r; r = r->chain){ if(r->attr&META) continue; if(strcmp(target, r->target)) continue; if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue; /* no effect; ignore */ if(cnt[r->rule] >= nreps) continue; cnt[r->rule]++; node->flags |= PROBABLE; /* if(r->attr&VIR) * node->flags |= VIRTUAL; * if(r->attr&NOREC) * node->flags |= NORECIPE; * if(r->attr&DEL) * node->flags |= DELETE; */ if(!r->tail || !r->tail->s || !*r->tail->s) { a->next = newarc((Node *)0, r, "", rmatch); a = a->next; } else for(w = r->tail; w; w = w->next){ a->next = newarc(applyrules(w->s, cnt), r, "", rmatch); a = a->next; } cnt[r->rule]--; head.n = node; } for(r = metarules; r; r = r->next){ if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue; /* no effect; ignore */ if ((r->attr&NOVIRT) && a != &head && (a->r->attr&VIR)) continue; if(r->attr®EXP){ stem[0] = 0; patrule = r; memset((char*)rmatch, 0, sizeof(rmatch)); if(regexec(r->pat, node->name, rmatch, NREGEXP) == 0) continue; } else { if(!match(node->name, r->target, stem)) continue; } if(cnt[r->rule] >= nreps) continue; cnt[r->rule]++; /* if(r->attr&VIR) * node->flags |= VIRTUAL; * if(r->attr&NOREC) * node->flags |= NORECIPE; * if(r->attr&DEL) * node->flags |= DELETE; */ if(!r->tail || !r->tail->s || !*r->tail->s) { a->next = newarc((Node *)0, r, stem, rmatch); a = a->next; } else for(w = r->tail; w; w = w->next){ if(r->attr®EXP) regsub(w->s, buf, rmatch, NREGEXP); else subst(stem, w->s, buf); a->next = newarc(applyrules(buf, cnt), r, stem, rmatch); a = a->next; } cnt[r->rule]--; } a->next = node->prereqs; node->prereqs = head.next; return(node); } static void togo(Node *node) { Arc *la, *a; /* delete them now */ la = 0; for(a = node->prereqs; a; la = a, a = a->next) if(a->flag&TOGO){ if(a == node->prereqs) node->prereqs = a->next; else la->next = a->next, a = la; } } static int vacuous(Node *node) { Arc *la, *a; int vac = !(node->flags&PROBABLE); if(node->flags&READY) return(node->flags&VACUOUS); node->flags |= READY; for(a = node->prereqs; a; a = a->next) if(a->n && vacuous(a->n) && (a->r->attr&META)) a->flag |= TOGO; else vac = 0; /* if a rule generated arcs that DON'T go; no others from that rule go */ for(a = node->prereqs; a; a = a->next) if((a->flag&TOGO) == 0) for(la = node->prereqs; la; la = la->next) if((la->flag&TOGO) && (la->r == a->r)){ la->flag &= ~TOGO; } togo(node); if(vac) node->flags |= VACUOUS; return(vac); } static Node * newnode(char *name) { register Node *node; node = (Node *)Malloc(sizeof(Node)); symlook(name, S_NODE, (void *)node); node->name = name; node->time = timeof(name, 0); node->prereqs = 0; node->flags = node->time? PROBABLE : 0; node->next = 0; return(node); } void dumpn(char *s, Node *n) { char buf[1024]; Arc *a; sprint(buf, "%s ", (*s == ' ')? s:""); Bprint(&bout, "%s%s@%ld: time=%ld flags=0x%x next=%ld\n", s, n->name, n, n->time, n->flags, n->next); for(a = n->prereqs; a; a = a->next) dumpa(buf, a); } static void trace(char *s, Arc *a) { fprint(2, "\t%s", s); while(a){ fprint(2, " <-(%s:%d)- %s", a->r->file, a->r->line, a->n? a->n->name:""); if(a->n){ for(a = a->n->prereqs; a; a = a->next) if(*a->r->recipe) break; } else a = 0; } fprint(2, "\n"); } static void cyclechk(Node *n) { Arc *a; if((n->flags&CYCLE) && n->prereqs){ fprint(2, "mk: cycle in graph detected at target %s\n", n->name); Exit(); } n->flags |= CYCLE; for(a = n->prereqs; a; a = a->next) if(a->n) cyclechk(a->n); n->flags &= ~CYCLE; } static void ambiguous(Node *n) { Arc *a; Rule *r = 0; Arc *la; int bad = 0; la = 0; for(a = n->prereqs; a; a = a->next){ if(a->n) ambiguous(a->n); if(*a->r->recipe == 0) continue; if(r == 0) r = a->r, la = a; else{ if(r->recipe != a->r->recipe){ if((r->attr&META) && !(a->r->attr&META)){ la->flag |= TOGO; r = a->r, la = a; } else if(!(r->attr&META) && (a->r->attr&META)){ a->flag |= TOGO; continue; } } if(r->recipe != a->r->recipe){ if(bad == 0){ fprint(2, "mk: ambiguous recipes for %s:\n", n->name); bad = 1; trace(n->name, la); } trace(n->name, a); } } } if(bad) Exit(); togo(n); } static void attribute(Node *n) { register Arc *a; for(a = n->prereqs; a; a = a->next){ if(a->r->attr&VIR) n->flags |= VIRTUAL; if(a->r->attr&NOREC) n->flags |= NORECIPE; if(a->r->attr&DEL) n->flags |= DELETE; if(a->n) attribute(a->n); } if(n->flags&VIRTUAL) n->time = 0; }