Re: [PATCH] RFC: add --shuffle[=seed] argument support

[Paul Smith]

Nice work!

On Sat, 2022-02-05 at 22:04 +0000, Sergei Trofimovich wrote:
> Some high level TODOs:

For this amount of change it's likely that you'll need to provide
copyright assignment paperwork.  Let me know if you'd like more details
about this.

> - No documentation for the optin yet.

This feature would also need a set of regression tests.

> - No(?) environment passing for recursive make.  I would prefer to
> share the same see across all calls to get easier reproducers.

You explicitly disabled this, though... was there a reason?

> - The dependency traversal is naive and uses potentially unbounded
> stack.
> - srand() / rand() is used from system libc.  This might make it
> harder to reproduce a failure on another machine.  But maybe it's
> fine.

There are a few issues here:

I recommend you try your version of GNU make on a bunch of different
real codebases and make sure it still works (and of course, create the
above-mentioned regression tests).

First, I think it's not correct to shuffle the goaldeps.  The goals
that are specified on the command line should always be invoked in the
order that the user requested.  It would be bad to convert:

  make clean all install

to:

  make install clean all

Second, you cannot rearrange the first prerequisite.  The first
prerequisite always must be placed in $<.  Consider the simple pattern
rule:

  %.o : %.c
          $(CC) $(CFLAGS) -c -o $@ $<

  foo.o: foo.c foo.h bar.h baz.h

If you rearrange the prerequisites to "bar.h foo.h foo.c baz.h" it will
not work well :).

Lastly, I'm not entirely sure that this is the best way to do the
shuffle.  Similar to my concern above about the first prerequisite,
this change will break makefiles that rely on the order of
prerequisites in perfectly legitimate ways; for example:

  foo%: arg%1 arg%2 arg%3 arg%4
          bld $< $(word 3,$^) $(word 2,$^) $(word 4,$^)

The concept you want to implement is not the shuffling of the actual
prerequisites, it's the shuffling of the BUILDING of the prerequisites.
The list of deps should not be modified but instead when make goes to
build the deps it should build them in a different order than they
appear in the prerequisites list.

Put another way, you don't want to change the structure of make's
dependency graph; you just want to change the order in which it's
walked.

If you do it this way you don't have to worry about any of the
reordering issues I raise above, because the values of $<, $^, etc.
won't change, and also you won't have to worry about deep recursions
etc. because you'll just be rearranging the targets that are being
built.

But, I think making it work this way will be trickier to code.