espy_paws/

lib.rs

mod error;

pub use anyhow;
pub use error::{DebugInfoError, Error, ErrorKind, InvalidBytecode};

use espy_heart::prelude::*;
use std::any::Any;
use std::borrow::Borrow;
use std::cell::RefCell;
use std::mem;
use std::num::NonZero;
use std::rc::{Rc, Weak};

#[macro_export]
macro_rules! extern_impl {
    {
        $(#[espy(
            $(debug = $description:literal)?
        )])?
        $vis:vis fn $this:ident <$host:lifetime> (&self, $argument:ident)
            $body:tt
    } => {
        #[derive(
            ::std::clone::Clone,
            ::std::marker::Copy,
            ::std::fmt::Debug,
            ::std::default::Default
        )]
        $vis struct $this;

        impl $crate::ExternFn for $this {
            fn call<$host>(
                &$host self, $argument: $crate::Value<$host>
            ) -> ::std::result::Result<$crate::Value<$host>, $crate::Error>
                $body

            fn to_static(&self) -> ::std::option::Option<&'static dyn $crate::ExternFn> {
                Some(&$this)
            }

            $($(
                fn debug(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
                    ::std::write!(f, $description)
                }
            )?)?
        }
    };
    {
        $(#[espy(
            // Allows the user to set a debug string to be shown used by the Extern trait.
            //
            // This is a format string, and the `self` parameter may be bound
            // by using square brackets after "debug".
            // Using `self` directly will not work because it is not considered in scope of the macro.
            $(debug$([$debug_name:ident])? = $description:literal)?
        )])?
        $vis:vis struct $this:ident {
            $($name:ident: $value:expr),* $(,)?
        }
    } => {
        #[derive(
            ::std::clone::Clone,
            ::std::marker::Copy,
            ::std::fmt::Debug,
            ::std::default::Default
        )]
        $vis struct $this;

        impl $crate::Extern for $this {
            fn index<'host>(
                &'host self, index: $crate::Value<'host>
            ) -> ::std::result::Result<$crate::Value<'host>, $crate::Error> {
                let index = index.string()?;
                match index.as_str() {
                    $(stringify!($name) => Ok($crate::Value::from($value)),)*
                    _ => Err($crate::Error::index_not_found(
                        &$crate::Value::borrow(self),
                        &index.into(),
                    )),
                }
            }

            fn to_static<'host>(&self) -> ::std::option::Option<&'static dyn $crate::Extern> {
                ::std::option::Option::Some(&$this)
            }

            fn any(&self) -> ::std::option::Option<&dyn ::std::any::Any> {
                ::std::option::Option::Some(self)
            }

            $($(
                fn debug(&self, f: &mut ::std::fmt::Formatter<'_>) -> ::std::fmt::Result {
                    $(let $debug_name = self;)?
                    ::std::write!(f, $description)
                }
            )?)?
        }
    };
}

fn rc_slice_try_from_iter_ordered<T, E>(
    len: usize,
    iter: impl Iterator<Item = Result<T, E>>,
    rev: bool,
) -> Result<Rc<[T]>, E> {
    let mut tuple = Rc::new_uninit_slice(len);
    // SAFETY: `get_mut` only returns `None` if the `Rc` has been cloned.
    let mutable_tuple = unsafe { Rc::get_mut(&mut tuple).unwrap_unchecked() };
    let mut count = 0;
    // This condition exists to avoid copy/pasting the unsafe code in this function.
    // It would be nice to make this generic somehow,
    // but that's probably unsafe and definitely unecessary.
    if rev {
        for (entry, value) in mutable_tuple.iter_mut().rev().zip(iter) {
            entry.write(value?);
            count += 1;
        }
    } else {
        for (entry, value) in mutable_tuple.iter_mut().zip(iter) {
            entry.write(value?);
            count += 1;
        }
    }
    assert!(
        count == len,
        "iter did not produce enough values ({count}) to initialize slice of length {len}"
    );
    // SAFETY: Since `count` == `len`, the slice is initialized.
    unsafe { Ok(tuple.assume_init()) }
}

fn rc_slice_try_from_iter<T, E>(
    len: usize,
    iter: impl Iterator<Item = Result<T, E>>,
) -> Result<Rc<[T]>, E> {
    rc_slice_try_from_iter_ordered(len, iter, false)
}

/// Same as rc_slice_try_from_iter, but inserts elements in reverse order.
/// This is used to construct a function's captures using `stack.pop()`
fn rc_slice_try_from_iter_rev<T, E>(
    len: usize,
    iter: impl Iterator<Item = Result<T, E>>,
) -> Result<Rc<[T]>, E> {
    rc_slice_try_from_iter_ordered(len, iter, true)
}

fn rc_slice_from_iter<T>(len: usize, iter: impl Iterator<Item = T>) -> Rc<[T]> {
    rc_slice_try_from_iter(len, iter.map(Ok::<_, ()>)).expect("iter is always Ok")
}

/// The root type of every espy value. All interoperation starts here.
///
/// Don't be afraid to [`Clone`] this type;
/// it contains only [`Copy`] types and [`Rc`]s.
#[derive(Clone)]
pub enum Value<'host> {
    /// Unit is the absense of a value.
    /// It can be thought of as both an empty tuple and an empty named tuple.
    Unit,
    Tuple(Tuple<Value<'host>>),

    Borrow(&'host dyn Extern, Option<Rc<Value<'host>>>),
    Owned(Rc<dyn ExternOwned>, Option<Rc<Value<'host>>>),
    I64(i64),
    Bool(bool),
    String(String),
    Function(Rc<Function<'host>>),
    EnumVariant(Rc<EnumVariant<'host>>),
    Option {
        contents: Option<Rc<Value<'host>>>,
        ty: ComplexType,
    },
    Mut(Mut<'host>),

    Type(Type),
}

impl std::fmt::Debug for Value<'_> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Value::Unit => write!(f, "Unit"),
            Value::Tuple(tuple) => write!(f, "{tuple:?}"),
            Value::Borrow(external, partial_index) => {
                write!(f, "Borrow(")?;
                external.debug(f)?;
                if let Some(partial_index) = partial_index {
                    write!(f, ", {partial_index:?}")?;
                }
                write!(f, ")")
            }
            Value::Owned(external, partial_index) => {
                write!(f, "Owned(")?;
                external.debug(f)?;
                if let Some(partial_index) = partial_index {
                    write!(f, ", {partial_index:?}")?;
                }
                write!(f, ")")
            }
            Value::I64(i) => write!(f, "I64({i:?})"),
            Value::Bool(i) => write!(f, "Bool({i:?})"),
            Value::String(i) => write!(f, "String({i:?})"),
            Value::Function(function) => write!(f, "{function:?}"),
            Value::EnumVariant(enum_variant) => write!(f, "{enum_variant:?}"),
            Value::Option { contents, ty: _ } => write!(f, "{contents:?}"),
            Value::Mut(inner) => write!(f, "{inner:?}"),
            Value::Type(t) => write!(f, "{t:?}"),
        }
    }
}

/// A version of [`Value`] with a static lifetime.
///
/// Must be cast back to a runtime-compatible [`Value`] using
/// [`StaticValue::to_runtime`] to be used.
///
/// The difference between this type and [`Value<'static>`] is the lack
/// of [`Mut`], which contains a [`RefCell`] and makes [`Value<'static>`]
/// [invariant](https://doc.rust-lang.org/nomicon/subtyping.html#variance) over
/// `'host`. This means that a [`Value<'static>`] cannot be combined with
/// non `'static` values in the same runtime,  which would prevent useful things
/// like a static [`Function`] accepting a borrowed [`Extern`] value with a
/// non-`'static` lifetime.
#[derive(Clone)]
pub enum StaticValue {
    Unit,
    Tuple(Tuple<StaticValue>),

    Borrow(&'static dyn Extern, Option<Rc<StaticValue>>),
    Owned(Rc<dyn ExternOwned>, Option<Rc<StaticValue>>),
    I64(i64),
    Bool(bool),
    String(String),
    Function(Rc<StaticFunction>),
    EnumVariant(Rc<StaticEnumVariant>),
    Option {
        contents: Option<Rc<StaticValue>>,
        ty: ComplexType,
    },

    Type(Type),
}

impl std::fmt::Debug for StaticValue {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self.to_runtime())
    }
}

impl StaticValue {
    #[must_use]
    pub fn to_runtime<'host>(&self) -> Value<'host> {
        match self {
            StaticValue::Unit => Value::Unit,
            StaticValue::Tuple(tuple) => Value::Tuple(tuple.to_runtime()),
            StaticValue::Borrow(extern_ref, partial_index) => Value::Borrow(
                *extern_ref,
                partial_index.as_ref().map(|x| x.to_runtime().into()),
            ),
            StaticValue::Owned(extern_owned, partial_index) => Value::Owned(
                extern_owned.clone(),
                partial_index.as_ref().map(|x| x.to_runtime().into()),
            ),
            StaticValue::I64(i) => Value::I64(*i),
            StaticValue::Bool(i) => Value::Bool(*i),
            StaticValue::String(i) => Value::String(i.clone()),
            StaticValue::Function(static_function) => {
                Value::Function(Rc::new(static_function.to_runtime()))
            }
            StaticValue::EnumVariant(static_enum_variant) => {
                Value::EnumVariant(Rc::new(EnumVariant {
                    contents: static_enum_variant.contents.clone().into(),
                    variant: static_enum_variant.variant,
                    definition: static_enum_variant.definition.clone(),
                }))
            }
            StaticValue::Option { contents, ty } => Value::Option {
                contents: contents.as_ref().map(|x| x.to_runtime().into()),
                ty: ty.clone(),
            },
            StaticValue::Type(i) => Value::Type(i.clone()),
        }
    }
}

impl<'host, T: Borrow<StaticValue>> From<T> for Value<'host> {
    fn from(value: T) -> Self {
        value.borrow().to_runtime()
    }
}

