The kcats Programming Language (Production Implementation)

//! Defines kcats internal data types.
/// Include Our own traits so we aren't saddled with orphan rule
/// issues.
use crate::list;
use crate::traits::*;
use crate::types::container as coll;
use crate::types::container::dictionary as dict;
use crate::types::container::environment as env;
use crate::types::container::error::Error;
use crate::types::container::Mutey;

use core::default::Default;
use internment::Intern;
use lazy_static::lazy_static;
use std::collections::{HashMap, VecDeque};

use std::fmt;
use std::hash::Hash;
use std::marker::Sync;

use std::pin::Pin;

pub mod container;
pub mod number;

/// A Word causes a kcats program to do something, usually taking some
/// items derive the top of the stack, and using them to create new
/// stack items. (examples: `swap`, `+`, `dip`).
#[derive(Clone, Eq, Hash, Debug, PartialOrd, Ord, Default)]
pub struct Word {
    pub data: Intern<String>,
    pub namespace: dict::Namespace,
}

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

impl Derive<String> for Word {
    fn derive(s: String) -> Self {
        Word::derive(s.as_str())
    }
}

impl Derive<&str> for Word {
    fn derive(s: &str) -> Self {
        Word {
            data: Intern::<String>::from(s),
            namespace: Default::default(),
        }
    }
}

impl<'a> Derive<&'a Word> for &'a str {
    fn derive(s: &'a Word) -> Self {
        s.data.as_str()
    }
}

impl Derive<Word> for String {
    fn derive(s: Word) -> Self {
        s.data.to_string()
    }
}

/// Represents a stack (the part of an
/// [crate::types::container::environment::Environment] that holds the data
/// values being manipulated by the program).
pub type Stack = container::List;

/// A byte array type
pub type Bytes = Vec<u8>;

/// A character type
pub type Char = char;

lazy_static! {
    pub static ref S_ASSOC: Word = Word::derive("association");
    pub static ref S_BOOLEAN: Word = Word::derive("boolean");
    pub static ref S_BYTES: Word = Word::derive("bytes");
    pub static ref S_CHAR: Word = Word::derive("character");
    pub static ref S_DICTIONARY: Word = Word::derive("dictionary");
    pub static ref S_DISPENSER: Word = Word::derive("dispenser");
    pub static ref S_ENVIRONMENT: Word = Word::derive("environment");
    pub static ref S_ERROR: Word = Word::derive("error");
    pub static ref S_FLOAT: Word = Word::derive("float");
    pub static ref S_INTEGER: Word = Word::derive("integer");
    pub static ref S_ITEM: Word = Word::derive("item");
    pub static ref S_LIST: Word = Word::derive("list");
    pub static ref S_NUMBER: Word = Word::derive("number");
    pub static ref S_ORDERED: Word = Word::derive("ordered");
    pub static ref S_PIPE: Word = Word::derive("pipe");
    pub static ref S_PROGRAM: Word = Word::derive("program");
    pub static ref S_RECEPTACLE: Word = Word::derive("receptacle");
    pub static ref S_SIZED: Word = Word::derive("sized");
    pub static ref S_STRING: Word = Word::derive("string");
    pub static ref S_WORD: Word = Word::derive("word");
}

/// A kcats data value.
#[derive(Debug, Clone)]
pub enum Item {
    /// A number value
    Number(number::Number),
    /// A word value. Words are atomic, they can't be broken down into
    /// characters like Strings.
    Word(Word),
    /// A character value, like 'a', or '\n'.
    Char(Char),
    /// A container value (that [Item]s can be taken derive)
    Dispenser(coll::Dispenser),
    /// A container value (that [Item]s can be put into)
    Receptacle(coll::Receptacle),
}

impl Item {
    /// Returns whether the item is empty - only containers can be empty.
    pub fn is_empty(&self) -> bool {
        match self {
            Item::Dispenser(coll::Dispenser::Sized(s)) => s.is_empty(),
            Item::Receptacle(coll::Receptacle::Sized(s)) => s.is_empty(),
            _ => false,
        }
    }
}

/// A Future value, used for async execution, which is how
/// multithreading is implemented in kcats.
pub type Future<T> = Pin<Box<dyn std::future::Future<Output = T> + Send>>;

/// A type for a function that advances the execution of a kcats
/// program by one step.
pub type StepFn = dyn Fn(env::Environment) -> Future<env::Environment> + Sync + Send;

impl PartialEq for Item {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            // same types, just use their own eq
            (Item::Number(a), Item::Number(b)) => a == b,
            (Item::Word(a), Item::Word(b)) => a.data == b.data,
            (
                Item::Dispenser(coll::Dispenser::Sized(a)),
                Item::Receptacle(coll::Receptacle::Sized(b)),
            ) => a == b,
            (
                Item::Receptacle(coll::Receptacle::Sized(a)),
                Item::Dispenser(coll::Dispenser::Sized(b)),
            ) => a == b,
            (Item::Dispenser(a), Item::Dispenser(b)) => a == b,
            (Item::Receptacle(a), Item::Receptacle(b)) => a == b,

            (Item::Char(a), Item::Char(b)) => a == b,
            _ => false,
        }
    }
}

/// The default Item is empty list.
impl Default for Item {
    fn default() -> Self {
        coll::Dispenser::default().fit()
    }
}

impl TryDerive<Item> for String {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let s = coll::Sized::try_derive(i)?;
        match s {
            coll::Sized::String(i) => Ok(i),
            i => Err(Error::expected("string", i)),
        }
    }
}

/// Converts Item to Word but also considers a quoted word as a word,
/// eg \[foo\] -> foo.
impl TryDerive<Item> for Word {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        match i {
            Item::Word(i) => Ok(i),
            i => {
                let i2 = i.clone();
                let l = coll::List::try_derive(i);
                match l {
                    Ok(mut l) => {
                        if l.len() == 1 {
                            let lm = l.mutate();

                            let i = lm.pop_front().unwrap();
                            i.try_fit()
                        } else {
                            Err(Error::expected("word", l))
                        }
                    }
                    Err(_) => Err(Error::expected("word", i2)),
                }
            }
        }
    }
}

impl TryDerive<Item> for Bytes {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let s = coll::Sized::try_derive(i)?;
        match s {
            coll::Sized::Bytes(b) => Ok(b),
            b => Err(Error::expected("bytes", b)),
        }
    }
}

/// As there are no real booleans, we use the word 'yes' but literally
/// any value except empty containers is truthy. If we read a value
/// 'false', that's not actually a boolean, it's just the [Word]
/// false. The fact that the word 'yes' is used in the language but
/// 'no' is not, is a known tradeoff.
impl Derive<bool> for Item {
    fn derive(b: bool) -> Item {
        if b {
            "yes".fit()
        } else {
            Item::default()
        }
    }
}

impl From<std::io::Error> for Error {
    fn from(err: std::io::Error) -> Error {
        Error::create(list!("io"), &err.to_string(), Option::<Item>::None)
    }
}

impl Derive<&str> for Item {
    fn derive(i: &str) -> Self {
        Item::Word(Word::derive(i))
    }
}

impl Derive<String> for Item {
    fn derive(i: String) -> Self {
        Item::Dispenser(coll::Dispenser::Sized(coll::Sized::String(i)))
    }
}

impl Derive<Bytes> for Item {
    fn derive(b: Bytes) -> Self {
        Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Bytes(b)))
    }
}

impl Derive<Word> for Item {
    fn derive(w: Word) -> Self {
        Item::Word(w)
    }
}

impl Derive<Char> for Item {
    fn derive(c: Char) -> Self {
        Item::Char(c)
    }
}

impl<T> Derive<Option<T>> for Item
where
    Item: Derive<T>,
{
    fn derive(opt: Option<T>) -> Item {
        match opt {
            Some(t) => Item::derive(t),
            None => Item::default(),
        }
    }
}

/// A generic impl to convert an Item to a vec of the given
/// type. Assumes the Item is some sort of container and converts each
/// item in the container.
impl<T: TryDerive<Item, Error = Error>> TryDerive<Item> for Vec<T> {
    type Error = Error;

    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        // First try to convert the Item to an IntoIterator<Item>
        let it: Box<dyn Iterator<Item = Item>> = i.try_fit()?;
        it.map(T::try_derive).collect()
    }
}

/// A macro to build a kcats List, accepts any values that are
/// convertible to [Item].
#[macro_export]
macro_rules! list {
      ( $( $x:expr ),* $(,)? ) => {
          {
              use $crate::traits::*;
              use $crate::types::Item;
              let v: Vec<Item> = vec![
                  $( $x.fit(), )*
              ];
              $crate::types::container::List::derive(v)
          }
      };
  }

mod serde {
    //! Support for json serialization of kcats objects
    use super::Item;
    use crate::traits::*;
    use crate::types::container as coll;
    use crate::types::container::associative as assoc;
    use crate::types::number;
    use crate::types::Error;
    use serde::de::{self, Deserialize, Deserializer, Visitor};
    use serde::ser::{Serialize, Serializer};
    use std::collections::HashMap;
    use std::fmt;

    struct ItemVisitor;

    impl<'de> Visitor<'de> for ItemVisitor {
        type Value = Item;

        fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
            formatter.write_str("expected a specific representation for Item")
        }

        fn visit_i64<E>(self, value: i64) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(Item::Number(number::Number::Int(value)))
        }

        fn visit_u64<E>(self, value: u64) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(Item::Number(number::Number::Int(value as i64)))
        }

        fn visit_f64<E>(self, value: f64) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(Item::Number(number::Number::Float(value)))
        }

        fn visit_none<E>(self) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(Item::default())
        }

        fn visit_bool<E>(self, v: bool) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(Item::derive(v))
        }

        fn visit_str<E>(self, v: &str) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(Item::Dispenser(coll::Dispenser::Sized(
                coll::Sized::String(v.to_string()),
            )))
        }

        fn visit_byte_buf<E>(self, v: Vec<u8>) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Bytes(
                v,
            ))))
        }

        fn visit_map<A>(self, mut ma: A) -> Result<Self::Value, A::Error>
        where
            A: de::MapAccess<'de>,
        {
            let mut map = HashMap::new();
            while let Some((key, value)) = ma.next_entry::<assoc::KeyItem, Item>()? {
                map.insert(key, value);
            }
            Ok(Item::Dispenser(coll::Dispenser::Sized(
                coll::Sized::Associative(assoc::Associative::Assoc(map.fit())),
            )))
        }

        fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
        where
            A: de::SeqAccess<'de>,
        {
            let mut items = Vec::new();
            while let Some(item) = seq.next_element::<Item>()? {
                items.push(item);
            }
            Ok(coll::List::derive(items).fit())
        }
    }

    impl<'de> Deserialize<'de> for Item {
        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
        where
            D: Deserializer<'de>,
        {
            deserializer.deserialize_any(ItemVisitor)
        }
    }

    impl From<serde_json::Error> for Error {
        fn from(err: serde_json::Error) -> Error {
            Error::create(list!("serialize"), &err.to_string(), Option::<Item>::None)
        }
    }

    impl Serialize for Item {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: Serializer,
        {
            match self {
                Item::Number(num) => num.serialize(serializer),
                Item::Char(c) => serializer.serialize_char(*c),
                Item::Word(w) => serializer.serialize_str(w.fit()),

                // Handle other variants
                Item::Dispenser(ref dispenser) => dispenser.serialize(serializer),
                Item::Receptacle(ref receptacle) => receptacle.serialize(serializer),
            }
        }
    }
}

//! Support for numbers in kcats. Currently just [i64] and [f64], but
//! this module will eventually support bignums and autopromotion.
use super::container::error::Error;
use crate::traits::*;
use crate::types::Item;
use num_integer::Roots;
use serde::ser::{Serialize, Serializer};
/// An integer type
pub type Int = i64;

/// A floating point type
pub type Float = f64;

#[derive(Clone, Debug)]
pub enum Number {
    Int(Int),
    Float(Float),
}

impl Number {
    pub fn add(&self, other: Number) -> Number {
        match (self, other) {
            (Number::Int(i), Number::Int(j)) => Number::Int(i + j),
            (Number::Float(i), Number::Float(j)) => Number::Float(i + j),
            (Number::Int(i), Number::Float(j)) => Number::Float(*i as Float + j),
            (Number::Float(i), Number::Int(j)) => Number::Float(i + j as Float),
        }
    }

    pub fn subtract(&self, other: Number) -> Number {
        match (self, other) {
            (Number::Int(i), Number::Int(j)) => Number::Int(i - j),
            (Number::Float(i), Number::Float(j)) => Number::Float(i - j),
            (Number::Int(i), Number::Float(j)) => Number::Float(*i as Float - j),
            (Number::Float(i), Number::Int(j)) => Number::Float(i - j as Float),
        }
    }

