godot_core/builtin/collections/

array.rs

/*
 * Copyright (c) godot-rust; Bromeon and contributors.
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at https://mozilla.org/MPL/2.0/.
 */

use std::cell::OnceCell;
use std::marker::PhantomData;
use std::{cmp, fmt};

use godot_ffi as sys;
use sys::{GodotFfi, ffi_methods, interface_fn};

use crate::builtin::iter::ArrayFunctionalOps;
use crate::builtin::*;
use crate::meta;
use crate::meta::error::{ArrayMismatch, ConvertError, FromGodotError, FromVariantError};
use crate::meta::inspect::ElementType;
use crate::meta::shape::{GodotElementShape, GodotShape};
use crate::meta::signed_range::SignedRange;
use crate::meta::{
    AsArg, ClassId, Element, ExtVariantType, FromGodot, GodotConvert, GodotFfiVariant, GodotType,
    RefArg, ToGodot, element_variant_type,
};
use crate::obj::{Bounds, DynGd, Gd, GodotClass, bounds};
use crate::registry::info::{ParamMetadata, PropertyHintInfo};
use crate::registry::property::{BuiltinExport, Export, Var};

/// Godot's `Array` type.
///
/// Versatile, linear storage container for all types that can be represented inside a `Variant`.  \
/// For space-efficient storage, consider using [`PackedArray<T>`][crate::builtin::PackedArray] or `Vec<T>`.
///
/// Check out the [book](https://godot-rust.github.io/book/godot-api/builtins.html#arrays-and-dictionaries) for a tutorial on arrays.
///
/// # Reference semantics
/// Like in GDScript, `Array` acts as a reference type: multiple `Array` instances may
/// refer to the same underlying array, and changes to one are visible in the other.
///
/// To create a copy that shares data with the original array, use [`Clone::clone()`].
/// If you want to create a copy of the data, use [`duplicate_shallow()`][Self::duplicate_shallow]
/// or [`duplicate_deep()`][Self::duplicate_deep].
///
/// # Element type
/// Godot's `Array` builtin can be either typed or untyped. In Rust, this maps to three representations:
///
/// - Untyped array: `VariantArray`, a type alias for `Array<Variant>`.  \
///   An untyped array can contain any kind of [`Variant`], even different types in the same array.
///
/// - Typed: `Array<T>`, with any non-`Variant` type `T` such as `i64`, `GString`, `Gd<T>` etc.  \
///   Typing is enforced at compile-time in Rust, and at runtime by Godot.
///
/// - Either typed or untyped: [`AnyArray`].  \
///   Represents either typed or untyped arrays. This is different from `Array<Variant>`, because the latter allows you to insert
///   `Variant` objects. However, for an array that has dynamic type `i64`, it is not allowed to insert any variants that are not `i64`.
///
/// If you plan to use any integer or float types apart from `i64` and `f64`, read
/// [this documentation](../meta/trait.Element.html#integer-and-float-types).
///
/// ## Conversions between arrays
/// The following table gives an overview of useful conversions.
///
/// | From               | To               | Conversion method                                        |
/// |--------------------|------------------|----------------------------------------------------------|
/// | `AnyArray`         | `Array<T>`       | [`AnyArray::try_cast_array::<T>`]                        |
/// | `AnyArray`         | `Array<Variant>` | [`AnyArray::try_cast_var_array`]                         |
/// | `&Array<T>`        | `&AnyArray`      | Implicit via [deref coercion]; often used in class APIs. |
/// | `Array<T>`         | `AnyArray`       | [`Array<T>::upcast_any_array`]                           |
/// | `Array<T>`         | `PackedArray<T>` | [`Array<T>::to_packed_array`]                            |
/// | `PackedArray<T>`   | `Array<T>`       | [`PackedArray<T>::to_typed_array`]                       |
/// | `PackedArray<T>`   | `Array<Variant>` | [`PackedArray<T>::to_var_array`]                         |
///
/// Note that it's **not** possible to upcast `Array<Gd<Derived>>` to `Array<Gd<Base>>`. `Array<T>` is not covariant over the `T` parameter,
/// otherwise it would be possible to insert `Base` pointers that aren't actually `Derived`.
// Note: the above could theoretically be implemented by making AnyArray<T> generic and covariant over T.
///
/// [deref coercion]: struct.Array.html#deref-methods-AnyArray
///
/// ## Typed array example
/// ```no_run
/// # use godot::prelude::*;
/// // Create typed Array<i64> and add values.
/// let mut array = Array::<i64>::new();
/// array.push(10);
/// array.push(20);
/// array.push(30);
///
/// // Or create the same array in a single expression.
/// let array = iarray![10, 20, 30];
///
/// // Access elements.
/// let value: i64 = array.at(0); // 10
/// let maybe: Option<i64> = array.get(3); // None
///
/// // Iterate over i64 elements.
/// for value in array.iter_shared() {
///    println!("{value}");
/// }
///
/// // Clone array (shares the reference), and overwrite elements through clone.
/// let mut cloned = array.clone();
/// cloned.set(0, 50); // [50, 20, 30]
/// cloned.remove(1);  // [50, 30]
/// cloned.pop();      // [50]
///
/// // Changes will be reflected in the original array.
/// assert_eq!(array.len(), 1);
/// assert_eq!(array.front(), Some(50));
/// ```
///
/// ## Untyped array example
/// ```no_run
/// # use godot::prelude::*;
/// // VarArray allows dynamic element types.
/// let mut array = VarArray::new();
/// array.push(&10.to_variant());
/// array.push(&"Hello".to_variant());
///
/// // Or equivalent, use the `varray!` macro which converts each element.
/// let array = varray![10, "Hello"];
///
/// // Access elements.
/// let value: Variant = array.at(0);
/// let value: i64 = array.at(0).to(); // Variant::to() extracts i64.
/// let maybe: Result<i64, _> = array.at(1).try_to(); // "Hello" is not i64 -> Err.
/// let maybe: Option<Variant> = array.get(3);
///
/// // ...and so on.
/// ```
///
/// # Working with signed ranges and steps
/// For negative indices, use [`wrapped()`](crate::meta::wrapped).
///
/// ```no_run
/// # use godot::builtin::{array, iarray};
/// # use godot::meta::wrapped;
/// let arr = iarray![0, 1, 2, 3, 4, 5];
///
/// // The values of `begin` (inclusive) and `end` (exclusive) will be clamped to the array size.
/// let clamped_array = arr.subarray_deep(999..99999, None);
/// assert_eq!(clamped_array, array![]);
///
/// // If either `begin` or `end` is negative, its value is relative to the end of the array.
/// let sub = arr.subarray_shallow(wrapped(-1..-5), None);
/// assert_eq!(sub, array![5, 3]);
///
/// // If `end` is not specified, the range spans through whole array.
/// let sub = arr.subarray_deep(1.., None);
/// assert_eq!(sub, array![1, 2, 3, 4, 5]);
/// let other_clamped_array = arr.subarray_shallow(5.., Some(2));
/// assert_eq!(other_clamped_array, array![5]);
///
/// // If specified, `step` is the relative index between source elements. It can be negative,
/// // in which case `begin` must be higher than `end`.
/// let sub = arr.subarray_shallow(wrapped(-1..-5), Some(-2));
/// assert_eq!(sub, array![5, 3]);
/// ```
///
/// # Thread safety
/// Usage is safe if the `Array` is used on a single thread only. Concurrent reads on
/// different threads are also safe, but any writes must be externally synchronized. The Rust
/// compiler will enforce this as long as you use only Rust threads, but it cannot protect against
/// concurrent modification on other threads (e.g. created through GDScript).
///
/// # Element type safety
/// We provide a richer set of element types than Godot, for convenience and stronger invariants in your _Rust_ code.
/// This, however, means that the Godot representation of such arrays is not capable of incorporating the additional "Rust-side" information.
/// This can lead to situations where GDScript code or the editor UI can insert values that do not fulfill the Rust-side invariants.
/// The library offers some best-effort protection in Debug mode, but certain errors may only occur on element access, in the form of panics.
///
/// Concretely, the following types lose type information when passed to Godot. If you want 100% bullet-proof arrays, avoid those.
/// - Non-`i64` integers: `i8`, `i16`, `i32`, `u8`, `u16`, `u32`. (`u64` is unsupported).
/// - Non-`f64` floats: `f32`.
/// - Non-null objects: [`Gd<T>`][crate::obj::Gd].
///   Godot generally allows `null` in arrays due to default-constructability, e.g. when using `resize()`.
///   The Godot-faithful (but less convenient) alternative is to use `Option<Gd<T>>` element types.
/// - Objects with dyn-trait association: [`DynGd<T, D>`][crate::obj::DynGd].
///   Godot doesn't know Rust traits and will only see the `T` part.
///
/// # Differences from GDScript
/// Unlike GDScript, all indices and sizes are unsigned, so negative indices are not supported.
///
/// # Godot docs
/// [`Array[T]` (stable)](https://docs.godotengine.org/en/stable/classes/class_array.html)
pub struct Array<T: Element> {
    // Safety Invariant: The type of all values in `opaque` matches the type `T`.
    opaque: sys::types::OpaqueArray,
    _phantom: PhantomData<T>,

