Bug 49382 – Spatial Navigation: issues with the node selection algorithm.

• Component: Accessibility
• Status: RESOLVED FIXED

[Yael]

A few issues were found in the spatial navigation algorithm.
1. When no node is focused, we use tab-index to determine which node to focus. That causes a problem because not all focusable elements have tab-index attribute, so we would skip them.
2. When a frame or scrollable container do not have visible focusable elements, but can scroll, they should scroll to reveal the rest of its content.
3. z-index is not taken into account.
4. If an element will become visible after the container scrolls, it should be focused without an additional click on the arrow key.

[Yael]

Created attachment 73612 [details]
Patch

Modify the Spatial Navigation algorithm, to better handle initial focus and navigation between frames. The new algorithm takes the rect of the focused node as the startingRect, instead of the node itself. That allows us to construct a virtual rect if there is no focused node, or if it is off the screen. The virtual rect is the edge of the container in the direction of the navigation.

With this patch, scrollable containers and frames will scroll regardless of weather they have focusable content. Users will be able to use arrow keys to view all the content of such a container. The only exception is if the container has style overflow:hidden. We will not scroll in that case.

With this patch, we handle z-index and positioning so that if there are 2 overlapping focusable nodes, we do a hit test and only the node on top can get focus.

hasOffScreenRect() was modified so that it can check if a node will be off-screen even after we scrolled its parent container.

For better readability of the patch, we only modified existing layout tests, to ensure that they pass. We will add the new layout tests in future revisions of the patch.
For better readability, we also we preferred creating new functions instead of modifying existing, so that things can be reviewed in better context. A future patch will clean-up code that is no longer used.

[Yael]

*** Bug 47170 has been marked as a duplicate of this bug. ***

[Yael]

*** Bug 47176 has been marked as a duplicate of this bug. ***

[Yael]

*** Bug 47266 has been marked as a duplicate of this bug. ***

[Yael]

Created attachment 73614 [details]
Patch

Forgot to check style before uploading the patch.

[Early Warning System Bot]

Attachment 73614 [details] did not build on qt:
Build output: http://queues.webkit.org/results/5535100

[Eric Seidel (no email)]

Attachment 73612 [details] did not build on mac:
Build output: http://queues.webkit.org/results/5630017

[Yael]

Created attachment 73617 [details]
Patch

Fix build warnings.

[Eric Seidel (no email)]

Attachment 73617 [details] did not build on mac:
Build output: http://queues.webkit.org/results/5489101

[Eric Seidel (no email)]

Attachment 73614 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/5559098

[Yael]

Created attachment 73627 [details]
Patch

Attempt to fix the mac build.

[Eric Seidel (no email)]

Attachment 73627 [details] did not build on mac:
Build output: http://queues.webkit.org/results/5473109

[Yael]

Created attachment 73639 [details]
Patch

Another attempt to fix the mac build. It is not failing on my Snow Leopard machine, so I can only guess :-)

[Yael]

Created attachment 73729 [details]
Patch including code and no tests

This patch is the same as previous, but without the layout tests. I just wanted to make it smaller and hopefully easier for reviewers to handle :-)

[Antonio Gomes]

Lets do it this way:

1) Put the patch w/out tests up for review.
2) Make the patch only with the tests, and put it up for review.
3) Then we review the code clean up in bug 49442.

They will get reviewed separately, but will get squashed altogether before landing.

[Antonio Gomes]

Comment on attachment 73729 [details]
Patch including code and no tests

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

Nice work! 

It needs one more round, though. I would like to get some of my comments addressed and questions answered.

> WebCore/page/SpatialNavigation.cpp:291
> +        return curRect.x() < targetRect.right() || curRect.x() - targetRect.right() > viewSize.width();

"curRect.x() < targetRect.right()". This should not be tested here OR the method has to be renamed. iirc there were other methods that would catch these cases.

areRectsTooFarApart essentially test the second conditions e.g. "curRect.x() - targetRect.right() > viewSize.width();"

> WebCore/page/SpatialNavigation.cpp:293
> +        return targetRect.x() < curRect.right() || targetRect.x() - curRect.right() > viewSize.width();

ditto

> WebCore/page/SpatialNavigation.cpp:295
> +        return curRect.y() < targetRect.bottom() || curRect.y() - targetRect.bottom() > viewSize.height();

ditto

> WebCore/page/SpatialNavigation.cpp:297
> +        return targetRect.y() < curRect.bottom() || targetRect.y() - curRect.bottom() > viewSize.height();

ditto

> WebCore/page/SpatialNavigation.cpp:524
> +bool scrollInDirection(Node* container, FocusDirection direction, const FocusCandidate&)

I wish, if possible you keep using the enclosingScrollableBox logic in FocusCandidate.

That way you should just do

scrollInDirection(direction, focusCandidate);

focuscandidate would have a reference for the 'container' node.

> WebCore/page/SpatialNavigation.cpp:653
> +Node* scrollableOrFrameParentForNodeAndDirection(FocusDirection direction, Node* node)

FocusCandidate POD has a enclosingScrollableBox. Why not using this?

> WebCore/page/SpatialNavigation.cpp:659
> +        if (parent->isDocumentNode())
> +            parent = static_cast<Document*>(parent)->document()->frame()->ownerElement();

put a 'break' right below here, and remove the isDocumentNode check from the loop condition.

> WebCore/page/SpatialNavigation.cpp:673
> +    if (!container->renderBox() || !container->renderBox()->canBeScrolledAndHasScrollableArea())
> +        return false;

why not use isScrollableContainerNode() ?

> WebCore/page/SpatialNavigation.cpp:695
> +    if ((direction == FocusDirectionLeft || direction == FocusDirectionRight) && !frame->view()->horizontalScrollbar())
> +        return false;

Will it work with scrollbar policy thing of the Qt API? It is toggled OFF for WRT.

> WebCore/page/SpatialNavigation.cpp:717
> +IntRect nodeRectInAbsCoords(Node* node, bool ignoreBorder)

