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 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); }
     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 #ifndef NDEBUG
     78         ASSERT(m_node);
     79         ASSERT(!m_node->isShadowRoot());
     80         ASSERT(!isActiveInsertionPoint(*m_node));
     81 #endif
     82     }
     83 
     84     void assertPostcondition() const
     85     {
     86 #ifndef NDEBUG
     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*, ParentTraversalDetails* = 0) const;
    111 
    112     const Node* m_node;
    113 };
    114 
    115 inline ComposedTreeWalker::ComposedTreeWalker(const Node* node, StartPolicy startPolicy)
    116     : m_node(node)
    117 {
    118 #ifndef NDEBUG
    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
    216