Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(439)

Unified Diff: Source/core/dom/Element.cpp

Issue 24350009: Reverse style resolution to avoid N^2 walk when building the render tree (Closed) Base URL: svn://svn.chromium.org/blink/trunk
Patch Set: Merge to ToT Created 7 years, 2 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « Source/core/css/SiblingTraversalStrategies.h ('k') | Source/core/dom/WhitespaceChildList.h » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: Source/core/dom/Element.cpp
diff --git a/Source/core/dom/Element.cpp b/Source/core/dom/Element.cpp
index f333acde4b35546c6eb0af44f625abf8d2e4a454..47f29512ee06dc9abe5a0642b97203e22d4fb9dd 100644
--- a/Source/core/dom/Element.cpp
+++ b/Source/core/dom/Element.cpp
@@ -63,6 +63,7 @@
#include "core/dom/ScriptableDocumentParser.h"
#include "core/dom/SelectorQuery.h"
#include "core/dom/Text.h"
+#include "core/dom/WhitespaceChildList.h"
#include "core/dom/custom/CustomElement.h"
#include "core/dom/custom/CustomElementRegistrationContext.h"
#include "core/dom/shadow/InsertionPoint.h"
@@ -1560,40 +1561,47 @@ void Element::recalcChildStyle(StyleRecalcChange change)
bool hasIndirectAdjacentRules = childrenAffectedByForwardPositionalRules();
bool forceCheckOfNextElementSibling = false;
bool forceCheckOfAnyElementSibling = false;
- bool forceReattachOfAnyWhitespaceSibling = false;
- for (Node* child = firstChild(); child; child = child->nextSibling()) {
- bool didReattach = false;
-
- if (child->renderer())
- forceReattachOfAnyWhitespaceSibling = false;
-
- if (child->isTextNode()) {
- if (forceReattachOfAnyWhitespaceSibling && toText(child)->containsOnlyWhitespace())
- child->reattach();
- else
- didReattach = toText(child)->recalcTextStyle(change);
- } else if (child->isElementNode()) {
+ if (hasDirectAdjacentRules || hasIndirectAdjacentRules) {
+ for (Node* child = firstChild(); child; child = child->nextSibling()) {
+ if (!child->isElementNode())
+ continue;
Element* element = toElement(child);
-
bool childRulesChanged = element->needsStyleRecalc() && element->styleChangeType() >= SubtreeStyleChange;
-
if (forceCheckOfNextElementSibling || forceCheckOfAnyElementSibling)
element->setNeedsStyleRecalc();
-
forceCheckOfNextElementSibling = childRulesChanged && hasDirectAdjacentRules;
forceCheckOfAnyElementSibling = forceCheckOfAnyElementSibling || (childRulesChanged && hasIndirectAdjacentRules);
-
+ }
+ }
+ // This loop is deliberately backwards because we use insertBefore in the rendering tree, and want to avoid
+ // a potentially n^2 loop to find the insertion point while resolving style. Having us start from the last
+ // child and work our way back means in the common case, we'll find the insertion point in O(1) time.
+ // Reversing this loop can lead to non-deterministic results in our code to optimize out empty whitespace
+ // RenderTexts. We try to put off recalcing their style until the end to avoid this issue.
+ // See crbug.com/288225
+ WhitespaceChildList whitespaceChildList(change);
+ for (Node* child = lastChild(); child; child = child->previousSibling()) {
+ if (child->isTextNode()) {
+ Text* textChild = toText(child);
+ // FIXME: This check is expensive and may negate the performance gained by the optimization of
+ // avoiding whitespace renderers.
+ if (textChild->containsOnlyWhitespace())
+ whitespaceChildList.append(textChild);
+ else
+ textChild->recalcTextStyle(change);
+ } else if (child->isElementNode()) {
+ Element* element = toElement(child);
if (shouldRecalcStyle(change, element)) {
parentPusher.push();
- didReattach = element->recalcStyle(change);
+ element->recalcStyle(change);
} else if (document().styleResolver()->supportsStyleSharing(element)) {
document().styleResolver()->addToStyleSharingList(element);
}
}
-
- forceReattachOfAnyWhitespaceSibling = didReattach || forceReattachOfAnyWhitespaceSibling;
}
+ whitespaceChildList.recalcStyle();
+
if (shouldRecalcStyle(change, this)) {
updatePseudoElement(AFTER, change);
updatePseudoElement(BACKDROP, change);
@@ -1763,7 +1771,7 @@ static void checkForSiblingStyleChanges(Element* e, RenderStyle* style, bool fin
// The + selector. We need to invalidate the first element following the insertion point. It is the only possible element
// that could be affected by this DOM change.
if (e->childrenAffectedByDirectAdjacentRules() && afterChange) {
- if (Node* firstElementAfterInsertion = afterChange->nextElementSibling())
+ if (Node* firstElementAfterInsertion = afterChange->isElementNode() ? afterChange : afterChange->nextElementSibling())
firstElementAfterInsertion->setNeedsStyleRecalc();
}
}
« no previous file with comments | « Source/core/css/SiblingTraversalStrategies.h ('k') | Source/core/dom/WhitespaceChildList.h » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698