Skip to content

:hedgehog: PostHog is the leading platform for building self-driving products. Our developer tools – AI observability, analytics, session replay, flags, experiments, error tracking, logs, and more – capture all the context agents need to diagnose problems, uncover opportunities, and ship fixes. Steer it all from Slack, web, desktop, or the MCP.

60.6 KB
Raw Blame
//! An abstract interpreter over the decoded control-flow graph, producing the set of globals a
//! condition reads.
//!
//! The abstract domain has two values: a compile-time literal string, and everything else. That is
//! all `GET_GLOBAL` needs, because it builds its path from literal strings the compiler pushed and
//! nothing else can reach the globals dict.
//!
//! Branches are followed rather than refused. A worklist carries an abstract stack along each path;
//! where paths meet, the stacks are joined cell by cell, and the pass repeats until nothing
//! changes. That matters because the cohort compiler lowers the ordinary operators through jumps:
//! `null_safe_comparisons` rewrites every `>`/`>=`/`<`/`<=` into an `if`, regex goes through
//! `ifNull`, and `between` compiles to a local-slot IIFE. Refusing branches would report almost
//! every date and regex condition as unreadable.
//!
//! Only instructions more than one edge can reach hold a stored stack, and a straight-line run is
//! walked in place with one stack rather than through the worklist. Both matter for cost, not
//! elegance: a `properties.x IN (...)` leaf pushes every list element before `IN` pops them, and
//! catalogs hold lists of several thousand. Storing and copying a stack per instruction over that
//! is quadratic in the program's own length, which on the largest real list size meant seconds of
//! blocking and over a gigabyte, for a program the VM evaluates in kilobytes.
//!
//! That gating answers the shape it was built for and no other. A program that is *all* merge
//! points — a deep stack of literals, then a chain of rejoining diamonds — stores and copies a
//! stack at every one of them, and a transfer-step ceiling does not bound that, because one step
//! can copy a whole stack. So the two ceilings in [`AnalysisBudget`] are both needed: steps for the
//! programs that spend without copying, copied cells for the programs that copy without spending.
//!
//! The pass stays fail-closed everywhere it is not sure. Two paths that meet at different stack
//! depths, a jump into the middle of an instruction, a local slot outside the frame, or a `RETURN`
//! that leaves the stack unbalanced all stop the analysis and widen the condition to every column.
//! Reads accumulate globally rather than per instruction, so a join can never retract one.
//!
//! One case answers rather than widens. A `GET_GLOBAL` root that no globals dict carries reads
//! nothing under any projection, so it claims no path and the walk continues. A bare
//! representation-sensitive native is the exception, because such a root is a closure the program
//! can still call — see [`Interpreter::get_global`].

use std::collections::{BTreeSet, VecDeque};
use std::sync::Arc;

use hogvm::Operation;
use serde_json::Value;

use super::decode::{decode, Decoded, InstrIndex, InstrKind, TokenIndex};
use super::{FullColumnsReason, GlobalRoot, Projection, ReadPath, UnanalyzableReason};

/// `elements_chain` falls back to this property when the event's own column is empty, so a caller
/// that projects an `elements_chain` read must carry it too.
pub(super) const ELEMENTS_CHAIN_PROPERTY: &str = "$elements_chain";

/// Natives whose result depends on how a JSON number was spelled, rather than on its value.
///
/// A caller acting on [`Projection::Reads`] supplies the claimed paths through its own storage, and
/// the seeder supplies them by having ClickHouse rebuild the blob from the kept keys. That rebuild
/// re-prints every number it copies, so a whole-number float token arrives as an integer one:
/// `{"n": 100.0}` becomes `{"n": 100}`, which the VM loads as `Num::Integer(100)` where live
/// evaluation loads `Num::Float(100.0)`.
///
/// Most of the VM cannot see that. Equality unifies the two variants, arithmetic and ordering widen
/// a mixed pair to `f64`, and the printer renders `Float(100.0)` and `Integer(100)` as the same
/// text. The exceptions are the natives below, each of which branches on `Num::is_float` in a way
/// that reaches its result: `typeof` answers `"float"` or `"integer"`, and `jsonStringify` keeps the
/// decimal point only for the float variant. A condition calling either would seed a membership its
/// live evaluation disagrees with, so the whole condition takes every column instead.
///
/// One residual is accepted rather than covered. `print_hog_value` renders an object carrying an
/// `__hx_ast` key back to SQL, and that printer does distinguish the variants, so `toString` of a
/// property whose value is shaped like a HogQL AST node is sensitive too. That needs a customer
/// blob built to look like compiler output, which no filter the product writes can produce.
const REPRESENTATION_SENSITIVE_NATIVES: [&str; 2] = ["typeof", "jsonStringify"];

/// A ceiling on transfer steps one program may take, so a program the lattice argument does not
/// cover cannot hang the caller. The fixpoint is reached far sooner: a merge point's stack can only
/// move upward, one cell at a time, so the work is quadratic in the program length at worst and
/// this only fires if that reasoning is wrong.
const MAX_WORKLIST_STEPS: usize = 1_000_000;

/// A ceiling on the abstract stack cells one program may copy in total.
///
/// The step ceiling does not bound the work on its own: one step can copy a whole stack at a merge
/// point, so the two multiply. A deep stack followed by a chain of rejoining diamonds is all merge
/// points, so merge-point gating does not apply to it, and the pair of ceilings alone admits about
/// `1e12` cell copies. Charging what is actually copied is what makes the bounded cost the cost
/// incurred.
const MAX_COPIED_CELLS: usize = 16_000_000;

/// A ceiling on the abstract stack cells the pass holds at once, across stored merge-point states
/// and the worklist together. A memory ceiling rather than a work one, so it is per program however
/// the caller shares [`AnalysisBudget`].
///
/// The pass would otherwise be quadratic in a shape production already writes: a `properties.x IN
/// (...)` leaf pushes every list element before `IN` pops them, and catalogs hold lists of several
/// thousand. Storing one stack per instruction across such a program is cells proportional to the
/// square of its length. Merge-point gating removes that for straight-line code; this bounds what
/// is left, so a shape nobody predicted costs a wide answer rather than the process.
const MAX_RETAINED_CELLS: usize = 1_000_000;

/// A ceiling on the work an analysis may do, in transfer steps and copied abstract stack cells.
///
/// Both units are load-bearing. A step ceiling alone lets one step copy a whole stack, so the two
/// multiply; a cell ceiling alone says nothing about a straight-line run, which is walked in place
/// and copies nothing.
///
/// A budget may be shared by a batch of conditions, which is how a caller bounds the batch rather
/// than each member of it: per-condition ceilings alone leave `conditions × ceiling`, and nothing
/// caps the conditions on a run. Sharing keeps the analysis a pure function of its input — a batch
/// is analyzed in a fixed order, so it always spends the budget the same way, which a wall-clock
/// deadline would not. Past the budget every remaining condition reports it and fails closed.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub struct AnalysisBudget {
    /// Transfer steps left to take.
    pub steps: usize,
    /// Abstract stack cells left to copy.
    pub cells: usize,
}

