WIP: <canvas> hit regions

Source/core/html/canvas/CanvasHitRegion.cpp

Index: Source/core/html/canvas/CanvasHitRegion.cpp
diff --git a/Source/core/html/canvas/CanvasHitRegion.cpp b/Source/core/html/canvas/CanvasHitRegion.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..0841a4128d5763ec27b8f0133e9ff27737f57196
--- /dev/null
+++ b/Source/core/html/canvas/CanvasHitRegion.cpp
@@ -0,0 +1,378 @@
+// Copyright 2014 The Chromium Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+#include "config.h"
+#include "core/html/canvas/CanvasHitRegion.h"
+
+#include "bindings/v8/Dictionary.h"
+#include "bindings/v8/ExceptionState.h"
+#include "core/dom/Element.h"
+#include "core/dom/ElementTraversal.h"
+#include "core/html/HTMLImageElement.h"
+#include "core/html/HTMLInputElement.h"
+#include "core/html/HTMLSelectElement.h"
+#include "core/html/canvas/Path2D.h"
+
+namespace WebCore {
+
+// FIXME: De-dupe.
+static WindRule parseWinding(const String& windingRuleString, WindRule defaultValue = RULE_EVENODD)
+{
+    if (windingRuleString == "nonzero")
+        return RULE_NONZERO;
+    if (windingRuleString == "evenodd")
+        return RULE_EVENODD;
+
+    return defaultValue;
+}
+
+DecodedHitRegionOptions::DecodedHitRegionOptions()
+    : hasPath(false)
+    , fillRule(RULE_NONZERO)
+{
+}
+
+DecodedHitRegionOptions::DecodedHitRegionOptions(const Dictionary& options)
+    : hasPath(false)
+    , fillRule(RULE_NONZERO)
+{
+    RefPtr<Path2D> pathFromDictionary;
+    if (options.get("path", pathFromDictionary) && pathFromDictionary) {
+        path = pathFromDictionary->path();
+        hasPath = true;
+    }
+    String windRuleString;
+    if (options.get("fillRule", windRuleString))
+        fillRule = parseWinding(windRuleString, RULE_NONZERO);
+    if (options.get("id", id) && id.isEmpty())
+        id = String();
+    if (options.getWithUndefinedOrNullCheck("parentID", parentId) && parentId.isEmpty())
+        parentId = String();
+    options.get("cursor", cursor);
+    options.get("control", control);
+    if (options.getWithUndefinedOrNullCheck("label", label) && label.isEmpty())
+        label = String();
+    if (options.getWithUndefinedOrNullCheck("role", role) && role.isEmpty())
+        role = String();
+}
+
+void DecodedHitRegionOptions::resolvePath(const Path& currentPath, const AffineTransform& currentTransform)
+{
+    if (!hasPath)
+        path = currentPath;
+    path.transform(currentTransform);
+}
+
+void DecodedHitRegionOptions::resolveIds(const CanvasHitRegionManager* hitRegionManager)
+{
+    parentHitRegion = !parentId.isEmpty() ? hitRegionManager->getHitRegionById(parentId) : 0;
+    previousHitRegion = !id.isEmpty() ? hitRegionManager->getHitRegionById(id) : 0;
+}
+
+static bool isSupportedInteractiveFallbackElement(Element& element)
+{
+    // "An element is a supported interactive canvas fallback element if it is one of the following:"
+
+    // "an 'a' element that represents a hyperlink and that does not have any img descendants"
+    if (element.hasTagName(HTMLNames::aTag))
+        return !Traversal<HTMLImageElement>::firstWithin(element);
+
+    // "a button element"
+    if (element.hasTagName(HTMLNames::buttonTag))
+        return true;
+
+    if (isHTMLInputElement(element)) {
+        // "an input element whose type attribute is in one of the Checkbox or Radio Button states"
+        const HTMLInputElement& inputElement = toHTMLInputElement(element);
+        if (inputElement.isCheckbox() || inputElement.isRadioButton())
+            return true;
+
+        // "an input element that is a button but its type attribute is not in the Image Button state"
+        if (inputElement.isTextButton() && !inputElement.isImageButton())
+            return true;
+    }
+
+    // "a select element with a multiple attribute or a display size greater than 1"
+    if (isHTMLSelectElement(element)) {
+        const HTMLSelectElement& selectElement = toHTMLSelectElement(element);
+        if (selectElement.multiple() || selectElement.size() > 1)
+            return true;
+    }
+
+    // "an option element that is in a list of options of a select element with
+    // a multiple attribute or a display size greater than 1"
+    // FIXME: Only direct descendant?
+    if (isHTMLOptionElement(element) && element.parentNode() && isHTMLSelectElement(*element.parentNode())) {
+        const HTMLSelectElement& selectElement = toHTMLSelectElement(*element.parentNode());
+        if (selectElement.multiple() || selectElement.size() > 1)
+            return true;
+    }
+
+    // "a sorting interface th element"
+    // Note: This seems redundant with the last condition.
+    if (element.hasTagName(HTMLNames::thTag) && element.fastHasAttribute(HTMLNames::sortableAttr))
+        return true;
+
+    // "an element that would not be interactive content except for having the
+    // tabindex attribute specified"
+    // FIXME: Does not test the "interactive content" part.
+    if (element.fastHasAttribute(HTMLNames::tabindexAttr))
+        return true;
+
+    // "a non-interactive table, caption, thead, tbody, tfoot, tr, td, or th element"
+    if (element.hasTagName(HTMLNames::tableTag)
+        || element.hasTagName(HTMLNames::captionTag)
+        || element.hasTagName(HTMLNames::theadTag)
+        || element.hasTagName(HTMLNames::tbodyTag)
+        || element.hasTagName(HTMLNames::tfootTag)
+        || element.hasTagName(HTMLNames::trTag)
+        || element.hasTagName(HTMLNames::tdTag)
+        || element.hasTagName(HTMLNames::thTag))
+        return true;
+
+    return false;
+}
+
+static bool isValidCSSCursor(const String& cursor)
+{
+    // FIXME: Implement.
+    return false;
+}
+
+static bool isValidCursorValue(const String& cursor)
+{
+    return cursor == "inherit" || isValidCSSCursor(cursor);
+}
+
+static bool hasValidAriaRoles(const String& roleList)
+{
+    // FIXME: Implement.
+    return false;
+}
+
+bool DecodedHitRegionOptions::validate(ExceptionState& exceptionState) const
+{
+    // 11. "If any of the following conditions are met, throw a NotSupportedError exception and abort these steps."
+
+    // "The arguments object's control and label members are both non-null."
+    if (control && !label.isNull())
+        exceptionState.throwDOMException(NotSupportedError, "cannot specify both a control and a label");
+
+    // "The arguments object's control and role members are both non-null."
+    if (control && !role.isNull())
+        exceptionState.throwDOMException(NotSupportedError, "cannot specify both a control and a role");
+
+    // "The arguments object's role member's value is the empty string, and the
+    // label member's value is either null or the empty string."
+    if (role.isEmpty() && (label.isNull() || label.isEmpty()))
+        exceptionState.throwDOMException(NotSupportedError, "both role and label cannot be empty");
+
+    // FIXME: Include clip.
+    // "The specified pixels has no pixels." (s/pixels/area/)
+    if (path.isEmpty() || path.boundingRect().isEmpty())
+        exceptionState.throwDOMException(NotSupportedError, "the specified region cannot be empty");
+
+    // "The arguments object's control member is neither null nor a supported
+    // interactive canvas fallback element."
+    if (control && !isSupportedInteractiveFallbackElement(*control))
+        exceptionState.throwDOMException(NotSupportedError, "the specified control is not supported");
+
+    // "The parent region is not null but has a control."
+    if (parentHitRegion && parentHitRegion->control())
+        exceptionState.throwDOMException(NotSupportedError, "the specified parent hit-region is associated with a control");
+
+    // "The previous region for this ID is the same hit region as the parent region."
+    if (previousHitRegion && parentHitRegion && previousHitRegion == parentHitRegion)
+        exceptionState.throwDOMException(NotSupportedError, "the previous region is the same as the parent region");
+
+    // "The previous region for this ID is an ancestor region of the parent region."
+    if (previousHitRegion && parentHitRegion && previousHitRegion->isAncestorOf(parentHitRegion.get()))
+        exceptionState.throwDOMException(NotSupportedError, "the previous region is an ancestor of the paretn region");
+
+    // 12. "If the parent member is not null but parent region is null, then
+    // throw a NotFoundError exception and abort these steps."
+    if (!parentId.isNull() && !parentHitRegion)
+        exceptionState.throwDOMException(NotFoundError, "the specified parent region does not exist");
+
+    // 13. "If any of the following conditions are met, throw a SyntaxError exception and abort these steps."
+
+    // "The arguments object's cursor member is not null but is neither an
+    // ASCII case-insensitive match for the string "inherit", nor a valid CSS
+    // 'cursor' property value."
+    if (!cursor.isNull() && !isValidCursorValue(cursor))
+        exceptionState.throwDOMException(SyntaxError, "the cursor value (' + cursor + ') is not recognized");
+
+    // "The arguments object's role member is not null but its value is not an
+    // ordered set of unique space-separated tokens whose tokens are all
+    // case-sensitive matches for names of non-abstract WAI-ARIA roles."
+    if (!role.isNull() && !hasValidAriaRoles(role))
+        exceptionState.throwDOMException(SyntaxError, "the specified role(s) not valid ARIA role(s)");
+
+    return !exceptionState.hadException();
+}
+
+CanvasHitRegion::CanvasHitRegion(const DecodedHitRegionOptions& options)
+    : m_geometryInfo(GeometryInfo::create(options.path, options.fillRule, this))
+    , m_parent(options.parentHitRegion)
+    , m_control(options.control)
+    , m_id(options.id)
+    , m_cursor(options.cursor)
+    , m_label(options.label)
+    , m_ariaRole(options.role)
+{
+}
+
+CanvasHitRegion::~CanvasHitRegion()
+{
+    // Detach ourselves from our GeometryInfo, rendering it unable to produce a
+    // matching result on a hit test (but still occupying the area.)
+    m_geometryInfo->detachHitRegion();
+}
+
+CanvasHitRegion::GeometryInfo::GeometryInfo(const Path& path, WindRule fillRule, CanvasHitRegion* hitRegion)
+    : m_path(path)
+    , m_fillRule(fillRule)
+    , m_hitRegion(hitRegion)
+{
+}
+
+bool CanvasHitRegion::GeometryInfo::contains(const LayoutPoint& point) const
+{
+    if (!m_path.boundingRect().contains(point))
+        return false;
+    return m_path.contains(point, m_fillRule);
+}
+
+bool CanvasHitRegion::GeometryInfo::isEnclosed(const FloatRect& queryRect, const AffineTransform& queryTransform) const
+{
+    // Pessimistic 'enclosure' test.
+    FloatRect testRect;
+    if (queryTransform.isIdentity()) {
+        testRect = m_path.boundingRect();
+    } else {
+        Path inverseTransformedPath = m_path;
+        inverseTransformedPath.transform(queryTransform);
+        testRect = inverseTransformedPath.boundingRect();
+    }
+    return queryRect.contains(testRect);
+}
+
+bool CanvasHitRegion::isAncestorOf(const CanvasHitRegion* hitRegion) const
+{
+    if (!hitRegion || hitRegion == this)
+        return false;
+
+    while ((hitRegion = hitRegion->parent())) {
+        if (hitRegion == this)
+            return true;
+    }
+    return false;
+}
+
+void CanvasHitRegion::trace(Visitor* visitor)
+{
+#if ENABLE(OILPAN)
+    visitor->trace(m_parent);
+    visitor->trace(m_control);
+#endif
+}
+
+void CanvasHitRegionManager::add(PassRefPtrWillBeRawPtr<CanvasHitRegion> passHitRegion)
+{
+    RefPtrWillBeRawPtr<CanvasHitRegion> hitRegion = passHitRegion;
+    ASSERT(!m_hitRegions.contains(hitRegion));
+    m_hitRegions.add(hitRegion);
+    // Add to the id -> hit region map.
+    if (!hitRegion->id().isEmpty()) {
+        ASSERT(!m_hitRegionIdMap.contains(hitRegion->id()));
+        m_hitRegionIdMap.set(hitRegion->id(), hitRegion);
+    }
+    // Add the hit region to the spatial query structure.
+    m_hitRegionGeometry.append(hitRegion->geometryInfo());
+}
+
+void CanvasHitRegionManager::remove(CanvasHitRegion* hitRegion)
+{
+    if (!hitRegion)
+        return;
+
+    if (!hitRegion->id().isEmpty()) {
+        ASSERT(m_hitRegionIdMap.get(hitRegion->id()) == hitRegion);
+        m_hitRegionIdMap.remove(hitRegion->id());
+    }
+    ASSERT(m_hitRegions.contains(hitRegion));
+    m_hitRegions.remove(hitRegion);
+}
+
+void CanvasHitRegionManager::clear()
+{
+    m_hitRegionGeometry.clear();
+    m_hitRegionIdMap.clear();
+    m_hitRegions.clear();
+}
+
+void CanvasHitRegionManager::removeEnclosed(const FloatRect& rect, const AffineTransform& currentTransform)
+{
+    size_t geometryCount = m_hitRegionGeometry.size();
+    if (!geometryCount)
+        return;
+
+    FloatRect queryRect;
+    AffineTransform queryTransform;
+    if (currentTransform.preservesAxisAlignment()) {
+        queryRect = currentTransform.mapRect(rect);
+        // |queryTransform| is identity.
+    } else {
+        queryRect = rect;
+        queryTransform = currentTransform.inverse();
+    }
+
+    for (size_t i = geometryCount - 1; i >= 0; --i) {
+        CanvasHitRegion::GeometryInfo* geometryInfo = m_hitRegionGeometry[i].get();
+        if (!geometryInfo->isEnclosed(queryRect, queryTransform))
+            continue;
+
+        // Drop the associated hit region (if any.)
+        remove(geometryInfo->hitRegion());
+        // Drop the geometry info.
+        m_hitRegionGeometry.remove(i);
+    }
+
+    // If there's still hit regions referenced from the geometry list, then add
+    // a query rectangle that will consume any queries to that area.
+    if (!m_hitRegions.isEmpty()) {
+        Path exclusionPath;
+        exclusionPath.addRect(rect);
+        exclusionPath.transform(currentTransform);
+        m_hitRegionGeometry.append(CanvasHitRegion::GeometryInfo::create(exclusionPath, RULE_NONZERO, 0));
+    } else {
+        // Clear the geometry list, since it will only contain exclusions.
+        m_hitRegionGeometry.clear();
+    }
+}
+
+CanvasHitRegion* CanvasHitRegionManager::getHitRegionById(const String& id) const
+{
+    return m_hitRegionIdMap.get(id);
+}
+
+CanvasHitRegion* CanvasHitRegionManager::getHitRegionAtPoint(const LayoutPoint& point) const
+{
+    HitRegionGeometry::const_reverse_iterator itEnd = m_hitRegionGeometry.rend();
+    for (HitRegionGeometry::const_reverse_iterator it = m_hitRegionGeometry.rbegin(); it != itEnd; ++it) {
+        if ((*it)->contains(point))
+            return (*it)->hitRegion();
+    }
+    return 0;
+}
+
+void CanvasHitRegionManager::trace(Visitor* visitor)
+{
+#if ENABLE(OILPAN)
+    visitor->trace(m_hitRegions);
+    visitor->trace(m_hitRegionIdMap);
+#endif
+}
+
+} // namespace WebCore