style/
piecewise_linear.rs

1/* This Source Code Form is subject to the terms of the Mozilla Public
2 * License, v. 2.0. If a copy of the MPL was not distributed with this
3 * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
4
5//! A piecewise linear function, following CSS linear easing
6use crate::values::computed::Percentage;
7use core::slice::Iter;
8/// draft as in https://github.com/w3c/csswg-drafts/pull/6533.
9use euclid::approxeq::ApproxEq;
10use itertools::Itertools;
11use std::fmt::{self, Write};
12use style_traits::{CssWriter, ToCss};
13
14use crate::values::CSSFloat;
15
16type ValueType = CSSFloat;
17/// a single entry in a piecewise linear function.
18#[allow(missing_docs)]
19#[derive(
20    Clone,
21    Copy,
22    Debug,
23    MallocSizeOf,
24    PartialEq,
25    SpecifiedValueInfo,
26    ToResolvedValue,
27    ToShmem,
28    Serialize,
29    Deserialize,
30)]
31#[repr(C)]
32pub struct PiecewiseLinearFunctionEntry {
33    pub x: ValueType,
34    pub y: ValueType,
35}
36
37impl ToCss for PiecewiseLinearFunctionEntry {
38    fn to_css<W>(&self, dest: &mut CssWriter<W>) -> fmt::Result
39    where
40        W: fmt::Write,
41    {
42        self.y.to_css(dest)?;
43        dest.write_char(' ')?;
44        Percentage(self.x).to_css(dest)
45    }
46}
47
48/// Representation of a piecewise linear function, a series of linear functions.
49#[derive(
50    Default,
51    Clone,
52    Debug,
53    MallocSizeOf,
54    PartialEq,
55    SpecifiedValueInfo,
56    ToResolvedValue,
57    ToCss,
58    ToShmem,
59    Serialize,
60    Deserialize,
61)]
62#[repr(C)]
63#[css(comma)]
64pub struct PiecewiseLinearFunction {
65    #[css(iterable)]
66    #[ignore_malloc_size_of = "Arc"]
67    #[shmem(field_bound)]
68    entries: crate::ArcSlice<PiecewiseLinearFunctionEntry>,
69}
70
71/// Parameters to define one linear stop.
72pub type PiecewiseLinearFunctionBuildParameters = (CSSFloat, Option<CSSFloat>);
73
74impl PiecewiseLinearFunction {
75    /// Interpolate y value given x and two points. The linear function will be rooted at the asymptote.
76    fn interpolate(
77        x: ValueType,
78        prev: PiecewiseLinearFunctionEntry,
79        next: PiecewiseLinearFunctionEntry,
80        asymptote: &PiecewiseLinearFunctionEntry,
81    ) -> ValueType {
82        // Short circuit if the x is on prev or next.
83        // `next` point is preferred as per spec.
84        if x.approx_eq(&next.x) {
85            return next.y;
86        }
87        if x.approx_eq(&prev.x) {
88            return prev.y;
89        }
90        // Avoid division by zero.
91        if prev.x.approx_eq(&next.x) {
92            return next.y;
93        }
94        let slope = (next.y - prev.y) / (next.x - prev.x);
95        return slope * (x - asymptote.x) + asymptote.y;
96    }
97
98    /// Get the y value of the piecewise linear function given the x value, as per
99    /// https://drafts.csswg.org/css-easing-2/#linear-easing-function-output
100    pub fn at(&self, x: ValueType) -> ValueType {
101        if !x.is_finite() {
102            return if x > 0.0 { 1.0 } else { 0.0 };
103        }
104        if self.entries.is_empty() {
105            // Implied y = x, as per spec.
106            return x;
107        }
108        if self.entries.len() == 1 {
109            // Implied y = <constant>, as per spec.
110            return self.entries[0].y;
111        }
112        // Spec dictates the valid input domain is [0, 1]. Outside of this range, the output
113        // should be calculated as if the slopes at start and end extend to infinity. However, if the
114        // start/end have two points of the same position, the line should extend along the x-axis.
115        // The function doesn't have to cover the input domain, in which case the extension logic
116        // applies even if the input falls in the input domain.
117        // Also, we're guaranteed to have at least two elements at this point.
118        if x < self.entries[0].x {
119            return Self::interpolate(x, self.entries[0], self.entries[1], &self.entries[0]);
120        }
121        let mut rev_iter = self.entries.iter().rev();
122        let last = rev_iter.next().unwrap();
123        if x >= last.x {
124            let second_last = rev_iter.next().unwrap();
125            return Self::interpolate(x, *second_last, *last, last);
126        }
127
128        // Now we know the input sits within the domain explicitly defined by our function.
129        for (point_b, point_a) in self.entries.iter().rev().tuple_windows() {
130            // Need to let point A be the _last_ point where its x is less than the input x,
131            // hence the reverse traversal.
132            if x < point_a.x {
133                continue;
134            }
135            return Self::interpolate(x, *point_a, *point_b, point_a);
136        }
137        unreachable!("Input is supposed to be within the entries' min & max!");
138    }
139
140    #[allow(missing_docs)]
141    pub fn iter(&self) -> Iter<PiecewiseLinearFunctionEntry> {
142        self.entries.iter()
143    }
144}
145
146/// Entry of a piecewise linear function while building, where the calculation of x value can be deferred.
147#[derive(Clone, Copy)]
148struct BuildEntry {
149    x: Option<ValueType>,
150    y: ValueType,
151}
152
153/// Builder object to generate a linear function.
154#[derive(Default)]
155pub struct PiecewiseLinearFunctionBuilder {
156    largest_x: Option<ValueType>,
157    smallest_x: Option<ValueType>,
158    entries: Vec<BuildEntry>,
159}
160
161impl PiecewiseLinearFunctionBuilder {
162    /// Create a builder for a known amount of linear stop entries.
163    pub fn with_capacity(len: usize) -> Self {
164        PiecewiseLinearFunctionBuilder {
165            largest_x: None,
166            smallest_x: None,
167            entries: Vec::with_capacity(len),
168        }
169    }
170
171    fn create_entry(&mut self, y: ValueType, x: Option<ValueType>) {
172        let x = match x {
173            Some(x) if x.is_finite() => x,
174            _ if self.entries.is_empty() => 0.0, // First x is 0 if not specified (Or not finite)
175            _ => {
176                self.entries.push(BuildEntry { x: None, y });
177                return;
178            },
179        };
180        // Specified x value cannot regress, as per spec.
181        let x = match self.largest_x {
182            Some(largest_x) => x.max(largest_x),
183            None => x,
184        };
185        self.largest_x = Some(x);
186        // Whatever we see the earliest is the smallest value.
187        if self.smallest_x.is_none() {
188            self.smallest_x = Some(x);
189        }
190        self.entries.push(BuildEntry { x: Some(x), y });
191    }
192
193    /// Add a new entry into the piecewise linear function with specified y value.
194    /// If the start x value is given, that is where the x value will be. Otherwise,
195    /// the x value is calculated later. If the end x value is specified, a flat segment
196    /// is generated. If start x value is not specified but end x is, it is treated as
197    /// start x.
198    pub fn push(&mut self, y: CSSFloat, x_start: Option<CSSFloat>) {
199        self.create_entry(y, x_start)
200    }
201
202    /// Finish building the piecewise linear function by resolving all undefined x values,
203    /// then return the result.
204    pub fn build(mut self) -> PiecewiseLinearFunction {
205        if self.entries.is_empty() {
206            return PiecewiseLinearFunction::default();
207        }
208        if self.entries.len() == 1 {
209            // Don't bother resolving anything.
210            return PiecewiseLinearFunction {
211                entries: crate::ArcSlice::from_iter(std::iter::once(
212                    PiecewiseLinearFunctionEntry {
213                        x: 0.,
214                        y: self.entries[0].y,
215                    },
216                )),
217            };
218        }
219        // Guaranteed at least two elements.
220        // Start element's x value should've been assigned when the first value was pushed.
221        debug_assert!(
222            self.entries[0].x.is_some(),
223            "Expected an entry with x defined!"
224        );
225        // Spec asserts that if the last entry does not have an x value, it is assigned the largest seen x value.
226        self.entries
227            .last_mut()
228            .unwrap()
229            .x
230            .get_or_insert(self.largest_x.filter(|x| x > &1.0).unwrap_or(1.0));
231        // Now we have at least two elements with x values, with start & end x values guaranteed.
232
233        let mut result = Vec::with_capacity(self.entries.len());
234        result.push(PiecewiseLinearFunctionEntry {
235            x: self.entries[0].x.unwrap(),
236            y: self.entries[0].y,
237        });
238        for (i, e) in self.entries.iter().enumerate().skip(1) {
239            if e.x.is_none() {
240                // Need to calculate x values by first finding an entry with the first
241                // defined x value (Guaranteed to exist as the list end has it defined).
242                continue;
243            }
244            // x is defined for this element.
245            let divisor = i - result.len() + 1;
246            // Any element(s) with undefined x to assign?
247            if divisor != 1 {
248                // Have at least one element in result at all times.
249                let start_x = result.last().unwrap().x;
250                let increment = (e.x.unwrap() - start_x) / divisor as ValueType;
251                // Grab every element with undefined x to this point, which starts at the end of the result
252                // array, and ending right before the current index. Then, assigned the evenly divided
253                // x values.
254                result.extend(
255                    self.entries[result.len()..i]
256                        .iter()
257                        .enumerate()
258                        .map(|(j, e)| {
259                            debug_assert!(e.x.is_none(), "Expected an entry with x undefined!");
260                            PiecewiseLinearFunctionEntry {
261                                x: increment * (j + 1) as ValueType + start_x,
262                                y: e.y,
263                            }
264                        }),
265                );
266            }
267            result.push(PiecewiseLinearFunctionEntry {
268                x: e.x.unwrap(),
269                y: e.y,
270            });
271        }
272        debug_assert_eq!(
273            result.len(),
274            self.entries.len(),
275            "Should've mapped one-to-one!"
276        );
277        PiecewiseLinearFunction {
278            entries: crate::ArcSlice::from_iter(result.into_iter()),
279        }
280    }
281}
style/piecewise_linear.rs

style/
piecewise_linear.rs
