Module mpython.core

class AnyDelayedArray(AnyMatlabArray):
    """
    This is an object that we return when we don't know how an indexed
    element will be used yet.

    It decides whether it is a Struct, Cell or Array based on the
    type of indexing that is used.

    In Matlab:

    * `a(x,y)   = num`  indicates that `a` is a numeric array;
    * `a(x,y)   = cell` indicates that `a` is a cell array;
    * `a{x,y}   = any`  indicates that `a` is a cell array;
    * `a(x,y).f = any`  indicates that `a` is a struct array;
    * `a.f      = any`  indicates that `a` is a struct.

    These indexing operations can be chained, so in
    `a(x).b.c{y}.d(z) = 2`:

    * `a`    is a struct array;
    * `b`    is a struct;
    * `c`    is a cell;
    * `c{y}` is a struct
    * `d`    is a numeric array.

    In Python, there is only one type of indexing (`[]`). This is a problem as
    we cannot differentiate `a{x}.b = y` — where `a` is a cell that contains
    a struct — from `a(x).b = y` — where `a` is a struct array.

    One solution may be to abuse the "call" operator `()`, so that it returns a
    cell. This would work in some situations (`a[x].b = y` is a struct array,
    whereas `a(x).b = y` is a cell of struct). However, the statement
    `a(x) = y` (which would correspond to matlab's `a{x} = y`) is not valid
    python syntax. Furthermore, it would induce a new problem, as cells could
    not be differentiated from function handles, in some cases.

    Instead, the use of brackets automatically transforms the object into
    either:

    * a `Struct` (in all "get" cases, and in the "set" context `a[x] = y`,
      when `y` is either a `dict` or a `Struct`); or
    * an `Array` (in the "set" context `a[x] = y`, when `y` is neither a
      `dict` nor a `Struct`).

    Alternatively, if the user wishes to specify which type the object should
    take, we implement the properties `as_cell`, `as_struct` and `as_num`.

    Therefore:

    * `a[x,y]             = num`    : `a` is a numeric array;
    * `a[x,y]             = struct` : `a` is a numeric array;
    * `a[x,y].f           = any`    : `a` is a struct array;
    * `a(x,y).f           = any`    : `a` is a cell array containing a struct;
    * `a.f                = any`    : `a` is a struct.

    And explictly:

    * `a.as_cell[x,y]     = any`    : `a` is a cell array;
    * `a.as_struct[x,y].f = any`    : `a` is a struct array;
    * `a.as_cell[x,y].f   = any`    : `a` is a cell array containing a struct;
    * `a.as_num[x,y]      = num`    : `a` is a numeric array.
    """

    _ATTRIBUTES = ("_parent", "_index", "_future", "_finalized")

    def __init__(self, parent, *index):
        """
        Parameters
        ----------
        parent : ndarray | dict
            Reference to the object that will eventually contain
            this element.

            * If the containing array is a `Cell`, `parent` should be a
              `ndarray` view of that cell, and `index` should be a
              [tuple of] int.
            * If the containing array is a `Struct`, `parent` should be a
              `dict`, and `index` should be a string.
        index : str | [tuple of] int
            Index into the parent where this element will be inserted.
        """
        super().__init__()
        self._parent = parent  # reference to parent container
        self._index = index  # index into parent container
        self._future = None  # future array
        self._finalized = False  # whether this array has been finalized

    @property
    def _final(self):
        self._finalize()
        return self._future

    def _finalize(self):
        if self._finalized:
            return

        if self._future is None:
            # FIXME: I am not entirely sure this should ever happen
            self._future = _empty_array()

        # if future array is wrapped, unwrap it
        if isinstance(self._future, WrappedDelayedArray):
            self._future = self._future._future
            if hasattr(self._future, "_delayed_wrapper"):
                del self._future._delayed_wrapper

        # set value in parent
        parent = self._parent
        for index in self._index[:-1]:
            parent = parent[index]
        parent[self._index[-1]] = self._future

        # finalize parent if needed
        if hasattr(self._parent, "_final"):
            self._parent = self._parent._final

        self._finalized = True

    def _error_is_not_finalized(self, *args, **kwargs):
        raise IndexOrKeyOrAttributeError(
            "This DelayedArray has not been finalized, and you are "
            "attempting to use it in a way that may break its finalization "
            "cycle. It most likely means that you are indexing out-of-bounds "
            "without *setting* the out-of-bound value. "
            "Correct usage: `a.b(i).c = x` | Incorrect usage: `x = a.b(i).c`."
        )

    # Kill all operators
    __str__ = __repr__ = _error_is_not_finalized
    __bool__ = __float__ = __int__ = _error_is_not_finalized
    __ceil__ = __floor__ = __round__ = __trunc__ = _error_is_not_finalized
    __add__ = __iadd__ = __radd__ = _error_is_not_finalized
    __sub__ = __isub__ = __rsub__ = _error_is_not_finalized
    __mul__ = __imul__ = __rmul__ = _error_is_not_finalized
    __truediv___ = __itruediv___ = __rtruediv___ = _error_is_not_finalized
    __floordiv___ = __ifloordiv___ = __rfloordiv___ = _error_is_not_finalized
    __eq__ = __ne__ = _error_is_not_finalized
    __gt__ = __ge__ = __lt__ = __le__ = _error_is_not_finalized
    __abs__ = __neg__ = __pos__ = _error_is_not_finalized
    __pow__ = __ipow__ = __rpow__ = _error_is_not_finalized
    __mod__ = __imod__ = __rmod__ = _error_is_not_finalized
    __divmod__ = __idivmod__ = __rdivmod__ = _error_is_not_finalized
    __contains__ = _error_is_not_finalized

    def __getattribute__(self, name):
        # Do not allow any attribute to be accessed except for those
        # explicitly allowed by the AnyDelayedArray class.
        # This is so no "computation" is peformed on DelayedCell,
        # DelayedStruct, etc.
        if name.startswith("_"):
            return super().__getattribute__(name)
        if name not in self.__dict__ and name not in AnyDelayedArray.__dict__:
            return self._error_is_not_finalized()
        return super().__getattribute__(name)

    # --- Promise type -------------------------------------------------

    @property
    def as_cell(self) -> "DelayedCell":
        if self._future is None:
            self._future = DelayedCell((), self._parent, *self._index)
        if not isinstance(self._future, DelayedCell):
            raise TypeError(
                f"{type(self._future)} cannot be interpreted as a Cell"
            )
        return self._future

    @property
    def as_struct(self) -> "DelayedStruct":
        if self._future is None:
            self._future = DelayedStruct((), self._parent, *self._index)
        if not isinstance(self._future, DelayedStruct):
            raise TypeError(
                f"{type(self._future)} cannot be interpreted as a Struct"
            )
        return self._future

    @property
    def as_num(self) -> "DelayedArray":
        if self._future is None:
            self._future = DelayedArray([0], self._parent, *self._index)
        if not isinstance(self._future, DelayedArray):
            raise TypeError(
                f"{type(self._future)} cannot be interpreted as a Array"
            )
        return self._future

    def as_obj(self, obj):
        MatlabClass = _imports.MatlabClass
        if (
            self._future is not None and
            not isinstance(self._future, MatlabClass)
        ):
            raise TypeError(
                f"{type(self._future)} cannot be interpreted as a {type(obj)}"
            )
        self._future = obj
        return self._future

    # --- Guess promised type ------------------------------------------

    def __call__(self, *index):
        return self.as_cell(*index)

    def __getitem__(self, index):
        return self.as_struct[index]

    def __getattr__(self, key):
        return self.as_struct[key]

    def __setitem__(self, index, value):
        Array = _imports.Array
        Cell = _imports.Cell
        MatlabClass = _imports.MatlabClass
        Struct = _imports.Struct

        if isinstance(index, str):
            arr = self.as_struct

        elif isinstance(value, MatlabClass):
            if index not in (0, -1):
                raise NotImplementedError(
                    "Implicit advanced indexing not implemented for",
                    type(value)
                )
            self.as_obj(value)
            return self._finalize()

        elif isinstance(value, (dict, Struct)):
            arr = self.as_struct
        elif isinstance(value, (tuple, list, set, Cell)):
            arr = self.as_cell
        elif isinstance(value, (int, float, np.number, Array)):
            arr = self.as_num
        elif isinstance(value, np.ndarray):
            if issubclass(value.dtype.type, np.number):
                arr = self.as_num
            else:
                arr = self.as_cell
        else:
            arr = self.as_cell

        arr[index] = value
        return self._finalize()  # Setter -> we can trigger finalize

    def __setattr__(self, key, value):
        if key in type(self)._ATTRIBUTES:
            return super().__setattr__(key, value)
        self.as_struct[key] = value
        return self._finalize()  # Setter -> we can trigger finalize

