Home | History | Annotate | Download | only in css 
      1 /*
      2  * Copyright (C) 1999 Lars Knoll (knoll (at) kde.org)
      3  *           (C) 2004-2005 Allan Sandfeld Jensen (kde (at) carewolf.com)
      4  * Copyright (C) 2006, 2007 Nicholas Shanks (webkit (at) nickshanks.com)
      5  * Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011 Apple Inc. All rights reserved.
      6  * Copyright (C) 2007 Alexey Proskuryakov <ap (at) webkit.org>
      7  * Copyright (C) 2007, 2008 Eric Seidel <eric (at) 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 #include "core/dom/Element.h"
     34 
     35 namespace WebCore {
     36 
     37 // Salt to separate otherwise identical string hashes so a class-selector like .article won't match <article> elements.
     38 enum { TagNameSalt = 13, IdAttributeSalt = 17, ClassAttributeSalt = 19 };
     39 
     40 static 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     if (element->isStyledElement() && element->hasClass()) {
     46         const SpaceSplitString& classNames = element->classNames();
     47         size_t count = classNames.size();
     48         for (size_t i = 0; i < count; ++i)
     49             identifierHashes.append(classNames[i].impl()->existingHash() * ClassAttributeSalt);
     50     }
     51 }
     52 
     53 void SelectorFilter::pushParentStackFrame(Element* parent)
     54 {
     55     ASSERT(m_ancestorIdentifierFilter);
     56     ASSERT(m_parentStack.isEmpty() || m_parentStack.last().element == parent->parentOrShadowHostElement());
     57     ASSERT(!m_parentStack.isEmpty() || !parent->parentOrShadowHostElement());
     58     m_parentStack.append(ParentStackFrame(parent));
     59     ParentStackFrame& parentFrame = m_parentStack.last();
     60     // Mix tags, class names and ids into some sort of weird bouillabaisse.
     61     // The filter is used for fast rejection of child and descendant selectors.
     62     collectElementIdentifierHashes(parent, parentFrame.identifierHashes);
     63     size_t count = parentFrame.identifierHashes.size();
     64     for (size_t i = 0; i < count; ++i)
     65         m_ancestorIdentifierFilter->add(parentFrame.identifierHashes[i]);
     66 }
     67 
     68 void SelectorFilter::popParentStackFrame()
     69 {
     70     ASSERT(!m_parentStack.isEmpty());
     71     ASSERT(m_ancestorIdentifierFilter);
     72     const ParentStackFrame& parentFrame = m_parentStack.last();
     73     size_t count = parentFrame.identifierHashes.size();
     74     for (size_t i = 0; i < count; ++i)
     75         m_ancestorIdentifierFilter->remove(parentFrame.identifierHashes[i]);
     76     m_parentStack.removeLast();
     77     if (m_parentStack.isEmpty()) {
     78         ASSERT(m_ancestorIdentifierFilter->likelyEmpty());
     79         m_ancestorIdentifierFilter.clear();
     80     }
     81 }
     82 
     83 void SelectorFilter::setupParentStack(Element* parent)
     84 {
     85     ASSERT(m_parentStack.isEmpty() == !m_ancestorIdentifierFilter);
     86     // Kill whatever we stored before.
     87     m_parentStack.shrink(0);
     88     m_ancestorIdentifierFilter = adoptPtr(new BloomFilter<bloomFilterKeyBits>);
     89     // Fast version if parent is a root element:
     90     if (!parent->parentOrShadowHostNode()) {
     91         pushParentStackFrame(parent);
     92         return;
     93     }
     94     // Otherwise climb up the tree.
     95     Vector<Element*, 30> ancestors;
     96     for (Element* ancestor = parent; ancestor; ancestor = ancestor->parentOrShadowHostElement())
     97         ancestors.append(ancestor);
     98     for (size_t n = ancestors.size(); n; --n)
     99         pushParentStackFrame(ancestors[n - 1]);
    100 }
    101 
    102 void SelectorFilter::pushParent(Element* parent)
    103 {
    104     ASSERT(m_ancestorIdentifierFilter);
    105     // We may get invoked for some random elements in some wacky cases during style resolve.
    106     // Pause maintaining the stack in this case.
    107     if (m_parentStack.last().element != parent->parentOrShadowHostElement())
    108         return;
    109     pushParentStackFrame(parent);
    110 }
    111 
    112 static inline void collectDescendantSelectorIdentifierHashes(const CSSSelector* selector, unsigned*& hash)
    113 {
    114     switch (selector->m_match) {
    115     case CSSSelector::Id:
    116         if (!selector->value().isEmpty())
    117             (*hash++) = selector->value().impl()->existingHash() * IdAttributeSalt;
    118         break;
    119     case CSSSelector::Class:
    120         if (!selector->value().isEmpty())
    121             (*hash++) = selector->value().impl()->existingHash() * ClassAttributeSalt;
    122         break;
    123     case CSSSelector::Tag:
    124         if (selector->tagQName().localName() != starAtom)
    125             (*hash++) = selector->tagQName().localName().impl()->existingHash() * TagNameSalt;
    126         break;
    127     default:
    128         break;
    129     }
    130 }
    131 
    132 void SelectorFilter::collectIdentifierHashes(const CSSSelector* selector, unsigned* identifierHashes, unsigned maximumIdentifierCount)
    133 {
    134     unsigned* hash = identifierHashes;
    135     unsigned* end = identifierHashes + maximumIdentifierCount;
    136     CSSSelector::Relation relation = selector->relation();
    137     bool relationIsAffectedByPseudoContent = selector->relationIsAffectedByPseudoContent();
    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::ShadowPseudo:
    151             skipOverSubselectors = true;
    152             break;
    153         case CSSSelector::Descendant:
    154         case CSSSelector::Child:
    155             if (relationIsAffectedByPseudoContent) {
    156                 skipOverSubselectors = true;
    157                 break;
    158             }
    159             skipOverSubselectors = false;
    160             collectDescendantSelectorIdentifierHashes(selector, hash);
    161             break;
    162         }
    163         if (hash == end)
    164             return;
    165         relation = selector->relation();
    166         relationIsAffectedByPseudoContent = selector->relationIsAffectedByPseudoContent();
    167     }
    168     *hash = 0;
    169 }
    170 
    171 }
    172