reduz/structs.cpp

## structs.cpp
// The idea of this proposal is that we can solve these following problems:

//* Add struct support to GDScript (this has some user demand, given classes are quite heavy resource wise)
//* Add limited struct support to the Godot API, so we avoid exposing things as dictionaries in the API, which are unfriendly (no code completion, no doc)
//* As a plus, have a way to have optimized, flat memory arrays of these structs. this allows much higher performance in GDScript when dealing with thousands of elements (as in, bullet hell). We know we can use multimesh to accelerate drawing (or the new APIs in Godot 3 for drawing which are more optimized), but storing logical data for processing all these is still inefficient cache wise.

//In GDScript, structs should look very simple:

struct MyStruct:
	var a : String
	var b : int
	var c # untyped should work too


// When this is instantiated and used, it actually is an Array internally. This makes everything far, far simpler.

// But we know we want to use this in C++ too, as an example:

STRUCT_LAYOUT( ProperyInfoLayout, STRUCT_MEMBER("name", Variant::STRING), STRUCT_MEMBER("type", Variant::INT), STRUCT_MEMBER("hint", Variant::INT), STRUCT_MEMBER("hint_string", Variant::STRING), STRUCT_MEMBER("class_name", Variant::STRING) );

// .. //

class Object {

//..//

// script bindings:
// Instead of
TYpedArray<Dictionary> _get_property_list();
// which we have now, we want to use:
TypedArray<Struct<ProperyInfoLayout>> _get_property_list();
// This gives us nice documentation and code completion.
//..//
}

////////////IMPLEMENTATION/////////////

// Implementation in Array

// ArrayPrivate needs to be changed:

class ArrayPrivate {
public:
	SafeRefCount refcount;
	Vector<Variant> array;
	Variant *read_only = nullptr; // If enabled, a pointer is used to a temporary value that is used to return read-only values.
	ContainerTypeValidate typed;

	// Added struct stuff:
	uint32_t struct_size = 0;
	StringName * struct_member_names = nullptr;
	ContainerTypeValidate * struct_member_types = nullptr;

	_FORCE_INLINE_ bool is_struct() const {
		return struct_size > 0;
	}

	_FORCE_INLINE_ int32_t find_member_index(const StringName& p_member) const {
		for(uint32_t i = 0 ; i<struct_size ; i++) {
			if (p_member == struct_member_names[i]) {
				return (int32_t)i;
			}
		}

		return -1;
	}

	_FORCE_INLINE_ bool validate_member(uint32_t p_index,const Variant& p_value) {
		// needs to check with ContainerValidate, return true is valid
	}

};

// Not using LocalVector and resorting to manual memory allocation to improve on resoure usage and performance.

// Then, besides all the type comparison and checking (leave this to someone else to do)
// Array needs to implement set and get named functions:


