blr-lang 0.1.0

//! Crust is the semantic layer representing the meaning of the program.
//!
//! This layer prioritizes the semantics of the language above all else. It does not preserve the
//! syntax and is primarily focused on inferring and checking types.
//!
//! There is a many to one relation between [`crate::air::Expr`]s to [`Expr`], meaning the same
//! program can be represented with multiple different syntaxes and programs with the same
//! [`Expr`] are identical in behavior.

pub mod builder;
mod infer;
mod inst;
mod sexpr;
mod subst;
mod ty;
mod unification;

mod items;
#[cfg(test)]
mod tests;

pub use items::{ItemId, ItemSource, Symbol};
pub use sexpr::{SExprConfig, SerializationDetail};
pub use ty::{ClosedRow, Row, RowVar, Type, TypeVar};
pub use unification::{TypeError, TypeErrorKind};

use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet};

use subst::SubstOut;
use ty::{RowCombination, RowUniVar, TypeUniVar};

use tracing::{debug, instrument};

use super::air;

use crate::{
    compiler::crust::unification::UnificationTable,
    external_type::{self, ExternalType},
    runtime::binary::{ADDITION, DIVISION, MULTIPLICATION, SUBTRACTION},
    trace_alt,
};

pub type Label = String;

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
pub struct Var(pub usize);

#[derive(PartialEq, Eq, Clone, Hash)]
pub struct TypedVar(pub Var, pub Type);

#[derive(PartialEq, Eq, Clone, Debug, PartialOrd, Ord, Copy, Hash)]
pub struct NodeId(pub u32);

impl std::fmt::Display for NodeId {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        write!(f, "{}", self.0)
    }
}

#[derive(Clone, PartialEq)]
pub struct Module<V> {
    pub items: BTreeMap<ItemId, Item<V>>,
}
#[derive(Clone, PartialEq)]
pub enum Item<V> {
    Native(NativeItem<V>),
    External(ExternalItem),
}

#[derive(Clone, PartialEq)]
pub struct NativeItem<V> {
    pub symbol: Symbol,
    pub abstraction: Expr<V>,
    pub typ: TypeScheme,
}

#[derive(Debug, Clone, PartialEq)]
pub struct ExternalItem {
    pub symbol: Symbol,
    pub scheme: TypeScheme,
    pub external_type: external_type::FunctionType,
}

/// An expression in the intermediate representation of the crust.
/// The representation focuses on unambiguous semantics within a program.
#[derive(Clone, PartialEq)]
pub enum Expr<V> {
    /// An empty literal
    Unit(NodeId),
    /// Integer literal
    Integer(NodeId, i64),
    /// Floating point numeric literal
    Float(NodeId, f64),
    /// String literal
    String(NodeId, String),
    /// Program variable
    Variable(NodeId, V),
    /// Apply an abstraction
    Application {
        id: NodeId,
        abstraction: Box<Self>,
        parameter: Box<Self>,
    },
    /// Abstract an expression by introducing a parameter.
    Abstraction {
        id: NodeId,
        parameter: V,
        body: Box<Self>,
    },
    /// Label an expression
    Label {
        id: NodeId,
        label: Label,
        expr: Box<Self>,
    },
    /// Extract an expression behind a label
    Unlabel {
        id: NodeId,
        expr: Box<Self>,
        label: Label,
    },
    /// Project a production into a sub-product.
    /// NOTE: The sub-product labels are determined via context and not enumerated as part of the
    /// project operation
    Project(NodeId, Box<Self>),
    /// Combine two products into a single product
    Concatenate {
        id: NodeId,
        left: Box<Self>,
        right: Box<Self>,
    },
    // Construct sum from an expressions
    Inject(NodeId, Box<Self>),
    // Deconstruct a sum.
    // Branch is an abstraction from goal -> 'a
    Branch {
        id: NodeId,
        left: Box<Self>,
        right: Box<Self>,
    },
    /// A reference to a top level abstraction. Items differ from normal abstractions in that they are
    /// let-polymorphic.
    Item(NodeId, ItemId, Symbol),
}

