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

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()

commit-reach: fix cast in compare_commits_by_gen()

2018-10-22T22:57:47Z

The elements of the array to be sorted are commit pointers, so the comparison function gets handed references to these pointers, not pointers to commit objects. Cast to the right type and dereference once to correctly get the commit reference. Found using Clang's ASan and t5500. Signed-off-by: Rene Scharfe Signed-off-by: Junio C Hamano

commit-reach: fix first-parent heuristic

2018-10-19T02:30:45Z

The algorithm in can_all_from_reach_with_flags() performs a depth- first-search, terminated by generation number, intending to use a hueristic that "important" commits are found in the first-parent history. This heuristic is valuable in scenarios like fetch negotiation. However, there is a problem! After the search finds a target commit, it should pop all commits off the stack and mark them as "can reach". This logic is incorrect, so the algorithm instead walks all reachable commits above the generation-number cutoff. The existing algorithm is still an improvement over the previous algorithm, as the worst-case complexity went from quadratic to linear. The performance measurement at the time was good, but not dramatic. By fixing this heuristic, we reduce the number of walked commits. We can also re-run the performance tests from commit 4fbcca4e "commit-reach: make can_all_from_reach... linear". Performance was measured on the Linux repository using 'test-tool reach can_all_from_reach'. The input included rows seeded by tag values. The "small" case included X-rows as v4.[0-9]* and Y-rows as v3.[0-9]*. This mimics a (very large) fetch that says "I have all major v3 releases and want all major v4 releases." The "large" case included X-rows as "v4.*" and Y-rows as "v3.*". This adds all release-candidate tags to the set, which does not greatly increase the number of objects that are considered, but does increase the number of 'from' commits, demonstrating the quadratic nature of the previous code. Small Case: 4fbcca4e~1: 0.85 s 4fbcca4e: 0.26 s (num_walked: 1,011,035) HEAD: 0.14 s (num_walked: 8,601) Large Case: 4fbcca4e~1: 24.0 s 4fbcca4e: 0.12 s (num_walked: 503,925) HEAD: 0.06 s (num_walked: 217,243) Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Merge branch 'jk/oideq-hasheq-cleanup'

2018-10-16T07:16:08Z

Code clean-up. * jk/oideq-hasheq-cleanup: more oideq/hasheq conversions

Merge branch 'ds/reachable-final-cleanup'

2018-10-16T07:16:04Z

Code already in 'master' is further cleaned-up by this patch. * ds/reachable-final-cleanup: commit-reach: cleanups in can_all_from_reach...

more oideq/hasheq conversions

2018-10-04T10:42:48Z

We added faster equality-comparison functions for hashes in 14438c4497 (introduce hasheq() and oideq(), 2018-08-28). A few topics were in-flight at the time, and can now be converted. This covers all spots found by "make coccicheck" in master (the coccicheck results were tweaked by hand for style). Signed-off-by: Jeff King Signed-off-by: Junio C Hamano

commit-reach: cleanups in can_all_from_reach...

2018-09-25T18:07:02Z

Due to a regression introduced by 4fbcca4e "commit-reach: make can_all_from_reach... linear" the series including b67f6b26 "commit-reach: properly peel tags" was merged to master quickly. There were a few more cleanups left to apply in the series, which are included by this change: 1. Clean up a comment that is in the incorrect style. 2. Replace multiple calls to clear_commit_marks() with one call to clear_commit_marks_many(). Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano

Merge branch 'ds/reachable'

2018-09-24T17:30:52Z

Recent update broke the reachability algorithm when refs (e.g. tags) that point at objects that are not commit were involved, which has been fixed. * ds/reachable: commit-reach: fix memory and flag leaks commit-reach: properly peel tags

commit-reach: fix memory and flag leaks

2018-09-21T18:36:29Z

The can_all_from_reach_with_flag() method uses 'assign_flag' as a value we can use to mark objects temporarily during our commit walk. The intent is that these flags are removed from all objects before returning. However, this is not the case. The 'from' array could also contain objects that are not commits, and we mark those objects with 'assign_flag'. Add a loop to the 'cleanup' section that removes these markers. Also, we forgot to free() the memory for 'list', so add that to the 'cleanup' section. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano