better display of cycles in -j mode.

lots of tests by krw@
review and comments by pirofti@, more tweaks to come

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);