The kcats Programming Language (Production Implementation)

//! Defines kcats internal data types.
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 core::fmt;
use internment::Intern;
use lazy_static::lazy_static;
use std::collections::{HashMap, VecDeque};

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, PartialOrd, Ord, Default, Hash, PartialEq)]
pub struct Word {
    pub data: Intern<String>,
    pub quoted: bool,
}

impl fmt::Debug for Word {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        if self.quoted {
            write!(f, "[{}]", self.data.as_str())
        } else {
            write!(f, "{}", self.data.as_str())
        }
    }
}

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),
            quoted: false,
        }
    }
}

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;

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

/// A kcats data value.
#[derive(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 from)
    Dispenser(coll::Dispenser),
    /// A container value (that [Item]s can be put into)
    Receptacle(coll::Receptacle),
}

impl fmt::Debug for Item {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Item::Number(n) => write!(f, "{:?}", n),
            Item::Word(w) => write!(f, "{:?}", w),
            Item::Char(c) => write!(f, "Char{:?}", c),
            Item::Dispenser(d) => write!(f, "{:?}", d),
            Item::Receptacle(r) => write!(f, "{:?}", r),
        }
    }
}

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
/// [env::Environment] 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 s = coll::Sized::try_derive(i)?;
                match s {
                    coll::Sized::String(s) => Ok(s.fit()),
                    s => {
                        let i2 = s.clone();
                        let l = coll::List::try_derive(s);
                        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)),
        }
    }
}