    pub fn multiply(&self, other: Number) -> Number {
        match (self, other) {
            (Number::Int(i), Number::Int(j)) => Number::Int(i * j),
            (Number::Float(i), Number::Float(j)) => Number::Float(i * j),
            (Number::Int(i), Number::Float(j)) => Number::Float(*i as Float * j),
            (Number::Float(i), Number::Int(j)) => Number::Float(i * j as Float),
        }
    }

    pub fn divide(i: Float, j: Float) -> Result<Float, Error> {
        let q = i / j;
        if q.is_nan() {
            Err(Error::division_by_zero())
        } else {
            Ok(q)
        }
    }

    pub fn gt(i: Number, j: Number) -> bool {
        match (i, j) {
            (Number::Int(i), Number::Int(j)) => i > j,
            (Number::Float(i), Number::Float(j)) => i > j,
            (Number::Int(i), Number::Float(j)) => i as Float > j,
            (Number::Float(i), Number::Int(j)) => i > j as Float,
        }
    }

    pub fn lt(i: Number, j: Number) -> bool {
        match (i, j) {
            (Number::Int(i), Number::Int(j)) => i < j,
            (Number::Float(i), Number::Float(j)) => i < j,
            (Number::Int(i), Number::Float(j)) => (i as Float) < j,
            (Number::Float(i), Number::Int(j)) => i < j as Float,
        }
    }

    pub fn gte(i: Number, j: Number) -> bool {
        match (i, j) {
            (Number::Int(i), Number::Int(j)) => i >= j,
            (Number::Float(i), Number::Float(j)) => i >= j,
            (Number::Int(i), Number::Float(j)) => (i as Float) >= j,
            (Number::Float(i), Number::Int(j)) => i >= j as Float,
        }
    }

    pub fn lte(i: Number, j: Number) -> bool {
        match (i, j) {
            (Number::Int(i), Number::Int(j)) => i <= j,
            (Number::Float(i), Number::Float(j)) => i <= j,
            (Number::Int(i), Number::Float(j)) => (i as Float) <= j,
            (Number::Float(i), Number::Int(j)) => i <= j as Float,
        }
    }

    pub fn abs(&self) -> Number {
        match self {
            Number::Int(i) => Number::Int(i.abs()),
            Number::Float(f) => Number::Float(f.abs()),
        }
    }

    pub fn sqrt(&self) -> Number {
        match self {
            Number::Int(i) => Number::Int(i.sqrt()),
            Number::Float(f) => Number::Float(f.sqrt()),
        }
    }
}

impl PartialEq for Number {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Number::Int(a), Number::Int(b)) => a == b,
            (Number::Float(a), Number::Float(b)) => a == b,
            (Number::Float(a), Number::Int(b)) => *a == *b as Float,
            (Number::Int(a), Number::Float(b)) => *a as Float == *b,
        }
    }
}

impl TryDerive<Number> for Float {
    type Error = Error;
    fn try_derive(i: Number) -> Result<Self, Self::Error> {
        match i {
            Number::Float(i) => Ok(i),
            i => Err(Error::expected("float", i)),
        }
    }
}

impl TryDerive<Number> for Int {
    type Error = Error;
    fn try_derive(i: Number) -> Result<Self, Self::Error> {
        match i {
            Number::Int(i) => Ok(i),
            i => Err(Error::expected("integer", i)),
        }
    }
}

impl Derive<Int> for Item {
    fn derive(c: Int) -> Self {
        Item::Number(Number::Int(c))
    }
}

impl Derive<Float> for Item {
    fn derive(c: Float) -> Self {
        Item::Number(Number::Float(c))
    }
}

impl TryDerive<Item> for Number {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        match i {
            Item::Number(i) => Ok(i),
            i => Err(Error::expected("number", i)),
        }
    }
}

impl TryDerive<Item> for Int {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        match Number::try_derive(i)? {
            Number::Int(i) => Ok(i),
            i => Err(Error::expected("integer", i)),
        }
    }
}

impl TryDerive<Item> for Float {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        match Number::try_derive(i)? {
            Number::Float(i) => Ok(i),
            i => Err(Error::expected("float", i)),
        }
    }
}

impl Derive<Number> for Item {
    fn derive(c: Number) -> Self {
        Item::Number(c)
    }
}

impl Serialize for Number {
    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
    where
        S: Serializer,
    {
        match self {
            Number::Int(i) => serializer.serialize_i64(*i),
            Number::Float(f) => serializer.serialize_f64(*f),
        }
    }
}

//! Support for containers in kcats. Includes types like
//! [List], [Set],
//! [associative::Association], String,
//! [pipe::In],
//! [pipe::Out], and Byte arrays. The
//! container contract is you can put things into, or take things out
//! of them. [Receptacle]s are for putting into, and [Dispenser]s are
//! for taking out of. For underlying types that support both
//! operations (like [List]), we can easily convert between
//! [Receptacle] and [Dispenser] as needed.
pub mod associative;
pub mod dictionary;
pub mod environment;
pub mod error;
pub mod pipe;

use futures::FutureExt;

use self::associative as assoc;
use crate::traits::*;
use crate::types::number::{Int, Number};
use crate::types::*;

use std::{collections::HashSet, future, sync};
use sync::Arc;

/// A generic Arc type that we control
//pub type Arc<T> = Newtype<sync::Arc<T>>;

/// A generic List type
pub type Listy<I> = VecDeque<I>;

/// A generic Set type
pub type Setty<I> = HashSet<I>;

/// A specific List type
pub type ListContent = Listy<Item>;

pub type List = Arc<ListContent>;
pub type Set = Arc<Setty<assoc::KeyItem>>;

impl Derive<HashSet<assoc::KeyItem>> for Set {
    fn derive(h: HashSet<assoc::KeyItem>) -> Set {
        Arc::new(h)
    }
}

impl Derive<ListContent> for List {
    fn derive(l: ListContent) -> List {
        Arc::new(l)
    }
}

impl DeriveIterator<Item> for List {
    fn derive_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = Item>,
    {
        Arc::new(iter.into_iter().collect::<VecDeque<Item>>())
    }
}

impl DeriveIterator<assoc::KeyItem> for Set {
    fn derive_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = assoc::KeyItem>,
    {
        sync::Arc::new(iter.into_iter().collect::<HashSet<assoc::KeyItem>>())
    }
}

impl<T> Fresh for Arc<T>
where
    T: Default,
{
    fn fresh() -> Self {
        Arc::new(T::default())
    }
}

pub trait Ordered {
    /// Appends the items to the beginning of this list, preserving
    /// their order. eg `[1, 2, 3].append([4, 5, 6])` -> `[4, 5, 6, 1,
    /// 2, 3]`.
    fn prepend(&mut self, items: List);

    /// Appends the items in the iterator to the beginning of this
    /// list, preserving order.
    fn extend<T: IntoIterator<Item = Item>>(&mut self, items: T);

    /// Reverses the order of the list.
    fn reverse(&mut self);
}

pub trait Mutey<T> {
    fn mutate(&mut self) -> &mut T;
}

impl<T: Clone> Mutey<T> for Arc<T> {
    fn mutate(&mut self) -> &mut T {
        Arc::make_mut(self)
    }
}

impl Ordered for List {
    fn prepend(&mut self, mut items: List) {
        // Ensure both VecDeques are uniquely owned to avoid cloning during modifications
        let self_mut = self.mutate();
        let items_mut = items.mutate();

        // Prepend the elements of `items` to `self`
        while let Some(item) = items_mut.pop_back() {
            self_mut.push_front(item);
        }
    }

    fn extend<T: IntoIterator<Item = Item>>(&mut self, items: T) {
        let m = sync::Arc::make_mut(self);
        let ct = m.len();
        m.extend(items);
        m.rotate_left(ct);
    }

    fn reverse(&mut self) {
        let m = sync::Arc::make_mut(self);
        m.make_contiguous().reverse();
    }
}

/// A generic container type, all we know is it can contain multiple
/// items. Includes things like lists, sets, and IO channels. Items
/// can be taken out.
#[derive(Debug, Clone, PartialEq)]
pub enum Dispenser {
    /// A container with a known number of items inside
    Sized(Sized),
    /// A pipe that dispenses an unknown number of items
    Out(pipe::Out),
    /// Similar to Out but also convertible to [Receptacle]
    Tunnel(pipe::Tunnel),
}

/// A generic container type, all we know is it can contain multiple
/// items. Includes things like lists, sets, and IO channels. Items
/// can be put in.
#[derive(Debug, Clone, PartialEq)]
pub enum Receptacle {
    /// A container with a known number of items inside
    Sized(Sized),
    /// A pipe that can receive an arbitrary number of items
    In(pipe::In),
    /// Similar to In but also convertible to [Dispenser]
    Tunnel(pipe::Tunnel),
}

/// Collections that have a definite size that we can access. Implies
/// that it can also be appended to.
#[derive(Debug, Clone)]
pub enum Sized {
    /// Associative containers associate Items in pairs, like Map or
    /// Dict in other languages.
    Associative(assoc::Associative),
    /// List containers have multiple Items in a specific order.
    List(List),
    /// Set containers have multiple Items in no particular order, and
    /// each Item can only appear once.
    Set(Set),
    //TODO: these should be inside an Arc too
    /// A String is a chunk of text, like a list of individual
    /// characters.
    String(String),
    /// Bytes is the lowest common denominator form of data, useful
    /// for when no other type applies.
    Bytes(Bytes),
}

impl PartialEq for Sized {
    fn eq(&self, other: &Self) -> bool {
        if self.is_empty() && other.is_empty() {
            return true;
        }
        match (self, other) {
            (Sized::Associative(a), Sized::Associative(b)) => a == b,
            (Sized::List(a), Sized::List(b)) => a == b,
            (Sized::String(a), Sized::String(b)) => a == b,
            (Sized::Bytes(a), Sized::Bytes(b)) => a == b,
            (Sized::Set(a), Sized::Set(b)) => a == b,
            _ => false,
        }
    }
}

impl Dispenser {
    /// Takes an item out of the [Dispenser], and returns a future
    /// that gives a new [Dispenser], and the [Item] that was removed
    /// (if there was one).
    pub fn take(self) -> Future<(Dispenser, Option<Item>)> {
        match self {
            Dispenser::Sized(s) => {
                let (s, item) = s.take();

                Box::pin(future::ready((Dispenser::Sized(s), item)))
            }
            Dispenser::Out(mut o) => Box::pin({
                let i = o.take();
                i.map(|r| {
                    (
                        Dispenser::Out(o),
                        match r {
                            Ok(Some(i)) => Some(i),
                            Ok(None) => None,
                            Err(e) => Some(Item::derive(e)),
                        },
                    )
                })
            }),
            Dispenser::Tunnel(mut t) => Box::pin({
                let i = t.take();
                i.map(|r| {
                    (
                        Dispenser::Tunnel(t),
                        match r {
                            Ok(Some(i)) => Some(i),
                            Ok(None) => None,
                            Err(e) => Some(Item::derive(e)),
                        },
                    )
                })
            }),
        }
    }
}

impl Sized {
    /// Returns whether the collection is empty
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Returns the number of items in the collection.
    pub fn len(&self) -> usize {
        match self {
            Sized::Associative(a) => a.len(),
            Sized::List(l) => l.len(),
            Sized::String(s) => s.len(),
            Sized::Bytes(b) => b.len(),
            Sized::Set(s) => s.len(),
        }
    }

    /// Takes an item out of the collection, returning the item and
    /// the rest of the collection separately. Items are taken from
    /// the front (beginning) of the collection.
    pub fn take(self) -> (Self, Option<Item>) {
        match self {
            Sized::Associative(a) => {
                let (a, i) = a.take();
                (Sized::Associative(a), i)
            }
            Sized::List(mut l) => {
                let lm = l.mutate();
                let i = lm.pop_front();
                (Sized::List(l), i)
            }
            Sized::String(mut s) => {
                // TODO: this may perform badly
                let first_char = s.chars().next();
                s.drain(..first_char.map(|s| s.len_utf8()).unwrap_or(0));
                let i = first_char.map(Item::Char);
                (Sized::String(s), i)
            }
            Sized::Bytes(mut b) => {
                if b.is_empty() {
                    (Sized::Bytes(b), None)
                } else {
                    let i = Some(Item::Number(Number::Int(b[0] as Int)));
                    b.drain(..1);
                    (Sized::Bytes(b), i)
                }
            }
            Sized::Set(mut s) => {
                let i = s.iter().next().cloned();
                let sm = s.mutate();
                if let Some(i) = i.clone() {
                    sm.take(&i);
                }
                (Sized::Set(s), i.map(Item::derive))
            }
        }
    }

