Array support

[Bromeon]

Implement a richer API for arrays -- both Array (containing Variant) and TypedArray<T> (containing concrete types).

Inspiration can be found in gdnative::core_types::PoolArray, as well as Godot's Array documentation.

Some ideas, can also be implemented as separate pull requests:

1. Basic methods: insertion, removal, random access, etc.
2. Trait support: Index, IntoIterator, PartialEq, PartialOrd
   • ideally use impl_builtin_traits! for the "object relation" traits
3. Conversions, e.g. From<Vec<T>>, also between Array and TypedArray (one way fallible)
4. Godot special methods like shuffle(), get_typed_builtin(), ...
   • would be good to discuss this first
   • lots of Godot methods have a more idiomatic approach or name in Rust: slice(), size(), sort_custom(), ...

If possible, additions should be accompanied by unit tests. Rather less functionality but properly tested than feature-creep 🙂

[chitoyuu]

Note on Index: the trait requires a return value of an actual &T reference, and as such a sound implementation might not be possible. It isn't in Godot 3 at least. If you're trying to write one, make doubly sure that your lifetime assumptions are correct.

[Bromeon]

Very good point. If e.g. IndexMut dereference

array[i] *= 2

is not possible, we could think about a convenience function:

array.edit(i, |e| e *= 2);

[chitoyuu]

Not sure if this makes it the "conventional" Rust name for such functions, but that signature looks pretty similar to the unstable Cell::update method: https://doc.rust-lang.org/std/cell/struct.Cell.html#method.update

I'm not exactly convinced of the "returns the new value" part of the std function though. Of course it should be possible due to Variant being reference-counted, but I wonder if it's useful to begin with. The related issue might be interesting to read.

[Hanna-Kitten]

So, I am not very experienced in programming, rust, or Godot, but I want to have a go at this issue. What I lack in knowledge, I can make up for in that I have a lot of free time.

Can you give me some directions on how to get started? I run Fedora Workstation 37. I have cargo and godot installed.

This is my first attempt at contributing to a project, so any help is much appreciated ☺️

[chitoyuu]

@Hanna-Kitten I would suggest starting with the non-generic (Variant) array type if you aren't very experienced with Rust. All you need to write is a bunch of simple wrappers around FFI functions. The VariantArray implementation from GDNative Rust for example looks like this:

https://github.com/godot-rust/gdnative/blob/f9200001af5497bb99f5060bd6c5a97378c8ddf9/gdnative-core/src/core_types/variant_array.rs#L87-L102

You should expect some differences both in the definitions of the FFI functions themselves and in the internal APIs, but the basic idea is the same.

The generic ones require a lot more engineering to get right, so I wouldn't suggest that to a beginner.

[Hanna-Kitten]

@Hanna-Kitten I would suggest starting with the non-generic (Variant) array type if you aren't very experienced with Rust. All you need to write is a bunch of simple wrappers around FFI functions. The VariantArray implementation from GDNative Rust for example looks like this:

https://github.com/godot-rust/gdnative/blob/f9200001af5497bb99f5060bd6c5a97378c8ddf9/gdnative-core/src/core_types/variant_array.rs#L87-L102

You should expect some differences both in the definitions of the FFI functions themselves and in the internal APIs, but the basic idea is the same.

The generic ones require a lot more engineering to get right, so I wouldn't suggest that to a beginner.

@chitoyuu Thank you so much for your reply. I want to try writing some wrapper functions like you suggested, but I'm not sure what my first objective is.

What should be my first goal/thing to implement (please try to be specific)? With this info I could focus on that idea, and hopefully I can use that knowledge to implement other aspects of this feature set.

I'll need to read about rust/godot FFI/API too. I'm starting from zero in on these subjects. All code I've written to learn is self contained and single purposed and basic in nature.

[chitoyuu]

What should be my first goal/thing to implement (please try to be specific)? With this info I could focus on that idea, and hopefully I can use that knowledge to implement other aspects of this feature set.

Try running cargo doc on the godot-ffi crate, which I think should give you a listing of all the builtin functions in the GlobalMethodTable type. Look for any functions pertaining to the variant array type, and write wrappers for them if non-existent. If you need to prioritize, start with basic operations like pushing and removing elements.

Focus on the important things: you don't have to do everything all at once. It's likely that the internal API will see a lot of changes before any versioned release, anyway. It could be beneficial, even, to keep the surface small, so less need to be undone when (not if!) the time eventually comes.

I'll need to read about rust/godot FFI/API too. I'm starting from zero in on these subjects. All code I've written to learn is self contained and single purposed and basic in nature.

The Rustonomicon has some information on FFI, but most of the machinery is done for you, so you shouldn't have to worry too much about it. Just call any appropriate *_sys functions whenever you need to convert something from/to its Godot counterpart.