Abs => Absolute

> WebCore/page/SpatialNavigation.cpp:732
> +    for (Frame* frame = node->document()->frame(); frame; frame = frame->tree()->parent()) {
> +        if (Element* element = static_cast<Element*>(frame->ownerElement())) {
> +            do {
> +                rect.move(element->offsetLeft(), element->offsetTop());
> +            } while ((element = element->offsetParent()));
> +            rect.move((-frame->view()->scrollOffset()));
> +        }
> +    }

This steps are duplicated here and in frameRectInAbsCoords. Lets make it a helper.

> WebCore/page/SpatialNavigation.cpp:734
> +    // For authors that use border indtead of outline in their CSS, we compensate by ignoring the border when calculating

typo: inStead

> WebCore/page/SpatialNavigation.cpp:744
> +IntRect frameRectInAbsCoords(Frame* frame)

Abs -> Absolute.

> WebCore/page/SpatialNavigation.cpp:755
> +    for (; frame; frame = frame->tree()->parent()) {
> +        if (Element* element = static_cast<Element*>(frame->ownerElement())) {
> +            do {
> +                rect.move(element->offsetLeft(), element->offsetTop());
> +            } while ((element = element->offsetParent()));
> +            rect.move((-frame->view()->scrollOffset()));
> +        }
> +    }

Duplicated code.

> WebCore/page/SpatialNavigation.cpp:816
> +void distanceDataForNode(FocusDirection direction, const IntRect& startingRect, FocusCandidate& candidate)

In my opinion,the signature of this method is inconsistent: you should be either pass the direction and both nodes OR the direction and both rects.

Maybe we need this first, where "startingNode" would be "FocusCandidate focusedNode". If there is not current focused not, focusedNode.isNull() would catch it and then you get your wanted starting rect from within this method.

[Yael]

(In reply to comment #16)
Thank you for the review, my comments are below. 

> > WebCore/page/SpatialNavigation.cpp:291
> > +        return curRect.x() < targetRect.right() || curRect.x() - targetRect.right() > viewSize.width();
> 
> "curRect.x() < targetRect.right()". This should not be tested here OR the method has to be renamed. iirc there were other methods that would catch these cases.
 
I will rename the method to reflect the fact that we do not want to select elements that are more than a full screen away. 
There is no other place that this is checked. If I remove this, and there is an element in full alignment, we will scroll all the way down to it, and will refuse any other element that is closer, but not in full alignment.

> > WebCore/page/SpatialNavigation.cpp:524
> > +bool scrollInDirection(Node* container, FocusDirection direction, const FocusCandidate&)
> 
> I wish, if possible you keep using the enclosingScrollableBox logic in FocusCandidate.
> 
Good idea, I will change FocusCandidate to include all the necessary information.

> > WebCore/page/SpatialNavigation.cpp:653
> > +Node* scrollableOrFrameParentForNodeAndDirection(FocusDirection direction, Node* node)
> 
> FocusCandidate POD has a enclosingScrollableBox. Why not using this?

This is used during the initialization, before we have a FocusCandidate.

 
> > WebCore/page/SpatialNavigation.cpp:659
> > +        if (parent->isDocumentNode())
> > +            parent = static_cast<Document*>(parent)->document()->frame()->ownerElement();
> 
> put a 'break' right below here, and remove the isDocumentNode check from the loop condition.
> 
Cannot do that:-) The check you are looking at is for the _current_ node, if we start from a document node, we want to ignore it and keep going up the parent tree. I will add a comment to explain that better.

> 
> > WebCore/page/SpatialNavigation.cpp:695
> > +    if ((direction == FocusDirectionLeft || direction == FocusDirectionRight) && !frame->view()->horizontalScrollbar())
> > +        return false;
> 
> Will it work with scrollbar policy thing of the Qt API? It is toggled OFF for WRT.
In my Symbian build of WRT there are scrollbars, I need to check what is going on :-) 

> 
> > WebCore/page/SpatialNavigation.cpp:816
> > +void distanceDataForNode(FocusDirection direction, const IntRect& startingRect, FocusCandidate& candidate)
> 
> In my opinion,the signature of this method is inconsistent: you should be either pass the direction and both nodes OR the direction and both rects.
> 
> Maybe we need this first, where "startingNode" would be "FocusCandidate focusedNode". If there is not current focused not, focusedNode.isNull() would catch it and then you get your wanted starting rect from within this method.
ok

I found a problem with the way I am detecting divs with overflow:hidden, so I will fix that before submitting a new patch.

[Yael]

Created attachment 73954 [details]
Patch - code only

This patch addresses comment #16. Due to the size of the patch it contains only code changes, the tests changes are coming soon.

[Yael]

Created attachment 73955 [details]
Patch - tests changes only.

This patch contains test changes only, they were split from https://bugs.webkit.org/attachment.cgi?id=73954&action=edit.

[Antonio Gomes]

Comment on attachment 73954 [details]
Patch - code only

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

Great! ... but we are still missing some stuff. One more batch needed.

> WebCore/page/FocusController.cpp:783
> +            rect = nodeRectInAbsoluteCoordinates(focusedNode, true);

Add a comment here explaining the bool.

rect = nodeRectInAbsoluteCoordinates(focusedNode, true /* ignore border */);

> WebCore/page/FocusController.cpp:817
> +bool FocusController::navigateIn4WayDirection(FocusDirection direction, KeyboardEvent* event)

I would really like a better name here. Why not keep the previous name?

> WebCore/page/FocusController.cpp:833
> +        container = scrollableOrFrameParentForNodeAndDirection(direction, focusedNode);
> +        startingRect = nodeRectInAbsoluteCoordinates(focusedNode, true);

On IRC we talked about renamed FocusableCandidate to FocusableContent. It would have an additional IntRect, and Node could be 0. The 'container' above would be the FocusableContent::scrollableEnclosingNode. Does it make sense to implement, so it all gets consistent?

