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