impl AnalysisBudget {
    /// What one condition may cost on its own.
    pub const fn for_one_condition() -> Self {
        Self {
            steps: MAX_WORKLIST_STEPS,
            cells: MAX_COPIED_CELLS,
        }
    }

    /// What `worst_case_conditions` conditions cost together, each saturating its own ceiling. The
    /// unit is a worst case rather than a condition, so a batch of any size fits a budget the
    /// caller can reason about in wall-clock terms.
    pub const fn for_conditions(worst_case_conditions: usize) -> Self {
        Self {
            steps: MAX_WORKLIST_STEPS.saturating_mul(worst_case_conditions),
            cells: MAX_COPIED_CELLS.saturating_mul(worst_case_conditions),
        }
    }

    fn spend(&mut self, steps: usize, cells: usize) {
        self.steps = self.steps.saturating_sub(steps);
        self.cells = self.cells.saturating_sub(cells);
    }
}

/// Which instructions more than one edge can reach.
///
/// The successor sets are the transfer function's, over-approximated: a conditional jump is counted
/// as reaching both of its edges even where the interpreter later finds only one live, and a refused
/// opcode is counted as falling through. Over-approximating only turns more instructions into merge
/// points, which costs memory and never correctness — while under-approximating would drop a join
/// and let the pass read a stack no path actually produces.
fn merge_points(decoded: &Decoded, starts: &[TokenIndex]) -> Vec<bool> {
    let mut in_degree = vec![0_u32; decoded.instrs.len()];
    if in_degree.is_empty() {
        return Vec::new();
    }
    // The program is entered at its first instruction, which is an edge like any other: a backward
    // jump onto it must make it a merge point rather than overwrite the entry state.
    in_degree[0] = 1;
    for (index, instr) in decoded.instrs.iter().enumerate() {
        let falls_through = !matches!(
            instr.kind,
            InstrKind::Bare(Operation::Return)
                | InstrKind::Branch {
                    op: Operation::Jump,
                    ..
                }
        );
        if falls_through && index + 1 < in_degree.len() {
            in_degree[index + 1] = in_degree[index + 1].saturating_add(1);
        }
        if let InstrKind::Branch {
            target: Some(target),
            ..
        } = instr.kind
        {
            if let Ok(landed) = starts.binary_search(&target) {
                in_degree[landed] = in_degree[landed].saturating_add(1);
            }
        }
    }
    in_degree.into_iter().map(|degree| degree >= 2).collect()
}

/// One cell of the abstract stack.
#[derive(Debug, Clone, PartialEq, Eq)]
enum AbstractValue {
    /// A string literal the compiler pushed, which a `GET_GLOBAL` path may be built from.
    LiteralString(Arc<str>),
    /// A value the model cannot name.
    Opaque,
}

impl AbstractValue {
    /// The join of two cells. Two identical literals stay a literal; anything else is the top of
    /// the two-value lattice, which is what makes the fixpoint terminate.
    fn join(&self, other: &Self) -> Self {
        match (self, other) {
            (Self::LiteralString(left), Self::LiteralString(right)) if left == right => {
                Self::LiteralString(Arc::clone(left))
            }
            _ => Self::Opaque,
        }
    }
}

type AbstractStack = Vec<AbstractValue>;

pub(super) fn project(bytecode: &[Value], budget: &mut AnalysisBudget) -> Projection {
    // A spent budget stops before the decode too. Decoding is work proportional to the whole
    // program, so a batch that ran out on its first condition would otherwise still pay it for
    // every remaining one.
    if budget.steps == 0 {
        return full_columns(UnanalyzableReason::IterationBudget);
    }
    let decoded = match decode(bytecode) {
        Ok(decoded) => decoded,
        Err(error) => return full_columns(UnanalyzableReason::Decode(error)),
    };
    let mut interpreter = Interpreter::new(&decoded, *budget);
    let outcome = interpreter.run();
    // Charged however the pass ended: a condition that spent the budget and then failed closed has
    // still spent it.
    budget.spend(interpreter.steps, interpreter.cells_copied);
    match outcome {
        Ok(reads) => Projection::Reads(reads),
        Err(Stop::Unanalyzable(reason)) => full_columns(reason),
        Err(Stop::Unnarrowable(reason)) => Projection::FullColumns(reason),
    }
}

fn full_columns(reason: UnanalyzableReason) -> Projection {
    Projection::FullColumns(FullColumnsReason::Unanalyzable(reason))
}

/// Why the interpreter stopped early. [`Stop::Unnarrowable`] is an ordinary program the analysis
/// understood and cannot narrow; everything else is the fail-closed arm.
enum Stop {
    Unanalyzable(UnanalyzableReason),
    Unnarrowable(FullColumnsReason),
}

/// What an instruction does to control flow, after its own stack effect has been applied. Both
/// conditional jumps produce [`Control::Fork`]: they differ in whether they pop, and that
/// difference is already spent by the time the successors are computed, so the two edges out of
/// either one carry the same stack.
enum Control {
    /// The program ends on this path.
    Terminate,
    /// Continue with the next instruction.
    Fall,
    /// Continue at one specific token. `None` is a jump the decoder could not resolve, which
    /// fails closed here rather than at decode, so a dead one costs nothing.
    Jump(Option<TokenIndex>),
    /// Continue at the next instruction and at one specific token.
    Fork(Option<TokenIndex>),
}

struct Interpreter<'a> {
    decoded: &'a Decoded,
    /// The token each instruction starts at, so a jump target resolves to an instruction. Linear
    /// rather than a map: programs are short, and this keeps the lookup allocation-free.
    starts: Vec<TokenIndex>,
    /// Which instructions more than one edge can reach. Only those need a stored stack to join
    /// into; the rest have a single predecessor, so their incoming stack is already the joined one
    /// and is handed straight to them on the worklist.
    merge_points: Vec<bool>,
    /// The joined stack every path into a merge point agrees on. Always `None` for the rest, so a
    /// straight-line program stores nothing at all.
    entry: Vec<Option<AbstractStack>>,
    /// Stack cells alive in `entry` and on the worklist together. Bounding this is what keeps the
    /// pass's memory a function of the program's branching rather than of its length.
    retained: usize,
    /// Transfer steps taken and stack cells copied so far. Read back by [`project`] and charged
    /// against the caller's budget, so a batch sharing one budget pays for what each member spent.
    steps: usize,
    cells_copied: usize,
    /// This program's ceilings: its own, capped by what the caller's budget has left.
    step_ceiling: usize,
    cell_ceiling: usize,
    /// Accumulated across every visit and never retracted. Held outside the per-instruction state
    /// on purpose: a join that narrowed a read set could make the analysis claim fewer globals
    /// than the program touches, which is the one failure this module must not have.
    reads: BTreeSet<ReadPath>,
    worklist: VecDeque<(InstrIndex, AbstractStack)>,
}