/// The type of a singular espy values.
///
/// This enum does *not* represent the type of tuples;
/// for that, see [`ComplexType`]
///
/// [`Type`] itself is a type, [`Type::Type`], because it may appear within an espy value.
///
/// Note that [`Value::type_of`] returns [`Type::Any`] for [`Value::Borrow`]
/// and [`Value::Owned`].
#[derive(Clone, Debug)]
pub enum Type {
    /// Any is the type of a value with unknown capabilities.
    ///
    /// Any is the type of all external values because they have arbitrary, unknowable properties.
    /// This means that external values must be casted to trait objects to interact with them.
    Any,
    I64,
    Bool,
    String,
    Function(Rc<FunctionType>),
    Enum(Rc<EnumType>),
    Option(Rc<ComplexType>),
    Mut(Rc<ComplexType>),

    /// The type of types.
    Type,
    Unit,
}

impl PartialEq for Type {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Self::Enum(l), Self::Enum(r)) => l == r,
            (Self::Option(l), Self::Option(r)) => l == r,
            _ => mem::discriminant(self) == mem::discriminant(other),
        }
    }
}

impl Eq for Type {}

/// The type of any espy value.
///
/// [`ComplexType`] is usually the only form of [`Type`] that the espy
/// interpreter is concerned with, but it cannot be represented within espy
/// itself (tuples of types represent [`ComplexType`]s, instead).
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum ComplexType {
    Simple(Type),
    Complex(Tuple<ComplexType>),
}

impl ComplexType {
    #[must_use]
    pub fn compare(&self, r: &Self) -> bool {
        match (self, r) {
            (ComplexType::Simple(Type::Any), _) | (_, ComplexType::Simple(Type::Any)) => true,
            (ComplexType::Simple(l), ComplexType::Simple(r)) => l == r,
            (ComplexType::Complex(l), ComplexType::Complex(r)) => {
                l.values().zip(r.values()).all(|(l, r)| l.compare(r))
            }
            _ => false,
        }
    }
}

impl From<Type> for ComplexType {
    fn from(value: Type) -> Self {
        Self::Simple(value)
    }
}

impl From<Tuple<ComplexType>> for ComplexType {
    fn from(value: Tuple<ComplexType>) -> Self {
        Self::Complex(value)
    }
}

impl From<ComplexType> for Value<'_> {
    fn from(value: ComplexType) -> Self {
        match value {
            ComplexType::Simple(ty) => ty.into(),
            ComplexType::Complex(tuple) => Value::Tuple(tuple.into()),
        }
    }
}

impl From<Type> for Value<'_> {
    fn from(t: Type) -> Self {
        Self::Type(t)
    }
}

impl<'host> Value<'host> {
    /// Returns None if `self` contains any [`Value::Borrow`] or [`Value::Mut`].
    ///
    /// [`Value::Borrow`] is not static for obvious reasons,
    /// and [`Value::Mut`] cannot be made static because of refcell subtyping.
    /// Instead, hosts using to_static should provide mutable state outside of
    /// the espy runtime.
    ///
    /// # Errors
    ///
    /// Returns an error if the value is mutable or an external value that
    /// cannot be made static.
    pub fn to_static(&self) -> Result<StaticValue, Error> {
        match self {
            Value::Unit => Ok(StaticValue::Unit),
            Value::Tuple(tuple) => Ok(StaticValue::Tuple(tuple.to_static()?)),
            Value::Borrow(extern_borrow, partial_index) => Ok(StaticValue::Borrow(
                extern_borrow
                    .to_static()
                    .ok_or(Error::from(ErrorKind::NotStatic))?,
                partial_index
                    .as_ref()
                    .map(|x| x.to_static().map(Rc::new))
                    .transpose()?,
            )),
            Value::Owned(extern_owned, partial_index) => Ok(StaticValue::Owned(
                extern_owned.clone(),
                partial_index
                    .as_ref()
                    .map(|x| x.to_static().map(Rc::new))
                    .transpose()?,
            )),
            Value::I64(x) => Ok(StaticValue::I64(*x)),
            Value::Bool(x) => Ok(StaticValue::Bool(*x)),
            Value::String(x) => Ok(StaticValue::String(x.clone())),
            Value::Function(function) => Ok(StaticValue::Function(function.to_static()?.into())),
            Value::EnumVariant(enum_variant) => {
                Ok(StaticValue::EnumVariant(Rc::new(StaticEnumVariant {
                    contents: enum_variant.contents.to_static()?,
                    variant: enum_variant.variant,
                    definition: enum_variant.definition.clone(),
                })))
            }
            Value::Option { contents, ty } => Ok(StaticValue::Option {
                contents: contents
                    .as_ref()
                    .map(|x| x.to_static())
                    .transpose()?
                    .map(Rc::new),
                ty: ty.clone(),
            }),
            Value::Mut(_) => Err(ErrorKind::NotStatic.into()),
            Value::Type(x) => Ok(StaticValue::Type(x.clone())),
        }
    }

