Source/WebCore/css/SelectorFilter.cpp

/*
 * Copyright (C) 1999 Lars Knoll (knoll@kde.org)
 *           (C) 2004-2005 Allan Sandfeld Jensen (kde@carewolf.com)
 * Copyright (C) 2006, 2007 Nicholas Shanks (webkit@nickshanks.com)
 * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
 * Copyright (C) 2007 Alexey Proskuryakov <ap@webkit.org>
 * Copyright (C) 2007, 2008 Eric Seidel <eric@webkit.org>
 * Copyright (C) 2008, 2009 Torch Mobile Inc. All rights reserved. (http://www.torchmobile.com/)
 * Copyright (c) 2011, Code Aurora Forum. All rights reserved.
 * Copyright (C) Research In Motion Limited 2011. All rights reserved.
 * Copyright (C) 2012 Google Inc. All rights reserved.
 *
 * 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 "config.h"
#include "SelectorFilter.h"

#include "CSSSelector.h"
#include "ShadowRoot.h"
#include "StyledElement.h"

namespace WebCore {

// Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
enum { TagNameSalt = 13, IdAttributeSalt = 17, ClassAttributeSalt = 19 };

static inline void collectElementIdentifierHashes(const Element* element, Vector<unsigned, 4>& identifierHashes)
{
    AtomicString tagLowercaseLocalName = element->localName().convertToASCIILowercase();
    identifierHashes.append(tagLowercaseLocalName.impl()->existingHash() * TagNameSalt);

    auto& id = element->idForStyleResolution();
    if (!id.isNull())
        identifierHashes.append(id.impl()->existingHash() * IdAttributeSalt);
    const StyledElement* styledElement = element->isStyledElement() ? static_cast<const StyledElement*>(element) : 0;
    if (styledElement && styledElement->hasClass()) {
        const SpaceSplitString& classNames = styledElement->classNames();
        size_t count = classNames.size();
        for (size_t i = 0; i < count; ++i)
            identifierHashes.append(classNames[i].impl()->existingHash() * ClassAttributeSalt);
    }
}

bool SelectorFilter::parentStackIsConsistent(const ContainerNode* parentNode) const
{
    if (!parentNode || is<Document>(parentNode) || is<ShadowRoot>(parentNode))
        return m_parentStack.isEmpty();

    return !m_parentStack.isEmpty() && m_parentStack.last().element == parentNode;
}

void SelectorFilter::pushParentStackFrame(Element* parent)
{
    ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentElement());
    ASSERT(!m_parentStack.isEmpty() || !parent->parentElement());
    m_parentStack.append(ParentStackFrame(parent));
    ParentStackFrame& parentFrame = m_parentStack.last();
    // Mix tags, class names and ids into some sort of weird bouillabaisse.
    // The filter is used for fast rejection of child and descendant selectors.
    collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
    size_t count = parentFrame.identifierHashes.size();
    for (size_t i = 0; i < count; ++i)
        m_ancestorIdentifierFilter.add(parentFrame.identifierHashes[i]);
}

void SelectorFilter::popParentStackFrame()
{
    ASSERT(!m_parentStack.isEmpty());
    const ParentStackFrame& parentFrame = m_parentStack.last();
    size_t count = parentFrame.identifierHashes.size();
    for (size_t i = 0; i < count; ++i)
        m_ancestorIdentifierFilter.remove(parentFrame.identifierHashes[i]);
    m_parentStack.removeLast();
    if (m_parentStack.isEmpty()) {
        ASSERT(m_ancestorIdentifierFilter.likelyEmpty());
        m_ancestorIdentifierFilter.clear();
    }
}

void SelectorFilter::pushParent(Element* parent)
{
    pushParentStackFrame(parent);
}

static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned*& hash)
{
    switch (selector->match()) {
    case CSSSelector::Id:
        if (!selector->value().isEmpty())
            (*hash++) = selector->value().impl()->existingHash() * IdAttributeSalt;
        break;
    case CSSSelector::Class:
        if (!selector->value().isEmpty())
            (*hash++) = selector->value().impl()->existingHash() * ClassAttributeSalt;
        break;
    case CSSSelector::Tag: {
        const AtomicString& tagLowercaseLocalName = selector->tagLowercaseLocalName();
        if (tagLowercaseLocalName != starAtom)
            (*hash++) = tagLowercaseLocalName.impl()->existingHash() * TagNameSalt;
        break;
    }
    default:
        break;
    }
}

void SelectorFilter::collectIdentifierHashes(const CSSSelector* selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
{
    unsigned* hash = identifierHashes;
    unsigned* end = identifierHashes + maximumIdentifierCount;
    CSSSelector::Relation relation = selector->relation();

    // Skip the topmost selector. It is handled quickly by the rule hashes.
    bool skipOverSubselectors = true;
    for (selector = selector->tagHistory(); selector; selector = selector->tagHistory()) {
        // Only collect identifiers that match ancestors.
        switch (relation) {
        case CSSSelector::SubSelector:
            if (!skipOverSubselectors)
                collectDescendantSelectorIdentifierHashes(selector, hash);
            break;
        case CSSSelector::DirectAdjacent:
        case CSSSelector::IndirectAdjacent:
        case CSSSelector::ShadowDescendant:
            skipOverSubselectors = true;
            break;
        case CSSSelector::ShadowSlot:
            // Disable fastRejectSelector.
            *identifierHashes = 0;
            return;
        case CSSSelector::Descendant:
        case CSSSelector::Child:
        case CSSSelector::ShadowPseudo:
        case CSSSelector::ShadowDeep:
            skipOverSubselectors = false;
            collectDescendantSelectorIdentifierHashes(selector, hash);
            break;
        }
        if (hash == end)
            return;
        relation = selector->relation();
    }
    *hash = 0;
}

}