⚠ Archived content — this site is no longer maintained.   Current WebKit documentation is at docs.webkit.org.

Changeset 268800 in webkit


Ignore:
Timestamp:
Oct 21, 2020, 9:39:37 AM (6 years ago)
Author:
Darin Adler
Message:

REGRESSION(r266295): Range allows start and end containers to belong to different trees
​https://bugs.webkit.org/show_bug.cgi?id=217895

Reviewed by Ryosuke Niwa.

Source/WebCore:

Test: fast/dom/Range/ranges-across-trees.html

  • dom/BoundaryPoint.h: Added treeOrder<TreeType>.
  • dom/Node.cpp:

(WebCore::parent<Tree>): Added.
(WebCore::parent<ComposedTree>): Added.
(WebCore::depth): Changed into a template that takes TreeType.
(WebCore::commonInclusiveAncestorAndChildren): Ditto.
(WebCore::commonInclusiveAncestor): Changed to explicitly use ComposedTree to preserve
the current behavior, but likely will return later to make this a template and have it
us the normal tree by default.
(WebCore::treeOrder): Changed into a template that takes TreeType.
(WebCore::documentOrder): Call treeOrder<ComposedTree> to preserve the current behavior.
Likely will delete this later after changing callers to use treeOrder.

  • dom/Node.h: Added Tree, ShadowIncludingTree, and ComposedTree. Added parent and

treeOrder function templates. TreeType currently is a set of classes but they could
also be objects of another type. Maybe an enumeration named TreeType instead?

  • dom/Range.cpp:

(WebCore::Range::setStart): Use treeOrder instead of documentOrder to use the normal
tree instead of the composed tree.
(WebCore::Range::setEnd): Ditto.
(WebCore::Range::isPointInRange): Use isPointInRange<Tree> instead of isPointInRange
to use the normal tree instead of the composed tree.
(WebCore::Range::comparePoint const): Use treeOrder instead of documentOrder to use
the normal tree instead of the composed tree.
(WebCore::Range::compareNode const): Ditto.
(WebCore::Range::compareBoundaryPoints const): Ditto.
(WebCore::Range::intersectsNode const): Use intersects<Tree> instead of isPointInRange
to use the normal tree instead of the composed tree.

  • dom/SimpleRange.cpp:

(WebCore::treeOrder): Changed into a template that takes TreeType.
(WebCore::documentOrder): Call treeOrder<ComposedTree> to preserve the current behavior.
Likely will delete this later after changing callers to use treeOrder.
(WebCore::isPointInRange): Changed into a template that takes TreeType.
For now the default tree type is still ComposedTree, but will change that later.
(WebCore::intersects): Ditto.
(WebCore::contains<Tree>): Added.
(WebCore::contains<ComposedTree>): Added.

  • dom/SimpleRange.h: Added isPointInRange, intersects, and treeOrder function templates.

LayoutTests:

  • fast/dom/Range/ranges-across-trees.html: Added.
