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