aver/interpreter/
mod.rs

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

aver/interpreter/
mod.rs
