Bug 88376 – Incorrect rect-based hit-test result when hit-test region includes culled inlines

• Component: WebKit Misc.
• Status: RESOLVED FIXED

[Raymes Khoury]

Currently rect-based hit-testing does not correctly handle culled inline elements. Currently culled-inlines are added to the hit-test result if a non-culled child is added AND the child does not fill the entire hit-test region (see HitTestResult::addNodeToRectBasedTestResult()). However, no check is performed to see if the culled-inline ancestors actually intersect with the hit-test region and addNodeToRectBasedTestResult() may not be the correct place to do this test.

See https://bugs.webkit.org/show_bug.cgi?id=85849 for more information

[Allan Sandfeld Jensen]

I might look into this. Do you have any test-cases that illustrates the problem?

[Raymes Khoury]

See https://bugs.webkit.org/show_bug.cgi?id=85849. The patch I checked
in contains 1 failing test. In this case the following happens:

The span is a culled inline. The img gets added to the hittest result
and then our "hack" code kicks in. Because the img doesn't fully cover
the hittest region, then the culled inlines are also added. So the
span is added to the hittest result. The span does fully cover the
hittest region, so the hittest should stop at this point. However,
because no bounds checking is performed in our "hack" code,
HitTestResult::addNodeToRectBasedTestResult returns true and the
hittest continues.

There are other cases that fail. For example, assume the culled inline
is completely outside of the hit-test region, it would still get added
to the hit-test result.

[Allan Sandfeld Jensen]

(In reply to comment #2)
> See https://bugs.webkit.org/show_bug.cgi?id=85849. The patch I checked
> in contains 1 failing test. In this case the following happens:
> 
> The span is a culled inline. The img gets added to the hittest result
> and then our "hack" code kicks in. Because the img doesn't fully cover
> the hittest region, then the culled inlines are also added. So the
> span is added to the hittest result. The span does fully cover the
> hittest region, so the hittest should stop at this point. However,
> because no bounds checking is performed in our "hack" code,
> HitTestResult::addNodeToRectBasedTestResult returns true and the
> hittest continues.
> 
Thanks, I noticed you talked about a failing case, but I didn't realise you had included it. I will have a look.

> There are other cases that fail. For example, assume the culled inline
> is completely outside of the hit-test region, it would still get added
> to the hit-test result.
How could it fall completely outside? Since we are moving up the tree, shouldn't the objects just get larger. If we were moving down or sideways I could see how some of them might be floating or positioned, but going up, they should be positioned the same as their children (at least within the same inline context). 

I am also confused why we are not checking siblings. Couldn't we end up missing culled nodes where we don't intersect their children, but we do intersect the culled node? It is the potential need to check siblings that I see as the biggest reason to change the logic itself. The other cases should be solvable by just improving your "hack" :)

[Raymes Khoury]

> How could it fall completely outside? Since we are moving up the tree, shouldn't the objects just get larger. If we were moving down or sideways I could see how some of them might be floating or positioned, but going up, they should be positioned the same as their children (at least within the same inline context). 

This is not strictly true AFAIK. See https://bugs.webkit.org/show_bug.cgi?id=85849#c22 for a simple example.

> 
> I am also confused why we are not checking siblings. Couldn't we end up missing culled nodes where we don't intersect their children, but we do intersect the culled node? It is the potential need to check siblings that I see as the biggest reason to change the logic itself. The other cases should be solvable by just improving your "hack" :)

I think that is true, though best to write a test to check. There is some weird stuff that happens with culled inlines so it might not necessarily be true (in particular, doing a point-based hit-test on a culled node seems to work properly). I definitely agree that I don't think the hack can just be improved to fix the problem. There are several subtle cases that I would be worried about.

[Allan Sandfeld Jensen]

I am looking at the test-case and the test you have marked as wrong, seems to pass just fine and return the right output (stopping at span).

[Allan Sandfeld Jensen]

