Add extendable collections to GDScript

[DaloLorn]

Describe the project you are working on

A 2D tactical game with an overcomplicated data model, because I wanted to be able to do too many things in the singleplayer campaign. 😬

Describe the problem or limitation you are having in your project

We've had typed arrays for... what, almost a year now? By this time next year, chances are we'll also have typed dictionaries via #56, and if #782 were implemented, that would seem to add optional strong typing to every collection or collection-like object in GDScript. And if we get #6416, who could stop us? 😂

Yet, the type system still feels a little immature compared to other languages offering typed collections:

1. Classes and methods must be written as either fully typeless, or be tightly bound to a specific class (or trait, as the case may become). (Duplicate of #1207, I only figured it out just now while reading @AlbertoRota's comment.)
2. Collections cannot have any contextual understanding of what they hold and how to work with it. This lack of context - this inability to be given context - results in more fragile code, dependent on the programmers both understanding the context and correctly working in that context every time they touch the collection.

Describe the feature / enhancement and how it helps to overcome the problem or limitation

Overriding the inner logic of a collection allows you to optimize them for a specific purpose, or ensure that a certain process is absolutely always followed when performing certain operations on that collection. For instance, an Array whose values need to always be sorted could have the insert(), push_back(), and push_front() methods call sort() every time, instead of requiring the caller to remember to do it every time they're adding values to the array.

Describe how your proposal will work, with code, pseudo-code, mock-ups, and/or diagrams

This is probably purely syntactic sugar: Collections are probably too different from objects to be extended, and providing core support for their extension would come at a performance cost. However, an object "extending" a collection could offer transparent access to that collection and its functions, much like an object extending another object offers transparent access to the original object's properties and functions. (With, of course, the same ability to override those functions. Overriding the collection itself might be... heh, tricky, not to mention redundant.)

An example SortedArray class:

class_name SortedArray
extends Array

func push_back(value: Variant):
    super(value)
    sort()

func push_front(value: Variant):
    super(value)
    sort()

func insert(position: int, value: Variant):
    super(position, value)
    sort()

If this enhancement will not be used often, can it be worked around with a few lines of script?

Sort of, and I almost already do it at one point. (Not quite, because my script does something slightly more complicated requiring two arrays and some other stuff... but almost!) You can write a class that owns a collection, and you can either have consumers access the collection directly, or expose wrappers for all its functions (but not its operators, because we can't define custom operators - material for another proposal, perhaps? 🤔) if you so desire.

It's needlessly clunky and verbose, and there's a perpetual risk that someone will fail to use your wrappers properly in favor of directly accessing the wrapped collection.

Is there a reason why this should be core and not an add-on in the asset library?

It is fundamentally an expansion of GDScript's syntax. I don't think it can be done by addons.

[ryanabx]

There are two proposals in one here, but I'd like to address the first one.

I think that generics would be a wonderful addition to GDScript, mainly in the spirit of making collections more recursive. Currently nested typed collections are not supported. If generics are implemented, I would want to also rectify this issue.

As for the syntax of generics, I propose the angle bracket syntax similar to C#

# my_list.gd
class_name MyList<T>

func append(item: T) -> void:
    # implementation...

# other_class.gd
class_name OtherClass

var list: MyList<int> = MyList<int>.new()

func add_item(element: int):
    list.add(element)

I also think that typed arrays (regardless of whether they eventually support nesting) should have the generic syntax optional to them (we would keep the [] syntax to avoid breaking compatibility)

var typed_array1: Array<int> = [5, 3, 2] # Valid

var typed_array2: Array[int] = [2, 3, 5] # Also valid

[dalexeev]

Currently, nested array types are not supported at the core level. This would be much easier to implement if we supported first class types (a type that represents a type), but these are too big core changes, I doubt that this will be feasible in the near future.

• See also #6502.

[DaloLorn]

I'm not sure how nested typed collections are relevant here? But yes, a solution that incorporated them would probably be preferable if possible...

[ryanabx]

I'm not sure how nested typed collections are relevant here? But yes, a solution that incorporated them would probably be preferable if possible...

They're only relevant if you'd like to extend typed arrays. Currently, typed collections are not "generics" per se, rather each base type an array could have is explicitly implemented, including TypedArray

[DaloLorn]

So what would be stopping one from making a class that extends TypedArray? 😕

As I see it, extendable collections are basically just syntactic sugar, a less verbose form of something like this:

class_name IntArrayWithMetadata

var arr: Array[int]
var metadata: String

func push_back(value: int):
  arr.push_back(value)
  metadata += "added %d" % value

func pop_back() -> int:
  return arr.pop_back()

# Insert a bunch of other wrappers for arr's functions here,
# or assume the consumer will just access arr directly when it needs anything fancier.

This could be simplified down, purely on the syntactic level, to:

class_name IntArrayWithMetadata
extends Array[int]

var metadata

func push_back(value: int):
  super(value)
  metadata += "added %d" % value

Likewise, accessing it could be simplified from array_with_metadata.arr[index] to array_with_metadata[index].

It's a stupid and entirely meaningless example, but I think it gets the point across.

[dalexeev]

Typed arrays are not syntactic sugar. They check the type when adding an element at runtime. The current implementation does not support nested types. We could hardcode the nesting level for types like Array[Array[ ... Array[T] ... ]], but this will not work with typed dictionaries when we add them. In my opinion, for proper implementation we need first class types that support parameter types in order to implement support for nested types.

[DaloLorn]

No, not typed arrays, extended arrays. I agree, typed arrays are a whole other can of worms, but the proposal doesn't really change the way typed collections work, it just adds a simplified method of attaching a wrapper around a collection.

Likewise, I don't think it's particularly critical that parameterized classes (i.e. generics) retain their type information at runtime. Both aspects of my proposal center exclusively around developer QoL, teaching the GDScript interpreter about constructs that can already be expressed in GDScript, but require outsized quantities of fragile code to express.

[dalexeev]

GDScript combines both dynamic and static typing. The user can not only choose one of the options, but use both at the same time, combining typed and untyped code. So we need to balance between these two aspects. Also GDScript relies heavily on the Godot core type system, it is not an independent language with type erasure like TypeScript.

In my opinion, adding "ephemeral" types like Array<int> (in runtime it’s just an Array, the element type is used only in the static analyzer), will not only complicate the implementation, but will also confuse users, given the fact that we already have Array[int] (current typed arrays, with runtime check). We already have "ephemeral" enums (in runtime it's just int), but this is consistent with core. GDScript simply borrowed this problem from C++, just like nullable objects.

[DaloLorn]

I need to get into the habit of writing these things elsewhere, where I can periodically hit Ctrl-S. Bloody machine blew up on me the first time I was writing a reply...

Summarized, then, because writing code examples in GitHub is a pain in the neck:

I don't care about Array<int>, precisely because we already have Array[int]. In fact, at no point does my proposal even allow for Array<int> to be a thing: You're attacking Ryan's suggested additions, not the core proposal.

What I am proposing is no more, and no less, than these two pieces of functionality:

• The possibility to define parameterized (i.e. generic) types, and have their type parameters respected by the static analyzer and the inspector.
• The possibility to define a class that extends a collection type (whether that collection is typed or not), and again have the implications thereof recognized by the static analyzer and the inspector.

Both of these things are already entirely possible in GDScript, but require unnecessarily bloated and potentially fragile script constructs to achieve. In my previous comment, I demonstrated how you could achieve almost the same effect as an extended collection type, with probably the biggest difference being that there's no way in current GDScript for a typed variable to be typed as being one of several possible types, so statically typed APIs written for 4.2 would need to choose between using an Array and using an ArrayWithMetadata. (Well, also the fact that you can't define operators for custom types, so bracket syntax would not work for ArrayWithMetadata.)

Meanwhile, my idea for generics? Literally lifting the Java rules would be perfectly adequate in my book, no matter what kind of syntax you settled on. Use Class<T>, Class[T], Class of T, whatever format floats your boat, but anything beyond the JVM implementation is also beyond the scope of what I was asking for here.

[AlbertoRota]

In regards of "The possibility to define parameterized (i.e. generic) types, and have their type parameters respected by the static analyzer and the inspector", I added a possible work around here:

https://github.com/godotengine/godot-proposals/issues/1207#issuecomment-1770330816

Is not as convenient as "True generics" (Java/Kotlin/C#), but it'll get the job done until they are added to GdScript.

[DaloLorn]

I'm not sure how I overlooked the above comment for so long, but reading it has made me realize half of my proposal is just duplicating #1207. Updated accordingly.