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 WebCore { 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(WebCore::TouchAdjustment::SubtargetGeometry) 71 72 namespace WebCore { 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 = toRenderText(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 if (targetNode) { 477 targetArea = targetNode->document().view()->contentsToWindow(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 WebCore 509