#include "config.h"
#include "SelectorQuery.h"
#include "CSSParser.h"
#include "ElementDescendantIterator.h"
#include "SelectorChecker.h"
#include "SelectorCheckerFastPath.h"
#include "StaticNodeList.h"
#include "StyledElement.h"
namespace WebCore {
#if !ASSERT_DISABLED
static bool isSingleTagNameSelector(const CSSSelector& selector)
{
return selector.isLastInTagHistory() && selector.m_match == CSSSelector::Tag;
}
static bool isSingleClassNameSelector(const CSSSelector& selector)
{
return selector.isLastInTagHistory() && selector.m_match == CSSSelector::Class;
}
#endif
enum class IdMatchingType : uint8_t {
None,
Rightmost,
Filter
};
static IdMatchingType findIdMatchingType(const CSSSelector& firstSelector)
{
bool inRightmost = true;
for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
if (selector->m_match == CSSSelector::Id) {
if (inRightmost)
return IdMatchingType::Rightmost;
return IdMatchingType::Filter;
}
if (selector->relation() != CSSSelector::SubSelector)
inRightmost = false;
}
return IdMatchingType::None;
}
SelectorDataList::SelectorDataList(const CSSSelectorList& selectorList)
{
unsigned selectorCount = 0;
for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector))
selectorCount++;
m_selectors.reserveInitialCapacity(selectorCount);
for (const CSSSelector* selector = selectorList.first(); selector; selector = CSSSelectorList::next(selector))
m_selectors.uncheckedAppend(SelectorData(selector, SelectorCheckerFastPath::canUse(selector)));
if (selectorCount == 1) {
const CSSSelector& selector = *m_selectors.first().selector;
if (selector.isLastInTagHistory()) {
switch (selector.m_match) {
case CSSSelector::Tag:
m_matchType = TagNameMatch;
break;
case CSSSelector::Class:
m_matchType = ClassNameMatch;
break;
case CSSSelector::Id:
m_matchType = RightMostWithIdMatch;
break;
default:
m_matchType = CompilableSingle;
break;
}
} else {
switch (findIdMatchingType(selector)) {
case IdMatchingType::None:
m_matchType = CompilableSingle;
break;
case IdMatchingType::Rightmost:
m_matchType = RightMostWithIdMatch;
break;
case IdMatchingType::Filter:
m_matchType = CompilableSingleWithRootFilter;
break;
}
}
} else
m_matchType = MultipleSelectorMatch;
}
inline bool SelectorDataList::selectorMatches(const SelectorData& selectorData, Element& element, const ContainerNode& rootNode) const
{
if (selectorData.isFastCheckable && !element.isSVGElement()) {
SelectorCheckerFastPath selectorCheckerFastPath(selectorData.selector, &element);
if (!selectorCheckerFastPath.matchesRightmostSelector(SelectorChecker::VisitedMatchDisabled))
return false;
return selectorCheckerFastPath.matches();
}
SelectorChecker selectorChecker(element.document(), SelectorChecker::Mode::QueryingRules);
SelectorChecker::SelectorCheckingContext selectorCheckingContext(selectorData.selector, &element, SelectorChecker::VisitedMatchDisabled);
selectorCheckingContext.scope = rootNode.isDocumentNode() ? nullptr : &rootNode;
return selectorChecker.match(selectorCheckingContext);
}
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;
}
struct AllElementExtractorSelectorQueryTrait {
typedef Vector<Ref<Element>> OutputType;
static const bool shouldOnlyMatchFirstElement = false;
ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element) { ASSERT(element); output.append(*element); }
};
RefPtr<NodeList> SelectorDataList::queryAll(ContainerNode& rootNode) const
{
Vector<Ref<Element>> result;
execute<AllElementExtractorSelectorQueryTrait>(rootNode, result);
return StaticElementList::adopt(result);
}
struct SingleElementExtractorSelectorQueryTrait {
typedef Element* OutputType;
static const bool shouldOnlyMatchFirstElement = true;
ALWAYS_INLINE static void appendOutputForElement(OutputType& output, Element* element)
{
ASSERT(element);
ASSERT(!output);
output = element;
}
};
Element* SelectorDataList::queryFirst(ContainerNode& rootNode) const
{
Element* result = nullptr;
execute<SingleElementExtractorSelectorQueryTrait>(rootNode, result);
return result;
}
static const CSSSelector* selectorForIdLookup(const ContainerNode& rootNode, const CSSSelector& firstSelector)
{
if (!rootNode.inDocument())
return nullptr;
if (rootNode.document().inQuirksMode())
return nullptr;
for (const CSSSelector* selector = &firstSelector; selector; selector = selector->tagHistory()) {
if (selector->m_match == CSSSelector::Id)
return selector;
if (selector->relation() != CSSSelector::SubSelector)
break;
}
return nullptr;
}
static inline bool isTreeScopeRoot(const ContainerNode& node)
{
return node.isDocumentNode() || node.isShadowRoot();
}
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::executeFastPathForIdSelector(const ContainerNode& rootNode, const SelectorData& selectorData, const CSSSelector* idSelector, typename SelectorQueryTrait::OutputType& output) const
{
ASSERT(m_selectors.size() == 1);
ASSERT(idSelector);
const AtomicString& idToMatch = idSelector->value();
if (UNLIKELY(rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
const Vector<Element*>* elements = rootNode.treeScope().getAllElementsById(idToMatch);
ASSERT(elements);
size_t count = elements->size();
bool rootNodeIsTreeScopeRoot = isTreeScopeRoot(rootNode);
for (size_t i = 0; i < count; ++i) {
Element& element = *elements->at(i);
if ((rootNodeIsTreeScopeRoot || element.isDescendantOf(&rootNode)) && selectorMatches(selectorData, element, rootNode)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
return;
}
Element* element = rootNode.treeScope().getElementById(idToMatch);
if (!element || !(isTreeScopeRoot(rootNode) || element->isDescendantOf(&rootNode)))
return;
if (selectorMatches(selectorData, *element, rootNode))
SelectorQueryTrait::appendOutputForElement(output, element);
}
#if ENABLE(CSS_SELECTOR_JIT)
static ContainerNode& filterRootById(ContainerNode& rootNode, const CSSSelector& firstSelector)
{
if (!rootNode.inDocument())
return rootNode;
if (rootNode.document().inQuirksMode())
return rootNode;
const CSSSelector* selector = &firstSelector;
do {
ASSERT(selector->m_match != CSSSelector::Id);
if (selector->relation() != CSSSelector::SubSelector)
break;
selector = selector->tagHistory();
} while (selector);
bool inAdjacentChain = false;
for (; selector; selector = selector->tagHistory()) {
if (selector->m_match == CSSSelector::Id) {
const AtomicString& idToMatch = selector->value();
if (ContainerNode* searchRoot = rootNode.treeScope().getElementById(idToMatch)) {
if (LIKELY(!rootNode.treeScope().containsMultipleElementsWithId(idToMatch))) {
if (inAdjacentChain)
searchRoot = searchRoot->parentNode();
if (searchRoot && (isTreeScopeRoot(rootNode) || searchRoot == &rootNode || searchRoot->isDescendantOf(&rootNode)))
return *searchRoot;
}
}
}
if (selector->relation() == CSSSelector::DirectAdjacent || selector->relation() == CSSSelector::IndirectAdjacent)
inAdjacentChain = true;
else
inAdjacentChain = false;
}
return rootNode;
}
#endif
template <typename SelectorQueryTrait>
static inline void elementsForLocalName(const ContainerNode& rootNode, const AtomicString& localName, typename SelectorQueryTrait::OutputType& output)
{
for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (element.tagQName().localName() == localName) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
template <typename SelectorQueryTrait>
static inline void anyElement(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output)
{
for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::executeSingleTagNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
{
ASSERT(m_selectors.size() == 1);
ASSERT(isSingleTagNameSelector(*selectorData.selector));
const QualifiedName& tagQualifiedName = selectorData.selector->tagQName();
const AtomicString& selectorLocalName = tagQualifiedName.localName();
const AtomicString& selectorNamespaceURI = tagQualifiedName.namespaceURI();
if (selectorNamespaceURI == starAtom) {
if (selectorLocalName != starAtom) {
elementsForLocalName<SelectorQueryTrait>(rootNode, selectorLocalName, output);
} else {
anyElement<SelectorQueryTrait>(rootNode, output);
}
} else {
for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (element.namespaceURI() == selectorNamespaceURI && (selectorLocalName == starAtom || element.tagQName().localName() == selectorLocalName)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
}
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::executeSingleClassNameSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
{
ASSERT(m_selectors.size() == 1);
ASSERT(isSingleClassNameSelector(*selectorData.selector));
const AtomicString& className = selectorData.selector->value();
for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (element.hasClass() && element.classNames().contains(className)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::executeSingleSelectorData(const ContainerNode& rootNode, const SelectorData& selectorData, typename SelectorQueryTrait::OutputType& output) const
{
ASSERT(m_selectors.size() == 1);
for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
if (selectorMatches(selectorData, element, rootNode)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::executeSingleMultiSelectorData(const ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
unsigned selectorCount = m_selectors.size();
for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
for (unsigned i = 0; i < selectorCount; ++i) {
if (selectorMatches(m_selectors[i], element, rootNode)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
break;
}
}
}
}
#if ENABLE(CSS_SELECTOR_JIT)
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::executeCompiledSimpleSelectorChecker(const ContainerNode& rootNode, SelectorCompiler::SimpleSelectorChecker selectorChecker, typename SelectorQueryTrait::OutputType& output, const SelectorData& selectorData) const
{
for (auto& element : elementDescendants(const_cast<ContainerNode&>(rootNode))) {
#if CSS_SELECTOR_JIT_PROFILING
selectorData.compiledSelectorUsed();
#else
UNUSED_PARAM(selectorData);
#endif
if (selectorChecker(&element)) {
SelectorQueryTrait::appendOutputForElement(output, &element);
if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
return;
}
}
}
#endif // ENABLE(CSS_SELECTOR_JIT)
template <typename SelectorQueryTrait>
ALWAYS_INLINE void SelectorDataList::execute(ContainerNode& rootNode, typename SelectorQueryTrait::OutputType& output) const
{
ContainerNode* searchRootNode = &rootNode;
switch (m_matchType) {
case RightMostWithIdMatch:
{
const SelectorData& selectorData = m_selectors.first();
if (const CSSSelector* idSelector = selectorForIdLookup(*searchRootNode, *selectorData.selector)) {
executeFastPathForIdSelector<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), idSelector, output);
break;
}
#if ENABLE(CSS_SELECTOR_JIT)
if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker)
goto CompiledSingleCase;
#endif
}
FALLTHROUGH;
case CompilableSingleWithRootFilter:
case CompilableSingle:
{
#if ENABLE(CSS_SELECTOR_JIT)
const SelectorData& selectorData = m_selectors.first();
ASSERT(m_matchType == RightMostWithIdMatch || selectorData.compilationStatus == SelectorCompilationStatus::NotCompiled);
JSC::VM& vm = searchRootNode->document().scriptExecutionContext()->vm();
selectorData.compilationStatus = SelectorCompiler::compileSelector(selectorData.selector, &vm, SelectorCompiler::SelectorContext::QuerySelector, selectorData.compiledSelectorCodeRef);
RELEASE_ASSERT(selectorData.compilationStatus != SelectorCompilationStatus::SelectorCheckerWithCheckingContext);
if (selectorData.compilationStatus == SelectorCompilationStatus::SimpleSelectorChecker) {
if (m_matchType == CompilableSingle) {
m_matchType = CompiledSingle;
goto CompiledSingleCase;
}
if (m_matchType == CompilableSingleWithRootFilter) {
m_matchType = CompiledSingleWithRootFilter;
goto CompiledSingleWithRootFilterCase;
}
goto CompiledSingleCase;
}
if (m_matchType != RightMostWithIdMatch)
m_matchType = SingleSelector;
goto SingleSelectorCase;
ASSERT_NOT_REACHED();
break;
#else
FALLTHROUGH;
#endif // ENABLE(CSS_SELECTOR_JIT)
}
case CompiledSingleWithRootFilter:
#if ENABLE(CSS_SELECTOR_JIT)
CompiledSingleWithRootFilterCase:
searchRootNode = &filterRootById(*searchRootNode, *m_selectors.first().selector);
#endif // ENABLE(CSS_SELECTOR_JIT)
FALLTHROUGH;
case CompiledSingle:
#if ENABLE(CSS_SELECTOR_JIT)
{
CompiledSingleCase:
const SelectorData& selectorData = m_selectors.first();
void* compiledSelectorChecker = selectorData.compiledSelectorCodeRef.code().executableAddress();
SelectorCompiler::SimpleSelectorChecker selectorChecker = SelectorCompiler::simpleSelectorCheckerFunction(compiledSelectorChecker, selectorData.compilationStatus);
executeCompiledSimpleSelectorChecker<SelectorQueryTrait>(*searchRootNode, selectorChecker, output, selectorData);
break;
}
#else
FALLTHROUGH;
#endif // ENABLE(CSS_SELECTOR_JIT)
case SingleSelector:
#if ENABLE(CSS_SELECTOR_JIT)
SingleSelectorCase:
#endif
executeSingleSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
break;
case TagNameMatch:
executeSingleTagNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
break;
case ClassNameMatch:
executeSingleClassNameSelectorData<SelectorQueryTrait>(*searchRootNode, m_selectors.first(), output);
break;
case MultipleSelectorMatch:
executeSingleMultiSelectorData<SelectorQueryTrait>(*searchRootNode, output);
break;
}
}
SelectorQuery::SelectorQuery(CSSSelectorList&& selectorList)
: m_selectorList(selectorList)
, m_selectors(m_selectorList)
{
}
SelectorQuery* SelectorQueryCache::add(const String& selectors, Document& document, ExceptionCode& ec)
{
auto it = m_entries.find(selectors);
if (it != m_entries.end())
return it->value.get();
CSSParser parser(document);
CSSSelectorList selectorList;
parser.parseSelector(selectors, selectorList);
if (!selectorList.first() || selectorList.hasInvalidSelector()) {
ec = SYNTAX_ERR;
return nullptr;
}
if (selectorList.selectorsNeedNamespaceResolution()) {
ec = NAMESPACE_ERR;
return nullptr;
}
const int maximumSelectorQueryCacheSize = 256;
if (m_entries.size() == maximumSelectorQueryCacheSize)
m_entries.remove(m_entries.begin());
return m_entries.add(selectors, std::make_unique<SelectorQuery>(WTF::move(selectorList))).iterator->value.get();
}
}