more parallel make fixes.

Preparations to fix the engine:
- new function has_been_built(gn), that tells you what's the status of
a given node. Allows us to run Suff_FindDeps later, by updating the number
of unmade children correctly.
- take out the code that handles shell expansions in an expand_children*
set of functions, called by Suff_FindDeps, among others. These must be
called early in the engine to avoid creating bogus nodes.

Engine fixes:
- take the predecessor/successor special handling out, deal with it in
separate functions.
- don't count nodes. Explicitly track them all in a hash table (better
way to deal with non-built issues).
- don't run Suff_FindDeps at start, but just before building an actual node.
This allows make to find all dependencies correctly, as in groff.

Pfiou! now it works.

6 files changed, 179 insertions, 127 deletions

diff --git a/usr.bin/make/gnode.h b/usr.bin/make/gnode.h
index aea2457f39f..51e33b307d9 100644
--- a/usr.bin/make/gnode.h
+++ b/usr.bin/make/gnode.h
@@ -1,7 +1,7 @@
 #ifndef GNODE_H
 #define GNODE_H
 /*	$OpenPackages$ */
-/*	$OpenBSD: gnode.h,v 1.10 2007/11/10 13:59:48 espie Exp $ */
+/*	$OpenBSD: gnode.h,v 1.11 2007/11/24 15:41:01 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -138,6 +138,7 @@ struct GNode_ {
     char name[1];	/* The target's name */
 };
 
+#define has_been_built(gn)	((gn)->built_status == MADE || (gn)->built_status == UPTODATE)
 /*
  * The OP_ constants are used when parsing a dependency line as a way of
  * communicating to other parts of the program the way in which a target
diff --git a/usr.bin/make/make.c b/usr.bin/make/make.c
index 1d3dc9af39d..535a8e57fbd 100644
--- a/usr.bin/make/make.c
+++ b/usr.bin/make/make.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: make.c,v 1.51 2007/11/18 09:20:25 espie Exp $	*/
+/*	$OpenBSD: make.c,v 1.52 2007/11/24 15:41:01 espie Exp $	*/
 /*	$NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $	*/
 
 /*
@@ -60,6 +60,9 @@
 #include <limits.h>
 #include <stdio.h>
 #include <signal.h>
+#include <stddef.h>
+#include <string.h>
+#include <ohash.h>
 #include "config.h"
 #include "defines.h"
 #include "dir.h"
@@ -80,9 +83,7 @@ static LIST	toBeMade;	/* The current fringe of the graph. These
 				 * MakeOODate. It is added to by
 				 * Make_Update and subtracted from by
 				 * MakeStartJobs */
-static int	numNodes;	/* Number of nodes to be processed. If this
-				 * is non-zero when Job_Empty() returns
-				 * true, there's a cycle in the graph */
+static struct ohash targets;	/* stuff we must build */
 
 static void MakeAddChild(void *, void *);
 static void MakeHandleUse(void *, void *);
@@ -91,30 +92,46 @@ static void MakePrintStatus(void *, void *);
 static bool try_to_make_node(GNode *);
 static void add_targets_to_make(Lst);
 
-/*-
- *-----------------------------------------------------------------------
- * MakeAddChild  --
- *	Function used by Make_Run to add a child to the list l.
- *	It will only add the child if its make field is false.
- *
- * Side Effects:
- *	The given list is extended
- *-----------------------------------------------------------------------
- */
-static void
-MakeAddChild(void *to_addp, void *lp)
+static bool has_unmade_predecessor(GNode *);
+static void requeue_successors(GNode *);
+
+static bool
+has_unmade_predecessor(GNode *gn)
 {
-	GNode	   *to_add = (GNode *)to_addp;
-	Lst 	   l = (Lst)lp;
+	LstNode ln;
+
+	if (Lst_IsEmpty(&gn->preds))
+		return false;
 
-	if (!to_add->must_make && !(to_add->type & OP_USE))
-		Lst_EnQueue(l, to_add);
+
+	for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)) {
+		GNode	*pgn = (GNode *)Lst_Datum(ln);
+
+		if (pgn->must_make && pgn->built_status == UNKNOWN) {
+			if (DEBUG(MAKE))
+				printf("predecessor %s not made yet.\n", 
+				    pgn->name);
+			return true;
+		}
+	}
+	return false;
 }
 
 static void
