threads / rfc / 50963

RFC patchMakefile: dedup list of files obtained from ls-files

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

## tl;dr

11 messages between Apr 21, 2019 and Apr 25, 2019. Diffs are folded; open one to read it.

replies: 10people: 5as markdown or json

Junio C Hamano· Apr 21, 2019, 13:19 UTC · lore

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 ;-)
Show changes to Makefile +3 −3
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)
Eric Sunshine· Apr 22, 2019, 03:23 UTC · re: Junio C Hamano · lore

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

On Sun, Apr 21, 2019 at 9:19 AM Junio C Hamano <gitster@pobox.com> wrote:
Show 10 quoted lines
> 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 ...))
Junio C Hamano· Apr 22, 2019, 06:11 UTC · re: Eric Sunshine · lore

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

Eric Sunshine <sunshine@sunshineco.com> writes:
Show 15 quoted lines
> 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.
Jeff King· Apr 22, 2019, 14:49 UTC · re: Junio C Hamano · lore

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

On Sun, Apr 21, 2019 at 10:19:04PM +0900, Junio C Hamano wrote:
Show 8 quoted lines
>    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
Ramsay Jones· Apr 22, 2019, 17:15 UTC · re: Jeff King · lore

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

On 22/04/2019 15:49, Jeff King wrote:
Show 15 quoted lines
> 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

Junio C Hamano· Apr 23, 2019, 01:18 UTC · re: Ramsay Jones · lore

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

Ramsay Jones <ramsay@ramsayjones.plus.com> writes:
Show 9 quoted lines
>> 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.

SZEDER Gábor· Apr 23, 2019, 20:21 UTC · re: Jeff King · lore

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

On Mon, Apr 22, 2019 at 10:49:27AM -0400, Jeff King wrote:
Show 19 quoted lines
> 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.

Junio C Hamano· Apr 24, 2019, 01:03 UTC · re: SZEDER Gábor · lore

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

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.
SZEDER Gábor· Apr 24, 2019, 11:25 UTC · re: Junio C Hamano · lore

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

On Wed, Apr 24, 2019 at 10:03:37AM +0900, Junio C Hamano wrote:
Show 16 quoted lines
> 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.
> 
Eric Sunshine· Apr 24, 2019, 17:19 UTC · re: SZEDER Gábor · lore

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

On Wed, Apr 24, 2019 at 7:26 AM SZEDER Gábor <szeder.dev@gmail.com> wrote:
Show 6 quoted lines
> 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.)

Junio C Hamano· Apr 25, 2019, 00:59 UTC · re: Eric Sunshine · lore

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

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.

← back to recent threads