    /// Takes an item from the back (end) of the collection.
    pub fn pop(self) -> (Self, Option<Item>) {
        match self {
            Sized::Associative(a) => {
                let (a, i) = a.take();
                (Sized::Associative(a), i)
            }
            Sized::List(mut l) => {
                let lm = l.mutate();
                let i = lm.pop_back();
                (Sized::List(l), i)
            }
            Sized::String(mut s) => s
                .pop()
                .map(|c| (Sized::String(s), Some(c.fit())))
                .unwrap_or((Sized::String(String::new()), None)),
            Sized::Bytes(mut b) => b
                .pop()
                .map(|c| (Sized::Bytes(b), Some((c as Int).fit())))
                .unwrap_or((Sized::Bytes(vec![]), None)),
            Sized::Set(mut s) => {
                let i = s.iter().next().cloned();
                let sm = s.mutate();
                if let Some(i) = i.clone() {
                    sm.take(&i);
                }
                (Sized::Set(s), i.map(Item::derive))
            }
        }
    }

    /// Puts an item into the collection, at the end.
    pub fn put(self, other: Item) -> Result<Sized, Error> {
        match (self, other) {
            (Sized::List(mut c), i) => {
                c.mutate().push_back(i);
                Ok(Sized::List(c))
            }
            (Sized::Associative(a), l) => Ok(Sized::Associative(a.put(l)?)),
            (Sized::Set(mut s), i) => {
                s.mutate().insert(assoc::KeyItem::try_derive(i)?);
                Ok(Sized::Set(s))
            }
            (Sized::Bytes(mut b), Item::Number(Number::Int(i))) => {
                b.push(i as u8);
                Ok(Sized::Bytes(b))
            }
            (Sized::Bytes(_), i) => Err(Error::expected("integer", i)),
            (Sized::String(mut s), Item::Char(c)) => Ok(Sized::String({
                s.push(c);
                s
            })),
            (Sized::String(_), i) => Err(Error::expected("char", i)),
        }
    }

    /// Joins two collections into one. If the collections are
    /// different types, generally the result is the type of the first
    /// argument.
    pub fn join(self, other: Sized) -> Result<Sized, Error> {
        Ok(match (self, other) {
            (Sized::Associative(a), Sized::List(l)) => {
                let la = assoc::Associative::Assoc(assoc::Association::try_from_iter(
                    l.iter().cloned(),
                )?);
                Sized::Associative(a.join(la))
            }
            (Sized::List(l), Sized::Associative(a)) => {
                let la = assoc::Associative::Assoc(assoc::Association::try_from_iter(
                    l.iter().cloned(),
                )?);
                Sized::Associative(la.join(a))
            }
            (Sized::Associative(a), Sized::Associative(b)) => Sized::Associative(a.join(b)),
            (Sized::List(mut a), Sized::List(b)) => {
                let am = a.mutate();
                am.extend(b.iter().cloned());
                Sized::List(a)
            }
            (Sized::Set(mut a), Sized::Set(b)) => {
                let am = a.mutate();
                am.extend(b.iter().cloned());
                Sized::Set(a)
            }
            (Sized::List(a), Sized::Set(mut b)) => {
                let bm = b.mutate();

                bm.extend(
                    a.iter()
                        .cloned()
                        .map(assoc::KeyItem::try_derive)
                        .collect::<Result<Vec<assoc::KeyItem>, Error>>()?,
                );
                Sized::Set(b)
            }
            (Sized::Set(mut a), Sized::List(b)) => {
                let am = a.mutate();

                am.extend(
                    b.iter()
                        .cloned()
                        .map(assoc::KeyItem::try_derive)
                        .collect::<Result<Vec<assoc::KeyItem>, Error>>()?,
                );
                Sized::Set(a)
            }
            (Sized::String(mut a), Sized::String(b)) => {
                a.push_str(&b);
                Sized::String(a)
            }
            (Sized::Bytes(mut a), Sized::Bytes(b)) => {
                a.extend(b);
                Sized::Bytes(a)
            }
            (s, other) => {
                if s.is_empty() {
                    other
                } else if other.is_empty() {
                    s
                } else {
                    Err(Error::expected("joinable", list!(s, other)))?
                }
            }
        })
    }

    /// Returns whether this collection contains the given [Item].
    pub fn contains(&self, other: &Item) -> bool {
        match (self, other) {
            (Sized::Associative(a), other) => {
                assoc::KeyItem::try_derive(other.clone()).map_or(false, |k| a.contains_key(&k))
            }
            (Sized::List(l), other) => l.contains(other),
            (Sized::Set(s), Item::Dispenser(Dispenser::Sized(Sized::Set(other)))) => {
                other.is_subset(s)
            }
            (Sized::Set(s), Item::Receptacle(Receptacle::Sized(Sized::Set(other)))) => {
                other.is_subset(s)
            }
            (Sized::Set(s), other) => {
                assoc::KeyItem::try_derive(other.clone()).map_or(false, |k| s.contains(&k))
            }
            (Sized::String(container), other) => match other {
                Item::Char(c) => container.contains(*c),
                i => {
                    let s = String::try_derive(i.clone());
                    match s {
                        Ok(s) => container.contains(&s),
                        Err(_) => false,
                    }
                }
            },
            _ => false,
        }
    }

    /// Returns a new empty version of this collection. Does not
    /// modify this collection. The new collection will be the same
    /// type as this one (if this is a [Sized::String], you'll get an empty
    /// [Sized::String], etc)
    pub fn empty(&self) -> Sized {
        match self {
            Sized::Associative(_) => {
                Sized::Associative(assoc::Associative::Assoc(assoc::Association::fresh()))
            }
            Sized::List(_) => Sized::List(List::default()),
            Sized::Set(_) => Sized::Set(Set::default()),
            Sized::String(_) => Sized::String(String::new()),
            Sized::Bytes(_) => Sized::Bytes(vec![]),
        }
    }
}

impl Receptacle {
    /// Puts the given [Item] into this collection, items are added at
    /// the end.
    pub fn put(self, i: Item) -> Future<Result<Receptacle, Error>> {
        match self {
            Receptacle::Sized(s) => Box::pin(future::ready(s.put(i).map(Receptacle::Sized))),
            Receptacle::In(mut p) => Box::pin(p.put(i).map(|r| r.map(|_| Receptacle::In(p)))),
            Receptacle::Tunnel(mut t) => {
                let p = t.put(i);
                Box::pin(p.map(|r| r.map(|_| Receptacle::Tunnel(t))))
            }
        }
    }
}

impl IntoIterator for Sized {
    type Item = Item;
    type IntoIter = Box<dyn Iterator<Item = Item>>;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Sized::Associative(map) => Box::new(map.to_iter().map(|kv| kv.fit())),
            Sized::List(list) => {
                let items: Vec<_> = list.iter().cloned().collect();
                Box::new(items.into_iter())
            }
            Sized::String(s) => {
                let chars: Vec<char> = s.chars().collect();
                Box::new(chars.into_iter().map(|c| c.fit()))
            }
            Sized::Bytes(b) => {
                let vec: Vec<Item> = b
                    .into_iter()
                    .map(|byte| Item::derive(byte as Int))
                    .collect();
                Box::new(vec.into_iter())
            }
            Sized::Set(s) => {
                let items: Vec<_> = s.iter().cloned().map(|i| i.fit()).collect();
                Box::new(items.into_iter())
            }
        }
    }
}

impl TryDerive<Dispenser> for Sized {
    type Error = Error;

    fn try_derive(c: Dispenser) -> Result<Self, Self::Error> {
        //println!("from iterable {:?}", c);
        match c {
            Dispenser::Sized(s) => Ok(s),
            i => Err(Error::expected("sized", i)),
        }
    }
}

impl TryDerive<Receptacle> for Sized {
    type Error = Error;

    fn try_derive(c: Receptacle) -> Result<Self, Self::Error> {
        match c {
            Receptacle::Sized(s) => Ok(s),
            i => Err(Error::expected("sized", Item::Receptacle(i))),
        }
    }
}

impl TryDerive<Sized> for List {
    type Error = Error;

    fn try_derive(s: Sized) -> Result<Self, Self::Error> {
        match s {
            Sized::List(l) => Ok(l),
            Sized::Associative(a) => Ok(List::derive_iter(a.to_iter().map(Item::derive))),
            i => Err(Error::expected("list", i)),
        }
    }
}
// Implement Derive for Item where T is an Iterator
impl<T, I> Derive<T> for Item
where
    T: ToIterator<Item = I> + IntoList,
    I: Fit<Item>,
{
    fn derive(iter: T) -> Self {
        let l: List = iter.to_iter().map(|t| t.fit()).my_collect();
        Item::derive(l)
    }
}

impl TryDerive<List> for Vec<dict::Namespace> {
    type Error = Error;

    fn try_derive(l: List) -> Result<Self, Self::Error> {
        l.iter().cloned().map(dict::Namespace::try_derive).collect()
    }
}

impl Derive<Vec<Item>> for List {
    fn derive(v: Vec<Item>) -> Self {
        List::derive_iter(v)
    }
}

impl TryDerive<Item> for List {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        match i {
            Item::Dispenser(l) => Sized::try_derive(l).and_then(List::try_derive),
            Item::Receptacle(l) => Sized::try_derive(l).and_then(List::try_derive),
            i => Err(Error::expected("list", i)),
        }
    }
}

impl TryDerive<Item> for Sized {
    type Error = Error;

    fn try_derive(item: Item) -> Result<Self, Self::Error> {
        match item {
            Item::Dispenser(c) => c.try_fit(),
            Item::Receptacle(p) => Dispenser::try_derive(p)?.try_fit(),
            i => {
                // let bt = backtrace::Backtrace::new();
                // println!("try from item {:?},\n {:?}", i, bt);
                Err(Error::expected("sized", i))
            }
        }
    }
}

impl TryDerive<Item> for Receptacle {
    type Error = Error;

    fn try_derive(item: Item) -> Result<Self, Self::Error> {
        match item {
            Item::Receptacle(p) => Ok(p),
            Item::Dispenser(c) => c.try_fit(),
            i => Err(Error::expected("packable", i)),
        }
    }
}

impl TryDerive<Dispenser> for Receptacle {
    type Error = Error;

    fn try_derive(c: Dispenser) -> Result<Self, Self::Error> {
        match c {
            Dispenser::Sized(s) => Ok(Receptacle::Sized(s)),
            Dispenser::Tunnel(t) => Ok(Receptacle::Tunnel(t)),
            i => Err(Error::expected("packable", i)),
        }
    }
}

impl TryDerive<Receptacle> for Dispenser {
    type Error = Error;

    fn try_derive(c: Receptacle) -> Result<Self, Self::Error> {
        match c {
            Receptacle::Sized(s) => Ok(Dispenser::Sized(s)),
            Receptacle::Tunnel(t) => Ok(Dispenser::Tunnel(t)),
            i => Err(Error::expected("iterable", Item::Receptacle(i))),
        }
    }
}

impl TryDerive<Item> for Box<dyn Iterator<Item = Item>> {
    type Error = Error;

    fn try_derive(item: Item) -> Result<Self, Self::Error> {
        Ok(Sized::try_derive(item)?.into_iter())
    }
}

impl Derive<Sized> for Box<dyn Iterator<Item = Item>> {
    fn derive(sized: Sized) -> Self {
        Box::new(sized.into_iter())
    }
}

impl Derive<List> for Sized {
    fn derive(l: List) -> Self {
        Sized::List(l)
    }
}

impl Derive<String> for Sized {
    fn derive(s: String) -> Self {
        Sized::String(s)
    }
}

impl Derive<Bytes> for Sized {
    fn derive(b: Bytes) -> Self {
        Sized::Bytes(b)
    }
}

impl Derive<Sized> for Dispenser {
    fn derive(s: Sized) -> Self {
        Dispenser::Sized(s)
    }
}

impl Derive<List> for Item {
    fn derive(l: List) -> Self {
        Item::Dispenser(Dispenser::Sized(Sized::List(l)))
    }
}

impl Derive<Set> for Item {
    fn derive(l: Set) -> Self {
        Item::Dispenser(Dispenser::Sized(Sized::Set(l)))
    }
}

impl Derive<Dispenser> for Item {
    fn derive(c: Dispenser) -> Self {
        Item::Dispenser(c)
    }
}

impl Derive<Sized> for Item {
    fn derive(s: Sized) -> Self {
        Dispenser::Sized(s).fit()
    }
}

impl TryDerive<Item> for Dispenser {
    type Error = Error;

    fn try_derive(item: Item) -> Result<Self, Self::Error> {
        match item {
            Item::Dispenser(c) => Ok(c),
            Item::Receptacle(p) => Ok(Dispenser::try_derive(p)?),
            i => Err(Error::expected("iterable", i)),
        }
    }
}