impl<'a> Interpreter<'a> {
    fn new(decoded: &'a Decoded, budget: AnalysisBudget) -> Self {
        let starts: Vec<TokenIndex> = decoded.instrs.iter().map(|instr| instr.start).collect();
        let count = decoded.instrs.len();
        // Every instruction is re-processed once per widening of a merge point upstream of it, and
        // a merge point widens at most once per stack cell. The quadratic term covers that; the
        // factor is headroom, so a legitimate program never reports the budget instead of an answer.
        let step_ceiling = count
            .checked_mul(count + 1)
            .and_then(|product| product.checked_mul(4))
            .unwrap_or(MAX_WORKLIST_STEPS)
            .min(MAX_WORKLIST_STEPS)
            .min(budget.steps);
        Self {
            merge_points: merge_points(decoded, &starts),
            starts,
            decoded,
            entry: vec![None; count],
            retained: 0,
            steps: 0,
            cells_copied: 0,
            step_ceiling,
            cell_ceiling: MAX_COPIED_CELLS.min(budget.cells),
            reads: BTreeSet::new(),
            worklist: VecDeque::new(),
        }
    }

    fn run(&mut self) -> Result<BTreeSet<ReadPath>, Stop> {
        if self.decoded.instrs.is_empty() {
            return Ok(BTreeSet::new());
        }
        self.enqueue(InstrIndex(0), AbstractStack::new());

        while let Some((InstrIndex(entry_index), stack)) = self.worklist.pop_front() {
            self.retained -= stack.len();
            let mut index = entry_index;
            let mut stack = stack;
            // Walk the straight-line run out of this instruction in place. Handing each step back
            // through the worklist would copy the whole stack per instruction, which is a copy per
            // element of a large `IN` list — quadratic in the program's own length.
            loop {
                self.steps += 1;
                if self.steps > self.step_ceiling {
                    return Err(Stop::Unanalyzable(UnanalyzableReason::IterationBudget));
                }
                if self.retained + stack.len() > MAX_RETAINED_CELLS
                    || self.cells_copied > self.cell_ceiling
                {
                    return Err(Stop::Unanalyzable(UnanalyzableReason::StateBudget));
                }
                let next = match self.transfer(index, &mut stack)? {
                    Control::Terminate => break,
                    Control::Fall => self.next_index(index),
                    Control::Jump(target) => self.target_index(target)?,
                    Control::Fork(target) => {
                        // Two live successors, so neither can take the stack by value.
                        self.propagate_next(index, &stack)?;
                        self.propagate_token(target, &stack)?;
                        break;
                    }
                };
                let Some(next) = next else {
                    break;
                };
                if self.merge_points[next] {
                    self.propagate(InstrIndex(next), &stack)?;
                    break;
                }
                index = next;
            }
        }
        Ok(std::mem::take(&mut self.reads))
    }

    fn enqueue(&mut self, index: InstrIndex, stack: AbstractStack) {
        // Every stack this pass copies is copied on the way here — the worklist entry itself, and
        // the merge-point store that precedes it. Charging by cells rather than by step is what
        // makes the ceiling bound the work: one step can copy a whole stack.
        self.cells_copied = self.cells_copied.saturating_add(stack.len());
        self.retained += stack.len();
        self.worklist.push_back((index, stack));
    }

    /// The instruction after `index`, or `None` at the end of the program. Running off the end is
    /// the program stopping, exactly as the VM's step loop stops when its instruction pointer
    /// leaves the body.
    fn next_index(&self, index: usize) -> Option<usize> {
        (index + 1 < self.decoded.instrs.len()).then_some(index + 1)
    }

    /// The instruction a jump lands on, or `None` when it lands one past the last token — a jump
    /// off the end, which terminates.
    fn target_index(&self, target: Option<TokenIndex>) -> Result<Option<usize>, Stop> {
        let Some(target) = target else {
            return Err(Stop::Unanalyzable(UnanalyzableReason::BadJumpTarget));
        };
        if target == self.decoded.body_end {
            return Ok(None);
        }
        self.starts
            .binary_search(&target)
            .map(Some)
            .map_err(|_| Stop::Unanalyzable(UnanalyzableReason::BadJumpTarget))
    }

    fn propagate_next(&mut self, index: usize, stack: &AbstractStack) -> Result<(), Stop> {
        if let Some(next) = self.next_index(index) {
            self.propagate(InstrIndex(next), stack)?;
        }
        Ok(())
    }

    /// Continue at a jump target. A target that is neither an instruction boundary nor the end of
    /// the program fails closed: the VM would read an immediate as an opcode there.
    fn propagate_token(
        &mut self,
        target: Option<TokenIndex>,
        stack: &AbstractStack,
    ) -> Result<(), Stop> {
        match self.target_index(target)? {
            Some(index) => self.propagate(InstrIndex(index), stack),
            None => Ok(()),
        }
    }

    fn propagate(
        &mut self,
        InstrIndex(index): InstrIndex,
        stack: &AbstractStack,
    ) -> Result<(), Stop> {
        if self.retained > MAX_RETAINED_CELLS {
            return Err(Stop::Unanalyzable(UnanalyzableReason::StateBudget));
        }
        // A single-predecessor instruction has nothing to join against, so its stack goes straight
        // onto the worklist and is never stored. That is what keeps a long straight-line program —
        // the shape a large `IN` list compiles to — from retaining one stack per instruction.
        if !self.merge_points[index] {
            self.enqueue(InstrIndex(index), stack.clone());
            return Ok(());
        }
        match &self.entry[index] {
            None => {
                self.retained += stack.len();
                self.entry[index] = Some(stack.clone());
                self.enqueue(InstrIndex(index), stack.clone());
                Ok(())
            }
            Some(existing) => {
                // Two paths reaching one instruction with different stack depths means the model
                // has lost track of the layout, and every later `GET_GLOBAL` would pop the wrong
                // cells. There is no join that recovers from it, so the program fails closed.
                if existing.len() != stack.len() {
                    return Err(Stop::Unanalyzable(UnanalyzableReason::StackDepthMismatch));
                }
                let joined: AbstractStack = existing
                    .iter()
                    .zip(stack)
                    .map(|(left, right)| left.join(right))
                    .collect();
                if joined != *existing {
                    self.entry[index] = Some(joined.clone());
                    self.enqueue(InstrIndex(index), joined);
                }
                Ok(())
            }
        }
    }

    fn transfer(&mut self, index: usize, stack: &mut AbstractStack) -> Result<Control, Stop> {
        match &self.decoded.instrs[index].kind {
            InstrKind::String(literal) => {
                stack.push(AbstractValue::LiteralString(Arc::clone(literal)));
                Ok(Control::Fall)
            }
            InstrKind::Number(_) => push_opaque(stack),
            InstrKind::Counted(op, count) => self.counted(*op, *count, stack),
            // A native consumes stack values and cannot reach the globals dict, so it never widens
            // the read set — which is what keeps `toDateTime(timestamp) > x` projectable. The
            // exception is a native that reads a value's *spelling* rather than its value; see
            // [`REPRESENTATION_SENSITIVE_NATIVES`].
            InstrKind::CallGlobal { name, argc } => {
                if REPRESENTATION_SENSITIVE_NATIVES.contains(&name.as_str()) {
                    return Err(Stop::Unnarrowable(
                        FullColumnsReason::RepresentationSensitiveCall,
                    ));
                }
                reduce(stack, *argc)
            }
            InstrKind::Bare(op) => self.bare(*op, stack),
            InstrKind::Branch { op, target } => branch(*op, *target, stack),
            // A callable or closure introduces a frame the model has no notion of, and `TRY`
            // installs a handler that can enter one from anywhere. Refused on visit, so an
            // occurrence in code no path reaches costs nothing.
            InstrKind::Callable { .. } => Err(unsupported(Operation::Callable)),
            InstrKind::Closure => Err(unsupported(Operation::Closure)),
            InstrKind::Try => Err(unsupported(Operation::Try)),
        }
    }

