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

[Sergei Trofimovich]

On Sat, 05 Feb 2022 18:39:41 -0500
Paul Smith <psmith@gnu.org> wrote:

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

Sounds good. Will start adding the 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?

Just a bug. I misinterpreted the 'toenv' meaning.

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

Will do. I tried on 100 simple packages, but most of them are resursive
makefiles (which I missed): 'toenv = 0' effectively disabled the option
very early. Will try a few crafted inputs and handpick projects with
handwritten build systems.

> 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

Just to clarify for myself: I agree changing the order of MAKECMDGOALS is
unexpected and harmful as it's observable in rules definitions (like
'echo $MAKECMDGOALS'). But I also think reordering rule execution should
be fine as it would be close to effect of -j in:

    make -j clean all install

Does it sound about right? Or there is some subtler difference between goal
order and prerequisite order treatment?

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

Oh, I did not realize prerequisite reordering completely breaks rule
definitions! That makes sense.

I'll spend some time to understand where I can plug in to reshuffle
schedulable queue instead.

Ideally I would like to preserve the order of execution across
incremental runs of:

    make --shuffle=$seed foo
    make --shuffle=$seed foo

but was afraid of the change of already satisfied prerequisites. Might
have to abandon the ideal for simplest first implementation.

Thank you for the detailed comment!

-- 

  Sergei