mice 0.11.1

//! An IR language to lower dice programs to, with the goal of permitting more complex dice operators.
//!
//! Design goals include:
//! - Providing a good backend for end-user custom logic
//! - Supporting a slow runtime mode that keeps many intermediate results
//!   for the purpose of end-user visible textual output
//! - Supporting a fast runtime mode for statistical sampling and analysis
//!
//! These are both currently implemented in the [`interp`](crate::interp) and
//! [`stack`](crate::stack) modules, and supporting these use cases is a
//! requirement for a shift to this IR.
//!
//! And we have possible stretch goals of:
//! - Supporting a possibly slow*er* runtime mode that keeps *all* intermediate
//!   results for the purpose of end-user visible 3D dice roll animations
//!   (this one's outside of my use case, but this IR shouldn't stand in the way of doing that)
//! - Supporting a JIT compiled runtime mode for *faster* statistical sampling and analysis
//! - Supporting a GPU based backend for *even faster* statistical sampling and analysis
mod check;
pub mod fmt;
#[cfg(feature = "script")]
mod misp;
pub mod opt;
pub mod stack;
mod viz;
use fmt::{Annotation, FmtNode};

use crate::parse::Term;
use ::id_arena::{Arena, Id};

// I need a MIR abstraction for dice roll.
// The input dice language will have some coercions,
// but those should ideally be made explicit during lowering.
// There should be some minor type inference on operators, but
// since all input data is given in literals, it should be fairly simple.
// So, MIR should be fully typed, and then type checked.

// List of coercions in the input dice language:
//   DiceRoll -> DiceResult
//   DiceResult -> i64
// Coercions `a -> b` occur when an operator that accepts `b`, but not `a`, is given
// an argument of type `a`.

#[derive(Debug, ::mbot_proc_macro_helpers::Bytecode)]
enum Sign {
    /// Positive filter: Choosing what to keep.
    Positive,
    /// Negative filter: Choosing what to drop.
    Negative,
}

#[derive(Debug, Clone)]
enum Filter {
    Simple(FilterKind),
    /// `(Integer -> Boolean)` → Keep elements of the set that satisfy
    /// the argument predicate.
    SatisfiesPredicate,
}

/// Particular kinds of set filter.
#[derive(Debug, Copy, Clone, ::mbot_proc_macro_helpers::Bytecode)]
enum FilterKind {
    /// `N` → Keep the highest `N` elements of a set.
    KeepHigh,
    /// `N` → Keep the lowest `N` elements of a set.
    KeepLow,
    /// `N` → Drop the highest `N` elements of a set.
    DropHigh,
    /// `N` → Drop the lowest `N` elements of a set.
    DropLow,
}
impl FilterKind {
    // This will be used to determine whether we highlight what is kept, or
    // cross out what is removed.
    /// Whether the filter operates by choosing which dice to keep,
    /// or by choosing which dice to throw away.
    #[allow(dead_code)]
    fn sign(&self) -> Sign {
        use FilterKind::*;
        match self {
            KeepHigh => Sign::Positive,
            KeepLow => Sign::Positive,
            DropHigh => Sign::Negative,
            DropLow => Sign::Negative,
        }
    }
}

/// Coercions, left implicit in the AST but explicit in MIR.
#[derive(Debug, Clone)]
enum Coercion {
    FromOutputToInt,
}

#[derive(Debug, Clone)]
enum Type {
    Output,
    Integer,
    Boolean,
}

#[derive(Debug, Clone)]
enum BinaryOp {
    Add,
    Subtract,
    #[allow(dead_code)]
    LogicalAnd,
}

#[derive(Copy, Clone, Debug, ::mbot_proc_macro_helpers::Bytecode)]
enum Comparison {
    Equal,
    GreaterThan,
}

/// A *region*, as in RVSDG.
#[derive(Debug, Clone)]
struct Region {
    graph: MirGraph,
    end: NodeIndex,
}