impl TryDerive<Item> for char {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        match i {
            Item::Char(c) => Ok(c),
            b => Err(Error::expected("char", 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 Derive<()> for Item {
    fn derive(_: ()) -> Self {
        Item::default()
    }
}

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::container as cont;
use crate::types::Item;
use num_integer::Roots;
use serde::ser::{Serialize, Serializer};
use std::num::{ParseFloatError, ParseIntError};
/// 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 From<ParseIntError> for Error {
    fn from(e: ParseIntError) -> Self {
        Error::parse(e.to_string().as_str())
    }
}
impl From<ParseFloatError> for Error {
    fn from(e: ParseFloatError) -> Self {
        Error::parse(e.to_string().as_str())
    }
}

impl TryDerive<Item> for Number {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let fromstr = |s: String| {
            let r = s
                .as_str()
                .parse::<i64>()
                .map(Number::Int)
                .map_err(Error::from);

            r.or_else(|_| s.as_str().parse::<Float>().map(Number::Float))
                .map_err(Error::from)
        };
        match i {
            Item::Number(i) => Ok(i),
            Item::Char(c) => Ok(Number::Int(c as Int)),
            Item::Dispenser(cont::Dispenser::Sized(cont::Sized::String(s))) => fromstr(s),
            Item::Receptacle(cont::Receptacle::Sized(cont::Sized::String(s))) => fromstr(s),
            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::container::error::Nested;
use crate::types::container::pipe::FutureTake;
use crate::types::number::{Int, Number};
use crate::types::*;

use core::fmt;
use std::convert::Infallible;
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 Derive<ListContent> for Item {
    fn derive(l: ListContent) -> Item {
        List::derive(l).fit()
    }
}

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<Char> for List {
    fn derive_iter<I>(iter: I) -> Self
    where
        I: IntoIterator<Item = Char>,
    {
        Arc::new(
            iter.into_iter()
                .map(Item::derive)
                .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())
    }
}

/// A trait for joining two values together. There are some precedence rules:
///
/// 1. If there are two different types being joined, the type that is
/// returned is either the most specialized types of the two being
/// joined, or the most specialized type that's possible to construct
/// given the two values. (For example, joining a Set with a List, or
/// vice versa, will always be a Set. Joining an Association with a
/// Dictionary will be an Associative enum but the variant will depend
/// on whether the Association data fits the schema of a
/// Dictionary. If so, it will be Dictionary, otherwise Assoc.)
///
/// 2. If the result type is keyed, (eg, Map or Set or struct types),
/// the RHS argument's keys take precedence over self's.
pub trait Join<RHS> {
    type Output;
    type Error;
    fn join(self, rhs: RHS) -> Result<Self::Output, Self::Error>;
}

impl Join<&str> for String {
    type Output = String;
    type Error = Infallible;
    fn join(mut self, rhs: &str) -> Result<Self::Output, Self::Error> {
        self.push_str(rhs);
        Ok(self)
    }
}

impl Join<char> for String {
    type Output = String;
    type Error = Infallible;
    fn join(mut self, rhs: char) -> Result<Self::Output, Self::Error> {
        self.push(rhs);
        Ok(self)
    }
}

impl Join<List> for List {
    type Output = List;
    type Error = Infallible;
    fn join(mut self, rhs: List) -> Result<Self::Output, Self::Error> {
        //println!("Joining list to list");
        let am = self.mutate();
        am.extend(rhs.iter().cloned());
        Ok(self)
    }
}

impl Join<Set> for Set {
    type Output = Set;
    type Error = Infallible;
    fn join(mut self, rhs: Set) -> Result<Self::Output, Self::Error> {
        let am = self.mutate();
        am.extend(rhs.iter().cloned());
        Ok(self)
    }
}

/// When joining a List with a String, which type we get back depends
/// on the contents of the list. If the list has non-char items in it,
/// we get a List. Otherwise, a string.
impl Join<String> for List {
    type Output = Sized;
    type Error = Infallible;
    fn join(mut self, rhs: String) -> Result<Self::Output, Self::Error> {
        match self
            .iter()
            .cloned()
            .map(|i| Char::try_derive(i))
            .collect::<Result<Vec<Char>, Error>>()
        {
            Ok(vc) => {
                //join as string if all the list items are chars
                let mut x = vc.iter().collect::<String>();

                x.push_str(rhs.as_str());
                Ok(Sized::String(x))
            }
            Err(_) => {
                // join as list
                self.mutate().extend(rhs.chars().map(Item::derive));
                Ok(Sized::List(self))
            }
        }
    }
}

/// When joining a String with a List, which type we get back depends
/// on the contents of the list. If the list has non-char items in it,
/// we get a List. Otherwise, a string.
impl Join<List> for String {
    type Output = Sized;
    type Error = Infallible;
    fn join(mut self, rhs: List) -> Result<Self::Output, Self::Error> {
        match rhs
            .iter()
            .cloned()
            .map(|i| Char::try_derive(i))
            .collect::<Result<Vec<Char>, Error>>()
        {
            Ok(vc) => {
                //join as string if all the list items are chars
                let x = vc.iter().collect::<String>();

                self.push_str(x.as_str());
                Ok(Sized::String(self))
            }
            Err(_) => {
                // join as list
                let mut sl: List = self.fit();
                sl.mutate().extend(rhs.iter().cloned());
                Ok(Sized::List(sl))
            }
        }
    }
}

impl Join<List> for assoc::Associative {
    type Output = assoc::Associative;
    type Error = Error;
    fn join(self, other: List) -> Result<Self::Output, <Self as Join<List>>::Error> {
        //println!("Joining list to associative");
        let la =
            assoc::Associative::Assoc(assoc::Association::try_from_iter(other.iter().cloned())?);
        Ok(self.join(la).unwrap())
    }
}

impl Join<assoc::Associative> for List {
    type Output = assoc::Associative;
    type Error = Error;
    fn join(self, other: assoc::Associative) -> Result<Self::Output, Self::Error> {
        //println!("Joining associative to list");
        let sa =
            assoc::Associative::Assoc(assoc::Association::try_from_iter(self.iter().cloned())?);
        Ok(sa.join(other).unwrap())
    }
}

/// Joining a List with a Set will be a set.
impl Join<Set> for List {
    type Output = Set;
    type Error = Error;
    fn join(self, mut other: Set) -> Result<Self::Output, Self::Error> {
        let bm = other.mutate();

        bm.extend(
            self.iter()
                .cloned()
                .map(assoc::KeyItem::try_derive)
                .collect::<Result<Vec<assoc::KeyItem>, Error>>()?,
        );
        Ok(other)
    }
}

impl Join<String> for String {
    type Output = String;
    type Error = Infallible;
    fn join(mut self, other: String) -> Result<Self::Output, Self::Error> {
        self.push_str(&other);
        Ok(self)
    }
}

/// Joins two containers into one.
impl Join<Sized> for Sized {
    type Output = Sized;
    type Error = Error;

    fn join(self, other: Sized) -> Result<Self::Output, Self::Error> {
        //println!("Joining sized {:?} to sized {:?}", self, other);
        Ok(match (self, other) {
            (Sized::Associative(a), Sized::List(l)) => Sized::Associative(a.join(l)?),
            (Sized::List(l), Sized::Associative(a)) => Sized::Associative(l.join(a)?),
            (Sized::Associative(a), Sized::Associative(b)) => {
                Sized::Associative(a.join(b).unwrap())
            }
            (Sized::List(a), Sized::List(b)) => Sized::List(a.join(b).unwrap()),
            (Sized::Set(a), Sized::Set(b)) => Sized::Set(a.join(b).unwrap()),
            (Sized::List(a), Sized::Set(b)) => Sized::Set(a.join(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)
            }
            (Sized::String(s), Sized::List(l)) => s.join(l).unwrap(),
            (Sized::List(l), Sized::String(s)) => l.join(s).unwrap(),
            (s, other) => {
                if s.is_empty() {
                    other
                } else if other.is_empty() {
                    s
                } else {
                    Err(Error::expected("joinable", list!(s, other)))?
                }
            }
        })
    }
}
pub trait Container<T> {
    fn has(&self, item: &T) -> bool;
}

pub trait Count {
    fn count(&self) -> usize;
}

/// A trait for containers where you can take an item out "in-place"
/// without blocking. The container itself is mutated and the item is
/// returned.
pub trait SimpleTake {
    type Item: Send + Fit<Item>;
    fn take_simple(&mut self) -> Option<Self::Item>;
}

// pub trait DemotingTake {
//     type Item;
//     type Output;
//     fn take_demoting(self) -> (Option<Self::Item>, Self::Output);
// }

pub trait Take {
    type Output;
    type Item;
    fn take(self) -> Future<(Result<Option<Self::Item>, Error>, Self::Output)>;
}

/// A blanket impl for Take, for any type that already implements SimpleTake.
impl<T> Take for T
where
    T: SimpleTake + Send + 'static,
{
    type Output = T;
    type Item = Item;

    fn take(mut self) -> Future<(Result<Option<Self::Item>, Error>, Self::Output)> {
        let item = self.take_simple();
        let result = future::ready((Ok(item.map(|i| i.fit())), self));
        Box::pin(result)
    }
}

impl Count for Sized {
    fn count(&self) -> usize {
        match self {
            Self::Associative(a) => a.len(),
            Self::List(l) => l.count(),
            Self::String(s) => s.len(),
            Self::Bytes(b) => b.len(),
            Self::Set(s) => s.len(),
        }
    }
}

impl Container<Item> for Sized {
    fn has(&self, other: &Item) -> bool {
        //println!("Has: {:?}\n{:?}", self, other);
        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.has(c),
                i => match String::try_derive(i.clone()) {
                    Ok(ref s) => container.has(s),
                    Err(_) => false,
                },
            },
            _ => false,
        }
    }
}

impl SimpleTake for Sized {
    //type Output = Self;
    type Item = Item;
    fn take_simple(&mut self) -> Option<Self::Item> {
        //println!("Taking! {:?}", self);
        match self {
            Self::Associative(ref mut a) => {
                let v = a.take_simple();
                *self = Sized::Associative(a.clone());
                v
            }
            Sized::List(ref mut l) => l.take_simple(),
            Sized::String(ref mut s) => s.take_simple().map(Item::derive),
            Sized::Bytes(ref mut b) => b.take_simple().map(Item::derive),
            Sized::Set(ref mut s) => s.take_simple(),
        }
    }
}

impl Count for String {
    fn count(&self) -> usize {
        self.len()
    }
}

impl Container<char> for String {
    fn has(&self, item: &char) -> bool {
        self.contains(*item)
    }
}

impl Container<String> for String {
    fn has(&self, item: &String) -> bool {
        self.contains(item.as_str())
    }
}

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 prepend_iter<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 Count for List {
    fn count(&self) -> usize {
        self.len()
    }
}

impl Container<Item> for List {
    fn has(&self, i: &Item) -> bool {
        self.contains(i)
    }
}

// impl Take for List {
//     type Item = Item;
//     type Output = List;
//     fn take(mut self) -> Future<(Self::Output, Result<Option<Item>, Error>)> {
//         let v = self.mutate().pop_front();
//         Box::pin(future::ready((self, Ok(v))))
//     }
// }

//impl Take for

impl Ordered for List {
    fn prepend(&mut self, items: List) {
        self.prepend_iter(items.iter().cloned());
    }

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

    fn reverse(&mut self) {
        let m = self.mutate();
        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(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),
}

impl fmt::Debug for Dispenser {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Dispenser::Sized(sized) => write!(f, "{:?}", sized),
            Dispenser::Out(out) => write!(f, "{:?}", out),
            Dispenser::Tunnel(tunnel) => write!(f, "{:?}", 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(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),
}

impl fmt::Debug for Receptacle {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Receptacle::Sized(sized) => write!(f, "{:?}", sized),
            Receptacle::In(i) => write!(f, "{:?}", i),
            Receptacle::Tunnel(tunnel) => write!(f, "{:?}", tunnel),
        }
    }
}

/// Collections that have a definite size that we can access. Implies
/// that it can also be appended to.
#[derive(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 fmt::Debug for Sized {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Sized::Associative(a) => write!(f, "{:?}", a),
            Sized::List(l) => write!(f, "{:?}", l),
            Sized::Set(s) => write!(f, "{:?}", s),
            Sized::String(s) => write!(f, "{:?}", s),
            Sized::Bytes(b) => write!(f, "{:?}", b),
        }
    }
}

