{"thread":{"id":"57196","subject":"[PATCH V3] git-rev-list: add --first-parent-not flag","startedAt":"2022-01-05T23:28:14Z","lastAt":"2022-01-11T21:39:48Z","messageCount":5,"participants":["Jerry Zhang","Junio C Hamano"],"isPatch":true,"patchVersion":3,"patchTotal":null},"messages":[{"id":"445592","messageId":"20220105232755.23523-1-jerry@skydio.com","threadId":"57196","inReplyTo":null,"subject":"[PATCH V3] git-rev-list: add --first-parent-not flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2022-01-05T23:27:55Z","receivedAt":"2022-01-05T23:28:14Z","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---\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 43a86fa562..59684d6a4f 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -120,23 +120,30 @@ providing this option will cause it to die.\n `--no-min-parents` and `--no-max-parents` reset these limits (to no limit)\n 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`.\n \n --all::\ndiff --git a/blame.c b/blame.c\nindex 206c295660..083d99fdbc 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -2613,11 +2613,11 @@ void assign_blame(struct blame_scoreboard *sb, int opt)\n \t\t     !(revs->max_age != -1 && commit->date < revs->max_age)))\n \t\t\tpass_blame(sb, suspect, 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)\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \ndiff --git a/revision.c b/revision.c\nindex 250f61e8cf..743e8d9e3c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -271,11 +271,11 @@ static void commit_stack_clear(struct commit_stack *stack)\n {\n \tFREE_AND_NULL(stack->items);\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 \n \tif (commit->object.flags & UNINTERESTING)\n@@ -288,24 +288,30 @@ static void mark_one_parent_uninteresting(struct commit *commit,\n \t * here. However, it may turn out that we've\n \t * reached this commit some other way (where it\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 }\n \n@@ -439,11 +445,11 @@ static struct commit *handle_commit(struct rev_info *revs,\n \t\tstruct commit *commit = (struct commit *)object;\n \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 \t\t}\n \t\tif (revs->sources) {\n@@ -1122,18 +1128,20 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\tif (p)\n \t\t\t\tp->object.flags |= UNINTERESTING;\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 \t\t\tif (list)\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 \n \t/*\n@@ -1420,11 +1428,11 @@ static int limit_list(struct rev_info *revs)\n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\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 \t\t\tbreak;\n \t\t}\n@@ -2221,10 +2229,12 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if ((argcount = parse_long_opt(\"until\", argv, &optarg))) {\n \t\trevs->min_age = approxidate(optarg);\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 \t\trevs->limited = 1;\n \t} else if (!strcmp(arg, \"-g\") || !strcmp(arg, \"--walk-reflogs\")) {\n@@ -3343,11 +3353,11 @@ static void explore_walk_step(struct rev_info *revs)\n \n \tif (process_parents(revs, c, NULL, NULL) < 0)\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);\n }\n \ndiff --git a/revision.h b/revision.h\nindex 3f66147bfd..667dd27740 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -156,10 +156,11 @@ struct rev_info {\n \t\t\tcherry_pick:1,\n \t\t\tcherry_mark:1,\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 \t\t\t/*\n \t\t\t * Blobs are shown without regard for their existence.\n@@ -396,11 +397,11 @@ struct commit *get_revision(struct rev_info *revs);\n const char *get_revision_mark(const struct rev_info *revs,\n \t\t\t      const struct commit *commit);\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 \n void show_object_with_name(FILE *, struct object *, const char *);\n \ndiff --git a/shallow.c b/shallow.c\nindex 9ed18eb884..71e5876f37 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -601,11 +601,11 @@ static int mark_uninteresting(const char *refname, const struct object_id *oid,\n \tstruct commit *commit = lookup_commit_reference_gently(the_repository,\n \t\t\t\t\t\t\t       oid, 1);\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 \n static void post_assign_shallow(struct shallow_info *info,\n \t\t\t\tstruct ref_bitmap *ref_bitmap,\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@@ -14,17 +14,16 @@ note () {\n unnote () {\n \tgit name-rev --tags --stdin | sed -e \"s|$OID_REGEX (tags/\\([^)]*\\)) |\\1 |g\"\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 #\n # There are a few places where we adjust the commit date or\n@@ -140,10 +139,17 @@ check_result 'I B A' --topo-order -- file\n check_result 'I B A' --date-order -- file\n 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 \tgit log --pretty=\"$FMT\" --full-history E -- lost |\n \tunnote >actual &&\n-- \n2.32.0.1314.g6ed4fcc4cc\n\n"},{"id":"445661","messageId":"xmqqpmp4bjni.fsf@gitster.g","threadId":"57196","inReplyTo":"20220105232755.23523-1-jerry@skydio.com","subject":"Re: [PATCH V3] git-rev-list: add --first-parent-not flag","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-06T22:10:09Z","receivedAt":"2022-01-06T22:10:20Z","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 --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\nIt may be true for _this_ particular topology, but it is unclear\nwhat \"the goal\" is, and if the \"ignore side branches that got\nmerged\" is the right way to achieve that goal.  Perhaps shuffling\nthe order of explanation to state what you want to achieve first may\nhelp clarify.\n\nIs the goal \"I have a commit that I know is at the tip of a topic\nbranch, but the topic may or may not have been merged to the primary\nintegration branch.  I want to know what commits were on the topic\nbranch\"?\n\nEven if we disregard a fast-forward merges from side branches, which\nwill screw up any algorithm that takes advantage of the assumption\nthat the first-parent chain is special, I am not quite convinced how\n\"propagate UNINTERESTING only along the first parent chain\" is\nnecessary and sufficient for the purpose of solving that problem.\nCare to elaborate on the correctness of the logic a bit more?\n\nPlease do not talk back with \"give me a topology that the algorithm\nwould not work on, then\".  The onus is on to whoever proposes a\nchange to show how it produces correct result.\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\nThis is a tangent.  Even though 45 is certainly less than 80, can we\nuse a bit wider lines?  What you used in the documentation patch\n(around 60-65?) may be more readable.\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\nThe only change is to clarify that the first-parent traversal is\ndone only on the positive side; what is implied but probably is lost\nto most readers is that propagation of UNINTERESTING bit is not\naffected by this option.  I made sure that \"This option can ...\"\nand everything after it are identical to save other reviewers' time,\nas the above hunk have unnecessary rewrapping of the text.\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\nAre there places we use a term '\"not\" commit'?  What you are trying\nto refer to is a subset of \"UNINTERESTING commits\"; it is the\ninitial set of UNINTERESTING commits the traversal starts with.  I\nknow we use the word \"negative\" (or sometimes \"bottom\") in the\ncontext of discussing revision ranges on this list, but I do not\nthink we used either in end-user facing documentation pages.\n\nLet's read the beginning of the description of \"git log --help\" to\nsee if we can find a good phrase our readers should already be\nfamiliar with.  This is how we describe the command:\n\n    List commits that are reachable by following the `parent` links\n    from the given commit(s), but exclude commits that are reachable\n    from the one(s) given with a '{caret}' in front of them.  The\n    output is given in reverse chronological order by default.\n\nAssuming that propagating the UNINTERESTING bit only along the first\nparent chain is a way to achieve some meaningful result (which, as I\nsaid, I am not convinced about), I probably would call this option\n\"--exclude-first-parent-only\" and explain it perhaps like so\n\n\tFollow only the first-parent chain from commits given with a\n\t{caret} in front of them, to find commits to exclude.\n\n        This prevents commits merged from the side branches from\n\tbecoming uninteresting and instead be shown if they are\n\treachable from the positive end of the range.\n\nI am debating myself if the second paragraph is necessary, though.\nI suspect that the first two-line paragraph may be sufficient.\n"},{"id":"445689","messageId":"CAMKO5CsGJdDYvBsb8_-AkpAeeoVGY0Qhv4sX8TimJ4eqR=sLvA@mail.gmail.com","threadId":"57196","inReplyTo":"xmqqpmp4bjni.fsf@gitster.g","subject":"Re: [PATCH V3] git-rev-list: add --first-parent-not flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2022-01-07T03:51:48Z","receivedAt":"2022-01-07T03:52:02Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"On Thu, Jan 6, 2022 at 2:10 PM Junio C Hamano <gitster@pobox.com> wrote:\n>\n> Jerry Zhang <jerry@skydio.com> writes:\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> It may be true for _this_ particular topology, but it is unclear\n> what \"the goal\" is, and if the \"ignore side branches that got\n> merged\" is the right way to achieve that goal.  Perhaps shuffling\n> the order of explanation to state what you want to achieve first may\n> help clarify.\n>\n> Is the goal \"I have a commit that I know is at the tip of a topic\n> branch, but the topic may or may not have been merged to the primary\n> integration branch.  I want to know what commits were on the topic\n> branch\"?\n\nAlthough this is a useful application of the flag, it's not something we use\nit for right now (although we might in the future).\n\nAs an overview, we're building a code review tool where the\n(simplified) workflow is:\n\n1. start off on some local version of an integration branch, tracking the\nremote version of that branch\n2. make some local changes. valid local changes include\n    - making a new commit(s)\n    - merging in other branches (could be remote integration branches\nor feature branches)\n    - merging in the head of the tracking branch to get the latest changes\n3. identify which local changes were made and upload them (in our case\nto github).\n\nSo our goals are:\n\n1. Automatically identify the appropriate integration branch that the user\nis intending to target, without needing to add arguments to the command.\n2. Automatically identify relevant commits that the user has made on top of\nthe integration branch, without needing to add arguments.\n\nWe accomplish these by defining the \"fork point\" of two branches, although\nnote that this is different from what is found by \"merge-base --fork-point\".\nFork point of branch \"dev\" and \"main\" is the first parent of the last element of\n\"git rev-list --first-parent --exclude-first-parent-only main ^dev\"\nor equivalently, the first parent of the last element of\n\"git rev-list --first-parent --exclude-first-parent-only ^main dev\".\n\nThe proof that those two are equivalent: when both flags are specified, rev-list\ncan only ever traverse first parents. This makes it as though all non\nfirst parent\nedges don't exist, so the git graph becomes basically a directed tree. Since we\nare only traversing from 2 leaves, only 2 paths are traversed, and since they\nare assumed to share history, the traversal forms a \"Y\".\n       B ---- main\n      /\n--- A\n      \\\n      C ---- dev\nSo \"git rev-list --first-parent --exclude-first-parent-only main ^dev\n--reverse | head -n 1\"\nfinds B and \"git rev-list --first-parent --exclude-first-parent-only\n^main dev --reverse | head -n 1\"\nfinds C, but both their parents are A. Hopefully this was sufficiently rigorous.\n\nTo solve goal #1, we loop the set of possible integration branches and\nfind the number of\nlocal changes that our algorithm would detect. The branch that our\nbranch has the smallest\nnumber of local changes (as identified in goal #2) with respect to is\nconsidered to be the target.\n\nTo solve goal #2 we find the fork-point of our branch and the\nintegration branch, then\nthe following set is our local commits: \"git rev-list --first-parent\ndev ^forkpoint\".\n\nMerges will all work well with our algorithm and the new flag because\nthey no longer \"look like\" merges in terms of finding the fork point.\nAnother way of saying this is that because the traversal that calculates\nthe fork point can't follow secondary parents, merges are indistinguishable\nfrom normal commits. Our algorithm that finds the fork-point and the set\nof local changes already assumes an arbitrary number of commits between\nthe fork point and heads of the two different branches. Thus its impossible\nto affect the correctness of the fork-point or the local commit set by adding\na normal commit. Since merges are indistinguishable from normal commits\nit must also be impossible to affect this correctness by adding a merge commit.\nThis should prove that the flag is sufficient for our goals.\n\nNow here is an example to show that the flag is necessary. It's a bit\ncomplicated\nbut it's all valid individual and organizational uses of git.\n- main branch is an integration branch that people work on\n- next is a forward looking integration branch with experimental\nfeatures. it needs\noccasional merges from main, but can't be merged back into main until\nexperimental\nfeatures have stabilized.\n- dev is a local development branch.\n\n -A--B---C--D---main\n   \\  \\ /    \\\n    \\  E------------F--dev\n     \\        \\    /\n      G--------H--I--J--next\n\n1. commit E is made on dev, PR is opened against main.\n2. overnight E merges into main at C, and main is merged into next at H.\n3. the next day, user fetches and merges in next at F, intending to\nmerge it into main.\n\nWith our algorithm, we find fork-point of dev and main to be B, so\nlocal commits against\nmain are [E, F]. Fork-point of dev and next is found as A, local\ncommits would be [B, E, F].\nSince main has a smaller set of local commits, it is chosen as the\ntarget branch.\n\nWithout the new flag, we don't have a good definition of fork-point since\n\"git rev-list --first-parent main ^dev --reverse | head -n 1\"\ndoes not equal \"git rev-list --first-parent ^main dev --reverse | head -n 1\".\nNevertheless we can try a few things to see if we can reach the same result.\nBy excluding the dev branch, we find the fork point of dev and main to be\nB, with local set [E, F]. However, we find the fork point of dev and\nnext to be I,\nwith local set [E, F] as well, so it becomes ambiguous which branch is the\npreferred target.\nSwitching to excluding the target branch, we find the fork point of dev and main\nto be E and working set to be [F]. Fork point of dev and next to be E\nand working\nset to be [F]. So it is still ambiguous and there's not any way I'm aware of to\nget our desired result.\n\n>\n> Even if we disregard a fast-forward merges from side branches, which\n> will screw up any algorithm that takes advantage of the assumption\n> that the first-parent chain is special, I am not quite convinced how\nFF merges aren't an issue here because our tool only uploads what the\nuser wants. If the user wants a real merge instead of an FF, its on them\nto make that commit. Another way to look at it is that our tool must be\nrobust to all sorts of merges in the git history. Fast forwards don't look\nlike merges, so it isn't an issue if they've happened.\n\n> \"propagate UNINTERESTING only along the first parent chain\" is\n> necessary and sufficient for the purpose of solving that problem.\n> Care to elaborate on the correctness of the logic a bit more?\n>\n> Please do not talk back with \"give me a topology that the algorithm\n> would not work on, then\".  The onus is on to whoever proposes a\n> change to show how it produces correct result.\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> This is a tangent.  Even though 45 is certainly less than 80, can we\n> use a bit wider lines?  What you used in the documentation patch\n> (around 60-65?) may be more readable.\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>\n> The only change is to clarify that the first-parent traversal is\n> done only on the positive side; what is implied but probably is lost\n> to most readers is that propagation of UNINTERESTING bit is not\n> affected by this option.  I made sure that \"This option can ...\"\n> and everything after it are identical to save other reviewers' time,\n> as the above hunk have unnecessary rewrapping of the text.\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> Are there places we use a term '\"not\" commit'?  What you are trying\n> to refer to is a subset of \"UNINTERESTING commits\"; it is the\n> initial set of UNINTERESTING commits the traversal starts with.  I\n> know we use the word \"negative\" (or sometimes \"bottom\") in the\n> context of discussing revision ranges on this list, but I do not\n> think we used either in end-user facing documentation pages.\n>\n> Let's read the beginning of the description of \"git log --help\" to\n> see if we can find a good phrase our readers should already be\n> familiar with.  This is how we describe the command:\n>\n>     List commits that are reachable by following the `parent` links\n>     from the given commit(s), but exclude commits that are reachable\n>     from the one(s) given with a '{caret}' in front of them.  The\n>     output is given in reverse chronological order by default.\n>\n> Assuming that propagating the UNINTERESTING bit only along the first\n> parent chain is a way to achieve some meaningful result (which, as I\n> said, I am not convinced about), I probably would call this option\n> \"--exclude-first-parent-only\" and explain it perhaps like so\n>\n>         Follow only the first-parent chain from commits given with a\n>         {caret} in front of them, to find commits to exclude.\n>\n>         This prevents commits merged from the side branches from\n>         becoming uninteresting and instead be shown if they are\n>         reachable from the positive end of the range.\n>\n> I am debating myself if the second paragraph is necessary, though.\n> I suspect that the first two-line paragraph may be sufficient.\nSure, I'll update the patch and commit text with these changes.\n"},{"id":"445747","messageId":"xmqqiluv8dk5.fsf@gitster.g","threadId":"57196","inReplyTo":"CAMKO5CsGJdDYvBsb8_-AkpAeeoVGY0Qhv4sX8TimJ4eqR=sLvA@mail.gmail.com","subject":"Re: [PATCH V3] git-rev-list: add --first-parent-not flag","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2022-01-07T21:02:18Z","receivedAt":"2022-01-07T21:02:24Z","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>> Assuming that propagating the UNINTERESTING bit only along the first\n>> parent chain is a way to achieve some meaningful result (which, as I\n>> said, I am not convinced about), I probably would call this option\n>> \"--exclude-first-parent-only\" and explain it perhaps like so\n>>\n>>         Follow only the first-parent chain from commits given with a\n>>         {caret} in front of them, to find commits to exclude.\n>>\n>>         This prevents commits merged from the side branches from\n>>         becoming uninteresting and instead be shown if they are\n>>         reachable from the positive end of the range.\n>>\n>> I am debating myself if the second paragraph is necessary, though.\n>> I suspect that the first two-line paragraph may be sufficient.\n> Sure, I'll update the patch and commit text with these changes.\n\nOK.  Also the log message for the commit needs to be updated so that\nthose who read \"git log\" and find the commit for this change will\nnot have to ask the same question as I asked.\n\nThanks.\n"},{"id":"445973","messageId":"20220111213941.30129-1-jerry@skydio.com","threadId":"57196","inReplyTo":"20220105232755.23523-1-jerry@skydio.com","subject":"[PATCH V4] git-rev-list: add --exclude-first-parent-only flag","fromName":"Jerry Zhang","fromEmail":"jerry@skydio.com","sentAt":"2022-01-11T21:39:41Z","receivedAt":"2022-01-11T21:39:48Z","isPatch":true,"sender":{"key":"jerry@skydio.com","avatar":"https://avatars.githubusercontent.com/u/81337184?v=4"},"body":"It is useful to know when a branch first diverged in history\nfrom some integration branch in order to be able to enumerate\nthe user's local changes. However, these local changes can\ninclude arbitrary merges, so it is necessary to ignore this\nmerge structure when finding the divergence point.\n\nIn order to do this, teach the \"rev-list\" family to accept\n\"--exclude-first-parent-only\", which restricts the traversal\nof excluded commits to only follow first parent links.\n\n   -A-----E-F-G--main\n     \\   / /\n      B-C-D--topic\n\nIn this example, the goal is to return the set {B, C, D} which\nrepresents a topic branch that has been merged into main branch.\n`git rev-list topic ^main` will end up returning no commits\nsince excluding main will end up traversing the commits on topic\nas well. `git rev-list --exclude-first-parent-only topic ^main`\nhowever will return {B, C, D} as desired.\n\nAdd docs for the new flag, and clarify the doc for --first-parent\nto indicate that it applies to traversing the set of included\ncommits only.\n\nSigned-off-by: Jerry Zhang <jerry@skydio.com>\n---\nV3->V4:\n- Updated flag name\n- Updated doc and commit text to describe the exact use-case\n\n Documentation/rev-list-options.txt | 22 +++++++++++++++-------\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, 51 insertions(+), 26 deletions(-)\n\ndiff --git a/Documentation/rev-list-options.txt b/Documentation/rev-list-options.txt\nindex 43a86fa562..fd4f4e26c9 100644\n--- a/Documentation/rev-list-options.txt\n+++ b/Documentation/rev-list-options.txt\n@@ -120,23 +120,31 @@ providing this option will cause it to die.\n `--no-min-parents` and `--no-max-parents` reset these limits (to no limit)\n 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-first-parent-only::\n+\tWhen finding commits to exclude (with a '{caret}'), follow only\n+\tthe first parent commit upon seeing a merge commit.\n+\tThis can be used to find the set of changes in a topic branch\n+\tfrom the point where it diverged from the remote branch, given\n+\tthat arbitrary merges can be valid topic branch changes.\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`.\n \n --all::\ndiff --git a/blame.c b/blame.c\nindex 206c295660..083d99fdbc 100644\n--- a/blame.c\n+++ b/blame.c\n@@ -2613,11 +2613,11 @@ void assign_blame(struct blame_scoreboard *sb, int opt)\n \t\t     !(revs->max_age != -1 && commit->date < revs->max_age)))\n \t\t\tpass_blame(sb, suspect, 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)\n \t\t\tcommit->object.flags |= UNINTERESTING;\n \ndiff --git a/revision.c b/revision.c\nindex ad4286fbdd..d8d326d6b0 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -271,11 +271,11 @@ static void commit_stack_clear(struct commit_stack *stack)\n {\n \tFREE_AND_NULL(stack->items);\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 \n \tif (commit->object.flags & UNINTERESTING)\n@@ -288,24 +288,30 @@ static void mark_one_parent_uninteresting(struct commit *commit,\n \t * here. However, it may turn out that we've\n \t * reached this commit some other way (where it\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_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_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 }\n \n@@ -439,11 +445,11 @@ static struct commit *handle_commit(struct rev_info *revs,\n \t\tstruct commit *commit = (struct commit *)object;\n \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 \t\t}\n \t\tif (revs->sources) {\n@@ -1122,18 +1128,20 @@ static int process_parents(struct rev_info *revs, struct commit *commit,\n \t\t\tif (p)\n \t\t\t\tp->object.flags |= UNINTERESTING;\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 \t\t\tif (list)\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_first_parent_only)\n+\t\t\t\tbreak;\n \t\t}\n \t\treturn 0;\n \t}\n \n \t/*\n@@ -1420,11 +1428,11 @@ static int limit_list(struct rev_info *revs)\n \t\tif (revs->max_age != -1 && (commit->date < revs->max_age))\n \t\t\tobj->flags |= UNINTERESTING;\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 \t\t\tbreak;\n \t\t}\n@@ -2221,10 +2229,12 @@ static int handle_revision_opt(struct rev_info *revs, int argc, const char **arg\n \t} else if ((argcount = parse_long_opt(\"until\", argv, &optarg))) {\n \t\trevs->min_age = approxidate(optarg);\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-first-parent-only\")) {\n+\t\trevs->exclude_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 \t\trevs->limited = 1;\n \t} else if (!strcmp(arg, \"-g\") || !strcmp(arg, \"--walk-reflogs\")) {\n@@ -3343,11 +3353,11 @@ static void explore_walk_step(struct rev_info *revs)\n \n \tif (process_parents(revs, c, NULL, NULL) < 0)\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);\n }\n \ndiff --git a/revision.h b/revision.h\nindex 3f66147bfd..374a4ff468 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -156,10 +156,11 @@ struct rev_info {\n \t\t\tcherry_pick:1,\n \t\t\tcherry_mark:1,\n \t\t\tbisect:1,\n \t\t\tancestry_path:1,\n \t\t\tfirst_parent_only:1,\n+\t\t\texclude_first_parent_only:1,\n \t\t\tline_level_traverse:1,\n \t\t\ttree_blobs_in_commit_order:1,\n \n \t\t\t/*\n \t\t\t * Blobs are shown without regard for their existence.\n@@ -396,11 +397,11 @@ struct commit *get_revision(struct rev_info *revs);\n const char *get_revision_mark(const struct rev_info *revs,\n \t\t\t      const struct commit *commit);\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 \n void show_object_with_name(FILE *, struct object *, const char *);\n \ndiff --git a/shallow.c b/shallow.c\nindex 9ed18eb884..71e5876f37 100644\n--- a/shallow.c\n+++ b/shallow.c\n@@ -601,11 +601,11 @@ static int mark_uninteresting(const char *refname, const struct object_id *oid,\n \tstruct commit *commit = lookup_commit_reference_gently(the_repository,\n \t\t\t\t\t\t\t       oid, 1);\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 \n static void post_assign_shallow(struct shallow_info *info,\n \t\t\t\tstruct ref_bitmap *ref_bitmap,\ndiff --git a/t/t6012-rev-list-simplify.sh b/t/t6012-rev-list-simplify.sh\nindex 4f7fa8b6c0..e2851fd75d 100755\n--- a/t/t6012-rev-list-simplify.sh\n+++ b/t/t6012-rev-list-simplify.sh\n@@ -14,17 +14,16 @@ note () {\n unnote () {\n \tgit name-rev --tags --stdin | sed -e \"s|$OID_REGEX (tags/\\([^)]*\\)) |\\1 |g\"\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 #\n # There are a few places where we adjust the commit date or\n@@ -140,10 +139,17 @@ check_result 'I B A' --topo-order -- file\n check_result 'I B A' --date-order -- file\n 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-first-parent-only 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-first-parent-only L ^F\n+check_result 'L K I H G B' --exclude-first-parent-only --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 \tgit log --pretty=\"$FMT\" --full-history E -- lost |\n \tunnote >actual &&\n-- \n2.32.0.1314.g6ed4fcc4cc\n\n"}]}