From: Derrick Stolee Date: Tue, 1 May 2018 12:47:11 +0000 (+0000) Subject: commit: use generations in paint_down_to_common() X-Git-Tag: v2.19.0-rc0~192^2~8 X-Git-Url: https://git.lorimer.id.au/gitweb.git/diff_plain/3afc679b3c13d99e4f02bceb686f11d51576d3ae?hp=3afc679b3c13d99e4f02bceb686f11d51576d3ae commit: use generations in paint_down_to_common() Define compare_commits_by_gen_then_commit_date(), which uses generation numbers as a primary comparison and commit date to break ties (or as a comparison when both commits do not have computed generation numbers). Since the commit-graph file is closed under reachability, we know that all commits in the file have generation at most GENERATION_NUMBER_MAX which is less than GENERATION_NUMBER_INFINITY. This change does not affect the number of commits that are walked during the execution of paint_down_to_common(), only the order that those commits are inspected. In the case that commit dates violate topological order (i.e. a parent is "newer" than a child), the previous code could walk a commit twice: if a commit is reached with the PARENT1 bit, but later is re-visited with the PARENT2 bit, then that PARENT2 bit must be propagated to its parents. Using generation numbers avoids this extra effort, even if it is somewhat rare. Signed-off-by: Derrick Stolee Signed-off-by: Junio C Hamano ---