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