    /// Convenience method for indexing values of various types by an integer.
    ///
    /// Usually this is most useful for reading function arguments by index,
    /// which are passed as a tuple by convention.
    ///
    /// # Errors
    ///
    /// Returns [`ErrorKind::IndexNotFound`] if `self` cannot be indexed or the index is out of range for the container.
    ///
    /// [`Extern`] and [`ExternOwned`] implementations may return arbitary errors.
    pub fn try_get(&self, index: i64) -> Result<Value<'host>, Error> {
        match self {
            Value::Tuple(tuple) => usize::try_from(index)
                .ok()
                .and_then(|index| tuple.get(index))
                .ok_or(Error::index_not_found(self, &index.into())),
            Value::Type(Type::Enum(ty)) => usize::try_from(index)
                .ok()
                .filter(|index| *index < ty.variants.len())
                .map(|index| {
                    Value::Function(Rc::new(
                        FunctionAction::Enum {
                            variant: index,
                            definition: ty.clone(),
                        }
                        .into(),
                    ))
                })
                .ok_or_else(|| Error::index_not_found(self, &index.into())),
            Value::Type(Type::Option(ty)) => match index {
                0 => Ok(Value::Function(Rc::new(
                    FunctionAction::OptionCase {
                        some: true,
                        ty: (**ty).clone(),
                    }
                    .into(),
                ))),
                1 => Ok(Value::Function(Rc::new(
                    FunctionAction::OptionCase {
                        some: false,
                        ty: (**ty).clone(),
                    }
                    .into(),
                ))),
                _ => Err(Error::index_not_found(self, &index.into())),
            },
            _ => Err(Error::index_not_found(self, &index.into())),
        }
    }

    #[must_use]
    pub fn get(&self, index: i64) -> Option<Value<'host>> {
        self.try_get(index).ok()
    }

    /// Convenience methods for indexing values of various types by a string.
    ///
    /// # Errors
    ///
    /// Returns [`Error::index_not_found`] if `self` cannot be indexed or the index is not found in the container.
    ///
    /// [`Value::Borrow`] and [`Value::Owned`] implementations may return arbitary errors.
    pub fn try_find(&self, index: impl Into<String>) -> Result<Value<'host>, Error> {
        let index = index.into();
        match self {
            Value::Tuple(tuple) => tuple
                .find(index.clone())
                .ok_or(Error::index_not_found(self, &index.into())),
            Value::Type(Type::Enum(ty)) => {
                if let Some(variant_id) = ty
                    .variants
                    .as_ref()
                    .iter()
                    .enumerate()
                    .find(|(_, (variant, _))| *variant == index)
                    .map(|(i, _)| i)
                {
                    Ok(Value::Function(Rc::new(
                        FunctionAction::Enum {
                            variant: variant_id,
                            definition: ty.clone(),
                        }
                        .into(),
                    )))
                } else {
                    Err(Error::index_not_found(self, &index.into()))
                }
            }
            Value::Type(Type::Option(ty)) => match index.as_str() {
                "Some" => Ok(Value::Function(Rc::new(
                    FunctionAction::OptionCase {
                        some: true,
                        ty: (**ty).clone(),
                    }
                    .into(),
                ))),
                "None" => Ok(Value::Function(Rc::new(
                    FunctionAction::OptionCase {
                        some: false,
                        ty: (**ty).clone(),
                    }
                    .into(),
                ))),
                _ => Err(Error::index_not_found(self, &index.into())),
            },
            _ => Err(Error::index_not_found(self, &index.into())),
        }
    }

    #[must_use]
    pub fn find(&self, index: impl Into<String>) -> Option<Value<'host>> {
        self.try_find(index).ok()
    }

    /// Convenience methods for indexing values of various types.
    ///
    /// # Errors
    ///
    /// Returns [`Error::index_not_found`] if `self` cannot be indexed or the index is not found in the container.
    ///
    /// [`Value::Borrow`] and [`Value::Owned`] implementations may return arbitary errors.
    pub fn index(&self, index: impl Into<Value<'host>>) -> Result<Value<'host>, Error> {
        match (self, index.into()) {
            (Value::Borrow(external, partial_index), index) => {
                external.index(if let Some(partial_index) = partial_index {
                    Value::concat((**partial_index).clone(), index)
                } else {
                    index
                })
            }
            (Value::Owned(external, partial_index), index) => {
                external
                    .clone()
                    .index(if let Some(partial_index) = partial_index {
                        Value::concat((**partial_index).clone(), index)
                    } else {
                        index
                    })
            }
            (_, Value::I64(index)) => self.try_get(index),
            (_, Value::String(index)) => self.try_find(index),
            (_, index) => Err(Error::index_not_found(self, &index)),
        }
    }

    /// Attempts to downcast instances of [`Value::Borrow`] and [`Value::Owned`] into `&T`.
    ///
    /// Note that [`Extern`] and [`ExternOwned`] implementations have to opt into this behavior
    /// by implementing their `any` functions.
    /// The default `any` implementation will result in this function returning `None`.
    #[must_use]
    pub fn downcast_extern<T: Any>(&self) -> Option<&T> {
        match self {
            Value::Borrow(borrow, ..) => (*borrow).any()?.downcast_ref(),
            Value::Owned(owned, ..) => (*owned).any()?.downcast_ref(),
            _ => None,
        }
    }

    /// # Errors
    ///
    /// Returns an error if `self` and `other` are incomparable.
    pub fn eq(self, other: Self) -> Result<bool, Error> {
        match (self, other) {
            (Value::Unit, Value::Unit) => Ok(true),
            (Value::Tuple(l), Value::Tuple(r)) if l.len() == r.len() => {
                for (l, r) in l.values().zip(r.values()) {
                    if !l.clone().eq(r.clone())? {
                        return Ok(false);
                    }
                }
                Ok(true)
            }
            (Value::I64(l), Value::I64(r)) => Ok(l == r),
            (Value::Bool(l), Value::Bool(r)) => Ok(l == r),
            (Value::String(l), Value::String(r)) => Ok(l == r),
            (Value::EnumVariant(l), Value::EnumVariant(r)) => Ok(l.variant == r.variant
                && Rc::ptr_eq(&l.definition, &r.definition)
                && Rc::try_unwrap(l)
                    .map_or_else(|l| l.contents.clone(), |l| l.contents)
                    .eq(Rc::try_unwrap(r).map_or_else(|r| r.contents.clone(), |r| r.contents))?),
            (
                Value::Option {
                    contents: l,
                    ty: l_type,
                },
                Value::Option {
                    contents: r,
                    ty: r_type,
                },
            ) if l_type.compare(&r_type) => Ok(l.is_none() && r.is_none()
                || l.zip(r).map_or(Ok(false), |(l, r)| {
                    Rc::unwrap_or_clone(l).eq(Rc::unwrap_or_clone(r))
                })?),
            (Value::Type(l), Value::Type(r)) => Ok(l == r),
            (this, other) => Err(Error::incomparable_values(&this, &other)),
        }
    }

    /// # Errors
    ///
    /// Returns an error if a mutable reference is being mutably borrowed.
    ///
    /// This can be safely ignored by the host if it has not deliberately borrowed an espy value.
    pub fn type_of(&self) -> Result<ComplexType, Error> {
        Ok(match &self {
            Value::Unit => Type::Unit.into(),
            Value::Tuple(tuple) => {
                let complex = match &tuple.0 {
                    TupleStorage::Numeric(items) => Tuple(TupleStorage::Numeric(
                        rc_slice_try_from_iter(items.len(), items.iter().map(Value::type_of))?,
                    )),
                    TupleStorage::Named(items) => {
                        Tuple(TupleStorage::Named(rc_slice_try_from_iter(
                            items.len(),
                            items.iter().map(|(name, value)| {
                                value.type_of().map(|value| (name.clone(), value))
                            }),
                        )?))
                    }
                };
                // The type of a tuple containing only types is `type`, not `(type, type, ..)`
                if complex
                    .values()
                    .all(|x| matches!(x, ComplexType::Simple(Type::Type)))
                {
                    Type::Type.into()
                } else {
                    complex.into()
                }
            }
            Value::Borrow(..) | Value::Owned(..) => Type::Any.into(),
            Value::I64(_) => Type::I64.into(),
            Value::Bool(_) => Type::Bool.into(),
            Value::String(_) => Type::String.into(),
            Value::Function(function) => match &function.action {
                FunctionAction::With { signature, .. } => {
                    Type::Function(Rc::new(signature.clone())).into()
                }
                _ => Type::Function(Rc::new(FunctionType {
                    input: Type::Any.into(),
                    output: Type::Any.into(),
                }))
                .into(),
            },
            Value::EnumVariant(enum_variant) => Type::Enum(enum_variant.definition.clone()).into(),
            Value::Option { contents: _, ty } => Type::Option(Rc::new(ty.clone())).into(),
            Value::Mut(inner) => Type::Mut(
                inner
                    .upgrade()
                    .ok_or(ErrorKind::OutOfScopeMut)?
                    .try_borrow()
                    .map_err(Error::other)?
                    .type_of()?
                    .into(),
            )
            .into(),
            Value::Type(_) => Type::Type.into(),
        })
    }

    #[must_use]
    pub fn concat(self, r: Self) -> Self {
        match (self, r) {
            (
                Value::Tuple(Tuple(TupleStorage::Numeric(l))),
                Value::Tuple(Tuple(TupleStorage::Numeric(r))),
            ) => Value::Tuple(Tuple(TupleStorage::Numeric(rc_slice_from_iter(
                l.len() + r.len(),
                l.iter().chain(r.iter()).cloned(),
            )))),
            (
                Value::Tuple(Tuple(TupleStorage::Named(l))),
                Value::Tuple(Tuple(TupleStorage::Named(r))),
            ) => Value::Tuple(Tuple(TupleStorage::Named(rc_slice_from_iter(
                l.len() + r.len(),
                l.iter().chain(r.iter()).cloned(),
            )))),
            (l, Value::Unit) => l,
            (Value::Unit, r) => r,
            (Value::Tuple(Tuple(TupleStorage::Numeric(l))), r) => {
                Value::Tuple(Tuple(TupleStorage::Numeric(rc_slice_from_iter(
                    l.len() + 1,
                    l.iter().cloned().chain([r]),
                ))))
            }
            (l, Value::Tuple(Tuple(TupleStorage::Numeric(r)))) => {
                Value::Tuple(Tuple(TupleStorage::Numeric(rc_slice_from_iter(
                    1 + r.len(),
                    [l].into_iter().chain(r.iter().cloned()),
                ))))
            }
            (l, r) => Value::Tuple(Tuple(TupleStorage::Numeric(Rc::new([l, r])))),
        }
    }

    pub fn borrow(external: &'host dyn Extern) -> Self {
        Value::Borrow(external, None)
    }

    pub fn owned(external: Rc<dyn ExternOwned>) -> Self {
        Value::Owned(external, None)
    }
}

impl From<()> for Value<'_> {
    fn from((): ()) -> Self {
        Value::Unit
    }
}

impl From<Option<()>> for Value<'_> {
    fn from(value: Option<()>) -> Self {
        Value::Option {
            contents: value.map(|()| Rc::new(Value::Unit)),
            ty: Type::Unit.into(),
        }
    }
}

impl From<bool> for Value<'_> {
    fn from(value: bool) -> Self {
        Value::Bool(value)
    }
}

impl From<Option<bool>> for Value<'_> {
    fn from(value: Option<bool>) -> Self {
        Value::Option {
            contents: value.map(|value| Rc::new(Value::Bool(value))),
            ty: Type::Bool.into(),
        }
    }
}

impl From<i64> for Value<'_> {
    fn from(i: i64) -> Self {
        Value::I64(i)
    }
}

impl From<Option<i64>> for Value<'_> {
    fn from(value: Option<i64>) -> Self {
        Value::Option {
            contents: value.map(|value| Rc::new(Value::I64(value))),
            ty: Type::I64.into(),
        }
    }
}

impl From<&'static str> for Value<'_> {
    fn from(s: &'static str) -> Self {
        Value::String(s.into())
    }
}

impl From<Rc<str>> for Value<'_> {
    fn from(s: Rc<str>) -> Self {
        Value::String(s.into())
    }
}

impl From<String> for Value<'_> {
    fn from(s: String) -> Self {
        Value::String(s)
    }
}

impl<T: Into<String>> From<Option<T>> for Value<'_> {
    fn from(value: Option<T>) -> Self {
        Value::Option {
            contents: value.map(|value| Rc::new(Value::String(value.into()))),
            ty: Type::String.into(),
        }
    }
}

impl<'host> From<Rc<[Value<'host>]>> for Value<'host> {
    fn from(value: Rc<[Value<'host>]>) -> Self {
        Self::Tuple(Tuple::from(value))
    }
}

impl<'host, T: Into<Value<'host>>, const N: usize> From<[T; N]> for Value<'host> {
    fn from(value: [T; N]) -> Self {
        let slice = rc_slice_from_iter(value.len(), value.into_iter().map(Into::into));
        Self::Tuple(Tuple::from(slice))
    }
}

impl<'host> From<Rc<[(String, Value<'host>)]>> for Value<'host> {
    fn from(value: Rc<[(String, Value<'host>)]>) -> Self {
        Self::Tuple(Tuple::from(value))
    }
}

impl<'host> From<Tuple<Value<'host>>> for Value<'host> {
    fn from(value: Tuple<Value<'host>>) -> Self {
        Self::Tuple(value)
    }
}

impl<'host, K: Into<String>, const N: usize> From<[(K, Value<'host>); N]> for Value<'host> {
    fn from(value: [(K, Value<'host>); N]) -> Self {
        Self::Tuple(Tuple::from(value))
    }
}

impl<'host> From<Option<Value<'host>>> for Value<'host> {
    fn from(value: Option<Self>) -> Self {
        value.map(Rc::new).into()
    }
}

impl<'host> From<Option<Rc<Value<'host>>>> for Value<'host> {
    fn from(value: Option<Rc<Self>>) -> Self {
        Value::Option {
            contents: value,
            ty: Type::Any.into(),
        }
    }
}

impl<'host> From<Rc<Function<'host>>> for Value<'host> {
    fn from(f: Rc<Function<'host>>) -> Self {
        Value::Function(f)
    }
}

impl<'host> From<Function<'host>> for Value<'host> {
    fn from(f: Function<'host>) -> Self {
        Rc::new(f).into()
    }
}

