[PATCH v4 00/28] Support reftable ref backend for Git

This is a version of the reftable series queued on top of my just-re-rolled fixes to the refs APIs, which it can make use of. For the base topics see:

    https://lore.kernel.org/git/cover-v5-00.13-00000000000-20210823T113115Z-avarab@gmail.com/
    https://lore.kernel.org/git/cover-v10-0.8-00000000000-20210823T114712Z-avarab@gmail.com/

For Han-Wen's v3 of this see: https://lore.kernel.org/git/pull.1054.v3.git.git.1629207607.gitgitgadget@gmail.com/

I've got no desire to take over the reftable topic in its entirety, but think given the rationale in https://lore.kernel.org/git/877dgch4rn.fsf@evledraar.gmail.com/ (summarized in https://lore.kernel.org/git/87y28sfokk.fsf@evledraar.gmail.com/) that having the refs API fixes I noted above wait on the still-unstable reftable doesn't make sense.

I think that plan came about due to my non-responsiveness for the past couple of weeks (I was on vacation).

So I'm submitting this so Junio has something to pick up and put in hn/reftable which compiles and passes tests, this should clear up the outstanding issues in the "seen" branch.

As the range-diff shows the only changes are the addition of three new patches at the end. Those patches clearly need to be squashed into their respective preceding commits.

I'll let Han-Wen deal with that squashing in a presumed future v5 of this, assuming of course that Junio's happy with the plan of basing hn/reftable on the refs API fixes above.

I'm not sure that the fix I have in 27/28 is the right one, perhaps we've already got information about what the tip OID of the refname is at that point in git_reftable_reflog_expire() via some API I missed, but that fix works, and is clearly more correct than the outstanding segfault.

Han-Wen Nienhuys (24):
  hash.h: provide constants for the hash IDs
  init-db: set the_repository->hash_algo early on
  reftable: RFC: add LICENSE
  reftable: add error related functionality
  reftable: utility functions
  reftable: add blocksource, an abstraction for random access reads
  reftable: (de)serialization for the polymorphic record type.
  Provide zlib's uncompress2 from compat/zlib-compat.c
  reftable: reading/writing blocks
  reftable: a generic binary tree implementation
  reftable: write reftable files
  reftable: generic interface to tables
  reftable: read reftable files
  reftable: reftable file level tests
  reftable: add a heap-based priority queue for reftable records
  reftable: add merged table view
  reftable: implement refname validation
  reftable: implement stack, a mutable database of reftable files.
  reftable: add dump utility
  refs: RFC: Reftable support for git-core
  Add "test-tool dump-reftable" command.
  t1301: document what needs to be done for reftable
  t1401,t2011: parameterize HEAD.lock for REFFILES
  t1404: annotate test cases with REFFILES

SZEDER Gábor (1):
  git-prompt: prepare for reftable refs backend