    fn counted(
        &mut self,
        op: Operation,
        count: usize,
        stack: &mut AbstractStack,
    ) -> Result<Control, Stop> {
        match op {
            Operation::GetGlobal => self.get_global(count, stack),
            Operation::Dict => reduce(stack, count.saturating_mul(2)),
            // The compiler emits `AND n` / `OR n` rather than a jump-form short circuit, so these
            // stay plain reductions.
            Operation::And | Operation::Or | Operation::Array | Operation::Tuple => {
                reduce(stack, count)
            }
            // The frame base is zero: `CALLABLE`, `CLOSURE`, and `CALL_LOCAL` are all refused, so
            // no path reaching here has pushed a frame, and a slot offset indexes the stack
            // directly. That is what makes the `between` IIFE readable.
            Operation::GetLocal => {
                let value = stack
                    .get(count)
                    .ok_or(Stop::Unanalyzable(UnanalyzableReason::LocalSlotOutOfRange))?
                    .clone();
                stack.push(value);
                Ok(Control::Fall)
            }
            Operation::SetLocal => {
                let value = pop(stack)?;
                // The VM pops before it indexes, so a slot equal to the post-pop depth is out of
                // range there too.
                let slot = stack
                    .get_mut(count)
                    .ok_or(Stop::Unanalyzable(UnanalyzableReason::LocalSlotOutOfRange))?;
                *slot = value;
                Ok(Control::Fall)
            }
            // Upvalue slots address a closure's captured environment, which only the refused frame
            // opcodes create.
            Operation::GetUpvalue | Operation::SetUpvalue | Operation::CallLocal => {
                Err(unsupported(op))
            }
            // `decode` builds `Counted` only from the opcodes above.
            other => Err(unsupported(other)),
        }
    }

    fn bare(&mut self, op: Operation, stack: &mut AbstractStack) -> Result<Control, Stop> {
        match op {
            Operation::True | Operation::False | Operation::Null => push_opaque(stack),
            Operation::Not => reduce(stack, 1),
            Operation::Plus
            | Operation::Minus
            | Operation::Mult
            | Operation::Div
            | Operation::Mod
            | Operation::Eq
            | Operation::NotEq
            | Operation::Gt
            | Operation::GtEq
            | Operation::Lt
            | Operation::LtEq
            | Operation::Like
            | Operation::Ilike
            | Operation::NotLike
            | Operation::NotIlike
            | Operation::In
            | Operation::NotIn
            | Operation::Regex
            | Operation::NotRegex
            | Operation::Iregex
            | Operation::NotIregex
            | Operation::GetProperty
            | Operation::GetPropertyNullish => reduce(stack, 2),
            Operation::Pop => {
                pop(stack)?;
                Ok(Control::Fall)
            }
            Operation::Return => {
                pop(stack)?;
                // The root frame's `RETURN` leaves nothing behind: the compiler emits one
                // expression, and every scope pops its own locals first. Junk left here means a
                // stack effect in the transfer table is wrong, and the next `GET_GLOBAL` would pop
                // the wrong cells — so this turns a silent misread into a wide answer.
                if stack.is_empty() {
                    Ok(Control::Terminate)
                } else {
                    Err(Stop::Unanalyzable(UnanalyzableReason::UnbalancedReturn))
                }
            }
            // `SET_PROPERTY` mutates the heap, which the model does not represent; the cohort
            // opcodes read membership state that is not in the globals dict at all; the exception
            // opcodes move the instruction pointer to a handler this pass does not track.
            Operation::SetProperty
            | Operation::InCohort
            | Operation::NotInCohort
            | Operation::Throw
            | Operation::PopTry
            | Operation::CloseUpvalue
            | Operation::DeclareFn => Err(unsupported(op)),
            // `decode` builds `Bare` only from the opcodes above.
            other => Err(unsupported(other)),
        }
    }

    /// `GET_GLOBAL` pops its path root first, because the compiler pushes the chain reversed.
    fn get_global(&mut self, count: usize, stack: &mut AbstractStack) -> Result<Control, Stop> {
        if count == 0 {
            return Err(Stop::Unanalyzable(
                UnanalyzableReason::ZeroLengthGlobalChain,
            ));
        }
        // Checked before the allocation, not during the pops: `Vec::with_capacity` on an
        // out-of-range count aborts the process rather than returning.
        if count > stack.len() {
            return Err(Stop::Unanalyzable(UnanalyzableReason::StackUnderflow));
        }
        let mut chain = Vec::with_capacity(count);
        for _ in 0..count {
            match pop(stack)? {
                AbstractValue::LiteralString(segment) => chain.push(segment),
                AbstractValue::Opaque => {
                    return Err(Stop::Unanalyzable(UnanalyzableReason::DynamicGlobalPath))
                }
            }
        }
        let (root_name, segments) = chain.split_first().expect("count is non-zero");
        let Some(root) = GlobalRoot::parse(root_name) else {
            // A one-element chain also resolves to a first-class closure over a native, and
            // `arrayMap` invokes that closure through `CALL_LOCAL`, so the `CallGlobal` arm never
            // sees the name. Reading a number's spelling is unsafe however the native is reached,
            // so [`REPRESENTATION_SENSITIVE_NATIVES`] has to be checked on both paths.
            if segments.is_empty() && REPRESENTATION_SENSITIVE_NATIVES.contains(&root_name.as_ref())
            {
                return Err(Stop::Unnarrowable(
                    FullColumnsReason::RepresentationSensitiveCall,
                ));
            }
            // Every other such name reads no event data, so it constrains no column. A projection
            // narrows the values *under* the roots a globals builder writes and never removes a
            // root, so a name absent from the dict is absent under every projection: its
            // `GET_GLOBAL` raises `UnknownGlobal` on the projected event and on the full one alike.
            // [`GlobalRoot`] is what makes "not a root" mean "in no dict this crate builds".
            //
            // Opaque rather than terminate: the closure case keeps executing, so ending the path
            // here could prune a genuine later read. Over-approximating is the safe direction.
            return push_opaque(stack);
        };
        // A bare `properties`, `person`, or `pdi` hands a whole object to whatever consumes it, so
        // which keys are read is decided at runtime and cannot be narrowed here. `pdi` counts
        // because the globals build it as a copy of the whole person tree.
        if segments.is_empty() {
            match root {
                GlobalRoot::Properties => {
                    return Err(Stop::Unnarrowable(FullColumnsReason::BarePropertiesRoot))
                }
                GlobalRoot::Person | GlobalRoot::Pdi => {
                    return Err(Stop::Unnarrowable(FullColumnsReason::BarePersonRoot))
                }
                _ => {}
            }
        }
        // `elements_chain` reads the event column, then falls back to this property when the column
        // is empty. Both are real reads, so both are recorded or the claimed set would be short.
        if root == GlobalRoot::ElementsChain {
            self.reads.insert(ReadPath::new(
                GlobalRoot::Properties,
                vec![ELEMENTS_CHAIN_PROPERTY.to_owned()],
            ));
        }
        let segments = segments.iter().map(|segment| segment.to_string()).collect();
        self.reads.insert(ReadPath::new(root, segments));
        push_opaque(stack)
    }
}

