[src/trunk]: src/usr.bin/make make(1): add Lst_ForEachUntilConcurrent

[rillig <rillig%NetBSD.org@localhost>]

details:   https://anonhg.NetBSD.org/src/rev/1de0991561b2
branches:  trunk
changeset: 956144:1de0991561b2
user:      rillig <rillig%NetBSD.org@localhost>
date:      Thu Oct 22 21:27:24 2020 +0000

description:
make(1): add Lst_ForEachUntilConcurrent

Previously, Lst_ForEachUntil allowed the list to be modified while
iterating.  Almost none of the code needs this, and it's also confusing
for human readers.

None of the current unit tests makes use of this concurrent modification
right now, but that's not evidence enough.  Only 72% of the code are
covered by unit tests right now, and there are lots of edge cases
(whether intended or not) that are not covered by unit tests.

Therefore, all calls to Lst_ForEachUntil were changed to
Lst_ForEachUntilConcurrent and those that were obvious were changed
back.  The remaining calls probably don't need the concurrent
modification code, but that's not obvious from looking at the code.

diffstat:

 usr.bin/make/lst.c  |  23 ++++++++++++++++++++---
 usr.bin/make/lst.h  |   5 +++--
 usr.bin/make/make.c |  21 ++++++++++++---------
 usr.bin/make/suff.c |   6 +++---
 4 files changed, 38 insertions(+), 17 deletions(-)

diffs (171 lines):

diff -r 7e0bb293c36c -r 1de0991561b2 usr.bin/make/lst.c
--- a/usr.bin/make/lst.c        Thu Oct 22 20:18:20 2020 +0000
+++ b/usr.bin/make/lst.c        Thu Oct 22 21:27:24 2020 +0000
@@ -1,4 +1,4 @@
-/* $NetBSD: lst.c,v 1.81 2020/10/22 20:18:20 rillig Exp $ */
+/* $NetBSD: lst.c,v 1.82 2020/10/22 21:27:24 rillig Exp $ */
 
 /*
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -34,7 +34,7 @@
 
 #include "make.h"
 
-MAKE_RCSID("$NetBSD: lst.c,v 1.81 2020/10/22 20:18:20 rillig Exp $");
+MAKE_RCSID("$NetBSD: lst.c,v 1.82 2020/10/22 21:27:24 rillig Exp $");
 
 /* Allocate and initialize a list node.
  *
@@ -293,11 +293,28 @@
     return NULL;
 }
 
+/* Apply the given function to each element of the given list, until the
+ * function returns non-zero. During this iteration, the list must not be
+ * modified structurally. */
+int
+Lst_ForEachUntil(List *list, LstActionUntilProc proc, void *procData)
+{
+    ListNode *node;
+    int result = 0;
+
+    for (node = list->first; node != NULL; node = node->next) {
+       result = proc(node->datum, procData);
+       if (result != 0)
+           break;
+    }
+    return result;
+}
+
 /* Apply the given function to each element of the given list. The function
  * should return 0 if traversal should continue and non-zero if it should
  * abort. */
 int
