LibWeb: Make Range.setStart and Range.setEnd spec compliant

These functions are way more involved than simply setting their
respective boundary points :^)

6 files changed, 185 insertions, 11 deletions

diff --git a/Userland/Libraries/LibWeb/DOM/Attribute.h b/Userland/Libraries/LibWeb/DOM/Attribute.h
index f441e1390d..5019a25926 100644
--- a/Userland/Libraries/LibWeb/DOM/Attribute.h
+++ b/Userland/Libraries/LibWeb/DOM/Attribute.h
@@ -46,4 +46,7 @@ private:
     WeakPtr<Element> m_owner_element;
 };
 
+template<>
+inline bool Node::fast_is<Attribute>() const { return is_attribute(); }
+
 }
diff --git a/Userland/Libraries/LibWeb/DOM/Node.cpp b/Userland/Libraries/LibWeb/DOM/Node.cpp
index a644552187..a20c94011e 100644
--- a/Userland/Libraries/LibWeb/DOM/Node.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Node.cpp
@@ -973,4 +973,21 @@ String Node::debug_description() const
     return builder.to_string();
 }
 
+// https://dom.spec.whatwg.org/#concept-node-length
+size_t Node::length() const
+{
+    // 1. If node is a DocumentType or Attr node, then return 0.
+    if (is_document_type() || is_attribute())
+        return 0;
+
+    // 2. If node is a CharacterData node, then return node’s data’s length.
+    if (is_character_data()) {
+        auto* character_data_node = verify_cast<CharacterData>(this);
+        return character_data_node->data().length();
+    }
+
+    // 3. Return the number of node’s children.
+    return child_count();
+}
+
 }
diff --git a/Userland/Libraries/LibWeb/DOM/Node.h b/Userland/Libraries/LibWeb/DOM/Node.h
index d6ebd15e12..ca1da26ab4 100644
--- a/Userland/Libraries/LibWeb/DOM/Node.h
+++ b/Userland/Libraries/LibWeb/DOM/Node.h
@@ -71,6 +71,7 @@ public:
     bool is_document_fragment() const { return type() == NodeType::DOCUMENT_FRAGMENT_NODE; }
     bool is_parent_node() const { return is_element() || is_document() || is_document_fragment(); }
     bool is_slottable() const { return is_element() || is_text(); }
+    bool is_attribute() const { return type() == NodeType::ATTRIBUTE_NODE; }
 
     virtual bool requires_svg_container() const { return false; }
     virtual bool is_svg_container() const { return false; }
@@ -210,6 +211,8 @@ public:
 
     String debug_description() const;
 
+    size_t length() const;
+
 protected:
     Node(Document&, NodeType);
 
diff --git a/Userland/Libraries/LibWeb/DOM/Range.cpp b/Userland/Libraries/LibWeb/DOM/Range.cpp
index ebab3fa061..447e155659 100644
--- a/Userland/Libraries/LibWeb/DOM/Range.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Range.cpp
@@ -6,6 +6,7 @@
  */
 
 #include <LibWeb/DOM/Document.h>
+#include <LibWeb/DOM/DocumentType.h>
 #include <LibWeb/DOM/Node.h>
 #include <LibWeb/DOM/Range.h>
 #include <LibWeb/DOM/Window.h>
@@ -46,6 +47,130 @@ Range::~Range()
 {
 }
 
