summaryrefslogtreecommitdiffstats
path: root/servo/components/style/piecewise_linear.rs
diff options
context:
space:
mode:
Diffstat (limited to 'servo/components/style/piecewise_linear.rs')
-rw-r--r--servo/components/style/piecewise_linear.rs281
1 files changed, 281 insertions, 0 deletions
diff --git a/servo/components/style/piecewise_linear.rs b/servo/components/style/piecewise_linear.rs
new file mode 100644
index 0000000000..1cabd01ea1
--- /dev/null
+++ b/servo/components/style/piecewise_linear.rs
@@ -0,0 +1,281 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at https://mozilla.org/MPL/2.0/. */
+
+//! A piecewise linear function, following CSS linear easing
+use crate::values::computed::Percentage;
+use core::slice::Iter;
+/// draft as in https://github.com/w3c/csswg-drafts/pull/6533.
+use euclid::approxeq::ApproxEq;
+use itertools::Itertools;
+use std::fmt::{self, Write};
+use style_traits::{CssWriter, ToCss};
+
+use crate::values::CSSFloat;
+
+type ValueType = CSSFloat;
+/// a single entry in a piecewise linear function.
+#[allow(missing_docs)]
+#[derive(
+ Clone,
+ Copy,
+ Debug,
+ MallocSizeOf,
+ PartialEq,
+ SpecifiedValueInfo,
+ ToResolvedValue,
+ ToShmem,
+ Serialize,
+ Deserialize,
+)]
+#[repr(C)]
+pub struct PiecewiseLinearFunctionEntry {
+ pub x: ValueType,
+ pub y: ValueType,
+}
+
+impl ToCss for PiecewiseLinearFunctionEntry {
+ fn to_css<W>(&self, dest: &mut CssWriter<W>) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ self.y.to_css(dest)?;
+ dest.write_char(' ')?;
+ Percentage(self.x).to_css(dest)
+ }
+}
+
+/// Representation of a piecewise linear function, a series of linear functions.
+#[derive(
+ Default,
+ Clone,
+ Debug,
+ MallocSizeOf,
+ PartialEq,
+ SpecifiedValueInfo,
+ ToResolvedValue,
+ ToCss,
+ ToShmem,
+ Serialize,
+ Deserialize,
+)]
+#[repr(C)]
+#[css(comma)]
+pub struct PiecewiseLinearFunction {
+ #[css(iterable)]
+ #[ignore_malloc_size_of = "Arc"]
+ #[shmem(field_bound)]
+ entries: crate::ArcSlice<PiecewiseLinearFunctionEntry>,
+}
+
+/// Parameters to define one linear stop.
+pub type PiecewiseLinearFunctionBuildParameters = (CSSFloat, Option<CSSFloat>);
+
+impl PiecewiseLinearFunction {
+ /// Interpolate y value given x and two points. The linear function will be rooted at the asymptote.
+ fn interpolate(
+ x: ValueType,
+ prev: PiecewiseLinearFunctionEntry,
+ next: PiecewiseLinearFunctionEntry,
+ asymptote: &PiecewiseLinearFunctionEntry,
+ ) -> ValueType {
+ // Short circuit if the x is on prev or next.
+ // `next` point is preferred as per spec.
+ if x.approx_eq(&next.x) {
+ return next.y;
+ }
+ if x.approx_eq(&prev.x) {
+ return prev.y;
+ }
+ // Avoid division by zero.
+ if prev.x.approx_eq(&next.x) {
+ return next.y;
+ }
+ let slope = (next.y - prev.y) / (next.x - prev.x);
+ return slope * (x - asymptote.x) + asymptote.y;
+ }
+
+ /// Get the y value of the piecewise linear function given the x value, as per
+ /// https://drafts.csswg.org/css-easing-2/#linear-easing-function-output
+ pub fn at(&self, x: ValueType) -> ValueType {
+ if !x.is_finite() {
+ return if x > 0.0 { 1.0 } else { 0.0 };
+ }
+ if self.entries.is_empty() {
+ // Implied y = x, as per spec.
+ return x;
+ }
+ if self.entries.len() == 1 {
+ // Implied y = <constant>, as per spec.
+ return self.entries[0].y;
+ }
+ // Spec dictates the valid input domain is [0, 1]. Outside of this range, the output
+ // should be calculated as if the slopes at start and end extend to infinity. However, if the
+ // start/end have two points of the same position, the line should extend along the x-axis.
+ // The function doesn't have to cover the input domain, in which case the extension logic
+ // applies even if the input falls in the input domain.
+ // Also, we're guaranteed to have at least two elements at this point.
+ if x < self.entries[0].x {
+ return Self::interpolate(x, self.entries[0], self.entries[1], &self.entries[0]);
+ }
+ let mut rev_iter = self.entries.iter().rev();
+ let last = rev_iter.next().unwrap();
+ if x >= last.x {
+ let second_last = rev_iter.next().unwrap();
+ return Self::interpolate(x, *second_last, *last, last);
+ }
+
+ // Now we know the input sits within the domain explicitly defined by our function.
+ for (point_b, point_a) in self.entries.iter().rev().tuple_windows() {
+ // Need to let point A be the _last_ point where its x is less than the input x,
+ // hence the reverse traversal.
+ if x < point_a.x {
+ continue;
+ }
+ return Self::interpolate(x, *point_a, *point_b, point_a);
+ }
+ unreachable!("Input is supposed to be within the entries' min & max!");
+ }
+
+ #[allow(missing_docs)]
+ pub fn iter(&self) -> Iter<PiecewiseLinearFunctionEntry> {
+ self.entries.iter()
+ }
+}
+
+/// Entry of a piecewise linear function while building, where the calculation of x value can be deferred.
+#[derive(Clone, Copy)]
+struct BuildEntry {
+ x: Option<ValueType>,
+ y: ValueType,
+}
+
+/// Builder object to generate a linear function.
+#[derive(Default)]
+pub struct PiecewiseLinearFunctionBuilder {
+ largest_x: Option<ValueType>,
+ smallest_x: Option<ValueType>,
+ entries: Vec<BuildEntry>,
+}
+
+impl PiecewiseLinearFunctionBuilder {
+ /// Create a builder for a known amount of linear stop entries.
+ pub fn with_capacity(len: usize) -> Self {
+ PiecewiseLinearFunctionBuilder {
+ largest_x: None,
+ smallest_x: None,
+ entries: Vec::with_capacity(len),
+ }
+ }
+
+ fn create_entry(&mut self, y: ValueType, x: Option<ValueType>) {
+ let x = match x {
+ Some(x) if x.is_finite() => x,
+ _ if self.entries.is_empty() => 0.0, // First x is 0 if not specified (Or not finite)
+ _ => {
+ self.entries.push(BuildEntry { x: None, y });
+ return;
+ },
+ };
+ // Specified x value cannot regress, as per spec.
+ let x = match self.largest_x {
+ Some(largest_x) => x.max(largest_x),
+ None => x,
+ };
+ self.largest_x = Some(x);
+ // Whatever we see the earliest is the smallest value.
+ if self.smallest_x.is_none() {
+ self.smallest_x = Some(x);
+ }
+ self.entries.push(BuildEntry { x: Some(x), y });
+ }
+
+ /// Add a new entry into the piecewise linear function with specified y value.
+ /// If the start x value is given, that is where the x value will be. Otherwise,
+ /// the x value is calculated later. If the end x value is specified, a flat segment
+ /// is generated. If start x value is not specified but end x is, it is treated as
+ /// start x.
+ pub fn push(&mut self, y: CSSFloat, x_start: Option<CSSFloat>) {
+ self.create_entry(y, x_start)
+ }
+
+ /// Finish building the piecewise linear function by resolving all undefined x values,
+ /// then return the result.
+ pub fn build(mut self) -> PiecewiseLinearFunction {
+ if self.entries.is_empty() {
+ return PiecewiseLinearFunction::default();
+ }
+ if self.entries.len() == 1 {
+ // Don't bother resolving anything.
+ return PiecewiseLinearFunction {
+ entries: crate::ArcSlice::from_iter(std::iter::once(
+ PiecewiseLinearFunctionEntry {
+ x: 0.,
+ y: self.entries[0].y,
+ },
+ )),
+ };
+ }
+ // Guaranteed at least two elements.
+ // Start element's x value should've been assigned when the first value was pushed.
+ debug_assert!(
+ self.entries[0].x.is_some(),
+ "Expected an entry with x defined!"
+ );
+ // Spec asserts that if the last entry does not have an x value, it is assigned the largest seen x value.
+ self.entries
+ .last_mut()
+ .unwrap()
+ .x
+ .get_or_insert(self.largest_x.filter(|x| x > &1.0).unwrap_or(1.0));
+ // Now we have at least two elements with x values, with start & end x values guaranteed.
+
+ let mut result = Vec::with_capacity(self.entries.len());
+ result.push(PiecewiseLinearFunctionEntry {
+ x: self.entries[0].x.unwrap(),
+ y: self.entries[0].y,
+ });
+ for (i, e) in self.entries.iter().enumerate().skip(1) {
+ if e.x.is_none() {
+ // Need to calculate x values by first finding an entry with the first
+ // defined x value (Guaranteed to exist as the list end has it defined).
+ continue;
+ }
+ // x is defined for this element.
+ let divisor = i - result.len() + 1;
+ // Any element(s) with undefined x to assign?
+ if divisor != 1 {
+ // Have at least one element in result at all times.
+ let start_x = result.last().unwrap().x;
+ let increment = (e.x.unwrap() - start_x) / divisor as ValueType;
+ // Grab every element with undefined x to this point, which starts at the end of the result
+ // array, and ending right before the current index. Then, assigned the evenly divided
+ // x values.
+ result.extend(
+ self.entries[result.len()..i]
+ .iter()
+ .enumerate()
+ .map(|(j, e)| {
+ debug_assert!(e.x.is_none(), "Expected an entry with x undefined!");
+ PiecewiseLinearFunctionEntry {
+ x: increment * (j + 1) as ValueType + start_x,
+ y: e.y,
+ }
+ }),
+ );
+ }
+ result.push(PiecewiseLinearFunctionEntry {
+ x: e.x.unwrap(),
+ y: e.y,
+ });
+ }
+ debug_assert_eq!(
+ result.len(),
+ self.entries.len(),
+ "Should've mapped one-to-one!"
+ );
+ PiecewiseLinearFunction {
+ entries: crate::ArcSlice::from_iter(result.into_iter()),
+ }
+ }
+}