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