Xdiff cleanup part 3

compat/ivec.c line 19

Quoted 3 lines · Ezekiel Newren via GitGitGadget

compat/ivec.c new file +3 -0

+     if (new_capacity == 0) {
+             free(self->ptr);
+             self->ptr = NULL;

        if (!new_capacity)
                FREE_AND_NULL(self->ptr);
        else
                ...;

compat/ivec.c line 92

Quoted 6 lines

compat/ivec.c new file +6 -0

+void ivec_free(void *self_)
+{
+     struct IVec_c_void *self = self_;
+
+     free(self->ptr);
+     self->ptr = NULL;

Likewise. Otherwise the code will fail coccicheck.

compat/ivec.c line 44

Quoted 3 lines

compat/ivec.c new file +3 -0

+     self->length = 0;
+     self->capacity = 0;
+     // DO NOT MODIFY element_size!!!

        /* A single-liner comment in our codebase looks like this */

From: Ezekiel Newren <[email protected]>

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.

compat/ivec.c new file +4 -0

+{
+	struct IVec_c_void *self = self_;
+
+	free(self->ptr);

compat/ivec.c new file +6 -0

+
+	src->ptr = NULL;
+	src->length = 0;
+	src->capacity = 0;
+	// DO NOT MODIFY element_size!!!
+}

compat/ivec.h new file +0 -0

new file mode 100644
index 0000000000..654a05c506

compat/ivec.h new file +37 -0

+
+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 */

meson.build +1 -0

index dd52efd1c8..42ac0c8c42 100644
@@ -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',

Quoted 5 lines

compat/ivec.c new file +0 -0

new file mode 100644
index 0000000000..0a777e78dc

compat/ivec.c line 3

Quoted 4 lines

compat/ivec.c new file +3 -0

@@ -0,0 +1,113 @@
+#include "ivec.h"
+
+struct IVec_c_void {

We normally use all lower case names for structs but as this is shared with rust it maybe makes sense to use CamelCase so the names are the same in both languages.

Quoted 6 lines

compat/ivec.c new file +6 -0

+     void *ptr;
+     size_t length;
+     size_t capacity;
+     size_t element_size;
+};
+

compat/ivec.c line 12

Quoted 3 lines

compat/ivec.c new file +3 -0

+static void _set_capacity(void *self_, size_t new_capacity)
+{
+     struct IVec_c_void *self = self_;

Passing any of the ivec variants defined below to this function invokes undefined behavior because we're not casting the pointer back to the orginal type. However I think on the platforms we care about sizeof(void*) == sizeof(T*) for all T so maybe we can look the other way.

compat/ivec.c line 23

Quoted 11 lines

compat/ivec.c new file +11 -0

+
+     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;

Not if realloc() returns NULL. We should check for that, probably by using xrealloc().

compat/ivec.c line 41

Quoted 5 lines

compat/ivec.c new file +5 -0

+void ivec_zero(void *self_, size_t capacity)
+{
+     struct IVec_c_void *self = self_;
+
+     self->ptr = calloc(capacity, self->element_size);

We should be handling allocation failures here probably by using xcalloc().

Quoted 5 lines

compat/ivec.c new file +5 -0

+void ivec_reserve(void *self_, size_t additional)
+{
+     struct IVec_c_void *self = self_;
+
+     size_t growby = 128;

compat/ivec.c line 62

Quoted 4 lines

compat/ivec.c new file +4 -0

+     if (self->capacity > growby)
+             growby = self->capacity;
+     if (additional > growby)
+             growby = additional;

This growth strategy differs from both ALLOC_GROW() and XDL_ALLOC_GROW(), if there isn't a good reason for that we should perhaps just use ALLOC_GROW() here.

Quoted 5 lines

compat/ivec.c new file +5 -0

+void ivec_push(void *self_, const void *value)
+{
+     struct IVec_c_void *self = self_;
+     void *dst = NULL;
+

compat/ivec.c line 83

Quoted 5 lines

compat/ivec.c new file +5 -0

+     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);

If self->element_size was a compile time constant the compiler could easily optimize this call away. I'm not sure that is easy to achieve though.

compat/ivec.c line 87

Quoted 1 line

compat/ivec.c new file +1 -0

+void ivec_free(void *self_)

Normally we'd call a like this that free the allocations and re-initializes the members ivec_clear()

Quoted 4 lines

compat/ivec.c new file +4 -0

+{
+     struct IVec_c_void *self = self_;
+
+     free(self->ptr);

compat/ivec.c line 101

Quoted 10 lines

compat/ivec.c new file +10 -0

+     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_;

Maybe we should add

        if (src->element_size != dst->element_size)
                BUG("moving incompatible arrays");

compat/ivec.c line 107

Quoted 6 lines

compat/ivec.c new file +6 -0

+
+     ivec_free(dst);
+     dst->ptr = src->ptr;
+     dst->length = src->length;
+     dst->capacity = src->capacity;
+     // DO NOT MODIFY element_size!!!

As the element sizes must match maybe *dst = *src would be clearer?

Quoted 12 lines

compat/ivec.c new file +6 -0

+
+     src->ptr = NULL;
+     src->length = 0;
+     src->capacity = 0;
+     // DO NOT MODIFY element_size!!!
+}

compat/ivec.h new file +0 -0

new file mode 100644
index 0000000000..654a05c506

compat/ivec.h line 4

Quoted 4 lines

compat/ivec.h new file +4 -0

@@ -0,0 +1,52 @@
+#ifndef IVEC_H
+#define IVEC_H
+
+#include <git-compat-util.h>

It would be nice to have some documentation in this header, see the examples in strvec.h and hashmap.h

compat/ivec.h line 6

Quoted 1 line

compat/ivec.h new file +1 -0

+#define IVEC_INIT(variable) ivec_init(&(variable), sizeof(*(variable).ptr))

This is a bit cumbersome to use compared to our usual *_INIT macros. I'm struggling to see how we can make it nicer though as DEFINE_IVEC_TYPE cannot define a per-type initializer macro and I we cannot initialize the element size without knowing the type.

compat/ivec.h line 15

Quoted 9 lines

compat/ivec.h new file +9 -0

+
+#ifndef CBINDGEN
+#define DEFINE_IVEC_TYPE(type, suffix) \
+struct IVec_##suffix { \
+     type* ptr; \
+     size_t length; \
+     size_t capacity; \
+     size_t element_size; \
+}

I wonder if we want to define type safe inline safe wrappers for the ivec_* functions here. I think the only functions where the element type matters are ivec_move() and ivec_push(), for the others like ivec_zero(), ivec_reserve() and ivec_free() the element type does not matter. ivec_push() would certainly be easier to use with a wrapper as means we can avoid forcing the caller to take the address of the value.

static inline ivec_##suffix##_push(struct IVec_##suffix *self, type

value) { \
        const void *ptr = &value; \
        ivec_push(self, ptr); \
}

Quoted 8 lines · Phillip Wood

compat/ivec.c line 12

Quoted 3 lines

compat/ivec.c new file +3 -0

+static void _set_capacity(void *self_, size_t new_capacity)
+{
+     struct IVec_c_void *self = self_;

Passing any of the ivec variants defined below to this function invokes undefined behavior because we're not casting the pointer back to the orginal type. However I think on the platforms we care about sizeof(void*) == sizeof(T*) for all T so maybe we can look the other way.

If someone finds that this code does not work because of this assumption I'd like to know. But I can't fathom a case where it wouldn't work.

I've Cc'd Peff and René for a second opinion if you have time please.

Quoted 11 lines · Ezekiel Newren

Quoted 8 lines · Phillip Wood

compat/ivec.c line 12

Quoted 3 lines

compat/ivec.c new file +3 -0

+static void _set_capacity(void *self_, size_t new_capacity)
+{
+     struct IVec_c_void *self = self_;

Passing any of the ivec variants defined below to this function invokes undefined behavior because we're not casting the pointer back to the orginal type. However I think on the platforms we care about sizeof(void*) == sizeof(T*) for all T so maybe we can look the other way.

Quoted 3 lines

If someone finds that this code does not work because of this assumption I'd like to know. But I can't fathom a case where it wouldn't work.

So we have two different structs

struct IVec_c_void {
    void *ptr;
    size_t length;
    size_t capacity;
    size_t element_size;
}

and

struct Ivec_u8 {
    uint8_t *ptr;
    size_t length;
    size_t capacity;
    size_t element_size;
}

One the platforms we care about they will have the same memory layout as all pointers have the same representation. However I don't think they are "compatible types" in the language of the C standard because the type of the "ptr" member differs. That means casting IVec_u8* to IVec_c_void* either directly or via void* is undefined and so

    struct IVec_u8 vec;
    ivec_init(&vec, sizeof(*vec.ptr));

is undefined. For the compiler to see the undefined cast it needs to look across translation units because the implementation of ivec_init() will be in a separate file to where it is called. Maybe that and the fact they have the same memory layout saves us from having to worry too much though I'm always nervous of undefined behavior.

An alternative would be to pass the individual struct members as function parameters

    void ivec_init(void **vec, size_t &length, size_t &capacity, size_t &element_size_, size_t element_size) {
        *vec = NULL;
        *length = 0;
        *capacity = 0;
        *element_size_ = element_size;
    }

and have DEFINE_IVEC_TYPE create typesafe wrappers

    static inline void ivec_u8_init(struct IVec_u8 *vec) {
        void *ptr = vec->ptr;
        ivec_init(&ptr, &v->length, &v->capacity, &v->element_size, sizeof(*(v->ptr)); vec->ptr = ptr;
    }

That's safe because we cast the "ptr" member to "void*" and then back to the original type. On the rust side the implementation of IVec<T> would also need to split out the individual struct members when it calls ivec_init() etc. It's all a bit more effort but the benefit is that we don't have any undefined behavior and we have a nice typesafe C interface to 'struct IVec_*'.

Quoted 46 lines · Phillip Wood

I've Cc'd Peff and René for a second opinion if you have time please.

Quoted 11 lines · Ezekiel Newren

Quoted 8 lines · Phillip Wood

compat/ivec.c line 12

Quoted 3 lines

compat/ivec.c new file +3 -0

+static void _set_capacity(void *self_, size_t new_capacity)
+{
+     struct IVec_c_void *self = self_;

Passing any of the ivec variants defined below to this function invokes undefined behavior because we're not casting the pointer back to the orginal type. However I think on the platforms we care about sizeof(void*) == sizeof(T*) for all T so maybe we can look the other way.

Quoted 3 lines

If someone finds that this code does not work because of this assumption I'd like to know. But I can't fathom a case where it wouldn't work.

So we have two different structs

struct IVec_c_void {
    void *ptr;
    size_t length;
    size_t capacity;
    size_t element_size;
}

and

struct Ivec_u8 {
    uint8_t *ptr;
    size_t length;
    size_t capacity;
    size_t element_size;
}

One the platforms we care about they will have the same memory layout as all pointers have the same representation. However I don't think they are "compatible types" in the language of the C standard because the type of the "ptr" member differs. That means casting IVec_u8* to IVec_c_void* either directly or via void* is undefined and so

    struct IVec_u8 vec;
    ivec_init(&vec, sizeof(*vec.ptr));

Quoted 6 lines

is undefined. For the compiler to see the undefined cast it needs to look across translation units because the implementation of ivec_init() will be in a separate file to where it is called. Maybe that and the fact they have the same memory layout saves us from having to worry too much though I'm always nervous of undefined behavior.

True. The GCC docs give a fun example of what a compiler might do when using different struct types to access the same memory:

https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Aliasing-Type-Rules.html

Not sure it applies to this case, but the point is that compilers can and will do terrifying things when they smell UB, with little concern for safety or original intent.

Quoted 10 lines

An alternative would be to pass the individual struct members as function parameters

    void ivec_init(void **vec, size_t &length, size_t &capacity, size_t &element_size_, size_t element_size) {
        *vec = NULL;
        *length = 0;
        *capacity = 0;
        *element_size_ = element_size;
    }

The ampersands (&) should be asterisks (*), right?

Quoted 9 lines

and have DEFINE_IVEC_TYPE create typesafe wrappers

    static inline void ivec_u8_init(struct IVec_u8 *vec) {
        void *ptr = vec->ptr;
        ivec_init(&ptr, &v->length, &v->capacity, &v->element_size, sizeof(*(v->ptr)); vec->ptr = ptr;
    }

Mixes "v" and "vec", misses a closing parenthesis. Looks viable, though, and this method should be applicable to the rest of the functions as well (on the C side).

I guess this doesn't require an element_size member anymore as each wrapper can pass in the sizeof value.

Quoted 6 lines

That's safe because we cast the "ptr" member to "void*" and then back to the original type. On the rust side the implementation of IVec<T> would also need to split out the individual struct members when it calls ivec_init() etc. It's all a bit more effort but the benefit is that we don't have any undefined behavior and we have a nice typesafe C interface to 'struct IVec_*'.

Right. No idea how ugly this would be on the Rust side, though.

René

Quoted 54 lines · René Scharfe

Quoted 46 lines · Phillip Wood

I've Cc'd Peff and René for a second opinion if you have time please.

Quoted 11 lines · Ezekiel Newren

Quoted 8 lines · Phillip Wood

compat/ivec.c line 12

Quoted 3 lines

compat/ivec.c new file +3 -0

+static void _set_capacity(void *self_, size_t new_capacity)
+{
+     struct IVec_c_void *self = self_;

Passing any of the ivec variants defined below to this function invokes undefined behavior because we're not casting the pointer back to the orginal type. However I think on the platforms we care about sizeof(void*) == sizeof(T*) for all T so maybe we can look the other way.

Quoted 3 lines

If someone finds that this code does not work because of this assumption I'd like to know. But I can't fathom a case where it wouldn't work.

So we have two different structs

struct IVec_c_void {
     void *ptr;
     size_t length;
     size_t capacity;
     size_t element_size;
}

and

struct Ivec_u8 {
     uint8_t *ptr;
     size_t length;
     size_t capacity;
     size_t element_size;
}

One the platforms we care about they will have the same memory layout as all pointers have the same representation. However I don't think they are "compatible types" in the language of the C standard because the type of the "ptr" member differs. That means casting IVec_u8* to IVec_c_void* either directly or via void* is undefined and so

     struct IVec_u8 vec;
     ivec_init(&vec, sizeof(*vec.ptr));

Quoted 6 lines

is undefined. For the compiler to see the undefined cast it needs to look across translation units because the implementation of ivec_init() will be in a separate file to where it is called. Maybe that and the fact they have the same memory layout saves us from having to worry too much though I'm always nervous of undefined behavior.

Quoted 4 lines

True. The GCC docs give a fun example of what a compiler might do when using different struct types to access the same memory:

https://www.gnu.org/software/c-intro-and-ref/manual/html_node/Aliasing-Type-Rules.html

Thanks for the link

Quoted 15 lines

Not sure it applies to this case, but the point is that compilers can and will do terrifying things when they smell UB, with little concern for safety or original intent.

Quoted 10 lines

An alternative would be to pass the individual struct members as function parameters

     void ivec_init(void **vec, size_t &length, size_t &capacity,
                size_t &element_size_, size_t element_size)
     {
         *vec = NULL;
         *length = 0;
         *capacity = 0;
         *element_size_ = element_size;
     }

Quoted 1 line

The ampersands (&) should be asterisks (*), right?

Indeed, that's embarrassing - I must have been thinking of the caller.

Quoted 10 lines

Quoted 9 lines

and have DEFINE_IVEC_TYPE create typesafe wrappers

     static inline void ivec_u8_init(struct IVec_u8 *vec)
     {
         void *ptr = vec->ptr;
         ivec_init(&ptr, &v->length, &v->capacity,
               &v->element_size, sizeof(*(v->ptr));
         vec->ptr = ptr;
     }

Quoted 6 lines

Mixes "v" and "vec", misses a closing parenthesis. Looks viable, though, and this method should be applicable to the rest of the functions as well (on the C side).

I guess this doesn't require an element_size member anymore as each wrapper can pass in the sizeof value.

Good point

Quoted 6 lines

Quoted 6 lines

That's safe because we cast the "ptr" member to "void*" and then back to the original type. On the rust side the implementation of IVec<T> would also need to split out the individual struct members when it calls ivec_init() etc. It's all a bit more effort but the benefit is that we don't have any undefined behavior and we have a nice typesafe C interface to 'struct IVec_*'.

Quoted 1 line

Right. No idea how ugly this would be on the Rust side, though.

I'm hoping it's not too bad and impl IVec<T> just contains the equivalent of the wrappers generated by DEFINE_IVEC_TYPE()

Thanks

Phillip

Quoted 3 lines

René

I don't like this solution. ivec_push() is the only function that deals with actual values. The rest are just generic memory management functions. What if we used:

#define ivec_init(vec) { \
    (vec)->ptr = NULL; \
    (vec)->length = 0; \
    (vec)->capacity = 0; \
    (vec)->element_size = sizeof(*(vec)->ptr); \
}

#define ivec_push_unsafe(vec, value) (vec)->ptr[(vec)->length++] = (value)

/*
* grow by at least 1
*/

#define ivec_push(vec, value) { \
    if ((vec)->length == (vec)->capacity) \
       ivec_reserve(vec, 1); \
    ivec_push_unsafe(vec, value); \
}

Instead of concrete functions?

I've Cc'd Peff and René for a second opinion if you have time please.

Quoted 11 lines · Ezekiel Newren

Quoted 8 lines · Phillip Wood

compat/ivec.c line 12

Quoted 3 lines

compat/ivec.c new file +3 -0

+static void _set_capacity(void *self_, size_t new_capacity)
+{
+     struct IVec_c_void *self = self_;

Passing any of the ivec variants defined below to this function invokes undefined behavior because we're not casting the pointer back to the orginal type. However I think on the platforms we care about sizeof(void*) == sizeof(T*) for all T so maybe we can look the other way.

Quoted 3 lines

If someone finds that this code does not work because of this assumption I'd like to know. But I can't fathom a case where it wouldn't work.

So we have two different structs

struct IVec_c_void {
        void *ptr;
        size_t length;
        size_t capacity;
        size_t element_size;
}

and

struct Ivec_u8 {
        uint8_t *ptr;
        size_t length;
        size_t capacity;
        size_t element_size;
}

One the platforms we care about they will have the same memory layout as all pointers have the same representation. However I don't think they are "compatible types" in the language of the C standard because the type of the "ptr" member differs. That means casting IVec_u8* to IVec_c_void* either directly or via void* is undefined and so

        struct IVec_u8 vec;
        ivec_init(&vec, sizeof(*vec.ptr));

is undefined. For the compiler to see the undefined cast it needs to look across translation units because the implementation of ivec_init() will be in a separate file to where it is called. Maybe that and the fact they have the same memory layout saves us from having to worry too much though I'm always nervous of undefined behavior.

An alternative would be to pass the individual struct members as function parameters

        void ivec_init(void **vec, size_t &length, size_t &capacity,
                       size_t &element_size_, size_t element_size)
        {
                *vec = NULL;
                *length = 0;
                *capacity = 0;
                *element_size_ = element_size;
        }

and have DEFINE_IVEC_TYPE create typesafe wrappers

        static inline void ivec_u8_init(struct IVec_u8 *vec)
        {
                void *ptr = vec->ptr;
                ivec_init(&ptr, &v->length, &v->capacity,
                          &v->element_size, sizeof(*(v->ptr));
                vec->ptr = ptr;
        }

That's safe because we cast the "ptr" member to "void*" and then back to the original type. On the rust side the implementation of IVec<T> would also need to split out the individual struct members when it calls ivec_init() etc. It's all a bit more effort but the benefit is that we don't have any undefined behavior and we have a nice typesafe C interface to 'struct IVec_*'.

Thanks

Phillip

If the size of different kinds of pointers ever differed from the size of void* then wouldn't that make all calls to malloc undefined? I

If the size of different kinds of pointers ever differed from the size of void* then wouldn't that make all calls to malloc undefined?

I
don't see this as a problem since I'm not casting between structs with different members that are not pointers.

I could use void* for
everything, but then we'd need an accessor like *(T*)ivec_at(&vec, i), but this is much more painful and error prone than simply vec.ptr[i].

Quoted 3 lines · Ezekiel Newren

If the size of different kinds of pointers ever differed from the size of void* then wouldn't that make all calls to malloc undefined?

I believe there are (Havard architecture?) platforms where function pointers are a different width to data pointers, and that's why you cannot store a function pointer in void*. I agree it would be weird for char* to have a different width to int*, I suspect the restrictions on casting from one type to another are about alignment.

Quoted 10 lines · Phillip Wood

Quoted 3 lines · Ezekiel Newren

If the size of different kinds of pointers ever differed from the size of void* then wouldn't that make all calls to malloc undefined?

I believe there are (Havard architecture?) platforms where function pointers are a different width to data pointers, and that's why you cannot store a function pointer in void*. I agree it would be weird for char* to have a different width to int*, I suspect the restrictions on casting from one type to another are about alignment.

The standard does allow for different pointer sizes for char and int. The key thing is that a void pointer has to be able to represent any. So you can cast a smaller pointer to void and vice versa (and the latter would presumably throw away some of the bits, which is OK as long as the void was made from one of those smaller pointers originally).

More discussion at:

https://c-faq.com/null/machexamp.html

I don't know how malloc worked on those platforms, though. The caller knows that malloc returns a void pointer, so it could cast to the smaller format in the usual way at the call-site. But I don't know how you would tell malloc() in a standard way what type of pointer you wanted to get out of it. I suspect they may have had specialized allocation functions. Or maybe it was enough to just throw away the low bits if you only cared about a word-addressable pointer.

At any rate, yeah, I agree with your original concern that the two structs are not compatible. The layouts could be totally different. And not just due to pointer size, but IIRC pointers to different types could have different alignment requirements. So:

  struct foo_void {
        size_t len;
        void *ptr;
  };

  struct foo_u8 {
        size_t len;
        uint8_t *ptr;
  };

might need different padding to properly align the pointers. In the case under discussion the pointers are always at the start, though, so I think it wouldn't matter.

-Peff

Ok..., is there a way to pad a field to the largest size needed so that this also works on the harvard architecture? If C isn't even self consistent then how are these structs going to be passed between C and Rust (which is THE point of ivec)?

Or do we just tell the arcane Harvard architecture "too bad" Git won't run on it anymore?

2. There are some modern platforms in which pointers are a bit more opaque than just numeric addresses. For example, we've had a few patches dealing with questionable pointer usage to make things work on CHERI Arm systems. I'm not sure if any of that would matter here, though (IIRC, it was mostly that pointers were unexpectedly large and had matching alignment requirements, but all of them equally so).

Quoted 4 lines · Ezekiel Newren

Ok..., is there a way to pad a field to the largest size needed so that this also works on the harvard architecture? If C isn't even self consistent then how are these structs going to be passed between C and Rust (which is THE point of ivec)?

If you make a union of the pointers, it will require the largest size and the strictest alignment requirement. So:

  struct foo {
        union {
                void *v;
                uint8_t *u8;
        } ptr;
        size_t len;
  };

would be a single struct you could use to store a void pointer _or_ a u8 pointer. The one thing you shouldn't do there, though, is assign via one union member and read from the other. So I don't know if that helps you or not (I confess I have not followed this rust discussion at all, and know nothing about rust/c ABI compatibility, and just got roped in on C esoterica).

Quoted 2 lines

Or do we just tell the arcane Harvard architecture "too bad" Git won't run on it anymore?

Minor nit: the Harvard architecture is one where function pointers are not the same as data pointers. An int/char distinction can happen even on more common (von Neumann) machines.

But I think we can rephrase your question as: are there real-world machines we care about that will have different pointer sizes, or can we ignore this issue for practical purposes?

I don't know the answer. I suspect it probably is OK for Git not to run on the machines mentioned in that C faq. But:

1. Sometimes there are subtle implications of undefined behavior that may cause a compiler (even for a sensible machine) to do unexpected things. I don't know offhand if that is the case here.

2. There are some modern platforms in which pointers are a bit more opaque than just numeric addresses. For example, we've had a few patches dealing with questionable pointer usage to make things work on CHERI Arm systems. I'm not sure if any of that would matter here, though (IIRC, it was mostly that pointers were unexpectedly large and had matching alignment requirements, but all of them equally so).

-Peff

What about adding clar unit tests to make sure that different ivec types have the same size and layout? e.g. sizeof(IVec_c_void) == sizeof(IVec_u8);
sizeof(IVec_c_void) == sizeof(IVec_u16); sizeof(IVec_c_void) == sizeof(IVec_u32); sizeof(IVec_c_void) == sizeof(IVec_u64);
...

As well as other tests for ivec.

Quoted 8 lines · Ezekiel Newren

What about adding clar unit tests to make sure that different ivec types have the same size and layout? e.g. sizeof(IVec_c_void) == sizeof(IVec_u8);
sizeof(IVec_c_void) == sizeof(IVec_u16); sizeof(IVec_c_void) == sizeof(IVec_u32); sizeof(IVec_c_void) == sizeof(IVec_u64);
...

Quoted 1 line

As well as other tests for ivec.

I'm a little hesitant in general to have run-time tests for properties around undefined behavior, just because the compiler is allowed to do a lot of tricky things when we get into that territory. Plus it is not really _solving_ the problem, but perhaps just alerting us slightly sooner than the production code itself crashing and burning.

Quoted 10 lines · Jeff King

Quoted 8 lines · Ezekiel Newren

What about adding clar unit tests to make sure that different ivec types have the same size and layout? e.g. sizeof(IVec_c_void) == sizeof(IVec_u8);
sizeof(IVec_c_void) == sizeof(IVec_u16); sizeof(IVec_c_void) == sizeof(IVec_u32); sizeof(IVec_c_void) == sizeof(IVec_u64);
...

Quoted 7 lines

Quoted 1 line

As well as other tests for ivec.

I'm a little hesitant in general to have run-time tests for properties around undefined behavior, just because the compiler is allowed to do a lot of tricky things when we get into that territory. Plus it is not really _solving_ the problem, but perhaps just alerting us slightly sooner than the production code itself crashing and burning.

Yup, by definition, testing undefined behaviour with code is more or less pointless. Implementation defined behaviour, maybe, but not undefined ones, please.

I thought you already gave them that having different possibilities in a union would work correctly, but perhaps I was reading a different thread? I dunno...

Quoted 10 lines · Phillip Wood

Quoted 3 lines · Ezekiel Newren

If the size of different kinds of pointers ever differed from the size of void* then wouldn't that make all calls to malloc undefined?

I believe there are (Havard architecture?) platforms where function pointers are a different width to data pointers, and that's why you cannot store a function pointer in void*. I agree it would be weird for char* to have a different width to int*, I suspect the restrictions on casting from one type to another are about alignment.

The standard does allow for different pointer sizes for char and int. The key thing is that a void pointer has to be able to represent any. So you can cast a smaller pointer to void and vice versa (and the latter would presumably throw away some of the bits, which is OK as long as the void was made from one of those smaller pointers originally).

More discussion at:

https://c-faq.com/null/machexamp.html

I don't know how malloc worked on those platforms, though. The caller knows that malloc returns a void pointer, so it could cast to the smaller format in the usual way at the call-site. But I don't know how you would tell malloc() in a standard way what type of pointer you wanted to get out of it. I suspect they may have had specialized allocation functions. Or maybe it was enough to just throw away the low bits if you only cared about a word-addressable pointer.

At any rate, yeah, I agree with your original concern that the two structs are not compatible. The layouts could be totally different. And not just due to pointer size, but IIRC pointers to different types could have different alignment requirements. So:

   struct foo_void {
	size_t len;
	void *ptr;
   };

   struct foo_u8 {
	size_t len;
	uint8_t *ptr;
   };

might need different padding to properly align the pointers. In the case under discussion the pointers are always at the start, though, so I think it wouldn't matter.

-Peff

Quoted 5 lines · Phillip Wood

Quoted 5 lines

compat/ivec.c new file +5 -0

+void ivec_reserve(void *self_, size_t additional)
+{
+     struct IVec_c_void *self = self_;
+
+     size_t growby = 128;

Quoted 8 lines

compat/ivec.c line 62

Quoted 4 lines

compat/ivec.c new file +4 -0

+     if (self->capacity > growby)
+             growby = self->capacity;
+     if (additional > growby)
+             growby = additional;

This growth strategy differs from both ALLOC_GROW() and XDL_ALLOC_GROW(), if there isn't a good reason for that we should perhaps just use ALLOC_GROW() here.

XDL_ALLOW_GROW() can't be used because the pointer is always a void* in this function.

Quoted 5 lines

Quoted 5 lines

compat/ivec.c new file +5 -0

+void ivec_push(void *self_, const void *value)
+{
+     struct IVec_c_void *self = self_;
+     void *dst = NULL;
+

Quoted 8 lines

compat/ivec.c line 83

Quoted 5 lines

compat/ivec.c new file +5 -0

+     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);

If self->element_size was a compile time constant the compiler could easily optimize this call away. I'm not sure that is easy to achieve though.

The problem is that I didn't want all of ivec to be macros that looked like function calls. I wanted to minimize use of macros so that it was easier to port and verify that the Rust implementation matches the behavior of the C implementation.

Quoted 4 lines

Quoted 1 line

+void ivec_free(void *self_)

Normally we'd call a like this that free the allocations and re-initializes the members ivec_clear()

In Rust Vec.clear() means to set length to zero, but leaves the allocation alone. The reason why I'm zeroing the struct is to help avoid FFI issues. If not zero then what should the members be set to, to indicate that using the struct is not valid anymore? In Rust an object is freed when it goes out of scope and _cannot_ be accessed afterward.

Quoted 16 lines

compat/ivec.h line 4

Quoted 10 lines

compat/ivec.h new file +4 -0

new file mode 100644
index 0000000000..654a05c506
@@ -0,0 +1,52 @@
+#ifndef IVEC_H
+#define IVEC_H
+
+#include <git-compat-util.h>

It would be nice to have some documentation in this header, see the examples in strvec.h and hashmap.h

Quoted 1 line

compat/ivec.h new file +1 -0

+#define IVEC_INIT(variable) ivec_init(&(variable), sizeof(*(variable).ptr))

Quoted 4 lines

This is a bit cumbersome to use compared to our usual *_INIT macros. I'm struggling to see how we can make it nicer though as DEFINE_IVEC_TYPE cannot define a per-type initializer macro and I we cannot initialize the element size without knowing the type.

I don't see what's cumbersome about it. Maybe an example use case would clarify things.

```
DEFINE_IVEC_TYPE(xrecord_t, xrecord);

void some_function() {
     struct IVec_xrecord rec;
     IVEC_INIT(rec);  // i.e. ivec_init(&rec, sizeof(*rec.ptr);

Hi Ezekiel

Quoted 15 lines · Ezekiel Newren

Quoted 5 lines · Phillip Wood

Quoted 5 lines

compat/ivec.c new file +5 -0

+void ivec_reserve(void *self_, size_t additional)
+{
+     struct IVec_c_void *self = self_;
+
+     size_t growby = 128;

Quoted 8 lines

compat/ivec.c line 62

Quoted 4 lines

compat/ivec.c new file +4 -0

+     if (self->capacity > growby)
+             growby = self->capacity;
+     if (additional > growby)
+             growby = additional;

This growth strategy differs from both ALLOC_GROW() and XDL_ALLOC_GROW(), if there isn't a good reason for that we should perhaps just use ALLOC_GROW() here.

Quoted 2 lines

XDL_ALLOW_GROW() can't be used because the pointer is always a void* in this function.

Oh right. I'm not sure that's not a reason to use a different growth strategy though. The minimum size of 128 elements is probably good for the xdiff code that creates arrays with one element per line but if this is supposed to be for general use it is going to waste space when we're allocating a lot of small arrays. ALLOC_GROW() uses alloc_nr() to calculate the new side so perhaps we could use that here?

Quoted 14 lines

Quoted 13 lines

compat/ivec.c line 83

Quoted 10 lines

compat/ivec.c new file +10 -0

+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);

If self->element_size was a compile time constant the compiler could easily optimize this call away. I'm not sure that is easy to achieve though.

Quoted 4 lines

The problem is that I didn't want all of ivec to be macros that looked like function calls. I wanted to minimize use of macros so that it was easier to port and verify that the Rust implementation matches the behavior of the C implementation.

I think that's a reasonable concern. So is the plan to have a parallel rust implementation of these functions rather than call the C implementation from rust?

Quoted 11 lines

Quoted 4 lines

Quoted 1 line

+void ivec_free(void *self_)

Normally we'd call a like this that free the allocations and re-initializes the members ivec_clear()

In Rust Vec.clear() means to set length to zero, but leaves the allocation alone. The reason why I'm zeroing the struct is to help avoid FFI issues. If not zero then what should the members be set to, to indicate that using the struct is not valid anymore? In Rust an object is freed when it goes out of scope and _cannot_ be accessed afterward.

I'm aware that Vec::clear() has different semantics (it does what strbuf_reset() does). That's unfortunate but this function has different semantics to all the other *_free() functions in git. Our coding guidelines say

- There are several common idiomatic names for functions performing specific tasks on a structure S:

- S_init() initializes a structure without allocating the structure itself.

- S_release() releases a structure's contents without freeing the structure.

- S_clear() is equivalent to S_release() followed by S_init() such that the structure is directly usable after clearing it. When S_clear() is provided, S_init() shall not allocate resources that need to be released again.

- S_free() releases a structure's contents and frees the structure.

As we write more rust code and so wrap more of our existing structs we're going to be wrapping C code that uses the definitions above so I think we should do the same with struct IVec_*.

Quoted 16 lines

Quoted 16 lines

compat/ivec.h line 4

Quoted 10 lines

compat/ivec.h new file +4 -0

new file mode 100644
index 0000000000..654a05c506
@@ -0,0 +1,52 @@
+#ifndef IVEC_H
+#define IVEC_H
+
+#include <git-compat-util.h>

It would be nice to have some documentation in this header, see the examples in strvec.h and hashmap.h

Quoted 1 line

compat/ivec.h new file +1 -0

+#define IVEC_INIT(variable) ivec_init(&(variable), sizeof(*(variable).ptr))

Quoted 7 lines

Quoted 4 lines

This is a bit cumbersome to use compared to our usual *_INIT macros. I'm struggling to see how we can make it nicer though as DEFINE_IVEC_TYPE cannot define a per-type initializer macro and I we cannot initialize the element size without knowing the type.

I don't see what's cumbersome about it. Maybe an example use case would clarify things.

It is cumbersome because it separates the initialization from the declaration. Normally our *_INIT macros are initializer lists so we can write

        struct strbuf = STRBUF_INIT;

which keeps the declaration and initialization together. Although they're on adjacent lines in your example in real code the initialization likely to be separated from the declaration by other variable declarations.

Quoted 22 lines · Phillip Wood

Hi Ezekiel

Quoted 15 lines · Ezekiel Newren

Quoted 5 lines · Phillip Wood

Quoted 5 lines

compat/ivec.c new file +5 -0

+void ivec_reserve(void *self_, size_t additional)
+{
+     struct IVec_c_void *self = self_;
+
+     size_t growby = 128;

Quoted 8 lines

compat/ivec.c line 62

Quoted 4 lines

compat/ivec.c new file +4 -0

+     if (self->capacity > growby)
+             growby = self->capacity;
+     if (additional > growby)
+             growby = additional;

This growth strategy differs from both ALLOC_GROW() and XDL_ALLOC_GROW(), if there isn't a good reason for that we should perhaps just use ALLOC_GROW() here.

Quoted 2 lines

XDL_ALLOW_GROW() can't be used because the pointer is always a void* in this function.

Quoted 6 lines

Oh right. I'm not sure that's not a reason to use a different growth strategy though. The minimum size of 128 elements is probably good for the xdiff code that creates arrays with one element per line but if this is supposed to be for general use it is going to waste space when we're allocating a lot of small arrays. ALLOC_GROW() uses alloc_nr() to calculate the new side so perhaps we could use that here?

If ivec_reserve() isn't suitable then ivec_reserve_exact() should be used instead.

Quoted 14 lines

Quoted 14 lines

Quoted 13 lines

compat/ivec.c line 83

Quoted 10 lines

compat/ivec.c new file +10 -0

+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);

If self->element_size was a compile time constant the compiler could easily optimize this call away. I'm not sure that is easy to achieve though.

Quoted 8 lines

Quoted 4 lines

The problem is that I didn't want all of ivec to be macros that looked like function calls. I wanted to minimize use of macros so that it was easier to port and verify that the Rust implementation matches the behavior of the C implementation.

I think that's a reasonable concern. So is the plan to have a parallel rust implementation of these functions rather than call the C implementation from rust?

Yes, the Rust implementation will be independent of the C implementation, but will behave the same way. That's why I'm calling it an interoperable vec as opposed to a compatible vec. Rust can't call the C ivec functions and C can't call the Rust ivec functions, but they'll behave the same way.

Quoted 11 lines

Quoted 11 lines

Quoted 4 lines

Quoted 1 line

+void ivec_free(void *self_)

Normally we'd call a like this that free the allocations and re-initializes the members ivec_clear()

In Rust Vec.clear() means to set length to zero, but leaves the allocation alone. The reason why I'm zeroing the struct is to help avoid FFI issues. If not zero then what should the members be set to, to indicate that using the struct is not valid anymore? In Rust an object is freed when it goes out of scope and _cannot_ be accessed afterward.

Maybe I should call this ivec_drop(). Though the notion of explicitly freeing an object in Rust is _almost_ nonsense. The way you free something in Rust is to let it go out of scope.

Quoted 19 lines

I'm aware that Vec::clear() has different semantics (it does what strbuf_reset() does). That's unfortunate but this function has different semantics to all the other *_free() functions in git. Our coding guidelines say

- There are several common idiomatic names for functions performing specific tasks on a structure S:

- S_init() initializes a structure without allocating the structure itself.

- S_release() releases a structure's contents without freeing the structure.

- S_clear() is equivalent to S_release() followed by S_init() such that the structure is directly usable after clearing it. When S_clear() is provided, S_init() shall not allocate resources that need to be released again.

Quoted 6 lines

- S_free() releases a structure's contents and frees the structure.

As we write more rust code and so wrap more of our existing structs we're going to be wrapping C code that uses the definitions above so I think we should do the same with struct IVec_*.

I disagree. IVec isn't a wrapper around an existing struct.

ivec is
meant to very closely mimic Rust's Vec while guaranteeing interoperability. For things like strbuf I haven't conceived of a solution for that yet. Making ivec diverge from Rust's Vec will result in POLA violations due to different behavior when refactoring an IVec<your_type_here> to Vec<your_type_here>.

Quoted 30 lines

Quoted 16 lines

Quoted 16 lines

compat/ivec.h line 4

Quoted 10 lines

compat/ivec.h new file +4 -0

new file mode 100644
index 0000000000..654a05c506
@@ -0,0 +1,52 @@
+#ifndef IVEC_H
+#define IVEC_H
+
+#include <git-compat-util.h>

It would be nice to have some documentation in this header, see the examples in strvec.h and hashmap.h

Quoted 1 line

compat/ivec.h new file +1 -0

+#define IVEC_INIT(variable) ivec_init(&(variable), sizeof(*(variable).ptr))

Quoted 7 lines

Quoted 4 lines

This is a bit cumbersome to use compared to our usual *_INIT macros. I'm struggling to see how we can make it nicer though as DEFINE_IVEC_TYPE cannot define a per-type initializer macro and I we cannot initialize the element size without knowing the type.

I don't see what's cumbersome about it. Maybe an example use case would clarify things.

It is cumbersome because it separates the initialization from the declaration. Normally our *_INIT macros are initializer lists so we can write

         struct strbuf = STRBUF_INIT;

Quoted 4 lines

which keeps the declaration and initialization together. Although they're on adjacent lines in your example in real code the initialization likely to be separated from the declaration by other variable declarations.

Ah I see what you mean now. I'll experiment with making IVEC_INIT() work like that. One wrinkle is that STRBUF_INIT is a single concrete type whereas IVEC_INIT() is meant for generic types.

compat/ivec.c new file +55 -0

new file mode 100644
index 0000000000..0a777e78dc
@@ -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)
+{

Quoted 61 lines · Ezekiel Newren via GitGitGadget

compat/ivec.c new file +55 -0

new file mode 100644
index 0000000000..0a777e78dc
@@ -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)
+{

compat/ivec.c line 65

Quoted 10 lines

compat/ivec.c new file +10 -0

+     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);
+}

Constant growth steps like these cause linear growth and quadratic complexity. ALLOC_GROW does exponential growth with factor 1.5 to get linear complexity. Here's an old plea to do the same:
https://blog.mozilla.org/nnethercote/2014/11/04/please-grow-your-buffers-exponentially/

René

Quoted 19 lines · René Scharfe

compat/ivec.c line 65

Quoted 13 lines

compat/ivec.c new file +12 -0

+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);
+}

Constant growth steps like these cause linear growth and quadratic complexity. ALLOC_GROW does exponential growth with factor 1.5 to get linear complexity. Here's an old plea to do the same:
https://blog.mozilla.org/nnethercote/2014/11/04/please-grow-your-buffers-exponentially/

Quoted 1 line

René

It _is_ exponential. ivec_reserve(&vec, 1) means grow by _at least_ 1.

From: Ezekiel Newren <[email protected]>

Later patches will prepare xdl_cleanup_records() to be moved into xdiffi.c since only the classic diff uses that function.

Signed-off-by Ezekiel Newren <[email protected]>

xdiff/xdiffi.c +8 -0

+int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+		xdfenv_t *xe) {
+	int res;
+
+	if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0)
+		return -1;
+
+	if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) {

   out:
  	if (res < 0)
  		xdl_free_env(xe);

xdiff/xdiffi.h +1 -0

index 49e52c67f9..8bf4c20373 100644
@@ -42,6 +42,7 @@ typedef struct s_xdchange {
  int xdl_recs_cmp(xdfile_t *xdf1, long off1, long lim1,
  		 xdfile_t *xdf2, long off2, long lim2,
  		 long *kvdf, long *kvdb, int need_min, xdalgoenv_t *xenv);
+int xdl_do_classic_diff(xdfenv_t *xe, uint64_t flags);
  int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  		xdfenv_t *xe);
  int xdl_change_compact(xdfile_t *xdf, xdfile_t *xdfo, long flags);

Quoted 4 lines · Ezekiel Newren via GitGitGadget

From: Ezekiel Newren <[email protected]>

Later patches will prepare xdl_cleanup_records() to be moved into xdiffi.c since only the classic diff uses that function.

I assume that's to make it easier to covert the myers implementation to rust without affecting the rest of the code? If so it would be nice to say that.

Quoted 10 lines

Signed-off-by Ezekiel Newren <[email protected]>

xdiff/xdiffi.c +8 -0

+int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
+             xdfenv_t *xe) {
+     int res;
+
+     if (xdl_prepare_env(mf1, mf2, xpp, xe) < 0)
+             return -1;
+
+     if (XDF_DIFF_ALG(xpp->flags) == XDF_PATIENCE_DIFF) {

xdiff/xdiffi.c int xdl_do_diff(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, · line 371

Quoted 10 lines

xdiff/xdiffi.c +10 -0

+             res = xdl_do_patience_diff(xpp, xe);
+             goto out;
+     }
+
+     if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF) {
+             res = xdl_do_histogram_diff(xpp, xe);
+             goto out;
+     }
+
+     res = xdl_do_classic_diff(xe, xpp->flags);

This might be clearer that we're calling only one of the three functions if we wrote this as

        if (XDF_DIFF_ALG(xpp->flags) == XDIF_PATIENCE_DIFF)
                res = xdl_do_patience_diff(xpp, xe);
        else if (XDF_DIFF_ALG(xpp->flags) == XDF_HISTOGRAM_DIFF)
                res = xdl_do_histogram_diff(xpp, xe);
        else
                res = xdl_do_classic_diff(xe, xpp->flags);

and then we can drop the out: label

From: Ezekiel Newren <[email protected]>

All lines must be read anyway, so classify them after they're read in. Also move the memset() into xdl_init_classifier().

xdiff/xprepare.c +5 -0

+	}
+
+	for (size_t i = 0; i < xe->xdf2.nrec; i++) {
+		xrecord_t *rec = &xe->xdf2.recs[i];
+		xdl_classify_record(2, &cf, rec);
  	}
 
  	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&

xdiff/xutils.c +0 -20

index 77ee1ad9c8..b3d51197c1 100644
@@ -118,26 +118,6 @@ void *xdl_cha_alloc(chastore_t *cha) {
  	return data;
  }
 
-long xdl_guess_lines(mmfile_t *mf, long sample) {
-	long nl = 0, size, tsize = 0;
-	char const *data, *cur, *top;
-
-	if ((cur = data = xdl_mmfile_first(mf, &size))) {
-		for (top = data + size; nl < sample && cur < top; ) {
-			nl++;
-			if (!(cur = memchr(cur, '\n', top - cur)))
-				cur = top;
-			else
-				cur++;
-		}
-		tsize += (long) (cur - data);
-	}
-
-	if (nl && tsize)
-		nl = xdl_mmfile_size(mf) / (tsize / nl);
-
-	return nl + 1;
-}
 
  int xdl_blankline(const char *line, long size, long flags)
  {

xdiff/xutils.h +0 -1

index 615b4a9d35..d800840dd0 100644
@@ -31,7 +31,6 @@ int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
  int xdl_cha_init(chastore_t *cha, long isize, long icount);
  void xdl_cha_free(chastore_t *cha);
  void *xdl_cha_alloc(chastore_t *cha);
-long xdl_guess_lines(mmfile_t *mf, long sample);
  int xdl_blankline(const char *line, long size, long flags);
  int xdl_recmatch(const char *l1, long s1, const char *l2, long s2, long flags);
  uint64_t xdl_hash_record_verbatim(uint8_t const **data, uint8_t const *top);

Quoted 4 lines · Ezekiel Newren via GitGitGadget

From: Ezekiel Newren <[email protected]>

All lines must be read anyway, so classify them after they're read in. Also move the memset() into xdl_init_classifier().

So instead of looping over the input lines one and a bit times (the bit being from xdl_guess_lines) we now loop over them twice as we split them first and then classify them in a separate loop. It does save some work not to call xdl_guess_lines but it is unclear if that offsets classifying them in a separate loop.

xdiff/xprepare.c static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2 · line 399

Quoted 3 lines

xdiff/xprepare.c +3 -0

+     for (size_t i = 0; i < xe->xdf1.nrec; i++) {
+             xrecord_t *rec = &xe->xdf1.recs[i];
+             xdl_classify_record(1, &cf, rec);

We seem to have lost the error handling if xdl_classify_record() fails.

Quoted 13 lines · Phillip Wood

Quoted 4 lines · Ezekiel Newren via GitGitGadget

From: Ezekiel Newren <[email protected]>

All lines must be read anyway, so classify them after they're read in. Also move the memset() into xdl_init_classifier().

So instead of looping over the input lines one and a bit times (the bit being from xdl_guess_lines) we now loop over them twice as we split them first and then classify them in a separate loop. It does save some work not to call xdl_guess_lines but it is unclear if that offsets classifying them in a separate loop.

Quoted 5 lines

xdiff/xprepare.c static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2 · line 399

Quoted 3 lines

xdiff/xprepare.c +3 -0

+     for (size_t i = 0; i < xe->xdf1.nrec; i++) {
+             xrecord_t *rec = &xe->xdf1.recs[i];
+             xdl_classify_record(1, &cf, rec);

We seem to have lost the error handling if xdl_classify_record() fails.

The error handling was not "lost" it was deliberately removed.

The
only way in which xdl_classify_record() could fail is by a failed memory allocation. On the Rust side this would result in a panic (panic means something different in Rust vs C) in which case C could not possibly recover.

Also for operations like Vec.push() in Rust it's
assumed that memory management functions will never fail and if they do they crash the program with no chance of recovery (unless you account for panic unwinding which is really ugly). It seems a lot of arguments about ivec and my xdiff cleanups are "We don't do things this way in Git/C" I'm aware of many of these arguments and I'm trying to address them with a more specific answer of "Yes, but that's not how things are done in Rust and all of this is to prepare the code for conversion to Rust and some things shouldn't, or even, cannot be done the C way in Rust."

From: Ezekiel Newren <[email protected]>

The patience diff is set up the exact same way as histogram, see xdl_do_historgram_diff() in xhistogram.c. xdl_optimize_ctxs() is redundant now, delete it.

xdiff/xprepare.c +0 -11

-static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {
-
-	if (xdl_trim_ends(xdf1, xdf2) < 0 ||
-	    xdl_cleanup_records(cf, xdf1, xdf2) < 0) {
-
-		return -1;
-	}
-
-	return 0;
-}
-
  int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  		    xdfenv_t *xe) {
  	xdlclassifier_t cf;

xdiff/xprepare.c +1 -1

  	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
  	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
-	    xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) {
+	    xdl_cleanup_records(&cf, &xe->xdf1, &xe->xdf2) < 0) {
 
  		xdl_free_ctx(&xe->xdf2);
  		xdl_free_ctx(&xe->xdf1);

Quoted 5 lines · Ezekiel Newren via GitGitGadget

From: Ezekiel Newren <[email protected]>

The patience diff is set up the exact same way as histogram, see xdl_do_historgram_diff() in xhistogram.c. xdl_optimize_ctxs() is redundant now, delete it.

Does this change the output? The patience diff looks for unique context lines and builds the context out from those. For files that look like

Old    New
A    A
B    B
C    A
B    B
A    C
    B
    A

That will give a hunk

(quoted diff) +2 -0

@@ -1,3 +0,5 @@
+A
+B
  A
  B
  C

but trimming the common prefix first would give

@@ -1,5 +1,7
 A
 B

(quoted diff) +2 -0

+A
+B
  C
  B
  A

Though it seems like the diff silder causes us to output the same diff in both cases for that simple test so maybe it is not an issue.

It would certainly be helpful to comment on any possible changes in the commit message as it could have been a deliberate choice not to trim the ends for those algorithms.

Quoted 16 lines

-static int xdl_optimize_ctxs(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xdf2) {

xdiff/xprepare.c +0 -10

-
-    if (xdl_trim_ends(xdf1, xdf2) < 0 ||
-        xdl_cleanup_records(cf, xdf1, xdf2) < 0) {
-
-        return -1;
-    }
-
-    return 0;
-}
-

  int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp, xdfenv_t *xe) {
      xdlclassifier_t cf;

xdiff/xprepare.c int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, · line 396

Quoted 4 lines

xdiff/xprepare.c +1 -0

@@ -404,9 +393,10 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, 
 xpparam_t const *xpp,
           xdl_classify_record(2, &cf, rec);
       }
+    xdl_trim_ends(&xe->xdf1, &xe->xdf2);

It would be clear that this was safe if you changed the function signature to return void as the way it is called in xdl_optimize_ctxs() makes it look like it can return an error.

Thanks

Phillip

Quoted 6 lines

      if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) && (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) && -        xdl_optimize_ctxs(&cf, &xe->xdf1, &xe->xdf2) < 0) { +        xdl_cleanup_records(&cf, &xe->xdf1, &xe->xdf2) < 0) { xdl_free_ctx(&xe->xdf2); xdl_free_ctx(&xe->xdf1);

From: Ezekiel Newren <[email protected]>

View with --color-words. Prepare these functions to use the fields:
delta_start, delta_end. A future patch will add these fields to xdfenv_t.

long i, nm, mlim;
xrecord_t *recs;
xdlclass_t *rcrec;

xdiff/xprepare.c +29 -29

@@ -273,11 +273,11 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
  	 * Create temporary arrays that will help us decide if
  	 * changed[i] should remain false, or become true.
  	 */
-	if (!XDL_CALLOC_ARRAY(action1, xdf1->nrec + 1)) {
+	if (!XDL_CALLOC_ARRAY(action1, xe->xdf1.nrec + 1)) {
  		ret = -1;
  		goto cleanup;
  	}
-	if (!XDL_CALLOC_ARRAY(action2, xdf2->nrec + 1)) {
+	if (!XDL_CALLOC_ARRAY(action2, xe->xdf2.nrec + 1)) {
  		ret = -1;
  		goto cleanup;
  	}

@@ -285,17 +285,17 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
  	/*
  	 * Initialize temporary arrays with DISCARD, KEEP, or INVESTIGATE.
  	 */
-	if ((mlim = xdl_bogosqrt((long)xdf1->nrec)) > XDL_MAX_EQLIMIT)
+	if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
  		mlim = XDL_MAX_EQLIMIT;
-	for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart]; i <= xdf1->dend; i++, recs++) {
+	for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart]; i <= xe->xdf1.dend; i++, recs++) {
  		rcrec = cf->rcrecs[recs->minimal_perfect_hash];
  		nm = rcrec ? rcrec->len2 : 0;
  		action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;
  	}
 
-	if ((mlim = xdl_bogosqrt((long)xdf2->nrec)) > XDL_MAX_EQLIMIT)
+	if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
  		mlim = XDL_MAX_EQLIMIT;
-	for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart]; i <= xdf2->dend; i++, recs++) {
+	for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart]; i <= xe->xdf2.dend; i++, recs++) {
  		rcrec = cf->rcrecs[recs->minimal_perfect_hash];
  		nm = rcrec ? rcrec->len1 : 0;
  		action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;

@@ -305,27 +305,27 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfile_t *xdf1, xdfile_t *xd
  	 * Use temporary arrays to decide if changed[i] should remain
  	 * false, or become true.
  	 */
-	xdf1->nreff = 0;
-	for (i = xdf1->dstart, recs = &xdf1->recs[xdf1->dstart];
-	     i <= xdf1->dend; i++, recs++) {
+	xe->xdf1.nreff = 0;
+	for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart];
+	     i <= xe->xdf1.dend; i++, recs++) {
  		if (action1[i] == KEEP ||
-		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xdf1->dstart, xdf1->dend))) {
-			xdf1->reference_index[xdf1->nreff++] = i;
+		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->xdf1.dstart, xe->xdf1.dend))) {
+			xe->xdf1.reference_index[xe->xdf1.nreff++] = i;
  			/* changed[i] remains false, i.e. keep */
  		} else
-			xdf1->changed[i] = true;
+			xe->xdf1.changed[i] = true;
  			/* i.e. discard */
  	}
 
-	xdf2->nreff = 0;
-	for (i = xdf2->dstart, recs = &xdf2->recs[xdf2->dstart];
-	     i <= xdf2->dend; i++, recs++) {
+	xe->xdf2.nreff = 0;
+	for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart];
+	     i <= xe->xdf2.dend; i++, recs++) {
  		if (action2[i] == KEEP ||
-		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xdf2->dstart, xdf2->dend))) {
-			xdf2->reference_index[xdf2->nreff++] = i;
+		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->xdf2.dstart, xe->xdf2.dend))) {
+			xe->xdf2.reference_index[xe->xdf2.nreff++] = i;
  			/* changed[i] remains false, i.e. keep */
  		} else
-			xdf2->changed[i] = true;
+			xe->xdf2.changed[i] = true;
  			/* i.e. discard */
  	}
 

@@ -340,27 +340,27 @@ cleanup:
  /*
   * Early trim initial and terminal matching records.
   */
-static int xdl_trim_ends(xdfile_t *xdf1, xdfile_t *xdf2) {
+static int xdl_trim_ends(xdfenv_t *xe) {
  	long i, lim;
  	xrecord_t *recs1, *recs2;
 
-	recs1 = xdf1->recs;
-	recs2 = xdf2->recs;
-	for (i = 0, lim = (long)XDL_MIN(xdf1->nrec, xdf2->nrec); i < lim;
+	recs1 = xe->xdf1.recs;
+	recs2 = xe->xdf2.recs;
+	for (i = 0, lim = (long)XDL_MIN(xe->xdf1.nrec, xe->xdf2.nrec); i < lim;
  	     i++, recs1++, recs2++)
  		if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash)
  			break;
 
-	xdf1->dstart = xdf2->dstart = i;
+	xe->xdf1.dstart = xe->xdf2.dstart = i;
 
-	recs1 = xdf1->recs + xdf1->nrec - 1;
-	recs2 = xdf2->recs + xdf2->nrec - 1;
+	recs1 = xe->xdf1.recs + xe->xdf1.nrec - 1;
+	recs2 = xe->xdf2.recs + xe->xdf2.nrec - 1;
  	for (lim -= i, i = 0; i < lim; i++, recs1--, recs2--)
  		if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash)
  			break;
 
-	xdf1->dend = (long)xdf1->nrec - i - 1;
-	xdf2->dend = (long)xdf2->nrec - i - 1;
+	xe->xdf1.dend = (long)xe->xdf1.nrec - i - 1;
+	xe->xdf2.dend = (long)xe->xdf2.nrec - i - 1;
 
  	return 0;
  }

@@ -393,10 +393,10 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  		xdl_classify_record(2, &cf, rec);
  	}
 
-	xdl_trim_ends(&xe->xdf1, &xe->xdf2);
+	xdl_trim_ends(xe);
  	if ((XDF_DIFF_ALG(xpp->flags) != XDF_PATIENCE_DIFF) &&
  	    (XDF_DIFF_ALG(xpp->flags) != XDF_HISTOGRAM_DIFF) &&
-	    xdl_cleanup_records(&cf, &xe->xdf1, &xe->xdf2) < 0) {
+	    xdl_cleanup_records(&cf, xe) < 0) {
 
  		xdl_free_ctx(&xe->xdf2);
  		xdl_free_ctx(&xe->xdf1);

From: Ezekiel Newren <[email protected]>

This patch is best viewed with a before and after of the whole function.

Rather than using 2 pointers and walking them. Use direct indexing with local variables of what is being compared to make it easier to follow along.

xdiff/xprepare.c +0 -8

index 0acb3437d4..06b6a6f804 100644
@@ -340,29 +340,29 @@ cleanup:
  /*
   * Early trim initial and terminal matching records.
   */
-static int xdl_trim_ends(xdfenv_t *xe) {
-	long i, lim;
-	xrecord_t *recs1, *recs2;
-
-	recs1 = xe->xdf1.recs;
-	recs2 = xe->xdf2.recs;
-	for (i = 0, lim = (long)XDL_MIN(xe->xdf1.nrec, xe->xdf2.nrec); i < lim;
-	     i++, recs1++, recs2++)

xdiff/xprepare.c +11 -11

+			lim -= i;
  			break;
+		}
+	}
 
-	xe->xdf1.dstart = xe->xdf2.dstart = i;
-
-	recs1 = xe->xdf1.recs + xe->xdf1.nrec - 1;
-	recs2 = xe->xdf2.recs + xe->xdf2.nrec - 1;
-	for (lim -= i, i = 0; i < lim; i++, recs1--, recs2--)
-		if (recs1->minimal_perfect_hash != recs2->minimal_perfect_hash)
+	for (size_t i = 0; i < lim; i++) {
+		size_t mph1 = xe->xdf1.recs[xe->xdf1.nrec - 1 - i].minimal_perfect_hash;
+		size_t mph2 = xe->xdf2.recs[xe->xdf2.nrec - 1 - i].minimal_perfect_hash;
+		if (mph1 != mph2) {
+			xe->xdf1.dend = xe->xdf1.nrec - 1 - i;
+			xe->xdf2.dend = xe->xdf2.nrec - 1 - i;
  			break;
-
-	xe->xdf1.dend = (long)xe->xdf1.nrec - i - 1;
-	xe->xdf2.dend = (long)xe->xdf2.nrec - i - 1;
-
-	return 0;
+		}
+	}
  }
 
 

From: Ezekiel Newren <[email protected]>

Placing delta_start in xdfenv_t instead of xdfile_t provides a more appropriate context since this variable only makes sense with a pair of files. View with --color-words.

Signed-off-by Ezekiel Newren <[email protected]>

---
  xdiff/xhistogram.c |  4 ++--
  xdiff/xpatience.c  |  4 ++--
  xdiff/xprepare.c   | 17 +++++++++--------
  xdiff/xtypes.h     |  3 ++-
  4 files changed, 15 insertions(+), 13 deletions(-)

xdiff/xhistogram.c +2 -2

index 5ae1282c27..eb6a52d9ba 100644
@@ -365,6 +365,6 @@ out:
  int xdl_do_histogram_diff(xpparam_t const *xpp, xdfenv_t *env)
  {
  	return histogram_diff(xpp, env,
-		env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
-		env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
+		env->delta_start + 1, env->xdf1.dend - env->delta_start + 1,
+		env->delta_start + 1, env->xdf2.dend - env->delta_start + 1);
  }

xdiff/xpatience.c +2 -2

index 2bce07cf48..bd0ffbb417 100644
@@ -374,6 +374,6 @@ static int patience_diff(xpparam_t const *xpp, xdfenv_t *env,
  int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env)
  {
  	return patience_diff(xpp, env,
-		env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
-		env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
+		env->delta_start + 1, env->xdf1.dend - env->delta_start + 1,
+		env->delta_start + 1, env->xdf2.dend - env->delta_start + 1);
  }

xdiff/xprepare.c +9 -8

index 06b6a6f804..e88468e74c 100644
@@ -173,7 +173,6 @@ static int xdl_prepare_ctx(mmfile_t *mf, xdfile_t *xdf, uint64_t flags) {
 
  	xdf->changed += 1;
  	xdf->nreff = 0;
-	xdf->dstart = 0;
  	xdf->dend = xdf->nrec - 1;
 
  	return 0;

@@ -287,7 +286,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) {
  	 */
  	if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
  		mlim = XDL_MAX_EQLIMIT;
-	for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart]; i <= xe->xdf1.dend; i++, recs++) {
+	for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; i <= xe->xdf1.dend; i++, recs++) {
  		rcrec = cf->rcrecs[recs->minimal_perfect_hash];
  		nm = rcrec ? rcrec->len2 : 0;
  		action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;

@@ -295,7 +294,7 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) {
 
  	if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
  		mlim = XDL_MAX_EQLIMIT;
-	for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart]; i <= xe->xdf2.dend; i++, recs++) {
+	for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; i <= xe->xdf2.dend; i++, recs++) {
  		rcrec = cf->rcrecs[recs->minimal_perfect_hash];
  		nm = rcrec ? rcrec->len1 : 0;
  		action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && !need_min) ? INVESTIGATE: KEEP;

@@ -306,10 +305,10 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) {
  	 * false, or become true.
  	 */
  	xe->xdf1.nreff = 0;
-	for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart];
+	for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start];
  	     i <= xe->xdf1.dend; i++, recs++) {
  		if (action1[i] == KEEP ||
-		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->xdf1.dstart, xe->xdf1.dend))) {
+		    (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->delta_start, xe->xdf1.dend))) {
  			xe->xdf1.reference_index[xe->xdf1.nreff++] = i;
  			/* changed[i] remains false, i.e. keep */
  		} else

@@ -318,10 +317,10 @@ static int xdl_cleanup_records(xdlclassifier_t *cf, xdfenv_t *xe) {
  	}
 
  	xe->xdf2.nreff = 0;
-	for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart];
+	for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start];
  	     i <= xe->xdf2.dend; i++, recs++) {
  		if (action2[i] == KEEP ||
-		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->xdf2.dstart, xe->xdf2.dend))) {
+		    (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->delta_start, xe->xdf2.dend))) {
  			xe->xdf2.reference_index[xe->xdf2.nreff++] = i;
  			/* changed[i] remains false, i.e. keep */
  		} else

@@ -348,7 +347,7 @@ static void xdl_trim_ends(xdfenv_t *xe)
  		size_t mph1 = xe->xdf1.recs[i].minimal_perfect_hash;
  		size_t mph2 = xe->xdf2.recs[i].minimal_perfect_hash;
  		if (mph1 != mph2) {
-			xe->xdf1.dstart = xe->xdf2.dstart = (ssize_t)i;
+			xe->delta_start = (ssize_t)i;
  			lim -= i;
  			break;
  		}

@@ -370,6 +369,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, xpparam_t const *xpp,
  		    xdfenv_t *xe) {
  	xdlclassifier_t cf;
 
+	xe->delta_start = 0;
+
  	if (xdl_prepare_ctx(mf1, &xe->xdf1, xpp->flags) < 0) {
 
  		return -1;

xdiff/xtypes.h +2 -1

index 979586f20a..bda1f85eb0 100644
@@ -48,7 +48,7 @@ typedef struct s_xrecord {
  typedef struct s_xdfile {
  	xrecord_t *recs;
  	size_t nrec;
-	ptrdiff_t dstart, dend;
+	ptrdiff_t dend;
  	bool *changed;
  	size_t *reference_index;
  	size_t nreff;

@@ -56,6 +56,7 @@ typedef struct s_xdfile {
 
  typedef struct s_xdfenv {
  	xdfile_t xdf1, xdf2;
+	size_t delta_start;
  } xdfenv_t;
 
 

Quoted 5 lines · Ezekiel Newren via GitGitGadget

From: Ezekiel Newren <[email protected]>

Placing delta_start in xdfenv_t instead of xdfile_t provides a more appropriate context since this variable only makes sense with a pair of files. View with --color-words.

So as dstart and dend must be the same for both files we now store the values once in xdfenv_t.

That explains why we start passing xdfenv_t around rather than xdfile_t in patch 5.

Thanks

Phillip

Quoted 135 lines

Signed-off-by Ezekiel Newren <[email protected]>

---
  xdiff/xhistogram.c |  4 ++--
  xdiff/xpatience.c  |  4 ++--
  xdiff/xprepare.c   | 17 +++++++++--------
  xdiff/xtypes.h     |  3 ++-

  4 files changed, 15 insertions(+), 13 deletions(-)

xdiff/xhistogram.c +2 -2

index 5ae1282c27..eb6a52d9ba 100644
@@ -365,6 +365,6 @@ out:
   int xdl_do_histogram_diff(xpparam_t const *xpp, xdfenv_t *env)
   {
       return histogram_diff(xpp, env,
-        env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
-        env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
+        env->delta_start + 1, env->xdf1.dend - env->delta_start + 1,
+        env->delta_start + 1, env->xdf2.dend - env->delta_start + 1);
   }

xdiff/xpatience.c +2 -2

index 2bce07cf48..bd0ffbb417 100644
@@ -374,6 +374,6 @@ static int patience_diff(xpparam_t const *xpp, 
 xdfenv_t *env,
   int xdl_do_patience_diff(xpparam_t const *xpp, xdfenv_t *env)
   {
       return patience_diff(xpp, env,
-        env->xdf1.dstart + 1, env->xdf1.dend - env->xdf1.dstart + 1,
-        env->xdf2.dstart + 1, env->xdf2.dend - env->xdf2.dstart + 1);
+        env->delta_start + 1, env->xdf1.dend - env->delta_start + 1,
+        env->delta_start + 1, env->xdf2.dend - env->delta_start + 1);

  }

xdiff/xprepare.c +1 -2

index 06b6a6f804..e88468e74c 100644
@@ -173,7 +173,6 @@ static int xdl_prepare_ctx(mmfile_t *mf, xdfile_t 
 *xdf, uint64_t flags) {
       xdf->changed += 1;
       xdf->nreff = 0;
-    xdf->dstart = 0;
       xdf->dend = xdf->nrec - 1;
       return 0;

@@ -287,7 +286,7 @@ static int xdl_cleanup_records(xdlclassifier_t 
 *cf, xdfenv_t *xe) {
        */
       if ((mlim = xdl_bogosqrt((long)xe->xdf1.nrec)) > XDL_MAX_EQLIMIT)
           mlim = XDL_MAX_EQLIMIT;
-    for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart]; 
 i <= xe->xdf1.dend; i++, recs++) {
+    for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start]; 
 i <= xe->xdf1.dend; i++, recs++) {

          rcrec = cf->rcrecs[recs->minimal_perfect_hash];
          nm = rcrec ? rcrec->len2 : 0;
          action1[i] = (nm == 0) ? DISCARD: (nm >= mlim && ! need_min) ? INVESTIGATE: KEEP;

xdiff/xprepare.c +1 -1

@@ -295,7 +294,7 @@ static int xdl_cleanup_records(xdlclassifier_t 
 *cf, xdfenv_t *xe) {
       if ((mlim = xdl_bogosqrt((long)xe->xdf2.nrec)) > XDL_MAX_EQLIMIT)
           mlim = XDL_MAX_EQLIMIT;
-    for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart]; 
 i <= xe->xdf2.dend; i++, recs++) {
+    for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start]; 
 i <= xe->xdf2.dend; i++, recs++) {
           rcrec = cf->rcrecs[recs->minimal_perfect_hash];

          nm = rcrec ? rcrec->len1 : 0;
          action2[i] = (nm == 0) ? DISCARD: (nm >= mlim && ! need_min) ? INVESTIGATE: KEEP;

xdiff/xprepare.c +1 -1

@@ -306,10 +305,10 @@ static int xdl_cleanup_records(xdlclassifier_t 
 *cf, xdfenv_t *xe) {
        * false, or become true.
        */
       xe->xdf1.nreff = 0;
-    for (i = xe->xdf1.dstart, recs = &xe->xdf1.recs[xe->xdf1.dstart];
+    for (i = xe->delta_start, recs = &xe->xdf1.recs[xe->delta_start];
            i <= xe->xdf1.dend; i++, recs++) {

          if (action1[i] == KEEP ||
-            (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->xdf1.dstart, xe->xdf1.dend))) {
+            (action1[i] == INVESTIGATE && !xdl_clean_mmatch(action1, i, xe->delta_start, xe->xdf1.dend))) { xe->xdf1.reference_index[xe->xdf1.nreff++] = i; /* changed[i] remains false, i.e. keep */
          } else

xdiff/xprepare.c +1 -1

@@ -318,10 +317,10 @@ static int xdl_cleanup_records(xdlclassifier_t 
 *cf, xdfenv_t *xe) {
       }
       xe->xdf2.nreff = 0;
-    for (i = xe->xdf2.dstart, recs = &xe->xdf2.recs[xe->xdf2.dstart];
+    for (i = xe->delta_start, recs = &xe->xdf2.recs[xe->delta_start];
            i <= xe->xdf2.dend; i++, recs++) {

          if (action2[i] == KEEP ||
-            (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->xdf2.dstart, xe->xdf2.dend))) {
+            (action2[i] == INVESTIGATE && !xdl_clean_mmatch(action2, i, xe->delta_start, xe->xdf2.dend))) { xe->xdf2.reference_index[xe->xdf2.nreff++] = i; /* changed[i] remains false, i.e. keep */
          } else

xdiff/xprepare.c +3 -1

@@ -348,7 +347,7 @@ static void xdl_trim_ends(xdfenv_t *xe)
           size_t mph1 = xe->xdf1.recs[i].minimal_perfect_hash;
           size_t mph2 = xe->xdf2.recs[i].minimal_perfect_hash;
           if (mph1 != mph2) {
-            xe->xdf1.dstart = xe->xdf2.dstart = (ssize_t)i;
+            xe->delta_start = (ssize_t)i;
               lim -= i;
               break;
           }

@@ -370,6 +369,8 @@ int xdl_prepare_env(mmfile_t *mf1, mmfile_t *mf2, 
 xpparam_t const *xpp,
               xdfenv_t *xe) {
       xdlclassifier_t cf;
+    xe->delta_start = 0;
+
       if (xdl_prepare_ctx(mf1, &xe->xdf1, xpp->flags) < 0) {
           return -1;

xdiff/xtypes.h +2 -1

index 979586f20a..bda1f85eb0 100644
@@ -48,7 +48,7 @@ typedef struct s_xrecord {
   typedef struct s_xdfile {
       xrecord_t *recs;
       size_t nrec;
-    ptrdiff_t dstart, dend;
+    ptrdiff_t dend;
       bool *changed;
       size_t *reference_index;
       size_t nreff;

@@ -56,6 +56,7 @@ typedef struct s_xdfile {
   typedef struct s_xdfenv {
       xdfile_t xdf1, xdf2;
+    size_t delta_start;
   } xdfenv_t;