impl<'host> TryFrom<Value<'host>> for () {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::Unit = value {
            Ok(())
        } else {
            Err(Error::type_error(&value, &Type::Unit.into()))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for Tuple<Value<'host>> {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::Tuple(value) = value {
            Ok(value)
        } else {
            Err(Error::expected_tuple(&value))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for bool {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::Bool(bool) = value {
            Ok(bool)
        } else {
            Err(Error::type_error(&value, &Type::Unit.into()))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for i64 {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::I64(value) = value {
            Ok(value)
        } else {
            Err(Error::type_error(&value, &Type::I64.into()))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for String {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::String(value) = value {
            Ok(value)
        } else {
            Err(Error::type_error(&value, &Type::String.into()))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for Rc<Function<'host>> {
    type Error = Error;
    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::Function(value) = value {
            Ok(value)
        } else {
            Err(Error::expected_function(&value))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for Function<'host> {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        Ok(Rc::unwrap_or_clone(Rc::<Self>::try_from(value)?))
    }
}

impl<'host> TryFrom<Value<'host>> for Rc<EnumVariant<'host>> {
    type Error = Error;
    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::EnumVariant(value) = value {
            Ok(value)
        } else {
            Err(Error::expected_enum_variant(&value))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for EnumVariant<'host> {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        Ok(Rc::unwrap_or_clone(Rc::<Self>::try_from(value)?))
    }
}

impl<'host> TryFrom<Value<'host>> for ComplexType {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        match value {
            Value::Type(t) => Ok(t.into()),
            Value::Tuple(tuple) => Ok(ComplexType::Complex(tuple.try_into()?)),
            _ => Err(Error::type_error(&value, &Type::Type.into())),
        }
    }
}

impl<'host> TryFrom<Value<'host>> for Rc<EnumType> {
    type Error = Error;
    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        if let Value::Type(Type::Enum(value)) = value {
            Ok(value)
        } else {
            Err(Error::expected_enum_type(&value))
        }
    }
}

impl<'host> TryFrom<Value<'host>> for EnumType {
    type Error = Error;

    fn try_from(value: Value<'host>) -> Result<Self, Self::Error> {
        Ok(Rc::unwrap_or_clone(Rc::<Self>::try_from(value)?))
    }
}

/// [`TryInto`] shortcuts
impl<'host> Value<'host> {
    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Unit`]
    pub fn unit(self) -> Result<(), Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Tuple`]
    pub fn tuple(self) -> Result<Tuple<Value<'host>>, Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Bool`]
    pub fn bool(self) -> Result<bool, Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::I64`]
    pub fn i64(self) -> Result<i64, Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::String`]
    pub fn string(self) -> Result<String, Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Function`]
    pub fn function(self) -> Result<Function<'host>, Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::EnumVariant`]
    pub fn enum_variant(self) -> Result<Rc<EnumVariant<'host>>, Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Option`]
    pub fn option(self) -> Result<Option<Value<'host>>, Error> {
        match self {
            Value::Option { contents, ty: _ } => Ok(contents.map(|x| (*x).clone())),
            _ => Err(Error::expected_option(&self)),
        }
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Mut`]
    pub fn into_refcell(self) -> Result<Rc<RefCell<Value<'host>>>, Error> {
        match &self {
            Value::Mut(inner) => Ok(inner.upgrade().ok_or(ErrorKind::OutOfScopeMut)?),
            _ => Err(Error::expected_reference(&self)),
        }
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Type`] or [`Value::Tuple`] of types.
    pub fn into_complex_type(self) -> Result<ComplexType, Error> {
        self.try_into()
    }

    /// # Errors
    ///
    /// Returns an error if `self` is not a [`Value::Type`] containing a [`Type::Enum`]
    pub fn into_enum_type(self) -> Result<Rc<EnumType>, Error> {
        self.try_into()
    }

    #[must_use]
    pub fn as_str(&self) -> Option<&str> {
        if let Value::String(s) = &self {
            Some(s.as_str())
        } else {
            None
        }
    }

    /// Turns this value into a vector of values.
    ///
    /// [`Value::Tuple`]'s members will be collected into the vector.
    /// [`Value::Unit`] will produce an empty vector.
    /// All other variants will produce a vector with just one member.
    pub fn into_vec(self) -> Vec<Value<'host>> {
        match self {
            Value::Unit => Vec::new(),
            Value::Tuple(tup) => tup.values().map(Value::clone).collect(),
            _ => Vec::from([self]),
        }
    }
}

#[derive(Clone)]
enum StringStorage {
    Static(&'static str),
    Floating(Rc<str>),
}

/// An espy string.
///
/// This container abstracts the possible in-memory representations of espy
/// strings as a single type.
#[derive(Clone)]
pub struct String(StringStorage);

impl String {
    /// View this string as a string slice.
    ///
    /// If you're trying to get an owned form of `str` and `Rc<str>` is
    /// acceptable, [`String::into_str`] may be cheaper if the espy string
    /// is already internally represented as one (due to concatenation, for
    /// example).
    #[must_use]
    pub fn as_str(&self) -> &str {
        match &self.0 {
            StringStorage::Static(s) => s,
            StringStorage::Floating(s) => s,
        }
    }

    /// Convert this string to a reference-counted string slice.
    ///
    /// If an espy string is already represented as an `Rc<str>`, this method
    /// will unwrap it without allocating any new memory.
    #[must_use]
    pub fn into_str(self) -> Rc<str> {
        match self.0 {
            StringStorage::Static(s) => s.into(),
            StringStorage::Floating(s) => s,
        }
    }

    /// Allocates an `Rc<str>` for `s` and wraps it in an espy string.
    #[must_use]
    pub fn owned(s: &str) -> Self {
        Rc::<str>::from(s).into()
    }
}

impl Default for String {
    fn default() -> Self {
        Self::from("")
    }
}

impl std::fmt::Display for String {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.as_str().fmt(f)
    }
}

impl std::fmt::Debug for String {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        self.as_str().fmt(f)
    }
}

impl PartialEq for String {
    fn eq(&self, other: &Self) -> bool {
        self.as_str() == other.as_str()
    }
}

impl Eq for String {}

impl From<&'static str> for String {
    fn from(value: &'static str) -> Self {
        Self(StringStorage::Static(value))
    }
}

impl From<std::string::String> for String {
    fn from(value: std::string::String) -> Self {
        Self(StringStorage::Floating(value.into()))
    }
}

impl From<Rc<str>> for String {
    fn from(value: Rc<str>) -> Self {
        Self(StringStorage::Floating(value))
    }
}

impl From<String> for Rc<str> {
    fn from(value: String) -> Self {
        value.into_str()
    }
}

impl Borrow<str> for &String {
    fn borrow(&self) -> &str {
        self.as_str()
    }
}

impl std::ops::Deref for String {
    type Target = str;

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

#[derive(Clone, Debug, PartialEq, Eq)]
enum TupleStorage<T> {
    Numeric(Rc<[T]>),
    Named(Rc<[(String, T)]>),
}

/// This type is used to store anything shaped like an espy tuple.
///
/// This includes:
/// - Tuple<[`Value`]> (an espy tuple)
/// - Tuple<[`StaticValue`]> (an espy tuple with a static lifetime)
/// - Tuple<[`ComplexType`]> (the type of an espy tuple)
///
/// It is either a "numeric" tuple (indexed only by order) or a "named" tuple
/// (indexed by both order and name).
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Tuple<T>(TupleStorage<T>);

impl<T> Tuple<T> {
    #[must_use]
    pub fn len(&self) -> usize {
        match &self.0 {
            TupleStorage::Numeric(items) => items.len(),
            TupleStorage::Named(items) => items.len(),
        }
    }

    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    #[must_use]
    pub fn get_ref(&self, index: usize) -> Option<&T> {
        match &self.0 {
            TupleStorage::Numeric(items) => items.get(index),
            TupleStorage::Named(items) => items.get(index).map(|(_name, value)| value),
        }
    }

    #[must_use]
    pub fn find_ref(&self, name: impl Borrow<str>) -> Option<&T> {
        let TupleStorage::Named(items) = &self.0 else {
            return None;
        };
        items.iter().find_map(|(n, v)| {
            if n.as_str() == name.borrow() {
                Some(v)
            } else {
                None
            }
        })
    }

    pub fn values(&self) -> impl Iterator<Item = &T> {
        (0..self.len()).map(|i| match &self.0 {
            TupleStorage::Numeric(items) => &items[i],
            TupleStorage::Named(items) => &items[i].1,
        })
    }

    #[must_use]
    pub fn as_numeric(&self) -> Option<&[T]> {
        match &self.0 {
            TupleStorage::Numeric(items) => Some(items),
            TupleStorage::Named(_) => None,
        }
    }

    #[must_use]
    pub fn as_named(&self) -> Option<&[(String, T)]> {
        match &self.0 {
            TupleStorage::Numeric(_) => None,
            TupleStorage::Named(items) => Some(items),
        }
    }
}

impl<T: Clone> Tuple<T> {
    #[must_use]
    pub fn get(&self, index: usize) -> Option<T> {
        match &self.0 {
            TupleStorage::Numeric(items) => items.get(index).cloned(),
            TupleStorage::Named(items) => items.get(index).map(|(_name, value)| value).cloned(),
        }
    }

    #[must_use]
    pub fn find(&self, name: impl Into<String>) -> Option<T> {
        let TupleStorage::Named(items) = &self.0 else {
            return None;
        };
        let name = name.into();
        items.iter().find_map(|(n, v)| {
            if n.as_str() == name.as_str() {
                Some(v.clone())
            } else {
                None
            }
        })
    }
}

impl<'host> Tuple<Value<'host>> {
    /// # Errors
    ///
    /// Returns an error if the index is not found.
    pub fn try_get_ref(&self, index: usize) -> Result<&Value<'host>, Error> {
        let value = match &self.0 {
            TupleStorage::Numeric(items) => items.get(index),
            TupleStorage::Named(items) => items.get(index).map(|(_name, value)| value),
        };
        value
            .ok_or_else(|| Error::index_not_found(&self.clone().into(), &Value::from(index as i64)))
    }

