1#include "shinobi.h"
2#include "internal.h"
3#include "posix.h"
4#include "gnu/pattern.h"
5
6#include <glob.h>
7#include <stdio.h>
8#include <stdlib.h>
9#include <string.h>
10
11/* graph builder */
12
13struct TAssign {
14 struct StrList targets;
15 char *lhs;
16 char *rhs;
17 enum AssignOp op;
18 enum Origin origin;
19};
20
21struct GraphState {
22 struct Graph *graph;
23 struct Env env;
24 const struct StrList *phony;
25 const struct RecipeList *defaultrule;
26 const struct RuleNode *rules;
27 size_t nrules;
28 struct PatRules patterns;
29 struct SufRules sufs;
30 struct TAssign *tas;
31 size_t ntas;
32 int saw_suffixes;
33 enum ShinMode mode;
34};
35
36static void
37seedsufs(struct SufRules *rules, const struct RuleNode *rule)
38{
39 char *from, *to;
40
41 if (rule->targets.n != 1 || rule->prereqs.n != 0 || rule->order_only.n != 0)
42 return;
43 if (issinglesuf(rule->targets.v[0], &from)) {
44 struct StrList list;
45
46 memset(&list, 0, sizeof(list));
47 list.v = &from;
48 list.n = 1;
49 addsufs(&rules->active, &list);
50 free(from);
51 return;
52 }
53 if (!issuf(rule->targets.v[0], &from, &to))
54 return;
55 {
56 char *tmp[2];
57 struct StrList list;
58
59 tmp[0] = from;
60 tmp[1] = to;
61 memset(&list, 0, sizeof(list));
62 list.v = tmp;
63 list.n = 2;
64 addsufs(&rules->active, &list);
65 }
66 free(from);
67 free(to);
68}
69
70static int
71targetmatches(const char *pat, const char *name)
72{
73 if (!ispat(pat))
74 return strcmp(pat, name) == 0;
75 return patmatches(pat, name);
76}
77
78/* we apply target assignments from the graphstate (gs.tas) to those specific
79 * targets, for some target like
80 *
81 * binary : LDFLAGS += -static
82 */
83static void
84applytassigns(struct GraphState *gs, struct EvalCtx *ctx, const char *name)
85{
86 size_t i, j;
87
88 for (i = 0; i < gs->ntas; i++) {
89 struct AssignNode in;
90
91 for (j = 0; j < gs->tas[i].targets.n; j++) {
92 if (!targetmatches(gs->tas[i].targets.v[j], name))
93 continue;
94 memset(&in, 0, sizeof(in));
95 in.lhs = gs->tas[i].lhs;
96 in.rhs = gs->tas[i].rhs;
97 in.op = gs->tas[i].op;
98 in.origin = gs->tas[i].origin;
99 evalassign(ctx, &in);
100 }
101 }
102}
103
104static void
105targetenv(struct GraphState *gs, struct EvalCtx *ctx, const struct Env *base, const char *name)
106{
107 if (base && base->n)
108 copyenv(ctx->env, base);
109 else
110 copyenv(ctx->env, &gs->env);
111 applytassigns(gs, ctx, name);
112}
113
114static int
115hasglobmeta(const char *s)
116{
117 size_t i;
118
119 for (i = 0; s[i]; i++) {
120 if (s[i] == '\\' && s[i + 1]) {
121 i++;
122 continue;
123 }
124 if (s[i] == '*' || s[i] == '?' || s[i] == '[')
125 return 1;
126 }
127 return 0;
128}
129
130static void
131addglobword(struct StrList *out, const char *s)
132{
133 glob_t g;
134 size_t i;
135 int rc;
136
137 if (!hasglobmeta(s)) {
138 addstr(out, s);
139 return;
140 }
141
142 memset(&g, 0, sizeof(g));
143 rc = glob(s, 0, 0, &g);
144 if (rc == 0 && g.gl_pathc > 0) {
145 for (i = 0; i < g.gl_pathc; i++)
146 addstr(out, g.gl_pathv[i]);
147 } else {
148 addstr(out, s);
149 }
150 globfree(&g);
151}
152
153static void
154addstaticpatrecipe(struct Target *t, const struct Recipe *src, const char *stem)
155{
156 char *exp;
157
158 exp = patexpandstem(src->body, stem);
159 if (!exp[0]) {
160 free(exp);
161 return;
162 }
163 t->recipes.v = xrealloc(t->recipes.v, (t->recipes.n + 1) * sizeof(t->recipes.v[0]));
164 t->recipes.v[t->recipes.n].body = exp;
165 t->recipes.v[t->recipes.n].silent = src->silent;
166 t->recipes.v[t->recipes.n].ignore = src->ignore;
167 t->recipes.v[t->recipes.n].recursive = src->recursive;
168 t->recipes.v[t->recipes.n].submake = src->submake;
169 copysubmake(&t->recipes.v[t->recipes.n].sm, &src->sm);
170 t->recipes.n++;
171}
172
173/* add an explicit target rule to the graph, and add all
174 * non-pattern prereqs also as placeholder nodes. later
175 * we discorver how to build them if they need to be built */
176static void
177addrule(struct GraphState *gs, const char *name, const struct RuleNode *rule)
178{
179 size_t i;
180 struct Target *t;
181 struct Env env;
182 struct EvalCtx ctx;
183 struct StrList prereqs;
184 struct StrList order_only;
185 char *stem;
186
187 memset(&ctx, 0, sizeof(ctx));
188 memset(&prereqs, 0, sizeof(prereqs));
189 memset(&order_only, 0, sizeof(order_only));
190 ctx.env = &env;
191 stem = 0;
192
193 if (rule->target_pattern) {
194 stem = patmatchstem(rule->target_pattern, name);
195 if (!stem)
196 return;
197 }
198
199 t = gettarget(gs->graph, name, 0);
200 if (!t->defined) {
201 t->dcolon = rule->dcolon;
202 } else if (t->defined && t->dcolon != rule->dcolon) {
203 fprintf(stderr, "target file `%s' has both : and :: entries, i can't handle that!\n", name);
204 exit(1);
205 }
206 t->defined = 1;
207 t->dcolon = rule->dcolon;
208 if (hasword(gs->phony, name))
209 t->phony = 1;
210 for (i = 0; i < rule->prereqs.n; i++) {
211 char *word;
212
213 word = stem ? patapplystem(rule->prereqs.v[i], stem) : xstrdup(rule->prereqs.v[i]);
214 addglobword(&prereqs, word);
215 free(word);
216 }
217 for (i = 0; i < rule->order_only.n; i++) {
218 char *word;
219
220 word = stem ? patapplystem(rule->order_only.v[i], stem) : xstrdup(rule->order_only.v[i]);
221 addglobword(&order_only, word);
222 free(word);
223 }
224 addwords(&t->prereqs, &prereqs);
225 addwords(&t->order_only, &order_only);
226 targetenv(gs, &ctx, t->env.n ? &t->env : 0, name);
227 if (stem) {
228 for (i = 0; i < rule->recipes.n; i++)
229 addstaticpatrecipe(t, &rule->recipes.v[i], stem);
230 } else {
231 addrecipes(&t->recipes, &rule->recipes);
232 }
233 freeenv(&t->env);
234 copyenv(&t->env, &env);
235
236 for (i = 0; i < prereqs.n; i++) {
237 struct Env penv;
238 struct EvalCtx pctx;
239
240 if (strchr(prereqs.v[i], '%'))
241 continue;
242 t = gettarget(gs->graph, prereqs.v[i], 0);
243 if (hasword(gs->phony, t->name))
244 t->phony = 1;
245 memset(&penv, 0, sizeof(penv));
246 memset(&pctx, 0, sizeof(pctx));
247 pctx.env = &penv;
248 targetenv(gs, &pctx, &env, t->name);
249 freeenv(&t->env);
250 copyenv(&t->env, pctx.env);
251 freeenv(&penv);
252 }
253 freestrs(&prereqs);
254 freestrs(&order_only);
255 freeenv(&env);
256 free(stem);
257}
258static void
259addtassign(struct GraphState *gs, const struct AssignNode *assign)
260{
261 struct TAssign *ta;
262
263 gs->tas = xrealloc(gs->tas, (gs->ntas + 1) * sizeof(gs->tas[0]));
264 ta = &gs->tas[gs->ntas++];
265 memset(ta, 0, sizeof(*ta));
266 addwords(&ta->targets, &assign->targets);
267 ta->lhs = xstrdup(assign->lhs);
268 ta->rhs = xstrdup(assign->rhs);
269 ta->op = assign->op;
270 ta->origin = assign->origin;
271}
272
273static void
274instdefaultrule(const struct GraphState *gs, struct Target *t, struct EvalCtx *ctx)
275{
276 if (!gs->defaultrule || gs->defaultrule->n == 0 || t->defined || t->phony || t->recipes.n > 0)
277 return;
278 addrecipes(&t->recipes, gs->defaultrule);
279 freeenv(&t->env);
280 copyenv(&t->env, ctx->env);
281}
282
283/*generate the graph from the evaluated rule set
284 * get the env and target specific assignments,
285 * then expand placeholder targets until all prereqs
286 * we can find are in the graph. */
287int
288buildgraph(const struct RuleSet *ruleset, const struct StrList *goals, struct Graph *graph, enum ShinMode mode)
289{
290 size_t i, j;
291 struct GraphState gs;
292 struct EvalCtx ctx;
293
294 memset(graph, 0, sizeof(*graph));
295 memset(&gs, 0, sizeof(gs));
296 memset(&ctx, 0, sizeof(ctx));
297 gs.graph = graph;
298 gs.phony = &ruleset->phony;
299 gs.defaultrule = &ruleset->defaultrule;
300 seedenv(&gs.env, ruleset->posix, ruleset->envoverride, mode);
301 gs.rules = ruleset->rules;
302 gs.nrules = ruleset->nrules;
303 gs.mode = mode;
304 ctx.env = &gs.env;
305 ctx.export_all = ruleset->export_all;
306 ctx.mode = mode;
307 imprules(&gs.sufs, mode);
308
309 for (i = 0; i < ruleset->nvars; i++)
310 evalassign(&ctx, &ruleset->vars[i]);
311
312 for (i = 0; i < ruleset->ntvars; i++)
313 addtassign(&gs, &ruleset->tvars[i]);
314
315 for (i = 0; i < gs.nrules; i++) {
316 if (!issufrule(&gs.rules[i]))
317 continue;
318 gs.saw_suffixes = 1;
319 if (gs.rules[i].prereqs.n == 0)
320 clearsufs(&gs.sufs.active);
321 else
322 addsufs(&gs.sufs.active, &gs.rules[i].prereqs);
323 }
324
325 if (!gs.saw_suffixes) {
326 for (i = 0; i < gs.nrules; i++)
327 seedsufs(&gs.sufs, &gs.rules[i]);
328 }
329
330 for (i = 0; i < gs.nrules; i++) {
331 size_t k;
332
333 if (issufrule(&gs.rules[i]))
334 continue;
335 if (collectsufrule(&gs.sufs, &gs.rules[i], 0))
336 continue;
337 /* pattern rules (%.o: %.c) are a gnu extension */
338 if (gs.mode == MODE_GNU)
339 collectpat(&gs.patterns, &gs.rules[i], 0);
340 for (k = 0; k < gs.rules[i].targets.n; k++) {
341 if (!ispat(gs.rules[i].targets.v[k]))
342 addrule(&gs, gs.rules[i].targets.v[k], &gs.rules[i]);
343 }
344 }
345 if (imppatrules(&gs.patterns, gs.mode) < 0) {
346 free(gs.tas);
347 freepatrule(&gs.patterns);
348 freesufrules(&gs.sufs);
349 freeenv(&gs.env);
350 return -1;
351 }
352
353 if (goals) {
354 /* explicitly requested goals need to exist in the generated graph before ninja runs.
355 * if a requested goal is missing but a .DEFAULT rule exists, create a
356 * placeholder target here so the default recipe will be attached later. */
357 for (i = 0; i < goals->n; i++) {
358 struct Target *t;
359
360 t = findtarget(graph, goals->v[i]);
361 if (t)
362 continue;
363 if (ruleset->defaultrule.n == 0) {
364 /* if there is no default rule but a target that doesn't exist
365 * is requested, die */
366 char *detail;
367
368 detail = cat3("'", goals->v[i], "'");
369 dielikemake(0, 0, "No rule to make target", detail);
370 free(detail);
371 freepatrule(&gs.patterns);
372 freesufrules(&gs.sufs);
373 freeenv(&gs.env);
374 free(gs.tas);
375 return -1;
376 }
377 t = gettarget(graph, goals->v[i], 0);
378 if (hasword(gs.phony, t->name))
379 t->phony = 1;
380 }
381 }
382
383 for (;;) {
384 int changed;
385
386 changed = 0;
387 for (i = 0; i < graph->n; i++) {
388 struct Target *t = &graph->v[i];
389 size_t nprereqs;
390 size_t old_graph_n, old_recipes_n, old_impprereqs_n;
391
392 old_graph_n = graph->n;
393 old_recipes_n = t->recipes.n;
394 old_impprereqs_n = t->impprereqs.n;
395 /* for targets with no recipe, try a pattern rule or
396 * suffix rule. existing prereqs dont block this,
397 * the rule may still supply the recipe */
398 if (t->recipes.n == 0) {
399 int matched;
400 struct Env env;
401 struct EvalCtx targetctx;
402
403 memset(&targetctx, 0, sizeof(targetctx));
404 targetctx.env = &env;
405 targetctx.mode = gs.mode;
406 targetenv(&gs, &targetctx, &t->env, t->name);
407 /* rule precedence in GNU mode:
408 * 1) user-defined pattern rules
409 * 2) user-defined suffix rules
410 * 3) built-in pattern rules
411 * 4) built-in suffix rules
412 *
413 * this makes sure we keep local suffix compile recipes ahead of GNU builtins,
414 * while allowing builtins such as %: %.o to beat the built-in .c
415 * link rule when we are interpreting a GNU makefile which matches what gmake does. */
416 if (gs.mode == MODE_GNU)
417 instpatrule(&gs.patterns, graph, t, &targetctx, 0);
418 matched = t->recipes.n > 0;
419 if (!matched) {
420 instsufrule(&gs.sufs, graph, t, &targetctx, 0);
421 if (gs.mode == MODE_GNU && t->recipes.n == 0) {
422 instpatrule(&gs.patterns, graph, t, &targetctx, 1);
423 }
424 if (t->recipes.n == 0)
425 instsufrule(&gs.sufs, graph, t, &targetctx, 1);
426 if (t->recipes.n == 0)
427 instdefaultrule(&gs, t, &targetctx);
428 }
429 freeenv(&env);
430 if (targetctx.errors)
431 ctx.errors += targetctx.errors;
432 }
433 if (graph->n != old_graph_n || t->recipes.n != old_recipes_n ||
434 t->impprereqs.n != old_impprereqs_n)
435 changed = 1;
436 nprereqs = totalprereqs(t);
437 for (j = 0; j < nprereqs; j++) {
438 const char *prereq;
439
440 if (j < t->impprereqs.n)
441 prereq = t->impprereqs.v[j];
442 else
443 prereq = t->prereqs.v[j - t->impprereqs.n];
444
445 if (!findtarget(graph, prereq)) {
446 struct Target *nt;
447
448 nt = gettarget(graph, prereq, 0);
449 if (hasword(gs.phony, nt->name))
450 nt->phony = 1;
451 changed = 1;
452 t = &graph->v[i];
453 }
454 }
455 }
456 if (!changed)
457 break;
458 }
459
460 for (i = 0; i < gs.ntas; i++) {
461 freestrs(&gs.tas[i].targets);
462 free(gs.tas[i].lhs);
463 free(gs.tas[i].rhs);
464 }
465 free(gs.tas);
466 freepatrule(&gs.patterns);
467 freesufrules(&gs.sufs);
468 freeenv(&gs.env);
469
470 return ctx.errors ? -1 : 0;
471}
472
473int
474expandgraph(struct Graph *graph, enum ShinMode mode)
475{
476 size_t i, k, j;
477
478 for (i = 0; i < graph->n; i++) {
479 struct Target *t = &graph->v[i];
480 struct EvalCtx ctx;
481 struct StrList side_effects;
482 struct RecipeList new_recipes;
483
484 if (!t->env.n) {
485 freeenv(&t->env);
486 continue;
487 }
488 memset(&ctx, 0, sizeof(ctx));
489 memset(&side_effects, 0, sizeof(side_effects));
490 memset(&new_recipes, 0, sizeof(new_recipes));
491 ctx.env = &t->env;
492 ctx.mode = mode;
493 ctx.auto_target = t->name;
494 {
495 struct StrList allprereqs;
496
497 memset(&allprereqs, 0, sizeof(allprereqs));
498 addwords(&allprereqs, &t->impprereqs);
499 addwords(&allprereqs, &t->prereqs);
500 ctx.auto_prereqs = &allprereqs;
501 ctx.avoid_io = 1;
502 ctx.side_effects = &side_effects;
503
504 for (k = 0; k < t->recipes.n; k++) {
505 struct Recipe *r = &t->recipes.v[k];
506 char *exp;
507
508 freestrs(&side_effects);
509 exp = expandstr(&ctx, r->body);
510 /* strip recipe prefixes that may have been
511 * introduced by variable expansion, eg something like Q_CC = @echo ... */
512 {
513 const char *s = exp;
514 while (*s == '@' || *s == '-' || *s == '+') {
515 if (*s == '@')
516 r->silent = 1;
517 else if (*s == '-')
518 r->ignore = 1;
519 else if (*s == '+')
520 r->recursive = 1;
521 s++;
522 while (*s == ' ' || *s == '\t')
523 s++;
524 }
525 if (s != exp) {
526 char *trimmed = xstrdup(s);
527 free(exp);
528 exp = trimmed;
529 }
530 }
531 for (j = 0; j < side_effects.n; j++) {
532 struct Recipe *nr;
533
534 new_recipes.v = xrealloc(new_recipes.v,
535 (new_recipes.n + 1) * sizeof(new_recipes.v[0]));
536 nr = &new_recipes.v[new_recipes.n++];
537 memset(nr, 0, sizeof(*nr));
538 nr->body = xstrdup(side_effects.v[j]);
539 nr->silent = r->silent;
540 nr->ignore = r->ignore;
541 }
542 if (exp[0]) {
543 struct Recipe *nr;
544
545 new_recipes.v = xrealloc(new_recipes.v,
546 (new_recipes.n + 1) * sizeof(new_recipes.v[0]));
547 nr = &new_recipes.v[new_recipes.n++];
548 *nr = *r;
549 nr->body = exp;
550 freesubmake(&nr->sm);
551 nr->submake = parsesubmake(&nr->sm, nr->body);
552 free(r->body);
553 r->body = 0;
554 memset(&r->sm, 0, sizeof(r->sm));
555 } else {
556 free(exp);
557 }
558 }
559 freestrs(&allprereqs);
560 }
561
562 freestrs(&side_effects);
563 freerecipes(&t->recipes);
564 t->recipes = new_recipes;
565 }
566
567 for (i = 0; i < graph->nsubs; i++) {
568 if (expandgraph(&graph->subs[i].graph, mode) < 0)
569 return -1;
570 }
571 return 0;
572}
573
574void
575freegraph(struct Graph *graph)
576{
577 size_t i;
578
579 if (!graph)
580 return;
581 for (i = 0; i < graph->n; i++) {
582 free(graph->v[i].owner);
583 freestrs(&graph->v[i].prereqs);
584 freestrs(&graph->v[i].impprereqs);
585 freestrs(&graph->v[i].order_only);
586 freerecipes(&graph->v[i].recipes);
587 freeenv(&graph->v[i].env);
588 }
589 for (i = 0; i < graph->nsubs; i++)
590 freesubgraph(&graph->subs[i]);
591 free(graph->v);
592 free(graph->targetindex);
593 free(graph->subs);
594 graph->v = 0;
595 graph->n = 0;
596 graph->targetindex = 0;
597 graph->ntargetindex = 0;
598 graph->cap_targetindex = 0;
599 graph->subs = 0;
600 graph->nsubs = 0;
601}