+// https://dom.spec.whatwg.org/#concept-range-root
+Node& Range::root()
+{
+    // The root of a live range is the root of its start node.
+    return m_start_container->root();
+}
+
+Node const& Range::root() const
+{
+    return m_start_container->root();
+}
+
+enum class RelativeBoundaryPointPosition {
+    Equal,
+    Before,
+    After,
+};
+
+// https://dom.spec.whatwg.org/#concept-range-bp-position
+static RelativeBoundaryPointPosition position_of_boundary_point_relative_to_other_boundary_point(Node const& node_a, u32 offset_a, Node const& node_b, u32 offset_b)
+{
+    // 1. Assert: nodeA and nodeB have the same root.
+    VERIFY(&node_a.root() == &node_b.root());
+
+    // 2. If nodeA is nodeB, then return equal if offsetA is offsetB, before if offsetA is less than offsetB, and after if offsetA is greater than offsetB.
+    if (&node_a == &node_b) {
+        if (offset_a == offset_b)
+            return RelativeBoundaryPointPosition::Equal;
+
+        if (offset_a < offset_b)
+            return RelativeBoundaryPointPosition::Before;
+
+        return RelativeBoundaryPointPosition::After;
+    }
+
+    // 3. If nodeA is following nodeB, then if the position of (nodeB, offsetB) relative to (nodeA, offsetA) is before, return after, and if it is after, return before.
+    if (node_a.is_following(node_b)) {
+        auto relative_position = position_of_boundary_point_relative_to_other_boundary_point(node_b, offset_b, node_a, offset_a);
+
+        if (relative_position == RelativeBoundaryPointPosition::Before)
+            return RelativeBoundaryPointPosition::After;
+
+        if (relative_position == RelativeBoundaryPointPosition::After)
+            return RelativeBoundaryPointPosition::Before;
+    }
+
+    // 4. If nodeA is an ancestor of nodeB:
+    if (node_a.is_ancestor_of(node_b)) {
+        // 1. Let child be nodeB.
+        NonnullRefPtr<Node> child = node_b;
+
+        // 2. While child is not a child of nodeA, set child to its parent.
+        while (!node_a.is_parent_of(child)) {
+            auto* parent = child->parent();
+            VERIFY(parent);
+            child = *parent;
+        }
+
+        // 3. If child’s index is less than offsetA, then return after.
+        if (child->index() < offset_a)
+            return RelativeBoundaryPointPosition::After;
+    }
+
+    // 5. Return before.
+    return RelativeBoundaryPointPosition::Before;
+}
+
+ExceptionOr<void> Range::set_start_or_end(Node& node, u32 offset, StartOrEnd start_or_end)
+{
+    // To set the start or end of a range to a boundary point (node, offset), run these steps:
+
+    // 1. If node is a doctype, then throw an "InvalidNodeTypeError" DOMException.
+    if (is<DocumentType>(node))
+        return InvalidNodeTypeError::create("Node cannot be a DocumentType.");
+
+    // 2. If offset is greater than node’s length, then throw an "IndexSizeError" DOMException.
+    if (offset > node.length())
+        return IndexSizeError::create(String::formatted("Node does not contain a child at offset {}", offset));
+
+    // 3. Let bp be the boundary point (node, offset).
+
+    if (start_or_end == StartOrEnd::Start) {
+        // -> If these steps were invoked as "set the start"
+
+        // 1. If range’s root is not equal to node’s root, or if bp is after the range’s end, set range’s end to bp.
+        if (&root() != &node.root() || position_of_boundary_point_relative_to_other_boundary_point(node, offset, m_end_container, m_end_offset) == RelativeBoundaryPointPosition::After) {
+            m_end_container = node;
+            m_end_offset = offset;
+        }
+
+        // 2. Set range’s start to bp.
+        m_start_container = node;
+        m_start_offset = offset;
+    } else {
+        // -> If these steps were invoked as "set the end"
+        VERIFY(start_or_end == StartOrEnd::End);
+
+        // 1. If range’s root is not equal to node’s root, or if bp is before the range’s start, set range’s start to bp.
+        if (&root() != &node.root() || position_of_boundary_point_relative_to_other_boundary_point(node, offset, m_start_container, m_start_offset) == RelativeBoundaryPointPosition::Before) {
+            m_start_container = node;
+            m_start_offset = offset;
+        }
+
+        // 2. Set range’s end to bp.
+        m_end_container = node;
+        m_end_offset = offset;
+    }
+
+    return {};
+}
+
+// https://dom.spec.whatwg.org/#concept-range-bp-set
+ExceptionOr<void> Range::set_start(Node& node, u32 offset)
+{
+    // The setStart(node, offset) method steps are to set the start of this to boundary point (node, offset).
+    return set_start_or_end(node, offset, StartOrEnd::Start);
+}
+
+ExceptionOr<void> Range::set_end(Node& node, u32 offset)
+{
+    // The setEnd(node, offset) method steps are to set the end of this to boundary point (node, offset).
+    return set_start_or_end(node, offset, StartOrEnd::End);
+}
+
 NonnullRefPtr<Range> Range::clone_range() const
 {
     return adopt_ref(*new Range(const_cast<Node&>(*m_start_container), m_start_offset, const_cast<Node&>(*m_end_container), m_end_offset));
diff --git a/Userland/Libraries/LibWeb/DOM/Range.h b/Userland/Libraries/LibWeb/DOM/Range.h
index 66c3c17091..06fed39b5d 100644
--- a/Userland/Libraries/LibWeb/DOM/Range.h
+++ b/Userland/Libraries/LibWeb/DOM/Range.h
@@ -24,17 +24,8 @@ public:
 
     // FIXME: There are a ton of methods missing here.
 
-    void set_start(Node& container, unsigned offset)
-    {
-        m_start_container = container;
-        m_start_offset = offset;
-    }
-
-    void set_end(Node& container, unsigned offset)
-    {
-        m_end_container = container;
-        m_end_offset = offset;
-    }
+    ExceptionOr<void> set_start(Node& node, u32 offset);
+    ExceptionOr<void> set_end(Node& node, u32 offset);
 
     NonnullRefPtr<Range> inverted() const;
     NonnullRefPtr<Range> normalized() const;
@@ -46,6 +37,16 @@ private:
     explicit Range(Document&);
 
     Range(Node& start_container, u32 start_offset, Node& end_container, u32 end_offset);
+
+    Node& root();
+    Node const& root() const;
+
+    enum class StartOrEnd {
+        Start,
+        End,
+    };
+
+    ExceptionOr<void> set_start_or_end(Node& node, u32 offset, StartOrEnd start_or_end);
 };
 
 }
