source: webkit/trunk/Source/WebCore/css/SelectorChecker.h

Last change on this file was 288012, checked in by Antti Koivisto, 3 years ago

[:has() pseudo-class] Avoid O(n2) in style invalidation with repeated DOM mutations
https://bugs.webkit.org/show_bug.cgi?id=234842
<rdar://problem/87397176>

Reviewed by Dean Jackson.

LayoutTests/imported/w3c:

  • web-platform-tests/css/selectors/invalidation/has-complexity-expected.txt: Added.
  • web-platform-tests/css/selectors/invalidation/has-complexity.html: Added.

Source/WebCore:

Use invalidation selectors to check if a given mutation needs :has() invalidation.

Test: imported/w3c/web-platform-tests/css/selectors/invalidation/has-complexity.html

  • css/SelectorChecker.cpp:

(WebCore::SelectorChecker::checkOne const):

  • css/SelectorChecker.h:
  • style/ChildChangeInvalidation.cpp:

(WebCore::Style::ChildChangeInvalidation::invalidateForChangedElement):

Invalidate only if the invalidation ruleset has an invalidation selector that matches
the added/removed element. Even in that case we only need to invalidate if that selector
has not already matched within this parent.

As we don't have persistent state that would remember what already matched accross multiple
mutations, approximate this by checking if the closest sibling matched.

(WebCore::Style::ChildChangeInvalidation::invalidateForHasBeforeMutation):
(WebCore::Style::ChildChangeInvalidation::invalidateForHasAfterMutation):

  • style/ChildChangeInvalidation.h:

LayoutTests:

  • Property svn:eol-style set to native
File size: 5.5 KB
Line 
1/*
2 * Copyright (C) 1999 Lars Knoll ([email protected])
3 * (C) 2004-2005 Allan Sandfeld Jensen ([email protected])
4 * Copyright (C) 2006, 2007 Nicholas Shanks ([email protected])
5 * Copyright (C) 2005-2016 Apple Inc. All rights reserved.
6 * Copyright (C) 2007 Alexey Proskuryakov <[email protected]>
7 * Copyright (C) 2007, 2008 Eric Seidel <[email protected]>
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 *
12 * This library is free software; you can redistribute it and/or
13 * modify it under the terms of the GNU Library General Public
14 * License as published by the Free Software Foundation; either
15 * version 2 of the License, or (at your option) any later version.
16 *
17 * This library is distributed in the hope that it will be useful,
18 * but WITHOUT ANY WARRANTY; without even the implied warranty of
19 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
20 * Library General Public License for more details.
21 *
22 * You should have received a copy of the GNU Library General Public License
23 * along with this library; see the file COPYING.LIB. If not, write to
24 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
25 * Boston, MA 02110-1301, USA.
26 */
27
28#pragma once
29
30#include "CSSSelector.h"
31#include "Element.h"
32#include "SelectorMatchingState.h"
33#include "StyleRelations.h"
34#include "StyleScopeOrdinal.h"
35
36namespace WebCore {
37
38class CSSSelector;
39class Element;
40class RenderScrollbar;
41class RenderStyle;
42
43struct StyleScrollbarState {
44 ScrollbarPart scrollbarPart { NoPart };
45 ScrollbarPart hoveredPart { NoPart };
46 ScrollbarPart pressedPart { NoPart };
47 ScrollbarOrientation orientation { ScrollbarOrientation::Vertical };
48 ScrollbarButtonsPlacement buttonsPlacement { ScrollbarButtonsNone };
49 bool enabled { false };
50 bool scrollCornerIsVisible { false };
51};
52
53class SelectorChecker {
54 WTF_MAKE_NONCOPYABLE(SelectorChecker);
55 enum class Match { SelectorMatches, SelectorFailsLocally, SelectorFailsAllSiblings, SelectorFailsCompletely };
56
57 enum class MatchType { VirtualPseudoElementOnly, Element };
58
59 struct MatchResult {
60 Match match;
61 MatchType matchType;
62
63 static MatchResult matches(MatchType matchType)
64 {
65 return { Match::SelectorMatches, matchType };
66 }
67
68 static MatchResult updateWithMatchType(MatchResult result, MatchType matchType)
69 {
70 if (matchType == MatchType::VirtualPseudoElementOnly)
71 result.matchType = MatchType::VirtualPseudoElementOnly;
72 return result;
73 }
74
75 static MatchResult fails(Match match)
76 {
77 return { match, MatchType::Element };
78 }
79 };
80
81public:
82 enum class Mode : unsigned char {
83 ResolvingStyle = 0, CollectingRules, CollectingRulesIgnoringVirtualPseudoElements, QueryingRules
84 };
85
86 SelectorChecker(Document&);
87
88 struct CheckingContext {
89 CheckingContext(SelectorChecker::Mode resolvingMode)
90 : resolvingMode(resolvingMode)
91 { }
92
93 const SelectorChecker::Mode resolvingMode;
94 PseudoId pseudoId { PseudoId::None };
95 std::optional<StyleScrollbarState> scrollbarState;
96 AtomString nameForHightlightPseudoElement;
97 const ContainerNode* scope { nullptr };
98 bool matchesAllScopes { false };
99 Style::ScopeOrdinal styleScopeOrdinal { Style::ScopeOrdinal::Element };
100 Style::SelectorMatchingState* selectorMatchingState { nullptr };
101
102 // FIXME: It would be nicer to have a separate object for return values. This requires some more work in the selector compiler.
103 Style::Relations styleRelations;
104 PseudoIdSet pseudoIDSet;
105 bool matchedInsideScope { false };
106 };
107
108 bool match(const CSSSelector&, const Element&, CheckingContext&) const;
109
110 bool matchHostPseudoClass(const CSSSelector&, const Element&, CheckingContext&) const;
111
112 static bool isCommonPseudoClassSelector(const CSSSelector*);
113 static bool attributeSelectorMatches(const Element&, const QualifiedName&, const AtomString& attributeValue, const CSSSelector&);
114
115 enum LinkMatchMask { MatchDefault = 0, MatchLink = 1, MatchVisited = 2, MatchAll = MatchLink | MatchVisited };
116 static unsigned determineLinkMatchType(const CSSSelector*);
117
118 struct LocalContext;
119
120private:
121 MatchResult matchRecursively(CheckingContext&, const LocalContext&, PseudoIdSet&) const;
122 bool checkOne(CheckingContext&, const LocalContext&, MatchType&) const;
123 bool matchSelectorList(CheckingContext&, const LocalContext&, const Element&, const CSSSelectorList&) const;
124 bool matchHasPseudoClass(CheckingContext&, const Element&, const CSSSelector&) const;
125
126 bool checkScrollbarPseudoClass(const CheckingContext&, const Element&, const CSSSelector&) const;
127
128 bool m_strictParsing;
129 bool m_documentIsHTML;
130};
131
132inline bool SelectorChecker::isCommonPseudoClassSelector(const CSSSelector* selector)
133{
134 if (selector->match() != CSSSelector::PseudoClass)
135 return false;
136 CSSSelector::PseudoClassType pseudoType = selector->pseudoClassType();
137 return pseudoType == CSSSelector::PseudoClassLink
138 || pseudoType == CSSSelector::PseudoClassAnyLink
139 || pseudoType == CSSSelector::PseudoClassAnyLinkDeprecated
140 || pseudoType == CSSSelector::PseudoClassVisited
141 || pseudoType == CSSSelector::PseudoClassFocus;
142}
143
144} // namespace WebCore
Note: See TracBrowser for help on using the repository browser.