reftable library

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.

Han-Wen Nienhuys (12):
reftable: add LICENSE
reftable: define the public API
reftable: add a barebones unittest framework
reftable: utility functions
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: file level tests
reftable: rest of library
reftable: "test-tool dump-reftable" command.

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

 Makefile                                   |   46 +-
 config.mak.uname                           |    2 +-
 contrib/buildsystems/Generators/Vcxproj.pm |   11 +-
 reftable/.gitattributes                    |    1 +
 reftable/LICENSE                           |   31 +
 reftable/VERSION                           |    1 +
 reftable/basics.c                          |  131 +++
 reftable/basics.h                          |   48 +
 reftable/block.c                           |  443 +++++++
 reftable/block.h                           |  129 +++
 reftable/block_test.c                      |  158 +++
 reftable/blocksource.c                     |  148 +++
 reftable/blocksource.h                     |   22 +
 reftable/compat.c                          |  110 ++
 reftable/compat.h                          |   48 +
 reftable/constants.h                       |   21 +
 reftable/dump.c                            |  212 ++++
 reftable/iter.c                            |  242 ++++
 reftable/iter.h                            |   72 ++
 reftable/merged.c                          |  358 ++++++
 reftable/merged.h                          |   39 +
 reftable/merged_test.c                     |  331 ++++++
 reftable/pq.c                              |  115 ++
 reftable/pq.h                              |   34 +
 reftable/publicbasics.c                    |  100 ++
 reftable/reader.c                          |  733 ++++++++++++
 reftable/reader.h                          |   78 ++
 reftable/record.c                          | 1114 ++++++++++++++++++
 reftable/record.h                          |  143 +++
 reftable/record_test.c                     |  410 +++++++
 reftable/refname.c                         |  209 ++++
 reftable/refname.h                         |   38 +
 reftable/refname_test.c                    |  100 ++
 reftable/reftable-tests.h                  |   22 +
 reftable/reftable.c                        |  104 ++
 reftable/reftable.h                        |  585 ++++++++++
 reftable/reftable_test.c                   |  585 ++++++++++
 reftable/stack.c                           | 1224 ++++++++++++++++++++
 reftable/stack.h                           |   50 +
 reftable/stack_test.c                      |  787 +++++++++++++
 reftable/strbuf.c                          |  142 +++
 reftable/strbuf.h                          |   80 ++
 reftable/strbuf_test.c                     |   37 +
 reftable/system.h                          |   51 +
 reftable/test_framework.c                  |   68 ++
 reftable/test_framework.h                  |   60 +
 reftable/tree.c                            |   63 +
 reftable/tree.h                            |   34 +
 reftable/tree_test.c                       |   62 +
 reftable/update.sh                         |   22 +
 reftable/writer.c                          |  664 +++++++++++
 reftable/writer.h                          |   60 +
 reftable/zlib-compat.c                     |   92 ++
 t/helper/test-reftable.c                   |   20 +
 t/helper/test-tool.c                       |    2 +
 t/helper/test-tool.h                       |    2 +
 56 files changed, 10489 insertions(+), 5 deletions(-)
 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/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/compat.c
 create mode 100644 reftable/compat.h
 create mode 100644 reftable/constants.h
 create mode 100644 reftable/dump.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-tests.h
 create mode 100644 reftable/reftable.c
 create mode 100644 reftable/reftable.h
 create mode 100644 reftable/reftable_test.c
 create mode 100644 reftable/stack.c
 create mode 100644 reftable/stack.h
 create mode 100644 reftable/stack_test.c
 create mode 100644 reftable/strbuf.c
 create mode 100644 reftable/strbuf.h
 create mode 100644 reftable/strbuf_test.c
 create mode 100644 reftable/system.h
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h
 create mode 100644 reftable/tree.c
 create mode 100644 reftable/tree.h
 create mode 100644 reftable/tree_test.c
 create mode 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c
 create mode 100644 t/helper/test-reftable.c

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

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 0000000000..402e0f9356
@@ -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]>

---
 reftable/reftable.h | 585 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 585 insertions(+)
 create mode 100644 reftable/reftable.h

new file mode 100644
index 0000000000..5f8ebf5540
@@ -0,0 +1,585 @@
+/*
+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 <stdint.h>
+#include <stddef.h>
+
+void reftable_set_alloc(void *(*malloc)(size_t),
+			void *(*realloc)(void *, size_t), void (*free)(void *));
+
+/****************************************************************
+ 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. */
+};
+
+/* 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 */
+void reftable_ref_record_print(struct reftable_ref_record *ref,
+			       uint32_t hash_id);
+
+/* frees and nulls all pointer values. */
+void reftable_ref_record_clear(struct reftable_ref_record *ref);
+
+/* returns whether two reftable_ref_records are the same */
+int reftable_ref_record_equal(struct reftable_ref_record *a,
+			      struct reftable_ref_record *b, int hash_size);
+
+/* reftable_log_record holds a reflog entry */
+struct reftable_log_record {
+	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;
+};
+
+/* returns whether 'ref' represents the deletion of a log record. */
+int reftable_log_record_is_deletion(const struct reftable_log_record *log);
+
+/* frees and nulls all pointer values. */
+void reftable_log_record_clear(struct reftable_log_record *log);
+
+/* returns whether two records are equal. */
+int reftable_log_record_equal(struct reftable_log_record *a,
+			      struct reftable_log_record *b, int hash_size);
+
+/* dumps a reftable_log_record on stdout, for debugging/testing. */
+void reftable_log_record_print(struct reftable_log_record *log,
+			       uint32_t hash_id);
+
+/****************************************************************
+ Error handling
+
+ Error are signaled with negative integer return values. 0 means success.
+ ****************************************************************/
+
+/* different types of errors */
+enum reftable_error {
+	/* Unexpected file system behavior */
+	REFTABLE_IO_ERROR = -2,
+
+	/* 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.
+	*/
+	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.
+	*/
+	REFTABLE_API_ERROR = -6,
+
+	/* Decompression error */
+	REFTABLE_ZLIB_ERROR = -7,
+
+	/* Wrote a table without blocks. */
+	REFTABLE_EMPTY_TABLE_ERROR = -8,
+
+	/* Dir/file conflict. */
+	REFTABLE_NAME_CONFLICT = -9,
+
+	/* Illegal ref name. */
+	REFTABLE_REFNAME_ERROR = -10,
+};
+
+/* convert the numeric error code to a string. The string should not be
+ * deallocated. */
+const char *reftable_error_str(int err);
+
+/*
+ * Convert the numeric error code to an equivalent errno code.
+ */
+int reftable_error_to_errno(int err);
+
+/****************************************************************
+ Writing
+
+ Writing single reftables
+ ****************************************************************/
+
+/* reftable_write_options sets options for writing a single reftable. */
+struct reftable_write_options {
+	/* boolean: do not pad out blocks to block size. */
+	int unpadded;
+
+	/* the blocksize. Should be less than 2^24. */
+	uint32_t block_size;
+
+	/* boolean: do not generate a SHA1 => ref index. */
+	int skip_index_objects;
+
+	/* how often to write complete keys in each block. */
+	int restart_interval;
+
+	/* 4-byte identifier ("sha1", "s256") of the hash.
+	 * Defaults to SHA1 if unset
+	 */
+	uint32_t hash_id;
+
+	/* boolean: do not check ref names for validity or dir/file conflicts.
+	 */
+	int skip_name_check;
+
+	/* boolean: copy log messages exactly. If unset, check that the message
+	 *   is a single line, and add '\n' if missing.
+	 */
+	int exact_log_message;
+};
+
+/* reftable_block_stats holds statistics for a single block type */
+struct reftable_block_stats {
+	/* total number of entries written */
+	int entries;
+	/* total number of key restarts */
+	int restarts;
+	/* total number of blocks */
+	int blocks;
+	/* total number of index blocks */
+	int index_blocks;
+	/* depth of the index */
+	int max_index_level;
+
+	/* offset of the first block for this type */
+	uint64_t offset;
+	/* offset of the top level index block for this type, or 0 if not
+	 * present */
+	uint64_t index_offset;
+};
+
+/* stats holds overall statistics for a single reftable */
+struct reftable_stats {
+	/* total number of blocks written. */
+	int blocks;
+	/* stats for ref data */
+	struct reftable_block_stats ref_stats;
+	/* stats for the SHA1 to ref map. */
+	struct reftable_block_stats obj_stats;
+	/* stats for index blocks */
+	struct reftable_block_stats idx_stats;
+	/* stats for log blocks */
+	struct reftable_block_stats log_stats;
+
+	/* disambiguation length of shortened object IDs. */
+	int object_id_len;
+};
+
+/* reftable_new_writer creates a new writer */
+struct reftable_writer *
+reftable_new_writer(int (*writer_func)(void *, const void *, size_t),
+		    void *writer_arg, struct reftable_write_options *opts);
+
+/* write to a file descriptor. fdp should be an int* pointing to the fd. */
+int reftable_fd_write(void *fdp, const void *data, size_t size);
+
+/* Set the range of update indices for the records we will add.  When
+   writing a table into a stack, the min should be at least
+   reftable_stack_next_update_index(), or REFTABLE_API_ERROR is returned.
+
+   For transactional updates, typically min==max. When converting an existing
+   ref database into a single reftable, this would be a range of update-index
+   timestamps.
+ */
+void reftable_writer_set_limits(struct reftable_writer *w, uint64_t min,
+				uint64_t max);
+
+/* adds a reftable_ref_record. Must be called in ascending
+   order. The update_index must be within the limits set by
+   reftable_writer_set_limits(), or REFTABLE_API_ERROR is returned.
+
+   It is an error to write a ref record after a log record.
+ */
+int reftable_writer_add_ref(struct reftable_writer *w,
+			    struct reftable_ref_record *ref);
+
+/* Convenience function to add multiple refs. Will sort the refs by
+   name before adding. */
+int reftable_writer_add_refs(struct reftable_writer *w,
+			     struct reftable_ref_record *refs, int n);
+
+/* adds a reftable_log_record. Must be called in ascending order (with more
+   recent log entries first.)
+ */
+int reftable_writer_add_log(struct reftable_writer *w,
+			    struct reftable_log_record *log);
+
+/* Convenience function to add multiple logs. Will sort the records by
+   key before adding. */
+int reftable_writer_add_logs(struct reftable_writer *w,
+			     struct reftable_log_record *logs, int n);
+
+/* reftable_writer_close finalizes the reftable. The writer is retained so
+ * statistics can be inspected. */
+int reftable_writer_close(struct reftable_writer *w);
+
+/* writer_stats returns the statistics on the reftable being written.
+
+   This struct becomes invalid when the writer is freed.
+ */
+const struct reftable_stats *writer_stats(struct reftable_writer *w);
+
+/* reftable_writer_free deallocates memory for the writer */
+void reftable_writer_free(struct reftable_writer *w);
+
+/****************************************************************
+ * ITERATING
+ ****************************************************************/
+
+/* iterator is the generic interface for walking over data stored in a
+   reftable. It is generally passed around by value.
+*/
+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);
+
+/****************************************************************
+ 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.
+ ****************************************************************/
+
+/* block_source is a generic wrapper for a seekable readable file.
+   It is generally passed around by value.
+ */
+struct reftable_block_source {
+	struct reftable_block_source_vtable *ops;
+	void *arg;
+};
+
+/* a contiguous segment of bytes. It keeps track of its generating block_source
+   so it can return itself into the pool.
+*/
+struct reftable_block {
+	uint8_t *data;
+	int len;
+	struct reftable_block_source source;
+};
+
+/* block_source_vtable are the operations that make up block_source */
+struct reftable_block_source_vtable {
+	/* returns the size of a block source */
+	uint64_t (*size)(void *source);
+
+	/* reads a segment from the block source. It is an error to read
+	   beyond the end of the block */
+	int (*read_block)(void *source, struct reftable_block *dest,
+			  uint64_t off, uint32_t size);
+	/* mark the block as read; may return the data back to malloc */
+	void (*return_block)(void *source, struct reftable_block *blockp);
+
+	/* release all resources associated with the block source */
+	void (*close)(void *source);
+};
+
+/* opens a file on the file system as a block_source */
+int reftable_block_source_from_file(struct reftable_block_source *block_src,
+				    const char *name);
+
+/* The reader struct is a handle to an open reftable file. */
+struct reftable_reader;
+
+/* reftable_new_reader opens a reftable for reading. If successful, returns 0
+ * code and sets pp. The name is used for creating a stack. Typically, it is the
+ * basename of the file. The block source `src` is owned by the reader, and is
+ * closed on calling reftable_reader_destroy().
+ */
+int reftable_new_reader(struct reftable_reader **pp,
+			struct reftable_block_source *src, const char *name);
+
+/* reftable_reader_seek_ref returns an iterator where 'name' would be inserted
+   in the table.  To seek to the start of the table, use name = "".
+
+   example:
+
+   struct reftable_reader *r = NULL;
+   int err = reftable_new_reader(&r, &src, "filename");
+   if (err < 0) { ... }
+   struct reftable_iterator it  = {0};
+   err = reftable_reader_seek_ref(r, &it, "refs/heads/master");
+   if (err < 0) { ... }
+   struct reftable_ref_record ref  = {0};
+   while (1) {
+     err = reftable_iterator_next_ref(&it, &ref);
+     if (err > 0) {
+       break;
+     }
+     if (err < 0) {
+       ..error handling..
+     }
+     ..found..
+   }
+   reftable_iterator_destroy(&it);
+   reftable_ref_record_clear(&ref);
+ */
+int reftable_reader_seek_ref(struct reftable_reader *r,
+			     struct reftable_iterator *it, const char *name);
+
+/* returns the hash ID used in this table. */
+uint32_t reftable_reader_hash_id(struct reftable_reader *r);
+
+/* seek to logs for the given name, older than update_index. To seek to the
+   start of the table, use name = "".
+ */
+int reftable_reader_seek_log_at(struct reftable_reader *r,
+				struct reftable_iterator *it, const char *name,
+				uint64_t update_index);
+
+/* seek to newest log entry for given name. */
+int reftable_reader_seek_log(struct reftable_reader *r,
+			     struct reftable_iterator *it, const char *name);
+
+/* closes and deallocates a reader. */
+void reftable_reader_free(struct reftable_reader *);
+
+/* return an iterator for the refs pointing to `oid`. */
+int reftable_reader_refs_for(struct reftable_reader *r,
+			     struct reftable_iterator *it, uint8_t *oid);
+
+/* return the max_update_index for a table */
+uint64_t reftable_reader_max_update_index(struct reftable_reader *r);
+
+/* return the min_update_index for a table */
+uint64_t reftable_reader_min_update_index(struct reftable_reader *r);
+
+/****************************************************************
+ 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.
+ ****************************************************************/
+
+/* A merged table is implements seeking/iterating over a stack of tables. */
+struct reftable_merged_table;
+
+/* A generic reftable; see below. */
+struct reftable_table;
+
+/* reftable_new_merged_table creates a new merged table. It takes ownership of
+   the stack array.
+*/
+int reftable_new_merged_table(struct reftable_merged_table **dest,
+			      struct reftable_table *stack, int n,
+			      uint32_t hash_id);
+
+/* returns an iterator positioned just before 'name' */
+int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,
+				   struct reftable_iterator *it,
+				   const char *name);
+
+/* returns an iterator for log entry, at given update_index */
+int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,
+				      struct reftable_iterator *it,
+				      const char *name, uint64_t update_index);
+
+/* like reftable_merged_table_seek_log_at but look for the newest entry. */
+int reftable_merged_table_seek_log(struct reftable_merged_table *mt,
+				   struct reftable_iterator *it,
+				   const char *name);
+
+/* returns the max update_index covered by this merged table. */
+uint64_t
+reftable_merged_table_max_update_index(struct reftable_merged_table *mt);
+
+/* returns the min update_index covered by this merged table. */
+uint64_t
+reftable_merged_table_min_update_index(struct reftable_merged_table *mt);
+
+/* releases memory for the merged_table */
+void reftable_merged_table_free(struct reftable_merged_table *m);
+
+/* return the hash ID of the merged table. */
+uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *m);
+
+/****************************************************************
+ Generic tables
+
+ A unified API for reading tables, either merged tables, or single readers.
+ ****************************************************************/
+
+struct reftable_table {
+	struct reftable_table_vtable *ops;
+	void *table_arg;
+};
+
+int reftable_table_seek_ref(struct reftable_table *tab,
+			    struct reftable_iterator *it, const char *name);
+
+void reftable_table_from_reader(struct reftable_table *tab,
+				struct reftable_reader *reader);
+
+/* returns the hash ID from a generic reftable_table */
+uint32_t reftable_table_hash_id(struct reftable_table *tab);
+
+/* create a generic table from reftable_merged_table */
+void reftable_table_from_merged_table(struct reftable_table *tab,
+				      struct reftable_merged_table *table);
+
+/* returns the max update_index covered by this table. */
+uint64_t reftable_table_max_update_index(struct reftable_table *tab);
+
+/* returns the min update_index covered by this table. */
+uint64_t reftable_table_min_update_index(struct reftable_table *tab);
+
+/* convenience function to read a single ref. Returns < 0 for error, 0
+   for success, and 1 if ref not found. */
+int reftable_table_read_ref(struct reftable_table *tab, const char *name,
+			    struct reftable_ref_record *ref);
+
+/****************************************************************
+ Mutable ref database
+
+ The stack presents an interface to a mutable sequence of reftables.
+ ****************************************************************/
+
+/* a stack is a stack of reftables, which can be mutated by pushing a table to
+ * the top of the stack */
+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.
+*/
+int reftable_new_stack(struct reftable_stack **dest, const char *dir,
+		       struct reftable_write_options config);
+
+/* returns the update_index at which a next table should be written. */
+uint64_t reftable_stack_next_update_index(struct reftable_stack *st);
+
+/* holds a transaction to add tables at the top of a stack. */
+struct reftable_addition;
+
+/*
+  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);
+
+/* Adds a reftable to transaction. */
+int reftable_addition_add(struct reftable_addition *add,
+			  int (*write_table)(struct reftable_writer *wr,
+					     void *arg),
+			  void *arg);
+
+/* Commits the transaction, releasing the lock. */
+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. */
+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. */
+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.
+*/
+struct reftable_merged_table *
+reftable_stack_merged_table(struct reftable_stack *st);
+
+/* frees all resources associated with the stack. */
+void reftable_stack_destroy(struct reftable_stack *st);
+
+/* Reloads the stack if necessary. This is very cheap to run if the stack was up
+ * to date */
+int reftable_stack_reload(struct reftable_stack *st);
+
+/* Policy for expiring reflog entries. */
+struct reftable_log_expiry_config {
+	/* Drop entries older than this timestamp */
+	uint64_t time;
+
+	/* Drop older entries */
+	uint64_t min_update_index;
+};
+
+/* compacts all reftables into a giant table. Expire reflog entries if config is
+ * non-NULL */
+int reftable_stack_compact_all(struct reftable_stack *st,
+			       struct reftable_log_expiry_config *config);
+
+/* 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. */
+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. */
+int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
+			    struct reftable_log_record *log);
+
+/* statistics on past compactions. */
+struct reftable_compaction_stats {
+	uint64_t bytes; /* total number of bytes written */
+	uint64_t entries_written; /* total number of entries written, including
+				     failures. */
+	int attempts; /* how often we tried to compact */
+	int failures; /* failures happen on concurrent updates */
+};
+
+/* return statistics for compaction up till now. */
+struct reftable_compaction_stats *
+reftable_stack_compaction_stats(struct reftable_stack *st);
+
+#endif

