LibWeb: Use DOM Selection instead of ad-hoc layout tree selection

Before this patch, we were expressing the current selection as a range
between two points in the layout tree. This was a made-up concept I
called LayoutRange (2x LayoutPosition) and as it turns out, we don't
actually need it!

Instead, we can just use the Selection API from the Selection API spec.
This API expresses selection in terms of the DOM, and we already had
many of the building blocks implemented.

To ensure that selections get visually updated when the underlying Range
of an active Selection is programmatically manipulated, Range now has
an "associated Selection". If a range is updated while associated with
a selection, we recompute layout tree selection states and repaint the
page to make it user-visible.

9 files changed, 161 insertions, 71 deletions

diff --git a/Userland/Libraries/LibWeb/DOM/Document.cpp b/Userland/Libraries/LibWeb/DOM/Document.cpp
index ef391c340a..7d9e6dd13c 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Document.cpp
@@ -873,6 +873,8 @@ void Document::update_layout()
             page->client().page_did_layout();
     }
 
+    m_layout_root->recompute_selection_states();
+
     m_needs_layout = false;
     m_layout_update_timer->stop();
 }
diff --git a/Userland/Libraries/LibWeb/DOM/Range.cpp b/Userland/Libraries/LibWeb/DOM/Range.cpp
index 75f723b201..d8cfe26de4 100644
--- a/Userland/Libraries/LibWeb/DOM/Range.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Range.cpp
@@ -17,6 +17,7 @@
 #include <LibWeb/DOM/Text.h>
 #include <LibWeb/Geometry/DOMRect.h>
 #include <LibWeb/HTML/Window.h>
+#include <LibWeb/Layout/InitialContainingBlock.h>
 
 namespace Web::DOM {
 
@@ -71,6 +72,28 @@ void Range::initialize(JS::Realm& realm)
     set_prototype(&Bindings::ensure_web_prototype<Bindings::RangePrototype>(realm, "Range"));
 }
 
+void Range::visit_edges(Cell::Visitor& visitor)
+{
+    Base::visit_edges(visitor);
+    visitor.visit(m_associated_selection);
+}
+
+void Range::set_associated_selection(Badge<Selection::Selection>, JS::GCPtr<Selection::Selection> selection)
+{
+    m_associated_selection = selection;
+    update_associated_selection();
+}
+
+void Range::update_associated_selection()
+{
+    if (!m_associated_selection)
+        return;
+    if (auto* layout_root = m_associated_selection->document()->layout_node()) {
+        layout_root->recompute_selection_states();
+        layout_root->set_needs_display();
+    }
+}
+
 // https://dom.spec.whatwg.org/#concept-range-root
 Node& Range::root()
 {
@@ -173,6 +196,7 @@ WebIDL::ExceptionOr<void> Range::set_start_or_end(Node& node, u32 offset, StartO
         m_end_offset = offset;
     }
 
+    update_associated_selection();
     return {};
 }
 
@@ -353,6 +377,7 @@ WebIDL::ExceptionOr<void> Range::select(Node& node)
     m_end_container = *parent;
     m_end_offset = index + 1;
 
+    update_associated_selection();
     return {};
 }
 
@@ -370,11 +395,11 @@ void Range::collapse(bool to_start)
     if (to_start) {
         m_end_container = m_start_container;
         m_end_offset = m_start_offset;
-        return;
+    } else {
+        m_start_container = m_end_container;
+        m_start_offset = m_end_offset;
     }
-
-    m_start_container = m_end_container;
-    m_start_offset = m_end_offset;
+    update_associated_selection();
 }
 
 // https://dom.spec.whatwg.org/#dom-range-selectnodecontents
@@ -395,6 +420,7 @@ WebIDL::ExceptionOr<void> Range::select_node_contents(Node const& node)
     m_end_container = node;
     m_end_offset = length;
 
+    update_associated_selection();
     return {};
 }
 
