commit-reach: remove get_reachable_subset()#2144
Open
spkrka wants to merge 1 commit into
Open
Conversation
get_reachable_subset() and tips_reachable_from_bases() answer the same question: given a set of bases and a set of tips, which tips are reachable from at least one base? get_reachable_subset() was introduced in fcb2c07 (2018-11-02) for add_missing_tags() in remote.c. tips_reachable_from_bases() was added in cbfe360 (2023-03-20) as part of the ahead-behind series. The two were never consolidated. With a commit-graph, tips_reachable_from_bases() can have an edge: its DFS raises the generation floor as lower targets are found, pruning more aggressively than the static floor in get_reachable_subset(). Without generation numbers, some edge cases may be slower with DFS instead of BFS since the date-ordered prio_queue naturally stays near the top of the graph, but this should not matter in practice -- worst case both visit the full graph down from the bases. The flag in remote.c changes from 1 (bit 0) to TMP_MARK (bit 4) because tips_reachable_from_bases() uses SEEN (bit 0) internally. TMP_MARK is already used for deduplication earlier in the same function and is cleared before the reachability check. Signed-off-by: Kristofer Karlsson <krka@spotify.com>
Author
|
/submit |
|
Submitted as pull.2144.git.1781033285419.gitgitgadget@gmail.com To fetch this version into To fetch this version to local tag |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
1 participant
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
This removes get_reachable_subset() and converts its only caller
to use tips_reachable_from_bases() directly. Both answer the same
category-2 reachability question ("which tips are reachable from
these bases?") but were introduced years apart and never consolidated.
On the no-commit-graph tradeoff: without generation numbers, the
date-ordered BFS in get_reachable_subset() can be more disciplined
than DFS since it naturally stays near the top of the graph. But
this only matters for repositories that are both large enough for
the difference to be measurable and missing a commit-graph -- a
combination that would already struggle for many other reasons.
The fix there is to enable the commit-graph, not to maintain two
implementations of the same reachability query.
Notes for reviewers:
The flag in remote.c changes from 1 to TMP_MARK because
tips_reachable_from_bases() uses SEEN (bit 0) internally.
TMP_MARK is already used earlier in the same function and
is cleared before the reachability block.
The sent_tips array is converted to a commit_list to match
the tips_reachable_from_bases() API. This is O(n) list-node
allocations, negligible compared to the graph walk.
Test helper and test names rename from get_reachable_subset
to tips_reachable_from_bases to match the function being
exercised.
cc: Derrick Stolee stolee@gmail.com