espy_tail/

lib.rs

//! Compiles an espy abstract syntax tree into bytecode.
//!
//! ```rust
//! use espy_eyes::Lexer;
//! use espy_ears::Block;
//! use espy_tail::compile;
//!
//! let source = "1 + 2";
//! let mut lexer = Lexer::from(source).peekable();
//! let block = Block::new(&mut lexer);
//! let program = compile(block, source).unwrap();
//! ```

use espy_ears::Diagnostics;
use espy_ears::Expression;
use espy_ears::FunctionBody;
use espy_ears::Let;
use espy_ears::Match;
use espy_ears::Node;
use espy_ears::Sequence;
use espy_ears::Set;
use espy_ears::Statement;
use espy_ears::Use;
use espy_ears::{Binding, BindingMethod};
use espy_ears::{Block, BlockResult};
use espy_ears::{Rebind, RebindBy};
use espy_eyes::{Lexigram, Token};
use espy_heart::prelude::*;
use std::borrow::Cow;
use std::iter;
use std::mem;
use std::num::NonZero;
use std::num::{ParseIntError, TryFromIntError};

#[cfg(test)]
mod tests;

#[must_use]
#[derive(Clone, Debug, Default)]
pub struct CompiledProgram {
    pub executable: Vec<u8>,
    pub debug_info: Vec<u8>,
}

/// Compiles a block directly into interpreter-ready bytecode.
///
/// # Errors
///
/// Returns an error if the block contained error diagnostics or failed to compile.
pub fn compile<'source>(
    ast: Box<Block<'source>>,
    source: &'source str,
) -> Result<CompiledProgram, Error<'source>> {
    Program::prepare(ast, source).and_then(Program::compile)
}

#[derive(Debug)]
pub enum Error<'source> {
    /// Emitted when the program is too large (produced bytecode larger than 4GiB)
    ProgramLimitExceeded,
    /// Attempted to break out of a scope, but no parent scope accepted unlabeled breaks.
    InvalidBreak(Token<'source>),
    /// The AST contained an integer that did not fit into the expected type.
    InvalidInteger(Token<'source>, ParseIntError),
    /// The AST contained a string with an invalid escape sequence.
    InvalidString(Token<'source>, espy_eyes::EscapeError),
    /// The AST contained an identifier with an invalid escape sequence.
    InvalidIdentifier(Token<'source>, espy_eyes::EscapeError),
    /// A variable was referenced that did not exist.
    UndefinedSymbol(Token<'source>),
    /// The AST contained an error.
    ///
    /// Note that this only contains the first error that the parser encounted.
    /// Inspecting the AST directly allows you to see all of the errors the parser encountered
    /// with some additional context.
    InvalidAst(espy_ears::Error<'source>),
}

impl<'source> std::fmt::Display for Error<'source> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            Error::ProgramLimitExceeded => write!(
                f,
                "program limit exceeded (bytecode must be less than 4GiB)"
            ),
            Error::InvalidBreak(_) => write!(
                f,
                "attempted to break out of a scope, but no parent scope accepted unlabeled breaks"
            ),
            Error::InvalidInteger(_, e) => write!(f, "invalid integer literal: {e}"),
            Error::InvalidString(_, e) => write!(f, "invalid string literal: {e:?}"),
            Error::InvalidIdentifier(_, e) => write!(f, "invalid raw identifier: {e:?}"),
            Error::UndefinedSymbol(_) => write!(f, "undefined symbol"),
            Error::InvalidAst(e) => write!(f, "failed to parse program: {e:?}"),
        }
    }
}

impl<'source> std::error::Error for Error<'source> {}

impl<'source> Error<'source> {
    /// Provides the span of source code causing this compiler error,
    /// if one is available.
    ///
    /// Note that this method will return `None` in the case of an invalid ast.
    /// Inspect ast diagnostics directly if you want to format them.
    ///
    /// # Panics
    ///
    /// Panics if provided a aosurce string slice that this error did not
    /// originate from.
    #[must_use]
    pub fn locate(&self, source: &'source str) -> Option<(usize, usize)> {
        let origin = match self {
            Error::ProgramLimitExceeded => return None,
            Error::InvalidBreak(token) => token.origin,
            Error::InvalidInteger(token, _) => token.origin,
            Error::InvalidString(token, _) => token.origin,
            Error::InvalidIdentifier(token, _) => token.origin,
            Error::UndefinedSymbol(token) => token.origin,
            Error::InvalidAst(_) => return None,
        };
        let start = usize::try_from(origin.as_ptr() as isize - source.as_ptr() as isize)
            .expect("origin must start after source string");
        let end = start + origin.len();
        assert!(
            origin.len() <= source.len(),
            "origin must be a subset of source string"
        );
        Some((start, end))
    }
}

impl From<TryFromIntError> for Error<'_> {
    fn from(_: TryFromIntError) -> Self {
        Self::ProgramLimitExceeded
    }
}

fn try_validate(diagnostics: Diagnostics) -> Result<(), Error> {
    if let Some(error) = diagnostics.errors.into_iter().next() {
        Err(Error::InvalidAst(error))
    } else {
        Ok(())
    }
}

/// For retroactively filling in jump instructions.
fn resolve_jump(block: &mut ProgramBlock, at: usize) {
    #[allow(
        clippy::cast_possible_truncation,
        reason = "this will produce incorrect code, but compile will return an error later anyways so it's fine"
    )]
    let pc = block.len() as ProgramCounter;
    block.instructions[at..(at + size_of_val(&pc))].copy_from_slice(&pc.to_le_bytes());
}

