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