    /// Lazily computed and cached element type information.
    pub(super) cached_element_type: OnceCell<ElementType>,
}

/// Guard that can only call immutable methods on the array.
pub(super) struct ImmutableInnerArray<'a> {
    inner: inner::InnerArray<'a>,
}

impl<'a> std::ops::Deref for ImmutableInnerArray<'a> {
    type Target = inner::InnerArray<'a>;

    fn deref(&self) -> &Self::Target {
        &self.inner
    }
}

impl<T: Element> std::ops::Deref for Array<T> {
    type Target = AnyArray;

    fn deref(&self) -> &Self::Target {
        self.as_any_ref()
    }
}

impl<T: Element> std::ops::DerefMut for Array<T> {
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.as_any_mut()
    }
}

// Compile-time validation of layout compatibility.
sys::static_assert_eq_size_align!(Array<i64>, VarArray);
sys::static_assert_eq_size_align!(Array<GString>, VarArray);
sys::static_assert_eq_size_align!(VarArray, AnyArray);

/// Untyped Godot `Array`.
pub type VarArray = Array<Variant>;

// TODO check if these return a typed array

// Methods that don't provide type-specific ergonomics are available through `Deref`/`DerefMut` to [`AnyArray`].
// This includes:
// - Read-only: `len()`, `is_empty()`, `hash_u32()`, `element_type()`
// - Mutable: `clear()`, `reverse()`, `shuffle()`, `shrink()`, `sort_unstable()`, `sort_unstable_custom()`
//
// Only methods that benefit from the type parameter `T` are implemented directly on `Array<T>`:
// - Methods returning `T` instead of `Variant`: `at()`, `get()`, `front()`, `back()`, `min()`, `max()`, `pick_random()`, `pop()`, `pop_front()`, `remove()`
// - Methods accepting `impl AsArg<T>`: `set()`, `push()`, `insert()`, `contains()`, `find()`, `erase()`, etc.
// - Methods with typed closures: `sort_unstable_by()`, `bsearch_by()`
// - Methods returning `Array<T>`: `duplicate_shallow()`, `duplicate_deep()`, `subarray_shallow()`, `subarray_deep()`
impl<T: Element> Array<T> {
    pub(super) fn from_opaque(opaque: sys::types::OpaqueArray) -> Self {
        // Note: type is not yet checked at this point, because array has not yet been initialized!
        Self {
            opaque,
            _phantom: PhantomData,
            cached_element_type: OnceCell::new(),
        }
    }

    /// Constructs an empty `Array`.
    pub fn new() -> Self {
        Self::default()
    }

    /// ⚠️ Returns the value at the specified index.
    ///
    /// This replaces the `Index` trait, which cannot be implemented for `Array`, as it stores variants and not references.
    ///
    /// # Panics
    /// If `index` is out of bounds. To handle out-of-bounds access fallibly, use [`get()`](Self::get) instead.
    pub fn at(&self, index: usize) -> T {
        // Panics on out-of-bounds.
        let ptr = self.ptr(index);

        // SAFETY: `ptr` is a live pointer to a variant since `ptr.is_null()` just verified that the index is not out of bounds.
        let variant = unsafe { Variant::borrow_var_sys(ptr) };
        T::from_variant(variant)
    }

    /// Returns the value at the specified index, or `None` if the index is out-of-bounds.
    ///
    /// If you know the index is correct, use [`at()`](Self::at) instead.
    pub fn get(&self, index: usize) -> Option<T> {
        let ptr = self.ptr_or_null(index);
        if ptr.is_null() {
            None
        } else {
            // SAFETY: `ptr` is a live pointer to a variant since `ptr.is_null()` just verified that the index is not out of bounds.
            let variant = unsafe { Variant::borrow_var_sys(ptr) };
            Some(T::from_variant(variant))
        }
    }

    /// Returns `true` if the array contains the given value. Equivalent of `has` in GDScript.
    pub fn contains(&self, value: impl AsArg<T>) -> bool {
        meta::arg_into_ref!(value: T);
        self.as_inner().has(&value.to_variant())
    }

    /// Returns the number of times a value is in the array.
    pub fn count(&self, value: impl AsArg<T>) -> usize {
        meta::arg_into_ref!(value: T);
        to_usize(self.as_inner().count(&value.to_variant()))
    }

    /// Returns the first element in the array, or `None` if the array is empty.
    #[doc(alias = "first")]
    pub fn front(&self) -> Option<T> {
        (!self.is_empty()).then(|| {
            let variant = self.as_inner().front();
            T::from_variant(&variant)
        })
    }

    /// Returns the last element in the array, or `None` if the array is empty.
    #[doc(alias = "last")]
    pub fn back(&self) -> Option<T> {
        (!self.is_empty()).then(|| {
            let variant = self.as_inner().back();
            T::from_variant(&variant)
        })
    }

    ///  ⚠️ Sets the value at the specified index.
    ///
    /// # Panics
    ///
    /// If `index` is out of bounds.
    pub fn set(&mut self, index: usize, value: impl AsArg<T>) {
        self.balanced_ensure_mutable();

        let ptr_mut = self.ptr_mut(index);

        meta::arg_into_ref!(value: T);
        let variant = value.to_variant();

        // SAFETY: `ptr_mut` just checked that the index is not out of bounds.
        unsafe { variant.move_into_var_ptr(ptr_mut) };
    }

    /// Appends an element to the end of the array.
    ///
    /// _Godot equivalents: `append` and `push_back`_
    #[doc(alias = "append")]
    #[doc(alias = "push_back")]
    pub fn push(&mut self, value: impl AsArg<T>) {
        self.balanced_ensure_mutable();

        meta::arg_into_ref!(value: T);

        // SAFETY: The array has type `T` and we're writing a value of type `T` to it.
        let mut inner = unsafe { self.as_inner_mut() };
        inner.push_back(&value.to_variant());
    }

    /// Internal helper for the `array!` macro; uses [`AsDirectElement`][meta::AsDirectElement] for unambiguous type inference.
    #[doc(hidden)]
    pub fn __macro_push_direct<E: meta::AsDirectElement<T>>(&mut self, value: E) {
        self.push(value)
    }

    /// Adds an element at the beginning of the array, in O(n).
    ///
    /// On large arrays, this method is much slower than [`push()`][Self::push], as it will move all the array's elements.
    /// The larger the array, the slower `push_front()` will be.
    pub fn push_front(&mut self, value: impl AsArg<T>) {
        self.balanced_ensure_mutable();

        meta::arg_into_ref!(value: T);

        // SAFETY: The array has type `T` and we're writing a value of type `T` to it.
        let mut inner_array = unsafe { self.as_inner_mut() };
        inner_array.push_front(&value.to_variant());
    }

    /// Removes and returns the last element of the array. Returns `None` if the array is empty.
    ///
    /// _Godot equivalent: `pop_back`_
    #[doc(alias = "pop_back")]
    pub fn pop(&mut self) -> Option<T> {
        self.balanced_ensure_mutable();

        (!self.is_empty()).then(|| {
            // SAFETY: We do not write any values to the array, we just remove one.
            let variant = unsafe { self.as_inner_mut() }.pop_back();
            T::from_variant(&variant)
        })
    }

