1#include "internal.h"
2
3#include <stdio.h>
4#include <stdlib.h>
5#include <string.h>
6#include <unistd.h>
7
8struct SubGraphStack {
9 char **v;
10 size_t n;
11 struct Arena arena;
12};
13
14static int
15isempty(const char *s)
16{
17 return !s || !s[0];
18}
19
20static int
21sameprefix(const char *a, const char *b)
22{
23 if (isempty(a))
24 return isempty(b);
25 if (isempty(b))
26 return 0;
27 return strcmp(a, b) == 0;
28}
29
30static int
31isunderprefix(const char *prefix, const char *name)
32{
33 size_t n;
34
35 if (isempty(prefix))
36 return 1;
37 n = strlen(prefix);
38 if (strncmp(name, prefix, n) != 0)
39 return 0;
40 return name[n] == 0 || name[n] == '/';
41}
42
43static int
44samelist(const struct StrList *a, const struct StrList *b)
45{
46 size_t i;
47
48 if (a->n != b->n)
49 return 0;
50 for (i = 0; i < a->n; i++) {
51 if (strcmp(a->v[i], b->v[i]) != 0)
52 return 0;
53 }
54 return 1;
55}
56
57static void
58addenvassign(struct StrList *list, const char *name, const char *val)
59{
60 char *s;
61
62 s = xmalloc(strlen(name) + 1 + strlen(val) + 1);
63 strcpy(s, name);
64 strcat(s, "=");
65 strcat(s, val);
66 list->v = xrealloc(list->v, (list->n + 1) * sizeof(list->v[0]));
67 list->v[list->n++] = s;
68}
69
70static char *
71joinprefix(const char *parent, const char *child)
72{
73 char *raw, *norm;
74
75 if (isempty(child))
76 return parent ? xstrdup(parent) : 0;
77 if (child[0] == '/')
78 return normpath(child);
79 if (isempty(parent))
80 return normpath(child);
81 raw = cat3(parent, "/", child);
82 norm = normpath(raw);
83 free(raw);
84 return norm;
85}
86
87static char *
88rebaseword(const char *prefix, const char *name)
89{
90 char *raw, *norm;
91
92 if (!name[0] || name[0] == '/')
93 return normpath(name);
94 if (isempty(prefix))
95 return normpath(name);
96 raw = cat3(prefix, "/", name);
97 norm = normpath(raw);
98 free(raw);
99 return norm;
100}
101
102static char *
103prefixrecipe(const char *prefix, const char *body)
104{
105 size_t nprefix, nbody;
106 char *out;
107
108 if (isempty(prefix) || strcmp(prefix, ".") == 0)
109 return xstrdup(body);
110 nprefix = strlen(prefix);
111 nbody = strlen(body);
112 out = xmalloc(5 + nprefix + 4 + nbody + 1);
113 memcpy(out, "cd ", 3);
114 memcpy(out + 3, prefix, nprefix);
115 memcpy(out + 3 + nprefix, " && ", 4);
116 memcpy(out + 7 + nprefix, body, nbody);
117 out[7 + nprefix + nbody] = 0;
118 return out;
119}
120
121static int
122resolvegoals(const struct SubGraph *sg, struct StrList *out)
123{
124 const struct Target *t;
125
126 memset(out, 0, sizeof(*out));
127 if (sg->goals.n) {
128 size_t i;
129
130 for (i = 0; i < sg->goals.n; i++) {
131 char *name;
132
133 name = rebaseword(sg->prefix, sg->goals.v[i]);
134 addstr(out, name);
135 free(name);
136 }
137 return 0;
138 }
139 t = defaulttarget(&sg->graph, sg->prefix);
140 if (t) {
141 addstr(out, t->name);
142 return 0;
143 }
144 fprintf(stderr, "submake has no default target\n");
145 return -1;
146}
147
148/* when expanding a submake, start from a target name and walk the graph backwards
149 * only for that target. if we expand the entire subgraph from the beginning,
150 * we get a lot of cases where the subgraph will recurse and try to create a new
151 * subgraph of itself */
152static void
153markreachable(const struct Graph *graph, const char *name, unsigned char *seen)
154{
155 const struct Target *t;
156 size_t i, idx;
157
158 t = findctarget(graph, name);
159 if (!t)
160 return;
161 idx = (size_t)(t - graph->v);
162 if (seen[idx])
163 return;
164 seen[idx] = 1;
165 for (i = 0; i < t->prereqs.n; i++)
166 markreachable(graph, t->prereqs.v[i], seen);
167 for (i = 0; i < t->impprereqs.n; i++)
168 markreachable(graph, t->impprereqs.v[i], seen);
169 for (i = 0; i < t->order_only.n; i++)
170 markreachable(graph, t->order_only.v[i], seen);
171}
172
173static int
174allsubmake(const struct Target *t)
175{
176 size_t i;
177
178 if (!t || t->recipes.n == 0)
179 return 0;
180 for (i = 0; i < t->recipes.n; i++) {
181 if (!t->recipes.v[i].submake)
182 return 0;
183 }
184 return 1;
185}
186
187static void
188pushstack(struct SubGraphStack *stack, const char *key)
189{
190 stack->v = xrealloc(stack->v, (stack->n + 1) * sizeof(stack->v[0]));
191 stack->v[stack->n++] = arena_strdup(&stack->arena, key);
192}
193
194static void
195popstack(struct SubGraphStack *stack)
196{
197 if (!stack->n)
198 return;
199 stack->n--;
200}
201
202static int
203instack(const struct SubGraphStack *stack, const char *key)
204{
205 size_t i;
206
207 for (i = 0; i < stack->n; i++) {
208 if (strcmp(stack->v[i], key) == 0)
209 return 1;
210 }
211 return 0;
212}
213
214static char *
215subgraphkey(const struct SubGraph *sg)
216{
217 size_t i, n, pos, len;
218 char *key;
219
220 n = strlen(sg->cwd) + 1 + strlen(sg->makefile ? sg->makefile : "") + 1;
221 for (i = 0; i < sg->envassigns.n; i++)
222 n += strlen(sg->envassigns.v[i]) + 1;
223 for (i = 0; i < sg->assigns.n; i++)
224 n += strlen(sg->assigns.v[i]) + 1;
225 key = xmalloc(n + 1);
226 pos = 0;
227 len = strlen(sg->cwd);
228 memcpy(key + pos, sg->cwd, len);
229 pos += len;
230 key[pos++] = '|';
231 if (sg->makefile) {
232 len = strlen(sg->makefile);
233 memcpy(key + pos, sg->makefile, len);
234 pos += len;
235 }
236 for (i = 0; i < sg->envassigns.n; i++) {
237 key[pos++] = '|';
238 len = strlen(sg->envassigns.v[i]);
239 memcpy(key + pos, sg->envassigns.v[i], len);
240 pos += len;
241 }
242 for (i = 0; i < sg->assigns.n; i++) {
243 key[pos++] = '|';
244 len = strlen(sg->assigns.v[i]);
245 memcpy(key + pos, sg->assigns.v[i], len);
246 pos += len;
247 }
248 key[pos] = 0;
249 return key;
250}
251
252static void
253removerecipe(struct RecipeList *list, size_t idx)
254{
255 size_t i;
256
257 free(list->v[idx].body);
258 freesubmake(&list->v[idx].sm);
259 for (i = idx + 1; i < list->n; i++)
260 list->v[i - 1] = list->v[i];
261 list->n--;
262 if (!list->n) {
263 free(list->v);
264 list->v = 0;
265 return;
266 }
267 list->v = xrealloc(list->v, list->n * sizeof(list->v[0]));
268}
269
270static void
271scopelist(struct StrList *list, const char *prefix)
272{
273 size_t i;
274
275 for (i = 0; i < list->n; i++) {
276 char *name;
277
278 name = rebaseword(prefix, list->v[i]);
279 free(list->v[i]);
280 list->v[i] = name;
281 }
282}
283
284static void
285scoperecipes(struct RecipeList *list, const char *prefix)
286{
287 size_t i;
288
289 for (i = 0; i < list->n; i++) {
290 char *body;
291
292 body = prefixrecipe(prefix, list->v[i].body);
293 free(list->v[i].body);
294 list->v[i].body = body;
295 }
296}
297
298static void
299scopegraph(struct Graph *graph, const char *prefix)
300{
301 size_t i;
302
303 if (isempty(prefix))
304 return;
305 for (i = 0; i < graph->n; i++) {
306 char *name;
307
308 name = rebaseword(prefix, graph->v[i].name);
309 graph->v[i].name = intern(name);
310 free(name);
311 free(graph->v[i].owner);
312 if ((graph->v[i].defined || graph->v[i].recipes.n > 0) &&
313 isunderprefix(prefix, graph->v[i].name))
314 graph->v[i].owner = xstrdup(prefix);
315 else
316 graph->v[i].owner = 0;
317 scopelist(&graph->v[i].prereqs, prefix);
318 scopelist(&graph->v[i].impprereqs, prefix);
319 scopelist(&graph->v[i].order_only, prefix);
320 scoperecipes(&graph->v[i].recipes, prefix);
321 }
322}
323
324static int
325mergetarget(struct Graph *graph, const struct Target *src)
326{
327 struct Target *dst;
328
329 dst = findtarget(graph, src->name);
330 if (!dst) {
331 graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
332 dst = &graph->v[graph->n++];
333 memset(dst, 0, sizeof(*dst));
334 dst->name = src->name;
335 if (src->owner)
336 dst->owner = xstrdup(src->owner);
337 } else if (!dst->owner && src->owner) {
338 dst->owner = xstrdup(src->owner);
339 } else if (dst->owner && src->owner && !sameprefix(dst->owner, src->owner)) {
340 /*
341 * shared targets like ../lib/libzstd.a may be referenced from
342 * multiple sibling subgraphs; if that happens, treat the
343 * target as shared instead of attributing it to one owner and erroring.
344 */
345 free(dst->owner);
346 dst->owner = 0;
347 } else if (dst->defined && src->defined && dst->dcolon != src->dcolon) {
348 fprintf(stderr, "target file `%s' has both : and :: entries, i can't handle that!\n", dst->name);
349 return -1;
350 }
351 if (!dst->defined && src->defined)
352 dst->dcolon = src->dcolon;
353 dst->defined |= src->defined;
354 if (src->defined)
355 dst->dcolon = src->dcolon;
356 addwords(&dst->prereqs, &src->prereqs);
357 addwords(&dst->impprereqs, &src->impprereqs);
358 addwords(&dst->order_only, &src->order_only);
359 addrecipes(&dst->recipes, &src->recipes);
360 return 0;
361}
362
363static int
364addgraphsub(struct Graph *graph, struct SubGraph *child)
365{
366 graph->subs = xrealloc(graph->subs, (graph->nsubs + 1) * sizeof(graph->subs[0]));
367 graph->subs[graph->nsubs++] = *child;
368 memset(child, 0, sizeof(*child));
369 return 0;
370}
371
372/* in make, recursive make calls run sequentially*/
373static void
374subgraphorder(struct Graph *graph, const char *owner, const struct StrList *prev)
375{
376 size_t i, j, n;
377
378 if (!prev->n)
379 return;
380 n = owner ? strlen(owner) : 0;
381 for (i = 0; i < graph->n; i++) {
382 struct Target *t = &graph->v[i];
383
384 if (!t->owner)
385 continue;
386 if (strncmp(t->owner, owner, n) != 0)
387 continue;
388 if (t->owner[n] != 0 && t->owner[n] != '/')
389 continue;
390 for (j = 0; j < prev->n; j++) {
391 if (!hasword(&t->order_only, prev->v[j]))
392 addstr(&t->order_only, prev->v[j]);
393 }
394 }
395}
396
397static struct SubGraph *
398findgraphsub(struct Graph *graph, const char *prefix)
399{
400 size_t i;
401
402 for (i = 0; i < graph->nsubs; i++) {
403 if (sameprefix(graph->subs[i].prefix, prefix))
404 return &graph->subs[i];
405 }
406 return 0;
407}
408
409static int
410sameinvocation(const struct SubGraph *a, const struct SubGraph *b)
411{
412 if (strcmp(a->cwd, b->cwd) != 0)
413 return 0;
414 if (!!a->makefile != !!b->makefile)
415 return 0;
416 if (a->makefile && strcmp(a->makefile, b->makefile) != 0)
417 return 0;
418 if (!samelist(&a->envassigns, &b->envassigns))
419 return 0;
420 if (!samelist(&a->assigns, &b->assigns))
421 return 0;
422 if (!samelist(&a->flags, &b->flags))
423 return 0;
424 return 1;
425}
426
427static void
428mergesubmeta(struct SubGraph *dst, struct SubGraph *src)
429{
430 size_t i;
431
432 for (i = 0; i < src->parents.n; i++) {
433 if (!hasword(&dst->parents, src->parents.v[i]))
434 addstr(&dst->parents, src->parents.v[i]);
435 }
436 for (i = 0; i < src->goals.n; i++) {
437 if (!hasword(&dst->goals, src->goals.v[i]))
438 addstr(&dst->goals, src->goals.v[i]);
439 }
440 freesubgraph(src);
441 memset(src, 0, sizeof(*src));
442}
443
444static int
445mergechildgraph(struct SubGraph *parent,
446 const char *tname,
447 struct SubGraph *child,
448 const struct StrList *goals)
449{
450 struct SubGraph *known;
451 unsigned char *reachable;
452 struct Target *t;
453 size_t i;
454
455 known = sameprefix(parent->prefix, child->prefix) ? 0 : findgraphsub(&parent->graph, child->prefix);
456 if (known && !sameinvocation(known, child)) {
457 fprintf(stderr, "multiple incompatible subgraphs map to %s/build.ninja\n",
458 child->prefix ? child->prefix : ".");
459 return -1;
460 }
461 if (!known) {
462 reachable = xmalloc(child->graph.n ? child->graph.n : 1);
463 memset(reachable, 0, child->graph.n ? child->graph.n : 1);
464 for (i = 0; i < goals->n; i++)
465 markreachable(&child->graph, goals->v[i], reachable);
466 for (i = 0; i < child->graph.n; i++) {
467 if (!reachable[i])
468 continue;
469 if (mergetarget(&parent->graph, &child->graph.v[i]) < 0) {
470 free(reachable);
471 return -1;
472 }
473 }
474 free(reachable);
475 }
476 t = findtarget(&parent->graph, tname);
477 if (!t) {
478 fprintf(stderr, "lost parent target `%s' while expanding submake\n", tname);
479 return -1;
480 }
481 for (i = 0; i < goals->n; i++) {
482 if (!hasword(&t->prereqs, goals->v[i]))
483 addstr(&t->prereqs, goals->v[i]);
484 }
485 if (child->prefix && child->prefix[0] && isunderprefix(child->prefix, tname)) {
486 size_t n;
487 const char *local;
488
489 n = strlen(child->prefix);
490 local = tname + n;
491 if (*local == '/')
492 local++;
493 if (*local && !hasword(&t->prereqs, local))
494 addstr(&t->prereqs, local);
495 }
496 if (!sameprefix(parent->prefix, child->prefix)) {
497 if (known) {
498 mergesubmeta(known, child);
499 } else if (addgraphsub(&parent->graph, child) < 0) {
500 return -1;
501 }
502 }
503 return 0;
504}
505
506static int buildsubgraph0(struct SubGraph *sg, struct SubGraphStack *stack);
507
508static int
509expandsubgraphs(struct SubGraph *sg, struct SubGraphStack *stack)
510{
511 struct StrList roots;
512 unsigned char *reachable;
513 size_t i, n;
514
515 if (resolvegoals(sg, &roots) < 0)
516 return -1;
517 for (i = 0; i < sg->graph.n; i++) {
518 if (!targetownedby(&sg->graph.v[i], sg->prefix))
519 continue;
520 if (!sg->graph.v[i].phony && !allsubmake(&sg->graph.v[i]))
521 continue;
522 if (!hasword(&roots, sg->graph.v[i].name))
523 addstr(&roots, sg->graph.v[i].name);
524 }
525 n = sg->graph.n;
526 reachable = xmalloc(n ? n : 1);
527 memset(reachable, 0, n ? n : 1);
528 for (i = 0; i < roots.n; i++)
529 markreachable(&sg->graph, roots.v[i], reachable);
530 freestrs(&roots);
531
532 for (i = 0; i < n; i++) {
533 size_t k;
534 const char *tname;
535 struct StrList prevgoals;
536
537 if (!reachable[i])
538 continue;
539
540 memset(&prevgoals, 0, sizeof(prevgoals));
541 tname = sg->graph.v[i].name;
542 for (k = 0; k < sg->graph.v[i].recipes.n;) {
543 struct Recipe *r;
544 struct SubGraph child;
545 struct StrList goals;
546 int rc;
547
548 r = &sg->graph.v[i].recipes.v[k];
549 if (!r->submake) {
550 k++;
551 continue;
552 }
553 memset(&child, 0, sizeof(child));
554 child.cwd = r->sm.dir ? joinpath(sg->cwd, r->sm.dir) : xstrdup(sg->cwd);
555 child.prefix = joinprefix(sg->prefix, r->sm.dir);
556 child.mode = sg->mode;
557 addstr(&child.parents, tname);
558 if (r->sm.makefile)
559 child.makefile = xstrdup(r->sm.makefile);
560 {
561 size_t ei;
562
563 for (ei = 0; ei < sg->graph.v[i].env.n; ei++) {
564 const struct Var *v = &sg->graph.v[i].env.v[ei];
565
566 if (!v->exported)
567 continue;
568 addenvassign(&child.envassigns, v->name, v->val);
569 }
570 }
571 addwords(&child.assigns, &r->sm.assigns);
572 addwords(&child.flags, &r->sm.flags);
573 addwords(&child.goals, &r->sm.goals);
574 if (strcmp(child.cwd, sg->cwd) == 0 &&
575 (!child.makefile || strcmp(child.makefile, sg->makefile) == 0)) {
576 freesubgraph(&child);
577 k++;
578 continue;
579 }
580 rc = buildsubgraph0(&child, stack);
581 if (rc > 0) {
582 struct SubGraph *known;
583
584 known = sameprefix(sg->prefix, child.prefix) ? 0 : findgraphsub(&sg->graph, child.prefix);
585 if (known && sameinvocation(known, &child) && child.goals.n > 0) {
586 size_t gi;
587 struct Target *pt;
588
589 removerecipe(&sg->graph.v[i].recipes, k);
590 pt = findtarget(&sg->graph, tname);
591 for (gi = 0; pt && gi < child.goals.n; gi++) {
592 char *gname;
593
594 gname = rebaseword(child.prefix, child.goals.v[gi]);
595 if (!hasword(&pt->prereqs, gname))
596 addstr(&pt->prereqs, gname);
597 free(gname);
598 }
599 freesubgraph(&child);
600 continue;
601 }
602 freesubgraph(&child);
603 k++;
604 continue;
605 }
606 if (rc < 0) {
607 freesubgraph(&child);
608 freestrs(&prevgoals);
609 free(reachable);
610 return -1;
611 }
612 /* remove the make invocation, we replace it with a graph*/
613 removerecipe(&sg->graph.v[i].recipes, k);
614 if (resolvegoals(&child, &goals) < 0) {
615 freesubgraph(&child);
616 freestrs(&prevgoals);
617 free(reachable);
618 return -1;
619 }
620 subgraphorder(&child.graph, child.prefix, &prevgoals);
621 if (mergechildgraph(sg, tname, &child, &goals) < 0) {
622 freesubgraph(&child);
623 freestrs(&goals);
624 freestrs(&prevgoals);
625 free(reachable);
626 return -1;
627 }
628 freestrs(&prevgoals);
629 prevgoals = goals;
630 if (!sameprefix(sg->prefix, child.prefix))
631 continue;
632 freesubgraph(&child);
633 }
634 freestrs(&prevgoals);
635 }
636 free(reachable);
637 return 0;
638}
639
640static int
641buildsubgraph0(struct SubGraph *sg, struct SubGraphStack *stack)
642{
643 struct Ast ast;
644 struct Ast pre;
645 struct RuleSet rs;
646 char *src;
647 char *path;
648 char *oldcwd;
649 char *key;
650 int rc;
651 size_t i;
652 int envoverride;
653 size_t nenvassigns;
654
655 memset(&ast, 0, sizeof(ast));
656 memset(&pre, 0, sizeof(pre));
657 memset(&rs, 0, sizeof(rs));
658 freegraph(&sg->graph);
659 memset(&sg->graph, 0, sizeof(sg->graph));
660 src = 0;
661 path = 0;
662 oldcwd = getcwddup();
663 if (chdir(sg->cwd) != 0) {
664 free(oldcwd);
665 return 1;
666 }
667 free(sg->cwd);
668 sg->cwd = getcwddup();
669 if (loadmakefile(sg->makefile, &path, &src) < 0) {
670 chdir(oldcwd);
671 free(oldcwd);
672 return 1;
673 }
674 free(sg->makefile);
675 sg->makefile = xstrdup(path);
676 key = subgraphkey(sg);
677 if (instack(stack, key)) {
678 free(key);
679 free(path);
680 free(src);
681 chdir(oldcwd);
682 free(oldcwd);
683 return 1;
684 }
685 pushstack(stack, key);
686 free(key);
687 envoverride = 0;
688 for (i = 0; i < sg->flags.n; i++) {
689 if (strcmp(sg->flags.v[i], "-e") == 0) {
690 envoverride = 1;
691 break;
692 }
693 }
694 nenvassigns = sg->envassigns.n;
695 if (sg->envassigns.n || sg->assigns.n) {
696 char *assignsrc;
697 struct StrList allassigns;
698
699 memset(&allassigns, 0, sizeof(allassigns));
700 addwords(&allassigns, &sg->envassigns);
701 addwords(&allassigns, &sg->assigns);
702 assignsrc = appendassigns(xstrdup(""), &allassigns);
703 freestrs(&allassigns);
704 rc = parse("<command line>", assignsrc, &pre, sg->mode);
705 free(assignsrc);
706 if (rc < 0)
707 goto out;
708 for (i = 0; i < pre.n; i++) {
709 if (pre.v[i].kind != NODE_ASSIGN)
710 continue;
711 if (nenvassigns > 0) {
712 pre.v[i].data.assign.origin = envoverride ? ORIGIN_ENV_OVERRIDE : ORIGIN_ENV;
713 nenvassigns--;
714 } else {
715 pre.v[i].data.assign.origin = ORIGIN_COMMAND;
716 }
717 }
718 }
719 rc = parse(path, src, &ast, sg->mode);
720 if (rc < 0)
721 goto out;
722 rc = eval(path, &ast, sg->assigns.n ? &pre : 0, envoverride, sg->mode, &rs);
723 if (rc < 0)
724 goto out;
725 rc = buildgraph(&rs, &sg->goals, &sg->graph, sg->mode);
726 if (rc < 0)
727 goto out;
728 rc = expandgraph(&sg->graph, sg->mode);
729 if (rc < 0)
730 goto out;
731 scopegraph(&sg->graph, sg->prefix);
732 rc = expandsubgraphs(sg, stack);
733out:
734 freeruleset(&rs);
735 freeast(&pre);
736 freeast(&ast);
737 free(src);
738 free(path);
739 popstack(stack);
740 chdir(oldcwd);
741 free(oldcwd);
742 return rc;
743}
744
745int
746buildsubgraph(struct SubGraph *sg)
747{
748 struct SubGraphStack stack;
749 int rc;
750
751 memset(&stack, 0, sizeof(stack));
752 arena_init(&stack.arena, 0);
753 if (!sg->cwd)
754 sg->cwd = getcwddup();
755 rc = buildsubgraph0(sg, &stack);
756 if (rc < 0) {
757 while (stack.n)
758 popstack(&stack);
759 arena_free(&stack.arena);
760 free(stack.v);
761 return rc;
762 }
763 arena_free(&stack.arena);
764 free(stack.v);
765 return 0;
766}
767
768void
769freesubgraph(struct SubGraph *sg)
770{
771 if (!sg)
772 return;
773 free(sg->cwd);
774 sg->cwd = 0;
775 free(sg->prefix);
776 sg->prefix = 0;
777 free(sg->makefile);
778 sg->makefile = 0;
779 freestrs(&sg->parents);
780 freestrs(&sg->envassigns);
781 freestrs(&sg->assigns);
782 freestrs(&sg->flags);
783 freestrs(&sg->goals);
784 freegraph(&sg->graph);
785}
