Source code
Revision control
Copy as Markdown
Other Tools
/* 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
//! A piecewise linear function, following CSS linear easing
use crate::values::computed::Percentage;
use core::slice::Iter;
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
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()),
}
}
}