ps: Add a comment explaining the bool here too.

> WebCore/page/FocusController.cpp:836
> +    bool consumed = false;

what is consumed?

> WebCore/page/FocusController.cpp:841
> +        startingRect = nodeRectInAbsoluteCoordinates(container, true);

Comment for the bool.

> WebCore/page/FocusController.cpp:844
> +    } while (!consumed && container);
> +    return consumed;

Add a line between these two.

> WebCore/page/SpatialNavigation.cpp:64
> +    , rect(nodeRectInAbsoluteCoordinates(n, true))

Please add a "/* */" comment explaining the bool.

> WebCore/page/SpatialNavigation.cpp:301
> +{

Could you consider making use of isRectInDirection() all over this method, instead of "curRect.x() < targetRect.right()" , "targetRect.x() < curRect.right()"...

It made practical results better for me, back on time.

> WebCore/page/SpatialNavigation.cpp:494
> +    default:
> +        break;
> +    }

Add an assert_not_reached here, and return :)

> WebCore/page/SpatialNavigation.cpp:528
> +            ASSERT_NOT_REACHED();

add a 'return' here as well.

> WebCore/page/SpatialNavigation.cpp:564
> +            ASSERT_NOT_REACHED();

'return' here too.

> WebCore/page/SpatialNavigation.cpp:569
> +
> +        return true;

Remove this empty line.

> WebCore/page/SpatialNavigation.cpp:667
> +        if (parent->isDocumentNode()) // This is true only if node is a document node.

I would remove this comment.

> WebCore/page/SpatialNavigation.cpp:672
> +            parent = parent->parentNode();
> +    } while (parent && !canScrollInDirection(direction, parent) && !parent->isDocumentNode());
> +    return parent;

Empty line between this two.

> WebCore/page/SpatialNavigation.cpp:705
> +    frame->view()->calculateScrollbarModesForLayout(horizontalMode, verticalMode);

Maybe FrameView::calculateScrollbarModesForLayout does not consider the case when Webkit side disabled the scrollbars? See ScrollView::scrollbarModes()...

> WebCore/page/SpatialNavigation.cpp:788
> +        ASSERT_NOT_REACHED();

'return' here too.

> WebCore/page/SpatialNavigation.cpp:848
> +    switch (direction) {
> +    case FocusDirectionLeft:
> +        if (nodeRect.right() > currentRect.x())
> +            return;
> +        break;
> +    case FocusDirectionUp:
> +        if (nodeRect.bottom() > currentRect.y())
> +            return;
> +        break;
> +    case FocusDirectionRight:
> +        if (nodeRect.x() < currentRect.right())
> +            return;
> +        break;
> +    case FocusDirectionDown:
> +        if (nodeRect.y() < currentRect.bottom())
> +            return;

are not you doing these checks in areRectsMoreThanFullScreenApart?

> WebCore/page/SpatialNavigation.cpp:851
> +        ASSERT_NOT_REACHED();

return here.

> WebCore/page/SpatialNavigation.cpp:857
> +    int sameAxisDist = 0;
> +    int otherAxisDist = 0;

Lets spell out 'Dist'.

> WebCore/page/SpatialNavigation.cpp:898
> +    IntRect candidateRect = nodeRectInAbsoluteCoordinates(candidate.node);

do not need to do this. Just use candidate.rect ?

[Antonio Gomes]

Comment on attachment 73955 [details]
Patch - tests changes only.

Yay!

[Yael]

(In reply to comment #20)
Thanks for reviewing at 1:30 in the morning :-) A new patch is coming as soon as I am done compiling and running some tests. 

> > WebCore/page/FocusController.cpp:817
> > +bool FocusController::navigateIn4WayDirection(FocusDirection direction, KeyboardEvent* event)
> 
> I would really like a better name here. Why not keep the previous name?
I like the old name better too :-)
 
> > WebCore/page/FocusController.cpp:833
> > +        container = scrollableOrFrameParentForNodeAndDirection(direction, focusedNode);
> > +        startingRect = nodeRectInAbsoluteCoordinates(focusedNode, true);
> 
> On IRC we talked about renamed FocusableCandidate to FocusableContent. It would have an additional IntRect, and Node could be 0. The 'container' above would be the FocusableContent::scrollableEnclosingNode. Does it make sense to implement, so it all gets consistent?

I did add a IntRect to FocusCandidate. The code you are pointing at is the initialization of the currently focused node, before we have a focus candidate. I kind of like the existing logic where we have a FocusCandidate, and a "contender" FocusCandidate. Do you really think we should wrap the currently focused node and its container with a FocusCandidate? That will break the current logic.
 
> > WebCore/page/FocusController.cpp:836
> > +    bool consumed = false;
> 
> what is consumed?
The keyboard event. If we move focus or scroll, we also consume the event. If we don't do any of those, we don't consume the keyboard event.

> > WebCore/page/SpatialNavigation.cpp:494
> > +    default:
> > +        break;
> > +    }
> 
> Add an assert_not_reached here, and return :)
> 
> > WebCore/page/SpatialNavigation.cpp:528
> > +            ASSERT_NOT_REACHED();
> 
> add a 'return' here as well.
Sometimes we call this without direction, mainly when we deal with overflow:hidden, and no scrolling is involved.

> 
> > WebCore/page/SpatialNavigation.cpp:569
> > +
> > +        return true;
> 
> Remove this empty line.
> 
> > WebCore/page/SpatialNavigation.cpp:667
> > +        if (parent->isDocumentNode()) // This is true only if node is a document node.
> 
> I would remove this comment.
> 
> > WebCore/page/SpatialNavigation.cpp:672
> > +            parent = parent->parentNode();
> > +    } while (parent && !canScrollInDirection(direction, parent) && !parent->isDocumentNode());
> > +    return parent;
> 
> Empty line between this two.
> 
> > WebCore/page/SpatialNavigation.cpp:705
> > +    frame->view()->calculateScrollbarModesForLayout(horizontalMode, verticalMode);
> 
> Maybe FrameView::calculateScrollbarModesForLayout does not consider the case when Webkit side disabled the scrollbars? See ScrollView::scrollbarModes()...
> 
During my testing I called the API to turn off scrollbars (hacked FrameLoaderClientQt to do that for every frame) and this gave the correct results.