class AnyMatlabArray(MatlabType):
    """Base class for all matlab-like arrays (numeric, cell, struct)."""

    @property
    def as_num(self):
        raise TypeError(
            f"Cannot interpret a {type(self).__name__} as a numeric array"
        )

    @property
    def as_cell(self):
        raise TypeError(
            f"Cannot interpret a {type(self).__name__} as a cell"
        )

    @property
    def as_struct(self):
        raise TypeError(
            f"Cannot interpret a {type(self).__name__} as a struct"
        )

    # TODO: `as_obj` for object arrays?

class AnyWrappedArray(AnyMatlabArray):
    """Base class for wrapped numpy/scipy arrays."""

    @classmethod
    def _parse_args(cls, *args, **kwargs):
        """
        This function is used in the `__new__` constructor of
        Array/Cell/Struct.

        It does some preliminary preprocesing to reduces the number of
        cases that must be handled by `__new__`.

        In particular:

        * It converts multiple integer arguments to a single list[int]
        * It extracts the shape or object to copy, if there is one.
        * It convert positional dtype/order into keywords.

        Returns
        -------
        mode : {"shape", "obj"}
        arg : array-like | list[int]
        kwargs : dict
        """
        __has_dtype = kwargs.pop("__has_dtype", True)
        __has_order = kwargs.pop("__has_order", True)

        # Detect integer arguments
        args, shape, obj = list(args), [], None
        while args and isinstance(args[0], int):
            shape.append(args.pop(0))

        # If no integer arguments, the first argument (if it exists)
        # must be a shape or an array-like object to convert.
        if not shape:
            # Catch case where no size/array is passed and the first
            # argument is a data type.
            if args and not isinstance(args[0], (str, np.dtype, type)):
                obj = args.pop(0)

        # If there are positional arguments remaining, they are:
        # 1. dtype
        if args and __has_dtype:
            if "dtype" in kwargs:
                raise TypeError(
                    f"{cls.__name__}() got multiple values for argument "
                    f"'dtype'"
                )
            kwargs["dtype"] = args.pop(0)
        # 2. order {"C", "F"}
        if args and __has_order:
            if "order" in kwargs:
                raise TypeError(
                    f"{cls.__name__}() got multiple values for argument "
                    f"'order'"
                )
            kwargs["order"] = args.pop(0)
        # 3. no other positionals allowed -> raise
        if args:
            raise TypeError(
                f"{cls.__name__}() takes from 1 to 3 positional "
                "arguments but more were given"
            )

        # If we found an object and it is a generator
        # (= an iterable that has no `len`), copy its values into a list.
        if hasattr(obj, "__iter__") and not hasattr(obj, "__len__"):
            # save iterator values in a list
            obj = list(obj)

        # If obj is a list[int] -> it is a shape
        if (
            not shape
            and isinstance(obj, (list, tuple))
            and all(isinstance(x, int) for x in obj)
        ):
            shape, obj = obj, None

        mode = "obj" if obj is not None else "shape"
        arg = obj if obj is not None else shape
        return mode, arg, kwargs