impl<V> Expr<V> {
    pub fn id(&self) -> NodeId {
        match self {
            Expr::Unit(id)
            | Expr::Variable(id, _)
            | Expr::Integer(id, _)
            | Expr::Float(id, _)
            | Expr::String(id, _)
            | Expr::Abstraction { id, .. }
            | Expr::Application { id, .. }
            | Expr::Label { id, .. }
            | Expr::Unlabel { id, .. }
            | Expr::Project(id, _)
            | Expr::Concatenate { id, .. }
            | Expr::Inject(id, _)
            | Expr::Branch { id, .. }
            | Expr::Item(id, _, _) => *id,
        }
    }

    pub fn variable(id: NodeId, var: V) -> Self {
        Self::Variable(id, var)
    }
    pub fn abstraction(id: NodeId, parameter: V, body: Self) -> Self {
        Self::Abstraction {
            id,
            parameter,
            body: Box::new(body),
        }
    }

    pub fn application(id: NodeId, abstraction: Self, parameter: Self) -> Self {
        Self::Application {
            id,
            abstraction: Box::new(abstraction),
            parameter: Box::new(parameter),
        }
    }

    pub fn label(id: NodeId, label: impl ToString, expr: Self) -> Self {
        Self::Label {
            id,
            label: label.to_string(),
            expr: Box::new(expr),
        }
    }

    pub fn unlabel(id: NodeId, expr: Self, label: impl ToString) -> Self {
        Self::Unlabel {
            id,
            expr: Box::new(expr),
            label: label.to_string(),
        }
    }

    pub fn project(id: NodeId, expr: Self) -> Self {
        Self::Project(id, Box::new(expr))
    }

    pub fn concatenate(id: NodeId, left: Self, right: Self) -> Self {
        Self::Concatenate {
            id,
            left: Box::new(left),
            right: Box::new(right),
        }
    }

    pub fn inject(id: NodeId, expr: Self) -> Self {
        Self::Inject(id, Box::new(expr))
    }
    pub fn branch(id: NodeId, left: Self, right: Self) -> Self {
        Self::Branch {
            id,
            left: Box::new(left),
            right: Box::new(right),
        }
    }
}

/// Lowers an [`air::Expr`] into an [`Expr`] desugaring the syntax leaving only the semantics of
/// the expression.
pub fn lower(module: air::Module, item_source: &mut ItemSource, module_path: &str) -> Module<Var> {
    // Add local items to the item source, this enables recursion as a local item is available to
    // itself.
    let items: Vec<_> = module
        .items
        .into_iter()
        .map(|item| {
            (
                item_source.register(
                    Symbol {
                        module: item.symbol().module.clone(),
                        field: item.symbol().field.clone(),
                    },
                    // TODO: Avoid clone
                    lower_typ(air::TypeExpr::Fun(item.typ().clone())),
                ),
                item,
            )
        })
        .collect();
    trace_alt!(symbols = item_source.symbols(), "symbols");
    trace_alt!(types = item_source.types(), "types");
    let mut lower = Lower::new(&module.imports, item_source);
    let items = items
        .into_iter()
        .map(|(id, item)| match item {
            air::Item::Native(item) => {
                let mut env = Default::default();
                (
                    id,
                    Item::Native(NativeItem {
                        symbol: Symbol {
                            module: item.symbol.module,
                            field: item.symbol.field,
                        },
                        abstraction: lower.lower(air::Expr::Function(item.function), &mut env),
                        typ: item_source.type_of_item(id),
                    }),
                )
            }
            air::Item::External(item) => (
                id,
                Item::External(ExternalItem {
                    symbol: Symbol {
                        // External items use a component module path.
                        // HACK? Can we type this safely so we don't cross different types of
                        // module paths?
                        module: module_path.to_string(),
                        field: item.symbol.field,
                    },
                    scheme: item_source.type_of_item(id),
                    external_type: match convert_ext_typ(air::TypeExpr::Fun(item.typ), None) {
                        ExternalType::Fun(function_type) => function_type,
                        _ => panic!("external item should be a function type"),
                    },
                }),
            ),
        })
        .collect();
    Module { items }
}

