changes to get target equivalence to work better.

- add new file to create lists of equivalent targets (siblings)
- use that for sequential mode to have much better VPATH support
- separate checking commands from reporting error, for later.
- zap DieHorribly accordingly
- renumber existing flags
- signal_running_jobs() is simpler than pass_signal_to_jobs()
- new debug option -dn for name matching.

Similar code to handle parallel make is still missing.

thanks to Mark, Miod, Theo, Otto, Todd for tests and/or comments.

18 files changed, 702 insertions, 209 deletions

diff --git a/usr.bin/make/Makefile b/usr.bin/make/Makefile
index e92d5eb048e..a6aaa17c604 100644
--- a/usr.bin/make/Makefile
+++ b/usr.bin/make/Makefile
@@ -1,4 +1,4 @@
-#	$OpenBSD: Makefile,v 1.49 2008/01/12 13:05:57 espie Exp $
+#	$OpenBSD: Makefile,v 1.50 2008/11/04 07:22:35 espie Exp $
 
 PROG=	make
 CFLAGS+= -I${.OBJDIR} -I${.CURDIR}
@@ -17,7 +17,7 @@ HOSTCFLAGS+=${CDEFS}
 
 SRCS=	arch.c buf.c cmd_exec.c compat.c cond.c dir.c direxpand.c engine.c \
 	error.c for.c init.c job.c lowparse.c main.c make.c memory.c parse.c \
-	parsevar.c str.c stats.c suff.c targ.c timestamp.c \
+	parsevar.c str.c stats.c suff.c targ.c targequiv.c timestamp.c \
 	var.c varmodifiers.c varname.c
 SRCS+=	lstAddNew.c lstAppend.c lstConcat.c lstConcatDestroy.c \
 	lstDeQueue.c lstDestroy.c lstDupl.c lstFindFrom.c lstForEachFrom.c \
diff --git a/usr.bin/make/compat.c b/usr.bin/make/compat.c
index 614cba7c566..f241f0d5669 100644
--- a/usr.bin/make/compat.c
+++ b/usr.bin/make/compat.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: compat.c,v 1.69 2008/01/29 22:23:10 espie Exp $	*/
+/*	$OpenBSD: compat.c,v 1.70 2008/11/04 07:22:35 espie Exp $	*/
 /*	$NetBSD: compat.c,v 1.14 1996/11/06 17:59:01 christos Exp $	*/
 
 /*
@@ -48,6 +48,7 @@
 #include "suff.h"
 #include "var.h"
 #include "targ.h"
+#include "targequiv.h"
 #include "error.h"
 #include "extern.h"
 #include "gnode.h"
@@ -72,11 +73,34 @@ CompatMake(void *gnp,	/* The node to make */
 	GNode *gn = (GNode *)gnp;
 	GNode *pgn = (GNode *)pgnp;
 
+	GNode *sib;
+	bool cmdsOk;
+
+	if (DEBUG(MAKE))
+		printf("CompatMake(%s, %s)\n", pgn ? pgn->name : "NULL", 
+		    gn->name);
+
+	/* XXX some loops are not loops, people write dependencies
+	 * between siblings to make sure they get built.
+	 * Also, we don't recognize direct loops.
+	 */
+	if (gn == pgn)
+		return;
 	look_harder_for_target(gn);
 
