reftable library

From: Han-Wen Nienhuys <[email protected]>

For background, see the previous commit introducing the library.

This introduces the file refs/reftable-backend.c containing a reftable-powered ref storage backend.

It can be activated by passing --ref-storage=reftable to "git init", or setting GIT_TEST_REFTABLE in the environment.

Example use: see t/t0031-reftable.sh

---
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |    4 +
 builtin/clone.c                               |    5 +-
 builtin/init-db.c                             |   55 +-
 builtin/worktree.c                            |   27 +-
 cache.h                                       |    8 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 refs.c                                        |   27 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1418 +++++++++++++++++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |    9 +-
 t/t0031-reftable.sh                           |  199 +++
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1450-fsck.sh                               |    6 +
 t/t3210-pack-refs.sh                          |    6 +
 t/test-lib.sh                                 |    5 +
 20 files changed, 1771 insertions(+), 33 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100755 t/t0031-reftable.sh

index 7844ef30ff..7257623583 100644
@@ -100,3 +100,10 @@ If set, by default "git config" reads from both "config" and
 multiple working directory mode, "config" file is shared while
 "config.worktree" is per-working directory (i.e., it's in
 GIT_COMMON_DIR/worktrees/<id>/config.worktree)
+
+==== `refStorage`
+
+Specifies the file format for the ref database. Values are `files`
+(for the traditional packed + loose ref format) and `reftable` for the
+binary reftable format. See https://github.com/google/reftable for
+more information.

index 278c489da4..ec91fa14f4 100644
@@ -978,6 +978,7 @@ LIB_OBJS += reflog-walk.o
 LIB_OBJS += refs.o
 LIB_OBJS += refs/debug.o
 LIB_OBJS += refs/files-backend.o
+LIB_OBJS += refs/reftable-backend.o
 LIB_OBJS += refs/iterator.o
 LIB_OBJS += refs/packed-backend.o
 LIB_OBJS += refs/ref-cache.o

@@ -2408,8 +2409,11 @@ REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
+REFTABLE_TEST_OBJS += reftable/merged_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
+REFTABLE_TEST_OBJS += reftable/refname_test.o
 REFTABLE_TEST_OBJS += reftable/reftable_test.o
+REFTABLE_TEST_OBJS += reftable/stack_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 REFTABLE_TEST_OBJS += reftable/tree_test.o
 

index a0841923cf..974a374e9c 100644
@@ -1138,7 +1138,7 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 	}
 
 	init_db(git_dir, real_git_dir, option_template, GIT_HASH_UNKNOWN, NULL,
-		INIT_DB_QUIET);
+		default_ref_storage(), INIT_DB_QUIET);
 
 	if (real_git_dir)
 		git_dir = real_git_dir;

@@ -1273,7 +1273,8 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		 * Now that we know what algorithm the remote side is using,
 		 * let's set ours to the same thing.
 		 */
-		initialize_repository_version(hash_algo, 1);
+		initialize_repository_version(hash_algo, 1,
+					      default_ref_storage());
 		repo_set_hash_algo(the_repository, hash_algo);
 
 		mapped_refs = wanted_peer_refs(refs, &remote->fetch);

index ce56fdaaa9..7931620788 100644
@@ -12,6 +12,7 @@
 #include "submodule.h"
 #include "utf8.h"
 #include "worktree.h"
