[PATCH v2 00/18] Consolidate reachability logic

There are many places in Git that use a commit walk to determine reachability between commits and/or refs. A lot of this logic is duplicated.

I wanted to achieve the following:

Consolidate several different commit walks into one file Reduce duplicate reachability logic Increase testability (correctness and performance) Improve performance of reachability queries My approach is mostly in three parts:

I. Move code to a new commit-reach.c file. II. Add a 'test-tool reach' command to test these methods directly. III. Modify the logic by improving performance and calling methods with similar logic but different prototypes.

The 'test-tool reach' command is helpful to make sure I don't break anything as I change the logic, but also so I can test methods that are normally only exposed by other more complicated commands. For instance, ref_newer() is part of 'git push -f' and ok_to_give_up() is buried deep within fetch negotiation. Both of these methods have some problematic performance issues that are corrected by this series. As I discovered them, it was clear that it would be better to consolidate walk logic instead of discovering a new walk in another file hidden somewhere.

For the ok_to_give_up() method, I refactored the method so I could pull the logic out of the depths of fetch negotiation. In the commit "commit-reach: make can_all_from_reach... linear" I discuss how the existing algorithm is quadratic and how we can make it linear. Also, we can use heuristic knowledge about the shape of the commit graph and the usual haves/wants to get some extra performance bonus. (The heuristic is to do a DFS with first-parents first, and stop on first found result. We expect haves/wants to include ref tips, which typically have their previous values in their first-parent history.)

One major difference in this series versus the RFC is that I added a new method 'generation_numbers_enabled()' to detect if we have a commit-graph file with non-zero generation numbers. Using can_all_from_reach in is_descendant_of is only faster if we have generation numbers as a cutoff.

V2 Update: The biggest material change in this version is that we drop the method declarations from commit.h, which requires adding a lot of references to commit-reach.h across the codebase. This change is in a commit on its own. In addition, we have the following smaller changes:

* Use 'unsigned int' for the flag variables.

* Properly align the here-doc test input data.

* Use single rev-parse commands in test output, and pipe the OIDs through 'sort'

* Check output of parse_commit()

* Update flag documentation in object.h

* Add tests for commit_contains() including both algorithms.

* Reduce size of "mixed-mode" commit-graph to ensure we start commit walks
  'above' the graph and then walk into the commits with generation numbers.

Thanks, -Stolee

This series is based on jt/commit-graph-per-object-store

Derrick Stolee (18):
  commit-reach: move walk methods from commit.c
  commit.h: remove method declarations
  commit-reach: move ref_newer from remote.c
  commit-reach: move commit_contains from ref-filter
  upload-pack: make reachable() more generic
  upload-pack: refactor ok_to_give_up()
  upload-pack: generalize commit date cutoff
  commit-reach: move can_all_from_reach_with_flags
  test-reach: create new test tool for ref_newer
  test-reach: test in_merge_bases
  test-reach: test is_descendant_of
  test-reach: test get_merge_bases_many
  test-reach: test reduce_heads
  test-reach: test can_all_from_reach_with_flags
  test-reach: test commit_contains
  commit-reach: replace ref_newer logic
  commit-reach: make can_all_from_reach... linear
  commit-reach: use can_all_from_reach

 Makefile                |   2 +
 bisect.c                |   1 +
 builtin/branch.c        |   1 +
 builtin/commit.c        |   1 +
 builtin/fetch.c         |   1 +
 builtin/fmt-merge-msg.c |   1 +
 builtin/log.c           |   1 +
 builtin/merge-base.c    |   1 +
 builtin/merge.c         |   1 +
 builtin/pull.c          |   1 +
 builtin/receive-pack.c  |   1 +
 builtin/remote.c        |   1 +
 builtin/rev-parse.c     |   1 +
 commit-graph.c          |  18 ++
 commit-graph.h          |   6 +
 commit-reach.c          | 662 ++++++++++++++++++++++++++++++++++++++++
 commit-reach.h          |  77 +++++
 commit.c                | 358 ----------------------
 commit.h                |  29 --
 fast-import.c           |   1 +
 http-push.c             |   2 +-
 merge-recursive.c       |   1 +
 notes-merge.c           |   1 +
 object.h                |   4 +-
 pack-bitmap-write.c     |   1 +
 ref-filter.c            | 146 +--------
 remote.c                |  50 +--
 remote.h                |   1 -
 revision.c              |   1 +
 sequencer.c             |   1 +
 sha1-name.c             |   1 +
 shallow.c               |   1 +
 submodule.c             |   1 +
 t/helper/test-reach.c   | 130 ++++++++
 t/helper/test-tool.c    |   1 +
 t/helper/test-tool.h    |   1 +
 t/t6600-test-reach.sh   | 242 +++++++++++++++
 upload-pack.c           |  58 +---
 38 files changed, 1177 insertions(+), 631 deletions(-)
 create mode 100644 commit-reach.c
 create mode 100644 commit-reach.h
 create mode 100644 t/helper/test-reach.c
 create mode 100755 t/t6600-test-reach.sh