class DelayedArray(WrappedDelayedArray):
    """
    An `Array` that will insert itself in its parent later.

    See `AnyDelayedArray`.
    """

    def __init__(self, shape, parent, *index):
        """
        Parameters
        ----------
        shape : list[int]
            Shape of the future numeric array.
        parent : Struct | Cell | AnyDelayedArray
            Parent object that contains the future object.
        *index : int | str
            Index of the future object in its parent.
        """
        Array = _imports.Array
        future = Array.from_shape(shape)
        future._delayed_wrapper = self
        super().__init__(future, parent, *index)

class DelayedCell(WrappedDelayedArray):
    """
    A `Cell` that will insert itself in its parent later.

    See `AnyDelayedArray`.
    """

    def __init__(self, shape, parent, *index):
        """
        Parameters
        ----------
        shape : list[int]
            Shape of the future cell array.
        parent : Struct | Cell | AnyDelayedArray
            Parent object that contains the future object.
        *index : int | str
            Index of the future object in its parent.
        """
        Cell = _imports.Cell
        future = Cell.from_shape(shape)
        future._delayed_wrapper = self
        super().__init__(future, parent, *index)

        # Insert delayed arrays instead of the usual defaults
        opt = dict(
            flags=["refs_ok", "zerosize_ok", "multi_index"],
            op_flags=["writeonly", "no_broadcast"],
        )
        arr = np.ndarray.view(self._future, np.ndarray)
        with np.nditer(arr, **opt) as iter:
            for elem in iter:
                elem[()] = AnyDelayedArray(self, iter.multi_index)

class DelayedStruct(WrappedDelayedArray):
    """
    A `Struct` that will insert itself in its parent later.

    See `AnyDelayedArray`.
    """

    def __init__(self, shape, parent, *index):
        """
        Parameters
        ----------
        shape : list[int]
            Shape of the future struct array.
        parent : Struct | Cell | AnyDelayedArray
            Parent object that contains the future object.
        *index : int | str
            Index of the future object in its parent.
        """
        Struct = _imports.Struct
        future = Struct.from_shape(shape)
        future._delayed_wrapper = self
        super().__init__(future, parent, *index)

class MatlabType:
    """Generic type for objects that have an exact matlab equivalent."""

    @classmethod
    def from_any(cls, other, **kwargs):
        """
        Convert python/matlab objects to `MatlabType` objects
        (`Cell`, `Struct`, `Array`, `MatlabClass`).

        !!! warning "Conversion is performed in-place when possible."
        """
        # Circular import
        Array = _imports.Array
        Cell = _imports.Cell
        MatlabClass = _imports.MatlabClass
        MatlabFunction = _imports.MatlabFunction
        SparseArray = _imports.SparseArray
        Struct = _imports.Struct
        AnyDelayedArray = _imports.AnyDelayedArray

        # Conversion rules:
        # - we do not convert to matlab's own array types
        #   (`matlab.double`, etc);
        # - we do not convert to types that can be passed directly to
        #   the matlab runtime;
        # - instead, we convert to python types that mimic matlab types.
        _from_any = partial(cls.from_any, **kwargs)
        _runtime = kwargs.pop("_runtime", None)

        if isinstance(other, MatlabType):
            if isinstance(other, AnyDelayedArray):
                other._error_is_not_finalized()
            return other

        if isinstance(other, dict):
            if "type__" in other:
                type__ = other["type__"]

                if type__ == "none":
                    # MPython returns this when catching a function
                    # that should return no values but is asked for one.
                    return None

                elif type__ == "emptystruct":
                    return Struct.from_shape([0])

                elif type__ == "structarray":
                    # MPython returns a list of dictionaries in data__
                    # and the array shape in size__.
                    return Struct._from_runtime(other, _runtime)

                elif type__ == "cell":
                    # MPython returns a list of dictionaries in data__
                    # and the array shape in size__.
                    return Cell._from_runtime(other, _runtime)

                elif type__ == "object":
                    # MPython returns the object's fields serialized
                    # in a dictionary.
                    return MatlabClass._from_runtime(other, _runtime)

                elif type__ == "sparse":
                    # MPython returns the coordinates and values in a dict.
                    return SparseArray._from_runtime(other, _runtime)

                elif type__ == "char":
                    # Character array that is not a row vector
                    # (row vector are converted to str automatically)
                    # MPython returns all rows in a (F-ordered) cell in data__
                    # Let's use the cell constructor to return a cellstr.
                    # -> A cellstr is a column vector, not a row vector
                    size = np.asarray(other["size__"]).tolist()[0]
                    size = size[:-1] + [1]
                    other["type__"] = "cell"
                    other["size__"] = np.asarray([size])
                    return Cell._from_runtime(other, _runtime)

                else:
                    raise ValueError("Don't know what to do with type", type__)

            else:
                other = type(other)(
                    zip(other.keys(), map(_from_any, other.values()))
                )
                return Struct.from_any(other)

        if isinstance(other, (list, tuple, set)):
            # nested tuples are cells of cells, not cell arrays
            if _runtime:
                return Cell._from_runtime(other, _runtime)
            else:
                return Cell.from_any(other)

        if isinstance(other, (np.ndarray, int, float, complex, bool)):
            # [array of] numbers -> Array
            if _runtime:
                return Array._from_runtime(other, _runtime)
            else:
                return Array.from_any(other)

        if isinstance(other, str):
            return other

        if isinstance(other, bytes):
            return other.decode()

        if other is None:
            # This can happen when matlab code is called without `nargout`
            return other

        matlab = _import_matlab()
        if matlab and isinstance(other, matlab.object):
            return MatlabFunction._from_runtime(other, _runtime)

        if type(other) in _matlab_array_types():
            return Array._from_runtime(other, _runtime)

        if hasattr(other, "__iter__"):
            # Iterable -> let's try to make it a cell
            return cls.from_any(list(other), _runtime=_runtime)

        raise TypeError(f"Cannot convert {type(other)} into a matlab object.")

    @classmethod
    def _from_runtime(cls, obj, _runtime):
        return cls.from_any(obj, _runtime=_runtime)

    @classmethod
    def _to_runtime(cls, obj):
        """
        Convert object to representation that the matlab runtime understands.
        """
        to_runtime = cls._to_runtime
        from ..utils import sparse  # FIXME: Circular import

        if isinstance(obj, MatlabType):
            # class / structarray / cell
            return obj._as_runtime()

        elif isinstance(obj, (list, tuple, set)):
            return type(obj)(map(to_runtime, obj))

        elif isinstance(obj, dict):
            if "type__" in obj:
                return obj
            return type(obj)(zip(obj.keys(), map(to_runtime, obj.values())))

        elif isinstance(obj, np.ndarray):
            obj = np.asarray(obj)
            if obj.dtype in (object, dict):
                shape, dtype = obj.shape, obj.dtype
                obj = np.fromiter(map(to_runtime, obj.flat), dtype=dtype)
                obj = obj.reshape(shape)
                return obj.tolist()
            return obj

        elif sparse and isinstance(obj, sparse.sparray):
            SparseArray = _imports.SparseArray
            return SparseArray.from_any(obj)._as_runtime()

        else:
            # TODO: do we want to raise if the type is not supported by matlab?
            #
            # Valid types for matlab bindings:
            #   - bool, int, float, complex, str, bytes, bytearray
            #
            # Valid matlab types that we have already dealt with:
            #   - list, tuple, set, dict, ndarray
            #
            # All other values/types are invalid (including `None`!)
            return obj

    def _as_runtime(self):
        raise NotImplementedError

    def _as_matlab_object(self):
        # Backward compatibility
        # FIXME: Or just keep `_as_matlab_object` and remove `_as_runtime`?
        return self._as_runtime()