-MakeHandleUse(void *pgn, void *cgn)
+requeue_successors(GNode *gn)
 {
-	Make_HandleUse((GNode *)pgn, (GNode *)cgn);
+	LstNode ln;
+	/* Deal with successor nodes. If any is marked for making and has an
+	 * unmade count of 0, has not been made and isn't in the examination
+	 * queue, it means we need to place it in the queue as it restrained
+	 * itself before.	*/
+	for (ln = Lst_First(&gn->successors); ln != NULL; ln = Lst_Adv(ln)) {
+		GNode	*succ = (GNode *)Lst_Datum(ln);
+
+		if (succ->must_make && succ->unmade == 0 
+		    && succ->built_status == UNKNOWN)
+			(void)Lst_QueueNew(&toBeMade, succ);
+	}
 }
 
 /*-
@@ -178,6 +195,9 @@ Make_Update(GNode *cgn)	/* the child node */
 		pgn = (GNode *)Lst_Datum(ln);
 		if (pgn->must_make) {
 			pgn->unmade--;
+			if (DEBUG(MAKE))
+				printf("%s--=%d ", 
+				    pgn->name, pgn->unmade);
 
 			if ( ! (cgn->type & (OP_EXEC|OP_USE))) {
 				if (cgn->built_status == MADE) {
@@ -195,23 +215,17 @@ Make_Update(GNode *cgn)	/* the child node */
 				 * predecessors will be dealt with in
 				 * MakeStartJobs.
 				 */
+				if (DEBUG(MAKE))
+					printf("QUEUING ");
 				Lst_EnQueue(&toBeMade, pgn);
 			} else if (pgn->unmade < 0) {
-				Error("Graph cycles through %s", pgn->name);
+				Error("Child %s discovered graph cycles through %s", cgn->name, pgn->name);
 			}
 		}
 	}
-	/* Deal with successor nodes. If any is marked for making and has an
-	 * unmade count of 0, has not been made and isn't in the examination
-	 * queue, it means we need to place it in the queue as it restrained
-	 * itself before.	*/
-	for (ln = Lst_First(&cgn->successors); ln != NULL; ln = Lst_Adv(ln)) {
-		GNode	*succ = (GNode *)Lst_Datum(ln);
-
-		if (succ->must_make && succ->unmade == 0 
-		    && succ->built_status == UNKNOWN)
-			(void)Lst_QueueNew(&toBeMade, succ);
-	}
+	if (DEBUG(MAKE))
+		printf("\n");
+	requeue_successors(cgn);
 }
 
 static bool
