display_list.rs
raw
//! The display list: plain-data drawing commands and the fragment tree they
//! live in.
//!
//! Everything here is inert data with structural equality (`PartialEq`), which
//! is what makes golden tests and codegen-vs-interpreter differential tests
//! able to compare scenes precisely instead of comparing pixels.
use std::sync::atomic::{AtomicU64, Ordering};
use slotmap::{SecondaryMap, SlotMap, new_key_type};
use crate::geom::{Affine, BezPath, Rect, RoundedRect, Shape as _, Stroke};
use crate::paint::{BlendMode, Brush, Fill, FontData, ImageBrush};
/// A shape a display item can fill, stroke, or clip to.
///
/// Rectangles and rounded rectangles are kept in symbolic form rather than
/// flattened to paths so that backends can use cheaper specialized encodings
/// for them.
#[derive(Clone, Debug, PartialEq)]
pub enum Shape {
Rect(Rect),
RoundedRect(RoundedRect),
Path(BezPath),
}
impl Shape {
/// Flatten this shape to a Bézier path, for backends without specialized
/// rect handling.
pub fn to_path(&self, tolerance: f64) -> BezPath {
match self {
Shape::Rect(rect) => rect.to_path(tolerance),
Shape::RoundedRect(rrect) => rrect.to_path(tolerance),
Shape::Path(path) => path.clone(),
}
}
/// The axis-aligned bounding box of the shape.
pub fn bounding_box(&self) -> Rect {
match self {
Shape::Rect(rect) => *rect,
Shape::RoundedRect(rrect) => rrect.bounding_box(),
Shape::Path(path) => path.bounding_box(),
}
}
}
impl From<Rect> for Shape {
fn from(rect: Rect) -> Self {
Shape::Rect(rect)
}
}
impl From<RoundedRect> for Shape {
fn from(rrect: RoundedRect) -> Self {
Shape::RoundedRect(rrect)
}
}
impl From<BezPath> for Shape {
fn from(path: BezPath) -> Self {
Shape::Path(path)
}
}
/// A positioned glyph within a [`GlyphRun`], in run-local coordinates.
#[derive(Copy, Clone, Debug, PartialEq)]
pub struct Glyph {
/// Glyph identifier in the run's font.
pub id: u32,
/// X offset relative to the run origin.
pub x: f32,
/// Y offset (baseline) relative to the run origin.
pub y: f32,
}
/// A normalized variable-font axis coordinate (2.14 fixed point).
pub type NormalizedCoord = i16;
/// A run of positioned glyphs in a single font and size.
#[derive(Clone, Debug, PartialEq)]
pub struct GlyphRun {
/// The font the glyph ids refer to.
pub font: FontData,
/// Font size in pixels per em.
pub size: f32,
/// Brush the glyphs are filled with.
pub brush: Brush,
/// The positioned glyphs.
pub glyphs: Vec<Glyph>,
/// Variable-font axis coordinates; empty for non-variable fonts.
pub normalized_coords: Vec<NormalizedCoord>,
/// Whether to hint glyph outlines to the pixel grid.
pub hint: bool,
}
/// One drawing command in a fragment's display list.
///
/// `Push*`/`Pop*` items must be balanced within a single fragment; state never
/// leaks across fragment boundaries.
#[derive(Clone, Debug, PartialEq)]
pub enum DisplayItem {
/// Fill a shape with a brush.
Fill {
shape: Shape,
brush: Brush,
rule: Fill,
},
/// Stroke the outline of a shape.
Stroke {
shape: Shape,
brush: Brush,
style: Stroke,
},
/// Draw a run of glyphs.
GlyphRun(GlyphRun),
/// Draw an image scaled into a destination rectangle.
Image {
image: ImageBrush,
dest: Rect,
},
/// Clip subsequent items to a shape, until the matching [`PopClip`].
///
/// [`PopClip`]: DisplayItem::PopClip
PushClip(Shape),
PopClip,
/// Apply a transform to subsequent items, until the matching
/// [`PopTransform`].
///
/// [`PopTransform`]: DisplayItem::PopTransform
PushTransform(Affine),
PopTransform,
/// Composite subsequent items as a group with opacity and blend mode,
/// clipped to `bounds`, until the matching [`PopLayer`].
///
/// [`PopLayer`]: DisplayItem::PopLayer
PushLayer {
alpha: f32,
blend: BlendMode,
bounds: Shape,
},
PopLayer,
/// Draw another fragment here, placed by `transform`.
///
/// The child inherits the clip/transform/layer state open at this point in
/// the list — this is how a scroll area clips and offsets its content —
/// while the child's own `Push*` state stays contained within it.
Child {
transform: Affine,
fragment: FragmentId,
},
}
new_key_type! {
/// Identifier of a [`Fragment`] within a [`FragmentStore`].
pub struct FragmentId;
}
/// The paint output of one widget: a display list, which may reference child
/// fragments inline via [`DisplayItem::Child`].
#[derive(Clone, Debug, Default, PartialEq)]
pub struct Fragment {
/// Drawing commands, in paint order.
pub items: Vec<DisplayItem>,
}
impl Fragment {
pub fn new() -> Self {
Self::default()
}
/// Remove all items, keeping the allocation for reuse.
pub fn clear(&mut self) {
self.items.clear();
}
/// Fill a shape with the non-zero winding rule.
pub fn fill(&mut self, shape: impl Into<Shape>, brush: impl Into<Brush>) {
self.fill_with_rule(shape, brush, Fill::NonZero);
}
pub fn fill_with_rule(&mut self, shape: impl Into<Shape>, brush: impl Into<Brush>, rule: Fill) {
self.items.push(DisplayItem::Fill {
shape: shape.into(),
brush: brush.into(),
rule,
});
}
pub fn stroke(&mut self, shape: impl Into<Shape>, brush: impl Into<Brush>, style: Stroke) {
self.items.push(DisplayItem::Stroke {
shape: shape.into(),
brush: brush.into(),
style,
});
}
pub fn glyph_run(&mut self, run: GlyphRun) {
self.items.push(DisplayItem::GlyphRun(run));
}
pub fn image(&mut self, image: ImageBrush, dest: Rect) {
self.items.push(DisplayItem::Image { image, dest });
}
pub fn push_clip(&mut self, shape: impl Into<Shape>) {
self.items.push(DisplayItem::PushClip(shape.into()));
}
pub fn pop_clip(&mut self) {
self.items.push(DisplayItem::PopClip);
}
pub fn push_transform(&mut self, transform: Affine) {
self.items.push(DisplayItem::PushTransform(transform));
}
pub fn pop_transform(&mut self) {
self.items.push(DisplayItem::PopTransform);
}
pub fn push_layer(&mut self, alpha: f32, blend: BlendMode, bounds: impl Into<Shape>) {
self.items.push(DisplayItem::PushLayer {
alpha,
blend,
bounds: bounds.into(),
});
}
pub fn pop_layer(&mut self) {
self.items.push(DisplayItem::PopLayer);
}
/// Draw a child fragment here, positioned by `transform`.
pub fn child(&mut self, transform: Affine, fragment: FragmentId) {
self.items.push(DisplayItem::Child {
transform,
fragment,
});
}
/// Whether every `Push*` item has a matching `Pop*` of the same kind, in
/// properly nested order. Backends enforce this while walking, via
/// [`ScopeTracker`].
pub fn is_balanced(&self) -> bool {
let mut tracker = ScopeTracker::default();
self.items.iter().all(|item| tracker.apply(item)) && tracker.is_closed()
}
}
/// The kind of scope opened by a `Push*` display item.
#[derive(Copy, Clone, Debug, PartialEq)]
pub enum ScopeKind {
Clip,
Transform,
Layer,
}
/// Tracks `Push*`/`Pop*` nesting through a display list, rejecting pops whose
/// kind does not match the innermost open scope.
///
/// This is the single definition of "balanced" shared by
/// [`Fragment::is_balanced`] and the render backends' walkers.
#[derive(Default)]
pub struct ScopeTracker {
stack: Vec<ScopeKind>,
}
impl ScopeTracker {
/// Record `item`'s effect on the scope stack. Returns false if `item` is
/// a pop that does not match the innermost open scope; non-scope items
/// always succeed.
#[must_use]
pub fn apply(&mut self, item: &DisplayItem) -> bool {
match item {
DisplayItem::PushClip(_) => self.stack.push(ScopeKind::Clip),
DisplayItem::PushTransform(_) => self.stack.push(ScopeKind::Transform),
DisplayItem::PushLayer { .. } => self.stack.push(ScopeKind::Layer),
DisplayItem::PopClip => return self.stack.pop() == Some(ScopeKind::Clip),
DisplayItem::PopTransform => return self.stack.pop() == Some(ScopeKind::Transform),
DisplayItem::PopLayer => return self.stack.pop() == Some(ScopeKind::Layer),
_ => {}
}
true
}
/// Whether every opened scope has been closed.
pub fn is_closed(&self) -> bool {
self.stack.is_empty()
}
}
/// Arena of fragments; the widget tree owns ids into this store.
///
/// The store carries the change-tracking contract render backends cache
/// against: a process-unique [`store_id`](Self::store_id) and a per-fragment
/// [`epoch`](Self::epoch) that advances on every mutable access. A backend
/// that remembers (store id, fragment id, epoch) knows a fragment's content
/// is unchanged when all three still match, and that the fragment is gone
/// when its epoch is no longer present.
pub struct FragmentStore {
fragments: SlotMap<FragmentId, Fragment>,
epochs: SecondaryMap<FragmentId, u64>,
/// Monotonic mutation counter; the source of epoch values.
counter: u64,
id: u64,
}
impl Default for FragmentStore {
fn default() -> Self {
static NEXT_STORE_ID: AtomicU64 = AtomicU64::new(0);
Self {
fragments: SlotMap::default(),
epochs: SecondaryMap::default(),
counter: 0,
id: NEXT_STORE_ID.fetch_add(1, Ordering::Relaxed),
}
}
}
impl FragmentStore {
pub fn new() -> Self {
Self::default()
}
/// This store's process-unique identity. Backends key their caches on it
/// so that fragment ids from different stores can never be conflated.
pub fn store_id(&self) -> u64 {
self.id
}
/// The store-wide mutation counter: advances on every insert, mutable
/// borrow, and removal. Two observations of the same (store id, counter)
/// pair guarantee the store's entire content is unchanged between them.
pub fn mutation_counter(&self) -> u64 {
self.counter
}
/// The fragment's mutation epoch: advances every time the fragment is
/// inserted or borrowed mutably. `None` when the fragment does not exist.
pub fn epoch(&self, id: FragmentId) -> Option<u64> {
self.epochs.get(id).copied()
}
fn stamp(&mut self, id: FragmentId) {
self.counter += 1;
self.epochs.insert(id, self.counter);
}
/// Insert an empty fragment and return its id.
pub fn create(&mut self) -> FragmentId {
let id = self.fragments.insert(Fragment::new());
self.stamp(id);
id
}
pub fn insert(&mut self, fragment: Fragment) -> FragmentId {
let id = self.fragments.insert(fragment);
self.stamp(id);
id
}
pub fn remove(&mut self, id: FragmentId) -> Option<Fragment> {
if self.fragments.contains_key(id) {
self.counter += 1;
}
self.epochs.remove(id);
self.fragments.remove(id)
}
pub fn get(&self, id: FragmentId) -> Option<&Fragment> {
self.fragments.get(id)
}
/// Borrow a fragment mutably, advancing its epoch. The bump is
/// unconditional — a borrow that ends up writing identical content still
/// counts as a change; over-invalidation is safe, staleness is not.
pub fn get_mut(&mut self, id: FragmentId) -> Option<&mut Fragment> {
if self.fragments.contains_key(id) {
self.stamp(id);
}
self.fragments.get_mut(id)
}
/// Remove all fragments. Existing ids become invalid.
pub fn clear(&mut self) {
if !self.fragments.is_empty() {
self.counter += 1;
}
self.fragments.clear();
self.epochs.clear();
}
/// Structural equality of two fragment trees, possibly across stores:
/// identical display items in identical order, with child references
/// compared recursively (ids themselves are irrelevant).
///
/// This is what makes "the compiled and interpreted component produce
/// the same scene" a precise, testable statement.
pub fn trees_equal(&self, a: FragmentId, other: &FragmentStore, b: FragmentId) -> bool {
let (Some(fa), Some(fb)) = (self.get(a), other.get(b)) else {
return false;
};
if fa.items.len() != fb.items.len() {
return false;
}
fa.items
.iter()
.zip(fb.items.iter())
.all(|(ia, ib)| match (ia, ib) {
(
DisplayItem::Child {
transform: ta,
fragment: ca,
},
DisplayItem::Child {
transform: tb,
fragment: cb,
},
) => ta == tb && self.trees_equal(*ca, other, *cb),
(ia, ib) => ia == ib,
})
}
}
#[cfg(test)]
mod tests;