gitgitgadget

From: Johannes Schindelin <[email protected]>

This allows Git to be compiled via Visual Studio again after integrating the hn/reftable branch.

---
 config.mak.uname                           |  2 +-
 contrib/buildsystems/Generators/Vcxproj.pm | 11 ++++++++++-
 2 files changed, 11 insertions(+), 2 deletions(-)

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">

gitgitgadget

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

---
 reftable/test_framework.c | 68 +++++++++++++++++++++++++++++++++++++++
 reftable/test_framework.h | 60 ++++++++++++++++++++++++++++++++++
 2 files changed, 128 insertions(+)
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h

new file mode 100644
index 0000000000..f304a2773a
@@ -0,0 +1,68 @@
+/*
+Copyright 2020 Google LLC
+
+Use of this source code is governed by a BSD-style
+license that can be found in the LICENSE file or at
+https://developers.google.com/open-source/licenses/bsd
+*/
+
+#include "test_framework.h"
+
+#include "system.h"
+#include "basics.h"
+
+struct test_case **test_cases;
+int test_case_len;
+int test_case_cap;
+
+struct test_case *new_test_case(const char *name, void (*testfunc)(void))
+{
+	struct test_case *tc = reftable_malloc(sizeof(struct test_case));
+	tc->name = name;
+	tc->testfunc = testfunc;
+	return tc;
+}
+
+struct test_case *add_test_case(const char *name, void (*testfunc)(void))
+{
+	struct test_case *tc = new_test_case(name, testfunc);
+	if (test_case_len == test_case_cap) {
+		test_case_cap = 2 * test_case_cap + 1;
+		test_cases = reftable_realloc(
+			test_cases, sizeof(struct test_case) * test_case_cap);
+	}
+
+	test_cases[test_case_len++] = tc;
+	return tc;
+}
+
+int test_main(int argc, const char *argv[])
+{
+	const char *filter = NULL;
+	int i = 0;
+	if (argc > 1) {
+		filter = argv[1];
+	}
+
+	for (i = 0; i < test_case_len; i++) {
+		const char *name = test_cases[i]->name;
+		if (filter == NULL || strstr(name, filter) != NULL) {
+			printf("case %s\n", name);
+			test_cases[i]->testfunc();
+		} else {
+			printf("skip %s\n", name);
+		}
+
+		reftable_free(test_cases[i]);
+	}
+	reftable_free(test_cases);
+	test_cases = 0;
+	test_case_len = 0;
+	test_case_cap = 0;
+	return 0;
+}
+
+void set_test_hash(uint8_t *p, int i)
+{
+	memset(p, (uint8_t)i, hash_size(SHA1_ID));
+}

gitgitgadget

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

This commit provides basic utility classes for the reftable library.

Since the reftable library must compile standalone, there may be some overlap with git-core utility functions.

---
 Makefile                  |  26 ++++++-
 reftable/basics.c         | 131 +++++++++++++++++++++++++++++++++
 reftable/basics.h         |  48 +++++++++++++
 reftable/blocksource.c    | 148 ++++++++++++++++++++++++++++++++++++++
 reftable/blocksource.h    |  22 ++++++
 reftable/compat.c         | 110 ++++++++++++++++++++++++++++
 reftable/compat.h         |  48 +++++++++++++
 reftable/publicbasics.c   | 100 ++++++++++++++++++++++++++
 reftable/reftable-tests.h |  22 ++++++
 reftable/strbuf.c         | 142 ++++++++++++++++++++++++++++++++++++
 reftable/strbuf.h         |  80 +++++++++++++++++++++
 reftable/strbuf_test.c    |  37 ++++++++++
 reftable/system.h         |  51 +++++++++++++
 t/helper/test-reftable.c  |   8 +++
 t/helper/test-tool.c      |   1 +
 t/helper/test-tool.h      |   1 +
 16 files changed, 972 insertions(+), 3 deletions(-)
 create mode 100644 reftable/basics.c
 create mode 100644 reftable/basics.h
 create mode 100644 reftable/blocksource.c
 create mode 100644 reftable/blocksource.h
 create mode 100644 reftable/compat.c
 create mode 100644 reftable/compat.h
 create mode 100644 reftable/publicbasics.c
 create mode 100644 reftable/reftable-tests.h
 create mode 100644 reftable/strbuf.c
 create mode 100644 reftable/strbuf.h
 create mode 100644 reftable/strbuf_test.c
 create mode 100644 reftable/system.h
 create mode 100644 t/helper/test-reftable.c

index 86e5411f39..66158525a9 100644
@@ -720,6 +720,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

@@ -799,6 +800,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 += config-list.h
 GENERATED_H += command-list.h

@@ -1160,7 +1163,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)

@@ -2341,10 +2344,21 @@ XDIFF_OBJS += xdiff/xpatience.o
 XDIFF_OBJS += xdiff/xprepare.o
 XDIFF_OBJS += xdiff/xutils.o
 
+REFTABLE_OBJS += reftable/basics.o
+REFTABLE_OBJS += reftable/blocksource.o
+REFTABLE_OBJS += reftable/publicbasics.o
+REFTABLE_OBJS += reftable/compat.o
+REFTABLE_OBJS += reftable/strbuf.o
+
+REFTABLE_TEST_OBJS += reftable/strbuf_test.o
+REFTABLE_TEST_OBJS += reftable/test_framework.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

@@ -2474,6 +2488,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

@@ -2752,7 +2772,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

@@ -3080,7 +3100,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)

new file mode 100644
index 0000000000..3faf83fa9d
@@ -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 "strbuf.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

new file mode 100644
index 0000000000..e38471888f
@@ -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 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 strbuf_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 0000000000..39f561c81a
@@ -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
+*/
+
+#include "strbuf.h"
+
+#include "system.h"
+
+#include "basics.h"
+#include "test_framework.h"
+#include "reftable-tests.h"
+
+static void test_strbuf(void)
+{
+	struct strbuf s = STRBUF_INIT;
+	struct strbuf t = STRBUF_INIT;
+
+	strbuf_addstr(&s, "abc");
+	assert(0 == strcmp("abc", s.buf));
+
+	strbuf_addstr(&t, "pqr");
+	strbuf_addbuf(&s, &t);
+	assert(0 == strcmp("abcpqr", s.buf));
+
+	strbuf_release(&s);
+	strbuf_release(&t);
+}
+
+int strbuf_test_main(int argc, const char *argv[])
+{
+	add_test_case("test_strbuf", &test_strbuf);
+	return test_main(argc, argv);
+}

new file mode 100644
index 0000000000..7d50aa6bcc
@@ -0,0 +1,8 @@
+#include "reftable/reftable-tests.h"
+#include "test-tool.h"
+
+int cmd__reftable(int argc, const char **argv)
+{
+	strbuf_test_main(argc, argv);
+	return 0;
+}