    /// # Errors
    ///
    /// Returns an error if the index is not found.
    pub fn try_find_ref(&self, name: impl Into<String>) -> Result<&Value<'host>, Error> {
        let name = name.into();
        if let TupleStorage::Named(items) = &self.0
            && let Some(value) = items.iter().find_map(|(n, v)| {
                if n.as_str() == name.as_str() {
                    Some(v)
                } else {
                    None
                }
            })
        {
            Ok(value)
        } else {
            Err(Error::index_not_found(&self.clone().into(), &name.into()))
        }
    }

    /// # Errors
    ///
    /// Returns an error if the index is not found.
    pub fn try_get(&self, index: usize) -> Result<Value<'host>, Error> {
        self.try_get_ref(index).cloned()
    }

    /// # Errors
    ///
    /// Returns an error if the index is not found.
    pub fn try_find(&self, name: impl Into<String>) -> Result<Value<'host>, Error> {
        self.try_find_ref(name).cloned()
    }
}

impl<'host> Tuple<Value<'host>> {
    fn to_static(&self) -> Result<Tuple<StaticValue>, Error> {
        match &self.0 {
            TupleStorage::Numeric(items) => rc_slice_try_from_iter(
                items.len(),
                items.iter().map(|value: &Value| value.to_static()),
            )
            .map(TupleStorage::Numeric)
            .map(Tuple),
            TupleStorage::Named(items) => rc_slice_try_from_iter(
                items.len(),
                items
                    .iter()
                    .map(|(name, value)| value.to_static().map(|value| (name.clone(), value))),
            )
            .map(TupleStorage::Named)
            .map(Tuple),
        }
    }
}

impl Tuple<StaticValue> {
    #[must_use]
    pub fn to_runtime<'host>(&self) -> Tuple<Value<'host>> {
        match &self.0 {
            TupleStorage::Numeric(items) => Tuple(TupleStorage::Numeric(rc_slice_from_iter(
                items.len(),
                items.iter().map(Value::from),
            ))),
            TupleStorage::Named(items) => Tuple(TupleStorage::Named(rc_slice_from_iter(
                items.len(),
                items
                    .iter()
                    .map(|(name, value)| (name.clone(), value.into())),
            ))),
        }
    }
}

impl<'host, T: Borrow<Tuple<StaticValue>>> From<T> for Tuple<Value<'host>> {
    fn from(value: T) -> Self {
        value.borrow().to_runtime()
    }
}

impl<'host> TryFrom<Tuple<Value<'host>>> for Tuple<ComplexType> {
    type Error = Error;

    fn try_from(tuple: Tuple<Value<'host>>) -> Result<Self, Self::Error> {
        match &tuple.0 {
            TupleStorage::Numeric(items) => rc_slice_try_from_iter(
                items.len(),
                items.iter().map(|value| value.clone().try_into()),
            )
            .map(TupleStorage::Numeric)
            .map(Tuple),
            TupleStorage::Named(items) => rc_slice_try_from_iter(
                items.len(),
                items.iter().map(|(name, value)| {
                    value.clone().try_into().map(|value| (name.clone(), value))
                }),
            )
            .map(TupleStorage::Named)
            .map(Tuple),
        }
    }
}

impl From<Tuple<ComplexType>> for Tuple<Value<'_>> {
    fn from(tuple: Tuple<ComplexType>) -> Self {
        match &tuple.0 {
            TupleStorage::Numeric(items) => Tuple(TupleStorage::Numeric(rc_slice_from_iter(
                items.len(),
                items.iter().map(|value| value.clone().into()),
            ))),
            TupleStorage::Named(items) => Tuple(TupleStorage::Named(rc_slice_from_iter(
                items.len(),
                items
                    .iter()
                    .map(|(name, value)| (name.clone(), value.clone().into())),
            ))),
        }
    }
}

impl<'host> TryFrom<Tuple<Value<'host>>> for Tuple<Function<'host>> {
    type Error = Error;

    fn try_from(tuple: Tuple<Value<'host>>) -> Result<Self, Self::Error> {
        match &tuple.0 {
            TupleStorage::Numeric(items) => rc_slice_try_from_iter(
                items.len(),
                items.iter().map(|value| value.clone().try_into()),
            )
            .map(TupleStorage::Numeric)
            .map(Tuple),
            TupleStorage::Named(items) => rc_slice_try_from_iter(
                items.len(),
                items.iter().map(|(name, value)| {
                    value.clone().try_into().map(|value| (name.clone(), value))
                }),
            )
            .map(TupleStorage::Named)
            .map(Tuple),
        }
    }
}

impl<T> From<Rc<[T]>> for Tuple<T> {
    fn from(value: Rc<[T]>) -> Self {
        Self(TupleStorage::Numeric(value))
    }
}

impl<const N: usize, T> From<[T; N]> for Tuple<T> {
    fn from(value: [T; N]) -> Self {
        Self(TupleStorage::Numeric(Rc::from(value)))
    }
}

impl<T> From<Rc<[(String, T)]>> for Tuple<T> {
    fn from(value: Rc<[(String, T)]>) -> Self {
        Self(TupleStorage::Named(value))
    }
}

impl<const N: usize, K: Into<String>, T> From<[(K, T); N]> for Tuple<T> {
    fn from(value: [(K, T); N]) -> Self {
        let slice = rc_slice_from_iter(value.len(), value.into_iter().map(|(k, v)| (k.into(), v)));
        Self(TupleStorage::Named(slice))
    }
}

/// An function which is callable by espy or its host.
///
/// This differs from [`Program`] in that it may accept an argument;
/// use [`Function::pipe`] or [`Function::piped`] to provide one,
/// and [`Function::eval`] to evaluate the function.
///
/// To instead provide a Rust function to espy, use [`Function::borrow`] or
/// [`Function::owned`] with the [`ExternFn`] and [`ExternFnOwned`] traits,
/// respectively.
#[derive(Clone, Debug)]
pub struct Function<'host> {
    action: FunctionAction<'host>,
    argument: Value<'host>,
}

/// A version of [`Function`] with a static lifetime.
///
/// See [`StaticValue`] for the difference between this and [`Function<'static>`].
#[derive(Clone)]
pub struct StaticFunction {
    action: StaticFunctionAction,
    argument: StaticValue,
}

impl std::fmt::Debug for StaticFunction {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{:?}", self.to_runtime())
    }
}

impl StaticFunction {
    #[must_use]
    pub fn to_runtime<'host>(&self) -> Function<'host> {
        Function {
            action: match &self.action {
                StaticFunctionAction::With {
                    program,
                    block_id,
                    program_counter,
                    signature,
                    captures,
                } => FunctionAction::With {
                    program: program.clone(),
                    block_id: *block_id,
                    program_counter: *program_counter,
                    signature: signature.clone(),
                    captures: rc_slice_from_iter(
                        captures.len(),
                        captures
                            .iter()
                            .map(|value: &StaticValue| value.clone().into()),
                    ),
                },
                StaticFunctionAction::Never { signature } => FunctionAction::Never {
                    signature: signature.clone(),
                },
                StaticFunctionAction::Enum {
                    variant,
                    definition,
                } => FunctionAction::Enum {
                    variant: *variant,
                    definition: definition.clone(),
                },
                StaticFunctionAction::Mut => FunctionAction::Mut,
                StaticFunctionAction::OptionConstructor => FunctionAction::OptionConstructor,
                StaticFunctionAction::OptionCase { some, ty } => FunctionAction::OptionCase {
                    some: *some,
                    ty: ty.clone(),
                },
                StaticFunctionAction::Borrow(extern_fn) => FunctionAction::Borrow(*extern_fn),
                StaticFunctionAction::Owned(extern_fn_owned) => {
                    FunctionAction::Owned(extern_fn_owned.clone())
                }
            },
            argument: self.argument.to_runtime(),
        }
    }
}

impl<'host, T: Borrow<StaticFunction>> From<T> for Function<'host> {
    fn from(value: T) -> Self {
        value.borrow().to_runtime()
    }
}

impl StaticFunction {
    pub fn borrow(external: &'static dyn ExternFn) -> Self {
        StaticFunction {
            action: StaticFunctionAction::Borrow(external),
            argument: StaticValue::Unit,
        }
    }

    pub fn owned(external: Rc<dyn ExternFnOwned>) -> Self {
        StaticFunction {
            action: StaticFunctionAction::Owned(external),
            argument: StaticValue::Unit,
        }
    }
}

impl<'host> Function<'host> {
    pub fn borrow(external: &'host dyn ExternFn) -> Self {
        Function {
            action: FunctionAction::Borrow(external),
            argument: ().into(),
        }
    }

    pub fn owned(external: Rc<dyn ExternFnOwned>) -> Self {
        Function {
            action: FunctionAction::Owned(external),
            argument: ().into(),
        }
    }

    /// # Errors
    ///
    /// Returns an error if the value is mutable or an external value that
    /// cannot be made static.
    pub fn to_static(&self) -> Result<StaticFunction, Error> {
        Ok(StaticFunction {
            action: match &self.action {
                FunctionAction::With {
                    program,
                    block_id,
                    program_counter,
                    signature,
                    captures,
                } => StaticFunctionAction::With {
                    program: program.clone(),
                    block_id: *block_id,
                    program_counter: *program_counter,
                    signature: signature.clone(),
                    captures: captures
                        .iter()
                        .map(|x| x.to_static())
                        .collect::<Result<_, Error>>()?,
                },
                FunctionAction::Never { signature } => StaticFunctionAction::Never {
                    signature: signature.clone(),
                },
                FunctionAction::Enum {
                    variant,
                    definition,
                } => StaticFunctionAction::Enum {
                    variant: *variant,
                    definition: definition.clone(),
                },
                FunctionAction::Mut => StaticFunctionAction::Mut,
                FunctionAction::OptionConstructor => StaticFunctionAction::OptionConstructor,
                FunctionAction::OptionCase { some, ty } => StaticFunctionAction::OptionCase {
                    some: *some,
                    ty: ty.clone(),
                },
                FunctionAction::Borrow(extern_fn_borrow) => StaticFunctionAction::Borrow(
                    extern_fn_borrow
                        .to_static()
                        .ok_or(Error::from(ErrorKind::NotStatic))?,
                ),
                FunctionAction::Owned(extern_fn_owned) => {
                    StaticFunctionAction::Owned(extern_fn_owned.clone())
                }
            },
            argument: self.argument.to_static()?,
        })
    }