#[instrument(ret(level=tracing::Level::TRACE))]
fn lower_typ(typ_expr: air::TypeExpr) -> TypeScheme {
    let mut evidence = Default::default();
    let mut var_supply = VarSupply::default();
    let mut row_supply = RowVarSupply::default();
    let typ = _lower_typ(typ_expr, &mut var_supply, &mut row_supply, &mut evidence);
    TypeScheme {
        unbound_rows: row_supply.names.into_values().collect(),
        unbound_tys: var_supply.names.into_values().collect(),
        evidence,
        typ,
    }
}

fn _lower_typ(
    typ_expr: air::TypeExpr,
    var_supply: &mut VarSupply,
    row_supply: &mut RowVarSupply,
    evidence: &mut Vec<Evidence>,
) -> Type {
    match typ_expr {
        air::TypeExpr::Unit => Type::Unit,
        air::TypeExpr::Int => Type::Int,
        air::TypeExpr::Float => Type::Float,
        air::TypeExpr::String => Type::String,
        air::TypeExpr::Var(name) => Type::Var(var_supply.supply_for(name)),
        air::TypeExpr::Fun(air::FunctionType {
            parameter_names: _,
            parameter_typs,
            ret,
        }) => Type::abstractions(
            parameter_typs
                .into_iter()
                .map(|param| _lower_typ(param, var_supply, row_supply, evidence))
                .collect::<Vec<_>>(),
            _lower_typ(*ret, var_supply, row_supply, evidence),
        ),
        air::TypeExpr::Prod(row) => Type::Prod(lower_row(row, var_supply, row_supply, evidence)),
        air::TypeExpr::Sum(row) => Type::Sum(lower_row(row, var_supply, row_supply, evidence)),
        air::TypeExpr::Nominal(_name, typ) => _lower_typ(*typ, var_supply, row_supply, evidence),
        air::TypeExpr::DataFrame => Type::DataFrame,
    }
}

fn lower_row(
    mut row: air::Row,
    var_supply: &mut VarSupply,
    row_supply: &mut RowVarSupply,
    evidence: &mut Vec<Evidence>,
) -> Row {
    row.fields.sort_by(|a, b| a.0.cmp(&b.0));
    let (fields, values) = row
        .fields
        .into_iter()
        .map(|(label, field_typ)| {
            (
                label,
                _lower_typ(field_typ, var_supply, row_supply, evidence),
            )
        })
        .unzip();
    Row::Closed(ClosedRow { fields, values })
}

fn convert_ext_typ(typ_expr: air::TypeExpr, name: Option<String>) -> ExternalType {
    match typ_expr {
        air::TypeExpr::Unit => ExternalType::Unit,
        air::TypeExpr::Int => ExternalType::Int,
        air::TypeExpr::Float => ExternalType::Float,
        air::TypeExpr::String => ExternalType::String,
        air::TypeExpr::DataFrame => ExternalType::Resource("data-frame".to_string()),
        air::TypeExpr::Var(_) => panic!("external types cannot be polymorphic"),
        air::TypeExpr::Fun(air::FunctionType {
            parameter_names,
            parameter_typs,
            ret,
        }) => ExternalType::Fun(crate::external_type::FunctionType {
            parameter_names,
            parameter_typs: parameter_typs
                .into_iter()
                .map(|param| convert_ext_typ(param, None))
                .collect::<Vec<_>>(),
            ret: Box::new(convert_ext_typ(*ret, None)),
        }),
        air::TypeExpr::Prod(row) => ExternalType::Record(
            // TODO Add error handling as this is user error
            name.expect("external record types should be named"),
            row.fields
                .into_iter()
                .map(|(label, field_typ)| (label, convert_ext_typ(field_typ, None)))
                .collect(),
        ),
        air::TypeExpr::Nominal(name, typ) => convert_ext_typ(*typ, Some(name)),
        air::TypeExpr::Sum(_row) => todo!(),
    }
}

