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 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) 2012 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/SelectorFilter.h"
31
32#include "core/css/CSSSelector.h"
33
34namespace blink {
35
36// Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
37enum { TagNameSalt = 13, IdAttributeSalt = 17, ClassAttributeSalt = 19 };
38
39static inline void collectElementIdentifierHashes(const Element& element, Vector<unsigned, 4>& identifierHashes)
40{
41    identifierHashes.append(element.localName().impl()->existingHash() * TagNameSalt);
42    if (element.hasID())
43        identifierHashes.append(element.idForStyleResolution().impl()->existingHash() * IdAttributeSalt);
44    if (element.isStyledElement() && element.hasClass()) {
45        const SpaceSplitString& classNames = element.classNames();
46        size_t count = classNames.size();
47        for (size_t i = 0; i < count; ++i)
48            identifierHashes.append(classNames[i].impl()->existingHash() * ClassAttributeSalt);
49    }
50}
51
52void SelectorFilter::pushParentStackFrame(Element& parent)
53{
54    ASSERT(m_ancestorIdentifierFilter);
55    ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent.parentOrShadowHostElement());
56    ASSERT(!m_parentStack.isEmpty() || !parent.parentOrShadowHostElement());
57    m_parentStack.append(ParentStackFrame(parent));
58    ParentStackFrame& parentFrame = m_parentStack.last();
59    // Mix tags, class names and ids into some sort of weird bouillabaisse.
60    // The filter is used for fast rejection of child and descendant selectors.
61    collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
62    size_t count = parentFrame.identifierHashes.size();
63    for (size_t i = 0; i < count; ++i)
64        m_ancestorIdentifierFilter->add(parentFrame.identifierHashes[i]);
65}
66
67void SelectorFilter::popParentStackFrame()
68{
69    ASSERT(!m_parentStack.isEmpty());
70    ASSERT(m_ancestorIdentifierFilter);
71    const ParentStackFrame& parentFrame = m_parentStack.last();
72    size_t count = parentFrame.identifierHashes.size();
73    for (size_t i = 0; i < count; ++i)
74        m_ancestorIdentifierFilter->remove(parentFrame.identifierHashes[i]);
75    m_parentStack.removeLast();
76    if (m_parentStack.isEmpty()) {
77        ASSERT(m_ancestorIdentifierFilter->likelyEmpty());
78        m_ancestorIdentifierFilter.clear();
79    }
80}
81
82void SelectorFilter::setupParentStack(Element& parent)
83{
84    ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
85    // Kill whatever we stored before.
86    m_parentStack.shrink(0);
87    m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
88    // Fast version if parent is a root element:
89    if (!parent.parentOrShadowHostNode()) {
90        pushParentStackFrame(parent);
91        return;
92    }
93    // Otherwise climb up the tree.
94    WillBeHeapVector<RawPtrWillBeMember<Element>, 30> ancestors;
95    for (Element* ancestor = &parent; ancestor; ancestor = ancestor->parentOrShadowHostElement())
96        ancestors.append(ancestor);
97    for (size_t n = ancestors.size(); n; --n)
98        pushParentStackFrame(*ancestors[n - 1]);
99}
100
101void SelectorFilter::pushParent(Element& parent)
102{
103    ASSERT(m_ancestorIdentifierFilter);
104    // We may get invoked for some random elements in some wacky cases during style resolve.
105    // Pause maintaining the stack in this case.
106    if (m_parentStack.last().element != parent.parentOrShadowHostElement())
107        return;
108    pushParentStackFrame(parent);
109}
110
111static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector& selector, unsigned*& hash)
112{
113    switch (selector.match()) {
114    case CSSSelector::Id:
115        if (!selector.value().isEmpty())
116            (*hash++) = selector.value().impl()->existingHash() * IdAttributeSalt;
117        break;
118    case CSSSelector::Class:
119        if (!selector.value().isEmpty())
120            (*hash++) = selector.value().impl()->existingHash() * ClassAttributeSalt;
121        break;
122    case CSSSelector::Tag:
123        if (selector.tagQName().localName() != starAtom)
124            (*hash++) = selector.tagQName().localName().impl()->existingHash() * TagNameSalt;
125        break;
126    default:
127        break;
128    }
129}
130
131void SelectorFilter::collectIdentifierHashes(const CSSSelector& selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
132{
133    unsigned* hash = identifierHashes;
134    unsigned* end = identifierHashes + maximumIdentifierCount;
135    CSSSelector::Relation relation = selector.relation();
136    bool relationIsAffectedByPseudoContent = selector.relationIsAffectedByPseudoContent();
137
138    // Skip the topmost selector. It is handled quickly by the rule hashes.
139    bool skipOverSubselectors = true;
140    for (const CSSSelector* current = selector.tagHistory(); current; current = current->tagHistory()) {
141        // Only collect identifiers that match ancestors.
142        switch (relation) {
143        case CSSSelector::SubSelector:
144            if (!skipOverSubselectors)
145                collectDescendantSelectorIdentifierHashes(*current, hash);
146            break;
147        case CSSSelector::DirectAdjacent:
148        case CSSSelector::IndirectAdjacent:
149            skipOverSubselectors = true;
150            break;
151        case CSSSelector::Descendant:
152        case CSSSelector::Child:
153            if (relationIsAffectedByPseudoContent) {
154                // Disable fastRejectSelector.
155                *identifierHashes = 0;
156                return;
157            }
158            // Fall through.
159        case CSSSelector::ShadowPseudo:
160        case CSSSelector::ShadowDeep:
161            skipOverSubselectors = false;
162            collectDescendantSelectorIdentifierHashes(*current, hash);
163            break;
164        }
165        if (hash == end)
166            return;
167        relation = current->relation();
168        relationIsAffectedByPseudoContent = current->relationIsAffectedByPseudoContent();
169    }
170    *hash = 0;
171}
172
173void SelectorFilter::ParentStackFrame::trace(Visitor* visitor)
174{
175    visitor->trace(element);
176}
177
178void SelectorFilter::trace(Visitor* visitor)
179{
180    visitor->trace(m_parentStack);
181}
182
183}
184