Skip to content

Consolidate reachability logic #10

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Closed
derrickstolee wants to merge 18 commits into from
Closed

Consolidate reachability logic #10

Changes from 1 commit
Commits
Show all changes
18 commits
Select commit Hold shift + click to select a range
56b7ca5
commit-reach: move walk methods from commit.c
derrickstolee Jun 25, 2018
ca88ec3
commit.h: remove method declarations
derrickstolee Jul 18, 2018
12349f5
commit-reach: move ref_newer from remote.c
derrickstolee Jun 25, 2018
f548989
commit-reach: move commit_contains from ref-filter
derrickstolee Jun 25, 2018
e822fd8
upload-pack: make reachable() more generic
derrickstolee Jun 19, 2018
08dcd4e
upload-pack: refactor ok_to_give_up()
derrickstolee Jun 19, 2018
a71ec7f
upload-pack: generalize commit date cutoff
derrickstolee Jul 12, 2018
aa96c80
commit-reach: move can_all_from_reach_with_flags
derrickstolee Jul 12, 2018
2da4fe8
test-reach: create new test tool for ref_newer
derrickstolee Jul 13, 2018
10bda49
test-reach: test in_merge_bases
derrickstolee Jul 13, 2018
9ab9511
test-reach: test is_descendant_of
derrickstolee Jul 13, 2018
d3dfbfc
test-reach: test get_merge_bases_many
derrickstolee Jul 13, 2018
91a6297
test-reach: test reduce_heads
derrickstolee Jul 13, 2018
0557fed
test-reach: test can_all_from_reach_with_flags
derrickstolee Jul 13, 2018
02d0386
test-reach: test commit_contains
derrickstolee Jul 18, 2018
3b44044
commit-reach: replace ref_newer logic
derrickstolee Jul 13, 2018
ae6fc62
commit-reach: make can_all_from_reach... linear
derrickstolee Jun 28, 2018
f40f6f4
commit-reach: use can_all_from_reach
derrickstolee Jul 13, 2018
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
Prev Previous commit
Next Next commit
commit-reach: replace ref_newer logic 
The ref_newer method is used by 'git push' to check if a force-push is
required. This method does not use any kind of cutoff when walking, so
in the case of a force-push will walk all reachable commits.

The is_descendant_of method already uses paint_down_to_common along with
cutoffs. By translating the ref_newer arguments into the commit and
commit_list required by is_descendant_of, we can have one fewer commit
walk and also improve our performance!

For a copy of the Linux repository, 'test-tool reach ref_newer' presents
the following improvements with the specified input. In the case that
ref_newer returns 1, there is no improvement. The improvement is in the
second case where ref_newer returns 0.

Input:
A:v4.9
B:v3.19

Before: 0.09 s
 After: 0.09 s

To test the negative case, add a new commit with parent v3.19,
regenerate the commit-graph, and then run with B pointing at that
commit.

Before: 0.43 s
 After: 0.09 s

Signed-off-by: Derrick Stolee <[email protected]>
  • Loading branch information
@derrickstolee
derrickstolee committed Jul 20, 2018
commit 3b4404433b0310fe9d869e60348e0c0b030b1e57
26 changes: 3 additions & 23 deletions commit-reach.c
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -366,20 +366,11 @@ void reduce_heads_replace(struct commit_list **heads)
*heads = result;
}

static void unmark_and_free(struct commit_list *list, unsigned int mark)
{
while (list) {
struct commit *commit = pop_commit(&list);
commit->object.flags &= ~mark;
}
}

int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
{
struct object *o;
struct commit *old_commit, *new_commit;
struct commit_list *list, *used;
int found = 0;
struct commit_list *old_commit_list = NULL;

/*
* Both new_commit and old_commit must be commit-ish and new_commit is descendant of
Expand All @@ -400,19 +391,8 @@ int ref_newer(const struct object_id *new_oid, const struct object_id *old_oid)
if (parse_commit(new_commit) < 0)
return 0;

used = list = NULL;
commit_list_insert(new_commit, &list);
while (list) {
new_commit = pop_most_recent_commit(&list, TMP_MARK);
commit_list_insert(new_commit, &used);
if (new_commit == old_commit) {
found = 1;
break;
}
}
unmark_and_free(list, TMP_MARK);
unmark_and_free(used, TMP_MARK);
return found;
commit_list_insert(old_commit, &old_commit_list);
return is_descendant_of(new_commit, old_commit_list);
}

/*
Expand Down