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

1 files changed, 2 insertions, 0 deletions

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.  */
   };