/// Empty Sized containers are equal to each other.
impl PartialEq for Sized {
    fn eq(&self, other: &Self) -> bool {
        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,
            _ => self.is_empty() && other.is_empty(),
        }
    }
}

/// 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).
impl Take for Dispenser {
    type Output = Self;
    type Item = Item;
    fn take(self) -> Future<(Result<Option<Self::Item>, Error>, Self::Output)> {
        match self {
            Dispenser::Sized(mut s) => {
                let v = s.take_simple();
                //let (r, s) = s.take();
                // i.map(|r| {
                //     (Dispenser::SIzed(s), Self::result_to_option(r))
                // })

                Box::pin(future::ready((Ok(v), Dispenser::Sized(s))))
            }
            Dispenser::Out(mut o) => {
                Box::pin(async move { (o.take_future().await, Dispenser::Out(o)) })
            }
            Dispenser::Tunnel(mut t) => {
                Box::pin(async move { (t.take_future().await, Dispenser::Tunnel(t)) })
            }
        }
    }
}

pub fn result_to_option(r: Result<Option<Item>, Error>) -> Option<Item> {
    match r {
        Ok(Some(i)) => Some(i),
        Ok(None) => None,
        Err(e) => Some(Item::derive(e)),
    }
}

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(mut s) => {
    //             let v = s.take_simple();
    //             //let (r, s) = s.take();
    //             // i.map(|r| {
    //             //     (Dispenser::SIzed(s), Self::result_to_option(r))
    //             // })

    //             Box::pin(future::ready((Dispenser::Sized(s), v)))
    //         }
    //         Dispenser::Out(mut o) => Box::pin({
    //             let i = o.take();
    //             i.map(|r| (Dispenser::Out(o), Self::result_to_option(r)))
    //         }),
    //         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 SimpleTake for List {
    type Item = Item;
    fn take_simple(&mut self) -> Option<Self::Item> {
        if self.is_empty() {
            None
        } else {
            let lm = self.mutate();
            let i = lm.pop_front();
            i
        }
    }
}

