[SV 62100] Add '--shuffle' option support

Introduce non-deterministic ordering into goal and prerequisite
traversal to help tease out inconsistent failures that may happen
when running in parallel build mode.

Introduce second order into each dependency chain:
1. Existing order is syntactic order reachable via 'dep->next'
2. New order is shuffled order stored as 'dep->shuf' in each 'dep'

When updating goals and prerequisites and '--shuffle' is provided,
use the shuffled order to walk the graph.  When automatic variable
are set always use the syntactic order of parameters.

* Makefile.am: Add new src/shuffle.c and src/shuffle.h file.
* build_w32.bat: Ditto.
* builddos.bat: Ditto.
* makefile.com: Ditto.
* po/POTFILES.in: Ditto.
* doc/make.texi: Add documentation for --shuffle.
* doc/make.1: Ditto.
* src/dep.h (DEP): Add the shuf pointer.
* src/filedef.h (struct file): Add was_shuffled flag.
* src/main.c: (shuffle_mode): Global flag for the shuffle mode.
(usage): Add the --shuffle option.
(switches): Ditto.
(main): Set shuffle_mode based on the command line parameter.
Reshuffle prerequisites if requested.
* src/remake.c (update_goal_chain): Walk the shuffled list if enabled.
(update_file_1): Ditto.
* src/shuffle.h: Provide an interface for shuffling prerequisites.
* src/shuffle.c: Implement option parsing and prerequisite shuffling.
* tests/scripts/options/shuffle: Test shuffle option and modes.

18 files changed, 591 insertions, 74 deletions

diff --git a/AUTHORS b/AUTHORS
index 12b9d19f..35719b99 100644
--- a/AUTHORS
+++ b/AUTHORS
@@ -90,6 +90,7 @@ Other contributors:
   Carl Staelin (Princeton University)
   Ian Stewartson (Data Logic Limited)
   Tobias Stoeckmann <tobias@stoeckmann.org>
+  Sergei Trofimovich <siarheit@google.com>
   Marc Ullman <marc@mathworks.com>
   Christof Warlich <cwarlich@gmx.de>
   Florian Weimer <fweimer@redhat.com>
diff --git a/Makefile.am b/Makefile.am
index 8ddfc0e6..1e7d0e3c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -35,8 +35,9 @@ make_SRCS =	src/ar.c src/arscan.c src/commands.c src/commands.h \
 		src/hash.c src/hash.h src/implicit.c src/job.c src/job.h \
 		src/load.c src/loadapi.c src/main.c src/makeint.h src/misc.c \
 		src/os.h src/output.c src/output.h src/read.c src/remake.c \
-		src/rule.c src/rule.h src/signame.c src/strcache.c \
-		src/variable.c src/variable.h src/version.c src/vpath.c
+		src/rule.c src/rule.h src/shuffle.h src/shuffle.c \
+		src/signame.c src/strcache.c src/variable.c src/variable.h \
+		src/version.c src/vpath.c
 
 w32_SRCS =	src/w32/pathstuff.c src/w32/w32os.c src/w32/compat/dirent.c \
 		src/w32/compat/posixfcn.c src/w32/include/dirent.h \
diff --git a/NEWS b/NEWS
index 169a7846..f555a0d7 100644
--- a/NEWS
+++ b/NEWS
@@ -61,6 +61,13 @@ https://sv.gnu.org/bugs/index.php?group=make&report_id=111&fix_release_id=109&se
   avoiding the need for heuristics.
   Implementation provided by Sven C. Dack <sdack@gmx.com>
 
+* New feature: The --shuffle command line option
+  This option reorders goals and prerequisites to simulate non-determinism
+  that may be seen using parallel build.  Shuffle mode allows a form of "fuzz
+  testing" of parallel builds to verify that all prerequisites are correctly
+  described in the makefile.
+  Implementation provided by Sergei Trofimovich <siarheit@google.com>
+
 * GNU make has sometimes chosen unexpected, and sub-optimal, chains of
   implicit rules due to the definition of "ought to exist" in the implicit
   rule search algorithm, which considered any prerequisite mentioned in the
diff --git a/build_w32.bat b/build_w32.bat
index 653841d7..c464e26d 100755
--- a/build_w32.bat
+++ b/build_w32.bat
@@ -257,6 +257,7 @@ call :Compile src/read
 call :Compile src/remake

 call :Compile src/remote-stub

 call :Compile src/rule

+call :Compile src/shuffle

 call :Compile src/signame

 call :Compile src/strcache

 call :Compile src/variable

