[PATCH 01/10] ivec: introduce the C side of ivec

["Ezekiel Newren via GitGitGadget" <gitgitgadget@gmail.com>]

From: Ezekiel Newren <ezekielnewren@gmail.com>

Trying to use Rust's Vec in C, or git's ALLOC_GROW() macros (via
wrapper functions) in Rust is painful because:

  * C doesn't define its own vector type, and even though Rust does
    have Vec its painful to use on the C side (more on that below).
    However its still not viable to use Rust's Vec type because Git
    needs to be able to compile without Rust. So ivec was created
    expressley to be interoperable between C and Rust without needing
    Rust.
  * C doing vector things the Rust way would require wrapper functions,
    and Rust doing vector things the C way would require wrapper
    functions, so ivec was created to ensure a consistent contract
    between the 2 languages for how to manipulate a vector.
  * Currently, Rust defines its own 'Vec' type that is generic, but its
    memory allocator and struct layout weren't designed for
    interoperability with C (or any language for that matter), meaning
    that the C side cannot push to or expand a 'Vec' without defining
    wrapper functions in Rust that C can call. Without special care,
    the two languages might use different allocators (malloc/free on
    the C side, and possibly something else in Rust), which would make
    it difficult for a function in one language to free elements
    allocated by a call from a function in the other language.
  * Similarly, git defines ALLOC_GROW() and related macros in
    git-compat-util.h. While we could add functions allowing Rust to
    invoke something similar to those macros, passing three variables
    (pointer, length, allocated_size) instead of a single variable
    (vector) across the language boundary requires more cognitive
    overhead for readers to keep track of and makes it easier to make
    mistakes. Further, for low-level components that we want to
    eventually convert to pure Rust, such triplets would feel very out
    of place.

To address these issue, introduce a new type, ivec -- short for
interoperable vector. (We refer to it as 'ivec' generally, though on
the Rust side the struct is called IVec to match Rust style.)  This new
type is specifically designed for FFI purposes, so that both languages
handle the vector in the same way, though it could be used on either
side independently. This type is designed such that it can easily be
replaced by a Rust 'Vec' once interoperability is no longer a concern.

One particular item to note is that Git's macros to handle vec
operations infer the amount that a vec needs to grow from the size of
a pointer, but that makes it somewhat specific to the macros used in C.
To avoid defining every ivec function as a macro I opted to also
include an element_size field that allows concrete functions like
push() to know how much to grow the memory. This element_size also
helps in verifying that the ivec is correct when passing from C to
Rust.

Signed-off-by: Ezekiel Newren <ezekielnewren@gmail.com>
---
 Makefile      |   1 +
 compat/ivec.c | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++
 compat/ivec.h |  52 +++++++++++++++++++++++
 meson.build   |   1 +
 4 files changed, 167 insertions(+)
 create mode 100644 compat/ivec.c
 create mode 100644 compat/ivec.h

diff --git a/Makefile b/Makefile
index 89d8d73ec0..f923b307d6 100644
--- a/Makefile
+++ b/Makefile
@@ -1107,6 +1107,7 @@ LIB_OBJS += commit-reach.o
 LIB_OBJS += commit.o
 LIB_OBJS += common-exit.o
 LIB_OBJS += common-init.o
+LIB_OBJS += compat/ivec.o
 LIB_OBJS += compat/nonblock.o
 LIB_OBJS += compat/obstack.o
 LIB_OBJS += compat/open.o
