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 "Editor.h" 26#include "FloatPoint.h" 27#include "FloatQuad.h" 28#include "FrameView.h" 29#include "HTMLFrameOwnerElement.h" 30#include "HTMLInputElement.h" 31#include "HTMLLabelElement.h" 32#include "HTMLNames.h" 33#include "IntPoint.h" 34#include "IntSize.h" 35#include "Node.h" 36#include "NodeRenderStyle.h" 37#include "RenderBox.h" 38#include "RenderObject.h" 39#include "RenderStyle.h" 40#include "RenderText.h" 41#include "ShadowRoot.h" 42#include "Text.h" 43#include "TextBreakIterator.h" 44 45namespace WebCore { 46 47namespace TouchAdjustment { 48 49const float zeroTolerance = 1e-6f; 50 51// Class for remembering absolute quads of a target node and what node they represent. 52class SubtargetGeometry { 53public: 54 SubtargetGeometry(Node* node, const FloatQuad& quad) 55 : m_node(node) 56 , m_quad(quad) 57 { } 58 59 Node* node() const { return m_node; } 60 FloatQuad quad() const { return m_quad; } 61 IntRect boundingBox() const { return m_quad.enclosingBoundingBox(); } 62 63private: 64 Node* m_node; 65 FloatQuad m_quad; 66}; 67 68typedef Vector<SubtargetGeometry> SubtargetGeometryList; 69typedef bool (*NodeFilter)(Node*); 70typedef void (*AppendSubtargetsForNode)(Node*, SubtargetGeometryList&); 71typedef float (*DistanceFunction)(const IntPoint&, const IntRect&, const SubtargetGeometry&); 72 73// Takes non-const Node* because isContentEditable is a non-const function. 74bool nodeRespondsToTapGesture(Node* node) 75{ 76 if (node->willRespondToMouseClickEvents() || node->willRespondToMouseMoveEvents()) 77 return true; 78 // Accept nodes that has a CSS effect when touched. 79 if (node->isElementNode()) { 80 Element* element = toElement(node); 81 if (element->isMouseFocusable()) 82 return true; 83 if (element->childrenAffectedByActive() || element->childrenAffectedByHover()) 84 return true; 85 } 86 if (RenderStyle* renderStyle = node->renderStyle()) { 87 if (renderStyle->affectedByActive() || renderStyle->affectedByHover()) 88 return true; 89 } 90 return false; 91} 92 93bool nodeIsZoomTarget(Node* node) 94{ 95 if (node->isTextNode() || node->isShadowRoot()) 96 return false; 97 98 ASSERT(node->renderer()); 99 return node->renderer()->isBox(); 100} 101 102bool providesContextMenuItems(Node* node) 103{ 104 // This function tries to match the nodes that receive special context-menu items in 105 // ContextMenuController::populate(), and should be kept uptodate with those. 106 ASSERT(node->renderer() || node->isShadowRoot()); 107 if (!node->renderer()) 108 return false; 109 if (node->isContentEditable()) 110 return true; 111 if (node->isLink()) 112 return true; 113 if (node->renderer()->isImage()) 114 return true; 115 if (node->renderer()->isMedia()) 116 return true; 117 if (node->renderer()->canBeSelectionLeaf()) { 118 // If the context menu gesture will trigger a selection all selectable nodes are valid targets. 119 if (node->renderer()->frame()->editor().behavior().shouldSelectOnContextualMenuClick()) 120 return true; 121 // Only the selected part of the renderer is a valid target, but this will be corrected in 122 // appendContextSubtargetsForNode. 123 if (node->renderer()->selectionState() != RenderObject::SelectionNone) 124 return true; 125 } 126 return false; 127} 128 129static inline void appendQuadsToSubtargetList(Vector<FloatQuad>& quads, Node* node, SubtargetGeometryList& subtargets) 130{ 131 Vector<FloatQuad>::const_iterator it = quads.begin(); 132 const Vector<FloatQuad>::const_iterator end = quads.end(); 133 for (; it != end; ++it) 134 subtargets.append(SubtargetGeometry(node, *it)); 135} 136 137static inline void appendBasicSubtargetsForNode(Node* node, SubtargetGeometryList& subtargets) 138{ 139 // Node guaranteed to have renderer due to check in node filter. 140 ASSERT(node->renderer()); 141 142 Vector<FloatQuad> quads; 143 node->renderer()->absoluteQuads(quads); 144 145 appendQuadsToSubtargetList(quads, node, subtargets); 146} 147 148static inline void appendContextSubtargetsForNode(Node* node, SubtargetGeometryList& subtargets) 149{ 150 // This is a variant of appendBasicSubtargetsForNode that adds special subtargets for 151 // selected or auto-selectable parts of text nodes. 152 ASSERT(node->renderer()); 153 154 if (!node->isTextNode()) 155 return appendBasicSubtargetsForNode(node, subtargets); 156 157 Text* textNode = static_cast<WebCore::Text*>(node); 158 RenderText* textRenderer = static_cast<RenderText*>(textNode->renderer()); 159 160 if (textRenderer->frame()->editor().behavior().shouldSelectOnContextualMenuClick()) { 161 // Make subtargets out of every word. 162 String textValue = textNode->data(); 163 TextBreakIterator* wordIterator = wordBreakIterator(textValue.characters(), textValue.length()); 164 int lastOffset = textBreakFirst(wordIterator); 165 if (lastOffset == -1) 166 return; 167 int offset; 168 while ((offset = textBreakNext(wordIterator)) != -1) { 169 if (isWordTextBreak(wordIterator)) { 170 Vector<FloatQuad> quads; 171 textRenderer->absoluteQuadsForRange(quads, lastOffset, offset); 172 appendQuadsToSubtargetList(quads, textNode, subtargets); 173 } 174 lastOffset = offset; 175 } 176 } else { 177 if (textRenderer->selectionState() == RenderObject::SelectionNone) 178 return appendBasicSubtargetsForNode(node, subtargets); 179 // If selected, make subtargets out of only the selected part of the text. 180 int startPos, endPos; 181 switch (textRenderer->selectionState()) { 182 case RenderObject::SelectionInside: 183 startPos = 0; 184 endPos = textRenderer->textLength(); 185 break; 186 case RenderObject::SelectionStart: 187 textRenderer->selectionStartEnd(startPos, endPos); 188 endPos = textRenderer->textLength(); 189 break; 190 case RenderObject::SelectionEnd: 191 textRenderer->selectionStartEnd(startPos, endPos); 192 startPos = 0; 193 break; 194 case RenderObject::SelectionBoth: 195 textRenderer->selectionStartEnd(startPos, endPos); 196 break; 197 default: 198 ASSERT_NOT_REACHED(); 199 return; 200 } 201 Vector<FloatQuad> quads; 202 textRenderer->absoluteQuadsForRange(quads, startPos, endPos); 203 appendQuadsToSubtargetList(quads, textNode, subtargets); 204 } 205} 206 207static inline void appendZoomableSubtargets(Node* node, SubtargetGeometryList& subtargets) 208{ 209 RenderBox* renderer = toRenderBox(node->renderer()); 210 ASSERT(renderer); 211 212 Vector<FloatQuad> quads; 213 FloatRect borderBoxRect = renderer->borderBoxRect(); 214 FloatRect contentBoxRect = renderer->contentBoxRect(); 215 quads.append(renderer->localToAbsoluteQuad(borderBoxRect)); 216 if (borderBoxRect != contentBoxRect) 217 quads.append(renderer->localToAbsoluteQuad(contentBoxRect)); 218 // FIXME: For RenderBlocks, add column boxes and content boxes cleared for floats. 219 220 Vector<FloatQuad>::const_iterator it = quads.begin(); 221 const Vector<FloatQuad>::const_iterator end = quads.end(); 222 for (; it != end; ++it) 223 subtargets.append(SubtargetGeometry(node, *it)); 224} 225 226static inline Node* parentShadowHostOrOwner(const Node* node) 227{ 228 if (Node* ancestor = node->parentOrShadowHostNode()) 229 return ancestor; 230 if (node->isDocumentNode()) 231 return toDocument(node)->ownerElement(); 232 return 0; 233} 234 235// Compiles a list of subtargets of all the relevant target nodes. 236void compileSubtargetList(const NodeListHashSet& intersectedNodes, SubtargetGeometryList& subtargets, NodeFilter nodeFilter, AppendSubtargetsForNode appendSubtargetsForNode) 237{ 238 // Find candidates responding to tap gesture events in O(n) time. 239 HashMap<Node*, Node*> responderMap; 240 HashSet<Node*> ancestorsToRespondersSet; 241 Vector<Node*> candidates; 242 HashSet<Node*> editableAncestors; 243 244 // A node matching the NodeFilter is called a responder. Candidate nodes must either be a 245 // responder or have an ancestor that is a responder. 246 // This iteration tests all ancestors at most once by caching earlier results. 247 NodeListHashSet::const_iterator end = intersectedNodes.end(); 248 for (NodeListHashSet::const_iterator it = intersectedNodes.begin(); it != end; ++it) { 249 Node* const node = it->get(); 250 Vector<Node*> visitedNodes; 251 Node* respondingNode = 0; 252 for (Node* visitedNode = node; visitedNode; visitedNode = visitedNode->parentOrShadowHostNode()) { 253 // Check if we already have a result for a common ancestor from another candidate. 254 respondingNode = responderMap.get(visitedNode); 255 if (respondingNode) 256 break; 257 visitedNodes.append(visitedNode); 258 // Check if the node filter applies, which would mean we have found a responding node. 259 if (nodeFilter(visitedNode)) { 260 respondingNode = visitedNode; 261 // Continue the iteration to collect the ancestors of the responder, which we will need later. 262 for (visitedNode = parentShadowHostOrOwner(visitedNode); visitedNode; visitedNode = parentShadowHostOrOwner(visitedNode)) { 263 HashSet<Node*>::AddResult addResult = ancestorsToRespondersSet.add(visitedNode); 264 if (!addResult.isNewEntry) 265 break; 266 } 267 break; 268 } 269 } 270 // Insert the detected responder for all the visited nodes. 271 for (unsigned j = 0; j < visitedNodes.size(); j++) 272 responderMap.add(visitedNodes[j], respondingNode); 273 274 if (respondingNode) 275 candidates.append(node); 276 } 277 278 // We compile the list of component absolute quads instead of using the bounding rect 279 // to be able to perform better hit-testing on inline links on line-breaks. 280 unsigned length = candidates.size(); 281 for (unsigned i = 0; i < length; i++) { 282 Node* candidate = candidates[i]; 283 // Skip nodes who's responders are ancestors of other responders. This gives preference to 284 // the inner-most event-handlers. So that a link is always preferred even when contained 285 // in an element that monitors all click-events. 286 Node* respondingNode = responderMap.get(candidate); 287 ASSERT(respondingNode); 288 if (ancestorsToRespondersSet.contains(respondingNode)) 289 continue; 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->parentOrShadowHostNode(); 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->parentOrShadowHostNode(); 304 } 305 candidate = replacement; 306 } 307 if (candidate) 308 appendSubtargetsForNode(candidate, subtargets); 309 } 310} 311 312// Compiles a list of zoomable subtargets. 313void compileZoomableSubtargets(const NodeListHashSet& intersectedNodes, SubtargetGeometryList& subtargets) 314{ 315 NodeListHashSet::const_iterator end = intersectedNodes.end(); 316 for (NodeListHashSet::const_iterator it = intersectedNodes.begin(); it != end; ++it) { 317 Node* const candidate = it->get(); 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. 325float 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. 348float 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 370FloatPoint 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. 379void 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 392bool 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. 442bool 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 479bool findBestClickableCandidate(Node*& targetNode, IntPoint &targetPoint, const IntPoint &touchHotspot, const IntRect &touchArea, const NodeListHashSet& 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 487bool findBestContextMenuCandidate(Node*& targetNode, IntPoint &targetPoint, const IntPoint &touchHotspot, const IntRect &touchArea, const NodeListHashSet& 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 495bool findBestZoomableArea(Node*& targetNode, IntRect& targetArea, const IntPoint& touchHotspot, const IntRect& touchArea, const NodeListHashSet& 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 504