/// A dice program lowered to a graph structure based on RVSDG.
#[derive(Debug)]
pub struct Mir {
    graph: MirGraph,
    top: NodeIndex,
}
impl Mir {
    pub fn size(&self) -> usize {
        use ::core::mem::size_of;
        (self.graph.node_count() * size_of::<MirNode>())
            + (self.graph.edge_count() * size_of::<MirEdge>())
    }
    pub fn print_externals(&self) {
        for node in self.graph.externals(::petgraph::Direction::Incoming) {
            println!("Incoming: {:?}", self.graph[node]);
        }
        for node in self.graph.externals(::petgraph::Direction::Outgoing) {
            println!("Outgoing: {:?}", self.graph[node]);
        }
    }
}

fn mir_type_of(graph: &MirGraph, node: NodeIndex) -> Type {
    // Note that this should not perform type inference for the more complex nodes.
    // The more complex nodes should simply have their types saved somewhere.
    // The MIR is meant to be an IR in which all types are known statically.
    match graph[node] {
        MirNode::Integer(_) => Type::Integer,
        MirNode::Coerce(Coercion::FromOutputToInt) => Type::Integer,
        MirNode::Roll => Type::Output,
        MirNode::BinOp(BinaryOp::Add | BinaryOp::Subtract) => Type::Integer,
        MirNode::BinOp(BinaryOp::LogicalAnd) => Type::Boolean,
        MirNode::Filter(_) => Type::Output,
        MirNode::Compare(_) => Type::Boolean,
        MirNode::Count => Type::Integer,
        MirNode::Apply => todo!("type of function application"),
        MirNode::PartialApply => todo!("type of partial function application"),
        MirNode::Loop(_, ref ty) => ty.clone(),
        MirNode::Decision(_) => todo!("type of if/switch expressions"),
        MirNode::FunctionDefinition(_) => todo!("type of function declaration"),
        MirNode::RecursiveEnvironment(_) => todo!("type of recursive environment"),
        MirNode::RegionArgument(_) => todo!("type of region argument"),
        MirNode::End => todo!("type of region end"),
        MirNode::Fmt(_) => todo!("type of fmt node"),
        MirNode::UseFuel(_) => todo!("type of UseFuel"),
    }
}

// /// Attempt to coerce a node's result to a given type.
// /// Succeeds by identity if the node is already of the type given.
// fn mir_coerce_to(graph: &mut MirGraph, node: NodeIndex, ty: Type) -> Option<NodeIndex> {
//     macro_rules! coerce {
//         ($coercion:ident) => {{
//             let coercion = graph.add_node(MirNode::Coerce(Coercion :: $coercion));
//             graph.add_edge(coercion, node, MirEdge::DataDependency { port: 0 });
//             coercion
//         }}
//     }
//     match (ty, mir_type_of(&*graph, node)) {
//         (Type::Output, Type::Output) => Some(node),
//         // There is no way to coerce an integer back into a collection of dice output.
//         (Type::Output, Type::Integer) => None,
//         (Type::Output, Type::Boolean) => None,
//         (Type::Integer, Type::Output) => Some(coerce!(FromOutputToInt)),
//         (Type::Integer, Type::Integer) => Some(node),
//         (Type::Integer, Type::Boolean) => None,
//         // There are no coercions to or from booleans.
//         (Type::Boolean, _) => None,
//     }
// }

// Typechecking should occur at MIR construction time.
// In particular, only valid coercions should be inserted.
//
// The MIR takes the form of an acyclic data dependency graph.
// At most, permit structured control flow via regions as in RVSDG.
// Ideally, we would only permit terminating programs to be constructed,
// but dice explosions make that tricky. However, there's no reason we couldn't
// encode evaluation fuel in the graph itself, right?
// That way guaranteed termination remains encoded in the program representation.
// Unfortunately, if we want to share evaluation fuel fairly across all explosions
// in an expression, the program representation cannot be a tree- it requires something
// like the state edges in RVSDG (which would probably be filled in left to right).
// Without a tree representation, making a recursive interpreter will be
// trickier, to say the least.