impl TryDerive<Item> for Set {
    type Error = Error;

    fn try_derive(item: Item) -> Result<Self, Self::Error> {
        let s = Sized::try_derive(item)?;
        let hs: HashSet<assoc::KeyItem> = s
            .into_iter()
            .map(|i| i.try_fit())
            .collect::<Result<HashSet<assoc::KeyItem>, Error>>()?;
        Ok(Set::derive(hs))
    }
}

impl Default for Sized {
    fn default() -> Self {
        Sized::List(List::default())
    }
}

impl Default for Dispenser {
    fn default() -> Self {
        Dispenser::Sized(Sized::default())
    }
}

impl Default for Receptacle {
    fn default() -> Self {
        Receptacle::Sized(Sized::default())
    }
}

mod serde {
    use super::{Dispenser, Receptacle, Sized};
    use crate::serialize::Display;
    use crate::traits::*;
    use crate::types::container::associative as assoc;
    use serde::ser::{Serialize, SerializeMap, SerializeSeq};

    impl Serialize for Dispenser {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: serde::Serializer,
        {
            match self {
                Dispenser::Out(o) => o.representation().serialize(serializer),
                Dispenser::Tunnel(t) => t.representation().serialize(serializer),
                Dispenser::Sized(s) => s.serialize(serializer),
            }
        }
    }

    impl Serialize for Receptacle {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: serde::Serializer,
        {
            match self {
                Receptacle::In(i) => i.representation().serialize(serializer),
                Receptacle::Tunnel(t) => t.representation().serialize(serializer),
                Receptacle::Sized(s) => s.serialize(serializer),
            }
        }
    }

    impl Serialize for Sized {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: serde::Serializer,
        {
            match self {
                Sized::Associative(a) => {
                    // Start serializing a map
                    let assoc = assoc::Association::derive(a.clone());
                    let mut map = serializer.serialize_map(Some(assoc.len()))?;
                    for (key, value) in assoc.iter() {
                        // Serialize each entry in the map
                        map.serialize_entry(&key, &value)?;
                    }
                    // Finish serializing the map
                    map.end()
                }

                Sized::List(ref l) => {
                    // Serialize a list (sequence)
                    let mut seq = serializer.serialize_seq(Some(l.len()))?;
                    for element in l.iter() {
                        seq.serialize_element(&element)?;
                    }
                    seq.end()
                }
                Sized::Bytes(b) => serializer.serialize_bytes(b.as_slice()),
                Sized::Set(s) => {
                    // Serialize a list (sequence)
                    let mut seq = serializer.serialize_seq(Some(s.len()))?;
                    for element in s.iter() {
                        seq.serialize_element(&element)?;
                    }
                    seq.end()
                }
                Sized::String(s) => serializer.serialize_str(s.as_str()),
            }
        }
    }
}

//! Support for Associative data types (similar contract to Rust's
//! HashMap). Includes specific runtime data types like Errors,
//! Dictionaries, Environments, as well as generic maps (which are
//! called "associations" in kcats)
use super::{dictionary as dict, environment as env};
use crate::traits::*;
use crate::types::container as coll;
use crate::types::container::Mutey;
use crate::types::number::{Int, Number};
use crate::types::*;
use std::sync;

pub type Associationy<K, V> = HashMap<K, V>;
pub type AssociationContent = Associationy<KeyItem, Item>;
pub type Association = coll::Arc<AssociationContent>;

/// A KeyItem is all the Item types that can be used as a key in an
/// Associative structure. In order to be a key, the type has to be
/// hashable and have an ordering, so types like floating point
/// numbers or sets can't be used.
#[derive(Debug, Clone, Eq, PartialEq, Hash, PartialOrd, Ord)]
pub enum KeyItem {
    // Order matters here, for comparison purposes - changing the
    // order will change the result of how eg int compares to word.
    Int(Int),
    Char(Char),
    Word(Word),
    Bytes(Bytes),
    String(String),
    List(KeyList),
}

/// An Entry is a single pairing in an Associative type
pub type Entry = (KeyItem, Item);

pub type KeyListContent = coll::Listy<KeyItem>;
pub type KeyList = coll::Arc<KeyListContent>;

impl TryDeriveIterator<Item> for KeyList {
    fn try_from_iter<I>(l: I) -> Result<Self, Error>
    where
        I: IntoIterator<Item = Item>,
    {
        Ok(sync::Arc::new(
            l.into_iter()
                .map(KeyItem::try_derive)
                .collect::<Result<VecDeque<KeyItem>, Error>>()?,
        ))
    }
}

/// An Associative is a container type that associates one Item (the
/// key) with another (the value). It has the property where you can
/// look up a value using the key, and you can update the value that a
/// key points to. Some Item types cannot be used as keys, only
/// [KeyItem] is accepted as an Associative key.
#[derive(Debug, Clone)]
pub enum Associative {
    /// A generic associative structure where you can associate any
    /// [KeyItem] with any [Item].
    Assoc(Association),
    /// Represents an [dict::Dictionary] entry structure with
    /// specific keys.
    DictEntry(dict::Entry),
    /// Represents an execution environment, with specific keys
    Env(env::Environment),
    /// Represents a runtime Error value, with specific keys
    Error(Error),
    /// Represents a dictionary for an execution environment, with
    /// more specific key and value types.
    Dictionary(dict::Dictionary),
    Nothing,
}

impl Derive<KeyItem> for Item {
    fn derive(i: KeyItem) -> Self {
        match i {
            KeyItem::Int(i) => Item::Number(Number::Int(i)),
            KeyItem::String(i) => i.fit(),
            KeyItem::List(l) => coll::List::derive_iter(l.iter().cloned().map(Item::derive)).fit(),
            KeyItem::Word(w) => Item::Word(w),
            KeyItem::Bytes(bs) => bs.fit(),
            KeyItem::Char(c) => Item::Char(c),
        }
    }
}

impl Derive<&str> for KeyItem {
    fn derive(i: &str) -> Self {
        KeyItem::Word(Word::derive(i))
    }
}

impl Derive<Word> for KeyItem {
    fn derive(i: Word) -> Self {
        KeyItem::Word(i)
    }
}

impl TryDerive<Item> for KeyItem {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Error> {
        match i {
            Item::Number(Number::Int(i)) => Ok(KeyItem::Int(i)),
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::String(i))) => {
                Ok(KeyItem::String(i))
            }
            Item::Receptacle(coll::Receptacle::Sized(coll::Sized::String(i))) => {
                Ok(KeyItem::String(i))
            }
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Bytes(i))) => Ok(KeyItem::Bytes(i)),
            Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Bytes(i))) => {
                Ok(KeyItem::Bytes(i))
            }
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::List(l))) => {
                Ok(KeyItem::List(KeyList::try_from_iter(l.iter().cloned())?))
            }
            Item::Word(w) => Ok(KeyItem::Word(w)),
            Item::Char(c) => Ok(KeyItem::Char(c)),

            i => Err(Error::expected("KeyItem", i)),
        }
    }
}

impl TryDerive<KeyItem> for Word {
    type Error = Error;
    fn try_derive(k: KeyItem) -> Result<Self, Self::Error> {
        match k {
            KeyItem::Word(w) => Ok(w),
            i => Err(Error::expected("word", i)),
        }
    }
}

impl PartialEq for Associative {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Associative::Assoc(a), Associative::Assoc(b)) => a == b,
            (Associative::DictEntry(a), Associative::DictEntry(b)) => a == b,
            (Associative::Env(a), Associative::Env(b)) => a == b,
            (Associative::Error(a), Associative::Error(b)) => a == b,
            (Associative::Dictionary(a), Associative::Dictionary(b)) => a == b,
            (Associative::Nothing, Associative::Nothing) => true,
            //(Associative::Assoc(a), b) => Association::derive(a) == Association::derive(b),
            //(a, Associative::Assoc(b)) => Association::derive(a) == Association::derive(b),
            _ => false,
        }
    }
}

impl Associative {
    /// Retuns the number of associations in the container
    pub fn len(&self) -> usize {
        match self {
            Associative::Assoc(a) => a.len(),
            Associative::DictEntry(a) => a.len(),
            Associative::Env(e) => e.len(),
            Associative::Error(e) => e.len(),
            Associative::Dictionary(d) => d.len(),
            Associative::Nothing => 0,
        }
    }

    /// Returns true if the container is empty
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// Inserts a new association of a [KeyItem] to [Item]. If the key
    /// already exists, the value is replaced and the old value is
    /// returned. If the key doesn't exist, a new one is created with
    /// the new value and no old value is returned. The overall return
    /// value is tuple of an updated Associative, and an optional old
    /// value.
    ///
    /// The Associative returned is not necessarily the same type as
    /// self, as sometimes there is auto-demotion, eg from Error to
    /// Association. Demotion typically happens when you insert a key
    /// into a type that doesn't support that key, you'll get a more
    /// generic type back instead.
    pub fn insert(self, k: KeyItem, v: Item) -> (Associative, Option<Item>) {
        match self {
            Associative::Assoc(mut a) => {
                let am = coll::Arc::mutate(&mut a);
                let e = am.insert(k, v);
                (Associative::Assoc(a), e)
            }
            Associative::Dictionary(mut d) => match (k, v) {
                (KeyItem::Word(w), e) => {
                    let e2 = e.clone();
                    if let Ok(e) = dict::Entry::try_derive(e) {
                        let dm = coll::Arc::mutate(&mut d);
                        let e = dm.insert(w, e).map(Item::derive);
                        (Associative::Dictionary(d), e)
                    } else {
                        // TODO silently failing to insert here is bad
                        println!("Warning, failed to insert into dictionary: {:?}", e2);
                        (Associative::Dictionary(d), None)
                    }
                }
                _ => (Associative::Dictionary(d), None),
            },
            Associative::Env(e) => e.insert(k, v),
            Associative::DictEntry(mut de) => match k {
                KeyItem::Word(ref w) => {
                    let w: &str = w.fit();
                    if w == "definition" {
                        let l = coll::List::try_derive(v);
                        match l {
                            Ok(l) => {
                                de.definition = dict::Definition::Derived(l);
                                (Associative::DictEntry(de), None) // TODO: return the old def
                            }
                            Err(_) => (Associative::DictEntry(de), None),
                        }
                    } else if w == "examples" {
                        let l = coll::List::try_derive(v);
                        match l {
                            Ok(l) => {
                                de.examples = Some(l);
                                (Associative::DictEntry(de), None) // TODO: return the old examples
                            }
                            Err(_) => (Associative::DictEntry(de), None),
                        }
                    } else if w == "spec" {
                        let l = coll::List::try_derive(v);
                        match l {
                            Ok(l) => {
                                de.spec = l.try_fit().ok();
                                (Associative::DictEntry(de), None) // TODO: return the old spec
                            }
                            Err(_) => (Associative::DictEntry(de), None),
                        }
                    } else {
                        (Associative::DictEntry(de), None)
                    }
                }
                _ => (Associative::DictEntry(de), None),
            },
            _ => todo!("insert Implementations for error, env etc"),
        }
    }

    /// The put operation is for generic containers, adding a new Item
    /// to the container. In the case of Associative, we can still do
    /// this if the Item is the right type: a key/value pair. If it's
    /// the right type, we [Self::insert] the value using the key,
    /// otherwise return an error.
    pub fn put(self, other: Item) -> Result<Associative, Error> {
        match (self, other) {
            (Associative::Dictionary(mut this), other) => {
                let (word, entry) = <(Word, dict::Entry)>::try_derive(other)?;
                let thismut = this.mutate();
                thismut.insert(word.fit(), entry.fit());
                Ok(Associative::Dictionary(this))
            }
            (this, other) => {
                let entry: (KeyItem, Item) = other.try_fit()?;
                Ok(this.insert(entry.0, entry.1).0)
            }
        }
    }

