src/third_party/WebKit/Source/core/dom/shadow/ComposedTreeWalker.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 ComposedTreeWalker_h
  28 #define ComposedTreeWalker_h
  29
  30 #include "core/dom/NodeRenderingTraversal.h"
  31 #include "core/dom/shadow/InsertionPoint.h"
  32 #include "core/dom/shadow/ShadowRoot.h"
  33
  34 namespace blink {
  35
  36 class Node;
  37
  38 // FIXME: Make some functions inline to optimise the performance.
  39 // https://bugs.webkit.org/show_bug.cgi?id=82702
  40 class ComposedTreeWalker {
  41     STACK_ALLOCATED();
  42 public:
  43     typedef NodeRenderingTraversal::ParentDetails ParentTraversalDetails;
  44
  45     enum StartPolicy {
  46         CanStartFromShadowBoundary,
  47         CannotStartFromShadowBoundary
  48     };
  49
  50     ComposedTreeWalker(const Node*, StartPolicy = CannotStartFromShadowBoundary);
  51
  52     Node* get() const { return const_cast<Node*>(m_node.get()); }
  53
  54     void firstChild();
  55     void lastChild();
  56
  57     void nextSibling();
  58     void previousSibling();
  59
  60     void parent();
  61
  62     void next();
  63     void previous();
  64
  65     Node* traverseParent(const Node*, ParentTraversalDetails* = 0) const;
  66
  67 private:
  68     ComposedTreeWalker(const Node*, ParentTraversalDetails*);
  69
  70     enum TraversalDirection {
  71         TraversalDirectionForward,
  72         TraversalDirectionBackward
  73     };
  74
  75     void assertPrecondition() const
  76     {
  77 #if ENABLE(ASSERT)
  78         ASSERT(m_node);
  79         ASSERT(!m_node->isShadowRoot());
  80         ASSERT(!isActiveInsertionPoint(*m_node));
  81 #endif
  82     }
  83
  84     void assertPostcondition() const
  85     {
  86 #if ENABLE(ASSERT)
  87         if (m_node)
  88             assertPrecondition();
  89 #endif
  90     }
  91
  92     static Node* traverseNode(const Node*, TraversalDirection);
  93     static Node* traverseLightChildren(const Node*, TraversalDirection);
  94
  95     Node* traverseFirstChild(const Node*) const;
  96     Node* traverseLastChild(const Node*) const;
  97     Node* traverseChild(const Node*, TraversalDirection) const;
  98
  99     static Node* traverseNextSibling(const Node*);
 100     static Node* traversePreviousSibling(const Node*);
 101
 102     static Node* traverseSiblingOrBackToInsertionPoint(const Node*, TraversalDirection);
 103     static Node* traverseSiblingInCurrentTree(const Node*, TraversalDirection);
 104
 105     static Node* traverseSiblings(const Node*, TraversalDirection);
 106     static Node* traverseDistributedNodes(const Node*, const InsertionPoint*, TraversalDirection);
 107
 108     static Node* traverseBackToYoungerShadowRoot(const Node*, TraversalDirection);
 109
 110     Node* traverseParentOrHost(const Node*) const;
 111
 112     RawPtrWillBeMember<const Node> m_node;
 113 };
 114
 115 inline ComposedTreeWalker::ComposedTreeWalker(const Node* node, StartPolicy startPolicy)
 116     : m_node(node)
 117 {
 118 #if ENABLE(ASSERT)
 119     if (m_node && startPolicy == CannotStartFromShadowBoundary)
 120         assertPrecondition();
 121 #endif
 122 }
 123
 124 inline void ComposedTreeWalker::parent()
 125 {
 126     assertPrecondition();
 127     m_node = traverseParent(m_node);
 128     assertPostcondition();
 129 }
 130
 131 inline void ComposedTreeWalker::nextSibling()
 132 {
 133     assertPrecondition();
 134     m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionForward);
 135     assertPostcondition();
 136 }
 137
 138 inline void ComposedTreeWalker::previousSibling()
 139 {
 140     assertPrecondition();
 141     m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionBackward);
 142     assertPostcondition();
 143 }
 144
 145 inline void ComposedTreeWalker::next()
 146 {
 147     assertPrecondition();
 148     if (Node* next = traverseFirstChild(m_node)) {
 149         m_node = next;
 150     } else {
 151         while (m_node) {
 152             if (Node* sibling = traverseNextSibling(m_node)) {
 153                 m_node = sibling;
 154                 break;
 155             }
 156             m_node = traverseParent(m_node);
 157         }
 158     }
 159     assertPostcondition();
 160 }
 161
 162 inline void ComposedTreeWalker::previous()
 163 {
 164     assertPrecondition();
 165     if (Node* previous = traversePreviousSibling(m_node)) {
 166         while (Node* child = traverseLastChild(previous))
 167             previous = child;
 168         m_node = previous;
 169     } else {
 170         parent();
 171     }
 172     assertPostcondition();
 173 }
 174
 175 inline void ComposedTreeWalker::firstChild()
 176 {
 177     assertPrecondition();
 178     m_node = traverseChild(m_node, TraversalDirectionForward);
 179     assertPostcondition();
 180 }
 181
 182 inline void ComposedTreeWalker::lastChild()
 183 {
 184     assertPrecondition();
 185     m_node = traverseLastChild(m_node);
 186     assertPostcondition();
 187 }
 188
 189 inline Node* ComposedTreeWalker::traverseNextSibling(const Node* node)
 190 {
 191     ASSERT(node);
 192     return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
 193 }
 194
 195 inline Node* ComposedTreeWalker::traversePreviousSibling(const Node* node)
 196 {
 197     ASSERT(node);
 198     return traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
 199 }
 200
 201 inline Node* ComposedTreeWalker::traverseFirstChild(const Node* node) const
 202 {
 203     ASSERT(node);
 204     return traverseChild(node, TraversalDirectionForward);
 205 }
 206
 207 inline Node* ComposedTreeWalker::traverseLastChild(const Node* node) const
 208 {
 209     ASSERT(node);
 210     return traverseChild(node, TraversalDirectionBackward);
 211 }
 212
 213 } // namespace
 214
 215 #endif