Skip to main content

unityrs_core/value/
builder.rs

1//! [`ValueBuilder`]: how a reader makes a [`Parsed`], every allocation
2//! charged before it is made (the module docs of [`crate::value`]).
3//!
4//! Owner: the scaffold (implemented); package B may add methods and fast
5//! paths but not change these signatures.
6
7use std::collections::HashMap;
8use std::sync::Arc;
9
10use super::{Built, ListIx, Map, Parsed, PrimArray, PrimRun, Value};
11use crate::error::{LimitError, LimitKind};
12use crate::limits::{Charge, ChargeError, Meter, MeteredVec, hash_table_cost};
13use crate::typetree::NodeId;
14
15/// Builds one object's value on its input's meter: the reader's only way to
16/// make a [`Parsed`] (plan section 3.10).
17///
18/// Every list, map, tuple and primitive run the reader makes grows in a
19/// [`MeteredVec`] from [`Self::vec`], so its capacity is charged before it
20/// is allocated, and is turned into a [`Built`] here, which carries its
21/// charge into its parent and on into the `Parsed`. The table of node lists
22/// ([`Parsed::lists`]) grows the same way. The builder keeps no value's
23/// charge, so dropping it (a read that failed) leaves nothing uncharged.
24pub struct ValueBuilder {
25    lists: MeteredVec<crate::typetree::SharedNodes>,
26    /// Once there are more than [`SCANNED_LISTS`] lists, each one's index by
27    /// its address ([`Self::list_index`]).
28    by_address: Option<ListTable>,
29}
30
31const _: () = crate::send_sync::<ValueBuilder>();
32
33/// The lists [`ValueBuilder::list_index`] finds by a scan; past them, by
34/// a table.
35const SCANNED_LISTS: usize = 8;
36
37/// Each list's index by its address, charged to the builder's meter before
38/// it grows ([`hash_table_cost`]).
39struct ListTable {
40    index: HashMap<usize, usize>,
41    charge: Charge,
42}
43
44impl ListTable {
45    fn cost(n: usize) -> u64 {
46        hash_table_cost(n, size_of::<(usize, usize)>())
47    }
48}
49
50impl std::fmt::Debug for ValueBuilder {
51    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
52        f.debug_struct("ValueBuilder")
53            .field("lists", &self.lists.len())
54            .finish_non_exhaustive()
55    }
56}
57
58/// Whether `value` itself owns heap (its children aside): a list, map,
59/// tuple or run with an allocation.
60pub(super) fn owns_heap(value: &Value) -> bool {
61    match value {
62        Value::List(v) => v.capacity() > 0,
63        Value::Tuple(v) => !v.is_empty(),
64        Value::Dict(m) => m.entries.capacity() > 0,
65        Value::Prims(PrimArray::U8(_)) => false,
66        Value::Prims(p) => !p.is_empty(),
67        _ => false,
68    }
69}
70
71impl ValueBuilder {
72    /// A builder charging `meter`, whose first node list is `root` (the tree
73    /// the object is read with).
74    pub fn new(
75        meter: &Arc<Meter>,
76        root: crate::typetree::SharedNodes,
77    ) -> Result<Self, ChargeError> {
78        let mut lists = MeteredVec::new(meter);
79        lists.push(root)?;
80        Ok(Self {
81            lists,
82            by_address: None,
83        })
84    }
85
86    /// The meter every allocation of the value is charged to.
87    #[must_use]
88    pub fn meter(&self) -> &Arc<Meter> {
89        self.lists.charge().meter()
90    }
91
92    /// An empty vector on the meter, for a list, a map's entries, a tuple or
93    /// a run.
94    #[must_use]
95    pub fn vec<T>(&self) -> MeteredVec<T> {
96        MeteredVec::new(self.meter())
97    }
98
99    /// The index of `list` in the value's lists, appending it the first time
100    /// (deduplicated by `Arc` pointer: one entry per distinct ref-type tree).
101    /// The first eight are found by a scan, the rest by a table
102    /// from each list's address, so a read of `n` references into `n` ref
103    /// types finds them in steps linear in `n` (claude X, review round 2: a
104    /// scan of every list made it `n`²). The lists' and the table's growth
105    /// are charged; past `u32` it is `LimitKind::Count`.
106    pub fn list_index(
107        &mut self,
108        list: &crate::typetree::SharedNodes,
109    ) -> Result<ListIx, ChargeError> {
110        let addr = triomphe::Arc::as_ptr(list).addr();
111        let found = match &self.by_address {
112            Some(t) => {
113                crate::walk::steps(1);
114                t.index.get(&addr).copied()
115            }
116            None => self.lists.as_slice().iter().position(|l| {
117                crate::walk::steps(1);
118                triomphe::Arc::ptr_eq(l, list)
119            }),
120        };
121        let at = if let Some(at) = found {
122            at
123        } else {
124            self.push_list(list, addr)?
125        };
126        ListIx::try_from(at).map_err(|_| {
127            ChargeError::Limit(LimitError::refused(
128                LimitKind::Count,
129                u64::try_from(at).unwrap_or(u64::MAX),
130                u64::from(ListIx::MAX),
131            ))
132        })
133    }
134
135    /// Appends `list`, at `addr`, to the lists and to their table (built
136    /// once they pass [`SCANNED_LISTS`]), the table charged before it
137    /// grows, so a refusal leaves the two as they were.
138    fn push_list(
139        &mut self,
140        list: &crate::typetree::SharedNodes,
141        addr: usize,
142    ) -> Result<usize, ChargeError> {
143        let at = self.lists.len();
144        let n = at + 1;
145        match &mut self.by_address {
146            Some(t) => t
147                .charge
148                .grow(ListTable::cost(n).saturating_sub(ListTable::cost(n - 1)))?,
149            None if n > SCANNED_LISTS => {
150                let charge = self.meter().charge(ListTable::cost(n))?;
151                let mut index = HashMap::with_capacity(n);
152                for (i, l) in self.lists.as_slice().iter().enumerate() {
153                    crate::walk::steps(1);
154                    index.insert(triomphe::Arc::as_ptr(l).addr(), i);
155                }
156                self.by_address = Some(ListTable { index, charge });
157            }
158            None => {}
159        }
160        self.lists.push(list.clone())?;
161        if let Some(t) = &mut self.by_address {
162            t.index.insert(addr, at);
163        }
164        Ok(at)
165    }
166
167    /// A value that owns no heap of its own (a scalar, a string or bytes
168    /// sliced from a charged buffer, an empty list or map), as a [`Built`]
169    /// with an empty charge; a list, map, tuple or run that owns an
170    /// allocation is handed back, since only the builder's own methods know
171    /// what it was charged. A `Str` or `Bytes` is taken as it is: it must be
172    /// a slice of a charged buffer (the file's, [`crate::RawStr::charged`],
173    /// a decoded block's), never one made from a `Vec` no meter charged,
174    /// which this cannot see (module docs).
175    pub fn scalar(&self, value: Value) -> Result<Built, Value> {
176        if owns_heap(&value) {
177            return Err(value);
178        }
179        Ok(Built {
180            value,
181            charge: Charge::zero(self.meter()),
182        })
183    }
184
185    /// A `List` of `items`, with their vector's charge.
186    #[must_use]
187    pub fn list(&self, items: MeteredVec<Value>) -> Built {
188        let (items, charge) = items.into_parts();
189        Built {
190            value: Value::List(items),
191            charge,
192        }
193    }
194
195    /// A `Dict` whose keys name nodes of list `list`, over `entries` with
196    /// distinct keys, with their vector's charge.
197    #[must_use]
198    pub fn map(&self, list: ListIx, entries: MeteredVec<(NodeId, Value)>) -> Built {
199        let (entries, charge) = entries.into_parts();
200        Built {
201            value: Value::Dict(Map { list, entries }),
202            charge,
203        }
204    }
205
206    /// A `Tuple` of `items`, moved into an exact allocation that is charged
207    /// first ([`MeteredVec::into_boxed_slice`]), with its charge.
208    pub fn tuple(&self, items: MeteredVec<Value>) -> Result<Built, ChargeError> {
209        let (items, charge) = items.into_boxed_slice()?;
210        Ok(Built {
211            value: Value::Tuple(items),
212            charge,
213        })
214    }
215
216    /// A `Prims` value of `run`, moved into an exact allocation that is
217    /// charged first, with its charge. (`vector<UInt8>`/`char` is a
218    /// zero-copy slice of the file, [`PrimArray::U8`], through
219    /// [`Self::scalar`].)
220    pub fn prims(&self, run: PrimRun) -> Result<Built, ChargeError> {
221        fn boxed<T>(
222            items: MeteredVec<T>,
223            wrap: fn(Box<[T]>) -> PrimArray,
224        ) -> Result<Built, ChargeError> {
225            let (items, charge) = items.into_boxed_slice()?;
226            Ok(Built {
227                value: Value::Prims(wrap(items)),
228                charge,
229            })
230        }
231        match run {
232            PrimRun::Bool(v) => boxed(v, PrimArray::Bool),
233            PrimRun::I8(v) => boxed(v, PrimArray::I8),
234            PrimRun::U16(v) => boxed(v, PrimArray::U16),
235            PrimRun::I16(v) => boxed(v, PrimArray::I16),
236            PrimRun::U32(v) => boxed(v, PrimArray::U32),
237            PrimRun::I32(v) => boxed(v, PrimArray::I32),
238            PrimRun::U64(v) => boxed(v, PrimArray::U64),
239            PrimRun::I64(v) => boxed(v, PrimArray::I64),
240            PrimRun::F32(v) => boxed(v, PrimArray::F32),
241            PrimRun::F64(v) => boxed(v, PrimArray::F64),
242        }
243    }
244
245    /// The `Parsed`: `value`, where the read ended, the lists, and the
246    /// charges of both; [`super::ReadBy::Boost`]'s, as a caller's value is
247    /// (the pure-Python reader marks its own).
248    #[must_use]
249    pub fn finish(self, value: Built, bytes_read: i64) -> Parsed {
250        let (lists, lists_charge) = self.lists.into_parts();
251        let Built { value, mut charge } = value;
252        charge.absorb(lists_charge);
253        Parsed {
254            lists,
255            value,
256            bytes_read,
257            read_by: super::ReadBy::Boost,
258            charge,
259        }
260    }
261}