Ævar Arnfjörð Bjarmason (3):
  reftable: fixup for new base topic 1/3
  reftable: fixup for new base topic 2/3
  reftable: fixup for new base topic 3/3

 Documentation/config/extensions.txt           |    9 +
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   54 +-
 builtin/clone.c                               |    5 +-
 builtin/init-db.c                             |   60 +-
 builtin/stash.c                               |    8 +-
 builtin/worktree.c                            |   27 +-
 cache.h                                       |    8 +-
 ci/lib.sh                                     |    1 +
 compat/.gitattributes                         |    1 +
 compat/zlib-uncompress2.c                     |   92 +
 config.mak.uname                              |    3 +-
 configure.ac                                  |   13 +
 contrib/buildsystems/CMakeLists.txt           |   14 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 contrib/completion/git-prompt.sh              |    7 +-
 contrib/workdir/git-new-workdir               |    2 +-
 hash.h                                        |    6 +
 object-file.c                                 |    7 +-
 refs.c                                        |   26 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1687 +++++++++++++++++
 reftable/LICENSE                              |   31 +
 reftable/basics.c                             |  128 ++
 reftable/basics.h                             |   60 +
 reftable/basics_test.c                        |   98 +
 reftable/block.c                              |  448 +++++
 reftable/block.h                              |  127 ++
 reftable/block_test.c                         |  120 ++
 reftable/blocksource.c                        |  148 ++
 reftable/blocksource.h                        |   22 +
 reftable/constants.h                          |   21 +
 reftable/dump.c                               |  107 ++
 reftable/error.c                              |   41 +
 reftable/generic.c                            |  169 ++
 reftable/generic.h                            |   32 +
 reftable/iter.c                               |  194 ++
 reftable/iter.h                               |   69 +
 reftable/merged.c                             |  362 ++++
 reftable/merged.h                             |   35 +
 reftable/merged_test.c                        |  292 +++
 reftable/pq.c                                 |  115 ++
 reftable/pq.h                                 |   32 +
 reftable/pq_test.c                            |   72 +
 reftable/publicbasics.c                       |   58 +
 reftable/reader.c                             |  801 ++++++++
 reftable/reader.h                             |   66 +
 reftable/readwrite_test.c                     |  652 +++++++
 reftable/record.c                             | 1212 ++++++++++++
 reftable/record.h                             |  139 ++
 reftable/record_test.c                        |  412 ++++
 reftable/refname.c                            |  209 ++
 reftable/refname.h                            |   29 +
 reftable/refname_test.c                       |  102 +
 reftable/reftable-blocksource.h               |   49 +
 reftable/reftable-error.h                     |   62 +
 reftable/reftable-generic.h                   |   47 +
 reftable/reftable-iterator.h                  |   39 +
 reftable/reftable-malloc.h                    |   18 +
 reftable/reftable-merged.h                    |   72 +
 reftable/reftable-reader.h                    |  101 +
 reftable/reftable-record.h                    |  114 ++
 reftable/reftable-stack.h                     |  128 ++
 reftable/reftable-tests.h                     |   23 +
 reftable/reftable-writer.h                    |  148 ++
 reftable/reftable.c                           |  115 ++
 reftable/stack.c                              | 1396 ++++++++++++++
 reftable/stack.h                              |   41 +
 reftable/stack_test.c                         |  948 +++++++++
 reftable/system.h                             |   24 +
 reftable/test_framework.c                     |   23 +
 reftable/test_framework.h                     |   53 +
 reftable/tree.c                               |   63 +
 reftable/tree.h                               |   34 +
 reftable/tree_test.c                          |   61 +
 reftable/writer.c                             |  690 +++++++
 reftable/writer.h                             |   50 +
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |    8 +
 t/helper/test-reftable.c                      |   21 +
 t/helper/test-tool.c                          |    4 +-
 t/helper/test-tool.h                          |    2 +
 t/t0031-reftable.sh                           |  316 +++
 t/t0032-reftable-unittest.sh                  |   15 +
 t/t1301-shared-repo.sh                        |    8 +-
 t/t1401-symbolic-ref.sh                       |   11 +-
 t/t1404-update-ref-errors.sh                  |   56 +-
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1450-fsck.sh                               |    6 +
 t/t2011-checkout-invalid-head.sh              |   11 +-
 t/t3210-pack-refs.sh                          |    6 +
 t/test-lib.sh                                 |    7 +-
 94 files changed, 13174 insertions(+), 62 deletions(-)
 create mode 100644 compat/.gitattributes
 create mode 100644 compat/zlib-uncompress2.c
 create mode 100644 refs/reftable-backend.c
 create mode 100644 reftable/LICENSE
 create mode 100644 reftable/basics.c
 create mode 100644 reftable/basics.h
 create mode 100644 reftable/basics_test.c
 create mode 100644 reftable/block.c
 create mode 100644 reftable/block.h
 create mode 100644 reftable/block_test.c
 create mode 100644 reftable/blocksource.c
 create mode 100644 reftable/blocksource.h
 create mode 100644 reftable/constants.h
 create mode 100644 reftable/dump.c
 create mode 100644 reftable/error.c
 create mode 100644 reftable/generic.c
 create mode 100644 reftable/generic.h
 create mode 100644 reftable/iter.c
 create mode 100644 reftable/iter.h
 create mode 100644 reftable/merged.c
 create mode 100644 reftable/merged.h
 create mode 100644 reftable/merged_test.c
 create mode 100644 reftable/pq.c
 create mode 100644 reftable/pq.h
 create mode 100644 reftable/pq_test.c
 create mode 100644 reftable/publicbasics.c
 create mode 100644 reftable/reader.c
 create mode 100644 reftable/reader.h
 create mode 100644 reftable/readwrite_test.c
 create mode 100644 reftable/record.c
 create mode 100644 reftable/record.h
 create mode 100644 reftable/record_test.c
 create mode 100644 reftable/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/refname_test.c
 create mode 100644 reftable/reftable-blocksource.h
 create mode 100644 reftable/reftable-error.h
 create mode 100644 reftable/reftable-generic.h
 create mode 100644 reftable/reftable-iterator.h
 create mode 100644 reftable/reftable-malloc.h
 create mode 100644 reftable/reftable-merged.h
 create mode 100644 reftable/reftable-reader.h
 create mode 100644 reftable/reftable-record.h
 create mode 100644 reftable/reftable-stack.h
 create mode 100644 reftable/reftable-tests.h
 create mode 100644 reftable/reftable-writer.h
 create mode 100644 reftable/reftable.c
 create mode 100644 reftable/stack.c
 create mode 100644 reftable/stack.h
 create mode 100644 reftable/stack_test.c
 create mode 100644 reftable/system.h
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h
 create mode 100644 reftable/tree.c
 create mode 100644 reftable/tree.h
 create mode 100644 reftable/tree_test.c
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 t/helper/test-reftable.c
 create mode 100755 t/t0031-reftable.sh
 create mode 100755 t/t0032-reftable-unittest.sh

