graph.c 5.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279
  1. #include "mk.h"
  2. static Node *applyrules(char *, char *);
  3. static void togo(Node *);
  4. static int vacuous(Node *);
  5. static Node *newnode(char *);
  6. static void trace(char *, Arc *);
  7. static void cyclechk(Node *);
  8. static void ambiguous(Node *);
  9. static void attribute(Node *);
  10. Node *
  11. graph(char *target)
  12. {
  13. Node *node;
  14. char *cnt;
  15. cnt = rulecnt();
  16. node = applyrules(target, cnt);
  17. free(cnt);
  18. cyclechk(node);
  19. node->flags |= PROBABLE; /* make sure it doesn't get deleted */
  20. vacuous(node);
  21. ambiguous(node);
  22. attribute(node);
  23. return(node);
  24. }
  25. static Node *
  26. applyrules(char *target, char *cnt)
  27. {
  28. Symtab *sym;
  29. Node *node;
  30. Rule *r;
  31. Arc head, *a = &head;
  32. Word *w;
  33. char stem[NAMEBLOCK], buf[NAMEBLOCK];
  34. Resub rmatch[NREGEXP];
  35. /* print("applyrules(%lux='%s')\n", target, target);/**/
  36. sym = symlook(target, S_NODE, 0);
  37. if(sym)
  38. return (Node *)(sym->value);
  39. target = strdup(target);
  40. node = newnode(target);
  41. head.n = 0;
  42. head.next = 0;
  43. sym = symlook(target, S_TARGET, 0);
  44. memset((char*)rmatch, 0, sizeof(rmatch));
  45. for(r = sym? (Rule *)(sym->value):0; r; r = r->chain){
  46. if(r->attr&META) continue;
  47. if(strcmp(target, r->target)) continue;
  48. if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue; /* no effect; ignore */
  49. if(cnt[r->rule] >= nreps) continue;
  50. cnt[r->rule]++;
  51. node->flags |= PROBABLE;
  52. /* if(r->attr&VIR)
  53. * node->flags |= VIRTUAL;
  54. * if(r->attr&NOREC)
  55. * node->flags |= NORECIPE;
  56. * if(r->attr&DEL)
  57. * node->flags |= DELETE;
  58. */
  59. if(!r->tail || !r->tail->s || !*r->tail->s) {
  60. a->next = newarc((Node *)0, r, "", rmatch);
  61. a = a->next;
  62. } else
  63. for(w = r->tail; w; w = w->next){
  64. a->next = newarc(applyrules(w->s, cnt), r, "", rmatch);
  65. a = a->next;
  66. }
  67. cnt[r->rule]--;
  68. head.n = node;
  69. }
  70. for(r = metarules; r; r = r->next){
  71. if((!r->recipe || !*r->recipe) && (!r->tail || !r->tail->s || !*r->tail->s)) continue; /* no effect; ignore */
  72. if ((r->attr&NOVIRT) && a != &head && (a->r->attr&VIR))
  73. continue;
  74. if(r->attr&REGEXP){
  75. stem[0] = 0;
  76. patrule = r;
  77. memset((char*)rmatch, 0, sizeof(rmatch));
  78. if(regexec(r->pat, node->name, rmatch, NREGEXP) == 0)
  79. continue;
  80. } else {
  81. if(!match(node->name, r->target, stem)) continue;
  82. }
  83. if(cnt[r->rule] >= nreps) continue;
  84. cnt[r->rule]++;
  85. /* if(r->attr&VIR)
  86. * node->flags |= VIRTUAL;
  87. * if(r->attr&NOREC)
  88. * node->flags |= NORECIPE;
  89. * if(r->attr&DEL)
  90. * node->flags |= DELETE;
  91. */
  92. if(!r->tail || !r->tail->s || !*r->tail->s) {
  93. a->next = newarc((Node *)0, r, stem, rmatch);
  94. a = a->next;
  95. } else
  96. for(w = r->tail; w; w = w->next){
  97. if(r->attr&REGEXP)
  98. regsub(w->s, buf, sizeof(buf), rmatch, NREGEXP);
  99. else
  100. subst(stem, w->s, buf, sizeof(buf));
  101. a->next = newarc(applyrules(buf, cnt), r, stem, rmatch);
  102. a = a->next;
  103. }
  104. cnt[r->rule]--;
  105. }
  106. a->next = node->prereqs;
  107. node->prereqs = head.next;
  108. return(node);
  109. }
  110. static void
  111. togo(Node *node)
  112. {
  113. Arc *la, *a;
  114. /* delete them now */
  115. la = 0;
  116. for(a = node->prereqs; a; la = a, a = a->next)
  117. if(a->flag&TOGO){
  118. if(a == node->prereqs)
  119. node->prereqs = a->next;
  120. else
  121. la->next = a->next, a = la;
  122. }
  123. }
  124. static
  125. vacuous(Node *node)
  126. {
  127. Arc *la, *a;
  128. int vac = !(node->flags&PROBABLE);
  129. if(node->flags&READY)
  130. return(node->flags&VACUOUS);
  131. node->flags |= READY;
  132. for(a = node->prereqs; a; a = a->next)
  133. if(a->n && vacuous(a->n) && (a->r->attr&META))
  134. a->flag |= TOGO;
  135. else
  136. vac = 0;
  137. /* if a rule generated arcs that DON'T go; no others from that rule go */
  138. for(a = node->prereqs; a; a = a->next)
  139. if((a->flag&TOGO) == 0)
  140. for(la = node->prereqs; la; la = la->next)
  141. if((la->flag&TOGO) && (la->r == a->r)){
  142. la->flag &= ~TOGO;
  143. }
  144. togo(node);
  145. if(vac)
  146. node->flags |= VACUOUS;
  147. return(vac);
  148. }
  149. static Node *
  150. newnode(char *name)
  151. {
  152. register Node *node;
  153. node = (Node *)Malloc(sizeof(Node));
  154. symlook(name, S_NODE, (void *)node);
  155. node->name = name;
  156. node->time = timeof(name, 0);
  157. node->prereqs = 0;
  158. node->flags = node->time? PROBABLE : 0;
  159. node->next = 0;
  160. return(node);
  161. }
  162. void
  163. dumpn(char *s, Node *n)
  164. {
  165. char buf[1024];
  166. Arc *a;
  167. Bprint(&bout, "%s%s@%p: time=%ld flags=0x%x next=%p\n",
  168. s, n->name, n, n->time, n->flags, n->next);
  169. for(a = n->prereqs; a; a = a->next){
  170. sprint(buf, "%s ", (*s == ' ')? s:"");
  171. dumpa(buf, a);
  172. }
  173. }
  174. static void
  175. trace(char *s, Arc *a)
  176. {
  177. fprint(2, "\t%s", s);
  178. while(a){
  179. fprint(2, " <-(%s:%d)- %s", a->r->file, a->r->line,
  180. a->n? a->n->name:"");
  181. if(a->n){
  182. for(a = a->n->prereqs; a; a = a->next)
  183. if(*a->r->recipe) break;
  184. } else
  185. a = 0;
  186. }
  187. fprint(2, "\n");
  188. }
  189. static void
  190. cyclechk(Node *n)
  191. {
  192. Arc *a;
  193. if((n->flags&CYCLE) && n->prereqs){
  194. fprint(2, "mk: cycle in graph detected at target %s\n", n->name);
  195. Exit();
  196. }
  197. n->flags |= CYCLE;
  198. for(a = n->prereqs; a; a = a->next)
  199. if(a->n)
  200. cyclechk(a->n);
  201. n->flags &= ~CYCLE;
  202. }
  203. static void
  204. ambiguous(Node *n)
  205. {
  206. Arc *a;
  207. Rule *r = 0;
  208. Arc *la;
  209. int bad = 0;
  210. la = 0;
  211. for(a = n->prereqs; a; a = a->next){
  212. if(a->n)
  213. ambiguous(a->n);
  214. if(*a->r->recipe == 0) continue;
  215. if(r == 0)
  216. r = a->r, la = a;
  217. else{
  218. if(r->recipe != a->r->recipe){
  219. if((r->attr&META) && !(a->r->attr&META)){
  220. la->flag |= TOGO;
  221. r = a->r, la = a;
  222. } else if(!(r->attr&META) && (a->r->attr&META)){
  223. a->flag |= TOGO;
  224. continue;
  225. }
  226. }
  227. if(r->recipe != a->r->recipe){
  228. if(bad == 0){
  229. fprint(2, "mk: ambiguous recipes for %s:\n", n->name);
  230. bad = 1;
  231. trace(n->name, la);
  232. }
  233. trace(n->name, a);
  234. }
  235. }
  236. }
  237. if(bad)
  238. Exit();
  239. togo(n);
  240. }
  241. static void
  242. attribute(Node *n)
  243. {
  244. register Arc *a;
  245. for(a = n->prereqs; a; a = a->next){
  246. if(a->r->attr&VIR)
  247. n->flags |= VIRTUAL;
  248. if(a->r->attr&NOREC)
  249. n->flags |= NORECIPE;
  250. if(a->r->attr&DEL)
  251. n->flags |= DELETE;
  252. if(a->n)
  253. attribute(a->n);
  254. }
  255. if(n->flags&VIRTUAL)
  256. n->time = 0;
  257. }