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