class WrappedArray(np.ndarray, AnyWrappedArray):
    """
    Base class for "arrays of things" (`Array`, `Cell`, `Struct`)
    """

    # Value used to initalize empty arrays
    @classmethod
    def _DEFAULT(cls, shape: list = ()):
        raise NotImplementedError

    def __str__(self):
        fmt = {"all": str}  # use str instead of repr for items
        return np.array2string(self, separator=", ", formatter=fmt)

    def __repr__(self):
        # close to np.array_repr, but hides dtype.
        pre = type(self).__name__ + "("
        suf = ")"
        arr = np.array2string(self, prefix=pre, suffix=suf, separator=", ")
        return pre + arr + suf

    def __bool__(self):
        # NumPy arrays do not lower to True/False in a boolean context.
        # We do lower our matlab equivalent using all()
        return np.ndarray.view(np.all(self), np.ndarray).item()

    def __iter__(self):
        # FIXME:
        #   ndarray.__iter__ seems to call __getattr__, which leads
        #   to infinite resizing.
        #   This overload seems to fix it, but may not be computationally
        #   optimal.
        for i in range(len(self)):
            yield self[i]

    def __getitem__(self, index):
        """Resize array if needed, then fallback to `np.ndarray` indexing."""
        try:
            return super().__getitem__(index)
        except IndexError:
            # We return a delayed version of the current type, with the
            # same shape as the requested view. Its elements will only
            # be inserted into the original object (self) is the view
            # is properly finalized by an eventual call to __setitem__
            # or __setattr__.
            return self._return_delayed(index)

    def __setitem__(self, index, value):
        """Resize array if needed, then fallback to `np.ndarray` indexing."""
        value = MatlabType.from_any(value)
        try:
            return super().__setitem__(index, value)
        except (IndexError, ValueError):
            self._resize_for_index(index)
            return super().__setitem__(index, value)

    def __delitem__(self, index):
        if isinstance(index, tuple):
            raise TypeError(
                "Multidimensional indices are not supported in `del`."
            )

        # --- list: delete sequentially, from tail to head -------------
        if hasattr(index, "__iter__"):
            index = (len(self) + i if i < 0 else i for i in index)
            index = sorted(index, reverse=True)
            for i in index:
                del self[i]

        # --- slice: skip the entire slice, if possible ----------------
        elif isinstance(index, slice):
            start, stop, step = index.start, index.stop, index.step

            # --- let's make the slice parameters a bit more useful ---
            step = step or 1
            # compute true start
            if start is None:
                if step < 0:
                    start = len(self) - 1
                else:
                    start = 0
            if start < 0:
                start = len(self) + start
            # compute stop in terms of "positive indices"
            # (where -1 really means -1, and not n-1)
            if stop is not None:
                if stop < 0:
                    stop = len(self) + stop
            else:
                stop = len(self) if step > 0 else -1
            stop = min(stop, len(self)) if step > 0 else max(stop, -1)
            # align stop with steps
            stop = start + int(np.ceil(abs(stop - start) / abs(step))) * step
            # compute true inclusive stop
            stop_inclusive = stop - step
            # ensure step is positive
            if step < 0:
                start, stop_inclusive, step = stop_inclusive, start, abs(step)

            # --- if non consecutive, fallback to sequential ---
            if step != 1:
                index = range(start, stop + 1, step)
                del self[index]

            # --- otherwise, skip the entire slice ---
            else:
                nb_del = 1 + stop_inclusive - start
                new_shape = list(np.shape(self))
                new_shape[0] -= nb_del
                self[start:-nb_del] = self[stop_inclusive:]
                np.ndarray.resize(self, new_shape, refcheck=False)

        # --- int: skip a single element -------------------------------
        else:
            index = int(index)
            if index < 0:
                index = len(self) + index
            new_shape = list(np.shape(self))
            new_shape[0] -= 1
            self[index:-1] = self[index + 1:]
            np.ndarray.resize(self, new_shape, refcheck=False)

    def _resize_for_index(self, index, set_default=True):
        """
        Resize the array so that the (multidimensional) index is not OOB.

        We only support a restricted number of cases:

        * Index should only contain integers and slices
          (no smart indexing, no new axis, no ellipsis)
        * Only integer indices are used to compute the new size.
          This is to be consistent with numpy, where slice-indexing never
          raises `IndexError` (but instead returns the overlap between
          the array and the slice -- eventually empty).

        Other cases could be handled but require much more complicated logic.
        """
        input_shape = self.shape
        if not isinstance(index, tuple):
            index = (index,)
        index, new_index = list(index), []
        shape, new_shape = list(np.shape(self)), []
        axis = -1
        while index:
            next_index = index.pop(0)
            if shape:
                next_shape = shape.pop(0)
            else:
                next_shape = 1
            axis += 1
            if isinstance(next_index, int):
                if next_index < 0:
                    next_index = next_shape + next_index
                if next_index >= next_shape:
                    next_shape = next_index + 1
            elif isinstance(next_index, slice):
                # FIXME: this is not exactly right when abs(step) != 1
                step = next_index.step or 1
                start = next_index.start
                stop = next_index.stop
                if start is not None:
                    start = next_shape + start if start < 0 else start
                if stop is not None:
                    stop = next_shape + stop if stop < 0 else stop
                if step < 0:
                    max_index = start
                else:
                    max_index = stop
                if max_index is None:
                    max_index = next_shape
                if max_index > next_shape:
                    next_shape = max_index
            elif not isinstance(next_index, slice):
                raise TypeError(
                    "Can only automatically resize cell if simple "
                    "indexing (int, slice) is used."
                )
            new_index.append(next_index)
            new_shape.append(next_shape)
        new_shape = new_shape + shape
        if not input_shape:
            # We risk erasing the original scalar whn setting the
            # defaults, so we save it and reinsert it at the end.
            scalar = np.ndarray.view(self, np.ndarray).item()
        np.ndarray.resize(self, new_shape, refcheck=False)
        if set_default:
            arr = np.ndarray.view(self, np.ndarray)
            view_index = tuple(slice(x, None) for x in input_shape)
            view_shape = arr[view_index].shape
            new_data = self._DEFAULT(view_shape)
            arr[view_index] = new_data
            if not input_shape:
                # Insert back scalar in the first position.
                scalar_index = (0,) * arr.ndim
                arr[scalar_index] = scalar

    def _return_delayed(self, index):
        Cell = _imports.Cell
        Struct = _imports.Struct

        if not isinstance(index, tuple):
            index = (index,)

        #   Resize as if we were already performing a valid __setitem__.
        #   This helps us guess the shape of the view.
        #   Also, we'll hopefully be able to use the allocated space
        #   later if the caller did not mess up their syntax, so there's
        #   not much wasted performance.
        shape = self.shape
        self._resize_for_index(index, set_default=False)

        #   Ensure that the indexed view is an array, not a single item.
        index_for_view = index
        if ... not in index_for_view:
            index_for_view = index_for_view + (...,)

        sub_shape = np.ndarray.view(self, np.ndarray)[index_for_view].shape

        #   Now, undo resize so that if the caller's syntax is wrong and
        #   an exception is raised (and caught), it's as if nothing ever
        #   happened.
        np.ndarray.resize(self, shape, refcheck=False)

        #   If self is wrapped in a DelayedCell/DelayedStruct,
        #   reference wrapper instead of self.
        parent = getattr(self, "_delayed_wrapper", self)

        if isinstance(self, Cell):
            if sub_shape == ():
                return AnyDelayedArray(parent, index)
            else:
                return DelayedCell(sub_shape, parent, index)

        elif isinstance(self, Struct):
            return DelayedStruct(sub_shape, parent, index)

        else:
            #   In numeric arrays, only seeting OOB items is allowed.
            #   Getting OOB items should raise an error, which this
            #   call to the ndarray accessor will do.
            return super().__getitem__(index)