    /// Removes and returns the first element of the array, in O(n). Returns `None` if the array is empty.
    ///
    /// Note: On large arrays, this method is much slower than `pop()` as it will move all the
    /// array's elements. The larger the array, the slower `pop_front()` will be.
    pub fn pop_front(&mut self) -> Option<T> {
        self.balanced_ensure_mutable();

        (!self.is_empty()).then(|| {
            // SAFETY: We do not write any values to the array, we just remove one.
            let variant = unsafe { self.as_inner_mut() }.pop_front();
            T::from_variant(&variant)
        })
    }

    /// ⚠️ Inserts a new element before the index. The index must be valid or the end of the array (`index == len()`).
    ///
    /// On large arrays, this method is much slower than [`push()`][Self::push], as it will move all the array's elements after the inserted element.
    /// The larger the array, the slower `insert()` will be.
    ///
    /// # Panics
    /// If `index > len()`.
    pub fn insert(&mut self, index: usize, value: impl AsArg<T>) {
        self.balanced_ensure_mutable();

        let len = self.len();
        assert!(
            index <= len,
            "Array insertion index {index} is out of bounds: length is {len}",
        );

        meta::arg_into_ref!(value: T);

        // SAFETY: The array has type `T` and we're writing a value of type `T` to it.
        unsafe { self.as_inner_mut() }.insert(to_i64(index), &value.to_variant());
    }

    /// ⚠️ Removes and returns the element at the specified index. Equivalent of `pop_at` in GDScript.
    ///
    /// On large arrays, this method is much slower than [`pop()`][Self::pop] as it will move all the array's
    /// elements after the removed element. The larger the array, the slower `remove()` will be.
    ///
    /// # Panics
    ///
    /// If `index` is out of bounds.
    #[doc(alias = "pop_at")]
    pub fn remove(&mut self, index: usize) -> T {
        self.balanced_ensure_mutable();
        self.check_bounds(index);

        // SAFETY: We do not write any values to the array, we just remove one.
        let variant = unsafe { self.as_inner_mut() }.pop_at(to_i64(index));
        T::from_variant(&variant)
    }

    /// Removes the first occurrence of a value from the array.
    ///
    /// If the value does not exist in the array, nothing happens. To remove an element by index, use [`remove()`][Self::remove] instead.
    ///
    /// On large arrays, this method is much slower than [`pop()`][Self::pop], as it will move all the array's
    /// elements after the removed element.
    pub fn erase(&mut self, value: impl AsArg<T>) {
        self.balanced_ensure_mutable();

        meta::arg_into_ref!(value: T);

        // SAFETY: We don't write anything to the array.
        unsafe { self.as_inner_mut() }.erase(&value.to_variant());
    }

    /// Assigns the given value to all elements in the array. This can be used together with
    /// `resize` to create an array with a given size and initialized elements.
    pub fn fill(&mut self, value: impl AsArg<T>) {
        self.balanced_ensure_mutable();

        meta::arg_into_ref!(value: T);

        // SAFETY: The array has type `T` and we're writing values of type `T` to it.
        unsafe { self.as_inner_mut() }.fill(&value.to_variant());
    }

    /// Resizes the array to contain a different number of elements.
    ///
    /// If the new size is smaller than the current size, then it removes elements from the end. If the new size is bigger than the current one
    /// then the new elements are set to `value`.
    ///
    /// If you know that the new size is smaller, then consider using [`shrink`][AnyArray::shrink] instead.
    pub fn resize(&mut self, new_size: usize, value: impl AsArg<T>) {
        self.balanced_ensure_mutable();

        let original_size = self.len();

        // SAFETY: While we do insert `Variant::nil()` if the new size is larger, we then fill it with `value` ensuring that all values in the
        // array are of type `T` still.
        unsafe { self.as_inner_mut() }.resize(to_i64(new_size));

        meta::arg_into_ref!(value: T);

        // If new_size < original_size then this is an empty iterator and does nothing.
        for i in original_size..new_size {
            // Exception safety: if to_variant() panics, the array will become inconsistent (filled with non-T nils).
            // At the moment (Nov 2024), this can only happen for u64, which isn't a valid Array element type.
            // This could be changed to use clone() (if that doesn't panic) or store a variant without moving.
            let variant = value.to_variant();

            let ptr_mut = self.ptr_mut(i);

            // SAFETY: we iterate pointer within bounds; ptr_mut() additionally checks them.
            // ptr_mut() lookup could be optimized if we know the internal layout.
            unsafe { variant.move_into_var_ptr(ptr_mut) };
        }
    }

    /// Appends another array at the end of this array. Equivalent of `append_array` in GDScript.
    pub fn extend_array(&mut self, other: &Array<T>) {
        self.balanced_ensure_mutable();

        // SAFETY: `append_array` will only write values gotten from `other` into `self`, and all values in `other` are guaranteed
        // to be of type `T`.
        let mut inner_self = unsafe { self.as_inner_mut() };
        inner_self.append_array(other);
    }

    /// Returns a shallow copy, sharing reference types (`Array`, `Dictionary`, `Object`...) with the original array.
    ///
    /// This operation retains the dynamic [element type][Self::element_type]: copying `Array<T>` will yield another `Array<T>`.
    ///
    /// To create a deep copy, use [`duplicate_deep()`][Self::duplicate_deep] instead.
    /// To create a new reference to the same array data, use [`clone()`][Clone::clone].
    pub fn duplicate_shallow(&self) -> Self {
        // duplicate() returns a typed array with the same type as Self, and all values are taken from `self` so have the right type.
        self.as_inner().duplicate(false).cast_array::<T>()
    }

    /// Returns a deep copy, duplicating nested `Array`/`Dictionary` elements but keeping `Object` elements shared.
    ///
    /// To create a shallow copy, use [`duplicate_shallow()`][Self::duplicate_shallow] instead.
    /// To create a new reference to the same array data, use [`clone()`][Clone::clone].
    pub fn duplicate_deep(&self) -> Self {
        // duplicate() returns a typed array with the same type as Self, and all values are taken from `self` so have the right type.
        self.as_inner().duplicate(true).cast_array::<T>()
    }

    /// Returns a sub-range `begin..end` as a new `Array`.
    ///
    /// Array elements are copied to the slice, but any reference types (such as `Array`,
    /// `Dictionary` and `Object`) will still refer to the same value. To create a deep copy, use
    /// [`subarray_deep()`][Self::subarray_deep] instead.
    ///
    /// _Godot equivalent: `slice`_
    #[doc(alias = "slice")]
    pub fn subarray_shallow(&self, range: impl SignedRange, step: Option<i32>) -> Self {
        self.subarray_impl(range, step, false)
    }

    /// Returns a sub-range `begin..end` as a new `Array`.
    ///
    /// All nested arrays and dictionaries are duplicated and will not be shared with the original
    /// array. Note that any `Object`-derived elements will still be shallow copied. To create a
    /// shallow copy, use [`subarray_shallow()`][Self::subarray_shallow] instead.
    ///
    /// _Godot equivalent: `slice`_
    #[doc(alias = "slice")]
    pub fn subarray_deep(&self, range: impl SignedRange, step: Option<i32>) -> Self {
        self.subarray_impl(range, step, true)
    }

    // Note: Godot will clamp values by itself.
    fn subarray_impl(&self, range: impl SignedRange, step: Option<i32>, deep: bool) -> Self {
        assert_ne!(step, Some(0), "subarray: step cannot be zero");

        let step = step.unwrap_or(1);
        let (begin, end) = range.signed();
        let end = end.unwrap_or(i32::MAX as i64);

        self.as_inner()
            .slice(begin, end, step as i64, deep)
            .cast_array::<T>()
    }

