flint_lean/
tracked.rs

1//! Collections that remember which keys changed since they were loaded,
2//! so the baseline persists what a save changed rather than the whole
3//! document (lever D, `docs/plans/flint-lean-latency-plan-2026-10-23.md`).
4//!
5//! Reads go through `Deref` to the plain `BTreeMap` / `BTreeSet`. There is
6//! deliberately no `DerefMut`: every mutation goes through a method here
7//! that records the key, so a mutation the journal would miss does not
8//! compile. A key is recorded whether or not the mutation changed its
9//! value (`get_mut`, a no-op `insert`): the journal may say more than
10//! changed, never less.
11//!
12//! What it cannot record is a collection REPLACED whole: an assignment
13//! drops the old one, and with it the members the new one lacks. So each
14//! collection carries the `lineage` it was loaded under. The store writes
15//! only the recorded keys when every collection is still of the lineage
16//! the disk holds, and the whole document otherwise. Anything built here
17//! rather than loaded (`Default`, `FromIterator`) is of lineage 0, which
18//! the disk never holds.
19
20use std::borrow::Borrow;
21use std::collections::{BTreeMap, BTreeSet};
22use std::ops::Deref;
23
24use serde::{Deserialize, Deserializer, Serialize, Serializer};
25
26/// A `BTreeMap<String, V>` that records the keys it was changed at.
27#[derive(Debug, Clone)]
28pub struct TrackedMap<V> {
29    inner: BTreeMap<String, V>,
30    touched: BTreeSet<String>,
31    lineage: u64,
32}
33
34impl<V> Default for TrackedMap<V> {
35    fn default() -> Self {
36        Self { inner: BTreeMap::new(), touched: BTreeSet::new(), lineage: 0 }
37    }
38}
39
40impl<V> Deref for TrackedMap<V> {
41    type Target = BTreeMap<String, V>;
42    fn deref(&self) -> &Self::Target {
43        &self.inner
44    }
45}
46
47impl<V: PartialEq> PartialEq for TrackedMap<V> {
48    fn eq(&self, other: &Self) -> bool {
49        self.inner == other.inner
50    }
51}
52
53impl<'a, V> IntoIterator for &'a TrackedMap<V> {
54    type Item = (&'a String, &'a V);
55    type IntoIter = std::collections::btree_map::Iter<'a, String, V>;
56    fn into_iter(self) -> Self::IntoIter {
57        self.inner.iter()
58    }
59}
60
61impl<V> TrackedMap<V> {
62    pub fn insert(&mut self, k: String, v: V) -> Option<V> {
63        self.touched.insert(k.clone());
64        self.inner.insert(k, v)
65    }
66
67    pub fn remove<Q>(&mut self, k: &Q) -> Option<V>
68    where
69        String: Borrow<Q>,
70        Q: Ord + ?Sized + ToOwned<Owned = String>,
71    {
72        let v = self.inner.remove(k);
73        if v.is_some() {
74            self.touched.insert(k.to_owned());
75        }
76        v
77    }
78
79    pub fn get_mut<Q>(&mut self, k: &Q) -> Option<&mut V>
80    where
81        String: Borrow<Q>,
82        Q: Ord + ?Sized + ToOwned<Owned = String>,
83    {
84        if self.inner.contains_key(k) {
85            self.touched.insert(k.to_owned());
86        }
87        self.inner.get_mut(k)
88    }
89
90    pub fn clear(&mut self) {
91        let old = std::mem::take(&mut self.inner);
92        self.touched.extend(old.into_keys());
93    }
94
95    pub fn retain(&mut self, mut keep: impl FnMut(&String, &mut V) -> bool) {
96        let touched = &mut self.touched;
97        self.inner.retain(|k, v| {
98            let kept = keep(k, v);
99            if !kept {
100                touched.insert(k.clone());
101            }
102            kept
103        });
104    }
105
106    /// The keys changed since the last call, and forget them.
107    pub(crate) fn take_touched(&mut self) -> BTreeSet<String> {
108        std::mem::take(&mut self.touched)
109    }
110
111    pub(crate) fn touched_len(&self) -> usize {
112        self.touched.len()
113    }
114
115    /// Replay a journal record: no key is recorded as changed.
116    pub(crate) fn lineage(&self) -> u64 {
117        self.lineage
118    }
119
120    /// The store's mark: this map is the disk's state at `lineage`, plus
121    /// the changes it records.
122    pub(crate) fn stamp(&mut self, lineage: u64) {
123        self.lineage = lineage;
124    }
125
126    pub(crate) fn apply_put(&mut self, k: String, v: V) {
127        self.inner.insert(k, v);
128    }
129
130    pub(crate) fn apply_del(&mut self, k: &str) {
131        self.inner.remove(k);
132    }
133}
134
135impl<V> FromIterator<(String, V)> for TrackedMap<V> {
136    /// A map built whole: every key counts as changed.
137    fn from_iter<I: IntoIterator<Item = (String, V)>>(iter: I) -> Self {
138        let inner: BTreeMap<String, V> = iter.into_iter().collect();
139        let touched = inner.keys().cloned().collect();
140        Self { inner, touched, lineage: 0 }
141    }
142}
143
144impl<V: Serialize> Serialize for TrackedMap<V> {
145    fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
146        self.inner.serialize(s)
147    }
148}
149
150impl<'de, V: Deserialize<'de>> Deserialize<'de> for TrackedMap<V> {
151    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
152        Ok(Self { inner: BTreeMap::deserialize(d)?, touched: BTreeSet::new(), lineage: 0 })
153    }
154}
155
156/// A `BTreeSet<String>` that records the members it gained or lost.
157#[derive(Debug, Clone, Default)]
158pub struct TrackedSet {
159    inner: BTreeSet<String>,
160    touched: BTreeSet<String>,
161    lineage: u64,
162}
163
164impl Deref for TrackedSet {
165    type Target = BTreeSet<String>;
166    fn deref(&self) -> &Self::Target {
167        &self.inner
168    }
169}
170
171impl PartialEq for TrackedSet {
172    fn eq(&self, other: &Self) -> bool {
173        self.inner == other.inner
174    }
175}
176
177impl<'a> IntoIterator for &'a TrackedSet {
178    type Item = &'a String;
179    type IntoIter = std::collections::btree_set::Iter<'a, String>;
180    fn into_iter(self) -> Self::IntoIter {
181        self.inner.iter()
182    }
183}
184
185impl TrackedSet {
186    pub fn insert(&mut self, k: String) -> bool {
187        let added = self.inner.insert(k.clone());
188        if added {
189            self.touched.insert(k);
190        }
191        added
192    }
193
194    pub fn remove<Q>(&mut self, k: &Q) -> bool
195    where
196        String: Borrow<Q>,
197        Q: Ord + ?Sized + ToOwned<Owned = String>,
198    {
199        let removed = self.inner.remove(k);
200        if removed {
201            self.touched.insert(k.to_owned());
202        }
203        removed
204    }
205
206    pub fn clear(&mut self) {
207        let old = std::mem::take(&mut self.inner);
208        self.touched.extend(old);
209    }
210
211    /// Become exactly `members`, which must be sorted and free of
212    /// duplicates (a `BTreeMap`'s or `BTreeSet`'s keys). One merge walk:
213    /// only the members gained or lost are copied, so a set of a million
214    /// that did not change costs comparisons, not a million allocations.
215    pub fn sync_to<'a>(&mut self, members: impl IntoIterator<Item = &'a String>) {
216        let mut add: Vec<String> = vec![];
217        let mut del: Vec<String> = vec![];
218        {
219            let mut have = self.inner.iter().peekable();
220            for want in members {
221                loop {
222                    match have.peek() {
223                        Some(h) if *h < want => {
224                            del.push((*h).clone());
225                            have.next();
226                        }
227                        Some(h) if *h == want => {
228                            have.next();
229                            break;
230                        }
231                        _ => {
232                            add.push(want.clone());
233                            break;
234                        }
235                    }
236                }
237            }
238            del.extend(have.cloned());
239        }
240        for k in del {
241            self.inner.remove(&k);
242            self.touched.insert(k);
243        }
244        for k in add {
245            self.inner.insert(k.clone());
246            self.touched.insert(k);
247        }
248    }
249
250    pub(crate) fn take_touched(&mut self) -> BTreeSet<String> {
251        std::mem::take(&mut self.touched)
252    }
253
254    pub(crate) fn touched_len(&self) -> usize {
255        self.touched.len()
256    }
257
258    pub(crate) fn lineage(&self) -> u64 {
259        self.lineage
260    }
261
262    pub(crate) fn stamp(&mut self, lineage: u64) {
263        self.lineage = lineage;
264    }
265
266    pub(crate) fn apply_add(&mut self, k: String) {
267        self.inner.insert(k);
268    }
269
270    pub(crate) fn apply_del(&mut self, k: &str) {
271        self.inner.remove(k);
272    }
273}
274
275impl FromIterator<String> for TrackedSet {
276    /// A set built whole: every member counts as changed.
277    fn from_iter<I: IntoIterator<Item = String>>(iter: I) -> Self {
278        let inner: BTreeSet<String> = iter.into_iter().collect();
279        let touched = inner.clone();
280        Self { inner, touched, lineage: 0 }
281    }
282}
283
284impl Serialize for TrackedSet {
285    fn serialize<S: Serializer>(&self, s: S) -> Result<S::Ok, S::Error> {
286        self.inner.serialize(s)
287    }
288}
289
290impl<'de> Deserialize<'de> for TrackedSet {
291    fn deserialize<D: Deserializer<'de>>(d: D) -> Result<Self, D::Error> {
292        Ok(Self { inner: BTreeSet::deserialize(d)?, touched: BTreeSet::new(), lineage: 0 })
293    }
294}
flint_lean/tracked.rs

flint_lean/
tracked.rs