impl SimpleTake for String {
    type Item = char;
    fn take_simple(&mut self) -> Option<Self::Item> {
        // TODO: this may perform badly
        let first_char = self.chars().next();
        self.drain(..first_char.map(|s| s.len_utf8()).unwrap_or(0));
        first_char
    }
}

impl SimpleTake for Bytes {
    type Item = Int;
    fn take_simple(&mut self) -> Option<Self::Item> {
        if self.is_empty() {
            None
        } else {
            let i = Some(self[0] as Int);
            self.drain(..1);
            i
        }
    }
}

impl SimpleTake for Set {
    type Item = Item;
    fn take_simple(&mut self) -> Option<Self::Item> {
        let sm = self.mutate();
        sm.iter().next().map(|v| v.clone().fit())
    }
}

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

    /// Takes an item from the back (end) of the container.
    pub fn pop(self) -> (Self, Option<Item>) {
        match self {
            Sized::Associative(mut a) => {
                let v = a.take_simple();
                (Sized::Associative(a), v)
            }
            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 container, 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)),
        }
    }

    /// Returns a new empty version of this container. Does not
    /// modify this container. The new container 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 container, 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 = Self::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(Fit::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 Derive<String> for List {
    fn derive(s: String) -> Self {
        List::derive_iter(s.chars())
    }
}

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.clone())
                .caused(Error::expected("list", 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.clone())
                .caused(Error::expected("sized", 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("receptacle", 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("receptacle", 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<Receptacle> for Item {
    fn derive(c: Receptacle) -> Self {
        Item::Receptacle(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<_, 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())
    }
}

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

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

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::{Count, Join, Mutey};
use crate::types::number::{Int, Number};
use crate::types::*;
use std::collections::HashSet;
use std::convert::Infallible;
use std::sync::{self, Arc};

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 the words available in to use
    Words(dict::Words),
    /// Represents a dictionary, including which modules have priority
    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::Word(w) => Ok(KeyItem::Word(w)),
            Item::Char(c) => Ok(KeyItem::Char(c)),
            i => match coll::Sized::try_derive(i)? {
                coll::Sized::String(i) => Ok(KeyItem::String(i)),

                coll::Sized::Bytes(i) => Ok(KeyItem::Bytes(i)),

                coll::Sized::List(l) => {
                    Ok(KeyItem::List(KeyList::try_from_iter(l.iter().cloned())?))
                }
                s => {
                    println!("Bad keyitem {:?}", s);
                    Err(Error::expected("KeyItem", s))
                }
            },
        }
    }
}

impl TryDerive<KeyItem> for Word {
    type Error = Error;
    fn try_derive(k: KeyItem) -> Result<Self, Self::Error> {
        match k {
            KeyItem::Word(w) => Ok(w),
            KeyItem::String(s) => Ok(s.fit()),
            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 coll::Join<coll::List> for Association {
    type Output = Association;
    type Error = Error;
    fn join(self, other: coll::List) -> Result<Self::Output, Self::Error> {
        //println!("Joining list to association");
        let la = Association::try_from_iter(other.iter().cloned())?;
        Ok(self.join(Associative::Assoc(la)).unwrap())
    }
}

// impl coll::Join<Association> for Associative {
//     type Output = Associative;
//     type Error = Infallible;
//     fn join(self, other: Association) -> Result<Self::Output, Error> {
//         let la = Association::try_from_iter(other.iter().cloned())?;
//         self.join(Associative::Assoc(la))
//     }
// }

impl coll::Join<Associative> for Association {
    type Output = Association;
    type Error = Infallible;
    fn join(mut self, other: Associative) -> Result<Self::Output, Self::Error> {
        let thism = self.mutate();
        thism.extend(other.to_iter());
        Ok(self)
    }
}

/// 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`.
impl coll::Join<Associative> for Associative {
    type Output = Associative;
    type Error = Infallible;
    fn join(self, other: Associative) -> Result<Self::Output, <Self as Join<Associative>>::Error> {
        //println!("Joining associative to associative");
        Ok(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(this), Associative::Dictionary(other)) => {
                Associative::Dictionary(this.join(other).unwrap())
            }
            //(Associative::Dictionary(this), Associative::Assoc(other)) => {}
            (Associative::Words(this), Associative::Assoc(other)) => this.join(other).unwrap(),
            (Associative::Assoc(this), Associative::Words(other)) => this.join(other).unwrap(),
            (Associative::Error(_), Associative::Error(other)) => Associative::Error(other),
            (Associative::Env(_), Associative::Env(other)) => Associative::Env(other),
            (Associative::Nothing, Associative::Nothing) => Associative::Nothing,
            // This is infallible so .unwrap should be safe
            (Associative::Assoc(this), other) => Associative::Assoc(this.join(other).unwrap()),
            (this, other) => {
                unimplemented!("Join between associatives: {:?} \n\n{:?}", this, other)
            }
        })
    }
}

impl coll::SimpleTake for Association {
    type Item = Entry;
    fn take_simple(&mut self) -> Option<Self::Item> {
        let maybe_key = self.keys().next().cloned();
        let am = self.mutate();
        let maybe_value = maybe_key.as_ref().and_then(|key| am.remove(key));

        maybe_key.map(|key| (key, maybe_value.unwrap_or_default()))
    }
}

/// The take operation is for generic containers but we can
/// perform it on an Associative by removing an arbitrary pair and
/// returning it.
impl coll::SimpleTake for Associative {
    type Item = Item;
    fn take_simple(&mut self) -> Option<Self::Item> {
        match self {
            Associative::Assoc(ref mut a) => a.take_simple().map(Item::derive),
            Associative::Words(ref mut d) => d.take_simple().map(Item::derive),
            // The remaining impls may require auto-demotion (eg,
            // removing a required field from say, Error). We'll just
            // demote all of them whether the field that is removed is
            // required or not, since the caller cannot know in
            // advance which it will be.
            ref a => {
                let mut assoc: Association = (*a).clone().fit();
                let v = assoc.take_simple().map(Item::derive);
                *self = Associative::Assoc(assoc);
                v
            }
        }
    }
}

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::Words(d) => d.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>) {
        //println!("Insert! {:?}", self);
        match self {
            Associative::Assoc(mut a) => {
                let am = coll::Arc::mutate(&mut a);
                let e = am.insert(k, v);
                (Associative::Assoc(a), e)
            }
            Associative::Words(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.fit(), e).map(Item::derive);
                        (Associative::Words(d), e)
                    } else {
                        // TODO silently failing to insert here is bad
                        println!("Warning, failed to insert into dictionary: {:?}", e2);
                        (Associative::Words(d), None)
                    }
                }
                _ => (Associative::Words(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),
            },
            Associative::Dictionary(mut d) => match k {
                KeyItem::Word(ref w) => {
                    let w: &str = w.fit();
                    if w == "words" {
                        let e = dict::Words::try_derive(v);
                        match e {
                            Ok(words) => {
                                d.words = words;
                                (Associative::Dictionary(d), None) // TODO: return the old entries
                            }
                            Err(_) => (Associative::Dictionary(d), None),
                        }
                    } else if w == "modules" {
                        let l = Vec::<dict::Namespace>::try_derive(v);
                        match l {
                            Ok(modules) => {
                                d.modules = modules;
                                (Associative::Dictionary(d), None) // TODO: return the old modules
                            }
                            Err(_) => (Associative::Dictionary(d), None),
                        }
                    } else {
                        (Associative::Dictionary(d), None)
                    }
                }
                _ => (Associative::Dictionary(d), None),
            },
            _ => todo!("insert Implementations for error, dictionary, 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::Words(mut this), other) => {
                let (word, entry) = <(dict::Word, dict::Entry)>::try_derive(other)?;
                let thismut = this.mutate();
                thismut.insert(word.fit(), entry.fit());
                Ok(Associative::Words(this))
            }
            (this, other) => {
                let entry: (KeyItem, Item) = other.try_fit()?;
                Ok(this.insert(entry.0, entry.1).0)
            }
        }
    }

    /// 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::Dictionary(d) => d.get(k),
            Associative::Error(e) => e.data.get(k).cloned(),
            Associative::Env(e) => e.get(k),
            Associative::DictEntry(d) => d.get(k),
            Associative::Words(d) => match k {
                KeyItem::Word(w) => d.get(&w.clone().fit()).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) => d.contains_key(k),
            Associative::Words(d) => match k {
                KeyItem::Word(w) => d.contains_key(&w.clone().fit()),
                _ => 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::Words(mut d) => {
                let dm = coll::Arc::mutate(&mut d);
                let v = dm.remove(&dict::Word::try_derive(k.clone()).unwrap_or_default());
                (Associative::Words(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"),
        }
    }
}

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) => Box::new(d.into_iter()),
            Associative::Words(d) => {
                let items: Vec<_> = d
                    .iter()
                    .map(|(k, v)| (KeyItem::Word(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.count() != 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 Derive<(KeyItem, Item)> for KeyItem {
    fn derive((k, _): (KeyItem, Item)) -> KeyItem {
        k
    }
}

/// Converting Associative to Set just returns the keys.
impl Derive<Associative> for coll::Set {
    fn derive(a: Associative) -> coll::Set {
        Arc::new(HashSet::from_iter(a.to_iter().map(|(k, _)| k)))
    }
}

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))
    }
}

