dioxus-flow 0.1.3

//! Grouping the graph into world tiles, so a browser can skip the parts of it
//! that are off screen.
//!
//! The reason this exists is a measurement. Panning a 20 000-node graph costs
//! the same whether 60 nodes are on screen or 950: the engine walks every node
//! subtree in the transformed layer on every frame, and what is *visible* never
//! enters into it. Cost tracks the size of the render tree under the viewport
//! transform, not the size of what a reader can see.
//!
//! So the fix is to give the engine permission to skip. A tile is a box drawn
//! around a group of neighbouring items; it carries `content-visibility: auto`,
//! and an engine that can see the box is off screen skips laying out and
//! painting everything inside it. One box stands in for a hundred nodes.
//!
//! Two properties make that safe, and both are why tiling is a function here
//! rather than a division in the renderer:
//!
//! * A tile's box is the union of what it holds, never the lattice cell that
//!   caught them. `content-visibility` brings paint containment with it, which
//!   clips to the box, so a tile that merely straddles its members would cut
//!   the shadow off a node sitting on its edge. [`Tile::rect`] contains every
//!   member outright, and [`PAD`] leaves room for the ink that spills past a
//!   member's own bounds.
//! * Tiles may overlap, and long items are allowed to make theirs large. An
//!   item is assigned by where it starts, so an edge crossing six cells widens
//!   one tile instead of being cut in half by six.

use crate::types::{Point, Rect};

/// The lattice pitch, in flow units.
///
/// What a pitch really sets is how far past the viewport the drawn region
/// reaches: a tile is kept whole, so the rendered area is the viewport grown
/// by roughly one pitch each way, and the waste grows as the square of it.
/// That argues for making it small. Against that, every tile is a box the
/// engine has to consider, and more of them cost more to build.
///
/// Swept over a 20 000-node grid at 1024 / 2048 / 4096, the middle value is
/// the one to keep, but the honest summary is that it barely matters. 4096 is
/// clearly worst (Chromium's fit-view frame 41 ms against 28 ms, WebKit's
/// 69 ms against 56 ms). Between 1024 and 2048 the wins split three-all with
/// four ties, and most of the gaps sit inside the ~20% run-to-run spread these
/// numbers carry. The one difference that clearly exceeds it goes to 2048:
/// mounting 20 000 nodes in WebKit takes 12.3 s against 16.6 s, because 1024
/// builds four times the tiles.
///
/// Two things the sweep did establish, both worth keeping in mind before
/// touching this again:
///
/// * Chromium's cost lands at ~0.012 ms per *rendered node* at every pitch, so
///   having a tile is nearly free next to drawing its contents.
/// * WebKit's cost does not depend on the tile count at all — 883 tiles and
///   238 tiles both pan at 46 ms with the same graph. What it tracks is the
///   number of elements in the document, skipped or not, which is why no pitch
///   reaches 60 fps there and why culling (unmounting, rather than skipping)
///   is the next thing that would.
pub(crate) const PITCH: f64 = 2048.0;

/// Room left around a tile's contents for ink that escapes their own bounds —
/// a node's shadow, a focus ring, the overshoot of the enter animation, half
/// an edge's stroke, an arrowhead. Paint containment clips to the tile box, so
/// anything not accounted for here would be visibly sliced off.
pub(crate) const PAD: f64 = 40.0;

/// One group of neighbouring items, and the box that contains them all.
#[derive(Clone, PartialEq, Debug)]
pub(crate) struct Tile {
    /// Lattice cell that gathered these items. Stable across re-tilings, so it
    /// keys the tile's element and keeps its subtree from being rebuilt as
    /// neighbouring tiles come and go.
    pub cell: (i64, i64),
    /// A box containing every member outright, padded by [`PAD`].
    pub rect: Rect,
    /// Indices into the slice that was tiled, in its original order — so the
    /// paint order within a tile is the order the caller asked for.
    pub members: Vec<usize>,
    /// Whether any member asked to be drawn above the rest of the graph.
    /// Containment makes each tile a stacking context, so a raised member can
    /// only rise above its own tile's siblings; the tile has to rise too, or a
    /// dragged node would slide under the next tile along.
    pub raised: bool,
}

