//! Tools for generating executable [`ByteCode`] from a project's abstract syntax tree.
//! 
//! To generate bytecode from a project, you can use [`ByteCode::compile`].

use std::prelude::v1::*;
use std::collections::{BTreeMap, VecDeque};
use std::rc::Rc;
use std::mem;

#[cfg(feature = "std")]
use std::io::{self, Write};

#[cfg(feature = "serde")]
use serde::{Serialize, Deserialize};

use superslice::Ext;
use monostate::MustBeU128;
use num_traits::FromPrimitive;
use bin_pool::BinPool;

use crate::*;
use crate::meta::*;
use crate::runtime::{Color, Number, NumberError, Event, KeyCode, Property, PrintStyle, Type, CustomTypes, System};

/// Number of bytes to display on each line of a hex dump
#[cfg(feature = "std")]
const BYTES_PER_LINE: usize = 10;

/// Max number of shrinking cycles to apply to variable width encoded values in an output binary
const SHRINK_CYCLES: usize = 3;

/// A NetsBlox project compile error generated by [`ByteCode::compile`].
#[derive(Debug)]
pub enum CompileError<'a> {
    UnsupportedStmt { kind: &'a ast::StmtKind },
    UnsupportedExpr { kind: &'a ast::ExprKind },
    UnsupportedEvent { kind: &'a ast::HatKind },
    BadKeycode { key: &'a str },
    InvalidLocation { loc: &'a str },
    BadNumber { error: NumberError },
    UndefinedRef { value: &'a ast::Value },
    CurrentlyUnsupported { info: String },
    InvalidBlock { loc: Option<&'a str> },
}
impl From<NumberError> for CompileError<'_> { fn from(error: NumberError) -> Self { Self::BadNumber { error } } }

#[derive(Clone, Copy, Debug, FromPrimitive)]
#[repr(u8)]
pub(crate) enum Relation {
    Equal,
    NotEqual,
    Less,
    LessEq,
    Greater,
    GreaterEq,
}

#[derive(Clone, Copy, Debug, FromPrimitive)]
#[repr(u8)]
pub(crate) enum BinaryOp {
    Add, Sub, Mul, Div, Mod, Pow, Log, Atan2,
    SplitBy,
    Range, Random,
    StrGet,
}
#[derive(Clone, Copy, Debug, FromPrimitive)]
#[repr(u8)]
pub(crate) enum UnaryOp {
    Not,
    Abs, Neg,
    Sqrt,
    Round, Floor, Ceil,
    Sin, Cos, Tan,
    Asin, Acos, Atan,
    SplitLetter, SplitWord, SplitTab, SplitCR, SplitLF, SplitCsv, SplitJson,
    StrLen,
    StrGetLast, StrGetRandom,
    UnicodeToChar, CharToUnicode,
}

impl From<Relation> for Instruction<'_> { fn from(relation: Relation) -> Self { Self::Cmp { relation } } }
impl From<BinaryOp> for Instruction<'_> { fn from(op: BinaryOp) -> Self { Self::BinaryOp { op } } }
impl From<UnaryOp> for Instruction<'_> { fn from(op: UnaryOp) -> Self { Self::UnaryOp { op } } }

#[derive(Clone, Copy, Debug, FromPrimitive)]
#[repr(u8)]
pub(crate) enum VariadicOp {
    Add, Mul, Min, Max,
    StrCat,
    MakeList, ListCat,
}
#[derive(Clone, Copy, Debug)]
#[repr(u8)]
pub(crate) enum VariadicLen {
    Fixed(usize), Dynamic,
}
impl BinaryRead<'_> for VariadicLen {
    fn read(code: &[u8], data: &[u8], start: usize) -> (Self, usize) {
        match BinaryRead::read(code, data, start) {
            (0, aft) => (VariadicLen::Dynamic, aft),
            (x, aft) => (VariadicLen::Fixed(x - 1), aft),
        }
    }
}
impl BinaryWrite for VariadicLen {
    fn append(val: &Self, code: &mut Vec<u8>, data: &mut BinPool, relocate_info: &mut Vec<RelocateInfo>) {
        let raw = match val { VariadicLen::Fixed(x) => x + 1, VariadicLen::Dynamic => 0 };
        BinaryWrite::append(&raw, code, data, relocate_info)
    }
}

#[derive(Clone, Copy, Debug, FromPrimitive)]
#[repr(u8)]
pub(crate) enum BasicType {
    Number, String, Bool, List, Entity, Image, Audio,
}
impl BasicType {
    pub fn to_type<C: CustomTypes<S>, S: System<C>>(self) -> Type<C, S> {
        match self {
            BasicType::Number => Type::Number,
            BasicType::String => Type::String,
            BasicType::Bool => Type::Bool,
            BasicType::List => Type::List,
            BasicType::Entity => Type::Entity,
            BasicType::Image => Type::Image,
            BasicType::Audio => Type::Audio,
        }
    }
}

pub(crate) enum InternalInstruction<'a> {
    /// Triggers an error when encountered.
    /// This is an internal value that is only used to denote incomplete linking results for better testing.
    /// Properly-linked byte code should not contain this value.
    Illegal,
    /// A special instruction which is used by the linker to simulate inserting multiple instructions at a single instruction position.
    /// After linking, this variant will not be present in the resulting binary.
    /// Notably, these packed instructions must be a single logical step, because addressing is only allowed at the [`InternalInstruction`] level.
    Packed(Vec<Instruction<'a>>),
    /// A valid instruction that will be present in the resulting binary.
    Valid(Instruction<'a>),
}
impl<'a> From<Instruction<'a>> for InternalInstruction<'a> { fn from(ins: Instruction<'a>) -> Self { Self::Valid(ins) } }

#[derive(Debug)]
#[repr(u8)]
pub(crate) enum Instruction<'a> {
    /// Explicitly trigger a yield point. This instruction is otherwise a no-op.
    Yield,
    /// Marks the start of a warp section. Note that warp sections can be nested.
    WarpStart,
    /// Marks the end of a warp section started by [`Instruction::WarpStart`].
    WarpStop,

    /// Pushes 1 bool value to the value stack.
    PushBool { value: bool },
    /// Pushes 1 number value to the value stack. This is a more compact encoding than [`Instruction::PushNumber`].
    PushInt { value: i32 },
    /// Pushes 1 number value to the value stack.
    PushNumber { value: f64 },
    /// Pushes 1 color value (encoded as an unsigned argb integer) to the value stack.
    PushColor { value: Color },
    /// Pushes 1 string value to the value stack.
    PushString { value: &'a str },
    /// Pushes 1 value to the value stack, as looked up from the current execution context.
    PushVariable { var: &'a str },
    /// Pushes a reference to a named entity onto the value stack.
    PushEntity { name: &'a str },
    /// Pushes a reference to the current running entity onto the value stack.
    PushSelf,
    /// Consumes `count` values from the value stack and discards them.
    PopValue,

    /// Pushes 1 value onto the value stack, which is a copy of item `top_index` from the value stack.
    /// The top of the stack has `top_index == 0`, the item below it has `top_index == 1`, and so on.
    DupeValue { top_index: u8 },
    /// Swaps two values in the value stack, as determined by the specified top index values (see [`Instruction::DupeValue`].
    SwapValues { top_index_1: u8, top_index_2: u8 },

    /// Consumes 1 value from the value stack and pushes a boolean denoting if the value was (exactly) the specified type.
    TypeQuery { ty: BasicType },
    /// Consumes 1 value from the value stack and pushes its bool coercion value onto the stack.
    ToBool,
    /// Consumes 1 value from the value stack and pushes its number coercion value onto the stack.
    ToNumber,

    /// Consumes two values, `list` and `item`, from the value stack and constructs a new list starting with `item` and then containing all the values of `list`.
    /// The new list is pushed onto the value stack.
    ListCons,
    /// Consumes one value, `list`, from the value stack and returns a new list containing all the items of `list` except the first.
    /// The new list is pushed onto the value stack.
    ListCdr,

    /// Consumes two values, `list` and `item`, from the value stack and pushes the index of `item` in `list` (or 0 if not present) onto the value stack.
    /// Note that normal Snap!-style (deep) equality is used to test for the presence of the item.
    ListFind,
    /// Consumes two values, `item` and `list`, from the value stack and pushes a boolean representing of `list` contains `item` onto the value stack.
    /// Note that normal Snap!-style (deep) equality is used to test for the presence of the item.
    ListContains,

    /// Consumes 1 value, `list`, from the value stack and pushes a bool representing if the list is empty onto the value stack.
    ListIsEmpty,
    /// Consumes 1 value, `list`, from the value stack and pushes the length of the list onto the value stack.
    ListLength,
    /// Consumes 1 value, `list`, from the value stack and pushes a list containing the dimensions of the list onto the value stack.
    ListDims,
    /// Consumes 1 value, `list`, from the value stack and pushes the number of dimensions of the list onto the value stack.
    ListRank,

    /// Consumes 1 value, `list`, from the value stack and pushes its reversed version onto the value stack.
    ListRev,
    /// Consumes 1 value, `list`, from the value stack and pushes a flattened list containing all the same values in order onto the value stack.
    ListFlatten,
    /// Consumes `len` values from the value stack (in reverse order) representing target dimensions, as well as another value, `list`.
    /// Pushes a new tensor (list) with the desired dimensions by sourcing from `list` (with cyclic repetition) onto the value stack.
    ListReshape { len: VariadicLen },
    /// Consumes `len` values from the value stack (in reverse order) representing source lists.
    /// Pushes a new list representing the cartesian product of the source lists onto the value stack.
    ListCartesianProduct { len: VariadicLen },

    /// Consumes 1 value, `list`, from the value stack and pushes its JSON-encoded string representation onto the value stack.
    ListJson,
    /// Consumes 1 value, `list`, from the value stack and pushes a list of its columns onto the value stack. This is a more generalized transpose operation.
    ListColumns,
    /// Consumes 1 value, `list`, from the value stack and pushes a string composed of its elements separated by new line characters.
    ListLines,

    /// Consumes three values, `list`, `index`, and `value, from the value stack and inserts `value` at position `index` of `list`.
    ListInsert,
    /// Consumes two values, `list` and `value`, from the value stack and inserts `value` at the end of `list`.
    ListInsertLast,
    /// Consumes two values, `list` and `value`, from the values stack and inserts `value` at a random position in the list.
    ListInsertRandom,

    /// Consumes two values, `list` and `index`, from the value stack and pushes the value `list[index]` onto the value stack.
    ListGet,
    /// Consumes 1 value, `list`, from the value stack and pushes the last item in the list onto the value stack.
    ListGetLast,
    /// Consumes 1 value, `list`, from the value stack and pushes a random item from the list onto the value stack.
    ListGetRandom,

    /// Consumes three values, `value`, `list`, and `index`, from the value stack and assigns `list[index] = value`.
    ListAssign,
    /// Consumes two values, `value` and `list`, from the value stack and assigns `value` to the last position in the list.
    ListAssignLast,
    /// Consumes two values, `value` and `list`, from the value stack and assigns `value` to a random position in the list.
    ListAssignRandom,

    /// Consumes two values, `list` and `index`, from the value stack and deletes item `index` from `list`.
    ListRemove,
    /// Consumes one value, `list`, from the value stack and deletes the last item from it.
    ListRemoveLast,
    /// Consumes one value, `list`, from the value stack and deletes all elements from it.
    ListRemoveAll,

    /// Consumes one value, `list`, from the value stack.
    /// If the list is empty, jumps to the specified position, otherwise pops the first value from the list and pushes it to the value stack.
    ListPopFirstOrElse { goto: usize },

    /// Consumes 2 values, `b` and `a`, from the value stack, and pushes the value `f(a, b)` onto the value stack.
    BinaryOp { op: BinaryOp },
    /// Consumes `len` values from the value stack (in reverse order) and combines them into one value based on `op`.
    VariadicOp { op: VariadicOp, len: VariadicLen },
    /// Consumes 2 values, `b` and `a`, from the value stack, and pushes the (boolean) result of the comparison onto the value stack,
    Cmp { relation: Relation },
    /// Consumes 2 values, `b` and `a`, from the value stack, and pushes the (boolean) result of a reference equality check onto the value stack.
    RefEq,
    /// Consumes 1 value, `x`, from the value stack, and pushes the value `f(x)` onto the value stack.
    UnaryOp { op: UnaryOp },

    /// Re/Declares a set of local variables, which are initialized to 0.
    /// Note that this is not equivalent to assigning a value of zero to the variable due to the potential issue of [`Shared::Aliased`].
    /// A new, [`Shared::Unique`] local variable must be created.
    DeclareLocal { var: &'a str },
    /// Initializes an upvar of the given name.
    /// This should be called by a custom block, which should supply the name of its upvar parameter.
    /// Upvar parameters are passed the name of the variable in the outer scope to link to (which this instruction does).
    InitUpvar { var: &'a str },
    /// Consumes 1 value from the value stack and assigns it to the specified variable.
    Assign { var: &'a str },
    /// Consumes 1 value, `b` from the value stack, fetches the variable `a`, and assigns it `f(a, b)`.
    /// Equivalent to fetching the variable, performing the operation, and re-assigning the new value, but is atomic.
    BinaryOpAssign { var: &'a str, op: BinaryOp },

    /// Creates or destroys a watcher for the given variable.
    /// If `create` is true, the process will emit a request to create a new watcher.
    /// If `create` is false, the process will emit a request to remove a watcher.
    /// In either case, a weak alias to the watched variable is created.
    /// It is up to the executor to deduplicate watchers to the same variable, if needed.
    Watcher { create: bool, var: &'a str },
    /// Generate a pause request and return it to the executor.
    Pause,

    /// Unconditionally jumps to the given location.
    Jump { to: usize },
    /// Pops a value from the value stack and jumps to the given location if its truthyness value is equal to `when`
    ConditionalJump { to: usize, when: bool },

    /// Pushes 1 string value onto the meta stack.
    MetaPush { value: &'a str },

    /// Consumes `params` values from the meta stack (in reverse order) which are names of parameters to pass.
    /// Then consumes `params` arguments from the value stack (in reverse order of the listed params) to assign to a new symbol table.
    /// Pushes the symbol table and return address to the call stack, and finally jumps to the given location.
    Call { pos: usize, params: usize },
    /// Consumes `captures` values from the meta stack (in reverse order), and then `params` values from the meta stack, each representing symbol names.
    /// Then creates a closure object with the given information.
    /// Captures are looked up and bound immediately based on the current execution context.
    MakeClosure { pos: usize, params: usize, captures: usize },
    /// Consumes `args` values, and another value, `closure`, from the value stack and calls the closure with the given arguments.
    /// If `new_entity` is true, consumes an additional value, `entity`, which is the target entity for the new execution context (otherwise the current entity is used).
    /// It is an error if the number of supplied arguments does not match the number of parameters.
    CallClosure { new_entity: bool, args: usize },
    /// Consumes `args` values, and another value, `closure`, from the value stack and forks a new process that invokes the closure with the given arguments.
    /// It is an error if the number of supplied arguments does not match the number of parameters.
    ForkClosure { args: usize },
    /// Pops a return address from the call stack and jumps to it.
    /// The return value is left on the top of the value stack.
    /// If the call stack is empty, this instead terminates the process
    /// with the reported value being the (only) value remaining in the value stack.
    Return,

    /// Pushes a new error handler onto the handler stack.
    PushHandler { pos: usize, var: &'a str },
    /// Pops an error handler from the handler stack.
    PopHandler,
    /// Consumes 1 value, msg, from the value stack and converts it into a hard error.
    Throw,

    /// Consumes `args` values from the meta stack and value stack, representing arguments.
    /// Then calls the given RPC, awaits the result, and pushes the return value onto the value stack.
    CallRpc { service: &'a str, rpc: &'a str, args: usize },
    /// Pushes the last RPC error message onto the value stack.
    PushRpcError,

    /// Consumes `len` values (in reverse order) representing arguments to a system call.
    /// Consumes 1 addition value representing the system call name.
    /// Invokes the given syscall, awaits the result, and pushes the result onto the value stack.
    Syscall { len: VariadicLen },
    /// Pushes the last syscall error message onto the value stack.
    PushSyscallError,

    /// Consumes 1 value from the value stack, `msg_type`, and broadcasts a message to all scripts.
    /// The `wait` flag can be set to denote that the broadcasting script should wait until all receiving scripts have terminated.
    /// If `target` is `true`, an extra value, `target`, is popped from the value stack (first) and represents the target of the message.
    SendLocalMessage { wait: bool, target: bool },
    /// Pushes the name of the currently-received message onto the value stack.
    PushLocalMessage,

    /// Consumes 1 value `msg` from the value stack and prints it to the stored printer.
    Print { style: PrintStyle },
    /// Consumes 1 value, `prompt`, from the value stack and uses it as a query to get input from the user.
    /// The result is NOT stored on the value stack, and instead [`Instruction::PushAnswer`] must be used to retrieve the result.
    Ask,
    /// Pushes the most recent answer from an execution of [`Instruction::Ask`] onto the value stack, or empty string if no question has yet been asked.
    /// Note that the most recent answer is a process-local value, so this cannot retrieve the answer to a question asked by another process.
    PushAnswer,

    /// Resets the process-local timer value to the current system time.
    ResetTimer,
    /// Gets the current timer value (in seconds) and pushes its value onto the value stack.
    PushTimer,
    /// Consumes one value, `secs`, from the value stack and asynchronously waits for that amount of time to elapse.
    /// Non-positive sleep times are ignored, but still generate a yield point.
    Sleep,

    /// Consumes 1 value, `target` from the value stack, which is either a single or a list of targets.
    /// Then consumes `values` values from the value stack and meta stack, representing the fields of a message packet to send to (each) target.
    /// The `expect_reply` flag denotes if this is a blocking operation that awaits a response from the target(s).
    /// If `expect_reply` is true, the reply value (or empty string on timeout) is pushed onto the value stack.
    SendNetworkMessage { msg_type: &'a str, values: usize, expect_reply: bool },
    /// Consumes 1 value, `value`, from the value stack and sends it as the response to a received message.
    /// It is not an error to reply to a message that was not expecting a reply, in which case the value is simply discarded.
    SendNetworkReply,

    /// Pushes the current value of a property onto the value stack.
    PushProperty { prop: Property },
    /// Consumes 1 value, `value`, and assigns it to the specified property.
    SetProperty { prop: Property },
    /// Consumes 1 value, `delta`, and adds its value to the specified property.
    ChangeProperty { prop: Property },

    /// Pushes a reference to the current costume onto the value stack.
    PushCostume,
    /// Pushes the current costume number onto the value stack (or zero if using no costume or a non-static costume for the given entity).
    PushCostumeNumber,
    /// Pushes a shallow copy of the entity's list of static costumes onto the value stack.
    PushCostumeList,
    /// Consumes 1 value, `costume`, from the value stack and assigns it as the current costume.
    /// This can be an image or the name of a static costume on the entity.
    /// Empty string can be used to remove the current costume.
    SetCostume,
    /// If using a static costume, advances to the next costume (if one exists).
    /// If using dynamic costumes or no costume, does nothing.
    NextCostume,

    /// Pops one value, `target`, from the value stack and pushes a clone of entity `target` onto the value stack.
    Clone,

    /// Clears all graphic effects on the entity.
    ClearEffects,

    /// Consumes 2 values, `y` and `x`, and asynchronously moves the entity to that position.
    GotoXY,
    /// Consumes 1 value, `target`, and asynchronously moves the entity to the target.
    /// The target can be an entity or an `[x, y]` position.
    Goto,

    /// Consumes 2 values, `y` and `x`, and asynchronously points the entity toward the specified location.
    PointTowardsXY,
    /// Consumes 1 value, `target`, and asynchronously points the entity toward the target.
    /// The target can be an entity or an `[x, y]` position.
    PointTowards,

    /// Consumes 1 value, `dist`, and asynchronously moves the entity forward by that distance (or backwards if negative).
    Forward,

    /// Consumes `args` values (in reverse order) representing arguments to an unknown function.
    /// This is then handed over to the system to fulfill or error out.
    /// The result of the async request is then pushed onto the value stack.
    UnknownBlock { name: &'a str, args: usize },
}

pub(crate) enum RelocateInfo {
    Code { code_addr: usize },
    Data { code_addr: usize },
}

pub(crate) trait BinaryRead<'a>: Sized {
    /// Reads a value from `src` starting at `start`.
    /// Returns the read value and the position of the first byte after the read segment.
    fn read(code: &'a [u8], data: &'a [u8], start: usize) -> (Self, usize);
}
trait BinaryWrite: Sized {
    /// Appends a binary representation of the value to the given buffers.
    /// And address/relocation information that is written will be stored in `relocate_info` in strictly ascending order of code address.
    /// This function is not intended for use outside of [`ByteCode`] linking.
    fn append(val: &Self, code: &mut Vec<u8>, data: &mut BinPool, relocate_info: &mut Vec<RelocateInfo>);
}

impl BinaryRead<'_> for u8 { fn read(code: &[u8], _: &[u8], start: usize) -> (Self, usize) { (code[start], start + 1) } }
impl BinaryWrite for u8 { fn append(val: &Self, code: &mut Vec<u8>, _: &mut BinPool, _: &mut Vec<RelocateInfo>) { code.push(*val) } }

impl BinaryRead<'_> for bool { fn read(code: &[u8], _: &[u8], start: usize) -> (Self, usize) { (code[start] != 0, start + 1) } }
impl BinaryWrite for bool { fn append(val: &Self, code: &mut Vec<u8>, _: &mut BinPool, _: &mut Vec<RelocateInfo>) { code.push(if *val { 1 } else { 0 }) } }

macro_rules! read_write_u8_type {
    ($($t:ty),+$(,)?) => {$(
        impl BinaryRead<'_> for $t {
            fn read(code: &[u8], _: &[u8], start: usize) -> (Self, usize) {
                (Self::from_u8(code[start]).unwrap(), start + 1)
            }
        }
        impl BinaryWrite for $t {
            fn append(val: &Self, code: &mut Vec<u8>, _: &mut BinPool, _: &mut Vec<RelocateInfo>) {
                debug_assert_eq!(mem::size_of::<Self>(), 1);
                code.push((*val) as u8)
            }
        }
    )*}
}
read_write_u8_type! { PrintStyle, Property, Relation, BinaryOp, UnaryOp, VariadicOp, BasicType }

fn encode_u64(mut val: u64, out: &mut Vec<u8>, bytes: Option<usize>) {
    let mut blocks = ((64 - val.leading_zeros() as usize + 6) / 7).max(1);
    if let Some(bytes) = bytes {
        debug_assert!(bytes >= blocks);
        blocks = bytes;
    }

    debug_assert!((1..=10).contains(&blocks));
    for _ in 1..blocks {
        out.push((val as u8 & 0x7f) | 0x80);
        val >>= 7;
    }
    debug_assert!(val <= 0x7f);
    out.push(val as u8);
}
fn decode_u64(data: &[u8], start: usize) -> (u64, usize) {
    let (mut val, mut aft) = (0, start);
    for &b in &data[start..] {
        aft += 1;
        if b & 0x80 == 0 { break }
    }
    for &b in data[start..aft].iter().rev() {
        val = (val << 7) | (b & 0x7f) as u64;
    }
    (val, aft)
}

// encodes values as a sequence of bytes of form [1: next][7: bits] in little-endian order.
// if `relocate_info` is provided to `append`, expanded mode is used, which encodes the value with the maximum of 10 bytes.
impl BinaryRead<'_> for u64 {
    fn read(code: &[u8], _: &[u8], start: usize) -> (Self, usize) {
        decode_u64(code, start)
    }
}
impl BinaryWrite for u64 {
    fn append(val: &Self, code: &mut Vec<u8>, _: &mut BinPool, _: &mut Vec<RelocateInfo>) {
        encode_u64(*val, code, None)
    }
}

#[test]
fn test_binary_u64() {
    let mut buf = vec![];
    let tests = [
        (0,                 [0x00].as_slice(),                                                       [0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00].as_slice()),
        (1,                 [0x01].as_slice(),                                                       [0x81, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00].as_slice()),
        (2,                 [0x02].as_slice(),                                                       [0x82, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00].as_slice()),
        (0x53,              [0x53].as_slice(),                                                       [0xd3, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00].as_slice()),
        (0x7f,              [0x7f].as_slice(),                                                       [0xff, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00].as_slice()),
        (0x80,              [0x80, 0x01].as_slice(),                                                 [0x80, 0x81, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x80, 0x00].as_slice()),
        (0x347462356236574, [0xf4, 0xca, 0x8d, 0xb1, 0xb5, 0xc4, 0xd1, 0xa3, 0x03].as_slice(),       [0xf4, 0xca, 0x8d, 0xb1, 0xb5, 0xc4, 0xd1, 0xa3, 0x83, 0x00].as_slice()),
        (u64::MAX >> 1,     [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x7f].as_slice(),       [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x00].as_slice()),
        (u64::MAX,          [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01].as_slice(), [0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0x01].as_slice()),
    ];
    for (v, expect_small, expect_large) in tests {
        for (expect, expanded) in [(expect_small, false), (expect_large, true)] {
            for prefix_bytes in 0..8 {
                buf.clear();
                buf.extend(std::iter::once(0x53).cycle().take(prefix_bytes));
                encode_u64(v, &mut buf, if expanded { Some(10) } else { None });
                assert!(buf[..prefix_bytes].iter().all(|&x| x == 0x53));
                assert_eq!(&buf[prefix_bytes..], expect);
                buf.extend(std::iter::once(0xff).cycle().take(8));
                let (back, aft) = <u64 as BinaryRead>::read(&buf, &[], prefix_bytes);
                assert_eq!(back, v);
                assert_eq!(aft, prefix_bytes + expect.len());
            }
        }
    }
}

// stores the value as u64 by shifting up by one bit and storing a bitwise-not flag in the low order bit.
// the u64 value is then stored using the variable width algorithm for u64.
impl BinaryRead<'_> for i32 {
    fn read(code: &[u8], data: &[u8], start: usize) -> (Self, usize) {
        let (raw, aft) = <u64 as BinaryRead>::read(code, data, start);
        let v = (raw >> 1) as u32;
        (if raw & 1 == 0 { v } else { !v } as i32, aft)
    }
}
impl BinaryWrite for i32 {
    fn append(val: &Self, code: &mut Vec<u8>, data: &mut BinPool, relocate_info: &mut Vec<RelocateInfo>) {
        let v: u64 = ((*val) as u64) << 1;
        BinaryWrite::append(&if v & 0x8000000000000000 == 0 { v } else { !v }, code, data, relocate_info)
    }
}

// encodes a color using exactly 4 bytes (argb encoded integer).
// for typical colors, there's no point in doing anything fancy like variable width encodings.
impl BinaryRead<'_> for Color {
    fn read(code: &[u8], _: &[u8], start: usize) -> (Self, usize) {
        let mut res = [0u8; 4];
        res[..].copy_from_slice(&code[start..start + 4]);
        let [a, r, g, b] = res;
        (Color { r, g, b, a }, start + 4)
    }
}
impl BinaryWrite for Color {
    fn append(val: &Self, code: &mut Vec<u8>, _: &mut BinPool, _: &mut Vec<RelocateInfo>) {
        let Color { r, g, b, a } = *val;
        code.extend_from_slice(&[a, r, g ,b]);
    }
}

#[test]
fn test_binary_i32() {
    let mut buf = vec![];
    let mut discard = (BinPool::new(), vec![]);
    let tests = [
        (0,         [0x00].as_slice()),
        (-1,        [0x01].as_slice()),
        (1,         [0x02].as_slice()),
        (-2,        [0x03].as_slice()),
        (2,         [0x04].as_slice()),
        (0x543245,  [0x8a, 0xc9, 0xa1, 0x05].as_slice()),
        (-0x376224, [0xc7, 0x88, 0xbb, 0x03].as_slice()),
        (-i32::MAX, [0xfd, 0xff, 0xff, 0xff, 0x0f].as_slice()),
        (i32::MAX,  [0xfe, 0xff, 0xff, 0xff, 0x0f].as_slice()),
        (i32::MIN,  [0xff, 0xff, 0xff, 0xff, 0x0f].as_slice()),
    ];
    for (v, expect) in tests {
        for prefix_bytes in 0..8 {
            buf.clear();
            buf.extend(std::iter::once(0x53).cycle().take(prefix_bytes));
            BinaryWrite::append(&v, &mut buf, &mut discard.0, &mut discard.1);
            assert_eq!(discard.0.len(), 0);
            assert_eq!(discard.1.len(), 0);
            assert!(buf[..prefix_bytes].iter().all(|&x| x == 0x53));
            assert_eq!(&buf[prefix_bytes..], expect);
            buf.extend(std::iter::once(0xff).cycle().take(8));
            let (back, aft) = <i32 as BinaryRead>::read(&buf, &[], prefix_bytes);
            assert_eq!(back, v);
            assert_eq!(aft, prefix_bytes + expect.len());
        }
    }
}

impl BinaryRead<'_> for f64 {
    fn read(code: &[u8], data: &[u8], start: usize) -> (Self, usize) {
        let (v, aft) = <u64 as BinaryRead>::read(code, data, start);
        (f64::from_bits(v.swap_bytes()), aft)
    }
}
impl BinaryWrite for f64 {
    fn append(val: &Self, code: &mut Vec<u8>, data: &mut BinPool, relocate_info: &mut Vec<RelocateInfo>) {
        BinaryWrite::append(&val.to_bits().swap_bytes(), code, data, relocate_info)
    }
}

impl BinaryRead<'_> for usize {
    fn read(code: &[u8], data: &[u8], start: usize) -> (Self, usize) {
        let (v, aft) = <u64 as BinaryRead>::read(code, data, start);
        debug_assert!(v <= usize::MAX as u64);
        (v as usize, aft)
    }
}
impl BinaryWrite for usize {
    fn append(val: &Self, code: &mut Vec<u8>, data: &mut BinPool, relocate_info: &mut Vec<RelocateInfo>) {
        BinaryWrite::append(&(*val as u64), code, data, relocate_info)
    }
}

impl<'a> BinaryRead<'a> for &'a str {
    fn read(code: &'a [u8], data: &'a [u8], start: usize) -> (Self, usize) {
        let (data_pos, aft) = <usize as BinaryRead>::read(code, data, start);
        let (data_len, aft) = <usize as BinaryRead>::read(code, data, aft);
        (std::str::from_utf8(&data[data_pos..data_pos + data_len]).unwrap(), aft)
    }
}

impl<'a> BinaryRead<'a> for Instruction<'a> {
    fn read(code: &'a [u8], data: &'a [u8], start: usize) -> (Self, usize) {
        macro_rules! read_prefixed {
            (Instruction::$root:ident) => {
                (Instruction::$root, start + 1)
            };
            (Instruction::$root:ident { $($tt:tt)* } $(: $($vals:ident),+$(,)? )?) => {{
                #[allow(unused_mut)]
                let mut parsing_stop = start + 1;
                $($(let $vals = {
                    let x = BinaryRead::read(code, data, parsing_stop);
                    parsing_stop = x.1;
                    x.0
                };)*)?
                (Instruction::$root { $($tt)* $($($vals),+ )? }, parsing_stop)
            }};
        }
        match code[start] {
            0 => read_prefixed!(Instruction::Yield),
            1 => read_prefixed!(Instruction::WarpStart),
            2 => read_prefixed!(Instruction::WarpStop),

            3 => read_prefixed!(Instruction::PushBool { value: false }),
            4 => read_prefixed!(Instruction::PushBool { value: true }),

            5 => read_prefixed!(Instruction::PushInt {} : value),
            6 => read_prefixed!(Instruction::PushNumber {} : value),
            7 => read_prefixed!(Instruction::PushColor {} : value),

            8 => read_prefixed!(Instruction::PushString { value: "" }),
            9 => read_prefixed!(Instruction::PushString {} : value),

            10 => read_prefixed!(Instruction::PushVariable {} : var),
            11 => read_prefixed!(Instruction::PushEntity {} : name),
            12 => read_prefixed!(Instruction::PushSelf),

            13 => read_prefixed!(Instruction::PopValue),

            14 => read_prefixed!(Instruction::DupeValue {} : top_index),
            15 => read_prefixed!(Instruction::SwapValues {} : top_index_1, top_index_2),

            16 => read_prefixed!(Instruction::TypeQuery {} : ty),
            17 => read_prefixed!(Instruction::ToBool),
            18 => read_prefixed!(Instruction::ToNumber),

            19 => read_prefixed!(Instruction::ListCons),
            20 => read_prefixed!(Instruction::ListCdr),

            21 => read_prefixed!(Instruction::ListFind),
            22 => read_prefixed!(Instruction::ListContains),

            23 => read_prefixed!(Instruction::ListIsEmpty),
            24 => read_prefixed!(Instruction::ListLength),
            25 => read_prefixed!(Instruction::ListDims),
            26 => read_prefixed!(Instruction::ListRank),

            27 => read_prefixed!(Instruction::ListRev),
            28 => read_prefixed!(Instruction::ListFlatten),
            29 => read_prefixed!(Instruction::ListReshape {} : len),
            30 => read_prefixed!(Instruction::ListCartesianProduct {} : len),

            31 => read_prefixed!(Instruction::ListJson),
            32 => read_prefixed!(Instruction::ListColumns),
            33 => read_prefixed!(Instruction::ListLines),

            34 => read_prefixed!(Instruction::ListInsert),
            35 => read_prefixed!(Instruction::ListInsertLast),
            36 => read_prefixed!(Instruction::ListInsertRandom),

            37 => read_prefixed!(Instruction::ListGet),
            38 => read_prefixed!(Instruction::ListGetLast),
            39 => read_prefixed!(Instruction::ListGetRandom),

            40 => read_prefixed!(Instruction::ListAssign),
            41 => read_prefixed!(Instruction::ListAssignLast),
            42 => read_prefixed!(Instruction::ListAssignRandom),

            43 => read_prefixed!(Instruction::ListRemove),
            44 => read_prefixed!(Instruction::ListRemoveLast),
            45 => read_prefixed!(Instruction::ListRemoveAll),

            46 => read_prefixed!(Instruction::ListPopFirstOrElse {} : goto),

            47 => read_prefixed!(Instruction::Cmp { relation: Relation::Equal }),
            48 => read_prefixed!(Instruction::Cmp { relation: Relation::NotEqual }),
            49 => read_prefixed!(Instruction::Cmp { relation: Relation::Less }),
            50 => read_prefixed!(Instruction::Cmp { relation: Relation::LessEq }),
            51 => read_prefixed!(Instruction::Cmp { relation: Relation::Greater }),
            52 => read_prefixed!(Instruction::Cmp { relation: Relation::GreaterEq }),
            53 => read_prefixed!(Instruction::RefEq),

            54 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Add }),
            55 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Sub }),
            56 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Mul }),
            57 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Div }),
            58 => read_prefixed!(Instruction::BinaryOp {} : op),

            59 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::Add, } : len),
            60 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::Mul, } : len),
            61 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::StrCat, } : len),
            62 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::MakeList, } : len),
            63 => read_prefixed!(Instruction::VariadicOp {} : op, len),

            64 => read_prefixed!(Instruction::UnaryOp { op: UnaryOp::Not }),
            65 => read_prefixed!(Instruction::UnaryOp { op: UnaryOp::Round }),
            66 => read_prefixed!(Instruction::UnaryOp {} : op),

            67 => read_prefixed!(Instruction::DeclareLocal {} : var),
            68 => read_prefixed!(Instruction::InitUpvar {} : var),
            69 => read_prefixed!(Instruction::Assign {} : var),

            70 => read_prefixed!(Instruction::BinaryOpAssign { op: BinaryOp::Add, } : var),
            71 => read_prefixed!(Instruction::BinaryOpAssign {} : var, op),

            72 => read_prefixed!(Instruction::Watcher {} : create, var),
            73 => read_prefixed!(Instruction::Pause),

            74 => read_prefixed!(Instruction::Jump {} : to),
            75 => read_prefixed!(Instruction::ConditionalJump { when: false, } : to),
            76 => read_prefixed!(Instruction::ConditionalJump { when: true, } : to),

            77 => read_prefixed!(Instruction::MetaPush {} : value),

            78 => read_prefixed!(Instruction::Call {} : pos, params),
            79 => read_prefixed!(Instruction::MakeClosure {} : pos, params, captures),
            80 => read_prefixed!(Instruction::CallClosure { new_entity: false, } : args),
            81 => read_prefixed!(Instruction::CallClosure { new_entity: true, } : args),
            82 => read_prefixed!(Instruction::ForkClosure {} : args),
            83 => read_prefixed!(Instruction::Return),

            84 => read_prefixed!(Instruction::PushHandler {} : pos, var),
            85 => read_prefixed!(Instruction::PopHandler),
            86 => read_prefixed!(Instruction::Throw),

            87 => read_prefixed!(Instruction::CallRpc {} : service, rpc, args),
            88 => read_prefixed!(Instruction::PushRpcError),

            89 => read_prefixed!(Instruction::Syscall {} : len),
            90 => read_prefixed!(Instruction::PushSyscallError),

            91 => read_prefixed!(Instruction::SendLocalMessage { wait: false, target: false }),
            92 => read_prefixed!(Instruction::SendLocalMessage { wait: false, target: true }),
            93 => read_prefixed!(Instruction::SendLocalMessage { wait: true, target: false }),
            94 => read_prefixed!(Instruction::SendLocalMessage { wait: true, target: true }),

            95 => read_prefixed!(Instruction::PushLocalMessage),

            96 => read_prefixed!(Instruction::Print { style: PrintStyle::Say }),
            97 => read_prefixed!(Instruction::Print { style: PrintStyle::Think }),
            98 => read_prefixed!(Instruction::Ask),
            99 => read_prefixed!(Instruction::PushAnswer),

            100 => read_prefixed!(Instruction::ResetTimer),
            101 => read_prefixed!(Instruction::PushTimer),
            102 => read_prefixed!(Instruction::Sleep),

            103 => read_prefixed!(Instruction::SendNetworkMessage { expect_reply: false, } : msg_type, values),
            104 => read_prefixed!(Instruction::SendNetworkMessage { expect_reply: true, } : msg_type, values),
            105 => read_prefixed!(Instruction::SendNetworkReply),

            106 => read_prefixed!(Instruction::PushProperty {} : prop),
            107 => read_prefixed!(Instruction::SetProperty {} : prop),
            108 => read_prefixed!(Instruction::ChangeProperty {} : prop),

            109 => read_prefixed!(Instruction::PushCostume),
            110 => read_prefixed!(Instruction::PushCostumeNumber),
            111 => read_prefixed!(Instruction::PushCostumeList),
            112 => read_prefixed!(Instruction::SetCostume),
            113 => read_prefixed!(Instruction::NextCostume),

            114 => read_prefixed!(Instruction::Clone),

            115 => read_prefixed!(Instruction::ClearEffects),

            116 => read_prefixed!(Instruction::GotoXY),
            117 => read_prefixed!(Instruction::Goto),

            118 => read_prefixed!(Instruction::PointTowardsXY),
            119 => read_prefixed!(Instruction::PointTowards),

            120 => read_prefixed!(Instruction::Forward),

            121 => read_prefixed!(Instruction::UnknownBlock {} : name, args),

            _ => unreachable!(),
        }
    }
}
impl BinaryWrite for Instruction<'_> {
    fn append(val: &Self, code: &mut Vec<u8>, data: &mut BinPool, relocate_info: &mut Vec<RelocateInfo>) {
        macro_rules! append_prefixed {
            ($op:literal $(: $($($vals:ident)+),+)?) => {{
                code.push($op);
                $($( append_prefixed!(@single $($vals)+); )*)?
            }};
            (@single move $val:ident) => {{
                relocate_info.push(RelocateInfo::Code { code_addr: code.len() });
                encode_u64(*$val as u64, code, Some(10));
            }};
            (@single move str $val:ident) => {{
                let pool_index = data.add($val.as_bytes());
                relocate_info.push(RelocateInfo::Data { code_addr: code.len() });
                encode_u64(pool_index as u64, code, Some(10));
                BinaryWrite::append(&$val.len(), code, data, relocate_info);
            }};
            (@single $val:ident) => { BinaryWrite::append($val, code, data, relocate_info) };
        }
        match val {
            Instruction::Yield => append_prefixed!(0),
            Instruction::WarpStart => append_prefixed!(1),
            Instruction::WarpStop => append_prefixed!(2),

            Instruction::PushBool { value: false } => append_prefixed!(3),
            Instruction::PushBool { value: true } => append_prefixed!(4),

            Instruction::PushInt { value } => append_prefixed!(5: value),
            Instruction::PushNumber { value } => append_prefixed!(6: value),
            Instruction::PushColor { value } => append_prefixed!(7: value),

            Instruction::PushString { value: "" } => append_prefixed!(8),
            Instruction::PushString { value } => append_prefixed!(9: move str value),

            Instruction::PushVariable { var } => append_prefixed!(10: move str var),
            Instruction::PushEntity { name } => append_prefixed!(11: move str name),
            Instruction::PushSelf => append_prefixed!(12),

            Instruction::PopValue => append_prefixed!(13),

            Instruction::DupeValue { top_index } => append_prefixed!(14: top_index),
            Instruction::SwapValues { top_index_1, top_index_2 } => append_prefixed!(15: top_index_1, top_index_2),

            Instruction::TypeQuery { ty } => append_prefixed!(16: ty),
            Instruction::ToBool => append_prefixed!(17),
            Instruction::ToNumber => append_prefixed!(18),

            Instruction::ListCons => append_prefixed!(19),
            Instruction::ListCdr => append_prefixed!(20),

            Instruction::ListFind => append_prefixed!(21),
            Instruction::ListContains => append_prefixed!(22),

            Instruction::ListIsEmpty => append_prefixed!(23),
            Instruction::ListLength => append_prefixed!(24),
            Instruction::ListDims => append_prefixed!(25),
            Instruction::ListRank => append_prefixed!(26),

            Instruction::ListRev => append_prefixed!(27),
            Instruction::ListFlatten => append_prefixed!(28),
            Instruction::ListReshape { len } => append_prefixed!(29: len),
            Instruction::ListCartesianProduct { len } => append_prefixed!(30: len),

            Instruction::ListJson => append_prefixed!(31),
            Instruction::ListColumns => append_prefixed!(32),
            Instruction::ListLines => append_prefixed!(33),

            Instruction::ListInsert => append_prefixed!(34),
            Instruction::ListInsertLast => append_prefixed!(35),
            Instruction::ListInsertRandom => append_prefixed!(36),

            Instruction::ListGet => append_prefixed!(37),
            Instruction::ListGetLast => append_prefixed!(38),
            Instruction::ListGetRandom => append_prefixed!(39),

            Instruction::ListAssign => append_prefixed!(40),
            Instruction::ListAssignLast => append_prefixed!(41),
            Instruction::ListAssignRandom => append_prefixed!(42),

            Instruction::ListRemove => append_prefixed!(43),
            Instruction::ListRemoveLast => append_prefixed!(44),
            Instruction::ListRemoveAll => append_prefixed!(45),

            Instruction::ListPopFirstOrElse { goto } => append_prefixed!(46: move goto),

            Instruction::Cmp { relation: Relation::Equal } => append_prefixed!(47),
            Instruction::Cmp { relation: Relation::NotEqual } => append_prefixed!(48),
            Instruction::Cmp { relation: Relation::Less } => append_prefixed!(49),
            Instruction::Cmp { relation: Relation::LessEq } => append_prefixed!(50),
            Instruction::Cmp { relation: Relation::Greater } => append_prefixed!(51),
            Instruction::Cmp { relation: Relation::GreaterEq } => append_prefixed!(52),
            Instruction::RefEq => append_prefixed!(53),

            Instruction::BinaryOp { op: BinaryOp::Add } => append_prefixed!(54),
            Instruction::BinaryOp { op: BinaryOp::Sub } => append_prefixed!(55),
            Instruction::BinaryOp { op: BinaryOp::Mul } => append_prefixed!(56),
            Instruction::BinaryOp { op: BinaryOp::Div } => append_prefixed!(57),
            Instruction::BinaryOp { op } => append_prefixed!(58: op),

            Instruction::VariadicOp { op: VariadicOp::Add, len } => append_prefixed!(59: len),
            Instruction::VariadicOp { op: VariadicOp::Mul, len } => append_prefixed!(60: len),
            Instruction::VariadicOp { op: VariadicOp::StrCat, len } => append_prefixed!(61: len),
            Instruction::VariadicOp { op: VariadicOp::MakeList, len } => append_prefixed!(62: len),
            Instruction::VariadicOp { op, len } => append_prefixed!(63: op, len),

            Instruction::UnaryOp { op: UnaryOp::Not } => append_prefixed!(64),
            Instruction::UnaryOp { op: UnaryOp::Round } => append_prefixed!(65),
            Instruction::UnaryOp { op } => append_prefixed!(66: op),

            Instruction::DeclareLocal { var } => append_prefixed!(67: move str var),
            Instruction::InitUpvar { var } => append_prefixed!(68: move str var),
            Instruction::Assign { var } => append_prefixed!(69: move str var),

            Instruction::BinaryOpAssign { var, op: BinaryOp::Add } => append_prefixed!(70: move str var),
            Instruction::BinaryOpAssign { var, op } => append_prefixed!(71: move str var, op),

            Instruction::Watcher { create, var } => append_prefixed!(72: create, move str var),
            Instruction::Pause => append_prefixed!(73),

            Instruction::Jump { to } => append_prefixed!(74: move to),
            Instruction::ConditionalJump { to, when: false } => append_prefixed!(75: move to),
            Instruction::ConditionalJump { to, when: true } => append_prefixed!(76: move to),

            Instruction::MetaPush { value } => append_prefixed!(77: move str value),

            Instruction::Call { pos, params } => append_prefixed!(78: move pos, params),
            Instruction::MakeClosure { pos, params, captures } => append_prefixed!(79: move pos, params, captures),
            Instruction::CallClosure { new_entity: false, args } => append_prefixed!(80: args),
            Instruction::CallClosure { new_entity: true, args } => append_prefixed!(81: args),
            Instruction::ForkClosure { args } => append_prefixed!(82: args),
            Instruction::Return => append_prefixed!(83),

            Instruction::PushHandler { pos, var } => append_prefixed!(84: move pos, move str var),
            Instruction::PopHandler => append_prefixed!(85),
            Instruction::Throw => append_prefixed!(86),

            Instruction::CallRpc { service, rpc, args } => append_prefixed!(87: move str service, move str rpc, args),
            Instruction::PushRpcError => append_prefixed!(88),

            Instruction::Syscall { len } => append_prefixed!(89: len),
            Instruction::PushSyscallError => append_prefixed!(90),

            Instruction::SendLocalMessage { wait: false, target: false } => append_prefixed!(91),
            Instruction::SendLocalMessage { wait: false, target: true } => append_prefixed!(92),
            Instruction::SendLocalMessage { wait: true, target: false } => append_prefixed!(93),
            Instruction::SendLocalMessage { wait: true, target: true } => append_prefixed!(94),

            Instruction::PushLocalMessage => append_prefixed!(95),

            Instruction::Print { style: PrintStyle::Say } => append_prefixed!(96),
            Instruction::Print { style: PrintStyle::Think } => append_prefixed!(97),
            Instruction::Ask => append_prefixed!(98),
            Instruction::PushAnswer => append_prefixed!(99),

            Instruction::ResetTimer => append_prefixed!(100),
            Instruction::PushTimer => append_prefixed!(101),
            Instruction::Sleep => append_prefixed!(102),

            Instruction::SendNetworkMessage { msg_type, values, expect_reply: false } => append_prefixed!(103: move str msg_type, values),
            Instruction::SendNetworkMessage { msg_type, values, expect_reply: true } => append_prefixed!(104: move str msg_type, values),
            Instruction::SendNetworkReply => append_prefixed!(105),

            Instruction::PushProperty { prop } => append_prefixed!(106: prop),
            Instruction::SetProperty { prop } => append_prefixed!(107: prop),
            Instruction::ChangeProperty { prop } => append_prefixed!(108: prop),

            Instruction::PushCostume => append_prefixed!(109),
            Instruction::PushCostumeNumber => append_prefixed!(110),
            Instruction::PushCostumeList => append_prefixed!(111),
            Instruction::SetCostume => append_prefixed!(112),
            Instruction::NextCostume => append_prefixed!(113),

            Instruction::Clone => append_prefixed!(114),

            Instruction::ClearEffects => append_prefixed!(115),

            Instruction::GotoXY => append_prefixed!(116),
            Instruction::Goto => append_prefixed!(117),

            Instruction::PointTowardsXY => append_prefixed!(118),
            Instruction::PointTowards => append_prefixed!(119),

            Instruction::Forward => append_prefixed!(120),

            Instruction::UnknownBlock { name, args } => append_prefixed!(121: move str name, args),
        }
    }
}