pub 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,
}

pub trait Nested {
    fn caused(self, other: Error) -> Self;
}

impl<T, E> Nested for Result<T, E>
where
    E: Nested,
{
    fn caused(self, other: Error) -> Self {
        self.map_err(|e| e.caused(other))
    }
}

impl Nested for Error {
    fn caused(self, mut e: Error) -> Error {
        e.data.mutate().insert("cause".fit(), self.fit());
        e
    }
}

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()
    }

    pub fn push(&mut self, key: assoc::KeyItem, value: Item) -> Option<Item> {
        self.data.mutate().insert(key, value)
    }
}

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::associative::Convert;
use crate::types::container::{self as coll, Count, Mutey};
use crate::types::{self, Bytes, Error, Item};
use core::fmt;
use internment::Intern;
use std::collections::HashMap;
use std::collections::HashSet;
use std::convert::Infallible;
use std::hash::Hash;
use std::ptr;
use std::sync::Arc;

/// A word in a dictionary is slightly different than a 'word' piece
/// of data: when looking up words in the dictionary, the namespace is
/// used for comparison. Due to differences in equality checking, we
/// use a wrapper type here so we can distinguish the behavior.
#[derive(Eq, Debug, Clone, Default, PartialEq, Hash)]
pub struct Word(pub types::Word, pub Namespace);

