[PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Junio C Hamano]

Since 33533975 ("Makefile: ask "ls-files" to list source files if
available", 2011-10-18), we optionally asked "ls-files" to list the
source files that ought to exist, as a faster approximation for
"find" on working tree files.

This works reasonably well, except that it ends up listing the same
path multiple times if the index is unmerged.  Because the original
use of this construct was to name files to run etags over, and the
etags command happily takes the same filename multiple times without
causing any harm, there was no problem (other than perhaps spending
slightly more cycles, but who cares how fast the TAGS file gets
updated).

We however recently added a similar call to "ls-files" to list *.h
files, instead of using "find", in 92b88eba ("Makefile: use `git
ls-files` to list header files, if possible", 2019-03-04).  In this
new use of "ls-files", the resulting list $(LIB_H) is used for,
among other things, generating the header files to run hdr-check
target, and the duplicate unfortunately becomes a true problem.  It
causes $(MAKE) to notice that there are multiple %.hco targets and
complain.

Feed the resulting list to "| sort -u" before using it as a list of
files to fix this.

---

 * I very often have to (1) perform a merge, which conflicts, (2)
   manually resolve new conflicts that are yet unknown to the rerere
   database, (3) before running "git add", run a trial build and
   optionally test, and then (4) commit the result (or just say "git
   rerere" and then "git reset --hard").

   In the step (3), we have (hopefully) good *.h files that are the
   result of conflict resolution in the working tree, over which we
   do want to run header check, but the whole point of running a
   trial build is to validate the result, the resolution is not yet
   registered to the index (or to the rerere database).  These paths
   have multiple stages in the index, and that is when $(MAKE)
   complained to make me notice this buglet.

   I am not fan of adding the "| sort -u" of the whole thing,
   because there is no need to dedup the output of the $(FIND) side
   of the alternative, but "(ls-files | sort -u) || (find)" would
   obviously not work.  If we truly care, perhaps we should add a
   new option to ls-files to show each path only once, unless it is
   showing the stage number (i.e. "ls-files -s" or "ls-files -u"),
   but this gets the problem go away without code change, hence this
   RFC ;-)

diff --git a/Makefile b/Makefile
index 9f1b6e8926..40716c0f81 100644
--- a/Makefile
+++ b/Makefile
@@ -822,12 +822,12 @@ VCSSVN_LIB = vcs-svn/lib.a
 
 GENERATED_H += command-list.h
 
-LIB_H := $(shell git ls-files '*.h' ':!t/' ':!Documentation/' 2>/dev/null || \
+LIB_H := $(shell (git ls-files '*.h' ':!t/' ':!Documentation/' 2>/dev/null || \
 	$(FIND) . \
 	-name .git -prune -o \
 	-name t -prune -o \
 	-name Documentation -prune -o \
-	-name '*.h' -print)
+	-name '*.h' -print) | sort -u)
 
 LIB_OBJS += abspath.o
 LIB_OBJS += advice.o
@@ -2588,7 +2588,7 @@ FIND_SOURCE_FILES = ( \
 		-o \( -name 'trash*' -type d -prune \) \
 		-o \( -name '*.[hcS]' -type f -print \) \
 		-o \( -name '*.sh' -type f -print \) \
-	)
+	| sort -u )
 
 $(ETAGS_TARGET): FORCE
 	$(RM) $(ETAGS_TARGET)

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Eric Sunshine]

On Sun, Apr 21, 2019 at 9:19 AM Junio C Hamano <gitster@pobox.com> wrote:
> diff --git a/Makefile b/Makefile
> @@ -822,12 +822,12 @@ VCSSVN_LIB = vcs-svn/lib.a
> -LIB_H := $(shell git ls-files '*.h' ':!t/' ':!Documentation/' 2>/dev/null || \
> +LIB_H := $(shell (git ls-files '*.h' ':!t/' ':!Documentation/' 2>/dev/null || \
>         $(FIND) . \
>         -name .git -prune -o \
>         -name t -prune -o \
>         -name Documentation -prune -o \
> -       -name '*.h' -print)
> +       -name '*.h' -print) | sort -u)

GNU make's "sort" function also de-dups, so an alternative is:

    LIB_H := $(sort $(shell ...))

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Junio C Hamano]

Eric Sunshine <sunshine@sunshineco.com> writes:

> On Sun, Apr 21, 2019 at 9:19 AM Junio C Hamano <gitster@pobox.com> wrote:
>> diff --git a/Makefile b/Makefile
>> @@ -822,12 +822,12 @@ VCSSVN_LIB = vcs-svn/lib.a
>> -LIB_H := $(shell git ls-files '*.h' ':!t/' ':!Documentation/' 2>/dev/null || \
>> +LIB_H := $(shell (git ls-files '*.h' ':!t/' ':!Documentation/' 2>/dev/null || \
>>         $(FIND) . \
>>         -name .git -prune -o \
>>         -name t -prune -o \
>>         -name Documentation -prune -o \
>> -       -name '*.h' -print)
>> +       -name '*.h' -print) | sort -u)
>
> GNU make's "sort" function also de-dups, so an alternative is:
>
>     LIB_H := $(sort $(shell ...))

That is a much better solution.  Let me use that.

Thanks.

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Jeff King]

On Sun, Apr 21, 2019 at 10:19:04PM +0900, Junio C Hamano wrote:

>    I am not fan of adding the "| sort -u" of the whole thing,
>    because there is no need to dedup the output of the $(FIND) side
>    of the alternative, but "(ls-files | sort -u) || (find)" would
>    obviously not work.  If we truly care, perhaps we should add a
>    new option to ls-files to show each path only once, unless it is
>    showing the stage number (i.e. "ls-files -s" or "ls-files -u"),
>    but this gets the problem go away without code change, hence this
>    RFC ;-)

FWIW, after reading your commit message my thoughts immediately turned
to "why can't ls-files have a mode that outputs each just once", but
then ended up at the same place as your patch: it's not that hard to
just de-dup the output.

It _could_ be a sign that other scripts besides our Makefile would
benefit from such an option, but I think I'd want to see at least one
other example before going in that direction.

So the patch itself looks good to me (though I agree that Eric's
suggestion to de-dup inside "make" is better still).

-Peff

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Ramsay Jones]

On 22/04/2019 15:49, Jeff King wrote:
> On Sun, Apr 21, 2019 at 10:19:04PM +0900, Junio C Hamano wrote:
> 
>>    I am not fan of adding the "| sort -u" of the whole thing,
>>    because there is no need to dedup the output of the $(FIND) side
>>    of the alternative, but "(ls-files | sort -u) || (find)" would
>>    obviously not work.  If we truly care, perhaps we should add a
>>    new option to ls-files to show each path only once, unless it is
>>    showing the stage number (i.e. "ls-files -s" or "ls-files -u"),
>>    but this gets the problem go away without code change, hence this
>>    RFC ;-)
> 
> FWIW, after reading your commit message my thoughts immediately turned
> to "why can't ls-files have a mode that outputs each just once", but
> then ended up at the same place as your patch: it's not that hard to
> just de-dup the output.

My immediate thought was "that is simply a bug, no?" :-D

I haven't used 'git ls-files' that much, so it's no great surprise
that I had not noticed it odd behaviour!

So, this evening, I decided to have a little play:

  $ git status
  On branch master
  You have unmerged paths.
    (fix conflicts and run "git commit")
    (use "git merge --abort" to abort the merge)
  
  Changes to be committed:
  
  	new file:   d
  
  Unmerged paths:
    (use "git add <file>..." to mark resolution)
  
  	both modified:   a
  
  Changes not staged for commit:
    (use "git add/rm <file>..." to update what will be committed)
    (use "git checkout -- <file>..." to discard changes in working directory)
  
  	modified:   b
  	deleted:    c
  
  Untracked files:
    (use "git add <file>..." to include in what will be committed)
  
  	e
  
  $ git ls-files
  a
  a
  a
  b
  c
  d
  $ git ls-files -c
  a
  a
  a
  b
  c
  d
  $ git ls-files -m
  a
  a
  a
  b
  c
  $ git ls-files -d
  c
  $ git ls-files -u
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  $ git ls-files -s
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4f2e6529203aa6d44b5af6e3292c837ceda003f9 0	b
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  100644 72ad562535b8551cdd6659e8fb6c7cf6830e6a07 0	d
  $ git ls-files -sd
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4f2e6529203aa6d44b5af6e3292c837ceda003f9 0	b
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  100644 72ad562535b8551cdd6659e8fb6c7cf6830e6a07 0	d
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  $ git ls-files -su
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  $ git ls-files -sm
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4f2e6529203aa6d44b5af6e3292c837ceda003f9 0	b
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  100644 72ad562535b8551cdd6659e8fb6c7cf6830e6a07 0	d
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4f2e6529203aa6d44b5af6e3292c837ceda003f9 0	b
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  $ git ls-files -sdu
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  $ git ls-files -sdum
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4f2e6529203aa6d44b5af6e3292c837ceda003f9 0	b
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  $ git ls-files -sdumo
  e
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4ef30bbfe26431a69c3820d3a683df54d688f2ec 1	a
  100644 af72a79d2a6bd4b252b0aca22dba9946f7eedf86 2	a
  100644 f8829dfb9bf82721903d239ef069fb5de395f3e7 3	a
  100644 4f2e6529203aa6d44b5af6e3292c837ceda003f9 0	b
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  100644 a296d0bb611188cabb256919f36bc30117cca005 0	c
  $ 

Er, ... well, I obviously don't have a clue how it is supposed
to work. This just looks broken to me. :(

> So the patch itself looks good to me (though I agree that Eric's
> suggestion to de-dup inside "make" is better still).

Agreed.

ATB,
Ramsay Jones

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Junio C Hamano]

Ramsay Jones <ramsay@ramsayjones.plus.com> writes:

>> FWIW, after reading your commit message my thoughts immediately turned
>> to "why can't ls-files have a mode that outputs each just once", but
>> then ended up at the same place as your patch: it's not that hard to
>> just de-dup the output.
>
> My immediate thought was "that is simply a bug, no?" :-D
>
> I haven't used 'git ls-files' that much, so it's no great surprise
> that I had not noticed it odd behaviour!

Yup, the real issue is that ls-files uses exactly the same code for
tagged output, output with stage numbers and just plain list of
paths, so as we saw in the motivating use case for this patch,
unmerged paths give us one source of duplication when we are asking
for list of paths without stages.

It also considers, IIRC, deletion is merely one of the forms of
modifications, so asking it to list modified paths and deleted paths
at the same time would give you another source of duplication.

Perhaps not-so-low-hanging fruit miniproject would be to teach
"ls-files" a new "--dedup" option that does two things:

 * When -m and -d are asked at the same time, ignore '-d', because
   '-d' will give duplicates for subsets of what '-m' would show
   anyway; and

 * When neither -s nor -u is given, do not show the same path more
   than once, even the ones with multiple stages.

Perhaps it is safe to leave a #leftoverbits mark for the above, now
that two people in addition to I noticed that the behaviour is less
than ideal.

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[SZEDER Gábor]

On Mon, Apr 22, 2019 at 10:49:27AM -0400, Jeff King wrote:
> On Sun, Apr 21, 2019 at 10:19:04PM +0900, Junio C Hamano wrote:
> 
> >    I am not fan of adding the "| sort -u" of the whole thing,
> >    because there is no need to dedup the output of the $(FIND) side
> >    of the alternative, but "(ls-files | sort -u) || (find)" would
> >    obviously not work.  If we truly care, perhaps we should add a
> >    new option to ls-files to show each path only once, unless it is
> >    showing the stage number (i.e. "ls-files -s" or "ls-files -u"),
> >    but this gets the problem go away without code change, hence this
> >    RFC ;-)
> 
> FWIW, after reading your commit message my thoughts immediately turned
> to "why can't ls-files have a mode that outputs each just once", but
> then ended up at the same place as your patch: it's not that hard to
> just de-dup the output.
> 
> It _could_ be a sign that other scripts besides our Makefile would
> benefit from such an option, but I think I'd want to see at least one
> other example before going in that direction.

I remember being rather puzzled by 'git ls-files' listing the same
file more than once depending on its --options when I was working on
the git-aware path completion parts of our completion script.

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Junio C Hamano]

SZEDER Gábor <szeder.dev@gmail.com> writes:

> I remember being rather puzzled by 'git ls-files' listing the same
> file more than once depending on its --options when I was working on
> the git-aware path completion parts of our completion script.

Yup, I recall a thread we recently had where we wondered why we see
two entries reported when we ask for 'modified' and 'deleted' at the
same time.

Perhaps not-so-low-hanging fruit miniproject would be to teach
"ls-files" a new "--dedup" option that does two things:

 * When -m and -d are asked at the same time, ignore '-d', because
   '-d' will give duplicates for subsets of what '-m' would show
   anyway; and

 * When neither -s nor -u is given, do not show the same path more
   than once, even the ones with multiple stages.

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[SZEDER Gábor]

On Wed, Apr 24, 2019 at 10:03:37AM +0900, Junio C Hamano wrote:
> SZEDER Gábor <szeder.dev@gmail.com> writes:
> 
> > I remember being rather puzzled by 'git ls-files' listing the same
> > file more than once depending on its --options when I was working on
> > the git-aware path completion parts of our completion script.
> 
> Yup, I recall a thread we recently had where we wondered why we see
> two entries reported when we ask for 'modified' and 'deleted' at the
> same time.
> 
> Perhaps not-so-low-hanging fruit miniproject would be to teach
> "ls-files" a new "--dedup" option that does two things:
> 
>  * When -m and -d are asked at the same time, ignore '-d', because
>    '-d' will give duplicates for subsets of what '-m' would show
>    anyway; and

There are other combination of options that need similar treatment,
e.g. '--cached --modified', '--cached --deleted', and I vaguely
remember a combination involving '--killed' as well.

On second thought, however, I'm not sure that such a '--dedup' option
would be all that useful in the above cases.  If the users have to
adjust their 'git ls-files' invocation by specifying '--dedup' to
avoid the same paths listed multiple times, then they might just as
well remove the redundant options.  After all, a deleted file is
inherently modified, and a modified file is inherently cached...

>  * When neither -s nor -u is given, do not show the same path more
>    than once, even the ones with multiple stages.
> 

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Eric Sunshine]

On Wed, Apr 24, 2019 at 7:26 AM SZEDER Gábor <szeder.dev@gmail.com> wrote:
> On second thought, however, I'm not sure that such a '--dedup' option
> would be all that useful in the above cases.  If the users have to
> adjust their 'git ls-files' invocation by specifying '--dedup' to
> avoid the same paths listed multiple times, then they might just as
> well remove the redundant options.  After all, a deleted file is
> inherently modified, and a modified file is inherently cached...

As a person who rarely, if ever, uses git-ls-files, I'm having trouble
understanding why de-duping isn't the default behavior when the
listing is otherwise not annotated (that is, when -t/-v/-f/--debug are
not used). Are consumers of an unannotated list able to derive any
additional useful information from the duplicate entries? If consumers
can't derive anything useful, then the duplication seems more an
accident of implementation (for the unannotated case) than a planned
feature, thus could be considered a bug worth fixing. And, the fix
would be to de-dup by default when unannotated, thus no need for a
--dedup option. (As for backward-compatibility concerns, I imagine
that existing consumers either don't care about the duplication or
already manually de-dup, but perhaps I'm not seeing the larger
picture.)

Re: [PATCH/RFC] Makefile: dedup list of files obtained from ls-files

[Junio C Hamano]

Eric Sunshine <sunshine@sunshineco.com> writes:

> As a person who rarely, if ever, uses git-ls-files, I'm having trouble
> understanding why de-duping isn't the default behavior when the
> listing is otherwise not annotated (that is, when -t/-v/-f/--debug are
> not used).

It was because the implementor of the original was bold enough to
say "if it hurts, don't do it" to those who try to combine flags
that may produce overlapping result that lead to duplicates.