patchfast-export: fix surprising behavior with --first-parent

> From: William Sprent <williams@unity3d.com>
>
> When invoking git-fast-export with the --first-parent flag on a branch
> with merges, fast-export would early-out on processing the first merge
> on the branch. If combined with --reverse, fast-export would instead
> output all single parent commits on the branch.
>
> This commit makes fast-export output the same commits as rev-list
> --first-parent, and makes --reverse not have an effect on which commits
> are output.
>
> The fix involves removing logic within fast-export which was responsible
> for ensuring that parents are processed before their children, which was
> what was exiting early due to missing second parents. This is replaced
> by setting 'reverse = 1' before revision walking, which, in conjuction
> with topo_order, allows for delegating the ordering of commits to
> revision.c. The reverse flag is set after parsing rev-list arguments to
> avoid having it disabled.
>
> Signed-off-by: William Sprent <williams@unity3d.com>
> ---
>     fast-export: fix surprising behavior with --first-parent
>     
>     Hi,
>     
>     This is my first time patching git, so I probably need some guidance on
>     my approach. :)

> -static int has_unshown_parent(struct commit *commit)
> -{
> -	struct commit_list *parent;
> -
> -	for (parent = commit->parents; parent; parent = parent->next)
> -		if (!(parent->item->object.flags & SHOWN) &&
> -		    !(parent->item->object.flags & UNINTERESTING))
> -			return 1;
> -	return 0;
> -}
> -
>  struct anonymized_entry {
>  	struct hashmap_entry hash;
>  	const char *anon;
> @@ -752,20 +740,6 @@ static char *anonymize_tag(void *data)
>  	return strbuf_detach(&out, NULL);
>  }
>  
> -static void handle_tail(struct object_array *commits, struct rev_info *revs,
> -			struct string_list *paths_of_changed_objects)
> -{
> -	struct commit *commit;
> -	while (commits->nr) {
> -		commit = (struct commit *)object_array_pop(commits);
> -		if (has_unshown_parent(commit)) {
> -			/* Queue again, to be handled later */
> -			add_object_array(&commit->object, NULL, commits);
> -			return;
> -		}
> -		handle_commit(commit, revs, paths_of_changed_objects);
> -	}
> -}

