Stop hit testing culled inlines when a match is found

Stop hit testing culled inlines when a match is found

Culled inline hittesting was recently fixed [1] which exposed a
bug in LayoutInline::hitTestCulledInline where hit testing checked
for region intersection but returned a value based on region
containment. This bug was partially fixed in [2] for list-based
tests but a bug still existed for point-based tests.

This patch updates LayoutInline::hitTestCulledInline to check for
hit tests using region intersection, and return a value based on
region intersection (not containment). This was done by fixing a FIXME
to implement HitTestRequest::addNodeToListBasedTestResult for regions.

In addition, this patch changes the return value of
HitTestRequest::addNodeToListBasedTestResult to be an enum which
better explains its behavior.

[1] https://src.chromium.org/viewvc/blink?view=rev&revision=193729
[2] https://crrev.com/b489f7917175e2449c8f6d5874ab3ba0b7f31e88

BUG=579412
Committed: https://crrev.com/4dd5f8bbaa8e06c2bca14e20758cd4f76d0a81d4
Cr-Commit-Position: refs/heads/master@{#372023}

[pdr., 2016-01-25 17:52:39]

pdr@chromium.org changed reviewers:
+ chrishtr@chromium.org, myid.m.shin@gmail.com, myid.shin@chromium.org,
rbyers@chromium.org

[pdr., 2016-01-25 17:52:43]

The CQ bit was checked by pdr@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-01-25 17:54:18]

Dry run: CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1630793002/1
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1630793002/1

[commit-bot: I haz the power, 2016-01-25 19:16:02]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-01-25 19:16:03]

Dry run: This issue passed the CQ dry run.

[Rick Byers, 2016-01-25 21:50:05]

https://codereview.chromium.org/1630793002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/HitTestResult.cpp (right):

https://codereview.chromium.org/1630793002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/HitTestResult.cpp:454: {
Seems a shame to copy/paste this entire function.  Refactor to implement the
rect verison in terms of the region version?  Or, worst case, make a template
method.

[pdr., 2016-01-25 23:47:37]

PTAL

@myid.m.shin, can you review this too? You're not a reviewer yet but you know a
lot about this area.

https://codereview.chromium.org/1630793002/diff/1/third_party/WebKit/Source/c...
File third_party/WebKit/Source/core/layout/HitTestResult.cpp (right):

https://codereview.chromium.org/1630793002/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/HitTestResult.cpp:454: {
On 2016/01/25 at 21:50:05, Rick Byers wrote:
> Seems a shame to copy/paste this entire function.  Refactor to implement the
rect verison in terms of the region version?  Or, worst case, make a template
method.

Good idea.

This isn't possible due to the default argument on the rect version, but I've
extracted out a common function and added a fixme that describes what the 3rd
argument is for.

I opted for not templatizing the new 3-line addNodeToListBasedTestResult
functions to keep things simple.

[Rick Byers, 2016-01-26 15:19:44]

On 2016/01/25 23:47:37, pdr wrote:
> PTAL
> 
> @myid.m.shin, can you review this too? You're not a reviewer yet but you know
a
> lot about this area.
> 
>
https://codereview.chromium.org/1630793002/diff/1/third_party/WebKit/Source/c...
> File third_party/WebKit/Source/core/layout/HitTestResult.cpp (right):
> 
>
https://codereview.chromium.org/1630793002/diff/1/third_party/WebKit/Source/c...
> third_party/WebKit/Source/core/layout/HitTestResult.cpp:454: {
> On 2016/01/25 at 21:50:05, Rick Byers wrote:
> > Seems a shame to copy/paste this entire function.  Refactor to implement the
> rect verison in terms of the region version?  Or, worst case, make a template
> method.
> 
> Good idea.
> 
> This isn't possible due to the default argument on the rect version, but I've
> extracted out a common function and added a fixme that describes what the 3rd
> argument is for.
> 
> I opted for not templatizing the new 3-line addNodeToListBasedTestResult
> functions to keep things simple.

Yep looks great, thanks!
  
LGTM, but I don't know the details about inline hit-testing, so I'd feel best if
Miyoung reviewed as well before landing.

[pdr., 2016-01-26 21:24:08]

pdr@chromium.org changed reviewers:
+ myid.o.shin@gmail.com, myid.shin@samsung.com

[pdr., 2016-01-26 21:24:35]

+cc the correct Miyoung Shin.

@Miyoung, could you review this?

[Miyoung Shin(c), 2016-01-27 06:29:35]

non owner's LGTM

[pdr., 2016-01-27 06:42:49]

The CQ bit was checked by pdr@chromium.org

[commit-bot: I haz the power, 2016-01-27 06:42:54]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1630793002/20001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1630793002/20001

[commit-bot: I haz the power, 2016-01-27 07:55:40]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-01-27 07:55:41]

