sys/src/cmd/mk/graph.c

   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&REGEXP){
  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&REGEXP)
 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 }