diff --git a/builddos.bat b/builddos.bat
index 2b3de301..d4ff8a63 100644
--- a/builddos.bat
+++ b/builddos.bat
@@ -68,12 +68,13 @@ gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/s
 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/remote-stub.c -o remote-stub.o

 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/getopt.c -o getopt.o

 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/getopt1.c -o getopt1.o

+gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/src/shuffle.c -o shuffle.o

 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/lib/glob.c -o lib/glob.o

 gcc -c -I./src -I%XSRC%/src -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/lib/fnmatch.c -o lib/fnmatch.o

 @echo off

 echo commands.o > respf.$$$

 for %%f in (job output dir file misc main read remake rule implicit default variable) do echo %%f.o >> respf.$$$

-for %%f in (expand function vpath hash strcache version ar arscan signame remote-stub getopt getopt1) do echo %%f.o >> respf.$$$

+for %%f in (expand function vpath hash strcache version ar arscan signame remote-stub getopt getopt1 shuffle) do echo %%f.o >> respf.$$$

 for %%f in (lib\glob lib\fnmatch) do echo %%f.o >> respf.$$$

 rem gcc  -c -I./src -I%XSRC% -I./lib -I%XSRC%/lib -DHAVE_CONFIG_H -O2 -g %XSRC%/guile.c -o guile.o

 rem echo guile.o >> respf.$$$

diff --git a/doc/make.1 b/doc/make.1
index ec6f8a3b..33058f08 100644
--- a/doc/make.1
+++ b/doc/make.1
@@ -1,4 +1,4 @@
-.TH MAKE 1 "28 February 2016" "GNU" "User Commands"
+.TH MAKE 1 "31 May 2022" "GNU" "User Commands"
 .SH NAME
 make \- GNU make utility to maintain groups of programs
 .SH SYNOPSIS
@@ -319,6 +319,26 @@ Turn off
 .BR \-w ,
 even if it was turned on implicitly.
 .TP 0.5i
+.BI \-\-shuffle "[=MODE]"
+Enable shuffling of goal and prerequisite ordering.
+.I MODE
+is one of
+.I none
+to disable shuffle mode,
+.I random
+to shuffle prerequisites in random order,
+.I reverse
+to consider prerequisites in reverse order, or an integer
+.I <seed>
+which enables
+.I random
+mode with a specific
+.I seed
+value.  If
+.I MODE
+is omitted the default is
+.IR random .
+.TP 0.5i
 \fB\-W\fR \fIfile\fR, \fB\-\-what\-if\fR=\fIfile\fR, \fB\-\-new\-file\fR=\fIfile\fR, \fB\-\-assume\-new\fR=\fIfile\fR
 Pretend that the target
 .I file
diff --git a/doc/make.texi b/doc/make.texi
index 8505e8d6..943c0941 100644
--- a/doc/make.texi
+++ b/doc/make.texi
@@ -9422,6 +9422,45 @@ from the top-level @code{make} via @code{MAKEFLAGS}
 (@pxref{Recursion, ,Recursive Use of @code{make}})
 or if you set @samp{-k} in @code{MAKEFLAGS} in your environment.@refill
 
+@item --shuffle[=@var{mode}]
+@cindex @code{--shuffle}
+@c Extra blank line here makes the table look better.
+
+This option enables a form of fuzz-testing of prerequisite relationships.
+When parallelism is enabled (@samp{-j}) the order in which targets are
+built becomes less deterministic.  If prerequisites are not fully declared
+in the makefile this can lead to intermittent and hard-to-track-down build
+failures.
+
+The @samp{--shuffle} option forces @code{make} to purposefully reorder goals
+and prerequisites so target/prerequisite relationships still hold, but
+ordering of prerequisites of a given target are reordered as described below.
+
+The order in which prerequisites are listed in automatic variables is not
+changed by this option.
+
+The @code{.NOTPARALLEL} pseudo-target disables shuffling for that makefile.
+
+The @samp{--shuffle=} option accepts these values:
+
+@table @code
+@item random
+Choose a random seed for the shuffle.  This is the default if no mode is
+specified.  The chosen seed is also provided to sub-@code{make} commands.  The
+seed is included in error messages so that it can be re-used in future runs to
+reproduce the problem or verify that it has been resolved.
+
+@item reverse
+Reverse the order of goals and prerequisites, rather than a random shuffle.
+
+@item @var{seed}
+Use @samp{random} shuffle initialized with the specified seed value.  The
+@var{seed} is an integer.
+
+@item none
+Disable shuffling.  This negates any previous @samp{--shuffle} options.
+@end table
+
 @item -t
 @cindex @code{-t}
 @itemx --touch