diff --git a/Userland/Libraries/LibWeb/TreeNode.h b/Userland/Libraries/LibWeb/TreeNode.h
index 038bab50a3..8b5adb9557 100644
--- a/Userland/Libraries/LibWeb/TreeNode.h
+++ b/Userland/Libraries/LibWeb/TreeNode.h
@@ -80,6 +80,16 @@ public:
         return const_cast<TreeNode*>(this)->child_at_index(index);
     }
 
+    // https://dom.spec.whatwg.org/#concept-tree-index
+    size_t index() const
+    {
+        // The index of an object is its number of preceding siblings, or 0 if it has none.
+        size_t index = 0;
+        for (auto* node = previous_sibling(); node; node = node->previous_sibling())
+            ++index;
+        return index;
+    }
+
     Optional<size_t> index_of_child(const T& search_child)
     {
         VERIFY(search_child.parent() == this);
@@ -118,6 +128,8 @@ public:
     bool is_descendant_of(const TreeNode&) const;
     bool is_inclusive_descendant_of(const TreeNode&) const;
 
+    bool is_following(TreeNode const&) const;
+
     void append_child(NonnullRefPtr<T> node);
     void prepend_child(NonnullRefPtr<T> node);
     void insert_before(NonnullRefPtr<T> node, RefPtr<T> child);
@@ -571,4 +583,17 @@ inline bool TreeNode<T>::is_inclusive_descendant_of(const TreeNode<T>& other) co
     return other.is_inclusive_ancestor_of(*this);
 }
 
+// https://dom.spec.whatwg.org/#concept-tree-following
+template<typename T>
+inline bool TreeNode<T>::is_following(TreeNode<T> const& other) const
+{
+    // An object A is following an object B if A and B are in the same tree and A comes after B in tree order.
+    for (auto* node = previous_in_pre_order(); node; node = node->previous_in_pre_order()) {
+        if (node == &other)
+            return true;
+    }
+
+    return false;
+}
+
 }