Try jobs failed on following builders:
  win_chromium_rel_ng on tryserver.chromium.win (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.win/builders/win_chromium_rel_...)

[pdr., 2016-01-28 00:42:04]

Sadly, the patch had an error in addNodeToListBasedTestResult which was caught
by the CQ.

I had to revisit the template function addNodeToListBasedTestResult and made a
version that does work (see patchset titled "template metaprogramming with
forwarding and explicit instantiation of internal template arguments").
Unfortunately, I think the cure is worse than the disease in this case because
the templated version is complex and hard to maintain. The difficulty is that we
have two area types (LayoutRect, Region) and in the implementation needs to be
slightly different due to a cast. Additionally, the LayoutRect version needs a
default argument but we want to prevent a default argument for the Region
version.

I've circled back to a version with duplicated code. I think this will end up
being the more maintainable approach.

PTAL

[Rick Byers, 2016-01-28 00:50:36]

On 2016/01/28 00:42:04, pdr wrote:
> Sadly, the patch had an error in addNodeToListBasedTestResult which was caught
> by the CQ.
> 
> I had to revisit the template function addNodeToListBasedTestResult and made a
> version that does work (see patchset titled "template metaprogramming with
> forwarding and explicit instantiation of internal template arguments").
> Unfortunately, I think the cure is worse than the disease in this case because
> the templated version is complex and hard to maintain. The difficulty is that
we
> have two area types (LayoutRect, Region) and in the implementation needs to be
> slightly different due to a cast. Additionally, the LayoutRect version needs a
> default argument but we want to prevent a default argument for the Region
> version.
> 
> I've circled back to a version with duplicated code. I think this will end up
> being the more maintainable approach.
> 
> PTAL

Why not just move the 11 lines in common (which don't refer to region at all)
into a private helper function?

[pdr., 2016-01-28 01:48:21]

On 2016/01/28 at 00:50:36, rbyers wrote:
> On 2016/01/28 00:42:04, pdr wrote:
> > Sadly, the patch had an error in addNodeToListBasedTestResult which was
caught
> > by the CQ.
> > 
> > I had to revisit the template function addNodeToListBasedTestResult and made
a
> > version that does work (see patchset titled "template metaprogramming with
> > forwarding and explicit instantiation of internal template arguments").
> > Unfortunately, I think the cure is worse than the disease in this case
because
> > the templated version is complex and hard to maintain. The difficulty is
that we
> > have two area types (LayoutRect, Region) and in the implementation needs to
be
> > slightly different due to a cast. Additionally, the LayoutRect version needs
a
> > default argument but we want to prevent a default argument for the Region
> > version.
> > 
> > I've circled back to a version with duplicated code. I think this will end
up
> > being the more maintainable approach.
> > 
> > PTAL
> 
> Why not just move the 11 lines in common (which don't refer to region at all)
into a private helper function?

The 11 lines are all early returns with different values, so we have one of
those annoying ternary return problems :P The helper function needs to return a
bool (ListBasedHitTestBehavior), plus a bool for whether we should continue
checking for containment. It would look something like this:

// Returns true if a hit test behavior has been determined without needing a
containment check.
bool addNodeToListBasedTestResultWithoutCheckingContainment(Node* node, const
HitTestLocation& location, ListBasedHitTestBehavior& outHitTestBehavior)
{
    // If not a list-based test, stop testing because the hit has been found.
    if (!hitTestRequest().listBased()) {
        outHitTestBehavior = StopHitTesting;
        return true;
    }

    if (!node) {
        outHitTestBehavior = ContinueHitTesting;
        return true;
    }

    mutableListBasedTestResult().add(node);

    if (hitTestRequest().penetratingList()) {
        outHitTestBehavior = ContinueHitTesting;
        return true;
    }

    return false;
}

ListBasedHitTestBehavior HitTestResult::addNodeToListBasedTestResult(Node* node,
const HitTestLocation& location, const LayoutRect& rect)
{
    ListBasedHitTestBehavior hitTestBehavior;
    if (addNodeToListBasedTestResultWithoutCheckingContainment(node, location,
hitTestBehavior))
        return hitTestBehavior;

    return rect.contains(LayoutRect(location.boundingBox())) ? StopHitTesting :
ContinueHitTesting;
}

ListBasedHitTestBehavior HitTestResult::addNodeToListBasedTestResult(Node* node,
const HitTestLocation& location, const Region& region)
{
    ListBasedHitTestBehavior hitTestBehavior;
    if (addNodeToListBasedTestResultWithoutCheckingContainment(node, location,
hitTestBehavior))
        return hitTestBehavior;

    return region.contains(location.boundingBox()) ? StopHitTesting :
ContinueHitTesting;
}

I prefer the template approach in the previous patchset to this because it keeps
the logic together (at the expense of complexity).

[pdr., 2016-01-28 01:57:30]

Summarizing a bit. We have three approaches:
1) templates
2) duplicated code
3) helper function with out param complexity

Each of these has downsides but none are terrible, and I'm okay with
implementing any of them. I think the template approach may be the favorite so
far.

[Rick Byers, 2016-01-28 02:04:22]

Yeah I was thinking a ternary return like that.
Or there's option 4) use a macro <grin>.

Ok this is getting silly - I agree any of the options are fine, I've probably
already wasted more of your time than this is worth, sorry.  A tiny bit of
duplication right next to eachother isn't a huge deal.  LGTM as-is.

[pdr., 2016-01-28 02:07:31]

On 2016/01/28 at 02:04:22, rbyers wrote:
> Yeah I was thinking a ternary return like that.
> Or there's option 4) use a macro <grin>.
> 
> Ok this is getting silly - I agree any of the options are fine, I've probably
already wasted more of your time than this is worth, sorry.  A tiny bit of
duplication right next to eachother isn't a huge deal.  LGTM as-is.

I really don't feel like you wasted my time :) You brought up good ideas, they
just got messy in the details because C++ is terrible.


Cool, lets go with this patch then. Off to the CQ!

[pdr., 2016-01-28 02:07:43]

The CQ bit was checked by pdr@chromium.org

[pdr., 2016-01-28 02:07:43]

The patchset sent to the CQ was uploaded after l-g-t-m from
myid.shin@chromium.org
Link to the patchset: https://codereview.chromium.org/1630793002/#ps60001
(title: "Simpler approach, but duplicated code")

[commit-bot: I haz the power, 2016-01-28 02:08:01]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1630793002/60001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1630793002/60001

[Rick Byers, 2016-01-28 02:49:52]

On 2016/01/28 02:07:31, pdr wrote:
> On 2016/01/28 at 02:04:22, rbyers wrote:
> > Yeah I was thinking a ternary return like that.
> > Or there's option 4) use a macro <grin>.
> > 
> > Ok this is getting silly - I agree any of the options are fine, I've
probably
> already wasted more of your time than this is worth, sorry.  A tiny bit of
> duplication right next to eachother isn't a huge deal.  LGTM as-is.
> 
> I really don't feel like you wasted my time :) You brought up good ideas, they
> just got messy in the details because C++ is terrible.

My thoughts exactly.  I was thinking of how I'd write this in something like
OCaml which handles this sort of multiple return case much nicer, and I guess we
could do roughly the same with C++ tuples:

// Returns true if a hit test behavior has been determined without needing a
containment check.
tuple<bool,ListBaseHitTestBehavior>
addNodeToListBasedTestResultWithoutCheckingContainment(Node* node, const
HitTestLocation& location)
{
    // If not a list-based test, stop testing because the hit has been found.
    if (!hitTestRequest().listBased())
        return std::make_tuple(true, StopHitTesting);

    if (!node)
        return std::make_tuple(true, ContinueHitTesting);

    mutableListBasedTestResult().add(node);

    if (hitTestRequest().penetratingList())
        return std::make_tuple(true, ContinueHitTesting);

    return std::make_tuple(false,ContinueHitTesting);
}

ListBasedHitTestBehavior HitTestResult::addNodeToListBasedTestResult(Node* node,
const HitTestLocation& location, const LayoutRect& rect)
{
    bool shouldReturn;
    ListBasedHitTestBehavior result;
    std::tie(shouldReturn, result) =
addNodeToListBasedTestResultWithoutCheckingContainment(node, location,
hitTestBehavior);
    if (shouldReturn)
        return result;

    return rect.contains(LayoutRect(location.boundingBox())) ? StopHitTesting :
ContinueHitTesting;
}

etc...

Not so bad (though would be cleaner with patern matching).

> 
> 
> Cool, lets go with this patch then. Off to the CQ!

[commit-bot: I haz the power, 2016-01-28 05:41:46]

Committed patchset #4 (id:60001)

[commit-bot: I haz the power, 2016-01-28 05:42:32]

Description was changed from

==========
Stop hit testing culled inlines when a match is found

Culled inline hittesting was recently fixed [1] which exposed a
bug in LayoutInline::hitTestCulledInline where hit testing checked
for region intersection but returned a value based on region
containment. This bug was partially fixed in [2] for list-based
tests but a bug still existed for point-based tests.

This patch updates LayoutInline::hitTestCulledInline to check for
hit tests using region intersection, and return a value based on
region intersection (not containment). This was done by fixing a FIXME
to implement HitTestRequest::addNodeToListBasedTestResult for regions.

In addition, this patch changes the return value of
HitTestRequest::addNodeToListBasedTestResult to be an enum which
better explains its behavior.

[1] https://src.chromium.org/viewvc/blink?view=rev&revision=193729
[2] https://crrev.com/b489f7917175e2449c8f6d5874ab3ba0b7f31e88

BUG=579412
==========

to

==========
Stop hit testing culled inlines when a match is found

Culled inline hittesting was recently fixed [1] which exposed a
bug in LayoutInline::hitTestCulledInline where hit testing checked
for region intersection but returned a value based on region
containment. This bug was partially fixed in [2] for list-based
tests but a bug still existed for point-based tests.

This patch updates LayoutInline::hitTestCulledInline to check for
hit tests using region intersection, and return a value based on
region intersection (not containment). This was done by fixing a FIXME
to implement HitTestRequest::addNodeToListBasedTestResult for regions.

In addition, this patch changes the return value of
HitTestRequest::addNodeToListBasedTestResult to be an enum which
better explains its behavior.

[1] https://src.chromium.org/viewvc/blink?view=rev&revision=193729
[2] https://crrev.com/b489f7917175e2449c8f6d5874ab3ba0b7f31e88

BUG=579412

Committed: https://crrev.com/4dd5f8bbaa8e06c2bca14e20758cd4f76d0a81d4
Cr-Commit-Position: refs/heads/master@{#372023}
==========

[commit-bot: I haz the power, 2016-01-28 05:42:33]

Patchset 4 (id:??) landed as
https://crrev.com/4dd5f8bbaa8e06c2bca14e20758cd4f76d0a81d4
Cr-Commit-Position: refs/heads/master@{#372023}