As for Godot FFI particularly, the bad news is that it's severely undocumented. Often you'll have to dig into the engine source code to see if something you want to do is really safe. When in doubt, avoid dealing with lifetimes.

[ttencate]

So we have a fully functional Array implementation now, which deals only in Variants. We also have a stub TypedArray<T> which is basically useless. Where to go from here?

Typed arrays in GDScript

GDScript 2.0 introduced the notion of "typed arrays", which are a very limited form of generics. An Array can now have a type assigned to it, at or shortly after construction (the refcount must be 1, and the array must be empty and not read-only).

This type consists of three parts:

1. a variant type (NIL is internally used to indicate an untyped array)
2. a class name (only for the OBJECT variant type)
3. a Script (which does not affect Rust typing so we'll ignore this)

Such a typed array is created in GDScript using a type annotation, and every attempt to put a value of the wrong type into it will log an error and continue as if it never happened:

var arr: Array[int] = [1, 2]
arr.push_back("hello") # Logs an error
print(arr)             # Prints [1, 2]

Remember that arrays are invariant, not covariant. A dog may be an animal, but an array of dogs is not an array of animals. GDScript violates this principle:

func add_a_string(strings: Array):
    strings.push_back("hello")

var arr: Array[int] = [1, 2]
add_a_string(arr) # This passes type checking.

Also keep in mind that all of the above is how it currently works; there is no spec or stability guarantee for GDScript.

Mapping this to Rust

There are basically three options.

1. Only variant arrays

The simplest approach would be to ignore the typing on arrays altogether. gdnative has only VariantArray, and it doesn't seem too bad.

The only problem is that a typed array (which Godot 3 and thus gdnative doesn't have) is not a variant array, since arrays are not covariant. So even though the API reflects type-unsafety, it doesn't reflect all of the type-unsafety, and some operations (such as push_back) can fail without being able to detect this from Rust.

We can work around that by explicitly type-checking everything that goes into the array, so that we can handle type errors before they get to Godot. Sadly, Godot will then just repeat the same check again. We would need to ensure (now and in the future) that our check is implemented in exactly the same way.

2. Variant and typed arrays

It would make sense to encode the runtime type of the array as a compile-type generic argument in Rust: TypedArray<T>, where T: VariantMetadata + FromVariant + ToVariant. Since Variant also implements all these, TypedArray<Variant> can be used to mean "untyped array".

The challenge is to make sure that the runtime type of the array always matches T. If the array is created from Rust, this is easy: we just set the type upon creation. But if it's passed in from Godot, it's trickier. The API JSON specifies typedarray::T for arrays of type T, but it's not clear what this means. Does it only contain Ts, or is it also typed? Note to self: find the answer.

There is also a problem with nested arrays. In Rust, we can write TypedArray<TypedArray<T>>. But in Godot the type system is not recursive: the outer array would be typed as containing the ARRAY variant type without recording T anywhere. This creates a loophole where we can get a TypedArray<T> of the wrong type:

var inner: Array[String] = ["The answer is:"]
var arr: Array[Array] = [inner]
obj.push_answer_to_first(arr)

#[func]
fn push_answer_to_first(arr: TypedArray<TypedArray<i64>>) {
    arr.get(0)
       .push(42); // Whoops! Looks safe, but Godot prints an error, and nothing else happens.
}

Since get doesn't return a Result, the only choice we have is to panic when the conversion from Variant fails despite the seemingly safe typing:

#[func]
fn push_answer_to_first(arr: TypedArray<TypedArray<i64>>) {
    arr.get(0) // Unexpected panic! Expected array of INT, got array of STRING.
       .push(42);
}

3. Variant, typed and unknown arrays

To avoid the above scenario, we could create a third type of array, the UnknownArray. The only operation you can do with it is a checked conversion to TypedArray<T> or VariantArray.

Instead of T: VariantMetadata we would have T: ArrayElement, where ArrayElement is implemented for the same types as VariantMetadata except for arrays. There, it's only implemented for UnknownArray. This would make TypedArray<TypedArray<T>> impossible at compile time; you'd have to write TypedArray<UnknownArray> and explicitly convert each element to a TypedArray<i64>.

There are no more unexpected panics, but the drawback is, of course, more boilerplate when working with nested arrays:

#[func]
fn push_answer_to_first(arr: TypedArray<UnknownArray>) {
    arr.get(0)
       .try_to_typed::<i64>()
       .unwrap() // Panic! But that's what you expect from unwrap()!
       .push(42);
}

I don't think this edge case is worth the extra complexity though.

[ttencate]

A few cleanup actions remain once #101 is merged:

• Rename Array → VariantArray and TypedArray → Array
• Add generics support to impl_builtin_froms! and use it to DRY up array.rs
• Check whether the From<Packed*Array> functions actually return typed arrays, and adjust if needed
• Implement PartialEq and PartialOrd on Packed*Array types, and also Eq and Ord where appropriate (need to check Godot's NaN handling)
• Use this to fix a TODO in array_test.rs

[ttencate]

A generic impl_builtin_froms! declarative macro is not going to fly. I tried:

macro_rules! impl_builtin_traits {
    (
        for $Type:ident $( < $T:ident > )?
        $( where ( $($where:tt)* ) )? // Parentheses required for parsing disambiguation.
        {
            $( $Trait:ident => $gd_method:ident; )*
        }
    ) => (
        $(
            impl_builtin_traits_inner! {
                $Trait for $Type $(< $T >)? $( where ( $($where:tt)* ) )? => $gd_method
            }
        )*
    )
}

The generic arguments need to be repeated for each inner macro invocation, but such "nested loops" are not supported in declarative macros:

error: meta-variable `Trait` repeats 3 times, but `T` repeats 1 time

If we want this, I think we'll need to resort to a procedural macro. Maybe even support something like #[derive_ffi(Drop => array_destroy, PartialEq => array_operator_equal)].

[Bromeon]

Following the previous proposal, a new idea came up in a Discord discussion.

The core observation is that arrays are still convariant when looking at read operations.
In other words, converting Array<T> -> Array<Variant> is safe as long as no one tries to write to the latter.

As a consequence, instead of UnknownArray, we could provide ReadOnlyArray (name to be defined) as the "common base". This would still provide all read operations just like Array<Variant>. However, it could be "downcast" to a concrete array Array<T> (with T including Variant).

---

Brainstorming:

1. Polymorphism could be allowed as follows, similar to Gd + Inherits:

   fn accept_array<A: ToReadArray>(array: A) {
       let array: ReadOnlyArray = array.read_only(); // upcast
       ...
   }

2. We might consider implementing Deref. DerefMut is likely not needed, as such I'd expect less problems.

3. GDScript allows implicit upcasting:

   func accept_array(a: Array) -> void:
       ...
   
   var a: Array[int] = ...
   accept_array(a)

   However, Rust code needs to forbid this, both inside Rust and on the boundary. So if a #[func] expects VariantArray, it must not accept typed arrays. Otherwise, ReadOnlyArray can be used.

4. We can't use Box<dyn ReadOnlyTrait>, because Box::downcast() is not generic, but defined on a concrete type. And in general, we may want to exploit the 3 array type-states having the same repr and lazy instantiation of the concrete array (only on downcast, not on creation).

[ttencate]

Found a bug on our end: this check is not actually called when calling a #[func] that takes a TypedArray. So we currently allow implicit upcasting¹ too, just like GDScript :)

---

That aside, let me try to understand your proposal:

fn accept_array<A: ToReadArray>(array: A) {
    let array: ReadOnlyArray = array.read_only(); // upcast
    ...
}

Why is there a generic there? Is it for calling accept_array from Rust in cases where you already have a TypedArray in hand?

• If so, how would we prevent calling it with the wrong type of array from Rust, since the type of elements is not in the function signature?

• If not, it's for calling this from GDScript. But then how would the FFI machinery infer the concrete type of A? It could look at the runtime type of the incoming array, and decide between A = UntypedArray and A = TypedArray<T>, but if the only operation on the ToReadArray trait is to cast it to a ReadOnlyArray that doesn't carry any generic type information, we don't gain any safety by creating a TypedArray in the first place. We might then as well write:

  #[func]
  fn accept_array(array: ReadOnlyArray) {
      ...
  }

---

¹ Since arrays are not covariant, it's not really upcasting, it's a conversion between two disjoint types, not unlike a transmute in Rust.

[Bromeon]

Found a bug on our end: this check is not actually called when calling a #[func] that takes a TypedArray. So we currently allow implicit upcasting¹ too, just like GDScript :)

Good catch. I think the whole binding interface should be hardened, I created #125 to track it.

---

That aside, let me try to understand your proposal:

fn accept_array<A: ToReadArray>(array: A) {
    let array: ReadOnlyArray = array.read_only(); // upcast
    ...
}

Why is there a generic there? Is it for calling accept_array from Rust in cases where you already have a TypedArray in hand?

Sorry for confusion, the ToReadArray would be a very simple trait like ToVariant:

// forget about naming
trait ToReadArray {
   fn read_only() -> ReadOnlyArray;
}

So it would not offer any functionality on its own, but allow converting/"upcasting".

Why not a ReadArray trait? Because that would require us to store Box<dyn ReadArray> for owned polymorphism, which doesn't fit layout-wise and cannot even be downcast properly. Instead, a dedicated ReadOnlyArray struct is more flexible.

[ttencate]

I think a full code example would be helpful to flesh this out. All the type definitions involved, as well as a basic example use case.

[ttencate]

@Bromeon I think this can be closed now, since you did #151. We can create new issues for specific changes as needed.

[Bromeon]

Agree, thanks for the reminder! And huge thanks for contributing so much to array support! 👍