This source file includes following definitions.
- m_currentElement
- isEmpty
- next
- nextInternal
- initialize
- selectorMatches
- matches
- queryAll
- queryFirst
- collectElementsByClassName
- collectElementsByTagName
- canUseFastQuery
- ancestorHasClassName
- findTraverseRootsAndExecute
- executeForTraverseRoot
- executeForTraverseRoots
- selectorListMatches
- executeSlow
- authorShadowRootOf
- firstWithinTraversingShadowTree
- nextTraversingShadowTree
- executeSlowTraversingShadowTree
- selectorForIdLookup
- execute
- matches
- queryAll
- queryFirst
- add
- invalidate
#include "config.h"
#include "core/dom/SelectorQuery.h"
#include "bindings/v8/ExceptionState.h"
#include "core/css/parser/BisonCSSParser.h"
#include "core/css/SelectorChecker.h"
#include "core/css/SiblingTraversalStrategies.h"
#include "core/dom/Document.h"
#include "core/dom/ElementTraversal.h"
#include "core/dom/Node.h"
#include "core/dom/StaticNodeList.h"
#include "core/dom/shadow/ElementShadow.h"
#include "core/dom/shadow/ShadowRoot.h"
namespace WebCore {
struct SingleElementSelectorQueryTrait {
typedef Element* OutputType;
static const bool shouldOnlyMatchFirstElement = true;
ALWAYS_INLINE static void appendElement(OutputType& output, Element& element)
{
ASSERT(!output);
output = &element;
}
};
struct AllElementsSelectorQueryTrait {
typedef Vector<RefPtr<Node> > OutputType;
static const bool shouldOnlyMatchFirstElement = false;
ALWAYS_INLINE static void appendElement(OutputType& output, Node& element)
{
output.append(RefPtr<Node>(element));
}
};
enum ClassElementListBehavior { AllElements, OnlyRoots };
template <ClassElementListBehavior onlyRoots>
class ClassElementList {
public:
ClassElementList(ContainerNode& rootNode, const AtomicString& className)
: m_className(className)
, m_rootNode(rootNode)
, m_currentElement(nextInternal(ElementTraversal::firstWithin(rootNode))) { }
bool isEmpty() const { return !m_currentElement; }
Element* next()
{
Element* current = m_currentElement;
ASSERT(current);
if (onlyRoots)
m_currentElement = nextInternal(ElementTraversal::nextSkippingChildren(*m_currentElement, &m_rootNode));
else
m_currentElement = nextInternal(ElementTraversal::next(*m_currentElement, &m_rootNode));
return current;
}
private:
Element* nextInternal(Element* element)
{
for (; element; element = ElementTraversal::next(*element, &m_rootNode)) {
if (element->hasClass() && element->classNames().contains(m_className))
return element;
}
return 0;
}
const AtomicString& m_className;
ContainerNode& m_rootNode;
Element* m_currentElement;
};
void SelectorDataList::initialize(const CSSSelectorList& selectorList)
{
ASSERT(m_selectors.isEmpty());
unsigned selectorCount = 0;
for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector))
selectorCount++;
m_crossesTreeBoundary = false;
m_selectors.reserveInitialCapacity(selectorCount);
unsigned index = 0;
for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(*selector), ++index) {
m_selectors.uncheckedAppend(selector);
m_crossesTreeBoundary |= selectorList.selectorCrossesTreeScopes(index);
}
}
inline bool SelectorDataList::selectorMatches(const CSSSelector& selector, Element& element, const ContainerNode& rootNode) const
{
SelectorChecker selectorChecker(element.document(), SelectorChecker::QueryingRules);
SelectorChecker::SelectorCheckingContext selectorCheckingContext(selector, &element, SelectorChecker::VisitedMatchDisabled);
selectorCheckingContext.behaviorAtBoundary = SelectorChecker::StaysWithinTreeScope;
selectorCheckingContext.scope = !rootNode.isDocumentNode() ? &rootNode : 0;
return selectorChecker.match(selectorCheckingContext, DOMSiblingTraversalStrategy()) == SelectorChecker::SelectorMatches;
}
bool SelectorDataList::matches(Element& targetElement) const
{
unsigned selectorCount = m_selectors.size();
for (unsigned i = 0; i < selectorCount; ++i) {
if (selectorMatches(*m_selectors[i], targetElement, targetElement))
return true;
}
return false;
}
PassRefPtr<NodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const
{
Vector<RefPtr<Node> > result;
execute<AllElementsSelectorQueryTrait>(rootNode, result);
return StaticNodeList::adopt(result);
}
PassRefPtr<Element> SelectorDataList::queryFirst(ContainerNode& rootNode) const
{
Element* matchedElement = 0;
execute<SingleElementSelectorQueryTrait>(rootNode, matchedElement);
return matchedElement;
}
template <typename SelectorQueryTrait>
void SelectorDataList::collectElementsByClassName(ContainerNode& rootNode, const AtomicString& className, typename SelectorQueryTrait::OutputType& output) const
{
for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
if (element->hasClass() && element->classNames().contains(className)) {
SelectorQueryTrait::appendElement(output, *element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
template <typename SelectorQueryTrait>
void SelectorDataList::collectElementsByTagName(ContainerNode& rootNode, const QualifiedName& tagName, typename SelectorQueryTrait::OutputType& output) const
{
for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
if (SelectorChecker::tagMatches(*element, tagName)) {
SelectorQueryTrait::appendElement(output, *element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
inline bool SelectorDataList::canUseFastQuery(const ContainerNode& rootNode) const
{
return m_selectors.size() == 1 && !m_crossesTreeBoundary && rootNode.inDocument() && !rootNode.document().inQuirksMode();
}
inline bool ancestorHasClassName(ContainerNode& rootNode, const AtomicString& className)
{
if (!rootNode.isElementNode())
return false;
for (Element* element = &toElement(rootNode); element; element = element->parentElement()) {
if (element->hasClass() && element->classNames().contains(className))
return true;
}
return false;
}
template <typename SelectorQueryTrait>
void SelectorDataList::findTraverseRootsAndExecute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
ASSERT(m_selectors.size() == 1);
bool isRightmostSelector = true;
bool startFromParent = false;
for (const CSSSelector* selector = m_selectors[0]; selector; selector = selector->tagHistory()) {
if (selector->m_match == CSSSelector::Id && !rootNode.document().containsMultipleElementsWithId(selector->value())) {
Element* element = rootNode.treeScope().getElementById(selector->value());
ContainerNode* adjustedNode = &rootNode;
if (element && (isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
adjustedNode = element;
else if (!element || isRightmostSelector)
adjustedNode = 0;
if (isRightmostSelector) {
executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], adjustedNode, MatchesTraverseRoots, rootNode, output);
return;
}
if (startFromParent && adjustedNode)
adjustedNode = adjustedNode->parentNode();
executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], adjustedNode, DoesNotMatchTraverseRoots, rootNode, output);
return;
}
if (!SelectorQueryTrait::shouldOnlyMatchFirstElement && !startFromParent && selector->m_match == CSSSelector::Class) {
if (isRightmostSelector) {
ClassElementList<AllElements> traverseRoots(rootNode, selector->value());
executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, MatchesTraverseRoots, rootNode, output);
return;
}
if (ancestorHasClassName(rootNode, selector->value())) {
executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
return;
}
ClassElementList<OnlyRoots> traverseRoots(rootNode, selector->value());
executeForTraverseRoots<SelectorQueryTrait>(*m_selectors[0], traverseRoots, DoesNotMatchTraverseRoots, rootNode, output);
return;
}
if (selector->relation() == CSSSelector::SubSelector)
continue;
isRightmostSelector = false;
if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
startFromParent = true;
else
startFromParent = false;
}
executeForTraverseRoot<SelectorQueryTrait>(*m_selectors[0], &rootNode, DoesNotMatchTraverseRoots, rootNode, output);
}
template <typename SelectorQueryTrait>
void SelectorDataList::executeForTraverseRoot(const CSSSelector& selector, ContainerNode* traverseRoot, MatchTraverseRootState matchTraverseRoot, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
if (!traverseRoot)
return;
if (matchTraverseRoot) {
if (selectorMatches(selector, toElement(*traverseRoot), rootNode))
SelectorQueryTrait::appendElement(output, toElement(*traverseRoot));
return;
}
for (Element* element = ElementTraversal::firstWithin(*traverseRoot); element; element = ElementTraversal::next(*element, traverseRoot)) {
if (selectorMatches(selector, *element, rootNode)) {
SelectorQueryTrait::appendElement(output, *element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
template <typename SelectorQueryTrait, typename SimpleElementListType>
void SelectorDataList::executeForTraverseRoots(const CSSSelector& selector, SimpleElementListType& traverseRoots, MatchTraverseRootState matchTraverseRoots, ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
if (traverseRoots.isEmpty())
return;
if (matchTraverseRoots) {
while (!traverseRoots.isEmpty()) {
Element& element = *traverseRoots.next();
if (selectorMatches(selector, element, rootNode)) {
SelectorQueryTrait::appendElement(output, element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
return;
}
while (!traverseRoots.isEmpty()) {
Element& traverseRoot = *traverseRoots.next();
for (Element* element = ElementTraversal::firstWithin(traverseRoot); element; element = ElementTraversal::next(*element, &traverseRoot)) {
if (selectorMatches(selector, *element, rootNode)) {
SelectorQueryTrait::appendElement(output, *element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
}
template <typename SelectorQueryTrait>
bool SelectorDataList::selectorListMatches(ContainerNode& rootNode, Element& element, typename SelectorQueryTrait::OutputType& output) const
{
for (unsigned i = 0; i < m_selectors.size(); ++i) {
if (selectorMatches(*m_selectors[i], element, rootNode)) {
SelectorQueryTrait::appendElement(output, element);
return true;
}
}
return false;
}
template <typename SelectorQueryTrait>
void SelectorDataList::executeSlow(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
for (Element* element = ElementTraversal::firstWithin(rootNode); element; element = ElementTraversal::next(*element, &rootNode)) {
if (selectorListMatches<SelectorQueryTrait>(rootNode, *element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
static ShadowRoot* authorShadowRootOf(const ContainerNode& node)
{
if (!node.isElementNode() || !isShadowHost(&node))
return 0;
ElementShadow* shadow = toElement(node).shadow();
ASSERT(shadow);
for (ShadowRoot* shadowRoot = shadow->oldestShadowRoot(); shadowRoot; shadowRoot = shadowRoot->youngerShadowRoot()) {
if (shadowRoot->type() == ShadowRoot::AuthorShadowRoot)
return shadowRoot;
}
return 0;
}
static ContainerNode* firstWithinTraversingShadowTree(const ContainerNode& rootNode)
{
if (ShadowRoot* shadowRoot = authorShadowRootOf(rootNode))
return shadowRoot;
return ElementTraversal::firstWithin(rootNode);
}
static ContainerNode* nextTraversingShadowTree(const ContainerNode& node, const ContainerNode* rootNode)
{
if (ShadowRoot* shadowRoot = authorShadowRootOf(node))
return shadowRoot;
if (Element* next = ElementTraversal::next(node, rootNode))
return next;
if (!node.isInShadowTree())
return 0;
ShadowRoot* shadowRoot = node.containingShadowRoot();
if (shadowRoot == rootNode)
return 0;
if (ShadowRoot* youngerShadowRoot = shadowRoot->youngerShadowRoot()) {
ASSERT(youngerShadowRoot->type() == ShadowRoot::AuthorShadowRoot);
return youngerShadowRoot;
}
Element* shadowHost = shadowRoot->host();
return ElementTraversal::next(*shadowHost, rootNode);
}
template <typename SelectorQueryTrait>
void SelectorDataList::executeSlowTraversingShadowTree(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
for (ContainerNode* node = firstWithinTraversingShadowTree(rootNode); node; node = nextTraversingShadowTree(*node, &rootNode)) {
if (!node->isElementNode())
continue;
Element* element = toElement(node);
if (selectorListMatches<SelectorQueryTrait>(rootNode, *element, output) && SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
const CSSSelector* SelectorDataList::selectorForIdLookup(const CSSSelector& firstSelector) const
{
for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
if (selector->m_match == CSSSelector::Id)
return selector;
if (selector->relation() != CSSSelector::SubSelector)
break;
}
return 0;
}
template <typename SelectorQueryTrait>
void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
if (!canUseFastQuery(rootNode)) {
if (m_crossesTreeBoundary)
executeSlowTraversingShadowTree<SelectorQueryTrait>(rootNode, output);
else
executeSlow<SelectorQueryTrait>(rootNode, output);
return;
}
ASSERT(m_selectors.size() == 1);
const CSSSelector& selector = *m_selectors[0];
const CSSSelector& firstSelector = selector;
if (const CSSSelector* idSelector = selectorForIdLookup(firstSelector)) {
const AtomicString& idToMatch = idSelector->value();
if (rootNode.treeScope().containsMultipleElementsWithId(idToMatch)) {
const Vector<Element*>& elements = rootNode.treeScope().getAllElementsById(idToMatch);
size_t count = elements.size();
for (size_t i = 0; i < count; ++i) {
Element& element = *elements[i];
if (!(isTreeScopeRoot(rootNode) || element.isDescendantOf(&rootNode)))
continue;
if (selectorMatches(selector, element, rootNode)) {
SelectorQueryTrait::appendElement(output, element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
return;
}
Element* element = rootNode.treeScope().getElementById(idToMatch);
if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
return;
if (selectorMatches(selector, *element, rootNode))
SelectorQueryTrait::appendElement(output, *element);
return;
}
if (!firstSelector.tagHistory()) {
switch (firstSelector.m_match) {
case CSSSelector::Class:
collectElementsByClassName<SelectorQueryTrait>(rootNode, firstSelector.value(), output);
return;
case CSSSelector::Tag:
collectElementsByTagName<SelectorQueryTrait>(rootNode, firstSelector.tagQName(), output);
return;
default:
break;
}
}
findTraverseRootsAndExecute<SelectorQueryTrait>(rootNode, output);
}
SelectorQuery::SelectorQuery(const CSSSelectorList& selectorList)
: m_selectorList(selectorList)
{
m_selectors.initialize(m_selectorList);
}
bool SelectorQuery::matches(Element& element) const
{
return m_selectors.matches(element);
}
PassRefPtr<NodeList> SelectorQuery::queryAll(ContainerNode& rootNode) const
{
return m_selectors.queryAll(rootNode);
}
PassRefPtr<Element> SelectorQuery::queryFirst(ContainerNode& rootNode) const
{
return m_selectors.queryFirst(rootNode);
}
SelectorQuery* SelectorQueryCache::add(const AtomicString& selectors, const Document& document, ExceptionState& exceptionState)
{
HashMap<AtomicString, OwnPtr<SelectorQuery> >::iterator it = m_entries.find(selectors);
if (it != m_entries.end())
return it->value.get();
BisonCSSParser parser(CSSParserContext(document, 0));
CSSSelectorList selectorList;
parser.parseSelector(selectors, selectorList);
if (!selectorList.first()) {
exceptionState.throwDOMException(SyntaxError, "'" + selectors + "' is not a valid selector.");
return 0;
}
if (selectorList.selectorsNeedNamespaceResolution()) {
exceptionState.throwDOMException(NamespaceError, "'" + selectors + "' contains namespaces, which are not supported.");
return 0;
}
const unsigned maximumSelectorQueryCacheSize = 256;
if (m_entries.size() == maximumSelectorQueryCacheSize)
m_entries.remove(m_entries.begin());
OwnPtr<SelectorQuery> selectorQuery = adoptPtr(new SelectorQuery(selectorList));
SelectorQuery* rawSelectorQuery = selectorQuery.get();
m_entries.add(selectors, selectorQuery.release());
return rawSelectorQuery;
}
void SelectorQueryCache::invalidate()
{
m_entries.clear();
}
}