git/commit-reach.c, branch v2.51.2

commit-reach: use `size_t` to track indices when computing merge bases

2024-12-27T16:12:40Z

The functions `repo_get_merge_bases_many()` and friends accepts an array of commits as well as a parameter that indicates how large that array is. This parameter is using a signed integer, which leads to a couple of warnings with -Wsign-compare. Refactor the code to use `size_t` to track indices instead and adapt callers accordingly. While most callers are trivial, there are two callers that require a bit more scrutiny: - builtin/merge-base.c:show_merge_base() subtracts `1` from the `rev_nr` before calling `repo_get_merge_bases_many_dirty()`, so if the variable was `0` it would wrap. This code is fine though because its only caller will execute that code only when `argc >= 2`, and it follows that `rev_nr >= 2`, as well. - bisect.ccheck_merge_bases() similarly subtracts `1` from `rev_nr`. Again, there is only a single caller that populates `rev_nr` with `good_revs.nr`. And because a bisection always requires at least one good revision it follws that `rev_nr >= 1`. Mark the file as -Wsign-compare-clean. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

commit-reach: use `size_t` to track indices in `get_reachable_subset()`

2024-12-27T16:11:45Z

Similar as with the preceding commit, adapt `get_reachable_subset()` so that it tracks array indices via `size_t` instead of using signed integers to fix a couple of -Wsign-compare warnings. Adapt callers accordingly. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

commit-reach: use `size_t` to track indices in `remove_redundant()`

2024-12-27T16:11:45Z

The function `remove_redundant()` gets as input an array of commits as well as the size of that array and then drops redundant commits from that array. It then returns either `-1` in case an error occurred, or the new number of items in the array. The function receives and returns these sizes with a signed integer, which causes several warnings with -Wsign-compare. Fix this issue by consistently using `size_t` to track array indices and splitting up the returned value into a returned error code and a separate out pointer for the new computed size. Note that `get_merge_bases_many()` and related functions still track array sizes as a signed integer. This will be fixed in a subsequent commit. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

commit-reach: fix type of `min_commit_date`

2024-12-27T16:11:45Z

The `can_all_from_reach_with_flag()` function accepts a parameter that allows callers to cut off traversal at a specified commit date. This parameter is of type `time_t`, which is a signed type, while we end up comparing it to a commit's `date` field, which is of the unsigned type `timestamp_t`. Fix the parameter to be of type `timestamp_t`. There is only a single caller in "upload-pack.c" that sets this parameter, and that caller knows to pass in a `timestamp_t` already. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

commit-reach: fix index used to loop through unsigned integer

2024-12-27T16:11:15Z

In 62e745ced2 (prio-queue: use size_t rather than int for size, 2024-12-20), we refactored `struct prio_queue` to track the number of contained entries via a `size_t`. While the refactoring adapted one of the users of that variable, it forgot to also adapt "commit-reach.c" accordingly. This was missed because that file has -Wsign-conversion disabled. Fix the issue by using a `size_t` to iterate through entries. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

global: mark code units that generate warnings with `-Wsign-compare`

2024-12-06T11:20:02Z

Mark code units that generate warnings with `-Wsign-compare`. This allows for a structured approach to get rid of all such warnings over time in a way that can be easily measured. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

Merge branch 'ds/for-each-ref-is-base'

2024-08-26T18:32:24Z

'git for-each-ref' learned a new "--format" atom to find the branch that the history leading to a given commit "%(is-base:)" is likely based on. * ds/for-each-ref-is-base: p1500: add is-base performance tests for-each-ref: add 'is-base' token commit: add gentle reference lookup method commit-reach: add get_branch_base_for_tip

commit-reach: add get_branch_base_for_tip

2024-08-14T17:10:05Z

