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, 2012, 2013 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/ElementRuleCollector.h"
31
32#include "core/css/CSSRuleList.h"
33#include "core/css/CSSSelector.h"
34#include "core/css/CSSStyleRule.h"
35#include "core/css/CSSStyleSheet.h"
36#include "core/css/SelectorCheckerFastPath.h"
37#include "core/css/SiblingTraversalStrategies.h"
38#include "core/css/StylePropertySet.h"
39#include "core/css/resolver/StyleResolver.h"
40#include "core/dom/shadow/ShadowRoot.h"
41#include "core/rendering/RenderRegion.h"
42
43namespace WebCore {
44
45ElementRuleCollector::ElementRuleCollector(const ElementResolveContext& context,
46    const SelectorFilter& filter, RenderStyle* style, ShouldIncludeStyleSheetInCSSOMWrapper includeStyleSheet)
47    : m_context(context)
48    , m_selectorFilter(filter)
49    , m_style(style)
50    , m_regionForStyling(0)
51    , m_pseudoStyleRequest(NOPSEUDO)
52    , m_mode(SelectorChecker::ResolvingStyle)
53    , m_canUseFastReject(m_selectorFilter.parentStackIsConsistent(context.parentNode()))
54    , m_sameOriginOnly(false)
55    , m_matchingUARules(false)
56    , m_includeStyleSheet(includeStyleSheet)
57{ }
58
59ElementRuleCollector::~ElementRuleCollector()
60{
61}
62
63MatchResult& ElementRuleCollector::matchedResult()
64{
65    return m_result;
66}
67
68PassRefPtr<StyleRuleList> ElementRuleCollector::matchedStyleRuleList()
69{
70    ASSERT(m_mode == SelectorChecker::CollectingStyleRules);
71    return m_styleRuleList.release();
72}
73
74PassRefPtr<CSSRuleList> ElementRuleCollector::matchedCSSRuleList()
75{
76    ASSERT(m_mode == SelectorChecker::CollectingCSSRules);
77    return m_cssRuleList.release();
78}
79
80inline void ElementRuleCollector::addMatchedRule(const RuleData* rule, unsigned specificity, CascadeScope cascadeScope, CascadeOrder cascadeOrder, unsigned styleSheetIndex)
81{
82    if (!m_matchedRules)
83        m_matchedRules = adoptPtr(new Vector<MatchedRule, 32>);
84    m_matchedRules->append(MatchedRule(rule, specificity, cascadeScope, cascadeOrder, styleSheetIndex));
85}
86
87void ElementRuleCollector::clearMatchedRules()
88{
89    if (!m_matchedRules)
90        return;
91    m_matchedRules->clear();
92}
93
94inline StyleRuleList* ElementRuleCollector::ensureStyleRuleList()
95{
96    if (!m_styleRuleList)
97        m_styleRuleList = StyleRuleList::create();
98    return m_styleRuleList.get();
99}
100
101inline StaticCSSRuleList* ElementRuleCollector::ensureRuleList()
102{
103    if (!m_cssRuleList)
104        m_cssRuleList = StaticCSSRuleList::create();
105    return m_cssRuleList.get();
106}
107
108void ElementRuleCollector::addElementStyleProperties(const StylePropertySet* propertySet, bool isCacheable)
109{
110    if (!propertySet)
111        return;
112    m_result.ranges.lastAuthorRule = m_result.matchedProperties.size();
113    if (m_result.ranges.firstAuthorRule == -1)
114        m_result.ranges.firstAuthorRule = m_result.ranges.lastAuthorRule;
115    m_result.addMatchedProperties(propertySet);
116    if (!isCacheable)
117        m_result.isCacheable = false;
118}
119
120static bool rulesApplicableInCurrentTreeScope(const Element* element, const ContainerNode* scopingNode, SelectorChecker::BehaviorAtBoundary behaviorAtBoundary, bool elementApplyAuthorStyles)
121{
122    TreeScope& treeScope = element->treeScope();
123
124    // [skipped, because already checked] a) it's a UA rule
125    // b) element is allowed to apply author rules
126    if (elementApplyAuthorStyles)
127        return true;
128    // c) the rules comes from a scoped style sheet within the same tree scope
129    if (!scopingNode || treeScope == scopingNode->treeScope())
130        return true;
131    // d) the rules comes from a scoped style sheet within an active shadow root whose host is the given element
132    if (element->isInShadowTree() && (behaviorAtBoundary & SelectorChecker::ScopeIsShadowHost) && scopingNode == element->containingShadowRoot()->host())
133        return true;
134    // e) the rules can cross boundaries
135    if ((behaviorAtBoundary & SelectorChecker::BoundaryBehaviorMask) == SelectorChecker::CrossesBoundary)
136        return true;
137    return false;
138}
139
140void ElementRuleCollector::collectMatchingRules(const MatchRequest& matchRequest, RuleRange& ruleRange, SelectorChecker::BehaviorAtBoundary behaviorAtBoundary, CascadeScope cascadeScope, CascadeOrder cascadeOrder)
141{
142    ASSERT(matchRequest.ruleSet);
143    ASSERT(m_context.element());
144
145    Element& element = *m_context.element();
146    const AtomicString& pseudoId = element.shadowPseudoId();
147    if (!pseudoId.isEmpty()) {
148        ASSERT(element.isStyledElement());
149        collectMatchingRulesForList(matchRequest.ruleSet->shadowPseudoElementRules(pseudoId.impl()), behaviorAtBoundary, ignoreCascadeScope, cascadeOrder, matchRequest, ruleRange);
150    }
151
152    if (element.isVTTElement())
153        collectMatchingRulesForList(matchRequest.ruleSet->cuePseudoRules(), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
154    // Check whether other types of rules are applicable in the current tree scope. Criteria for this:
155    // a) it's a UA rule
156    // b) the tree scope allows author rules
157    // c) the rules comes from a scoped style sheet within the same tree scope
158    // d) the rules comes from a scoped style sheet within an active shadow root whose host is the given element
159    // e) the rules can cross boundaries
160    // b)-e) is checked in rulesApplicableInCurrentTreeScope.
161    if (!m_matchingUARules && !rulesApplicableInCurrentTreeScope(&element, matchRequest.scope, behaviorAtBoundary, matchRequest.elementApplyAuthorStyles))
162        return;
163
164    // We need to collect the rules for id, class, tag, and everything else into a buffer and
165    // then sort the buffer.
166    if (element.hasID())
167        collectMatchingRulesForList(matchRequest.ruleSet->idRules(element.idForStyleResolution().impl()), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
168    if (element.isStyledElement() && element.hasClass()) {
169        for (size_t i = 0; i < element.classNames().size(); ++i)
170            collectMatchingRulesForList(matchRequest.ruleSet->classRules(element.classNames()[i].impl()), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
171    }
172
173    if (element.isLink())
174        collectMatchingRulesForList(matchRequest.ruleSet->linkPseudoClassRules(), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
175    if (SelectorChecker::matchesFocusPseudoClass(element))
176        collectMatchingRulesForList(matchRequest.ruleSet->focusPseudoClassRules(), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
177    collectMatchingRulesForList(matchRequest.ruleSet->tagRules(element.localName().impl()), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
178    collectMatchingRulesForList(matchRequest.ruleSet->universalRules(), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
179}
180
181void ElementRuleCollector::collectMatchingRulesForRegion(const MatchRequest& matchRequest, RuleRange& ruleRange, SelectorChecker::BehaviorAtBoundary behaviorAtBoundary, CascadeScope cascadeScope, CascadeOrder cascadeOrder)
182{
183    if (!m_regionForStyling)
184        return;
185
186    unsigned size = matchRequest.ruleSet->m_regionSelectorsAndRuleSets.size();
187    for (unsigned i = 0; i < size; ++i) {
188        const CSSSelector* regionSelector = matchRequest.ruleSet->m_regionSelectorsAndRuleSets.at(i).selector;
189        if (checkRegionSelector(regionSelector, toElement(m_regionForStyling->nodeForRegion()))) {
190            RuleSet* regionRules = matchRequest.ruleSet->m_regionSelectorsAndRuleSets.at(i).ruleSet.get();
191            ASSERT(regionRules);
192            collectMatchingRules(MatchRequest(regionRules, matchRequest.includeEmptyRules, matchRequest.scope), ruleRange, behaviorAtBoundary, cascadeScope, cascadeOrder);
193        }
194    }
195}
196
197
198static CSSStyleSheet* findStyleSheet(StyleEngine* styleEngine, StyleRule* rule)
199{
200    // FIXME: StyleEngine has a bunch of different accessors for StyleSheet lists, is this the only one we need to care about?
201    const Vector<RefPtr<CSSStyleSheet> >& stylesheets = styleEngine->activeAuthorStyleSheets();
202    for (size_t i = 0; i < stylesheets.size(); ++i) {
203        CSSStyleSheet* sheet = stylesheets[i].get();
204        for (unsigned j = 0; j < sheet->length(); ++j) {
205            CSSRule* cssRule = sheet->item(j);
206            if (cssRule->type() != CSSRule::STYLE_RULE)
207                continue;
208            CSSStyleRule* cssStyleRule = toCSSStyleRule(cssRule);
209            if (cssStyleRule->styleRule() == rule)
210                return sheet;
211        }
212    }
213    return 0;
214}
215
216void ElementRuleCollector::appendCSSOMWrapperForRule(StyleRule* rule)
217{
218    // FIXME: There should be no codepath that creates a CSSOMWrapper without a parent stylesheet or rule because
219    // then that codepath can lead to the CSSStyleSheet contents not getting correctly copied when the rule is modified
220    // through the wrapper (e.g. rule.selectorText="div"). Right now, the inspector uses the pointers for identity though,
221    // so calling CSSStyleSheet->willMutateRules breaks the inspector.
222    CSSStyleSheet* sheet = m_includeStyleSheet == IncludeStyleSheetInCSSOMWrapper ? findStyleSheet(m_context.element()->document().styleEngine(), rule) : 0;
223    RefPtr<CSSRule> cssRule = rule->createCSSOMWrapper(sheet);
224    if (sheet)
225        sheet->registerExtraChildRuleCSSOMWrapper(cssRule);
226    ensureRuleList()->rules().append(cssRule);
227}
228
229void ElementRuleCollector::sortAndTransferMatchedRules()
230{
231    if (!m_matchedRules || m_matchedRules->isEmpty())
232        return;
233
234    sortMatchedRules();
235
236    Vector<MatchedRule, 32>& matchedRules = *m_matchedRules;
237    if (m_mode == SelectorChecker::CollectingStyleRules) {
238        for (unsigned i = 0; i < matchedRules.size(); ++i)
239            ensureStyleRuleList()->m_list.append(matchedRules[i].ruleData()->rule());
240        return;
241    }
242
243    if (m_mode == SelectorChecker::CollectingCSSRules) {
244        for (unsigned i = 0; i < matchedRules.size(); ++i)
245            appendCSSOMWrapperForRule(matchedRules[i].ruleData()->rule());
246        return;
247    }
248
249    // Now transfer the set of matched rules over to our list of declarations.
250    for (unsigned i = 0; i < matchedRules.size(); i++) {
251        // FIXME: Matching should not modify the style directly.
252        const RuleData* ruleData = matchedRules[i].ruleData();
253        if (m_style && ruleData->containsUncommonAttributeSelector())
254            m_style->setUnique();
255        m_result.addMatchedProperties(ruleData->rule()->properties(), ruleData->rule(), ruleData->linkMatchType(), ruleData->propertyWhitelistType(m_matchingUARules));
256    }
257}
258
259inline bool ElementRuleCollector::ruleMatches(const RuleData& ruleData, const ContainerNode* scope, SelectorChecker::BehaviorAtBoundary behaviorAtBoundary, SelectorChecker::MatchResult* result)
260{
261    // Scoped rules can't match because the fast path uses a pool of tag/class/ids, collected from
262    // elements in that tree and those will never match the host, since it's in a different pool.
263    if (ruleData.hasFastCheckableSelector() && !scope) {
264        // We know this selector does not include any pseudo elements.
265        if (m_pseudoStyleRequest.pseudoId != NOPSEUDO)
266            return false;
267        // We know a sufficiently simple single part selector matches simply because we found it from the rule hash.
268        // This is limited to HTML only so we don't need to check the namespace.
269        ASSERT(m_context.element());
270        if (ruleData.hasRightmostSelectorMatchingHTMLBasedOnRuleHash() && m_context.element()->isHTMLElement()) {
271            if (!ruleData.hasMultipartSelector())
272                return true;
273        }
274        if (ruleData.selector()->m_match == CSSSelector::Tag && !SelectorChecker::tagMatches(*m_context.element(), ruleData.selector()->tagQName()))
275            return false;
276        SelectorCheckerFastPath selectorCheckerFastPath(ruleData.selector(), *m_context.element());
277        if (!selectorCheckerFastPath.matchesRightmostAttributeSelector())
278            return false;
279
280        return selectorCheckerFastPath.matches();
281    }
282
283    // Slow path.
284    SelectorChecker selectorChecker(m_context.element()->document(), m_mode);
285    SelectorChecker::SelectorCheckingContext context(ruleData.selector(), m_context.element(), SelectorChecker::VisitedMatchEnabled);
286    context.elementStyle = m_style.get();
287    context.scope = scope;
288    context.pseudoId = m_pseudoStyleRequest.pseudoId;
289    context.scrollbar = m_pseudoStyleRequest.scrollbar;
290    context.scrollbarPart = m_pseudoStyleRequest.scrollbarPart;
291    context.behaviorAtBoundary = behaviorAtBoundary;
292    SelectorChecker::Match match = selectorChecker.match(context, DOMSiblingTraversalStrategy(), result);
293    if (match != SelectorChecker::SelectorMatches)
294        return false;
295    if (m_pseudoStyleRequest.pseudoId != NOPSEUDO && m_pseudoStyleRequest.pseudoId != result->dynamicPseudo)
296        return false;
297    return true;
298}
299
300void ElementRuleCollector::collectRuleIfMatches(const RuleData& ruleData, SelectorChecker::BehaviorAtBoundary behaviorAtBoundary, CascadeScope cascadeScope, CascadeOrder cascadeOrder, const MatchRequest& matchRequest, RuleRange& ruleRange)
301{
302    if (m_canUseFastReject && m_selectorFilter.fastRejectSelector<RuleData::maximumIdentifierCount>(ruleData.descendantSelectorIdentifierHashes()))
303        return;
304
305    StyleRule* rule = ruleData.rule();
306    SelectorChecker::MatchResult result;
307    if (ruleMatches(ruleData, matchRequest.scope, behaviorAtBoundary, &result)) {
308        // If the rule has no properties to apply, then ignore it in the non-debug mode.
309        const StylePropertySet* properties = rule->properties();
310        if (!properties || (properties->isEmpty() && !matchRequest.includeEmptyRules))
311            return;
312        // FIXME: Exposing the non-standard getMatchedCSSRules API to web is the only reason this is needed.
313        if (m_sameOriginOnly && !ruleData.hasDocumentSecurityOrigin())
314            return;
315
316        PseudoId dynamicPseudo = result.dynamicPseudo;
317        // If we're matching normal rules, set a pseudo bit if
318        // we really just matched a pseudo-element.
319        if (dynamicPseudo != NOPSEUDO && m_pseudoStyleRequest.pseudoId == NOPSEUDO) {
320            if (m_mode == SelectorChecker::CollectingCSSRules || m_mode == SelectorChecker::CollectingStyleRules)
321                return;
322            // FIXME: Matching should not modify the style directly.
323            if (m_style && dynamicPseudo < FIRST_INTERNAL_PSEUDOID)
324                m_style->setHasPseudoStyle(dynamicPseudo);
325        } else {
326            // Update our first/last rule indices in the matched rules array.
327            ++ruleRange.lastRuleIndex;
328            if (ruleRange.firstRuleIndex == -1)
329                ruleRange.firstRuleIndex = ruleRange.lastRuleIndex;
330
331            // Add this rule to our list of matched rules.
332            addMatchedRule(&ruleData, result.specificity, cascadeScope, cascadeOrder, matchRequest.styleSheetIndex);
333            return;
334        }
335    }
336}
337
338void ElementRuleCollector::collectMatchingRulesForList(const RuleData* rules, SelectorChecker::BehaviorAtBoundary behaviorAtBoundary, CascadeScope cascadeScope, CascadeOrder cascadeOrder, const MatchRequest& matchRequest, RuleRange& ruleRange)
339{
340    if (!rules)
341        return;
342    while (!rules->isLastInArray())
343        collectRuleIfMatches(*rules++, behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
344    collectRuleIfMatches(*rules, behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
345}
346
347void ElementRuleCollector::collectMatchingRulesForList(const Vector<RuleData>* rules, SelectorChecker::BehaviorAtBoundary behaviorAtBoundary, CascadeScope cascadeScope, CascadeOrder cascadeOrder, const MatchRequest& matchRequest, RuleRange& ruleRange)
348{
349    if (!rules)
350        return;
351    unsigned size = rules->size();
352    for (unsigned i = 0; i < size; ++i)
353        collectRuleIfMatches(rules->at(i), behaviorAtBoundary, cascadeScope, cascadeOrder, matchRequest, ruleRange);
354}
355
356static inline bool compareRules(const MatchedRule& matchedRule1, const MatchedRule& matchedRule2)
357{
358    if (matchedRule1.cascadeScope() != matchedRule2.cascadeScope())
359        return matchedRule1.cascadeScope() > matchedRule2.cascadeScope();
360
361    unsigned specificity1 = matchedRule1.specificity();
362    unsigned specificity2 = matchedRule2.specificity();
363    if (specificity1 != specificity2)
364        return specificity1 < specificity2;
365
366    if (matchedRule1.styleSheetIndex() != matchedRule2.styleSheetIndex())
367        return matchedRule1.styleSheetIndex() < matchedRule2.styleSheetIndex();
368
369    return matchedRule1.position() < matchedRule2.position();
370}
371
372void ElementRuleCollector::sortMatchedRules()
373{
374    ASSERT(m_matchedRules);
375    std::sort(m_matchedRules->begin(), m_matchedRules->end(), compareRules);
376}
377
378bool ElementRuleCollector::hasAnyMatchingRules(RuleSet* ruleSet)
379{
380    clearMatchedRules();
381
382    m_mode = SelectorChecker::SharingRules;
383    // To check whether a given RuleSet has any rule matching a given element,
384    // should not see the element's treescope. Because RuleSet has no
385    // information about "scope".
386    int firstRuleIndex = -1, lastRuleIndex = -1;
387    RuleRange ruleRange(firstRuleIndex, lastRuleIndex);
388    // FIXME: Verify whether it's ok to ignore CascadeScope here.
389    collectMatchingRules(MatchRequest(ruleSet), ruleRange, SelectorChecker::StaysWithinTreeScope);
390
391    return m_matchedRules && !m_matchedRules->isEmpty();
392}
393
394} // namespace WebCore
395