| /* |
| * Copyright (C) 2009 Nokia Corporation and/or its subsidiary(-ies) |
| * Copyright (C) 2009 Antonio Gomes <tonikitoo@webkit.org> |
| * |
| * 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. |
| */ |
| |
| #include "third_party/blink/renderer/core/page/spatial_navigation.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 "third_party/blink/renderer/platform/geometry/int_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 = std::numeric_limits<int>::lowest(); |
| constexpr double kPriorityClassA = kMinDistance; |
| constexpr double kPriorityClassB = kMinDistance / 2; |
| |
| constexpr int kFudgeFactor = 2; |
| |
| FocusCandidate::FocusCandidate(Node* node, SpatialNavigationDirection direction) |
| : visible_node(nullptr), focusable_node(nullptr), is_offscreen(true) { |
| DCHECK(node); |
| DCHECK(node->IsElementNode()); |
| |
| if (auto* area = DynamicTo<HTMLAreaElement>(*node)) { |
| HTMLImageElement* image = area->ImageElement(); |
| if (!image || !image->GetLayoutObject()) |
| return; |
| |
| visible_node = image; |
| rect_in_root_frame = StartEdgeForAreaElement(*area, direction); |
| } else { |
| if (!node->GetLayoutObject()) |
| return; |
| |
| visible_node = node; |
| rect_in_root_frame = NodeRectInRootFrame(node); |
| |
| // Remove any overlap with line boxes *above* the search origin. |
| rect_in_root_frame = |
| ShrinkInlineBoxToLineBox(*node->GetLayoutObject(), rect_in_root_frame); |
| } |
| |
| focusable_node = node; |
| is_offscreen = IsOffscreen(visible_node); |
| } |
| |
| bool IsSpatialNavigationEnabled(const LocalFrame* frame) { |
| return (frame && frame->GetSettings() && |
| frame->GetSettings()->GetSpatialNavigationEnabled()); |
| } |
| |
| static bool RectsIntersectOnOrthogonalAxis(SpatialNavigationDirection direction, |
| const PhysicalRect& a, |
| const PhysicalRect& b) { |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| case SpatialNavigationDirection::kRight: |
| return a.Bottom() > b.Y() && a.Y() < b.Bottom(); |
| case SpatialNavigationDirection::kUp: |
| case SpatialNavigationDirection::kDown: |
| return a.Right() > b.X() && a.X() < b.Right(); |
| default: |
| NOTREACHED(); |
| return false; |
| } |
| } |
| |
| // Return true if rect |a| is below |b|. False otherwise. |
| // For overlapping rects, |a| is considered to be below |b| |
| // if both edges of |a| are below the respective ones of |b|. |
| static inline bool Below(const PhysicalRect& a, const PhysicalRect& b) { |
| return a.Y() >= b.Bottom() || (a.Y() >= b.Y() && a.Bottom() > b.Bottom() && |
| a.X() < b.Right() && a.Right() > b.X()); |
| } |
| |
| // 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 both edges of |a| are on the right of the respective ones of |b|. |
| static inline bool RightOf(const PhysicalRect& a, const PhysicalRect& b) { |
| return a.X() >= b.Right() || (a.X() >= b.X() && a.Right() > b.Right() && |
| a.Y() < b.Bottom() && a.Bottom() > b.Y()); |
| } |
| |
| static bool IsRectInDirection(SpatialNavigationDirection direction, |
| const PhysicalRect& cur_rect, |
| const PhysicalRect& target_rect) { |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| return RightOf(cur_rect, target_rect); |
| case SpatialNavigationDirection::kRight: |
| return RightOf(target_rect, cur_rect); |
| case SpatialNavigationDirection::kUp: |
| return Below(cur_rect, target_rect); |
| case SpatialNavigationDirection::kDown: |
| return Below(target_rect, cur_rect); |
| default: |
| NOTREACHED(); |
| return false; |
| } |
| } |
| |
| int LineBoxes(const LayoutObject& layout_object) { |
| if (!layout_object.IsInline() || layout_object.IsAtomicInlineLevel()) |
| return 1; |
| |
| // If it has empty quads, it's most likely not a line broken ("fragmented") |
| // text. <a><div></div></a> has for example one empty rect. |
| Vector<FloatQuad> quads; |
| layout_object.AbsoluteQuads(quads); |
| for (const FloatQuad& quad : quads) { |
| if (quad.IsEmpty()) |
| return 1; |
| } |
| |
| return quads.size(); |
| } |
| |
| bool IsFragmentedInline(const LayoutObject& layout_object) { |
| return LineBoxes(layout_object) > 1; |
| } |
| |
| FloatRect RectInViewport(const Node& node) { |
| LocalFrameView* frame_view = node.GetDocument().View(); |
| if (!frame_view) |
| return FloatRect(); |
| |
| DCHECK(!frame_view->NeedsLayout()); |
| |
| LayoutObject* object = node.GetLayoutObject(); |
| if (!object) |
| return FloatRect(); |
| |
| PhysicalRect rect_in_root_frame = NodeRectInRootFrame(&node); |
| |
| // Convert to the visual viewport which will account for pinch zoom. |
| VisualViewport& visual_viewport = |
| object->GetDocument().GetPage()->GetVisualViewport(); |
| FloatRect rect_in_viewport = |
| visual_viewport.RootFrameToViewport(FloatRect(rect_in_root_frame)); |
| |
| // RootFrameToViewport doesn't clip so manually apply the viewport clip here. |
| FloatRect viewport_rect = |
| FloatRect(FloatPoint(), FloatSize(visual_viewport.Size())); |
| rect_in_viewport.Intersect(viewport_rect); |
| |
| return rect_in_viewport; |
| } |
| |
| // 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) { |
| DCHECK(node); |
| return RectInViewport(*node).IsEmpty(); |
| } |
| |
| ScrollableArea* ScrollableAreaFor(const Node* node) { |
| if (node->IsDocumentNode()) { |
| LocalFrameView* view = node->GetDocument().View(); |
| if (!view) |
| return nullptr; |
| |
| return view->GetScrollableArea(); |
| } |
| |
| LayoutObject* object = node->GetLayoutObject(); |
| if (!object || !object->IsBox()) |
| return nullptr; |
| |
| return To<LayoutBox>(object)->GetScrollableArea(); |
| } |
| |
| bool IsUnobscured(const FocusCandidate& candidate) { |
| DCHECK(candidate.visible_node); |
| |
| const LocalFrame* local_main_frame = DynamicTo<LocalFrame>( |
| candidate.visible_node->GetDocument().GetPage()->MainFrame()); |
| if (!local_main_frame) |
| return false; |
| |
| // TODO(crbug.com/955952): We cannot evaluate visibility for media element |
| // using hit test since attached media controls cover media element. |
| if (candidate.visible_node->IsMediaElement()) |
| return true; |
| |
| PhysicalRect viewport_rect( |
| local_main_frame->GetPage()->GetVisualViewport().VisibleContentRect()); |
| PhysicalRect interesting_rect = |
| Intersection(candidate.rect_in_root_frame, viewport_rect); |
| |
| if (interesting_rect.IsEmpty()) |
| return false; |
| |
| HitTestLocation location(interesting_rect); |
| HitTestResult result = |
| local_main_frame->GetEventHandler().HitTestResultAtLocation( |
| location, HitTestRequest::kReadOnly | HitTestRequest::kListBased | |
| HitTestRequest::kIgnoreZeroOpacityObjects | |
| HitTestRequest::kAllowChildFrameContent); |
| |
| const HitTestResult::NodeSet& nodes = result.ListBasedTestResult(); |
| for (auto hit_node = nodes.rbegin(); hit_node != nodes.rend(); ++hit_node) { |
| if (candidate.visible_node->ContainsIncludingHostElements(**hit_node)) |
| return true; |
| |
| if (FrameOwnerElement(candidate) && |
| FrameOwnerElement(candidate) |
| ->contentDocument() |
| ->ContainsIncludingHostElements(**hit_node)) |
| return true; |
| } |
| |
| return false; |
| } |
| |
| bool HasRemoteFrame(const Node* node) { |
| auto* frame_owner_element = DynamicTo<HTMLFrameOwnerElement>(node); |
| if (!frame_owner_element) |
| return false; |
| |
| return frame_owner_element->ContentFrame() && |
| frame_owner_element->ContentFrame()->IsRemoteFrame(); |
| } |
| |
| bool ScrollInDirection(Node* container, SpatialNavigationDirection direction) { |
| DCHECK(container); |
| |
| if (!CanScrollInDirection(container, direction)) |
| return false; |
| |
| int dx = 0; |
| int dy = 0; |
| int pixels_per_line_step = |
| ScrollableArea::PixelsPerLineStep(container->GetDocument().GetFrame()); |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| dx = -pixels_per_line_step; |
| break; |
| case SpatialNavigationDirection::kRight: |
| // TODO(bokan, https://crbug.com/952326): Fix this DCHECK. |
| // DCHECK_GT(container->GetLayoutBox()->ScrollWidth(), |
| // container->GetLayoutBoxForScrolling() |
| // ->GetScrollableArea() |
| // ->ScrollPosition() |
| // .X() + |
| // container->GetLayoutBox()->ClientWidth()); |
| dx = pixels_per_line_step; |
| break; |
| case SpatialNavigationDirection::kUp: |
| dy = -pixels_per_line_step; |
| break; |
| case SpatialNavigationDirection::kDown: |
| // TODO(bokan, https://crbug.com/952326): Fix this DCHECK. |
| // DCHECK_GT(container->GetLayoutBox()->ScrollHeight(), |
| // container->GetLayoutBoxForScrolling() |
| // ->GetScrollableArea() |
| // ->ScrollPosition() |
| // .Y() + |
| // container->GetLayoutBox()->ClientHeight()); |
| dy = pixels_per_line_step; |
| break; |
| default: |
| NOTREACHED(); |
| return false; |
| } |
| |
| // TODO(crbug.com/914775): Use UserScroll() instead. UserScroll() does a |
| // smooth, animated scroll which might make it easier for users to understand |
| // spatnav's moves. Another advantage of using ScrollableArea::UserScroll() is |
| // that it returns a ScrollResult so we don't need to call |
| // CanScrollInDirection(). Regular arrow-key scrolling (without |
| // --enable-spatial-navigation) already uses smooth scrolling by default. |
| ScrollableArea* scroller = ScrollableAreaFor(container); |
| if (!scroller) |
| return false; |
| |
| scroller->ScrollBy(ScrollOffset(dx, dy), mojom::blink::ScrollType::kUser); |
| return true; |
| } |
| |
| bool IsScrollableNode(const Node* node) { |
| if (!node) |
| return false; |
| |
| if (node->IsDocumentNode()) |
| return true; |
| |
| if (auto* box = DynamicTo<LayoutBox>(node->GetLayoutObject())) |
| return box->CanBeScrolledAndHasScrollableArea(); |
| return false; |
| } |
| |
| Node* ScrollableAreaOrDocumentOf(Node* node) { |
| DCHECK(node); |
| Node* parent = node; |
| do { |
| // FIXME: Spatial navigation is broken for OOPI. |
| if (auto* document = DynamicTo<Document>(parent)) |
| parent = document->GetFrame()->DeprecatedLocalOwner(); |
| else |
| parent = parent->ParentOrShadowHostNode(); |
| } while (parent && !IsScrollableAreaOrDocument(parent)); |
| |
| return parent; |
| } |
| |
| bool IsScrollableAreaOrDocument(const Node* node) { |
| if (!node) |
| return false; |
| |
| auto* frame_owner_element = DynamicTo<HTMLFrameOwnerElement>(node); |
| return (frame_owner_element && frame_owner_element->ContentFrame()) || |
| IsScrollableNode(node); |
| } |
| |
| bool CanScrollInDirection(const Node* container, |
| SpatialNavigationDirection direction) { |
| DCHECK(container); |
| if (auto* document = DynamicTo<Document>(container)) |
| return CanScrollInDirection(document->GetFrame(), direction); |
| |
| if (!IsScrollableNode(container)) |
| return false; |
| |
| const Element* container_element = DynamicTo<Element>(container); |
| if (!container_element) |
| return false; |
| LayoutBox* box = container_element->GetLayoutBoxForScrolling(); |
| if (!box) |
| return false; |
| auto* scrollable_area = box->GetScrollableArea(); |
| if (!scrollable_area) |
| return false; |
| |
| DCHECK(container->GetLayoutObject()); |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| return (container->GetLayoutObject()->Style()->OverflowX() != |
| EOverflow::kHidden && |
| scrollable_area->ScrollPosition().X() > 0); |
| case SpatialNavigationDirection::kUp: |
| return (container->GetLayoutObject()->Style()->OverflowY() != |
| EOverflow::kHidden && |
| scrollable_area->ScrollPosition().Y() > 0); |
| case SpatialNavigationDirection::kRight: |
| return (container->GetLayoutObject()->Style()->OverflowX() != |
| EOverflow::kHidden && |
| LayoutUnit(scrollable_area->ScrollPosition().X()) + |
| container->GetLayoutBox()->ClientWidth() < |
| container->GetLayoutBox()->ScrollWidth()); |
| case SpatialNavigationDirection::kDown: |
| return (container->GetLayoutObject()->Style()->OverflowY() != |
| EOverflow::kHidden && |
| LayoutUnit(scrollable_area->ScrollPosition().Y()) + |
| container->GetLayoutBox()->ClientHeight() < |
| container->GetLayoutBox()->ScrollHeight()); |
| default: |
| NOTREACHED(); |
| return false; |
| } |
| } |
| |
| bool CanScrollInDirection(const LocalFrame* frame, |
| SpatialNavigationDirection direction) { |
| if (!frame->View()) |
| return false; |
| LayoutView* layoutView = frame->ContentLayoutObject(); |
| if (!layoutView) |
| return false; |
| mojom::blink::ScrollbarMode vertical_mode; |
| mojom::blink::ScrollbarMode horizontal_mode; |
| layoutView->CalculateScrollbarModes(horizontal_mode, vertical_mode); |
| if ((direction == SpatialNavigationDirection::kLeft || |
| direction == SpatialNavigationDirection::kRight) && |
| mojom::blink::ScrollbarMode::kAlwaysOff == horizontal_mode) |
| return false; |
| if ((direction == SpatialNavigationDirection::kUp || |
| direction == SpatialNavigationDirection::kDown) && |
| mojom::blink::ScrollbarMode::kAlwaysOff == vertical_mode) |
| return false; |
| ScrollableArea* scrollable_area = frame->View()->GetScrollableArea(); |
| LayoutSize size(scrollable_area->ContentsSize()); |
| LayoutSize offset(scrollable_area->ScrollOffsetInt()); |
| PhysicalRect rect(scrollable_area->VisibleContentRect(kIncludeScrollbars)); |
| |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| return offset.Width() > 0; |
| case SpatialNavigationDirection::kUp: |
| return offset.Height() > 0; |
| case SpatialNavigationDirection::kRight: |
| return rect.Width() + offset.Width() < size.Width(); |
| case SpatialNavigationDirection::kDown: |
| return rect.Height() + offset.Height() < size.Height(); |
| default: |
| NOTREACHED(); |
| return false; |
| } |
| } |
| |
| PhysicalRect NodeRectInRootFrame(const Node* node) { |
| DCHECK(node); |
| DCHECK(node->GetLayoutObject()); |
| DCHECK(!node->GetDocument().View()->NeedsLayout()); |
| |
| LayoutObject* object = node->GetLayoutObject(); |
| |
| PhysicalRect rect = PhysicalRect::EnclosingRect( |
| object->LocalBoundingBoxRectForAccessibility()); |
| |
| // Inset the bounding box by the border. |
| // TODO(bokan): As far as I can tell, this is to work around empty iframes |
| // that have a border. It's unclear if that's still useful. |
| rect.ContractEdges(LayoutUnit(object->StyleRef().BorderTopWidth()), |
| LayoutUnit(object->StyleRef().BorderRightWidth()), |
| LayoutUnit(object->StyleRef().BorderBottomWidth()), |
| LayoutUnit(object->StyleRef().BorderLeftWidth())); |
| |
| object->MapToVisualRectInAncestorSpace(/*ancestor=*/nullptr, rect); |
| return rect; |
| } |
| |
| // 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) { |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| exit_point.SetX(starting_rect.X()); |
| if (potential_rect.Right() < starting_rect.X()) |
| entry_point.SetX(potential_rect.Right()); |
| else |
| entry_point.SetX(starting_rect.X()); |
| break; |
| case SpatialNavigationDirection::kUp: |
| exit_point.SetY(starting_rect.Y()); |
| if (potential_rect.Bottom() < starting_rect.Y()) |
| entry_point.SetY(potential_rect.Bottom()); |
| else |
| entry_point.SetY(starting_rect.Y()); |
| break; |
| case SpatialNavigationDirection::kRight: |
| exit_point.SetX(starting_rect.Right()); |
| if (potential_rect.X() > starting_rect.Right()) |
| entry_point.SetX(potential_rect.X()); |
| else |
| entry_point.SetX(starting_rect.Right()); |
| break; |
| case SpatialNavigationDirection::kDown: |
| exit_point.SetY(starting_rect.Bottom()); |
| if (potential_rect.Y() > starting_rect.Bottom()) |
| entry_point.SetY(potential_rect.Y()); |
| else |
| entry_point.SetY(starting_rect.Bottom()); |
| break; |
| default: |
| NOTREACHED(); |
| } |
| |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| case SpatialNavigationDirection::kRight: |
| if (Below(starting_rect, potential_rect)) { |
| exit_point.SetY(starting_rect.Y()); |
| if (potential_rect.Bottom() < starting_rect.Y()) |
| entry_point.SetY(potential_rect.Bottom()); |
| else |
| entry_point.SetY(starting_rect.Y()); |
| } else if (Below(potential_rect, starting_rect)) { |
| exit_point.SetY(starting_rect.Bottom()); |
| if (potential_rect.Y() > starting_rect.Bottom()) |
| entry_point.SetY(potential_rect.Y()); |
| else |
| entry_point.SetY(starting_rect.Bottom()); |
| } else { |
| exit_point.SetY(max(starting_rect.Y(), potential_rect.Y())); |
| entry_point.SetY(exit_point.Y()); |
| } |
| break; |
| case SpatialNavigationDirection::kUp: |
| case SpatialNavigationDirection::kDown: |
| if (RightOf(starting_rect, potential_rect)) { |
| exit_point.SetX(starting_rect.X()); |
| if (potential_rect.Right() < starting_rect.X()) |
| entry_point.SetX(potential_rect.Right()); |
| else |
| entry_point.SetX(starting_rect.X()); |
| } else if (RightOf(potential_rect, starting_rect)) { |
| exit_point.SetX(starting_rect.Right()); |
| if (potential_rect.X() > starting_rect.Right()) |
| entry_point.SetX(potential_rect.X()); |
| else |
| entry_point.SetX(starting_rect.Right()); |
| } else { |
| exit_point.SetX(max(starting_rect.X(), potential_rect.X())); |
| entry_point.SetX(exit_point.X()); |
| } |
| break; |
| default: |
| NOTREACHED(); |
| } |
| } |
| |
| double ProjectedOverlap(SpatialNavigationDirection direction, |
| PhysicalRect current, |
| PhysicalRect candidate) { |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| case SpatialNavigationDirection::kRight: |
| current.SetWidth(LayoutUnit(1)); |
| candidate.SetX(current.X()); |
| current.Intersect(candidate); |
| return current.Height(); |
| case SpatialNavigationDirection::kUp: |
| case SpatialNavigationDirection::kDown: |
| current.SetHeight(LayoutUnit(1)); |
| candidate.SetY(current.Y()); |
| current.Intersect(candidate); |
| return current.Width(); |
| default: |
| NOTREACHED(); |
| return kMaxDistance; |
| } |
| } |
| |
| double Alignment(SpatialNavigationDirection direction, |
| PhysicalRect current, |
| PhysicalRect candidate) { |
| // The formula and constants for "alignment" are experimental and |
| // come from https://drafts.csswg.org/css-nav-1/#heuristics. |
| const int kAlignWeight = 5; |
| |
| double projected_overlap = ProjectedOverlap(direction, current, candidate); |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| case SpatialNavigationDirection::kRight: |
| return (kAlignWeight * projected_overlap) / current.Height(); |
| case SpatialNavigationDirection::kUp: |
| case SpatialNavigationDirection::kDown: |
| return (kAlignWeight * projected_overlap) / current.Width(); |
| default: |
| NOTREACHED(); |
| return kMaxDistance; |
| } |
| } |
| |
| bool BothOnTopmostPaintLayerInStackingContext( |
| const FocusCandidate& current_interest, |
| const FocusCandidate& candidate) { |
| if (!current_interest.visible_node) |
| return false; |
| |
| const LayoutObject* origin = current_interest.visible_node->GetLayoutObject(); |
| const PaintLayer* focused_layer = origin->PaintingLayer(); |
| if (!focused_layer || focused_layer->IsRootLayer()) |
| return false; |
| |
| const LayoutObject* next = candidate.visible_node->GetLayoutObject(); |
| const PaintLayer* candidate_layer = next->PaintingLayer(); |
| if (focused_layer != candidate_layer) |
| return false; |
| |
| return !candidate_layer->HasVisibleDescendant(); |
| } |
| |
| double ComputeDistanceDataForNode(SpatialNavigationDirection direction, |
| const FocusCandidate& current_interest, |
| const FocusCandidate& candidate) { |
| double distance = 0.0; |
| PhysicalRect node_rect = candidate.rect_in_root_frame; |
| PhysicalRect current_rect = current_interest.rect_in_root_frame; |
| if (node_rect.Contains(current_rect)) { |
| // When leaving an "insider", don't focus its underlaying container box. |
| // Go directly to the outside world. This avoids focus from being trapped |
| // inside a container. |
| return kMaxDistance; |
| } |
| |
| if (current_rect.Contains(node_rect)) { |
| // We give highest priority to "insiders", candidates that are completely |
| // inside the current focus rect, by giving them a negative, < 0, distance |
| // number. |
| distance = kPriorityClassA; |
| |
| // For insiders we cannot meassure the distance from the outer box. Instead, |
| // we meassure distance _from_ the focused container's rect's "opposite |
| // edge" in the navigated direction, just like we do when we look for |
| // candidates inside a focused scroll container. |
| current_rect = OppositeEdge(direction, current_rect); |
| |
| // This candidate fully overlaps the current focus rect so we can omit the |
| // overlap term of the equation. An "insider" will always win against an |
| // "outsider". |
| } else if (!IsRectInDirection(direction, current_rect, node_rect)) { |
| return kMaxDistance; |
| } else if (BothOnTopmostPaintLayerInStackingContext(current_interest, |
| candidate)) { |
| // Prioritize "popup candidates" over other candidates by giving them a |
| // negative, < 0, distance number. |
| distance = kPriorityClassB; |
| } |
| |
| LayoutPoint exit_point; |
| LayoutPoint entry_point; |
| EntryAndExitPointsForDirection(direction, current_rect, node_rect, exit_point, |
| entry_point); |
| |
| LayoutUnit x_axis = (exit_point.X() - entry_point.X()).Abs(); |
| LayoutUnit y_axis = (exit_point.Y() - entry_point.Y()).Abs(); |
| double euclidian_distance = |
| sqrt((x_axis * x_axis + y_axis * y_axis).ToDouble()); |
| distance += euclidian_distance; |
| |
| LayoutUnit navigation_axis_distance; |
| LayoutUnit weighted_orthogonal_axis_distance; |
| |
| // Bias and weights are put to the orthogonal axis distance calculation |
| // so aligned candidates would have advantage over partially-aligned ones |
| // and then over not-aligned candidates. The bias is given to not-aligned |
| // candidates with respect to size of the current rect. The weight for |
| // left/right direction is given a higher value to allow navigation on |
| // common horizonally-aligned elements. The hardcoded values are based on |
| // tests and experiments. |
| const int kOrthogonalWeightForLeftRight = 30; |
| const int kOrthogonalWeightForUpDown = 2; |
| int orthogonal_bias = 0; |
| |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| case SpatialNavigationDirection::kRight: |
| navigation_axis_distance = x_axis; |
| if (!RectsIntersectOnOrthogonalAxis(direction, current_rect, node_rect)) |
| orthogonal_bias = (current_rect.Height() / 2).ToInt(); |
| weighted_orthogonal_axis_distance = |
| (y_axis + orthogonal_bias) * kOrthogonalWeightForLeftRight; |
| break; |
| case SpatialNavigationDirection::kUp: |
| case SpatialNavigationDirection::kDown: |
| navigation_axis_distance = y_axis; |
| if (!RectsIntersectOnOrthogonalAxis(direction, current_rect, node_rect)) |
| orthogonal_bias = (current_rect.Width() / 2).ToInt(); |
| weighted_orthogonal_axis_distance = |
| (x_axis + orthogonal_bias) * kOrthogonalWeightForUpDown; |
| break; |
| default: |
| NOTREACHED(); |
| return kMaxDistance; |
| } |
| |
| // We try to formalize this distance calculation at |
| // https://drafts.csswg.org/css-nav-1/. |
| distance += weighted_orthogonal_axis_distance.ToDouble() + |
| navigation_axis_distance.ToDouble(); |
| return distance - Alignment(direction, current_rect, node_rect); |
| } |
| |
| // 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 thin_rect = box; |
| switch (side) { |
| case SpatialNavigationDirection::kLeft: |
| thin_rect.SetX(thin_rect.Right() - thickness); |
| thin_rect.SetWidth(thickness); |
| thin_rect.offset.left += 1; |
| break; |
| case SpatialNavigationDirection::kRight: |
| thin_rect.SetWidth(thickness); |
| thin_rect.offset.left -= 1; |
| break; |
| case SpatialNavigationDirection::kDown: |
| thin_rect.SetHeight(thickness); |
| thin_rect.offset.top -= 1; |
| break; |
| case SpatialNavigationDirection::kUp: |
| thin_rect.SetY(thin_rect.Bottom() - thickness); |
| thin_rect.SetHeight(thickness); |
| thin_rect.offset.top += 1; |
| break; |
| default: |
| NOTREACHED(); |
| } |
| |
| return thin_rect; |
| } |
| |
| PhysicalRect StartEdgeForAreaElement(const HTMLAreaElement& area, |
| SpatialNavigationDirection direction) { |
| DCHECK(area.ImageElement()); |
| // Area elements tend to overlap more than other focusable elements. We |
| // flatten the rect of the area elements to minimize the effect of overlapping |
| // areas. |
| PhysicalRect rect = OppositeEdge( |
| direction, |
| area.GetDocument().GetFrame()->View()->ConvertToRootFrame( |
| area.ComputeAbsoluteRect(area.ImageElement()->GetLayoutObject())), |
| LayoutUnit(kFudgeFactor) /* snav-imagemap-overlapped-areas.html */); |
| return rect; |
| } |
| |
| HTMLFrameOwnerElement* FrameOwnerElement(const FocusCandidate& candidate) { |
| return DynamicTo<HTMLFrameOwnerElement>(candidate.visible_node); |
| } |
| |
| // The visual viewport's rect (given in the root frame's coordinate space). |
| PhysicalRect RootViewport(const LocalFrame* current_frame) { |
| return PhysicalRect::EnclosingRect( |
| current_frame->GetPage()->GetVisualViewport().VisibleRect()); |
| } |
| |
| // 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) { |
| while (fragment != end) { |
| PhysicalRect physical_fragment = |
| PhysicalRect::EnclosingRect(fragment->BoundingBox()); |
| physical_fragment.Intersect(visibility); |
| if (!physical_fragment.IsEmpty()) |
| return physical_fragment; |
| ++fragment; |
| } |
| return visibility; |
| } |
| |
| LayoutUnit GetLogicalHeight(const PhysicalRect& rect, |
| const LayoutObject& layout_object) { |
| if (layout_object.IsHorizontalWritingMode()) |
| return rect.Height(); |
| else |
| return rect.Width(); |
| } |
| |
| void SetLogicalHeight(PhysicalRect& rect, |
| const LayoutObject& layout_object, |
| LayoutUnit height) { |
| if (layout_object.IsHorizontalWritingMode()) |
| rect.SetHeight(height); |
| else |
| rect.SetWidth(height); |
| } |
| |
| LayoutUnit TallestInlineAtomicChild(const LayoutObject& layout_object) { |
| LayoutUnit max_child_size(0); |
| |
| if (!layout_object.IsLayoutInline()) |
| return max_child_size; |
| |
| for (LayoutObject* child = layout_object.SlowFirstChild(); child; |
| child = child->NextSibling()) { |
| if (child->IsOutOfFlowPositioned()) |
| continue; |
| |
| if (child->IsAtomicInlineLevel()) { |
| max_child_size = |
| std::max(To<LayoutBox>(child)->LogicalHeight(), max_child_size); |
| } |
| } |
| |
| return max_child_size; |
| } |
| |
| // "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) { |
| if (!layout_object.IsInline() || layout_object.IsLayoutReplaced() || |
| layout_object.IsButtonIncludingNG()) |
| return node_rect; |
| |
| // If actual line-height is bigger than the inline box, we shouldn't change |
| // anything. This is, for example, needed to not break |
| // snav-stay-in-overflow-div.html where the link's inline box doesn't fill |
| // the entire line box vertically. |
| LayoutUnit line_height = layout_object.StyleRef().ComputedLineHeightAsFixed(); |
| LayoutUnit current_height = GetLogicalHeight(node_rect, layout_object); |
| if (line_height >= current_height) |
| return node_rect; |
| |
| // Handle focusables like <a><img><a> (a LayoutInline that carries atomic |
| // inline boxes [3]). Despite a small line-height on the <a>, <a>'s line box |
| // will still fit the <img>. |
| line_height = std::max(TallestInlineAtomicChild(layout_object), line_height); |
| if (line_height >= current_height) |
| return node_rect; |
| |
| // Cap the box at its line height to avoid overlapping inline links. |
| // Links can overlap vertically when CSS line-height < font-size, see |
| // snav-line-height_less_font-size.html. |
| line_boxes = line_boxes == -1 ? LineBoxes(layout_object) : line_boxes; |
| line_height = line_height * line_boxes; |
| if (line_height >= current_height) |
| return node_rect; |
| SetLogicalHeight(node_rect, layout_object, line_height); |
| return node_rect; |
| } |
| |
| // TODO(crbug.com/1131419): Add tests and support for other writing-modes. |
| PhysicalRect SearchOriginFragment(const PhysicalRect& visible_part, |
| const LayoutObject& fragmented, |
| const SpatialNavigationDirection direction) { |
| // For accuracy, use the first visible fragment (not the fragmented element's |
| // entire bounding rect which is a union of all fragments) as search origin. |
| Vector<FloatQuad> fragments; |
| fragmented.AbsoluteQuads( |
| fragments, kTraverseDocumentBoundaries | kApplyRemoteMainFrameTransform); |
| switch (direction) { |
| case SpatialNavigationDirection::kLeft: |
| case SpatialNavigationDirection::kDown: |
| // Search from the topmost fragment. |
| return FirstVisibleFragment(visible_part, fragments.begin(), |
| fragments.end()); |
| case SpatialNavigationDirection::kRight: |
| case SpatialNavigationDirection::kUp: |
| // Search from the bottommost fragment. |
| return FirstVisibleFragment(visible_part, fragments.rbegin(), |
| fragments.rend()); |
| case SpatialNavigationDirection::kNone: |
| break; |
| // Nothing to do. |
| } |
| return visible_part; |
| } |
| |
| // 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) { |
| if (!focus_node) { |
| // Search from one of the visual viewport's edges towards the navigated |
| // direction. For example, UP makes spatnav search upwards, starting at the |
| // visual viewport's bottom. |
| return OppositeEdge(direction, viewport_rect_of_root_frame); |
| } |
| |
| auto* area_element = DynamicTo<HTMLAreaElement>(focus_node); |
| if (area_element) |
| focus_node = area_element->ImageElement(); |
| |
| if (!IsOffscreen(focus_node)) { |
| if (area_element) |
| return StartEdgeForAreaElement(*area_element, direction); |
| |
| PhysicalRect box_in_root_frame = NodeRectInRootFrame(focus_node); |
| PhysicalRect visible_part = |
| Intersection(box_in_root_frame, viewport_rect_of_root_frame); |
| |
| const LayoutObject* const layout_object = focus_node->GetLayoutObject(); |
| if (IsFragmentedInline(*layout_object)) { |
| visible_part = |
| SearchOriginFragment(visible_part, *layout_object, direction); |
| } |
| |
| // Remove any overlap with line boxes *below* the search origin. |
| // The search origin is always only one line (because if |focus_node| is |
| // line broken, SearchOriginFragment picks the first or last line's box). |
| visible_part = ShrinkInlineBoxToLineBox(*layout_object, visible_part, 1); |
| |
| return visible_part; |
| } |
| |
| Node* container = ScrollableAreaOrDocumentOf(focus_node); |
| while (container) { |
| if (!IsOffscreen(container)) { |
| // The first scroller that encloses focus and is [partially] visible. |
| PhysicalRect box_in_root_frame = NodeRectInRootFrame(container); |
| return OppositeEdge(direction, Intersection(box_in_root_frame, |
| viewport_rect_of_root_frame)); |
| } |
| container = ScrollableAreaOrDocumentOf(container); |
| } |
| return OppositeEdge(direction, viewport_rect_of_root_frame); |
| } |
| |
| } // namespace blink |
