Subject: [PATCH v6 00/20] reftable library

From: "Han-Wen Nienhuys via GitGitGadget" <[email-masked]>
Date: Mon, 12 Apr 2021 19:25:32 +0000

This splits the giant commit from
https://github.com/gitgitgadget/git/pull/539 into a series of smaller
commits, which build and have unittests.

version 12 Apr 2021:

 * handle cleanup for concurrent access on Windows
 * split up commits further

Based on github.com/hanwen/reftable at
c33a40ad23dd622d8c72139c41a2be1cfa063e5f Add random suffix to table names

Han-Wen Nienhuys (19):
  init-db: set the_repository->hash_algo early on
  reftable: 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.
  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
  Reftable support for git-core
  Add "test-tool dump-reftable" command.

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

 Documentation/config/extensions.txt           |    9 +
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   48 +-
 builtin/clone.c                               |    5 +-
 builtin/init-db.c                             |   76 +-
 builtin/worktree.c                            |   27 +-
 cache.h                                       |    8 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/CMakeLists.txt           |   14 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 contrib/completion/git-prompt.sh              |    7 +-
 refs.c                                        |   27 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1451 +++++++++++++++++
 reftable/.gitattributes                       |    1 +
 reftable/LICENSE                              |   31 +
 reftable/basics.c                             |  128 ++
 reftable/basics.h                             |   60 +
 reftable/basics_test.c                        |   98 ++
 reftable/block.c                              |  440 +++++
 reftable/block.h                              |  127 ++
 reftable/block_test.c                         |  121 ++
 reftable/blocksource.c                        |  148 ++
 reftable/blocksource.h                        |   22 +
 reftable/constants.h                          |   21 +
 reftable/dump.c                               |  213 +++
 reftable/error.c                              |   41 +
 reftable/generic.h                            |   32 +
 reftable/iter.c                               |  197 +++
 reftable/iter.h                               |   67 +
 reftable/merged.c                             |  367 +++++
 reftable/merged.h                             |   35 +
 reftable/merged_test.c                        |  291 ++++
 reftable/pq.c                                 |  115 ++
 reftable/pq.h                                 |   32 +
 reftable/pq_test.c                            |   72 +
 reftable/publicbasics.c                       |   58 +
 reftable/reader.c                             |  773 +++++++++
 reftable/reader.h                             |   66 +
 reftable/record.c                             | 1203 ++++++++++++++
 reftable/record.h                             |  139 ++
 reftable/record_test.c                        |  405 +++++
 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                   |   41 +
 reftable/reftable-iterator.h                  |   39 +
 reftable/reftable-malloc.h                    |   18 +
 reftable/reftable-merged.h                    |   72 +
 reftable/reftable-reader.h                    |   98 ++
 reftable/reftable-record.h                    |  114 ++
 reftable/reftable-stack.h                     |  123 ++
 reftable/reftable-tests.h                     |   23 +
 reftable/reftable-writer.h                    |  147 ++
 reftable/reftable.c                           |  115 ++
 reftable/reftable_test.c                      |  583 +++++++
 reftable/stack.c                              | 1376 ++++++++++++++++
 reftable/stack.h                              |   41 +
 reftable/stack_test.c                         |  928 +++++++++++
 reftable/system.h                             |   32 +
 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                             |  691 ++++++++
 reftable/writer.h                             |   50 +
 reftable/zlib-compat.c                        |   92 ++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |    9 +-
 t/helper/test-reftable.c                      |   21 +
 t/helper/test-tool.c                          |    4 +-
 t/helper/test-tool.h                          |    2 +
 t/t0031-reftable.sh                           |  203 +++
 t/t0032-reftable-unittest.sh                  |   15 +
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1450-fsck.sh                               |    6 +
 t/t3210-pack-refs.sh                          |    6 +
 t/test-lib.sh                                 |    5 +
 83 files changed, 12509 insertions(+), 40 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100644 reftable/.gitattributes
 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.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/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/reftable_test.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 reftable/zlib-compat.c
 create mode 100644 t/helper/test-reftable.c
 create mode 100755 t/t0031-reftable.sh
 create mode 100755 t/t0032-reftable-unittest.sh

base-commit: 89b43f80a514aee58b662ad606e6352e03eaeee4
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-git-847%2Fhanwen%2Flibreftable-v6
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-git-847/hanwen/libreftable-v6
Pull-Request: https://github.com/git/git/pull/847