/// An interpreter-ready sequence of instructions.
///
/// [`Process`](crate::process::Process) is an execution primitive that can be used to execute generated [`ByteCode`].
///
/// Generated [`ByteCode`] is highly optimized for size and sees frequent breaking changes.
/// Because of this, there is currently no support for touching the actual bytecode itself.
/// If you wish to view the generated bytecode, you may use the [`ByteCode::dump_code`] and [`ByteCode::dump_data`] utilities,
/// a wrapper for which is included in the standard `netsblox-vm` [`cli`](crate::cli).
/// 
/// This type supports serde serialization if the `serde` feature flag is enabled.
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct ByteCode {
    #[allow(dead_code)] tag: MustBeU128<FINGERPRINT>,

    pub(crate) code: Box<[u8]>,
    pub(crate) data: Box<[u8]>,
}

#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub(crate) enum InitValue {
    Bool(bool),
    Number(Number),
    Ref(usize),
}
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub(crate) enum RefValue {
    List(Vec<InitValue>),
    Image(Vec<u8>),
    String(String),
}
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub(crate) struct EntityInitInfo {
    pub(crate) name: String,
    pub(crate) fields: Vec<(String, InitValue)>,
    pub(crate) costumes: Vec<(String, InitValue)>,
    pub(crate) scripts: Vec<(Event, usize)>,

    pub(crate) visible: bool,
    pub(crate) active_costume: Option<usize>,
    pub(crate) size: Number,
    pub(crate) color: (u8, u8, u8, u8),
    pub(crate) pos: (Number, Number),
    pub(crate) heading: Number,
}
/// A structure that stores the initialization state of a project.
/// 
/// When compiling a project via [`ByteCode::compile`], the [`ByteCode`] object will contain all
/// the necessary code and logic to run the project.
/// However, this does not include the state on which the bytecode acts, which only exists at runtime.
/// [`InitInfo`] exists to hold the initial state of a project in a serializable format.
/// 
/// This type supports serde serialization if the `serde` feature flag is enabled.
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct InitInfo {
    #[allow(dead_code)] tag: MustBeU128<FINGERPRINT>,

    pub(crate) proj_name: String,
    pub(crate) ref_values: Vec<RefValue>,
    pub(crate) globals: Vec<(String, InitValue)>,
    pub(crate) entities: Vec<EntityInitInfo>,
}

