: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.
Python ab-testingai-analyticsanalyticscdpdata-warehouseexperimentsfeature-flagsjavascriptproduct-analyticspythonreactsession-replaysurveystypescriptweb-analytics
//! Static analysis of a pinned condition's HogVM bytecode: which event globals it reads, and
//! whether it is nothing more than an event-name equality. Depends on `hogvm::Operation` only.
//!
//! Cohort policy stays out of the shared `common/hogvm` crate, the same way [`super::executor`]
//! layers evaluation on top of the VM's primitives rather than changing them.
//!
//! # Fail closed
//!
//! Every unmodeled input becomes [`Projection::FullColumns`], which means "read everything". A
//! caller acting on the result is then slower than it could be, never wrong. That is why
//! [`analyze_condition`] is total: it returns no error and never panics, because the alternative
//! (treating an analysis failure as "reads nothing") would silently drop rows from a scan.
//!
//! One input is answered rather than widened: a `GET_GLOBAL` root outside [`GlobalRoot`] claims no
//! read. That is not an exception to the rule above, but a consequence of the section below — such
//! a root reads no event data at all. A root naming a representation-sensitive native still widens,
//! because it resolves to a closure the program can call.
//!
//! # Why the read set can be trusted
//!
//! `GET_GLOBAL` is the VM's only path into the globals dict, and it takes its path from literal
//! strings the compiler pushed. Every other opcode consumes values already on the stack. So a
//! program whose `GET_GLOBAL`s all resolve to literal paths cannot reach a global this analysis did
//! not record, however it combines those values afterwards.
//!
//! A path whose root is outside [`GlobalRoot`] records nothing. A name no globals dict carries is
//! absent from the narrowed event and from the full one alike, so it names no column and no root.
//! That rests on [`GlobalRoot`] covering every dict this crate builds, which
//! `every_globals_dict_key_is_a_named_root` in `hogvm::globals` checks.
//!
//! The two consumers narrow differently and [`Projection::Reads`] serves both: the seeder narrows
//! the values under a root and keeps the root, while [`GlobalsPlan`] removes whole roots. So a read
//! set is sound for both only because every path records its root as well as its segments.
//!
//! Reading no event data is only half the obligation. A bare native name resolves to a closure
//! instead of a read, so such a root widens whenever calling it would read a value's spelling
//! rather than its value, the same way a direct call to it does.
mod decode;
mod event_only;
mod exactness;
mod plan;
mod projection;
mod row_filter;
use std::collections::BTreeSet;
use hogvm::Operation;
use serde_json::Value;
pub use decode::DecodeError;
pub use exactness::{ColumnExactness, Exactness};
pub use plan::{GlobalsBuild, GlobalsPlan};
pub use projection::AnalysisBudget;
pub use row_filter::{event_equalities, EventEqualities, EventRowFilter, PropertyAlternatives};
/// What a static pass could establish about one condition's bytecode.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ConditionAnalysis {
pub evaluation: EvaluationClass,
pub projection: Projection,
}
/// How much of the VM a condition actually needs.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum EvaluationClass {
/// The whole program is `event == <name>`. Such a condition is decided by the event name a
/// scan already filters on, so it needs no per-row evaluation at all.
EventOnly { event: String },
/// Anything else.
General,
}
/// The globals a condition reads, when they can be named.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum Projection {
/// Exactly these paths, and nothing else. Empty means the program reads no globals.
///
/// A path names a subtree, not a leaf: `person.properties` claims everything under it, because
/// the program may hand that object to a function that indexes it at runtime. A caller
/// building a projection has to supply the whole subtree each path names. The analysis never
/// returns a bare object root here — [`FullColumnsReason::BarePropertiesRoot`] and
/// [`FullColumnsReason::BarePersonRoot`] carry those — so a `Reads` path is always at least one
/// key deep under `properties`, `person`, or `pdi`.
Reads(BTreeSet<ReadPath>),
/// The read set could not be narrowed, so a caller must supply every column.
FullColumns(FullColumnsReason),
}
/// Why a condition fell back to every column. Every case but [`FullColumnsReason::Unanalyzable`] is
/// an ordinary program the analysis understood and still cannot narrow; that one is the fail-closed
/// arm, where the model lost track of the program.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum FullColumnsReason {
/// The program passes the whole `properties` dict somewhere, for example to a function.
BarePropertiesRoot,
/// The program passes the whole `person` object somewhere.
BarePersonRoot,
/// The program calls a native that reads how a number was spelled rather than what it is, so a
/// caller supplying the claimed paths from re-serialized JSON would change the answer. The read
/// set itself is exact; what cannot be narrowed is how it may be supplied.
RepresentationSensitiveCall,
Unanalyzable(UnanalyzableReason),
}
impl FullColumnsReason {
/// A closed, bounded label. Safe as a metric dimension: it never carries program text.
pub fn as_str(&self) -> &'static str {
match self {
Self::BarePropertiesRoot => "bare_properties_root",
Self::BarePersonRoot => "bare_person_root",
Self::RepresentationSensitiveCall => "representation_sensitive_call",
Self::Unanalyzable(reason) => reason.as_str(),
}
}
/// Which opcode stopped the analysis, when one did. See [`UnanalyzableReason::op`].
pub fn op(&self) -> Option<Operation> {
match self {
Self::Unanalyzable(reason) => reason.op(),
Self::RepresentationSensitiveCall => Some(Operation::CallGlobal),
Self::BarePropertiesRoot | Self::BarePersonRoot => None,
}
}
}
/// Why a program escaped the abstract model. Each variant is a closed metric label, so this
/// vocabulary is what a census reports on.
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum UnanalyzableReason {
Decode(DecodeError),
/// An opcode whose effect the model does not reproduce: a frame, a heap write, or an exception
/// handler.
UnsupportedOp(Operation),
/// A `GET_GLOBAL` path segment that is not a compile-time literal.
DynamicGlobalPath,
StackUnderflow,
/// `GET_GLOBAL 0`, which the VM itself rejects.
ZeroLengthGlobalChain,
/// Two paths reached one instruction holding stacks of different depths, so the model has lost
/// the layout every later `GET_GLOBAL` depends on.
StackDepthMismatch,
/// A jump landing inside an instruction rather than on one, which the VM would read as an
/// opcode where an immediate is.
BadJumpTarget,
/// The worklist ran past its step ceiling, so the fixpoint argument does not hold for this
/// program. Never expected on its own; it exists so an unforeseen shape is a wide answer, not a
/// hang. Also how a condition reports a shared [`AnalysisBudget`] its siblings already spent.
IterationBudget,
/// The pass would have had to hold or copy more abstract stack state than its ceiling allows.
/// Bounds the memory and the copying a condition can cost, whatever its branching shape, and
/// reports a shared [`AnalysisBudget`] spent down to its cell half.
StateBudget,
/// A local slot outside the current frame, which the VM's own bounds check refuses.
LocalSlotOutOfRange,
/// A `RETURN` that left values on the stack, meaning a stack effect in the transfer table is
/// wrong.
UnbalancedReturn,
}
impl UnanalyzableReason {
/// A closed, bounded label. The payloads (an opcode, a decode position) stay out of it, so it
/// is safe as a metric dimension however hostile the bytecode is. Use [`Self::op`] for the one
/// payload that is itself bounded.
pub fn as_str(&self) -> &'static str {
match self {
Self::Decode(_) => "decode",
Self::UnsupportedOp(_) => "unsupported_op",
Self::DynamicGlobalPath => "dynamic_global_path",
Self::StackUnderflow => "stack_underflow",
Self::ZeroLengthGlobalChain => "zero_length_global_chain",
Self::StackDepthMismatch => "stack_depth_mismatch",
Self::BadJumpTarget => "bad_jump_target",
Self::IterationBudget => "iteration_budget",
Self::StateBudget => "state_budget",
Self::LocalSlotOutOfRange => "local_slot_out_of_range",
Self::UnbalancedReturn => "unbalanced_return",
}
}
/// Which opcode stopped the analysis, when one did.
///
/// [`Operation`] is a closed 57-variant enum, so this is as bounded as [`Self::as_str`] and
/// safe as a second metric dimension. It is worth carrying because "unsupported_op" alone
/// cannot tell one fixable compiler template apart from a genuinely unreadable program.
///
/// A decode failure names its opcode too, and that is the case the label earns the most: a
/// decoder whose immediate table drifts from `vm.rs` fails on the opcode that drifted.
/// Exhaustive rather than defaulted, so a new variant has to decide.
pub fn op(&self) -> Option<Operation> {
match self {
Self::Decode(error) => error.op(),
Self::UnsupportedOp(op) => Some(*op),
Self::DynamicGlobalPath
| Self::StackUnderflow
| Self::ZeroLengthGlobalChain
| Self::StackDepthMismatch
| Self::BadJumpTarget
| Self::IterationBudget
| Self::StateBudget
| Self::LocalSlotOutOfRange
| Self::UnbalancedReturn => None,
}
}
}
/// One global the program reads, as a root plus the keys taken under it. `Ord` so a
/// [`BTreeSet`] of these has a stable order, which keeps a census reproducible.
#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
pub struct ReadPath {
pub root: GlobalRoot,
pub segments: Vec<String>,
}
impl ReadPath {
pub fn new(root: GlobalRoot, segments: Vec<String>) -> Self {
Self { root, segments }
}
/// The dotted rendering, for logs and census output.
pub fn render(&self) -> String {
let mut rendered = self.root.as_str().to_owned();
for segment in &self.segments {
rendered.push('.');
rendered.push_str(segment);
}
rendered
}
}
/// A group ordinal, which the behavioral globals define for 0 through 4.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct GroupIndex(u8);
impl GroupIndex {
pub const COUNT: u8 = 5;
pub fn parse(index: u8) -> Option<Self> {
(index < Self::COUNT).then_some(Self(index))
}
pub const fn get(self) -> u8 {
self.0
}
pub fn all() -> impl Iterator<Item = Self> {
(0..Self::COUNT).map(Self)
}
}
/// Every root of every globals dict this crate builds, which is the whole surface a condition can
/// read.
///
/// The list is load-bearing in one direction. A name outside it claims no read, so a key added to a
/// globals dict without a variant here would be pruned from a scan while the program still reads
/// it. `every_globals_dict_key_is_a_named_root` in `hogvm::globals` is what earns that: it walks
/// the dicts themselves rather than a list, so it fails as soon as one gains a key.
///
/// The other direction is benign. A variant no dict carries over-claims a read, which costs bytes
/// and never correctness, so nothing here has to chase it.
#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub enum GlobalRoot {
Event,
Uuid,
ElementsChain,
ElementsChainHref,
ElementsChainTexts,
ElementsChainIds,
ElementsChainElements,
Timestamp,
Properties,
Person,
Pdi,
DistinctId,
DollarGroup(GroupIndex),
Group(GroupIndex),
Variables,
/// Only in the person-scope dict, never in the behavioral one. Named here so that "not a
/// [`GlobalRoot`]" means "in no globals dict this crate builds" rather than "in the behavioral
/// one".
Project,
}
impl GlobalRoot {
/// Resolve a literal root name. `None` means no globals dict this crate builds carries the
/// name — which the analysis reads as "this path touches no event data", so the scope of the
/// `None` is what makes that sound.
pub fn parse(name: &str) -> Option<Self> {
match name {
"event" => Some(Self::Event),
"uuid" => Some(Self::Uuid),
"elements_chain" => Some(Self::ElementsChain),
"elements_chain_href" => Some(Self::ElementsChainHref),
"elements_chain_texts" => Some(Self::ElementsChainTexts),
"elements_chain_ids" => Some(Self::ElementsChainIds),
"elements_chain_elements" => Some(Self::ElementsChainElements),
"timestamp" => Some(Self::Timestamp),
"properties" => Some(Self::Properties),
"person" => Some(Self::Person),
"pdi" => Some(Self::Pdi),
"distinct_id" => Some(Self::DistinctId),
"variables" => Some(Self::Variables),
"project" => Some(Self::Project),
_ => name
.strip_prefix("$group_")
.and_then(group_index)
.map(Self::DollarGroup)
.or_else(|| {
name.strip_prefix("group_")
.and_then(group_index)
.map(Self::Group)
}),
}
}
pub const COUNT: u8 = FIRST_GROUP_ORDINAL + 2 * GroupIndex::COUNT;
/// A dense index into `0..COUNT`, never persisted, that [`GlobalRoot::from_ordinal`] inverts.
pub fn ordinal(self) -> u8 {
match self {
Self::Event => 0,
Self::Uuid => 1,
Self::ElementsChain => 2,
Self::ElementsChainHref => 3,
Self::ElementsChainTexts => 4,
Self::ElementsChainIds => 5,
Self::ElementsChainElements => 6,
Self::Timestamp => 7,
Self::Properties => 8,
Self::Person => 9,
Self::Pdi => 10,
Self::DistinctId => 11,
Self::Variables => 12,
Self::Project => 13,
Self::DollarGroup(index) => FIRST_GROUP_ORDINAL + index.get(),
Self::Group(index) => FIRST_GROUP_ORDINAL + GroupIndex::COUNT + index.get(),
}
}
/// Every root, in ordinal order.
pub fn all() -> impl Iterator<Item = Self> {
(0..Self::COUNT).filter_map(Self::from_ordinal)
}
pub fn from_ordinal(ordinal: u8) -> Option<Self> {
let root = match ordinal {
0 => Self::Event,
1 => Self::Uuid,
2 => Self::ElementsChain,
3 => Self::ElementsChainHref,
4 => Self::ElementsChainTexts,
5 => Self::ElementsChainIds,
6 => Self::ElementsChainElements,
7 => Self::Timestamp,
8 => Self::Properties,
9 => Self::Person,
10 => Self::Pdi,
11 => Self::DistinctId,
12 => Self::Variables,
13 => Self::Project,
_ => {
let group = ordinal - FIRST_GROUP_ORDINAL;
return match GroupIndex::parse(group) {
Some(index) => Some(Self::DollarGroup(index)),
None => {
GroupIndex::parse(group.wrapping_sub(GroupIndex::COUNT)).map(Self::Group)
}
};
}
};
Some(root)
}
pub fn as_str(&self) -> &'static str {
match self {
Self::Event => "event",
Self::Uuid => "uuid",
Self::ElementsChain => "elements_chain",
Self::ElementsChainHref => "elements_chain_href",
Self::ElementsChainTexts => "elements_chain_texts",
Self::ElementsChainIds => "elements_chain_ids",
Self::ElementsChainElements => "elements_chain_elements",
Self::Timestamp => "timestamp",
Self::Properties => "properties",
Self::Person => "person",
Self::Pdi => "pdi",
Self::DistinctId => "distinct_id",
Self::DollarGroup(index) => DOLLAR_GROUP_NAMES[index.get() as usize],
Self::Group(index) => GROUP_NAMES[index.get() as usize],
Self::Variables => "variables",
Self::Project => "project",
}
}
}
const FIRST_GROUP_ORDINAL: u8 = 14;
const DOLLAR_GROUP_NAMES: [&str; GroupIndex::COUNT as usize] =
["$group_0", "$group_1", "$group_2", "$group_3", "$group_4"];
const GROUP_NAMES: [&str; GroupIndex::COUNT as usize] =
["group_0", "group_1", "group_2", "group_3", "group_4"];
/// A single-digit group ordinal, rejecting `group_00` and `group_10` alike.
fn group_index(suffix: &str) -> Option<GroupIndex> {
let [digit] = suffix.as_bytes() else {
return None;
};
GroupIndex::parse(digit.checked_sub(b'0')?)
}
/// Analyze one condition's loaded bytecode, under a budget of its own.
///
/// Total: it returns no error and never panics. Anything the model does not cover becomes
/// [`Projection::FullColumns`] carrying the reason, because a wrong narrow answer would drop rows
/// from a scan while a wide one only costs time.
pub fn analyze_condition(bytecode: &[Value]) -> ConditionAnalysis {
analyze_condition_within(bytecode, &mut AnalysisBudget::for_one_condition())
}
/// Analyze one condition against a budget its siblings share.
///
/// A caller with many conditions wants the batch bounded, not each member of it: the per-condition
/// ceilings leave `conditions × ceiling`, which is unbounded wherever nothing caps the conditions.
/// Spending one budget in a fixed order keeps that bounded and keeps the analysis a pure function
/// of its input, so the same batch always classifies the same way.
pub fn analyze_condition_within(
bytecode: &[Value],
budget: &mut AnalysisBudget,
) -> ConditionAnalysis {
ConditionAnalysis {
evaluation: event_only::classify(bytecode),
projection: projection::project(bytecode, budget),
}
}
#[cfg(test)]
mod tests {
use serde_json::json;
use super::*;
/// The assumption the read set rests on, checked against the VM's own standard library.
///
/// A `CALL_GLOBAL` to a hog-implemented standard-library function is not a native call: the VM
/// pushes a frame and runs that function's body against the *same* globals dict. The abstract
/// interpreter does not follow the callee, so if any of those bodies read a global, a condition
/// calling it would read a global this analysis never recorded, and a projection built from the
/// claimed set would evaluate it against a truncated event.
///
/// Today no standard-library body contains a `GET_GLOBAL`; they work purely on their arguments.
/// This fails if one ever does, which is the moment `CALL_GLOBAL` would stop being safe to treat
/// as a plain stack reduction.
///
/// A body may itself define a lambda, whose tokens `decode` steps over rather than into —
/// `sortableSemver` already does. Those tokens are still code the VM runs against the same
/// globals dict, so the scan follows every nested `CALLABLE` body too. Without that, the check
/// would pass on exactly the shape it exists to catch.
#[test]
fn no_standard_library_function_body_reads_a_global() {
let module = hogvm::hog_stl();
let functions = module.functions();
assert!(
!functions.is_empty(),
"the standard library is empty, so this check would pass vacuously"
);
let mut nested_bodies_seen = 0;
for (name, function) in functions {
// The bodies are raw instruction lists, so give them the header the decoder expects.
let mut body = vec![json!("_H"), json!(1)];
let mut index = 0;
while let Some(token) = function.get(index) {
body.push(token.clone());
index += 1;
}
let decoded = decode::decode(&body).unwrap_or_else(|error| {
panic!("standard library function {name} did not decode: {error}")
});
let mut pending = vec![decoded];
while let Some(decoded) = pending.pop() {
for instr in &decoded.instrs {
assert!(
!matches!(
instr.kind,
decode::InstrKind::Counted(Operation::GetGlobal, _)
),
"standard library function {name} reads a global, so a condition calling \
it would read globals this analysis does not record"
);
if let decode::InstrKind::Callable { body: span } = instr.kind {
nested_bodies_seen += 1;
pending.push(decode::decode_span(&body, span).unwrap_or_else(|error| {
panic!("a lambda body in {name} did not decode: {error}")
}));
}
}
}
}
assert!(
nested_bodies_seen > 0,
"no standard library function defines a lambda, so the recursion is untested"
);
}
/// The compiler forces a new variant to take an ordinal, but not to update
/// [`GlobalRoot::COUNT`], and a stale one leaves `GlobalsPlan::FULL` short of a root.
#[test]
fn every_global_root_round_trips_through_its_name_and_ordinal() {
let by_ordinal: Vec<GlobalRoot> = (0..GlobalRoot::COUNT)
.map(|ordinal| {
GlobalRoot::from_ordinal(ordinal).unwrap_or_else(|| {
panic!("ordinal {ordinal} is below COUNT and resolved to no root")
})
})
.collect();
assert_eq!(
by_ordinal.iter().collect::<BTreeSet<_>>().len(),
GlobalRoot::COUNT as usize,
"two roots share an ordinal, so a bitset over them would conflate them",
);
assert_eq!(
GlobalRoot::from_ordinal(GlobalRoot::COUNT),
None,
"COUNT is not past the last ordinal, so `GlobalsPlan::FULL` would be short a root",
);
for root in &by_ordinal {
assert_eq!(GlobalRoot::from_ordinal(root.ordinal()), Some(*root));
}
let roots = [
GlobalRoot::Event,
GlobalRoot::Uuid,
GlobalRoot::ElementsChain,
GlobalRoot::ElementsChainHref,
GlobalRoot::ElementsChainTexts,
GlobalRoot::ElementsChainIds,
GlobalRoot::ElementsChainElements,
GlobalRoot::Timestamp,
GlobalRoot::Properties,
GlobalRoot::Person,
GlobalRoot::Pdi,
GlobalRoot::DistinctId,
GlobalRoot::Variables,
GlobalRoot::Project,
];
for root in roots {
assert_eq!(GlobalRoot::parse(root.as_str()), Some(root));
}
for index in 0..GroupIndex::COUNT {
let index = GroupIndex::parse(index).unwrap();
for root in [GlobalRoot::DollarGroup(index), GlobalRoot::Group(index)] {
assert_eq!(GlobalRoot::parse(root.as_str()), Some(root));
}
}
}
/// A name close to a real root must not resolve to one. Accepting `group_9` would let the
/// analysis claim a read of a global the event does not carry.
#[test]
fn near_miss_root_names_do_not_resolve() {
for name in [
"group_5",
"group_9",
"group_00",
"group_10",
"group_",
"$group_5",
"$group_",
"Event",
"properties2",
"",
"person.properties",
] {
assert_eq!(GlobalRoot::parse(name), None, "{name} resolved to a root");
}
}
#[test]
fn read_paths_render_dotted_and_sort_by_root_then_segments() {
let path = ReadPath::new(
GlobalRoot::Person,
vec!["properties".to_owned(), "email".to_owned()],
);
assert_eq!(path.render(), "person.properties.email");
assert_eq!(
ReadPath::new(GlobalRoot::Event, Vec::new()).render(),
"event"
);
let mut set = BTreeSet::new();
set.insert(ReadPath::new(GlobalRoot::Properties, vec!["b".to_owned()]));
set.insert(ReadPath::new(GlobalRoot::Event, Vec::new()));
set.insert(ReadPath::new(GlobalRoot::Properties, vec!["a".to_owned()]));
assert_eq!(
set.iter().map(ReadPath::render).collect::<Vec<_>>(),
["event", "properties.a", "properties.b"]
);
}
}