Subject: [PATCH v16 00/14] Reftable support git-core

From: "Han-Wen Nienhuys via GitGitGadget" <[email-masked]>
Date: Fri, 05 Jun 2020 18:03:04 +0000

This adds the reftable library, and hooks it up as a ref backend. Based on
hn/refs-cleanup.

Includes testing support, to test: make -C t/ GIT_TEST_REFTABLE=1

Summary 20479 tests pass 1299 tests fail

Some issues:

 * many tests inspect .git/{logs,heads}/ directly.
 * worktrees broken. 

v18

 * fix pseudo ref usage
 * import and execute unittests too.

Han-Wen Nienhuys (13):
  Write pseudorefs through ref backends.
  Make refs_ref_exists public
  Treat BISECT_HEAD as a pseudo ref
  Treat CHERRY_PICK_HEAD as a pseudo ref
  Treat REVERT_HEAD as a pseudo ref
  Move REF_LOG_ONLY to refs-internal.h
  Iterate over the "refs/" namespace in for_each_[raw]ref
  Add .gitattributes for the reftable/ directory
  Add reftable library
  Reftable support for git-core
  Hookup unittests for the reftable library.
  Add GIT_DEBUG_REFS debugging mechanism
  Add reftable testing infrastructure

Johannes Schindelin (1):
  vcxproj: adjust for the reftable changes

 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   45 +-
 builtin/bisect--helper.c                      |    3 +-
 builtin/clone.c                               |    3 +-
 builtin/commit.c                              |   34 +-
 builtin/init-db.c                             |   56 +-
 builtin/merge.c                               |    2 +-
 cache.h                                       |    6 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 git-bisect.sh                                 |    4 +-
 path.c                                        |    2 -
 path.h                                        |    9 +-
 refs.c                                        |  157 +-
 refs.h                                        |   16 +
 refs/debug.c                                  |  309 ++++
 refs/files-backend.c                          |  121 +-
 refs/packed-backend.c                         |   21 +-
 refs/refs-internal.h                          |   32 +
 refs/reftable-backend.c                       | 1331 +++++++++++++++++
 reftable/.gitattributes                       |    1 +
 reftable/LICENSE                              |   31 +
 reftable/README.md                            |   11 +
 reftable/VERSION                              |    1 +
 reftable/basics.c                             |  215 +++
 reftable/basics.h                             |   53 +
 reftable/block.c                              |  433 ++++++
 reftable/block.h                              |  129 ++
 reftable/block_test.c                         |  156 ++
 reftable/constants.h                          |   21 +
 reftable/file.c                               |   95 ++
 reftable/iter.c                               |  243 +++
 reftable/iter.h                               |   72 +
 reftable/merged.c                             |  320 ++++
 reftable/merged.h                             |   39 +
 reftable/merged_test.c                        |  273 ++++
 reftable/pq.c                                 |  113 ++
 reftable/pq.h                                 |   34 +
 reftable/reader.c                             |  742 +++++++++
 reftable/reader.h                             |   65 +
 reftable/record.c                             | 1113 ++++++++++++++
 reftable/record.h                             |  128 ++
 reftable/record_test.c                        |  400 +++++
 reftable/refname.c                            |  209 +++
 reftable/refname.h                            |   38 +
 reftable/refname_test.c                       |   99 ++
 reftable/reftable-tests.h                     |   13 +
 reftable/reftable.c                           |   90 ++
 reftable/reftable.h                           |  564 +++++++
 reftable/reftable_test.c                      |  631 ++++++++
 reftable/slice.c                              |  243 +++
 reftable/slice.h                              |   87 ++
 reftable/slice_test.c                         |   40 +
 reftable/stack.c                              | 1207 +++++++++++++++
 reftable/stack.h                              |   48 +
 reftable/stack_test.c                         |  743 +++++++++
 reftable/system.h                             |   54 +
 reftable/test_framework.c                     |   69 +
 reftable/test_framework.h                     |   64 +
 reftable/tree.c                               |   63 +
 reftable/tree.h                               |   34 +
 reftable/tree_test.c                          |   62 +
 reftable/update.sh                            |   25 +
 reftable/writer.c                             |  644 ++++++++
 reftable/writer.h                             |   60 +
 reftable/zlib-compat.c                        |   92 ++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 sequencer.c                                   |   56 +-
 setup.c                                       |   12 +-
 t/helper/test-tool.c                          |    1 +
 t/helper/test-tool.h                          |    1 +
 t/t0031-reftable.sh                           |  147 ++
 t/t0033-debug-refs.sh                         |   18 +
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1450-fsck.sh                               |    6 +
 t/t3210-pack-refs.sh                          |    6 +
 t/t9903-bash-prompt.sh                        |    6 +
 t/test-lib.sh                                 |    5 +
 wt-status.c                                   |    6 +-
 80 files changed, 12118 insertions(+), 195 deletions(-)
 create mode 100644 refs/debug.c
 create mode 100644 refs/reftable-backend.c
 create mode 100644 reftable/.gitattributes
 create mode 100644 reftable/LICENSE
 create mode 100644 reftable/README.md
 create mode 100644 reftable/VERSION
 create mode 100644 reftable/basics.c
 create mode 100644 reftable/basics.h
 create mode 100644 reftable/block.c
 create mode 100644 reftable/block.h
 create mode 100644 reftable/block_test.c
 create mode 100644 reftable/constants.h
 create mode 100644 reftable/file.c
 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/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-tests.h
 create mode 100644 reftable/reftable.c
 create mode 100644 reftable/reftable.h
 create mode 100644 reftable/reftable_test.c
 create mode 100644 reftable/slice.c
 create mode 100644 reftable/slice.h
 create mode 100644 reftable/slice_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 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c
 create mode 100755 t/t0031-reftable.sh
 create mode 100755 t/t0033-debug-refs.sh

base-commit: aada2199e11bff14ee91d5d590c2e3d3eba5e148
Published-As: https://github.com/gitgitgadget/git/releases/tag/pr-539%2Fhanwen%2Freftable-v16
Fetch-It-Via: git fetch https://github.com/gitgitgadget/git pr-539/hanwen/reftable-v16
Pull-Request: https://github.com/gitgitgadget/git/pull/539