impl Tile {
    /// Where the tile's box starts. Members are positioned relative to this,
    /// because the tile is their containing block once it is an element.
    pub fn origin(&self) -> Point {
        self.rect.origin()
    }
}

/// Group `items` into tiles by where each one starts.
///
/// `raised` marks an item that must paint above the rest of the graph, which
/// lifts its whole tile. Empty input yields no tiles; a graph small enough to
/// sit in one cell yields exactly one, which costs a single element and skips
/// nothing — the case tiling should not be paying for.
pub(crate) fn tiles(items: impl IntoIterator<Item = (Rect, bool)>) -> Vec<Tile> {
    let mut tiles: Vec<Tile> = Vec::new();
    // Small graphs have a handful of cells, so a scan beats hashing — and it
    // keeps the output ordered by first appearance, which keeps paint order
    // stable as nodes move between tiles.
    let mut index: Vec<((i64, i64), usize)> = Vec::new();
    for (i, (rect, raised)) in items.into_iter().enumerate() {
        // A non-finite position would poison the whole tile's box and take
        // every node in it off screen with it. Such a node is already not
        // drawable; give it its own tile so it cannot do that.
        let cell = if rect.x.is_finite() && rect.y.is_finite() {
            (
                (rect.x / PITCH).floor() as i64,
                (rect.y / PITCH).floor() as i64,
            )
        } else {
            (i64::MIN, i as i64)
        };
        match index.iter().find(|(c, _)| *c == cell) {
            Some((_, at)) => {
                let tile = &mut tiles[*at];
                tile.rect = tile.rect.union(&rect);
                tile.members.push(i);
                tile.raised |= raised;
            }
            None => {
                index.push((cell, tiles.len()));
                tiles.push(Tile {
                    cell,
                    rect,
                    members: vec![i],
                    raised,
                });
            }
        }
    }
    for tile in &mut tiles {
        tile.rect = Rect::new(
            tile.rect.x - PAD,
            tile.rect.y - PAD,
            tile.rect.width + 2.0 * PAD,
            tile.rect.height + 2.0 * PAD,
        );
    }
    tiles
}

#[cfg(test)]
mod tests {
    use super::*;

    fn rect(x: f64, y: f64) -> Rect {
        Rect::new(x, y, 130.0, 46.0)
    }

    fn plain(rects: &[Rect]) -> Vec<Tile> {
        tiles(rects.iter().map(|r| (*r, false)))
    }

    #[test]
    fn nothing_tiles_to_nothing() {
        assert!(plain(&[]).is_empty());
    }

    /// A graph that fits in one cell must not be made to pay for tiling: one
    /// tile, one element, every node in it.
    #[test]
    fn a_small_graph_is_one_tile() {
        let tiles = plain(&[rect(0.0, 0.0), rect(300.0, 100.0), rect(80.0, 500.0)]);
        assert_eq!(tiles.len(), 1);
        assert_eq!(tiles[0].members, vec![0, 1, 2]);
    }

    /// The property that makes tiling safe to combine with paint containment:
    /// whatever a tile holds, it holds outright.
    #[test]
    fn every_tile_contains_its_members() {
        let rects: Vec<Rect> = (0..200)
            .map(|i| rect((i % 20) as f64 * 190.0, (i / 20) as f64 * 110.0))
            .collect();
        for tile in plain(&rects) {
            for &i in &tile.members {
                let member = rects[i];
                assert!(
                    tile.rect.x <= member.x
                        && tile.rect.y <= member.y
                        && tile.rect.max_x() >= member.max_x()
                        && tile.rect.max_y() >= member.max_y(),
                    "tile {:?} does not contain member {member:?}",
                    tile.rect,
                );
            }
        }
    }