class WrappedDelayedArray(AnyDelayedArray):
    """
    Base class for future objects with known type.

    See `DelayedStruct`, `DelayedCell`, `DelayedArray`.
    """

    def __init__(self, future, parent, *index):
        """
        Parameters
        ----------
        future : Struct | Cell | Array
            Concrete object that will be inserted in the parent later.
        parent : Struct | Cell | AnyDelayedArray
            Parent object that contains the future object.
        *index : int | str
            Index of the future obect in its parent.
        """
        super().__init__(parent, *index)
        self._future = future

    def __call__(self, *index):
        return self._future.__call__(*index)

    def __getitem__(self, index):
        return self._future.__getitem__(index)

    def __getattr__(self, key):
        return self._future.__getattr__(key)

    def __setitem__(self, index, value):
        self._future.__setitem__(index, value)
        self._finalize()

    def __setattr__(self, key, value):
        if key in type(self)._ATTRIBUTES:
            return super().__setattr__(key, value)
        self._future.__setattr__(key, value)
        self._finalize()

class _DictMixin(MutableMapping):
    # NOTE:
    #
    #   Making Struct inherit from MutableMapping is a bit hacky
    #   because only scalar Struct implement a proper mapping protocol.
    #   For non-scalar Struct arrays, iteration is over array elements
    #   (not keys), as are `__len__`, `__contains__`, `__eq__`, etc.
    #
    #   The only abstract methods from MutableMapping are:
    #   * __getitem__   -> implemented in Struct
    #   * __setitem__   -> implemented in Struct
    #   * __delitem__   -> implemented in Struct
    #   * __len__       -> !! double meaning, implemented here
    #   * __iter__      -> !! double meaning, implemented here
    #
    #   MutableSequence implements the following non-abstract methods,
    #   but we overload them for speed:
    #   * __contains__  -> !! double meaning
    #   * __eq__        -> !! double meaning -> implemented in np.ndarray
    #   * __ne__        -> !! double meaning -> implemented in np.ndarray
    #   * keys          -> implemented here
    #   * items         -> implemented here
    #   * values        -> implemented here
    #   * get           -> implemented in Struct
    #   * pop           -> implemented in Struct
    #   * popitem       -> implemented in Struct
    #   * clear         -> implemented in Struct
    #   * update        -> implemented in Struct
    #   * setdefault    -> implemented in Struct

    # --- views --------------------------------------------------------
    class KeysView(KeysView):
        def __init__(self, parent):
            self._parent = parent

        def __len__(self):
            return len(self._parent._allkeys())

        def __iter__(self):
            return iter(self._parent._allkeys())

        def __contains__(self, key):
            return key in self._parent._allkeys()

        def __repr__(self):
            return f"dict_keys({list(self)})"

        __str__ = __repr__

    class ValuesView(ValuesView):
        def __init__(self, parent):
            self._parent = parent

        def __len__(self):
            return len(self._parent.as_dict().values())

        def __iter__(self):
            return iter(self._parent.as_dict().values())

        def __contains__(self, value):
            return value in self._parent.as_dict().values()

        def __repr__(self):
            return f"dict_values({list(self)})"

        __str__ = __repr__

    class ItemsView(ItemsView):
        def __init__(self, parent):
            self._parent = parent

        def __len__(self):
            return len(self._parent.as_dict().items())

        def __iter__(self):
            return iter(self._parent.as_dict().items())

        def __contains__(self, item):
            return item in self._parent.as_dict().items()

        def __repr__(self):
            return f"dict_items({list(self)})"

        __str__ = __repr__

    # --- magic --------------------------------------------------------

    def __len__(self):
        if self.ndim:
            return np.ndarray.__len__(self)
        else:
            return len(self.keys())

    def __contains__(self, key):
        if self.ndim:
            return np.ndarray.__contains__(self, key)
        else:
            return key in self.keys()

    def __iter__(self):
        if self.ndim:
            return np.ndarray.__iter__(self)
        else:
            return iter(self.keys())

    def __getitem__(self, key):
        if key in self.keys():
            # NOTE
            #   If some of the dictionaries in the array do not have
            #   their field `key` properly set, we assign an empty
            #   numeric array (same default value as in matlab).

            arr = np.ndarray.view(self, np.ndarray)
            opt = dict(flags=["refs_ok", "zerosize_ok"], op_flags=["readonly"])
            with np.nditer(arr, **opt) as iter:
                for elem in iter:
                    elem.item().setdefault(key, _empty_array())

            # NOTE
            #   We then defer to `as_dict`

            return self.as_dict(keys=[key])[key]

        else:
            # NOTE
            #   We return a new (delayed) struct, whose elements under
            #  `key` are delayed arrays that point to `self` (and *not*
            #   to the delayed struct). This way, when the objects
            #   implicitely assigned to `key` get finalized, they are
            #   inserted into the orginal struct (`self`), not into
            #   the delayed struct (`delayed`).
            #
            #   We do not need to use a `DelayedStruct` here.
            parent = getattr(self, "_delayed_wrapper", self)

            Struct = _imports.Struct

            delayed = Struct(self.shape)
            opt = dict(
                flags=["refs_ok", "zerosize_ok", "multi_index"],
                op_flags=["writeonly", "no_broadcast"],
            )
            arr = np.ndarray.view(delayed, np.ndarray)
            with np.nditer(arr, **opt) as iter:
                for elem in iter:
                    item = elem.item()
                    item[key] = AnyDelayedArray(parent, iter.multi_index, key)

            return delayed.as_dict(keys=[key])[key]

    def __setitem__(self, key, value):
        arr = np.ndarray.view(self, np.ndarray)

        if np.ndim(arr) == 0:
            # Scalar array: assign value to the field
            if isinstance(value, self.deal):
                # `deal` objects are cells and cannot be 0-dim
                raise ValueError("Cannot broadcast.")
            arr.item()[key] = MatlabType.from_any(value)

        elif isinstance(value, self.deal):
            # Each element in the struct array is matched with an element
            # in the "deal" array.
            value = value.broadcast_to_struct(self)
            opt = dict(
                flags=["refs_ok", "zerosize_ok", "multi_index"],
                op_flags=["readonly"]
            )
            with np.nditer(arr, **opt) as iter:
                for elem in iter:
                    val = value[iter.multi_index]
                    if isinstance(val, self.deal):
                        val = val.to_cell()
                    elem.item()[key] = MatlabType.from_any(val)

        else:
            # Assign the same value to all elements in the struct array.
            opt = dict(flags=["refs_ok", "zerosize_ok"], op_flags=["readonly"])
            value = MatlabType.from_any(value)
            with np.nditer(arr, **opt) as iter:
                for elem in iter:
                    elem.item()[key] = value

    def __delitem__(self, key):
        if key not in self._allkeys():
            raise KeyError(key)
        arr = np.ndarray.view(self, np.ndarray)
        opt = dict(flags=["refs_ok", "zerosize_ok"], op_flags=["readonly"])
        with np.nditer(arr, **opt) as iter:
            for elem in iter:
                del elem.item()[key]

    # --- mapping ------------------------------------------------------

    def keys(self):
        return self.KeysView(self)

    def items(self):
        return self.ItemsView(self)

    def values(self):
        return self.ValuesView(self)

    def setdefault(self, key, value=None):
        arr = np.ndarray.view(self, np.ndarray)
        opt = dict(flags=["refs_ok", "zerosize_ok"], op_flags=["readonly"])
        with np.nditer(arr, **opt) as iter:
            for elem in iter:
                item = elem.item()
                if value is None:
                    value = _empty_array()
                else:
                    value = MatlabType.from_any(value)
                item.setdefault(key, value)

    def update(self, other):
        Struct = _imports.Struct

        other = Struct.from_any(other)
        other = np.ndarray.view(other, np.ndarray)
        other = np.broadcast_to(other, self.shape)

        arr = np.ndarray.view(self, np.ndarray)
        opt = dict(
            flags=["refs_ok", "zerosize_ok", "multi_index"],
            op_flags=["readonly"]
        )
        with np.nditer(arr, **opt) as iter:
            for elem in iter:
                other_elem = other[iter.multi_index]
                item = elem.item()
                item.update(other_elem)

    # --- helper ------------------------------------------------------
    class deal:  # FIXME: Removed dependency to Cell
        """
        Helper class to assign values into a specific field of a Struct array.

        ```python
        s = Struct(2)
        s.field = [1, 2]
        print(s)
        # [{"field": [1, 2]}, {"field": [1, 2]}]

        s = Struct(2)
        s.field = Struct.deal([1, 2])
        print(s)
        # [{"field": 1}, {"field": 2}]
        ```
        """

        # The idea is to have a type that tells Struct.__setattr__
        # that we want to broadcast the object before assigning it to
        # the field. We let the target struct tell this object which
        # field is being assigned and this object transforms itself
        # into a struct array with a single field (but multiple elements).
        # We can then let broadcasting do its magic.

        def __new__(cls, arg, **kwargs):
            return cls.from_any(arg, **kwargs)

        def broadcast_to_struct(self, struct):
            shape = struct.shape + self.shape[len(struct.shape):]
            return np.broadcast_to(self, shape)

        def to_cell(self):
            Cell = _imports.Cell
            return np.ndarray.view(self, Cell)

