blob: 21e7b1cbada3856a7d91040c259be80ae95df07e [file] [log] [blame]
// Copyright 2020 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
#include "third_party/blink/renderer/core/mobile_metrics/mobile_friendliness_checker.h"
#include <cmath>
#include "third_party/blink/public/common/mobile_metrics/mobile_friendliness.h"
#include "third_party/blink/public/mojom/mobile_metrics/mobile_friendliness.mojom-blink.h"
#include "third_party/blink/renderer/bindings/core/v8/v8_get_root_node_options.h"
#include "third_party/blink/renderer/core/frame/local_dom_window.h"
#include "third_party/blink/renderer/core/frame/local_frame.h"
#include "third_party/blink/renderer/core/frame/local_frame_client.h"
#include "third_party/blink/renderer/core/frame/local_frame_view.h"
#include "third_party/blink/renderer/core/frame/page_scale_constraints_set.h"
#include "third_party/blink/renderer/core/frame/root_frame_viewport.h"
#include "third_party/blink/renderer/core/frame/visual_viewport.h"
#include "third_party/blink/renderer/core/html/forms/html_form_control_element.h"
#include "third_party/blink/renderer/core/html/html_anchor_element.h"
#include "third_party/blink/renderer/core/html/html_image_element.h"
#include "third_party/blink/renderer/core/layout/adjust_for_absolute_zoom.h"
#include "third_party/blink/renderer/core/layout/layout_image.h"
#include "third_party/blink/renderer/core/layout/layout_object.h"
#include "third_party/blink/renderer/core/layout/layout_view.h"
#include "third_party/blink/renderer/core/page/chrome_client.h"
#include "third_party/blink/renderer/core/page/page.h"
#include "third_party/blink/renderer/core/page/viewport_description.h"
#include "third_party/blink/renderer/platform/heap/visitor.h"
#include "third_party/blink/renderer/platform/wtf/math_extras.h"
#include "ui/display/screen_info.h"
namespace blink {
static constexpr int kSmallFontThresholdInDips = 9;
static constexpr int kTimeBudgetExceeded = -2;
// Values of maximum-scale smaller than this threshold will be considered to
// prevent the user from scaling the page as if user-scalable=no was set.
static constexpr double kMaximumScalePreventsZoomingThreshold = 1.2;
// Finding bad tap targets may costs too long time for big page and should abort
// if it takes more than 5ms.
static constexpr base::TimeDelta kTimeBudgetForBadTapTarget =
base::Milliseconds(5);
// Extracting tap targets phase is the major part of finding bad tap targets.
// This phase will abort when it consumes more than 4ms.
static constexpr base::TimeDelta kTimeBudgetForTapTargetExtraction =
base::Milliseconds(4);
static constexpr base::TimeDelta kEvaluationDelay = base::Seconds(5);
static constexpr base::TimeDelta kEvaluationInterval = base::Minutes(1);
MobileFriendlinessChecker::MobileFriendlinessChecker(LocalFrameView& frame_view)
: frame_view_(&frame_view),
timer_(frame_view_->GetFrame().GetTaskRunner(TaskType::kInternalDefault),
this,
&MobileFriendlinessChecker::Activate) {}
MobileFriendlinessChecker::~MobileFriendlinessChecker() = default;
void MobileFriendlinessChecker::NotifyPaint() {
DCHECK(frame_view_->GetFrame().Client()->IsLocalFrameClientImpl());
DCHECK(frame_view_->GetFrame().IsLocalRoot());
if (timer_.IsActive() ||
base::TimeTicks::Now() - last_evaluated_ < kEvaluationInterval) {
return;
}
timer_.StartOneShot(kEvaluationDelay, FROM_HERE);
}
void MobileFriendlinessChecker::WillBeRemovedFromFrame() {
timer_.Stop();
}
namespace {
bool IsTimeBudgetExpired(const base::TimeTicks& from) {
return base::TimeTicks::Now() - from > kTimeBudgetForBadTapTarget;
}
// Fenwick tree is a data structure which can efficiently update elements and
// calculate prefix sums in an array of numbers. We use it here to track tap
// targets which are too close.
class FenwickTree {
public:
explicit FenwickTree(wtf_size_t n) : tree(n + 1) {}
// Returns prefix sum of the array from 0 to |index|.
int sum(wtf_size_t index) const {
int sum = 0;
for (index += 1; 0 < index; index -= index & -index)
sum += tree[index];
return sum;
}
// Adds |val| at |index| of the array.
void add(wtf_size_t index, int val) {
for (index += 1; index <= tree.size() - 1; index += index & -index)
tree[index] += val;
}
private:
Vector<int> tree;
};
// Stands for a vertex in the view, this is four corner or center of tap targets
// rectangles.
// Start edge means top edge of rectangle, End edge means bottom edge of
// rectangle, Center means arithmetic mean of four corners.
// In bad tap targets context, "Bad target" means a targets hard to tap
// precisely because there are other targets which are too close to the target.
struct EdgeOrCenter {
enum Type : int { kStartEdge = 0, kCenter = 1, kEndEdge = 2 } type;
union PositionOrIndexUnion {
int position;
wtf_size_t index;
};
union EdgeOrCenterUnion {
// Valid iff |type| is Edge.
struct Edge {
PositionOrIndexUnion left;
PositionOrIndexUnion right;
} edge;
// Valid iff |type| is Center.
PositionOrIndexUnion center;
} v;
static EdgeOrCenter StartEdge(int left, int right) {
EdgeOrCenter edge;
edge.type = EdgeOrCenter::kStartEdge;
edge.v.edge.left.position = left;
edge.v.edge.right.position = right;
return edge;
}
static EdgeOrCenter EndEdge(int left, int right) {
EdgeOrCenter edge;
edge.type = EdgeOrCenter::kEndEdge;
edge.v.edge.left.position = left;
edge.v.edge.right.position = right;
return edge;
}
static EdgeOrCenter Center(int center) {
EdgeOrCenter edge;
edge.type = EdgeOrCenter::kCenter;
edge.v.center.position = center;
return edge;
}
};
bool IsTapTargetCandidate(Node* node) {
if (const auto* anchor = DynamicTo<HTMLAnchorElement>(node)) {
return !anchor->Href().IsEmpty();
} else if (auto* element = DynamicTo<HTMLElement>(node);
element && element->WillRespondToMouseClickEvents()) {
return true;
}
return IsA<HTMLFormControlElement>(node);
}
// Skip the whole subtree if the object is invisible. Some elements in subtree
// may have visibility: visible property which should not be ignored for
// correctness, but it is rare and we prioritize performance.
bool ShouldSkipSubtree(const LayoutObject* object) {
const auto& style = object->StyleRef();
if (const LayoutBox* box = DynamicTo<LayoutBox>(object)) {
const auto& rect = box->LocalVisualRect();
if ((rect.Width() == LayoutUnit() &&
style.OverflowX() != EOverflow::kVisible) ||
(rect.Height() == LayoutUnit() &&
style.OverflowY() != EOverflow::kVisible)) {
return true;
}
}
return object->IsElementContinuation() ||
style.Visibility() != EVisibility::kVisible ||
!style.IsContentVisibilityVisible();
}
void UnionAllChildren(const LayoutObject* parent, gfx::RectF& rect) {
const LayoutObject* obj = parent;
while (obj) {
blink::GetRootNodeOptions options;
if (obj->GetNode() &&
obj->GetNode()->getRootNode(&options)->IsInUserAgentShadowRoot()) {
obj = obj->NextInPreOrderAfterChildren(parent);
} else if (ShouldSkipSubtree(obj)) {
obj = obj->NextInPreOrderAfterChildren(parent);
} else {
if (auto* element = DynamicTo<HTMLElement>(obj->GetNode())) {
rect.Union(element->GetBoundingClientRectNoLifecycleUpdate());
}
obj = obj->NextInPreOrder(parent);
}
}
}
// Appends |object| to evaluation targets if the object is a tap target.
// Returns false only if |object| is already inserted.
bool AddElement(const LayoutObject* object,
WTF::HashSet<Member<const LayoutObject>>* tap_targets,
int finger_radius,
Vector<int>& x_positions,
Vector<std::pair<int, EdgeOrCenter>>& vertices) {
Node* node = object->GetNode();
if (!node || !IsTapTargetCandidate(node))
return true;
if (auto* element = DynamicTo<HTMLElement>(object->GetNode())) {
// Ignore body tag even if it is a tappable element because majority of such
// case does not mean "bad" tap target.
if (element->IsHTMLBodyElement())
return true;
if (!tap_targets->insert(object).is_new_entry)
return false;
gfx::RectF rect = element->GetBoundingClientRectNoLifecycleUpdate();
if (auto* anchor = DynamicTo<HTMLAnchorElement>(element))
UnionAllChildren(object, rect);
if (!rect.IsEmpty() && !isnan(rect.x()) && !isnan(rect.y()) &&
!isnan(rect.right()) && !isnan(rect.bottom())) {
// Expand each corner by the size of fingertips.
const int top = ClampTo<int>(rect.y() - finger_radius);
const int bottom = ClampTo<int>(rect.bottom() + finger_radius);
const int left = ClampTo<int>(rect.x() - finger_radius);
const int right = ClampTo<int>(rect.right() + finger_radius);
const int center = right / 2 + left / 2;
vertices.emplace_back(top, EdgeOrCenter::StartEdge(left, right));
vertices.emplace_back(bottom / 2 + top / 2, EdgeOrCenter::Center(center));
vertices.emplace_back(bottom, EdgeOrCenter::EndEdge(left, right));
x_positions.push_back(left);
x_positions.push_back(right);
x_positions.push_back(center);
}
}
return true;
}
// Scans full DOM tree and register all tap regions.
// frame_view: DOM tree's root.
// finger_radius: Extends every tap regions with given pixels.
// x_positions: Collects and inserts every x dimension positions.
// vertices: Inserts y dimension keyed vertex positions with its attribute.
// Returns total count of tap targets.
int ExtractAndCountAllTapTargets(
const LocalFrameView& frame_view,
int finger_radius,
Vector<int>& x_positions,
const base::TimeTicks& started,
Vector<std::pair<int, EdgeOrCenter>>& vertices) {
LayoutObject* const root =
frame_view.GetFrame().GetDocument()->GetLayoutView();
WTF::HashSet<Member<const LayoutObject>> tap_targets;
// Simultaneously iterate front-to-back and back-to-front to consider
// both page headers and footers using the same time budget.
for (const LayoutObject *forward = root, *backward = root;
forward && backward;) {
if (base::TimeTicks::Now() - started > kTimeBudgetForTapTargetExtraction)
return static_cast<int>(tap_targets.size());
blink::GetRootNodeOptions options;
if (forward->GetNode() != nullptr &&
forward->GetNode()->getRootNode(&options)->IsInUserAgentShadowRoot()) {
// Ignore shadow elements that may contain overlapping tap targets.
forward = forward->NextInPreOrderAfterChildren();
} else if (ShouldSkipSubtree(forward)) {
forward = forward->NextInPreOrderAfterChildren();
} else {
if (!AddElement(forward, &tap_targets, finger_radius, x_positions,
vertices)) {
break;
}
forward = forward->NextInPreOrder();
}
if (backward->GetNode() != nullptr &&
backward->GetNode()->getRootNode(&options)->IsInUserAgentShadowRoot()) {
// Ignore shadow elements that may contain overlapping tap targets.
backward = backward->PreviousInPostOrderBeforeChildren(nullptr);
} else if (ShouldSkipSubtree(backward)) {
backward = backward->PreviousInPostOrderBeforeChildren(nullptr);
} else {
if (!AddElement(backward, &tap_targets, finger_radius, x_positions,
vertices)) {
break;
}
backward = backward->PreviousInPostOrder(nullptr);
}
}
return static_cast<int>(tap_targets.size());
}
// Compress the x-dimension range and overwrites the value.
// Precondition: |positions| must be sorted and unique.
void CompressKeyWithVector(const Vector<int>& positions,
Vector<std::pair<int, EdgeOrCenter>>& vertices) {
// Overwrite the vertex key with the position of the map.
for (auto& it : vertices) {
EdgeOrCenter& vertex = it.second;
switch (vertex.type) {
case EdgeOrCenter::kStartEdge:
case EdgeOrCenter::kEndEdge: {
vertex.v.edge.left.index = static_cast<wtf_size_t>(
std::distance(positions.begin(),
std::lower_bound(positions.begin(), positions.end(),
vertex.v.edge.left.position)));
vertex.v.edge.right.index = static_cast<wtf_size_t>(
std::distance(positions.begin(),
std::lower_bound(positions.begin(), positions.end(),
vertex.v.edge.right.position)));
break;
}
case EdgeOrCenter::kCenter: {
vertex.v.center.index = static_cast<wtf_size_t>(
std::distance(positions.begin(),
std::lower_bound(positions.begin(), positions.end(),
vertex.v.center.position)));
break;
}
}
}
}
// Scans the vertices from top to bottom with updating FenwickTree to track
// tap target regions.
// Precondition: |vertex| must be sorted by its |first|.
// rightmost_position: Rightmost x position in all vertices.
// Returns bad tap targets count.
// Returns kTimeBudgetExceeded if time limit exceeded.
int CountBadTapTargets(wtf_size_t rightmost_position,
const Vector<std::pair<int, EdgeOrCenter>>& vertices,
const base::TimeTicks& started) {
FenwickTree tree(rightmost_position);
int bad_tap_targets = 0;
for (const auto& it : vertices) {
const EdgeOrCenter& vertex = it.second;
switch (vertex.type) {
case EdgeOrCenter::kStartEdge: {
// Tap region begins.
tree.add(vertex.v.edge.left.index, 1);
tree.add(vertex.v.edge.right.index, -1);
break;
}
case EdgeOrCenter::kEndEdge: {
// Tap region ends.
tree.add(vertex.v.edge.left.index, -1);
tree.add(vertex.v.edge.right.index, 1);
break;
}
case EdgeOrCenter::kCenter: {
// Iff the center of a tap target is included other than itself, it is a
// Bad Target.
if (tree.sum(vertex.v.center.index) > 1)
bad_tap_targets++;
break;
}
}
if (IsTimeBudgetExpired(started))
return kTimeBudgetExceeded;
}
return bad_tap_targets;
}
} // namespace
// Counts and calculate ration of bad tap targets. The process is a surface scan
// with region tracking by Fenwick tree. The detail of the algorithm is
// go/bad-tap-target-ukm
int MobileFriendlinessChecker::ComputeBadTapTargetsRatio() {
DCHECK(frame_view_->GetFrame().IsLocalRoot());
base::TimeTicks started = base::TimeTicks::Now();
constexpr float kOneDipInMm = 0.15875;
double initial_scale = frame_view_->GetPage()
->GetPageScaleConstraintsSet()
.FinalConstraints()
.initial_scale;
DCHECK_GT(initial_scale, 0);
const int finger_radius =
std::floor((3 / kOneDipInMm) / initial_scale); // 3mm in logical pixel.
Vector<std::pair<int, EdgeOrCenter>> vertices;
vertices.ReserveInitialCapacity(1024);
Vector<int> x_positions;
x_positions.ReserveInitialCapacity(1024);
// Recursively evaluate MF values into subframes.
int all_tap_targets = 0;
for (const Frame* frame = &frame_view_->GetFrame(); frame;
frame = frame->Tree().TraverseNext()) {
const auto* local_frame = DynamicTo<LocalFrame>(frame);
if (!local_frame)
continue;
const LocalFrameView* view = local_frame->View();
// Scan full DOM tree and extract every corner and center position of tap
// targets.
const int got_tap_targets = ExtractAndCountAllTapTargets(
*view, finger_radius, x_positions, started, vertices);
all_tap_targets += got_tap_targets;
if (base::TimeTicks::Now() - started > kTimeBudgetForTapTargetExtraction)
break;
}
if (all_tap_targets == 0)
return 0; // Means there is no tap target.
// Compress x dimension of all vertices to save memory.
// This will reduce rightmost position of vertices without sacrificing
// accuracy so that required memory by Fenwick Tree will be reduced.
std::sort(x_positions.begin(), x_positions.end());
x_positions.erase(std::unique(x_positions.begin(), x_positions.end()),
x_positions.end());
CompressKeyWithVector(x_positions, vertices);
if (IsTimeBudgetExpired(started))
return kTimeBudgetExceeded;
// Reorder vertices by y dimension for sweeping full page from top to bottom.
std::sort(vertices.begin(), vertices.end(),
[](const std::pair<int, EdgeOrCenter>& a,
const std::pair<int, EdgeOrCenter>& b) {
// Ordering with kStart < kCenter < kEnd.
return std::tie(a.first, a.second.type) <
std::tie(b.first, b.second.type);
});
if (IsTimeBudgetExpired(started))
return kTimeBudgetExceeded;
// Sweep x-compressed y-ordered vertices to detect bad tap targets.
const int bad_tap_targets =
CountBadTapTargets(x_positions.size(), vertices, started);
if (bad_tap_targets == kTimeBudgetExceeded)
return kTimeBudgetExceeded;
return std::ceil(bad_tap_targets * 100.0 / all_tap_targets);
}
void MobileFriendlinessChecker::Activate(TimerBase*) {
DCHECK(frame_view_->GetFrame().Client()->IsLocalFrameClientImpl());
// If detached, there's no need to calculate any metrics.
if (!frame_view_->GetChromeClient())
return;
frame_view_->RegisterForLifecycleNotifications(this);
frame_view_->ScheduleAnimation();
}
void MobileFriendlinessChecker::DidFinishLifecycleUpdate(
const LocalFrameView&) {
DCHECK(frame_view_->GetFrame().Client()->IsLocalFrameClientImpl());
DCHECK(frame_view_->GetFrame().IsLocalRoot());
frame_view_->UnregisterFromLifecycleNotifications(this);
frame_view_->DidChangeMobileFriendliness(MobileFriendliness{
.viewport_device_width = viewport_device_width_,
.viewport_initial_scale_x10 = viewport_initial_scale_x10_,
.viewport_hardcoded_width = viewport_hardcoded_width_,
.allow_user_zoom = allow_user_zoom_,
.small_text_ratio = text_area_sizes_.SmallTextRatio(),
.text_content_outside_viewport_percentage =
ComputeContentOutsideViewport(),
.bad_tap_targets_ratio = ComputeBadTapTargetsRatio()});
last_evaluated_ = base::TimeTicks::Now();
}
void MobileFriendlinessChecker::NotifyViewportUpdated(
const ViewportDescription& viewport) {
DCHECK(frame_view_->GetFrame().Client()->IsLocalFrameClientImpl());
DCHECK(frame_view_->GetFrame().IsLocalRoot());
if (viewport.type != ViewportDescription::Type::kViewportMeta)
return;
const double zoom = viewport.zoom_is_explicit ? viewport.zoom : 1.0;
viewport_device_width_ = viewport.max_width.IsDeviceWidth();
if (viewport.max_width.IsFixed()) {
viewport_hardcoded_width_ = viewport.max_width.GetFloatValue();
// Convert value from Blink space to device-independent pixels.
const double viewport_scalar =
frame_view_->GetPage()->GetChromeClient().WindowToViewportScalar(
&frame_view_->GetFrame(), 1);
if (viewport_scalar != 0)
viewport_hardcoded_width_ /= viewport_scalar;
}
if (viewport.zoom_is_explicit)
viewport_initial_scale_x10_ = std::round(viewport.zoom * 10);
if (viewport.user_zoom_is_explicit) {
allow_user_zoom_ = viewport.user_zoom;
// If zooming is only allowed slightly.
if (viewport.max_zoom / zoom < kMaximumScalePreventsZoomingThreshold)
allow_user_zoom_ = false;
}
}
int MobileFriendlinessChecker::TextAreaWithFontSize::SmallTextRatio() const {
if (total_text_area == 0)
return 0;
return small_font_area * 100 / total_text_area;
}
void MobileFriendlinessChecker::NotifyInvalidatePaint(
const LayoutObject& object) {
DCHECK(frame_view_->GetFrame().Client()->IsLocalFrameClientImpl());
DCHECK(frame_view_->GetFrame().IsLocalRoot());
// Compute small text ratio.
if (const auto* text = DynamicTo<LayoutText>(object)) {
const auto& style = text->StyleRef();
// Ignore elements that users cannot see.
if (style.Visibility() != EVisibility::kVisible)
return;
// Ignore elements intended only for screen readers.
if (style.HasOutOfFlowPosition() && style.ClipLeft().IsZero() &&
style.ClipRight().IsZero() && style.ClipTop().IsZero() &&
style.ClipBottom().IsZero())
return;
const double viewport_scalar =
frame_view_->GetPage()->GetChromeClient().WindowToViewportScalar(
&frame_view_->GetFrame(), 1);
double initial_scale = frame_view_->GetPage()
->GetPageScaleConstraintsSet()
.FinalConstraints()
.initial_scale;
DCHECK_GT(initial_scale, 0);
double actual_font_size =
style.FontSize() * initial_scale / viewport_scalar;
double area = text->PhysicalAreaSize();
if (std::round(actual_font_size) < kSmallFontThresholdInDips)
text_area_sizes_.small_font_area += area;
text_area_sizes_.total_text_area += area;
}
}
int MobileFriendlinessChecker::ComputeContentOutsideViewport() {
int frame_width = frame_view_->GetPage()->GetVisualViewport().Size().width();
if (frame_width == 0) {
return 0;
}
const auto* root_frame_viewport = frame_view_->GetRootFrameViewport();
if (root_frame_viewport == nullptr) {
return 0;
}
double initial_scale = frame_view_->GetPage()
->GetPageScaleConstraintsSet()
.FinalConstraints()
.initial_scale;
int content_width =
root_frame_viewport->LayoutViewport().ContentsSize().width() *
initial_scale;
int max_scroll_offset = content_width - frame_width;
// We use ceil function here because we want to treat 100.1% as 101 which
// requires a scroll bar.
return std::ceil(max_scroll_offset * 100.0 / frame_width);
}
void MobileFriendlinessChecker::Trace(Visitor* visitor) const {
visitor->Trace(frame_view_);
visitor->Trace(timer_);
}
} // namespace blink