@@ -219,35 +233,32 @@ try_to_make_node(GNode *gn)
 {
 	if (DEBUG(MAKE))
 		printf("Examining %s...", gn->name);
-	/*
-	 * Make sure any and all predecessors that are going to be made,
-	 * have been.
-	 */
-	if (!Lst_IsEmpty(&gn->preds)) {
-		LstNode ln;
-
-		for (ln = Lst_First(&gn->preds); ln != NULL; ln = Lst_Adv(ln)){
-			GNode	*pgn = (GNode *)Lst_Datum(ln);
-
-			if (pgn->must_make && pgn->built_status == UNKNOWN) {
-				if (DEBUG(MAKE))
-					printf(
-					    "predecessor %s not made yet.\n", 
-					    pgn->name);
-				/*
-				 * there's a predecessor as yet unmade, so we
-				 * just drop this node on the floor. When the
-				 * node in question has been made, it will
-				 * notice this node as being ready to make but
-				 * as yet unmade and will place the node on the
-				 * queue.
-				 */
-				return false;
-			}
-		}
+		
+	if (gn->unmade != 0) {
+		if (DEBUG(MAKE))
+			printf(" Requeuing (%d)\n", gn->unmade);
+		add_targets_to_make(&gn->children);
+		Lst_EnQueue(&toBeMade, gn);
+		return false;
+	}
+	if (has_been_built(gn)) {
+		if (DEBUG(MAKE))
+			printf(" already made\n");
+			return false;
+	}
+	if (has_unmade_predecessor(gn)) {
+		if (DEBUG(MAKE))
+			printf(" Dropping for now\n");
+		return false;
 	}
 
-	numNodes--;
+	Suff_FindDeps(gn);
+	if (gn->unmade != 0) {
+		if (DEBUG(MAKE))
+			printf(" Requeuing (after deps: %d)\n", gn->unmade);
+		add_targets_to_make(&gn->children);
+		return false;
+	}
 	if (Make_OODate(gn)) {
 		if (DEBUG(MAKE))
 			printf("out-of-date\n");
@@ -354,40 +365,63 @@ MakePrintStatus(
 }
 
 
-/*
- * Make an initial downward pass over the graph, marking nodes to be
- * made as we go down. We call Suff_FindDeps to find where a node is and
- * to get some children for it if it has none and also has no commands.
- * If the node is a leaf, we stick it on the toBeMade queue to
- * be looked at in a minute, otherwise we add its children to our queue
- * and go on about our business.
+static void
+MakeAddChild(void *to_addp, void *lp)
+{
+	GNode *gn = (GNode *)to_addp;
+
+	if (!gn->must_make && !(gn->type & OP_USE))
+		Lst_EnQueue((Lst)lp, gn);
+}
+
+static void
+MakeHandleUse(void *pgn, void *cgn)
+{
+	Make_HandleUse((GNode *)pgn, (GNode *)cgn);
+}
+
+/* Add stuff to the toBeMade queue. we try to sort things so that stuff 
+ * that can be done directly is done right away.  This won't be perfect,
+ * since some dependencies are only discovered later (e.g., SuffFindDeps).
  */
 static void
-add_targets_to_make(Lst targs)
+add_targets_to_make(Lst todo)
 {
-	LIST examine;	/* List of targets to examine */
 	GNode *gn;
+	LIST examine;
+	unsigned int slot;
+
+	Lst_Clone(&examine, todo, NOCOPY);
 
-	Lst_Clone(&examine, targs, NOCOPY);
 	while ((gn = (GNode *)Lst_DeQueue(&examine)) != NULL) {
-		if (!gn->must_make) {
-			gn->must_make = true;
-			numNodes++;
+		if (gn->must_make) 	/* already known */
+			continue;
+		gn->must_make = true;
 
-			look_harder_for_target(gn);
-			/*
-			 * Apply any .USE rules before looking for implicit
-			 * dependencies to make sure everything that should have
-			 * commands has commands ...
-			 */
-			Lst_ForEach(&gn->children, MakeHandleUse, gn);
-			Suff_FindDeps(gn);
-
-			if (gn->unmade != 0)
-				Lst_ForEach(&gn->children, MakeAddChild,
-				    &examine);
-			else
-				Lst_EnQueue(&toBeMade, gn);
+		slot = ohash_qlookup(&targets, gn->name);
+		if (!ohash_find(&targets, slot))
+			ohash_insert(&targets, slot, gn);
+
+
+		look_harder_for_target(gn);
+		/*
+		 * Apply any .USE rules before looking for implicit
+		 * dependencies to make sure everything that should have
+		 * commands has commands ...
+		 */
+		Lst_ForEach(&gn->children, MakeHandleUse, gn);
+		expand_all_children(gn);
+
+		if (gn->unmade != 0) {
+			if (DEBUG(MAKE))
+				printf("%s: not queuing (%d unmade children)\n",
+				    gn->name, gn->unmade);
+			Lst_ForEach(&gn->children, MakeAddChild,
+			    &examine);
+		} else {
+			if (DEBUG(MAKE))
+				printf("%s: queuing\n", gn->name);
+			Lst_EnQueue(&toBeMade, gn);
 		}
 	}
 }
@@ -416,11 +450,13 @@ add_targets_to_make(Lst targs)
 bool
 Make_Run(Lst targs)		/* the initial list of targets */
 {
-	int 	    errors;	/* Number of errors the Job module reports */
+	int errors;	/* Number of errors the Job module reports */
+	GNode *gn;
+	unsigned int i;
+	bool cycle;
 
 	Static_Lst_Init(&toBeMade);
-
-	numNodes = 0;
+	ohash_init(&targets, 10, &gnode_info);
 
 	add_targets_to_make(targs);
 	if (queryFlag) {
@@ -458,13 +494,24 @@ Make_Run(Lst targs)		/* the initial list of targets */
 	}
 
 	errors = 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;
+		errors++;
+	    	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.
 	 */
-	errors = errors == 0 && numNodes != 0;
-	Lst_ForEach(targs, MakePrintStatus, &errors);
+	Lst_ForEach(targs, MakePrintStatus, &cycle);
+	if (errors)
+		Fatal("Errors while building");
 
 	return true;
 }
diff --git a/usr.bin/make/suff.c b/usr.bin/make/suff.c
index 206c63cfe18..c0b29ebf7e3 100644
--- a/usr.bin/make/suff.c
+++ b/usr.bin/make/suff.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: suff.c,v 1.76 2007/11/17 16:39:45 espie Exp $ */
+/*	$OpenBSD: suff.c,v 1.77 2007/11/24 15:41:01 espie Exp $ */
 /*	$NetBSD: suff.c,v 1.13 1996/11/06 17:59:25 christos Exp $	*/
 
 /*
@@ -207,7 +207,7 @@ static int SuffRemoveSrc(Lst);
 static void SuffAddLevel(Lst, Src *);
 static Src *SuffFindThem(Lst, Lst);
 static Src *SuffFindCmds(Src *, Lst);
-static void SuffExpandChildren(void *, void *);
+static void SuffExpandChildren(LstNode, GNode *);
 static void SuffExpandVarChildren(LstNode, GNode *, GNode *);
 static void SuffExpandWildChildren(LstNode, GNode *, GNode *);
 static bool SuffApplyTransform(GNode *, GNode *, Suff *, Suff *);
@@ -1138,7 +1138,8 @@ SuffExpandVarChildren(LstNode after, GNode *cgn, GNode *pgn)
 			Lst_Append(&pgn->children, after, gn);
 			after = Lst_Adv(after);
 			Lst_AtEnd(&gn->parents, pgn);
-			pgn->unmade++;
+			if (!has_been_built(gn))
+				pgn->unmade++;
 		}
 	}
 	/* Free the result.  */
@@ -1192,7 +1193,8 @@ SuffExpandWildChildren(LstNode after, GNode *cgn, GNode *pgn)
 			Lst_Append(&pgn->children, after, gn);
 			after = Lst_Adv(after);
 			Lst_AtEnd(&gn->parents, pgn);
-			pgn->unmade++;
+			if (!has_been_built(gn))
+				pgn->unmade++;
 		}
 	}
 
@@ -1213,16 +1215,10 @@ SuffExpandWildChildren(LstNode after, GNode *cgn, GNode *pgn)
  *-----------------------------------------------------------------------
  */
 static void
-SuffExpandChildren(
-    void	*cgnp,		/* Child to examine */
-    void	*pgnp)		/* Parent node being processed */
+SuffExpandChildren(LstNode ln, /* LstNode of child, so we can replace it */
+    GNode *pgn)
 {
-	GNode	*cgn = (GNode *)cgnp;
-	GNode	*pgn = (GNode *)pgnp;
-	LstNode	ln;
-	/* New nodes effectively take the place of the child, so we place them
-	 * after the child.  */
-	ln = Lst_Member(&pgn->children, cgn);
+	GNode	*cgn = (GNode *)Lst_Datum(ln);
 
 	/* First do variable expansion -- this takes precedence over wildcard
 	 * expansion. If the result contains wildcards, they'll be gotten to
@@ -1242,6 +1238,17 @@ SuffExpandChildren(
 	Lst_Remove(&pgn->children, ln);
 }
 
+void
+expand_children_from(GNode *parent, LstNode from)
+{
+	LstNode np, ln;
+
+	for (ln = from; ln != NULL; ln = np) {
+		np = Lst_Adv(ln);
+		SuffExpandChildren(ln, parent);
+	}
+}
+
 /*-
  *-----------------------------------------------------------------------
  * SuffApplyTransform --
@@ -1267,7 +1274,6 @@ SuffApplyTransform(
     Suff	*s)	/* Source suffix */
 {
 	LstNode	ln;	/* General node */
-	LstNode	np;	    /* Next node for loop */
 	char	*tname; /* Name of transformation rule */
 	GNode	*gn;	/* Node for same */
 
@@ -1275,7 +1281,8 @@ SuffApplyTransform(
 		/* Not already linked, so form the proper links between the
 		 * target and source.  */
 		Lst_AtEnd(&sGn->parents, tGn);
-		tGn->unmade++;
+		if (!has_been_built(sGn))
+			tGn->unmade++;
 	}
 
 	if ((sGn->type & OP_OPMASK) == OP_DOUBLEDEP) {
@@ -1290,7 +1297,8 @@ SuffApplyTransform(
 				/* Not already linked, so form the proper links
 				 * between the target and source.  */
 				Lst_AtEnd(&gn->parents, tGn);
-				tGn->unmade++;
+				if (!has_been_built(gn))
+					tGn->unmade++;
 			}
 		}
 	}
@@ -1318,10 +1326,7 @@ SuffApplyTransform(
 	Make_HandleUse(gn, tGn);
 
 	/* Deal with wildcards and variables in any acquired sources.  */
-	for (ln = Lst_Succ(ln); ln != NULL; ln = np) {
-		np = Lst_Adv(ln);
-		SuffExpandChildren(Lst_Datum(ln), tGn);
-	}
+	expand_children_from(tGn, Lst_Succ(ln));
 
 	/* Keep track of another parent to which this beast is transformed so
 	 * the .IMPSRC variable can be set correctly for the parent.  */
@@ -1387,7 +1392,8 @@ SuffFindArchiveDeps(
 	/* Create the link between the two nodes right off. */
 	if (Lst_AddNew(&gn->children, mem)) {
 		Lst_AtEnd(&mem->parents, gn);
-		gn->unmade++;
+		if (!has_been_built(mem))
+			gn->unmade++;
 	}
 
 	/* Copy variables from member node to this one.  */
@@ -1513,8 +1519,6 @@ SuffFindNormalDeps(
     GNode	*gn,	    /* Node for which to find sources */
     Lst 	slst)
 {
-	LstNode	np;
-	LstNode ln;
 	LIST srcs;	/* List of sources at which to look */
 	LIST targs;	/* List of targets to which things can be
 			 * transformed. They all have the same file,
@@ -1608,10 +1612,7 @@ SuffFindNormalDeps(
 
 	/* Now we've got the important local variables set, expand any sources
 	 * that still contain variables or wildcards in their names.  */
-	for (ln = Lst_First(&gn->children); ln != NULL; ln = np) {
-		np = Lst_Adv(ln);
-		SuffExpandChildren(Lst_Datum(ln), gn);
-	}
+	expand_all_children(gn);
 
 	if (targ == NULL) {
 		if (DEBUG(SUFF))
diff --git a/usr.bin/make/suff.h b/usr.bin/make/suff.h
index fd6a6d19873..de1df279a00 100644
--- a/usr.bin/make/suff.h
+++ b/usr.bin/make/suff.h
@@ -1,7 +1,7 @@
 #ifndef SUFF_H
 #define SUFF_H
 /*	$OpenPackages$ */
-/*	$OpenBSD: suff.h,v 1.3 2007/09/17 12:42:09 espie Exp $ */
+/*	$OpenBSD: suff.h,v 1.4 2007/11/24 15:41:01 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -45,5 +45,8 @@ extern void Suff_End(void);
 #define Suff_End()
 #endif
 extern void Suff_PrintAll(void);
+extern void expand_children_from(GNode *, LstNode);
+#define expand_all_children(gn)	\
+    expand_children_from(gn, Lst_First(&(gn)->children))
 
 #endif
diff --git a/usr.bin/make/targ.c b/usr.bin/make/targ.c
index 6477b8b2ea7..71bb7490383 100644
--- a/usr.bin/make/targ.c
+++ b/usr.bin/make/targ.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: targ.c,v 1.53 2007/11/10 13:59:48 espie Exp $ */
+/*	$OpenBSD: targ.c,v 1.54 2007/11/24 15:41:01 espie Exp $ */
 /*	$NetBSD: targ.c,v 1.11 1997/02/20 16:51:50 christos Exp $	*/
 
 /*
@@ -134,7 +134,6 @@ static LIST allTargets;
 static void TargFreeGN(void *);
 #endif
 #define Targ_FindConstantNode(n, f) Targ_FindNodeh(n, sizeof(n), K_##n, f)
-static const char *status_to_string(GNode *);
 
 
 GNode *begin_node, *end_node, *interrupt_node, *DEFAULT;
@@ -349,7 +348,7 @@ Targ_PrintType(int type)
 		}
     }
 }
-static const char *
+const char *
 status_to_string(GNode *gn)
 {
 	switch (gn->built_status) {
diff --git a/usr.bin/make/targ.h b/usr.bin/make/targ.h
index 8af62308438..fd88500ecaf 100644
--- a/usr.bin/make/targ.h
+++ b/usr.bin/make/targ.h
@@ -1,7 +1,7 @@
 #ifndef TARG_H
 #define TARG_H
 /*	$OpenPackages$ */
-/*	$OpenBSD: targ.h,v 1.5 2007/11/02 17:27:24 espie Exp $ */
+/*	$OpenBSD: targ.h,v 1.6 2007/11/24 15:41:01 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -79,4 +79,5 @@ extern struct ohash_info gnode_info;
 
 extern void look_harder_for_target(GNode *);
 extern void Targ_setdirs(const char *, const char *);
+const char *status_to_string(GNode *);
 #endif