moli/moli-layout/src/layout_tree/hit_test.rs

//! Streaming hit-test candidates and caret projections derived per query.

use std::{collections::HashSet, fmt::Debug, hash::Hash};

use super::{
    model::{
        LayoutBoxModel, LayoutClipChainId, LayoutClipNode, LayoutCoordinateSpaceId,
        LayoutFragmentId, LayoutFragmentKind, LayoutOutputBoxId, LayoutPoint, LayoutQuad,
        LayoutRect, LayoutTransform2D,
    },
    tree::FrozenLayoutTree,
};

/// One point-resolved surface in the exact front-to-back paint stack.
#[derive(Clone, Copy, Debug, PartialEq)]
pub enum LayoutPaintedSurfaceHit<N> {
    Dom(LayoutHit<N>),
    Control(crate::LayoutControlSurfaceHit<N>),
}

impl<N: Copy> LayoutPaintedSurfaceHit<N> {
    pub fn paint_order(self) -> u32 {
        match self {
            Self::Dom(hit) => hit.paint_order.unwrap_or(0),
            Self::Control(hit) => hit.paint_order(),
        }
    }
}

/// One hit-test candidate in fragment storage order.
#[derive(Clone, Debug, PartialEq)]
struct LayoutHitTestEntry<N> {
    source: N,
    fragment: LayoutFragmentId,
    coordinate_space: LayoutCoordinateSpaceId,
    clip_chain: Option<LayoutClipChainId>,
    local_rect: LayoutRect,
    paint_order: u32,
    is_text: bool,
    pointer_events: bool,
}

/// Result of resolving a point against hit candidates derived from the tree.
#[derive(Clone, Copy, Debug, PartialEq)]
pub struct LayoutHit<N> {
    pub source: N,
    /// The real provider identifies the exact fragment. Explicit mock
    /// providers can return a source-only hit without manufacturing a
    /// tree-local fragment identity.
    pub fragment: Option<LayoutFragmentId>,
    /// Exact paint ordinal for a real frozen-tree fragment. Explicit mock
    /// providers may return a source-only hit without one.
    pub paint_order: Option<u32>,
    pub local_point: LayoutPoint,
    pub is_text: bool,
    /// The exact physical content box in the hit fragment's own coordinate
    /// space.
    ///
    /// This rectangle has not been projected through CSS transforms.
    /// Embedded-content consumers use it to enter the child frame
    /// without reconstructing the iframe's used size from authored CSS.
    pub local_content_box: Option<LayoutRect>,
    /// Converts a point from this tree's viewport into the hit fragment's
    /// coordinate space. This is retained on the short-lived hit result so
    /// frame and native-scrollbar routing can compose the same inverse
    /// transforms that produced `local_point`.
    pub viewport_to_local: LayoutTransform2D,
}

/// Caret geometry resolved from the same text fragments and coordinate spaces
/// as Range geometry and hit testing.
#[derive(Clone, Debug, PartialEq)]
pub struct LayoutCaretPosition<N> {
    pub source: N,
    /// Present when `source` owns a rendered text fragment. The offset uses
    /// the source node's UTF-16 code-unit coordinate space.
    pub utf16_offset: Option<usize>,
    pub rect: LayoutQuad,
    /// Source boxes from the selected fragment towards the construction root.
    /// This lets tree-scope retargeting use the same pass without retaining
    /// output-local box identifiers or forcing a follow-up layout.
    pub ancestor_boxes: Vec<(N, LayoutBoxModel)>,
}

