da63afa64dcc512b457b1a0c56a992a67da49cd1
[WebKit-https.git] / Source / WebCore / page / TouchAdjustment.cpp
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 "FloatPoint.h"
26 #include "FloatQuad.h"
27 #include "FrameView.h"
28 #include "HTMLLabelElement.h"
29 #include "HTMLNames.h"
30 #include "IntPoint.h"
31 #include "IntSize.h"
32 #include "Node.h"
33 #include "NodeRenderStyle.h"
34 #include "RenderBox.h"
35 #include "RenderObject.h"
36 #include "RenderStyle.h"
37
38 namespace WebCore {
39
40 namespace TouchAdjustment {
41
42 // Class for remembering absolute quads of a target node and what node they represent.
43 class SubtargetGeometry {
44 public:
45     SubtargetGeometry(Node* node, const FloatQuad& quad)
46         : m_node(node)
47         , m_quad(quad)
48     { }
49
50     Node* node() const { return m_node; }
51     FloatQuad quad() const { return m_quad; }
52     IntRect boundingBox() const { return m_quad.enclosingBoundingBox(); }
53
54 private:
55     Node* m_node;
56     FloatQuad m_quad;
57 };
58
59 typedef Vector<SubtargetGeometry> SubtargetGeometryList;
60 typedef bool (*NodeFilter)(Node*);
61 typedef float (*DistanceFunction)(const IntPoint&, const IntRect&, const SubtargetGeometry&);
62
63 // Takes non-const Node* because isContentEditable is a non-const function.
64 bool nodeRespondsToTapGesture(Node* node)
65 {
66     if (node->isLink()
67         || node->isContentEditable()
68         || node->isMouseFocusable())
69         return true;
70     if (node->isElementNode()) {
71         Element* element =  static_cast<Element*>(node);
72         if (element->hasTagName(HTMLNames::labelTag) && static_cast<HTMLLabelElement*>(element)->control())
73             return true;
74     }
75     // FIXME: Implement hasDefaultEventHandler and use that instead of all of the above checks.
76     if (node->hasEventListeners()
77         && (node->hasEventListeners(eventNames().clickEvent)
78             || node->hasEventListeners(eventNames().DOMActivateEvent)
79             || node->hasEventListeners(eventNames().mousedownEvent)
80             || node->hasEventListeners(eventNames().mouseupEvent)
81             || node->hasEventListeners(eventNames().mousemoveEvent)
82             // Checking for focus events is not necessary since they can only fire on
83             // focusable elements which have already been captured above.
84         ))
85         return true;
86     if (node->renderStyle()) {
87         // Accept nodes that has a CSS effect when touched.
88         if (node->renderStyle()->affectedByActiveRules() || node->renderStyle()->affectedByHoverRules())
89             return true;
90     }
91     return false;
92 }
93
94 static inline void appendSubtargetsForNodeToList(Node* node, SubtargetGeometryList& subtargets)
95 {
96     // Since the node is a result of a hit test, we are already ensured it has a renderer.
97     ASSERT(node->renderer());
98
99     Vector<FloatQuad> quads;
100     node->renderer()->absoluteQuads(quads);
101
102     Vector<FloatQuad>::const_iterator it = quads.begin();
103     const Vector<FloatQuad>::const_iterator end = quads.end();
104     for (; it != end; ++it)
105         subtargets.append(SubtargetGeometry(node, *it));
106 }
107
108 // Compiles a list of subtargets of all the relevant target nodes.
109 void compileSubtargetList(const NodeList& intersectedNodes, SubtargetGeometryList& subtargets, NodeFilter nodeFilter)
110 {
111     // Find candidates responding to tap gesture events in O(n) time.
112     HashMap<Node*, Node*> responderMap;
113     HashSet<Node*> ancestorsToRespondersSet;
114     Vector<Node*> candidates;
115
116     // A node matching the NodeFilter is called a responder. Candidate nodes must either be a
117     // responder or have an ancestor that is a responder.
118     // This iteration tests all ancestors at most once by caching earlier results.
119     unsigned length = intersectedNodes.length();
120     for (unsigned i = 0; i < length; ++i) {
121         Node* const node = intersectedNodes.item(i);
122         Vector<Node*> visitedNodes;
123         Node* respondingNode = 0;
124         for (Node* visitedNode = node; visitedNode; visitedNode = visitedNode->parentOrHostNode()) {
125             // Check if we already have a result for a common ancestor from another candidate.
126             respondingNode = responderMap.get(visitedNode);
127             if (respondingNode)
128                 break;
129             visitedNodes.append(visitedNode);
130             // Check if the node filter applies, which would mean we have found a responding node.
131             if (nodeFilter(visitedNode)) {
132                 respondingNode = visitedNode;
133                 // Continue the iteration to collect the ancestors of the responder, which we will need later.
134                 for (visitedNode = visitedNode->parentOrHostNode(); visitedNode; visitedNode = visitedNode->parentOrHostNode()) {
135                     HashSet<Node*>::AddResult addResult = ancestorsToRespondersSet.add(visitedNode);
136                     if (!addResult.isNewEntry)
137                         break;
138                 }
139                 break;
140             }
141         }
142         // Insert the detected responder for all the visited nodes.
143         for (unsigned j = 0; j < visitedNodes.size(); j++)
144             responderMap.add(visitedNodes[j], respondingNode);
145
146         if (respondingNode)
147             candidates.append(node);
148     }
149
150     // We compile the list of component absolute quads instead of using the bounding rect
151     // to be able to perform better hit-testing on inline links on line-breaks.
152     length = candidates.size();
153     for (unsigned i = 0; i < length; i++) {
154         Node* candidate = candidates[i];
155         // Skip nodes who's responders are ancestors of other responders. This gives preference to
156         // the inner-most event-handlers. So that a link is always preferred even when contained
157         // in an element that monitors all click-events.
158         Node* respondingNode = responderMap.get(candidate);
159         ASSERT(respondingNode);
160         if (ancestorsToRespondersSet.contains(respondingNode))
161             continue;
162         appendSubtargetsForNodeToList(candidate, subtargets);
163     }
164 }
165
166 float distanceSquaredToTargetCenterLine(const IntPoint& touchHotspot, const IntRect& touchArea, const SubtargetGeometry& subtarget)
167 {
168     UNUSED_PARAM(touchArea);
169     // For a better center of a line-box we use the center-line instead of the center-point.
170     // We use the center-line of the bounding box of the quad though, since it is much faster
171     // and gives the same result in all untransformed cases, and in transformed cases still
172     // gives a better distance-function than the distance to the center-point.
173     IntRect rect = subtarget.boundingBox();
174     ASSERT(subtarget.node()->document());
175     ASSERT(subtarget.node()->document()->view());
176     // Convert from frame coordinates to window coordinates.
177     rect = subtarget.node()->document()->view()->contentsToWindow(rect);
178
179     return rect.distanceSquaredFromCenterLineToPoint(touchHotspot);
180 }
181
182 // A generic function for finding the target node with the lowest distance metric. A distance metric here is the result
183 // of a distance-like function, that computes how well the touch hits the node.
184 // Distance functions could for instance be distance squared or area of intersection.
185 bool findNodeWithLowestDistanceMetric(Node*& targetNode, IntPoint& targetPoint, const IntPoint& touchHotspot, const IntRect& touchArea, SubtargetGeometryList& subtargets, DistanceFunction distanceFunction)
186 {
187     targetNode = 0;
188     float bestDistanceMetric = INFINITY;
189     SubtargetGeometryList::const_iterator it = subtargets.begin();
190     const SubtargetGeometryList::const_iterator end = subtargets.end();
191     for (; it != end; ++it) {
192         Node* node = it->node();
193         float distanceMetric = distanceFunction(touchHotspot, touchArea, *it);
194         if (distanceMetric < bestDistanceMetric) {
195             targetPoint = roundedIntPoint(it->quad().center());
196             targetNode = node;
197             bestDistanceMetric = distanceMetric;
198         } else if (distanceMetric == bestDistanceMetric) {
199             // Try to always return the inner-most element.
200             if (node->isDescendantOf(targetNode))
201                 targetNode = node;
202         }
203     }
204
205     return (targetNode);
206 }
207
208 } // namespace TouchAdjustment
209
210 bool findBestClickableCandidate(Node*& targetNode, IntPoint &targetPoint, const IntPoint &touchHotspot, const IntRect &touchArea, const NodeList& nodeList)
211 {
212     TouchAdjustment::SubtargetGeometryList subtargets;
213     TouchAdjustment::compileSubtargetList(nodeList, subtargets, TouchAdjustment::nodeRespondsToTapGesture);
214     return TouchAdjustment::findNodeWithLowestDistanceMetric(targetNode, targetPoint, touchHotspot, touchArea, subtargets, TouchAdjustment::distanceSquaredToTargetCenterLine);
215 }
216
217 } // namespace WebCore