#[derive(Debug, Default)]
struct VarSupply {
    next: u32,
    names: HashMap<String, TypeVar>,
}
impl VarSupply {
    fn supply_for(&mut self, name: String) -> TypeVar {
        *self.names.entry(name).or_insert_with(|| {
            let id = self.next;
            self.next += 1;
            TypeVar(id)
        })
    }
}
#[derive(Debug, Default)]
#[allow(dead_code)]
struct RowVarSupply {
    next: u32,
    names: HashMap<String, RowVar>,
}
impl RowVarSupply {
    #[allow(dead_code)]
    fn supply_for(&mut self, name: String) -> RowVar {
        *self.names.entry(name).or_insert_with(|| {
            let id = self.next;
            self.next += 1;
            RowVar(id)
        })
    }
}

struct Lower<'a> {
    next_node_id: u32,
    next_var: usize,
    imports: &'a Vec<air::Import>,
    item_source: &'a ItemSource,
}

impl<'a> Lower<'a> {
    fn new(imports: &'a Vec<air::Import>, item_source: &'a ItemSource) -> Self {
        Self {
            next_node_id: 0,
            next_var: 0,
            imports,
            item_source,
        }
    }
    fn new_node_id(&mut self) -> NodeId {
        let id = self.next_node_id;
        self.next_node_id += 1;
        NodeId(id)
    }
    fn bind(&mut self, name: String, env: &mut im::HashMap<String, Var>) -> Var {
        let var = Var(self.next_var);
        self.next_var += 1;
        env.insert(name, var);
        var
    }
    #[allow(dead_code)]
    fn bind_for(&mut self, name: String, var: Var, env: &mut im::HashMap<String, Var>) {
        env.insert(name, var);
    }
    fn fresh_var(&mut self) -> Var {
        let var = Var(self.next_var);
        self.next_var += 1;
        var
    }
    fn lookup(&mut self, name: &str, env: &im::HashMap<String, Var>) -> Expr<Var> {
        // A variable can reference either a value in scope or an item
        env.get(name)
            .map(|var| Expr::Variable(self.new_node_id(), *var))
            .unwrap_or_else(|| {
                let (symbol, item_id) = self
                    .item_source
                    .symbols()
                    .iter()
                    .find(|(symbol, _item_id)| symbol.field == name)
                    .unwrap_or_else(|| panic!("variable should be defined {name}"));
                Expr::Item(self.new_node_id(), *item_id, symbol.clone())
            })
    }

