Annotation of src/usr.bin/make/make.c, Revision 1.78
1.78 ! espie 1: /* $OpenBSD: make.c,v 1.77 2020/01/08 14:09:29 espie Exp $ */
1.6 millert 2: /* $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $ */
1.1 deraadt 3:
4: /*
1.4 millert 5: * Copyright (c) 1988, 1989, 1990, 1993
6: * The Regents of the University of California. All rights reserved.
1.1 deraadt 7: * Copyright (c) 1989 by Berkeley Softworks
8: * All rights reserved.
9: *
10: * This code is derived from software contributed to Berkeley by
11: * Adam de Boor.
12: *
13: * Redistribution and use in source and binary forms, with or without
14: * modification, are permitted provided that the following conditions
15: * are met:
16: * 1. Redistributions of source code must retain the above copyright
17: * notice, this list of conditions and the following disclaimer.
18: * 2. Redistributions in binary form must reproduce the above copyright
19: * notice, this list of conditions and the following disclaimer in the
20: * documentation and/or other materials provided with the distribution.
1.33 millert 21: * 3. Neither the name of the University nor the names of its contributors
1.1 deraadt 22: * may be used to endorse or promote products derived from this software
23: * without specific prior written permission.
24: *
25: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
26: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
27: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
28: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
29: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
30: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
31: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
32: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
33: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
34: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
35: * SUCH DAMAGE.
36: */
37:
38: /*-
39: * make.c --
40: * The functions which perform the examination of targets and
41: * their suitability for creation
42: *
43: * Interface:
1.25 espie 44: * Make_Run Initialize things for the module and recreate
1.26 espie 45: * whatever needs recreating. Returns true if
46: * work was (or would have been) done and
47: * false
1.25 espie 48: * otherwise.
49: *
50: * Make_Update Update all parents of a given child. Performs
1.67 espie 51: * various bookkeeping chores like finding the
52: * youngest child of the parent, filling
1.76 espie 53: * the IMPSRC local variable, etc. It will
1.75 espie 54: * place the parent on the to_build queue if it
1.25 espie 55: * should be.
56: *
1.1 deraadt 57: */
58:
1.27 espie 59: #include <limits.h>
1.43 espie 60: #include <signal.h>
1.52 espie 61: #include <stddef.h>
1.66 espie 62: #include <stdint.h>
63: #include <stdio.h>
1.54 espie 64: #include <stdlib.h>
1.52 espie 65: #include <string.h>
66: #include <ohash.h>
1.26 espie 67: #include "config.h"
68: #include "defines.h"
69: #include "dir.h"
70: #include "job.h"
71: #include "suff.h"
72: #include "var.h"
73: #include "error.h"
1.78 ! espie 74: #include "expandchildren.h"
1.26 espie 75: #include "make.h"
76: #include "gnode.h"
77: #include "extern.h"
78: #include "timestamp.h"
1.37 espie 79: #include "engine.h"
1.26 espie 80: #include "lst.h"
1.43 espie 81: #include "targ.h"
1.58 espie 82: #include "targequiv.h"
1.56 espie 83: #include "garray.h"
84: #include "memory.h"
85:
86: /* what gets added each time. Kept as one static array so that it doesn't
87: * get resized every time.
88: */
89: static struct growableArray examine;
90: /* The current fringe of the graph. These are nodes which await examination by
91: * MakeOODate. It is added to by Make_Update and subtracted from by
92: * MakeStartJobs */
1.75 espie 93: static struct growableArray to_build;
1.25 espie 94:
1.64 espie 95: /* Hold back on nodes where equivalent stuff is already building... */
96: static struct growableArray heldBack;
97:
1.52 espie 98: static struct ohash targets; /* stuff we must build */
1.1 deraadt 99:
1.25 espie 100: static void MakeAddChild(void *, void *);
101: static void MakeHandleUse(void *, void *);
1.26 espie 102: static bool MakeStartJobs(void);
1.72 espie 103: static void MakePrintStatus(void *);
104:
105: /* Cycle detection functions */
106: static bool targets_contain_cycles(void);
107: static void print_unlink_cycle(struct growableArray *, GNode *);
108: static void break_and_print_cycles(Lst);
109: static GNode *find_cycle(Lst, struct growableArray *);
110:
1.46 espie 111: static bool try_to_make_node(GNode *);
112: static void add_targets_to_make(Lst);
1.40 espie 113:
1.75 espie 114: static bool has_predecessor_left_to_build(GNode *);
1.52 espie 115: static void requeue_successors(GNode *);
1.54 espie 116: static void random_setup(void);
117:
118: static bool randomize_queue;
119: long random_delay = 0;
120:
1.73 espie 121: bool
1.56 espie 122: no_jobs_left()
123: {
1.75 espie 124: return Array_IsEmpty(&to_build);
1.56 espie 125: }
126:
1.54 espie 127: static void
128: random_setup()
129: {
130: randomize_queue = Var_Definedi("RANDOM_ORDER", NULL);
131:
1.67 espie 132: /* no random delay in the new engine for now */
133: #if 0
1.54 espie 134: if (Var_Definedi("RANDOM_DELAY", NULL))
1.73 espie 135: random_delay = strtonum(Var_Value("RANDOM_DELAY"), 0, 1000,
1.54 espie 136: NULL) * 1000000;
1.67 espie 137: #endif
1.54 espie 138:
139: }
1.52 espie 140:
1.56 espie 141: static void
142: randomize_garray(struct growableArray *g)
143: {
144: /* This is a fairly standard algorithm to randomize an array. */
145: unsigned int i, v;
146: GNode *e;
147:
148: for (i = g->n; i > 0; i--) {
1.67 espie 149: v = arc4random_uniform(i);
1.56 espie 150: if (v == i-1)
151: continue;
152: else {
153: e = g->a[i-1];
154: g->a[i-1] = g->a[v];
155: g->a[v] = e;
156: }
157: }
158: }
159:
1.52 espie 160: static bool
1.75 espie 161: has_predecessor_left_to_build(GNode *gn)
1.1 deraadt 162: {
1.52 espie 163: LstNode ln;
164:
1.75 espie 165: if (Lst_IsEmpty(&gn->predecessors))
1.52 espie 166: return false;
1.5 millert 167:
1.52 espie 168:
1.75 espie 169: for (ln = Lst_First(&gn->predecessors); ln != NULL; ln = Lst_Adv(ln)) {
1.71 espie 170: GNode *pgn = Lst_Datum(ln);
1.52 espie 171:
172: if (pgn->must_make && pgn->built_status == UNKNOWN) {
173: if (DEBUG(MAKE))
1.73 espie 174: printf("predecessor %s not made yet.\n",
1.52 espie 175: pgn->name);
176: return true;
177: }
178: }
179: return false;
1.1 deraadt 180: }
1.25 espie 181:
1.15 espie 182: static void
1.52 espie 183: requeue_successors(GNode *gn)
1.1 deraadt 184: {
1.52 espie 185: LstNode ln;
186: /* Deal with successor nodes. If any is marked for making and has an
1.75 espie 187: * children_left count of 0, has not been made and isn't in the
188: * examination queue, it means we need to place it in the queue as
189: * it restrained itself before. */
1.52 espie 190: for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) {
1.71 espie 191: GNode *succ = Lst_Datum(ln);
1.52 espie 192:
1.75 espie 193: if (succ->must_make && succ->children_left == 0
1.52 espie 194: && succ->built_status == UNKNOWN)
1.75 espie 195: Array_PushNew(&to_build, succ);
1.52 espie 196: }
1.1 deraadt 197: }
1.25 espie 198:
1.64 espie 199: static void
200: requeue(GNode *gn)
201: {
202: /* this is where we go inside the array and move things around */
203: unsigned int i, j;
204:
205: for (i = 0, j = 0; i < heldBack.n; i++, j++) {
206: if (heldBack.a[i]->watched == gn) {
207: j--;
208: heldBack.a[i]->built_status = UNKNOWN;
209: if (DEBUG(HELDJOBS))
1.73 espie 210: printf("%s finished, releasing: %s\n",
1.64 espie 211: gn->name, heldBack.a[i]->name);
1.75 espie 212: Array_Push(&to_build, heldBack.a[i]);
1.64 espie 213: continue;
214: }
215: heldBack.a[j] = heldBack.a[i];
216: }
217: heldBack.n = j;
218: }
219:
1.1 deraadt 220: /*-
221: *-----------------------------------------------------------------------
1.25 espie 222: * Make_Update --
1.1 deraadt 223: * Perform update on the parents of a node. Used by JobFinish once
224: * a node has been dealt with and by MakeStartJobs if it finds an
1.4 millert 225: * up-to-date node.
1.1 deraadt 226: *
227: * Results:
228: * Always returns 0
229: *
230: * Side Effects:
1.75 espie 231: * The children_left field of pgn is decremented and pgn may be placed on
232: * the to_build queue if this field becomes 0.
1.1 deraadt 233: *
1.75 espie 234: * If the child got built, the parent's child_rebuilt field will be set to
1.67 espie 235: * true
1.1 deraadt 236: *-----------------------------------------------------------------------
237: */
238: void
1.35 espie 239: Make_Update(GNode *cgn) /* the child node */
1.1 deraadt 240: {
1.40 espie 241: GNode *pgn; /* the parent node */
1.47 espie 242: LstNode ln; /* Element in parents list */
1.40 espie 243:
1.1 deraadt 244: /*
1.40 espie 245: * If the child was actually made, see what its modification time is
246: * now -- some rules won't actually update the file. If the file still
247: * doesn't exist, make its mtime now.
1.1 deraadt 248: */
1.48 espie 249: if (cgn->built_status != UPTODATE) {
1.40 espie 250: /*
251: * This is what Make does and it's actually a good thing, as it
252: * allows rules like
253: *
254: * cmp -s y.tab.h parse.h || cp y.tab.h parse.h
255: *
1.41 espie 256: * to function as intended. Unfortunately, thanks to the
257: * stateless nature of NFS, there are times when the
258: * modification time of a file created on a remote machine
1.40 espie 259: * will not be modified before the local stat() implied by
1.41 espie 260: * the Dir_MTime occurs, thus leading us to believe that the
261: * file is unchanged, wreaking havoc with files that depend
1.40 espie 262: * on this one.
263: */
1.43 espie 264: if (noExecute || is_out_of_date(Dir_MTime(cgn)))
1.67 espie 265: clock_gettime(CLOCK_REALTIME, &cgn->mtime);
1.40 espie 266: if (DEBUG(MAKE))
1.73 espie 267: printf("update time: %s\n",
1.67 espie 268: time_to_string(&cgn->mtime));
1.40 espie 269: }
270:
1.64 espie 271: requeue(cgn);
1.58 espie 272: /* SIB: this is where I should mark the build as finished */
1.40 espie 273: for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
1.71 espie 274: pgn = Lst_Datum(ln);
1.58 espie 275: /* SIB: there should be a siblings loop there */
1.75 espie 276: pgn->children_left--;
1.48 espie 277: if (pgn->must_make) {
1.52 espie 278: if (DEBUG(MAKE))
1.73 espie 279: printf("%s--=%d ",
1.75 espie 280: pgn->name, pgn->children_left);
1.40 espie 281:
282: if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
1.74 espie 283: if (cgn->built_status == REBUILT)
1.75 espie 284: pgn->child_rebuilt = true;
1.63 guenther 285: (void)Make_TimeStamp(pgn, cgn);
1.40 espie 286: }
1.75 espie 287: if (pgn->children_left == 0) {
1.40 espie 288: /*
1.75 espie 289: * Queue the node up -- any yet-to-build
1.41 espie 290: * predecessors will be dealt with in
1.40 espie 291: * MakeStartJobs.
292: */
1.52 espie 293: if (DEBUG(MAKE))
294: printf("QUEUING ");
1.75 espie 295: Array_Push(&to_build, pgn);
296: } else if (pgn->children_left < 0) {
1.52 espie 297: Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
1.40 espie 298: }
299: }
1.1 deraadt 300: }
1.52 espie 301: if (DEBUG(MAKE))
302: printf("\n");
303: requeue_successors(cgn);
1.1 deraadt 304: }
1.25 espie 305:
1.46 espie 306: static bool
307: try_to_make_node(GNode *gn)
308: {
309: if (DEBUG(MAKE))
310: printf("Examining %s...", gn->name);
1.52 espie 311:
1.64 espie 312: if (gn->built_status == HELDBACK) {
313: if (DEBUG(HELDJOBS))
314: printf("%s already held back ???\n", gn->name);
315: return false;
316: }
317:
1.75 espie 318: if (gn->children_left != 0) {
1.52 espie 319: if (DEBUG(MAKE))
1.75 espie 320: printf(" Requeuing (%d)\n", gn->children_left);
1.52 espie 321: add_targets_to_make(&gn->children);
1.75 espie 322: Array_Push(&to_build, gn);
1.52 espie 323: return false;
324: }
325: if (has_been_built(gn)) {
326: if (DEBUG(MAKE))
327: printf(" already made\n");
1.70 jsg 328: return false;
1.52 espie 329: }
1.75 espie 330: if (has_predecessor_left_to_build(gn)) {
1.52 espie 331: if (DEBUG(MAKE))
332: printf(" Dropping for now\n");
333: return false;
334: }
1.46 espie 335:
1.58 espie 336: /* SIB: this is where there should be a siblings loop */
1.75 espie 337: if (gn->children_left != 0) {
1.52 espie 338: if (DEBUG(MAKE))
1.75 espie 339: printf(" Requeuing (after deps: %d)\n",
340: gn->children_left);
1.52 espie 341: add_targets_to_make(&gn->children);
342: return false;
1.46 espie 343: }
1.64 espie 344: /* this is where we hold back nodes */
345: if (gn->groupling != NULL) {
346: GNode *gn2;
347: for (gn2 = gn->groupling; gn2 != gn; gn2 = gn2->groupling)
348: if (gn2->built_status == BUILDING) {
349: gn->watched = gn2;
350: gn->built_status = HELDBACK;
351: if (DEBUG(HELDJOBS))
352: printf("Holding back job %s, "
1.73 espie 353: "groupling to %s\n",
1.64 espie 354: gn->name, gn2->name);
355: Array_Push(&heldBack, gn);
356: return false;
357: }
358: }
359: if (gn->sibling != gn) {
360: GNode *gn2;
361: for (gn2 = gn->sibling; gn2 != gn; gn2 = gn2->sibling)
362: if (gn2->built_status == BUILDING) {
363: gn->watched = gn2;
364: gn->built_status = HELDBACK;
365: if (DEBUG(HELDJOBS))
366: printf("Holding back job %s, "
1.73 espie 367: "sibling to %s\n",
1.64 espie 368: gn->name, gn2->name);
369: Array_Push(&heldBack, gn);
370: return false;
371: }
372: }
1.46 espie 373: if (Make_OODate(gn)) {
374: if (DEBUG(MAKE))
375: printf("out-of-date\n");
376: if (queryFlag)
377: return true;
1.58 espie 378: /* SIB: this is where commands should get prepared */
1.46 espie 379: Make_DoAllVar(gn);
380: Job_Make(gn);
381: } else {
382: if (DEBUG(MAKE))
383: printf("up-to-date\n");
1.48 espie 384: gn->built_status = UPTODATE;
1.46 espie 385: if (gn->type & OP_JOIN) {
386: /*
1.76 espie 387: * Even for an up-to-date .JOIN node, we need its
388: * local variables, so that we have the right
389: * value for .TARGET when computing the
390: * local variables of its parent(s)...
1.46 espie 391: */
392: Make_DoAllVar(gn);
393: }
394:
395: Make_Update(gn);
396: }
397: return false;
398: }
399:
1.40 espie 400: /*
1.1 deraadt 401: *-----------------------------------------------------------------------
402: * MakeStartJobs --
403: * Start as many jobs as possible.
404: *
405: * Results:
406: * If the query flag was given to pmake, no job will be started,
407: * but as soon as an out-of-date target is found, this function
1.26 espie 408: * returns true. At all other times, this function returns false.
1.1 deraadt 409: *
410: * Side Effects:
1.75 espie 411: * Nodes are removed from the to_build queue and job table slots
1.1 deraadt 412: * are filled.
413: *-----------------------------------------------------------------------
414: */
1.26 espie 415: static bool
1.35 espie 416: MakeStartJobs(void)
1.1 deraadt 417: {
1.40 espie 418: GNode *gn;
1.4 millert 419:
1.75 espie 420: while (can_start_job() && (gn = Array_Pop(&to_build)) != NULL) {
1.46 espie 421: if (try_to_make_node(gn))
422: return true;
1.1 deraadt 423: }
1.40 espie 424: return false;
1.1 deraadt 425: }
1.25 espie 426:
1.15 espie 427: static void
1.72 espie 428: MakePrintStatus(void *gnp)
1.1 deraadt 429: {
1.69 espie 430: GNode *gn = gnp;
1.48 espie 431: if (gn->built_status == UPTODATE) {
1.40 espie 432: printf("`%s' is up to date.\n", gn->name);
1.75 espie 433: } else if (gn->children_left != 0) {
1.72 espie 434: printf("`%s' not remade because of errors.\n", gn->name);
1.1 deraadt 435: }
436: }
1.25 espie 437:
1.52 espie 438: static void
1.56 espie 439: MakeAddChild(void *to_addp, void *ap)
1.52 espie 440: {
1.69 espie 441: GNode *gn = to_addp;
442: struct growableArray *a = ap;
1.52 espie 443:
444: if (!gn->must_make && !(gn->type & OP_USE))
1.69 espie 445: Array_Push(a, gn);
1.52 espie 446: }
447:
448: static void
1.58 espie 449: MakeHandleUse(void *cgnp, void *pgnp)
1.52 espie 450: {
1.69 espie 451: GNode *cgn = cgnp;
452: GNode *pgn = pgnp;
1.58 espie 453:
454: if (cgn->type & OP_USE)
455: Make_HandleUse(cgn, pgn);
1.52 espie 456: }
457:
1.75 espie 458: /* Add stuff to the to_build queue. we try to sort things so that stuff
1.52 espie 459: * that can be done directly is done right away. This won't be perfect,
460: * since some dependencies are only discovered later (e.g., SuffFindDeps).
1.46 espie 461: */
462: static void
1.52 espie 463: add_targets_to_make(Lst todo)
1.46 espie 464: {
465: GNode *gn;
1.56 espie 466:
1.52 espie 467: unsigned int slot;
468:
1.56 espie 469: AppendList2Array(todo, &examine);
1.46 espie 470:
1.56 espie 471: while ((gn = Array_Pop(&examine)) != NULL) {
1.52 espie 472: if (gn->must_make) /* already known */
473: continue;
474: gn->must_make = true;
1.46 espie 475:
1.52 espie 476: slot = ohash_qlookup(&targets, gn->name);
477: if (!ohash_find(&targets, slot))
478: ohash_insert(&targets, slot, gn);
479:
480:
481: look_harder_for_target(gn);
1.58 espie 482: kludge_look_harder_for_target(gn);
1.52 espie 483: /*
484: * Apply any .USE rules before looking for implicit
485: * dependencies to make sure everything that should have
486: * commands has commands ...
487: */
488: Lst_ForEach(&gn->children, MakeHandleUse, gn);
1.68 espie 489: Suff_FindDeps(gn);
1.52 espie 490: expand_all_children(gn);
1.46 espie 491:
1.75 espie 492: if (gn->children_left != 0) {
1.52 espie 493: if (DEBUG(MAKE))
1.75 espie 494: printf("%s: not queuing (%d children left to build)\n",
495: gn->name, gn->children_left);
1.52 espie 496: Lst_ForEach(&gn->children, MakeAddChild,
497: &examine);
498: } else {
499: if (DEBUG(MAKE))
500: printf("%s: queuing\n", gn->name);
1.75 espie 501: Array_Push(&to_build, gn);
1.46 espie 502: }
503: }
1.56 espie 504: if (randomize_queue)
1.75 espie 505: randomize_garray(&to_build);
1.46 espie 506: }
507:
1.1 deraadt 508: /*-
509: *-----------------------------------------------------------------------
1.6 millert 510: * Make_Run --
511: * Initialize the nodes to remake and the list of nodes which are
512: * ready to be made by doing a breadth-first traversal of the graph
513: * starting from the nodes in the given list. Once this traversal
1.75 espie 514: * is finished, all the 'leaves' of the graph are in the to_build
1.6 millert 515: * queue.
516: * Using this queue and the Job module, work back up the graph,
517: * calling on MakeStartJobs to keep the job table as full as
518: * possible.
519: *
1.1 deraadt 520: * Results:
1.26 espie 521: * true if work was done. false otherwise.
1.1 deraadt 522: *
523: * Side Effects:
1.48 espie 524: * The must_make field of all nodes involved in the creation of the given
1.75 espie 525: * targets is set to 1. The to_build list is set to contain all the
1.6 millert 526: * 'leaves' of these subgraphs.
1.1 deraadt 527: *-----------------------------------------------------------------------
528: */
1.26 espie 529: bool
1.35 espie 530: Make_Run(Lst targs) /* the initial list of targets */
1.1 deraadt 531: {
1.65 espie 532: bool problem; /* errors occurred */
1.40 espie 533:
1.54 espie 534: /* wild guess at initial sizes */
1.75 espie 535: Array_Init(&to_build, 500);
1.56 espie 536: Array_Init(&examine, 150);
1.64 espie 537: Array_Init(&heldBack, 100);
1.52 espie 538: ohash_init(&targets, 10, &gnode_info);
1.54 espie 539: if (DEBUG(PARALLEL))
540: random_setup();
1.40 espie 541:
1.46 espie 542: add_targets_to_make(targs);
1.40 espie 543: if (queryFlag) {
544: /*
1.41 espie 545: * We wouldn't do any work unless we could start some jobs in
546: * the next loop... (we won't actually start any, of course,
1.40 espie 547: * this is just to see if any of the targets was out of date)
548: */
549: return MakeStartJobs();
550: } else {
551: /*
552: * Initialization. At the moment, no jobs are running and until
553: * some get started, nothing will happen since the remaining
1.41 espie 554: * upward traversal of the graph is performed by the routines
555: * in job.c upon the finishing of a job. So we fill the Job
1.40 espie 556: * table as much as we can before going into our loop.
557: */
558: (void)MakeStartJobs();
1.1 deraadt 559: }
1.4 millert 560:
1.1 deraadt 561: /*
1.40 espie 562: * Main Loop: The idea here is that the ending of jobs will take
563: * care of the maintenance of data structures and the waiting for output
564: * will cause us to be idle most of the time while our children run as
565: * much as possible. Because the job table is kept as full as possible,
566: * the only time when it will be empty is when all the jobs which need
567: * running have been run, so that is the end condition of this loop.
1.41 espie 568: * Note that the Job module will exit if there were any errors unless
1.40 espie 569: * the keepgoing flag was given.
1.1 deraadt 570: */
1.40 espie 571: while (!Job_Empty()) {
1.57 espie 572: handle_running_jobs();
1.40 espie 573: (void)MakeStartJobs();
574: }
575:
1.77 espie 576: if (!queryFlag)
577: problem = Job_Finish();
1.40 espie 578:
1.1 deraadt 579: /*
1.40 espie 580: * Print the final status of each target. E.g. if it wasn't made
581: * because some inferior reported an error.
1.1 deraadt 582: */
1.72 espie 583: if (targets_contain_cycles()) {
584: break_and_print_cycles(targs);
585: problem = true;
586: }
587: Lst_Every(targs, MakePrintStatus);
1.65 espie 588: if (problem)
1.52 espie 589: Fatal("Errors while building");
1.4 millert 590:
1.40 espie 591: return true;
1.72 espie 592: }
593:
594: /* round-about detection: assume make is bug-free, if there are targets
595: * that have not been touched, it means they never were reached, so we can
596: * look for a cycle
597: */
598: static bool
599: targets_contain_cycles(void)
600: {
601: GNode *gn;
602: unsigned int i;
603: bool cycle = false;
604: bool first = true;
605:
1.73 espie 606: for (gn = ohash_first(&targets, &i); gn != NULL;
1.72 espie 607: gn = ohash_next(&targets, &i)) {
608: if (has_been_built(gn))
609: continue;
610: cycle = true;
611: if (first)
612: printf("Error target(s) unaccounted for: ");
613: printf("%s ", gn->name);
614: first = false;
615: }
616: if (!first)
617: printf("\n");
618: return cycle;
619: }
620:
621: static void
622: print_unlink_cycle(struct growableArray *l, GNode *c)
623: {
624: LstNode ln;
625: GNode *gn = NULL;
626: unsigned int i;
627:
628: printf("Cycle found: ");
629:
630: for (i = 0; i != l->n; i++) {
631: gn = l->a[i];
632: if (gn == c)
633: printf("(");
634: printf("%s -> ", gn->name);
635: }
636: printf("%s)\n", c->name);
637: assert(gn);
638:
639: /* So the first element is tied to our node, find and kill the link */
640: for (ln = Lst_First(&gn->children); ln != NULL; ln = Lst_Adv(ln)) {
641: GNode *gn2 = Lst_Datum(ln);
642: if (gn2 == c) {
643: Lst_Remove(&gn->children, ln);
644: return;
645: }
646: }
647: /* this shouldn't happen ever */
648: assert(0);
649: }
650:
651: /* each call to find_cycle records a cycle in cycle, to break at node c.
652: * this will stop eventually.
653: */
654: static void
655: break_and_print_cycles(Lst t)
656: {
657: struct growableArray cycle;
658:
659: Array_Init(&cycle, 16); /* cycles are generally shorter */
660: while (1) {
661: GNode *c;
662:
663: Array_Reset(&cycle);
664: c = find_cycle(t, &cycle);
665: if (c)
666: print_unlink_cycle(&cycle, c);
667: else
668: break;
669: }
670: free(cycle.a);
671: }
672:
673:
674: static GNode *
675: find_cycle(Lst l, struct growableArray *cycle)
676: {
677: LstNode ln;
678:
679: for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
680: GNode *gn = Lst_Datum(ln);
681: if (gn->in_cycle) {
682: /* we should print the cycle and not do more */
683: return gn;
684: }
685:
686: if (gn->built_status == UPTODATE)
687: continue;
1.75 espie 688: if (gn->children_left != 0) {
1.73 espie 689: GNode *c;
1.72 espie 690:
691: gn->in_cycle = true;
692: Array_Push(cycle, gn);
693: c = find_cycle(&gn->children, cycle);
694: gn->in_cycle = false;
695: if (c)
696: return c;
697: Array_Pop(cycle);
698: }
699: }
700: return NULL;
1.1 deraadt 701: }