/// Easily convert from [Word]
impl Derive<Word> for types::Word {
    fn derive(w: Word) -> Self {
        w.0
    }
}

/// Easily convert from [types::Word]
impl Derive<types::Word> for Word {
    fn derive(w: types::Word) -> Self {
        Word(w, None)
    }
}

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

impl TryDerive<assoc::KeyItem> for Word {
    type Error = Error;
    fn try_derive(k: assoc::KeyItem) -> Result<Self, Self::Error> {
        Ok(types::Word::try_derive(k)?.fit())
    }
}

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

impl Eq for Entry {}
// 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: types::Word,
    pub name: Option<types::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 = types::Word::try_derive(s.front().unwrap().clone())?;
                    let n = types::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.front().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: &assoc::KeyItem) -> Option<Item> {
        match key {
            assoc::KeyItem::Word(w) => match w.data.as_str() {
                "spec" => self.spec.clone().map(|x| x.fit()),
                "examples" => self.examples.clone().map(|x| x.fit()),
                "definition" => Some(match self.definition.clone() {
                    Definition::Axiom(_) => "builtin".fit(),
                    Definition::Derived(d) => d.fit(),
                }),
                _ => None,
            },
            _ => None,
        }
    }

    pub fn contains_key(&self, key: &assoc::KeyItem) -> bool {
        types::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))
                }
            }
        }
    }
}

/// Holds [Word]s and their definitions.
pub type Words = coll::Arc<HashMap<Word, Entry>>;
/// Words are looked up from the Cache, which takes modules into
/// account.
pub type Cache = HashMap<types::Word, Entry>;

/// One of the main components of an
/// [crate::types::container::environment::Environment]. Provides
/// definitions of words and a resolver, which decides which
/// definition of the same word to use (based on which module it comes
/// from).
#[derive(Clone, PartialEq)]
pub struct Dictionary {
    pub words: Words,
    pub cache: Cache,
    pub modules: Vec<Namespace>,
}