    /// The join operation is for generic containers, but we can join
    /// two Associatives by merging them together. If both
    /// Associatives are the same specific type, the type is
    /// preserved. If `other` can be converted to the same specific
    /// type as `self`, that conversion will be done and the specific
    /// type of `self` is preserved. If they are different types and we
    /// can't convert `other` to `self`s type, the result will be
    /// demoted to a more generic form.
    ///
    /// Keys in `other` have priority over those in `self` - if a key
    /// is in both containers, the result will have only the value
    /// from `other`.
    pub fn join(self, other: Associative) -> Associative {
        match (self, other) {
            // same type means 2nd one wins.
            //TODO: a little more complex for types that can be extended
            (Associative::DictEntry(_), Associative::DictEntry(other)) => {
                Associative::DictEntry(other)
            }
            (Associative::Dictionary(mut this), Associative::Dictionary(other)) => {
                let thism = coll::Arc::mutate(&mut this);
                thism.extend(
                    other
                        .iter()
                        .map(|(key, value)| (key.clone(), value.clone())),
                );
                Associative::Dictionary(this)
            }
            (Associative::Dictionary(mut this), Associative::Assoc(other)) => {
                // Try to convert to dictionary type
                //println!("dict + assoc join");
                match other.convert::<Word, dict::Entry>() {
                    Ok(d) => {
                        let tm = this.mutate();
                        tm.extend(d);
                        Associative::Dictionary(this)
                    }
                    // TODO: convert the other way (to assoc) instead
                    Err(e) => {
                        println!("Conversion error: {:?}", e);
                        Associative::Dictionary(this)
                    }
                }
            }
            (Associative::Assoc(this), Associative::Dictionary(mut dict)) => {
                // Try to convert to dictionary type
                //println!("assoc + dict join");
                match this.convert::<Word, dict::Entry>() {
                    Ok(d) => {
                        let tm = dict.mutate();
                        tm.extend(d);
                        Associative::Dictionary(dict)
                    }
                    // TODO: convert the other way (to assoc) instead
                    Err(_) => Associative::Dictionary(dict),
                }
            }
            (Associative::Error(_), Associative::Error(other)) => Associative::Error(other),
            (Associative::Env(_), Associative::Env(other)) => Associative::Env(other),
            (Associative::Nothing, Associative::Nothing) => Associative::Nothing,
            (Associative::Assoc(mut this), other) => {
                let thism = this.mutate();
                thism.extend(other.to_iter());
                Associative::Assoc(this)
            }
            (this, other) => {
                let thisa: Association = this.fit();
                (Associative::Assoc(thisa)).join(other)
            }
        }
    }

    /// Retrieves a value from the container using the key
    /// `k`. Returns [None] if the key is not present.
    pub fn get(&self, k: &KeyItem) -> Option<Item> {
        match self {
            Associative::Assoc(a) => a.get(k).cloned(),
            Associative::Error(e) => e.data.get(k).cloned(),
            Associative::Env(e) => match k {
                KeyItem::Word(s) => e.get(s.fit()),
                _ => None,
            },
            Associative::DictEntry(d) => match k {
                KeyItem::Word(s) => d.get(s.fit()),
                _ => None,
            },
            Associative::Dictionary(d) => match k {
                KeyItem::Word(w) => d.get(w).map(|x| x.clone().fit()),
                _ => None,
            },
            &Associative::Nothing => None,
        }
    }

    /// Returns true if the key `k` is present in the container.
    pub fn contains_key(&self, k: &KeyItem) -> bool {
        match self {
            Associative::Assoc(a) => a.contains_key(k),
            Associative::Error(e) => e.data.contains_key(k),
            Associative::Env(e) => e.contains_key(k),
            Associative::DictEntry(d) => d.contains_key(k),
            Associative::Dictionary(d) => match k {
                KeyItem::Word(w) => d.contains_key(w),
                _ => false,
            },
            &Associative::Nothing => false,
        }
    }

    /// Removes the key `k` from the container, returning a tuple of a
    /// new [Associative] and an optional value if the key was
    /// present.
    pub fn remove(self, k: &KeyItem) -> (Associative, Option<Item>) {
        match self {
            Associative::Assoc(mut a) => {
                let am = coll::Arc::mutate(&mut a);
                let v = am.remove(k);
                (Associative::Assoc(a), v)
            }
            Associative::Dictionary(mut d) => {
                let dm = coll::Arc::mutate(&mut d);
                let v = dm.remove(&Word::try_derive(k.clone()).unwrap_or_default());
                (Associative::Dictionary(d), v.map(|v| v.fit()))
            }
            Associative::Error(mut e) => {
                let a = e.data.mutate();
                let v = a.remove(k);
                (Associative::Error(e), v)
            }
            Associative::Env(e) => {
                let a = Association::derive_iter(e);
                Associative::Assoc(a).remove(k)
            }
            _ => todo!("Removing from other associative types"),
        }
    }

    /// The take operation is for generic containers but we can
    /// perform it on an Associative by removing an arbitrary pair and
    /// returning it.
    pub fn take(self) -> (Self, Option<Item>) {
        match self {
            Associative::Assoc(mut a) => {
                let maybe_key = a.keys().next().cloned();
                let am = a.mutate();
                let maybe_value = maybe_key.as_ref().and_then(|key| am.remove(key));
                (
                    Associative::Assoc(a),
                    maybe_key.map(|key| {
                        coll::List::derive_iter(vec![
                            Item::derive(key),
                            maybe_value.unwrap_or_default(),
                        ])
                        .fit()
                    }),
                )
            }
            Associative::Dictionary(mut d) => {
                let maybe_key = d.keys().next().cloned();
                let dm = d.mutate();
                let maybe_value = maybe_key.clone().and_then(|key| dm.remove(&key));
                (
                    Associative::Dictionary(d),
                    maybe_key.map(|key| {
                        coll::List::derive_iter(vec![
                            Item::Word(key),
                            maybe_value.map(Item::derive).unwrap_or(Item::default()),
                        ])
                        .fit()
                    }),
                )
            }
            // The remaining impls may require auto-demotion (eg,
            // removing a required field from say, Error)
            _ => todo!("taking from assoc Requires insert/remove impl"),
        }
    }
}

impl ToIterator for Associative {
    type Item = Entry;
    type IntoIter = Box<dyn Iterator<Item = Entry>>;

    fn to_iter<'a>(self) -> Self::IntoIter {
        match self {
            Associative::Assoc(a) => {
                let items: Vec<_> = a.iter().map(|(k, v)| (k.clone(), v.clone())).collect();
                Box::new(items.into_iter())
            }
            Associative::DictEntry(e) => Box::new(e.into_iter()),
            Associative::Dictionary(d) => {
                let items: Vec<_> = d
                    .iter()
                    .map(|(k, v)| (k.clone().fit(), v.clone().fit()))
                    .collect();
                Box::new(items.into_iter())
            }
            Associative::Error(e) => e.into_iter(),
            Associative::Env(e) => e.into_iter(),
            Associative::Nothing => Box::new(std::iter::empty()),
        }
    }
}

impl Derive<Associative> for coll::List {
    fn derive(a: Associative) -> Self {
        coll::List::derive_iter(a.to_iter())
    }
}

impl TryDerive<coll::Sized> for Associative {
    type Error = Error;
    fn try_derive(s: coll::Sized) -> Result<Self, Error> {
        match s {
            coll::Sized::Associative(a) => Ok(a),
            coll::Sized::String(i) => Err(Error::expected("associative", i)),
            coll::Sized::Bytes(i) => Err(Error::expected("associative", i)),
            s => Ok(Associative::Assoc(Association::try_from_iter(s)?)),
        }
    }
}

impl TryDerive<Item> for Associative {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Error> {
        let s = coll::Sized::try_derive(i)?;
        Associative::try_derive(s)
    }
}

// Convert anything that can be iterated over as Items, to an
// Association. The items must be pairs that are
// convertable to Entry, otherwise it will return an error.
impl TryDeriveIterator<Item> for Association {
    fn try_from_iter<I>(l: I) -> Result<Self, Error>
    where
        I: IntoIterator<Item = Item>,
    {
        Ok(sync::Arc::new(
            l.into_iter()
                .map(|i| Entry::try_derive(i.clone()))
                .collect::<Result<HashMap<KeyItem, Item>, Error>>()?,
        ))
    }
}

impl Derive<HashMap<KeyItem, Item>> for Association {
    fn derive(h: HashMap<KeyItem, Item>) -> Self {
        sync::Arc::new(h)
    }
}

impl DeriveIterator<Entry> for Association {
    fn derive_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = Entry>,
    {
        sync::Arc::new(iter.into_iter().collect::<HashMap<KeyItem, Item>>())
    }
}

impl DeriveIterator<Entry> for coll::List {
    fn derive_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = Entry>,
    {
        coll::Arc::new(
            iter.into_iter()
                .map(|e| e.fit())
                .collect::<VecDeque<Item>>(),
        )
    }
}

impl DeriveIterator<KeyItem> for KeyList {
    fn derive_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = KeyItem>,
    {
        sync::Arc::new(iter.into_iter().collect::<VecDeque<KeyItem>>())
    }
}

impl Derive<Entry> for Item {
    fn derive(e: Entry) -> Item {
        coll::List::derive_iter([Item::derive(e.0), e.1]).fit()
    }
}

impl TryDerive<Item> for Entry {
    type Error = Error;

    fn try_derive(i: Item) -> Result<Self, Error> {
        let s = coll::Sized::try_derive(i)?;
        if s.len() != 2 {
            Err(Error::expected("pair", s))
        } else {
            let mut iter = s.into_iter();
            let key: KeyItem = iter.next().unwrap().try_fit()?;
            let value = iter.next().unwrap();
            Ok((key, value))
        }
    }
}

impl Derive<Associative> for Association {
    fn derive(a: Associative) -> Association {
        match a {
            Associative::Assoc(a) => a,
            a => Association::derive_iter(a.to_iter()),
        }
    }
}

impl Derive<AssociationContent> for Item {
    fn derive(a: AssociationContent) -> Item {
        sync::Arc::new(a).fit()
    }
}

impl Derive<Association> for Item {
    fn derive(a: Association) -> Item {
        Associative::Assoc(a).fit()
    }
}

impl Derive<Associative> for Item {
    fn derive(a: Associative) -> Item {
        coll::Sized::Associative(a).fit()
    }
}

impl<T, E, C> DeriveIterator<Result<T, E>> for Result<C, E>
where
    C: DeriveIterator<T>,
{
    fn derive_iter<I: IntoIterator<Item = Result<T, E>>>(iter: I) -> Self {
        let mut result = Vec::new();

        for item in iter {
            match item {
                Ok(value) => result.push(value),
                Err(e) => return Err(e),
            }
        }

        Ok(C::derive_iter(result))
    }
}

trait Convert<KA, VA> {
    /// Convert from any type of hashmap to any other, assuming the keys
    /// and values convert
    fn convert<KB, VB>(&self) -> Result<HashMap<KB, VB>, Error>
    where
        KB: Clone + Eq + Hash + TryDerive<KA, Error = Error>,
        VB: Clone + TryDerive<VA, Error = Error>,
        KA: Clone + Eq + Hash, // Assuming Clone is needed for TryFrom
        VA: Clone;
}

impl<KA, VA> Convert<KA, VA> for HashMap<KA, VA>
where
    KA: Eq + Hash + Clone,
    VA: Clone,
{
    fn convert<KB, VB>(&self) -> Result<HashMap<KB, VB>, Error>
    where
        KB: Clone + Eq + Hash + TryDerive<KA, Error = Error>,
        VB: Clone + TryDerive<VA, Error = Error>,
        KA: Clone + Eq + Hash, // Assuming Clone is needed for TryFrom
        VA: Clone,
    {
        let mut new_hashmap = HashMap::new();

        for (key, value) in self.iter().map(|(k, v)| (k.clone(), v.clone())) {
            let new_key: KB = key.try_fit()?;
            let new_value: VB = value.try_fit()?;
            new_hashmap.insert(new_key, new_value);
        }

        Ok(new_hashmap)
    }
}

mod serde {
    use super::{KeyItem, KeyList};
    use crate::traits::*;
    use serde::de::{self, Deserialize, Deserializer, Visitor};
    use serde::ser::{Serialize, SerializeSeq};
    use std::fmt;

    struct KeyItemVisitor;

    impl<'de> Visitor<'de> for KeyItemVisitor {
        type Value = KeyItem;

        fn expecting(&self, formatter: &mut fmt::Formatter) -> fmt::Result {
            formatter.write_str("expected a specific representation for Item")
        }

        fn visit_i64<E>(self, value: i64) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(KeyItem::Int(value))
        }

        fn visit_u64<E>(self, value: u64) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(KeyItem::Int(value as i64))
        }

        fn visit_str<E>(self, v: &str) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(KeyItem::String(v.to_string()))
        }

        fn visit_byte_buf<E>(self, v: Vec<u8>) -> Result<Self::Value, E>
        where
            E: de::Error,
        {
            Ok(KeyItem::Bytes(v))
        }

        fn visit_seq<A>(self, mut seq: A) -> Result<Self::Value, A::Error>
        where
            A: de::SeqAccess<'de>,
        {
            let mut items: Vec<KeyItem> = Vec::new();
            while let Some(item) = seq.next_element::<KeyItem>()? {
                items.push(item);
            }
            Ok(KeyItem::List(KeyList::derive_iter(items)))
        }
    }

    impl<'de> Deserialize<'de> for KeyItem {
        fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
        where
            D: Deserializer<'de>,
        {
            deserializer.deserialize_any(KeyItemVisitor)
        }
    }

    impl Serialize for KeyItem {
        fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
        where
            S: serde::Serializer,
        {
            match self {
                KeyItem::Int(i) => serializer.serialize_i64(*i),
                KeyItem::Word(w) => serializer.serialize_str(w.fit()),
                KeyItem::Char(c) => serializer.serialize_char(*c),
                KeyItem::Bytes(b) => serializer.serialize_bytes(b.as_slice()),
                KeyItem::List(ref l) => {
                    // Serialize a list (sequence)
                    let mut seq = serializer.serialize_seq(Some(l.len()))?;
                    for element in l.iter() {
                        seq.serialize_element(&element)?;
                    }
                    seq.end()
                }
                KeyItem::String(s) => serializer.serialize_str(s.as_str()),
            }
        }
    }
}

