implicit_predicates_core/point.rs
1//! The contract every point type implements, explicit or implicit.
2//!
3//! A predicate reads a point twice. Its fast path, the floating-point
4//! filter, uses [`Point::approx`], an approximation of the coordinates, and
5//! [`Point::err`], a bound on the error of each one. Only when the filter
6//! cannot decide does it ask for [`Point::exact`], the coordinates as
7//! expansions in a [`Scratch`] arena, in homogeneous form.
8//!
9//! `[f64; 3]` implements the contract as an explicit point: its components
10//! are its exact coordinates, with no error.
11
12use core::fmt;
13
14use crate::expansion;
15use crate::scratch::{Scratch, ScratchExhausted, Span};
16
17/// A point in three dimensions, as the predicates read it.
18///
19/// Implementations must uphold, for each axis `k`:
20///
21/// - `err()[k]` is not negative (it may be `+∞`) and bounds the distance
22/// between `approx()[k]` and coordinate `k` of the point, `x_k / w`,
23/// where `x_k` is the numerator and `w` the weight that
24/// [`exact`](Self::exact) writes (`x_k` itself when `w` is
25/// [`Weight::One`]);
26/// - `err()[k]` is zero only when `approx()[k]` is that coordinate;
27/// - [`is_explicit`](Self::is_explicit) returns `true` only if `approx()`
28/// holds the exact coordinates, `err()` is zero on every axis and
29/// [`exact`](Self::exact) gives [`Weight::One`]: for such points the
30/// predicates use `approx()` alone, with no uncertainty;
31/// - every span of the [`ExactCoords`] that [`exact`](Self::exact) returns
32/// holds a valid expansion (see [`expansion`]: nonzero components of
33/// strictly increasing magnitude that do not overlap), written in the
34/// arena it was given;
35/// - [`exact`](Self::exact) leaves the arena below the top it had when
36/// `exact` was called as it was: it writes only above that top and never
37/// resets the arena to a mark taken before the call, since a predicate
38/// keeps the exact coordinates of the points it read before there;
39/// - while a predicate runs, which may call each method more than once,
40/// [`approx`](Self::approx), [`err`](Self::err) and
41/// [`is_explicit`](Self::is_explicit) give the same answer every time and
42/// [`exact`](Self::exact) the same coordinates: a type with interior
43/// mutability must not change them in the middle of a call.
44///
45/// A predicate given a point that breaks this contract can return a wrong
46/// sign: predicates do not check it.
47///
48/// # Examples
49///
50/// ```
51/// use implicit_predicates_core::{Point, Scratch, Weight};
52///
53/// let p = [1.5, 0.0, -2.0];
54/// assert!(p.is_explicit());
55/// assert_eq!(p.err(), &[0.0; 3]);
56///
57/// let mut buf = [0.0; 3];
58/// let mut scratch = Scratch::borrowed(&mut buf);
59/// let exact = p.exact(&mut scratch)?;
60/// assert_eq!(scratch.get(exact.x), &[1.5]);
61/// assert!(exact.y.is_empty()); // zero
62/// assert_eq!(exact.w, Weight::One);
63/// # Ok::<(), implicit_predicates_core::ExactError>(())
64/// ```
65pub trait Point {
66 /// Returns an approximation of the coordinates.
67 fn approx(&self) -> &[f64; 3];
68
69 /// Returns, per coordinate, a bound on the error of
70 /// [`approx`](Self::approx).
71 fn err(&self) -> &[f64; 3];
72
73 /// Whether the point is explicit. It may return `true` only if
74 /// [`approx`](Self::approx) holds the exact coordinates, every
75 /// [`err`](Self::err) is zero and [`exact`](Self::exact) gives
76 /// [`Weight::One`]; returning `false` is always allowed. A wrong `true`
77 /// makes the predicates return wrong signs, unchecked.
78 fn is_explicit(&self) -> bool;
79
80 /// Writes the exact coordinates as expansions in `scratch`: the point is
81 /// `(x / w, y / w, z / w)`. Every span returned must hold a valid
82 /// expansion of `scratch` (see [`expansion`]); predicates rely on it
83 /// without checking it.
84 ///
85 /// # Errors
86 ///
87 /// - [`ExactError::Exhausted`] if `scratch` runs out of room;
88 /// - [`ExactError::OutOfRange`] if the inputs of the point lie outside
89 /// the range in which its exact coordinates can be computed: they are
90 /// not finite, or a product they need leaves the product domain of
91 /// [`eft`](crate::eft).
92 ///
93 /// After an error, `scratch` may hold partial results above the top it
94 /// had before the call; resetting to a mark taken before the call
95 /// releases them.
96 fn exact(&self, scratch: &mut Scratch<'_>) -> Result<ExactCoords, ExactError>;
97}
98
99/// The exact coordinates of a point, in homogeneous form: the point is
100/// `(x / w, y / w, z / w)`. The spans belong to the arena given to
101/// [`Point::exact`], and each holds a valid expansion (see [`expansion`]);
102/// the predicates that read them do not check it.
103#[derive(Clone, Copy, Debug, PartialEq, Eq)]
104pub struct ExactCoords {
105 /// The numerator of the first coordinate.
106 pub x: Span,
107 /// The numerator of the second coordinate.
108 pub y: Span,
109 /// The numerator of the third coordinate.
110 pub z: Span,
111 /// The common denominator.
112 pub w: Weight,
113}
114
115/// The common denominator of the exact coordinates of a point.
116#[derive(Clone, Copy, Debug, PartialEq, Eq)]
117pub enum Weight {
118 /// The denominator is one: the numerators are the coordinates.
119 One,
120 /// The denominator is the expansion at this span. The predicates of the
121 /// `implicit-predicates` crate do not support it yet: they return `None`
122 /// for a point whose exact coordinates have it.
123 Expansion(Span),
124}
125
126/// The error of [`Point::exact`].
127#[derive(Clone, Copy, Debug, PartialEq, Eq)]
128pub enum ExactError {
129 /// The arena ran out of room.
130 Exhausted(ScratchExhausted),
131 /// The inputs of the point lie outside the range of the exact
132 /// arithmetic.
133 OutOfRange,
134}
135
136impl From<ScratchExhausted> for ExactError {
137 fn from(e: ScratchExhausted) -> Self {
138 ExactError::Exhausted(e)
139 }
140}
141
142impl fmt::Display for ExactError {
143 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
144 match self {
145 ExactError::Exhausted(e) => e.fmt(f),
146 ExactError::OutOfRange => {
147 f.write_str("point outside the range of the exact arithmetic")
148 }
149 }
150 }
151}
152
153impl core::error::Error for ExactError {
154 fn source(&self) -> Option<&(dyn core::error::Error + 'static)> {
155 match self {
156 ExactError::Exhausted(e) => Some(e),
157 ExactError::OutOfRange => None,
158 }
159 }
160}
161
162/// An explicit point, not validated: its components are its exact
163/// coordinates. A component that is not finite makes
164/// [`exact`](Point::exact) fail with [`ExactError::OutOfRange`].
165impl Point for [f64; 3] {
166 #[inline]
167 fn approx(&self) -> &[f64; 3] {
168 self
169 }
170
171 #[inline]
172 fn err(&self) -> &[f64; 3] {
173 &[0.0; 3]
174 }
175
176 #[inline]
177 fn is_explicit(&self) -> bool {
178 true
179 }
180
181 /// Writes each coordinate as an expansion of one component, or none for
182 /// zero, with [`Weight::One`]. Needs up to 3 free components; on an
183 /// error the arena is unchanged.
184 fn exact(&self, scratch: &mut Scratch<'_>) -> Result<ExactCoords, ExactError> {
185 if !self.iter().all(|c| c.is_finite()) {
186 return Err(ExactError::OutOfRange);
187 }
188 let mark = scratch.mark();
189 let mut write = |c: f64| {
190 scratch
191 .write(1, |out| expansion::from_f64(c, out))
192 .inspect_err(|_| scratch.reset(mark))
193 };
194 Ok(ExactCoords {
195 x: write(self[0])?,
196 y: write(self[1])?,
197 z: write(self[2])?,
198 w: Weight::One,
199 })
200 }
201}