> > WebCore/page/SpatialNavigation.cpp:848
> > +    switch (direction) {
> > +    case FocusDirectionLeft:
> > +        if (nodeRect.right() > currentRect.x())
> > +            return;
> > +        break;
> > +    case FocusDirectionUp:
> > +        if (nodeRect.bottom() > currentRect.y())
> > +            return;
> > +        break;
> > +    case FocusDirectionRight:
> > +        if (nodeRect.x() < currentRect.right())
> > +            return;
> > +        break;
> > +    case FocusDirectionDown:
> > +        if (nodeRect.y() < currentRect.bottom())
> > +            return;
> 
> are not you doing these checks in areRectsMoreThanFullScreenApart?
Sorry :-) Removed the check from areRectsMoreThanFullScreenApart() since this is done first.

> > WebCore/page/SpatialNavigation.cpp:898
> > +    IntRect candidateRect = nodeRectInAbsoluteCoordinates(candidate.node);
> 
> do not need to do this. Just use candidate.rect ?
Good catch.

One last comment, I tried using the middle point before started I using entry/exit points, and the results seem to not be as good as using entry/exit points. I'd like to not use middle point, so I modified isRectInDirection accordingly.

[Yael]

Created attachment 73990 [details]
Patch- code only

Address comment #20.
I will update the patch in https://bugs.webkit.org/show_bug.cgi?id=49442 once we finalize this, and commit them all together.

[Yael]

Created attachment 73991 [details]
Patch - code only

When will I learn to run check-webkit-style _before_ attaching a patch?

[WebKit Review Bot]

Attachment 73990 [details] did not pass style-queue:

Failed to run "['WebKitTools/Scripts/check-webkit-style', '--diff-files', u'WebCore/ChangeLog', u'WebCore/page/FocusController.cpp', u'WebCore/page/FocusController.h', u'WebCore/page/FrameView.h', u'WebCore/page/SpatialNavigation.cpp', u'WebCore/page/SpatialNavigation.h']" exit_code: 1
WebCore/page/SpatialNavigation.cpp:449:  Non-label code inside switch statements should be indented.  [whitespace/indent] [4]
Total errors found: 1 in 6 files


If any of these errors are false positives, please file a bug against check-webkit-style.

[Build Bot]

Attachment 73990 [details] did not build on win:
Build output: http://queues.webkit.org/results/6004088

[Build Bot]

Attachment 73991 [details] did not build on win:
Build output: http://queues.webkit.org/results/6012090

[Yael]

Created attachment 73993 [details]
Patch - code only

Build fix for windows.

[Antonio Gomes]

Comment on attachment 73993 [details]
Patch - code only

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

> WebCore/page/FocusController.cpp:638
> +        HitTestResult result = candidate.node->document()->page()->mainFrame()->eventHandler()->hitTestResultAtPoint(IntPoint(x, y), false, true);

page()->eventHandler()

> WebCore/page/FocusController.cpp:700
> +    // The starting rect is the rect of the focused node, in document coordinates.
> +    // Compose a virtual starting rect if there is no focused node or if it is off screen.
> +    // The virtual rect is the edge of the container or frame. We select which
> +    // edge depending on the direction of the navigation.
> +    IntRect newStartingRect = startingRect;
> +
> +    if (startingRect.isEmpty()) {
> +        newStartingRect = nodeRectInAbsoluteCoordinates(container);
> +        switch (direction) {
> +        case FocusDirectionLeft:
> +            newStartingRect.setX(newStartingRect.right());
> +            newStartingRect.setWidth(0);
> +            break;
> +        case FocusDirectionUp:
> +            newStartingRect.setY(newStartingRect.bottom());
> +            newStartingRect.setHeight(0);
> +            break;
> +        case FocusDirectionRight:
> +            newStartingRect.setWidth(0);
> +            break;
> +        case FocusDirectionDown:
> +            newStartingRect.setHeight(0);
> +            break;
> +        default:
> +            ASSERT_NOT_REACHED();
> +        }
> +    }

Make it a helper.

