1 /*

     2  * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)

     3  * Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org>

     4  *

     5  * All rights reserved.

     6  *

     7  * Redistribution and use in source and binary forms, with or without

     8  * modification, are permitted provided that the following conditions

     9  * are met:

    10  * 1. Redistributions of source code must retain the above copyright

    11  *    notice, this list of conditions and the following disclaimer.

    12  * 2. Redistributions in binary form must reproduce the above copyright

    13  *    notice, this list of conditions and the following disclaimer in the

    14  *    documentation and/or other materials provided with the distribution.

    15  *

    16  * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY

    17  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE

    18  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR

    19  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR

    20  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,

    21  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,

    22  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR

    23  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY

    24  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

    25  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

    26  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

    27  */

    28 

    29 #include "config.h"

    30 #include "SpatialNavigation.h"

    31 

    32 #include "Frame.h"

    33 #include "FrameTree.h"

    34 #include "FrameView.h"

    35 #include "HTMLFrameOwnerElement.h"

    36 #include "IntRect.h"

    37 #include "Node.h"

    38 #include "Page.h"

    39 

    40 namespace WebCore {

    41 

    42 static long long spatialDistance(FocusDirection, const IntRect&, const IntRect&);

    43 static IntRect renderRectRelativeToRootDocument(RenderObject*);

    44 static RectsAlignment alignmentForRects(FocusDirection, const IntRect&, const IntRect&);

    45 static bool areRectsFullyAligned(FocusDirection, const IntRect&, const IntRect&);

    46 static bool areRectsPartiallyAligned(FocusDirection, const IntRect&, const IntRect&);

    47 static bool isRectInDirection(FocusDirection, const IntRect&, const IntRect&);

    48 static void deflateIfOverlapped(IntRect&, IntRect&);

    49 static bool checkNegativeCoordsForNode(Node*, const IntRect&);

    50 

    51 void distanceDataForNode(FocusDirection direction, Node* start, FocusCandidate& candidate)

    52 {

    53     RenderObject* startRender = start->renderer();

    54     if (!startRender) {

    55         candidate.distance = maxDistance();

    56         return;

    57     }

    58 

    59     RenderObject* destRender = candidate.node->renderer();

    60     if (!destRender) {

    61         candidate.distance = maxDistance();

    62         return;

    63     }

    64 

    65     IntRect curRect = renderRectRelativeToRootDocument(startRender);

    66     IntRect targetRect  = renderRectRelativeToRootDocument(destRender);

    67 

    68     // The bounding rectangle of two consecutive nodes can overlap. In such cases,

    69     // deflate both.

    70     deflateIfOverlapped(curRect, targetRect);

    71 

    72     // If empty rects or negative width or height, bail out.

    73     if (curRect.isEmpty() || targetRect.isEmpty()

    74      || targetRect.width() <= 0 || targetRect.height() <= 0) {

    75         candidate.distance = maxDistance();

    76         return;

    77     }

    78 

    79     // Negative coordinates can be used if node is scrolled up offscreen.

    80     if (!checkNegativeCoordsForNode(start, curRect)) {

    81         candidate.distance = maxDistance();

    82         return;

    83     }

    84 

    85     if (!checkNegativeCoordsForNode(candidate.node, targetRect)) {

    86         candidate.distance = maxDistance();

    87         return;

    88     }

    89 

    90     if (!isRectInDirection(direction, curRect, targetRect)) {

    91         candidate.distance = maxDistance();

    92         return;

    93     }

    94 

    95     // The distance between two nodes is not to be considered alone when evaluating/looking

    96     // for the best focus candidate node. Alignment of rects can be also a good point to be

    97     // considered in order to make the algorithm to behavior in a more intuitive way.

    98     candidate.alignment = alignmentForRects(direction, curRect, targetRect);

    99     candidate.distance = spatialDistance(direction, curRect, targetRect);

   100 }

   101 

   102 // FIXME: This function does not behave correctly with transformed frames.

   103 static IntRect renderRectRelativeToRootDocument(RenderObject* render)

   104 {

   105     ASSERT(render);

   106 

   107     IntRect rect(render->absoluteClippedOverflowRect());

   108 

   109     if (rect.isEmpty()) {

   110         Element* e = static_cast<Element*>(render->node());

   111         rect = e->getRect();

   112     }

   113 

   114     // In cases when the |render|'s associated node is in a scrollable inner

   115     // document, we only consider its scrollOffset if it is not offscreen.

   116     Node* node = render->node();

   117     Document* mainDocument = node->document()->page()->mainFrame()->document();

   118     bool considerScrollOffset = !(hasOffscreenRect(node) && node->document() != mainDocument);

   119 

   120     if (considerScrollOffset) {

   121         if (FrameView* frameView = render->node()->document()->view())

   122             rect.move(-frameView->scrollOffset());

   123     }

   124 

   125     // Handle nested frames.

   126     for (Frame* frame = render->document()->frame(); frame; frame = frame->tree()->parent()) {

   127         if (HTMLFrameOwnerElement* ownerElement = frame->ownerElement())

   128             rect.move(ownerElement->offsetLeft(), ownerElement->offsetTop());

   129     }

   130 

   131     return rect;

   132 }

   133 

   134 static RectsAlignment alignmentForRects(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect)

   135 {

   136     if (areRectsFullyAligned(direction, curRect, targetRect))

   137         return Full;

   138 

   139     if (areRectsPartiallyAligned(direction, curRect, targetRect))

   140         return Partial;

   141 

   142     return None;

   143 }

   144 

   145 static inline bool isHorizontalMove(FocusDirection direction)

   146 {

   147     return direction == FocusDirectionLeft || direction == FocusDirectionRight;

   148 }

   149 

   150 static inline int start(FocusDirection direction, const IntRect& rect)

   151 {

   152     return isHorizontalMove(direction) ? rect.y() : rect.x();

   153 }

   154 

   155 static inline int middle(FocusDirection direction, const IntRect& rect)

   156 {

   157     IntPoint center(rect.center());

   158     return isHorizontalMove(direction) ? center.y(): center.x();

   159 }

   160 

   161 static inline int end(FocusDirection direction, const IntRect& rect)

   162 {

   163     return isHorizontalMove(direction) ? rect.bottom() : rect.right();

   164 }

   165 

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

   167 // horizontally. In general, rects whose central point falls between the top or

   168 // bottom of each other are considered fully aligned.

   169 // Rects that match this criteria are preferable target nodes in move focus changing

   170 // operations.

   171 // * a = Current focused node's rect.

   172 // * b = Focus candidate node's rect.

   173 static bool areRectsFullyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)

   174 {

   175     int aStart, bStart, aEnd, bEnd;

   176 

   177     switch (direction) {

   178     case FocusDirectionLeft:

   179         aStart = a.x();

   180         bEnd = b.right();

   181         break;

   182     case FocusDirectionRight:

   183         aStart = b.x();

   184         bEnd = a.right();

   185         break;

   186     case FocusDirectionUp:

   187         aStart = a.y();

   188         bEnd = b.y();

   189         break;

   190     case FocusDirectionDown:

   191         aStart = b.y();

   192         bEnd = a.y();

   193         break;

   194     default:

   195         ASSERT_NOT_REACHED();

   196         return false;

   197     }

   198 

   199     if (aStart < bEnd)

   200         return false;

   201 

   202     aStart = start(direction, a);

   203     bStart = start(direction, b);

   204 

   205     int aMiddle = middle(direction, a);

   206     int bMiddle = middle(direction, b);

   207 

   208     aEnd = end(direction, a);

   209     bEnd = end(direction, b);

   210 

   211     // Picture of the totally aligned logic:

   212     //

   213     //     Horizontal    Vertical        Horizontal     Vertical

   214     //  ****************************  *****************************

   215     //  *  _          *   _ _ _ _  *  *         _   *      _ _    *

   216     //  * |_|     _   *  |_|_|_|_| *  *  _     |_|  *     |_|_|   *

   217     //  * |_|....|_|  *      .     *  * |_|....|_|  *       .     *

   218     //  * |_|    |_| (1)     .     *  * |_|    |_| (2)      .     *

   219     //  * |_|         *     _._    *  *        |_|  *    _ _._ _  *

   220     //  *             *    |_|_|   *  *             *   |_|_|_|_| *

   221     //  *             *            *  *             *             *

   222     //  ****************************  *****************************

   223 

   224     //     Horizontal    Vertical        Horizontal     Vertical

   225     //  ****************************  *****************************

   226     //  *  _......_   *   _ _ _ _  *  *  _          *    _ _ _ _  *

   227     //  * |_|    |_|  *  |_|_|_|_| *  * |_|     _   *   |_|_|_|_| *

   228     //  * |_|    |_|  *  .         *  * |_|    |_|  *           . *

   229     //  * |_|        (3) .         *  * |_|....|_| (4)          . *

   230     //  *             *  ._ _      *  *             *        _ _. *

   231     //  *             *  |_|_|     *  *             *       |_|_| *

   232     //  *             *            *  *             *             *

   233     //  ****************************  *****************************

   234 

   235     return ((bMiddle >= aStart && bMiddle <= aEnd) // (1)

   236             || (aMiddle >= bStart && aMiddle <= bEnd) // (2)

   237             || (bStart == aStart) // (3)

   238             || (bEnd == aEnd)); // (4)

   239 }

   240 

   241 // This method checks if |start| and |dest| have a partial intersection, either

   242 // horizontally or vertically.

   243 // * a = Current focused node's rect.

   244 // * b = Focus candidate node's rect.

   245 static bool areRectsPartiallyAligned(FocusDirection direction, const IntRect& a, const IntRect& b)

   246 {

   247     int aStart  = start(direction, a);

   248     int bStart  = start(direction, b);

   249     int bMiddle = middle(direction, b);

   250     int aEnd = end(direction, a);

   251     int bEnd = end(direction, b);

   252 

   253     // Picture of the partially aligned logic:

   254     //

   255     //    Horizontal       Vertical

   256     // ********************************

   257     // *  _            *   _ _ _      *

   258     // * |_|           *  |_|_|_|     *

   259     // * |_|.... _     *      . .     *

   260     // * |_|    |_|    *      . .     *

   261     // * |_|....|_|    *      ._._ _  *

   262     // *        |_|    *      |_|_|_| *

   263     // *        |_|    *              *

   264     // *               *              *

   265     // ********************************

   266     //

   267     // ... and variants of the above cases.

   268     return ((bStart >= aStart && bStart <= aEnd)

   269             || (bStart >= aStart && bStart <= aEnd)

   270             || (bEnd >= aStart && bEnd <= aEnd)

   271             || (bMiddle >= aStart && bMiddle <= aEnd)

   272             || (bEnd >= aStart && bEnd <= aEnd));

   273 }

   274 

   275 // Return true if rect |a| is below |b|. False otherwise.

   276 static inline bool below(const IntRect& a, const IntRect& b)

   277 {

   278     return a.y() > b.bottom();

   279 }

   280 

   281 // Return true if rect |a| is on the right of |b|. False otherwise.

   282 static inline bool rightOf(const IntRect& a, const IntRect& b)

   283 {

   284     return a.x() > b.right();

   285 }

   286 

   287 // * a = Current focused node's rect.

   288 // * b = Focus candidate node's rect.

   289 static long long spatialDistance(FocusDirection direction, const IntRect& a, const IntRect& b)

   290 {

   291     int x1 = 0, y1 = 0, x2 = 0, y2 = 0;

   292 

   293     if (direction == FocusDirectionLeft) {

   294         // #1  |--|

   295         //

   296         // #2  |--|  |--|

   297         //

   298         // #3  |--|

   299 

   300         x1 = a.x();

   301         x2 = b.right();

   302 

   303         if (below(a, b)) {

   304             // #1 The a rect is below b.

   305             y1 = a.y();

   306             y2 = b.bottom();

   307         } else if (below(b, a)) {

   308             // #3 The b rect is below a.

   309             y1 = a.bottom();

   310             y2 = b.y();

   311         } else {

   312             // #2 Both b and a share some common y's.

   313             y1 = 0;

   314             y2 = 0;

   315         }

   316     } else if (direction == FocusDirectionRight) {

   317         //        |--|  #1

   318         //

   319         //  |--|  |--|  #2

   320         //

   321         //        |--|  #3

   322 

   323         x1 = a.right();

   324         x2 = b.x();

   325 

   326         if (below(a, b)) {

   327             // #1 The b rect is above a.

   328             y1 = a.y();

   329             y2 = b.bottom();

   330         } else if (below(b, a)) {

   331             // #3 The b rect is below a.

   332             y1 = a.bottom();

   333             y2 = b.y();

   334         } else {

   335             // #2 Both b and a share some common y's.

   336             y1 = 0;

   337             y2 = 0;

   338         }

   339     } else if (direction == FocusDirectionUp) {

   340         //

   341         //   #1    #2    #3

   342         //

   343         //  |--|  |--|  |--|

   344         //

   345         //        |--|

   346 

   347         y1 = a.y();

   348         y2 = b.bottom();

   349 

   350         if (rightOf(a, b)) {

   351             // #1 The b rect is to the left of a.

   352             x1 = a.x();

   353             x2 = b.right();

   354         } else if (rightOf(b, a)) {

   355             // #3 The b rect is to the right of a.

   356             x1 = a.right();

   357             x2 = b.x();

   358         } else {

   359             // #2 Both b and a share some common x's.

   360             x1 = 0;

   361             x2 = 0;

   362         }

   363     } else if (direction == FocusDirectionDown) {

   364         //        |--|

   365         //

   366         //  |--|  |--|  |--|

   367         //

   368         //   #1    #2    #3

   369 

   370         y1 = a.bottom();

   371         y2 = b.y();

   372 

   373         if (rightOf(a, b)) {

   374             // #1 The b rect is to the left of a.

   375             x1 = a.x();

   376             x2 = b.right();

   377         } else if (rightOf(b, a)) {

   378             // #3 The b rect is to the right of a

   379             x1 = a.right();

   380             x2 = b.x();

   381         } else {

   382             // #2 Both b and a share some common x's.

   383             x1 = 0;

   384             x2 = 0;

   385         }

   386     }

   387 

   388     long long dx = x1 - x2;

   389     long long dy = y1 - y2;

   390 

   391     long long distance = (dx * dx) + (dy * dy);

   392 

   393     if (distance < 0)

   394         distance *= -1;

   395 

   396     return distance;

   397 }

   398 

   399 static bool isRectInDirection(FocusDirection direction, const IntRect& curRect, const IntRect& targetRect)

   400 {

   401     IntPoint center(targetRect.center());

   402     int targetMiddle = isHorizontalMove(direction) ? center.x() : center.y();

   403 

   404     switch (direction) {

   405     case FocusDirectionLeft:

   406         return targetMiddle < curRect.x();

   407     case FocusDirectionRight:

   408         return targetMiddle > curRect.right();

   409     case FocusDirectionUp:

   410         return targetMiddle < curRect.y();

   411     case FocusDirectionDown:

   412         return targetMiddle > curRect.bottom();

   413     default:

   414         ASSERT_NOT_REACHED();

   415     }

   416 

   417     return false;

   418 }

   419 

   420 // Checks if |node| is offscreen the visible area (viewport) of its container

   421 // document. In case it is, one can scroll in direction or take any different

   422 // desired action later on.

   423 bool hasOffscreenRect(Node* node)

   424 {

   425     // Get the FrameView in which |node| is (which means the current viewport if |node|

   426     // is not in an inner document), so we can check if its content rect is visible

   427     // before we actually move the focus to it.

   428     FrameView* frameView = node->document()->view();

   429     if (!frameView)

   430         return true;

   431 

   432     IntRect containerViewportRect = frameView->visibleContentRect();

   433 

   434     RenderObject* render = node->renderer();

   435     if (!render)

   436         return true;

   437 

   438     IntRect rect(render->absoluteClippedOverflowRect());

   439     if (rect.isEmpty())

   440         return true;

   441 

   442     return !containerViewportRect.intersects(rect);

   443 }

   444 

   445 // In a bottom-up way, this method tries to scroll |frame| in a given direction

   446 // |direction|, going up in the frame tree hierarchy in case it does not succeed.

   447 bool scrollInDirection(Frame* frame, FocusDirection direction)

   448 {

   449     if (!frame)

   450         return false;

   451 

   452     ScrollDirection scrollDirection;

   453 

   454     switch (direction) {

   455     case FocusDirectionLeft:

   456         scrollDirection = ScrollLeft;

   457         break;

   458     case FocusDirectionRight:

   459         scrollDirection = ScrollRight;

   460         break;

   461     case FocusDirectionUp:

   462         scrollDirection = ScrollUp;

   463         break;

   464     case FocusDirectionDown:

   465         scrollDirection = ScrollDown;

   466         break;

   467     default:

   468         return false;

   469     }

   470 

   471     return frame->eventHandler()->scrollRecursively(scrollDirection, ScrollByLine);

   472 }

   473 

   474 void scrollIntoView(Element* element)

   475 {

   476     // NOTE: Element's scrollIntoView method could had been used here, but

   477     // it is preferable to inflate |element|'s bounding rect a bit before

   478     // scrolling it for accurate reason.

   479     // Element's scrollIntoView method does not provide this flexibility.

   480     IntRect bounds = element->getRect();

   481     bounds.inflate(fudgeFactor());

   482     element->renderer()->enclosingLayer()->scrollRectToVisible(bounds);

   483 }

   484 

   485 bool isInRootDocument(Node* node)

   486 {

   487     if (!node)

   488         return false;

   489 

   490     Document* rootDocument = node->document()->page()->mainFrame()->document();

   491     return node->document() == rootDocument;

   492 }

   493 

   494 static void deflateIfOverlapped(IntRect& a, IntRect& b)

   495 {

   496     if (!a.intersects(b) || a.contains(b) || b.contains(a))

   497         return;

   498 

   499     int deflateFactor = -fudgeFactor();

   500 

   501     // Avoid negative width or height values.

   502     if ((a.width() + 2 * deflateFactor > 0) && (a.height() + 2 * deflateFactor > 0))

   503         a.inflate(deflateFactor);

   504 

   505     if ((b.width() + 2 * deflateFactor > 0) && (b.height() + 2 * deflateFactor > 0))

   506         b.inflate(deflateFactor);

   507 }

   508 

   509 static bool checkNegativeCoordsForNode(Node* node, const IntRect& curRect)

   510 {

   511     ASSERT(node || node->renderer());

   512 

   513     if (curRect.x() > 0 && curRect.y() > 0)

   514         return true;

   515 

   516     bool canBeScrolled = false;

   517 

   518     RenderObject* renderer = node->renderer();

   519     for (; renderer; renderer = renderer->parent()) {

   520         if (renderer->isBox() && toRenderBox(renderer)->canBeScrolledAndHasScrollableArea()) {

   521             canBeScrolled = true;

   522             break;

   523         }

   524     }

   525 

   526     return canBeScrolled;

   527 }

   528 

   529 } // namespace WebCore