/// A custom impl for Dictionary that doesn't dump a massive data
/// structure. comment this out to get access to the full debug output.
impl fmt::Debug for Dictionary {
    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
        f.debug_struct("Dictionary")
            .field("words", &format_args!("Words(len={})", self.words.len()))
            .field("modules", &self.modules)
            .finish()
    }
}

impl Dictionary {
    /// Treats the [Dictionary] as an associative structure,
    /// returning one of its fields, or [None].
    pub fn get(&self, key: &assoc::KeyItem) -> Option<Item> {
        match key {
            assoc::KeyItem::Word(w) => match w.data.as_str() {
                "words" => Some(self.words.clone().fit()),
                "modules" => Some(self.modules.clone().fit()),
                _ => None,
            },
            _ => None,
        }
    }

    /// Get an [Entry] from the dictionary, doing namespace
    /// resolution.
    pub fn get_entry(&self, key: &types::Word) -> Option<Entry> {
        self.cache.get(key).cloned()
    }

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

    pub fn merge(&mut self, new: Self, namespace: &Namespace) {
        self.words.merge(new.words, namespace);
        //self.resolve();
    }

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

    /// Produce an [Words] map that is pre-resolved using the
    /// modules from this dictionary. Saves computation at runtime
    /// because resolution is already done.
    pub fn resolve(&mut self) {
        fn group_by_namespace(words: &Words) -> HashMap<Namespace, Vec<(types::Word, Entry)>> {
            let mut grouped: HashMap<Namespace, Vec<(types::Word, Entry)>> = HashMap::new();

            for (k, v) in words.iter() {
                grouped
                    .entry(k.1)
                    .or_insert_with(Vec::new)
                    .push((k.0.clone(), v.clone()));
            }

            grouped
        }
        let by_ns = group_by_namespace(&self.words);
        //println!("by namespace: {:?}", by_ns);
        let mut cache = Cache::new();
        // first all the non-namespaced core words that can be overridden
        cache.extend(by_ns.get(&None).cloned().unwrap_or_default());
        for module in self.modules.iter() {
            cache.extend(by_ns.get(module).cloned().unwrap_or_default())
        }

        // println!(
        //     "Cache now selected {} words. modules: {:?}",
        //     cache.len(),
        //     by_ns.keys()
        // );
        //println!("resolve: contains? {:?}", cache.get(&"contains?".fit()));
        self.cache = cache;
        //println!("After resolve: {:?}", self);
    }
}

pub trait Dict {
    /// Returns the difference between this dictionary and a "newer"
    /// one: The additions/updates, and the deletions.
    fn diff(&self, newer: Words) -> (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) -> Result<(), Error>;

    /// 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. Leaves other fields as None to be filled in later.
    fn builtins() -> Self;

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

impl coll::SimpleTake for Words {
    type Item = (Word, Entry);
    fn take_simple(&mut self) -> Option<Self::Item> {
        if let Some(ref k) = self.keys().next().cloned() {
            let dm = self.mutate();
            let v = dm.remove(k).unwrap();
            Some((k.clone(), v))
        } else {
            None
        }
    }
}

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

    fn merge(&mut self, new: Words, namespace: &Namespace) {
        let (adds, deletes) = self.diff(new);
        // add namepaces to the adds and deletes
        //println!("Merge {} adds, {} deletes", adds.len(), deletes.len());

        let adds: Vec<_> = adds
            .into_iter()
            .map(|(mut w, e)| {
                w.1 = *namespace;
                //println!("Adding {:?}", w);
                (w, e)
            })
            .collect();
        let deletes: Vec<_> = deletes
            .into_iter()
            .map(|mut w| {
                w.1 = *namespace;
                w
            })
            .collect();
        let d = self.mutate();

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

        //println!("Contains: {:?}", d.get(&"contains?".fit()))
    }

    fn insert_core_module(&mut self, lexicon: String) -> Result<(), Error> {
        //println!("Parsing: {}", lexicon);
        let items = serialize::parse(lexicon)?;
        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: 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;
                    // Don't overwrite the definition, this should be
                    // an axiom word where we've left the
                    // spec/examples temporarily blank and we're
                    // filling them in now that we've read the
                    // lexicon. The definition is the builtin and we
                    // want to keep that.
                    //e.definition = new_entry.definition;
                })
                .or_insert(new_entry2);
        }
        Ok(())
    }

    fn builtins() -> Self {
        let mut dict = HashMap::new();
        for (bw, bd) in BUILTIN_FUNCTIONS.iter() {
            let entry = Entry {
                definition: bd.clone(),
                examples: None,
                spec: None,
                namespace: None,
            };
            dict.insert(Word::derive(bw.clone()), entry);
        }
        Arc::new(dict)
    }
}