fn token_range(token: Token, source: &str) -> Span {
    let start = usize::try_from(token.origin.as_ptr() as isize - source.as_ptr() as isize)
        .expect("origin must start after source string");
    let end = start + token.origin.len();
    assert!(
        token.origin.len() <= source.len(),
        "origin must be a subset of source string"
    );
    Span {
        start,
        end: end
            .try_into()
            .expect("origin should be at least one character"),
    }
}

// These are practically used as functions which return iterators over bytes at this point.
// There isn't a good reason for this other than that they used to be stored for a little while,
// so if true functions make more sense for any reason this type can be removed.
#[derive(Clone, Debug, PartialEq, Eq)]
enum Instruction {
    /// Copy a value from the given position and put it on the top of the stack.
    Clone(StackPointer),
    /// Pop a value off the stack.
    Pop,
    /// Pop a value off the stack and write it to the given position.
    /// Then, pop each value above this position and discard it.
    Collapse(StackPointer),
    /// Set the program counter.
    Jump(ProgramCounter),
    /// Pop a boolean value off the stack.
    /// If it is *false*, set the program counter.
    If(ProgramCounter),

    PushUnit,
    PushI64(i64),
    /// Pop the top value off the stack and use it as the return type of the function.
    ///
    /// Pop the next value off the stack and use it as the input type of the function.
    ///
    /// Pop the following `captures` values off the stack and onto a new stack,
    /// and then push a function containing the new stack and the proceeding block id to the current stack.
    /// If the block id is zero (referring to the program entrypoint),
    /// the function should panic when called (have a body of never).
    PushFunction {
        captures: StackPointer,
        function: BlockId,
    },
    PushTrue,
    PushFalse,
    /// Pop the top value off the stack;
    /// it should be unit or a named tuple of types.
    /// Use this value as the enum's variants.
    ///
    /// Push the resulting enum type to the stack.
    PushEnum,
    PushString(StringId),

    Add,
    Sub,
    Mul,
    Div,
    /// Pop the top value off the stack and push it to the function's stack.
    /// The next value is the function to be called.
    /// After pushing the value, jump to the function's block id.
    /// It will return a single value which is placed to the stack in its place.
    Call,
    /// Pop the first value off the stack, then pop the second and index it using the first.
    /// Push the result.
    Index,
    /// Pop two values off the stack and combine them into a tuple.
    /// If one of them is already a tuple, concatenate them (always producing a flat tuple).
    /// The topmost value should be appended to the value underneath it.
    Tuple,
    /// Pop a value off the stack and turn it into a named tuple with a single value,
    /// and a name according to the following string id.
    Name(StringId),
    /// Pop a value off the stack and turn it into a numeric tuple with a single value.
    Nest,
    Negative,
    Pipe,
    BitwiseAnd,
    BitwiseOr,
    BitwiseXor,
    EqualTo,
    NotEqualTo,
    Greater,
    GreaterEqual,
    Lesser,
    LesserEqual,
    LogicalAnd,
    LogicalOr,
    Deref,
    Set,
    Matches,
    /// Pop a value off the stack; this is the bind function.
    /// Pop the next value off the stack; this is the first argument to the bind function.
    /// Turn the current state of the interpreter into a function and pass it as the second argument to the bind function.
    /// Finally, execute the bind function with these arguments.
    Bind,
    /// Pop a value off the stack.
    /// Then turn the current state of the interpreter into a function.
    /// Return a tuple of these values from the current function.
    Yield,
}

struct InstructionIter {
    instruction: Instruction,
    index: usize,
}

impl Iterator for InstructionIter {
    type Item = u8;