    /// Returns an non-exclusive iterator over the elements of the `Array`.
    ///
    /// Takes the array by reference but returns its elements by value, since they are internally converted from `Variant`.
    ///
    /// Notice that it's possible to modify the `Array` through another reference while iterating over it. This will not result
    /// in unsoundness or crashes, but will cause the iterator to behave in an unspecified way.
    pub fn iter_shared(&self) -> ArrayIter<'_, T> {
        ArrayIter {
            array: self,
            next_idx: 0,
        }
    }

    /// Returns the minimum value contained in the array if all elements are of comparable types.
    ///
    /// If the elements can't be compared or the array is empty, `None` is returned.
    pub fn min(&self) -> Option<T> {
        let min = self.as_inner().min();
        (!min.is_nil()).then(|| T::from_variant(&min))
    }

    /// Returns the maximum value contained in the array if all elements are of comparable types.
    ///
    /// If the elements can't be compared or the array is empty, `None` is returned.
    pub fn max(&self) -> Option<T> {
        let max = self.as_inner().max();
        (!max.is_nil()).then(|| T::from_variant(&max))
    }

    /// Returns a random element from the array, or `None` if it is empty.
    pub fn pick_random(&self) -> Option<T> {
        (!self.is_empty()).then(|| {
            let variant = self.as_inner().pick_random();
            T::from_variant(&variant)
        })
    }

    /// Searches the array for the first occurrence of a value and returns its index, or `None` if
    /// not found.
    ///
    /// Starts searching at index `from`; pass `None` to search the entire array.
    pub fn find(&self, value: impl AsArg<T>, from: Option<usize>) -> Option<usize> {
        meta::arg_into_ref!(value: T);

        let from = to_i64(from.unwrap_or(0));
        let index = self.as_inner().find(&value.to_variant(), from);
        if index >= 0 {
            Some(index.try_into().unwrap())
        } else {
            None
        }
    }

    /// Searches the array backwards for the last occurrence of a value and returns its index, or
    /// `None` if not found.
    ///
    /// Starts searching at index `from`; pass `None` to search the entire array.
    pub fn rfind(&self, value: impl AsArg<T>, from: Option<usize>) -> Option<usize> {
        meta::arg_into_ref!(value: T);

        let from = from.map(to_i64).unwrap_or(-1);
        let index = self.as_inner().rfind(&value.to_variant(), from);

        // It's not documented, but `rfind` returns -1 if not found.
        if index >= 0 {
            Some(to_usize(index))
        } else {
            None
        }
    }

    /// Finds the index of a value in a sorted array using binary search.
    ///
    /// If the value is not present in the array, returns the insertion index that would maintain sorting order.
    ///
    /// Calling `bsearch` on an unsorted array results in unspecified behavior. Consider using `sort()` to ensure the sorting
    /// order is compatible with your callable's ordering.
    ///
    /// See also: [`bsearch_by()`][Self::bsearch_by], [`functional_ops().bsearch_custom()`][ArrayFunctionalOps::bsearch_custom].
    pub fn bsearch(&self, value: impl AsArg<T>) -> usize {
        meta::arg_into_ref!(value: T);

        to_usize(self.as_inner().bsearch(&value.to_variant(), true))
    }

    /// Finds the index of a value in a sorted array using binary search, with type-safe custom predicate.
    ///
    /// The comparator function should return an ordering that indicates whether its argument is `Less`, `Equal` or `Greater` the desired value.
    /// For example, for an ascending-ordered array, a simple predicate searching for a constant value would be `|elem| elem.cmp(&4)`.
    /// This follows the design of [`slice::binary_search_by()`].
    ///
    /// If the value is found, returns `Ok(index)` with its index. Otherwise, returns `Err(index)`, where `index` is the insertion index
    /// that would maintain sorting order.
    ///
    /// Calling `bsearch_by` on an unsorted array results in unspecified behavior. Consider using [`sort_unstable_by()`][Self::sort_unstable_by]
    /// to ensure the sorting order is compatible with your callable's ordering.
    ///
    /// See also: [`bsearch()`][Self::bsearch], [`functional_ops().bsearch_custom()`][ArrayFunctionalOps::bsearch_custom].
    pub fn bsearch_by<F>(&self, mut func: F) -> Result<usize, usize>
    where
        F: FnMut(&T) -> cmp::Ordering + 'static,
    {
        // Early exit; later code relies on index 0 being present.
        if self.is_empty() {
            return Err(0);
        }

        // We need one dummy element of type T, because Godot's bsearch_custom() checks types (so Variant::nil() can't be passed).
        // Optimization: roundtrip Variant -> T -> Variant could be avoided, but anyone needing speed would use Rust binary search...
        let ignored_value = self.at(0);
        let ignored_value = meta::owned_into_arg(ignored_value);

        let godot_comparator = |args: &[&Variant]| {
            let value = T::from_variant(args[0]);
            let is_less = matches!(func(&value), cmp::Ordering::Less);

            is_less.to_variant()
        };

        let debug_name = std::any::type_name::<F>();
        let index = Callable::with_scoped_fn(debug_name, godot_comparator, |pred| {
            self.functional_ops().bsearch_custom(ignored_value, pred)
        });

        if let Some(value_at_index) = self.get(index)
            && func(&value_at_index) == cmp::Ordering::Equal
        {
            return Ok(index);
        }

        Err(index)
    }

    /// Sorts the array, using a type-safe comparator.
    ///
    /// The predicate expects two parameters `(a, b)` and should return an ordering relation. For example, simple ascending ordering of the
    /// elements themselves would be achieved with `|a, b| a.cmp(b)`.
    ///
    /// The sorting algorithm used is not [stable](https://en.wikipedia.org/wiki/Sorting_algorithm#Stability).
    /// This means that values considered equal may have their order changed when using `sort_unstable_by()`. For most variant types,
    /// this distinction should not matter though.
    ///
    /// See also: [`sort_unstable()`][Self::sort_unstable], [`sort_unstable_custom()`][Self::sort_unstable_custom].
    pub fn sort_unstable_by<F>(&mut self, mut func: F)
    where
        F: FnMut(&T, &T) -> cmp::Ordering,
    {
        self.balanced_ensure_mutable();

        let godot_comparator = |args: &[&Variant]| {
            let lhs = T::from_variant(args[0]);
            let rhs = T::from_variant(args[1]);
            let is_less = matches!(func(&lhs, &rhs), cmp::Ordering::Less);

            is_less.to_variant()
        };

        let debug_name = std::any::type_name::<F>();
        Callable::with_scoped_fn(debug_name, godot_comparator, |pred| {
            self.sort_unstable_custom(pred)
        });
    }

    /// Access to Godot's functional-programming APIs based on callables.
    ///
    /// Exposes Godot array methods such as `filter()`, `map()`, `reduce()` and many more. See return type docs.
    pub fn functional_ops(&self) -> ArrayFunctionalOps<'_, T> {
        ArrayFunctionalOps::new(self)
    }

    /// Turns the array into a shallow-immutable array.
    ///
    /// Makes the array read-only and returns the original array. The array's elements cannot be overridden with different values, and their
    /// order cannot change. Does not apply to nested elements, such as dictionaries. This operation is irreversible.
    ///
    /// In GDScript, arrays are automatically read-only if declared with the `const` keyword.
    ///
    /// # Semantics and alternatives
    /// You can use this in Rust, but the behavior of mutating methods is only validated in a best-effort manner (more than in GDScript though):
    /// some methods like `set()` panic in Debug mode, when used on a read-only array. There is no guarantee that any attempts to change result
    /// in feedback; some may silently do nothing.
    ///
    /// In Rust, you can use shared references (`&Array<T>`) to prevent mutation. Note however that `Clone` can be used to create another
    /// reference, through which mutation can still occur. For deep-immutable arrays, you'll need to keep your `Array` encapsulated or directly
    /// use Rust data structures.
    ///
    /// _Godot equivalent: `make_read_only`_
    #[doc(alias = "make_read_only")]
    pub fn into_read_only(self) -> Self {
        // SAFETY: Changes a per-array property, no elements.
        unsafe { self.as_inner_mut() }.make_read_only();
        self
    }

    /// Downgrades this typed/untyped `Array<T>` into an owned `AnyArray`.
    ///
    /// Typically, you can use deref coercion to convert `&Array<T>` to `&AnyArray`. This method is useful if you need `AnyArray` by value.
    /// It consumes `self` to avoid incrementing the reference count; use `clone()` if you use the original array further.
    pub fn upcast_any_array(self) -> AnyArray {
        AnyArray::from_typed_or_untyped(self)
    }

    /// Converts this typed `Array<T>` into a `PackedArray<T>`.
    pub fn to_packed_array(&self) -> PackedArray<T>
    where
        T: meta::PackedElement,
    {
        PackedArray::<T>::from_typed_array(self)
    }

    /// Returns true if the array is read-only.
    ///
    /// See [`into_read_only()`][Self::into_read_only].
    /// In GDScript, arrays are automatically read-only if declared with the `const` keyword.
    pub fn is_read_only(&self) -> bool {
        self.as_inner().is_read_only()
    }

    /// Best-effort mutability check.
    ///
    /// # Panics (safeguards-balanced)
    /// If the array is marked as read-only.
    fn balanced_ensure_mutable(&self) {
        sys::balanced_assert!(
            !self.is_read_only(),
            "mutating operation on read-only array"
        );
    }

    /// Asserts that the given index refers to an existing element.
    ///
    /// # Panics
    /// If `index` is out of bounds.
    fn check_bounds(&self, index: usize) {
        // Safety-relevant; explicitly *don't* use safeguards-dependent validation.
        let len = self.len();
        assert!(
            index < len,
            "Array index {index} is out of bounds: length is {len}",
        );
    }

    /// Returns a pointer to the element at the given index.
    ///
    /// # Panics
    /// If `index` is out of bounds.
    fn ptr(&self, index: usize) -> sys::GDExtensionConstVariantPtr {
        let ptr = self.ptr_or_null(index);
        assert!(
            !ptr.is_null(),
            "Array index {index} out of bounds (len {len})",
            len = self.len(),
        );
        ptr
    }

    /// Returns a pointer to the element at the given index, or null if out of bounds.
    fn ptr_or_null(&self, index: usize) -> sys::GDExtensionConstVariantPtr {
        let index = to_i64(index);

        // SAFETY: array_operator_index_const returns null for invalid indexes.
        let variant_ptr = unsafe { interface_fn!(array_operator_index_const)(self.sys(), index) };

        // Signature is wrong in GDExtension, semantically this is a const ptr
        sys::SysPtr::as_const(variant_ptr)
    }

    /// Returns a mutable pointer to the element at the given index.
    ///
    /// # Panics
    ///
    /// If `index` is out of bounds.
    fn ptr_mut(&mut self, index: usize) -> sys::GDExtensionVariantPtr {
        let ptr = self.ptr_mut_or_null(index);
        assert!(
            !ptr.is_null(),
            "Array index {index} out of bounds (len {len})",
            len = self.len(),
        );
        ptr
    }

    /// Returns a pointer to the element at the given index, or null if out of bounds.
    fn ptr_mut_or_null(&mut self, index: usize) -> sys::GDExtensionVariantPtr {
        let index = to_i64(index);

        // SAFETY: array_operator_index returns null for invalid indexes.
        unsafe { interface_fn!(array_operator_index)(self.sys_mut(), index) }
    }

    /// # Safety
    /// This has the same safety issues as doing `self.assume_type::<Variant>()` and so the relevant safety invariants from
    /// [`assume_type`](Self::assume_type) must be upheld.
    ///
    /// In particular this means that all reads are fine, since all values can be converted to `Variant`. However, writes are only OK
    /// if they match the type `T`.
    #[doc(hidden)]
    pub unsafe fn as_inner_mut(&self) -> inner::InnerArray<'_> {
        // The memory layout of `Array<T>` does not depend on `T`.
        inner::InnerArray::from_outer_typed(self)
    }

    pub(super) fn as_inner(&self) -> ImmutableInnerArray<'_> {
        ImmutableInnerArray {
            // SAFETY: We can only read from the array.
            inner: unsafe { self.as_inner_mut() },
        }
    }

    /// Changes the generic type on this array, without changing its contents. Needed for API functions
    /// that take a variant array even though we want to pass a typed one.
    ///
    /// # Safety
    /// - Any values written to the array must match the runtime type of the array.
    /// - Any values read from the array must be convertible to the type `U`.
    ///
    /// If the safety invariant of `Array` is intact, which it must be for any publicly accessible arrays, then `U` must match
    /// the runtime type of the array. This then implies that both of the conditions above hold. This means that you only need
    /// to keep the above conditions in mind if you are intentionally violating the safety invariant of `Array`.
    ///
    /// Note also that any `GodotType` can be written to a `Variant` array.
    ///
    /// In the current implementation, both cases will produce a panic rather than undefined behavior, but this should not be relied upon.
    #[cfg(safeguards_strict)] #[cfg_attr(published_docs, doc(cfg(safeguards_strict)))]
    unsafe fn assume_type_ref<U: Element>(&self) -> &Array<U> {
        // SAFETY: per function precondition.
        unsafe { std::mem::transmute::<&Array<T>, &Array<U>>(self) }
    }

    fn as_any_ref(&self) -> &AnyArray {
        // SAFETY:
        // - Array<T> and Array<Variant> have identical memory layout.
        // - AnyArray is #[repr(transparent)] around VariantArray and provides no "in" operations (moving data in) that could violate covariance.
        unsafe { std::mem::transmute::<&Array<T>, &AnyArray>(self) }
    }

    fn as_any_mut(&mut self) -> &mut AnyArray {
        // SAFETY:
        // - Array<T> and Array<Variant> have identical memory layout (validated by static_assert_eq_size_align!).
        // - AnyArray is #[repr(transparent)] around VariantArray.
        // - Mutable operations on AnyArray work with Variant values, maintaining type safety through balanced_ensure_mutable() checks.
        unsafe { std::mem::transmute::<&mut Array<T>, &mut AnyArray>(self) }
    }

    /// Changes the type parameter without runtime checks, consuming the array.
    ///
    /// # Safety
    /// Same safety requirements as [`assume_type_ref`](Self::assume_type_ref):
    /// - Values written to array must match runtime type.
    /// - Values read must be convertible to type `U`.
    /// - If runtime type matches `U`, both conditions hold automatically.
    // TODO(v0.6): fragile manual field move + mem::forget; if a field is added, it must be moved here too.
    // Consider transmute (requires #[repr(C)]) or ManuallyDrop + ptr::read. Same issue in Dictionary::assume_type.
    pub(super) unsafe fn assume_type<U: Element>(self) -> Array<U> {
        let result = Array::<U> {
            opaque: self.opaque,
            _phantom: PhantomData,
            cached_element_type: OnceCell::new(),
        };

        // Transfer cached type to avoid redundant FFI calls.
        ElementType::transfer_cache(&self.cached_element_type, &result.cached_element_type);

        // Prevent drop of self since we moved opaque.
        std::mem::forget(self);

        result
    }

    /// Validates that all elements in this array can be converted to integers of type `T`.
    #[cfg(safeguards_strict)] #[cfg_attr(published_docs, doc(cfg(safeguards_strict)))]
    pub(crate) fn debug_validate_int_elements(&self) -> Result<(), ConvertError> {
        // SAFETY: every element is internally represented as Variant.
        let canonical_array = unsafe { self.assume_type_ref::<Variant>() };

        // If any element is not convertible, this will return an error.
        for elem in canonical_array.iter_shared() {
            elem.try_to::<T>().map_err(|_err| {
                FromGodotError::BadArrayTypeInt {
                    expected_int_type: std::any::type_name::<T>(),
                    value: elem
                        .try_to::<i64>()
                        .expect("origin must be i64 compatible; this is a bug"),
                }
                .into_error(self.clone()) // Context info about array, not element.
            })?;
        }

        Ok(())
    }

    // No-op in Release. Avoids O(n) conversion checks, but still panics on access.
    #[cfg(not(safeguards_strict))] #[cfg_attr(published_docs, doc(cfg(not(safeguards_strict))))]
    pub(crate) fn debug_validate_int_elements(&self) -> Result<(), ConvertError> {
        Ok(())
    }

    /// Checks that the inner array has the correct type set on it for storing elements of type `T`.
    fn with_checked_type(self) -> Result<Self, ConvertError> {
        let actual = self.element_type();
        let expected = ElementType::of::<T>();

        if actual.is_compatible_with(&expected) {
            Ok(self)
        } else {
            let mismatch = ArrayMismatch { expected, actual };
            Err(FromGodotError::BadArrayType(mismatch).into_error(self))
        }
    }

    /// Sets the type of the inner array.
    ///
    /// # Safety
    /// Must only be called once, directly after creation.
    unsafe fn init_inner_type(&mut self) {
        sys::strict_assert!(self.is_empty());
        sys::strict_assert!(
            self.cached_element_type.get().is_none(),
            "init_inner_type() called twice"
        );

        // Immediately set cache to static type.
        let elem_ty = ElementType::of::<T>();
        let _ = self.cached_element_type.set(elem_ty);

        if elem_ty.is_typed() {
            let script = Variant::nil();

            // A bit contrived because empty StringName is lazy-initialized but must also remain valid.
            #[allow(unused_assignments)]
            let mut empty_string_name = None;
            let class_name = if let Some(class_id) = elem_ty.class_id() {
                class_id.string_sys()
            } else {
                empty_string_name = Some(StringName::default());
                // as_ref() crucial here -- otherwise the StringName is dropped.
                empty_string_name.as_ref().unwrap().string_sys()
            };

            // SAFETY: Valid pointers are passed in.
            // Relevant for correctness, not safety: the array is a newly created, empty, untyped array.
            unsafe {
                interface_fn!(array_set_typed)(
                    self.sys_mut(),
                    elem_ty.variant_type().sys(),
                    class_name, // must be empty if variant_type != OBJECT.
                    script.var_sys(),
                );
            }
        }
    }

    /// Creates a new array for [`GodotFfi::new_with_init()`], without setting a type yet.
    pub(super) fn new_uncached_type(init_fn: impl FnOnce(sys::GDExtensionTypePtr)) -> Self {
        let mut result = unsafe {
            Self::new_with_uninit(|self_ptr| {
                let ctor = sys::builtin_fn!(array_construct_default);
                ctor(self_ptr, std::ptr::null_mut());
            })
        };
        init_fn(result.sys_mut());
        result
    }

    /// # Safety
    /// Does not validate the array element type; `with_checked_type()` should be called afterward.
    // Visibility: shared with AnyArray.
    pub(super) unsafe fn unchecked_from_variant(variant: &Variant) -> Result<Self, ConvertError> {
        let dest_type = Self::VARIANT_TYPE.variant_as_nil();

        if variant.get_type() != dest_type {
            return Err(FromVariantError::BadType {
                expected: dest_type,
                actual: variant.get_type(),
            }
            .into_error(variant.clone()));
        }

        let array = unsafe {
            Self::new_with_uninit(|self_ptr| {
                let array_from_variant = sys::builtin_fn!(array_from_variant);
                array_from_variant(self_ptr, sys::SysPtr::force_mut(variant.var_sys()));
            })
        };

        Ok(array)
    }

    /// Returns a clone of the array without checking the resulting type.
    ///
    /// # Safety
    /// Should be used only in scenarios where the caller can guarantee that the resulting array will have the correct type,
    /// or when an incorrect Rust type is acceptable (passing raw arrays to Godot FFI).
    pub(super) unsafe fn clone_unchecked(&self) -> Self {
        let result = unsafe {
            Self::new_with_uninit(|self_ptr| {
                let ctor = sys::builtin_fn!(array_construct_copy);
                let args = [self.sys()];
                ctor(self_ptr, args.as_ptr());
            })
        };

        result.with_cache(self)
    }

    /// Whether this array is untyped and holds `Variant` elements (compile-time check).
    ///
    /// Used as `if` statement in trait impls. Avoids defining yet another trait or non-local overridden function just for this case;
    /// `Variant` is the only Godot type that has variant type NIL and can be used as an array element.
    fn has_variant_t() -> bool {
        element_variant_type::<T>() == VariantType::NIL
    }

    /// Execute a function that creates a new Array, transferring cached element type if available.
    ///
    /// This is a convenience helper for methods that create new Array instances and want to preserve
    /// cached type information to avoid redundant FFI calls.
    fn with_cache(self, source: &Self) -> Self {
        ElementType::transfer_cache(&source.cached_element_type, &self.cached_element_type);
        self
    }
}