Variant Array::get_named(const StringName& p_member) const {
	ERR_FAIL_COND_V(!_p->is_struct(),Variant();
	int32_t offset = _p->find_member_index(p_member);
	ERR_FAIL_INDEX_V(offset,_p->array.size(),Variant());
	return _p->array[offset];
}

void Array::set_named(const StringName& p_member,const Variant& p_value) {
	ERR_FAIL_COND(!_p->is_struct());
	int32_t offset = _p->find_member_index(p_member);
	ERR_FAIL_INDEX(offset,_p->array.size());
	ERR_FAIL_COND(!p->validate_member(p_value);
	_p->array[offset].write[offset]=p_value;
}

// These can be exposed in Variant binder so they support named indexing
// Keep in mind some extra versions with validation that return invalid set/get will need to be added for GDScript to properly throw errors

// Additionally, the Array::set needs to also perform validation if this is a struct.


// ARRAYS OF STRUCTS
// We may also want to have an array of structs, the goal is when users needs to store data for a huge amount of elements (like lots of bullets) doing
// so in flat memory fashion is a lot more efficient cache wise. Keep in mind that because variants re always 24 bytes in size, there will always be some
// memory wasting, specially if you use many floats. Additionally larger types like Transform3D are allocated separately because they don't
// fit in a Variant, but they have their own memory pools where they will most likely be allocated contiguously too.
// To sump up, this is not as fast as using C structs memory wise, but still orders of magnitude faster and more efficient than
// using regular arrays.


// Doing this in GDScript:
var a = Array[StructType]
// ..//
a[5].member = 819

// And it will be expected to work. But this is still a regular array of structs and is not contiguous in memory (and its expected).
// The idea is that this flat struct array is a special case that users only use when they have a very large amount of elements (like thousands).
// So it will need a bit of a different syntax when you want performance (WHICH AGAIN IT IS A VERY RARE USE CASE, MOST USERS WILL NOT KNOW NOR THEY NEED TO LNOW THIS EXISTS BECAUSE IT WILL __NOT__ BENEFIT THEM):
//

var a = StructType()
a.resize_structs(55) // fails if not a struct, of course
print(a.structs_size()) // 1 for single structs
a.struct_at(5).member = 819

// Your brain is likely puzzled here, so lets do a FAQ
// FAQ:
// Q: IT IS WONKY
// A: BUT THIS IS GOOD.
//
// Q: Can we not make the syntax the same for this case and the regular array struct and compiler infers by type?
// A: No, because for untyped code this is just an array, and the syntax just has to work
//
// Q: Can we add some kind of specialized syntax like a[index, member] ?
// A: I think adding this syntax just for this use case would probably be horrible and confusing to users?
//
// Q: I hate it, can we do something?
// A: I think ultimately this is good because you have to mentalize that 99.99% of use cases, users will not use this syntax. This is very specific and custom syntax that you only have to use when you have huge (and I mean realy huge, dozens of thousands) arrays of structs and you need performance.
//   As such, I think its good users don't use or abuse this syntax unnecesarily, thinking it has more performance or something like that.
//   Even if we could make a nicer syntax, users would not know what to use, and they are obviously incompatible (in this second case, you can't pass
//   A struct as an argument, it would need to be re-constructed and you would be operating on copies. Its just more lose than win.

// So how this last thing work?
// The idea is to add a member to the Array class (not ArrayPrivate):

class Array {
	mutable ArrayPrivate *_p;
	void _unref() const;
	uint32_t struct_offset = 0; // Add this
public:

// And the functions described above actually are implemented like this:

Variant Array::get_named(const StringName& p_member) const {
	ERR_FAIL_COND_V(!_p->struct_layout.is_struct(),Variant();
	int32_t offset = _p->find_member_index(p_member);
	offset += struct_offset * _p->struct_size;
	ERR_FAIL_INDEX_V(offset,_p->array.size(),Variant());
	return _p->array[offset];
}

void Array::set_named(const StringName& p_member,const Variant& p_value) {
	ERR_FAIL_COND(!_p->struct_layout.is_struct());
	int32_t offset = _p->find_member_index(p_member);
	ERR_FAIL_COND(!p->validate_member(p_value);
	offset += struct_offset * _p->struct_size;
	ERR_FAIL_INDEX(offset,_p->array.size());
	_p->array[offset].write[offset]=p_value;
}

Array Array::struct_at(int p_index) const {
	ERR_FAIL_COND_V(!_p->struct_layout.is_struct(),Array());
	ERR_FAIL_INDEX_V(p_index,_p->array.size() / _p->struct_layout.get_member_count(),Array())
	Array copy = *this;
	copy.struct_offset = p_index;
	return copy;
}


// TYPE DESCRIPTIONS in C++

// Another problem we will face with this approach is that there are many cases where we will want to actually describe the type.
// If we had a function that returned a dictionary and now we want to change it to a struct because its easier for the user to use (description in doc, autocomplete in GDScript, etc) we must find a way. As an example for typed arrays we have:

TypedArray<Type> get_someting() const;

// And the binder takes care. Ideally we want to be able to do something like:

Struct<StructLayout> get_someting() const;

// We know we want to eventually do things like like this exposed to the binder.

TypedArray<Struct<PropertyInfoLayout>> get_property_list();

// So what are Struct and StructLayout?

//We would like to do PropertyInfoLayout like this:


STRUCT_LAYOUT( ProperyInfo, STRUCT_MEMBER("name", Variant::STRING), STRUCT_MEMBER("type", Variant::INT), STRUCT_MEMBER("hint", Variant::INT), STRUCT_MEMBER("hint_string", Variant::STRING), STRUCT_MEMBER("class_name", Variant::STRING) );

// How does this convert to C?

// Here is a rough sketch
struct StructMember {
	StringName name;
	Variant:Type type;
	StringName class_name;

	StructMember(const StringName& p_name, const Variant::Type p_type, const StringName& p_class_name = StringName()) { name = p_name; type=p_type; class_name = p_class_name; }
};

// Important so we force SNAME to it, otherwise this will be leaked memory
#define STRUCT_MEMBER(m_name,m_type) StructMember(SNAME(m_name),m_type)
#define STRUCT_CLASS_MEMBER(m_name,m_class) StructMember(SNAME(m_name),Variant::OBJECT,m_class)


// StructLayout should ideally be something that we can define like


#define STRUCT_LAYOUT(m_name,...) \
struct m_name { \
	static constexpr uint32_t member_count = GET_ARGUMENT_COUNT;\
	_FORCE_INLINE_ static const StructMember& get_member(uint32_t p_index) {\
		CRASH_BAD_INDEX(p_index,member_count)\
		static StructMember members[member_count]={ __VA_ARGS__ };\
		return members[p_index];\
	}\
};

// Note GET_ARGUMENT_COUNT is a macro that we probably need to add tp typedefs.h, see:
// https://stackoverflow.com/questions/2124339/c-preprocessor-va-args-number-of-arguments

// Okay, so what is Struct<> ?

// Its a similar class to TypedArray


template <class T>
class Struct : public Array {
public:
	typedef Type T;

	_FORCE_INLINE_ void operator=(const Array &p_array) {
		ERR_FAIL_COND_MSG(!is_same_typed(p_array), "Cannot assign a Struct from array with a different format.");
		_ref(p_array);
	}
	_FORCE_INLINE_ Struct(const Variant &p_variant) :
			Array(T::member_count, T::get_member,Array(p_variant)) {
	}
	_FORCE_INLINE_ Struct(const Array &p_array) :
			Array(T::member_count, T::get_member,p_array) {
	}
	_FORCE_INLINE_ Struct() {
			Array(T::member_count, T::get_member) {
	}
};

// You likely saw correctly, we pass pointer to T::get_member. This is because we can't pass a structure and we want to initialize ArrayPRivate efficiently without allocating extra memory than needed, plus we want to keep this function around for validation:

Array::Array(uint32_t p_member_count, const StructMember& (*p_get_member)(uint32_t));
Array::Array(uint32_t p_member_count, const StructMember& (*p_get_member)(uint32_t),const Array &p_from); // separate one is best for performance since Array() does internal memory allocation when constructed.

// Keep in mind also that GDScript VM is not able to pass a function pointer since this is dynamic, so it will need a separate constructor to initialize the array format. Same reason why the function pointer should not be kept inside of Array.
// Likewise, GDScript may also need to pass a Script for class name, which is what ContainerTypeValidate neeeds.


// Optimizations:

// The idea here is that if GDScript code is typed, it should be able to access everything without any kind of validation or even copies. I will add this in the GDScript optimization proposal I have soon (pointer addressing mode).

// That said, I think we should consider changing ArrayPrivate::Array from Vector to LocalVector, this should enormously improve performance when accessing untyped (And eventually typed) arrays in GDScript. Arrays are shared, so there is not much of a need to use Vector<> here.
	// The idea of this proposal is that we can solve these following problems:

	//* Add struct support to GDScript (this has some user demand, given classes are quite heavy resource wise)
	//* Add limited struct support to the Godot API, so we avoid exposing things as dictionaries in the API, which are unfriendly (no code completion, no doc)
	//* As a plus, have a way to have optimized, flat memory arrays of these structs. this allows much higher performance in GDScript when dealing with thousands of elements (as in, bullet hell). We know we can use multimesh to accelerate drawing (or the new APIs in Godot 3 for drawing which are more optimized), but storing logical data for processing all these is still inefficient cache wise.

	//In GDScript, structs should look very simple:

	struct MyStruct:
	var a : String
	var b : int
	var c # untyped should work too


	// When this is instantiated and used, it actually is an Array internally. This makes everything far, far simpler.

	// But we know we want to use this in C++ too, as an example:

	STRUCT_LAYOUT( ProperyInfoLayout, STRUCT_MEMBER("name", Variant::STRING), STRUCT_MEMBER("type", Variant::INT), STRUCT_MEMBER("hint", Variant::INT), STRUCT_MEMBER("hint_string", Variant::STRING), STRUCT_MEMBER("class_name", Variant::STRING) );

	// .. //

	class Object {

	//..//

	// script bindings:
	// Instead of
	TYpedArray<Dictionary> _get_property_list();
	// which we have now, we want to use:
	TypedArray<Struct<ProperyInfoLayout>> _get_property_list();
	// This gives us nice documentation and code completion.
	//..//
	}

	////////////IMPLEMENTATION/////////////

	// Implementation in Array

	// ArrayPrivate needs to be changed:

	class ArrayPrivate {
	public:
	SafeRefCount refcount;
	Vector<Variant> array;
	Variant *read_only = nullptr; // If enabled, a pointer is used to a temporary value that is used to return read-only values.
	ContainerTypeValidate typed;

	// Added struct stuff:
	uint32_t struct_size = 0;
	StringName * struct_member_names = nullptr;
	ContainerTypeValidate * struct_member_types = nullptr;

	_FORCE_INLINE_ bool is_struct() const {
	return struct_size > 0;
	}

	_FORCE_INLINE_ int32_t find_member_index(const StringName& p_member) const {
	for(uint32_t i = 0 ; i<struct_size ; i++) {
	if (p_member == struct_member_names[i]) {
	return (int32_t)i;
	}
	}

	return -1;
	}

	_FORCE_INLINE_ bool validate_member(uint32_t p_index,const Variant& p_value) {
	// needs to check with ContainerValidate, return true is valid
	}

	};

	// Not using LocalVector and resorting to manual memory allocation to improve on resoure usage and performance.

	// Then, besides all the type comparison and checking (leave this to someone else to do)
	// Array needs to implement set and get named functions:


	Variant Array::get_named(const StringName& p_member) const {
	ERR_FAIL_COND_V(!_p->is_struct(),Variant();
	int32_t offset = _p->find_member_index(p_member);
	ERR_FAIL_INDEX_V(offset,_p->array.size(),Variant());
	return _p->array[offset];
	}

	void Array::set_named(const StringName& p_member,const Variant& p_value) {
	ERR_FAIL_COND(!_p->is_struct());
	int32_t offset = _p->find_member_index(p_member);
	ERR_FAIL_INDEX(offset,_p->array.size());
	ERR_FAIL_COND(!p->validate_member(p_value);
	_p->array[offset].write[offset]=p_value;
	}

	// These can be exposed in Variant binder so they support named indexing
	// Keep in mind some extra versions with validation that return invalid set/get will need to be added for GDScript to properly throw errors

	// Additionally, the Array::set needs to also perform validation if this is a struct.


	// ARRAYS OF STRUCTS
	// We may also want to have an array of structs, the goal is when users needs to store data for a huge amount of elements (like lots of bullets) doing
	// so in flat memory fashion is a lot more efficient cache wise. Keep in mind that because variants re always 24 bytes in size, there will always be some
	// memory wasting, specially if you use many floats. Additionally larger types like Transform3D are allocated separately because they don't
	// fit in a Variant, but they have their own memory pools where they will most likely be allocated contiguously too.
	// To sump up, this is not as fast as using C structs memory wise, but still orders of magnitude faster and more efficient than
	// using regular arrays.


	// Doing this in GDScript:
	var a = Array[StructType]
	// ..//
	a[5].member = 819

	// And it will be expected to work. But this is still a regular array of structs and is not contiguous in memory (and its expected).
	// The idea is that this flat struct array is a special case that users only use when they have a very large amount of elements (like thousands).
	// So it will need a bit of a different syntax when you want performance (WHICH AGAIN IT IS A VERY RARE USE CASE, MOST USERS WILL NOT KNOW NOR THEY NEED TO LNOW THIS EXISTS BECAUSE IT WILL __NOT__ BENEFIT THEM):
	//

	var a = StructType()
	a.resize_structs(55) // fails if not a struct, of course
	print(a.structs_size()) // 1 for single structs
	a.struct_at(5).member = 819

	// Your brain is likely puzzled here, so lets do a FAQ
	// FAQ:
	// Q: IT IS WONKY
	// A: BUT THIS IS GOOD.
	//
	// Q: Can we not make the syntax the same for this case and the regular array struct and compiler infers by type?
	// A: No, because for untyped code this is just an array, and the syntax just has to work
	//
	// Q: Can we add some kind of specialized syntax like a[index, member] ?
	// A: I think adding this syntax just for this use case would probably be horrible and confusing to users?
	//
	// Q: I hate it, can we do something?
	// A: I think ultimately this is good because you have to mentalize that 99.99% of use cases, users will not use this syntax. This is very specific and custom syntax that you only have to use when you have huge (and I mean realy huge, dozens of thousands) arrays of structs and you need performance.
	// As such, I think its good users don't use or abuse this syntax unnecesarily, thinking it has more performance or something like that.
	// Even if we could make a nicer syntax, users would not know what to use, and they are obviously incompatible (in this second case, you can't pass
	// A struct as an argument, it would need to be re-constructed and you would be operating on copies. Its just more lose than win.

	// So how this last thing work?
	// The idea is to add a member to the Array class (not ArrayPrivate):

	class Array {
	mutable ArrayPrivate *_p;
	void _unref() const;
	uint32_t struct_offset = 0; // Add this
	public:

	// And the functions described above actually are implemented like this:

	Variant Array::get_named(const StringName& p_member) const {
	ERR_FAIL_COND_V(!_p->struct_layout.is_struct(),Variant();
	int32_t offset = _p->find_member_index(p_member);
	offset += struct_offset * _p->struct_size;
	ERR_FAIL_INDEX_V(offset,_p->array.size(),Variant());
	return _p->array[offset];
	}

	void Array::set_named(const StringName& p_member,const Variant& p_value) {
	ERR_FAIL_COND(!_p->struct_layout.is_struct());
	int32_t offset = _p->find_member_index(p_member);
	ERR_FAIL_COND(!p->validate_member(p_value);
	offset += struct_offset * _p->struct_size;
	ERR_FAIL_INDEX(offset,_p->array.size());
	_p->array[offset].write[offset]=p_value;
	}

	Array Array::struct_at(int p_index) const {
	ERR_FAIL_COND_V(!_p->struct_layout.is_struct(),Array());
	ERR_FAIL_INDEX_V(p_index,_p->array.size() / _p->struct_layout.get_member_count(),Array())
	Array copy = *this;
	copy.struct_offset = p_index;
	return copy;
	}


	// TYPE DESCRIPTIONS in C++

	// Another problem we will face with this approach is that there are many cases where we will want to actually describe the type.
	// If we had a function that returned a dictionary and now we want to change it to a struct because its easier for the user to use (description in doc, autocomplete in GDScript, etc) we must find a way. As an example for typed arrays we have:

	TypedArray<Type> get_someting() const;

	// And the binder takes care. Ideally we want to be able to do something like:

	Struct<StructLayout> get_someting() const;

	// We know we want to eventually do things like like this exposed to the binder.

	TypedArray<Struct<PropertyInfoLayout>> get_property_list();

	// So what are Struct and StructLayout?

	//We would like to do PropertyInfoLayout like this:


	STRUCT_LAYOUT( ProperyInfo, STRUCT_MEMBER("name", Variant::STRING), STRUCT_MEMBER("type", Variant::INT), STRUCT_MEMBER("hint", Variant::INT), STRUCT_MEMBER("hint_string", Variant::STRING), STRUCT_MEMBER("class_name", Variant::STRING) );

	// How does this convert to C?

	// Here is a rough sketch
	struct StructMember {
	StringName name;
	Variant:Type type;
	StringName class_name;

	StructMember(const StringName& p_name, const Variant::Type p_type, const StringName& p_class_name = StringName()) { name = p_name; type=p_type; class_name = p_class_name; }
	};

	// Important so we force SNAME to it, otherwise this will be leaked memory
	#define STRUCT_MEMBER(m_name,m_type) StructMember(SNAME(m_name),m_type)
	#define STRUCT_CLASS_MEMBER(m_name,m_class) StructMember(SNAME(m_name),Variant::OBJECT,m_class)


	// StructLayout should ideally be something that we can define like


	#define STRUCT_LAYOUT(m_name,...) \
	struct m_name { \
	static constexpr uint32_t member_count = GET_ARGUMENT_COUNT;\
	_FORCE_INLINE_ static const StructMember& get_member(uint32_t p_index) {\
	CRASH_BAD_INDEX(p_index,member_count)\
	static StructMember members[member_count]={ __VA_ARGS__ };\
	return members[p_index];\
	}\
	};

	// Note GET_ARGUMENT_COUNT is a macro that we probably need to add tp typedefs.h, see:
	// https://stackoverflow.com/questions/2124339/c-preprocessor-va-args-number-of-arguments

	// Okay, so what is Struct<> ?

	// Its a similar class to TypedArray


	template <class T>
	class Struct : public Array {
	public:
	typedef Type T;

	_FORCE_INLINE_ void operator=(const Array &p_array) {
	ERR_FAIL_COND_MSG(!is_same_typed(p_array), "Cannot assign a Struct from array with a different format.");
	_ref(p_array);
	}
	_FORCE_INLINE_ Struct(const Variant &p_variant) :
	Array(T::member_count, T::get_member,Array(p_variant)) {
	}
	_FORCE_INLINE_ Struct(const Array &p_array) :
	Array(T::member_count, T::get_member,p_array) {
	}
	_FORCE_INLINE_ Struct() {
	Array(T::member_count, T::get_member) {
	}
	};

	// You likely saw correctly, we pass pointer to T::get_member. This is because we can't pass a structure and we want to initialize ArrayPRivate efficiently without allocating extra memory than needed, plus we want to keep this function around for validation:

	Array::Array(uint32_t p_member_count, const StructMember& (*p_get_member)(uint32_t));
	Array::Array(uint32_t p_member_count, const StructMember& (*p_get_member)(uint32_t),const Array &p_from); // separate one is best for performance since Array() does internal memory allocation when constructed.

	// Keep in mind also that GDScript VM is not able to pass a function pointer since this is dynamic, so it will need a separate constructor to initialize the array format. Same reason why the function pointer should not be kept inside of Array.
	// Likewise, GDScript may also need to pass a Script for class name, which is what ContainerTypeValidate neeeds.


	// Optimizations:

	// The idea here is that if GDScript code is typed, it should be able to access everything without any kind of validation or even copies. I will add this in the GDScript optimization proposal I have soon (pointer addressing mode).

	// That said, I think we should consider changing ArrayPrivate::Array from Vector to LocalVector, this should enormously improve performance when accessing untyped (And eventually typed) arrays in GDScript. Arrays are shared, so there is not much of a need to use Vector<> here.