    fn next(&mut self) -> Option<Self::Item> {
        macro_rules! decompose {
            ($instruction:expr, $($arg:ident as $offset:literal..=$end:literal),*) => {
                match self.index {
                    0 => $instruction,
                    $(
                        $offset..=$end => $arg.to_le_bytes()[self.index - $offset],
                    )*
                    _ => return None,
                }
            };
        }
        let byte = match self.instruction {
            Instruction::Clone(from) => decompose!(instruction::CLONE, from as 1..=4),
            Instruction::Pop => decompose!(instruction::POP,),
            Instruction::Collapse(to) => decompose!(instruction::COLLAPSE, to as 1..=4),
            Instruction::Jump(pc) => decompose!(instruction::JUMP, pc as 1..=4),
            Instruction::If(pc) => decompose!(instruction::IF, pc as 1..=4),

            Instruction::PushUnit => decompose!(instruction::PUSH_UNIT,),
            Instruction::PushI64(literal) => decompose!(instruction::PUSH_I64, literal as 1..=8),
            Instruction::PushFunction { captures, function } => {
                decompose!(instruction::PUSH_FUNCTION, captures as 1..=4, function as 5..=8)
            }
            Instruction::PushTrue => decompose!(instruction::PUSH_TRUE,),
            Instruction::PushFalse => decompose!(instruction::PUSH_FALSE,),
            Instruction::PushEnum => decompose!(instruction::PUSH_ENUM,),
            Instruction::PushString(s) => decompose!(instruction::PUSH_STRING, s as 1..=4),

            Instruction::Add => decompose!(instruction::ADD,),
            Instruction::Sub => decompose!(instruction::SUB,),
            Instruction::Mul => decompose!(instruction::MUL,),
            Instruction::Div => decompose!(instruction::DIV,),
            Instruction::Call => decompose!(instruction::CALL,),
            Instruction::Index => decompose!(instruction::INDEX,),
            Instruction::Tuple => decompose!(instruction::TUPLE,),
            Instruction::Name(name) => decompose!(instruction::NAME, name as 1..=4),
            Instruction::Nest => decompose!(instruction::NEST,),
            Instruction::Negative => decompose!(instruction::NEGATIVE,),
            Instruction::Pipe => decompose!(instruction::PIPE,),
            Instruction::BitwiseAnd => decompose!(instruction::BITWISE_AND,),
            Instruction::BitwiseOr => decompose!(instruction::BITWISE_OR,),
            Instruction::BitwiseXor => decompose!(instruction::BITWISE_XOR,),
            Instruction::EqualTo => decompose!(instruction::EQUAL_TO,),
            Instruction::NotEqualTo => decompose!(instruction::NOT_EQUAL_TO,),
            Instruction::Greater => decompose!(instruction::GREATER,),
            Instruction::GreaterEqual => decompose!(instruction::GREATER_EQUAL,),
            Instruction::Lesser => decompose!(instruction::LESSER,),
            Instruction::LesserEqual => decompose!(instruction::LESSER_EQUAL,),
            Instruction::LogicalAnd => decompose!(instruction::LOGICAL_AND,),
            Instruction::LogicalOr => decompose!(instruction::LOGICAL_OR,),
            Instruction::Deref => decompose!(instruction::DEREF,),
            Instruction::Set => decompose!(instruction::SET,),
            Instruction::Matches => decompose!(instruction::MATCHES,),
            Instruction::Bind => decompose!(instruction::BIND,),
            Instruction::Yield => decompose!(instruction::YIELD,),
        };
        self.index += 1;
        Some(byte)
    }
}

impl IntoIterator for Instruction {
    type Item = u8;
    type IntoIter = InstructionIter;
    fn into_iter(self) -> Self::IntoIter {
        InstructionIter {
            instruction: self,
            index: 0,
        }
    }
}

#[derive(Clone, Copy, Debug)]
struct Span {
    start: usize,
    // a token must have a length of at least one character,
    // so we use this fact to provide Option<Span> a niche.
    end: NonZero<usize>,
}

impl Span {
    fn merge(&self, other: &Self) -> Self {
        Self {
            start: self.start,
            end: other.end,
        }
    }
}

#[derive(Clone, Debug, Default)]
struct ProgramBlock {
    instructions: Vec<u8>,
    debug_info: Vec<u8>,
}

struct ProgramPushBuilder<'block> {
    span: Option<Span>,
    block: &'block mut ProgramBlock,
}

impl ProgramBlock {
    fn len(&self) -> usize {
        self.instructions.len()
    }

    fn at(&mut self, span: Span) -> ProgramPushBuilder<'_> {
        ProgramPushBuilder {
            span: Some(span),
            block: self,
        }
    }

    fn push(&mut self, instruction: Instruction, span: Option<Span>) -> &mut Self {
        let prev_len = self.instructions.len();
        self.instructions.extend(instruction);
        // The bytes of this instruction which need to be accounted for with ditto marks.
        let remaining_bytes = self.instructions.len() - prev_len - span.is_some() as usize;
        if let Some(span) = span {
            let start = (span.start as u64).to_le_bytes();
            let start =
                &start[0..(size_of::<u64>() - start.into_iter().rev().filter(|x| *x == 0).count())];
            let end = (usize::from(span.end) as u64).to_le_bytes();
            let end =
                &end[0..(size_of::<u64>() - end.into_iter().rev().filter(|x| *x == 0).count())];
            self.debug_info.extend(
                iter::once(debug::SPAN)
                    .chain(iter::once(start.len() as u8))
                    .chain(start.iter().copied())
                    .chain(iter::once(end.len() as u8))
                    .chain(end.iter().copied()),
            );
        }
        if remaining_bytes > 0 {
            self.debug_info
                .extend([debug::DITTO, remaining_bytes as u8]);
        }
        self
    }

    // This should only be used for generated instructions where no position is available.
    // Document why it is appropriate!
    fn push_positionless(&mut self, instruction: Instruction) -> &mut Self {
        self.push(instruction, None)
    }
}