impl VarArray {
    /// # Safety
    /// - Variant must have type `VariantType::ARRAY`.
    /// - Subsequent operations on this array must not rely on the type of the array.
    pub(crate) unsafe fn from_variant_unchecked(variant: &Variant) -> Self {
        unsafe {
            // See also ffi_from_variant().
            Self::new_with_uninit(|self_ptr| {
                let array_from_variant = sys::builtin_fn!(array_from_variant);
                array_from_variant(self_ptr, sys::SysPtr::force_mut(variant.var_sys()));
            })
        }
    }
}

// ----------------------------------------------------------------------------------------------------------------------------------------------
// Traits

// Godot has some inconsistent behavior around NaN values. In GDScript, `NAN == NAN` is `false`,
// but `[NAN] == [NAN]` is `true`. If they decide to make all NaNs equal, we can implement `Eq` and
// `Ord`; if they decide to make all NaNs unequal, we can remove this comment.
//
// impl<T> Eq for Array<T> {}
//
// impl<T> Ord for Array<T> {
//     ...
// }

// SAFETY:
// - `move_return_ptr`
//   Nothing special needs to be done beyond a `std::mem::swap` when returning an Array.
//   So we can just use `ffi_methods`.
//
// - `from_arg_ptr`
//   Arrays are properly initialized through a `from_sys` call, but the ref-count should be incremented
//   as that is the callee's responsibility. Which we do by calling `std::mem::forget(array.clone())`.
unsafe impl<T: Element> GodotFfi for Array<T> {
    const VARIANT_TYPE: ExtVariantType = ExtVariantType::Concrete(VariantType::ARRAY);