/// A node in the MIR data dependency graph.
#[derive(Debug, Clone)]
enum MirNode {
    /// Integer constants.
    Integer(i64),
    /// Type conversions that are left implicit in
    /// input dice expressions.
    Coerce(Coercion),
    // TODO: generalize over dice roll kinds?
    /// A single dice term, `NdN`.
    Roll,
    /// Some basic operations that take two arguments
    /// and whose return types match their input types.
    BinOp(BinaryOp),
    /// Set filtering operations.
    Filter(Filter),
    /// Integer comparison operations.
    Compare(Comparison),
    /// Count the elements of a set.
    Count,
    /// Function application.
    #[allow(dead_code)]
    Apply,
    /// The building block for compile time erasable closures.
    /// This node kind takes a function and some arguments, and returns
    /// a new function that acts like the argument function, with
    /// the given arguments already bound.
    /// Despite this node kind existing, functions are not true values
    /// and cannot be stored in containers that can store values.
    /// Functions given to `Apply` or `FilterSatisfies` are *required* to be
    /// resolvable at compile time.
    PartialApply,
    // These contain *regions*, as in RVSDG.
    // TODO: Both of these need to have an explicit type attached.
    /// Known as a "Theta" node in the RVSDG paper.
    Loop(Region, Type),
    /// Known as a "Gamma" node in the RVSDG paper.
    #[allow(dead_code)]
    Decision(Vec<Region>),
    /// Known as a "Lambda" node in the RVSDG paper.
    FunctionDefinition(Region),
    /// Known as a "Phi" node in the RVSDG paper.
    #[allow(dead_code)]
    RecursiveEnvironment(Region),
    /// A special node that retrieves an argument of the containing region.
    /// We use this because [`petgraph`] doesn't support representing
    /// RVSDGs completely faithfully- there can only exist edges between nodes.
    RegionArgument(u8),
    End,
    Fmt(FmtNode),
    UseFuel(u64),
}

impl MirNode {
    // TODO: consider replacing this sort of inspection with an edge kind for
    // depending on things that do not produce values, like function definitions
    fn produces_value(&self) -> bool {
        match self {
            MirNode::FunctionDefinition(_)
            | MirNode::RecursiveEnvironment(_)
            | MirNode::End
            | MirNode::Fmt(_)
            | MirNode::PartialApply => false,
            MirNode::Integer(_)
            | MirNode::Coerce(_)
            | MirNode::Roll
            | MirNode::BinOp(_)
            | MirNode::Filter(_)
            | MirNode::Compare(_)
            | MirNode::Count
            | MirNode::Apply
            | MirNode::Loop(_, _)
            | MirNode::Decision(_)
            | MirNode::RegionArgument(_)
            | MirNode::UseFuel(_) => true,
        }
    }
    fn produces_output(&self) -> bool {
        use ::petgraph::Direction;
        use MirNode::*;
        match self {
            Fmt(_) => true,
            // TODO: consider saving this result on the node itself
            Loop(region, _ty) => region
                .graph
                .edges_directed(region.end, Direction::Outgoing)
                .any(|edge| matches!(edge.weight(), MirEdge::IntermediateResultDependency { .. })),
            Decision(_regions) => todo!("output effect inference for decision points"),
            _ => false,
        }
    }
    #[allow(dead_code)]
    fn is_structural(&self) -> bool {
        use MirNode::*;
        matches!(
            self,
            Loop(_, _) | Decision(_) | FunctionDefinition(_) | RecursiveEnvironment(_)
        )
    }
}

/// A dummy macro so I can write example snippets with full editor support.
macro_rules! mir {
    ($($t:tt)*) => {};
}
mir! {
    // An example of how we might structure an explosion in MIR.
    let mut results = Stack::new();
    let mut to_roll = (2, 6);
    loop {
        let result = roll(..to_roll);
        results.push(result);
        to_roll = (count((== 6), result), to_roll.1);
    } while (to_roll.0 != 0);
}

/// An edge in the MIR data dependency graph.
#[derive(Debug, Clone)]
enum MirEdge {
    /// Data dependence edges as described in the RVSDG and other papers.
    DataDependency {
        port: u8,
    },
    FuelDependency,
    /// Very similar to `DataDependency`, but written distinctly for ease
    /// of special treatment.
    IntermediateResultDependency {
        port: u8,
    },
    /// Dependency on a function, written distinctly for ease of special treatment.
    /// This kind of edge cannot connect to `Decision`s, and functions *must* be
    /// conveyed using this edge kind.
    FunctionDependency {
        port: u8,
    },
}

