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

aver/interpreter/
mod.rs