> WebCore/page/FocusController.cpp:709
> +    if (focusCandidate.isNull()) {
> +        if (canScrollInDirection(direction, container)) {
> +            // Nothing to focus, scroll if possible.
> +            scrollInDirection(container, direction);

Lets change the logic here as following:

if (focusCandidate.isNull()) {

  // Nothing to focus, scroll if possible.
  if (scrollInDirection)
  ...
}

From within scrollInDirection, you check canScrollInDirection, bailing out earlier if it can not. Adjust the following 'return' calls accordingly.

> WebCore/page/FocusController.cpp:719
> +        if (hasOffscreenRect(focusCandidate.node, direction)) {
> +            Frame* frame = focusCandidate.node->document()->view()->frame();
> +            scrollInDirection(frame->document(), direction);
> +            return true;

You have two scrollInDirection methods. Here you should just use the one that takes Frame*

Frame* frame = focusCandidate.node->document()->view()->frame();
scrollInDirection(frame, direction);
return true;

or make it:

Document* document = focusCandidate.node->document();
scrollInDirection(document, direction);
return true;

> WebCore/page/FocusController.cpp:725
> +        IntRect rect;
> +        Node* focusedNode = focusedOrMainFrame()->document()->focusedNode();
> +        if (focusedNode && !hasOffscreenRect(focusedNode))
> +            rect = nodeRectInAbsoluteCoordinates(focusedNode, true /* ignore border */);

what happens here if you have no focused node, so 'rect' is empty. Also 'rect' is a too generic name in this context. Lets give it a more descriptive name.

> WebCore/page/FocusController.cpp:726
> +        ASSERT(static_cast<HTMLFrameOwnerElement*>(focusCandidate.node)->contentFrame());

Move this assert to outside the outer if here. If FrameOwnerElement is not a contentFrame it just be no-op.

it should be 

if (focusCandidate.node->isFrameOwnerElement() && static_cast<HTMLFrameOwnerElement*>(focusableCandidate.node)->contentFrame())

> WebCore/page/FocusController.cpp:727
> +        static_cast<HTMLFrameOwnerElement*>(focusCandidate.node)->contentFrame()->document()->updateLayoutIgnorePendingStylesheets();

Why not just do 

focusCandidate.node->document()?

> WebCore/page/FocusController.cpp:728
> +        if (!navigateInContainer(static_cast<HTMLFrameOwnerElement*>(focusCandidate.node)->contentFrame()->document(), rect, direction, event))

Same here.

Also, let same "Document* focusedDocument = focusCandidate.node->document()" in a auxiliar variable to avoid make this cast so many times.

> WebCore/page/FocusController.cpp:729
> +            // The new frame had nothing interesting, skip past it and try again.

"skip past it" sounds strange.

Also put {} around the 'if' here.

> WebCore/page/FocusController.cpp:747
> +        scrollInDirection(container, direction);

you are ignoring the return value here. Should you?

> WebCore/page/FrameView.h:238
> +    void calculateScrollbarModesForLayout(ScrollbarMode& hMode, ScrollbarMode& vMode);

Your changelog should explain this change. Is this method designed to be public?

> WebCore/page/SpatialNavigation.cpp:491
> +    default:
> +        break;

It is not clear to me why you do not assert, and bail out. Could you explain?

> WebCore/page/SpatialNavigation.cpp:507
> +    ASSERT(frame && canScrollInDirection(direction, frame->document()));

you should be assert "canScrollInDirection" here. it should actually early return here.

> WebCore/page/SpatialNavigation.cpp:560
> +        switch (direction) {
> +        case FocusDirectionLeft:
> +            dx = - min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollLeft());
> +            break;
> +        case FocusDirectionRight:
> +            ASSERT(container->renderBox()->scrollWidth() > (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
> +            dx = min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollWidth() - (container->renderBox()->scrollLeft() + container->renderBox()->clientWidth()));
> +            break;
> +        case FocusDirectionUp:
> +            dy = - min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollTop());
> +            break;
> +        case FocusDirectionDown:
> +            ASSERT(container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));
> +            dy = min(Scrollbar::pixelsPerLineStep(), container->renderBox()->scrollHeight() - (container->renderBox()->scrollTop() + container->renderBox()->clientHeight()));

why do we need the minimal between the scrollable offset available and Scrollbar::pixelPerLineStep ?

Just do ScrollGranularity line, and the rest will be handled for you.

> WebCore/page/SpatialNavigation.cpp:567
> +        container->renderBox()->enclosingLayer()->scrollByRecursively(dx, dy);

Why not do page()->eventHandler()->scrollRecursively( ... , ..., node), where 'node' is the 'startingNode'. It does that enclosing layer does and more.

> WebCore/page/SpatialNavigation.cpp:628
> +bool isScrollableContainerNode(const Node* node)

why does it need to be const here and not in the other method we are passing a Node*?

> WebCore/page/SpatialNavigation.cpp:767
> +// Exit point is the closest point in the startingRect, depending on the direction of the navigation.
> +// Entry point is the closest point in the candidate node, depending on the direction of the navigation.

Lets rephrase this comment.

> WebCore/page/SpatialNavigation.h:133
> +Node* scrollableOrFrameParentForNodeAndDirection(FocusDirection, Node* node);

Lets name it either scrollableEnclosingBoxOrParentFrameForNodeInDirection or scrollableOrParentFrameForNodeInDirection

[Yael]

(In reply to comment #29)
> (From update of attachment 73993 [details])
Thank you for the review, Antonio. Your comments are very good feedback to me, but I would like to address a few comments here, and explain why things were done the way I did them.

I added ASSERTs in the code to make sure we never get "stuck". Some of the comments below will result in removing those ASSERTs, but I would really like to avoid that. If we get "stuck" in the algorithm, the user will press an arrow key and will get no feedback, which is a very frustrating situation. Please consider if we should really remove those ASSERTs.

I added code to control the scrolling very tightly. A suggestion below is to rely on existing API for scrolling, and not use my own code. The reason I did not do that is that there are cases in which the existing API was scroll the parent when that was not needed. The result was not pretty :-(

I tracked the unwanted scrolling to RenderLayer::scrollRectToVisible line 1487:
parentLayer->scrollRectToVisible(newRect, scrollToAnchor, alignX, alignY);
Sometimes it scrolls the parent unnecessarily. We could look at why it does that separately.

I will update the patch soon, and ask you to review again :-)

>> WebCore/page/FocusController.cpp:638
>> +        HitTestResult result = >candidate.node->document()->page()->mainFrame()->eventHandler()->hitTestResult>AtPoint(IntPoint(x, y), false, true);
>
>page()->eventHandler()
page does not have a eventHandler ?
 
> > WebCore/page/FocusController.cpp:709
> From within scrollInDirection, you check canScrollInDirection, bailing out earlier if it can not. Adjust the following 'return' calls accordingly.

Currently, I do not check if can scroll from inside scrollInDirection. There is an ASSERT there, to make sure scrollInDirection is called _ONLY_ if we can scroll. There is only one call site that calls canScrollInDirection before scrollInDirection. That happens only if we found nothing. If I make the change, I will loose the ASSERT, and that will allow bugs to creep, where if someone forgets to check return value, we think we scroll, but in effect we get "stuck". That will leave the user not knowing why the browser ignored his click.

> > WebCore/page/FocusController.cpp:725
> what happens here if you have no focused node, so 'rect' is empty. Also 'rect' is a too generic name in this context. Lets give it a more descriptive name.
Changed the name to "startingRect". If the startingRect is empty, we construct a virtual starting rect. 


> > WebCore/page/FocusController.cpp:727
> > +        static_cast<HTMLFrameOwnerElement*>(focusCandidate.node)->contentFrame()->document()->updateLayoutIgnorePendingStylesheets();
> 
> Why not just do 
> 
> focusCandidate.node->document()?

focusCandidate.node->document() returns the parent document of the iframe element, here I need the document inside the iframe itself.

> > WebCore/page/FocusController.cpp:729
> Also put {} around the 'if' here.
"Style police" does not allow that :-)

> > WebCore/page/FocusController.cpp:747
> > +        scrollInDirection(container, direction);
> 
> you are ignoring the return value here. Should you?
Yes. 
A scrollable container is considered in the algorithm only if it can scroll in the specific direction. Otherwise, it is treated like any non-scrollable node. I added the ASSERT in scrollInDirection to make sure that we keep the logic this way. So if the ASSERT was not hit, I can be sure that we scrolled.

> 
> > WebCore/page/FrameView.h:238
> > +    void calculateScrollbarModesForLayout(ScrollbarMode& hMode, ScrollbarMode& vMode);
> 
> Your changelog should explain this change. Is this method designed to be public?
I will explain this in the changelog.
This method knows if a frame can scroll, without taking the scrollMode API into account (we discussed this API on IRC). We really need a public method to tell us if we can scroll the frame or not, and this function is perfect for that purpose.

> > WebCore/page/SpatialNavigation.cpp:491
> > +    default:
> > +        break;
> 
> It is not clear to me why you do not assert, and bail out. Could you explain?
> 
We use this method for 2 different situations. (1) If the container of the node is scrollable, we pass the direction, and we want to know if the node will be offscreen after we scroll (if needed). (2) If the container has overflow:hidden,  we want to know if the node is offscreen without scrolling, because scrolling is not allowed.
I updated the comment to explain that.

> > WebCore/page/SpatialNavigation.cpp:507
> > +    ASSERT(frame && canScrollInDirection(direction, frame->document()));
> 
> you should be assert "canScrollInDirection" here. it should actually early return here.
See explanation above :-)

> > WebCore/page/SpatialNavigation.cpp:560
> 
> why do we need the minimal between the scrollable offset available and Scrollbar::pixelPerLineStep ?
> 
> Just do ScrollGranularity line, and the rest will be handled for you.
My testing showed unwanted scrolling of the parent container if I don't do that. 
 
> > WebCore/page/SpatialNavigation.cpp:567
> > +        container->renderBox()->enclosingLayer()->scrollByRecursively(dx, dy);
> 
> Why not do page()->eventHandler()->scrollRecursively( ... , ..., node), where 'node' is the 'startingNode'. It does that enclosing layer does and more.
Again, my testing show unwanted scrolling of the parent if I do that. We do not want the "more" that it gives :-) This is especially true in nested iframes.