/// Entity-level [`ScriptInfo`] in a [`ByteCode`] object.
pub struct EntityScriptInfo<'a> {
    pub funcs: Vec<(&'a ast::Function, usize)>,
    pub scripts: Vec<(&'a ast::Script, usize)>,
}
/// Script information in a [`ByteCode`] object.
/// 
/// When a project is compiled via [`ByteCode::compile`], a contiguous stream of bytecode instructions is generated.
/// This object maps each function (block) and script to its final bytecode location,
/// making it possible to execute specific blocks or scripts.
/// 
/// In typical usage, this info is not needed, and is only used internally for generating bytecode.
/// Its primary use would be in executing a single [`Process`](crate::process::Process) rather than an entire [`Project`](crate::project::Project).
pub struct ScriptInfo<'a> {
    pub funcs: Vec<(&'a ast::Function, usize)>,
    pub entities: Vec<(&'a ast::Entity, EntityScriptInfo<'a>)>,
}

/// Location lookup table from bytecode address to original AST location.
/// 
/// When a project is compiled via [`ByteCode::compile`], a stream of instructions is produced.
/// However, this conversion loses the information that would be needed to produce human-readable error locations.
/// This object acts as a map from bytecode location to original AST location in the source project.
/// 
/// This type supports serde serialization if the `serde` feature flag is enabled.
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub struct Locations {
    #[allow(dead_code)] tag: MustBeU128<FINGERPRINT>,

    prefix: String,
    base_token: usize,
    token_data: Vec<u8>,
    locs: Vec<(usize, usize)>,
}
impl Locations {
    fn condense<'a>(orig_locs: BTreeMap<usize, &'a str>) -> Result<Self, CompileError<'a>> {
        if orig_locs.is_empty() {
            return Ok(Self {
                tag: Default::default(),
                prefix: String::new(),
                base_token: 0,
                token_data: Default::default(),
                locs: Default::default(),
            });
        }

        let prefix = {
            let loc = *orig_locs.values().next().unwrap();
            match loc.find('_') {
                Some(x) => loc[..x].to_owned(),
                None => return Err(CompileError::InvalidLocation { loc }),
            }
        };

        let mut token_map = Vec::with_capacity(orig_locs.len());
        for (&pos, &loc) in orig_locs.iter() {
            if !loc.starts_with(&prefix) { return Err(CompileError::InvalidLocation { loc }) }
            debug_assert!(loc[prefix.len()..].starts_with('_'));

            let mut tokens = vec![];
            for token in loc[prefix.len() + 1..].split('_') {
                let v: usize = match token.parse() {
                    Ok(x) => x,
                    Err(_) => return Err(CompileError::InvalidLocation { loc }),
                };
                if v.to_string() != token {
                    return Err(CompileError::InvalidLocation { loc });
                }
                tokens.push(v);
            }
            token_map.push((pos, tokens));
        }

        let base_token = token_map.iter().flat_map(|x| &x.1).copied().min().unwrap_or(0);

        let mut token_data = Vec::with_capacity(token_map.len());
        let mut locs = Vec::with_capacity(token_map.len());
        for (pos, toks) in token_map {
            locs.push((pos, token_data.len()));
            for tok in toks {
                encode_u64((tok - base_token + 1) as u64, &mut token_data, None);
            }
            encode_u64(0, &mut token_data, None); // null terminator
        }

        let res = Self { tag: Default::default(), prefix, base_token, token_data, locs };

        #[cfg(test)]
        {
            for pos in 0..orig_locs.iter().last().unwrap().0 + 16 {
                let expected = orig_locs.range(pos + 1..).next().map(|x| *x.1);
                let actual = res.lookup(pos);
                assert_eq!(expected, actual.as_deref());
            }
        }

        Ok(res)
    }

    /// Looks up a bytecode position and returns the most local block location provided by the ast.
    /// If the ast came from a standard NetsBlox XML file, this is the collab id of the looked up bytecode address.
    /// In other cases, this could be some other localization mechanism for error reporting (e.g., line number and column).
    ///
    /// Note that it is possible for blocks to not have location information,
    /// hence returning the most local location that was provided in the ast.
    pub fn lookup(&self, bytecode_pos: usize) -> Option<String> {
        let mut start = {
            let p = self.locs.lower_bound_by_key(&(bytecode_pos + 1), |x| x.0);
            debug_assert!(p <= self.locs.len());
            self.locs.get(p)?.1
        };

        let mut res = self.prefix.clone();
        loop {
            let (v, aft) = decode_u64(&self.token_data, start);
            if v == 0 { return Some(res) }

            start = aft;
            res.push('_');
            res.push_str(&(v as usize - 1 + self.base_token).to_string());
        }
    }
}

