Bug 61557 - REGRESSION (r84166): recalcStyle for display:inline to display:none transition has complexity N^2 where N is the number of child Text nodes
Summary: REGRESSION (r84166): recalcStyle for display:inline to display:none transitio...
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Layout and Rendering (show other bugs)
Version: 528+ (Nightly build)
Hardware: Unspecified Unspecified
: P1 Normal
Assignee: Ilya Tikhonovsky
URL:
Keywords: InRadar, Regression
Depends on:
Blocks: 60959
  Show dependency treegraph
 
Reported: 2011-05-26 14:05 PDT by Ilya Tikhonovsky
Modified: 2011-06-18 13:41 PDT (History)
4 users (show)

See Also:


Attachments
test. It adds 50 new text nodes and dumps time/(count^2) at each iteration (852 bytes, text/html)
2011-05-26 14:05 PDT, Ilya Tikhonovsky
no flags Details
[patch] initial version. (6.66 KB, patch)
2011-06-03 01:35 PDT, Ilya Tikhonovsky
hyatt: review-
Details | Formatted Diff | Diff
[patch] second version. r84166 was reverted. Special case for relative positioned renderer was added. (5.01 KB, patch)
2011-06-06 06:48 PDT, Ilya Tikhonovsky
no flags Details | Formatted Diff | Diff
Use the containing block unless it is across a layer boundary (2.39 KB, patch)
2011-06-11 10:58 PDT, mitz@webkit.org
darin: review+
Details | Formatted Diff | Diff

Note You need to log in before you can comment on or make changes to this bug.
Description Ilya Tikhonovsky 2011-05-26 14:05:28 PDT
Created attachment 95037 [details]
test. It adds 50 new text nodes and dumps time/(count^2) at each iteration

The regression was introduced at http://trac.webkit.org/changeset/84166

When I change display:inline to display:none then
1) Node::detach() will be called for each child node;
2) repaint will be called for each child node's renderer for invalidating the affected area;
3) RenderText::clippedOverflowRectForRepaint was changed in the patch. As result parent RenderInline renderer object will be returned instead of RenderBlock in the old code
4) RenderInline::culledInlineVisualOverflowBoundingBox of the parent node's renderer will be called for each child node
  but it has a cycle over all the child node's renderers
  RenderInline::culledInlineBoundingBox has the same cycle too.

1>	webkit.dll!WebCore::RenderInline::culledInlineBoundingBox(const WebCore::RenderInline * container=0x0d9ed9bc)  Line 782	C++
2 	webkit.dll!WebCore::RenderInline::culledInlineVisualOverflowBoundingBox()  Line 890 + 0x10 bytes	C++
3 	webkit.dll!WebCore::RenderInline::linesVisualOverflowBoundingBox()  Line 931 + 0xc bytes	C++
4 	webkit.dll!WebCore::RenderInline::clippedOverflowRectForRepaint(WebCore::RenderBoxModelObject * repaintContainer=0x00000000)  Line 967	C++
5 	webkit.dll!WebCore::RenderText::clippedOverflowRectForRepaint(WebCore::RenderBoxModelObject * repaintContainer=0x00000000)  Line 1357 + 0x1a bytes	C++
6 	webkit.dll!WebCore::RenderObject::repaint(bool immediate=false)  Line 1208 + 0x32 bytes	C++
7 	webkit.dll!WebCore::RenderObjectChildList::removeChildNode(WebCore::RenderObject * owner=0x0d9ed9bc, WebCore::RenderObject * oldChild=0x0da64c3c, bool fullRemove=true)  Line 80	C++
8 	webkit.dll!WebCore::RenderObject::removeChild(WebCore::RenderObject * oldChild=0x0da64c3c)  Line 334	C++
9 	webkit.dll!WebCore::RenderObject::remove()  Line 764 + 0x42 bytes	C++
10 	webkit.dll!WebCore::RenderObject::destroy()  Line 2070	C++
11 	webkit.dll!WebCore::RenderText::destroy()  Line 201	C++
12 	webkit.dll!WebCore::Node::detach()  Line 1367 + 0x1d bytes	C++
13 	webkit.dll!WebCore::ContainerNode::detach()  Line 761 + 0x12 bytes	C++
14 	webkit.dll!WebCore::Element::detach()  Line 1026	C++
15 	webkit.dll!WebCore::Element::recalcStyle(WebCore::Node::StyleChange change=NoChange)  Line 1090 + 0x12 bytes	C++


