Changeset 137715 in webkit


Ignore:
Timestamp:
Dec 13, 2012 10:50:52 PM (11 years ago)
Author:
morrita@google.com
Message:

NodeRenderingContext is slow due to ComposedShadowTreeWalker
https://bugs.webkit.org/show_bug.cgi?id=104332

Reviewed by Dimitri Glazkov.

NodeRenderingContext has some slowness due to the complexity of
ComposedShadowTreeWalker that NRC relies on. This change
creates some fast paths to address such slowness.

NodeRenderingTraversal module:

This change introduces NodeRenderingTraversal namespace, a sister
of NodeTraversal. NRT consists of a set of tree traversal
functions that is responsible for traversal in NRC. Before this
change, NRC directly used CSTW. This NRT module hides and narrows
the usage of CSTW.

  • Traversals provided by NRT have fast paths. In many case, such traversals don't need to use CSTW and just goes to neighboring nodes in a plain DOM way.
  • It also handles NRC specific traversal concerns like pseudo elements. CSTW::pseudoAwareNextSibling() and CSTW::pseudoAwarePreviousSibling() are merged into this module.
  • CSTW::ParentTraversalDetails is moved and renamed to NRT::ParentDetails with small modification. This is a pure refactoring: As the name implies, This class is used only by NRC and used during a traversal there.

NodeRenderingTraversal is an isolation layer between generic DOM and CSTW. This hides CSTW
behind the wall and will help further reduction of its usage.

Node::NeedsShadowTreeWalkerFlag flag:

NRT fast path is enabled by newly introduced NeedsShadowTreeWalker
node flag. Each DOM node is now markd as NeedsShadowTreeWalker if
it requires non-trivial traversal in NRT which uses CSTW. This
means that each node can go fast path unless it is marked with this flag.

A node is marked as it NeedsShadowTreeWalker if:

  • The node is a shadow boundary like InsertionPoint or ShadowRoot,
  • The node has pseudo elements like generated content or
  • The node is a pseudo element.

This criteria is defined in Node::needsShadowTreeWalkerSlow(). The node actually needs
the walker if the node or its parent is marked with this flag.

The original idea of this change was demonstrated by Antti Koivisto on bug 103208 and bug 104507.
This chagne has 2-3% speedup on Dromaeo/dom-modify/innerHTML on Apple Mac.

No new tests. Covered by existing tests.

  • CMakeLists.txt:
  • GNUmakefile.list.am:
  • Target.pri:
  • WebCore.gypi:
  • WebCore.xcodeproj/project.pbxproj:
  • dom/ComposedShadowTreeWalker.cpp:
  • dom/ComposedShadowTreeWalker.h:

(ComposedShadowTreeWalker): Move some part to NodeRenderingTraversal

  • dom/ContainerNode.h:

(WebCore::Node::needsShadowTreeWalker): Added. This is located here since it refers ContainerNode definition.
(WebCore):

  • dom/DOMAllInOne.cpp:
  • dom/Element.cpp:

(WebCore::Element::updatePseudoElement): Refactored.
(WebCore::Element::hasPseudoElements): Ditto.
(WebCore::Element::pseudoElement): Ditto.
(WebCore::Element::setPseudoElement): Refactored and added a flag update logic.
(WebCore):

  • dom/Element.h:

(Element):
(WebCore::Element::beforePseudoElement): Refactored.
(WebCore::Element::afterPseudoElement): Refactored.

  • dom/ElementRareData.h:

(WebCore::ElementRareData::hasPseudoElements): Factored out.

  • dom/ElementShadow.cpp:

(WebCore::ElementShadow::addShadowRoot): Added a flag update logic.

  • dom/Node.cpp:

(WebCore::Node::needsShadowTreeWalkerSlow): Added.

  • dom/Node.h:

(WebCore::Node::isInsertionPointNode): Added.
(Node):
(WebCore::Node::isInsertionPoint): Changed to use NeedsShadowTreeWalkerFlag.
(WebCore::Node::setNeedsShadowTreeWalker):
(WebCore::Node::resetNeedsShadowTreeWalker):

  • dom/NodeRenderingContext.cpp: Adopted NodeRenderingTraversal.

(WebCore::NodeRenderingContext::NodeRenderingContext):
(WebCore::NodeRenderingContext::nextRenderer):
(WebCore::NodeRenderingContext::previousRenderer):
(WebCore::NodeRenderingContext::parentRenderer):
(WebCore::NodeRenderingContext::shouldCreateRenderer):

  • dom/NodeRenderingContext.h: Ditto.

(NodeRenderingContext):
(WebCore::NodeRenderingContext::parentNodeForRenderingAndStyle):

  • dom/NodeRenderingTraversal.cpp: Added.

(WebCore):
(NodeRenderingTraversal):
(WebCore::NodeRenderingTraversal::ParentDetails::didTraverseInsertionPoint): Moved from ComposedShadowTreeWalker
(WebCore::NodeRenderingTraversal::ParentDetails::didTraverseShadowRoot): Ditto.
(WebCore::NodeRenderingTraversal::parentSlow): Ditto.
(WebCore::NodeRenderingTraversal::nextSiblingSlow): Ditto. The original was pseudoAwareNextSibling.
(WebCore::NodeRenderingTraversal::previousSiblingSlow): Ditto. The original was pseudoAwarePreviousSibling.

  • dom/NodeRenderingTraversal.h: Added.

