Continuations are too slow, since pathological nesting results in O(n^2) RenderObjects being made (and then our O(n^2) algorithms run on it to create a really horrible performance bottleneck).
They should be phased out in favor of a new approach that uses anonymous inline blocks to enable blocks to live inside inlines.
Created attachment 14120[details]
Work in progress
Here is a first cut that demonstrates the gigantic performance gains. On the tag nesting PLT, this patch cuts the time from 34 seconds down to 6 seconds.
Open issues abound though:
(1) Margin collapsing has to run on contiguous inline blocks. This could complicate line layout a fair bit, as it would have to become even more of a hybrid.
(2) Floats need a lot more testing. There is some concern that certain cases could get slower in DHTML scenarios if floats are present.
(3) Selection is kind of horked.
(4) Many editing tests fail. Editing's typical fragility makes it unprepared for the use of inline blocks.
Little test to remind myself of some other issues:
<!doctype html>
<div style="float:left; width:100px;height:100px;background-color:lime"></div>
<span style="border:5px solid red">Hello
<div style="border:1px solid black">world</div>
wow</span>
Paint stacking order is wrong. The inline block has to pretend to be a block as far as stacking order and painting goes. This means the float background should paint above the black border of the div block that is inside the inline.
Whitespace needs to be consumed at the end of the line preceding the anonymous inline block.
Created attachment 38435[details]
This patch fixes a bunch of bugs in margin collapsing and pref width calculations.
With this patch 001.html in fast/margin-collapsing passes (which is great given how complex the test is). I'll be working to ensure that all 65 margin collapsing tests pass when every block is wrapped in a span.
Created attachment 38442[details]
001.html-033.html pass
This patch fixes the paint stacking issue, the trailing whitespace issue, and a number of float issues. It gets basic float positioning working.
More notes:
(1) Have to make determineStartPosition work. This means rerunning as much of margin collapsing as is needed to get the right state for the next child and to have the right state at the top of the block.
(2) Not necessarily something that has to be fixed for landing, but need to teach line layout how to do multiple start/end positions since missing out on clean lines is lame. If line 2 changes and line 10000 changes, throwing away all the clean lines in between is dumb.
(3) Have to make sure repainting is pretty smart, although this is also not super critical, since continuations don't do well when they split. We should at least make the common case of appending into the same anonymous inline block work correctly.
(4) Selection painting is not good.
(5) Probably huge layout test failures still in other areas. :)
Created attachment 38448[details]
Clean up some layout test failures. No progress on margin-collapsing test suite, but fixed some errors and crashes in other layout tests.
Current issues:
(1) Have to make determineStartPosition work. This means rerunning as much of
margin collapsing as is needed to get the right state for the next child and to
have the right state at the top of the block.
(2) Not necessarily something that has to be fixed for landing, but need to
teach line layout how to do multiple start/end positions since missing out on
clean lines is lame. If line 2 changes and line 10000 changes, throwing away
all the clean lines in between is dumb.
(3) Have to make sure repainting is pretty smart, although this is also not
super critical, since continuations don't do well when they split. We should
at least make the common case of appending into the same anonymous inline block
work correctly.
(4) Hit testing doesn't work yet in the margins of anonymous inline blocks. Need to special case this in the line hit testing code.
(5) Floats will need lots of testing.
Created attachment 48514[details]
Patch that makes blocks work inside inlines with layers
And now for something totally awesome:
<span style="position:relative;left:100px; opacity:0.7"><i>Hello <div style="border:5px solid blue">world</div> goodbye</span>
This patch makes the above finally work in WebKit for the first time. Blocks will now work when nested inside enclosing inlines with layers.
Even better, the inlines that enclose an anonymous inline block are only created if they have a layer or an outline. Otherwise they don't get made. This optimization will be applicable even to the normal line box tree eventually (e.g., don't make line boxes that don't paint anything or provide any useful info).
Current notes:
(1) Have to make determineStartPosition work. This means rerunning as much of
margin collapsing as is needed to get the right state for the next child and to
have the right state at the top of the block.
(2) Not necessarily something that has to be fixed for landing, but need to
teach line layout how to do multiple start/end positions since missing out on
clean lines is lame. If line 2 changes and line 10000 changes, throwing away
all the clean lines in between is dumb.
(3) Have to make sure repainting is pretty smart, although this is also not
super critical, since continuations don't do well when they split. We should
at least make the common case of appending into the same anonymous inline block
work correctly.
(4) Outline painting is messed up in the non-auto case.
(5) Empty inlines with borders/padding are no longer showing up. Maybe they are being subsumed by the anonymous inline block line?
(6) Because of the culling of line boxes (in order to avoid O(n^2) behavior), methods on RenderInline like absoluteRects and linesBoundingBox don't know about the inline block lines. Options are to disable the culling or to taint the RenderInline so that it has to grovel into descendants looking for the anonymous inline blocks.
(7) When line boxes don't get culled, they still need to have the dimensions of the anonymous inline block. However right now because of height() on InlineFlowBox just returning the font's height, it isn't possible to customize the height of these boxes. I will probably need to make a special subclass of InlineFlowBox with a height member to deal with this.
Created attachment 48766[details]
Fix the determineStartPosition problem
This patch fixes the determineStartPosition issue and makes sure margin collapsing re-runs like it's supposed to.
The performance issues continue to be pretty complex though.
(1) If only an anonymous inline block is dirty, you end up repainting the whole block plus everything that follows it.
(2) If only an anonymous inline block is dirty, you end up extracting all the lines that follow and then re-attaching them. This makes layout way more expensive if say images are loading in earlier blocks.
The "cars" pages on the nesting PLT is way way slower, mainly because 50% of the time is spent in attach/extractLine. So this means determineStartPosition/EndPosition are working, but the problem is content is coming in to early anonymous blocks, causing the extraction/attachment to run over and over on all the later lines for each layout operation.
(In reply to comment #17)
> Created an attachment (id=48514) [details]
> Patch that makes blocks work inside inlines with layers
>
> And now for something totally awesome:
>
> <span style="position:relative;left:100px; opacity:0.7"><i>Hello <div style="border:5px solid blue">world</div> goodbye</span>
>
> This patch makes the above finally work in WebKit for the first time. Blocks will now work when nested inside enclosing inlines with layers.
>
> Even better, the inlines that enclose an anonymous inline block are only created if they have a layer or an outline. Otherwise they don't get made. This optimization will be applicable even to the normal line box tree eventually (e.g., don't make line boxes that don't paint anything or provide any useful info).
This test renders identically in Firefox and Webkit now, did a fix get landed separately? Are they both wrong?
(In reply to comment #27)
> (In reply to comment #17)
> > Created an attachment (id=48514) [details] [details]
> > Patch that makes blocks work inside inlines with layers
> >
> > And now for something totally awesome:
> >
> > <span style="position:relative;left:100px; opacity:0.7"><i>Hello <div style="border:5px solid blue">world</div> goodbye</span>
> >
> > This patch makes the above finally work in WebKit for the first time. Blocks will now work when nested inside enclosing inlines with layers.
> >
> > Even better, the inlines that enclose an anonymous inline block are only created if they have a layer or an outline. Otherwise they don't get made. This optimization will be applicable even to the normal line box tree eventually (e.g., don't make line boxes that don't paint anything or provide any useful info).
>
> This test renders identically in Firefox and Webkit now, did a fix get landed separately? Are they both wrong?
There's a hack that made the positioning part work for continuations, so this is less about correctness now and more about better performance and code simplicity.
Created attachment 248528[details]
More work to bring patch to ToT (about 75% merged)
Does not compile.
One big new issue that will have to be dealt with is pagination. We're going to have to make sure that the anonymous inline-block line is not treated as unsplittable, and that pagination really will drill down into it and never move the line.
Recording thoughts:
We should add a special mode to line layout that can lay out anonymous inline blocks and not make them contribute to the repaint rect or to line dirtying.
What we'd like to do is, as long as we hit anonymous inline blocks first when looking for dirty lines, try to lay it out and see if it moves.
If the anonymous inline block does not move or change size and does not have any overhanging floats, then we simply undirty the line and keep going.
If the anonymous inline block does move or change size but does not have overhanging floats, then we can move the lines that follow without extraction.
Another big thing to think about is pagination. Pagination came online after the 2010 patch. We have to make sure to drill into anonymous inline blocks and paginate them, and our line is irrelevant for pagination and should just be allowed to sit where it wants.
Pagination struts may need to be handled for contiguous inline blocks.
The dirty line optimizations mentioned above may need to turn off when pagination is involved.
Attachment 248528[details] did not pass style-queue:
ERROR: Source/WebCore/rendering/InlineFlowBox.cpp:1136: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/accessibility/AccessibilityRenderObject.cpp:339: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineElementBox.cpp:70: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineElementBox.cpp:76: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineElementBox.cpp:121: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderInline.h:171: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlock.cpp:2654: Tests for true/false, null/non-null, and zero/non-zero should all be done without equality comparisons. [readability/comparison_to_zero] [5]
ERROR: Source/WebCore/rendering/RenderBlock.cpp:3190: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlock.cpp:3428: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineBox.h:38: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:40: Missing spaces around : [whitespace/init] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:40: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:42: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineBox.h:47: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:49: Missing spaces around : [whitespace/init] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:49: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/InlineBox.h:54: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1023: Should have only a single space after a punctuation in a comment. [whitespace/comments] [5]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1078: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1566: Should have only a single space after a punctuation in a comment. [whitespace/comments] [5]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:1575: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2080: Should have only a single space after a punctuation in a comment. [whitespace/comments] [5]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2095: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2099: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2103: More than one command on the same line in for [whitespace/parens] [4]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2104: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2107: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockLineLayout.cpp:2112: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineBox.cpp:29: Alphabetical sorting problem. [build/include_order] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:2747: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3103: Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side. [whitespace/operators] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3103: Multi line control clauses should use braces. [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3372: Boolean expressions that span multiple lines should have their operators on the left side of the line instead of the right side. [whitespace/operators] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3372: Multi line control clauses should use braces. [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/RenderBlockFlow.cpp:3377: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/InlineFlowBox.h:357: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/InlineFlowBox.h:360: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/RenderBlock.h:474: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
ERROR: Source/WebCore/rendering/RootInlineBox.h:240: This { should be at the end of the previous line [whitespace/braces] [4]
ERROR: Source/WebCore/rendering/RootInlineBox.h:243: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/RootInlineBox.h:244: Wrong number of spaces before statement. (expected: 8) [whitespace/indent] [4]
ERROR: Source/WebCore/rendering/RootInlineBox.h:257: Weird number of spaces at line-start. Are you using a 4-space indent? [whitespace/indent] [3]
Total errors found: 42 in 29 files
If any of these errors are false positives, please file a bug against check-webkit-style.
https://bugs.webkit.org/show_bug.cgi?id=143238 merged the preferred width calculation and the concept of a bit on RootInlineBoxes to know about anonymous inline blocks. Line construction was fixed up to set the bit and avoid intermediate boxes. Line layout was patched to make sure breaks occurred before and after the anonymous inline-block.
https://bugs.webkit.org/show_bug.cgi?id=143307 has merged in the behavior of floats intruding into the inline-block, as well as making sure lines have the correct height excluding margins.
https://bugs.webkit.org/show_bug.cgi?id=143320 merged in the code to get painting and hit testing stacking correct. Note that there is some subtle stuff with collapsed margins in RenderLineBoxList that has not yet been merged. That will come once I merge margin collapsing.
So one new problem is the handling of empty inlines with border and padding. The current continuation code handles this pretty naturally because you have two RenderInlines (one before and one after the split).
The new code can handle the inline before the split, but there is no second inline after the split, so getting a line box built there is problematic.
2007-04-21 03:19 PDT, Dave Hyatt
2009-08-19 19:18 PDT, Dave Hyatt
2009-08-22 12:33 PDT, Dave Hyatt
2009-08-22 14:04 PDT, Dave Hyatt
2009-08-22 19:32 PDT, Dave Hyatt
2009-08-22 21:24 PDT, Dave Hyatt
2009-08-23 01:06 PDT, Dave Hyatt
2010-02-08 12:27 PST, Dave Hyatt
2010-02-08 13:03 PST, Dave Hyatt
2010-02-08 23:48 PST, Dave Hyatt
2010-02-09 11:40 PST, Dave Hyatt
2010-02-09 15:44 PST, Dave Hyatt
2010-02-10 13:10 PST, Dave Hyatt
2010-02-10 14:33 PST, Dave Hyatt
2010-02-11 13:22 PST, Dave Hyatt
2010-02-11 17:00 PST, Dave Hyatt
2010-02-12 09:08 PST, Dave Hyatt
2010-02-15 11:57 PST, Dave Hyatt
2015-03-11 16:43 PDT, Dave Hyatt
2015-03-12 11:32 PDT, Dave Hyatt