Range-diff vs v15:

  1:  9bb64f748dc !  1:  4a1f600fb85 Write pseudorefs through ref backends.
     @@ refs/refs-internal.h: typedef int copy_ref_fn(struct ref_store *ref_store,
      +			       const struct object_id *oid,
      +			       const struct object_id *old_oid,
      +			       struct strbuf *err);
     ++
     ++/*
     ++ * Deletes a pseudoref. Deletion always succeeds (even if the pseudoref doesn't
     ++ * exist.), except if old_oid is specified. If it is, it can fail due to lock
     ++ * failure, failure reading the old OID, or an OID mismatch
     ++ */
      +typedef int delete_pseudoref_fn(struct ref_store *ref_store,
      +				const char *pseudoref,
      +				const struct object_id *old_oid);
  2:  d489806907b =  2:  a4a67ce9635 Make refs_ref_exists public
  3:  60a82678a1b =  3:  ecd6591d86f Treat BISECT_HEAD as a pseudo ref
  4:  1a925f5671a !  4:  7c31727de69 Treat CHERRY_PICK_HEAD as a pseudo ref
     @@ sequencer.c: static int commit_staged_changes(struct repository *r,
      -		if (file_exists(cherry_pick_head) && unlink(cherry_pick_head))
      +		if (refs_ref_exists(get_main_ref_store(r),
      +				    "CHERRY_PICK_HEAD") &&
     -+		    !refs_delete_pseudoref(get_main_ref_store(r),
     -+					   "CHERRY_PICK_HEAD", NULL))
     ++		    refs_delete_pseudoref(get_main_ref_store(r),
     ++					  "CHERRY_PICK_HEAD", NULL))
       			return error(_("could not remove CHERRY_PICK_HEAD"));
       		if (!final_fixup)
       			return 0;
  5:  8f2ebf65b90 !  5:  fbdcee5208b Treat REVERT_HEAD as a pseudo ref
     @@ sequencer.c: static int create_seq_dir(struct repository *r)
       	const char *in_progress_advice = NULL;
       	unsigned int advise_skip =
      -		file_exists(git_path_revert_head(r)) ||
     --		refs_ref_exists(get_main_ref_store(r), "CHERRY_PICK_HEAD");
     -+		refs_ref_exists(get_main_ref_store(r), "REVERT_HEAD");
     -+	refs_ref_exists(get_main_ref_store(r), "CHERRY_PICK_HEAD");
     ++		refs_ref_exists(get_main_ref_store(r), "REVERT_HEAD") ||
     + 		refs_ref_exists(get_main_ref_store(r), "CHERRY_PICK_HEAD");
       
       	if (!sequencer_get_last_command(r, &action)) {
     - 		switch (action) {
      @@ sequencer.c: static int rollback_single_pick(struct repository *r)
       	struct object_id head_oid;
       
  6:  e0e1e3a558d =  6:  d8801367f7d Move REF_LOG_ONLY to refs-internal.h
  7:  27a980d1d9d =  7:  556d57610cc Iterate over the "refs/" namespace in for_each_[raw]ref
  8:  dcbd000e7f7 =  8:  78cb1930172 Add .gitattributes for the reftable/ directory
  9:  718b646a54e !  9:  0bc28ac610f Add reftable library
     @@ reftable/README.md (new)
      
       ## reftable/VERSION (new) ##
      @@
     -+commit fe15c65dd95b6a13de92b4baf711e50338ef20ae
     -+Author: Han-Wen Nienhuys <[email-masked]>
     -+Date:   Thu May 28 19:28:24 2020 +0200
     -+
     -+    C: add 'canary' to struct slice
     -+    
     -+    This enforces that all slices are initialized explicitly with
     -+    SLICE_INIT, for future compatibility with git's strbuf.
     ++0c164275ea8f8aa7d099f7425ddcef1affe137e9 C: compile framework with Git options
      
       ## reftable/basics.c (new) ##
      @@
     @@ reftable/block.c (new)
      +}
      +
      +int block_writer_register_restart(struct block_writer *w, int n, bool restart,
     -+				  struct slice key);
     ++				  struct slice *key);
      +
      +void block_writer_init(struct block_writer *bw, byte typ, byte *buf,
      +		       uint32_t block_size, uint32_t header_off, int hash_size)
     @@ reftable/block.c (new)
      +	slice_consume(&out, n);
      +
      +	if (block_writer_register_restart(w, start.len - out.len, restart,
     -+					  key) < 0)
     ++					  &key) < 0)
      +		goto done;
      +
      +	slice_release(&key);
     @@ reftable/block.c (new)
      +}
      +
      +int block_writer_register_restart(struct block_writer *w, int n, bool restart,
     -+				  struct slice key)
     ++				  struct slice *key)
      +{
      +	int rlen = w->restart_len;
      +	if (rlen >= MAX_RESTARTS) {
     @@ reftable/block.c (new)
      +		return -1;
      +	}
      +
     -+	result = slice_cmp(a->key, rkey);
     ++	result = slice_cmp(&a->key, &rkey);
      +	slice_release(&rkey);
      +	return result;
      +}
     @@ reftable/block.c (new)
      +{
      +	dest->br = src->br;
      +	dest->next_off = src->next_off;
     -+	slice_copy(&dest->last_key, src->last_key);
     ++	slice_copy(&dest->last_key, &src->last_key);
      +}
      +
      +int block_iter_next(struct block_iter *it, struct reftable_record *rec)
     @@ reftable/block.c (new)
      +		return -1;
      +	slice_consume(&in, n);
      +
     -+	slice_copy(&it->last_key, key);
     ++	slice_copy(&it->last_key, &key);
      +	it->next_off += start.len - in.len;
      +	slice_release(&key);
      +	return 0;
     @@ reftable/block.c (new)
      +	return 0;
      +}
      +
     -+int block_iter_seek(struct block_iter *it, struct slice want)
     ++int block_iter_seek(struct block_iter *it, struct slice *want)
      +{
      +	return block_reader_seek(it->br, it, want);
      +}
     @@ reftable/block.c (new)
      +}
      +
      +int block_reader_seek(struct block_reader *br, struct block_iter *it,
     -+		      struct slice want)
     ++		      struct slice *want)
      +{
      +	struct restart_find_args args = {
     -+		.key = want,
     ++		.key = *want,
      +		.r = br,
      +	};
      +	struct reftable_record rec = reftable_new_record(block_reader_type(br));
     @@ reftable/block.c (new)
      +			goto done;
      +
      +		reftable_record_key(&rec, &key);
     -+		if (err > 0 || slice_cmp(key, want) >= 0) {
     ++		if (err > 0 || slice_cmp(&key, want) >= 0) {
      +			err = 0;
      +			goto done;
      +		}
     @@ reftable/block.h (new)
      +
      +/* Position `it` to the `want` key in the block */
      +int block_reader_seek(struct block_reader *br, struct block_iter *it,
     -+		      struct slice want);
     ++		      struct slice *want);
      +
      +/* Returns the block type (eg. 'r' for refs) */
      +byte block_reader_type(struct block_reader *r);
     @@ reftable/block.h (new)
      +int block_iter_next(struct block_iter *it, struct reftable_record *rec);
      +
      +/* Seek to `want` with in the block pointed to by `it` */
     -+int block_iter_seek(struct block_iter *it, struct slice want);
     ++int block_iter_seek(struct block_iter *it, struct slice *want);
      +
      +/* deallocate memory for `it`. The block reader and its block is left intact. */
      +void block_iter_close(struct block_iter *it);
     @@ reftable/block.h (new)
      +
      +#endif
      
     + ## reftable/block_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 "block.h"
     ++
     ++#include "system.h"
     ++
     ++#include "basics.h"
     ++#include "constants.h"
     ++#include "record.h"
     ++#include "reftable.h"
     ++#include "test_framework.h"
     ++#include "reftable-tests.h"
     ++
     ++struct binsearch_args {
     ++	int key;
     ++	int *arr;
     ++};
     ++
     ++static int binsearch_func(size_t i, void *void_args)
     ++{
     ++	struct binsearch_args *args = (struct binsearch_args *)void_args;
     ++
     ++	return args->key < args->arr[i];
     ++}
     ++
     ++static void test_binsearch(void)
     ++{
     ++	int arr[] = { 2, 4, 6, 8, 10 };
     ++	size_t sz = ARRAY_SIZE(arr);
     ++	struct binsearch_args args = {
     ++		.arr = arr,
     ++	};
     ++
     ++	int i = 0;
     ++	for (i = 1; i < 11; i++) {
     ++		int res;
     ++		args.key = i;
     ++		res = binsearch(sz, &binsearch_func, &args);
     ++
     ++		if (res < sz) {
     ++			assert(args.key < arr[res]);
     ++			if (res > 0) {
     ++				assert(args.key >= arr[res - 1]);
     ++			}
     ++		} else {
     ++			assert(args.key == 10 || args.key == 11);
     ++		}
     ++	}
     ++}
     ++
     ++static void test_block_read_write(void)
     ++{
     ++	const int header_off = 21; /* random */
     ++	char *names[30];
     ++	const int N = ARRAY_SIZE(names);
     ++	const int block_size = 1024;
     ++	struct reftable_block block = { 0 };
     ++	struct block_writer bw = {
     ++		.last_key = SLICE_INIT,
     ++	};
     ++	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_record rec = { 0 };
     ++	int i = 0;
     ++	int n;
     ++	struct block_reader br = { 0 };
     ++	struct block_iter it = { .last_key = SLICE_INIT };
     ++	int j = 0;
     ++	struct slice want = SLICE_INIT;
     ++
     ++	block.data = reftable_calloc(block_size);
     ++	block.len = block_size;
     ++	block.source = malloc_block_source();
     ++	block_writer_init(&bw, BLOCK_TYPE_REF, block.data, block_size,
     ++			  header_off, hash_size(SHA1_ID));
     ++	reftable_record_from_ref(&rec, &ref);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		char name[100];
     ++		byte hash[SHA1_SIZE];
     ++		snprintf(name, sizeof(name), "branch%02d", i);
     ++		memset(hash, i, sizeof(hash));
     ++
     ++		ref.ref_name = name;
     ++		ref.value = hash;
     ++		names[i] = xstrdup(name);
     ++		n = block_writer_add(&bw, &rec);
     ++		ref.ref_name = NULL;
     ++		ref.value = NULL;
     ++		assert(n == 0);
     ++	}
     ++
     ++	n = block_writer_finish(&bw);
     ++	assert(n > 0);
     ++
     ++	block_writer_clear(&bw);
     ++
     ++	block_reader_init(&br, &block, header_off, block_size, SHA1_SIZE);
     ++
     ++	block_reader_start(&br, &it);
     ++
     ++	while (true) {
     ++		int r = block_iter_next(&it, &rec);
     ++		assert(r >= 0);
     ++		if (r > 0) {
     ++			break;
     ++		}
     ++		assert_streq(names[j], ref.ref_name);
     ++		j++;
     ++	}
     ++
     ++	reftable_record_clear(&rec);
     ++	block_iter_close(&it);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		struct block_iter it = { .last_key = SLICE_INIT };
     ++		slice_set_string(&want, names[i]);
     ++
     ++		n = block_reader_seek(&br, &it, &want);
     ++		assert(n == 0);
     ++
     ++		n = block_iter_next(&it, &rec);
     ++		assert(n == 0);
     ++
     ++		assert_streq(names[i], ref.ref_name);
     ++
     ++		want.len--;
     ++		n = block_reader_seek(&br, &it, &want);
     ++		assert(n == 0);
     ++
     ++		n = block_iter_next(&it, &rec);
     ++		assert(n == 0);
     ++		assert_streq(names[10 * (i / 10)], ref.ref_name);
     ++
     ++		block_iter_close(&it);
     ++	}
     ++
     ++	reftable_record_clear(&rec);
     ++	reftable_block_done(&br.block);
     ++	slice_release(&want);
     ++	for (i = 0; i < N; i++) {
     ++		reftable_free(names[i]);
     ++	}
     ++}
     ++
     ++int block_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("binsearch", &test_binsearch);
     ++	add_test_case("block_read_write", &test_block_read_write);
     ++	return test_main(argc, argv);
     ++}
     +
       ## reftable/constants.h (new) ##
      @@
      +/*
     @@ reftable/merged.c (new)
      +
      +		reftable_record_key(&top.rec, &k);
      +
     -+		cmp = slice_cmp(k, entry_key);
     ++		cmp = slice_cmp(&k, &entry_key);
      +		slice_release(&k);
      +
      +		if (cmp > 0) {
     @@ reftable/merged.h (new)
      +
      +#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 "block.h"
     ++#include "constants.h"
     ++#include "pq.h"
     ++#include "reader.h"
     ++#include "record.h"
     ++#include "reftable.h"
     ++#include "test_framework.h"
     ++#include "reftable-tests.h"
     ++
     ++static void test_pq(void)
     ++{
     ++	char *names[54] = { 0 };
     ++	int N = ARRAY_SIZE(names) - 1;
     ++
     ++	struct merged_iter_pqueue pq = { 0 };
     ++	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)->ref_name = 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->ref_name) < 0);
     ++		}
     ++		last = ref->ref_name;
     ++		ref->ref_name = NULL;
     ++		reftable_free(ref);
     ++	}
     ++
     ++	for (i = 0; i < N; i++) {
     ++		reftable_free(names[i]);
     ++	}
     ++
     ++	merged_iter_pqueue_clear(&pq);
     ++}
     ++
     ++static void write_test_table(struct slice *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(&slice_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);
     ++	assert_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, int *sizes,
     ++			  struct slice *buf, int n)
     ++{
     ++	struct reftable_reader **rd = reftable_calloc(n * sizeof(*rd));
     ++	int i = 0;
     ++	struct reftable_merged_table *mt = NULL;
     ++	int err;
     ++	*source = reftable_calloc(n * sizeof(**source));
     ++	for (i = 0; i < n; i++) {
     ++		write_test_table(&buf[i], refs[i], sizes[i]);
     ++		block_source_from_slice(&(*source)[i], &buf[i]);
     ++
     ++		err = reftable_new_reader(&rd[i], &(*source)[i], "name");
     ++		assert_err(err);
     ++	}
     ++
     ++	err = reftable_new_merged_table(&mt, rd, n, SHA1_ID);
     ++	assert_err(err);
     ++	return mt;
     ++}
     ++
     ++static void test_merged_between(void)
     ++{
     ++	byte hash1[SHA1_SIZE] = { 1, 2, 3, 0 };
     ++
     ++	struct reftable_ref_record r1[] = { {
     ++		.ref_name = "b",
     ++		.update_index = 1,
     ++		.value = hash1,
     ++	} };
     ++	struct reftable_ref_record r2[] = { {
     ++		.ref_name = "a",
     ++		.update_index = 2,
     ++	} };
     ++
     ++	struct reftable_ref_record *refs[] = { r1, r2 };
     ++	int sizes[] = { 1, 1 };
     ++	struct slice bufs[2] = { SLICE_INIT, SLICE_INIT };
     ++	struct reftable_block_source *bs = NULL;
     ++	struct reftable_merged_table *mt =
     ++		merged_table_from_records(refs, &bs, sizes, bufs, 2);
     ++	int i;
     ++	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_iterator it = { 0 };
     ++	int err = reftable_merged_table_seek_ref(mt, &it, "a");
     ++	assert_err(err);
     ++
     ++	err = reftable_iterator_next_ref(&it, &ref);
     ++	assert_err(err);
     ++	assert(ref.update_index == 2);
     ++	reftable_ref_record_clear(&ref);
     ++
     ++	reftable_iterator_destroy(&it);
     ++	reftable_merged_table_close(mt);
     ++	reftable_merged_table_free(mt);
     ++	for (i = 0; i < ARRAY_SIZE(bufs); i++) {
     ++		slice_release(&bufs[i]);
     ++	}
     ++	reftable_free(bs);
     ++}
     ++
     ++static void test_merged(void)
     ++{
     ++	byte hash1[SHA1_SIZE] = { 1 };
     ++	byte hash2[SHA1_SIZE] = { 2 };
     ++	struct reftable_ref_record r1[] = { {
     ++						    .ref_name = "a",
     ++						    .update_index = 1,
     ++						    .value = hash1,
     ++					    },
     ++					    {
     ++						    .ref_name = "b",
     ++						    .update_index = 1,
     ++						    .value = hash1,
     ++					    },
     ++					    {
     ++						    .ref_name = "c",
     ++						    .update_index = 1,
     ++						    .value = hash1,
     ++					    } };
     ++	struct reftable_ref_record r2[] = { {
     ++		.ref_name = "a",
     ++		.update_index = 2,
     ++	} };
     ++	struct reftable_ref_record r3[] = {
     ++		{
     ++			.ref_name = "c",
     ++			.update_index = 3,
     ++			.value = hash2,
     ++		},
     ++		{
     ++			.ref_name = "d",
     ++			.update_index = 3,
     ++			.value = 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 slice bufs[3] = { SLICE_INIT, SLICE_INIT, SLICE_INIT };
     ++	struct reftable_block_source *bs = NULL;
     ++
     ++	struct reftable_merged_table *mt =
     ++		merged_table_from_records(refs, &bs, sizes, bufs, 3);
     ++
     ++	struct reftable_iterator it = { 0 };
     ++	int err = reftable_merged_table_seek_ref(mt, &it, "a");
     ++	struct reftable_ref_record *out = NULL;
     ++	int len = 0;
     ++	int cap = 0;
     ++	int i = 0;
     ++
     ++	assert_err(err);
     ++	while (len < 100) { /* cap loops/recursion. */
     ++		struct reftable_ref_record ref = { 0 };
     ++		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_clear(&out[i]);
     ++	}
     ++	reftable_free(out);
     ++
     ++	for (i = 0; i < 3; i++) {
     ++		slice_release(&bufs[i]);
     ++	}
     ++	reftable_merged_table_close(mt);
     ++	reftable_merged_table_free(mt);
     ++	reftable_free(bs);
     ++}
     ++
     ++/* XXX test refs_for(oid) */
     ++
     ++int merged_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("test_merged_between", &test_merged_between);
     ++	add_test_case("test_pq", &test_pq);
     ++	add_test_case("test_merged", &test_merged);
     ++	return test_main(argc, argv);
     ++}
     +
       ## reftable/pq.c (new) ##
      @@
      +/*
     @@ reftable/pq.c (new)
      +	reftable_record_key(&a.rec, &ak);
      +	reftable_record_key(&b.rec, &bk);
      +
     -+	cmp = slice_cmp(ak, bk);
     ++	cmp = slice_cmp(&ak, &bk);
      +
      +	slice_release(&ak);
      +	slice_release(&bk);
     @@ reftable/reader.c (new)
      +		if (err < 0)
      +			goto done;
      +
     -+		if (slice_cmp(got_key, want_key) > 0) {
     ++		if (slice_cmp(&got_key, &want_key) > 0) {
      +			table_iter_block_done(&next);
      +			break;
      +		}
     @@ reftable/reader.c (new)
      +		table_iter_copy_from(ti, &next);
      +	}
      +
     -+	err = block_iter_seek(&ti->bi, want_key);
     ++	err = block_iter_seek(&ti->bi, &want_key);
      +	if (err < 0)
      +		goto done;
      +	err = 0;
     @@ reftable/reader.c (new)
      +		if (err != 0)
      +			goto done;
      +
     -+		err = block_iter_seek(&next.bi, want_index.last_key);
     ++		err = block_iter_seek(&next.bi, &want_index.last_key);
      +		if (err < 0)
      +			goto done;
      +
     @@ reftable/record.c (new)
      +#include "constants.h"
      +#include "reftable.h"
      +
     -+int get_var_int(uint64_t *dest, struct slice in)
     ++int get_var_int(uint64_t *dest, struct slice *in)
      +{
      +	int ptr = 0;
      +	uint64_t val;
      +
     -+	if (in.len == 0)
     ++	if (in->len == 0)
      +		return -1;
     -+	val = in.buf[ptr] & 0x7f;
     ++	val = in->buf[ptr] & 0x7f;
      +
     -+	while (in.buf[ptr] & 0x80) {
     ++	while (in->buf[ptr] & 0x80) {
      +		ptr++;
     -+		if (ptr > in.len) {
     ++		if (ptr > in->len) {
      +			return -1;
      +		}
     -+		val = (val + 1) << 7 | (uint64_t)(in.buf[ptr] & 0x7f);
     ++		val = (val + 1) << 7 | (uint64_t)(in->buf[ptr] & 0x7f);
      +	}
      +
      +	*dest = val;
      +	return ptr + 1;
      +}
      +
     -+int put_var_int(struct slice dest, uint64_t val)
     ++int put_var_int(struct slice *dest, uint64_t val)
      +{
      +	byte buf[10] = { 0 };
      +	int i = 9;
     @@ reftable/record.c (new)
      +	}
      +
      +	n = sizeof(buf) - i - 1;
     -+	if (dest.len < n)
     ++	if (dest->len < n)
      +		return -1;
     -+	memcpy(dest.buf, &buf[i + 1], n);
     ++	memcpy(dest->buf, &buf[i + 1], n);
      +	return n;
      +}
      +
     @@ reftable/record.c (new)
      +{
      +	int start_len = in.len;
      +	uint64_t tsize = 0;
     -+	int n = get_var_int(&tsize, in);
     ++	int n = get_var_int(&tsize, &in);
      +	if (n <= 0)
      +		return -1;
      +	slice_consume(&in, n);
     @@ reftable/record.c (new)
      +{
      +	struct slice start = s;
      +	int l = strlen(str);
     -+	int n = put_var_int(s, l);
     ++	int n = put_var_int(&s, l);
      +	if (n < 0)
      +		return -1;
      +	slice_consume(&s, n);
     @@ reftable/record.c (new)
      +			struct slice key, byte extra)
      +{
      +	struct slice start = dest;
     -+	int prefix_len = common_prefix_size(prev_key, key);
     ++	int prefix_len = common_prefix_size(&prev_key, &key);
      +	uint64_t suffix_len = key.len - prefix_len;
     -+	int n = put_var_int(dest, (uint64_t)prefix_len);
     ++	int n = put_var_int(&dest, (uint64_t)prefix_len);
      +	if (n < 0)
      +		return -1;
      +	slice_consume(&dest, n);
      +
      +	*restart = (prefix_len == 0);
      +
     -+	n = put_var_int(dest, suffix_len << 3 | (uint64_t)extra);
     ++	n = put_var_int(&dest, suffix_len << 3 | (uint64_t)extra);
      +	if (n < 0)
      +		return -1;
      +	slice_consume(&dest, n);
     @@ reftable/record.c (new)
      +	int start_len = in.len;
      +	uint64_t prefix_len = 0;
      +	uint64_t suffix_len = 0;
     -+	int n = get_var_int(&prefix_len, in);
     ++	int n = get_var_int(&prefix_len, &in);
      +	if (n < 0)
      +		return -1;
      +	slice_consume(&in, n);
     @@ reftable/record.c (new)
      +	if (prefix_len > last_key.len)
      +		return -1;
      +
     -+	n = get_var_int(&suffix_len, in);
     ++	n = get_var_int(&suffix_len, &in);
      +	if (n <= 0)
      +		return -1;
      +	slice_consume(&in, n);
     @@ reftable/record.c (new)
      +	const struct reftable_ref_record *r =
      +		(const struct reftable_ref_record *)rec;
      +	struct slice start = s;
     -+	int n = put_var_int(s, r->update_index);
     ++	int n = put_var_int(&s, r->update_index);
      +	assert(hash_size > 0);
      +	if (n < 0)
      +		return -1;
     @@ reftable/record.c (new)
      +	bool seen_target_value = false;
      +	bool seen_target = false;
      +
     -+	int n = get_var_int(&r->update_index, in);
     ++	int n = get_var_int(&r->update_index, &in);
      +	if (n < 0)
      +		return n;
      +	assert(hash_size > 0);
     @@ reftable/record.c (new)
      +	int n = 0;
      +	uint64_t last = 0;
      +	if (r->offset_len == 0 || r->offset_len >= 8) {
     -+		n = put_var_int(s, r->offset_len);
     ++		n = put_var_int(&s, r->offset_len);
      +		if (n < 0) {
      +			return -1;
      +		}
     @@ reftable/record.c (new)
      +	}
      +	if (r->offset_len == 0)
      +		return start.len - s.len;
     -+	n = put_var_int(s, r->offsets[0]);
     ++	n = put_var_int(&s, r->offsets[0]);
      +	if (n < 0)
      +		return -1;
      +	slice_consume(&s, n);
      +
      +	last = r->offsets[0];
      +	for (i = 1; i < r->offset_len; i++) {
     -+		int n = put_var_int(s, r->offsets[i] - last);
     ++		int n = put_var_int(&s, r->offsets[i] - last);
      +		if (n < 0) {
      +			return -1;
      +		}
     @@ reftable/record.c (new)
      +	r->hash_prefix_len = key.len;
      +
      +	if (val_type == 0) {
     -+		n = get_var_int(&count, in);
     ++		n = get_var_int(&count, &in);
      +		if (n < 0) {
      +			return n;
      +		}
     @@ reftable/record.c (new)
      +	r->offsets = reftable_malloc(count * sizeof(uint64_t));
      +	r->offset_len = count;
      +
     -+	n = get_var_int(&r->offsets[0], in);
     ++	n = get_var_int(&r->offsets[0], &in);
      +	if (n < 0)
      +		return n;
      +	slice_consume(&in, n);
     @@ reftable/record.c (new)
      +	j = 1;
      +	while (j < count) {
      +		uint64_t delta = 0;
     -+		int n = get_var_int(&delta, in);
     ++		int n = get_var_int(&delta, &in);
      +		if (n < 0) {
      +			return n;
      +		}
     @@ reftable/record.c (new)
      +		return -1;
      +	slice_consume(&s, n);
      +
     -+	n = put_var_int(s, r->time);
     ++	n = put_var_int(&s, r->time);
      +	if (n < 0)
      +		return -1;
      +	slice_consume(&s, n);
     @@ reftable/record.c (new)
      +	r->email[dest.len] = 0;
      +
      +	ts = 0;
     -+	n = get_var_int(&ts, in);
     ++	n = get_var_int(&ts, &in);
      +	if (n < 0)
      +		goto done;
      +	slice_consume(&in, n);
     @@ reftable/record.c (new)
      +static void reftable_index_record_key(const void *r, struct slice *dest)
      +{
      +	struct reftable_index_record *rec = (struct reftable_index_record *)r;
     -+	slice_copy(dest, rec->last_key);
     ++	slice_copy(dest, &rec->last_key);
      +}
      +
      +static void reftable_index_record_copy_from(void *rec, const void *src_rec,
     @@ reftable/record.c (new)
      +	struct reftable_index_record *src =
      +		(struct reftable_index_record *)src_rec;
      +
     -+	slice_copy(&dst->last_key, src->last_key);
     ++	slice_copy(&dst->last_key, &src->last_key);
      +	dst->offset = src->offset;
      +}
      +
     @@ reftable/record.c (new)
      +		(const struct reftable_index_record *)rec;
      +	struct slice start = out;
      +
     -+	int n = put_var_int(out, r->offset);
     ++	int n = put_var_int(&out, r->offset);
      +	if (n < 0)
      +		return n;
      +
     @@ reftable/record.c (new)
      +	struct reftable_index_record *r = (struct reftable_index_record *)rec;
      +	int n = 0;
      +
     -+	slice_copy(&r->last_key, key);
     ++	slice_copy(&r->last_key, &key);
      +
     -+	n = get_var_int(&r->offset, in);
     ++	n = get_var_int(&r->offset, &in);
      +	if (n < 0)
      +		return n;
      +
     @@ reftable/record.h (new)
      +
      +/* utilities for de/encoding varints */
      +
     -+int get_var_int(uint64_t *dest, struct slice in);
     -+int put_var_int(struct slice dest, uint64_t val);
     ++int get_var_int(uint64_t *dest, struct slice *in);
     ++int put_var_int(struct slice *dest, uint64_t val);
      +
      +/* Methods for records. */
      +struct reftable_record_vtable {
     @@ reftable/record.h (new)
      +
      +#endif
      
     - ## reftable/refname.c (new) ##
     + ## reftable/record_test.c (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
      +*/
      +
     ++#include "record.h"
     ++
      +#include "system.h"
     -+#include "reftable.h"
      +#include "basics.h"
     -+#include "refname.h"
     -+#include "slice.h"
     -+
     -+struct find_arg {
     -+	char **names;
     -+	const char *want;
     -+};
     ++#include "constants.h"
     ++#include "reftable.h"
     ++#include "test_framework.h"
     ++#include "reftable-tests.h"
      +
     -+static int find_name(size_t k, void *arg)
     ++static void test_copy(struct reftable_record *rec)
      +{
     -+	struct find_arg *f_arg = (struct find_arg *)arg;
     -+	return strcmp(f_arg->names[k], f_arg->want) >= 0;
     ++	struct reftable_record copy =
     ++		reftable_new_record(reftable_record_type(rec));
     ++	reftable_record_copy_from(&copy, rec, SHA1_SIZE);
     ++	/* do it twice to catch memory leaks */
     ++	reftable_record_copy_from(&copy, rec, SHA1_SIZE);
     ++	switch (reftable_record_type(&copy)) {
     ++	case BLOCK_TYPE_REF:
     ++		assert(reftable_ref_record_equal(reftable_record_as_ref(&copy),
     ++						 reftable_record_as_ref(rec),
     ++						 SHA1_SIZE));
     ++		break;
     ++	case BLOCK_TYPE_LOG:
     ++		assert(reftable_log_record_equal(reftable_record_as_log(&copy),
     ++						 reftable_record_as_log(rec),
     ++						 SHA1_SIZE));
     ++		break;
     ++	}
     ++	reftable_record_destroy(&copy);
      +}
      +
     -+int modification_has_ref(struct modification *mod, const char *name)
     ++static void test_varint_roundtrip(void)
      +{
     -+	struct reftable_ref_record ref = { 0 };
     -+	int err = 0;
     ++	uint64_t inputs[] = { 0,
     ++			      1,
     ++			      27,
     ++			      127,
     ++			      128,
     ++			      257,
     ++			      4096,
     ++			      ((uint64_t)1 << 63),
     ++			      ((uint64_t)1 << 63) + ((uint64_t)1 << 63) - 1 };
     ++	int i = 0;
     ++	for (i = 0; i < ARRAY_SIZE(inputs); i++) {
     ++		byte dest[10];
      +
     -+	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;
     -+		}
     -+	}
     ++		struct slice out = { .buf = dest, .len = 10, .cap = 10 };
      +
     -+	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;
     -+		}
     ++		uint64_t in = inputs[i];
     ++		int n = put_var_int(&out, in);
     ++		uint64_t got = 0;
     ++
     ++		assert(n > 0);
     ++		out.len = n;
     ++		n = get_var_int(&got, &out);
     ++		assert(n > 0);
     ++
     ++		assert(got == in);
      +	}
     ++}
      +
     -+	err = reftable_table_read_ref(&mod->tab, name, &ref);
     -+	reftable_ref_record_clear(&ref);
     -+	return err;
     ++static void test_common_prefix(void)
     ++{
     ++	struct {
     ++		const char *a, *b;
     ++		int want;
     ++	} cases[] = {
     ++		{ "abc", "ab", 2 },
     ++		{ "", "abc", 0 },
     ++		{ "abc", "abd", 2 },
     ++		{ "abc", "pqr", 0 },
     ++	};
     ++
     ++	int i = 0;
     ++	for (i = 0; i < ARRAY_SIZE(cases); i++) {
     ++		struct slice a = SLICE_INIT;
     ++		struct slice b = SLICE_INIT;
     ++		slice_set_string(&a, cases[i].a);
     ++		slice_set_string(&b, cases[i].b);
     ++
     ++		assert(common_prefix_size(&a, &b) == cases[i].want);
     ++
     ++		slice_release(&a);
     ++		slice_release(&b);
     ++	}
      +}
      +
     -+static void modification_clear(struct modification *mod)
     ++static void set_hash(byte *h, int j)
      +{
     -+	/* 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;
     ++	int i = 0;
     ++	for (i = 0; i < hash_size(SHA1_ID); i++) {
     ++		h[i] = (j >> i) & 0xff;
     ++	}
      +}
      +
     -+int modification_has_ref_with_prefix(struct modification *mod,
     -+				     const char *prefix)
     ++static void test_reftable_ref_record_roundtrip(void)
      +{
     -+	struct reftable_iterator it = { NULL };
     -+	struct reftable_ref_record ref = { NULL };
     -+	int err = 0;
     ++	int i = 0;
     ++
     ++	for (i = 0; i <= 3; i++) {
     ++		struct reftable_ref_record in = { 0 };
     ++		struct reftable_ref_record out = {
     ++			.ref_name = xstrdup("old name"),
     ++			.value = reftable_calloc(SHA1_SIZE),
     ++			.target_value = reftable_calloc(SHA1_SIZE),
     ++			.target = xstrdup("old value"),
     ++		};
     ++		struct reftable_record rec_out = { 0 };
     ++		struct slice key = SLICE_INIT;
     ++		struct reftable_record rec = { 0 };
     ++		struct slice dest = SLICE_INIT;
     ++		int n, m;
     ++
     ++		switch (i) {
     ++		case 0:
     ++			break;
     ++		case 1:
     ++			in.value = reftable_malloc(SHA1_SIZE);
     ++			set_hash(in.value, 1);
     ++			break;
     ++		case 2:
     ++			in.value = reftable_malloc(SHA1_SIZE);
     ++			set_hash(in.value, 1);
     ++			in.target_value = reftable_malloc(SHA1_SIZE);
     ++			set_hash(in.target_value, 2);
     ++			break;
     ++		case 3:
     ++			in.target = xstrdup("target");
     ++			break;
     ++		}
     ++		in.ref_name = xstrdup("refs/heads/master");
     ++
     ++		reftable_record_from_ref(&rec, &in);
     ++		test_copy(&rec);
     ++
     ++		assert(reftable_record_val_type(&rec) == i);
     ++
     ++		reftable_record_key(&rec, &key);
     ++		slice_resize(&dest, 1024);
     ++		n = reftable_record_encode(&rec, dest, SHA1_SIZE);
     ++		assert(n > 0);
     ++
     ++		/* decode into a non-zero reftable_record to test for leaks. */
     ++
     ++		reftable_record_from_ref(&rec_out, &out);
     ++		m = reftable_record_decode(&rec_out, key, i, dest, SHA1_SIZE);
     ++		assert(n == m);
     ++
     ++		assert((out.value != NULL) == (in.value != NULL));
     ++		assert((out.target_value != NULL) == (in.target_value != NULL));
     ++		assert((out.target != NULL) == (in.target != NULL));
     ++		reftable_record_clear(&rec_out);
     ++
     ++		slice_release(&key);
     ++		slice_release(&dest);
     ++		reftable_ref_record_clear(&in);
     ++	}
     ++}
     ++
     ++static void test_reftable_log_record_equal(void)
     ++{
     ++	struct reftable_log_record in[2] = {
     ++		{
     ++			.ref_name = xstrdup("refs/heads/master"),
     ++			.update_index = 42,
     ++		},
     ++		{
     ++			.ref_name = xstrdup("refs/heads/master"),
     ++			.update_index = 22,
     ++		}
     ++	};
     ++
     ++	assert(!reftable_log_record_equal(&in[0], &in[1], SHA1_SIZE));
     ++	in[1].update_index = in[0].update_index;
     ++	assert(reftable_log_record_equal(&in[0], &in[1], SHA1_SIZE));
     ++	reftable_log_record_clear(&in[0]);
     ++	reftable_log_record_clear(&in[1]);
     ++}
     ++
     ++static void test_reftable_log_record_roundtrip(void)
     ++{
     ++	struct reftable_log_record in[2] = {
     ++		{
     ++			.ref_name = xstrdup("refs/heads/master"),
     ++			.old_hash = reftable_malloc(SHA1_SIZE),
     ++			.new_hash = reftable_malloc(SHA1_SIZE),
     ++			.name = xstrdup("han-wen"),
     ++			.email = xstrdup("[email-masked]"),
     ++			.message = xstrdup("test"),
     ++			.update_index = 42,
     ++			.time = 1577123507,
     ++			.tz_offset = 100,
     ++		},
     ++		{
     ++			.ref_name = xstrdup("refs/heads/master"),
     ++			.update_index = 22,
     ++		}
     ++	};
     ++	set_test_hash(in[0].new_hash, 1);
     ++	set_test_hash(in[0].old_hash, 2);
     ++	for (int i = 0; i < ARRAY_SIZE(in); i++) {
     ++		struct reftable_record rec = { 0 };
     ++		struct slice key = SLICE_INIT;
     ++		struct slice dest = SLICE_INIT;
     ++		/* populate out, to check for leaks. */
     ++		struct reftable_log_record out = {
     ++			.ref_name = xstrdup("old name"),
     ++			.new_hash = reftable_calloc(SHA1_SIZE),
     ++			.old_hash = reftable_calloc(SHA1_SIZE),
     ++			.name = xstrdup("old name"),
     ++			.email = xstrdup("old@email"),
     ++			.message = xstrdup("old message"),
     ++		};
     ++		struct reftable_record rec_out = { 0 };
     ++		int n, m, valtype;
     ++
     ++		reftable_record_from_log(&rec, &in[i]);
     ++
     ++		test_copy(&rec);
     ++
     ++		reftable_record_key(&rec, &key);
     ++
     ++		slice_resize(&dest, 1024);
     ++
     ++		n = reftable_record_encode(&rec, dest, SHA1_SIZE);
     ++		assert(n >= 0);
     ++		reftable_record_from_log(&rec_out, &out);
     ++		valtype = reftable_record_val_type(&rec);
     ++		m = reftable_record_decode(&rec_out, key, valtype, dest,
     ++					   SHA1_SIZE);
     ++		assert(n == m);
     ++
     ++		assert(reftable_log_record_equal(&in[i], &out, SHA1_SIZE));
     ++		reftable_log_record_clear(&in[i]);
     ++		slice_release(&key);
     ++		slice_release(&dest);
     ++		reftable_record_clear(&rec_out);
     ++	}
     ++}
     ++
     ++static void test_u24_roundtrip(void)
     ++{
     ++	uint32_t in = 0x112233;
     ++	byte dest[3];
     ++	uint32_t out;
     ++	put_be24(dest, in);
     ++	out = get_be24(dest);
     ++	assert(in == out);
     ++}
     ++
     ++static void test_key_roundtrip(void)
     ++{
     ++	struct slice dest = SLICE_INIT;
     ++	struct slice last_key = SLICE_INIT;
     ++	struct slice key = SLICE_INIT;
     ++	struct slice roundtrip = SLICE_INIT;
     ++	bool restart;
     ++	byte extra;
     ++	int n, m;
     ++	byte rt_extra;
     ++
     ++	slice_resize(&dest, 1024);
     ++	slice_set_string(&last_key, "refs/heads/master");
     ++	slice_set_string(&key, "refs/tags/bla");
     ++
     ++	extra = 6;
     ++	n = reftable_encode_key(&restart, dest, last_key, key, extra);
     ++	assert(!restart);
     ++	assert(n > 0);
     ++
     ++	m = reftable_decode_key(&roundtrip, &rt_extra, last_key, dest);
     ++	assert(n == m);
     ++	assert(slice_equal(&key, &roundtrip));
     ++	assert(rt_extra == extra);
     ++
     ++	slice_release(&last_key);
     ++	slice_release(&key);
     ++	slice_release(&dest);
     ++	slice_release(&roundtrip);
     ++}
     ++
     ++static void test_reftable_obj_record_roundtrip(void)
     ++{
     ++	byte testHash1[SHA1_SIZE] = { 1, 2, 3, 4, 0 };
     ++	uint64_t till9[] = { 1, 2, 3, 4, 500, 600, 700, 800, 9000 };
     ++	struct reftable_obj_record recs[3] = { {
     ++						       .hash_prefix = testHash1,
     ++						       .hash_prefix_len = 5,
     ++						       .offsets = till9,
     ++						       .offset_len = 3,
     ++					       },
     ++					       {
     ++						       .hash_prefix = testHash1,
     ++						       .hash_prefix_len = 5,
     ++						       .offsets = till9,
     ++						       .offset_len = 9,
     ++					       },
     ++					       {
     ++						       .hash_prefix = testHash1,
     ++						       .hash_prefix_len = 5,
     ++					       } };
     ++	int i = 0;
     ++	for (i = 0; i < ARRAY_SIZE(recs); i++) {
     ++		struct reftable_obj_record in = recs[i];
     ++		struct slice dest = SLICE_INIT;
     ++		struct reftable_record rec = { 0 };
     ++		struct slice key = SLICE_INIT;
     ++		struct reftable_obj_record out = { 0 };
     ++		struct reftable_record rec_out = { 0 };
     ++		int n, m;
     ++		byte extra;
     ++
     ++		reftable_record_from_obj(&rec, &in);
     ++		test_copy(&rec);
     ++		reftable_record_key(&rec, &key);
     ++		slice_resize(&dest, 1024);
     ++		n = reftable_record_encode(&rec, dest, SHA1_SIZE);
     ++		assert(n > 0);
     ++		extra = reftable_record_val_type(&rec);
     ++		reftable_record_from_obj(&rec_out, &out);
     ++		m = reftable_record_decode(&rec_out, key, extra, dest,
     ++					   SHA1_SIZE);
     ++		assert(n == m);
     ++
     ++		assert(in.hash_prefix_len == out.hash_prefix_len);
     ++		assert(in.offset_len == out.offset_len);
     ++
     ++		assert(!memcmp(in.hash_prefix, out.hash_prefix,
     ++			       in.hash_prefix_len));
     ++		assert(0 == memcmp(in.offsets, out.offsets,
     ++				   sizeof(uint64_t) * in.offset_len));
     ++		slice_release(&key);
     ++		slice_release(&dest);
     ++		reftable_record_clear(&rec_out);
     ++	}
     ++}
     ++
     ++static void test_reftable_index_record_roundtrip(void)
     ++{
     ++	struct reftable_index_record in = {
     ++		.offset = 42,
     ++		.last_key = SLICE_INIT,
     ++	};
     ++	struct slice dest = SLICE_INIT;
     ++	struct slice key = SLICE_INIT;
     ++	struct reftable_record rec = { 0 };
     ++	struct reftable_index_record out = { .last_key = SLICE_INIT };
     ++	struct reftable_record out_rec = { NULL };
     ++	int n, m;
     ++	byte extra;
     ++
     ++	slice_set_string(&in.last_key, "refs/heads/master");
     ++	reftable_record_from_index(&rec, &in);
     ++	reftable_record_key(&rec, &key);
     ++	test_copy(&rec);
     ++
     ++	assert(0 == slice_cmp(&key, &in.last_key));
     ++	slice_resize(&dest, 1024);
     ++	n = reftable_record_encode(&rec, dest, SHA1_SIZE);
     ++	assert(n > 0);
     ++
     ++	extra = reftable_record_val_type(&rec);
     ++	reftable_record_from_index(&out_rec, &out);
     ++	m = reftable_record_decode(&out_rec, key, extra, dest, SHA1_SIZE);
     ++	assert(m == n);
     ++
     ++	assert(in.offset == out.offset);
     ++
     ++	reftable_record_clear(&out_rec);
     ++	slice_release(&key);
     ++	slice_release(&in.last_key);
     ++	slice_release(&dest);
     ++}
     ++
     ++int record_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("test_reftable_log_record_equal",
     ++		      &test_reftable_log_record_equal);
     ++	add_test_case("test_reftable_log_record_roundtrip",
     ++		      &test_reftable_log_record_roundtrip);
     ++	add_test_case("test_reftable_ref_record_roundtrip",
     ++		      &test_reftable_ref_record_roundtrip);
     ++	add_test_case("test_varint_roundtrip", &test_varint_roundtrip);
     ++	add_test_case("test_key_roundtrip", &test_key_roundtrip);
     ++	add_test_case("test_common_prefix", &test_common_prefix);
     ++	add_test_case("test_reftable_obj_record_roundtrip",
     ++		      &test_reftable_obj_record_roundtrip);
     ++	add_test_case("test_reftable_index_record_roundtrip",
     ++		      &test_reftable_index_record_roundtrip);
     ++	add_test_case("test_u24_roundtrip", &test_u24_roundtrip);
     ++	return test_main(argc, argv);
     ++}
     +
     + ## 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.h"
     ++#include "basics.h"
     ++#include "refname.h"
     ++#include "slice.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;
     ++}
     ++
     ++int modification_has_ref(struct modification *mod, const char *name)
     ++{
     ++	struct reftable_ref_record ref = { 0 };
     ++	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_clear(&ref);
     ++	return err;
     ++}
     ++
     ++static void modification_clear(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;
     ++}
     ++
     ++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 = {
     @@ reftable/refname.h (new)
      +
      +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 "reftable.h"
     ++
     ++#include "basics.h"
     ++#include "block.h"
     ++#include "constants.h"
     ++#include "reader.h"
     ++#include "record.h"
     ++#include "refname.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 slice buf = SLICE_INIT;
     ++	struct reftable_writer *w =
     ++		reftable_new_writer(&slice_add_void, &buf, &opts);
     ++	struct reftable_ref_record rec = {
     ++		.ref_name = "a/b",
     ++		.target = "destination", /* make sure it's not a symref. */
     ++		.update_index = 1,
     ++	};
     ++	int err;
     ++	int i;
     ++	struct reftable_block_source source = { 0 };
     ++	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);
     ++	assert_err(err);
     ++
     ++	err = reftable_writer_close(w);
     ++	assert_err(err);
     ++	reftable_writer_free(w);
     ++
     ++	block_source_from_slice(&source, &buf);
     ++	err = reftable_new_reader(&rd, &source, "filename");
     ++	assert_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);
     ++		assert(err == cases[i].error_code);
     ++	}
     ++
     ++	reftable_reader_free(rd);
     ++	slice_release(&buf);
     ++}
     ++
     ++int refname_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("test_conflict", &test_conflict);
     ++	return test_main(argc, argv);
     ++}
     +
     + ## reftable/reftable-tests.h (new) ##
     +@@
     ++#ifndef REFTABLE_TESTS_H
     ++#define REFTABLE_TESTS_H
     ++
     ++int block_test_main(int argc, const char **argv);
     ++int merged_test_main(int argc, const char **argv);
     ++int record_test_main(int argc, const char **argv);
     ++int refname_test_main(int argc, const char **argv);
     ++int reftable_test_main(int argc, const char **argv);
     ++int slice_test_main(int argc, const char **argv);
     ++int stack_test_main(int argc, const char **argv);
     ++int tree_test_main(int argc, const char **argv);
     ++
      +#endif
      
       ## reftable/reftable.c (new) ##
     @@ reftable/reftable.h (new)
      +
      +#endif
      
     - ## reftable/slice.c (new) ##
     + ## reftable/reftable_test.c (new) ##
      @@
      +/*
      +Copyright 2020 Google LLC
     @@ reftable/slice.c (new)
      +https://developers.google.com/open-source/licenses/bsd
      +*/
      +
     -+#include "slice.h"
     ++#include "reftable.h"
      +
      +#include "system.h"
      +
     -+#include "reftable.h"
     ++#include "basics.h"
     ++#include "block.h"
     ++#include "constants.h"
     ++#include "reader.h"
     ++#include "record.h"
     ++#include "test_framework.h"
     ++#include "reftable-tests.h"
      +
     -+struct slice reftable_empty_slice = SLICE_INIT;
     ++static const int update_index = 5;
      +
     -+void slice_set_string(struct slice *s, const char *str)
     ++static void test_buffer(void)
      +{
     -+	int l;
     -+	if (str == NULL) {
     -+		s->len = 0;
     -+		return;
     -+	}
     -+	assert(s->canary == SLICE_CANARY);
     ++	struct slice buf = SLICE_INIT;
     ++	struct reftable_block_source source = { NULL };
     ++	struct reftable_block out = { 0 };
     ++	int n;
     ++	byte in[] = "hello";
     ++	slice_add(&buf, in, sizeof(in));
     ++	block_source_from_slice(&source, &buf);
     ++	assert(block_source_size(&source) == 6);
     ++	n = block_source_read_block(&source, &out, 0, sizeof(in));
     ++	assert(n == sizeof(in));
     ++	assert(!memcmp(in, out.data, n));
     ++	reftable_block_done(&out);
     ++
     ++	n = block_source_read_block(&source, &out, 1, 2);
     ++	assert(n == 2);
     ++	assert(!memcmp(out.data, "el", 2));
     ++
     ++	reftable_block_done(&out);
     ++	block_source_close(&source);
     ++	slice_release(&buf);
     ++}
     ++
     ++static void test_default_write_opts(void)
     ++{
     ++	struct reftable_write_options opts = { 0 };
     ++	struct slice buf = SLICE_INIT;
     ++	struct reftable_writer *w =
     ++		reftable_new_writer(&slice_add_void, &buf, &opts);
     ++
     ++	struct reftable_ref_record rec = {
     ++		.ref_name = "master",
     ++		.update_index = 1,
     ++	};
     ++	int err;
     ++	struct reftable_block_source source = { 0 };
     ++	struct reftable_reader **readers = malloc(sizeof(*readers) * 1);
     ++	uint32_t hash_id;
     ++	struct reftable_reader *rd = NULL;
     ++	struct reftable_merged_table *merged = NULL;
      +
     -+	l = strlen(str);
     -+	l++; /* \0 */
     -+	slice_resize(s, l);
     -+	memcpy(s->buf, str, l);
     -+	s->len = l - 1;
     -+}
     ++	reftable_writer_set_limits(w, 1, 1);
      +
     -+void slice_init(struct slice *s)
     -+{
     -+	struct slice empty = SLICE_INIT;
     -+	*s = empty;
     -+}
     ++	err = reftable_writer_add_ref(w, &rec);
     ++	assert_err(err);
      +
     -+void slice_resize(struct slice *s, int l)
     -+{
     -+	assert(s->canary == SLICE_CANARY);
     -+	if (s->cap < l) {
     -+		int c = s->cap * 2;
     -+		if (c < l) {
     -+			c = l;
     -+		}
     -+		s->cap = c;
     -+		s->buf = reftable_realloc(s->buf, s->cap);
     -+	}
     -+	s->len = l;
     -+}
     ++	err = reftable_writer_close(w);
     ++	assert_err(err);
     ++	reftable_writer_free(w);
      +
     -+void slice_addstr(struct slice *d, const char *s)
     -+{
     -+	int l1 = d->len;
     -+	int l2 = strlen(s);
     -+	assert(d->canary == SLICE_CANARY);
     ++	block_source_from_slice(&source, &buf);
      +
     -+	slice_resize(d, l2 + l1);
     -+	memcpy(d->buf + l1, s, l2);
     ++	err = reftable_new_reader(&rd, &source, "filename");
     ++	assert_err(err);
     ++
     ++	hash_id = reftable_reader_hash_id(rd);
     ++	assert(hash_id == SHA1_ID);
     ++
     ++	readers[0] = rd;
     ++
     ++	err = reftable_new_merged_table(&merged, readers, 1, SHA1_ID);
     ++	assert_err(err);
     ++
     ++	reftable_merged_table_close(merged);
     ++	reftable_merged_table_free(merged);
     ++	slice_release(&buf);
      +}
      +
     -+void slice_addbuf(struct slice *s, struct slice a)
     ++static void write_table(char ***names, struct slice *buf, int N, int block_size,
     ++			uint32_t hash_id)
      +{
     -+	int end = s->len;
     -+	assert(s->canary == SLICE_CANARY);
     -+	slice_resize(s, s->len + a.len);
     -+	memcpy(s->buf + end, a.buf, a.len);
     -+}
     -+
     -+void slice_consume(struct slice *s, int n)
     -+{
     -+	assert(s->canary == SLICE_CANARY);
     -+	s->buf += n;
     -+	s->len -= n;
     -+}
     ++	struct reftable_write_options opts = {
     ++		.block_size = block_size,
     ++		.hash_id = hash_id,
     ++	};
     ++	struct reftable_writer *w =
     ++		reftable_new_writer(&slice_add_void, buf, &opts);
     ++	struct reftable_ref_record ref = { 0 };
     ++	int i = 0, n;
     ++	struct reftable_log_record log = { 0 };
     ++	const struct reftable_stats *stats = NULL;
     ++	*names = reftable_calloc(sizeof(char *) * (N + 1));
     ++	reftable_writer_set_limits(w, update_index, update_index);
     ++	for (i = 0; i < N; i++) {
     ++		byte hash[SHA256_SIZE] = { 0 };
     ++		char name[100];
     ++		int n;
      +
     -+byte *slice_detach(struct slice *s)
     -+{
     -+	byte *p = s->buf;
     -+	assert(s->canary == SLICE_CANARY);
     -+	s->buf = NULL;
     -+	s->cap = 0;
     -+	s->len = 0;
     -+	return p;
     -+}
     ++		set_test_hash(hash, i);
      +
     -+void slice_release(struct slice *s)
     -+{
     -+	assert(s->canary == SLICE_CANARY);
     -+	reftable_free(slice_detach(s));
     -+}
     ++		snprintf(name, sizeof(name), "refs/heads/branch%02d", i);
      +
     -+void slice_copy(struct slice *dest, struct slice src)
     -+{
     -+	assert(dest->canary == SLICE_CANARY);
     -+	assert(src.canary == SLICE_CANARY);
     -+	slice_resize(dest, src.len);
     -+	memcpy(dest->buf, src.buf, src.len);
     -+}
     ++		ref.ref_name = name;
     ++		ref.value = hash;
     ++		ref.update_index = update_index;
     ++		(*names)[i] = xstrdup(name);
      +
     -+/* return the underlying data as char*. len is left unchanged, but
     -+   a \0 is added at the end. */
     -+const char *slice_as_string(struct slice *s)
     -+{
     -+	assert(s->canary == SLICE_CANARY);
     -+	if (s->cap == s->len) {
     -+		int l = s->len;
     -+		slice_resize(s, l + 1);
     -+		s->len = l;
     ++		n = reftable_writer_add_ref(w, &ref);
     ++		assert(n == 0);
      +	}
     -+	s->buf[s->len] = 0;
     -+	return (const char *)s->buf;
     -+}
      +
     -+/* return a newly malloced string for this slice */
     -+char *slice_to_string(struct slice in)
     -+{
     -+	struct slice s = SLICE_INIT;
     -+	assert(in.canary == SLICE_CANARY);
     -+	slice_resize(&s, in.len + 1);
     -+	s.buf[in.len] = 0;
     -+	memcpy(s.buf, in.buf, in.len);
     -+	return (char *)slice_detach(&s);
     -+}
     ++	for (i = 0; i < N; i++) {
     ++		byte hash[SHA256_SIZE] = { 0 };
     ++		char name[100];
     ++		int n;
      +
     -+bool slice_equal(struct slice a, struct slice b)
     -+{
     -+	assert(a.canary == SLICE_CANARY);
     -+	assert(b.canary == SLICE_CANARY);
     -+	if (a.len != b.len)
     -+		return 0;
     -+	return memcmp(a.buf, b.buf, a.len) == 0;
     -+}
     ++		set_test_hash(hash, i);
      +
     -+int slice_cmp(struct slice a, struct slice b)
     -+{
     -+	int min = a.len < b.len ? a.len : b.len;
     -+	int res = memcmp(a.buf, b.buf, min);
     -+	assert(a.canary == SLICE_CANARY);
     -+	assert(b.canary == SLICE_CANARY);
     -+	if (res != 0)
     -+		return res;
     -+	if (a.len < b.len)
     -+		return -1;
     -+	else if (a.len > b.len)
     -+		return 1;
     -+	else
     -+		return 0;
     -+}
     ++		snprintf(name, sizeof(name), "refs/heads/branch%02d", i);
      +
     -+int slice_add(struct slice *b, byte *data, size_t sz)
     -+{
     -+	assert(b->canary == SLICE_CANARY);
     -+	if (b->len + sz > b->cap) {
     -+		int newcap = 2 * b->cap + 1;
     -+		if (newcap < b->len + sz) {
     -+			newcap = (b->len + sz);
     ++		log.ref_name = name;
     ++		log.new_hash = hash;
     ++		log.update_index = update_index;
     ++		log.message = "message";
     ++
     ++		n = reftable_writer_add_log(w, &log);
     ++		assert(n == 0);
     ++	}
     ++
     ++	n = reftable_writer_close(w);
     ++	assert(n == 0);
     ++
     ++	stats = writer_stats(w);
     ++	for (i = 0; i < stats->ref_stats.blocks; i++) {
     ++		int off = i * opts.block_size;
     ++		if (off == 0) {
     ++			off = header_size((hash_id == SHA256_ID) ? 2 : 1);
      +		}
     -+		b->buf = reftable_realloc(b->buf, newcap);
     -+		b->cap = newcap;
     ++		assert(buf->buf[off] == 'r');
      +	}
      +
     -+	memcpy(b->buf + b->len, data, sz);
     -+	b->len += sz;
     -+	return sz;
     ++	assert(stats->log_stats.blocks > 0);
     ++	reftable_writer_free(w);
      +}
      +
     -+int slice_add_void(void *b, byte *data, size_t sz)
     ++static void test_log_buffer_size(void)
      +{
     -+	return slice_add((struct slice *)b, data, sz);
     -+}
     ++	struct slice buf = SLICE_INIT;
     ++	struct reftable_write_options opts = {
     ++		.block_size = 4096,
     ++	};
     ++	int err;
     ++	struct reftable_log_record log = {
     ++		.ref_name = "refs/heads/master",
     ++		.name = "Han-Wen Nienhuys",
     ++		.email = "[email-masked]",
     ++		.tz_offset = 100,
     ++		.time = 0x5e430672,
     ++		.update_index = 0xa,
     ++		.message = "commit: 9\n",
     ++	};
     ++	struct reftable_writer *w =
     ++		reftable_new_writer(&slice_add_void, &buf, &opts);
      +
     -+static uint64_t slice_size(void *b)
     -+{
     -+	return ((struct slice *)b)->len;
     -+}
     ++	/* This tests buffer extension for log compression. Must use a random
     ++	   hash, to ensure that the compressed part is larger than the original.
     ++	*/
     ++	byte hash1[SHA1_SIZE], hash2[SHA1_SIZE];
     ++	for (int i = 0; i < SHA1_SIZE; i++) {
     ++		hash1[i] = (byte)(rand() % 256);
     ++		hash2[i] = (byte)(rand() % 256);
     ++	}
     ++	log.old_hash = hash1;
     ++	log.new_hash = hash2;
     ++	reftable_writer_set_limits(w, update_index, update_index);
     ++	err = reftable_writer_add_log(w, &log);
     ++	assert_err(err);
     ++	err = reftable_writer_close(w);
     ++	assert_err(err);
     ++	reftable_writer_free(w);
     ++	slice_release(&buf);
     ++}
     ++
     ++static void test_log_write_read(void)
     ++{
     ++	int N = 2;
     ++	char **names = reftable_calloc(sizeof(char *) * (N + 1));
     ++	int err;
     ++	struct reftable_write_options opts = {
     ++		.block_size = 256,
     ++	};
     ++	struct reftable_ref_record ref = { 0 };
     ++	int i = 0;
     ++	struct reftable_log_record log = { 0 };
     ++	int n;
     ++	struct reftable_iterator it = { 0 };
     ++	struct reftable_reader rd = { 0 };
     ++	struct reftable_block_source source = { 0 };
     ++	struct slice buf = SLICE_INIT;
     ++	struct reftable_writer *w =
     ++		reftable_new_writer(&slice_add_void, &buf, &opts);
     ++	const struct reftable_stats *stats = NULL;
     ++	reftable_writer_set_limits(w, 0, N);
     ++	for (i = 0; i < N; i++) {
     ++		char name[256];
     ++		struct reftable_ref_record ref = { 0 };
     ++		snprintf(name, sizeof(name), "b%02d%0*d", i, 130, 7);
     ++		names[i] = xstrdup(name);
     ++		puts(name);
     ++		ref.ref_name = name;
     ++		ref.update_index = i;
      +
     -+static void slice_return_block(void *b, struct reftable_block *dest)
     -+{
     -+	memset(dest->data, 0xff, dest->len);
     -+	reftable_free(dest->data);
     -+}
     ++		err = reftable_writer_add_ref(w, &ref);
     ++		assert_err(err);
     ++	}
     ++	for (i = 0; i < N; i++) {
     ++		byte hash1[SHA1_SIZE], hash2[SHA1_SIZE];
     ++		struct reftable_log_record log = { 0 };
     ++		set_test_hash(hash1, i);
     ++		set_test_hash(hash2, i + 1);
      +
     -+static void slice_close(void *b)
     -+{
     -+}
     ++		log.ref_name = names[i];
     ++		log.update_index = i;
     ++		log.old_hash = hash1;
     ++		log.new_hash = hash2;
      +
     -+static int slice_read_block(void *v, struct reftable_block *dest, uint64_t off,
     -+			    uint32_t size)
     -+{
     -+	struct slice *b = (struct slice *)v;
     -+	assert(off + size <= b->len);
     -+	dest->data = reftable_calloc(size);
     -+	memcpy(dest->data, b->buf + off, size);
     -+	dest->len = size;
     -+	return size;
     -+}
     ++		err = reftable_writer_add_log(w, &log);
     ++		assert_err(err);
     ++	}
      +
     -+struct reftable_block_source_vtable slice_vtable = {
     -+	.size = &slice_size,
     -+	.read_block = &slice_read_block,
     -+	.return_block = &slice_return_block,
     -+	.close = &slice_close,
     -+};
     ++	n = reftable_writer_close(w);
     ++	assert(n == 0);
      +
     -+void block_source_from_slice(struct reftable_block_source *bs,
     -+			     struct slice *buf)
     -+{
     -+	assert(bs->ops == NULL);
     -+	bs->ops = &slice_vtable;
     -+	bs->arg = buf;
     -+}
     ++	stats = writer_stats(w);
     ++	assert(stats->log_stats.blocks > 0);
     ++	reftable_writer_free(w);
     ++	w = NULL;
      +
     -+static void malloc_return_block(void *b, struct reftable_block *dest)
     -+{
     -+	memset(dest->data, 0xff, dest->len);
     -+	reftable_free(dest->data);
     -+}
     ++	block_source_from_slice(&source, &buf);
      +
     -+struct reftable_block_source_vtable malloc_vtable = {
     -+	.return_block = &malloc_return_block,
     -+};
     ++	err = init_reader(&rd, &source, "file.log");
     ++	assert_err(err);
      +
     -+struct reftable_block_source malloc_block_source_instance = {
     -+	.ops = &malloc_vtable,
     -+};
     ++	err = reftable_reader_seek_ref(&rd, &it, names[N - 1]);
     ++	assert_err(err);
      +
     -+struct reftable_block_source malloc_block_source(void)
     -+{
     -+	return malloc_block_source_instance;
     -+}
     ++	err = reftable_iterator_next_ref(&it, &ref);
     ++	assert_err(err);
      +
     -+int common_prefix_size(struct slice a, struct slice b)
     -+{
     -+	int p = 0;
     -+	assert(a.canary == SLICE_CANARY);
     -+	assert(b.canary == SLICE_CANARY);
     -+	while (p < a.len && p < b.len) {
     -+		if (a.buf[p] != b.buf[p]) {
     ++	/* end of iteration. */
     ++	err = reftable_iterator_next_ref(&it, &ref);
     ++	assert(0 < err);
     ++
     ++	reftable_iterator_destroy(&it);
     ++	reftable_ref_record_clear(&ref);
     ++
     ++	err = reftable_reader_seek_log(&rd, &it, "");
     ++	assert_err(err);
     ++
     ++	i = 0;
     ++	while (true) {
     ++		int err = reftable_iterator_next_log(&it, &log);
     ++		if (err > 0) {
      +			break;
      +		}
     -+		p++;
     ++
     ++		assert_err(err);
     ++		assert_streq(names[i], log.ref_name);
     ++		assert(i == log.update_index);
     ++		i++;
     ++		reftable_log_record_clear(&log);
      +	}
      +
     -+	return p;
     ++	assert(i == N);
     ++	reftable_iterator_destroy(&it);
     ++
     ++	/* cleanup. */
     ++	slice_release(&buf);
     ++	free_names(names);
     ++	reader_close(&rd);
      +}
     -
     - ## reftable/slice.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
     -+*/
     ++static void test_table_read_write_sequential(void)
     ++{
     ++	char **names;
     ++	struct slice buf = SLICE_INIT;
     ++	int N = 50;
     ++	struct reftable_iterator it = { 0 };
     ++	struct reftable_block_source source = { 0 };
     ++	struct reftable_reader rd = { 0 };
     ++	int err = 0;
     ++	int j = 0;
      +
     -+#ifndef SLICE_H
     -+#define SLICE_H
     ++	write_table(&names, &buf, N, 256, SHA1_ID);
      +
     -+#include "basics.h"
     -+#include "reftable.h"
     ++	block_source_from_slice(&source, &buf);
      +
     -+/*
     -+  provides bounds-checked byte ranges.
     -+  To use, initialize as "slice x = {0};"
     -+ */
     -+struct slice {
     -+	int len;
     -+	int cap;
     -+	byte *buf;
     -+	byte canary;
     -+};
     -+#define SLICE_CANARY 0x42
     -+#define SLICE_INIT                       \
     -+	{                                \
     -+		0, 0, NULL, SLICE_CANARY \
     ++	err = init_reader(&rd, &source, "file.ref");
     ++	assert_err(err);
     ++
     ++	err = reftable_reader_seek_ref(&rd, &it, "");
     ++	assert_err(err);
     ++
     ++	while (true) {
     ++		struct reftable_ref_record ref = { 0 };
     ++		int r = reftable_iterator_next_ref(&it, &ref);
     ++		assert(r >= 0);
     ++		if (r > 0) {
     ++			break;
     ++		}
     ++		assert(0 == strcmp(names[j], ref.ref_name));
     ++		assert(update_index == ref.update_index);
     ++
     ++		j++;
     ++		reftable_ref_record_clear(&ref);
      +	}
     -+extern struct slice reftable_empty_slice;
     ++	assert(j == N);
     ++	reftable_iterator_destroy(&it);
     ++	slice_release(&buf);
     ++	free_names(names);
      +
     -+void slice_set_string(struct slice *dest, const char *src);
     -+void slice_addstr(struct slice *dest, const char *src);
     ++	reader_close(&rd);
     ++}
      +
     -+/* Deallocate and clear slice */
     -+void slice_release(struct slice *slice);
     ++static void test_table_write_small_table(void)
     ++{
     ++	char **names;
     ++	struct slice buf = SLICE_INIT;
     ++	int N = 1;
     ++	write_table(&names, &buf, N, 4096, SHA1_ID);
     ++	assert(buf.len < 200);
     ++	slice_release(&buf);
     ++	free_names(names);
     ++}
      +
     -+/* Return a malloced string for `src` */
     -+char *slice_to_string(struct slice src);
     ++static void test_table_read_api(void)
     ++{
     ++	char **names;
     ++	struct slice buf = SLICE_INIT;
     ++	int N = 50;
     ++	struct reftable_reader rd = { 0 };
     ++	struct reftable_block_source source = { 0 };
     ++	int err;
     ++	int i;
     ++	struct reftable_log_record log = { 0 };
     ++	struct reftable_iterator it = { 0 };
      +
     -+/* Initializes a slice. Accepts a slice with random garbage. */
     -+void slice_init(struct slice *slice);
     ++	write_table(&names, &buf, N, 256, SHA1_ID);
      +
     -+/* Ensure that `buf` is \0 terminated. */
     -+const char *slice_as_string(struct slice *src);
     ++	block_source_from_slice(&source, &buf);
      +
     -+/* Compare slices */
     -+bool slice_equal(struct slice a, struct slice b);
     ++	err = init_reader(&rd, &source, "file.ref");
     ++	assert_err(err);
      +
     -+/* Return `buf`, clearing out `s` */
     -+byte *slice_detach(struct slice *s);
     ++	err = reftable_reader_seek_ref(&rd, &it, names[0]);
     ++	assert_err(err);
      +
     -+/* Copy bytes */
     -+void slice_copy(struct slice *dest, struct slice src);
     ++	err = reftable_iterator_next_log(&it, &log);
     ++	assert(err == REFTABLE_API_ERROR);
      +
     -+/* Advance `buf` by `n`, and decrease length. A copy of the slice
     -+   should be kept for deallocating the slice. */
     -+void slice_consume(struct slice *s, int n);
     ++	slice_release(&buf);
     ++	for (i = 0; i < N; i++) {
     ++		reftable_free(names[i]);
     ++	}
     ++	reftable_iterator_destroy(&it);
     ++	reftable_free(names);
     ++	reader_close(&rd);
     ++	slice_release(&buf);
     ++}
      +
     -+/* Set length of the slice to `l` */
     -+void slice_resize(struct slice *s, int l);
     ++static void test_table_read_write_seek(bool index, int hash_id)
     ++{
     ++	char **names;
     ++	struct slice buf = SLICE_INIT;
     ++	int N = 50;
     ++	struct reftable_reader rd = { 0 };
     ++	struct reftable_block_source source = { 0 };
     ++	int err;
     ++	int i = 0;
      +
     -+/* Signed comparison */
     -+int slice_cmp(struct slice a, struct slice b);
     ++	struct reftable_iterator it = { 0 };
     ++	struct slice pastLast = SLICE_INIT;
     ++	struct reftable_ref_record ref = { 0 };
      +
     -+/* Append `data` to the `dest` slice.  */
     -+int slice_add(struct slice *dest, byte *data, size_t sz);
     ++	write_table(&names, &buf, N, 256, hash_id);
      +
     -+/* Append `add` to `dest. */
     -+void slice_addbuf(struct slice *dest, struct slice add);
     ++	block_source_from_slice(&source, &buf);
      +
     -+/* Like slice_add, but suitable for passing to reftable_new_writer
     -+ */
     -+int slice_add_void(void *b, byte *data, size_t sz);
     ++	err = init_reader(&rd, &source, "file.ref");
     ++	assert_err(err);
     ++	assert(hash_id == reftable_reader_hash_id(&rd));
      +
     -+/* Find the longest shared prefix size of `a` and `b` */
     -+int common_prefix_size(struct slice a, struct slice b);
     ++	if (!index) {
     ++		rd.ref_offsets.index_offset = 0;
     ++	} else {
     ++		assert(rd.ref_offsets.index_offset > 0);
     ++	}
      +
     -+struct reftable_block_source;
     ++	for (i = 1; i < N; i++) {
     ++		int err = reftable_reader_seek_ref(&rd, &it, names[i]);
     ++		assert_err(err);
     ++		err = reftable_iterator_next_ref(&it, &ref);
     ++		assert_err(err);
     ++		assert(0 == strcmp(names[i], ref.ref_name));
     ++		assert(i == ref.value[0]);
      +
     -+/* Create an in-memory block source for reading reftables */
     -+void block_source_from_slice(struct reftable_block_source *bs,
     -+			     struct slice *buf);
     ++		reftable_ref_record_clear(&ref);
     ++		reftable_iterator_destroy(&it);
     ++	}
      +
     -+struct reftable_block_source malloc_block_source(void);
     ++	slice_set_string(&pastLast, names[N - 1]);
     ++	slice_addstr(&pastLast, "/");
      +
     -+#endif
     -
     - ## reftable/stack.c (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     ++	err = reftable_reader_seek_ref(&rd, &it, slice_as_string(&pastLast));
     ++	if (err == 0) {
     ++		struct reftable_ref_record ref = { 0 };
     ++		int err = reftable_iterator_next_ref(&it, &ref);
     ++		assert(err > 0);
     ++	} else {
     ++		assert(err > 0);
     ++	}
      +
     -+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
     -+*/
     ++	slice_release(&pastLast);
     ++	reftable_iterator_destroy(&it);
      +
     -+#include "stack.h"
     ++	slice_release(&buf);
     ++	for (i = 0; i < N; i++) {
     ++		reftable_free(names[i]);
     ++	}
     ++	reftable_free(names);
     ++	reader_close(&rd);
     ++}
      +
     -+#include "system.h"
     -+#include "merged.h"
     -+#include "reader.h"
     -+#include "refname.h"
     -+#include "reftable.h"
     -+#include "writer.h"
     ++static void test_table_read_write_seek_linear(void)
     ++{
     ++	test_table_read_write_seek(false, SHA1_ID);
     ++}
      +
     -+int reftable_new_stack(struct reftable_stack **dest, const char *dir,
     -+		       struct reftable_write_options config)
     ++static void test_table_read_write_seek_linear_sha256(void)
      +{
     -+	struct reftable_stack *p =
     -+		reftable_calloc(sizeof(struct reftable_stack));
     -+	struct slice list_file_name = SLICE_INIT;
     -+	int err = 0;
     ++	test_table_read_write_seek(false, SHA256_ID);
     ++}
      +
     -+	if (config.hash_id == 0) {
     -+		config.hash_id = SHA1_ID;
     -+	}
     ++static void test_table_read_write_seek_index(void)
     ++{
     ++	test_table_read_write_seek(true, SHA1_ID);
     ++}
      +
     -+	*dest = NULL;
     ++static void test_table_refs_for(bool indexed)
     ++{
     ++	int N = 50;
     ++	char **want_names = reftable_calloc(sizeof(char *) * (N + 1));
     ++	int want_names_len = 0;
     ++	byte want_hash[SHA1_SIZE];
      +
     -+	slice_set_string(&list_file_name, dir);
     -+	slice_addstr(&list_file_name, "/tables.list");
     ++	struct reftable_write_options opts = {
     ++		.block_size = 256,
     ++	};
     ++	struct reftable_ref_record ref = { 0 };
     ++	int i = 0;
     ++	int n;
     ++	int err;
     ++	struct reftable_reader rd;
     ++	struct reftable_block_source source = { 0 };
      +
     -+	p->list_file = slice_to_string(list_file_name);
     -+	slice_release(&list_file_name);
     -+	p->reftable_dir = xstrdup(dir);
     -+	p->config = config;
     ++	struct slice buf = SLICE_INIT;
     ++	struct reftable_writer *w =
     ++		reftable_new_writer(&slice_add_void, &buf, &opts);
      +
     -+	err = reftable_stack_reload_maybe_reuse(p, true);
     -+	if (err < 0) {
     -+		reftable_stack_destroy(p);
     -+	} else {
     -+		*dest = p;
     -+	}
     -+	return err;
     -+}
     ++	struct reftable_iterator it = { 0 };
     ++	int j;
      +
     -+static int fd_read_lines(int fd, char ***namesp)
     -+{
     -+	off_t size = lseek(fd, 0, SEEK_END);
     -+	char *buf = NULL;
     -+	int err = 0;
     -+	if (size < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		goto done;
     -+	}
     -+	err = lseek(fd, 0, SEEK_SET);
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		goto done;
     ++	set_test_hash(want_hash, 4);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		byte hash[SHA1_SIZE];
     ++		char fill[51] = { 0 };
     ++		char name[100];
     ++		byte hash1[SHA1_SIZE];
     ++		byte hash2[SHA1_SIZE];
     ++		struct reftable_ref_record ref = { 0 };
     ++
     ++		memset(hash, i, sizeof(hash));
     ++		memset(fill, 'x', 50);
     ++		/* Put the variable part in the start */
     ++		snprintf(name, sizeof(name), "br%02d%s", i, fill);
     ++		name[40] = 0;
     ++		ref.ref_name = name;
     ++
     ++		set_test_hash(hash1, i / 4);
     ++		set_test_hash(hash2, 3 + i / 4);
     ++		ref.value = hash1;
     ++		ref.target_value = hash2;
     ++
     ++		/* 80 bytes / entry, so 3 entries per block. Yields 17
     ++		 */
     ++		/* blocks. */
     ++		n = reftable_writer_add_ref(w, &ref);
     ++		assert(n == 0);
     ++
     ++		if (!memcmp(hash1, want_hash, SHA1_SIZE) ||
     ++		    !memcmp(hash2, want_hash, SHA1_SIZE)) {
     ++			want_names[want_names_len++] = xstrdup(name);
     ++		}
      +	}
      +
     -+	buf = reftable_malloc(size + 1);
     -+	if (read(fd, buf, size) != size) {
     -+		err = REFTABLE_IO_ERROR;
     -+		goto done;
     ++	n = reftable_writer_close(w);
     ++	assert(n == 0);
     ++
     ++	reftable_writer_free(w);
     ++	w = NULL;
     ++
     ++	block_source_from_slice(&source, &buf);
     ++
     ++	err = init_reader(&rd, &source, "file.ref");
     ++	assert_err(err);
     ++	if (!indexed) {
     ++		rd.obj_offsets.present = 0;
      +	}
     -+	buf[size] = 0;
      +
     -+	parse_names(buf, size, namesp);
     ++	err = reftable_reader_seek_ref(&rd, &it, "");
     ++	assert_err(err);
     ++	reftable_iterator_destroy(&it);
      +
     -+done:
     -+	reftable_free(buf);
     -+	return err;
     -+}
     ++	err = reftable_reader_refs_for(&rd, &it, want_hash);
     ++	assert_err(err);
      +
     -+int read_lines(const char *filename, char ***namesp)
     -+{
     -+	int fd = open(filename, O_RDONLY, 0644);
     -+	int err = 0;
     -+	if (fd < 0) {
     -+		if (errno == ENOENT) {
     -+			*namesp = reftable_calloc(sizeof(char *));
     -+			return 0;
     ++	j = 0;
     ++	while (true) {
     ++		int err = reftable_iterator_next_ref(&it, &ref);
     ++		assert(err >= 0);
     ++		if (err > 0) {
     ++			break;
      +		}
      +
     -+		return REFTABLE_IO_ERROR;
     ++		assert(j < want_names_len);
     ++		assert(0 == strcmp(ref.ref_name, want_names[j]));
     ++		j++;
     ++		reftable_ref_record_clear(&ref);
      +	}
     -+	err = fd_read_lines(fd, namesp);
     -+	close(fd);
     -+	return err;
     -+}
     ++	assert(j == want_names_len);
      +
     -+struct reftable_merged_table *
     -+reftable_stack_merged_table(struct reftable_stack *st)
     -+{
     -+	return st->merged;
     ++	slice_release(&buf);
     ++	free_names(want_names);
     ++	reftable_iterator_destroy(&it);
     ++	reader_close(&rd);
      +}
      +
     -+/* Close and free the stack */
     -+void reftable_stack_destroy(struct reftable_stack *st)
     ++static void test_table_refs_for_no_index(void)
      +{
     -+	if (st->merged != NULL) {
     -+		reftable_merged_table_close(st->merged);
     -+		reftable_merged_table_free(st->merged);
     -+		st->merged = NULL;
     -+	}
     -+	FREE_AND_NULL(st->list_file);
     -+	FREE_AND_NULL(st->reftable_dir);
     -+	reftable_free(st);
     ++	test_table_refs_for(false);
      +}
      +
     -+static struct reftable_reader **stack_copy_readers(struct reftable_stack *st,
     -+						   int cur_len)
     ++static void test_table_refs_for_obj_index(void)
      +{
     -+	struct reftable_reader **cur =
     -+		reftable_calloc(sizeof(struct reftable_reader *) * cur_len);
     -+	int i = 0;
     -+	for (i = 0; i < cur_len; i++) {
     -+		cur[i] = st->merged->stack[i];
     -+	}
     -+	return cur;
     ++	test_table_refs_for(true);
      +}
      +
     -+static int reftable_stack_reload_once(struct reftable_stack *st, char **names,
     -+				      bool reuse_open)
     ++static void test_table_empty(void)
      +{
     -+	int cur_len = st->merged == NULL ? 0 : st->merged->stack_len;
     -+	struct reftable_reader **cur = stack_copy_readers(st, cur_len);
     -+	int err = 0;
     -+	int names_len = names_length(names);
     -+	struct reftable_reader **new_tables =
     -+		reftable_malloc(sizeof(struct reftable_reader *) * names_len);
     -+	int new_tables_len = 0;
     -+	struct reftable_merged_table *new_merged = NULL;
     -+	int i;
     -+	struct slice table_path = SLICE_INIT;
     ++	struct reftable_write_options opts = { 0 };
     ++	struct slice buf = SLICE_INIT;
     ++	struct reftable_writer *w =
     ++		reftable_new_writer(&slice_add_void, &buf, &opts);
     ++	struct reftable_block_source source = { 0 };
     ++	struct reftable_reader *rd = NULL;
     ++	struct reftable_ref_record rec = { 0 };
     ++	struct reftable_iterator it = { 0 };
     ++	int err;
      +
     -+	while (*names) {
     -+		struct reftable_reader *rd = NULL;
     -+		char *name = *names++;
     ++	reftable_writer_set_limits(w, 1, 1);
      +
     -+		/* this is linear; we assume compaction keeps the number of
     -+		   tables under control so this is not quadratic. */
     -+		int j = 0;
     -+		for (j = 0; reuse_open && j < cur_len; j++) {
     -+			if (cur[j] != NULL && 0 == strcmp(cur[j]->name, name)) {
     -+				rd = cur[j];
     -+				cur[j] = NULL;
     -+				break;
     -+			}
     -+		}
     ++	err = reftable_writer_close(w);
     ++	assert(err == REFTABLE_EMPTY_TABLE_ERROR);
     ++	reftable_writer_free(w);
      +
     -+		if (rd == NULL) {
     -+			struct reftable_block_source src = { 0 };
     -+			slice_set_string(&table_path, st->reftable_dir);
     -+			slice_addstr(&table_path, "/");
     -+			slice_addstr(&table_path, name);
     ++	assert(buf.len == header_size(1) + footer_size(1));
      +
     -+			err = reftable_block_source_from_file(
     -+				&src, slice_as_string(&table_path));
     -+			if (err < 0)
     -+				goto done;
     ++	block_source_from_slice(&source, &buf);
      +
     -+			err = reftable_new_reader(&rd, &src, name);
     -+			if (err < 0)
     -+				goto done;
     -+		}
     ++	err = reftable_new_reader(&rd, &source, "filename");
     ++	assert_err(err);
      +
     -+		new_tables[new_tables_len++] = rd;
     -+	}
     ++	err = reftable_reader_seek_ref(rd, &it, "");
     ++	assert_err(err);
      +
     -+	/* success! */
     -+	err = reftable_new_merged_table(&new_merged, new_tables, new_tables_len,
     -+					st->config.hash_id);
     -+	if (err < 0)
     -+		goto done;
     ++	err = reftable_iterator_next_ref(&it, &rec);
     ++	assert(err > 0);
      +
     -+	new_tables = NULL;
     -+	new_tables_len = 0;
     -+	if (st->merged != NULL) {
     -+		merged_table_clear(st->merged);
     -+		reftable_merged_table_free(st->merged);
     -+	}
     -+	new_merged->suppress_deletions = true;
     -+	st->merged = new_merged;
     ++	reftable_iterator_destroy(&it);
     ++	reftable_reader_free(rd);
     ++	slice_release(&buf);
     ++}
     ++
     ++int reftable_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("test_default_write_opts", test_default_write_opts);
     ++	add_test_case("test_log_write_read", test_log_write_read);
     ++	add_test_case("test_table_read_write_seek_linear_sha256",
     ++		      &test_table_read_write_seek_linear_sha256);
     ++	add_test_case("test_log_buffer_size", test_log_buffer_size);
     ++	add_test_case("test_table_write_small_table",
     ++		      &test_table_write_small_table);
     ++	add_test_case("test_buffer", &test_buffer);
     ++	add_test_case("test_table_read_api", &test_table_read_api);
     ++	add_test_case("test_table_read_write_sequential",
     ++		      &test_table_read_write_sequential);
     ++	add_test_case("test_table_read_write_seek_linear",
     ++		      &test_table_read_write_seek_linear);
     ++	add_test_case("test_table_read_write_seek_index",
     ++		      &test_table_read_write_seek_index);
     ++	add_test_case("test_table_read_write_refs_for_no_index",
     ++		      &test_table_refs_for_no_index);
     ++	add_test_case("test_table_read_write_refs_for_obj_index",
     ++		      &test_table_refs_for_obj_index);
     ++	add_test_case("test_table_empty", &test_table_empty);
     ++	return test_main(argc, argv);
     ++}
     +
     + ## reftable/slice.c (new) ##
     +@@
     ++/*
     ++Copyright 2020 Google LLC
      +
     -+	for (i = 0; i < cur_len; i++) {
     -+		if (cur[i] != NULL) {
     -+			reader_close(cur[i]);
     -+			reftable_reader_free(cur[i]);
     -+		}
     -+	}
     ++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
     ++*/
      +
     -+done:
     -+	slice_release(&table_path);
     -+	for (i = 0; i < new_tables_len; i++) {
     -+		reader_close(new_tables[i]);
     -+		reftable_reader_free(new_tables[i]);
     -+	}
     -+	reftable_free(new_tables);
     -+	reftable_free(cur);
     -+	return err;
     -+}
     ++#include "slice.h"
      +
     -+/* return negative if a before b. */
     -+static int tv_cmp(struct timeval *a, struct timeval *b)
     ++#include "system.h"
     ++
     ++#include "reftable.h"
     ++
     ++struct slice reftable_empty_slice = SLICE_INIT;
     ++
     ++void slice_set_string(struct slice *s, const char *str)
      +{
     -+	time_t diff = a->tv_sec - b->tv_sec;
     -+	int udiff = a->tv_usec - b->tv_usec;
     ++	int l;
     ++	if (str == NULL) {
     ++		s->len = 0;
     ++		return;
     ++	}
     ++	assert(s->canary == SLICE_CANARY);
      +
     -+	if (diff != 0)
     -+		return diff;
     ++	l = strlen(str);
     ++	l++; /* \0 */
     ++	slice_resize(s, l);
     ++	memcpy(s->buf, str, l);
     ++	s->len = l - 1;
     ++}
      +
     -+	return udiff;
     ++void slice_init(struct slice *s)
     ++{
     ++	struct slice empty = SLICE_INIT;
     ++	*s = empty;
      +}
      +
     -+int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
     -+				      bool reuse_open)
     ++void slice_resize(struct slice *s, int l)
      +{
     -+	struct timeval deadline = { 0 };
     ++	assert(s->canary == SLICE_CANARY);
     ++	if (s->cap < l) {
     ++		int c = s->cap * 2;
     ++		if (c < l) {
     ++			c = l;
     ++		}
     ++		s->cap = c;
     ++		s->buf = reftable_realloc(s->buf, s->cap);
     ++	}
     ++	s->len = l;
     ++}
     ++
     ++void slice_addstr(struct slice *d, const char *s)
     ++{
     ++	int l1 = d->len;
     ++	int l2 = strlen(s);
     ++	assert(d->canary == SLICE_CANARY);
     ++
     ++	slice_resize(d, l2 + l1);
     ++	memcpy(d->buf + l1, s, l2);
     ++}
     ++
     ++void slice_addbuf(struct slice *s, struct slice *a)
     ++{
     ++	int end = s->len;
     ++	assert(s->canary == SLICE_CANARY);
     ++	slice_resize(s, s->len + a->len);
     ++	memcpy(s->buf + end, a->buf, a->len);
     ++}
     ++
     ++void slice_consume(struct slice *s, int n)
     ++{
     ++	assert(s->canary == SLICE_CANARY);
     ++	s->buf += n;
     ++	s->len -= n;
     ++}
     ++
     ++byte *slice_detach(struct slice *s)
     ++{
     ++	byte *p = s->buf;
     ++	assert(s->canary == SLICE_CANARY);
     ++	s->buf = NULL;
     ++	s->cap = 0;
     ++	s->len = 0;
     ++	return p;
     ++}
     ++
     ++void slice_release(struct slice *s)
     ++{
     ++	assert(s->canary == SLICE_CANARY);
     ++	reftable_free(slice_detach(s));
     ++}
     ++
     ++void slice_copy(struct slice *dest, struct slice *src)
     ++{
     ++	assert(dest->canary == SLICE_CANARY);
     ++	assert(src->canary == SLICE_CANARY);
     ++	slice_resize(dest, src->len);
     ++	memcpy(dest->buf, src->buf, src->len);
     ++}
     ++
     ++/* return the underlying data as char*. len is left unchanged, but
     ++   a \0 is added at the end. */
     ++const char *slice_as_string(struct slice *s)
     ++{
     ++	assert(s->canary == SLICE_CANARY);
     ++	if (s->cap == s->len) {
     ++		int l = s->len;
     ++		slice_resize(s, l + 1);
     ++		s->len = l;
     ++	}
     ++	s->buf[s->len] = 0;
     ++	return (const char *)s->buf;
     ++}
     ++
     ++/* return a newly malloced string for this slice */
     ++char *slice_to_string(struct slice *in)
     ++{
     ++	struct slice s = SLICE_INIT;
     ++	assert(in->canary == SLICE_CANARY);
     ++	slice_resize(&s, in->len + 1);
     ++	s.buf[in->len] = 0;
     ++	memcpy(s.buf, in->buf, in->len);
     ++	return (char *)slice_detach(&s);
     ++}
     ++
     ++bool slice_equal(struct slice *a, struct slice *b)
     ++{
     ++	return slice_cmp(a, b) == 0;
     ++}
     ++
     ++int slice_cmp(const struct slice *a, const struct slice *b)
     ++{
     ++	int min = a->len < b->len ? a->len : b->len;
     ++	int res = memcmp(a->buf, b->buf, min);
     ++	assert(a->canary == SLICE_CANARY);
     ++	assert(b->canary == SLICE_CANARY);
     ++	if (res != 0)
     ++		return res;
     ++	if (a->len < b->len)
     ++		return -1;
     ++	else if (a->len > b->len)
     ++		return 1;
     ++	else
     ++		return 0;
     ++}
     ++
     ++int slice_add(struct slice *b, byte *data, size_t sz)
     ++{
     ++	assert(b->canary == SLICE_CANARY);
     ++	if (b->len + sz > b->cap) {
     ++		int newcap = 2 * b->cap + 1;
     ++		if (newcap < b->len + sz) {
     ++			newcap = (b->len + sz);
     ++		}
     ++		b->buf = reftable_realloc(b->buf, newcap);
     ++		b->cap = newcap;
     ++	}
     ++
     ++	memcpy(b->buf + b->len, data, sz);
     ++	b->len += sz;
     ++	return sz;
     ++}
     ++
     ++int slice_add_void(void *b, byte *data, size_t sz)
     ++{
     ++	return slice_add((struct slice *)b, data, sz);
     ++}
     ++
     ++static uint64_t slice_size(void *b)
     ++{
     ++	return ((struct slice *)b)->len;
     ++}
     ++
     ++static void slice_return_block(void *b, struct reftable_block *dest)
     ++{
     ++	memset(dest->data, 0xff, dest->len);
     ++	reftable_free(dest->data);
     ++}
     ++
     ++static void slice_close(void *b)
     ++{
     ++}
     ++
     ++static int slice_read_block(void *v, struct reftable_block *dest, uint64_t off,
     ++			    uint32_t size)
     ++{
     ++	struct slice *b = (struct slice *)v;
     ++	assert(off + size <= b->len);
     ++	dest->data = reftable_calloc(size);
     ++	memcpy(dest->data, b->buf + off, size);
     ++	dest->len = size;
     ++	return size;
     ++}
     ++
     ++struct reftable_block_source_vtable slice_vtable = {
     ++	.size = &slice_size,
     ++	.read_block = &slice_read_block,
     ++	.return_block = &slice_return_block,
     ++	.close = &slice_close,
     ++};
     ++
     ++void block_source_from_slice(struct reftable_block_source *bs,
     ++			     struct slice *buf)
     ++{
     ++	assert(bs->ops == NULL);
     ++	bs->ops = &slice_vtable;
     ++	bs->arg = buf;
     ++}
     ++
     ++static void malloc_return_block(void *b, struct reftable_block *dest)
     ++{
     ++	memset(dest->data, 0xff, dest->len);
     ++	reftable_free(dest->data);
     ++}
     ++
     ++struct reftable_block_source_vtable malloc_vtable = {
     ++	.return_block = &malloc_return_block,
     ++};
     ++
     ++struct reftable_block_source malloc_block_source_instance = {
     ++	.ops = &malloc_vtable,
     ++};
     ++
     ++struct reftable_block_source malloc_block_source(void)
     ++{
     ++	return malloc_block_source_instance;
     ++}
     ++
     ++int common_prefix_size(struct slice *a, struct slice *b)
     ++{
     ++	int p = 0;
     ++	assert(a->canary == SLICE_CANARY);
     ++	assert(b->canary == SLICE_CANARY);
     ++	while (p < a->len && p < b->len) {
     ++		if (a->buf[p] != b->buf[p]) {
     ++			break;
     ++		}
     ++		p++;
     ++	}
     ++
     ++	return p;
     ++}
     +
     + ## reftable/slice.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 SLICE_H
     ++#define SLICE_H
     ++
     ++#include "basics.h"
     ++#include "reftable.h"
     ++
     ++/*
     ++  provides bounds-checked byte ranges.
     ++  To use, initialize as "slice x = {0};"
     ++ */
     ++struct slice {
     ++	int len;
     ++	int cap;
     ++	byte *buf;
     ++	byte canary;
     ++};
     ++#define SLICE_CANARY 0x42
     ++#define SLICE_INIT                       \
     ++	{                                \
     ++		0, 0, NULL, SLICE_CANARY \
     ++	}
     ++extern struct slice reftable_empty_slice;
     ++
     ++void slice_set_string(struct slice *dest, const char *src);
     ++void slice_addstr(struct slice *dest, const char *src);
     ++
     ++/* Deallocate and clear slice */
     ++void slice_release(struct slice *slice);
     ++
     ++/* Return a malloced string for `src` */
     ++char *slice_to_string(struct slice *src);
     ++
     ++/* Initializes a slice. Accepts a slice with random garbage. */
     ++void slice_init(struct slice *slice);
     ++
     ++/* Ensure that `buf` is \0 terminated. */
     ++const char *slice_as_string(struct slice *src);
     ++
     ++/* Compare slices */
     ++bool slice_equal(struct slice *a, struct slice *b);
     ++
     ++/* Return `buf`, clearing out `s` */
     ++byte *slice_detach(struct slice *s);
     ++
     ++/* Copy bytes */
     ++void slice_copy(struct slice *dest, struct slice *src);
     ++
     ++/* Advance `buf` by `n`, and decrease length. A copy of the slice
     ++   should be kept for deallocating the slice. */
     ++void slice_consume(struct slice *s, int n);
     ++
     ++/* Set length of the slice to `l` */
     ++void slice_resize(struct slice *s, int l);
     ++
     ++/* Signed comparison */
     ++int slice_cmp(const struct slice *a, const struct slice *b);
     ++
     ++/* Append `data` to the `dest` slice.  */
     ++int slice_add(struct slice *dest, byte *data, size_t sz);
     ++
     ++/* Append `add` to `dest. */
     ++void slice_addbuf(struct slice *dest, struct slice *add);
     ++
     ++/* Like slice_add, but suitable for passing to reftable_new_writer
     ++ */
     ++int slice_add_void(void *b, byte *data, size_t sz);
     ++
     ++/* Find the longest shared prefix size of `a` and `b` */
     ++int common_prefix_size(struct slice *a, struct slice *b);
     ++
     ++struct reftable_block_source;
     ++
     ++/* Create an in-memory block source for reading reftables */
     ++void block_source_from_slice(struct reftable_block_source *bs,
     ++			     struct slice *buf);
     ++
     ++struct reftable_block_source malloc_block_source(void);
     ++
     ++#endif
     +
     + ## reftable/slice_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 "slice.h"
     ++
     ++#include "system.h"
     ++
     ++#include "basics.h"
     ++#include "record.h"
     ++#include "reftable.h"
     ++#include "test_framework.h"
     ++#include "reftable-tests.h"
     ++
     ++static void test_slice(void)
     ++{
     ++	struct slice s = SLICE_INIT;
     ++	struct slice t = SLICE_INIT;
     ++
     ++	slice_set_string(&s, "abc");
     ++	assert(0 == strcmp("abc", slice_as_string(&s)));
     ++
     ++	slice_set_string(&t, "pqr");
     ++
     ++	slice_addbuf(&s, &t);
     ++	assert(0 == strcmp("abcpqr", slice_as_string(&s)));
     ++
     ++	slice_release(&s);
     ++	slice_release(&t);
     ++}
     ++
     ++int slice_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("test_slice", &test_slice);
     ++	return test_main(argc, argv);
     ++}
     +
     + ## reftable/stack.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 "stack.h"
     ++
     ++#include "system.h"
     ++#include "merged.h"
     ++#include "reader.h"
     ++#include "refname.h"
     ++#include "reftable.h"
     ++#include "writer.h"
     ++
     ++int reftable_new_stack(struct reftable_stack **dest, const char *dir,
     ++		       struct reftable_write_options config)
     ++{
     ++	struct reftable_stack *p =
     ++		reftable_calloc(sizeof(struct reftable_stack));
     ++	struct slice list_file_name = SLICE_INIT;
     ++	int err = 0;
     ++
     ++	if (config.hash_id == 0) {
     ++		config.hash_id = SHA1_ID;
     ++	}
     ++
     ++	*dest = NULL;
     ++
     ++	slice_set_string(&list_file_name, dir);
     ++	slice_addstr(&list_file_name, "/tables.list");
     ++
     ++	p->list_file = slice_to_string(&list_file_name);
     ++	slice_release(&list_file_name);
     ++	p->reftable_dir = xstrdup(dir);
     ++	p->config = config;
     ++
     ++	err = reftable_stack_reload_maybe_reuse(p, true);
     ++	if (err < 0) {
     ++		reftable_stack_destroy(p);
     ++	} else {
     ++		*dest = p;
     ++	}
     ++	return err;
     ++}
     ++
     ++static int fd_read_lines(int fd, char ***namesp)
     ++{
     ++	off_t size = lseek(fd, 0, SEEK_END);
     ++	char *buf = NULL;
     ++	int err = 0;
     ++	if (size < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++	err = lseek(fd, 0, SEEK_SET);
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	buf = reftable_malloc(size + 1);
     ++	if (read(fd, buf, size) != size) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++	buf[size] = 0;
     ++
     ++	parse_names(buf, size, namesp);
     ++
     ++done:
     ++	reftable_free(buf);
     ++	return err;
     ++}
     ++
     ++int read_lines(const char *filename, char ***namesp)
     ++{
     ++	int fd = open(filename, O_RDONLY, 0644);
     ++	int err = 0;
     ++	if (fd < 0) {
     ++		if (errno == ENOENT) {
     ++			*namesp = reftable_calloc(sizeof(char *));
     ++			return 0;
     ++		}
     ++
     ++		return REFTABLE_IO_ERROR;
     ++	}
     ++	err = fd_read_lines(fd, namesp);
     ++	close(fd);
     ++	return err;
     ++}
     ++
     ++struct reftable_merged_table *
     ++reftable_stack_merged_table(struct reftable_stack *st)
     ++{
     ++	return st->merged;
     ++}
     ++
     ++/* Close and free the stack */
     ++void reftable_stack_destroy(struct reftable_stack *st)
     ++{
     ++	if (st->merged != NULL) {
     ++		reftable_merged_table_close(st->merged);
     ++		reftable_merged_table_free(st->merged);
     ++		st->merged = NULL;
     ++	}
     ++	FREE_AND_NULL(st->list_file);
     ++	FREE_AND_NULL(st->reftable_dir);
     ++	reftable_free(st);
     ++}
     ++
     ++static struct reftable_reader **stack_copy_readers(struct reftable_stack *st,
     ++						   int cur_len)
     ++{
     ++	struct reftable_reader **cur =
     ++		reftable_calloc(sizeof(struct reftable_reader *) * cur_len);
     ++	int i = 0;
     ++	for (i = 0; i < cur_len; i++) {
     ++		cur[i] = st->merged->stack[i];
     ++	}
     ++	return cur;
     ++}
     ++
     ++static int reftable_stack_reload_once(struct reftable_stack *st, char **names,
     ++				      bool reuse_open)
     ++{
     ++	int cur_len = st->merged == NULL ? 0 : st->merged->stack_len;
     ++	struct reftable_reader **cur = stack_copy_readers(st, cur_len);
     ++	int err = 0;
     ++	int names_len = names_length(names);
     ++	struct reftable_reader **new_tables =
     ++		reftable_malloc(sizeof(struct reftable_reader *) * names_len);
     ++	int new_tables_len = 0;
     ++	struct reftable_merged_table *new_merged = NULL;
     ++	int i;
     ++	struct slice table_path = SLICE_INIT;
     ++
     ++	while (*names) {
     ++		struct reftable_reader *rd = NULL;
     ++		char *name = *names++;
     ++
     ++		/* this is linear; we assume compaction keeps the number of
     ++		   tables under control so this is not quadratic. */
     ++		int j = 0;
     ++		for (j = 0; reuse_open && j < cur_len; j++) {
     ++			if (cur[j] != NULL && 0 == strcmp(cur[j]->name, name)) {
     ++				rd = cur[j];
     ++				cur[j] = NULL;
     ++				break;
     ++			}
     ++		}
     ++
     ++		if (rd == NULL) {
     ++			struct reftable_block_source src = { 0 };
     ++			slice_set_string(&table_path, st->reftable_dir);
     ++			slice_addstr(&table_path, "/");
     ++			slice_addstr(&table_path, name);
     ++
     ++			err = reftable_block_source_from_file(
     ++				&src, slice_as_string(&table_path));
     ++			if (err < 0)
     ++				goto done;
     ++
     ++			err = reftable_new_reader(&rd, &src, name);
     ++			if (err < 0)
     ++				goto done;
     ++		}
     ++
     ++		new_tables[new_tables_len++] = rd;
     ++	}
     ++
     ++	/* success! */
     ++	err = reftable_new_merged_table(&new_merged, new_tables, new_tables_len,
     ++					st->config.hash_id);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	new_tables = NULL;
     ++	new_tables_len = 0;
     ++	if (st->merged != NULL) {
     ++		merged_table_clear(st->merged);
     ++		reftable_merged_table_free(st->merged);
     ++	}
     ++	new_merged->suppress_deletions = true;
     ++	st->merged = new_merged;
     ++
     ++	for (i = 0; i < cur_len; i++) {
     ++		if (cur[i] != NULL) {
     ++			reader_close(cur[i]);
     ++			reftable_reader_free(cur[i]);
     ++		}
     ++	}
     ++
     ++done:
     ++	slice_release(&table_path);
     ++	for (i = 0; i < new_tables_len; i++) {
     ++		reader_close(new_tables[i]);
     ++		reftable_reader_free(new_tables[i]);
     ++	}
     ++	reftable_free(new_tables);
     ++	reftable_free(cur);
     ++	return err;
     ++}
     ++
     ++/* return negative if a before b. */
     ++static int tv_cmp(struct timeval *a, struct timeval *b)
     ++{
     ++	time_t diff = a->tv_sec - b->tv_sec;
     ++	int udiff = a->tv_usec - b->tv_usec;
     ++
     ++	if (diff != 0)
     ++		return diff;
     ++
     ++	return udiff;
     ++}
     ++
     ++int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
     ++				      bool reuse_open)
     ++{
     ++	struct timeval deadline = { 0 };
      +	int err = gettimeofday(&deadline, NULL);
      +	int64_t delay = 0;
      +	int tries = 0;
      +	if (err < 0)
     -+		return err;
     ++		return err;
     ++
     ++	deadline.tv_sec += 3;
     ++	while (true) {
     ++		char **names = NULL;
     ++		char **names_after = NULL;
     ++		struct timeval now = { 0 };
     ++		int err = gettimeofday(&now, NULL);
     ++		int err2 = 0;
     ++		if (err < 0) {
     ++			return err;
     ++		}
     ++
     ++		/* Only look at deadlines after the first few times. This
     ++		   simplifies debugging in GDB */
     ++		tries++;
     ++		if (tries > 3 && tv_cmp(&now, &deadline) >= 0) {
     ++			break;
     ++		}
     ++
     ++		err = read_lines(st->list_file, &names);
     ++		if (err < 0) {
     ++			free_names(names);
     ++			return err;
     ++		}
     ++		err = reftable_stack_reload_once(st, names, reuse_open);
     ++		if (err == 0) {
     ++			free_names(names);
     ++			break;
     ++		}
     ++		if (err != REFTABLE_NOT_EXIST_ERROR) {
     ++			free_names(names);
     ++			return err;
     ++		}
     ++
     ++		/* err == REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
     ++		   writer. Check if there was one by checking if the name list
     ++		   changed.
     ++		*/
     ++		err2 = read_lines(st->list_file, &names_after);
     ++		if (err2 < 0) {
     ++			free_names(names);
     ++			return err2;
     ++		}
     ++
     ++		if (names_equal(names_after, names)) {
     ++			free_names(names);
     ++			free_names(names_after);
     ++			return err;
     ++		}
     ++		free_names(names);
     ++		free_names(names_after);
     ++
     ++		delay = delay + (delay * rand()) / RAND_MAX + 1;
     ++		sleep_millisec(delay);
     ++	}
     ++
     ++	return 0;
     ++}
     ++
     ++/* -1 = error
     ++ 0 = up to date
     ++ 1 = changed. */
     ++static int stack_uptodate(struct reftable_stack *st)
     ++{
     ++	char **names = NULL;
     ++	int err = read_lines(st->list_file, &names);
     ++	int i = 0;
     ++	if (err < 0)
     ++		return err;
     ++
     ++	for (i = 0; i < st->merged->stack_len; i++) {
     ++		if (names[i] == NULL) {
     ++			err = 1;
     ++			goto done;
     ++		}
     ++
     ++		if (strcmp(st->merged->stack[i]->name, names[i])) {
     ++			err = 1;
     ++			goto done;
     ++		}
     ++	}
     ++
     ++	if (names[st->merged->stack_len] != NULL) {
     ++		err = 1;
     ++		goto done;
     ++	}
     ++
     ++done:
     ++	free_names(names);
     ++	return err;
     ++}
     ++
     ++int reftable_stack_reload(struct reftable_stack *st)
     ++{
     ++	int err = stack_uptodate(st);
     ++	if (err > 0)
     ++		return reftable_stack_reload_maybe_reuse(st, true);
     ++	return err;
     ++}
     ++
     ++int reftable_stack_add(struct reftable_stack *st,
     ++		       int (*write)(struct reftable_writer *wr, void *arg),
     ++		       void *arg)
     ++{
     ++	int err = stack_try_add(st, write, arg);
     ++	if (err < 0) {
     ++		if (err == REFTABLE_LOCK_ERROR) {
     ++			/* Ignore error return, we want to propagate
     ++			   REFTABLE_LOCK_ERROR.
     ++			*/
     ++			reftable_stack_reload(st);
     ++		}
     ++		return err;
     ++	}
     ++
     ++	if (!st->disable_auto_compact)
     ++		return reftable_stack_auto_compact(st);
     ++
     ++	return 0;
     ++}
     ++
     ++static void format_name(struct slice *dest, uint64_t min, uint64_t max)
     ++{
     ++	char buf[100];
     ++	snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64, min, max);
     ++	slice_set_string(dest, buf);
     ++}
     ++
     ++struct reftable_addition {
     ++	int lock_file_fd;
     ++	struct slice lock_file_name;
     ++	struct reftable_stack *stack;
     ++	char **names;
     ++	char **new_tables;
     ++	int new_tables_len;
     ++	uint64_t next_update_index;
     ++};
     ++
     ++#define REFTABLE_ADDITION_INIT               \
     ++	{                                    \
     ++		.lock_file_name = SLICE_INIT \
     ++	}
     ++
     ++static int reftable_stack_init_addition(struct reftable_addition *add,
     ++					struct reftable_stack *st)
     ++{
     ++	int err = 0;
     ++	add->stack = st;
     ++
     ++	slice_set_string(&add->lock_file_name, st->list_file);
     ++	slice_addstr(&add->lock_file_name, ".lock");
     ++
     ++	add->lock_file_fd = open(slice_as_string(&add->lock_file_name),
     ++				 O_EXCL | O_CREAT | O_WRONLY, 0644);
     ++	if (add->lock_file_fd < 0) {
     ++		if (errno == EEXIST) {
     ++			err = REFTABLE_LOCK_ERROR;
     ++		} else {
     ++			err = REFTABLE_IO_ERROR;
     ++		}
     ++		goto done;
     ++	}
     ++	err = stack_uptodate(st);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	if (err > 1) {
     ++		err = REFTABLE_LOCK_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	add->next_update_index = reftable_stack_next_update_index(st);
     ++done:
     ++	if (err) {
     ++		reftable_addition_close(add);
     ++	}
     ++	return err;
     ++}
     ++
     ++void reftable_addition_close(struct reftable_addition *add)
     ++{
     ++	int i = 0;
     ++	struct slice nm = SLICE_INIT;
     ++	for (i = 0; i < add->new_tables_len; i++) {
     ++		slice_set_string(&nm, add->stack->list_file);
     ++		slice_addstr(&nm, "/");
     ++		slice_addstr(&nm, add->new_tables[i]);
     ++		unlink(slice_as_string(&nm));
     ++		reftable_free(add->new_tables[i]);
     ++		add->new_tables[i] = NULL;
     ++	}
     ++	reftable_free(add->new_tables);
     ++	add->new_tables = NULL;
     ++	add->new_tables_len = 0;
     ++
     ++	if (add->lock_file_fd > 0) {
     ++		close(add->lock_file_fd);
     ++		add->lock_file_fd = 0;
     ++	}
     ++	if (add->lock_file_name.len > 0) {
     ++		unlink(slice_as_string(&add->lock_file_name));
     ++		slice_release(&add->lock_file_name);
     ++	}
     ++
     ++	free_names(add->names);
     ++	add->names = NULL;
     ++	slice_release(&nm);
     ++}
     ++
     ++void reftable_addition_destroy(struct reftable_addition *add)
     ++{
     ++	if (add == NULL) {
     ++		return;
     ++	}
     ++	reftable_addition_close(add);
     ++	reftable_free(add);
     ++}
     ++
     ++int reftable_addition_commit(struct reftable_addition *add)
     ++{
     ++	struct slice table_list = SLICE_INIT;
     ++	int i = 0;
     ++	int err = 0;
     ++	if (add->new_tables_len == 0)
     ++		goto done;
     ++
     ++	for (i = 0; i < add->stack->merged->stack_len; i++) {
     ++		slice_addstr(&table_list, add->stack->merged->stack[i]->name);
     ++		slice_addstr(&table_list, "\n");
     ++	}
     ++	for (i = 0; i < add->new_tables_len; i++) {
     ++		slice_addstr(&table_list, add->new_tables[i]);
     ++		slice_addstr(&table_list, "\n");
     ++	}
     ++
     ++	err = write(add->lock_file_fd, table_list.buf, table_list.len);
     ++	slice_release(&table_list);
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	err = close(add->lock_file_fd);
     ++	add->lock_file_fd = 0;
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	err = rename(slice_as_string(&add->lock_file_name),
     ++		     add->stack->list_file);
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	err = reftable_stack_reload(add->stack);
     ++
     ++done:
     ++	reftable_addition_close(add);
     ++	return err;
     ++}
     ++
     ++int reftable_stack_new_addition(struct reftable_addition **dest,
     ++				struct reftable_stack *st)
     ++{
     ++	int err = 0;
     ++	struct reftable_addition empty = REFTABLE_ADDITION_INIT;
     ++	*dest = reftable_calloc(sizeof(**dest));
     ++	**dest = empty;
     ++	err = reftable_stack_init_addition(*dest, st);
     ++	if (err) {
     ++		reftable_free(*dest);
     ++		*dest = NULL;
     ++	}
     ++	return err;
     ++}
     ++
     ++int stack_try_add(struct reftable_stack *st,
     ++		  int (*write_table)(struct reftable_writer *wr, void *arg),
     ++		  void *arg)
     ++{
     ++	struct reftable_addition add = REFTABLE_ADDITION_INIT;
     ++	int err = reftable_stack_init_addition(&add, st);
     ++	if (err < 0)
     ++		goto done;
     ++	if (err > 0) {
     ++		err = REFTABLE_LOCK_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	err = reftable_addition_add(&add, write_table, arg);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	err = reftable_addition_commit(&add);
     ++done:
     ++	reftable_addition_close(&add);
     ++	return err;
     ++}
     ++
     ++int reftable_addition_add(struct reftable_addition *add,
     ++			  int (*write_table)(struct reftable_writer *wr,
     ++					     void *arg),
     ++			  void *arg)
     ++{
     ++	struct slice temp_tab_file_name = SLICE_INIT;
     ++	struct slice tab_file_name = SLICE_INIT;
     ++	struct slice next_name = SLICE_INIT;
     ++	struct reftable_writer *wr = NULL;
     ++	int err = 0;
     ++	int tab_fd = 0;
     ++
     ++	slice_resize(&next_name, 0);
     ++	format_name(&next_name, add->next_update_index, add->next_update_index);
     ++
     ++	slice_set_string(&temp_tab_file_name, add->stack->reftable_dir);
     ++	slice_addstr(&temp_tab_file_name, "/");
     ++	slice_addbuf(&temp_tab_file_name, &next_name);
     ++	slice_addstr(&temp_tab_file_name, ".temp.XXXXXX");
     ++
     ++	tab_fd = mkstemp((char *)slice_as_string(&temp_tab_file_name));
     ++	if (tab_fd < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	wr = reftable_new_writer(reftable_fd_write, &tab_fd,
     ++				 &add->stack->config);
     ++	err = write_table(wr, arg);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	err = reftable_writer_close(wr);
     ++	if (err == REFTABLE_EMPTY_TABLE_ERROR) {
     ++		err = 0;
     ++		goto done;
     ++	}
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	err = close(tab_fd);
     ++	tab_fd = 0;
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	err = stack_check_addition(add->stack,
     ++				   slice_as_string(&temp_tab_file_name));
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	if (wr->min_update_index < add->next_update_index) {
     ++		err = REFTABLE_API_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	format_name(&next_name, wr->min_update_index, wr->max_update_index);
     ++	slice_addstr(&next_name, ".ref");
     ++
     ++	slice_set_string(&tab_file_name, add->stack->reftable_dir);
     ++	slice_addstr(&tab_file_name, "/");
     ++	slice_addbuf(&tab_file_name, &next_name);
     ++
     ++	/* TODO: should check destination out of paranoia */
     ++	err = rename(slice_as_string(&temp_tab_file_name),
     ++		     slice_as_string(&tab_file_name));
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		goto done;
     ++	}
     ++
     ++	add->new_tables = reftable_realloc(add->new_tables,
     ++					   sizeof(*add->new_tables) *
     ++						   (add->new_tables_len + 1));
     ++	add->new_tables[add->new_tables_len] = slice_to_string(&next_name);
     ++	add->new_tables_len++;
     ++done:
     ++	if (tab_fd > 0) {
     ++		close(tab_fd);
     ++		tab_fd = 0;
     ++	}
     ++	if (temp_tab_file_name.len > 0) {
     ++		unlink(slice_as_string(&temp_tab_file_name));
     ++	}
     ++
     ++	slice_release(&temp_tab_file_name);
     ++	slice_release(&tab_file_name);
     ++	slice_release(&next_name);
     ++	reftable_writer_free(wr);
     ++	return err;
     ++}
     ++
     ++uint64_t reftable_stack_next_update_index(struct reftable_stack *st)
     ++{
     ++	int sz = st->merged->stack_len;
     ++	if (sz > 0)
     ++		return reftable_reader_max_update_index(
     ++			       st->merged->stack[sz - 1]) +
     ++		       1;
     ++	return 1;
     ++}
     ++
     ++static int stack_compact_locked(struct reftable_stack *st, int first, int last,
     ++				struct slice *temp_tab,
     ++				struct reftable_log_expiry_config *config)
     ++{
     ++	struct slice next_name = SLICE_INIT;
     ++	int tab_fd = -1;
     ++	struct reftable_writer *wr = NULL;
     ++	int err = 0;
     ++
     ++	format_name(&next_name,
     ++		    reftable_reader_min_update_index(st->merged->stack[first]),
     ++		    reftable_reader_max_update_index(st->merged->stack[first]));
     ++
     ++	slice_set_string(temp_tab, st->reftable_dir);
     ++	slice_addstr(temp_tab, "/");
     ++	slice_addbuf(temp_tab, &next_name);
     ++	slice_addstr(temp_tab, ".temp.XXXXXX");
     ++
     ++	tab_fd = mkstemp((char *)slice_as_string(temp_tab));
     ++	wr = reftable_new_writer(reftable_fd_write, &tab_fd, &st->config);
     ++
     ++	err = stack_write_compact(st, wr, first, last, config);
     ++	if (err < 0)
     ++		goto done;
     ++	err = reftable_writer_close(wr);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	err = close(tab_fd);
     ++	tab_fd = 0;
     ++
     ++done:
     ++	reftable_writer_free(wr);
     ++	if (tab_fd > 0) {
     ++		close(tab_fd);
     ++		tab_fd = 0;
     ++	}
     ++	if (err != 0 && temp_tab->len > 0) {
     ++		unlink(slice_as_string(temp_tab));
     ++		slice_release(temp_tab);
     ++	}
     ++	slice_release(&next_name);
     ++	return err;
     ++}
     ++
     ++int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr,
     ++			int first, int last,
     ++			struct reftable_log_expiry_config *config)
     ++{
     ++	int subtabs_len = last - first + 1;
     ++	struct reftable_reader **subtabs = reftable_calloc(
     ++		sizeof(struct reftable_reader *) * (last - first + 1));
     ++	struct reftable_merged_table *mt = NULL;
     ++	int err = 0;
     ++	struct reftable_iterator it = { 0 };
     ++	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_log_record log = { 0 };
     ++
     ++	uint64_t entries = 0;
     ++
     ++	int i = 0, j = 0;
     ++	for (i = first, j = 0; i <= last; i++) {
     ++		struct reftable_reader *t = st->merged->stack[i];
     ++		subtabs[j++] = t;
     ++		st->stats.bytes += t->size;
     ++	}
     ++	reftable_writer_set_limits(wr,
     ++				   st->merged->stack[first]->min_update_index,
     ++				   st->merged->stack[last]->max_update_index);
     ++
     ++	err = reftable_new_merged_table(&mt, subtabs, subtabs_len,
     ++					st->config.hash_id);
     ++	if (err < 0) {
     ++		reftable_free(subtabs);
     ++		goto done;
     ++	}
     ++
     ++	err = reftable_merged_table_seek_ref(mt, &it, "");
     ++	if (err < 0)
     ++		goto done;
      +
     -+	deadline.tv_sec += 3;
      +	while (true) {
     -+		char **names = NULL;
     -+		char **names_after = NULL;
     -+		struct timeval now = { 0 };
     -+		int err = gettimeofday(&now, NULL);
     -+		int err2 = 0;
     ++		err = reftable_iterator_next_ref(&it, &ref);
     ++		if (err > 0) {
     ++			err = 0;
     ++			break;
     ++		}
      +		if (err < 0) {
     -+			return err;
     ++			break;
     ++		}
     ++		if (first == 0 && reftable_ref_record_is_deletion(&ref)) {
     ++			continue;
      +		}
      +
     -+		/* Only look at deadlines after the first few times. This
     -+		   simplifies debugging in GDB */
     -+		tries++;
     -+		if (tries > 3 && tv_cmp(&now, &deadline) >= 0) {
     ++		err = reftable_writer_add_ref(wr, &ref);
     ++		if (err < 0) {
      +			break;
      +		}
     ++		entries++;
     ++	}
     ++	reftable_iterator_destroy(&it);
      +
     -+		err = read_lines(st->list_file, &names);
     -+		if (err < 0) {
     -+			free_names(names);
     -+			return err;
     ++	err = reftable_merged_table_seek_log(mt, &it, "");
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	while (true) {
     ++		err = reftable_iterator_next_log(&it, &log);
     ++		if (err > 0) {
     ++			err = 0;
     ++			break;
      +		}
     -+		err = reftable_stack_reload_once(st, names, reuse_open);
     -+		if (err == 0) {
     -+			free_names(names);
     ++		if (err < 0) {
      +			break;
      +		}
     -+		if (err != REFTABLE_NOT_EXIST_ERROR) {
     -+			free_names(names);
     -+			return err;
     ++		if (first == 0 && reftable_log_record_is_deletion(&log)) {
     ++			continue;
      +		}
      +
     -+		/* err == REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
     -+		   writer. Check if there was one by checking if the name list
     -+		   changed.
     -+		*/
     -+		err2 = read_lines(st->list_file, &names_after);
     -+		if (err2 < 0) {
     -+			free_names(names);
     -+			return err2;
     ++		if (config != NULL && config->time > 0 &&
     ++		    log.time < config->time) {
     ++			continue;
      +		}
      +
     -+		if (names_equal(names_after, names)) {
     -+			free_names(names);
     -+			free_names(names_after);
     -+			return err;
     ++		if (config != NULL && config->min_update_index > 0 &&
     ++		    log.update_index < config->min_update_index) {
     ++			continue;
      +		}
     -+		free_names(names);
     -+		free_names(names_after);
      +
     -+		delay = delay + (delay * rand()) / RAND_MAX + 1;
     -+		sleep_millisec(delay);
     ++		err = reftable_writer_add_log(wr, &log);
     ++		if (err < 0) {
     ++			break;
     ++		}
     ++		entries++;
     ++	}
     ++
     ++done:
     ++	reftable_iterator_destroy(&it);
     ++	if (mt != NULL) {
     ++		merged_table_clear(mt);
     ++		reftable_merged_table_free(mt);
     ++	}
     ++	reftable_ref_record_clear(&ref);
     ++	reftable_log_record_clear(&log);
     ++	st->stats.entries_written += entries;
     ++	return err;
     ++}
     ++
     ++/* <  0: error. 0 == OK, > 0 attempt failed; could retry. */
     ++static int stack_compact_range(struct reftable_stack *st, int first, int last,
     ++			       struct reftable_log_expiry_config *expiry)
     ++{
     ++	struct slice temp_tab_file_name = SLICE_INIT;
     ++	struct slice new_table_name = SLICE_INIT;
     ++	struct slice lock_file_name = SLICE_INIT;
     ++	struct slice ref_list_contents = SLICE_INIT;
     ++	struct slice new_table_path = SLICE_INIT;
     ++	int err = 0;
     ++	bool have_lock = false;
     ++	int lock_file_fd = 0;
     ++	int compact_count = last - first + 1;
     ++	char **listp = NULL;
     ++	char **delete_on_success =
     ++		reftable_calloc(sizeof(char *) * (compact_count + 1));
     ++	char **subtable_locks =
     ++		reftable_calloc(sizeof(char *) * (compact_count + 1));
     ++	int i = 0;
     ++	int j = 0;
     ++	bool is_empty_table = false;
     ++
     ++	if (first > last || (expiry == NULL && first == last)) {
     ++		err = 0;
     ++		goto done;
     ++	}
     ++
     ++	st->stats.attempts++;
     ++
     ++	slice_set_string(&lock_file_name, st->list_file);
     ++	slice_addstr(&lock_file_name, ".lock");
     ++
     ++	lock_file_fd = open(slice_as_string(&lock_file_name),
     ++			    O_EXCL | O_CREAT | O_WRONLY, 0644);
     ++	if (lock_file_fd < 0) {
     ++		if (errno == EEXIST) {
     ++			err = 1;
     ++		} else {
     ++			err = REFTABLE_IO_ERROR;
     ++		}
     ++		goto done;
     ++	}
     ++	/* Don't want to write to the lock for now.  */
     ++	close(lock_file_fd);
     ++	lock_file_fd = 0;
     ++
     ++	have_lock = true;
     ++	err = stack_uptodate(st);
     ++	if (err != 0)
     ++		goto done;
     ++
     ++	for (i = first, j = 0; i <= last; i++) {
     ++		struct slice subtab_file_name = SLICE_INIT;
     ++		struct slice subtab_lock = SLICE_INIT;
     ++		int sublock_file_fd = -1;
     ++
     ++		slice_set_string(&subtab_file_name, st->reftable_dir);
     ++		slice_addstr(&subtab_file_name, "/");
     ++		slice_addstr(&subtab_file_name,
     ++			     reader_name(st->merged->stack[i]));
     ++
     ++		slice_copy(&subtab_lock, &subtab_file_name);
     ++		slice_addstr(&subtab_lock, ".lock");
     ++
     ++		sublock_file_fd = open(slice_as_string(&subtab_lock),
     ++				       O_EXCL | O_CREAT | O_WRONLY, 0644);
     ++		if (sublock_file_fd > 0) {
     ++			close(sublock_file_fd);
     ++		} else if (sublock_file_fd < 0) {
     ++			if (errno == EEXIST) {
     ++				err = 1;
     ++			} else {
     ++				err = REFTABLE_IO_ERROR;
     ++			}
     ++		}
     ++
     ++		subtable_locks[j] = (char *)slice_as_string(&subtab_lock);
     ++		delete_on_success[j] =
     ++			(char *)slice_as_string(&subtab_file_name);
     ++		j++;
     ++
     ++		if (err != 0)
     ++			goto done;
      +	}
      +
     -+	return 0;
     -+}
     ++	err = unlink(slice_as_string(&lock_file_name));
     ++	if (err < 0)
     ++		goto done;
     ++	have_lock = false;
      +
     -+/* -1 = error
     -+ 0 = up to date
     -+ 1 = changed. */
     -+static int stack_uptodate(struct reftable_stack *st)
     -+{
     -+	char **names = NULL;
     -+	int err = read_lines(st->list_file, &names);
     -+	int i = 0;
     ++	err = stack_compact_locked(st, first, last, &temp_tab_file_name,
     ++				   expiry);
     ++	/* Compaction + tombstones can create an empty table out of non-empty
     ++	 * tables. */
     ++	is_empty_table = (err == REFTABLE_EMPTY_TABLE_ERROR);
     ++	if (is_empty_table) {
     ++		err = 0;
     ++	}
      +	if (err < 0)
     -+		return err;
     ++		goto done;
      +
     -+	for (i = 0; i < st->merged->stack_len; i++) {
     -+		if (names[i] == NULL) {
     ++	lock_file_fd = open(slice_as_string(&lock_file_name),
     ++			    O_EXCL | O_CREAT | O_WRONLY, 0644);
     ++	if (lock_file_fd < 0) {
     ++		if (errno == EEXIST) {
      +			err = 1;
     -+			goto done;
     ++		} else {
     ++			err = REFTABLE_IO_ERROR;
      +		}
     ++		goto done;
     ++	}
     ++	have_lock = true;
      +
     -+		if (strcmp(st->merged->stack[i]->name, names[i])) {
     -+			err = 1;
     ++	format_name(&new_table_name, st->merged->stack[first]->min_update_index,
     ++		    st->merged->stack[last]->max_update_index);
     ++	slice_addstr(&new_table_name, ".ref");
     ++
     ++	slice_set_string(&new_table_path, st->reftable_dir);
     ++	slice_addstr(&new_table_path, "/");
     ++
     ++	slice_addbuf(&new_table_path, &new_table_name);
     ++
     ++	if (!is_empty_table) {
     ++		err = rename(slice_as_string(&temp_tab_file_name),
     ++			     slice_as_string(&new_table_path));
     ++		if (err < 0) {
     ++			err = REFTABLE_IO_ERROR;
      +			goto done;
      +		}
      +	}
      +
     -+	if (names[st->merged->stack_len] != NULL) {
     -+		err = 1;
     ++	for (i = 0; i < first; i++) {
     ++		slice_addstr(&ref_list_contents, st->merged->stack[i]->name);
     ++		slice_addstr(&ref_list_contents, "\n");
     ++	}
     ++	if (!is_empty_table) {
     ++		slice_addbuf(&ref_list_contents, &new_table_name);
     ++		slice_addstr(&ref_list_contents, "\n");
     ++	}
     ++	for (i = last + 1; i < st->merged->stack_len; i++) {
     ++		slice_addstr(&ref_list_contents, st->merged->stack[i]->name);
     ++		slice_addstr(&ref_list_contents, "\n");
     ++	}
     ++
     ++	err = write(lock_file_fd, ref_list_contents.buf, ref_list_contents.len);
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		unlink(slice_as_string(&new_table_path));
     ++		goto done;
     ++	}
     ++	err = close(lock_file_fd);
     ++	lock_file_fd = 0;
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		unlink(slice_as_string(&new_table_path));
     ++		goto done;
     ++	}
     ++
     ++	err = rename(slice_as_string(&lock_file_name), st->list_file);
     ++	if (err < 0) {
     ++		err = REFTABLE_IO_ERROR;
     ++		unlink(slice_as_string(&new_table_path));
      +		goto done;
      +	}
     ++	have_lock = false;
     ++
     ++	/* Reload the stack before deleting. On windows, we can only delete the
     ++	   files after we closed them.
     ++	*/
     ++	err = reftable_stack_reload_maybe_reuse(st, first < last);
     ++
     ++	listp = delete_on_success;
     ++	while (*listp) {
     ++		if (strcmp(*listp, slice_as_string(&new_table_path))) {
     ++			unlink(*listp);
     ++		}
     ++		listp++;
     ++	}
      +
      +done:
     -+	free_names(names);
     ++	free_names(delete_on_success);
     ++
     ++	listp = subtable_locks;
     ++	while (*listp) {
     ++		unlink(*listp);
     ++		listp++;
     ++	}
     ++	free_names(subtable_locks);
     ++	if (lock_file_fd > 0) {
     ++		close(lock_file_fd);
     ++		lock_file_fd = 0;
     ++	}
     ++	if (have_lock) {
     ++		unlink(slice_as_string(&lock_file_name));
     ++	}
     ++	slice_release(&new_table_name);
     ++	slice_release(&new_table_path);
     ++	slice_release(&ref_list_contents);
     ++	slice_release(&temp_tab_file_name);
     ++	slice_release(&lock_file_name);
      +	return err;
      +}
      +
     -+int reftable_stack_reload(struct reftable_stack *st)
     ++int reftable_stack_compact_all(struct reftable_stack *st,
     ++			       struct reftable_log_expiry_config *config)
      +{
     -+	int err = stack_uptodate(st);
     -+	if (err > 0)
     -+		return reftable_stack_reload_maybe_reuse(st, true);
     -+	return err;
     ++	return stack_compact_range(st, 0, st->merged->stack_len - 1, config);
      +}
      +
     -+int reftable_stack_add(struct reftable_stack *st,
     -+		       int (*write)(struct reftable_writer *wr, void *arg),
     -+		       void *arg)
     ++static int stack_compact_range_stats(struct reftable_stack *st, int first,
     ++				     int last,
     ++				     struct reftable_log_expiry_config *config)
      +{
     -+	int err = stack_try_add(st, write, arg);
     -+	if (err < 0) {
     -+		if (err == REFTABLE_LOCK_ERROR) {
     -+			/* Ignore error return, we want to propagate
     -+			   REFTABLE_LOCK_ERROR.
     -+			*/
     -+			reftable_stack_reload(st);
     -+		}
     -+		return err;
     ++	int err = stack_compact_range(st, first, last, config);
     ++	if (err > 0) {
     ++		st->stats.failures++;
      +	}
     -+
     -+	if (!st->disable_auto_compact)
     -+		return reftable_stack_auto_compact(st);
     -+
     -+	return 0;
     ++	return err;
      +}
      +
     -+static void format_name(struct slice *dest, uint64_t min, uint64_t max)
     ++static int segment_size(struct segment *s)
      +{
     -+	char buf[100];
     -+	snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64, min, max);
     -+	slice_set_string(dest, buf);
     ++	return s->end - s->start;
      +}
      +
     -+struct reftable_addition {
     -+	int lock_file_fd;
     -+	struct slice lock_file_name;
     -+	struct reftable_stack *stack;
     -+	char **names;
     -+	char **new_tables;
     -+	int new_tables_len;
     -+	uint64_t next_update_index;
     -+};
     -+
     -+#define REFTABLE_ADDITION_INIT               \
     -+	{                                    \
     -+		.lock_file_name = SLICE_INIT \
     ++int fastlog2(uint64_t sz)
     ++{
     ++	int l = 0;
     ++	if (sz == 0)
     ++		return 0;
     ++	for (; sz; sz /= 2) {
     ++		l++;
      +	}
     ++	return l - 1;
     ++}
      +
     -+static int reftable_stack_init_addition(struct reftable_addition *add,
     -+					struct reftable_stack *st)
     ++struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n)
      +{
     -+	int err = 0;
     -+	add->stack = st;
     ++	struct segment *segs = reftable_calloc(sizeof(struct segment) * n);
     ++	int next = 0;
     ++	struct segment cur = { 0 };
     ++	int i = 0;
      +
     -+	slice_set_string(&add->lock_file_name, st->list_file);
     -+	slice_addstr(&add->lock_file_name, ".lock");
     ++	if (n == 0) {
     ++		*seglen = 0;
     ++		return segs;
     ++	}
     ++	for (i = 0; i < n; i++) {
     ++		int log = fastlog2(sizes[i]);
     ++		if (cur.log != log && cur.bytes > 0) {
     ++			struct segment fresh = {
     ++				.start = i,
     ++			};
      +
     -+	add->lock_file_fd = open(slice_as_string(&add->lock_file_name),
     -+				 O_EXCL | O_CREAT | O_WRONLY, 0644);
     -+	if (add->lock_file_fd < 0) {
     -+		if (errno == EEXIST) {
     -+			err = REFTABLE_LOCK_ERROR;
     -+		} else {
     -+			err = REFTABLE_IO_ERROR;
     ++			segs[next++] = cur;
     ++			cur = fresh;
      +		}
     -+		goto done;
     ++
     ++		cur.log = log;
     ++		cur.end = i + 1;
     ++		cur.bytes += sizes[i];
      +	}
     -+	err = stack_uptodate(st);
     -+	if (err < 0)
     -+		goto done;
     ++	segs[next++] = cur;
     ++	*seglen = next;
     ++	return segs;
     ++}
      +
     -+	if (err > 1) {
     -+		err = REFTABLE_LOCK_ERROR;
     -+		goto done;
     ++struct segment suggest_compaction_segment(uint64_t *sizes, int n)
     ++{
     ++	int seglen = 0;
     ++	struct segment *segs = sizes_to_segments(&seglen, sizes, n);
     ++	struct segment min_seg = {
     ++		.log = 64,
     ++	};
     ++	int i = 0;
     ++	for (i = 0; i < seglen; i++) {
     ++		if (segment_size(&segs[i]) == 1) {
     ++			continue;
     ++		}
     ++
     ++		if (segs[i].log < min_seg.log) {
     ++			min_seg = segs[i];
     ++		}
      +	}
      +
     -+	add->next_update_index = reftable_stack_next_update_index(st);
     -+done:
     -+	if (err) {
     -+		reftable_addition_close(add);
     ++	while (min_seg.start > 0) {
     ++		int prev = min_seg.start - 1;
     ++		if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev])) {
     ++			break;
     ++		}
     ++
     ++		min_seg.start = prev;
     ++		min_seg.bytes += sizes[prev];
      +	}
     -+	return err;
     ++
     ++	reftable_free(segs);
     ++	return min_seg;
      +}
      +
     -+void reftable_addition_close(struct reftable_addition *add)
     ++static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)
      +{
     ++	uint64_t *sizes =
     ++		reftable_calloc(sizeof(uint64_t) * st->merged->stack_len);
     ++	int version = (st->config.hash_id == SHA1_ID) ? 1 : 2;
     ++	int overhead = header_size(version) - 1;
      +	int i = 0;
     -+	struct slice nm = SLICE_INIT;
     -+	for (i = 0; i < add->new_tables_len; i++) {
     -+		slice_set_string(&nm, add->stack->list_file);
     -+		slice_addstr(&nm, "/");
     -+		slice_addstr(&nm, add->new_tables[i]);
     -+		unlink(slice_as_string(&nm));
     -+		reftable_free(add->new_tables[i]);
     -+		add->new_tables[i] = NULL;
     ++	for (i = 0; i < st->merged->stack_len; i++) {
     ++		sizes[i] = st->merged->stack[i]->size - overhead;
      +	}
     -+	reftable_free(add->new_tables);
     -+	add->new_tables = NULL;
     -+	add->new_tables_len = 0;
     ++	return sizes;
     ++}
      +
     -+	if (add->lock_file_fd > 0) {
     -+		close(add->lock_file_fd);
     -+		add->lock_file_fd = 0;
     -+	}
     -+	if (add->lock_file_name.len > 0) {
     -+		unlink(slice_as_string(&add->lock_file_name));
     -+		slice_release(&add->lock_file_name);
     -+	}
     ++int reftable_stack_auto_compact(struct reftable_stack *st)
     ++{
     ++	uint64_t *sizes = stack_table_sizes_for_compaction(st);
     ++	struct segment seg =
     ++		suggest_compaction_segment(sizes, st->merged->stack_len);
     ++	reftable_free(sizes);
     ++	if (segment_size(&seg) > 0)
     ++		return stack_compact_range_stats(st, seg.start, seg.end - 1,
     ++						 NULL);
      +
     -+	free_names(add->names);
     -+	add->names = NULL;
     -+	slice_release(&nm);
     ++	return 0;
      +}
      +
     -+void reftable_addition_destroy(struct reftable_addition *add)
     ++struct reftable_compaction_stats *
     ++reftable_stack_compaction_stats(struct reftable_stack *st)
      +{
     -+	if (add == NULL) {
     -+		return;
     -+	}
     -+	reftable_addition_close(add);
     -+	reftable_free(add);
     ++	return &st->stats;
      +}
      +
     -+int reftable_addition_commit(struct reftable_addition *add)
     ++int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
     ++			    struct reftable_ref_record *ref)
      +{
     -+	struct slice table_list = SLICE_INIT;
     -+	int i = 0;
     -+	int err = 0;
     -+	if (add->new_tables_len == 0)
     -+		goto done;
     -+
     -+	for (i = 0; i < add->stack->merged->stack_len; i++) {
     -+		slice_addstr(&table_list, add->stack->merged->stack[i]->name);
     -+		slice_addstr(&table_list, "\n");
     -+	}
     -+	for (i = 0; i < add->new_tables_len; i++) {
     -+		slice_addstr(&table_list, add->new_tables[i]);
     -+		slice_addstr(&table_list, "\n");
     -+	}
     ++	struct reftable_table tab = { NULL };
     ++	reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
     ++	return reftable_table_read_ref(&tab, refname, ref);
     ++}
      +
     -+	err = write(add->lock_file_fd, table_list.buf, table_list.len);
     -+	slice_release(&table_list);
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     ++int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
     ++			    struct reftable_log_record *log)
     ++{
     ++	struct reftable_iterator it = { 0 };
     ++	struct reftable_merged_table *mt = reftable_stack_merged_table(st);
     ++	int err = reftable_merged_table_seek_log(mt, &it, refname);
     ++	if (err)
      +		goto done;
     -+	}
      +
     -+	err = close(add->lock_file_fd);
     -+	add->lock_file_fd = 0;
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     ++	err = reftable_iterator_next_log(&it, log);
     ++	if (err)
      +		goto done;
     -+	}
      +
     -+	err = rename(slice_as_string(&add->lock_file_name),
     -+		     add->stack->list_file);
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     ++	if (strcmp(log->ref_name, refname) ||
     ++	    reftable_log_record_is_deletion(log)) {
     ++		err = 1;
      +		goto done;
      +	}
      +
     -+	err = reftable_stack_reload(add->stack);
     -+
      +done:
     -+	reftable_addition_close(add);
     -+	return err;
     -+}
     -+
     -+int reftable_stack_new_addition(struct reftable_addition **dest,
     -+				struct reftable_stack *st)
     -+{
     -+	int err = 0;
     -+	struct reftable_addition empty = REFTABLE_ADDITION_INIT;
     -+	*dest = reftable_calloc(sizeof(**dest));
     -+	**dest = empty;
     -+	err = reftable_stack_init_addition(*dest, st);
      +	if (err) {
     -+		reftable_free(*dest);
     -+		*dest = NULL;
     ++		reftable_log_record_clear(log);
      +	}
     ++	reftable_iterator_destroy(&it);
      +	return err;
      +}
      +
     -+int stack_try_add(struct reftable_stack *st,
     -+		  int (*write_table)(struct reftable_writer *wr, void *arg),
     -+		  void *arg)
     ++int stack_check_addition(struct reftable_stack *st, const char *new_tab_name)
      +{
     -+	struct reftable_addition add = REFTABLE_ADDITION_INIT;
     -+	int err = reftable_stack_init_addition(&add, st);
     ++	int err = 0;
     ++	struct reftable_block_source src = { 0 };
     ++	struct reftable_reader *rd = NULL;
     ++	struct reftable_table tab = { NULL };
     ++	struct reftable_ref_record *refs = NULL;
     ++	struct reftable_iterator it = { NULL };
     ++	int cap = 0;
     ++	int len = 0;
     ++	int i = 0;
     ++
     ++	if (st->config.skip_name_check)
     ++		return 0;
     ++
     ++	err = reftable_block_source_from_file(&src, new_tab_name);
     ++	if (err < 0)
     ++		goto done;
     ++
     ++	err = reftable_new_reader(&rd, &src, new_tab_name);
      +	if (err < 0)
      +		goto done;
     ++
     ++	err = reftable_reader_seek_ref(rd, &it, "");
      +	if (err > 0) {
     -+		err = REFTABLE_LOCK_ERROR;
     ++		err = 0;
      +		goto done;
      +	}
     -+
     -+	err = reftable_addition_add(&add, write_table, arg);
      +	if (err < 0)
      +		goto done;
      +
     -+	err = reftable_addition_commit(&add);
     ++	while (true) {
     ++		struct reftable_ref_record ref = { 0 };
     ++		err = reftable_iterator_next_ref(&it, &ref);
     ++		if (err > 0) {
     ++			break;
     ++		}
     ++		if (err < 0)
     ++			goto done;
     ++
     ++		if (len >= cap) {
     ++			cap = 2 * cap + 1;
     ++			refs = reftable_realloc(refs, cap * sizeof(refs[0]));
     ++		}
     ++
     ++		refs[len++] = ref;
     ++	}
     ++
     ++	reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
     ++
     ++	err = validate_ref_record_addition(tab, refs, len);
     ++
      +done:
     -+	reftable_addition_close(&add);
     ++	for (i = 0; i < len; i++) {
     ++		reftable_ref_record_clear(&refs[i]);
     ++	}
     ++
     ++	free(refs);
     ++	reftable_iterator_destroy(&it);
     ++	reftable_reader_free(rd);
      +	return err;
      +}
     +
     + ## reftable/stack.h (new) ##
     +@@
     ++/*
     ++Copyright 2020 Google LLC
      +
     -+int reftable_addition_add(struct reftable_addition *add,
     -+			  int (*write_table)(struct reftable_writer *wr,
     -+					     void *arg),
     -+			  void *arg)
     -+{
     -+	struct slice temp_tab_file_name = SLICE_INIT;
     -+	struct slice tab_file_name = SLICE_INIT;
     -+	struct slice next_name = SLICE_INIT;
     -+	struct reftable_writer *wr = NULL;
     -+	int err = 0;
     -+	int tab_fd = 0;
     ++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
     ++*/
      +
     -+	slice_resize(&next_name, 0);
     -+	format_name(&next_name, add->next_update_index, add->next_update_index);
     ++#ifndef STACK_H
     ++#define STACK_H
      +
     -+	slice_set_string(&temp_tab_file_name, add->stack->reftable_dir);
     -+	slice_addstr(&temp_tab_file_name, "/");
     -+	slice_addbuf(&temp_tab_file_name, next_name);
     -+	slice_addstr(&temp_tab_file_name, ".temp.XXXXXX");
     ++#include "reftable.h"
     ++#include "system.h"
      +
     -+	tab_fd = mkstemp((char *)slice_as_string(&temp_tab_file_name));
     -+	if (tab_fd < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		goto done;
     -+	}
     ++struct reftable_stack {
     ++	char *list_file;
     ++	char *reftable_dir;
     ++	bool disable_auto_compact;
      +
     -+	wr = reftable_new_writer(reftable_fd_write, &tab_fd,
     -+				 &add->stack->config);
     -+	err = write_table(wr, arg);
     -+	if (err < 0)
     -+		goto done;
     ++	struct reftable_write_options config;
      +
     -+	err = reftable_writer_close(wr);
     -+	if (err == REFTABLE_EMPTY_TABLE_ERROR) {
     -+		err = 0;
     -+		goto done;
     -+	}
     -+	if (err < 0)
     -+		goto done;
     ++	struct reftable_merged_table *merged;
     ++	struct reftable_compaction_stats stats;
     ++};
      +
     -+	err = close(tab_fd);
     -+	tab_fd = 0;
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		goto done;
     -+	}
     ++int read_lines(const char *filename, char ***lines);
     ++int stack_try_add(struct reftable_stack *st,
     ++		  int (*write_table)(struct reftable_writer *wr, void *arg),
     ++		  void *arg);
     ++int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr,
     ++			int first, int last,
     ++			struct reftable_log_expiry_config *config);
     ++int fastlog2(uint64_t sz);
     ++int stack_check_addition(struct reftable_stack *st, const char *new_tab_name);
     ++void reftable_addition_close(struct reftable_addition *add);
     ++int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
     ++				      bool reuse_open);
      +
     -+	err = stack_check_addition(add->stack,
     -+				   slice_as_string(&temp_tab_file_name));
     -+	if (err < 0)
     -+		goto done;
     ++struct segment {
     ++	int start, end;
     ++	int log;
     ++	uint64_t bytes;
     ++};
      +
     -+	if (wr->min_update_index < add->next_update_index) {
     -+		err = REFTABLE_API_ERROR;
     -+		goto done;
     -+	}
     ++struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n);
     ++struct segment suggest_compaction_segment(uint64_t *sizes, int n);
      +
     -+	format_name(&next_name, wr->min_update_index, wr->max_update_index);
     -+	slice_addstr(&next_name, ".ref");
     ++#endif
     +
     + ## reftable/stack_test.c (new) ##
     +@@
     ++/*
     ++Copyright 2020 Google LLC
      +
     -+	slice_set_string(&tab_file_name, add->stack->reftable_dir);
     -+	slice_addstr(&tab_file_name, "/");
     -+	slice_addbuf(&tab_file_name, next_name);
     ++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
     ++*/
      +
     -+	/* TODO: should check destination out of paranoia */
     -+	err = rename(slice_as_string(&temp_tab_file_name),
     -+		     slice_as_string(&tab_file_name));
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		goto done;
     -+	}
     ++#include "stack.h"
      +
     -+	add->new_tables = reftable_realloc(add->new_tables,
     -+					   sizeof(*add->new_tables) *
     -+						   (add->new_tables_len + 1));
     -+	add->new_tables[add->new_tables_len] = slice_to_string(next_name);
     -+	add->new_tables_len++;
     -+done:
     -+	if (tab_fd > 0) {
     -+		close(tab_fd);
     -+		tab_fd = 0;
     -+	}
     -+	if (temp_tab_file_name.len > 0) {
     -+		unlink(slice_as_string(&temp_tab_file_name));
     -+	}
     ++#include "system.h"
      +
     -+	slice_release(&temp_tab_file_name);
     -+	slice_release(&tab_file_name);
     -+	slice_release(&next_name);
     -+	reftable_writer_free(wr);
     -+	return err;
     -+}
     ++#include "merged.h"
     ++#include "basics.h"
     ++#include "constants.h"
     ++#include "record.h"
     ++#include "reftable.h"
     ++#include "test_framework.h"
     ++#include "reftable-tests.h"
      +
     -+uint64_t reftable_stack_next_update_index(struct reftable_stack *st)
     -+{
     -+	int sz = st->merged->stack_len;
     -+	if (sz > 0)
     -+		return reftable_reader_max_update_index(
     -+			       st->merged->stack[sz - 1]) +
     -+		       1;
     -+	return 1;
     -+}
     ++#include <sys/types.h>
     ++#include <dirent.h>
      +
     -+static int stack_compact_locked(struct reftable_stack *st, int first, int last,
     -+				struct slice *temp_tab,
     -+				struct reftable_log_expiry_config *config)
     ++static void clear_dir(const char *dirname)
      +{
     -+	struct slice next_name = SLICE_INIT;
     -+	int tab_fd = -1;
     -+	struct reftable_writer *wr = NULL;
     -+	int err = 0;
     ++	int fd = open(dirname, O_DIRECTORY, 0);
     ++	DIR *dir = fdopendir(fd);
     ++	struct dirent *ent = NULL;
      +
     -+	format_name(&next_name,
     -+		    reftable_reader_min_update_index(st->merged->stack[first]),
     -+		    reftable_reader_max_update_index(st->merged->stack[first]));
     ++	assert(fd >= 0);
      +
     -+	slice_set_string(temp_tab, st->reftable_dir);
     -+	slice_addstr(temp_tab, "/");
     -+	slice_addbuf(temp_tab, next_name);
     -+	slice_addstr(temp_tab, ".temp.XXXXXX");
     ++	while ((ent = readdir(dir)) != NULL) {
     ++		unlinkat(fd, ent->d_name, 0);
     ++	}
     ++	closedir(dir);
     ++	rmdir(dirname);
     ++}
      +
     -+	tab_fd = mkstemp((char *)slice_as_string(temp_tab));
     -+	wr = reftable_new_writer(reftable_fd_write, &tab_fd, &st->config);
     ++static void test_read_file(void)
     ++{
     ++	char fn[256] = "/tmp/stack.test_read_file.XXXXXX";
     ++	int fd = mkstemp(fn);
     ++	char out[1024] = "line1\n\nline2\nline3";
     ++	int n, err;
     ++	char **names = NULL;
     ++	char *want[] = { "line1", "line2", "line3" };
     ++	int i = 0;
      +
     -+	err = stack_write_compact(st, wr, first, last, config);
     -+	if (err < 0)
     -+		goto done;
     -+	err = reftable_writer_close(wr);
     -+	if (err < 0)
     -+		goto done;
     ++	assert(fd > 0);
     ++	n = write(fd, out, strlen(out));
     ++	assert(n == strlen(out));
     ++	err = close(fd);
     ++	assert(err >= 0);
      +
     -+	err = close(tab_fd);
     -+	tab_fd = 0;
     ++	err = read_lines(fn, &names);
     ++	assert_err(err);
      +
     -+done:
     -+	reftable_writer_free(wr);
     -+	if (tab_fd > 0) {
     -+		close(tab_fd);
     -+		tab_fd = 0;
     ++	for (i = 0; names[i] != NULL; i++) {
     ++		assert(0 == strcmp(want[i], names[i]));
      +	}
     -+	if (err != 0 && temp_tab->len > 0) {
     -+		unlink(slice_as_string(temp_tab));
     -+		slice_release(temp_tab);
     -+	}
     -+	slice_release(&next_name);
     -+	return err;
     ++	free_names(names);
     ++	remove(fn);
      +}
      +
     -+int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr,
     -+			int first, int last,
     -+			struct reftable_log_expiry_config *config)
     ++static void test_parse_names(void)
      +{
     -+	int subtabs_len = last - first + 1;
     -+	struct reftable_reader **subtabs = reftable_calloc(
     -+		sizeof(struct reftable_reader *) * (last - first + 1));
     -+	struct reftable_merged_table *mt = NULL;
     -+	int err = 0;
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_ref_record ref = { 0 };
     -+	struct reftable_log_record log = { 0 };
     ++	char buf[] = "line\n";
     ++	char **names = NULL;
     ++	parse_names(buf, strlen(buf), &names);
      +
     -+	uint64_t entries = 0;
     ++	assert(NULL != names[0]);
     ++	assert(0 == strcmp(names[0], "line"));
     ++	assert(NULL == names[1]);
     ++	free_names(names);
     ++}
      +
     -+	int i = 0, j = 0;
     -+	for (i = first, j = 0; i <= last; i++) {
     -+		struct reftable_reader *t = st->merged->stack[i];
     -+		subtabs[j++] = t;
     -+		st->stats.bytes += t->size;
     -+	}
     -+	reftable_writer_set_limits(wr,
     -+				   st->merged->stack[first]->min_update_index,
     -+				   st->merged->stack[last]->max_update_index);
     ++static void test_names_equal(void)
     ++{
     ++	char *a[] = { "a", "b", "c", NULL };
     ++	char *b[] = { "a", "b", "d", NULL };
     ++	char *c[] = { "a", "b", NULL };
      +
     -+	err = reftable_new_merged_table(&mt, subtabs, subtabs_len,
     -+					st->config.hash_id);
     -+	if (err < 0) {
     -+		reftable_free(subtabs);
     -+		goto done;
     -+	}
     ++	assert(names_equal(a, a));
     ++	assert(!names_equal(a, b));
     ++	assert(!names_equal(a, c));
     ++}
      +
     -+	err = reftable_merged_table_seek_ref(mt, &it, "");
     -+	if (err < 0)
     -+		goto done;
     ++static int write_test_ref(struct reftable_writer *wr, void *arg)
     ++{
     ++	struct reftable_ref_record *ref = arg;
     ++	reftable_writer_set_limits(wr, ref->update_index, ref->update_index);
     ++	return reftable_writer_add_ref(wr, ref);
     ++}
      +
     -+	while (true) {
     -+		err = reftable_iterator_next_ref(&it, &ref);
     -+		if (err > 0) {
     -+			err = 0;
     -+			break;
     -+		}
     -+		if (err < 0) {
     -+			break;
     -+		}
     -+		if (first == 0 && reftable_ref_record_is_deletion(&ref)) {
     -+			continue;
     -+		}
     ++struct write_log_arg {
     ++	struct reftable_log_record *log;
     ++	uint64_t update_index;
     ++};
      +
     -+		err = reftable_writer_add_ref(wr, &ref);
     -+		if (err < 0) {
     -+			break;
     -+		}
     -+		entries++;
     -+	}
     -+	reftable_iterator_destroy(&it);
     ++static int write_test_log(struct reftable_writer *wr, void *arg)
     ++{
     ++	struct write_log_arg *wla = arg;
      +
     -+	err = reftable_merged_table_seek_log(mt, &it, "");
     -+	if (err < 0)
     -+		goto done;
     ++	reftable_writer_set_limits(wr, wla->update_index, wla->update_index);
     ++	return reftable_writer_add_log(wr, wla->log);
     ++}
      +
     -+	while (true) {
     -+		err = reftable_iterator_next_log(&it, &log);
     -+		if (err > 0) {
     -+			err = 0;
     -+			break;
     -+		}
     -+		if (err < 0) {
     -+			break;
     -+		}
     -+		if (first == 0 && reftable_log_record_is_deletion(&log)) {
     -+			continue;
     -+		}
     ++static void test_reftable_stack_add_one(void)
     ++{
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err;
     ++	struct reftable_ref_record ref = {
     ++		.ref_name = "HEAD",
     ++		.update_index = 1,
     ++		.target = "master",
     ++	};
     ++	struct reftable_ref_record dest = { 0 };
      +
     -+		if (config != NULL && config->time > 0 &&
     -+		    log.time < config->time) {
     -+			continue;
     -+		}
     ++	assert(mkdtemp(dir));
      +
     -+		if (config != NULL && config->min_update_index > 0 &&
     -+		    log.update_index < config->min_update_index) {
     -+			continue;
     -+		}
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
      +
     -+		err = reftable_writer_add_log(wr, &log);
     -+		if (err < 0) {
     -+			break;
     -+		}
     -+		entries++;
     -+	}
     ++	err = reftable_stack_add(st, &write_test_ref, &ref);
     ++	assert_err(err);
      +
     -+done:
     -+	reftable_iterator_destroy(&it);
     -+	if (mt != NULL) {
     -+		merged_table_clear(mt);
     -+		reftable_merged_table_free(mt);
     -+	}
     -+	reftable_ref_record_clear(&ref);
     -+	reftable_log_record_clear(&log);
     -+	st->stats.entries_written += entries;
     -+	return err;
     ++	err = reftable_stack_read_ref(st, ref.ref_name, &dest);
     ++	assert_err(err);
     ++	assert(0 == strcmp("master", dest.target));
     ++
     ++	reftable_ref_record_clear(&dest);
     ++	reftable_stack_destroy(st);
     ++	clear_dir(dir);
      +}
      +
     -+/* <  0: error. 0 == OK, > 0 attempt failed; could retry. */
     -+static int stack_compact_range(struct reftable_stack *st, int first, int last,
     -+			       struct reftable_log_expiry_config *expiry)
     ++static void test_reftable_stack_uptodate(void)
      +{
     -+	struct slice temp_tab_file_name = SLICE_INIT;
     -+	struct slice new_table_name = SLICE_INIT;
     -+	struct slice lock_file_name = SLICE_INIT;
     -+	struct slice ref_list_contents = SLICE_INIT;
     -+	struct slice new_table_path = SLICE_INIT;
     -+	int err = 0;
     -+	bool have_lock = false;
     -+	int lock_file_fd = 0;
     -+	int compact_count = last - first + 1;
     -+	char **listp = NULL;
     -+	char **delete_on_success =
     -+		reftable_calloc(sizeof(char *) * (compact_count + 1));
     -+	char **subtable_locks =
     -+		reftable_calloc(sizeof(char *) * (compact_count + 1));
     -+	int i = 0;
     -+	int j = 0;
     -+	bool is_empty_table = false;
     -+
     -+	if (first > last || (expiry == NULL && first == last)) {
     -+		err = 0;
     -+		goto done;
     -+	}
     -+
     -+	st->stats.attempts++;
     -+
     -+	slice_set_string(&lock_file_name, st->list_file);
     -+	slice_addstr(&lock_file_name, ".lock");
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st1 = NULL;
     ++	struct reftable_stack *st2 = NULL;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	int err;
     ++	struct reftable_ref_record ref1 = {
     ++		.ref_name = "HEAD",
     ++		.update_index = 1,
     ++		.target = "master",
     ++	};
     ++	struct reftable_ref_record ref2 = {
     ++		.ref_name = "branch2",
     ++		.update_index = 2,
     ++		.target = "master",
     ++	};
      +
     -+	lock_file_fd = open(slice_as_string(&lock_file_name),
     -+			    O_EXCL | O_CREAT | O_WRONLY, 0644);
     -+	if (lock_file_fd < 0) {
     -+		if (errno == EEXIST) {
     -+			err = 1;
     -+		} else {
     -+			err = REFTABLE_IO_ERROR;
     -+		}
     -+		goto done;
     -+	}
     -+	/* Don't want to write to the lock for now.  */
     -+	close(lock_file_fd);
     -+	lock_file_fd = 0;
     ++	assert(mkdtemp(dir));
      +
     -+	have_lock = true;
     -+	err = stack_uptodate(st);
     -+	if (err != 0)
     -+		goto done;
     ++	err = reftable_new_stack(&st1, dir, cfg);
     ++	assert_err(err);
      +
     -+	for (i = first, j = 0; i <= last; i++) {
     -+		struct slice subtab_file_name = SLICE_INIT;
     -+		struct slice subtab_lock = SLICE_INIT;
     -+		int sublock_file_fd = -1;
     ++	err = reftable_new_stack(&st2, dir, cfg);
     ++	assert_err(err);
      +
     -+		slice_set_string(&subtab_file_name, st->reftable_dir);
     -+		slice_addstr(&subtab_file_name, "/");
     -+		slice_addstr(&subtab_file_name,
     -+			     reader_name(st->merged->stack[i]));
     ++	err = reftable_stack_add(st1, &write_test_ref, &ref1);
     ++	assert_err(err);
      +
     -+		slice_copy(&subtab_lock, subtab_file_name);
     -+		slice_addstr(&subtab_lock, ".lock");
     ++	err = reftable_stack_add(st2, &write_test_ref, &ref2);
     ++	assert(err == REFTABLE_LOCK_ERROR);
      +
     -+		sublock_file_fd = open(slice_as_string(&subtab_lock),
     -+				       O_EXCL | O_CREAT | O_WRONLY, 0644);
     -+		if (sublock_file_fd > 0) {
     -+			close(sublock_file_fd);
     -+		} else if (sublock_file_fd < 0) {
     -+			if (errno == EEXIST) {
     -+				err = 1;
     -+			} else {
     -+				err = REFTABLE_IO_ERROR;
     -+			}
     -+		}
     ++	err = reftable_stack_reload(st2);
     ++	assert_err(err);
      +
     -+		subtable_locks[j] = (char *)slice_as_string(&subtab_lock);
     -+		delete_on_success[j] =
     -+			(char *)slice_as_string(&subtab_file_name);
     -+		j++;
     ++	err = reftable_stack_add(st2, &write_test_ref, &ref2);
     ++	assert_err(err);
     ++	reftable_stack_destroy(st1);
     ++	reftable_stack_destroy(st2);
     ++	clear_dir(dir);
     ++}
      +
     -+		if (err != 0)
     -+			goto done;
     -+	}
     ++static void test_reftable_stack_transaction_api(void)
     ++{
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err;
     ++	struct reftable_addition *add = NULL;
      +
     -+	err = unlink(slice_as_string(&lock_file_name));
     -+	if (err < 0)
     -+		goto done;
     -+	have_lock = false;
     ++	struct reftable_ref_record ref = {
     ++		.ref_name = "HEAD",
     ++		.update_index = 1,
     ++		.target = "master",
     ++	};
     ++	struct reftable_ref_record dest = { 0 };
      +
     -+	err = stack_compact_locked(st, first, last, &temp_tab_file_name,
     -+				   expiry);
     -+	/* Compaction + tombstones can create an empty table out of non-empty
     -+	 * tables. */
     -+	is_empty_table = (err == REFTABLE_EMPTY_TABLE_ERROR);
     -+	if (is_empty_table) {
     -+		err = 0;
     -+	}
     -+	if (err < 0)
     -+		goto done;
     ++	assert(mkdtemp(dir));
      +
     -+	lock_file_fd = open(slice_as_string(&lock_file_name),
     -+			    O_EXCL | O_CREAT | O_WRONLY, 0644);
     -+	if (lock_file_fd < 0) {
     -+		if (errno == EEXIST) {
     -+			err = 1;
     -+		} else {
     -+			err = REFTABLE_IO_ERROR;
     -+		}
     -+		goto done;
     -+	}
     -+	have_lock = true;
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
      +
     -+	format_name(&new_table_name, st->merged->stack[first]->min_update_index,
     -+		    st->merged->stack[last]->max_update_index);
     -+	slice_addstr(&new_table_name, ".ref");
     ++	reftable_addition_destroy(add);
      +
     -+	slice_set_string(&new_table_path, st->reftable_dir);
     -+	slice_addstr(&new_table_path, "/");
     ++	err = reftable_stack_new_addition(&add, st);
     ++	assert_err(err);
      +
     -+	slice_addbuf(&new_table_path, new_table_name);
     ++	err = reftable_addition_add(add, &write_test_ref, &ref);
     ++	assert_err(err);
      +
     -+	if (!is_empty_table) {
     -+		err = rename(slice_as_string(&temp_tab_file_name),
     -+			     slice_as_string(&new_table_path));
     -+		if (err < 0) {
     -+			err = REFTABLE_IO_ERROR;
     -+			goto done;
     -+		}
     -+	}
     ++	err = reftable_addition_commit(add);
     ++	assert_err(err);
      +
     -+	for (i = 0; i < first; i++) {
     -+		slice_addstr(&ref_list_contents, st->merged->stack[i]->name);
     -+		slice_addstr(&ref_list_contents, "\n");
     -+	}
     -+	if (!is_empty_table) {
     -+		slice_addbuf(&ref_list_contents, new_table_name);
     -+		slice_addstr(&ref_list_contents, "\n");
     -+	}
     -+	for (i = last + 1; i < st->merged->stack_len; i++) {
     -+		slice_addstr(&ref_list_contents, st->merged->stack[i]->name);
     -+		slice_addstr(&ref_list_contents, "\n");
     -+	}
     ++	reftable_addition_destroy(add);
      +
     -+	err = write(lock_file_fd, ref_list_contents.buf, ref_list_contents.len);
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		unlink(slice_as_string(&new_table_path));
     -+		goto done;
     -+	}
     -+	err = close(lock_file_fd);
     -+	lock_file_fd = 0;
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		unlink(slice_as_string(&new_table_path));
     -+		goto done;
     -+	}
     ++	err = reftable_stack_read_ref(st, ref.ref_name, &dest);
     ++	assert_err(err);
     ++	assert(0 == strcmp("master", dest.target));
      +
     -+	err = rename(slice_as_string(&lock_file_name), st->list_file);
     -+	if (err < 0) {
     -+		err = REFTABLE_IO_ERROR;
     -+		unlink(slice_as_string(&new_table_path));
     -+		goto done;
     -+	}
     -+	have_lock = false;
     ++	reftable_ref_record_clear(&dest);
     ++	reftable_stack_destroy(st);
     ++	clear_dir(dir);
     ++}
      +
     -+	/* Reload the stack before deleting. On windows, we can only delete the
     -+	   files after we closed them.
     -+	*/
     -+	err = reftable_stack_reload_maybe_reuse(st, first < last);
     ++static void test_reftable_stack_validate_refname(void)
     ++{
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	int i;
     ++	struct reftable_ref_record ref = {
     ++		.ref_name = "a/b",
     ++		.update_index = 1,
     ++		.target = "master",
     ++	};
     ++	char *additions[] = { "a", "a/b/c" };
      +
     -+	listp = delete_on_success;
     -+	while (*listp) {
     -+		if (strcmp(*listp, slice_as_string(&new_table_path))) {
     -+			unlink(*listp);
     -+		}
     -+		listp++;
     -+	}
     ++	assert(mkdtemp(dir));
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
      +
     -+done:
     -+	free_names(delete_on_success);
     ++	err = reftable_stack_add(st, &write_test_ref, &ref);
     ++	assert_err(err);
      +
     -+	listp = subtable_locks;
     -+	while (*listp) {
     -+		unlink(*listp);
     -+		listp++;
     -+	}
     -+	free_names(subtable_locks);
     -+	if (lock_file_fd > 0) {
     -+		close(lock_file_fd);
     -+		lock_file_fd = 0;
     -+	}
     -+	if (have_lock) {
     -+		unlink(slice_as_string(&lock_file_name));
     ++	for (i = 0; i < ARRAY_SIZE(additions); i++) {
     ++		struct reftable_ref_record ref = {
     ++			.ref_name = additions[i],
     ++			.update_index = 1,
     ++			.target = "master",
     ++		};
     ++
     ++		err = reftable_stack_add(st, &write_test_ref, &ref);
     ++		assert(err == REFTABLE_NAME_CONFLICT);
      +	}
     -+	slice_release(&new_table_name);
     -+	slice_release(&new_table_path);
     -+	slice_release(&ref_list_contents);
     -+	slice_release(&temp_tab_file_name);
     -+	slice_release(&lock_file_name);
     -+	return err;
     -+}
      +
     -+int reftable_stack_compact_all(struct reftable_stack *st,
     -+			       struct reftable_log_expiry_config *config)
     -+{
     -+	return stack_compact_range(st, 0, st->merged->stack_len - 1, config);
     ++	reftable_stack_destroy(st);
     ++	clear_dir(dir);
      +}
      +
     -+static int stack_compact_range_stats(struct reftable_stack *st, int first,
     -+				     int last,
     -+				     struct reftable_log_expiry_config *config)
     ++static int write_error(struct reftable_writer *wr, void *arg)
      +{
     -+	int err = stack_compact_range(st, first, last, config);
     -+	if (err > 0) {
     -+		st->stats.failures++;
     -+	}
     -+	return err;
     ++	return *((int *)arg);
      +}
      +
     -+static int segment_size(struct segment *s)
     ++static void test_reftable_stack_update_index_check(void)
      +{
     -+	return s->end - s->start;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err;
     ++	struct reftable_ref_record ref1 = {
     ++		.ref_name = "name1",
     ++		.update_index = 1,
     ++		.target = "master",
     ++	};
     ++	struct reftable_ref_record ref2 = {
     ++		.ref_name = "name2",
     ++		.update_index = 1,
     ++		.target = "master",
     ++	};
     ++	assert(mkdtemp(dir));
     ++
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
     ++
     ++	err = reftable_stack_add(st, &write_test_ref, &ref1);
     ++	assert_err(err);
     ++
     ++	err = reftable_stack_add(st, &write_test_ref, &ref2);
     ++	assert(err == REFTABLE_API_ERROR);
     ++	reftable_stack_destroy(st);
     ++	clear_dir(dir);
      +}
      +
     -+int fastlog2(uint64_t sz)
     ++static void test_reftable_stack_lock_failure(void)
      +{
     -+	int l = 0;
     -+	if (sz == 0)
     -+		return 0;
     -+	for (; sz; sz /= 2) {
     -+		l++;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err, i;
     ++	assert(mkdtemp(dir));
     ++
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
     ++	for (i = -1; i != REFTABLE_EMPTY_TABLE_ERROR; i--) {
     ++		err = reftable_stack_add(st, &write_error, &i);
     ++		assert(err == i);
      +	}
     -+	return l - 1;
     ++
     ++	reftable_stack_destroy(st);
     ++	clear_dir(dir);
      +}
      +
     -+struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n)
     ++static void test_reftable_stack_add(void)
      +{
     -+	struct segment *segs = reftable_calloc(sizeof(struct segment) * n);
     -+	int next = 0;
     -+	struct segment cur = { 0 };
      +	int i = 0;
     ++	int err = 0;
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_ref_record refs[2] = { 0 };
     ++	struct reftable_log_record logs[2] = { 0 };
     ++	int N = ARRAY_SIZE(refs);
     ++
     ++	assert(mkdtemp(dir));
     ++
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
     ++	st->disable_auto_compact = true;
     ++
     ++	for (i = 0; i < N; i++) {
     ++		char buf[256];
     ++		snprintf(buf, sizeof(buf), "branch%02d", i);
     ++		refs[i].ref_name = xstrdup(buf);
     ++		refs[i].value = reftable_malloc(SHA1_SIZE);
     ++		refs[i].update_index = i + 1;
     ++		set_test_hash(refs[i].value, i);
     ++
     ++		logs[i].ref_name = xstrdup(buf);
     ++		logs[i].update_index = N + i + 1;
     ++		logs[i].new_hash = reftable_malloc(SHA1_SIZE);
     ++		logs[i].email = xstrdup("identity@invalid");
     ++		set_test_hash(logs[i].new_hash, i);
     ++	}
     ++
     ++	for (i = 0; i < N; i++) {
     ++		int err = reftable_stack_add(st, &write_test_ref, &refs[i]);
     ++		assert_err(err);
     ++	}
     ++
     ++	for (i = 0; i < N; i++) {
     ++		struct write_log_arg arg = {
     ++			.log = &logs[i],
     ++			.update_index = reftable_stack_next_update_index(st),
     ++		};
     ++		int err = reftable_stack_add(st, &write_test_log, &arg);
     ++		assert_err(err);
     ++	}
      +
     -+	if (n == 0) {
     -+		*seglen = 0;
     -+		return segs;
     ++	err = reftable_stack_compact_all(st, NULL);
     ++	assert_err(err);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		struct reftable_ref_record dest = { 0 };
     ++		int err = reftable_stack_read_ref(st, refs[i].ref_name, &dest);
     ++		assert_err(err);
     ++		assert(reftable_ref_record_equal(&dest, refs + i, SHA1_SIZE));
     ++		reftable_ref_record_clear(&dest);
      +	}
     -+	for (i = 0; i < n; i++) {
     -+		int log = fastlog2(sizes[i]);
     -+		if (cur.log != log && cur.bytes > 0) {
     -+			struct segment fresh = {
     -+				.start = i,
     -+			};
      +
     -+			segs[next++] = cur;
     -+			cur = fresh;
     -+		}
     ++	for (i = 0; i < N; i++) {
     ++		struct reftable_log_record dest = { 0 };
     ++		int err = reftable_stack_read_log(st, refs[i].ref_name, &dest);
     ++		assert_err(err);
     ++		assert(reftable_log_record_equal(&dest, logs + i, SHA1_SIZE));
     ++		reftable_log_record_clear(&dest);
     ++	}
      +
     -+		cur.log = log;
     -+		cur.end = i + 1;
     -+		cur.bytes += sizes[i];
     ++	/* cleanup */
     ++	reftable_stack_destroy(st);
     ++	for (i = 0; i < N; i++) {
     ++		reftable_ref_record_clear(&refs[i]);
     ++		reftable_log_record_clear(&logs[i]);
      +	}
     -+	segs[next++] = cur;
     -+	*seglen = next;
     -+	return segs;
     ++	clear_dir(dir);
      +}
      +
     -+struct segment suggest_compaction_segment(uint64_t *sizes, int n)
     ++static void test_reftable_stack_tombstone(void)
      +{
     -+	int seglen = 0;
     -+	struct segment *segs = sizes_to_segments(&seglen, sizes, n);
     -+	struct segment min_seg = {
     -+		.log = 64,
     -+	};
      +	int i = 0;
     -+	for (i = 0; i < seglen; i++) {
     -+		if (segment_size(&segs[i]) == 1) {
     -+			continue;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err;
     ++	struct reftable_ref_record refs[2] = { 0 };
     ++	struct reftable_log_record logs[2] = { 0 };
     ++	int N = ARRAY_SIZE(refs);
     ++	struct reftable_ref_record dest = { 0 };
     ++	struct reftable_log_record log_dest = { 0 };
     ++
     ++	assert(mkdtemp(dir));
     ++
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		const char *buf = "branch";
     ++		refs[i].ref_name = xstrdup(buf);
     ++		refs[i].update_index = i + 1;
     ++		if (i % 2 == 0) {
     ++			refs[i].value = reftable_malloc(SHA1_SIZE);
     ++			set_test_hash(refs[i].value, i);
      +		}
     -+
     -+		if (segs[i].log < min_seg.log) {
     -+			min_seg = segs[i];
     ++		logs[i].ref_name = xstrdup(buf);
     ++		/* update_index is part of the key. */
     ++		logs[i].update_index = 42;
     ++		if (i % 2 == 0) {
     ++			logs[i].new_hash = reftable_malloc(SHA1_SIZE);
     ++			set_test_hash(logs[i].new_hash, i);
     ++			logs[i].email = xstrdup("identity@invalid");
      +		}
      +	}
     ++	for (i = 0; i < N; i++) {
     ++		int err = reftable_stack_add(st, &write_test_ref, &refs[i]);
     ++		assert_err(err);
     ++	}
     ++	for (i = 0; i < N; i++) {
     ++		struct write_log_arg arg = {
     ++			.log = &logs[i],
     ++			.update_index = reftable_stack_next_update_index(st),
     ++		};
     ++		int err = reftable_stack_add(st, &write_test_log, &arg);
     ++		assert_err(err);
     ++	}
      +
     -+	while (min_seg.start > 0) {
     -+		int prev = min_seg.start - 1;
     -+		if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev])) {
     -+			break;
     -+		}
     ++	err = reftable_stack_read_ref(st, "branch", &dest);
     ++	assert(err == 1);
     ++	reftable_ref_record_clear(&dest);
      +
     -+		min_seg.start = prev;
     -+		min_seg.bytes += sizes[prev];
     -+	}
     ++	err = reftable_stack_read_log(st, "branch", &log_dest);
     ++	assert(err == 1);
     ++	reftable_log_record_clear(&log_dest);
      +
     -+	reftable_free(segs);
     -+	return min_seg;
     -+}
     ++	err = reftable_stack_compact_all(st, NULL);
     ++	assert_err(err);
      +
     -+static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)
     -+{
     -+	uint64_t *sizes =
     -+		reftable_calloc(sizeof(uint64_t) * st->merged->stack_len);
     -+	int version = (st->config.hash_id == SHA1_ID) ? 1 : 2;
     -+	int overhead = header_size(version) - 1;
     -+	int i = 0;
     -+	for (i = 0; i < st->merged->stack_len; i++) {
     -+		sizes[i] = st->merged->stack[i]->size - overhead;
     ++	err = reftable_stack_read_ref(st, "branch", &dest);
     ++	assert(err == 1);
     ++
     ++	err = reftable_stack_read_log(st, "branch", &log_dest);
     ++	assert(err == 1);
     ++	reftable_ref_record_clear(&dest);
     ++	reftable_log_record_clear(&log_dest);
     ++
     ++	/* cleanup */
     ++	reftable_stack_destroy(st);
     ++	for (i = 0; i < N; i++) {
     ++		reftable_ref_record_clear(&refs[i]);
     ++		reftable_log_record_clear(&logs[i]);
      +	}
     -+	return sizes;
     ++	clear_dir(dir);
      +}
      +
     -+int reftable_stack_auto_compact(struct reftable_stack *st)
     ++static void test_reftable_stack_hash_id(void)
      +{
     -+	uint64_t *sizes = stack_table_sizes_for_compaction(st);
     -+	struct segment seg =
     -+		suggest_compaction_segment(sizes, st->merged->stack_len);
     -+	reftable_free(sizes);
     -+	if (segment_size(&seg) > 0)
     -+		return stack_compact_range_stats(st, seg.start, seg.end - 1,
     -+						 NULL);
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err;
     ++
     ++	struct reftable_ref_record ref = {
     ++		.ref_name = "master",
     ++		.target = "target",
     ++		.update_index = 1,
     ++	};
     ++	struct reftable_write_options cfg32 = { .hash_id = SHA256_ID };
     ++	struct reftable_stack *st32 = NULL;
     ++	struct reftable_write_options cfg_default = { 0 };
     ++	struct reftable_stack *st_default = NULL;
     ++	struct reftable_ref_record dest = { 0 };
     ++
     ++	assert(mkdtemp(dir));
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
     ++
     ++	err = reftable_stack_add(st, &write_test_ref, &ref);
     ++	assert_err(err);
     ++
     ++	/* can't read it with the wrong hash ID. */
     ++	err = reftable_new_stack(&st32, dir, cfg32);
     ++	assert(err == REFTABLE_FORMAT_ERROR);
     ++
     ++	/* check that we can read it back with default config too. */
     ++	err = reftable_new_stack(&st_default, dir, cfg_default);
     ++	assert_err(err);
     ++
     ++	err = reftable_stack_read_ref(st_default, "master", &dest);
     ++	assert_err(err);
     ++
     ++	assert(!strcmp(dest.target, ref.target));
     ++	reftable_ref_record_clear(&dest);
     ++	reftable_stack_destroy(st);
     ++	reftable_stack_destroy(st_default);
     ++	clear_dir(dir);
     ++}
      +
     -+	return 0;
     ++static void test_log2(void)
     ++{
     ++	assert(1 == fastlog2(3));
     ++	assert(2 == fastlog2(4));
     ++	assert(2 == fastlog2(5));
      +}
      +
     -+struct reftable_compaction_stats *
     -+reftable_stack_compaction_stats(struct reftable_stack *st)
     ++static void test_sizes_to_segments(void)
      +{
     -+	return &st->stats;
     ++	uint64_t sizes[] = { 2, 3, 4, 5, 7, 9 };
     ++	/* .................0  1  2  3  4  5 */
     ++
     ++	int seglen = 0;
     ++	struct segment *segs =
     ++		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
     ++	assert(segs[2].log == 3);
     ++	assert(segs[2].start == 5);
     ++	assert(segs[2].end == 6);
     ++
     ++	assert(segs[1].log == 2);
     ++	assert(segs[1].start == 2);
     ++	assert(segs[1].end == 5);
     ++	reftable_free(segs);
      +}
      +
     -+int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
     -+			    struct reftable_ref_record *ref)
     ++static void test_sizes_to_segments_empty(void)
      +{
     -+	struct reftable_table tab = { NULL };
     -+	reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
     -+	return reftable_table_read_ref(&tab, refname, ref);
     ++	uint64_t sizes[0];
     ++
     ++	int seglen = 0;
     ++	struct segment *segs =
     ++		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
     ++	assert(seglen == 0);
     ++	reftable_free(segs);
      +}
      +
     -+int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
     -+			    struct reftable_log_record *log)
     ++static void test_sizes_to_segments_all_equal(void)
      +{
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_merged_table *mt = reftable_stack_merged_table(st);
     -+	int err = reftable_merged_table_seek_log(mt, &it, refname);
     -+	if (err)
     -+		goto done;
     ++	uint64_t sizes[] = { 5, 5 };
      +
     -+	err = reftable_iterator_next_log(&it, log);
     -+	if (err)
     -+		goto done;
     ++	int seglen = 0;
     ++	struct segment *segs =
     ++		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
     ++	assert(seglen == 1);
     ++	assert(segs[0].start == 0);
     ++	assert(segs[0].end == 2);
     ++	reftable_free(segs);
     ++}
      +
     -+	if (strcmp(log->ref_name, refname) ||
     -+	    reftable_log_record_is_deletion(log)) {
     -+		err = 1;
     -+		goto done;
     -+	}
     ++static void test_suggest_compaction_segment(void)
     ++{
     ++	uint64_t sizes[] = { 128, 64, 17, 16, 9, 9, 9, 16, 16 };
     ++	/* .................0    1    2  3   4  5  6 */
     ++	struct segment min =
     ++		suggest_compaction_segment(sizes, ARRAY_SIZE(sizes));
     ++	assert(min.start == 2);
     ++	assert(min.end == 7);
     ++}
      +
     -+done:
     -+	if (err) {
     -+		reftable_log_record_clear(log);
     -+	}
     -+	reftable_iterator_destroy(&it);
     -+	return err;
     ++static void test_suggest_compaction_segment_nothing(void)
     ++{
     ++	uint64_t sizes[] = { 64, 32, 16, 8, 4, 2 };
     ++	struct segment result =
     ++		suggest_compaction_segment(sizes, ARRAY_SIZE(sizes));
     ++	assert(result.start == result.end);
      +}
      +
     -+int stack_check_addition(struct reftable_stack *st, const char *new_tab_name)
     ++static void test_reflog_expire(void)
      +{
     -+	int err = 0;
     -+	struct reftable_block_source src = { 0 };
     -+	struct reftable_reader *rd = NULL;
     -+	struct reftable_table tab = { NULL };
     -+	struct reftable_ref_record *refs = NULL;
     -+	struct reftable_iterator it = { NULL };
     -+	int cap = 0;
     -+	int len = 0;
     ++	char dir[256] = "/tmp/stack.test_reflog_expire.XXXXXX";
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	struct reftable_log_record logs[20] = { 0 };
     ++	int N = ARRAY_SIZE(logs) - 1;
      +	int i = 0;
     ++	int err;
     ++	struct reftable_log_expiry_config expiry = {
     ++		.time = 10,
     ++	};
     ++	struct reftable_log_record log = { 0 };
      +
     -+	if (st->config.skip_name_check)
     -+		return 0;
     ++	assert(mkdtemp(dir));
      +
     -+	err = reftable_block_source_from_file(&src, new_tab_name);
     -+	if (err < 0)
     -+		goto done;
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
      +
     -+	err = reftable_new_reader(&rd, &src, new_tab_name);
     -+	if (err < 0)
     -+		goto done;
     ++	for (i = 1; i <= N; i++) {
     ++		char buf[256];
     ++		snprintf(buf, sizeof(buf), "branch%02d", i);
      +
     -+	err = reftable_reader_seek_ref(rd, &it, "");
     -+	if (err > 0) {
     -+		err = 0;
     -+		goto done;
     ++		logs[i].ref_name = xstrdup(buf);
     ++		logs[i].update_index = i;
     ++		logs[i].time = i;
     ++		logs[i].new_hash = reftable_malloc(SHA1_SIZE);
     ++		logs[i].email = xstrdup("identity@invalid");
     ++		set_test_hash(logs[i].new_hash, i);
      +	}
     -+	if (err < 0)
     -+		goto done;
      +
     -+	while (true) {
     -+		struct reftable_ref_record ref = { 0 };
     -+		err = reftable_iterator_next_ref(&it, &ref);
     -+		if (err > 0) {
     -+			break;
     -+		}
     -+		if (err < 0)
     -+			goto done;
     ++	for (i = 1; i <= N; i++) {
     ++		struct write_log_arg arg = {
     ++			.log = &logs[i],
     ++			.update_index = reftable_stack_next_update_index(st),
     ++		};
     ++		int err = reftable_stack_add(st, &write_test_log, &arg);
     ++		assert_err(err);
     ++	}
      +
     -+		if (len >= cap) {
     -+			cap = 2 * cap + 1;
     -+			refs = reftable_realloc(refs, cap * sizeof(refs[0]));
     -+		}
     ++	err = reftable_stack_compact_all(st, NULL);
     ++	assert_err(err);
      +
     -+		refs[len++] = ref;
     -+	}
     ++	err = reftable_stack_compact_all(st, &expiry);
     ++	assert_err(err);
      +
     -+	reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
     ++	err = reftable_stack_read_log(st, logs[9].ref_name, &log);
     ++	assert(err == 1);
      +
     -+	err = validate_ref_record_addition(tab, refs, len);
     ++	err = reftable_stack_read_log(st, logs[11].ref_name, &log);
     ++	assert_err(err);
      +
     -+done:
     -+	for (i = 0; i < len; i++) {
     -+		reftable_ref_record_clear(&refs[i]);
     -+	}
     ++	expiry.min_update_index = 15;
     ++	err = reftable_stack_compact_all(st, &expiry);
     ++	assert_err(err);
      +
     -+	free(refs);
     -+	reftable_iterator_destroy(&it);
     -+	reftable_reader_free(rd);
     -+	return err;
     -+}
     -
     - ## reftable/stack.h (new) ##
     -@@
     -+/*
     -+Copyright 2020 Google LLC
     ++	err = reftable_stack_read_log(st, logs[14].ref_name, &log);
     ++	assert(err == 1);
      +
     -+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
     -+*/
     ++	err = reftable_stack_read_log(st, logs[16].ref_name, &log);
     ++	assert_err(err);
      +
     -+#ifndef STACK_H
     -+#define STACK_H
     ++	/* cleanup */
     ++	reftable_stack_destroy(st);
     ++	for (i = 0; i <= N; i++) {
     ++		reftable_log_record_clear(&logs[i]);
     ++	}
     ++	clear_dir(dir);
     ++	reftable_log_record_clear(&log);
     ++}
      +
     -+#include "reftable.h"
     -+#include "system.h"
     ++static int write_nothing(struct reftable_writer *wr, void *arg)
     ++{
     ++	reftable_writer_set_limits(wr, 1, 1);
     ++	return 0;
     ++}
      +
     -+struct reftable_stack {
     -+	char *list_file;
     -+	char *reftable_dir;
     -+	bool disable_auto_compact;
     ++static void test_empty_add(void)
     ++{
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	int err;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	struct reftable_stack *st2 = NULL;
      +
     -+	struct reftable_write_options config;
     ++	assert(mkdtemp(dir));
      +
     -+	struct reftable_merged_table *merged;
     -+	struct reftable_compaction_stats stats;
     -+};
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
      +
     -+int read_lines(const char *filename, char ***lines);
     -+int stack_try_add(struct reftable_stack *st,
     -+		  int (*write_table)(struct reftable_writer *wr, void *arg),
     -+		  void *arg);
     -+int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr,
     -+			int first, int last,
     -+			struct reftable_log_expiry_config *config);
     -+int fastlog2(uint64_t sz);
     -+int stack_check_addition(struct reftable_stack *st, const char *new_tab_name);
     -+void reftable_addition_close(struct reftable_addition *add);
     -+int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
     -+				      bool reuse_open);
     ++	err = reftable_stack_add(st, &write_nothing, NULL);
     ++	assert_err(err);
      +
     -+struct segment {
     -+	int start, end;
     -+	int log;
     -+	uint64_t bytes;
     -+};
     ++	err = reftable_new_stack(&st2, dir, cfg);
     ++	assert_err(err);
     ++	clear_dir(dir);
     ++	reftable_stack_destroy(st);
     ++	reftable_stack_destroy(st2);
     ++}
      +
     -+struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n);
     -+struct segment suggest_compaction_segment(uint64_t *sizes, int n);
     ++static void test_reftable_stack_auto_compaction(void)
     ++{
     ++	struct reftable_write_options cfg = { 0 };
     ++	struct reftable_stack *st = NULL;
     ++	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	int err, i;
     ++	int N = 100;
     ++	assert(mkdtemp(dir));
      +
     -+#endif
     ++	err = reftable_new_stack(&st, dir, cfg);
     ++	assert_err(err);
     ++
     ++	for (i = 0; i < N; i++) {
     ++		char name[100];
     ++		struct reftable_ref_record ref = {
     ++			.ref_name = name,
     ++			.update_index = reftable_stack_next_update_index(st),
     ++			.target = "master",
     ++		};
     ++		snprintf(name, sizeof(name), "branch%04d", i);
     ++
     ++		err = reftable_stack_add(st, &write_test_ref, &ref);
     ++		assert_err(err);
     ++
     ++		assert(i < 3 || st->merged->stack_len < 2 * fastlog2(i));
     ++	}
     ++
     ++	assert(reftable_stack_compaction_stats(st)->entries_written <
     ++	       (uint64_t)(N * fastlog2(N)));
     ++
     ++	reftable_stack_destroy(st);
     ++	clear_dir(dir);
     ++}
     ++
     ++int stack_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("test_reftable_stack_uptodate",
     ++		      &test_reftable_stack_uptodate);
     ++	add_test_case("test_reftable_stack_transaction_api",
     ++		      &test_reftable_stack_transaction_api);
     ++	add_test_case("test_reftable_stack_hash_id",
     ++		      &test_reftable_stack_hash_id);
     ++	add_test_case("test_sizes_to_segments_all_equal",
     ++		      &test_sizes_to_segments_all_equal);
     ++	add_test_case("test_reftable_stack_auto_compaction",
     ++		      &test_reftable_stack_auto_compaction);
     ++	add_test_case("test_reftable_stack_validate_refname",
     ++		      &test_reftable_stack_validate_refname);
     ++	add_test_case("test_reftable_stack_update_index_check",
     ++		      &test_reftable_stack_update_index_check);
     ++	add_test_case("test_reftable_stack_lock_failure",
     ++		      &test_reftable_stack_lock_failure);
     ++	add_test_case("test_reftable_stack_tombstone",
     ++		      &test_reftable_stack_tombstone);
     ++	add_test_case("test_reftable_stack_add_one",
     ++		      &test_reftable_stack_add_one);
     ++	add_test_case("test_empty_add", test_empty_add);
     ++	add_test_case("test_reflog_expire", test_reflog_expire);
     ++	add_test_case("test_suggest_compaction_segment",
     ++		      &test_suggest_compaction_segment);
     ++	add_test_case("test_suggest_compaction_segment_nothing",
     ++		      &test_suggest_compaction_segment_nothing);
     ++	add_test_case("test_sizes_to_segments", &test_sizes_to_segments);
     ++	add_test_case("test_sizes_to_segments_empty",
     ++		      &test_sizes_to_segments_empty);
     ++	add_test_case("test_log2", &test_log2);
     ++	add_test_case("test_parse_names", &test_parse_names);
     ++	add_test_case("test_read_file", &test_read_file);
     ++	add_test_case("test_names_equal", &test_names_equal);
     ++	add_test_case("test_reftable_stack_add", &test_reftable_stack_add);
     ++	return test_main(argc, argv);
     ++}
      
       ## reftable/system.h (new) ##
      @@
     @@ reftable/system.h (new)
      +			       const Bytef *source, uLong *sourceLen);
      +int hash_size(uint32_t id);
      +
     ++#endif
     +
     + ## reftable/test_framework.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 "test_framework.h"
     ++
     ++#include "system.h"
     ++#include "basics.h"
     ++#include "constants.h"
     ++
     ++struct test_case **test_cases;
     ++int test_case_len;
     ++int test_case_cap;
     ++
     ++struct test_case *new_test_case(const char *name, void (*testfunc)(void))
     ++{
     ++	struct test_case *tc = reftable_malloc(sizeof(struct test_case));
     ++	tc->name = name;
     ++	tc->testfunc = testfunc;
     ++	return tc;
     ++}
     ++
     ++struct test_case *add_test_case(const char *name, void (*testfunc)(void))
     ++{
     ++	struct test_case *tc = new_test_case(name, testfunc);
     ++	if (test_case_len == test_case_cap) {
     ++		test_case_cap = 2 * test_case_cap + 1;
     ++		test_cases = reftable_realloc(
     ++			test_cases, sizeof(struct test_case) * test_case_cap);
     ++	}
     ++
     ++	test_cases[test_case_len++] = tc;
     ++	return tc;
     ++}
     ++
     ++int test_main(int argc, const char *argv[])
     ++{
     ++	const char *filter = NULL;
     ++	int i = 0;
     ++	if (argc > 1) {
     ++		filter = argv[1];
     ++	}
     ++
     ++	for (i = 0; i < test_case_len; i++) {
     ++		const char *name = test_cases[i]->name;
     ++		if (filter == NULL || strstr(name, filter) != NULL) {
     ++			printf("case %s\n", name);
     ++			test_cases[i]->testfunc();
     ++		} else {
     ++			printf("skip %s\n", name);
     ++		}
     ++
     ++		reftable_free(test_cases[i]);
     ++	}
     ++	reftable_free(test_cases);
     ++	test_cases = 0;
     ++	test_case_len = 0;
     ++	test_case_cap = 0;
     ++	return 0;
     ++}
     ++
     ++void set_test_hash(byte *p, int i)
     ++{
     ++	memset(p, (byte)i, hash_size(SHA1_ID));
     ++}
     +
     + ## reftable/test_framework.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 TEST_FRAMEWORK_H
     ++#define TEST_FRAMEWORK_H
     ++
     ++#include "system.h"
     ++
     ++#include "reftable.h"
     ++
     ++#ifdef NDEBUG
     ++#undef NDEBUG
     ++#endif
     ++
     ++#include "system.h"
     ++
     ++#ifdef assert
     ++#undef assert
     ++#endif
     ++
     ++#define assert_err(c)                                                  \
     ++	if (c != 0) {                                                  \
     ++		fflush(stderr);                                        \
     ++		fflush(stdout);                                        \
     ++		fprintf(stderr, "%s: %d: error == %d (%s), want 0\n",  \
     ++			__FILE__, __LINE__, c, reftable_error_str(c)); \
     ++		abort();                                               \
     ++	}
     ++
     ++#define assert_streq(a, b)                                               \
     ++	if (strcmp(a, b)) {                                              \
     ++		fflush(stderr);                                          \
     ++		fflush(stdout);                                          \
     ++		fprintf(stderr, "%s:%d: %s (%s) != %s (%s)\n", __FILE__, \
     ++			__LINE__, #a, a, #b, b);                         \
     ++		abort();                                                 \
     ++	}
     ++
     ++#define assert(c)                                                          \
     ++	if (!(c)) {                                                        \
     ++		fflush(stderr);                                            \
     ++		fflush(stdout);                                            \
     ++		fprintf(stderr, "%s: %d: failed assertion %s\n", __FILE__, \
     ++			__LINE__, #c);                                     \
     ++		abort();                                                   \
     ++	}
     ++
     ++struct test_case {
     ++	const char *name;
     ++	void (*testfunc)(void);
     ++};
     ++
     ++struct test_case *new_test_case(const char *name, void (*testfunc)(void));
     ++struct test_case *add_test_case(const char *name, void (*testfunc)(void));
     ++int test_main(int argc, const char *argv[]);
     ++
     ++void set_test_hash(byte *p, int i);
     ++
      +#endif
      
       ## reftable/tree.c (new) ##
     @@ reftable/tree.h (new)
      +
      +#endif
      
     + ## reftable/tree_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 "tree.h"
     ++
     ++#include "basics.h"
     ++#include "record.h"
     ++#include "reftable.h"
     ++#include "test_framework.h"
     ++#include "reftable-tests.h"
     ++
     ++static int test_compare(const void *a, const void *b)
     ++{
     ++	return (char *)a - (char *)b;
     ++}
     ++
     ++struct curry {
     ++	void *last;
     ++};
     ++
     ++static void check_increasing(void *arg, void *key)
     ++{
     ++	struct curry *c = (struct curry *)arg;
     ++	if (c->last != NULL) {
     ++		assert(test_compare(c->last, key) < 0);
     ++	}
     ++	c->last = key;
     ++}
     ++
     ++static void test_tree(void)
     ++{
     ++	struct tree_node *root = NULL;
     ++
     ++	void *values[11] = { 0 };
     ++	struct tree_node *nodes[11] = { 0 };
     ++	int i = 1;
     ++	struct curry c = { 0 };
     ++	do {
     ++		nodes[i] = tree_search(values + i, &root, &test_compare, 1);
     ++		i = (i * 7) % 11;
     ++	} while (i != 1);
     ++
     ++	for (i = 1; i < ARRAY_SIZE(nodes); i++) {
     ++		assert(values + i == nodes[i]->key);
     ++		assert(nodes[i] ==
     ++		       tree_search(values + i, &root, &test_compare, 0));
     ++	}
     ++
     ++	infix_walk(root, check_increasing, &c);
     ++	tree_free(root);
     ++}
     ++
     ++int tree_test_main(int argc, const char *argv[])
     ++{
     ++	add_test_case("test_tree", &test_tree);
     ++	return test_main(argc, argv);
     ++}
     +
       ## reftable/update.sh (new) ##
      @@
      +#!/bin/sh
     @@ reftable/update.sh (new)
      +SRC=${SRC:-origin}
      +BRANCH=${BRANCH:-master}
      +
     -+((git --git-dir reftable-repo/.git fetch ${SRC} ${BRANCH}:import && cd reftable-repo && git checkout -f $(git rev-parse import) ) ||
     ++((git --git-dir reftable-repo/.git fetch -f ${SRC} ${BRANCH}:import && cd reftable-repo && git checkout -f $(git rev-parse import) ) ||
      +   git clone https://github.com/google/reftable reftable-repo)
      +
      +cp reftable-repo/c/*.[ch] reftable/
      +cp reftable-repo/c/include/*.[ch] reftable/
      +cp reftable-repo/LICENSE reftable/
     -+git --git-dir reftable-repo/.git show --no-patch HEAD \
     ++
     ++git --git-dir reftable-repo/.git show --no-patch --format=oneline HEAD \
      +  > reftable/VERSION
      +
      +mv reftable/system.h reftable/system.h~
      +sed 's|if REFTABLE_IN_GITCORE|if 1 /* REFTABLE_IN_GITCORE */|'  < reftable/system.h~ > reftable/system.h
      +
     -+# Remove unittests and compatibility hacks we don't need here.  
     -+rm reftable/*_test.c reftable/test_framework.* reftable/compat.*
     ++# Remove compatibility hacks we don't need here.
     ++rm reftable/compat.*
      +
     -+git add reftable/*.[ch] reftable/LICENSE reftable/VERSION 
     ++git add reftable/*.[ch] reftable/LICENSE reftable/VERSION
      
       ## reftable/writer.c (new) ##
      @@
     @@ reftable/writer.c (new)
      +
      +static int obj_index_tree_node_compare(const void *a, const void *b)
      +{
     -+	return slice_cmp(((const struct obj_index_tree_node *)a)->hash,
     -+			 ((const struct obj_index_tree_node *)b)->hash);
     ++	return slice_cmp(&((const struct obj_index_tree_node *)a)->hash,
     ++			 &((const struct obj_index_tree_node *)b)->hash);
      +}
      +
     -+static void writer_index_hash(struct reftable_writer *w, struct slice hash)
     ++static void writer_index_hash(struct reftable_writer *w, struct slice *hash)
      +{
      +	uint64_t off = w->next;
      +
     -+	struct obj_index_tree_node want = { .hash = hash };
     ++	struct obj_index_tree_node want = { .hash = *hash };
      +
      +	struct tree_node *node = tree_search(&want, &w->obj_index_tree,
      +					     &obj_index_tree_node_compare, 0);
     @@ reftable/writer.c (new)
      +	struct slice key = SLICE_INIT;
      +	int err = 0;
      +	reftable_record_key(rec, &key);
     -+	if (slice_cmp(w->last_key, key) >= 0)
     ++	if (slice_cmp(&w->last_key, &key) >= 0)
      +		goto done;
      +
     -+	slice_copy(&w->last_key, key);
     ++	slice_copy(&w->last_key, &key);
      +	if (w->block_writer == NULL) {
      +		writer_reinit_block_writer(w, reftable_record_type(rec));
      +	}
     @@ reftable/writer.c (new)
      +			.canary = SLICE_CANARY,
      +		};
      +
     -+		writer_index_hash(w, h);
     ++		writer_index_hash(w, &h);
      +	}
      +
      +	if (!w->opts.skip_index_objects && ref->target_value != NULL) {
     @@ reftable/writer.c (new)
      +			.len = hash_size(w->opts.hash_id),
      +			.canary = SLICE_CANARY,
      +		};
     -+		writer_index_hash(w, h);
     ++		writer_index_hash(w, &h);
      +	}
      +	return 0;
      +}
     @@ reftable/writer.c (new)
      +	struct common_prefix_arg *arg = (struct common_prefix_arg *)void_arg;
      +	struct obj_index_tree_node *entry = (struct obj_index_tree_node *)key;
      +	if (arg->last != NULL) {
     -+		int n = common_prefix_size(entry->hash, *arg->last);
     ++		int n = common_prefix_size(&entry->hash, arg->last);
      +		if (n > arg->max) {
      +			arg->max = n;
      +		}
     @@ reftable/writer.c (new)
      +	}
      +
      +	ir.offset = w->next;
     -+	slice_copy(&ir.last_key, w->block_writer->last_key);
     ++	slice_copy(&ir.last_key, &w->block_writer->last_key);
      +	w->index[w->index_len] = ir;
      +
      +	w->index_len++;
 10:  a86c3753717 ! 10:  f3d74b78135 Reftable support for git-core
     @@ builtin/init-db.c: static const char *const init_db_usage[] = {
       int cmd_init_db(int argc, const char **argv, const char *prefix)
       {
       	const char *git_dir;
     -+	const char *ref_storage_format = DEFAULT_REF_STORAGE;
     ++	const char *ref_storage_format = default_ref_storage();
       	const char *real_git_dir = NULL;
       	const char *work_tree;
       	const char *template_dir = NULL;
     @@ refs/reftable-backend.c (new)
      +	QSORT(sorted, transaction->nr, ref_update_cmp);
      +	reftable_writer_set_limits(writer, ts, ts);
      +
     -+
      +	for (i = 0; i < transaction->nr; i++) {
      +		struct ref_update *u = sorted[i];
      +		struct reftable_log_record *log = &logs[i];
     @@ t/t0031-reftable.sh (new)
      +	grep "commit: number 10" output &&
      +	git gc &&
      +	git reflog refs/heads/master >output &&
     -+	test_line_count = 0 output 
     ++	test_line_count = 0 output
      +'
      +
      +# This matches show-ref's output
     @@ t/t0031-reftable.sh (new)
      +		print_ref "refs/heads/master" &&
      +		print_ref "refs/tags/file" &&
      +		print_ref "refs/tags/test_tag" &&
     -+		print_ref "refs/tags/test_tag^{}" 
     ++		print_ref "refs/tags/test_tag^{}"
      +	} >expect &&
      +	git show-ref -d >actual &&
      +	test_cmp expect actual
  -:  ----------- > 11:  3e7868ee409 Hookup unittests for the reftable library.
 11:  d3613c2ff53 = 12:  1f193b6da23 Add GIT_DEBUG_REFS debugging mechanism
 12:  9b98ed614ec = 13:  0471f7e3570 vcxproj: adjust for the reftable changes
 13:  5e401e4f1ac ! 14:  a03c882b075 Add reftable testing infrastructure
     @@ builtin/clone.c: int cmd_clone(int argc, const char **argv, const char *prefix)
       	if (real_git_dir)
       		git_dir = real_git_dir;
      
     - ## builtin/init-db.c ##
     -@@ builtin/init-db.c: static const char *const init_db_usage[] = {
     - int cmd_init_db(int argc, const char **argv, const char *prefix)
     - {
     - 	const char *git_dir;
     --	const char *ref_storage_format = DEFAULT_REF_STORAGE;
     -+	const char *ref_storage_format = default_ref_storage();
     - 	const char *real_git_dir = NULL;
     - 	const char *work_tree;
     - 	const char *template_dir = NULL;
     -
       ## refs.c ##
      @@ refs.c: struct ref_store *get_main_ref_store(struct repository *r)
       	r->refs_private = ref_store_init(r->gitdir,

-- 
gitgitgadget