> > WebCore/page/SpatialNavigation.cpp:628
> > +bool isScrollableContainerNode(const Node* node)
> 
> why does it need to be const here and not in the other method we are passing a Node*?
I tried to add const everywhere that the node is not modified. e.g. canScrollInDIrection does not modify the node, so it has a const Node*.
scrollInDirection does modify the node, so it does not have const. since canScrollInDirection calls isScrollableContainerNode, they need to be consistent or they won't compile.

[Yael]

Created attachment 74401 [details]
Patch - code only

Addressing comment #29.

[Antonio Gomes]

Comment on attachment 74401 [details]
Patch - code only

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

> WebCore/page/FocusController.cpp:712
> +        if (!navigateInContainer(frameElement->contentFrame()->document(), rect, direction, event))
> +            // The new frame had nothing interesting, need to find another candidate.
> +            return navigateInContainer(container, nodeRectInAbsoluteCoordinates(focusCandidate.node, true), direction, event);

Please lets fix this before landing :)

One-line control clauses should not use braces unless comments are included or a single statement spans multiple lines.
Right:

if (condition) {
    // Some comment
    doIt();
}

Wrong:

if (condition)
    // Some comment
    doIt();

[Yael]

Created attachment 74412 [details]
Patch - code only

Added the braces. check-webkit-style did not complain about them, sorry for getting confused about that.

[Yael]

Antonio,
besides the braces (I added them :), did you have more comments? thanks!

[Daniel Bates]

Comment on attachment 74412 [details]
Patch - code only

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

> WebCore/page/FocusController.cpp:606
> +void updateFocusCandidateIfNeeded(FocusDirection direction, const IntRect& startingRect, FocusCandidate& candidate, FocusCandidate& closest)

As far as I can tell, this function does not modify candidate. Can we make this const?

> WebCore/page/FocusController.cpp:609
> +    if (!candidate.node->isElementNode() ||!candidate.node->renderer())
> +        return;

Nit: There should be a space between '||' and "!candidate.node->renderer()". The style bot didn't seem to catch this, we should consider updating our style-checker code.

> WebCore/page/FocusController.cpp:668
> +    for (Node* node = container->firstChild(); node; node = (node->isFrameOwnerElement() || canScrollInDirection(direction, node)) ? node->traverseNextSibling(container) : node->traverseNextNode(container)) {
> +        if ((!focusedFrame() || !focusedFrame()->document() || node != focusedFrame()->document()->focusedNode()) && (node->isKeyboardFocusable(event) || node->isFrameOwnerElement() || canScrollInDirection(direction, node))) {
> +            if (!node->renderer())
> +                continue;
> +            FocusCandidate candidate(node);
> +            candidate.enclosingScrollableBox = container;
> +            updateFocusCandidateIfNeeded(direction, startingRect, candidate, closest);
> +        }
> +    }

It is a common convention to write code using early returns/continues/breaks so as to make the code easier to read and follow its flow control.

