[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.

2 files changed, 60 insertions, 1 deletions

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