#[derive(Default)]
struct ByteCodeBuilder<'a> {
    ins: Vec<InternalInstruction<'a>>,
    call_holes: Vec<(usize, &'a ast::FnRef, Option<&'a ast::Entity>)>, // (hole pos, function, entity)
    closure_holes: VecDeque<(usize, &'a [ast::VariableDef], &'a [ast::VariableRef], &'a [ast::Stmt], Option<&'a ast::Entity>)>, // (hole pos, params, captures, stmts, entity)
    ins_locations: BTreeMap<usize, &'a str>,
}
impl<'a> ByteCodeBuilder<'a> {
    fn append_simple_ins(&mut self, entity: Option<&'a ast::Entity>, values: &[&'a ast::Expr], op: Instruction<'a>) -> Result<(), CompileError<'a>> {
        for value in values {
            self.append_expr(value, entity)?;
        }
        self.ins.push(op.into());
        Ok(())
    }
    fn append_variadic_op(&mut self, entity: Option<&'a ast::Entity>, src: &'a ast::Expr, op: VariadicOp) -> Result<(), CompileError<'a>> {
        let len = self.append_variadic(src, entity)?;
        self.ins.push(Instruction::VariadicOp { op, len}.into());
        Ok(())
    }
    fn append_variadic(&mut self, src: &'a ast::Expr, entity: Option<&'a ast::Entity>) -> Result<VariadicLen, CompileError<'a>> {
        Ok(match &src.kind {
            ast::ExprKind::Value(ast::Value::List(values, _)) => {
                for value in values.iter() {
                    self.append_value(value, entity)?;
                }
                VariadicLen::Fixed(values.len())
            }
            ast::ExprKind::MakeList { values } => {
                for value in values.iter() {
                    self.append_expr(value, entity)?;
                }
                VariadicLen::Fixed(values.len())
            }
            _ => {
                self.append_expr(src, entity)?;
                VariadicLen::Dynamic
            }
        })
    }
    fn append_value(&mut self, value: &'a ast::Value, entity: Option<&'a ast::Entity>) -> Result<(), CompileError<'a>> {
        match value {
            ast::Value::Number(v) => self.ins.push(Instruction::PushNumber { value: *v }.into()),
            ast::Value::String(v) => self.ins.push(Instruction::PushString { value: v }.into()),
            ast::Value::Constant(v) => self.ins.push(Instruction::PushNumber { value: match v {
                ast::Constant::Pi => std::f64::consts::PI,
                ast::Constant::E => std::f64::consts::E,
            }}.into()),
            ast::Value::Bool(v) => self.ins.push(Instruction::PushBool { value: *v }.into()),
            ast::Value::List(values, _) => {
                for v in values {
                    self.append_value(v, entity)?;
                }
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Fixed(values.len()) }.into());
            }
            ast::Value::Image(_) => unreachable!(), // Snap! doesn't have image literals
            ast::Value::Ref(_) => unreachable!(), // Snap! doesn't have reference literals
        }
        Ok(())
    }
    fn append_expr(&mut self, expr: &'a ast::Expr, entity: Option<&'a ast::Entity>) -> Result<(), CompileError<'a>> {
        match &expr.kind {
            ast::ExprKind::Value(v) => self.append_value(v, entity)?,
            ast::ExprKind::Variable { var } => self.ins.push(Instruction::PushVariable { var: &var.trans_name }.into()),
            ast::ExprKind::Atan2 { y, x } => self.append_simple_ins(entity, &[y, x], BinaryOp::Atan2.into())?,
            ast::ExprKind::Sub { left, right } => self.append_simple_ins(entity, &[left, right], BinaryOp::Sub.into())?,
            ast::ExprKind::Div { left, right } => self.append_simple_ins(entity, &[left, right], BinaryOp::Div.into())?,
            ast::ExprKind::Pow { base, power } => self.append_simple_ins(entity, &[base, power], BinaryOp::Pow.into())?,
            ast::ExprKind::Mod { left, right } => self.append_simple_ins(entity, &[left, right], BinaryOp::Mod.into())?,
            ast::ExprKind::Log { base, value } => self.append_simple_ins(entity, &[base, value], BinaryOp::Log.into())?,
            ast::ExprKind::Neg { value } => self.append_simple_ins(entity, &[value], UnaryOp::Neg.into())?,
            ast::ExprKind::Abs { value } => self.append_simple_ins(entity, &[value], UnaryOp::Abs.into())?,
            ast::ExprKind::Sqrt { value } => self.append_simple_ins(entity, &[value], UnaryOp::Sqrt.into())?,
            ast::ExprKind::Sin { value } => self.append_simple_ins(entity, &[value], UnaryOp::Sin.into())?,
            ast::ExprKind::Cos { value } => self.append_simple_ins(entity, &[value], UnaryOp::Cos.into())?,
            ast::ExprKind::Tan { value } => self.append_simple_ins(entity, &[value], UnaryOp::Tan.into())?,
            ast::ExprKind::Asin { value } => self.append_simple_ins(entity, &[value], UnaryOp::Asin.into())?,
            ast::ExprKind::Acos { value } => self.append_simple_ins(entity, &[value], UnaryOp::Acos.into())?,
            ast::ExprKind::Atan { value } => self.append_simple_ins(entity, &[value], UnaryOp::Atan.into())?,
            ast::ExprKind::Round { value } => self.append_simple_ins(entity, &[value], UnaryOp::Round.into())?,
            ast::ExprKind::Floor { value } => self.append_simple_ins(entity, &[value], UnaryOp::Floor.into())?,
            ast::ExprKind::Ceil { value } => self.append_simple_ins(entity, &[value], UnaryOp::Ceil.into())?,
            ast::ExprKind::Not { value } => self.append_simple_ins(entity, &[value], UnaryOp::Not.into())?,
            ast::ExprKind::StrLen { value } => self.append_simple_ins(entity, &[value], UnaryOp::StrLen.into())?,
            ast::ExprKind::UnicodeToChar { value } => self.append_simple_ins(entity, &[value], UnaryOp::UnicodeToChar.into())?,
            ast::ExprKind::CharToUnicode { value } => self.append_simple_ins(entity, &[value], UnaryOp::CharToUnicode.into())?,
            ast::ExprKind::Greater { left, right } => self.append_simple_ins(entity, &[left, right], Relation::Greater.into())?,
            ast::ExprKind::GreaterEq { left, right } => self.append_simple_ins(entity, &[left, right], Relation::GreaterEq.into())?,
            ast::ExprKind::Less { left, right } => self.append_simple_ins(entity, &[left, right], Relation::Less.into())?,
            ast::ExprKind::LessEq { left, right } => self.append_simple_ins(entity, &[left, right], Relation::LessEq.into())?,
            ast::ExprKind::Eq { left, right } => self.append_simple_ins(entity, &[left, right], Relation::Equal.into())?,
            ast::ExprKind::Neq { left, right } => self.append_simple_ins(entity, &[left, right], Relation::NotEqual.into())?,
            ast::ExprKind::Identical { left, right } => self.append_simple_ins(entity, &[left, right], Instruction::RefEq)?,
            ast::ExprKind::ListGet { list, index } => self.append_simple_ins(entity, &[index, list], Instruction::ListGet)?,
            ast::ExprKind::ListGetLast { list } => self.append_simple_ins(entity, &[list], Instruction::ListGetLast)?,
            ast::ExprKind::ListGetRandom { list } => self.append_simple_ins(entity, &[list], Instruction::ListGetRandom)?,
            ast::ExprKind::ListLength { value } => self.append_simple_ins(entity, &[value], Instruction::ListLength)?,
            ast::ExprKind::ListDims { value } => self.append_simple_ins(entity, &[value], Instruction::ListDims)?,
            ast::ExprKind::ListRank { value } => self.append_simple_ins(entity, &[value], Instruction::ListRank)?,
            ast::ExprKind::ListRev { value } => self.append_simple_ins(entity, &[value], Instruction::ListRev)?,
            ast::ExprKind::ListFlatten { value } => self.append_simple_ins(entity, &[value], Instruction::ListFlatten)?,
            ast::ExprKind::ListIsEmpty { value } => self.append_simple_ins(entity, &[value], Instruction::ListIsEmpty)?,
            ast::ExprKind::ListCons { item, list } => self.append_simple_ins(entity, &[item, list], Instruction::ListCons)?,
            ast::ExprKind::ListCdr { value } => self.append_simple_ins(entity, &[value], Instruction::ListCdr)?,
            ast::ExprKind::ListFind { list, value } => self.append_simple_ins(entity, &[value, list], Instruction::ListFind)?,
            ast::ExprKind::ListContains { list, value } => self.append_simple_ins(entity, &[list, value], Instruction::ListContains)?,
            ast::ExprKind::Range { start, stop } => self.append_simple_ins(entity, &[start, stop], BinaryOp::Range.into())?,
            ast::ExprKind::Random { a, b } => self.append_simple_ins(entity, &[a, b], BinaryOp::Random.into())?,
            ast::ExprKind::ListColumns { value } => self.append_simple_ins(entity, &[value], Instruction::ListColumns)?,
            ast::ExprKind::ListLines { value } => self.append_simple_ins(entity, &[value], Instruction::ListLines)?,
            ast::ExprKind::ListJson { value } => self.append_simple_ins(entity, &[value], Instruction::ListJson)?,
            ast::ExprKind::StrGet { string, index } => self.append_simple_ins(entity, &[index, string], BinaryOp::StrGet.into())?,
            ast::ExprKind::StrGetLast { string } => self.append_simple_ins(entity, &[string], UnaryOp::StrGetLast.into())?,
            ast::ExprKind::StrGetRandom { string } => self.append_simple_ins(entity, &[string], UnaryOp::StrGetRandom.into())?,
            ast::ExprKind::Effect { kind } => self.append_simple_ins(entity, &[], Instruction::PushProperty { prop: Property::from_effect(kind) })?,
            ast::ExprKind::Clone { target } => self.append_simple_ins(entity, &[target], Instruction::Clone)?,
            ast::ExprKind::This => self.ins.push(Instruction::PushSelf.into()),
            ast::ExprKind::Heading => self.ins.push(Instruction::PushProperty { prop: Property::Heading }.into()),
            ast::ExprKind::RpcError => self.ins.push(Instruction::PushRpcError.into()),
            ast::ExprKind::Answer => self.ins.push(Instruction::PushAnswer.into()),
            ast::ExprKind::Message => self.ins.push(Instruction::PushLocalMessage.into()),
            ast::ExprKind::Timer => self.ins.push(Instruction::PushTimer.into()),
            ast::ExprKind::XPos => self.ins.push(Instruction::PushProperty { prop: Property::XPos }.into()),
            ast::ExprKind::YPos => self.ins.push(Instruction::PushProperty { prop: Property::YPos }.into()),
            ast::ExprKind::PenDown => self.ins.push(Instruction::PushProperty { prop: Property::PenDown }.into()),
            ast::ExprKind::PenAttr { attr } => self.ins.push(Instruction::PushProperty { prop: Property::from_pen_attr(attr) }.into()),
            ast::ExprKind::Costume => self.ins.push(Instruction::PushCostume.into()),
            ast::ExprKind::CostumeNumber => self.ins.push(Instruction::PushCostumeNumber.into()),
            ast::ExprKind::CostumeList => self.ins.push(Instruction::PushCostumeList.into()),
            ast::ExprKind::Size => self.ins.push(Instruction::PushProperty { prop: Property::Size }.into()),
            ast::ExprKind::IsVisible => self.ins.push(Instruction::PushProperty { prop: Property::Visible }.into()),
            ast::ExprKind::Entity { trans_name, .. } => self.ins.push(Instruction::PushEntity { name: trans_name }.into()),
            ast::ExprKind::Add { values } => self.append_variadic_op(entity, values, VariadicOp::Add)?,
            ast::ExprKind::Mul { values } => self.append_variadic_op(entity, values, VariadicOp::Mul)?,
            ast::ExprKind::Min { values } => self.append_variadic_op(entity, values, VariadicOp::Min)?,
            ast::ExprKind::Max { values } => self.append_variadic_op(entity, values, VariadicOp::Max)?,
            ast::ExprKind::StrCat { values } => self.append_variadic_op(entity, values, VariadicOp::StrCat)?,
            ast::ExprKind::ListCat { lists } => self.append_variadic_op(entity, lists, VariadicOp::ListCat)?,
            ast::ExprKind::CopyList { list } => self.append_variadic_op(entity, list, VariadicOp::MakeList)?,
            ast::ExprKind::MakeList { values } => {
                for value in values {
                    self.append_expr(value, entity)?;
                }
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Fixed(values.len()) }.into());
            }
            ast::ExprKind::UnknownBlock { name, args } => match name.as_str() {
                "nativeCallSyscall" => {
                    let (name, args) = match args.as_slice() {
                        [name, args] => (name, args),
                        _ => return Err(CompileError::InvalidBlock { loc: expr.info.location.as_deref() }),
                    };
                    self.append_expr(name, entity)?;
                    let len = self.append_variadic(args, entity)?;
                    self.ins.push(Instruction::Syscall { len }.into());
                }
                "nativeSyscallError" => {
                    if !args.is_empty() { return Err(CompileError::InvalidBlock { loc: expr.info.location.as_deref() }) }
                    self.ins.push(Instruction::PushSyscallError.into());
                }
                _ => {
                    for arg in args {
                        self.append_expr(arg, entity)?;
                    }
                    self.ins.push(Instruction::UnknownBlock { name: &name, args: args.len() }.into());
                }
            }
            ast::ExprKind::TypeQuery { value, ty } => {
                self.append_expr(value, entity)?;
                let ty = match ty {
                    ast::ValueType::Number => BasicType::Number,
                    ast::ValueType::Text => BasicType::String,
                    ast::ValueType::Bool => BasicType::Bool,
                    ast::ValueType::List => BasicType::List,
                    ast::ValueType::Sprite => BasicType::Entity,
                    ast::ValueType::Costume => BasicType::Image,
                    ast::ValueType::Sound => BasicType::Audio,
                    ast::ValueType::Command | ast::ValueType::Reporter | ast::ValueType::Predicate => return Err(CompileError::CurrentlyUnsupported { info: format!("closure types are indistinguishable") }),
                };
                self.ins.push(Instruction::TypeQuery { ty }.into());
            }
            ast::ExprKind::ListReshape { value, dims } => {
                self.append_expr(value, entity)?;
                let len = self.append_variadic(dims, entity)?;
                self.ins.push(Instruction::ListReshape { len }.into());
            }
            ast::ExprKind::ListCombinations { sources } => {
                let len = self.append_variadic(sources, entity)?;
                self.ins.push(Instruction::ListCartesianProduct { len }.into());
            }
            ast::ExprKind::Conditional { condition, then, otherwise } => {
                self.append_expr(condition, entity)?;
                let test_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                self.append_expr(then, entity)?;
                let jump_aft_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                let test_false_pos = self.ins.len();
                self.append_expr(otherwise, entity)?;
                let aft_pos = self.ins.len();

                self.ins[test_pos] = Instruction::ConditionalJump { to: test_false_pos, when: false }.into();
                self.ins[jump_aft_pos] = Instruction::Jump { to: aft_pos }.into();
            }
            ast::ExprKind::Or { left, right } => {
                self.append_expr(left, entity)?;
                self.ins.push(Instruction::DupeValue { top_index: 0 }.into());
                let check_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::PopValue.into());
                self.append_expr(right, entity)?;
                let aft = self.ins.len();

                self.ins[check_pos] = Instruction::ConditionalJump { to: aft, when: true }.into();

                self.ins.push(Instruction::ToBool.into());
            }
            ast::ExprKind::And { left, right } => {
                self.append_expr(left, entity)?;
                self.ins.push(Instruction::DupeValue { top_index: 0 }.into());
                let check_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::PopValue.into());
                self.append_expr(right, entity)?;
                let aft = self.ins.len();

                self.ins[check_pos] = Instruction::ConditionalJump { to: aft, when: false }.into();

                self.ins.push(Instruction::ToBool.into());
            }
            ast::ExprKind::CallFn { function, args, upvars } => {
                for upvar in upvars {
                    self.ins.push(Instruction::DeclareLocal { var: &upvar.name }.into());
                }
                for arg in args {
                    self.append_expr(arg, entity)?;
                }
                let call_hole_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                self.call_holes.push((call_hole_pos, function, entity));
            }
            ast::ExprKind::CallClosure { new_entity, closure, args } => {
                if let Some(new_entity) = new_entity {
                    self.append_expr(new_entity, entity)?;
                }
                self.append_expr(closure, entity)?;
                for arg in args {
                    self.append_expr(arg, entity)?;
                }
                self.ins.push(Instruction::CallClosure { new_entity: new_entity.is_some(), args: args.len() }.into());
            }
            ast::ExprKind::CallRpc { service, rpc, args } => {
                for (arg_name, arg) in args {
                    self.ins.push(Instruction::MetaPush { value: arg_name }.into());
                    self.append_expr(arg, entity)?;
                }
                self.ins.push(Instruction::CallRpc { service, rpc, args: args.len() }.into());
            }
            ast::ExprKind::NetworkMessageReply { target, msg_type, values } => {
                for (field, value) in values {
                    self.append_expr(value, entity)?;
                    self.ins.push(Instruction::MetaPush { value: field }.into());
                }
                self.append_expr(target, entity)?;
                self.ins.push(Instruction::SendNetworkMessage { msg_type, values: values.len(), expect_reply: true }.into());
            }
            ast::ExprKind::Closure { kind: _, params, captures, stmts } => {
                let closure_hole_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.closure_holes.push_back((closure_hole_pos, params, captures, stmts, entity));
            }
            ast::ExprKind::TextSplit { text, mode } => {
                self.append_expr(text, entity)?;
                let ins: Instruction = match mode {
                    ast::TextSplitMode::Letter => UnaryOp::SplitLetter.into(),
                    ast::TextSplitMode::Word => UnaryOp::SplitWord.into(),
                    ast::TextSplitMode::Tab => UnaryOp::SplitTab.into(),
                    ast::TextSplitMode::CR => UnaryOp::SplitCR.into(),
                    ast::TextSplitMode::LF => UnaryOp::SplitLF.into(),
                    ast::TextSplitMode::Csv => UnaryOp::SplitCsv.into(),
                    ast::TextSplitMode::Json => UnaryOp::SplitJson.into(),
                    ast::TextSplitMode::Custom(pattern) => {
                        self.append_expr(pattern, entity)?;
                        BinaryOp::SplitBy.into()
                    }
                };
                self.ins.push(ins.into());
            }
            ast::ExprKind::Map { f, list } => {
                self.append_expr(f, entity)?;
                self.append_expr(list, entity)?;
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Dynamic }.into()); // shallow copy the input list
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Fixed(0) }.into()); // push an empty list

                let top = self.ins.len();
                self.ins.push(Instruction::DupeValue { top_index: 2 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 2 }.into());
                let exit_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::CallClosure { new_entity: false, args: 1 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::ListInsertLast.into());
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
                let aft = self.ins.len();

                self.ins[exit_jump_pos] = Instruction::ListPopFirstOrElse { goto: aft }.into();

                self.ins.push(Instruction::SwapValues { top_index_1: 1, top_index_2: 3 }.into());
                self.ins.push(Instruction::PopValue.into());
                self.ins.push(Instruction::PopValue.into());
                self.ins.push(Instruction::PopValue.into());
            }
            ast::ExprKind::Keep { f, list } => {
                self.append_expr(f, entity)?;
                self.append_expr(list, entity)?;
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Dynamic }.into()); // shallow copy the input list
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Fixed(0) }.into()); // push an empty list

                let top = self.ins.len();
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                let exit_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::DupeValue { top_index: 3 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::CallClosure { new_entity: false, args: 1 }.into());
                let skip_append_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::ListInsertLast.into());
                let kept_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                let pop_cont = self.ins.len();
                self.ins.push(Instruction::PopValue.into());
                let cont = self.ins.len();
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
                let aft = self.ins.len();

                self.ins[exit_jump_pos] = Instruction::ListPopFirstOrElse { goto: aft }.into();
                self.ins[skip_append_pos] = Instruction::ConditionalJump { to: pop_cont, when: false }.into();
                self.ins[kept_jump_pos] = Instruction::Jump { to: cont }.into();

                self.ins.push(Instruction::SwapValues { top_index_1: 0, top_index_2: 2 }.into());
                self.ins.push(Instruction::PopValue.into());
                self.ins.push(Instruction::PopValue.into());
            }
            ast::ExprKind::FindFirst { f, list } => {
                self.append_expr(f, entity)?;
                self.append_expr(list, entity)?;
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Dynamic }.into()); // shallow copy the input list

                let top = self.ins.len();
                self.ins.push(Instruction::DupeValue { top_index: 0 }.into());
                let exit_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::DupeValue { top_index: 2 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::CallClosure { new_entity: false, args: 1 }.into());
                let skip_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::PopValue.into());
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());

                let aft_loop = self.ins.len();
                self.ins.push(Instruction::PushString { value: "" }.into());
                let ret = self.ins.len();
                self.ins.push(Instruction::SwapValues { top_index_1: 0, top_index_2: 2 }.into());
                self.ins.push(Instruction::PopValue.into());
                self.ins.push(Instruction::PopValue.into());

                self.ins[exit_jump_pos] = Instruction::ListPopFirstOrElse { goto: aft_loop }.into();
                self.ins[skip_jump_pos] = Instruction::ConditionalJump { to: ret, when: true }.into();
            }
            ast::ExprKind::Combine { f, list } => {
                self.append_expr(list, entity)?;
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Dynamic }.into()); // shallow copy the input list
                self.append_expr(f, entity)?;

                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                let first_check_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                let top = self.ins.len();
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 3 }.into());
                let loop_done_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::SwapValues { top_index_1: 1, top_index_2: 2 }.into());
                self.ins.push(Instruction::CallClosure { new_entity: false, args: 2 }.into());
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());

                let clean_inner = self.ins.len();
                self.ins.push(Instruction::PopValue.into());
                let clean_inner_ret = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                let empty_list = self.ins.len();
                self.ins.push(Instruction::PushInt { value: 0 }.into());
                let ret = self.ins.len();
                self.ins.push(Instruction::SwapValues { top_index_1: 0, top_index_2: 2 }.into());
                self.ins.push(Instruction::PopValue.into());
                self.ins.push(Instruction::PopValue.into());

                self.ins[first_check_pos] = Instruction::ListPopFirstOrElse { goto: empty_list }.into();
                self.ins[loop_done_pos] = Instruction::ListPopFirstOrElse { goto: clean_inner }.into();
                self.ins[clean_inner_ret] = Instruction::Jump { to: ret }.into();
            }
            kind => return Err(CompileError::UnsupportedExpr { kind }),
        }

        if let Some(location) = expr.info.location.as_deref() {
            self.ins_locations.insert(self.ins.len(), location);
        }

        Ok(())
    }
    fn append_stmt(&mut self, stmt: &'a ast::Stmt, entity: Option<&'a ast::Entity>) -> Result<(), CompileError<'a>> {
        match &stmt.kind {
            ast::StmtKind::Assign { var, value } => self.append_simple_ins(entity, &[value], Instruction::Assign { var: &var.trans_name })?,
            ast::StmtKind::AddAssign { var, value } => self.append_simple_ins(entity, &[value], Instruction::BinaryOpAssign { var: &var.trans_name, op: BinaryOp::Add })?,
            ast::StmtKind::ShowVar { var } => self.ins.push(Instruction::Watcher { create: true, var: &var.trans_name }.into()),
            ast::StmtKind::HideVar { var } => self.ins.push(Instruction::Watcher { create: false, var: &var.trans_name }.into()),
            ast::StmtKind::Pause => self.ins.push(Instruction::Pause.into()),
            ast::StmtKind::ListInsert { list, value, index } => self.append_simple_ins(entity, &[value, index, list], Instruction::ListInsert)?,
            ast::StmtKind::ListInsertLast { list, value } => self.append_simple_ins(entity, &[value, list], Instruction::ListInsertLast)?,
            ast::StmtKind::ListInsertRandom { list, value } => self.append_simple_ins(entity, &[value, list], Instruction::ListInsertRandom)?,
            ast::StmtKind::ListRemove { list, index } => self.append_simple_ins(entity, &[index, list], Instruction::ListRemove)?,
            ast::StmtKind::ListRemoveLast { list } => self.append_simple_ins(entity, &[list], Instruction::ListRemoveLast)?,
            ast::StmtKind::ListRemoveAll { list } => self.append_simple_ins(entity, &[list], Instruction::ListRemoveAll)?,
            ast::StmtKind::ListAssign { list, index, value } => self.append_simple_ins(entity, &[index, list, value], Instruction::ListAssign)?,
            ast::StmtKind::ListAssignLast { list, value } => self.append_simple_ins(entity, &[list, value], Instruction::ListAssignLast)?,
            ast::StmtKind::ListAssignRandom { list, value } => self.append_simple_ins(entity, &[list, value], Instruction::ListAssignRandom)?,
            ast::StmtKind::Return { value } => self.append_simple_ins(entity, &[value], Instruction::Return)?,
            ast::StmtKind::Throw { error } => self.append_simple_ins(entity, &[error], Instruction::Throw)?,
            ast::StmtKind::Ask { prompt } => self.append_simple_ins(entity, &[prompt], Instruction::Ask)?,
            ast::StmtKind::Sleep { seconds } => self.append_simple_ins(entity, &[seconds], Instruction::Sleep)?,
            ast::StmtKind::SendNetworkReply { value } => self.append_simple_ins(entity, &[value], Instruction::SendNetworkReply)?,
            ast::StmtKind::SetSize { value } => self.append_simple_ins(entity, &[value], Instruction::SetProperty { prop: Property::Size })?,
            ast::StmtKind::ChangeSize { delta } => self.append_simple_ins(entity, &[delta], Instruction::ChangeProperty { prop: Property::Size })?,
            ast::StmtKind::SetEffect { kind, value } => self.append_simple_ins(entity, &[value], Instruction::SetProperty { prop: Property::from_effect(kind) })?,
            ast::StmtKind::ChangeEffect { kind, delta } => self.append_simple_ins(entity, &[delta], Instruction::ChangeProperty { prop: Property::from_effect(kind) })?,
            ast::StmtKind::ClearEffects => self.ins.push(Instruction::ClearEffects.into()),
            ast::StmtKind::Forward { distance } => self.append_simple_ins(entity, &[distance], Instruction::Forward)?,
            ast::StmtKind::ResetTimer => self.ins.push(Instruction::ResetTimer.into()),
            ast::StmtKind::ChangePenAttr { attr, delta } => self.append_simple_ins(entity, &[delta], Instruction::ChangeProperty { prop: Property::from_pen_attr(attr) })?,
            ast::StmtKind::SetPenAttr { attr, value } => self.append_simple_ins(entity, &[value], Instruction::SetProperty { prop: Property::from_pen_attr(attr) })?,
            ast::StmtKind::GotoXY { x, y } => self.append_simple_ins(entity, &[x, y], Instruction::GotoXY)?,
            ast::StmtKind::ChangeX { delta } => self.append_simple_ins(entity, &[delta], Instruction::ChangeProperty { prop: Property::XPos })?,
            ast::StmtKind::ChangeY { delta } => self.append_simple_ins(entity, &[delta], Instruction::ChangeProperty { prop: Property::YPos })?,
            ast::StmtKind::SetX { value } => self.append_simple_ins(entity, &[value], Instruction::SetProperty { prop: Property::XPos })?,
            ast::StmtKind::SetY { value } => self.append_simple_ins(entity, &[value], Instruction::SetProperty { prop: Property::YPos })?,
            ast::StmtKind::TurnRight { angle } => self.append_simple_ins(entity, &[angle], Instruction::ChangeProperty { prop: Property::Heading })?,
            ast::StmtKind::SetHeading { value } => self.append_simple_ins(entity, &[value], Instruction::SetProperty { prop: Property::Heading })?,
            ast::StmtKind::PointTowards { target } => self.append_simple_ins(entity, &[target], Instruction::PointTowards)?,
            ast::StmtKind::PointTowardsXY { x, y } => self.append_simple_ins(entity, &[x, y], Instruction::PointTowardsXY)?,
            ast::StmtKind::Goto { target } => self.append_simple_ins(entity, &[target], Instruction::Goto)?,
            ast::StmtKind::SetPenSize { value } => self.append_simple_ins(entity, &[value], Instruction::SetProperty { prop: Property::PenSize })?,
            ast::StmtKind::ChangePenSize { delta } => self.append_simple_ins(entity, &[delta], Instruction::ChangeProperty { prop: Property::PenSize })?,
            ast::StmtKind::NextCostume => self.ins.push(Instruction::NextCostume.into()),
            ast::StmtKind::SetCostume { costume } => match costume {
                Some(x) => self.append_simple_ins(entity, &[x], Instruction::SetCostume)?,
                None => {
                    self.ins.push(Instruction::PushString { value: "" }.into());
                    self.ins.push(Instruction::SetCostume.into());
                }
            }
            ast::StmtKind::SetVisible { value } => {
                self.ins.push(Instruction::PushBool { value: *value }.into());
                self.ins.push(Instruction::SetProperty { prop: Property::Visible }.into());
            }
            ast::StmtKind::SetPenDown { value } => {
                self.ins.push(Instruction::PushBool { value: *value }.into());
                self.ins.push(Instruction::SetProperty { prop: Property::PenDown }.into());
            }
            ast::StmtKind::TurnLeft { angle } => {
                self.append_expr(angle, entity)?;
                self.ins.push(Instruction::from(UnaryOp::Neg).into());
                self.ins.push(Instruction::ChangeProperty { prop: Property::Heading }.into());
            }
            ast::StmtKind::SetPenColor { color } => {
                let (r, g, b, a) = *color;
                self.ins.push(Instruction::PushColor { value: Color { r, g, b, a } }.into());
                self.ins.push(Instruction::SetProperty { prop: Property::PenColor }.into());
            }
            x @ (ast::StmtKind::Say { content, duration } | ast::StmtKind::Think { content, duration }) => {
                let style = match x {
                    ast::StmtKind::Say { .. } => PrintStyle::Say,
                    ast::StmtKind::Think { .. } => PrintStyle::Think,
                    _ => unreachable!(),
                };

                self.append_simple_ins(entity, &[content], Instruction::Print { style })?;
                if let Some(t) = duration {
                    self.append_simple_ins(entity, &[t], Instruction::Sleep)?;
                    self.ins.push(Instruction::PushString { value: "" }.into());
                    self.ins.push(Instruction::Print { style }.into());
                }
            }
            ast::StmtKind::DeclareLocals { vars } => {
                for var in vars {
                    self.ins.push(Instruction::DeclareLocal { var: &var.trans_name }.into());
                }
            }
            ast::StmtKind::CallFn { function, args, upvars } => {
                for upvar in upvars {
                    self.ins.push(Instruction::DeclareLocal { var: &upvar.name }.into());
                }
                for arg in args {
                    self.append_expr(arg, entity)?;
                }
                let call_hole_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::PopValue.into());

                self.call_holes.push((call_hole_pos, function, entity));
            }
            ast::StmtKind::RunClosure { new_entity, closure, args } => {
                if let Some(new_entity) = new_entity {
                    self.append_expr(new_entity, entity)?;
                }
                self.append_expr(closure, entity)?;
                for arg in args {
                    self.append_expr(arg, entity)?;
                }
                self.ins.push(Instruction::CallClosure { new_entity: new_entity.is_some(), args: args.len() }.into());
                self.ins.push(Instruction::PopValue.into());
            }
            ast::StmtKind::ForkClosure { closure, args } => {
                self.append_expr(closure, entity)?;
                for arg in args {
                    self.append_expr(arg, entity)?;
                }
                self.ins.push(Instruction::ForkClosure { args: args.len() }.into());
            }
            ast::StmtKind::Warp { stmts } => {
                self.ins.push(Instruction::WarpStart.into());
                for stmt in stmts {
                    self.append_stmt(stmt, entity)?;
                }
                self.ins.push(Instruction::WarpStop.into());
            }
            ast::StmtKind::InfLoop { stmts } => {
                let top = self.ins.len();
                for stmt in stmts {
                    self.append_stmt(stmt, entity)?;
                }
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
            }
            ast::StmtKind::WaitUntil { condition } => {
                let top = self.ins.len();
                self.append_expr(condition, entity)?;
                let jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
                let aft = self.ins.len();

                self.ins[jump_pos] = Instruction::ConditionalJump { to: aft, when: true }.into();
            }
            ast::StmtKind::UntilLoop { condition, stmts } => {
                let top = self.ins.len();
                self.append_expr(condition, entity)?;
                let exit_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                for stmt in stmts {
                    self.append_stmt(stmt, entity)?;
                }
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
                let aft = self.ins.len();

                self.ins[exit_jump_pos] = Instruction::ConditionalJump { to: aft, when: true }.into();
            }
            ast::StmtKind::Repeat { times, stmts } => {
                self.append_expr(times, entity)?;

                let top = self.ins.len();
                self.ins.push(Instruction::DupeValue { top_index: 0 }.into());
                self.ins.push(Instruction::PushInt { value: 0 }.into());
                self.ins.push(Instruction::from(Relation::Greater).into());
                let aft_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                for stmt in stmts {
                    self.append_stmt(stmt, entity)?;
                }

                self.ins.push(Instruction::PushInt { value: 1 }.into());
                self.ins.push(Instruction::from(BinaryOp::Sub).into());
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
                let aft = self.ins.len();

                self.ins[aft_jump_pos] = Instruction::ConditionalJump { to: aft, when: false }.into();

                self.ins.push(Instruction::PopValue.into());
            }
            ast::StmtKind::ForLoop { var, start, stop, stmts } => {
                self.ins.push(Instruction::DeclareLocal { var: &var.name }.into());

                self.append_expr(start, entity)?;
                self.ins.push(Instruction::ToNumber.into());
                self.append_expr(stop, entity)?;
                self.ins.push(Instruction::ToNumber.into());

                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::from(Relation::Greater).into());
                let delta_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                self.ins.push(Instruction::PushInt { value: 1 }.into());
                let positive_delta_end = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                let negative_delta_pos = self.ins.len();
                self.ins.push(Instruction::PushInt { value: -1 }.into());
                let aft_delta = self.ins.len();

                self.ins[delta_jump_pos] = Instruction::ConditionalJump { to: negative_delta_pos, when: true }.into();
                self.ins[positive_delta_end] = Instruction::Jump { to: aft_delta }.into();

                self.ins.push(Instruction::SwapValues { top_index_1: 0, top_index_2: 2 }.into());
                self.ins.push(Instruction::SwapValues { top_index_1: 0, top_index_2: 1 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::from(BinaryOp::Sub).into());
                self.ins.push(Instruction::from(UnaryOp::Abs).into());

                let top = self.ins.len();
                self.ins.push(Instruction::DupeValue { top_index: 0 }.into());
                self.ins.push(Instruction::PushInt { value: 0 }.into());
                self.ins.push(Instruction::from(Relation::Less).into());
                let exit_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::Assign { var: &var.trans_name }.into());
                for stmt in stmts {
                    self.append_stmt(stmt, entity)?;
                }

                self.ins.push(Instruction::PushInt { value: 1 }.into());
                self.ins.push(Instruction::from(BinaryOp::Sub).into());
                self.ins.push(Instruction::DupeValue { top_index: 1 }.into());
                self.ins.push(Instruction::DupeValue { top_index: 3 }.into());
                self.ins.push(Instruction::from(BinaryOp::Add).into());
                self.ins.push(Instruction::SwapValues { top_index_1: 0, top_index_2: 2 }.into());
                self.ins.push(Instruction::PopValue.into());
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
                let aft = self.ins.len();

                self.ins[exit_jump_pos] = Instruction::ConditionalJump { to: aft, when: true }.into();

                for _ in 0..3 {
                    self.ins.push(Instruction::PopValue.into());
                }
            }
            ast::StmtKind::ForeachLoop { var, items, stmts } => {
                self.ins.push(Instruction::DeclareLocal { var: &var.name }.into());

                self.append_expr(items, entity)?;
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Dynamic }.into()); // shallow copy the input list

                let top = self.ins.len();
                self.ins.push(Instruction::DupeValue { top_index: 0 }.into());
                let exit_jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                self.ins.push(Instruction::Assign { var: &var.trans_name }.into());
                for stmt in stmts {
                    self.append_stmt(stmt, entity)?;
                }
                self.ins.push(Instruction::Yield.into());
                self.ins.push(Instruction::Jump { to: top }.into());
                let aft = self.ins.len();

                self.ins[exit_jump_pos] = Instruction::ListPopFirstOrElse { goto: aft }.into();

                self.ins.push(Instruction::PopValue.into());
            }
            ast::StmtKind::If { condition, then } => {
                self.append_expr(condition, entity)?;
                let patch_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                for stmt in then {
                    self.append_stmt(stmt, entity)?;
                }
                let else_pos = self.ins.len();

                self.ins[patch_pos] = Instruction::ConditionalJump { to: else_pos, when: false }.into();
            }
            ast::StmtKind::IfElse { condition, then, otherwise } => {
                self.append_expr(condition, entity)?;
                let check_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                for stmt in then {
                    self.append_stmt(stmt, entity)?;
                }
                let jump_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);
                let else_pos = self.ins.len();
                for stmt in otherwise {
                    self.append_stmt(stmt, entity)?;
                }
                let aft = self.ins.len();

                self.ins[check_pos] = Instruction::ConditionalJump { to: else_pos, when: false }.into();
                self.ins[jump_pos] = Instruction::Jump { to: aft }.into();
            }
            ast::StmtKind::TryCatch { code, var, handler } => {
                let push_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                for stmt in code {
                    self.append_stmt(stmt, entity)?;
                }
                self.ins.push(Instruction::PopHandler.into());
                let success_end_pos = self.ins.len();
                self.ins.push(InternalInstruction::Illegal);

                let error_handler_pos = self.ins.len();
                self.ins.push(Instruction::PopHandler.into());
                for stmt in handler {
                    self.append_stmt(stmt, entity)?;
                }
                let aft = self.ins.len();

                self.ins[push_pos] = Instruction::PushHandler { pos: error_handler_pos, var: &var.trans_name }.into();
                self.ins[success_end_pos] = Instruction::Jump { to: aft }.into();
            }
            ast::StmtKind::SendLocalMessage { target, msg_type, wait } => match target {
                Some(target) => self.append_simple_ins(entity, &[msg_type, target], Instruction::SendLocalMessage { wait: *wait, target: true })?,
                None => self.append_simple_ins(entity, &[msg_type], Instruction::SendLocalMessage { wait: *wait, target: false })?,
            }
            ast::StmtKind::RunRpc { service, rpc, args } => {
                for (arg_name, arg) in args {
                    self.ins.push(Instruction::MetaPush { value: arg_name }.into());
                    self.append_expr(arg, entity)?;
                }
                self.ins.push(Instruction::CallRpc { service, rpc, args: args.len() }.into());
                self.ins.push(Instruction::PopValue.into());
            }
            ast::StmtKind::SendNetworkMessage { target, msg_type, values } => {
                for (field, value) in values {
                    self.append_expr(value, entity)?;
                    self.ins.push(Instruction::MetaPush { value: field }.into());
                }
                self.append_expr(target, entity)?;
                self.ins.push(Instruction::SendNetworkMessage { msg_type, values: values.len(), expect_reply: false }.into());
            }
            ast::StmtKind::Clone { target } => {
                self.append_expr(target, entity)?;
                self.ins.push(Instruction::Clone.into());
                self.ins.push(Instruction::PopValue.into());
            }
            ast::StmtKind::UnknownBlock { name, args } => match name.as_str() {
                "nativeRunSyscall" => {
                    let (name, args) = match args.as_slice() {
                        [name, args] => (name, args),
                        _ => return Err(CompileError::InvalidBlock { loc: stmt.info.location.as_deref() }),
                    };
                    self.append_expr(name, entity)?;
                    let len = self.append_variadic(args, entity)?;
                    self.ins.push(Instruction::Syscall { len }.into());
                    self.ins.push(Instruction::PopValue.into());
                }
                _ => {
                    for arg in args {
                        self.append_expr(arg, entity)?;
                    }
                    self.ins.push(Instruction::UnknownBlock { name: &name, args: args.len() }.into());
                    self.ins.push(Instruction::PopValue.into());
                }
            }
            kind => return Err(CompileError::UnsupportedStmt { kind }),
        }

        if let Some(location) = stmt.info.location.as_deref() {
            self.ins_locations.insert(self.ins.len(), location);
        }

        Ok(())
    }
    fn append_stmts_ret(&mut self, upvars: &'a [ast::VariableRef], stmts: &'a [ast::Stmt], entity: Option<&'a ast::Entity>) -> Result<(), CompileError<'a>> {
        for upvar in upvars {
            self.ins.push(Instruction::InitUpvar { var: &upvar.name }.into());
        }
        for stmt in stmts {
            self.append_stmt(stmt, entity)?;
        }
        self.ins.push(Instruction::PushString { value: "" }.into());
        self.ins.push(Instruction::Return.into());
        Ok(())
    }
    fn link(mut self, funcs: Vec<(&'a ast::Function, usize)>, entities: Vec<(&'a ast::Entity, EntityScriptInfo<'a>)>) -> Result<(ByteCode, ScriptInfo<'a>, Locations), CompileError<'a>> {
        assert!(self.closure_holes.is_empty());

        let global_fn_to_info = {
            let mut res = BTreeMap::new();
            for (func, pos) in funcs.iter() {
                res.insert(&*func.trans_name, (*pos, *func));
            }
            res
        };
        let entity_fn_to_info = {
            let mut res = BTreeMap::new();
            for (entity, entity_locs) in entities.iter() {
                let mut inner = BTreeMap::new();
                for (func, pos) in entity_locs.funcs.iter() {
                    inner.insert(&*func.trans_name, (*pos, *func));
                }
                res.insert(*entity as *const ast::Entity, inner);
            }
            res
        };

        let get_ptr = |x: Option<&ast::Entity>| x.map(|x| x as *const ast::Entity).unwrap_or(std::ptr::null());
        for (hole_pos, hole_fn, hole_ent) in self.call_holes.iter() {
            let sym = &*hole_fn.trans_name;
            let &(pos, fn_info) = entity_fn_to_info.get(&get_ptr(*hole_ent)).and_then(|tab| tab.get(sym)).or_else(|| global_fn_to_info.get(sym)).unwrap();

            let mut ins_pack = Vec::with_capacity(fn_info.params.len() + 1);
            for param in fn_info.params.iter() {
                ins_pack.push(Instruction::MetaPush { value: &param.trans_name });
            }
            ins_pack.push(Instruction::Call { pos, params: fn_info.params.len() });

            self.ins[*hole_pos] = InternalInstruction::Packed(ins_pack);
        }

        self.finalize(funcs, entities)
    }
    fn finalize(self, funcs: Vec<(&'a ast::Function, usize)>, entities: Vec<(&'a ast::Entity, EntityScriptInfo<'a>)>) -> Result<(ByteCode, ScriptInfo<'a>, Locations), CompileError<'a>> {
        let mut code = Vec::with_capacity(self.ins.len() * 4);
        let mut data = BinPool::new();
        let mut relocate_info = Vec::with_capacity(64);

        let mut final_ins_pos = Vec::with_capacity(self.ins.len());
        for ins in self.ins.iter() {
            final_ins_pos.push(code.len());
            match ins {
                InternalInstruction::Illegal => unreachable!(),
                InternalInstruction::Packed(vals) => for val in vals {
                    BinaryWrite::append(val, &mut code, &mut data, &mut relocate_info);
                }
                InternalInstruction::Valid(val) => BinaryWrite::append(val, &mut code, &mut data, &mut relocate_info),
            }
        }

        let data_backing = data.into_backing();
        let (data, data_backing_pos) = {
            let mut data = Vec::with_capacity(data_backing.0.iter().map(Vec::len).sum::<usize>());
            let mut data_backing_pos = Vec::with_capacity(data_backing.0.len());
            for backing in data_backing.0.iter() {
                data_backing_pos.push(data.len());
                data.extend_from_slice(backing);
            }
            (data, data_backing_pos)
        };

        fn apply_shrinking_plan(plan: &[(usize, usize, usize)], final_relocates: &mut [usize], code: &mut Vec<u8>, final_ins_pos: &mut [usize]) -> usize {
            let old_pos_to_ins: BTreeMap<usize, usize> = final_ins_pos.iter().copied().enumerate().map(|(a, b)| (b, a)).collect();
            let orig_code_size = code.len();

            let mut final_ins_pos_update_iter = final_ins_pos.iter_mut().fuse().peekable();
            let mut old_hole_pos_to_new_pos = BTreeMap::default();
            let (mut dest_pos, mut src_pos, mut total_shift) = (0, 0, 0);
            for (code_addr, prev_size, new_size) in plan.iter().copied() {
                debug_assert!(prev_size >= new_size);
                debug_assert!(code_addr >= src_pos);

                while let Some(old) = final_ins_pos_update_iter.peek() {
                    if **old > code_addr { break }
                    *final_ins_pos_update_iter.next().unwrap() -= total_shift;
                }

                code.copy_within(src_pos..code_addr + new_size, dest_pos);
                dest_pos += code_addr + new_size - src_pos;
                src_pos = code_addr + prev_size;
                old_hole_pos_to_new_pos.insert(code_addr, dest_pos - new_size);
                total_shift += prev_size - new_size;
            }
            for old in final_ins_pos_update_iter { *old -= total_shift; }
            code.copy_within(src_pos..src_pos + (orig_code_size - total_shift - dest_pos), dest_pos);
            code.truncate(orig_code_size - total_shift);

            let mut buf = Vec::with_capacity(10);
            for code_addr in final_relocates.iter_mut() {
                *code_addr = old_hole_pos_to_new_pos[code_addr];
                let old_pos = <usize as BinaryRead>::read(code, &[], *code_addr);
                buf.clear();
                encode_u64(final_ins_pos[old_pos_to_ins[&old_pos.0]] as u64, &mut buf, Some(old_pos.1 - *code_addr));
                debug_assert_eq!(buf.len(), old_pos.1 - *code_addr);
                code[*code_addr..old_pos.1].copy_from_slice(&buf);
            }

            total_shift
        }

        let mut fmt_buf = Vec::with_capacity(10);
        let mut shrinking_plan = vec![];
        let mut final_relocates = vec![];
        for info in relocate_info {
            fmt_buf.clear();
            let (code_addr, prev_size) = match info {
                RelocateInfo::Code { code_addr } => {
                    final_relocates.push(code_addr);
                    let pos = <usize as BinaryRead>::read(&code, &data, code_addr);
                    encode_u64(final_ins_pos[pos.0] as u64, &mut fmt_buf, None);
                    (code_addr, pos.1 - code_addr)
                }
                RelocateInfo::Data { code_addr } => {
                    let pool_index = <usize as BinaryRead>::read(&code, &data, code_addr);
                    let slice = &data_backing.1[pool_index.0];
                    encode_u64((data_backing_pos[slice.src] + slice.start) as u64, &mut fmt_buf, None);
                    (code_addr, pool_index.1 - code_addr)
                }
            };
            debug_assert!(prev_size >= fmt_buf.len());
            shrinking_plan.push((code_addr, prev_size, fmt_buf.len()));
            code[code_addr..code_addr + fmt_buf.len()].copy_from_slice(&fmt_buf);
        }

        apply_shrinking_plan(&shrinking_plan, &mut final_relocates, &mut code, &mut final_ins_pos);

        for _ in 0..SHRINK_CYCLES {
            shrinking_plan.clear();
            for code_addr in final_relocates.iter().copied() {
                let val = <usize as BinaryRead>::read(&code, &data, code_addr);
                fmt_buf.clear();
                encode_u64(val.0 as u64, &mut fmt_buf, None);
                debug_assert!(fmt_buf.len() <= val.1 - code_addr);
                code[code_addr..code_addr + fmt_buf.len()].copy_from_slice(&fmt_buf);
                shrinking_plan.push((code_addr, val.1 - code_addr, fmt_buf.len()));
            }
            let delta = apply_shrinking_plan(&shrinking_plan, &mut final_relocates, &mut code, &mut final_ins_pos);
            if delta == 0 { break }
        }

        let (mut funcs, mut entities) = (funcs, entities);

        for func in funcs.iter_mut() { func.1 = final_ins_pos[func.1]; }
        for entity in entities.iter_mut() {
            for func in entity.1.funcs.iter_mut() { func.1 = final_ins_pos[func.1]; }
            for script in entity.1.scripts.iter_mut() { script.1 = final_ins_pos[script.1]; }
        }
        let locations = Locations::condense(self.ins_locations.iter().map(|(p, v)| (final_ins_pos[*p], *v)).collect())?;

        Ok((ByteCode { tag: Default::default(), code: code.into_boxed_slice(), data: data.into_boxed_slice() }, ScriptInfo { funcs, entities }, locations))
    }
}