Add a new reachability algorithm that intends to discover (from a heuristic) which branch was used as the starting point for a given commit. Add focused tests using the 'test-tool reach' command. In repositories that use pull requests (or merge requests) to advance one or more "protected" branches, the history of that reference can be recovered by following the first-parent history in most cases. Most are completed using no-fast-forward merges, though squash merges are quite common. Less common is rebase-and-merge, which still validates this assumption. Finally, the case that breaks this assumption is the fast-forward update (with potential rebasing). Even in this case, the previous commit commonly appears in the first-parent history of the branch. Similar assumptions can be made for a topic branch created by a single user with the intention to merge back into another branch. Using 'git commit', 'git merge', and 'git cherry-pick' from HEAD will default to having the first-parent commit be the previous commit at HEAD. This history changes only with commands such as 'git reset' or 'git rebase', where the command names also imply that the branch is starting from a new location. With this movement of branches in mind, the following heuristic is proposed as a way to determine the base branch for a given source branch: Among a list of candidate base branches, select the candidate that minimizes the number of commits in the first-parent history of the source that are not in the first-parent history of the candidate. Prior third-party solutions to this problem have used this optimization criteria, but have relied upon extracting the first-parent history and comparing those lists as tables instead of using commit-graph walks. Given current command-line interface options, this optimization criteria is not easy to detect directly. Even using the command git rev-list --count --first-parent .. does not measure this count, as it uses full reachability from to determine which commits to remove from the range '..'. This may lead to one asking if we should instead be using the full reachability of the candidate and only the first-parent history of the source. This, unfortunately, does not work for repositories that use long-lived branches and automation to merge across those branches. In extremely large repositories, merging into a single trunk may not be feasible. This is usually due to the desired frequency of updates (thousands of engineers doing daily work) combined with the time required to perform a validation build. These factors combine to create significant risk of semantic merge conflicts, leading to build breaks on the trunk. In response, repository maintainers can create a single Level Zero (L0) trunk and multiple Level One (L1) branches. By partitioning the engineers by organization, these engineers may see lower risk of semantic merge conflicts as well as be protected against build breaks in other L1 branches. The key to making this system work is a semi-automated process of merging L1 branches into the L0 trunk and vice-versa. In a large enough organization, these L1 branches may further split into L2 or L3 branches, but the same principles apply for merging across deeper levels. If these automated merges use a typical merge with the second parent bringing in the "new" content, then each L0 and L1 branch can track its previous positions by following first-parent history, which appear as parallel paths (until reaching the first place where the branches diverged). If we also walk to second parents, then the histories overlap significantly and cannot be distinguished except for very-recent changes. For this reason, the first-parent condition should be symmetrical across the base and source branches. Another common case for desiring the result of this optimization method is the use of release branches. When releasing a version of a repository, a branch can be used to track that release. Any updates that are worth fixing in that release can be merged to the release branch and shipped with only the necessary fixes without any new features introduced in the trunk branch. The 'maint-2.' branches represent this pattern in the Git project. The microsoft/git fork uses 'vfs-2..' branches to track the changes that are custom to that fork on top of each upstream Git release 2... This application doesn't need the symmetrical first-parent condition, but the use of first-parent histories does not change the results for these branches. To determine the base branch from a list of candidates, create a new method in commit-reach.c that performs a single* commit-graph walk. The core concept is to walk first-parents starting at the candidate bases and the source, tracking the "best" base to reach a given commit. Use generation numbers to ensure that a commit is walked at most once and all children have been explored before visiting it. When reaching a commit that is reachable from both a base and the source, we will then have a guarantee that this is the closest intersection of first-parent histories. Track the best base to reach that commit and return it as a result. In rare cases involving multiple root commits, the first-parent history of the source may never intersect any of the candidates and thus a null result is returned. * There are up to two walks, since we require all commits to have a computed generation number in order to avoid incorrect results. This is similar to the need for computed generation numbers in ahead_behind() as implemented in fd67d149bde (commit-reach: implement ahead_behind() logic, 2023-03-20). In order to track the "best" base, use a new commit slab that stores an integer. This value defaults to zero upon initialization, so use -1 to track that the source commit can reach this commit and use 'i + 1' to track that the ith base can reach this commit. When multiple bases can reach a commit, minimize the index to break ties. This allows the caller to specify an order to the bases that determines some amount of preference when the heuristic does not result in a unique result. The trickiest part of the integer slab is what happens when reaching a collision among the histories of the bases and the history of the source. This is noticed when viewing the first parent and seeing that it has a slab value that differs in sign (negative or positive). In this case, the collision commit is stored in the method variable 'branch_point' and its slab value is set to -1. The index of the best base (so far) is stored in the method variable 'best_index'. It is possible that there are multiple commits that have the branch_point as its first parent, leading to multiple updates of best_index. The result is determined when 'branch_point' is visited in the commit walk, giving the guarantee that all commits that could reach 'branch_point' were visited. Several interesting cases of collisions and different results are tested in the t6600-test-reach.sh script. Recall that this script also tests the algorithm in three possible states involving the commit-graph file and how many commits are written in the file. This provides some coverage of the need (and lack of need) for the ensure_generations_valid() method. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

commit-reach: fix trivial memory leak when computing reachability

2024-08-01T15:47:38Z

We don't free the local `stack` commit list that we use to compute reachability of multiple commits at once. Do so. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano

global: introduce `USE_THE_REPOSITORY_VARIABLE` macro

2024-06-14T17:26:33Z

Use of the `the_repository` variable is deprecated nowadays, and we slowly but steadily convert the codebase to not use it anymore. Instead, callers should be passing down the repository to work on via parameters. It is hard though to prove that a given code unit does not use this variable anymore. The most trivial case, merely demonstrating that there is no direct use of `the_repository`, is already a bit of a pain during code reviews as the reviewer needs to manually verify claims made by the patch author. The bigger problem though is that we have many interfaces that implicitly rely on `the_repository`. Introduce a new `USE_THE_REPOSITORY_VARIABLE` macro that allows code units to opt into usage of `the_repository`. The intent of this macro is to demonstrate that a certain code unit does not use this variable anymore, and to keep it from new dependencies on it in future changes, be it explicit or implicit For now, the macro only guards `the_repository` itself as well as `the_hash_algo`. There are many more known interfaces where we have an implicit dependency on `the_repository`, but those are not guarded at the current point in time. Over time though, we should start to add guards as required (or even better, just remove them). Define the macro as required in our code units. As expected, most of our code still relies on the global variable. Nearly all of our builtins rely on the variable as there is no way yet to pass `the_repository` to their entry point. For now, declare the macro in "biultin.h" to keep the required changes at least a little bit more contained. Signed-off-by: Patrick Steinhardt Signed-off-by: Junio C Hamano