fn branch(
    op: Operation,
    target: Option<TokenIndex>,
    stack: &mut AbstractStack,
) -> Result<Control, Stop> {
    match op {
        Operation::Jump => Ok(Control::Jump(target)),
        // The condition is popped before the branch is taken, so both edges continue from the same
        // stack.
        Operation::JumpIfFalse => {
            pop(stack)?;
            Ok(Control::Fork(target))
        }
        // This one peeks and never pops, on either edge. On an empty stack the VM cannot read a
        // top value, so it silently falls through — and modelling the jump anyway would merge two
        // paths at different depths and fail a program the VM runs fine.
        Operation::JumpIfStackNotNull => Ok(match stack.is_empty() {
            true => Control::Fall,
            false => Control::Fork(target),
        }),
        // `decode` builds `Branch` only from the opcodes above.
        other => Err(unsupported(other)),
    }
}

/// Consume `count` operands and leave one unnameable result.
fn reduce(stack: &mut AbstractStack, count: usize) -> Result<Control, Stop> {
    for _ in 0..count {
        pop(stack)?;
    }
    push_opaque(stack)
}

fn push_opaque(stack: &mut AbstractStack) -> Result<Control, Stop> {
    stack.push(AbstractValue::Opaque);
    Ok(Control::Fall)
}

fn pop(stack: &mut AbstractStack) -> Result<AbstractValue, Stop> {
    stack
        .pop()
        .ok_or(Stop::Unanalyzable(UnanalyzableReason::StackUnderflow))
}

fn unsupported(op: Operation) -> Stop {
    Stop::Unanalyzable(UnanalyzableReason::UnsupportedOp(op))
}

#[cfg(test)]
mod tests {
    use serde_json::json;

    use super::*;

    fn program(tokens: Vec<Value>) -> Vec<Value> {
        let mut bytecode = vec![json!("_H"), json!(1)];
        bytecode.extend(tokens);
        bytecode.push(json!(38));
        bytecode
    }

    /// A global read, written the way the compiler emits it: the path is pushed leaf first so that
    /// `GET_GLOBAL` pops the root first.
    fn read(path: &[&str]) -> Vec<Value> {
        let mut tokens = Vec::new();
        for segment in path.iter().rev() {
            tokens.push(json!(32));
            tokens.push(json!(segment));
        }
        tokens.push(json!(1));
        tokens.push(json!(path.len()));
        tokens
    }

    fn reads(tokens: Vec<Value>) -> Vec<String> {
        reads_of(&program(tokens))
    }

    fn reads_of(bytecode: &[Value]) -> Vec<String> {
        match project(bytecode, &mut AnalysisBudget::for_one_condition()) {
            Projection::Reads(paths) => paths.iter().map(ReadPath::render).collect(),
            other => panic!("expected reads, got {other:?}"),
        }
    }

    fn full_columns_reason(tokens: Vec<Value>) -> FullColumnsReason {
        match project(&program(tokens), &mut AnalysisBudget::for_one_condition()) {
            Projection::FullColumns(reason) => reason,
            other => panic!("expected full columns, got {other:?}"),
        }
    }

    fn unanalyzable_within(bytecode: &[Value], budget: &mut AnalysisBudget) -> UnanalyzableReason {
        match project(bytecode, budget) {
            Projection::FullColumns(FullColumnsReason::Unanalyzable(reason)) => reason,
            other => panic!("expected an unanalyzable reason, got {other:?}"),
        }
    }

    fn unanalyzable(tokens: Vec<Value>) -> UnanalyzableReason {
        match full_columns_reason(tokens) {
            FullColumnsReason::Unanalyzable(reason) => reason,
            other => panic!("expected an unanalyzable reason, got {other:?}"),
        }
    }

    /// The ordering test. The compiler pushes a chain reversed, so a reader that popped the leaf
    /// first would record `key.properties` and project a column that does not exist. Written out
    /// literally rather than through the helper, so the helper cannot hide the same mistake.
    #[test]
    fn a_global_chain_is_read_root_first_from_its_reversed_pushes() {
        let tokens = vec![
            json!(32),
            json!("key"),
            json!(32),
            json!("properties"),
            json!(1),
            json!(2),
        ];
        assert_eq!(reads(tokens), ["properties.key"]);
    }

    #[test]
    fn nested_paths_under_a_root_stay_precise() {
        assert_eq!(
            reads(read(&["person", "properties", "email"])),
            ["person.properties.email"]
        );
        assert_eq!(reads(read(&["event"])), ["event"]);
        assert_eq!(reads(read(&["pdi", "person_id"])), ["pdi.person_id"]);
        assert_eq!(
            reads(read(&["group_2", "properties", "tier"])),
            ["group_2.properties.tier"]
        );
    }

    /// Handing a whole `properties`, `person`, or `pdi` object to something decides its keys at
    /// runtime. These are ordinary programs, so they are reported as bare roots rather than as
    /// failures. `pdi` is a copy of the whole person tree, so a claimed read of it alone would look
    /// narrow while needing every person column.
    #[test]
    fn a_bare_object_root_widens_to_every_column() {
        assert_eq!(
            full_columns_reason(read(&["properties"])),
            FullColumnsReason::BarePropertiesRoot
        );
        assert_eq!(
            full_columns_reason(read(&["person"])),
            FullColumnsReason::BarePersonRoot
        );
        assert_eq!(
            full_columns_reason(read(&["pdi"])),
            FullColumnsReason::BarePersonRoot
        );
    }

    /// The shape a group-type-name filter compiles to. `organization` is a per-team group type: the
    /// SQL printer aliases it onto `group_0`, but the bytecode compiler emits the written chain
    /// verbatim, so the root reaches the VM and no globals dict carries it. Such a root reads no
    /// event data under any projection, so the program claims nothing.
    ///
    /// Written out literally rather than through the `read` helper, so the helper cannot hide the
    /// same mistake, for the same reason
    /// `a_global_chain_is_read_root_first_from_its_reversed_pushes` is written that way.
    #[test]
    fn a_root_no_globals_dict_carries_claims_no_reads() {
        // organization.properties.name == 'Example Org'
        let tokens = vec![
            json!(32),
            json!("Example Org"),
            json!(32),
            json!("name"),
            json!(32),
            json!("properties"),
            json!(32),
            json!("organization"),
            json!(1),
            json!(3),
            json!(11),
        ];
        assert_eq!(reads(tokens), Vec::<String>::new());
    }

    /// The absent root continues the walk rather than ending it, so a read after one is still
    /// claimed. A `Control::Terminate` implementation passes every other test in this file and
    /// fails only here.
    #[test]
    fn a_read_after_an_absent_root_is_still_claimed() {
        let mut tokens = read(&["organization"]);
        tokens.extend(read(&["properties", "plan"]));
        // `AND` of the two, so the program balances its stack the way the compiler would.
        tokens.push(json!(3));
        tokens.push(json!(2));
        assert_eq!(reads(tokens), ["properties.plan"]);
    }