use super::associative as assoc;
use crate::list;
use crate::traits::*;
use crate::types::container::{self as coll, Mutey};
use crate::types::number::Int;
use crate::types::{Item, Word};
use std::convert::Infallible;

/// Represents a runtime error type. Contains generic fields to hold
/// things like what type of error, the actual vs expected conditions,
/// etc. Also holds whether the error has been handled or not, which
/// the runtime uses to decide whether to keep unwinding the program
/// looking for something to handle the error. An error that has been
/// handled is inert, it is just another data value.
#[derive(Clone, PartialEq)]
pub struct Error {
    pub data: assoc::Association,
    pub is_handled: bool,
}

impl Error {
    /// Creates a new error.
    pub fn create<T: Fit<Item>>(asked: coll::List, reason: &str, actual: Option<T>) -> Error {
        // let bt = backtrace::Backtrace::new();
        let mut data: Vec<(assoc::KeyItem, Item)> = vec![
            ("type".fit(), "error".fit()),
            ("asked".fit(), asked.fit()),
            ("reason".fit(), reason.to_string().fit()),
            //("backtrace".fit(), Item::String(format!("{:?}", bt))),
        ];
        if let Some(actual) = actual {
            data.push(("actual".fit(), actual.fit()));
        }
        Error {
            is_handled: false,

            data: assoc::Association::derive_iter(data),
        }
    }

    /// Creates a stack underflow error for when the current word
    /// needs more items than there are on the stack.
    pub fn stack_underflow() -> Error {
        Error::create(
            list!("consume"),
            "not enough items on stack",
            Option::<Item>::None,
        )
    }

    pub fn overflow() -> Error {
        Error::create(list!("arithmetic"), "number overflow", Option::<Item>::None)
    }

    pub fn undefined(w: Word) -> Error {
        Error::create(list!(w), "word is not defined", Option::<Item>::None)
    }

    pub fn type_mismatch<T: Fit<Item>>(asked: coll::List, actual: Option<T>) -> Error {
        Error::create(asked, "type mismatch", actual)
    }

    pub fn division_by_zero() -> Error {
        Error::create(list!("/"), "division by zero", Option::<Item>::None)
    }

    pub fn expected<T: Fit<Item>>(typestr: &str, actual: T) -> Error {
        Error::type_mismatch(list!(typestr), Some(actual))
    }

    pub fn short_list(expected: Int) -> Error {
        Error::create(
            list!("count", expected, ">="),
            "list had too few items",
            Option::<Item>::None,
        )
    }

    pub fn list_count(expected: Int) -> Error {
        Error::create(
            list!("count", expected, "="),
            "list had wrong number of items",
            Option::<Item>::None,
        )
    }

    pub fn negative(actual: Int) -> Error {
        Error::too_small(actual, 0)
    }

    pub fn too_small(actual: Int, expected: Int) -> Error {
        Error::create(list!(expected, ">="), "number too small", Some(actual))
    }

    pub fn too_large(actual: Int, expected: Int) -> Error {
        Error::create(list!(expected, "<="), "number too large", Some(actual))
    }

    pub fn parse(reason: &str) -> Error {
        Error::create(list!("read"), reason, Option::<Item>::None)
    }

    pub fn test_assertion(program: coll::List, expected: coll::List, actual: coll::List) -> Error {
        let mut e = Error::create(program, "assertion failed", Some(actual));
        let d = e.data.mutate();
        d.insert("expected-program".fit(), expected.fit());
        e
    }

    pub fn len(&self) -> usize {
        self.data.len()
    }
}

impl Derive<Infallible> for Error {
    fn derive(_x: Infallible) -> Self {
        match _x {} // Since Infallible can never be instantiated, this will never run
    }
}

impl Derive<Infallible> for Item {
    fn derive(_x: Infallible) -> Self {
        match _x {} // Since Infallible can never be instantiated, this will never run
    }
}

impl Derive<Error> for assoc::Association {
    fn derive(e: Error) -> assoc::Association {
        e.data
    }
}

impl TryDerive<Item> for Error {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        match i {
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(
                assoc::Associative::Error(e),
            ))) => Ok(e),
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::String(_)))
            | Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Bytes(_)))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::String(_)))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Bytes(_))) => {
                Err(Error::expected("error", Item::default()))
            }
            Item::Dispenser(coll::Dispenser::Sized(c)) => c.into_iter().try_fit(),
            i => Err(Error::expected("error", i)),
        }
    }
}

impl TryDerive<Box<dyn Iterator<Item = Item>>> for Error {
    type Error = Error;
    fn try_derive(i: Box<dyn Iterator<Item = Item>>) -> Result<Self, Self::Error> {
        //TODO: this can't fail, can just be a From.
        // Really though, Error should have predefined fields like Environment.
        let data = assoc::Association::try_from_iter(i)?;
        Ok(Error {
            data,
            is_handled: false,
        })
    }
}

impl TryDerive<assoc::Associative> for Error {
    type Error = Error;
    fn try_derive(a: assoc::Associative) -> Result<Self, Self::Error> {
        match a {
            assoc::Associative::Error(e) => Ok(e),
            assoc::Associative::Assoc(a) => {
                if a.get(&assoc::KeyItem::derive("type")) != Some(&Item::derive("error")) {
                    Err(Error::expected("error", a))
                } else {
                    Ok(Error {
                        data: a.clone(),
                        is_handled: true,
                    })
                }
            }
            i => Err(Error::expected("error", i)),
        }
    }
}

impl Derive<Error> for Item {
    fn derive(e: Error) -> Item {
        assoc::Associative::Error(e).fit()
    }
}

impl IntoIterator for Error {
    type Item = assoc::Entry;
    type IntoIter = Box<dyn Iterator<Item = assoc::Entry>>;

    fn into_iter(self) -> Self::IntoIter {
        let items: Vec<_> = self
            .data
            .iter()
            .map(|(k, v)| (k.clone(), v.clone()))
            .chain(std::iter::once(("handled".fit(), self.is_handled.fit())))
            .collect();
        Box::new(items.into_iter())
    }
}

use super::associative as assoc;
use crate::axiom::BUILTIN_FUNCTIONS;
use crate::list;
use crate::serialize;
use crate::traits::*;
use crate::types::container::{self as coll, Mutey};
use crate::types::*;
use internment::Intern;
use std::collections::HashSet;
use std::ptr;
use std::sync::Arc;

/// The definition of a [Word], contains its actual code (the
/// definition), and also documentation like specs and examples.
#[derive(Debug, Clone)]
pub struct Entry {
    pub examples: Option<coll::List>,
    pub spec: Option<Spec>,
    pub definition: Definition,
}

// TODO: move specs to their own module
/// An element of a [Spec], either an input or an output. Holds the
/// type and optional name of the input/output.
#[derive(Debug, Clone, PartialEq)]
pub struct SpecElement {
    pub elemtype: Word,
    pub name: Option<Word>,
}

pub type StackSpec = Vec<SpecElement>;

/// The spec of a [Word] consists of the input spec and the output
/// spec, that shows what the stack should look like before and after
/// the [Word] is invoked.
pub type Spec = (StackSpec, StackSpec);

impl TryDerive<Item> for SpecElement {
    type Error = Error;
    fn try_derive(i: Item) -> Result<SpecElement, Error> {
        match i {
            Item::Word(w) => Ok(SpecElement {
                elemtype: w,
                name: None,
            }),
            i => {
                let s = coll::List::try_derive(i)?;
                if s.len() != 2 {
                    Err(Error::list_count(2))
                } else {
                    let t = Word::try_derive(s.get(0).unwrap().clone())?;
                    let n = Word::try_derive(s.get(1).unwrap().clone())?;
                    Ok(SpecElement {
                        elemtype: t,
                        name: Some(n),
                    })
                }
            }
        }
    }
}

impl TryDerive<coll::List> for StackSpec {
    type Error = Error;
    fn try_derive(s: coll::List) -> Result<StackSpec, Error> {
        s.iter()
            .cloned()
            .map(SpecElement::try_derive)
            //.map(|r| r.and_then(SpecElement::try_derive))
            .collect::<Result<StackSpec, Error>>()
    }
}

impl TryDerive<coll::List> for Spec {
    type Error = Error;
    fn try_derive(s: coll::List) -> Result<Spec, Error> {
        if s.len() != 2 {
            Err(Error::list_count(2))
        } else {
            Ok((
                StackSpec::try_derive(coll::List::try_derive(s.get(0).unwrap().clone())?)?,
                StackSpec::try_derive(coll::List::try_derive(s.get(1).unwrap().clone())?)?,
            ))
        }
    }
}

impl TryDerive<Item> for Spec {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Spec, Error> {
        Spec::try_derive(coll::List::try_derive(i)?)
    }
}

impl Derive<SpecElement> for Item {
    fn derive(se: SpecElement) -> Item {
        if se.name.is_some() {
            list!(se.elemtype, se.name).fit()
        } else {
            Item::Word(se.elemtype)
        }
    }
}

impl Derive<Spec> for Item {
    fn derive(s: Spec) -> Item {
        list!(s.0, s.1).fit()
    }
}

impl ToIterator for Vec<SpecElement> {
    type Item = SpecElement;
    type IntoIter = std::vec::IntoIter<SpecElement>;

    fn to_iter(self) -> Self::IntoIter {
        self.into_iter()
    }
}

impl ToIterator for Vec<Namespace> {
    type Item = Namespace;
    type IntoIter = std::vec::IntoIter<Namespace>;

    fn to_iter(self) -> Self::IntoIter {
        self.into_iter()
    }
}

impl Derive<Namespace> for Item {
    fn derive(ns: Namespace) -> Item {
        match ns {
            Some(ns) => (*ns).clone().fit(),
            None => Item::default(),
        }
    }
}

impl IntoList for Vec<Namespace> {}
impl IntoList for Vec<SpecElement> {}

//impl Derive<Intern<Vec<u8>>> for

impl Entry {
    pub fn len(&self) -> usize {
        3 // 3 fields
    }

    pub fn get(&self, key: &str) -> Option<Item> {
        match key {
            "spec" => self.spec.clone().map(|x| x.fit()),
            "examples" => self.examples.clone().map(|x| x.fit()),
            "definition" => Some(match self.definition.clone() {
                dict::Definition::Axiom(_) => "builtin".fit(),
                dict::Definition::Derived(d) => d.fit(),
            }),
            _ => None,
        }
    }

    pub fn contains_key(&self, key: &assoc::KeyItem) -> bool {
        Word::try_derive(key.clone()).map_or(false, |ref w| {
            matches!(w.fit(), "examples" | "spec" | "definition")
        })
    }
}

// TODO: Use the builtin Bytes type
pub type Namespace = Option<Intern<Vec<u8>>>;

pub fn bytes_to_ns(b: Bytes) -> Namespace {
    if b.is_empty() {
        Default::default()
    } else {
        Some(Intern::new(b))
    }
}

impl TryDerive<Item> for Namespace {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Namespace, Error> {
        match i {
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Bytes(b))) => Ok(bytes_to_ns(b)),
            Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Bytes(b))) => Ok(bytes_to_ns(b)),
            i => {
                let s = coll::Sized::try_derive(i)?;
                if s.is_empty() {
                    Ok(Default::default())
                } else {
                    Err(Error::expected("namespace", s))
                }
            }
        }
    }
}

/// One of the main components of an
/// [crate::types::container::environment::Environment], holds [Word]s and their
/// definitions.
pub type Dictionary = coll::Arc<HashMap<Word, Entry>>;

pub trait Dict {
    /// Returns the difference between this dictionary and a "newer"
    /// one: The additions/updates, and the deletions.
    fn diff(&self, newer: Dictionary) -> (Vec<(Word, Entry)>, Vec<Word>);

    /// Takes a core module (in string form - should contain a series
    /// of word definitions, not wrapped in a single list), and
    /// inserts all the definitions into the dictionary, with an
    /// optional namespace.
    fn insert_core_module(&mut self, lexicon: String);

