Bug 18662 – Extend keyboard navigation to allow directional navigation

• Status: CLOSED
• Resolution: FIXED
• Component: Accessibility

[Marco Barisione]

Currently it's possible to navigate through links and widgets using tab, shift-tab and enter. For accessibility and embedded devices it would be useful to allow the user to move to the link at the left/right/bottom/top of the current focused link, like on the gecko-based browser on the Nokia N810.

The keys should customisable by the app to allow better integration with hw keys on embedded devices.

[Marco Barisione]

This bug is not specific to the GTK port, so I'm changing the subject and component.

[Marco Barisione]

Created attachment 20923 [details]
Add directional navigation to WebCore

I set the review ? flag because I need a review and some help but the patch is not ready to be committed as is.

Some comments:
1) realLocation() is just an hack, I didn't find a better way to do it and atm it doesn't work with iframes. I tried with RenderObject::absolutePosition() but it returns the position of the block containing an <a>, not of the link itself.
2) I added new values to FocusDirection and then we have only one public method to move focus, but it just calls two different private methods based on the direction. Is it better to have 2 different public methods?

[Marco Barisione]

Created attachment 20924 [details]
Navigate through links using CTRL + arrow keys

This one is needed to test the previous patch, but I don't think it's the right solution because I would like to be able to configure the keys used for that.

[Adele Peterson]

quick comment- you don't need an extra check for tabIndex >=0, since that check is included in isKeyboardFocusable.

With these new functions, the tab order specified by tabindex will be ignored.  But maybe if you're using arrow keys to navigate, that's not important- is that right?

[Marco Barisione]

