{"thread":{"id":"61884","subject":"[PATCH 0/3] git for-each-ref: is-base atom and base branches","startedAt":"2024-08-01T22:10:29Z","lastAt":"2024-08-20T01:33:52Z","messageCount":23,"participants":["Derrick Stolee via GitGitGadget","Junio C Hamano","Derrick Stolee"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"499909","messageId":"pull.1768.git.1722550226.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":null,"subject":"[PATCH 0/3] git for-each-ref: is-base atom and base branches","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-01T22:10:23Z","receivedAt":"2024-08-01T22:10:29Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This change introduces a new 'git for-each-ref' atom, 'is-base', in a very\nsimilar way to the 'ahead-behind' atom. As detailed carefully in the first\nchange, this is motivated by the need to detect the concept of a \"base\nbranch\" in a repository with multiple long-lived branches.\n\nThis change is motivated by a third-party tool created to make this\ndetection with the same optimization mechanism, but using a much slower\ntechnique due to the limitations of the Git CLI not presenting this\ninformation. The existing algorithm involves using git rev-list\n--first-parent - in batches for the collection of considered references,\ncomparing those lists, and increasing as needed until finding a\ncollision. This new use of 'git for-each-ref' will allow determining this\nmechanism within a single process and walking a minimal number of commits.\n\nThere are benefits to users both on client-side and server-side. In an\ninternal monorepo, this base branch detection algorithm is used to determine\na long-lived branch based on the HEAD commit, mapping to a group within the\norganizational structure of the repository, which determines a set of\nprojects that the user will likely need to build; this leads to\nautomatically selecting an initial sparse-checkout definition based on the\nbuild dependencies required. An upcoming feature in Azure Repos will use\nthis algorithm to automatically create a pull request against the correct\ntarget branch, reducing user pain from needing to select a different branch\nafter a large commit diff is rendered against the default branch. This atom\nunlocks that ability for Git hosting services that use Git in their backend.\n\nThanks, -Stolee\n\nDerrick Stolee (3):\n commit-reach: add get_branch_base_for_tip\n for-each-ref: add 'is-base' token\n p1500: add is-base performance tests\n\n commit-reach.c | 118 ++++++++++++++++++++++++++++++++++++\n commit-reach.h | 17 ++++++\n ref-filter.c | 78 +++++++++++++++++++++++-\n ref-filter.h | 15 +++++\n t/helper/test-reach.c | 2 +\n t/perf/p1500-graph-walks.sh | 31 ++++++++++\n t/t6600-test-reach.sh | 94 ++++++++++++++++++++++++++++\n 7 files changed, 354 insertions(+), 1 deletion(-)\n\n\nbase-commit: bea9ecd24b0c3bf06cab4a851694fe09e7e51408\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1768%2Fderrickstolee%2Ftarget-ref-v1\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1768/derrickstolee/target-ref-v1\nPull-Request: https://github.com/gitgitgadget/git/pull/1768\n-- \ngitgitgadget\n"},{"id":"499911","messageId":"a1fbdca374fe665d3194187ff3ae7977693f01ad.1722550226.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.git.1722550226.gitgitgadget@gmail.com","subject":"[PATCH 2/3] for-each-ref: add 'is-base' token","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-01T22:10:25Z","receivedAt":"2024-08-01T22:10:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change introduced the get_branch_base_for_tip() method in\ncommit-reach.c. The motivation of that change was about using a heuristic to\ndeteremine the base branch for a source commit from a list of candidate\ncommit tips. This change makes that algorithm visible to users via a new\natom in the 'git for-each-ref' format. This change is very similar to the\nchang in 49abcd21da6 (for-each-ref: add ahead-behind format atom,\n2023-03-20).\n\nIntroduce the 'is-base:' atom, which will indicate that the\nalgorithm should be computed and the result of the algorithm is reported\nusing an indicator of the form '()'. For example, using\n'%(is-base:HEAD)' would result in one line having the token '(HEAD)'.\n\nUse the sorted order of refs included in the ref filter to break ties in the\nalgorithm's heuristic. In the previous change, the motivating examples\ninclude using an L0 trunk, long-lived L1 branches, and temporary release\nbranches. A caller could communicate the ordered preference among these\ncategories using the input refpecs and avoiding a different sort mechanism.\nThis sorting behavior is tested in the test scripts.\n\nIt is important to include this atom as a special case to\ncan_do_iterative_format() to match the expectations created in bd98f9774e1\n(ref-filter.c: filter & format refs in the same callback, 2023-11-14). The\nahead-behind atom was one of the special cases, and this similarly requires\nusing an algorithm across all input refs before starting the format of any\nsingle ref.\n\nIn the test script, the format tokens use colons or lack whitespace to avoid\nGit complaining about trailing whitespace errors.\n\nSigned-off-by: Derrick Stolee \n---\n ref-filter.c | 78 ++++++++++++++++++++++++++++++++++++++++++-\n ref-filter.h | 15 +++++++++\n t/t6600-test-reach.sh | 47 ++++++++++++++++++++++++++\n 3 files changed, 139 insertions(+), 1 deletion(-)\n\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 59ad6f54ddb..59689672da1 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -167,6 +167,7 @@ enum atom_type {\n \tATOM_ELSE,\n \tATOM_REST,\n \tATOM_AHEADBEHIND,\n+\tATOM_ISBASE,\n };\n \n /*\n@@ -889,6 +890,23 @@ static int ahead_behind_atom_parser(struct ref_format *format,\n \treturn 0;\n }\n \n+static int is_base_atom_parser(struct ref_format *format,\n+\t\t\t struct used_atom *atom UNUSED,\n+\t\t\t const char *arg, struct strbuf *err)\n+{\n+\tstruct string_list_item *item;\n+\n+\tif (!arg)\n+\t\treturn strbuf_addf_ret(err, -1, _(\"expected format: %%(is-base:)\"));\n+\n+\titem = string_list_append(&format->is_base_tips, arg);\n+\titem->util = lookup_commit_reference_by_name(arg);\n+\tif (!item->util)\n+\t\tdie(\"failed to find '%s'\", arg);\n+\n+\treturn 0;\n+}\n+\n static int head_atom_parser(struct ref_format *format UNUSED,\n \t\t\t struct used_atom *atom,\n \t\t\t const char *arg, struct strbuf *err)\n@@ -952,6 +970,7 @@ static struct {\n \t[ATOM_ELSE] = { \"else\", SOURCE_NONE },\n \t[ATOM_REST] = { \"rest\", SOURCE_NONE, FIELD_STR, rest_atom_parser },\n \t[ATOM_AHEADBEHIND] = { \"ahead-behind\", SOURCE_OTHER, FIELD_STR, ahead_behind_atom_parser },\n+\t[ATOM_ISBASE] = { \"is-base\", SOURCE_OTHER, FIELD_STR, is_base_atom_parser },\n \t/*\n \t * Please update $__git_ref_fieldlist in git-completion.bash\n \t * when you add new atoms\n@@ -2334,6 +2353,7 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err)\n \tint i;\n \tstruct object_info empty = OBJECT_INFO_INIT;\n \tint ahead_behind_atoms = 0;\n+\tint is_base_atoms = 0;\n \n \tCALLOC_ARRAY(ref->value, used_atom_cnt);\n \n@@ -2475,6 +2495,16 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err)\n \t\t\t\tv->s = xstrdup(\"\");\n \t\t\t}\n \t\t\tcontinue;\n+\t\t} else if (atom_type == ATOM_ISBASE) {\n+\t\t\tif (ref->is_base && ref->is_base[is_base_atoms]) {\n+\t\t\t\tv->s = xstrfmt(\"(%s)\", ref->is_base[is_base_atoms]);\n+\t\t\t\tfree(ref->is_base[is_base_atoms]);\n+\t\t\t} else {\n+\t\t\t\t/* Not a commit. */\n+\t\t\t\tv->s = xstrdup(\"\");\n+\t\t\t}\n+\t\t\tis_base_atoms++;\n+\t\t\tcontinue;\n \t\t} else\n \t\t\tcontinue;\n \n@@ -2876,6 +2906,7 @@ static void free_array_item(struct ref_array_item *item)\n \t\tfree(item->value);\n \t}\n \tfree(item->counts);\n+\tfree(item->is_base);\n \tfree(item);\n }\n \n@@ -3040,6 +3071,49 @@ void filter_ahead_behind(struct repository *r,\n \tfree(commits);\n }\n \n+void filter_is_base(struct repository *r,\n+\t\t struct ref_format *format,\n+\t\t struct ref_array *array)\n+{\n+\tstruct commit **bases;\n+\tsize_t bases_nr = 0;\n+\tstruct ref_array_item **back_index;\n+\n+\tif (!format->is_base_tips.nr || !array->nr)\n+\t\treturn;\n+\n+\tCALLOC_ARRAY(back_index, array->nr);\n+\tCALLOC_ARRAY(bases, array->nr);\n+\n+\tfor (size_t i = 0; i < array->nr; i++) {\n+\t\tconst char *name = array->items[i]->refname;\n+\t\tstruct commit *c = lookup_commit_reference_by_name(name);\n+\n+\t\tCALLOC_ARRAY(array->items[i]->is_base, format->is_base_tips.nr);\n+\n+\t\tif (!c)\n+\t\t\tcontinue;\n+\n+\t\tback_index[bases_nr] = array->items[i];\n+\t\tbases[bases_nr] = c;\n+\t\tbases_nr++;\n+\t}\n+\n+\tfor (size_t i = 0; i < format->is_base_tips.nr; i++) {\n+\t\tstruct commit *tip = format->is_base_tips.items[i].util;\n+\t\tint base_index = get_branch_base_for_tip(r, tip, bases, bases_nr);\n+\n+\t\tif (base_index < 0)\n+\t\t\tcontinue;\n+\n+\t\t/* Store the string for use in output later. */\n+\t\tback_index[base_index]->is_base[i] = xstrdup(format->is_base_tips.items[i].string);\n+\t}\n+\n+\tfree(back_index);\n+\tfree(bases);\n+}\n+\n static int do_filter_refs(struct ref_filter *filter, unsigned int type, each_ref_fn fn, void *cb_data)\n {\n \tint ret = 0;\n@@ -3126,7 +3200,8 @@ static inline int can_do_iterative_format(struct ref_filter *filter,\n \treturn !(filter->reachable_from ||\n \t\t filter->unreachable_from ||\n \t\t sorting ||\n-\t\t format->bases.nr);\n+\t\t format->bases.nr ||\n+\t\t format->is_base_tips.nr);\n }\n \n void filter_and_format_refs(struct ref_filter *filter, unsigned int type,\n@@ -3150,6 +3225,7 @@ void filter_and_format_refs(struct ref_filter *filter, unsigned int type,\n \t\tstruct ref_array array = { 0 };\n \t\tfilter_refs(&array, filter, type);\n \t\tfilter_ahead_behind(the_repository, format, &array);\n+\t\tfilter_is_base(the_repository, format, &array);\n \t\tref_array_sort(sorting, &array);\n \t\tprint_formatted_ref_array(&array, format);\n \t\tref_array_clear(&array);\ndiff --git a/ref-filter.h b/ref-filter.h\nindex 0ca28d2bba6..20419a56218 100644\n--- a/ref-filter.h\n+++ b/ref-filter.h\n@@ -48,6 +48,7 @@ struct ref_array_item {\n \tstruct commit *commit;\n \tstruct atom_value *value;\n \tstruct ahead_behind_count **counts;\n+\tchar **is_base;\n \n \tchar refname[FLEX_ARRAY];\n };\n@@ -101,6 +102,9 @@ struct ref_format {\n \t/* List of bases for ahead-behind counts. */\n \tstruct string_list bases;\n \n+\t/* List of bases for is-base indicators. */\n+\tstruct string_list is_base_tips;\n+\n \tstruct {\n \t\tint max_count;\n \t\tint omit_empty;\n@@ -114,6 +118,7 @@ struct ref_format {\n #define REF_FORMAT_INIT { \\\n \t.use_color = -1, \\\n \t.bases = STRING_LIST_INIT_DUP, \\\n+\t.is_base_tips = STRING_LIST_INIT_DUP, \\\n }\n \n /* Macros for checking --merged and --no-merged options */\n@@ -203,6 +208,16 @@ void filter_ahead_behind(struct repository *r,\n \t\t\t struct ref_format *format,\n \t\t\t struct ref_array *array);\n \n+/*\n+ * If the provided format includes is-base atoms, then compute the base checks\n+ * for those tips against all refs.\n+ *\n+ * If this is not called, then any is-base atoms will be blank.\n+ */\n+void filter_is_base(struct repository *r,\n+\t\t struct ref_format *format,\n+\t\t struct ref_array *array);\n+\n void ref_filter_init(struct ref_filter *filter);\n void ref_filter_clear(struct ref_filter *filter);\n \ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex 3069efc8601..6c7f92bcb38 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -659,4 +659,51 @@ test_expect_success 'get_branch_base_for_tip: all reach tip' '\n \ttest_all_modes get_branch_base_for_tip\n '\n \n+test_expect_success 'for-each-ref is-base: none reach' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-4-4\n+\trefs/heads/commit-8-4\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-1-1:\n+\trefs/heads/commit-4-2:(commit-2-3)\n+\trefs/heads/commit-4-4:\n+\trefs/heads/commit-8-4:\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname):%(is-base:commit-2-3)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref is-base: all reach' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-5-1\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-4-2:(commit-4-1)\n+\trefs/heads/commit-5-1:\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname):%(is-base:commit-4-1)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref is-base:multiple' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-4-4\n+\trefs/heads/commit-8-4\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-1-1[-]\n+\trefs/heads/commit-4-2[(commit-2-3)-]\n+\trefs/heads/commit-4-4[-]\n+\trefs/heads/commit-8-4[-(commit-6-5)]\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname)[%(is-base:commit-2-3)-%(is-base:commit-6-5)]\" --stdin\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"499912","messageId":"580026f910daaae6dba599fcd2408721b4f86c59.1722550226.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.git.1722550226.gitgitgadget@gmail.com","subject":"[PATCH 1/3] commit-reach: add get_branch_base_for_tip","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-01T22:10:24Z","receivedAt":"2024-08-01T22:10:31Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAdd a new reachability algorithm that intends to discover (from a heuristic)\nwhich branch was used as the starting point for a given commit. Add focused\ntests using the 'test-tool reach' command.\n\nRepositories that use pull requests (or merge requests) to advance one or\nmore \"protected\" branches, the history of that reference can be recovered by\nfollowing the first-parent history in most cases. Most are completed using\nno-fast-forward merges, though squash merges are quite common. Less common\nis rebase-and-merge, which still validates this assumption. Finally, the\ncase that breaks this assumption is the fast-forward update (with potential\nrebasing). Even in this case, the previous commit commonly appears in the\nfirst-parent history of the branch.\n\nSimilar assumptions can be made for a topic branch created by a single user\nwith the intention to merge back into another branch. Using 'git commit',\n'git merge', and 'git cherry-pick' from HEAD will default to having the\nfirst-parent commit be the previous commit at HEAD. This history changes\nonly with commands such as 'git reset' or 'git rebase', where the command\nnames also imply that the branch is starting from a new location.\n\nWith this movement of branches in mind, the following heuristic is proposed\nas a way to determine the base branch for a given source branch:\n\n Among a list of candidate base branches, select the candidate that\n minimizes the number of commits in the first-parent history of the source\n that are not in the first-parent history of the candidate.\n\nPrior third-party solutions to this problem have used this optimization\ncriteria, but have relied upon extracting the first-parent history and\ncomparing those lists as tables instead of using commit-graph walks.\n\nGiven current command-line interface options, this optimization criteria is\nnot easy to detect directly. Even using the command\n\n git rev-list --count --first-parent ..\n\ndoes not measure this count, as it uses full reachability from to\ndetermine which commits to remove from the range '..'. This\nmay lead to one asking if we should instead be using the full reachability\nof the candidate and only the first-parent history of the source. This,\nunfortunately, does not work for repositories that use long-lived branches\nand automation to merge across those branches.\n\nIn extremely large repositories, merging into a single trunk may not be\nfeasible. This is usually due to the desired frequency of updates\n(thousands of engineers doing daily work) combined with the time required to\nperform a validation build. These factors combine to create significant\nrisk of semantic merge conflicts, leading to build breaks on the trunk. In\nresponse, repository maintainers can create a single Level Zero (L0) trunk\nand multiple Level One (L1) branches. By partitioning the engineers by\norganization, these engineers may see lower risk of semantic merge conflicts\nas well as be protected against build breaks in other L1 branches. The key\nto making this system work is a semi-automated process of merging L1\nbranches into the L0 trunk and vice-versa. In a large enough organization,\nthese L1 branches may further split into L2 or L3 branches, but the same\nprinciples apply for merging across deeper levels.\n\nIf these automated merges use a typical merge with the second parent\nbringing in the \"new\" content, then each L0 and L1 branch can track its\nprevious positions by following first-parent history, which appear as\nparallel paths (until reaching the first place where the branches diverged).\nIf we also walk to second parents, then the histories overlap significantly\nand cannot be distinguished except for very-recent changes.\n\nFor this reason, the first-parent condition should be symmetrical across the\nbase and source branches.\n\nAnother common case for desiring the result of this optimization method is\nthe use of release branches. When releasing a version of a repository, a\nbranch can be used to track that release. Any updates that are worth fixing\nin that release can be merged to the release branch and shipped with only\nthe necessary fixes without any new features introduced in the trunk branch.\nThe 'maint-2.' branches represent this pattern in the Git project. The\nmicrosoft/git fork uses 'vfs-2..' branches to track the changes that\nare custom to that fork on top of each upstream Git release 2... This\napplication doesn't need the symmetrical first-parent condition, but the use\nof first-parent histories does not change the results for these branches.\n\nTo determine the base branch from a list of candidates, create a new method\nin commit-reach.c that performs a single* commit-graph walk. The core\nconcept is to walk first-parents starting at the candidate bases and the\nsource, tracking the \"best\" base to reach a given commit. Use generation\nnumbers to ensure that a commit is walked at most once and all children have\nbeen explored before visiting it. When reaching a commit that is reachable\nfrom both a base and the source, we will then have a guarantee that this is\nthe closest intersection of first-parent histories. Track the best base to\nreach that commit and return it as a result. In rare cases involving\nmultiple root commits, the first-parent history of the source may never\nintersect any of the candidates and thus a null result is returned.\n\n* There are up to two walks, since we require all commits to have a computed\n generation number in order to avoid incorrect results. This is similar to\n the need for computed generation numbers in ahead_behind() as implemented\n in fd67d149bde (commit-reach: implement ahead_behind() logic, 2023-03-20).\n\nIn order to track the \"best\" base, use a new commit slab that stores an\ninteger. This value defaults to zero upon initialization, so use -1 to\ntrack that the source commit can reach this commit and use 'i + 1' to track\nthat the ith base can reach this commit. When multiple bases can reach a\ncommit, minimize the index to break ties. This allows the caller to specify\nan order to the bases that determines some amount of preference when the\nheuristic does not result in a unique result.\n\nThe trickiest part of the integer slab is what happens when reaching a\ncollision among the histories of the bases and the history of the source.\nThis is noticed when viewing the first parent and seeing that it has a slab\nvalue that differs in sign (negative or positive). In this case, the\ncollision commit is stored in the method variable 'branch_point' and its\nslab value is set to -1. The index of the best base (so far) is stored in\nthe method variable 'best_index'. It is possible that there are multiple\ncommits that have the branch_point as its first parent, leading to multiple\nupdates of best_index. The result is determined when 'branch_point' is\nvisited in the commit walk, giving the guarantee that all commits that could\nreach 'branch_point' were visited.\n\nSeveral interesting cases of collisions and different results are tested in\nthe t6600-test-reach.sh script. Recall that this script also tests the\nalgorithm in three possible states involving the commit-graph file and how\nmany commits are written in the file. This provides some coverage of the\nneed (and lack of need) for the ensure_generations_valid() method.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 118 ++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 17 ++++++\n t/helper/test-reach.c | 2 +\n t/t6600-test-reach.sh | 47 +++++++++++++++++\n 4 files changed, 184 insertions(+)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 8f9b008f876..1b56fb081a6 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1222,3 +1222,121 @@ done:\n \tfree(commits);\n \trepo_clear_commit_marks(r, SEEN);\n }\n+\n+/*\n+ * This slab initializes integers to zero, so use \"-1\" for \"tip is best\" and\n+ * \"i + 1\" for \"bases[i] is best\".\n+ */\n+define_commit_slab(best_branch_base, int);\n+static struct best_branch_base best_branch_base;\n+#define get_best(c) (*best_branch_base_at(&best_branch_base, c))\n+#define set_best(c,v) (*best_branch_base_at(&best_branch_base, c) = v)\n+\n+int get_branch_base_for_tip(struct repository *r,\n+\t\t\t struct commit *tip,\n+\t\t\t struct commit **bases,\n+\t\t\t size_t bases_nr)\n+{\n+\tint best_index = -1;\n+\tstruct commit *branch_point = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tint found_missing_gen = 0;\n+\n+\tif (!bases_nr)\n+\t\treturn -1;\n+\n+\trepo_parse_commit(r, tip);\n+\tif (commit_graph_generation(tip) == GENERATION_NUMBER_INFINITY)\n+\t\tfound_missing_gen = 1;\n+\n+\t/* Check for missing generation numbers. */\n+\tfor (size_t i = 0; i < bases_nr; i++) {\n+\t\tstruct commit *c = bases[i];\n+\t\trepo_parse_commit(r, c);\n+\t\tif (commit_graph_generation(c) == GENERATION_NUMBER_INFINITY)\n+\t\t\tfound_missing_gen = 1;\n+\t}\n+\n+\tif (found_missing_gen) {\n+\t\tstruct commit **commits;\n+\t\tsize_t commits_nr = bases_nr + 1;\n+\n+\t\tCALLOC_ARRAY(commits, commits_nr);\n+\t\tCOPY_ARRAY(commits, bases, bases_nr);\n+\t\tcommits[bases_nr] = tip;\n+\t\tensure_generations_valid(r, commits, commits_nr);\n+\t\tfree(commits);\n+\t}\n+\n+\t/* Initialize queue and slab now that generations are guaranteed. */\n+\tinit_best_branch_base(&best_branch_base);\n+\tset_best(tip, -1);\n+\tprio_queue_put(&queue, tip);\n+\n+\tfor (size_t i = 0; i < bases_nr; i++) {\n+\t\tstruct commit *c = bases[i];\n+\n+\t\t/* Has this already been marked as best by another commit? */\n+\t\tif (get_best(c))\n+\t\t\tcontinue;\n+\n+\t\tset_best(c, i + 1);\n+\t\tprio_queue_put(&queue, c);\n+\t}\n+\n+\twhile (queue.nr) {\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\t\tint best_for_c = get_best(c);\n+\t\tint best_for_p, positive;\n+\t\tstruct commit *parent;\n+\n+\t\t/* Have we reached a known branch point? It's optimal. */\n+\t\tif (c == branch_point)\n+\t\t\tbreak;\n+\n+\t\trepo_parse_commit(r, c);\n+\t\tif (!c->parents)\n+\t\t\tcontinue;\n+\n+\t\tparent = c->parents->item;\n+\t\trepo_parse_commit(r, parent);\n+\t\tbest_for_p = get_best(parent);\n+\n+\t\tif (!best_for_p) {\n+\t\t\t/* 'parent' is new, so pass along best_for_c. */\n+\t\t\tset_best(parent, best_for_c);\n+\t\t\tprio_queue_put(&queue, parent);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (best_for_p > 0 && best_for_c > 0) {\n+\t\t\t/* Collision among bases. Minimize. */\n+\t\t\tif (best_for_c < best_for_p)\n+\t\t\t\tset_best(parent, best_for_c);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/*\n+\t\t * At this point, we have reached a commit that is reachable\n+\t\t * from the tip, either from 'c' or from an earlier commit to\n+\t\t * have 'parent' as its first parent.\n+\t\t *\n+\t\t * Update 'best_index' to match the minimum of all base indices\n+\t\t * to reach 'parent'.\n+\t\t */\n+\n+\t\t/* Exactly one is positive due to initial conditions. */\n+\t\tpositive = (best_for_c < 0) ? best_for_p : best_for_c;\n+\n+\t\tif (best_index < 0 || positive < best_index)\n+\t\t\tbest_index = positive;\n+\n+\t\t/* No matter what, track that the parent is reachable from tip. */\n+\t\tset_best(parent, -1);\n+\t\tbranch_point = parent;\n+\t}\n+\n+\tclear_best_branch_base(&best_branch_base);\n+\tclear_prio_queue(&queue);\n+\treturn best_index > 0 ? best_index - 1 : -1;\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex bf63cc468fd..9a745b7e176 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -139,4 +139,21 @@ void tips_reachable_from_bases(struct repository *r,\n \t\t\t struct commit **tips, size_t tips_nr,\n \t\t\t int mark);\n \n+/*\n+ * Given a 'tip' commit and a list potential 'bases', return the index 'i' that\n+ * minimizes the number of commits in the first-parent history of 'tip' and not\n+ * in the first-parent history of 'bases[i]'.\n+ *\n+ * Among a list of long-lived branches that are updated only by merges (with the\n+ * first parent being the previous position of the branch), this would inform\n+ * which branch was used to create the tip reference.\n+ *\n+ * Returns -1 if no common point is found in first-parent histories, which is\n+ * rare, but possible with multiple root commits.\n+ */\n+int get_branch_base_for_tip(struct repository *r,\n+\t\t\t struct commit *tip,\n+\t\t\t struct commit **bases,\n+\t\t\t size_t bases_nr);\n+\n #endif\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 1e3b431e3e7..8579b607aa5 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -114,6 +114,8 @@ int cmd__reach(int ac, const char **av)\n \t\t repo_in_merge_bases_many(the_repository, A, X_nr, X_array, 0));\n \telse if (!strcmp(av[1], \"is_descendant_of\"))\n \t\tprintf(\"%s(A,X):%d\\n\", av[1], repo_is_descendant_of(r, A, X));\n+\telse if (!strcmp(av[1], \"get_branch_base_for_tip\"))\n+\t\tprintf(\"%s(A,X):%d\\n\", av[1], get_branch_base_for_tip(r, A, X_array, X_nr));\n \telse if (!strcmp(av[1], \"get_merge_bases_many\")) {\n \t\tstruct commit_list *list = NULL;\n \t\tif (repo_get_merge_bases_many(the_repository,\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b330945f497..3069efc8601 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -612,4 +612,51 @@ test_expect_success 'for-each-ref merged:none' '\n \t\t--format=\"%(refname)\" --stdin\n '\n \n+# For get_branch_base_for_tip, we only care about\n+# first-parent history. Here is the test graph with\n+# second parents removed:\n+#\n+# (10,10)\n+# /\n+# (10,9) (9,10)\n+# / /\n+# (10,8) (9,9) (8,10)\n+# / / /\n+# ( continued...)\n+# \\ / / /\n+# (3,1) (2,2) (1,3)\n+# \\ / /\n+# (2,1) (1,2)\n+# \\ /\n+# (1,1)\n+#\n+# In short, for a commit (i,j), the first-parent history\n+# walks all commits (i, k) with k from j to 1, then the\n+# commits (l, 1) with l from i to 1.\n+\n+test_expect_success 'get_branch_base_for_tip: none reach' '\n+\t# (2,3) branched from the first tip (i,4) in X with i > 2\n+\tcat >input <<-\\EOF &&\n+\t\tA:commit-2-3\n+\t\tX:commit-1-2\n+\t\tX:commit-1-4\n+\t\tX:commit-4-4\n+\t\tX:commit-8-4\n+\t\tX:commit-10-4\n+\tEOF\n+\techo \"get_branch_base_for_tip(A,X):2\" >expect &&\n+\ttest_all_modes get_branch_base_for_tip\n+'\n+\n+test_expect_success 'get_branch_base_for_tip: all reach tip' '\n+\t# (2,3) branched from the first tip (i,4) in X with i > 2\n+\tcat >input <<-\\EOF &&\n+\t\tA:commit-4-1\n+\t\tX:commit-4-2\n+\t\tX:commit-5-1\n+\tEOF\n+\techo \"get_branch_base_for_tip(A,X):0\" >expect &&\n+\ttest_all_modes get_branch_base_for_tip\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"499910","messageId":"db87434e146df2228529dc967bdd2e8f34c59f72.1722550226.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.git.1722550226.gitgitgadget@gmail.com","subject":"[PATCH 3/3] p1500: add is-base performance tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-01T22:10:26Z","receivedAt":"2024-08-01T22:10:32Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous two changes introduced a commit walking heuristic for finding\nthe most likely base branch for a given source. This algorithm walks\nfirst-parent histories until reaching a collision.\n\nThis walk _should_ be very fast. Exceptions include cases where a\ncommit-graph file does not exist, leading to a full walk of all reachable\ncommits to compute generation numbers, or a case where no collision in the\nfirst-parent history exists, leading to a walk of all first-parent history\nto the root commits.\n\nThe p1500 test script guarantees a complete commit-graph file during its\nsetup, so we will not test that scenario. Do create a new root commit in an\neffort to test the scenario of parallel first-parent histories.\n\nEven with the extra root commit, these tests take no longer than 0.02\nseconds on my machine for the Git repository. However, the results are\nslightly more interesting in a copy of the Linux kernel repository:\n\nTest\n---------------------------------------------------------------\n1500.2: ahead-behind counts: git for-each-ref 0.12\n1500.3: ahead-behind counts: git branch 0.12\n1500.4: ahead-behind counts: git tag 0.12\n1500.5: contains: git for-each-ref --merged 0.04\n1500.6: contains: git branch --merged 0.04\n1500.7: contains: git tag --merged 0.04\n1500.8: is-base check: test-tool reach (refs) 0.03\n1500.9: is-base check: test-tool reach (tags) 0.03\n1500.10: is-base check: git for-each-ref 0.03\n1500.11: is-base check: git for-each-ref (disjoint-base) 0.07\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p1500-graph-walks.sh | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\nindex e14e7620cce..5b23ce5db93 100755\n--- a/t/perf/p1500-graph-walks.sh\n+++ b/t/perf/p1500-graph-walks.sh\n@@ -20,6 +20,21 @@ test_expect_success 'setup' '\n \t\techo tag-$ref ||\n \t\treturn 1\n \tdone >tags &&\n+\n+\techo \"A:HEAD\" >test-tool-refs &&\n+\tfor line in $(cat refs)\n+\tdo\n+\t\techo \"X:$line\" >>test-tool-refs || return 1\n+\tdone &&\n+\techo \"A:HEAD\" >test-tool-tags &&\n+\tfor line in $(cat tags)\n+\tdo\n+\t\techo \"X:$line\" >>test-tool-tags || return 1\n+\tdone &&\n+\n+\tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n+\tgit update-ref refs/heads/disjoint-base $commit &&\n+\n \tgit commit-graph write --reachable\n '\n \n@@ -47,4 +62,20 @@ test_perf 'contains: git tag --merged' '\n \txargs git tag --merged=HEAD writes:\n\n> Derrick Stolee (3):\n> commit-reach: add get_branch_base_for_tip\n> for-each-ref: add 'is-base' token\n> p1500: add is-base performance tests\n>\n> commit-reach.c | 118 ++++++++++++++++++++++++++++++++++++\n> commit-reach.h | 17 ++++++\n> ref-filter.c | 78 +++++++++++++++++++++++-\n> ref-filter.h | 15 +++++\n> t/helper/test-reach.c | 2 +\n> t/perf/p1500-graph-walks.sh | 31 ++++++++++\n> t/t6600-test-reach.sh | 94 ++++++++++++++++++++++++++++\n> 7 files changed, 354 insertions(+), 1 deletion(-)\n\nI was expecting to see an documentation update to for-each-ref (and\nprobably branch and tag) so that what this new atom means. Is it\nthat %(is-base:) interpolates to for a ref that is an\nancestor of , and interpolates to an empty string for a ref\nthat is not, or something?\n\nThanks.\n\n"},{"id":"499947","messageId":"27f3de89-55b2-413d-b4b4-6b35f8c4bcc9@gmail.com","threadId":"61884","inReplyTo":"xmqqmslvhmgm.fsf@gitster.g","subject":"Re: [PATCH 0/3] git for-each-ref: is-base atom and base branches","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-08-02T14:32:46Z","receivedAt":"2024-08-02T14:32:49Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/1/24 7:06 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> Derrick Stolee (3):\n>> commit-reach: add get_branch_base_for_tip\n>> for-each-ref: add 'is-base' token\n>> p1500: add is-base performance tests\n>>\n>> commit-reach.c | 118 ++++++++++++++++++++++++++++++++++++\n>> commit-reach.h | 17 ++++++\n>> ref-filter.c | 78 +++++++++++++++++++++++-\n>> ref-filter.h | 15 +++++\n>> t/helper/test-reach.c | 2 +\n>> t/perf/p1500-graph-walks.sh | 31 ++++++++++\n>> t/t6600-test-reach.sh | 94 ++++++++++++++++++++++++++++\n>> 7 files changed, 354 insertions(+), 1 deletion(-)\n> \n> I was expecting to see an documentation update to for-each-ref (and\n> probably branch and tag) so that what this new atom means. Is it\n> that %(is-base:) interpolates to for a ref that is an\n> ancestor of , and interpolates to an empty string for a ref\n> that is not, or something?\n\nYou are absolutely right that I missed this crucial detail. I will\neventually send a v2 with this oversight corrected. For now, please\nconsider this documentation diff, and I look forward to other review\ncomments that I can use to improve this series before sending v2.\n\ndiff --git a/Documentation/git-for-each-ref.txt \nb/Documentation/git-for-each-ref.txt\nindex c1dd12b93cf..5154ba3e2a7 100644\n--- a/Documentation/git-for-each-ref.txt\n+++ b/Documentation/git-for-each-ref.txt\n@@ -264,6 +264,16 @@ ahead-behind:::\n \tcommits ahead and behind, respectively, when comparing the output\n \tref to the `` specified in the format.\n\n+is-base:::\n+\tIn at most one row, `()` will appear to indicate the ref\n+\tthat minimizes the number of commits in the first-parent history of\n+\t`` and not in the first-parent history of the ref. Ties\n+\tare broken by favoring the earliest ref in the list. Note that this\n+\ttoken will not appear if the first-parent history of ``\n+\tdoes not intersect the first-parent histories of the filtered refs.\n+\tThis can be used as a heuristic to guess which of the filtered refs\n+\twas used as the base of the branch that produced ``.\n+\n describe[:options]::\n \tA human-readable name, like linkgit:git-describe[1];\n \tempty string for undescribable commits. The `describe` string may\n\n"},{"id":"499961","messageId":"xmqqzfpudful.fsf@gitster.g","threadId":"61884","inReplyTo":"27f3de89-55b2-413d-b4b4-6b35f8c4bcc9@gmail.com","subject":"Re: [PATCH 0/3] git for-each-ref: is-base atom and base branches","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-08-02T16:55:30Z","receivedAt":"2024-08-02T16:55:36Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Derrick Stolee writes:\n\n> consider this documentation diff, and I look forward to other review\n> comments that I can use to improve this series before sending v2.\n>\n> diff --git a/Documentation/git-for-each-ref.txt\n> b/Documentation/git-for-each-ref.txt\n> index c1dd12b93cf..5154ba3e2a7 100644\n> --- a/Documentation/git-for-each-ref.txt\n> +++ b/Documentation/git-for-each-ref.txt\n> @@ -264,6 +264,16 @@ ahead-behind:::\n> \tcommits ahead and behind, respectively, when comparing the output\n> \tref to the `` specified in the format.\n>\n> +is-base:::\n> +\tIn at most one row, `()` will appear to indicate the ref\n> +\tthat minimizes the number of commits in the first-parent history of\n> +\t`` and not in the first-parent history of the ref. Ties\n> +\tare broken by favoring the earliest ref in the list. Note that this\n> +\ttoken will not appear if the first-parent history of ``\n> +\tdoes not intersect the first-parent histories of the filtered refs.\n> +\tThis can be used as a heuristic to guess which of the filtered refs\n> +\twas used as the base of the branch that produced ``.\n> +\n\nOK. Knowing what definition you used is crucial when reading the\nimplementation, as we cannot tell what you wanted to implement\nwithout it ;-)\n\nThanks.\n"},{"id":"499963","messageId":"xmqqo76ade8r.fsf@gitster.g","threadId":"61884","inReplyTo":"xmqqzfpudful.fsf@gitster.g","subject":"Re: [PATCH 0/3] git for-each-ref: is-base atom and base branches","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-08-02T17:30:12Z","receivedAt":"2024-08-02T17:30:20Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano writes:\n\n>> +is-base:::\n>> +\tIn at most one row, `()` will appear to indicate the ref\n>> +\tthat minimizes the number of commits in the first-parent history of\n>> +\t`` and not in the first-parent history of the ref.\n\nThis was a bit too dense for me to grok. So if I have a \nthat is at the tip of a branch B forked from 'master', and then\n'master' advanced by a lot since the branch forked, the number this\nis minimizing for 'master' is the commits on the branch B, but when\nshowing 'maint', then even though the branch B may have the tip of\n'maint' as an ancestor, the number for 'maint' would be a lot more\nthan the number for 'master'. If there were another branch C that\nwas forked from 'master' and shared some (or all) commits that are\nnear the tip of branch B, e.g.\n\n ---o---o---o---o---o---o---o---o---o 'master'\n \\\n o---o---o---o 'C'\n \\ \n o---o---o---o 'B'\n\nthen the number may be even smaller for branch 'C' than 'master'.\n\nAnd for at most one ref, %(is-base:) becomes \"()\";\nfor all other refs, it becomes an empty string.\n\nOK.\n\n> OK. Knowing what definition you used is crucial when reading the\n> implementation, as we cannot tell what you wanted to implement\n> without it ;-)\n>\n> Thanks.\n"},{"id":"500603","messageId":"pull.1768.v2.git.1723397687.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.git.1722550226.gitgitgadget@gmail.com","subject":"[PATCH v2 0/3] git for-each-ref: is-base atom and base branches","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-11T17:34:44Z","receivedAt":"2024-08-11T17:34:50Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This change introduces a new 'git for-each-ref' atom, 'is-base', in a very\nsimilar way to the 'ahead-behind' atom. As detailed carefully in the first\nchange, this is motivated by the need to detect the concept of a \"base\nbranch\" in a repository with multiple long-lived branches.\n\nThis change is motivated by a third-party tool created to make this\ndetection with the same optimization mechanism, but using a much slower\ntechnique due to the limitations of the Git CLI not presenting this\ninformation. The existing algorithm involves using git rev-list\n--first-parent - in batches for the collection of considered references,\ncomparing those lists, and increasing as needed until finding a\ncollision. This new use of 'git for-each-ref' will allow determining this\nmechanism within a single process and walking a minimal number of commits.\n\nThere are benefits to users both on client-side and server-side. In an\ninternal monorepo, this base branch detection algorithm is used to determine\na long-lived branch based on the HEAD commit, mapping to a group within the\norganizational structure of the repository, which determines a set of\nprojects that the user will likely need to build; this leads to\nautomatically selecting an initial sparse-checkout definition based on the\nbuild dependencies required. An upcoming feature in Azure Repos will use\nthis algorithm to automatically create a pull request against the correct\ntarget branch, reducing user pain from needing to select a different branch\nafter a large commit diff is rendered against the default branch. This atom\nunlocks that ability for Git hosting services that use Git in their backend.\n\nThanks, -Stolee\n\n\nUpdates in v2\n=============\n\n * I had forgotten to include a documentation change in v1. My attempt to\n create a succinct doc change in a follow-up hunk continued to be\n confusing. This version includes a more expanded version of the\n documentation blurb for the is-base token.\n\nDerrick Stolee (3):\n commit-reach: add get_branch_base_for_tip\n for-each-ref: add 'is-base' token\n p1500: add is-base performance tests\n\n Documentation/git-for-each-ref.txt | 42 ++++++++++\n commit-reach.c | 118 +++++++++++++++++++++++++++++\n commit-reach.h | 17 +++++\n ref-filter.c | 78 ++++++++++++++++++-\n ref-filter.h | 15 ++++\n t/helper/test-reach.c | 2 +\n t/perf/p1500-graph-walks.sh | 31 ++++++++\n t/t6600-test-reach.sh | 94 +++++++++++++++++++++++\n 8 files changed, 396 insertions(+), 1 deletion(-)\n\n\nbase-commit: bea9ecd24b0c3bf06cab4a851694fe09e7e51408\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1768%2Fderrickstolee%2Ftarget-ref-v2\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1768/derrickstolee/target-ref-v2\nPull-Request: https://github.com/gitgitgadget/git/pull/1768\n\nRange-diff vs v1:\n\n 1: 580026f910d = 1: 580026f910d commit-reach: add get_branch_base_for_tip\n 2: a1fbdca374f ! 2: 13341e7e512 for-each-ref: add 'is-base' token\n @@ Commit message\n \n Signed-off-by: Derrick Stolee \n \n + ## Documentation/git-for-each-ref.txt ##\n +@@ Documentation/git-for-each-ref.txt: ahead-behind:::\n + \tcommits ahead and behind, respectively, when comparing the output\n + \tref to the `` specified in the format.\n + \n ++is-base:::\n ++\tIn at most one row, `()` will appear to indicate the ref\n ++\tthat is most likely the ref used as a starting point for the branch\n ++\tthat produced ``. This choice is made using a heuristic:\n ++\tchoose the ref that minimizes the number of commits in the\n ++\tfirst-parent history of `` and not in the first-parent\n ++\thistory of the ref.\n +++\n ++For example, consider the following figure of first-parent histories of\n ++several refs:\n +++\n ++----\n ++*--*--*--*--*--* refs/heads/A\n ++\\\n ++ \\\n ++ *--*--*--* refs/heads/B\n ++ \\ \\\n ++ \\ \\\n ++ * * refs/heads/C\n ++ \\\n ++ \\\n ++\t*--* refs/heads/D\n ++----\n +++\n ++Here, if `A`, `B`, and `C` are the filtered references, and the format\n ++string is `%(refname):%(is-base:D)`, then the output would be\n +++\n ++----\n ++refs/heads/A:\n ++refs/heads/B:(D)\n ++refs/heads/C:\n ++----\n +++\n ++This is because the first-parent history of `D` has its earliest\n ++intersection with the first-parent histories of the filtered refs at a\n ++common first-parent ancestor of `B` and `C` and ties are broken by the\n ++earliest ref in the sorted order.\n +++\n ++Note that this token will not appear if the first-parent history of\n ++`` does not intersect the first-parent histories of the\n ++filtered refs.\n ++\n + describe[:options]::\n + \tA human-readable name, like linkgit:git-describe[1];\n + \tempty string for undescribable commits. The `describe` string may\n +\n ## ref-filter.c ##\n @@ ref-filter.c: enum atom_type {\n \tATOM_ELSE,\n 3: db87434e146 = 3: 757c20090db p1500: add is-base performance tests\n\n-- \ngitgitgadget\n"},{"id":"500604","messageId":"13341e7e51241e077a85ea83eb76d4e48d04be7b.1723397687.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v2.git.1723397687.gitgitgadget@gmail.com","subject":"[PATCH v2 2/3] for-each-ref: add 'is-base' token","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-11T17:34:46Z","receivedAt":"2024-08-11T17:34:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change introduced the get_branch_base_for_tip() method in\ncommit-reach.c. The motivation of that change was about using a heuristic to\ndeteremine the base branch for a source commit from a list of candidate\ncommit tips. This change makes that algorithm visible to users via a new\natom in the 'git for-each-ref' format. This change is very similar to the\nchang in 49abcd21da6 (for-each-ref: add ahead-behind format atom,\n2023-03-20).\n\nIntroduce the 'is-base:' atom, which will indicate that the\nalgorithm should be computed and the result of the algorithm is reported\nusing an indicator of the form '()'. For example, using\n'%(is-base:HEAD)' would result in one line having the token '(HEAD)'.\n\nUse the sorted order of refs included in the ref filter to break ties in the\nalgorithm's heuristic. In the previous change, the motivating examples\ninclude using an L0 trunk, long-lived L1 branches, and temporary release\nbranches. A caller could communicate the ordered preference among these\ncategories using the input refpecs and avoiding a different sort mechanism.\nThis sorting behavior is tested in the test scripts.\n\nIt is important to include this atom as a special case to\ncan_do_iterative_format() to match the expectations created in bd98f9774e1\n(ref-filter.c: filter & format refs in the same callback, 2023-11-14). The\nahead-behind atom was one of the special cases, and this similarly requires\nusing an algorithm across all input refs before starting the format of any\nsingle ref.\n\nIn the test script, the format tokens use colons or lack whitespace to avoid\nGit complaining about trailing whitespace errors.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-for-each-ref.txt | 42 ++++++++++++++++\n ref-filter.c | 78 +++++++++++++++++++++++++++++-\n ref-filter.h | 15 ++++++\n t/t6600-test-reach.sh | 47 ++++++++++++++++++\n 4 files changed, 181 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt\nindex c1dd12b93cf..d3764401a23 100644\n--- a/Documentation/git-for-each-ref.txt\n+++ b/Documentation/git-for-each-ref.txt\n@@ -264,6 +264,48 @@ ahead-behind:::\n \tcommits ahead and behind, respectively, when comparing the output\n \tref to the `` specified in the format.\n \n+is-base:::\n+\tIn at most one row, `()` will appear to indicate the ref\n+\tthat is most likely the ref used as a starting point for the branch\n+\tthat produced ``. This choice is made using a heuristic:\n+\tchoose the ref that minimizes the number of commits in the\n+\tfirst-parent history of `` and not in the first-parent\n+\thistory of the ref.\n++\n+For example, consider the following figure of first-parent histories of\n+several refs:\n++\n+----\n+*--*--*--*--*--* refs/heads/A\n+\\\n+ \\\n+ *--*--*--* refs/heads/B\n+ \\ \\\n+ \\ \\\n+ * * refs/heads/C\n+ \\\n+ \\\n+\t*--* refs/heads/D\n+----\n++\n+Here, if `A`, `B`, and `C` are the filtered references, and the format\n+string is `%(refname):%(is-base:D)`, then the output would be\n++\n+----\n+refs/heads/A:\n+refs/heads/B:(D)\n+refs/heads/C:\n+----\n++\n+This is because the first-parent history of `D` has its earliest\n+intersection with the first-parent histories of the filtered refs at a\n+common first-parent ancestor of `B` and `C` and ties are broken by the\n+earliest ref in the sorted order.\n++\n+Note that this token will not appear if the first-parent history of\n+`` does not intersect the first-parent histories of the\n+filtered refs.\n+\n describe[:options]::\n \tA human-readable name, like linkgit:git-describe[1];\n \tempty string for undescribable commits. The `describe` string may\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 59ad6f54ddb..59689672da1 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -167,6 +167,7 @@ enum atom_type {\n \tATOM_ELSE,\n \tATOM_REST,\n \tATOM_AHEADBEHIND,\n+\tATOM_ISBASE,\n };\n \n /*\n@@ -889,6 +890,23 @@ static int ahead_behind_atom_parser(struct ref_format *format,\n \treturn 0;\n }\n \n+static int is_base_atom_parser(struct ref_format *format,\n+\t\t\t struct used_atom *atom UNUSED,\n+\t\t\t const char *arg, struct strbuf *err)\n+{\n+\tstruct string_list_item *item;\n+\n+\tif (!arg)\n+\t\treturn strbuf_addf_ret(err, -1, _(\"expected format: %%(is-base:)\"));\n+\n+\titem = string_list_append(&format->is_base_tips, arg);\n+\titem->util = lookup_commit_reference_by_name(arg);\n+\tif (!item->util)\n+\t\tdie(\"failed to find '%s'\", arg);\n+\n+\treturn 0;\n+}\n+\n static int head_atom_parser(struct ref_format *format UNUSED,\n \t\t\t struct used_atom *atom,\n \t\t\t const char *arg, struct strbuf *err)\n@@ -952,6 +970,7 @@ static struct {\n \t[ATOM_ELSE] = { \"else\", SOURCE_NONE },\n \t[ATOM_REST] = { \"rest\", SOURCE_NONE, FIELD_STR, rest_atom_parser },\n \t[ATOM_AHEADBEHIND] = { \"ahead-behind\", SOURCE_OTHER, FIELD_STR, ahead_behind_atom_parser },\n+\t[ATOM_ISBASE] = { \"is-base\", SOURCE_OTHER, FIELD_STR, is_base_atom_parser },\n \t/*\n \t * Please update $__git_ref_fieldlist in git-completion.bash\n \t * when you add new atoms\n@@ -2334,6 +2353,7 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err)\n \tint i;\n \tstruct object_info empty = OBJECT_INFO_INIT;\n \tint ahead_behind_atoms = 0;\n+\tint is_base_atoms = 0;\n \n \tCALLOC_ARRAY(ref->value, used_atom_cnt);\n \n@@ -2475,6 +2495,16 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err)\n \t\t\t\tv->s = xstrdup(\"\");\n \t\t\t}\n \t\t\tcontinue;\n+\t\t} else if (atom_type == ATOM_ISBASE) {\n+\t\t\tif (ref->is_base && ref->is_base[is_base_atoms]) {\n+\t\t\t\tv->s = xstrfmt(\"(%s)\", ref->is_base[is_base_atoms]);\n+\t\t\t\tfree(ref->is_base[is_base_atoms]);\n+\t\t\t} else {\n+\t\t\t\t/* Not a commit. */\n+\t\t\t\tv->s = xstrdup(\"\");\n+\t\t\t}\n+\t\t\tis_base_atoms++;\n+\t\t\tcontinue;\n \t\t} else\n \t\t\tcontinue;\n \n@@ -2876,6 +2906,7 @@ static void free_array_item(struct ref_array_item *item)\n \t\tfree(item->value);\n \t}\n \tfree(item->counts);\n+\tfree(item->is_base);\n \tfree(item);\n }\n \n@@ -3040,6 +3071,49 @@ void filter_ahead_behind(struct repository *r,\n \tfree(commits);\n }\n \n+void filter_is_base(struct repository *r,\n+\t\t struct ref_format *format,\n+\t\t struct ref_array *array)\n+{\n+\tstruct commit **bases;\n+\tsize_t bases_nr = 0;\n+\tstruct ref_array_item **back_index;\n+\n+\tif (!format->is_base_tips.nr || !array->nr)\n+\t\treturn;\n+\n+\tCALLOC_ARRAY(back_index, array->nr);\n+\tCALLOC_ARRAY(bases, array->nr);\n+\n+\tfor (size_t i = 0; i < array->nr; i++) {\n+\t\tconst char *name = array->items[i]->refname;\n+\t\tstruct commit *c = lookup_commit_reference_by_name(name);\n+\n+\t\tCALLOC_ARRAY(array->items[i]->is_base, format->is_base_tips.nr);\n+\n+\t\tif (!c)\n+\t\t\tcontinue;\n+\n+\t\tback_index[bases_nr] = array->items[i];\n+\t\tbases[bases_nr] = c;\n+\t\tbases_nr++;\n+\t}\n+\n+\tfor (size_t i = 0; i < format->is_base_tips.nr; i++) {\n+\t\tstruct commit *tip = format->is_base_tips.items[i].util;\n+\t\tint base_index = get_branch_base_for_tip(r, tip, bases, bases_nr);\n+\n+\t\tif (base_index < 0)\n+\t\t\tcontinue;\n+\n+\t\t/* Store the string for use in output later. */\n+\t\tback_index[base_index]->is_base[i] = xstrdup(format->is_base_tips.items[i].string);\n+\t}\n+\n+\tfree(back_index);\n+\tfree(bases);\n+}\n+\n static int do_filter_refs(struct ref_filter *filter, unsigned int type, each_ref_fn fn, void *cb_data)\n {\n \tint ret = 0;\n@@ -3126,7 +3200,8 @@ static inline int can_do_iterative_format(struct ref_filter *filter,\n \treturn !(filter->reachable_from ||\n \t\t filter->unreachable_from ||\n \t\t sorting ||\n-\t\t format->bases.nr);\n+\t\t format->bases.nr ||\n+\t\t format->is_base_tips.nr);\n }\n \n void filter_and_format_refs(struct ref_filter *filter, unsigned int type,\n@@ -3150,6 +3225,7 @@ void filter_and_format_refs(struct ref_filter *filter, unsigned int type,\n \t\tstruct ref_array array = { 0 };\n \t\tfilter_refs(&array, filter, type);\n \t\tfilter_ahead_behind(the_repository, format, &array);\n+\t\tfilter_is_base(the_repository, format, &array);\n \t\tref_array_sort(sorting, &array);\n \t\tprint_formatted_ref_array(&array, format);\n \t\tref_array_clear(&array);\ndiff --git a/ref-filter.h b/ref-filter.h\nindex 0ca28d2bba6..20419a56218 100644\n--- a/ref-filter.h\n+++ b/ref-filter.h\n@@ -48,6 +48,7 @@ struct ref_array_item {\n \tstruct commit *commit;\n \tstruct atom_value *value;\n \tstruct ahead_behind_count **counts;\n+\tchar **is_base;\n \n \tchar refname[FLEX_ARRAY];\n };\n@@ -101,6 +102,9 @@ struct ref_format {\n \t/* List of bases for ahead-behind counts. */\n \tstruct string_list bases;\n \n+\t/* List of bases for is-base indicators. */\n+\tstruct string_list is_base_tips;\n+\n \tstruct {\n \t\tint max_count;\n \t\tint omit_empty;\n@@ -114,6 +118,7 @@ struct ref_format {\n #define REF_FORMAT_INIT { \\\n \t.use_color = -1, \\\n \t.bases = STRING_LIST_INIT_DUP, \\\n+\t.is_base_tips = STRING_LIST_INIT_DUP, \\\n }\n \n /* Macros for checking --merged and --no-merged options */\n@@ -203,6 +208,16 @@ void filter_ahead_behind(struct repository *r,\n \t\t\t struct ref_format *format,\n \t\t\t struct ref_array *array);\n \n+/*\n+ * If the provided format includes is-base atoms, then compute the base checks\n+ * for those tips against all refs.\n+ *\n+ * If this is not called, then any is-base atoms will be blank.\n+ */\n+void filter_is_base(struct repository *r,\n+\t\t struct ref_format *format,\n+\t\t struct ref_array *array);\n+\n void ref_filter_init(struct ref_filter *filter);\n void ref_filter_clear(struct ref_filter *filter);\n \ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex 3069efc8601..6c7f92bcb38 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -659,4 +659,51 @@ test_expect_success 'get_branch_base_for_tip: all reach tip' '\n \ttest_all_modes get_branch_base_for_tip\n '\n \n+test_expect_success 'for-each-ref is-base: none reach' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-4-4\n+\trefs/heads/commit-8-4\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-1-1:\n+\trefs/heads/commit-4-2:(commit-2-3)\n+\trefs/heads/commit-4-4:\n+\trefs/heads/commit-8-4:\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname):%(is-base:commit-2-3)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref is-base: all reach' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-5-1\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-4-2:(commit-4-1)\n+\trefs/heads/commit-5-1:\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname):%(is-base:commit-4-1)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref is-base:multiple' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-4-4\n+\trefs/heads/commit-8-4\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-1-1[-]\n+\trefs/heads/commit-4-2[(commit-2-3)-]\n+\trefs/heads/commit-4-4[-]\n+\trefs/heads/commit-8-4[-(commit-6-5)]\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname)[%(is-base:commit-2-3)-%(is-base:commit-6-5)]\" --stdin\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"500606","messageId":"580026f910daaae6dba599fcd2408721b4f86c59.1723397687.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v2.git.1723397687.gitgitgadget@gmail.com","subject":"[PATCH v2 1/3] commit-reach: add get_branch_base_for_tip","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-11T17:34:45Z","receivedAt":"2024-08-11T17:34:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAdd a new reachability algorithm that intends to discover (from a heuristic)\nwhich branch was used as the starting point for a given commit. Add focused\ntests using the 'test-tool reach' command.\n\nRepositories that use pull requests (or merge requests) to advance one or\nmore \"protected\" branches, the history of that reference can be recovered by\nfollowing the first-parent history in most cases. Most are completed using\nno-fast-forward merges, though squash merges are quite common. Less common\nis rebase-and-merge, which still validates this assumption. Finally, the\ncase that breaks this assumption is the fast-forward update (with potential\nrebasing). Even in this case, the previous commit commonly appears in the\nfirst-parent history of the branch.\n\nSimilar assumptions can be made for a topic branch created by a single user\nwith the intention to merge back into another branch. Using 'git commit',\n'git merge', and 'git cherry-pick' from HEAD will default to having the\nfirst-parent commit be the previous commit at HEAD. This history changes\nonly with commands such as 'git reset' or 'git rebase', where the command\nnames also imply that the branch is starting from a new location.\n\nWith this movement of branches in mind, the following heuristic is proposed\nas a way to determine the base branch for a given source branch:\n\n Among a list of candidate base branches, select the candidate that\n minimizes the number of commits in the first-parent history of the source\n that are not in the first-parent history of the candidate.\n\nPrior third-party solutions to this problem have used this optimization\ncriteria, but have relied upon extracting the first-parent history and\ncomparing those lists as tables instead of using commit-graph walks.\n\nGiven current command-line interface options, this optimization criteria is\nnot easy to detect directly. Even using the command\n\n git rev-list --count --first-parent ..\n\ndoes not measure this count, as it uses full reachability from to\ndetermine which commits to remove from the range '..'. This\nmay lead to one asking if we should instead be using the full reachability\nof the candidate and only the first-parent history of the source. This,\nunfortunately, does not work for repositories that use long-lived branches\nand automation to merge across those branches.\n\nIn extremely large repositories, merging into a single trunk may not be\nfeasible. This is usually due to the desired frequency of updates\n(thousands of engineers doing daily work) combined with the time required to\nperform a validation build. These factors combine to create significant\nrisk of semantic merge conflicts, leading to build breaks on the trunk. In\nresponse, repository maintainers can create a single Level Zero (L0) trunk\nand multiple Level One (L1) branches. By partitioning the engineers by\norganization, these engineers may see lower risk of semantic merge conflicts\nas well as be protected against build breaks in other L1 branches. The key\nto making this system work is a semi-automated process of merging L1\nbranches into the L0 trunk and vice-versa. In a large enough organization,\nthese L1 branches may further split into L2 or L3 branches, but the same\nprinciples apply for merging across deeper levels.\n\nIf these automated merges use a typical merge with the second parent\nbringing in the \"new\" content, then each L0 and L1 branch can track its\nprevious positions by following first-parent history, which appear as\nparallel paths (until reaching the first place where the branches diverged).\nIf we also walk to second parents, then the histories overlap significantly\nand cannot be distinguished except for very-recent changes.\n\nFor this reason, the first-parent condition should be symmetrical across the\nbase and source branches.\n\nAnother common case for desiring the result of this optimization method is\nthe use of release branches. When releasing a version of a repository, a\nbranch can be used to track that release. Any updates that are worth fixing\nin that release can be merged to the release branch and shipped with only\nthe necessary fixes without any new features introduced in the trunk branch.\nThe 'maint-2.' branches represent this pattern in the Git project. The\nmicrosoft/git fork uses 'vfs-2..' branches to track the changes that\nare custom to that fork on top of each upstream Git release 2... This\napplication doesn't need the symmetrical first-parent condition, but the use\nof first-parent histories does not change the results for these branches.\n\nTo determine the base branch from a list of candidates, create a new method\nin commit-reach.c that performs a single* commit-graph walk. The core\nconcept is to walk first-parents starting at the candidate bases and the\nsource, tracking the \"best\" base to reach a given commit. Use generation\nnumbers to ensure that a commit is walked at most once and all children have\nbeen explored before visiting it. When reaching a commit that is reachable\nfrom both a base and the source, we will then have a guarantee that this is\nthe closest intersection of first-parent histories. Track the best base to\nreach that commit and return it as a result. In rare cases involving\nmultiple root commits, the first-parent history of the source may never\nintersect any of the candidates and thus a null result is returned.\n\n* There are up to two walks, since we require all commits to have a computed\n generation number in order to avoid incorrect results. This is similar to\n the need for computed generation numbers in ahead_behind() as implemented\n in fd67d149bde (commit-reach: implement ahead_behind() logic, 2023-03-20).\n\nIn order to track the \"best\" base, use a new commit slab that stores an\ninteger. This value defaults to zero upon initialization, so use -1 to\ntrack that the source commit can reach this commit and use 'i + 1' to track\nthat the ith base can reach this commit. When multiple bases can reach a\ncommit, minimize the index to break ties. This allows the caller to specify\nan order to the bases that determines some amount of preference when the\nheuristic does not result in a unique result.\n\nThe trickiest part of the integer slab is what happens when reaching a\ncollision among the histories of the bases and the history of the source.\nThis is noticed when viewing the first parent and seeing that it has a slab\nvalue that differs in sign (negative or positive). In this case, the\ncollision commit is stored in the method variable 'branch_point' and its\nslab value is set to -1. The index of the best base (so far) is stored in\nthe method variable 'best_index'. It is possible that there are multiple\ncommits that have the branch_point as its first parent, leading to multiple\nupdates of best_index. The result is determined when 'branch_point' is\nvisited in the commit walk, giving the guarantee that all commits that could\nreach 'branch_point' were visited.\n\nSeveral interesting cases of collisions and different results are tested in\nthe t6600-test-reach.sh script. Recall that this script also tests the\nalgorithm in three possible states involving the commit-graph file and how\nmany commits are written in the file. This provides some coverage of the\nneed (and lack of need) for the ensure_generations_valid() method.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 118 ++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 17 ++++++\n t/helper/test-reach.c | 2 +\n t/t6600-test-reach.sh | 47 +++++++++++++++++\n 4 files changed, 184 insertions(+)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 8f9b008f876..1b56fb081a6 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1222,3 +1222,121 @@ done:\n \tfree(commits);\n \trepo_clear_commit_marks(r, SEEN);\n }\n+\n+/*\n+ * This slab initializes integers to zero, so use \"-1\" for \"tip is best\" and\n+ * \"i + 1\" for \"bases[i] is best\".\n+ */\n+define_commit_slab(best_branch_base, int);\n+static struct best_branch_base best_branch_base;\n+#define get_best(c) (*best_branch_base_at(&best_branch_base, c))\n+#define set_best(c,v) (*best_branch_base_at(&best_branch_base, c) = v)\n+\n+int get_branch_base_for_tip(struct repository *r,\n+\t\t\t struct commit *tip,\n+\t\t\t struct commit **bases,\n+\t\t\t size_t bases_nr)\n+{\n+\tint best_index = -1;\n+\tstruct commit *branch_point = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tint found_missing_gen = 0;\n+\n+\tif (!bases_nr)\n+\t\treturn -1;\n+\n+\trepo_parse_commit(r, tip);\n+\tif (commit_graph_generation(tip) == GENERATION_NUMBER_INFINITY)\n+\t\tfound_missing_gen = 1;\n+\n+\t/* Check for missing generation numbers. */\n+\tfor (size_t i = 0; i < bases_nr; i++) {\n+\t\tstruct commit *c = bases[i];\n+\t\trepo_parse_commit(r, c);\n+\t\tif (commit_graph_generation(c) == GENERATION_NUMBER_INFINITY)\n+\t\t\tfound_missing_gen = 1;\n+\t}\n+\n+\tif (found_missing_gen) {\n+\t\tstruct commit **commits;\n+\t\tsize_t commits_nr = bases_nr + 1;\n+\n+\t\tCALLOC_ARRAY(commits, commits_nr);\n+\t\tCOPY_ARRAY(commits, bases, bases_nr);\n+\t\tcommits[bases_nr] = tip;\n+\t\tensure_generations_valid(r, commits, commits_nr);\n+\t\tfree(commits);\n+\t}\n+\n+\t/* Initialize queue and slab now that generations are guaranteed. */\n+\tinit_best_branch_base(&best_branch_base);\n+\tset_best(tip, -1);\n+\tprio_queue_put(&queue, tip);\n+\n+\tfor (size_t i = 0; i < bases_nr; i++) {\n+\t\tstruct commit *c = bases[i];\n+\n+\t\t/* Has this already been marked as best by another commit? */\n+\t\tif (get_best(c))\n+\t\t\tcontinue;\n+\n+\t\tset_best(c, i + 1);\n+\t\tprio_queue_put(&queue, c);\n+\t}\n+\n+\twhile (queue.nr) {\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\t\tint best_for_c = get_best(c);\n+\t\tint best_for_p, positive;\n+\t\tstruct commit *parent;\n+\n+\t\t/* Have we reached a known branch point? It's optimal. */\n+\t\tif (c == branch_point)\n+\t\t\tbreak;\n+\n+\t\trepo_parse_commit(r, c);\n+\t\tif (!c->parents)\n+\t\t\tcontinue;\n+\n+\t\tparent = c->parents->item;\n+\t\trepo_parse_commit(r, parent);\n+\t\tbest_for_p = get_best(parent);\n+\n+\t\tif (!best_for_p) {\n+\t\t\t/* 'parent' is new, so pass along best_for_c. */\n+\t\t\tset_best(parent, best_for_c);\n+\t\t\tprio_queue_put(&queue, parent);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (best_for_p > 0 && best_for_c > 0) {\n+\t\t\t/* Collision among bases. Minimize. */\n+\t\t\tif (best_for_c < best_for_p)\n+\t\t\t\tset_best(parent, best_for_c);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/*\n+\t\t * At this point, we have reached a commit that is reachable\n+\t\t * from the tip, either from 'c' or from an earlier commit to\n+\t\t * have 'parent' as its first parent.\n+\t\t *\n+\t\t * Update 'best_index' to match the minimum of all base indices\n+\t\t * to reach 'parent'.\n+\t\t */\n+\n+\t\t/* Exactly one is positive due to initial conditions. */\n+\t\tpositive = (best_for_c < 0) ? best_for_p : best_for_c;\n+\n+\t\tif (best_index < 0 || positive < best_index)\n+\t\t\tbest_index = positive;\n+\n+\t\t/* No matter what, track that the parent is reachable from tip. */\n+\t\tset_best(parent, -1);\n+\t\tbranch_point = parent;\n+\t}\n+\n+\tclear_best_branch_base(&best_branch_base);\n+\tclear_prio_queue(&queue);\n+\treturn best_index > 0 ? best_index - 1 : -1;\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex bf63cc468fd..9a745b7e176 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -139,4 +139,21 @@ void tips_reachable_from_bases(struct repository *r,\n \t\t\t struct commit **tips, size_t tips_nr,\n \t\t\t int mark);\n \n+/*\n+ * Given a 'tip' commit and a list potential 'bases', return the index 'i' that\n+ * minimizes the number of commits in the first-parent history of 'tip' and not\n+ * in the first-parent history of 'bases[i]'.\n+ *\n+ * Among a list of long-lived branches that are updated only by merges (with the\n+ * first parent being the previous position of the branch), this would inform\n+ * which branch was used to create the tip reference.\n+ *\n+ * Returns -1 if no common point is found in first-parent histories, which is\n+ * rare, but possible with multiple root commits.\n+ */\n+int get_branch_base_for_tip(struct repository *r,\n+\t\t\t struct commit *tip,\n+\t\t\t struct commit **bases,\n+\t\t\t size_t bases_nr);\n+\n #endif\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 1e3b431e3e7..8579b607aa5 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -114,6 +114,8 @@ int cmd__reach(int ac, const char **av)\n \t\t repo_in_merge_bases_many(the_repository, A, X_nr, X_array, 0));\n \telse if (!strcmp(av[1], \"is_descendant_of\"))\n \t\tprintf(\"%s(A,X):%d\\n\", av[1], repo_is_descendant_of(r, A, X));\n+\telse if (!strcmp(av[1], \"get_branch_base_for_tip\"))\n+\t\tprintf(\"%s(A,X):%d\\n\", av[1], get_branch_base_for_tip(r, A, X_array, X_nr));\n \telse if (!strcmp(av[1], \"get_merge_bases_many\")) {\n \t\tstruct commit_list *list = NULL;\n \t\tif (repo_get_merge_bases_many(the_repository,\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b330945f497..3069efc8601 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -612,4 +612,51 @@ test_expect_success 'for-each-ref merged:none' '\n \t\t--format=\"%(refname)\" --stdin\n '\n \n+# For get_branch_base_for_tip, we only care about\n+# first-parent history. Here is the test graph with\n+# second parents removed:\n+#\n+# (10,10)\n+# /\n+# (10,9) (9,10)\n+# / /\n+# (10,8) (9,9) (8,10)\n+# / / /\n+# ( continued...)\n+# \\ / / /\n+# (3,1) (2,2) (1,3)\n+# \\ / /\n+# (2,1) (1,2)\n+# \\ /\n+# (1,1)\n+#\n+# In short, for a commit (i,j), the first-parent history\n+# walks all commits (i, k) with k from j to 1, then the\n+# commits (l, 1) with l from i to 1.\n+\n+test_expect_success 'get_branch_base_for_tip: none reach' '\n+\t# (2,3) branched from the first tip (i,4) in X with i > 2\n+\tcat >input <<-\\EOF &&\n+\t\tA:commit-2-3\n+\t\tX:commit-1-2\n+\t\tX:commit-1-4\n+\t\tX:commit-4-4\n+\t\tX:commit-8-4\n+\t\tX:commit-10-4\n+\tEOF\n+\techo \"get_branch_base_for_tip(A,X):2\" >expect &&\n+\ttest_all_modes get_branch_base_for_tip\n+'\n+\n+test_expect_success 'get_branch_base_for_tip: all reach tip' '\n+\t# (2,3) branched from the first tip (i,4) in X with i > 2\n+\tcat >input <<-\\EOF &&\n+\t\tA:commit-4-1\n+\t\tX:commit-4-2\n+\t\tX:commit-5-1\n+\tEOF\n+\techo \"get_branch_base_for_tip(A,X):0\" >expect &&\n+\ttest_all_modes get_branch_base_for_tip\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"500605","messageId":"757c20090dbcca7b87c30138bd383eb55656ba90.1723397687.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v2.git.1723397687.gitgitgadget@gmail.com","subject":"[PATCH v2 3/3] p1500: add is-base performance tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-11T17:34:47Z","receivedAt":"2024-08-11T17:34:53Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous two changes introduced a commit walking heuristic for finding\nthe most likely base branch for a given source. This algorithm walks\nfirst-parent histories until reaching a collision.\n\nThis walk _should_ be very fast. Exceptions include cases where a\ncommit-graph file does not exist, leading to a full walk of all reachable\ncommits to compute generation numbers, or a case where no collision in the\nfirst-parent history exists, leading to a walk of all first-parent history\nto the root commits.\n\nThe p1500 test script guarantees a complete commit-graph file during its\nsetup, so we will not test that scenario. Do create a new root commit in an\neffort to test the scenario of parallel first-parent histories.\n\nEven with the extra root commit, these tests take no longer than 0.02\nseconds on my machine for the Git repository. However, the results are\nslightly more interesting in a copy of the Linux kernel repository:\n\nTest\n---------------------------------------------------------------\n1500.2: ahead-behind counts: git for-each-ref 0.12\n1500.3: ahead-behind counts: git branch 0.12\n1500.4: ahead-behind counts: git tag 0.12\n1500.5: contains: git for-each-ref --merged 0.04\n1500.6: contains: git branch --merged 0.04\n1500.7: contains: git tag --merged 0.04\n1500.8: is-base check: test-tool reach (refs) 0.03\n1500.9: is-base check: test-tool reach (tags) 0.03\n1500.10: is-base check: git for-each-ref 0.03\n1500.11: is-base check: git for-each-ref (disjoint-base) 0.07\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p1500-graph-walks.sh | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\nindex e14e7620cce..5b23ce5db93 100755\n--- a/t/perf/p1500-graph-walks.sh\n+++ b/t/perf/p1500-graph-walks.sh\n@@ -20,6 +20,21 @@ test_expect_success 'setup' '\n \t\techo tag-$ref ||\n \t\treturn 1\n \tdone >tags &&\n+\n+\techo \"A:HEAD\" >test-tool-refs &&\n+\tfor line in $(cat refs)\n+\tdo\n+\t\techo \"X:$line\" >>test-tool-refs || return 1\n+\tdone &&\n+\techo \"A:HEAD\" >test-tool-tags &&\n+\tfor line in $(cat tags)\n+\tdo\n+\t\techo \"X:$line\" >>test-tool-tags || return 1\n+\tdone &&\n+\n+\tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n+\tgit update-ref refs/heads/disjoint-base $commit &&\n+\n \tgit commit-graph write --reachable\n '\n \n@@ -47,4 +62,20 @@ test_perf 'contains: git tag --merged' '\n \txargs git tag --merged=HEAD writes:\n\n> From: Derrick Stolee \n>\n> Add a new reachability algorithm that intends to discover (from a heuristic)\n> which branch was used as the starting point for a given commit. Add focused\n> tests using the 'test-tool reach' command.\n>\n> Repositories that use pull requests (or merge requests) to advance one or\n> more \"protected\" branches, the history of that reference can be recovered by\n> following the first-parent history in most cases.\n\nI cannot quite parse it, but perhaps \"Repositories that\" -> \"In\nrepositories that\"?\n\n> Most are completed using\n> no-fast-forward merges, though squash merges are quite common. Less common\n> is rebase-and-merge, which still validates this assumption. Finally, the\n> case that breaks this assumption is the fast-forward update (with potential\n> rebasing). Even in this case, the previous commit commonly appears in the\n> first-parent history of the branch.\n\n> Given current command-line interface options, this optimization criteria is\n> not easy to detect directly. Even using the command\n>\n> git rev-list --count --first-parent ..\n>\n> does not measure this count, as it uses full reachability from to\n> determine which commits to remove from the range '..'.\n\nMakes me wonder if \"--ancestry-path\" would help.\n\n> The trickiest part of the integer slab is what happens when reaching a\n> collision among the histories of the bases and the history of the source.\n> This is noticed when viewing the first parent and seeing that it has a slab\n> value that differs in sign (negative or positive). In this case, the\n> collision commit is stored in the method variable 'branch_point' and its\n> slab value is set to -1. The index of the best base (so far) is stored in\n> the method variable 'best_index'. It is possible that there are multiple\n> commits that have the branch_point as its first parent, leading to multiple\n> updates of best_index. The result is determined when 'branch_point' is\n> visited in the commit walk, giving the guarantee that all commits that could\n> reach 'branch_point' were visited.\n\nOK.\n\n> +/*\n> + * This slab initializes integers to zero, so use \"-1\" for \"tip is best\" and\n> + * \"i + 1\" for \"bases[i] is best\".\n> + */\n> +define_commit_slab(best_branch_base, int);\n> +static struct best_branch_base best_branch_base;\n> +#define get_best(c) (*best_branch_base_at(&best_branch_base, c))\n> +#define set_best(c,v) (*best_branch_base_at(&best_branch_base, c) = v)\n\nMicronit. Prepare for macro arguments to be expressions, even if\ncurrent callers don't use anything more complex, i.e., something\nlike\n\n\t(*best_branch_base_at(&best_branch_base, (c)))\n\t(*best_branch_base_at(&best_branch_base, (c)) = (v))\n\n> +\tif (found_missing_gen) {\n> +\t\tstruct commit **commits;\n> +\t\tsize_t commits_nr = bases_nr + 1;\n> +\n> +\t\tCALLOC_ARRAY(commits, commits_nr);\n> +\t\tCOPY_ARRAY(commits, bases, bases_nr);\n> +\t\tcommits[bases_nr] = tip;\n> +\t\tensure_generations_valid(r, commits, commits_nr);\n> +\t\tfree(commits);\n> +\t}\n\nIt would have been very unfortunate if this copying were done only\nbecause commits and tip are not in the same array, but the called\nfunction mutates the given array of commits so we cannot avoid\npassing a copy anyway. Given these constraints, this is the\ncleanest implementation, probably.\n\n> +\n> +\t/* Initialize queue and slab now that generations are guaranteed. */\n> +\tinit_best_branch_base(&best_branch_base);\n> +\tset_best(tip, -1);\n> +\tprio_queue_put(&queue, tip);\n> +\n> +\tfor (size_t i = 0; i < bases_nr; i++) {\n> +\t\tstruct commit *c = bases[i];\n> +\n> +\t\t/* Has this already been marked as best by another commit? */\n> +\t\tif (get_best(c))\n> +\t\t\tcontinue;\n\nOh, so this defines the tie-breaking behaviour, but simply removing\nit is a wrong solution if we wanted our tie-breaking to work as\n\"last one wins\", as we still do not want to put it in the queue, so\nthis \"if best is already found, skip the rest\" is serving dual\npurposes. Good.\n\n> +\t\tset_best(c, i + 1);\n> +\t\tprio_queue_put(&queue, c);\n> +\t}\n> +\n> +\twhile (queue.nr) {\n> +\t\tstruct commit *c = prio_queue_get(&queue);\n> +\t\tint best_for_c = get_best(c);\n> +\t\tint best_for_p, positive;\n> +\t\tstruct commit *parent;\n> +\n> +\t\t/* Have we reached a known branch point? It's optimal. */\n> +\t\tif (c == branch_point)\n> +\t\t\tbreak;\n> +\n> +\t\trepo_parse_commit(r, c);\n> +\t\tif (!c->parents)\n> +\t\t\tcontinue;\n> +\n> +\t\tparent = c->parents->item;\n> +\t\trepo_parse_commit(r, parent);\n> +\t\tbest_for_p = get_best(parent);\n> +\n> +\t\tif (!best_for_p) {\n> +\t\t\t/* 'parent' is new, so pass along best_for_c. */\n> +\t\t\tset_best(parent, best_for_c);\n> +\t\t\tprio_queue_put(&queue, parent);\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\tif (best_for_p > 0 && best_for_c > 0) {\n> +\t\t\t/* Collision among bases. Minimize. */\n> +\t\t\tif (best_for_c < best_for_p)\n> +\t\t\t\tset_best(parent, best_for_c);\n> +\t\t\tcontinue;\n> +\t\t}\n> +\n> +\t\t/*\n> +\t\t * At this point, we have reached a commit that is reachable\n> +\t\t * from the tip, either from 'c' or from an earlier commit to\n> +\t\t * have 'parent' as its first parent.\n> +\t\t *\n> +\t\t * Update 'best_index' to match the minimum of all base indices\n> +\t\t * to reach 'parent'.\n> +\t\t */\n> +\n> +\t\t/* Exactly one is positive due to initial conditions. */\n> +\t\tpositive = (best_for_c < 0) ? best_for_p : best_for_c;\n> +\n> +\t\tif (best_index < 0 || positive < best_index)\n> +\t\t\tbest_index = positive;\n> +\n> +\t\t/* No matter what, track that the parent is reachable from tip. */\n> +\t\tset_best(parent, -1);\n> +\t\tbranch_point = parent;\n> +\t}\n> +\n> +\tclear_best_branch_base(&best_branch_base);\n> +\tclear_prio_queue(&queue);\n\nOK. We get rid of the slab and prio-queue once we are done.\nNice.\n\nThanks.\n\n\n"},{"id":"500661","messageId":"xmqqsev9zc2j.fsf@gitster.g","threadId":"61884","inReplyTo":"13341e7e51241e077a85ea83eb76d4e48d04be7b.1723397687.git.gitgitgadget@gmail.com","subject":"Re: [PATCH v2 2/3] for-each-ref: add 'is-base' token","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2024-08-12T21:05:40Z","receivedAt":"2024-08-12T21:05:47Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"\"Derrick Stolee via GitGitGadget\" writes:\n\n> +is-base:::\n> +\tIn at most one row, `()` will appear to indicate the ref\n> +\tthat is most likely the ref used as a starting point for the branch\n> +\tthat produced ``. This choice is made using a heuristic:\n> +\tchoose the ref that minimizes the number of commits in the\n> +\tfirst-parent history of `` and not in the first-parent\n> +\thistory of the ref.\n\nVery nicely described. \n\nGiving the end-user oriented \"purpose/meaning\" first makes it easier\nto understand for readers when they want to use it, and giving the\nheuristics to compute the result (and the example) next allows them\nto verify that the feature matches what they are looking for.\n\n\n> @@ -2475,6 +2495,16 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err)\n> \t\t\t\tv->s = xstrdup(\"\");\n> \t\t\t}\n> \t\t\tcontinue;\n> +\t\t} else if (atom_type == ATOM_ISBASE) {\n> +\t\t\tif (ref->is_base && ref->is_base[is_base_atoms]) {\n> +\t\t\t\tv->s = xstrfmt(\"(%s)\", ref->is_base[is_base_atoms]);\n> +\t\t\t\tfree(ref->is_base[is_base_atoms]);\n> +\t\t\t} else {\n> +\t\t\t\t/* Not a commit. */\n\nThis is unexpected. I thought that most of the branches except at\nmost one that gets annotated with \"Yeah, this is forked from branch\nB\" would take the \"else\" side. They are still commits, no?\n\n> +\t\t\t\tv->s = xstrdup(\"\");\n> +\t\t\t}\n> +\t\t\tis_base_atoms++;\n> +\t\t\tcontinue;\n> \t\t} else\n> \t\t\tcontinue;\n> \n> @@ -2876,6 +2906,7 @@ static void free_array_item(struct ref_array_item *item)\n> \t\tfree(item->value);\n> \t}\n> \tfree(item->counts);\n> +\tfree(item->is_base);\n> \tfree(item);\n> }\n> \n> @@ -3040,6 +3071,49 @@ void filter_ahead_behind(struct repository *r,\n> \tfree(commits);\n> }\n> \n> +void filter_is_base(struct repository *r,\n> +\t\t struct ref_format *format,\n> +\t\t struct ref_array *array)\n> +{\n> +\tstruct commit **bases;\n> +\tsize_t bases_nr = 0;\n> +\tstruct ref_array_item **back_index;\n> +\n> +\tif (!format->is_base_tips.nr || !array->nr)\n> +\t\treturn;\n> +\n> +\tCALLOC_ARRAY(back_index, array->nr);\n> +\tCALLOC_ARRAY(bases, array->nr);\n> +\n> +\tfor (size_t i = 0; i < array->nr; i++) {\n> +\t\tconst char *name = array->items[i]->refname;\n> +\t\tstruct commit *c = lookup_commit_reference_by_name(name);\n> +\n> +\t\tCALLOC_ARRAY(array->items[i]->is_base, format->is_base_tips.nr);\n> +\n> +\t\tif (!c)\n> +\t\t\tcontinue;\n\nHmph, wouldn't we want to leave array->items[i]->is_base NULL if\n\"name\" looked up to \"c\" happens to be non-commit (i.e. NULL)?\n\n> +\t\tback_index[bases_nr] = array->items[i];\n> +\t\tbases[bases_nr] = c;\n> +\t\tbases_nr++;\n> +\t}\n\n\nThanks.\n"},{"id":"500781","messageId":"bc7fac52-a055-46e5-83de-218fbcbdd605@gmail.com","threadId":"61884","inReplyTo":"xmqqv8051o22.fsf@gitster.g","subject":"Re: [PATCH v2 1/3] commit-reach: add get_branch_base_for_tip","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-08-13T13:39:10Z","receivedAt":"2024-08-13T13:39:13Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/12/24 4:30 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n>> Repositories that use pull requests (or merge requests) to advance one or\n>> more \"protected\" branches, the history of that reference can be recovered by\n>> following the first-parent history in most cases.\n> \n> I cannot quite parse it, but perhaps \"Repositories that\" -> \"In\n> repositories that\"?\n\nThat is an improvement, thanks.\n\n>> Most are completed using\n>> no-fast-forward merges, though squash merges are quite common. Less common\n>> is rebase-and-merge, which still validates this assumption. Finally, the\n>> case that breaks this assumption is the fast-forward update (with potential\n>> rebasing). Even in this case, the previous commit commonly appears in the\n>> first-parent history of the branch.\n> \n>> Given current command-line interface options, this optimization criteria is\n>> not easy to detect directly. Even using the command\n>>\n>> git rev-list --count --first-parent ..\n>>\n>> does not measure this count, as it uses full reachability from to\n>> determine which commits to remove from the range '..'.\n> \n> Makes me wonder if \"--ancestry-path\" would help.\n\nOne difficulty here is that we don't know the \"first-parent merge base\"\nto supply to the --ancestry-path argument. You could first find this by\nrunning\n\n git rev-list --first-parent --boundary --reverse A...B\n\nand pulling out the first boundary commit 'C'. Then, that could be used in\n\n git rev-list --first-parent --count --ancestry-path=C B\n\nI believe that this two-process-per-ref approach would provide an\nexisting way to compute these results.\n\n>> The trickiest part of the integer slab is what happens when reaching a\n>> collision among the histories of the bases and the history of the source.\n>> This is noticed when viewing the first parent and seeing that it has a slab\n>> value that differs in sign (negative or positive). In this case, the\n>> collision commit is stored in the method variable 'branch_point' and its\n>> slab value is set to -1. The index of the best base (so far) is stored in\n>> the method variable 'best_index'. It is possible that there are multiple\n>> commits that have the branch_point as its first parent, leading to multiple\n>> updates of best_index. The result is determined when 'branch_point' is\n>> visited in the commit walk, giving the guarantee that all commits that could\n>> reach 'branch_point' were visited.\n> \n> OK.\n> \n>> +/*\n>> + * This slab initializes integers to zero, so use \"-1\" for \"tip is best\" and\n>> + * \"i + 1\" for \"bases[i] is best\".\n>> + */\n>> +define_commit_slab(best_branch_base, int);\n>> +static struct best_branch_base best_branch_base;\n>> +#define get_best(c) (*best_branch_base_at(&best_branch_base, c))\n>> +#define set_best(c,v) (*best_branch_base_at(&best_branch_base, c) = v)\n> \n> Micronit. Prepare for macro arguments to be expressions, even if\n> current callers don't use anything more complex, i.e., something\n> like\n> \n> \t(*best_branch_base_at(&best_branch_base, (c)))\n> \t(*best_branch_base_at(&best_branch_base, (c)) = (v))\n\nThanks. I should have caught this myself.\n\n>> +\n>> +\t/* Initialize queue and slab now that generations are guaranteed. */\n>> +\tinit_best_branch_base(&best_branch_base);\n>> +\tset_best(tip, -1);\n>> +\tprio_queue_put(&queue, tip);\n>> +\n>> +\tfor (size_t i = 0; i < bases_nr; i++) {\n>> +\t\tstruct commit *c = bases[i];\n>> +\n>> +\t\t/* Has this already been marked as best by another commit? */\n>> +\t\tif (get_best(c))\n>> +\t\t\tcontinue;\n> \n> Oh, so this defines the tie-breaking behaviour, but simply removing\n> it is a wrong solution if we wanted our tie-breaking to work as\n> \"last one wins\", as we still do not want to put it in the queue, so\n> this \"if best is already found, skip the rest\" is serving dual\n> purposes. Good.\n\nWhen trying to make a test case for the for-each-ref behavior around\nnon-commits, I noticed a bug here. If get_best(c) is -1, then 'c' is\nequal to the base and should be selected. I will update the logic here\nand add an appropriate test in this patch.\n\nThanks,\n-Stolee\n\n"},{"id":"500783","messageId":"8b1b05fa-829b-4f3d-9c25-cbb478176531@gmail.com","threadId":"61884","inReplyTo":"xmqqsev9zc2j.fsf@gitster.g","subject":"Re: [PATCH v2 2/3] for-each-ref: add 'is-base' token","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-08-13T13:44:52Z","receivedAt":"2024-08-13T13:44:54Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/12/24 5:05 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n\n>> +\t\t} else if (atom_type == ATOM_ISBASE) {\n>> +\t\t\tif (ref->is_base && ref->is_base[is_base_atoms]) {\n>> +\t\t\t\tv->s = xstrfmt(\"(%s)\", ref->is_base[is_base_atoms]);\n>> +\t\t\t\tfree(ref->is_base[is_base_atoms]);\n>> +\t\t\t} else {\n>> +\t\t\t\t/* Not a commit. */\n> \n> This is unexpected. I thought that most of the branches except at\n> most one that gets annotated with \"Yeah, this is forked from branch\n> B\" would take the \"else\" side. They are still commits, no?\n\nYou are correct. This is leftover from copy-pasting the ahead-behind section.\nWill remove.\n\n>> +\tfor (size_t i = 0; i < array->nr; i++) {\n>> +\t\tconst char *name = array->items[i]->refname;\n>> +\t\tstruct commit *c = lookup_commit_reference_by_name(name);\n>> +\n>> +\t\tCALLOC_ARRAY(array->items[i]->is_base, format->is_base_tips.nr);\n>> +\n>> +\t\tif (!c)\n>> +\t\t\tcontinue;\n> \n> Hmph, wouldn't we want to leave array->items[i]->is_base NULL if\n> \"name\" looked up to \"c\" happens to be non-commit (i.e. NULL)?\n\nYour comment initially made me second-guess the logic here, but...\n\n>> +\t\tback_index[bases_nr] = array->items[i];\n>> +\t\tbases[bases_nr] = c;\n>> +\t\tbases_nr++;\n\nThis array of \"back_index\" is intended to allow the array being passed to\nget_branch_base_for_tip() to have no gaps with NULL commits. The indices\nare then translated back to the original array items when scanning the\nresults.\n\nThis matches the behavior of the ahead-behind code, giving an existing\nbehavior. The alternative would be to allow get_branch_base_for_tip() to\nbe sensitive to NULL commits in the 'bases' array. But since we need to\ncreate an array of commit pointers (different from the array of ref\nitems that we start with) this is likely the simplest approach.\n\nYou did inspire me to double-check that this code works in the presence\nof non-commit refs, so I'll update some things and send a v3 with a new\ntest. It will also include some things to make error messages quieter\nfor that case.\n\nThanks,\n-Stolee\n\n"},{"id":"500869","messageId":"pull.1768.v3.git.1723631490.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v2.git.1723397687.gitgitgadget@gmail.com","subject":"[PATCH v3 0/4] git for-each-ref: is-base atom and base branches","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-14T10:31:26Z","receivedAt":"2024-08-14T10:31:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"This change introduces a new 'git for-each-ref' atom, 'is-base', in a very\nsimilar way to the 'ahead-behind' atom. As detailed carefully in the first\nchange, this is motivated by the need to detect the concept of a \"base\nbranch\" in a repository with multiple long-lived branches.\n\nThis change is motivated by a third-party tool created to make this\ndetection with the same optimization mechanism, but using a much slower\ntechnique due to the limitations of the Git CLI not presenting this\ninformation. The existing algorithm involves using git rev-list\n--first-parent - in batches for the collection of considered references,\ncomparing those lists, and increasing as needed until finding a\ncollision. This new use of 'git for-each-ref' will allow determining this\nmechanism within a single process and walking a minimal number of commits.\n\nThere are benefits to users both on client-side and server-side. In an\ninternal monorepo, this base branch detection algorithm is used to determine\na long-lived branch based on the HEAD commit, mapping to a group within the\norganizational structure of the repository, which determines a set of\nprojects that the user will likely need to build; this leads to\nautomatically selecting an initial sparse-checkout definition based on the\nbuild dependencies required. An upcoming feature in Azure Repos will use\nthis algorithm to automatically create a pull request against the correct\ntarget branch, reducing user pain from needing to select a different branch\nafter a large commit diff is rendered against the default branch. This atom\nunlocks that ability for Git hosting services that use Git in their backend.\n\nThanks, -Stolee\n\n\nUpdates in v2\n=============\n\n * I had forgotten to include a documentation change in v1. My attempt to\n create a succinct doc change in a follow-up hunk continued to be\n confusing. This version includes a more expanded version of the\n documentation blurb for the is-base token.\n\n\nUpdates in v3\n=============\n\n * Corrected some grammar in a commit message.\n * Fixed (and tested for) a bug where the source branch is equal to a\n candidate ref.\n * Added a test in t6500-for-each-ref.sh to cover some non-commit refs and\n some broken objects.\n * Motivated by the test in t6500, add a new patch that adds a ..._gently()\n method to reduce error noise for non-commit refs.\n\nDerrick Stolee (4):\n commit-reach: add get_branch_base_for_tip\n commit: add gentle reference lookup method\n for-each-ref: add 'is-base' token\n p1500: add is-base performance tests\n\n Documentation/git-for-each-ref.txt | 42 ++++++++++\n commit-reach.c | 126 +++++++++++++++++++++++++++++\n commit-reach.h | 17 ++++\n commit.c | 8 +-\n commit.h | 2 +\n ref-filter.c | 77 +++++++++++++++++-\n ref-filter.h | 15 ++++\n t/helper/test-reach.c | 2 +\n t/perf/p1500-graph-walks.sh | 31 +++++++\n t/t6300-for-each-ref.sh | 9 +++\n t/t6600-test-reach.sh | 121 +++++++++++++++++++++++++++\n 11 files changed, 448 insertions(+), 2 deletions(-)\n\n\nbase-commit: bea9ecd24b0c3bf06cab4a851694fe09e7e51408\nPublished-As: https://github.com/gitgitgadget/git/releases/tag/pr-1768%2Fderrickstolee%2Ftarget-ref-v3\nFetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-1768/derrickstolee/target-ref-v3\nPull-Request: https://github.com/gitgitgadget/git/pull/1768\n\nRange-diff vs v2:\n\n 1: 580026f910d ! 1: f93d642c8d9 commit-reach: add get_branch_base_for_tip\n @@ Commit message\n which branch was used as the starting point for a given commit. Add focused\n tests using the 'test-tool reach' command.\n \n - Repositories that use pull requests (or merge requests) to advance one or\n + In repositories that use pull requests (or merge requests) to advance one or\n more \"protected\" branches, the history of that reference can be recovered by\n following the first-parent history in most cases. Most are completed using\n no-fast-forward merges, though squash merges are quite common. Less common\n @@ commit-reach.c: done:\n + */\n +define_commit_slab(best_branch_base, int);\n +static struct best_branch_base best_branch_base;\n -+#define get_best(c) (*best_branch_base_at(&best_branch_base, c))\n -+#define set_best(c,v) (*best_branch_base_at(&best_branch_base, c) = v)\n ++#define get_best(c) (*best_branch_base_at(&best_branch_base, (c)))\n ++#define set_best(c,v) (*best_branch_base_at(&best_branch_base, (c)) = (v))\n +\n +int get_branch_base_for_tip(struct repository *r,\n +\t\t\t struct commit *tip,\n @@ commit-reach.c: done:\n +\n +\tfor (size_t i = 0; i < bases_nr; i++) {\n +\t\tstruct commit *c = bases[i];\n ++\t\tint best = get_best(c);\n +\n +\t\t/* Has this already been marked as best by another commit? */\n -+\t\tif (get_best(c))\n ++\t\tif (best) {\n ++\t\t\tif (best == -1) {\n ++\t\t\t\t/* We agree at this position. Stop now. */\n ++\t\t\t\tbest_index = i + 1;\n ++\t\t\t\tgoto cleanup;\n ++\t\t\t}\n +\t\t\tcontinue;\n ++\t\t}\n +\n +\t\tset_best(c, i + 1);\n +\t\tprio_queue_put(&queue, c);\n @@ commit-reach.c: done:\n +\t\tbranch_point = parent;\n +\t}\n +\n ++cleanup:\n +\tclear_best_branch_base(&best_branch_base);\n +\tclear_prio_queue(&queue);\n +\treturn best_index > 0 ? best_index - 1 : -1;\n @@ t/t6600-test-reach.sh: test_expect_success 'for-each-ref merged:none' '\n +\ttest_all_modes get_branch_base_for_tip\n +'\n +\n ++test_expect_success 'get_branch_base_for_tip: equal to tip' '\n ++\t# (2,3) branched from the first tip (i,4) in X with i > 2\n ++\tcat >input <<-\\EOF &&\n ++\t\tA:commit-8-4\n ++\t\tX:commit-1-2\n ++\t\tX:commit-1-4\n ++\t\tX:commit-4-4\n ++\t\tX:commit-8-4\n ++\t\tX:commit-10-4\n ++\tEOF\n ++\techo \"get_branch_base_for_tip(A,X):3\" >expect &&\n ++\ttest_all_modes get_branch_base_for_tip\n ++'\n ++\n +test_expect_success 'get_branch_base_for_tip: all reach tip' '\n +\t# (2,3) branched from the first tip (i,4) in X with i > 2\n +\tcat >input <<-\\EOF &&\n -: ----------- > 2: 5240c2a7b32 commit: add gentle reference lookup method\n 2: 13341e7e512 ! 3: df05cee6003 for-each-ref: add 'is-base' token\n @@ ref-filter.c: static int populate_value(struct ref_array_item *ref, struct strbu\n +\t\t\t\tv->s = xstrfmt(\"(%s)\", ref->is_base[is_base_atoms]);\n +\t\t\t\tfree(ref->is_base[is_base_atoms]);\n +\t\t\t} else {\n -+\t\t\t\t/* Not a commit. */\n +\t\t\t\tv->s = xstrdup(\"\");\n +\t\t\t}\n +\t\t\tis_base_atoms++;\n @@ ref-filter.c: void filter_ahead_behind(struct repository *r,\n +\n +\tfor (size_t i = 0; i < array->nr; i++) {\n +\t\tconst char *name = array->items[i]->refname;\n -+\t\tstruct commit *c = lookup_commit_reference_by_name(name);\n ++\t\tstruct commit *c = lookup_commit_reference_by_name_gently(name, 1);\n +\n +\t\tCALLOC_ARRAY(array->items[i]->is_base, format->is_base_tips.nr);\n +\n @@ ref-filter.h: void filter_ahead_behind(struct repository *r,\n void ref_filter_clear(struct ref_filter *filter);\n \n \n + ## t/t6300-for-each-ref.sh ##\n +@@ t/t6300-for-each-ref.sh: test_expect_success 'git for-each-ref with nested tags' '\n + \ttest_cmp expect actual\n + '\n + \n ++test_expect_success 'is-base atom with non-commits' '\n ++\tgit for-each-ref --format=\"%(is-base:HEAD) %(refname)\" >out 2>err &&\n ++\tgrep \"(HEAD) refs/heads/main\" out &&\n ++\n ++\ttest_line_count = 2 err &&\n ++\tgrep \"error: object .* is a commit, not a blob\" err &&\n ++\tgrep \"error: bad tag pointer to\" err\n ++'\n ++\n + GRADE_FORMAT=\"%(signature:grade)%0a%(signature:key)%0a%(signature:signer)%0a%(signature:fingerprint)%0a%(signature:primarykeyfingerprint)\"\n + TRUSTLEVEL_FORMAT=\"%(signature:trustlevel)%0a%(signature:key)%0a%(signature:signer)%0a%(signature:fingerprint)%0a%(signature:primarykeyfingerprint)\"\n + \n +\n ## t/t6600-test-reach.sh ##\n @@ t/t6600-test-reach.sh: test_expect_success 'get_branch_base_for_tip: all reach tip' '\n \ttest_all_modes get_branch_base_for_tip\n @@ t/t6600-test-reach.sh: test_expect_success 'get_branch_base_for_tip: all reach t\n +\t\t--format=\"%(refname):%(is-base:commit-4-1)\" --stdin\n +'\n +\n ++test_expect_success 'for-each-ref is-base: equal to tip' '\n ++\tcat >input <<-\\EOF &&\n ++\trefs/heads/commit-4-2\n ++\trefs/heads/commit-5-1\n ++\tEOF\n ++\tcat >expect <<-\\EOF &&\n ++\trefs/heads/commit-4-2:(commit-4-2)\n ++\trefs/heads/commit-5-1:\n ++\tEOF\n ++\trun_all_modes git for-each-ref \\\n ++\t\t--format=\"%(refname):%(is-base:commit-4-2)\" --stdin\n ++'\n ++\n +test_expect_success 'for-each-ref is-base:multiple' '\n +\tcat >input <<-\\EOF &&\n +\trefs/heads/commit-1-1\n 3: 757c20090db = 4: cce9921bbd8 p1500: add is-base performance tests\n\n-- \ngitgitgadget\n"},{"id":"500870","messageId":"f93d642c8d93e3f394b04d7cb655863268a60ee8.1723631490.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v3.git.1723631490.gitgitgadget@gmail.com","subject":"[PATCH v3 1/4] commit-reach: add get_branch_base_for_tip","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-14T10:31:27Z","receivedAt":"2024-08-14T10:31:35Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nAdd a new reachability algorithm that intends to discover (from a heuristic)\nwhich branch was used as the starting point for a given commit. Add focused\ntests using the 'test-tool reach' command.\n\nIn repositories that use pull requests (or merge requests) to advance one or\nmore \"protected\" branches, the history of that reference can be recovered by\nfollowing the first-parent history in most cases. Most are completed using\nno-fast-forward merges, though squash merges are quite common. Less common\nis rebase-and-merge, which still validates this assumption. Finally, the\ncase that breaks this assumption is the fast-forward update (with potential\nrebasing). Even in this case, the previous commit commonly appears in the\nfirst-parent history of the branch.\n\nSimilar assumptions can be made for a topic branch created by a single user\nwith the intention to merge back into another branch. Using 'git commit',\n'git merge', and 'git cherry-pick' from HEAD will default to having the\nfirst-parent commit be the previous commit at HEAD. This history changes\nonly with commands such as 'git reset' or 'git rebase', where the command\nnames also imply that the branch is starting from a new location.\n\nWith this movement of branches in mind, the following heuristic is proposed\nas a way to determine the base branch for a given source branch:\n\n Among a list of candidate base branches, select the candidate that\n minimizes the number of commits in the first-parent history of the source\n that are not in the first-parent history of the candidate.\n\nPrior third-party solutions to this problem have used this optimization\ncriteria, but have relied upon extracting the first-parent history and\ncomparing those lists as tables instead of using commit-graph walks.\n\nGiven current command-line interface options, this optimization criteria is\nnot easy to detect directly. Even using the command\n\n git rev-list --count --first-parent ..\n\ndoes not measure this count, as it uses full reachability from to\ndetermine which commits to remove from the range '..'. This\nmay lead to one asking if we should instead be using the full reachability\nof the candidate and only the first-parent history of the source. This,\nunfortunately, does not work for repositories that use long-lived branches\nand automation to merge across those branches.\n\nIn extremely large repositories, merging into a single trunk may not be\nfeasible. This is usually due to the desired frequency of updates\n(thousands of engineers doing daily work) combined with the time required to\nperform a validation build. These factors combine to create significant\nrisk of semantic merge conflicts, leading to build breaks on the trunk. In\nresponse, repository maintainers can create a single Level Zero (L0) trunk\nand multiple Level One (L1) branches. By partitioning the engineers by\norganization, these engineers may see lower risk of semantic merge conflicts\nas well as be protected against build breaks in other L1 branches. The key\nto making this system work is a semi-automated process of merging L1\nbranches into the L0 trunk and vice-versa. In a large enough organization,\nthese L1 branches may further split into L2 or L3 branches, but the same\nprinciples apply for merging across deeper levels.\n\nIf these automated merges use a typical merge with the second parent\nbringing in the \"new\" content, then each L0 and L1 branch can track its\nprevious positions by following first-parent history, which appear as\nparallel paths (until reaching the first place where the branches diverged).\nIf we also walk to second parents, then the histories overlap significantly\nand cannot be distinguished except for very-recent changes.\n\nFor this reason, the first-parent condition should be symmetrical across the\nbase and source branches.\n\nAnother common case for desiring the result of this optimization method is\nthe use of release branches. When releasing a version of a repository, a\nbranch can be used to track that release. Any updates that are worth fixing\nin that release can be merged to the release branch and shipped with only\nthe necessary fixes without any new features introduced in the trunk branch.\nThe 'maint-2.' branches represent this pattern in the Git project. The\nmicrosoft/git fork uses 'vfs-2..' branches to track the changes that\nare custom to that fork on top of each upstream Git release 2... This\napplication doesn't need the symmetrical first-parent condition, but the use\nof first-parent histories does not change the results for these branches.\n\nTo determine the base branch from a list of candidates, create a new method\nin commit-reach.c that performs a single* commit-graph walk. The core\nconcept is to walk first-parents starting at the candidate bases and the\nsource, tracking the \"best\" base to reach a given commit. Use generation\nnumbers to ensure that a commit is walked at most once and all children have\nbeen explored before visiting it. When reaching a commit that is reachable\nfrom both a base and the source, we will then have a guarantee that this is\nthe closest intersection of first-parent histories. Track the best base to\nreach that commit and return it as a result. In rare cases involving\nmultiple root commits, the first-parent history of the source may never\nintersect any of the candidates and thus a null result is returned.\n\n* There are up to two walks, since we require all commits to have a computed\n generation number in order to avoid incorrect results. This is similar to\n the need for computed generation numbers in ahead_behind() as implemented\n in fd67d149bde (commit-reach: implement ahead_behind() logic, 2023-03-20).\n\nIn order to track the \"best\" base, use a new commit slab that stores an\ninteger. This value defaults to zero upon initialization, so use -1 to\ntrack that the source commit can reach this commit and use 'i + 1' to track\nthat the ith base can reach this commit. When multiple bases can reach a\ncommit, minimize the index to break ties. This allows the caller to specify\nan order to the bases that determines some amount of preference when the\nheuristic does not result in a unique result.\n\nThe trickiest part of the integer slab is what happens when reaching a\ncollision among the histories of the bases and the history of the source.\nThis is noticed when viewing the first parent and seeing that it has a slab\nvalue that differs in sign (negative or positive). In this case, the\ncollision commit is stored in the method variable 'branch_point' and its\nslab value is set to -1. The index of the best base (so far) is stored in\nthe method variable 'best_index'. It is possible that there are multiple\ncommits that have the branch_point as its first parent, leading to multiple\nupdates of best_index. The result is determined when 'branch_point' is\nvisited in the commit walk, giving the guarantee that all commits that could\nreach 'branch_point' were visited.\n\nSeveral interesting cases of collisions and different results are tested in\nthe t6600-test-reach.sh script. Recall that this script also tests the\nalgorithm in three possible states involving the commit-graph file and how\nmany commits are written in the file. This provides some coverage of the\nneed (and lack of need) for the ensure_generations_valid() method.\n\nSigned-off-by: Derrick Stolee \n---\n commit-reach.c | 126 ++++++++++++++++++++++++++++++++++++++++++\n commit-reach.h | 17 ++++++\n t/helper/test-reach.c | 2 +\n t/t6600-test-reach.sh | 61 ++++++++++++++++++++\n 4 files changed, 206 insertions(+)\n\ndiff --git a/commit-reach.c b/commit-reach.c\nindex 8f9b008f876..4753197ec88 100644\n--- a/commit-reach.c\n+++ b/commit-reach.c\n@@ -1222,3 +1222,129 @@ done:\n \tfree(commits);\n \trepo_clear_commit_marks(r, SEEN);\n }\n+\n+/*\n+ * This slab initializes integers to zero, so use \"-1\" for \"tip is best\" and\n+ * \"i + 1\" for \"bases[i] is best\".\n+ */\n+define_commit_slab(best_branch_base, int);\n+static struct best_branch_base best_branch_base;\n+#define get_best(c) (*best_branch_base_at(&best_branch_base, (c)))\n+#define set_best(c,v) (*best_branch_base_at(&best_branch_base, (c)) = (v))\n+\n+int get_branch_base_for_tip(struct repository *r,\n+\t\t\t struct commit *tip,\n+\t\t\t struct commit **bases,\n+\t\t\t size_t bases_nr)\n+{\n+\tint best_index = -1;\n+\tstruct commit *branch_point = NULL;\n+\tstruct prio_queue queue = { compare_commits_by_gen_then_commit_date };\n+\tint found_missing_gen = 0;\n+\n+\tif (!bases_nr)\n+\t\treturn -1;\n+\n+\trepo_parse_commit(r, tip);\n+\tif (commit_graph_generation(tip) == GENERATION_NUMBER_INFINITY)\n+\t\tfound_missing_gen = 1;\n+\n+\t/* Check for missing generation numbers. */\n+\tfor (size_t i = 0; i < bases_nr; i++) {\n+\t\tstruct commit *c = bases[i];\n+\t\trepo_parse_commit(r, c);\n+\t\tif (commit_graph_generation(c) == GENERATION_NUMBER_INFINITY)\n+\t\t\tfound_missing_gen = 1;\n+\t}\n+\n+\tif (found_missing_gen) {\n+\t\tstruct commit **commits;\n+\t\tsize_t commits_nr = bases_nr + 1;\n+\n+\t\tCALLOC_ARRAY(commits, commits_nr);\n+\t\tCOPY_ARRAY(commits, bases, bases_nr);\n+\t\tcommits[bases_nr] = tip;\n+\t\tensure_generations_valid(r, commits, commits_nr);\n+\t\tfree(commits);\n+\t}\n+\n+\t/* Initialize queue and slab now that generations are guaranteed. */\n+\tinit_best_branch_base(&best_branch_base);\n+\tset_best(tip, -1);\n+\tprio_queue_put(&queue, tip);\n+\n+\tfor (size_t i = 0; i < bases_nr; i++) {\n+\t\tstruct commit *c = bases[i];\n+\t\tint best = get_best(c);\n+\n+\t\t/* Has this already been marked as best by another commit? */\n+\t\tif (best) {\n+\t\t\tif (best == -1) {\n+\t\t\t\t/* We agree at this position. Stop now. */\n+\t\t\t\tbest_index = i + 1;\n+\t\t\t\tgoto cleanup;\n+\t\t\t}\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tset_best(c, i + 1);\n+\t\tprio_queue_put(&queue, c);\n+\t}\n+\n+\twhile (queue.nr) {\n+\t\tstruct commit *c = prio_queue_get(&queue);\n+\t\tint best_for_c = get_best(c);\n+\t\tint best_for_p, positive;\n+\t\tstruct commit *parent;\n+\n+\t\t/* Have we reached a known branch point? It's optimal. */\n+\t\tif (c == branch_point)\n+\t\t\tbreak;\n+\n+\t\trepo_parse_commit(r, c);\n+\t\tif (!c->parents)\n+\t\t\tcontinue;\n+\n+\t\tparent = c->parents->item;\n+\t\trepo_parse_commit(r, parent);\n+\t\tbest_for_p = get_best(parent);\n+\n+\t\tif (!best_for_p) {\n+\t\t\t/* 'parent' is new, so pass along best_for_c. */\n+\t\t\tset_best(parent, best_for_c);\n+\t\t\tprio_queue_put(&queue, parent);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tif (best_for_p > 0 && best_for_c > 0) {\n+\t\t\t/* Collision among bases. Minimize. */\n+\t\t\tif (best_for_c < best_for_p)\n+\t\t\t\tset_best(parent, best_for_c);\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\t/*\n+\t\t * At this point, we have reached a commit that is reachable\n+\t\t * from the tip, either from 'c' or from an earlier commit to\n+\t\t * have 'parent' as its first parent.\n+\t\t *\n+\t\t * Update 'best_index' to match the minimum of all base indices\n+\t\t * to reach 'parent'.\n+\t\t */\n+\n+\t\t/* Exactly one is positive due to initial conditions. */\n+\t\tpositive = (best_for_c < 0) ? best_for_p : best_for_c;\n+\n+\t\tif (best_index < 0 || positive < best_index)\n+\t\t\tbest_index = positive;\n+\n+\t\t/* No matter what, track that the parent is reachable from tip. */\n+\t\tset_best(parent, -1);\n+\t\tbranch_point = parent;\n+\t}\n+\n+cleanup:\n+\tclear_best_branch_base(&best_branch_base);\n+\tclear_prio_queue(&queue);\n+\treturn best_index > 0 ? best_index - 1 : -1;\n+}\ndiff --git a/commit-reach.h b/commit-reach.h\nindex bf63cc468fd..9a745b7e176 100644\n--- a/commit-reach.h\n+++ b/commit-reach.h\n@@ -139,4 +139,21 @@ void tips_reachable_from_bases(struct repository *r,\n \t\t\t struct commit **tips, size_t tips_nr,\n \t\t\t int mark);\n \n+/*\n+ * Given a 'tip' commit and a list potential 'bases', return the index 'i' that\n+ * minimizes the number of commits in the first-parent history of 'tip' and not\n+ * in the first-parent history of 'bases[i]'.\n+ *\n+ * Among a list of long-lived branches that are updated only by merges (with the\n+ * first parent being the previous position of the branch), this would inform\n+ * which branch was used to create the tip reference.\n+ *\n+ * Returns -1 if no common point is found in first-parent histories, which is\n+ * rare, but possible with multiple root commits.\n+ */\n+int get_branch_base_for_tip(struct repository *r,\n+\t\t\t struct commit *tip,\n+\t\t\t struct commit **bases,\n+\t\t\t size_t bases_nr);\n+\n #endif\ndiff --git a/t/helper/test-reach.c b/t/helper/test-reach.c\nindex 1e3b431e3e7..8579b607aa5 100644\n--- a/t/helper/test-reach.c\n+++ b/t/helper/test-reach.c\n@@ -114,6 +114,8 @@ int cmd__reach(int ac, const char **av)\n \t\t repo_in_merge_bases_many(the_repository, A, X_nr, X_array, 0));\n \telse if (!strcmp(av[1], \"is_descendant_of\"))\n \t\tprintf(\"%s(A,X):%d\\n\", av[1], repo_is_descendant_of(r, A, X));\n+\telse if (!strcmp(av[1], \"get_branch_base_for_tip\"))\n+\t\tprintf(\"%s(A,X):%d\\n\", av[1], get_branch_base_for_tip(r, A, X_array, X_nr));\n \telse if (!strcmp(av[1], \"get_merge_bases_many\")) {\n \t\tstruct commit_list *list = NULL;\n \t\tif (repo_get_merge_bases_many(the_repository,\ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex b330945f497..e789a4720c1 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -612,4 +612,65 @@ test_expect_success 'for-each-ref merged:none' '\n \t\t--format=\"%(refname)\" --stdin\n '\n \n+# For get_branch_base_for_tip, we only care about\n+# first-parent history. Here is the test graph with\n+# second parents removed:\n+#\n+# (10,10)\n+# /\n+# (10,9) (9,10)\n+# / /\n+# (10,8) (9,9) (8,10)\n+# / / /\n+# ( continued...)\n+# \\ / / /\n+# (3,1) (2,2) (1,3)\n+# \\ / /\n+# (2,1) (1,2)\n+# \\ /\n+# (1,1)\n+#\n+# In short, for a commit (i,j), the first-parent history\n+# walks all commits (i, k) with k from j to 1, then the\n+# commits (l, 1) with l from i to 1.\n+\n+test_expect_success 'get_branch_base_for_tip: none reach' '\n+\t# (2,3) branched from the first tip (i,4) in X with i > 2\n+\tcat >input <<-\\EOF &&\n+\t\tA:commit-2-3\n+\t\tX:commit-1-2\n+\t\tX:commit-1-4\n+\t\tX:commit-4-4\n+\t\tX:commit-8-4\n+\t\tX:commit-10-4\n+\tEOF\n+\techo \"get_branch_base_for_tip(A,X):2\" >expect &&\n+\ttest_all_modes get_branch_base_for_tip\n+'\n+\n+test_expect_success 'get_branch_base_for_tip: equal to tip' '\n+\t# (2,3) branched from the first tip (i,4) in X with i > 2\n+\tcat >input <<-\\EOF &&\n+\t\tA:commit-8-4\n+\t\tX:commit-1-2\n+\t\tX:commit-1-4\n+\t\tX:commit-4-4\n+\t\tX:commit-8-4\n+\t\tX:commit-10-4\n+\tEOF\n+\techo \"get_branch_base_for_tip(A,X):3\" >expect &&\n+\ttest_all_modes get_branch_base_for_tip\n+'\n+\n+test_expect_success 'get_branch_base_for_tip: all reach tip' '\n+\t# (2,3) branched from the first tip (i,4) in X with i > 2\n+\tcat >input <<-\\EOF &&\n+\t\tA:commit-4-1\n+\t\tX:commit-4-2\n+\t\tX:commit-5-1\n+\tEOF\n+\techo \"get_branch_base_for_tip(A,X):0\" >expect &&\n+\ttest_all_modes get_branch_base_for_tip\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"500871","messageId":"5240c2a7b328e3d356574a1ab00e2faa8a71d92a.1723631490.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v3.git.1723631490.gitgitgadget@gmail.com","subject":"[PATCH v3 2/4] commit: add gentle reference lookup method","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-14T10:31:28Z","receivedAt":"2024-08-14T10:31:36Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe lookup_commit_reference_by_name() method uses lookup_commit_reference()\nwithout an option to use lookup_commit_reference_gently(). Create a gentle\nversion of the method so it can be used in locations where non-commits may\nbe found but error messages should be silenced.\n\nSigned-off-by: Derrick Stolee \n---\n commit.c | 8 +++++++-\n commit.h | 2 ++\n 2 files changed, 9 insertions(+), 1 deletion(-)\n\ndiff --git a/commit.c b/commit.c\nindex 1a479a997c4..ed49be8dce5 100644\n--- a/commit.c\n+++ b/commit.c\n@@ -82,13 +82,19 @@ struct commit *lookup_commit(struct repository *r, const struct object_id *oid)\n }\n \n struct commit *lookup_commit_reference_by_name(const char *name)\n+{\n+\treturn lookup_commit_reference_by_name_gently(name, 0);\n+}\n+\n+struct commit *lookup_commit_reference_by_name_gently(const char *name,\n+\t\t\t\t\t\t int quiet)\n {\n \tstruct object_id oid;\n \tstruct commit *commit;\n \n \tif (repo_get_oid_committish(the_repository, name, &oid))\n \t\treturn NULL;\n-\tcommit = lookup_commit_reference(the_repository, &oid);\n+\tcommit = lookup_commit_reference_gently(the_repository, &oid, quiet);\n \tif (repo_parse_commit(the_repository, commit))\n \t\treturn NULL;\n \treturn commit;\ndiff --git a/commit.h b/commit.h\nindex 62fe0d77a70..ef17668cc69 100644\n--- a/commit.h\n+++ b/commit.h\n@@ -81,6 +81,8 @@ struct commit *lookup_commit_reference_gently(struct repository *r,\n \t\t\t\t\t const struct object_id *oid,\n \t\t\t\t\t int quiet);\n struct commit *lookup_commit_reference_by_name(const char *name);\n+struct commit *lookup_commit_reference_by_name_gently(const char *name,\n+\t\t\t\t\t\t int quiet);\n \n /*\n * Look up object named by \"oid\", dereference tag as necessary,\n-- \ngitgitgadget\n\n"},{"id":"500872","messageId":"df05cee6003d7ad5ea750835cad763848365c043.1723631490.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v3.git.1723631490.gitgitgadget@gmail.com","subject":"[PATCH v3 3/4] for-each-ref: add 'is-base' token","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-14T10:31:29Z","receivedAt":"2024-08-14T10:31:37Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous change introduced the get_branch_base_for_tip() method in\ncommit-reach.c. The motivation of that change was about using a heuristic to\ndeteremine the base branch for a source commit from a list of candidate\ncommit tips. This change makes that algorithm visible to users via a new\natom in the 'git for-each-ref' format. This change is very similar to the\nchang in 49abcd21da6 (for-each-ref: add ahead-behind format atom,\n2023-03-20).\n\nIntroduce the 'is-base:' atom, which will indicate that the\nalgorithm should be computed and the result of the algorithm is reported\nusing an indicator of the form '()'. For example, using\n'%(is-base:HEAD)' would result in one line having the token '(HEAD)'.\n\nUse the sorted order of refs included in the ref filter to break ties in the\nalgorithm's heuristic. In the previous change, the motivating examples\ninclude using an L0 trunk, long-lived L1 branches, and temporary release\nbranches. A caller could communicate the ordered preference among these\ncategories using the input refpecs and avoiding a different sort mechanism.\nThis sorting behavior is tested in the test scripts.\n\nIt is important to include this atom as a special case to\ncan_do_iterative_format() to match the expectations created in bd98f9774e1\n(ref-filter.c: filter & format refs in the same callback, 2023-11-14). The\nahead-behind atom was one of the special cases, and this similarly requires\nusing an algorithm across all input refs before starting the format of any\nsingle ref.\n\nIn the test script, the format tokens use colons or lack whitespace to avoid\nGit complaining about trailing whitespace errors.\n\nSigned-off-by: Derrick Stolee \n---\n Documentation/git-for-each-ref.txt | 42 ++++++++++++++++\n ref-filter.c | 77 +++++++++++++++++++++++++++++-\n ref-filter.h | 15 ++++++\n t/t6300-for-each-ref.sh | 9 ++++\n t/t6600-test-reach.sh | 60 +++++++++++++++++++++++\n 5 files changed, 202 insertions(+), 1 deletion(-)\n\ndiff --git a/Documentation/git-for-each-ref.txt b/Documentation/git-for-each-ref.txt\nindex c1dd12b93cf..d3764401a23 100644\n--- a/Documentation/git-for-each-ref.txt\n+++ b/Documentation/git-for-each-ref.txt\n@@ -264,6 +264,48 @@ ahead-behind:::\n \tcommits ahead and behind, respectively, when comparing the output\n \tref to the `` specified in the format.\n \n+is-base:::\n+\tIn at most one row, `()` will appear to indicate the ref\n+\tthat is most likely the ref used as a starting point for the branch\n+\tthat produced ``. This choice is made using a heuristic:\n+\tchoose the ref that minimizes the number of commits in the\n+\tfirst-parent history of `` and not in the first-parent\n+\thistory of the ref.\n++\n+For example, consider the following figure of first-parent histories of\n+several refs:\n++\n+----\n+*--*--*--*--*--* refs/heads/A\n+\\\n+ \\\n+ *--*--*--* refs/heads/B\n+ \\ \\\n+ \\ \\\n+ * * refs/heads/C\n+ \\\n+ \\\n+\t*--* refs/heads/D\n+----\n++\n+Here, if `A`, `B`, and `C` are the filtered references, and the format\n+string is `%(refname):%(is-base:D)`, then the output would be\n++\n+----\n+refs/heads/A:\n+refs/heads/B:(D)\n+refs/heads/C:\n+----\n++\n+This is because the first-parent history of `D` has its earliest\n+intersection with the first-parent histories of the filtered refs at a\n+common first-parent ancestor of `B` and `C` and ties are broken by the\n+earliest ref in the sorted order.\n++\n+Note that this token will not appear if the first-parent history of\n+`` does not intersect the first-parent histories of the\n+filtered refs.\n+\n describe[:options]::\n \tA human-readable name, like linkgit:git-describe[1];\n \tempty string for undescribable commits. The `describe` string may\ndiff --git a/ref-filter.c b/ref-filter.c\nindex 59ad6f54ddb..3d598f6b6e6 100644\n--- a/ref-filter.c\n+++ b/ref-filter.c\n@@ -167,6 +167,7 @@ enum atom_type {\n \tATOM_ELSE,\n \tATOM_REST,\n \tATOM_AHEADBEHIND,\n+\tATOM_ISBASE,\n };\n \n /*\n@@ -889,6 +890,23 @@ static int ahead_behind_atom_parser(struct ref_format *format,\n \treturn 0;\n }\n \n+static int is_base_atom_parser(struct ref_format *format,\n+\t\t\t struct used_atom *atom UNUSED,\n+\t\t\t const char *arg, struct strbuf *err)\n+{\n+\tstruct string_list_item *item;\n+\n+\tif (!arg)\n+\t\treturn strbuf_addf_ret(err, -1, _(\"expected format: %%(is-base:)\"));\n+\n+\titem = string_list_append(&format->is_base_tips, arg);\n+\titem->util = lookup_commit_reference_by_name(arg);\n+\tif (!item->util)\n+\t\tdie(\"failed to find '%s'\", arg);\n+\n+\treturn 0;\n+}\n+\n static int head_atom_parser(struct ref_format *format UNUSED,\n \t\t\t struct used_atom *atom,\n \t\t\t const char *arg, struct strbuf *err)\n@@ -952,6 +970,7 @@ static struct {\n \t[ATOM_ELSE] = { \"else\", SOURCE_NONE },\n \t[ATOM_REST] = { \"rest\", SOURCE_NONE, FIELD_STR, rest_atom_parser },\n \t[ATOM_AHEADBEHIND] = { \"ahead-behind\", SOURCE_OTHER, FIELD_STR, ahead_behind_atom_parser },\n+\t[ATOM_ISBASE] = { \"is-base\", SOURCE_OTHER, FIELD_STR, is_base_atom_parser },\n \t/*\n \t * Please update $__git_ref_fieldlist in git-completion.bash\n \t * when you add new atoms\n@@ -2334,6 +2353,7 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err)\n \tint i;\n \tstruct object_info empty = OBJECT_INFO_INIT;\n \tint ahead_behind_atoms = 0;\n+\tint is_base_atoms = 0;\n \n \tCALLOC_ARRAY(ref->value, used_atom_cnt);\n \n@@ -2475,6 +2495,15 @@ static int populate_value(struct ref_array_item *ref, struct strbuf *err)\n \t\t\t\tv->s = xstrdup(\"\");\n \t\t\t}\n \t\t\tcontinue;\n+\t\t} else if (atom_type == ATOM_ISBASE) {\n+\t\t\tif (ref->is_base && ref->is_base[is_base_atoms]) {\n+\t\t\t\tv->s = xstrfmt(\"(%s)\", ref->is_base[is_base_atoms]);\n+\t\t\t\tfree(ref->is_base[is_base_atoms]);\n+\t\t\t} else {\n+\t\t\t\tv->s = xstrdup(\"\");\n+\t\t\t}\n+\t\t\tis_base_atoms++;\n+\t\t\tcontinue;\n \t\t} else\n \t\t\tcontinue;\n \n@@ -2876,6 +2905,7 @@ static void free_array_item(struct ref_array_item *item)\n \t\tfree(item->value);\n \t}\n \tfree(item->counts);\n+\tfree(item->is_base);\n \tfree(item);\n }\n \n@@ -3040,6 +3070,49 @@ void filter_ahead_behind(struct repository *r,\n \tfree(commits);\n }\n \n+void filter_is_base(struct repository *r,\n+\t\t struct ref_format *format,\n+\t\t struct ref_array *array)\n+{\n+\tstruct commit **bases;\n+\tsize_t bases_nr = 0;\n+\tstruct ref_array_item **back_index;\n+\n+\tif (!format->is_base_tips.nr || !array->nr)\n+\t\treturn;\n+\n+\tCALLOC_ARRAY(back_index, array->nr);\n+\tCALLOC_ARRAY(bases, array->nr);\n+\n+\tfor (size_t i = 0; i < array->nr; i++) {\n+\t\tconst char *name = array->items[i]->refname;\n+\t\tstruct commit *c = lookup_commit_reference_by_name_gently(name, 1);\n+\n+\t\tCALLOC_ARRAY(array->items[i]->is_base, format->is_base_tips.nr);\n+\n+\t\tif (!c)\n+\t\t\tcontinue;\n+\n+\t\tback_index[bases_nr] = array->items[i];\n+\t\tbases[bases_nr] = c;\n+\t\tbases_nr++;\n+\t}\n+\n+\tfor (size_t i = 0; i < format->is_base_tips.nr; i++) {\n+\t\tstruct commit *tip = format->is_base_tips.items[i].util;\n+\t\tint base_index = get_branch_base_for_tip(r, tip, bases, bases_nr);\n+\n+\t\tif (base_index < 0)\n+\t\t\tcontinue;\n+\n+\t\t/* Store the string for use in output later. */\n+\t\tback_index[base_index]->is_base[i] = xstrdup(format->is_base_tips.items[i].string);\n+\t}\n+\n+\tfree(back_index);\n+\tfree(bases);\n+}\n+\n static int do_filter_refs(struct ref_filter *filter, unsigned int type, each_ref_fn fn, void *cb_data)\n {\n \tint ret = 0;\n@@ -3126,7 +3199,8 @@ static inline int can_do_iterative_format(struct ref_filter *filter,\n \treturn !(filter->reachable_from ||\n \t\t filter->unreachable_from ||\n \t\t sorting ||\n-\t\t format->bases.nr);\n+\t\t format->bases.nr ||\n+\t\t format->is_base_tips.nr);\n }\n \n void filter_and_format_refs(struct ref_filter *filter, unsigned int type,\n@@ -3150,6 +3224,7 @@ void filter_and_format_refs(struct ref_filter *filter, unsigned int type,\n \t\tstruct ref_array array = { 0 };\n \t\tfilter_refs(&array, filter, type);\n \t\tfilter_ahead_behind(the_repository, format, &array);\n+\t\tfilter_is_base(the_repository, format, &array);\n \t\tref_array_sort(sorting, &array);\n \t\tprint_formatted_ref_array(&array, format);\n \t\tref_array_clear(&array);\ndiff --git a/ref-filter.h b/ref-filter.h\nindex 0ca28d2bba6..20419a56218 100644\n--- a/ref-filter.h\n+++ b/ref-filter.h\n@@ -48,6 +48,7 @@ struct ref_array_item {\n \tstruct commit *commit;\n \tstruct atom_value *value;\n \tstruct ahead_behind_count **counts;\n+\tchar **is_base;\n \n \tchar refname[FLEX_ARRAY];\n };\n@@ -101,6 +102,9 @@ struct ref_format {\n \t/* List of bases for ahead-behind counts. */\n \tstruct string_list bases;\n \n+\t/* List of bases for is-base indicators. */\n+\tstruct string_list is_base_tips;\n+\n \tstruct {\n \t\tint max_count;\n \t\tint omit_empty;\n@@ -114,6 +118,7 @@ struct ref_format {\n #define REF_FORMAT_INIT { \\\n \t.use_color = -1, \\\n \t.bases = STRING_LIST_INIT_DUP, \\\n+\t.is_base_tips = STRING_LIST_INIT_DUP, \\\n }\n \n /* Macros for checking --merged and --no-merged options */\n@@ -203,6 +208,16 @@ void filter_ahead_behind(struct repository *r,\n \t\t\t struct ref_format *format,\n \t\t\t struct ref_array *array);\n \n+/*\n+ * If the provided format includes is-base atoms, then compute the base checks\n+ * for those tips against all refs.\n+ *\n+ * If this is not called, then any is-base atoms will be blank.\n+ */\n+void filter_is_base(struct repository *r,\n+\t\t struct ref_format *format,\n+\t\t struct ref_array *array);\n+\n void ref_filter_init(struct ref_filter *filter);\n void ref_filter_clear(struct ref_filter *filter);\n \ndiff --git a/t/t6300-for-each-ref.sh b/t/t6300-for-each-ref.sh\nindex eb6c8204e8b..8d15713cc67 100755\n--- a/t/t6300-for-each-ref.sh\n+++ b/t/t6300-for-each-ref.sh\n@@ -1907,6 +1907,15 @@ test_expect_success 'git for-each-ref with nested tags' '\n \ttest_cmp expect actual\n '\n \n+test_expect_success 'is-base atom with non-commits' '\n+\tgit for-each-ref --format=\"%(is-base:HEAD) %(refname)\" >out 2>err &&\n+\tgrep \"(HEAD) refs/heads/main\" out &&\n+\n+\ttest_line_count = 2 err &&\n+\tgrep \"error: object .* is a commit, not a blob\" err &&\n+\tgrep \"error: bad tag pointer to\" err\n+'\n+\n GRADE_FORMAT=\"%(signature:grade)%0a%(signature:key)%0a%(signature:signer)%0a%(signature:fingerprint)%0a%(signature:primarykeyfingerprint)\"\n TRUSTLEVEL_FORMAT=\"%(signature:trustlevel)%0a%(signature:key)%0a%(signature:signer)%0a%(signature:fingerprint)%0a%(signature:primarykeyfingerprint)\"\n \ndiff --git a/t/t6600-test-reach.sh b/t/t6600-test-reach.sh\nindex e789a4720c1..2591f8b8b39 100755\n--- a/t/t6600-test-reach.sh\n+++ b/t/t6600-test-reach.sh\n@@ -673,4 +673,64 @@ test_expect_success 'get_branch_base_for_tip: all reach tip' '\n \ttest_all_modes get_branch_base_for_tip\n '\n \n+test_expect_success 'for-each-ref is-base: none reach' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-4-4\n+\trefs/heads/commit-8-4\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-1-1:\n+\trefs/heads/commit-4-2:(commit-2-3)\n+\trefs/heads/commit-4-4:\n+\trefs/heads/commit-8-4:\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname):%(is-base:commit-2-3)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref is-base: all reach' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-5-1\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-4-2:(commit-4-1)\n+\trefs/heads/commit-5-1:\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname):%(is-base:commit-4-1)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref is-base: equal to tip' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-5-1\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-4-2:(commit-4-2)\n+\trefs/heads/commit-5-1:\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname):%(is-base:commit-4-2)\" --stdin\n+'\n+\n+test_expect_success 'for-each-ref is-base:multiple' '\n+\tcat >input <<-\\EOF &&\n+\trefs/heads/commit-1-1\n+\trefs/heads/commit-4-2\n+\trefs/heads/commit-4-4\n+\trefs/heads/commit-8-4\n+\tEOF\n+\tcat >expect <<-\\EOF &&\n+\trefs/heads/commit-1-1[-]\n+\trefs/heads/commit-4-2[(commit-2-3)-]\n+\trefs/heads/commit-4-4[-]\n+\trefs/heads/commit-8-4[-(commit-6-5)]\n+\tEOF\n+\trun_all_modes git for-each-ref \\\n+\t\t--format=\"%(refname)[%(is-base:commit-2-3)-%(is-base:commit-6-5)]\" --stdin\n+'\n+\n test_done\n-- \ngitgitgadget\n\n"},{"id":"500873","messageId":"cce9921bbd8825c3a12d32b2c8b62a2c4b06333a.1723631490.git.gitgitgadget@gmail.com","threadId":"61884","inReplyTo":"pull.1768.v3.git.1723631490.gitgitgadget@gmail.com","subject":"[PATCH v3 4/4] p1500: add is-base performance tests","fromName":"Derrick Stolee via GitGitGadget","fromEmail":"gitgitgadget@gmail.com","sentAt":"2024-08-14T10:31:30Z","receivedAt":"2024-08-14T10:31:38Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"From: Derrick Stolee \n\nThe previous two changes introduced a commit walking heuristic for finding\nthe most likely base branch for a given source. This algorithm walks\nfirst-parent histories until reaching a collision.\n\nThis walk _should_ be very fast. Exceptions include cases where a\ncommit-graph file does not exist, leading to a full walk of all reachable\ncommits to compute generation numbers, or a case where no collision in the\nfirst-parent history exists, leading to a walk of all first-parent history\nto the root commits.\n\nThe p1500 test script guarantees a complete commit-graph file during its\nsetup, so we will not test that scenario. Do create a new root commit in an\neffort to test the scenario of parallel first-parent histories.\n\nEven with the extra root commit, these tests take no longer than 0.02\nseconds on my machine for the Git repository. However, the results are\nslightly more interesting in a copy of the Linux kernel repository:\n\nTest\n---------------------------------------------------------------\n1500.2: ahead-behind counts: git for-each-ref 0.12\n1500.3: ahead-behind counts: git branch 0.12\n1500.4: ahead-behind counts: git tag 0.12\n1500.5: contains: git for-each-ref --merged 0.04\n1500.6: contains: git branch --merged 0.04\n1500.7: contains: git tag --merged 0.04\n1500.8: is-base check: test-tool reach (refs) 0.03\n1500.9: is-base check: test-tool reach (tags) 0.03\n1500.10: is-base check: git for-each-ref 0.03\n1500.11: is-base check: git for-each-ref (disjoint-base) 0.07\n\nSigned-off-by: Derrick Stolee \n---\n t/perf/p1500-graph-walks.sh | 31 +++++++++++++++++++++++++++++++\n 1 file changed, 31 insertions(+)\n\ndiff --git a/t/perf/p1500-graph-walks.sh b/t/perf/p1500-graph-walks.sh\nindex e14e7620cce..5b23ce5db93 100755\n--- a/t/perf/p1500-graph-walks.sh\n+++ b/t/perf/p1500-graph-walks.sh\n@@ -20,6 +20,21 @@ test_expect_success 'setup' '\n \t\techo tag-$ref ||\n \t\treturn 1\n \tdone >tags &&\n+\n+\techo \"A:HEAD\" >test-tool-refs &&\n+\tfor line in $(cat refs)\n+\tdo\n+\t\techo \"X:$line\" >>test-tool-refs || return 1\n+\tdone &&\n+\techo \"A:HEAD\" >test-tool-tags &&\n+\tfor line in $(cat tags)\n+\tdo\n+\t\techo \"X:$line\" >>test-tool-tags || return 1\n+\tdone &&\n+\n+\tcommit=$(git commit-tree $(git rev-parse HEAD^{tree})) &&\n+\tgit update-ref refs/heads/disjoint-base $commit &&\n+\n \tgit commit-graph write --reachable\n '\n \n@@ -47,4 +62,20 @@ test_perf 'contains: git tag --merged' '\n \txargs git tag --merged=HEAD writes:\n\n> There are benefits to users both on client-side and server-side. In an\n> internal monorepo, this base branch detection algorithm is used to determine\n> a long-lived branch based on the HEAD commit, mapping to a group within the\n> organizational structure of the repository, which determines a set of\n> projects that the user will likely need to build; this leads to\n> automatically selecting an initial sparse-checkout definition based on the\n> build dependencies required. An upcoming feature in Azure Repos will use\n> this algorithm to automatically create a pull request against the correct\n> target branch, reducing user pain from needing to select a different branch\n> after a large commit diff is rendered against the default branch. This atom\n> unlocks that ability for Git hosting services that use Git in their backend.\n\nThanks for an update. This iteration looks good to me.\n\n"},{"id":"501312","messageId":"be1182e5-5b0d-4deb-8b47-e38d05d184a0@gmail.com","threadId":"61884","inReplyTo":"xmqqed6ke1dx.fsf@gitster.g","subject":"Re: [PATCH v3 0/4] git for-each-ref: is-base atom and base branches","fromName":"Derrick Stolee","fromEmail":"stolee@gmail.com","sentAt":"2024-08-20T01:33:50Z","receivedAt":"2024-08-20T01:33:52Z","isPatch":true,"sender":{"key":"stolee@gmail.com","avatar":"https://avatars.githubusercontent.com/u/570044?v=4"},"body":"On 8/19/24 3:52 PM, Junio C Hamano wrote:\n> \"Derrick Stolee via GitGitGadget\" writes:\n> \n>> There are benefits to users both on client-side and server-side. In an\n>> internal monorepo, this base branch detection algorithm is used to determine\n>> a long-lived branch based on the HEAD commit, mapping to a group within the\n>> organizational structure of the repository, which determines a set of\n>> projects that the user will likely need to build; this leads to\n>> automatically selecting an initial sparse-checkout definition based on the\n>> build dependencies required. An upcoming feature in Azure Repos will use\n>> this algorithm to automatically create a pull request against the correct\n>> target branch, reducing user pain from needing to select a different branch\n>> after a large commit diff is rendered against the default branch. This atom\n>> unlocks that ability for Git hosting services that use Git in their backend.\n> \n> Thanks for an update. This iteration looks good to me.\n\nThank you for your careful review.\n\n-Stolee\n\n\n"}]}