Chromium Code Reviews
Help | Chromium Project | Gerrit Changes | Sign in
(9)

Issue 27217007: Merge 158839 "Reverse style resolution to avoid N^2 walk when bu..." (Closed)

Can't Edit
Can't Publish+Mail
Start Review
Created:
4 years ago by leviw_travelin_and_unemployed
Modified:
3 years, 11 months ago
Reviewers:
laforge, esprehn, eseidel, ojan
CC:
blink-reviews, caseq+blink_chromium.org, loislo+blink_chromium.org, chromiumbugtracker_adobe.com, darktears, eustas+blink_chromium.org, webcomponents-bugzilla_chromium.org, alph+blink_chromium.org, eae+blinkwatch, yurys+blink_chromium.org, lushnikov+blink_chromium.org, leviw+renderwatch, vsevik+blink_chromium.org, pfeldman+blink_chromium.org, dglazkov+blink, paulirish+reviews_chromium.org, apavlov+blink_chromium.org, adamk+blink_chromium.org, jchaffraix+rendering, devtools-reviews_chromium.org, aandrey+blink_chromium.org
Visibility:
Public.

Description

Merge 158839 "Reverse style resolution to avoid N^2 walk when bu..." This change has been on trunk for 11 days, shipped in 10 canaries and presumably at least 2 dev-channel releases. We've had no regressions/crashes reported from this CL and I believe it's the safest way to solve this issue on the M31 branch. The merge was clean with the exception of header includes and core.gypi. I believe this to be our safest/best option for M31. BUG=288225 > Reverse style resolution to avoid N^2 walk when building the render tree > > Blink resolves style by walking each element from first child to last, but > when we go to insert their renderer, we look for the next renderer to insert > before. On the initial style resolve, this means we'll walk the entire DOM > tree trying to find the right renderer to insert before leading to an N^2 > loop over the DOM on load. > > This could be fixed by changing the semantics by which we insert renderers > (insert after instead of insert before). Instead, here I reverse the order > we resolve style. This should ensure that in the common case, we'll find > the renderer to insert before immediately. > > Testing this change uncovered a bug in checkForSiblingStyleChanges whereby > we'd invalidate the wrong sibling in certain cases for changed children > of elements with directly adjacent sibling selectors. I fixed this > and added a simplified test (acid3 caught it with this change, but it's > a nightmare to debug). > > We still attempt to process whitespace text nodes in DOM order by keeping a > stack-allocated vector of whitespace children we postpone recalcing style on > until the end. If we go past that limit, we process them and continue going. > Also removing the didReattach check to force whitespace reattachment. This > causes some whitespace layout tests results to change, but doesn't appear > to break anything. > > BUG=288225, 245478 > R=esprehn@chromium.org, ojan@chromium.org > > Review URL: https://codereview.chromium.org/24350009

Patch Set 1 #

Unified diffs Side-by-side diffs Delta from patch set Stats (+277 lines, -252 lines) Patch
M LayoutTests/TestExpectations View 1 chunk +33 lines, -0 lines 0 comments Download
M LayoutTests/editing/execCommand/outdent-break-with-style-expected.txt View 1 chunk +4 lines, -0 lines 0 comments Download
M LayoutTests/editing/selection/focus-crash-expected.txt View 1 chunk +1 line, -1 line 0 comments Download
M LayoutTests/editing/style/remove-underline-after-paragraph-expected.txt View 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/editing/style/remove-underline-after-paragraph-in-bold-expected.txt View 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/editing/style/typing-style-003-expected.txt View 1 chunk +18 lines, -18 lines 0 comments Download
M LayoutTests/editing/style/underline-expected.txt View 1 chunk +19 lines, -19 lines 0 comments Download
M LayoutTests/fast/css/getComputedStyle/getComputedStyle-resolved-values-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
A + LayoutTests/fast/css/next-sibling-changed.html View 0 chunks +-1 lines, --1 lines 0 comments Download
A + LayoutTests/fast/css/next-sibling-changed-expected.txt View 0 chunks +-1 lines, --1 lines 0 comments Download
M LayoutTests/inspector/elements/edit-dom-actions-expected.txt View 1 chunk +1 line, -1 line 0 comments Download
M LayoutTests/platform/win/editing/deleting/delete-block-merge-contents-001-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/deleting/delete-block-merge-contents-019-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/deleting/delete-block-merge-contents-020-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/inserting/editable-html-element-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/inserting/editing-empty-divs-expected.txt View 2 chunks +0 lines, -2 lines 0 comments Download
M LayoutTests/platform/win/editing/pasteboard/copy-standalone-image-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/pasteboard/paste-match-style-001-expected.txt View 1 chunk +0 lines, -2 lines 0 comments Download
M LayoutTests/platform/win/editing/selection/4983858-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/selection/drag-to-contenteditable-iframe-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-across-paragraph-expected.txt View 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-across-paragraph-in-bold-expected.txt View 1 chunk +28 lines, -28 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-expected.txt View 1 chunk +20 lines, -20 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-from-stylesheet-expected.txt View 1 chunk +2 lines, -0 lines 0 comments Download
M LayoutTests/platform/win/editing/style/remove-underline-in-bold-expected.txt View 1 chunk +20 lines, -20 lines 0 comments Download
M LayoutTests/platform/win/editing/style/style-boundary-005-expected.txt View 1 chunk +0 lines, -2 lines 0 comments Download
M LayoutTests/platform/win/fast/body-propagation/background-color/004-xhtml-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/fast/body-propagation/background-image/004-xhtml-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M LayoutTests/platform/win/fast/dynamic/move-node-with-selection-expected.txt View 1 chunk +0 lines, -3 lines 0 comments Download
M LayoutTests/platform/win/fast/inline/positionedLifetime-expected.txt View 1 chunk +0 lines, -1 line 0 comments Download
M Source/core/core.gypi View 1 chunk +1 line, -0 lines 0 comments Download
M Source/core/css/SiblingTraversalStrategies.h View 2 chunks +8 lines, -8 lines 0 comments Download
M Source/core/dom/Element.cpp View 3 chunks +29 lines, -21 lines 0 comments Download
A + Source/core/dom/WhitespaceChildList.h View 0 chunks +-1 lines, --1 lines 0 comments Download
M Source/core/dom/shadow/ShadowRoot.cpp View 2 chunks +10 lines, -13 lines 0 comments Download
M Source/core/rendering/RenderRegion.cpp View 2 chunks +2 lines, -2 lines 0 comments Download
Trybot results:
Commit queue not available (can’t edit this change).

Messages

Total messages: 5 (0 generated)
leviw_travelin_and_unemployed
4 years ago (2013-10-15 17:56:25 UTC) #1
eseidel
Why is the whitespaceChildList.h file empty in rietfail? Otherwise lgtm.
4 years ago (2013-10-15 18:08:37 UTC) #2
leviw_travelin_and_unemployed
That's weird. It's added by this patch... it should just be entirely green.
4 years ago (2013-10-15 18:15:23 UTC) #3
eseidel
Ready to land this with your approval Anthony.
4 years ago (2013-10-15 19:25:15 UTC) #4
laforge
4 years ago (2013-10-15 19:57:03 UTC) #5
On 2013/10/15 19:25:15, eseidel wrote:
> Ready to land this with your approval Anthony.

LGTM, w/ a cringe.
Sign in to reply to this message.

Powered by Google App Engine
RSS Feeds Recent Issues | This issue
This is Rietveld 81bcdb8aa