    ffi_methods! { type sys::GDExtensionTypePtr = *mut Opaque;
        fn new_from_sys;
        fn new_with_uninit;
        fn sys;
        fn sys_mut;
        fn from_arg_ptr;
        fn move_return_ptr;
    }

    /// Constructs a valid Godot array as ptrcall destination, without caching the element type.
    ///
    /// Ptrcall may replace the underlying data with an array of a different type (e.g. `duplicate()` on a typed
    /// array returns `VarArray` in codegen, but the actual data is typed). The cache is lazily populated on first
    /// access from the actual Godot data.
    unsafe fn new_with_init(init_fn: impl FnOnce(sys::GDExtensionTypePtr)) -> Self {
        Self::new_uncached_type(init_fn)
    }
}

// Only implement for untyped arrays; typed arrays cannot be nested in Godot.
impl Element for VarArray {}

impl<T: Element> GodotConvert for Array<T> {
    type Via = Self;

    fn godot_shape() -> GodotShape {
        if Self::has_variant_t() {
            return GodotShape::Builtin {
                variant_type: VariantType::ARRAY,
                metadata: ParamMetadata::NONE,
            };
        }

        GodotShape::TypedArray {
            element: GodotElementShape::new(T::godot_shape()),
        }
    }
}

impl<T: Element> ToGodot for Array<T> {
    type Pass = meta::ByRef;

    fn to_godot(&self) -> &Self::Via {
        self
    }

    fn to_godot_owned(&self) -> Self::Via
    where
        Self::Via: Clone,
    {
        // Overridden, because default clone() validates that before/after element types are equal, which doesn't matter when we pass to FFI.
        // This may however be an issue if to_godot_owned() is used by the user directly.
        unsafe { self.clone_unchecked() }
    }
}

impl<T: Element> FromGodot for Array<T> {
    fn try_from_godot(via: Self::Via) -> Result<Self, ConvertError> {
        T::debug_validate_elements(&via)?;
        Ok(via)
    }
}

impl<T: Element> fmt::Debug for Array<T> {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        // Going through `Variant` because there doesn't seem to be a direct way.
        // Reuse Display.
        write!(f, "{}", self.to_variant().stringify())
    }
}

impl<T: Element + fmt::Display> fmt::Display for Array<T> {
    /// Formats `Array` to match Godot's string representation.
    ///
    /// # Example
    /// ```no_run
    /// # use godot::prelude::*;
    /// let a = iarray![1,2,3,4];
    /// assert_eq!(format!("{a}"), "[1, 2, 3, 4]");
    /// ```
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        write!(f, "[")?;
        for (count, v) in self.iter_shared().enumerate() {
            if count != 0 {
                write!(f, ", ")?;
            }
            write!(f, "{v}")?;
        }
        write!(f, "]")
    }
}

/// Creates a new reference to the data in this array. Changes to the original array will be
/// reflected in the copy and vice versa.
///
/// To create a (mostly) independent copy instead, see [`Array::duplicate_shallow()`] and
/// [`Array::duplicate_deep()`].
impl<T: Element> Clone for Array<T> {
    fn clone(&self) -> Self {
        // SAFETY: `self` is a valid array, since we have a reference that keeps it alive.
        // Type-check follows below.
        let copy = unsafe { self.clone_unchecked() };

        // Double-check copy's runtime type in Debug mode.
        if cfg!(safeguards_strict) {
            copy.with_checked_type()
                .expect("copied array should have same type as original array")
        } else {
            copy
        }
    }
}

