aver/interpreter/
mod.rs

1use crate::value::hash_memo_args;
2use std::collections::{HashMap, HashSet};
3use std::path::{Path, PathBuf};
4use std::rc::Rc;
5
6use crate::ast::*;
7use crate::replay::{
8    EffectRecord, JsonValue, RecordedOutcome, SessionRecording, json_to_string,
9    session_recording_to_string_pretty, value_to_json, values_to_json_lossy,
10};
11use crate::services::{console, disk, http, http_server, tcp};
12use crate::source::{
13    canonicalize_path, find_module_file, parse_source, require_module_declaration,
14};
15use crate::types::{byte, char, float, int, list, map, option, result, string};
16// Re-export value types so existing `use aver::interpreter::Value` imports keep working.
17pub use crate::value::{Env, EnvFrame, RuntimeError, Value, aver_display, aver_repr};
18use crate::value::{list_from_vec, list_len, list_slice, list_tail_view};
19
20#[derive(Debug, Clone)]
21struct CallFrame {
22    name: String,
23    effects: Vec<String>,
24}
25
26#[derive(Debug, Clone, Copy, PartialEq, Eq)]
27pub enum ExecutionMode {
28    Normal,
29    Record,
30    Replay,
31}
32
33const MEMO_CACHE_CAP_PER_FN: usize = 4096;
34
35#[derive(Debug, Clone)]
36struct MemoEntry {
37    id: u64,
38    args: Vec<Value>,
39    result: Value,
40}
41
42#[derive(Debug, Clone)]
43struct RecordingSink {
44    path: PathBuf,
45    request_id: String,
46    timestamp: String,
47    program_file: String,
48    module_root: String,
49    entry_fn: String,
50    input: JsonValue,
51}
52
53type MatchSiteKey = (usize, usize); // (line, arm_count)
54
55#[derive(Debug, Clone)]
56struct VerifyMatchCoverageTracker {
57    target_fn: String,
58    expected_arms: std::collections::BTreeMap<MatchSiteKey, usize>,
59    visited_arms: HashMap<MatchSiteKey, HashSet<usize>>,
60}
61
62#[derive(Debug, Clone, PartialEq, Eq)]
63pub struct VerifyMatchCoverageMiss {
64    pub line: usize,
65    pub total_arms: usize,
66    pub missing_arms: Vec<usize>, // 0-based arm indices
67}
68
69#[derive(Debug, Clone)]
70pub struct RecordingConfig {
71    pub path: PathBuf,
72    pub request_id: String,
73    pub timestamp: String,
74    pub program_file: String,
75    pub module_root: String,
76    pub entry_fn: String,
77    pub input: JsonValue,
78}
79
80/// Per-function memo cache with collision-safe buckets and true LRU eviction.
81#[derive(Debug, Default, Clone)]
82struct FnMemoCache {
83    /// Primary index: hash(args) -> bucket of potentially colliding entries.
84    buckets: HashMap<u64, Vec<MemoEntry>>,
85    /// Entry id -> (bucket hash, index in bucket vec).
86    positions: HashMap<u64, (u64, usize)>,
87    /// LRU links: entry id -> (prev, next).
88    links: HashMap<u64, (Option<u64>, Option<u64>)>,
89    lru_head: Option<u64>,
90    lru_tail: Option<u64>,
91    next_id: u64,
92    len: usize,
93}
94
95impl FnMemoCache {
96    fn get(&mut self, hash: u64, args: &[Value]) -> Option<Value> {
97        let found = self
98            .buckets
99            .get_mut(&hash)
100            .and_then(|entries| entries.iter_mut().find(|entry| entry.args == args))
101            .map(|entry| (entry.id, entry.result.clone()));
102
103        if let Some((id, value)) = found {
104            self.touch(id);
105            Some(value)
106        } else {
107            None
108        }
109    }
110
111    fn insert(&mut self, hash: u64, args: Vec<Value>, result: Value, cap: usize) {
112        let update_hit = self
113            .buckets
114            .get_mut(&hash)
115            .and_then(|entries| entries.iter_mut().find(|entry| entry.args == args))
116            .map(|entry| {
117                entry.result = result.clone();
118                entry.id
119            });
120
121        if let Some(id) = update_hit {
122            self.touch(id);
123            return;
124        }
125
126        if self.len >= cap {
127            self.evict_lru();
128        }
129
130        let id = self.alloc_id();
131        let entry = MemoEntry { id, args, result };
132        let idx = self.buckets.entry(hash).or_default().len();
133        self.buckets.entry(hash).or_default().push(entry);
134        self.positions.insert(id, (hash, idx));
135        self.append_tail(id);
136        self.len += 1;
137    }
138
139    fn alloc_id(&mut self) -> u64 {
140        let id = self.next_id;
141        self.next_id = self.next_id.wrapping_add(1);
142        id
143    }
144
145    fn evict_lru(&mut self) {
146        if let Some(id) = self.lru_head {
147            self.remove_entry(id);
148        }
149    }
150
151    fn touch(&mut self, id: u64) {
152        if self.lru_tail == Some(id) {
153            return;
154        }
155        self.detach(id);
156        self.append_tail(id);
157    }
158
159    fn append_tail(&mut self, id: u64) {
160        let prev = self.lru_tail;
161        self.links.insert(id, (prev, None));
162        if let Some(tail) = prev {
163            if let Some((_, next)) = self.links.get_mut(&tail) {
164                *next = Some(id);
165            }
166        } else {
167            self.lru_head = Some(id);
168        }
169        self.lru_tail = Some(id);
170    }
171
172    fn detach(&mut self, id: u64) {
173        let Some((prev, next)) = self.links.get(&id).copied() else {
174            return;
175        };
176
177        if let Some(p) = prev {
178            if let Some((_, p_next)) = self.links.get_mut(&p) {
179                *p_next = next;
180            }
181        } else {
182            self.lru_head = next;
183        }
184
185        if let Some(n) = next {
186            if let Some((n_prev, _)) = self.links.get_mut(&n) {
187                *n_prev = prev;
188            }
189        } else {
190            self.lru_tail = prev;
191        }
192
193        if let Some(link) = self.links.get_mut(&id) {
194            *link = (None, None);
195        }
196    }
197
198    fn remove_entry(&mut self, id: u64) {
199        let Some((hash, idx)) = self.positions.remove(&id) else {
200            return;
201        };
202        self.detach(id);
203        self.links.remove(&id);
204
205        let mut remove_bucket = false;
206        if let Some(entries) = self.buckets.get_mut(&hash) {
207            entries.swap_remove(idx);
208            if idx < entries.len() {
209                let moved_id = entries[idx].id;
210                self.positions.insert(moved_id, (hash, idx));
211            }
212            remove_bucket = entries.is_empty();
213        }
214        if remove_bucket {
215            self.buckets.remove(&hash);
216        }
217        self.len = self.len.saturating_sub(1);
218    }
219}
220
221pub struct Interpreter {
222    pub env: Env,
223    module_cache: HashMap<String, Value>,
224    /// Record field order schemas by type name (used to validate and
225    /// canonicalize `RecordCreate` runtime values).
226    record_schemas: HashMap<String, Vec<String>>,
227    call_stack: Vec<CallFrame>,
228    /// Named effect aliases: `effects AppIO = [Console, Disk]`
229    effect_aliases: HashMap<String, Vec<String>>,
230    /// Active slot mapping for resolved function bodies.
231    /// Set when entering a resolved fn, cleared on exit.
232    active_local_slots: Option<HashMap<String, u16>>,
233    /// Names of pure recursive functions eligible for auto-memoization.
234    memo_fns: HashSet<String>,
235    /// Per-function memo cache with collision-safe entries and LRU eviction.
236    memo_cache: HashMap<String, FnMemoCache>,
237    execution_mode: ExecutionMode,
238    recorded_effects: Vec<EffectRecord>,
239    replay_effects: Vec<EffectRecord>,
240    replay_pos: usize,
241    validate_replay_args: bool,
242    recording_sink: Option<RecordingSink>,
243    verify_match_coverage: Option<VerifyMatchCoverageTracker>,
244}
245
246mod api;
247mod builtins;
248mod core;
249mod effects;
250mod eval;
251mod exec;
252mod ops;
253mod patterns;
254
255#[cfg(test)]
256mod memo_cache_tests {
257    use super::*;
258
259    #[test]
260    fn collision_bucket_is_exact_match_on_args() {
261        let mut cache = FnMemoCache::default();
262        cache.insert(1, vec![Value::Int(1)], Value::Int(10), 8);
263        cache.insert(1, vec![Value::Int(2)], Value::Int(20), 8);
264
265        assert_eq!(cache.get(1, &[Value::Int(1)]), Some(Value::Int(10)));
266        assert_eq!(cache.get(1, &[Value::Int(2)]), Some(Value::Int(20)));
267        assert_eq!(cache.get(1, &[Value::Int(3)]), None);
268    }
269
270    #[test]
271    fn lru_evicts_least_recently_used() {
272        let mut cache = FnMemoCache::default();
273        cache.insert(11, vec![Value::Int(1)], Value::Int(10), 2);
274        cache.insert(22, vec![Value::Int(2)], Value::Int(20), 2);
275
276        // Touch key=11 so key=22 becomes LRU.
277        assert_eq!(cache.get(11, &[Value::Int(1)]), Some(Value::Int(10)));
278        cache.insert(33, vec![Value::Int(3)], Value::Int(30), 2);
279
280        assert_eq!(cache.get(11, &[Value::Int(1)]), Some(Value::Int(10)));
281        assert_eq!(cache.get(22, &[Value::Int(2)]), None);
282        assert_eq!(cache.get(33, &[Value::Int(3)]), Some(Value::Int(30)));
283    }
284}
aver/interpreter/mod.rs

aver/interpreter/
mod.rs