diff --git a/compat/ivec.c b/compat/ivec.c
new file mode 100644
index 0000000000..0a777e78dc
--- /dev/null
+++ b/compat/ivec.c
@@ -0,0 +1,113 @@
+#include "ivec.h"
+
+struct IVec_c_void {
+	void *ptr;
+	size_t length;
+	size_t capacity;
+	size_t element_size;
+};
+
+static void _set_capacity(void *self_, size_t new_capacity)
+{
+	struct IVec_c_void *self = self_;
+
+	if (new_capacity == self->capacity) {
+		return;
+	}
+	if (new_capacity == 0) {
+		free(self->ptr);
+		self->ptr = NULL;
+	} else {
+		self->ptr = realloc(self->ptr, new_capacity * self->element_size);
+	}
+	self->capacity = new_capacity;
+}
+
+
+void ivec_init(void *self_, size_t element_size)
+{
+	struct IVec_c_void *self = self_;
+
+	self->ptr = NULL;
+	self->length = 0;
+	self->capacity = 0;
+	self->element_size = element_size;
+}
+
+void ivec_zero(void *self_, size_t capacity)
+{
+	struct IVec_c_void *self = self_;
+
+	self->ptr = calloc(capacity, self->element_size);
+	self->length = capacity;
+	self->capacity = capacity;
+	// DO NOT MODIFY element_size!!!
+}
+
+void ivec_reserve_exact(void *self_, size_t additional)
+{
+	struct IVec_c_void *self = self_;
+
+	_set_capacity(self, self->capacity + additional);
+}
+
+void ivec_reserve(void *self_, size_t additional)
+{
+	struct IVec_c_void *self = self_;
+
+	size_t growby = 128;
+	if (self->capacity > growby)
+		growby = self->capacity;
+	if (additional > growby)
+		growby = additional;
+
+	_set_capacity(self, self->capacity + growby);
+}
+
+void ivec_shrink_to_fit(void *self_)
+{
+	struct IVec_c_void *self = self_;
+
+	_set_capacity(self, self->length);
+}
+
+void ivec_push(void *self_, const void *value)
+{
+	struct IVec_c_void *self = self_;
+	void *dst = NULL;
+
+	if (self->length == self->capacity)
+		ivec_reserve(self, 1);
+
+	dst = (uint8_t*)self->ptr + self->length * self->element_size;
+	memcpy(dst, value, self->element_size);
+	self->length++;
+}
+
+void ivec_free(void *self_)
+{
+	struct IVec_c_void *self = self_;
+
+	free(self->ptr);
+	self->ptr = NULL;
+	self->length = 0;
+	self->capacity = 0;
+	// DO NOT MODIFY element_size!!!
+}
+
+void ivec_move(void *src_, void *dst_)
+{
+	struct IVec_c_void *src = src_;
+	struct IVec_c_void *dst = dst_;
+
+	ivec_free(dst);
+	dst->ptr = src->ptr;
+	dst->length = src->length;
+	dst->capacity = src->capacity;
+	// DO NOT MODIFY element_size!!!
+
+	src->ptr = NULL;
+	src->length = 0;
+	src->capacity = 0;
+	// DO NOT MODIFY element_size!!!
+}
diff --git a/compat/ivec.h b/compat/ivec.h
new file mode 100644
index 0000000000..654a05c506
--- /dev/null
+++ b/compat/ivec.h
@@ -0,0 +1,52 @@
+#ifndef IVEC_H
+#define IVEC_H
+
+#include <git-compat-util.h>
+
+#define IVEC_INIT(variable) ivec_init(&(variable), sizeof(*(variable).ptr))
+
+#ifndef CBINDGEN
+#define DEFINE_IVEC_TYPE(type, suffix) \
+struct IVec_##suffix { \
+	type* ptr; \
+	size_t length; \
+	size_t capacity; \
+	size_t element_size; \
+}
+
+DEFINE_IVEC_TYPE(bool, bool);
+
+DEFINE_IVEC_TYPE(uint8_t, u8);
+DEFINE_IVEC_TYPE(uint16_t, u16);
+DEFINE_IVEC_TYPE(uint32_t, u32);
+DEFINE_IVEC_TYPE(uint64_t, u64);
+
+DEFINE_IVEC_TYPE(int8_t, i8);
+DEFINE_IVEC_TYPE(int16_t, i16);
+DEFINE_IVEC_TYPE(int32_t, i32);
+DEFINE_IVEC_TYPE(int64_t, i64);
+
+DEFINE_IVEC_TYPE(float, f32);
+DEFINE_IVEC_TYPE(double, f64);
+
+DEFINE_IVEC_TYPE(size_t, usize);
+DEFINE_IVEC_TYPE(ssize_t, isize);
+#endif
+
+void ivec_init(void *self_, size_t element_size);
+
+void ivec_zero(void *self_, size_t capacity);
+
+void ivec_reserve_exact(void *self_, size_t additional);
+
+void ivec_reserve(void *self_, size_t additional);
+
+void ivec_shrink_to_fit(void *self_);
+
+void ivec_push(void *self_, const void *value);
+
+void ivec_free(void *self_);
+
+void ivec_move(void *src, void *dst);
+
+#endif /* IVEC_H */
diff --git a/meson.build b/meson.build
index dd52efd1c8..42ac0c8c42 100644
--- a/meson.build
+++ b/meson.build
@@ -302,6 +302,7 @@ libgit_sources = [
   'commit.c',
   'common-exit.c',
   'common-init.c',
+  'compat/ivec.c',
   'compat/nonblock.c',
   'compat/obstack.c',
   'compat/open.c',
-- 
gitgitgadget