(In reply to comment #5)
> I am looking at the test-case and the test you have marked as wrong, seems to pass just fine and return the right output (stopping at span).

Oh wait, I get it, span shouldn't be included at all. The comment is just confusing.

[Raymes Khoury]

No, something has changed. When I initially checked in the test it was failing:
http://trac.webkit.org/browser/trunk/LayoutTests/fast/dom/nodesFromRect-culled-inlines-expected.txt?rev=119733

It was changed here: https://bugs.webkit.org/attachment.cgi?id=151962&action=prettypatch

I couldn't tell you what has changed though.

[Allan Sandfeld Jensen]

(In reply to comment #7)
> No, something has changed. When I initially checked in the test it was failing:
> http://trac.webkit.org/browser/trunk/LayoutTests/fast/dom/nodesFromRect-culled-inlines-expected.txt?rev=119733
> 
> It was changed here: https://bugs.webkit.org/attachment.cgi?id=151962&action=prettypatch
> 
> I couldn't tell you what has changed though.

Only the doctype was changed I think. When moving the tests, I cleaned them up to all use strict parsing. Odd that it solved this bug.

[Raymes Khoury]

Yes the doctype did have an impact on the test results. I have no idea why though.

[Allan Sandfeld Jensen]

(In reply to comment #8)
> (In reply to comment #7)
> > No, something has changed. When I initially checked in the test it was failing:
> > http://trac.webkit.org/browser/trunk/LayoutTests/fast/dom/nodesFromRect-culled-inlines-expected.txt?rev=119733
> > 
> > It was changed here: https://bugs.webkit.org/attachment.cgi?id=151962&action=prettypatch
> > 
> > I couldn't tell you what has changed though.
> 
> Only the doctype was changed I think. When moving the tests, I cleaned them up to all use strict parsing. Odd that it solved this bug.

Ah, dhyatt included the strict doctype for a reason in his comment. Without it the linebox does not have a descender, a thus span and img has identical dimensions.  So only after my cleanup did the test actually function.

[Raymes Khoury]

Ah ok. Glad you know more about it than me =)

[Allan Sandfeld Jensen]

Created attachment 155301 [details]
nodesFromRect-culled-inlines.html

I have expanded the test-case, everything seems to work exactly like it should. Perhaps these cases are no longer culled?

[Allan Sandfeld Jensen]

(In reply to comment #11)
> Ah ok. Glad you know more about it than me =)

I didn't, but I knew what I had changed, so it had to be that :D

Now I have no idea why it works though.

[Allan Sandfeld Jensen]

So, the reason it works is that inlines that has a different ascent/descent creates a new line-boxes. I have not been able to create test-cases that do not work.

I think my assumption at this point will have to be that as long as line-boxes are correctly created, then this code will work correctly, since it includes all culled inlines up to one that creates line-boxes, and all the cases that could make this code wrong should make new line-boxes.

I guess I will rename the bug to indicate it actually works, and close it by removing the comments to it from the code.

[Allan Sandfeld Jensen]

Created attachment 155480 [details]
nodesFromRect-culled-inlines.html

I finally made a test that fails. The original test no longer fails because if forces its inline containers to not be culled, so I made a new test with only normal inlines, and can force the result of getting too many containers.

So the bug is real, but the original test-case was failing for another reason that was solved accidently during a clean-up.

[Allan Sandfeld Jensen]

Created attachment 155517 [details]
Patch

[WebKit Review Bot]

Comment on attachment 155517 [details]
Patch

Attachment 155517 [details] did not pass chromium-ews (chromium-xvfb):
Output: http://queues.webkit.org/results/13389689

New failing tests:
fast/dom/nodesFromRect/nodesFromRect-inline-image.html

[WebKit Review Bot]

Created attachment 155529 [details]
Archive of layout-test-results from gce-cr-linux-04

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: gce-cr-linux-04  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.39-gcg-201203291735-x86_64-with-Ubuntu-10.04-lucid

[Allan Sandfeld Jensen]

(In reply to comment #17)
> (From update of attachment 155517 [details])
> Attachment 155517 [details] did not pass chromium-ews (chromium-xvfb):
> Output: http://queues.webkit.org/results/13389689
> 
> New failing tests:
> fast/dom/nodesFromRect/nodesFromRect-inline-image.html

Hmm. Does chromium add a non-standard margin or padding to images? I removed all the margin: 0 and padding:0 commands because they shouldn't really have any effect. But either chromium styles some elements here in a non-standard way, or they parse the input it in a non-standard way, and chooses to render the whitespace different too. Most likely seems to be styling, but they could be ignoring the strict-parsing rule as well.

[Allan Sandfeld Jensen]

Created attachment 155550 [details]
Patch

Increase error-margin to account to try to account for potentially very different font metrics.

[Allan Sandfeld Jensen]

Created attachment 157978 [details]
Patch

Rebase patch, cleanup test and add comments to the new code

[Allan Sandfeld Jensen]

Created attachment 163101 [details]
Patch

Rebased on trunk to celebrate one month anniversary

[Allan Sandfeld Jensen]

Created attachment 163103 [details]
Patch

Regenerate the ChangeLog as well, the javascript functions used by the test have already landed as part of another patch.

[Eric Seidel (no email)]

Comment on attachment 163103 [details]
Patch

My difficulty in reviewing this is that I don't really understand what culled inlines are.  Perhaps you could explain what you mean by "culled" in this patch.

[Allan Sandfeld Jensen]

(In reply to comment #24)
> (From update of attachment 163103 [details])
> My difficulty in reviewing this is that I don't really understand what culled inlines are.  Perhaps you could explain what you mean by "culled" in this patch.

I think it would be a bit too complicated to explain in patch, but I could give it a try.

Culled inline elements are inline-boxes that have been removed (culled) from the line layout, because they were unimportant to layout and take up memory and hurt performance. Imagine something like <span><span>Text</span></span>. The two spans would have the exact same size and dimensions as the inner text-node and could be culled without changing anything about the layout, leaving just one inline-box instead of three. The elements are still in the render-tree, but do not take part in line-layout.

Note that culled inlines are not a problem to point-based hit-testing because they can not be hit (they are fully covered by their children), but in area-based hit-testing we want all elements in the area, and therefore need to find the culled inlines again.

[Eric Seidel (no email)]

(In reply to comment #25)
> (In reply to comment #24)
> > (From update of attachment 163103 [details] [details])
> > My difficulty in reviewing this is that I don't really understand what culled inlines are.  Perhaps you could explain what you mean by "culled" in this patch.
> 
> I think it would be a bit too complicated to explain in patch, but I could give it a try.
> 
> Culled inline elements are inline-boxes that have been removed (culled) from the line layout, because they were unimportant to layout and take up memory and hurt performance. Imagine something like <span><span>Text</span></span>. The two spans would have the exact same size and dimensions as the inner text-node and could be culled without changing anything about the layout, leaving just one inline-box instead of three. The elements are still in the render-tree, but do not take part in line-layout.
> 
> Note that culled inlines are not a problem to point-based hit-testing because they can not be hit (they are fully covered by their children), but in area-based hit-testing we want all elements in the area, and therefore need to find the culled inlines again.

Thank you.  I was not aware the linebox tree had that optimization.

[Allan Sandfeld Jensen]

(In reply to comment #26)
> (In reply to comment #25)
> > (In reply to comment #24)
> > > (From update of attachment 163103 [details] [details] [details])
> > > My difficulty in reviewing this is that I don't really understand what culled inlines are.  Perhaps you could explain what you mean by "culled" in this patch.
> > 
> > I think it would be a bit too complicated to explain in patch, but I could give it a try.
> > 
> > Culled inline elements are inline-boxes that have been removed (culled) from the line layout, because they were unimportant to layout and take up memory and hurt performance. Imagine something like <span><span>Text</span></span>. The two spans would have the exact same size and dimensions as the inner text-node and could be culled without changing anything about the layout, leaving just one inline-box instead of three. The elements are still in the render-tree, but do not take part in line-layout.
> > 
> > Note that culled inlines are not a problem to point-based hit-testing because they can not be hit (they are fully covered by their children), but in area-based hit-testing we want all elements in the area, and therefore need to find the culled inlines again.
> 
> Thank you.  I was not aware the linebox tree had that optimization.

Neither did I before working on this patch. It is a rather obscure optimization, I guess that means it works well and stays out of way most of the time ;)

[Dave Hyatt]

Comment on attachment 163103 [details]
Patch

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

> Source/WebCore/rendering/InlineFlowBox.cpp:1058
> +    if (!renderer->isRenderInline() || !renderer->visibleToHitTesting())

Minor nitpick, but it's a bit faster to just say:

if (!parent() || !renderer->visibleToHitTesting())
 
You won't be hit testing anything that is unrooted, so you can just do the nice fast non-virtual check of whether or not you have a parent or not. Only RootInlineBoxes don't have parents, and all the others will be render inlines. We use this trick elsewhere in the code a fair bit for speed, so I'd do it here too.

> Source/WebCore/rendering/InlineFlowBox.cpp:1063
> +    FloatRect adjustedRect = renderInline->linesBoundingBox();

Isn't this a bit inaccurate? Don't you need to check for intersection with each individual rect?  Seems like you want to use generateCulledLineBoxRects and look at each rect individually no?

[Allan Sandfeld Jensen]

(In reply to comment #28)
> (From update of attachment 163103 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=163103&action=review
> 
> > Source/WebCore/rendering/InlineFlowBox.cpp:1058
> > +    if (!renderer->isRenderInline() || !renderer->visibleToHitTesting())
> 
> Minor nitpick, but it's a bit faster to just say:
> 
> if (!parent() || !renderer->visibleToHitTesting())
> 
> You won't be hit testing anything that is unrooted, so you can just do the nice fast non-virtual check of whether or not you have a parent or not. Only RootInlineBoxes don't have parents, and all the others will be render inlines. We use this trick elsewhere in the code a fair bit for speed, so I'd do it here too.
> 
> > Source/WebCore/rendering/InlineFlowBox.cpp:1063
> > +    FloatRect adjustedRect = renderInline->linesBoundingBox();
> 
> Isn't this a bit inaccurate? Don't you need to check for intersection with each individual rect?  Seems like you want to use generateCulledLineBoxRects and look at each rect individually no?

Right, it could be inaccurate if a culled inline spans over multiple lines starting or ending with a partial line.

[Allan Sandfeld Jensen]

Created attachment 163875 [details]
Patch

Make the intersection and contains check using a culled inlines generator context.

[Allan Sandfeld Jensen]

Created attachment 164391 [details]
Patch

Rebased and added a test for the case spotted by dhyatt and fixed in the last patch.

[Dave Hyatt]

Comment on attachment 164391 [details]
Patch

r=me

[Allan Sandfeld Jensen]

Committed r135841: <http://trac.webkit.org/changeset/135841>