src/third_party/WebKit/Source/core/css/SelectorCheckerFastPath.cpp

   1 /*
   2  * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
   3  *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
   4  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
   5  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013 Apple Inc. All rights reserved.
   6  * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
   7  * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
   8  * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
   9  * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
  10  * Copyright (C) Research In Motion Limited 2011. All rights reserved.
  11  * Copyright (C) 2013 Google Inc. All rights reserved.
  12  *
  13  * This library is free software; you can redistribute it and/or
  14  * modify it under the terms of the GNU Library General Public
  15  * License as published by the Free Software Foundation; either
  16  * version 2 of the License, or (at your option) any later version.
  17  *
  18  * This library is distributed in the hope that it will be useful,
  19  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  20  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  21  * Library General Public License for more details.
  22  *
  23  * You should have received a copy of the GNU Library General Public License
  24  * along with this library; see the file COPYING.LIB.  If not, write to
  25  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  26  * Boston, MA 02110-1301, USA.
  27  */
  28
  29 #include "config.h"
  30 #include "core/css/SelectorCheckerFastPath.h"
  31
  32 #include "HTMLNames.h"
  33 #include "core/dom/Element.h"
  34 #include "core/html/HTMLDocument.h"
  35
  36 namespace WebCore {
  37
  38 using namespace HTMLNames;
  39
  40 namespace {
  41
  42 template <bool checkValue(const Element&, const CSSSelector&)>
  43 inline bool fastCheckSingleSelector(const CSSSelector*& selector, const Element*& element, const CSSSelector*& topChildOrSubselector, const Element*& topChildOrSubselectorMatchElement)
  44 {
  45     for (; element; element = element->parentElement()) {
  46         if (checkValue(*element, *selector)) {
  47             if (selector->relation() == CSSSelector::Descendant)
  48                 topChildOrSubselector = 0;
  49             else if (!topChildOrSubselector) {
  50                 ASSERT(selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector);
  51                 topChildOrSubselector = selector;
  52                 topChildOrSubselectorMatchElement = element;
  53             }
  54             if (selector->relation() != CSSSelector::SubSelector)
  55                 element = element->parentElement();
  56             selector = selector->tagHistory();
  57             return true;
  58         }
  59         if (topChildOrSubselector) {
  60             // Child or subselector check failed.
  61             // If the match element is null, topChildOrSubselector was also the very topmost selector and had to match
  62             // the original element we were checking.
  63             if (!topChildOrSubselectorMatchElement)
  64                 return false;
  65             // There may be other matches down the ancestor chain.
  66             // Rewind to the topmost child or subselector and the element it matched, continue checking ancestors.
  67             selector = topChildOrSubselector;
  68             element = topChildOrSubselectorMatchElement->parentElement();
  69             topChildOrSubselector = 0;
  70             return true;
  71         }
  72     }
  73     return false;
  74 }
  75
  76 inline bool checkClassValue(const Element& element, const CSSSelector& selector)
  77 {
  78     return element.hasClass() && element.classNames().contains(selector.value());
  79 }
  80
  81 inline bool checkIDValue(const Element& element, const CSSSelector& selector)
  82 {
  83     return element.hasID() && element.idForStyleResolution() == selector.value();
  84 }
  85
  86 inline bool checkExactAttributeValue(const Element& element, const CSSSelector& selector)
  87 {
  88     return SelectorChecker::checkExactAttribute(element, selector.attribute(), selector.value().impl());
  89 }
  90
  91 inline bool checkTagValue(const Element& element, const CSSSelector& selector)
  92 {
  93     return SelectorChecker::tagMatches(element, selector.tagQName());
  94 }
  95
  96 }
  97
  98 SelectorCheckerFastPath::SelectorCheckerFastPath(const CSSSelector& selector, const Element& element)
  99     : m_selector(selector)
 100     , m_element(element)
 101 {
 102 }
 103
 104 bool SelectorCheckerFastPath::matchesRightmostSelector(SelectorChecker::VisitedMatchType visitedMatchType) const
 105 {
 106     ASSERT(SelectorCheckerFastPath::canUse(m_selector));
 107
 108     switch (m_selector.m_match) {
 109     case CSSSelector::Tag:
 110         return checkTagValue(m_element, m_selector);
 111     case CSSSelector::Class:
 112         return checkClassValue(m_element, m_selector);
 113     case CSSSelector::Id:
 114         return checkIDValue(m_element, m_selector);
 115     case CSSSelector::Exact:
 116     case CSSSelector::Set:
 117         return checkExactAttributeValue(m_element, m_selector);
 118     case CSSSelector::PseudoClass:
 119         return commonPseudoClassSelectorMatches(visitedMatchType);
 120     default:
 121         ASSERT_NOT_REACHED();
 122     }
 123     return false;
 124 }
 125
 126 bool SelectorCheckerFastPath::matches() const
 127 {
 128     ASSERT(matchesRightmostSelector(SelectorChecker::VisitedMatchEnabled));
 129     const CSSSelector* selector = &m_selector;
 130     const Element* element = &m_element;
 131
 132     const CSSSelector* topChildOrSubselector = 0;
 133     const Element* topChildOrSubselectorMatchElement = 0;
 134     if (selector->relation() == CSSSelector::Child || selector->relation() == CSSSelector::SubSelector)
 135         topChildOrSubselector = selector;
 136
 137     if (selector->relation() != CSSSelector::SubSelector)
 138         element = element->parentElement();
 139
 140     selector = selector->tagHistory();
 141
 142     // We know this compound selector has descendant, child and subselector combinators only and all components are simple.
 143     while (selector) {
 144         switch (selector->m_match) {
 145         case CSSSelector::Class:
 146             if (!fastCheckSingleSelector<checkClassValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
 147                 return false;
 148             break;
 149         case CSSSelector::Id:
 150             if (!fastCheckSingleSelector<checkIDValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
 151                 return false;
 152             break;
 153         case CSSSelector::Tag:
 154             if (!fastCheckSingleSelector<checkTagValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
 155                 return false;
 156             break;
 157         case CSSSelector::Set:
 158         case CSSSelector::Exact:
 159             if (!fastCheckSingleSelector<checkExactAttributeValue>(selector, element, topChildOrSubselector, topChildOrSubselectorMatchElement))
 160                 return false;
 161             break;
 162         default:
 163             ASSERT_NOT_REACHED();
 164         }
 165     }
 166     return true;
 167 }
 168
 169 static inline bool isFastCheckableRelation(CSSSelector::Relation relation)
 170 {
 171     return relation == CSSSelector::Descendant || relation == CSSSelector::Child || relation == CSSSelector::SubSelector;
 172 }
 173
 174 static inline bool isFastCheckableMatch(const CSSSelector& selector)
 175 {
 176     if (selector.m_match == CSSSelector::Set) {
 177         // Style attribute is generated lazily but the fast path doesn't trigger it.
 178         // Disallow them here rather than making the fast path more branchy.
 179         return selector.attribute() != styleAttr;
 180     }
 181     if (selector.m_match == CSSSelector::Exact)
 182         return selector.attribute() != styleAttr && HTMLDocument::isCaseSensitiveAttribute(selector.attribute());
 183     return selector.m_match == CSSSelector::Tag || selector.m_match == CSSSelector::Id || selector.m_match == CSSSelector::Class;
 184 }
 185
 186 static inline bool isFastCheckableRightmostSelector(const CSSSelector& selector)
 187 {
 188     if (!isFastCheckableRelation(selector.relation()))
 189         return false;
 190     return isFastCheckableMatch(selector) || SelectorChecker::isCommonPseudoClassSelector(selector);
 191 }
 192
 193 bool SelectorCheckerFastPath::canUse(const CSSSelector& selector)
 194 {
 195     if (!isFastCheckableRightmostSelector(selector))
 196         return false;
 197     for (const CSSSelector* current = selector.tagHistory(); current; current = current->tagHistory()) {
 198         if (!isFastCheckableRelation(current->relation()))
 199             return false;
 200         if (!isFastCheckableMatch(*current))
 201             return false;
 202     }
 203     return true;
 204 }
 205
 206 bool SelectorCheckerFastPath::commonPseudoClassSelectorMatches(SelectorChecker::VisitedMatchType visitedMatchType) const
 207 {
 208     ASSERT(SelectorChecker::isCommonPseudoClassSelector(m_selector));
 209     switch (m_selector.pseudoType()) {
 210     case CSSSelector::PseudoLink:
 211     case CSSSelector::PseudoAnyLink:
 212         return m_element.isLink();
 213     case CSSSelector::PseudoVisited:
 214         return m_element.isLink() && visitedMatchType == SelectorChecker::VisitedMatchEnabled;
 215     case CSSSelector::PseudoFocus:
 216         return SelectorChecker::matchesFocusPseudoClass(m_element);
 217     default:
 218         ASSERT_NOT_REACHED();
 219     }
 220     return true;
 221 }
 222
 223
 224 }