6 #include "tm_core_cmds.h"
8 /* The goal target of the current execution */
11 /* All the rules defined by the TMakefile */
12 tm_rule_list
*tm_rules
= NULL
;
15 /* Create a new explicit rule.
16 * Makes copies of all the arguments to store in the rule.
18 tm_rule
*new_rule(const char *target
, target_list
*deps
, const char *recipe
)
20 tm_rule
*rule
= malloc(sizeof(tm_rule
));
21 rule
->target
= malloc(strlen(target
) + 1);
23 rule
->recipe
= malloc(strlen(recipe
) + 1);
25 strcpy(rule
->target
, target
);
26 rule
->deps
= target_list_copy(deps
);
28 strcpy(rule
->recipe
, recipe
);
31 rule
->type
= TM_EXPLICIT
;
32 rule
->mark
= TM_UNMARKED
;
37 /* Create a new filename rule.
38 * Makes a copy of its argument.
40 tm_rule
*new_filename(const char *target
)
42 tm_rule
*rule
= new_rule(target
, NULL
, NULL
);
44 rule
->type
= TM_FILENAME
;
49 /* Make a copy of a rule.
51 tm_rule
*rule_copy(tm_rule
*rule
)
59 copy
= malloc(sizeof(tm_rule
));
62 copy
->target
= malloc(strlen(rule
->target
) + 1);
63 strcpy(copy
->target
, rule
->target
);
68 copy
->deps
= target_list_copy(rule
->deps
);
73 copy
->recipe
= malloc(strlen(rule
->recipe
) + 1);
74 strcpy(copy
->recipe
, rule
->recipe
);
78 copy
->type
= rule
->type
;
79 copy
->mark
= rule
->mark
;
85 void free_rule(tm_rule
*rule
)
89 free_target_list(rule
->deps
);
96 /* Takes the name of a target and another target list and
97 * returns a target list with the target at the head.
98 * Target lists are NULL-terminated.
100 * e.g., to make a one-element list:
101 * target_cons("foo", NULL);
103 target_list
*target_cons(const char *name
, target_list
*next
)
105 target_list
*targets
= malloc(sizeof(target_list
));
107 targets
->name
= malloc(strlen(name
) + 1);
109 strcpy(targets
->name
, name
);
110 targets
->next
= next
;
115 /* Frees a target list.
117 void free_target_list(target_list
*targets
)
120 target_list
*node
= targets
->next
;
127 /* Copy a target list.
129 target_list
*target_list_copy(target_list
*targets
)
134 if (!targets
) return NULL
;
136 rev
= target_list_reverse(targets
);
137 copy
= target_list_reverse(rev
);
138 free_target_list(rev
);
143 /* Take a rule and another rule list and return
144 * a rule list with the rule at the head.
145 * Rule lists are NULL-terminated.
147 tm_rule_list
*rule_cons(tm_rule
*rule
, tm_rule_list
*next
)
149 tm_rule_list
*rules
= malloc(sizeof(tm_rule_list
));
151 rules
->rule
= rule_copy(rule
);
159 void free_rule_list(tm_rule_list
*rules
)
162 tm_rule_list
*node
= rules
->next
;
164 free_rule(rules
->rule
);
171 /* Return 1 if the target is in targets, else return 0.
173 int target_exists(const char *target
, target_list
*targets
)
175 for (; targets
; targets
= targets
->next
) {
176 if (strcmp(targets
->name
, target
) == 0) {
185 /* Take a target and a rule list and return the rule associated
186 * with that target if it exists, otherwise return NULL.
188 tm_rule
*find_rule(const char *target
, tm_rule_list
*rules
)
190 tm_rule_list
*node
= rules
;
191 tm_rule
*rule
= NULL
;
194 if (strcmp(node
->rule
->target
, target
) == 0) {
206 /* Take a list of targets and a pointer to a rule list.
207 * If no rule for a target is found in the rule list, add
208 * a new TM_FILENAME rule to the rule list.
210 static void find_files_from_deps(target_list
*targets
, tm_rule_list
**rules
)
212 for (; targets
; targets
= targets
->next
) {
213 tm_rule
*rule
= find_rule(targets
->name
, *rules
);
216 rule
= new_filename(targets
->name
);
217 *rules
= rule_cons(rule
, *rules
);
223 /* Scour through all the dependencies in a rule list and allocate new
224 * filename rules for things deemed to be files.
225 * Updates the rule list with the new rules.
227 void find_files(tm_rule_list
**rules
)
231 for (node
= *rules
; node
; node
= node
->next
) {
232 find_files_from_deps(node
->rule
->deps
, rules
);
237 /* Take a list of targets and a list of rules and return
238 * a list of the rules associated with those targets.
240 tm_rule_list
*find_rules(target_list
*targets
, tm_rule_list
*rules
)
242 tm_rule_list
*mapped
= NULL
;
243 target_list
*node
= targets
;
246 tm_rule
*rule
= find_rule(node
->name
, rules
);
248 mapped
= rule_cons(rule
, mapped
);
256 /* Return a new rule list representing the reverse of another rule list
258 tm_rule_list
*rule_list_reverse(tm_rule_list
*rules
)
260 tm_rule_list
*rev
= NULL
;
261 tm_rule_list
*node
= rules
;
263 for (; node
; node
= node
->next
) {
264 rev
= rule_cons(node
->rule
, rev
);
270 /* Return a new target list representing the reverse of another target list
272 target_list
*target_list_reverse(target_list
*targets
)
274 target_list
*rev
= NULL
;
275 target_list
*node
= targets
;
277 for (; node
; node
= node
->next
) {
278 rev
= target_cons(node
->name
, rev
);
285 /* Tarjan's algorithm for topological sorting */
286 static int topsort_visit(tm_rule
*rule
, tm_rule_list
*rules
, tm_rule_list
**sorted
)
288 if (rule
->mark
== TM_TEMPORARY
) {
289 fprintf(stderr
, "ERROR: Cycle detected in dependency graph\n");
293 if (rule
->mark
== TM_UNMARKED
) {
294 tm_rule_list
*deps
= NULL
;
295 tm_rule_list
*node
= NULL
;
297 rule
->mark
= TM_TEMPORARY
;
298 deps
= find_rules(rule
->deps
, rules
);
300 for (node
= deps
; node
; node
= node
->next
) {
304 n
= topsort_visit(node
->rule
, rules
, sorted
);
307 free_rule_list(deps
);
311 free_rule_list(deps
);
313 rule
->mark
= TM_PERMANENT
;
314 *sorted
= rule_cons(rule
, *sorted
);
320 /* Perform a topological sort of the dependency graph to reach target.
321 * Also checks for cycles in the dependency graph.
323 tm_rule_list
*topsort(const char *target
, tm_rule_list
*rules
)
325 tm_rule_list
*sorted
= NULL
;
326 tm_rule_list
*rev
= NULL
;
327 tm_rule
*rule
= find_rule(target
, rules
);
332 if (topsort_visit(rule
, rules
, &sorted
) < 0) {
336 rev
= rule_list_reverse(sorted
);
337 free_rule_list(sorted
);
342 /* Return a string representation of a target list.
343 * Consists of all the targets in the list separated by spaces.
345 char *target_list_to_string(target_list
*targets
)
347 target_list
*node
= targets
;
348 int len
= 1; /* for NUL terminator */
358 for (node
= targets
; node
; node
= node
->next
) {
359 len
+= strlen(node
->name
) + 1;
364 for (node
= targets
; node
; node
= node
->next
) {
365 p
+= sprintf(p
, "%s ", node
->name
);
367 *(p
-1) = '\0'; /* get rid of the trailing space */
373 /* Print a rule list to stdout.
375 void print_rule_list(tm_rule_list
*rules
)
380 for (node
= rules
; node
; node
= node
->next
) {
383 printf("\t%s: ", node
->rule
->target
);
384 for (deps
= node
->rule
->deps
; deps
; deps
= deps
->next
) {
385 printf("%s ", deps
->name
);
387 switch (node
->rule
->type
) {
389 printf("(explicit)");
392 printf("(implicit)");
395 printf("(filename)");
401 if (node
->rule
->recipe
) {