    /// A bare native name is not a read. `GET_GLOBAL` resolves it to a first-class closure, and
    /// `arrayMap` invokes that closure through `CALL_LOCAL`, so the `CALL_GLOBAL` guard never sees
    /// the name. `typeof` answers from how a number was spelled, so a caller rebuilding the blob
    /// from the claimed keys re-prints `100.0` as `100` and the condition decides the other way.
    /// The root carries the same obligation a direct call does.
    #[test]
    fn a_representation_sensitive_native_reached_as_a_root_widens() {
        // arrayMap(typeof, [properties.n]) == ['float']
        let tokens = vec![
            json!(32),
            json!("typeof"),
            json!(1),
            json!(1),
            json!(32),
            json!("n"),
            json!(32),
            json!("properties"),
            json!(1),
            json!(2),
            json!(43),
            json!(1),
            json!(2),
            json!("arrayMap"),
            json!(2),
            json!(32),
            json!("float"),
            json!(43),
            json!(1),
            json!(11),
        ];
        assert_eq!(
            full_columns_reason(tokens),
            FullColumnsReason::RepresentationSensitiveCall
        );
    }

    /// A native the rebuild cannot disturb stays projectable when it arrives as a root, so the
    /// guard above widens on representation sensitivity rather than on every native reference.
    #[test]
    fn an_insensitive_native_reached_as_a_root_still_claims_its_reads() {
        // arrayMap(base64Encode, [properties.n])
        let tokens = vec![
            json!(32),
            json!("base64Encode"),
            json!(1),
            json!(1),
            json!(32),
            json!("n"),
            json!(32),
            json!("properties"),
            json!(1),
            json!(2),
            json!(43),
            json!(1),
            json!(2),
            json!("arrayMap"),
            json!(2),
        ];
        assert_eq!(reads(tokens), ["properties.n"]);
    }

    /// `elements_chain` resolves to the event column or, when that is empty, to
    /// `properties.$elements_chain`. A claimed read set that named only the column would be short,
    /// and a caller projecting from it would evaluate the condition against a null chain.
    #[test]
    fn an_elements_chain_read_also_claims_its_properties_fallback() {
        assert_eq!(
            reads(read(&["elements_chain"])),
            ["elements_chain", "properties.$elements_chain"]
        );
        // The sibling roots are constants in the globals, independent of the event, so they claim
        // nothing extra.
        assert_eq!(
            reads(read(&["elements_chain_texts"])),
            ["elements_chain_texts"]
        );
    }

    #[test]
    fn several_reads_under_one_program_are_collected_and_deduplicated() {
        let mut tokens = read(&["properties", "b"]);
        tokens.extend(read(&["properties", "a"]));
        tokens.extend(read(&["properties", "b"]));
        tokens.push(json!(3));
        tokens.push(json!(3));
        assert_eq!(reads(tokens), ["properties.a", "properties.b"]);
    }

    /// A path segment computed at runtime, an unmodeled opcode, and garbage all have to fail
    /// closed, each naming what stopped the analysis.
    #[test]
    fn unmodeled_programs_fail_closed_with_their_reason() {
        // `properties[someValue]`: the segment on the stack is not a literal.
        let dynamic = vec![
            json!(33),
            json!(3),
            json!(32),
            json!("properties"),
            json!(1),
            json!(2),
        ];
        assert_eq!(unanalyzable(dynamic), UnanalyzableReason::DynamicGlobalPath);
        assert_eq!(
            unanalyzable(vec![json!(1), json!(0)]),
            UnanalyzableReason::ZeroLengthGlobalChain
        );
        // A `TRY` installs a handler this pass does not follow.
        assert_eq!(
            unanalyzable(vec![json!(50), json!(1), json!(29)]),
            UnanalyzableReason::UnsupportedOp(Operation::Try)
        );
        assert_eq!(
            unanalyzable(vec![json!(11)]),
            UnanalyzableReason::StackUnderflow
        );
        assert!(matches!(
            unanalyzable(vec![json!(99)]),
            UnanalyzableReason::Decode(_)
        ));
    }

    /// The `if(cond, a, b)` shape the compiler emits for `null_safe_comparisons`. Both arms are
    /// visited, so a read reachable on either one is claimed. Refusing the branch — as the linear
    /// model did — reported every `>`/`>=`/`<`/`<=` condition as unreadable.
    #[test]
    fn both_arms_of_a_conditional_contribute_their_reads() {
        // if(<opaque>, properties.a, properties.b)
        let then = read(&["properties", "a"]);
        let otherwise = read(&["properties", "b"]);
        let mut tokens = vec![json!(29)];
        tokens.push(json!(40));
        tokens.push(json!(then.len() as i64 + 2));
        tokens.extend(then);
        tokens.push(json!(39));
        tokens.push(json!(otherwise.len() as i64));
        tokens.extend(otherwise);
        assert_eq!(reads(tokens), ["properties.a", "properties.b"]);
    }

    /// The `ifNull(expr, fallback)` shape, which wraps every regex comparison. The peek does not
    /// pop, and the fall-through arm's `POP` is what balances it, so the two paths meet at the
    /// same depth.
    #[test]
    fn an_ifnull_peek_and_its_pop_arm_meet_at_the_same_depth() {
        let mut tokens = read(&["properties", "url"]);
        // JUMP_IF_STACK_NOT_NULL over the POP and the FALSE that replaces the null.
        tokens.push(json!(47));
        tokens.push(json!(2));
        tokens.push(json!(35));
        tokens.push(json!(30));
        assert_eq!(reads(tokens), ["properties.url"]);
    }

    /// The `between` lowering: an IIFE that keeps its operands in local slots, reads them back with
    /// `GET_LOCAL`, merges two arms, and pops the locals on the way out. The whole shape has to
    /// stay readable, because a date range is one of the commonest cohort conditions.
    #[test]
    fn a_between_iife_over_local_slots_stays_readable() {
        // NULL (result slot), then the three operands into slots 1-3.
        let mut tokens = vec![json!(31)];
        tokens.extend(read(&["properties", "score"]));
        tokens.push(json!(33));
        tokens.push(json!(1));
        tokens.push(json!(33));
        tokens.push(json!(10));
        // low != null AND high != null AND expr != null
        for slot in [2, 3, 1] {
            tokens.push(json!(36));
            tokens.push(json!(slot));
            tokens.push(json!(31));
            tokens.push(json!(12));
        }
        tokens.push(json!(3));
        tokens.push(json!(3));
        // expr >= low AND expr <= high
        let between = vec![
            json!(36),
            json!(2),
            json!(36),
            json!(1),
            json!(14),
            json!(36),
            json!(3),
            json!(36),
            json!(1),
            json!(16),
            json!(3),
            json!(2),
        ];
        tokens.push(json!(40));
        tokens.push(json!(between.len() as i64 + 2));
        tokens.extend(between);
        tokens.push(json!(39));
        tokens.push(json!(1));
        tokens.push(json!(30));
        // Store into the result slot, then pop the three locals.
        tokens.push(json!(37));
        tokens.push(json!(0));
        tokens.extend([json!(35), json!(35), json!(35)]);
        assert_eq!(reads(tokens), ["properties.score"]);
    }