Additionally, it is unnecessary to re-compute the focused node (i.e. focusedFrame()->document()->focusedNode()) for each iteration. Instead, we should compute it once outside of the loop-body. Then I suggest we use an early continue for when "node == focusedFrame()->document()->focusedNode()". We can also further break down the if-condition into additional early continues.

Moreover, we should hoist the early-continue:

if (!node->renderer())
    continue;

out of the body for the if statement.

On another note, I wish we could simplify and/or shorten the step condition of the for-loop construct. Maybe, we should write this loop using the while-loop construct?

> WebCore/page/FocusController.cpp:713
> +        HTMLFrameOwnerElement* frameElement = static_cast<HTMLFrameOwnerElement*>(focusCandidate.node);
> +        // If we have an iframe without the src attribute, it will not have a contentFrame().
> +        // We should never consider such an iframe as a candidate.
> +        ASSERT(frameElement->contentFrame());
> +
> +        if (hasOffscreenRect(focusCandidate.node, direction)) {
> +            scrollInDirection(focusCandidate.node->document(), direction);
> +            return true;
> +        }
> +        // Navigate into a new frame.
> +        IntRect rect;
> +        Node* focusedNode = focusedOrMainFrame()->document()->focusedNode();
> +        if (focusedNode && !hasOffscreenRect(focusedNode))
> +            rect = nodeRectInAbsoluteCoordinates(focusedNode, true /* ignore border */);
> +        frameElement->contentFrame()->document()->updateLayoutIgnorePendingStylesheets();
> +        if (!navigateInContainer(frameElement->contentFrame()->document(), rect, direction, event)) {
> +            // The new frame had nothing interesting, need to find another candidate.
> +            return navigateInContainer(container, nodeRectInAbsoluteCoordinates(focusCandidate.node, true), direction, event);
> +        }

I am unclear from the ASSERT(frameElement->contentFrame()) and the comment above it whether it is possible for frameElement->contentFrame() to be null. In particular, the second sentence of the comment seems to imply it can happen in practice. So, it seems insufficient to only ASSERT here (which is only useful in a debug build) and subsequently dereference frameElement->contentFrame(), which could be a null pointer. Can frameElement->contentFrame() be null given the context?

> WebCore/page/FocusController.cpp:736
> +    // We found a new focus node, navigate to it.
> +    Element* element = static_cast<Element*>(focusCandidate.node);
> +    ASSERT(element);

I suggest we use toElement() (see Element.h) instead of explicitly performing the static_cast and null check here.

[Yael]

