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

use alloc::collections::{BTreeMap, VecDeque};
use alloc::string::ToString;
use alloc::boxed::Box;
use alloc::vec::Vec;
use alloc::rc::Rc;

use core::mem;

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

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};
use crate::util::LosslessJoin;
use crate::vecmap::VecMap;
use crate::compact_str::{CompactString, ToCompactString};

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

/// Max number of bytes produced by [`encode_u64`].
const MAX_U64_ENCODED_BYTES: 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: CompactString },
    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 enum AbortMode {
    All, Current, Others, MyOthers,
}
#[derive(Clone, Copy, Debug, FromPrimitive)]
#[repr(u8)]
pub(crate) enum TimeQuery {
    Year, Month, Date, DayOfWeek, Hour, Minute, Second, UnixTimestampMs,
}
impl From<&'_ ast::TimeQuery> for TimeQuery {
    fn from(value: &'_ ast::TimeQuery) -> Self {
        match value {
            ast::TimeQuery::Year => TimeQuery::Year,
            ast::TimeQuery::Month => TimeQuery::Month,
            ast::TimeQuery::Date => TimeQuery::Date,
            ast::TimeQuery::DayOfWeek => TimeQuery::DayOfWeek,
            ast::TimeQuery::Hour => TimeQuery::Hour,
            ast::TimeQuery::Minute => TimeQuery::Minute,
            ast::TimeQuery::Second => TimeQuery::Second,
            ast::TimeQuery::UnixTimestampMs => TimeQuery::UnixTimestampMs,
        }
    }
}