impl<'block> ProgramPushBuilder<'block> {
    fn push(mut self, instruction: Instruction) -> Self {
        self.block.push(instruction, self.span);
        self.span = None;
        self
    }
}

#[derive(Clone, Debug, Default)]
struct Program<'source> {
    source: &'source str,
    blocks: Vec<ProgramBlock>,
    strings: Vec<Cow<'source, str>>,
}

impl<'source> Program<'source> {
    fn prepare(ast: Box<Block<'source>>, source: &'source str) -> Result<Self, Error<'source>> {
        let mut this = Self {
            source,
            ..Default::default()
        };
        let block_id = this.create_block()?;
        this.add_block(block_id, ast, Scope::default())?;
        Ok(this)
    }

    /// # Errors
    ///
    /// Returns an error if the program results in bytecode over 4GiB.
    fn compile(self) -> Result<CompiledProgram, Error<'source>> {
        let mut output = CompiledProgram {
            executable: Vec::new(),
            debug_info: Vec::new(),
        };

        output
            .executable
            .extend(u32::try_from(self.blocks.len())?.to_le_bytes());
        output
            .executable
            .extend(u32::try_from(self.strings.len())?.to_le_bytes());
        // Reserve space for vector offsets.
        // Blocks, strings, and string sets are only referred to by index,
        // so this is the only program-wide retroactive filling required.
        let block_offsets = output.executable.len();
        output
            .executable
            .extend(iter::repeat_n(0, self.blocks.len() * size_of::<u32>()));
        // same for strings.
        let string_offsets = output.executable.len();
        output
            .executable
            .extend(iter::repeat_n(0, self.strings.len() * size_of::<u32>()));

        // Fill in offsets.
        for (block_id, block) in self.blocks.into_iter().enumerate() {
            let src = BlockId::try_from(output.executable.len())?;
            let dest = block_offsets + block_id * size_of_val(&src);
            output.executable[dest..(dest + size_of_val(&src))].copy_from_slice(&src.to_le_bytes());
            output.executable.extend(block.instructions);
            output.debug_info.extend(block.debug_info);
        }
        for (string_id, string) in self.strings.into_iter().enumerate() {
            let src = StringId::try_from(output.executable.len())?;
            let dest = string_offsets + string_id * size_of_val(&src);
            output.executable[dest..(dest + size_of_val(&src))].copy_from_slice(&src.to_le_bytes());
            output.executable.extend(string.bytes());
        }
        Ok(output)
    }

    fn create_block(&mut self) -> Result<BlockId, Error<'source>> {
        self.blocks.push(ProgramBlock::default());
        (self.blocks.len() - 1)
            .try_into()
            .map_err(|_| Error::ProgramLimitExceeded)
    }

    fn create_string(
        &mut self,
        s: impl Into<Cow<'source, str>>,
    ) -> Result<StringId, Error<'source>> {
        let s = s.into();
        if let Some((i, _)) = self.strings.iter().enumerate().find(|(_, x)| **x == s) {
            i
        } else {
            self.strings.push(s);
            self.strings.len() - 1
        }
        .try_into()
        .map_err(|_| Error::ProgramLimitExceeded)
    }

    fn add_block(
        &mut self,
        block_id: BlockId,
        block: Box<Block<'source>>,
        mut scope: Scope<'_, 'source>,
    ) -> Result<(), Error<'source>> {
        self.insert_block(block_id, block, &mut scope)?;
        Ok(())
    }

    fn insert_block(
        &mut self,
        block_id: BlockId,
        block: Box<Block<'source>>,
        scope: &mut Scope<'_, 'source>,
    ) -> Result<(), Error<'source>> {
        let (result, diagnostics, statements) = Block::destructure(block);
        try_validate(diagnostics)?;
        for statement in statements {
            self.add_statement(block_id, statement, scope)?;
        }
        // Collapse the scope if any additional values are left the stack.
        // This occurs when statements bind variables.
        // We have to check this here because BlockResult::Function is about to move the scope,
        // but the instruction is not emitted until after the result is pushed to the stack.
        // This is fine because block results must push one and only one value.
        let collapse_point = scope
            .parent
            .filter(|parent| parent.stack_pointer < scope.stack_pointer)
            .map(|parent| parent.stack_pointer);
        match result {
            BlockResult::Expression(i) => {
                self.add_expression(block_id, i, scope)?;
            }
            BlockResult::Function(function) => {
                try_validate(function.diagnostics)?;
                if let Some(input) = function.input {
                    self.add_expression(block_id, input, scope)?;
                } else {
                    self.blocks[block_id as usize]
                        .at(token_range(function.with_token, self.source))
                        .push(Instruction::Clone(builtins::ANY));
                    scope.stack_pointer += 1;
                }
                if let Some(output) = function.output {
                    self.add_expression(block_id, output, scope)?;
                } else {
                    self.blocks[block_id as usize]
                        .at(token_range(function.with_token, self.source))
                        .push(Instruction::Clone(builtins::ANY));
                    scope.stack_pointer += 1;
                }
                // Account for input and output being popped by PushFunction.
                scope.stack_pointer -= 2;
                let mut scope = scope.promote();
                let captures = scope.stack_pointer;
                let function_id = if let FunctionBody::Block(block) = function.body {
                    let function_id = self.create_block()?;
                    // to be filled in by the argument (which is about to be bound)
                    scope.stack_pointer += 1;
                    if let Some(argument) = function.argument {
                        self.add_binding(function_id, argument, &mut scope)?;
                    }
                    self.add_block(function_id, block, scope)?;
                    function_id
                } else {
                    if let Some(argument) = function.argument {
                        self.validate_binding(argument)?;
                    }
                    0
                };
                self.blocks[block_id as usize]
                    .at(token_range(function.with_token, self.source))
                    .push(Instruction::PushFunction {
                        captures,
                        function: function_id,
                    });
            }
        }
        if let Some(collapse_point) = collapse_point {
            // Collapse is entirely generated;
            // `}` or `end` might fit as the associated token, but top-level blocks have no equivalent.
            // (they may have no tokens at all)
            self.blocks[block_id as usize].push_positionless(Instruction::Collapse(collapse_point));
        }
        Ok(())
    }

    /// This is a copy of add_binding with compilation disabled,
    /// so that the argument to a never function is still validated even though its compilation is skipped.
    /// I would prefer any other way to do this.
    ///
    /// self is entirely unused.
    fn validate_binding(&self, binding: Binding<'source>) -> Result<(), Error<'source>> {
        try_validate(binding.diagnostics)?;
        match binding.method {
            BindingMethod::Single(_) => {}
            BindingMethod::Numeric { bindings, .. } => {
                for binding in bindings {
                    self.validate_binding(binding.binding)?;
                }
            }
            BindingMethod::Named { bindings, .. } => {
                for binding in bindings.into_iter().flat_map(|x| x.binding) {
                    self.validate_binding(binding.binding)?;
                }
            }
        }
        Ok(())
    }

    fn add_binding(
        &mut self,
        block_id: BlockId,
        binding: Binding<'source>,
        scope: &mut Scope<'_, 'source>,
    ) -> Result<(), Error<'source>> {
        try_validate(binding.diagnostics)?;
        let root = scope.stack_pointer - 1;
        match binding.method {
            BindingMethod::Single(token) => match token.lexigram {
                Lexigram::Ident => scope.insert(
                    token
                        .resolve()
                        .map_err(|e| Error::InvalidIdentifier(token, e))?,
                ),
                Lexigram::Discard => {}
                _ => unreachable!("only idents and discards are valid bindings"),
            },
            BindingMethod::Numeric {
                open_paren,
                bindings,
                close_paren,
            } => {
                for (i, binding) in bindings.into_iter().enumerate() {
                    let range = token_range(open_paren, self.source).merge(&token_range(
                        close_paren.expect("close paren should be present in a valid numeric bind"),
                        self.source,
                    ));
                    self.blocks[block_id as usize]
                        .at(range)
                        .push(Instruction::Clone(root))
                        .push(Instruction::PushI64(
                            i64::try_from(i).expect("stack should never reach isize::MAX"),
                        ))
                        .push(Instruction::Index);
                    scope.stack_pointer += 1;
                    self.add_binding(block_id, binding.binding, scope)?;
                }
            }
            BindingMethod::Named {
                open_brace,
                bindings,
                close_brace,
            } => {
                for binding in bindings {
                    let range = token_range(open_brace, self.source).merge(&token_range(
                        close_brace.expect("close brace should be present in a valid numeric bind"),
                        self.source,
                    ));
                    let s = self.create_string(
                        binding
                            .field
                            .resolve()
                            .map_err(|e| Error::InvalidIdentifier(binding.field, e))?,
                    )?;
                    self.blocks[block_id as usize]
                        .at(range)
                        .push(Instruction::Clone(root))
                        .push(Instruction::PushString(s))
                        .push(Instruction::Index);
                    scope.stack_pointer += 1;
                    if let Some(sub_binding) = binding.binding {
                        self.add_binding(block_id, sub_binding.binding, scope)?;
                    } else {
                        scope.insert(
                            binding
                                .field
                                .resolve()
                                .map_err(|e| Error::InvalidIdentifier(binding.field, e))?,
                        );
                    }
                }
            }
        }
        Ok(())
    }

    /// # Panic
    ///
    /// Panics if provided an invalid statement.
    /// Statements should be validated beforehand by checking the `diagnostics.errors` field.
    fn add_statement(
        &mut self,
        block_id: BlockId,
        statement: Statement<'source>,
        scope: &mut Scope<'_, 'source>,
    ) -> Result<(), Error<'source>> {
        match statement {
            Statement::Sequence(Sequence {
                expression,
                semicolon_token,
            }) => {
                self.add_expression(block_id, expression, scope)?;
                self.blocks[block_id as usize]
                    .at(token_range(semicolon_token, self.source))
                    .push(Instruction::Pop);
                scope.stack_pointer -= 1;
            }
            Statement::Let(Let {
                binding,
                expression,
                diagnostics,
                ..
            }) => {
                try_validate(diagnostics)?;
                let binding = binding.expect("missing bindings should be caught by diagnostics");
                self.add_expression(block_id, expression, scope)?;
                self.add_binding(block_id, binding, scope)?;
            }
            Statement::Rebind(Rebind {
                by, diagnostics, ..
            }) => {
                try_validate(diagnostics)?;
                match by {
                    RebindBy::Glob { star_token } => {
                        for (ident, value) in scope
                            .parent
                            .iter()
                            .flat_map(|parent| parent.bindings.iter())
                        {
                            self.blocks[block_id as usize]
                                .at(token_range(star_token, self.source))
                                .push(Instruction::Clone(*value));
                            scope.stack_pointer += 1;
                            // This is an inlined scope.insert call to allow
                            // mutating these fields while borrowing `parent`.
                            scope.bindings.push((
                                ident.clone(),
                                scope
                                    .stack_pointer
                                    .checked_sub(1)
                                    .expect("attempted to assign variable while stack was empty"),
                            ));
                        }
                    }
                    RebindBy::Identifiers { bindings } => {
                        for binding in bindings {
                            let token = binding
                                .ident_token
                                .expect("bindings should be some in a valid rebind");
                            let ident = token
                                .resolve()
                                .map_err(|e| Error::InvalidIdentifier(token, e))?;
                            let value = scope.get(&ident).ok_or(Error::UndefinedSymbol(token))?;
                            self.blocks[block_id as usize]
                                .at(token_range(token, self.source))
                                .push(Instruction::Clone(value));
                            scope.stack_pointer += 1;
                            scope.insert(ident);
                        }
                    }
                }
            }
            Statement::Set(Set {
                target,
                expression,
                diagnostics,
                set_token,
                ..
            }) => {
                try_validate(diagnostics)?;
                self.add_expression(block_id, target, scope)?;
                self.add_expression(block_id, expression, scope)?;
                self.blocks[block_id as usize]
                    .at(token_range(set_token, self.source))
                    .push(Instruction::Set);
                scope.stack_pointer -= 2;
            }
            Statement::Use(Use {
                expression,
                diagnostics,
                ..
            }) => {
                try_validate(diagnostics)?;
                self.add_expression(block_id, expression, scope)?;
                scope.bind_function = Some(
                    scope
                        .stack_pointer
                        .checked_sub(1)
                        .expect("attempted to assign bind function while stack was empty"),
                );
            }
        }
        Ok(())
    }

    fn add_expression(
        &mut self,
        block_id: BlockId,
        expression: impl Into<Option<Box<Expression<'source>>>>,
        scope: &mut Scope<'_, 'source>,
    ) -> Result<(), Error<'source>> {
        // Shortcut for re-indexing self.blocks.
        // This is necessary because add_block etc take &mut self.
        macro_rules! block {
            () => {
                self.blocks[block_id as usize]
            };
        }
        macro_rules! binop {
            ($instruction:expr, $token:expr) => {{
                scope.stack_pointer -= 1;
                block!()
                    .at(token_range($token, self.source))
                    .push($instruction);
            }};
        }
        let Some(expression) = expression.into() else {
            scope.stack_pointer += 1;
            // This expression has no tokens
            // so this instruction can't have a position.
            block!().push_positionless(Instruction::PushUnit);
            return Ok(());
        };
        let (_first_token, _last_token, diagnostics, nodes) = Expression::destructure(expression);
        try_validate(diagnostics)?;
        for node in nodes {
            match node {
                Node::Unit(open_paren, close_paren) => {
                    scope.stack_pointer += 1;
                    block!()
                        .at(token_range(open_paren, self.source)
                            .merge(&token_range(close_paren, self.source)))
                        .push(Instruction::PushUnit);
                }
                Node::Number(token) => {
                    let integer = token
                        .origin
                        .parse()
                        .map_err(|e| Error::InvalidInteger(token, e))?;
                    scope.stack_pointer += 1;
                    block!()
                        .at(token_range(token, self.source))
                        .push(Instruction::PushI64(integer));
                }
                Node::String(string_token) => {
                    // trim starting and ending quotes.
                    // adjust this if additional string formats are added.
                    let string = self.create_string(
                        string_token
                            .resolve()
                            .map_err(|e| Error::InvalidString(string_token, e))?,
                    )?;
                    scope.stack_pointer += 1;
                    block!()
                        .at(token_range(string_token, self.source))
                        .push(Instruction::PushString(string));
                }
                Node::Variable(token) => {
                    let value = scope
                        .get(
                            &token
                                .resolve()
                                .map_err(|e| Error::InvalidIdentifier(token, e))?,
                        )
                        .ok_or(Error::UndefinedSymbol(token))?;
                    scope.stack_pointer += 1;
                    block!()
                        .at(token_range(token, self.source))
                        .push(Instruction::Clone(value));
                }
                Node::Add(t) => binop!(Instruction::Add, t),
                Node::Sub(t) => binop!(Instruction::Sub, t),
                Node::Mul(t) => binop!(Instruction::Mul, t),
                Node::Div(t) => binop!(Instruction::Div, t),
                Node::Tuple(t) => binop!(Instruction::Tuple, t),
                Node::Call(t) => binop!(Instruction::Call, t),
                Node::Pipe(t) => binop!(Instruction::Pipe, t),
                Node::BitwiseAnd(t) => binop!(Instruction::BitwiseAnd, t),
                Node::BitwiseOr(t) => binop!(Instruction::BitwiseOr, t),
                Node::BitwiseXor(t) => binop!(Instruction::BitwiseXor, t),
                Node::EqualTo(t) => binop!(Instruction::EqualTo, t),
                Node::NotEqualTo(t) => binop!(Instruction::NotEqualTo, t),
                Node::Greater(t) => binop!(Instruction::Greater, t),
                Node::GreaterEqual(t) => binop!(Instruction::GreaterEqual, t),
                Node::Lesser(t) => binop!(Instruction::Lesser, t),
                Node::LesserEqual(t) => binop!(Instruction::LesserEqual, t),
                Node::LogicalAnd(t) => binop!(Instruction::LogicalAnd, t),
                Node::LogicalOr(t) => binop!(Instruction::LogicalOr, t),
                // Unaries
                // These do not move the stack,
                // and say "+= 0" to make this clear.
                Node::Positive(_) => {
                    scope.stack_pointer += 0;
                    // + is a no-op
                }
                Node::Negative(t) => {
                    scope.stack_pointer += 0;
                    block!()
                        .at(token_range(t, self.source))
                        .push(Instruction::Negative);
                }
                Node::Annotation(_) => {
                    scope.stack_pointer += 0;
                    // annotations are a no-op
                }
                Node::Deref(t) => {
                    scope.stack_pointer += 0;
                    block!()
                        .at(token_range(t, self.source))
                        .push(Instruction::Deref);
                }
                Node::Name { name, colon_token } => {
                    scope.stack_pointer += 0;
                    let range = token_range(colon_token, self.source);
                    if name.lexigram == Lexigram::Discard {
                        block!().at(range).push(Instruction::Nest);
                    } else {
                        let s = self.create_string(
                            name.resolve()
                                .map_err(|e| Error::InvalidIdentifier(name, e))?,
                        )?;
                        block!().at(range).push(Instruction::Name(s));
                    }
                }

                Node::Block(block) => {
                    self.add_block(block_id, block, scope.child())?;
                    scope.stack_pointer += 1;
                }
                Node::Bool(boolean, t) => {
                    scope.stack_pointer += 1;
                    block!().at(token_range(t, self.source)).push(if boolean {
                        Instruction::PushTrue
                    } else {
                        Instruction::PushFalse
                    });
                }
                Node::Bind(t) => {
                    let range = token_range(t, self.source);
                    if let Some(bind) = scope.get_bind() {
                        block!()
                            .at(range)
                            .push(Instruction::Clone(bind))
                            .push(Instruction::Bind);
                        scope.stack_pointer += 0;
                    } else {
                        block!().at(range).push(Instruction::Yield);
                    }
                }
                Node::If(if_block) => {
                    try_validate(if_block.diagnostics)?;
                    let range = token_range(if_block.if_token, self.source);
                    self.add_expression(block_id, if_block.condition, scope)?;
                    block!().at(range).push(Instruction::If(0));
                    scope.stack_pointer -= 1;
                    let if_destination = block!().len() - size_of::<ProgramCounter>();
                    self.add_block(block_id, if_block.first, scope.child())?;

                    // the first block always returns a value (though it may be implicit unit)
                    // so there always needs to be an else block with some value as well,
                    // but an empty else block will merely return unit.

                    // This jump is the last instruction of the first block--
                    // it skips over else.
                    block!().at(range).push(Instruction::Jump(0));
                    let jump_destination = block!().len() - size_of::<ProgramCounter>();

                    // Now that the first block is complete,
                    // we can fill in the conditional jump's destination.
                    resolve_jump(&mut block!(), if_destination);
                    self.add_block(block_id, if_block.second, scope.child())?;

                    resolve_jump(&mut block!(), jump_destination);
                    scope.stack_pointer += 1;
                }
                Node::Field {
                    dot_token: _,
                    index,
                } => {
                    let instruction = match index {
                        Token {
                            lexigram: Lexigram::Ident,
                            ..
                        } => {
                            let s = self.create_string(
                                index
                                    .resolve()
                                    .map_err(|e| Error::InvalidIdentifier(index, e))?,
                            )?;
                            Instruction::PushString(s)
                        }
                        Token {
                            lexigram: Lexigram::Number,
                            origin,
                        } => {
                            let integer = origin
                                .parse()
                                .map_err(|e| Error::InvalidInteger(index, e))?;
                            Instruction::PushI64(integer)
                        }
                        _ => {
                            panic!("expected an identifier or number in field index, got {index:?}")
                        }
                    };
                    block!()
                        .at(token_range(index, self.source))
                        .push(instruction)
                        .push(Instruction::Index);
                    // the stack pointer does not move by the end,
                    // because while Index pops twice, we performed one of the pushes ourselves.
                    scope.stack_pointer += 0;
                }
                Node::Enum(enumeration) => {
                    try_validate(enumeration.diagnostics)?;
                    self.add_expression(block_id, enumeration.variants, scope)?;
                    // at this point, the stack has grown by 2 + statics.
                    // however only the variants (bottom of the stack) are accounted for in our scope,
                    // and the resulting enum will replace it.
                    scope.stack_pointer += 0;
                    self.blocks[block_id as usize]
                        .at(token_range(enumeration.enum_token, self.source))
                        .push(Instruction::PushEnum);
                }
                Node::Match(match_expression) => {
                    let (_match_token, expression, _then_token, _end_token, diagnostics, cases) =
                        Match::destructure(match_expression);
                    try_validate(diagnostics)?;
                    let subject = scope.stack_pointer;
                    self.add_expression(block_id, expression, scope)?;
                    let jump_locations = cases
                        .map(|case| {
                            let scope = &mut scope.child();
                            // There isn't really a good place to anchor the generated instructions to,
                            // but i think it's best to use something.
                            let range = token_range(
                                case.arrow_token
                                    .expect("valid enum cases should have an arrow token"),
                                self.source,
                            );
                            self.blocks[block_id as usize]
                                .at(range)
                                .push(Instruction::Clone(subject));
                            scope.stack_pointer += 1;
                            self.add_expression(block_id, case.case, scope)?;
                            self.blocks[block_id as usize]
                                .at(range)
                                .push(Instruction::Matches)
                                .push(Instruction::If(0));
                            scope.stack_pointer -= 2;
                            let if_location =
                                self.blocks[block_id as usize].len() - size_of::<ProgramCounter>();

                            assert_eq!(scope.stack_pointer - 1, subject);
                            if let Some(binding) = case.binding {
                                self.add_binding(block_id, binding, scope)?;
                            }
                            self.add_expression(block_id, case.expression, scope)?;
                            self.blocks[block_id as usize]
                                .at(range)
                                .push(Instruction::Collapse(subject))
                                .push(Instruction::Jump(0));
                            resolve_jump(&mut self.blocks[block_id as usize], if_location);
                            Ok(self.blocks[block_id as usize].len() - size_of::<ProgramCounter>())
                        })
                        .collect::<Result<Box<[usize]>, Error>>()?;
                    for jump_location in jump_locations {
                        resolve_jump(&mut self.blocks[block_id as usize], jump_location);
                    }
                }
            }
        }
        Ok(())
    }
}

