Bug 85792 – NodesFromRect and area-based hit-testing can not handle CSS transforms

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Allan Sandfeld Jensen]

If CSS transforms such as scale() or rotate()  are applied to an element nodesFromRect will not return the correct nodes in the rect, since the transforms are ignored on the rectangle dimensions.

The problem is that only the central pointer is transformed when recursing down the document tree, while the rectangle is not. To solve this hit-testing must include a transformed area and not just a transformed pointer.

Also we will need a fast way to test intersection between a rectangle and a transformed rectangle (a FloatQuad).

[Allan Sandfeld Jensen]

Created attachment 140697 [details]
WIP

This patch is not for review.
It is still missing ChangeLog. There is still Qt instrumentation.
Automated testing is not yet complete. And I am still searching for a source of a few weird results.

But I do think the code is mostly complete and the strategy and logic can be examined and commented on.

[Allan Sandfeld Jensen]

Created attachment 140713 [details]
Patch

[Build Bot]

Comment on attachment 140713 [details]
Patch

Attachment 140713 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/12653285

[Antonio Gomes]

did not review, just a request: lets factor out HitTestPoint one its on patch.

[Early Warning System Bot]

Comment on attachment 140713 [details]
Patch

Attachment 140713 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/12653288

[Early Warning System Bot]

Comment on attachment 140713 [details]
Patch

Attachment 140713 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/12649382

[Allan Sandfeld Jensen]

Created attachment 140719 [details]
Patch

Include build-system updates.

[Allan Sandfeld Jensen]

