Tags: gitgitgadget/git
Tags
rust: validate object map insert algorithms From: Feng Wu <wufengwufengwufeng@gmail.com> The loose object map stores entries keyed by the repository's storage hash and the compatible hash. ObjectMap::insert() accepts its two object IDs in either order, but it currently checks only whether oid1 uses the compatible hash algorithm. If it does not, oid2 is assumed to be the compatible ID without validating oid2's algorithm. That means callers can pass two IDs with the same algorithm, or an ID using an unknown algorithm, and have one of them silently treated as the storage ID. This does not match the map invariant that each entry must contain exactly one storage hash and one compatible hash. Make the invariant explicit by decoding both object ID algorithms and rejecting unknown or mismatched pairs before inserting anything. Introduce ObjectMapInsertError with InvalidHashAlgorithm and MismatchedAlgorithms variants for clear error reporting. Update the existing tests to unwrap successful insertions, and add tests for same-algorithm and unknown-algorithm inputs. Signed-off-by: Feng Wu <wufengwufengwufeng@gmail.com> Submitted-As: https://lore.kernel.org/git/pull.2350.git.git.1782489506255.gitgitgadget@gmail.com
commit-reach: terminate merge-base walk when one side is exhausted
commit-reach: terminate merge-base walk when one paint side is exhausted
Optimize paint_down_to_common() for merge-base queries that hit large
one-sided histories.
When the walk from one side reaches a commit with a very low generation
number that the other side never paints, the walk is forced to drain most of
the graph. A common trigger is a repository import that grafts a separate
history with its own root, but any merge that introduces a low-generation
commit never painted by the other side has the same effect.
A new merge-base candidate can only be discovered when exclusive PARENT1 and
PARENT2 paint meet. This series teaches paint_down_to_common() to stop as
soon as one side has no exclusive commits left in the queue; once one side
is exhausted, no further candidates can appear.
origin/HEAD o o PR HEAD
| |
(import) o :
/ \ /
| o merge-base
| |
: : (~2.5M commits)
| |
import root main root
In the RFC thread [1], Derrick Stolee provided a criss-cross counterexample
that sharpened the halt condition, and Elijah Newren independently
discovered the same optimization and shared an implementation in PR #2150
[2]. Patches 2-3 incorporate test cases from Elijah's branch.
This series implements the optimization only after the walk enters the
finite-generation region, where generation ordering guarantees that paint on
visited commits is final.
Patch layout:
1/8 Documentation/technical: add paint-down-to-common doc 2/8 t6600: add
test cases for side-exhaustion edge cases 3/8 t6099, t6600: add
side-exhaustion regression tests 4/8 commit-reach: add trace2
instrumentation to paint_down_to_common() 5/8 commit-reach: introduce struct
paint_state with per-side counters 6/8 commit-reach: remove unused
nonstale_queue dedup wrappers 7/8 commit-reach: terminate merge-base walk
when one paint side is exhausted 8/8 commit-reach: move min_generation check
into paint_queue_get()
Benchmarks
Step counts are deterministic (measured via trace2_data_intmax added in
patch 4). Wall-clock times are best-of-11 runs.
2.6M-commit monorepo with commit-graph:
steps wall-clock
merge-base --all (across import) 2143438 -> 3 3.67s -> 5ms
merge-base --all (1000 apart) 2692915 -> 1035 4.41s -> 7ms
merge-base --all (5000 apart) 2692915 -> 6401 4.45s -> 13ms
merge-base --all (HEAD vs import) 2698872 -> 45960 4.50s -> 79ms
merge-tree (across import) 2143438 -> 3 4.42s -> 11ms
git.git (88k commits, commit-graph):
steps wall-clock
merge-base --all v2.0.0 v2.55.0-rc1 72264 -> 44589 110ms -> 68ms
merge-base --all HEAD HEAD~1000 9891 -> 3828 18ms -> 10ms
merge-base --all HEAD HEAD~10000 72303 -> 41487 101ms -> 50ms
Changes since v2:
* New patch 8/8: moved the min_generation termination check and the
last_gen monotonicity assertion into paint_queue_get(), consolidating
halt conditions. commit_graph_generation() is now called once per
dequeued commit and shared across all checks.
* Widened the generation-monotonicity BUG assertion to fire
unconditionally, not only when min_generation is set. The side-exhaustion
optimization depends on correct generation ordering, so the assertion
should always be active. This is a behavior change: the BUG() now fires
for any generation ordering violation, regardless of the caller.
* Moved all halt conditions inside paint_queue_get() with the "pop first"
form: pop, check, then decrement counters. This keeps the optimization
commit's diff minimal (just inserting the new checks between pop and
decrement).
* Shortened the doc comment on paint_queue_get() to describe what it does
rather than how. Inline comments on each return NULL explain the specific
halt condition.
* Replaced the manual commit-graph setup in the step-count test with
run_all_modes, which now sets GIT_TRACE2_EVENT per mode and produces
trace-mode-{none,full,half,no-gdat}.txt files.
* Added a test_paint_down_steps helper for concise 4-mode step assertions
with diagnostic output on mismatch (prints "expected X, got Y" instead of
a silent grep failure).
* Added step-count assertions to the single-walk edge-case tests:
in_merge_bases_many:self, pending-stale, infinity-both-sides,
mixed-finite-infinity.
* Included step counts alongside wall-clock times in the benchmark tables.
Changes since v1:
* Reordered patches: documentation first (describing the existing
algorithm), tests before code changes, so they demonstrate passing with
old logic first.
* Dropped the ahead_behind decoupling patch. paint_state is now a NEW
struct alongside nonstale_queue instead of replacing it. ahead_behind()
is completely untouched.
* Removed nonstale_queue_put_dedup() and nonstale_queue_get_dedup() (dead
code after the conversion) in a separate commit.
* Renamed: struct paint_queue -> paint_state, field pq -> queue,
paint_count_add/remove -> paint_count_update (single function with signed
delta parameter).
* Split the old paint_count_transition (which handled both old and new
flags in one call) into separate remove/add calls with a signed delta.
This eliminates the need for the case 0 handler (which tracked "not in
the queue") and allows an exhaustive switch on (PARENT1 | PARENT2 |
STALE) that documents all valid flag combinations, with BUG() in default.
* Added trace2_data_intmax() instrumentation to report the number of
commits visited per paint walk (separate commit), with deterministic
step-count assertions in t6600.
* Expanded switch statements to multi-line format per .clang-format.
* Used !count style throughout instead of count == 0.
* Updated technical documentation alongside code changes.
[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] #2150
Elijah Newren (1):
t6600: add test cases for side-exhaustion edge cases
Kristofer Karlsson (7):
Documentation/technical: add paint-down-to-common doc
t6099, t6600: add side-exhaustion regression tests
commit-reach: add trace2 instrumentation to paint_down_to_common()
commit-reach: introduce struct paint_state with per-side counters
commit-reach: remove unused nonstale_queue dedup wrappers
commit-reach: terminate merge-base walk when one paint side is
exhausted
commit-reach: move min_generation check into paint_queue_get()
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 137 +++++++++++++
commit-reach.c | 147 ++++++++++----
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 ++++++++
t/t6600-test-reach.sh | 181 ++++++++++++++++--
7 files changed, 501 insertions(+), 49 deletions(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
base-commit: 6c3d7b7
Submitted-As: https://lore.kernel.org/git/pull.2149.v3.git.1782479286.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2149.git.1781951820.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2149.v2.git.1782303254.gitgitgadget@gmail.com
history: close COMMIT_EDITMSG before launching the editor From: Johannes Schindelin <johannes.schindelin@gmx.de> The `git history reword` and `git history fixup` subcommands prepare the commit message by writing it to COMMIT_EDITMSG and then opening that same file a second time, in append mode, through `wt_status`'s `fp` field to append the status information. That second handle is never closed before `launch_editor()` runs, so the editor is started while git still holds the file open. Everywhere this leaks a file descriptor, but on Windows it is outright broken: a process cannot replace a file that another process keeps open, so an editor that rewrites COMMIT_EDITMSG by creating a fresh file in its place fails. This surfaced while running Git for Windows' test suite with BusyBox' `ash` as the POSIX shell: the fake editor's `cp message "$1"` aborts with "cp: can't create '.../COMMIT_EDITMSG': File exists" (MSYS2's coreutils `cp` hides the problem via its POSIX unlink emulation, BusyBox' native `cp` does not), making t3451-history-reword and t3453-history-fixup fail wholesale. Close the handle once the status has been written, before handing the file off to the editor. Assisted-by: Opus 4.8 Signed-off-by: Johannes Schindelin <johannes.schindelin@gmx.de> Submitted-As: https://lore.kernel.org/git/pull.2158.git.1782412427801.gitgitgadget@gmail.com
history: add squash subcommand to fold a range Adds git history squash <revision-range> to fold a range of commits. Changes in v5: * The range walk now uses --ancestry-path, so only commits descended from the base are folded; a single revision such as HEAD or HEAD~1 is now rejected as "not a <base>..<tip> range" rather than treated as a squash down to the root. * This adopts the --ancestry-path suggestion; the multi-base rejection is unchanged, so a side branch that forked before the base and merged in is still refused. * Added tests covering more merge topologies: two interior merges, a nested merge, an octopus merge, an octopus arm forked before the base, a merge among the descendants replayed above the range, and a ref pointing at an interior merge commit. Changes in v4: * git history squash now detects when another ref points at a commit inside the range being folded and refuses, with an advice.historyUpdateRefs hint to use --update-refs=head. * A merge inside the range is folded fine as long as the range has a single base; a range with merge commit at the tip or base also folds correctly. Only a range with more than one base is rejected. Changes in v3: * Moved the feature out of git rebase and into a new git history squash <revision-range> subcommand, per the list discussion. git rebase --squash is dropped. * Takes an arbitrary range (git history squash @~3.., git history squash @~5..@~2), folding it into the oldest commit and replaying any descendants on top. * Implemented as a single tree operation rather than picking each commit, so there are no repeated conflict stops (addresses Phillip's efficiency point). * A merge inside the range is folded fine, only a range with more than one base is rejected. * --reedit-message seeds the editor with every folded-in message, not just the oldest. Harald Nordgren (4): history: extract helper for a commit's parent tree history: give commit_tree_ext a message template history: add squash subcommand to fold a range history: re-edit a squash with every message Documentation/config/advice.adoc | 4 + Documentation/git-history.adoc | 26 ++ advice.c | 1 + advice.h | 1 + builtin/history.c | 341 ++++++++++++++++++--- t/meson.build | 1 + t/t3455-history-squash.sh | 497 +++++++++++++++++++++++++++++++ 7 files changed, 833 insertions(+), 38 deletions(-) create mode 100755 t/t3455-history-squash.sh base-commit: 26d8d94 Submitted-As: https://lore.kernel.org/git/pull.2337.v5.git.git.1782338102.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2337.git.git.1781465141.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2337.v2.git.git.1781512625.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2337.v3.git.git.1781810226.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2337.v4.git.git.1782021195.gitgitgadget@gmail.com
branch/push: suggest intended form when remote/branch slip given When the repository or upstream argument is a slip like "origin/main" or "origin main", suggest the intended "git push origin main" or "git branch --set-upstream-to=origin/main" form instead of failing with an unrelated error. Changes in v2: * Rewrote both commit messages to lead with the intended command, the easy slip, and the resulting error, instead of the terse original. * Gated each suggestion on advice_enabled() up front, so a user who silenced the hint pays no remote/ref lookups and falls through to the original error. Extracted the detection logic into helpers (die_if_repo_looks_like_ref, die_if_upstream_looks_like_remote) so each call site reads as a single guarded line. Harald Nordgren (2): branch: suggest <remote>/<branch> on upstream slip push: suggest <remote> <branch> for a slash slip Documentation/config/advice.adoc | 5 +++++ advice.c | 1 + advice.h | 1 + builtin/branch.c | 26 ++++++++++++++++++++++ builtin/push.c | 31 +++++++++++++++++++++++++- t/t3200-branch.sh | 38 ++++++++++++++++++++++++++++++++ t/t5529-push-errors.sh | 31 ++++++++++++++++++++++++++ 7 files changed, 132 insertions(+), 1 deletion(-) base-commit: ab776a6 Submitted-As: https://lore.kernel.org/git/pull.2331.v2.git.git.1782338114.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2331.git.git.1781262619.gitgitgadget@gmail.com
branch: delete-merged
Delete branches that have already been merged on upstream.
Changes in v18:
* Instead of keeping the whole chain of upstream branches, keep only the
ones an unmerged branch still needs. When a kept (merged) branch in turn
tracks a branch that is being deleted, clear its now-stale upstream
config.
* Rework spare_stacked_bases() to record the kept bases and, in a second
pass, clear the upstream of any whose own base is going away. Build the
to-delete list with strset_for_each_entry() instead of re-walking the
candidate array.
Changes in v17:
* Keep a merged branch when another surviving branch still tracks it as its
upstream, so --delete-merged no longer deletes a branch out from under
one stacked on top of it.
* Move the --dry-run and branch.<name>.deleteMerged opt-out fully into
their own commits.
Changes in v16:
* Convert delete_merged_branches() to take an unsigned int flags argument
instead of separate quiet/dry_run booleans, matching delete_branches()
* Reuse the strbuf across the skip-config loop (strbuf_reset per iteration,
single strbuf_release after) instead of allocating and freeing it each
time
* Rewrite the --delete-merged tests as integration tests: branches that
land commits upstream, with deletion and the checked-out, upstream-gone,
and push-equals-upstream safety cases exercised together in one run and
output asserted via test_cmp
* Collapse the many per-aspect test repos into a single reused repo set up
by a setup_repo_for_delete_merged helper, and rename helpers off the old
pm_/prune naming
* Nest single-repo setup sequences in ( cd ... ) subshells instead of
prefixing every command with -C
Changes in v15:
* Renamed --prune-merged to --delete-merged throughout. Not necessarily
final, but something to advance the discussion.
* --delete-merged now silently skips not-yet-merged branches instead of
warning.
* Initialized the delete_branches() flag locals where declared. Only force
stays deferred.
* delete_branches()/check_branch_commit() doc and code cleanups: redundant
branch NULL checks dropped, ref_array candidates = { 0 }, a BUG() for the
unreachable non-branch ref, and reworked --delete-merged doc wording.
* Broadened the --forked tests (local commits for realism, remote add -f,
--forked coverage), renamed the misleading trunk fixture, and replaced
the misnamed detached branch with git checkout --detach.
Changes in v14:
* Fixed a git branch -d -r regression (broke t5404/t5505/t5514): the
remotes path set a local force but not the DELETE_BRANCH_FORCE bit that
check_branch_commit() reads, so it wrongly ran the merge check.
* Made flags the single source of truth in delete_branches() so the bit and
the derived locals can't disagree.
* Works locally, but GitHub CI has problems that are there for other
branches too, hopefully not related
(git#2285).
Changes in v13:
* Reworked --forked into a real ref-filter applied in apply_ref_filter()
instead of a post-pass, so non-matching branches are never allocated.
* Match exact --forked patterns on full refnames (only globs use the
abbreviated upstream), and dropped the old helper machinery, forward
declaration, and string_list in favor of a strvec.
* Replaced the boolean parameters of
delete_branches()/check_branch_commit() with a single unsigned int flags.
* --prune-merged now collects candidates via filter_refs() rather than its
own branch walk.
* --prune-merged now takes its patterns as positional arguments (e.g. git
branch --prune-merged origin/main 'feature*') instead of repeating the
option.
Changes in v12:
* Reworked --forked from a standalone action into a --list-mode filter.
* Switched --forked and --prune-merged to repeatable OPT_STRING_LIST
options.
* Dropped the bare-remote-name resolution for --forked, the argument is now
a ref or a glob.
Changes in v11:
* The flags now take a branch, not a remote. --forked and --prune-merged
accept a literal upstream short name like origin/main or a wildmatch
pattern like origin/. The old --all-remotes flag is gone, since origin/
covers that case.
* The prune guard now compares @{push} against @{upstream}. A branch is
spared when these are equal. That is the trunk like case, such as local
main tracking and pushing to origin/main, where "fully merged to
upstream" cannot be told apart from "just pulled". Only branches that
push somewhere other than their upstream, typically fork based topics,
are candidates. The earlier /HEAD by name guard that the reviewer
rejected is gone.
* New --dry-run for --prune-merged.
Changes in v10:
* --forked / --prune-merged now take a branch glob instead of a remote name
— origin, origin/*, origin/release-- all work. This replaces the
remote-only form and subsumes the old --all-remotes flag, which has been
dropped.
* New --dry-run for --prune-merged.
Changes in v9:
* --force no longer has special meaning with --prune-merged; reachability
is always enforced. Use git branch -D to delete an unmerged branch.
Matches how git branch's other read/safe actions treat --force.
* Synopsis drops [-f]; "not fully merged" hint points at git branch -D.
* Dropped the --prune-merged --force tests.
Changes in v8:
* Delete only when the branch's work is actually reachable from its
upstream
* Skip branches whose upstream is gone (even with --force)
* Simplified the internal safety flag to live in one place
Changes in v7:
* --prune-merged now checks if a branch is merged into its own upstream
first. If the upstream is gone, it checks against the remote's default
branch instead. If neither exists, the branch is refused (use --force to
delete anyway).
Changes in v6:
* --prune-merged now measures merged-ness against the remote's default
branch instead of the candidate's upstream — so the decision no longer
depends on which branch happens to be checked out locally.
* delete_branches() / check_branch_commit() gained a per-candidate override
that lets a caller substitute a different "what counts as merged"
reference (or skip the check). branch -d callers pass NULL and keep their
existing semantics.
* prune_merged_branches() resolves each candidate's push-remote HEAD and
threads it through, so --prune-merged --all-remotes measures each
candidate against its own remote rather than a single global reference.
Changes in v5:
* Drop commit 'fetch: add --prune-merged'
Changes in v4:
* Resolve each remote's HEAD and collect the targets into a
protected_default_refs set in collect_forked_set.
* In prune_merged_branches, skip a candidate when its upstream is a
protected default ref and the local branch name matches the default
branch's leaf name (so a local main tracking origin/main is spared, but a
renamed trunk tracking origin/main is not).
* Also skip when the candidate's push ref points at a protected default
ref, so a topic branch configured to push to origin/main is never pruned.
* Tests: spare the local default branch; only protect by matching leaf name
(not by upstream alone); spare a branch whose push ref is the remote
default.
Changes in v3:
* s/remote-tracking refs/remote-tracking branches/g
Changes in v2:
* The whole feature moved out of git fetch and into git branch. git fetch
--prune-merged now just calls git branch --prune-merged after fetching.
* The fetch.pruneLocalBranches and remote..pruneLocalBranches config
options are gone, replaced by per-branch opt-out via branch..pruneMerged.
* New git branch --forked lists local branches whose upstream lives on the
given remote (read-only building block).
* New git branch --prune-merged deletes those branches, but only if their
tip is reachable from the upstream tracking ref; --force skips that
safety check.
* New git branch --all-remotes lets --forked/--prune-merged operate across
every configured remote at once.
* The currently checked-out branch in any worktree is always preserved.
* branch..pruneMerged=false lets you exempt a branch (e.g. a long-running
topic branch) even with --force; doesn't affect explicit git branch -d.
* delete_branches() got a warn_only mode so bulk deletion prints a one-line
warning per skipped branch instead of the noisy four-line hint that git
branch -d shows.
* New section in git-branch docs; git-fetch docs trimmed to just mention
--prune-merged.
* New tests in t3200-branch.sh for the new branch flags; t5510-fetch.sh
shrunk since most logic moved.
Harald Nordgren (7):
branch: add --forked filter for --list mode
branch: convert delete_branches() to a flags argument
branch: let delete_branches skip unmerged branches on bulk refusal
branch: prepare delete_branches for a bulk caller
branch: add --delete-merged <branch>
branch: add branch.<name>.deleteMerged opt-out
branch: add --dry-run for --delete-merged
Documentation/config/branch.adoc | 7 +
Documentation/git-branch.adoc | 48 ++++-
builtin/branch.c | 266 +++++++++++++++++++++---
ref-filter.c | 70 +++++++
ref-filter.h | 10 +
t/t3200-branch.sh | 342 +++++++++++++++++++++++++++++++
6 files changed, 715 insertions(+), 28 deletions(-)
base-commit: ab776a6
Submitted-As: https://lore.kernel.org/git/pull.2285.v18.git.git.1782338106.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.git.git.1777671337839.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v2.git.git.1777919250.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v3.git.git.1777965747.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v4.git.git.1778009038.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v5.git.git.1778482708.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v6.git.git.1778492691.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v7.git.git.1778574229.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v8.git.git.1778605658.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v9.git.git.1778700883.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v10.git.git.1779403204.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v11.git.git.1779449498.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v12.git.git.1780477479.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v13.git.git.1780684553.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v14.git.git.1780999917.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v15.git.git.1781542042.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v16.git.git.1781810729.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v17.git.git.1782113388.gitgitgadget@gmail.com
checkout: --track=fetch Extend checkout --track with a fetch mode to refresh start-point. Changes in v15: * Reword commit message to lead with motivation. * Drop RESOLVE_REF_NO_RECURSE so <ns>/HEAD lookup matches what git checkout does for the same ref. Drop redundant check_refname_format on a ref we just read. Replace memset with brace initializer. Use refs_ref_exists and pass NULL for the OID out-params. * Split the "set HEAD" error onto its own line via die_message and advise, matching the suggested format. * Remove 6 redundant tests, replace test $a = $b with test_cmp_rev, and rename test titles to avoid "namespace". Changes in v14: * Handle .h files in a better way. Changes in v13: * Create a preparatory commit that exposes find_tracking_remote_for_ref() and advise_ambiguous_fetch_refspec() from branch.c, so checkout can reuse the same lookup git branch --track uses. * Use advise_ambiguous_fetch_refspec() for the "multiple remotes match" case, so the wording matches git branch --track. Harald Nordgren (2): branch: expose helpers for finding the remote owning a tracking ref checkout: extend --track with a "fetch" mode to refresh start-point Documentation/git-checkout.adoc | 17 ++- Documentation/git-switch.adoc | 5 +- branch.c | 96 +++++++------- branch.h | 16 +++ builtin/checkout.c | 138 +++++++++++++++++++- t/t7201-co.sh | 222 ++++++++++++++++++++++++++++++++ 6 files changed, 443 insertions(+), 51 deletions(-) base-commit: ab776a6 Submitted-As: https://lore.kernel.org/git/pull.2281.v15.git.git.1782338098.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.git.git.1777024991531.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v2.git.git.1777140755373.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v3.git.git.1777188295021.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v4.git.git.1777228346809.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v5.git.git.1777367012441.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v6.git.git.1777847487823.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v7.git.git.1778280727849.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v8.git.git.1778507225500.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v9.git.git.1778583307774.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v10.git.git.1779091483321.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v11.git.git.1779177508772.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v12.git.git.1779358803652.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v13.git.git.1779565714.gitgitgadget@gmail.com In-Reply-To: https://lore.kernel.org/git/pull.2281.v14.git.git.1781786652.gitgitgadget@gmail.com
commit-reach: terminate merge-base walk when one side is exhausted
commit-reach: terminate merge-base walk when one side is exhausted
Optimize paint_down_to_common() for merge-base queries that hit large
one-sided histories.
When the walk from one side reaches a commit with a very low generation
number that the other side never paints, the walk is forced to drain most of
the graph. A common trigger is a repository import that grafts a separate
history with its own root, but any merge that introduces a low-generation
commit never painted by the other side has the same effect.
A new merge-base candidate can only be discovered when exclusive PARENT1 and
PARENT2 paint meet. This series teaches paint_down_to_common() to stop as
soon as one side has no exclusive commits left in the queue; once one side
is exhausted, no further candidates can appear.
origin/HEAD o o PR HEAD
| |
(import) o :
/ \ /
| o merge-base
| |
: : (~2.5M commits)
| |
import root main root
In the RFC thread [1], Derrick Stolee provided a criss-cross counterexample
that sharpened the halt condition, and Elijah Newren independently
discovered the same optimization and shared an implementation in PR #2150
[2]. Patches 2-3 incorporate test cases from Elijah's branch.
This series implements the optimization only after the walk enters the
finite-generation region, where generation ordering guarantees that paint on
visited commits is final.
Patch layout:
1/7 Documentation/technical: add paint-down-to-common doc 2/7 t6600: add
test cases for side-exhaustion edge cases 3/7 t6099, t6600: add
side-exhaustion regression tests 4/7 commit-reach: add trace2
instrumentation to paint_down_to_common() 5/7 commit-reach: introduce struct
paint_state with per-side counters 6/7 commit-reach: remove unused
nonstale_queue dedup wrappers 7/7 commit-reach: terminate merge-base walk
when one paint side is exhausted
Benchmarks
Step counts are deterministic (measured via trace2_data_intmax added in
patch 4). Wall-clock times are medians over 10-20 runs with CPU governor set
to performance.
2.6M-commit monorepo with commit-graph (baseline v2.55.0-rc1):
steps wall-clock
merge-base --all (across import) 2682391 -> 53521 7.26s -> 88ms
merge-base --all (1000 apart) 2659607 -> 1106 6.98s -> 8ms
merge-tree (across import) - 8.11s -> 100ms
git.git (88k commits, commit-graph):
steps wall-clock
merge-base --all v2.0.0 v2.55.0-rc1 72264 -> 44589 82ms -> 49ms
merge-base --all HEAD HEAD~1000 9873 -> 3817 19ms -> 9ms
merge-base --all HEAD HEAD~10000 72285 -> 41523 80ms -> 48ms
merge-base HEAD HEAD~1000 - 9ms -> 9ms
merge-base --is-ancestor HEAD~1000 HEAD - 6ms -> 6ms
Changes since v1:
* Reordered patches: documentation first (describing the existing
algorithm), tests before code changes, so they demonstrate passing with
old logic first.
* Dropped the ahead_behind decoupling patch. paint_state is now a NEW
struct alongside nonstale_queue instead of replacing it. ahead_behind()
is completely untouched.
* Removed nonstale_queue_put_dedup() and nonstale_queue_get_dedup() (dead
code after the conversion) in a separate commit.
* Renamed: struct paint_queue -> paint_state, field pq -> queue,
paint_count_add/remove -> paint_count_update (single function with signed
delta parameter).
* Split the old paint_count_transition (which handled both old and new
flags in one call) into separate remove/add calls with a signed delta.
This eliminates the need for the case 0 handler (which tracked "not in
the queue") and allows an exhaustive switch on (PARENT1 | PARENT2 |
STALE) that documents all valid flag combinations, with BUG() in default.
* Moved all termination conditions into paint_queue_get(). The all-zero
check and the side-exhaustion check are merged under a shared
!pending_merge_bases guard. paint_queue_get() derives the generation from
the dequeued commit itself, so no extra parameter is needed.
* Added trace2_data_intmax() instrumentation to report the number of
commits visited per paint walk (separate commit), with deterministic
step-count assertions in t6600.
* Expanded switch statements to multi-line format per .clang-format.
* Used !count style throughout instead of count == 0.
* Updated technical documentation alongside code changes.
* Added benchmark data (both git-bench wall-clock and trace2 step counts)
to commit messages.
[1]
https://lore.kernel.org/git/CAL71e4Ps-2_0+uuZu43N9pFnXBemoAohPs_eyRJf8taXHJPAXQ@mail.gmail.com/T/#u
[2] #2150
Elijah Newren (1):
t6600: add test cases for side-exhaustion edge cases
Kristofer Karlsson (6):
Documentation/technical: add paint-down-to-common doc
t6099, t6600: add side-exhaustion regression tests
commit-reach: add trace2 instrumentation to paint_down_to_common()
commit-reach: introduce struct paint_state with per-side counters
commit-reach: remove unused nonstale_queue dedup wrappers
commit-reach: terminate merge-base walk when one paint side is
exhausted
Documentation/Makefile | 1 +
Documentation/technical/meson.build | 1 +
.../technical/paint-down-to-common.adoc | 128 ++++++++++++++
commit-reach.c | 119 ++++++++++---
t/meson.build | 1 +
t/t6099-merge-base-side-exhaustion.sh | 82 +++++++++
t/t6600-test-reach.sh | 157 ++++++++++++++++++
7 files changed, 464 insertions(+), 25 deletions(-)
create mode 100644 Documentation/technical/paint-down-to-common.adoc
create mode 100755 t/t6099-merge-base-side-exhaustion.sh
base-commit: ab776a6
Submitted-As: https://lore.kernel.org/git/pull.2149.v2.git.1782303254.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2149.git.1781951820.gitgitgadget@gmail.com
branch: delete-merged
Delete branches that have already been merged on upstream.
Changes in v17:
* Keep a merged branch when another surviving branch still tracks it as its
upstream, so --delete-merged no longer deletes a branch out from under
one stacked on top of it.
* Move the --dry-run and branch.<name>.deleteMerged opt-out fully into
their own commits.
Changes in v16:
* Convert delete_merged_branches() to take an unsigned int flags argument
instead of separate quiet/dry_run booleans, matching delete_branches()
* Reuse the strbuf across the skip-config loop (strbuf_reset per iteration,
single strbuf_release after) instead of allocating and freeing it each
time
* Rewrite the --delete-merged tests as integration tests: branches that
land commits upstream, with deletion and the checked-out, upstream-gone,
and push-equals-upstream safety cases exercised together in one run and
output asserted via test_cmp
* Collapse the many per-aspect test repos into a single reused repo set up
by a setup_repo_for_delete_merged helper, and rename helpers off the old
pm_/prune naming
* Nest single-repo setup sequences in ( cd ... ) subshells instead of
prefixing every command with -C
Changes in v15:
* Renamed --prune-merged to --delete-merged throughout. Not necessarily
final, but something to advance the discussion.
* --delete-merged now silently skips not-yet-merged branches instead of
warning.
* Initialized the delete_branches() flag locals where declared. Only force
stays deferred.
* delete_branches()/check_branch_commit() doc and code cleanups: redundant
branch NULL checks dropped, ref_array candidates = { 0 }, a BUG() for the
unreachable non-branch ref, and reworked --delete-merged doc wording.
* Broadened the --forked tests (local commits for realism, remote add -f,
--forked coverage), renamed the misleading trunk fixture, and replaced
the misnamed detached branch with git checkout --detach.
Changes in v14:
* Fixed a git branch -d -r regression (broke t5404/t5505/t5514): the
remotes path set a local force but not the DELETE_BRANCH_FORCE bit that
check_branch_commit() reads, so it wrongly ran the merge check.
* Made flags the single source of truth in delete_branches() so the bit and
the derived locals can't disagree.
* Works locally, but GitHub CI has problems that are there for other
branches too, hopefully not related
(git#2285).
Changes in v13:
* Reworked --forked into a real ref-filter applied in apply_ref_filter()
instead of a post-pass, so non-matching branches are never allocated.
* Match exact --forked patterns on full refnames (only globs use the
abbreviated upstream), and dropped the old helper machinery, forward
declaration, and string_list in favor of a strvec.
* Replaced the boolean parameters of
delete_branches()/check_branch_commit() with a single unsigned int flags.
* --prune-merged now collects candidates via filter_refs() rather than its
own branch walk.
* --prune-merged now takes its patterns as positional arguments (e.g. git
branch --prune-merged origin/main 'feature*') instead of repeating the
option.
Changes in v12:
* Reworked --forked from a standalone action into a --list-mode filter.
* Switched --forked and --prune-merged to repeatable OPT_STRING_LIST
options.
* Dropped the bare-remote-name resolution for --forked, the argument is now
a ref or a glob.
Changes in v11:
* The flags now take a branch, not a remote. --forked and --prune-merged
accept a literal upstream short name like origin/main or a wildmatch
pattern like origin/. The old --all-remotes flag is gone, since origin/
covers that case.
* The prune guard now compares @{push} against @{upstream}. A branch is
spared when these are equal. That is the trunk like case, such as local
main tracking and pushing to origin/main, where "fully merged to
upstream" cannot be told apart from "just pulled". Only branches that
push somewhere other than their upstream, typically fork based topics,
are candidates. The earlier /HEAD by name guard that the reviewer
rejected is gone.
* New --dry-run for --prune-merged.
Changes in v10:
* --forked / --prune-merged now take a branch glob instead of a remote name
— origin, origin/*, origin/release-- all work. This replaces the
remote-only form and subsumes the old --all-remotes flag, which has been
dropped.
* New --dry-run for --prune-merged.
Changes in v9:
* --force no longer has special meaning with --prune-merged; reachability
is always enforced. Use git branch -D to delete an unmerged branch.
Matches how git branch's other read/safe actions treat --force.
* Synopsis drops [-f]; "not fully merged" hint points at git branch -D.
* Dropped the --prune-merged --force tests.
Changes in v8:
* Delete only when the branch's work is actually reachable from its
upstream
* Skip branches whose upstream is gone (even with --force)
* Simplified the internal safety flag to live in one place
Changes in v7:
* --prune-merged now checks if a branch is merged into its own upstream
first. If the upstream is gone, it checks against the remote's default
branch instead. If neither exists, the branch is refused (use --force to
delete anyway).
Changes in v6:
* --prune-merged now measures merged-ness against the remote's default
branch instead of the candidate's upstream — so the decision no longer
depends on which branch happens to be checked out locally.
* delete_branches() / check_branch_commit() gained a per-candidate override
that lets a caller substitute a different "what counts as merged"
reference (or skip the check). branch -d callers pass NULL and keep their
existing semantics.
* prune_merged_branches() resolves each candidate's push-remote HEAD and
threads it through, so --prune-merged --all-remotes measures each
candidate against its own remote rather than a single global reference.
Changes in v5:
* Drop commit 'fetch: add --prune-merged'
Changes in v4:
* Resolve each remote's HEAD and collect the targets into a
protected_default_refs set in collect_forked_set.
* In prune_merged_branches, skip a candidate when its upstream is a
protected default ref and the local branch name matches the default
branch's leaf name (so a local main tracking origin/main is spared, but a
renamed trunk tracking origin/main is not).
* Also skip when the candidate's push ref points at a protected default
ref, so a topic branch configured to push to origin/main is never pruned.
* Tests: spare the local default branch; only protect by matching leaf name
(not by upstream alone); spare a branch whose push ref is the remote
default.
Changes in v3:
* s/remote-tracking refs/remote-tracking branches/g
Changes in v2:
* The whole feature moved out of git fetch and into git branch. git fetch
--prune-merged now just calls git branch --prune-merged after fetching.
* The fetch.pruneLocalBranches and remote..pruneLocalBranches config
options are gone, replaced by per-branch opt-out via branch..pruneMerged.
* New git branch --forked lists local branches whose upstream lives on the
given remote (read-only building block).
* New git branch --prune-merged deletes those branches, but only if their
tip is reachable from the upstream tracking ref; --force skips that
safety check.
* New git branch --all-remotes lets --forked/--prune-merged operate across
every configured remote at once.
* The currently checked-out branch in any worktree is always preserved.
* branch..pruneMerged=false lets you exempt a branch (e.g. a long-running
topic branch) even with --force; doesn't affect explicit git branch -d.
* delete_branches() got a warn_only mode so bulk deletion prints a one-line
warning per skipped branch instead of the noisy four-line hint that git
branch -d shows.
* New section in git-branch docs; git-fetch docs trimmed to just mention
--prune-merged.
* New tests in t3200-branch.sh for the new branch flags; t5510-fetch.sh
shrunk since most logic moved.
Harald Nordgren (7):
branch: add --forked filter for --list mode
branch: convert delete_branches() to a flags argument
branch: let delete_branches skip unmerged branches on bulk refusal
branch: prepare delete_branches for a bulk caller
branch: add --delete-merged <branch>
branch: add branch.<name>.deleteMerged opt-out
branch: add --dry-run for --delete-merged
Documentation/config/branch.adoc | 7 +
Documentation/git-branch.adoc | 47 ++++-
builtin/branch.c | 247 ++++++++++++++++++++++---
ref-filter.c | 70 +++++++
ref-filter.h | 10 +
t/t3200-branch.sh | 308 +++++++++++++++++++++++++++++++
6 files changed, 661 insertions(+), 28 deletions(-)
base-commit: 8d96f09
Submitted-As: https://lore.kernel.org/git/pull.2285.v17.git.git.1782113388.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.git.git.1777671337839.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v2.git.git.1777919250.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v3.git.git.1777965747.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v4.git.git.1778009038.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v5.git.git.1778482708.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v6.git.git.1778492691.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v7.git.git.1778574229.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v8.git.git.1778605658.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v9.git.git.1778700883.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v10.git.git.1779403204.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v11.git.git.1779449498.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v12.git.git.1780477479.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v13.git.git.1780684553.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v14.git.git.1780999917.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v15.git.git.1781542042.gitgitgadget@gmail.com
In-Reply-To: https://lore.kernel.org/git/pull.2285.v16.git.git.1781810729.gitgitgadget@gmail.com
PreviousNext