diff --git a/Userland/Libraries/LibWeb/DOM/Range.h b/Userland/Libraries/LibWeb/DOM/Range.h
index d7e84cf1bc..52c1eeab0e 100644
--- a/Userland/Libraries/LibWeb/DOM/Range.h
+++ b/Userland/Libraries/LibWeb/DOM/Range.h
@@ -9,6 +9,7 @@
 #pragma once
 
 #include <LibWeb/DOM/AbstractRange.h>
+#include <LibWeb/Selection/Selection.h>
 
 namespace Web::DOM {
 
@@ -86,15 +87,20 @@ public:
 
     bool contains_node(Node const&) const;
 
+    void set_associated_selection(Badge<Selection::Selection>, JS::GCPtr<Selection::Selection>);
+
 private:
     explicit Range(Document&);
     Range(Node& start_container, u32 start_offset, Node& end_container, u32 end_offset);
 
     virtual void initialize(JS::Realm&) override;
+    virtual void visit_edges(Cell::Visitor&) override;
 
     Node& root();
     Node const& root() const;
 
+    void update_associated_selection();
+
     enum class StartOrEnd {
         Start,
         End,
@@ -108,6 +114,8 @@ private:
     WebIDL::ExceptionOr<void> insert(JS::NonnullGCPtr<Node>);
 
     bool partially_contains_node(Node const&) const;
+
+    JS::GCPtr<Selection::Selection> m_associated_selection;
 };
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.cpp b/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.cpp
index 4d56d16cde..df74329fbc 100644
--- a/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.cpp
+++ b/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.cpp
@@ -4,6 +4,7 @@
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
+#include <LibWeb/DOM/Range.h>
 #include <LibWeb/Dump.h>
 #include <LibWeb/Layout/InitialContainingBlock.h>
 #include <LibWeb/Painting/PaintableBox.h>
@@ -18,6 +19,11 @@ InitialContainingBlock::InitialContainingBlock(DOM::Document& document, NonnullR
 
 InitialContainingBlock::~InitialContainingBlock() = default;
 
+JS::GCPtr<Selection::Selection> InitialContainingBlock::selection() const
+{
+    return const_cast<DOM::Document&>(document()).get_selection();
+}
+
 void InitialContainingBlock::build_stacking_context_tree_if_needed()
 {
     if (paint_box()->stacking_context())
@@ -56,40 +62,52 @@ void InitialContainingBlock::paint_all_phases(PaintContext& context)
 
 void InitialContainingBlock::recompute_selection_states()
 {
-    SelectionState state = SelectionState::None;
-
-    auto selection = this->selection().normalized();
-
+    // 1. Start by resetting the selection state of all layout nodes to None.
     for_each_in_inclusive_subtree([&](auto& layout_node) {
-        if (!selection.is_valid()) {
-            // Everything gets SelectionState::None.
-        } else if (&layout_node == selection.start().layout_node && &layout_node == selection.end().layout_node) {
-            state = SelectionState::StartAndEnd;
-        } else if (&layout_node == selection.start().layout_node) {
-            state = SelectionState::Start;
-        } else if (&layout_node == selection.end().layout_node) {
-            state = SelectionState::End;
-        } else {
-            if (state == SelectionState::Start)
-                state = SelectionState::Full;
-            else if (state == SelectionState::End || state == SelectionState::StartAndEnd)
-                state = SelectionState::None;
-        }
-        layout_node.set_selection_state(state);
+        layout_node.set_selection_state(SelectionState::None);
         return IterationDecision::Continue;
     });
-}
 
-void InitialContainingBlock::set_selection(LayoutRange const& selection)
-{
-    m_selection = selection;
-    recompute_selection_states();
-}
+    // 2. If there is no active Selection or selected Range, return.
+    auto selection = document().get_selection();
+    if (!selection)
+        return;
+    auto range = selection->range();
+    if (!range)
+        return;
 
-void InitialContainingBlock::set_selection_end(LayoutPosition const& position)
-{
-    m_selection.set_end(position);
-    recompute_selection_states();
+    auto* start_container = range->start_container();
+    auto* end_container = range->end_container();
+
+    // 3. If the selection starts and ends in the same text node, mark it as StartAndEnd and return.
+    if (start_container == end_container && is<DOM::Text>(*start_container)) {
+        if (auto* layout_node = start_container->layout_node()) {
+            layout_node->set_selection_state(SelectionState::StartAndEnd);
+        }
+        return;
+    }
+
+    // 4. Mark the selection start node as Start (if text) or Full (if anything else).
+    if (auto* layout_node = start_container->layout_node()) {
+        if (is<DOM::Text>(*start_container))
+            layout_node->set_selection_state(SelectionState::Start);
+        else
+            layout_node->set_selection_state(SelectionState::Full);
+    }
+
+    // 5. Mark the selection end node as End (if text) or Full (if anything else).
+    if (auto* layout_node = end_container->layout_node()) {
+        if (is<DOM::Text>(*end_container))
+            layout_node->set_selection_state(SelectionState::End);
+        else
+            layout_node->set_selection_state(SelectionState::Full);
+    }
+
+    // 6. Mark the nodes between start node and end node (in tree order) as Full.
+    for (auto* node = start_container->next_in_pre_order(); node && node != end_container; node = node->next_in_pre_order()) {
+        if (auto* layout_node = node->layout_node())
+            layout_node->set_selection_state(SelectionState::Full);
+    }
 }
 
 }
diff --git a/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.h b/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.h
index 10c5f75074..b653c05746 100644
--- a/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.h
+++ b/Userland/Libraries/LibWeb/Layout/InitialContainingBlock.h
@@ -9,6 +9,7 @@
 #include <LibWeb/DOM/Document.h>
 #include <LibWeb/Layout/BlockContainer.h>
 #include <LibWeb/Layout/LayoutPosition.h>
+#include <LibWeb/Selection/Selection.h>
 
 namespace Web::Layout {
 
@@ -23,9 +24,7 @@ public:
 
     void paint_all_phases(PaintContext&);
 
-    LayoutRange const& selection() const { return m_selection; }
-    void set_selection(LayoutRange const&);
-    void set_selection_end(LayoutPosition const&);
+    JS::GCPtr<Selection::Selection> selection() const;
 
     void build_stacking_context_tree_if_needed();
     void recompute_selection_states();
@@ -33,8 +32,6 @@ public:
 private:
     void build_stacking_context_tree();
     virtual bool is_initial_containing_block_box() const override { return true; }
-
-    LayoutRange m_selection;
 };
 
 template<>
diff --git a/Userland/Libraries/LibWeb/Layout/LineBoxFragment.cpp b/Userland/Libraries/LibWeb/Layout/LineBoxFragment.cpp
index 4e8b9d5ffe..584e415d3a 100644
--- a/Userland/Libraries/LibWeb/Layout/LineBoxFragment.cpp
+++ b/Userland/Libraries/LibWeb/Layout/LineBoxFragment.cpp
@@ -1,10 +1,11 @@
 /*
- * Copyright (c) 2018-2020, Andreas Kling <kling@serenityos.org>
+ * Copyright (c) 2018-2023, Andreas Kling <kling@serenityos.org>
  *
  * SPDX-License-Identifier: BSD-2-Clause
  */
 
 #include <AK/Utf8View.h>
+#include <LibWeb/DOM/Range.h>
 #include <LibWeb/Layout/InitialContainingBlock.h>
 #include <LibWeb/Layout/LayoutState.h>
 #include <LibWeb/Layout/LineBoxFragment.h>
@@ -73,28 +74,33 @@ CSSPixelRect LineBoxFragment::selection_rect(Gfx::Font const& font) const
     if (layout_node().selection_state() == Node::SelectionState::Full)
         return absolute_rect();
 
-    auto selection = layout_node().root().selection().normalized();
-    if (!selection.is_valid())
-        return {};
     if (!is<TextNode>(layout_node()))
         return {};
 
-    auto const start_index = m_start;
-    auto const end_index = m_start + m_length;
+    auto selection = layout_node().root().selection();
+    if (!selection)
+        return {};
+    auto range = selection->range();
+    if (!range)
+        return {};
+
+    // FIXME: m_start and m_length should be unsigned and then we won't need these casts.
+    auto const start_index = static_cast<unsigned>(m_start);
+    auto const end_index = static_cast<unsigned>(m_start) + static_cast<unsigned>(m_length);
     auto text = this->text();
 
     if (layout_node().selection_state() == Node::SelectionState::StartAndEnd) {
         // we are in the start/end node (both the same)
-        if (start_index > selection.end().index_in_node)
+        if (start_index > range->end_offset())
             return {};
-        if (end_index < selection.start().index_in_node)
+        if (end_index < range->start_offset())
             return {};
 
-        if (selection.start().index_in_node == selection.end().index_in_node)
+        if (range->start_offset() == range->end_offset())
             return {};
 
-        auto selection_start_in_this_fragment = max(0, selection.start().index_in_node - m_start);
-        auto selection_end_in_this_fragment = min(m_length, selection.end().index_in_node - m_start);
+        auto selection_start_in_this_fragment = max(0, range->start_offset() - m_start);
+        auto selection_end_in_this_fragment = min(m_length, range->end_offset() - m_start);
         auto pixel_distance_to_first_selected_character = font.width(text.substring_view(0, selection_start_in_this_fragment));
         auto pixel_width_of_selection = font.width(text.substring_view(selection_start_in_this_fragment, selection_end_in_this_fragment - selection_start_in_this_fragment)) + 1;
 
@@ -106,10 +112,10 @@ CSSPixelRect LineBoxFragment::selection_rect(Gfx::Font const& font) const
     }
     if (layout_node().selection_state() == Node::SelectionState::Start) {
         // we are in the start node
-        if (end_index < selection.start().index_in_node)
+        if (end_index < range->start_offset())
             return {};
 
-        auto selection_start_in_this_fragment = max(0, selection.start().index_in_node - m_start);
+        auto selection_start_in_this_fragment = max(0, range->start_offset() - m_start);
         auto selection_end_in_this_fragment = m_length;
         auto pixel_distance_to_first_selected_character = font.width(text.substring_view(0, selection_start_in_this_fragment));
         auto pixel_width_of_selection = font.width(text.substring_view(selection_start_in_this_fragment, selection_end_in_this_fragment - selection_start_in_this_fragment)) + 1;
@@ -122,11 +128,11 @@ CSSPixelRect LineBoxFragment::selection_rect(Gfx::Font const& font) const
     }
     if (layout_node().selection_state() == Node::SelectionState::End) {
         // we are in the end node
-        if (start_index > selection.end().index_in_node)
+        if (start_index > range->end_offset())
             return {};
 
         auto selection_start_in_this_fragment = 0;
-        auto selection_end_in_this_fragment = min(selection.end().index_in_node - m_start, m_length);
+        auto selection_end_in_this_fragment = min(range->end_offset() - m_start, m_length);
         auto pixel_distance_to_first_selected_character = font.width(text.substring_view(0, selection_start_in_this_fragment));
         auto pixel_width_of_selection = font.width(text.substring_view(selection_start_in_this_fragment, selection_end_in_this_fragment - selection_start_in_this_fragment)) + 1;
 
diff --git a/Userland/Libraries/LibWeb/Page/EventHandler.cpp b/Userland/Libraries/LibWeb/Page/EventHandler.cpp
index c493602cb1..f42049812a 100644
--- a/Userland/Libraries/LibWeb/Page/EventHandler.cpp
+++ b/Userland/Libraries/LibWeb/Page/EventHandler.cpp
@@ -399,7 +399,9 @@ bool EventHandler::handle_mousedown(CSSPixelPoint position, unsigned button, uns
                 // FIXME: This is all rather strange. Find a better solution.
                 if (!did_focus_something) {
                     m_browsing_context.set_cursor_position(DOM::Position(*paintable->dom_node(), result->index_in_node));
-                    layout_root()->set_selection({ { paintable->layout_node(), result->index_in_node }, {} });
+                    if (auto selection = document->get_selection()) {
+                        (void)selection->set_base_and_extent(*paintable->dom_node(), result->index_in_node, *paintable->dom_node(), result->index_in_node);
+                    }
                     m_in_mouse_selection = true;
                 }
             }
@@ -495,7 +497,13 @@ bool EventHandler::handle_mousemove(CSSPixelPoint position, unsigned buttons, un
             auto hit = paint_root()->hit_test(position, Painting::HitTestType::TextCursor);
             if (start_index.has_value() && hit.has_value() && hit->dom_node()) {
                 m_browsing_context.set_cursor_position(DOM::Position(*hit->dom_node(), *start_index));
-                layout_root()->set_selection_end({ hit->paintable->layout_node(), hit->index_in_node });
+                if (auto selection = document.get_selection()) {
+                    auto anchor_node = selection->anchor_node();
+                    if (anchor_node)
+                        (void)selection->set_base_and_extent(*anchor_node, selection->anchor_offset(), *hit->paintable->dom_node(), hit->index_in_node);
+                    else
+                        (void)selection->set_base_and_extent(*hit->paintable->dom_node(), hit->index_in_node, *hit->paintable->dom_node(), hit->index_in_node);
+                }
                 m_browsing_context.set_needs_display();
             }
             if (auto* page = m_browsing_context.page())
@@ -607,7 +615,9 @@ bool EventHandler::handle_doubleclick(CSSPixelPoint position, unsigned button, u
             }();
 
             m_browsing_context.set_cursor_position(DOM::Position(*paintable->dom_node(), first_word_break_after));
-            layout_root()->set_selection({ { paintable->layout_node(), first_word_break_before }, { paintable->layout_node(), first_word_break_after } });
+            if (auto selection = node->document().get_selection()) {
+                (void)selection->set_base_and_extent(*paintable->dom_node(), first_word_break_before, *paintable->dom_node(), first_word_break_after);
+            }
         }
     }
 
@@ -696,18 +706,16 @@ bool EventHandler::handle_keydown(KeyCode key, unsigned modifiers, u32 code_poin
     if (!document->layout_node())
         return false;
 
-    JS::NonnullGCPtr<Layout::InitialContainingBlock> layout_root = *document->layout_node();
-
     if (key == KeyCode::Key_Tab) {
         if (modifiers & KeyModifier::Mod_Shift)
             return focus_previous_element();
         return focus_next_element();
     }
 
-    if (layout_root->selection().is_valid()) {
-        auto range = layout_root->selection().to_dom_range()->normalized();
-        if (range->start_container()->is_editable()) {
-            layout_root->set_selection({});
+    if (auto selection = document->get_selection()) {
+        auto range = selection->range();
+        if (range && range->start_container()->is_editable()) {
+            selection->remove_all_ranges();
 
             // FIXME: This doesn't work for some reason?
             m_browsing_context.set_cursor_position({ *range->start_container(), range->start_offset() });
diff --git a/Userland/Libraries/LibWeb/Selection/Selection.cpp b/Userland/Libraries/LibWeb/Selection/Selection.cpp
index 6305d5fec2..72aa62b0e6 100644
--- a/Userland/Libraries/LibWeb/Selection/Selection.cpp
+++ b/Userland/Libraries/LibWeb/Selection/Selection.cpp
@@ -136,7 +136,7 @@ void Selection::add_range(JS::NonnullGCPtr<DOM::Range> range)
         return;
 
     // 3. Set this's range to range by a strong reference (not by making a copy).
-    m_range = range;
+    set_range(range);
 }
 
 // https://w3c.github.io/selection-api/#dom-selection-removerange
@@ -144,7 +144,7 @@ WebIDL::ExceptionOr<void> Selection::remove_range(JS::NonnullGCPtr<DOM::Range> r
 {
     // The method must make this empty by disassociating its range if this's range is range.
     if (m_range == range) {
-        m_range = nullptr;
+        set_range(nullptr);
         return {};
     }
 
@@ -156,7 +156,7 @@ WebIDL::ExceptionOr<void> Selection::remove_range(JS::NonnullGCPtr<DOM::Range> r
 void Selection::remove_all_ranges()
 {
     // The method must make this empty by disassociating its range if this has an associated range.
-    m_range = nullptr;
+    set_range(nullptr);
 }
 
 // https://w3c.github.io/selection-api/#dom-selection-empty
@@ -191,7 +191,7 @@ WebIDL::ExceptionOr<void> Selection::collapse(JS::GCPtr<DOM::Node> node, unsigne
     TRY(new_range->set_start(*node, offset));
 
     // 6. Set this's range to newRange.
-    m_range = new_range;
+    set_range(new_range);
 
     return {};
 }
@@ -219,7 +219,7 @@ WebIDL::ExceptionOr<void> Selection::collapse_to_start()
     TRY(new_range->set_end(*anchor_node(), m_range->start_offset()));
 
     // 4. Then set this's range to the newly-created range.
-    m_range = new_range;
+    set_range(new_range);
     return {};
 }
 
@@ -239,7 +239,8 @@ WebIDL::ExceptionOr<void> Selection::collapse_to_end()
     TRY(new_range->set_end(*anchor_node(), m_range->end_offset()));
 
     // 4. Then set this's range to the newly-created range.
-    m_range = new_range;
+    set_range(new_range);
+
     return {};
 }
 
@@ -280,7 +281,7 @@ WebIDL::ExceptionOr<void> Selection::extend(JS::NonnullGCPtr<DOM::Node> node, un
     }
 
     // 8. Set this's range to newRange.
-    m_range = new_range;
+    set_range(new_range);
 
     // 9. If newFocus is before oldAnchor, set this's direction to backwards. Otherwise, set it to forwards.
     if (new_focus_node->is_before(old_anchor_node)) {
@@ -325,7 +326,7 @@ WebIDL::ExceptionOr<void> Selection::set_base_and_extent(JS::NonnullGCPtr<DOM::N
     }
 
     // 6. Set this's range to newRange.
-    m_range = new_range;
+    set_range(new_range);
 
     // 7. If focus is before anchor, set this's direction to backwards. Otherwise, set it to forwards
     // NOTE: "Otherwise" can be seen as "focus is equal to or after anchor".
@@ -355,7 +356,7 @@ WebIDL::ExceptionOr<void> Selection::select_all_children(JS::NonnullGCPtr<DOM::N
     TRY(new_range->set_end(node, child_count));
 
     // 5. Set this's range to newRange.
-    m_range = new_range;
+    set_range(new_range);
 
     // 6. Set this's direction to forwards.
     m_direction = Direction::Forwards;
@@ -429,9 +430,28 @@ DeprecatedString Selection::to_deprecated_string() const
     return m_range->to_deprecated_string();
 }
 
+JS::NonnullGCPtr<DOM::Document> Selection::document() const
+{
+    return m_document;
+}
+
 JS::GCPtr<DOM::Range> Selection::range() const
 {
     return m_range;
 }
 
+void Selection::set_range(JS::GCPtr<DOM::Range> range)
+{
+    if (m_range == range)
+        return;
+
+    if (m_range)
+        m_range->set_associated_selection({}, nullptr);
+
+    m_range = range;
+
+    if (m_range)
+        m_range->set_associated_selection({}, this);
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/Selection/Selection.h b/Userland/Libraries/LibWeb/Selection/Selection.h
index a96a6e4fc1..581336e39b 100644
--- a/Userland/Libraries/LibWeb/Selection/Selection.h
+++ b/Userland/Libraries/LibWeb/Selection/Selection.h
@@ -53,6 +53,9 @@ public:
     // Non-standard convenience accessor for the selection's range.
     JS::GCPtr<DOM::Range> range() const;
 
+    // Non-standard accessor for the selection's document.
+    JS::NonnullGCPtr<DOM::Document> document() const;
+
 private:
     Selection(JS::NonnullGCPtr<JS::Realm>, JS::NonnullGCPtr<DOM::Document>);
 
@@ -61,6 +64,8 @@ private:
     virtual void initialize(JS::Realm&) override;
     virtual void visit_edges(Cell::Visitor&) override;
 
+    void set_range(JS::GCPtr<DOM::Range>);
+
     // https://w3c.github.io/selection-api/#dfn-empty
     JS::GCPtr<DOM::Range> m_range;