// No Var bound on T.
impl<T: Element> Var for Array<T> {
    type PubType = Self;

    fn var_get(field: &Self) -> Self::Via {
        field.to_godot_owned()
    }

    fn var_set(field: &mut Self, value: Self::Via) {
        *field = FromGodot::from_godot(value);
    }

    fn var_pub_get(field: &Self) -> Self::PubType {
        field.clone()
    }

    fn var_pub_set(field: &mut Self, value: Self::PubType) {
        *field = value;
    }
}

impl<T> Export for Array<T> where T: Element + Export {}

impl<T: Element> BuiltinExport for Array<T> {}

impl<T> Export for Array<Gd<T>>
where
    T: GodotClass + Bounds<Exportable = bounds::Yes>,
{
    #[doc(hidden)]
    fn as_node_class() -> Option<ClassId> {
        PropertyHintInfo::object_as_node_class::<T>()
    }
}

/// `#[export]` for `Array<DynGd<T, D>>` is available only for `T` being Engine class (such as Node or Resource).
///
/// Consider exporting `Array<Gd<T>>` instead of `Array<DynGd<T, D>>` for user-declared GDExtension classes.
impl<T: GodotClass, D> Export for Array<DynGd<T, D>>
where
    T: GodotClass + Bounds<Exportable = bounds::Yes>,
    D: ?Sized + 'static,
{
    #[doc(hidden)]
    fn as_node_class() -> Option<ClassId> {
        PropertyHintInfo::object_as_node_class::<T>()
    }
}

impl<T: Element> Default for Array<T> {
    #[inline]
    fn default() -> Self {
        let mut array = unsafe {
            Self::new_with_uninit(|self_ptr| {
                let ctor = sys::builtin_fn!(array_construct_default);
                ctor(self_ptr, std::ptr::null_mut())
            })
        };

        // SAFETY: We just created this array, and haven't called `init_inner_type` before.
        unsafe { array.init_inner_type() };
        array
    }
}

// T must be GodotType (or subtrait Element), because drop() requires sys_mut(), which is on the GodotFfi trait.
// Its sister method GodotFfi::from_sys_init() requires Default, which is only implemented for T: GodotType.
// This could be addressed by splitting up GodotFfi if desired.
impl<T: Element> Drop for Array<T> {
    #[inline]
    fn drop(&mut self) {
        unsafe {
            let array_destroy = sys::builtin_fn!(array_destroy);
            array_destroy(self.sys_mut());
        }
    }
}

impl<T: Element> GodotType for Array<T> {
    type Ffi = Self;

    type ToFfi<'f>
        = RefArg<'f, Array<T>>
    where
        Self: 'f;

    fn to_ffi(&self) -> Self::ToFfi<'_> {
        RefArg::new(self)
    }

    fn into_ffi(self) -> Self::Ffi {
        self
    }

    fn try_from_ffi(ffi: Self::Ffi) -> Result<Self, ConvertError> {
        Ok(ffi)
    }
}

impl<T: Element> GodotFfiVariant for Array<T> {
    fn ffi_to_variant(&self) -> Variant {
        unsafe {
            Variant::new_with_var_uninit(|variant_ptr| {
                let array_to_variant = sys::builtin_fn!(array_to_variant);
                array_to_variant(variant_ptr, sys::SysPtr::force_mut(self.sys()));
            })
        }
    }

    fn ffi_from_variant(variant: &Variant) -> Result<Self, ConvertError> {
        // SAFETY: if conversion succeeds, we call with_checked_type() afterwards.
        let array = unsafe { Self::unchecked_from_variant(variant) }?;

        // Then, check the runtime type of the array.
        array.with_checked_type()
    }
}

// ----------------------------------------------------------------------------------------------------------------------------------------------
// Conversion traits

// From impls converting values (like [T; N] or Vec<T>) are explicitly not supported, because there's no perf benefit in submitting ownership.
// This is different for PackedArray, which can move values. See also related: https://github.com/godot-rust/gdext/pull/1286.

/// Creates a `Array` from the given Rust array.
impl<T: Element + ToGodot, const N: usize> From<&[T; N]> for Array<T> {
    fn from(arr: &[T; N]) -> Self {
        Self::from(&arr[..])
    }
}

/// Creates a `Array` from the given slice.
impl<T: Element + ToGodot> From<&[T]> for Array<T> {
    fn from(slice: &[T]) -> Self {
        let mut array = Self::new();
        let len = slice.len();
        if len == 0 {
            return array;
        }

        // SAFETY: We fill the array with `Variant::nil()`, however since we're resizing to the size of the slice we'll end up rewriting all
        // the nulls with values of type `T`.
        unsafe { array.as_inner_mut() }.resize(to_i64(len));

        // SAFETY: `array` has `len` elements since we just resized it, and they are all valid `Variant`s. Additionally, since
        // the array was created in this function, and we do not access the array while this slice exists, the slice has unique
        // access to the elements.
        let elements = unsafe { Variant::borrow_slice_mut(array.ptr_mut(0), len) };
        for (element, array_slot) in slice.iter().zip(elements.iter_mut()) {
            *array_slot = element.to_variant();
        }

        array
    }
}

/// Creates a `Array` from an iterator.
impl<T: Element + ToGodot> FromIterator<T> for Array<T> {
    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
        let mut array = Self::new();
        array.extend(iter);
        array
    }
}

/// Extends a `Array` with the contents of an iterator.
impl<T: Element> Extend<T> for Array<T> {
    fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) {
        // Unfortunately the GDExtension API does not offer the equivalent of `Vec::reserve`.
        // Otherwise, we could use it to pre-allocate based on `iter.size_hint()`.
        //
        // A faster implementation using `resize()` and direct pointer writes might still be possible.
        // Note that this could technically also use iter(), since no moves need to happen (however Extend requires IntoIterator).
        for item in iter.into_iter() {
            // self.push(AsArg::into_arg(&item));
            self.push(meta::owned_into_arg(item));
        }
    }
}

/// Converts this array to a strongly typed Rust vector.
impl<T: Element + FromGodot> From<&Array<T>> for Vec<T> {
    fn from(array: &Array<T>) -> Vec<T> {
        let len = array.len();
        let mut vec = Vec::with_capacity(len);

        // SAFETY: Unless `experimental-threads` is enabled, then we cannot have concurrent access to this array.
        // And since we don't concurrently access the array in this function, we can create a slice to its contents.
        let elements = unsafe { Variant::borrow_slice(array.ptr(0), len) };

        vec.extend(elements.iter().map(T::from_variant));

        vec
    }
}

// ----------------------------------------------------------------------------------------------------------------------------------------------
// Iterators

/// An iterator over typed elements of an [`Array`].
///
/// Unlike dictionary iterators, this does not provide a `typed()` method to re-type an untyped `VarArray` iterator.
// Currently doesn't have a `typed()` method like dictionary iterators. Less useful here, as arrays are more often properly typed.
pub struct ArrayIter<'a, T: Element> {
    array: &'a Array<T>,
    next_idx: usize,
}

impl<T: Element + FromGodot> Iterator for ArrayIter<'_, T> {
    type Item = T;

    fn next(&mut self) -> Option<Self::Item> {
        if self.next_idx < self.array.len() {
            let idx = self.next_idx;
            self.next_idx += 1;

            let element_ptr = self.array.ptr_or_null(idx);

            // SAFETY: We just checked that the index is not out of bounds, so the pointer won't be null.
            // We immediately convert this to the right element, so barring `experimental-threads` the pointer won't be invalidated in time.
            let variant = unsafe { Variant::borrow_var_sys(element_ptr) };
            let element = T::from_variant(variant);
            Some(element)
        } else {
            None
        }
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        let remaining = self.array.len() - self.next_idx;
        (remaining, Some(remaining))
    }
}

// TODO There's a macro for this, but it doesn't support generics yet; add support and use it
impl<T: Element> PartialEq for Array<T> {
    #[inline]
    fn eq(&self, other: &Self) -> bool {
        unsafe {
            let mut result = false;
            sys::builtin_call! {
                array_operator_equal(self.sys(), other.sys(), result.sys_mut())
            }
            result
        }
    }
}

impl<T: Element> PartialOrd for Array<T> {
    #[inline]
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        let op_less = |lhs, rhs| unsafe {
            let mut result = false;
            sys::builtin_call! {
                array_operator_less(lhs, rhs, result.sys_mut())
            }
            result
        };