Should I just revert it or add something like 

while (container->isRenderInline() && container->parent())
    container = container->parent();

into RenderText::clippedOverflowRectForRepaint

Another idea with caching the rect looks much more complex.
Comment 1 mitz@webkit.org 2011-05-26 22:01:41 PDT
<rdar://problem/9513180>
Comment 2 Ilya Tikhonovsky 2011-06-03 01:35:59 PDT
Created attachment 95872 [details]
[patch] initial version.
Comment 3 mitz@webkit.org 2011-06-03 07:32:43 PDT
I think a simpler fix would be to revet to using the containing block except in the case r84166 was addressing, by stopping at layer boundaries.
Comment 4 Dave Hyatt 2011-06-03 11:17:51 PDT
Comment on attachment 95872 [details]
[patch] initial version.

Surely this can be fixed without adding a bit to all RenderObjects.  Do we even have a free bit? I don't think we do.
Comment 5 Ilya Tikhonovsky 2011-06-06 06:48:59 PDT
Created attachment 96084 [details]
[patch] second version. r84166 was reverted. Special case for relative positioned renderer was added.
Comment 6 Dave Hyatt 2011-06-08 11:06:52 PDT
Comment on attachment 96084 [details]
[patch] second version. r84166 was reverted. Special case for relative positioned renderer was added.

I'm not sure RenderLayer::repaintRect() is reliable. Isn't that the old cached rect and not necessarily current? I think Dan wanted you to do something more like his patch in the one specific case and then more like the original code otherwise, but I'll let him comment.
Comment 7 mitz@webkit.org 2011-06-11 10:58:22 PDT
Created attachment 96857 [details]
Use the containing block unless it is across a layer boundary

No need to change the test. I confirmed that it still fails with TOT minus r84166, and passes with TOT plus this patch.
Comment 8 Darin Adler 2011-06-11 20:45:21 PDT
Comment on attachment 96857 [details]
Use the containing block unless it is across a layer boundary

View in context: https://bugs.webkit.org/attachment.cgi?id=96857&action=review

> Source/WebCore/rendering/RenderText.cpp:1361
> +    RenderObject* cb = containingBlock();

I would much prefer a word or phrase to the acronym cb here. If “cb” is a good name, then I suggest:

    RenderObject* containingBlock = this->containingBlock();

But if there is a better name for the local variable, then all the better.

> Source/WebCore/rendering/RenderText.cpp:1370
> +    // The containing block may be an ancestor of repaintContainer, but we need to do a repaintContainer-relative repaint.
> +    if (repaintContainer && repaintContainer != cb && !cb->isDescendantOf(repaintContainer))
> +            return repaintContainer->clippedOverflowRectForRepaint(repaintContainer);

Wrong indentation on the body of this if.
Comment 9 mitz@webkit.org 2011-06-12 11:29:03 PDT
Fixed in r88617. <http://trac.webkit.org/changeset/88617>
Comment 10 Eric Seidel 2011-06-18 13:41:25 PDT
Comment on attachment 96084 [details]
[patch] second version. r84166 was reverted. Special case for relative positioned renderer was added.

Cleared review? from attachment 96084 [details] so that this bug does not appear in http://webkit.org/pending-review.  If you would like this patch reviewed, please attach it to a new bug (or re-open this bug before marking it for review again).