LibWeb: Move hit testing to the painting tree

6 files changed, 163 insertions, 18 deletions

diff --git a/Userland/Libraries/LibWeb/Painting/Paintable.cpp b/Userland/Libraries/LibWeb/Painting/Paintable.cpp
index 88b384dcdc..008e871def 100644
--- a/Userland/Libraries/LibWeb/Painting/Paintable.cpp
+++ b/Userland/Libraries/LibWeb/Painting/Paintable.cpp
@@ -38,4 +38,9 @@ bool Paintable::handle_mousewheel(Badge<EventHandler>, Gfx::IntPoint const&, uns
     return false;
 }
 
+HitTestResult Paintable::hit_test(Gfx::IntPoint const&, HitTestType) const
+{
+    VERIFY_NOT_REACHED();
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/Painting/Paintable.h b/Userland/Libraries/LibWeb/Painting/Paintable.h
index ecb9a66759..ea81a8d867 100644
--- a/Userland/Libraries/LibWeb/Painting/Paintable.h
+++ b/Userland/Libraries/LibWeb/Painting/Paintable.h
@@ -10,10 +10,35 @@
 #include <LibWeb/Layout/Box.h>
 #include <LibWeb/Layout/LineBox.h>
 #include <LibWeb/Layout/TextNode.h>
-#include <LibWeb/Painting/StackingContext.h>
 
 namespace Web::Painting {
 
+enum class PaintPhase {
+    Background,
+    Border,
+    Foreground,
+    FocusOutline,
+    Overlay,
+};
+
+struct HitTestResult {
+    RefPtr<Painting::Paintable> paintable;
+    int index_in_node { 0 };
+
+    enum InternalPosition {
+        None,
+        Before,
+        Inside,
+        After,
+    };
+    InternalPosition internal_position { None };
+};
+
+enum class HitTestType {
+    Exact,      // Exact matches only
+    TextCursor, // Clicking past the right/bottom edge of text will still hit the text
+};
+
 class Paintable : public RefCounted<Paintable> {
     AK_MAKE_NONMOVABLE(Paintable);
     AK_MAKE_NONCOPYABLE(Paintable);
@@ -25,6 +50,8 @@ public:
     virtual void before_children_paint(PaintContext&, PaintPhase) const { }
     virtual void after_children_paint(PaintContext&, PaintPhase) const { }
 
+    virtual HitTestResult hit_test(Gfx::IntPoint const&, HitTestType) const;
+
     virtual bool wants_mouse_events() const { return false; }
     virtual void handle_mousedown(Badge<EventHandler>, const Gfx::IntPoint&, unsigned button, unsigned modifiers);
     virtual void handle_mouseup(Badge<EventHandler>, const Gfx::IntPoint&, unsigned button, unsigned modifiers);
diff --git a/Userland/Libraries/LibWeb/Painting/PaintableBox.cpp b/Userland/Libraries/LibWeb/Painting/PaintableBox.cpp
index 3315a654cd..b0ce44c761 100644
--- a/Userland/Libraries/LibWeb/Painting/PaintableBox.cpp
+++ b/Userland/Libraries/LibWeb/Painting/PaintableBox.cpp
@@ -10,6 +10,7 @@
 #include <LibWeb/Painting/BackgroundPainting.h>
 #include <LibWeb/Painting/PaintableBox.h>
 #include <LibWeb/Painting/ShadowPainting.h>
+#include <LibWeb/Painting/StackingContext.h>
 
 namespace Web::Painting {
 
@@ -307,4 +308,116 @@ Layout::BlockContainer& PaintableWithLines::layout_box()
     return static_cast<Layout::BlockContainer&>(PaintableBox::layout_box());
 }
 
+void PaintableBox::set_stacking_context(NonnullOwnPtr<StackingContext> stacking_context)
+{
+    m_stacking_context = move(stacking_context);
+}
+
+template<typename Callback>
+void PaintableBox::for_each_child_in_paint_order(Callback callback) const
+{
+    // Element traversal using the order defined in https://www.w3.org/TR/CSS2/zindex.html#painting-order.
+    // Note: Some steps are skipped because they are not relevant to node traversal.
+
+    // 3. Stacking contexts formed by positioned descendants with negative z-indices (excluding 0) in z-index order
+    //    (most negative first) then tree order.
+    // FIXME: This does not retrieve elements in the z-index order.
+    layout_box().for_each_child([&](auto& child) {
+        if (!child.is_positioned() || !is<Layout::Box>(child))
+            return;
+
+        auto& box_child = verify_cast<Layout::Box>(child);
+        auto* stacking_context = box_child.paint_box()->stacking_context();
+        if (stacking_context && box_child.computed_values().z_index().has_value() && box_child.computed_values().z_index().value() < 0)
+            callback(child);
+    });
+
+    // 4. For all its in-flow, non-positioned, block-level descendants in tree order: If the element is a block, list-item,
+    //    or other block equivalent:
+    layout_box().for_each_child([&](auto& child) {
+        if (is<Layout::Box>(child) && verify_cast<Layout::Box>(child).paint_box()->stacking_context())
+            return;
+        if (!child.is_positioned())
+            callback(child);
+    });
+
+    // 5. All non-positioned floating descendants, in tree order. For each one of these, treat the element as if it created
+    //    a new stacking context, but any positioned descendants and descendants which actually create a new stacking context
+    //    should be considered part of the parent stacking context, not this new one.
+    layout_box().for_each_child([&](auto& child) {
+        if (is<Layout::Box>(child) && verify_cast<Layout::Box>(child).paint_box()->stacking_context())
+            return;
+        if (child.is_positioned())
+            callback(child);
+    });
+
+    // 8. All positioned descendants with 'z-index: auto' or 'z-index: 0', in tree order. For those with 'z-index: auto', treat
+    //    the element as if it created a new stacking context, but any positioned descendants and descendants which actually
+    //    create a new stacking context should be considered part of the parent stacking context, not this new one. For those
+    //    with 'z-index: 0', treat the stacking context generated atomically.
+    layout_box().for_each_child([&](auto& child) {
+        if (!child.is_positioned() || !is<Layout::Box>(child))
+            return;
+
+        auto& box_child = verify_cast<Layout::Box>(child);
+        auto* stacking_context = box_child.paint_box()->stacking_context();
+        if (stacking_context && box_child.computed_values().z_index().has_value() && box_child.computed_values().z_index().value() == 0)
+            callback(child);
+    });
+
+    // 9. Stacking contexts formed by positioned descendants with z-indices greater than or equal to 1 in z-index order
+    //    (smallest first) then tree order.
+    // FIXME: This does not retrieve elements in the z-index order.
+    layout_box().for_each_child([&](auto& child) {
+        if (!child.is_positioned() || !is<Layout::Box>(child))
+            return;
+
+        auto& box_child = verify_cast<Layout::Box>(child);
+        auto* stacking_context = box_child.paint_box()->stacking_context();
+        if (stacking_context && box_child.computed_values().z_index().has_value() && box_child.computed_values().z_index().value() > 0)
+            callback(child);
+    });
+}
+
+HitTestResult PaintableBox::hit_test(Gfx::IntPoint const& position, HitTestType type) const
+{
+    if (layout_box().is_initial_containing_block_box())
+        return stacking_context()->hit_test(position, type);
+
+    HitTestResult result { absolute_border_box_rect().contains(position.x(), position.y()) ? this : nullptr };
+    for_each_child_in_paint_order([&](auto& child) {
+        if (child.paintable()) {
+            auto child_result = child.paintable()->hit_test(position, type);
+            if (child_result.paintable)
+                result = child_result;
+        }
+    });
+    return result;
+}
+
+HitTestResult PaintableWithLines::hit_test(const Gfx::IntPoint& position, HitTestType type) const
+{
+    if (!layout_box().children_are_inline())
+        return PaintableBox::hit_test(position, type);
+
+    HitTestResult last_good_candidate;
+    for (auto& line_box : m_line_boxes) {
+        for (auto& fragment : line_box.fragments()) {
+            if (is<Layout::Box>(fragment.layout_node()) && static_cast<Layout::Box const&>(fragment.layout_node()).paint_box()->stacking_context())
+                continue;
+            if (enclosing_int_rect(fragment.absolute_rect()).contains(position)) {
+                if (is<Layout::BlockContainer>(fragment.layout_node()) && fragment.layout_node().paintable())
+                    return fragment.layout_node().paintable()->hit_test(position, type);
+                return { fragment.layout_node().paintable(), fragment.text_index_at(position.x()) };
+            }
+            if (fragment.absolute_rect().top() <= position.y())
+                last_good_candidate = { fragment.layout_node().paintable(), fragment.text_index_at(position.x()) };
+        }
+    }
+
+    if (type == HitTestType::TextCursor && last_good_candidate.paintable)
+        return last_good_candidate;
+    return { absolute_border_box_rect().contains(position.x(), position.y()) ? this : nullptr };
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/Painting/PaintableBox.h b/Userland/Libraries/LibWeb/Painting/PaintableBox.h
index 43dc3ef0b8..95545196dc 100644
--- a/Userland/Libraries/LibWeb/Painting/PaintableBox.h
+++ b/Userland/Libraries/LibWeb/Painting/PaintableBox.h
@@ -103,7 +103,7 @@ public:
 
     StackingContext* stacking_context() { return m_stacking_context; }
     StackingContext const* stacking_context() const { return m_stacking_context; }
-    void set_stacking_context(NonnullOwnPtr<Painting::StackingContext> context) { m_stacking_context = move(context); }
+    void set_stacking_context(NonnullOwnPtr<Painting::StackingContext>);
     StackingContext* enclosing_stacking_context();
 
     DOM::Node const* dom_node() const { return layout_box().dom_node(); }
@@ -115,6 +115,8 @@ public:
     virtual void before_children_paint(PaintContext&, PaintPhase) const override;
     virtual void after_children_paint(PaintContext&, PaintPhase) const override;
 
+    virtual HitTestResult hit_test(Gfx::IntPoint const&, HitTestType) const override;
+
 protected:
     explicit PaintableBox(Layout::Box const&);
 
@@ -123,6 +125,9 @@ protected:
     virtual void paint_box_shadow(PaintContext&) const;
 
 private:
+    template<typename Callback>
+    void for_each_child_in_paint_order(Callback) const;
+
     Painting::BorderRadiusData normalized_border_radius_data() const;
 
     OwnPtr<Painting::StackingContext> m_stacking_context;
@@ -157,6 +162,8 @@ public:
     virtual bool wants_mouse_events() const override { return false; }
     virtual bool handle_mousewheel(Badge<EventHandler>, const Gfx::IntPoint&, unsigned buttons, unsigned modifiers, int wheel_delta_x, int wheel_delta_y) override;
 
+    virtual HitTestResult hit_test(Gfx::IntPoint const&, HitTestType) const override;
+
 private:
     PaintableWithLines(Layout::BlockContainer const&);
 
diff --git a/Userland/Libraries/LibWeb/Painting/StackingContext.cpp b/Userland/Libraries/LibWeb/Painting/StackingContext.cpp
index ae2f106aa6..fb0dc9d51c 100644
--- a/Userland/Libraries/LibWeb/Painting/StackingContext.cpp
+++ b/Userland/Libraries/LibWeb/Painting/StackingContext.cpp
@@ -157,7 +157,7 @@ void StackingContext::paint(PaintContext& context) const
     }
 }
 
-Layout::HitTestResult StackingContext::hit_test(const Gfx::IntPoint& position, Layout::HitTestType type) const
+HitTestResult StackingContext::hit_test(Gfx::IntPoint const& position, HitTestType type) const
 {
     // NOTE: Hit testing basically happens in reverse painting order.
     // https://www.w3.org/TR/CSS22/visuren.html#z-index
@@ -172,11 +172,11 @@ Layout::HitTestResult StackingContext::hit_test(const Gfx::IntPoint& position, L
             return result;
     }
 
-    Layout::HitTestResult result;
+    HitTestResult result;
     // 6. the child stacking contexts with stack level 0 and the positioned descendants with stack level 0.
     m_box.for_each_in_subtree_of_type<Layout::Box>([&](Layout::Box const& box) {
         if (box.is_positioned() && !box.paint_box()->stacking_context()) {
-            result = box.hit_test(position, type);
+            result = box.paint_box()->hit_test(position, type);
             if (result.paintable)
                 return IterationDecision::Break;
         }
@@ -187,7 +187,7 @@ Layout::HitTestResult StackingContext::hit_test(const Gfx::IntPoint& position, L
 
     // 5. the in-flow, inline-level, non-positioned descendants, including inline tables and inline blocks.
     if (m_box.children_are_inline() && is<Layout::BlockContainer>(m_box)) {
-        auto result = m_box.hit_test(position, type);
+        auto result = m_box.paint_box()->hit_test(position, type);
         if (result.paintable)
             return result;
     }
@@ -195,7 +195,7 @@ Layout::HitTestResult StackingContext::hit_test(const Gfx::IntPoint& position, L
     // 4. the non-positioned floats.
     m_box.for_each_in_subtree_of_type<Layout::Box>([&](Layout::Box const& box) {
         if (box.is_floating()) {
-            result = box.hit_test(position, type);
+            result = box.paint_box()->hit_test(position, type);
             if (result.paintable)
                 return IterationDecision::Break;
         }
@@ -206,7 +206,7 @@ Layout::HitTestResult StackingContext::hit_test(const Gfx::IntPoint& position, L
     if (!m_box.children_are_inline()) {
         m_box.for_each_in_subtree_of_type<Layout::Box>([&](Layout::Box const& box) {
             if (!box.is_absolutely_positioned() && !box.is_floating()) {
-                result = box.hit_test(position, type);
+                result = box.paint_box()->hit_test(position, type);
                 if (result.paintable)
                     return IterationDecision::Break;
             }
@@ -228,7 +228,7 @@ Layout::HitTestResult StackingContext::hit_test(const Gfx::IntPoint& position, L
 
     // 1. the background and borders of the element forming the stacking context.
     if (m_box.paint_box()->absolute_border_box_rect().contains(position.to_type<float>())) {
-        return Layout::HitTestResult {
+        return HitTestResult {
             .paintable = m_box.paintable(),
         };
     }
diff --git a/Userland/Libraries/LibWeb/Painting/StackingContext.h b/Userland/Libraries/LibWeb/Painting/StackingContext.h
index ebbc384387..0851a93984 100644
--- a/Userland/Libraries/LibWeb/Painting/StackingContext.h
+++ b/Userland/Libraries/LibWeb/Painting/StackingContext.h
@@ -8,17 +8,10 @@
 
 #include <AK/Vector.h>
 #include <LibWeb/Layout/Node.h>
+#include <LibWeb/Painting/Paintable.h>
 
 namespace Web::Painting {
 
-enum class PaintPhase {
-    Background,
-    Border,
-    Foreground,
-    FocusOutline,
-    Overlay,
-};
-
 class StackingContext {
 public:
     StackingContext(Layout::Box&, StackingContext* parent);
@@ -36,7 +29,7 @@ public:
 
     void paint_descendants(PaintContext&, Layout::Node&, StackingContextPaintPhase) const;
     void paint(PaintContext&) const;
-    Layout::HitTestResult hit_test(Gfx::IntPoint const&, Layout::HitTestType) const;
+    HitTestResult hit_test(Gfx::IntPoint const&, HitTestType) const;
 
     void dump(int indent = 0) const;