implicit_predicates_core/scratch/
mod.rs

1//! A bump arena for expansion arithmetic.
2//!
3//! A [`Scratch`] arena hands out the memory for the expansions that a
4//! computation builds step by step. Its memory is a buffer the caller lends
5//! it ([`Scratch::borrowed`]), so nothing allocates. With the `alloc` feature
6//! an arena can instead own its memory and grow on the heap
7//! (`Scratch::growable`).
8//!
9//! # Model
10//!
11//! - **Bump allocation.** The arena keeps a *top*: the buffer below it is in
12//!   use, the rest is free. Each operation writes its result just above the
13//!   top and raises the top by the length of that result.
14//! - **Spans are indices.** Operations take and return [`Span`]s, positions
15//!   in the arena rather than references to it, so a computation can hold
16//!   many results while it keeps calling `&mut self` operations. Read the
17//!   components of a span with [`Scratch::get`]; write an expansion computed
18//!   elsewhere with [`Scratch::write`].
19//! - **Marks and reset.** [`Scratch::mark`] records the current top and
20//!   [`Scratch::reset`] lowers the top back to a mark, releasing at once
21//!   every result built since. Spans created before the mark stay valid.
22//! - **Exhaustion.** Before it writes, an operation reserves all the space
23//!   it may need above the top: the longest result it can produce (the
24//!   capacity documented by the slice primitive in [`expansion`]), plus, for
25//!   [`Scratch::product`], room for its intermediate expansions. If that does
26//!   not fit, the operation returns [`ScratchExhausted`] and leaves the arena
27//!   unchanged. [`Scratch::high_water`] tells how much of the buffer a
28//!   computation needed, which is how to size the buffer.
29//!
30//! An arena uses at most `u32::MAX` components of its buffer. An arena that
31//! grows fails with [`ScratchExhausted`] only when an operation needs more
32//! than that.
33//!
34//! A span means something only to the arena that created it, and only while
35//! the top stays above it. Using a span after a [`reset`](Scratch::reset)
36//! past its start, or with another arena, is a logic error: debug builds
37//! detect it when the span reaches past the top, and the result is otherwise
38//! unspecified (a panic or unrelated components), but never undefined
39//! behavior.
40//!
41//! # Examples
42//!
43//! ```
44//! use implicit_predicates_core::{Scratch, Sign};
45//!
46//! let mut buf = [0.0; 16];
47//! let mut scratch = Scratch::borrowed(&mut buf);
48//! let a = scratch.push(&[1e-20, 1.0])?;
49//! let b = scratch.push(&[3.0])?;
50//!
51//! let mark = scratch.mark();
52//! let sum = scratch.sum(a, b)?; // 1 + 3 + 1e-20
53//! let scaled = scratch.scale(sum, -2.0)?;
54//! assert_eq!(scratch.get(scaled), &[-2e-20, -8.0]);
55//! assert_eq!(scratch.sign(scaled), Sign::Negative);
56//!
57//! // Release `sum` and `scaled`; `a` and `b` stay valid.
58//! scratch.reset(mark);
59//! assert_eq!(scratch.used(), 3);
60//! assert_eq!(scratch.get(a), &[1e-20, 1.0]);
61//! # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
62//! ```
63
64mod error;
65#[cfg(feature = "alloc")]
66mod growable;
67mod product;
68mod reservation;
69mod span;
70mod storage;
71mod write;
72
73pub use error::ScratchExhausted;
74pub use span::{Mark, Span};
75
76use core::fmt;
77
78use crate::{Sign, expansion};
79use span::to_index;
80use storage::Storage;
81
82/// A bump arena of `f64` components for expansion arithmetic. See the
83/// [module documentation](self) for the model.
84pub struct Scratch<'a> {
85    storage: Storage<'a>,
86    /// The top: components `..used` are in use.
87    used: u32,
88    /// The highest the top has been, counting worst-case reservations.
89    high_water: u32,
90}
91
92impl<'a> Scratch<'a> {
93    /// Creates an empty arena over `buf`, of which it uses at most
94    /// `u32::MAX` components. The initial contents of `buf` do not matter.
95    ///
96    /// # Examples
97    ///
98    /// ```
99    /// use implicit_predicates_core::Scratch;
100    ///
101    /// let mut buf = [0.0; 64];
102    /// let scratch = Scratch::borrowed(&mut buf);
103    /// assert_eq!(scratch.capacity(), 64);
104    /// assert_eq!(scratch.used(), 0);
105    /// ```
106    #[must_use]
107    pub fn borrowed(buf: &'a mut [f64]) -> Scratch<'a> {
108        Scratch {
109            storage: Storage::Borrowed(buf),
110            used: 0,
111            high_water: 0,
112        }
113    }
114
115    /// Returns a mark of the current top, to return to with
116    /// [`reset`](Self::reset).
117    ///
118    /// # Examples
119    ///
120    /// ```
121    /// use implicit_predicates_core::Scratch;
122    ///
123    /// let mut buf = [0.0; 4];
124    /// let mut scratch = Scratch::borrowed(&mut buf);
125    /// scratch.push(&[1.0])?;
126    /// let mark = scratch.mark();
127    /// scratch.push(&[2.0])?;
128    /// scratch.reset(mark);
129    /// assert_eq!(scratch.used(), 1);
130    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
131    /// ```
132    #[must_use]
133    pub fn mark(&self) -> Mark {
134        Mark(self.used)
135    }
136
137    /// Lowers the top to the mark `m`, releasing every span created since
138    /// `m` was taken. [`high_water`](Self::high_water) is unchanged.
139    ///
140    /// `m` must not be above the current top, which happens when a reset
141    /// to an earlier mark came in between. That is a logic error: debug
142    /// builds panic, release builds leave the top unchanged.
143    ///
144    /// # Examples
145    ///
146    /// ```
147    /// use implicit_predicates_core::Scratch;
148    ///
149    /// let mut buf = [0.0; 4];
150    /// let mut scratch = Scratch::borrowed(&mut buf);
151    /// let mark = scratch.mark();
152    /// scratch.push(&[1e-20, 1.0])?;
153    /// scratch.reset(mark);
154    /// assert_eq!(scratch.used(), 0);
155    /// assert_eq!(scratch.high_water(), 2);
156    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
157    /// ```
158    pub fn reset(&mut self, m: Mark) {
159        debug_assert!(
160            m.0 <= self.used,
161            "reset to a mark at {} above the top at {}",
162            m.0,
163            self.used
164        );
165        self.used = self.used.min(m.0);
166    }
167
168    /// Returns the components of the expansion at `s`.
169    ///
170    /// Debug builds panic if `s` reaches past the top; see the
171    /// [module documentation](self) for spans that are no longer valid.
172    ///
173    /// # Examples
174    ///
175    /// ```
176    /// use implicit_predicates_core::Scratch;
177    ///
178    /// let mut buf = [0.0; 4];
179    /// let mut scratch = Scratch::borrowed(&mut buf);
180    /// let s = scratch.push(&[1e-20, 1.0])?;
181    /// assert_eq!(scratch.get(s), &[1e-20, 1.0]);
182    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
183    /// ```
184    #[must_use]
185    pub fn get(&self, s: Span) -> &[f64] {
186        self.debug_check(s);
187        &self.storage.as_slice()[..self.used()][s.range()]
188    }
189
190    /// Returns the number of components in use, below the top.
191    ///
192    /// # Examples
193    ///
194    /// ```
195    /// use implicit_predicates_core::Scratch;
196    ///
197    /// let mut buf = [0.0; 4];
198    /// let mut scratch = Scratch::borrowed(&mut buf);
199    /// scratch.push(&[1e-20, 1.0])?;
200    /// assert_eq!(scratch.used(), 2);
201    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
202    /// ```
203    #[must_use]
204    pub fn used(&self) -> usize {
205        to_index(self.used)
206    }
207
208    /// Returns the number of components the arena can hold: the length of
209    /// its buffer, or `u32::MAX` if the buffer is longer.
210    ///
211    /// # Examples
212    ///
213    /// ```
214    /// use implicit_predicates_core::Scratch;
215    ///
216    /// let mut buf = [0.0; 8];
217    /// assert_eq!(Scratch::borrowed(&mut buf).capacity(), 8);
218    /// ```
219    #[must_use]
220    pub fn capacity(&self) -> usize {
221        to_index(self.storage.capacity())
222    }
223
224    /// Returns the highest [`used`](Self::used) ever reached, counting the
225    /// space each successful operation reserves while it works, even when
226    /// its result turns out shorter. A buffer this long is enough
227    /// to repeat the same computation. Failed operations reserve nothing.
228    ///
229    /// # Examples
230    ///
231    /// ```
232    /// use implicit_predicates_core::Scratch;
233    ///
234    /// let mut buf = [0.0; 8];
235    /// let mut scratch = Scratch::borrowed(&mut buf);
236    /// let a = scratch.push(&[1e-20, 1.0])?;
237    /// let zero = scratch.diff(a, a)?; // reserves 4 components, keeps none
238    /// assert!(zero.is_empty());
239    /// assert_eq!(scratch.used(), 2);
240    /// assert_eq!(scratch.high_water(), 6);
241    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
242    /// ```
243    #[must_use]
244    pub fn high_water(&self) -> usize {
245        to_index(self.high_water)
246    }
247
248    /// Copies the expansion `e` into the arena and returns its span.
249    ///
250    /// Needs `e.len()` free components; an empty `e` always succeeds, giving
251    /// an empty span. Requirement: `e` is a valid expansion (see
252    /// [`expansion`]); it is copied as is, and debug builds panic if it is
253    /// not valid.
254    ///
255    /// # Errors
256    ///
257    /// [`ScratchExhausted`] if `e` does not fit; the arena is unchanged.
258    ///
259    /// # Examples
260    ///
261    /// ```
262    /// use implicit_predicates_core::Scratch;
263    ///
264    /// let mut buf = [0.0; 2];
265    /// let mut scratch = Scratch::borrowed(&mut buf);
266    /// let s = scratch.push(&[1e-20, 1.0])?;
267    /// assert_eq!(scratch.get(s), &[1e-20, 1.0]);
268    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
269    /// ```
270    pub fn push(&mut self, e: &[f64]) -> Result<Span, ScratchExhausted> {
271        debug_assert!(
272            expansion::is_valid(e),
273            "Scratch::push of {e:?}, which is not a valid expansion"
274        );
275        let worst_case = u64::try_from(e.len()).unwrap_or(u64::MAX);
276        self.write_result([], worst_case, |[], out| {
277            out.copy_from_slice(e);
278            e.len()
279        })
280    }
281
282    /// Writes the expansion of `a + b` and returns its span, as
283    /// [`expansion::sum`] does.
284    ///
285    /// Needs `a.len() + b.len()` free components while it works.
286    ///
287    /// # Errors
288    ///
289    /// [`ScratchExhausted`] if that space is not free; the arena is
290    /// unchanged.
291    ///
292    /// # Examples
293    ///
294    /// ```
295    /// use implicit_predicates_core::Scratch;
296    ///
297    /// let mut buf = [0.0; 8];
298    /// let mut scratch = Scratch::borrowed(&mut buf);
299    /// let a = scratch.push(&[1e-20, 1.0])?;
300    /// let b = scratch.push(&[-1e-20, 2.0])?;
301    /// let s = scratch.sum(a, b)?;
302    /// assert_eq!(scratch.get(s), &[3.0]);
303    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
304    /// ```
305    pub fn sum(&mut self, a: Span, b: Span) -> Result<Span, ScratchExhausted> {
306        let worst_case = u64::from(a.len) + u64::from(b.len);
307        self.write_result([a, b], worst_case, |[a, b], out| expansion::sum(a, b, out))
308    }
309
310    /// Writes the expansion of `a - b` and returns its span, as
311    /// [`expansion::diff`] does.
312    ///
313    /// Needs `a.len() + b.len()` free components while it works.
314    ///
315    /// # Errors
316    ///
317    /// [`ScratchExhausted`] if that space is not free; the arena is
318    /// unchanged.
319    ///
320    /// # Examples
321    ///
322    /// ```
323    /// use implicit_predicates_core::Scratch;
324    ///
325    /// let mut buf = [0.0; 8];
326    /// let mut scratch = Scratch::borrowed(&mut buf);
327    /// let a = scratch.push(&[1e-20, 1.0])?;
328    /// let b = scratch.push(&[1e-20, 2.0])?;
329    /// let d = scratch.diff(a, b)?;
330    /// assert_eq!(scratch.get(d), &[-1.0]);
331    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
332    /// ```
333    pub fn diff(&mut self, a: Span, b: Span) -> Result<Span, ScratchExhausted> {
334        let worst_case = u64::from(a.len) + u64::from(b.len);
335        self.write_result([a, b], worst_case, |[a, b], out| expansion::diff(a, b, out))
336    }
337
338    /// Writes the expansion of `a * b` and returns its span, as
339    /// [`expansion::scale`] does, with the same requirements on the
340    /// magnitudes.
341    ///
342    /// Needs `2 * a.len()` free components while it works.
343    ///
344    /// # Errors
345    ///
346    /// [`ScratchExhausted`] if that space is not free; the arena is
347    /// unchanged.
348    ///
349    /// # Examples
350    ///
351    /// ```
352    /// use implicit_predicates_core::Scratch;
353    ///
354    /// let mut buf = [0.0; 8];
355    /// let mut scratch = Scratch::borrowed(&mut buf);
356    /// let a = scratch.push(&[0.25, 4.0])?;
357    /// let s = scratch.scale(a, 3.0)?;
358    /// assert_eq!(scratch.get(s), &[12.75]);
359    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
360    /// ```
361    pub fn scale(&mut self, a: Span, b: f64) -> Result<Span, ScratchExhausted> {
362        let worst_case = 2 * u64::from(a.len);
363        self.write_result([a], worst_case, |[a], out| expansion::scale(a, b, out))
364    }
365
366    /// Returns the exact sign of the expansion at `a`, as
367    /// [`expansion::sign`] does.
368    ///
369    /// # Examples
370    ///
371    /// ```
372    /// use implicit_predicates_core::{Scratch, Sign};
373    ///
374    /// let mut buf = [0.0; 2];
375    /// let mut scratch = Scratch::borrowed(&mut buf);
376    /// let a = scratch.push(&[1e-20, -1.0])?;
377    /// assert_eq!(scratch.sign(a), Sign::Negative);
378    /// # Ok::<(), implicit_predicates_core::ScratchExhausted>(())
379    /// ```
380    #[must_use]
381    pub fn sign(&self, a: Span) -> Sign {
382        expansion::sign(self.get(a))
383    }
384}
385
386/// Shows the accounting of the arena, not its contents.
387impl fmt::Debug for Scratch<'_> {
388    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
389        f.debug_struct("Scratch")
390            .field("used", &self.used)
391            .field("capacity", &self.storage.capacity())
392            .field("high_water", &self.high_water)
393            .finish()
394    }
395}
implicit_predicates_core/scratch/mod.rs

implicit_predicates_core/scratch/
mod.rs