>  static void handle_tag(const char *name, struct tag *tag)
>  {
> @@ -1185,7 +1159,6 @@ static int parse_opt_anonymize_map(const struct option *opt,
>  int cmd_fast_export(int argc, const char **argv, const char *prefix)
>  {
>  	struct rev_info revs;
> -	struct object_array commits = OBJECT_ARRAY_INIT;
>  	struct commit *commit;
>  	char *export_filename = NULL,
>  	     *import_filename = NULL,
> @@ -1281,19 +1254,14 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
>  
>  	get_tags_and_duplicates(&revs.cmdline);
>  
> +	revs.reverse = 1;

>  	revs.diffopt.format_callback = show_filemodify;
>  	revs.diffopt.format_callback_data = &paths_of_changed_objects;
>  	revs.diffopt.flags.recursive = 1;
>  	while ((commit = get_revision(&revs))) {
> -		if (has_unshown_parent(commit)) {
> -			add_object_array(&commit->object, NULL, &commits);
> -		}
> -		else {
> -			handle_commit(commit, &revs, &paths_of_changed_objects);
> -			handle_tail(&commits, &revs, &paths_of_changed_objects);
> -		}
> +		handle_commit(commit, &revs, &paths_of_changed_objects);
>  	}
>  

> +	test_commit init &&
> +	git checkout -b topic1 &&
> +	test_commit file2 file2.txt &&
> +	git checkout main &&
> +	git merge topic1 --no-ff &&
> +
> +	git checkout -b topic2 &&
> +	test_commit file3 file3.txt &&
> +	git checkout main &&
> +	git merge topic2 --no-ff &&

> 
> On Tue, Nov 23 2021, William Sprent via GitGitGadget wrote:
> 
>> From: William Sprent <williams@unity3d.com>
>>
>> When invoking git-fast-export with the --first-parent flag on a branch
>> with merges, fast-export would early-out on processing the first merge
>> on the branch. If combined with --reverse, fast-export would instead
>> output all single parent commits on the branch.
>>
>> This commit makes fast-export output the same commits as rev-list
>> --first-parent, and makes --reverse not have an effect on which commits
>> are output.
>>
>> The fix involves removing logic within fast-export which was responsible
>> for ensuring that parents are processed before their children, which was
>> what was exiting early due to missing second parents. This is replaced
>> by setting 'reverse = 1' before revision walking, which, in conjuction
>> with topo_order, allows for delegating the ordering of commits to
>> revision.c. The reverse flag is set after parsing rev-list arguments to
>> avoid having it disabled.
>>
>> Signed-off-by: William Sprent <williams@unity3d.com>
>> ---
>>      fast-export: fix surprising behavior with --first-parent
>>      
>>      Hi,
>>      
>>      This is my first time patching git, so I probably need some guidance on
>>      my approach. :)
> 
> Hi, thanks for your first contribution to git. This is a rather shallow
> review, a deeper one is much deserved.
> > I notice that you're removing code in builtin/fast-export.c, presumably
> we have code in revision.c that does the same thing. It would really
> help a reviewer for you to dig a bit into the relevant commit history
> and note it in the commit message.
> 
> I.e. could revision.c always do this, and this was always needless
> duplication, or at time X it was needed, but as of Y revision.c learned
> to do this, and callers A, B and C were adjusted, but just not this
> missed call D? etc.
> 

>> -static int has_unshown_parent(struct commit *commit)
>> -{
>> -	struct commit_list *parent;
>> -
>> -	for (parent = commit->parents; parent; parent = parent->next)
>> -		if (!(parent->item->object.flags & SHOWN) &&
>> -		    !(parent->item->object.flags & UNINTERESTING))
>> -			return 1;
>> -	return 0;
>> -}
>> -
>>   struct anonymized_entry {
>>   	struct hashmap_entry hash;
>>   	const char *anon;
>> @@ -752,20 +740,6 @@ static char *anonymize_tag(void *data)
>>   	return strbuf_detach(&out, NULL);
>>   }
>>   
>> -static void handle_tail(struct object_array *commits, struct rev_info *revs,
>> -			struct string_list *paths_of_changed_objects)
>> -{
>> -	struct commit *commit;
>> -	while (commits->nr) {
>> -		commit = (struct commit *)object_array_pop(commits);
>> -		if (has_unshown_parent(commit)) {
>> -			/* Queue again, to be handled later */
>> -			add_object_array(&commit->object, NULL, commits);
>> -			return;
>> -		}
>> -		handle_commit(commit, revs, paths_of_changed_objects);
>> -	}
>> -}
> 
> ...
> 
>>   static void handle_tag(const char *name, struct tag *tag)
>>   {
>> @@ -1185,7 +1159,6 @@ static int parse_opt_anonymize_map(const struct option *opt,
>>   int cmd_fast_export(int argc, const char **argv, const char *prefix)
>>   {
>>   	struct rev_info revs;
>> -	struct object_array commits = OBJECT_ARRAY_INIT;
>>   	struct commit *commit;
>>   	char *export_filename = NULL,
>>   	     *import_filename = NULL,
>> @@ -1281,19 +1254,14 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
>>   
>>   	get_tags_and_duplicates(&revs.cmdline);
>>   
>> +	revs.reverse = 1;
> 
> Is the placement of revs.reverse = 1 here important, or could it go
> earlier after init_revision_sources() when we assign some other values
> ir revs?
> 
>>   	if (prepare_revision_walk(&revs))
>>   		die("revision walk setup failed");
> 
> A light reading of prepare_revision_walk() suggests it could come after,
> but maybe I'm entirely wrong.

>>   	revs.diffopt.format_callback = show_filemodify;
>>   	revs.diffopt.format_callback_data = &paths_of_changed_objects;
>>   	revs.diffopt.flags.recursive = 1;
>>   	while ((commit = get_revision(&revs))) {
>> -		if (has_unshown_parent(commit)) {
>> -			add_object_array(&commit->object, NULL, &commits);
>> -		}
>> -		else {
>> -			handle_commit(commit, &revs, &paths_of_changed_objects);
>> -			handle_tail(&commits, &revs, &paths_of_changed_objects);
>> -		}
>> +		handle_commit(commit, &revs, &paths_of_changed_objects);
>>   	}
>>   
> 
> Yay code deletion, good if it works (I didn't check).
> 
> Since this is just a one-statement while-loop we can also remove its
> braces now.
>  >> +test_expect_success 'fast-export --first-parent outputs all 

>> +	git init first-parent &&
>> +	cd first-parent &&
> 
> Do any such "cd" in a sub-shell:
> 
> 	git init x &&
> 	(
>      		cd x &&
>                  ...
> 	)
> Otherwise the next test after you is going to run in anotherdirectory.
> 
>> +	test_commit init &&
>> +	git checkout -b topic1 &&
>> +	test_commit file2 file2.txt &&
>> +	git checkout main &&
>> +	git merge topic1 --no-ff &&
>> +
>> +	git checkout -b topic2 &&
>> +	test_commit file3 file3.txt &&
>> +	git checkout main &&
>> +	git merge topic2 --no-ff &&
> 
> Just a nit. I'd use "test_commit A", "test_commit B" etc. when the
> filenames etc. aren't important. There's no subsequent reference here,
> so I assume they're not.
> 
>> +	test_commit branch-head &&
>> +
>> +	git rev-list --format="%ad%B" --first-parent --topo-order --no-commit-header main > expected &&
> 
> nit; >expected, not > expected is the usual style.
>> +
>> +	git fast-export main -- --first-parent > first-parent-export &&
>> +	git fast-export main -- --first-parent --reverse > first-parent-reverse-export &&
> 
> ditto:
> 
>> +	git init import && cd import &&
> 
> ditto earlier "cd" comment.
> 
>> +	cat ../first-parent-export | git fast-import &&
> 
> Instead of "cat x | prog" do "prog <x".
> 
>> +	git rev-list --format="%ad%B" --topo-order --all --no-commit-header > actual &&
> 
>> +	test $(git rev-list --all | wc -l) -eq 4 &&
> 
> Instead:
> 
>      git rev-list --all >tmp &&
>      test_line_count = 4 tmp
> 
> (for some value of tmp)
> 
>> +	test_cmp ../expected actual &&
>> +	test_cmp ../first-parent-export ../first-parent-reverse-export
>> +'
> 
> Maybe some of the CD-ing around here wouldu be easier by not doing that
> and instead running e.g.:
> 
>      git -C subdir fast-export >file-not-in-subdir &&
>      ...
> 

>
> From: William Sprent <williams@unity3d.com>
>
> When invoking git-fast-export with the --first-parent flag on a branch
> with merges, fast-export would early-out on processing the first merge
> on the branch. If combined with --reverse, fast-export would instead
> output all single parent commits on the branch.
>
> This commit makes fast-export output the same commits as rev-list
> --first-parent, and makes --reverse not have an effect on which commits
> are output.
>
> The fix involves removing logic within fast-export which was responsible
> for ensuring that parents are processed before their children, which was
> what was exiting early due to missing second parents. This is replaced
> by setting 'reverse = 1' before revision walking, which, in conjuction
> with topo_order, allows for delegating the ordering of commits to
> revision.c. The reverse flag is set after parsing rev-list arguments to
> avoid having it disabled.
>
> Signed-off-by: William Sprent <williams@unity3d.com>
> ---
>     fast-export: fix surprising behavior with --first-parent
>
>     Hi,
>
>     This is my first time patching git, so I probably need some guidance on
>     my approach. :)
>
>     I've noticed that git fast-export exhibits some odd behavior when passed
>     the --first-parent flag. In the repository I was working on, it would
>     only output the initial commit before exiting. Moreover, adding the
>     --reverse flag causes it to behave differently and instead output all
>     commits in the first parent line that only have one parent. My
>     expectation is more or less that git fast-export should output the same
>     set of commits as git rev-list would output given the same arguments,
>     which matches how it acts when given revision ranges.
>
>     It seems like this behavior comes from the fact that has_unshown_parents
>     will never be false for any merge commits encountered when fast-export
>     is called with --first-parent. This causes the while loop to follow the
>     pattern of pushing all commits into the "commits" queue until the
>     initial commit is encountered, at which point it calls handle_tail which
>     falls through on the first merge commit, causing most of the commits to
>     be unhandled.
>
>     My impression is that this logic only serves to ensure that parents are
>     processed before their children, so in my patch I've opted to fix the
>     issue by delegating that responsibility to revision.c by adding the
>     reverse flag before performing the revision walk. From what I can see,
>     this should be equivalent to what the previous logic is trying to
>     achieve, but I can also see that there could be risk in these changes.
>
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1084%2Fwilliams-unity%2Ffast-export%2Ffirst-parent-issues-v1
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1084/williams-unity/fast-export/first-parent-issues-v1
> Pull-Request: https://github.com/gitgitgadget/git/pull/1084
>
>  builtin/fast-export.c  | 36 ++----------------------------------
>  t/t9350-fast-export.sh | 30 ++++++++++++++++++++++++++++++
>  2 files changed, 32 insertions(+), 34 deletions(-)
>
> diff --git a/builtin/fast-export.c b/builtin/fast-export.c
> index 8e2caf72819..50f8c224b6e 100644
> --- a/builtin/fast-export.c
> +++ b/builtin/fast-export.c
> @@ -107,18 +107,6 @@ static int parse_opt_reencode_mode(const struct option *opt,
>
>  static struct decoration idnums;
>  static uint32_t last_idnum;
> -
> -static int has_unshown_parent(struct commit *commit)
> -{
> -       struct commit_list *parent;
> -
> -       for (parent = commit->parents; parent; parent = parent->next)
> -               if (!(parent->item->object.flags & SHOWN) &&
> -                   !(parent->item->object.flags & UNINTERESTING))
> -                       return 1;
> -       return 0;
> -}
> -
>  struct anonymized_entry {
>         struct hashmap_entry hash;
>         const char *anon;
> @@ -752,20 +740,6 @@ static char *anonymize_tag(void *data)
>         return strbuf_detach(&out, NULL);
>  }
>
> -static void handle_tail(struct object_array *commits, struct rev_info *revs,
> -                       struct string_list *paths_of_changed_objects)
> -{
> -       struct commit *commit;
> -       while (commits->nr) {
> -               commit = (struct commit *)object_array_pop(commits);
> -               if (has_unshown_parent(commit)) {
> -                       /* Queue again, to be handled later */
> -                       add_object_array(&commit->object, NULL, commits);
> -                       return;
> -               }
> -               handle_commit(commit, revs, paths_of_changed_objects);
> -       }
> -}
>
>  static void handle_tag(const char *name, struct tag *tag)
>  {
> @@ -1185,7 +1159,6 @@ static int parse_opt_anonymize_map(const struct option *opt,
>  int cmd_fast_export(int argc, const char **argv, const char *prefix)
>  {
>         struct rev_info revs;
> -       struct object_array commits = OBJECT_ARRAY_INIT;
>         struct commit *commit;
>         char *export_filename = NULL,
>              *import_filename = NULL,
> @@ -1281,19 +1254,14 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
>
>         get_tags_and_duplicates(&revs.cmdline);
>
> +       revs.reverse = 1;
>         if (prepare_revision_walk(&revs))
>                 die("revision walk setup failed");
>         revs.diffopt.format_callback = show_filemodify;
>         revs.diffopt.format_callback_data = &paths_of_changed_objects;
>         revs.diffopt.flags.recursive = 1;
>         while ((commit = get_revision(&revs))) {
> -               if (has_unshown_parent(commit)) {
> -                       add_object_array(&commit->object, NULL, &commits);
> -               }
> -               else {
> -                       handle_commit(commit, &revs, &paths_of_changed_objects);
> -                       handle_tail(&commits, &revs, &paths_of_changed_objects);
> -               }
> +               handle_commit(commit, &revs, &paths_of_changed_objects);

>         }
>
>         handle_tags_and_duplicates(&extra_refs);
> diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
> index 409b48e2442..bd08101b81d 100755
> --- a/t/t9350-fast-export.sh
> +++ b/t/t9350-fast-export.sh
> @@ -750,4 +750,34 @@ test_expect_success 'merge commit gets exported with --import-marks' '
>         )
>  '
>
> +
> +test_expect_success 'fast-export --first-parent outputs all revisions output by revision walk' '
> +       git init first-parent &&
> +       cd first-parent &&
> +       test_commit init &&
> +       git checkout -b topic1 &&
> +       test_commit file2 file2.txt &&
> +       git checkout main &&
> +       git merge topic1 --no-ff &&
> +
> +       git checkout -b topic2 &&
> +       test_commit file3 file3.txt &&
> +       git checkout main &&
> +       git merge topic2 --no-ff &&
> +
> +       test_commit branch-head &&
> +
> +       git rev-list --format="%ad%B" --first-parent --topo-order --no-commit-header main > expected &&
> +
> +       git fast-export main -- --first-parent > first-parent-export &&
> +       git fast-export main -- --first-parent --reverse > first-parent-reverse-export &&
> +       git init import && cd import &&
> +       cat ../first-parent-export | git fast-import &&
> +
> +       git rev-list --format="%ad%B" --topo-order --all --no-commit-header > actual &&
> +       test $(git rev-list --all | wc -l) -eq 4 &&
> +       test_cmp ../expected actual &&
> +       test_cmp ../first-parent-export ../first-parent-reverse-export
> +'
> +
>  test_done
>
> base-commit: cd3e606211bb1cf8bc57f7d76bab98cc17a150bc
> --
> gitgitgadget

> On Tue, Nov 23, 2021 at 5:25 AM William Sprent via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
>>
>> From: William Sprent <williams@unity3d.com>
>> ...
> 
> Wow, interesting.  I did some related work that I never submitted at
> https://github.com/newren/git/commit/08f799b4667de1c755c78e1ea1657f946b588556
> -- in that commit, I also noticed that fast-export did not seem
> careful enough about making sure to process all commits, and came up
> with a much different fix.  However, in my case, I didn't know how to
> trigger the problems in fast-export without some additional changes I
> was trying to make, and since I never got those other changes working,
> I didn't think it was worth submitting my fix.  My solution is more
> complex, in part because it was designed to handle ordering
> requirements & recommendations other than just ancestry.  However, we
> don't currently have any additional ordering requirements (the current
> code only considers ancestry), so your solution is much simpler.  If I
> do at some point get my other changes working, I'd need to
> re-introduce the queue and handle_tail() and my changes to these, but
> that can always be done later if and when I get those other changes
> working.
> 

> Interestingly, Dscho added both the --reverse ability to revision.c
> and the commits object_array and the handle_tail() stuff in
> fast-export.c.  Both were done in the same year, and --reverse came
> first.  See 9c5e66e97da8 (Teach revision machinery about --reverse,
> 2007-01-20) and f2dc849e9c5f (Add 'git fast-export', the sister of
> 'git fast-import', 2007-12-02).  It's not clear why revs.reverse = 1
> wasn't used previously, although it certainly didn't occur to me
> either and I think it would have been an alternative solution to my
> first ever git.git contribution -- 784f8affe4df (fast-export: ensure
> we traverse commits in topological order, 2009-02-10).  (Though
> rev.reverse = 1 wouldn't have provided the same speedups that
> rev.topo_order=1 provided.)

> From: William Sprent <williams@unity3d.com>
>
> When invoking git-fast-export with the --first-parent flag on a branch
> with merges, fast-export would early-out on processing the first merge
> on the branch. If combined with --reverse, fast-export would instead
> output all single parent commits on the branch.

> "William Sprent via GitGitGadget" <gitgitgadget@gmail.com> writes:
> 
>> From: William Sprent <williams@unity3d.com>
>>
>> When invoking git-fast-export with the --first-parent flag on a branch
>> with merges, fast-export would early-out on processing the first merge
>> on the branch. If combined with --reverse, fast-export would instead
>> output all single parent commits on the branch.
> 
> I do not doubt we would want to make the command behave sensibly
> with all options it accepts, but let me first ask a more basic and
> possibly stupid question.
> 
> What is "git fast-export --first-parent <options>" supposed to do
> differently from "git fast-export <options>" (with the same set of
> options other than "--first-parent")?  Should it omit merge commits
> altogether, pretending that the first single-parent ancestor it
> finds on the first parent chain is a direct parent of a
> single-parent descendant, e.g. if the real history were with two
> single-parente commits A and B, with two merges M and N, on the
> mainline, making the resulting commits into a single strand of two
> pearls, with A and B before and after the rewrite to have the same
> tree objects?
> 
>      ---A---M---N---B             ---A---B
>            /   /           ==>
>           X   Y
> 
> Or should it pretend merge commits have only their first parent as
> their parents, i.e.
> 
>      ---A---M---N---B             ---A---M---N---B
>            /   /           ==>
>           X   Y
> 
> "git fast-export --help" does not even mention "--first-parent" and
> pretend that any and all [<git-rev-list-args>...] are valid requests
> to make to the command, but I am wondering if that is what we intend
> to support in the first place.  In builtin/fast-export.c, I do not
> see any attempt to do anything differently when "--first-parent" is
> requested.  Perhaps we shouldn't be even taking "--first-parent" as
> an option to begin with.
> The "--reverse" feels even more iffy.  Are we reversing the history
> with such an export, i.e. pretending that parents are children and
> merges are forks?
> 
>      ---A---M---N---B             B---N---M---A---
>            /   /           ==>         \   \
>           X   Y                         X   Y
> 
> Or are we supposed to produce the same history in the end, just
> spewing older commits first in the output stream?  I am not sure
> what purpose such a request serves---the "fast-import" downstream
> would need the same set of objects before it can create each commit
> anyway, so I am not sure what the point of giving "--reverse" is.
> 
> If there is no sensible interpretation for some of the options that
> are valid in rev-list in the context of "fast-export" command, should
> we just error out when we parse the command line, instead of producing
> nonsense output stream, I wonder.
> 

>
> From: William Sprent <williams@unity3d.com>
>
> When invoking git-fast-export with the --first-parent flag on a branch
> with merges, fast-export would early-out on processing the first merge
> on the branch. If combined with --reverse, fast-export would instead
> output all single parent commits on the branch.
>
> This commit makes fast-export output the same commits as rev-list
> --first-parent, and makes --reverse not have an effect on which commits
> are output.
>
> The fix involves removing logic within fast-export which was responsible
> for ensuring that parents are processed before their children, which was
> what was exiting early due to missing second parents. This is replaced
> by setting 'reverse = 1' before revision walking, which, in conjuction
> with topo_order, allows for delegating the ordering of commits to
> revision.c. The reverse flag is set after parsing rev-list arguments to
> avoid having it disabled.

>
> Signed-off-by: William Sprent <williams@unity3d.com>
> ---
>     fast-export: fix surprising behavior with --first-parent
>
>     Hi,
>
>     I've noticed that git fast-export exhibits some odd behavior when passed
>     the --first-parent flag. In the repository I was working on, it would
>     only output the initial commit before exiting. Moreover, adding the
>     --reverse flag causes it to behave differently and instead output all
>     commits in the first parent line that only have one parent. My
>     expectation is more or less that git fast-export should output the same
>     set of commits as git rev-list would output given the same arguments,
>     which matches how it acts when given revision ranges.
>
>     It seems like this behavior comes from the fact that has_unshown_parents
>     will never be false for any merge commits encountered when fast-export
>     is called with --first-parent. This causes the while loop to follow the
>     pattern of pushing all commits into the "commits" queue until the
>     initial commit is encountered, at which point it calls handle_tail which
>     falls through on the first merge commit, causing most of the commits to
>     be unhandled.
>
>     My impression is that this logic only serves to ensure that parents are
>     processed before their children, so in my patch I've opted to fix the
>     issue by delegating that responsibility to revision.c by adding the
>     reverse flag before performing the revision walk. From what I can see,
>     this should be equivalent to what the previous logic is trying to
>     achieve, but I can also see that there could be risk in these changes.
>
>     Changes since v1:
>
>      * Moved revs.reverse assignment down to similar assignments below.
>      * Removed braces around single statement while loop.
>      * The test now only changes directory inside a sub-shell.
>      * Applied stylistic feedback on test such as: making redirections be on
>        the form >FILE etc.
>
>     There were questions raised about whether it makes sense at all for
>     fast-export to simply accept all git rev-list arguments whether they
>     have an effect or not - in particular for a flag like --reverse. I think
>     I agree that it is questionable behavior, or at least questionably
>     documented, but I also think it is out of scope for this change.
>
>     I did consider teaching fast-export to complain if given --reverse, but
>     it seemed inconsistent to me as it will gladly accept every other
>     rev-list argument (for example, "git fast-export HEAD --show-signature
>     --graph" works just fine).
>
>     cc: Ævar Arnfjörð Bjarmason avarab@gmail.com
>

> diff --git a/builtin/fast-export.c b/builtin/fast-export.c
> index 8e2caf72819..cb1d6473f12 100644
> --- a/builtin/fast-export.c
> +++ b/builtin/fast-export.c
> @@ -107,18 +107,6 @@ static int parse_opt_reencode_mode(const struct option *opt,
>
>  static struct decoration idnums;
>  static uint32_t last_idnum;
> -
> -static int has_unshown_parent(struct commit *commit)
> -{
> -       struct commit_list *parent;
> -
> -       for (parent = commit->parents; parent; parent = parent->next)
> -               if (!(parent->item->object.flags & SHOWN) &&
> -                   !(parent->item->object.flags & UNINTERESTING))
> -                       return 1;
> -       return 0;
> -}
> -
>  struct anonymized_entry {
>         struct hashmap_entry hash;
>         const char *anon;
> @@ -752,20 +740,6 @@ static char *anonymize_tag(void *data)
>         return strbuf_detach(&out, NULL);
>  }
>
> -static void handle_tail(struct object_array *commits, struct rev_info *revs,
> -                       struct string_list *paths_of_changed_objects)
> -{
> -       struct commit *commit;
> -       while (commits->nr) {
> -               commit = (struct commit *)object_array_pop(commits);
> -               if (has_unshown_parent(commit)) {
> -                       /* Queue again, to be handled later */
> -                       add_object_array(&commit->object, NULL, commits);
> -                       return;
> -               }
> -               handle_commit(commit, revs, paths_of_changed_objects);
> -       }
> -}

>
>  static void handle_tag(const char *name, struct tag *tag)
>  {
> @@ -1185,7 +1159,6 @@ static int parse_opt_anonymize_map(const struct option *opt,
>  int cmd_fast_export(int argc, const char **argv, const char *prefix)
>  {
>         struct rev_info revs;
> -       struct object_array commits = OBJECT_ARRAY_INIT;
>         struct commit *commit;
>         char *export_filename = NULL,
>              *import_filename = NULL,
> @@ -1283,18 +1256,13 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
>
>         if (prepare_revision_walk(&revs))
>                 die("revision walk setup failed");
> +
> +       revs.reverse = 1;

>         revs.diffopt.format_callback = show_filemodify;
>         revs.diffopt.format_callback_data = &paths_of_changed_objects;
>         revs.diffopt.flags.recursive = 1;
> -       while ((commit = get_revision(&revs))) {
> -               if (has_unshown_parent(commit)) {
> -                       add_object_array(&commit->object, NULL, &commits);
> -               }
> -               else {
> -                       handle_commit(commit, &revs, &paths_of_changed_objects);
> -                       handle_tail(&commits, &revs, &paths_of_changed_objects);
> -               }
> -       }
> +       while ((commit = get_revision(&revs)))
> +               handle_commit(commit, &revs, &paths_of_changed_objects);

>
>         handle_tags_and_duplicates(&extra_refs);
>         handle_tags_and_duplicates(&tag_refs);
> diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
> index 409b48e2442..df1a5b1013a 100755
> --- a/t/t9350-fast-export.sh
> +++ b/t/t9350-fast-export.sh
> @@ -750,4 +750,39 @@ test_expect_success 'merge commit gets exported with --import-marks' '
>         )
>  '
>
> +
> +test_expect_success 'fast-export --first-parent outputs all revisions output by revision walk' '
> +       git init first-parent &&
> +       (
> +               cd first-parent &&
> +               test_commit A &&
> +               git checkout -b topic1 &&
> +               test_commit B &&
> +               git checkout main &&
> +               git merge topic1 --no-ff &&
> +
> +               git checkout -b topic2 &&
> +               test_commit C &&
> +               git checkout main &&
> +               git merge topic2 --no-ff &&

> +
> +               git fast-export main -- --first-parent >first-parent-export &&
> +               git fast-export main -- --first-parent --reverse >first-parent-reverse-export &&
> +
> +               git init import &&
> +               git -C import fast-import <first-parent-export &&
> +
> +               git -C import rev-list --format="%ad%B" --topo-order --all --no-commit-header >actual &&

> ...  Here's what I think are the relevant points
> (and yeah, it's lengthy):
>
>
> The revision traversal machinery typically processes and returns all
> children before any parent.  fast-export needs to operate in the
> reverse fashion, handling parents before any of their children in
> order to build up the history starting from the root commit(s).  This
> would be a clear case where we could just use the revision traversal
> machinery's "reverse" option to achieve this desired affect.
>
> However, this wasn't what the code did.  It added its own array for
> queuing.  The obvious hand-rolled solution would be to just push all
> the commits into the array and then traverse afterwards, but it didn't
> quite do that either.  It instead attempted to process anything it
> could as soon as it could, and once it could, check whether it could
> process anything that had been queued.  As far as I can tell, this was
> an effort to save a little memory in the case of multiple root commits
> since it could process some commits before queueing all of them.  This
> involved some helper functions named has_unshown_parent() and
> handle_tail().  For typical invocations of fast-export, this
> alternative essentially amounted to a hand-rolled method of reversing
> the commits -- it was a bunch of work to duplicate the revision
> traversal machinery's "reverse" option.
>
> This hand-rolled reversing mechanism is actually somewhat difficult to
> reason about.  It takes some time to figure out how it ensures in
> normal cases that it will actually process all traversed commits
> (rather than just dropping some and not printing anything for them).
>
> And it turns out there are some cases where the code does drop commits
> without handling them, and not even printing an error or warning for
> the user.  Due to the has_unshown_parent() checks, some commits could
> be left in the array at the end of the "while...get_revision()" loop
> which would be unprocessed.  This could be triggered for example with
>     git fast-export main -- --first-parent
> or non-sensical traversal rules such as
>     git fast-export main -- --grep=Merge --invert-grep
>
> While most traversals that don't include all parents should likely
> trigger errors in fast-export (or at least require being used in
> combination with --reference-excluded-parents), the --first-parent
> traversal is at least reasonable and it'd be nice if it didn't just
> drop commits.  It'd also be nice to have a simpler "reverse traversal"
> mechanism.  Use the "reverse" option of the revision traversal
> machinery to achieve both.

> Even for the non-sensical traversal flags like the --grep one above,
> this would be an improvement.  For example, in that case, the code
> previously would have silently truncated history to only those commits
> that do not have an ancestor containing "Merge" in their commit
> message.  After this code change, that case would would include all

> commits without "Merge" in their commit message -- but any commit that
> previously had a "Merge"-mentioning parent would lose that parent
> (likely resulting in many new root commits).  While the new behavior
> is still odd, it is at least understandable given that
> --reference-excluded-parents is not the default.

>
> Elijah Newren <newren@gmail.com> writes:
>
> > ...  Here's what I think are the relevant points
> > (and yeah, it's lengthy):
> >
> >
> > The revision traversal machinery typically processes and returns all
> > children before any parent.  fast-export needs to operate in the
> > reverse fashion, handling parents before any of their children in
> > order to build up the history starting from the root commit(s).  This
> > would be a clear case where we could just use the revision traversal
> > machinery's "reverse" option to achieve this desired affect.
> >
> > However, this wasn't what the code did.  It added its own array for
> > queuing.  The obvious hand-rolled solution would be to just push all
> > the commits into the array and then traverse afterwards, but it didn't
> > quite do that either.  It instead attempted to process anything it
> > could as soon as it could, and once it could, check whether it could
> > process anything that had been queued.  As far as I can tell, this was
> > an effort to save a little memory in the case of multiple root commits
> > since it could process some commits before queueing all of them.  This
> > involved some helper functions named has_unshown_parent() and
> > handle_tail().  For typical invocations of fast-export, this
> > alternative essentially amounted to a hand-rolled method of reversing
> > the commits -- it was a bunch of work to duplicate the revision
> > traversal machinery's "reverse" option.
> >
> > This hand-rolled reversing mechanism is actually somewhat difficult to
> > reason about.  It takes some time to figure out how it ensures in
> > normal cases that it will actually process all traversed commits
> > (rather than just dropping some and not printing anything for them).
> >
> > And it turns out there are some cases where the code does drop commits
> > without handling them, and not even printing an error or warning for
> > the user.  Due to the has_unshown_parent() checks, some commits could
> > be left in the array at the end of the "while...get_revision()" loop
> > which would be unprocessed.  This could be triggered for example with
> >     git fast-export main -- --first-parent
> > or non-sensical traversal rules such as
> >     git fast-export main -- --grep=Merge --invert-grep
> >
> > While most traversals that don't include all parents should likely
> > trigger errors in fast-export (or at least require being used in
> > combination with --reference-excluded-parents), the --first-parent
> > traversal is at least reasonable and it'd be nice if it didn't just
> > drop commits.  It'd also be nice to have a simpler "reverse traversal"
> > mechanism.  Use the "reverse" option of the revision traversal
> > machinery to achieve both.
>
> The above is a very helpful and understandable explanation of what
> is going on.  I am a bit puzzled by the very last part, though. By
> "It'd also be nice to have a simpler 'reverse traversal' mechanism",
> do you mean that the end users have need to control the direction
> the traversal goes (in other words, they use "git fast-export" for
> some thing, and "git fast-export --reverse" to achieve some other
> things)?  Or do you just mean that we need to do a reverse traversal
> but that is already available in the revision traversal machinery,
> and not using it and rolling our own does not make sense?

> > Even for the non-sensical traversal flags like the --grep one above,
> > this would be an improvement.  For example, in that case, the code
> > previously would have silently truncated history to only those commits
> > that do not have an ancestor containing "Merge" in their commit
> > message.  After this code change, that case would would include all
>
> "would would" -> "would"

> > commits without "Merge" in their commit message -- but any commit that
> > previously had a "Merge"-mentioning parent would lose that parent
> > (likely resulting in many new root commits).  While the new behavior
> > is still odd, it is at least understandable given that
> > --reference-excluded-parents is not the default.
>
> Nicely written.

>   On Thu, Dec 9, 2021 at 12:13 AM William Sprent via GitGitGadget
> <gitgitgadget@gmail.com> wrote:
>>
>> From: William Sprent <williams@unity3d.com>
>>
>> When invoking git-fast-export with the --first-parent flag on a branch
>> with merges, fast-export would early-out on processing the first merge
>> on the branch. If combined with --reverse, fast-export would instead
>> output all single parent commits on the branch.
>>
>> This commit makes fast-export output the same commits as rev-list
>> --first-parent, and makes --reverse not have an effect on which commits
>> are output.
>>
>> The fix involves removing logic within fast-export which was responsible
>> for ensuring that parents are processed before their children, which was
>> what was exiting early due to missing second parents. This is replaced
>> by setting 'reverse = 1' before revision walking, which, in conjuction
>> with topo_order, allows for delegating the ordering of commits to
>> revision.c. The reverse flag is set after parsing rev-list arguments to
>> avoid having it disabled.
> 
> This explains how you discovered the issue, but seems to focus on
> these particular flags, leaving the reader wondering whether there are
> other flags that are also mishandled that need additional care, and
> whether this fix might break things for other sets of flags.  It took
> me quite a bit of reasoning to satisfy myself on those points; it's
> actually somewhat complex.  May I suggest an alternative commit
> message based on that?  Here's what I think are the relevant points
> (and yeah, it's lengthy):
> 
> 
> The revision traversal machinery typically processes and returns all
> children before any parent.  fast-export needs to operate in the
> reverse fashion, handling parents before any of their children in
> order to build up the history starting from the root commit(s).  This
> would be a clear case where we could just use the revision traversal
> machinery's "reverse" option to achieve this desired affect.
> 
> However, this wasn't what the code did.  It added its own array for
> queuing.  The obvious hand-rolled solution would be to just push all
> the commits into the array and then traverse afterwards, but it didn't
> quite do that either.  It instead attempted to process anything it
> could as soon as it could, and once it could, check whether it could
> process anything that had been queued.  As far as I can tell, this was
> an effort to save a little memory in the case of multiple root commits
> since it could process some commits before queueing all of them.  This
> involved some helper functions named has_unshown_parent() and
> handle_tail().  For typical invocations of fast-export, this
> alternative essentially amounted to a hand-rolled method of reversing
> the commits -- it was a bunch of work to duplicate the revision
> traversal machinery's "reverse" option.
> 
> This hand-rolled reversing mechanism is actually somewhat difficult to
> reason about.  It takes some time to figure out how it ensures in
> normal cases that it will actually process all traversed commits
> (rather than just dropping some and not printing anything for them).
> 
> And it turns out there are some cases where the code does drop commits
> without handling them, and not even printing an error or warning for
> the user.  Due to the has_unshown_parent() checks, some commits could
> be left in the array at the end of the "while...get_revision()" loop
> which would be unprocessed.  This could be triggered for example with
>      git fast-export main -- --first-parent
> or non-sensical traversal rules such as
>      git fast-export main -- --grep=Merge --invert-grep
> 
> While most traversals that don't include all parents should likely
> trigger errors in fast-export (or at least require being used in
> combination with --reference-excluded-parents), the --first-parent
> traversal is at least reasonable and it'd be nice if it didn't just
> drop commits.  It'd also be nice to have a simpler "reverse traversal"
> mechanism.  Use the "reverse" option of the revision traversal
> machinery to achieve both.
> 
> Even for the non-sensical traversal flags like the --grep one above,
> this would be an improvement.  For example, in that case, the code
> previously would have silently truncated history to only those commits
> that do not have an ancestor containing "Merge" in their commit
> message.  After this code change, that case would would include all
> commits without "Merge" in their commit message -- but any commit that
> previously had a "Merge"-mentioning parent would lose that parent
> (likely resulting in many new root commits).  While the new behavior
> is still odd, it is at least understandable given that
> --reference-excluded-parents is not the default.
> 
> 

>>
>> Signed-off-by: William Sprent <williams@unity3d.com>
>> ---
>>      fast-export: fix surprising behavior with --first-parent
>>
>>      Hi,
>>
>>      I've noticed that git fast-export exhibits some odd behavior when passed
>>      the --first-parent flag. In the repository I was working on, it would
>>      only output the initial commit before exiting. Moreover, adding the
>>      --reverse flag causes it to behave differently and instead output all
>>      commits in the first parent line that only have one parent. My
>>      expectation is more or less that git fast-export should output the same
>>      set of commits as git rev-list would output given the same arguments,
>>      which matches how it acts when given revision ranges.
>>
>>      It seems like this behavior comes from the fact that has_unshown_parents
>>      will never be false for any merge commits encountered when fast-export
>>      is called with --first-parent. This causes the while loop to follow the
>>      pattern of pushing all commits into the "commits" queue until the
>>      initial commit is encountered, at which point it calls handle_tail which
>>      falls through on the first merge commit, causing most of the commits to
>>      be unhandled.
>>
>>      My impression is that this logic only serves to ensure that parents are
>>      processed before their children, so in my patch I've opted to fix the
>>      issue by delegating that responsibility to revision.c by adding the
>>      reverse flag before performing the revision walk. From what I can see,
>>      this should be equivalent to what the previous logic is trying to
>>      achieve, but I can also see that there could be risk in these changes.
>>
>>      Changes since v1:
>>
>>       * Moved revs.reverse assignment down to similar assignments below.
>>       * Removed braces around single statement while loop.
>>       * The test now only changes directory inside a sub-shell.
>>       * Applied stylistic feedback on test such as: making redirections be on
>>         the form >FILE etc.
>>
>>      There were questions raised about whether it makes sense at all for
>>      fast-export to simply accept all git rev-list arguments whether they
>>      have an effect or not - in particular for a flag like --reverse. I think
>>      I agree that it is questionable behavior, or at least questionably
>>      documented, but I also think it is out of scope for this change.
>>
>>      I did consider teaching fast-export to complain if given --reverse, but
>>      it seemed inconsistent to me as it will gladly accept every other
>>      rev-list argument (for example, "git fast-export HEAD --show-signature
>>      --graph" works just fine).
>>
>>      cc: Ævar Arnfjörð Bjarmason avarab@gmail.com
>>
> ...
>> diff --git a/builtin/fast-export.c b/builtin/fast-export.c
>> index 8e2caf72819..cb1d6473f12 100644
>> --- a/builtin/fast-export.c
>> +++ b/builtin/fast-export.c
>> @@ -107,18 +107,6 @@ static int parse_opt_reencode_mode(const struct option *opt,
>>
>>   static struct decoration idnums;
>>   static uint32_t last_idnum;
>> -
>> -static int has_unshown_parent(struct commit *commit)
>> -{
>> -       struct commit_list *parent;
>> -
>> -       for (parent = commit->parents; parent; parent = parent->next)
>> -               if (!(parent->item->object.flags & SHOWN) &&
>> -                   !(parent->item->object.flags & UNINTERESTING))
>> -                       return 1;
>> -       return 0;
>> -}
>> -
>>   struct anonymized_entry {
>>          struct hashmap_entry hash;
>>          const char *anon;
>> @@ -752,20 +740,6 @@ static char *anonymize_tag(void *data)
>>          return strbuf_detach(&out, NULL);
>>   }
>>
>> -static void handle_tail(struct object_array *commits, struct rev_info *revs,
>> -                       struct string_list *paths_of_changed_objects)
>> -{
>> -       struct commit *commit;
>> -       while (commits->nr) {
>> -               commit = (struct commit *)object_array_pop(commits);
>> -               if (has_unshown_parent(commit)) {
>> -                       /* Queue again, to be handled later */
>> -                       add_object_array(&commit->object, NULL, commits);
>> -                       return;
>> -               }
>> -               handle_commit(commit, revs, paths_of_changed_objects);
>> -       }
>> -}
> 
> Deleted code is debugged code!  :-)
> 
>>
>>   static void handle_tag(const char *name, struct tag *tag)
>>   {
>> @@ -1185,7 +1159,6 @@ static int parse_opt_anonymize_map(const struct option *opt,
>>   int cmd_fast_export(int argc, const char **argv, const char *prefix)
>>   {
>>          struct rev_info revs;
>> -       struct object_array commits = OBJECT_ARRAY_INIT;
>>          struct commit *commit;
>>          char *export_filename = NULL,
>>               *import_filename = NULL,
>> @@ -1283,18 +1256,13 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
>>
>>          if (prepare_revision_walk(&revs))
>>                  die("revision walk setup failed");
>> +
>> +       revs.reverse = 1;
> 
> I really wanted to see this next to the
>      rev.topo_order = 1
> statement elsewhere, but as you alluded to in the commit message, this
> part of revision.c makes that unsafe:
> 
> """
> } else if (!strcmp(arg, "--reverse")) {
>      revs->reverse ^= 1;
> """
> 
> However, given that it's unsafe to set revs.reverse=1 earlier, now
> that I think about it, isn't it also unsafe to set revs.topo_order
> where it is?  Someone could override it by passing --date-order to
> fast-export.  (It's okay if you want to leave fixing that to someone
> else, just thought I'd mention it while reviewing.)
> 

>
> > However, given that it's unsafe to set revs.reverse=1 earlier, now
> > that I think about it, isn't it also unsafe to set revs.topo_order
> > where it is?  Someone could override it by passing --date-order to
> > fast-export.  (It's okay if you want to leave fixing that to someone
> > else, just thought I'd mention it while reviewing.)
> >
>
> I couldn't tell you for sure if the topo_order placement is safe. I at
> least don't see any place where topo_order itself can be toggled off in
> revision.c.  I'm sure there exists at least one rev-list argument which
> will cause unexpected behaviour, though.
>
> I agree that it would be nice to have the traversal order options be
> assigned in the same place. I guess we have three options:
>
>
>     1. Put the reverse assignment to the top (together with topo_order),
> allowing the user to disable it with --reverse, which will cause odd
> behaviour.

> I don't think any of the three options are particularly good. The first
> one for obvious reasons. The second seems inconsistent to me as we would
> only error on --reverse but not any of the other "nonsensical" rev-list
> args. However, silently ignoring certain arguments does also not make
> for a good user experience.
>
> I think that it might be a good idea to move up the 'reverse' assignment
> and then add a paragraph to the man page for git-fast-export explaining
> that some arguments, in particular the ones that change the ordering of
> commits and the ones that change how commits are displayed (such as
> --graph), may have no or unexpected effects.

> I've tried writing a snippet in git-fast-export.txt, which I could include
> in the next version, if you think it seems like a reasonable approach:
>
> diff --git a/Documentation/git-fast-export.txt b/Documentation/git-fast-export.txt
> index 1978dbdc6a..34875ef01d 100644
> --- a/Documentation/git-fast-export.txt
> +++ b/Documentation/git-fast-export.txt
> @@ -157,16 +157,21 @@ by keeping the marks the same across runs.
>  [<git-rev-list-args>...]::
>         A list of arguments, acceptable to 'git rev-parse' and
>         'git rev-list', that specifies the specific objects and references
>         to export.  For example, `master~10..master` causes the
>         current master reference to be exported along with all objects
>         added since its 10th ancestor commit and (unless the
>         --reference-excluded-parents option is specified) all files
>         common to master{tilde}9 and master{tilde}10.
> ++
> +Arguments to `git rev-list` which change the _order_ in which commits are
> +traversed, such as '--reverse', as well as arguments which control how commits
> +are displayed, such as '--graph', may either have no effect or have an
> +unexpected effect on which commits are exported.

> >> +
> >> +               git fast-export main -- --first-parent >first-parent-export &&
> >> +               git fast-export main -- --first-parent --reverse >first-parent-reverse-export &&
> >> +
> >> +               git init import &&
> >> +               git -C import fast-import <first-parent-export &&
> >> +
> >> +               git -C import rev-list --format="%ad%B" --topo-order --all --no-commit-header >actual &&
> >
> > Same simplifications as above here:
> >     git -C import log --format="%ad %s" --topo-order --all >actual &&
> >
> > However, is there a reason you're using "--all" instead of "main"?
> > Although main is the only branch, which makes either output the same
> > thing, it'd be easier for folks reading to catch the equivalence if it
> > was clear you were now listing information about the same branch.
> >
>
> I guess the intent is to be completely sure that only four commits were
> exported, and no other refs made it into the new repository. I don't feel
> too strongly about it, but I think it is a slightly stronger test than
> leaving out the '--all'.

> On Mon, Dec 13, 2021 at 7:09 AM William Sprent <williams@unity3d.com> wrote:
>>
>>> However, given that it's unsafe to set revs.reverse=1 earlier, now
>>> that I think about it, isn't it also unsafe to set revs.topo_order
>>> where it is?  Someone could override it by passing --date-order to
>>> fast-export.  (It's okay if you want to leave fixing that to someone
>>> else, just thought I'd mention it while reviewing.)
>>>
>>
>> I couldn't tell you for sure if the topo_order placement is safe. I at
>> least don't see any place where topo_order itself can be toggled off in
>> revision.c.  I'm sure there exists at least one rev-list argument which
>> will cause unexpected behaviour, though.
>>
>> I agree that it would be nice to have the traversal order options be
>> assigned in the same place. I guess we have three options:
>>
>>
>>      1. Put the reverse assignment to the top (together with topo_order),
>> allowing the user to disable it with --reverse, which will cause odd
>> behaviour.
> 
> I'd call it broken rather than merely odd; more on this below.
> 
>>      2. Put the reverse assignment to the top and throw an error if the
>> user passes the --reverse option.
> 
> Might be a reasonable longer term solution if someone wants to dive
> into all the non-sensical options and mark them as such.  But I agree
> that it's slightly odd only picking one specific one when we know
> there's likely a pile of them here.
> 
>>      3. Keep the reverse assignment at the bottom, silently ignoring any
>> --reverse option.
> 
> "silently ignored" or "dismissed with prejudice"?  :-)
> 

>> I don't think any of the three options are particularly good. The first
>> one for obvious reasons. The second seems inconsistent to me as we would
>> only error on --reverse but not any of the other "nonsensical" rev-list
>> args. However, silently ignoring certain arguments does also not make
>> for a good user experience.
>>
>> I think that it might be a good idea to move up the 'reverse' assignment
>> and then add a paragraph to the man page for git-fast-export explaining
>> that some arguments, in particular the ones that change the ordering of
>> commits and the ones that change how commits are displayed (such as
>> --graph), may have no or unexpected effects.
> 
> I'd rather choose option #3, like builtin/add.c does with max_count.
> In part this is because...
> 
>> I've tried writing a snippet in git-fast-export.txt, which I could include
>> in the next version, if you think it seems like a reasonable approach:
>>
>> diff --git a/Documentation/git-fast-export.txt b/Documentation/git-fast-export.txt
>> index 1978dbdc6a..34875ef01d 100644
>> --- a/Documentation/git-fast-export.txt
>> +++ b/Documentation/git-fast-export.txt
>> @@ -157,16 +157,21 @@ by keeping the marks the same across runs.
>>   [<git-rev-list-args>...]::
>>          A list of arguments, acceptable to 'git rev-parse' and
>>          'git rev-list', that specifies the specific objects and references
>>          to export.  For example, `master~10..master` causes the
>>          current master reference to be exported along with all objects
>>          added since its 10th ancestor commit and (unless the
>>          --reference-excluded-parents option is specified) all files
>>          common to master{tilde}9 and master{tilde}10.
>> ++
>> +Arguments to `git rev-list` which change the _order_ in which commits are
>> +traversed, such as '--reverse', as well as arguments which control how commits
>> +are displayed, such as '--graph', may either have no effect or have an
>> +unexpected effect on which commits are exported.
> 
> After your patch, --reverse won't have an unexpected effect on _which_
> commits are exported, it would instead have an unexpected effect on
> _how_ commits are exported (turning _every_ commit into a root
> commit).  I'd rather just go with your option #3.
> 

>>>> +
>>>> +               git fast-export main -- --first-parent >first-parent-export &&
>>>> +               git fast-export main -- --first-parent --reverse >first-parent-reverse-export &&
>>>> +
>>>> +               git init import &&
>>>> +               git -C import fast-import <first-parent-export &&
>>>> +
>>>> +               git -C import rev-list --format="%ad%B" --topo-order --all --no-commit-header >actual &&
>>>
>>> Same simplifications as above here:
>>>      git -C import log --format="%ad %s" --topo-order --all >actual &&
>>>
>>> However, is there a reason you're using "--all" instead of "main"?
>>> Although main is the only branch, which makes either output the same
>>> thing, it'd be easier for folks reading to catch the equivalence if it
>>> was clear you were now listing information about the same branch.
>>>
>>
>> I guess the intent is to be completely sure that only four commits were
>> exported, and no other refs made it into the new repository. I don't feel
>> too strongly about it, but I think it is a slightly stronger test than
>> leaving out the '--all'.
> 
> Fair enough, '--all' works for me with that explanation.
> 

>
> From: William Sprent <williams@unity3d.com>
>
> The revision traversal machinery typically processes and returns all
> children before any parent.  fast-export needs to operate in the
> reverse fashion, handling parents before any of their children in
> order to build up the history starting from the root commit(s).  This
> would be a clear case where we could just use the revision traversal
> machinery's "reverse" option to achieve this desired affect.
>
> However, this wasn't what the code did.  It added its own array for
> queuing.  The obvious hand-rolled solution would be to just push all
> the commits into the array and then traverse afterwards, but it didn't
> quite do that either.  It instead attempted to process anything it
> could as soon as it could, and once it could, check whether it could
> process anything that had been queued.  As far as I can tell, this was
> an effort to save a little memory in the case of multiple root commits
> since it could process some commits before queueing all of them.  This
> involved some helper functions named has_unshown_parent() and
> handle_tail().  For typical invocations of fast-export, this
> alternative essentially amounted to a hand-rolled method of reversing
> the commits -- it was a bunch of work to duplicate the revision
> traversal machinery's "reverse" option.
>
> This hand-rolled reversing mechanism is actually somewhat difficult to
> reason about.  It takes some time to figure out how it ensures in
> normal cases that it will actually process all traversed commits
> (rather than just dropping some and not printing anything for them).
>
> And it turns out there are some cases where the code does drop commits
> without handling them, and not even printing an error or warning for
> the user.  Due to the has_unshown_parent() checks, some commits could
> be left in the array at the end of the "while...get_revision()" loop
> which would be unprocessed.  This could be triggered for example with
>     git fast-export main -- --first-parent
> or non-sensical traversal rules such as
>     git fast-export main -- --grep=Merge --invert-grep
>
> While most traversals that don't include all parents should likely
> trigger errors in fast-export (or at least require being used in
> combination with --reference-excluded-parents), the --first-parent
> traversal is at least reasonable and it'd be nice if it didn't just drop
> commits. It'd also be nice for future readers of the code to have a
> simpler "reverse traversal" mechanism. Use the "reverse" option of the
> revision traversal machinery to achieve both.
>
> Even for the non-sensical traversal flags like the --grep one above,
> this would be an improvement. For example, in that case, the code
> previously would have silently truncated history to only those commits
> that do not have an ancestor containing "Merge" in their commit message.
> After this code change, that case would include all commits without
> "Merge" in their commit message -- but any commit that previously had a
> "Merge"-mentioning parent would lose that parent
> (likely resulting in many new root commits). While the new behavior is
> still odd, it is at least understandable given that
> --reference-excluded-parents is not the default.
>
> Signed-off-by: William Sprent <williams@unity3d.com>
> ---
>     fast-export: fix surprising behavior with --first-parent
>
>     Hi,
>
>     Here's a revised version of my previously submitted patch regarding
>     fast-export and how it reacts to the --first-parent flag.
>
>     Changes since v2:
>
>      * Changed commit message to include the detailed description of the
>        problem area as suggested by Elijah. I went back and forth with my
>        self about whether the message needs some "lead in", but it ended up
>        getting long without adding much.

>      * Cleaned up test such that the comparison with the --reverse output is
>        just below where it is generated.
>      * In test, moved all usages of --no-ff to just after 'git merge' .
>      * In test, replaced long 'git rev-list' incantation with simpler 'git
>        log' format.
>
>     Changes since v1:
>
>      * Moved revs.reverse assignment down to similar assignments below.
>      * Removed braces around single statement while loop.
>      * The test now only changes directory inside a sub-shell.
>      * Applied stylistic feedback on test such as: making redirections be on
>        the form >FILE etc.
>
>     There were questions raised about whether it makes sense at all for
>     fast-export to simply accept all git rev-list arguments whether they
>     have an effect or not - in particular for a flag like --reverse. I think
>     I agree that it is questionable behavior, or at least questionably
>     documented, but I also think it is out of scope for this change.
>
>     I did consider teaching fast-export to complain if given --reverse, but
>     it seemed inconsistent to me as it will gladly accept every other
>     rev-list argument (for example, "git fast-export HEAD --show-signature
>     --graph" works just fine).
>
>     Original Message: I've noticed that git fast-export exhibits some odd
>     behavior when passed the --first-parent flag. In the repository I was
>     working on, it would only output the initial commit before exiting.
>     Moreover, adding the --reverse flag causes it to behave differently and
>     instead output all commits in the first parent line that only have one
>     parent. My expectation is more or less that git fast-export should
>     output the same set of commits as git rev-list would output given the
>     same arguments, which matches how it acts when given revision ranges.
>
>     It seems like this behavior comes from the fact that has_unshown_parents
>     will never be false for any merge commits encountered when fast-export
>     is called with --first-parent. This causes the while loop to follow the
>     pattern of pushing all commits into the "commits" queue until the
>     initial commit is encountered, at which point it calls handle_tail which
>     falls through on the first merge commit, causing most of the commits to
>     be unhandled.
>
>     My impression is that this logic only serves to ensure that parents are
>     processed before their children, so in my patch I've opted to fix the
>     issue by delegating that responsibility to revision.c by adding the
>     reverse flag before performing the revision walk. From what I can see,
>     this should be equivalent to what the previous logic is trying to
>     achieve, but I can also see that there could be risk in these changes.
>
> Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-1084%2Fwilliams-unity%2Ffast-export%2Ffirst-parent-issues-v3
> Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1084/williams-unity/fast-export/first-parent-issues-v3
> Pull-Request: https://github.com/gitgitgadget/git/pull/1084
>
> Range-diff vs v2:
>
>  1:  af552f37dbe ! 1:  312255260b1 fast-export: fix surprising behavior with --first-parent
>      @@ Metadata
>        ## Commit message ##
>           fast-export: fix surprising behavior with --first-parent
>
>      -    When invoking git-fast-export with the --first-parent flag on a branch
>      -    with merges, fast-export would early-out on processing the first merge
>      -    on the branch. If combined with --reverse, fast-export would instead
>      -    output all single parent commits on the branch.
>      +    The revision traversal machinery typically processes and returns all
>      +    children before any parent.  fast-export needs to operate in the
>      +    reverse fashion, handling parents before any of their children in
>      +    order to build up the history starting from the root commit(s).  This
>      +    would be a clear case where we could just use the revision traversal
>      +    machinery's "reverse" option to achieve this desired affect.
>
>      -    This commit makes fast-export output the same commits as rev-list
>      -    --first-parent, and makes --reverse not have an effect on which commits
>      -    are output.
>      +    However, this wasn't what the code did.  It added its own array for
>      +    queuing.  The obvious hand-rolled solution would be to just push all
>      +    the commits into the array and then traverse afterwards, but it didn't
>      +    quite do that either.  It instead attempted to process anything it
>      +    could as soon as it could, and once it could, check whether it could
>      +    process anything that had been queued.  As far as I can tell, this was
>      +    an effort to save a little memory in the case of multiple root commits
>      +    since it could process some commits before queueing all of them.  This
>      +    involved some helper functions named has_unshown_parent() and
>      +    handle_tail().  For typical invocations of fast-export, this
>      +    alternative essentially amounted to a hand-rolled method of reversing
>      +    the commits -- it was a bunch of work to duplicate the revision
>      +    traversal machinery's "reverse" option.
>
>      -    The fix involves removing logic within fast-export which was responsible
>      -    for ensuring that parents are processed before their children, which was
>      -    what was exiting early due to missing second parents. This is replaced
>      -    by setting 'reverse = 1' before revision walking, which, in conjuction
>      -    with topo_order, allows for delegating the ordering of commits to
>      -    revision.c. The reverse flag is set after parsing rev-list arguments to
>      -    avoid having it disabled.
>      +    This hand-rolled reversing mechanism is actually somewhat difficult to
>      +    reason about.  It takes some time to figure out how it ensures in
>      +    normal cases that it will actually process all traversed commits
>      +    (rather than just dropping some and not printing anything for them).
>      +
>      +    And it turns out there are some cases where the code does drop commits
>      +    without handling them, and not even printing an error or warning for
>      +    the user.  Due to the has_unshown_parent() checks, some commits could
>      +    be left in the array at the end of the "while...get_revision()" loop
>      +    which would be unprocessed.  This could be triggered for example with
>      +        git fast-export main -- --first-parent
>      +    or non-sensical traversal rules such as
>      +        git fast-export main -- --grep=Merge --invert-grep
>      +
>      +    While most traversals that don't include all parents should likely
>      +    trigger errors in fast-export (or at least require being used in
>      +    combination with --reference-excluded-parents), the --first-parent
>      +    traversal is at least reasonable and it'd be nice if it didn't just drop
>      +    commits. It'd also be nice for future readers of the code to have a
>      +    simpler "reverse traversal" mechanism. Use the "reverse" option of the
>      +    revision traversal machinery to achieve both.
>      +
>      +    Even for the non-sensical traversal flags like the --grep one above,
>      +    this would be an improvement. For example, in that case, the code
>      +    previously would have silently truncated history to only those commits
>      +    that do not have an ancestor containing "Merge" in their commit message.
>      +    After this code change, that case would include all commits without
>      +    "Merge" in their commit message -- but any commit that previously had a
>      +    "Merge"-mentioning parent would lose that parent
>      +    (likely resulting in many new root commits). While the new behavior is
>      +    still odd, it is at least understandable given that
>      +    --reference-excluded-parents is not the default.
>
>           Signed-off-by: William Sprent <williams@unity3d.com>
>
>      @@ t/t9350-fast-export.sh: test_expect_success 'merge commit gets exported with --i
>       +         git checkout -b topic1 &&
>       +         test_commit B &&
>       +         git checkout main &&
>      -+         git merge topic1 --no-ff &&
>      ++         git merge --no-ff topic1 &&
>       +
>       +         git checkout -b topic2 &&
>       +         test_commit C &&
>       +         git checkout main &&
>      -+         git merge topic2 --no-ff &&
>      ++         git merge --no-ff topic2 &&
>       +
>       +         test_commit D &&
>       +
>      -+         git rev-list --format="%ad%B" --first-parent --topo-order --no-commit-header main >expected &&
>      -+
>       +         git fast-export main -- --first-parent >first-parent-export &&
>       +         git fast-export main -- --first-parent --reverse >first-parent-reverse-export &&
>      ++         test_cmp first-parent-export first-parent-reverse-export &&
>       +
>       +         git init import &&
>       +         git -C import fast-import <first-parent-export &&
>       +
>      -+         git -C import rev-list --format="%ad%B" --topo-order --all --no-commit-header >actual &&
>      -+         git -C import rev-list --all >tmp &&
>      -+
>      -+         test_line_count = 4 tmp &&
>      ++         git log --format="%ad %s" --first-parent main >expected &&
>      ++         git -C import log --format="%ad %s" --all >actual &&
>       +         test_cmp expected actual &&
>      -+         test_cmp first-parent-export first-parent-reverse-export
>      ++         test_line_count = 4 actual
>       + )
>       +'
>       +
>
>
>  builtin/fast-export.c  | 40 ++++------------------------------------
>  t/t9350-fast-export.sh | 32 ++++++++++++++++++++++++++++++++
>  2 files changed, 36 insertions(+), 36 deletions(-)
>
> diff --git a/builtin/fast-export.c b/builtin/fast-export.c
> index 8e2caf72819..cb1d6473f12 100644
> --- a/builtin/fast-export.c
> +++ b/builtin/fast-export.c
> @@ -107,18 +107,6 @@ static int parse_opt_reencode_mode(const struct option *opt,
>
>  static struct decoration idnums;
>  static uint32_t last_idnum;
> -
> -static int has_unshown_parent(struct commit *commit)
> -{
> -       struct commit_list *parent;
> -
> -       for (parent = commit->parents; parent; parent = parent->next)
> -               if (!(parent->item->object.flags & SHOWN) &&
> -                   !(parent->item->object.flags & UNINTERESTING))
> -                       return 1;
> -       return 0;
> -}
> -
>  struct anonymized_entry {
>         struct hashmap_entry hash;
>         const char *anon;
> @@ -752,20 +740,6 @@ static char *anonymize_tag(void *data)
>         return strbuf_detach(&out, NULL);
>  }
>
> -static void handle_tail(struct object_array *commits, struct rev_info *revs,
> -                       struct string_list *paths_of_changed_objects)
> -{
> -       struct commit *commit;
> -       while (commits->nr) {
> -               commit = (struct commit *)object_array_pop(commits);
> -               if (has_unshown_parent(commit)) {
> -                       /* Queue again, to be handled later */
> -                       add_object_array(&commit->object, NULL, commits);
> -                       return;
> -               }
> -               handle_commit(commit, revs, paths_of_changed_objects);
> -       }
> -}
>
>  static void handle_tag(const char *name, struct tag *tag)
>  {
> @@ -1185,7 +1159,6 @@ static int parse_opt_anonymize_map(const struct option *opt,
>  int cmd_fast_export(int argc, const char **argv, const char *prefix)
>  {
>         struct rev_info revs;
> -       struct object_array commits = OBJECT_ARRAY_INIT;
>         struct commit *commit;
>         char *export_filename = NULL,
>              *import_filename = NULL,
> @@ -1283,18 +1256,13 @@ int cmd_fast_export(int argc, const char **argv, const char *prefix)
>
>         if (prepare_revision_walk(&revs))
>                 die("revision walk setup failed");
> +
> +       revs.reverse = 1;
>         revs.diffopt.format_callback = show_filemodify;
>         revs.diffopt.format_callback_data = &paths_of_changed_objects;
>         revs.diffopt.flags.recursive = 1;
> -       while ((commit = get_revision(&revs))) {
> -               if (has_unshown_parent(commit)) {
> -                       add_object_array(&commit->object, NULL, &commits);
> -               }
> -               else {
> -                       handle_commit(commit, &revs, &paths_of_changed_objects);
> -                       handle_tail(&commits, &revs, &paths_of_changed_objects);
> -               }
> -       }
> +       while ((commit = get_revision(&revs)))
> +               handle_commit(commit, &revs, &paths_of_changed_objects);
>
>         handle_tags_and_duplicates(&extra_refs);
>         handle_tags_and_duplicates(&tag_refs);
> diff --git a/t/t9350-fast-export.sh b/t/t9350-fast-export.sh
> index 409b48e2442..7b7a18dd2c1 100755
> --- a/t/t9350-fast-export.sh
> +++ b/t/t9350-fast-export.sh
> @@ -750,4 +750,36 @@ test_expect_success 'merge commit gets exported with --import-marks' '
>         )
>  '
>
> +
> +test_expect_success 'fast-export --first-parent outputs all revisions output by revision walk' '
> +       git init first-parent &&
> +       (
> +               cd first-parent &&
> +               test_commit A &&
> +               git checkout -b topic1 &&
> +               test_commit B &&
> +               git checkout main &&
> +               git merge --no-ff topic1 &&
> +
> +               git checkout -b topic2 &&
> +               test_commit C &&
> +               git checkout main &&
> +               git merge --no-ff topic2 &&
> +
> +               test_commit D &&
> +
> +               git fast-export main -- --first-parent >first-parent-export &&
> +               git fast-export main -- --first-parent --reverse >first-parent-reverse-export &&
> +               test_cmp first-parent-export first-parent-reverse-export &&
> +
> +               git init import &&
> +               git -C import fast-import <first-parent-export &&
> +
> +               git log --format="%ad %s" --first-parent main >expected &&
> +               git -C import log --format="%ad %s" --all >actual &&
> +               test_cmp expected actual &&
> +               test_line_count = 4 actual
> +       )
> +'
> +
>  test_done
>
> base-commit: cd3e606211bb1cf8bc57f7d76bab98cc17a150bc

>>      * Changed commit message to include the detailed description of the
>>        problem area as suggested by Elijah. I went back and forth with my
>>        self about whether the message needs some "lead in", but it ended up
>>        getting long without adding much.
>
> If it feels weird quoting someone else so extensively and just using
> their words for the commit message, we've used a "Commit-message-by:"
> trailer in the past; that could be useful here.

> Elijah Newren <newren@gmail.com> writes:
> 
>>>       * Changed commit message to include the detailed description of the
>>>         problem area as suggested by Elijah. I went back and forth with my
>>>         self about whether the message needs some "lead in", but it ended up
>>>         getting long without adding much.
>>
>> If it feels weird quoting someone else so extensively and just using
>> their words for the commit message, we've used a "Commit-message-by:"
>> trailer in the past; that could be useful here.
> 
> I do not mind tweaking the copy I already have with "Helped-by"
> myself, while ...
> 
>> This version looks good to me:
>>
>> Reviewed-by: Elijah Newren <newren@gmail.com>
> 
> ... adding this one before merging the result to 'next'.
> 
> Thanks, both.