    /// # Errors
    ///
    /// Returns an error if evaluating the function results in an error
    pub fn eval(self) -> Result<Value<'host>, Error> {
        let result = match self.action {
            FunctionAction::With {
                program,
                block_id,
                program_counter,
                signature: FunctionType { input, output },
                captures,
            } => {
                if !self.argument.type_of()?.compare(&input) {
                    return Err(Error::type_error(&self.argument, &input));
                }
                let result =
                    program.eval_block(block_id, program_counter, captures, self.argument)?;
                if !result.type_of()?.compare(&output) {
                    return Err(Error::type_error(&result, &output));
                }
                result
            }
            FunctionAction::Never { signature: _ } => {
                return Err(ErrorKind::CalledNeverFunction.into());
            }
            FunctionAction::Enum {
                variant,
                definition,
            } => {
                let ty = &definition.variants[variant].1;
                if *ty != Type::Any.into() && self.argument.type_of()? != *ty {
                    return Err(Error::type_error(&self.argument, ty));
                }
                Value::EnumVariant(Rc::new(EnumVariant {
                    contents: self.argument,
                    variant,
                    definition,
                }))
            }
            FunctionAction::Mut => {
                if let Ok(ty) = ComplexType::try_from(self.argument.clone()) {
                    Type::Mut(Rc::new(ty)).into()
                } else {
                    Value::Mut(Mut::new(Rc::new(RefCell::new(self.argument))))
                }
            }
            FunctionAction::OptionConstructor => {
                Type::Option(Rc::new(self.argument.into_complex_type()?)).into()
            }
            FunctionAction::OptionCase { some: true, ty } => {
                if self.argument.type_of()? != ty {
                    return Err(Error::type_error(&self.argument, &ty));
                }
                Value::Option {
                    contents: Some(Rc::new(self.argument)),
                    ty,
                }
            }
            FunctionAction::OptionCase { some: false, ty } => {
                self.argument.unit()?;
                Value::Option { contents: None, ty }
            }
            FunctionAction::Borrow(external) => external.call(self.argument)?,
            FunctionAction::Owned(external) => external.call(self.argument)?,
        };
        Ok(result)
    }

    /// Concatentes the function's argument list with `argument`.
    pub fn pipe(&mut self, argument: Value<'host>) {
        let mut arguments = ().into();
        mem::swap(&mut arguments, &mut self.argument);
        arguments = Value::concat(arguments, argument);
        mem::swap(&mut arguments, &mut self.argument);
    }

    #[must_use]
    pub fn piped(mut self, argument: Value<'host>) -> Self {
        self.pipe(argument);
        self
    }
}

#[derive(Clone)]
enum FunctionAction<'host> {
    With {
        program: Program,
        block_id: usize,
        program_counter: usize,
        signature: FunctionType,
        captures: Rc<[Value<'host>]>,
    },
    Never {
        signature: FunctionType,
    },
    Enum {
        variant: usize,
        definition: Rc<EnumType>,
    },
    Mut,
    OptionConstructor,
    OptionCase {
        some: bool,
        ty: ComplexType,
    },
    Borrow(&'host dyn ExternFn),
    Owned(Rc<dyn ExternFnOwned>),
}

#[derive(Clone)]
enum StaticFunctionAction {
    With {
        program: Program,
        block_id: usize,
        program_counter: usize,
        signature: FunctionType,
        captures: Rc<[StaticValue]>,
    },
    Never {
        signature: FunctionType,
    },
    Enum {
        variant: usize,
        definition: Rc<EnumType>,
    },
    Mut,
    OptionConstructor,
    OptionCase {
        some: bool,
        ty: ComplexType,
    },
    Borrow(&'static dyn ExternFn),
    Owned(Rc<dyn ExternFnOwned>),
}

impl<'host> From<FunctionAction<'host>> for Function<'host> {
    fn from(action: FunctionAction<'host>) -> Self {
        Self {
            action,
            argument: ().into(),
        }
    }
}

impl std::fmt::Debug for FunctionAction<'_> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Self::With {
                program,
                block_id,
                program_counter,
                signature,
                captures,
            } => f
                .debug_struct("Block")
                .field("program", &Rc::as_ptr(&program.bytes))
                .field("block_id", block_id)
                .field("program_counter", program_counter)
                .field("signature", signature)
                .field("captures", captures)
                .finish(),
            Self::Never { signature } => f
                .debug_struct("Never")
                .field("signature", signature)
                .finish(),
            Self::Enum {
                variant,
                definition,
            } => f
                .debug_struct("Enum")
                .field("variant", variant)
                .field("definition", definition)
                .finish(),
            Self::Mut => write!(f, "Mut"),
            Self::OptionConstructor => write!(f, "Option"),
            Self::OptionCase { some: true, ty } => f.debug_tuple("Some").field(ty).finish(),
            Self::OptionCase { some: false, ty } => f.debug_tuple("None").field(ty).finish(),
            Self::Borrow(arg0) => arg0.debug(f),
            Self::Owned(arg0) => arg0.debug(f),
        }
    }
}

#[derive(Debug)]
enum MutRefSource<'host> {
    Origin(Rc<RefCell<Value<'host>>>),
    Child(Weak<RefCell<Value<'host>>>),
}

/// A mutable reference to an espy value.
///
/// espy does not have inherited mutability, only interior mutability.
/// This means that [`Mut`] contains a [`RefCell`].
///
/// Only the original [`Mut`] contains a strong [`Rc`] to its contained
/// value; any time the mutable reference is copied the copy is instead a weak
/// reference. This prevents reference cycles from being constructed by espy
/// programs to leak memory. However, [`Mut::upgrade`] is provided for hosts to
/// upgrade weak references into strong ones should the need arise.
#[derive(Debug)]
pub struct Mut<'host> {
    source: MutRefSource<'host>,
}

impl<'host> Mut<'host> {
    pub fn new(rc: Rc<RefCell<Value<'host>>>) -> Self {
        Self {
            source: MutRefSource::Origin(rc),
        }
    }

    /// Creates a strong reference to the mutable reference's origin if it still exists.
    ///
    /// This can be used to create reference cycles and leak memory,
    /// so it should only be exposed to trusted espy programs.
    #[must_use]
    pub fn upgrade(&self) -> Option<Rc<RefCell<Value<'host>>>> {
        match &self.source {
            MutRefSource::Origin(rc) => Some(rc.clone()),
            MutRefSource::Child(weak) => weak.upgrade(),
        }
    }
}

impl Clone for Mut<'_> {
    fn clone(&self) -> Self {
        Self {
            source: MutRefSource::Child(match &self.source {
                MutRefSource::Origin(rc) => Rc::downgrade(rc),
                MutRefSource::Child(weak) => weak.clone(),
            }),
        }
    }
}

/// The combined type of a [`Function`]'s input and output.
#[derive(Clone, Debug)]
pub struct FunctionType {
    pub input: ComplexType,
    pub output: ComplexType,
}

/// An instance of an [`EnumType`].
///
/// Use [`EnumVariant::variant`] to determine which variant this is intended to be,
/// and [`EnumVariant::contents`] to read that variant's value.
///
/// If you're interested in the [`EnumType`] this variant corresponds to, you
/// can use [`EnumVariant::definition`]. Conversely if you care only about the
/// enum's reported name and value and not the type it originated from, use
/// [`EnumVariant::unwrap`].
#[derive(Clone, Debug)]
pub struct EnumVariant<'host> {
    contents: Value<'host>,
    variant: usize,
    definition: Rc<EnumType>,
}

/// A version of [`EnumVariant`] with a static lifetime.
///
/// See [`StaticValue`] for the difference between this and [`EnumVariant<'static>`].
#[derive(Clone, Debug)]
pub struct StaticEnumVariant {
    contents: StaticValue,
    variant: usize,
    definition: Rc<EnumType>,
}

impl StaticEnumVariant {
    #[must_use]
    pub fn to_runtime<'host>(&self) -> EnumVariant<'host> {
        EnumVariant {
            contents: self.contents.to_runtime(),
            variant: self.variant,
            definition: self.definition.clone(),
        }
    }
}

impl<'host, T: Borrow<StaticEnumVariant>> From<T> for EnumVariant<'host> {
    fn from(value: T) -> Self {
        value.borrow().to_runtime()
    }
}

impl<'host> EnumVariant<'host> {
    #[must_use]
    pub fn contents(&self) -> &Value<'host> {
        &self.contents
    }

    #[must_use]
    pub fn definition(&self) -> &Rc<EnumType> {
        &self.definition
    }

    #[must_use]
    pub fn variant(&self) -> usize {
        self.variant
    }

    #[must_use]
    pub fn split(self) -> (String, Value<'host>) {
        (
            self.definition.variants[self.variant].0.clone(),
            self.contents,
        )
    }
}

/// The definition of an espy enum.
///
/// See [`EnumVariant`] also.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct EnumType {
    pub variants: Rc<[(String, ComplexType)]>,
}

impl From<Rc<EnumType>> for Type {
    fn from(value: Rc<EnumType>) -> Self {
        Type::Enum(value)
    }
}

impl From<EnumType> for Type {
    fn from(value: EnumType) -> Self {
        Rc::new(value).into()
    }
}

