| /* |
| * Copyright (C) 2012 Nokia Corporation and/or its subsidiary(-ies) |
| * |
| * This library is free software; you can redistribute it and/or |
| * modify it under the terms of the GNU Library General Public |
| * License as published by the Free Software Foundation; either |
| * version 2 of the License, or (at your option) any later version. |
| * |
| * This library is distributed in the hope that it will be useful, |
| * but WITHOUT ANY WARRANTY; without even the implied warranty of |
| * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU |
| * Library General Public License for more details. |
| * |
| * You should have received a copy of the GNU Library General Public License |
| * along with this library; see the file COPYING.LIB. If not, write to |
| * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, |
| * Boston, MA 02110-1301, USA. |
| */ |
| |
| #include "core/page/TouchAdjustment.h" |
| |
| #include "core/dom/ContainerNode.h" |
| #include "core/dom/Node.h" |
| #include "core/dom/NodeComputedStyle.h" |
| #include "core/dom/Text.h" |
| #include "core/editing/EditingUtilities.h" |
| #include "core/editing/Editor.h" |
| #include "core/frame/FrameView.h" |
| #include "core/frame/LocalFrame.h" |
| #include "core/html/HTMLFrameOwnerElement.h" |
| #include "core/layout/LayoutBox.h" |
| #include "core/layout/LayoutObject.h" |
| #include "core/layout/LayoutText.h" |
| #include "core/layout/api/SelectionState.h" |
| #include "core/style/ComputedStyle.h" |
| #include "platform/geometry/FloatPoint.h" |
| #include "platform/geometry/FloatQuad.h" |
| #include "platform/geometry/IntSize.h" |
| #include "platform/text/TextBreakIterator.h" |
| |
| namespace blink { |
| |
| namespace TouchAdjustment { |
| |
| const float zeroTolerance = 1e-6f; |
| |
| // Class for remembering absolute quads of a target node and what node they |
| // represent. |
| class SubtargetGeometry { |
| DISALLOW_NEW_EXCEPT_PLACEMENT_NEW(); |
| |
| public: |
| SubtargetGeometry(Node* node, const FloatQuad& quad) |
| : m_node(node), m_quad(quad) {} |
| DEFINE_INLINE_TRACE() { visitor->trace(m_node); } |
| |
| Node* node() const { return m_node; } |
| FloatQuad quad() const { return m_quad; } |
| IntRect boundingBox() const { return m_quad.enclosingBoundingBox(); } |
| |
| private: |
| Member<Node> m_node; |
| FloatQuad m_quad; |
| }; |
| |
| } // namespace TouchAdjustment |
| |
| } // namespace blink |
| |
| WTF_ALLOW_MOVE_INIT_AND_COMPARE_WITH_MEM_FUNCTIONS( |
| blink::TouchAdjustment::SubtargetGeometry) |
| |
| namespace blink { |
| |
| namespace TouchAdjustment { |
| |
| typedef HeapVector<SubtargetGeometry> SubtargetGeometryList; |
| typedef bool (*NodeFilter)(Node*); |
| typedef void (*AppendSubtargetsForNode)(Node*, SubtargetGeometryList&); |
| typedef float (*DistanceFunction)(const IntPoint&, |
| const IntRect&, |
| const SubtargetGeometry&); |
| |
| // Takes non-const Node* because isContentEditable is a non-const function. |
| bool nodeRespondsToTapGesture(Node* node) { |
| if (node->willRespondToMouseClickEvents() || |
| node->willRespondToMouseMoveEvents()) |
| return true; |
| if (node->isElementNode()) { |
| Element* element = toElement(node); |
| // Tapping on a text field or other focusable item should trigger |
| // adjustment, except that iframe elements are hard-coded to support focus |
| // but the effect is often invisible so they should be excluded. |
| if (element->isMouseFocusable() && !isHTMLIFrameElement(element)) |
| return true; |
| // Accept nodes that has a CSS effect when touched. |
| if (element->childrenOrSiblingsAffectedByActive() || |
| element->childrenOrSiblingsAffectedByHover()) |
| return true; |
| } |
| if (const ComputedStyle* computedStyle = node->computedStyle()) { |
| if (computedStyle->affectedByActive() || computedStyle->affectedByHover()) |
| return true; |
| } |
| return false; |
| } |
| |
| bool nodeIsZoomTarget(Node* node) { |
| if (node->isTextNode() || node->isShadowRoot()) |
| return false; |
| |
| ASSERT(node->layoutObject()); |
| return node->layoutObject()->isBox(); |
| } |
| |
| bool providesContextMenuItems(Node* node) { |
| // This function tries to match the nodes that receive special context-menu |
| // items in ContextMenuController::populate(), and should be kept uptodate |
| // with those. |
| ASSERT(node->layoutObject() || node->isShadowRoot()); |
| if (!node->layoutObject()) |
| return false; |
| node->document().updateStyleAndLayoutTree(); |
| if (hasEditableStyle(*node)) |
| return true; |
| if (node->isLink()) |
| return true; |
| if (node->layoutObject()->isImage()) |
| return true; |
| if (node->layoutObject()->isMedia()) |
| return true; |
| if (node->layoutObject()->canBeSelectionLeaf()) { |
| // If the context menu gesture will trigger a selection all selectable nodes |
| // are valid targets. |
| if (node->layoutObject() |
| ->frame() |
| ->editor() |
| .behavior() |
| .shouldSelectOnContextualMenuClick()) |
| return true; |
| // Only the selected part of the layoutObject is a valid target, but this |
| // will be corrected in appendContextSubtargetsForNode. |
| if (node->layoutObject()->getSelectionState() != SelectionNone) |
| return true; |
| } |
| return false; |
| } |
| |
| static inline void appendQuadsToSubtargetList( |
| Vector<FloatQuad>& quads, |
| Node* node, |
| SubtargetGeometryList& subtargets) { |
| Vector<FloatQuad>::const_iterator it = quads.begin(); |
| const Vector<FloatQuad>::const_iterator end = quads.end(); |
| for (; it != end; ++it) |
| subtargets.append(SubtargetGeometry(node, *it)); |
| } |
| |
| static inline void appendBasicSubtargetsForNode( |
| Node* node, |
| SubtargetGeometryList& subtargets) { |
| // Node guaranteed to have layoutObject due to check in node filter. |
| ASSERT(node->layoutObject()); |
| |
| Vector<FloatQuad> quads; |
| node->layoutObject()->absoluteQuads(quads); |
| |
| appendQuadsToSubtargetList(quads, node, subtargets); |
| } |
| |
| static inline void appendContextSubtargetsForNode( |
| Node* node, |
| SubtargetGeometryList& subtargets) { |
| // This is a variant of appendBasicSubtargetsForNode that adds special |
| // subtargets for selected or auto-selectable parts of text nodes. |
| ASSERT(node->layoutObject()); |
| |
| if (!node->isTextNode()) |
| return appendBasicSubtargetsForNode(node, subtargets); |
| |
| Text* textNode = toText(node); |
| LayoutText* textLayoutObject = textNode->layoutObject(); |
| |
| if (textLayoutObject->frame() |
| ->editor() |
| .behavior() |
| .shouldSelectOnContextualMenuClick()) { |
| // Make subtargets out of every word. |
| String textValue = textNode->data(); |
| TextBreakIterator* wordIterator = |
| wordBreakIterator(textValue, 0, textValue.length()); |
| int lastOffset = wordIterator->first(); |
| if (lastOffset == -1) |
| return; |
| int offset; |
| while ((offset = wordIterator->next()) != -1) { |
| if (isWordTextBreak(wordIterator)) { |
| Vector<FloatQuad> quads; |
| textLayoutObject->absoluteQuadsForRange(quads, lastOffset, offset); |
| appendQuadsToSubtargetList(quads, textNode, subtargets); |
| } |
| lastOffset = offset; |
| } |
| } else { |
| if (textLayoutObject->getSelectionState() == SelectionNone) |
| return appendBasicSubtargetsForNode(node, subtargets); |
| // If selected, make subtargets out of only the selected part of the text. |
| int startPos, endPos; |
| switch (textLayoutObject->getSelectionState()) { |
| case SelectionInside: |
| startPos = 0; |
| endPos = textLayoutObject->textLength(); |
| break; |
| case SelectionStart: |
| textLayoutObject->selectionStartEnd(startPos, endPos); |
| endPos = textLayoutObject->textLength(); |
| break; |
| case SelectionEnd: |
| textLayoutObject->selectionStartEnd(startPos, endPos); |
| startPos = 0; |
| break; |
| case SelectionBoth: |
| textLayoutObject->selectionStartEnd(startPos, endPos); |
| break; |
| default: |
| ASSERT_NOT_REACHED(); |
| return; |
| } |
| Vector<FloatQuad> quads; |
| textLayoutObject->absoluteQuadsForRange(quads, startPos, endPos); |
| appendQuadsToSubtargetList(quads, textNode, subtargets); |
| } |
| } |
| |
| static inline void appendZoomableSubtargets(Node* node, |
| SubtargetGeometryList& subtargets) { |
| LayoutBox* layoutObject = toLayoutBox(node->layoutObject()); |
| ASSERT(layoutObject); |
| |
| Vector<FloatQuad> quads; |
| FloatRect borderBoxRect(layoutObject->borderBoxRect()); |
| FloatRect contentBoxRect(layoutObject->contentBoxRect()); |
| quads.append(layoutObject->localToAbsoluteQuad(borderBoxRect)); |
| if (borderBoxRect != contentBoxRect) |
| quads.append(layoutObject->localToAbsoluteQuad(contentBoxRect)); |
| // FIXME: For LayoutBlocks, add column boxes and content boxes cleared for |
| // floats. |
| |
| Vector<FloatQuad>::const_iterator it = quads.begin(); |
| const Vector<FloatQuad>::const_iterator end = quads.end(); |
| for (; it != end; ++it) |
| subtargets.append(SubtargetGeometry(node, *it)); |
| } |
| |
| static inline Node* parentShadowHostOrOwner(const Node* node) { |
| if (Node* ancestor = node->parentOrShadowHostNode()) |
| return ancestor; |
| if (node->isDocumentNode()) |
| return toDocument(node)->localOwner(); |
| return nullptr; |
| } |
| |
| // Compiles a list of subtargets of all the relevant target nodes. |
| void compileSubtargetList(const HeapVector<Member<Node>>& intersectedNodes, |
| SubtargetGeometryList& subtargets, |
| NodeFilter nodeFilter, |
| AppendSubtargetsForNode appendSubtargetsForNode) { |
| // Find candidates responding to tap gesture events in O(n) time. |
| HeapHashMap<Member<Node>, Member<Node>> responderMap; |
| HeapHashSet<Member<Node>> ancestorsToRespondersSet; |
| HeapVector<Member<Node>> candidates; |
| HeapHashSet<Member<Node>> editableAncestors; |
| |
| // A node matching the NodeFilter is called a responder. Candidate nodes must |
| // either be a responder or have an ancestor that is a responder. This |
| // iteration tests all ancestors at most once by caching earlier results. |
| for (unsigned i = 0; i < intersectedNodes.size(); ++i) { |
| Node* node = intersectedNodes[i].get(); |
| HeapVector<Member<Node>> visitedNodes; |
| Node* respondingNode = nullptr; |
| for (Node* visitedNode = node; visitedNode; |
| visitedNode = visitedNode->parentOrShadowHostNode()) { |
| // Check if we already have a result for a common ancestor from another |
| // candidate. |
| respondingNode = responderMap.get(visitedNode); |
| if (respondingNode) |
| break; |
| visitedNodes.append(visitedNode); |
| // Check if the node filter applies, which would mean we have found a |
| // responding node. |
| if (nodeFilter(visitedNode)) { |
| respondingNode = visitedNode; |
| // Continue the iteration to collect the ancestors of the responder, |
| // which we will need later. |
| for (visitedNode = parentShadowHostOrOwner(visitedNode); visitedNode; |
| visitedNode = parentShadowHostOrOwner(visitedNode)) { |
| HeapHashSet<Member<Node>>::AddResult addResult = |
| ancestorsToRespondersSet.add(visitedNode); |
| if (!addResult.isNewEntry) |
| break; |
| } |
| break; |
| } |
| } |
| // Insert the detected responder for all the visited nodes. |
| for (unsigned j = 0; j < visitedNodes.size(); j++) |
| responderMap.add(visitedNodes[j], respondingNode); |
| |
| if (respondingNode) |
| candidates.append(node); |
| } |
| |
| // We compile the list of component absolute quads instead of using the |
| // bounding rect to be able to perform better hit-testing on inline links on |
| // line-breaks. |
| for (unsigned i = 0; i < candidates.size(); i++) { |
| Node* candidate = candidates[i]; |
| // Skip nodes who's responders are ancestors of other responders. This gives |
| // preference to the inner-most event-handlers. So that a link is always |
| // preferred even when contained in an element that monitors all |
| // click-events. |
| Node* respondingNode = responderMap.get(candidate); |
| ASSERT(respondingNode); |
| if (ancestorsToRespondersSet.contains(respondingNode)) |
| continue; |
| // Consolidate bounds for editable content. |
| if (editableAncestors.contains(candidate)) |
| continue; |
| candidate->document().updateStyleAndLayoutTree(); |
| if (hasEditableStyle(*candidate)) { |
| Node* replacement = candidate; |
| Node* parent = candidate->parentOrShadowHostNode(); |
| while (parent && hasEditableStyle(*parent)) { |
| replacement = parent; |
| if (editableAncestors.contains(replacement)) { |
| replacement = nullptr; |
| break; |
| } |
| editableAncestors.add(replacement); |
| parent = parent->parentOrShadowHostNode(); |
| } |
| candidate = replacement; |
| } |
| if (candidate) |
| appendSubtargetsForNode(candidate, subtargets); |
| } |
| } |
| |
| // Compiles a list of zoomable subtargets. |
| void compileZoomableSubtargets(const HeapVector<Member<Node>>& intersectedNodes, |
| SubtargetGeometryList& subtargets) { |
| for (unsigned i = 0; i < intersectedNodes.size(); ++i) { |
| Node* candidate = intersectedNodes[i].get(); |
| if (nodeIsZoomTarget(candidate)) |
| appendZoomableSubtargets(candidate, subtargets); |
| } |
| } |
| |
| // This returns quotient of the target area and its intersection with the touch |
| // area. This will prioritize largest intersection and smallest area, while |
| // balancing the two against each other. |
| float zoomableIntersectionQuotient(const IntPoint& touchHotspot, |
| const IntRect& touchArea, |
| const SubtargetGeometry& subtarget) { |
| IntRect rect = subtarget.node()->document().view()->contentsToRootFrame( |
| subtarget.boundingBox()); |
| |
| // Check the rectangle is meaningful zoom target. It should at least contain |
| // the hotspot. |
| if (!rect.contains(touchHotspot)) |
| return std::numeric_limits<float>::infinity(); |
| IntRect intersection = rect; |
| intersection.intersect(touchArea); |
| |
| // Return the quotient of the intersection. |
| return rect.size().area() / (float)intersection.size().area(); |
| } |
| |
| // Uses a hybrid of distance to adjust and intersect ratio, normalizing each |
| // score between 0 and 1 and combining them. The distance to adjust works best |
| // for disambiguating clicks on targets such as links, where the width may be |
| // significantly larger than the touch width. Using area of overlap in such |
| // cases can lead to a bias towards shorter links. Conversely, percentage of |
| // overlap can provide strong confidence in tapping on a small target, where the |
| // overlap is often quite high, and works well for tightly packed controls. |
| float hybridDistanceFunction(const IntPoint& touchHotspot, |
| const IntRect& touchRect, |
| const SubtargetGeometry& subtarget) { |
| IntRect rect = subtarget.node()->document().view()->contentsToRootFrame( |
| subtarget.boundingBox()); |
| |
| float radiusSquared = 0.25f * (touchRect.size().diagonalLengthSquared()); |
| float distanceToAdjustScore = |
| rect.distanceSquaredToPoint(touchHotspot) / radiusSquared; |
| |
| int maxOverlapWidth = std::min(touchRect.width(), rect.width()); |
| int maxOverlapHeight = std::min(touchRect.height(), rect.height()); |
| float maxOverlapArea = std::max(maxOverlapWidth * maxOverlapHeight, 1); |
| rect.intersect(touchRect); |
| float intersectArea = rect.size().area(); |
| float intersectionScore = 1 - intersectArea / maxOverlapArea; |
| |
| float hybridScore = intersectionScore + distanceToAdjustScore; |
| |
| return hybridScore; |
| } |
| |
| FloatPoint contentsToRootFrame(FrameView* view, FloatPoint pt) { |
| int x = static_cast<int>(pt.x() + 0.5f); |
| int y = static_cast<int>(pt.y() + 0.5f); |
| IntPoint adjusted = view->contentsToRootFrame(IntPoint(x, y)); |
| return FloatPoint(adjusted.x(), adjusted.y()); |
| } |
| |
| // Adjusts 'point' to the nearest point inside rect, and leaves it unchanged if |
| // already inside. |
| void adjustPointToRect(FloatPoint& point, const FloatRect& rect) { |
| if (point.x() < rect.x()) |
| point.setX(rect.x()); |
| else if (point.x() > rect.maxX()) |
| point.setX(rect.maxX()); |
| |
| if (point.y() < rect.y()) |
| point.setY(rect.y()); |
| else if (point.y() > rect.maxY()) |
| point.setY(rect.maxY()); |
| } |
| |
| bool snapTo(const SubtargetGeometry& geom, |
| const IntPoint& touchPoint, |
| const IntRect& touchArea, |
| IntPoint& adjustedPoint) { |
| FrameView* view = geom.node()->document().view(); |
| FloatQuad quad = geom.quad(); |
| |
| if (quad.isRectilinear()) { |
| IntRect bounds = view->contentsToRootFrame(geom.boundingBox()); |
| if (bounds.contains(touchPoint)) { |
| adjustedPoint = touchPoint; |
| return true; |
| } |
| if (bounds.intersects(touchArea)) { |
| bounds.intersect(touchArea); |
| adjustedPoint = bounds.center(); |
| return true; |
| } |
| return false; |
| } |
| |
| // The following code tries to adjust the point to place inside a both the |
| // touchArea and the non-rectilinear quad. |
| // FIXME: This will return the point inside the touch area that is the closest |
| // to the quad center, but does not guarantee that the point will be inside |
| // the quad. Corner-cases exist where the quad will intersect but this will |
| // fail to adjust the point to somewhere in the intersection. |
| |
| FloatPoint p1 = contentsToRootFrame(view, quad.p1()); |
| FloatPoint p2 = contentsToRootFrame(view, quad.p2()); |
| FloatPoint p3 = contentsToRootFrame(view, quad.p3()); |
| FloatPoint p4 = contentsToRootFrame(view, quad.p4()); |
| quad = FloatQuad(p1, p2, p3, p4); |
| |
| if (quad.containsPoint(touchPoint)) { |
| adjustedPoint = touchPoint; |
| return true; |
| } |
| |
| // Pull point towards the center of the element. |
| FloatPoint center = quad.center(); |
| |
| adjustPointToRect(center, touchArea); |
| adjustedPoint = roundedIntPoint(center); |
| |
| return quad.containsPoint(adjustedPoint); |
| } |
| |
| // A generic function for finding the target node with the lowest distance |
| // metric. A distance metric here is the result of a distance-like function, |
| // that computes how well the touch hits the node. Distance functions could for |
| // instance be distance squared or area of intersection. |
| bool findNodeWithLowestDistanceMetric(Node*& targetNode, |
| IntPoint& targetPoint, |
| IntRect& targetArea, |
| const IntPoint& touchHotspot, |
| const IntRect& touchArea, |
| SubtargetGeometryList& subtargets, |
| DistanceFunction distanceFunction) { |
| targetNode = nullptr; |
| float bestDistanceMetric = std::numeric_limits<float>::infinity(); |
| SubtargetGeometryList::const_iterator it = subtargets.begin(); |
| const SubtargetGeometryList::const_iterator end = subtargets.end(); |
| IntPoint adjustedPoint; |
| |
| for (; it != end; ++it) { |
| Node* node = it->node(); |
| float distanceMetric = distanceFunction(touchHotspot, touchArea, *it); |
| if (distanceMetric < bestDistanceMetric) { |
| if (snapTo(*it, touchHotspot, touchArea, adjustedPoint)) { |
| targetPoint = adjustedPoint; |
| targetArea = it->boundingBox(); |
| targetNode = node; |
| bestDistanceMetric = distanceMetric; |
| } |
| } else if (distanceMetric - bestDistanceMetric < zeroTolerance) { |
| if (snapTo(*it, touchHotspot, touchArea, adjustedPoint)) { |
| if (node->isDescendantOf(targetNode)) { |
| // Try to always return the inner-most element. |
| targetPoint = adjustedPoint; |
| targetNode = node; |
| targetArea = it->boundingBox(); |
| } |
| } |
| } |
| } |
| |
| // As for HitTestResult.innerNode, we skip over pseudo elements. |
| if (targetNode && targetNode->isPseudoElement()) |
| targetNode = targetNode->parentOrShadowHostNode(); |
| |
| if (targetNode) |
| targetArea = targetNode->document().view()->contentsToRootFrame(targetArea); |
| |
| return (targetNode); |
| } |
| |
| } // namespace TouchAdjustment |
| |
| bool findBestClickableCandidate(Node*& targetNode, |
| IntPoint& targetPoint, |
| const IntPoint& touchHotspot, |
| const IntRect& touchArea, |
| const HeapVector<Member<Node>>& nodes) { |
| IntRect targetArea; |
| TouchAdjustment::SubtargetGeometryList subtargets; |
| TouchAdjustment::compileSubtargetList( |
| nodes, subtargets, TouchAdjustment::nodeRespondsToTapGesture, |
| TouchAdjustment::appendBasicSubtargetsForNode); |
| return TouchAdjustment::findNodeWithLowestDistanceMetric( |
| targetNode, targetPoint, targetArea, touchHotspot, touchArea, subtargets, |
| TouchAdjustment::hybridDistanceFunction); |
| } |
| |
| bool findBestContextMenuCandidate(Node*& targetNode, |
| IntPoint& targetPoint, |
| const IntPoint& touchHotspot, |
| const IntRect& touchArea, |
| const HeapVector<Member<Node>>& nodes) { |
| IntRect targetArea; |
| TouchAdjustment::SubtargetGeometryList subtargets; |
| TouchAdjustment::compileSubtargetList( |
| nodes, subtargets, TouchAdjustment::providesContextMenuItems, |
| TouchAdjustment::appendContextSubtargetsForNode); |
| return TouchAdjustment::findNodeWithLowestDistanceMetric( |
| targetNode, targetPoint, targetArea, touchHotspot, touchArea, subtargets, |
| TouchAdjustment::hybridDistanceFunction); |
| } |
| |
| bool findBestZoomableArea(Node*& targetNode, |
| IntRect& targetArea, |
| const IntPoint& touchHotspot, |
| const IntRect& touchArea, |
| const HeapVector<Member<Node>>& nodes) { |
| IntPoint targetPoint; |
| TouchAdjustment::SubtargetGeometryList subtargets; |
| TouchAdjustment::compileZoomableSubtargets(nodes, subtargets); |
| return TouchAdjustment::findNodeWithLowestDistanceMetric( |
| targetNode, targetPoint, targetArea, touchHotspot, touchArea, subtargets, |
| TouchAdjustment::zoomableIntersectionQuotient); |
| } |
| |
| } // namespace blink |