use ::petgraph::{graph::NodeIndex, Directed, Graph};
type MirGraph = Graph<MirNode, MirEdge, Directed>;

/// Error type for constructing MIR programs.
/// The specific role that this will play is not yet clear,
/// as our story for constructing MIR is still quite immature.
#[derive(Debug)]
pub enum InvalidProgram {
    BooleanAsInteger,
}

struct BooleanAsInteger;
impl From<BooleanAsInteger> for InvalidProgram {
    fn from(BooleanAsInteger: BooleanAsInteger) -> Self {
        Self::BooleanAsInteger
    }
}

/// Lower a parsed dice program to MIR.
/// Currently infallible, as the parser already rejects ill-typed programs.
pub fn lower(ast: &crate::parse::Program) -> Result<Mir, InvalidProgram> {
    let mut graph = MirGraph::new();
    // Evaluation order is depth first, left to right, across the
    // whole dice program.
    // There may be optimization opportunities that involve relaxing
    // that ordering, of varying quality.
    // First, rolls are held to be independent of each other-
    // we do not guarantee a particular starting seed in any context,
    // although it has been considered for reproducible sample distribution
    // plotting.
    // Therefore, we can reorder rolls, or perform them in parallel, if it would
    // improve performance.
    // Second, we may completely fold all constant arithmetic, even though doing so
    // may change the overflow behavior near integer limits, as I have made
    // no particular guarantee around overflow handling.
    // It would also be possible to only fold constant arithmetic that does not overflow,
    // or which would definitely overflow at runtime *anyway*.
    /// State kept while scrolling depth first, left to right, across
    /// the dice program we're lowering to MIR.
    struct State {
        // Note that `Graph` indices are stable as long as you don't
        // *remove* any nodes or edges. Since we don't do that during
        // MIR construction, we don't need to worry about this.
        last_fuel_use: Option<NodeIndex>,
    }
    impl State {
        fn new() -> Self {
            Self {
                last_fuel_use: None,
            }
        }
        /// Add a runtime fuel dependency. This is for operations whose fuel use cannot
        /// be known statically, prior to runtime.
        #[allow(dead_code)]
        fn add_fuel_use(&mut self, graph: &mut MirGraph, node: NodeIndex) {
            if let Some(last_fuel_use) = self.last_fuel_use {
                graph.add_edge(node, last_fuel_use, MirEdge::FuelDependency);
            }
            self.last_fuel_use = Some(node);
        }
    }
    let mut state = State::new();
    struct Lowered {
        data: NodeIndex,
        intermediates: NodeIndex,
    }
    fn lower_node(
        terms: &Arena<Term>,
        graph: &mut MirGraph,
        state: &mut State,
        current: Id<Term>,
    ) -> Result<Lowered, InvalidProgram> {
        fn coerce_to_int(
            graph: &mut MirGraph,
            term: NodeIndex,
        ) -> Result<NodeIndex, BooleanAsInteger> {
            match mir_type_of(&*graph, term) {
                Type::Output => {
                    let coercion = graph.add_node(MirNode::Coerce(Coercion::FromOutputToInt));
                    graph.add_edge(coercion, term, MirEdge::DataDependency { port: 0 });
                    Ok(coercion)
                }
                Type::Integer => Ok(term),
                Type::Boolean => Err(BooleanAsInteger),
            }
        }
        // TODO: Consider macro generating more of this code.
        Ok(match &terms[current] {
            Term::Constant(val) => {
                let data = graph.add_node(MirNode::Integer(*val));
                let record = graph.add_node(MirNode::Fmt(FmtNode::Record));
                graph.add_edge(
                    record,
                    data,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                let annotate =
                    graph.add_node(MirNode::Fmt(FmtNode::Annotate(Annotation::Constant)));
                graph.add_edge(
                    annotate,
                    record,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                Lowered {
                    data,
                    intermediates: annotate,
                }
            }
            Term::DiceRoll(count, sides) => {
                let annotation = Annotation::Roll {
                    count: *count,
                    sides: *sides,
                };
                let count = graph.add_node(MirNode::Integer(*count));
                let sides = graph.add_node(MirNode::Integer(*sides));
                let roll = graph.add_node(MirNode::Roll);
                graph.add_edge(roll, count, MirEdge::DataDependency { port: 0 });
                graph.add_edge(roll, sides, MirEdge::DataDependency { port: 1 });
                let output = graph.add_node(MirNode::Fmt(FmtNode::Record));
                graph.add_edge(
                    output,
                    roll,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                let annotate = graph.add_node(MirNode::Fmt(FmtNode::Annotate(annotation)));
                graph.add_edge(
                    annotate,
                    output,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                Lowered {
                    data: roll,
                    intermediates: annotate,
                }
            }
            Term::KeepHigh(term, keep_count) | Term::KeepLow(term, keep_count) => {
                // At least for now, the parser doesn't permit other things in here.
                assert!(matches!(&terms[*term], Term::DiceRoll(_, _)));
                let annotation = match &terms[current] {
                    Term::KeepHigh(_, _) => Annotation::KeepHigh {
                        keep_count: *keep_count,
                    },
                    Term::KeepLow(_, _) => Annotation::KeepLow {
                        keep_count: *keep_count,
                    },
                    _ => unreachable!(),
                };
                let Lowered {
                    data: roll,
                    intermediates: roll_intermediates,
                } = lower_node(terms, &mut *graph, &mut *state, *term)?;
                let keep_count = graph.add_node(MirNode::Integer(*keep_count));
                let keep_by =
                    graph.add_node(MirNode::Filter(Filter::Simple(match &terms[current] {
                        Term::KeepHigh(_, _) => FilterKind::KeepHigh,
                        Term::KeepLow(_, _) => FilterKind::KeepLow,
                        _ => unreachable!(),
                    })));
                graph.add_edge(keep_by, roll, MirEdge::DataDependency { port: 0 });
                graph.add_edge(keep_by, keep_count, MirEdge::DataDependency { port: 1 });
                let output = graph.add_node(MirNode::Fmt(FmtNode::Record));
                graph.add_edge(
                    output,
                    keep_by,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                let list = graph.add_node(MirNode::Fmt(FmtNode::MakeList));
                let add_roll_intermediates = graph.add_node(MirNode::Fmt(FmtNode::PushToList));
                graph.add_edge(
                    add_roll_intermediates,
                    list,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                graph.add_edge(
                    add_roll_intermediates,
                    roll_intermediates,
                    MirEdge::IntermediateResultDependency { port: 1 },
                );
                let add_filtered_intermediates = graph.add_node(MirNode::Fmt(FmtNode::PushToList));
                graph.add_edge(
                    add_filtered_intermediates,
                    add_roll_intermediates,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                graph.add_edge(
                    add_filtered_intermediates,
                    output,
                    MirEdge::IntermediateResultDependency { port: 1 },
                );
                let annotate = graph.add_node(MirNode::Fmt(FmtNode::Annotate(annotation)));
                graph.add_edge(
                    annotate,
                    add_filtered_intermediates,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                Lowered {
                    data: keep_by,
                    intermediates: annotate,
                }
            }
            Term::Explode(roll) => {
                let (start_count, side_count): (_, i64) = match terms[*roll] {
                    Term::DiceRoll(count, sides) => (count, sides),
                    _ => unreachable!("the parser wouldn't accept explosion in invalid position"),
                };
                let annotate =
                    graph.add_node(MirNode::Fmt(FmtNode::Annotate(Annotation::Explode {
                        count: start_count,
                        sides: side_count,
                    })));
                let mut explosion = MirGraph::new();
                // let roll = lower_node(terms, &mut explosion, &mut explosion_state, *roll)?;
                let count = explosion.add_node(MirNode::RegionArgument(0));
                let sum = explosion.add_node(MirNode::RegionArgument(1));
                let iterations = explosion.add_node(MirNode::Fmt(FmtNode::RegionArgument(0)));

                let fueled_count =
                    explosion.add_node(MirNode::UseFuel((start_count as u64).saturating_mul(4)));
                explosion.add_edge(fueled_count, count, MirEdge::DataDependency { port: 0 });

                let sides = explosion.add_node(MirNode::Integer(side_count));

                let roll = explosion.add_node(MirNode::Roll);
                explosion.add_edge(roll, fueled_count, MirEdge::DataDependency { port: 0 });
                explosion.add_edge(roll, sides, MirEdge::DataDependency { port: 1 });

                let iteration = explosion.add_node(MirNode::Fmt(FmtNode::Record));
                explosion.add_edge(
                    iteration,
                    roll,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                let iterations = {
                    let out = explosion.add_node(MirNode::Fmt(FmtNode::PushToList));
                    explosion.add_edge(
                        out,
                        iterations,
                        MirEdge::IntermediateResultDependency { port: 0 },
                    );
                    explosion.add_edge(
                        out,
                        iteration,
                        MirEdge::IntermediateResultDependency { port: 1 },
                    );
                    out
                };

                let filter = explosion.add_node({
                    let mut func = MirGraph::new();
                    let die_result = func.add_node(MirNode::RegionArgument(0));
                    let sides = func.add_node(MirNode::Integer(side_count));

                    let cmp = func.add_node(MirNode::Compare(Comparison::Equal));
                    func.add_edge(cmp, die_result, MirEdge::DataDependency { port: 0 });
                    func.add_edge(cmp, sides, MirEdge::DataDependency { port: 1 });

                    let end = func.add_node(MirNode::End);
                    func.add_edge(end, cmp, MirEdge::DataDependency { port: 0 });
                    MirNode::FunctionDefinition(Region { graph: func, end })
                });

                let remaining = explosion.add_node(MirNode::Filter(Filter::SatisfiesPredicate));
                explosion.add_edge(remaining, roll, MirEdge::DataDependency { port: 0 });
                explosion.add_edge(remaining, filter, MirEdge::FunctionDependency { port: 0 });

                let roll_sum = explosion.add_node(MirNode::Coerce(Coercion::FromOutputToInt));
                explosion.add_edge(roll_sum, roll, MirEdge::DataDependency { port: 0 });
                let next_sum = explosion.add_node(MirNode::BinOp(BinaryOp::Add));
                explosion.add_edge(next_sum, sum, MirEdge::DataDependency { port: 0 });
                explosion.add_edge(next_sum, roll_sum, MirEdge::DataDependency { port: 1 });

                let remaining_count = explosion.add_node(MirNode::Count);
                explosion.add_edge(
                    remaining_count,
                    remaining,
                    MirEdge::DataDependency { port: 0 },
                );

                let not_empty = explosion.add_node(MirNode::Compare(Comparison::GreaterThan));
                explosion.add_edge(
                    not_empty,
                    remaining_count,
                    MirEdge::DataDependency { port: 0 },
                );
                let zero = explosion.add_node(MirNode::Integer(0));
                explosion.add_edge(not_empty, zero, MirEdge::DataDependency { port: 1 });

                let end = explosion.add_node(MirNode::End);
                explosion.add_edge(end, next_sum, MirEdge::DataDependency { port: 1 });
                explosion.add_edge(end, remaining_count, MirEdge::DataDependency { port: 0 });
                explosion.add_edge(end, not_empty, MirEdge::DataDependency { port: 2 });
                // explosion.add_edge(end, fuel, MirEdge::DataDependency { port: 1 });
                explosion.add_edge(
                    end,
                    iterations,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );

                let explosion = graph.add_node(MirNode::Loop(
                    Region {
                        graph: explosion,
                        end,
                    },
                    Type::Integer,
                ));
                let start_count = graph.add_node(MirNode::Integer(start_count));
                graph.add_edge(explosion, start_count, MirEdge::DataDependency { port: 0 });
                let zero = graph.add_node(MirNode::Integer(0));
                graph.add_edge(explosion, zero, MirEdge::DataDependency { port: 1 });
                let start_iterations = graph.add_node(MirNode::Fmt(FmtNode::MakeList));
                graph.add_edge(
                    explosion,
                    start_iterations,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                graph.add_edge(
                    annotate,
                    explosion,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                // TODO: map arguments and results and such
                Lowered {
                    data: explosion,
                    intermediates: annotate,
                }
            }
            Term::Add(left, right) | Term::Subtract(left, right) => {
                let left = lower_node(terms, &mut *graph, &mut *state, *left)?;
                let right = lower_node(terms, &mut *graph, &mut *state, *right)?;
                let input_list = graph.add_node(MirNode::Fmt(FmtNode::MakeList));
                let add_left_intermediates = graph.add_node(MirNode::Fmt(FmtNode::PushToList));
                graph.add_edge(
                    add_left_intermediates,
                    input_list,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                graph.add_edge(
                    add_left_intermediates,
                    left.intermediates,
                    MirEdge::IntermediateResultDependency { port: 1 },
                );
                let add_right_intermediates = graph.add_node(MirNode::Fmt(FmtNode::PushToList));
                graph.add_edge(
                    add_right_intermediates,
                    add_left_intermediates,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                graph.add_edge(
                    add_right_intermediates,
                    right.intermediates,
                    MirEdge::IntermediateResultDependency { port: 1 },
                );
                let annotate;
                let left = coerce_to_int(&mut *graph, left.data)?;
                let right = coerce_to_int(&mut *graph, right.data)?;
                let total = match &terms[current] {
                    Term::Add(_, _) => {
                        annotate = graph.add_node(MirNode::Fmt(FmtNode::Annotate(Annotation::Add)));
                        BinaryOp::Add
                    }
                    Term::Subtract(_, _) => {
                        annotate =
                            graph.add_node(MirNode::Fmt(FmtNode::Annotate(Annotation::Subtract)));
                        BinaryOp::Subtract
                    }
                    _ => unreachable!(),
                };
                graph.add_edge(
                    annotate,
                    add_right_intermediates,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                let total = graph.add_node(MirNode::BinOp(total));
                graph.add_edge(total, left, MirEdge::DataDependency { port: 0 });
                graph.add_edge(total, right, MirEdge::DataDependency { port: 1 });
                Lowered {
                    data: total,
                    intermediates: annotate,
                }
            }
            // TODO: decide if we want a distinct negation operator.
            // Currently we just lower `-x` to `0 - x`.
            Term::UnarySubtract(term) => {
                let zero = graph.add_node(MirNode::Integer(0));
                let term = lower_node(terms, &mut *graph, &mut *state, *term)?;
                let annotate =
                    graph.add_node(MirNode::Fmt(FmtNode::Annotate(Annotation::UnarySubtract)));
                graph.add_edge(
                    annotate,
                    term.intermediates,
                    MirEdge::IntermediateResultDependency { port: 0 },
                );
                let term = coerce_to_int(&mut *graph, term.data)?;
                let total = graph.add_node(MirNode::BinOp(BinaryOp::Subtract));
                graph.add_edge(total, zero, MirEdge::DataDependency { port: 0 });
                graph.add_edge(total, term, MirEdge::DataDependency { port: 1 });
                Lowered {
                    data: total,
                    intermediates: annotate,
                }
            }
            Term::UnaryAdd(term) => {
                // TODO: insert integer coercion?
                // As `+x` is equivalent to `x`, we just elide this operation
                // when lowering to MIR.
                let term = lower_node(terms, &mut *graph, &mut *state, *term)?;
                term
            }
        })
    }
    let end = lower_node(ast.terms(), &mut graph, &mut state, ast.top)?;
    let top = graph.add_node(MirNode::End);
    graph.add_edge(top, end.data, MirEdge::DataDependency { port: 0 });
    graph.add_edge(
        top,
        end.intermediates,
        MirEdge::IntermediateResultDependency { port: 0 },
    );
    Ok(Mir { graph, top })
}

/// Generate GraphViz DOT code for a MIR graph.
pub fn dot(mir: &Mir) -> String {
    viz::dot(mir)
}