+	if (pgn != NULL && is_sibling(gn, pgn))
+		return;
+
+	if (pgn == NULL)
+		pgn = gn;
+
 	if (pgn->type & OP_MADE) {
-		(void)Dir_MTime(gn);
-		gn->built_status = UPTODATE;
+		sib = gn;
+		do {
+			(void)Dir_MTime(sib);
+			sib->built_status = UPTODATE;
+			sib = sib->sibling;
+		} while (sib != gn);
 	}
 
 	if (gn->type & OP_USE) {
@@ -91,9 +115,19 @@ CompatMake(void *gnp,	/* The node to make */
 		 * parent as well.  */
 		gn->must_make = true;
 		gn->built_status = BEINGMADE;
-		Suff_FindDeps(gn);
-		Lst_ForEach(&gn->children, CompatMake, gn);
+		/* note that, in case we have siblings, we only check all
+		 * children for all siblings, but we don't try to apply
+		 * any other rule.
+		 */
+		sib = gn;
+		do {
+			Suff_FindDeps(sib);
+			Lst_ForEach(&sib->children, CompatMake, gn);
+			sib = sib->sibling;
+		} while (sib != gn);
+
 		if (!gn->must_make) {
+			Error("Build for %s aborted", gn->name);
 			gn->built_status = ABORTED;
 			pgn->must_make = false;
 			return;
@@ -118,20 +152,40 @@ CompatMake(void *gnp,	/* The node to make */
 		if (queryFlag)
 			exit(-1);
 
-		/* We need to be re-made. We also have to make sure we've
-		 * got a $?  variable. To be nice, we also define the $>
-		 * variable using Make_DoAllVar().  */
-		Make_DoAllVar(gn);
+		/* normally, we run the job, but if we can't find any
+		 * commands, we defer to siblings instead.
+		 */
+		sib = gn;
+		do {
+			/* We need to be re-made. We also have to make sure
+			 * we've got a $?  variable. To be nice, we also define
+			 * the $> variable using Make_DoAllVar().  
+			 */
+			Make_DoAllVar(sib);
+			cmdsOk = Job_CheckCommands(sib);
+			if (cmdsOk || (gn->type & OP_OPTIONAL))
+				break;
+
+			sib = sib->sibling;
+		} while (sib != gn);
 
-		if (Job_CheckCommands(gn, Fatal)) {
+		if (cmdsOk) {
 			/* Our commands are ok, but we still have to worry
 			 * about the -t flag...	*/
 			if (!touchFlag)
-				run_gnode(gn);
-			else
-				Job_Touch(gn);
-		} else
-			gn->built_status = ERROR;
+				run_gnode(sib);
+			else {
+				Job_Touch(sib);
+				if (gn != sib)
+					Job_Touch(gn);
+			}
+		} else {
+			job_failure(gn, Fatal);
+			sib->built_status = ERROR;
+		}
+
+		/* copy over what we just did */
+		gn->built_status = sib->built_status;
 
 		if (gn->built_status != ERROR) {
 			/* If the node was made successfully, mark it so,
@@ -140,6 +194,7 @@ CompatMake(void *gnp,	/* The node to make */
 			 * This is to keep its state from affecting that of
 			 * its parent.  */
 			gn->built_status = MADE;
+			sib->built_status = MADE;
 			/* This is what Make does and it's actually a good
 			 * thing, as it allows rules like
 			 *
@@ -158,6 +213,12 @@ CompatMake(void *gnp,	/* The node to make */
 				gn->mtime = now;
 			if (is_strictly_before(gn->mtime, gn->cmtime))
 				gn->mtime = gn->cmtime;
+			if (sib != gn) {
+				if (noExecute || is_out_of_date(Dir_MTime(sib)))
+					sib->mtime = now;
+				if (is_strictly_before(sib->mtime, sib->cmtime))
+					sib->mtime = sib->cmtime;
+			}
 			if (DEBUG(MAKE))
 				printf("update time: %s\n",
 				    time_to_string(gn->mtime));
@@ -186,7 +247,7 @@ CompatMake(void *gnp,	/* The node to make */
 	else {
 		switch (gn->built_status) {
 		case BEINGMADE:
-			Error("Graph cycles through %s\n", gn->name);
+			Error("Graph cycles through %s", gn->name);
 			gn->built_status = ERROR;
 			pgn->must_make = false;
 			break;
@@ -234,7 +295,7 @@ Compat_Run(Lst targs)		/* List of target nodes to re-create */
 	 */
 	errors = 0;
 	while ((gn = (GNode *)Lst_DeQueue(targs)) != NULL) {
-		CompatMake(gn, gn);
+		CompatMake(gn, NULL);
 
 		if (gn->built_status == UPTODATE)
 			printf("`%s' is up to date.\n", gn->name);
diff --git a/usr.bin/make/defines.h b/usr.bin/make/defines.h
index 90f762742c6..b0df89d0f5f 100644
--- a/usr.bin/make/defines.h
+++ b/usr.bin/make/defines.h
@@ -2,7 +2,7 @@
 #define DEFINES_H
 
 /*	$OpenPackages$ */
-/*	$OpenBSD: defines.h,v 1.6 2007/11/28 09:40:08 espie Exp $ */
+/*	$OpenBSD: defines.h,v 1.7 2008/11/04 07:22:35 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -91,6 +91,7 @@ extern int debug;
 #define DEBUG_LOUD	0x0800
 #define DEBUG_JOBBANNER	0x1000
 #define DEBUG_PARALLEL	0x2000
+#define DEBUG_NAME_MATCHING	0x4000
 
 #define CONCAT(a,b)	a##b
 
diff --git a/usr.bin/make/dir.c b/usr.bin/make/dir.c
index d9ab9b918c8..b43efefe89c 100644
--- a/usr.bin/make/dir.c
+++ b/usr.bin/make/dir.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: dir.c,v 1.55 2007/09/17 12:17:27 espie Exp $ */
+/*	$OpenBSD: dir.c,v 1.56 2008/11/04 07:22:35 espie Exp $ */
 /*	$NetBSD: dir.c,v 1.14 1997/03/29 16:51:26 christos Exp $	*/
 
 /*
@@ -347,6 +347,12 @@ create_PathEntry(const char *name, const char *ename)
 	return p;
 }
 
+char *
+PathEntry_name(struct PathEntry *p)
+{
+	return p->name;
+}
+
 /* Side Effects: cache the current directory */
 void
 Dir_Init(void)
diff --git a/usr.bin/make/dir.h b/usr.bin/make/dir.h
index ec856f6c573..4eb17781720 100644
--- a/usr.bin/make/dir.h
+++ b/usr.bin/make/dir.h
@@ -2,7 +2,7 @@
 #define DIR_H
 
 /*	$OpenPackages$ */
-/*	$OpenBSD: dir.h,v 1.23 2007/09/17 09:44:20 espie Exp $	*/
+/*	$OpenBSD: dir.h,v 1.24 2008/11/04 07:22:35 espie Exp $	*/
 /*	$NetBSD: dir.h,v 1.4 1996/11/06 17:59:05 christos Exp $ */
 
 /*
@@ -152,4 +152,5 @@ extern struct PathEntry *dot;
 /* Handles wildcard expansion on a given directory. */
 extern  void Dir_MatchFilesi(const char *, const char *, struct PathEntry *,
     Lst);
+extern char *PathEntry_name(struct PathEntry *);
 #endif /* DIR_H */
diff --git a/usr.bin/make/engine.c b/usr.bin/make/engine.c
index 0c6e123fd25..d9c03f1faa9 100644
--- a/usr.bin/make/engine.c
+++ b/usr.bin/make/engine.c
@@ -1,4 +1,4 @@
-/*	$OpenBSD: engine.c,v 1.19 2008/01/29 22:23:10 espie Exp $ */
+/*	$OpenBSD: engine.c,v 1.20 2008/11/04 07:22:35 espie Exp $ */
 /*
  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
  * Copyright (c) 1988, 1989 by Adam de Boor
@@ -35,6 +35,7 @@
 
 #include <sys/types.h>
 #include <sys/wait.h>
+#include <assert.h>
 #include <limits.h>
 #include <stdio.h>
 #include <stdlib.h>
@@ -74,7 +75,7 @@ static void run_command(const char *, bool);
 static void handle_compat_interrupts(GNode *);
 
 bool
-Job_CheckCommands(GNode *gn, void (*abortProc)(char *, ...))
+Job_CheckCommands(GNode *gn)
 {
 	/* Alter our type to tell if errors should be ignored or things
 	 * should not be printed so CompatRunCommand knows what to do.
@@ -109,32 +110,38 @@ Job_CheckCommands(GNode *gn, void (*abortProc)(char *, ...))
 			 * The node wasn't the target of an operator we have no
 			 * .DEFAULT rule to go on and the target doesn't
 			 * already exist. There's nothing more we can do for
-			 * this branch. If the -k flag wasn't given, we stop in
-			 * our tracks, otherwise we just don't update this
-			 * node's parents so they never get examined.
+			 * this branch. 
 			 */
-			static const char msg[] =
-			    "make: don't know how to make";
-
-			if (gn->type & OP_OPTIONAL) {
-				(void)fprintf(stdout, "%s %s(ignored)\n", msg,
-				    gn->name);
-				(void)fflush(stdout);
-			} else if (keepgoing) {
-				(void)fprintf(stdout, "%s %s(continuing)\n",
-				    msg, gn->name);
-				(void)fflush(stdout);
-				return false;
-			} else {
-				(*abortProc)("%s %s. Stop in %s.", msg,
-				    gn->name, Var_Value(".CURDIR"));
-				return false;
-			}
-		}
+			 return false;
+	    	}
 	}
 	return true;
 }
 
+void
+job_failure(GNode *gn, void (*abortProc)(char *, ...))
+{
+	/*
+	 If the -k flag wasn't given, we stop in
+	 * our tracks, otherwise we just don't update this
+	 * node's parents so they never get examined.
+	 */
+	static const char msg[] =
+	    "make: don't know how to make";
+
+	if (gn->type & OP_OPTIONAL) {
+		(void)fprintf(stdout, "%s %s(ignored)\n", msg,
+		    gn->name);
+		(void)fflush(stdout);
+	} else if (keepgoing) {
+		(void)fprintf(stdout, "%s %s(continuing)\n",
+		    msg, gn->name);
+		(void)fflush(stdout);
+	} else {
+		(*abortProc)("%s %s. Stop in %s.", msg,
+		    gn->name, Var_Value(".CURDIR"));
+	}
+}
 /* touch files the hard way, by writing stuff to them */
 static int
 rewrite_time(const char *name)
@@ -210,35 +217,37 @@ Make_HandleUse(GNode	*cgn,	/* The .USE node */
 	GNode	*gn;	/* A child of the .USE node */
 	LstNode	ln;	/* An element in the children list */
 
-	if (cgn->type & (OP_USE|OP_TRANSFORM)) {
-		if ((cgn->type & OP_USE) || Lst_IsEmpty(&pgn->commands)) {
-			/* .USE or transformation and target has no commands
-			 * -- append the child's commands to the parent.  */
-			Lst_Concat(&pgn->commands, &cgn->commands);
-		}
 
-		for (ln = Lst_First(&cgn->children); ln != NULL;
-		    ln = Lst_Adv(ln)) {
-			gn = (GNode *)Lst_Datum(ln);
+	assert(cgn->type & (OP_USE|OP_TRANSFORM));
 
-			if (Lst_AddNew(&pgn->children, gn)) {
-				Lst_AtEnd(&gn->parents, pgn);
-				pgn->unmade++;
-			}
-		}
+	if ((cgn->type & OP_USE) || Lst_IsEmpty(&pgn->commands)) {
+		/* .USE or transformation and target has no commands
+		 * -- append the child's commands to the parent.  */
+		Lst_Concat(&pgn->commands, &cgn->commands);
+	}
 
-		pgn->type |= cgn->type & ~(OP_OPMASK|OP_USE|OP_TRANSFORM);
+	for (ln = Lst_First(&cgn->children); ln != NULL;
+	    ln = Lst_Adv(ln)) {
+		gn = (GNode *)Lst_Datum(ln);
 
-		/*
-		 * This child node is now "made", so we decrement the count of
-		 * unmade children in the parent... We also remove the child
-		 * from the parent's list to accurately reflect the number of
-		 * decent children the parent has. This is used by Make_Run to
-		 * decide whether to queue the parent or examine its children...
-		 */
-		if (cgn->type & OP_USE)
-			pgn->unmade--;
+		if (Lst_AddNew(&pgn->children, gn)) {
+			Lst_AtEnd(&gn->parents, pgn);
+			pgn->unmade++;
+		}
 	}
+
+	pgn->type |= cgn->type & ~(OP_OPMASK|OP_USE|OP_TRANSFORM);
+
+	/*
+	 * This child node is now "made", so we decrement the count of
+	 * unmade children in the parent... We also remove the child
+	 * from the parent's list to accurately reflect the number of
+	 * decent children the parent has. This is used by Make_Run to
+	 * decide whether to queue the parent or examine its children...
+	 */
+	if (cgn->type & OP_USE)
+		pgn->unmade--;
+
 	/* if the parent node doesn't have any location, then inherit the
 	 * use stuff, since that gives us better error messages.
 	 */
diff --git a/usr.bin/make/engine.h b/usr.bin/make/engine.h
index 7c0a7eaf3c8..e41dcf92dde 100644
--- a/usr.bin/make/engine.h
+++ b/usr.bin/make/engine.h
@@ -1,6 +1,6 @@
 #ifndef ENGINE_H
 #define ENGINE_H
-/*	$OpenBSD: engine.h,v 1.5 2008/01/29 22:23:10 espie Exp $	*/
+/*	$OpenBSD: engine.h,v 1.6 2008/11/04 07:22:35 espie Exp $	*/
 
 /*
  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -38,11 +38,12 @@
  *	from: @(#)job.h 8.1 (Berkeley) 6/6/93
  */
 
-/* ok = Job_CheckCommands(node, abort);
+/* ok = Job_CheckCommands(node);
  *	verify the integrity of a node's commands, pulling stuff off
  * 	.DEFAULT and other places if necessary.
  */
-extern bool Job_CheckCommands(GNode *, void (*abortProc)(char *, ...));
+extern bool Job_CheckCommands(GNode *);
+extern void job_failure(GNode *, void (*abortProc)(char *, ...));
 /* Job_Touch(node);
  *	touch the path corresponding to a node or update the corresponding
  *	archive object.
diff --git a/usr.bin/make/error.c b/usr.bin/make/error.c
index a017524c844..30b19f7c391 100644
--- a/usr.bin/make/error.c
+++ b/usr.bin/make/error.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: error.c,v 1.16 2008/01/12 13:08:59 espie Exp $ */
+/*	$OpenBSD: error.c,v 1.17 2008/11/04 07:22:35 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -108,19 +108,6 @@ Punt(char *fmt, ...)
 	va_end(ap);
 	(void)fprintf(stderr, "\n");
 
-	DieHorribly();
-}
-
-/*-
- * DieHorribly --
- *	Exit without giving a message.
- *
- * Side Effects:
- *	A big one...
- */
-void
-DieHorribly(void)
-{
 	Job_AbortAll();
 	if (DEBUG(GRAPH2))
 		Targ_PrintGraph(2);
diff --git a/usr.bin/make/error.h b/usr.bin/make/error.h
index e501b52f9a9..2e9905fb2f9 100644
--- a/usr.bin/make/error.h
+++ b/usr.bin/make/error.h
@@ -1,7 +1,7 @@
 #ifndef ERROR_H
 #define ERROR_H
 /*	$OpenPackages$ */
-/*	$OpenBSD: error.h,v 1.8 2007/11/03 10:41:48 espie Exp $ */
+/*	$OpenBSD: error.h,v 1.9 2008/11/04 07:22:35 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -45,7 +45,6 @@
 extern void Error(char *, ...);
 extern void Fatal(char *, ...);
 extern void Punt(char *, ...);
-extern void DieHorribly(void);
 extern void Finish(int);
 
 /*
diff --git a/usr.bin/make/gnode.h b/usr.bin/make/gnode.h
index 122963b8e39..9039728999c 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.13 2008/01/29 22:23:10 espie Exp $ */
+/*	$OpenBSD: gnode.h,v 1.14 2008/11/04 07:22:35 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -88,7 +88,7 @@ struct Suff_;
 struct GNode_ {
     int special_op;	/* special op to apply */
     unsigned char special;/* type of special node */
-    char must_make;		/* true if this target needs to be remade */
+    char must_make;	/* true if this target needs to be remade */
     char childMade;	/* true if one of this target's children was
 			 * made */
     char built_status;	/* Set to reflect the state of processing
@@ -109,8 +109,9 @@ struct GNode_ {
 			 *	printed. Go back and unmark all its
 			 *	members.
 			 */
+    char build_lock;	/* for parallel build in siblings */
     char *path;		/* The full pathname of the file */
-    int type;		/* Its type (see the OP flags, below) */
+    unsigned int type;		/* Its type (see the OP flags, below) */
     int order;		/* Its wait weight */
 
     int unmade;		/* The number of unmade children */
@@ -134,10 +135,18 @@ struct GNode_ {
     struct Suff_ *suffix;/* Suffix for the node (determined by
 			 * Suff_FindDeps and opaque to everyone
 			 * but the Suff module) */
+    struct GNode_ *sibling;	/* equivalent targets */
+    /* stuff for target name equivalence */
+    char *basename;	/* pointer to name stripped of path */
+    struct GNode_ *next;
     char name[1];	/* The target's name */
 };
 
-#define has_been_built(gn)	((gn)->built_status == MADE || (gn)->built_status == UPTODATE)
+#define has_been_built(gn) \
+	((gn)->built_status == MADE || (gn)->built_status == UPTODATE)
+#define should_have_file(gn) \
+	((gn)->special == SPECIAL_NONE && \
+	((gn)->type & (OP_PHONY | OP_DUMMY)) == 0)
 /*
  * 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
@@ -174,26 +183,26 @@ struct GNode_ {
 				     * children was out-of-date */
 #define OP_MADE 	0x00000800  /* Assume the node is already made; even if
 				     * it really is out of date */
-#define OP_INVISIBLE	0x00004000  /* The node is invisible to its parents.
+#define OP_INVISIBLE	0x00001000  /* The node is invisible to its parents.
 				     * I.e. it doesn't show up in the parents's
 				     * local variables. */
-#define OP_NOTMAIN	0x00008000  /* The node is exempt from normal 'main
+#define OP_NOTMAIN	0x00002000  /* The node is exempt from normal 'main
 				     * target' processing in parse.c */
-#define OP_PHONY	0x00010000  /* Not a file target; run always */
-#define OP_NOPATH	0x00020000  /* Don't search for file in the path */
-#define OP_NODEFAULT	0x00040000  /* Special node that never needs */
+#define OP_PHONY	0x00004000  /* Not a file target; run always */
+#define OP_NOPATH	0x00008000  /* Don't search for file in the path */
+#define OP_NODEFAULT	0x00010000  /* Special node that never needs */
 				    /* DEFAULT commands applied */
-#define OP_DUMMY	0x00080000  /* node was created by default, but it */
+#define OP_DUMMY	0x00020000  /* node was created by default, but it */
 				    /* does not really exist. */
 /* Attributes applied by PMake */
-#define OP_TRANSFORM	0x80000000  /* The node is a transformation rule */
-#define OP_MEMBER	0x40000000  /* Target is a member of an archive */
-#define OP_LIB		0x20000000  /* Target is a library */
-#define OP_ARCHV	0x10000000  /* Target is an archive construct */
-#define OP_HAS_COMMANDS 0x08000000  /* Target has all the commands it should.
+#define OP_TRANSFORM	0x00040000  /* The node is a transformation rule */
+#define OP_MEMBER	0x00080000  /* Target is a member of an archive */
+#define OP_LIB		0x00100000  /* Target is a library */
+#define OP_ARCHV	0x00200000  /* Target is an archive construct */
+#define OP_HAS_COMMANDS 0x00400000  /* Target has all the commands it should.
 				     * Used when parsing to catch multiple
 				     * commands for a target */
-#define OP_DEPS_FOUND	0x02000000  /* Already processed by Suff_FindDeps */
+#define OP_DEPS_FOUND	0x00800000  /* Already processed by Suff_FindDeps */
 #define OP_RESOLVED	0x01000000  /* We looked harder already */
 
 /*
diff --git a/usr.bin/make/job.c b/usr.bin/make/job.c
index f6afd59401d..e769b0e91eb 100644
--- a/usr.bin/make/job.c
+++ b/usr.bin/make/job.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: job.c,v 1.113 2008/03/24 18:03:53 espie Exp $	*/
+/*	$OpenBSD: job.c,v 1.114 2008/11/04 07:22:35 espie Exp $	*/
 /*	$NetBSD: job.c,v 1.16 1996/11/06 17:59:08 christos Exp $	*/
 
 /*
@@ -171,13 +171,7 @@ static fd_set *actual_mask = NULL;	/* actual select argument */
 static int largest_fd = -1;
 static size_t mask_size = 0;
 
-/*
- * When JobStart attempts to run a job but isn't allowed to,
- * the job is placed on the queuedJobs queue to be run
- * when the next job finishes.
- */
 static LIST	stoppedJobs;	
-static LIST	queuedJobs;
 
 /* wait possibilities */
 #define JOB_EXITED 0
@@ -205,7 +199,7 @@ struct error_info {
 # endif
 #endif
 
-static void pass_signal_to_job(void *, void *);
+static void signal_running_jobs(int);
 static void handle_all_signals(void);
 static void handle_signal(int);
 static int JobCmpPid(void *, void *);
@@ -353,29 +347,20 @@ handle_all_signals()
 	}
 }
 
-/*-
- *-----------------------------------------------------------------------
- * JobCondPassSig --
- *	Pass a signal to a job if USE_PGRP
- *	is defined.
- *
- * Side Effects:
- *	None, except the job may bite it.
- *-----------------------------------------------------------------------
- */
 static void
-pass_signal_to_job(void *jobp,	/* Job to biff */
-    void *signop)		/* Signal to send it */
+signal_running_jobs(int signo)
 {
-	Job *job = (Job *)jobp;
-	int signo = *(int *)signop;
-	if (DEBUG(JOB)) {
-		(void)fprintf(stdout,
-		    "pass_signal_to_job passing signal %d to child %ld.\n",
-		    signo, (long)job->pid);
-		(void)fflush(stdout);
+	LstNode ln;
+	for (ln = Lst_First(&runningJobs); ln != NULL; ln = Lst_Adv(ln)) {
+	    	Job *job = Lst_Datum(ln);
+		if (DEBUG(JOB)) {
+			(void)fprintf(stdout,
+			    "signal %d to child %ld.\n",
+			    signo, (long)job->pid);
+			(void)fflush(stdout);
+		}
+		KILL(job->pid, signo);
 	}
-	KILL(job->pid, signo);
 }
 
 /*-
@@ -398,7 +383,7 @@ handle_signal(int signo) /* The signal number we've received */
 		(void)fprintf(stdout, "handle_signal(%d) called.\n", signo);
 		(void)fflush(stdout);
 	}
-	Lst_ForEach(&runningJobs, pass_signal_to_job, &signo);
+	signal_running_jobs(signo);
 
 	/*
 	 * Deal with proper cleanup based on the signal received. We only run
@@ -444,8 +429,7 @@ handle_signal(int signo) /* The signal number we've received */
 
 	(void)KILL(getpid(), signo);
 
-	signo = SIGCONT;
-	Lst_ForEach(&runningJobs, pass_signal_to_job, &signo);
+	signal_running_jobs(SIGCONT);
 
 	(void)sigprocmask(SIG_SETMASK, &omask, NULL);
 	sigprocmask(SIG_SETMASK, &omask, NULL);
@@ -567,11 +551,6 @@ finish_job(Job *job, int reason, int code)
 		 * exited non-zero.
 		 */
 		done = code != 0;
-		/*
-		 * Old comment said: "Note we don't want to close down any of
-		 * the streams until we know we're at the end." But we do.
-		 * Otherwise when are we going to print the rest of the stuff?
-		 */
 		close_job_pipes(job);
 	} else {
 		/*
@@ -606,16 +585,6 @@ finish_job(Job *job, int reason, int code)
 			    "Warning: "
 			    "process %ld was not continuing.\n",
 			    (long)job->pid);
-#if 0
-			/*
-			 * We don't really want to restart a job from
-			 * scratch just because it continued,
-			 * especially not without killing the
-			 * continuing process!	That's why this is
-			 * ifdef'ed out.  FD - 9/17/90
-			 */
-			JobRestart(job);
-#endif
 		}
 		job->flags &= ~JOB_CONTINUING;
 		Lst_AtEnd(&runningJobs, job);
@@ -954,7 +923,7 @@ prepare_job(GNode *gn, int flags)
 	 * Check the commands now so any attributes from .DEFAULT have a chance
 	 * to migrate to the node
 	 */
-	cmdsOK = Job_CheckCommands(gn, Error);
+	cmdsOK = Job_CheckCommands(gn);
 	expand_commands(gn);
 
 	if ((gn->type & OP_MAKE) || (!noExecute && !touchFlag)) {
@@ -962,9 +931,8 @@ prepare_job(GNode *gn, int flags)
 		 * We're serious here, but if the commands were bogus, we're
 		 * also dead...
 		 */
-		if (!cmdsOK) {
-			DieHorribly();
-		}
+		if (!cmdsOK)
+			job_failure(gn, Punt);
 
 		if (Lst_IsEmpty(&gn->commands))
 			noExec = true;
@@ -1016,7 +984,7 @@ prepare_job(GNode *gn, int flags)
  *
  * Side Effects:
  *	A new Job node is created and added to the list of running
- *	jobs. PMake is forked and a child shell created.
+ *	jobs. Make is forked and a child shell created.
  *-----------------------------------------------------------------------
  */
 static void
@@ -1313,7 +1281,6 @@ Job_Init(int maxproc)
 {
 	Static_Lst_Init(&runningJobs);
 	Static_Lst_Init(&stoppedJobs);
-	Static_Lst_Init(&queuedJobs);
 	Static_Lst_Init(&errorsList);
 	maxJobs =	  maxproc;
 	nJobs =	  	  0;
diff --git a/usr.bin/make/main.c b/usr.bin/make/main.c
index 16700f36260..be58856340e 100644
--- a/usr.bin/make/main.c
+++ b/usr.bin/make/main.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: main.c,v 1.91 2008/01/10 20:34:03 espie Exp $ */
+/*	$OpenBSD: main.c,v 1.92 2008/11/04 07:22:35 espie Exp $ */
 /*	$NetBSD: main.c,v 1.34 1997/03/24 20:56:36 gwr Exp $	*/
 
 /*
@@ -267,6 +267,9 @@ MainParseArgs(int argc, char **argv)
 				case 'm':
 					debug |= DEBUG_MAKE;
 					break;
+				case 'n':
+					debug |= DEBUG_NAME_MATCHING;
+					break;
 				case 'p':
 					debug |= DEBUG_PARALLEL;
 					break;
diff --git a/usr.bin/make/make.1 b/usr.bin/make/make.1
index f0f5f73e121..9eda2eb92fe 100644
--- a/usr.bin/make/make.1
+++ b/usr.bin/make/make.1
@@ -1,4 +1,4 @@
-.\"	$OpenBSD: make.1,v 1.81 2008/09/01 08:37:45 jmc Exp $
+.\"	$OpenBSD: make.1,v 1.82 2008/11/04 07:22:35 espie Exp $
 .\"	$OpenPackages$
 .\"	$NetBSD: make.1,v 1.18 1997/03/10 21:19:53 christos Exp $
 .\"
@@ -31,7 +31,7 @@
 .\"
 .\"	from: @(#)make.1	8.4 (Berkeley) 3/19/94
 .\"
-.Dd $Mdocdate: September 1 2008 $
+.Dd $Mdocdate: November 4 2008 $
 .Dt MAKE 1
 .Os
 .Sh NAME
@@ -174,6 +174,8 @@ Also known as loud behavior.
 .It Ar m
 Print debugging information about making targets, including modification
 dates.
+.It Ar n
+Print debugging information about target names equivalence computations.
 .It Ar p
 Help finding concurrency issues for parallel make by adding some
 randomization.
diff --git a/usr.bin/make/make.c b/usr.bin/make/make.c
index d10e8b07e26..1751aceb611 100644
--- a/usr.bin/make/make.c
+++ b/usr.bin/make/make.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: make.c,v 1.57 2008/01/12 13:08:59 espie Exp $	*/
+/*	$OpenBSD: make.c,v 1.58 2008/11/04 07:22:36 espie Exp $	*/
 /*	$NetBSD: make.c,v 1.10 1996/11/06 17:59:15 christos Exp $	*/
 
 /*
@@ -78,6 +78,7 @@
 #include "engine.h"
 #include "lst.h"
 #include "targ.h"
+#include "targequiv.h"
 #include "garray.h"
 #include "memory.h"
 
@@ -250,8 +251,11 @@ Make_Update(GNode *cgn)	/* the child node */
 			printf("update time: %s\n", time_to_string(cgn->mtime));
 	}
 
+	/* SIB: this is where I should mark the build as finished */
+	cgn->build_lock = false;
 	for (ln = Lst_First(&cgn->parents); ln != NULL; ln = Lst_Adv(ln)) {
 		pgn = (GNode *)Lst_Datum(ln);
+		/* SIB: there should be a siblings loop there */
 		pgn->unmade--;
 		if (pgn->must_make) {
 			if (DEBUG(MAKE))
@@ -311,6 +315,7 @@ try_to_make_node(GNode *gn)
 		return false;
 	}
 
+	/* SIB: this is where there should be a siblings loop */
 	Suff_FindDeps(gn);
 	if (gn->unmade != 0) {
 		if (DEBUG(MAKE))
@@ -319,11 +324,15 @@ try_to_make_node(GNode *gn)
 		return false;
 	}
 	if (Make_OODate(gn)) {
+		/* SIB: if a sibling is getting built, I don't build it right now */
 		if (DEBUG(MAKE))
 			printf("out-of-date\n");
 		if (queryFlag)
 			return true;
+		/* SIB: this is where commands should get prepared */
 		Make_DoAllVar(gn);
+		/* SIB: this is where I should make the gn as `being built */
+		gn->build_lock = true;
 		Job_Make(gn);
 	} else {
 		if (DEBUG(MAKE))
@@ -434,9 +443,13 @@ MakeAddChild(void *to_addp, void *ap)
 }
 
 static void
-MakeHandleUse(void *pgn, void *cgn)
+MakeHandleUse(void *cgnp, void *pgnp)
 {
-	Make_HandleUse((GNode *)pgn, (GNode *)cgn);
+	GNode *cgn = (GNode *)cgnp;
+	GNode *pgn = (GNode *)pgnp;
+
+	if (cgn->type & OP_USE)
+		Make_HandleUse(cgn, pgn);
 }
 
 /* Add stuff to the toBeMade queue. we try to sort things so that stuff 
@@ -463,6 +476,7 @@ add_targets_to_make(Lst todo)
 
 
 		look_harder_for_target(gn);
+		kludge_look_harder_for_target(gn);
 		/*
 		 * Apply any .USE rules before looking for implicit
 		 * dependencies to make sure everything that should have
diff --git a/usr.bin/make/targ.c b/usr.bin/make/targ.c
index d0f69171d7a..4238910b67a 100644
--- a/usr.bin/make/targ.c
+++ b/usr.bin/make/targ.c
@@ -1,5 +1,5 @@
 /*	$OpenPackages$ */
-/*	$OpenBSD: targ.c,v 1.56 2008/01/29 22:23:10 espie Exp $ */
+/*	$OpenBSD: targ.c,v 1.57 2008/11/04 07:22:36 espie Exp $ */
 /*	$NetBSD: targ.c,v 1.11 1997/02/20 16:51:50 christos Exp $	*/
 
 /*
@@ -121,7 +121,7 @@
 #include <stdlib.h>
 #endif
 
-static struct ohash targets;	/* a hash table of same */
+static struct ohash targets;	/* hash table of targets */
 struct ohash_info gnode_info = {
 	offsetof(GNode, name), NULL, hash_alloc, hash_free, element_alloc
 };
@@ -198,6 +198,10 @@ Targ_NewGNi(const char *name, const char *ename)
 	Lst_Init(&gn->commands);
 	Lst_Init(&gn->expanded);
 	gn->suffix = NULL;
+	gn->next = NULL;
+	gn->basename = NULL;
+	gn->sibling = gn;
+	gn->build_lock = false;
 
 #ifdef STATS_GN_CREATION
 	STAT_GN_COUNT++;
@@ -453,48 +457,8 @@ Targ_PrintGraph(int pass)	/* Which pass this is. 1 => no processing
 	Suff_PrintAll();
 }
 
-static char *curdir, *objdir;
-static size_t curdir_len, objdir_len;
-
-void
-Targ_setdirs(const char *c, const char *o)
-{
-	curdir_len = strlen(c);
-	curdir = emalloc(curdir_len+2);
-	memcpy(curdir, c, curdir_len);
-	curdir[curdir_len++] = '/';
-	curdir[curdir_len] = 0;
-
-	objdir_len = strlen(o);
-	objdir = emalloc(objdir_len+2);
-	memcpy(objdir, o, objdir_len);
-	objdir[objdir_len++] = '/';
-	objdir[objdir_len] = 0;
-}
-
-void
-look_harder_for_target(GNode *gn)
+struct ohash *
+targets_hash()
 {
-	GNode *extra, *cgn;
-	LstNode ln;
-
-	if (gn->type & (OP_RESOLVED|OP_PHONY))
-		return;
-	gn->type |= OP_RESOLVED;
-	if (strncmp(gn->name, objdir, objdir_len) == 0) {
-		extra = Targ_FindNode(gn->name + objdir_len, TARG_NOCREATE);
-		if (extra != NULL) {
-			if (Lst_IsEmpty(&gn->commands))
-				Lst_Concat(&gn->commands, &extra->commands);
-			for (ln = Lst_First(&extra->children); ln != NULL;
-			    ln = Lst_Adv(ln)) {
-				cgn = (GNode *)Lst_Datum(ln);
-
-				if (Lst_AddNew(&gn->children, cgn)) {
-					Lst_AtEnd(&cgn->parents, gn);
-					gn->unmade++;
-				}
-			}
-		}
-	}
+	return &targets;
 }
diff --git a/usr.bin/make/targ.h b/usr.bin/make/targ.h
index fd88500ecaf..a061a3c0994 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.6 2007/11/24 15:41:01 espie Exp $ */
+/*	$OpenBSD: targ.h,v 1.7 2008/11/04 07:22:36 espie Exp $ */
 
 /*
  * Copyright (c) 2001 Marc Espie.
@@ -77,7 +77,7 @@ struct ohash_info;
 
 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 *);
+struct ohash *targets_hash(void);
 #endif
diff --git a/usr.bin/make/targequiv.c b/usr.bin/make/targequiv.c
new file mode 100644
index 00000000000..956d12dfebb
--- /dev/null
+++ b/usr.bin/make/targequiv.c
@@ -0,0 +1,461 @@
+/*	$OpenBSD: targequiv.c,v 1.1 2008/11/04 07:22:36 espie Exp $ */
+/*
+ * Copyright (c) 2007-2008 Marc Espie.
+ *
+ * Extensive code changes for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+/* Compute equivalence tables of targets, helpful for VPATH and parallel
+ * make.
+ */
+
+#include <stdlib.h>
+#include <stdint.h>
+#include <stddef.h>
+#include <stdio.h>
+#include <sys/param.h>
+#include <string.h>
+#include "config.h"
+#include "defines.h"
+#include "memory.h"
+#include "ohash.h"
+#include "gnode.h"
+#include "lst.h"
+#include "suff.h"
+#include "dir.h"
+#include "targ.h"
+#include "targequiv.h"
+
+struct equiv_list {
+	GNode *first, *last;
+	char name[1];
+};
+
+static struct ohash_info equiv_info = {
+	offsetof(struct equiv_list, name), NULL, hash_alloc, hash_free, 
+	element_alloc
+};
+
+static void attach_node(GNode *, GNode *);
+static void build_equivalence(void);
+static void add_to_equiv_list(struct ohash *, GNode *);
+static char *names_match(GNode *, GNode *);
+static char *names_match_with_dir(const char *, const char *, char *, 
+    char *,  const char *);
+static char *names_match_with_dirs(const char *, const char *, char *, 
+    char *,  const char *, const char *);
+static char *relative_reduce(const char *, const char *);
+static char *relative_reduce2(const char *, const char *, const char *);
+static char *absolute_reduce(const char *);
+static size_t parse_reduce(size_t, const char *);
+static void find_siblings(GNode *);
+
+/* These functions build `equivalence lists' of targets with the same
+ * basename, as circular lists. They use an intermediate ohash as scaffold,
+ * to insert same-basename targets in a simply linked list. Then they make
+ * those lists circular, to the exception of lone elements, since they can't
+ * alias to anything.
+ * 
+ * This structure is used to simplify alias-lookup to a great extent: two
+ * nodes can only alias each other if they're part of the same equivalence
+ * set. Most nodes either don't belong to an alias set, or to a very simple
+ * alias set, thus removing most possibilities.
+ */
+static void
+add_to_equiv_list(struct ohash *equiv, GNode *gn)
+{
+	const char *end = NULL;
+	struct equiv_list *e;
+	unsigned int slot;
+
+	if (!should_have_file(gn))
+		return;
+
+	gn->basename = strrchr(gn->name, '/');
+	if (gn->basename == NULL)
+		gn->basename = gn->name;
+	else
+		gn->basename++;
+	slot = ohash_qlookupi(equiv, gn->basename, &end);
+	e = ohash_find(equiv, slot);
+	if (e == NULL) {
+		e = ohash_create_entry(&equiv_info, gn->basename, &end);
+		e->first = NULL;
+		e->last = gn;
+		ohash_insert(equiv, slot, e);
+	}
+	gn->next = e->first;
+	e->first = gn;
+}
+
+static void
+build_equivalence()
+{
+	unsigned int i;
+	GNode *gn;
+	struct equiv_list *e;
+	struct ohash equiv;
+	struct ohash *t = targets_hash();
+
+
+	ohash_init(&equiv, 10, &equiv_info);
+
+	for (gn = ohash_first(t, &i); gn != NULL; gn = ohash_next(t, &i))
+		add_to_equiv_list(&equiv, gn);
+
+	/* finish making the lists circular */
+	for (e = ohash_first(&equiv, &i); e != NULL;
+	    e = ohash_next(&equiv, &i)) {
+	    	if (e->last != e->first)
+			e->last->next = e->first;
+#ifdef CLEANUP
+		free(e);
+#endif
+	}
+#ifdef CLEANUP
+	ohash_delete(&equiv);
+#endif
+}
+
+static const char *curdir, *objdir;
+static char *kobjdir;
+static size_t objdir_len;
+
+void
+Targ_setdirs(const char *c, const char *o)
+{
+	curdir = c;
+	objdir = o;
+
+	objdir_len = strlen(o);
+	kobjdir = emalloc(objdir_len+2);
+	memcpy(kobjdir, o, objdir_len);
+	kobjdir[objdir_len++] = '/';
+	kobjdir[objdir_len] = 0;
+}
+
+
+void
+kludge_look_harder_for_target(GNode *gn)
+{
+	GNode *extra, *cgn;
+	LstNode ln;
+
+	if (strncmp(gn->name, kobjdir, objdir_len) == 0) {
+		extra = Targ_FindNode(gn->name + objdir_len, TARG_NOCREATE);
+		if (extra != NULL) {
+			if (Lst_IsEmpty(&gn->commands))
+				Lst_Concat(&gn->commands, &extra->commands);
+			for (ln = Lst_First(&extra->children); ln != NULL;
+			    ln = Lst_Adv(ln)) {
+				cgn = (GNode *)Lst_Datum(ln);
+
+				if (Lst_AddNew(&gn->children, cgn)) {
+					Lst_AtEnd(&cgn->parents, gn);
+					gn->unmade++;
+				}
+			}
+		}
+	}
+}
+
+static void
+attach_node(GNode *gn, GNode *extra)
+{
+	/* XXX normally extra->sibling == extra, but this is not
+	 * always the case yet, so we merge the two lists 
+	 */
+	GNode *tmp;
+
+	tmp = gn->sibling;
+	gn->sibling = extra->sibling;
+	extra->sibling = tmp;
+}
+
+static char *buffer = NULL;
+static size_t bufsize = MAXPATHLEN;
+
+static size_t
+parse_reduce(size_t i, const char *src)
+{
+	while (src[0] != 0) {
+		while (src[0] == '/')
+			src++;
+		/* special cases */
+		if (src[0] == '.') {
+			if (src[1] == '/') {
+				src += 2;
+				continue;
+			}
+			if (src[1] == '.' && src[2] == '/') {
+				src += 3;
+				i--;
+				while (i > 0 && buffer[i-1] != '/')
+					i--;
+				if (i == 0)
+					i = 1;
+				continue;
+			}
+		}
+		while (src[0] != '/' && src[0] != 0) {
+			if (i > bufsize - 2) {
+				bufsize *= 2;
+				buffer = erealloc(buffer, bufsize);
+			}
+			buffer[i++] = *src++;
+		}
+		buffer[i++] = *src;
+	}
+	return i;
+}
+
+static char *
+absolute_reduce(const char *src)
+{
+	size_t i = 0;
+
+	if (buffer == NULL)
+		buffer = emalloc(bufsize);
+
+	buffer[i++] = '/';
+	i = parse_reduce(i, src);
+	return estrdup(buffer); 
+}
+
+static char *
+relative_reduce(const char *dir, const char *src)
+{
+	size_t i = 0;
+	
+	if (buffer == NULL)
+		buffer = emalloc(bufsize);
+
+	buffer[i++] = '/';
+	i = parse_reduce(i, dir);
+	i--;
+
+	if (buffer[i-1] != '/')
+		buffer[i++] = '/';
+	i = parse_reduce(i, src);
+	return estrdup(buffer); 
+}
+
+static char *
+relative_reduce2(const char *dir1, const char *dir2, const char *src)
+{
+	size_t i = 0;
+	
+	if (buffer == NULL)
+		buffer = emalloc(bufsize);
+
+	buffer[i++] = '/';
+	i = parse_reduce(i, dir1);
+	i--;
+	if (buffer[i-1] != '/')
+		buffer[i++] = '/';
+
+	i = parse_reduce(i, dir2);
+	i--;
+	if (buffer[i-1] != '/')
+		buffer[i++] = '/';
+
+	i = parse_reduce(i, src);
+	return estrdup(buffer); 
+}
+
+static char *
+names_match_with_dir(const char *a, const char *b, char *ra, 
+    char *rb,  const char *dir)
+{
+	bool r;
+	bool free_a, free_b;
+	
+	if (ra == NULL) {
+		ra = relative_reduce(dir, a);
+		free_a = true;
+	} else {
+		free_a = false;
+	}
+
+	if (rb == NULL) {
+		rb = relative_reduce(dir, b);
+		free_b = true;
+	} else {
+		free_b = false;
+	}
+	r = strcmp(ra, rb) == 0;
+	if (free_a)
+		free(ra);
+	if (r)
+		return rb;
+	else {
+		if (free_b)
+			free(rb);
+		return NULL;
+	}
+}
+
+static char *
+names_match_with_dirs(const char *a, const char *b, char *ra, 
+    char *rb,  const char *dir1, const char *dir2)
+{
+	bool r;
+	bool free_a, free_b;
+	
+	if (ra == NULL) {
+		ra = relative_reduce2(dir1, dir2, a);
+		free_a = true;
+	} else {
+		free_a = false;
+	}
+
+	if (rb == NULL) {
+		rb = relative_reduce2(dir1, dir2, b);
+		free_b = true;
+	} else {
+		free_b = false;
+	}
+	r = strcmp(ra, rb) == 0;
+	if (free_a)
+		free(ra);
+	if (r)
+		return rb;
+	else {
+		if (free_b)
+			free(rb);
+		return NULL;
+	}
+}
+
+static char *
+names_match(GNode *a, GNode *b)
+{
+	char *ra = NULL , *rb = NULL;
+	char *r;
+
+	if (a->name[0] == '/')
+		ra = absolute_reduce(a->name);
+	if (b->name[0] == '/')
+		rb = absolute_reduce(b->name);
+	if (ra && rb) {
+		if (strcmp(ra, rb) == 0)
+			r = rb;
+		else
+			r = NULL;
+	} else {
+		r = names_match_with_dir(a->name, b->name, ra, rb, objdir);
+		if (!r)
+			r = names_match_with_dir(a->name, b->name, ra, rb, 
+			    curdir);
+		if (!r) {
+			/* b has necessarily the same one */
+			Lst l = find_suffix_path(a);
+			LstNode ln;
+
+			for (ln = Lst_First(l); ln != NULL; ln = Lst_Adv(ln)) {
+				const char *p = PathEntry_name(Lst_Datum(ln));
+				if (p[0] == '/') {
+					r = names_match_with_dir(a->name, 
+					    b->name, ra, rb, p);
+					if (r)
+						break;
+				} else {
+					r = names_match_with_dirs(a->name,
+					    b->name, ra, rb, p, objdir);
+					if (r)
+						break;
+					r = names_match_with_dirs(a->name,
+					    b->name, ra, rb, p, curdir);
+					if (r)
+						break;
+				}
+			}
+		}
+	}
+	free(ra);
+	if (r != rb)
+		free(rb);
+	return r;
+}
+
+static void
+find_siblings(GNode *gn)
+{
+	GNode *gn2;
+	char *fullpath;
+
+	/* not part of an equivalence class: can't alias */
+	if (gn->next == NULL)
+		return;
+	/* already resolved, actually */
+	if (gn->sibling != gn)
+		return;
+	if (DEBUG(NAME_MATCHING))
+		fprintf(stderr, "Matching for %s:", gn->name);
+	/* look through the aliases */
+	for (gn2 = gn->next; gn2 != gn; gn2 = gn2->next) {
+		fullpath = names_match(gn, gn2);
+		if (fullpath) {
+			attach_node(gn, gn2);
+		} else {
+			if (DEBUG(NAME_MATCHING))
+				fputc('!', stderr);
+		}
+		if (DEBUG(NAME_MATCHING))
+			fprintf(stderr, "%s ", gn2->name);
+	}
+	if (DEBUG(NAME_MATCHING))
+		fputc('\n', stderr);
+}
+
+void
+look_harder_for_target(GNode *gn)
+{
+	static bool equiv_was_built = false;
+
+	if (!equiv_was_built) {
+		build_equivalence();
+		equiv_was_built = true;
+	}
+
+	if (gn->type & (OP_RESOLVED | OP_PHONY))
+		return;
+	gn->type |= OP_RESOLVED;
+	find_siblings(gn);
+}
+
+bool
+is_sibling(GNode *gn, GNode *gn2)
+{
+	GNode *sibling;
+	
+	sibling = gn;
+	do {
+		if (sibling == gn2)
+			return true;
+		sibling = sibling->sibling;
+	} while (sibling != gn);
+
+	return false;
+}
diff --git a/usr.bin/make/targequiv.h b/usr.bin/make/targequiv.h
new file mode 100644
index 00000000000..bb094152da0
--- /dev/null
+++ b/usr.bin/make/targequiv.h
@@ -0,0 +1,8 @@
+#ifndef TARGEQUIV_H
+#define TARGEQUIV_H
+extern void look_harder_for_target(GNode *);
+extern void Targ_setdirs(const char *, const char *);
+extern bool is_sibling(GNode *, GNode *);
+extern void kludge_look_harder_for_target(GNode *);
+
+#endif