user/sven/git.git/commit-reach.c, branch v2.26.0-rc2

commit-graph: fix writing first commit-graph during fetch

2019-10-25T02:19:16Z

The previous commit includes a failing test for an issue around fetch.writeCommitGraph and fetching in a repo with a submodule. Here, we fix that bug and set the test to "test_expect_success". The problem arises with this set of commands when the remote repo at has a submodule. Note that --recurse-submodules is not needed to demonstrate the bug. $ git clone test $ cd test $ git -c fetch.writeCommitGraph=true fetch origin Computing commit graph generation numbers: 100% (12/12), done. BUG: commit-graph.c:886: missing parent for commit Aborted (core dumped) As an initial fix, I converted the code in builtin/fetch.c that calls write_commit_graph_reachable() to instead launch a "git commit-graph write --reachable --split" process. That code worked, but is not how we want the feature to work long-term. That test did demonstrate that the issue must be something to do with internal state of the 'git fetch' process. The write_commit_graph() method in commit-graph.c ensures the commits we plan to write are "closed under reachability" using close_reachable(). This method walks from the input commits, and uses the UNINTERESTING flag to mark which commits have already been visited. This allows the walk to take O(N) time, where N is the number of commits, instead of O(P) time, where P is the number of paths. (The number of paths can be exponential in the number of commits.) However, the UNINTERESTING flag is used in lots of places in the codebase. This flag usually means some barrier to stop a commit walk, such as in revision-walking to compare histories. It is not often cleared after the walk completes because the starting points of those walks do not have the UNINTERESTING flag, and clear_commit_marks() would stop immediately. This is happening during a 'git fetch' call with a remote. The fetch negotiation is comparing the remote refs with the local refs and marking some commits as UNINTERESTING. I tested running clear_commit_marks_many() to clear the UNINTERESTING flag inside close_reachable(), but the tips did not have the flag, so that did nothing. It turns out that the calculate_changed_submodule_paths() method is at fault. Thanks, Peff, for pointing out this detail! More specifically, for each submodule, the collect_changed_submodules() runs a revision walk to essentially do file-history on the list of submodules. That revision walk marks commits UNININTERESTING if they are simplified away by not changing the submodule. Instead, I finally arrived on the conclusion that I should use a flag that is not used in any other part of the code. In commit-reach.c, a number of flags were defined for commit walk algorithms. The REACHABLE flag seemed like it made the most sense, and it seems it was not actually used in the file. The REACHABLE flag was used in early versions of commit-reach.c, but was removed by 4fbcca4 (commit-reach: make can_all_from_reach... linear, 2018-07-20). Add the REACHABLE flag to commit-graph.c and use it instead of UNINTERESTING in close_reachable(). This fixes the bug in manual testing. Reported-by: Johannes Schindelin Helped-by: Jeff King Helped-by: Szeder Gábor Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Merge branch 'sb/more-repo-in-api'

2019-02-05T22:26:09Z

The in-core repository instances are passed through more codepaths. * sb/more-repo-in-api: (23 commits) t/helper/test-repository: celebrate independence from the_repository path.h: make REPO_GIT_PATH_FUNC repository agnostic commit: prepare free_commit_buffer and release_commit_memory for any repo commit-graph: convert remaining functions to handle any repo submodule: don't add submodule as odb for push submodule: use submodule repos for object lookup pretty: prepare format_commit_message to handle arbitrary repositories commit: prepare logmsg_reencode to handle arbitrary repositories commit: prepare repo_unuse_commit_buffer to handle any repo commit: prepare get_commit_buffer to handle any repo commit-reach: prepare in_merge_bases[_many] to handle any repo commit-reach: prepare get_merge_bases to handle any repo commit-reach.c: allow get_merge_bases_many_0 to handle any repo commit-reach.c: allow remove_redundant to handle any repo commit-reach.c: allow merge_bases_many to handle any repo commit-reach.c: allow paint_down_to_common to handle any repo commit: allow parse_commit* to handle any repo object: parse_object to honor its repository argument object-store: prepare has_{sha1, object}_file to handle any repo object-store: prepare read_object_file to deal with any repo ...

commit-reach: prepare in_merge_bases[_many] to handle any repo

2018-11-14T08:22:40Z

Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

commit-reach: prepare get_merge_bases to handle any repo

2018-11-14T08:22:40Z

Similarly to previous patches, the get_merge_base functions are used often in the code base, which makes migrating them hard. Implement the new functions, prefixed with 'repo_' and hide the old functions behind a wrapper macro. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

commit-reach.c: allow get_merge_bases_many_0 to handle any repo

2018-11-14T08:22:40Z

Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

commit-reach.c: allow remove_redundant to handle any repo

2018-11-14T08:22:40Z

Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

commit-reach.c: allow merge_bases_many to handle any repo

2018-11-14T08:22:40Z

Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

commit-reach.c: allow paint_down_to_common to handle any repo

2018-11-14T08:22:40Z

As the function is file local and not widely used, migrate it all at once. Signed-off-by: Stefan Beller Signed-off-by: Junio C Hamano

commit-reach: implement get_reachable_subset

2018-11-02T15:12:06Z

The existing reachability algorithms in commit-reach.c focus on finding merge-bases or determining if all commits in a set X can reach at least one commit in a set Y. However, for two commits sets X and Y, we may also care about which commits in Y are reachable from at least one commit in X. Implement get_reachable_subset() which answers this question. Given two arrays of commits, 'from' and 'to', return a commit_list with every commit from the 'to' array that is reachable from at least one commit in the 'from' array. The algorithm is a simple walk starting at the 'from' commits, using the PARENT2 flag to indicate "this commit has already been added to the walk queue". By marking the 'to' commits with the PARENT1 flag, we can determine when we see a commit from the 'to' array. We remove the PARENT1 flag as we add that commit to the result list to avoid duplicates. The order of the resulting list is a reverse of the order that the commits are discovered in the walk. There are a couple shortcuts to avoid walking more than we need: 1. We determine the minimum generation number of commits in the 'to' array. We do not walk commits with generation number below this minimum. 2. We count how many distinct commits are in the 'to' array, and decrement this count when we discover a 'to' commit during the walk. If this number reaches zero, then we can terminate the walk. Tests will be added using the 'test-tool reach' helper in a subsequent commit. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Merge branch 'ds/reachable'

2018-10-30T06:43:47Z

Trivial bugfix. * ds/reachable: commit-reach: fix cast in compare_commits_by_gen()