class _ListMixin(_ListishMixin, MutableSequence):
    """These methods are implemented in Cell, but not in Array or Struct."""

    # NOTE:
    #   The only abstract methods from MutableSequence are:
    #   * __getitem__   -> inherited from WrappedArray
    #   * __setitem__   -> inherited from WrappedArray
    #   * __delitem__   -> implemented here
    #   * __len__       -> inherited from np.ndarray
    #   * insert        -> implemented here
    #
    #   MutableSequence implements the following non-abstract methods,
    #   but we overload them for speed:
    #   * index         -> implemented here
    #   * count         -> implemented here
    #   * append        -> inherited from _ListishMixin
    #   * clear         -> inherited from _ListishMixin
    #   * reverse       -> implemented here
    #   * extend        -> inherited from _ListishMixin
    #   * pop           -> implemented here
    #   * remove        -> implemented here
    #   * __iter__      -> inherited from np.ndarray
    #   * __reversed__  -> inherited from Sequence
    #   * __iadd__      -> implemented here
    #   * __eq__        -> implemented here
    #   * __ne__        -> implemented here
    #   * __ge__        -> implemented here
    #   * __gt__        -> implemented here
    #   * __le__        -> implemented here
    #   * __lt__        -> implemented here
    #
    #   Mutable implements the following non-abstract method, whose
    #   behaviour differs from that of np.ndarray.
    #   We use np.ndarray's instead.
    #   * __contains__  -> inherited from np.ndarray

    # --- ndarray ------------------------------------------------------

    # need to explicitely reference np.ndarray methods otherwise it
    # goes back to MutableSequence, which raises.
    __len__ = WrappedArray.__len__
    __getitem__ = WrappedArray.__getitem__
    __setitem__ = WrappedArray.__setitem__
    __delitem__ = WrappedArray.__delitem__
    __contains__ = WrappedArray.__contains__
    __iter__ = WrappedArray.__iter__

    # --- magic --------------------------------------------------------

    def __add__(self, other):
        other = type(self).from_any(other)
        return np.concatenate([self, other])

    def __radd__(self, other):
        other = type(self).from_any(other)
        return np.concatenate([other, self])

    def __iadd__(self, other):
        self.extend(other)
        return self

    def __mul__(self, value):
        return np.concatenate([self] * value)

    def __rmul__(self, value):
        return np.concatenate([self] * value)

    def __imul__(self, value):
        length = len(self)
        new_shape = list(np.shape(self))
        new_shape[0] *= value
        np.ndarray.resize(self, new_shape, refcheck=False)
        for i in range(1, value):
            self[i * length:(i + 1) * length] = self[:length]
        return self

    # In lists, __contains__ should be treated as meaning "contains this
    # element along the first dimension." I.e.,
    # `value in sequence` should be equivalent to `value in iter(sequence)`.
    #
    # In contrast, ndarray's __contains__ is used "element-wise".
    # I.e., it is equivalent to `value in sequence.flat`.
    # It is the main reason ndarray do not implement the MutableSequence
    # protocol:
    # https://github.com/numpy/numpy/issues/2776#issuecomment-652584346
    #
    # We use the numpy behaviour, and implement list_contains to recover
    # the list behaviour.

    def list_contains(self, value, broadcast=True):
        """
        Check whether a value is in the object, when iterated along its
        first dimension.

        Should be roughly equivalent to `value in iter(self)`, although
        it also takes care of collapsing boolean arrays into a single
        boolean by calling `all()` on them.

        * If `broadcast=True` (default), equality is loose in the sense
          that `1` matches `[1, 1, 1]`.
        * If `broadcast=False`, array-like objects only match if they
          have the exact same shape.
        """
        value = np.asarray(value)
        for elem in self:
            elem = np.asarray(elem)
            if not broadcast and value.shape != elem.shape:
                continue
            if (elem == value).all():
                return True
        return False

    # --- sequence -----------------------------------------------------

    def count(self, value, broadcast=True):
        """
        Return number of occurrences of value, when iterating along the
        object's first dimension.

        * If `broadcast=True` (default), equality is loose in the sense
          that `1` matches `[1, 1, 1]`.
        * If `broadcast=False`, array-like objects only match if they
          have the exact same shape.
        """
        value = np.asarray(value)

        def iter():
            for elem in self:
                elem = np.asarray(elem)
                if not broadcast and value.shape != elem.shape:
                    yield False
                yield bool((elem == value).all())

        return sum(iter())

    def index(self, value, broadcast=True):
        """
        Return first index of value, when iterating along the object's
        first dimension.

        * If `broadcast=True` (default), equality is loose in the sense
          that `1` matches `[1, 1, 1]`.
        * If `broadcast=False`, array-like objects only match if they
          have the exact same shape.
        """
        value = np.asarray(value)
        for i, elem in enumerate(self):
            elem = np.asarray(elem)
            if not broadcast and value.shape != elem.shape:
                continue
            if (elem == value).all():
                return i
        raise ValueError(value, "is not in", type(self).__name__)

    def insert(self, index, obj):
        """Insert object before index."""
        if index < 0:
            # +1 because we insert *after* the index if negative
            index = len(self) + index + 1
        if not isinstance(index, int):
            raise TypeError("Only scalar elements can be inserted.")
        new_shape = list(np.shape(self))
        new_shape[0] += 1
        np.ndarray.resize(self, new_shape, refcheck=False)
        self[index + 1:] = self[index:-1]
        self[index] = obj

    def pop(self, index=-1):
        """Remove and return item at index (default last)."""
        if index < 0:
            index = len(self) + index
        # need to copy as its memory location will be overwritten by del
        if not isinstance(index, int):
            raise TypeError("Only scalar indices can be popped.")
        value = np.copy(self[index])
        del self[index]
        return value

    def remove(self, value):
        """Remove first occurrence of value."""
        new_shape = list(np.shape(self))
        new_shape[0] -= 1
        index = self.index(value)
        del self[index]

    def reverse(self):
        """Reverse *IN PLACE*."""
        self[:] = self[::-1]

    def sort(self, *, key=None, reverse=False, kind="stable", axis=0):
        """
        Sort the list in ascending order and return None.

        The sort is in-place (i.e. the list itself is modified) and stable
        (i.e. the order of two equal elements is maintained).

        If a key function is given, apply it once to each list item and sort
        them, ascending or descending, according to their function values.

        The reverse flag can be set to sort in descending order.

        !!! note
            We further expose options from `np.ndarray.sort`, which is used
            under the hood. However, we use different defaults
            (kind="stable" instead of "quicksort", axis=0 instead of -1).

            If `key` is provided, we fallback to `list.sort`
            (triggers a temporary copy).
        """
        if key:
            aslist = list(np.moveaxis(self, axis, 0))
            aslist.sort(key=key, reverse=reverse)
            asarray = np.stack(aslist, axis=axis)
            self[...] = asarray
        else:
            np.ndarray.sort(self, kind=kind, axis=axis)
            if reverse:
                self.reverse()

