Source-Changes-HG archive
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]
[src/trunk]: src/usr.bin/make Rework how :: dependencies are handled.
details: https://anonhg.NetBSD.org/src/rev/fa3a338606d5
branches: trunk
changeset: 476382:fa3a338606d5
user: mycroft <mycroft%NetBSD.org@localhost>
date: Wed Sep 15 10:47:37 1999 +0000
description:
Rework how :: dependencies are handled.
Build a list of `cohorts' as before, but do *not* link each one into all the
parent nodes; instead, copy the `cohort' lists into the stream of targets to
be built inside Make_ExpandUse(). Also do the attribute propagation as a
separate pass after parsing.
This eliminates several O(n^2) algorithms.
diffstat:
usr.bin/make/main.c | 11 ++++++--
usr.bin/make/make.c | 13 +++++++--
usr.bin/make/nonints.h | 3 +-
usr.bin/make/parse.c | 63 +++++++++++++++----------------------------------
usr.bin/make/suff.c | 29 +++-------------------
usr.bin/make/targ.c | 42 +++++++++++++++++++++++++++-----
6 files changed, 80 insertions(+), 81 deletions(-)
diffs (truncated from 369 to 300 lines):
diff -r b539998e5aca -r fa3a338606d5 usr.bin/make/main.c
--- a/usr.bin/make/main.c Wed Sep 15 10:25:30 1999 +0000
+++ b/usr.bin/make/main.c Wed Sep 15 10:47:37 1999 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: main.c,v 1.49 1999/09/15 08:48:17 mycroft Exp $ */
+/* $NetBSD: main.c,v 1.50 1999/09/15 10:47:37 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,7 +39,7 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: main.c,v 1.49 1999/09/15 08:48:17 mycroft Exp $";
+static char rcsid[] = "$NetBSD: main.c,v 1.50 1999/09/15 10:47:37 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
@@ -51,7 +51,7 @@
#if 0
static char sccsid[] = "@(#)main.c 8.3 (Berkeley) 3/19/94";
#else
-__RCSID("$NetBSD: main.c,v 1.49 1999/09/15 08:48:17 mycroft Exp $");
+__RCSID("$NetBSD: main.c,v 1.50 1999/09/15 10:47:37 mycroft Exp $");
#endif
#endif /* not lint */
#endif
@@ -782,6 +782,11 @@
*/
Suff_DoPaths();
+ /*
+ * Propagate attributes through :: dependency lists.
+ */
+ Targ_Propagate();
+
/* print the initial graph, if the user requested it */
if (DEBUG(GRAPH1))
Targ_PrintGraph(1);
diff -r b539998e5aca -r fa3a338606d5 usr.bin/make/make.c
--- a/usr.bin/make/make.c Wed Sep 15 10:25:30 1999 +0000
+++ b/usr.bin/make/make.c Wed Sep 15 10:47:37 1999 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: make.c,v 1.22 1998/11/11 19:37:06 christos Exp $ */
+/* $NetBSD: make.c,v 1.23 1999/09/15 10:47:38 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,14 +39,14 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: make.c,v 1.22 1998/11/11 19:37:06 christos Exp $";
+static char rcsid[] = "$NetBSD: make.c,v 1.23 1999/09/15 10:47:38 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)make.c 8.1 (Berkeley) 6/6/93";
#else
-__RCSID("$NetBSD: make.c,v 1.22 1998/11/11 19:37:06 christos Exp $");
+__RCSID("$NetBSD: make.c,v 1.23 1999/09/15 10:47:38 mycroft Exp $");
#endif
#endif /* not lint */
#endif
@@ -934,6 +934,13 @@
while (!Lst_IsEmpty (examine)) {
gn = (GNode *) Lst_DeQueue (examine);
+ if ((gn->type & OP_OPMASK) == OP_DOUBLEDEP) {
+ Lst new;
+ new = Lst_Duplicate (gn->cohorts, NOCOPY);
+ Lst_Concat (new, examine, LST_CONCLINK);
+ examine = new;
+ }
+
if ((gn->flags & REMAKE) == 0) {
gn->flags |= REMAKE;
numNodes++;
diff -r b539998e5aca -r fa3a338606d5 usr.bin/make/nonints.h
--- a/usr.bin/make/nonints.h Wed Sep 15 10:25:30 1999 +0000
+++ b/usr.bin/make/nonints.h Wed Sep 15 10:47:37 1999 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: nonints.h,v 1.17 1998/09/18 20:35:11 christos Exp $ */
+/* $NetBSD: nonints.h,v 1.18 1999/09/15 10:47:44 mycroft Exp $ */
/*-
* Copyright (c) 1988, 1989, 1990, 1993
@@ -131,6 +131,7 @@
char *Targ_FmtTime __P((time_t));
void Targ_PrintType __P((int));
void Targ_PrintGraph __P((int));
+void Targ_Propagate __P((void));
/* var.c */
void Var_Delete __P((char *, GNode *));
diff -r b539998e5aca -r fa3a338606d5 usr.bin/make/parse.c
--- a/usr.bin/make/parse.c Wed Sep 15 10:25:30 1999 +0000
+++ b/usr.bin/make/parse.c Wed Sep 15 10:47:37 1999 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: parse.c,v 1.45 1999/09/15 08:43:22 mycroft Exp $ */
+/* $NetBSD: parse.c,v 1.46 1999/09/15 10:47:44 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,14 +39,14 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: parse.c,v 1.45 1999/09/15 08:43:22 mycroft Exp $";
+static char rcsid[] = "$NetBSD: parse.c,v 1.46 1999/09/15 10:47:44 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)parse.c 8.3 (Berkeley) 3/19/94";
#else
-__RCSID("$NetBSD: parse.c,v 1.45 1999/09/15 08:43:22 mycroft Exp $");
+__RCSID("$NetBSD: parse.c,v 1.46 1999/09/15 10:47:44 mycroft Exp $");
#endif
#endif /* not lint */
#endif
@@ -437,6 +437,8 @@
{
GNode *pgn = (GNode *) pgnp;
GNode *cgn = (GNode *) cgnp;
+ if ((pgn->type & OP_OPMASK) == OP_DOUBLEDEP && !Lst_IsEmpty (pgn->cohorts))
+ pgn = (GNode *) Lst_Datum (Lst_Last (pgn->cohorts));
if (Lst_Member (pgn->children, (ClientData)cgn) == NILLNODE) {
(void)Lst_AtEnd (pgn->children, (ClientData)cgn);
if (specType == Not) {
@@ -493,45 +495,31 @@
* instance.
*/
register GNode *cohort;
- LstNode ln;
/*
- * Make sure the copied bits apply to all previous cohorts.
+ * Propagate copied bits to the initial node. They'll be propagated
+ * back to the rest of the cohorts later.
*/
- for (ln = Lst_First(gn->cohorts); ln != NILLNODE; ln = Lst_Succ(ln)) {
- cohort = (GNode *)Lst_Datum(ln);
-
- cohort->type |= op & OP_PHONY;
- }
+ gn->type |= op & ~OP_OPMASK;
cohort = Targ_NewGN(gn->name);
/*
- * Duplicate links to parents so graph traversal is simple. Perhaps
- * some type bits should be duplicated?
- *
* Make the cohort invisible as well to avoid duplicating it into
* other variables. True, parents of this target won't tend to do
* anything with their local variables, but better safe than
- * sorry.
- */
- Lst_ForEach(gn->parents, ParseLinkSrc, (ClientData)cohort);
- cohort->type = OP_DOUBLEDEP|OP_INVISIBLE|(gn->type & OP_PHONY);
- (void)Lst_AtEnd(gn->cohorts, (ClientData)cohort);
-
- /*
- * Replace the node in the targets list with the new copy
+ * sorry. (I think this is pointless now, since the relevant list
+ * traversals will no longer see this node anyway. -mycroft)
*/
- ln = Lst_Member(targets, (ClientData)gn);
- Lst_Replace(ln, (ClientData)cohort);
- gn = cohort;
+ cohort->type = op | OP_INVISIBLE;
+ (void)Lst_AtEnd(gn->cohorts, (ClientData)cohort);
+ } else {
+ /*
+ * We don't want to nuke any previous flags (whatever they were) so we
+ * just OR the new operator into the old
+ */
+ gn->type |= op;
}
- /*
- * We don't want to nuke any previous flags (whatever they were) so we
- * just OR the new operator into the old
- */
- gn->type |= op;
-
return (0);
}
@@ -667,19 +655,6 @@
} else {
Lst_ForEach (targets, ParseLinkSrc, (ClientData)gn);
}
- if ((gn->type & OP_OPMASK) == OP_DOUBLEDEP) {
- register GNode *cohort;
- register LstNode ln;
-
- for (ln=Lst_First(gn->cohorts); ln != NILLNODE; ln = Lst_Succ(ln)){
- cohort = (GNode *)Lst_Datum(ln);
- if (tOp) {
- cohort->type |= tOp;
- } else {
- Lst_ForEach(targets, ParseLinkSrc, (ClientData)cohort);
- }
- }
- }
break;
}
@@ -1586,6 +1561,8 @@
{
GNode *gn = (GNode *) gnp;
/* if target already supplied, ignore commands */
+ if ((gn->type & OP_OPMASK) == OP_DOUBLEDEP && !Lst_IsEmpty (gn->cohorts))
+ gn = (GNode *) Lst_Datum (Lst_Last (gn->cohorts));
if (!(gn->type & OP_HAS_COMMANDS))
(void)Lst_AtEnd(gn->commands, cmd);
return(0);
diff -r b539998e5aca -r fa3a338606d5 usr.bin/make/suff.c
--- a/usr.bin/make/suff.c Wed Sep 15 10:25:30 1999 +0000
+++ b/usr.bin/make/suff.c Wed Sep 15 10:47:37 1999 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: suff.c,v 1.25 1999/09/15 08:43:22 mycroft Exp $ */
+/* $NetBSD: suff.c,v 1.26 1999/09/15 10:47:44 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,14 +39,14 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: suff.c,v 1.25 1999/09/15 08:43:22 mycroft Exp $";
+static char rcsid[] = "$NetBSD: suff.c,v 1.26 1999/09/15 10:47:44 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
#if 0
static char sccsid[] = "@(#)suff.c 8.4 (Berkeley) 3/21/94";
#else
-__RCSID("$NetBSD: suff.c,v 1.25 1999/09/15 08:43:22 mycroft Exp $");
+__RCSID("$NetBSD: suff.c,v 1.26 1999/09/15 10:47:44 mycroft Exp $");
#endif
#endif /* not lint */
#endif
@@ -706,6 +706,8 @@
{
GNode *gn = (GNode *) gnp;
+ if ((gn->type & OP_OPMASK) == OP_DOUBLEDEP && !Lst_IsEmpty (gn->cohorts))
+ gn = (GNode *) Lst_Datum (Lst_Last (gn->cohorts));
if ((gn->type & OP_TRANSFORM) && Lst_IsEmpty(gn->commands) &&
Lst_IsEmpty(gn->children))
{
@@ -1688,27 +1690,6 @@
tGn->unmade += 1;
}
- if ((sGn->type & OP_OPMASK) == OP_DOUBLEDEP) {
- /*
- * When a :: node is used as the implied source of a node, we have
- * to link all its cohorts in as sources as well. Only the initial
- * sGn gets the target in its iParents list, however, as that
- * will be sufficient to get the .IMPSRC variable set for tGn
- */
- for (ln=Lst_First(sGn->cohorts); ln != NILLNODE; ln=Lst_Succ(ln)) {
- gn = (GNode *)Lst_Datum(ln);
-
- if (Lst_Member(tGn->children, (ClientData)gn) == NILLNODE) {
- /*
- * Not already linked, so form the proper links between the
- * target and source.
- */
- (void)Lst_AtEnd(tGn->children, (ClientData)gn);
- (void)Lst_AtEnd(gn->parents, (ClientData)tGn);
- tGn->unmade += 1;
- }
- }
- }
/*
* Locate the transformation rule itself
*/
diff -r b539998e5aca -r fa3a338606d5 usr.bin/make/targ.c
--- a/usr.bin/make/targ.c Wed Sep 15 10:25:30 1999 +0000
+++ b/usr.bin/make/targ.c Wed Sep 15 10:47:37 1999 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: targ.c,v 1.18 1999/09/15 08:43:22 mycroft Exp $ */
+/* $NetBSD: targ.c,v 1.19 1999/09/15 10:47:45 mycroft Exp $ */
/*
* Copyright (c) 1988, 1989, 1990, 1993
@@ -39,14 +39,14 @@
*/
#ifdef MAKE_BOOTSTRAP
-static char rcsid[] = "$NetBSD: targ.c,v 1.18 1999/09/15 08:43:22 mycroft Exp $";
+static char rcsid[] = "$NetBSD: targ.c,v 1.19 1999/09/15 10:47:45 mycroft Exp $";
#else
#include <sys/cdefs.h>
#ifndef lint
Home |
Main Index |
Thread Index |
Old Index