/// Reads a u32 and casts it to usize for convenience.
fn read_header(bytes: &[u8], at: usize) -> Result<usize, InvalidBytecode> {
    let (((a, b), c), d) = bytes
        .get(at)
        .zip(bytes.get(at + 1))
        .zip(bytes.get(at + 2))
        .zip(bytes.get(at + 3))
        .ok_or(InvalidBytecode::MalformedHeader)?;
    Ok(u32::from_le_bytes([*a, *b, *c, *d]) as usize)
}

fn block_count(bytes: &[u8]) -> Result<usize, InvalidBytecode> {
    read_header(bytes, 0)
}

fn string_count(bytes: &[u8]) -> Result<usize, InvalidBytecode> {
    read_header(bytes, size_of::<u32>())
}

fn offsets(bytes: &[u8]) -> Result<&[u8], InvalidBytecode> {
    let offset_count = block_count(bytes)? + string_count(bytes)?;
    let first_offset = size_of::<u32>() * 2;
    let last_offset = first_offset + size_of::<u32>() * offset_count;
    bytes
        .get(first_offset..last_offset)
        .ok_or(InvalidBytecode::MalformedHeader)
}

fn block(bytes: &[u8], block_id: usize) -> Result<&[u8], InvalidBytecode> {
    let offsets = offsets(bytes)?;
    let block_position = size_of::<u32>() * block_id;
    let start = read_header(offsets, block_position)?;
    let end = read_header(offsets, size_of::<u32>() + block_position).unwrap_or(bytes.len());
    bytes
        .get(start..end)
        .ok_or(InvalidBytecode::MalformedHeader)
}

struct Frame<'a, 'host> {
    bytecode: &'a [u8],
    pc: usize,
    captures: Option<(Rc<[Value<'host>]>, NonZero<usize>)>,
    stack: Vec<Value<'host>>,
}

impl<'host> Frame<'_, 'host> {
    fn next(&mut self) -> Result<u8, InvalidBytecode> {
        let next = self
            .bytecode
            .get(self.pc)
            .ok_or(InvalidBytecode::ProgramOutOfBounds)?;
        self.pc += 1;
        Ok(*next)
    }

    fn next4(&mut self) -> Result<usize, InvalidBytecode> {
        Ok(u32::from_le_bytes([self.next()?, self.next()?, self.next()?, self.next()?]) as usize)
    }

    fn next_i64(&mut self) -> Result<i64, InvalidBytecode> {
        Ok(i64::from_le_bytes([
            self.next()?,
            self.next()?,
            self.next()?,
            self.next()?,
            self.next()?,
            self.next()?,
            self.next()?,
            self.next()?,
        ]))
    }

    fn stack_len(&self) -> usize {
        self.captures
            .as_ref()
            .map_or(0, |captures| captures.1.into())
            + self.stack.len()
    }

    fn get(&self, index: usize) -> Result<&Value<'host>, InvalidBytecode> {
        if let Some((captures, len)) = &self.captures {
            if index < usize::from(*len) {
                captures.get(index)
            } else {
                self.stack.get(index - usize::from(*len))
            }
        } else {
            self.stack.get(index)
        }
        .ok_or(InvalidBytecode::StackOutOfBounds)
    }

    fn push(&'_ mut self, value: Value<'host>) {
        self.stack.push(value);
    }

    fn pop(&'_ mut self) -> Result<Value<'host>, Error> {
        self.stack.pop().map_or_else(
            || {
                if let Some((captures, len)) = &mut self.captures {
                    let capture = captures[usize::from(*len) - 1].clone();
                    if let Ok(new_len) = NonZero::try_from(usize::from(*len) - 1) {
                        *len = new_len;
                    } else {
                        self.captures = None;
                    }
                    Ok(capture)
                } else {
                    Err(InvalidBytecode::StackUnderflow.into())
                }
            },
            Ok,
        )
    }

    fn into_bind(mut self, program: Program, block_id: usize) -> Result<Value<'host>, Error> {
        Ok(Value::Tuple(
            [
                self.pop()?,
                Function {
                    action: FunctionAction::With {
                        program,
                        block_id,
                        program_counter: self.pc,
                        signature: FunctionType {
                            input: Type::Any.into(),
                            output: Type::Any.into(),
                        },
                        captures: rc_slice_from_iter(
                            self.stack_len(),
                            self.captures
                                .iter()
                                .flat_map(|captures| {
                                    captures.0[0..captures.1.into()].iter().cloned()
                                })
                                .chain(self.stack),
                        ),
                    },
                    argument: Value::Unit,
                }
                .into(),
            ]
            .into(),
        ))
    }
}

enum StepOutcome<'a, 'host> {
    Frame(Frame<'a, 'host>),
    Yield(Value<'host>),
}

/// An espy program which has been loaded into memory and is ready to be executed.
///
/// This program will be kept alive by any [`Function`]s it produces. If you
/// intend on returning a small function from a large program and are concerned
/// about the memory usage, consider moving that function and its dependencies
/// to its own program, whose memory can then be managed separately.
#[derive(Clone, Debug)]
pub struct Program {
    pub(crate) bytes: Rc<[u8]>,
    owned_strings: Rc<[Rc<str>]>,
}

impl TryFrom<Rc<[u8]>> for Program {
    type Error = Error;

    fn try_from(bytes: Rc<[u8]>) -> Result<Self, Self::Error> {
        let string_count = string_count(&bytes)?;
        let owned_strings = (0..string_count)
            .map(|string| {
                let string = size_of::<u32>() * (string + block_count(&bytes)?);
                let offsets = offsets(&bytes)?;
                let start = read_header(offsets, string)?;
                let end = read_header(offsets, size_of::<u32>() + string).unwrap_or(bytes.len());
                let string_bytes = bytes
                    .get(start..end)
                    .ok_or(InvalidBytecode::MalformedHeader)?;
                let string = str::from_utf8(string_bytes).map_err(InvalidBytecode::Utf8Error)?;
                Ok(Rc::from(string))
            })
            .collect::<Result<_, Error>>()?;
        Ok(Self {
            bytes,
            owned_strings,
        })
    }
}

impl Program {
    /// # Errors
    ///
    /// Returns an error if the evaluating the program results in an error
    pub fn eval<'host>(&self) -> Result<Value<'host>, Error> {
        self.eval_block(0, 0, None, None)
    }

    fn eval_block<'host>(
        &self,
        block_id: usize,
        program_counter: usize,
        captures: impl Into<Option<Rc<[Value<'host>]>>>,
        argument: impl Into<Option<Value<'host>>>,
    ) -> Result<Value<'host>, Error> {
        let captures = captures
            .into()
            .and_then(|x| x.len().try_into().ok().map(|len| (x, len)));
        let mut frame = Frame {
            bytecode: block(&self.bytes, block_id)?,
            pc: program_counter,
            captures,
            stack: argument.into().into_iter().collect(),
        };
        // Program counter, ignoring block boundries.
        let absolute_program_counter =
            frame.bytecode.as_ptr() as usize - block(&self.bytes, 0)?.as_ptr() as usize;

        // The program counter reaching the first (and only the first)
        // out-of-bounds byte should be considered a return.
        while frame.pc != frame.bytecode.len() {
            let pc = frame.pc;
            frame = match self
                .eval_step(block_id, frame)
                .map_err(|e| e.suggest_location(absolute_program_counter + pc))?
            {
                StepOutcome::Frame(frame) => frame,
                StepOutcome::Yield(value) => return Ok(value),
            }
        }
        frame.pop()
    }

    fn eval_step<'a, 'host>(
        &self,
        block_id: usize,
        mut frame: Frame<'a, 'host>,
    ) -> Result<StepOutcome<'a, 'host>, Error> {
        macro_rules! bi_op {
            (let $l:ident, $r:ident: $type:ident => $expr_type:ident: $expr:expr) => {{
                let $r = frame.pop()?;
                let $l = frame.pop()?;
                match (&$l, &$r) {
                    (Value::$type($l), Value::$type($r)) => frame.push(Value::$expr_type($expr)),
                    _ => return Err(Error::expected_integers(&$l, &$r)),
                }
            }};
        }
        macro_rules! bi_num {
            (let $l:ident, $r:ident => $expr:expr) => {
                bi_op!(let $l, $r: I64 => I64: $expr)
            };
        }
        macro_rules! bi_cmp {
            (let $l:ident, $r:ident => $expr:expr) => {
                bi_op!(let $l, $r: I64 => Bool: $expr)
            };
        }
        let instruction = frame.next()?;
        match instruction {
            instruction::CLONE => {
                let index = frame.next4()?;
                #[allow(
                    clippy::cast_possible_truncation,
                    clippy::cast_possible_wrap,
                    reason = "next4 only returns 32 bits"
                )]
                match index as i32 {
                    0.. => {
                        let value = frame.get(index)?;
                        frame.push(value.clone());
                    }
                    builtins::ANY => {
                        frame.push(Type::Any.into());
                    }
                    builtins::UNIT => {
                        frame.push(Type::Unit.into());
                    }
                    builtins::I64 => {
                        frame.push(Type::I64.into());
                    }
                    builtins::STRING => {
                        frame.push(Type::String.into());
                    }
                    builtins::OPTION => {
                        frame.push(Value::Function(Rc::new(
                            FunctionAction::OptionConstructor.into(),
                        )));
                    }
                    builtins::MUT => {
                        frame.push(Value::Function(Rc::new(FunctionAction::Mut.into())));
                    }
                    _ => Err(InvalidBytecode::InvalidBuiltin)?,
                }
            }
            instruction::POP => {
                frame.pop()?;
            }
            instruction::COLLAPSE => {
                let value = frame.pop()?;
                for _ in 0..(frame.stack_len() - frame.next4()?) {
                    frame.pop()?;
                }
                frame.push(value);
            }
            instruction::JUMP => {
                frame.pc = frame.next4()?;
            }
            instruction::IF => {
                let target = frame.next4()?;
                if let Value::Bool(false) = frame.pop()? {
                    frame.pc = target;
                }
            }