-Lst_ForEachUntil(List *list, LstActionUntilProc proc, void *procData)
+Lst_ForEachUntilConcurrent(List *list, LstActionUntilProc proc, void *procData)
 {
     ListNode *tln = list->first;
     int result = 0;
diff -r 7e0bb293c36c -r 1de0991561b2 usr.bin/make/lst.h
--- a/usr.bin/make/lst.h        Thu Oct 22 20:18:20 2020 +0000
+++ b/usr.bin/make/lst.h        Thu Oct 22 21:27:24 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: lst.h,v 1.76 2020/10/22 20:18:20 rillig Exp $  */
+/*     $NetBSD: lst.h,v 1.77 2020/10/22 21:27:24 rillig Exp $  */
 
 /*
  * Copyright (c) 1988, 1989, 1990 The Regents of the University of California.
@@ -114,7 +114,7 @@
 typedef void LstFreeProc(void *);
 /* Return TRUE if the datum matches the args, for Lst_Find. */
 typedef Boolean LstFindProc(const void *datum, const void *args);
-/* An action for Lst_ForEachUntil. */
+/* An action for Lst_ForEachUntil and Lst_ForEachUntilConcurrent. */
 typedef int LstActionUntilProc(void *datum, void *args);
 
 /* Create or destroy a list */
@@ -167,6 +167,7 @@
 /* Apply a function to each datum of the list, until the callback function
  * returns non-zero. */
 int Lst_ForEachUntil(List *, LstActionUntilProc, void *);
+int Lst_ForEachUntilConcurrent(List *, LstActionUntilProc, void *);
 
 /* Iterating over a list while keeping track of the current node and possible
  * concurrent modifications */
diff -r 7e0bb293c36c -r 1de0991561b2 usr.bin/make/make.c
--- a/usr.bin/make/make.c       Thu Oct 22 20:18:20 2020 +0000
+++ b/usr.bin/make/make.c       Thu Oct 22 21:27:24 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: make.c,v 1.171 2020/10/22 20:09:07 rillig Exp $        */
+/*     $NetBSD: make.c,v 1.172 2020/10/22 21:27:24 rillig Exp $        */
 
 /*
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -107,7 +107,7 @@
 #include    "job.h"
 
 /*     "@(#)make.c     8.1 (Berkeley) 6/6/93"  */
-MAKE_RCSID("$NetBSD: make.c,v 1.171 2020/10/22 20:09:07 rillig Exp $");
+MAKE_RCSID("$NetBSD: make.c,v 1.172 2020/10/22 21:27:24 rillig Exp $");
 
 /* Sequence # to detect recursion. */
 static unsigned int checked = 1;
@@ -645,7 +645,8 @@
     parents = centurion->parents;
 
     /* If this was a .ORDER node, schedule the RHS */
-    Lst_ForEachUntil(centurion->order_succ, MakeBuildParent, toBeMade->first);
+    Lst_ForEachUntilConcurrent(centurion->order_succ,
+                              MakeBuildParent, toBeMade->first);
 
     /* Now mark all the parents as having one less unmade child */
     for (ln = parents->first; ln != NULL; ln = ln->next) {
@@ -751,9 +752,10 @@
 }
 
 /* Add a child's name to the ALLSRC and OODATE variables of the given
- * node. Called from Make_DoAllVar via Lst_ForEachUntil. A child is added only
- * if it has not been given the .EXEC, .USE or .INVISIBLE attributes.
- * .EXEC and .USE children are very rarely going to be files, so...
+ * node, but only if it has not been given the .EXEC, .USE or .INVISIBLE
+ * attributes. .EXEC and .USE children are very rarely going to be files,
+ * so...
+ *
  * If the child is a .JOIN node, its ALLSRC is propagated to the parent.
  *
  * A child is added to the OODATE variable if its modification time is
@@ -899,7 +901,7 @@
        Lst_InsertBefore(toBeMade, toBeMade_next, cn);
 
     if (cn->unmade_cohorts != 0)
-       Lst_ForEachUntil(cn->cohorts, MakeBuildChild, toBeMade_next);
+       Lst_ForEachUntilConcurrent(cn->cohorts, MakeBuildChild, toBeMade_next);
 
     /*
      * If this node is a .WAIT node with unmade children
@@ -966,7 +968,8 @@
             * just before the current first element.
             */
            gn->made = DEFERRED;
-           Lst_ForEachUntil(gn->children, MakeBuildChild, toBeMade->first);
+           Lst_ForEachUntilConcurrent(gn->children,
+                                      MakeBuildChild, toBeMade->first);
            /* and drop this node on the floor */
            DEBUG2(MAKE, "dropped %s%s\n", gn->name, gn->cohort_num);
            continue;
@@ -1163,7 +1166,7 @@
            Suff_FindDeps(gn);
        else {
            /* Pretend we made all this node's children */
-           Lst_ForEachUntil(gn->children, MakeFindChild, gn);
+           Lst_ForEachUntilConcurrent(gn->children, MakeFindChild, gn);
            if (gn->unmade != 0)
                    printf("Warning: %s%s still has %d unmade children\n",
                            gn->name, gn->cohort_num, gn->unmade);
diff -r 7e0bb293c36c -r 1de0991561b2 usr.bin/make/suff.c
--- a/usr.bin/make/suff.c       Thu Oct 22 20:18:20 2020 +0000
+++ b/usr.bin/make/suff.c       Thu Oct 22 21:27:24 2020 +0000
@@ -1,4 +1,4 @@
-/*     $NetBSD: suff.c,v 1.216 2020/10/22 19:30:37 rillig Exp $        */
+/*     $NetBSD: suff.c,v 1.217 2020/10/22 21:27:24 rillig Exp $        */
 
 /*
  * Copyright (c) 1988, 1989, 1990, 1993
@@ -129,7 +129,7 @@
 #include "dir.h"
 
 /*     "@(#)suff.c     8.4 (Berkeley) 3/21/94" */
-MAKE_RCSID("$NetBSD: suff.c,v 1.216 2020/10/22 19:30:37 rillig Exp $");
+MAKE_RCSID("$NetBSD: suff.c,v 1.217 2020/10/22 21:27:24 rillig Exp $");
 
 #define SUFF_DEBUG0(text) DEBUG0(SUFF, text)
 #define SUFF_DEBUG1(fmt, arg1) DEBUG1(SUFF, fmt, arg1)
@@ -592,7 +592,7 @@
     }
 }
 
-/* Called from Suff_AddSuffix via Lst_ForEachUntil to search through the list of
+/* Called from Suff_AddSuffix to search through the list of
  * existing transformation rules and rebuild the transformation graph when
  * it has been destroyed by Suff_ClearSuffixes. If the given rule is a
  * transformation involving this suffix and another, existing suffix, the