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