{"thread":{"id":"55507","subject":"[PATCH] git-rev-list: add --exclude-path-first-parent flag","startedAt":"2021-04-17T00:15:32Z","lastAt":"2021-12-11T02:13:19Z","messageCount":9,"participants":["Jerry Zhang","Junio C Hamano","Felipe Contreras"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"422140","messageId":"20210417001525.19960-1-jerry@skydio.com","threadId":"55507","inReplyTo":null,"subject":"[PATCH] git-rev-list: add --exclude-path-first-parent flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2021-04-17T00:15:25Z","receivedAt":"2021-04-17T00:15:32Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"Add the --exclude-path-first-parent flag,\nwhich works similarly to --first-parent,\nbut affects only the graph traversal for\nthe set of commits being excluded.\n\n   -A-------E-HEAD\n     \\     /\n      B-C-D\n\nIn this example, the goal is to return the\nset {B, C, D} which represents a working\nbranch that has been merged into main branch\nE. `git rev-list D ^E` will end up returning\nno commits since the exclude path eliminates\nD and its ancestors.\n`git rev-list --exclude-path-first-parent D ^E`\nhowever will return {B, C, D} as desired.\n\nAdd docs for the new flag, and clarify the\ndoc for --first-parent to indicate that it\napplies to traversing the set of included\ncommits only. The semantics of existing flags\nhowever have not changed.\n\nSigned-off-by: Jerry Zhang <jerry@skydio.com>\n---\n Documentation/rev-list-options.txt | 21 ++++++++++++++-------\n blame.c                            |  2 +-\n revision.c                         | 30 ++++++++++++++++++++----------\n revision.h                         |  3 ++-\n shallow.c                          |  2 +-\n t/t6012-rev-list-simplify.sh       | 18 ++++++++++++------\n 6 files changed, 50 insertions(+), 26 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex b1c8f86c6e..681d6649b4 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -122,19 +122,26 @@ again.  Equivalent forms are `--min-parents=0` (any commit has 0 or more\n parents) and `--max-parents=-1` (negative numbers denote no upper limit).\n \n --first-parent::\n-\tFollow only the first parent commit upon seeing a merge\n-\tcommit.  This option can give a better overview when\n-\tviewing the evolution of a particular topic branch,\n-\tbecause merges into a topic branch tend to be only about\n-\tadjusting to updated upstream from time to time, and\n-\tthis option allows you to ignore the individual commits\n-\tbrought in to your history by such a merge.\n+\tWhen finding commits to include, follow only the first\n+\tparent commit upon seeing a merge commit.  This option\n+\tcan give a better overview when viewing the evolution of\n+\ta particular topic branch, because merges into a topic\n+\tbranch tend to be only about adjusting to updated upstream\n+\tfrom time to time, and this option allows you to ignore\n+\tthe individual commits brought in to your history by such\n+\ta merge.\n ifdef::git-log[]\n +\n This option also changes default diff format for merge commits\n to `first-parent`, see `--diff-merges=first-parent` for details.\n endif::git-log[]\n \n+--exclude-path-first-parent::\n+\tWhen finding commits to exclude, follow only the first\n+\tparent commit upon seeing a merge commit.  This causes\n+\texclusions to exclude only commits on that branch itself\n+\tand not those brought in by a merge.\n+\n --not::\n \tReverses the meaning of the '{caret}' prefix (or lack thereof)\n \tfor all following revision specifiers, up to the next `--not`.\ndiff --git a/blame.c b/blame.c\nindex 5018bb8fb2..8354dc0252 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -2615,7 +2615,7 @@ void assign_blame(struct blame_scoreboard *sb, int opt)\n \t\telse {\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \t\t\tif (commit->object.parsed)\n-\t\t\t\tmark_parents_uninteresting(commit);\n+\t\t\t\tmark_parents_uninteresting(sb->revs, commit);\n \t\t}\n \t\t/* treat root commit as boundary */\n \t\tif (!commit->parents && !sb->show_root)\ndiff --git a/revision.c b/revision.c\nindex 553c0faa9b..e1deb3f194 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -268,7 +268,7 @@ static void commit_stack_clear(struct commit_stack *stack)\n \tstack->nr = stack->alloc = 0;\n }\n \n-static void mark_one_parent_uninteresting(struct commit *commit,\n+static void mark_one_parent_uninteresting(struct rev_info *revs, struct commit *commit,\n \t\t\t\t\t  struct commit_stack *pending)\n {\n \tstruct commit_list *l;\n@@ -285,20 +285,26 @@ static void mark_one_parent_uninteresting(struct commit *commit,\n \t * wasn't uninteresting), in which case we need\n \t * to mark its parents recursively too..\n \t */\n-\tfor (l = commit->parents; l; l = l->next)\n+\tfor (l = commit->parents; l; l = l->next) {\n \t\tcommit_stack_push(pending, l->item);\n+\t\tif (revs && revs->exclude_path_first_parent_only)\n+\t\t\tbreak;\n+\t}\n }\n \n-void mark_parents_uninteresting(struct commit *commit)\n+void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_stack pending = COMMIT_STACK_INIT;\n \tstruct commit_list *l;\n \n-\tfor (l = commit->parents; l; l = l->next)\n-\t\tmark_one_parent_uninteresting(l->item, &pending);\n+\tfor (l = commit->parents; l; l = l->next) {\n+\t\tmark_one_parent_uninteresting(revs, l->item, &pending);\n+\t\tif (revs && revs->exclude_path_first_parent_only)\n+\t\t\tbreak;\n+\t}\n \n \twhile (pending.nr > 0)\n-\t\tmark_one_parent_uninteresting(commit_stack_pop(&pending),\n+\t\tmark_one_parent_uninteresting(revs, commit_stack_pop(&pending),\n \t\t\t\t\t      &pending);\n \n \tcommit_stack_clear(&pending);\n@@ -437,7 +443,7 @@ static struct commit *handle_commit(struct rev_info *revs,\n \t\tif (repo_parse_commit(revs->repo, commit) < 0)\n \t\t\tdie(\"unable to parse commit %s\", name);\n \t\tif (flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tmark_parents_uninteresting(revs, commit);\n \n \t\t\tif (!revs->topo_order || !generation_numbers_enabled(the_repository))\n \t\t\t\trevs->limited = 1;\n@@ -1120,7 +1126,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\tif (repo_parse_commit_gently(revs->repo, p, 1) < 0)\n \t\t\t\tcontinue;\n \t\t\tif (p->parents)\n-\t\t\t\tmark_parents_uninteresting(p);\n+\t\t\t\tmark_parents_uninteresting(revs, p);\n \t\t\tif (p->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= SEEN;\n@@ -1128,6 +1134,8 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\t\tcommit_list_insert_by_date(p, list);\n \t\t\tif (queue)\n \t\t\t\tprio_queue_put(queue, p);\n+\t\t\tif (revs->exclude_path_first_parent_only)\n+\t\t\t\tbreak;\n \t\t}\n \t\treturn 0;\n \t}\n@@ -1418,7 +1426,7 @@ static int limit_list(struct rev_info *revs)\n \t\tif (process_parents(revs, commit, &list, NULL) < 0)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tmark_parents_uninteresting(revs, commit);\n \t\t\tslop = still_interesting(list, date, slop, &interesting_cache);\n \t\t\tif (slop)\n \t\t\t\tcontinue;\n@@ -2214,6 +2222,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\treturn argcount;\n \t} else if (!strcmp(arg, \"--first-parent\")) {\n \t\trevs->first_parent_only = 1;\n+\t} else if (!strcmp(arg, \"--exclude-path-first-parent\")) {\n+\t\trevs->exclude_path_first_parent_only = 1;\n \t} else if (!strcmp(arg, \"--ancestry-path\")) {\n \t\trevs->ancestry_path = 1;\n \t\trevs->simplify_history = 0;\n@@ -3341,7 +3351,7 @@ static void explore_walk_step(struct rev_info *revs)\n \t\treturn;\n \n \tif (c->object.flags & UNINTERESTING)\n-\t\tmark_parents_uninteresting(c);\n+\t\tmark_parents_uninteresting(revs, c);\n \n \tfor (p = c->parents; p; p = p->next)\n \t\ttest_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);\ndiff --git a/revision.h b/revision.h\nindex a24f72dcd1..712710ed62 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -164,6 +164,7 @@ struct rev_info {\n \t\t\tbisect:1,\n \t\t\tancestry_path:1,\n \t\t\tfirst_parent_only:1,\n+\t\t\texclude_path_first_parent_only:1,\n \t\t\tline_level_traverse:1,\n \t\t\ttree_blobs_in_commit_order:1,\n \n@@ -405,7 +406,7 @@ const char *get_revision_mark(const struct rev_info *revs,\n void put_revision_mark(const struct rev_info *revs,\n \t\t       const struct commit *commit);\n \n-void mark_parents_uninteresting(struct commit *commit);\n+void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit);\n void mark_tree_uninteresting(struct repository *r, struct tree *tree);\n void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees);\n \ndiff --git a/shallow.c b/shallow.c\nindex 9ed18eb884..71e5876f37 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -603,7 +603,7 @@ static int mark_uninteresting(const char *refname, const struct object_id *oid,\n \tif (!commit)\n \t\treturn 0;\n \tcommit->object.flags |= UNINTERESTING;\n-\tmark_parents_uninteresting(commit);\n+\tmark_parents_uninteresting(NULL, commit);\n \treturn 0;\n }\n \ndiff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\nindex 4f7fa8b6c0..aa8220f3a4 100755\n--- a/t/t6012-rev-list-simplify.sh\n+++ b/t/t6012-rev-list-simplify.sh\n@@ -16,13 +16,12 @@ unnote () {\n }\n \n #\n-# Create a test repo with interesting commit graph:\n+# Create a test repo with an interesting commit graph:\n #\n-# A--B----------G--H--I--K--L\n-#  \\  \\           /     /\n-#   \\  \\         /     /\n-#    C------E---F     J\n-#        \\_/\n+# A-----B-----G--H--I--K--L\n+#  \\     \\      /     /\n+#   \\     \\    /     /\n+#    C--D--E--F     J\n #\n # The commits are laid out from left-to-right starting with\n # the root commit A and terminating at the tip commit L.\n@@ -142,6 +141,13 @@ check_result 'I B A' --author-date-order -- file\n check_result 'H' --first-parent -- another-file\n check_result 'H' --first-parent --topo-order -- another-file\n \n+check_result 'L K I H G B A' --first-parent L\n+check_result 'F E D C' --exclude-path-first-parent F ^L\n+check_result '' F ^L\n+check_result 'L K I H G J' L ^F\n+check_result 'L K I H G B J' --exclude-path-first-parent L ^F\n+check_result 'L K I H G B' --exclude-path-first-parent --first-parent L ^F\n+\n check_result 'E C B A' --full-history E -- lost\n test_expect_success 'full history simplification without parent' '\n \tprintf \"%s\\n\" E C B A >expect &&\n-- \n2.29.0\n\n"},{"id":"422142","messageId":"xmqqzgxxivrb.fsf@gitster.g","threadId":"55507","inReplyTo":"20210417001525.19960-1-jerry@skydio.com","subject":"Re: [PATCH] git-rev-list: add --exclude-path-first-parent flag","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-04-17T00:45:44Z","receivedAt":"2021-04-17T00:45:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jerry Zhang <jerry@skydio.com> writes:\n\n> Add the --exclude-path-first-parent flag,\n> which works similarly to --first-parent,\n> but affects only the graph traversal for\n> the set of commits being excluded.\n>\n>    -A-------E-HEAD\n>      \\     /\n>       B-C-D\n>\n> In this example, the goal is to return the\n> set {B, C, D} which represents a working\n> branch that has been merged into main branch\n> E. `git rev-list D ^E` will end up returning\n> no commits since the exclude path eliminates\n> D and its ancestors.\n> `git rev-list --exclude-path-first-parent D ^E`\n> however will return {B, C, D} as desired.\n\nIt is not clera why you want to have this, instead of doing a more\nobvious \"D..E^\".  Even better is \"E^..E\", which is often what you\nwant when viewing a history like my 'seen' that is a straight-line\ninto which tips of branches are merged.\n\nE^..E (or doing the same for any commit on the mainline in such a\nhistory whose first-parent chain solely consists of merges) would\nshow the list of the commits that came from the side branch that was\nmerged, plus the merge commit, where the committer who created a\nmerge would hava a chance to give a summary of what happened on the\nside branch.\n"},{"id":"422143","messageId":"CAMKO5Cutas2BM_CTHTJs_O9NSp2Vyn-bK0jV0K758eq5M6-Oag@mail.gmail.com","threadId":"55507","inReplyTo":"xmqqzgxxivrb.fsf@gitster.g","subject":"Re: [PATCH] git-rev-list: add --exclude-path-first-parent flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2021-04-17T01:07:18Z","receivedAt":"2021-04-17T01:07:31Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"On Fri, Apr 16, 2021 at 5:45 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Jerry Zhang <jerry@skydio.com> writes:\n>\n> > Add the --exclude-path-first-parent flag,\n> > which works similarly to --first-parent,\n> > but affects only the graph traversal for\n> > the set of commits being excluded.\n> >\n> >    -A-------E-HEAD\n> >      \\     /\n> >       B-C-D\n> >\n> > In this example, the goal is to return the\n> > set {B, C, D} which represents a working\n> > branch that has been merged into main branch\n> > E. `git rev-list D ^E` will end up returning\n> > no commits since the exclude path eliminates\n> > D and its ancestors.\n> > `git rev-list --exclude-path-first-parent D ^E`\n> > however will return {B, C, D} as desired.\n>\n> It is not clera why you want to have this, instead of doing a more\n> obvious \"D..E^\".  Even better is \"E^..E\", which is often what you\n> want when viewing a history like my 'seen' that is a straight-line\n> into which tips of branches are merged.\nMy motivation is to find the point at which a release branch forked off from\na main branch, even though the release branch could have been merged\ninto the main branch multiple times since it was forked off.\n\nIf we add another merge from release to main, it will be more clear\nthat those give different results:\n\n        -A-------E-F-main\n          \\   / /\n           B-C-D-release\n\n`git rev-list --exclude-path-first-parent release ^main` returns {B, C, D}.\nI've added commit F to show that we don't necessarily have info on E,\nthere could be many commits between it and the tip of main.\n\n`git rev-list E^..E` returns {E, D} only, it depends on us knowing E and\nloses all the commits after a merge from release to main.\n\nI could do `git rev-parse (git rev-list --first-parent main\n^release)^` and I'd get\nA, but then I have to run `git rev-list D ^A` to get the set {B, C, D},\nwhereas the --exclude-path-first-parent invocation gives exactly\nwhat I want in one invocation. I'm sure there's more use-cases\nI'm not able to think of.\n\n>\n> E^..E (or doing the same for any commit on the mainline in such a\n> history whose first-parent chain solely consists of merges) would\n> show the list of the commits that came from the side branch that was\n> merged, plus the merge commit, where the committer who created a\n> merge would hava a chance to give a summary of what happened on the\n> side branch.\n"},{"id":"422148","messageId":"607a5f701977c_18dc520893@natae.notmuch","threadId":"55507","inReplyTo":"CAMKO5Cutas2BM_CTHTJs_O9NSp2Vyn-bK0jV0K758eq5M6-Oag@mail.gmail.com","subject":"Re: [PATCH] git-rev-list: add --exclude-path-first-parent flag","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2021-04-17T04:09:20Z","receivedAt":"2021-04-17T04:09:29Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"Jerry Zhang wrote:\n> My motivation is to find the point at which a release branch forked off from\n> a main branch, even though the release branch could have been merged\n> into the main branch multiple times since it was forked off.\n\nAs far as I'm aware this is precisely the only advantage of Mercurial\nover Git.\n\nLast time I checked the only way to actually find out the fork point\nconsidering multiple corner cases was to directly store it.\n\nPerhaps --exclude-path-first-parent would be a good approximation.\n\n-- \nFelipe Contreras\n"},{"id":"422150","messageId":"xmqqczutiddk.fsf@gitster.g","threadId":"55507","inReplyTo":"CAMKO5Cutas2BM_CTHTJs_O9NSp2Vyn-bK0jV0K758eq5M6-Oag@mail.gmail.com","subject":"Re: [PATCH] git-rev-list: add --exclude-path-first-parent flag","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2021-04-17T07:22:47Z","receivedAt":"2021-04-17T07:22:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jerry Zhang <jerry@skydio.com> writes:\n\n> On Fri, Apr 16, 2021 at 5:45 PM Junio C Hamano <gitster@pobox.com> wrote:\n>>\n>> Jerry Zhang <jerry@skydio.com> writes:\n>>\n>> > Add the --exclude-path-first-parent flag,\n>> > which works similarly to --first-parent,\n>> > but affects only the graph traversal for\n>> > the set of commits being excluded.\n>> >\n>> >    -A-------E-HEAD\n>> >      \\     /\n>> >       B-C-D\n>> >\n>> > In this example, the goal is to return the\n>> > set {B, C, D} which represents a working\n>> > branch that has been merged into main branch\n>> > E. `git rev-list D ^E` will end up returning\n>> > no commits since the exclude path eliminates\n>> > D and its ancestors.\n>> > `git rev-list --exclude-path-first-parent D ^E`\n>> > however will return {B, C, D} as desired.\n>>\n>> It is not clera why you want to have this, instead of doing a more\n>> obvious \"D..E^\".  Even better is \"E^..E\", which is often what you\n>> want when viewing a history like my 'seen' that is a straight-line\n>> into which tips of branches are merged.\n> My motivation is to find the point at which a release branch forked off from\n> a main branch, even though the release branch could have been merged\n> into the main branch multiple times since it was forked off.\n>\n> If we add another merge from release to main, it will be more clear\n> that those give different results:\n>\n>         -A-----E-F-main\n>           \\   / /\n>            B-C-D-release\n>\n> `git rev-list --exclude-path-first-parent release ^main` returns {B, C, D}.\n> I've added commit F to show that we don't necessarily have info on E,\n> there could be many commits between it and the tip of main.\n\nOK, you meant to deal with repeated merges into integration branch.\n\nSo the idea is to just name the end point merge, say F (you also\ncould name D as the starting point, but see below), and \n\n - initially mark its first parent as UNINTERESTING (i.e. E), and\n   other parents as INTERESTING (i.e. D).\n\n - run the revision traversal machinery, but when propagating the\n   UNINTERESTING bit, give it only to the first parent.  The second\n   and later parents won't become UNINTERESTING.\n\n - stop after we exhaust INTERESTING commits.\n\nIt would probably work for your idealized topology, but I do not\nknow what happens when there are criss-cross merges.  In the revised\npicture, you are merging down from the B-C-D chain into the\nmainline, but once the B-C-D chain becomes longer and diverges too\nmuch from the mainline, it becomes tempting to break the \"merge only\nin one direction\" discipline and merge back from the mainline, to\n\"catch up\", and such a merge will have the history of B-C-D line of\ndevelopment as its first parent.  Would that screw up the selection\nof which line of development is uninteresting?\n\n>> > Add the --exclude-path-first-parent flag,\n>> > which works similarly to --first-parent,\n>> > but affects only the graph traversal for\n>> > the set of commits being excluded.\n>> >\n>> >    -A-------E-HEAD\n>> >      \\     /\n>> >       B-C-D\n\nIn any case, it was totally unclear from the proposed log messsage,\nand the overlong option name that does not say much did not help me\nguess what you wanted to do with it.  Specifically, it is not clear\nwhat \"exclude\" means (we do not usually use the word in the context\nof revision traversal), and when we talk about \"path\" in the context\nof revision traversal, we almost always mean the paths to the files,\ni.e. pathspec that limits and simplifies the shape of the history.\nAlso, it claims that it works similarly to --first-parent, but what\nyou are doing is to propagate UNINTERESTING bit on the first-parent\nchain, which ends up showing the side branch (i.e. B-C-D chain),\nwithout showing the commits on the first-parent chain (A and E).\n\nWhat are the words that convey the idea behind this operation\nclearly at the conceptual level?  Let's think aloud to see if we can\ncome up with a better name.\n\n * first parents are unintertesting\n\n * show commits on side branch(es)\n\n * follow side branch.\n\nI think that is closer to the problem you are solving, if I\nunderstand what you wrote above correctly.\n\nPerhaps --show-side-branch or --follow-side-branch?  I dunno.\n"},{"id":"422508","messageId":"CAMKO5Cu68cnUu6UEuwQSHoFQ31g9g4TtYgy5vpe35cr90cETXw@mail.gmail.com","threadId":"55507","inReplyTo":"xmqqczutiddk.fsf@gitster.g","subject":"Re: [PATCH] git-rev-list: add --exclude-path-first-parent flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2021-04-21T00:16:59Z","receivedAt":"2021-04-21T00:17:37Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"On Sat, Apr 17, 2021 at 12:22 AM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Jerry Zhang <jerry@skydio.com> writes:\n>\n> > On Fri, Apr 16, 2021 at 5:45 PM Junio C Hamano <gitster@pobox.com> wrote:\n> >>\n> >> Jerry Zhang <jerry@skydio.com> writes:\n> >>\n> >> > Add the --exclude-path-first-parent flag,\n> >> > which works similarly to --first-parent,\n> >> > but affects only the graph traversal for\n> >> > the set of commits being excluded.\n> >> >\n> >> >    -A-------E-HEAD\n> >> >      \\     /\n> >> >       B-C-D\n> >> >\n> >> > In this example, the goal is to return the\n> >> > set {B, C, D} which represents a working\n> >> > branch that has been merged into main branch\n> >> > E. `git rev-list D ^E` will end up returning\n> >> > no commits since the exclude path eliminates\n> >> > D and its ancestors.\n> >> > `git rev-list --exclude-path-first-parent D ^E`\n> >> > however will return {B, C, D} as desired.\n> >>\n> >> It is not clera why you want to have this, instead of doing a more\n> >> obvious \"D..E^\".  Even better is \"E^..E\", which is often what you\n> >> want when viewing a history like my 'seen' that is a straight-line\n> >> into which tips of branches are merged.\n> > My motivation is to find the point at which a release branch forked off from\n> > a main branch, even though the release branch could have been merged\n> > into the main branch multiple times since it was forked off.\n> >\n> > If we add another merge from release to main, it will be more clear\n> > that those give different results:\n> >\n> >         -A-----E-F-main\n> >           \\   / /\n> >            B-C-D-release\n> >\n> > `git rev-list --exclude-path-first-parent release ^main` returns {B, C, D}.\n> > I've added commit F to show that we don't necessarily have info on E,\n> > there could be many commits between it and the tip of main.\n>\n> OK, you meant to deal with repeated merges into integration branch.\n>\n> So the idea is to just name the end point merge, say F (you also\n> could name D as the starting point, but see below), and\n>\n>  - initially mark its first parent as UNINTERESTING (i.e. E), and\n>    other parents as INTERESTING (i.e. D).\n>\n>  - run the revision traversal machinery, but when propagating the\n>    UNINTERESTING bit, give it only to the first parent.  The second\n>    and later parents won't become UNINTERESTING.\n>\n>  - stop after we exhaust INTERESTING commits.\n>\n> It would probably work for your idealized topology, but I do not\n> know what happens when there are criss-cross merges.  In the revised\n> picture, you are merging down from the B-C-D chain into the\n> mainline, but once the B-C-D chain becomes longer and diverges too\n> much from the mainline, it becomes tempting to break the \"merge only\n> in one direction\" discipline and merge back from the mainline, to\n> \"catch up\", and such a merge will have the history of B-C-D line of\n> development as its first parent.  Would that screw up the selection\n> of which line of development is uninteresting?\nYeah this flag (as well as the --first-parent flag) is mainly only useful\nbecause \"git merge\" will always put the \"branch you're on\" as parent 1\nand the \"branch being merged in\" as parent 2. It is possible to break\nthis assumption with either commit-tree or by merging while on one\nbranch and pushing to another, but then the user should understand\nthe consequences of doing so. In our case this isn't possible because\na server handles all merges into the main branches.\n>\n> >> > Add the --exclude-path-first-parent flag,\n> >> > which works similarly to --first-parent,\n> >> > but affects only the graph traversal for\n> >> > the set of commits being excluded.\n> >> >\n> >> >    -A-------E-HEAD\n> >> >      \\     /\n> >> >       B-C-D\n>\n> In any case, it was totally unclear from the proposed log messsage,\n> and the overlong option name that does not say much did not help me\n> guess what you wanted to do with it.  Specifically, it is not clear\n> what \"exclude\" means (we do not usually use the word in the context\nExclude appears in the first paragraph of the man for git rev-list:\n\"      List commits that are reachable by following the parent\n       links from the given commit(s), but exclude commits that\n       are reachable from the one(s) given with a ^ in front of\n       them. The output is given in reverse chronological order\n       by default.\"\nIt appears 5+ more times in the man page with the same meaning.\n> of revision traversal), and when we talk about \"path\" in the context\n> of revision traversal, we almost always mean the paths to the files,\n> i.e. pathspec that limits and simplifies the shape of the history.\n\"path\" is used in the same man page for the flag \"--ancestry-path\".\nI agree that it could be ambiguous though, so perhaps \"chain\" would\nbe better.\n> Also, it claims that it works similarly to --first-parent, but what\n> you are doing is to propagate UNINTERESTING bit on the first-parent\n> chain, which ends up showing the side branch (i.e. B-C-D chain),\n> without showing the commits on the first-parent chain (A and E).\n>\n> What are the words that convey the idea behind this operation\n> clearly at the conceptual level?  Let's think aloud to see if we can\n> come up with a better name.\n>\n>  * first parents are unintertesting\n>\n>  * show commits on side branch(es)\n>\n>  * follow side branch.\n>\n> I think that is closer to the problem you are solving, if I\n> understand what you wrote above correctly.\n>\n> Perhaps --show-side-branch or --follow-side-branch?  I dunno.\nFor my particular use-case I am using it in combination with\n--first-parent and a single include and exclude commit to show the\ncommits on the \"side-branch\" of the include commit. But if you specify\nmultiple commits for either or don't use --first-parent, the behavior is\ndifferent and I don't think \"--side-branch\" describes it well in those cases.\n\nSince I don't believe I can predict all use-cases for the flag,\nI'd rather name it by what it \"does\" rather than what it is \"for\".\nIf we're concerned about length, maybe \"first-parent-not\" could\nget the meaning across:\n- for \"rev-list --first-parent A --not B\" only first parents are visited\nalong A's ancestry\n- for \"rev-list --first-parent-not A --not B\" it might be reasonable\nthat since B is a \"not\" commit, only first parents are visited along\nB's ancestry.\n\nOverall I don't think we can make a name so clear that the user\ncan avoid the man page anyway.\n"},{"id":"422512","messageId":"20210421004817.22536-1-jerry@skydio.com","threadId":"55507","inReplyTo":"20210417001525.19960-1-jerry@skydio.com","subject":"[PATCH V2] git-rev-list: add --first-parent-not flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2021-04-21T00:48:17Z","receivedAt":"2021-04-21T00:48:25Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"Add the --path-first-parent-not flag, which\ncauses the traversal of any \"not\" commits\nto visit only the first parent upon encountering\na merge commit.\n\n   -A-----E-F-G--main\n     \\   / /\n      B-C-D--topic\n\nIn this example, the goal is to return the\nset {B, C, D} which represents a topic\nbranch that has been merged into main branch.\n`git rev-list topic ^main` will end up returning\nno commits since excluding main will end up\ntraversing the commits on topic as well.\n`git rev-list --first-parent-not topic ^main`\nhowever will return {B, C, D} as desired.\n\nAdd docs for the new flag, and clarify the\ndoc for --first-parent to indicate that it\napplies to traversing the set of included\ncommits only. The semantics of existing flags\nhowever have not changed.\n\nSigned-off-by: Jerry Zhang <jerry@skydio.com>\n---\nV1->V2:\n- Shortened flag name to --first-parent-not\n- Updated example history in commit msg\n\n Documentation/rev-list-options.txt | 21 ++++++++++++++-------\n blame.c                            |  2 +-\n revision.c                         | 30 ++++++++++++++++++++----------\n revision.h                         |  3 ++-\n shallow.c                          |  2 +-\n t/t6012-rev-list-simplify.sh       | 18 ++++++++++++------\n 6 files changed, 50 insertions(+), 26 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex b1c8f86c6e..6666f13b30 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -122,19 +122,26 @@ again.  Equivalent forms are `--min-parents=0` (any commit has 0 or more\n parents) and `--max-parents=-1` (negative numbers denote no upper limit).\n \n --first-parent::\n-\tFollow only the first parent commit upon seeing a merge\n-\tcommit.  This option can give a better overview when\n-\tviewing the evolution of a particular topic branch,\n-\tbecause merges into a topic branch tend to be only about\n-\tadjusting to updated upstream from time to time, and\n-\tthis option allows you to ignore the individual commits\n-\tbrought in to your history by such a merge.\n+\tWhen finding commits to include, follow only the first\n+\tparent commit upon seeing a merge commit.  This option\n+\tcan give a better overview when viewing the evolution of\n+\ta particular topic branch, because merges into a topic\n+\tbranch tend to be only about adjusting to updated upstream\n+\tfrom time to time, and this option allows you to ignore\n+\tthe individual commits brought in to your history by such\n+\ta merge.\n ifdef::git-log[]\n +\n This option also changes default diff format for merge commits\n to `first-parent`, see `--diff-merges=first-parent` for details.\n endif::git-log[]\n \n+--first-parent-not::\n+\tWhen finding commits to exclude, follow only the first\n+\tparent commit upon seeing a merge commit.  This causes\n+\t\"not\" commits to exclude only commits on that branch itself\n+\tand not those brought in by a merge.\n+\n --not::\n \tReverses the meaning of the '{caret}' prefix (or lack thereof)\n \tfor all following revision specifiers, up to the next `--not`.\ndiff --git a/blame.c b/blame.c\nindex 5018bb8fb2..8354dc0252 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -2615,7 +2615,7 @@ void assign_blame(struct blame_scoreboard *sb, int opt)\n \t\telse {\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \t\t\tif (commit->object.parsed)\n-\t\t\t\tmark_parents_uninteresting(commit);\n+\t\t\t\tmark_parents_uninteresting(sb->revs, commit);\n \t\t}\n \t\t/* treat root commit as boundary */\n \t\tif (!commit->parents && !sb->show_root)\ndiff --git a/revision.c b/revision.c\nindex 553c0faa9b..4b87b48235 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -268,7 +268,7 @@ static void commit_stack_clear(struct commit_stack *stack)\n \tstack->nr = stack->alloc = 0;\n }\n \n-static void mark_one_parent_uninteresting(struct commit *commit,\n+static void mark_one_parent_uninteresting(struct rev_info *revs, struct commit *commit,\n \t\t\t\t\t  struct commit_stack *pending)\n {\n \tstruct commit_list *l;\n@@ -285,20 +285,26 @@ static void mark_one_parent_uninteresting(struct commit *commit,\n \t * wasn't uninteresting), in which case we need\n \t * to mark its parents recursively too..\n \t */\n-\tfor (l = commit->parents; l; l = l->next)\n+\tfor (l = commit->parents; l; l = l->next) {\n \t\tcommit_stack_push(pending, l->item);\n+\t\tif (revs && revs->first_parent_not)\n+\t\t\tbreak;\n+\t}\n }\n \n-void mark_parents_uninteresting(struct commit *commit)\n+void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_stack pending = COMMIT_STACK_INIT;\n \tstruct commit_list *l;\n \n-\tfor (l = commit->parents; l; l = l->next)\n-\t\tmark_one_parent_uninteresting(l->item, &pending);\n+\tfor (l = commit->parents; l; l = l->next) {\n+\t\tmark_one_parent_uninteresting(revs, l->item, &pending);\n+\t\tif (revs && revs->first_parent_not)\n+\t\t\tbreak;\n+\t}\n \n \twhile (pending.nr > 0)\n-\t\tmark_one_parent_uninteresting(commit_stack_pop(&pending),\n+\t\tmark_one_parent_uninteresting(revs, commit_stack_pop(&pending),\n \t\t\t\t\t      &pending);\n \n \tcommit_stack_clear(&pending);\n@@ -437,7 +443,7 @@ static struct commit *handle_commit(struct rev_info *revs,\n \t\tif (repo_parse_commit(revs->repo, commit) < 0)\n \t\t\tdie(\"unable to parse commit %s\", name);\n \t\tif (flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tmark_parents_uninteresting(revs, commit);\n \n \t\t\tif (!revs->topo_order || !generation_numbers_enabled(the_repository))\n \t\t\t\trevs->limited = 1;\n@@ -1120,7 +1126,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\tif (repo_parse_commit_gently(revs->repo, p, 1) < 0)\n \t\t\t\tcontinue;\n \t\t\tif (p->parents)\n-\t\t\t\tmark_parents_uninteresting(p);\n+\t\t\t\tmark_parents_uninteresting(revs, p);\n \t\t\tif (p->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= SEEN;\n@@ -1128,6 +1134,8 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\t\tcommit_list_insert_by_date(p, list);\n \t\t\tif (queue)\n \t\t\t\tprio_queue_put(queue, p);\n+\t\t\tif (revs->first_parent_not)\n+\t\t\t\tbreak;\n \t\t}\n \t\treturn 0;\n \t}\n@@ -1418,7 +1426,7 @@ static int limit_list(struct rev_info *revs)\n \t\tif (process_parents(revs, commit, &list, NULL) < 0)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tmark_parents_uninteresting(revs, commit);\n \t\t\tslop = still_interesting(list, date, slop, &interesting_cache);\n \t\t\tif (slop)\n \t\t\t\tcontinue;\n@@ -2214,6 +2222,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\treturn argcount;\n \t} else if (!strcmp(arg, \"--first-parent\")) {\n \t\trevs->first_parent_only = 1;\n+\t} else if (!strcmp(arg, \"--first-parent-not\")) {\n+\t\trevs->first_parent_not = 1;\n \t} else if (!strcmp(arg, \"--ancestry-path\")) {\n \t\trevs->ancestry_path = 1;\n \t\trevs->simplify_history = 0;\n@@ -3341,7 +3351,7 @@ static void explore_walk_step(struct rev_info *revs)\n \t\treturn;\n \n \tif (c->object.flags & UNINTERESTING)\n-\t\tmark_parents_uninteresting(c);\n+\t\tmark_parents_uninteresting(revs, c);\n \n \tfor (p = c->parents; p; p = p->next)\n \t\ttest_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);\ndiff --git a/revision.h b/revision.h\nindex a24f72dcd1..82afbd0f8a 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -164,6 +164,7 @@ struct rev_info {\n \t\t\tbisect:1,\n \t\t\tancestry_path:1,\n \t\t\tfirst_parent_only:1,\n+\t\t\tfirst_parent_not:1,\n \t\t\tline_level_traverse:1,\n \t\t\ttree_blobs_in_commit_order:1,\n \n@@ -405,7 +406,7 @@ const char *get_revision_mark(const struct rev_info *revs,\n void put_revision_mark(const struct rev_info *revs,\n \t\t       const struct commit *commit);\n \n-void mark_parents_uninteresting(struct commit *commit);\n+void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit);\n void mark_tree_uninteresting(struct repository *r, struct tree *tree);\n void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees);\n \ndiff --git a/shallow.c b/shallow.c\nindex 9ed18eb884..71e5876f37 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -603,7 +603,7 @@ static int mark_uninteresting(const char *refname, const struct object_id *oid,\n \tif (!commit)\n \t\treturn 0;\n \tcommit->object.flags |= UNINTERESTING;\n-\tmark_parents_uninteresting(commit);\n+\tmark_parents_uninteresting(NULL, commit);\n \treturn 0;\n }\n \ndiff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\nindex 4f7fa8b6c0..7da8542e58 100755\n--- a/t/t6012-rev-list-simplify.sh\n+++ b/t/t6012-rev-list-simplify.sh\n@@ -16,13 +16,12 @@ unnote () {\n }\n \n #\n-# Create a test repo with interesting commit graph:\n+# Create a test repo with an interesting commit graph:\n #\n-# A--B----------G--H--I--K--L\n-#  \\  \\           /     /\n-#   \\  \\         /     /\n-#    C------E---F     J\n-#        \\_/\n+# A-----B-----G--H--I--K--L\n+#  \\     \\      /     /\n+#   \\     \\    /     /\n+#    C--D--E--F     J\n #\n # The commits are laid out from left-to-right starting with\n # the root commit A and terminating at the tip commit L.\n@@ -142,6 +141,13 @@ check_result 'I B A' --author-date-order -- file\n check_result 'H' --first-parent -- another-file\n check_result 'H' --first-parent --topo-order -- another-file\n \n+check_result 'L K I H G B A' --first-parent L\n+check_result 'F E D C' --first-parent-not F ^L\n+check_result '' F ^L\n+check_result 'L K I H G J' L ^F\n+check_result 'L K I H G B J' --first-parent-not L ^F\n+check_result 'L K I H G B' --first-parent-not --first-parent L ^F\n+\n check_result 'E C B A' --full-history E -- lost\n test_expect_success 'full history simplification without parent' '\n \tprintf \"%s\\n\" E C B A >expect &&\n-- \n2.29.0\n\n"},{"id":"431378","messageId":"20210728032033.24233-1-jerry@skydio.com","threadId":"55507","inReplyTo":"20210421004817.22536-1-jerry@skydio.com","subject":"[PATCH V3] git-rev-list: add --first-parent-not flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2021-07-28T03:20:33Z","receivedAt":"2021-07-28T03:20:42Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"Add the --path-first-parent-not flag, which\ncauses the traversal of any \"not\" commits\nto visit only the first parent upon encountering\na merge commit.\n\n   -A-----E-F-G--main\n     \\   / /\n      B-C-D--topic\n\nIn this example, the goal is to return the\nset {B, C, D} which represents a topic\nbranch that has been merged into main branch.\n`git rev-list topic ^main` will end up returning\nno commits since excluding main will end up\ntraversing the commits on topic as well.\n`git rev-list --first-parent-not topic ^main`\nhowever will return {B, C, D} as desired.\n\nAdd docs for the new flag, and clarify the\ndoc for --first-parent to indicate that it\napplies to traversing the set of included\ncommits only. The semantics of existing flags\nhowever have not changed.\n\nSigned-off-by: Jerry Zhang <jerry@skydio.com>\n---\nV2->V3: rebase on master and rerun tests\n\nMost recent discussion was relating to the specific\nflag name. If you have a specific suggestion for\nwhat the name should be I'm happy to use that.\n\n Documentation/rev-list-options.txt | 21 ++++++++++++++-------\n blame.c                            |  2 +-\n revision.c                         | 30 ++++++++++++++++++++----------\n revision.h                         |  3 ++-\n shallow.c                          |  2 +-\n t/t6012-rev-list-simplify.sh       | 18 ++++++++++++------\n 6 files changed, 50 insertions(+), 26 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 24569b06d1..8e8b1e7c9b 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -122,19 +122,26 @@ again.  Equivalent forms are `--min-parents=0` (any commit has 0 or more\n parents) and `--max-parents=-1` (negative numbers denote no upper limit).\n \n --first-parent::\n-\tFollow only the first parent commit upon seeing a merge\n-\tcommit.  This option can give a better overview when\n-\tviewing the evolution of a particular topic branch,\n-\tbecause merges into a topic branch tend to be only about\n-\tadjusting to updated upstream from time to time, and\n-\tthis option allows you to ignore the individual commits\n-\tbrought in to your history by such a merge.\n+\tWhen finding commits to include, follow only the first\n+\tparent commit upon seeing a merge commit.  This option\n+\tcan give a better overview when viewing the evolution of\n+\ta particular topic branch, because merges into a topic\n+\tbranch tend to be only about adjusting to updated upstream\n+\tfrom time to time, and this option allows you to ignore\n+\tthe individual commits brought in to your history by such\n+\ta merge.\n ifdef::git-log[]\n +\n This option also changes default diff format for merge commits\n to `first-parent`, see `--diff-merges=first-parent` for details.\n endif::git-log[]\n \n+--first-parent-not::\n+\tWhen finding commits to exclude, follow only the first\n+\tparent commit upon seeing a merge commit.  This causes\n+\t\"not\" commits to exclude only commits on that branch itself\n+\tand not those brought in by a merge.\n+\n --not::\n \tReverses the meaning of the '{caret}' prefix (or lack thereof)\n \tfor all following revision specifiers, up to the next `--not`.\ndiff --git a/blame.c b/blame.c\nindex 206c295660..083d99fdbc 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -2615,7 +2615,7 @@ void assign_blame(struct blame_scoreboard *sb, int opt)\n \t\telse {\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \t\t\tif (commit->object.parsed)\n-\t\t\t\tmark_parents_uninteresting(commit);\n+\t\t\t\tmark_parents_uninteresting(sb->revs, commit);\n \t\t}\n \t\t/* treat root commit as boundary */\n \t\tif (!commit->parents && !sb->show_root)\ndiff --git a/revision.c b/revision.c\nindex cddd0542a6..60b78b4dce 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -268,7 +268,7 @@ static void commit_stack_clear(struct commit_stack *stack)\n \tstack->nr = stack->alloc = 0;\n }\n \n-static void mark_one_parent_uninteresting(struct commit *commit,\n+static void mark_one_parent_uninteresting(struct rev_info *revs, struct commit *commit,\n \t\t\t\t\t  struct commit_stack *pending)\n {\n \tstruct commit_list *l;\n@@ -285,20 +285,26 @@ static void mark_one_parent_uninteresting(struct commit *commit,\n \t * wasn't uninteresting), in which case we need\n \t * to mark its parents recursively too..\n \t */\n-\tfor (l = commit->parents; l; l = l->next)\n+\tfor (l = commit->parents; l; l = l->next) {\n \t\tcommit_stack_push(pending, l->item);\n+\t\tif (revs && revs->first_parent_not)\n+\t\t\tbreak;\n+\t}\n }\n \n-void mark_parents_uninteresting(struct commit *commit)\n+void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit)\n {\n \tstruct commit_stack pending = COMMIT_STACK_INIT;\n \tstruct commit_list *l;\n \n-\tfor (l = commit->parents; l; l = l->next)\n-\t\tmark_one_parent_uninteresting(l->item, &pending);\n+\tfor (l = commit->parents; l; l = l->next) {\n+\t\tmark_one_parent_uninteresting(revs, l->item, &pending);\n+\t\tif (revs && revs->first_parent_not)\n+\t\t\tbreak;\n+\t}\n \n \twhile (pending.nr > 0)\n-\t\tmark_one_parent_uninteresting(commit_stack_pop(&pending),\n+\t\tmark_one_parent_uninteresting(revs, commit_stack_pop(&pending),\n \t\t\t\t\t      &pending);\n \n \tcommit_stack_clear(&pending);\n@@ -438,7 +444,7 @@ static struct commit *handle_commit(struct rev_info *revs,\n \t\tif (repo_parse_commit(revs->repo, commit) < 0)\n \t\t\tdie(\"unable to parse commit %s\", name);\n \t\tif (flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tmark_parents_uninteresting(revs, commit);\n \n \t\t\tif (!revs->topo_order || !generation_numbers_enabled(the_repository))\n \t\t\t\trevs->limited = 1;\n@@ -1121,7 +1127,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\tif (repo_parse_commit_gently(revs->repo, p, 1) < 0)\n \t\t\t\tcontinue;\n \t\t\tif (p->parents)\n-\t\t\t\tmark_parents_uninteresting(p);\n+\t\t\t\tmark_parents_uninteresting(revs, p);\n \t\t\tif (p->object.flags & SEEN)\n \t\t\t\tcontinue;\n \t\t\tp->object.flags |= (SEEN | NOT_USER_GIVEN);\n@@ -1129,6 +1135,8 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\t\tcommit_list_insert_by_date(p, list);\n \t\t\tif (queue)\n \t\t\t\tprio_queue_put(queue, p);\n+\t\t\tif (revs->first_parent_not)\n+\t\t\t\tbreak;\n \t\t}\n \t\treturn 0;\n \t}\n@@ -1419,7 +1427,7 @@ static int limit_list(struct rev_info *revs)\n \t\tif (process_parents(revs, commit, &original_list, NULL) < 0)\n \t\t\treturn -1;\n \t\tif (obj->flags & UNINTERESTING) {\n-\t\t\tmark_parents_uninteresting(commit);\n+\t\t\tmark_parents_uninteresting(revs, commit);\n \t\t\tslop = still_interesting(original_list, date, slop, &interesting_cache);\n \t\t\tif (slop)\n \t\t\t\tcontinue;\n@@ -2220,6 +2228,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t\treturn argcount;\n \t} else if (!strcmp(arg, \"--first-parent\")) {\n \t\trevs->first_parent_only = 1;\n+\t} else if (!strcmp(arg, \"--first-parent-not\")) {\n+\t\trevs->first_parent_not = 1;\n \t} else if (!strcmp(arg, \"--ancestry-path\")) {\n \t\trevs->ancestry_path = 1;\n \t\trevs->simplify_history = 0;\n@@ -3347,7 +3357,7 @@ static void explore_walk_step(struct rev_info *revs)\n \t\treturn;\n \n \tif (c->object.flags & UNINTERESTING)\n-\t\tmark_parents_uninteresting(c);\n+\t\tmark_parents_uninteresting(revs, c);\n \n \tfor (p = c->parents; p; p = p->next)\n \t\ttest_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);\ndiff --git a/revision.h b/revision.h\nindex fbb068da9f..cec6898c2c 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -161,6 +161,7 @@ struct rev_info {\n \t\t\tbisect:1,\n \t\t\tancestry_path:1,\n \t\t\tfirst_parent_only:1,\n+\t\t\tfirst_parent_not:1,\n \t\t\tline_level_traverse:1,\n \t\t\ttree_blobs_in_commit_order:1,\n \n@@ -404,7 +405,7 @@ const char *get_revision_mark(const struct rev_info *revs,\n void put_revision_mark(const struct rev_info *revs,\n \t\t       const struct commit *commit);\n \n-void mark_parents_uninteresting(struct commit *commit);\n+void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit);\n void mark_tree_uninteresting(struct repository *r, struct tree *tree);\n void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees);\n \ndiff --git a/shallow.c b/shallow.c\nindex 9ed18eb884..71e5876f37 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -603,7 +603,7 @@ static int mark_uninteresting(const char *refname, const struct object_id *oid,\n \tif (!commit)\n \t\treturn 0;\n \tcommit->object.flags |= UNINTERESTING;\n-\tmark_parents_uninteresting(commit);\n+\tmark_parents_uninteresting(NULL, commit);\n \treturn 0;\n }\n \ndiff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\nindex 4f7fa8b6c0..7da8542e58 100755\n--- a/t/t6012-rev-list-simplify.sh\n+++ b/t/t6012-rev-list-simplify.sh\n@@ -16,13 +16,12 @@ unnote () {\n }\n \n #\n-# Create a test repo with interesting commit graph:\n+# Create a test repo with an interesting commit graph:\n #\n-# A--B----------G--H--I--K--L\n-#  \\  \\           /     /\n-#   \\  \\         /     /\n-#    C------E---F     J\n-#        \\_/\n+# A-----B-----G--H--I--K--L\n+#  \\     \\      /     /\n+#   \\     \\    /     /\n+#    C--D--E--F     J\n #\n # The commits are laid out from left-to-right starting with\n # the root commit A and terminating at the tip commit L.\n@@ -142,6 +141,13 @@ check_result 'I B A' --author-date-order -- file\n check_result 'H' --first-parent -- another-file\n check_result 'H' --first-parent --topo-order -- another-file\n \n+check_result 'L K I H G B A' --first-parent L\n+check_result 'F E D C' --first-parent-not F ^L\n+check_result '' F ^L\n+check_result 'L K I H G J' L ^F\n+check_result 'L K I H G B J' --first-parent-not L ^F\n+check_result 'L K I H G B' --first-parent-not --first-parent L ^F\n+\n check_result 'E C B A' --full-history E -- lost\n test_expect_success 'full history simplification without parent' '\n \tprintf \"%s\\n\" E C B A >expect &&\n-- \n2.32.0.1314.g6ed4fcc4cc\n\n"},{"id":"443856","messageId":"CAMKO5Cui30=sY0CUmAAUg+eyW0_BsByVK2tK9rPzaqhnW=pcwg@mail.gmail.com","threadId":"55507","inReplyTo":"20210728032033.24233-1-jerry@skydio.com","subject":"Re: [PATCH V3] git-rev-list: add --first-parent-not flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2021-12-11T02:13:05Z","receivedAt":"2021-12-11T02:13:19Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"On Tue, Jul 27, 2021 at 8:20 PM Jerry Zhang <jerry@skydio.com> wrote:\n>\n> Add the --path-first-parent-not flag, which\n> causes the traversal of any \"not\" commits\n> to visit only the first parent upon encountering\n> a merge commit.\n>\n>    -A-----E-F-G--main\n>      \\   / /\n>       B-C-D--topic\n>\n> In this example, the goal is to return the\n> set {B, C, D} which represents a topic\n> branch that has been merged into main branch.\n> `git rev-list topic ^main` will end up returning\n> no commits since excluding main will end up\n> traversing the commits on topic as well.\n> `git rev-list --first-parent-not topic ^main`\n> however will return {B, C, D} as desired.\n>\n> Add docs for the new flag, and clarify the\n> doc for --first-parent to indicate that it\n> applies to traversing the set of included\n> commits only. The semantics of existing flags\n> however have not changed.\n>\n> Signed-off-by: Jerry Zhang <jerry@skydio.com>\n> ---\n> V2->V3: rebase on master and rerun tests\n>\n> Most recent discussion was relating to the specific\n> flag name. If you have a specific suggestion for\n> what the name should be I'm happy to use that.\n>\n>  Documentation/rev-list-options.txt | 21 ++++++++++++++-------\n>  blame.c                            |  2 +-\n>  revision.c                         | 30 ++++++++++++++++++++----------\n>  revision.h                         |  3 ++-\n>  shallow.c                          |  2 +-\n>  t/t6012-rev-list-simplify.sh       | 18 ++++++++++++------\n>  6 files changed, 50 insertions(+), 26 deletions(-)\n>\n> diff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\n> index 24569b06d1..8e8b1e7c9b 100644\n> --- a/Documentation/rev-list-options.txt\n> +++ b/Documentation/rev-list-options.txt\n> @@ -122,19 +122,26 @@ again.  Equivalent forms are `--min-parents=0` (any commit has 0 or more\n>  parents) and `--max-parents=-1` (negative numbers denote no upper limit).\n>\n>  --first-parent::\n> -       Follow only the first parent commit upon seeing a merge\n> -       commit.  This option can give a better overview when\n> -       viewing the evolution of a particular topic branch,\n> -       because merges into a topic branch tend to be only about\n> -       adjusting to updated upstream from time to time, and\n> -       this option allows you to ignore the individual commits\n> -       brought in to your history by such a merge.\n> +       When finding commits to include, follow only the first\n> +       parent commit upon seeing a merge commit.  This option\n> +       can give a better overview when viewing the evolution of\n> +       a particular topic branch, because merges into a topic\n> +       branch tend to be only about adjusting to updated upstream\n> +       from time to time, and this option allows you to ignore\n> +       the individual commits brought in to your history by such\n> +       a merge.\n>  ifdef::git-log[]\n>  +\n>  This option also changes default diff format for merge commits\n>  to `first-parent`, see `--diff-merges=first-parent` for details.\n>  endif::git-log[]\n>\n> +--first-parent-not::\n> +       When finding commits to exclude, follow only the first\n> +       parent commit upon seeing a merge commit.  This causes\n> +       \"not\" commits to exclude only commits on that branch itself\n> +       and not those brought in by a merge.\n> +\n>  --not::\n>         Reverses the meaning of the '{caret}' prefix (or lack thereof)\n>         for all following revision specifiers, up to the next `--not`.\n> diff --git a/blame.c b/blame.c\n> index 206c295660..083d99fdbc 100644\n> --- a/blame.c\n> +++ b/blame.c\n> @@ -2615,7 +2615,7 @@ void assign_blame(struct blame_scoreboard *sb, int opt)\n>                 else {\n>                         commit->object.flags |= UNINTERESTING;\n>                         if (commit->object.parsed)\n> -                               mark_parents_uninteresting(commit);\n> +                               mark_parents_uninteresting(sb->revs, commit);\n>                 }\n>                 /* treat root commit as boundary */\n>                 if (!commit->parents && !sb->show_root)\n> diff --git a/revision.c b/revision.c\n> index cddd0542a6..60b78b4dce 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -268,7 +268,7 @@ static void commit_stack_clear(struct commit_stack *stack)\n>         stack->nr = stack->alloc = 0;\n>  }\n>\n> -static void mark_one_parent_uninteresting(struct commit *commit,\n> +static void mark_one_parent_uninteresting(struct rev_info *revs, struct commit *commit,\n>                                           struct commit_stack *pending)\n>  {\n>         struct commit_list *l;\n> @@ -285,20 +285,26 @@ static void mark_one_parent_uninteresting(struct commit *commit,\n>          * wasn't uninteresting), in which case we need\n>          * to mark its parents recursively too..\n>          */\n> -       for (l = commit->parents; l; l = l->next)\n> +       for (l = commit->parents; l; l = l->next) {\n>                 commit_stack_push(pending, l->item);\n> +               if (revs && revs->first_parent_not)\n> +                       break;\n> +       }\n>  }\n>\n> -void mark_parents_uninteresting(struct commit *commit)\n> +void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit)\n>  {\n>         struct commit_stack pending = COMMIT_STACK_INIT;\n>         struct commit_list *l;\n>\n> -       for (l = commit->parents; l; l = l->next)\n> -               mark_one_parent_uninteresting(l->item, &pending);\n> +       for (l = commit->parents; l; l = l->next) {\n> +               mark_one_parent_uninteresting(revs, l->item, &pending);\n> +               if (revs && revs->first_parent_not)\n> +                       break;\n> +       }\n>\n>         while (pending.nr > 0)\n> -               mark_one_parent_uninteresting(commit_stack_pop(&pending),\n> +               mark_one_parent_uninteresting(revs, commit_stack_pop(&pending),\n>                                               &pending);\n>\n>         commit_stack_clear(&pending);\n> @@ -438,7 +444,7 @@ static struct commit *handle_commit(struct rev_info *revs,\n>                 if (repo_parse_commit(revs->repo, commit) < 0)\n>                         die(\"unable to parse commit %s\", name);\n>                 if (flags & UNINTERESTING) {\n> -                       mark_parents_uninteresting(commit);\n> +                       mark_parents_uninteresting(revs, commit);\n>\n>                         if (!revs->topo_order || !generation_numbers_enabled(the_repository))\n>                                 revs->limited = 1;\n> @@ -1121,7 +1127,7 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n>                         if (repo_parse_commit_gently(revs->repo, p, 1) < 0)\n>                                 continue;\n>                         if (p->parents)\n> -                               mark_parents_uninteresting(p);\n> +                               mark_parents_uninteresting(revs, p);\n>                         if (p->object.flags & SEEN)\n>                                 continue;\n>                         p->object.flags |= (SEEN | NOT_USER_GIVEN);\n> @@ -1129,6 +1135,8 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n>                                 commit_list_insert_by_date(p, list);\n>                         if (queue)\n>                                 prio_queue_put(queue, p);\n> +                       if (revs->first_parent_not)\n> +                               break;\n>                 }\n>                 return 0;\n>         }\n> @@ -1419,7 +1427,7 @@ static int limit_list(struct rev_info *revs)\n>                 if (process_parents(revs, commit, &original_list, NULL) < 0)\n>                         return -1;\n>                 if (obj->flags & UNINTERESTING) {\n> -                       mark_parents_uninteresting(commit);\n> +                       mark_parents_uninteresting(revs, commit);\n>                         slop = still_interesting(original_list, date, slop, &interesting_cache);\n>                         if (slop)\n>                                 continue;\n> @@ -2220,6 +2228,8 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n>                 return argcount;\n>         } else if (!strcmp(arg, \"--first-parent\")) {\n>                 revs->first_parent_only = 1;\n> +       } else if (!strcmp(arg, \"--first-parent-not\")) {\n> +               revs->first_parent_not = 1;\n>         } else if (!strcmp(arg, \"--ancestry-path\")) {\n>                 revs->ancestry_path = 1;\n>                 revs->simplify_history = 0;\n> @@ -3347,7 +3357,7 @@ static void explore_walk_step(struct rev_info *revs)\n>                 return;\n>\n>         if (c->object.flags & UNINTERESTING)\n> -               mark_parents_uninteresting(c);\n> +               mark_parents_uninteresting(revs, c);\n>\n>         for (p = c->parents; p; p = p->next)\n>                 test_flag_and_insert(&info->explore_queue, p->item, TOPO_WALK_EXPLORED);\n> diff --git a/revision.h b/revision.h\n> index fbb068da9f..cec6898c2c 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -161,6 +161,7 @@ struct rev_info {\n>                         bisect:1,\n>                         ancestry_path:1,\n>                         first_parent_only:1,\n> +                       first_parent_not:1,\n>                         line_level_traverse:1,\n>                         tree_blobs_in_commit_order:1,\n>\n> @@ -404,7 +405,7 @@ const char *get_revision_mark(const struct rev_info *revs,\n>  void put_revision_mark(const struct rev_info *revs,\n>                        const struct commit *commit);\n>\n> -void mark_parents_uninteresting(struct commit *commit);\n> +void mark_parents_uninteresting(struct rev_info *revs, struct commit *commit);\n>  void mark_tree_uninteresting(struct repository *r, struct tree *tree);\n>  void mark_trees_uninteresting_sparse(struct repository *r, struct oidset *trees);\n>\n> diff --git a/shallow.c b/shallow.c\n> index 9ed18eb884..71e5876f37 100644\n> --- a/shallow.c\n> +++ b/shallow.c\n> @@ -603,7 +603,7 @@ static int mark_uninteresting(const char *refname, const struct object_id *oid,\n>         if (!commit)\n>                 return 0;\n>         commit->object.flags |= UNINTERESTING;\n> -       mark_parents_uninteresting(commit);\n> +       mark_parents_uninteresting(NULL, commit);\n>         return 0;\n>  }\n>\n> diff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\n> index 4f7fa8b6c0..7da8542e58 100755\n> --- a/t/t6012-rev-list-simplify.sh\n> +++ b/t/t6012-rev-list-simplify.sh\n> @@ -16,13 +16,12 @@ unnote () {\n>  }\n>\n>  #\n> -# Create a test repo with interesting commit graph:\n> +# Create a test repo with an interesting commit graph:\n>  #\n> -# A--B----------G--H--I--K--L\n> -#  \\  \\           /     /\n> -#   \\  \\         /     /\n> -#    C------E---F     J\n> -#        \\_/\n> +# A-----B-----G--H--I--K--L\n> +#  \\     \\      /     /\n> +#   \\     \\    /     /\n> +#    C--D--E--F     J\n>  #\n>  # The commits are laid out from left-to-right starting with\n>  # the root commit A and terminating at the tip commit L.\n> @@ -142,6 +141,13 @@ check_result 'I B A' --author-date-order -- file\n>  check_result 'H' --first-parent -- another-file\n>  check_result 'H' --first-parent --topo-order -- another-file\n>\n> +check_result 'L K I H G B A' --first-parent L\n> +check_result 'F E D C' --first-parent-not F ^L\n> +check_result '' F ^L\n> +check_result 'L K I H G J' L ^F\n> +check_result 'L K I H G B J' --first-parent-not L ^F\n> +check_result 'L K I H G B' --first-parent-not --first-parent L ^F\n> +\n>  check_result 'E C B A' --full-history E -- lost\n>  test_expect_success 'full history simplification without parent' '\n>         printf \"%s\\n\" E C B A >expect &&\n> --\n> 2.32.0.1314.g6ed4fcc4cc\n>\nAny updates on this patch? This is used in our automatic base\nbranch detection logic, which aims to find the original branch the\nuser branched off of, regardless of however many branches they\nmay have merged in since. There is no other way to achieve this\nfunctionality with git so far.\n"}]}