Range-diff against v3:
 1:  cad3c4835a2 =  1:  295ccff312f hash.h: provide constants for the hash IDs
 2:  97aba3ae406 =  2:  2fb0fb20282 init-db: set the_repository->hash_algo early on
 3:  fca162dd676 =  3:  6cf0b244fc5 reftable: RFC: add LICENSE
 4:  44923074a5a =  4:  a0686356c11 reftable: add error related functionality
 5:  2f2beb70078 =  5:  23ceb2e5723 reftable: utility functions
 6:  79d4a23764d =  6:  9429aaf7c76 reftable: add blocksource, an abstraction for random access reads
 7:  2c143c75cd5 =  7:  f4cebccb9e0 reftable: (de)serialization for the polymorphic record type.
 8:  d92338467d6 =  8:  e2f2729443b Provide zlib's uncompress2 from compat/zlib-compat.c
 9:  74ac0b135fa =  9:  9d468fbdd07 reftable: reading/writing blocks
10:  a2219670079 = 10:  7d8b8e3b76a reftable: a generic binary tree implementation
11:  ac3063fd08c = 11:  7ec422318eb reftable: write reftable files
12:  e0f3476555e = 12:  df4fae30ceb reftable: generic interface to tables
13:  f1fe338f67e = 13:  7e8a613206f reftable: read reftable files
14:  7da9a85c1db = 14:  ebe55aa6295 reftable: reftable file level tests
15:  953590034a8 = 15:  a9880fc1a10 reftable: add a heap-based priority queue for reftable records
16:  64fe3c8edc5 = 16:  c073be56a6b reftable: add merged table view
17:  acb0d435a20 = 17:  092b9715672 reftable: implement refname validation
18:  764d45fccd4 = 18:  374c22efbd9 reftable: implement stack, a mutable database of reftable files.
19:  88dbab683dc = 19:  007c9359f42 reftable: add dump utility
20:  3d57f7c4430 = 20:  8f948c0b257 refs: RFC: Reftable support for git-core
21:  460658a13cb = 21:  443bdebfb5d git-prompt: prepare for reftable refs backend
22:  b305fcd49f1 = 22:  f76e7a7bd10 Add "test-tool dump-reftable" command.
23:  a44956d7b08 = 23:  6b62a8c52ae t1301: document what needs to be done for reftable
24:  f0b7b1e2380 = 24:  c926f1526aa t1401,t2011: parameterize HEAD.lock for REFFILES
25:  3110d6e6758 = 25:  0b3db9fc2d6 t1404: annotate test cases with REFFILES
 -:  ----------- > 26:  dde80a982c1 reftable: fixup for new base topic 1/3
 -:  ----------- > 27:  c4f9fb42d9e reftable: fixup for new base topic 2/3
 -:  ----------- > 28:  c863b03201c reftable: fixup for new base topic 3/3