    /// Takes a mapping of word to definition, and updates all the
    /// dictionary entries so that the word will call that definition
    /// when the word is executed. The definitions should be Axiom
    /// variants, since those are the ones we have to define in rust.
    ///
    /// This method is used during bootstrap of the default environment.
    fn insert_axiom_fns(&mut self, updates: Vec<(Word, Definition)>);

    /// For stdlib words that are both built-in and part of a module
    /// that isn't necessarily loaded as part of the standard
    /// environment, we need to be able to link the word to its rust
    /// definition. Calling this function on a dictionary (whether
    /// full or just the partial dictionary created from a module),
    /// will create those links. In order for the links to be created,
    /// the current word currently has to have no definition field
    /// (set to None). Otherwise changes will not be applied.
    fn add_builtins(&mut self);

    /// Find the word in the dictionary in one of the given
    /// namespaces. The first match is applied to the word, or None if
    /// no matches.
    fn resolve_word(&self, w: &mut Word, namespaces: &[dict::Namespace]);

    /// Merges this dictionary with the given new dictionary. The new
    /// entries are added with the given namespace.
    fn merge(&mut self, new: Dictionary, namespace: &Namespace);
}

impl Dict for Dictionary {
    fn diff(&self, newer: Dictionary) -> (Vec<(Word, Entry)>, Vec<Word>) {
        diff_hashmaps(&self, &newer)
    }

    fn merge(&mut self, new: Dictionary, namespace: &Namespace) {
        let (adds, deletes) = self.diff(new);
        // add namepaces to the adds and deletes
        let adds: Vec<_> = adds
            .into_iter()
            .map(|(mut w, e)| {
                w.namespace = namespace.clone();
                (w, e)
            })
            .collect();
        let deletes: Vec<_> = deletes
            .into_iter()
            .map(|mut w| {
                w.namespace = namespace.clone();
                w
            })
            .collect();
        let d = self.mutate();

        d.extend(adds.into_iter());
        d.extend(make_deletes(deletes));
    }

    fn insert_core_module(&mut self, lexicon: String) {
        //println!("Parsing: {}", lexicon);
        let items = serialize::parse(lexicon).unwrap();
        for r in Box::new(items.iter().cloned()) {
            let (k, def): (assoc::KeyItem, Item) = r.try_fit().unwrap();
            let word: Word = k.try_fit().unwrap();

            let iter: Box<dyn Iterator<Item = Item>> = def.try_fit().unwrap();
            let new_entry: dict::Entry = iter.try_fit().unwrap();
            let new_entry2 = new_entry.clone();
            let dict = self.mutate();
            dict.entry(word)
                .and_modify(|e| {
                    e.examples = new_entry.examples;
                    e.spec = new_entry.spec;
                    e.definition = new_entry.definition;
                })
                .or_insert(new_entry2);
        }
    }

    fn insert_axiom_fns(&mut self, updates: Vec<(Word, Definition)>) {
        let dm = self.mutate();
        for (w, f) in updates {
            dm.entry(w).and_modify(|e| e.definition = f);
        }
    }

    fn add_builtins(&mut self) {
        let dm = self.mutate();
        for (bw, bd) in BUILTIN_FUNCTIONS.iter() {
            dm.entry(bw.clone()).and_modify(|d| match &d.definition {
                Definition::Derived(dd) => {
                    if dd.is_empty() {
                        d.definition = bd.clone();
                    }
                }
                _ => {}
            });
        }
    }

    fn resolve_word(&self, w: &mut Word, namespaces: &[dict::Namespace]) {
        // if the word is already namespaced we're done
        if w.namespace.is_none() {
            for namespace in namespaces.iter() {
                w.namespace = namespace.clone();
                if self.contains_key(w) {
                    return;
                }
            }
            // no match found, clear the namespace
            w.namespace = Default::default();
        }
    }
}

/// Each word should run a program that calls fail (already namespaced
/// to the stdlib so that the word acts like it isn't in the dictionary
/// even though it is.)
fn make_deletes(words: Vec<Word>) -> Vec<(Word, dict::Entry)> {
    words
        .into_iter()
        .map(|word| {
            println!("Shadowing word: {:?}", word);
            let err = Error::create(
                list!(word.clone()),
                "word removed by module",
                Some("access-denied"),
            );
            let entry = dict::Entry {
                examples: None,
                spec: None,
                definition: dict::Definition::Derived(list!(err, "fail")),
            };
            (word, entry)
        })
        .collect()
}

/// Returns the differences between two hashmaps, including the keys
/// that have been added or changed (including the new values), and
/// the keys that were deleted.
fn diff_hashmaps<K, V>(a: &HashMap<K, V>, b: &HashMap<K, V>) -> (Vec<(K, V)>, Vec<K>)
where
    K: Eq + Hash + Clone,
    V: PartialEq + Clone,
{
    let a_keys: HashSet<K> = a.keys().cloned().collect();
    let b_keys: HashSet<K> = b.keys().cloned().collect();

    // Keys that are in `b` but not in `a` or have updated values in `b`
    let added_or_updated: Vec<(K, V)> = b
        .iter()
        .filter(|(k, v)| !a_keys.contains(k) || a.get(k) != Some(v))
        .map(|(k, v)| (k.clone(), v.clone()))
        .collect();

    // Keys that are in `a` but not in `b`
    let deleted: Vec<K> = a_keys.difference(&b_keys).cloned().collect();

    (added_or_updated, deleted)
}

/// The actual code for what a [Word] should do.
#[derive(Clone)]
pub enum Definition {
    /// A definition in the base language - a rust function that
    /// modifies the environment.
    Axiom(&'static StepFn),
    /// A definition in terms of other [Word]s - a kcats program
    Derived(coll::List),
}

// dictionary entries are equal if they have the same function reference,
// no need to compare the function values
impl PartialEq for Definition {
    fn eq(&self, other: &Self) -> bool {
        match (self, other) {
            (Definition::Axiom(s), Definition::Axiom(o)) => ptr::eq(*s, *o),
            (Definition::Derived(s), Definition::Derived(o)) => s == o,
            _ => false,
        }
    }
}

impl PartialEq for Entry {
    fn eq(&self, other: &Self) -> bool {
        self.definition == other.definition
            && self.examples == other.examples
            && self.spec == other.spec
    }
}

impl fmt::Debug for Definition {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        match self {
            Definition::Axiom(_) => f.write_str("Builtin"),
            Definition::Derived(d) => {
                let mut ds = f.debug_list();
                ds.entries(d.iter());
                ds.finish()
            }
        }
    }
}

impl IntoIterator for Entry {
    type Item = assoc::Entry;
    type IntoIter = Box<dyn Iterator<Item = assoc::Entry>>;

    fn into_iter(self) -> Self::IntoIter {
        let mut v: Vec<(assoc::KeyItem, Item)> = vec![("definition".fit(), {
            match self.definition {
                dict::Definition::Derived(l) => l.fit(),
                dict::Definition::Axiom(_) => "builtin-function".fit(),
            }
        })];
        if let Some(e) = self.examples {
            v.push(("examples".fit(), e.fit()));
        }
        if let Some(s) = self.spec {
            v.push(("spec".fit(), s.fit()))
        }
        Box::new(v.into_iter())
    }
}

impl TryDerive<Box<dyn Iterator<Item = Item>>> for Entry {
    type Error = Error;
    fn try_derive(iter: Box<dyn Iterator<Item = Item>>) -> Result<Self, Error> {
        let mut examples: Option<coll::List> = None;
        let mut definition: Option<Definition> = None;
        let mut spec: Option<Spec> = None;
        for i in iter {
            let (k, v): (assoc::KeyItem, Item) = i.try_fit()?;
            //println!("k: {:?}, v: {:?}", k, v);
            if k == "examples".fit() {
                examples = Some(v.try_fit()?);
            } else if k == "definition".fit() {
                definition = Some(v.try_fit()?);
            } else if k == "spec".fit() {
                spec = v.try_fit().ok();
            } else {
                continue;
            }
        }
        Ok(Entry {
            examples,
            definition: definition.unwrap_or(Definition::Derived(coll::List::default())),
            spec,
        })
    }
}

impl TryDerive<Box<dyn Iterator<Item = Item>>> for Dictionary {
    type Error = Error;

    fn try_derive(iter: Box<dyn Iterator<Item = Item>>) -> Result<Self, Error> {
        iter.map(<(Word, Entry)>::try_derive)
            .collect::<Result<HashMap<Word, Entry>, Error>>()
            .map(Arc::new)
    }
}

impl TryDerive<Item> for Definition {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        coll::List::try_derive(i).map(Definition::Derived)
    }
}

impl TryDerive<Item> for Entry {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let s = coll::Sized::try_derive(i)?;
        match s {
            coll::Sized::Associative(assoc::Associative::DictEntry(d)) => Ok(d),
            c => c.into_iter().try_fit(),
        }
    }
}

impl Derive<Entry> for assoc::Associative {
    fn derive(d: Entry) -> assoc::Associative {
        let mut assoc = assoc::Association::fresh();
        let a = assoc.mutate();
        d.examples.and_then(|l| a.insert("examples".fit(), l.fit()));
        d.spec.and_then(|l| a.insert("spec".fit(), l.fit()));

        if let Definition::Derived(d) = d.definition {
            a.insert("definition".fit(), d.fit());
        }

        assoc::Associative::Assoc(assoc)
    }
}

impl TryDerive<Item> for Dictionary {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let s = coll::Sized::try_derive(i)?;
        match s {
            coll::Sized::Associative(assoc::Associative::Dictionary(d)) => Ok(d),
            c => c.into_iter().try_fit(),
        }
    }
}

impl Derive<Entry> for Item {
    fn derive(e: Entry) -> Self {
        Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(
            assoc::Associative::DictEntry(e),
        )))
    }
}

impl Derive<Dictionary> for Item {
    fn derive(d: Dictionary) -> Self {
        Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(
            assoc::Associative::Dictionary(d),
        )))
    }
}

impl Derive<(Word, Entry)> for Item {
    fn derive((k, v): (Word, Entry)) -> Item {
        coll::List::derive_iter([Item::Word(k), Item::derive(v.clone())]).fit()
    }
}

impl TryDerive<Item> for (Word, Entry) {
    type Error = Error;

    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let s = coll::Sized::try_derive(i)?;
        if s.len() != 2 {
            Err(Error::expected("pair", s))
        } else {
            let mut iter = s.into_iter();
            let key: Word = iter.next().unwrap().try_fit()?;
            let value: Entry = iter.next().unwrap().try_fit()?;
            Ok((key, value))
        }
    }
}

//! Functionality of a kcats execution environment.
use super::{associative as assoc, dictionary as dict};
use crate::axiom;
use crate::list;
use crate::serialize;
use crate::traits::*;
use crate::types::container::dictionary::Dict;
use crate::types::container::{self as coll, Mutey, Ordered};
use crate::types::number::Number;
use crate::types::*;

use once_cell::sync::Lazy;
use std::future;
use std::ops::Range;
use std::sync;

/// A struct to hold the state of an executing kcats program. The
/// `stack` is the data being manipulated, the `program` is program
/// remaining to be executed, and the `dictionary` is the set of
/// functions available to the program.
#[derive(Clone, PartialEq)]
pub struct Environment {
    pub stack: Stack,
    pub program: Stack,
    pub dictionary: dict::Dictionary,
    pub resolver: Vec<dict::Namespace>,
}

impl Environment {
    /// Push the [Item] onto the top of the stack.
    pub fn push<T: Fit<Item>>(&mut self, i: T) {
        coll::Arc::mutate(&mut self.stack).push_front(i.fit());
    }

    /// Pop the top [Item] from the stack, panicking if the stack is
    /// empty.
    pub fn pop(&mut self) -> Item {
        coll::Arc::mutate(&mut self.stack).pop_front().unwrap()
    }

    /// Pushes one item onto the front of the program (so that it
    /// executes first).
    pub fn push_prog(&mut self, i: Item) {
        coll::Arc::mutate(&mut self.program).push_front(i);
    }

    /// Pops an [Item] from the front of the program.
    pub fn pop_prog(&mut self) -> Item {
        coll::Arc::mutate(&mut self.program).pop_front().unwrap()
    }

    /// Returns a reference to the top stack [Item], or [None] if it's
    /// empty.
    pub fn tos(&self) -> Option<&Item> {
        self.stack.front()
    }

    /// Returns the length of this struct (as an associative
    /// structure), which is constant.
    pub fn len(&self) -> usize {
        3 // 3 fields
    }

    /// Treats the [Environment] as an associative structure,
    /// returning one of its fields, or [None].
    pub fn get(&self, key: &str) -> Option<Item> {
        match key {
            "stack" => Some(self.stack.clone().fit()),
            "program" => Some(self.program.clone().fit()),
            "dictionary" => Some(self.dictionary.clone().fit()),
            _ => None,
        }
    }