(WebCore):
(NodeRenderingTraversal):
(ParentDetails): Moved from ComposedShadowTreeWalker.
(WebCore::NodeRenderingTraversal::ParentDetails::ParentDetails):
(WebCore::NodeRenderingTraversal::ParentDetails::insertionPoint):
(WebCore::NodeRenderingTraversal::ParentDetails::resetStyleInheritance):
(WebCore::NodeRenderingTraversal::ParentDetails::outOfComposition):
(WebCore::NodeRenderingTraversal::ParentDetails::childWasOutOfComposition):
(WebCore::NodeRenderingTraversal::ParentDetails::operator==):
(WebCore::NodeRenderingTraversal::parent):
(WebCore::NodeRenderingTraversal::nextSibling):
(WebCore::NodeRenderingTraversal::previousSibling):

  • dom/PseudoElement.cpp:

(WebCore::PseudoElement::PseudoElement): Added an assertion.

  • dom/Text.cpp:
  • html/HTMLOptGroupElement.cpp: Added a #include which revealed by a chagne on NodeRenderingContext.h
  • html/HTMLOptionElement.cpp: Ditto.
  • html/HTMLProgressElement.cpp: Dito.
  • html/shadow/InsertionPoint.h: Added an override of isInsertionPointNode().
Location:
trunk/Source/WebCore
Files:
2 added
24 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/CMakeLists.txt

    r137703 r137715  
    11961196    dom/NodeRareData.cpp
    11971197    dom/NodeRenderingContext.cpp
     1198    dom/NodeRenderingTraversal.cpp
    11981199    dom/NodeTraversal.cpp
    11991200    dom/Notation.cpp
  • trunk/Source/WebCore/ChangeLog

    r137713 r137715  
     12012-12-13  Hajime Morrita  <morrita@google.com>
     2
     3        NodeRenderingContext is slow due to ComposedShadowTreeWalker
     4        https://bugs.webkit.org/show_bug.cgi?id=104332
     5
     6        Reviewed by Dimitri Glazkov.
     7
     8        NodeRenderingContext has some slowness due to the complexity of
     9        ComposedShadowTreeWalker that NRC relies on. This change
     10        creates some fast paths to address such slowness.
     11
     12        = NodeRenderingTraversal module:
     13
     14        This change introduces NodeRenderingTraversal namespace, a sister
     15        of NodeTraversal. NRT consists of a set of tree traversal
     16        functions that is responsible for traversal in NRC.  Before this
     17        change, NRC directly used CSTW. This NRT module hides and narrows
     18        the usage of CSTW.
     19
     20        - Traversals provided by NRT have fast paths. In many case, such traversals
     21          don't need to use CSTW and just goes to neighboring nodes in a plain DOM way.
     22        - It also handles NRC specific traversal concerns like pseudo elements.
     23          CSTW::pseudoAwareNextSibling() and CSTW::pseudoAwarePreviousSibling() are
     24          merged into this module.
     25        - CSTW::ParentTraversalDetails is moved and renamed to
     26          NRT::ParentDetails with small modification. This is a pure
     27          refactoring: As the name implies, This class is used only by NRC
     28          and used during a traversal there.
     29
     30        NodeRenderingTraversal is an isolation layer between generic DOM and CSTW. This hides CSTW
     31        behind the wall and will help further reduction of its usage.
     32
     33        = Node::NeedsShadowTreeWalkerFlag flag:
     34
     35        NRT fast path is enabled by newly introduced NeedsShadowTreeWalker
     36        node flag. Each DOM node is now markd as NeedsShadowTreeWalker if
     37        it requires non-trivial traversal in NRT which uses CSTW. This
     38        means that each node can go fast path unless it is marked with this flag.
     39
     40        A node is marked as it NeedsShadowTreeWalker if:
     41
     42        - The node is a shadow boundary like InsertionPoint or ShadowRoot,
     43        - The node has pseudo elements like generated content or
     44        - The node is a pseudo element.
     45
     46        This criteria is defined in Node::needsShadowTreeWalkerSlow(). The node actually needs
     47        the walker if the node or its parent is marked with this flag.
     48
     49        The original idea of this change was demonstrated by Antti Koivisto on bug 103208 and bug 104507.
     50        This chagne has 2-3% speedup on Dromaeo/dom-modify/innerHTML on Apple Mac.
     51
     52        No new tests. Covered by existing tests.
     53
     54        * CMakeLists.txt:
     55        * GNUmakefile.list.am:
     56        * Target.pri:
     57        * WebCore.gypi:
     58        * WebCore.xcodeproj/project.pbxproj:
     59        * dom/ComposedShadowTreeWalker.cpp:
     60        * dom/ComposedShadowTreeWalker.h:
     61        (ComposedShadowTreeWalker): Move some part to NodeRenderingTraversal
     62        * dom/ContainerNode.h:
     63        (WebCore::Node::needsShadowTreeWalker): Added. This is located here since it refers ContainerNode definition.
     64        (WebCore):
     65        * dom/DOMAllInOne.cpp:
     66        * dom/Element.cpp:
     67        (WebCore::Element::updatePseudoElement): Refactored.
     68        (WebCore::Element::hasPseudoElements): Ditto.
     69        (WebCore::Element::pseudoElement): Ditto.
     70        (WebCore::Element::setPseudoElement): Refactored and added a flag update logic.
     71        (WebCore):
     72        * dom/Element.h:
     73        (Element):
     74        (WebCore::Element::beforePseudoElement): Refactored.
     75        (WebCore::Element::afterPseudoElement): Refactored.
     76        * dom/ElementRareData.h:
     77        (WebCore::ElementRareData::hasPseudoElements): Factored out.
     78        * dom/ElementShadow.cpp:
     79        (WebCore::ElementShadow::addShadowRoot): Added a flag update logic.
     80        * dom/Node.cpp:
     81        (WebCore::Node::needsShadowTreeWalkerSlow): Added.
     82        * dom/Node.h:
     83        (WebCore::Node::isInsertionPointNode): Added.
     84        (Node):
     85        (WebCore::Node::isInsertionPoint): Changed to use NeedsShadowTreeWalkerFlag.
     86        (WebCore::Node::setNeedsShadowTreeWalker):
     87        (WebCore::Node::resetNeedsShadowTreeWalker):
     88        * dom/NodeRenderingContext.cpp: Adopted NodeRenderingTraversal.
     89        (WebCore::NodeRenderingContext::NodeRenderingContext):
     90        (WebCore::NodeRenderingContext::nextRenderer):
     91        (WebCore::NodeRenderingContext::previousRenderer):
     92        (WebCore::NodeRenderingContext::parentRenderer):
     93        (WebCore::NodeRenderingContext::shouldCreateRenderer):
     94        * dom/NodeRenderingContext.h: Ditto.
     95        (NodeRenderingContext):
     96        (WebCore::NodeRenderingContext::parentNodeForRenderingAndStyle):
     97        * dom/NodeRenderingTraversal.cpp: Added.
     98        (WebCore):
     99        (NodeRenderingTraversal):
     100        (WebCore::NodeRenderingTraversal::ParentDetails::didTraverseInsertionPoint): Moved from ComposedShadowTreeWalker
     101        (WebCore::NodeRenderingTraversal::ParentDetails::didTraverseShadowRoot): Ditto.
     102        (WebCore::NodeRenderingTraversal::parentSlow): Ditto.
     103        (WebCore::NodeRenderingTraversal::nextSiblingSlow): Ditto. The original was pseudoAwareNextSibling.
     104        (WebCore::NodeRenderingTraversal::previousSiblingSlow): Ditto. The original was pseudoAwarePreviousSibling.
     105        * dom/NodeRenderingTraversal.h: Added.
     106        (WebCore):
     107        (NodeRenderingTraversal):
     108        (ParentDetails): Moved from ComposedShadowTreeWalker.
     109        (WebCore::NodeRenderingTraversal::ParentDetails::ParentDetails):
     110        (WebCore::NodeRenderingTraversal::ParentDetails::insertionPoint):
     111        (WebCore::NodeRenderingTraversal::ParentDetails::resetStyleInheritance):
     112        (WebCore::NodeRenderingTraversal::ParentDetails::outOfComposition):
     113        (WebCore::NodeRenderingTraversal::ParentDetails::childWasOutOfComposition):
     114        (WebCore::NodeRenderingTraversal::ParentDetails::operator==):
     115        (WebCore::NodeRenderingTraversal::parent):
     116        (WebCore::NodeRenderingTraversal::nextSibling):
     117        (WebCore::NodeRenderingTraversal::previousSibling):
     118        * dom/PseudoElement.cpp:
     119        (WebCore::PseudoElement::PseudoElement): Added an assertion.
     120        * dom/Text.cpp:
     121        * html/HTMLOptGroupElement.cpp: Added a #include which revealed by a chagne on NodeRenderingContext.h
     122        * html/HTMLOptionElement.cpp: Ditto.
     123        * html/HTMLProgressElement.cpp: Dito.
     124        * html/shadow/InsertionPoint.h: Added an override of isInsertionPointNode().
     125
    11262012-12-13  Kent Tamura  <tkent@chromium.org>
    2127
  • trunk/Source/WebCore/GNUmakefile.list.am

    r137703 r137715  
    28812881        Source/WebCore/dom/NodeRareData.h \
    28822882        Source/WebCore/dom/NodeRenderingContext.h \
     2883        Source/WebCore/dom/NodeRenderingTraversal.h \
     2884        Source/WebCore/dom/NodeRenderingTraversal.cpp \
    28832885        Source/WebCore/dom/NodeRenderStyle.h \
    28842886    Source/WebCore/dom/NodeTraversal.cpp \
  • trunk/Source/WebCore/Target.pri

    r137703 r137715  
    421421    dom/NodeRareData.cpp \
    422422    dom/NodeRenderingContext.cpp \
     423    dom/NodeRenderingTraversal.cpp \
    423424    dom/NodeTraversal.cpp \
    424425    dom/Notation.cpp \
     
    16051606    dom/NodeRareData.h \
    16061607    dom/NodeRenderingContext.h \
     1608    dom/NodeRenderingTraversal.h \
    16071609    dom/NodeTraversal.h \
    16081610    dom/Notation.h \
  • trunk/Source/WebCore/WebCore.gypi

    r137703 r137715  
    28462846            'dom/NodeRenderingContext.cpp',
    28472847            'dom/NodeRenderingContext.h',
     2848            'dom/NodeRenderingTraversal.cpp',
     2849            'dom/NodeRenderingTraversal.h',
    28482850            'dom/NodeRenderStyle.h',
    28492851            'dom/NodeTraversal.cpp',
  • trunk/Source/WebCore/WebCore.xcodeproj/project.pbxproj

    r137703 r137715  
    38893889                A740B5A714C935AF00A77FA4 /* JSInternalSettings.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7B4EA7814C9348400C8F5BF /* JSInternalSettings.cpp */; };
    38903890                A74BB76B13BDA86300FF7BF0 /* ExceptionCodePlaceholder.h in Headers */ = {isa = PBXBuildFile; fileRef = A74BB76A13BDA86300FF7BF0 /* ExceptionCodePlaceholder.h */; settings = {ATTRIBUTES = (Private, ); }; };
     3891                A74F3EF31678B24A00B05A6E /* NodeRenderingTraversal.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A7211F231678A54200957444 /* NodeRenderingTraversal.cpp */; };
     3892                A74F3EF51678B24F00B05A6E /* NodeRenderingTraversal.h in Headers */ = {isa = PBXBuildFile; fileRef = A7211F241678A54200957444 /* NodeRenderingTraversal.h */; };
    38913893                A75E497610752ACB00C9B896 /* SerializedScriptValue.h in Headers */ = {isa = PBXBuildFile; fileRef = A75E497410752ACB00C9B896 /* SerializedScriptValue.h */; settings = {ATTRIBUTES = (Private, ); }; };
    38923894                A75E497710752ACB00C9B896 /* SerializedScriptValue.cpp in Sources */ = {isa = PBXBuildFile; fileRef = A75E497510752ACB00C9B896 /* SerializedScriptValue.cpp */; };
     
    1121211214                A718788F0B2D04AC00A16ECE /* DragControllerMac.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = DragControllerMac.mm; sourceTree = "<group>"; };
    1121311215                A71A70C911AFB02000989D6D /* HTMLMeterElement.idl */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = text; path = HTMLMeterElement.idl; sourceTree = "<group>"; };
     11216                A7211F231678A54200957444 /* NodeRenderingTraversal.cpp */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = NodeRenderingTraversal.cpp; sourceTree = "<group>"; };
     11217                A7211F241678A54200957444 /* NodeRenderingTraversal.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = NodeRenderingTraversal.h; sourceTree = "<group>"; };
    1121411218                A723F77A1484CA4C008C6DBE /* PlatformExportMacros.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = PlatformExportMacros.h; sourceTree = "<group>"; };
    1121511219                A72763BE16689BFB002FCACB /* UserActionElementSet.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = UserActionElementSet.h; sourceTree = "<group>"; };
     
    2210122105                                A7F5D94D1384F02D00A29A87 /* NodeRenderingContext.cpp */,
    2210222106                                A7F5D94E1384F02D00A29A87 /* NodeRenderingContext.h */,
     22107                                A7211F231678A54200957444 /* NodeRenderingTraversal.cpp */,
     22108                                A7211F241678A54200957444 /* NodeRenderingTraversal.h */,
    2210322109                                63D7B32C0E78CD3F00F7617C /* NodeRenderStyle.h */,
    2210422110                                E43105B716750F0C00DB2FB8 /* NodeTraversal.cpp */,
     
    2480624812                                63189AE30E83A33300012E41 /* NodeRareData.h in Headers */,
    2480724813                                A7F5D9501384F02D00A29A87 /* NodeRenderingContext.h in Headers */,
     24814                                A74F3EF51678B24F00B05A6E /* NodeRenderingTraversal.h in Headers */,
    2480824815                                63D7B32D0E78CD3F00F7617C /* NodeRenderStyle.h in Headers */,
    2480924816                                9382AAB40D8C386100F357A6 /* NodeWithIndex.h in Headers */,
     
    2812628133                                854FE7340A2297BE0058D7AD /* NodeIterator.cpp in Sources */,
    2812728134                                A7F5D94F1384F02D00A29A87 /* NodeRenderingContext.cpp in Sources */,
     28135                                A74F3EF31678B24A00B05A6E /* NodeRenderingTraversal.cpp in Sources */,
    2812828136                                A8EA7EBF0A1945D000A8EF5F /* Notation.cpp in Sources */,
    2812928137                                33503CC71017A1B1003B47E1 /* Notification.cpp in Sources */,
  • trunk/Source/WebCore/dom/ComposedShadowTreeWalker.cpp

    r137418 r137715  
     1
    12/*
    23 * Copyright (C) 2012 Google Inc. All rights reserved.
     
    7172}
    7273
    73 inline void ComposedShadowTreeWalker::ParentTraversalDetails::didTraverseInsertionPoint(InsertionPoint* insertionPoint)
    74 {
    75     if (!m_insertionPoint) {
    76         m_insertionPoint = insertionPoint;
    77         m_resetStyleInheritance  = m_resetStyleInheritance || insertionPoint->resetStyleInheritance();
    78     }
    79 }
    80 
    81 inline void ComposedShadowTreeWalker::ParentTraversalDetails::didTraverseShadowRoot(const ShadowRoot* root)
    82 {
    83     m_resetStyleInheritance  = m_resetStyleInheritance || root->resetStyleInheritance();
    84 }
    85 
    86 inline void ComposedShadowTreeWalker::ParentTraversalDetails::didFindNode(ContainerNode* node)
    87 {
    88     if (!m_outOfComposition)
    89         m_node = node;
    90 }
    91 
    9274ComposedShadowTreeWalker ComposedShadowTreeWalker::fromFirstChild(const Node* node, Policy policy)
    9375{
     
    9577    walker.firstChild();
    9678    return walker;
    97 }
    98 
    99 void ComposedShadowTreeWalker::findParent(const Node* node, ParentTraversalDetails* details)
    100 {
    101     ComposedShadowTreeWalker walker(node, CrossUpperBoundary, CanStartFromShadowBoundary);
    102     ContainerNode* found = toContainerNode(walker.traverseParent(walker.get(), details));
    103     if (found)
    104         details->didFindNode(found);
    10579}
    10680
     
    181155    assertPrecondition();
    182156    m_node = traverseSiblingOrBackToInsertionPoint(m_node, TraversalDirectionBackward);
    183     assertPostcondition();
    184 }
    185 
    186 void ComposedShadowTreeWalker::pseudoAwareNextSibling()
    187 {
    188     assertPrecondition();
    189 
    190     const Node* node = m_node;
    191 
    192     if (node->isBeforePseudoElement())
    193         m_node = traverseFirstChild(traverseParent(node));
    194     else
    195         m_node = traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionForward);
    196 
    197     if (!m_node && !node->isAfterPseudoElement()) {
    198         Node* parent = traverseParent(node);
    199         if (parent && parent->isElementNode())
    200             m_node = toElement(parent)->afterPseudoElement();
    201     }
    202 
    203     assertPostcondition();
    204 }
    205 
    206 void ComposedShadowTreeWalker::pseudoAwarePreviousSibling()
    207 {
    208     assertPrecondition();
    209 
    210     const Node* node = m_node;
    211 
    212     if (node->isAfterPseudoElement())
    213         m_node = traverseLastChild(traverseParent(node));
    214     else
    215         m_node = traverseSiblingOrBackToInsertionPoint(node, TraversalDirectionBackward);
    216 
    217     if (!m_node && !node->isBeforePseudoElement()) {
    218         Node* parent = traverseParent(node);
    219         if (parent && parent->isElementNode())
    220             m_node = toElement(parent)->beforePseudoElement();
    221     }
    222 
    223157    assertPostcondition();
    224158}
  • trunk/Source/WebCore/dom/ComposedShadowTreeWalker.h

    r137336 r137715  
    2929
    3030#include "InsertionPoint.h"
     31#include "NodeRenderingTraversal.h"
    3132#include "ShadowRoot.h"
    3233
     
    4041class ComposedShadowTreeWalker {
    4142public:
     43    typedef NodeRenderingTraversal::ParentDetails ParentTraversalDetails;
     44
    4245    enum Policy {
    4346        CrossUpperBoundary,
     
    5053    };
    5154
    52     class ParentTraversalDetails {
    53     public:
    54         ParentTraversalDetails()
    55             : m_node(0)
    56             , m_insertionPoint(0)
    57             , m_resetStyleInheritance(false)
    58             , m_outOfComposition(false)
    59         { }
    60 
    61         ContainerNode* node() const { return m_node; }
    62         InsertionPoint* insertionPoint() const { return m_insertionPoint; }
    63         bool resetStyleInheritance() const { return m_resetStyleInheritance; }
    64         bool outOfComposition() const { return m_outOfComposition; }
    65 
    66         void didFindNode(ContainerNode*);
    67         void didTraverseInsertionPoint(InsertionPoint*);
    68         void didTraverseShadowRoot(const ShadowRoot*);
    69         void childWasOutOfComposition() { m_outOfComposition = true; }
    70 
    71     private:
    72         ContainerNode* m_node;
    73         InsertionPoint* m_insertionPoint;
    74         bool m_resetStyleInheritance;
    75         bool m_outOfComposition;
    76     };
    77 
    7855    ComposedShadowTreeWalker(const Node*, Policy = CrossUpperBoundary, StartPolicy = CannotStartFromShadowBoundary);
    7956
     
    8158    // for (ComposedShadowTreeWalker walker = ComposedShadowTreeWalker::fromFirstChild(node); walker.get(); walker.nextSibling())
    8259    static ComposedShadowTreeWalker fromFirstChild(const Node*, Policy = CrossUpperBoundary);
    83     static void findParent(const Node*, ParentTraversalDetails*);
    8460
    8561    Node* get() const { return const_cast<Node*>(m_node); }
     
    9167    void previousSibling();
    9268
    93     void pseudoAwareNextSibling();
    94     void pseudoAwarePreviousSibling();
    95 
    9669    void parent();
    9770
    9871    void next();
    9972    void previous();
     73
     74    Node* traverseParent(const Node*, ParentTraversalDetails* = 0) const;
    10075
    10176private:
     
    135110    Node* traverseLastChild(const Node*) const;
    136111    Node* traverseChild(const Node*, TraversalDirection) const;
    137     Node* traverseParent(const Node*, ParentTraversalDetails* = 0) const;
    138112
    139113    static Node* traverseNextSibling(const Node*);
  • trunk/Source/WebCore/dom/ContainerNode.h

    r137702 r137715  
    266266}
    267267
     268inline bool Node::needsShadowTreeWalker() const
     269{
     270    if (getFlag(NeedsShadowTreeWalkerFlag))
     271        return true;
     272    ContainerNode* parent = parentOrHostNode();
     273    return parent && parent->getFlag(NeedsShadowTreeWalkerFlag);
     274}
     275
    268276// This constant controls how much buffer is initially allocated
    269277// for a Node Vector that is used to store child Nodes of a given Node.
  • trunk/Source/WebCore/dom/DOMAllInOne.cpp

    r137277 r137715  
    106106#include "NodeIterator.cpp"
    107107#include "NodeRenderingContext.cpp"
     108#include "NodeRenderingTraversal.cpp"
    108109#include "Notation.cpp"
    109110#include "OverflowEvent.cpp"
  • trunk/Source/WebCore/dom/Element.cpp

    r137535 r137715  
    20992099void Element::updatePseudoElement(PseudoId pseudoId, StyleChange change)
    21002100{
    2101     PseudoElement* existing = hasRareData() ? elementRareData()->pseudoElement(pseudoId) : 0;
     2101    PseudoElement* existing = pseudoElement(pseudoId);
    21022102    if (existing) {
    21032103        // PseudoElement styles hang off their parent element's style so if we needed
     
    21102110        // PseudoElement's renderer for each style recalc.
    21112111        if (!renderer() || !pseudoElementRendererIsNeeded(renderer()->getCachedPseudoStyle(pseudoId)))
    2112             elementRareData()->setPseudoElement(pseudoId, 0);
     2112            setPseudoElement(pseudoId, 0);
    21132113    } else if (RefPtr<PseudoElement> element = createPseudoElementIfNeeded(pseudoId)) {
    21142114        element->attach();
    2115         ensureElementRareData()->setPseudoElement(pseudoId, element.release());
     2115        setPseudoElement(pseudoId, element.release());
    21162116    }
    21172117}
     
    21342134}
    21352135
    2136 PseudoElement* Element::beforePseudoElement() const
    2137 {
    2138     return hasRareData() ? elementRareData()->pseudoElement(BEFORE) : 0;
    2139 }
    2140 
    2141 PseudoElement* Element::afterPseudoElement() const
    2142 {
    2143     return hasRareData() ? elementRareData()->pseudoElement(AFTER) : 0;
    2144 }
     2136bool Element::hasPseudoElements() const
     2137{
     2138    return hasRareData() && elementRareData()->hasPseudoElements();
     2139}
     2140
     2141PseudoElement* Element::pseudoElement(PseudoId pseudoId) const
     2142{
     2143    return hasRareData() ? elementRareData()->pseudoElement(pseudoId) : 0;
     2144}
     2145
     2146void Element::setPseudoElement(PseudoId pseudoId, PassRefPtr<PseudoElement> element)
     2147{
     2148    ensureElementRareData()->setPseudoElement(pseudoId, element);
     2149    resetNeedsShadowTreeWalker();
     2150}
     2151
    21452152
    21462153// ElementTraversal API
  • trunk/Source/WebCore/dom/Element.h

    r137463 r137715  
    367367    virtual void beginParsingChildren();
    368368
    369     PseudoElement* beforePseudoElement() const;
    370     PseudoElement* afterPseudoElement() const;
     369    bool hasPseudoElements() const;
     370    PseudoElement* pseudoElement(PseudoId) const;
     371    PseudoElement* beforePseudoElement() const { return pseudoElement(BEFORE); }
     372    PseudoElement* afterPseudoElement() const { return pseudoElement(AFTER); }
     373    bool childNeedsShadowWalker() const;
     374    void didShadowTreeAwareChildrenChange();
    371375
    372376    // ElementTraversal API
     
    501505    void updatePseudoElement(PseudoId, StyleChange = NoChange);
    502506    PassRefPtr<PseudoElement> createPseudoElementIfNeeded(PseudoId);
     507    void setPseudoElement(PseudoId, PassRefPtr<PseudoElement>);
    503508
    504509    // FIXME: Remove the need for Attr to call willModifyAttribute/didModifyAttribute.
  • trunk/Source/WebCore/dom/ElementRareData.h

    r137535 r137715  
    4141    void setPseudoElement(PseudoId, PassRefPtr<PseudoElement>);
    4242    PseudoElement* pseudoElement(PseudoId) const;
     43    bool hasPseudoElements() const { return m_generatedBefore || m_generatedAfter; }
    4344
    4445    void resetComputedStyle();
  • trunk/Source/WebCore/dom/ElementShadow.cpp

    r137429 r137715  
    8888    ChildNodeInsertionNotifier(shadowHost).notify(shadowRoot.get());
    8989
     90    // Existence of shadow roots requires the host and its children to do traversal using ComposedShadowTreeWalker.
     91    shadowHost->setNeedsShadowTreeWalker();
     92
    9093    // FIXME(94905): ShadowHost should be reattached during recalcStyle.
    9194    // Set some flag here and recreate shadow hosts' renderer in
  • trunk/Source/WebCore/dom/Node.cpp

    r137570 r137715  
    12911291}
    12921292
     1293bool Node::needsShadowTreeWalkerSlow() const
     1294{
     1295    return (isShadowRoot() || (isElementNode() && (isInsertionPoint() || isPseudoElement() || toElement(this)->hasPseudoElements() || toElement(this)->shadow())));
     1296}
    12931297
    12941298bool Node::isBlockFlow() const
  • trunk/Source/WebCore/dom/Node.h

    r137535 r137715  
    248248    virtual bool isPluginElement() const { return false; }
    249249    virtual bool documentFragmentIsShadowRoot() const;
     250    virtual bool isInsertionPointNode() const { return false; }
     251
    250252    bool isDocumentNode() const;
    251253    bool isDocumentFragment() const { return getFlag(IsDocumentFragmentFlag); }
    252254    bool isShadowRoot() const { return isDocumentFragment() && documentFragmentIsShadowRoot(); }
    253     bool isInsertionPoint() const { return getFlag(IsInsertionPointFlag); }
     255    bool isInsertionPoint() const { return getFlag(NeedsShadowTreeWalkerFlag) && isInsertionPointNode(); }
     256
     257    bool needsShadowTreeWalker() const;
     258    bool needsShadowTreeWalkerSlow() const;
     259    void setNeedsShadowTreeWalker() { setFlag(NeedsShadowTreeWalkerFlag); }
     260    void resetNeedsShadowTreeWalker() { setFlag(needsShadowTreeWalkerSlow(), NeedsShadowTreeWalkerFlag); }
     261
    254262    bool inNamedFlow() const { return getFlag(InNamedFlowFlag); }
    255263    bool hasCustomCallbacks() const { return getFlag(HasCustomCallbacksFlag); }
     
    704712        HasEventTargetDataFlag = 1 << 23,
    705713        V8CollectableDuringMinorGCFlag = 1 << 24,
    706         IsInsertionPointFlag = 1 << 25,
     714        NeedsShadowTreeWalkerFlag = 1 << 25,
    707715
    708716        DefaultNodeFlags = IsParsingChildrenFinishedFlag
     
    722730        CreateContainer = DefaultNodeFlags | IsContainerFlag,
    723731        CreateElement = CreateContainer | IsElementFlag,
    724         CreatePseudoElement =  CreateElement | InDocumentFlag,
    725         CreateShadowRoot = CreateContainer | IsDocumentFragmentFlag,
     732        CreatePseudoElement =  CreateElement | InDocumentFlag | NeedsShadowTreeWalkerFlag,
     733        CreateShadowRoot = CreateContainer | IsDocumentFragmentFlag | NeedsShadowTreeWalkerFlag,
    726734        CreateDocumentFragment = CreateContainer | IsDocumentFragmentFlag,
    727735        CreateStyledElement = CreateElement | IsStyledElementFlag,
     
    730738        CreateSVGElement = CreateStyledElement | IsSVGFlag,
    731739        CreateDocument = CreateContainer | InDocumentFlag,
    732         CreateInsertionPoint = CreateHTMLElement | IsInsertionPointFlag,
     740        CreateInsertionPoint = CreateHTMLElement | NeedsShadowTreeWalkerFlag,
    733741        CreateEditingText = CreateText | HasNameOrIsEditingTextFlag,
    734742    };
  • trunk/Source/WebCore/dom/NodeRenderingContext.cpp

    r137418 r137715  
    2727#include "NodeRenderingContext.h"
    2828
    29 #include "ComposedShadowTreeWalker.h"
    3029#include "ContainerNode.h"
    3130#include "ContentDistributor.h"
     
    6059    , m_parentFlowRenderer(0)
    6160{
    62     ComposedShadowTreeWalker::findParent(m_node, &m_parentDetails);
     61    m_renderingParent = NodeRenderingTraversal::parent(node, &m_parentDetails);
    6362}
    6463
    6564NodeRenderingContext::NodeRenderingContext(Node* node, RenderStyle* style)
    6665    : m_node(node)
     66    , m_renderingParent(0)
    6767    , m_style(style)
    6868    , m_parentFlowRenderer(0)
     
    8484    // Avoid an O(N^2) problem with this function by not checking for
    8585    // nextRenderer() when the parent element hasn't attached yet.
    86     if (m_parentDetails.node() && !m_parentDetails.node()->attached())
     86    if (m_renderingParent && !m_renderingParent->attached())
    8787        return 0;
    8888
    89     ComposedShadowTreeWalker walker(m_node);
    90     for (walker.pseudoAwareNextSibling(); walker.get(); walker.pseudoAwareNextSibling()) {
    91         if (RenderObject* renderer = walker.get()->renderer()) {
     89    for (Node* sibling = NodeRenderingTraversal::nextSibling(m_node); sibling; sibling = NodeRenderingTraversal::nextSibling(sibling)) {
     90        if (RenderObject* renderer = sibling->renderer()) {
    9291            // Renderers for elements attached to a flow thread should be skipped because they are parented differently.
    9392            if (renderer->node()->isElementNode() && renderer->style() && !renderer->style()->flowThread().isEmpty())
     
    110109    // FIXME: We should have the same O(N^2) avoidance as nextRenderer does
    111110    // however, when I tried adding it, several tests failed.
    112 
    113     ComposedShadowTreeWalker walker(m_node);
    114     for (walker.pseudoAwarePreviousSibling(); walker.get(); walker.pseudoAwarePreviousSibling()) {
    115         if (RenderObject* renderer = walker.get()->renderer()) {
     111    for (Node* sibling = NodeRenderingTraversal::previousSibling(m_node); sibling; sibling = NodeRenderingTraversal::previousSibling(sibling)) {
     112        if (RenderObject* renderer = sibling->renderer()) {
    116113            // Renderers for elements attached to a flow thread should be skipped because they are parented differently.
    117114            if (renderer->node()->isElementNode() && renderer->style() && !renderer->style()->flowThread().isEmpty())
     
    131128        return m_parentFlowRenderer;
    132129
    133     return m_parentDetails.node() ? m_parentDetails.node()->renderer() : 0;
     130    return m_renderingParent ? m_renderingParent->renderer() : 0;
    134131}
    135132
     
    138135    if (!m_node->document()->shouldCreateRenderers())
    139136        return false;
    140     if (!m_parentDetails.node())
     137    if (!m_renderingParent)
    141138        return false;
    142139    RenderObject* parentRenderer = this->parentRenderer();
     
    145142    if (!parentRenderer->canHaveChildren())
    146143        return false;
    147     if (!m_parentDetails.node()->childShouldCreateRenderer(*this))
     144    if (!m_renderingParent->childShouldCreateRenderer(*this))
    148145        return false;
    149146    return true;
  • trunk/Source/WebCore/dom/NodeRenderingContext.h

    r135668 r137715  
    2727#define NodeRenderingContext_h
    2828
    29 #include "ComposedShadowTreeWalker.h"
     29#include "NodeRenderingTraversal.h"
     30
    3031#include <wtf/Noncopyable.h>
    3132#include <wtf/RefPtr.h>
     
    7071
    7172    Node* m_node;
    72     ComposedShadowTreeWalker::ParentTraversalDetails m_parentDetails;
     73    ContainerNode* m_renderingParent;
     74    NodeRenderingTraversal::ParentDetails m_parentDetails;
    7375    RefPtr<RenderStyle> m_style;
    7476    RenderNamedFlowThread* m_parentFlowRenderer;
     
    8385inline ContainerNode* NodeRenderingContext::parentNodeForRenderingAndStyle() const
    8486{
    85     return m_parentDetails.node();
     87    return m_renderingParent;
    8688}
    8789
  • trunk/Source/WebCore/dom/PseudoElement.cpp

    r136744 r137715  
    4444    , m_pseudoId(pseudoId)
    4545{
     46    ASSERT(pseudoId != NOPSEUDO);
    4647    ASSERT(parent->inDocument());
    4748    setParentOrHostNode(parent);
  • trunk/Source/WebCore/dom/Text.cpp

    r137418 r137715  
    2727#include "RenderCombineText.h"
    2828#include "RenderText.h"
     29#include "ShadowRoot.h"
    2930
    3031#if ENABLE(SVG)
  • trunk/Source/WebCore/html/HTMLOptGroupElement.cpp

    r135069 r137715  
    2727
    2828#include "Document.h"
     29#include "ElementShadow.h"
    2930#include "HTMLNames.h"
    3031#include "HTMLSelectElement.h"
  • trunk/Source/WebCore/html/HTMLOptionElement.cpp

    r137221 r137715  
    3030#include "Attribute.h"
    3131#include "Document.h"
     32#include "ElementShadow.h"
    3233#include "ExceptionCode.h"
    3334#include "HTMLDataListElement.h"
  • trunk/Source/WebCore/html/HTMLProgressElement.cpp

    r135069 r137715  
    2424#if ENABLE(PROGRESS_ELEMENT)
    2525#include "Attribute.h"
     26#include "ElementShadow.h"
    2627#include "EventNames.h"
    2728#include "ExceptionCode.h"
    28 #include "NodeRenderingContext.h"
    2929#include "HTMLDivElement.h"
    3030#include "HTMLNames.h"
    3131#include "HTMLParserIdioms.h"
     32#include "NodeRenderingContext.h"
    3233#include "ProgressShadowElement.h"
    3334#include "RenderProgress.h"
  • trunk/Source/WebCore/html/shadow/InsertionPoint.h

    r137233 r137715  
    8888    virtual void removedFrom(ContainerNode*) OVERRIDE;
    8989    virtual void parseAttribute(const QualifiedName&, const AtomicString&) OVERRIDE;
    90 
     90    virtual bool isInsertionPointNode() const OVERRIDE { return true; }
    9191private:
    9292
Note: See TracChangeset for help on using the changeset viewer.