[Qt] Find zoomable area using area-based hit-testing
[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 bool nodeIsZoomTarget(Node* node)
95 {
96     if (node->isTextNode() || node->isShadowRoot())
97         return false;
98
99     ASSERT(node->renderer());
100     return node->renderer()->isBox();
101 }
102
103 static inline void appendSubtargetsForNodeToList(Node* node, SubtargetGeometryList& subtargets)
104 {
105     // Since the node is a result of a hit test, we are already ensured it has a renderer.
106     ASSERT(node->renderer());
107
108     Vector<FloatQuad> quads;
109     node->renderer()->absoluteQuads(quads);
110
111     Vector<FloatQuad>::const_iterator it = quads.begin();
112     const Vector<FloatQuad>::const_iterator end = quads.end();
113     for (; it != end; ++it)
114         subtargets.append(SubtargetGeometry(node, *it));
115 }
116
117 static inline void appendZoomableSubtargets(Node* node, SubtargetGeometryList& subtargets)
118 {
119     RenderBox* renderer = toRenderBox(node->renderer());
120     ASSERT(renderer);
121
122     Vector<FloatQuad> quads;
123     FloatRect borderBoxRect = renderer->borderBoxRect();
124     FloatRect contentBoxRect = renderer->contentBoxRect();
125     quads.append(renderer->localToAbsoluteQuad(borderBoxRect));
126     if (borderBoxRect != contentBoxRect)
127         quads.append(renderer->localToAbsoluteQuad(contentBoxRect));
128     // FIXME: For RenderBlocks, add column boxes and content boxes cleared for floats.
129
130     Vector<FloatQuad>::const_iterator it = quads.begin();
131     const Vector<FloatQuad>::const_iterator end = quads.end();
132     for (; it != end; ++it)
133         subtargets.append(SubtargetGeometry(node, *it));
134 }
135
136 // Compiles a list of subtargets of all the relevant target nodes.
137 void compileSubtargetList(const NodeList& intersectedNodes, SubtargetGeometryList& subtargets, NodeFilter nodeFilter)
138 {
139     // Find candidates responding to tap gesture events in O(n) time.
140     HashMap<Node*, Node*> responderMap;
141     HashSet<Node*> ancestorsToRespondersSet;
142     Vector<Node*> candidates;
143
144     // A node matching the NodeFilter is called a responder. Candidate nodes must either be a
145     // responder or have an ancestor that is a responder.
146     // This iteration tests all ancestors at most once by caching earlier results.
147     unsigned length = intersectedNodes.length();
148     for (unsigned i = 0; i < length; ++i) {
149         Node* const node = intersectedNodes.item(i);
150         Vector<Node*> visitedNodes;
151         Node* respondingNode = 0;
152         for (Node* visitedNode = node; visitedNode; visitedNode = visitedNode->parentOrHostNode()) {
153             // Check if we already have a result for a common ancestor from another candidate.
154             respondingNode = responderMap.get(visitedNode);
155             if (respondingNode)
156                 break;
157             visitedNodes.append(visitedNode);
158             // Check if the node filter applies, which would mean we have found a responding node.
159             if (nodeFilter(visitedNode)) {
160                 respondingNode = visitedNode;
161                 // Continue the iteration to collect the ancestors of the responder, which we will need later.
162                 for (visitedNode = visitedNode->parentOrHostNode(); visitedNode; visitedNode = visitedNode->parentOrHostNode()) {
163                     HashSet<Node*>::AddResult addResult = ancestorsToRespondersSet.add(visitedNode);
164                     if (!addResult.isNewEntry)
165                         break;
166                 }
167                 break;
168             }
169         }
170         // Insert the detected responder for all the visited nodes.
171         for (unsigned j = 0; j < visitedNodes.size(); j++)
172             responderMap.add(visitedNodes[j], respondingNode);
173
174         if (respondingNode)
175             candidates.append(node);
176     }
177
178     // We compile the list of component absolute quads instead of using the bounding rect
179     // to be able to perform better hit-testing on inline links on line-breaks.
180     length = candidates.size();
181     for (unsigned i = 0; i < length; i++) {
182         Node* candidate = candidates[i];
183         // Skip nodes who's responders are ancestors of other responders. This gives preference to
184         // the inner-most event-handlers. So that a link is always preferred even when contained
185         // in an element that monitors all click-events.
186         Node* respondingNode = responderMap.get(candidate);
187         ASSERT(respondingNode);
188         if (ancestorsToRespondersSet.contains(respondingNode))
189             continue;
190         appendSubtargetsForNodeToList(candidate, subtargets);
191     }
192 }
193
194 // Compiles a list of zoomable subtargets.
195 void compileZoomableSubtargets(const NodeList& intersectedNodes, SubtargetGeometryList& subtargets)
196 {
197     unsigned length = intersectedNodes.length();
198     for (unsigned i = 0; i < length; ++i) {
199         Node* const candidate = intersectedNodes.item(i);
200         if (nodeIsZoomTarget(candidate))
201             appendZoomableSubtargets(candidate, subtargets);
202     }
203 }
204
205
206 float distanceSquaredToTargetCenterLine(const IntPoint& touchHotspot, const IntRect& touchArea, const SubtargetGeometry& subtarget)
207 {
208     UNUSED_PARAM(touchArea);
209     // For a better center of a line-box we use the center-line instead of the center-point.
210     // We use the center-line of the bounding box of the quad though, since it is much faster
211     // and gives the same result in all untransformed cases, and in transformed cases still
212     // gives a better distance-function than the distance to the center-point.
213     IntRect rect = subtarget.boundingBox();
214     ASSERT(subtarget.node()->document());
215     ASSERT(subtarget.node()->document()->view());
216     // Convert from frame coordinates to window coordinates.
217     rect = subtarget.node()->document()->view()->contentsToWindow(rect);
218
219     return rect.distanceSquaredFromCenterLineToPoint(touchHotspot);
220 }
221
222 float areaOfIntersection(const IntPoint& touchHotspot, const IntRect& touchArea, const SubtargetGeometry& subtarget)
223 {
224     UNUSED_PARAM(touchHotspot);
225     IntRect rect = subtarget.boundingBox();
226
227     // Convert from frame coordinates to window coordinates.
228     rect = subtarget.node()->document()->view()->contentsToWindow(rect);
229     rect.intersect(touchArea);
230
231     return rect.size().area();
232 }
233
234
235 // A generic function for finding the target node with the lowest distance metric. A distance metric here is the result
236 // of a distance-like function, that computes how well the touch hits the node.
237 // Distance functions could for instance be distance squared or area of intersection.
238 bool findNodeWithLowestDistanceMetric(Node*& targetNode, IntPoint& targetPoint, const IntPoint& touchHotspot, const IntRect& touchArea, SubtargetGeometryList& subtargets, DistanceFunction distanceFunction)
239 {
240     targetNode = 0;
241     float bestDistanceMetric = INFINITY;
242     SubtargetGeometryList::const_iterator it = subtargets.begin();
243     const SubtargetGeometryList::const_iterator end = subtargets.end();
244     for (; it != end; ++it) {
245         Node* node = it->node();
246         float distanceMetric = distanceFunction(touchHotspot, touchArea, *it);
247         if (distanceMetric < bestDistanceMetric) {
248             targetPoint = roundedIntPoint(it->quad().center());
249             targetNode = node;
250             bestDistanceMetric = distanceMetric;
251         } else if (distanceMetric == bestDistanceMetric) {
252             // Try to always return the inner-most element.
253             if (node->isDescendantOf(targetNode))
254                 targetNode = node;
255         }
256     }
257
258     return (targetNode);
259 }
260
261 // Similar generic function as findNodeWithLowestDistanceMetric, except this finds the innermost area with the largest intersection.
262 bool findAreaWithLargestIntersection(Node*& targetNode, IntRect& targetArea, const IntPoint& touchHotspot, const IntRect& touchArea, SubtargetGeometryList& subtargets)
263 {
264     targetNode = 0;
265     float bestDistanceMetric = 0.;
266     SubtargetGeometryList::const_iterator it = subtargets.begin();
267     const SubtargetGeometryList::const_iterator end = subtargets.end();
268     for (; it != end; ++it) {
269         Node* node = it->node();
270         float distanceMetric = areaOfIntersection(touchHotspot, touchArea, *it);
271         if (distanceMetric > bestDistanceMetric) {
272             targetArea = it->boundingBox();
273             targetNode = node;
274             bestDistanceMetric = distanceMetric;
275         } else if (distanceMetric == bestDistanceMetric) {
276             // Try to return the smallest inner-most subtarget.
277             if (node == targetNode) {
278                 if (it->boundingBox().size().area() < targetArea.size().area())
279                     targetArea = it->boundingBox();
280             } else if (node->isDescendantOf(targetNode)) {
281                 targetArea = it->boundingBox();
282                 targetNode = node;
283             }
284         }
285     }
286
287     return (targetNode);
288 }
289
290
291 } // namespace TouchAdjustment
292
293 bool findBestClickableCandidate(Node*& targetNode, IntPoint &targetPoint, const IntPoint &touchHotspot, const IntRect &touchArea, const NodeList& nodeList)
294 {
295     TouchAdjustment::SubtargetGeometryList subtargets;
296     TouchAdjustment::compileSubtargetList(nodeList, subtargets, TouchAdjustment::nodeRespondsToTapGesture);
297     return TouchAdjustment::findNodeWithLowestDistanceMetric(targetNode, targetPoint, touchHotspot, touchArea, subtargets, TouchAdjustment::distanceSquaredToTargetCenterLine);
298 }
299
300 bool findBestZoomableArea(Node*& targetNode, IntRect& targetArea, const IntPoint& touchHotspot, const IntRect& touchArea, const NodeList& nodeList)
301 {
302     TouchAdjustment::SubtargetGeometryList subtargets;
303     TouchAdjustment::compileZoomableSubtargets(nodeList, subtargets);
304     return TouchAdjustment::findAreaWithLargestIntersection(targetNode, targetArea, touchHotspot, touchArea, subtargets);
305 }
306
307 } // namespace WebCore