REGRESSION (r84166): recalcStyle for display:inline to display:none transition has complexity N^2 where N is the number of child Text nodes

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Ilya Tikhonovsky]

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.

<rdar://problem/9513180>

[Ilya Tikhonovsky]

Created attachment 95872 [details]
[patch] initial version.

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.

[Dave Hyatt]

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.

[Ilya Tikhonovsky]

Created attachment 96084 [details]
[patch] second version. r84166 was reverted. Special case for relative positioned renderer was added.

[Dave Hyatt]

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.

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.

[Darin Adler]

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.

Fixed in r88617. <http://trac.webkit.org/changeset/88617>

[Eric Seidel (no email)]

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).