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 = findtarget(gs->graph, name);
200 if (!t) {
201 gs->graph->v = xrealloc(gs->graph->v, (gs->graph->n + 1) * sizeof(gs->graph->v[0]));
202 t = &gs->graph->v[gs->graph->n++];
203 memset(t, 0, sizeof(*t));
204 t->name = intern(name);
205 t->dcolon = rule->dcolon;
206 } else if (t->defined && t->dcolon != rule->dcolon) {
207 fprintf(stderr, "target file `%s' has both : and :: entries, i can't handle that!\n", name);
208 exit(1);
209 }
210 t->defined = 1;
211 t->dcolon = rule->dcolon;
212 if (hasword(gs->phony, name))
213 t->phony = 1;
214 for (i = 0; i < rule->prereqs.n; i++) {
215 char *word;
216
217 word = stem ? patapplystem(rule->prereqs.v[i], stem) : xstrdup(rule->prereqs.v[i]);
218 addglobword(&prereqs, word);
219 free(word);
220 }
221 for (i = 0; i < rule->order_only.n; i++) {
222 char *word;
223
224 word = stem ? patapplystem(rule->order_only.v[i], stem) : xstrdup(rule->order_only.v[i]);
225 addglobword(&order_only, word);
226 free(word);
227 }
228 addwords(&t->prereqs, &prereqs);
229 addwords(&t->order_only, &order_only);
230 targetenv(gs, &ctx, t->env.n ? &t->env : 0, name);
231 if (stem) {
232 for (i = 0; i < rule->recipes.n; i++)
233 addstaticpatrecipe(t, &rule->recipes.v[i], stem);
234 } else {
235 addrecipes(&t->recipes, &rule->recipes);
236 }
237 freeenv(&t->env);
238 copyenv(&t->env, &env);
239
240 for (i = 0; i < prereqs.n; i++) {
241 struct Env penv;
242 struct EvalCtx pctx;
243
244 if (strchr(prereqs.v[i], '%'))
245 continue;
246 t = findtarget(gs->graph, prereqs.v[i]);
247 if (!t) {
248 gs->graph->v = xrealloc(gs->graph->v, (gs->graph->n + 1) * sizeof(gs->graph->v[0]));
249 t = &gs->graph->v[gs->graph->n++];
250 memset(t, 0, sizeof(*t));
251 t->name = intern(prereqs.v[i]);
252 }
253 if (hasword(gs->phony, t->name))
254 t->phony = 1;
255 memset(&penv, 0, sizeof(penv));
256 memset(&pctx, 0, sizeof(pctx));
257 pctx.env = &penv;
258 targetenv(gs, &pctx, &env, t->name);
259 freeenv(&t->env);
260 copyenv(&t->env, pctx.env);
261 freeenv(&penv);
262 }
263 freestrs(&prereqs);
264 freestrs(&order_only);
265 freeenv(&env);
266 free(stem);
267}
268static void
269addtassign(struct GraphState *gs, const struct AssignNode *assign)
270{
271 struct TAssign *ta;
272
273 gs->tas = xrealloc(gs->tas, (gs->ntas + 1) * sizeof(gs->tas[0]));
274 ta = &gs->tas[gs->ntas++];
275 memset(ta, 0, sizeof(*ta));
276 addwords(&ta->targets, &assign->targets);
277 ta->lhs = xstrdup(assign->lhs);
278 ta->rhs = xstrdup(assign->rhs);
279 ta->op = assign->op;
280 ta->origin = assign->origin;
281}
282
283static void
284instdefaultrule(const struct GraphState *gs, struct Target *t, struct EvalCtx *ctx)
285{
286 if (!gs->defaultrule || gs->defaultrule->n == 0 || t->defined || t->phony || t->recipes.n > 0)
287 return;
288 addrecipes(&t->recipes, gs->defaultrule);
289 freeenv(&t->env);
290 copyenv(&t->env, ctx->env);
291}
292
293/*generate the graph from the evaluated rule set
294 * get the env and target specific assignments,
295 * then expand placeholder targets until all prereqs
296 * we can find are in the graph. */
297int
298buildgraph(const struct RuleSet *ruleset, const struct StrList *goals, struct Graph *graph, enum ShinMode mode)
299{
300 size_t i, j;
301 struct GraphState gs;
302 struct EvalCtx ctx;
303
304 memset(graph, 0, sizeof(*graph));
305 memset(&gs, 0, sizeof(gs));
306 memset(&ctx, 0, sizeof(ctx));
307 gs.graph = graph;
308 gs.phony = &ruleset->phony;
309 gs.defaultrule = &ruleset->defaultrule;
310 seedenv(&gs.env, ruleset->posix, ruleset->envoverride, mode);
311 gs.rules = ruleset->rules;
312 gs.nrules = ruleset->nrules;
313 gs.mode = mode;
314 ctx.env = &gs.env;
315 ctx.export_all = ruleset->export_all;
316 ctx.mode = mode;
317 imprules(&gs.sufs, ruleset->posix, mode);
318
319 for (i = 0; i < ruleset->nvars; i++)
320 evalassign(&ctx, &ruleset->vars[i]);
321
322 for (i = 0; i < ruleset->ntvars; i++)
323 addtassign(&gs, &ruleset->tvars[i]);
324
325 for (i = 0; i < gs.nrules; i++) {
326 if (!issufrule(&gs.rules[i]))
327 continue;
328 gs.saw_suffixes = 1;
329 if (gs.rules[i].prereqs.n == 0)
330 clearsufs(&gs.sufs.active);
331 else
332 addsufs(&gs.sufs.active, &gs.rules[i].prereqs);
333 }
334
335 if (!gs.saw_suffixes) {
336 for (i = 0; i < gs.nrules; i++)
337 seedsufs(&gs.sufs, &gs.rules[i]);
338 }
339
340 for (i = 0; i < gs.nrules; i++) {
341 size_t k;
342
343 if (issufrule(&gs.rules[i]))
344 continue;
345 if (collectsufrule(&gs.sufs, &gs.rules[i]))
346 continue;
347 /* pattern rules (%.o: %.c) are a gnu extension */
348 if (gs.mode == MODE_GNU)
349 collectpat(&gs.patterns, &gs.rules[i], 0);
350 for (k = 0; k < gs.rules[i].targets.n; k++) {
351 if (!ispat(gs.rules[i].targets.v[k]))
352 addrule(&gs, gs.rules[i].targets.v[k], &gs.rules[i]);
353 }
354 }
355 if (imppatrules(&gs.patterns, gs.mode) < 0) {
356 free(gs.tas);
357 freepatrule(&gs.patterns);
358 freesufrules(&gs.sufs);
359 freeenv(&gs.env);
360 return -1;
361 }
362
363 if (goals) {
364 /* explicitly requested goals need to exist in the generated graph before ninja runs.
365 * if a requested goal is missing but a .DEFAULT rule exists, create a
366 * placeholder target here so the default recipe will be attached later. */
367 for (i = 0; i < goals->n; i++) {
368 struct Target *t;
369
370 t = findtarget(graph, goals->v[i]);
371 if (t)
372 continue;
373 if (ruleset->defaultrule.n == 0) {
374 /* if there is no default rule but a target that doesn't exist
375 * is requested, die */
376 char *detail;
377
378 detail = cat3("'", goals->v[i], "'");
379 dielikemake(0, 0, "No rule to make target", detail);
380 free(detail);
381 freepatrule(&gs.patterns);
382 freesufrules(&gs.sufs);
383 freeenv(&gs.env);
384 free(gs.tas);
385 return -1;
386 }
387 graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
388 t = &graph->v[graph->n++];
389 memset(t, 0, sizeof(*t));
390 t->name = intern(goals->v[i]);
391 if (hasword(gs.phony, t->name))
392 t->phony = 1;
393 }
394 }
395
396 for (;;) {
397 int changed;
398
399 changed = 0;
400 for (i = 0; i < graph->n; i++) {
401 struct Target *t = &graph->v[i];
402 size_t nprereqs;
403 size_t old_graph_n, old_recipes_n, old_impprereqs_n;
404
405 old_graph_n = graph->n;
406 old_recipes_n = t->recipes.n;
407 old_impprereqs_n = t->impprereqs.n;
408 /* for targets with no recipe, try a pattern rule or
409 * suffix rule. existing prereqs dont block this,
410 * the rule may still supply the recipe */
411 if (t->recipes.n == 0) {
412 int matched;
413 struct Env env;
414 struct EvalCtx targetctx;
415
416 memset(&targetctx, 0, sizeof(targetctx));
417 targetctx.env = &env;
418 targetctx.mode = gs.mode;
419 targetenv(&gs, &targetctx, &t->env, t->name);
420 /* rule precedence in GNU mode:
421 * 1) user defined pattern rules
422 * 2) suffix rules
423 * 3) builtin pattern rules
424 *
425 * we make sure local suffix compile recipes dont get overshadowed
426 * by GNU builtins like %.o: %.c (dropbear fails without this). */
427 if (gs.mode == MODE_GNU)
428 instpatrule(&gs.patterns, graph, t, &targetctx, 0);
429 matched = t->recipes.n > 0;
430 if (!matched) {
431 instsufrule(&gs.sufs, graph, t, &targetctx);
432 if (gs.mode == MODE_GNU && t->recipes.n == 0)
433 instpatrule(&gs.patterns, graph, t, &targetctx, 1);
434 if (t->recipes.n == 0)
435 instdefaultrule(&gs, t, &targetctx);
436 }
437 freeenv(&env);
438 if (targetctx.errors)
439 ctx.errors += targetctx.errors;
440 }
441 if (graph->n != old_graph_n || t->recipes.n != old_recipes_n ||
442 t->impprereqs.n != old_impprereqs_n)
443 changed = 1;
444 nprereqs = totalprereqs(t);
445 for (j = 0; j < nprereqs; j++) {
446 const char *prereq;
447
448 if (j < t->impprereqs.n)
449 prereq = t->impprereqs.v[j];
450 else
451 prereq = t->prereqs.v[j - t->impprereqs.n];
452
453 if (!findtarget(graph, prereq)) {
454 struct Target *nt;
455
456 graph->v = xrealloc(graph->v, (graph->n + 1) * sizeof(graph->v[0]));
457 nt = &graph->v[graph->n++];
458 memset(nt, 0, sizeof(*nt));
459 nt->name = intern(prereq);
460 if (hasword(gs.phony, nt->name))
461 nt->phony = 1;
462 changed = 1;
463 t = &graph->v[i];
464 }
465 }
466 }
467 if (!changed)
468 break;
469 }
470
471 for (i = 0; i < gs.ntas; i++) {
472 freestrs(&gs.tas[i].targets);
473 free(gs.tas[i].lhs);
474 free(gs.tas[i].rhs);
475 }
476 free(gs.tas);
477 freepatrule(&gs.patterns);
478 freesufrules(&gs.sufs);
479 freeenv(&gs.env);
480
481 return ctx.errors ? -1 : 0;
482}
483
484int
485expandgraph(struct Graph *graph, enum ShinMode mode)
486{
487 size_t i, k, j;
488
489 for (i = 0; i < graph->n; i++) {
490 struct Target *t = &graph->v[i];
491 struct EvalCtx ctx;
492 struct StrList side_effects;
493 struct RecipeList new_recipes;
494
495 if (!t->env.n) {
496 freeenv(&t->env);
497 continue;
498 }
499 memset(&ctx, 0, sizeof(ctx));
500 memset(&side_effects, 0, sizeof(side_effects));
501 memset(&new_recipes, 0, sizeof(new_recipes));
502 ctx.env = &t->env;
503 ctx.mode = mode;
504 ctx.auto_target = t->name;
505 {
506 struct StrList allprereqs;
507
508 memset(&allprereqs, 0, sizeof(allprereqs));
509 addwords(&allprereqs, &t->impprereqs);
510 addwords(&allprereqs, &t->prereqs);
511 ctx.auto_prereqs = &allprereqs;
512 ctx.avoid_io = 1;
513 ctx.side_effects = &side_effects;
514
515 for (k = 0; k < t->recipes.n; k++) {
516 struct Recipe *r = &t->recipes.v[k];
517 char *exp;
518
519 freestrs(&side_effects);
520 exp = expandstr(&ctx, r->body);
521 /* strip recipe prefixes that may have been
522 * introduced by variable expansion, eg something like Q_CC = @echo ... */
523 {
524 const char *s = exp;
525 while (*s == '@' || *s == '-' || *s == '+') {
526 if (*s == '@')
527 r->silent = 1;
528 else if (*s == '-')
529 r->ignore = 1;
530 else if (*s == '+')
531 r->recursive = 1;
532 s++;
533 while (*s == ' ' || *s == '\t')
534 s++;
535 }
536 if (s != exp) {
537 char *trimmed = xstrdup(s);
538 free(exp);
539 exp = trimmed;
540 }
541 }
542 for (j = 0; j < side_effects.n; j++) {
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 memset(nr, 0, sizeof(*nr));
549 nr->body = xstrdup(side_effects.v[j]);
550 nr->silent = r->silent;
551 nr->ignore = r->ignore;
552 }
553 if (exp[0]) {
554 struct Recipe *nr;
555
556 new_recipes.v = xrealloc(new_recipes.v,
557 (new_recipes.n + 1) * sizeof(new_recipes.v[0]));
558 nr = &new_recipes.v[new_recipes.n++];
559 *nr = *r;
560 nr->body = exp;
561 freesubmake(&nr->sm);
562 nr->submake = parsesubmake(&nr->sm, nr->body);
563 free(r->body);
564 r->body = 0;
565 memset(&r->sm, 0, sizeof(r->sm));
566 } else {
567 free(exp);
568 }
569 }
570 freestrs(&allprereqs);
571 }
572
573 freestrs(&side_effects);
574 freerecipes(&t->recipes);
575 t->recipes = new_recipes;
576 }
577
578 for (i = 0; i < graph->nsubs; i++) {
579 if (expandgraph(&graph->subs[i].graph, mode) < 0)
580 return -1;
581 }
582 return 0;
583}
584
585void
586freegraph(struct Graph *graph)
587{
588 size_t i;
589
590 if (!graph)
591 return;
592 for (i = 0; i < graph->n; i++) {
593 free(graph->v[i].owner);
594 freestrs(&graph->v[i].prereqs);
595 freestrs(&graph->v[i].impprereqs);
596 freestrs(&graph->v[i].order_only);
597 freerecipes(&graph->v[i].recipes);
598 freeenv(&graph->v[i].env);
599 }
600 for (i = 0; i < graph->nsubs; i++)
601 freesubgraph(&graph->subs[i]);
602 free(graph->v);
603 free(graph->subs);
604 graph->v = 0;
605 graph->n = 0;
606 graph->subs = 0;
607 graph->nsubs = 0;
608}