diff --git a/makefile.com b/makefile.com
index 4a36a354..86da500c 100644
--- a/makefile.com
+++ b/makefile.com
@@ -76,7 +76,7 @@ $ filelist = "[.src]ar [.src]arscan [.src]commands [.src]default [.src]dir " + -
              "[.src]hash [.src]implicit [.src]job [.src]load [.src]main " + -
              "[.src]misc [.src]read [.src]remake [.src]remote-stub " + -
              "[.src]rule [.src]output [.src]signame [.src]variable " + -
-             "[.src]version [.src]strcache [.src]vpath " + -
+             "[.src]version [.src]shuffle [.src]strcache [.src]vpath " + -
              "[.src]vmsfunctions [.src]vmsify [.src]vms_progname " + -
              "[.src]vms_exit [.src]vms_export_symbol " + -
              "[.lib]alloca [.lib]fnmatch [.lib]glob [.src]getopt1 [.src]getopt"
diff --git a/po/POTFILES.in b/po/POTFILES.in
index e163a058..16cfbdd9 100644
--- a/po/POTFILES.in
+++ b/po/POTFILES.in
@@ -37,6 +37,7 @@ src/read.c
 src/remake.c
 src/remote-cstms.c
 src/rule.c
+src/shuffle.c
 src/signame.c
 src/strcache.c
 src/variable.c
diff --git a/src/dep.h b/src/dep.h
index fdd3fa30..80092076 100644
--- a/src/dep.h
+++ b/src/dep.h
@@ -46,6 +46,7 @@ struct nameseq
 #define DEP(_t)                                 \
     NAMESEQ (_t);                               \
     struct file *file;                          \
+    _t *shuf;                                   \
     const char *stem;                           \
     unsigned int flags : 8;                     \
     unsigned int changed : 1;                   \
diff --git a/src/filedef.h b/src/filedef.h
index 392988e4..4330d787 100644
--- a/src/filedef.h
+++ b/src/filedef.h
@@ -108,6 +108,8 @@ struct file
                                    pattern-specific variables.  */
     unsigned int no_diag:1;     /* True if the file failed to update and no
                                    diagnostics has been issued (dontcare). */
+    unsigned int was_shuffled:1; /* Did we already shuffle 'deps'? used when
+                                    --shuffle passes through the graph.  */
   };
 
 
diff --git a/src/implicit.c b/src/implicit.c
index 9aee7db5..a89994b9 100644
--- a/src/implicit.c
+++ b/src/implicit.c
@@ -22,6 +22,7 @@ this program.  If not, see <http://www.gnu.org/licenses/>.  */
 #include "variable.h"
 #include "job.h"      /* struct child, used inside commands.h */
 #include "commands.h" /* set_file_variables */