        if op_less(self.sys(), other.sys()) {
            Some(std::cmp::Ordering::Less)
        } else if op_less(other.sys(), self.sys()) {
            Some(std::cmp::Ordering::Greater)
        } else if self.eq(other) {
            Some(std::cmp::Ordering::Equal)
        } else {
            None
        }
    }
}

// ----------------------------------------------------------------------------------------------------------------------------------------------
// Expression macros
// Intra-doc-links use HTML to stay in same module (not switch to prelude when looking at godot::builtin).

/// **Array**: constructs `Array` literals for all possible element types.
///
/// # Type inference
/// There are three related macros, all of which create [`Array<T>`] expressions, but they differ in how the type `T` is inferred:
///
/// - `array!` uses [`AsArg`][crate::meta::AsArg] to push elements. This works when the array's element type `T` is already
///   determined from context -- a type annotation, function parameter, etc. This supports all element types including `Gd<T>` and `Variant`.
/// - [`iarray!`](macro.iarray.html) uses [`AsDirectElement`][crate::meta::AsDirectElement] for (opinionated) type inference from literals.
///   This macro needs no type annotations, however is limited to common types, like `i32`, `&str` (inferred as `GString`), etc.
/// - [`varray!`](macro.varray.html) uses `AsArg<Variant>`, meaning it's like `array!` but inferred as [`VarArray`].
///
/// # Examples
/// ```no_run
/// # use godot::prelude::*;
/// // array! requires type context (e.g. annotation, return type, etc.).
/// // The same expression can be used to initialize different array types:
///
/// let ints: Array<i8>      = array![3, 1, 4];
/// let ints: Array<i64>     = array![3, 1, 4];
/// let ints: Array<Variant> = array![3, 1, 4];
///
/// let strs: Array<GString>    = array!["a", "b"];
/// let strs: Array<StringName> = array!["a", "b"];
/// let strs: Array<Variant>    = array!["a", "b"];
///
/// // More strict inference with iarray! and varray! macros:
///
/// let ints = iarray![3, 1, 4];  // Array<i32>.
/// let strs = iarray!["a", "b"]; // Array<GString>.
///
/// let strs = varray!["a", "b"]; // VarArray.
/// ```
///
/// # See also
/// For dictionaries, a similar macro [`dict!`](macro.dict.html) exists.
///
/// To construct slices of variants, use [`vslice!`](macro.vslice.html).
#[macro_export]
macro_rules! array {
    ($($elements:expr_2021),* $(,)?) => {
        {
            let mut array = $crate::builtin::Array::default();
            $(array.push($elements);)*
            array
        }
    };
}

/// **I**nferred **array**: constructs `Array` literals without ambiguity.
///
/// See [`array!`](macro.array.html) for docs and examples.
#[macro_export]
macro_rules! iarray {
    ($($elements:expr_2021),* $(,)?) => {
        {
            let mut array = $crate::builtin::Array::default();
            $(array.__macro_push_direct($elements);)*
            array
        }
    };
}

/// **V**ariant **array**: constructs [`VarArray`] literals.
///
/// See [`array!`](macro.array.html) for docs and examples.
#[macro_export]
macro_rules! varray {
    // Uses `AsArg` semantics, consistent with `array!`.
    ($($elements:expr_2021),* $(,)?) => {
        {
            let mut array = $crate::builtin::VarArray::default();
            $(
                array.push($elements);
            )*
            array
        } as $crate::builtin::VarArray
        // The `as` cast is necessary for Deref coercion to AnyArray; type inference doesn't seem to pick it up otherwise.
    };
}

/// Constructs a slice of [`Variant`] literals, useful for passing to vararg functions.
///
/// Many APIs in Godot have variable-length arguments. GDScript can call such functions by simply passing more arguments, but in Rust,
/// the parameter type `&[Variant]` is used.
///
/// This macro creates a [slice](https://doc.rust-lang.org/std/primitive.slice.html) of `Variant` values.
///
/// # Examples
/// ## Variable number of arguments
/// ```no_run
/// # use godot::prelude::*;
/// let slice: &[Variant] = vslice![42, "hello", true];
/// let concat: GString = godot::global::str(slice);
/// ```
/// _In practice, you might want to use [`godot_str!`][crate::global::godot_str] instead of `str()`._
///
/// ## Dynamic function call via reflection
/// NIL can still be passed inside `vslice!`, just use `Variant::nil()`.
/// ```no_run
/// # use godot::prelude::*;
/// # fn some_object() -> Gd<Object> { unimplemented!() }
/// let mut obj: Gd<Object> = some_object();
///
/// obj.call("some_method", vslice![
///     Vector2i::new(1, 2),
///     Variant::nil(),
/// ]);
/// ```
///
/// # See also
/// To create typed and untyped `Array`s, use the [`array!`] macro and its variants.
///
/// For dictionaries, a similar macro [`vdict!`] exists.
#[macro_export]
macro_rules! vslice {
    // Note: use to_variant() and not Variant::from(), as that works with both references and values.
    ($($elements:expr_2021),* $(,)?) => {
        &[$( $crate::meta::ToGodot::to_variant(&$elements), )*]
    };
}

// ----------------------------------------------------------------------------------------------------------------------------------------------
// Serde support

#[cfg(feature = "serde")] #[cfg_attr(published_docs, doc(cfg(feature = "serde")))]
mod serialize {
    use std::marker::PhantomData;

    use serde::de::{SeqAccess, Visitor};
    use serde::ser::SerializeSeq;
    use serde::{Deserialize, Deserializer, Serialize, Serializer};

    use super::*;

    impl<T> Serialize for Array<T>
    where
        T: Element + Serialize,
    {
        #[inline]
        fn serialize<S>(
            &self,
            serializer: S,
        ) -> Result<<S as Serializer>::Ok, <S as Serializer>::Error>
        where
            S: Serializer,
        {
            let mut sequence = serializer.serialize_seq(Some(self.len()))?;
            for e in self.iter_shared() {
                sequence.serialize_element(&e)?
            }
            sequence.end()
        }
    }

    impl<'de, T> Deserialize<'de> for Array<T>
    where
        T: Element + Deserialize<'de>,
    {
        #[inline]
        fn deserialize<D>(deserializer: D) -> Result<Self, <D as Deserializer<'de>>::Error>
        where
            D: Deserializer<'de>,
        {
            struct ArrayVisitor<T>(PhantomData<T>);
            impl<'de, T> Visitor<'de> for ArrayVisitor<T>
            where
                T: Element + Deserialize<'de>,
            {
                type Value = Array<T>;

                fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
                    formatter.write_str(std::any::type_name::<Self::Value>())
                }

                fn visit_seq<A>(
                    self,
                    mut seq: A,
                ) -> Result<Self::Value, <A as SeqAccess<'de>>::Error>
                where
                    A: SeqAccess<'de>,
                {
                    let mut vec = seq.size_hint().map_or_else(Vec::new, Vec::with_capacity);
                    while let Some(val) = seq.next_element::<T>()? {
                        vec.push(val);
                    }
                    Ok(Self::Value::from(vec.as_slice()))
                }
            }

            deserializer.deserialize_seq(ArrayVisitor::<T>(PhantomData))
        }
    }
}

// ----------------------------------------------------------------------------------------------------------------------------------------------
// Tests

/// Verifies that `AnyArray::try_cast*()` cannot be called on concrete arrays.
///
/// > error[E0507]: cannot move out of dereference of `godot::prelude::Array<i64>`
///
/// ```compile_fail
/// use godot::prelude::*;
/// let a: Array<i64> = array![1, 2, 3];
/// a.try_cast_var_array();
/// ```
///
/// ```compile_fail
/// use godot::prelude::*;
/// let a: VarArray = varray![1, 2, 3];
/// a.try_cast_array::<i64>();
/// ```
///
/// This works:
/// ```no_run
/// use godot::prelude::*;
/// let a: VarArray = varray![1, 2, 3];
/// a.upcast_any_array().try_cast_array::<i64>();
/// ```
fn __cannot_downcast_from_concrete() {}

#[test]
fn correct_variant_t() {
    assert!(Array::<Variant>::has_variant_t());
    assert!(!Array::<i64>::has_variant_t());
}