    /// A backward jump makes the worklist revisit instructions until the joined stacks stop
    /// changing. Without a fixpoint this would either loop forever or report a program the VM runs.
    #[test]
    fn a_backward_jump_converges_on_a_fixpoint() {
        // properties.a; loop: POP; properties.b; JUMP back to loop.
        let mut tokens = read(&["properties", "a"]);
        let loop_body_len: i64 = 1 + read(&["properties", "b"]).len() as i64;
        tokens.push(json!(35));
        tokens.extend(read(&["properties", "b"]));
        tokens.push(json!(39));
        tokens.push(json!(-(loop_body_len + 2)));
        assert_eq!(reads(tokens), ["properties.a", "properties.b"]);
    }

    /// Two paths that meet holding different stack depths mean the transfer table has lost the
    /// layout, and every later `GET_GLOBAL` would pop the wrong cells.
    #[test]
    fn paths_meeting_at_different_depths_fail_closed() {
        // TRUE; JUMP_IF_FALSE over one push; TRUE; (merge) — the taken edge arrives one shallower.
        let tokens = vec![json!(29), json!(40), json!(1), json!(29)];
        assert_eq!(unanalyzable(tokens), UnanalyzableReason::StackDepthMismatch);
    }

    /// A jump into the middle of an instruction would have the VM read an immediate as an opcode.
    /// Landing one past the last token is different: that is a jump off the end, and the program
    /// simply stops there.
    #[test]
    fn a_jump_off_a_boundary_fails_closed_but_a_jump_off_the_end_terminates() {
        // JUMP into the middle of the following STRING instruction.
        assert_eq!(
            unanalyzable(vec![json!(39), json!(1), json!(32), json!("x"), json!(35)]),
            UnanalyzableReason::BadJumpTarget
        );
        // JUMP past `program`'s trailing RETURN, which is one token past the end.
        assert_eq!(
            unanalyzable(vec![json!(39), json!(99)]),
            UnanalyzableReason::BadJumpTarget
        );
        // A read, then a jump that lands exactly on the end: the read still counts.
        let mut off_the_end = read(&["event"]);
        off_the_end.push(json!(35));
        off_the_end.push(json!(39));
        off_the_end.push(json!(1));
        assert_eq!(reads(off_the_end), ["event"]);
    }

    /// A local slot outside the frame is what the VM's own bounds check refuses, so the analysis
    /// must not silently read or write a cell that is not there.
    #[test]
    fn a_local_slot_outside_the_frame_fails_closed() {
        assert_eq!(
            unanalyzable(vec![json!(36), json!(3), json!(29)]),
            UnanalyzableReason::LocalSlotOutOfRange
        );
        assert_eq!(
            unanalyzable(vec![json!(29), json!(37), json!(4)]),
            UnanalyzableReason::LocalSlotOutOfRange
        );
    }

    /// A `RETURN` that leaves values behind means a stack effect in the transfer table is wrong.
    /// Reporting it turns a class of silent misreads into a wide, safe answer.
    #[test]
    fn a_return_over_an_unbalanced_stack_fails_closed() {
        assert_eq!(
            unanalyzable(vec![json!(29), json!(29)]),
            UnanalyzableReason::UnbalancedReturn
        );
    }

    /// The loader appends a `RETURN` to bytecode that may already end in one, so a repeated
    /// trailing `RETURN` is normal: the first one terminates every path, and the second is simply
    /// never reached.
    #[test]
    fn a_repeated_trailing_return_is_never_reached() {
        assert_eq!(reads(read(&["event"])), ["event"]);
    }

    /// A long straight-line program has no merge point, so the pass stores no per-instruction
    /// state at all.
    ///
    /// This is the shape a large `IN` list compiles to, and catalogs hold lists of several
    /// thousand. Storing one abstract stack per instruction across such a program is cells
    /// proportional to the square of its length: at the largest list size production is known to
    /// carry, that was over a gigabyte and seconds of blocking on the caller's task, for a program
    /// the VM itself evaluates in kilobytes.
    #[test]
    fn a_long_straight_line_program_costs_no_stored_state() {
        const ELEMENTS: usize = 2_000;
        let mut tokens = Vec::new();
        for index in 0..ELEMENTS {
            tokens.push(json!(32));
            tokens.push(json!(format!("v{index}")));
        }
        tokens.push(json!(44));
        tokens.push(json!(ELEMENTS));
        tokens.extend(read(&["properties", "plan"]));
        tokens.push(json!(21));

        let bytecode = program(tokens);
        let decoded = decode(&bytecode).expect("an IN list decodes");
        let starts: Vec<TokenIndex> = decoded.instrs.iter().map(|instr| instr.start).collect();
        assert!(
            !merge_points(&decoded, &starts).contains(&true),
            "an IN list has a merge point, so the pass would store one stack per instruction"
        );
        assert_eq!(reads_of(&bytecode), ["properties.plan"]);
    }

    /// A jump the decoder could not resolve is refused where it is visited, not where it is read.
    /// A dead one costs nothing, which is the same rule every other unmodeled construct follows.
    #[test]
    fn an_unresolvable_jump_fails_closed_only_when_a_path_reaches_it() {
        assert_eq!(
            unanalyzable(vec![json!(39), json!(-99)]),
            UnanalyzableReason::BadJumpTarget
        );
        // The same jump, behind an unconditional jump over it.
        let mut tokens = read(&["properties", "plan"]);
        tokens.push(json!(39));
        tokens.push(json!(2));
        tokens.push(json!(39));
        tokens.push(json!(-99));
        assert_eq!(reads(tokens), ["properties.plan"]);
    }

    /// Refusal happens when an instruction is visited, so an unmodeled opcode no path reaches costs
    /// nothing. Without that, one dead `CALLABLE` would widen an otherwise readable condition.
    #[test]
    fn an_unmodeled_opcode_no_path_reaches_is_harmless() {
        let mut tokens = read(&["properties", "plan"]);
        tokens.push(json!(39));
        // Jump over a CALLABLE with an empty body.
        tokens.push(json!(5));
        tokens.extend([json!(52), json!("f"), json!(0), json!(0), json!(0)]);
        assert_eq!(reads(tokens), ["properties.plan"]);
    }

    /// An ordinary native call is projection-safe, because it only consumes stack values. Refusing
    /// every native would make every `toDateTime(timestamp) > x` condition unprojectable.
    #[test]
    fn a_native_call_over_a_read_keeps_the_read_precise() {
        assert_eq!(reads(call_over_timestamp("toDateTime")), ["timestamp"]);
    }

    /// A native that reads a number's spelling is the one call the read set cannot describe: the
    /// paths are right, but supplying them from re-serialized JSON changes the answer. See
    /// [`REPRESENTATION_SENSITIVE_NATIVES`]. Reported as an understood program rather than as a
    /// failure, because nothing about it escaped the model.
    #[test]
    fn a_representation_sensitive_native_widens_to_every_column() {
        for name in REPRESENTATION_SENSITIVE_NATIVES {
            assert_eq!(
                full_columns_reason(call_over_timestamp(name)),
                FullColumnsReason::RepresentationSensitiveCall,
                "{name}"
            );
        }
    }