+#include "../refs/refs-internal.h"
 
 static const char * const worktree_usage[] = {
 	N_("git worktree add [<options>] <path> [<commit-ish>]"),

@@ -402,9 +403,29 @@ static int add_worktree(const char *path, const char *refname,
 	 * worktree.
 	 */
 	strbuf_reset(&sb);
-	strbuf_addf(&sb, "%s/HEAD", sb_repo.buf);
-	write_file(sb.buf, "%s", oid_to_hex(&null_oid));
-	strbuf_reset(&sb);
+	if (get_main_ref_store(the_repository)->be == &refs_be_reftable) {
+		/* XXX this is cut & paste from reftable_init_db. */
+		strbuf_addf(&sb, "%s/HEAD", sb_repo.buf);
+		write_file(sb.buf, "%s", "ref: refs/heads/.invalid\n");
+		strbuf_reset(&sb);
+
+		strbuf_addf(&sb, "%s/refs", sb_repo.buf);
+		safe_create_dir(sb.buf, 1);
+		strbuf_reset(&sb);
+
+		strbuf_addf(&sb, "%s/refs/heads", sb_repo.buf);
+		write_file(sb.buf, "this repository uses the reftable format");
+		strbuf_reset(&sb);
+
+		strbuf_addf(&sb, "%s/reftable", sb_repo.buf);
+		safe_create_dir(sb.buf, 1);
+		strbuf_reset(&sb);
+	} else {
+		strbuf_addf(&sb, "%s/HEAD", sb_repo.buf);
+		write_file(sb.buf, "%s", oid_to_hex(&null_oid));
+		strbuf_reset(&sb);
+	}
+
 	strbuf_addf(&sb, "%s/commondir", sb_repo.buf);
 	write_file(sb.buf, "../..");
 

index e986cf4ea9..545d2b7260 100644
@@ -627,9 +627,10 @@ int path_inside_repo(const char *prefix, const char *path);
 #define INIT_DB_EXIST_OK 0x0002
 
 int init_db(const char *git_dir, const char *real_git_dir,
-	    const char *template_dir, int hash_algo,
-	    const char *initial_branch, unsigned int flags);
-void initialize_repository_version(int hash_algo, int reinit);
+	    const char *template_dir, int hash_algo, const char *initial_branch,
+	    const char *ref_storage_format, unsigned int flags);
+void initialize_repository_version(int hash_algo, int reinit,
+				   const char *ref_storage_format);
 
 void sanitize_stdfds(void);
 int daemonize(void);

@@ -1043,6 +1044,7 @@ struct repository_format {
 	int is_bare;
 	int hash_algo;
 	char *work_tree;
+	char *ref_storage;
 	struct string_list unknown_extensions;
 	struct string_list v1_only_extensions;
 };

index c7eba69e54..ae4e25a1a4 100644
@@ -709,7 +709,7 @@ vcxproj:
 	# Make .vcxproj files and add them
 	unset QUIET_GEN QUIET_BUILT_IN; \
 	perl contrib/buildsystems/generate -g Vcxproj
-	git add -f git.sln {*,*/lib,t/helper/*}/*.vcxproj
+	git add -f git.sln {*,*/lib,*/libreftable,t/helper/*}/*.vcxproj
 
 	# Generate the LinkOrCopyBuiltins.targets and LinkOrCopyRemoteHttp.targets file
 	(echo '<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003">' && \

index d2584450ba..1a25789d28 100644
@@ -77,7 +77,7 @@ sub createProject {
     my $libs_release = "\n    ";
     my $libs_debug = "\n    ";
     if (!$static_library) {
-      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
+      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib|reftable\/libreftable\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
       $libs_debug = $libs_release;
       $libs_debug =~ s/zlib\.lib/zlibd\.lib/g;
       $libs_debug =~ s/libexpat\.lib/libexpatd\.lib/g;

@@ -232,6 +232,7 @@ sub createProject {
 EOM
     if (!$static_library || $target =~ 'vcs-svn' || $target =~ 'xdiff') {
       my $uuid_libgit = $$build_structure{"LIBS_libgit_GUID"};
+      my $uuid_libreftable = $$build_structure{"LIBS_reftable/libreftable_GUID"};
       my $uuid_xdiff_lib = $$build_structure{"LIBS_xdiff/lib_GUID"};
 
       print F << "EOM";

@@ -241,6 +242,14 @@ sub createProject {
       <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
     </ProjectReference>
 EOM
+      if (!($name =~ /xdiff|libreftable/)) {
+        print F << "EOM";
+    <ProjectReference Include="$cdup\\reftable\\libreftable\\libreftable.vcxproj">
+      <Project>$uuid_libreftable</Project>
+      <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
+    </ProjectReference>
+EOM
+      }
       if (!($name =~ 'xdiff')) {
         print F << "EOM";
     <ProjectReference Include="$cdup\\xdiff\\lib\\xdiff_lib.vcxproj">

index 392f0bbf68..1b874db334 100644
@@ -19,10 +19,16 @@
 #include "repository.h"
 #include "sigchain.h"
 
+const char *default_ref_storage(void)
+{
+	const char *test = getenv("GIT_TEST_REFTABLE");
+	return test ? "reftable" : "files";
+}
+
 /*
  * List of all available backends
  */
-static struct ref_storage_be *refs_backends = &refs_be_files;
+static struct ref_storage_be *refs_backends = &refs_be_reftable;
 
 static struct ref_storage_be *find_ref_storage_backend(const char *name)
 {

@@ -1754,13 +1760,13 @@ static struct ref_store *lookup_ref_store_map(struct hashmap *map,
  * Create, record, and return a ref_store instance for the specified
  * gitdir.
  */
-static struct ref_store *ref_store_init(const char *gitdir,
+static struct ref_store *ref_store_init(const char *gitdir, const char *be_name,
 					unsigned int flags)
 {
-	const char *be_name = "files";
-	struct ref_storage_be *be = find_ref_storage_backend(be_name);
+	struct ref_storage_be *be;
 	struct ref_store *refs;
 
+	be = find_ref_storage_backend(be_name);
 	if (!be)
 		BUG("reference backend %s is unknown", be_name);
 

@@ -1776,7 +1782,11 @@ struct ref_store *get_main_ref_store(struct repository *r)
 	if (!r->gitdir)
 		BUG("attempting to get main_ref_store outside of repository");
 
-	r->refs_private = ref_store_init(r->gitdir, REF_STORE_ALL_CAPS);
+	r->refs_private = ref_store_init(r->gitdir,
+					 r->ref_storage_format ?
+						       r->ref_storage_format :
+						       default_ref_storage(),
+					 REF_STORE_ALL_CAPS);
 	r->refs_private = maybe_debug_wrap_ref_store(r->gitdir, r->refs_private);
 	return r->refs_private;
 }

@@ -1832,7 +1842,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 		goto done;
 
 	/* assume that add_submodule_odb() has been called */
-	refs = ref_store_init(submodule_sb.buf,
+	refs = ref_store_init(submodule_sb.buf, default_ref_storage(),
 			      REF_STORE_READ | REF_STORE_ODB);
 	register_ref_store_map(&submodule_ref_stores, "submodule",
 			       refs, submodule);

@@ -1846,6 +1856,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 
 struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 {
+	const char *format = default_ref_storage();
 	struct ref_store *refs;
 	const char *id;
 

@@ -1859,9 +1870,9 @@ struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 
 	if (wt->id)
 		refs = ref_store_init(git_common_path("worktrees/%s", wt->id),
-				      REF_STORE_ALL_CAPS);
+				      format, REF_STORE_ALL_CAPS);
 	else
-		refs = ref_store_init(get_git_common_dir(),
+		refs = ref_store_init(get_git_common_dir(), format,
 				      REF_STORE_ALL_CAPS);
 
 	if (refs)

index 6695518156..7dc60472c9 100644
@@ -11,6 +11,9 @@ struct string_list;
 struct string_list_item;
 struct worktree;
 
+/* Returns the ref storage backend to use by default. */
+const char *default_ref_storage(void);
+
 /*
  * Resolve a reference, recursively following symbolic refererences.
  *

index 467f4b3c93..28166bf1f8 100644
@@ -669,6 +669,7 @@ struct ref_storage_be {
 };
 
 extern struct ref_storage_be refs_be_files;
+extern struct ref_storage_be refs_be_reftable;
 extern struct ref_storage_be refs_be_packed;
 
 /*

index a4174ddb06..ff0988dac8 100644
@@ -174,6 +174,8 @@ int repo_init(struct repository *repo,
 	if (worktree)
 		repo_set_worktree(repo, worktree);
 
+	repo->ref_storage_format = xstrdup_or_null(format.ref_storage);
+
 	clear_repository_format(&format);
 	return 0;
 

index b385ca3c94..8019a7d0a1 100644
@@ -78,6 +78,9 @@ struct repository {
 	 */
 	struct ref_store *refs_private;
 
+	/* The format to use for the ref database. */
+	char *ref_storage_format;
+
 	/*
 	 * Contains path to often used file names.
 	 */

index c04cd25a30..c6b57efd03 100644
@@ -500,6 +500,9 @@ static enum extension_result handle_extension(const char *var,
 			return error("invalid value for 'extensions.objectformat'");
 		data->hash_algo = format;
 		return EXTENSION_OK;
+	} else if (!strcmp(ext, "refstorage")) {
+		data->ref_storage = xstrdup(value);
+		return EXTENSION_OK;
 	}
 	return EXTENSION_UNKNOWN;
 }

@@ -651,6 +654,7 @@ void clear_repository_format(struct repository_format *format)
 	string_list_clear(&format->v1_only_extensions, 0);
 	free(format->work_tree);
 	free(format->partial_clone);
+	free(format->ref_storage);
 	init_repository_format(format);
 }
 

@@ -1308,8 +1312,11 @@ const char *setup_git_directory_gently(int *nongit_ok)
 				gitdir = DEFAULT_GIT_DIR_ENVIRONMENT;
 			setup_git_env(gitdir);
 		}
-		if (startup_info->have_repository)
+		if (startup_info->have_repository) {
 			repo_set_hash_algo(the_repository, repo_fmt.hash_algo);
+			the_repository->ref_storage_format =
+				xstrdup_or_null(repo_fmt.ref_storage);
+		}
 	}
 
 	strbuf_release(&dir);

index be12fb6350..c6f7832556 100755
@@ -4,6 +4,12 @@ test_description='avoid rewriting packed-refs unnecessarily'
 
 . ./test-lib.sh
 
+if test_have_prereq REFTABLE
+then
+  skip_all='skipping pack-refs tests; incompatible with reftable'
+  test_done
+fi
+
 # Add an identifying mark to the packed-refs file header line. This
 # shouldn't upset readers, and it should be omitted if the file is
 # ever rewritten.

index b17f5c21fb..cc5d01571a 100755
@@ -8,6 +8,12 @@ test_description='git fsck random collection of tests
 
 . ./test-lib.sh
 
+if test_have_prereq REFTABLE
+then
+  skip_all='skipping tests; incompatible with reftable'
+  test_done
+fi
+
 test_expect_success setup '
 	git config gc.auto 0 &&
 	git config i18n.commitencoding ISO-8859-1 &&

index f41b2afb99..edaef2c175 100755
@@ -11,6 +11,12 @@ semantic is still the same.
 '
 . ./test-lib.sh
 
+if test_have_prereq REFTABLE
+then
+  skip_all='skipping pack-refs tests; incompatible with reftable'
+  test_done
+fi
+
 test_expect_success 'enable reflogs' '
 	git config core.logallrefupdates true
 '

index a863ccee7e..7b638e0b8c 100644
@@ -1520,6 +1520,11 @@ parisc* | hppa*)
 	;;
 esac
 
+if test -n "$GIT_TEST_REFTABLE"
+then
+  test_set_prereq REFTABLE
+fi
+
 ( COLUMNS=1 && test $COLUMNS = 1 ) && test_set_prereq COLUMNS_CAN_BE_1
 test -z "$NO_PERL" && test_set_prereq PERL
 test -z "$NO_PTHREADS" && test_set_prereq PTHREADS

gitgitgadget

From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= <[email protected]>

In our git-prompt script we strive to use Bash builtins wherever possible, because fork()-ing subshells for command substitutions and fork()+exec()-ing Git commands are expensive on some platforms. We even read and parse '.git/HEAD' using Bash builtins to get the name of the current branch [1]. However, the upcoming reftable refs backend won't use '.git/HEAD' at all, but will write an invalid refname as placeholder for backwards compatibility instead, which will break our git-prompt script.

Update the git-prompt script to recognize the placeholder '.git/HEAD' written by the reftable backend (its content is specified in the reftable specs), and then fall back to use 'git symbolic-ref' to get the name of the current branch.

[1] 3a43c4b5bd (bash prompt: use bash builtins to find out current

    branch, 2011-03-31)

---
 contrib/completion/git-prompt.sh | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

index 4640a1535d..2e5a5d8027 100644
@@ -478,10 +478,15 @@ __git_ps1 ()
 			if ! __git_eread "$g/HEAD" head; then
 				return $exit
 			fi
-			# is it a symbolic ref?
 			b="${head#ref: }"
 			if [ "$head" = "$b" ]; then
 				detached=yes
+			elif [ "$b" = "refs/heads/.invalid" ]; then
+				# Reftable
+				b="$(git symbolic-ref HEAD 2>/dev/null)" ||
+				detached=yes
+			fi
+			if [ "$detached" = yes ]; then
 				b="$(
 				case "${GIT_PS1_DESCRIBE_STYLE-}" in
 				(contains)

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This command dumps individual tables or a stack of of tables.

---
 Makefile                 |  1 +
 reftable/dump.c          | 31 +++++++++++++++++++------------
 t/helper/test-reftable.c |  5 +++++
 t/helper/test-tool.c     |  1 +
 t/helper/test-tool.h     |  1 +
 5 files changed, 27 insertions(+), 12 deletions(-)

index ec91fa14f4..6154db5615 100644
@@ -2409,6 +2409,7 @@ REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
+REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/refname_test.o

index 00b444e8c9..0bd7a1cfa6 100644
@@ -12,18 +12,25 @@ license that can be found in the LICENSE file or at
 #include <unistd.h>
 #include <string.h>
 
-#include "reftable.h"
+#include "reftable-blocksource.h"
+#include "reftable-error.h"
+#include "reftable-merged.h"
+#include "reftable-record.h"
 #include "reftable-tests.h"
+#include "reftable-writer.h"
+#include "reftable-iterator.h"
+#include "reftable-reader.h"
+#include "reftable-stack.h"
 
 static uint32_t hash_id;
 
 static int dump_table(const char *tablename)
 {
-	struct reftable_block_source src = { 0 };
+	struct reftable_block_source src = { NULL };
 	int err = reftable_block_source_from_file(&src, tablename);
-	struct reftable_iterator it = { 0 };
-	struct reftable_ref_record ref = { 0 };
-	struct reftable_log_record log = { 0 };
+	struct reftable_iterator it = { NULL };
+	struct reftable_ref_record ref = { NULL };
+	struct reftable_log_record log = { NULL };
 	struct reftable_reader *r = NULL;
 
 	if (err < 0)

@@ -49,7 +56,7 @@ static int dump_table(const char *tablename)
 		reftable_ref_record_print(&ref, hash_id);
 	}
 	reftable_iterator_destroy(&it);
-	reftable_ref_record_clear(&ref);
+	reftable_ref_record_release(&ref);
 
 	err = reftable_reader_seek_log(r, &it, "");
 	if (err < 0) {

@@ -66,7 +73,7 @@ static int dump_table(const char *tablename)
 		reftable_log_record_print(&log, hash_id);
 	}
 	reftable_iterator_destroy(&it);
-	reftable_log_record_clear(&log);
+	reftable_log_record_release(&log);
 
 	reftable_reader_free(r);
 	return 0;

@@ -95,9 +102,9 @@ static int dump_stack(const char *stackdir)
 {
 	struct reftable_stack *stack = NULL;
 	struct reftable_write_options cfg = {};
-	struct reftable_iterator it = { 0 };
-	struct reftable_ref_record ref = { 0 };
-	struct reftable_log_record log = { 0 };
+	struct reftable_iterator it = { NULL };
+	struct reftable_ref_record ref = { NULL };
+	struct reftable_log_record log = { NULL };
 	struct reftable_merged_table *merged = NULL;
 
 	int err = reftable_new_stack(&stack, stackdir, cfg);

@@ -122,7 +129,7 @@ static int dump_stack(const char *stackdir)
 		reftable_ref_record_print(&ref, hash_id);
 	}
 	reftable_iterator_destroy(&it);
-	reftable_ref_record_clear(&ref);
+	reftable_ref_record_release(&ref);
 
 	err = reftable_merged_table_seek_log(merged, &it, "");
 	if (err < 0) {

@@ -139,7 +146,7 @@ static int dump_stack(const char *stackdir)
 		reftable_log_record_print(&log, hash_id);
 	}
 	reftable_iterator_destroy(&it);
-	reftable_log_record_clear(&log);
+	reftable_log_record_release(&log);
 
 	reftable_stack_destroy(stack);
 	return 0;

index 3b702f4855..c1ba131c3a 100644
@@ -13,3 +13,8 @@ int cmd__reftable(int argc, const char **argv)
 	tree_test_main(argc, argv);
 	return 0;
 }
+
+int cmd__dump_reftable(int argc, const char **argv)
+{
+	return reftable_dump_main(argc, (char *const *)argv);
+}

index 0208a0a41c..f064440a31 100644
@@ -56,6 +56,7 @@ static struct test_cmd cmds[] = {
 	{ "read-midx", cmd__read_midx },
 	{ "ref-store", cmd__ref_store },
 	{ "reftable", cmd__reftable },
+	{ "dump-reftable", cmd__dump_reftable },
 	{ "regex", cmd__regex },
 	{ "repository", cmd__repository },
 	{ "revision-walking", cmd__revision_walking },

index 1de39ce5b5..226af8c6b8 100644
@@ -18,6 +18,7 @@ int cmd__dump_cache_tree(int argc, const char **argv);
 int cmd__dump_fsmonitor(int argc, const char **argv);
 int cmd__dump_split_index(int argc, const char **argv);
 int cmd__dump_untracked_cache(int argc, const char **argv);
+int cmd__dump_reftable(int argc, const char **argv);
 int cmd__example_decorate(int argc, const char **argv);
 int cmd__fast_rebase(int argc, const char **argv);
 int cmd__genrandom(int argc, const char **argv);

gitgitgadget

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

The final commit should also be split up, but I want to wait until we have consensus that the bottom commits look good.

version 8 Dec 2020:

* fixes for windows: add random suffix to table names
* tagged unions for reftable_ref_record
* some fixes by dscho
* some tweaks in response to Felipe Contreras
* switched to github.com/hanwen/reftable (which does not need CLA)

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

Han-Wen Nienhuys (14):
init-db: set the_repository->hash_algo early on
reftable: add LICENSE
reftable: add error related functionality
reftable: utility functions
reftable: add blocksource, an abstraction for random access reads
reftable: (de)serialization for the polymorphic record type.
reftable: reading/writing blocks
reftable: a generic binary tree implementation
reftable: write reftable files
reftable: read reftable files
reftable: reftable file level tests
reftable: rest of library
Reftable support for git-core
Add "test-tool dump-reftable" command.

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

 Documentation/config/extensions.txt           |    9 +
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   46 +-
 builtin/clone.c                               |    5 +-
 builtin/init-db.c                             |   76 +-
 builtin/worktree.c                            |   27 +-
 cache.h                                       |    8 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/CMakeLists.txt           |   14 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 contrib/completion/git-prompt.sh              |    7 +-
 refs.c                                        |   27 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1435 +++++++++++++++++
 reftable/.gitattributes                       |    1 +
 reftable/LICENSE                              |   31 +
 reftable/VERSION                              |    1 +
 reftable/basics.c                             |  128 ++
 reftable/basics.h                             |   60 +
 reftable/basics_test.c                        |   98 ++
 reftable/block.c                              |  440 +++++
 reftable/block.h                              |  127 ++
 reftable/block_test.c                         |  121 ++
 reftable/blocksource.c                        |  148 ++
 reftable/blocksource.h                        |   22 +
 reftable/constants.h                          |   21 +
 reftable/dump.c                               |  213 +++
 reftable/error.c                              |   41 +
 reftable/iter.c                               |  248 +++
 reftable/iter.h                               |   75 +
 reftable/merged.c                             |  366 +++++
 reftable/merged.h                             |   35 +
 reftable/merged_test.c                        |  343 ++++
 reftable/pq.c                                 |  115 ++
 reftable/pq.h                                 |   32 +
 reftable/publicbasics.c                       |   58 +
 reftable/reader.c                             |  733 +++++++++
 reftable/reader.h                             |   75 +
 reftable/record.c                             | 1157 +++++++++++++
 reftable/record.h                             |  139 ++
 reftable/record_test.c                        |  398 +++++
 reftable/refname.c                            |  209 +++
 reftable/refname.h                            |   29 +
 reftable/refname_test.c                       |  102 ++
 reftable/reftable-blocksource.h               |   49 +
 reftable/reftable-error.h                     |   62 +
 reftable/reftable-generic.h                   |   48 +
 reftable/reftable-iterator.h                  |   37 +
 reftable/reftable-malloc.h                    |   18 +
 reftable/reftable-merged.h                    |   68 +
 reftable/reftable-reader.h                    |   89 +
 reftable/reftable-record.h                    |  100 ++
 reftable/reftable-stack.h                     |  120 ++
 reftable/reftable-tests.h                     |   22 +
 reftable/reftable-writer.h                    |  147 ++
 reftable/reftable.c                           |   98 ++
 reftable/reftable_test.c                      |  580 +++++++
 reftable/stack.c                              | 1260 +++++++++++++++
 reftable/stack.h                              |   41 +
 reftable/stack_test.c                         |  803 +++++++++
 reftable/system.h                             |   32 +
 reftable/test_framework.c                     |   23 +
 reftable/test_framework.h                     |   53 +
 reftable/tree.c                               |   63 +
 reftable/tree.h                               |   34 +
 reftable/tree_test.c                          |   61 +
 reftable/writer.c                             |  681 ++++++++
 reftable/writer.h                             |   50 +
 reftable/zlib-compat.c                        |   92 ++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |    9 +-
 t/helper/test-reftable.c                      |   20 +
 t/helper/test-tool.c                          |    4 +-
 t/helper/test-tool.h                          |    2 +
 t/t0031-reftable.sh                           |  199 +++
 t/t0032-reftable-unittest.sh                  |   15 +
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1450-fsck.sh                               |    6 +
 t/t3210-pack-refs.sh                          |    6 +
 t/test-lib.sh                                 |    5 +
 82 files changed, 12112 insertions(+), 40 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100644 reftable/.gitattributes
 create mode 100644 reftable/LICENSE
 create mode 100644 reftable/VERSION
 create mode 100644 reftable/basics.c
 create mode 100644 reftable/basics.h
 create mode 100644 reftable/basics_test.c
 create mode 100644 reftable/block.c
 create mode 100644 reftable/block.h
 create mode 100644 reftable/block_test.c
 create mode 100644 reftable/blocksource.c
 create mode 100644 reftable/blocksource.h
 create mode 100644 reftable/constants.h
 create mode 100644 reftable/dump.c
 create mode 100644 reftable/error.c
 create mode 100644 reftable/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/publicbasics.c
 create mode 100644 reftable/reader.c
 create mode 100644 reftable/reader.h
 create mode 100644 reftable/record.c
 create mode 100644 reftable/record.h
 create mode 100644 reftable/record_test.c
 create mode 100644 reftable/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/refname_test.c
 create mode 100644 reftable/reftable-blocksource.h
 create mode 100644 reftable/reftable-error.h
 create mode 100644 reftable/reftable-generic.h
 create mode 100644 reftable/reftable-iterator.h
 create mode 100644 reftable/reftable-malloc.h
 create mode 100644 reftable/reftable-merged.h
 create mode 100644 reftable/reftable-reader.h
 create mode 100644 reftable/reftable-record.h
 create mode 100644 reftable/reftable-stack.h
 create mode 100644 reftable/reftable-tests.h
 create mode 100644 reftable/reftable-writer.h
 create mode 100644 reftable/reftable.c
 create mode 100644 reftable/reftable_test.c
 create mode 100644 reftable/stack.c
 create mode 100644 reftable/stack.h
 create mode 100644 reftable/stack_test.c
 create mode 100644 reftable/system.h
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h
 create mode 100644 reftable/tree.c
 create mode 100644 reftable/tree.h
 create mode 100644 reftable/tree_test.c
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c
 create mode 100644 t/helper/test-reftable.c
 create mode 100755 t/t0031-reftable.sh
 create mode 100755 t/t0032-reftable-unittest.sh

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

Range-diff vs v3:

  1:  030998a732a <  -:  ----------- move sleep_millisec to git-compat-util.h
  2:  cf667653dff <  -:  ----------- init-db: set the_repository->hash_algo early on
  -:  ----------- >  1:  40ac041d0ef init-db: set the_repository->hash_algo early on
  3:  91c3ac2449e =  2:  cc0fe58bd33 reftable: add LICENSE
  4:  2aa30f536fb !  3:  798f680b800 reftable: add error related functionality
     @@ reftable/error.c (new)
      +		return "zlib failure";
      +	case REFTABLE_NAME_CONFLICT:
      +		return "file/directory conflict";
     ++	case REFTABLE_EMPTY_TABLE_ERROR:
     ++		return "wrote empty table";
      +	case REFTABLE_REFNAME_ERROR:
      +		return "invalid refname";
      +	case -1:
     @@ reftable/reftable-error.h (new)
      +#define REFTABLE_ERROR_H
      +
      +/*
     -+ Errors in reftable calls are signaled with negative integer return values. 0
     -+ means success.
     -+*/
     ++ * Errors in reftable calls are signaled with negative integer return values. 0
     ++ * means success.
     ++ */
      +enum reftable_error {
      +	/* Unexpected file system behavior */
      +	REFTABLE_IO_ERROR = -2,
      +
     -+	/* Format inconsistency on reading data
     -+	 */
     ++	/* Format inconsistency on reading data */
      +	REFTABLE_FORMAT_ERROR = -3,
      +
     -+	/* File does not exist. Returned from block_source_from_file(),  because
     -+	   it needs special handling in stack.
     -+	*/
     ++	/* File does not exist. Returned from block_source_from_file(), because
     ++	 * it needs special handling in stack.
     ++	 */
      +	REFTABLE_NOT_EXIST_ERROR = -4,
      +
      +	/* Trying to write out-of-date data. */
      +	REFTABLE_LOCK_ERROR = -5,
      +
      +	/* Misuse of the API:
     -+	   - on writing a record with NULL refname.
     -+	   - on writing a reftable_ref_record outside the table limits
     -+	   - on writing a ref or log record before the stack's next_update_index
     -+	   - on writing a log record with multiline message with
     -+	   exact_log_message unset
     -+	   - on reading a reftable_ref_record from log iterator, or vice versa.
     -+
     -+	  When a call misuses the API, the internal state of the library is kept
     -+	  unchanged.
     -+	*/
     ++	 *  - on writing a record with NULL refname.
     ++	 *  - on writing a reftable_ref_record outside the table limits
     ++	 *  - on writing a ref or log record before the stack's
     ++	 * next_update_inde*x
     ++	 *  - on writing a log record with multiline message with
     ++	 *  exact_log_message unset
     ++	 *  - on reading a reftable_ref_record from log iterator, or vice versa.
     ++	 *
     ++	 * When a call misuses the API, the internal state of the library is
     ++	 * kept unchanged.
     ++	 */
      +	REFTABLE_API_ERROR = -6,
      +
      +	/* Decompression error */
     @@ reftable/reftable-error.h (new)
      +	/* Dir/file conflict. */
      +	REFTABLE_NAME_CONFLICT = -9,
      +
     -+	/* Illegal ref name. */
     ++	/* Invalid ref name. */
      +	REFTABLE_REFNAME_ERROR = -10,
      +};
      +
  5:  987d1d186fd !  4:  2f55ff6d240 reftable: utility functions
     @@ Commit message
          This commit provides basic utility classes for the reftable library.
      
          Signed-off-by: Han-Wen Nienhuys <[email protected]>
     +    Helped-by: Johannes Schindelin <[email protected]>
      
       ## Makefile ##
      @@ Makefile: TEST_BUILTINS_OBJS += test-read-cache.o
     @@ Makefile: cocciclean:
       	$(RM) $(TEST_PROGRAMS)
       	$(RM) $(FUZZ_PROGRAMS)
      
     + ## contrib/buildsystems/CMakeLists.txt ##
     +@@ contrib/buildsystems/CMakeLists.txt: parse_makefile_for_sources(libxdiff_SOURCES "XDIFF_OBJS")
     + list(TRANSFORM libxdiff_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
     + add_library(xdiff STATIC ${libxdiff_SOURCES})
     + 
     ++#reftable
     ++parse_makefile_for_sources(reftable_SOURCES "REFTABLE_OBJS")
     ++
     ++list(TRANSFORM reftable_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
     ++add_library(reftable STATIC ${reftable_SOURCES})
     ++
     + if(WIN32)
     + 	if(NOT MSVC)#use windres when compiling with gcc and clang
     + 		add_custom_command(OUTPUT ${CMAKE_BINARY_DIR}/git.res
     +@@ contrib/buildsystems/CMakeLists.txt: endif()
     + #link all required libraries to common-main
     + add_library(common-main OBJECT ${CMAKE_SOURCE_DIR}/common-main.c)
     + 
     +-target_link_libraries(common-main libgit xdiff ${ZLIB_LIBRARIES})
     ++target_link_libraries(common-main libgit xdiff reftable ${ZLIB_LIBRARIES})
     + if(Intl_FOUND)
     + 	target_link_libraries(common-main ${Intl_LIBRARIES})
     + endif()
     +@@ contrib/buildsystems/CMakeLists.txt: if(BUILD_TESTING)
     + add_executable(test-fake-ssh ${CMAKE_SOURCE_DIR}/t/helper/test-fake-ssh.c)
     + target_link_libraries(test-fake-ssh common-main)
     + 
     ++#reftable-tests
     ++parse_makefile_for_sources(test-reftable_SOURCES "REFTABLE_TEST_OBJS")
     ++list(TRANSFORM test-reftable_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
     ++
     + #test-tool
     + parse_makefile_for_sources(test-tool_SOURCES "TEST_BUILTINS_OBJS")
     + 
     + list(TRANSFORM test-tool_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/t/helper/")
     +-add_executable(test-tool ${CMAKE_SOURCE_DIR}/t/helper/test-tool.c ${test-tool_SOURCES})
     ++add_executable(test-tool ${CMAKE_SOURCE_DIR}/t/helper/test-tool.c ${test-tool_SOURCES} ${test-reftable_SOURCES})
     + target_link_libraries(test-tool common-main)
     + 
     + set_target_properties(test-fake-ssh test-tool
     +
       ## reftable/basics.c (new) ##
      @@
      +/*
     @@ reftable/basics.c (new)
      +	size_t lo = 0;
      +	size_t hi = sz;
      +
     -+	/* invariant: (hi == sz) || f(hi) == true
     -+	   (lo == 0 && f(0) == true) || fi(lo) == false
     ++	/* Invariants:
     ++	 *
     ++	 *  (hi == sz) || f(hi) == true
     ++	 *  (lo == 0 && f(0) == true) || fi(lo) == false
      +	 */
      +	while (hi - lo > 1) {
      +		size_t mid = lo + (hi - lo) / 2;
      +
     -+		int val = f(mid, args);
     -+		if (val) {
     ++		if (f(mid, args))
      +			hi = mid;
     -+		} else {
     ++		else
      +			lo = mid;
     -+		}
      +	}
      +
     -+	if (lo == 0) {
     -+		if (f(0, args)) {
     -+			return 0;
     -+		} else {
     -+			return 1;
     -+		}
     -+	}
     ++	if (lo)
     ++		return hi;
      +
     -+	return hi;
     ++	return f(0, args) ? 0 : 1;
      +}
      +
      +void free_names(char **a)
      +{
     -+	char **p = a;
     -+	if (p == NULL) {
     ++	char **p;
     ++	if (a == NULL) {
      +		return;
      +	}
     -+	while (*p) {
     ++	for (p = a; *p; p++) {
      +		reftable_free(*p);
     -+		p++;
      +	}
      +	reftable_free(a);
      +}
      +
      +int names_length(char **names)
      +{
     -+	int len = 0;
      +	char **p = names;
     -+	while (*p) {
     -+		p++;
     -+		len++;
     ++	for (; *p; p++) {
     ++		/* empty */
      +	}
     -+	return len;
     ++	return p - names;
      +}
      +
      +void parse_names(char *buf, int size, char ***namesp)
     @@ reftable/basics.c (new)
      +	char *end = buf + size;
      +	while (p < end) {
      +		char *next = strchr(p, '\n');
     -+		if (next != NULL) {
     ++		if (next && next < end) {
      +			*next = 0;
      +		} else {
      +			next = end;
     @@ reftable/basics.c (new)
      +			if (names_len == names_cap) {
      +				names_cap = 2 * names_cap + 1;
      +				names = reftable_realloc(
     -+					names, names_cap * sizeof(char *));
     ++					names, names_cap * sizeof(*names));
      +			}
      +			names[names_len++] = xstrdup(p);
      +		}
      +		p = next + 1;
      +	}
      +
     -+	if (names_len == names_cap) {
     -+		names_cap = 2 * names_cap + 1;
     -+		names = reftable_realloc(names, names_cap * sizeof(char *));
     -+	}
     -+
     ++	names = reftable_realloc(names, (names_len + 1) * sizeof(*names));
      +	names[names_len] = NULL;
      +	*namesp = names;
      +}
      +
      +int names_equal(char **a, char **b)
      +{
     -+	while (*a && *b) {
     -+		if (strcmp(*a, *b)) {
     ++	int i = 0;
     ++	for (; a[i] && b[i]; i++) {
     ++		if (strcmp(a[i], b[i])) {
      +			return 0;
      +		}
     -+
     -+		a++;
     -+		b++;
      +	}
      +
     -+	return *a == *b;
     ++	return a[i] == b[i];
      +}
      +
      +int common_prefix_size(struct strbuf *a, struct strbuf *b)
      +{
      +	int p = 0;
     -+	while (p < a->len && p < b->len) {
     -+		if (a->buf[p] != b->buf[p]) {
     ++	for (; p < a->len && p < b->len; p++) {
     ++		if (a->buf[p] != b->buf[p])
      +			break;
     -+		}
     -+		p++;
      +	}
      +
      +	return p;
     @@ reftable/basics.h (new)
      +void put_be16(uint8_t *out, uint16_t i);
      +
      +/*
     -+  find smallest index i in [0, sz) at which f(i) is true, assuming
     -+  that f is ascending. Return sz if f(i) is false for all indices.
     -+*/
     ++ * find smallest index i in [0, sz) at which f(i) is true, assuming
     ++ * that f is ascending. Return sz if f(i) is false for all indices.
     ++ *
     ++ * Contrary to bsearch(3), this returns something useful if the argument is not
     ++ * found.
     ++ */
      +int binsearch(size_t sz, int (*f)(size_t k, void *args), void *args);
      +
      +/*
     -+  Frees a NULL terminated array of malloced strings. The array itself is also
     -+  freed.
     ++ * Frees a NULL terminated array of malloced strings. The array itself is also
     ++ * freed.
      + */
      +void free_names(char **a);
      +
     -+/* parse a newline separated list of names. Empty names are discarded. */
     ++/* parse a newline separated list of names. `size` is the length of the buffer,
     ++ * without terminating '\0'. Empty names are discarded. */
      +void parse_names(char *buf, int size, char ***namesp);
      +
      +/* compares two NULL-terminated arrays of strings. */
     @@ reftable/basics_test.c (new)
      +	}
      +}
      +
     -+int basics_test_main(int argc, const char *argv[])
     ++static void test_names_length(void)
      +{
     -+	test_binsearch();
     -+	return 0;
     ++	char *a[] = { "a", "b", NULL };
     ++	EXPECT(names_length(a) == 2);
      +}
     -
     - ## reftable/compat.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 COMPAT_H
     -+#define COMPAT_H
      +
     -+#include "system.h"
     -+
     -+#ifdef REFTABLE_STANDALONE
     -+
     -+/* functions that git-core provides, for standalone compilation */
     -+#include <stdint.h>
     -+
     -+uint64_t get_be64(void *in);
     -+void put_be64(void *out, uint64_t i);
     -+
     -+void put_be32(void *out, uint32_t i);
     -+uint32_t get_be32(uint8_t *in);
     -+
     -+uint16_t get_be16(uint8_t *in);
     -+
     -+#define ARRAY_SIZE(a) sizeof((a)) / sizeof((a)[0])
     -+#define FREE_AND_NULL(x)          \
     -+	do {                      \
     -+		reftable_free(x); \
     -+		(x) = NULL;       \
     -+	} while (0)
     -+#define QSORT(arr, n, cmp) qsort(arr, n, sizeof(arr[0]), cmp)
     -+#define SWAP(a, b)                              \
     -+	{                                       \
     -+		char tmp[sizeof(a)];            \
     -+		assert(sizeof(a) == sizeof(b)); \
     -+		memcpy(&tmp[0], &a, sizeof(a)); \
     -+		memcpy(&a, &b, sizeof(a));      \
     -+		memcpy(&b, &tmp[0], sizeof(a)); \
     -+	}
     ++static void test_parse_names_normal(void)
     ++{
     ++	char in[] = "a\nb\n";
     ++	char **out = NULL;
     ++	parse_names(in, strlen(in), &out);
     ++	EXPECT(!strcmp(out[0], "a"));
     ++	EXPECT(!strcmp(out[1], "b"));
     ++	EXPECT(out[2] == NULL);
     ++	free_names(out);
     ++}
      +
     -+char *xstrdup(const char *s);
     ++static void test_parse_names_drop_empty(void)
     ++{
     ++	char in[] = "a\n\n";
     ++	char **out = NULL;
     ++	parse_names(in, strlen(in), &out);
     ++	EXPECT(!strcmp(out[0], "a"));
     ++	EXPECT(out[1] == NULL);
     ++	free_names(out);
     ++}
      +
     -+void sleep_millisec(int millisecs);
     ++static void test_common_prefix(void)
     ++{
     ++	struct strbuf s1 = STRBUF_INIT;
     ++	struct strbuf s2 = STRBUF_INIT;
     ++	strbuf_addstr(&s1, "abcdef");
     ++	strbuf_addstr(&s2, "abc");
     ++	EXPECT(common_prefix_size(&s1, &s2) == 3);
     ++	strbuf_release(&s1);
     ++	strbuf_release(&s2);
     ++}
      +
     -+#endif
     -+#endif
     ++int basics_test_main(int argc, const char *argv[])
     ++{
     ++	RUN_TEST(test_common_prefix);
     ++	RUN_TEST(test_parse_names_normal);
     ++	RUN_TEST(test_parse_names_drop_empty);
     ++	RUN_TEST(test_binsearch);
     ++	RUN_TEST(test_names_length);
     ++	return 0;
     ++}
      
       ## reftable/publicbasics.c (new) ##
      @@
     @@ reftable/reftable-malloc.h (new)
      +
      +#include <stddef.h>
      +
     -+/*
     -+  Overrides the functions to use for memory management.
     -+ */
     ++/* Overrides the functions to use for memory management. */
      +void reftable_set_alloc(void *(*malloc)(size_t),
      +			void *(*realloc)(void *, size_t), void (*free)(void *));
      +
     @@ reftable/test_framework.h (new)
      +		abort();                                                   \
      +	}
      +
     ++#define RUN_TEST(f)                          \
     ++	fprintf(stderr, "running %s\n", #f); \
     ++	fflush(stderr);                      \
     ++	f();
     ++
      +void set_test_hash(uint8_t *p, int i);
      +
      +/* Like strbuf_add, but suitable for passing to reftable_new_writer
     @@ t/t0032-reftable-unittest.sh (new)
      +. ./test-lib.sh
      +
      +test_expect_success 'unittests' '
     -+       test-tool reftable
     ++	TMPDIR=$(pwd) && export TMPDIR &&
     ++	test-tool reftable
      +'
      +
      +test_done
  6:  f71e82b995d !  5:  aaa817f8598 reftable: add blocksource, an abstraction for random access reads
     @@ reftable/reftable-blocksource.h (new)
      +};
      +
      +/* a contiguous segment of bytes. It keeps track of its generating block_source
     -+   so it can return itself into the pool.
     -+*/
     ++ * so it can return itself into the pool. */
      +struct reftable_block {
      +	uint8_t *data;
      +	int len;
  7:  bbe2ed71734 !  6:  e13afe31525 reftable: (de)serialization for the polymorphic record type.
     @@ reftable/record.c (new)
      +	return 0;
      +}
      +
     ++uint8_t *reftable_ref_record_val1(struct reftable_ref_record *rec)
     ++{
     ++	switch (rec->value_type) {
     ++	case REFTABLE_REF_VAL1:
     ++		return rec->value.val1;
     ++	case REFTABLE_REF_VAL2:
     ++		return rec->value.val2.value;
     ++	default:
     ++		return NULL;
     ++	}
     ++}
     ++
     ++uint8_t *reftable_ref_record_val2(struct reftable_ref_record *rec)
     ++{
     ++	switch (rec->value_type) {
     ++	case REFTABLE_REF_VAL2:
     ++		return rec->value.val2.target_value;
     ++	default:
     ++		return NULL;
     ++	}
     ++}
     ++
      +static int decode_string(struct strbuf *dest, struct string_view in)
      +{
      +	int start_len = in.len;
     @@ reftable/record.c (new)
      +	assert(hash_size > 0);
      +
      +	/* This is simple and correct, but we could probably reuse the hash
     -+	   fields. */
     ++	 * fields. */
      +	reftable_ref_record_release(ref);
      +	if (src->refname != NULL) {
      +		ref->refname = xstrdup(src->refname);
      +	}
     -+
     -+	if (src->target != NULL) {
     -+		ref->target = xstrdup(src->target);
     -+	}
     -+
     -+	if (src->target_value != NULL) {
     -+		ref->target_value = reftable_malloc(hash_size);
     -+		memcpy(ref->target_value, src->target_value, hash_size);
     -+	}
     -+
     -+	if (src->value != NULL) {
     -+		ref->value = reftable_malloc(hash_size);
     -+		memcpy(ref->value, src->value, hash_size);
     -+	}
      +	ref->update_index = src->update_index;
     ++	ref->value_type = src->value_type;
     ++	switch (src->value_type) {
     ++	case REFTABLE_REF_DELETION:
     ++		break;
     ++	case REFTABLE_REF_VAL1:
     ++		ref->value.val1 = reftable_malloc(hash_size);
     ++		memcpy(ref->value.val1, src->value.val1, hash_size);
     ++		break;
     ++	case REFTABLE_REF_VAL2:
     ++		ref->value.val2.value = reftable_malloc(hash_size);
     ++		memcpy(ref->value.val2.value, src->value.val2.value, hash_size);
     ++		ref->value.val2.target_value = reftable_malloc(hash_size);
     ++		memcpy(ref->value.val2.target_value,
     ++		       src->value.val2.target_value, hash_size);
     ++		break;
     ++	case REFTABLE_REF_SYMREF:
     ++		ref->value.symref = xstrdup(src->value.symref);
     ++		break;
     ++	}
      +}
      +
      +static char hexdigit(int c)
     @@ reftable/record.c (new)
      +void reftable_ref_record_print(struct reftable_ref_record *ref,
      +			       uint32_t hash_id)
      +{
     -+	char hex[SHA256_SIZE + 1] = { 0 };
     ++	char hex[2 * SHA256_SIZE + 1] = { 0 }; /* BUG */
      +	printf("ref{%s(%" PRIu64 ") ", ref->refname, ref->update_index);
     -+	if (ref->value != NULL) {
     -+		hex_format(hex, ref->value, hash_size(hash_id));
     -+		printf("%s", hex);
     -+	}
     -+	if (ref->target_value != NULL) {
     -+		hex_format(hex, ref->target_value, hash_size(hash_id));
     -+		printf(" (T %s)", hex);
     -+	}
     -+	if (ref->target != NULL) {
     -+		printf("=> %s", ref->target);
     ++	switch (ref->value_type) {
     ++	case REFTABLE_REF_SYMREF:
     ++		printf("=> %s", ref->value.symref);
     ++		break;
     ++	case REFTABLE_REF_VAL2:
     ++		hex_format(hex, ref->value.val2.value, hash_size(hash_id));
     ++		printf("val 2 %s", hex);
     ++		hex_format(hex, ref->value.val2.target_value,
     ++			   hash_size(hash_id));
     ++		printf("(T %s)", hex);
     ++		break;
     ++	case REFTABLE_REF_VAL1:
     ++		hex_format(hex, ref->value.val1, hash_size(hash_id));
     ++		printf("val 1 %s", hex);
     ++		break;
     ++	case REFTABLE_REF_DELETION:
     ++		printf("delete");
     ++		break;
      +	}
      +	printf("}\n");
      +}
     @@ reftable/record.c (new)
      +
      +void reftable_ref_record_release(struct reftable_ref_record *ref)
      +{
     ++	switch (ref->value_type) {
     ++	case REFTABLE_REF_SYMREF:
     ++		reftable_free(ref->value.symref);
     ++		break;
     ++	case REFTABLE_REF_VAL2:
     ++		reftable_free(ref->value.val2.target_value);
     ++		reftable_free(ref->value.val2.value);
     ++		break;
     ++	case REFTABLE_REF_VAL1:
     ++		reftable_free(ref->value.val1);
     ++		break;
     ++	case REFTABLE_REF_DELETION:
     ++		break;
     ++	default:
     ++		abort();
     ++	}
     ++
      +	reftable_free(ref->refname);
     -+	reftable_free(ref->target);
     -+	reftable_free(ref->target_value);
     -+	reftable_free(ref->value);
      +	memset(ref, 0, sizeof(struct reftable_ref_record));
      +}
      +
     @@ reftable/record.c (new)
      +{
      +	const struct reftable_ref_record *r =
      +		(const struct reftable_ref_record *)rec;
     -+	if (r->value != NULL) {
     -+		if (r->target_value != NULL) {
     -+			return 2;
     -+		} else {
     -+			return 1;
     -+		}
     -+	} else if (r->target != NULL)
     -+		return 3;
     -+	return 0;
     ++	return r->value_type;
      +}
      +
      +static int reftable_ref_record_encode(const void *rec, struct string_view s,
     @@ reftable/record.c (new)
      +		return -1;
      +	string_view_consume(&s, n);
      +
     -+	if (r->value != NULL) {
     -+		if (s.len < hash_size) {
     ++	switch (r->value_type) {
     ++	case REFTABLE_REF_SYMREF:
     ++		n = encode_string(r->value.symref, s);
     ++		if (n < 0) {
      +			return -1;
      +		}
     -+		memcpy(s.buf, r->value, hash_size);
     -+		string_view_consume(&s, hash_size);
     -+	}
     -+
     -+	if (r->target_value != NULL) {
     -+		if (s.len < hash_size) {
     ++		string_view_consume(&s, n);
     ++		break;
     ++	case REFTABLE_REF_VAL2:
     ++		if (s.len < 2 * hash_size) {
      +			return -1;
      +		}
     -+		memcpy(s.buf, r->target_value, hash_size);
     ++		memcpy(s.buf, r->value.val2.value, hash_size);
      +		string_view_consume(&s, hash_size);
     -+	}
     -+
     -+	if (r->target != NULL) {
     -+		int n = encode_string(r->target, s);
     -+		if (n < 0) {
     ++		memcpy(s.buf, r->value.val2.target_value, hash_size);
     ++		string_view_consume(&s, hash_size);
     ++		break;
     ++	case REFTABLE_REF_VAL1:
     ++		if (s.len < hash_size) {
      +			return -1;
      +		}
     -+		string_view_consume(&s, n);
     ++		memcpy(s.buf, r->value.val1, hash_size);
     ++		string_view_consume(&s, hash_size);
     ++		break;
     ++	case REFTABLE_REF_DELETION:
     ++		break;
     ++	default:
     ++		abort();
      +	}
      +
      +	return start.len - s.len;
     @@ reftable/record.c (new)
      +{
      +	struct reftable_ref_record *r = (struct reftable_ref_record *)rec;
      +	struct string_view start = in;
     -+	int seen_value = 0;
     -+	int seen_target_value = 0;
     -+	int seen_target = 0;
     -+
     -+	int n = get_var_int(&r->update_index, &in);
     ++	uint64_t update_index = 0;
     ++	int n = get_var_int(&update_index, &in);
      +	if (n < 0)
      +		return n;
     -+	assert(hash_size > 0);
     -+
      +	string_view_consume(&in, n);
      +
     ++	reftable_ref_record_release(r);
     ++
     ++	assert(hash_size > 0);
     ++
      +	r->refname = reftable_realloc(r->refname, key.len + 1);
      +	memcpy(r->refname, key.buf, key.len);
     ++	r->update_index = update_index;
      +	r->refname[key.len] = 0;
     -+
     ++	r->value_type = val_type;
      +	switch (val_type) {
     -+	case 1:
     -+	case 2:
     ++	case REFTABLE_REF_VAL1:
      +		if (in.len < hash_size) {
      +			return -1;
      +		}
      +
     -+		if (r->value == NULL) {
     -+			r->value = reftable_malloc(hash_size);
     -+		}
     -+		seen_value = 1;
     -+		memcpy(r->value, in.buf, hash_size);
     ++		r->value.val1 = reftable_malloc(hash_size);
     ++		memcpy(r->value.val1, in.buf, hash_size);
      +		string_view_consume(&in, hash_size);
     -+		if (val_type == 1) {
     -+			break;
     -+		}
     -+		if (r->target_value == NULL) {
     -+			r->target_value = reftable_malloc(hash_size);
     ++		break;
     ++
     ++	case REFTABLE_REF_VAL2:
     ++		if (in.len < 2 * hash_size) {
     ++			return -1;
      +		}
     -+		seen_target_value = 1;
     -+		memcpy(r->target_value, in.buf, hash_size);
     ++
     ++		r->value.val2.value = reftable_malloc(hash_size);
     ++		memcpy(r->value.val2.value, in.buf, hash_size);
     ++		string_view_consume(&in, hash_size);
     ++
     ++		r->value.val2.target_value = reftable_malloc(hash_size);
     ++		memcpy(r->value.val2.target_value, in.buf, hash_size);
      +		string_view_consume(&in, hash_size);
      +		break;
     -+	case 3: {
     ++
     ++	case REFTABLE_REF_SYMREF: {
      +		struct strbuf dest = STRBUF_INIT;
      +		int n = decode_string(&dest, in);
      +		if (n < 0) {
      +			return -1;
      +		}
      +		string_view_consume(&in, n);
     -+		seen_target = 1;
     -+		if (r->target != NULL) {
     -+			reftable_free(r->target);
     -+		}
     -+		r->target = dest.buf;
     ++		r->value.symref = dest.buf;
      +	} break;
      +
     -+	case 0:
     ++	case REFTABLE_REF_DELETION:
      +		break;
      +	default:
      +		abort();
      +		break;
      +	}
      +
     -+	if (!seen_target && r->target != NULL) {
     -+		FREE_AND_NULL(r->target);
     -+	}
     -+	if (!seen_target_value && r->target_value != NULL) {
     -+		FREE_AND_NULL(r->target_value);
     -+	}
     -+	if (!seen_value && r->value != NULL) {
     -+		FREE_AND_NULL(r->value);
     -+	}
     -+
      +	return start.len - in.len;
      +}
      +
     @@ reftable/record.c (new)
      +	return a == b;
      +}
      +
     -+static int str_equal(char *a, char *b)
     -+{
     -+	if (a != NULL && b != NULL)
     -+		return 0 == strcmp(a, b);
     -+
     -+	return a == b;
     -+}
     -+
      +int reftable_ref_record_equal(struct reftable_ref_record *a,
      +			      struct reftable_ref_record *b, int hash_size)
      +{
      +	assert(hash_size > 0);
     -+	return 0 == strcmp(a->refname, b->refname) &&
     -+	       a->update_index == b->update_index &&
     -+	       hash_equal(a->value, b->value, hash_size) &&
     -+	       hash_equal(a->target_value, b->target_value, hash_size) &&
     -+	       str_equal(a->target, b->target);
     ++	if (!(0 == strcmp(a->refname, b->refname) &&
     ++	      a->update_index == b->update_index &&
     ++	      a->value_type == b->value_type))
     ++		return 0;
     ++
     ++	switch (a->value_type) {
     ++	case REFTABLE_REF_SYMREF:
     ++		return !strcmp(a->value.symref, b->value.symref);
     ++	case REFTABLE_REF_VAL2:
     ++		return hash_equal(a->value.val2.value, b->value.val2.value,
     ++				  hash_size) &&
     ++		       hash_equal(a->value.val2.target_value,
     ++				  b->value.val2.target_value, hash_size);
     ++	case REFTABLE_REF_VAL1:
     ++		return hash_equal(a->value.val1, b->value.val1, hash_size);
     ++	case REFTABLE_REF_DELETION:
     ++		return 1;
     ++	default:
     ++		abort();
     ++	}
      +}
      +
      +int reftable_ref_record_compare_name(const void *a, const void *b)
     @@ reftable/record.c (new)
      +
      +int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref)
      +{
     -+	return ref->value == NULL && ref->target == NULL &&
     -+	       ref->target_value == NULL;
     ++	return ref->value_type == REFTABLE_REF_DELETION;
      +}
      +
      +int reftable_log_record_compare_key(const void *a, const void *b)
     @@ reftable/record.h (new)
      +#include "reftable-record.h"
      +
      +/*
     -+  A substring of existing string data. This structure takes no responsibility
     -+  for the lifetime of the data it points to.
     -+*/
     ++ * A substring of existing string data. This structure takes no responsibility
     ++ * for the lifetime of the data it points to.
     ++ */
      +struct string_view {
      +	uint8_t *buf;
      +	size_t len;
     @@ reftable/record.h (new)
      +struct reftable_record reftable_new_record(uint8_t typ);
      +
      +/* Encode `key` into `dest`. Sets `is_restart` to indicate a restart. Returns
     -+   number of bytes written. */
     ++ * number of bytes written. */
      +int reftable_encode_key(int *is_restart, struct string_view dest,
      +			struct strbuf prev_key, struct strbuf key,
      +			uint8_t extra);
     @@ reftable/record_test.c (new)
      +{
      +	int i = 0;
      +
     -+	for (i = 0; i <= 3; i++) {
     ++	for (i = REFTABLE_REF_DELETION; i < REFTABLE_NR_REF_VALUETYPES; i++) {
      +		struct reftable_ref_record in = { NULL };
     -+		struct reftable_ref_record out = {
     -+			.refname = xstrdup("old name"),
     -+			.value = reftable_calloc(SHA1_SIZE),
     -+			.target_value = reftable_calloc(SHA1_SIZE),
     -+			.target = xstrdup("old value"),
     -+		};
     ++		struct reftable_ref_record out = { NULL };
      +		struct reftable_record rec_out = { NULL };
      +		struct strbuf key = STRBUF_INIT;
      +		struct reftable_record rec = { NULL };
     @@ reftable/record_test.c (new)
      +
      +		int n, m;
      +
     ++		in.value_type = i;
      +		switch (i) {
     -+		case 0:
     ++		case REFTABLE_REF_DELETION:
      +			break;
     -+		case 1:
     -+			in.value = reftable_malloc(SHA1_SIZE);
     -+			set_hash(in.value, 1);
     ++		case REFTABLE_REF_VAL1:
     ++			in.value.val1 = reftable_malloc(SHA1_SIZE);
     ++			set_hash(in.value.val1, 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);
     ++		case REFTABLE_REF_VAL2:
     ++			in.value.val2.value = reftable_malloc(SHA1_SIZE);
     ++			set_hash(in.value.val2.value, 1);
     ++			in.value.val2.target_value = reftable_malloc(SHA1_SIZE);
     ++			set_hash(in.value.val2.target_value, 2);
      +			break;
     -+		case 3:
     -+			in.target = xstrdup("target");
     ++		case REFTABLE_REF_SYMREF:
     ++			in.value.symref = xstrdup("target");
      +			break;
      +		}
      +		in.refname = xstrdup("refs/heads/master");
     @@ reftable/record_test.c (new)
      +		m = reftable_record_decode(&rec_out, key, i, dest, SHA1_SIZE);
      +		EXPECT(n == m);
      +
     -+		EXPECT((out.value != NULL) == (in.value != NULL));
     -+		EXPECT((out.target_value != NULL) == (in.target_value != NULL));
     -+		EXPECT((out.target != NULL) == (in.target != NULL));
     ++		EXPECT(reftable_ref_record_equal(&in, &out, SHA1_SIZE));
      +		reftable_record_release(&rec_out);
      +
      +		strbuf_release(&key);
     @@ reftable/record_test.c (new)
      +
      +int record_test_main(int argc, const char *argv[])
      +{
     -+	test_reftable_log_record_equal();
     -+	test_reftable_log_record_roundtrip();
     -+	test_reftable_ref_record_roundtrip();
     -+	test_varint_roundtrip();
     -+	test_key_roundtrip();
     -+	test_common_prefix();
     -+	test_reftable_obj_record_roundtrip();
     -+	test_reftable_index_record_roundtrip();
     -+	test_u24_roundtrip();
     ++	RUN_TEST(test_reftable_log_record_equal);
     ++	RUN_TEST(test_reftable_log_record_roundtrip);
     ++	RUN_TEST(test_reftable_ref_record_roundtrip);
     ++	RUN_TEST(test_varint_roundtrip);
     ++	RUN_TEST(test_key_roundtrip);
     ++	RUN_TEST(test_common_prefix);
     ++	RUN_TEST(test_reftable_obj_record_roundtrip);
     ++	RUN_TEST(test_reftable_index_record_roundtrip);
     ++	RUN_TEST(test_u24_roundtrip);
      +	return 0;
      +}
      
     @@ reftable/reftable-record.h (new)
      +#include <stdint.h>
      +
      +/*
     -+ Basic data types
     -+
     -+ Reftables store the state of each ref in struct reftable_ref_record, and they
     -+ store a sequence of reflog updates in struct reftable_log_record.
     -+*/
     ++ * Basic data types
     ++ *
     ++ * Reftables store the state of each ref in struct reftable_ref_record, and they
     ++ * store a sequence of reflog updates in struct reftable_log_record.
     ++ */
      +
      +/* reftable_ref_record holds a ref database entry target_value */
      +struct reftable_ref_record {
      +	char *refname; /* Name of the ref, malloced. */
      +	uint64_t update_index; /* Logical timestamp at which this value is
     -+				  written */
     -+	uint8_t *value; /* SHA1, or NULL. malloced. */
     -+	uint8_t *target_value; /* peeled annotated tag, or NULL. malloced. */
     -+	char *target; /* symref, or NULL. malloced. */
     ++				* written */
     ++
     ++	enum {
     ++		/* tombstone to hide deletions from earlier tables */
     ++		REFTABLE_REF_DELETION = 0x0,
     ++
     ++		/* a simple ref */
     ++		REFTABLE_REF_VAL1 = 0x1,
     ++		/* a tag, plus its peeled hash */
     ++		REFTABLE_REF_VAL2 = 0x2,
     ++
     ++		/* a symbolic reference */
     ++		REFTABLE_REF_SYMREF = 0x3,
     ++#define REFTABLE_NR_REF_VALUETYPES 4
     ++	} value_type;
     ++	union {
     ++		uint8_t *val1; /* malloced hash. */
     ++		struct {
     ++			uint8_t *value; /* first value, malloced hash  */
     ++			uint8_t *target_value; /* second value, malloced hash */
     ++		} val2;
     ++		char *symref; /* referent, malloced 0-terminated string */
     ++	} value;
      +};
      +
     ++/* Returns the first hash, or NULL if `rec` is not of type
     ++ * REFTABLE_REF_VAL1 or REFTABLE_REF_VAL2. */
     ++uint8_t *reftable_ref_record_val1(struct reftable_ref_record *rec);
     ++
     ++/* Returns the second hash, or NULL if `rec` is not of type
     ++ * REFTABLE_REF_VAL2. */
     ++uint8_t *reftable_ref_record_val2(struct reftable_ref_record *rec);
     ++
      +/* returns whether 'ref' represents a deletion */
      +int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref);
      +
     -+/* prints a reftable_ref_record onto stdout */
     ++/* prints a reftable_ref_record onto stdout. Useful for debugging. */
      +void reftable_ref_record_print(struct reftable_ref_record *ref,
      +			       uint32_t hash_id);
      +
     -+/* frees and nulls all pointer values. */
     ++/* frees and nulls all pointer values inside `ref`. */
      +void reftable_ref_record_release(struct reftable_ref_record *ref);
      +
     -+/* returns whether two reftable_ref_records are the same */
     ++/* returns whether two reftable_ref_records are the same. Useful for testing. */
      +int reftable_ref_record_equal(struct reftable_ref_record *a,
      +			      struct reftable_ref_record *b, int hash_size);
      +
  8:  a358b052d56 !  7:  a48b9937642 reftable: reading/writing blocks
     @@ reftable/block.h (new)
      +#include "reftable-blocksource.h"
      +
      +/*
     -+  Writes reftable blocks. The block_writer is reused across blocks to minimize
     -+  allocation overhead.
     -+*/
     ++ * Writes reftable blocks. The block_writer is reused across blocks to minimize
     ++ * allocation overhead.
     ++ */
      +struct block_writer {
      +	uint8_t *buf;
      +	uint32_t block_size;
     @@ reftable/block.h (new)
      +};
      +
      +/*
     -+  initializes the blockwriter to write `typ` entries, using `buf` as temporary
     -+  storage. `buf` is not owned by the block_writer. */
     ++ * initializes the blockwriter to write `typ` entries, using `buf` as temporary
     ++ * storage. `buf` is not owned by the block_writer. */
      +void block_writer_init(struct block_writer *bw, uint8_t typ, uint8_t *buf,
      +		       uint32_t block_size, uint32_t header_off, int hash_size);
      +
     -+/*
     -+  returns the block type (eg. 'r' for ref records.
     -+*/
     ++/* returns the block type (eg. 'r' for ref records. */
      +uint8_t block_writer_type(struct block_writer *bw);
      +
      +/* appends the record, or -1 if it doesn't fit. */
     @@ reftable/block_test.c (new)
      +		memset(hash, i, sizeof(hash));
      +
      +		ref.refname = name;
     -+		ref.value = hash;
     ++		ref.value_type = REFTABLE_REF_VAL1;
     ++		ref.value.val1 = hash;
     ++
      +		names[i] = xstrdup(name);
      +		n = block_writer_add(&bw, &rec);
      +		ref.refname = NULL;
     -+		ref.value = NULL;
     ++		ref.value_type = REFTABLE_REF_DELETION;
      +		EXPECT(n == 0);
      +	}
      +
     @@ reftable/block_test.c (new)
      +
      +int block_test_main(int argc, const char *argv[])
      +{
     -+	test_block_read_write();
     ++	RUN_TEST(test_block_read_write);
      +	return 0;
      +}

9: 24afac9c91a ! 8: 6968dbc3828 reftable: a generic binary tree implementation

     @@ reftable/tree.h (new)
      +};
      +
      +/* looks for `key` in `rootp` using `compare` as comparison function. If insert
     -+   is set, insert the key if it's not found. Else, return NULL.
     -+*/
     ++ * is set, insert the key if it's not found. Else, return NULL.
     ++ */
      +struct tree_node *tree_search(void *key, struct tree_node **rootp,
      +			      int (*compare)(const void *, const void *),
      +			      int insert);
     @@ reftable/tree.h (new)
      +		void *arg);
      +
      +/*
     -+  deallocates the tree nodes recursively. Keys should be deallocated separately
     -+  by walking over the tree. */
     ++ * deallocates the tree nodes recursively. Keys should be deallocated separately
     ++ * by walking over the tree. */
      +void tree_free(struct tree_node *t);
      +
      +#endif
     @@ reftable/tree_test.c (new)
      +
      +int tree_test_main(int argc, const char *argv[])
      +{
     -+	test_tree();
     ++	RUN_TEST(test_tree);
      +	return 0;
      +}

10: 5f0b7c55925 ! 9: ff5b424d12f reftable: write reftable files

     @@ reftable/reftable-writer.h (new)
      +
      +#include "reftable-record.h"
      +
     -+/*
     -+ Writing single reftables
     -+*/
     ++/* Writing single reftables */
      +
      +/* reftable_write_options sets options for writing a single reftable. */
      +struct reftable_write_options {
     @@ reftable/writer.c (new)
      +
      +	reftable_record_from_ref(&rec, &copy);
      +	copy.update_index -= w->min_update_index;
     ++
      +	err = writer_add_record(w, &rec);
      +	if (err < 0)
      +		return err;
      +
     -+	if (!w->opts.skip_index_objects && ref->value != NULL) {
     ++	if (!w->opts.skip_index_objects &&
     ++	    reftable_ref_record_val1(ref) != NULL) {
      +		struct strbuf h = STRBUF_INIT;
     -+		strbuf_add(&h, (char *)ref->value, hash_size(w->opts.hash_id));
     ++		strbuf_add(&h, (char *)reftable_ref_record_val1(ref),
     ++			   hash_size(w->opts.hash_id));
      +		writer_index_hash(w, &h);
      +		strbuf_release(&h);
      +	}
      +
     -+	if (!w->opts.skip_index_objects && ref->target_value != NULL) {
     ++	if (!w->opts.skip_index_objects &&
     ++	    reftable_ref_record_val2(ref) != NULL) {
      +		struct strbuf h = STRBUF_INIT;
     -+		strbuf_add(&h, ref->target_value, hash_size(w->opts.hash_id));
     ++		strbuf_add(&h, reftable_ref_record_val2(ref),
     ++			   hash_size(w->opts.hash_id));
      +		writer_index_hash(w, &h);
      +		strbuf_release(&h);
      +	}
     @@ reftable/writer.h (new)
      +	size_t index_cap;
      +
      +	/*
     -+	  tree for use with tsearch; used to populate the 'o' inverse OID
     -+	  map */
     ++	 * tree for use with tsearch; used to populate the 'o' inverse OID
     ++	 * map */
      +	struct tree_node *obj_index_tree;
      +
      +	struct reftable_stats stats;
 11:  9aa2caade8c ! 10:  3c2de7dcc65 reftable: read reftable files
     @@ reftable/iter.c (new)
      +			}
      +		}
      +
     -+		if ((ref->target_value != NULL &&
     -+		     !memcmp(fri->oid.buf, ref->target_value, fri->oid.len)) ||
     -+		    (ref->value != NULL &&
     -+		     !memcmp(fri->oid.buf, ref->value, fri->oid.len))) {
     ++		if (ref->value_type == REFTABLE_REF_VAL2 &&
     ++		    (!memcmp(fri->oid.buf, ref->value.val2.target_value,
     ++			     fri->oid.len) ||
     ++		     !memcmp(fri->oid.buf, ref->value.val2.value,
     ++			     fri->oid.len)))
     ++			return 0;
     ++
     ++		if (ref->value_type == REFTABLE_REF_VAL1 &&
     ++		    !memcmp(fri->oid.buf, ref->value.val1, fri->oid.len)) {
      +			return 0;
      +		}
      +	}
     @@ reftable/iter.c (new)
      +			}
      +			continue;
      +		}
     -+
     -+		if (!memcmp(it->oid.buf, ref->target_value, it->oid.len) ||
     -+		    !memcmp(it->oid.buf, ref->value, it->oid.len)) {
     ++		/* BUG */
     ++		if (!memcmp(it->oid.buf, ref->value.val2.target_value,
     ++			    it->oid.len) ||
     ++		    !memcmp(it->oid.buf, ref->value.val2.value, it->oid.len)) {
      +			return 0;
      +		}
      +	}
     @@ reftable/iter.h (new)
      +int iterator_next(struct reftable_iterator *it, struct reftable_record *rec);
      +
      +/* Returns true for a zeroed out iterator, such as the one returned from
     -+   iterator_destroy. */
     ++ * iterator_destroy. */
      +int iterator_is_null(struct reftable_iterator *it);
      +
      +/* iterator that produces only ref records that point to `oid` */
     @@ reftable/iter.h (new)
      +					  struct filtering_ref_iterator *);
      +
      +/* iterator that produces only ref records that point to `oid`,
     -+   but using the object index.
     ++ * but using the object index.
      + */
      +struct indexed_table_ref_iter {
      +	struct reftable_reader *r;
     @@ reftable/reftable-iterator.h (new)
      +#include "reftable-record.h"
      +
      +/* iterator is the generic interface for walking over data stored in a
     -+   reftable.
     -+*/
     ++ * reftable.
     ++ */
      +struct reftable_iterator {
      +	struct reftable_iterator_vtable *ops;
      +	void *iter_arg;
      +};
      +
      +/* reads the next reftable_ref_record. Returns < 0 for error, 0 for OK and > 0:
     -+   end of iteration.
     -+*/
     ++ * end of iteration.
     ++ */
      +int reftable_iterator_next_ref(struct reftable_iterator *it,
      +			       struct reftable_ref_record *ref);
      +
      +/* reads the next reftable_log_record. Returns < 0 for error, 0 for OK and > 0:
     -+   end of iteration.
     -+*/
     ++ * end of iteration.
     ++ */
      +int reftable_iterator_next_log(struct reftable_iterator *it,
      +			       struct reftable_log_record *log);
      +
     @@ reftable/reftable-reader.h (new)
      +#include "reftable-blocksource.h"
      +
      +/*
     -+ Reading single tables
     -+
     -+ The follow routines are for reading single files. For an application-level
     -+ interface, skip ahead to struct reftable_merged_table and struct
     -+ reftable_stack.
     -+*/
     ++ * Reading single tables
     ++ *
     ++ * The follow routines are for reading single files. For an application-level
     ++ * interface, skip ahead to struct reftable_merged_table and struct
     ++ * reftable_stack.
     ++ */
      +
      +/* The reader struct is a handle to an open reftable file. */
      +struct reftable_reader;
 12:  581a4200d64 ! 11:  03681b820d1 reftable: reftable file level tests
     @@ reftable/reftable_test.c (new)
      +		snprintf(name, sizeof(name), "refs/heads/branch%02d", i);
      +
      +		ref.refname = name;
     -+		ref.value = hash;
      +		ref.update_index = update_index;
     ++		ref.value_type = REFTABLE_REF_VAL1;
     ++		ref.value.val1 = hash;
      +		(*names)[i] = xstrdup(name);
      +
      +		n = reftable_writer_add_ref(w, &ref);
     @@ reftable/reftable_test.c (new)
      +		err = reftable_iterator_next_ref(&it, &ref);
      +		EXPECT_ERR(err);
      +		EXPECT(0 == strcmp(names[i], ref.refname));
     -+		EXPECT(i == ref.value[0]);
     ++		EXPECT(REFTABLE_REF_VAL1 == ref.value_type);
     ++		EXPECT(i == ref.value.val1[0]);
      +
      +		reftable_ref_record_release(&ref);
      +		reftable_iterator_destroy(&it);
     @@ reftable/reftable_test.c (new)
      +
      +		set_test_hash(hash1, i / 4);
      +		set_test_hash(hash2, 3 + i / 4);
     -+		ref.value = hash1;
     -+		ref.target_value = hash2;
     ++		ref.value_type = REFTABLE_REF_VAL2;
     ++		ref.value.val2.value = hash1;
     ++		ref.value.val2.target_value = hash2;
      +
      +		/* 80 bytes / entry, so 3 entries per block. Yields 17
      +		 */
     @@ reftable/reftable_test.c (new)
      +
      +int reftable_test_main(int argc, const char *argv[])
      +{
     -+	test_log_write_read();
     -+	test_table_read_write_seek_linear_sha256();
     -+	test_log_buffer_size();
     -+	test_table_write_small_table();
     -+	test_buffer();
     -+	test_table_read_api();
     -+	test_table_read_write_sequential();
     -+	test_table_read_write_seek_linear();
     -+	test_table_read_write_seek_index();
     -+	test_table_refs_for_no_index();
     -+	test_table_refs_for_obj_index();
     -+	test_table_empty();
     ++	RUN_TEST(test_log_write_read);
     ++	RUN_TEST(test_table_read_write_seek_linear_sha256);
     ++	RUN_TEST(test_log_buffer_size);
     ++	RUN_TEST(test_table_write_small_table);
     ++	RUN_TEST(test_buffer);
     ++	RUN_TEST(test_table_read_api);
     ++	RUN_TEST(test_table_read_write_sequential);
     ++	RUN_TEST(test_table_read_write_seek_linear);
     ++	RUN_TEST(test_table_read_write_seek_index);
     ++	RUN_TEST(test_table_refs_for_no_index);
     ++	RUN_TEST(test_table_refs_for_obj_index);
     ++	RUN_TEST(test_table_empty);
      +	return 0;
      +}

13: a26fb180add ! 12: 557183d3e3e reftable: rest of library

     @@ Makefile: REFTABLE_OBJS += reftable/error.o
      
       ## reftable/VERSION (new) ##
      @@
     -+b8ec0f74c74cb6752eb2033ad8e755a9c19aad15 C: add missing header
     ++9b4a54059db9a05c270c0a0587f245bc6868d576 C: use rand() rather than cobbled together random generator.
      
       ## reftable/dump.c (new) ##
      @@
     @@ reftable/merged_test.c (new)
      +	struct reftable_ref_record r1[] = { {
      +		.refname = "b",
      +		.update_index = 1,
     -+		.value = hash1,
     ++		.value_type = REFTABLE_REF_VAL1,
     ++		.value.val1 = hash1,
      +	} };
      +	struct reftable_ref_record r2[] = { {
      +		.refname = "a",
      +		.update_index = 2,
     ++		.value_type = REFTABLE_REF_DELETION,
      +	} };
      +
      +	struct reftable_ref_record *refs[] = { r1, r2 };
     @@ reftable/merged_test.c (new)
      +{
      +	uint8_t hash1[SHA1_SIZE] = { 1 };
      +	uint8_t hash2[SHA1_SIZE] = { 2 };
     -+	struct reftable_ref_record r1[] = { {
     -+						    .refname = "a",
     -+						    .update_index = 1,
     -+						    .value = hash1,
     -+					    },
     -+					    {
     -+						    .refname = "b",
     -+						    .update_index = 1,
     -+						    .value = hash1,
     -+					    },
     -+					    {
     -+						    .refname = "c",
     -+						    .update_index = 1,
     -+						    .value = hash1,
     -+					    } };
     ++	struct reftable_ref_record r1[] = {
     ++		{
     ++			.refname = "a",
     ++			.update_index = 1,
     ++			.value_type = REFTABLE_REF_VAL1,
     ++			.value.val1 = hash1,
     ++		},
     ++		{
     ++			.refname = "b",
     ++			.update_index = 1,
     ++			.value_type = REFTABLE_REF_VAL1,
     ++			.value.val1 = hash1,
     ++		},
     ++		{
     ++			.refname = "c",
     ++			.update_index = 1,
     ++			.value_type = REFTABLE_REF_VAL1,
     ++			.value.val1 = hash1,
     ++		}
     ++	};
      +	struct reftable_ref_record r2[] = { {
      +		.refname = "a",
      +		.update_index = 2,
     ++		.value_type = REFTABLE_REF_DELETION,
      +	} };
      +	struct reftable_ref_record r3[] = {
      +		{
      +			.refname = "c",
      +			.update_index = 3,
     -+			.value = hash2,
     ++			.value_type = REFTABLE_REF_VAL1,
     ++			.value.val1 = hash2,
      +		},
      +		{
      +			.refname = "d",
      +			.update_index = 3,
     -+			.value = hash1,
     ++			.value_type = REFTABLE_REF_VAL1,
     ++			.value.val1 = hash1,
      +		},
      +	};
      +
     @@ reftable/merged_test.c (new)
      +
      +int merged_test_main(int argc, const char *argv[])
      +{
     -+	test_merged_between();
     -+	test_pq();
     -+	test_merged();
     -+	test_default_write_opts();
     ++	RUN_TEST(test_merged_between);
     ++	RUN_TEST(test_pq);
     ++	RUN_TEST(test_merged);
     ++	RUN_TEST(test_default_write_opts);
      +	return 0;
      +}
      
     @@ reftable/refname_test.c (new)
      +		reftable_new_writer(&strbuf_add_void, &buf, &opts);
      +	struct reftable_ref_record rec = {
      +		.refname = "a/b",
     -+		.target = "destination", /* make sure it's not a symref. */
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "destination", /* make sure it's not a symref.
     ++						*/
      +		.update_index = 1,
      +	};
      +	int err;
     @@ reftable/refname_test.c (new)
      +
      +int refname_test_main(int argc, const char *argv[])
      +{
     -+	test_conflict();
     ++	RUN_TEST(test_conflict);
      +	return 0;
      +}
      
     @@ reftable/reftable-generic.h (new)
      +#include "reftable-merged.h"
      +
      +/*
     -+ Provides a unified API for reading tables, either merged tables, or single
     -+ readers.
     -+*/
     ++ * Provides a unified API for reading tables, either merged tables, or single
     ++ * readers. */
      +struct reftable_table {
      +	struct reftable_table_vtable *ops;
      +	void *table_arg;
     @@ reftable/reftable-merged.h (new)
      +#include "reftable-iterator.h"
      +
      +/*
     -+ Merged tables
     -+
     -+ A ref database kept in a sequence of table files. The merged_table presents a
     -+ unified view to reading (seeking, iterating) a sequence of immutable tables.
     -+
     -+ The merged tables are on purpose kept disconnected from their actual storage
     -+ (eg. files on disk), because it is useful to merge tables aren't files. For
     -+ example, the per-workspace and global ref namespace can be implemented as a
     -+ merged table of two stacks of file-backed reftables.
     -+*/
     ++ * Merged tables
     ++ *
     ++ * A ref database kept in a sequence of table files. The merged_table presents a
     ++ * unified view to reading (seeking, iterating) a sequence of immutable tables.
     ++ *
     ++ * The merged tables are on purpose kept disconnected from their actual storage
     ++ * (eg. files on disk), because it is useful to merge tables aren't files. For
     ++ * example, the per-workspace and global ref namespace can be implemented as a
     ++ * merged table of two stacks of file-backed reftables.
     ++ */
      +
      +/* A merged table is implements seeking/iterating over a stack of tables. */
      +struct reftable_merged_table;
     @@ reftable/reftable-stack.h (new)
      +#include "reftable-writer.h"
      +
      +/*
     -+  The stack presents an interface to a mutable sequence of reftables.
     ++ * The stack presents an interface to a mutable sequence of reftables.
      +
     -+  A stack can be mutated by pushing a table to the top of the stack.
     ++ * A stack can be mutated by pushing a table to the top of the stack.
      +
     -+  The reftable_stack automatically compacts files on disk to ensure good
     -+  amortized performance.
     -+*/
     ++ * The reftable_stack automatically compacts files on disk to ensure good
     ++ * amortized performance.
     ++ *
     ++ * For windows and other platforms that cannot have open files as rename
     ++ * destinations, concurrent access from multiple processes needs the rand()
     ++ * random seed to be randomized.
     ++ */
      +struct reftable_stack;
      +
      +/* open a new reftable stack. The tables along with the table list will be
     -+   stored in 'dir'. Typically, this should be .git/reftables.
     -+*/
     ++ *  stored in 'dir'. Typically, this should be .git/reftables.
     ++ */
      +int reftable_new_stack(struct reftable_stack **dest, const char *dir,
      +		       struct reftable_write_options config);
      +
     @@ reftable/reftable-stack.h (new)
      +struct reftable_addition;
      +
      +/*
     -+  returns a new transaction to add reftables to the given stack. As a side
     -+  effect, the ref database is locked.
     -+*/
     ++ * returns a new transaction to add reftables to the given stack. As a side
     ++ * effect, the ref database is locked.
     ++ */
      +int reftable_stack_new_addition(struct reftable_addition **dest,
      +				struct reftable_stack *st);
      +
     @@ reftable/reftable-stack.h (new)
      +int reftable_addition_commit(struct reftable_addition *add);
      +
      +/* Release all non-committed data from the transaction, and deallocate the
     -+   transaction. Releases the lock if held. */
     ++ * transaction. Releases the lock if held. */
      +void reftable_addition_destroy(struct reftable_addition *add);
      +
      +/* add a new table to the stack. The write_table function must call
     -+   reftable_writer_set_limits, add refs and return an error value. */
     ++ * reftable_writer_set_limits, add refs and return an error value. */
      +int reftable_stack_add(struct reftable_stack *st,
      +		       int (*write_table)(struct reftable_writer *wr,
      +					  void *write_arg),
      +		       void *write_arg);
      +
      +/* returns the merged_table for seeking. This table is valid until the
     -+   next write or reload, and should not be closed or deleted.
     -+*/
     ++ * next write or reload, and should not be closed or deleted.
     ++ */
      +struct reftable_merged_table *
      +reftable_stack_merged_table(struct reftable_stack *st);
      +
     @@ reftable/reftable-stack.h (new)
      +/* heuristically compact unbalanced table stack. */
      +int reftable_stack_auto_compact(struct reftable_stack *st);
      +
     -+/* convenience function to read a single ref. Returns < 0 for error, 0
     -+   for success, and 1 if ref not found. */
     ++/* convenience function to read a single ref. Returns < 0 for error, 0 for
     ++ * success, and 1 if ref not found. */
      +int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
      +			    struct reftable_ref_record *ref);
      +
     -+/* convenience function to read a single log. Returns < 0 for error, 0
     -+   for success, and 1 if ref not found. */
     ++/* convenience function to read a single log. Returns < 0 for error, 0 for
     ++ * success, and 1 if ref not found. */
      +int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
      +			    struct reftable_log_record *log);
      +
     @@ reftable/stack.c (new)
      +static void format_name(struct strbuf *dest, uint64_t min, uint64_t max)
      +{
      +	char buf[100];
     -+	snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64, min, max);
     ++	uint32_t rnd = (uint32_t)rand();
     ++	snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64 "-%08x",
     ++		 min, max, rnd);
      +	strbuf_reset(dest);
      +	strbuf_addstr(dest, buf);
      +}
     @@ reftable/stack.c (new)
      +	int lock_file_fd;
      +	struct strbuf lock_file_name;
      +	struct reftable_stack *stack;
     -+	char **names;
     ++
      +	char **new_tables;
      +	int new_tables_len;
      +	uint64_t next_update_index;
     @@ reftable/stack.c (new)
      +	struct strbuf nm = STRBUF_INIT;
      +	for (i = 0; i < add->new_tables_len; i++) {
      +		strbuf_reset(&nm);
     -+		strbuf_addstr(&nm, add->stack->list_file);
     ++		strbuf_addstr(&nm, add->stack->reftable_dir);
      +		strbuf_addstr(&nm, "/");
      +		strbuf_addstr(&nm, add->new_tables[i]);
      +		unlink(nm.buf);
     @@ reftable/stack.c (new)
      +		strbuf_release(&add->lock_file_name);
      +	}
      +
     -+	free_names(add->names);
     -+	add->names = NULL;
      +	strbuf_release(&nm);
      +}
      +
     @@ reftable/stack.c (new)
      +		goto done;
      +	}
      +
     -+	err = reftable_stack_reload(add->stack);
     ++	/* success, no more state to clean up. */
     ++	strbuf_release(&add->lock_file_name);
     ++	for (i = 0; i < add->new_tables_len; i++) {
     ++		reftable_free(add->new_tables[i]);
     ++	}
     ++	reftable_free(add->new_tables);
     ++	add->new_tables = NULL;
     ++	add->new_tables_len = 0;
      +
     ++	err = reftable_stack_reload(add->stack);
      +done:
      +	reftable_addition_close(add);
      +	return err;
     @@ reftable/stack.c (new)
      +	strbuf_addstr(&tab_file_name, "/");
      +	strbuf_addbuf(&tab_file_name, &next_name);
      +
     -+	/* TODO: should check destination out of paranoia */
     ++	/*
     ++	  On windows, this relies on rand() picking a unique destination name.
     ++	  Maybe we should do retry loop as well?
     ++	 */
      +	err = rename(temp_tab_file_name.buf, tab_file_name.buf);
      +	if (err < 0) {
      +		err = REFTABLE_IO_ERROR;
     @@ reftable/stack.c (new)
      +
      +	format_name(&next_name,
      +		    reftable_reader_min_update_index(st->readers[first]),
     -+		    reftable_reader_max_update_index(st->readers[first]));
     ++		    reftable_reader_max_update_index(st->readers[last]));
      +
      +	strbuf_reset(temp_tab);
      +	strbuf_addstr(temp_tab, st->reftable_dir);
     @@ reftable/stack.c (new)
      +		if (err < 0) {
      +			break;
      +		}
     ++
      +		if (first == 0 && reftable_ref_record_is_deletion(&ref)) {
      +			continue;
      +		}
     @@ reftable/stack.c (new)
      +	strbuf_addbuf(&new_table_path, &new_table_name);
      +
      +	if (!is_empty_table) {
     ++		/* retry? */
      +		err = rename(temp_tab_file_name.buf, new_table_path.buf);
      +		if (err < 0) {
      +			err = REFTABLE_IO_ERROR;
     @@ reftable/stack_test.c (new)
      +	strbuf_release(&path);
      +}
      +
     ++static char *get_tmp_template(const char *prefix)
     ++{
     ++	const char *tmp = getenv("TMPDIR");
     ++	static char template[1024];
     ++	snprintf(template, sizeof(template) - 1, "%s/%s.XXXXXX",
     ++		 tmp ? tmp : "/tmp", prefix);
     ++	return template;
     ++}
     ++
      +static void test_read_file(void)
      +{
     -+	char fn[256] = "/tmp/stack.test_read_file.XXXXXX";
     ++	char *fn = get_tmp_template(__FUNCTION__);
      +	int fd = mkstemp(fn);
      +	char out[1024] = "line1\n\nline2\nline3";
      +	int n, err;
     @@ reftable/stack_test.c (new)
      +
      +static void test_reftable_stack_add_one(void)
      +{
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
      +	struct reftable_ref_record ref = {
      +		.refname = "HEAD",
      +		.update_index = 1,
     -+		.target = "master",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "master",
      +	};
      +	struct reftable_ref_record dest = { NULL };
      +
     @@ reftable/stack_test.c (new)
      +
      +	err = reftable_stack_read_ref(st, ref.refname, &dest);
      +	EXPECT_ERR(err);
     -+	EXPECT(0 == strcmp("master", dest.target));
     ++	EXPECT(0 == strcmp("master", dest.value.symref));
      +
      +	reftable_ref_record_release(&dest);
      +	reftable_stack_destroy(st);
     @@ reftable/stack_test.c (new)
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st1 = NULL;
      +	struct reftable_stack *st2 = NULL;
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	int err;
      +	struct reftable_ref_record ref1 = {
      +		.refname = "HEAD",
      +		.update_index = 1,
     -+		.target = "master",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "master",
      +	};
      +	struct reftable_ref_record ref2 = {
      +		.refname = "branch2",
      +		.update_index = 2,
     -+		.target = "master",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "master",
      +	};
      +
      +	EXPECT(mkdtemp(dir));
      +
     ++	/* simulate multi-process access to the same stack
     ++	   by creating two stacks for the same directory.
     ++	 */
      +	err = reftable_new_stack(&st1, dir, cfg);
      +	EXPECT_ERR(err);
      +
     @@ reftable/stack_test.c (new)
      +
      +static void test_reftable_stack_transaction_api(void)
      +{
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
     @@ reftable/stack_test.c (new)
      +	struct reftable_ref_record ref = {
      +		.refname = "HEAD",
      +		.update_index = 1,
     -+		.target = "master",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "master",
      +	};
      +	struct reftable_ref_record dest = { NULL };
      +
     @@ reftable/stack_test.c (new)
      +
      +	err = reftable_stack_read_ref(st, ref.refname, &dest);
      +	EXPECT_ERR(err);
     -+	EXPECT(0 == strcmp("master", dest.target));
     ++	EXPECT(REFTABLE_REF_SYMREF == dest.value_type);
     ++	EXPECT(0 == strcmp("master", dest.value.symref));
      +
      +	reftable_ref_record_release(&dest);
      +	reftable_stack_destroy(st);
     @@ reftable/stack_test.c (new)
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	int i;
      +	struct reftable_ref_record ref = {
      +		.refname = "a/b",
      +		.update_index = 1,
     -+		.target = "master",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "master",
      +	};
      +	char *additions[] = { "a", "a/b/c" };
      +
     @@ reftable/stack_test.c (new)
      +		struct reftable_ref_record ref = {
      +			.refname = additions[i],
      +			.update_index = 1,
     -+			.target = "master",
     ++			.value_type = REFTABLE_REF_SYMREF,
     ++			.value.symref = "master",
      +		};
      +
      +		err = reftable_stack_add(st, &write_test_ref, &ref);
     @@ reftable/stack_test.c (new)
      +
      +static void test_reftable_stack_update_index_check(void)
      +{
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
      +	struct reftable_ref_record ref1 = {
      +		.refname = "name1",
      +		.update_index = 1,
     -+		.target = "master",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "master",
      +	};
      +	struct reftable_ref_record ref2 = {
      +		.refname = "name2",
      +		.update_index = 1,
     -+		.target = "master",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "master",
      +	};
      +	EXPECT(mkdtemp(dir));
      +
     @@ reftable/stack_test.c (new)
      +
      +static void test_reftable_stack_lock_failure(void)
      +{
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err, i;
     @@ reftable/stack_test.c (new)
      +		.exact_log_message = 1,
      +	};
      +	struct reftable_stack *st = NULL;
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_ref_record refs[2] = { { NULL } };
      +	struct reftable_log_record logs[2] = { { NULL } };
      +	int N = ARRAY_SIZE(refs);
     @@ reftable/stack_test.c (new)
      +		char buf[256];
      +		snprintf(buf, sizeof(buf), "branch%02d", i);
      +		refs[i].refname = xstrdup(buf);
     -+		refs[i].value = reftable_malloc(SHA1_SIZE);
      +		refs[i].update_index = i + 1;
     -+		set_test_hash(refs[i].value, i);
     ++		refs[i].value_type = REFTABLE_REF_VAL1;
     ++		refs[i].value.val1 = reftable_malloc(SHA1_SIZE);
     ++		set_test_hash(refs[i].value.val1, i);
      +
      +		logs[i].refname = xstrdup(buf);
      +		logs[i].update_index = N + i + 1;
     @@ reftable/stack_test.c (new)
      +		0,
      +	};
      +	struct reftable_stack *st = NULL;
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +
      +	uint8_t h1[SHA1_SIZE] = { 0x01 }, h2[SHA1_SIZE] = { 0x02 };
      +
     @@ reftable/stack_test.c (new)
      +static void test_reftable_stack_tombstone(void)
      +{
      +	int i = 0;
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
     @@ reftable/stack_test.c (new)
      +		refs[i].refname = 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);
     ++			refs[i].value_type = REFTABLE_REF_VAL1;
     ++			refs[i].value.val1 = reftable_malloc(SHA1_SIZE);
     ++			set_test_hash(refs[i].value.val1, i);
      +		}
      +		logs[i].refname = xstrdup(buf);
      +		/* update_index is part of the key. */
     @@ reftable/stack_test.c (new)
      +
      +static void test_reftable_stack_hash_id(void)
      +{
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
      +
      +	struct reftable_ref_record ref = {
      +		.refname = "master",
     -+		.target = "target",
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = "target",
      +		.update_index = 1,
      +	};
      +	struct reftable_write_options cfg32 = { .hash_id = SHA256_ID };
     @@ reftable/stack_test.c (new)
      +	err = reftable_stack_read_ref(st_default, "master", &dest);
      +	EXPECT_ERR(err);
      +
     -+	EXPECT(!strcmp(dest.target, ref.target));
     ++	EXPECT(reftable_ref_record_equal(&ref, &dest, SHA1_SIZE));
      +	reftable_ref_record_release(&dest);
      +	reftable_stack_destroy(st);
      +	reftable_stack_destroy(st_default);
     @@ reftable/stack_test.c (new)
      +
      +static void test_sizes_to_segments_empty(void)
      +{
     -+	uint64_t sizes[0];
     -+
      +	int seglen = 0;
     -+	struct segment *segs =
     -+		sizes_to_segments(&seglen, sizes, ARRAY_SIZE(sizes));
     ++	struct segment *segs = sizes_to_segments(&seglen, NULL, 0);
      +	EXPECT(seglen == 0);
      +	reftable_free(segs);
      +}
     @@ reftable/stack_test.c (new)
      +
      +static void test_reflog_expire(void)
      +{
     -+	char dir[256] = "/tmp/stack.test_reflog_expire.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	struct reftable_log_record logs[20] = { { NULL } };
     @@ reftable/stack_test.c (new)
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	struct reftable_stack *st2 = NULL;
      +
      +	EXPECT(mkdtemp(dir));
     @@ reftable/stack_test.c (new)
      +{
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
     -+	char dir[256] = "/tmp/stack_test.XXXXXX";
     ++	char *dir = get_tmp_template(__FUNCTION__);
      +	int err, i;
      +	int N = 100;
      +	EXPECT(mkdtemp(dir));
     @@ reftable/stack_test.c (new)
      +		struct reftable_ref_record ref = {
      +			.refname = name,
      +			.update_index = reftable_stack_next_update_index(st),
     -+			.target = "master",
     ++			.value_type = REFTABLE_REF_SYMREF,
     ++			.value.symref = "master",
      +		};
      +		snprintf(name, sizeof(name), "branch%04d", i);
      +
     @@ reftable/stack_test.c (new)
      +
      +int stack_test_main(int argc, const char *argv[])
      +{
     -+	test_reftable_stack_uptodate();
     -+	test_reftable_stack_transaction_api();
     -+	test_reftable_stack_hash_id();
     -+	test_sizes_to_segments_all_equal();
     -+	test_reftable_stack_auto_compaction();
     -+	test_reftable_stack_validate_refname();
     -+	test_reftable_stack_update_index_check();
     -+	test_reftable_stack_lock_failure();
     -+	test_reftable_stack_log_normalize();
     -+	test_reftable_stack_tombstone();
     -+	test_reftable_stack_add_one();
     -+	test_empty_add();
     -+	test_reflog_expire();
     -+	test_suggest_compaction_segment();
     -+	test_suggest_compaction_segment_nothing();
     -+	test_sizes_to_segments();
     -+	test_sizes_to_segments_empty();
     -+	test_log2();
     -+	test_parse_names();
     -+	test_read_file();
     -+	test_names_equal();
     -+	test_reftable_stack_add();
     ++	RUN_TEST(test_reftable_stack_uptodate);
     ++	RUN_TEST(test_reftable_stack_transaction_api);
     ++	RUN_TEST(test_reftable_stack_hash_id);
     ++	RUN_TEST(test_sizes_to_segments_all_equal);
     ++	RUN_TEST(test_reftable_stack_auto_compaction);
     ++	RUN_TEST(test_reftable_stack_validate_refname);
     ++	RUN_TEST(test_reftable_stack_update_index_check);
     ++	RUN_TEST(test_reftable_stack_lock_failure);
     ++	RUN_TEST(test_reftable_stack_log_normalize);
     ++	RUN_TEST(test_reftable_stack_tombstone);
     ++	RUN_TEST(test_reftable_stack_add_one);
     ++	RUN_TEST(test_empty_add);
     ++	RUN_TEST(test_reflog_expire);
     ++	RUN_TEST(test_suggest_compaction_segment);
     ++	RUN_TEST(test_suggest_compaction_segment_nothing);
     ++	RUN_TEST(test_sizes_to_segments);
     ++	RUN_TEST(test_sizes_to_segments_empty);
     ++	RUN_TEST(test_log2);
     ++	RUN_TEST(test_parse_names);
     ++	RUN_TEST(test_read_file);
     ++	RUN_TEST(test_names_equal);
     ++	RUN_TEST(test_reftable_stack_add);
      +	return 0;
      +}

14: a590865a700 ! 13: d57023d9f13 Reftable support for git-core

     @@ Commit message
          Helped-by: Johannes Schindelin <[email protected]>
          Co-authored-by: Jeff King <[email protected]>
      
     + ## Documentation/config/extensions.txt ##
     +@@ Documentation/config/extensions.txt: extensions.objectFormat::
     + Note that this setting should only be set by linkgit:git-init[1] or
     + linkgit:git-clone[1].  Trying to change it after initialization will not
     + work and will produce hard-to-diagnose issues.
     +++
     ++extensions.refStorage::
     ++	Specify the ref storage mechanism to use.  The acceptable values are `files` and
     ++	`reftable`.  If not specified, `files` is assumed.  It is an error to specify
     ++	this key unless `core.repositoryFormatVersion` is 1.
     +++
     ++Note that this setting should only be set by linkgit:git-init[1] or
     ++linkgit:git-clone[1].  Trying to change it after initialization will not
     ++work and will produce hard-to-diagnose issues.
     +
       ## Documentation/technical/repository-version.txt ##
      @@ Documentation/technical/repository-version.txt: If set, by default "git config" reads from both "config" and
       multiple working directory mode, "config" file is shared while
     @@ refs/reftable-backend.c (new)
      +			continue;
      +
      +		ri->base.flags = 0;
     -+		if (ri->ref.value != NULL) {
     -+			hashcpy(ri->oid.hash, ri->ref.value);
     -+		} else if (ri->ref.target != NULL) {
     ++		switch (ri->ref.value_type) {
     ++		case REFTABLE_REF_VAL1:
     ++			hashcpy(ri->oid.hash, ri->ref.value.val1);
     ++			break;
     ++		case REFTABLE_REF_VAL2:
     ++			hashcpy(ri->oid.hash, ri->ref.value.val2.value);
     ++			break;
     ++		case REFTABLE_REF_SYMREF: {
      +			int out_flags = 0;
      +			const char *resolved = refs_resolve_ref_unsafe(
      +				ri->ref_store, ri->ref.refname,
     @@ refs/reftable-backend.c (new)
      +			    (ri->base.flags & REF_ISBROKEN)) {
      +				continue;
      +			}
     ++			break;
     ++		}
     ++		default:
     ++			abort();
      +		}
      +
      +		ri->base.oid = &ri->oid;
     @@ refs/reftable-backend.c (new)
      +{
      +	struct git_reftable_iterator *ri =
      +		(struct git_reftable_iterator *)ref_iterator;
     -+	if (ri->ref.target_value != NULL) {
     -+		hashcpy(peeled->hash, ri->ref.target_value);
     ++	if (ri->ref.value_type == REFTABLE_REF_VAL2) {
     ++		hashcpy(peeled->hash, ri->ref.value.val2.target_value);
      +		return 0;
      +	}
      +
     @@ refs/reftable-backend.c (new)
      +
      +			int peel_error = peel_object(&u->new_oid, &peeled);
      +			ref.refname = (char *)u->refname;
     -+
     -+			if (!is_null_oid(&u->new_oid)) {
     -+				ref.value = u->new_oid.hash;
     -+			}
      +			ref.update_index = ts;
     ++
      +			if (!peel_error) {
     -+				ref.target_value = peeled.hash;
     ++				ref.value_type = REFTABLE_REF_VAL2;
     ++				ref.value.val2.target_value = peeled.hash;
     ++				ref.value.val2.value = u->new_oid.hash;
     ++			} else if (!is_null_oid(&u->new_oid)) {
     ++				ref.value_type = REFTABLE_REF_VAL1;
     ++				ref.value.val1 = u->new_oid.hash;
      +			}
      +
      +			err = reftable_writer_add_ref(writer, &ref);
     @@ refs/reftable-backend.c (new)
      +	for (i = 0; i < arg->refnames->nr; i++) {
      +		struct reftable_ref_record ref = {
      +			.refname = (char *)arg->refnames->items[i].string,
     ++			.value_type = REFTABLE_REF_DELETION,
      +			.update_index = ts,
      +		};
      +		err = reftable_writer_add_ref(writer, &ref);
     @@ refs/reftable-backend.c (new)
      +
      +		if (reftable_stack_read_ref(arg->stack, log.refname,
      +					    &current) == 0) {
     -+			log.old_hash = current.value;
     ++			log.old_hash = reftable_ref_record_val1(&current);
      +		}
      +		err = reftable_writer_add_log(writer, &log);
      +		log.old_hash = NULL;
     @@ refs/reftable-backend.c (new)
      +
      +	struct reftable_ref_record ref = {
      +		.refname = (char *)create->refname,
     -+		.target = (char *)create->target,
     ++		.value_type = REFTABLE_REF_SYMREF,
     ++		.value.symref = (char *)create->target,
      +		.update_index = ts,
      +	};
      +	reftable_writer_set_limits(writer, ts, ts);
     @@ refs/reftable-backend.c (new)
      +		goto done;
      +	}
      +
     -+	free(ref.refname);
     -+	ref.refname = strdup(arg->newname);
      +	reftable_writer_set_limits(writer, ts, ts);
     -+	ref.update_index = ts;
      +
      +	{
     -+		struct reftable_ref_record todo[2] = { { NULL } };
     -+		todo[0].refname = (char *)arg->oldname;
     -+		todo[0].update_index = ts;
     -+		/* leave todo[0] empty */
     -+		todo[1] = ref;
     ++		struct reftable_ref_record todo[2] = {
     ++			{
     ++				.refname = (char *)arg->oldname,
     ++				.update_index = ts,
     ++				.value_type = REFTABLE_REF_DELETION,
     ++			},
     ++			ref,
     ++		};
      +		todo[1].update_index = ts;
     ++		free(todo[1].refname);
     ++		todo[1].refname = strdup(arg->newname);
      +
      +		err = reftable_writer_add_refs(writer, todo, 2);
      +		if (err < 0) {
     @@ refs/reftable-backend.c (new)
      +		}
      +	}
      +
     -+	if (ref.value != NULL) {
     ++	if (reftable_ref_record_val1(&ref)) {
     ++		uint8_t *val1 = reftable_ref_record_val1(&ref);
      +		struct reftable_log_record todo[2] = { { NULL } };
      +		fill_reftable_log_record(&todo[0]);
      +		fill_reftable_log_record(&todo[1]);
     @@ refs/reftable-backend.c (new)
      +		todo[0].refname = (char *)arg->oldname;
      +		todo[0].update_index = ts;
      +		todo[0].message = (char *)arg->logmsg;
     -+		todo[0].old_hash = ref.value;
     ++		todo[0].old_hash = val1;
      +		todo[0].new_hash = NULL;
      +
      +		todo[1].refname = (char *)arg->newname;
      +		todo[1].update_index = ts;
      +		todo[1].old_hash = NULL;
     -+		todo[1].new_hash = ref.value;
     ++		todo[1].new_hash = val1;
      +		todo[1].message = (char *)arg->logmsg;
      +
      +		err = reftable_writer_add_logs(writer, todo, 2);
     @@ refs/reftable-backend.c (new)
      +		err = -1;
      +		goto done;
      +	}
     -+	if (ref.target != NULL) {
     ++
     ++	if (ref.value_type == REFTABLE_REF_SYMREF) {
      +		strbuf_reset(referent);
     -+		strbuf_addstr(referent, ref.target);
     ++		strbuf_addstr(referent, ref.value.symref);
      +		*type |= REF_ISSYMREF;
     -+	} else if (ref.value != NULL) {
     -+		hashcpy(oid->hash, ref.value);
     ++	} else if (reftable_ref_record_val1(&ref) != NULL) {
     ++		hashcpy(oid->hash, reftable_ref_record_val1(&ref));
      +	} else {
      +		*type |= REF_ISBROKEN;
      +		errno = EINVAL;
 15:  57626bfe2d4 = 14:  9df5bc69f97 git-prompt: prepare for reftable refs backend
 16:  6229da992e4 ! 15:  4076ef5d20b Add "test-tool dump-reftable" command.
     @@ reftable/dump.c: static int dump_table(const char *tablename)
       
       	reftable_reader_free(r);
       	return 0;
     -@@ reftable/dump.c: static int dump_stack(const char *stackdir)
     +@@ reftable/dump.c: static int dump_table(const char *tablename)
     + static int compact_stack(const char *stackdir)
       {
       	struct reftable_stack *stack = NULL;
     - 	struct reftable_write_options cfg = {};
     +-	struct reftable_write_options cfg = {};
     ++	struct reftable_write_options cfg = { 0 };
     + 
     + 	int err = reftable_new_stack(&stack, stackdir, cfg);
     + 	if (err < 0)
     +@@ reftable/dump.c: static int compact_stack(const char *stackdir)
     + static int dump_stack(const char *stackdir)
     + {
     + 	struct reftable_stack *stack = NULL;
     +-	struct reftable_write_options cfg = {};
      -	struct reftable_iterator it = { 0 };
      -	struct reftable_ref_record ref = { 0 };
      -	struct reftable_log_record log = { 0 };
     ++	struct reftable_write_options cfg = { 0 };
      +	struct reftable_iterator it = { NULL };
      +	struct reftable_ref_record ref = { NULL };
      +	struct reftable_log_record log = { NULL };
     @@ reftable/dump.c: static int dump_stack(const char *stackdir)
       
       	reftable_stack_destroy(stack);
       	return 0;
     +@@ reftable/dump.c: static void print_help(void)
     + int reftable_dump_main(int argc, char *const *argv)
     + {
     + 	int err = 0;
     +-	int opt;
     + 	int opt_dump_table = 0;
     + 	int opt_dump_stack = 0;
     + 	int opt_compact = 0;
     +-	const char *arg = NULL;
     +-	while ((opt = getopt(argc, argv, "2chts")) != -1) {
     +-		switch (opt) {
     +-		case '2':
     +-			hash_id = 0x73323536;
     ++	const char *arg = NULL, *argv0 = argv[0];
     ++
     ++	for (; argc > 1; argv++, argc--)
     ++		if (*argv[1] != '-')
     + 			break;
     +-		case 't':
     ++		else if (!strcmp("-2", argv[1]))
     ++			hash_id = 0x73323536;
     ++		else if (!strcmp("-t", argv[1]))
     + 			opt_dump_table = 1;
     +-			break;
     +-		case 's':
     ++		else if (!strcmp("-s", argv[1]))
     + 			opt_dump_stack = 1;
     +-			break;
     +-		case 'c':
     ++		else if (!strcmp("-c", argv[1]))
     + 			opt_compact = 1;
     +-			break;
     +-		case '?':
     +-		case 'h':
     ++		else if (!strcmp("-?", argv[1]) || !strcmp("-h", argv[1])) {
     + 			print_help();
     + 			return 2;
     +-			break;
     + 		}
     +-	}
     + 
     +-	if (argv[optind] == NULL) {
     ++	if (argc != 2) {
     + 		fprintf(stderr, "need argument\n");
     + 		print_help();
     + 		return 2;
     + 	}
     + 
     +-	arg = argv[optind];
     ++	arg = argv[1];
     + 
     + 	if (opt_dump_table) {
     + 		err = dump_table(arg);
     +@@ reftable/dump.c: int reftable_dump_main(int argc, char *const *argv)
     + 	}
     + 
     + 	if (err < 0) {
     +-		fprintf(stderr, "%s: %s: %s\n", argv[0], arg,
     ++		fprintf(stderr, "%s: %s: %s\n", argv0, arg,
     + 			reftable_error_str(err));
     + 		return 1;
     + 	}
      
       ## t/helper/test-reftable.c ##
      @@ t/helper/test-reftable.c: int cmd__reftable(int argc, const char **argv)

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable backend needs to know the hash algorithm for writing the initialization hash table.

The initial reftable contains a symref HEAD => "main" (or "master"), which is agnostic to the size of hash value, but this is an exceptional circumstance, and the reftable library does not cater to this exception. It insists that all tables in the stack have a consistent format ID for the hash algorithm.

Call set_repo_hash_algo directly after calling validate_hash_algorithm() (which reads $GIT_DEFAULT_HASH).

---
 builtin/init-db.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

index 01bc648d416..dcb7015db48 100644
@@ -437,6 +437,27 @@ int init_db(const char *git_dir, const char *real_git_dir,
 
 	validate_hash_algorithm(&repo_fmt, hash);
 
+	/*
+	 * At this point, the_repository we have in-core does not look
+	 * anything like one that we would see initialized in an already
+	 * working repository after calling setup_git_directory().
+	 *
+	 * Calling repository.c::initialize_the_repository() may have
+	 * prepared the .index .objects and .parsed_objects members, but
+	 * other members like .gitdir, .commondir, etc. have not been
+	 * initialized.
+	 *
+	 * Many API functions assume they are working with the_repository
+	 * that has sensibly been initialized, but because we haven't
+	 * really read from an existing repository, we need to hand-craft
+	 * the necessary members of the structure to get out of this
+	 * chicken-and-egg situation.
+	 *
+	 * For now, we update the hash algorithm member to what the
+	 * validate_hash_algorithm() call decided for us.
+	 */
+	repo_set_hash_algo(the_repository, repo_fmt.hash_algo);
+
 	reinit = create_default_files(template_dir, original_git_dir,
 				      initial_branch, &repo_fmt);
 	if (reinit && initial_branch)

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

TODO: relicense?

---
 reftable/LICENSE | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)
 create mode 100644 reftable/LICENSE

new file mode 100644
index 00000000000..402e0f9356b
@@ -0,0 +1,31 @@
+BSD License
+
+Copyright (c) 2020, Google LLC
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+* Redistributions of source code must retain the above copyright notice,
+this list of conditions and the following disclaimer.
+
+* Redistributions in binary form must reproduce the above copyright
+notice, this list of conditions and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+
+* Neither the name of Google LLC nor the names of its contributors may
+be used to endorse or promote products derived from this software
+without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable/ directory is structured as a library, so it cannot crash on misuse. Instead, it returns an error codes.

In addition, the error code can be used to signal conditions from lower levels of the library to be handled by higher levels of the library. For example, a transaction might legitimately write an empty reftable file, but in that case, we'd want to shortcut the transaction overhead.

---
 reftable/error.c          | 41 ++++++++++++++++++++++++++
 reftable/reftable-error.h | 62 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 103 insertions(+)
 create mode 100644 reftable/error.c
 create mode 100644 reftable/reftable-error.h

new file mode 100644
index 00000000000..f6f16def921
@@ -0,0 +1,41 @@
+/*
+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-error.h"
+
+#include <stdio.h>
+
+const char *reftable_error_str(int err)
+{
+	static char buf[250];
+	switch (err) {
+	case REFTABLE_IO_ERROR:
+		return "I/O error";
+	case REFTABLE_FORMAT_ERROR:
+		return "corrupt reftable file";
+	case REFTABLE_NOT_EXIST_ERROR:
+		return "file does not exist";
+	case REFTABLE_LOCK_ERROR:
+		return "data is outdated";
+	case REFTABLE_API_ERROR:
+		return "misuse of the reftable API";
+	case REFTABLE_ZLIB_ERROR:
+		return "zlib failure";
+	case REFTABLE_NAME_CONFLICT:
+		return "file/directory conflict";
+	case REFTABLE_EMPTY_TABLE_ERROR:
+		return "wrote empty table";
+	case REFTABLE_REFNAME_ERROR:
+		return "invalid refname";
+	case -1:
+		return "general error";
+	default:
+		snprintf(buf, sizeof(buf), "unknown error code %d", err);
+		return buf;
+	}
+}

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This commit provides basic utility classes for the reftable library.

---
 Makefile                            |  24 +++++-
 contrib/buildsystems/CMakeLists.txt |  14 ++-
 reftable/basics.c                   | 128 ++++++++++++++++++++++++++++
 reftable/basics.h                   |  60 +++++++++++++
 reftable/basics_test.c              |  98 +++++++++++++++++++++
 reftable/publicbasics.c             |  58 +++++++++++++
 reftable/reftable-malloc.h          |  18 ++++
 reftable/reftable-tests.h           |  22 +++++
 reftable/system.h                   |  32 +++++++
 reftable/test_framework.c           |  23 +++++
 reftable/test_framework.h           |  53 ++++++++++++
 t/helper/test-reftable.c            |   9 ++
 t/helper/test-tool.c                |   3 +-
 t/helper/test-tool.h                |   1 +
 t/t0032-reftable-unittest.sh        |  15 ++++
 15 files changed, 552 insertions(+), 6 deletions(-)
 create mode 100644 reftable/basics.c
 create mode 100644 reftable/basics.h
 create mode 100644 reftable/basics_test.c
 create mode 100644 reftable/publicbasics.c
 create mode 100644 reftable/reftable-malloc.h
 create mode 100644 reftable/reftable-tests.h
 create mode 100644 reftable/system.h
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h
 create mode 100644 t/helper/test-reftable.c
 create mode 100755 t/t0032-reftable-unittest.sh

index 45bce31016b..9b6d84af8f6 100644
@@ -731,6 +731,7 @@ TEST_BUILTINS_OBJS += test-read-cache.o
 TEST_BUILTINS_OBJS += test-read-graph.o
 TEST_BUILTINS_OBJS += test-read-midx.o
 TEST_BUILTINS_OBJS += test-ref-store.o
+TEST_BUILTINS_OBJS += test-reftable.o
 TEST_BUILTINS_OBJS += test-regex.o
 TEST_BUILTINS_OBJS += test-repository.o
 TEST_BUILTINS_OBJS += test-revision-walking.o

@@ -820,6 +821,8 @@ TEST_SHELL_PATH = $(SHELL_PATH)
 
 LIB_FILE = libgit.a
 XDIFF_LIB = xdiff/lib.a
+REFTABLE_LIB = reftable/libreftable.a
+REFTABLE_TEST_LIB = reftable/libreftable_test.a
 
 GENERATED_H += command-list.h
 GENERATED_H += config-list.h

@@ -1185,7 +1188,7 @@ THIRD_PARTY_SOURCES += compat/regex/%
 THIRD_PARTY_SOURCES += sha1collisiondetection/%
 THIRD_PARTY_SOURCES += sha1dc/%
 
-GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB)
+GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB)
 EXTLIBS =
 
 GIT_USER_AGENT = git/$(GIT_VERSION)

@@ -2386,10 +2389,19 @@ XDIFF_OBJS += xdiff/xpatience.o
 XDIFF_OBJS += xdiff/xprepare.o
 XDIFF_OBJS += xdiff/xutils.o
 
+REFTABLE_OBJS += reftable/basics.o
+REFTABLE_OBJS += reftable/error.o
+REFTABLE_OBJS += reftable/publicbasics.o
+
+REFTABLE_TEST_OBJS += reftable/test_framework.o
+REFTABLE_TEST_OBJS += reftable/basics_test.o
+
 TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
 OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \
 	$(XDIFF_OBJS) \
 	$(FUZZ_OBJS) \
+	$(REFTABLE_OBJS) \
+	$(REFTABLE_TEST_OBJS) \
 	common-main.o \
 	git.o
 ifndef NO_CURL

@@ -2541,6 +2553,12 @@ $(LIB_FILE): $(LIB_OBJS)
 $(XDIFF_LIB): $(XDIFF_OBJS)
 	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
 
+$(REFTABLE_LIB): $(REFTABLE_OBJS)
+	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
+
+$(REFTABLE_TEST_LIB): $(REFTABLE_TEST_OBJS)
+	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
+
 export DEFAULT_EDITOR DEFAULT_PAGER
 
 Documentation/GIT-EXCLUDED-PROGRAMS: FORCE

@@ -2821,7 +2839,7 @@ perf: all
 
 t/helper/test-tool$X: $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
 
-t/helper/test-%$X: t/helper/test-%.o GIT-LDFLAGS $(GITLIBS)
+t/helper/test-%$X: t/helper/test-%.o GIT-LDFLAGS $(GITLIBS) $(REFTABLE_TEST_LIB)
 	$(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) $(filter %.a,$^) $(LIBS)
 
 check-sha1:: t/helper/test-tool$X

@@ -3150,7 +3168,7 @@ cocciclean:
 clean: profile-clean coverage-clean cocciclean
 	$(RM) *.res
 	$(RM) $(OBJECTS)
-	$(RM) $(LIB_FILE) $(XDIFF_LIB)
+	$(RM) $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB) $(REFTABLE_TEST_LIB)
 	$(RM) $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) git$X
 	$(RM) $(TEST_PROGRAMS)
 	$(RM) $(FUZZ_PROGRAMS)

index df539a44fa0..f3a2fd35616 100644
@@ -591,6 +591,12 @@ parse_makefile_for_sources(libxdiff_SOURCES "XDIFF_OBJS")
 list(TRANSFORM libxdiff_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
 add_library(xdiff STATIC ${libxdiff_SOURCES})
 
+#reftable
+parse_makefile_for_sources(reftable_SOURCES "REFTABLE_OBJS")
+
+list(TRANSFORM reftable_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
+add_library(reftable STATIC ${reftable_SOURCES})
+
 if(WIN32)
 	if(NOT MSVC)#use windres when compiling with gcc and clang
 		add_custom_command(OUTPUT ${CMAKE_BINARY_DIR}/git.res

@@ -613,7 +619,7 @@ endif()
 #link all required libraries to common-main
 add_library(common-main OBJECT ${CMAKE_SOURCE_DIR}/common-main.c)
 
-target_link_libraries(common-main libgit xdiff ${ZLIB_LIBRARIES})
+target_link_libraries(common-main libgit xdiff reftable ${ZLIB_LIBRARIES})
 if(Intl_FOUND)
 	target_link_libraries(common-main ${Intl_LIBRARIES})
 endif()

@@ -848,11 +854,15 @@ if(BUILD_TESTING)
 add_executable(test-fake-ssh ${CMAKE_SOURCE_DIR}/t/helper/test-fake-ssh.c)
 target_link_libraries(test-fake-ssh common-main)
 
+#reftable-tests
+parse_makefile_for_sources(test-reftable_SOURCES "REFTABLE_TEST_OBJS")
+list(TRANSFORM test-reftable_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
+
 #test-tool
 parse_makefile_for_sources(test-tool_SOURCES "TEST_BUILTINS_OBJS")
 
 list(TRANSFORM test-tool_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/t/helper/")
-add_executable(test-tool ${CMAKE_SOURCE_DIR}/t/helper/test-tool.c ${test-tool_SOURCES})
+add_executable(test-tool ${CMAKE_SOURCE_DIR}/t/helper/test-tool.c ${test-tool_SOURCES} ${test-reftable_SOURCES})
 target_link_libraries(test-tool common-main)
 
 set_target_properties(test-fake-ssh test-tool

new file mode 100644
index 00000000000..5f2185f1f34
@@ -0,0 +1,18 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef REFTABLE_H
+#define REFTABLE_H
+
+#include <stddef.h>
+
+/* Overrides the functions to use for memory management. */
+void reftable_set_alloc(void *(*malloc)(size_t),
+			void *(*realloc)(void *, size_t), void (*free)(void *));
+
+#endif

new file mode 100644
index 00000000000..5e7698ae654
@@ -0,0 +1,22 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef REFTABLE_TESTS_H
+#define REFTABLE_TESTS_H
+
+int basics_test_main(int argc, const char **argv);
+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 stack_test_main(int argc, const char **argv);
+int tree_test_main(int argc, const char **argv);
+int reftable_dump_main(int argc, char *const *argv);
+
+#endif

new file mode 100644
index 00000000000..07277ca0627
@@ -0,0 +1,32 @@
+/*
+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 SYSTEM_H
+#define SYSTEM_H
+
+#include "git-compat-util.h"
+#include "strbuf.h"
+
+#include <zlib.h>
+
+struct strbuf;
+/* In git, this is declared in dir.h */
+int remove_dir_recursively(struct strbuf *path, int flags);
+
+#define SHA1_ID 0x73686131
+#define SHA256_ID 0x73323536
+#define SHA1_SIZE 20
+#define SHA256_SIZE 32
+
+/* This is uncompress2, which is only available in zlib as of 2017.
+ */
+int uncompress_return_consumed(Bytef *dest, uLongf *destLen,
+			       const Bytef *source, uLong *sourceLen);
+int hash_size(uint32_t id);
+
+#endif

new file mode 100644
index 00000000000..a5ff4e2a2d2
@@ -0,0 +1,23 @@
+/*
+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 "test_framework.h"
+
+#include "basics.h"
+
+void set_test_hash(uint8_t *p, int i)
+{
+	memset(p, (uint8_t)i, hash_size(SHA1_ID));
+}
+
+int strbuf_add_void(void *b, const void *data, size_t sz)
+{
+	strbuf_add((struct strbuf *)b, data, sz);
+	return sz;
+}

new file mode 100644
index 00000000000..3b58e423e7b
@@ -0,0 +1,9 @@
+#include "reftable/reftable-tests.h"
+#include "test-tool.h"
+
+int cmd__reftable(int argc, const char **argv)
+{
+	basics_test_main(argc, argv);
+
+	return 0;
+}

index 9d6d14d9293..0208a0a41cf 100644
@@ -48,13 +48,14 @@ static struct test_cmd cmds[] = {
 	{ "path-utils", cmd__path_utils },
 	{ "pkt-line", cmd__pkt_line },
 	{ "prio-queue", cmd__prio_queue },
-	{ "proc-receive", cmd__proc_receive},
+	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
 	{ "read-cache", cmd__read_cache },
 	{ "read-graph", cmd__read_graph },
 	{ "read-midx", cmd__read_midx },
 	{ "ref-store", cmd__ref_store },
+	{ "reftable", cmd__reftable },
 	{ "regex", cmd__regex },
 	{ "repository", cmd__repository },
 	{ "revision-walking", cmd__revision_walking },

index a6470ff62c4..1de39ce5b58 100644
@@ -44,6 +44,7 @@ int cmd__read_cache(int argc, const char **argv);
 int cmd__read_graph(int argc, const char **argv);
 int cmd__read_midx(int argc, const char **argv);
 int cmd__ref_store(int argc, const char **argv);
+int cmd__reftable(int argc, const char **argv);
 int cmd__regex(int argc, const char **argv);
 int cmd__repository(int argc, const char **argv);
 int cmd__revision_walking(int argc, const char **argv);

new file mode 100755
index 00000000000..0ed14971a58
@@ -0,0 +1,15 @@
+#!/bin/sh
+#
+# Copyright (c) 2020 Google LLC
+#
+
+test_description='reftable unittests'
+
+. ./test-lib.sh
+
+test_expect_success 'unittests' '
+	TMPDIR=$(pwd) && export TMPDIR &&
+	test-tool reftable
+'
+
+test_done

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable format is usually used with files for storage. However, we abstract away this using the blocksource data structure. This has two advantages:

* log blocks are zlib compressed, and handling them is simplified if we can discard byte segments from within the block layer.

* for unittests, it is useful to read and write in-memory. The blocksource allows us to abstract the data away from on-disk files.

---
 Makefile                        |   1 +
 reftable/blocksource.c          | 148 ++++++++++++++++++++++++++++++++
 reftable/blocksource.h          |  22 +++++
 reftable/reftable-blocksource.h |  49 +++++++++++
 4 files changed, 220 insertions(+)
 create mode 100644 reftable/blocksource.c
 create mode 100644 reftable/blocksource.h
 create mode 100644 reftable/reftable-blocksource.h

index 9b6d84af8f6..f623611bde2 100644
@@ -2391,6 +2391,7 @@ XDIFF_OBJS += xdiff/xutils.o
 
 REFTABLE_OBJS += reftable/basics.o
 REFTABLE_OBJS += reftable/error.o
+REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
 
 REFTABLE_TEST_OBJS += reftable/test_framework.o

new file mode 100644
index 00000000000..072e2727ad2
@@ -0,0 +1,22 @@
+/*
+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 BLOCKSOURCE_H
+#define BLOCKSOURCE_H
+
+#include "system.h"
+
+struct reftable_block_source;
+
+/* Create an in-memory block source for reading reftables */
+void block_source_from_strbuf(struct reftable_block_source *bs,
+			      struct strbuf *buf);
+
+struct reftable_block_source malloc_block_source(void);
+
+#endif

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable format is structured as a sequence of blocks, and each block contains a sequence of prefix-compressed key-value records. There are 4 types of records, and they have similarities in how they must be handled. This is achieved by introducing a polymorphic 'record' type that encapsulates ref, log, index and object records.

---
 Makefile                   |    2 +
 reftable/constants.h       |   21 +
 reftable/record.c          | 1157 ++++++++++++++++++++++++++++++++++++
 reftable/record.h          |  139 +++++
 reftable/record_test.c     |  398 +++++++++++++
 reftable/reftable-record.h |  100 ++++
 t/helper/test-reftable.c   |    2 +-
 7 files changed, 1818 insertions(+), 1 deletion(-)
 create mode 100644 reftable/constants.h
 create mode 100644 reftable/record.c
 create mode 100644 reftable/record.h
 create mode 100644 reftable/record_test.c
 create mode 100644 reftable/reftable-record.h

index f623611bde2..ce3052169b4 100644
@@ -2393,7 +2393,9 @@ REFTABLE_OBJS += reftable/basics.o
 REFTABLE_OBJS += reftable/error.o
 REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
+REFTABLE_OBJS += reftable/record.o
 
+REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 REFTABLE_TEST_OBJS += reftable/basics_test.o
 

new file mode 100644
index 00000000000..5eee72c4c11
@@ -0,0 +1,21 @@
+/*
+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 CONSTANTS_H
+#define CONSTANTS_H
+
+#define BLOCK_TYPE_LOG 'g'
+#define BLOCK_TYPE_INDEX 'i'
+#define BLOCK_TYPE_REF 'r'
+#define BLOCK_TYPE_OBJ 'o'
+#define BLOCK_TYPE_ANY 0
+
+#define MAX_RESTARTS ((1 << 16) - 1)
+#define DEFAULT_BLOCK_SIZE 4096
+
+#endif

index 3b58e423e7b..09d4b83ef9b 100644
@@ -4,6 +4,6 @@
 int cmd__reftable(int argc, const char **argv)
 {
 	basics_test_main(argc, argv);
-
+	record_test_main(argc, argv);
 	return 0;
 }

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable format is structured as a sequence of block. Within a block, records are prefix compressed, with an index of offsets for fully expand keys to enable binary search within blocks.

This commit provides the logic to read and write these blocks.

Includes a code snippet copied from zlib

---
 Makefile                 |   3 +
 reftable/.gitattributes  |   1 +
 reftable/block.c         | 440 +++++++++++++++++++++++++++++++++++++++
 reftable/block.h         | 127 +++++++++++
 reftable/block_test.c    | 121 +++++++++++
 reftable/zlib-compat.c   |  92 ++++++++
 t/helper/test-reftable.c |   1 +
 7 files changed, 785 insertions(+)
 create mode 100644 reftable/.gitattributes
 create mode 100644 reftable/block.c
 create mode 100644 reftable/block.h
 create mode 100644 reftable/block_test.c
 create mode 100644 reftable/zlib-compat.c

index ce3052169b4..abe0dda5777 100644
@@ -2391,10 +2391,13 @@ XDIFF_OBJS += xdiff/xutils.o
 
 REFTABLE_OBJS += reftable/basics.o
 REFTABLE_OBJS += reftable/error.o
+REFTABLE_OBJS += reftable/block.o
 REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/record.o
+REFTABLE_OBJS += reftable/zlib-compat.o
 
+REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 REFTABLE_TEST_OBJS += reftable/basics_test.o

new file mode 100644
index 00000000000..f44451a3795
@@ -0,0 +1 @@
+/zlib-compat.c	whitespace=-indent-with-non-tab,-trailing-space

index 09d4b83ef9b..c9deeaf08c7 100644
@@ -4,6 +4,7 @@
 int cmd__reftable(int argc, const char **argv)
 {
 	basics_test_main(argc, argv);
+	block_test_main(argc, argv);
 	record_test_main(argc, argv);
 	return 0;
 }

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable format includes support for an (OID => ref) map. This map can speed up visibility and reachability checks. In particular, various operations along the fetch/push path within Gerrit have ben sped up by using this structure.

The map is constructed with help of a binary tree. Object IDs are hashes, so they are uniformly distributed. Hence, the tree does not attempt forced rebalancing.

---
 Makefile                 |  4 ++-
 reftable/tree.c          | 63 ++++++++++++++++++++++++++++++++++++++++
 reftable/tree.h          | 34 ++++++++++++++++++++++
 reftable/tree_test.c     | 61 ++++++++++++++++++++++++++++++++++++++
 t/helper/test-reftable.c |  1 +
 5 files changed, 162 insertions(+), 1 deletion(-)
 create mode 100644 reftable/tree.c
 create mode 100644 reftable/tree.h
 create mode 100644 reftable/tree_test.c

index abe0dda5777..734c05655b2 100644
@@ -2395,12 +2395,14 @@ REFTABLE_OBJS += reftable/block.o
 REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/record.o
+REFTABLE_OBJS += reftable/tree.o
 REFTABLE_OBJS += reftable/zlib-compat.o
 
+REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
-REFTABLE_TEST_OBJS += reftable/basics_test.o
+REFTABLE_TEST_OBJS += reftable/tree_test.o
 
 TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
 OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \

new file mode 100644
index 00000000000..fbdd002e23a
@@ -0,0 +1,34 @@
+/*
+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 TREE_H
+#define TREE_H
+
+/* tree_node is a generic binary search tree. */
+struct tree_node {
+	void *key;
+	struct tree_node *left, *right;
+};
+
+/* looks for `key` in `rootp` using `compare` as comparison function. If insert
+ * is set, insert the key if it's not found. Else, return NULL.
+ */
+struct tree_node *tree_search(void *key, struct tree_node **rootp,
+			      int (*compare)(const void *, const void *),
+			      int insert);
+
+/* performs an infix walk of the tree. */
+void infix_walk(struct tree_node *t, void (*action)(void *arg, void *key),
+		void *arg);
+
+/*
+ * deallocates the tree nodes recursively. Keys should be deallocated separately
+ * by walking over the tree. */
+void tree_free(struct tree_node *t);
+
+#endif

index c9deeaf08c7..050551fa698 100644
@@ -6,5 +6,6 @@ int cmd__reftable(int argc, const char **argv)
 	basics_test_main(argc, argv);
 	block_test_main(argc, argv);
 	record_test_main(argc, argv);
+	tree_test_main(argc, argv);
 	return 0;
 }

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

---
 Makefile                   |   1 +
 reftable/reftable-writer.h | 147 ++++++++
 reftable/writer.c          | 681 +++++++++++++++++++++++++++++++++++++
 reftable/writer.h          |  50 +++
 4 files changed, 879 insertions(+)
 create mode 100644 reftable/reftable-writer.h
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h

index 734c05655b2..e78908c976a 100644
@@ -2396,6 +2396,7 @@ REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/record.o
 REFTABLE_OBJS += reftable/tree.o
+REFTABLE_OBJS += reftable/writer.o
 REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/basics_test.o

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This supports reading a single reftable file.

The commit introduces an abstract iterator type, which captures the usecases both of reading individual refs, and iterating over a segment of the ref namespace.

---
 Makefile                     |   3 +
 reftable/iter.c              | 248 ++++++++++++
 reftable/iter.h              |  75 ++++
 reftable/reader.c            | 733 +++++++++++++++++++++++++++++++++++
 reftable/reader.h            |  75 ++++
 reftable/reftable-iterator.h |  37 ++
 reftable/reftable-reader.h   |  89 +++++
 7 files changed, 1260 insertions(+)
 create mode 100644 reftable/iter.c
 create mode 100644 reftable/iter.h
 create mode 100644 reftable/reader.c
 create mode 100644 reftable/reader.h
 create mode 100644 reftable/reftable-iterator.h
 create mode 100644 reftable/reftable-reader.h

index e78908c976a..2bafcb1b62a 100644
@@ -2393,8 +2393,11 @@ REFTABLE_OBJS += reftable/basics.o
 REFTABLE_OBJS += reftable/error.o
 REFTABLE_OBJS += reftable/block.o
 REFTABLE_OBJS += reftable/blocksource.o
+REFTABLE_OBJS += reftable/iter.o
 REFTABLE_OBJS += reftable/publicbasics.o
+REFTABLE_OBJS += reftable/reader.o
 REFTABLE_OBJS += reftable/record.o
+REFTABLE_OBJS += reftable/reftable.o
 REFTABLE_OBJS += reftable/tree.o
 REFTABLE_OBJS += reftable/writer.o
 REFTABLE_OBJS += reftable/zlib-compat.o

new file mode 100644
index 00000000000..d8251a45ba1
@@ -0,0 +1,37 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef REFTABLE_ITERATOR_H
+#define REFTABLE_ITERATOR_H
+
+#include "reftable-record.h"
+
+/* iterator is the generic interface for walking over data stored in a
+ * reftable.
+ */
+struct reftable_iterator {
+	struct reftable_iterator_vtable *ops;
+	void *iter_arg;
+};
+
+/* reads the next reftable_ref_record. Returns < 0 for error, 0 for OK and > 0:
+ * end of iteration.
+ */
+int reftable_iterator_next_ref(struct reftable_iterator *it,
+			       struct reftable_ref_record *ref);
+
+/* reads the next reftable_log_record. Returns < 0 for error, 0 for OK and > 0:
+ * end of iteration.
+ */
+int reftable_iterator_next_log(struct reftable_iterator *it,
+			       struct reftable_log_record *log);
+
+/* releases resources associated with an iterator. */
+void reftable_iterator_destroy(struct reftable_iterator *it);
+
+#endif

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

With support for reading and writing files in place, we can construct files (in memory) and attempt to read them back.

Because some sections of the format are optional (eg. indices, log entries), we have to exercise this code using multiple sizes of input data

---
 Makefile                 |   1 +
 reftable/reftable_test.c | 580 +++++++++++++++++++++++++++++++++++++++
 t/helper/test-reftable.c |   1 +
 3 files changed, 582 insertions(+)
 create mode 100644 reftable/reftable_test.c

index 2bafcb1b62a..c913e90b643 100644
@@ -2405,6 +2405,7 @@ REFTABLE_OBJS += reftable/zlib-compat.o
 REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
+REFTABLE_TEST_OBJS += reftable/reftable_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 REFTABLE_TEST_OBJS += reftable/tree_test.o
 

index 050551fa698..fdf92586737 100644
@@ -6,6 +6,7 @@ int cmd__reftable(int argc, const char **argv)
 	basics_test_main(argc, argv);
 	block_test_main(argc, argv);
 	record_test_main(argc, argv);
+	reftable_test_main(argc, argv);
 	tree_test_main(argc, argv);
 	return 0;
 }

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

---
 Makefile                    |    4 +
 reftable/VERSION            |    1 +
 reftable/dump.c             |  212 ++++++
 reftable/merged.c           |  366 ++++++++++
 reftable/merged.h           |   35 +
 reftable/merged_test.c      |  343 ++++++++++
 reftable/pq.c               |  115 ++++
 reftable/pq.h               |   32 +
 reftable/refname.c          |  209 ++++++
 reftable/refname.h          |   29 +
 reftable/refname_test.c     |  102 +++
 reftable/reftable-generic.h |   48 ++
 reftable/reftable-merged.h  |   68 ++
 reftable/reftable-stack.h   |  120 ++++
 reftable/reftable.c         |   98 +++
 reftable/stack.c            | 1260 +++++++++++++++++++++++++++++++++++
 reftable/stack.h            |   41 ++
 reftable/stack_test.c       |  803 ++++++++++++++++++++++
 t/helper/test-reftable.c    |    3 +
 19 files changed, 3889 insertions(+)
 create mode 100644 reftable/VERSION
 create mode 100644 reftable/dump.c
 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/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/refname_test.c
 create mode 100644 reftable/reftable-generic.h
 create mode 100644 reftable/reftable-merged.h
 create mode 100644 reftable/reftable-stack.h
 create mode 100644 reftable/reftable.c
 create mode 100644 reftable/stack.c
 create mode 100644 reftable/stack.h
 create mode 100644 reftable/stack_test.c

index c913e90b643..18cc18c2153 100644
@@ -2394,10 +2394,14 @@ REFTABLE_OBJS += reftable/error.o
 REFTABLE_OBJS += reftable/block.o
 REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/iter.o
+REFTABLE_OBJS += reftable/merged.o
+REFTABLE_OBJS += reftable/pq.o
 REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/reader.o
 REFTABLE_OBJS += reftable/record.o
+REFTABLE_OBJS += reftable/refname.o
 REFTABLE_OBJS += reftable/reftable.o
+REFTABLE_OBJS += reftable/stack.o
 REFTABLE_OBJS += reftable/tree.o
 REFTABLE_OBJS += reftable/writer.o
 REFTABLE_OBJS += reftable/zlib-compat.o

new file mode 100644
index 00000000000..a67c0682e1b
@@ -0,0 +1 @@
+9b4a54059db9a05c270c0a0587f245bc6868d576 C: use rand() rather than cobbled together random generator.

new file mode 100644
index 00000000000..8c4d4d58d77
@@ -0,0 +1,35 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef MERGED_H
+#define MERGED_H
+
+#include "pq.h"
+
+struct reftable_merged_table {
+	struct reftable_table *stack;
+	size_t stack_len;
+	uint32_t hash_id;
+	int suppress_deletions;
+
+	uint64_t min;
+	uint64_t max;
+};
+
+struct merged_iter {
+	struct reftable_iterator *stack;
+	uint32_t hash_id;
+	size_t stack_len;
+	uint8_t typ;
+	int suppress_deletions;
+	struct merged_iter_pqueue pq;
+};
+
+void merged_table_release(struct reftable_merged_table *mt);
+
+#endif

new file mode 100644
index 00000000000..385d2fb139a
@@ -0,0 +1,32 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef PQ_H
+#define PQ_H
+
+#include "record.h"
+
+struct pq_entry {
+	int index;
+	struct reftable_record rec;
+};
+
+struct merged_iter_pqueue {
+	struct pq_entry *heap;
+	size_t len;
+	size_t cap;
+};
+
+struct pq_entry merged_iter_pqueue_top(struct merged_iter_pqueue pq);
+int merged_iter_pqueue_is_empty(struct merged_iter_pqueue pq);
+void merged_iter_pqueue_check(struct merged_iter_pqueue pq);
+struct pq_entry merged_iter_pqueue_remove(struct merged_iter_pqueue *pq);
+void merged_iter_pqueue_add(struct merged_iter_pqueue *pq, struct pq_entry e);
+void merged_iter_pqueue_release(struct merged_iter_pqueue *pq);
+
+#endif

new file mode 100644
index 00000000000..a24b40fcb42
@@ -0,0 +1,29 @@
+/*
+  Copyright 2020 Google LLC
+
+  Use of this source code is governed by a BSD-style
+  license that can be found in the LICENSE file or at
+  https://developers.google.com/open-source/licenses/bsd
+*/
+#ifndef REFNAME_H
+#define REFNAME_H
+
+#include "reftable-record.h"
+#include "reftable-generic.h"
+
+struct modification {
+	struct reftable_table tab;
+
+	char **add;
+	size_t add_len;
+
+	char **del;
+	size_t del_len;
+};
+
+int validate_ref_record_addition(struct reftable_table tab,
+				 struct reftable_ref_record *recs, size_t sz);
+
+int modification_validate(struct modification *mod);
+
+#endif

index fdf92586737..3b702f4855e 100644

gitgitgadget

Part of the diff is not shown here. View the raw message.

From: Han-Wen Nienhuys <[email protected]>

For background, see the previous commit introducing the library.

This introduces the file refs/reftable-backend.c containing a reftable-powered ref storage backend.

It can be activated by passing --ref-storage=reftable to "git init", or setting GIT_TEST_REFTABLE in the environment.

Example use: see t/t0031-reftable.sh

---
 Documentation/config/extensions.txt           |    9 +
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |    4 +
 builtin/clone.c                               |    5 +-
 builtin/init-db.c                             |   55 +-
 builtin/worktree.c                            |   27 +-
 cache.h                                       |    8 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 refs.c                                        |   27 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1435 +++++++++++++++++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |    9 +-
 t/t0031-reftable.sh                           |  199 +++
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1450-fsck.sh                               |    6 +
 t/t3210-pack-refs.sh                          |    6 +
 t/test-lib.sh                                 |    5 +
 21 files changed, 1797 insertions(+), 33 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100755 t/t0031-reftable.sh

index 4e23d73cdca..82c5940f143 100644
@@ -6,3 +6,12 @@ extensions.objectFormat::
 Note that this setting should only be set by linkgit:git-init[1] or
 linkgit:git-clone[1].  Trying to change it after initialization will not
 work and will produce hard-to-diagnose issues.
++
+extensions.refStorage::
+	Specify the ref storage mechanism to use.  The acceptable values are `files` and
+	`reftable`.  If not specified, `files` is assumed.  It is an error to specify
+	this key unless `core.repositoryFormatVersion` is 1.
++
+Note that this setting should only be set by linkgit:git-init[1] or
+linkgit:git-clone[1].  Trying to change it after initialization will not
+work and will produce hard-to-diagnose issues.

index 7844ef30ffd..72576235833 100644
@@ -100,3 +100,10 @@ If set, by default "git config" reads from both "config" and
 multiple working directory mode, "config" file is shared while
 "config.worktree" is per-working directory (i.e., it's in
 GIT_COMMON_DIR/worktrees/<id>/config.worktree)
+
+==== `refStorage`
+
+Specifies the file format for the ref database. Values are `files`
+(for the traditional packed + loose ref format) and `reftable` for the
+binary reftable format. See https://github.com/google/reftable for
+more information.

index 18cc18c2153..6b7c8a165f4 100644
@@ -977,6 +977,7 @@ LIB_OBJS += reflog-walk.o
 LIB_OBJS += refs.o
 LIB_OBJS += refs/debug.o
 LIB_OBJS += refs/files-backend.o
+LIB_OBJS += refs/reftable-backend.o
 LIB_OBJS += refs/iterator.o
 LIB_OBJS += refs/packed-backend.o
 LIB_OBJS += refs/ref-cache.o

@@ -2408,8 +2409,11 @@ REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
+REFTABLE_TEST_OBJS += reftable/merged_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
+REFTABLE_TEST_OBJS += reftable/refname_test.o
 REFTABLE_TEST_OBJS += reftable/reftable_test.o
+REFTABLE_TEST_OBJS += reftable/stack_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 REFTABLE_TEST_OBJS += reftable/tree_test.o
 

index a0841923cfe..974a374e9c9 100644
@@ -1138,7 +1138,7 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 	}
 
 	init_db(git_dir, real_git_dir, option_template, GIT_HASH_UNKNOWN, NULL,
-		INIT_DB_QUIET);
+		default_ref_storage(), INIT_DB_QUIET);
 
 	if (real_git_dir)
 		git_dir = real_git_dir;

@@ -1273,7 +1273,8 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 		 * Now that we know what algorithm the remote side is using,
 		 * let's set ours to the same thing.
 		 */
-		initialize_repository_version(hash_algo, 1);
+		initialize_repository_version(hash_algo, 1,
+					      default_ref_storage());
 		repo_set_hash_algo(the_repository, hash_algo);
 
 		mapped_refs = wanted_peer_refs(refs, &remote->fetch);

index 197fd24a555..a102aedfca7 100644
@@ -12,6 +12,7 @@
 #include "submodule.h"
 #include "utf8.h"
 #include "worktree.h"
+#include "../refs/refs-internal.h"
 
 static const char * const worktree_usage[] = {
 	N_("git worktree add [<options>] <path> [<commit-ish>]"),

@@ -402,9 +403,29 @@ static int add_worktree(const char *path, const char *refname,
 	 * worktree.
 	 */
 	strbuf_reset(&sb);
-	strbuf_addf(&sb, "%s/HEAD", sb_repo.buf);
-	write_file(sb.buf, "%s", oid_to_hex(&null_oid));
-	strbuf_reset(&sb);
+	if (get_main_ref_store(the_repository)->be == &refs_be_reftable) {
+		/* XXX this is cut & paste from reftable_init_db. */
+		strbuf_addf(&sb, "%s/HEAD", sb_repo.buf);
+		write_file(sb.buf, "%s", "ref: refs/heads/.invalid\n");
+		strbuf_reset(&sb);
+
+		strbuf_addf(&sb, "%s/refs", sb_repo.buf);
+		safe_create_dir(sb.buf, 1);
+		strbuf_reset(&sb);
+
+		strbuf_addf(&sb, "%s/refs/heads", sb_repo.buf);
+		write_file(sb.buf, "this repository uses the reftable format");
+		strbuf_reset(&sb);
+
+		strbuf_addf(&sb, "%s/reftable", sb_repo.buf);
+		safe_create_dir(sb.buf, 1);
+		strbuf_reset(&sb);
+	} else {
+		strbuf_addf(&sb, "%s/HEAD", sb_repo.buf);
+		write_file(sb.buf, "%s", oid_to_hex(&null_oid));
+		strbuf_reset(&sb);
+	}
+
 	strbuf_addf(&sb, "%s/commondir", sb_repo.buf);
 	write_file(sb.buf, "../..");
 

index e986cf4ea9c..545d2b72607 100644
@@ -627,9 +627,10 @@ int path_inside_repo(const char *prefix, const char *path);
 #define INIT_DB_EXIST_OK 0x0002
 
 int init_db(const char *git_dir, const char *real_git_dir,
-	    const char *template_dir, int hash_algo,
-	    const char *initial_branch, unsigned int flags);
-void initialize_repository_version(int hash_algo, int reinit);
+	    const char *template_dir, int hash_algo, const char *initial_branch,
+	    const char *ref_storage_format, unsigned int flags);
+void initialize_repository_version(int hash_algo, int reinit,
+				   const char *ref_storage_format);
 
 void sanitize_stdfds(void);
 int daemonize(void);

@@ -1043,6 +1044,7 @@ struct repository_format {
 	int is_bare;
 	int hash_algo;
 	char *work_tree;
+	char *ref_storage;
 	struct string_list unknown_extensions;
 	struct string_list v1_only_extensions;
 };

index 5b30a9154ac..4ab0191f5e6 100644
@@ -701,7 +701,7 @@ vcxproj:
 	# Make .vcxproj files and add them
 	unset QUIET_GEN QUIET_BUILT_IN; \
 	perl contrib/buildsystems/generate -g Vcxproj
-	git add -f git.sln {*,*/lib,t/helper/*}/*.vcxproj
+	git add -f git.sln {*,*/lib,*/libreftable,t/helper/*}/*.vcxproj
 
 	# Generate the LinkOrCopyBuiltins.targets and LinkOrCopyRemoteHttp.targets file
 	(echo '<Project xmlns="http://schemas.microsoft.com/developer/msbuild/2003">' && \

index d2584450ba1..1a25789d285 100644
@@ -77,7 +77,7 @@ sub createProject {
     my $libs_release = "\n    ";
     my $libs_debug = "\n    ";
     if (!$static_library) {
-      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
+      $libs_release = join(";", sort(grep /^(?!libgit\.lib|xdiff\/lib\.lib|vcs-svn\/lib\.lib|reftable\/libreftable\.lib)/, @{$$build_structure{"$prefix${name}_LIBS"}}));
       $libs_debug = $libs_release;
       $libs_debug =~ s/zlib\.lib/zlibd\.lib/g;
       $libs_debug =~ s/libexpat\.lib/libexpatd\.lib/g;

@@ -232,6 +232,7 @@ sub createProject {
 EOM
     if (!$static_library || $target =~ 'vcs-svn' || $target =~ 'xdiff') {
       my $uuid_libgit = $$build_structure{"LIBS_libgit_GUID"};
+      my $uuid_libreftable = $$build_structure{"LIBS_reftable/libreftable_GUID"};
       my $uuid_xdiff_lib = $$build_structure{"LIBS_xdiff/lib_GUID"};
 
       print F << "EOM";

@@ -241,6 +242,14 @@ sub createProject {
       <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
     </ProjectReference>
 EOM
+      if (!($name =~ /xdiff|libreftable/)) {
+        print F << "EOM";
+    <ProjectReference Include="$cdup\\reftable\\libreftable\\libreftable.vcxproj">
+      <Project>$uuid_libreftable</Project>
+      <ReferenceOutputAssembly>false</ReferenceOutputAssembly>
+    </ProjectReference>
+EOM
+      }
       if (!($name =~ 'xdiff')) {
         print F << "EOM";
     <ProjectReference Include="$cdup\\xdiff\\lib\\xdiff_lib.vcxproj">

index 392f0bbf68b..1b874db3345 100644
@@ -19,10 +19,16 @@
 #include "repository.h"
 #include "sigchain.h"
 
+const char *default_ref_storage(void)
+{
+	const char *test = getenv("GIT_TEST_REFTABLE");
+	return test ? "reftable" : "files";
+}
+
 /*
  * List of all available backends
  */
-static struct ref_storage_be *refs_backends = &refs_be_files;
+static struct ref_storage_be *refs_backends = &refs_be_reftable;
 
 static struct ref_storage_be *find_ref_storage_backend(const char *name)
 {

@@ -1754,13 +1760,13 @@ static struct ref_store *lookup_ref_store_map(struct hashmap *map,
  * Create, record, and return a ref_store instance for the specified
  * gitdir.
  */
-static struct ref_store *ref_store_init(const char *gitdir,
+static struct ref_store *ref_store_init(const char *gitdir, const char *be_name,
 					unsigned int flags)
 {
-	const char *be_name = "files";
-	struct ref_storage_be *be = find_ref_storage_backend(be_name);
+	struct ref_storage_be *be;
 	struct ref_store *refs;
 
+	be = find_ref_storage_backend(be_name);
 	if (!be)
 		BUG("reference backend %s is unknown", be_name);
 

@@ -1776,7 +1782,11 @@ struct ref_store *get_main_ref_store(struct repository *r)
 	if (!r->gitdir)
 		BUG("attempting to get main_ref_store outside of repository");
 
-	r->refs_private = ref_store_init(r->gitdir, REF_STORE_ALL_CAPS);
+	r->refs_private = ref_store_init(r->gitdir,
+					 r->ref_storage_format ?
+						       r->ref_storage_format :
+						       default_ref_storage(),
+					 REF_STORE_ALL_CAPS);
 	r->refs_private = maybe_debug_wrap_ref_store(r->gitdir, r->refs_private);
 	return r->refs_private;
 }

@@ -1832,7 +1842,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 		goto done;
 
 	/* assume that add_submodule_odb() has been called */
-	refs = ref_store_init(submodule_sb.buf,
+	refs = ref_store_init(submodule_sb.buf, default_ref_storage(),
 			      REF_STORE_READ | REF_STORE_ODB);
 	register_ref_store_map(&submodule_ref_stores, "submodule",
 			       refs, submodule);

@@ -1846,6 +1856,7 @@ struct ref_store *get_submodule_ref_store(const char *submodule)
 
 struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 {
+	const char *format = default_ref_storage();
 	struct ref_store *refs;
 	const char *id;
 

@@ -1859,9 +1870,9 @@ struct ref_store *get_worktree_ref_store(const struct worktree *wt)
 
 	if (wt->id)
 		refs = ref_store_init(git_common_path("worktrees/%s", wt->id),
-				      REF_STORE_ALL_CAPS);
+				      format, REF_STORE_ALL_CAPS);
 	else
-		refs = ref_store_init(get_git_common_dir(),
+		refs = ref_store_init(get_git_common_dir(), format,
 				      REF_STORE_ALL_CAPS);
 
 	if (refs)

index 66955181569..7dc60472c96 100644
@@ -11,6 +11,9 @@ struct string_list;
 struct string_list_item;
 struct worktree;
 
+/* Returns the ref storage backend to use by default. */
+const char *default_ref_storage(void);
+
 /*
  * Resolve a reference, recursively following symbolic refererences.
  *

index 467f4b3c936..28166bf1f82 100644
@@ -669,6 +669,7 @@ struct ref_storage_be {
 };
 
 extern struct ref_storage_be refs_be_files;
+extern struct ref_storage_be refs_be_reftable;
 extern struct ref_storage_be refs_be_packed;
 
 /*

index a4174ddb062..ff0988dac84 100644
@@ -174,6 +174,8 @@ int repo_init(struct repository *repo,
 	if (worktree)
 		repo_set_worktree(repo, worktree);
 
+	repo->ref_storage_format = xstrdup_or_null(format.ref_storage);
+
 	clear_repository_format(&format);
 	return 0;
 

index b385ca3c94b..8019a7d0a1f 100644
@@ -78,6 +78,9 @@ struct repository {
 	 */
 	struct ref_store *refs_private;
 
+	/* The format to use for the ref database. */
+	char *ref_storage_format;
+
 	/*
 	 * Contains path to often used file names.
 	 */

index c04cd25a30d..c6b57efd031 100644
@@ -500,6 +500,9 @@ static enum extension_result handle_extension(const char *var,
 			return error("invalid value for 'extensions.objectformat'");
 		data->hash_algo = format;
 		return EXTENSION_OK;
+	} else if (!strcmp(ext, "refstorage")) {
+		data->ref_storage = xstrdup(value);
+		return EXTENSION_OK;
 	}
 	return EXTENSION_UNKNOWN;
 }

@@ -651,6 +654,7 @@ void clear_repository_format(struct repository_format *format)
 	string_list_clear(&format->v1_only_extensions, 0);
 	free(format->work_tree);
 	free(format->partial_clone);
+	free(format->ref_storage);
 	init_repository_format(format);
 }
 

@@ -1308,8 +1312,11 @@ const char *setup_git_directory_gently(int *nongit_ok)
 				gitdir = DEFAULT_GIT_DIR_ENVIRONMENT;
 			setup_git_env(gitdir);
 		}
-		if (startup_info->have_repository)
+		if (startup_info->have_repository) {
 			repo_set_hash_algo(the_repository, repo_fmt.hash_algo);
+			the_repository->ref_storage_format =
+				xstrdup_or_null(repo_fmt.ref_storage);
+		}
 	}
 
 	strbuf_release(&dir);

index be12fb63506..c6f78325563 100755
@@ -4,6 +4,12 @@ test_description='avoid rewriting packed-refs unnecessarily'
 
 . ./test-lib.sh
 
+if test_have_prereq REFTABLE
+then
+  skip_all='skipping pack-refs tests; incompatible with reftable'
+  test_done
+fi
+
 # Add an identifying mark to the packed-refs file header line. This
 # shouldn't upset readers, and it should be omitted if the file is
 # ever rewritten.

index b17f5c21fbc..cc5d01571a4 100755
@@ -8,6 +8,12 @@ test_description='git fsck random collection of tests
 
 . ./test-lib.sh
 
+if test_have_prereq REFTABLE
+then
+  skip_all='skipping tests; incompatible with reftable'
+  test_done
+fi
+
 test_expect_success setup '
 	git config gc.auto 0 &&
 	git config i18n.commitencoding ISO-8859-1 &&

index f41b2afb996..edaef2c175a 100755
@@ -11,6 +11,12 @@ semantic is still the same.
 '
 . ./test-lib.sh
 
+if test_have_prereq REFTABLE
+then
+  skip_all='skipping pack-refs tests; incompatible with reftable'
+  test_done
+fi
+
 test_expect_success 'enable reflogs' '
 	git config core.logallrefupdates true
 '

index a863ccee7e9..7b638e0b8c8 100644
@@ -1520,6 +1520,11 @@ parisc* | hppa*)
 	;;
 esac
 
+if test -n "$GIT_TEST_REFTABLE"
+then
+  test_set_prereq REFTABLE
+fi
+
 ( COLUMNS=1 && test $COLUMNS = 1 ) && test_set_prereq COLUMNS_CAN_BE_1
 test -z "$NO_PERL" && test_set_prereq PERL
 test -z "$NO_PTHREADS" && test_set_prereq PTHREADS

gitgitgadget

One of the earlier iterations of this code didn't have the errno handling, and it caused a bug that I tracked down to the errno handling. I'm fairly sure of this, because I remember being perplexed and flabbergasted at using errno as an out-of-band API mechanism. The first iteration of reftable code was about a year ago, so if you checkout the Git source code from that time, and remove the errno assignments, you would be able to see which test exercised this code path.

Or you could check where errno is read-back (I believe ENOENT is the case that has special meaning)

Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

In refs.c, there is behavior that depends on errno,

if (refs_read_raw_ref(refs, refname,

      oid, &sb_refname, &read_flags)) {

..
/*
* Otherwise a missing ref is OK. But the files backend
* may show errors besides ENOENT if there are
* similarly-named refs.
*/
if (errno != ENOENT &&

    errno != EISDIR &&
    errno != ENOTDIR)

return NULL;

blame tells me it has something to do with dir/file conflicts and commit a1c1d8170db.

Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--
Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

I'm aware mostly of what the code is doing. Yes some of it's used, some of it's not.

My upthread [1] wasn't clear enough, the intended message was "hey this new major refactoring/replacement of a core git format still has zero coverage on at least some of the code it seeks to replace" not "hey what's this thing in refs.c doing?".

I.e. lack of test coverage on refactored code as part of a big patch series is a lot scarier than the same lack of coverage on existing long-established code we'll either not update, or in small incremental updates.

So it was a gentle prod to maybe look into what the state of that in the reftable series as a whole is and fix the coverage gaps. I'd like the feature in git.git, but this series has been stalled for a while. I for one would feel a lot more confident in reviewing it if I knew I'd just discovered an outlier case.

But in any case, when I wrote[1] I didn't know about / had forgotten "make cover". As noted in t/README that can even give pretty HTML output. It takes ages to run so I haven't run it on your series, but I ran it on master a couple of days ago and it flagged those (and other) parts of refs.c.

So perhaps running it on the reftables series will find some useful cases to make up the test difference / potential bugs.

Of course 100% line coverage isn't practical (hitting every BUG(...)), and even 100% line coverage != 100% test coverage. But it's a very good first stop to see glaring omissions. E.g. the refs.c cases I mentioned where we'resetting flag "xyz" in a() and then acting on "xyz/!xyz" in b().

1. <[email protected]>

..

..

I think that is an unfair characterization. The API documentation of read_raw_ref_fn says that implementations should return EINVAL for certain cases, so that's what I did. The point of having a documented internal API is that one doesn't have to double check what is behind the API.

--
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays. --

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

I'm only meaning to point out that the behavior being relied on here doesn't have any tests.

I agree that whether or not we should have any tests at all is a matter of opinion and circumstance. I don't think in general that someone using some random internal API needs to be checking what is and isn't tested in that API.

I do think in this case that it's worth digging a bit further. The APIs in question are using EINVAL and EISDIR to pass up errors that are had a 1:1 mapping into the FS historically.

Are we really better off faking those up, or is some of that perhaps not used at all? Maybe we'd find that this level of abstraction isn't what we need, and it could actually be much simpler.

My main goal here is not to keep creating some infinite amount of work for you, but to try to help this along into some shape that's better reviewable & land-able.

It seems to me that a good way to get there is to seek some systematic ways of focusing review onto various edge cases of this series. I.e. to begin with having GIT_TEST_REFTABLE pass as noted elsewhere, and in this case calling attention to some of the underlying assumptions behind this series.

One of the hardest things I've found about trying to review this has been closing the gap between things that exist in your mind and commit messages / code.

E.g. in this case sure, you can be of the opinion that since the point of an internal API is to provide an interface we can simply assume it's OK and working as intended.

I don't think given the history and use of this code that that's an assumption I'd be as comfortable making, but anyway. Getting back on point, I do think whatever opinion anyone is of on that subject having something like this in the commit message (and other applicable commits etc.) would be *very* valuable:

In functions such as git_reftable_read_raw_ref() (and ????, are there more?) we're diligently emulating the documented behavior and return values of the refs file backend. According to "make gcov" we can see we don't have coverage for this, in particular the behavior of EINVAL etc.

I.e. per [1] once if and when we have GIT_TEST_REFTABLE passing surely one of the best way to garner feedback on the rest is to discover those parts (using "make gcov", after running with/without GIT_TEST_REFTABLE=[true|false]) where we still have outstanding blind spots between the tests and code.

1. https://lore.kernel.org/git/[email protected]/

I think none of these error functions are being used at all, and I've made a start at removing them in https://github.com/git/git/pull/1012
(see also my discussion with peff.)

thanks, that is valuable feedback.

I haven't done this, because a lot of these considerations are transient, and I'd rather not spend a lot of time documenting what I don't know.

Getting GIT_TEST_REFTABLE=1 passing is the hard part, because it means having to understand exactly how the current code is supposed to work. Once I get to that point (with knowledge being complete and tests passing), it will be easy to document what is happening and why.

I was hoping that by posting these series with known test failures, and questions marked "XXX" in reftable-backend.c, I would get feedback from the other people who know exactly how this part of the code works. But from your mail, I get the sense that nobody understands how the whole picture fits together?

--
Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays. --

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

Almost definitely not. I don't know about you but when I'm looking at code I wrote 6 months ago handling some special case it takes me a while to get up to speed on just knowing what I knew then, and when we're talking about something like refs.c ...

On the topic of the way forward: I for one would very much be for a plan where step 0 is to just a series import the reftable code you have as-is. I.e. we'd include it as an imported external library, maybe have some light test-tool integration and compile it / run its own tests, but not have/advertise the "git init" etc. integration yet.

I.e. my opinion on GIT_TEST_REFTABLE=1 needing to pass is implicit (but I now realize I haven't explicitly said this) on that happening before the tree is in a state where we'd code/doc-wise be in a state of shipping this to users.

Whereas just importing the library != that, and I think we'd be in much better shape if we had it in-tree and would incrementally work on integration from that point, v.s. having more re-rolls of mostly-the-same big codebase being re-submitted.

I'm sure there's some things that'll need to change as we start the test/integration work, e.g. the reflog topic that's been discussed. But that's surely better done as some patches on top of the already-landed library import at this point v.s. trying to get the library perfect before getting it in-tree.

Maybe Junio disagrees, just my 0.02....

:-(

on the bright side, once this is in, the expectations will be much more explicit, because there are two backends that have to work in roughly the same way.

I would really like that too, and I support this way forward. The bulk of the work and problems are in the refs/reftable-backend.c and assorted incompatibilities across the code base. The library itself seems pretty solid at this point.

Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--

Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich

Registergericht und -nummer: Hamburg, HRB 86891

Sitz der Gesellschaft: Hamburg

Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

Different ref backends will have different ways to write out the invalid 00..00 ref when starting a new worktree. Encapsulate this into a function and expose the function in the refs API.

---

Hi Han-Wen,

it's been a while since I looked at git source code, but today is the day! I was actually looking how the refs table work progresses and this patch caught my attention. I think the changes in builtin/worktree.c (that if/else depending on the actual refs backend used)
demonstrate that the refs API layer is leaking implementation details.

What do you think about rolling this patch first, and then implementing the following part inside the reftable as a function?

int reftable_write_invalid_head_ref(struct *ref_store, const char *dir)

{
	struct sb  = STRBUF_INIT;
	/* the following adapted from this patch: */

+ /* XXX this is cut & paste from reftable_init_db. */
+ strbuf_addf(&sb, "%s/HEAD", dir);
+ write_file(sb.buf, "%s", "ref: refs/heads/.invalid\n");
+ strbuf_reset(&sb);
+
+ strbuf_addf(&sb, "%s/refs", sb_repo.buf);
+ safe_create_dir(sb.buf, 1);
+ strbuf_reset(&sb);
+
+ strbuf_addf(&sb, "%s/refs/heads", sb_repo.buf);
+ write_file(sb.buf, "this repository uses the reftable format");
+ strbuf_reset(&sb);
+
+ strbuf_addf(&sb, "%s/reftable", sb_repo.buf);
+ safe_create_dir(sb.buf, 1);
+ strbuf_reset(&sb);

	return 0;
}

What do you think?

Cheers,
Stefan

 builtin/worktree.c    |  6 +++---
 refs.c                |  5 +++++
 refs.h                |  3 +++
 refs/debug.c          | 10 ++++++++++
 refs/files-backend.c  | 13 +++++++++++++
 refs/packed-backend.c |  7 +++++++
 refs/refs-internal.h  |  3 +++
 7 files changed, 44 insertions(+), 3 deletions(-)

index 1cd5c2016e..6f5d79e5ec 100644
@@ -330,9 +330,9 @@ static int add_worktree(const char *path, const char *refname,
 	 * worktree.
 	 */
 	strbuf_reset(&sb);
-	strbuf_addf(&sb, "%s/HEAD", sb_repo.buf);
-	write_file(sb.buf, "%s", oid_to_hex(&null_oid));
-	strbuf_reset(&sb);
+
+	write_invalid_head(get_main_ref_store(the_repository), sb_repo.buf);
+
 	strbuf_addf(&sb, "%s/commondir", sb_repo.buf);
 	write_file(sb.buf, "../..");
 

index a665ed5e10..a7b415c386 100644
@@ -2454,3 +2454,8 @@ int copy_existing_ref(const char *oldref, const char *newref, const char *logmsg
 {
 	return refs_copy_existing_ref(get_main_ref_store(the_repository), oldref, newref, logmsg);
 }
+
+int write_invalid_head(struct ref_store *refs, const char *dir)
+{
+	return refs->be->write_invalid_head_ref(refs, dir);
+}

index 48970dfc7e..7a64f777d5 100644
@@ -456,6 +456,9 @@ int refs_delete_refs(struct ref_store *refs, const char *msg,
 int delete_refs(const char *msg, struct string_list *refnames,
 		unsigned int flags);
 
+
+int write_invalid_head(struct ref_store *refs, const char *dir);
+
 /** Delete a reflog */
 int refs_delete_reflog(struct ref_store *refs, const char *refname);
 int delete_reflog(const char *refname);

index 922e64fa6a..9cfc3ca9f3 100644
@@ -175,6 +175,15 @@ static int debug_copy_ref(struct ref_store *ref_store, const char *oldref,
 	return res;
 }
 
+static int debug_write_invalid_head_ref(struct ref_store *ref_store,
+					const char *dir)
+{
+	struct debug_ref_store *drefs = (struct debug_ref_store *)ref_store;
+	int res = drefs->refs->be->write_invalid_head_ref(drefs->refs, dir);
+	trace_printf_key(&trace_refs, "write_invalid_head: %s\n", dir);
+	return res;
+}
+
 struct debug_ref_iterator {
 	struct ref_iterator base;
 	struct ref_iterator *iter;

@@ -384,6 +393,7 @@ struct ref_storage_be refs_be_debug = {
 	debug_delete_refs,
 	debug_rename_ref,
 	debug_copy_ref,
+	debug_write_invalid_head_ref,
 
 	debug_ref_iterator_begin,
 	debug_read_raw_ref,

index 4fdc68810b..b1c82a6f61 100644
@@ -3169,6 +3169,18 @@ static int files_init_db(struct ref_store *ref_store, struct strbuf *err)
 	return 0;
 }
 
+static int files_write_invalid_head_ref(struct ref_store *ref_store,
+					const char *dir)
+{
+	struct strbuf sb = STRBUF_INIT;
+
+	strbuf_addf(&sb, "%s/HEAD", dir);
+	write_file(sb.buf, "%s", oid_to_hex(&null_oid));
+	strbuf_release(&sb);
+
+	return 0;
+}
+
 struct ref_storage_be refs_be_files = {
 	NULL,
 	"files",

@@ -3184,6 +3196,7 @@ struct ref_storage_be refs_be_files = {
 	files_delete_refs,
 	files_rename_ref,
 	files_copy_ref,
+	files_write_invalid_head_ref,
 
 	files_ref_iterator_begin,
 	files_read_raw_ref,

index b912f2505f..a1adb81777 100644
@@ -1591,6 +1591,12 @@ static int packed_copy_ref(struct ref_store *ref_store,
 	BUG("packed reference store does not support copying references");
 }
 
+static int packed_write_invalid_head_ref(struct ref_store *ref_store,
+					 const char *dir)
+{
+	BUG("packed reference store does not support writing an invalid head ref");
+}
+
 static struct ref_iterator *packed_reflog_iterator_begin(struct ref_store *ref_store)
 {
 	return empty_ref_iterator_begin();

@@ -1656,6 +1662,7 @@ struct ref_storage_be refs_be_packed = {
 	packed_delete_refs,
 	packed_rename_ref,
 	packed_copy_ref,
+	packed_write_invalid_head_ref,
 
 	packed_ref_iterator_begin,
 	packed_read_raw_ref,

index 467f4b3c93..5055226f75 100644
@@ -556,6 +556,8 @@ typedef int rename_ref_fn(struct ref_store *ref_store,
 typedef int copy_ref_fn(struct ref_store *ref_store,
 			  const char *oldref, const char *newref,
 			  const char *logmsg);
+typedef int write_invalid_head_ref_fn(struct ref_store *ref_store,
+				      const char *dir);
 
 /*
  * Iterate over the references in `ref_store` whose names start with

@@ -655,6 +657,7 @@ struct ref_storage_be {
 	delete_refs_fn *delete_refs;
 	rename_ref_fn *rename_ref;
 	copy_ref_fn *copy_ref;
+	write_invalid_head_ref_fn *write_invalid_head_ref;
 
 	ref_iterator_begin_fn *iterator_begin;
 	read_raw_ref_fn *read_raw_ref;

2.26.2.266.ge870325ee8

Welcome back. I have a few comments in response to this proposal. See below...

    strbuf_release(&sb);

    write_invalid_head(..., sb_repo.buf);

    strbuf_add(&sb, ...);

    write_invalid_head(..., sb_repo.buf);

    strbuf_release(&sb);
    strbuf_add(&sb, ...);

By the way, the only reason the hack of creating a temporary HEAD (containing arbitrary OID) is needed is that add_worktree() shells out to invoke one of git-update-ref or git-symbolic-ref. It is that shell-out to invoke a Git command which triggers the necessity of pacifying is_git_directory()...

... so, a much cleaner fix would be to stop shelling out to set up HEAD in the newly-created worktree, and instead call C API to perform those functions (update-ref and symbolic-ref) directly. If that C API does not yet exist, then it should be added.

The "invalid HEAD" hack is there to avoid confusing historical git implementations. It's not a part of the "modern" refs API layer, so I think we shouldn't add it as a method on the ref backend API.

Han-Wen Nienhuys - Google Munich
I work 80%. Don't expect answers from me on Fridays.
--
Google Germany GmbH, Erika-Mann-Strasse 33, 80636 Munich
Registergericht und -nummer: Hamburg, HRB 86891
Sitz der Gesellschaft: Hamburg
Geschäftsführer: Paul Manicle, Halimah DeLaine Prado

From: =?UTF-8?q?SZEDER=20G=C3=A1bor?= <[email protected]>

In our git-prompt script we strive to use Bash builtins wherever possible, because fork()-ing subshells for command substitutions and fork()+exec()-ing Git commands are expensive on some platforms. We even read and parse '.git/HEAD' using Bash builtins to get the name of the current branch [1]. However, the upcoming reftable refs backend won't use '.git/HEAD' at all, but will write an invalid refname as placeholder for backwards compatibility instead, which will break our git-prompt script.

Update the git-prompt script to recognize the placeholder '.git/HEAD' written by the reftable backend (its content is specified in the reftable specs), and then fall back to use 'git symbolic-ref' to get the name of the current branch.

[1] 3a43c4b5bd (bash prompt: use bash builtins to find out current

    branch, 2011-03-31)

---
 contrib/completion/git-prompt.sh | 7 ++++++-
 1 file changed, 6 insertions(+), 1 deletion(-)

index 4640a1535d1..2e5a5d80271 100644
@@ -478,10 +478,15 @@ __git_ps1 ()
 			if ! __git_eread "$g/HEAD" head; then
 				return $exit
 			fi
-			# is it a symbolic ref?
 			b="${head#ref: }"
 			if [ "$head" = "$b" ]; then
 				detached=yes
+			elif [ "$b" = "refs/heads/.invalid" ]; then
+				# Reftable
+				b="$(git symbolic-ref HEAD 2>/dev/null)" ||
+				detached=yes
+			fi
+			if [ "$detached" = yes ]; then
 				b="$(
 				case "${GIT_PS1_DESCRIBE_STYLE-}" in
 				(contains)

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This command dumps individual tables or a stack of of tables.

---
 Makefile                 |  1 +
 reftable/dump.c          | 67 ++++++++++++++++++++--------------------
 t/helper/test-reftable.c |  5 +++
 t/helper/test-tool.c     |  1 +
 t/helper/test-tool.h     |  1 +
 5 files changed, 42 insertions(+), 33 deletions(-)

index 6b7c8a165f4..2f9bf61fffb 100644
@@ -2409,6 +2409,7 @@ REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/basics_test.o
 REFTABLE_TEST_OBJS += reftable/block_test.o
+REFTABLE_TEST_OBJS += reftable/dump.o
 REFTABLE_TEST_OBJS += reftable/merged_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/refname_test.o

index 3b702f4855e..c1ba131c3a4 100644
@@ -13,3 +13,8 @@ int cmd__reftable(int argc, const char **argv)
 	tree_test_main(argc, argv);
 	return 0;
 }
+
+int cmd__dump_reftable(int argc, const char **argv)
+{
+	return reftable_dump_main(argc, (char *const *)argv);
+}

index 0208a0a41cf..f064440a319 100644
@@ -56,6 +56,7 @@ static struct test_cmd cmds[] = {
 	{ "read-midx", cmd__read_midx },
 	{ "ref-store", cmd__ref_store },
 	{ "reftable", cmd__reftable },
+	{ "dump-reftable", cmd__dump_reftable },
 	{ "regex", cmd__regex },
 	{ "repository", cmd__repository },
 	{ "revision-walking", cmd__revision_walking },

index 1de39ce5b58..226af8c6b89 100644
@@ -18,6 +18,7 @@ int cmd__dump_cache_tree(int argc, const char **argv);
 int cmd__dump_fsmonitor(int argc, const char **argv);
 int cmd__dump_split_index(int argc, const char **argv);
 int cmd__dump_untracked_cache(int argc, const char **argv);
+int cmd__dump_reftable(int argc, const char **argv);
 int cmd__example_decorate(int argc, const char **argv);
 int cmd__fast_rebase(int argc, const char **argv);
 int cmd__genrandom(int argc, const char **argv);

gitgitgadget

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

The final commit should also be split up, but I want to wait until we have consensus that the bottom commits look good.

version 12 Mar 2021:

* tagged unions for reftable_log_record
* some fixups by jun

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

Han-Wen Nienhuys (14):
init-db: set the_repository->hash_algo early on
reftable: add LICENSE
reftable: add error related functionality
reftable: utility functions
reftable: add blocksource, an abstraction for random access reads
reftable: (de)serialization for the polymorphic record type.
reftable: reading/writing blocks
reftable: a generic binary tree implementation
reftable: write reftable files
reftable: read reftable files
reftable: reftable file level tests
reftable: rest of library
Reftable support for git-core
Add "test-tool dump-reftable" command.

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

 Documentation/config/extensions.txt           |    9 +
 .../technical/repository-version.txt          |    7 +
 Makefile                                      |   46 +-
 builtin/clone.c                               |    5 +-
 builtin/init-db.c                             |   76 +-
 builtin/worktree.c                            |   27 +-
 cache.h                                       |    8 +-
 config.mak.uname                              |    2 +-
 contrib/buildsystems/CMakeLists.txt           |   14 +-
 contrib/buildsystems/Generators/Vcxproj.pm    |   11 +-
 contrib/completion/git-prompt.sh              |    7 +-
 refs.c                                        |   27 +-
 refs.h                                        |    3 +
 refs/refs-internal.h                          |    1 +
 refs/reftable-backend.c                       | 1446 +++++++++++++++++
 reftable/.gitattributes                       |    1 +
 reftable/LICENSE                              |   31 +
 reftable/VERSION                              |    1 +
 reftable/basics.c                             |  128 ++
 reftable/basics.h                             |   60 +
 reftable/basics_test.c                        |   98 ++
 reftable/block.c                              |  440 +++++
 reftable/block.h                              |  127 ++
 reftable/block_test.c                         |  121 ++
 reftable/blocksource.c                        |  148 ++
 reftable/blocksource.h                        |   22 +
 reftable/constants.h                          |   21 +
 reftable/dump.c                               |  213 +++
 reftable/error.c                              |   41 +
 reftable/iter.c                               |  248 +++
 reftable/iter.h                               |   75 +
 reftable/merged.c                             |  366 +++++
 reftable/merged.h                             |   35 +
 reftable/merged_test.c                        |  343 ++++
 reftable/pq.c                                 |  115 ++
 reftable/pq.h                                 |   32 +
 reftable/publicbasics.c                       |   58 +
 reftable/reader.c                             |  733 +++++++++
 reftable/reader.h                             |   75 +
 reftable/record.c                             | 1203 ++++++++++++++
 reftable/record.h                             |  139 ++
 reftable/record_test.c                        |  405 +++++
 reftable/refname.c                            |  209 +++
 reftable/refname.h                            |   29 +
 reftable/refname_test.c                       |  102 ++
 reftable/reftable-blocksource.h               |   49 +
 reftable/reftable-error.h                     |   62 +
 reftable/reftable-generic.h                   |   48 +
 reftable/reftable-iterator.h                  |   37 +
 reftable/reftable-malloc.h                    |   18 +
 reftable/reftable-merged.h                    |   68 +
 reftable/reftable-reader.h                    |   89 +
 reftable/reftable-record.h                    |  114 ++
 reftable/reftable-stack.h                     |  120 ++
 reftable/reftable-tests.h                     |   22 +
 reftable/reftable-writer.h                    |  147 ++
 reftable/reftable.c                           |   98 ++
 reftable/reftable_test.c                      |  583 +++++++
 reftable/stack.c                              | 1260 ++++++++++++++
 reftable/stack.h                              |   41 +
 reftable/stack_test.c                         |  809 +++++++++
 reftable/system.h                             |   32 +
 reftable/test_framework.c                     |   23 +
 reftable/test_framework.h                     |   53 +
 reftable/tree.c                               |   63 +
 reftable/tree.h                               |   34 +
 reftable/tree_test.c                          |   61 +
 reftable/writer.c                             |  691 ++++++++
 reftable/writer.h                             |   50 +
 reftable/zlib-compat.c                        |   92 ++
 repository.c                                  |    2 +
 repository.h                                  |    3 +
 setup.c                                       |    9 +-
 t/helper/test-reftable.c                      |   20 +
 t/helper/test-tool.c                          |    4 +-
 t/helper/test-tool.h                          |    2 +
 t/t0031-reftable.sh                           |  203 +++
 t/t0032-reftable-unittest.sh                  |   15 +
 t/t1409-avoid-packing-refs.sh                 |    6 +
 t/t1450-fsck.sh                               |    6 +
 t/t3210-pack-refs.sh                          |    6 +
 t/test-lib.sh                                 |    5 +
 82 files changed, 12213 insertions(+), 40 deletions(-)
 create mode 100644 refs/reftable-backend.c
 create mode 100644 reftable/.gitattributes
 create mode 100644 reftable/LICENSE
 create mode 100644 reftable/VERSION
 create mode 100644 reftable/basics.c
 create mode 100644 reftable/basics.h
 create mode 100644 reftable/basics_test.c
 create mode 100644 reftable/block.c
 create mode 100644 reftable/block.h
 create mode 100644 reftable/block_test.c
 create mode 100644 reftable/blocksource.c
 create mode 100644 reftable/blocksource.h
 create mode 100644 reftable/constants.h
 create mode 100644 reftable/dump.c
 create mode 100644 reftable/error.c
 create mode 100644 reftable/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/publicbasics.c
 create mode 100644 reftable/reader.c
 create mode 100644 reftable/reader.h
 create mode 100644 reftable/record.c
 create mode 100644 reftable/record.h
 create mode 100644 reftable/record_test.c
 create mode 100644 reftable/refname.c
 create mode 100644 reftable/refname.h
 create mode 100644 reftable/refname_test.c
 create mode 100644 reftable/reftable-blocksource.h
 create mode 100644 reftable/reftable-error.h
 create mode 100644 reftable/reftable-generic.h
 create mode 100644 reftable/reftable-iterator.h
 create mode 100644 reftable/reftable-malloc.h
 create mode 100644 reftable/reftable-merged.h
 create mode 100644 reftable/reftable-reader.h
 create mode 100644 reftable/reftable-record.h
 create mode 100644 reftable/reftable-stack.h
 create mode 100644 reftable/reftable-tests.h
 create mode 100644 reftable/reftable-writer.h
 create mode 100644 reftable/reftable.c
 create mode 100644 reftable/reftable_test.c
 create mode 100644 reftable/stack.c
 create mode 100644 reftable/stack.h
 create mode 100644 reftable/stack_test.c
 create mode 100644 reftable/system.h
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h
 create mode 100644 reftable/tree.c
 create mode 100644 reftable/tree.h
 create mode 100644 reftable/tree_test.c
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c
 create mode 100644 t/helper/test-reftable.c
 create mode 100755 t/t0031-reftable.sh
 create mode 100755 t/t0032-reftable-unittest.sh

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

Range-diff vs v4:

1: 40ac041d0efe ! 1: e1d1d9f49807 init-db: set the_repository->hash_algo early on
@@ builtin/init-db.c: int init_db(const char *git_dir, const char *real_git_dir,
+ repo_set_hash_algo(the_repository, repo_fmt.hash_algo);
+
reinit = create_default_files(template_dir, original_git_dir,
- initial_branch, &repo_fmt);
- if (reinit && initial_branch)
+ initial_branch, &repo_fmt,
+ flags & INIT_DB_QUIET);

  2:  cc0fe58bd333 =  2:  502a66befabe reftable: add LICENSE
  3:  798f680b800b =  3:  1bd136f6a6df reftable: add error related functionality
  4:  2f55ff6d2406 !  4:  5bbbafb428e9 reftable: utility functions
     @@ t/helper/test-reftable.c (new)
      
       ## t/helper/test-tool.c ##
      @@ t/helper/test-tool.c: static struct test_cmd cmds[] = {
     - 	{ "path-utils", cmd__path_utils },
     + 	{ "pcre2-config", cmd__pcre2_config },
       	{ "pkt-line", cmd__pkt_line },
       	{ "prio-queue", cmd__prio_queue },
      -	{ "proc-receive", cmd__proc_receive},
  5:  aaa817f8598b =  5:  e41fa780882d reftable: add blocksource, an abstraction for random access reads
  6:  e13afe315258 !  6:  390eaca4fc8c reftable: (de)serialization for the polymorphic record type.
     @@ reftable/record.c (new)
      +{
      +	char hex[SHA256_SIZE + 1] = { 0 };
      +
     -+	printf("log{%s(%" PRIu64 ") %s <%s> %" PRIu64 " %04d\n", log->refname,
     -+	       log->update_index, log->name, log->email, log->time,
     -+	       log->tz_offset);
     -+	hex_format(hex, log->old_hash, hash_size(hash_id));
     -+	printf("%s => ", hex);
     -+	hex_format(hex, log->new_hash, hash_size(hash_id));
     -+	printf("%s\n\n%s\n}\n", hex, log->message);
     ++	switch (log->value_type) {
     ++	case REFTABLE_LOG_DELETION:
     ++		printf("log{%s(%" PRIu64 ") delete", log->refname,
     ++		       log->update_index);
     ++		break;
     ++	case REFTABLE_LOG_UPDATE:
     ++		printf("log{%s(%" PRIu64 ") %s <%s> %" PRIu64 " %04d\n",
     ++		       log->refname, log->update_index, log->update.name,
     ++		       log->update.email, log->update.time,
     ++		       log->update.tz_offset);
     ++		hex_format(hex, log->update.old_hash, hash_size(hash_id));
     ++		printf("%s => ", hex);
     ++		hex_format(hex, log->update.new_hash, hash_size(hash_id));
     ++		printf("%s\n\n%s\n}\n", hex, log->update.message);
     ++		break;
     ++	}
      +}
      +
      +static void reftable_log_record_key(const void *r, struct strbuf *dest)
     @@ reftable/record.c (new)
      +	if (dst->refname != NULL) {
      +		dst->refname = xstrdup(dst->refname);
      +	}
     -+	if (dst->email != NULL) {
     -+		dst->email = xstrdup(dst->email);
     -+	}
     -+	if (dst->name != NULL) {
     -+		dst->name = xstrdup(dst->name);
     -+	}
     -+	if (dst->message != NULL) {
     -+		dst->message = xstrdup(dst->message);
     -+	}
     ++	switch (dst->value_type) {
     ++	case REFTABLE_LOG_DELETION:
     ++		break;
     ++	case REFTABLE_LOG_UPDATE:
     ++		if (dst->update.email != NULL) {
     ++			dst->update.email = xstrdup(dst->update.email);
     ++		}
     ++		if (dst->update.name != NULL) {
     ++			dst->update.name = xstrdup(dst->update.name);
     ++		}
     ++		if (dst->update.message != NULL) {
     ++			dst->update.message = xstrdup(dst->update.message);
     ++		}
      +
     -+	if (dst->new_hash != NULL) {
     -+		dst->new_hash = reftable_malloc(hash_size);
     -+		memcpy(dst->new_hash, src->new_hash, hash_size);
     -+	}
     -+	if (dst->old_hash != NULL) {
     -+		dst->old_hash = reftable_malloc(hash_size);
     -+		memcpy(dst->old_hash, src->old_hash, hash_size);
     ++		if (dst->update.new_hash != NULL) {
     ++			dst->update.new_hash = reftable_malloc(hash_size);
     ++			memcpy(dst->update.new_hash, src->update.new_hash,
     ++			       hash_size);
     ++		}
     ++		if (dst->update.old_hash != NULL) {
     ++			dst->update.old_hash = reftable_malloc(hash_size);
     ++			memcpy(dst->update.old_hash, src->update.old_hash,
     ++			       hash_size);
     ++		}
     ++		break;
      +	}
      +}
      +
     @@ reftable/record.c (new)
      +void reftable_log_record_release(struct reftable_log_record *r)
      +{
      +	reftable_free(r->refname);
     -+	reftable_free(r->new_hash);
     -+	reftable_free(r->old_hash);
     -+	reftable_free(r->name);
     -+	reftable_free(r->email);
     -+	reftable_free(r->message);
     ++	switch (r->value_type) {
     ++	case REFTABLE_LOG_DELETION:
     ++		break;
     ++	case REFTABLE_LOG_UPDATE:
     ++		reftable_free(r->update.new_hash);
     ++		reftable_free(r->update.old_hash);
     ++		reftable_free(r->update.name);
     ++		reftable_free(r->update.email);
     ++		reftable_free(r->update.message);
     ++		break;
     ++	}
      +	memset(r, 0, sizeof(struct reftable_log_record));
      +}
      +
     @@ reftable/record.c (new)
      +	struct reftable_log_record *r = (struct reftable_log_record *)rec;
      +	struct string_view start = s;
      +	int n = 0;
     -+	uint8_t *oldh = r->old_hash;
     -+	uint8_t *newh = r->new_hash;
     ++	uint8_t *oldh = NULL;
     ++	uint8_t *newh = NULL;
      +	if (reftable_log_record_is_deletion(r))
      +		return 0;
      +
     ++	oldh = r->update.old_hash;
     ++	newh = r->update.new_hash;
      +	if (oldh == NULL) {
      +		oldh = zero;
      +	}
     @@ reftable/record.c (new)
      +	memcpy(s.buf + hash_size, newh, hash_size);
      +	string_view_consume(&s, 2 * hash_size);
      +
     -+	n = encode_string(r->name ? r->name : "", s);
     ++	n = encode_string(r->update.name ? r->update.name : "", s);
      +	if (n < 0)
      +		return -1;
      +	string_view_consume(&s, n);
      +
     -+	n = encode_string(r->email ? r->email : "", s);
     ++	n = encode_string(r->update.email ? r->update.email : "", s);
      +	if (n < 0)
      +		return -1;
      +	string_view_consume(&s, n);
      +
     -+	n = put_var_int(&s, r->time);
     ++	n = put_var_int(&s, r->update.time);
      +	if (n < 0)
      +		return -1;
      +	string_view_consume(&s, n);
     @@ reftable/record.c (new)
      +	if (s.len < 2)
      +		return -1;
      +
     -+	put_be16(s.buf, r->tz_offset);
     ++	put_be16(s.buf, r->update.tz_offset);
      +	string_view_consume(&s, 2);
      +
     -+	n = encode_string(r->message ? r->message : "", s);
     ++	n = encode_string(r->update.message ? r->update.message : "", s);
      +	if (n < 0)
      +		return -1;
      +	string_view_consume(&s, n);
     @@ reftable/record.c (new)
      +
      +	r->update_index = (~max) - ts;
      +
     -+	if (val_type == 0) {
     -+		FREE_AND_NULL(r->old_hash);
     -+		FREE_AND_NULL(r->new_hash);
     -+		FREE_AND_NULL(r->message);
     -+		FREE_AND_NULL(r->email);
     -+		FREE_AND_NULL(r->name);
     -+		return 0;
     ++	if (val_type != r->value_type) {
     ++		switch (r->value_type) {
     ++		case REFTABLE_LOG_UPDATE:
     ++			FREE_AND_NULL(r->update.old_hash);
     ++			FREE_AND_NULL(r->update.new_hash);
     ++			FREE_AND_NULL(r->update.message);
     ++			FREE_AND_NULL(r->update.email);
     ++			FREE_AND_NULL(r->update.name);
     ++			break;
     ++		case REFTABLE_LOG_DELETION:
     ++			break;
     ++		}
      +	}
      +
     ++	r->value_type = val_type;
     ++	if (val_type == REFTABLE_LOG_DELETION)
     ++		return 0;
     ++
      +	if (in.len < 2 * hash_size)
      +		return REFTABLE_FORMAT_ERROR;
      +
     -+	r->old_hash = reftable_realloc(r->old_hash, hash_size);
     -+	r->new_hash = reftable_realloc(r->new_hash, hash_size);
     ++	r->update.old_hash = reftable_realloc(r->update.old_hash, hash_size);
     ++	r->update.new_hash = reftable_realloc(r->update.new_hash, hash_size);
      +
     -+	memcpy(r->old_hash, in.buf, hash_size);
     -+	memcpy(r->new_hash, in.buf + hash_size, hash_size);
     ++	memcpy(r->update.old_hash, in.buf, hash_size);
     ++	memcpy(r->update.new_hash, in.buf + hash_size, hash_size);
      +
      +	string_view_consume(&in, 2 * hash_size);
      +
     @@ reftable/record.c (new)
      +		goto done;
      +	string_view_consume(&in, n);
      +
     -+	r->name = reftable_realloc(r->name, dest.len + 1);
     -+	memcpy(r->name, dest.buf, dest.len);
     -+	r->name[dest.len] = 0;
     ++	r->update.name = reftable_realloc(r->update.name, dest.len + 1);
     ++	memcpy(r->update.name, dest.buf, dest.len);
     ++	r->update.name[dest.len] = 0;
      +
      +	strbuf_reset(&dest);
      +	n = decode_string(&dest, in);
     @@ reftable/record.c (new)
      +		goto done;
      +	string_view_consume(&in, n);
      +
     -+	r->email = reftable_realloc(r->email, dest.len + 1);
     -+	memcpy(r->email, dest.buf, dest.len);
     -+	r->email[dest.len] = 0;
     ++	r->update.email = reftable_realloc(r->update.email, dest.len + 1);
     ++	memcpy(r->update.email, dest.buf, dest.len);
     ++	r->update.email[dest.len] = 0;
      +
      +	ts = 0;
      +	n = get_var_int(&ts, &in);
      +	if (n < 0)
      +		goto done;
      +	string_view_consume(&in, n);
     -+	r->time = ts;
     ++	r->update.time = ts;
      +	if (in.len < 2)
      +		goto done;
      +
     -+	r->tz_offset = get_be16(in.buf);
     ++	r->update.tz_offset = get_be16(in.buf);
      +	string_view_consume(&in, 2);
      +
      +	strbuf_reset(&dest);
     @@ reftable/record.c (new)
      +		goto done;
      +	string_view_consume(&in, n);
      +
     -+	r->message = reftable_realloc(r->message, dest.len + 1);
     -+	memcpy(r->message, dest.buf, dest.len);
     -+	r->message[dest.len] = 0;
     ++	r->update.message = reftable_realloc(r->update.message, dest.len + 1);
     ++	memcpy(r->update.message, dest.buf, dest.len);
     ++	r->update.message[dest.len] = 0;
      +
      +	strbuf_release(&dest);
      +	return start.len - in.len;
     @@ reftable/record.c (new)
      +int reftable_log_record_equal(struct reftable_log_record *a,
      +			      struct reftable_log_record *b, int hash_size)
      +{
     -+	return null_streq(a->name, b->name) && null_streq(a->email, b->email) &&
     -+	       null_streq(a->message, b->message) &&
     -+	       zero_hash_eq(a->old_hash, b->old_hash, hash_size) &&
     -+	       zero_hash_eq(a->new_hash, b->new_hash, hash_size) &&
     -+	       a->time == b->time && a->tz_offset == b->tz_offset &&
     -+	       a->update_index == b->update_index;
     ++	if (!(null_streq(a->refname, b->refname) &&
     ++	      a->update_index == b->update_index &&
     ++	      a->value_type == b->value_type))
     ++		return 0;
     ++
     ++	switch (a->value_type) {
     ++	case REFTABLE_LOG_DELETION:
     ++		return 1;
     ++	case REFTABLE_LOG_UPDATE:
     ++		return null_streq(a->update.name, b->update.name) &&
     ++		       a->update.time == b->update.time &&
     ++		       a->update.tz_offset == b->update.tz_offset &&
     ++		       null_streq(a->update.email, b->update.email) &&
     ++		       null_streq(a->update.message, b->update.message) &&
     ++		       zero_hash_eq(a->update.old_hash, b->update.old_hash,
     ++				    hash_size) &&
     ++		       zero_hash_eq(a->update.new_hash, b->update.new_hash,
     ++				    hash_size);
     ++	}
     ++
     ++	abort();
      +}
      +
      +static int reftable_log_record_is_deletion_void(const void *p)
     @@ reftable/record.c (new)
      +
      +int reftable_log_record_is_deletion(const struct reftable_log_record *log)
      +{
     -+	return (log->new_hash == NULL && log->old_hash == NULL &&
     -+		log->name == NULL && log->email == NULL &&
     -+		log->message == NULL && log->time == 0 && log->tz_offset == 0 &&
     -+		log->message == NULL);
     ++	return (log->value_type == REFTABLE_LOG_DELETION);
      +}
      +
      +void string_view_consume(struct string_view *s, int n)
     @@ reftable/record.h (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"
     @@ reftable/record_test.c (new)
      +	struct reftable_log_record in[2] = {
      +		{
      +			.refname = xstrdup("refs/heads/master"),
     -+			.old_hash = reftable_malloc(SHA1_SIZE),
     -+			.new_hash = reftable_malloc(SHA1_SIZE),
     -+			.name = xstrdup("han-wen"),
     -+			.email = xstrdup("[email protected]"),
     -+			.message = xstrdup("test"),
      +			.update_index = 42,
     -+			.time = 1577123507,
     -+			.tz_offset = 100,
     ++			.value_type = REFTABLE_LOG_UPDATE,
     ++			.update = {
     ++				.old_hash = reftable_malloc(SHA1_SIZE),
     ++				.new_hash = reftable_malloc(SHA1_SIZE),
     ++				.name = xstrdup("han-wen"),
     ++				.email = xstrdup("[email protected]"),
     ++				.message = xstrdup("test"),
     ++				.time = 1577123507,
     ++				.tz_offset = 100,
     ++			}
      +		},
      +		{
      +			.refname = xstrdup("refs/heads/master"),
      +			.update_index = 22,
     ++			.value_type = REFTABLE_LOG_DELETION,
      +		}
      +	};
     -+	set_test_hash(in[0].new_hash, 1);
     -+	set_test_hash(in[0].old_hash, 2);
     ++	set_test_hash(in[0].update.new_hash, 1);
     ++	set_test_hash(in[0].update.old_hash, 2);
      +	for (int i = 0; i < ARRAY_SIZE(in); i++) {
      +		struct reftable_record rec = { NULL };
      +		struct strbuf key = STRBUF_INIT;
     @@ reftable/record_test.c (new)
      +		/* populate out, to check for leaks. */
      +		struct reftable_log_record out = {
      +			.refname = 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"),
     ++			.value_type = REFTABLE_LOG_UPDATE,
     ++			.update = {
     ++				.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 = { NULL };
      +		int n, m, valtype;
     @@ reftable/reftable-record.h (new)
      +	char *refname;
      +	uint64_t update_index; /* logical timestamp of a transactional update.
      +				*/
     -+	uint8_t *new_hash;
     -+	uint8_t *old_hash;
     -+	char *name;
     -+	char *email;
     -+	uint64_t time;
     -+	int16_t tz_offset;
     -+	char *message;
     ++
     ++	enum {
     ++		/* tombstone to hide deletions from earlier tables */
     ++		REFTABLE_LOG_DELETION = 0x0,
     ++
     ++		/* a simple update */
     ++		REFTABLE_LOG_UPDATE = 0x1,
     ++#define REFTABLE_NR_LOG_VALUETYPES 2
     ++	} value_type;
     ++
     ++	union {
     ++		struct {
     ++			uint8_t *new_hash;
     ++			uint8_t *old_hash;
     ++			char *name;
     ++			char *email;
     ++			uint64_t time;
     ++			int16_t tz_offset;
     ++			char *message;
     ++		} update;
     ++	};
      +};
      +
      +/* returns whether 'ref' represents the deletion of a log record. */
  7:  a48b9937642e =  7:  b108525009d9 reftable: reading/writing blocks
  8:  6968dbc3828f =  8:  b6eed7283aac reftable: a generic binary tree implementation
  9:  ff5b424d12fb !  9:  f2f005afca19 reftable: write reftable files
     @@ reftable/writer.c (new)
      +	return err;
      +}
      +
     -+int reftable_writer_add_log(struct reftable_writer *w,
     -+			    struct reftable_log_record *log)
     ++static int reftable_writer_add_log_verbatim(struct reftable_writer *w,
     ++					    struct reftable_log_record *log)
      +{
      +	struct reftable_record rec = { NULL };
     -+	char *input_log_message = log->message;
     -+	struct strbuf cleaned_message = STRBUF_INIT;
     -+	int err;
     -+	if (log->refname == NULL)
     -+		return REFTABLE_API_ERROR;
     -+
      +	if (w->block_writer != NULL &&
      +	    block_writer_type(w->block_writer) == BLOCK_TYPE_REF) {
      +		int err = writer_finish_public_section(w);
     @@ reftable/writer.c (new)
      +			return err;
      +	}
      +
     -+	if (!w->opts.exact_log_message && log->message != NULL) {
     -+		strbuf_addstr(&cleaned_message, log->message);
     ++	w->next -= w->pending_padding;
     ++	w->pending_padding = 0;
     ++
     ++	reftable_record_from_log(&rec, log);
     ++	return writer_add_record(w, &rec);
     ++}
     ++
     ++int reftable_writer_add_log(struct reftable_writer *w,
     ++			    struct reftable_log_record *log)
     ++{
     ++	char *input_log_message = NULL;
     ++	struct strbuf cleaned_message = STRBUF_INIT;
     ++	int err = 0;
     ++
     ++	if (log->value_type == REFTABLE_LOG_DELETION)
     ++		return reftable_writer_add_log_verbatim(w, log);
     ++
     ++	if (log->refname == NULL)
     ++		return REFTABLE_API_ERROR;
     ++
     ++	input_log_message = log->update.message;
     ++	if (!w->opts.exact_log_message && log->update.message != NULL) {
     ++		strbuf_addstr(&cleaned_message, log->update.message);
      +		while (cleaned_message.len &&
      +		       cleaned_message.buf[cleaned_message.len - 1] == '\n')
      +			strbuf_setlen(&cleaned_message,
     @@ reftable/writer.c (new)
      +			goto done;
      +		}
      +		strbuf_addstr(&cleaned_message, "\n");
     -+		log->message = cleaned_message.buf;
     ++		log->update.message = cleaned_message.buf;
      +	}
      +
     -+	w->next -= w->pending_padding;
     -+	w->pending_padding = 0;
     -+
     -+	reftable_record_from_log(&rec, log);
     -+	err = writer_add_record(w, &rec);
     -+
     ++	err = reftable_writer_add_log_verbatim(w, log);
     ++	log->update.message = input_log_message;
      +done:
     -+	log->message = input_log_message;
      +	strbuf_release(&cleaned_message);
      +	return err;
      +}
 10:  3c2de7dcc65c = 10:  1f17d5edab52 reftable: read reftable files
 11:  03681b820d13 ! 11:  c916629c562a reftable: reftable file level tests
     @@ reftable/reftable_test.c (new)
      +		snprintf(name, sizeof(name), "refs/heads/branch%02d", i);
      +
      +		log.refname = name;
     -+		log.new_hash = hash;
      +		log.update_index = update_index;
     -+		log.message = "message";
     ++		log.value_type = REFTABLE_LOG_UPDATE;
     ++		log.update.new_hash = hash;
     ++		log.update.message = "message";
      +
      +		n = reftable_writer_add_log(w, &log);
      +		EXPECT(n == 0);
     @@ reftable/reftable_test.c (new)
      +		.block_size = 4096,
      +	};
      +	int err;
     -+	struct reftable_log_record log = {
     -+		.refname = "refs/heads/master",
     -+		.name = "Han-Wen Nienhuys",
     -+		.email = "[email protected]",
     -+		.tz_offset = 100,
     -+		.time = 0x5e430672,
     -+		.update_index = 0xa,
     -+		.message = "commit: 9\n",
     -+	};
     ++	struct reftable_log_record log = { .refname = "refs/heads/master",
     ++					   .update_index = 0xa,
     ++					   .value_type = REFTABLE_LOG_UPDATE,
     ++					   .update = {
     ++						   .name = "Han-Wen Nienhuys",
     ++						   .email = "[email protected]",
     ++						   .tz_offset = 100,
     ++						   .time = 0x5e430672,
     ++						   .message = "commit: 9\n",
     ++					   } };
      +	struct reftable_writer *w =
      +		reftable_new_writer(&strbuf_add_void, &buf, &opts);
      +
     @@ reftable/reftable_test.c (new)
      +		hash1[i] = (uint8_t)(rand() % 256);
      +		hash2[i] = (uint8_t)(rand() % 256);
      +	}
     -+	log.old_hash = hash1;
     -+	log.new_hash = hash2;
     ++	log.update.old_hash = hash1;
     ++	log.update.new_hash = hash2;
      +	reftable_writer_set_limits(w, update_index, update_index);
      +	err = reftable_writer_add_log(w, &log);
      +	EXPECT_ERR(err);
     @@ reftable/reftable_test.c (new)
      +
      +		log.refname = names[i];
      +		log.update_index = i;
     -+		log.old_hash = hash1;
     -+		log.new_hash = hash2;
     ++		log.value_type = REFTABLE_LOG_UPDATE;
     ++		log.update.old_hash = hash1;
     ++		log.update.new_hash = hash2;
      +
      +		err = reftable_writer_add_log(w, &log);
      +		EXPECT_ERR(err);
 12:  557183d3e3e2 ! 12:  28aa69f7bbcb reftable: rest of library
     @@ Makefile: REFTABLE_OBJS += reftable/error.o
      
       ## reftable/VERSION (new) ##
      @@
     -+9b4a54059db9a05c270c0a0587f245bc6868d576 C: use rand() rather than cobbled together random generator.
     ++a337d48d4d42d513d6baa33addc172f0e0e36288 C: use tagged union for reftable_log_record
      
       ## reftable/dump.c (new) ##
      @@
     @@ reftable/stack.c (new)
      +			continue;
      +		}
      +
     -+		if (config != NULL && config->time > 0 &&
     -+		    log.time < config->time) {
     ++		if (config != NULL && config->min_update_index > 0 &&
     ++		    log.update_index < config->min_update_index) {
      +			continue;
      +		}
      +
     -+		if (config != NULL && config->min_update_index > 0 &&
     -+		    log.update_index < config->min_update_index) {
     ++		if (config != NULL && config->time > 0 &&
     ++		    log.update.time < config->time) {
      +			continue;
      +		}
      +
     @@ reftable/stack_test.c (new)
      +
      +		logs[i].refname = 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);
     ++		logs[i].value_type = REFTABLE_LOG_UPDATE;
     ++
     ++		logs[i].update.new_hash = reftable_malloc(SHA1_SIZE);
     ++		logs[i].update.email = xstrdup("identity@invalid");
     ++		set_test_hash(logs[i].update.new_hash, i);
      +	}
      +
      +	for (i = 0; i < N; i++) {
     @@ reftable/stack_test.c (new)
      +
      +	uint8_t h1[SHA1_SIZE] = { 0x01 }, h2[SHA1_SIZE] = { 0x02 };
      +
     -+	struct reftable_log_record input = {
     -+		.refname = "branch",
     -+		.update_index = 1,
     -+		.new_hash = h1,
     -+		.old_hash = h2,
     -+	};
     ++	struct reftable_log_record input = { .refname = "branch",
     ++					     .update_index = 1,
     ++					     .value_type = REFTABLE_LOG_UPDATE,
     ++					     .update = {
     ++						     .new_hash = h1,
     ++						     .old_hash = h2,
     ++					     } };
      +	struct reftable_log_record dest = {
      +		.update_index = 0,
      +	};
     @@ reftable/stack_test.c (new)
      +	err = reftable_new_stack(&st, dir, cfg);
      +	EXPECT_ERR(err);
      +
     -+	input.message = "one\ntwo";
     ++	input.update.message = "one\ntwo";
      +	err = reftable_stack_add(st, &write_test_log, &arg);
      +	EXPECT(err == REFTABLE_API_ERROR);
      +
     -+	input.message = "one";
     ++	input.update.message = "one";
      +	err = reftable_stack_add(st, &write_test_log, &arg);
      +	EXPECT_ERR(err);
      +
      +	err = reftable_stack_read_log(st, input.refname, &dest);
      +	EXPECT_ERR(err);
     -+	EXPECT(0 == strcmp(dest.message, "one\n"));
     ++	EXPECT(0 == strcmp(dest.update.message, "one\n"));
      +
     -+	input.message = "two\n";
     ++	input.update.message = "two\n";
      +	arg.update_index = 2;
      +	err = reftable_stack_add(st, &write_test_log, &arg);
      +	EXPECT_ERR(err);
      +	err = reftable_stack_read_log(st, input.refname, &dest);
      +	EXPECT_ERR(err);
     -+	EXPECT(0 == strcmp(dest.message, "two\n"));
     ++	EXPECT(0 == strcmp(dest.update.message, "two\n"));
      +
      +	/* cleanup */
      +	reftable_stack_destroy(st);
     @@ reftable/stack_test.c (new)
      +			refs[i].value.val1 = reftable_malloc(SHA1_SIZE);
      +			set_test_hash(refs[i].value.val1, i);
      +		}
     ++
      +		logs[i].refname = 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");
     ++			logs[i].value_type = REFTABLE_LOG_UPDATE;
     ++			logs[i].update.new_hash = reftable_malloc(SHA1_SIZE);
     ++			set_test_hash(logs[i].update.new_hash, i);
     ++			logs[i].update.email = xstrdup("identity@invalid");
      +		}
      +	}
      +	for (i = 0; i < N; i++) {
     @@ reftable/stack_test.c (new)
      +
      +		logs[i].refname = 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);
     ++		logs[i].value_type = REFTABLE_LOG_UPDATE;
     ++		logs[i].update.time = i;
     ++		logs[i].update.new_hash = reftable_malloc(SHA1_SIZE);
     ++		logs[i].update.email = xstrdup("identity@invalid");
     ++		set_test_hash(logs[i].update.new_hash, i);
      +	}
      +
      +	for (i = 1; i <= N; i++) {
 13:  d57023d9f13d ! 13:  bdb19af22cc7 Reftable support for git-core
     @@ Commit message
          Signed-off-by: Han-Wen Nienhuys <[email protected]>
          Signed-off-by: Johannes Schindelin <[email protected]>
          Helped-by: Johannes Schindelin <[email protected]>
     +    Helped-by: Junio Hamano <[email protected]>
          Co-authored-by: Jeff King <[email protected]>
      
       ## Documentation/config/extensions.txt ##
     @@ builtin/init-db.c: int cmd_init_db(int argc, const char **argv, const char *pref
      
       ## builtin/worktree.c ##
      @@
     - #include "submodule.h"
       #include "utf8.h"
       #include "worktree.h"
     + #include "quote.h"
      +#include "../refs/refs-internal.h"
       
       static const char * const worktree_usage[] = {
     @@ refs/reftable-backend.c (new)
      +
      +static void clear_reftable_log_record(struct reftable_log_record *log)
      +{
     -+	log->old_hash = NULL;
     -+	log->new_hash = NULL;
     -+	log->message = NULL;
      +	log->refname = NULL;
     ++	switch (log->value_type) {
     ++	case REFTABLE_LOG_UPDATE:
     ++		log->update.old_hash = NULL;
     ++		log->update.new_hash = NULL;
     ++		log->update.message = NULL;
     ++		break;
     ++	case REFTABLE_LOG_DELETION:
     ++		break;
     ++	}
      +	reftable_log_record_release(log);
      +}
      +
     @@ refs/reftable-backend.c (new)
      +	assert(0 == result);
      +
      +	reftable_log_record_release(log);
     -+	log->name =
     ++	log->value_type = REFTABLE_LOG_UPDATE;
     ++	log->update.name =
      +		xstrndup(split.name_begin, split.name_end - split.name_begin);
     -+	log->email =
     ++	log->update.email =
      +		xstrndup(split.mail_begin, split.mail_end - split.mail_begin);
     -+	log->time = atol(split.date_begin);
     ++	log->update.time = atol(split.date_begin);
      +	if (*split.tz_begin == '-') {
      +		sign = -1;
      +		split.tz_begin++;
     @@ refs/reftable-backend.c (new)
      +		split.tz_begin++;
      +	}
      +
     -+	log->tz_offset = sign * atoi(split.tz_begin);
     ++	log->update.tz_offset = sign * atoi(split.tz_begin);
      +}
      +
      +static int has_suffix(struct strbuf *b, const char *suffix)
     @@ refs/reftable-backend.c (new)
      +		struct ref_update *u = sorted[i];
      +		struct reftable_log_record *log = &logs[i];
      +		fill_reftable_log_record(log);
     -+		log->refname = (char *)u->refname;
     -+		log->old_hash = u->old_oid.hash;
     -+		log->new_hash = u->new_oid.hash;
      +		log->update_index = ts;
     -+		log->message = u->msg;
     ++		log->value_type = REFTABLE_LOG_UPDATE;
     ++		log->refname = (char *)u->refname;
     ++		log->update.old_hash = u->old_oid.hash;
     ++		log->update.new_hash = u->new_oid.hash;
     ++		log->update.message = u->msg;
      +
      +		if (u->flags & REF_LOG_ONLY) {
      +			continue;
     @@ refs/reftable-backend.c (new)
      +		};
      +		struct reftable_ref_record current = { NULL };
      +		fill_reftable_log_record(&log);
     -+		log.message = xstrdup(arg->logmsg);
     -+		log.new_hash = NULL;
     -+		log.old_hash = NULL;
      +		log.update_index = ts;
      +		log.refname = (char *)arg->refnames->items[i].string;
      +
     ++		log.update.message = xstrdup(arg->logmsg);
     ++		log.update.new_hash = NULL;
     ++		log.update.old_hash = NULL;
      +		if (reftable_stack_read_ref(arg->stack, log.refname,
      +					    &current) == 0) {
     -+			log.old_hash = reftable_ref_record_val1(&current);
     ++			log.update.old_hash =
     ++				reftable_ref_record_val1(&current);
      +		}
      +		err = reftable_writer_add_log(writer, &log);
     -+		log.old_hash = NULL;
     ++		log.update.old_hash = NULL;
      +		reftable_ref_record_release(&current);
      +
      +		clear_reftable_log_record(&log);
     @@ refs/reftable-backend.c (new)
      +
      +		fill_reftable_log_record(&log);
      +		log.refname = (char *)create->refname;
     -+		log.message = (char *)create->logmsg;
      +		log.update_index = ts;
     ++		log.update.message = (char *)create->logmsg;
      +		if (refs_resolve_ref_unsafe(
      +			    (struct ref_store *)create->refs, create->refname,
      +			    RESOLVE_REF_READING, &old_oid, NULL) != NULL) {
     -+			log.old_hash = old_oid.hash;
     ++			log.update.old_hash = old_oid.hash;
      +		}
      +
      +		if (refs_resolve_ref_unsafe((struct ref_store *)create->refs,
      +					    create->target, RESOLVE_REF_READING,
      +					    &new_oid, NULL) != NULL) {
     -+			log.new_hash = new_oid.hash;
     ++			log.update.new_hash = new_oid.hash;
      +		}
      +
     -+		if (log.old_hash != NULL || log.new_hash != NULL) {
     ++		if (log.update.old_hash != NULL ||
     ++		    log.update.new_hash != NULL) {
      +			err = reftable_writer_add_log(writer, &log);
      +		}
      +		log.refname = NULL;
     -+		log.message = NULL;
     -+		log.old_hash = NULL;
     -+		log.new_hash = NULL;
     ++		log.update.message = NULL;
     ++		log.update.old_hash = NULL;
     ++		log.update.new_hash = NULL;
      +		clear_reftable_log_record(&log);
      +	}
      +	return err;
     @@ refs/reftable-backend.c (new)
      +
      +		todo[0].refname = (char *)arg->oldname;
      +		todo[0].update_index = ts;
     -+		todo[0].message = (char *)arg->logmsg;
     -+		todo[0].old_hash = val1;
     -+		todo[0].new_hash = NULL;
     ++		todo[0].update.message = (char *)arg->logmsg;
     ++		todo[0].update.old_hash = val1;
     ++		todo[0].update.new_hash = NULL;
      +
      +		todo[1].refname = (char *)arg->newname;
      +		todo[1].update_index = ts;
     -+		todo[1].old_hash = NULL;
     -+		todo[1].new_hash = val1;
     -+		todo[1].message = (char *)arg->logmsg;
     ++		todo[1].update.old_hash = NULL;
     ++		todo[1].update.new_hash = val1;
     ++		todo[1].update.message = (char *)arg->logmsg;
      +
      +		err = reftable_writer_add_logs(writer, todo, 2);
      +
     @@ refs/reftable-backend.c (new)
      +
      +		free(ri->last_name);
      +		ri->last_name = xstrdup(ri->log.refname);
     -+		hashcpy(ri->oid.hash, ri->log.new_hash);
     ++		hashcpy(ri->oid.hash, ri->log.update.new_hash);
      +		return ITER_OK;
      +	}
      +}
     @@ refs/reftable-backend.c (new)
      +static struct ref_iterator *
      +git_reftable_reflog_iterator_begin(struct ref_store *ref_store)
      +{
     -+	struct git_reftable_reflog_ref_iterator *ri = xcalloc(sizeof(*ri), 1);
     ++	struct git_reftable_reflog_ref_iterator *ri = xcalloc(1, sizeof(*ri));
      +	struct git_reftable_ref_store *refs =
      +		(struct git_reftable_ref_store *)ref_store;
      +
     @@ refs/reftable-backend.c (new)
      +			break;
      +		}
      +
     -+		hashcpy(old_oid.hash, log.old_hash);
     -+		hashcpy(new_oid.hash, log.new_hash);
     ++		hashcpy(old_oid.hash, log.update.old_hash);
     ++		hashcpy(new_oid.hash, log.update.new_hash);
      +
     -+		full_committer = fmt_ident(log.name, log.email,
     ++		full_committer = fmt_ident(log.update.name, log.update.email,
      +					   WANT_COMMITTER_IDENT,
      +					   /*date*/ NULL, IDENT_NO_DATE);
     -+		err = fn(&old_oid, &new_oid, full_committer, log.time,
     -+			 log.tz_offset, log.message, cb_data);
     ++		err = fn(&old_oid, &new_oid, full_committer, log.update.time,
     ++			 log.update.tz_offset, log.update.message, cb_data);
      +		if (err)
      +			break;
      +	}
     @@ refs/reftable-backend.c (new)
      +		struct object_id new_oid;
      +		const char *full_committer = "";
      +
     -+		hashcpy(old_oid.hash, log->old_hash);
     -+		hashcpy(new_oid.hash, log->new_hash);
     ++		hashcpy(old_oid.hash, log->update.old_hash);
     ++		hashcpy(new_oid.hash, log->update.new_hash);
      +
     -+		full_committer = fmt_ident(log->name, log->email,
     ++		full_committer = fmt_ident(log->update.name, log->update.email,
      +					   WANT_COMMITTER_IDENT, NULL,
      +					   IDENT_NO_DATE);
     -+		err = fn(&old_oid, &new_oid, full_committer, log->time,
     -+			 log->tz_offset, log->message, cb_data);
     ++		err = fn(&old_oid, &new_oid, full_committer, log->update.time,
     ++			 log->update.tz_offset, log->update.message, cb_data);
      +		if (err) {
      +			break;
      +		}
     @@ refs/reftable-backend.c (new)
      +		if (err > 0 || strcmp(log.refname, refname)) {
      +			break;
      +		}
     -+		hashcpy(ooid.hash, log.old_hash);
     -+		hashcpy(noid.hash, log.new_hash);
     ++		hashcpy(ooid.hash, log.update.old_hash);
     ++		hashcpy(noid.hash, log.update.new_hash);
      +
     -+		if (should_prune_fn(&ooid, &noid, log.email,
     -+				    (timestamp_t)log.time, log.tz_offset,
     -+				    log.message, policy_cb_data)) {
     ++		if (should_prune_fn(&ooid, &noid, log.update.email,
     ++				    (timestamp_t)log.update.time,
     ++				    log.update.tz_offset, log.update.message,
     ++				    policy_cb_data)) {
      +			add_log_tombstone(&arg, refname, log.update_index);
      +		}
      +	}
     @@ t/t0031-reftable.sh (new)
      +
      +INVALID_SHA1=aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa
      +
     ++git_init () {
     ++	git init -b primary "$@"
     ++}
     ++
      +initialize ()  {
      +	rm -rf .git &&
     -+	git init --ref-storage=reftable &&
     ++	git_init --ref-storage=reftable &&
      +	mv .git/hooks .git/hooks-disabled
      +}
      +
      +test_expect_success 'SHA256 support, env' '
      +	rm -rf .git &&
      +	GIT_DEFAULT_HASH=sha256 && export GIT_DEFAULT_HASH &&
     -+	git init --ref-storage=reftable &&
     ++	git_init --ref-storage=reftable &&
      +	mv .git/hooks .git/hooks-disabled &&
      +	test_commit file
      +'
      +
      +test_expect_success 'SHA256 support, option' '
      +	rm -rf .git &&
     -+	git init --ref-storage=reftable --object-format=sha256 &&
     ++	git_init --ref-storage=reftable --object-format=sha256 &&
      +	mv .git/hooks .git/hooks-disabled &&
      +	test_commit file
      +'
     @@ t/t0031-reftable.sh (new)
      +	initialize &&
      +	test_commit file &&
      +	SHA=$(git show-ref -s --verify HEAD) &&
     -+	test_write_lines "$SHA refs/heads/master" "$SHA refs/tags/file" >expect &&
     -+	git show-ref > actual &&
     ++	test_write_lines "$SHA refs/heads/primary" "$SHA refs/tags/file" >expect &&
     ++	git show-ref >actual &&
      +	! git update-ref -d refs/tags/file $INVALID_SHA1 &&
      +	test_cmp expect actual &&
      +	git update-ref -d refs/tags/file $SHA  &&
     -+	test_write_lines "$SHA refs/heads/master" >expect &&
     -+	git show-ref > actual &&
     ++	test_write_lines "$SHA refs/heads/primary" >expect &&
     ++	git show-ref >actual &&
      +	test_cmp expect actual
      +'
      +
     @@ t/t0031-reftable.sh (new)
      +test_expect_success 'basic operation of reftable storage: commit, show-ref' '
      +	initialize &&
      +	test_commit file &&
     -+	test_write_lines refs/heads/master refs/tags/file >expect &&
     ++	test_write_lines refs/heads/primary refs/tags/file >expect &&
      +	git show-ref &&
     -+	git show-ref | cut -f2 -d" " > actual &&
     ++	git show-ref | cut -f2 -d" " >actual &&
      +	test_cmp actual expect
      +'
      +
     @@ t/t0031-reftable.sh (new)
      +	git pack-refs &&
      +	ls -1 .git/reftable >table-files &&
      +	test_line_count = 2 table-files &&
     -+	git reflog refs/heads/master >output &&
     ++	git reflog refs/heads/primary >output &&
      +	test_line_count = 10 output &&
      +	grep "commit (initial): number 1" output &&
      +	grep "commit: number 10" output &&
      +	git gc &&
     -+	git reflog refs/heads/master >output &&
     ++	git reflog refs/heads/primary >output &&
      +	test_line_count = 0 output
      +'
      +
     @@ t/t0031-reftable.sh (new)
      +	test_commit file2 &&
      +	git checkout -b branch2 &&
      +	git switch - &&
     -+	git rev-parse --symbolic-full-name HEAD > actual &&
     -+	echo refs/heads/branch1 > expect &&
     ++	git rev-parse --symbolic-full-name HEAD >actual &&
     ++	echo refs/heads/branch1 >expect &&
      +	test_cmp actual expect
      +'
      +
     @@ t/t0031-reftable.sh (new)
      +	test_commit file &&
      +	git tag -m "annotated tag" test_tag HEAD &&
      +	{
     -+		print_ref "refs/heads/master" &&
     ++		print_ref "refs/heads/primary" &&
      +		print_ref "refs/tags/file" &&
      +		print_ref "refs/tags/test_tag" &&
      +		print_ref "refs/tags/test_tag^{}"
     @@ t/t0031-reftable.sh (new)
      +test_expect_success 'show-ref works on fresh repo' '
      +	initialize &&
      +	rm -rf .git &&
     -+	git init --ref-storage=reftable &&
     ++	git_init --ref-storage=reftable &&
      +	>expect &&
     -+	! git show-ref > actual &&
     ++	! git show-ref >actual &&
      +	test_cmp expect actual
      +'
      +
      +test_expect_success 'checkout unborn branch' '
      +	initialize &&
     -+	git checkout -b master
     ++	git checkout -b primary
      +'
      +
      +
      +test_expect_success 'dir/file conflict' '
      +	initialize &&
      +	test_commit file &&
     -+	! git branch master/forbidden
     ++	! git branch primary/forbidden
      +'
      +
      +
      +test_expect_success 'do not clobber existing repo' '
      +	rm -rf .git &&
     -+	git init --ref-storage=files &&
     -+	cat .git/HEAD > expect &&
     ++	git_init --ref-storage=files &&
     ++	cat .git/HEAD >expect &&
      +	test_commit file &&
     -+	(git init --ref-storage=reftable || true) &&
     -+	cat .git/HEAD > actual &&
     ++	(git_init --ref-storage=reftable || true) &&
     ++	cat .git/HEAD >actual &&
      +	test_cmp expect actual
      +'
      +
     @@ t/t0031-reftable.sh (new)
      +'
      +
      +test_expect_success 'worktrees' '
     -+	git init --ref-storage=reftable start &&
     ++	git_init --ref-storage=reftable start &&
      +	(cd start && test_commit file1 && git checkout -b branch1 &&
      +	git checkout -b branch2 &&
      +	git worktree add  ../wt
     @@ t/t0031-reftable.sh (new)
      +	initialize &&
      +	test_commit file1 &&
      +	mkdir existing_empty &&
     -+	git worktree add --detach existing_empty master
     ++	git worktree add --detach existing_empty primary
      +'
      +
      +test_expect_success 'FETCH_HEAD' '
      +	initialize &&
      +	test_commit one &&
     -+	(git init sub && cd sub && test_commit two) &&
     ++	(git_init sub && cd sub && test_commit two) &&
      +	git --git-dir sub/.git rev-parse HEAD >expect &&
      +	git fetch sub &&
      +	git checkout FETCH_HEAD &&
     @@ t/t1450-fsck.sh: test_description='git fsck random collection of tests
       	git config i18n.commitencoding ISO-8859-1 &&
      
       ## t/t3210-pack-refs.sh ##
     -@@ t/t3210-pack-refs.sh: semantic is still the same.
     - '
     +@@ t/t3210-pack-refs.sh: export GIT_TEST_DEFAULT_INITIAL_BRANCH_NAME
     + 
       . ./test-lib.sh
       
      +if test_have_prereq REFTABLE
 14:  9df5bc69f971 = 14:  0d9477941678 git-prompt: prepare for reftable refs backend
 15:  4076ef5d20b4 = 15:  59f432522230 Add "test-tool dump-reftable" command.

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable backend needs to know the hash algorithm for writing the initialization hash table.

The initial reftable contains a symref HEAD => "main" (or "master"), which is agnostic to the size of hash value, but this is an exceptional circumstance, and the reftable library does not cater to this exception. It insists that all tables in the stack have a consistent format ID for the hash algorithm.

Call set_repo_hash_algo directly after calling validate_hash_algorithm() (which reads $GIT_DEFAULT_HASH).

---
 builtin/init-db.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

index dcc45bef5148..7766661a4755 100644
@@ -438,6 +438,27 @@ int init_db(const char *git_dir, const char *real_git_dir,
 
 	validate_hash_algorithm(&repo_fmt, hash);
 
+	/*
+	 * At this point, the_repository we have in-core does not look
+	 * anything like one that we would see initialized in an already
+	 * working repository after calling setup_git_directory().
+	 *
+	 * Calling repository.c::initialize_the_repository() may have
+	 * prepared the .index .objects and .parsed_objects members, but
+	 * other members like .gitdir, .commondir, etc. have not been
+	 * initialized.
+	 *
+	 * Many API functions assume they are working with the_repository
+	 * that has sensibly been initialized, but because we haven't
+	 * really read from an existing repository, we need to hand-craft
+	 * the necessary members of the structure to get out of this
+	 * chicken-and-egg situation.
+	 *
+	 * For now, we update the hash algorithm member to what the
+	 * validate_hash_algorithm() call decided for us.
+	 */
+	repo_set_hash_algo(the_repository, repo_fmt.hash_algo);
+
 	reinit = create_default_files(template_dir, original_git_dir,
 				      initial_branch, &repo_fmt,
 				      flags & INIT_DB_QUIET);

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

TODO: relicense?

---
 reftable/LICENSE | 31 +++++++++++++++++++++++++++++++
 1 file changed, 31 insertions(+)
 create mode 100644 reftable/LICENSE

new file mode 100644
index 000000000000..402e0f9356ba
@@ -0,0 +1,31 @@
+BSD License
+
+Copyright (c) 2020, Google LLC
+All rights reserved.
+
+Redistribution and use in source and binary forms, with or without
+modification, are permitted provided that the following conditions are
+met:
+
+* Redistributions of source code must retain the above copyright notice,
+this list of conditions and the following disclaimer.
+
+* Redistributions in binary form must reproduce the above copyright
+notice, this list of conditions and the following disclaimer in the
+documentation and/or other materials provided with the distribution.
+
+* Neither the name of Google LLC nor the names of its contributors may
+be used to endorse or promote products derived from this software
+without specific prior written permission.
+
+THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+"AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

The reftable/ directory is structured as a library, so it cannot crash on misuse. Instead, it returns an error codes.

In addition, the error code can be used to signal conditions from lower levels of the library to be handled by higher levels of the library. For example, a transaction might legitimately write an empty reftable file, but in that case, we'd want to shortcut the transaction overhead.

---
 reftable/error.c          | 41 ++++++++++++++++++++++++++
 reftable/reftable-error.h | 62 +++++++++++++++++++++++++++++++++++++++
 2 files changed, 103 insertions(+)
 create mode 100644 reftable/error.c
 create mode 100644 reftable/reftable-error.h

new file mode 100644
index 000000000000..f6f16def9214
@@ -0,0 +1,41 @@
+/*
+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-error.h"
+
+#include <stdio.h>
+
+const char *reftable_error_str(int err)
+{
+	static char buf[250];
+	switch (err) {
+	case REFTABLE_IO_ERROR:
+		return "I/O error";
+	case REFTABLE_FORMAT_ERROR:
+		return "corrupt reftable file";
+	case REFTABLE_NOT_EXIST_ERROR:
+		return "file does not exist";
+	case REFTABLE_LOCK_ERROR:
+		return "data is outdated";
+	case REFTABLE_API_ERROR:
+		return "misuse of the reftable API";
+	case REFTABLE_ZLIB_ERROR:
+		return "zlib failure";
+	case REFTABLE_NAME_CONFLICT:
+		return "file/directory conflict";
+	case REFTABLE_EMPTY_TABLE_ERROR:
+		return "wrote empty table";
+	case REFTABLE_REFNAME_ERROR:
+		return "invalid refname";
+	case -1:
+		return "general error";
+	default:
+		snprintf(buf, sizeof(buf), "unknown error code %d", err);
+		return buf;
+	}
+}

gitgitgadget

From: Han-Wen Nienhuys <[email protected]>

This commit provides basic utility classes for the reftable library.

---
 Makefile                            |  24 +++++-
 contrib/buildsystems/CMakeLists.txt |  14 ++-
 reftable/basics.c                   | 128 ++++++++++++++++++++++++++++
 reftable/basics.h                   |  60 +++++++++++++
 reftable/basics_test.c              |  98 +++++++++++++++++++++
 reftable/publicbasics.c             |  58 +++++++++++++
 reftable/reftable-malloc.h          |  18 ++++
 reftable/reftable-tests.h           |  22 +++++
 reftable/system.h                   |  32 +++++++
 reftable/test_framework.c           |  23 +++++
 reftable/test_framework.h           |  53 ++++++++++++
 t/helper/test-reftable.c            |   9 ++
 t/helper/test-tool.c                |   3 +-
 t/helper/test-tool.h                |   1 +
 t/t0032-reftable-unittest.sh        |  15 ++++
 15 files changed, 552 insertions(+), 6 deletions(-)
 create mode 100644 reftable/basics.c
 create mode 100644 reftable/basics.h
 create mode 100644 reftable/basics_test.c
 create mode 100644 reftable/publicbasics.c
 create mode 100644 reftable/reftable-malloc.h
 create mode 100644 reftable/reftable-tests.h
 create mode 100644 reftable/system.h
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h
 create mode 100644 t/helper/test-reftable.c
 create mode 100755 t/t0032-reftable-unittest.sh

index dfb0f1000fa3..43ed67fdb9db 100644
@@ -728,6 +728,7 @@ TEST_BUILTINS_OBJS += test-read-cache.o
 TEST_BUILTINS_OBJS += test-read-graph.o
 TEST_BUILTINS_OBJS += test-read-midx.o
 TEST_BUILTINS_OBJS += test-ref-store.o
+TEST_BUILTINS_OBJS += test-reftable.o
 TEST_BUILTINS_OBJS += test-regex.o
 TEST_BUILTINS_OBJS += test-repository.o
 TEST_BUILTINS_OBJS += test-revision-walking.o

@@ -804,6 +805,8 @@ TEST_SHELL_PATH = $(SHELL_PATH)
 
 LIB_FILE = libgit.a
 XDIFF_LIB = xdiff/lib.a
+REFTABLE_LIB = reftable/libreftable.a
+REFTABLE_TEST_LIB = reftable/libreftable_test.a
 
 GENERATED_H += command-list.h
 GENERATED_H += config-list.h

@@ -1172,7 +1175,7 @@ THIRD_PARTY_SOURCES += compat/regex/%
 THIRD_PARTY_SOURCES += sha1collisiondetection/%
 THIRD_PARTY_SOURCES += sha1dc/%
 
-GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB)
+GITLIBS = common-main.o $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB)
 EXTLIBS =
 
 GIT_USER_AGENT = git/$(GIT_VERSION)

@@ -2379,10 +2382,19 @@ XDIFF_OBJS += xdiff/xpatience.o
 XDIFF_OBJS += xdiff/xprepare.o
 XDIFF_OBJS += xdiff/xutils.o
 
+REFTABLE_OBJS += reftable/basics.o
+REFTABLE_OBJS += reftable/error.o
+REFTABLE_OBJS += reftable/publicbasics.o
+
+REFTABLE_TEST_OBJS += reftable/test_framework.o
+REFTABLE_TEST_OBJS += reftable/basics_test.o
+
 TEST_OBJS := $(patsubst %$X,%.o,$(TEST_PROGRAMS)) $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
 OBJECTS := $(LIB_OBJS) $(BUILTIN_OBJS) $(PROGRAM_OBJS) $(TEST_OBJS) \
 	$(XDIFF_OBJS) \
 	$(FUZZ_OBJS) \
+	$(REFTABLE_OBJS) \
+	$(REFTABLE_TEST_OBJS) \
 	common-main.o \
 	git.o
 ifndef NO_CURL

@@ -2534,6 +2546,12 @@ $(LIB_FILE): $(LIB_OBJS)
 $(XDIFF_LIB): $(XDIFF_OBJS)
 	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
 
+$(REFTABLE_LIB): $(REFTABLE_OBJS)
+	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
+
+$(REFTABLE_TEST_LIB): $(REFTABLE_TEST_OBJS)
+	$(QUIET_AR)$(RM) $@ && $(AR) $(ARFLAGS) $@ $^
+
 export DEFAULT_EDITOR DEFAULT_PAGER
 
 Documentation/GIT-EXCLUDED-PROGRAMS: FORCE

@@ -2812,7 +2830,7 @@ perf: all
 
 t/helper/test-tool$X: $(patsubst %,t/helper/%,$(TEST_BUILTINS_OBJS))
 
-t/helper/test-%$X: t/helper/test-%.o GIT-LDFLAGS $(GITLIBS)
+t/helper/test-%$X: t/helper/test-%.o GIT-LDFLAGS $(GITLIBS) $(REFTABLE_TEST_LIB)
 	$(QUIET_LINK)$(CC) $(ALL_CFLAGS) -o $@ $(ALL_LDFLAGS) $(filter %.o,$^) $(filter %.a,$^) $(LIBS)
 
 check-sha1:: t/helper/test-tool$X

@@ -3142,7 +3160,7 @@ cocciclean:
 clean: profile-clean coverage-clean cocciclean
 	$(RM) *.res
 	$(RM) $(OBJECTS)
-	$(RM) $(LIB_FILE) $(XDIFF_LIB)
+	$(RM) $(LIB_FILE) $(XDIFF_LIB) $(REFTABLE_LIB) $(REFTABLE_TEST_LIB)
 	$(RM) $(ALL_PROGRAMS) $(SCRIPT_LIB) $(BUILT_INS) git$X
 	$(RM) $(TEST_PROGRAMS)
 	$(RM) $(FUZZ_PROGRAMS)

index ac3dbc079af8..986bfc04e0dc 100644
@@ -601,6 +601,12 @@ parse_makefile_for_sources(libxdiff_SOURCES "XDIFF_OBJS")
 list(TRANSFORM libxdiff_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
 add_library(xdiff STATIC ${libxdiff_SOURCES})
 
+#reftable
+parse_makefile_for_sources(reftable_SOURCES "REFTABLE_OBJS")
+
+list(TRANSFORM reftable_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
+add_library(reftable STATIC ${reftable_SOURCES})
+
 if(WIN32)
 	if(NOT MSVC)#use windres when compiling with gcc and clang
 		add_custom_command(OUTPUT ${CMAKE_BINARY_DIR}/git.res

@@ -623,7 +629,7 @@ endif()
 #link all required libraries to common-main
 add_library(common-main OBJECT ${CMAKE_SOURCE_DIR}/common-main.c)
 
-target_link_libraries(common-main libgit xdiff ${ZLIB_LIBRARIES})
+target_link_libraries(common-main libgit xdiff reftable ${ZLIB_LIBRARIES})
 if(Intl_FOUND)
 	target_link_libraries(common-main ${Intl_LIBRARIES})
 endif()

@@ -855,11 +861,15 @@ if(BUILD_TESTING)
 add_executable(test-fake-ssh ${CMAKE_SOURCE_DIR}/t/helper/test-fake-ssh.c)
 target_link_libraries(test-fake-ssh common-main)
 
+#reftable-tests
+parse_makefile_for_sources(test-reftable_SOURCES "REFTABLE_TEST_OBJS")
+list(TRANSFORM test-reftable_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/")
+
 #test-tool
 parse_makefile_for_sources(test-tool_SOURCES "TEST_BUILTINS_OBJS")
 
 list(TRANSFORM test-tool_SOURCES PREPEND "${CMAKE_SOURCE_DIR}/t/helper/")
-add_executable(test-tool ${CMAKE_SOURCE_DIR}/t/helper/test-tool.c ${test-tool_SOURCES})
+add_executable(test-tool ${CMAKE_SOURCE_DIR}/t/helper/test-tool.c ${test-tool_SOURCES} ${test-reftable_SOURCES})
 target_link_libraries(test-tool common-main)
 
 set_target_properties(test-fake-ssh test-tool

new file mode 100644
index 000000000000..5f2185f1f343
@@ -0,0 +1,18 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef REFTABLE_H
+#define REFTABLE_H
+
+#include <stddef.h>
+
+/* Overrides the functions to use for memory management. */
+void reftable_set_alloc(void *(*malloc)(size_t),
+			void *(*realloc)(void *, size_t), void (*free)(void *));
+
+#endif

new file mode 100644
index 000000000000..5e7698ae654e
@@ -0,0 +1,22 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#ifndef REFTABLE_TESTS_H
+#define REFTABLE_TESTS_H
+
+int basics_test_main(int argc, const char **argv);
+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 stack_test_main(int argc, const char **argv);
+int tree_test_main(int argc, const char **argv);
+int reftable_dump_main(int argc, char *const *argv);
+
+#endif

new file mode 100644
index 000000000000..07277ca06273
@@ -0,0 +1,32 @@
+/*
+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 SYSTEM_H
+#define SYSTEM_H
+
+#include "git-compat-util.h"
+#include "strbuf.h"
+
+#include <zlib.h>
+
+struct strbuf;
+/* In git, this is declared in dir.h */
+int remove_dir_recursively(struct strbuf *path, int flags);
+
+#define SHA1_ID 0x73686131
+#define SHA256_ID 0x73323536
+#define SHA1_SIZE 20
+#define SHA256_SIZE 32
+
+/* This is uncompress2, which is only available in zlib as of 2017.
+ */
+int uncompress_return_consumed(Bytef *dest, uLongf *destLen,
+			       const Bytef *source, uLong *sourceLen);
+int hash_size(uint32_t id);
+
+#endif

new file mode 100644
index 000000000000..a5ff4e2a2d2f
@@ -0,0 +1,23 @@
+/*
+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 "test_framework.h"
+
+#include "basics.h"
+
+void set_test_hash(uint8_t *p, int i)
+{
+	memset(p, (uint8_t)i, hash_size(SHA1_ID));
+}
+
+int strbuf_add_void(void *b, const void *data, size_t sz)
+{
+	strbuf_add((struct strbuf *)b, data, sz);
+	return sz;
+}

new file mode 100644
index 000000000000..3b58e423e7b1
@@ -0,0 +1,9 @@
+#include "reftable/reftable-tests.h"
+#include "test-tool.h"
+
+int cmd__reftable(int argc, const char **argv)
+{
+	basics_test_main(argc, argv);
+
+	return 0;
+}

index f97cd9f48a69..dfa2bee9e8a2 100644
@@ -49,13 +49,14 @@ static struct test_cmd cmds[] = {
 	{ "pcre2-config", cmd__pcre2_config },
 	{ "pkt-line", cmd__pkt_line },
 	{ "prio-queue", cmd__prio_queue },
-	{ "proc-receive", cmd__proc_receive},
+	{ "proc-receive", cmd__proc_receive },
 	{ "progress", cmd__progress },
 	{ "reach", cmd__reach },
 	{ "read-cache", cmd__read_cache },
 	{ "read-graph", cmd__read_graph },
 	{ "read-midx", cmd__read_midx },
 	{ "ref-store", cmd__ref_store },
+	{ "reftable", cmd__reftable },
 	{ "regex", cmd__regex },
 	{ "repository", cmd__repository },
 	{ "revision-walking", cmd__revision_walking },