Implement findAnchor and computeRelativeOffset in ScrollAnchor.

Implement findAnchor and computeRelativeOffset in ScrollAnchor.

BUG=558575
Committed: https://crrev.com/151ee85f4f13bb30afdfe0986a1a85216868ce04
Cr-Commit-Position: refs/heads/master@{#373998}

[skobes, 2016-01-29 06:46:40]

skobes@chromium.org changed reviewers:
+ ojan@chromium.org

[ojan, 2016-02-02 06:26:41]

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

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:47: while (child) {
I think we'll need to think about how out of flow positioned and floated
elements should be treated. My gut feeling is that we should skip them, but I'm
not sure what to do on pages where all the visible content is out of flow or
floated. In either case, this is a good start and we can figure that out in
followup patches as we experiment.

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:50: candidate = child;
I think we can make this more efficient by restarting the tree walk as soon as
we hit any child that intersects. Which is to say, once we hit a child that
intersects, we don't need to walk any of it's other siblings or aunts. We just
need to find the deepest child that intersects. That way you can also avoid the
contains check below.

I think the two key bits to making findAnchor fast will be:
1. Pruning the tree walk as much as possible
2. Minimizes the number of rect comparisons for the tree walking we need to do.

[chrishtr, 2016-02-02 17:56:14]

chrishtr@chromium.org changed reviewers:
+ chrishtr@chromium.org

[chrishtr, 2016-02-02 17:56:15]

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

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:42: :
scrollerBox->localToAbsoluteQuad(
absolute maps to the space of the containing view, even for scrollers which are
not
a FrameView. Mapping to the space of the scroller should be sufficient, and more
efficient.

[skobes, 2016-02-02 23:03:55]

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

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:42: :
scrollerBox->localToAbsoluteQuad(
On 2016/02/02 17:56:15, chrishtr wrote:
> absolute maps to the space of the containing view, even for scrollers which
are
> not
> a FrameView. Mapping to the space of the scroller should be sufficient, and
more
> efficient.

I agree, however it may require some new plumbing since
LayoutObject::absoluteQuads has useful overrides in LayoutText and LayoutInline
with (as far as I can tell) no local-coordinate equivalent.  Added a TODO.

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:47: while (child) {
On 2016/02/02 06:26:41, ojan wrote:
> I think we'll need to think about how out of flow positioned and floated
> elements should be treated. My gut feeling is that we should skip them, but
I'm
> not sure what to do on pages where all the visible content is out of flow or
> floated. In either case, this is a good start and we can figure that out in
> followup patches as we experiment.

Yes I expect we'll add a bunch of edge cases and exceptions here in follow up
patches.

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:50: candidate = child;
On 2016/02/02 06:26:41, ojan wrote:
> I think we can make this more efficient by restarting the tree walk as soon as
> we hit any child that intersects. Which is to say, once we hit a child that
> intersects, we don't need to walk any of it's other siblings or aunts. We just
> need to find the deepest child that intersects. That way you can also avoid
the
> contains check below.

I was thinking we should prefer a fully-contained node to an intersecting node. 
If we limit our walk to to the first intersecting node we may miss a
fully-contained node further down.  E.g.

Scroller
  div id=A
  div id=B
    div id=B1

If A and B both overlap the viewport, and B1 is fully contained, we want to
anchor to B1, not stop at A.

[ojan, 2016-02-03 01:37:03]

lgtm assuming chris is OK with the absolute quad computation being fixed as a
TODO.

At this point, we still need to experiment to see what a good user experience
is, so I'm OK putting off the work of performance optimizing findAnchor since
what we decide to do there might be very different. We'll definitely want more
pruning in the end than a whole subtree walk, but that's something we can figure
out once we know the behavior we want.

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

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:50: candidate = child;
On 2016/02/02 at 23:03:55, skobes wrote:
> On 2016/02/02 06:26:41, ojan wrote:
> > I think we can make this more efficient by restarting the tree walk as soon
as
> > we hit any child that intersects. Which is to say, once we hit a child that
> > intersects, we don't need to walk any of it's other siblings or aunts. We
just
> > need to find the deepest child that intersects. That way you can also avoid
the
> > contains check below.
> 
> I was thinking we should prefer a fully-contained node to an intersecting
node.  If we limit our walk to to the first intersecting node we may miss a
fully-contained node further down.  E.g.
> 
> Scroller
>   div id=A
>   div id=B
>     div id=B1
> 
> If A and B both overlap the viewport, and B1 is fully contained, we want to
anchor to B1, not stop at A.

Do A and B both partially overlap the viewport in this example? I was picturing
that we pick the deepest element in the first element that overlaps the
viewport. What's the case where fully contained is better? (honest question)

https://codereview.chromium.org/1640973005/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ScrollAnchorTest.cpp (right):

https://codereview.chromium.org/1640973005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ScrollAnchorTest.cpp:16: class
ScrollAnchorTest : public RenderingTest {
I think this might be better as a SimTest. See
https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...
for examples. The advantage of a SimTest is that it runs something closer to
what an actual web page does instead of calling updateAllLifeCyclePhases outside
of the context of actually pumping a frame from the compositor. It makes the
tests a bit less fragile to refactors as we change how we do things like
updating the lifecycle phases.

[chrishtr, 2016-02-03 18:33:03]

I'm ok with a TODO. We should also look closely at the performance
characteristics leading
up to any launch of the feature. But I agree that for now it's most important to
have a
performant-enough version that we can play with to see if it works well.

[skobes, 2016-02-04 01:51:15]

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

https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:50: candidate = child;
On 2016/02/03 01:37:03, ojan wrote:
> On 2016/02/02 at 23:03:55, skobes wrote:
> > On 2016/02/02 06:26:41, ojan wrote:
> > > I think we can make this more efficient by restarting the tree walk as
soon
> as
> > > we hit any child that intersects. Which is to say, once we hit a child
that
> > > intersects, we don't need to walk any of it's other siblings or aunts. We
> just
> > > need to find the deepest child that intersects. That way you can also
avoid
> the
> > > contains check below.
> > 
> > I was thinking we should prefer a fully-contained node to an intersecting
> node.  If we limit our walk to to the first intersecting node we may miss a
> fully-contained node further down.  E.g.
> > 
> > Scroller
> >   div id=A
> >   div id=B
> >     div id=B1
> > 
> > If A and B both overlap the viewport, and B1 is fully contained, we want to
> anchor to B1, not stop at A.
> 
> Do A and B both partially overlap the viewport in this example? I was
picturing
> that we pick the deepest element in the first element that overlaps the
> viewport. What's the case where fully contained is better? (honest question)

Yes, A and B both partially overlap (perhaps A continues above the fold and B
continues below the fold), but only B has a fully-contained descendent.  In this
case it is better to anchor to B1.

[ojan, 2016-02-05 10:37:58]

On 2016/02/04 at 01:51:15, skobes wrote:
>
https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
> File third_party/WebKit/Source/core/layout/ScrollAnchor.cpp (right):
> 
>
https://codereview.chromium.org/1640973005/diff/1/third_party/WebKit/Source/c...
> third_party/WebKit/Source/core/layout/ScrollAnchor.cpp:50: candidate = child;
> On 2016/02/03 01:37:03, ojan wrote:
> > On 2016/02/02 at 23:03:55, skobes wrote:
> > > On 2016/02/02 06:26:41, ojan wrote:
> > > > I think we can make this more efficient by restarting the tree walk as
soon
> > as
> > > > we hit any child that intersects. Which is to say, once we hit a child
that
> > > > intersects, we don't need to walk any of it's other siblings or aunts.
We
> > just
> > > > need to find the deepest child that intersects. That way you can also
avoid
> > the
> > > > contains check below.
> > > 
> > > I was thinking we should prefer a fully-contained node to an intersecting
> > node.  If we limit our walk to to the first intersecting node we may miss a
> > fully-contained node further down.  E.g.
> > > 
> > > Scroller
> > >   div id=A
> > >   div id=B
> > >     div id=B1
> > > 
> > > If A and B both overlap the viewport, and B1 is fully contained, we want
to
> > anchor to B1, not stop at A.
> > 
> > Do A and B both partially overlap the viewport in this example? I was
picturing
> > that we pick the deepest element in the first element that overlaps the
> > viewport. What's the case where fully contained is better? (honest question)
> 
> Yes, A and B both partially overlap (perhaps A continues above the fold and B
continues below the fold), but only B has a fully-contained descendent.  In this
case it is better to anchor to B1.

I still don't see the advantage of being fully contained. I think the best way
to make sense of this though is to browse around the web and find example of
tricky cases we need to get right for a good user experience that we then turn
into test cases.

[skobes, 2016-02-05 17:53:47]

On 2016/02/05 10:37:58, ojan wrote:
> I still don't see the advantage of being fully contained. I think the best way
> to make sense of this though is to browse around the web and find example of
> tricky cases we need to get right for a good user experience that we then turn
> into test cases.

I was picturing something like this:
https://docs.google.com/drawings/d/1zrrMeu_0rLcSYYpUrVvnzSHfMcVk73cAh-io3_89m...

Maybe it doesn't matter though.

[ojan, 2016-02-06 00:23:57]

On 2016/02/05 at 17:53:47, skobes wrote:
> On 2016/02/05 10:37:58, ojan wrote:
> > I still don't see the advantage of being fully contained. I think the best
way
> > to make sense of this though is to browse around the web and find example of
> > tricky cases we need to get right for a good user experience that we then
turn
> > into test cases.
> 
> I was picturing something like this:
>
https://docs.google.com/drawings/d/1zrrMeu_0rLcSYYpUrVvnzSHfMcVk73cAh-io3_89m...
> 
> Maybe it doesn't matter though.

The question is what scenario it would make sense to do something differently if
we pick the "Lorem ipsum" box versus the "Phasellus quis" box. The only one I
can think of is if there's an image at the bottom of the "Lorem ipsum" box that
loads. In this case picking the "Phasellus quis" box is clearly better, but
that's not because it's fully contained, but rather because it takes up more of
the content a user is likely to be looking at.

This makes me think we should try to find the first in flow element that's in
the middle of the page if we find this scenario to be common. Or maybe the
biggest deep in-flow element? Or the deepest element that takes up the most of
the screen? These are all things we can iterate on.

[skobes, 2016-02-06 00:32:04]

On 2016/02/06 00:23:57, ojan wrote:
> The question is what scenario it would make sense to do something differently
if
> we pick the "Lorem ipsum" box versus the "Phasellus quis" box. The only one I
> can think of is if there's an image at the bottom of the "Lorem ipsum" box
that
> loads.

It doesn't have to be at the bottom.  Consider an image load in the middle of
the "Lorem ipsum" box, above the viewport.  If we anchor to the "Lorem ipsum"
box, the whole screen will jump.  If we anchor to the "Phasellus quis" box, none
of the pixels inside the viewport change.  A fully-contained box won't have
anything dropping in above the fold.

> This makes me think we should try to find the first in flow element that's in
> the middle of the page if we find this scenario to be common. Or maybe the
> biggest deep in-flow element? Or the deepest element that takes up the most of
> the screen? These are all things we can iterate on.

Agreed.

[skobes, 2016-02-06 01:02:17]

https://codereview.chromium.org/1640973005/diff/40001/third_party/WebKit/Sour...
File third_party/WebKit/Source/core/layout/ScrollAnchorTest.cpp (right):

https://codereview.chromium.org/1640973005/diff/40001/third_party/WebKit/Sour...
third_party/WebKit/Source/core/layout/ScrollAnchorTest.cpp:16: class
ScrollAnchorTest : public RenderingTest {
On 2016/02/03 01:37:03, ojan wrote:
> I think this might be better as a SimTest. See
>
https://code.google.com/p/chromium/codesearch#chromium/src/third_party/WebKit...
> for examples. The advantage of a SimTest is that it runs something closer to
> what an actual web page does instead of calling updateAllLifeCyclePhases
outside
> of the context of actually pumping a frame from the compositor. It makes the
> tests a bit less fragile to refactors as we change how we do things like
> updating the lifecycle phases.

This is made tricky by SimTest being in web instead of core.  Do you think we
should move ScrollAnchorTest into web?

[skobes, 2016-02-06 01:02:33]

The CQ bit was checked by skobes@chromium.org

[skobes, 2016-02-06 01:02:33]

The patchset sent to the CQ was uploaded after l-g-t-m from ojan@chromium.org
Link to the patchset: https://codereview.chromium.org/1640973005/#ps100001
(title: "cache offset between layouts")

[skobes, 2016-02-06 01:05:29]

(Patch set 6 incorporates suggestion from http://crrev.com/1647793002 to not
recompute m_savedRelativeOffset when the anchor node has not changed.)

[commit-bot: I haz the power, 2016-02-06 01:05:42]

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

[commit-bot: I haz the power, 2016-02-06 02:42:31]

Committed patchset #6 (id:100001)

[commit-bot: I haz the power, 2016-02-06 02:44:02]

Description was changed from

==========
Implement findAnchor and computeRelativeOffset in ScrollAnchor.

BUG=558575
==========

to

==========
Implement findAnchor and computeRelativeOffset in ScrollAnchor.

BUG=558575

Committed: https://crrev.com/151ee85f4f13bb30afdfe0986a1a85216868ce04
Cr-Commit-Position: refs/heads/master@{#373998}
==========

[commit-bot: I haz the power, 2016-02-06 02:44:02]

Patchset 6 (id:??) landed as
https://crrev.com/151ee85f4f13bb30afdfe0986a1a85216868ce04
Cr-Commit-Position: refs/heads/master@{#373998}