toml_spanner/
table.rs

1#![allow(unsafe_code)]
2
3#[cfg(test)]
4#[path = "./table_tests.rs"]
5mod tests;
6
7use crate::value::{
8    FLAG_HEADER, FLAG_MASK, FLAG_SHIFT, FLAG_TABLE, Item, Key, MaybeItem, NONE, TAG_MASK,
9    TAG_SHIFT, TAG_TABLE,
10};
11use crate::{Deserialize, Error, ErrorKind, Span};
12use std::mem::size_of;
13use std::ptr::NonNull;
14
15use crate::arena::Arena;
16
17type TableEntry<'de> = (Key<'de>, Item<'de>);
18
19const MIN_CAP: u32 = 2;
20
21/// A TOML table: a flat list of key-value pairs with linear lookup.
22#[repr(C, align(8))]
23pub(crate) struct InnerTable<'de> {
24    len: u32,
25    cap: u32,
26    ptr: NonNull<TableEntry<'de>>,
27}
28
29impl<'de> InnerTable<'de> {
30    /// Creates an empty table.
31    #[inline]
32    pub fn new() -> Self {
33        Self {
34            len: 0,
35            cap: 0,
36            ptr: NonNull::dangling(),
37        }
38    }
39
40    /// Inserts a key-value pair. Does **not** check for duplicates.
41    pub fn insert(
42        &mut self,
43        key: Key<'de>,
44        item: Item<'de>,
45        arena: &Arena,
46    ) -> &mut TableEntry<'de> {
47        let len = self.len;
48        if self.len == self.cap {
49            self.grow(arena);
50        }
51        unsafe {
52            let ptr = self.ptr.as_ptr().add(len as usize);
53            ptr.write((key, item));
54            self.len = len + 1;
55            &mut (*ptr)
56        }
57    }
58
59    /// Returns the number of entries.
60    #[inline]
61    pub fn len(&self) -> usize {
62        self.len as usize
63    }
64
65    /// Returns `true` if the table has no entries.
66    #[inline]
67    pub fn is_empty(&self) -> bool {
68        self.len == 0
69    }
70
71    /// Linear scan for a key, returning both key and value references.
72    pub fn get_key_value(&self, name: &str) -> Option<(&Key<'de>, &Item<'de>)> {
73        for entry in self.entries() {
74            if entry.0.name == name {
75                return Some((&entry.0, &entry.1));
76            }
77        }
78        None
79    }
80
81    /// Returns a reference to the value for `name`.
82    pub fn get(&self, name: &str) -> Option<&Item<'de>> {
83        for entry in self.entries() {
84            if entry.0.name == name {
85                return Some(&entry.1);
86            }
87        }
88        None
89    }
90
91    /// Returns a mutable reference to the value for `name`.
92    pub fn get_mut(&mut self, name: &str) -> Option<&mut Item<'de>> {
93        for entry in self.entries_mut() {
94            if entry.0.name == name {
95                return Some(&mut entry.1);
96            }
97        }
98        None
99    }
100
101    /// Returns `true` if the table contains the key.
102    #[inline]
103    pub fn contains_key(&self, name: &str) -> bool {
104        self.get(name).is_some()
105    }
106
107    /// Removes the first entry matching `name`, returning its value.
108    /// Uses swap-remove, so the ordering of remaining entries may change.
109    pub fn remove(&mut self, name: &str) -> Option<Item<'de>> {
110        self.remove_entry(name).map(|(_, v)| v)
111    }
112
113    /// Removes the first entry matching `name`, returning the key-value pair.
114    /// Uses swap-remove, so the ordering of remaining entries may change.
115    pub fn remove_entry(&mut self, name: &str) -> Option<(Key<'de>, Item<'de>)> {
116        let idx = self.find_index(name)?;
117        Some(self.remove_at(idx))
118    }
119
120    /// Returns an iterator over mutable references to the values.
121    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut Item<'de>> {
122        self.entries_mut().iter_mut().map(|(_, v)| v)
123    }
124
125    /// Returns the span start of the first key. Used as a table discriminator
126    /// in the parser's hash index.
127    ///
128    /// # Panics
129    ///
130    /// Debug-asserts that the table is non-empty.
131    #[inline]
132    pub(crate) unsafe fn first_key_span_start_unchecked(&self) -> u32 {
133        debug_assert!(self.len > 0);
134        unsafe { (*self.ptr.as_ptr()).0.span.start }
135    }
136
137    /// Returns a slice of all entries.
138    #[inline]
139    pub fn entries(&self) -> &[TableEntry<'de>] {
140        unsafe { std::slice::from_raw_parts(self.ptr.as_ptr(), self.len as usize) }
141    }
142
143    #[inline]
144    pub(crate) fn entries_mut(&mut self) -> &mut [TableEntry<'de>] {
145        unsafe { std::slice::from_raw_parts_mut(self.ptr.as_ptr(), self.len as usize) }
146    }
147
148    pub(crate) fn find_index(&self, name: &str) -> Option<usize> {
149        for (i, entry) in self.entries().iter().enumerate() {
150            if entry.0.name == name {
151                return Some(i);
152            }
153        }
154        None
155    }
156
157    /// Remove entry at `idx` by swapping it with the last entry.
158    fn remove_at(&mut self, idx: usize) -> (Key<'de>, Item<'de>) {
159        let last = self.len as usize - 1;
160        let ptr = unsafe { self.ptr.as_ptr().add(idx) };
161        let entry = unsafe { ptr.read() };
162        if idx != last {
163            // Safety: `last` is a valid, initialized index distinct from `idx`.
164            unsafe {
165                ptr.write(self.ptr.as_ptr().add(last).read());
166            }
167        }
168        self.len -= 1;
169        entry
170    }
171
172    #[cold]
173    fn grow(&mut self, arena: &Arena) {
174        let new_cap = if self.cap == 0 {
175            MIN_CAP
176        } else {
177            self.cap.checked_mul(2).expect("capacity overflow")
178        };
179        self.grow_to(new_cap, arena);
180    }
181
182    fn grow_to(&mut self, new_cap: u32, arena: &Arena) {
183        let new_size = new_cap as usize * size_of::<TableEntry<'_>>();
184        if self.cap > 0 {
185            let old_size = self.cap as usize * size_of::<TableEntry<'_>>();
186            // Safety: ptr was returned by a prior arena alloc of old_size bytes.
187            self.ptr = unsafe { arena.realloc(self.ptr.cast(), old_size, new_size).cast() };
188        } else {
189            self.ptr = arena.alloc(new_size).cast();
190        }
191        self.cap = new_cap;
192    }
193}
194
195impl std::fmt::Debug for InnerTable<'_> {
196    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
197        let mut map = f.debug_map();
198        for (k, v) in self.entries() {
199            map.entry(k, v);
200        }
201        map.finish()
202    }
203}
204
205/// Consuming iterator over a [`Table`], yielding `(`[`Key`]`, `[`Item`]`)` pairs.
206pub struct IntoIter<'de> {
207    table: InnerTable<'de>,
208    index: u32,
209}
210
211impl<'de> Iterator for IntoIter<'de> {
212    type Item = (Key<'de>, Item<'de>);
213
214    fn next(&mut self) -> Option<Self::Item> {
215        if self.index < self.table.len {
216            let entry = unsafe { self.table.ptr.as_ptr().add(self.index as usize).read() };
217            self.index += 1;
218            Some(entry)
219        } else {
220            None
221        }
222    }
223
224    fn size_hint(&self) -> (usize, Option<usize>) {
225        let remaining = (self.table.len - self.index) as usize;
226        (remaining, Some(remaining))
227    }
228}
229
230impl ExactSizeIterator for IntoIter<'_> {}
231
232/// A TOML table with span information.
233///
234/// A `Table` is the top-level value returned by [`parse`](crate::parse) and is
235/// also the value inside any `[section]` or inline `{ ... }` table in TOML.
236/// It stores `(`[`Key`]`, `[`Item`]`)` pairs in insertion order.
237///
238/// # Accessing values
239///
240/// - **Index operators** — `table["key"]` returns a [`MaybeItem`] that never
241///   panics on missing keys, and supports chained indexing.
242/// - **`get` / `get_mut`** — return `Option<&Item>` / `Option<&mut Item>`.
243/// - **`required` / `optional`** — deserialize and *remove* a field in one
244///   step, used when implementing [`Deserialize`](crate::Deserialize).
245///   After extracting all expected fields, call [`expect_empty`](Self::expect_empty)
246///   to reject unknown keys.
247///
248/// # Constructing tables
249///
250/// Tables are normally obtained from [`parse`](crate::parse). To build one
251/// programmatically, create a table with [`Table::new`] and insert entries
252/// with [`Table::insert`]. An [`Arena`](crate::Arena) is required for
253/// insertion because entries are arena-allocated.
254///
255/// # Iteration
256///
257/// `Table` implements [`IntoIterator`] (both by reference and by value),
258/// yielding `(`[`Key`]`, `[`Item`]`)` pairs.
259///
260/// Removal via [`remove`](Self::remove), [`required`](Self::required), and
261/// [`optional`](Self::optional) uses swap-remove and may reorder remaining
262/// entries.
263#[repr(C)]
264pub struct Table<'de> {
265    pub(crate) value: InnerTable<'de>,
266    /// Bits 2-0: tag, bits 31-3: span.start
267    start_and_tag: u32,
268    /// Bit 0: flag bit (parser-internal), bits 31-1: span.end
269    end_and_flag: u32,
270}
271
272impl<'de> Table<'de> {
273    /// Creates an empty table with the given span.
274    pub fn new(span: Span) -> Table<'de> {
275        Table {
276            start_and_tag: span.start << TAG_SHIFT | TAG_TABLE,
277            end_and_flag: (span.end << FLAG_SHIFT) | FLAG_TABLE,
278            value: InnerTable::new(),
279        }
280    }
281    /// Returns the byte-offset span of this table in the source document.
282    pub fn span(&self) -> Span {
283        Span {
284            start: self.start_and_tag >> TAG_SHIFT,
285            end: self.end_and_flag >> FLAG_SHIFT,
286        }
287    }
288}
289
290impl<'de> Default for Table<'de> {
291    fn default() -> Self {
292        Self::new(Span::default())
293    }
294}
295
296impl std::fmt::Debug for Table<'_> {
297    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
298        self.value.fmt(f)
299    }
300}
301
302impl<'de> Table<'de> {
303    /// Inserts a key-value pair. Does **not** check for duplicates.
304    pub fn insert(&mut self, key: Key<'de>, value: Item<'de>, arena: &Arena) {
305        self.value.insert(key, value, arena);
306    }
307
308    /// Returns the number of entries.
309    #[inline]
310    pub fn len(&self) -> usize {
311        self.value.len()
312    }
313
314    /// Returns `true` if the table has no entries.
315    #[inline]
316    pub fn is_empty(&self) -> bool {
317        self.value.is_empty()
318    }
319
320    /// Linear scan for a key, returning both key and value references.
321    pub fn get_key_value(&self, name: &str) -> Option<(&Key<'de>, &Item<'de>)> {
322        self.value.get_key_value(name)
323    }
324
325    /// Returns a reference to the value for `name`.
326    pub fn get(&self, name: &str) -> Option<&Item<'de>> {
327        self.value.get(name)
328    }
329
330    /// Returns a mutable reference to the value for `name`.
331    pub fn get_mut(&mut self, name: &str) -> Option<&mut Item<'de>> {
332        self.value.get_mut(name)
333    }
334
335    /// Returns `true` if the table contains the key.
336    #[inline]
337    pub fn contains_key(&self, name: &str) -> bool {
338        self.value.contains_key(name)
339    }
340
341    /// Removes the first entry matching `name`, returning its value.
342    /// Uses swap-remove, so the ordering of remaining entries may change.
343    pub fn remove(&mut self, name: &str) -> Option<Item<'de>> {
344        self.value.remove(name)
345    }
346
347    /// Removes the first entry matching `name`, returning the key-value pair.
348    /// Uses swap-remove, so the ordering of remaining entries may change.
349    pub fn remove_entry(&mut self, name: &str) -> Option<(Key<'de>, Item<'de>)> {
350        self.value.remove_entry(name)
351    }
352
353    /// Returns an iterator over mutable references to the values.
354    pub fn values_mut(&mut self) -> impl Iterator<Item = &mut Item<'de>> {
355        self.value.values_mut()
356    }
357
358    /// Returns a slice of all entries.
359    #[inline]
360    pub fn entries(&self) -> &[TableEntry<'de>] {
361        self.value.entries()
362    }
363
364    /// Converts this `Table` into an [`Item`] with the same span and payload.
365    pub fn into_item(self) -> Item<'de> {
366        let span = self.span();
367        Item::table(self.value, span)
368    }
369
370    /// Removes and deserializes a field, returning an error if the key is missing.
371    pub fn required<T: Deserialize<'de>>(&mut self, name: &'static str) -> Result<T, Error> {
372        let Some(mut val) = self.value.remove(name) else {
373            return Err(Error {
374                kind: ErrorKind::MissingField(name),
375                span: self.span(),
376            });
377        };
378
379        T::deserialize(&mut val)
380    }
381
382    /// Removes and deserializes a field, returning [`None`] if the key is missing.
383    pub fn optional<T: Deserialize<'de>>(&mut self, name: &str) -> Result<Option<T>, Error> {
384        let Some(mut val) = self.value.remove(name) else {
385            return Ok(None);
386        };
387
388        match T::deserialize(&mut val) {
389            Ok(value) => Ok(Some(value)),
390            Err(err) => Err(err),
391        }
392    }
393
394    /// Returns an error if the table still has unconsumed entries.
395    ///
396    /// Call this after extracting all expected fields with [`required`](Self::required)
397    /// and [`optional`](Self::optional) to reject unknown keys.
398    pub fn expect_empty(&self) -> Result<(), Error> {
399        if self.value.is_empty() {
400            return Ok(());
401        }
402
403        // let keys = self
404        //     .value
405        //     .entries()
406        //     .iter()
407        //     .map(|(key, _)| (key.name.into(), key.span))
408        //     .collect();
409        // Note: collect version ends up generating a lot of code bloat
410        // despite being more efficient in theory.
411        let mut keys = Vec::with_capacity(self.value.len());
412        for (key, _) in self.value.entries() {
413            keys.push((key.name.into(), key.span));
414        }
415
416        Err(Error::from((
417            ErrorKind::UnexpectedKeys { keys },
418            self.span(),
419        )))
420    }
421}
422
423impl<'a, 'de> IntoIterator for &'a mut Table<'de> {
424    type Item = &'a mut (Key<'de>, Item<'de>);
425    type IntoIter = std::slice::IterMut<'a, TableEntry<'de>>;
426
427    fn into_iter(self) -> Self::IntoIter {
428        self.value.entries_mut().iter_mut()
429    }
430}
431impl<'a, 'de> IntoIterator for &'a Table<'de> {
432    type Item = &'a (Key<'de>, Item<'de>);
433    type IntoIter = std::slice::Iter<'a, TableEntry<'de>>;
434
435    fn into_iter(self) -> Self::IntoIter {
436        self.value.entries().iter()
437    }
438}
439
440impl<'de> IntoIterator for Table<'de> {
441    type Item = (Key<'de>, Item<'de>);
442    type IntoIter = IntoIter<'de>;
443
444    fn into_iter(self) -> Self::IntoIter {
445        IntoIter {
446            table: self.value,
447            index: 0,
448        }
449    }
450}
451
452const _: () = assert!(std::mem::size_of::<Table<'_>>() == std::mem::size_of::<Item<'_>>());
453const _: () = assert!(std::mem::align_of::<Table<'_>>() == std::mem::align_of::<Item<'_>>());
454
455impl<'de> Table<'de> {
456    #[inline]
457    pub(crate) fn span_start(&self) -> u32 {
458        self.start_and_tag >> TAG_SHIFT
459    }
460
461    #[inline]
462    pub(crate) fn set_span_start(&mut self, v: u32) {
463        self.start_and_tag = (v << TAG_SHIFT) | (self.start_and_tag & TAG_MASK);
464    }
465
466    #[inline]
467    pub(crate) fn set_span_end(&mut self, v: u32) {
468        self.end_and_flag = (v << FLAG_SHIFT) | (self.end_and_flag & FLAG_MASK);
469    }
470
471    #[inline]
472    pub(crate) fn extend_span_end(&mut self, new_end: u32) {
473        let old = self.end_and_flag;
474        let current = old >> FLAG_SHIFT;
475        self.end_and_flag = (current.max(new_end) << FLAG_SHIFT) | (old & FLAG_MASK);
476    }
477
478    #[inline]
479    pub(crate) fn set_header_flag(&mut self) {
480        self.end_and_flag = (self.end_and_flag & !FLAG_MASK) | FLAG_HEADER;
481    }
482}
483
484impl<'de> std::ops::Index<&str> for Table<'de> {
485    type Output = MaybeItem<'de>;
486
487    #[inline]
488    fn index(&self, index: &str) -> &Self::Output {
489        if let Some(item) = self.get(index) {
490            return MaybeItem::from_ref(item);
491        }
492        &NONE
493    }
494}
toml_spanner/table.rs

toml_spanner/
table.rs
