spatial_navigation.cc | Explore in Territory

/*
 * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies)
 * Copyright (C) 2009 Antonio Gomes <[email protected]>
 *
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE COMPUTER, INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/351564777): Remove this and convert code to safer constructs.
#pragma allow_unsafe_buffers
#endif

#include "third_party/blink/renderer/core/page/spatial_navigation.h"

#include "base/containers/adapters.h"
#include "third_party/blink/public/mojom/scroll/scrollbar_mode.mojom-blink.h"
#include "third_party/blink/renderer/core/dom/node_traversal.h"
#include "third_party/blink/renderer/core/frame/local_frame.h"
#include "third_party/blink/renderer/core/frame/local_frame_view.h"
#include "third_party/blink/renderer/core/frame/settings.h"
#include "third_party/blink/renderer/core/frame/visual_viewport.h"
#include "third_party/blink/renderer/core/html/html_area_element.h"
#include "third_party/blink/renderer/core/html/html_frame_owner_element.h"
#include "third_party/blink/renderer/core/html/html_image_element.h"
#include "third_party/blink/renderer/core/html_names.h"
#include "third_party/blink/renderer/core/input/event_handler.h"
#include "third_party/blink/renderer/core/layout/layout_box.h"
#include "third_party/blink/renderer/core/layout/layout_inline.h"
#include "third_party/blink/renderer/core/layout/layout_view.h"
#include "third_party/blink/renderer/core/page/frame_tree.h"
#include "third_party/blink/renderer/core/page/page.h"
#include "third_party/blink/renderer/core/paint/paint_layer.h"
#include "third_party/blink/renderer/core/paint/paint_layer_scrollable_area.h"
#include "ui/gfx/geometry/rect.h"

namespace blink {

// A small integer that easily fits into a double with a good margin for
// arithmetic. In particular, we don't want to use
// std::numeric_limits<double>::lowest() because, if subtracted, it becomes
// NaN which will make all following arithmetic NaN too (an unusable number).
constexpr double kMinDistance = …;
// Assign negative values to the distance value to give the candidate a higher
// priority.
// kPriorityClassA is for elements in separate layers such as pop-ups.
// kPriorityClassB is for intersecting elements.
constexpr double kPriorityClassA = …;
constexpr double kPriorityClassB = …;

constexpr int kFudgeFactor = …;

FocusCandidate::FocusCandidate(Node* node, SpatialNavigationDirection direction)
    : … { … }

bool IsSpatialNavigationEnabled(const LocalFrame* frame) { … }

static bool RectsIntersectOnOrthogonalAxis(SpatialNavigationDirection direction,
                                           const PhysicalRect& a,
                                           const PhysicalRect& b) { … }

// Determines if a candidate element is in a specific direction.
// It has to deal with overlapping situations.
// See https://github.com/w3c/csswg-drafts/issues/4483 for details.

// Return true if rect |a| is below |b|. False otherwise.
// For overlapping rects, |a| is considered to be below |b|,
// if the top edge of |a| is below the top edge of |b|.
static inline bool Below(const PhysicalRect& a, const PhysicalRect& b) { … }

// Return true if rect |a| is above |b|. False otherwise.
// For overlapping rects, |a| is considered to be above |b|,
// if the bottom edge of |a| is above the bottom edge of |b|.
static inline bool Above(const PhysicalRect& a, const PhysicalRect& b) { … }

// Return true if rect |a| is on the right of |b|. False otherwise.
// For overlapping rects, |a| is considered to be on the right of |b|,
// if the left edge of |a| is on the right of the left edge of |b|.
static inline bool RightOf(const PhysicalRect& a, const PhysicalRect& b) { … }

// Return true if rect |a| is on the left of |b|. False otherwise.
// For overlapping rects, |a| is considered to be on the left of |b|,
// if the right edge of |a| is on the left of the right edge of |b|.
static inline bool LeftOf(const PhysicalRect& a, const PhysicalRect& b) { … }

static bool IsRectInDirection(SpatialNavigationDirection direction,
                              const PhysicalRect& cur_rect,
                              const PhysicalRect& target_rect) { … }

int LineBoxes(const LayoutObject& layout_object) { … }

bool IsFragmentedInline(const LayoutObject& layout_object) { … }

gfx::RectF RectInViewport(const Node& node) { … }

// Answers true if |node| is completely outside the user's (visual) viewport.
// This logic is used by spatnav to rule out offscreen focus candidates and an
// offscreen activeElement. When activeElement is offscreen, spatnav doesn't use
// it as the search origin; the search will start at an edge of the visual
// viewport instead.
// TODO(crbug.com/889840): Fix VisibleBoundsInVisualViewport().
// If VisibleBoundsInVisualViewport() would have taken "element-clips" into
// account, spatnav could have called it directly; no need to check the
// LayoutObject's VisibleContentRect.
bool IsOffscreen(const Node* node) { … }

ScrollableArea* ScrollableAreaFor(const Node* node) { … }

bool IsUnobscured(const FocusCandidate& candidate) { … }

bool HasRemoteFrame(const Node* node) { … }

bool ScrollInDirection(Node* container, SpatialNavigationDirection direction) { … }

bool IsScrollableNode(const Node* node) { … }

Node* ScrollableAreaOrDocumentOf(Node* node) { … }

bool IsScrollableAreaOrDocument(const Node* node) { … }

bool CanScrollInDirection(const Node* container,
                          SpatialNavigationDirection direction) { … }

bool CanScrollInDirection(const LocalFrame* frame,
                          SpatialNavigationDirection direction) { … }

PhysicalRect NodeRectInRootFrame(const Node* node) { … }

// This method calculates the exitPoint from the startingRect and the entryPoint
// into the candidate rect.  The line between those 2 points is the closest
// distance between the 2 rects.  Takes care of overlapping rects, defining
// points so that the distance between them is zero where necessary.
void EntryAndExitPointsForDirection(SpatialNavigationDirection direction,
                                    const PhysicalRect& starting_rect,
                                    const PhysicalRect& potential_rect,
                                    LayoutPoint& exit_point,
                                    LayoutPoint& entry_point) { … }

double ProjectedOverlap(SpatialNavigationDirection direction,
                        PhysicalRect current,
                        PhysicalRect candidate) { … }

double Alignment(SpatialNavigationDirection direction,
                 PhysicalRect current,
                 PhysicalRect candidate) { … }

bool BothOnTopmostPaintLayerInStackingContext(
    const FocusCandidate& current_interest,
    const FocusCandidate& candidate) { … }

double ComputeDistanceDataForNode(SpatialNavigationDirection direction,
                                  const FocusCandidate& current_interest,
                                  const FocusCandidate& candidate) { … }

// Returns a thin rectangle that represents one of |box|'s edges.
// To not intersect elements that are positioned inside |box|, we add one
// LayoutUnit of margin that puts the returned slice "just outside" |box|.
PhysicalRect OppositeEdge(SpatialNavigationDirection side,
                          const PhysicalRect& box,
                          LayoutUnit thickness) { … }

PhysicalRect StartEdgeForAreaElement(const HTMLAreaElement& area,
                                     SpatialNavigationDirection direction) { … }

HTMLFrameOwnerElement* FrameOwnerElement(const FocusCandidate& candidate) { … }

// The visual viewport's rect (given in the root frame's coordinate space).
PhysicalRect RootViewport(const LocalFrame* current_frame) { … }

// Ignores fragments that are completely offscreen.
// Returns the first one that is not offscreen, in the given iterator range.
template <class Iterator>
PhysicalRect FirstVisibleFragment(const PhysicalRect& visibility,
                                  Iterator fragment,
                                  Iterator end) { … }

LayoutUnit GetLogicalHeight(const PhysicalRect& rect,
                            const LayoutObject& layout_object) { … }

void SetLogicalHeight(PhysicalRect& rect,
                      const LayoutObject& layout_object,
                      LayoutUnit height) { … }

LayoutUnit TallestInlineAtomicChild(const LayoutObject& layout_object) { … }

//   "Although margins, borders, and padding of non-replaced elements do not
//    enter into the line box calculation, they are still rendered around
//    inline boxes. This means that if the height specified by line-height is
//    less than the content height of contained boxes, backgrounds and colors
//    of padding and borders may "bleed" into adjoining line boxes". [1]
// [1] https://drafts.csswg.org/css2/#leading
// [2] https://drafts.csswg.org/css2/#line-box
// [3] https://drafts.csswg.org/css2/#atomic-inline-level-boxes
//
// If an inline box is "bleeding", ShrinkInlineBoxToLineBox shrinks its
// rect to the size of of its "line box" [2]. We need to do so because
// "bleeding" can make links intersect vertically. We need to avoid that
// overlap because it could make links on the same line (to the left or right)
// unreachable as SpatNav's distance formula favors intersecting rects (on the
// line below or above).
PhysicalRect ShrinkInlineBoxToLineBox(const LayoutObject& layout_object,
                                      PhysicalRect node_rect,
                                      int line_boxes) { … }

// TODO(crbug.com/1131419): Add tests and support for other writing-modes.
PhysicalRect SearchOriginFragment(const PhysicalRect& visible_part,
                                  const LayoutObject& fragmented,
                                  const SpatialNavigationDirection direction) { … }

// Spatnav uses this rectangle to measure distances to focus candidates.
// The search origin is either activeElement F itself, if it's being at least
// partially visible, or else, its first [partially] visible scroller. If both
// F and its enclosing scroller are completely off-screen, we recurse to the
// scroller’s scroller ... all the way up until the root frame's document.
// The root frame's document is a good base case because it's, per definition,
// a visible scrollable area.
PhysicalRect SearchOrigin(const PhysicalRect& viewport_rect_of_root_frame,
                          Node* focus_node,
                          const SpatialNavigationDirection direction) { … }

}  // namespace blink
chromium/third_party/blink/renderer/core/page/spatial_navigation.cc