Location:
trunk
Files:
2 added
8 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r268799 r268800  
     12020-10-20  Darin Adler  <darin@apple.com>
     2
     3        REGRESSION(r266295): Range allows start and end containers to belong to different trees
     4        https://bugs.webkit.org/show_bug.cgi?id=217895
     5
     6        Reviewed by Ryosuke Niwa.
     7
     8        * fast/dom/Range/ranges-across-trees.html: Added.
     9
    1102020-10-21  Hector Lopez  <hector_i_lopez@apple.com>
    211

  • trunk/Source/WebCore/ChangeLog

    r268798 r268800  
     12020-10-20  Darin Adler  <darin@apple.com>
     2
     3        REGRESSION(r266295): Range allows start and end containers to belong to different trees
     4        https://bugs.webkit.org/show_bug.cgi?id=217895
     5
     6        Reviewed by Ryosuke Niwa.
     7
     8        Test: fast/dom/Range/ranges-across-trees.html
     9
     10        * dom/BoundaryPoint.h: Added treeOrder<TreeType>.
     11
     12        * dom/Node.cpp:
     13        (WebCore::parent<Tree>): Added.
     14        (WebCore::parent<ComposedTree>): Added.
     15        (WebCore::depth): Changed into a template that takes TreeType.
     16        (WebCore::commonInclusiveAncestorAndChildren): Ditto.
     17        (WebCore::commonInclusiveAncestor): Changed to explicitly use ComposedTree to preserve
     18        the current behavior, but likely will return later to make this a template and have it
     19        us the normal tree by default.
     20        (WebCore::treeOrder): Changed into a template that takes TreeType.
     21        (WebCore::documentOrder): Call treeOrder<ComposedTree> to preserve the current behavior.
     22        Likely will delete this later after changing callers to use treeOrder.
     23
     24        * dom/Node.h: Added Tree, ShadowIncludingTree, and ComposedTree. Added parent and
     25        treeOrder function templates. TreeType currently is a set of classes but they could
     26        also be objects of another type. Maybe an enumeration named TreeType instead?
     27
     28        * dom/Range.cpp:
     29        (WebCore::Range::setStart): Use treeOrder instead of documentOrder to use the normal
     30        tree instead of the composed tree.
     31        (WebCore::Range::setEnd): Ditto.
     32        (WebCore::Range::isPointInRange): Use isPointInRange<Tree> instead of isPointInRange
     33        to use the normal tree instead of the composed tree.
     34        (WebCore::Range::comparePoint const): Use treeOrder instead of documentOrder to use
     35        the normal tree instead of the composed tree.
     36        (WebCore::Range::compareNode const): Ditto.
     37        (WebCore::Range::compareBoundaryPoints const): Ditto.
     38        (WebCore::Range::intersectsNode const): Use intersects<Tree> instead of isPointInRange
     39        to use the normal tree instead of the composed tree.
     40
     41        * dom/SimpleRange.cpp:
     42        (WebCore::treeOrder): Changed into a template that takes TreeType.
     43        (WebCore::documentOrder): Call treeOrder<ComposedTree> to preserve the current behavior.
     44        Likely will delete this later after changing callers to use treeOrder.
     45        (WebCore::isPointInRange): Changed into a template that takes TreeType.
     46        For now the default tree type is still ComposedTree, but will change that later.
     47        (WebCore::intersects): Ditto.
     48        (WebCore::contains<Tree>): Added.
     49        (WebCore::contains<ComposedTree>): Added.
     50
     51        * dom/SimpleRange.h: Added isPointInRange, intersects, and treeOrder function templates.
     52
    1532020-10-21  Antti Koivisto  <antti@apple.com>
    254

  • trunk/Source/WebCore/dom/BoundaryPoint.h

    r266026 r268800  
    4141bool operator==(const BoundaryPoint&, const BoundaryPoint&);
    4242bool operator!=(const BoundaryPoint&, const BoundaryPoint&);
     43
     44template<typename TreeType = Tree> PartialOrdering treeOrder(const BoundaryPoint&, const BoundaryPoint&);
    4345WEBCORE_EXPORT PartialOrdering documentOrder(const BoundaryPoint&, const BoundaryPoint&);
    4446

  • trunk/Source/WebCore/dom/Node.cpp

    r268695 r268800  
    26232623}
    26242624
    2625 static size_t depthInComposedTree(const Node& node)
     2625template<> ContainerNode* parent<Tree>(const Node& node)
     2626{
     2627    return node.parentNode();
     2628}
     2629
     2630template<> ContainerNode* parent<ComposedTree>(const Node& node)
     2631{
     2632    return node.parentInComposedTree();
     2633}
     2634
     2635template<typename TreeType> size_t depth(const Node& node)
    26262636{
    26272637    size_t depth = 0;
    26282638    auto ancestor = &node;
    2629     while ((ancestor = ancestor->parentInComposedTree()))
     2639    while ((ancestor = parent<TreeType>(*ancestor)))
    26302640        ++depth;
    26312641    return depth;
    … …  
    26382648};
    26392649
    2640 // FIXME: This function's name is not explicit about the fact that it's the common inclusive ancestor in the composed tree.
    2641 static AncestorAndChildren commonInclusiveAncestorAndChildren(const Node& a, const Node& b)
     2650template<typename TreeType> AncestorAndChildren commonInclusiveAncestorAndChildren(const Node& a, const Node& b)
    26422651{
    26432652    // This check isn't needed for correctness, but it is cheap and likely to be
    … …  
    26482657    // FIXME: Could optimize cases where nodes are in different documents to quickly return false.
    26492658    // FIXME: Could optimize cases where one node is connected and the other is not to quickly return false.
    2650     auto [depthA, depthB] = std::make_tuple(depthInComposedTree(a), depthInComposedTree(b));
     2659    auto [depthA, depthB] = std::make_tuple(depth<TreeType>(a), depth<TreeType>(b));
    26512660    auto [x, y, difference] = depthA >= depthB
    26522661        ? std::make_tuple(&a, &b, depthA - depthB)
    … …  
    26552664    for (decltype(difference) i = 0; i < difference; ++i) {
    26562665        distinctAncestorA = x;
    2657         x = x->parentInComposedTree();
     2666        x = parent<TreeType>(*x);
    26582667    }
    26592668    decltype(y) distinctAncestorB = nullptr;
    … …  
    26612670        distinctAncestorA = x;
    26622671        distinctAncestorB = y;
    2663         x = x->parentInComposedTree();
    2664         y = y->parentInComposedTree();
     2672        x = parent<TreeType>(*x);
     2673        y = parent<TreeType>(*y);
    26652674    }
    26662675    if (depthA < depthB)
    … …  
    26692678}
    26702679
    2671 // FIXME: This function's name is not explicit about the fact that it's the common inclusive ancestor in the composed tree.
     2680// FIXME: Change this to work within the normal tree instead of the composed tree. Or rename and/or split into multiple functions.
    26722681RefPtr<Node> commonInclusiveAncestor(Node& a, Node& b)
    26732682{
    2674     return const_cast<Node*>(commonInclusiveAncestorAndChildren(a, b).commonAncestor);
     2683    return const_cast<Node*>(commonInclusiveAncestorAndChildren<ComposedTree>(a, b).commonAncestor);
    26752684}
    26762685
    … …  
    26872696}
    26882697
    2689 PartialOrdering documentOrder(const Node& a, const Node& b)
     2698template<typename TreeType> PartialOrdering treeOrder(const Node& a, const Node& b)
    26902699{
    26912700    if (&a == &b)
    26922701        return PartialOrdering::equivalent;
    2693     auto result = commonInclusiveAncestorAndChildren(a, b);
     2702    auto result = commonInclusiveAncestorAndChildren<TreeType>(a, b);
    26942703    if (!result.commonAncestor)
    26952704        return PartialOrdering::unordered;
    … …  
    27112720}
    27122721
     2722template PartialOrdering treeOrder<Tree>(const Node&, const Node&);
     2723template PartialOrdering treeOrder<ComposedTree>(const Node&, const Node&);
     2724
     2725PartialOrdering documentOrder(const Node& a, const Node& b)
     2726{
     2727    return treeOrder<ComposedTree>(a, b);
     2728}
     2729
    27132730TextStream& operator<<(TextStream& ts, const Node& node)
    27142731{

  • trunk/Source/WebCore/dom/Node.h

    r268695 r268800  
    756756constexpr bool is_gteq(PartialOrdering);
    757757
     758struct Tree { };
     759struct ShadowIncludingTree { };
     760struct ComposedTree { };
     761template<typename TreeType = Tree> ContainerNode* parent(const Node&);
     762template<typename TreeType = Tree> PartialOrdering treeOrder(const Node&, const Node&);
     763
    758764WEBCORE_EXPORT PartialOrdering documentOrder(const Node&, const Node&);
    759765

  • trunk/Source/WebCore/dom/Range.cpp

    r268648 r268800  
    117117
    118118    m_start.set(WTFMove(container), offset, childNode.releaseReturnValue());
    119     if (!is_lteq(documentOrder(makeBoundaryPoint(m_start), makeBoundaryPoint(m_end))))
     119    if (!is_lteq(treeOrder(makeBoundaryPoint(m_start), makeBoundaryPoint(m_end))))
    120120        m_end = m_start;
    121121    updateAssociatedSelection();
    … …  
    131131
    132132    m_end.set(WTFMove(container), offset, childNode.releaseReturnValue());
    133     if (!is_lteq(documentOrder(makeBoundaryPoint(m_start), makeBoundaryPoint(m_end))))
     133    if (!is_lteq(treeOrder(makeBoundaryPoint(m_start), makeBoundaryPoint(m_end))))
    134134        m_start = m_end;
    135135    updateAssociatedSelection();
    … …  
    156156        return checkResult.releaseException();
    157157    }
    158     return WebCore::isPointInRange(makeSimpleRange(*this), { container, offset });
     158    return WebCore::isPointInRange<Tree>(makeSimpleRange(*this), { container, offset });
    159159}
    160160
    … …  
    168168        return checkResult.releaseException();
    169169    }
    170     auto ordering = documentOrder({ container, offset }, makeSimpleRange(*this));
     170    auto ordering = treeOrder({ container, offset }, makeSimpleRange(*this));
    171171    if (is_lt(ordering))
    172172        return -1;
    … …  
    199199    }
    200200
    201     auto startOrdering = documentOrder(nodeRange->start, makeBoundaryPoint(m_start));
    202     auto endOrdering = documentOrder(nodeRange->end, makeBoundaryPoint(m_end));
     201    auto startOrdering = treeOrder(nodeRange->start, makeBoundaryPoint(m_start));
     202    auto endOrdering = treeOrder(nodeRange->end, makeBoundaryPoint(m_end));
    203203    if (is_gteq(startOrdering) && is_lteq(endOrdering))
    204204        return NODE_INSIDE;
    … …  
    236236        return Exception { NotSupportedError };
    237237    }
    238     auto ordering = documentOrder(makeBoundaryPoint(*thisPoint), makeBoundaryPoint(*otherPoint));
     238    auto ordering = treeOrder(makeBoundaryPoint(*thisPoint), makeBoundaryPoint(*otherPoint));
    239239    if (is_lt(ordering))
    240240        return -1;
    … …  
    256256bool Range::intersectsNode(Node& node) const
    257257{
    258     return intersects(makeSimpleRange(*this), node);
     258    return intersects<Tree>(makeSimpleRange(*this), node);
    259259}
    260260

  • trunk/Source/WebCore/dom/SimpleRange.cpp

    r266987 r268800  
    9696}
    9797
    98 // FIXME: Create BoundaryPoint.cpp and move this there.
    99 PartialOrdering documentOrder(const BoundaryPoint& a, const BoundaryPoint& b)
     98template<typename TreeType> PartialOrdering treeOrder(const BoundaryPoint& a, const BoundaryPoint& b)
    10099{
    101100    if (a.container.ptr() == b.container.ptr())
    … …  
    103102
    104103    for (auto ancestor = b.container.ptr(); ancestor; ) {
    105         auto nextAncestor = ancestor->parentInComposedTree();
     104        auto nextAncestor = parent<TreeType>(*ancestor);
    106105        if (nextAncestor == a.container.ptr())
    107106            return isOffsetBeforeChild(*nextAncestor, a.offset, *ancestor) ? PartialOrdering::less : PartialOrdering::greater;
    … …  
    110109
    111110    for (auto ancestor = a.container.ptr(); ancestor; ) {
    112         auto nextAncestor = ancestor->parentInComposedTree();
     111        auto nextAncestor = parent<TreeType>(*ancestor);
    113112        if (nextAncestor == b.container.ptr())
    114113            return isOffsetBeforeChild(*nextAncestor, b.offset, *ancestor) ? PartialOrdering::greater : PartialOrdering::less;
    … …  
    116115    }
    117116
    118     return documentOrder(a.container, b.container);
     117    return treeOrder<TreeType>(a.container, b.container);
     118}
     119
     120PartialOrdering documentOrder(const BoundaryPoint& a, const BoundaryPoint& b)
     121{
     122    return treeOrder<ComposedTree>(a, b);
    119123}
    120124
    … …  
    209213}
    210214
     215template<typename TreeType> bool isPointInRange(const SimpleRange& range, const BoundaryPoint& point)
     216{
     217    return is_lteq(treeOrder<TreeType>(range.start, point)) && is_lteq(treeOrder<TreeType>(point, range.end));
     218}
     219
     220template bool isPointInRange<Tree>(const SimpleRange&, const BoundaryPoint&);
     221
     222template<typename TreeType> bool isPointInRange(const SimpleRange& range, const Optional<BoundaryPoint>& point)
     223{
     224    return point && isPointInRange<TreeType>(range, *point);
     225}
     226
    211227bool isPointInRange(const SimpleRange& range, const BoundaryPoint& point)
    212228{
    213     return is_lteq(documentOrder(range.start, point)) && is_lteq(documentOrder(point, range.end));
     229    return isPointInRange<ComposedTree>(range, point);
    214230}
    215231
    216232bool isPointInRange(const SimpleRange& range, const Optional<BoundaryPoint>& point)
    217233{
    218     return point && isPointInRange(range, *point);
    219 }
    220 
    221 PartialOrdering documentOrder(const SimpleRange& range, const BoundaryPoint& point)
    222 {
    223     if (auto order = documentOrder(range.start, point); !is_lt(order))
     234    return isPointInRange<ComposedTree>(range, point);
     235}
     236
     237template<typename TreeType> PartialOrdering treeOrder(const SimpleRange& range, const BoundaryPoint& point)
     238{
     239    if (auto order = treeOrder<TreeType>(range.start, point); !is_lt(order))
    224240        return order;
    225     if (auto order = documentOrder(range.end, point); !is_gt(order))
     241    if (auto order = treeOrder<TreeType>(range.end, point); !is_gt(order))
    226242        return order;
    227243    return PartialOrdering::equivalent;
    228244}
    229245
    230 PartialOrdering documentOrder(const BoundaryPoint& point, const SimpleRange& range)
    231 {
    232     if (auto order = documentOrder(point, range.start); !is_gt(order))
     246template<typename TreeType> PartialOrdering treeOrder(const BoundaryPoint& point, const SimpleRange& range)
     247{
     248    if (auto order = treeOrder<TreeType>(point, range.start); !is_gt(order))
    233249        return order;
    234     if (auto order = documentOrder(point, range.end); !is_lt(order))
     250    if (auto order = treeOrder<TreeType>(point, range.end); !is_lt(order))
    235251        return order;
    236252    return PartialOrdering::equivalent;
    237253}
    238254
     255template PartialOrdering treeOrder<Tree>(const SimpleRange&, const BoundaryPoint&);
     256template PartialOrdering treeOrder<Tree>(const BoundaryPoint&, const SimpleRange&);
     257
     258PartialOrdering documentOrder(const SimpleRange& range, const BoundaryPoint& point)
     259{
     260    return treeOrder<ComposedTree>(range, point);
     261}
     262
     263PartialOrdering documentOrder(const BoundaryPoint& point, const SimpleRange& range)
     264{
     265    return treeOrder<ComposedTree>(point, range);
     266}
     267
    239268bool contains(const SimpleRange& outerRange, const SimpleRange& innerRange)
    240269{
    … …  
    242271}
    243272
     273template<typename TreeType> bool intersects(const SimpleRange& a, const SimpleRange& b)
     274{
     275    return is_lteq(treeOrder<TreeType>(a.start, b.end)) && is_lteq(treeOrder<TreeType>(b.start, a.end));
     276}
     277
     278template bool intersects<Tree>(const SimpleRange&, const SimpleRange&);
     279
    244280bool intersects(const SimpleRange& a, const SimpleRange& b)
    245281{
    246     return is_lteq(documentOrder(a.start, b.end)) && is_lteq(documentOrder(b.start, a.end));
     282    return intersects<ComposedTree>(a, b);
    247283}
    248284
    … …  
    273309}
    274310
    275 bool intersects(const SimpleRange& range, const Node& node)
     311template<typename TreeType> bool contains(const Node& outer, const Node& inner);
     312
     313template<> bool contains<Tree>(const Node& outer, const Node& inner)
     314{
     315    return outer.contains(inner);
     316}
     317
     318template<> bool contains<ComposedTree>(const Node& outer, const Node& inner)
     319{
     320    // FIXME: This is what the code did before, but it is not correct!
     321    return outer.contains(inner);
     322}
     323
     324template<typename TreeType> bool intersects(const SimpleRange& range, const Node& node)
    276325{
    277326    // FIXME: Consider a more efficient algorithm that avoids always computing the node index.
    … …  
    279328    auto nodeRange = makeRangeSelectingNode(const_cast<Node&>(node));
    280329    if (!nodeRange)
    281         return node.contains(range.start.container.ptr());
    282     return is_lt(documentOrder(nodeRange->start, range.end)) && is_lt(documentOrder(range.start, nodeRange->end));
    283 
    284 }
    285 
    286 }
     330        return contains<TreeType>(node, range.start.container);
     331    return is_lt(treeOrder<TreeType>(nodeRange->start, range.end)) && is_lt(treeOrder<TreeType>(range.start, nodeRange->end));
     332
     333}
     334
     335template bool intersects<Tree>(const SimpleRange&, const Node&);
     336
     337bool intersects(const SimpleRange& range, const Node& node)
     338{
     339    return intersects<ComposedTree>(range, node);
     340
     341}
     342
     343}

  • trunk/Source/WebCore/dom/SimpleRange.h

    r266987 r268800  
    6666bool operator==(const SimpleRange&, const SimpleRange&);
    6767
     68template<typename TreeType> bool isPointInRange(const SimpleRange&, const BoundaryPoint&);
     69template<typename TreeType> bool isPointInRange(const SimpleRange&, const Optional<BoundaryPoint>&);
    6870WEBCORE_EXPORT bool isPointInRange(const SimpleRange&, const BoundaryPoint&);
    6971bool isPointInRange(const SimpleRange&, const Optional<BoundaryPoint>&);
    7072
    7173WEBCORE_EXPORT bool contains(const SimpleRange& outerRange, const SimpleRange& innerRange);
     74template<typename TreeType> bool intersects(const SimpleRange&, const SimpleRange&);
    7275WEBCORE_EXPORT bool intersects(const SimpleRange&, const SimpleRange&);
    7376WEBCORE_EXPORT SimpleRange unionRange(const SimpleRange&, const SimpleRange&);
    … …  
    7578
    7679WEBCORE_EXPORT bool contains(const SimpleRange&, const Node&);
     80template<typename TreeType> bool intersects(const SimpleRange&, const Node&);
    7781WEBCORE_EXPORT bool intersects(const SimpleRange&, const Node&);
    7882
    7983// Returns equivalent if point is in range.
     84template<typename TreeType = Tree> PartialOrdering treeOrder(const SimpleRange&, const BoundaryPoint&);
     85template<typename TreeType = Tree> PartialOrdering treeOrder(const BoundaryPoint&, const SimpleRange&);
    8086WEBCORE_EXPORT PartialOrdering documentOrder(const SimpleRange&, const BoundaryPoint&);
    8187WEBCORE_EXPORT PartialOrdering documentOrder(const BoundaryPoint&, const SimpleRange&);
Note: See TracChangeset for help on using the changeset viewer.