(In reply to comment #35)
Thanks for reviewing, Daniel!
I'll update the patch according to your recommendations, but wanted to explain the ASSERT you pointed out.
It is possible to have an iframe without a src attribute, and that will cause us to have a HTMLFrameOwnerElement without contentFrame().

However, I am handling this situation in the second if in updateFocusCandidateIfNeeded.
The ASSERT you saw is there to make sure that in the future, people will not change the code in a way that will cause us to select an empty iframe as the next focus element.
I hope I was able to explain this properly, if it is still not clear, I am happy to continue discussing this, here or on IRC.

[Yael]

(In reply to comment #35)
> (From update of attachment 74412 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=74412&action=review
> 
> > WebCore/page/FocusController.cpp:606
> > +void updateFocusCandidateIfNeeded(FocusDirection direction, const IntRect& startingRect, FocusCandidate& candidate, FocusCandidate& closest)
> 
> As far as I can tell, this function does not modify candidate. Can we make this const?
> 
Unfortunately, this causes a chain reaction that does not compile ATM. Mainly because we have 2 copies of the method distanceDataForNode, and that causes the compiler to not be able to convert FocusCandidate to const FocusCandidate.
If you don't mind, I will defer adding the const to https://bugs.webkit.org/show_bug.cgi?id=49442, in which I am removing code that becomes obsolete after this patch. I split it out because this patch is already huge :-)

[Yael]

Created attachment 74526 [details]
Patch - code only

Address comment #35

[Antonio Gomes]

Comment on attachment 74526 [details]
Patch - code only

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

> WebCore/ChangeLog:18
> +        content of such a container. The only exception is if the container has style overflow:hidden. 
> +        We will not scroll in that case.

It would be nice to have a test case for this case. I do not remember if you added it in the other bug.

> WebCore/ChangeLog:21
> +        With this patch, we handle z-index and positioning so that if there are 2 overlapping focusable nodes,
> +        we do a hit test and only the node on top can get focus.

Same here.

> WebCore/page/FocusController.cpp:679
> +bool FocusController::navigateInContainer(Node* container, const IntRect& startingRect, FocusDirection direction, KeyboardEvent* event)

advanceFocusDirectionallyInContainer?

> WebCore/page/FocusController.cpp:687
> +        newStartingRect = virtualStartingRectForDirection(direction, nodeRectInAbsoluteCoordinates(container));

Lets name it virtualRectForDirection.

> WebCore/page/SpatialNavigation.cpp:543
> +    if (!container->renderBox())

being a renderBox does not necessarily mean it is scrollable. Maybe

toRenderBox(container->renderer()) && toRenderBox(container->renderer())->canBeScrolledAndHasScrollableArea()

?

[Daniel Bates]

Comment on attachment 74526 [details]
Patch - code only

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

> WebCore/page/FocusController.cpp:670
> +        if (!(node->isKeyboardFocusable(event) || node->isFrameOwnerElement() || canScrollInDirection(direction, node)))

Nit: I would suggest pushing the negation through this expression. Then we can remove a pair of parentheses.

[Yael]

(In reply to comment #39)
Hi Antonio, thanks for reviewing (again :)

> (From update of attachment 74526 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=74526&action=review
> 
> > WebCore/ChangeLog:18
> > +        content of such a container. The only exception is if the container has style overflow:hidden. 
> > +        We will not scroll in that case.
> 
> It would be nice to have a test case for this case. I do not remember if you added it in the other bug.
> 
> > WebCore/ChangeLog:21
> > +        With this patch, we handle z-index and positioning so that if there are 2 overlapping focusable nodes,
> > +        we do a hit test and only the node on top can get focus.
> 
> Same here.
> 

The 2 tests that you are asking for were added in https://bugs.webkit.org/show_bug.cgi?id=49604. I will set the review flag for those tests after commiting the 2 patches from this bug.


> > WebCore/page/SpatialNavigation.cpp:543
> > +    if (!container->renderBox())
> 
> being a renderBox does not necessarily mean it is scrollable. Maybe
> 
> toRenderBox(container->renderer()) && toRenderBox(container->renderer())->canBeScrolledAndHasScrollableArea()
> 
> ?

I call canScrollInDirection() right bellow this line.

[Yael]

Committed r72522: <http://trac.webkit.org/changeset/72522>

[Yael]

(In reply to comment #35)
> (From update of attachment 74412 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=74412&action=review
> 
> > WebCore/page/FocusController.cpp:606
> > +void updateFocusCandidateIfNeeded(FocusDirection direction, const IntRect& startingRect, FocusCandidate& candidate, FocusCandidate& closest)
> 
> As far as I can tell, this function does not modify candidate. Can we make this const?

I misinterpreted the compile error I received when I tried to add the const. candidate actually is being modified in this function, inside the call to distanceDataForNode. Sorry for not explaining it correctly in the first place.

[Ademar Reis]

Revision r72522 cherry-picked into qtwebkit-2.1 with commit a55b974 <http://gitorious.org/webkit/qtwebkit/commit/a55b974>

[Ademar Reis]

(In reply to comment #44)
> Revision r72522 cherry-picked into qtwebkit-2.1 with commit a55b974 <http://gitorious.org/webkit/qtwebkit/commit/a55b974>

Had to revert it because it doesn't build in qtwebkit-2.1 (depends on changes from bug 48157). To apply it to qtwebkit-2.1 we'll need a backported patch. Sorry for the noise.

[Yael]

(In reply to comment #45)
> (In reply to comment #44)
> > Revision r72522 cherry-picked into qtwebkit-2.1 with commit a55b974 <http://gitorious.org/webkit/qtwebkit/commit/a55b974>
> 
> Had to revert it because it doesn't build in qtwebkit-2.1 (depends on changes from bug 48157). To apply it to qtwebkit-2.1 we'll need a backported patch. Sorry for the noise.

Can you replace FocusController.cpp line 744 
toElement(focusCandidate.node) with 
static_cast<Element*>(focusCandidate.node) ?

After that it should compile.

[Ademar Reis]

(In reply to comment #46)
> (In reply to comment #45)
> > (In reply to comment #44)
> > > Revision r72522 cherry-picked into qtwebkit-2.1 with commit a55b974 <http://gitorious.org/webkit/qtwebkit/commit/a55b974>
> > 
> > Had to revert it because it doesn't build in qtwebkit-2.1 (depends on changes from bug 48157). To apply it to qtwebkit-2.1 we'll need a backported patch. Sorry for the noise.
> 
> Can you replace FocusController.cpp line 744 
> toElement(focusCandidate.node) with 
> static_cast<Element*>(focusCandidate.node) ?
> 
> After that it should compile.

That's the trivial part. The complex part is the requirement of WebCore::FrameView::calculateScrollbarModesForLayout(), which is not on qtwebkit-2.1 (see bug 48157).

[Ademar Reis]

(In reply to comment #47)
> That's the trivial part. The complex part is the requirement of WebCore::FrameView::calculateScrollbarModesForLayout(), which is not on qtwebkit-2.1 (see bug 48157).

bug 48157, on the other hand requires the changes from bug 47285 and bug 29240... we all know where it ends :-(

That's of course the view of someone unexperienced with the codebase. I believe a backport of the original patch would be simpler and is the right thing to do (but I'm not the right person to do it at this point).

[Antonio Gomes]

There could be a patch backported to 2.1 that does not require all this chain of backporting.

Basically, it is because yael addressed a request I made about spatial navigation scrolling content even if the scrollbars were turned off by via QWebFrame API. We could live w/out this in 2.1.

[Ademar Reis]

(In reply to comment #49)
> There could be a patch backported to 2.1 that does not require all this chain of backporting.

Yep, that's exactly what I mean :)

[Yael]

Ademar, can you please take a look at http://gitorious.org/~yael/webkit/yaels-qtwebkit/commit/d7788b5e68b9a6909e4a6c545e4b233729921d38 ?
I ported this patch and https://bugs.webkit.org/show_bug.cgi?id=49442 to the webkit 2.1 branch.

[Ademar Reis]

(In reply to comment #51)
> Ademar, can you please take a look at http://gitorious.org/~yael/webkit/yaels-qtwebkit/commit/d7788b5e68b9a6909e4a6c545e4b233729921d38 ?
> I ported this patch and https://bugs.webkit.org/show_bug.cgi?id=49442 to the webkit 2.1 branch.

Great! I cherry-picked it (just ammended a more comprehensive git changelog) and pushed it to qtwebkit-2.1:

http://gitorious.org/webkit/qtwebkit/commit/0f2e0cc960f49a04e4bd86a7f36373697b660bda

[Yael]

Ossy told me that the patch I posted in gitorious caused 12 layout tests to fail. The patch at the following URL reverts a small part of the previous patch, and it should fix those 12 failures.

http://gitorious.org/webkit/yaels-qtwebkit/commit/00998cc63aeb9ed2e4d979797a8aefa604fa842b

Sorry for the trouble.

[Ademar Reis]

(In reply to comment #53)
> Ossy told me that the patch I posted in gitorious caused 12 layout tests to fail. The patch at the following URL reverts a small part of the previous patch, and it should fix those 12 failures.
> 
> http://gitorious.org/webkit/yaels-qtwebkit/commit/00998cc63aeb9ed2e4d979797a8aefa604fa842b
> 
> Sorry for the trouble.

Done: http://gitorious.org/webkit/qtwebkit/commit/e9227821f63dd1119ee5510e8336d40ef97ee75e