impl<N> FrozenLayoutTree<N>
where
    N: Copy + Debug + Eq + Hash,
{
    pub fn hit_test(
        &self,
        viewport_point: LayoutPoint,
        ignore_pointer_events_none: bool,
    ) -> Option<LayoutHit<N>> {
        if !self.viewport.contains(viewport_point) {
            return None;
        }
        let mut clips = PointClipQuery::new(self, viewport_point);
        let mut foremost: Option<LayoutHit<N>> = None;
        for entry in self.hit_test_entries() {
            if foremost.is_some_and(|hit| hit.paint_order >= Some(entry.paint_order)) {
                continue;
            }
            if let Some(hit) = self.hit_for_entry(&entry, ignore_pointer_events_none, &mut clips) {
                foremost = Some(hit);
            }
        }
        foremost
    }

    pub fn hit_test_all(
        &self,
        viewport_point: LayoutPoint,
        ignore_pointer_events_none: bool,
    ) -> Vec<LayoutHit<N>> {
        if !self.viewport.contains(viewport_point) {
            return Vec::new();
        }
        let mut clips = PointClipQuery::new(self, viewport_point);
        let mut hits = self
            .hit_test_entries()
            .filter_map(|entry| self.hit_for_entry(&entry, ignore_pointer_events_none, &mut clips))
            .collect::<Vec<_>>();
        hits.sort_by_key(|hit| std::cmp::Reverse(hit.paint_order));
        let mut seen = HashSet::new();
        hits.retain(|hit| seen.insert(hit.source));
        hits
    }

    /// Resolves every DOM or UA-control surface under one point in exact
    /// front-to-back paint order. Consumers can skip stale DOM sources without
    /// accidentally promoting a geometrically lower scrollbar over a live
    /// overlay.
    pub fn painted_surface_hits(
        &self,
        viewport_point: LayoutPoint,
        ignore_pointer_events_none: bool,
    ) -> Vec<LayoutPaintedSurfaceHit<N>> {
        if !self.viewport.contains(viewport_point) {
            return Vec::new();
        }
        let mut clips = PointClipQuery::new(self, viewport_point);
        let mut hits = self
            .hit_test_entries()
            .filter_map(|entry| {
                self.hit_for_entry(&entry, ignore_pointer_events_none, &mut clips)
                    .map(LayoutPaintedSurfaceHit::Dom)
            })
            .chain(
                self.control_surface_hits(viewport_point)
                    .into_iter()
                    .map(LayoutPaintedSurfaceHit::Control),
            )
            .collect::<Vec<_>>();
        hits.sort_by_key(|hit| std::cmp::Reverse(hit.paint_order()));
        hits
    }

    /// Returns the topmost painted UA control without comparing it to DOM
    /// fragments. Input dispatch should normally use [`Self::painted_surface_hits`].
    pub fn control_surface_hit_test(
        &self,
        viewport_point: LayoutPoint,
    ) -> Option<crate::LayoutControlSurfaceHit<N>> {
        self.control_surface_hits(viewport_point)
            .into_iter()
            .max_by_key(|hit| hit.paint_order())
    }

    /// Compatibility query for the topmost scrollbar among UA controls only.
    ///
    /// This does not resolve DOM occlusion. Input dispatch must use
    /// [`Self::painted_surface_hits`] so a later-painted DOM fragment can win
    /// over a scrollbar.
    pub fn scrollbar_hit_test(
        &self,
        viewport_point: LayoutPoint,
    ) -> Option<crate::LayoutScrollbarHit<N>> {
        self.control_surface_hits(viewport_point)
            .into_iter()
            .filter_map(|hit| match hit {
                crate::LayoutControlSurfaceHit::Scrollbar(hit) => Some(hit),
                crate::LayoutControlSurfaceHit::ScrollbarCorner(_) => None,
            })
            .max_by_key(|hit| hit.paint_order)
    }

    fn control_surface_hits(
        &self,
        viewport_point: LayoutPoint,
    ) -> Vec<crate::LayoutControlSurfaceHit<N>> {
        let mut hits = Vec::new();
        for (index, layout_box) in self.boxes.iter().enumerate() {
            if !layout_box.visible || !layout_box.pointer_events {
                continue;
            }
            let Some(paint_order) = layout_box.control_paint_order else {
                continue;
            };
            let Some(source) = layout_box.geometry_source.or(layout_box.hit_source) else {
                continue;
            };
            let layout_box = &self.boxes[index];
            let is_root = layout_box.id == self.root_box;
            if !is_root && !self.point_passes_clip_chain(viewport_point, layout_box.clip_chain) {
                continue;
            }
            let local_to_viewport = if is_root {
                LayoutTransform2D::IDENTITY
            } else {
                layout_box.coordinate_space.local_to_viewport
            };
            let Some(viewport_to_local) = local_to_viewport.inverse() else {
                continue;
            };
            let local_point = viewport_to_local.map_point(viewport_point);
            if let Some(rect) = layout_box.scroll_extent.scrollbar_corner
                && rect.contains(local_point)
            {
                hits.push(crate::LayoutControlSurfaceHit::ScrollbarCorner(
                    crate::LayoutScrollbarCornerHit {
                        source,
                        rect,
                        local_point,
                        viewport_to_local,
                        paint_order,
                    },
                ));
                continue;
            }
            for scrollbar in [
                layout_box.scroll_extent.vertical_scrollbar,
                layout_box.scroll_extent.horizontal_scrollbar,
            ] {
                let Some(scrollbar) = scrollbar else {
                    continue;
                };
                let Some(part) = scrollbar.part_at(local_point) else {
                    continue;
                };
                hits.push(crate::LayoutControlSurfaceHit::Scrollbar(
                    crate::LayoutScrollbarHit {
                        source,
                        scrollbar,
                        part,
                        local_point,
                        viewport_to_local,
                        paint_order,
                    },
                ));
                break;
            }
        }
        hits
    }

    pub fn caret_position(&self, viewport_point: LayoutPoint) -> Option<LayoutCaretPosition<N>> {
        if !self.viewport.contains(viewport_point) {
            return None;
        }
        let mut clips = PointClipQuery::new(self, viewport_point);
        // Caret distance ties follow front-to-back order. Keep that ordering
        // local to the caret query rather than sorting every point query.
        let mut entries = self.hit_test_entries().collect::<Vec<_>>();
        entries.sort_by_key(|entry| std::cmp::Reverse(entry.paint_order));
        let top_entry = entries
            .iter()
            .find(|entry| self.hit_for_entry(entry, true, &mut clips).is_some())?;
        let top_box = self.fragment_box_id(top_entry.fragment)?;
        let text_entry = entries
            .iter()
            .filter(|entry| entry.is_text)
            .filter(|entry| {
                self.fragment_box_id(entry.fragment)
                    .is_some_and(|box_id| self.box_is_construction_descendant_of(box_id, top_box))
            })
            .filter_map(|entry| {
                self.hit_entry_distance_to_point(entry, viewport_point)
                    .map(|distance| (entry, distance))
            })
            .min_by(|(_, left), (_, right)| left.total_cmp(right))
            .map(|(entry, _)| entry);
        if let Some(entry) = text_entry {
            return self.caret_position_for_text_entry(entry, viewport_point);
        }

        let fragment = self.fragment(top_entry.fragment)?;
        let space = self.coordinate_space(top_entry.coordinate_space)?;
        let inverse = space.local_to_viewport.inverse()?;
        let local_point = inverse.map_point(viewport_point);
        let caret_x = if local_point.x <= fragment.rect.x + fragment.rect.width / 2.0 {
            fragment.rect.x
        } else {
            fragment.rect.right()
        };
        let rect = space.local_to_viewport.map_rect(LayoutRect::new(
            caret_x,
            fragment.rect.y,
            0.0,
            fragment.rect.height,
        ));
        Some(LayoutCaretPosition {
            source: top_entry.source,
            utf16_offset: None,
            rect,
            ancestor_boxes: self.ancestor_box_models(top_box),
        })
    }

    /// Streams candidates directly from canonical geometry, without retaining
    /// an index or duplicating the fragment set into a query-local vector.
    ///
    /// Fragment storage order is not paint order; callers select or sort by
    /// the explicit paint ordinal only after resolving geometric hits.
    fn hit_test_entries(&self) -> impl Iterator<Item = LayoutHitTestEntry<N>> + '_ {
        self.fragments.iter().filter_map(|fragment| {
            let paint_order = fragment.paint_order?;
            let (box_id, is_text) = match fragment.kind {
                LayoutFragmentKind::Box { box_id }
                | LayoutFragmentKind::InlineBox { box_id, .. } => (box_id, false),
                LayoutFragmentKind::Text { box_id, .. } => (box_id, true),
                LayoutFragmentKind::Line { .. } => return None,
            };
            let layout_box = self.boxes.get(box_id.index())?;
            if !layout_box.visible {
                return None;
            }
            Some(LayoutHitTestEntry {
                source: layout_box.hit_source?,
                fragment: fragment.id,
                coordinate_space: fragment.coordinate_space,
                clip_chain: fragment.clip_chain,
                local_rect: fragment.rect,
                paint_order,
                is_text,
                pointer_events: layout_box.pointer_events,
            })
        })
    }

    fn caret_position_for_text_entry(
        &self,
        entry: &LayoutHitTestEntry<N>,
        viewport_point: LayoutPoint,
    ) -> Option<LayoutCaretPosition<N>> {
        let fragment = self.fragment(entry.fragment)?;
        let LayoutFragmentKind::Text {
            box_id,
            source_utf16_range,
            rtl,
            ..
        } = &fragment.kind
        else {
            return None;
        };
        let space = self.coordinate_space(entry.coordinate_space)?;
        let local_point = space.local_to_viewport.inverse()?.map_point(viewport_point);
        let source_len = source_utf16_range
            .end
            .saturating_sub(source_utf16_range.start);
        let on_left_half = local_point.x <= fragment.rect.x + fragment.rect.width * 0.5;
        let at_source_start = if *rtl { !on_left_half } else { on_left_half };
        let fragment_offset = if at_source_start { 0 } else { source_len };
        let caret_x = if at_source_start == *rtl {
            fragment.rect.right()
        } else {
            fragment.rect.x
        };
        Some(LayoutCaretPosition {
            source: entry.source,
            utf16_offset: Some(source_utf16_range.start + fragment_offset),
            rect: space.local_to_viewport.map_rect(LayoutRect::new(
                caret_x,
                fragment.rect.y,
                0.0,
                fragment.rect.height,
            )),
            ancestor_boxes: self.ancestor_box_models(*box_id),
        })
    }

    fn hit_entry_distance_to_point(
        &self,
        entry: &LayoutHitTestEntry<N>,
        viewport_point: LayoutPoint,
    ) -> Option<f64> {
        let space = self.coordinate_space(entry.coordinate_space)?;
        let local_point = space.local_to_viewport.inverse()?.map_point(viewport_point);
        let nearest_local = LayoutPoint::new(
            local_point
                .x
                .clamp(entry.local_rect.x, entry.local_rect.right()),
            local_point
                .y
                .clamp(entry.local_rect.y, entry.local_rect.bottom()),
        );
        let nearest_viewport = space.local_to_viewport.map_point(nearest_local);
        if !self.point_passes_clip_chain(nearest_viewport, entry.clip_chain) {
            return None;
        }
        let dx = f64::from(nearest_viewport.x - viewport_point.x);
        let dy = f64::from(nearest_viewport.y - viewport_point.y);
        Some(dx * dx + dy * dy)
    }

    fn fragment_box_id(&self, fragment: LayoutFragmentId) -> Option<LayoutOutputBoxId> {
        match self.fragment(fragment)?.kind {
            LayoutFragmentKind::Box { box_id }
            | LayoutFragmentKind::InlineBox { box_id, .. }
            | LayoutFragmentKind::Text { box_id, .. } => Some(box_id),
            LayoutFragmentKind::Line { owner, .. } => Some(owner),
        }
    }

    fn box_is_construction_descendant_of(
        &self,
        mut candidate: LayoutOutputBoxId,
        ancestor: LayoutOutputBoxId,
    ) -> bool {
        loop {
            if candidate == ancestor {
                return true;
            }
            let Some(parent) = self.box_geometry(candidate).and_then(|box_| box_.parent) else {
                return false;
            };
            candidate = parent;
        }
    }

    fn ancestor_box_models(&self, mut box_id: LayoutOutputBoxId) -> Vec<(N, LayoutBoxModel)> {
        let mut seen = HashSet::new();
        let mut ancestors = Vec::new();
        loop {
            if let Some(source) = self
                .boxes
                .get(box_id.index())
                .and_then(|layout_box| layout_box.geometry_source)
                && seen.insert(source)
                && let Some(model) = self.box_model_for_source(source)
            {
                ancestors.push((source, model));
            }
            let Some(parent) = self.box_geometry(box_id).and_then(|box_| box_.parent) else {
                break;
            };
            box_id = parent;
        }
        ancestors
    }

    fn hit_for_entry(
        &self,
        entry: &LayoutHitTestEntry<N>,
        ignore_pointer_events_none: bool,
        clips: &mut PointClipQuery<'_, N>,
    ) -> Option<LayoutHit<N>> {
        if !ignore_pointer_events_none && !entry.pointer_events {
            return None;
        }
        let inverse = self
            .coordinate_space(entry.coordinate_space)?
            .local_to_viewport
            .inverse()?;
        let local_point = inverse.map_point(clips.point);
        if !entry.local_rect.contains(local_point) {
            return None;
        }
        if !clips.passes(entry.clip_chain) {
            return None;
        }
        let local_content_box = self
            .fragment(entry.fragment)
            .and_then(|fragment| fragment.box_model.map(|model| model.content))
            .or_else(|| {
                let box_id = self.fragment_box_id(entry.fragment)?;
                let geometry = self.box_geometry(box_id)?;
                Some(geometry.content_box)
            });
        Some(LayoutHit {
            source: entry.source,
            fragment: Some(entry.fragment),
            paint_order: Some(entry.paint_order),
            local_point,
            is_text: entry.is_text,
            local_content_box,
            viewport_to_local: inverse,
        })
    }
}

