9base

revived minimalist port of Plan 9 userland to Unix
git clone git://git.suckless.org/9base
Log | Files | Refs | README | LICENSE

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