Diff
Modified: branches/safari-610-branch/Source/WebCore/dom/BoundaryPoint.h (268529 => 268530)
--- branches/safari-610-branch/Source/WebCore/dom/BoundaryPoint.h 2020-10-15 17:34:26 UTC (rev 268529)
+++ branches/safari-610-branch/Source/WebCore/dom/BoundaryPoint.h 2020-10-15 17:34:30 UTC (rev 268530)
@@ -39,6 +39,7 @@
};
bool operator==(const BoundaryPoint&, const BoundaryPoint&);
+WEBCORE_EXPORT PartialOrdering documentOrder(const BoundaryPoint&, const BoundaryPoint&);
WEBCORE_EXPORT Optional<BoundaryPoint> makeBoundaryPointBeforeNode(Node&);
WEBCORE_EXPORT Optional<BoundaryPoint> makeBoundaryPointAfterNode(Node&);
Modified: branches/safari-610-branch/Source/WebCore/dom/Node.cpp (268529 => 268530)
--- branches/safari-610-branch/Source/WebCore/dom/Node.cpp 2020-10-15 17:34:26 UTC (rev 268529)
+++ branches/safari-610-branch/Source/WebCore/dom/Node.cpp 2020-10-15 17:34:30 UTC (rev 268530)
@@ -2636,6 +2636,52 @@
return depth;
}
+static size_t depthInComposedTree(const Node& node)
+{
+ size_t depth = 0;
+ auto ancestor = &node;
+ while ((ancestor = ancestor->parentInComposedTree()))
+ ++depth;
+ return depth;
+}
+
+struct AncestorAndChildren {
+ const Node* commonAncestor;
+ const Node* distinctAncestorA;
+ const Node* distinctAncestorB;
+};
+
+// FIXME: This function's name is not explicit about the fact that it's the common inclusive ancestor in the composed tree.
+static AncestorAndChildren commonInclusiveAncestorAndChildren(const Node& a, const Node& b)
+{
+ // This check isn't needed for correctness, but it is cheap and likely to be
+ // common enough to be worth optimizing so we don't have to walk to the root.
+ if (&a == &b)
+ return { &a, nullptr, nullptr };
+ // FIXME: Could optimize cases where nodes are both in the same shadow tree.
+ // FIXME: Could optimize cases where nodes are in different documents to quickly return false.
+ // FIXME: Could optimize cases where one node is connected and the other is not to quickly return false.
+ auto [depthA, depthB] = std::make_tuple(depthInComposedTree(a), depthInComposedTree(b));
+ auto [x, y, difference] = depthA >= depthB
+ ? std::make_tuple(&a, &b, depthA - depthB)
+ : std::make_tuple(&b, &a, depthB - depthA);
+ decltype(x) distinctAncestorA = nullptr;
+ for (decltype(difference) i = 0; i < difference; ++i) {
+ distinctAncestorA = x;
+ x = x->parentInComposedTree();
+ }
+ decltype(y) distinctAncestorB = nullptr;
+ while (x != y) {
+ distinctAncestorA = x;
+ distinctAncestorB = y;
+ x = x->parentInComposedTree();
+ y = y->parentInComposedTree();
+ }
+ if (depthA < depthB)
+ std::swap(distinctAncestorA, distinctAncestorB);
+ return { x, distinctAncestorA, distinctAncestorB };
+}
+
RefPtr<Node> commonInclusiveAncestor(Node& a, Node& b)
{
// This first check isn't needed for correctness, but it is cheap and likely to be
@@ -2655,6 +2701,42 @@
return x;
}
+static bool isSiblingSubsequent(const Node& siblingA, const Node& siblingB)
+{
+ ASSERT(siblingA.parentNode());
+ ASSERT(siblingA.parentNode() == siblingB.parentNode());
+ ASSERT(&siblingA != &siblingB);
+ for (auto sibling = &siblingA; sibling; sibling = sibling->nextSibling()) {
+ if (sibling == &siblingB)
+ return true;
+ }
+ return false;
+}
+
+PartialOrdering documentOrder(const Node& a, const Node& b)
+{
+ if (&a == &b)
+ return PartialOrdering::equivalent;
+ auto result = commonInclusiveAncestorAndChildren(a, b);
+ if (!result.commonAncestor)
+ return PartialOrdering::unordered;
+ if (!result.distinctAncestorA)
+ return PartialOrdering::less;
+ if (!result.distinctAncestorB)
+ return PartialOrdering::greater;
+ bool isShadowRootA = result.distinctAncestorA->isShadowRoot();
+ bool isShadowRootB = result.distinctAncestorB->isShadowRoot();
+ if (isShadowRootA || isShadowRootB) {
+ if (!isShadowRootB)
+ return PartialOrdering::less;
+ if (!isShadowRootA)
+ return PartialOrdering::greater;
+ ASSERT_NOT_REACHED();
+ return PartialOrdering::unordered;
+ }
+ return isSiblingSubsequent(*result.distinctAncestorA, *result.distinctAncestorB) ? PartialOrdering::less : PartialOrdering::greater;
+}
+
TextStream& operator<<(TextStream& ts, const Node& node)
{
ts << "node " << &node << " " << node.debugDescription();
Modified: branches/safari-610-branch/Source/WebCore/dom/Node.h (268529 => 268530)
--- branches/safari-610-branch/Source/WebCore/dom/Node.h 2020-10-15 17:34:26 UTC (rev 268529)
+++ branches/safari-610-branch/Source/WebCore/dom/Node.h 2020-10-15 17:34:30 UTC (rev 268530)
@@ -672,6 +672,24 @@
WEBCORE_EXPORT RefPtr<Node> commonInclusiveAncestor(Node&, Node&);
+class PartialOrdering {
+public:
+ static const PartialOrdering less;
+ static const PartialOrdering equivalent;
+ static const PartialOrdering greater;
+ static const PartialOrdering unordered;
+
+ friend constexpr bool is_gt(PartialOrdering);
+
+private:
+ enum class Type : uint8_t { Less, Equivalent, Greater, Unordered };
+ constexpr PartialOrdering(Type type) : m_type { type } { }
+ Type m_type;
+};
+constexpr bool is_gt(PartialOrdering);
+
+WEBCORE_EXPORT PartialOrdering documentOrder(const Node&, const Node&);
+
#if ASSERT_ENABLED
inline void adopted(Node* node)
@@ -786,6 +804,16 @@
moveTreeToNewScope(*this, *m_treeScope, newTreeScope);
}
+inline constexpr PartialOrdering PartialOrdering::less(Type::Less);
+inline constexpr PartialOrdering PartialOrdering::equivalent(Type::Equivalent);
+inline constexpr PartialOrdering PartialOrdering::greater(Type::Greater);
+inline constexpr PartialOrdering PartialOrdering::unordered(Type::Unordered);
+
+constexpr bool is_gt(PartialOrdering ordering)
+{
+ return ordering.m_type == PartialOrdering::Type::Greater;
+}
+
bool areNodesConnectedInSameTreeScope(const Node*, const Node*);
WTF::TextStream& operator<<(WTF::TextStream&, const Node&);
Modified: branches/safari-610-branch/Source/WebCore/dom/SimpleRange.cpp (268529 => 268530)
--- branches/safari-610-branch/Source/WebCore/dom/SimpleRange.cpp 2020-10-15 17:34:26 UTC (rev 268529)
+++ branches/safari-610-branch/Source/WebCore/dom/SimpleRange.cpp 2020-10-15 17:34:30 UTC (rev 268530)
@@ -66,6 +66,52 @@
return BoundaryPoint { *parent, node.computeNodeIndex() + 1 };
}
+static bool isOffsetBeforeChild(ContainerNode& container, unsigned offset, Node& child)
+{
+ if (!offset)
+ return true;
+ // If the container is not the parent, the child is part of a shadow tree, which we sort between offset 0 and offset 1.
+ if (child.parentNode() != &container)
+ return false;
+ unsigned currentOffset = 0;
+ for (auto currentChild = container.firstChild(); currentChild && currentChild != &child; currentChild = currentChild->nextSibling()) {
+ if (offset <= ++currentOffset)
+ return true;
+ }
+ return false;
+}
+
+static PartialOrdering order(unsigned a, unsigned b)
+{
+ if (a < b)
+ return PartialOrdering::less;
+ if (a > b)
+ return PartialOrdering::greater;
+ return PartialOrdering::equivalent;
+}
+
+PartialOrdering documentOrder(const BoundaryPoint& a, const BoundaryPoint& b)
+{
+ if (a.container.ptr() == b.container.ptr())
+ return order(a.offset, b.offset);
+
+ for (auto ancestor = b.container.ptr(); ancestor; ) {
+ auto nextAncestor = ancestor->parentInComposedTree();
+ if (nextAncestor == a.container.ptr())
+ return isOffsetBeforeChild(*nextAncestor, a.offset, *ancestor) ? PartialOrdering::less : PartialOrdering::greater;
+ ancestor = nextAncestor;
+ }
+
+ for (auto ancestor = a.container.ptr(); ancestor; ) {
+ auto nextAncestor = ancestor->parentInComposedTree();
+ if (nextAncestor == b.container.ptr())
+ return isOffsetBeforeChild(*nextAncestor, b.offset, *ancestor) ? PartialOrdering::greater : PartialOrdering::less;
+ ancestor = nextAncestor;
+ }
+
+ return documentOrder(a.container, b.container);
+}
+
Optional<SimpleRange> makeRangeSelectingNode(Node& node)
{
auto parent = node.parentNode();
