yo/
map.rs

1//! `Map<K, V>`, the first typed handle (`15` section 2).
2
3use core::marker::PhantomData;
4use std::borrow::Borrow;
5
6use yo_common::{Code, Error, Result};
7use yo_index::RawMap;
8use yo_shape::Tag;
9
10use crate::db::Handle;
11use crate::store::{Decode, Encode};
12
13/// A map from `K` to `V`.
14///
15/// Cheap to clone and cheap to keep around: the handle is a pointer and an
16/// index, so cloning one does not copy anything and every clone is the same
17/// collection.
18///
19/// The type parameters are not decoration. They are the collection's shape
20/// (`15` section 3), they are written down when it is created, and they are
21/// what a later open is checked against.
22///
23/// # Borrowed lookups
24///
25/// A lookup takes a borrowed form of the key, the same way `HashMap` does, so
26/// a `Map<String, u64>` is read with `map.get("home")` and not with a `String`
27/// built for the length of one call.
28///
29/// ```
30/// let db = yo::open(yo::MEMORY)?;
31/// let hits = db.map::<String, u64>("hits")?;
32///
33/// hits.set("home", &1)?;
34/// assert_eq!(hits.get("home")?, Some(1));
35/// assert_eq!(hits.get("about")?, None);
36/// # Ok::<(), yo::Error>(())
37/// ```
38pub struct Map<K, V> {
39    db: Handle,
40    at: usize,
41    tag: Tag,
42    /// `fn() -> (K, V)` rather than `(K, V)` so that the handle's auto traits
43    /// and variance come from the handle rather than from what it holds.
44    marker: PhantomData<fn() -> (K, V)>,
45}
46
47impl<K, V> Clone for Map<K, V> {
48    fn clone(&self) -> Map<K, V> {
49        Map {
50            db: self.db.clone(),
51            at: self.at,
52            tag: self.tag,
53            marker: PhantomData,
54        }
55    }
56}
57
58impl<K, V> core::fmt::Debug for Map<K, V> {
59    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
60        let name = self
61            .db
62            .read(|inner| Ok(inner.collections[self.at].name.clone()))
63            .unwrap_or_else(|_| "?".to_owned());
64        f.debug_struct("Map").field("name", &name).finish()
65    }
66}
67
68impl<K: Decode, V: Decode> Map<K, V> {
69    pub(crate) fn new(db: Handle, at: usize, tag: Tag) -> Map<K, V> {
70        Map {
71            db,
72            at,
73            tag,
74            marker: PhantomData,
75        }
76    }
77
78    /// The name this collection was opened under.
79    ///
80    /// # Errors
81    ///
82    /// [`Code::Invalid`] if called from inside a callback that is already
83    /// holding this database.
84    pub fn name(&self) -> Result<String> {
85        self.read(|c| Ok(c.name.clone()))
86    }
87
88    /// This collection's shape tag.
89    ///
90    /// The same 128 bits that a file carries and that another language's
91    /// binding computes for the same type. Carried in the handle rather than
92    /// read out of the database, so it costs nothing and cannot fail.
93    #[must_use]
94    pub fn tag(&self) -> Tag {
95        self.tag
96    }
97
98    /// Read a value, owned.
99    ///
100    /// One allocation for the value, and none for the key. When even that one
101    /// is too many, [`Map::with`] hands over the bytes where they lie.
102    ///
103    /// # Errors
104    ///
105    /// [`Code::Corrupt`] if the stored bytes are not a `V`, which means the
106    /// file disagrees with its own shape.
107    pub fn get<Q>(&self, key: &Q) -> Result<Option<V>>
108    where
109        K: Borrow<Q>,
110        Q: Encode + ?Sized,
111    {
112        self.read(|c| match key.encode(|k| c.data.get(k)) {
113            // Decoded straight out of the arena rather than copied out and then
114            // decoded, so a fixed width value costs no allocation at all and a
115            // string costs exactly the one the caller asked for.
116            Some(bytes) => V::decode(bytes).map(Some),
117            None => Ok(None),
118        })
119    }
120
121    /// Read a value without copying it, by handing the borrowed view to `f`.
122    ///
123    /// This is Y29 in one method: zero copy is always available and never
124    /// mandatory. The view points into the arena, so nothing is allocated and
125    /// nothing is decoded beyond checking that the bytes are a `V`. It is also
126    /// where G6's point read budget is spent, which is why the closure takes
127    /// the view rather than the value.
128    ///
129    /// `f` runs while the database is borrowed, so it cannot call back into
130    /// the same database. One that tries gets [`Code::Invalid`] rather than a
131    /// panic.
132    ///
133    /// ```
134    /// let db = yo::open(yo::MEMORY)?;
135    /// let names = db.map::<u64, String>("names")?;
136    /// names.set(&7, "ada")?;
137    ///
138    /// // No String is built here, and no bytes are copied.
139    /// let len = names.with(&7, str::len)?;
140    /// assert_eq!(len, Some(3));
141    /// # Ok::<(), yo::Error>(())
142    /// ```
143    ///
144    /// # Errors
145    ///
146    /// [`Code::Corrupt`] if the stored bytes are not a `V`.
147    pub fn with<Q, R>(&self, key: &Q, f: impl FnOnce(V::Ref<'_>) -> R) -> Result<Option<R>>
148    where
149        K: Borrow<Q>,
150        Q: Encode + ?Sized,
151    {
152        self.read(|c| match key.encode(|k| c.data.get(k)) {
153            Some(bytes) => V::view(bytes).map(|view| Some(f(view))),
154            None => Ok(None),
155        })
156    }
157
158    /// Store a value, replacing whatever was there.
159    ///
160    /// The value is taken borrowed as well as the key, so a
161    /// `Map<String, String>` is written with `map.set("k", "v")`.
162    ///
163    /// # Errors
164    ///
165    /// [`Code::Full`] if the key and the value together are larger than
166    /// [`Map::max_entry`]. A value that big belongs in the log region, which
167    /// arrives with the file format in M5.
168    pub fn set<Q, W>(&self, key: &Q, value: &W) -> Result<()>
169    where
170        K: Borrow<Q>,
171        Q: Encode + ?Sized,
172        V: Borrow<W>,
173        W: Encode + ?Sized,
174    {
175        self.write(|c| {
176            key.encode(|k| {
177                value.encode(|v| {
178                    let total = RawMap::header_len() + k.len() + v.len();
179                    if total > RawMap::max_record() {
180                        return Err(too_big(total));
181                    }
182                    c.data.set(k, v);
183                    Ok(())
184                })
185            })
186        })
187    }
188
189    /// Remove a key, returning whether it was there.
190    ///
191    /// # Errors
192    ///
193    /// [`Code::Invalid`] if called from inside a callback that is already
194    /// holding this database.
195    pub fn del<Q>(&self, key: &Q) -> Result<bool>
196    where
197        K: Borrow<Q>,
198        Q: Encode + ?Sized,
199    {
200        self.write(|c| Ok(key.encode(|k| c.data.del(k))))
201    }
202
203    /// Whether a key is present, without reading its value.
204    ///
205    /// # Errors
206    ///
207    /// [`Code::Invalid`] if called from inside a callback that is already
208    /// holding this database.
209    pub fn contains<Q>(&self, key: &Q) -> Result<bool>
210    where
211        K: Borrow<Q>,
212        Q: Encode + ?Sized,
213    {
214        self.read(|c| Ok(key.encode(|k| c.data.contains(k))))
215    }
216
217    /// How many keys are stored.
218    ///
219    /// # Errors
220    ///
221    /// [`Code::Invalid`] if called from inside a callback that is already
222    /// holding this database.
223    pub fn len(&self) -> Result<usize> {
224        self.read(|c| Ok(c.data.len()))
225    }
226
227    /// Whether the collection is empty.
228    ///
229    /// # Errors
230    ///
231    /// [`Code::Invalid`] if called from inside a callback that is already
232    /// holding this database.
233    pub fn is_empty(&self) -> Result<bool> {
234        self.read(|c| Ok(c.data.is_empty()))
235    }
236
237    /// The largest key and value this collection takes, the two together.
238    #[must_use]
239    pub const fn max_entry() -> usize {
240        RawMap::max_record() - RawMap::header_len()
241    }
242
243    fn read<R>(&self, f: impl FnOnce(&crate::db::Collection) -> Result<R>) -> Result<R> {
244        self.db.read(|inner| f(&inner.collections[self.at]))
245    }
246
247    fn write<R>(&self, f: impl FnOnce(&mut crate::db::Collection) -> Result<R>) -> Result<R> {
248        self.db.write(|inner| f(&mut inner.collections[self.at]))
249    }
250}
251
252fn too_big(total: usize) -> Error {
253    Error::fmt(
254        Code::Full,
255        format_args!(
256            "a key and value of {} bytes is larger than the {} a record holds. A value that size belongs in the log region, which arrives with the .yo format in M5",
257            total - RawMap::header_len(),
258            Map::<Vec<u8>, Vec<u8>>::max_entry()
259        ),
260    )
261}
262
263#[cfg(test)]
264mod tests {
265    use crate::{MEMORY, open};
266
267    #[test]
268    fn a_map_of_strings_to_numbers_reads_back_what_it_wrote() {
269        let db = open(MEMORY).unwrap();
270        let hits = db.map::<String, u64>("hits").unwrap();
271
272        assert!(hits.is_empty().unwrap());
273        hits.set("home", &1).unwrap();
274        hits.set("about", &2).unwrap();
275
276        assert_eq!(hits.get("home").unwrap(), Some(1));
277        assert_eq!(hits.get("about").unwrap(), Some(2));
278        assert_eq!(hits.get("nowhere").unwrap(), None);
279        assert_eq!(hits.len().unwrap(), 2);
280        assert!(hits.contains("home").unwrap());
281        assert_eq!(hits.name().unwrap(), "hits");
282    }
283
284    #[test]
285    fn a_write_replaces_and_a_delete_removes() {
286        let db = open(MEMORY).unwrap();
287        let hits = db.map::<String, u64>("hits").unwrap();
288
289        hits.set("home", &1).unwrap();
290        hits.set("home", &9).unwrap();
291        assert_eq!(hits.get("home").unwrap(), Some(9));
292        assert_eq!(hits.len().unwrap(), 1);
293
294        assert!(hits.del("home").unwrap());
295        assert!(!hits.del("home").unwrap());
296        assert_eq!(hits.get("home").unwrap(), None);
297        assert!(hits.is_empty().unwrap());
298    }
299
300    /// The DX claim in one test: neither side of a write needs an owned value
301    /// built for the length of the call.
302    #[test]
303    fn neither_the_key_nor_the_value_has_to_be_owned() {
304        let db = open(MEMORY).unwrap();
305        let names = db.map::<String, String>("names").unwrap();
306
307        names.set("7", "ada").unwrap();
308        assert_eq!(names.get("7").unwrap().as_deref(), Some("ada"));
309        assert_eq!(
310            names.with("7", str::to_owned).unwrap().as_deref(),
311            Some("ada")
312        );
313    }
314
315    #[test]
316    fn keys_can_be_numbers_and_values_can_be_bytes() {
317        let db = open(MEMORY).unwrap();
318        let blobs = db.map::<u64, Vec<u8>>("blobs").unwrap();
319
320        blobs.set(&7, b"\x00\xff".as_slice()).unwrap();
321        assert_eq!(blobs.get(&7).unwrap().as_deref(), Some(&b"\x00\xff"[..]));
322        assert_eq!(blobs.with(&7, <[u8]>::len).unwrap(), Some(2));
323        assert_eq!(blobs.with(&8, <[u8]>::len).unwrap(), None);
324    }
325
326    #[test]
327    fn a_clone_of_a_handle_is_the_same_collection() {
328        let db = open(MEMORY).unwrap();
329        let hits = db.map::<String, u64>("hits").unwrap();
330        let same = hits.clone();
331
332        hits.set("home", &4).unwrap();
333        assert_eq!(same.get("home").unwrap(), Some(4));
334        assert_eq!(same.tag(), hits.tag());
335        assert!(format!("{same:?}").contains("hits"));
336    }
337
338    /// A `with` closure that reaches back into the same database is a mistake
339    /// the caller can fix, so it gets a sentence rather than a panic.
340    #[test]
341    fn calling_back_into_the_database_from_a_closure_is_an_error() {
342        let db = open(MEMORY).unwrap();
343        let hits = db.map::<String, u64>("hits").unwrap();
344        hits.set("home", &1).unwrap();
345
346        let inner = hits.clone();
347        let e = hits
348            .with("home", |_| inner.set("other", &2))
349            .unwrap()
350            .unwrap()
351            .expect_err("a write inside a read is re-entrant");
352        assert_eq!(e.code(), yo_common::Code::Invalid);
353        assert!(e.message().contains("cannot call back"), "{e}");
354
355        // A read inside a read is fine, because nothing is being moved.
356        assert_eq!(
357            hits.with("home", |_| inner.get("home").unwrap()).unwrap(),
358            Some(Some(1))
359        );
360    }
361
362    #[test]
363    fn a_record_larger_than_the_arena_takes_is_full_rather_than_a_panic() {
364        let db = open(MEMORY).unwrap();
365        let blobs = db.map::<String, Vec<u8>>("blobs").unwrap();
366
367        let huge = vec![0u8; super::Map::<String, Vec<u8>>::max_entry()];
368        let e = blobs
369            .set("k", huge.as_slice())
370            .expect_err("one byte too far");
371        assert_eq!(e.code(), yo_common::Code::Full);
372        assert!(e.message().contains("belongs in the log region"), "{e}");
373
374        // And the edge itself still fits, header and key included.
375        let fits = vec![0u8; super::Map::<String, Vec<u8>>::max_entry() - 1];
376        blobs.set("k", fits.as_slice()).unwrap();
377        assert_eq!(blobs.with("k", <[u8]>::len).unwrap(), Some(fits.len()));
378    }
379}
yo/map.rs

yo/
map.rs