#[derive(Default)]
struct Scope<'parent, 'source> {
    parent: Option<&'parent Scope<'parent, 'source>>,

    stack_pointer: StackPointer,
    bindings: Vec<(Cow<'source, str>, StackPointer)>,
    bind_function: Option<StackPointer>,
}

impl<'parent, 'source> Scope<'parent, 'source> {
    fn get(&self, k: &'source str) -> Option<StackPointer> {
        self.bindings
            .iter()
            // Use most recent binding
            .rev()
            .find(|(x, _)| *x == k)
            .map(|(_, x)| x)
            .copied()
            .or_else(|| {
                self.parent
                    .and_then(|parent| parent.get(k))
                    .or_else(|| builtins::from_str(k))
            })
    }

    fn insert(&mut self, k: impl Into<Cow<'source, str>>) {
        self.bindings.push((
            k.into(),
            self.stack_pointer
                .checked_sub(1)
                .expect("attempted to assign variable while stack was empty"),
        ));
    }

    fn get_bind(&self) -> Option<StackPointer> {
        self.bind_function
            .or_else(|| self.parent.and_then(|parent| parent.get_bind()))
    }

    fn child(&'parent self) -> Self {
        Self {
            parent: Some(self),
            stack_pointer: self.stack_pointer,
            ..Default::default()
        }
    }

    /// Removes all variable bindings from this scope
    /// and creates a new scope which begins with them.
    ///
    /// The new scope will not inherit the original scope's bind function.
    fn promote(&mut self) -> Self {
        let lost_size = self.parent.map_or(0, |x| x.stack_pointer);
        let mut new_bindings = Vec::new();
        mem::swap(&mut self.bindings, &mut new_bindings);
        for binding in &mut new_bindings {
            binding.1 -= lost_size;
        }
        Self {
            parent: None,
            stack_pointer: self.stack_pointer - lost_size,
            bindings: new_bindings,
            bind_function: None,
        }
    }
}