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