third_party/WebKit/Source/core/dom/shadow/ComposedTreeTraversal.h

   1 /*
   2  * Copyright (C) 2012 Google Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions are
   6  * met:
   7  *
   8  *     * Redistributions of source code must retain the above copyright
   9  * notice, this list of conditions and the following disclaimer.
  10  *     * Neither the name of Google Inc. nor the names of its
  11  * contributors may be used to endorse or promote products derived from
  12  * this software without specific prior written permission.
  13  *
  14  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  15  * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  16  * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  17  * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  18  * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  19  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  20  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  21  * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  22  * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25  */
  26
  27 #ifndef ComposedTreeTraversal_h
  28 #define ComposedTreeTraversal_h
  29
  30 #include "core/CoreExport.h"
  31 #include "core/dom/Document.h"
  32 #include "core/dom/LayoutTreeBuilderTraversal.h"
  33 #include "core/dom/shadow/InsertionPoint.h"
  34 #include "core/dom/shadow/ShadowRoot.h"
  35 #include "wtf/Allocator.h"
  36
  37 namespace blink {
  38
  39 class ContainerNode;
  40 class Node;
  41
  42 // Composed tree version of |NodeTraversal|.
  43 //
  44 // None of member functions takes a |ShadowRoot| or an active insertion point,
  45 // e.g. roughly speaking <content> and <shadow> in the shadow tree, see
  46 // |InsertionPoint::isActive()| for details of active insertion points, since
  47 // they aren't appeared in the composed tree. |assertPrecondition()| and
  48 // |assertPostCondition()| check this condition.
  49 //
  50 // FIXME: Make some functions inline to optimise the performance.
  51 // https://bugs.webkit.org/show_bug.cgi?id=82702
  52 class CORE_EXPORT ComposedTreeTraversal {
  53     STATIC_ONLY(ComposedTreeTraversal);
  54 public:
  55     typedef LayoutTreeBuilderTraversal::ParentDetails ParentTraversalDetails;
  56
  57     static Node* next(const Node&);
  58     static Node* next(const Node&, const Node* stayWithin);
  59     static Node* previous(const Node&);
  60
  61     static Node* firstChild(const Node&);
  62     static Node* lastChild(const Node&);
  63     static bool hasChildren(const Node&);
  64
  65     static ContainerNode* parent(const Node&, ParentTraversalDetails* = 0);
  66     static Element* parentElement(const Node&);
  67
  68     static Node* nextSibling(const Node&);
  69     static Node* previousSibling(const Node&);
  70
  71     // Returns a child node at |index|. If |index| is greater than or equal to
  72     // the children, this function returns |nullptr|.
  73     static Node* childAt(const Node&, unsigned index);
  74
  75     // Composed tree version of |NodeTraversal::nextSkippingChildren()|. This
  76     // function is similar to |next()| but skips child nodes of a specified
  77     // node.
  78     static Node* nextSkippingChildren(const Node&);
  79     static Node* nextSkippingChildren(const Node&, const Node* stayWithin);
  80
  81     // Composed tree version of |NodeTraversal::previousSkippingChildren()|
  82     // similar to |previous()| but skipping child nodes of the specified node.
  83     static Node* previousSkippingChildren(const Node&);
  84
  85     // Like previous, but visits parents before their children.
  86     static Node* previousPostOrder(const Node&, const Node* stayWithin = nullptr);
  87
  88     // Composed tree version of |Node::isDescendantOf(other)|. This function
  89     // returns true if |other| contains |node|, otherwise returns
  90     // false. If |other| is |node|, this function returns false.
  91     static bool isDescendantOf(const Node& /*node*/, const Node& other);
  92
  93     static bool contains(const ContainerNode& container, const Node& node)
  94     {
  95         assertPrecondition(container);
  96         assertPrecondition(node);
  97         return container == node || isDescendantOf(node, container);
  98     }
  99
 100     static bool containsIncludingPseudoElement(const ContainerNode&, const Node&);
 101
 102     // Returns a common ancestor of |nodeA| and |nodeB| if exists, otherwise
 103     // returns |nullptr|.
 104     static Node* commonAncestor(const Node& nodeA, const Node& nodeB);
 105
 106     // Composed tree version of |Node::nodeIndex()|. This function returns a
 107     // zero base position number of the specified node in child nodes list, or
 108     // zero if the specified node has no parent.
 109     static unsigned index(const Node&);
 110
 111     // Composed tree version of |ContainerNode::countChildren()|. This function
 112     // returns the number of the child nodes of the specified node in the
 113     // composed tree.
 114     static unsigned countChildren(const Node&);
 115
 116     static Node* lastWithin(const Node&);
 117     static Node& lastWithinOrSelf(const Node&);
 118
 119 private:
 120     enum TraversalDirection {
 121         TraversalDirectionForward,
 122         TraversalDirectionBackward
 123     };
 124
 125     static void assertPrecondition(const Node& node)
 126     {
 127 #if ENABLE(ASSERT)
 128         ASSERT(!node.needsDistributionRecalc());
 129         ASSERT(node.canParticipateInComposedTree());
 130 #endif
 131     }
 132
 133     static void assertPostcondition(const Node* node)
 134     {
 135 #if ENABLE(ASSERT)
 136         if (node)
 137             assertPrecondition(*node);
 138 #endif
 139     }
 140
 141     static Node* traverseNode(const Node&, TraversalDirection);
 142     static Node* traverseLightChildren(const Node&, TraversalDirection);
 143
 144     static Node* traverseNext(const Node&);
 145     static Node* traverseNext(const Node&, const Node* stayWithin);
 146     static Node* traverseNextSkippingChildren(const Node&, const Node* stayWithin);
 147     static Node* traversePrevious(const Node&);
 148
 149     static Node* traverseFirstChild(const Node&);
 150     static Node* traverseLastChild(const Node&);
 151     static Node* traverseChild(const Node&, TraversalDirection);
 152
 153     static ContainerNode* traverseParent(const Node&, ParentTraversalDetails* = 0);
 154
 155     static Node* traverseNextSibling(const Node&);
 156     static Node* traversePreviousSibling(const Node&);
 157
 158     static Node* traverseSiblingOrBackToInsertionPoint(const Node&, TraversalDirection);
 159     static Node* traverseSiblingInCurrentTree(const Node&, TraversalDirection);
 160
 161     static Node* traverseSiblings(const Node*, TraversalDirection);
 162     static Node* traverseDistributedNodes(const Node*, const InsertionPoint&, TraversalDirection);
 163
 164     static Node* traverseBackToYoungerShadowRoot(const Node&, TraversalDirection);
 165
 166     static ContainerNode* traverseParentOrHost(const Node&);
 167     static Node* traverseNextAncestorSibling(const Node&);
 168     static Node* traversePreviousAncestorSibling(const Node&);
 169 };
 170
 171 inline ContainerNode* ComposedTreeTraversal::parent(const Node& node, ParentTraversalDetails* details)
 172 {
 173     assertPrecondition(node);
 174     ContainerNode* result = traverseParent(node, details);
 175     assertPostcondition(result);
 176     return result;
 177 }
 178
 179 inline Element* ComposedTreeTraversal::parentElement(const Node& node)
 180 {
 181     ContainerNode* parent = ComposedTreeTraversal::parent(node);
 182     return parent && parent->isElementNode() ? toElement(parent) : nullptr;
 183 }
 184
 185 inline Node* ComposedTreeTraversal::nextSibling(const Node& node)
 186 {
 187     assertPrecondition(node);
 188     Node* result = traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
 189     assertPostcondition(result);
 190     return result;
 191 }
 192
 193 inline Node* ComposedTreeTraversal::previousSibling(const Node& node)
 194 {
 195     assertPrecondition(node);
 196     Node* result = traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
 197     assertPostcondition(result);
 198     return result;
 199 }
 200
 201 inline Node* ComposedTreeTraversal::next(const Node& node)
 202 {
 203     assertPrecondition(node);
 204     Node* result = traverseNext(node);
 205     assertPostcondition(result);
 206     return result;
 207 }
 208
 209 inline Node* ComposedTreeTraversal::next(const Node& node, const Node* stayWithin)
 210 {
 211     assertPrecondition(node);
 212     Node* result = traverseNext(node, stayWithin);
 213     assertPostcondition(result);
 214     return result;
 215 }
 216
 217 inline Node* ComposedTreeTraversal::nextSkippingChildren(const Node& node, const Node* stayWithin)
 218 {
 219     assertPrecondition(node);
 220     Node* result = traverseNextSkippingChildren(node, stayWithin);
 221     assertPostcondition(result);
 222     return result;
 223 }
 224
 225 inline Node* ComposedTreeTraversal::traverseNext(const Node& node)
 226 {
 227     if (Node* next = traverseFirstChild(node))
 228         return next;
 229     for (const Node* next = &node; next; next = traverseParent(*next)) {
 230         if (Node* sibling = traverseNextSibling(*next))
 231             return sibling;
 232     }
 233     return 0;
 234 }
 235
 236 inline Node* ComposedTreeTraversal::traverseNext(const Node& node, const Node* stayWithin)
 237 {
 238     if (Node* next = traverseFirstChild(node))
 239         return next;
 240     return traverseNextSkippingChildren(node, stayWithin);
 241 }
 242
 243 inline Node* ComposedTreeTraversal::traverseNextSkippingChildren(const Node& node, const Node* stayWithin)
 244 {
 245     for (const Node* next = &node; next; next = traverseParent(*next)) {
 246         if (next == stayWithin)
 247             return nullptr;
 248         if (Node* sibling = traverseNextSibling(*next))
 249             return sibling;
 250     }
 251     return nullptr;
 252 }
 253
 254 inline Node* ComposedTreeTraversal::previous(const Node& node)
 255 {
 256     assertPrecondition(node);
 257     Node* result = traversePrevious(node);
 258     assertPostcondition(result);
 259     return result;
 260 }
 261
 262 inline Node* ComposedTreeTraversal::traversePrevious(const Node& node)
 263 {
 264     if (Node* previous = traversePreviousSibling(node)) {
 265         while (Node* child = traverseLastChild(*previous))
 266             previous = child;
 267         return previous;
 268     }
 269     return traverseParent(node);
 270 }
 271
 272 inline Node* ComposedTreeTraversal::firstChild(const Node& node)
 273 {
 274     assertPrecondition(node);
 275     Node* result = traverseChild(node, TraversalDirectionForward);
 276     assertPostcondition(result);
 277     return result;
 278 }
 279
 280 inline Node* ComposedTreeTraversal::lastChild(const Node& node)
 281 {
 282     assertPrecondition(node);
 283     Node* result = traverseLastChild(node);
 284     assertPostcondition(result);
 285     return result;
 286 }
 287
 288 inline bool ComposedTreeTraversal::hasChildren(const Node& node)
 289 {
 290     return firstChild(node);
 291 }
 292
 293 inline Node* ComposedTreeTraversal::traverseNextSibling(const Node& node)
 294 {
 295     return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
 296 }
 297
 298 inline Node* ComposedTreeTraversal::traversePreviousSibling(const Node& node)
 299 {
 300     return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
 301 }
 302
 303 inline Node* ComposedTreeTraversal::traverseFirstChild(const Node& node)
 304 {
 305     return traverseChild(node, TraversalDirectionForward);
 306 }
 307
 308 inline Node* ComposedTreeTraversal::traverseLastChild(const Node& node)
 309 {
 310     return traverseChild(node, TraversalDirectionBackward);
 311 }
 312
 313 } // namespace
 314
 315 #endif