    fn lower(&mut self, ast: air::Expr, env: &mut im::HashMap<String, Var>) -> Expr<Var> {
        match ast {
            air::Expr::Unit => Expr::Unit(self.new_node_id()),
            air::Expr::Integer(i) => Expr::Integer(self.new_node_id(), i),
            air::Expr::Float(f) => Expr::Float(self.new_node_id(), f),
            air::Expr::Variable(name) => self.lookup(&name, env),
            air::Expr::String(s) => Expr::String(self.new_node_id(), s),
            air::Expr::Let {
                pattern,
                init,
                body,
            } => {
                let init = self.lower(*init, env);
                self.lower_pattern_binding(pattern, init, *body, env)
            }
            air::Expr::Function(air::Function { parameters, body }) => {
                let mut env = env.clone();
                parameters.iter().for_each(|parameter| {
                    self.bind(parameter.clone(), &mut env);
                });
                //TODO: Do not special case empty parameters, either require a paramter or find a
                //different solution.
                if parameters.is_empty() {
                    Expr::abstraction(
                        self.new_node_id(),
                        self.bind("_".to_string(), &mut env),
                        self.lower(*body, &mut env),
                    )
                } else {
                    parameters
                        .into_iter()
                        .rfold(self.lower(*body, &mut env), |abs, parameter| {
                            Expr::abstraction(
                                self.new_node_id(),
                                *env.get(&parameter)
                                    .expect("abstraction parameters should be bound"),
                                abs,
                            )
                        })
                }
            }
            air::Expr::Variant(label, expr) => Expr::inject(
                self.new_node_id(),
                Expr::label(self.new_node_id(), label, self.lower(*expr, env)),
            ),
            air::Expr::Match(scrutinee, mut cases) => {
                let (pattern, body) = cases.pop().unwrap();
                Expr::application(
                    self.new_node_id(),
                    cases.into_iter().fold(
                        {
                            let var = self.fresh_var();
                            let init = Expr::variable(self.new_node_id(), var);
                            Expr::abstraction(
                                self.new_node_id(),
                                var,
                                self.lower_pattern_binding(pattern, init, body, env),
                            )
                        },
                        |left, (pattern, body)| {
                            let var = self.fresh_var();
                            let init = Expr::variable(self.new_node_id(), var);
                            Expr::branch(
                                self.new_node_id(),
                                left,
                                Expr::abstraction(
                                    self.new_node_id(),
                                    var,
                                    self.lower_pattern_binding(pattern, init, body, env),
                                ),
                            )
                        },
                    ),
                    self.lower(*scrutinee, env),
                )
            }
            air::Expr::Binary { left, op, right } => {
                let left = self.lower(*left, env);
                let right = self.lower(*right, env);
                let mut bin_op_application = |var, left, right| {
                    Expr::application(
                        self.new_node_id(),
                        Expr::application(self.new_node_id(), self.lookup(var, env), left),
                        right,
                    )
                };
                match op {
                    air::BinaryOperator::Addition => bin_op_application(ADDITION, left, right),
                    air::BinaryOperator::Subtraction => {
                        bin_op_application(SUBTRACTION, left, right)
                    }
                    air::BinaryOperator::Multiplication => {
                        bin_op_application(MULTIPLICATION, left, right)
                    }
                    air::BinaryOperator::Division => bin_op_application(DIVISION, left, right),
                    air::BinaryOperator::Concat => {
                        Expr::concatenate(self.new_node_id(), left, right)
                    }
                }
            }
            air::Expr::Forward { parameter, call } => Expr::application(
                self.new_node_id(),
                self.lower(*call, env),
                self.lower(*parameter, env),
            ),
            air::Expr::Application {
                function,
                parameters,
            } => {
                parameters
                    .into_iter()
                    .fold(self.lower(*function, env), |abstraction, parameter| {
                        Expr::application(
                            self.new_node_id(),
                            abstraction,
                            self.lower(parameter, env),
                        )
                    })
            }
            air::Expr::Record { fields } => {
                let mut fields = fields.into_iter();
                if let Some((label, expr)) = fields.next() {
                    let first = Expr::label(self.new_node_id(), label, self.lower(expr, env));
                    fields.fold(first, |left, (label, expr)| {
                        Expr::concatenate(
                            self.new_node_id(),
                            left,
                            Expr::label(self.new_node_id(), label, self.lower(expr, env)),
                        )
                    })
                } else {
                    unreachable!("should always be at least one field in a record")
                }
            }
            air::Expr::RecordSelect { record, label } => Expr::unlabel(
                self.new_node_id(),
                Expr::project(self.new_node_id(), self.lower(*record, env)),
                label,
            ),
            air::Expr::Parenthesized(expr) => self.lower(*expr, env),
            air::Expr::Item(symbol) => {
                // HACK, build real path parsing
                let import = self
                    .imports
                    .iter()
                    .find(|import| {
                        if let Some((_, tail)) = import.path.rsplit_once("::") {
                            tail == symbol.module
                        } else {
                            import.path == symbol.module
                        }
                    })
                    .unwrap_or_else(|| panic!("item import not found {:?}", symbol));
                let symbol = Symbol {
                    module: import.path.clone(),
                    field: symbol.field.clone(),
                };
                let item_id = self.item_source.resolve(&symbol);
                Expr::Item(self.new_node_id(), item_id, symbol.clone())
            }
        }
    }