            instruction::PUSH_UNIT => {
                frame.push(().into());
            }
            instruction::PUSH_TRUE => {
                frame.push(true.into());
            }
            instruction::PUSH_FALSE => {
                frame.push(false.into());
            }
            instruction::PUSH_I64 => {
                let i = frame.next_i64()?.into();
                frame.push(i);
            }
            instruction::PUSH_STRING => {
                let string_id = frame.next4()?;
                let string = self
                    .owned_strings
                    .get(string_id)
                    .ok_or(InvalidBytecode::InvalidStringId)?
                    .clone();
                frame.push(string.into());
            }
            instruction::PUSH_FUNCTION => {
                let captures = frame.next4()?;
                let function = frame.next4()?;
                let output = frame.pop()?;
                let input = frame.pop()?;
                if function == 0 {
                    // ignore captures if the function will never be called.
                    for _ in 0..captures {
                        frame.pop()?;
                    }
                    frame.push(Value::Function(Rc::new(
                        FunctionAction::Never {
                            signature: FunctionType {
                                input: input.try_into()?,
                                output: output.try_into()?,
                            },
                        }
                        .into(),
                    )));
                } else {
                    let new_stack =
                        rc_slice_try_from_iter_rev(captures, (0..captures).map(|_| frame.pop()))?;
                    frame.push(Value::Function(Rc::new(
                        FunctionAction::With {
                            program: self.clone(),
                            signature: FunctionType {
                                input: input.try_into()?,
                                output: output.try_into()?,
                            },
                            block_id: function,
                            program_counter: 0,
                            captures: new_stack,
                        }
                        .into(),
                    )));
                }
            }
            instruction::PUSH_ENUM => {
                let variants = frame.pop()?;
                let Value::Tuple(Tuple(TupleStorage::Named(variants))) = variants else {
                    Err(Error::expected_named_tuple(&variants))?
                };
                let variants = rc_slice_try_from_iter(
                    variants.len(),
                    variants.iter().map(|(name, value)| {
                        value.clone().try_into().map(|value| (name.clone(), value))
                    }),
                )?;
                frame.push(Type::from(EnumType { variants }).into());
            }

            instruction::ADD => bi_num!(let l, r => l + r),
            instruction::SUB => bi_num!(let l, r => l - r),
            instruction::MUL => bi_num!(let l, r => l * r),
            instruction::DIV => bi_num!(let l, r => l / r),
            instruction::BITWISE_AND => bi_num!(let l, r => l & r),
            instruction::BITWISE_OR => bi_num!(let l, r => l | r),
            instruction::BITWISE_XOR => bi_num!(let l, r => l ^ r),
            instruction::GREATER => bi_cmp!(let l, r => l > r),
            instruction::GREATER_EQUAL => bi_cmp!(let l, r => l >= r),
            instruction::LESSER => bi_cmp!(let l, r => l < r),
            instruction::LESSER_EQUAL => bi_cmp!(let l, r => l <= r),
            instruction::MATCHES => {
                let candidate = frame.pop()?;
                let subject = frame.pop()?;
                if let Value::EnumVariant(subject) = &subject
                    && let Value::Function(function) = &candidate
                    && let FunctionAction::Enum {
                        variant,
                        definition,
                    } = &function.action
                    && subject.definition == *definition
                {
                    // Destructuring changes the value forwarded to the match arm.
                    if subject.variant == *variant {
                        frame.pop()?;
                        frame.push(subject.contents.clone());

                        frame.push(true.into());
                    } else {
                        frame.push(false.into());
                    }
                } else if let Value::Option { contents, ty } = &subject
                    && let Value::Function(function) = &candidate
                    && let FunctionAction::OptionCase {
                        some,
                        ty: expected_ty,
                    } = &function.action
                {
                    match (contents, some) {
                        (Some(contents), true) => {
                            if !ty.compare(expected_ty) {
                                return Err(Error::type_error(&subject, expected_ty));
                            }
                            // Destructuring changes the value forwarded to the match arm.
                            frame.pop()?;
                            frame.push((**contents).clone());
                            frame.push(true.into());
                        }
                        (None, false) => {
                            // Destructuring changes the value forwarded to the match arm.
                            frame.pop()?;
                            frame.push(().into());
                            frame.push(true.into());
                        }
                        _ => {
                            frame.push(false.into());
                        }
                    }
                } else {
                    frame.push(subject.clone().eq(candidate)?.into());
                }
            }
            instruction::EQUAL_TO => {
                let r = frame.pop()?;
                let l = frame.pop()?;
                frame.push(l.eq(r)?.into());
            }
            instruction::NOT_EQUAL_TO => {
                let r = frame.pop()?;
                let l = frame.pop()?;
                frame.push((!l.eq(r)?).into());
            }
            instruction::LOGICAL_AND => bi_op!(let l, r: Bool => Bool: *l && *r),
            instruction::LOGICAL_OR => bi_op!(let l, r: Bool => Bool: *l || *r),
            instruction::PIPE => {
                let mut function = Rc::<Function>::try_from(frame.pop()?)?;
                let argument = frame.pop()?;
                let function_mut = Rc::make_mut(&mut function);
                let mut arguments = ().into();
                mem::swap(&mut arguments, &mut function_mut.argument);
                arguments = Value::concat(arguments, argument);
                mem::swap(&mut arguments, &mut function_mut.argument);
                frame.push(Value::Function(function));
            }

            instruction::CALL => {
                let argument = frame.pop()?;
                let function = frame.pop()?;
                let result = match function {
                    Value::Function(function) => Rc::<Function>::try_unwrap(function)
                        .unwrap_or_else(|function| (*function).clone())
                        .piped(argument)
                        .eval()?,
                    function => Err(Error::expected_function(&function))?,
                };
                frame.push(result);
            }
            instruction::JOIN => {
                let r = frame.pop()?;
                let l = frame.pop()?;
                frame.push(Value::concat(l, r));
            }
            instruction::LIST => {
                let length = frame.next4()?;
                let tuple = rc_slice_try_from_iter_rev(length, (0..length).map(|_| frame.pop()))?;
                frame.push(Tuple::from(tuple).into());
            }
            instruction::INDEX => {
                let index = frame.pop()?;
                let container = frame.pop()?;
                frame.push(container.index(index)?);
            }
            instruction::TRY_INDEX => {
                let index = frame.pop()?;
                let container = frame.pop()?;
                frame.push(container.index(index).ok().into());
            }
            instruction::NAME => {
                let name_id = frame.next4()?;
                let name = self
                    .owned_strings
                    .get(name_id)
                    .ok_or(InvalidBytecode::InvalidStringId)?
                    .clone();
                let value = frame.pop()?;
                frame.push(Value::Tuple(Tuple::from([(name, value)])));
            }
            instruction::NEGATIVE => {
                let value = frame.pop()?.i64()?;
                frame.push((-value).into());
            }
            instruction::DEREF => {
                let value = frame.pop()?.into_refcell()?;
                frame.push(value.try_borrow().map_err(Error::other)?.clone());
            }
            instruction::SET => {
                let value = frame.pop()?;
                let target = frame.pop()?.into_refcell()?;
                *target.borrow_mut() = value;
            }
            instruction::BIND => {
                let bind = frame.pop()?.function()?;
                return Ok(StepOutcome::Yield(
                    bind.piped(frame.into_bind(self.clone(), block_id)?)
                        .eval()?,
                ));
            }
            instruction::YIELD => {
                return Ok(StepOutcome::Yield(frame.into_bind(self.clone(), block_id)?));
            }

            _ => Err(InvalidBytecode::InvalidInstruction)?,
        };
        Ok(StepOutcome::Frame(frame))
    }
}

#[allow(clippy::missing_errors_doc)]
pub trait Extern {
    fn index<'host>(&'host self, index: Value<'host>) -> Result<Value<'host>, Error>;

    fn to_static(&self) -> Option<&'static dyn Extern> {
        None
    }

    /// Allows the [`Extern`] trait object to be downcasted back into its original type.
    ///
    /// Implementing this method is optional.
    /// The default implementation will always return `None` and reject all downcasting attempts via [`Value::downcast_extern`].
    fn any(&self) -> Option<&dyn Any> {
        None
    }

    fn debug(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{{external value}}")
    }
}

#[allow(clippy::missing_errors_doc)]
pub trait ExternOwned {
    /// Note that self's reference count will always be greater than one,
    /// so [`Rc::unwrap_or_clone`], [`Rc::get_mut`], etc. are useless.
    fn index<'host>(self: Rc<Self>, index: Value<'host>) -> Result<Value<'host>, Error>;

    /// Allows the [`ExternOwned`] trait object to be downcasted back into its original type.
    ///
    /// Implementing this method is optional.
    /// The default implementation will always return `None` and reject all downcasting attempts via [`Value::downcast_extern`].
    ///
    /// There is no way to downcast from an [`Rc<dyn Any>`],
    /// so this functin has the same signature as [`Extern`]'s equivalent.
    fn any(&self) -> Option<&dyn Any> {
        None
    }

    fn debug(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{{external value}}")
    }
}

#[allow(clippy::missing_errors_doc)]
pub trait ExternFn {
    fn call<'host>(&'host self, argument: Value<'host>) -> Result<Value<'host>, Error>;

    fn to_static(&self) -> Option<&'static dyn ExternFn> {
        None
    }

    fn debug(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{{external function}}")
    }
}

#[allow(clippy::missing_errors_doc)]
pub trait ExternFnOwned {
    /// Note that self's reference count will always be greater than one when a function is called from espy,
    /// so [`Rc::unwrap_or_clone`], [`Rc::get_mut`], etc. are useless.
    fn call<'host>(self: Rc<Self>, argument: Value<'host>) -> Result<Value<'host>, Error>;

    fn debug(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{{external function}}")
    }
}