    /// And it holds them with room to spare, because a node's ink runs past
    /// its own box.
    #[test]
    fn a_tile_leaves_room_for_ink_outside_the_box() {
        let tiles = plain(&[rect(500.0, 500.0)]);
        assert_eq!(tiles.len(), 1);
        let member = rect(500.0, 500.0);
        assert!(member.x - tiles[0].rect.x >= PAD);
        assert!(member.y - tiles[0].rect.y >= PAD);
        assert!(tiles[0].rect.max_x() - member.max_x() >= PAD);
        assert!(tiles[0].rect.max_y() - member.max_y() >= PAD);
    }

    /// Every item lands in exactly one tile: none dropped, none drawn twice.
    #[test]
    fn every_item_is_placed_once() {
        let rects: Vec<Rect> = (0..500)
            .map(|i| rect((i % 25) as f64 * 400.0, (i / 25) as f64 * 400.0))
            .collect();
        let mut seen: Vec<usize> = plain(&rects).into_iter().flat_map(|t| t.members).collect();
        seen.sort_unstable();
        assert_eq!(seen, (0..rects.len()).collect::<Vec<_>>());
    }

    /// A long item widens its tile rather than being cut in half by the cells
    /// it crosses — an edge spanning the graph is still drawn whole.
    #[test]
    fn a_long_item_widens_its_own_tile() {
        let long = Rect::new(0.0, 0.0, PITCH * 6.0, 10.0);
        let tiles = plain(&[long]);
        assert_eq!(tiles.len(), 1);
        assert!(tiles[0].rect.width >= long.width);
    }

    /// Members keep the caller's order inside a tile, so paint order within a
    /// tile is the order the graph was given in.
    #[test]
    fn members_keep_their_original_order() {
        let rects = [rect(0.0, 0.0), rect(9000.0, 0.0), rect(100.0, 0.0)];
        let tiles = plain(&rects);
        let first = tiles.iter().find(|t| t.cell == (0, 0)).unwrap();
        assert_eq!(first.members, vec![0, 2]);
    }

    /// One raised member lifts its tile, because containment would otherwise
    /// trap it below the next tile along.
    #[test]
    fn a_raised_member_raises_its_tile() {
        let tiles = tiles([
            (rect(0.0, 0.0), false),
            (rect(100.0, 0.0), true),
            (rect(9000.0, 0.0), false),
        ]);
        let raised: Vec<bool> = tiles.iter().map(|t| t.raised).collect();
        assert_eq!(raised, vec![true, false]);
    }

    /// A node with a nonsense position must not drag a whole tile's worth of
    /// perfectly good nodes off screen with it.
    #[test]
    fn a_nonsense_position_is_quarantined() {
        let tiles = plain(&[
            rect(0.0, 0.0),
            rect(f64::NAN, 0.0),
            rect(100.0, 0.0),
            rect(f64::INFINITY, 0.0),
        ]);
        let good = tiles.iter().find(|t| t.cell == (0, 0)).unwrap();
        assert_eq!(good.members, vec![0, 2]);
        assert!(good.rect.x.is_finite() && good.rect.width.is_finite());
        // The nonsense ones are off on their own, one tile each.
        assert_eq!(tiles.len(), 3);
    }

    /// Tiles are keyed by cell, not by position in the list, so a node moving
    /// does not renumber its neighbours' tiles.
    #[test]
    fn cells_key_tiles_independently_of_list_order() {
        let a = plain(&[rect(0.0, 0.0), rect(9000.0, 9000.0)]);
        let b = plain(&[rect(9000.0, 9000.0), rect(0.0, 0.0)]);
        let mut cells_a: Vec<_> = a.iter().map(|t| t.cell).collect();
        let mut cells_b: Vec<_> = b.iter().map(|t| t.cell).collect();
        cells_a.sort_unstable();
        cells_b.sort_unstable();
        assert_eq!(cells_a, cells_b);
    }
}