(In reply to comment #4)
> quick comment- you don't need an extra check for tabIndex >=0, since that check
> is included in isKeyboardFocusable.

I will fix it in the next version of the patch.

> With these new functions, the tab order specified by tabindex will be ignored. 
> But maybe if you're using arrow keys to navigate, that's not important- is that
> right?

Yes and the normal navigation using (SHIFT-)TAB will be still available without any change (so it will use tabindex).

[Eric Seidel (no email)]

How can we test this?  Who do we have who can review this well?

[Marco Barisione]

(In reply to comment #6)
> How can we test this?

The second patch allows to test this using CThttps://bugs.webkit.org/show_bug.cgi?id=18662RL+LEFT/RIGHT/UP/DOWN.
I'm not sure that hard coding these keys in WebCore is the best option but I don't know how to do that in another way.

[Marco Barisione]

Created attachment 22634 [details]
Add directional navigation to WebCore

Updated patch. You can test it with CTRL-LEFT/RIGHT/UP/DOWN.

The algorithm I use to select the closes link in a given direction is not perfect but seems to work better than the one used for instance by mozilla on the Nokia N810 Internet Tablets. The main problem with every algorithm is that the layout of a page is very different for the grid-like layouts normally used for user interfaces.

[Eric Seidel (no email)]

By "how do we test this" I mean, providing a html file which explained what keys to press to test, and the expected results, tried this in different combinations (like inside content editable, etc.) and again explained what the tester was supposed to see.

http://trac.webkit.org/browser/trunk/WebCore/manual-tests
is where such tests would go.

[Sam Weinig]

could this not be tested in DRT?

[Sam Weinig]

Comment on attachment 22634 [details]
Add directional navigation to WebCore

This is great patch.  I think for it to go in we really need a way platforms too choose whether to use this or not.  Perhaps it can go in Settings.  Some style issues follow.  r- for the platform choice issue for now.

         if (event->keyIdentifier() == "U+0009")
             defaultTabEventHandler(event);
+         else if (event->keyIdentifier() == "Down" || event->keyIdentifier() == "Up" ||
+                 event->keyIdentifier() == "Right" || event->keyIdentifier() == "Left")
+             defaultArrowEventHandler(event);

There are some whitespace issues here.

inline IntPoint realLocation(RenderObject* render)
inline int rectangleDistance(IntRect rect1, IntRect rect2)
inline int rectangleDistance(IntRect rect1, IntRect rect2)
inline bool isPointAboveAntiDiagonal(const IntPoint& rectPoint, const IntPoint& point)
inline bool isRectAboveMainDiagonal(const IntPoint& rectPoint, const IntRect& rect)
inline bool isRectBelowMainDiagonal(const IntPoint& rectPoint, const IntRect& rect)
inline bool isRectAboveAntiDiagonal(const IntPoint& rectPoint, const IntRect& rect)
inline bool isRectBelowAntiDiagonal(const IntPoint& rectPoint, const IntRect& rect)

These should all be marked static to get internal linkage if they are not inlined.

+            ASSERT(false);

This can be written as ASSERT_NOT_REACHED();

+class BestCandidate

This should be a struct,  

+{

{ should go on the first line

+public:
+    BestCandidate() : node(0), distance(INT_MAX) {}

We like to style this as 

BestCandidate()
    : node(0)
    , distance(numeric_limits<int>::max())
{
}

+    for (Node* candidate = document->firstChild(); candidate; candidate = candidate->traverseNextNode())
+        if (candidate->isFrameOwnerElement()) {

The for loop should have braces.

+    Node* focusedNode = focusedDocument->focusedNode();
+    if (!focusedNode)
+        // Just move to the first focusable node.
+        // initialFocus is set to true so the chrome is not focused.
+        return advanceFocusLinear(FocusDirectionForward, event, true);

This if should have braces.  Our rule is that if there is more than one line (code or comments) we use braces. 

+    if (!node)
+      // Leave the focus on the same node.
+      return true;

Here too.

+    if (!node->isElementNode())
+        // FIXME: May need a way to focus a document here.
+        return false;

And here.

[Antonio Gomes]

Created attachment 26291 [details]
Add directional navigation to WebCore (v3)

+ addressed all sam's suggestions in comment #11 (https://bugs.webkit.org/show_bug.cgi?id=18662#c11)

+ added Settings support, so no need to set CONTROL as a modifier, IMO (although modifiers as mozilla's snav has would be good).

ps: in order to locally test the feature I set 'F12' as the toggle ON/OFF for the keyboard-navigation/scrolling.

[Antonio Gomes]

Comment on attachment 26291 [details]
Add directional navigation to WebCore (v3)

carry sam's review

ps: btw, it worths to say that the core of the patch is the same as the previous ones. I just addressed reviewer comments.

[Simon Fraser (smfr)]

The realLocation() function should just call localToAbsolute(), and the code needs to do something useful with transforms. Consider just using absoluteClippedOverflowRect().

[Darin Adler]

There seems to be some overlap between this and bug 22935.

[Darin Adler]

Oops, sorry, wrong bug number. That one is about directional navigation, but not the one I was thinking of.

[Darin Adler]

There seems to be some overlap between this and bug 22740.

[Antonio Gomes]

(In reply to comment #14)
> The realLocation() function should just call localToAbsolute(), and the code
> needs to do something useful with transforms. 

humm .. not really. Option below works better.

> Consider just using absoluteClippedOverflowRect().

absoluteClippedOverflowRect() can do the work realLocation does fine, however  both do not take frames under consideration: the position of nodes inside frames are relatives to the frame not to the outermost document. is there a good way to get the absolute position of a node (relative to the outermost document always) in a webpage ? if not, I can handle it by my own.

[Antonio Gomes]

Created attachment 26499 [details]
Add directional navigation to WebCore (v4)

Same patch as in comment #12 + recursive support to frames / iframes , and name in it.

It also uses absoluteClippedOverflowRect() as per Simon's suggetion.

[Darin Adler]

Comment on attachment 26499 [details]
Add directional navigation to WebCore (v4)

I like the general direction this is going in.

I do see many problems, though.

It's critical that the patch include test cases, not just code changes. And a change log entry.

> +        else if (event->keyIdentifier() == "Down"
> +                 || event->keyIdentifier() == "Up"
> +                 || event->keyIdentifier() == "Right"
> +                 || event->keyIdentifier() == "Left") {

This list is long enough that I think we should make a helper function isArrowKey that takes either a key identifier or a KeyboardEvent*. Maybe it could also return the focus direction so you don't have to repeat the list of key identifiers.

> +            if(m_frame->page()) {
> +                if (!m_frame->settings())
> +                    return;
> +                if(m_frame->settings()->enableKeyboardNavigation()) {
> +                    defaultArrowEventHandler(event);
> +                }
> +            }

The page and settings checks checks should be moved inside defaultArrowEventHandler; in fact, the check for a page of 0 is already in there.

Also, need a space after the if statement.

> +    if (!page->tabKeyCyclesThroughElements())
> +        return;

What's this tab check check for? That seems like a copy and paste error. And if not, needs a comment to explain it.

> +    // FIXME: Are CTRL-arrow keys needed in design mode?
> +    if (m_frame->document()->inDesignMode())
> +        return;

It seems wrong to check design mode specifically here. I think the check you want is about whether the document has editable text, or whether the insertion point is inside editable text or if not, if the entire document is editable. Despite its name that seems to imply otherwise, design mode is just one of many ways to make a document or part of a document editable.

> +inline static IntRect absoluteRenderRect(RenderObject* render)

We almost always order it as "static inline" rather than "inline static".

> +{
> +    ASSERT(render);
> +    // FIXME: consider 'transforms' ?

Not sure why you put the word transforms in quotes. You should use more normal formatting here and write something less uncertain:

    // FIXME: This function is flawed because it doesn't consider the effects of CSS or SVG transforms.

> +    // handle nested frames.
> +    if (Frame* frame = render->document()->frame()) {
> +        while (frame) {
> +            HTMLFrameOwnerElement* ownerElement = frame->ownerElement();
> +            if(Node* node = static_cast<Node*>(ownerElement))
> +                rect.move(node->renderer()->offsetLeft(), node->renderer()->offsetTop());
> +
> +            frame = frame->tree()->parent();
> +        }
> +    }

This checks frame for null twice. Since you have the while you don't also need the if. Also, that while should be written as a for statement. And the inner if statement should be checking ownerElement for 0, not a separate node variable. There's no reason to copy the ownerElement into a Node*; you can call the functions directly on the HTMLFrameOwnerElement.

It's not correct to use the offsetLeft and offsetTop of the frame owner element's renderer because that's just the distance from the offsetParent, not the absolute position. Instead you should use one of the localToAbsolute family of functions for this.

> +inline static int rectangleDistance(IntRect rect1, IntRect rect2)

These should be const IntRect& -- we don't want to copy them.

I think the title should say "distance squared" rather than just "distance".

I think there may be excessive use of "inline" here. It might be making the code bigger and slower than it needs to be.

The code should to be written so that overflow doesn't make extremely distant elements seems to be very close. That might have to start with a rectangleDistance function that can handle overflow.

We want test cases that try to put elements at very far-away positions to see if overflow gives us the wrong result.

> +inline static bool isRectAboveMainDiagonal(const IntPoint& rectPoint, const IntRect& rect)

I don't understand the name "rectPoint" for this point. What's a "rectangle point"?

> +    // Check if some points belonging to rect are above the y = x + c line passing for rectPoint.

Passing "for"? Do you mean "passing through"?

> +    return (isPointAboveMainDiagonal(rectPoint, rect.location())
> +            || isPointAboveMainDiagonal(rectPoint, IntPoint(rect.right(), rect.y()))
> +            || isPointAboveMainDiagonal(rectPoint, IntPoint(rect.x(), rect.bottom()))
> +            || isPointAboveMainDiagonal(rectPoint, IntPoint(rect.right(), rect.bottom())));

No need for the parentheses here in this expression.

If it wasn't for the brokenness of those functions, I would have suggested you use the named functions like bottomLeft() and bottomRight(). But they're broken in design, so I won't suggest you use them here unless someone fixes them and converts the old callers.

> +inline static bool isRectAboveAntiDiagonal(const IntPoint& rectPoint, const IntRect& rect)

I believe antidiagonal is one word, so the "D" should not be capitalized.

> +static int distanceInDirection(Node* start, Node* dest, FocusDirection direction)

> +    // The bounding rectangle of two consecutive links could overlap, so we decrease the size of
> +    // both rectangles.
> +    // FIXME: Is there a better way to do this?
> +    startRect.inflate(-4);
> +    destRect.inflate(-4);

The comment needs to indicate where the constant 4 comes from. Why is 4 good enough? Why not 3 or 5?

And we need a test case in the regression tests directory that demonstrates that 4 is a good choice.

> +        , distance(std::numeric_limits<int>::max())

Should do "using namespace std" at the top of the file and not say "std::" here.

Also, this code uses both INT_MAX and numeric_limits<int>::max() in the same algorithm. Lets chose one or the other.

> +        } else if (candidate != start && candidate->isKeyboardFocusable(event) && candidate->tabIndex() >= 0) {

Why the explicit check for tabIndex() here? That seems like it should be the responsibility of isKeyboardFocusable? Is there any special reason you're ruling out items that have a negative tab index? If so, I think you need a comment and if the rule really needs to be different than isKeyboardFocusable then it should be encapsulated in a function like isDirectionallyFocusable (or some better name).

We need a test demonstrating and double-checking which elements are and are not focusable with directional navigation.

> +bool FocusController::advanceFocusDirectional(FocusDirection direction, KeyboardEvent* event, bool initialFocus)

The name isn't great here because "advance focus directional" is not good grammar. Even advanceFocusDirectionally would be slightly better, but it's not a good name either because "forwards" and "backwards" seem like directions to me. Maybe advanceFocusGeometrically? You should think about what you'd call this in conversation and see if you can convert that into a name.

The meaning of the initialFocus argument is quite unclear.

It would be better if the algorithm was expressed in terms of Element* rather than Node* from top to bottom. I'd rather see that handled right when we go from the renderer to its node, rather than higher up.

> +bool FocusController::advanceFocusLinear(FocusDirection direction, KeyboardEvent* event, bool initialFocus)

This is not a good name. Moving forward and backward through the document is not "linear" -- it doesn't go along a line. I'd suggest advanceFocusInDocumentOrder perhaps.

> +    , m_enableKeyboardNavigation(false)

Unfortunately, "keyboard navigation" already has a meaning, especially to the visually impaired, and I don't believe it has anything to do with using arrow keys to move between elements based on their geometric position. We need a name that's more specific to what this feature is.

I'm not sure I like the idea of coding in the key bindings to the arrow keys. But since, for good or bad, that's what this turns on and off, the name could be shouldUseArrowKeysForDirectionalNavigation or something along those lines.

I think we should consider exposing the directional navigation to JavaScript somehow, so we can test it even in a browser that has the end-user binding turned off.

Something like commands for execCommand, but maybe not that because there could be compatibility consequences of adding something there.

[Darin Adler]

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

[Antonio Gomes]

Darin. Thank you the the nice review. Please comments quoted below.

> It's critical that the patch include test cases, not just code changes. And a
> change log entry.

I thought of the following tests:

* table traverse.
* test page w/ many iframes, nested probably.
* page w/ disabled html elements (which should not get focused).
* form integration (not supported in the current patch).
* elements far away from each other, to test the int overflow Darin mentioned in rectangleDistance method.
* testcase varying the inflate value (currently hardcoded as -4).

What do you think ? I will work on it.

> > +        else if (event->keyIdentifier() == "Down"
> > +                 || event->keyIdentifier() == "Up"
> > +                 || event->keyIdentifier() == "Right"
> > +                 || event->keyIdentifier() == "Left") {

> This list is long enough that I think we should make a helper function
> isArrowKey that takes either a key identifier or a KeyboardEvent*. Maybe it
> could also return the focus direction so you don't have to repeat the list of
> key identifiers.

right. helper method added:

FocusDirection EventHandler::isArrowKey(const String& keyIdentifier)

> > +            if(m_frame->page()) {
> > +                if (!m_frame->settings())
> > +                    return;
> > +                if(m_frame->settings()->enableKeyboardNavigation()) {
> > +                    defaultArrowEventHandler(event);
> > +                }
> > +            }
> 
> The page and settings checks checks should be moved inside
> defaultArrowEventHandler; in fact, the check for a page of 0 is already in
> there.

done.

> > +    if (!page->tabKeyCyclesThroughElements())
> > +        return;
> 
> What's this tab check check for? That seems like a copy and paste error. And if
> not, needs a comment to explain it.

yeah, copy and paste error. removed.

> > +    // FIXME: Are CTRL-arrow keys needed in design mode?
> > +    if (m_frame->document()->inDesignMode())
> > +        return;
> 
> It seems wrong to check design mode specifically here. I think the check you
> want is about whether the document has editable text, or whether the insertion
> point is inside editable text or if not, if the entire document is editable.
> Despite its name that seems to imply otherwise, design mode is just one of many
> ways to make a document or part of a document editable.

Darin, do you have cases when inDesignMode is true ? rich email compose mode in gmail ?

> > +inline static IntRect absoluteRenderRect(RenderObject* render)
> 
> We almost always order it as "static inline" rather than "inline static".

changed.

> > +{
> > +    ASSERT(render);
> > +    // FIXME: consider 'transforms' 
> Not sure why you put the word transforms in quotes. You should use more normal
> formatting here and write something less uncertain:
>     // FIXME: This function is flawed because it doesn't consider the effects
> of CSS or SVG transforms.

changed.

> > +    // handle nested frames.
> > +    if (Frame* frame = render->document()->frame()) {
> > +        while (frame) {
> > +            HTMLFrameOwnerElement* ownerElement = frame->ownerElement();
> > +            if(Node* node = static_cast<Node*>(ownerElement))
> > +                rect.move(node->renderer()->offsetLeft(), node->renderer()->offsetTop());
> > +
> > +            frame = frame->tree()->parent();
> > +        }
> > +    }
> 
> This checks frame for null twice. Since you have the while you don't also need
> the if. Also, that while should be written as a for statement. And the inner if
> statement should be checking ownerElement for 0, not a separate node variable.
> There's no reason to copy the ownerElement into a Node*; you can call the
> functions directly on the HTMLFrameOwnerElement.

fixed all.

> It's not correct to use the offsetLeft and offsetTop of the frame owner
> element's renderer because that's just the distance from the offsetParent, not
> the absolute position. Instead you should use one of the localToAbsolute family
> of functions for this.

that is what is hapenning here:

IntRect rect(render->absoluteClippedOverflowRect());

does get the position of the current node (referred by render in the method) in the Frame it is in.

later, if it node is inside an iframe or a html frame document, we walk up in the frame tree to get the position of the current html (i)frame relative to its parent document and move the rect accordingly. it does such for nested frame until we pick outer document. The offset is absolute.

I tried to use localToAbsolute(), however it was getting me the wrong absolute position values. maybe I am passing wrong parameter ... actually I am not passing any parameter to it. Should that be called ?

> > +inline static int rectangleDistance(IntRect rect1, IntRect rect2)
> 
> These should be const IntRect& -- we don't want to copy them.

fixed.

> I think the title should say "distance squared" rather than just "distance".

humm .. the square operation in the method refers to the rectangle distance formula. Does the method have to be named according to how it is implemented ?


> The code should to be written so that overflow doesn't make extremely distant
> elements seems to be very close. That might have to start with a
> rectangleDistance function that can handle overflow.

would using 'long' avoid any overflow here ?

> We want test cases that try to put elements at very far-away positions to see
> if overflow gives us the wrong result.

I will add that test. ok.

> > +inline static bool isRectAboveMainDiagonal(const IntPoint& rectPoint, const IntRect& rect)
> 
> I don't understand the name "rectPoint" for this point. What's a "rectangle
> point"?
> 
> > +    // Check if some points belonging to rect are above the y = x + c line passing for rectPoint.
> 
> Passing "for"? Do you mean "passing through"?

changed.

> > +    return (isPointAboveMainDiagonal(rectPoint, rect.location())
> > +            || isPointAboveMainDiagonal(rectPoint, IntPoint(rect.right(), rect.y()))
> > +            || isPointAboveMainDiagonal(rectPoint, IntPoint(rect.x(), rect.bottom()))
> > +            || isPointAboveMainDiagonal(rectPoint, IntPoint(rect.right(), rect.bottom())));
> 
> No need for the parentheses here in this expression.

done for this and other similar expressions.

> If it wasn't for the brokenness of those functions, I would have suggested you
> use the named functions like bottomLeft() and bottomRight(). But they're broken
> in design, so I won't suggest you use them here unless someone fixes them and
> converts the old callers.

You mean using IntRect::bottomLeft() and friends in distanceInDirection() ? What is broken in design?

> > +inline static bool isRectAboveAntiDiagonal(const IntPoint& rectPoint, const IntRect& rect)
> 
> I believe antidiagonal is one word, so the "D" should not be capitalized.
> 
> > +static int distanceInDirection(Node* start, Node* dest, FocusDirection direction)
> 
> > +    // The bounding rectangle of two consecutive links could overlap, so we decrease the size of
> > +    // both rectangles.
> > +    // FIXME: Is there a better way to do this?
> > +    startRect.inflate(-4);
> > +    destRect.inflate(-4);
> 
> The comment needs to indicate where the constant 4 comes from. Why is 4 good
> enough? Why not 3 or 5?
> And we need a test case in the regression tests directory that demonstrates
> that 4 is a good choice.

I will add a test for that

> > +        , distance(std::numeric_limits<int>::max())
> 
> Should do "using namespace std" at the top of the file and not say "std::"
> here.
> 
> Also, this code uses both INT_MAX and numeric_limits<int>::max() in the same
> algorithm. Lets chose one or the other.

Fixed. Using 'numeric_limits<int>::max()' everywhere now.

> > +        } else if (candidate != start && candidate->isKeyboardFocusable(event) && candidate->tabIndex() >= 0) {
> 
> Why the explicit check for tabIndex() here? That seems like it should be the
> responsibility of isKeyboardFocusable? Is there any special reason you're
> ruling out items that have a negative tab index? If so, I think you need a
> comment and if the rule really needs to be different than isKeyboardFocusable
> then it should be encapsulated in a function like isDirectionallyFocusable (or
> some better name).
> 
> We need a test demonstrating and double-checking which elements are and are not
> focusable with directional navigation.

removed 'candidate->tabIndex() >= 0' check. as it is being done in isKeyboardFocusable side.

> > +bool FocusController::advanceFocusDirectional(FocusDirection direction, KeyboardEvent* event, bool initialFocus)
> 
> The name isn't great here because "advance focus directional" is not good
> grammar. Even advanceFocusDirectionally would be slightly better, but it's not
> a good name either because "forwards" and "backwards" seem like directions to
> me. Maybe advanceFocusGeometrically? You should think about what you'd call
> this in conversation and see if you can convert that into a name.

'advanceFocusDirectionally' sounds ok to me I left it that way for instance. What do you think about 'advanceFocusSpatialy' ?

> The meaning of the initialFocus argument is quite unclear.

'initialFocus' originally is used to indicate if focus will advance to chrome. In directional navigation it should never go to chrome, so I removed the parameter.

> It would be better if the algorithm was expressed in terms of Element* rather
> than Node* from top to bottom. I'd rather see that handled right when we go
> from the renderer to its node, rather than higher up.

Sorry Darin, I did not get your point here.

> > +bool FocusController::advanceFocusLinear(FocusDirection direction, KeyboardEvent* event, bool initialFocus)
> 
> This is not a good name. Moving forward and backward through the document is
> not "linear" -- it doesn't go along a line. I'd suggest
> advanceFocusInDocumentOrder perhaps.
> 

changed.

> > +    , m_enableKeyboardNavigation(false)
> 
> Unfortunately, "keyboard navigation" already has a meaning, especially to the
> visually impaired, and I don't believe it has anything to do with using arrow
> keys to move between elements based on their geometric position. We need a name
> that's more specific to what this feature is.
> 
> I'm not sure I like the idea of coding in the key bindings to the arrow keys.
> But since, for good or bad, that's what this turns on and off, the name could
> be shouldUseArrowKeysForDirectionalNavigation or something along those lines.

changed.

> I think we should consider exposing the directional navigation to JavaScript
> somehow, so we can test it even in a browser that has the end-user binding
> turned off.
> 
> Something like commands for execCommand, but maybe not that because there could
> be compatibility consequences of adding something there.

Maybe doing this in a follow up bug as it is not core of the feature ?

[Antonio Gomes]

Created attachment 26645 [details]
WIP - Add directional navigation to WebCore (v5)

WIP patch. see comment 22 for reference.

https://bugs.webkit.org/show_bug.cgi?id=18662#c22


missing: tests, change log entry, open questions.

[Joseph Ligman]

Created attachment 26650 [details]
patch from bug 22740

Here is the patch from bug 22740. Not sure if it's useful at all, but thought I would put it up here nonetheless.

[Joseph Ligman]

(In reply to comment #23)
> Created an attachment (id=26645) [review]
> Add directional navigation to WebCore (v4)
> 
> WIP patch. see comment 22 for reference.
> 
> https://bugs.webkit.org/show_bug.cgi?id=18662#c22
> 
> 
> missing: tests, change log entry, open questions.
> 

Is it possible to navigate only to focus nodes that intersect the visible view? The point being if you jump to a node that is far outside the current viewport it is a undesirable user experience on small screens. In this case, it would be nice to scroll by a fixed distance in the direction of navigation until the next element intersects the viewing area and then continue navigation as before. This lets the user read pages that have sparsely distributed focus nodes. Navigating frames this way would be great too.

[Antonio Gomes]

Joseph,  we should definitively join efforts :)

1) Scrollby if target node is not in current view port would be great (avoid possible crazy jumps). Does your patch support so ?

2) Currently initial focused node is always the first node in the TAB INDEX. This initial focus shoudl be according to the TAB INDEX, yes, but it should be the first node in the current viewport. If no focusable in current viewport, scroll should be done.

I am right now working on the tests.

> Is it possible to navigate only to focus nodes that intersect the visible view?
> The point being if you jump to a node that is far outside the current viewport
> it is a undesirable user experience on small screens. In this case, it would be
> nice to scroll by a fixed distance in the direction of navigation until the
> next element intersects the viewing area and then continue navigation as
> before. This lets the user read pages that have sparsely distributed focus
> nodes. Navigating frames this way would be great too.
> 

[Joseph Ligman]

(In reply to comment #26)
> Joseph,  we should definitively join efforts :)
> 
> 1) Scrollby if target node is not in current view port would be great (avoid
> possible crazy jumps). Does your patch support so ?
> 
> 2) Currently initial focused node is always the first node in the TAB INDEX.
> This initial focus shoudl be according to the TAB INDEX, yes, but it should be
> the first node in the current viewport. If no focusable in current viewport,
> scroll should be done.
> 
> I am right now working on the tests.
> 
> > Is it possible to navigate only to focus nodes that intersect the visible view?
> > The point being if you jump to a node that is far outside the current viewport
> > it is a undesirable user experience on small screens. In this case, it would be
> > nice to scroll by a fixed distance in the direction of navigation until the
> > next element intersects the viewing area and then continue navigation as
> > before. This lets the user read pages that have sparsely distributed focus
> > nodes. Navigating frames this way would be great too.
> > 
> 

Ok. I will start working off of your patch, see if I can offer help for the view intersection issue. I have a layout test in my patch that might be useful for you. It doesn't do much, but I think it fulfills the requirement.   

[Onne Gorter]

I've been working on this based on the v5 patch, though heavily modified.

* implements: http://www.w3.org/TR/WICD/#current-focus-point-algorithm , mostly

It handles flowing elements by evaluating each rect individually, not the bounding rect.

Also experimented a bit on navigating out of text-boxes and other input elements. And (for debugging) drawing the focus point and selected element (second patch).

Some weirdness in the code is due to FocusController not being the only one responsible for setting focus and active elements, sometimes elements call back into FocusController after the fact.

What doesn't work so well is overlapping links (e.g. a list with negative margins on the <li> elements). And other overlapping layers.

Also the rects we use to evaluate other links, likely, are broken in respect to transformations, but I read that those functions will be fixed some point in the future.

The second patch is for experimentation only, it doesn't draw/refresh quite right. Also it enables keyboard navigation by default, and by just the plain cursor keys.

recap: more work is required ...

[Onne Gorter]

Created attachment 26971 [details]
main patch, adding focuspoint spatial navigation

[Onne Gorter]

Created attachment 26972 [details]
expirimental, highligh focused rect and focus point

[Onne Gorter]

Created attachment 28687 [details]
better implementation

updated the patch, many cleanups, better algorithm and also input/textarea and select form elements are keyboard controllable.

I'm only working on this every now and then, so I cleaned up the patch for others to work on. There is a TODO list in the patch.

I would propose we call this 'spatial navigation' from http://en.wikipedia.org/wiki/Spatial_navigation , though this is not in the patch yet. (Still shouldUseArrowKeysForDirectionNavigation ... )

[Joseph Ligman]

Hi Onne.

I'm looking forward to looking at your implementation in more detail. 
Here are a couple of things I found out in my recent attempt at this implementation.
 
1.) I need to limit the search area in my nextInDirection method (see below). This really helps when navigating on a small screen (meaning if a rectangle is not intersected with the viewport I just scroll by some fixed amount) otherwise the users can get lost with long jumps. 

if (visibleRect.intersects(nextRect)) {
    double distance = calculateDistance (direction, nextRect, focusPoint, focusRect, searchRect);
    if (bestDistance > distance) {
       bestDistance = distance;
       bestRect = nextRect;
    }

2.) The other thing I do is navigate frames independently, this way you can move in and out of frames even if there are no "focusable" elements. Where navigateFrame either gets the nextInDirection or scrolls or returns false.
 
if (!enterFrame(direction)) {
   if (!navigateFrame(direction)) {
     if (exitFrame(direction))
        navigate(direction);
     }
}

Most of my implementation has been moved out of the WebKit, and is tailored to small screen devices so I'm not sure if it applies anymore, but I thought those issues might be useful. Since you are still working on this I am going to look and see how it would apply. For me it would be best to add the API "nextInDirection" and not have the WebKit maintain any state information. 

[Onne Gorter]

(In reply to comment #32)
> 1.) I need to limit the search area in my nextInDirection method (see below).
> This really helps when navigating on a small screen (meaning if a rectangle is
> not intersected with the viewport I just scroll by some fixed amount)

I put in a TODO in the code where to implement this. It is not just useful on small devices, also to allow general smooth scrolling with just cursor keys.

> 2.) The other thing I do is navigate frames independently, this way you can
> move in and out of frames even if there are no "focusable" elements. Where
> navigateFrame either gets the nextInDirection or scrolls or returns false.

Good point, didn't thing of this. Worse, right now frames (or any area with a scrollbar) don't work so well.

> Most of my implementation has been moved out of the WebKit, and is tailored to
> small screen devices so I'm not sure if it applies anymore, but I thought those
> issues might be useful. Since you are still working on this I am going to look
> and see how it would apply. For me it would be best to add the API
> "nextInDirection" and not have the WebKit maintain any state information.

Not entirely sure if that is true. You would need a lot of support from WebCore stuff in the first place, like <select>, <textarea> and <input type=radio|checkbox>, they need to be aware of spatial navigation. And with frames, likely the best solution involves a stack of focus points. But that will turn into a lot of state duplication externally to get right, and will have difficulties tracking internal webcore state as it changes.

On the other hand, I am currently drawing a mouse like cursor, which is likely a task for outside of webcore at least.

[Antonio Gomes]

finally working on this.

[Antonio Gomes]

Created attachment 46370 [details]
WIP - Add directional navigation to WebCore (v6)   

Updated version of  "WIP - Add directional navigation to WebCore (v5)". Also WIP

This version (v6) is a followup of (v5) patch, and mostly adds some Layout Test infra structure for the feature, as well as tests coverage for some edge cases (more to come). Specifically about this test infra (see LayoutTests/fast/events/spatial-navigation/spatial-navigation-utils.js), it is based on Mozilla's SNav chrome test code. I have to check the license and copyright for that ... which i helped to implement.

As I am algo going to improved/re-work the current math algorithm used, I am not marking the patch for review. (but v7 will be ready to be reviewed).

[Antonio Gomes]

Created attachment 46537 [details]
WIP - Add directional navigation to WebCore (v7)

WIP - Add directional navigation to WebCore (v7)

> As I am algo going to improved/re-work the current math algorithm used, I am
> not marking the patch for review. (but v7 will be ready to be reviewed).

Algorithm reworked: superPrecedence logic added for a much smoother arrow navigation experience.

closer to a reviewable version ...

[Antonio Gomes]

Created attachment 46576 [details]
Add directional navigation to WebCore (v8)

Patch v8:

1) Improves the algorithm inicially proposed by Marco Barisione:
* Now it is based on a super-precedence logic, whereas rects whose middle
  falls between the top or bottom of the current rect are preferible to
  move focus to. It falls back to the common eucledian distance.
2) Adds LayoutLayout for the following edge cases:
* table traversal.
* iframe traversal (no scrollable content).
* unit-overflow during distance calculation.
* scroll-in-direction.
* super precedence in vertical direction.


TODO in followup bugs:
* Add port specific hooks to each DRTs to enable/disable Spatial Navigation.
* Form navigation and SNav interaction.
* Better support Iframes with scrollable content.
* Make navigation keys customizable. It currently works with arrows keys only
  (up, down, right and left).
* Make it support modifiers (Alt, Ctrl and Shift).

[Antonio Gomes]

Created attachment 46881 [details]
Add directional navigation to WebCore (v9)

Patch v9: It has all described in comment 37 plus:

* Fixed frame traversal code.
* Added new horizontal super-precendence layout test.

[Gyuyoung Kim]

I make a try to use the last patch on my linux PC. However, When I went some websites, browser(GtkLauncher) sometimes came to crash during the keyboard navigation. It seems to me that the distanceIndirection() of FocusController.cpp needs to check if renderer of start / end node is null or not. To my knowledge, node can has a renderer or not.(But, I am not sure)

After modifing the source code as below, I don't meet crash further.

static long long distanceInDirection(Node* start,... 
{
...
  RenderObject* startRender = NULL;
  startRender = start->renderer();
  if (!startRender)
      return -1;

  RenderObject* destRender = NULL;
  destRender = dest->renderer();
  if (!destRender)
      return -1;
...

[Antonio Gomes]

Comment on attachment 46881 [details]
Add directional navigation to WebCore (v9)

clearing review flag for now to incorporate further fixes and Kim's suggestion.

@Kim: Thanks for the input. Could you share the test cases you faced the crashes ? I would hapelly add layout tests to cover these cases as well.

(In reply to comment #39)
> I make a try to use the last patch on my linux PC. However, When I went some
> websites, browser(GtkLauncher) sometimes came to crash during the keyboard
> navigation. It seems to me that the distanceIndirection() of
> FocusController.cpp needs to check if renderer of start / end node is null or
> not. To my knowledge, node can has a renderer or not.(But, I am not sure)
> 
> After modifing the source code as below, I don't meet crash further.
> 
> static long long distanceInDirection(Node* start,... 
> {
> ...
>   RenderObject* startRender = NULL;
>   startRender = start->renderer();
>   if (!startRender)
>       return -1;
> 
>   RenderObject* destRender = NULL;
>   destRender = dest->renderer();
>   if (!destRender)
>       return -1;
> ...

[Antonio Gomes]

Created attachment 47581 [details]
Add directional navigation to WebCore (v10) 

Patch v10

Summary:

* see comment #37
* Fixed crash when trying to focus nodes w/ a renderer (e.g. display:none)
* Implemented support for SNav'ing through scrollable iframe content.
- LayoutTests/fast/events/spatial-navigation/snav-iframe-no-focusable-content.html
- LayoutTests/fast/events/spatial-navigation/snav-iframe-with-offscreen-focusable-element.html

[WebKit Review Bot]

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

Failed to run "WebKitTools/Scripts/check-webkit-style" exit_code: 1
WebCore/page/FocusController.cpp:526:  Missing space before ( in if(  [whitespace/parens] [5]
WebCore/page/FocusController.cpp:926:  An else should appear on the same line as the preceding }  [whitespace/newline] [4]
WebCore/page/EventHandler.cpp:2177:  An else if statement should be written as an if statement when the prior "if" concludes with a return, break, continue or goto statement.  [readability/control_flow] [4]
Total errors found: 3


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

[Antonio Gomes]

Created attachment 47590 [details]
Add directional navigation to WebCore (v10+)

see comment #41 for details (it is the same patch plus style issues pointed by the bot in comment #42)

[WebKit Review Bot]

Attachment 47590 [details] did not build on gtk:
Build output: http://webkit-commit-queue.appspot.com/results/216467

[WebKit Review Bot]

Attachment 47590 [details] did not build on qt:
Build output: http://webkit-commit-queue.appspot.com/results/215568

[Antonio Gomes]

Created attachment 47592 [details]
Add directional navigation to WebCore (v10++)

it is the same patch plus as in comment #41 (see details) plus:

* style issues pointed by the bot in comment #42 .
* build issue pointed by the bot in comment #44 and comment #45 .

(sorry about the noise)

[Gyuyoung Kim]

(In reply to comment #40)
> (From update of attachment 46881 [details])
> clearing review flag for now to incorporate further fixes and Kim's suggestion.
> 
> @Kim: Thanks for the input. Could you share the test cases you faced the
> crashes ? I would hapelly add layout tests to cover these cases as well.
> 

Sorry, recently, I am too busy. So, I don't know when the test case will be summited. If I have a time, I will try to summit the test case. :)

I met the crash on websites below,

- http://www.daum.net (Korea famous website)
- http://www.naver.net (Korea famous website)

[Antonio Gomes]

Created attachment 47640 [details]
Add directional navigation to WebCore (v11)

Patch v11:

Summary:
1) Improves the algorithm inicially proposed by Marco Barisione:
* Now it is based on a super-precedence logic, whereas rects whose middle
  falls between the top or bottom of the current rect are preferible to
  move focus to. It falls back to the common eucledian distance.
2) Adds 8 LayoutLayout for the following edge cases:
* table traversal.
* tiny table traversal (which validates the rect inflate value used).
* iframe traversal (scrollable content).
* iframe traversal (no scrollable content).
* iframe traversal (no focusable content).
* unit-overflow during distance calculation (focusable elements 100.000.000px distant from each other).
* scroll-in-direction.
* super precedence in vertical direction.
* super precedence in horizontal direction.

TODO in followup bugs:
* Add port specific hooks to each DRTs to enable/disable Spatial Navigation (see bug 33715 for Qt).
* Form navigation and SNav interaction.
* Better support Iframes with scrollable content (working initial support already implemented).
* Make navigation keys customizable. It currently works with arrows keys only
  (up, down, right and left).
* Make it support modifiers (Alt, Ctrl and Shift).


Diff from patch 47592 "v10++":
* Fixes issues related to the scrollOffset usage inside iframes.

[Simon Fraser (smfr)]

Comment on attachment 47640 [details]
Add directional navigation to WebCore (v11)

> diff --git a/WebCore/page/EventHandler.cpp b/WebCore/page/EventHandler.cpp

> +FocusDirection EventHandler::isArrowKey(const String& keyIdentifier)

The name of this method is confusing. An "isFoo" method should return a bool. It should be something like
"focusDirectionForKey()" and at call sites you'd do
if (focusDirectionForKey(s) != FocusDirectionNone) {
...

> +{
> +    FocusDirection retVal = (FocusDirection) 0;

I think there should be a FocusDirectionNone enum value.

> +    if (keyIdentifier == "Down")
> +        retVal = FocusDirectionDown;
> +    else if (keyIdentifier == "Up")
> +        retVal = FocusDirectionUp;
> +    else if (keyIdentifier == "Left")
> +        retVal = FocusDirectionLeft;
> +    else if (keyIdentifier == "Right")
> +        retVal = FocusDirectionRight;

Maybe use AtomicStrings for these?

> diff --git a/WebCore/page/FocusController.cpp b/WebCore/page/FocusController.cpp

> +enum PrecedenceMode {
> +    None = -1,
> +    Low,
> +    Precedent,
> +    SuperPrecedent
> +};

Precedence of what? Maybe rename to FocusCandidatePrecedence?
Also needs a comment to explain how "SuperPrecedent" differs from "Precedent". Why not just use a numeric value, or "Low, Medium, High"?

> +struct BestCandidate {
> +    BestCandidate()
> +        : node(0)
> +        , distance(numeric_limits<long long>::max())
> +        , parentDistance(numeric_limits<long long>::max())
> +        , mode(None)
> +        , parentMode(None)
> +    {
> +    }
> +    Node* node;
> +    long long distance;
> +    long long parentDistance;
> +    PrecedenceMode mode;
> +    PrecedenceMode parentMode;
> +};

BestCandidate for what? Rename to FocusCandidate?

> +static long long precedenceDistance(FocusDirection, IntRect&, IntRect&);
> +static long long distanceInDirection(Node*, Node*, FocusDirection, BestCandidate&);

Do you really need long long for distance? All other WebCore positions are floats or ints.

> +static void nextInDirection(Document*, Node*, FocusDirection, KeyboardEvent*, BestCandidate&);
> +static bool isRectInDirection(FocusDirection, IntRect, IntRect);
> +static inline IntRect renderRect(RenderObject*);
> +static long long spatialDistance(FocusDirection, IntRect&, IntRect&);
> +static bool scrollInDirection(Frame*, FocusDirection);
> +static bool isOffscreenRect(Node*);

Should any of these be instance or class methods?

> +///////////////////////////////////////
> +// HELPER SPATIAL NAVIGATION METHODS //
> +///////////////////////////////////////

We don't normally add comments like this.

> +static void nextInDirection(Document* document, Node* start, FocusDirection direction, KeyboardEvent* event, BestCandidate& bestCandidate)

I think this would be better named getNextFocusCandidate() or fetchNextFocusCandidate().

> +            if (innerDocument == start->document())
> +                nextInDirection(innerDocument, start, direction, event, bestCandidate);
> +            else {
> +                // Check if the current iframe (or frame) element itself is a good candidate to move focus to.
> +                // If it is, then we traverse its inner nodes.
> +                // ps: lets pass a copy of the best candidate, to not get fooled by a frame w/out
> +                // focusable elements.

The "ps:" is weird. Just make it a normal sentence.

> +                BestCandidate bestCandidateCopy = bestCandidate;
> +                long long distance = distanceInDirection(start, candidate, direction, bestCandidateCopy);
> +                if (distance < bestCandidateCopy.distance) {
> +                    bestCandidateCopy.parentMode = bestCandidateCopy.mode;
> +                    bestCandidateCopy.parentDistance = distance;
> +
> +                    nextInDirection(innerDocument, start, direction, event, bestCandidateCopy);
> +
> +                    // If we really have a inner best node candidate, take it.
> +                    if (bestCandidate.node != bestCandidateCopy.node)
> +                        bestCandidate = bestCandidateCopy;

It seems like this "compare and set" logic might be better as a method on BestCandidate.

> +static long long distanceInDirection(Node* start, Node* dest, FocusDirection direction, BestCandidate& candidate)
> +{
> +    long long distance = candidate.distance;
> +
> +    IntRect startRect = IntRect();
> +    IntRect destRect = IntRect();
> +    RenderObject* startRender = 0;
> +    RenderObject* destRender = 0;
> +
> +    startRender = start->renderer();
> +    if (!startRender)
> +        goto exitPoint;
> +
> +    destRender = dest->renderer();
> +    if (!destRender)
> +        goto exitPoint;

No gotos please.

> +    startRect = renderRect(startRender);
> +    destRect  = renderRect(destRender);

Declare the IntRects here.

> +    // The bounding rectangle of two consecutive links could overlap, so we decrease the size
> +    // of both rectangles.
> +    startRect.inflate(-4);
> +    destRect.inflate(-4);

These can cause the rect widths to go negative, which you don't want. Why the special case for links?

> +    if (takesSuperPrecedence(direction, startRect, destRect) || candidate.parentMode == SuperPrecedent) {
> +        // reset distance as we are now in super precedence mode

Comments should use Sentence case.

Seems like more logic to push into BestCandidate, perhaps.

> +exitPoint:
> +    return numeric_limits<long long>::max();

I think it would be clearer if you had a constant for numeric_limits<long long>::max(), like cMaxDistance.

> +// FIXME: This function is flawed because it doesn't consider the effects of CSS or SVG transforms.

It does take transforms into account; absoluteClippedOverflowRect() does the right thing.

However, it does not behave correctly with transformed frames.

> +static inline IntRect renderRect(RenderObject* render)

The method should be renamed to indicate that it is returning a rect relative to the root document.

> +{
> +    ASSERT(render);
> +
> +    Node* node = render->node();
> +    Document* mainDocument = node->document()->page()->mainFrame()->document();
> +    bool useScrollOffset = !isOffscreenRect(node) && node->document() != mainDocument;
> +
> +    IntRect rect(render->absoluteClippedOverflowRect());
> +
> +    // There are cases, mostly when |render|'s associated node is offscreen,
> +    // it is safier to get its position regardless the container scroll offset.

Typo: "safier".

> +    if (useScrollOffset)
> +        if (FrameView* frameView = render->node()->document()->view())
> +            rect.move(-frameView->scrollOffset());
> +
> +    // handle nested frames.
> +    for (Frame* frame = render->document()->frame(); frame; frame = frame->tree()->parent())
> +        if (HTMLFrameOwnerElement* ownerElement = frame->ownerElement())
> +            rect.move(ownerElement->offsetLeft(), ownerElement->offsetTop());
> +
> +    return rect;
> +}

> +// -- grabbed from MICROB excepted by UP|DOWN logic.

What is MICROB? What is the license for this code?

> +static bool isRectInDirection(FocusDirection direction, IntRect startRect, IntRect destRect)

Pass rects by const reference.

> +    int middle = 0;

Declare this only where used.

> +    switch (direction) {
> +    case FocusDirectionLeft:
> +        middle = destRect.x() + abs(destRect.width()) / 2;
> +        return (middle < startRect.x());
> +    case FocusDirectionRight:
> +        middle = destRect.x() + abs(destRect.width()) / 2;
> +        return (middle  > startRect.x() + abs(startRect.width()));
> +    case FocusDirectionUp :
> +        return (destRect.y() < startRect.y());
> +    case FocusDirectionDown:
> +        return (destRect.y() + abs(destRect.height()) > startRect.y() + abs(startRect.height()));
> +    default:
> +        ASSERT_NOT_REACHED();

This assert is not required, and prevents the compiler from warning about unhandled values.

> +// Checks if |node| is in the visible area (viewport) of its container document.

But that's backwards from the method behavior.

> +static bool isOffscreenRect(Node* node)
> +{
> +    // Get the current viewport rect so we can check if bestCandidate's rect
> +    // is visible before actually moving the focus to it. In case it is not visible,
> +    // we scroll in direction later on instead.
> +    FrameView* frameView = node->document()->view();
> +    if (!frameView)
> +        return true;
> +
> +    IntRect containerViewportRect = frameView->visibleContentRect();
> +
> +    RenderObject* render = node->renderer();
> +    if (!render)
> +        return true;
> +
> +    IntRect rect(render->absoluteClippedOverflowRect());

No need for 'rect' here.

> +// In a bottom-up way, this method tries to scroll |frame| in a given direction
> +// |direction|, going up in the frame tree hierarchy in case it does not succeed.
> +static bool scrollInDirection(Frame* frame, FocusDirection direction)
> +{
> +    if (!frame)
> +        return false;
> +
> +    // Leave the focus on the same node but scroll.
> +    ScrollDirection scrollDirection;
> +
> +    switch (direction) {
> +    case FocusDirectionLeft:
> +        scrollDirection = ScrollLeft;
> +        break;
> +    case FocusDirectionRight:
> +        scrollDirection = ScrollRight;
> +        break;
> +    case FocusDirectionUp:
> +        scrollDirection = ScrollUp;
> +        break;
> +    case FocusDirectionDown:
> +        scrollDirection = ScrollDown;
> +        break;
> +    default:
> +        ASSERT_NOT_REACHED();
> +        return false;

Remove default case.

> +// This method checks for very preferable rect to move focus to. In essence targets

"very preferable"?

> +// whose middle falls between the top or bottom of the current rect.

This is not a complete sentence.

> +static bool takesSuperPrecedence(FocusDirection direction, IntRect& startRect, IntRect& destRect)

You need a better term than "super precedence".

Rect params should be const.

> +{
> +    if (direction == FocusDirectionLeft || direction == FocusDirectionRight) {
> +        int destMiddle = destRect.y() + abs(destRect.height()) / 2;
> +        int destBottom = destRect.y() + abs(destRect.height());
> +        int destEnd    = destRect.x() + abs(destRect.width());
> +
> +        int startBottom = startRect.y() + abs(startRect.height());
> +        int startEnd    = startRect.x() + abs(startRect.width());

We don't line up code like this.

> +        return ((destRect.y() >= startRect.y() && destRect.y() <= startBottom)
> +            ||  (destMiddle >= startRect.y() && destMiddle <= startBottom)
> +            ||  (destBottom >= startRect.y() && destBottom <= startBottom)
> +            ||  (destRect.y() == startRect.y())
> +            ||  (destBottom == startBottom)
> +            ||  (destRect.y() <= startRect.y() && destBottom >= startBottom));

Just one space after the ||.

> +        return ((destMiddle >= startRect.x() && destMiddle <= startEnd)
> +            ||  (destRect.x() >= startRect.x() && destRect.x() <= startEnd)
> +            ||  (startRect.x() == destRect.x())
> +            ||  (startEnd == destEnd)
> +            ||  (destEnd >= startRect.x() && destEnd <= startEnd)
> +            ||  (destRect.x() <= startRect.x() && destEnd >= startEnd));

Ditto.

> +static bool takesPrecedence(FocusDirection direction, IntRect& startRect, IntRect& destRect)

Const rects.

> +    if (direction == FocusDirectionLeft || direction == FocusDirectionRight) {
> +        int minY = startRect.y() /* - half */;
> +        int maxY = startRect.y() + abs(startRect.height()) /* + half */;
> +        int startBottom = startRect.y() + abs(startRect.height());
> +
> +        int destMiddle = destRect.y() + abs(destRect.height()) / 2;
> +        int destBottom = destRect.y() + abs(destRect.height());
> +
> +        return ((destRect.y() >= minY && destRect.y() <= maxY)
> +            ||  (destBottom >= minY && destBottom <= maxY)
> +            ||  (destMiddle >= startRect.y() && destMiddle <= startBottom)
> +            ||  (destRect.y() >= startRect.y() && destRect.y() <= startBottom)
> +            ||  (destBottom >= startRect.y() && destBottom <= startBottom)
> +            ||  (destRect.y() <= startRect.y() && destBottom >= startBottom));

Ditto.

> +// sqrt(((x1 - x2) ^ 2) + ((y1 - y2) ^ 2))
> +static long long precedenceDistance(FocusDirection direction, IntRect& startRect, IntRect& destRect)
> +{
> +    long long distance = numeric_limits<long long>::max();
> +    long long sec = numeric_limits<long long>::max();

I don't understand 'sec'. Needs a better name.

> +
> +    if (direction == FocusDirectionLeft) {
> +        int startX = startRect.x();
> +        int startY = startRect.y() + abs(startRect.height()) / 2;
> +        int destX  = destRect.x() + abs(destRect.width());
> +        int destY  = destRect.y() + abs(destRect.height()) / 2;
> +
> +        long long p = ((startX - destX) * (startX - destX)) + ((startY - destY) * (destY - destY));
> +        sec = sqrt(p);
> +
> +        p = ((startRect.x() - destRect.x()) * (startRect.x() - destRect.x())) + ((startRect.y() - destRect.y()) * (startRect.y() - destRect.y()));
> +        distance = sqrt(p);
> +
> +        if (sec < distance && startRect.y() == destRect.y())
> +            distance = sec;
> +    }
> +
> +    if (direction == FocusDirectionRight) {
> +        int startX = startRect.x() + abs(startRect.width());
> +        int startY = startRect.y() + abs(startRect.height()) / 2;
> +        int destX  = destRect.x();
> +        int destY  = destRect.y() + abs(destRect.height()) / 2;
> +
> +        long long p = ((destX - startX) * (destX - startX)) + ((destY - startY) * (destY - startY));
> +        sec = sqrt(p);
> +
> +        p = ((destRect.x() - startRect.x()) * (destRect.x() - startRect.x())) + ((destRect.y() - startRect.y()) * (destRect.y() - startRect.y()));
> +        distance = sqrt(p);
> +
> +        if (sec < distance && startRect.y() == destRect.y())
> +            distance = sec;
> +    }
> +
> +    if (direction == FocusDirectionUp) {
> +        int startX = startRect.x() + abs(startRect.width()) / 2;
> +        int startY = startRect.y();
> +        int destX  = destRect.x() + abs(destRect.width()) / 2;
> +        int destY = destRect.y() + abs(destRect.height());
> +
> +        long long p = ((startX - destX) * (startX - destX)) + ((startY - destY) * (startY - destY));
> +        sec = sqrt(p);
> +
> +        p = ((startRect.x() - destRect.x()) * (startRect.x() - destRect.x())) + ((startRect.y() - destRect.y()) * (startRect.y() - destRect.y()));
> +
> +        distance = sqrt(p);
> +
> +        if (sec < distance && startRect.x() == destRect.x())
> +            distance = sec;
> +
> +        sec = (startRect.y() - destRect.y());
> +
> +        if (sec < distance)
> +            distance = sec;
> +    }
> +
> +    if (direction == FocusDirectionDown) {
> +        // get middle X for current and target rects
> +        int startX = startRect.x() + abs(startRect.width()) / 2;
> +        int startY = startRect.y() + abs(startRect.height()) / 2;
> +        int destX  = destRect.x() + abs(destRect.width()) / 2;
> +        int destY  = destRect.y() + abs(destRect.height()) / 2;
> +
> +        long long p = ((destX - startX) * (destX - startX)) + ((destY - startY) * (destY - startY));
> +        sec = sqrt(p);
> +
> +        p = ((destRect.x() - startRect.x()) * (destRect.x() - startRect.x())) + ((destRect.y() - startRect.y()) * (destRect.y() - startRect.y()));
> +        distance = sqrt(p);
> +
> +        if (sec < distance && startRect.x() == destRect.x())
> +            distance = sec;
> +
> +        sec = (destRect.y() - startRect.y());
> +
> +        if (sec < distance)
> +            distance = sec;
> +    }

Lots of repeated code here. Can you factor into a new method?

 // namespace WebCore
> diff --git a/WebCore/page/FocusController.h b/WebCore/page/FocusController.h
> index d86408a..38c08c4 100644
> --- a/WebCore/page/FocusController.h
> +++ b/WebCore/page/FocusController.h
> @@ -58,6 +58,9 @@ namespace WebCore {
>          bool isFocused() const { return m_isFocused; }
>  
>      private:
> +        bool advanceFocusDirectionally(FocusDirection, KeyboardEvent*);
> +        bool advanceFocusInDocumentOrder(FocusDirection, KeyboardEvent*, bool initialFocus);

We try to avoid using boolean parameters because they make the code at the call site hard to read.

> diff --git a/WebCore/page/Settings.h b/WebCore/page/Settings.h

> +        bool isSpatialNavigationEnabled() { return m_isSpatialNavigationEnabled; }

This method should be |const|.

r- for the MICROB licensing issue. I'd like to see one more round.

[Kenneth Rohde Christiansen]

Judging from http://en.wikipedia.org/wiki/MicroB the license is as follows:

Proprietary EULA Engine under MPL/GPL/LGPL tri-license

[Antonio Gomes]

Created attachment 47855 [details]
Add directional navigation to WebCore (v12)

Patch v12:

Summary:
see comment #48

Addressed Simon's comments.

[Antonio Gomes]

Thanks for reviewing, Simon.

Comments below.

> > +FocusDirection EventHandler::isArrowKey(const String& keyIdentifier)
> 
> The name of this method is confusing. An "isFoo" method should return a bool.
> It should be something like
> "focusDirectionForKey()" and at call sites you'd do
> if (focusDirectionForKey(s) != FocusDirectionNone) {

I agree. EventHandler::focusDirectionForKey method added.

> > +{
> > +    FocusDirection retVal = (FocusDirection) 0;
> 
> I think there should be a FocusDirectionNone enum value.

Done.

> > +    if (keyIdentifier == "Down")
> > +        retVal = FocusDirectionDown;
> > +    else if (keyIdentifier == "Up")
> > +        retVal = FocusDirectionUp;
> > +    else if (keyIdentifier == "Left")
> > +        retVal = FocusDirectionLeft;
> > +    else if (keyIdentifier == "Right")
> > +        retVal = FocusDirectionRight;
> 
> Maybe use AtomicStrings for these?

Done.

> > diff --git a/WebCore/page/FocusController.cpp b/WebCore/page/FocusController.cpp
> 
> > +enum PrecedenceMode {
> > +    None = -1,
> > +    Low,
> > +    Precedent,
> > +    SuperPrecedent
> > +};
> 
> Precedence of what? Maybe rename to FocusCandidatePrecedence?
> Also needs a comment to explain how "SuperPrecedent" differs from "Precedent".
> Why not just use a numeric value, or "Low, Medium, High"?

I changed the enum logic here. It is now in SpatialNavigationUtils.h , and now looks like:

// Spatially speaking, elements in a web page can be:
// 1) Totally aligned: There is a full intersection between the rects, either
//    vertically or horizontally.
// 2) Partially aligned: There is a partial intersection between the rects, either
//    vertically or horizontally.
// 3) Or, otherwise, not aligned at all.
enum FocusCandidateAlignment {
    None = 0,
    Partial,
    Full
};

> > +struct BestCandidate {
> > +    BestCandidate()
> > +        : node(0)
> > +        , distance(numeric_limits<long long>::max())
> > +        , parentDistance(numeric_limits<long long>::max())
> > +        , mode(None)
> > +        , parentMode(None)
> > +    {
> > +    }
> > +    Node* node;
> > +    long long distance;
> > +    long long parentDistance;
> > +    PrecedenceMode mode;
> > +    PrecedenceMode parentMode;
> > +};
> 
> BestCandidate for what? Rename to FocusCandidate?

Done.

> > +static long long precedenceDistance(FocusDirection, IntRect&, IntRect&);
> > +static long long distanceInDirection(Node*, Node*, FocusDirection, BestCandidate&);
> 
> Do you really need long long for distance? All other WebCore positions are
> floats or ints.

Darin concerned about the int usage of previous version of the patch, and I decided to use long long for safity.
There is a LayoutTest that tests the algorigthm behaviour with very far way nodes from each other.

> > +static void nextInDirection(Document*, Node*, FocusDirection, KeyboardEvent*, BestCandidate&);
> > +static bool isRectInDirection(FocusDirection, IntRect, IntRect);
> > +static inline IntRect renderRect(RenderObject*);
> > +static long long spatialDistance(FocusDirection, IntRect&, IntRect&);
> > +static bool scrollInDirection(Frame*, FocusDirection);
> > +static bool isOffscreenRect(Node*);
> 
> Should any of these be instance or class methods?

I do not think so, Simon, but rather I added a SpatialNavigationUtils.cpp|h instead.

> > +static void nextInDirection(Document* document, Node* start, FocusDirection direction, KeyboardEvent* event, BestCandidate& bestCandidate)
> 
> I think this would be better named getNextFocusCandidate() or
> fetchNextFocusCandidate().

As per a Kenneth suggestion, I renamed it to 'findFocusableNodeInDirection'.
 
> I think it would be clearer if you had a constant for numeric_limits<long
> long>::max(), like cMaxDistance.

Done. Constant added to SpatialNavigationUtils.h

> > +// FIXME: This function is flawed because it doesn't consider the effects of CSS or SVG transforms.

> It does take transforms into account; absoluteClippedOverflowRect() does the
> right thing. However, it does not behave correctly with transformed frames.
> > +static inline IntRect renderRect(RenderObject* render)

I re-wrote the comment to match to its real weak point.

> The method should be renamed to indicate that it is returning a rect relative
> to the root document.

renamed to:
IntRect renderRectRelativeToRootDocument(RenderObject*);

> > +// -- grabbed from MICROB excepted by UP|DOWN logic.
> What is MICROB? What is the license for this code?

see comment #50

> > +    switch (direction) {
> > +    case FocusDirectionLeft:
> > +        middle = destRect.x() + abs(destRect.width()) / 2;
> > +        return (middle < startRect.x());
> > +    case FocusDirectionRight:
> > +        middle = destRect.x() + abs(destRect.width()) / 2;
> > +        return (middle  > startRect.x() + abs(startRect.width()));
> > +    case FocusDirectionUp :
> > +        return (destRect.y() < startRect.y());
> > +    case FocusDirectionDown:
> > +        return (destRect.y() + abs(destRect.height()) > startRect.y() + abs(startRect.height()));
> > +    default:
> > +        ASSERT_NOT_REACHED();
> 
> This assert is not required, and prevents the compiler from warning about
> unhandled values.

We have unhandled values in this enum: FocusDirectionForward, FocusDirectionBackward and FocusDirectionNone. So it was needed to shut up the compiler.

> > +static bool scrollInDirection(Frame* frame, FocusDirection direction)
> > +{
> > +    if (!frame)
> > +        return false;
> > +
> > +    // Leave the focus on the same node but scroll.
> > +    ScrollDirection scrollDirection;
> > +
> > +    switch (direction) {
> > +    case FocusDirectionLeft:
> > +        scrollDirection = ScrollLeft;
> > +        break;
> > +    case FocusDirectionRight:
> > +        scrollDirection = ScrollRight;
> > +        break;
> > +    case FocusDirectionUp:
> > +        scrollDirection = ScrollUp;
> > +        break;
> > +    case FocusDirectionDown:
> > +        scrollDirection = ScrollDown;
> > +        break;
> > +    default:
> > +        ASSERT_NOT_REACHED();
> > +        return false;
> 
> Remove default case.

Same here. It was needed.

> > +static bool takesSuperPrecedence(FocusDirection direction, IntRect& startRect, IntRect& destRect)
> You need a better term than "super precedence".

takesSuperPrecedence() renamed to areRectsFullyAligned() and 
takesPrecedence() renamed to areRectsPartiallyAligned().
 
>  // namespace WebCore
> > diff --git a/WebCore/page/FocusController.h b/WebCore/page/FocusController.h
> > index d86408a..38c08c4 100644
> > --- a/WebCore/page/FocusController.h
> > +++ b/WebCore/page/FocusController.h
> > @@ -58,6 +58,9 @@ namespace WebCore {
> >          bool isFocused() const { return m_isFocused; }
> >  
> >      private:
> > +        bool advanceFocusDirectionally(FocusDirection, KeyboardEvent*);
> > +        bool advanceFocusInDocumentOrder(FocusDirection, KeyboardEvent*, bool initialFocus);
> 
> We try to avoid using boolean parameters because they make the code at the call
> site hard to read.

I know, but |FocusController::advanceFocusInDocumentOrder| is just a wrapped by FocusController::AdvanceFocus (see below) which already receives a bool.

bool FocusController::advanceFocus(FocusDirection direction, KeyboardEvent* event, bool initialFocus)

[WebKit Review Bot]

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

Failed to run "WebKitTools/Scripts/check-webkit-style" exit_code: 1
WebCore/page/FocusController.cpp:499:  Missing space before ( in if(  [whitespace/parens] [5]
Total errors found: 1


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

[Antonio Gomes]

Created attachment 48139 [details]
Add directional navigation to WebCore (v13)

Summary:
see comment #48
+
* Addressed Simon's comments.
* fixes the style issue pointed by the bot.
* better document the code.

(ping review?)

[WebKit Review Bot]

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

Failed to run "WebKitTools/Scripts/check-webkit-style" exit_code: 1
WebCore/page/SpatialNavigationUtils.cpp:148:  Missing spaces around /  [whitespace/operators] [3]
WebCore/page/SpatialNavigationUtils.cpp:150:  Should have a space between // and comment  [whitespace/comments] [4]
Total errors found: 2


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

[Antonio Gomes]

Created attachment 48141 [details]
Add directional navigation to WebCore (v13+)

err , and now the right patch.

Summary:
see comment #48
+
* Addressed Simon's comments.
* fixes the style issue pointed by the bot.
* better document the code.

sorry for bugspamming :(

[Eric Seidel (no email)]

Comment on attachment 48141 [details]
Add directional navigation to WebCore (v13+)

There are huge sections of copy/paste code here.  Couldn't those be turned into template functions which used -1/+1 to denote up/down/left/right?  I feel like that would make the code cleaner, because although it would be a little awkward to use the functions, you're always 100% certain that tehre are no copy paste errors with them.

This patch is difficutl to review because it's so long on a bug that has so many comments.  Reviewers are "scared" to miss something either in the bug history, or in this huge patch.

It would be possible to land this in smaller, more easily reviewed steps, including just the layout tests first, followed by the code change.

Going to stare at the patch a bit more now.

[Eric Seidel (no email)]

Comment on attachment 48141 [details]
Add directional navigation to WebCore (v13+)

Doesn't frametree have a top() method?
 300     // Move up in the chain of nested frames.
 301     while (true) {
 302         Frame* parentFrame = frame->tree()->parent();
 303         if (!parentFrame || !parentFrame->document())
 304             break;
 305 
 306         frame = parentFrame;
 307     }

Seems slightly dangerous having this so far away from the isElement check:
 343     static_cast<Element*>(node)->focus(false);

I think I owuld haev made this whole block:
 473                 // Check if the current {i}frame element itself is a good candidate
its own small function.
Yeah, probably one for each half of the if.

Another way to make part of this more readable (to my eye) woudl have been to use early return for things like:
 492             if (distance < closestFocusCandidate.distance) {

We generally avoid files called "utils" or "utilities" as they become sewers very quickly.  In this case, I woudl just have called this file "SpatialNavigation.h" and probably still left most of the content here.

Why is this OK license wise?
 160 // Based on the MICROB SNav logic (MPL/GLP/LGPG), excepted by the Down logic.

I don't think it's OK to add code w/o citing the full license, but I'm not a lawyer.

The ifs in areRectsFullyAligned are copy paste!
So is spatialDistanceForAlignedRects.

This is too hard to review at this size, and this amount of copy/paste code.

I would split the code out from the layout tests.  Get the layout tests approved and possibly landed (skipped) and then work on landing the code in parts, ideally with as little copy paste code as possible.

WebKit wants this functionality.  It's just impossible for a reviewer to do anything more than rubber-stamp this code at this size.  Given all the copy paste code I don't know how I could be sure that you haven't missed a minus sign or forgotten to fix one half of a copy/paste if.  Again these things make it difficult to r+.

r-  Mostly for the copy paste, partially for the license confusion.

[Antonio Gomes]

Created attachment 49074 [details]
Add directional navigation to WebCore (v14)

Addressed Eric's comments.


(In reply to comment #57)
> (From update of attachment 48141 [details])
> There are huge sections of copy/paste code here.  Couldn't those be turned into
> template functions which used -1/+1 to denote up/down/left/right?  I feel like
> that would make the code cleaner, because although it would be a little awkward
> to use the functions, you're always 100% certain that tehre are no copy paste
> errors with them.

Done. I introduced the following macros: START, MIDDLE, END, which tak |direction| and
|rect| as parameter. It makes 'if's in areRectsFullyAligned and areRectsPartlyAligned
not copy and paste anymore.

> It would be possible to land this in smaller, more easily reviewed steps,
> including just the layout tests first, followed by the code change.

Done. This patch does not include the LayoutTests.


> Doesn't frametree have a top() method?
>  300     // Move up in the chain of nested frames.
>  301     while (true) {
>  302         Frame* parentFrame = frame->tree()->parent();
>  303         if (!parentFrame || !parentFrame->document())
>  304             break;
>  305 
>  306         frame = parentFrame;
>  307     }

It does have. Using it now. The qouted code above has gone in favor of ir.

> I think I owuld haev made this whole block:
>  473                 // Check if the current {i}frame element itself is a good
> candidate
> its own small function.

Done. I put this in a new method call "deepFindFocusableNodeInDirection()".

> Yeah, probably one for each half of the if.

Also added a static helper: "updateFocusCandidateIfCloser()".

> Another way to make part of this more readable (to my eye) woudl have been to
> use early return for things like:
>  492             if (distance < closestFocusCandidate.distance) {

Done.

> We generally avoid files called "utils" or "utilities" as they become sewers
> very quickly.  In this case, I woudl just have called this file
> "SpatialNavigation.h" and probably still left most of the content here.

Done - renamed.

> Why is this OK license wise?
>  160 // Based on the MICROB SNav logic (MPL/GLP/LGPG), excepted by the Down
> logic.
> > So is spatialDistanceForAlignedRects.

The microb code is node needed anymore, so we do not need to care about licenses.
I drop the method spatialDistanceForAlignedRects. only "spatialDistance" is being used.

> WebKit wants this functionality.  It's just impossible for a reviewer to do
> anything more than rubber-stamp this code at this size.  Given all the copy
> paste code I don't know how I could be sure that you haven't missed a minus
> sign or forgotten to fix one half of a copy/paste if.  Again these things make
> it difficult to r+.
> 
> r-  Mostly for the copy paste, partially for the license confusion.

I hope we are in a better shape now.

[Antonio Gomes]

Created attachment 49076 [details]
Add directional navigation to WebCore (LayoutTests - v1)

LayoutTests splitted on its own  file, to separate the code logic of the feature to its tests, and also to help reviewers.

The following layout tests are included:

* snav-horizontal-superprecedence.html
* snav-iframe-no-focusable-content.html
* snav-iframe-no-scrollable-content.html
* snav-iframe-with-offscreen-focusable-element.html
* snav-table-traversal.html
* snav-tiny-table-traversal.html
* snav-unit-overflow-and-scroll-in-direction.html
* snav-vertical-superprecedence.html

, all them placed in LayoutTests/fast/events/spatial-navigation/

-> Each HTML has in its header explaination about what the patch is trying to test.

-> spatial-navigation-utils.js is a helper that takes are of moving the focus around between
elements, making sure it reaches the right target.

-> for now I am skipping the tests on all plaftorms (gtk, qt, mac, win) and follow up bugs are to be filed individually to revert that. I've done it already for qt and gtk.

[Antonio Gomes]

ping review ?

[Antonio Gomes]

I am hosting my development on this feature in thie branch: 

* http://gitorious.org/~tonikitoo/qtwebkit/tonikitoos-clone/commits/snav-dev

apart from the two patches also attached to this bug (one about thre core of the feature and other including layout tests), There are some followup work already been done (see patches on the top), and some even already r+'ed.

more to come in.

[Simon Fraser (smfr)]

Comment on attachment 49074 [details]
Add directional navigation to WebCore (v14)

> +    FocusDirection focusDirectionForKey(const AtomicString&);

This method should be |const|



> +        FocusDirection tabDirection = (FocusDirectionUp || direction == FocusDirectionLeft) ?
> +                                       FocusDirectionForward : FocusDirectionBackward;

Shouldn't this be:

  FocusDirection tabDirection = ( direction == FocusDirectionUp || direction == FocusDirectionLeft)
?

> +    // Move up in the chain of nested frames.
> +    frame = frame->tree()->top();

I don't undersand this. Why jump to the topmost frame?

> +        if (!(isMovingToRootDocument(focusedNode, candidate)
> +            && (closestFocusCandidate.node
> +            && (focusedNode->document() == closestFocusCandidate.node->document())))) {

You don't need so many parens here.



>  
>  namespace WebCore {
>      enum FocusDirection {
>          FocusDirectionForward = 0,
> -        FocusDirectionBackward
> +        FocusDirectionBackward,
> +        FocusDirectionNone,
> +        FocusDirectionUp,
> +        FocusDirectionDown,
> +        FocusDirectionLeft,
> +        FocusDirectionRight
>      };

Would making FocusDirectionNone have value 0 break anything? It would be preferable.


> +++ b/WebCore/page/SpatialNavigation.cpp


> +namespace WebCore {
> +
> +long long spatialDistance(FocusDirection, const IntRect&, const IntRect&);
> +IntRect renderRectRelativeToRootDocument(RenderObject*);
> +RectsAlignment alignmentForRects(FocusDirection, const IntRect&, const IntRect&);
> +bool areRectsFullyAligned(FocusDirection, const IntRect&, const IntRect&);
> +bool areRectsPartiallyAligned(FocusDirection, const IntRect&, const IntRect&);
> +bool isRectInDirection(FocusDirection, const IntRect&, const IntRect&);

I'm not sure if we normally declare file-local functions as 'static'. Take a look at some other files to see.

> +// FIXME_tonikitoo: FocusCandidate distanceDataForNode(start, dest, direction)

It's not clear what the action item is.

> +long long distanceInDirection(Node* start, Node* dest, FocusDirection direction, FocusCandidate& candidate)
> +{
> +    long long& distance = candidate.distance;

You set distance to be a reference to candidate.distance here...

> +        // Reset distance if we are now in higher precedence case.
> +        if (candidate.alignment < alignment && candidate.parentAlignment < alignment)
> +            distance = cMaxDistance;

and then assign to it lower down. Why use the reference at all? This is hard to follow.

> +        // FIXME_tonikitoo: make this assignment in the caller method ?

Either do it, or remove the FIXME.


> +    // There are cases, mostly when |render|'s associated node is offscreen,
> +    // it is safer to get its position regardless the container scroll offset.

This is a bit obscure. Why?

> +    if (useScrollOffset)
> +        if (FrameView* frameView = render->node()->document()->view())
> +            rect.move(-frameView->scrollOffset());

We would normally put braces at if (useScrollOffset) {

> +#define MIDDLE(direction, rect)       \
> +    isHorizontalMove(direction) ?     \
> +        rect.y() + rect.height() / 2: \
> +        rect.x() + rect.width()  / 2;
> +
> +#define END(direction, rect)          \
> +    isHorizontalMove(direction) ?     \
> +        rect.y() + rect.height() :    \
> +        rect.x() + rect.width();
> +
> +#define START(direction, rect)        \
> +    isHorizontalMove(direction) ? rect.y() : rect.x();

Please convert these into inline functions.

> +// This method checks if rects |a| and |b| are fully aligned either vertical or

vertically

> +// horizontally. Rects that match this criteria are preferable target nodes in
> +// move focus changing operations.
> +// In essence, targets whose middle falls between the top or bottom of the current rect.

This isn't a complete sentence.

> +    // About the logic below:

What about it?

> +    return ((bStart >= aStart && bStart <= aEnd)
> +            || (bStart >= aStart && bStart <= aEnd)
> +            || (bEnd >= aStart && bEnd <= aEnd)
> +            || (bMiddle >= aStart && bMiddle <= aEnd)
> +            || (bEnd >= aStart && bEnd <= aEnd));
> +}
> +
> +// * a = Current focused node.
> +// * b = Focus candidate node.

In all these methods, rather than commenting what a and b are, you should just name them appropriately: curRect, targetRect, or something.


> +        if (a.y() > b.y() + b.height()) {

use IntRect:bottom(), IntRect:right() here and in all these methods.

You could also define some inline methods like:

bool below(const IntRect& r, int pos)
{
  return pos > r.bottom();
}

to make this code more readable. You could also add IntPoint IntRect::center() const if you like (FloatRect has one).

> +bool isMovingToRootDocument(Node* from, Node* to)
> +{
> +    if (!from || !to)
> +        return false;
> +
> +    Document* rootDocument = to->document()->page()->mainFrame()->document();
> +    return (to->document() == rootDocument && from->document() != to->document());
> +}

The 'moving to' terminology is confusing. I think this would be clearer with:

bool isInRootDocument(Node*)

and then put the other logic at the call site.

> +void deflateIfNeeded(IntRect& a, IntRect& b, int fudgeFactor)

If needed for what?

I think this needs one more round of changes.

[Antonio Gomes]

Created attachment 49463 [details]
Add directional navigation to WebCore (v15)

Addressed most of Simon's comments.

(In reply to comment #63)
> (From update of attachment 49074 [details])
> > +    FocusDirection focusDirectionForKey(const AtomicString&);
> 
> This method should be |const|

Fixed.
 
> > +        FocusDirection tabDirection = (FocusDirectionUp || direction == FocusDirectionLeft) ?
> > +                                       FocusDirectionForward : FocusDirectionBackward;
> 
> Shouldn't this be:
> 
>   FocusDirection tabDirection = ( direction == FocusDirectionUp || direction ==
> FocusDirectionLeft)
> ?

Fixed. Not sure how I miss that for so long.

> > +    // Move up in the chain of nested frames.
> > +    frame = frame->tree()->top();
> 
> I don't undersand this. Why jump to the topmost frame?

Simon, the logic used here relies on a top-down traversal algorithm
to walk through all keyboard focusable elements in the dom tree,
looking the "closest" node. That is why it goes to the top one
in before all.

> > +        if (!(isMovingToRootDocument(focusedNode, candidate)
> > +            && (closestFocusCandidate.node
> > +            && (focusedNode->document() == closestFocusCandidate.node->document())))) {
> 
> You don't need so many parens here.

Fixed.

> >  namespace WebCore {
> >      enum FocusDirection {
> >          FocusDirectionForward = 0,
> > -        FocusDirectionBackward
> > +        FocusDirectionBackward,
> > +        FocusDirectionNone,
> > +        FocusDirectionUp,
> > +        FocusDirectionDown,
> > +        FocusDirectionLeft,
> > +        FocusDirectionRight
> >      };
> 
> Would making FocusDirectionNone have value 0 break anything? It would be
> preferable.

Fixed. It does not break anything, and indeed looks better.

> > +++ b/WebCore/page/SpatialNavigation.cpp
> 
> > +namespace WebCore {
> > +
> > +long long spatialDistance(FocusDirection, const IntRect&, const IntRect&);
> > +IntRect renderRectRelativeToRootDocument(RenderObject*);
> > +RectsAlignment alignmentForRects(FocusDirection, const IntRect&, const IntRect&);
> > +bool areRectsFullyAligned(FocusDirection, const IntRect&, const IntRect&);
> > +bool areRectsPartiallyAligned(FocusDirection, const IntRect&, const IntRect&);
> > +bool isRectInDirection(FocusDirection, const IntRect&, const IntRect&);
> 
> I'm not sure if we normally declare file-local functions as 'static'. Take a
> look at some other files to see.

Fixed. Made all file-local functions static.

> 
> > +// FIXME_tonikitoo: FocusCandidate distanceDataForNode(start, dest, direction)
> It's not clear what the action item is.

Fixed. Comment removed.

> > +long long distanceInDirection(Node* start, Node* dest, FocusDirection direction, FocusCandidate& candidate)
> > +{
> > +    long long& distance = candidate.distance;
> 
> You set distance to be a reference to candidate.distance here...
> 
> > +        // Reset distance if we are now in higher precedence case.
> > +        if (candidate.alignment < alignment && candidate.parentAlignment < alignment)
> > +            distance = cMaxDistance;
> 
> and then assign to it lower down. Why use the reference at all? This is hard to
> follow.

Right the logic here is: in case we find a node with a higher focus precedence
than the current best focus candidate (e.g. totally or partially aligned), 
we want to take that node regardless its distance. So I set current best candidate
node's current distance to the maximum possible value, which makes me sure that any
distance we get from |spatialDistance| later on is shorter.

I modified to comment in the code to better reflect that.

> > +        // FIXME_tonikitoo: make this assignment in the caller method ?
> 
> Either do it, or remove the FIXME.

Removed.

> We would normally put braces at if (useScrollOffset) {

Fixed.

> > +#define MIDDLE(direction, rect)       \
> > +    isHorizontalMove(direction) ?     \
> > +        rect.y() + rect.height() / 2: \
> > +        rect.x() + rect.width()  / 2;
> > +
> > +#define END(direction, rect)          \
> > +    isHorizontalMove(direction) ?     \
> > +        rect.y() + rect.height() :    \
> > +        rect.x() + rect.width();
> > +
> > +#define START(direction, rect)        \
> > +    isHorizontalMove(direction) ? rect.y() : rect.x();
> 
> Please convert these into inline functions.

Fixed. static inline functions added.

> > +// This method checks if rects |a| and |b| are fully aligned either vertical or
> 
> vertically

Fixed.

> > +// In essence, targets whose middle falls between the top or bottom of the current rect.
> 
> This isn't a complete sentence.

Fixed.

> > +    // About the logic below:
> 
> What about it?

Fixed. Comment added in the code.

> > +// * a = Current focused node.
> > +// * b = Focus candidate node.
> 
> In all these methods, rather than commenting what a and b are, you should just
> name them appropriately: curRect, targetRect, or something.

I agree w/ you, but it could make code harder to read, imho.
And comment is used three times, not much, again imho.
So in this round, I opted to leave it was it was, but if you
really prefer I can fix it as you wish. 
 
> > +        if (a.y() > b.y() + b.height()) {
> 
> use IntRect:bottom(), IntRect:right() here and in all these methods.

Fixed.

> You could also define some inline methods like:
> 
> bool below(const IntRect& r, int pos)
> {
>   return pos > r.bottom();
> }

Added:
   static inline bool belowOf(const intrect& rect a , const intrect& rect b)
and a correspondent |rightOf| function. is that ok ?

> to make this code more readable. You could also add IntPoint IntRect::center()
> const if you like (FloatRect has one).

Done in bug 35346.

> > +bool isMovingToRootDocument(Node* from, Node* to)
> > +{
> > +    if (!from || !to)
> > +        return false;
> > +
> > +    Document* rootDocument = to->document()->page()->mainFrame()->document();
> > +    return (to->document() == rootDocument && from->document() != to->document());
> > +}
> 
> The 'moving to' terminology is confusing. I think this would be clearer with:
> 
> bool isInRootDocument(Node*)
> and then put the other logic at the call site.

Fixed. Done.

> > +void deflateIfNeeded(IntRect& a, IntRect& b, int fudgeFactor)
> If needed for what?

I think comments in the caller site says it. See:

    // The bounding rectangle of two consecutive nodes can overlap. In such cases,
    // deflate both.
    deflateIfOverlapped(curRect, targetRect);

btw, i renamed function to |deflateIfOverlapped|.

> I think this needs one more round of changes.

very helpful review. thx

[WebKit Review Bot]

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

Failed to run "WebKitTools/Scripts/check-webkit-style" exit_code: 1
WebCore/page/SpatialNavigation.cpp:154:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
WebCore/page/SpatialNavigation.cpp:155:  Weird number of spaces at line-start.  Are you using a 4-space indent?  [whitespace/indent] [3]
Total errors found: 2 in 15 files


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

[WebKit Review Bot]

Attachment 49463 [details] did not build on chromium:
Build output: http://webkit-commit-queue.appspot.com/results/309301

[WebKit Review Bot]

Attachment 49463 [details] did not build on gtk:
Build output: http://webkit-commit-queue.appspot.com/results/308385

[WebKit Review Bot]

Attachment 49463 [details] did not build on qt:
Build output: http://webkit-commit-queue.appspot.com/results/308388

[Kenneth Rohde Christiansen]

belowOf(..)? That should just be called below(..) or mayube isBelow?

[Antonio Gomes]

Created attachment 49483 [details]
(committed in r55543) Add directional navigation to WebCore (v15.1)

Same patch as patch 49463 (v15) - see comment 64, but now:

* it builds (see bug 35346).
* fixed the style erros.
* replaces |belowOf| by |below| (kenneth's suggestion).

[Kenneth Rohde Christiansen]

Comment on attachment 49483 [details]
(committed in r55543) Add directional navigation to WebCore (v15.1)


> +void updateFocusCandidateIfCloser(Node* focusedNode, Node* candidate,
> +                                  long long distance, FocusCandidate& closestFocusCandidate)

> +void FocusController::findFocusableNodeInDirection(Document* document,
> +                                                   Node* focusedNode,
> +                                                   FocusDirection direction,
> +                                                   KeyboardEvent* event,
> +                                                   FocusCandidate& closestFocusCandidate)

According to our coding style guide these should be one line only. Could you please fix that before committing?

[Antonio Gomes]

I just got a first review round of the layout tests patch (see attachment 49076 [details]) with kenneth, and we decided:

1) to split this big patch in smallers ones as well, to help reviewers. Each one should come on its own bug. It makes sense because most of them are testing specific edge cases of spatial navigation usage that I faced during the development phase, and decided to create a unit test for it.

2) for this bug, I will be uploading a more generic test about the feature usage.

[Antonio Gomes]

Comment on attachment 49076 [details]
Add directional navigation to WebCore (LayoutTests - v1)

marking the patch as obsolete based on comment #72. a new one coming.

[Antonio Gomes]

The core patch of this feature has landed on trunk in http://trac.webkit.org/changeset/55543 , and it is currently referred as "Spatial Navigation".

Follow-up commits also landed, including:

* fix Mac build:
- r55544 (thx Jesus);
- r55550, r55553 and 55554 (thx so much to Simon Fraser).

* fix Windows build: r55552 (by my self).

I am considering this bug now as FIXED, and all follow-up work (yeah, feature not yet complete) are going to happen own their own bugs. I will be linking them as dependency of this one for the record.

Follow up work includes (but not limited to):

* Land all the layout tests I have for specific behaviour of the feature (unit overflow, table traversal, iframe traversal,  etc);
* Fix scrollable content traversal.
* Improve the initial focus insertion.
* Provide hooks for browser clients to customize the scroll action.
* Fix site specific issues ...

[Antonio Gomes]

Bug 46905 is tracking the remaining existing spatial navigation work.

This one has done its job.