    /// Returns true if the [Environment] contains the given key,
    /// which is only true for its fixed fields.
    pub fn contains_key(&self, key: &assoc::KeyItem) -> bool {
        Word::try_derive(key.clone()).map_or(false, |ref w| {
            matches!(w.fit(), "stack" | "program" | "dictionary")
        })
    }

    /// Inserts the key/value into the [Environment]. If the key is
    /// not one of its fixed fields, return a demoted
    /// [assoc::Associative] value that's more generic and supports
    /// any key. Also optionally return any old value that might get
    /// overwritten.
    pub fn insert(mut self, k: assoc::KeyItem, v: Item) -> (assoc::Associative, Option<Item>) {
        let demote = |o: Environment, k: assoc::KeyItem, v: Item| {
            let mut a = assoc::Association::derive_iter(o);
            let am = a.mutate();
            let old = am.insert(k, v);
            (assoc::Associative::Assoc(a), old)
        };
        match k {
            assoc::KeyItem::Word(ref w) => {
                let w: &str = w.fit();
                match w {
                    "stack" => {
                        let l = coll::List::try_derive(v.clone());
                        match l {
                            Ok(l) => {
                                let old = self.stack.clone();
                                self.stack = l;
                                (assoc::Associative::Env(self), Some(old.fit()))
                            }
                            Err(_) => demote(self, k, v),
                        }
                    }
                    "program" => {
                        let l = coll::List::try_derive(v.clone());
                        match l {
                            Ok(l) => {
                                let old = self.program.clone();
                                self.program = l;
                                (assoc::Associative::Env(self), Some(old.fit()))
                            }
                            Err(_) => demote(self, k, v),
                        }
                    }
                    "dictionary" => {
                        let d = dict::Dictionary::try_derive(v.clone());
                        match d {
                            Ok(d) => {
                                let old = self.dictionary.clone();
                                self.dictionary = d;
                                (assoc::Associative::Env(self), Some(old.fit()))
                            }
                            Err(_) => demote(self, k, v),
                        }
                    }
                    "resolver" => {
                        let l = coll::List::try_derive(v.clone());
                        match l {
                            Ok(l) => {
                                let old = self.resolver.clone();
                                let namespaces: Result<Vec<dict::Namespace>, Error> = l.try_fit();
                                match namespaces {
                                    Ok(ns) => {
                                        self.resolver = ns;
                                        (assoc::Associative::Env(self), Some(old.fit()))
                                    }
                                    Err(_) => demote(self, k, v),
                                }
                            }
                            Err(_) => demote(self, k, v),
                        }
                    }
                    k => demote(self, k.fit(), v),
                }
            }
            _ => demote(self, k, v),
        }
    }

    /// Reads a stdlib module and updates the dictionary.
    pub fn load_builtin_module(&mut self, module_alias: Word) -> Result<(), Error> {
        self.push(module_alias);
        axiom::read_blob(self)
    }

    /// Loads the core modules as part of preparing a standard
    /// environment.
    fn load_core_modules(&mut self) -> Result<(), Error> {
        // Assuming /project/core/ is in your project's root directory and part of the source
        let files: Vec<&[u8]> = vec![
            include_bytes!("../../kcats/core/stack-builtins.kcats"),
            include_bytes!("../../kcats/core/motion-builtins.kcats"),
            include_bytes!("../../kcats/core/compare-builtins.kcats"),
            include_bytes!("../../kcats/core/math-builtins.kcats"),
            include_bytes!("../../kcats/core/boolean-builtins.kcats"),
            include_bytes!("../../kcats/core/serialize-builtins.kcats"),
            include_bytes!("../../kcats/core/encode-builtins.kcats"),
            include_bytes!("../../kcats/core/strings-builtins.kcats"),
            include_bytes!("../../kcats/core/errors-builtins.kcats"),
            include_bytes!("../../kcats/core/pipes-builtins.kcats"),
            include_bytes!("../../kcats/core/stack.kcats"),
            include_bytes!("../../kcats/core/motion.kcats"),
            include_bytes!("../../kcats/core/collections-builtins.kcats"),
            include_bytes!("../../kcats/core/execute-builtins.kcats"),
            include_bytes!("../../kcats/core/execute.kcats"),
            include_bytes!("../../kcats/core/dictionary-builtins.kcats"),
            include_bytes!("../../kcats/core/math.kcats"),
            include_bytes!("../../kcats/core/compare.kcats"),
            include_bytes!("../../kcats/core/collections.kcats"),
            include_bytes!("../../kcats/core/associations-builtins.kcats"),
            include_bytes!("../../kcats/core/associations.kcats"),
            include_bytes!("../../kcats/core/dictionary.kcats"),
            include_bytes!("../../kcats/core/environment-builtins.kcats"),
            include_bytes!("../../kcats/core/environment.kcats"),
        ];

        for &file_contents in &files {
            let lexicon = String::from_utf8_lossy(file_contents).into_owned();
            self.dictionary.insert_core_module(lexicon);
        }
        Ok(())
    }

    /// Returns an error if the stack isn't at least `min_depth` deep.
    fn check_stack_depth(&self, min_depth: usize) -> Result<(), Error> {
        //println!("Checking stack has at least {} items", min_depth);
        if self.stack.len() < min_depth {
            Err(Error::stack_underflow())
        } else {
            Ok(())
        }
    }

    /// Returns an error if the stack doesn't match the given input spec.
    pub fn check_input_spec(&self, specs: &dict::StackSpec) -> Result<(), Error> {
        self.check_stack_depth(specs.len())?;
        let indexes = Range {
            start: 0,
            end: specs.len(),
        };

        indexes.into_iter().try_for_each(|i| {
            let item = self.stack.get(i).unwrap();
            let spec = specs.get(i).unwrap();
            check_type(item, &spec.elemtype)
        })
    }

    pub fn is_finished(&self) -> bool {
        self.program.is_empty()
    }
}

impl Default for Environment {
    /// Returns the default environment, which is the "standard"
    /// environment. It loads some standard libraries and core
    /// functions. The environment is only built once and memoized.
    fn default() -> Self {
        static INST: Lazy<Environment> = Lazy::new(|| {
            let mut env = Environment {
                dictionary: sync::Arc::new(HashMap::new()),
                stack: Default::default(),
                program: Default::default(),
                resolver: Default::default(),
            };
            env.load_core_modules()
                .expect("failed to load core modules");
            env.push(list!(
                "errors",
                "environment-builtins",
                "encode",
                "sets-builtins",
                "time", // good candidate for lib
                "pipes",
                "methods",
                "generators",
                "template",
                "debug" // END default namespace // another good candidate for lib
            ));

            // Here we can no longer modify our own dictionary, so
            // here's what we do instead, we build a new dictionary
            // and leave it on the stack. Then when finished we grab
            // it at the end of this function.
            // We also want to load a few optional (non-core) libs
            env.program.prepend(list!(
                "dictionary",
                "swap",
                list!("decache", "string", "read", "shielddown"),
                "step"
            ));

            // There's a problem here: the builtins need to be added in a
            // way that they don't get overwritten. They may need to get
            // added piece by piece, somehow. Perhaps a hashmap that we
            // can lookup values in as words get loaded, and specify
            // they're builtin somehow (maybe [builtin yes], but just not
            // having definition would also do it)
            env.dictionary.add_builtins();
            let mut env = futures::executor::block_on(async move { axiom::eval(env).await });
            //print!("Env: {:?}", env);
            let mut dict: dict::Dictionary = env.pop().try_fit().unwrap();
            dict.add_builtins();
            env.dictionary = dict;
            env
        });
        INST.clone()
    }
}

/// Returns an error if the [Item] is not of the type specified by
/// [Word] `w`. This allows specs to have their own little type
/// hierarchy, eg, `integer` is a `number`, `list` is a `sized` etc.
fn check_type(i: &Item, w: &Word) -> Result<(), Error> {
    //println!("Check {:?} is {:?}", w, i);
    match (w, i) {
        (w, _) if *w == *S_ITEM => Ok(()),
        (w, Item::Dispenser(_) | Item::Receptacle(_)) if *w == *S_DISPENSER => Ok(()),
        (w, Item::Receptacle(_) | Item::Dispenser(_)) if *w == *S_RECEPTACLE => Ok(()),
        (w, Item::Number(Number::Int(_))) if *w == *S_INTEGER || *w == *S_NUMBER => Ok(()),
        (w, Item::Number(Number::Float(_))) if *w == *S_FLOAT || *w == *S_NUMBER => Ok(()),
        // TODO: also handle cases where bytes/string is a list
        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Bytes(_)))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Bytes(_))),
        ) if *w == *S_BYTES || *w == *S_ORDERED => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::String(_)))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::String(_))),
        ) if *w == *S_STRING => Ok(()),
        (w, Item::Word(_)) if *w == *S_WORD => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Out(_))
            | Item::Dispenser(coll::Dispenser::Tunnel(_))
            | Item::Receptacle(coll::Receptacle::Tunnel(_))
            | Item::Receptacle(coll::Receptacle::In(_)),
        ) if *w == *S_PIPE => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::List(_)))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::List(_))),
        ) if *w == *S_LIST || *w == *S_PROGRAM => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(_)))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Associative(_))),
        ) if *w == *S_ASSOC => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(
                assoc::Associative::Error(_),
            )))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Associative(
                assoc::Associative::Error(_),
            ))),
        ) if *w == *S_ERROR => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(
                assoc::Associative::Dictionary(_),
            )))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Associative(
                assoc::Associative::Dictionary(_),
            ))),
        ) if *w == *S_DICTIONARY => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(_))
            | Item::Receptacle(coll::Receptacle::Sized(_)),
        ) if *w == *S_SIZED || *w == *S_ORDERED => Ok(()),

        (
            w,
            Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(
                assoc::Associative::Env(_),
            )))
            | Item::Receptacle(coll::Receptacle::Sized(coll::Sized::Associative(
                assoc::Associative::Env(_),
            ))),
        ) if *w == *S_ENVIRONMENT => Ok(()),
        (w, i) => {
            //println!("Type check failed! wanted {} got {:?}", w, i);
            Err(Error::expected(w.fit(), i.clone()))
        }
    }
}

impl TryDerive<Box<dyn Iterator<Item = Item>>> for Environment {
    type Error = Error;
    fn try_derive(iter: Box<dyn Iterator<Item = Item>>) -> Result<Self, Error> {
        let mut stack: Option<coll::List> = None;
        let mut program: Option<coll::List> = None;
        let mut dictionary: Option<dict::Dictionary> = None;
        let mut resolver: Option<Vec<dict::Namespace>> = None;
        for i in iter {
            let (k, v): (assoc::KeyItem, Item) = i.try_fit()?;
            if k == "stack".fit() {
                stack = Some(v.try_fit()?)
            } else if k == "program".fit() {
                program = Some(v.try_fit()?)
            } else if k == "dictionary".fit() {
                dictionary = Some(v.try_fit()?)
            } else if k == "resolver".fit() {
                resolver = Some(v.try_fit()?)
            } else {
                continue;
            }
        }
        let mut env = Environment::default();
        env.stack = stack.unwrap_or_default();
        env.program = program.unwrap_or_default();
        env.dictionary = dictionary.unwrap_or_else(|| Environment::default().dictionary);
        env.resolver = resolver.unwrap_or_default();
        Ok(env)
    }
}
impl TryDerive<Item> for Environment {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let s = coll::Sized::try_derive(i)?;

        match s {
            coll::Sized::Associative(assoc::Associative::Env(e)) => Ok(e),
            l => l.into_iter().try_fit(),
        }
    }
}

impl Derive<Environment> for Item {
    fn derive(env: Environment) -> Item {
        assoc::Associative::Env(env).fit()
    }
}

impl Derive<Environment> for Future<Environment> {
    fn derive(env: Environment) -> Future<Environment> {
        Box::pin(future::ready(env))
    }
}

impl IntoIterator for Environment {
    type Item = assoc::Entry;
    type IntoIter = Box<dyn Iterator<Item = assoc::Entry>>;

    fn into_iter(self) -> Self::IntoIter {
        let v: Vec<(assoc::KeyItem, Item)> = vec![
            ("stack".fit(), self.stack.fit()),
            ("program".fit(), self.program.fit()),
            ("dictionary".fit(), self.dictionary.fit()),
        ];
        Box::new(v.into_iter())
    }
}

impl serialize::Display for Environment {
    fn representation(&self) -> Item {
        let assoc = assoc::Association::derive_iter(self.clone());
        //let am = assoc.mutate();
        //am.remove(&("dictionary".fit()));
        assoc.fit()
    }
}