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