    fn lower_pattern_binding(
        &mut self,
        pattern: air::Pattern,
        init: Expr<Var>,
        body: air::Expr,
        env: &mut im::HashMap<String, Var>,
    ) -> Expr<Var> {
        match pattern {
            air::Pattern::Identifier(name) => {
                let mut env = env.clone();
                let var = self.bind(name, &mut env);
                let body = self.lower(body, &mut env);
                Expr::application(
                    self.new_node_id(),
                    Expr::abstraction(self.new_node_id(), var, body),
                    init,
                )
            }
            air::Pattern::Variant(label, pattern) => {
                let init = Expr::unlabel(self.new_node_id(), init, label);
                self.lower_pattern_binding(*pattern, init, body, env)
            }
        }
    }
}

#[derive(PartialEq, Eq, Hash, Clone)]
pub struct ItemWrapper {
    pub types: Vec<Type>,
    pub rows: Vec<Row>,
    pub evidence: Vec<Evidence>,
}

/// Our constraints
/// Right now this is just type equality but it will be more substantial later
#[derive(Debug, PartialEq, Eq, Clone)]
pub enum Constraint {
    TypeEqual(NodeId, Type, Type),
    RowCombine(NodeId, RowCombination),
}

/// Type inference
/// This struct holds some commong state that will useful to share between our stages of type
/// inference.
#[derive(Default)]
pub struct TypeInference {
    unification_table: UnificationTable<TypeUniVar>,
    row_unification_table: UnificationTable<RowUniVar>,
    partial_row_combs: BTreeSet<RowCombination>,
    item_source: ItemSource,

    row_to_ev: HashMap<NodeId, RowCombination>,
    branch_to_ret_typ: HashMap<NodeId, Type>,

    item_wrappers: BTreeMap<NodeId, ItemWrapper>,
    subst_unifiers_to_tyvars: HashMap<TypeUniVar, TypeVar>,
    next_tyvar: u32,
    subst_unifiers_to_rowvars: HashMap<RowUniVar, RowVar>,
    next_rowvar: u32,
}
impl TypeInference {
    fn normalize_mentioned_row_combs<T>(
        &mut self,
        subst_out: SubstOut<T>,
    ) -> SubstOut<(T, Vec<Evidence>)> {
        let mut subst_out = subst_out.map(|t| (t, vec![]));
        for norm_row_comb in std::mem::take(&mut self.partial_row_combs)
            .into_iter()
            .map(|row_comb| self.substitute_row_comb(row_comb))
        {
            if norm_row_comb
                .unbound_tys
                .intersection(&subst_out.unbound_tys)
                .next()
                .is_some()
                || norm_row_comb
                    .unbound_rows
                    .intersection(&subst_out.unbound_rows)
                    .next()
                    .is_some()
            {
                subst_out = subst_out.merge(norm_row_comb, |(t, mut evidences), ev| {
                    evidences.push(ev);
                    (t, evidences)
                })
            }
        }
        subst_out
    }
}

/// Evidence holds information about types in scope.
/// With the evidence we can construct type safe functions over values and ultimatley erase types
/// before runtime.
#[derive(Debug, Clone, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub enum Evidence {
    /// RowEquation holds enough information about a row so that operations over product and sums
    /// types can be generated.
    RowEquation { left: Row, right: Row, goal: Row },
}

#[derive(Debug, PartialEq, Eq, Clone)]
pub struct TypeScheme {
    pub unbound_rows: BTreeSet<RowVar>,
    pub unbound_tys: BTreeSet<TypeVar>,
    pub evidence: Vec<Evidence>,
    pub typ: Type,
}

