Changeset 166303 in webkit


Ignore:
Timestamp:
Mar 26, 2014 11:35:55 AM (10 years ago)
Author:
Antti Koivisto
Message:

Render tree construction is O(N2) in number of siblings
​https://bugs.webkit.org/show_bug.cgi?id=129065

Source/WebCore:

Reviewed by Darin Adler.

When adding a new renderer to the tree we would search for the correct render tree
position by traversing DOM children forward to find something that already has a renderer.
In common case there is no such renderer. This would be repeated for each inserted renderer
leading to O(n2) in respect to child node count.

This patch caches the computed render tree insertion position and passes it to siblings.
Until the cached position is reached it can be used for all new renderers.

Test: perf/sibling-renderer-On2.html

  • style/StyleResolveTree.cpp:

(WebCore::Style::RenderTreePosition::parent):
(WebCore::Style::RenderTreePosition::RenderTreePosition):
(WebCore::Style::RenderTreePosition::canInsert):
(WebCore::Style::RenderTreePosition::insert):
(WebCore::Style::RenderTreePosition::computeNextSibling):
(WebCore::Style::RenderTreePosition::invalidateNextSibling):
(WebCore::Style::styleForElement):
(WebCore::Style::elementInsideRegionNeedsRenderer):
(WebCore::Style::createRendererIfNeeded):
(WebCore::Style::createTextRendererIfNeeded):
(WebCore::Style::attachTextRenderer):
(WebCore::Style::updateTextRendererAfterContentChange):
(WebCore::Style::attachChildren):
(WebCore::Style::attachDistributedChildren):
(WebCore::Style::attachShadowRoot):
(WebCore::Style::attachBeforeOrAfterPseudoElementIfNeeded):
(WebCore::Style::attachRenderTree):
(WebCore::Style::resolveLocal):
(WebCore::Style::resolveTextNode):
(WebCore::Style::resolveShadowTree):
(WebCore::Style::updateBeforeOrAfterPseudoElement):
(WebCore::Style::resolveTree):

LayoutTests:

Reviewed by Darin Adler.

  • perf/sibling-renderer-On2-expected.txt: Added.
  • perf/sibling-renderer-On2.html: Added.


The test doesn't use magnitude-perf.js as this requires a relatively long-running test function and
it seemed unsuitable for that.