+#include "shuffle.h"
 #include <assert.h>
 
 static int pattern_search (struct file *file, int archive,
@@ -1053,8 +1054,14 @@ pattern_search (struct file *file, int archive,
 
       dep->next = file->deps;
       file->deps = dep;
+
+      /* The file changed its dependencies; schedule the shuffle.  */
+      file->was_shuffled = 0;
     }
 
+  if (!file->was_shuffled)
+    shuffle_deps_recursive (file->deps);
+
   if (!tryrules[foundrule].checked_lastslash)
     {
       /* Always allocate new storage, since STEM might be on the stack for an
diff --git a/src/job.c b/src/job.c
index d24288ac..80d261bb 100644
--- a/src/job.c
+++ b/src/job.c
@@ -25,6 +25,8 @@ this program.  If not, see <http://www.gnu.org/licenses/>.  */
 #include "commands.h"
 #include "variable.h"
 #include "os.h"
+#include "dep.h"
+#include "shuffle.h"
 
 /* Default shell to use.  */
 #ifdef WINDOWS32
@@ -539,6 +541,7 @@ child_error (struct child *child,
   const struct file *f = child->file;
   const floc *flocp = &f->cmds->fileinfo;
   const char *nm;
+  const char *smode;
   size_t l;
 
   if (ignored && run_silent)
@@ -564,18 +567,29 @@ child_error (struct child *child,
 
   l = strlen (pre) + strlen (nm) + strlen (f->name) + strlen (post);
 
+  smode = shuffle_get_mode ();
+  if (smode)
+    {
+#define SHUFFLE_PREFIX " shuffle="
+      char *a = alloca (CSTRLEN(SHUFFLE_PREFIX) + strlen (smode) + 1);
+      sprintf (a, SHUFFLE_PREFIX "%s", smode);
+      smode = a;
+      l += strlen (smode);
+#undef SHUFFLE_PREFIX
+    }
+
   OUTPUT_SET (&child->output);
 
   show_goal_error ();
 
   if (exit_sig == 0)
-    error (NILF, l + INTSTR_LENGTH,
-           _("%s[%s: %s] Error %d%s"), pre, nm, f->name, exit_code, post);
+    error (NILF, l + INTSTR_LENGTH, _("%s[%s: %s] Error %d%s%s"),
+           pre, nm, f->name, exit_code, post, smode ? smode : "");
   else
     {
       const char *s = strsignal (exit_sig);
-      error (NILF, l + strlen (s) + strlen (dump),
-             "%s[%s: %s] %s%s%s", pre, nm, f->name, s, dump, post);
+      error (NILF, l + strlen (s) + strlen (dump), "%s[%s: %s] %s%s%s%s",
+             pre, nm, f->name, s, dump, post, smode ? smode : "");
     }
 
   OUTPUT_UNSET ();
diff --git a/src/main.c b/src/main.c
index 0d2dff72..5912b06c 100644
--- a/src/main.c
+++ b/src/main.c
@@ -24,6 +24,7 @@ this program.  If not, see <http://www.gnu.org/licenses/>.  */
 #include "rule.h"
 #include "debug.h"
 #include "getopt.h"
+#include "shuffle.h"
 
 #include <assert.h>
 #ifdef _AMIGA
@@ -233,6 +234,10 @@ static const int inf_jobs = 0;
 
 static char *jobserver_auth = NULL;
 
+/* Shuffle mode for goals and prerequisites.  */
+
+static char *shuffle_mode = NULL;
+
 /* Handle for the mutex used on Windows to synchronize output of our
    children under -O.  */
 
@@ -361,6 +366,9 @@ static const char *const usage[] =
     N_("\
   -R, --no-builtin-variables  Disable the built-in variable settings.\n"),
     N_("\
+  --shuffle[={SEED|random|reverse|none}]\n\
+                              Perform shuffle of prerequisites and goals.\n"),
+    N_("\
   -s, --silent, --quiet       Don't echo recipes.\n"),
     N_("\
   --no-silent                 Echo recipes (disable --silent mode).\n"),
@@ -479,6 +487,7 @@ static const struct command_switch switches[] =
     { CHAR_MAX+9, string, &jobserver_auth, 1, 0, 0, 0, 0, "jobserver-fds" },
     /* There is special-case handling for this in decode_switches() as well.  */
     { TEMP_STDIN_OPT, filename, &makefiles, 0, 0, 0, 0, 0, "temp-stdin" },
+    { CHAR_MAX+11, string, &shuffle_mode, 1, 1, 0, "random", 0, "shuffle" },
     { 0, 0, 0, 0, 0, 0, 0, 0, 0 }
   };
 
@@ -1504,6 +1513,22 @@ main (int argc, char **argv, char **envp)
       arg_job_slots = env_slots;
   }
 
+  /* Handle shuffle mode argument.  */
+  if (shuffle_mode)
+    {
+      const char *effective_mode;
+      shuffle_set_mode (shuffle_mode);
+
+      /* Write fixed seed back to argument list to propagate mode and
+         fixed seed to child $(MAKE) runs.  */
+      free (shuffle_mode);
+      effective_mode = shuffle_get_mode ();
+      if (effective_mode)
+        shuffle_mode = xstrdup (effective_mode);
+      else
+        shuffle_mode = NULL;
+    }
+
   /* Set a variable specifying whether stdout/stdin is hooked to a TTY.  */
 #ifdef HAVE_ISATTY
   if (isatty (fileno (stdout)))
@@ -2759,6 +2784,10 @@ main (int argc, char **argv, char **envp)
       O (fatal, NILF, _("No targets specified and no makefile found"));
     }
 
+  /* Shuffle prerequisites to catch makefiles with incomplete depends. */
+
+  shuffle_goaldeps_recursive (goals);
+
   /* Update the goals.  */
 
   DB (DB_BASIC, (_("Updating goal targets....\n")));
diff --git a/src/remake.c b/src/remake.c
index 09cfb8ca..2930a5bb 100644
--- a/src/remake.c
+++ b/src/remake.c
@@ -93,8 +93,8 @@ update_goal_chain (struct goaldep *goaldeps)
   enum update_status status = us_none;
 
   /* Duplicate the chain so we can remove things from it.  */
-
-  struct dep *goals = copy_dep_chain ((struct dep *)goaldeps);
+  struct dep *goals_orig = copy_dep_chain ((struct dep *)goaldeps);
+  struct dep *goals = goals_orig;
 
   goal_list = rebuilding_makefiles ? goaldeps : NULL;
 
@@ -108,7 +108,7 @@ update_goal_chain (struct goaldep *goaldeps)
 
   while (goals != 0)
     {
-      struct dep *g, *lastgoal;
+      struct dep *gu, *g, *lastgoal;
 
       /* Start jobs that are waiting for the load to go down.  */
 
@@ -119,13 +119,15 @@ update_goal_chain (struct goaldep *goaldeps)
       reap_children (1, 0);
 
       lastgoal = 0;
-      g = goals;
-      while (g != 0)
+      gu = goals;
+      while (gu != 0)
         {
           /* Iterate over all double-colon entries for this file.  */
           struct file *file;
           int stop = 0, any_not_updated = 0;
 
+          g = gu->shuf ? gu->shuf : gu;
+
           goal_dep = g;
 
           for (file = g->file->double_colon ? g->file->double_colon : g->file;
@@ -235,31 +237,30 @@ update_goal_chain (struct goaldep *goaldeps)
 
               /* This goal is finished.  Remove it from the chain.  */
               if (lastgoal == 0)
-                goals = g->next;
+                goals = gu->next;
               else
-                lastgoal->next = g->next;
-
-              /* Free the storage.  */
-              free (g);
+                lastgoal->next = gu->next;
 
-              g = lastgoal == 0 ? goals : lastgoal->next;
+              gu = lastgoal == 0 ? goals : lastgoal->next;
 
               if (stop)
                 break;
             }
           else
             {
-              lastgoal = g;
-              g = g->next;
+              lastgoal = gu;
+              gu = gu->next;
             }
         }
 
       /* If we reached the end of the dependency graph update CONSIDERED
          for the next pass.  */
-      if (g == 0)
+      if (gu == 0)
         ++considered;
     }
 
+  free_dep_chain (goals_orig);
+
   if (rebuilding_makefiles)
     {
       touch_flag = t;
@@ -424,7 +425,7 @@ update_file_1 (struct file *file, unsigned int depth)
   FILE_TIMESTAMP this_mtime;
   int noexist, must_make, deps_changed;
   struct file *ofile;
-  struct dep *d, *ad;
+  struct dep *du, *d, *ad;
   struct dep amake;
   int running = 0;
 
@@ -532,16 +533,18 @@ update_file_1 (struct file *file, unsigned int depth)
       struct dep *lastd = 0;
 
       /* Find the deps we're scanning */
-      d = ad->file->deps;
+      du = ad->file->deps;
       ad = ad->next;
 
-      while (d)
+      while (du)
         {
           enum update_status new;
           FILE_TIMESTAMP mtime;
           int maybe_make;
           int dontcare = 0;
 
+          d = du->shuf ? du->shuf : du;
+
           check_renamed (d->file);
 
           mtime = file_mtime (d->file);
@@ -551,14 +554,16 @@ update_file_1 (struct file *file, unsigned int depth)
             {
               OSS (error, NILF, _("Circular %s <- %s dependency dropped."),
                    file->name, d->file->name);
+
               /* We cannot free D here because our the caller will still have
                  a reference to it when we were called recursively via
                  check_dep below.  */
               if (lastd == 0)
-                file->deps = d->next;
+                file->deps = du->next;
               else
-                lastd->next = d->next;
-              d = d->next;
+                lastd->next = du->next;
+
+              du = du->next;
               continue;
             }
 
@@ -607,8 +612,8 @@ update_file_1 (struct file *file, unsigned int depth)
             d->changed = ((file_mtime (d->file) != mtime)
                           || (mtime == NONEXISTENT_MTIME));
 
-          lastd = d;
-          d = d->next;
+          lastd = du;
+          du = du->next;
         }
     }
 
@@ -617,58 +622,61 @@ update_file_1 (struct file *file, unsigned int depth)
 
   if (must_make || always_make_flag)
     {
-      for (d = file->deps; d != 0; d = d->next)
-        if (d->file->intermediate)
-          {
-            enum update_status new;
-            int dontcare = 0;
+      for (du = file->deps; du != 0; du = du->next)
+        {
+          d = du->shuf ? du->shuf : du;
+          if (d->file->intermediate)
+            {
+              enum update_status new;
+              int dontcare = 0;
 
-            FILE_TIMESTAMP mtime = file_mtime (d->file);
-            check_renamed (d->file);
-            d->file->parent = file;
+              FILE_TIMESTAMP mtime = file_mtime (d->file);
+              check_renamed (d->file);
+              d->file->parent = file;
 
-            /* Inherit dontcare flag from our parent. */
-            if (rebuilding_makefiles)
-              {
-                dontcare = d->file->dontcare;
-                d->file->dontcare = file->dontcare;
-              }
+              /* Inherit dontcare flag from our parent. */
+              if (rebuilding_makefiles)
+                {
+                  dontcare = d->file->dontcare;
+                  d->file->dontcare = file->dontcare;
+                }
 
-            /* We may have already considered this file, when we didn't know
-               we'd need to update it.  Force update_file() to consider it and
-               not prune it.  */
-            d->file->considered = 0;
+              /* We may have already considered this file, when we didn't know
+                 we'd need to update it.  Force update_file() to consider it and
+                 not prune it.  */
+              d->file->considered = 0;
 
-            new = update_file (d->file, depth);
-            if (new > dep_status)
-              dep_status = new;
+              new = update_file (d->file, depth);
+              if (new > dep_status)
+                dep_status = new;
 
-            /* Restore original dontcare flag. */
-            if (rebuilding_makefiles)
-              d->file->dontcare = dontcare;
+              /* Restore original dontcare flag. */
+              if (rebuilding_makefiles)
+                d->file->dontcare = dontcare;
 
-            check_renamed (d->file);
+              check_renamed (d->file);
 
-            {
-              struct file *f = d->file;
-              if (f->double_colon)
-                f = f->double_colon;
-              do
-                {
-                  running |= (f->command_state == cs_running
-                              || f->command_state == cs_deps_running);
-                  f = f->prev;
-                }
-              while (f != 0);
-            }
+              {
+                struct file *f = d->file;
+                if (f->double_colon)
+                  f = f->double_colon;
+                do
+                  {
+                    running |= (f->command_state == cs_running
+                                || f->command_state == cs_deps_running);
+                    f = f->prev;
+                  }
+                while (f != 0);
+              }
 
-            if (dep_status && !keep_going_flag)
-              break;
+              if (dep_status && !keep_going_flag)
+                break;
 
-            if (!running)
-              d->changed = ((file->phony && file->cmds != 0)
-                            || file_mtime (d->file) != mtime);
-          }
+              if (!running)
+                d->changed = ((file->phony && file->cmds != 0)
+                              || file_mtime (d->file) != mtime);
+            }
+        }
     }
 
   finish_updating (file);
diff --git a/src/shuffle.c b/src/shuffle.c
new file mode 100644
index 00000000..ea6e836d
--- /dev/null
+++ b/src/shuffle.c
@@ -0,0 +1,240 @@
+/* Provide prerequisite shuffle support.
+Copyright (C) 2022 Free Software Foundation, Inc.
+This file is part of GNU Make.
+
+GNU Make is free software; you can redistribute it and/or modify it under the
+terms of the GNU General Public License as published by the Free Software
+Foundation; either version 3 of the License, or (at your option) any later
+version.
+
+GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+#include "makeint.h"
+
+#include "shuffle.h"
+
+#include "filedef.h"
+#include "dep.h"
+
+/* Supported shuffle modes.  */
+static void random_shuffle_array (void ** a, size_t len);
+static void reverse_shuffle_array (void ** a, size_t len);
+static void identity_shuffle_array (void ** a, size_t len);
+
+/* The way goals and rules are shuffled during update.  */
+enum shuffle_mode
+  {
+    /* No shuffle data is populated or used.  */
+    sm_none,
+    /* Random within dependency list.  */
+    sm_random,
+    /* Inverse order.  */
+    sm_reverse,
+    /* identity order. Differs from SM_NONE by explicitly populating
+       the traversal order.  */
+    sm_identity,
+  };
+
+/* Shuffle configuration.  */
+static struct
+  {
+    enum shuffle_mode mode;
+    unsigned int seed;
+    void (*shuffler) (void **a, size_t len);
+    char strval[INTSTR_LENGTH];
+  } config = { sm_none, 0, NULL, "" };
+
+/* Return string value of --shuffle= option passed.
+   If none was passed or --shuffle=none was used function
+   returns NULL.  */
+const char *
+shuffle_get_mode ()
+{
+  return config.strval[0] ? config.strval : NULL;
+}
+
+void
+shuffle_set_mode (const char *cmdarg)
+{
+  /* Parse supported '--shuffle' mode.  */
+  if (strcasecmp (cmdarg, "random") == 0)
+    {
+      config.mode = sm_random;
+      config.seed = (unsigned int) (time (NULL) ^ make_pid ());
+    }
+  else if (strcasecmp (cmdarg, "reverse") == 0)
+    config.mode = sm_reverse;
+  else if (strcasecmp (cmdarg, "identity") == 0)
+    config.mode = sm_identity;
+  else if (strcasecmp (cmdarg, "none") == 0)
+    config.mode = sm_none;
+  /* Assume explicit seed if starts from a digit.  */
+  else
+    {
+      const char *err;
+      config.mode = sm_random;
+      config.seed = make_toui (cmdarg, &err);
+
+      if (err)
+        {
+          OS (error, NILF, _("invalid shuffle mode: '%s'"), cmdarg);
+          die (MAKE_FAILURE);
+        }
+    }
+
+  switch (config.mode)
+    {
+    case sm_random:
+      config.shuffler = random_shuffle_array;
+      sprintf (config.strval, "%u", config.seed);
+      break;
+    case sm_reverse:
+      config.shuffler = reverse_shuffle_array;
+      strcpy (config.strval, "reverse");
+      break;
+    case sm_identity:
+      config.shuffler = identity_shuffle_array;
+      strcpy (config.strval, "identity");
+      break;
+    case sm_none:
+      config.strval[0] = '\0';
+      break;
+    }
+}
+
+/* Shuffle array elements using RAND().  */
+static void
+random_shuffle_array (void **a, size_t len)
+{
+  size_t i;
+  for (i = 0; i < len; i++)
+    {
+      void *t;
+
+      /* Pick random element and swap. */
+      unsigned int j = rand () % len;
+      if (i == j)
+        continue;
+
+      /* Swap. */
+      t = a[i];
+      a[i] = a[j];
+      a[j] = t;
+    }
+}
+
+/* Shuffle array elements using reverse order.  */
+static void
+reverse_shuffle_array (void **a, size_t len)
+{
+  size_t i;
+  for (i = 0; i < len / 2; i++)
+    {
+      void *t;
+
+      /* Pick mirror and swap. */
+      unsigned int j = len - 1 - i;
+
+      /* Swap. */
+      t = a[i];
+      a[i] = a[j];
+      a[j] = t;
+    }
+}
+
+/* Shuffle array elements using identity order.  */
+static void
+identity_shuffle_array (void **a UNUSED, size_t len UNUSED)
+{
+  /* No-op!  */
+}
+
+/* Shuffle list of dependencies by populating '->next'
+   field in each 'struct dep'.  */
+static void
+shuffle_deps (struct dep *deps)
+{
+  size_t ndeps = 0;
+  struct dep *dep;
+  void **da;
+  void **dp;
+
+  for (dep = deps; dep; dep = dep->next)
+    ndeps++;
+
+  if (ndeps == 0)
+    return;
+
+  /* Allocate array of all deps, store, shuffle, write back.  */
+  da = xmalloc (sizeof (struct dep *) * ndeps);
+
+  /* Store locally.  */
+  for (dep = deps, dp = da; dep; dep = dep->next, dp++)
+    *dp = dep;
+
+  /* Shuffle.  */
+  config.shuffler (da, ndeps);
+
+  /* Write back.  */
+  for (dep = deps, dp = da; dep; dep = dep->next, dp++)
+    dep->shuf = *dp;
+
+  free (da);
+}
+
+/* Shuffle 'deps' of each 'file' recursively.  */
+static void
+shuffle_file_deps_recursive (struct file *f)
+{
+  struct dep *dep;
+
+  /* Implicit rules do not always provide any depends.  */
+  if (!f)
+    return;
+
+  /* Avoid repeated shuffles and loops.  */
+  if (f->was_shuffled)
+    return;
+  f->was_shuffled = 1;
+
+  shuffle_deps (f->deps);
+
+  /* Shuffle dependencies. */
+  for (dep = f->deps; dep; dep = dep->next)
+    shuffle_file_deps_recursive (dep->file);
+}
+
+/* Shuffle goal dependencies first, then shuffle dependency list
+   of each file reachable from goaldep recursively.  Used by
+   --shuffle flag to introduce artificial non-determinism in build
+   order.  .*/
+
+void
+shuffle_deps_recursive (struct dep *deps)
+{
+  struct dep *dep;
+
+  /* Exit early if shuffling was not requested.  */
+  if (config.mode == sm_none)
+    return;
+
+  /* Do not reshuffle targets if Makefile is explicitly marked as
+     problematic for parallelism.  */
+  if (not_parallel)
+    return;
+
+  /* Set specific seed at the top level of recursion.  */
+  if (config.mode == sm_random)
+    srand (config.seed);
+
+  shuffle_deps (deps);
+
+  /* Shuffle dependencies. */
+  for (dep = deps; dep; dep = dep->next)
+    shuffle_file_deps_recursive (dep->file);
+}
diff --git a/src/shuffle.h b/src/shuffle.h
new file mode 100644
index 00000000..a3b275ec
--- /dev/null
+++ b/src/shuffle.h
@@ -0,0 +1,26 @@
+/* Declarations for target shuffling support.
+Copyright (C) 2022-2022 Free Software Foundation, Inc.
+This file is part of GNU Make.
+
+GNU Make is free software; you can redistribute it and/or modify it under the
+terms of the GNU General Public License as published by the Free Software
+Foundation; either version 3 of the License, or (at your option) any later
+version.
+
+GNU Make is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR
+A PARTICULAR PURPOSE.  See the GNU General Public License for more details.
+
+You should have received a copy of the GNU General Public License along with
+this program.  If not, see <http://www.gnu.org/licenses/>.  */
+
+struct dep;
+struct goaldep;
+
+void shuffle_set_mode (const char *cmdarg);
+const char * shuffle_get_mode ();
+void shuffle_deps_recursive (struct dep* g);
+
+#define shuffle_goaldeps_recursive(_g) do{              \
+        shuffle_deps_recursive ((struct dep *)_g);      \
+    } while(0)
diff --git a/tests/scripts/options/shuffle b/tests/scripts/options/shuffle
new file mode 100644
index 00000000..e037ed1a
--- /dev/null
+++ b/tests/scripts/options/shuffle
@@ -0,0 +1,119 @@
+#                                                                    -*-perl-*-
+
+$description = "Test the --shuffle option.";
+
+$details = "Verify that --shuffle has expected effect on target order and argument order.";
+
+#
+# Test --shuffle=random
+#
+
+# TEST 1: Fixed seed should yield the same order from run to run.
+
+$makefile = &get_tmpfile;
+
+open(MAKEFILE, "> $makefile");
+print MAKEFILE <<'EOF';
+# More target prerequisites lower collision chance in TEST 2
+all: a_ b_ c_ d_ e_ f_ g_ i_ j_ k_ l_
+%: ; echo $@
+EOF
+close(MAKEFILE);
+
+$log1 = &get_logfile;
+$log2 = &get_logfile;
+&run_make_with_options($makefile, "--shuffle=12345", $log1);
+&run_make_with_options($makefile, "--shuffle=12345", $log2);
+
+&compare_output(&read_file_into_string($log1), $log2);
+
+# TEST 2: Sequential runs should produce different orders.
+
+$log3 = &get_logfile;
+$log4 = &get_logfile;
+&run_make_with_options($makefile, "--shuffle", $log3);
+&run_make_with_options($makefile, "--shuffle", $log4);
+
+++$tests_run;
+if (&read_file_into_string($log3) ne &read_file_into_string($log4)) {
+  print "ok\n" if $debug;
+  ++$tests_passed;
+}
+
+#
+# Test --shuffle=reverse
+#
+
+run_make_test('
+%: ; @echo $@
+all: a b c
+',
+              '--shuffle=reverse', "c\nb\na\nall");
+
+run_make_test('
+%: ; @echo $@
+all: a b c
+',
+              '--shuffle=none', "a\nb\nc\nall");
+
+run_make_test('
+%: ; @echo $@
+all: a b c
+',
+              '--shuffle=identity', "a\nb\nc\nall");
+
+# Make sure prerequisites get reverse order and commands don't get affected.
+run_make_test('
+all: foo.o ; @echo $@
+%.o : %.c ; @echo cc -c -o $@ $<
+foo.o : foo.c foo.h bar.h baz.h
+%.h: ; @echo $@
+%.c: ; @echo $@
+',
+              '--shuffle=reverse',
+              "baz.h\nbar.h\nfoo.h\nfoo.c\ncc -c -o foo.o foo.c\nall");
+
+# Make sure pattern prerequisites get reverse order and commands don't get
+# affected.
+run_make_test('
+all: foo_ ; @echo $@
+foo%: arg%1 arg%2 arg%3 arg%4 ; @echo bld $@ $< $(word 3,$^) $(word 2,$^) $(word 4,$^)
+
+arg%: ; @echo $@
+',
+              '--shuffle=reverse',
+              "arg_4\narg_3\narg_2\narg_1\nbld foo_ arg_1 arg_3 arg_2 arg_4\nall");
+
+# Check if make can survive circular dependency.
+run_make_test('
+all: a_ b_ ; @echo $@
+%_: ; @echo $@
+
+a_: b_
+b_: a_
+',
+              '--shuffle=reverse', "#MAKE#: Circular a_ <- b_ dependency dropped.\na_\nb_\nall");
+
+# Check if order-only dependencies get reordered.
+run_make_test('
+all: a_ ; @echo $@
+%_: ; @echo $@
+a_: b_ c_ | d_ e_
+',
+              '--shuffle=reverse', "e_\nd_\nc_\nb_\na_\nall");
+
+# Check if goals are reordered.
+run_make_test('
+%_: ; @echo $@
+',
+              '--shuffle=reverse a_ b_ c_', "c_\nb_\na_");
+
+# .NOTPARALLEL should prevent reordering from happening.
+run_make_test('
+%_: ; @echo $@
+# disable shuffling
+.NOTPARALLEL:
+',
+              '--shuffle=reverse a_ b_ c_', "a_\nb_\nc_");
+
+1;