From ca33491d33329c58b92027fe3a82f6f2e9cce689 Mon Sep 17 00:00:00 2001 From: espie Date: Thu, 22 Jun 2017 17:08:20 +0000 Subject: [PATCH] better display of cycles in -j mode. lots of tests by krw@ review and comments by pirofti@, more tweaks to come --- usr.bin/make/gnode.h | 10 +-- usr.bin/make/make.c | 185 +++++++++++++++++++++++++++++-------------- usr.bin/make/targ.c | 3 +- 3 files changed, 129 insertions(+), 69 deletions(-) diff --git a/usr.bin/make/gnode.h b/usr.bin/make/gnode.h index e5b34ab377a..af56fd47f71 100644 --- a/usr.bin/make/gnode.h +++ b/usr.bin/make/gnode.h @@ -1,6 +1,6 @@ #ifndef GNODE_H #define GNODE_H -/* $OpenBSD: gnode.h,v 1.28 2013/05/30 08:58:38 espie Exp $ */ +/* $OpenBSD: gnode.h,v 1.29 2017/06/22 17:08:20 espie Exp $ */ /* * Copyright (c) 2001 Marc Espie. @@ -129,19 +129,13 @@ struct GNode_ { * made (used only in compat mode) * ABORTED - The target was aborted due to * an error making an inferior. - * CYCLE - Marked as potentially being part of - * a graph cycle. If we come back to a - * node marked this way, it is printed - * and 'built_status' is changed to ENDCYCLE. - * ENDCYCLE - the cycle has been completely - * printed. Go back and unmark all its - * members. */ char *path; /* The full pathname of the file */ unsigned int type; /* Its type (see the OP flags, below) */ int order; /* Its wait weight */ int unmade; /* The number of unmade children */ + int in_cycle; /* cycle detection */ struct timespec mtime; /* Its modification time */ GNode *youngest; /* Its youngest child */ diff --git a/usr.bin/make/make.c b/usr.bin/make/make.c index f3423e5ab74..8d36f3d9fa5 100644 --- a/usr.bin/make/make.c +++ b/usr.bin/make/make.c @@ -1,4 +1,4 @@ -/* $OpenBSD: make.c,v 1.71 2016/10/21 16:12:38 espie Exp $ */ +/* $OpenBSD: make.c,v 1.72 2017/06/22 17:08:20 espie Exp $ */ /* $NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $ */ /* @@ -99,7 +99,14 @@ static struct ohash targets; /* stuff we must build */ static void MakeAddChild(void *, void *); static void MakeHandleUse(void *, void *); static bool MakeStartJobs(void); -static void MakePrintStatus(void *, void *); +static void MakePrintStatus(void *); + +/* Cycle detection functions */ +static bool targets_contain_cycles(void); +static void print_unlink_cycle(struct growableArray *, GNode *); +static void break_and_print_cycles(Lst); +static GNode *find_cycle(Lst, struct growableArray *); + static bool try_to_make_node(GNode *); static void add_targets_to_make(Lst); @@ -416,59 +423,17 @@ MakeStartJobs(void) return false; } -/*- - *----------------------------------------------------------------------- - * MakePrintStatus -- - * Print the status of a top-level node, viz. it being up-to-date - * already or not created due to an error in a lower level. - * Callback function for Make_Run via Lst_ForEach. - * - * Side Effects: - * A message may be printed. - *----------------------------------------------------------------------- - */ static void -MakePrintStatus( - void *gnp, /* Node to examine */ - void *cyclep) /* True if gn->unmade being non-zero implies - * a cycle in the graph, not an error in an - * inferior */ +MakePrintStatus(void *gnp) { GNode *gn = gnp; - bool *cp = cyclep; - bool cycle = *cp; if (gn->built_status == UPTODATE) { printf("`%s' is up to date.\n", gn->name); } else if (gn->unmade != 0) { - if (cycle) { - bool t = true; - /* - * If printing cycles and came to one that has unmade - * children, print out the cycle by recursing on its - * children. Note a cycle like: - * a : b - * b : c - * c : b - * will cause this to erroneously complain about a - * being in the cycle, but this is a good approximation. - */ - if (gn->built_status == CYCLE) { - Error("Graph cycles through `%s'", gn->name); - gn->built_status = ENDCYCLE; - Lst_ForEach(&gn->children, MakePrintStatus, &t); - gn->built_status = UNKNOWN; - } else if (gn->built_status != ENDCYCLE) { - gn->built_status = CYCLE; - Lst_ForEach(&gn->children, MakePrintStatus, &t); - } - } else { - printf("`%s' not remade because of errors.\n", - gn->name); - } + printf("`%s' not remade because of errors.\n", gn->name); } } - static void MakeAddChild(void *to_addp, void *ap) { @@ -564,9 +529,6 @@ bool Make_Run(Lst targs) /* the initial list of targets */ { bool problem; /* errors occurred */ - GNode *gn; - unsigned int i; - bool cycle; /* wild guess at initial sizes */ Array_Init(&toBeMade, 500); @@ -611,24 +573,127 @@ Make_Run(Lst targs) /* the initial list of targets */ } problem = Job_Finish(); - cycle = false; - for (gn = ohash_first(&targets, &i); gn != NULL; - gn = ohash_next(&targets, &i)) { - if (has_been_built(gn)) - continue; - cycle = true; - problem = true; - printf("Error: target %s unaccounted for (%s)\n", - gn->name, status_to_string(gn)); - } /* * Print the final status of each target. E.g. if it wasn't made * because some inferior reported an error. */ - Lst_ForEach(targs, MakePrintStatus, &cycle); + if (targets_contain_cycles()) { + break_and_print_cycles(targs); + problem = true; + } + Lst_Every(targs, MakePrintStatus); if (problem) Fatal("Errors while building"); return true; } + +/* round-about detection: assume make is bug-free, if there are targets + * that have not been touched, it means they never were reached, so we can + * look for a cycle + */ +static bool +targets_contain_cycles(void) +{ + GNode *gn; + unsigned int i; + bool cycle = false; + bool first = true; + + for (gn = ohash_first(&targets, &i); gn != NULL; + gn = ohash_next(&targets, &i)) { + if (has_been_built(gn)) + continue; + cycle = true; + if (first) + printf("Error target(s) unaccounted for: "); + printf("%s ", gn->name); + first = false; + } + if (!first) + printf("\n"); + return cycle; +} + +static void +print_unlink_cycle(struct growableArray *l, GNode *c) +{ + LstNode ln; + GNode *gn = NULL; + unsigned int i; + + printf("Cycle found: "); + + for (i = 0; i != l->n; i++) { + gn = l->a[i]; + if (gn == c) + printf("("); + printf("%s -> ", gn->name); + } + printf("%s)\n", c->name); + assert(gn); + + /* So the first element is tied to our node, find and kill the link */ + for (ln = Lst_First(&gn->children); ln != NULL; ln = Lst_Adv(ln)) { + GNode *gn2 = Lst_Datum(ln); + if (gn2 == c) { + Lst_Remove(&gn->children, ln); + return; + } + } + /* this shouldn't happen ever */ + assert(0); +} + +/* each call to find_cycle records a cycle in cycle, to break at node c. + * this will stop eventually. + */ +static void +break_and_print_cycles(Lst t) +{ + struct growableArray cycle; + + Array_Init(&cycle, 16); /* cycles are generally shorter */ + while (1) { + GNode *c; + + Array_Reset(&cycle); + c = find_cycle(t, &cycle); + if (c) + print_unlink_cycle(&cycle, c); + else + break; + } + free(cycle.a); +} + + +static GNode * +find_cycle(Lst l, struct growableArray *cycle) +{ + LstNode ln; + + for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) { + GNode *gn = Lst_Datum(ln); + if (gn->in_cycle) { + /* we should print the cycle and not do more */ + return gn; + } + + if (gn->built_status == UPTODATE) + continue; + if (gn->unmade != 0) { + GNode *c; + + gn->in_cycle = true; + Array_Push(cycle, gn); + c = find_cycle(&gn->children, cycle); + gn->in_cycle = false; + if (c) + return c; + Array_Pop(cycle); + } + } + return NULL; +} diff --git a/usr.bin/make/targ.c b/usr.bin/make/targ.c index df4712ef9bf..03003e94f2b 100644 --- a/usr.bin/make/targ.c +++ b/usr.bin/make/targ.c @@ -1,4 +1,4 @@ -/* $OpenBSD: targ.c,v 1.77 2016/10/21 16:12:38 espie Exp $ */ +/* $OpenBSD: targ.c,v 1.78 2017/06/22 17:08:20 espie Exp $ */ /* $NetBSD: targ.c,v 1.11 1997/02/20 16:51:50 christos Exp $ */ /* @@ -155,6 +155,7 @@ Targ_NewGNi(const char *name, const char *ename) gn->unmade = 0; gn->must_make = false; gn->built_status = UNKNOWN; + gn->in_cycle = false; gn->childMade = false; gn->order = 0; ts_set_out_of_date(gn->mtime); -- 2.20.1