Implement findAnchor and computeRelativeOffset in ScrollAnchor.

third_party/WebKit/Source/core/layout/ScrollAnchor.cpp

Index: third_party/WebKit/Source/core/layout/ScrollAnchor.cpp
diff --git a/third_party/WebKit/Source/core/layout/ScrollAnchor.cpp b/third_party/WebKit/Source/core/layout/ScrollAnchor.cpp
index 0b4a85d02dd0c068b629815050c143fe62b3e1c0..e1a4e7e1645f8b56163c30568ff8480ebfd6dda0 100644
--- a/third_party/WebKit/Source/core/layout/ScrollAnchor.cpp
+++ b/third_party/WebKit/Source/core/layout/ScrollAnchor.cpp
@@ -4,6 +4,10 @@
 
 #include "core/layout/ScrollAnchor.h"
 
+#include "core/frame/FrameView.h"
+#include "core/layout/LayoutBox.h"
+#include "core/layout/LayoutView.h"
+#include "core/paint/PaintLayerScrollableArea.h"
 #include "platform/scroll/ScrollableArea.h"
 #include "wtf/Assertions.h"
 
@@ -20,16 +24,40 @@ ScrollAnchor::~ScrollAnchor()
 {
 }
 
+static LayoutBox* scrollerLayoutBox(const ScrollableArea* scroller)
+{
+    LayoutBox* box = scroller->isFrameView()
+        ? toFrameView(scroller)->layoutView()
+        : &toPaintLayerScrollableArea(scroller)->box();
+    ASSERT(box);
+    return box;
+}
+
 static LayoutObject* findAnchor(const ScrollableArea* scroller)
 {
-    // TODO(skobes): implement.
-    return nullptr;
+    LayoutBox* scrollerBox = scrollerLayoutBox(scroller);
+
+    FloatRect absoluteVisibleRect = scroller->isFrameView()
+        ? scroller->visibleContentRect()
+        : scrollerBox->localToAbsoluteQuad(

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

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]

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.

+            FloatQuad(FloatRect(scrollerBox->overflowClipRect(LayoutPoint())))).boundingBox();
+
+    LayoutObject* child = scrollerBox->nextInPreOrder(scrollerBox);
+    LayoutObject* candidate = nullptr;
+    while (child) {

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

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.

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

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

+        FloatRect childRect = child->absoluteBoundingBoxFloatRect();
+        if (absoluteVisibleRect.intersects(childRect))
+            candidate = child;

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

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.

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

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]

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)

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

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.

+        if (absoluteVisibleRect.contains(childRect))
+            break;
+        child = child->nextInPreOrder(scrollerBox);
+    }
+    return candidate;
 }
 
 static DoublePoint computeRelativeOffset(const ScrollableArea* scroller, const LayoutObject* layoutObject)
 {
-    // TODO(skobes): implement.
-    return DoublePoint();
+    return DoublePoint(layoutObject->localToAbsolute() - scrollerLayoutBox(scroller)->localToAbsolute());
 }
 
 void ScrollAnchor::save()