use crate::fixed_point_execution_plan::{plan_prepared_graph, FixedPointExecutionPlan};
use crate::fixed_point_graph::{FixedPointAnalysisKind, FixedPointForwardGraph};
use crate::fixed_point_scratch::{FrontierDensityTelemetry, FrontierExecutionMode};
use crate::resident_cache_lru::ResidentCacheLru;
use std::collections::HashMap;
#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
pub struct FixedPointExecutionPlanCacheStats {
pub hits: u64,
pub misses: u64,
pub evictions: u64,
pub entries: usize,
}
#[derive(Clone, Debug, PartialEq)]
pub struct FixedPointExecutionPlanCache {
entries: HashMap<FixedPointExecutionPlanCacheKey, FixedPointExecutionPlanCacheEntry>,
lru: ResidentCacheLru<FixedPointExecutionPlanCacheKey>,
max_entries: usize,
clock: u64,
hits: u64,
misses: u64,
evictions: u64,
}
#[derive(Clone, Debug, Eq, Hash, PartialEq)]
struct FixedPointExecutionPlanCacheKey {
backend_id: &'static str,
backend_version: &'static str,
supported_ops_fingerprint: u64,
kind: FixedPointAnalysisKind,
layout_hash: u64,
node_count: u32,
edge_count: u32,
density_mode: FrontierExecutionMode,
}
#[derive(Clone, Debug, PartialEq)]
struct FixedPointExecutionPlanCacheEntry {
last_seen: u64,
plan: FixedPointExecutionPlan,
}
impl Default for FixedPointExecutionPlanCache {
fn default() -> Self {
Self {
entries: HashMap::new(),
lru: ResidentCacheLru::default(),
max_entries: 1024,
clock: 0,
hits: 0,
misses: 0,
evictions: 0,
}
}
}
impl FixedPointExecutionPlanCache {
#[must_use]
pub fn new() -> Self {
Self::default()
}
#[must_use]
pub fn with_max_entries(max_entries: usize) -> Self {
Self {
max_entries: max_entries.max(1),
..Self::default()
}
}
pub fn get_or_plan(
&mut self,
backend: &dyn vyre::VyreBackend,
kind: FixedPointAnalysisKind,
graph: &FixedPointForwardGraph,
frontier_density: FrontierDensityTelemetry,
) -> Result<FixedPointExecutionPlan, String> {
graph.require_kind(kind, "FixedPointExecutionPlanCache::get_or_plan")?;
let supported_ops_fingerprint = self.backend_supported_ops_fingerprint(backend)?;
let key = FixedPointExecutionPlanCacheKey {
backend_id: backend.id(),
backend_version: backend.version(),
supported_ops_fingerprint,
kind,
layout_hash: graph.stable_layout_hash(),
node_count: graph.node_count(),
edge_count: graph.edge_count(),
density_mode: frontier_density.recommended_execution_mode(),
};
if let Some(entry) = self.entries.get_mut(&key) {
self.hits = self.hits.checked_add(1).ok_or_else(|| {
"weir fixed-point execution-plan cache hit counter overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
.to_string()
})?;
self.clock = self.clock.checked_add(1).ok_or_else(|| {
"weir fixed-point execution-plan cache logical clock overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
.to_string()
})?;
let last_seen = self.clock;
entry.last_seen = last_seen;
let plan = entry.plan;
self.record_lru(key, last_seen)?;
return Ok(FixedPointExecutionPlan {
frontier_density,
..plan
});
}
self.misses = self.misses.checked_add(1).ok_or_else(|| {
"weir fixed-point execution-plan cache miss counter overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
.to_string()
})?;
self.evict_until_room()?;
self.reserve_entry_slot()?;
let plan = plan_prepared_graph(graph, frontier_density)?;
let last_seen = self.next_cache_tick()?;
self.entries.insert(
key.clone(),
FixedPointExecutionPlanCacheEntry { last_seen, plan },
);
self.record_lru(key, last_seen)?;
Ok(plan)
}
#[must_use]
pub fn stats(&self) -> FixedPointExecutionPlanCacheStats {
FixedPointExecutionPlanCacheStats {
hits: self.hits,
misses: self.misses,
evictions: self.evictions,
entries: self.entries.len(),
}
}
pub fn clear(&mut self) {
self.entries.clear();
self.lru.clear();
}
fn backend_supported_ops_fingerprint(
&self,
backend: &dyn vyre::VyreBackend,
) -> Result<u64, String> {
supported_ops_fingerprint(backend.supported_ops())
}
fn evict_until_room(&mut self) -> Result<(), String> {
while self.entries.len() >= self.max_entries {
let Some(key) = self.pop_lru_key() else {
return Ok(());
};
self.entries.remove(&key);
self.evictions = self.evictions.checked_add(1).ok_or_else(|| {
"weir fixed-point execution-plan cache eviction counter overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
.to_string()
})?;
}
Ok(())
}
fn pop_lru_key(&mut self) -> Option<FixedPointExecutionPlanCacheKey> {
self.lru.pop_valid(
|key| self.entries.get(key).map(|entry| entry.last_seen),
|| self.entries.keys().next().cloned(),
)
}
fn record_lru(
&mut self,
key: FixedPointExecutionPlanCacheKey,
last_seen: u64,
) -> Result<(), String> {
self.lru.record(
key,
last_seen,
self.entries
.iter()
.map(|(key, entry)| (key.clone(), entry.last_seen)),
"weir fixed-point execution-plan cache",
)
}
fn next_cache_tick(&mut self) -> Result<u64, String> {
self.clock = self.clock.checked_add(1).ok_or_else(|| {
"weir fixed-point execution-plan cache logical clock overflowed u64. Fix: recreate the cache before continuing an unbounded planning stream."
.to_string()
})?;
Ok(self.clock)
}
fn reserve_entry_slot(&mut self) -> Result<(), String> {
let needed = self.entries.len().checked_add(1).ok_or_else(|| {
"weir fixed-point execution-plan cache entry count overflowed usize. Fix: lower the cache bound or recreate the cache before continuing an unbounded planning stream."
.to_string()
})?;
if self.entries.capacity() >= needed {
return Ok(());
}
self.entries.try_reserve(needed - self.entries.capacity()).map_err(|error| {
format!(
"weir fixed-point execution-plan cache could not reserve {needed} plan entry slot(s): {error}. Fix: lower the cache bound or recreate the cache before continuing an unbounded planning stream."
)
})
}
}
fn supported_ops_fingerprint(
supported_ops: &std::collections::HashSet<vyre::ir::OpId>,
) -> Result<u64, String> {
const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
let count = u64::try_from(supported_ops.len()).map_err(|source| {
format!(
"weir fixed-point execution-plan supported-op count cannot fit u64: {source}. Fix: shard backend capability sets before fingerprinting."
)
});
let mut sum = 0u64;
let mut xor = 0u64;
let mut product = FNV_OFFSET;
let mut hash = FNV_OFFSET;
let count = count?;
for op in supported_ops {
let op_hash = stable_op_hash(op.as_ref())?;
sum = sum.wrapping_add(op_hash);
xor ^= op_hash.rotate_left((op_hash & 63) as u32);
product = product.wrapping_mul(op_hash | 1);
}
mix_u64(&mut hash, count);
mix_u64(&mut hash, sum);
mix_u64(&mut hash, xor);
mix_u64(&mut hash, product);
Ok(hash)
}
fn stable_op_hash(op: &str) -> Result<u64, String> {
const FNV_OFFSET: u64 = 0xcbf2_9ce4_8422_2325;
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
let mut hash = FNV_OFFSET;
for byte in op.as_bytes() {
hash ^= u64::from(*byte);
hash = hash.wrapping_mul(FNV_PRIME);
}
let len = u64::try_from(op.len()).map_err(|source| {
format!(
"weir fixed-point execution-plan op name length cannot fit u64: {source}. Fix: reject oversized backend op identifiers before fingerprinting."
)
})?;
Ok(hash ^ len)
}
fn mix_u64(hash: &mut u64, value: u64) {
const FNV_PRIME: u64 = 0x0000_0100_0000_01b3;
for byte in value.to_le_bytes() {
*hash ^= u64::from(byte);
*hash = hash.wrapping_mul(FNV_PRIME);
}
}
#[cfg(test)]
mod tests {
use super::*;
use std::collections::HashSet;
use vyre::backend::{private, BackendError, DispatchConfig, Resource};
struct FakeBackend {
version: &'static str,
supported_ops: HashSet<vyre::ir::OpId>,
}
impl private::Sealed for FakeBackend {}
impl vyre::VyreBackend for FakeBackend {
fn id(&self) -> &'static str {
"weir_test_fixed_point_execution_plan_cache"
}
fn version(&self) -> &'static str {
self.version
}
fn supported_ops(&self) -> &HashSet<vyre::ir::OpId> {
&self.supported_ops
}
fn dispatch(
&self,
_: &vyre::ir::Program,
_: &[Vec<u8>],
_: &DispatchConfig,
) -> Result<Vec<Vec<u8>>, BackendError> {
unreachable!("plan cache tests never dispatch")
}
fn allocate_resident(&self, _: usize) -> Result<Resource, BackendError> {
unreachable!("plan cache tests never allocate")
}
fn upload_resident(&self, _: &Resource, _: &[u8]) -> Result<(), BackendError> {
unreachable!("plan cache tests never upload")
}
fn upload_resident_many(&self, _: &[(&Resource, &[u8])]) -> Result<(), BackendError> {
unreachable!("plan cache tests never upload")
}
fn free_resident(&self, _: Resource) -> Result<(), BackendError> {
unreachable!("plan cache tests never free")
}
}
fn graph_for_kind(kind: FixedPointAnalysisKind) -> FixedPointForwardGraph {
FixedPointForwardGraph::new_for_kind(
kind,
"fixed_point_execution_plan_cache_test",
4096,
&[0; 4097],
&[],
&[],
)
.expect("empty graph fixture must pack")
}
fn graph() -> FixedPointForwardGraph {
graph_for_kind(FixedPointAnalysisKind::Reaching)
}
fn density(active_bits_total: u64) -> FrontierDensityTelemetry {
FrontierDensityTelemetry {
domain_bits: 4096,
samples: 2,
iterations: 1,
active_bits_total,
delta_bits_total: 1,
last_active_bits: active_bits_total / 2,
last_delta_bits: 1,
peak_active_bits: active_bits_total / 2,
peak_delta_bits: 1,
truncated_frontier_samples: 0,
domain_overflow_events: 0,
arithmetic_overflow_events: 0,
}
}
fn backend(version: &'static str, ops: &[&str]) -> FakeBackend {
FakeBackend {
version,
supported_ops: ops.iter().map(|op| vyre::ir::OpId::from(*op)).collect(),
}
}
#[test]
fn execution_plan_cache_reuses_equivalent_backend_graph_and_density_bucket() {
let backend = backend("v1", &["weir.reaching"]);
let graph = graph();
let mut cache = FixedPointExecutionPlanCache::new();
let first = cache
.get_or_plan(
&backend,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("first plan-cache lookup must build a plan");
let second = cache
.get_or_plan(
&backend,
FixedPointAnalysisKind::Reaching,
&graph,
density(10),
)
.expect("equivalent density bucket must reuse a plan");
assert_eq!(first.layout_hash, second.layout_hash);
assert_eq!(cache.stats().misses, 1);
assert_eq!(cache.stats().hits, 1);
assert_eq!(cache.stats().entries, 1);
}
#[test]
fn execution_plan_cache_separates_backend_versions_and_analysis_families() {
let backend_v1 = backend("v1", &["weir.reaching"]);
let backend_v2 = backend("v2", &["weir.reaching"]);
let reaching_graph = graph();
let live_graph = graph_for_kind(FixedPointAnalysisKind::Live);
let mut cache = FixedPointExecutionPlanCache::new();
let _ = cache
.get_or_plan(
&backend_v1,
FixedPointAnalysisKind::Reaching,
&reaching_graph,
density(8),
)
.expect("backend v1 reaching plan must build");
let _ = cache
.get_or_plan(
&backend_v2,
FixedPointAnalysisKind::Reaching,
&reaching_graph,
density(8),
)
.expect("backend v2 reaching plan must build separately");
let _ = cache
.get_or_plan(
&backend_v1,
FixedPointAnalysisKind::Live,
&live_graph,
density(8),
)
.expect("live plan must build separately from reaching");
assert_eq!(cache.stats().misses, 3);
assert_eq!(cache.stats().hits, 0);
assert_eq!(cache.stats().entries, 3);
}
#[test]
fn execution_plan_cache_rejects_mismatched_graph_family_before_cache_mutation() {
let backend = backend("v1", &["weir.reaching"]);
let graph = FixedPointForwardGraph::new_for_kind(
FixedPointAnalysisKind::Live,
"fixed_point_execution_plan_cache_wrong_family",
2,
&[0, 1, 1],
&[1],
&[vyre_primitives::predicate::edge_kind::CONTROL],
)
.expect("typed live graph must pack");
let mut cache = FixedPointExecutionPlanCache::new();
let error = cache
.get_or_plan(
&backend,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect_err("plan cache must reject mismatched analysis family");
assert!(
error.contains("expected Reaching"),
"unexpected diagnostic: {error}"
);
assert_eq!(cache.stats(), FixedPointExecutionPlanCacheStats::default());
}
#[test]
fn execution_plan_cache_separates_supported_op_feature_sets() {
let backend_control_only = backend("v1", &["weir.reaching"]);
let backend_control_and_live = backend("v1", &["weir.live", "weir.reaching"]);
let graph = graph();
let mut cache = FixedPointExecutionPlanCache::new();
let _ = cache
.get_or_plan(
&backend_control_only,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("first supported-op feature-set plan must build");
let _ = cache
.get_or_plan(
&backend_control_and_live,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("changed supported-op feature-set plan must build separately");
assert_eq!(cache.stats().misses, 2);
assert_eq!(cache.stats().hits, 0);
assert_eq!(cache.stats().entries, 2);
}
#[test]
fn supported_ops_fingerprint_is_order_independent_without_sorted_scratch() {
let first = ["weir.reaching", "weir.live", "weir.slice"]
.into_iter()
.map(vyre::ir::OpId::from)
.collect::<HashSet<_>>();
let second = ["weir.slice", "weir.reaching", "weir.live"]
.into_iter()
.map(vyre::ir::OpId::from)
.collect::<HashSet<_>>();
let third = ["weir.reaching", "weir.live", "weir.points_to_subset"]
.into_iter()
.map(vyre::ir::OpId::from)
.collect::<HashSet<_>>();
assert_eq!(
supported_ops_fingerprint(&first).expect("first fingerprint must fit"),
supported_ops_fingerprint(&second).expect("second fingerprint must fit")
);
assert_ne!(
supported_ops_fingerprint(&first).expect("first fingerprint must fit"),
supported_ops_fingerprint(&third).expect("third fingerprint must fit")
);
}
#[test]
fn execution_plan_cache_evicts_least_recently_used_entry_at_bound() {
let backend_a = backend("v1", &["weir.a"]);
let backend_b = backend("v1", &["weir.b"]);
let backend_c = backend("v1", &["weir.c"]);
let graph = graph();
let mut cache = FixedPointExecutionPlanCache::with_max_entries(2);
let _ = cache
.get_or_plan(
&backend_a,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("backend a plan must build");
let _ = cache
.get_or_plan(
&backend_b,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("backend b plan must build");
let _ = cache
.get_or_plan(
&backend_a,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("backend a plan must hit");
let _ = cache
.get_or_plan(
&backend_c,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("backend c plan must evict least-recently-used entry");
assert_eq!(cache.stats().entries, 2);
assert_eq!(cache.stats().evictions, 1);
assert_eq!(cache.stats().hits, 1);
assert_eq!(cache.stats().misses, 3);
let _ = cache
.get_or_plan(
&backend_b,
FixedPointAnalysisKind::Reaching,
&graph,
density(8),
)
.expect("evicted backend b plan must rebuild");
assert_eq!(
cache.stats().misses,
4,
"Fix: the least-recently-used backend_b entry should have been evicted, not the recently-hit backend_a entry."
);
}
#[test]
fn execution_plan_cache_lru_heap_stays_capacity_scale() {
let graph = graph();
let mut cache = FixedPointExecutionPlanCache::with_max_entries(4);
for idx in 0..96u32 {
let op = format!("weir.op.{idx}");
let backend = backend("v1", &[op.as_str()]);
let _ = cache
.get_or_plan(
&backend,
FixedPointAnalysisKind::Reaching,
&graph,
density(u64::from(idx.saturating_add(1))),
)
.expect("plan cache lookup must build or reuse");
let _ = cache
.get_or_plan(
&backend,
FixedPointAnalysisKind::Reaching,
&graph,
density(u64::from(idx.saturating_add(1))),
)
.expect("plan cache hit must update recency");
}
assert_eq!(cache.stats().entries, 4);
assert!(
cache.lru.len() <= cache.entries.len().saturating_mul(4).max(8),
"Fix: execution-plan cache LRU heap must compact stale touches to cache-capacity scale"
);
}
#[test]
fn execution_plan_cache_source_has_no_release_path_panic_or_unwrap() {
let source = include_str!("fixed_point_execution_plan_cache.rs");
for forbidden in [
concat!("panic", "!("),
concat!(".unwrap_or_else", "(|source|"),
concat!(".", "unwrap()"),
] {
assert!(
!source.contains(forbidden),
"Fix: fixed-point execution-plan cache must return errors instead of panicking or unwrapping in release-path planning/fingerprinting: {forbidden}"
);
}
assert!(
source.contains("fn reserve_entry_slot(&mut self)")
&& source.contains("self.reserve_entry_slot()?")
&& source.contains("ResidentCacheLru")
&& source.contains("self.lru.record("),
"Fix: fixed-point execution-plan cache allocation and recency policy must stay modular and share the fallible LRU helper instead of reimplementing a local heap."
);
}
}