Location:
trunk
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed

  • trunk/LayoutTests/ChangeLog

    r166301 r166303  
     12014-03-26  Antti Koivisto  <antti@apple.com>
     2
     3        Render tree construction is O(N^2) in number of siblings
     4        https://bugs.webkit.org/show_bug.cgi?id=129065
     5
     6        Reviewed by Darin Adler.
     7
     8        * perf/sibling-renderer-On2-expected.txt: Added.
     9        * perf/sibling-renderer-On2.html: Added.
     10       
     11            The test doesn't use magnitude-perf.js as this requires a relatively long-running test function and
     12            it seemed unsuitable for that.
     13
    1142014-03-26  Zoltan Horvath  <zoltan@webkit.org>
    215

  • trunk/Source/WebCore/ChangeLog

    r166302 r166303  
     12014-03-26  Antti Koivisto  <antti@apple.com>
     2
     3        Render tree construction is O(N^2) in number of siblings
     4        https://bugs.webkit.org/show_bug.cgi?id=129065
     5
     6        Reviewed by Darin Adler.
     7       
     8        When adding a new renderer to the tree we would search for the correct render tree
     9        position by traversing DOM children forward to find something that already has a renderer.
     10        In common case there is no such renderer. This would be repeated for each inserted renderer
     11        leading to O(n^2) in respect to child node count.
     12       
     13        This patch caches the computed render tree insertion position and passes it to siblings.
     14        Until the cached position is reached it can be used for all new renderers.
     15
     16        Test: perf/sibling-renderer-On2.html
     17
     18        * style/StyleResolveTree.cpp:
     19        (WebCore::Style::RenderTreePosition::parent):
     20        (WebCore::Style::RenderTreePosition::RenderTreePosition):
     21        (WebCore::Style::RenderTreePosition::canInsert):
     22        (WebCore::Style::RenderTreePosition::insert):
     23        (WebCore::Style::RenderTreePosition::computeNextSibling):
     24        (WebCore::Style::RenderTreePosition::invalidateNextSibling):
     25        (WebCore::Style::styleForElement):
     26        (WebCore::Style::elementInsideRegionNeedsRenderer):
     27        (WebCore::Style::createRendererIfNeeded):
     28        (WebCore::Style::createTextRendererIfNeeded):
     29        (WebCore::Style::attachTextRenderer):
     30        (WebCore::Style::updateTextRendererAfterContentChange):
     31        (WebCore::Style::attachChildren):
     32        (WebCore::Style::attachDistributedChildren):
     33        (WebCore::Style::attachShadowRoot):
     34        (WebCore::Style::attachBeforeOrAfterPseudoElementIfNeeded):
     35        (WebCore::Style::attachRenderTree):
     36        (WebCore::Style::resolveLocal):
     37        (WebCore::Style::resolveTextNode):
     38        (WebCore::Style::resolveShadowTree):
     39        (WebCore::Style::updateBeforeOrAfterPseudoElement):
     40        (WebCore::Style::resolveTree):
     41
    1422014-03-26  Commit Queue  <commit-queue@webkit.org>
    243

  • trunk/Source/WebCore/style/StyleResolveTree.cpp

    r166173 r166303  
    55 *           (C) 2001 Dirk Mueller (mueller@kde.org)
    66 *           (C) 2007 David Smith (catfish.man@gmail.com)
    7  * Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2012, 2013 Apple Inc. All rights reserved.
     7 * Copyright (C) 2004-2010, 2012-2014 Apple Inc. All rights reserved.
    88 *           (C) 2007 Eric Seidel (eric@webkit.org)
    99 *
    … …  
    6262enum DetachType { NormalDetach, ReattachDetach };
    6363
    64 static void attachRenderTree(Element&, ContainerNode& renderingParentNode, PassRefPtr<RenderStyle>);
    65 static void attachTextRenderer(Text&, ContainerNode& renderingParentNode);
     64class RenderTreePosition {
     65public:
     66    RenderTreePosition(RenderElement* parent);
     67    RenderTreePosition(RenderElement* parent, RenderObject* nextSibling);
     68
     69    RenderElement* parent() { return m_parent; }
     70
     71    void insert(RenderObject&);
     72    bool canInsert(RenderElement&) const;
     73    bool canInsert(RenderText&) const;
     74
     75    void computeNextSibling(const Node&, ContainerNode& renderingParentNode);
     76    void invalidateNextSibling(const RenderObject&);
     77
     78private:
     79    RenderElement* m_parent;
     80    RenderObject* m_nextSibling;
     81    bool m_hasValidNextSibling;
     82#if !ASSERT_DISABLED
     83    unsigned m_assertionLimitCounter;
     84#endif
     85};
     86
     87static void attachRenderTree(Element&, ContainerNode& renderingParentNode, RenderTreePosition&, PassRefPtr<RenderStyle>);
     88static void attachTextRenderer(Text&, ContainerNode& renderingParentNode, RenderTreePosition&);
    6689static void detachRenderTree(Element&, DetachType);
    67 static void resolveTextNode(Text&, ContainerNode& renderingParentNode);
    68 static void resolveTree(Element&, ContainerNode& renderingParentNode, Change);
     90static void resolveTextNode(Text&, ContainerNode& renderingParentNode, RenderTreePosition&);
     91static void resolveTree(Element&, ContainerNode& renderingParentNode, RenderTreePosition&, Change);
    6992
    7093Change determineChange(const RenderStyle* s1, const RenderStyle* s2)
    … …  
    152175}
    153176
     177RenderTreePosition::RenderTreePosition(RenderElement* parent)
     178    : m_parent(parent)
     179    , m_nextSibling(nullptr)
     180    , m_hasValidNextSibling(false)
     181#if !ASSERT_DISABLED
     182    , m_assertionLimitCounter(0)
     183#endif
     184{
     185}
     186
     187RenderTreePosition::RenderTreePosition(RenderElement* parent, RenderObject* nextSibling)
     188    : m_parent(parent)
     189    , m_nextSibling(nextSibling)
     190    , m_hasValidNextSibling(true)
     191#if !ASSERT_DISABLED
     192    , m_assertionLimitCounter(0)
     193#endif
     194{
     195}
     196
     197bool RenderTreePosition::canInsert(RenderElement& renderer) const
     198{
     199    ASSERT(m_parent);
     200    ASSERT(!renderer.parent());
     201    return m_parent->isChildAllowed(renderer, renderer.style());
     202}
     203
     204bool RenderTreePosition::canInsert(RenderText& renderer) const
     205{
     206    ASSERT(m_parent);
     207    ASSERT(!renderer.parent());
     208    return m_parent->isChildAllowed(renderer, m_parent->style());
     209}
     210
     211void RenderTreePosition::insert(RenderObject& renderer)
     212{
     213    ASSERT(m_parent);
     214    ASSERT(m_hasValidNextSibling);
     215    m_parent->addChild(&renderer, m_nextSibling);
     216}
     217
     218void RenderTreePosition::computeNextSibling(const Node& node, ContainerNode& renderingParentNode)
     219{
     220    ASSERT(!node.renderer());
     221    if (m_hasValidNextSibling) {
     222        // Stop validating at some point so the assert doesn't make us O(N^2) on debug builds.
     223        ASSERT(++m_assertionLimitCounter > 20 || nextSiblingRenderer(node, renderingParentNode) == m_nextSibling);
     224        return;
     225    }
     226    m_nextSibling = nextSiblingRenderer(node, renderingParentNode);
     227    m_hasValidNextSibling = true;
     228}
     229
     230void RenderTreePosition::invalidateNextSibling(const RenderObject& siblingRenderer)
     231{
     232    if (!m_hasValidNextSibling)
     233        return;
     234    if (m_nextSibling == &siblingRenderer)
     235        m_hasValidNextSibling = false;
     236}
     237
    154238static bool shouldCreateRenderer(const Element& element, const ContainerNode& renderingParent)
    155239{
    … …  
    166250}
    167251
    168 static PassRef<RenderStyle> styleForElement(Element& element, RenderStyle& parentStyle)
    169 {
    170     if (element.hasCustomStyleResolveCallbacks()) {
    171         if (RefPtr<RenderStyle> style = element.customStyleForRenderer(parentStyle))
     252static PassRef<RenderStyle> styleForElement(Element& element, ContainerNode& renderingParentNode)
     253{
     254    RenderStyle* parentStyle = renderingParentNode.renderStyle();
     255    if (element.hasCustomStyleResolveCallbacks() && parentStyle) {
     256        if (RefPtr<RenderStyle> style = element.customStyleForRenderer(*parentStyle))
    172257            return style.releaseNonNull();
    173258    }
    174     return element.document().ensureStyleResolver().styleForElement(&element, &parentStyle);
     259    return element.document().ensureStyleResolver().styleForElement(&element, parentStyle);
    175260}
    176261
    177262// Check the specific case of elements that are children of regions but are flowed into a flow thread themselves.
    178 static bool elementInsideRegionNeedsRenderer(Element& element, const ContainerNode& renderingParentNode, RefPtr<RenderStyle>& style)
     263static bool elementInsideRegionNeedsRenderer(Element& element, ContainerNode& renderingParentNode, RefPtr<RenderStyle>& style)
    179264{
    180265#if ENABLE(CSS_REGIONS)
    … …  
    188273
    189274    if (!style)
    190         style = styleForElement(element, *renderingParentNode.renderStyle());
     275        style = styleForElement(element, renderingParentNode);
    191276
    192277    // Children of this element will only be allowed to be flowed into other flow-threads if display is NOT none.
    … …  
    216301#endif
    217302
    218 static void createRendererIfNeeded(Element& element, ContainerNode& renderingParentNode, PassRefPtr<RenderStyle> resolvedStyle)
     303static void createRendererIfNeeded(Element& element, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition, PassRefPtr<RenderStyle> resolvedStyle)
    219304{
    220305    ASSERT(!element.renderer());
    … …  
    228313
    229314    if (!style)
    230         style = styleForElement(element, *renderingParentNode.renderStyle());
     315        style = styleForElement(element, renderingParentNode);
    231316
    232317    RenderNamedFlowThread* parentFlowRenderer = 0;
    … …  
    238323        return;
    239324
    240     RenderElement* parentRenderer;
    241     RenderObject* nextRenderer;
    242     if (parentFlowRenderer) {
    243         parentRenderer = parentFlowRenderer;
    244         nextRenderer = parentFlowRenderer->nextRendererForElement(element);
    245     } else {
    246         // FIXME: Make this path Element only, handle the root special case separately.
    247         parentRenderer = renderingParentNode.renderer();
    248         nextRenderer = nextSiblingRenderer(element, renderingParentNode);
    249     }
     325    renderTreePosition.computeNextSibling(element, renderingParentNode);
     326
     327    RenderTreePosition insertionPosition = parentFlowRenderer
     328        ? RenderTreePosition(parentFlowRenderer, parentFlowRenderer->nextRendererForElement(element))
     329        : renderTreePosition;
    250330
    251331    RenderElement* newRenderer = element.createElementRenderer(style.releaseNonNull()).leakPtr();
    252332    if (!newRenderer)
    253333        return;
    254     if (!parentRenderer->isChildAllowed(*newRenderer, newRenderer->style())) {
     334    if (!insertionPosition.canInsert(*newRenderer)) {
    255335        newRenderer->destroy();
    256336        return;
    … …  
    259339    // Make sure the RenderObject already knows it is going to be added to a RenderFlowThread before we set the style
    260340    // for the first time. Otherwise code using inRenderFlowThread() in the styleWillChange and styleDidChange will fail.
    261     newRenderer->setFlowThreadState(parentRenderer->flowThreadState());
     341    newRenderer->setFlowThreadState(insertionPosition.parent()->flowThreadState());
    262342
    263343    // Code below updateAnimations() can depend on Element::renderer() already being set.
    … …  
    273353    Document& document = element.document();
    274354    if (document.webkitIsFullScreen() && document.webkitCurrentFullScreenElement() == &element) {
    275         newRenderer = RenderFullScreen::wrapRenderer(newRenderer, parentRenderer, document);
     355        newRenderer = RenderFullScreen::wrapRenderer(newRenderer, insertionPosition.parent(), document);
    276356        if (!newRenderer)
    277357            return;
    … …  
    279359#endif
    280360    // Note: Adding newRenderer instead of renderer(). renderer() may be a child of newRenderer.
    281     parentRenderer->addChild(newRenderer, nextRenderer);
     361    insertionPosition.insert(*newRenderer);
    282362}
    283363
    … …  
    368448}
    369449
    370 static void createTextRendererIfNeeded(Text& textNode, ContainerNode& renderingParentNode)
     450static void createTextRendererIfNeeded(Text& textNode, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition)
    371451{
    372452    ASSERT(!textNode.renderer());
    … …  
    374454    if (!textRendererIsNeeded(textNode, renderingParentNode))
    375455        return;
    376     RenderElement& parentRenderer = *renderingParentNode.renderer();
    377     const auto& style = parentRenderer.style();
    378 
    379     auto newRenderer = textNode.createTextRenderer(style);
     456
     457    auto newRenderer = textNode.createTextRenderer(*renderingParentNode.renderStyle());
    380458    ASSERT(newRenderer);
    381459
    382     if (!parentRenderer.isChildAllowed(*newRenderer, style))
     460    renderTreePosition.computeNextSibling(textNode, renderingParentNode);
     461
     462    if (!renderTreePosition.canInsert(*newRenderer))
    383463        return;
    384464
    385465    // Make sure the RenderObject already knows it is going to be added to a RenderFlowThread before we set the style
    386466    // for the first time. Otherwise code using inRenderFlowThread() in the styleWillChange and styleDidChange will fail.
    387     newRenderer->setFlowThreadState(parentRenderer.flowThreadState());
    388 
    389     RenderObject* nextRenderer = nextSiblingRenderer(textNode, renderingParentNode);
     467    newRenderer->setFlowThreadState(renderTreePosition.parent()->flowThreadState());
     468
    390469    textNode.setRenderer(newRenderer.get());
    391470    // Parent takes care of the animations, no need to call setAnimatableStyle.
    392     parentRenderer.addChild(newRenderer.leakPtr(), nextRenderer);
    393 }
    394 
    395 void attachTextRenderer(Text& textNode, ContainerNode& renderingParent)
    396 {
    397     createTextRendererIfNeeded(textNode, renderingParent);
     471    renderTreePosition.insert(*newRenderer.leakPtr());
     472}
     473
     474void attachTextRenderer(Text& textNode, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition)
     475{
     476    createTextRendererIfNeeded(textNode, renderingParentNode, renderTreePosition);
    398477
    399478    textNode.clearNeedsStyleRecalc();
    … …  
    414493
    415494    bool hadRenderer = textNode.renderer();
    416     resolveTextNode(textNode, *renderingParentNode);
     495
     496    RenderTreePosition renderTreePosition(renderingParentNode->renderer());
     497    resolveTextNode(textNode, *renderingParentNode, renderTreePosition);
    417498
    418499    if (hadRenderer && textNode.renderer())
    … …  
    420501}
    421502
    422 static void attachChildren(ContainerNode& current, ContainerNode& renderingParentNode)
     503static void attachChildren(ContainerNode& current, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition)
    423504{
    424505    for (Node* child = current.firstChild(); child; child = child->nextSibling()) {
    425506        ASSERT((!child->renderer() || child->inNamedFlow()) || current.shadowRoot());
    426         if (child->renderer())
     507        if (child->renderer()) {
     508            renderTreePosition.invalidateNextSibling(*child->renderer());
    427509            continue;
     510        }
    428511        if (child->isTextNode()) {
    429             attachTextRenderer(*toText(child), renderingParentNode);
     512            attachTextRenderer(*toText(child), renderingParentNode, renderTreePosition);
    430513            continue;
    431514        }
    432515        if (child->isElementNode())
    433             attachRenderTree(*toElement(child), renderingParentNode, nullptr);
    434     }
    435 }
    436 
    437 static void attachDistributedChildren(InsertionPoint& insertionPoint, ContainerNode& renderingParentNode)
     516            attachRenderTree(*toElement(child), renderingParentNode, renderTreePosition, nullptr);
     517    }
     518}
     519
     520static void attachDistributedChildren(InsertionPoint& insertionPoint, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition)
    438521{
    439522    if (ShadowRoot* shadowRoot = insertionPoint.containingShadowRoot())
    … …  
    441524
    442525    for (Node* current = insertionPoint.firstDistributed(); current; current = insertionPoint.nextDistributedTo(current)) {
     526        if (current->renderer())
     527            renderTreePosition.invalidateNextSibling(*current->renderer());
    443528        if (current->isTextNode()) {
    444529            if (current->renderer())
    445530                continue;
    446             attachTextRenderer(*toText(current), renderingParentNode);
     531            attachTextRenderer(*toText(current), renderingParentNode, renderTreePosition);
    447532            continue;
    448533        }
    … …  
    451536            if (currentElement.renderer())
    452537                detachRenderTree(currentElement);
    453             attachRenderTree(currentElement, renderingParentNode, nullptr);
     538            attachRenderTree(currentElement, renderingParentNode, renderTreePosition, nullptr);
    454539        }
    455540    }
    456541    // Use actual children as fallback content.
    457542    if (!insertionPoint.hasDistribution())
    458         attachChildren(insertionPoint, renderingParentNode);
     543        attachChildren(insertionPoint, renderingParentNode, renderTreePosition);
    459544}
    460545
    461546static void attachShadowRoot(ShadowRoot& shadowRoot)
    462547{
    463     attachChildren(shadowRoot, *shadowRoot.hostElement());
     548    ASSERT(shadowRoot.hostElement());
     549
     550    RenderTreePosition renderTreePosition(shadowRoot.hostElement()->renderer());
     551    attachChildren(shadowRoot, *shadowRoot.hostElement(), renderTreePosition);
    464552
    465553    shadowRoot.clearNeedsStyleRecalc();
    … …  
    508596}
    509597
    510 static void attachBeforeOrAfterPseudoElementIfNeeded(Element& current, PseudoId pseudoId)
     598static void attachBeforeOrAfterPseudoElementIfNeeded(Element& current, PseudoId pseudoId, RenderTreePosition& renderTreePosition)
    511599{
    512600    if (!needsPseudoElement(current, pseudoId))
    … …  
    514602    RefPtr<PseudoElement> pseudoElement = PseudoElement::create(current, pseudoId);
    515603    setBeforeOrAfterPseudoElement(current, pseudoElement, pseudoId);
    516     attachRenderTree(*pseudoElement, current, nullptr);
    517 }
    518 
    519 static void attachRenderTree(Element& current, ContainerNode& renderingParentNode, PassRefPtr<RenderStyle> resolvedStyle)
     604    attachRenderTree(*pseudoElement, current, renderTreePosition, nullptr);
     605}
     606
     607static void attachRenderTree(Element& current, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition, PassRefPtr<RenderStyle> resolvedStyle)
    520608{
    521609    PostResolutionCallbackDisabler callbackDisabler(current.document());
    … …  
    525613        current.willAttachRenderers();
    526614
    527     createRendererIfNeeded(current, renderingParentNode, resolvedStyle);
     615    createRendererIfNeeded(current, renderingParentNode, renderTreePosition, resolvedStyle);
    528616
    529617    if (current.parentElement() && current.parentElement()->isInCanvasSubtree())
    530618        current.setIsInCanvasSubtree(true);
    531619
    532     attachBeforeOrAfterPseudoElementIfNeeded(current, BEFORE);
    533 
    534620    StyleResolverParentPusher parentPusher(&current);
     621
     622    RenderTreePosition childRenderTreePosition(current.renderer());
     623    attachBeforeOrAfterPseudoElementIfNeeded(current, BEFORE, childRenderTreePosition);
    535624
    536625    if (ShadowRoot* shadowRoot = current.shadowRoot()) {
    … …  
    541630
    542631    if (isInsertionPoint(current))
    543         attachDistributedChildren(toInsertionPoint(current), renderingParentNode);
     632        attachDistributedChildren(toInsertionPoint(current), renderingParentNode, renderTreePosition);
    544633    else
    545         attachChildren(current, current);
     634        attachChildren(current, current, childRenderTreePosition);
    546635
    547636    current.clearNeedsStyleRecalc();
    … …  
    551640        cache->updateCacheAfterNodeIsAttached(&current);
    552641
    553     attachBeforeOrAfterPseudoElementIfNeeded(current, AFTER);
     642    attachBeforeOrAfterPseudoElementIfNeeded(current, AFTER, childRenderTreePosition);
    554643
    555644    current.updateFocusAppearanceAfterAttachIfNeeded();
    … …  
    653742}
    654743
    655 static Change resolveLocal(Element& current, ContainerNode& renderingParentNode, Change inheritedChange)
     744static Change resolveLocal(Element& current, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition, Change inheritedChange)
    656745{
    657746    Change localChange = Detach;
    … …  
    661750    Document& document = current.document();
    662751    if (currentStyle && current.styleChangeType() != ReconstructRenderTree) {
    663         newStyle = styleForElement(current, *renderingParentNode.renderStyle());
     752        newStyle = styleForElement(current, renderingParentNode);
    664753        localChange = determineChange(currentStyle.get(), newStyle.get());
    665754    }
    … …  
    667756        if (current.renderer() || current.inNamedFlow())
    668757            detachRenderTree(current, ReattachDetach);
    669         attachRenderTree(current, renderingParentNode, newStyle.release());
     758        attachRenderTree(current, renderingParentNode, renderTreePosition, newStyle.release());
    670759        invalidateWhitespaceOnlyTextSiblingsAfterAttachIfNeeded(current);
    671760
    … …  
    699788}
    700789
    701 void resolveTextNode(Text& text, ContainerNode& renderingParentNode)
     790void resolveTextNode(Text& text, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition)
    702791{
    703792    text.clearNeedsStyleRecalc();
    … …  
    714803    if (!needsRenderer)
    715804        return;
    716     attachTextRenderer(text, renderingParentNode);
     805    attachTextRenderer(text, renderingParentNode, renderTreePosition);
    717806    invalidateWhitespaceOnlyTextSiblingsAfterAttachIfNeeded(text);
    718807}
    719808
    720 static void resolveShadowTree(ShadowRoot& shadowRoot, Style::Change change)
    721 {
     809static void resolveShadowTree(ShadowRoot& shadowRoot, Element& host, Style::Change change)
     810{
     811    ASSERT(shadowRoot.hostElement() == &host);
     812    RenderTreePosition renderTreePosition(host.renderer());
    722813    for (Node* child = shadowRoot.firstChild(); child; child = child->nextSibling()) {
     814        if (child->renderer())
     815            renderTreePosition.invalidateNextSibling(*child->renderer());
    723816        if (child->isTextNode() && child->needsStyleRecalc()) {
    724             resolveTextNode(*toText(child), *shadowRoot.hostElement());
     817            resolveTextNode(*toText(child), host, renderTreePosition);
    725818            continue;
    726819        }
    727820        if (child->isElementNode())
    728             resolveTree(*toElement(child), *shadowRoot.hostElement(), change);
     821            resolveTree(*toElement(child), host, renderTreePosition, change);
    729822    }
    730823
    … …  
    733826}
    734827
    735 static void updateBeforeOrAfterPseudoElement(Element& current, Change change, PseudoId pseudoId)
     828static void updateBeforeOrAfterPseudoElement(Element& current, Change change, PseudoId pseudoId, RenderTreePosition& renderTreePosition)
    736829{
    737830    if (PseudoElement* existingPseudoElement = beforeOrAfterPseudoElement(current, pseudoId)) {
    738831        if (needsPseudoElement(current, pseudoId))
    739             resolveTree(*existingPseudoElement, current, current.needsStyleRecalc() ? Force : change);
     832            resolveTree(*existingPseudoElement, current, renderTreePosition, current.needsStyleRecalc() ? Force : change);
    740833        else
    741834            clearBeforeOrAfterPseudoElement(current, pseudoId);
    742835        return;
    743836    }
    744     attachBeforeOrAfterPseudoElementIfNeeded(current, pseudoId);
     837    attachBeforeOrAfterPseudoElementIfNeeded(current, pseudoId, renderTreePosition);
    745838}
    746839
    … …  
    797890#endif // PLATFORM(IOS)
    798891
    799 void resolveTree(Element& current, ContainerNode& renderingParentNode, Change change)
     892void resolveTree(Element& current, ContainerNode& renderingParentNode, RenderTreePosition& renderTreePosition, Change change)
    800893{
    801894    ASSERT(change != Detach);
    … …  
    818911
    819912    if (hasParentStyle && (change >= Inherit || current.needsStyleRecalc()))
    820         change = resolveLocal(current, renderingParentNode, change);
     913        change = resolveLocal(current, renderingParentNode, renderTreePosition, change);
    821914
    822915    if (change != Detach) {
    … …  
    826919            if (change >= Inherit || shadowRoot->childNeedsStyleRecalc() || shadowRoot->needsStyleRecalc()) {
    827920                parentPusher.push();
    828                 resolveShadowTree(*shadowRoot, change);
     921                resolveShadowTree(*shadowRoot, current, change);
    829922            }
    830923        }
    831924
    832         updateBeforeOrAfterPseudoElement(current, change, BEFORE);
     925        RenderTreePosition childRenderTreePosition(current.renderer());
     926        updateBeforeOrAfterPseudoElement(current, change, BEFORE, childRenderTreePosition);
    833927
    834928        // FIXME: This check is good enough for :hover + foo, but it is not good enough for :hover + foo + bar.
    … …  
    838932        bool forceCheckOfAnyElementSibling = false;
    839933        for (Node* child = current.firstChild(); child; child = child->nextSibling()) {
     934            if (child->renderer())
     935                childRenderTreePosition.invalidateNextSibling(*child->renderer());
    840936            if (child->isTextNode() && child->needsStyleRecalc()) {
    841                 resolveTextNode(*toText(child), current);
     937                resolveTextNode(*toText(child), current, childRenderTreePosition);
    842938                continue;
    843939            }
    … …  
    850946            if (change >= Inherit || childElement->childNeedsStyleRecalc() || childElement->needsStyleRecalc()) {
    851947                parentPusher.push();
    852                 resolveTree(*childElement, current, change);
     948                resolveTree(*childElement, current, childRenderTreePosition, change);
    853949            }
    854950            forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
    … …  
    856952        }
    857953
    858         updateBeforeOrAfterPseudoElement(current, change, AFTER);
     954        updateBeforeOrAfterPseudoElement(current, change, AFTER, childRenderTreePosition);
    859955    }
    860956
    … …  
    891987    if (change < Inherit && !documentElement->childNeedsStyleRecalc() && !documentElement->needsStyleRecalc())
    892988        return;
    893     resolveTree(*documentElement, document, change);
     989    RenderTreePosition renderTreePosition(document.renderView());
     990    resolveTree(*documentElement, document, renderTreePosition, change);
    894991}
    895992
Note: See TracChangeset for help on using the changeset viewer.