#[derive(PartialEq, Clone)]
pub enum TypedItem {
    Native(TypedNativeItem),
    External(ExternalItem),
}
#[derive(PartialEq, Clone)]
pub struct TypedNativeItem {
    pub symbol: Symbol,
    pub typed_expr: Expr<TypedVar>,
    pub scheme: TypeScheme,
    pub row_to_ev: BTreeMap<NodeId, Evidence>,
    pub branch_to_ret_typ: BTreeMap<NodeId, Type>,
    pub item_wrappers: BTreeMap<NodeId, ItemWrapper>,
}

#[derive(PartialEq, Clone)]
pub struct TypedModule {
    pub items: BTreeMap<ItemId, TypedItem>,
}

pub fn type_infer_with_items(
    item_source: ItemSource,
    module: Module<Var>,
) -> Result<TypedModule, TypeError> {
    let mut ctx = TypeInference {
        item_source,
        ..Default::default()
    };

    // Constraint generation
    let typed_items = module
        .items
        .into_iter()
        .map(|(id, item)| {
            match item {
                Item::Native(item) => {
                    let env = im::HashMap::default();
                    let symbol = item.symbol.clone();

                    let (out, typ) = ctx.infer_item(env, item);
                    trace_alt!(out, "constraints generated");

                    // Constraint solving
                    ctx.unification(out.constraints)?;
                    trace_alt!(
                        unification = ctx.unification_table,
                        row_unification = ctx.row_unification_table,
                        "unification solution"
                    );

                    // Apply our substition to our inferred types
                    let subst_out = ctx
                        .substitute_ty(typ)
                        .merge(ctx.substitute_expr(out.typed_expr), |ty, expr| (ty, expr));
                    trace_alt!(subst = subst_out, row_to_ev = ctx.row_to_ev, "substition");

                    let mut evidence_subst = ctx.normalize_mentioned_row_combs(subst_out);
                    trace_alt!(normal_subst = evidence_subst, "normalized substition");

                    let row_to_ev: BTreeMap<_, _> = std::mem::take(&mut ctx.row_to_ev)
                        .into_iter()
                        .map(|(id, combo)| {
                            let out = ctx.substitute_row_comb(combo);
                            evidence_subst.unbound_rows.extend(out.unbound_rows);
                            evidence_subst.unbound_tys.extend(out.unbound_tys);
                            (id, out.value)
                        })
                        .collect();
                    let item_wrappers = std::mem::take(&mut ctx.item_wrappers)
                        .into_iter()
                        .map(|(id, wrapper)| {
                            let out = ctx.substitute_wrapper(wrapper);
                            evidence_subst.unbound_rows.extend(out.unbound_rows);
                            evidence_subst.unbound_tys.extend(out.unbound_tys);
                            (id, out.value)
                        })
                        .collect();
                    let branch_to_ret_typ = std::mem::take(&mut ctx.branch_to_ret_typ)
                        .into_iter()
                        .map(|(id, typ)| {
                            debug!(?typ, "branch_to_ret_typ");
                            let out = ctx.substitute_ty(typ);
                            evidence_subst.unbound_rows.extend(out.unbound_rows);
                            evidence_subst.unbound_tys.extend(out.unbound_tys);
                            (id, out.value)
                        })
                        .collect();

                    // Return our typed expr and it's type scheme
                    let ((ty, expr), evidence) = evidence_subst.value;
                    let scheme = TypeScheme {
                        unbound_rows: evidence_subst.unbound_rows,
                        unbound_tys: evidence_subst.unbound_tys,
                        evidence,
                        typ: ty,
                    };
                    trace_alt!(symbol, scheme, "typed item");
                    Ok((
                        id,
                        TypedItem::Native(TypedNativeItem {
                            symbol,
                            typed_expr: expr,
                            scheme,
                            row_to_ev,
                            branch_to_ret_typ,
                            item_wrappers,
                        }),
                    ))
                }
                Item::External(external_item) => Ok((id, TypedItem::External(external_item))),
            }
        })
        .collect::<Result<_, _>>()?;

    Ok(TypedModule { items: typed_items })
}

#[allow(dead_code)]
fn type_check(expr: Expr<Var>, signature: TypeScheme) -> Result<TypedNativeItem, TypeError> {
    type_check_with_items(ItemSource::default(), expr, signature)
}