impl<N> FrozenLayoutTree<N>
where
    N: Copy + Debug + Eq + Hash,
{
    fn point_passes_clip(&self, viewport_point: LayoutPoint, node: &LayoutClipNode) -> bool {
        self.coordinate_space(node.coordinate_space)
            .and_then(|space| space.local_to_viewport.inverse())
            .is_some_and(|inverse| node.rect.contains(inverse.map_point(viewport_point)))
    }

    fn point_passes_clip_chain(
        &self,
        viewport_point: LayoutPoint,
        mut clip: Option<LayoutClipChainId>,
    ) -> bool {
        while let Some(id) = clip {
            let Some(node) = self.clip_chain.get(id.index()) else {
                return false;
            };
            if !self.point_passes_clip(viewport_point, node) {
                return false;
            }
            clip = node.parent;
        }
        true
    }
}

/// Scratch for exactly one viewport point. Shared clip ancestors are checked
/// once, and nothing survives the query or changes the retained tree.
struct PointClipQuery<'a, N: Copy + Debug + Eq + Hash> {
    tree: &'a FrozenLayoutTree<N>,
    point: LayoutPoint,
    results: Vec<Option<bool>>,
}

impl<'a, N: Copy + Debug + Eq + Hash> PointClipQuery<'a, N> {
    fn new(tree: &'a FrozenLayoutTree<N>, point: LayoutPoint) -> Self {
        Self {
            tree,
            point,
            results: Vec::new(),
        }
    }

