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

implicit_predicates_core/scratch/
mod.rs