#[allow(dead_code)]
fn type_check_with_items(
    item_source: ItemSource,
    expr: Expr<Var>,
    signature: TypeScheme,
) -> Result<TypedNativeItem, TypeError> {
    let mut ctx = TypeInference {
        item_source,
        next_tyvar: signature
            .unbound_tys
            .iter()
            .max()
            .map(|tv| tv.0 + 1)
            .unwrap_or(0),
        next_rowvar: signature
            .unbound_rows
            .iter()
            .max()
            .map(|rv| rv.0 + 1)
            .unwrap_or(0),
        ..Default::default()
    };

    let id = expr.id();
    // Constraint generation
    let mut out = ctx.check(im::HashMap::default(), expr, signature.typ.clone());

    // Add any evidence in our type annotation to be used during solving
    out.constraints
        .extend(signature.evidence.iter().map(|ev| match ev {
            Evidence::RowEquation { left, right, goal } => Constraint::RowCombine(
                id,
                RowCombination {
                    left: left.clone(),
                    right: right.clone(),
                    goal: goal.clone(),
                },
            ),
        }));

    // Constraint solving
    ctx.unification(out.constraints)?;

    // Apply our substition to our expr
    let subst_out = ctx.substitute_expr(out.typed_expr);

    // Here we have to make sure we didn't invent new constraints or types
    // during unification, and if we did that's an error.
    let mut evidence_subst = ctx.normalize_mentioned_row_combs(subst_out);
    let row_to_ev = std::mem::take(&mut ctx.row_to_ev)
        .into_iter()
        .map(|(id, combo)| {
            let out = ctx.substitute_row_comb(combo);
            evidence_subst.unbound_rows.extend(out.unbound_rows);
            evidence_subst.unbound_tys.extend(out.unbound_tys);
            (id, out.value)
        })
        .collect();
    let item_wrappers = std::mem::take(&mut ctx.item_wrappers)
        .into_iter()
        .map(|(id, wrapper)| {
            let out = ctx.substitute_wrapper(wrapper);
            evidence_subst.unbound_rows.extend(out.unbound_rows);
            evidence_subst.unbound_tys.extend(out.unbound_tys);
            (id, out.value)
        })
        .collect();
    let branch_to_ret_ty = std::mem::take(&mut ctx.branch_to_ret_typ)
        .into_iter()
        .map(|(id, ty)| {
            let out = ctx.substitute_ty(ty);
            evidence_subst.unbound_rows.extend(out.unbound_rows);
            evidence_subst.unbound_tys.extend(out.unbound_tys);
            (id, out.value)
        })
        .collect();
    let (expr, evs) = evidence_subst.value;

    let extra_types = evidence_subst
        .unbound_tys
        .difference(&signature.unbound_tys)
        .copied()
        .collect::<Vec<_>>();
    let extra_row = evidence_subst
        .unbound_rows
        .difference(&signature.unbound_rows)
        .copied()
        .collect::<Vec<_>>();

    let sig_evs = signature.evidence.iter().cloned().collect::<HashSet<_>>();
    let extra_evidence = evs
        .into_iter()
        .collect::<HashSet<_>>()
        .difference(&sig_evs)
        .cloned()
        .collect::<Vec<_>>();
    if !extra_types.is_empty() || !extra_row.is_empty() || !extra_evidence.is_empty() {
        return Err(TypeError {
            kind: TypeErrorKind::CheckIntroducedExtraVariablesOrConstraints {
                extra_types,
                extra_row,
                extra_evidence,
            },
            node_id: id,
        });
    }

    Ok(TypedNativeItem {
        symbol: Symbol {
            module: "".to_string(),
            field: "".to_string(),
        },
        typed_expr: expr,
        scheme: signature,
        row_to_ev,
        branch_to_ret_typ: branch_to_ret_ty,
        item_wrappers,
    })
}

pub use sexpr::{parse_expr, parse_module};