Range-diff vs v5:

  1:  e1d1d9f49807 =  1:  15b8306fbe4b init-db: set the_repository->hash_algo early on
  2:  502a66befabe =  2:  02bd1f40fa4e reftable: add LICENSE
  3:  1bd136f6a6df =  3:  bffa33c012ad reftable: add error related functionality
  4:  5bbbafb428e9 !  4:  df8003cb9a7d reftable: utility functions
     @@ Makefile: THIRD_PARTY_SOURCES += compat/regex/%
       EXTLIBS =
       
       GIT_USER_AGENT = git/$(GIT_VERSION)
     -@@ Makefile: XDIFF_OBJS += xdiff/xpatience.o
     - XDIFF_OBJS += xdiff/xprepare.o
     - XDIFF_OBJS += xdiff/xutils.o
     +@@ Makefile: XDIFF_OBJS += xdiff/xutils.o
     + .PHONY: xdiff-objs
     + xdiff-objs: $(XDIFF_OBJS)
       
      +REFTABLE_OBJS += reftable/basics.o
      +REFTABLE_OBJS += reftable/error.o
     @@ Makefile: XDIFF_OBJS += xdiff/xpatience.o
      +REFTABLE_TEST_OBJS += reftable/basics_test.o
      +
       TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
     - OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \
     - 	$(XDIFF_OBJS) \
     - 	$(FUZZ_OBJS) \
     -+	$(REFTABLE_OBJS) \
     -+	$(REFTABLE_TEST_OBJS) \
     - 	common-main.o \
     - 	git.o
     ++
     + .PHONY: test-objs
     + test-objs: $(TEST_OBJS)
     + 
     +@@ Makefile: OBJECTS += $(PROGRAM_OBJS)
     + OBJECTS += $(TEST_OBJS)
     + OBJECTS += $(XDIFF_OBJS)
     + OBJECTS += $(FUZZ_OBJS)
     ++OBJECTS += $(REFTABLE_OBJS) $(REFTABLE_TEST_OBJS)
     ++
       ifndef NO_CURL
     + 	OBJECTS += http.o http-walker.o remote-curl.o
     + endif
      @@ Makefile: $(LIB_FILE): $(LIB_OBJS)
       $(XDIFF_LIB): $(XDIFF_OBJS)
       	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
  5:  e41fa780882d !  5:  6807af53e9a0 reftable: add blocksource, an abstraction for random access reads
     @@ Commit message
          Signed-off-by: Han-Wen Nienhuys <[email-masked]>
      
       ## Makefile ##
     -@@ Makefile: XDIFF_OBJS += xdiff/xutils.o
     +@@ Makefile: xdiff-objs: $(XDIFF_OBJS)
       
       REFTABLE_OBJS += reftable/basics.o
       REFTABLE_OBJS += reftable/error.o
  6:  390eaca4fc8c =  6:  78a352c96f82 reftable: (de)serialization for the polymorphic record type.
  7:  b108525009d9 !  7:  9297b9c363f6 reftable: reading/writing blocks
     @@ Commit message
          Signed-off-by: Han-Wen Nienhuys <[email-masked]>
      
       ## Makefile ##
     -@@ Makefile: XDIFF_OBJS += xdiff/xutils.o
     +@@ Makefile: xdiff-objs: $(XDIFF_OBJS)
       
       REFTABLE_OBJS += reftable/basics.o
       REFTABLE_OBJS += reftable/error.o
  8:  b6eed7283aac !  8:  ceddefadd48c reftable: a generic binary tree implementation
     @@ Makefile: REFTABLE_OBJS += reftable/block.o
      +REFTABLE_TEST_OBJS += reftable/tree_test.o
       
       TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
     - OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \
     + 
      
       ## reftable/tree.c (new) ##
      @@
  9:  f2f005afca19 =  9:  1f635e6c86c5 reftable: write reftable files
  -:  ------------ > 10:  9c3fd77fbbac reftable: generic interface to tables
 10:  1f17d5edab52 ! 11:  8ba486f44a72 reftable: read reftable files
     @@ Makefile: REFTABLE_OBJS += reftable/basics.o
       REFTABLE_OBJS += reftable/publicbasics.o
      +REFTABLE_OBJS += reftable/reader.o
       REFTABLE_OBJS += reftable/record.o
     -+REFTABLE_OBJS += reftable/reftable.o
     + REFTABLE_OBJS += reftable/reftable.o
       REFTABLE_OBJS += reftable/tree.o
     - REFTABLE_OBJS += reftable/writer.o
     - REFTABLE_OBJS += reftable/zlib-compat.o
      
       ## reftable/iter.c (new) ##
      @@
     @@ reftable/iter.c (new)
      +#include "system.h"
      +
      +#include "block.h"
     ++#include "generic.h"
      +#include "constants.h"
      +#include "reader.h"
      +#include "reftable-error.h"
     @@ reftable/iter.c (new)
      +	return it->ops == NULL;
      +}
      +
     -+static int empty_iterator_next(void *arg, struct reftable_record *rec)
     -+{
     -+	return 1;
     -+}
     -+
     -+static void empty_iterator_close(void *arg)
     -+{
     -+}
     -+
     -+static struct reftable_iterator_vtable empty_vtable = {
     -+	.next = &empty_iterator_next,
     -+	.close = &empty_iterator_close,
     -+};
     -+
     -+void iterator_set_empty(struct reftable_iterator *it)
     -+{
     -+	assert(it->ops == NULL);
     -+	it->iter_arg = NULL;
     -+	it->ops = &empty_vtable;
     -+}
     -+
     -+int iterator_next(struct reftable_iterator *it, struct reftable_record *rec)
     -+{
     -+	return it->ops->next(it->iter_arg, rec);
     -+}
     -+
     -+void reftable_iterator_destroy(struct reftable_iterator *it)
     -+{
     -+	if (it->ops == NULL) {
     -+		return;
     -+	}
     -+	it->ops->close(it->iter_arg);
     -+	it->ops = NULL;
     -+	FREE_AND_NULL(it->iter_arg);
     -+}
     -+
     -+int reftable_iterator_next_ref(struct reftable_iterator *it,
     -+			       struct reftable_ref_record *ref)
     -+{
     -+	struct reftable_record rec = { NULL };
     -+	reftable_record_from_ref(&rec, ref);
     -+	return iterator_next(it, &rec);
     -+}
     -+
     -+int reftable_iterator_next_log(struct reftable_iterator *it,
     -+			       struct reftable_log_record *log)
     -+{
     -+	struct reftable_record rec = { NULL };
     -+	reftable_record_from_log(&rec, log);
     -+	return iterator_next(it, &rec);
     -+}
     -+
      +static void filtering_ref_iterator_close(void *iter_arg)
      +{
      +	struct filtering_ref_iterator *fri =
     @@ reftable/iter.h (new)
      +#include "reftable-iterator.h"
      +#include "reftable-generic.h"
      +
     -+struct reftable_iterator_vtable {
     -+	int (*next)(void *iter_arg, struct reftable_record *rec);
     -+	void (*close)(void *iter_arg);
     -+};
     -+
     -+void iterator_set_empty(struct reftable_iterator *it);
     -+int iterator_next(struct reftable_iterator *it, struct reftable_record *rec);
     -+
      +/* Returns true for a zeroed out iterator, such as the one returned from
      + * iterator_destroy. */
      +int iterator_is_null(struct reftable_iterator *it);
     @@ reftable/reader.c (new)
      +#include "system.h"
      +#include "block.h"
      +#include "constants.h"
     ++#include "generic.h"
      +#include "iter.h"
      +#include "record.h"
      +#include "reftable-error.h"
     ++#include "reftable-generic.h"
      +#include "tree.h"
      +
      +uint64_t block_source_size(struct reftable_block_source *source)
     @@ reftable/reader.c (new)
      +uint64_t reftable_reader_min_update_index(struct reftable_reader *r)
      +{
      +	return r->min_update_index;
     ++}
     ++
     ++/* generic table interface. */
     ++
     ++static int reftable_reader_seek_void(void *tab, struct reftable_iterator *it,
     ++				     struct reftable_record *rec)
     ++{
     ++	return reader_seek((struct reftable_reader *)tab, it, rec);
     ++}
     ++
     ++static uint32_t reftable_reader_hash_id_void(void *tab)
     ++{
     ++	return reftable_reader_hash_id((struct reftable_reader *)tab);
     ++}
     ++
     ++static uint64_t reftable_reader_min_update_index_void(void *tab)
     ++{
     ++	return reftable_reader_min_update_index((struct reftable_reader *)tab);
     ++}
     ++
     ++static uint64_t reftable_reader_max_update_index_void(void *tab)
     ++{
     ++	return reftable_reader_max_update_index((struct reftable_reader *)tab);
     ++}
     ++
     ++static struct reftable_table_vtable reader_vtable = {
     ++	.seek_record = reftable_reader_seek_void,
     ++	.hash_id = reftable_reader_hash_id_void,
     ++	.min_update_index = reftable_reader_min_update_index_void,
     ++	.max_update_index = reftable_reader_max_update_index_void,
     ++};
     ++
     ++void reftable_table_from_reader(struct reftable_table *tab,
     ++				struct reftable_reader *reader)
     ++{
     ++	assert(tab->ops == NULL);
     ++	tab->ops = &reader_vtable;
     ++	tab->table_arg = reader;
      +}
      
       ## reftable/reader.h (new) ##
     @@ reftable/reader.h (new)
      +int reader_init_block_reader(struct reftable_reader *r, struct block_reader *br,
      +			     uint64_t next_off, uint8_t want_typ);
      +
     -+/* generic interface to reftables */
     -+struct reftable_table_vtable {
     -+	int (*seek_record)(void *tab, struct reftable_iterator *it,
     -+			   struct reftable_record *);
     -+	uint32_t (*hash_id)(void *tab);
     -+	uint64_t (*min_update_index)(void *tab);
     -+	uint64_t (*max_update_index)(void *tab);
     -+};
     -+
     -+#endif
     -
     - ## reftable/reftable-iterator.h (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#ifndef REFTABLE_ITERATOR_H
     -+#define REFTABLE_ITERATOR_H
     -+
     -+#include "reftable-record.h"
     -+
     -+/* iterator is the generic interface for walking over data stored in a
     -+ * reftable.
     -+ */
     -+struct reftable_iterator {
     -+	struct reftable_iterator_vtable *ops;
     -+	void *iter_arg;
     -+};
     -+
     -+/* reads the next reftable_ref_record. Returns < 0 for error, 0 for OK and > 0:
     -+ * end of iteration.
     -+ */
     -+int reftable_iterator_next_ref(struct reftable_iterator *it,
     -+			       struct reftable_ref_record *ref);
     -+
     -+/* reads the next reftable_log_record. Returns < 0 for error, 0 for OK and > 0:
     -+ * end of iteration.
     -+ */
     -+int reftable_iterator_next_log(struct reftable_iterator *it,
     -+			       struct reftable_log_record *log);
     -+
     -+/* releases resources associated with an iterator. */
     -+void reftable_iterator_destroy(struct reftable_iterator *it);
     -+
      +#endif
      
       ## reftable/reftable-reader.h (new) ##
      @@
      +/*
     -+Copyright 2020 Google LLC
     ++  Copyright 2020 Google LLC
      +
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     ++  Use of this source code is governed by a BSD-style
     ++  license that can be found in the LICENSE file or at
     ++  https://developers.google.com/open-source/licenses/bsd
      +*/
      +
      +#ifndef REFTABLE_READER_H
     @@ reftable/reftable-reader.h (new)
      +/*
      + * Reading single tables
      + *
     -+ * The follow routines are for reading single files. For an application-level
     -+ * interface, skip ahead to struct reftable_merged_table and struct
     -+ * reftable_stack.
     ++ * The follow routines are for reading single files. For an
     ++ * application-level interface, skip ahead to struct
     ++ * reftable_merged_table and struct reftable_stack.
      + */
      +
      +/* The reader struct is a handle to an open reftable file. */
      +struct reftable_reader;
      +
     -+/* reftable_new_reader opens a reftable for reading. If successful, returns 0
     -+ * code and sets pp. The name is used for creating a stack. Typically, it is the
     -+ * basename of the file. The block source `src` is owned by the reader, and is
     -+ * closed on calling reftable_reader_destroy().
     ++/* Generic table. */
     ++struct reftable_table;
     ++
     ++/* reftable_new_reader opens a reftable for reading. If successful,
     ++ * returns 0 code and sets pp. The name is used for creating a
     ++ * stack. Typically, it is the basename of the file. The block source
     ++ * `src` is owned by the reader, and is closed on calling
     ++ * reftable_reader_destroy(). On error, the block source `src` is
     ++ * closed as well.
      + */
      +int reftable_new_reader(struct reftable_reader **pp,
      +			struct reftable_block_source *src, const char *name);
     @@ reftable/reftable-reader.h (new)
      +   if (err < 0) { ... }
      +   struct reftable_ref_record ref  = {0};
      +   while (1) {
     -+     err = reftable_iterator_next_ref(&it, &ref);
     -+     if (err > 0) {
     -+       break;
     -+     }
     -+     if (err < 0) {
     -+       ..error handling..
     -+     }
     -+     ..found..
     ++   err = reftable_iterator_next_ref(&it, &ref);
     ++   if (err > 0) {
     ++   break;
     ++   }
     ++   if (err < 0) {
     ++   ..error handling..
     ++   }
     ++   ..found..
      +   }
      +   reftable_iterator_destroy(&it);
      +   reftable_ref_record_release(&ref);
     -+ */
     ++*/
      +int reftable_reader_seek_ref(struct reftable_reader *r,
      +			     struct reftable_iterator *it, const char *name);
      +
     @@ reftable/reftable-reader.h (new)
      +
      +/* seek to logs for the given name, older than update_index. To seek to the
      +   start of the table, use name = "".
     -+ */
     ++*/
      +int reftable_reader_seek_log_at(struct reftable_reader *r,
      +				struct reftable_iterator *it, const char *name,
      +				uint64_t update_index);
     @@ reftable/reftable-reader.h (new)
      +/* return the min_update_index for a table */
      +uint64_t reftable_reader_min_update_index(struct reftable_reader *r);
      +
     ++/* creates a generic table from a file reader. */
     ++void reftable_table_from_reader(struct reftable_table *tab,
     ++				struct reftable_reader *reader);
     ++
      +#endif
 11:  c916629c562a ! 12:  9ade9303f08f reftable: reftable file level tests
     @@ reftable/reftable_test.c (new)
      +#include "record.h"
      +#include "test_framework.h"
      +#include "reftable-tests.h"
     -+#include "reftable-stack.h"
     ++#include "reftable-writer.h"
      +
      +static const int update_index = 5;
      +
  -:  ------------ > 13:  0a6119d910a3 reftable: add a heap-based priority queue for reftable records
  -:  ------------ > 14:  393fcecdae1e reftable: add merged table view
  -:  ------------ > 15:  3186b2b70f73 reftable: implement refname validation
 12:  28aa69f7bbcb ! 16:  b5492d5a13d7 reftable: rest of library
     @@ Metadata
      Author: Han-Wen Nienhuys <[email-masked]>
      
       ## Commit message ##
     -    reftable: rest of library
     +    reftable: implement stack, a mutable database of reftable files.
      
          Signed-off-by: Han-Wen Nienhuys <[email-masked]>
      
       ## Makefile ##
     -@@ Makefile: REFTABLE_OBJS += reftable/error.o
     - REFTABLE_OBJS += reftable/block.o
     - REFTABLE_OBJS += reftable/blocksource.o
     - REFTABLE_OBJS += reftable/iter.o
     -+REFTABLE_OBJS += reftable/merged.o
     -+REFTABLE_OBJS += reftable/pq.o
     - REFTABLE_OBJS += reftable/publicbasics.o
     - REFTABLE_OBJS += reftable/reader.o
     +@@ Makefile: REFTABLE_OBJS += reftable/reader.o
       REFTABLE_OBJS += reftable/record.o
     -+REFTABLE_OBJS += reftable/refname.o
     + REFTABLE_OBJS += reftable/refname.o
       REFTABLE_OBJS += reftable/reftable.o
      +REFTABLE_OBJS += reftable/stack.o
       REFTABLE_OBJS += reftable/tree.o
       REFTABLE_OBJS += reftable/writer.o
       REFTABLE_OBJS += reftable/zlib-compat.o
     -
     - ## reftable/VERSION (new) ##
     -@@
     -+a337d48d4d42d513d6baa33addc172f0e0e36288 C: use tagged union for reftable_log_record
     -
     - ## reftable/dump.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include <stddef.h>
     -+#include <stdio.h>
     -+#include <stdlib.h>
     -+#include <unistd.h>
     -+#include <string.h>
     -+
     -+#include "reftable.h"
     -+#include "reftable-tests.h"
     -+
     -+static uint32_t hash_id;
     -+
     -+static int dump_table(const char *tablename)
     -+{
     -+	struct reftable_block_source src = { 0 };
     -+	int err = reftable_block_source_from_file(&src, tablename);
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_ref_record ref = { 0 };
     -+	struct reftable_log_record log = { 0 };
     -+	struct reftable_reader *r = NULL;
     -+
     -+	if (err < 0)
     -+		return err;
     -+
     -+	err = reftable_new_reader(&r, &src, tablename);
     -+	if (err < 0)
     -+		return err;
     -+
     -+	err = reftable_reader_seek_ref(r, &it, "");
     -+	if (err < 0) {
     -+		return err;
     -+	}
     -+
     -+	while (1) {
     -+		err = reftable_iterator_next_ref(&it, &ref);
     -+		if (err > 0) {
     -+			break;
     -+		}
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+		reftable_ref_record_print(&ref, hash_id);
     -+	}
     -+	reftable_iterator_destroy(&it);
     -+	reftable_ref_record_clear(&ref);
     -+
     -+	err = reftable_reader_seek_log(r, &it, "");
     -+	if (err < 0) {
     -+		return err;
     -+	}
     -+	while (1) {
     -+		err = reftable_iterator_next_log(&it, &log);
     -+		if (err > 0) {
     -+			break;
     -+		}
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+		reftable_log_record_print(&log, hash_id);
     -+	}
     -+	reftable_iterator_destroy(&it);
     -+	reftable_log_record_clear(&log);
     -+
     -+	reftable_reader_free(r);
     -+	return 0;
     -+}
     -+
     -+static int compact_stack(const char *stackdir)
     -+{
     -+	struct reftable_stack *stack = NULL;
     -+	struct reftable_write_options cfg = {};
     -+
     -+	int err = reftable_new_stack(&stack, stackdir, cfg);
     -+	if (err < 0)
     -+		goto done;
     -+
     -+	err = reftable_stack_compact_all(stack, NULL);
     -+	if (err < 0)
     -+		goto done;
     -+done:
     -+	if (stack != NULL) {
     -+		reftable_stack_destroy(stack);
     -+	}
     -+	return err;
     -+}
     -+
     -+static int dump_stack(const char *stackdir)
     -+{
     -+	struct reftable_stack *stack = NULL;
     -+	struct reftable_write_options cfg = {};
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_ref_record ref = { 0 };
     -+	struct reftable_log_record log = { 0 };
     -+	struct reftable_merged_table *merged = NULL;
     -+
     -+	int err = reftable_new_stack(&stack, stackdir, cfg);
     -+	if (err < 0)
     -+		return err;
     -+
     -+	merged = reftable_stack_merged_table(stack);
     -+
     -+	err = reftable_merged_table_seek_ref(merged, &it, "");
     -+	if (err < 0) {
     -+		return err;
     -+	}
     -+
     -+	while (1) {
     -+		err = reftable_iterator_next_ref(&it, &ref);
     -+		if (err > 0) {
     -+			break;
     -+		}
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+		reftable_ref_record_print(&ref, hash_id);
     -+	}
     -+	reftable_iterator_destroy(&it);
     -+	reftable_ref_record_clear(&ref);
     -+
     -+	err = reftable_merged_table_seek_log(merged, &it, "");
     -+	if (err < 0) {
     -+		return err;
     -+	}
     -+	while (1) {
     -+		err = reftable_iterator_next_log(&it, &log);
     -+		if (err > 0) {
     -+			break;
     -+		}
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+		reftable_log_record_print(&log, hash_id);
     -+	}
     -+	reftable_iterator_destroy(&it);
     -+	reftable_log_record_clear(&log);
     -+
     -+	reftable_stack_destroy(stack);
     -+	return 0;
     -+}
     -+
     -+static void print_help(void)
     -+{
     -+	printf("usage: dump [-cst] arg\n\n"
     -+	       "options: \n"
     -+	       "  -c compact\n"
     -+	       "  -t dump table\n"
     -+	       "  -s dump stack\n"
     -+	       "  -h this help\n"
     -+	       "  -2 use SHA256\n"
     -+	       "\n");
     -+}
     -+
     -+int reftable_dump_main(int argc, char *const *argv)
     -+{
     -+	int err = 0;
     -+	int opt;
     -+	int opt_dump_table = 0;
     -+	int opt_dump_stack = 0;
     -+	int opt_compact = 0;
     -+	const char *arg = NULL;
     -+	while ((opt = getopt(argc, argv, "2chts")) != -1) {
     -+		switch (opt) {
     -+		case '2':
     -+			hash_id = 0x73323536;
     -+			break;
     -+		case 't':
     -+			opt_dump_table = 1;
     -+			break;
     -+		case 's':
     -+			opt_dump_stack = 1;
     -+			break;
     -+		case 'c':
     -+			opt_compact = 1;
     -+			break;
     -+		case '?':
     -+		case 'h':
     -+			print_help();
     -+			return 2;
     -+			break;
     -+		}
     -+	}
     -+
     -+	if (argv[optind] == NULL) {
     -+		fprintf(stderr, "need argument\n");
     -+		print_help();
     -+		return 2;
     -+	}
     -+
     -+	arg = argv[optind];
     -+
     -+	if (opt_dump_table) {
     -+		err = dump_table(arg);
     -+	} else if (opt_dump_stack) {
     -+		err = dump_stack(arg);
     -+	} else if (opt_compact) {
     -+		err = compact_stack(arg);
     -+	}
     -+
     -+	if (err < 0) {
     -+		fprintf(stderr, "%s: %s: %s\n", argv[0], arg,
     -+			reftable_error_str(err));
     -+		return 1;
     -+	}
     -+	return 0;
     -+}
     -
     - ## reftable/merged.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include "merged.h"
     -+
     -+#include "constants.h"
     -+#include "iter.h"
     -+#include "pq.h"
     -+#include "reader.h"
     -+#include "record.h"
     -+#include "reftable-merged.h"
     -+#include "reftable-error.h"
     -+#include "system.h"
     -+
     -+static int merged_iter_init(struct merged_iter *mi)
     -+{
     -+	int i = 0;
     -+	for (i = 0; i < mi->stack_len; i++) {
     -+		struct reftable_record rec = reftable_new_record(mi->typ);
     -+		int err = iterator_next(&mi->stack[i], &rec);
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+
     -+		if (err > 0) {
     -+			reftable_iterator_destroy(&mi->stack[i]);
     -+			reftable_record_destroy(&rec);
     -+		} else {
     -+			struct pq_entry e = {
     -+				.rec = rec,
     -+				.index = i,
     -+			};
     -+			merged_iter_pqueue_add(&mi->pq, e);
     -+		}
     -+	}
     -+
     -+	return 0;
     -+}
     -+
     -+static void merged_iter_close(void *p)
     -+{
     -+	struct merged_iter *mi = (struct merged_iter *)p;
     -+	int i = 0;
     -+	merged_iter_pqueue_release(&mi->pq);
     -+	for (i = 0; i < mi->stack_len; i++) {
     -+		reftable_iterator_destroy(&mi->stack[i]);
     -+	}
     -+	reftable_free(mi->stack);
     -+}
     -+
     -+static int merged_iter_advance_nonnull_subiter(struct merged_iter *mi,
     -+					       size_t idx)
     -+{
     -+	struct reftable_record rec = reftable_new_record(mi->typ);
     -+	struct pq_entry e = {
     -+		.rec = rec,
     -+		.index = idx,
     -+	};
     -+	int err = iterator_next(&mi->stack[idx], &rec);
     -+	if (err < 0)
     -+		return err;
     -+
     -+	if (err > 0) {
     -+		reftable_iterator_destroy(&mi->stack[idx]);
     -+		reftable_record_destroy(&rec);
     -+		return 0;
     -+	}
     -+
     -+	merged_iter_pqueue_add(&mi->pq, e);
     -+	return 0;
     -+}
     -+
     -+static int merged_iter_advance_subiter(struct merged_iter *mi, size_t idx)
     -+{
     -+	if (iterator_is_null(&mi->stack[idx]))
     -+		return 0;
     -+	return merged_iter_advance_nonnull_subiter(mi, idx);
     -+}
     -+
     -+static int merged_iter_next_entry(struct merged_iter *mi,
     -+				  struct reftable_record *rec)
     -+{
     -+	struct strbuf entry_key = STRBUF_INIT;
     -+	struct pq_entry entry = { 0 };
     -+	int err = 0;
     -+
     -+	if (merged_iter_pqueue_is_empty(mi->pq))
     -+		return 1;
     -+
     -+	entry = merged_iter_pqueue_remove(&mi->pq);
     -+	err = merged_iter_advance_subiter(mi, entry.index);
     -+	if (err < 0)
     -+		return err;
     -+
     -+	/*
     -+	  One can also use reftable as datacenter-local storage, where the ref
     -+	  database is maintained in globally consistent database (eg.
     -+	  CockroachDB or Spanner). In this scenario, replication delays together
     -+	  with compaction may cause newer tables to contain older entries. In
     -+	  such a deployment, the loop below must be changed to collect all
     -+	  entries for the same key, and return new the newest one.
     -+	*/
     -+	reftable_record_key(&entry.rec, &entry_key);
     -+	while (!merged_iter_pqueue_is_empty(mi->pq)) {
     -+		struct pq_entry top = merged_iter_pqueue_top(mi->pq);
     -+		struct strbuf k = STRBUF_INIT;
     -+		int err = 0, cmp = 0;
     -+
     -+		reftable_record_key(&top.rec, &k);
     -+
     -+		cmp = strbuf_cmp(&k, &entry_key);
     -+		strbuf_release(&k);
     -+
     -+		if (cmp > 0) {
     -+			break;
     -+		}
     -+
     -+		merged_iter_pqueue_remove(&mi->pq);
     -+		err = merged_iter_advance_subiter(mi, top.index);
     -+		if (err < 0) {
     -+			return err;
     -+		}
     -+		reftable_record_destroy(&top.rec);
     -+	}
     -+
     -+	reftable_record_copy_from(rec, &entry.rec, hash_size(mi->hash_id));
     -+	reftable_record_destroy(&entry.rec);
     -+	strbuf_release(&entry_key);
     -+	return 0;
     -+}
     -+
     -+static int merged_iter_next(struct merged_iter *mi, struct reftable_record *rec)
     -+{
     -+	while (1) {
     -+		int err = merged_iter_next_entry(mi, rec);
     -+		if (err == 0 && mi->suppress_deletions &&
     -+		    reftable_record_is_deletion(rec)) {
     -+			continue;
     -+		}
     -+
     -+		return err;
     -+	}
     -+}
     -+
     -+static int merged_iter_next_void(void *p, struct reftable_record *rec)
     -+{
     -+	struct merged_iter *mi = (struct merged_iter *)p;
     -+	if (merged_iter_pqueue_is_empty(mi->pq))
     -+		return 1;
     -+
     -+	return merged_iter_next(mi, rec);
     -+}
     -+
     -+static struct reftable_iterator_vtable merged_iter_vtable = {
     -+	.next = &merged_iter_next_void,
     -+	.close = &merged_iter_close,
     -+};
     -+
     -+static void iterator_from_merged_iter(struct reftable_iterator *it,
     -+				      struct merged_iter *mi)
     -+{
     -+	assert(it->ops == NULL);
     -+	it->iter_arg = mi;
     -+	it->ops = &merged_iter_vtable;
     -+}
     -+
     -+int reftable_new_merged_table(struct reftable_merged_table **dest,
     -+			      struct reftable_table *stack, int n,
     -+			      uint32_t hash_id)
     -+{
     -+	struct reftable_merged_table *m = NULL;
     -+	uint64_t last_max = 0;
     -+	uint64_t first_min = 0;
     -+	int i = 0;
     -+	for (i = 0; i < n; i++) {
     -+		uint64_t min = reftable_table_min_update_index(&stack[i]);
     -+		uint64_t max = reftable_table_max_update_index(&stack[i]);
     -+
     -+		if (reftable_table_hash_id(&stack[i]) != hash_id) {
     -+			return REFTABLE_FORMAT_ERROR;
     -+		}
     -+		if (i == 0 || min < first_min) {
     -+			first_min = min;
     -+		}
     -+		if (i == 0 || max > last_max) {
     -+			last_max = max;
     -+		}
     -+	}
     -+
     -+	m = (struct reftable_merged_table *)reftable_calloc(
     -+		sizeof(struct reftable_merged_table));
     -+	m->stack = stack;
     -+	m->stack_len = n;
     -+	m->min = first_min;
     -+	m->max = last_max;
     -+	m->hash_id = hash_id;
     -+	*dest = m;
     -+	return 0;
     -+}
     -+
     -+/* clears the list of subtable, without affecting the readers themselves. */
     -+void merged_table_release(struct reftable_merged_table *mt)
     -+{
     -+	FREE_AND_NULL(mt->stack);
     -+	mt->stack_len = 0;
     -+}
     -+
     -+void reftable_merged_table_free(struct reftable_merged_table *mt)
     -+{
     -+	if (mt == NULL) {
     -+		return;
     -+	}
     -+	merged_table_release(mt);
     -+	reftable_free(mt);
     -+}
     -+
     -+uint64_t
     -+reftable_merged_table_max_update_index(struct reftable_merged_table *mt)
     -+{
     -+	return mt->max;
     -+}
     -+
     -+uint64_t
     -+reftable_merged_table_min_update_index(struct reftable_merged_table *mt)
     -+{
     -+	return mt->min;
     -+}
     -+
     -+static int reftable_table_seek_record(struct reftable_table *tab,
     -+				      struct reftable_iterator *it,
     -+				      struct reftable_record *rec)
     -+{
     -+	return tab->ops->seek_record(tab->table_arg, it, rec);
     -+}
     -+
     -+static int merged_table_seek_record(struct reftable_merged_table *mt,
     -+				    struct reftable_iterator *it,
     -+				    struct reftable_record *rec)
     -+{
     -+	struct reftable_iterator *iters = reftable_calloc(
     -+		sizeof(struct reftable_iterator) * mt->stack_len);
     -+	struct merged_iter merged = {
     -+		.stack = iters,
     -+		.typ = reftable_record_type(rec),
     -+		.hash_id = mt->hash_id,
     -+		.suppress_deletions = mt->suppress_deletions,
     -+	};
     -+	int n = 0;
     -+	int err = 0;
     -+	int i = 0;
     -+	for (i = 0; i < mt->stack_len && err == 0; i++) {
     -+		int e = reftable_table_seek_record(&mt->stack[i], &iters[n],
     -+						   rec);
     -+		if (e < 0) {
     -+			err = e;
     -+		}
     -+		if (e == 0) {
     -+			n++;
     -+		}
     -+	}
     -+	if (err < 0) {
     -+		int i = 0;
     -+		for (i = 0; i < n; i++) {
     -+			reftable_iterator_destroy(&iters[i]);
     -+		}
     -+		reftable_free(iters);
     -+		return err;
     -+	}
     -+
     -+	merged.stack_len = n;
     -+	err = merged_iter_init(&merged);
     -+	if (err < 0) {
     -+		merged_iter_close(&merged);
     -+		return err;
     -+	} else {
     -+		struct merged_iter *p =
     -+			reftable_malloc(sizeof(struct merged_iter));
     -+		*p = merged;
     -+		iterator_from_merged_iter(it, p);
     -+	}
     -+	return 0;
     -+}
     -+
     -+int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,
     -+				   struct reftable_iterator *it,
     -+				   const char *name)
     -+{
     -+	struct reftable_ref_record ref = {
     -+		.refname = (char *)name,
     -+	};
     -+	struct reftable_record rec = { NULL };
     -+	reftable_record_from_ref(&rec, &ref);
     -+	return merged_table_seek_record(mt, it, &rec);
     -+}
     -+
     -+int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,
     -+				      struct reftable_iterator *it,
     -+				      const char *name, uint64_t update_index)
     -+{
     -+	struct reftable_log_record log = {
     -+		.refname = (char *)name,
     -+		.update_index = update_index,
     -+	};
     -+	struct reftable_record rec = { NULL };
     -+	reftable_record_from_log(&rec, &log);
     -+	return merged_table_seek_record(mt, it, &rec);
     -+}
     -+
     -+int reftable_merged_table_seek_log(struct reftable_merged_table *mt,
     -+				   struct reftable_iterator *it,
     -+				   const char *name)
     -+{
     -+	uint64_t max = ~((uint64_t)0);
     -+	return reftable_merged_table_seek_log_at(mt, it, name, max);
     -+}
     -+
     -+uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *mt)
     -+{
     -+	return mt->hash_id;
     -+}
     -+
     -+static int reftable_merged_table_seek_void(void *tab,
     -+					   struct reftable_iterator *it,
     -+					   struct reftable_record *rec)
     -+{
     -+	return merged_table_seek_record((struct reftable_merged_table *)tab, it,
     -+					rec);
     -+}
     -+
     -+static uint32_t reftable_merged_table_hash_id_void(void *tab)
     -+{
     -+	return reftable_merged_table_hash_id(
     -+		(struct reftable_merged_table *)tab);
     -+}
     -+
     -+static uint64_t reftable_merged_table_min_update_index_void(void *tab)
     -+{
     -+	return reftable_merged_table_min_update_index(
     -+		(struct reftable_merged_table *)tab);
     -+}
     -+
     -+static uint64_t reftable_merged_table_max_update_index_void(void *tab)
     -+{
     -+	return reftable_merged_table_max_update_index(
     -+		(struct reftable_merged_table *)tab);
     -+}
     -+
     -+static struct reftable_table_vtable merged_table_vtable = {
     -+	.seek_record = reftable_merged_table_seek_void,
     -+	.hash_id = reftable_merged_table_hash_id_void,
     -+	.min_update_index = reftable_merged_table_min_update_index_void,
     -+	.max_update_index = reftable_merged_table_max_update_index_void,
     -+};
     -+
     -+void reftable_table_from_merged_table(struct reftable_table *tab,
     -+				      struct reftable_merged_table *merged)
     -+{
     -+	assert(tab->ops == NULL);
     -+	tab->ops = &merged_table_vtable;
     -+	tab->table_arg = merged;
     -+}
     -
     - ## reftable/merged.h (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#ifndef MERGED_H
     -+#define MERGED_H
     -+
     -+#include "pq.h"
     -+
     -+struct reftable_merged_table {
     -+	struct reftable_table *stack;
     -+	size_t stack_len;
     -+	uint32_t hash_id;
     -+	int suppress_deletions;
     -+
     -+	uint64_t min;
     -+	uint64_t max;
     -+};
     -+
     -+struct merged_iter {
     -+	struct reftable_iterator *stack;
     -+	uint32_t hash_id;
     -+	size_t stack_len;
     -+	uint8_t typ;
     -+	int suppress_deletions;
     -+	struct merged_iter_pqueue pq;
     -+};
     -+
     -+void merged_table_release(struct reftable_merged_table *mt);
     -+
     -+#endif
     -
     - ## reftable/merged_test.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include "merged.h"
     -+
     -+#include "system.h"
     -+
     -+#include "basics.h"
     -+#include "blocksource.h"
     -+#include "constants.h"
     -+#include "pq.h"
     -+#include "reader.h"
     -+#include "record.h"
     -+#include "test_framework.h"
     -+#include "reftable-merged.h"
     -+#include "reftable-tests.h"
     -+#include "reftable-generic.h"
     -+#include "reftable-stack.h"
     -+
     -+static void test_pq(void)
     -+{
     -+	char *names[54] = { NULL };
     -+	int N = ARRAY_SIZE(names) - 1;
     -+
     -+	struct merged_iter_pqueue pq = { NULL };
     -+	const char *last = NULL;
     -+
     -+	int i = 0;
     -+	for (i = 0; i < N; i++) {
     -+		char name[100];
     -+		snprintf(name, sizeof(name), "%02d", i);
     -+		names[i] = xstrdup(name);
     -+	}
     -+
     -+	i = 1;
     -+	do {
     -+		struct reftable_record rec =
     -+			reftable_new_record(BLOCK_TYPE_REF);
     -+		struct pq_entry e = { 0 };
     -+
     -+		reftable_record_as_ref(&rec)->refname = names[i];
     -+		e.rec = rec;
     -+		merged_iter_pqueue_add(&pq, e);
     -+		merged_iter_pqueue_check(pq);
     -+		i = (i * 7) % N;
     -+	} while (i != 1);
     -+
     -+	while (!merged_iter_pqueue_is_empty(pq)) {
     -+		struct pq_entry e = merged_iter_pqueue_remove(&pq);
     -+		struct reftable_ref_record *ref =
     -+			reftable_record_as_ref(&e.rec);
     -+
     -+		merged_iter_pqueue_check(pq);
     -+
     -+		if (last != NULL) {
     -+			assert(strcmp(last, ref->refname) < 0);
     -+		}
     -+		last = ref->refname;
     -+		ref->refname = NULL;
     -+		reftable_free(ref);
     -+	}
     -+
     -+	for (i = 0; i < N; i++) {
     -+		reftable_free(names[i]);
     -+	}
     -+
     -+	merged_iter_pqueue_release(&pq);
     -+}
     -+
     -+static void write_test_table(struct strbuf *buf,
     -+			     struct reftable_ref_record refs[], int n)
     -+{
     -+	int min = 0xffffffff;
     -+	int max = 0;
     -+	int i = 0;
     -+	int err;
     -+
     -+	struct reftable_write_options opts = {
     -+		.block_size = 256,
     -+	};
     -+	struct reftable_writer *w = NULL;
     -+	for (i = 0; i < n; i++) {
     -+		uint64_t ui = refs[i].update_index;
     -+		if (ui > max) {
     -+			max = ui;
     -+		}
     -+		if (ui < min) {
     -+			min = ui;
     -+		}
     -+	}
     -+
     -+	w = reftable_new_writer(&strbuf_add_void, buf, &opts);
     -+	reftable_writer_set_limits(w, min, max);
     -+
     -+	for (i = 0; i < n; i++) {
     -+		uint64_t before = refs[i].update_index;
     -+		int n = reftable_writer_add_ref(w, &refs[i]);
     -+		assert(n == 0);
     -+		assert(before == refs[i].update_index);
     -+	}
     -+
     -+	err = reftable_writer_close(w);
     -+	EXPECT_ERR(err);
     -+
     -+	reftable_writer_free(w);
     -+}
     -+
     -+static struct reftable_merged_table *
     -+merged_table_from_records(struct reftable_ref_record **refs,
     -+			  struct reftable_block_source **source,
     -+			  struct reftable_reader ***readers, int *sizes,
     -+			  struct strbuf *buf, int n)
     -+{
     -+	int i = 0;
     -+	struct reftable_merged_table *mt = NULL;
     -+	int err;
     -+	struct reftable_table *tabs =
     -+		reftable_calloc(n * sizeof(struct reftable_table));
     -+	*readers = reftable_calloc(n * sizeof(struct reftable_reader *));
     -+	*source = reftable_calloc(n * sizeof(**source));
     -+	for (i = 0; i < n; i++) {
     -+		write_test_table(&buf[i], refs[i], sizes[i]);
     -+		block_source_from_strbuf(&(*source)[i], &buf[i]);
     -+
     -+		err = reftable_new_reader(&(*readers)[i], &(*source)[i],
     -+					  "name");
     -+		EXPECT_ERR(err);
     -+		reftable_table_from_reader(&tabs[i], (*readers)[i]);
     -+	}
     -+
     -+	err = reftable_new_merged_table(&mt, tabs, n, SHA1_ID);
     -+	EXPECT_ERR(err);
     -+	return mt;
     -+}
     -+
     -+static void readers_destroy(struct reftable_reader **readers, size_t n)
     -+{
     -+	int i = 0;
     -+	for (; i < n; i++)
     -+		reftable_reader_free(readers[i]);
     -+	reftable_free(readers);
     -+}
     -+
     -+static void test_merged_between(void)
     -+{
     -+	uint8_t hash1[SHA1_SIZE] = { 1, 2, 3, 0 };
     -+
     -+	struct reftable_ref_record r1[] = { {
     -+		.refname = "b",
     -+		.update_index = 1,
     -+		.value_type = REFTABLE_REF_VAL1,
     -+		.value.val1 = hash1,
     -+	} };
     -+	struct reftable_ref_record r2[] = { {
     -+		.refname = "a",
     -+		.update_index = 2,
     -+		.value_type = REFTABLE_REF_DELETION,
     -+	} };
     -+
     -+	struct reftable_ref_record *refs[] = { r1, r2 };
     -+	int sizes[] = { 1, 1 };
     -+	struct strbuf bufs[2] = { STRBUF_INIT, STRBUF_INIT };
     -+	struct reftable_block_source *bs = NULL;
     -+	struct reftable_reader **readers = NULL;
     -+	struct reftable_merged_table *mt =
     -+		merged_table_from_records(refs, &bs, &readers, sizes, bufs, 2);
     -+	int i;
     -+	struct reftable_ref_record ref = { NULL };
     -+	struct reftable_iterator it = { NULL };
     -+	int err = reftable_merged_table_seek_ref(mt, &it, "a");
     -+	EXPECT_ERR(err);
     -+
     -+	err = reftable_iterator_next_ref(&it, &ref);
     -+	EXPECT_ERR(err);
     -+	EXPECT(ref.update_index == 2);
     -+	reftable_ref_record_release(&ref);
     -+	reftable_iterator_destroy(&it);
     -+	readers_destroy(readers, 2);
     -+	reftable_merged_table_free(mt);
     -+	for (i = 0; i < ARRAY_SIZE(bufs); i++) {
     -+		strbuf_release(&bufs[i]);
     -+	}
     -+	reftable_free(bs);
     -+}
     -+
     -+static void test_merged(void)
     -+{
     -+	uint8_t hash1[SHA1_SIZE] = { 1 };
     -+	uint8_t hash2[SHA1_SIZE] = { 2 };
     -+	struct reftable_ref_record r1[] = {
     -+		{
     -+			.refname = "a",
     -+			.update_index = 1,
     -+			.value_type = REFTABLE_REF_VAL1,
     -+			.value.val1 = hash1,
     -+		},
     -+		{
     -+			.refname = "b",
     -+			.update_index = 1,
     -+			.value_type = REFTABLE_REF_VAL1,
     -+			.value.val1 = hash1,
     -+		},
     -+		{
     -+			.refname = "c",
     -+			.update_index = 1,
     -+			.value_type = REFTABLE_REF_VAL1,
     -+			.value.val1 = hash1,
     -+		}
     -+	};
     -+	struct reftable_ref_record r2[] = { {
     -+		.refname = "a",
     -+		.update_index = 2,
     -+		.value_type = REFTABLE_REF_DELETION,
     -+	} };
     -+	struct reftable_ref_record r3[] = {
     -+		{
     -+			.refname = "c",
     -+			.update_index = 3,
     -+			.value_type = REFTABLE_REF_VAL1,
     -+			.value.val1 = hash2,
     -+		},
     -+		{
     -+			.refname = "d",
     -+			.update_index = 3,
     -+			.value_type = REFTABLE_REF_VAL1,
     -+			.value.val1 = hash1,
     -+		},
     -+	};
     -+
     -+	struct reftable_ref_record want[] = {
     -+		r2[0],
     -+		r1[1],
     -+		r3[0],
     -+		r3[1],
     -+	};
     -+
     -+	struct reftable_ref_record *refs[] = { r1, r2, r3 };
     -+	int sizes[3] = { 3, 1, 2 };
     -+	struct strbuf bufs[3] = { STRBUF_INIT, STRBUF_INIT, STRBUF_INIT };
     -+	struct reftable_block_source *bs = NULL;
     -+	struct reftable_reader **readers = NULL;
     -+	struct reftable_merged_table *mt =
     -+		merged_table_from_records(refs, &bs, &readers, sizes, bufs, 3);
     -+
     -+	struct reftable_iterator it = { NULL };
     -+	int err = reftable_merged_table_seek_ref(mt, &it, "a");
     -+	struct reftable_ref_record *out = NULL;
     -+	size_t len = 0;
     -+	size_t cap = 0;
     -+	int i = 0;
     -+
     -+	EXPECT_ERR(err);
     -+	while (len < 100) { /* cap loops/recursion. */
     -+		struct reftable_ref_record ref = { NULL };
     -+		int err = reftable_iterator_next_ref(&it, &ref);
     -+		if (err > 0) {
     -+			break;
     -+		}
     -+		if (len == cap) {
     -+			cap = 2 * cap + 1;
     -+			out = reftable_realloc(
     -+				out, sizeof(struct reftable_ref_record) * cap);
     -+		}
     -+		out[len++] = ref;
     -+	}
     -+	reftable_iterator_destroy(&it);
     -+
     -+	assert(ARRAY_SIZE(want) == len);
     -+	for (i = 0; i < len; i++) {
     -+		assert(reftable_ref_record_equal(&want[i], &out[i], SHA1_SIZE));
     -+	}
     -+	for (i = 0; i < len; i++) {
     -+		reftable_ref_record_release(&out[i]);
     -+	}
     -+	reftable_free(out);
     -+
     -+	for (i = 0; i < 3; i++) {
     -+		strbuf_release(&bufs[i]);
     -+	}
     -+	readers_destroy(readers, 3);
     -+	reftable_merged_table_free(mt);
     -+	reftable_free(bs);
     -+}
     -+
     -+static void test_default_write_opts(void)
     -+{
     -+	struct reftable_write_options opts = { 0 };
     -+	struct strbuf buf = STRBUF_INIT;
     -+	struct reftable_writer *w =
     -+		reftable_new_writer(&strbuf_add_void, &buf, &opts);
     -+
     -+	struct reftable_ref_record rec = {
     -+		.refname = "master",
     -+		.update_index = 1,
     -+	};
     -+	int err;
     -+	struct reftable_block_source source = { NULL };
     -+	struct reftable_table *tab = reftable_calloc(sizeof(*tab) * 1);
     -+	uint32_t hash_id;
     -+	struct reftable_reader *rd = NULL;
     -+	struct reftable_merged_table *merged = NULL;
     -+
     -+	reftable_writer_set_limits(w, 1, 1);
     -+
     -+	err = reftable_writer_add_ref(w, &rec);
     -+	EXPECT_ERR(err);
     -+
     -+	err = reftable_writer_close(w);
     -+	EXPECT_ERR(err);
     -+	reftable_writer_free(w);
     -+
     -+	block_source_from_strbuf(&source, &buf);
     -+
     -+	err = reftable_new_reader(&rd, &source, "filename");
     -+	EXPECT_ERR(err);
     -+
     -+	hash_id = reftable_reader_hash_id(rd);
     -+	assert(hash_id == SHA1_ID);
     -+
     -+	reftable_table_from_reader(&tab[0], rd);
     -+	err = reftable_new_merged_table(&merged, tab, 1, SHA1_ID);
     -+	EXPECT_ERR(err);
     -+
     -+	reftable_reader_free(rd);
     -+	reftable_merged_table_free(merged);
     -+	strbuf_release(&buf);
     -+}
     -+
     -+/* XXX test refs_for(oid) */
     -+
     -+int merged_test_main(int argc, const char *argv[])
     -+{
     -+	RUN_TEST(test_merged_between);
     -+	RUN_TEST(test_pq);
     -+	RUN_TEST(test_merged);
     -+	RUN_TEST(test_default_write_opts);
     -+	return 0;
     -+}
     -
     - ## reftable/pq.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include "pq.h"
     -+
     -+#include "reftable-record.h"
     -+#include "system.h"
     -+#include "basics.h"
     -+
     -+static int pq_less(struct pq_entry a, struct pq_entry b)
     -+{
     -+	struct strbuf ak = STRBUF_INIT;
     -+	struct strbuf bk = STRBUF_INIT;
     -+	int cmp = 0;
     -+	reftable_record_key(&a.rec, &ak);
     -+	reftable_record_key(&b.rec, &bk);
     -+
     -+	cmp = strbuf_cmp(&ak, &bk);
     -+
     -+	strbuf_release(&ak);
     -+	strbuf_release(&bk);
     -+
     -+	if (cmp == 0)
     -+		return a.index > b.index;
     -+
     -+	return cmp < 0;
     -+}
     -+
     -+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq)
     -+{
     -+	return pq.heap[0];
     -+}
     -+
     -+int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq)
     -+{
     -+	return pq.len == 0;
     -+}
     -+
     -+void merged_iter_pqueue_check(struct merged_iter_pqueue pq)
     -+{
     -+	int i = 0;
     -+	for (i = 1; i < pq.len; i++) {
     -+		int parent = (i - 1) / 2;
     -+
     -+		assert(pq_less(pq.heap[parent], pq.heap[i]));
     -+	}
     -+}
     -+
     -+struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq)
     -+{
     -+	int i = 0;
     -+	struct pq_entry e = pq->heap[0];
     -+	pq->heap[0] = pq->heap[pq->len - 1];
     -+	pq->len--;
     -+
     -+	i = 0;
     -+	while (i < pq->len) {
     -+		int min = i;
     -+		int j = 2 * i + 1;
     -+		int k = 2 * i + 2;
     -+		if (j < pq->len && pq_less(pq->heap[j], pq->heap[i])) {
     -+			min = j;
     -+		}
     -+		if (k < pq->len && pq_less(pq->heap[k], pq->heap[min])) {
     -+			min = k;
     -+		}
     -+
     -+		if (min == i) {
     -+			break;
     -+		}
     -+
     -+		SWAP(pq->heap[i], pq->heap[min]);
     -+		i = min;
     -+	}
     -+
     -+	return e;
     -+}
     -+
     -+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e)
     -+{
     -+	int i = 0;
     -+	if (pq->len == pq->cap) {
     -+		pq->cap = 2 * pq->cap + 1;
     -+		pq->heap = reftable_realloc(pq->heap,
     -+					    pq->cap * sizeof(struct pq_entry));
     -+	}
     -+
     -+	pq->heap[pq->len++] = e;
     -+	i = pq->len - 1;
     -+	while (i > 0) {
     -+		int j = (i - 1) / 2;
     -+		if (pq_less(pq->heap[j], pq->heap[i])) {
     -+			break;
     -+		}
     -+
     -+		SWAP(pq->heap[j], pq->heap[i]);
     -+
     -+		i = j;
     -+	}
     -+}
     -+
     -+void merged_iter_pqueue_release(struct merged_iter_pqueue *pq)
     -+{
     -+	int i = 0;
     -+	for (i = 0; i < pq->len; i++) {
     -+		reftable_record_destroy(&pq->heap[i].rec);
     -+	}
     -+	FREE_AND_NULL(pq->heap);
     -+	pq->len = pq->cap = 0;
     -+}
     -
     - ## reftable/pq.h (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#ifndef PQ_H
     -+#define PQ_H
     -+
     -+#include "record.h"
     -+
     -+struct pq_entry {
     -+	int index;
     -+	struct reftable_record rec;
     -+};
     -+
     -+struct merged_iter_pqueue {
     -+	struct pq_entry *heap;
     -+	size_t len;
     -+	size_t cap;
     -+};
     -+
     -+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
     -+int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);
     -+void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
     -+struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
     -+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e);
     -+void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
     -+
     -+#endif
     -
     - ## reftable/refname.c (new) ##
     -@@
     -+/*
     -+  Copyright 2020 Google LLC
     -+
     -+  Use of this source code is governed by a BSD-style
     -+  license that can be found in the LICENSE file or at
     -+  https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include "system.h"
     -+#include "reftable-error.h"
     -+#include "basics.h"
     -+#include "refname.h"
     -+#include "reftable-iterator.h"
     -+
     -+struct find_arg {
     -+	char **names;
     -+	const char *want;
     -+};
     -+
     -+static int find_name(size_t k, void *arg)
     -+{
     -+	struct find_arg *f_arg = (struct find_arg *)arg;
     -+	return strcmp(f_arg->names[k], f_arg->want) >= 0;
     -+}
     -+
     -+static int modification_has_ref(struct modification *mod, const char *name)
     -+{
     -+	struct reftable_ref_record ref = { NULL };
     -+	int err = 0;
     -+
     -+	if (mod->add_len > 0) {
     -+		struct find_arg arg = {
     -+			.names = mod->add,
     -+			.want = name,
     -+		};
     -+		int idx = binsearch(mod->add_len, find_name, &arg);
     -+		if (idx < mod->add_len && !strcmp(mod->add[idx], name)) {
     -+			return 0;
     -+		}
     -+	}
     -+
     -+	if (mod->del_len > 0) {
     -+		struct find_arg arg = {
     -+			.names = mod->del,
     -+			.want = name,
     -+		};
     -+		int idx = binsearch(mod->del_len, find_name, &arg);
     -+		if (idx < mod->del_len && !strcmp(mod->del[idx], name)) {
     -+			return 1;
     -+		}
     -+	}
     -+
     -+	err = reftable_table_read_ref(&mod->tab, name, &ref);
     -+	reftable_ref_record_release(&ref);
     -+	return err;
     -+}
     -+
     -+static void modification_release(struct modification *mod)
     -+{
     -+	/* don't delete the strings themselves; they're owned by ref records.
     -+	 */
     -+	FREE_AND_NULL(mod->add);
     -+	FREE_AND_NULL(mod->del);
     -+	mod->add_len = 0;
     -+	mod->del_len = 0;
     -+}
     -+
     -+static int modification_has_ref_with_prefix(struct modification *mod,
     -+					    const char *prefix)
     -+{
     -+	struct reftable_iterator it = { NULL };
     -+	struct reftable_ref_record ref = { NULL };
     -+	int err = 0;
     -+
     -+	if (mod->add_len > 0) {
     -+		struct find_arg arg = {
     -+			.names = mod->add,
     -+			.want = prefix,
     -+		};
     -+		int idx = binsearch(mod->add_len, find_name, &arg);
     -+		if (idx < mod->add_len &&
     -+		    !strncmp(prefix, mod->add[idx], strlen(prefix)))
     -+			goto done;
     -+	}
     -+	err = reftable_table_seek_ref(&mod->tab, &it, prefix);
     -+	if (err)
     -+		goto done;
     -+
     -+	while (1) {
     -+		err = reftable_iterator_next_ref(&it, &ref);
     -+		if (err)
     -+			goto done;
     -+
     -+		if (mod->del_len > 0) {
     -+			struct find_arg arg = {
     -+				.names = mod->del,
     -+				.want = ref.refname,
     -+			};
     -+			int idx = binsearch(mod->del_len, find_name, &arg);
     -+			if (idx < mod->del_len &&
     -+			    !strcmp(ref.refname, mod->del[idx])) {
     -+				continue;
     -+			}
     -+		}
     -+
     -+		if (strncmp(ref.refname, prefix, strlen(prefix))) {
     -+			err = 1;
     -+			goto done;
     -+		}
     -+		err = 0;
     -+		goto done;
     -+	}
     -+
     -+done:
     -+	reftable_ref_record_release(&ref);
     -+	reftable_iterator_destroy(&it);
     -+	return err;
     -+}
     -+
     -+static int validate_refname(const char *name)
     -+{
     -+	while (1) {
     -+		char *next = strchr(name, '/');
     -+		if (!*name) {
     -+			return REFTABLE_REFNAME_ERROR;
     -+		}
     -+		if (!next) {
     -+			return 0;
     -+		}
     -+		if (next - name == 0 || (next - name == 1 && *name == '.') ||
     -+		    (next - name == 2 && name[0] == '.' && name[1] == '.'))
     -+			return REFTABLE_REFNAME_ERROR;
     -+		name = next + 1;
     -+	}
     -+	return 0;
     -+}
     -+
     -+int validate_ref_record_addition(struct reftable_table tab,
     -+				 struct reftable_ref_record *recs, size_t sz)
     -+{
     -+	struct modification mod = {
     -+		.tab = tab,
     -+		.add = reftable_calloc(sizeof(char *) * sz),
     -+		.del = reftable_calloc(sizeof(char *) * sz),
     -+	};
     -+	int i = 0;
     -+	int err = 0;
     -+	for (; i < sz; i++) {
     -+		if (reftable_ref_record_is_deletion(&recs[i])) {
     -+			mod.del[mod.del_len++] = recs[i].refname;
     -+		} else {
     -+			mod.add[mod.add_len++] = recs[i].refname;
     -+		}
     -+	}
     -+
     -+	err = modification_validate(&mod);
     -+	modification_release(&mod);
     -+	return err;
     -+}
     -+
     -+static void strbuf_trim_component(struct strbuf *sl)
     -+{
     -+	while (sl->len > 0) {
     -+		int is_slash = (sl->buf[sl->len - 1] == '/');
     -+		strbuf_setlen(sl, sl->len - 1);
     -+		if (is_slash)
     -+			break;
     -+	}
     -+}
     -+
     -+int modification_validate(struct modification *mod)
     -+{
     -+	struct strbuf slashed = STRBUF_INIT;
     -+	int err = 0;
     -+	int i = 0;
     -+	for (; i < mod->add_len; i++) {
     -+		err = validate_refname(mod->add[i]);
     -+		if (err)
     -+			goto done;
     -+		strbuf_reset(&slashed);
     -+		strbuf_addstr(&slashed, mod->add[i]);
     -+		strbuf_addstr(&slashed, "/");
     -+
     -+		err = modification_has_ref_with_prefix(mod, slashed.buf);
     -+		if (err == 0) {
     -+			err = REFTABLE_NAME_CONFLICT;
     -+			goto done;
     -+		}
     -+		if (err < 0)
     -+			goto done;
     -+
     -+		strbuf_reset(&slashed);
     -+		strbuf_addstr(&slashed, mod->add[i]);
     -+		while (slashed.len) {
     -+			strbuf_trim_component(&slashed);
     -+			err = modification_has_ref(mod, slashed.buf);
     -+			if (err == 0) {
     -+				err = REFTABLE_NAME_CONFLICT;
     -+				goto done;
     -+			}
     -+			if (err < 0)
     -+				goto done;
     -+		}
     -+	}
     -+	err = 0;
     -+done:
     -+	strbuf_release(&slashed);
     -+	return err;
     -+}
     -
     - ## reftable/refname.h (new) ##
     -@@
     -+/*
     -+  Copyright 2020 Google LLC
     -+
     -+  Use of this source code is governed by a BSD-style
     -+  license that can be found in the LICENSE file or at
     -+  https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+#ifndef REFNAME_H
     -+#define REFNAME_H
     -+
     -+#include "reftable-record.h"
     -+#include "reftable-generic.h"
     -+
     -+struct modification {
     -+	struct reftable_table tab;
     -+
     -+	char **add;
     -+	size_t add_len;
     -+
     -+	char **del;
     -+	size_t del_len;
     -+};
     -+
     -+int validate_ref_record_addition(struct reftable_table tab,
     -+				 struct reftable_ref_record *recs, size_t sz);
     -+
     -+int modification_validate(struct modification *mod);
     -+
     -+#endif
     -
     - ## reftable/refname_test.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include "basics.h"
     -+#include "block.h"
     -+#include "blocksource.h"
     -+#include "constants.h"
     -+#include "reader.h"
     -+#include "record.h"
     -+#include "refname.h"
     -+#include "reftable-error.h"
     -+#include "reftable-writer.h"
     -+#include "system.h"
     -+
     -+#include "test_framework.h"
     -+#include "reftable-tests.h"
     -+
     -+struct testcase {
     -+	char *add;
     -+	char *del;
     -+	int error_code;
     -+};
     -+
     -+static void test_conflict(void)
     -+{
     -+	struct reftable_write_options opts = { 0 };
     -+	struct strbuf buf = STRBUF_INIT;
     -+	struct reftable_writer *w =
     -+		reftable_new_writer(&strbuf_add_void, &buf, &opts);
     -+	struct reftable_ref_record rec = {
     -+		.refname = "a/b",
     -+		.value_type = REFTABLE_REF_SYMREF,
     -+		.value.symref = "destination", /* make sure it's not a symref.
     -+						*/
     -+		.update_index = 1,
     -+	};
     -+	int err;
     -+	int i;
     -+	struct reftable_block_source source = { NULL };
     -+	struct reftable_reader *rd = NULL;
     -+	struct reftable_table tab = { NULL };
     -+	struct testcase cases[] = {
     -+		{ "a/b/c", NULL, REFTABLE_NAME_CONFLICT },
     -+		{ "b", NULL, 0 },
     -+		{ "a", NULL, REFTABLE_NAME_CONFLICT },
     -+		{ "a", "a/b", 0 },
     -+
     -+		{ "p/", NULL, REFTABLE_REFNAME_ERROR },
     -+		{ "p//q", NULL, REFTABLE_REFNAME_ERROR },
     -+		{ "p/./q", NULL, REFTABLE_REFNAME_ERROR },
     -+		{ "p/../q", NULL, REFTABLE_REFNAME_ERROR },
     -+
     -+		{ "a/b/c", "a/b", 0 },
     -+		{ NULL, "a//b", 0 },
     -+	};
     -+	reftable_writer_set_limits(w, 1, 1);
     -+
     -+	err = reftable_writer_add_ref(w, &rec);
     -+	EXPECT_ERR(err);
     -+
     -+	err = reftable_writer_close(w);
     -+	EXPECT_ERR(err);
     -+	reftable_writer_free(w);
     -+
     -+	block_source_from_strbuf(&source, &buf);
     -+	err = reftable_new_reader(&rd, &source, "filename");
     -+	EXPECT_ERR(err);
     -+
     -+	reftable_table_from_reader(&tab, rd);
     -+
     -+	for (i = 0; i < ARRAY_SIZE(cases); i++) {
     -+		struct modification mod = {
     -+			.tab = tab,
     -+		};
     -+
     -+		if (cases[i].add != NULL) {
     -+			mod.add = &cases[i].add;
     -+			mod.add_len = 1;
     -+		}
     -+		if (cases[i].del != NULL) {
     -+			mod.del = &cases[i].del;
     -+			mod.del_len = 1;
     -+		}
     -+
     -+		err = modification_validate(&mod);
     -+		EXPECT(err == cases[i].error_code);
     -+	}
     -+
     -+	reftable_reader_free(rd);
     -+	strbuf_release(&buf);
     -+}
     -+
     -+int refname_test_main(int argc, const char *argv[])
     -+{
     -+	RUN_TEST(test_conflict);
     -+	return 0;
     -+}
     -
     - ## reftable/reftable-generic.h (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#ifndef REFTABLE_GENERIC_H
     -+#define REFTABLE_GENERIC_H
     -+
     -+#include "reftable-iterator.h"
     -+#include "reftable-reader.h"
     -+#include "reftable-merged.h"
     -+
     -+/*
     -+ * Provides a unified API for reading tables, either merged tables, or single
     -+ * readers. */
     -+struct reftable_table {
     -+	struct reftable_table_vtable *ops;
     -+	void *table_arg;
     -+};
     -+
     -+int reftable_table_seek_ref(struct reftable_table *tab,
     -+			    struct reftable_iterator *it, const char *name);
     -+
     -+void reftable_table_from_reader(struct reftable_table *tab,
     -+				struct reftable_reader *reader);
     -+
     -+/* returns the hash ID from a generic reftable_table */
     -+uint32_t reftable_table_hash_id(struct reftable_table *tab);
     -+
     -+/* create a generic table from reftable_merged_table */
     -+void reftable_table_from_merged_table(struct reftable_table *tab,
     -+				      struct reftable_merged_table *table);
     -+
     -+/* returns the max update_index covered by this table. */
     -+uint64_t reftable_table_max_update_index(struct reftable_table *tab);
     -+
     -+/* returns the min update_index covered by this table. */
     -+uint64_t reftable_table_min_update_index(struct reftable_table *tab);
     -+
     -+/* convenience function to read a single ref. Returns < 0 for error, 0
     -+   for success, and 1 if ref not found. */
     -+int reftable_table_read_ref(struct reftable_table *tab, const char *name,
     -+			    struct reftable_ref_record *ref);
     -+
     -+#endif
     -
     - ## reftable/reftable-merged.h (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#ifndef REFTABLE_MERGED_H
     -+#define REFTABLE_MERGED_H
     -+
     -+#include "reftable-iterator.h"
     -+
     -+/*
     -+ * Merged tables
     -+ *
     -+ * A ref database kept in a sequence of table files. The merged_table presents a
     -+ * unified view to reading (seeking, iterating) a sequence of immutable tables.
     -+ *
     -+ * The merged tables are on purpose kept disconnected from their actual storage
     -+ * (eg. files on disk), because it is useful to merge tables aren't files. For
     -+ * example, the per-workspace and global ref namespace can be implemented as a
     -+ * merged table of two stacks of file-backed reftables.
     -+ */
     -+
     -+/* A merged table is implements seeking/iterating over a stack of tables. */
     -+struct reftable_merged_table;
     -+
     -+/* A generic reftable; see below. */
     -+struct reftable_table;
     -+
     -+/* reftable_new_merged_table creates a new merged table. It takes ownership of
     -+   the stack array.
     -+*/
     -+int reftable_new_merged_table(struct reftable_merged_table **dest,
     -+			      struct reftable_table *stack, int n,
     -+			      uint32_t hash_id);
     -+
     -+/* returns an iterator positioned just before 'name' */
     -+int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,
     -+				   struct reftable_iterator *it,
     -+				   const char *name);
     -+
     -+/* returns an iterator for log entry, at given update_index */
     -+int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,
     -+				      struct reftable_iterator *it,
     -+				      const char *name, uint64_t update_index);
     -+
     -+/* like reftable_merged_table_seek_log_at but look for the newest entry. */
     -+int reftable_merged_table_seek_log(struct reftable_merged_table *mt,
     -+				   struct reftable_iterator *it,
     -+				   const char *name);
     -+
     -+/* returns the max update_index covered by this merged table. */
     -+uint64_t
     -+reftable_merged_table_max_update_index(struct reftable_merged_table *mt);
     -+
     -+/* returns the min update_index covered by this merged table. */
     -+uint64_t
     -+reftable_merged_table_min_update_index(struct reftable_merged_table *mt);
     -+
     -+/* releases memory for the merged_table */
     -+void reftable_merged_table_free(struct reftable_merged_table *m);
     -+
     -+/* return the hash ID of the merged table. */
     -+uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *m);
     -+
     -+#endif
     +@@ Makefile: REFTABLE_TEST_OBJS += reftable/pq_test.o
     + REFTABLE_TEST_OBJS += reftable/record_test.o
     + REFTABLE_TEST_OBJS += reftable/refname_test.o
     + REFTABLE_TEST_OBJS += reftable/reftable_test.o
     ++REFTABLE_TEST_OBJS += reftable/stack_test.o
     + REFTABLE_TEST_OBJS += reftable/test_framework.o
     + REFTABLE_TEST_OBJS += reftable/tree_test.o
     + 
      
       ## reftable/reftable-stack.h (new) ##
      @@
     @@ reftable/reftable-stack.h (new)
      +/* heuristically compact unbalanced table stack. */
      +int reftable_stack_auto_compact(struct reftable_stack *st);
      +
     ++/* delete stale .ref tables. */
     ++int reftable_stack_clean(struct reftable_stack *st);
     ++
      +/* convenience function to read a single ref. Returns < 0 for error, 0 for
      + * success, and 1 if ref not found. */
      +int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
     @@ reftable/reftable-stack.h (new)
      +
      +#endif
      
     - ## reftable/reftable.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     -+
     -+Use of this source code is governed by a BSD-style
     -+license that can be found in the LICENSE file or at
     -+https://developers.google.com/open-source/licenses/bsd
     -+*/
     -+
     -+#include "record.h"
     -+#include "reader.h"
     -+#include "reftable-iterator.h"
     -+#include "reftable-generic.h"
     -+
     -+static int reftable_reader_seek_void(void *tab, struct reftable_iterator *it,
     -+				     struct reftable_record *rec)
     -+{
     -+	return reader_seek((struct reftable_reader *)tab, it, rec);
     -+}
     -+
     -+static uint32_t reftable_reader_hash_id_void(void *tab)
     -+{
     -+	return reftable_reader_hash_id((struct reftable_reader *)tab);
     -+}
     -+
     -+static uint64_t reftable_reader_min_update_index_void(void *tab)
     -+{
     -+	return reftable_reader_min_update_index((struct reftable_reader *)tab);
     -+}
     -+
     -+static uint64_t reftable_reader_max_update_index_void(void *tab)
     -+{
     -+	return reftable_reader_max_update_index((struct reftable_reader *)tab);
     -+}
     -+
     -+static struct reftable_table_vtable reader_vtable = {
     -+	.seek_record = reftable_reader_seek_void,
     -+	.hash_id = reftable_reader_hash_id_void,
     -+	.min_update_index = reftable_reader_min_update_index_void,
     -+	.max_update_index = reftable_reader_max_update_index_void,
     -+};
     -+
     -+int reftable_table_seek_ref(struct reftable_table *tab,
     -+			    struct reftable_iterator *it, const char *name)
     -+{
     -+	struct reftable_ref_record ref = {
     -+		.refname = (char *)name,
     -+	};
     -+	struct reftable_record rec = { NULL };
     -+	reftable_record_from_ref(&rec, &ref);
     -+	return tab->ops->seek_record(tab->table_arg, it, &rec);
     -+}
     -+
     -+void reftable_table_from_reader(struct reftable_table *tab,
     -+				struct reftable_reader *reader)
     -+{
     -+	assert(tab->ops == NULL);
     -+	tab->ops = &reader_vtable;
     -+	tab->table_arg = reader;
     -+}
     -+
     -+int reftable_table_read_ref(struct reftable_table *tab, const char *name,
     -+			    struct reftable_ref_record *ref)
     -+{
     -+	struct reftable_iterator it = { NULL };
     -+	int err = reftable_table_seek_ref(tab, &it, name);
     -+	if (err)
     -+		goto done;
     -+
     -+	err = reftable_iterator_next_ref(&it, ref);
     -+	if (err)
     -+		goto done;
     -+
     -+	if (strcmp(ref->refname, name) ||
     -+	    reftable_ref_record_is_deletion(ref)) {
     -+		reftable_ref_record_release(ref);
     -+		err = 1;
     -+		goto done;
     -+	}
     -+
     -+done:
     -+	reftable_iterator_destroy(&it);
     -+	return err;
     -+}
     -+
     -+uint64_t reftable_table_max_update_index(struct reftable_table *tab)
     -+{
     -+	return tab->ops->max_update_index(tab->table_arg);
     -+}
     -+
     -+uint64_t reftable_table_min_update_index(struct reftable_table *tab)
     -+{
     -+	return tab->ops->min_update_index(tab->table_arg);
     -+}
     -+
     -+uint32_t reftable_table_hash_id(struct reftable_table *tab)
     -+{
     -+	return tab->ops->hash_id(tab->table_arg);
     -+}
     -
       ## reftable/stack.c (new) ##
      @@
      +/*
     @@ reftable/stack.c (new)
      +#include "refname.h"
      +#include "reftable-error.h"
      +#include "reftable-record.h"
     ++#include "reftable-merged.h"
      +#include "writer.h"
      +
      +static int stack_try_add(struct reftable_stack *st,
     @@ reftable/stack.c (new)
      +static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
      +					     int reuse_open);
      +
     ++static void stack_filename(struct strbuf *dest, struct reftable_stack *st,
     ++			   const char *name)
     ++{
     ++	strbuf_reset(dest);
     ++	strbuf_addstr(dest, st->reftable_dir);
     ++	strbuf_addstr(dest, "/");
     ++	strbuf_addstr(dest, name);
     ++}
     ++
      +static int reftable_fd_write(void *arg, const void *data, size_t sz)
      +{
      +	int *fdp = (int *)arg;
     @@ reftable/stack.c (new)
      +	return st->merged;
      +}
      +
     ++static int has_name(char **names, const char *name)
     ++{
     ++	while (*names) {
     ++		if (!strcmp(*names, name))
     ++			return 1;
     ++		names++;
     ++	}
     ++	return 0;
     ++}
     ++
      +/* Close and free the stack */
      +void reftable_stack_destroy(struct reftable_stack *st)
      +{
     ++	char **names = NULL;
     ++	int err = 0;
      +	if (st->merged != NULL) {
      +		reftable_merged_table_free(st->merged);
      +		st->merged = NULL;
      +	}
      +
     ++	err = read_lines(st->list_file, &names);
     ++	if (err < 0) {
     ++		FREE_AND_NULL(names);
     ++	}
     ++
      +	if (st->readers != NULL) {
      +		int i = 0;
     ++		struct strbuf filename = STRBUF_INIT;
      +		for (i = 0; i < st->readers_len; i++) {
     ++			const char *name = reader_name(st->readers[i]);
     ++			strbuf_reset(&filename);
     ++			if (names && !has_name(names, name)) {
     ++				stack_filename(&filename, st, name);
     ++			}
      +			reftable_reader_free(st->readers[i]);
     ++
     ++			if (filename.len) {
     ++				// On Windows, can only unlink after closing.
     ++				unlink(filename.buf);
     ++			}
      +		}
     ++		strbuf_release(&filename);
      +		st->readers_len = 0;
      +		FREE_AND_NULL(st->readers);
      +	}
      +	FREE_AND_NULL(st->list_file);
      +	FREE_AND_NULL(st->reftable_dir);
      +	reftable_free(st);
     ++	free_names(names);
      +}
      +
      +static struct reftable_reader **stack_copy_readers(struct reftable_stack *st,
     @@ reftable/stack.c (new)
      +		if (rd == NULL) {
      +			struct reftable_block_source src = { NULL };
      +			struct strbuf table_path = STRBUF_INIT;
     -+			strbuf_addstr(&table_path, st->reftable_dir);
     -+			strbuf_addstr(&table_path, "/");
     -+			strbuf_addstr(&table_path, name);
     ++			stack_filename(&table_path, st, name);
      +
      +			err = reftable_block_source_from_file(&src,
      +							      table_path.buf);
     @@ reftable/stack.c (new)
      +	st->merged = new_merged;
      +	for (i = 0; i < cur_len; i++) {
      +		if (cur[i] != NULL) {
     ++			const char *name = reader_name(cur[i]);
     ++			struct strbuf filename = STRBUF_INIT;
     ++			stack_filename(&filename, st, name);
     ++
      +			reader_close(cur[i]);
      +			reftable_reader_free(cur[i]);
     ++
     ++			// On Windows, can only unlink after closing.
     ++			unlink(filename.buf);
     ++
     ++			strbuf_release(&filename);
      +		}
      +	}
      +
     @@ reftable/stack.c (new)
      +	int i = 0;
      +	struct strbuf nm = STRBUF_INIT;
      +	for (i = 0; i < add->new_tables_len; i++) {
     -+		strbuf_reset(&nm);
     -+		strbuf_addstr(&nm, add->stack->reftable_dir);
     -+		strbuf_addstr(&nm, "/");
     -+		strbuf_addstr(&nm, add->new_tables[i]);
     ++		stack_filename(&nm, add->stack, add->new_tables[i]);
      +		unlink(nm.buf);
      +		reftable_free(add->new_tables[i]);
      +		add->new_tables[i] = NULL;
     @@ reftable/stack.c (new)
      +	strbuf_reset(&next_name);
      +	format_name(&next_name, add->next_update_index, add->next_update_index);
      +
     -+	strbuf_addstr(&temp_tab_file_name, add->stack->reftable_dir);
     -+	strbuf_addstr(&temp_tab_file_name, "/");
     -+	strbuf_addbuf(&temp_tab_file_name, &next_name);
     ++	stack_filename(&temp_tab_file_name, add->stack, next_name.buf);
      +	strbuf_addstr(&temp_tab_file_name, ".temp.XXXXXX");
      +
      +	tab_fd = mkstemp(temp_tab_file_name.buf);
     @@ reftable/stack.c (new)
      +	format_name(&next_name, wr->min_update_index, wr->max_update_index);
      +	strbuf_addstr(&next_name, ".ref");
      +
     -+	strbuf_addstr(&tab_file_name, add->stack->reftable_dir);
     -+	strbuf_addstr(&tab_file_name, "/");
     -+	strbuf_addbuf(&tab_file_name, &next_name);
     ++	stack_filename(&tab_file_name, add->stack, next_name.buf);
      +
      +	/*
      +	  On windows, this relies on rand() picking a unique destination name.
     @@ reftable/stack.c (new)
      +		    reftable_reader_min_update_index(st->readers[first]),
      +		    reftable_reader_max_update_index(st->readers[last]));
      +
     -+	strbuf_reset(temp_tab);
     -+	strbuf_addstr(temp_tab, st->reftable_dir);
     -+	strbuf_addstr(temp_tab, "/");
     -+	strbuf_addbuf(temp_tab, &next_name);
     ++	stack_filename(temp_tab, st, next_name.buf);
      +	strbuf_addstr(temp_tab, ".temp.XXXXXX");
      +
      +	tab_fd = mkstemp(temp_tab->buf);
     @@ reftable/stack.c (new)
      +		struct strbuf subtab_lock = STRBUF_INIT;
      +		int sublock_file_fd = -1;
      +
     -+		strbuf_addstr(&subtab_file_name, st->reftable_dir);
     -+		strbuf_addstr(&subtab_file_name, "/");
     -+		strbuf_addstr(&subtab_file_name, reader_name(st->readers[i]));
     ++		stack_filename(&subtab_file_name, st,
     ++			       reader_name(st->readers[i]));
      +
      +		strbuf_reset(&subtab_lock);
      +		strbuf_addbuf(&subtab_lock, &subtab_file_name);
     @@ reftable/stack.c (new)
      +		    st->readers[last]->max_update_index);
      +	strbuf_addstr(&new_table_name, ".ref");
      +
     -+	strbuf_reset(&new_table_path);
     -+	strbuf_addstr(&new_table_path, st->reftable_dir);
     -+	strbuf_addstr(&new_table_path, "/");
     -+	strbuf_addbuf(&new_table_path, &new_table_name);
     ++	stack_filename(&new_table_path, st, new_table_name.buf);
      +
      +	if (!is_empty_table) {
      +		/* retry? */
     @@ reftable/stack.c (new)
      +	reftable_iterator_destroy(&it);
      +	reftable_reader_free(rd);
      +	return err;
     ++}
     ++
     ++static int is_table_name(const char *s)
     ++{
     ++	const char *dot = strrchr(s, '.');
     ++	return dot != NULL && !strcmp(dot, ".ref");
     ++}
     ++
     ++static void remove_maybe_stale_table(struct reftable_stack *st, uint64_t max,
     ++				     const char *name)
     ++{
     ++	int err = 0;
     ++	uint64_t update_idx = 0;
     ++	struct reftable_block_source src = { NULL };
     ++	struct reftable_reader *rd = NULL;
     ++	struct strbuf table_path = STRBUF_INIT;
     ++	stack_filename(&table_path, st, name);
     ++
     ++	err = reftable_block_source_from_file(&src, table_path.buf);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	err = reftable_new_reader(&rd, &src, name);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	update_idx = reftable_reader_max_update_index(rd);
     ++	reftable_reader_free(rd);
     ++
     ++	if (update_idx <= max) {
     ++		unlink(table_path.buf);
     ++	}
     ++done:
     ++	strbuf_release(&table_path);
     ++}
     ++
     ++static int reftable_stack_clean_locked(struct reftable_stack *st)
     ++{
     ++	uint64_t max = reftable_merged_table_max_update_index(
     ++		reftable_stack_merged_table(st));
     ++	DIR *dir = opendir(st->reftable_dir);
     ++	struct dirent *d = NULL;
     ++	if (dir == NULL) {
     ++		return REFTABLE_IO_ERROR;
     ++	}
     ++
     ++	while ((d = readdir(dir)) != NULL) {
     ++		int i = 0;
     ++		int found = 0;
     ++		if (!is_table_name(d->d_name))
     ++			continue;
     ++
     ++		for (i = 0; !found && i < st->readers_len; i++) {
     ++			found = !strcmp(reader_name(st->readers[i]), d->d_name);
     ++		}
     ++		if (found)
     ++			continue;
     ++
     ++		remove_maybe_stale_table(st, max, d->d_name);
     ++	}
     ++
     ++	closedir(dir);
     ++	return 0;
     ++}
     ++
     ++int reftable_stack_clean(struct reftable_stack *st)
     ++{
     ++	struct reftable_addition *add = NULL;
     ++	int err = reftable_stack_new_addition(&add, st);
     ++	if (err < 0) {
     ++		goto done;
     ++	}
     ++
     ++	err = reftable_stack_reload(st);
     ++	if (err < 0) {
     ++		goto done;
     ++	}
     ++
     ++	err = reftable_stack_clean_locked(st);
     ++
     ++done:
     ++	reftable_addition_destroy(add);
     ++	return err;
      +}
      
       ## reftable/stack.h (new) ##
     @@ reftable/stack_test.c (new)
      +
      +#include "system.h"
      +
     ++#include "reftable-reader.h"
      +#include "merged.h"
      +#include "basics.h"
      +#include "constants.h"
     @@ reftable/stack_test.c (new)
      +	strbuf_release(&path);
      +}
      +
     ++static int count_dir_entries(const char *dirname)
     ++{
     ++	DIR *dir = opendir(dirname);
     ++	int len = 0;
     ++	struct dirent *d;
     ++	if (dir == NULL)
     ++		return 0;
     ++
     ++	while ((d = readdir(dir)) != NULL) {
     ++		if (!strcmp(d->d_name, "..") || !strcmp(d->d_name, "."))
     ++			continue;
     ++		len++;
     ++	}
     ++	closedir(dir);
     ++	return len;
     ++}
     ++
      +static char *get_tmp_template(const char *prefix)
      +{
      +	const char *tmp = getenv("TMPDIR");
     @@ reftable/stack_test.c (new)
      +	clear_dir(dir);
      +}
      +
     ++static void test_reftable_stack_compaction_concurrent(void)
     ++{
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st1 = NULL, *st2 = NULL;
     ++	char *dir = get_tmp_template(__FUNCTION__);
     ++	int err, i;
     ++	int N = 3;
     ++	EXPECT(mkdtemp(dir));
     ++
     ++	err = reftable_new_stack(&st1, dir, cfg);
     ++	EXPECT_ERR(err);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		char name[100];
     ++		struct reftable_ref_record ref = {
     ++			.refname = name,
     ++			.update_index = reftable_stack_next_update_index(st1),
     ++			.value_type = REFTABLE_REF_SYMREF,
     ++			.value.symref = "master",
     ++		};
     ++		snprintf(name, sizeof(name), "branch%04d", i);
     ++
     ++		err = reftable_stack_add(st1, &write_test_ref, &ref);
     ++		EXPECT_ERR(err);
     ++	}
     ++
     ++	err = reftable_new_stack(&st2, dir, cfg);
     ++	EXPECT_ERR(err);
     ++
     ++	err = reftable_stack_compact_all(st1, NULL);
     ++	EXPECT_ERR(err);
     ++
     ++	reftable_stack_destroy(st1);
     ++	reftable_stack_destroy(st2);
     ++
     ++	EXPECT(count_dir_entries(dir) == 2);
     ++	clear_dir(dir);
     ++}
     ++
     ++static void unclean_stack_close(struct reftable_stack *st)
     ++{
     ++	// break abstraction boundary to simulate unclean shutdown.
     ++	int i = 0;
     ++	for (; i < st->readers_len; i++) {
     ++		reftable_reader_free(st->readers[i]);
     ++	}
     ++	st->readers_len = 0;
     ++	FREE_AND_NULL(st->readers);
     ++}
     ++
     ++static void test_reftable_stack_compaction_concurrent_clean(void)
     ++{
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st1 = NULL, *st2 = NULL, *st3 = NULL;
     ++	char *dir = get_tmp_template(__FUNCTION__);
     ++	int err, i;
     ++	int N = 3;
     ++	EXPECT(mkdtemp(dir));
     ++
     ++	err = reftable_new_stack(&st1, dir, cfg);
     ++	EXPECT_ERR(err);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		char name[100];
     ++		struct reftable_ref_record ref = {
     ++			.refname = name,
     ++			.update_index = reftable_stack_next_update_index(st1),
     ++			.value_type = REFTABLE_REF_SYMREF,
     ++			.value.symref = "master",
     ++		};
     ++		snprintf(name, sizeof(name), "branch%04d", i);
     ++
     ++		err = reftable_stack_add(st1, &write_test_ref, &ref);
     ++		EXPECT_ERR(err);
     ++	}
     ++
     ++	err = reftable_new_stack(&st2, dir, cfg);
     ++	EXPECT_ERR(err);
     ++
     ++	err = reftable_stack_compact_all(st1, NULL);
     ++	EXPECT_ERR(err);
     ++
     ++	unclean_stack_close(st1);
     ++	unclean_stack_close(st2);
     ++
     ++	err = reftable_new_stack(&st3, dir, cfg);
     ++	EXPECT_ERR(err);
     ++
     ++	err = reftable_stack_clean(st3);
     ++	EXPECT_ERR(err);
     ++	EXPECT(count_dir_entries(dir) == 2);
     ++
     ++	reftable_stack_destroy(st1);
     ++	reftable_stack_destroy(st2);
     ++	reftable_stack_destroy(st3);
     ++
     ++	clear_dir(dir);
     ++}
     ++
      +int stack_test_main(int argc, const char *argv[])
      +{
     ++	RUN_TEST(test_reftable_stack_compaction_concurrent_clean);
     ++	RUN_TEST(test_reftable_stack_compaction_concurrent);
      +	RUN_TEST(test_reftable_stack_uptodate);
      +	RUN_TEST(test_reftable_stack_transaction_api);
      +	RUN_TEST(test_reftable_stack_hash_id);
     @@ reftable/stack_test.c (new)
      
       ## t/helper/test-reftable.c ##
      @@ t/helper/test-reftable.c: int cmd__reftable(int argc, const char **argv)
     - {
     - 	basics_test_main(argc, argv);
     - 	block_test_main(argc, argv);
     -+	merged_test_main(argc, argv);
       	record_test_main(argc, argv);
     -+	refname_test_main(argc, argv);
     + 	refname_test_main(argc, argv);
       	reftable_test_main(argc, argv);
      +	stack_test_main(argc, argv);
       	tree_test_main(argc, argv);
  -:  ------------ > 17:  5db7c8ab7f23 reftable: add dump utility
 13:  bdb19af22cc7 ! 18:  2dc73bf2ec96 Reftable support for git-core
     @@ Makefile: LIB_OBJS += reflog-walk.o
       LIB_OBJS += refs/iterator.o
       LIB_OBJS += refs/packed-backend.o
       LIB_OBJS += refs/ref-cache.o
     -@@ Makefile: REFTABLE_OBJS += reftable/zlib-compat.o
     - 
     - REFTABLE_TEST_OBJS += reftable/basics_test.o
     - REFTABLE_TEST_OBJS += reftable/block_test.o
     -+REFTABLE_TEST_OBJS += reftable/merged_test.o
     - REFTABLE_TEST_OBJS += reftable/record_test.o
     -+REFTABLE_TEST_OBJS += reftable/refname_test.o
     - REFTABLE_TEST_OBJS += reftable/reftable_test.o
     -+REFTABLE_TEST_OBJS += reftable/stack_test.o
     - REFTABLE_TEST_OBJS += reftable/test_framework.o
     - REFTABLE_TEST_OBJS += reftable/tree_test.o
     - 
      
       ## builtin/clone.c ##
      @@ builtin/clone.c: int cmd_clone(int argc, const char **argv, const char *prefix)
     @@ builtin/init-db.c: static int needs_work_tree_config(const char *git_dir, const
       
       	/* This forces creation of new config file */
      @@ builtin/init-db.c: static int create_default_files(const char *template_path,
     - 	is_bare_repository_cfg = init_is_bare_repository;
     + 	is_bare_repository_cfg = init_is_bare_repository || !work_tree;
       	if (init_shared_repository != -1)
       		set_shared_repository(init_shared_repository);
      +	the_repository->ref_storage_format = xstrdup(fmt->ref_storage);
     @@ refs/reftable-backend.c (new)
      +	err = reftable_stack_compact_all(refs->main_stack, NULL);
      +	if (err == 0 && refs->worktree_stack != NULL)
      +		err = reftable_stack_compact_all(refs->worktree_stack, NULL);
     ++	if (err == 0)
     ++		err = reftable_stack_clean(refs->main_stack);
     ++	if (err == 0 && refs->worktree_stack != NULL)
     ++		err = reftable_stack_clean(refs->worktree_stack);
     ++
      +	return err;
      +}
      +
 14:  0d9477941678 = 19:  b2fa6ea62c16 git-prompt: prepare for reftable refs backend
 15:  59f432522230 ! 20:  39e644b9436b Add "test-tool dump-reftable" command.
     @@ Makefile: REFTABLE_OBJS += reftable/zlib-compat.o
       REFTABLE_TEST_OBJS += reftable/block_test.o
      +REFTABLE_TEST_OBJS += reftable/dump.o
       REFTABLE_TEST_OBJS += reftable/merged_test.o
     + REFTABLE_TEST_OBJS += reftable/pq_test.o
       REFTABLE_TEST_OBJS += reftable/record_test.o
     - REFTABLE_TEST_OBJS += reftable/refname_test.o
      
       ## reftable/dump.c ##
      @@ reftable/dump.c: license that can be found in the LICENSE file or at

-- 
gitgitgadget