index 590b2efca7..10366b7b76 100644
@@ -52,6 +52,7 @@ static struct test_cmd cmds[] = {
 	{ "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 ddc8e990e9..d52ba2f5e5 100644
@@ -41,6 +41,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);

gitgitgadget

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

---
 Makefile                 |    2 +
 reftable/constants.h     |   21 +
 reftable/record.c        | 1114 ++++++++++++++++++++++++++++++++++++++
 reftable/record.h        |  143 +++++
 reftable/record_test.c   |  410 ++++++++++++++
 t/helper/test-reftable.c |    1 +
 6 files changed, 1691 insertions(+)
 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

index 66158525a9..0fb0048c34 100644
@@ -2348,8 +2348,10 @@ REFTABLE_OBJS += reftable/basics.o
 REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/compat.o
+REFTABLE_OBJS += reftable/record.o
 REFTABLE_OBJS += reftable/strbuf.o
 
+REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/strbuf_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 

new file mode 100644
index 0000000000..5eee72c4c1
@@ -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 7d50aa6bcc..9341272089 100644
@@ -3,6 +3,7 @@
 
 int cmd__reftable(int argc, const char **argv)
 {
+	record_test_main(argc, argv);
 	strbuf_test_main(argc, argv);
 	return 0;
 }

gitgitgadget

Thanks for bringing this up. I did see this before, but I've been unable to reproduce this locally, and I forgot about it.

The problem is actually triggered by the Git-provided put_be64() (which appears unused in the Git source code). The definition

  #define put_be64(p, v) do { *(uint64_t *)(p) = htonll(v); } while (0)

is trying to reinterpret a char* as a uint64_t* , which is illegal in strict aliasing rules? I originally had

+void put_be64(uint8_t *out, uint64_t v)
+{
+ int i = sizeof(uint64_t);
+ while (i--) {
+ out[i] = (uint8_t)(v & 0xff);
+ v >>= 8;
+ }
+}

in my reftable library, which is portable. Is there a reason for the magic with htonll and friends?

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

Ah, thanks for finding that. I think this resolves the mystery I had around aliasing warnings with put_be32() in f39ad38410 (fast-export: use local array to store anonymized oid, 2020-06-25). I got confused because when I looked at the implementation of put_be32(), I stupidly looked at the NO_ALIGNED_LOADS fallback code, which indeed does not alias. But the one we use on x86 does.

I thought this would be OK because C allows aliasing through "char *" pointers. But I think it may only go the other way. I.e., you can type-pun a uint64_t as a char, but not the other way around. But then why doesn't basically every use of put_be32() and put_be64() complain?

Presumably it was thought to be faster. This comes originally from the block-sha1 code in 660231aa97 (block-sha1: support for architectures with memory alignment restrictions, 2009-08-12). I don't know how it compares in practice, and especially these days.

Our fallback routines are similar to an unrolled version of what you wrote above.

-Peff

We should be able to measure it pretty easily, since block-sha1 uses a lot of get_be32/put_be32. I generated a 4GB random file, built with BLK_SHA1=Yes and -O2, and timed:

t/helper/test-tool sha1 <foo.rand

Then I did the same, but building with -DNO_UNALIGNED_LOADS. The latter actually ran faster, by a small margin. Here are the hyperfine results:

[stock]
Time (mean ± σ): 6.638 s ± 0.081 s [User: 6.269 s, System: 0.368 s]
Range (min … max): 6.550 s … 6.841 s 10 runs

[-DNO_UNALIGNED_LOADS]
Time (mean ± σ): 6.418 s ± 0.015 s [User: 6.058 s, System: 0.360 s]
Range (min … max): 6.394 s … 6.447 s 10 runs

For casual use as in reftables I doubt the difference is even measurable. But this result implies that perhaps we ought to just be using the fallback version all the time.

-Peff

I like that one. One less configurable knob that makes us execute different codepaths is one less thing to be worried about.

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

Includes a code snippet copied from zlib

---
 Makefile                 |   3 +
 reftable/.gitattributes  |   1 +
 reftable/block.c         | 443 +++++++++++++++++++++++++++++++++++++++
 reftable/block.h         | 129 ++++++++++++
 reftable/block_test.c    | 158 ++++++++++++++
 reftable/zlib-compat.c   |  92 ++++++++
 t/helper/test-reftable.c |   1 +
 7 files changed, 827 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 0fb0048c34..a897818a7e 100644
@@ -2345,12 +2345,15 @@ XDIFF_OBJS += xdiff/xprepare.o
 XDIFF_OBJS += xdiff/xutils.o
 
 REFTABLE_OBJS += reftable/basics.o
+REFTABLE_OBJS += reftable/block.o
 REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/compat.o
 REFTABLE_OBJS += reftable/record.o
 REFTABLE_OBJS += reftable/strbuf.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/strbuf_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o

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

index 9341272089..81a9bd5667 100644
@@ -3,6 +3,7 @@
 
 int cmd__reftable(int argc, const char **argv)
 {
+	block_test_main(argc, argv);
 	record_test_main(argc, argv);
 	strbuf_test_main(argc, argv);
 	return 0;

gitgitgadget

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

This is necessary for building a OID => ref map on write

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

index a897818a7e..b96c235087 100644
@@ -2351,12 +2351,14 @@ REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/compat.o
 REFTABLE_OBJS += reftable/record.o
 REFTABLE_OBJS += reftable/strbuf.o
+REFTABLE_OBJS += reftable/tree.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/strbuf_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.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 0000000000..954512e9a3
@@ -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 81a9bd5667..9c4e0f42dc 100644
@@ -6,5 +6,6 @@ int cmd__reftable(int argc, const char **argv)
 	block_test_main(argc, argv);
 	record_test_main(argc, argv);
 	strbuf_test_main(argc, argv);
+	tree_test_main(argc, argv);
 	return 0;
 }

gitgitgadget

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

---
 Makefile          |   1 +
 reftable/writer.c | 664 ++++++++++++++++++++++++++++++++++++++++++++++
 reftable/writer.h |  60 +++++
 3 files changed, 725 insertions(+)
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h

index b96c235087..a200633945 100644
@@ -2352,6 +2352,7 @@ REFTABLE_OBJS += reftable/compat.o
 REFTABLE_OBJS += reftable/record.o
 REFTABLE_OBJS += reftable/strbuf.o
 REFTABLE_OBJS += reftable/tree.o
+REFTABLE_OBJS += reftable/writer.o
 REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/block_test.o

gitgitgadget

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

---
 Makefile            |   3 +
 reftable/iter.c     | 242 +++++++++++++++
 reftable/iter.h     |  72 +++++
 reftable/reader.c   | 733 ++++++++++++++++++++++++++++++++++++++++++++
 reftable/reader.h   |  78 +++++
 reftable/reftable.c | 104 +++++++
 6 files changed, 1232 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.c

index a200633945..275fc4227c 100644
@@ -2349,7 +2349,10 @@ REFTABLE_OBJS += reftable/block.o
 REFTABLE_OBJS += reftable/blocksource.o
 REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/compat.o
+REFTABLE_OBJS += reftable/iter.o
+REFTABLE_OBJS += reftable/reader.o
 REFTABLE_OBJS += reftable/record.o
+REFTABLE_OBJS += reftable/reftable.o
 REFTABLE_OBJS += reftable/strbuf.o
 REFTABLE_OBJS += reftable/tree.o
 REFTABLE_OBJS += reftable/writer.o

gitgitgadget

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

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

index 275fc4227c..22dd31e7ff 100644
@@ -2360,6 +2360,7 @@ REFTABLE_OBJS += reftable/zlib-compat.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/strbuf_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 REFTABLE_TEST_OBJS += reftable/tree_test.o

index 9c4e0f42dc..2273fdfe39 100644
@@ -5,6 +5,7 @@ int cmd__reftable(int argc, const char **argv)
 {
 	block_test_main(argc, argv);
 	record_test_main(argc, argv);
+	reftable_test_main(argc, argv);
 	strbuf_test_main(argc, argv);
 	tree_test_main(argc, argv);
 	return 0;

gitgitgadget

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

This will be further split up once preceding commits have passed review.

---
 Makefile                 |    8 +-
 reftable/VERSION         |    1 +
 reftable/dump.c          |  212 +++++++
 reftable/merged.c        |  358 +++++++++++
 reftable/merged.h        |   39 ++
 reftable/merged_test.c   |  331 +++++++++++
 reftable/pq.c            |  115 ++++
 reftable/pq.h            |   34 ++
 reftable/refname.c       |  209 +++++++
 reftable/refname.h       |   38 ++
 reftable/refname_test.c  |  100 ++++
 reftable/stack.c         | 1224 ++++++++++++++++++++++++++++++++++++++
 reftable/stack.h         |   50 ++
 reftable/stack_test.c    |  787 ++++++++++++++++++++++++
 reftable/update.sh       |   22 +
 t/helper/test-reftable.c |    3 +
 16 files changed, 3530 insertions(+), 1 deletion(-)
 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/stack.c
 create mode 100644 reftable/stack.h
 create mode 100644 reftable/stack_test.c
 create mode 100755 reftable/update.sh

index 22dd31e7ff..6652259baf 100644
@@ -2347,12 +2347,16 @@ XDIFF_OBJS += xdiff/xutils.o
 REFTABLE_OBJS += reftable/basics.o
 REFTABLE_OBJS += reftable/block.o
 REFTABLE_OBJS += reftable/blocksource.o
-REFTABLE_OBJS += reftable/publicbasics.o
 REFTABLE_OBJS += reftable/compat.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/strbuf.o
 REFTABLE_OBJS += reftable/tree.o
 REFTABLE_OBJS += reftable/writer.o

@@ -2360,7 +2364,9 @@ REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/block_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/strbuf_test.o
 REFTABLE_TEST_OBJS += reftable/test_framework.o
 REFTABLE_TEST_OBJS += reftable/tree_test.o

new file mode 100644
index 0000000000..7553c395eb
@@ -0,0 +1 @@
+b8ec0f74c74cb6752eb2033ad8e755a9c19aad15 C: add missing header

new file mode 100644
index 0000000000..66a1d71830
@@ -0,0 +1,39 @@
+/*
+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"
+#include "reftable.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_clear(struct reftable_merged_table *mt);
+int merged_table_seek_record(struct reftable_merged_table *mt,
+			     struct reftable_iterator *it,
+			     struct reftable_record *rec);
+
+#endif

new file mode 100644
index 0000000000..918ac3990d
@@ -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 PQ_H
+#define PQ_H
+
+#include "record.h"
+
+struct pq_entry {
+	int index;
+	struct reftable_record rec;
+};
+
+int pq_less(struct pq_entry a, struct pq_entry b);
+
+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_clear(struct merged_iter_pqueue *pq);
+
+#endif

new file mode 100644
index 0000000000..13bf1e6861
@@ -0,0 +1,38 @@
+/*
+  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.h"
+
+struct modification {
+	struct reftable_table tab;
+
+	char **add;
+	size_t add_len;
+
+	char **del;
+	size_t del_len;
+};
+
+// -1 = error, 0 = found, 1 = not found
+int modification_has_ref(struct modification *mod, const char *name);
+
+// -1 = error, 0 = found, 1 = not found.
+int modification_has_ref_with_prefix(struct modification *mod,
+				     const char *prefix);
+
+// 0 = OK.
+int validate_refname(const char *name);
+
+int validate_ref_record_addition(struct reftable_table tab,
+				 struct reftable_ref_record *recs, size_t sz);
+
+int modification_validate(struct modification *mod);
+
+#endif

new file mode 100755
index 0000000000..4dadd875f4

index 2273fdfe39..def8883439 100644

gitgitgadget

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

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

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

---
 Makefile                 | 2 ++
 t/helper/test-reftable.c | 5 +++++
 t/helper/test-tool.c     | 1 +
 t/helper/test-tool.h     | 1 +
 4 files changed, 9 insertions(+)

index 6652259baf..ee82ff2915 100644
@@ -2363,6 +2363,8 @@ REFTABLE_OBJS += reftable/writer.o
 REFTABLE_OBJS += reftable/zlib-compat.o
 
 REFTABLE_TEST_OBJS += reftable/block_test.o
+REFTABLE_TEST_OBJS += reftable/dump.o
+REFTABLE_TEST_OBJS += reftable/merged_test.o
 REFTABLE_TEST_OBJS += reftable/record_test.o
 REFTABLE_TEST_OBJS += reftable/refname_test.o
 REFTABLE_TEST_OBJS += reftable/reftable_test.o

index def8883439..aff4fbccda 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 10366b7b76..9e689f9d2b 100644
@@ -53,6 +53,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 d52ba2f5e5..bf833e01d4 100644
@@ -17,6 +17,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__genrandom(int argc, const char **argv);
 int cmd__genzeros(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.

Han-Wen Nienhuys (12):
reftable: add LICENSE
reftable: define the public API
reftable: add a barebones unittest framework
reftable: utility functions
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: file level tests
reftable: rest of library
reftable: "test-tool dump-reftable" command.

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

 Makefile                                   |   46 +-
 config.mak.uname                           |    2 +-
 contrib/buildsystems/Generators/Vcxproj.pm |   11 +-
 reftable/.gitattributes                    |    1 +
 reftable/LICENSE                           |   31 +
 reftable/VERSION                           |    1 +
 reftable/basics.c                          |  131 +++
 reftable/basics.h                          |   48 +
 reftable/block.c                           |  441 +++++++
 reftable/block.h                           |  129 ++
 reftable/block_test.c                      |  158 +++
 reftable/blocksource.c                     |  148 +++
 reftable/blocksource.h                     |   22 +
 reftable/compat.c                          |  110 ++
 reftable/compat.h                          |   48 +
 reftable/constants.h                       |   21 +
 reftable/dump.c                            |  212 ++++
 reftable/iter.c                            |  242 ++++
 reftable/iter.h                            |   72 ++
 reftable/merged.c                          |  358 ++++++
 reftable/merged.h                          |   36 +
 reftable/merged_test.c                     |  331 ++++++
 reftable/pq.c                              |  115 ++
 reftable/pq.h                              |   32 +
 reftable/publicbasics.c                    |  100 ++
 reftable/reader.c                          |  733 ++++++++++++
 reftable/reader.h                          |   78 ++
 reftable/record.c                          | 1116 ++++++++++++++++++
 reftable/record.h                          |  137 +++
 reftable/record_test.c                     |  410 +++++++
 reftable/refname.c                         |  209 ++++
 reftable/refname.h                         |   28 +
 reftable/refname_test.c                    |  100 ++
 reftable/reftable-tests.h                  |   22 +
 reftable/reftable.c                        |  104 ++
 reftable/reftable.h                        |  585 +++++++++
 reftable/reftable_test.c                   |  585 +++++++++
 reftable/stack.c                           | 1240 ++++++++++++++++++++
 reftable/stack.h                           |   40 +
 reftable/stack_test.c                      |  788 +++++++++++++
 reftable/strbuf.c                          |  142 +++
 reftable/strbuf.h                          |   80 ++
 reftable/strbuf_test.c                     |   37 +
 reftable/system.h                          |   51 +
 reftable/test_framework.c                  |   68 ++
 reftable/test_framework.h                  |   59 +
 reftable/tree.c                            |   63 +
 reftable/tree.h                            |   34 +
 reftable/tree_test.c                       |   62 +
 reftable/update.sh                         |   22 +
 reftable/writer.c                          |  673 +++++++++++
 reftable/writer.h                          |   51 +
 reftable/zlib-compat.c                     |   92 ++
 t/helper/test-reftable.c                   |   20 +
 t/helper/test-tool.c                       |    2 +
 t/helper/test-tool.h                       |    2 +
 56 files changed, 10474 insertions(+), 5 deletions(-)
 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/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/compat.c
 create mode 100644 reftable/compat.h
 create mode 100644 reftable/constants.h
 create mode 100644 reftable/dump.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-tests.h
 create mode 100644 reftable/reftable.c
 create mode 100644 reftable/reftable.h
 create mode 100644 reftable/reftable_test.c
 create mode 100644 reftable/stack.c
 create mode 100644 reftable/stack.h
 create mode 100644 reftable/stack_test.c
 create mode 100644 reftable/strbuf.c
 create mode 100644 reftable/strbuf.h
 create mode 100644 reftable/strbuf_test.c
 create mode 100644 reftable/system.h
 create mode 100644 reftable/test_framework.c
 create mode 100644 reftable/test_framework.h
 create mode 100644 reftable/tree.c
 create mode 100644 reftable/tree.h
 create mode 100644 reftable/tree_test.c
 create mode 100755 reftable/update.sh
 create mode 100644 reftable/writer.c
 create mode 100644 reftable/writer.h
 create mode 100644 reftable/zlib-compat.c
 create mode 100644 t/helper/test-reftable.c

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

Range-diff vs v1:

  1:  f697eac228 =  1:  6228103b4a reftable: add LICENSE
  2:  e2dbc84833 =  2:  5d1b946ab5 reftable: define the public API
  3:  0f6efc065c =  3:  01a669a731 vcxproj: adjust for the reftable changes
  4:  7bf59d491d !  4:  b94c5f5c61 reftable: add a barebones unittest framework
     @@ reftable/test_framework.c (new)
      +#include "system.h"
      +#include "basics.h"
      +
     -+struct test_case **test_cases;
     -+int test_case_len;
     -+int test_case_cap;
     ++static struct test_case **test_cases;
     ++static int test_case_len;
     ++static int test_case_cap;
      +
     -+struct test_case *new_test_case(const char *name, void (*testfunc)(void))
     ++static struct test_case *new_test_case(const char *name, void (*testfunc)(void))
      +{
      +	struct test_case *tc = reftable_malloc(sizeof(struct test_case));
      +	tc->name = name;
     @@ reftable/test_framework.c (new)
      +		reftable_free(test_cases[i]);
      +	}
      +	reftable_free(test_cases);
     -+	test_cases = 0;
     ++	test_cases = NULL;
      +	test_case_len = 0;
      +	test_case_cap = 0;
      +	return 0;
     @@ reftable/test_framework.h (new)
      +	void (*testfunc)(void);
      +};
      +
     -+struct test_case *new_test_case(const char *name, void (*testfunc)(void));
      +struct test_case *add_test_case(const char *name, void (*testfunc)(void));
      +int test_main(int argc, const char *argv[]);
      +
  5:  570a8c4bca !  5:  4190da597e reftable: utility functions
     @@ reftable/blocksource.c (new)
      +	return ((struct strbuf *)b)->len;
      +}
      +
     -+struct reftable_block_source_vtable strbuf_vtable = {
     ++static struct reftable_block_source_vtable strbuf_vtable = {
      +	.size = &strbuf_size,
      +	.read_block = &strbuf_read_block,
      +	.return_block = &strbuf_return_block,
     @@ reftable/blocksource.c (new)
      +	reftable_free(dest->data);
      +}
      +
     -+struct reftable_block_source_vtable malloc_vtable = {
     ++static struct reftable_block_source_vtable malloc_vtable = {
      +	.return_block = &malloc_return_block,
      +};
      +
     -+struct reftable_block_source malloc_block_source_instance = {
     ++static struct reftable_block_source malloc_block_source_instance = {
      +	.ops = &malloc_vtable,
      +};
      +
     @@ reftable/blocksource.c (new)
      +	return size;
      +}
      +
     -+struct reftable_block_source_vtable file_vtable = {
     ++static struct reftable_block_source_vtable file_vtable = {
      +	.size = &file_size,
      +	.read_block = &file_read_block,
      +	.return_block = &file_return_block,
     @@ reftable/publicbasics.c (new)
      +	}
      +}
      +
     -+void *(*reftable_malloc_ptr)(size_t sz) = &malloc;
     -+void *(*reftable_realloc_ptr)(void *, size_t) = &realloc;
     -+void (*reftable_free_ptr)(void *) = &free;
     ++static void *(*reftable_malloc_ptr)(size_t sz) = &malloc;
     ++static void *(*reftable_realloc_ptr)(void *, size_t) = &realloc;
     ++static void (*reftable_free_ptr)(void *) = &free;
      +
      +void *reftable_malloc(size_t sz)
      +{
  6:  791f69c000 !  6:  8eb944ea9b reftable: (de)serialization for the polymorphic record type.
     @@ reftable/record.c (new)
      +		(const struct reftable_ref_record *)p);
      +}
      +
     -+struct reftable_record_vtable reftable_ref_record_vtable = {
     ++static struct reftable_record_vtable reftable_ref_record_vtable = {
      +	.key = &reftable_ref_record_key,
      +	.type = BLOCK_TYPE_REF,
      +	.copy_from = &reftable_ref_record_copy_from,
     @@ reftable/record.c (new)
      +	return 0;
      +}
      +
     -+struct reftable_record_vtable reftable_obj_record_vtable = {
     ++static struct reftable_record_vtable reftable_obj_record_vtable = {
      +	.key = &reftable_obj_record_key,
      +	.type = BLOCK_TYPE_OBJ,
      +	.copy_from = &reftable_obj_record_copy_from,
     @@ reftable/record.c (new)
      +		(const struct reftable_log_record *)p);
      +}
      +
     -+struct reftable_record_vtable reftable_log_record_vtable = {
     ++static struct reftable_record_vtable reftable_log_record_vtable = {
      +	.key = &reftable_log_record_key,
      +	.type = BLOCK_TYPE_LOG,
      +	.copy_from = &reftable_log_record_copy_from,
     @@ reftable/record.c (new)
      +	return rec;
      +}
      +
     -+void *reftable_record_yield(struct reftable_record *rec)
     ++/* clear out the record, yielding the reftable_record data that was
     ++ * encapsulated. */
     ++static void *reftable_record_yield(struct reftable_record *rec)
      +{
      +	void *p = rec->data;
      +	rec->data = NULL;
     @@ reftable/record.c (new)
      +	return start.len - in.len;
      +}
      +
     -+struct reftable_record_vtable reftable_index_record_vtable = {
     ++static struct reftable_record_vtable reftable_index_record_vtable = {
      +	.key = &reftable_index_record_key,
      +	.type = BLOCK_TYPE_INDEX,
      +	.copy_from = &reftable_index_record_copy_from,
     @@ reftable/record.h (new)
      +/* creates a malloced record of the given type. Dispose with record_destroy */
      +struct reftable_record reftable_new_record(uint8_t typ);
      +
     -+extern struct reftable_record_vtable reftable_ref_record_vtable;
     -+
      +/* Encode `key` into `dest`. Sets `is_restart` to indicate a restart. Returns
      +   number of bytes written. */
      +int reftable_encode_key(int *is_restart, struct string_view dest,
     @@ reftable/record.h (new)
      +/* zeroes out the embedded record */
      +void reftable_record_clear(struct reftable_record *rec);
      +
     -+/* clear out the record, yielding the reftable_record data that was
     -+ * encapsulated. */
     -+void *reftable_record_yield(struct reftable_record *rec);
     -+
      +/* clear and deallocate embedded record, and zero `rec`. */
      +void reftable_record_destroy(struct reftable_record *rec);
      +
     @@ reftable/record_test.c (new)
      +	int i = 0;
      +
      +	for (i = 0; i <= 3; i++) {
     -+		struct reftable_ref_record in = { 0 };
     ++		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_record rec_out = { 0 };
     ++		struct reftable_record rec_out = { NULL };
      +		struct strbuf key = STRBUF_INIT;
     -+		struct reftable_record rec = { 0 };
     ++		struct reftable_record rec = { NULL };
      +		uint8_t buffer[1024] = { 0 };
      +		struct string_view dest = {
      +			.buf = buffer,
     @@ reftable/record_test.c (new)
      +	set_test_hash(in[0].new_hash, 1);
      +	set_test_hash(in[0].old_hash, 2);
      +	for (int i = 0; i < ARRAY_SIZE(in); i++) {
     -+		struct reftable_record rec = { 0 };
     ++		struct reftable_record rec = { NULL };
      +		struct strbuf key = STRBUF_INIT;
      +		uint8_t buffer[1024] = { 0 };
      +		struct string_view dest = {
     @@ reftable/record_test.c (new)
      +			.email = xstrdup("old@email"),
      +			.message = xstrdup("old message"),
      +		};
     -+		struct reftable_record rec_out = { 0 };
     ++		struct reftable_record rec_out = { NULL };
      +		int n, m, valtype;
      +
      +		reftable_record_from_log(&rec, &in[i]);
     @@ reftable/record_test.c (new)
      +			.buf = buffer,
      +			.len = sizeof(buffer),
      +		};
     -+		struct reftable_record rec = { 0 };
     ++		struct reftable_record rec = { NULL };
      +		struct strbuf key = STRBUF_INIT;
     -+		struct reftable_obj_record out = { 0 };
     -+		struct reftable_record rec_out = { 0 };
     ++		struct reftable_obj_record out = { NULL };
     ++		struct reftable_record rec_out = { NULL };
      +		int n, m;
      +		uint8_t extra;
      +
     @@ reftable/record_test.c (new)
      +		.len = sizeof(buffer),
      +	};
      +	struct strbuf key = STRBUF_INIT;
     -+	struct reftable_record rec = { 0 };
     ++	struct reftable_record rec = { NULL };
      +	struct reftable_index_record out = { .last_key = STRBUF_INIT };
      +	struct reftable_record out_rec = { NULL };
      +	int n, m;
  7:  1ba8e3eb30 !  7:  757dd30fe2 reftable: reading/writing blocks
     @@ reftable/block.c (new)
      +	abort();
      +}
      +
     -+int block_writer_register_restart(struct block_writer *w, int n, int restart,
     -+				  struct strbuf *key);
     ++static int block_writer_register_restart(struct block_writer *w, int n,
     ++					 int is_restart, struct strbuf *key)
     ++{
     ++	int rlen = w->restart_len;
     ++	if (rlen >= MAX_RESTARTS) {
     ++		is_restart = 0;
     ++	}
     ++
     ++	if (is_restart) {
     ++		rlen++;
     ++	}
     ++	if (2 + 3 * rlen + n > w->block_size - w->next)
     ++		return -1;
     ++	if (is_restart) {
     ++		if (w->restart_len == w->restart_cap) {
     ++			w->restart_cap = w->restart_cap * 2 + 1;
     ++			w->restarts = reftable_realloc(
     ++				w->restarts, sizeof(uint32_t) * w->restart_cap);
     ++		}
     ++
     ++		w->restarts[w->restart_len++] = w->next;
     ++	}
     ++
     ++	w->next += n;
     ++
     ++	strbuf_reset(&w->last_key);
     ++	strbuf_addbuf(&w->last_key, key);
     ++	w->entries++;
     ++	return 0;
     ++}
      +
      +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)
     @@ reftable/block.c (new)
      +	return -1;
      +}
      +
     -+int block_writer_register_restart(struct block_writer *w, int n, int is_restart,
     -+				  struct strbuf *key)
     -+{
     -+	int rlen = w->restart_len;
     -+	if (rlen >= MAX_RESTARTS) {
     -+		is_restart = 0;
     -+	}
     -+
     -+	if (is_restart) {
     -+		rlen++;
     -+	}
     -+	if (2 + 3 * rlen + n > w->block_size - w->next)
     -+		return -1;
     -+	if (is_restart) {
     -+		if (w->restart_len == w->restart_cap) {
     -+			w->restart_cap = w->restart_cap * 2 + 1;
     -+			w->restarts = reftable_realloc(
     -+				w->restarts, sizeof(uint32_t) * w->restart_cap);
     -+		}
     -+
     -+		w->restarts[w->restart_len++] = w->next;
     -+	}
     -+
     -+	w->next += n;
     -+
     -+	strbuf_reset(&w->last_key);
     -+	strbuf_addbuf(&w->last_key, key);
     -+	w->entries++;
     -+	return 0;
     -+}
      +
      +int block_writer_finish(struct block_writer *w)
      +{
     @@ reftable/block_test.c (new)
      +	char *names[30];
      +	const int N = ARRAY_SIZE(names);
      +	const int block_size = 1024;
     -+	struct reftable_block block = { 0 };
     ++	struct reftable_block block = { NULL };
      +	struct block_writer bw = {
      +		.last_key = STRBUF_INIT,
      +	};
     -+	struct reftable_ref_record ref = { 0 };
     -+	struct reftable_record rec = { 0 };
     ++	struct reftable_ref_record ref = { NULL };
     ++	struct reftable_record rec = { NULL };
      +	int i = 0;
      +	int n;
      +	struct block_reader br = { 0 };
  8:  17fb8d050d !  8:  e30a7e0281 reftable: a generic binary tree implementation
     @@ reftable/tree_test.c (new)
      +{
      +	struct tree_node *root = NULL;
      +
     -+	void *values[11] = { 0 };
     -+	struct tree_node *nodes[11] = { 0 };
     ++	void *values[11] = { NULL };
     ++	struct tree_node *nodes[11] = { NULL };
      +	int i = 1;
     -+	struct curry c = { 0 };
     ++	struct curry c = { NULL };
      +	do {
      +		nodes[i] = tree_search(values + i, &root, &test_compare, 1);
      +		i = (i * 7) % 11;
  9:  4e40fc3b40 !  9:  68aee16e60 reftable: write reftable files
     @@ reftable/writer.c (new)
      +#include "reftable.h"
      +#include "tree.h"
      +
     ++/* finishes a block, and writes it to storage */
     ++static int writer_flush_block(struct reftable_writer *w);
     ++
     ++/* deallocates memory related to the index */
     ++static void writer_clear_index(struct reftable_writer *w);
     ++
     ++/* finishes writing a 'r' (refs) or 'g' (reflogs) section */
     ++static int writer_finish_public_section(struct reftable_writer *w);
     ++
      +static struct reftable_block_stats *
      +writer_reftable_block_stats(struct reftable_writer *w, uint8_t typ)
      +{
     @@ reftable/writer.c (new)
      +int reftable_writer_add_ref(struct reftable_writer *w,
      +			    struct reftable_ref_record *ref)
      +{
     -+	struct reftable_record rec = { 0 };
     ++	struct reftable_record rec = { NULL };
      +	struct reftable_ref_record copy = *ref;
      +	int err = 0;
      +
     @@ reftable/writer.c (new)
      +int reftable_writer_add_log(struct reftable_writer *w,
      +			    struct reftable_log_record *log)
      +{
     -+	struct reftable_record rec = { 0 };
     ++	struct reftable_record rec = { NULL };
      +	char *input_log_message = log->message;
      +	struct strbuf cleaned_message = STRBUF_INIT;
      +	int err;
     @@ reftable/writer.c (new)
      +		w->index_len = 0;
      +		w->index_cap = 0;
      +		for (i = 0; i < idx_len; i++) {
     -+			struct reftable_record rec = { 0 };
     ++			struct reftable_record rec = { NULL };
      +			reftable_record_from_index(&rec, idx + i);
      +			if (block_writer_add(w->block_writer, &rec) == 0) {
      +				continue;
     @@ reftable/writer.c (new)
      +		.offsets = entry->offsets,
      +		.offset_len = entry->offset_len,
      +	};
     -+	struct reftable_record rec = { 0 };
     ++	struct reftable_record rec = { NULL };
      +	if (arg->err < 0)
      +		goto done;
      +
     @@ reftable/writer.c (new)
      +static int writer_dump_object_index(struct reftable_writer *w)
      +{
      +	struct write_record_arg closure = { .w = w };
     -+	struct common_prefix_arg common = { 0 };
     ++	struct common_prefix_arg common = { NULL };
      +	if (w->obj_index_tree != NULL) {
      +		infix_walk(w->obj_index_tree, &update_common, &common);
      +	}
     @@ reftable/writer.c (new)
      +	return writer_finish_section(w);
      +}
      +
     -+int writer_finish_public_section(struct reftable_writer *w)
     ++static int writer_finish_public_section(struct reftable_writer *w)
      +{
      +	uint8_t typ = 0;
      +	int err = 0;
     @@ reftable/writer.c (new)
      +	return err;
      +}
      +
     -+void writer_clear_index(struct reftable_writer *w)
     ++static void writer_clear_index(struct reftable_writer *w)
      +{
      +	int i = 0;
      +	for (i = 0; i < w->index_len; i++) {
     @@ reftable/writer.c (new)
      +	w->index_cap = 0;
      +}
      +
     -+const int debug = 0;
     ++static const int debug = 0;
      +
      +static int writer_flush_nonempty_block(struct reftable_writer *w)
      +{
     @@ reftable/writer.c (new)
      +	return 0;
      +}
      +
     -+int writer_flush_block(struct reftable_writer *w)
     ++static int writer_flush_block(struct reftable_writer *w)
      +{
      +	if (w->block_writer == NULL)
      +		return 0;
     @@ reftable/writer.h (new)
      +	struct reftable_stats stats;
      +};
      +
     -+/* finishes a block, and writes it to storage */
     -+int writer_flush_block(struct reftable_writer *w);
     -+
     -+/* deallocates memory related to the index */
     -+void writer_clear_index(struct reftable_writer *w);
     -+
     -+/* finishes writing a 'r' (refs) or 'g' (reflogs) section */
     -+int writer_finish_public_section(struct reftable_writer *w);
     -+
      +#endif
 10:  25259b683b ! 10:  c196de7f06 reftable: read reftable files
     @@ reftable/iter.c (new)
      +{
      +}
      +
     -+struct reftable_iterator_vtable empty_vtable = {
     ++static struct reftable_iterator_vtable empty_vtable = {
      +	.next = &empty_iterator_next,
      +	.close = &empty_iterator_close,
      +};
     @@ reftable/iter.c (new)
      +	return err;
      +}
      +
     -+struct reftable_iterator_vtable filtering_ref_iterator_vtable = {
     ++static struct reftable_iterator_vtable filtering_ref_iterator_vtable = {
      +	.next = &filtering_ref_iterator_next,
      +	.close = &filtering_ref_iterator_close,
      +};
     @@ reftable/iter.c (new)
      +	return err;
      +}
      +
     -+struct reftable_iterator_vtable indexed_table_ref_iter_vtable = {
     ++static struct reftable_iterator_vtable indexed_table_ref_iter_vtable = {
      +	.next = &indexed_table_ref_iter_next,
      +	.close = &indexed_table_ref_iter_close,
      +};
     @@ reftable/reader.c (new)
      +	block_iter_close(&ti->bi);
      +}
      +
     -+struct reftable_iterator_vtable table_iter_vtable = {
     ++static struct reftable_iterator_vtable table_iter_vtable = {
      +	.next = &table_iter_next_void,
      +	.close = &table_iter_close,
      +};
 11:  3448fcf828 ! 11:  bf6b929b86 reftable: file level tests
     @@ reftable/reftable_test.c (new)
      +{
      +	struct strbuf buf = STRBUF_INIT;
      +	struct reftable_block_source source = { NULL };
     -+	struct reftable_block out = { 0 };
     ++	struct reftable_block out = { NULL };
      +	int n;
      +	uint8_t in[] = "hello";
      +	strbuf_add(&buf, in, sizeof(in));
     @@ reftable/reftable_test.c (new)
      +	};
      +	struct reftable_writer *w =
      +		reftable_new_writer(&strbuf_add_void, buf, &opts);
     -+	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_ref_record ref = { NULL };
      +	int i = 0, n;
     -+	struct reftable_log_record log = { 0 };
     ++	struct reftable_log_record log = { NULL };
      +	const struct reftable_stats *stats = NULL;
      +	*names = reftable_calloc(sizeof(char *) * (N + 1));
      +	reftable_writer_set_limits(w, update_index, update_index);
     @@ reftable/reftable_test.c (new)
      +	struct reftable_write_options opts = {
      +		.block_size = 256,
      +	};
     -+	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_ref_record ref = { NULL };
      +	int i = 0;
     -+	struct reftable_log_record log = { 0 };
     ++	struct reftable_log_record log = { NULL };
      +	int n;
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_reader rd = { 0 };
     -+	struct reftable_block_source source = { 0 };
     ++	struct reftable_iterator it = { NULL };
     ++	struct reftable_reader rd = { NULL };
     ++	struct reftable_block_source source = { NULL };
      +	struct strbuf buf = STRBUF_INIT;
      +	struct reftable_writer *w =
      +		reftable_new_writer(&strbuf_add_void, &buf, &opts);
     @@ reftable/reftable_test.c (new)
      +	reftable_writer_set_limits(w, 0, N);
      +	for (i = 0; i < N; i++) {
      +		char name[256];
     -+		struct reftable_ref_record ref = { 0 };
     ++		struct reftable_ref_record ref = { NULL };
      +		snprintf(name, sizeof(name), "b%02d%0*d", i, 130, 7);
      +		names[i] = xstrdup(name);
      +		ref.refname = name;
     @@ reftable/reftable_test.c (new)
      +	}
      +	for (i = 0; i < N; i++) {
      +		uint8_t hash1[SHA1_SIZE], hash2[SHA1_SIZE];
     -+		struct reftable_log_record log = { 0 };
     ++		struct reftable_log_record log = { NULL };
      +		set_test_hash(hash1, i);
      +		set_test_hash(hash2, i + 1);
      +
     @@ reftable/reftable_test.c (new)
      +	char **names;
      +	struct strbuf buf = STRBUF_INIT;
      +	int N = 50;
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_block_source source = { 0 };
     -+	struct reftable_reader rd = { 0 };
     ++	struct reftable_iterator it = { NULL };
     ++	struct reftable_block_source source = { NULL };
     ++	struct reftable_reader rd = { NULL };
      +	int err = 0;
      +	int j = 0;
      +
     @@ reftable/reftable_test.c (new)
      +	assert_err(err);
      +
      +	while (1) {
     -+		struct reftable_ref_record ref = { 0 };
     ++		struct reftable_ref_record ref = { NULL };
      +		int r = reftable_iterator_next_ref(&it, &ref);
      +		assert(r >= 0);
      +		if (r > 0) {
     @@ reftable/reftable_test.c (new)
      +	char **names;
      +	struct strbuf buf = STRBUF_INIT;
      +	int N = 50;
     -+	struct reftable_reader rd = { 0 };
     -+	struct reftable_block_source source = { 0 };
     ++	struct reftable_reader rd = { NULL };
     ++	struct reftable_block_source source = { NULL };
      +	int err;
      +	int i;
     -+	struct reftable_log_record log = { 0 };
     -+	struct reftable_iterator it = { 0 };
     ++	struct reftable_log_record log = { NULL };
     ++	struct reftable_iterator it = { NULL };
      +
      +	write_table(&names, &buf, N, 256, SHA1_ID);
      +
     @@ reftable/reftable_test.c (new)
      +	char **names;
      +	struct strbuf buf = STRBUF_INIT;
      +	int N = 50;
     -+	struct reftable_reader rd = { 0 };
     -+	struct reftable_block_source source = { 0 };
     ++	struct reftable_reader rd = { NULL };
     ++	struct reftable_block_source source = { NULL };
      +	int err;
      +	int i = 0;
      +
     -+	struct reftable_iterator it = { 0 };
     ++	struct reftable_iterator it = { NULL };
      +	struct strbuf pastLast = STRBUF_INIT;
     -+	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_ref_record ref = { NULL };
      +
      +	write_table(&names, &buf, N, 256, hash_id);
      +
     @@ reftable/reftable_test.c (new)
      +
      +	err = reftable_reader_seek_ref(&rd, &it, pastLast.buf);
      +	if (err == 0) {
     -+		struct reftable_ref_record ref = { 0 };
     ++		struct reftable_ref_record ref = { NULL };
      +		int err = reftable_iterator_next_ref(&it, &ref);
      +		assert(err > 0);
      +	} else {
     @@ reftable/reftable_test.c (new)
      +	struct reftable_write_options opts = {
      +		.block_size = 256,
      +	};
     -+	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_ref_record ref = { NULL };
      +	int i = 0;
      +	int n;
      +	int err;
      +	struct reftable_reader rd;
     -+	struct reftable_block_source source = { 0 };
     ++	struct reftable_block_source source = { NULL };
      +
      +	struct strbuf buf = STRBUF_INIT;
      +	struct reftable_writer *w =
      +		reftable_new_writer(&strbuf_add_void, &buf, &opts);
      +
     -+	struct reftable_iterator it = { 0 };
     ++	struct reftable_iterator it = { NULL };
      +	int j;
      +
      +	set_test_hash(want_hash, 4);
     @@ reftable/reftable_test.c (new)
      +		char name[100];
      +		uint8_t hash1[SHA1_SIZE];
      +		uint8_t hash2[SHA1_SIZE];
     -+		struct reftable_ref_record ref = { 0 };
     ++		struct reftable_ref_record ref = { NULL };
      +
      +		memset(hash, i, sizeof(hash));
      +		memset(fill, 'x', 50);
     @@ reftable/reftable_test.c (new)
      +	struct strbuf buf = STRBUF_INIT;
      +	struct reftable_writer *w =
      +		reftable_new_writer(&strbuf_add_void, &buf, &opts);
     -+	struct reftable_block_source source = { 0 };
     ++	struct reftable_block_source source = { NULL };
      +	struct reftable_reader *rd = NULL;
     -+	struct reftable_ref_record rec = { 0 };
     -+	struct reftable_iterator it = { 0 };
     ++	struct reftable_ref_record rec = { NULL };
     ++	struct reftable_iterator it = { NULL };
      +	int err;
      +
      +	reftable_writer_set_limits(w, 1, 1);
 12:  64d98e60b2 ! 12:  4e38db7f48 reftable: rest of library
     @@ Makefile: REFTABLE_OBJS += reftable/zlib-compat.o
      
       ## reftable/VERSION (new) ##
      @@
     -+b8ec0f74c74cb6752eb2033ad8e755a9c19aad15 C: add missing header
     ++7134eb9f8171a9759800f4187f9e6dde997335e7 C: NULL iso 0 for init
      
       ## reftable/dump.c (new) ##
      @@
     @@ reftable/dump.c (new)
      +
      +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)
     @@ reftable/dump.c (new)
      +{
      +	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);
     @@ reftable/merged.c (new)
      +	return merged_iter_next(mi, rec);
      +}
      +
     -+struct reftable_iterator_vtable merged_iter_vtable = {
     ++static struct reftable_iterator_vtable merged_iter_vtable = {
      +	.next = &merged_iter_next_void,
      +	.close = &merged_iter_close,
      +};
     @@ reftable/merged.c (new)
      +	return mt->min;
      +}
      +
     -+int merged_table_seek_record(struct reftable_merged_table *mt,
     -+			     struct reftable_iterator *it,
     -+			     struct reftable_record *rec)
     ++static int merged_table_seek_record(struct reftable_merged_table *mt,
     ++				    struct reftable_iterator *it,
     ++				    struct reftable_record *rec)
      +{
      +	struct reftable_iterator *iters = reftable_calloc(
      +		sizeof(struct reftable_iterator) * mt->stack_len);
     @@ reftable/merged.c (new)
      +	struct reftable_ref_record ref = {
      +		.refname = (char *)name,
      +	};
     -+	struct reftable_record rec = { 0 };
     ++	struct reftable_record rec = { NULL };
      +	reftable_record_from_ref(&rec, &ref);
      +	return merged_table_seek_record(mt, it, &rec);
      +}
     @@ reftable/merged.c (new)
      +		.refname = (char *)name,
      +		.update_index = update_index,
      +	};
     -+	struct reftable_record rec = { 0 };
     ++	struct reftable_record rec = { NULL };
      +	reftable_record_from_log(&rec, &log);
      +	return merged_table_seek_record(mt, it, &rec);
      +}
     @@ reftable/merged.h (new)
      +};
      +
      +void merged_table_clear(struct reftable_merged_table *mt);
     -+int merged_table_seek_record(struct reftable_merged_table *mt,
     -+			     struct reftable_iterator *it,
     -+			     struct reftable_record *rec);
      +
      +#endif
      
     @@ reftable/merged_test.c (new)
      +
      +static void test_pq(void)
      +{
     -+	char *names[54] = { 0 };
     ++	char *names[54] = { NULL };
      +	int N = ARRAY_SIZE(names) - 1;
      +
     -+	struct merged_iter_pqueue pq = { 0 };
     ++	struct merged_iter_pqueue pq = { NULL };
      +	const char *last = NULL;
      +
      +	int i = 0;
     @@ reftable/merged_test.c (new)
      +	struct reftable_merged_table *mt =
      +		merged_table_from_records(refs, &bs, &readers, sizes, bufs, 2);
      +	int i;
     -+	struct reftable_ref_record ref = { 0 };
     -+	struct reftable_iterator it = { 0 };
     ++	struct reftable_ref_record ref = { NULL };
     ++	struct reftable_iterator it = { NULL };
      +	int err = reftable_merged_table_seek_ref(mt, &it, "a");
      +	assert_err(err);
      +
     @@ reftable/merged_test.c (new)
      +	struct reftable_merged_table *mt =
      +		merged_table_from_records(refs, &bs, &readers, sizes, bufs, 3);
      +
     -+	struct reftable_iterator it = { 0 };
     ++	struct reftable_iterator it = { NULL };
      +	int err = reftable_merged_table_seek_ref(mt, &it, "a");
      +	struct reftable_ref_record *out = NULL;
      +	size_t len = 0;
     @@ reftable/merged_test.c (new)
      +
      +	assert_err(err);
      +	while (len < 100) { /* cap loops/recursion. */
     -+		struct reftable_ref_record ref = { 0 };
     ++		struct reftable_ref_record ref = { NULL };
      +		int err = reftable_iterator_next_ref(&it, &ref);
      +		if (err > 0) {
      +			break;
     @@ reftable/merged_test.c (new)
      +		.update_index = 1,
      +	};
      +	int err;
     -+	struct reftable_block_source source = { 0 };
     ++	struct reftable_block_source source = { NULL };
      +	struct reftable_table *tab = reftable_calloc(sizeof(*tab) * 1);
      +	uint32_t hash_id;
      +	struct reftable_reader *rd = NULL;
     @@ reftable/pq.c (new)
      +#include "system.h"
      +#include "basics.h"
      +
     -+int pq_less(struct pq_entry a, struct pq_entry b)
     ++static int pq_less(struct pq_entry a, struct pq_entry b)
      +{
      +	struct strbuf ak = STRBUF_INIT;
      +	struct strbuf bk = STRBUF_INIT;
     @@ reftable/pq.h (new)
      +	struct reftable_record rec;
      +};
      +
     -+int pq_less(struct pq_entry a, struct pq_entry b);
     -+
      +struct merged_iter_pqueue {
      +	struct pq_entry *heap;
      +	size_t len;
     @@ reftable/refname.c (new)
      +	return strcmp(f_arg->names[k], f_arg->want) >= 0;
      +}
      +
     -+int modification_has_ref(struct modification *mod, const char *name)
     ++static int modification_has_ref(struct modification *mod, const char *name)
      +{
     -+	struct reftable_ref_record ref = { 0 };
     ++	struct reftable_ref_record ref = { NULL };
      +	int err = 0;
      +
      +	if (mod->add_len > 0) {
     @@ reftable/refname.c (new)
      +	mod->del_len = 0;
      +}
      +
     -+int modification_has_ref_with_prefix(struct modification *mod,
     -+				     const char *prefix)
     ++static int modification_has_ref_with_prefix(struct modification *mod,
     ++					    const char *prefix)
      +{
      +	struct reftable_iterator it = { NULL };
      +	struct reftable_ref_record ref = { NULL };
     @@ reftable/refname.c (new)
      +	return err;
      +}
      +
     -+int validate_refname(const char *name)
     ++static int validate_refname(const char *name)
      +{
      +	while (1) {
      +		char *next = strchr(name, '/');
     @@ reftable/refname.h (new)
      +	size_t del_len;
      +};
      +
     -+// -1 = error, 0 = found, 1 = not found
     -+int modification_has_ref(struct modification *mod, const char *name);
     -+
     -+// -1 = error, 0 = found, 1 = not found.
     -+int modification_has_ref_with_prefix(struct modification *mod,
     -+				     const char *prefix);
     -+
     -+// 0 = OK.
     -+int validate_refname(const char *name);
     -+
      +int validate_ref_record_addition(struct reftable_table tab,
      +				 struct reftable_ref_record *recs, size_t sz);
      +
     @@ reftable/refname_test.c (new)
      +	};
      +	int err;
      +	int i;
     -+	struct reftable_block_source source = { 0 };
     ++	struct reftable_block_source source = { NULL };
      +	struct reftable_reader *rd = NULL;
      +	struct reftable_table tab = { NULL };
      +	struct testcase cases[] = {
     @@ reftable/refname_test.c (new)
      +	return test_main(argc, argv);
      +}
      
     + ## reftable/reftable.c ##
     +@@ reftable/reftable.c: int reftable_table_seek_ref(struct reftable_table *tab,
     + 	struct reftable_ref_record ref = {
     + 		.refname = (char *)name,
     + 	};
     +-	struct reftable_record rec = { 0 };
     ++	struct reftable_record rec = { NULL };
     + 	reftable_record_from_ref(&rec, &ref);
     + 	return tab->ops->seek_record(tab->table_arg, it, &rec);
     + }
     +@@ reftable/reftable.c: void reftable_table_from_reader(struct reftable_table *tab,
     + int reftable_table_read_ref(struct reftable_table *tab, const char *name,
     + 			    struct reftable_ref_record *ref)
     + {
     +-	struct reftable_iterator it = { 0 };
     ++	struct reftable_iterator it = { NULL };
     + 	int err = reftable_table_seek_ref(tab, &it, name);
     + 	if (err)
     + 		goto done;
     +
       ## reftable/stack.c (new) ##
      @@
      +/*
     @@ reftable/stack.c (new)
      +#include "reftable.h"
      +#include "writer.h"
      +
     ++static int stack_try_add(struct reftable_stack *st,
     ++			 int (*write_table)(struct reftable_writer *wr,
     ++					    void *arg),
     ++			 void *arg);
     ++static int stack_write_compact(struct reftable_stack *st,
     ++			       struct reftable_writer *wr, int first, int last,
     ++			       struct reftable_log_expiry_config *config);
     ++static int stack_check_addition(struct reftable_stack *st,
     ++				const char *new_tab_name);
     ++static void reftable_addition_close(struct reftable_addition *add);
     ++static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
     ++					     int reuse_open);
     ++
      +int reftable_new_stack(struct reftable_stack **dest, const char *dir,
      +		       struct reftable_write_options config)
      +{
     @@ reftable/stack.c (new)
      +		}
      +
      +		if (rd == NULL) {
     -+			struct reftable_block_source src = { 0 };
     ++			struct reftable_block_source src = { NULL };
      +			struct strbuf table_path = STRBUF_INIT;
      +			strbuf_addstr(&table_path, st->reftable_dir);
      +			strbuf_addstr(&table_path, "/");
     @@ reftable/stack.c (new)
      +	return udiff;
      +}
      +
     -+int reftable_stack_reload_maybe_reuse(struct reftable_stack *st, int reuse_open)
     ++static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
     ++					     int reuse_open)
      +{
      +	struct timeval deadline = { 0 };
      +	int err = gettimeofday(&deadline, NULL);
     @@ reftable/stack.c (new)
      +	return err;
      +}
      +
     -+void reftable_addition_close(struct reftable_addition *add)
     ++static void reftable_addition_close(struct reftable_addition *add)
      +{
      +	int i = 0;
      +	struct strbuf nm = STRBUF_INIT;
     @@ reftable/stack.c (new)
      +	return err;
      +}
      +
     -+int stack_try_add(struct reftable_stack *st,
     -+		  int (*write_table)(struct reftable_writer *wr, void *arg),
     -+		  void *arg)
     ++static int stack_try_add(struct reftable_stack *st,
     ++			 int (*write_table)(struct reftable_writer *wr,
     ++					    void *arg),
     ++			 void *arg)
      +{
      +	struct reftable_addition add = REFTABLE_ADDITION_INIT;
      +	int err = reftable_stack_init_addition(&add, st);
     @@ reftable/stack.c (new)
      +	return err;
      +}
      +
     -+int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr,
     -+			int first, int last,
     -+			struct reftable_log_expiry_config *config)
     ++static int stack_write_compact(struct reftable_stack *st,
     ++			       struct reftable_writer *wr, int first, int last,
     ++			       struct reftable_log_expiry_config *config)
      +{
      +	int subtabs_len = last - first + 1;
      +	struct reftable_table *subtabs = reftable_calloc(
      +		sizeof(struct reftable_table) * (last - first + 1));
      +	struct reftable_merged_table *mt = NULL;
      +	int err = 0;
     -+	struct reftable_iterator it = { 0 };
     -+	struct reftable_ref_record ref = { 0 };
     -+	struct reftable_log_record log = { 0 };
     ++	struct reftable_iterator it = { NULL };
     ++	struct reftable_ref_record ref = { NULL };
     ++	struct reftable_log_record log = { NULL };
      +
      +	uint64_t entries = 0;
      +
     @@ reftable/stack.c (new)
      +int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
      +			    struct reftable_log_record *log)
      +{
     -+	struct reftable_iterator it = { 0 };
     ++	struct reftable_iterator it = { NULL };
      +	struct reftable_merged_table *mt = reftable_stack_merged_table(st);
      +	int err = reftable_merged_table_seek_log(mt, &it, refname);
      +	if (err)
     @@ reftable/stack.c (new)
      +	return err;
      +}
      +
     -+int stack_check_addition(struct reftable_stack *st, const char *new_tab_name)
     ++static int stack_check_addition(struct reftable_stack *st,
     ++				const char *new_tab_name)
      +{
      +	int err = 0;
     -+	struct reftable_block_source src = { 0 };
     ++	struct reftable_block_source src = { NULL };
      +	struct reftable_reader *rd = NULL;
      +	struct reftable_table tab = { NULL };
      +	struct reftable_ref_record *refs = NULL;
     @@ reftable/stack.c (new)
      +		goto done;
      +
      +	while (1) {
     -+		struct reftable_ref_record ref = { 0 };
     ++		struct reftable_ref_record ref = { NULL };
      +		err = reftable_iterator_next_ref(&it, &ref);
      +		if (err > 0) {
      +			break;
     @@ reftable/stack.h (new)
      +};
      +
      +int read_lines(const char *filename, char ***lines);
     -+int stack_try_add(struct reftable_stack *st,
     -+		  int (*write_table)(struct reftable_writer *wr, void *arg),
     -+		  void *arg);
     -+int stack_write_compact(struct reftable_stack *st, struct reftable_writer *wr,
     -+			int first, int last,
     -+			struct reftable_log_expiry_config *config);
     -+int fastlog2(uint64_t sz);
     -+int stack_check_addition(struct reftable_stack *st, const char *new_tab_name);
     -+void reftable_addition_close(struct reftable_addition *add);
     -+int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
     -+				      int reuse_open);
      +
      +struct segment {
      +	int start, end;
     @@ reftable/stack.h (new)
      +	uint64_t bytes;
      +};
      +
     ++int fastlog2(uint64_t sz);
      +struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n);
      +struct segment suggest_compaction_segment(uint64_t *sizes, int n);
      +
     @@ reftable/stack_test.c (new)
      +		.update_index = 1,
      +		.target = "master",
      +	};
     -+	struct reftable_ref_record dest = { 0 };
     ++	struct reftable_ref_record dest = { NULL };
      +
      +	assert(mkdtemp(dir));
      +
     @@ reftable/stack_test.c (new)
      +		.update_index = 1,
      +		.target = "master",
      +	};
     -+	struct reftable_ref_record dest = { 0 };
     ++	struct reftable_ref_record dest = { NULL };
      +
      +	assert(mkdtemp(dir));
      +
     @@ reftable/stack_test.c (new)
      +	};
      +	struct reftable_stack *st = NULL;
      +	char dir[256] = "/tmp/stack_test.XXXXXX";
     -+	struct reftable_ref_record refs[2] = { { 0 } };
     -+	struct reftable_log_record logs[2] = { { 0 } };
     ++	struct reftable_ref_record refs[2] = { { NULL } };
     ++	struct reftable_log_record logs[2] = { { NULL } };
      +	int N = ARRAY_SIZE(refs);
      +
      +	assert(mkdtemp(dir));
     @@ reftable/stack_test.c (new)
      +	assert_err(err);
      +
      +	for (i = 0; i < N; i++) {
     -+		struct reftable_ref_record dest = { 0 };
     ++		struct reftable_ref_record dest = { NULL };
     ++
      +		int err = reftable_stack_read_ref(st, refs[i].refname, &dest);
      +		assert_err(err);
      +		assert(reftable_ref_record_equal(&dest, refs + i, SHA1_SIZE));
     @@ reftable/stack_test.c (new)
      +	}
      +
      +	for (i = 0; i < N; i++) {
     -+		struct reftable_log_record dest = { 0 };
     ++		struct reftable_log_record dest = { NULL };
      +		int err = reftable_stack_read_log(st, refs[i].refname, &dest);
      +		assert_err(err);
      +		assert(reftable_log_record_equal(&dest, logs + i, SHA1_SIZE));
     @@ reftable/stack_test.c (new)
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
      +	int err;
     -+	struct reftable_ref_record refs[2] = { { 0 } };
     -+	struct reftable_log_record logs[2] = { { 0 } };
     ++	struct reftable_ref_record refs[2] = { { NULL } };
     ++	struct reftable_log_record logs[2] = { { NULL } };
      +	int N = ARRAY_SIZE(refs);
     -+	struct reftable_ref_record dest = { 0 };
     -+	struct reftable_log_record log_dest = { 0 };
     ++	struct reftable_ref_record dest = { NULL };
     ++	struct reftable_log_record log_dest = { NULL };
      +
      +	assert(mkdtemp(dir));
      +
     @@ reftable/stack_test.c (new)
      +	struct reftable_stack *st32 = NULL;
      +	struct reftable_write_options cfg_default = { 0 };
      +	struct reftable_stack *st_default = NULL;
     -+	struct reftable_ref_record dest = { 0 };
     ++	struct reftable_ref_record dest = { NULL };
      +
      +	assert(mkdtemp(dir));
      +	err = reftable_new_stack(&st, dir, cfg);
     @@ reftable/stack_test.c (new)
      +	char dir[256] = "/tmp/stack.test_reflog_expire.XXXXXX";
      +	struct reftable_write_options cfg = { 0 };
      +	struct reftable_stack *st = NULL;
     -+	struct reftable_log_record logs[20] = { { 0 } };
     ++	struct reftable_log_record logs[20] = { { NULL } };
      +	int N = ARRAY_SIZE(logs) - 1;
      +	int i = 0;
      +	int err;
      +	struct reftable_log_expiry_config expiry = {
      +		.time = 10,
      +	};
     -+	struct reftable_log_record log = { 0 };
     ++	struct reftable_log_record log = { NULL };
      +
      +	assert(mkdtemp(dir));
      +

13: b8729fee9e ! 13: c535f838d6 reftable: "test-tool dump-reftable" command.
@@ Makefile: REFTABLE_OBJS += reftable/writer.o
REFTABLE_TEST_OBJS += reftable/refname_test.o REFTABLE_TEST_OBJS += reftable/reftable_test.o

+ ## reftable/iter.c ##
+@@ reftable/iter.c: void reftable_iterator_destroy(struct reftable_iterator *it)
+ int reftable_iterator_next_ref(struct reftable_iterator *it,
+ struct reftable_ref_record *ref)
+ {
+- struct reftable_record rec = { 0 };
++ struct reftable_record rec = { NULL };
+ reftable_record_from_ref(&rec, ref);
+ return iterator_next(it, &rec);
+ }
+@@ reftable/iter.c: int reftable_iterator_next_ref(struct reftable_iterator *it,
+ int reftable_iterator_next_log(struct reftable_iterator *it,
+ struct reftable_log_record *log)
+ {
+- struct reftable_record rec = { 0 };
++ struct reftable_record rec = { NULL };
+ reftable_record_from_log(&rec, log);
+ return iterator_next(it, &rec);
+ }
+@@ reftable/iter.c: static int filtering_ref_iterator_next(void *iter_arg,
+ }
+
+ if (fri->double_check) {
+- struct reftable_iterator it = { 0 };
++ struct reftable_iterator it = { NULL };
+
+ err = reftable_table_seek_ref(&fri->tab, &it,
+ ref->refname);
+
+ ## reftable/reader.c ##
+@@ reftable/reader.c: static int parse_footer(struct reftable_reader *r, uint8_t *footer,
+ int init_reader(struct reftable_reader *r, struct reftable_block_source *source,
+ const char *name)
+ {
+- struct reftable_block footer = { 0 };
+- struct reftable_block header = { 0 };
++ struct reftable_block footer = { NULL };
++ struct reftable_block header = { NULL };
+ int err = 0;
+
+ memset(r, 0, sizeof(struct reftable_reader));
+@@ reftable/reader.c: int reader_init_block_reader(struct reftable_reader *r, struct block_reader *br,
+ {
+ int32_t guess_block_size = r->block_size ? r->block_size :
+ DEFAULT_BLOCK_SIZE;
+- struct reftable_block block = { 0 };
++ struct reftable_block block = { NULL };
+ uint8_t block_typ = 0;
+ int err = 0;
+ uint32_t header_off = next_off ? 0 : header_size(r->version);
+@@ reftable/reader.c: static int reader_seek_indexed(struct reftable_reader *r,
+ struct reftable_record *rec)
+ {
+ struct reftable_index_record want_index = { .last_key = STRBUF_INIT };
+- struct reftable_record want_index_rec = { 0 };
++ struct reftable_record want_index_rec = { NULL };
+ struct reftable_index_record index_result = { .last_key = STRBUF_INIT };
+- struct reftable_record index_result_rec = { 0 };
++ struct reftable_record index_result_rec = { NULL };
+ struct table_iter index_iter = TABLE_ITER_INIT;
+ struct table_iter next = TABLE_ITER_INIT;
+ int err = 0;
+@@ reftable/reader.c: int reftable_reader_seek_ref(struct reftable_reader *r,
+ struct reftable_ref_record ref = {
+ .refname = (char *)name,
+ };
+- struct reftable_record rec = { 0 };
++ struct reftable_record rec = { NULL };
+ reftable_record_from_ref(&rec, &ref);
+ return reader_seek(r, it, &rec);
+ }
+@@ reftable/reader.c: int reftable_reader_seek_log_at(struct reftable_reader *r,
+ .refname = (char *)name,
+ .update_index = update_index,
+ };
+- struct reftable_record rec = { 0 };
++ struct reftable_record rec = { NULL };
+ reftable_record_from_log(&rec, &log);
+ return reader_seek(r, it, &rec);
+ }
+@@ reftable/reader.c: static int reftable_reader_refs_for_indexed(struct reftable_reader *r,
+ .hash_prefix = oid,
+ .hash_prefix_len = r->object_id_len,
+ };
+- struct reftable_record want_rec = { 0 };
+- struct reftable_iterator oit = { 0 };
+- struct reftable_obj_record got = { 0 };
+- struct reftable_record got_rec = { 0 };
++ struct reftable_record want_rec = { NULL };
++ struct reftable_iterator oit = { NULL };
++ struct reftable_obj_record got = { NULL };
++ struct reftable_record got_rec = { NULL };
+ int err = 0;
+ struct indexed_table_ref_iter *itr = NULL;
+
+
## t/helper/test-reftable.c ##
@@ t/helper/test-reftable.c: int cmd__reftable(int argc, const char **argv)
tree_test_main(argc, argv);

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 0000000000..402e0f9356
@@ -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

Hi,

This line presumably doesn't want to be part of permanent history. :)

Instead, it can say a little about rationale. For example, does this make the code easier for other projects like libgit2 to share?

Should there be a reftable/README as well?

[...]

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

---
 reftable/reftable.h | 585 ++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 585 insertions(+)
 create mode 100644 reftable/reftable.h

new file mode 100644
index 0000000000..5f8ebf5540
@@ -0,0 +1,585 @@
+/*
+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 <stdint.h>
+#include <stddef.h>
+
+void reftable_set_alloc(void *(*malloc)(size_t),
+			void *(*realloc)(void *, size_t), void (*free)(void *));
+
+/****************************************************************
+ 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. */
+};
+
+/* 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 */
+void reftable_ref_record_print(struct reftable_ref_record *ref,
+			       uint32_t hash_id);
+
+/* frees and nulls all pointer values. */
+void reftable_ref_record_clear(struct reftable_ref_record *ref);
+
+/* returns whether two reftable_ref_records are the same */
+int reftable_ref_record_equal(struct reftable_ref_record *a,
+			      struct reftable_ref_record *b, int hash_size);
+
+/* reftable_log_record holds a reflog entry */
+struct reftable_log_record {
+	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;
+};
+
+/* returns whether 'ref' represents the deletion of a log record. */
+int reftable_log_record_is_deletion(const struct reftable_log_record *log);
+
+/* frees and nulls all pointer values. */
+void reftable_log_record_clear(struct reftable_log_record *log);
+
+/* returns whether two records are equal. */
+int reftable_log_record_equal(struct reftable_log_record *a,
+			      struct reftable_log_record *b, int hash_size);
+
+/* dumps a reftable_log_record on stdout, for debugging/testing. */
+void reftable_log_record_print(struct reftable_log_record *log,
+			       uint32_t hash_id);
+
+/****************************************************************
+ Error handling
+
+ Error are signaled with negative integer return values. 0 means success.
+ ****************************************************************/
+
+/* different types of errors */
+enum reftable_error {
+	/* Unexpected file system behavior */
+	REFTABLE_IO_ERROR = -2,
+
+	/* 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.
+	*/
+	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.
+	*/
+	REFTABLE_API_ERROR = -6,
+
+	/* Decompression error */
+	REFTABLE_ZLIB_ERROR = -7,
+
+	/* Wrote a table without blocks. */
+	REFTABLE_EMPTY_TABLE_ERROR = -8,
+
+	/* Dir/file conflict. */
+	REFTABLE_NAME_CONFLICT = -9,
+
+	/* Illegal ref name. */
+	REFTABLE_REFNAME_ERROR = -10,
+};
+
+/* convert the numeric error code to a string. The string should not be
+ * deallocated. */
+const char *reftable_error_str(int err);
+
+/*
+ * Convert the numeric error code to an equivalent errno code.
+ */
+int reftable_error_to_errno(int err);
+
+/****************************************************************
+ Writing
+
+ Writing single reftables
+ ****************************************************************/
+
+/* reftable_write_options sets options for writing a single reftable. */
+struct reftable_write_options {
+	/* boolean: do not pad out blocks to block size. */
+	int unpadded;
+
+	/* the blocksize. Should be less than 2^24. */
+	uint32_t block_size;
+
+	/* boolean: do not generate a SHA1 => ref index. */
+	int skip_index_objects;
+
+	/* how often to write complete keys in each block. */
+	int restart_interval;
+
+	/* 4-byte identifier ("sha1", "s256") of the hash.
+	 * Defaults to SHA1 if unset
+	 */
+	uint32_t hash_id;
+
+	/* boolean: do not check ref names for validity or dir/file conflicts.
+	 */
+	int skip_name_check;
+
+	/* boolean: copy log messages exactly. If unset, check that the message
+	 *   is a single line, and add '\n' if missing.
+	 */
+	int exact_log_message;
+};
+
+/* reftable_block_stats holds statistics for a single block type */
+struct reftable_block_stats {
+	/* total number of entries written */
+	int entries;
+	/* total number of key restarts */
+	int restarts;
+	/* total number of blocks */
+	int blocks;
+	/* total number of index blocks */
+	int index_blocks;
+	/* depth of the index */
+	int max_index_level;
+
+	/* offset of the first block for this type */
+	uint64_t offset;
+	/* offset of the top level index block for this type, or 0 if not
+	 * present */
+	uint64_t index_offset;
+};
+
+/* stats holds overall statistics for a single reftable */
+struct reftable_stats {
+	/* total number of blocks written. */
+	int blocks;
+	/* stats for ref data */
+	struct reftable_block_stats ref_stats;
+	/* stats for the SHA1 to ref map. */
+	struct reftable_block_stats obj_stats;
+	/* stats for index blocks */
+	struct reftable_block_stats idx_stats;
+	/* stats for log blocks */
+	struct reftable_block_stats log_stats;
+
+	/* disambiguation length of shortened object IDs. */
+	int object_id_len;
+};
+
+/* reftable_new_writer creates a new writer */
+struct reftable_writer *
+reftable_new_writer(int (*writer_func)(void *, const void *, size_t),
+		    void *writer_arg, struct reftable_write_options *opts);
+
+/* write to a file descriptor. fdp should be an int* pointing to the fd. */
+int reftable_fd_write(void *fdp, const void *data, size_t size);
+
+/* Set the range of update indices for the records we will add.  When
+   writing a table into a stack, the min should be at least
+   reftable_stack_next_update_index(), or REFTABLE_API_ERROR is returned.
+
+   For transactional updates, typically min==max. When converting an existing
+   ref database into a single reftable, this would be a range of update-index
+   timestamps.
+ */
+void reftable_writer_set_limits(struct reftable_writer *w, uint64_t min,
+				uint64_t max);
+
+/* adds a reftable_ref_record. Must be called in ascending
+   order. The update_index must be within the limits set by
+   reftable_writer_set_limits(), or REFTABLE_API_ERROR is returned.
+
+   It is an error to write a ref record after a log record.
+ */
+int reftable_writer_add_ref(struct reftable_writer *w,
+			    struct reftable_ref_record *ref);
+
+/* Convenience function to add multiple refs. Will sort the refs by
+   name before adding. */
+int reftable_writer_add_refs(struct reftable_writer *w,
+			     struct reftable_ref_record *refs, int n);
+
+/* adds a reftable_log_record. Must be called in ascending order (with more
+   recent log entries first.)
+ */
+int reftable_writer_add_log(struct reftable_writer *w,
+			    struct reftable_log_record *log);
+
+/* Convenience function to add multiple logs. Will sort the records by
+   key before adding. */
+int reftable_writer_add_logs(struct reftable_writer *w,
+			     struct reftable_log_record *logs, int n);
+
+/* reftable_writer_close finalizes the reftable. The writer is retained so
+ * statistics can be inspected. */
+int reftable_writer_close(struct reftable_writer *w);
+
+/* writer_stats returns the statistics on the reftable being written.
+
+   This struct becomes invalid when the writer is freed.
+ */
+const struct reftable_stats *writer_stats(struct reftable_writer *w);
+
+/* reftable_writer_free deallocates memory for the writer */
+void reftable_writer_free(struct reftable_writer *w);
+
+/****************************************************************
+ * ITERATING
+ ****************************************************************/
+
+/* iterator is the generic interface for walking over data stored in a
+   reftable. It is generally passed around by value.
+*/
+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);
+
+/****************************************************************
+ 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.
+ ****************************************************************/
+
+/* block_source is a generic wrapper for a seekable readable file.
+   It is generally passed around by value.
+ */
+struct reftable_block_source {
+	struct reftable_block_source_vtable *ops;
+	void *arg;
+};
+
+/* a contiguous segment of bytes. It keeps track of its generating block_source
+   so it can return itself into the pool.
+*/
+struct reftable_block {
+	uint8_t *data;
+	int len;
+	struct reftable_block_source source;
+};
+
+/* block_source_vtable are the operations that make up block_source */
+struct reftable_block_source_vtable {
+	/* returns the size of a block source */
+	uint64_t (*size)(void *source);
+
+	/* reads a segment from the block source. It is an error to read
+	   beyond the end of the block */
+	int (*read_block)(void *source, struct reftable_block *dest,
+			  uint64_t off, uint32_t size);
+	/* mark the block as read; may return the data back to malloc */
+	void (*return_block)(void *source, struct reftable_block *blockp);
+
+	/* release all resources associated with the block source */
+	void (*close)(void *source);
+};
+
+/* opens a file on the file system as a block_source */
+int reftable_block_source_from_file(struct reftable_block_source *block_src,
+				    const char *name);
+
+/* The reader struct is a handle to an open reftable file. */
+struct reftable_reader;
+
+/* reftable_new_reader opens a reftable for reading. If successful, returns 0
+ * code and sets pp. The name is used for creating a stack. Typically, it is the
+ * basename of the file. The block source `src` is owned by the reader, and is
+ * closed on calling reftable_reader_destroy().
+ */
+int reftable_new_reader(struct reftable_reader **pp,
+			struct reftable_block_source *src, const char *name);
+
+/* reftable_reader_seek_ref returns an iterator where 'name' would be inserted
+   in the table.  To seek to the start of the table, use name = "".
+
+   example:
+
+   struct reftable_reader *r = NULL;
+   int err = reftable_new_reader(&r, &src, "filename");
+   if (err < 0) { ... }
+   struct reftable_iterator it  = {0};
+   err = reftable_reader_seek_ref(r, &it, "refs/heads/master");
+   if (err < 0) { ... }
+   struct reftable_ref_record ref  = {0};
+   while (1) {
+     err = reftable_iterator_next_ref(&it, &ref);
+     if (err > 0) {
+       break;
+     }
+     if (err < 0) {
+       ..error handling..
+     }
+     ..found..
+   }
+   reftable_iterator_destroy(&it);
+   reftable_ref_record_clear(&ref);
+ */
+int reftable_reader_seek_ref(struct reftable_reader *r,
+			     struct reftable_iterator *it, const char *name);
+
+/* returns the hash ID used in this table. */
+uint32_t reftable_reader_hash_id(struct reftable_reader *r);
+
+/* seek to logs for the given name, older than update_index. To seek to the
+   start of the table, use name = "".
+ */
+int reftable_reader_seek_log_at(struct reftable_reader *r,
+				struct reftable_iterator *it, const char *name,
+				uint64_t update_index);
+
+/* seek to newest log entry for given name. */
+int reftable_reader_seek_log(struct reftable_reader *r,
+			     struct reftable_iterator *it, const char *name);
+
+/* closes and deallocates a reader. */
+void reftable_reader_free(struct reftable_reader *);
+
+/* return an iterator for the refs pointing to `oid`. */
+int reftable_reader_refs_for(struct reftable_reader *r,
+			     struct reftable_iterator *it, uint8_t *oid);
+
+/* return the max_update_index for a table */
+uint64_t reftable_reader_max_update_index(struct reftable_reader *r);
+
+/* return the min_update_index for a table */
+uint64_t reftable_reader_min_update_index(struct reftable_reader *r);
+
+/****************************************************************
+ 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.
+ ****************************************************************/
+
+/* A merged table is implements seeking/iterating over a stack of tables. */
+struct reftable_merged_table;
+
+/* A generic reftable; see below. */
+struct reftable_table;
+
+/* reftable_new_merged_table creates a new merged table. It takes ownership of
+   the stack array.
+*/
+int reftable_new_merged_table(struct reftable_merged_table **dest,
+			      struct reftable_table *stack, int n,
+			      uint32_t hash_id);
+
+/* returns an iterator positioned just before 'name' */
+int reftable_merged_table_seek_ref(struct reftable_merged_table *mt,
+				   struct reftable_iterator *it,
+				   const char *name);
+
+/* returns an iterator for log entry, at given update_index */
+int reftable_merged_table_seek_log_at(struct reftable_merged_table *mt,
+				      struct reftable_iterator *it,
+				      const char *name, uint64_t update_index);
+
+/* like reftable_merged_table_seek_log_at but look for the newest entry. */
+int reftable_merged_table_seek_log(struct reftable_merged_table *mt,
+				   struct reftable_iterator *it,
+				   const char *name);
+
+/* returns the max update_index covered by this merged table. */
+uint64_t
+reftable_merged_table_max_update_index(struct reftable_merged_table *mt);
+
+/* returns the min update_index covered by this merged table. */
+uint64_t
+reftable_merged_table_min_update_index(struct reftable_merged_table *mt);
+
+/* releases memory for the merged_table */
+void reftable_merged_table_free(struct reftable_merged_table *m);
+
+/* return the hash ID of the merged table. */
+uint32_t reftable_merged_table_hash_id(struct reftable_merged_table *m);
+
+/****************************************************************
+ Generic tables
+
+ A unified API for reading tables, either merged tables, or single readers.
+ ****************************************************************/
+
+struct reftable_table {
+	struct reftable_table_vtable *ops;
+	void *table_arg;
+};
+
+int reftable_table_seek_ref(struct reftable_table *tab,
+			    struct reftable_iterator *it, const char *name);
+
+void reftable_table_from_reader(struct reftable_table *tab,
+				struct reftable_reader *reader);
+
+/* returns the hash ID from a generic reftable_table */
+uint32_t reftable_table_hash_id(struct reftable_table *tab);
+
+/* create a generic table from reftable_merged_table */
+void reftable_table_from_merged_table(struct reftable_table *tab,
+				      struct reftable_merged_table *table);
+
+/* returns the max update_index covered by this table. */
+uint64_t reftable_table_max_update_index(struct reftable_table *tab);
+
+/* returns the min update_index covered by this table. */
+uint64_t reftable_table_min_update_index(struct reftable_table *tab);
+
+/* convenience function to read a single ref. Returns < 0 for error, 0
+   for success, and 1 if ref not found. */
+int reftable_table_read_ref(struct reftable_table *tab, const char *name,
+			    struct reftable_ref_record *ref);
+
+/****************************************************************
+ Mutable ref database
+
+ The stack presents an interface to a mutable sequence of reftables.
+ ****************************************************************/
+
+/* a stack is a stack of reftables, which can be mutated by pushing a table to
+ * the top of the stack */
+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.
+*/
+int reftable_new_stack(struct reftable_stack **dest, const char *dir,
+		       struct reftable_write_options config);
+
+/* returns the update_index at which a next table should be written. */
+uint64_t reftable_stack_next_update_index(struct reftable_stack *st);
+
+/* holds a transaction to add tables at the top of a stack. */
+struct reftable_addition;
+
+/*
+  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);
+
+/* Adds a reftable to transaction. */
+int reftable_addition_add(struct reftable_addition *add,
+			  int (*write_table)(struct reftable_writer *wr,
+					     void *arg),
+			  void *arg);
+
+/* Commits the transaction, releasing the lock. */
+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. */
+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. */
+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.
+*/
+struct reftable_merged_table *
+reftable_stack_merged_table(struct reftable_stack *st);
+
+/* frees all resources associated with the stack. */
+void reftable_stack_destroy(struct reftable_stack *st);
+
+/* Reloads the stack if necessary. This is very cheap to run if the stack was up
+ * to date */
+int reftable_stack_reload(struct reftable_stack *st);
+
+/* Policy for expiring reflog entries. */
+struct reftable_log_expiry_config {
+	/* Drop entries older than this timestamp */
+	uint64_t time;
+
+	/* Drop older entries */
+	uint64_t min_update_index;
+};
+
+/* compacts all reftables into a giant table. Expire reflog entries if config is
+ * non-NULL */
+int reftable_stack_compact_all(struct reftable_stack *st,
+			       struct reftable_log_expiry_config *config);
+
+/* 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. */
+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. */
+int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
+			    struct reftable_log_record *log);
+
+/* statistics on past compactions. */
+struct reftable_compaction_stats {
+	uint64_t bytes; /* total number of bytes written */
+	uint64_t entries_written; /* total number of entries written, including
+				     failures. */
+	int attempts; /* how often we tried to compact */
+	int failures; /* failures happen on concurrent updates */
+};
+
+/* return statistics for compaction up till now. */
+struct reftable_compaction_stats *
+reftable_stack_compaction_stats(struct reftable_stack *st);
+
+#endif

gitgitgadget

Hi,

Adding a header in a separate patch from the implementation doesn't match the usual practice. Can we add declarations in the same patch as the functions being declared instead?

We could still introduce the header early in its own patch if we want, but it would be a skeleton of a header that gets filled out by later patches.

[...]

[...]

	/* logical timestamp at which this value was written */
	uint64_t update_index;

Nice as well.

[...]

	uint64_t reftable_merged_table_max_update_index(
					struct reftable_merged_table *mt);

Are there callers/helpers that don't know whether they want one or the other?

[...]

Nice.

[...]

To poke a little deeper into what I think Jonathan is trying to say:

When we reviewed this for review club, the general feeling was that A) this commit structure is still pretty difficult to review, and B) we want to make sure you aren't spending a ton of time reorganizing the code only to find that people still don't like the structure (as may have happened with the current iteration).

One point I think Jonathan is making is that each commit should stand
alone: compile, be tested, and do something succinct. Another point (or maybe the same point from a different angle) is that a series of commits should tell a progressive story. That is, something like

add infrastructure to support reftable library
reftable: read/write blocks
reftable: write files
reftable: read files
reftable: generate binary tree from file
...

is much more compelling (and easier to review) than

reftable: LICENSE
reftable: headers
reftable: tests
...

Towards the latter end of your series it seems like you started to take that approach; but some commits, like this one (reftable: define the public API) are not quite so. That is, this commit is hard to review without the context of the rest of the series: I read it, I say, "well WHY do we need these functions?", and then I cannot continue my review of this patch until I've completed my review of the rest of the series.

Of course, taking a completed project - like your initial reftable submission - and then chopping it up into a cute story of commits is a pain in the ***. Doing it twice - or more - is just aggravating. So I wonder whether we can bikeshed what story would look nice before you even pick up your 'git rebase -i'? Doing that bikeshedding here on list means that we also have a chance for someone to interrupt and say, "no, that organization doesn't make sense" - or even for someone to say "Emily, there is no need to reorganize these commits, go sit down" ;)

Or maybe what I said runs contrary to what Jonathan was actually saying. Please, correct me :)

- Emily

It would be great if you could bikeshed about this while I'm on holiday :)

That said, I think it's worthwhile to first look at the commit that uses the library to implement a ref backend, because that will show better how the reftable library fits with the way that Git likes to consume its data.

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

Looks like this didn't happen. I went with Jonathan's suggestion, and chopped the public API header in smaller bits. PTAL.

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

We could, but it would considerably complicate work on this patch series, as the commit boundary then doesn't fall on file boundaries anymore. Would you be open to having multiple headers for the public interface? eg. reftable-record.h, reftable-reader.h etc. ?

Since this was written as a standalone library, it's up to the caller to decide what should be done. It also simplifies testing: you can verify that incorrect API usage returns a certain error code, but a BUG() that prints an error or crashes the program is much harder to verify.

yes.

The read_raw_ref method in the ref backend API uses errno values as out-of-band communication mechanism.

you get an REFTABLE_API_ERROR.

you pass in block_source->arg. Should struct implementations of polymorphic types carry a pointer to their own vtable instead?

Log blocks are compressed, so the caller doesn't know the correct size to supply. By letting the block source handle the management, we can swap out the block read from the file for a block managed by malloc on decompressing a log block.

The hash identifier, eg. "sha1" for SHA1 and "s256" for SHA-256.

The setup with per-worktree refs means that there are two reftable stacks in a .git repo. In order to iterate over the entire ref space, you have to merge two merged tables, but the stack itslef merges a set of simple reftables.

No. You'd usually add only one table, but at the same time, it seemed kind of arbitrary to allow adding only one table. FWIW, I added this because libgit2 wants to be able to lock a ref database: creating the reftable_addition institutes the lock.

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'd be more than open to it: I think that would make for a clearer API.

For example, a caller like refs.c wouldn't have any need to use reftable-block.h because that's a lower-level detail that operates behind the scenes when operating on a stack of reftables. So I think this would be a good step toward addressing the feedback Jonathan gave about the set of functions exposed by the API being overwhelming.

I'm not strongly opinionated about this, but just a quick note: this implies that the library would need to make sure it is producing a valid state in error cases.

Does the API documentation describe what state a handle is in after an error --- e.g., what operations are permitted after that?

Could we change that? It sounds error-prone.

[...]

(To be clear, with all of these questions, I am asking not only for my own curiosity but so that the documentation, naming, etc can be cleared up to help the next person who wonders the same thing.)

[...]

I think a pointer to block_source would make it more self-explanatory, yes.

(Aside: this is a difference between how Go and e.g. Java and C++ implement polymorphism. In Go, an interface object contains a vtable and a pointer to the object. In Java and C++, the object contains a vptr.)

Hm, my naive assumption would have been that we'd use different buffers for the compressed and uncompressed data.

I see. That's subtle, so it seems worth documenting for the next person reading this documentation and wondering why.

Thanks,
Jonathan

Done.

This is what it already does. I tried to clarify this in some places.

API_ERROR should not result in state changes.

I moved it into refs/reftable-backend.c; I'd rather not also have to clean up the files backend as part of this work, though.

This has a number of downsides, though. It means I have to introduce separate structs strbuf_blocksource and file_blocksource, along with functions to create and deallocate them, so it makes the whole thing more unwieldy to use.

Maybe you can comment on how to solve this differently when we get to the implementation of block reading/writing in the commit series.