/// 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, Entry)> {
    words
        .into_iter()
        .map(|word| {
            //println!("Shadowing word: {:?}", word);
            let err = Error::create(
                list!(types::Word::derive(word.clone())),
                "word removed by module",
                Some("access-denied"),
            );
            let entry = Entry {
                examples: None,
                spec: None,
                definition: Definition::Derived(list!(err, "fail")),
                namespace: word.1,
            };
            (word, entry)
        })
        .collect()
}

/// Returns an owned pair given a pair of references
fn owned<T: Clone, U: Clone>(entry: (&T, &U)) -> (T, U) {
    (entry.0.clone(), entry.1.clone())
}

/// 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(owned)
        .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)
}

impl coll::Join<Words> for Words {
    type Output = Words;
    type Error = Infallible;
    fn join(mut self, other: Words) -> Result<Self::Output, Self::Error> {
        let sm = self.mutate();
        sm.extend(other.iter().map(owned));
        Ok(self)
    }
}

impl coll::Join<Dictionary> for Dictionary {
    type Output = Dictionary;
    type Error = Infallible;
    fn join(mut self, other: Self) -> Result<Self::Output, Self::Error> {
        self.words = self.words.join(other.words)?;
        Ok(self)
    }
}

impl coll::Join<assoc::Association> for Words {
    type Output = assoc::Associative;
    type Error = Infallible;
    fn join(mut self, other: assoc::Association) -> Result<Self::Output, Self::Error> {
        // Try to convert to dictionary type
        //println!("dict + assoc join");
        match other.convert::<Word, Entry>() {
            Ok(d) => {
                let tm = self.mutate();
                tm.extend(d);
                Ok(assoc::Associative::Words(self))
            }
            // TODO: convert the other way (to assoc) instead
            Err(_) => {
                //println!("Conversion error: {:?}", e);
                Ok(assoc::Associative::Words(self))
            }
        }
    }
}

impl coll::Join<Words> for assoc::Association {
    type Output = assoc::Associative;
    type Error = Infallible;
    fn join(self, mut other: Words) -> Result<Self::Output, Self::Error> {
        // Try to convert to dictionary type
        //println!("assoc + dict join");
        Ok(match self.convert::<Word, Entry>() {
            Ok(d) => {
                let tm = other.mutate();
                tm.extend(d.iter().map(owned));
                assoc::Associative::Words(other)
            }
            // TODO: convert the other way (to assoc) instead
            Err(_) => assoc::Associative::Words(other),
        })
    }
}

/// 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 types::StepFn),
    /// A definition in terms of other [Word]s - a kcats program
    Derived(coll::List),
}

// dictionary words 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 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 {
                Definition::Derived(l) => l.fit(),
                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 IntoIterator for Dictionary {
    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![
            ("words".fit(), self.words.fit()),
            ("modules".fit(), self.modules.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;
        let mut namespace: Namespace = 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 if k == "namespace".fit() {
                namespace = v.try_fit().unwrap_or_default();
            } else {
                continue;
            }
        }
        Ok(Entry {
            examples,
            definition: definition.unwrap_or(Definition::Derived(coll::List::default())),
            spec,
            namespace,
        })
    }
}

impl TryDerive<Box<dyn Iterator<Item = Item>>> for Words {
    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<Box<dyn Iterator<Item = Item>>> for Dictionary {
    type Error = Error;
    fn try_derive(iter: Box<dyn Iterator<Item = Item>>) -> Result<Self, Error> {
        let mut words = Words::default();
        let mut modules = Vec::<Namespace>::default();

        for i in iter {
            let (k, v): (assoc::KeyItem, Item) = i.try_fit()?;
            //println!("k: {:?}, v: {:?}", k, v);
            if k == "words".fit() {
                words = v.try_fit()?;
            } else if k == "modules".fit() {
                modules = v.try_fit()?;
            } else {
                continue;
            }
        }
        Ok(Dictionary {
            words: words,
            modules,
            cache: HashMap::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 Words {
    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::Words(d)) => Ok(d),
            c => c.into_iter().try_fit(),
        }
    }
}

impl TryDerive<Item> for Dictionary {
    type Error = Error;
    fn try_derive(i: Item) -> Result<Self, Self::Error> {
        let s = assoc::Associative::try_derive(i)?;
        match s {
            assoc::Associative::Dictionary(d) => Ok(d),
            //assoc::Associative::Assoc(a) => a.into_iter().try_fit(),
            a => Err(Error::expected("dictionary", a)),
        }
    }
}

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

impl Derive<Words> for Item {
    fn derive(e: Words) -> Self {
        Item::Dispenser(coll::Dispenser::Sized(coll::Sized::Associative(
            assoc::Associative::Words(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.fit()), 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.count() != 2 {
            Err(Error::expected("pair", s))
        } else {
            let mut iter = s.into_iter();
            let key: types::Word = iter.next().unwrap().try_fit()?;
            let value: Entry = iter.next().unwrap().try_fit()?;
            Ok((key.fit(), value))
        }
    }
}