third_party/WebKit/Source/core/page/TouchAdjustment.cpp

   1 /*
   2  * Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies)
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public License
  15  * along with this library; see the file COPYING.LIB.  If not, write to
  16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  */
  19
  20 #include "config.h"
  21
  22 #include "core/page/TouchAdjustment.h"
  23
  24 #include "core/dom/ContainerNode.h"
  25 #include "core/dom/Node.h"
  26 #include "core/dom/NodeComputedStyle.h"
  27 #include "core/dom/Text.h"
  28 #include "core/editing/Editor.h"
  29 #include "core/frame/FrameView.h"
  30 #include "core/frame/LocalFrame.h"
  31 #include "core/html/HTMLFrameOwnerElement.h"
  32 #include "core/layout/LayoutBox.h"
  33 #include "core/layout/LayoutObject.h"
  34 #include "core/layout/LayoutText.h"
  35 #include "core/layout/api/SelectionState.h"
  36 #include "core/style/ComputedStyle.h"
  37 #include "platform/geometry/FloatPoint.h"
  38 #include "platform/geometry/FloatQuad.h"
  39 #include "platform/geometry/IntSize.h"
  40 #include "platform/text/TextBreakIterator.h"
  41
  42 namespace blink {
  43
  44 namespace TouchAdjustment {
  45
  46 const float zeroTolerance = 1e-6f;
  47
  48 // Class for remembering absolute quads of a target node and what node they represent.
  49 class SubtargetGeometry {
  50     ALLOW_ONLY_INLINE_ALLOCATION();
  51 public:
  52     SubtargetGeometry(Node* node, const FloatQuad& quad)
  53         : m_node(node)
  54         , m_quad(quad)
  55     { }
  56     DEFINE_INLINE_TRACE() { visitor->trace(m_node); }
  57
  58     Node* node() const { return m_node; }
  59     FloatQuad quad() const { return m_quad; }
  60     IntRect boundingBox() const { return m_quad.enclosingBoundingBox(); }
  61
  62 private:
  63     RawPtrWillBeMember<Node> m_node;
  64     FloatQuad m_quad;
  65 };
  66
  67 }
  68
  69 }
  70
  71 WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS(blink::TouchAdjustment::SubtargetGeometry)
  72
  73 namespace blink {
  74
  75 namespace TouchAdjustment {
  76
  77 typedef WillBeHeapVector<SubtargetGeometry> SubtargetGeometryList;
  78 typedef bool (*NodeFilter)(Node*);
  79 typedef void (*AppendSubtargetsForNode)(Node*, SubtargetGeometryList&);
  80 typedef float (*DistanceFunction)(const IntPoint&, const IntRect&, const SubtargetGeometry&);
  81
  82 // Takes non-const Node* because isContentEditable is a non-const function.
  83 bool nodeRespondsToTapGesture(Node* node)
  84 {
  85     if (node->willRespondToMouseClickEvents() || node->willRespondToMouseMoveEvents())
  86         return true;
  87     if (node->isElementNode()) {
  88         Element* element = toElement(node);
  89         // Tapping on a text field or other focusable item should trigger adjustment, except
  90         // that iframe elements are hard-coded to support focus but the effect is often invisible
  91         // so they should be excluded.
  92         if (element->isMouseFocusable() && !isHTMLIFrameElement(element))
  93             return true;
  94         // Accept nodes that has a CSS effect when touched.
  95         if (element->childrenOrSiblingsAffectedByActive() || element->childrenOrSiblingsAffectedByHover())
  96             return true;
  97     }
  98     if (const ComputedStyle* computedStyle = node->computedStyle()) {
  99         if (computedStyle->affectedByActive() || computedStyle->affectedByHover())
 100             return true;
 101     }
 102     return false;
 103 }
 104
 105 bool nodeIsZoomTarget(Node* node)
 106 {
 107     if (node->isTextNode() || node->isShadowRoot())
 108         return false;
 109
 110     ASSERT(node->layoutObject());
 111     return node->layoutObject()->isBox();
 112 }
 113
 114 bool providesContextMenuItems(Node* node)
 115 {
 116     // This function tries to match the nodes that receive special context-menu items in
 117     // ContextMenuController::populate(), and should be kept uptodate with those.
 118     ASSERT(node->layoutObject() || node->isShadowRoot());
 119     if (!node->layoutObject())
 120         return false;
 121     if (node->isContentEditable())
 122         return true;
 123     if (node->isLink())
 124         return true;
 125     if (node->layoutObject()->isImage())
 126         return true;
 127     if (node->layoutObject()->isMedia())
 128         return true;
 129     if (node->layoutObject()->canBeSelectionLeaf()) {
 130         // If the context menu gesture will trigger a selection all selectable nodes are valid targets.
 131         if (node->layoutObject()->frame()->editor().behavior().shouldSelectOnContextualMenuClick())
 132             return true;
 133         // Only the selected part of the layoutObject is a valid target, but this will be corrected in
 134         // appendContextSubtargetsForNode.
 135         if (node->layoutObject()->selectionState() != SelectionNone)
 136             return true;
 137     }
 138     return false;
 139 }
 140
 141 static inline void appendQuadsToSubtargetList(Vector<FloatQuad>& quads, Node* node, SubtargetGeometryList& subtargets)
 142 {
 143     Vector<FloatQuad>::const_iterator it = quads.begin();
 144     const Vector<FloatQuad>::const_iterator end = quads.end();
 145     for (; it != end; ++it)
 146         subtargets.append(SubtargetGeometry(node, *it));
 147 }
 148
 149 static inline void appendBasicSubtargetsForNode(Node* node, SubtargetGeometryList& subtargets)
 150 {
 151     // Node guaranteed to have layoutObject due to check in node filter.
 152     ASSERT(node->layoutObject());
 153
 154     Vector<FloatQuad> quads;
 155     node->layoutObject()->absoluteQuads(quads);
 156
 157     appendQuadsToSubtargetList(quads, node, subtargets);
 158 }
 159
 160 static inline void appendContextSubtargetsForNode(Node* node, SubtargetGeometryList& subtargets)
 161 {
 162     // This is a variant of appendBasicSubtargetsForNode that adds special subtargets for
 163     // selected or auto-selectable parts of text nodes.
 164     ASSERT(node->layoutObject());
 165
 166     if (!node->isTextNode())
 167         return appendBasicSubtargetsForNode(node, subtargets);
 168
 169     Text* textNode = toText(node);
 170     LayoutText* textLayoutObject = textNode->layoutObject();
 171
 172     if (textLayoutObject->frame()->editor().behavior().shouldSelectOnContextualMenuClick()) {
 173         // Make subtargets out of every word.
 174         String textValue = textNode->data();
 175         TextBreakIterator* wordIterator = wordBreakIterator(textValue, 0, textValue.length());
 176         int lastOffset = wordIterator->first();
 177         if (lastOffset == -1)
 178             return;
 179         int offset;
 180         while ((offset = wordIterator->next()) != -1) {
 181             if (isWordTextBreak(wordIterator)) {
 182                 Vector<FloatQuad> quads;
 183                 textLayoutObject->absoluteQuadsForRange(quads, lastOffset, offset);
 184                 appendQuadsToSubtargetList(quads, textNode, subtargets);
 185             }
 186             lastOffset = offset;
 187         }
 188     } else {
 189         if (textLayoutObject->selectionState() == SelectionNone)
 190             return appendBasicSubtargetsForNode(node, subtargets);
 191         // If selected, make subtargets out of only the selected part of the text.
 192         int startPos, endPos;
 193         switch (textLayoutObject->selectionState()) {
 194         case SelectionInside:
 195             startPos = 0;
 196             endPos = textLayoutObject->textLength();
 197             break;
 198         case SelectionStart:
 199             textLayoutObject->selectionStartEnd(startPos, endPos);
 200             endPos = textLayoutObject->textLength();
 201             break;
 202         case SelectionEnd:
 203             textLayoutObject->selectionStartEnd(startPos, endPos);
 204             startPos = 0;
 205             break;
 206         case SelectionBoth:
 207             textLayoutObject->selectionStartEnd(startPos, endPos);
 208             break;
 209         default:
 210             ASSERT_NOT_REACHED();
 211             return;
 212         }
 213         Vector<FloatQuad> quads;
 214         textLayoutObject->absoluteQuadsForRange(quads, startPos, endPos);
 215         appendQuadsToSubtargetList(quads, textNode, subtargets);
 216     }
 217 }
 218
 219 static inline void appendZoomableSubtargets(Node* node, SubtargetGeometryList& subtargets)
 220 {
 221     LayoutBox* layoutObject = toLayoutBox(node->layoutObject());
 222     ASSERT(layoutObject);
 223
 224     Vector<FloatQuad> quads;
 225     FloatRect borderBoxRect(layoutObject->borderBoxRect());
 226     FloatRect contentBoxRect(layoutObject->contentBoxRect());
 227     quads.append(layoutObject->localToAbsoluteQuad(borderBoxRect));
 228     if (borderBoxRect != contentBoxRect)
 229         quads.append(layoutObject->localToAbsoluteQuad(contentBoxRect));
 230     // FIXME: For LayoutBlocks, add column boxes and content boxes cleared for floats.
 231
 232     Vector<FloatQuad>::const_iterator it = quads.begin();
 233     const Vector<FloatQuad>::const_iterator end = quads.end();
 234     for (; it != end; ++it)
 235         subtargets.append(SubtargetGeometry(node, *it));
 236 }
 237
 238 static inline Node* parentShadowHostOrOwner(const Node* node)
 239 {
 240     if (Node* ancestor = node->parentOrShadowHostNode())
 241         return ancestor;
 242     if (node->isDocumentNode())
 243         return toDocument(node)->ownerElement();
 244     return nullptr;
 245 }
 246
 247 // Compiles a list of subtargets of all the relevant target nodes.
 248 void compileSubtargetList(const WillBeHeapVector<RefPtrWillBeMember<Node>>& intersectedNodes, SubtargetGeometryList& subtargets, NodeFilter nodeFilter, AppendSubtargetsForNode appendSubtargetsForNode)
 249 {
 250     // Find candidates responding to tap gesture events in O(n) time.
 251     WillBeHeapHashMap<RawPtrWillBeMember<Node>, RawPtrWillBeMember<Node>> responderMap;
 252     WillBeHeapHashSet<RawPtrWillBeMember<Node>> ancestorsToRespondersSet;
 253     WillBeHeapVector<RawPtrWillBeMember<Node>> candidates;
 254     WillBeHeapHashSet<RawPtrWillBeMember<Node>> editableAncestors;
 255
 256     // A node matching the NodeFilter is called a responder. Candidate nodes must either be a
 257     // responder or have an ancestor that is a responder.
 258     // This iteration tests all ancestors at most once by caching earlier results.
 259     for (unsigned i = 0; i < intersectedNodes.size(); ++i) {
 260         Node* node = intersectedNodes[i].get();
 261         WillBeHeapVector<RawPtrWillBeMember<Node>> visitedNodes;
 262         Node* respondingNode = nullptr;
 263         for (Node* visitedNode = node; visitedNode; visitedNode = visitedNode->parentOrShadowHostNode()) {
 264             // Check if we already have a result for a common ancestor from another candidate.
 265             respondingNode = responderMap.get(visitedNode);
 266             if (respondingNode)
 267                 break;
 268             visitedNodes.append(visitedNode);
 269             // Check if the node filter applies, which would mean we have found a responding node.
 270             if (nodeFilter(visitedNode)) {
 271                 respondingNode = visitedNode;
 272                 // Continue the iteration to collect the ancestors of the responder, which we will need later.
 273                 for (visitedNode = parentShadowHostOrOwner(visitedNode); visitedNode; visitedNode = parentShadowHostOrOwner(visitedNode)) {
 274                     WillBeHeapHashSet<RawPtrWillBeMember<Node>>::AddResult addResult = ancestorsToRespondersSet.add(visitedNode);
 275                     if (!addResult.isNewEntry)
 276                         break;
 277                 }
 278                 break;
 279             }
 280         }
 281         // Insert the detected responder for all the visited nodes.
 282         for (unsigned j = 0; j < visitedNodes.size(); j++)
 283             responderMap.add(visitedNodes[j], respondingNode);
 284
 285         if (respondingNode)
 286             candidates.append(node);
 287     }
 288
 289     // We compile the list of component absolute quads instead of using the bounding rect
 290     // to be able to perform better hit-testing on inline links on line-breaks.
 291     for (unsigned i = 0; i < candidates.size(); i++) {
 292         Node* candidate = candidates[i];
 293         // Skip nodes who's responders are ancestors of other responders. This gives preference to
 294         // the inner-most event-handlers. So that a link is always preferred even when contained
 295         // in an element that monitors all click-events.
 296         Node* respondingNode = responderMap.get(candidate);
 297         ASSERT(respondingNode);
 298         if (ancestorsToRespondersSet.contains(respondingNode))
 299             continue;
 300         // Consolidate bounds for editable content.
 301         if (editableAncestors.contains(candidate))
 302             continue;
 303         if (candidate->isContentEditable()) {
 304             Node* replacement = candidate;
 305             Node* parent = candidate->parentOrShadowHostNode();
 306             while (parent && parent->isContentEditable()) {
 307                 replacement = parent;
 308                 if (editableAncestors.contains(replacement)) {
 309                     replacement = nullptr;
 310                     break;
 311                 }
 312                 editableAncestors.add(replacement);
 313                 parent = parent->parentOrShadowHostNode();
 314             }
 315             candidate = replacement;
 316         }
 317         if (candidate)
 318             appendSubtargetsForNode(candidate, subtargets);
 319     }
 320 }
 321
 322 // Compiles a list of zoomable subtargets.
 323 void compileZoomableSubtargets(const WillBeHeapVector<RefPtrWillBeMember<Node>>& intersectedNodes, SubtargetGeometryList& subtargets)
 324 {
 325     for (unsigned i = 0; i < intersectedNodes.size(); ++i) {
 326         Node* candidate = intersectedNodes[i].get();
 327         if (nodeIsZoomTarget(candidate))
 328             appendZoomableSubtargets(candidate, subtargets);
 329     }
 330 }
 331
 332 // This returns quotient of the target area and its intersection with the touch area.
 333 // This will prioritize largest intersection and smallest area, while balancing the two against each other.
 334 float zoomableIntersectionQuotient(const IntPoint& touchHotspot, const IntRect& touchArea, const SubtargetGeometry& subtarget)
 335 {
 336     IntRect rect = subtarget.node()->document().view()->contentsToRootFrame(subtarget.boundingBox());
 337
 338     // Check the rectangle is meaningful zoom target. It should at least contain the hotspot.
 339     if (!rect.contains(touchHotspot))
 340         return std::numeric_limits<float>::infinity();
 341     IntRect intersection = rect;
 342     intersection.intersect(touchArea);
 343
 344     // Return the quotient of the intersection.
 345     return rect.size().area() / (float)intersection.size().area();
 346 }
 347
 348 // Uses a hybrid of distance to adjust and intersect ratio, normalizing each score between 0 and 1
 349 // and combining them. The distance to adjust works best for disambiguating clicks on targets such
 350 // as links, where the width may be significantly larger than the touch width. Using area of overlap
 351 // in such cases can lead to a bias towards shorter links. Conversely, percentage of overlap can
 352 // provide strong confidence in tapping on a small target, where the overlap is often quite high,
 353 // and works well for tightly packed controls.
 354 float hybridDistanceFunction(const IntPoint& touchHotspot, const IntRect& touchRect, const SubtargetGeometry& subtarget)
 355 {
 356     IntRect rect = subtarget.node()->document().view()->contentsToRootFrame(subtarget.boundingBox());
 357
 358     float radiusSquared = 0.25f * (touchRect.size().diagonalLengthSquared());
 359     float distanceToAdjustScore = rect.distanceSquaredToPoint(touchHotspot) / radiusSquared;
 360
 361     int maxOverlapWidth = std::min(touchRect.width(), rect.width());
 362     int maxOverlapHeight = std::min(touchRect.height(), rect.height());
 363     float maxOverlapArea = std::max(maxOverlapWidth * maxOverlapHeight, 1);
 364     rect.intersect(touchRect);
 365     float intersectArea = rect.size().area();
 366     float intersectionScore = 1 - intersectArea / maxOverlapArea;
 367
 368     float hybridScore = intersectionScore + distanceToAdjustScore;
 369
 370     return hybridScore;
 371 }
 372
 373 FloatPoint contentsToRootFrame(FrameView *view, FloatPoint pt)
 374 {
 375     int x = static_cast<int>(pt.x() + 0.5f);
 376     int y = static_cast<int>(pt.y() + 0.5f);
 377     IntPoint adjusted = view->contentsToRootFrame(IntPoint(x, y));
 378     return FloatPoint(adjusted.x(), adjusted.y());
 379 }
 380
 381 // Adjusts 'point' to the nearest point inside rect, and leaves it unchanged if already inside.
 382 void adjustPointToRect(FloatPoint& point, const FloatRect& rect)
 383 {
 384     if (point.x() < rect.x())
 385         point.setX(rect.x());
 386     else if (point.x() > rect.maxX())
 387         point.setX(rect.maxX());
 388
 389     if (point.y() < rect.y())
 390         point.setY(rect.y());
 391     else if (point.y() > rect.maxY())
 392         point.setY(rect.maxY());
 393 }
 394
 395 bool snapTo(const SubtargetGeometry& geom, const IntPoint& touchPoint, const IntRect& touchArea, IntPoint& adjustedPoint)
 396 {
 397     FrameView* view = geom.node()->document().view();
 398     FloatQuad quad = geom.quad();
 399
 400     if (quad.isRectilinear()) {
 401         IntRect bounds = view->contentsToRootFrame(geom.boundingBox());
 402         if (bounds.contains(touchPoint)) {
 403             adjustedPoint = touchPoint;
 404             return true;
 405         }
 406         if (bounds.intersects(touchArea)) {
 407             bounds.intersect(touchArea);
 408             adjustedPoint = bounds.center();
 409             return true;
 410         }
 411         return false;
 412     }
 413
 414     // The following code tries to adjust the point to place inside a both the touchArea and the non-rectilinear quad.
 415     // FIXME: This will return the point inside the touch area that is the closest to the quad center, but does not
 416     // guarantee that the point will be inside the quad. Corner-cases exist where the quad will intersect but this
 417     // will fail to adjust the point to somewhere in the intersection.
 418
 419     FloatPoint p1 = contentsToRootFrame(view, quad.p1());
 420     FloatPoint p2 = contentsToRootFrame(view, quad.p2());
 421     FloatPoint p3 = contentsToRootFrame(view, quad.p3());
 422     FloatPoint p4 = contentsToRootFrame(view, quad.p4());
 423     quad = FloatQuad(p1, p2, p3, p4);
 424
 425     if (quad.containsPoint(touchPoint)) {
 426         adjustedPoint = touchPoint;
 427         return true;
 428     }
 429
 430     // Pull point towards the center of the element.
 431     FloatPoint center = quad.center();
 432
 433     adjustPointToRect(center, touchArea);
 434     adjustedPoint = roundedIntPoint(center);
 435
 436     return quad.containsPoint(adjustedPoint);
 437 }
 438
 439 // A generic function for finding the target node with the lowest distance metric. A distance metric here is the result
 440 // of a distance-like function, that computes how well the touch hits the node.
 441 // Distance functions could for instance be distance squared or area of intersection.
 442 bool findNodeWithLowestDistanceMetric(Node*& targetNode, IntPoint& targetPoint, IntRect& targetArea, const IntPoint& touchHotspot, const IntRect& touchArea, SubtargetGeometryList& subtargets, DistanceFunction distanceFunction)
 443 {
 444     targetNode = nullptr;
 445     float bestDistanceMetric = std::numeric_limits<float>::infinity();
 446     SubtargetGeometryList::const_iterator it = subtargets.begin();
 447     const SubtargetGeometryList::const_iterator end = subtargets.end();
 448     IntPoint adjustedPoint;
 449
 450     for (; it != end; ++it) {
 451         Node* node = it->node();
 452         float distanceMetric = distanceFunction(touchHotspot, touchArea, *it);
 453         if (distanceMetric < bestDistanceMetric) {
 454             if (snapTo(*it, touchHotspot, touchArea, adjustedPoint)) {
 455                 targetPoint = adjustedPoint;
 456                 targetArea = it->boundingBox();
 457                 targetNode = node;
 458                 bestDistanceMetric = distanceMetric;
 459             }
 460         } else if (distanceMetric - bestDistanceMetric < zeroTolerance) {
 461             if (snapTo(*it, touchHotspot, touchArea, adjustedPoint)) {
 462                 if (node->isDescendantOf(targetNode)) {
 463                     // Try to always return the inner-most element.
 464                     targetPoint = adjustedPoint;
 465                     targetNode = node;
 466                     targetArea = it->boundingBox();
 467                 }
 468             }
 469         }
 470     }
 471
 472     // As for HitTestResult.innerNode, we skip over pseudo elements.
 473     if (targetNode && targetNode->isPseudoElement())
 474         targetNode = targetNode->parentOrShadowHostNode();
 475
 476     if (targetNode)
 477         targetArea = targetNode->document().view()->contentsToRootFrame(targetArea);
 478
 479     return (targetNode);
 480 }
 481
 482 } // namespace TouchAdjustment
 483
 484 bool findBestClickableCandidate(Node*& targetNode, IntPoint& targetPoint, const IntPoint& touchHotspot, const IntRect& touchArea, const WillBeHeapVector<RefPtrWillBeMember<Node>>& nodes)
 485 {
 486     IntRect targetArea;
 487     TouchAdjustment::SubtargetGeometryList subtargets;
 488     TouchAdjustment::compileSubtargetList(nodes, subtargets, TouchAdjustment::nodeRespondsToTapGesture, TouchAdjustment::appendBasicSubtargetsForNode);
 489     return TouchAdjustment::findNodeWithLowestDistanceMetric(targetNode, targetPoint, targetArea, touchHotspot, touchArea, subtargets, TouchAdjustment::hybridDistanceFunction);
 490 }
 491
 492 bool findBestContextMenuCandidate(Node*& targetNode, IntPoint& targetPoint, const IntPoint& touchHotspot, const IntRect& touchArea, const WillBeHeapVector<RefPtrWillBeMember<Node>>& nodes)
 493 {
 494     IntRect targetArea;
 495     TouchAdjustment::SubtargetGeometryList subtargets;
 496     TouchAdjustment::compileSubtargetList(nodes, subtargets, TouchAdjustment::providesContextMenuItems, TouchAdjustment::appendContextSubtargetsForNode);
 497     return TouchAdjustment::findNodeWithLowestDistanceMetric(targetNode, targetPoint, targetArea, touchHotspot, touchArea, subtargets, TouchAdjustment::hybridDistanceFunction);
 498 }
 499
 500 bool findBestZoomableArea(Node*& targetNode, IntRect& targetArea, const IntPoint& touchHotspot, const IntRect& touchArea, const WillBeHeapVector<RefPtrWillBeMember<Node>>& nodes)
 501 {
 502     IntPoint targetPoint;
 503     TouchAdjustment::SubtargetGeometryList subtargets;
 504     TouchAdjustment::compileZoomableSubtargets(nodes, subtargets);
 505     return TouchAdjustment::findNodeWithLowestDistanceMetric(targetNode, targetPoint, targetArea, touchHotspot, touchArea, subtargets, TouchAdjustment::zoomableIntersectionQuotient);
 506 }
 507
 508 } // namespace blink