(In reply to comment #4)
> did not review, just a request: lets factor out HitTestPoint one its on patch.

We could do that. It is a very small change actually. The only issue is that the patch looks kind of odd on its own.

[Eric Seidel (no email)]

I'm amazed that WebKit has two separate DOM apis for this:
https://developer.mozilla.org/en/XPCOM_Interface_Reference/nsIDOMWindowUtils#nodesFromRect()
and
http://trac.webkit.org/browser/trunk/Source/WebCore/svg/SVGSVGElement.cpp#L362

:)  One which uses SVG types, and one which uses bare values.  (Assuming nodesFromRect is what WebKit implements here.)  Also that these hit testing systems are presumably implemented separately, since getIntersectionList does not use HitTestResult. :(
http://trac.webkit.org/browser/trunk/Source/WebCore/svg/SVGSVGElement.cpp#L342

[Eric Seidel (no email)]

Ah, looks like this is currently only exposed via internals?
http://trac.webkit.org/browser/trunk/LayoutTests/fast/dom/resources/nodesFromRect.js#L14

Do we expose rect-based hittesting in any other fashion?  Do you know?  My hittesting knowledge is rather dated at this point.

[Allan Sandfeld Jensen]

(In reply to comment #10)
> Ah, looks like this is currently only exposed via internals?
> http://trac.webkit.org/browser/trunk/LayoutTests/fast/dom/resources/nodesFromRect.js#L14
> 
> Do we expose rect-based hittesting in any other fashion?  Do you know?  My hittesting knowledge is rather dated at this point.

Well, it is not in Document.idl, so probably not. This means it is only used for touch-based hit-testing.

[Allan Sandfeld Jensen]

Created attachment 142196 [details]
Patch

[Kenneth Rohde Christiansen]

Comment on attachment 142196 [details]
Patch

You forgot the tests

[Allan Sandfeld Jensen]

Created attachment 142198 [details]
Patch

Now including the tests

[Build Bot]

Comment on attachment 142198 [details]
Patch

Attachment 142198 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/12721048

[Allan Sandfeld Jensen]

Created attachment 142205 [details]
Patch

Fix win build

[Allan Sandfeld Jensen]

Comment on attachment 142205 [details]
Patch

With green bot, promote to candidate to commit.

[WebKit Review Bot]

Comment on attachment 142205 [details]
Patch

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

New failing tests:
touchadjustment/scroll-delegation/iframe-with-mainframe-scroll-offset.html

[WebKit Review Bot]

Created attachment 142227 [details]
Archive of layout-test-results from ec2-cr-linux-04

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: ec2-cr-linux-04  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.35-28-virtual-x86_64-with-Ubuntu-10.10-maverick

[Allan Sandfeld Jensen]

Created attachment 142236 [details]
Patch

Correct area used in touch-adjustment functions

[Allan Sandfeld Jensen]

Comment on attachment 142236 [details]
Patch

Requires slight rebasing after review.

[Allan Sandfeld Jensen]

Created attachment 144767 [details]
Patch

Patch rebased to apply on top of patch from bug 86605, do not feed to bots until that patch has landed.

Also cleaned the two test-cases based on reviewer feedback.

[Julien Chaffraix]

Comment on attachment 144767 [details]
Patch

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

After a quick glance, the direction seems OK. I haven't spotted anything too bad but it's difficult to look into the details when the patch is so big. Several of the refactorings could be pushed to blocking bugs to ease review though.

> Source/WebCore/rendering/HitTestResult.h:56
> +    HitTestPoint(const FloatPoint&, const FloatQuad&);
> +    HitTestPoint(const LayoutPoint& centerPoint, const IntRect&);

Shouldn't we make those constructor also explicit for consistency?

> Source/WebCore/rendering/HitTestResult.h:87
> +    IntRect m_boundingRect;

I would move part of this refactoring to a new bug. The change is already pretty massive.

> Source/WebCore/rendering/RenderEmbeddedObject.cpp:275
> -    IntPoint roundedPoint = roundedIntPoint(pointInContainer);
> +    IntPoint roundedPoint = pointInContainer.roundedPoint();

You could keep the external function pattern here to avoid having 2 ways between LayoutPoint/IntPoint and HitTestPoints.

> Source/WebCore/rendering/RenderFlowThread.cpp:310
> +    LayoutSize renderFlowThreadOffset;

This change is arguable and WebKit as a project hasn't done a good job at saying how an offset should be represented... If it can be avoided, I would rather not changing the type from Point to Size but I don't feel strongly about it.

> Source/WebCore/rendering/RenderObject.h:654
> +    virtual bool nodeAtPoint(const HitTestRequest&, HitTestResult&, const HitTestPoint& pointInContainer, const LayoutPoint& accumulatedOffset, HitTestAction);

OVERRIDE :)

[Allan Sandfeld Jensen]

(In reply to comment #23)
> (From update of attachment 144767 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=144767&action=review
> 
> After a quick glance, the direction seems OK. I haven't spotted anything too bad but it's difficult to look into the details when the patch is so big. Several of the refactorings could be pushed to blocking bugs to ease review though.
>
I can separate a few more things out, you also bring up a good option for that, but the final patch is still going to be large because changing the input type for nodeAtPoint requires minor changes in many files.

> > Source/WebCore/rendering/HitTestResult.h:56
> > +    HitTestPoint(const FloatPoint&, const FloatQuad&);
> > +    HitTestPoint(const LayoutPoint& centerPoint, const IntRect&);
> 
> Shouldn't we make those constructor also explicit for consistency?
> 
No, since these constructors takes two arguments explicit is not necessary, and might not even be allowed.

> > Source/WebCore/rendering/RenderObject.h:654
> > +    virtual bool nodeAtPoint(const HitTestRequest&, HitTestResult&, const HitTestPoint& pointInContainer, const LayoutPoint& accumulatedOffset, HitTestAction);
> 
> OVERRIDE :)

No, not this one. It is the base declaration. Funny enough I had override on it until I actually got to test it with GCC 4.7 in C++11 mode, and realized it was wrong :)

[Allan Sandfeld Jensen]

I have separated the largest but also most harmless change into bug #89448, this is simply changing the API of nodeAtPoint, and a naturally continuation of bug #85965 which was separated earlier.

[Allan Sandfeld Jensen]

Created attachment 148301 [details]
Patch

[Eric Seidel (no email)]

Allan: Again here, the patch looks sane, and I'm happy to help review once I slog through more of my post-vacation backlog.

I'm still missing (likely due to my oversight!) a high-level overview of why we have rect-based-hittesting implemented in this manner, and how it's different from the other rect-based hit testing mentioned in comment 9.

Is there a webkit-dev post (or bug or bug comment) you could point me to about understanding the rational behind this work?  Specifically I'm interested in the following:

1.  What are we adding with this new rect-based hittesting work?  (Fixing an exiting feature, or adding new functionality?)

2.  What's this functionality for (a device?  a DOM API? which ports does it affect?)

3.  How does this relate to our existing "rect based hit testing" (assuming I'm understanding those other APIs correctly).  Are they going to move to this model?

4.  I'd kinda like a general overview of how much work there is on this feature.  Is this patch 1 of 35?  Or 1 of 4?

Anyway, if you could point me to those answers, I'm happy to be a reviewer on this (and any future!) rect-based hit-testing patches.  Thank you in advance!

[Allan Sandfeld Jensen]

(In reply to comment #27)
> Allan: Again here, the patch looks sane, and I'm happy to help review once I slog through more of my post-vacation backlog.
> 
> I'm still missing (likely due to my oversight!) a high-level overview of why we have rect-based-hittesting implemented in this manner, and how it's different from the other rect-based hit testing mentioned in comment 9.
> 
> Is there a webkit-dev post (or bug or bug comment) you could point me to about understanding the rational behind this work?  Specifically I'm interested in the following:
> 
> 1.  What are we adding with this new rect-based hittesting work?  (Fixing an exiting feature, or adding new functionality?)
> 
This is bug-fix to nodesFromRect, but nodesFromRect is an internal API, but is used by all the touch resolution code. NodesFromRect currently doesn't handle SVG, though this patch should make it possible to fix that later now.

> 2.  What's this functionality for (a device?  a DOM API? which ports does it affect?)
> 
It affects touch devices. It means you will be able to actually touch-activate transformed elements, were you are currently likely to activate a wrong element on the screen, or at least show the activation high-light on the wrong element, but end up activating the right one any way (depending on platform.

> 3.  How does this relate to our existing "rect based hit testing" (assuming I'm understanding those other APIs correctly).  Are they going to move to this model?
> 
This is a fix to the existing rect-based hit testing model. It doesn't change, the patch just adds the ability for the area being tested to have been transformed instead of staying the same size and shape.

> 4.  I'd kinda like a general overview of how much work there is on this feature.  Is this patch 1 of 35?  Or 1 of 4?
> 
> Anyway, if you could point me to those answers, I'm happy to be a reviewer on this (and any future!) rect-based hit-testing patches.  Thank you in advance!

This is the final patch for this bug fix. Originally it was the only patch, but due to the size of it, several reviewers has asked me to split it into several parts.

[Eric Seidel (no email)]

(In reply to comment #28)
> (In reply to comment #27)

Thank you for your helpful answers!

> > 2.  What's this functionality for (a device?  a DOM API? which ports does it affect?)
> > 
> It affects touch devices. It means you will be able to actually touch-activate transformed elements, were you are currently likely to activate a wrong element on the screen, or at least show the activation high-light on the wrong element, but end up activating the right one any way (depending on platform.

Which platforms use this touch code?  Qt?  Do you know if iOS WebKit does?

[Allan Sandfeld Jensen]

(In reply to comment #29)
> 
> Which platforms use this touch code?  Qt?  Do you know if iOS WebKit does?

I can't know for sure, the code that does touch is only shipped as compiled binaries in the iOS source dump, but I suspect that they do.

But I know Qt, Android, Blackberry and Chromium for Android uses nodesFromRect.

[Eric Seidel (no email)]

(In reply to comment #30)
> (In reply to comment #29)
> > 
> > Which platforms use this touch code?  Qt?  Do you know if iOS WebKit does?
> 
> I can't know for sure, the code that does touch is only shipped as compiled binaries in the iOS source dump, but I suspect that they do.
> 
> But I know Qt, Android, Blackberry and Chromium for Android uses nodesFromRect.

Thank you again.  So this is common support, which i just simply wasn't aware of. :)

[Eric Seidel (no email)]

Simon Fraser is probably your best reviewer for this, but I can also do so if needed.  I trust his recall of basic geometry more than my own. :)

[Allan Sandfeld Jensen]

Created attachment 149282 [details]
Patch

Rebased on landed requisite patches

[Allan Sandfeld Jensen]

After this patch it will make sense to remove m_lastPlanarPoint and m_lastPlanarQuad from HitTestingTransformState. They are only used from one remaining function now, and doesn't really belong there.

Moving m_region from HitTestResult to HitTestPoint might also make sense now, and would eliminate saving and restoring of HitTestResult::region in RenderFlowThread::hitTestRegion.

Neither are directly required for this bug-fix though.

[Gustavo Noronha (kov)]

Comment on attachment 149282 [details]
Patch

Attachment 149282 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/13087164

[Build Bot]

Comment on attachment 149282 [details]
Patch

Attachment 149282 [details] did not pass win-ews (win):
Output: http://queues.webkit.org/results/13088187

[WebKit Review Bot]

Comment on attachment 149282 [details]
Patch

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

[Allan Sandfeld Jensen]

Created attachment 149287 [details]
Patch

[WebKit Review Bot]

Comment on attachment 149287 [details]
Patch

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

New failing tests:
transforms/3d/hit-testing/perspective-clipped.html
transforms/3d/hit-testing/coplanar-with-camera.html
transforms/3d/point-mapping/3d-point-mapping-overlapping.html
transforms/3d/point-mapping/3d-point-mapping-preserve-3d.html
transforms/3d/hit-testing/rotated-hit-test2.html
transforms/3d/hit-testing/rotated-hit-test.html
transforms/3d/hit-testing/rotated-hit-test-with-child.html
transforms/3d/point-mapping/3d-point-mapping-origins.html
transforms/3d/point-mapping/3d-point-mapping.html

[WebKit Review Bot]

Created attachment 149314 [details]
Archive of layout-test-results from ec2-cr-linux-02

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: ec2-cr-linux-02  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.35-28-virtual-x86_64-with-Ubuntu-10.10-maverick

[Allan Sandfeld Jensen]

Created attachment 149508 [details]
Patch

[Early Warning System Bot]

Comment on attachment 149508 [details]
Patch

Attachment 149508 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/13103395

[Early Warning System Bot]

Comment on attachment 149508 [details]
Patch

Attachment 149508 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/13097429

[Gyuyoung Kim]

Comment on attachment 149508 [details]
Patch

Attachment 149508 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/13098409

[Allan Sandfeld Jensen]

Created attachment 149513 [details]
Patch

Re-add accidentally removed line

[WebKit Review Bot]

Comment on attachment 149513 [details]
Patch

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

New failing tests:
svg/text/select-x-list-4.svg

[WebKit Review Bot]

Created attachment 149521 [details]
Archive of layout-test-results from ec2-cr-linux-01

The attached test failures were seen while running run-webkit-tests on the chromium-ews.
Bot: ec2-cr-linux-01  Port: <class 'webkitpy.common.config.ports.ChromiumXVFBPort'>  Platform: Linux-2.6.35-28-virtual-x86_64-with-Ubuntu-10.10-maverick

[Allan Sandfeld Jensen]

Created attachment 149534 [details]
Patch

Keep the rounding in SVG-text unchanged to floored ints.

[Allan Sandfeld Jensen]

Comment on attachment 149534 [details]
Patch

Will need to have the test-cases moved before landing.

[Eric Seidel (no email)]

Comment on attachment 149534 [details]
Patch

Looks reasonable.

[Allan Sandfeld Jensen]

Committed r123624: <http://trac.webkit.org/changeset/123624>