#[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 {
    ToNumber,
    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,
        }
    }
}

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 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 as a string. This is a more compact encoding than [`Instruction::PushString`] for small numbers.
    PushIntString { 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 its CSV-encoded string representation onto the value stack.
    ListCsv,
    /// 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 an identicalness check onto the value stack.
    Identical,
    /// 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 },

    /// `tokens` is a [`LosslessJoin`] of 0+ parameter names.
    /// Consumes `params` arguments from the value stack (in reverse order) 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, tokens: &'a str },
    /// `tokens` is a [`LosslessJoin`] sequence of `params` parameter names and 0+ captured variable names.
    /// Creates a closure targeting some bytecode position with the given settings.
    /// Captures are looked up and bound immediately based on the current execution context.
    MakeClosure { pos: usize, params: usize, tokens: &'a str },
    /// 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,
    /// Stops one of more processes immediately without running any following code.
    Abort { mode: AbortMode },

    /// 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,

    /// `tokens` is a [`LosslessJoin`] of service, rpc, and 0+ args, which are popped from the value stack.
    /// Then calls the given RPC, awaits the result, and pushes the return value onto the value stack.
    CallRpc { tokens: &'a str },
    /// 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,
    /// Computes a specific query about the real-world time and pushes the result onto the value stack.
    PushRealTime { query: TimeQuery },

    /// `tokens` is a [`LosslessJoin`] of msg type and 0+ field names.
    /// Consumes 1 value, `target` from the value stack, which is either a single or a list of targets.
    /// Then consumes one value from the value stack for each field to be sent.
    /// 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 { tokens: &'a str, 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,

    /// Pushes a shallow copy of the entity's list of static sounds onto the value stack.
    PushSoundList,
    /// Consumes 1 value, `sound`, from the value stack and attempts to play it.
    /// This can be an audio object or the name of a static sound on the entity.
    /// Empty string can be used as a no-op.
    PlaySound { blocking: bool },
    /// Consumes 2 values, `duration` and `notes`, from the value stack and plays them.
    /// `notes` can be a single or list of notes in either MIDI value form or (extended) English names of notes.
    PlayNotes { blocking: bool },
    /// Stops playback of all currently-playing sounds.
    StopSounds,

    /// Pops one value, `target`, from the value stack and pushes a clone of entity `target` onto the value stack.
    Clone,
    /// Deletes the current active entity if it is a clone, and requests to abort all of its associated processes.
    DeleteClone,

    /// Clears all graphic effects on the entity.
    ClearEffects,
    // Requests to erase all drawings made by all sprites.
    ClearDrawings,

    /// 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 },
}
#[test]
fn test_bin_sizes() {
    if core::mem::size_of::<Instruction>() > 40 {
        panic!("instructions are too big!");
    }
    if core::mem::size_of::<InternalInstruction>() > 40 {
        panic!("internal instructions are too big!");
    }
}

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, TimeQuery, BinaryOp, UnaryOp, VariadicOp, BasicType, AbortMode }

/// encodes values as a sequence of bytes of form [1: next][7: bits] in little-endian order.
/// `bytes` can be used to force a specific size (too small will panic), otherwise calculates and uses the smallest possible size.
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..=MAX_U64_ENCODED_BYTES).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)
}

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(core::iter::once(0x53).cycle().take(prefix_bytes));
                encode_u64(v, &mut buf, if expanded { Some(MAX_U64_ENCODED_BYTES) } else { None });
                assert!(buf[..prefix_bytes].iter().all(|&x| x == 0x53));
                assert_eq!(&buf[prefix_bytes..], expect);
                buf.extend(core::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(core::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(core::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);
        (core::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::PushIntString {} : value),
            7 => read_prefixed!(Instruction::PushNumber {} : value),
            8 => read_prefixed!(Instruction::PushColor {} : value),

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

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

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

            15 => read_prefixed!(Instruction::DupeValue { top_index: 0 }),
            16 => read_prefixed!(Instruction::DupeValue { top_index: 1 }),
            17 => read_prefixed!(Instruction::DupeValue { top_index: 2 }),
            18 => read_prefixed!(Instruction::DupeValue { top_index: 3 }),

            19 => read_prefixed!(Instruction::SwapValues { top_index_1: 0, top_index_2: 1 }),
            20 => read_prefixed!(Instruction::SwapValues { top_index_1: 0, top_index_2: 2 }),
            21 => read_prefixed!(Instruction::SwapValues { top_index_1: 1, top_index_2: 2 }),
            22 => read_prefixed!(Instruction::SwapValues { top_index_1: 1, top_index_2: 3 }),

            23 => read_prefixed!(Instruction::TypeQuery {} : ty),
            24 => read_prefixed!(Instruction::ToBool),
            25 => read_prefixed!(Instruction::ToNumber),

            26 => read_prefixed!(Instruction::ListCons),
            27 => read_prefixed!(Instruction::ListCdr),

            28 => read_prefixed!(Instruction::ListFind),
            29 => read_prefixed!(Instruction::ListContains),

            30 => read_prefixed!(Instruction::ListIsEmpty),
            31 => read_prefixed!(Instruction::ListLength),
            32 => read_prefixed!(Instruction::ListDims),
            33 => read_prefixed!(Instruction::ListRank),

            34 => read_prefixed!(Instruction::ListRev),
            35 => read_prefixed!(Instruction::ListFlatten),
            36 => read_prefixed!(Instruction::ListReshape {} : len),
            37 => read_prefixed!(Instruction::ListCartesianProduct {} : len),

            38 => read_prefixed!(Instruction::ListJson),
            39 => read_prefixed!(Instruction::ListCsv),
            40 => read_prefixed!(Instruction::ListColumns),
            41 => read_prefixed!(Instruction::ListLines),

            42 => read_prefixed!(Instruction::ListInsert),
            43 => read_prefixed!(Instruction::ListInsertLast),
            44 => read_prefixed!(Instruction::ListInsertRandom),

            45 => read_prefixed!(Instruction::ListGet),
            46 => read_prefixed!(Instruction::ListGetLast),
            47 => read_prefixed!(Instruction::ListGetRandom),

            48 => read_prefixed!(Instruction::ListAssign),
            49 => read_prefixed!(Instruction::ListAssignLast),
            50 => read_prefixed!(Instruction::ListAssignRandom),

            51 => read_prefixed!(Instruction::ListRemove),
            52 => read_prefixed!(Instruction::ListRemoveLast),
            53 => read_prefixed!(Instruction::ListRemoveAll),

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

            55 => read_prefixed!(Instruction::Cmp { relation: Relation::Equal }),
            56 => read_prefixed!(Instruction::Cmp { relation: Relation::NotEqual }),
            57 => read_prefixed!(Instruction::Cmp { relation: Relation::Less }),
            58 => read_prefixed!(Instruction::Cmp { relation: Relation::LessEq }),
            59 => read_prefixed!(Instruction::Cmp { relation: Relation::Greater }),
            60 => read_prefixed!(Instruction::Cmp { relation: Relation::GreaterEq }),
            61 => read_prefixed!(Instruction::Identical),

            62 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Add }),
            63 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Sub }),
            64 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Mul }),
            65 => read_prefixed!(Instruction::BinaryOp { op: BinaryOp::Div }),
            66 => read_prefixed!(Instruction::BinaryOp {} : op),

            67 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::Add, } : len),
            68 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::Mul, } : len),
            69 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::StrCat, } : len),
            70 => read_prefixed!(Instruction::VariadicOp { op: VariadicOp::MakeList, } : len),
            71 => read_prefixed!(Instruction::VariadicOp {} : op, len),

            72 => read_prefixed!(Instruction::UnaryOp { op: UnaryOp::Not }),
            73 => read_prefixed!(Instruction::UnaryOp { op: UnaryOp::Round }),
            74 => read_prefixed!(Instruction::UnaryOp {} : op),

            75 => read_prefixed!(Instruction::DeclareLocal {} : var),
            76 => read_prefixed!(Instruction::InitUpvar {} : var),
            77 => read_prefixed!(Instruction::Assign {} : var),

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

            80 => read_prefixed!(Instruction::Watcher {} : create, var),
            81 => read_prefixed!(Instruction::Pause),

            82 => read_prefixed!(Instruction::Jump {} : to),
            83 => read_prefixed!(Instruction::ConditionalJump { when: false, } : to),
            84 => read_prefixed!(Instruction::ConditionalJump { when: true, } : to),

            85 => read_prefixed!(Instruction::Call { tokens: "", } : pos),
            86 => read_prefixed!(Instruction::Call {} : pos, tokens),
            87 => read_prefixed!(Instruction::MakeClosure {} : pos, params, tokens),
            88 => read_prefixed!(Instruction::CallClosure { new_entity: false, } : args),
            89 => read_prefixed!(Instruction::CallClosure { new_entity: true, } : args),
            90 => read_prefixed!(Instruction::ForkClosure {} : args),
            91 => read_prefixed!(Instruction::Return),
            92 => read_prefixed!(Instruction::Abort {} : mode),

            93 => read_prefixed!(Instruction::PushHandler {} : pos, var),
            94 => read_prefixed!(Instruction::PopHandler),
            95 => read_prefixed!(Instruction::Throw),

            96 => read_prefixed!(Instruction::CallRpc {} : tokens),
            97 => read_prefixed!(Instruction::PushRpcError),

            98 => read_prefixed!(Instruction::Syscall {} : len),
            99 => read_prefixed!(Instruction::PushSyscallError),

            100 => read_prefixed!(Instruction::SendLocalMessage { wait: false, target: false }),
            101 => read_prefixed!(Instruction::SendLocalMessage { wait: false, target: true }),
            102 => read_prefixed!(Instruction::SendLocalMessage { wait: true, target: false }),
            103 => read_prefixed!(Instruction::SendLocalMessage { wait: true, target: true }),

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

            105 => read_prefixed!(Instruction::Print { style: PrintStyle::Say }),
            106 => read_prefixed!(Instruction::Print { style: PrintStyle::Think }),
            107 => read_prefixed!(Instruction::Ask),
            108 => read_prefixed!(Instruction::PushAnswer),

            109 => read_prefixed!(Instruction::ResetTimer),
            110 => read_prefixed!(Instruction::PushTimer),
            111 => read_prefixed!(Instruction::Sleep),
            112 => read_prefixed!(Instruction::PushRealTime {} : query),

            113 => read_prefixed!(Instruction::SendNetworkMessage { expect_reply: false, } : tokens),
            114 => read_prefixed!(Instruction::SendNetworkMessage { expect_reply: true, } : tokens),
            115 => read_prefixed!(Instruction::SendNetworkReply),

            116 => read_prefixed!(Instruction::PushProperty {} : prop),
            117 => read_prefixed!(Instruction::SetProperty {} : prop),
            118 => read_prefixed!(Instruction::ChangeProperty {} : prop),

            119 => read_prefixed!(Instruction::PushCostume),
            120 => read_prefixed!(Instruction::PushCostumeNumber),
            121 => read_prefixed!(Instruction::PushCostumeList),
            122 => read_prefixed!(Instruction::SetCostume),
            123 => read_prefixed!(Instruction::NextCostume),

            124 => read_prefixed!(Instruction::PushSoundList),
            125 => read_prefixed!(Instruction::PlaySound { blocking: true }),
            126 => read_prefixed!(Instruction::PlaySound { blocking: false }),
            127 => read_prefixed!(Instruction::PlayNotes { blocking: true }),
            128 => read_prefixed!(Instruction::PlayNotes { blocking: false }),
            129 => read_prefixed!(Instruction::StopSounds),

            130 => read_prefixed!(Instruction::Clone),
            131 => read_prefixed!(Instruction::DeleteClone),

            132 => read_prefixed!(Instruction::ClearEffects),
            133 => read_prefixed!(Instruction::ClearDrawings),

            134 => read_prefixed!(Instruction::GotoXY),
            135 => read_prefixed!(Instruction::Goto),

            136 => read_prefixed!(Instruction::PointTowardsXY),
            137 => read_prefixed!(Instruction::PointTowards),

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

            139 => 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(MAX_U64_ENCODED_BYTES));
            }};
            (@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(MAX_U64_ENCODED_BYTES));
                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::PushIntString { value } => append_prefixed!(6: value),
            Instruction::PushNumber { value } => append_prefixed!(7: value),
            Instruction::PushColor { value } => append_prefixed!(8: value),

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

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

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

            Instruction::DupeValue { top_index: 0 } => append_prefixed!(15),
            Instruction::DupeValue { top_index: 1 } => append_prefixed!(16),
            Instruction::DupeValue { top_index: 2 } => append_prefixed!(17),
            Instruction::DupeValue { top_index: 3 } => append_prefixed!(18),
            Instruction::DupeValue { top_index: _ } => unreachable!(),

            Instruction::SwapValues { top_index_1: 0, top_index_2: 1 } => append_prefixed!(19),
            Instruction::SwapValues { top_index_1: 0, top_index_2: 2 } => append_prefixed!(20),
            Instruction::SwapValues { top_index_1: 1, top_index_2: 2 } => append_prefixed!(21),
            Instruction::SwapValues { top_index_1: 1, top_index_2: 3 } => append_prefixed!(22),
            Instruction::SwapValues { top_index_1: _, top_index_2: _ } => unreachable!(),

            Instruction::TypeQuery { ty } => append_prefixed!(23: ty),
            Instruction::ToBool => append_prefixed!(24),
            Instruction::ToNumber => append_prefixed!(25),

            Instruction::ListCons => append_prefixed!(26),
            Instruction::ListCdr => append_prefixed!(27),

            Instruction::ListFind => append_prefixed!(28),
            Instruction::ListContains => append_prefixed!(29),

            Instruction::ListIsEmpty => append_prefixed!(30),
            Instruction::ListLength => append_prefixed!(31),
            Instruction::ListDims => append_prefixed!(32),
            Instruction::ListRank => append_prefixed!(33),

            Instruction::ListRev => append_prefixed!(34),
            Instruction::ListFlatten => append_prefixed!(35),
            Instruction::ListReshape { len } => append_prefixed!(36: len),
            Instruction::ListCartesianProduct { len } => append_prefixed!(37: len),

            Instruction::ListJson => append_prefixed!(38),
            Instruction::ListCsv => append_prefixed!(39),
            Instruction::ListColumns => append_prefixed!(40),
            Instruction::ListLines => append_prefixed!(41),

            Instruction::ListInsert => append_prefixed!(42),
            Instruction::ListInsertLast => append_prefixed!(43),
            Instruction::ListInsertRandom => append_prefixed!(44),

            Instruction::ListGet => append_prefixed!(45),
            Instruction::ListGetLast => append_prefixed!(46),
            Instruction::ListGetRandom => append_prefixed!(47),

            Instruction::ListAssign => append_prefixed!(48),
            Instruction::ListAssignLast => append_prefixed!(49),
            Instruction::ListAssignRandom => append_prefixed!(50),

            Instruction::ListRemove => append_prefixed!(51),
            Instruction::ListRemoveLast => append_prefixed!(52),
            Instruction::ListRemoveAll => append_prefixed!(53),

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

            Instruction::Cmp { relation: Relation::Equal } => append_prefixed!(55),
            Instruction::Cmp { relation: Relation::NotEqual } => append_prefixed!(56),
            Instruction::Cmp { relation: Relation::Less } => append_prefixed!(57),
            Instruction::Cmp { relation: Relation::LessEq } => append_prefixed!(58),
            Instruction::Cmp { relation: Relation::Greater } => append_prefixed!(59),
            Instruction::Cmp { relation: Relation::GreaterEq } => append_prefixed!(60),
            Instruction::Identical => append_prefixed!(61),

            Instruction::BinaryOp { op: BinaryOp::Add } => append_prefixed!(62),
            Instruction::BinaryOp { op: BinaryOp::Sub } => append_prefixed!(63),
            Instruction::BinaryOp { op: BinaryOp::Mul } => append_prefixed!(64),
            Instruction::BinaryOp { op: BinaryOp::Div } => append_prefixed!(65),
            Instruction::BinaryOp { op } => append_prefixed!(66: op),

            Instruction::VariadicOp { op: VariadicOp::Add, len } => append_prefixed!(67: len),
            Instruction::VariadicOp { op: VariadicOp::Mul, len } => append_prefixed!(68: len),
            Instruction::VariadicOp { op: VariadicOp::StrCat, len } => append_prefixed!(69: len),
            Instruction::VariadicOp { op: VariadicOp::MakeList, len } => append_prefixed!(70: len),
            Instruction::VariadicOp { op, len } => append_prefixed!(71: op, len),

            Instruction::UnaryOp { op: UnaryOp::Not } => append_prefixed!(72),
            Instruction::UnaryOp { op: UnaryOp::Round } => append_prefixed!(73),
            Instruction::UnaryOp { op } => append_prefixed!(74: op),

            Instruction::DeclareLocal { var } => append_prefixed!(75: move str var),
            Instruction::InitUpvar { var } => append_prefixed!(76: move str var),
            Instruction::Assign { var } => append_prefixed!(77: move str var),

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

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

            Instruction::Jump { to } => append_prefixed!(82: move to),
            Instruction::ConditionalJump { to, when: false } => append_prefixed!(83: move to),
            Instruction::ConditionalJump { to, when: true } => append_prefixed!(84: move to),

            Instruction::Call { pos, tokens: "" } => append_prefixed!(85: move pos),
            Instruction::Call { pos, tokens } => append_prefixed!(86: move pos, move str tokens),
            Instruction::MakeClosure { pos, params, tokens } => append_prefixed!(87: move pos, params, move str tokens),
            Instruction::CallClosure { new_entity: false, args } => append_prefixed!(88: args),
            Instruction::CallClosure { new_entity: true, args } => append_prefixed!(89: args),
            Instruction::ForkClosure { args } => append_prefixed!(90: args),
            Instruction::Return => append_prefixed!(91),
            Instruction::Abort { mode } => append_prefixed!(92: mode),

            Instruction::PushHandler { pos, var } => append_prefixed!(93: move pos, move str var),
            Instruction::PopHandler => append_prefixed!(94),
            Instruction::Throw => append_prefixed!(95),

            Instruction::CallRpc { tokens } => append_prefixed!(96: move str tokens),
            Instruction::PushRpcError => append_prefixed!(97),

            Instruction::Syscall { len } => append_prefixed!(98: len),
            Instruction::PushSyscallError => append_prefixed!(99),

            Instruction::SendLocalMessage { wait: false, target: false } => append_prefixed!(100),
            Instruction::SendLocalMessage { wait: false, target: true } => append_prefixed!(101),
            Instruction::SendLocalMessage { wait: true, target: false } => append_prefixed!(102),
            Instruction::SendLocalMessage { wait: true, target: true } => append_prefixed!(103),

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

            Instruction::Print { style: PrintStyle::Say } => append_prefixed!(105),
            Instruction::Print { style: PrintStyle::Think } => append_prefixed!(106),
            Instruction::Ask => append_prefixed!(107),
            Instruction::PushAnswer => append_prefixed!(108),

            Instruction::ResetTimer => append_prefixed!(109),
            Instruction::PushTimer => append_prefixed!(110),
            Instruction::Sleep => append_prefixed!(111),
            Instruction::PushRealTime { query } => append_prefixed!(112: query),

            Instruction::SendNetworkMessage { tokens, expect_reply: false } => append_prefixed!(113: move str tokens),
            Instruction::SendNetworkMessage { tokens, expect_reply: true } => append_prefixed!(114: move str tokens),
            Instruction::SendNetworkReply => append_prefixed!(115),

            Instruction::PushProperty { prop } => append_prefixed!(116: prop),
            Instruction::SetProperty { prop } => append_prefixed!(117: prop),
            Instruction::ChangeProperty { prop } => append_prefixed!(118: prop),

            Instruction::PushCostume => append_prefixed!(119),
            Instruction::PushCostumeNumber => append_prefixed!(120),
            Instruction::PushCostumeList => append_prefixed!(121),
            Instruction::SetCostume => append_prefixed!(122),
            Instruction::NextCostume => append_prefixed!(123),

            Instruction::PushSoundList => append_prefixed!(124),
            Instruction::PlaySound { blocking: true } => append_prefixed!(125),
            Instruction::PlaySound { blocking: false } => append_prefixed!(126),
            Instruction::PlayNotes { blocking: true } => append_prefixed!(127),
            Instruction::PlayNotes { blocking: false } => append_prefixed!(128),
            Instruction::StopSounds => append_prefixed!(129),

            Instruction::Clone => append_prefixed!(130),
            Instruction::DeleteClone => append_prefixed!(131),

            Instruction::ClearEffects => append_prefixed!(132),
            Instruction::ClearDrawings => append_prefixed!(133),

            Instruction::GotoXY => append_prefixed!(134),
            Instruction::Goto => append_prefixed!(135),

            Instruction::PointTowardsXY => append_prefixed!(136),
            Instruction::PointTowards => append_prefixed!(137),

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

            Instruction::UnknownBlock { name, args } => append_prefixed!(139: 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`].
/// 
/// 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>, Option<(Number, Number)>),
    Audio(Vec<u8>),
    String(CompactString),
}
#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
pub(crate) struct EntityInitInfo {
    pub(crate) name: CompactString,
    pub(crate) fields: VecMap<CompactString, InitValue, false>,
    pub(crate) costumes: VecMap<CompactString, InitValue, false>,
    pub(crate) sounds: VecMap<CompactString, InitValue, false>,
    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: CompactString,
    pub(crate) ref_values: Vec<RefValue>,
    pub(crate) globals: VecMap<CompactString, InitValue, false>,
    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>)>,
}

struct LocationTokenizer<'a> {
    src: &'a str,
    state: bool,
}
impl<'a> LocationTokenizer<'a> {
    fn new(src: &'a str) -> Self {
        Self { src, state: false }
    }
}
impl<'a> Iterator for LocationTokenizer<'a> {
    type Item = &'a str;
    fn next(&mut self) -> Option<Self::Item> {
        if self.src.is_empty() {
            return None;
        }

        let p = self.src.char_indices().find(|x| self.state ^ (x.1 == '-' || ('0'..='9').contains(&x.1))).map(|x| x.0).unwrap_or(self.src.len());
        let res;
        (res, self.src) = self.src.split_at(p);
        self.state ^= true;
        Some(res)
    }
}
#[test]
fn test_locations_tokenizer() {
    assert_eq!(LocationTokenizer::new("").collect::<Vec<_>>(), &[] as &[&str]);
    assert_eq!(LocationTokenizer::new("x").collect::<Vec<_>>(), &["x"]);
    assert_eq!(LocationTokenizer::new("3").collect::<Vec<_>>(), &["", "3"]);
    assert_eq!(LocationTokenizer::new("collab_").collect::<Vec<_>>(), &["collab_"]);
    assert_eq!(LocationTokenizer::new("collab_-1").collect::<Vec<_>>(), &["collab_", "-1"]);
    assert_eq!(LocationTokenizer::new("collab_23_43").collect::<Vec<_>>(), &["collab_", "23", "_", "43"]);
    assert_eq!(LocationTokenizer::new("cab_=_2334fhd__43").collect::<Vec<_>>(), &["cab_=_", "2334", "fhd__", "43"]);
    assert_eq!(LocationTokenizer::new("cab_=_2334fhd__43__").collect::<Vec<_>>(), &["cab_=_", "2334", "fhd__", "43", "__"]);
    assert_eq!(LocationTokenizer::new("-4cab_=_2334fhd__43__").collect::<Vec<_>>(), &["", "-4", "cab_=_", "2334", "fhd__", "43", "__"]);
    assert_eq!(LocationTokenizer::new("714cab_=_2334fhd__43__").collect::<Vec<_>>(), &["", "714", "cab_=_", "2334", "fhd__", "43", "__"]);
}

/// 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))]
#[derive(Debug)]
pub struct Locations {
    #[allow(dead_code)] tag: MustBeU128<FINGERPRINT>,

    prefix: CompactString,
    separator: CompactString,
    suffix: CompactString,

    base_token: isize,
    value_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: CompactString::default(),
                separator: CompactString::default(),
                suffix: CompactString::default(),

                base_token: 0,
                value_data: Default::default(),
                locs: Default::default(),
            });
        }

        let (prefix, suffix) = {
            let mut tokens = LocationTokenizer::new(*orig_locs.values().next().unwrap()).enumerate();
            let prefix = tokens.next().map(|x| CompactString::new(x.1)).unwrap_or_default();
            let suffix = tokens.last().filter(|x| x.0 & 1 == 0).map(|x| CompactString::new(x.1)).unwrap_or_default();
            (prefix, suffix)
        };
        let mut separator = None;

        let mut value_map = Vec::with_capacity(orig_locs.len());
        for (&pos, &loc) in orig_locs.iter() {
            let mut tokens = LocationTokenizer::new(loc).peekable();
            let mut values = vec![];
            for i in 0.. {
                match tokens.next() {
                    Some(token) => {
                        if i & 1 != 0 {
                            let v: isize = match token.parse() {
                                Ok(x) => x,
                                Err(_) => return Err(CompileError::InvalidLocation { loc }),
                            };
                            if v.to_string() != token {
                                return Err(CompileError::InvalidLocation { loc });
                            }
                            values.push(v);
                        }
                        else if i == 0 {
                            if token != prefix {
                                return Err(CompileError::InvalidLocation { loc });
                            }
                        }
                        else if tokens.peek().is_none() {
                            if token != suffix {
                                return Err(CompileError::InvalidLocation { loc });
                            }
                        } else {
                            match &separator {
                                Some(separator) => if token != *separator {
                                    return Err(CompileError::InvalidLocation { loc });
                                }
                                None => separator = Some(CompactString::new(token)),
                            }
                        }
                    }
                    None => {
                        if i < 2 || (i & 1 == 0 && !suffix.is_empty()) {
                            return Err(CompileError::InvalidLocation { loc });
                        }
                        break;
                    }
                }
            }
            debug_assert!(values.len() >= 1);
            value_map.push((pos, values));
        }

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

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

        let res = Self { tag: Default::default(), separator: separator.unwrap_or_default(), prefix, suffix, base_token, value_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<CompactString> {
        let mut start = {
            let p = self.locs.partition_point(|x| x.0 <= bytecode_pos);
            debug_assert!(p <= self.locs.len());
            self.locs.get(p)?.1
        };

        let mut res = self.prefix.clone();
        let mut first = true;
        loop {
            let (v, aft) = decode_u64(&self.value_data, start);
            if v == 0 {
                break;
            }

            start = aft;
            if !first {
                res.push_str(&self.separator);
            }
            first = false;
            res.push_str(&(v as isize - 1 + self.base_token).to_string());
        }
        res.push_str(&self.suffix);
        Some(res)
    }
}
#[test]
fn test_locations_formats() {
    fn test_vals<'a>(orig_locs: &BTreeMap<usize, &'a str>) -> Result<(), CompileError<'a>> {
        let condensed = Locations::condense(orig_locs)?;

        let mut back = BTreeMap::new();
        for &k in orig_locs.keys() {
            back.insert(k, condensed.lookup(k - 1).unwrap());
        }

        if orig_locs.len() != back.len() || orig_locs.iter().zip(back.iter()).any(|(a, b)| a.0 != b.0 || a.1 != b.1) {
            panic!("expected {orig_locs:?}\ngot {back:?}");
        }

        Ok(())
    }
    macro_rules! map {
        ($($k:expr => $v:expr),*$(,)?) => {{
            #[allow(unused_mut)]
            let mut res = BTreeMap::new();
            $(res.insert($k, $v);)*
            res
        }}
    }

    test_vals(&map! { }).unwrap();
    test_vals(&map! { 43 => "collab_3_4" }).unwrap();
    test_vals(&map! { 43 => "collab_3_4", 2 => "collab_-2_-34" }).unwrap();
    test_vals(&map! { 43 => "collab_3_4", 2 => "collab_-02_-34" }).unwrap_err();
    test_vals(&map! { 43 => "collab_3_4", 2 => "coLlab_-2_-34" }).unwrap_err();
    test_vals(&map! { 43 => "_31_-24", 2 => "_-2_-342", 6 => "_23" }).unwrap();
    test_vals(&map! { 43 => "31_-24", 2 => "-2_-342", 6 => "23" }).unwrap();
    test_vals(&map! { 43 => "31_-24", 2 => "-2_-342", 6 => "g23" }).unwrap_err();
    test_vals(&map! { 43 => "31_-24", 2 => "g-2_-342", 6 => "23" }).unwrap_err();
    test_vals(&map! { 43 => "g31_-24", 2 => "g-2_-342", 6 => "g23" }).unwrap();
    test_vals(&map! { 43 => "31_-24", 2 => "-2_-342<", 6 => "23" }).unwrap_err();
    test_vals(&map! { 43 => "31_-24", 2 => "-2_-342", 6 => "23&" }).unwrap_err();
    test_vals(&map! { 43 => "31_-24&", 2 => "-2_-342&", 6 => "23&" }).unwrap();
    test_vals(&map! { 43 => "31::-24&", 2 => "-2::-342&", 6 => "23&" }).unwrap();
    test_vals(&map! { 43 => "31::-24&", 2 => "-2::-342&", 6 => "23&", 7 => "&" }).unwrap_err();
    test_vals(&map! { 43 => "31::-24&", 2 => "-2::-342&", 6 => "23&", 0 => "&" }).unwrap_err();
    test_vals(&map! { 43 => "31::-24&", 2 => "-2::-342&", 6 => "23&" }).unwrap();
    test_vals(&map! { 43 => "31::-24&", 2 => "-2::-342&", 6 => "23&&" }).unwrap_err();
    test_vals(&map! { 43 => "<>31::-24&", 2 => "<>-2::-342:.:5::-22&", 6 => "<>23&" }).unwrap_err();
    test_vals(&map! { 43 => "<>31::-24&", 2 => "<>-2::-342::5::-22&", 6 => "<>23&" }).unwrap();
    test_vals(&map! { 43 => "<>31::-24&", 2 => "<>-2::-342::5::-22&", 6 => "<>&" }).unwrap_err();
    test_vals(&map! { 43 => "<>31::-24&", 2 => "<>-2::-342::5::-22&", 0 => "<>&" }).unwrap_err();
    test_vals(&map! { 43 => "<>31::-24&", 2 => "<>-2::-342::5::-22&", 6 => "<>23" }).unwrap_err();
    test_vals(&map! { 43 => "31,-24", 2 => "-2,-342,5,-22", 6 => "23", 7 => "" }).unwrap_err();
    test_vals(&map! { 43 => "31,-24", 2 => "-2,-342,5,-22", 6 => "23", 0 => "" }).unwrap_err();
}

struct ByteCodeBuilder<'a: 'b, 'b> {
    ins: Vec<InternalInstruction<'b>>,
    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>,
    string_arena: &'b typed_arena::Arena<CompactString>,
}
impl<'a: 'b, 'b> ByteCodeBuilder<'a, 'b> {
    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 => core::f64::consts::PI,
                ast::Constant::E => core::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::Audio(_) => unreachable!(), // Snap! doesn't have audio 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::Identical)?,
            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::ListLen { 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::ListCsv { value } => self.append_simple_ins(entity, &[value], Instruction::ListCsv)?,
            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::RealTime { query } => self.ins.push(Instruction::PushRealTime { query: query.into() }.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::SoundList => self.ins.push(Instruction::PushSoundList.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, 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: "closure types are indistinguishable".into() }),
                };
                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 } => {
                let mut tokens = LosslessJoin::new();
                tokens.push(service);
                tokens.push(rpc);
                for (arg_name, arg) in args {
                    tokens.push(arg_name);
                    self.append_expr(arg, entity)?;
                }
                self.ins.push(Instruction::CallRpc { tokens: self.string_arena.alloc(tokens.finish()) }.into());
            }
            ast::ExprKind::NetworkMessageReply { target, msg_type, values } => {
                let mut tokens = LosslessJoin::new();
                tokens.push(msg_type);
                for (field, value) in values {
                    self.append_expr(value, entity)?;
                    tokens.push(field);
                }
                self.append_expr(target, entity)?;
                self.ins.push(Instruction::SendNetworkMessage { tokens: self.string_arena.alloc(tokens.finish()), 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::PenClear => self.ins.push(Instruction::ClearDrawings.into()),
            ast::StmtKind::DeleteClone => self.ins.push(Instruction::DeleteClone.into()),
            ast::StmtKind::Stop { mode: ast::StopMode::ThisScript } => self.ins.push(Instruction::Abort { mode: AbortMode::Current }.into()),
            ast::StmtKind::Stop { mode: ast::StopMode::All } => self.ins.push(Instruction::Abort { mode: AbortMode::All }.into()),
            ast::StmtKind::Stop { mode: ast::StopMode::AllButThisScript } => self.ins.push(Instruction::Abort { mode: AbortMode::Others }.into()),
            ast::StmtKind::Stop { mode: ast::StopMode::OtherScriptsInSprite } => self.ins.push(Instruction::Abort { mode: AbortMode::MyOthers }.into()),
            ast::StmtKind::SetCostume { costume } => self.append_simple_ins(entity, &[costume], Instruction::SetCostume)?,
            ast::StmtKind::PlaySound { sound, blocking } => self.append_simple_ins(entity, &[sound], Instruction::PlaySound { blocking: *blocking })?,
            ast::StmtKind::PlayNotes { notes, beats, blocking } => self.append_simple_ins(entity, &[notes, beats], Instruction::PlayNotes { blocking: *blocking })?,
            ast::StmtKind::Rest { beats } => {
                self.ins.push(Instruction::VariadicOp { op: VariadicOp::MakeList, len: VariadicLen::Fixed(0) }.into());
                self.append_expr(beats, entity)?;
                self.ins.push(Instruction::PlayNotes { blocking: true }.into());
            }
            ast::StmtKind::StopSounds => self.ins.push(Instruction::StopSounds.into()),
            ast::StmtKind::Stop { mode: ast::StopMode::ThisBlock } => {
                self.ins.push(Instruction::PushString { value: "" }.into());
                self.ins.push(Instruction::Return.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::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());
                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::CallRpc { service, rpc, args } => {
                let mut tokens = LosslessJoin::new();
                tokens.push(service);
                tokens.push(rpc);
                for (arg_name, arg) in args {
                    tokens.push(arg_name);
                    self.append_expr(arg, entity)?;
                }
                self.ins.push(Instruction::CallRpc { tokens: self.string_arena.alloc(tokens.finish()) }.into());
                self.ins.push(Instruction::PopValue.into());
            }
            ast::StmtKind::SendNetworkMessage { target, msg_type, values } => {
                let mut tokens = LosslessJoin::new();
                tokens.push(msg_type);
                for (field, value) in values {
                    self.append_expr(value, entity)?;
                    tokens.push(field);
                }
                self.append_expr(target, entity)?;
                self.ins.push(Instruction::SendNetworkMessage { tokens: self.string_arena.alloc(tokens.finish()), 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, 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(core::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 tokens = LosslessJoin::new();
            for param in fn_info.params.iter() {
                tokens.push(&param.trans_name);
            }

            self.ins[*hole_pos] = Instruction::Call { pos, tokens: self.string_arena.alloc(tokens.finish()) }.into();
        }

        self.optimize();
        self.finalize(funcs, entities)
    }
    fn optimize(&mut self) {
        let mut code = vec![];
        let mut data = BinPool::new(); // not used
        let mut relocate_info = vec![]; // not used

        for ins in &mut self.ins {
            match ins {
                InternalInstruction::Illegal => unreachable!(),
                InternalInstruction::Valid(ins) => match ins {
                    Instruction::PushString { value: str_value } => match str_value.parse::<i32>() {
                        Ok(value) => {
                            if value.to_compact_string() != *str_value { continue }

                            code.clear();
                            BinaryWrite::append(&value, &mut code, &mut data, &mut relocate_info);
                            debug_assert!(code.len() > 0);
                            if code.len() >= 3 { continue }

                            *ins = Instruction::PushIntString { value };
                        }
                        Err(_) => (),
                    }
                    _ => (),
                }
            }
        }

        debug_assert!(data.is_empty());
        debug_assert!(relocate_info.is_empty());
    }
    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::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(MAX_U64_ENCODED_BYTES);
            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(MAX_U64_ENCODED_BYTES);
        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(role: &ast::Role) -> Result<(ByteCode, InitInfo, Locations, ScriptInfo), CompileError> {
        let string_arena = Default::default();
        let mut code = ByteCodeBuilder {
            ins: Default::default(),
            call_holes: Default::default(),
            closure_holes: Default::default(),
            ins_locations: Default::default(),
            string_arena: &string_arena,
        };

        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 tokens = LosslessJoin::new();
            for param in params {
                tokens.push(&param.trans_name);
            }
            for param in captures {
                tokens.push(&param.trans_name);
            }

            code.ins[hole_pos] = Instruction::MakeClosure { pos, params: params.len(), tokens: string_arena.alloc(tokens.finish()) }.into();
        }

        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();
        let mut audio_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(_) | ast::Value::Audio(_) => (), // lazily link
                ast::Value::List(values, 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 value in values {
                        register_ref_values(value, ref_values, refs);
                    }
                }
            }
        }

        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>, Option<(f64, f64)>), usize>, audio_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(core::f64::consts::E)?),
                    ast::Constant::Pi => InitValue::Number(Number::new(core::f64::consts::PI)?),
                }
                ast::Value::Ref(x) => {
                    let idx = *refs.get(&x.0).ok_or(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 center = x.1.map(|(x, y)| Ok::<_,NumberError>((Number::new(x)?, Number::new(y)?))).transpose()?;
                    let idx = *image_refs.entry(Rc::as_ptr(x)).or_insert_with(|| {
                        ref_values.push((Some(RefValue::Image(x.0.clone(), center)), value));
                        ref_values.len() - 1
                    });
                    InitValue::Ref(idx)
                }
                ast::Value::Audio(x) => {
                    let idx = *audio_refs.entry(Rc::as_ptr(x)).or_insert_with(|| {
                        ref_values.push((Some(RefValue::Audio((**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, audio_refs)).collect::<Result<_,_>>()?);
                    match ref_id {
                        Some(ref_id) => {
                            let idx = *refs.get(&ref_id.0).ok_or(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 = VecMap::new();
        let mut entities = vec![];

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

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

            let visible = entity.visible;
            let active_costume = entity.active_costume;
            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(util::modulus(entity.heading, 360.0))?;

            for field in entity.fields.iter() {
                fields.insert(field.def.name.clone(), get_value(&field.init, &mut ref_values, &refs, &mut string_refs, &mut image_refs, &mut audio_refs)?);
            }
            for costume in entity.costumes.iter() {
                costumes.insert(costume.def.name.clone(), get_value(&costume.init, &mut ref_values, &refs, &mut string_refs, &mut image_refs, &mut audio_refs)?);
            }
            for sound in entity.sounds.iter() {
                sounds.insert(sound.def.name.clone(), get_value(&sound.init, &mut ref_values, &refs, &mut string_refs, &mut image_refs, &mut audio_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::Unknown { name, fields } => Event::Custom { name: name.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, sounds, costumes, scripts, active_costume, pos, heading, size, visible, color });
        }

        let ref_values = ref_values.into_iter().map(|x| x.0.ok_or(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 std::io::Write) -> std::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 std::io::Write) -> std::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()
    }
}