devpage_design/display/
run.rs

1//! A run's children in the index: each child a space of its own — its
2//! chunks in its own coordinates under an R-tree of its own — placed along
3//! the run by the prefix sums of the sizes before it. The run is one entry in
4//! the space it sits in; a query inside it finds the first child that
5//! reaches the rectangle by a search of the sums, widened by the furthest any
6//! child paints past its box, and walks on until a child starts past it. A
7//! child that changes size moves no other child's entry: their places are
8//! the sums.
9
10use std::collections::{BTreeMap, HashMap};
11
12use kurbo::{Rect as KRect, Vec2};
13
14use crate::sums::{Item, Summary, Sums};
15use crate::tree::OrderKey;
16
17use super::*;
18
19/// A run, by its slot.
20pub type RunId = u32;
21
22/// Where a chunk's coordinates are: the design's own, or a run's child's,
23/// whose origin is the child's box's top-left.
24#[derive(Clone, Debug, PartialEq, Eq, Hash)]
25pub enum Space {
26    Root,
27    Item(RunId, OrderKey),
28}
29
30/// A run's children placed along it, and what they paint.
31pub struct Run {
32    /// The space its own node is in.
33    pub space: Space,
34    /// Its node's unrounded top-left and its rounded one, in its space.
35    pub raw: Vec2,
36    pub at: Vec2,
37    /// Where its space's origin was in the design's coordinates when it was
38    /// last placed: its children are placed in single precision there, as
39    /// taffy places them, so they round where a whole tree's do.
40    pub origin: Vec2,
41    /// Whether its children go along x; else along y.
42    pub row: bool,
43    /// Where its first child starts along the run, from its node's unrounded
44    /// top-left: the padding and any `justify` offset.
45    pub start: f64,
46    /// Where its children's line starts across, from the same: the padding.
47    pub across: f64,
48    /// The gap between children.
49    pub gap: f64,
50    /// The breadth of its children's line.
51    pub line: f64,
52    /// What cuts it in its space: its clipping frames' boxes.
53    pub cut: Option<KRect>,
54    pub(super) items: Sums<OrderKey, Placed>,
55    pub(super) spaces: HashMap<OrderKey, SpaceIndex>,
56    /// The furthest any child reaches past its box along the run, and each
57    /// child's reach and cover across, from the line's start: counted sets.
58    pub(super) overhang: Counted,
59    pub(super) reach_across: (Counted, Counted),
60    pub(super) cover_across: (Counted, Counted),
61    /// Its entry in its space's index, and what it adds to its space's cover.
62    pub(super) entry: Option<KRect>,
63    pub(super) cover: Option<KRect>,
64}
65
66/// One space's index: its chunks and runs by their bounds in its own
67/// coordinates, and the extent of what its chunks cover.
68#[derive(Default)]
69pub struct SpaceIndex {
70    pub(super) index: rstar::RTree<Entry>,
71    pub(super) covers: Extent,
72}
73
74/// A child of a run as the run's sums see it: its size along the run, the
75/// gap after it, where it sits across, and what it reaches and covers along
76/// the run from its unrounded start.
77#[derive(Clone, Debug, PartialEq)]
78pub struct Placed {
79    pub size: f64,
80    pub gap: f64,
81    /// Its unrounded place across, from the line's start.
82    pub across: f64,
83    /// Its rounded top-left less its unrounded one: fixed while what the
84    /// run places it at keeps its fraction of a pixel.
85    pub delta: Vec2,
86    pub(super) reach: Option<(f64, f64)>,
87    pub(super) covered: Option<(f64, f64)>,
88    /// What it put in the run's counted sets, to take out again.
89    pub(super) counted: Counts,
90}
91
92/// A child's entries in its run's counted sets.
93#[derive(Clone, Debug, PartialEq, Default)]
94pub struct Counts {
95    overhang: Option<f64>,
96    reach: Option<(f64, f64)>,
97    cover: Option<(f64, f64)>,
98}
99
100impl Placed {
101    pub fn new(size: f64, gap: f64, across: f64, delta: Vec2) -> Placed {
102        Placed {
103            size,
104            gap,
105            across,
106            delta,
107            reach: None,
108            covered: None,
109            counted: Counts::default(),
110        }
111    }
112}
113
114/// A stretch of a run's children: how many, how far they advance — each
115/// child's size and the gap after it — and the least and greatest each
116/// reaches and covers, along the run from the stretch's start.
117#[derive(Clone, Debug)]
118pub struct Span {
119    pub n: usize,
120    pub length: f64,
121    pub reach: (f64, f64),
122    pub covered: (f64, f64),
123}
124
125impl Default for Span {
126    fn default() -> Self {
127        Span {
128            n: 0,
129            length: 0.0,
130            reach: (f64::INFINITY, f64::NEG_INFINITY),
131            covered: (f64::INFINITY, f64::NEG_INFINITY),
132        }
133    }
134}
135
136impl Summary for Span {
137    fn then(&self, next: &Self) -> Self {
138        let shift = |(lo, hi): (f64, f64), (nlo, nhi): (f64, f64)| {
139            (lo.min(self.length + nlo), hi.max(self.length + nhi))
140        };
141        Span {
142            n: self.n + next.n,
143            length: self.length + next.length,
144            reach: shift(self.reach, next.reach),
145            covered: shift(self.covered, next.covered),
146        }
147    }
148}
149
150impl Item for Placed {
151    type Sum = Span;
152    fn summary(&self) -> Span {
153        let none = (f64::INFINITY, f64::NEG_INFINITY);
154        Span {
155            n: 1,
156            length: self.size + self.gap,
157            reach: self.reach.unwrap_or(none),
158            covered: self.covered.unwrap_or(none),
159        }
160    }
161}
162
163/// A multiset of numbers that knows its least and greatest in log time.
164#[derive(Default)]
165pub struct Counted(BTreeMap<i64, usize>);
166
167impl Counted {
168    pub(super) fn add(&mut self, v: f64) {
169        *self.0.entry(key(v)).or_default() += 1;
170    }
171    pub(super) fn remove(&mut self, v: f64) {
172        let k = key(v);
173        if let Some(n) = self.0.get_mut(&k) {
174            *n -= 1;
175            if *n == 0 {
176                self.0.remove(&k);
177            }
178        }
179    }
180    pub(super) fn least(&self) -> Option<f64> {
181        self.0.keys().next().map(|k| *k as f64 / 1e6)
182    }
183    pub(super) fn greatest(&self) -> Option<f64> {
184        self.0.keys().next_back().map(|k| *k as f64 / 1e6)
185    }
186}
187
188/// A rectangle's span along a run and across it.
189fn spans(row: bool, r: KRect) -> ((f64, f64), (f64, f64)) {
190    if row {
191        ((r.x0, r.x1), (r.y0, r.y1))
192    } else {
193        ((r.y0, r.y1), (r.x0, r.x1))
194    }
195}
196
197fn rect(row: bool, along: (f64, f64), across: (f64, f64)) -> KRect {
198    if row {
199        KRect::new(along.0, across.0, along.1, across.1)
200    } else {
201        KRect::new(across.0, along.0, across.1, along.1)
202    }
203}
204
205impl Run {
206    pub fn new(space: Space) -> Run {
207        Run {
208            space,
209            raw: Vec2::ZERO,
210            at: Vec2::ZERO,
211            origin: Vec2::ZERO,
212            row: false,
213            start: 0.0,
214            across: 0.0,
215            gap: 0.0,
216            line: 0.0,
217            cut: None,
218            items: Sums::new(),
219            spaces: HashMap::new(),
220            overhang: Counted::default(),
221            reach_across: Default::default(),
222            cover_across: Default::default(),
223            entry: None,
224            cover: None,
225        }
226    }
227
228    pub fn len(&self) -> usize {
229        self.items.len()
230    }
231
232    pub fn is_empty(&self) -> bool {
233        self.items.is_empty()
234    }
235
236    /// Where the run places a child: its unrounded top-left in the run's
237    /// space, and its rounded one — each edge where taffy's pass puts it,
238    /// measured from the run's node, a box in the flow.
239    pub fn place(&self, before: f64, across: f64) -> (Vec2, Vec2) {
240        // In single precision, as taffy places a box and its rounding pass
241        // rounds it: the child's place within the run, then the run's.
242        let along = (self.start + before) as f32;
243        let across = (self.across + across) as f32;
244        let (dx, dy) = if self.row {
245            (along, across)
246        } else {
247            (across, along)
248        };
249        let o = self.origin;
250        let (rx, ry) = ((o.x + self.raw.x) as f32, (o.y + self.raw.y) as f32);
251        let raw = (rx + dx, ry + dy);
252        let snap32 = |v: f32| (v + 0.5).floor();
253        let at = (
254            (o.x + self.at.x) as f32 + snap32(raw.0) - snap32(rx),
255            (o.y + self.at.y) as f32 + snap32(raw.1) - snap32(ry),
256        );
257        (
258            Vec2::new(raw.0 as f64 - o.x, raw.1 as f64 - o.y),
259            Vec2::new(at.0 as f64 - o.x, at.1 as f64 - o.y),
260        )
261    }
262
263    /// The child at `key`: how far along the run the children before it
264    /// advance, and how it is placed.
265    pub fn child(&self, key: &OrderKey) -> Option<(f64, &Placed)> {
266        let placed = self.items.get(key)?;
267        Some((self.items.before(key).length, placed))
268    }
269
270    /// How far along the run the children before `key` advance.
271    pub fn prefix(&self, key: &OrderKey) -> f64 {
272        self.items.before(key).length
273    }
274
275    /// The keys of the children after `key`, in order.
276    pub fn keys_after(&self, key: &OrderKey) -> Vec<OrderKey> {
277        self.items
278            .from(key)
279            .filter(|(k, _)| *k != key)
280            .map(|(k, _)| k.clone())
281            .collect()
282    }
283
284    /// Its entry's bounds in its space's index.
285    pub fn entry(&self) -> Option<KRect> {
286        self.entry
287    }
288
289    /// Where the child at `key` is: its rounded top-left in the run's space.
290    pub fn child_at(&self, key: &OrderKey) -> Option<Vec2> {
291        let (before, p) = self.child(key)?;
292        Some(self.place(before, p.across).1)
293    }
294
295    /// The children in order, each with how far the ones before it advance.
296    pub fn children(&self) -> impl Iterator<Item = (&OrderKey, f64, &Placed)> {
297        let mut before = 0.0;
298        self.items.iter().map(move |(k, p)| {
299            let b = before;
300            before += p.size + p.gap;
301            (k, b, p)
302        })
303    }
304
305    /// The children that can touch `r`, in the run's space, in order: from
306    /// the first whose box ends past `r`'s start, less the furthest any child
307    /// reaches past its box, to the last that starts before its end, plus
308    /// that.
309    pub(super) fn touching(&self, r: KRect) -> Vec<(&OrderKey, Vec2)> {
310        self.touching_rounded(r)
311            .into_iter()
312            .map(|(k, at, _)| (k, at))
313            .collect()
314    }
315
316    /// [`Run::touching`], each child with whether it still rounds as its
317    /// space was made: whether its rounded place less its unrounded one is
318    /// what it was when its boxes and chunks were made. A child the sums
319    /// moved by a fraction of a pixel doesn't, and is rounded anew before it
320    /// is read.
321    pub(super) fn touching_rounded(&self, r: KRect) -> Vec<(&OrderKey, Vec2, bool)> {
322        let ((a0, a1), _) = spans(self.row, r);
323        let base = if self.row { self.raw.x } else { self.raw.y } + self.start;
324        let over = self.overhang.greatest().unwrap_or(0.0).max(0.0);
325        let (from, to) = (a0 - base - over, a1 - base + over);
326        let Some((first, _, before)) = self.items.seek(|s| s.length - s_gap(s, self.gap) >= from)
327        else {
328            return Vec::new();
329        };
330        let mut out = Vec::new();
331        let mut at = before.length;
332        for (k, p) in self.items.from(first) {
333            if at > to {
334                break;
335            }
336            let (raw, rounded) = self.place(at, p.across);
337            let fresh = ((rounded - raw) - p.delta).hypot() < 1e-3;
338            out.push((k, rounded, fresh));
339            at += p.size + p.gap;
340        }
341        out
342    }
343
344    /// What the run's children reach and cover in its space, from its sums
345    /// and counted sets; `None` where nothing.
346    pub(super) fn extents(&self) -> (Option<KRect>, Option<KRect>) {
347        let total = self.items.total();
348        let base = if self.row { self.raw.x } else { self.raw.y } + self.start;
349        let across = if self.row { self.raw.y } else { self.raw.x } + self.across;
350        let make = |along: (f64, f64), lo: &Counted, hi: &Counted| {
351            let (Some(c0), Some(c1)) = (lo.least(), hi.greatest()) else {
352                return None;
353            };
354            if along.0.partial_cmp(&along.1) == Some(std::cmp::Ordering::Greater)
355                || along.0.is_nan()
356            {
357                return None;
358            }
359            Some(rect(
360                self.row,
361                (base + along.0, base + along.1),
362                (across + c0, across + c1),
363            ))
364        };
365        let reach = make(total.reach, &self.reach_across.0, &self.reach_across.1);
366        let cover = make(total.covered, &self.cover_across.0, &self.cover_across.1)
367            .and_then(|r| super::chunk::cut_to(r, self.cut));
368        (reach, cover)
369    }
370
371    /// Puts what a child is, from its space's index and covers, in the sums
372    /// and the counted sets.
373    pub(super) fn set(&mut self, key: OrderKey, mut placed: Placed) {
374        self.unset(&key);
375        let local = self.spaces.entry(key.clone()).or_default();
376        let reach = local.index.root().envelope();
377        let reach = (reach.lower()[0] <= reach.upper()[0]).then(|| {
378            KRect::new(
379                reach.lower()[0],
380                reach.lower()[1],
381                reach.upper()[0],
382                reach.upper()[1],
383            )
384        });
385        let covered = local.covers.rect();
386        let d = if self.row {
387            (placed.delta.x, placed.delta.y)
388        } else {
389            (placed.delta.y, placed.delta.x)
390        };
391        let along = |r: KRect| {
392            let ((a0, a1), _) = spans(self.row, r);
393            (a0 + d.0, a1 + d.0)
394        };
395        let across = |r: KRect| {
396            let (_, (c0, c1)) = spans(self.row, r);
397            (placed.across + d.1 + c0, placed.across + d.1 + c1)
398        };
399        placed.reach = reach.map(along);
400        placed.covered = covered.map(along);
401        placed.counted = Counts::default();
402        if let Some(r) = reach {
403            let (lo, hi) = along(r);
404            let o = (-lo).max(hi - placed.size).max(0.0);
405            self.overhang.add(o);
406            let c = across(r);
407            self.reach_across.0.add(c.0);
408            self.reach_across.1.add(c.1);
409            placed.counted.overhang = Some(o);
410            placed.counted.reach = Some(c);
411        }
412        if let Some(r) = covered {
413            let c = across(r);
414            self.cover_across.0.add(c.0);
415            self.cover_across.1.add(c.1);
416            placed.counted.cover = Some(c);
417        }
418        self.items.insert(key, placed);
419    }
420
421    /// Takes a child out of the sums and the counted sets, keeping its
422    /// space; returns how it was placed.
423    pub(super) fn unset(&mut self, key: &OrderKey) -> Option<Placed> {
424        let p = self.items.remove(key)?;
425        if let Some(o) = p.counted.overhang {
426            self.overhang.remove(o);
427        }
428        if let Some((c0, c1)) = p.counted.reach {
429            self.reach_across.0.remove(c0);
430            self.reach_across.1.remove(c1);
431        }
432        if let Some((c0, c1)) = p.counted.cover {
433            self.cover_across.0.remove(c0);
434            self.cover_across.1.remove(c1);
435        }
436        Some(p)
437    }
438}
439
440/// The gap a stretch's length counts after its last child.
441fn s_gap(s: &Span, gap: f64) -> f64 {
442    if s.n == 0 { 0.0 } else { gap }
443}
devpage_design/display/run.rs

devpage_design/display/
run.rs