class _ListishMixin:
    """These methods are implemented in Cell and Array, but not Struct."""

    # TODO:
    #   The following _ListLike methods could potentially be moved here
    #   (i.e., be implemented in Array as well as Cell):
    #
    #   * index
    #   * count
    #   * reverse
    #   * pop
    #   * remove

    def append(self, value):
        """
        Append object to the end of the list
        (along the first dimension).
        """
        new_shape = list(np.shape(self))
        new_shape[0] += 1
        np.ndarray.resize(self, new_shape, refcheck=False)
        self[-1] = value

    def extend(self, value):
        """
        Extend list by appending elements from the iterable
        (along the first dimension).
        """
        value = type(self).from_any(value)
        init_len = len(self)
        batch = len(self) + len(value)
        shape = np.broadcast_shapes(np.shape(self)[1:], np.shape(value)[1:])
        new_shape = [batch] + list(shape)
        np.ndarray.resize(self, new_shape, refcheck=False)
        self[init_len:] = value

    def clear(self):
        """Remove all items by setting the first axis to have size 0."""
        zero_shape = list(np.shape(self))
        zero_shape[0] = 0
        np.ndarray.resize(zero_shape, refcheck=False)

class _SparseMixin:
    """Methods common to the scipy.sparse and dense backends."""

    def _as_runtime(self) -> dict:
        # NOTE: self[self.nonzero()] sometimes return a sparse array
        #       (when self is entirely zeros?). We must therefore
        #       explictly convert `values` to a (dense) numpy array.
        indices = self.nonzero()
        values = self[indices].reshape([-1, 1]).astype(np.double)
        if hasattr(values, 'todense'):
            values = values.todense()
        indices = np.stack(indices, -1)
        indices += 1
        size = np.array([[*np.shape(self)]])
        return dict(
            type__="sparse",
            size__=size,
            indices__=indices,
            values__=values,
        )

    @classmethod
    def _from_runtime(cls, dictobj: dict, runtime=None):
        # NOTE: If there is a single nonzero value, it is passed as a
        # scalar float, rather than a matlab.double.
        if dictobj["type__"] != "sparse":
            raise ValueError("Not a matlab sparse matrix")
        size = np.array(dictobj["size__"], dtype=np.uint64).ravel()
        size = size.tolist()
        ndim = len(size)
        if isinstance(dictobj["values__"], float):
            dtype = np.double
        else:
            dtype = _matlab_array_types()[type(dictobj["values__"])]
        indices = np.asarray(dictobj["indices__"], dtype=np.long)
        values = np.asarray(dictobj["values__"], dtype=dtype).ravel()
        indices -= 1
        if indices.size == 0:
            indices = indices.reshape([0, ndim])
        elif indices.shape[0] == 1:
            # NOTE: I've encountered this issue while runngin the PEB
            # tutorial, but it is difficult to find a minimal example.
            # It seems that for some reason, find() has returned row vectors
            # instead of column vectors, so [ii, jj] generates a long row
            # vector. When this is detected, I properly unfold the data,
            # but this should probably be fixed in mpython_endpoint
            # as well.
            indices = indices.reshape([ndim, -1]).T
        return cls.from_coo(values, indices.T, size)