impl ByteCode {
    /// Compiles a single project role into an executable form.
    /// The core information is stored in [`ByteCode`] (instructions acting on a state) and [`InitInfo`] (the initial project state).
    /// 
    /// This also emits a [`Locations`] object mapping bytecode index to code location (e.g., the block `collabId` from project xml),
    /// which is needed to provide human-readable error locations at runtime,
    /// as well as a [`ScriptInfo`] object that contains a symbol table of functions and scripts
    /// (needed to execute a specific segment of code).
    pub fn compile<'a>(role: &'a ast::Role) -> Result<(ByteCode, InitInfo, Locations, ScriptInfo<'a>), CompileError<'a>> {
        let mut code = ByteCodeBuilder::default();

        let mut funcs = Vec::with_capacity(role.funcs.len());
        for func in role.funcs.iter() {
            funcs.push((func, code.ins.len()));
            code.append_stmts_ret(&func.upvars, &func.stmts, None)?;
        }

        let mut entities = Vec::with_capacity(role.entities.len());
        for entity in role.entities.iter() {
            let mut funcs = Vec::with_capacity(entity.funcs.len());
            for func in entity.funcs.iter() {
                funcs.push((func, code.ins.len()));
                code.append_stmts_ret(&func.upvars, &func.stmts, Some(entity))?;
            }

            let mut scripts = Vec::with_capacity(entity.scripts.len());
            for script in entity.scripts.iter() {
                scripts.push((script, code.ins.len()));
                code.append_stmts_ret(&[], &script.stmts, Some(entity))?;
            }

            entities.push((entity, EntityScriptInfo { funcs, scripts }));
        }

        while let Some((hole_pos, params, captures, stmts, entity)) = code.closure_holes.pop_front() {
            let pos = code.ins.len();
            code.append_stmts_ret(&[], stmts, entity)?;

            let mut ins_pack = Vec::with_capacity(params.len() + captures.len() + 1);
            for param in params {
                ins_pack.push(Instruction::MetaPush { value: &param.trans_name });
            }
            for param in captures {
                ins_pack.push(Instruction::MetaPush { value: &param.trans_name });
            }
            ins_pack.push(Instruction::MakeClosure { pos, params: params.len(), captures: captures.len() });

            code.ins[hole_pos] = InternalInstruction::Packed(ins_pack);
        }

        let (bytecode, script_info, locations) = code.link(funcs, entities)?;
        let init_info = Self::extract_init_info(role, &script_info)?;

        Ok((bytecode, init_info, locations, script_info))
    }
    fn extract_init_info<'a>(role: &'a ast::Role, script_info: &ScriptInfo<'a>) -> Result<InitInfo, CompileError<'a>> {
        let mut ref_values = vec![];

        let mut refs = BTreeMap::new();
        let mut string_refs = BTreeMap::new();
        let mut image_refs = BTreeMap::new();

        fn register_ref_values<'a>(value: &'a ast::Value, ref_values: &mut Vec<(Option<RefValue>, &'a ast::Value)>, refs: &mut BTreeMap<usize, usize>) {
            match value {
                ast::Value::Bool(_) | ast::Value::Number(_) | ast::Value::Constant(_) => (), // non-ref types
                ast::Value::Ref(_) | ast::Value::String(_) | ast::Value::Image(_) => (), // lazily link
                ast::Value::List(_, ref_id) => if let Some(ref_id) = ref_id {
                    refs.entry(ref_id.0).or_insert_with(|| {
                        ref_values.push((None, value)); // we don't have the value yet (might contain undefined refs, so can't be handled yet)
                        ref_values.len() - 1
                    });
                }
            }
        }

        for global in role.globals.iter() {
            register_ref_values(&global.init, &mut ref_values, &mut refs);
        }
        for entity in role.entities.iter() {
            for field in entity.fields.iter() {
                register_ref_values(&field.init, &mut ref_values, &mut refs);
            }
            for costume in entity.costumes.iter() {
                register_ref_values(&costume.init, &mut ref_values, &mut refs);
            }
        }

        fn get_value<'a>(value: &'a ast::Value, ref_values: &mut Vec<(Option<RefValue>, &'a ast::Value)>, refs: &BTreeMap<usize, usize>, string_refs: &mut BTreeMap<&'a str, usize>, image_refs: &mut BTreeMap<*const Vec<u8>, usize>) -> Result<InitValue, CompileError<'a>> {
            Ok(match value {
                ast::Value::Bool(x) => InitValue::Bool(*x),
                ast::Value::Number(x) => InitValue::Number(Number::new(*x)?),
                ast::Value::Constant(x) => match x {
                    ast::Constant::E => InitValue::Number(Number::new(std::f64::consts::E)?),
                    ast::Constant::Pi => InitValue::Number(Number::new(std::f64::consts::PI)?),
                }
                ast::Value::Ref(x) => {
                    let idx = *refs.get(&x.0).ok_or_else(|| CompileError::UndefinedRef { value })?;
                    InitValue::Ref(idx)
                }
                ast::Value::String(x) => {
                    let idx = *string_refs.entry(x).or_insert_with(|| {
                        ref_values.push((Some(RefValue::String(x.clone())), value));
                        ref_values.len() - 1
                    });
                    InitValue::Ref(idx)
                }
                ast::Value::Image(x) => {
                    let idx = *image_refs.entry(Rc::as_ptr(x)).or_insert_with(|| {
                        ref_values.push((Some(RefValue::Image((**x).clone())), value));
                        ref_values.len() - 1
                    });
                    InitValue::Ref(idx)
                }
                ast::Value::List(values, ref_id) => {
                    let res = RefValue::List(values.iter().map(|x| get_value(x, ref_values, refs, string_refs, image_refs)).collect::<Result<_,_>>()?);
                    match ref_id {
                        Some(ref_id) => {
                            let idx = *refs.get(&ref_id.0).ok_or_else(|| CompileError::UndefinedRef { value })?;
                            let target = &mut ref_values[idx];
                            debug_assert!(target.0.is_none());
                            target.0 = Some(res);
                            InitValue::Ref(idx)
                        }
                        None => {
                            ref_values.push((Some(res), value));
                            InitValue::Ref(ref_values.len() - 1)
                        }
                    }
                }
            })
        }

        // -------------------------------------------------------------------

        let proj_name = role.name.clone();
        let mut globals = vec![];
        let mut entities = vec![];

        for global in role.globals.iter() {
            globals.push((global.def.name.clone(), get_value(&global.init, &mut ref_values, &refs, &mut string_refs, &mut image_refs)?));
        }

        for (entity, entity_info) in script_info.entities.iter() {
            let name = entity.name.clone();
            let mut fields = vec![];
            let mut scripts = vec![];
            let mut costumes = vec![];

            let visible = entity.visible;
            let active_costume = entity.active_costume.clone();
            let color = entity.color;
            let size = Number::new(entity.scale * 100.0)?;
            let pos = (Number::new(entity.pos.0)?, Number::new(entity.pos.1)?);
            let heading = Number::new(entity.heading.rem_euclid(360.0))?;

            for field in entity.fields.iter() {
                fields.push((field.def.name.clone(), get_value(&field.init, &mut ref_values, &refs, &mut string_refs, &mut image_refs)?));
            }

            for costume in entity.costumes.iter() {
                costumes.push((costume.def.name.clone(), get_value(&costume.init, &mut ref_values, &refs, &mut string_refs, &mut image_refs)?));
            }

            for (script, pos) in entity_info.scripts.iter().copied() {
                let hat = match script.hat.as_ref() {
                    Some(x) => x,
                    None => continue,
                };
                let event = match &hat.kind {
                    ast::HatKind::OnFlag => Event::OnFlag,
                    ast::HatKind::OnClone => Event::OnClone,
                    ast::HatKind::LocalMessage { msg_type } => Event::LocalMessage { msg_type: msg_type.clone() },
                    ast::HatKind::NetworkMessage { msg_type, fields } => Event::NetworkMessage { msg_type: msg_type.clone(), fields: fields.iter().map(|x| x.trans_name.clone()).collect() },
                    ast::HatKind::OnKey { key } => Event::OnKey {
                        key_filter: match key.as_str() {
                            "any key" => None,
                            "up arrow" => Some(KeyCode::Up),
                            "down arrow" => Some(KeyCode::Down),
                            "left arrow" => Some(KeyCode::Left),
                            "right arrow" => Some(KeyCode::Right),
                            "enter" => Some(KeyCode::Enter),
                            "space" => Some(KeyCode::Char(' ')),
                            _ => {
                                let mut chars = key.chars();
                                let res = chars.next().map(|x| KeyCode::Char(x.to_ascii_lowercase()));
                                if res.is_none() || chars.next().is_some() { return Err(CompileError::BadKeycode { key }); }
                                Some(res.unwrap())
                            }
                        }
                    },
                    kind => return Err(CompileError::UnsupportedEvent { kind }),
                };
                scripts.push((event, pos));
            }

            entities.push(EntityInitInfo { name, fields, costumes, scripts, active_costume, pos, heading, size, visible, color });
        }

        let ref_values = ref_values.into_iter().map(|x| x.0.ok_or_else(|| CompileError::UndefinedRef { value: x.1 })).collect::<Result<_,_>>()?;

        Ok(InitInfo { tag: Default::default(), proj_name, ref_values, globals, entities })
    }
    /// Generates a hex dump of the stored code, including instructions and addresses.
    #[cfg(feature = "std")]
    pub fn dump_code(&self, f: &mut dyn Write) -> io::Result<()> {
        let mut pos = 0;
        while pos < self.code.len() {
            let (ins, aft) = Instruction::read(&self.code, &self.data, pos);
            for (i, bytes) in self.code[pos..aft].chunks(BYTES_PER_LINE).enumerate() {
                if i == 0 {
                    write!(f, "{pos:08}   ")?;
                } else {
                    write!(f, "           ")?;
                }

                for &b in bytes {
                    write!(f, " {b:02x}")?;
                }
                for _ in bytes.len()..BYTES_PER_LINE {
                    write!(f, "   ")?;
                }

                if i == 0 {
                    write!(f, "    {ins:?}")?;
                }
                writeln!(f)?;
            }
            pos = aft;
        }
        Ok(())
    }
    /// Generate a hex dump of the stored program data, including string literals and meta values.
    #[cfg(feature = "std")]
    pub fn dump_data(&self, f: &mut dyn Write) -> io::Result<()> {
        for (i, bytes) in self.data.chunks(BYTES_PER_LINE).enumerate() {
            write!(f, "{:08}   ", i * BYTES_PER_LINE)?;
            for &b in bytes {
                write!(f, " {b:02x}")?;
            }
            for _ in bytes.len()..BYTES_PER_LINE {
                write!(f, "   ")?;
            }
            write!(f, "    ")?;
            for &b in bytes {
                write!(f, "{}", if (0x21..=0x7e).contains(&b) { b as char } else { '.' })?;
            }
            writeln!(f)?;
        }
        Ok(())
    }
    /// Returns the total size of the [`ByteCode`] object (in bytes).
    pub fn total_size(&self) -> usize {
        self.code.len() + self.data.len()
    }
}