    fn passes(&mut self, clip: Option<LayoutClipChainId>) -> bool {
        if clip.is_none() {
            return true;
        }
        // Allocate only after a candidate's local rectangle contains the point.
        if self.results.is_empty() {
            self.results.resize(self.tree.clip_chain.len(), None);
        }
        let mut current = clip;
        let passed = loop {
            let Some(id) = current else {
                break true;
            };
            let Some(result) = self.results.get(id.index()) else {
                break false;
            };
            if let Some(result) = result {
                break *result;
            }
            let node = &self.tree.clip_chain[id.index()];
            if !self.tree.point_passes_clip(self.point, node) {
                self.results[id.index()] = Some(false);
                break false;
            }
            current = node.parent;
        };
        // Propagate the chain result along the visited prefix. Walking it
        // twice avoids recursion or a second allocation for deep clip chains.
        current = clip;
        while let Some(id) = current {
            let Some(result) = self.results.get_mut(id.index()) else {
                break;
            };
            if result.is_some() {
                break;
            }
            *result = Some(passed);
            current = self.tree.clip_chain[id.index()].parent;
        }
        passed
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::{FrozenCoordinateSpace, LayoutSize, LayoutViewport};

    #[test]
    fn shared_clip_results_are_scoped_to_one_point() {
        let root = LayoutClipChainId::from_index(0);
        let broad = LayoutClipChainId::from_index(1);
        let narrow = LayoutClipChainId::from_index(2);
        let tree = FrozenLayoutTree::new(
            0_u8,
            LayoutViewport::new(100, 100, 1.0),
            LayoutPoint::ZERO,
            LayoutSize::new(100.0, 100.0),
            LayoutOutputBoxId::from_index(0),
            Vec::new(),
            Vec::new(),
            Vec::new(),
            FrozenCoordinateSpace {
                owner: None,
                local_to_viewport: LayoutTransform2D::IDENTITY,
                local_to_viewport_ignoring_css_transforms: LayoutTransform2D::IDENTITY,
            },
            [(None, 100.0), (Some(root), 200.0), (Some(root), 40.0)]
                .into_iter()
                .map(|(parent, size)| LayoutClipNode {
                    parent,
                    owner: None,
                    coordinate_space: LayoutCoordinateSpaceId::from_index(0),
                    rect: LayoutRect::new(0.0, 0.0, size, size),
                })
                .collect(),
            Vec::new(),
        );
        let mut query = PointClipQuery::new(&tree, LayoutPoint::new(25.0, 25.0));
        assert!(query.results.is_empty());
        assert!(query.passes(Some(broad)));
        assert_eq!(query.results, [Some(true), Some(true), None]);
        assert!(query.passes(Some(narrow)));
        assert_eq!(query.results, [Some(true), Some(true), Some(true)]);

        for point in [
            LayoutPoint::new(75.0, 25.0),
            LayoutPoint::new(150.0, 25.0),
            LayoutPoint::new(f32::NAN, 0.0),
        ] {
            let mut query = PointClipQuery::new(&tree, point);
            for clip in [Some(broad), Some(narrow), Some(root), None, Some(broad)] {
                assert_eq!(
                    query.passes(clip),
                    tree.point_passes_clip_chain(point, clip)
                );
            }
        }
    }
}