    /// The refusal is on the call, not on the read under it: a program that never calls one of
    /// these keeps its narrow answer however many other natives it uses.
    #[test]
    fn a_sensitive_native_name_only_matters_when_it_is_called() {
        assert_eq!(reads(call_over_timestamp("toTypeOf")), ["timestamp"]);
        assert_eq!(
            reads(read(&["properties", "typeof"])),
            ["properties.typeof"]
        );
    }

    /// `name(timestamp) > '2026-01-01'`.
    fn call_over_timestamp(name: &str) -> Vec<Value> {
        let mut tokens = read(&["timestamp"]);
        tokens.push(json!(2));
        tokens.push(json!(name));
        tokens.push(json!(1));
        tokens.push(json!(32));
        tokens.push(json!("2026-01-01"));
        tokens.push(json!(13));
        tokens
    }

    /// A hostile count immediate must not reach an allocation. `u64::MAX` is a capacity-overflow
    /// panic and a merely huge value is an allocation abort; either would take down the caller's
    /// task, which the fail-closed contract cannot absorb.
    ///
    /// The refusal also names the opcode it stopped on. A decode failure is the reason a census
    /// cannot diagnose from the coarse label alone, because it is what a decoder drifting from
    /// `vm.rs` looks like, and the opcode is the field that says which table entry drifted.
    #[test]
    fn a_hostile_global_chain_count_never_allocates() {
        for count in [json!(u64::MAX), json!(4_000_000_000u64)] {
            let reason = unanalyzable(vec![json!(1), count.clone()]);
            assert!(matches!(reason, UnanalyzableReason::Decode(_)));
            assert_eq!(reason.op(), Some(Operation::GetGlobal));
        }
        // A count the decoder accepts, still deeper than the stack.
        let padded = std::iter::repeat_n(json!(29), 8)
            .chain([json!(1), json!(6)])
            .collect::<Vec<_>>();
        assert_eq!(
            unanalyzable(padded),
            UnanalyzableReason::DynamicGlobalPath,
            "eight opaque pushes are enough for a six-deep chain, so this is not an underflow"
        );
        let shallow = vec![json!(29), json!(29), json!(1), json!(6)];
        assert_eq!(unanalyzable(shallow), UnanalyzableReason::StackUnderflow);
    }

    /// Both ceilings, on programs small enough to reach them at unit cost rather than at a million
    /// steps. They are guards rather than dead code, so the risk they carry is not an unreachable
    /// branch — it is a guard that is wrong and nothing that says so.
    ///
    /// The step ceiling is reached through the loop here rather than through the spent-budget
    /// shortcut, which the next test covers.
    #[test]
    fn each_ceiling_fails_closed_under_its_own_reason() {
        // STRING, STRING, GET_GLOBAL, RETURN.
        let straight_line = program(read(&["properties", "plan"]));
        assert_eq!(
            unanalyzable_within(
                &straight_line,
                &mut AnalysisBudget {
                    steps: 1,
                    cells: usize::MAX
                }
            ),
            UnanalyzableReason::IterationBudget
        );

        // A fork whose two edges both land on the POP, so the pass copies its one-deep stack onto
        // the worklist rather than walking it in place. Without a copy there is no cell to charge.
        let forked = program(vec![
            json!(32),
            json!("x"),
            json!(29),
            json!(40),
            json!(0),
            json!(35),
            json!(29),
        ]);
        assert_eq!(
            reads_of(&forked),
            Vec::<String>::new(),
            "the fork analyzes cleanly when the budget allows it"
        );
        assert_eq!(
            unanalyzable_within(
                &forked,
                &mut AnalysisBudget {
                    steps: usize::MAX,
                    cells: 0
                }
            ),
            UnanalyzableReason::StateBudget
        );
    }

    /// One budget across several conditions is what bounds a batch rather than each member of it.
    /// The spend has to be real: a budget that reset per condition would leave `conditions ×
    /// ceiling`, which is the shape this exists to refuse.
    #[test]
    fn a_shared_budget_is_spent_down_and_then_refuses() {
        // STRING, STRING, GET_GLOBAL, RETURN: four transfer steps, exactly.
        let bytecode = program(read(&["properties", "plan"]));
        let mut budget = AnalysisBudget {
            steps: 4,
            cells: usize::MAX,
        };
        assert!(matches!(
            project(&bytecode, &mut budget),
            Projection::Reads(_)
        ));
        assert_eq!(budget.steps, 0);
        // The next condition is refused before it is even decoded.
        assert_eq!(
            unanalyzable_within(&bytecode, &mut budget),
            UnanalyzableReason::IterationBudget
        );
    }

    /// A deep stack, then diamonds whose two arms write different literals into one local slot, so
    /// every rejoin widens a cell and re-enqueues a full-depth stack.
    fn widening_diamonds(depth: usize, count: usize) -> Vec<Value> {
        let mut tokens = Vec::new();
        for index in 0..depth {
            tokens.push(json!(32));
            tokens.push(json!(format!("v{index}")));
        }
        for index in 0..count {
            let slot = index % depth;
            // TRUE; JUMP_IF_FALSE over the first arm.
            tokens.extend([json!(29), json!(40), json!(6)]);
            // STRING "a"; SET_LOCAL slot; JUMP over the second arm.
            tokens.extend([
                json!(32),
                json!("a"),
                json!(37),
                json!(slot),
                json!(39),
                json!(4),
            ]);
            // STRING "b"; SET_LOCAL slot.
            tokens.extend([json!(32), json!("b"), json!(37), json!(slot)]);
        }
        for _ in 0..depth {
            tokens.push(json!(35));
        }
        tokens.push(json!(31));
        tokens
    }

    /// The shape merge-point gating does not answer: a program that is *all* merge points.
    ///
    /// Its cost is the copying, and neither of the other two ceilings sees it. Steps do not, because
    /// one step copies a whole stack. The memory ceiling does not either, because each copy is
    /// popped again, so the pass holds a fraction of what it has copied. At the sizes a catalog row
    /// can carry this ran for over a second on the caller's task before the copied-cell ceiling
    /// existed.
    #[test]
    fn a_program_that_is_all_merge_points_is_charged_by_the_cells_it_copies() {
        let bytecode = program(widening_diamonds(40, 40));
        let decoded = decode(&bytecode).expect("the shape decodes");
        let mut interpreter = Interpreter::new(&decoded, AnalysisBudget::for_one_condition());
        interpreter
            .run()
            .unwrap_or_else(|_| panic!("the shape analyzes cleanly under a whole budget"));
        assert!(
            interpreter.cells_copied > interpreter.steps * 5,
            "{} steps against {} copied cells, so the step ceiling bounds this shape after all",
            interpreter.steps,
            interpreter.cells_copied
        );
        assert!(
            interpreter.retained < MAX_RETAINED_CELLS / 10,
            "{} cells held at the end, so the memory ceiling is what bounds this shape",
            interpreter.retained
        );

        assert_eq!(
            unanalyzable_within(
                &bytecode,
                &mut AnalysisBudget {
                    steps: usize::MAX,
                    cells: 1_000
                }
            ),
            UnanalyzableReason::StateBudget
        );
    }
}