Diff
Modified: trunk/Source/WebCore/ChangeLog (287771 => 287772)
--- trunk/Source/WebCore/ChangeLog 2022-01-07 19:34:59 UTC (rev 287771)
+++ trunk/Source/WebCore/ChangeLog 2022-01-07 19:38:44 UTC (rev 287772)
@@ -1,3 +1,48 @@
+2022-01-07 Antti Koivisto <[email protected]>
+
+ Make separate invalidation rulesets for negated selectors (inside :not())
+ https://bugs.webkit.org/show_bug.cgi?id=234959
+
+ Reviewed by Darin Adler.
+
+ Use this information to reduce traversal on class changes. Other mutations will follow.
+
+ * style/ClassChangeInvalidation.cpp:
+ (WebCore::Style::collectClasses):
+ (WebCore::Style::computeClassChanges):
+ (WebCore::Style::ClassChangeInvalidation::computeInvalidation):
+
+ Adding a class can only make a regular selector (not inside :not()) start matching.
+ Adding a class can only make a negated selector (inside :not()) stop matching.
+ We only need to invalidate for the first case after the mutation has happened and for the second
+ case before it happens.
+
+ These are reversed when removing a class.
+
+ (WebCore::Style::ClassChangeInvalidation::invalidateBeforeChange):
+ (WebCore::Style::ClassChangeInvalidation::invalidateAfterChange):
+ (WebCore::Style::computeClassChange): Deleted.
+ (WebCore::Style::ClassChangeInvalidation::invalidateStyleWithRuleSets): Deleted.
+ * style/ClassChangeInvalidation.h:
+ (WebCore::Style::ClassChangeInvalidation::ClassChangeInvalidation):
+ (WebCore::Style::ClassChangeInvalidation::~ClassChangeInvalidation):
+ * style/RuleFeature.cpp:
+ (WebCore::Style::RuleFeature::RuleFeature):
+ (WebCore::Style::RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector):
+ (WebCore::Style::RuleFeatureSet::recursivelyCollectFeaturesFromSelector):
+
+ Compute the negation state. :not(foo) is negated, :not(:not(foo)) isn't.
+
+ (WebCore::Style::RuleFeatureSet::collectFeatures):
+ * style/RuleFeature.h:
+ (WebCore::Style::RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector): Deleted.
+ * style/StyleScopeRuleSets.cpp:
+ (WebCore::Style::ensureInvalidationRuleSets):
+
+ Make separate ruleset.
+
+ * style/StyleScopeRuleSets.h:
+
2022-01-07 Gabriel Nava Marino <[email protected]>
nullptr deref in ComputeFloatOffsetForLineLayoutAdapter<FloatingObject::FloatLeft>::updateOffsetIfNeeded
Modified: trunk/Source/WebCore/style/ClassChangeInvalidation.cpp (287771 => 287772)
--- trunk/Source/WebCore/style/ClassChangeInvalidation.cpp 2022-01-07 19:34:59 UTC (rev 287771)
+++ trunk/Source/WebCore/style/ClassChangeInvalidation.cpp 2022-01-07 19:38:44 UTC (rev 287772)
@@ -34,26 +34,33 @@
namespace WebCore {
namespace Style {
-using ClassChangeVector = Vector<AtomStringImpl*, 4>;
+enum class ClassChangeType : bool { Add, Remove };
-static ClassChangeVector collectClasses(const SpaceSplitString& classes)
+struct ClassChange {
+ AtomStringImpl* className { };
+ ClassChangeType type;
+};
+
+using ClassChangeVector = Vector<ClassChange, 4>;
+
+static ClassChangeVector collectClasses(const SpaceSplitString& classes, ClassChangeType changeType)
{
ClassChangeVector result;
result.reserveCapacity(classes.size());
for (unsigned i = 0; i < classes.size(); ++i)
- result.uncheckedAppend(classes[i].impl());
+ result.uncheckedAppend({ classes[i].impl(), changeType });
return result;
}
-static ClassChangeVector computeClassChange(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses)
+static ClassChangeVector computeClassChanges(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses)
{
unsigned oldSize = oldClasses.size();
unsigned newSize = newClasses.size();
if (!oldSize)
- return collectClasses(newClasses);
+ return collectClasses(newClasses, ClassChangeType::Add);
if (!newSize)
- return collectClasses(oldClasses);
+ return collectClasses(oldClasses, ClassChangeType::Remove);
ClassChangeVector changedClasses;
@@ -70,13 +77,13 @@
}
if (foundFromBoth)
continue;
- changedClasses.append(newClasses[i].impl());
+ changedClasses.append({ newClasses[i].impl(), ClassChangeType::Add });
}
for (unsigned i = 0; i < oldSize; ++i) {
// If the bit is not set the corresponding class has been removed.
if (remainingClassBits.quickGet(i))
continue;
- changedClasses.append(oldClasses[i].impl());
+ changedClasses.append({ oldClasses[i].impl(), ClassChangeType::Remove });
}
return changedClasses;
@@ -84,16 +91,16 @@
void ClassChangeInvalidation::computeInvalidation(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses)
{
- auto changedClasses = computeClassChange(oldClasses, newClasses);
+ auto classChanges = computeClassChanges(oldClasses, newClasses);
bool shouldInvalidateCurrent = false;
bool mayAffectStyleInShadowTree = false;
traverseRuleFeatures(m_element, [&] (const RuleFeatureSet& features, bool mayAffectShadowTree) {
- for (auto* changedClass : changedClasses) {
- if (mayAffectShadowTree && features.classRules.contains(changedClass))
+ for (auto& classChange : classChanges) {
+ if (mayAffectShadowTree && features.classRules.contains(classChange.className))
mayAffectStyleInShadowTree = true;
- if (features.classesAffectingHost.contains(changedClass))
+ if (features.classesAffectingHost.contains(classChange.className))
shouldInvalidateCurrent = true;
}
});
@@ -108,18 +115,33 @@
auto& ruleSets = m_element.styleResolver().ruleSets();
- for (auto* changedClass : changedClasses) {
- if (auto* invalidationRuleSets = ruleSets.classInvalidationRuleSets(changedClass)) {
- for (auto& invalidationRuleSet : *invalidationRuleSets)
- Invalidator::addToMatchElementRuleSets(m_matchElementRuleSets, invalidationRuleSet);
+ auto invalidateBeforeChange = [](ClassChangeType type, IsNegation isNegation) {
+ if (type == ClassChangeType::Remove)
+ return isNegation == IsNegation::No;
+ return isNegation == IsNegation::Yes;
+ };
+
+ for (auto& classChange : classChanges) {
+ if (auto* invalidationRuleSets = ruleSets.classInvalidationRuleSets(classChange.className)) {
+ for (auto& invalidationRuleSet : *invalidationRuleSets) {
+ if (invalidateBeforeChange(classChange.type, invalidationRuleSet.isNegation))
+ Invalidator::addToMatchElementRuleSets(m_beforeChangeRuleSets, invalidationRuleSet);
+ else
+ Invalidator::addToMatchElementRuleSets(m_afterChangeRuleSets, invalidationRuleSet);
+ }
}
}
}
-void ClassChangeInvalidation::invalidateStyleWithRuleSets()
+void ClassChangeInvalidation::invalidateBeforeChange()
{
- Invalidator::invalidateWithMatchElementRuleSets(m_element, m_matchElementRuleSets);
+ Invalidator::invalidateWithMatchElementRuleSets(m_element, m_beforeChangeRuleSets);
}
+void ClassChangeInvalidation::invalidateAfterChange()
+{
+ Invalidator::invalidateWithMatchElementRuleSets(m_element, m_afterChangeRuleSets);
}
+
}
+}
Modified: trunk/Source/WebCore/style/ClassChangeInvalidation.h (287771 => 287772)
--- trunk/Source/WebCore/style/ClassChangeInvalidation.h 2022-01-07 19:34:59 UTC (rev 287771)
+++ trunk/Source/WebCore/style/ClassChangeInvalidation.h 2022-01-07 19:38:44 UTC (rev 287772)
@@ -42,12 +42,14 @@
private:
void computeInvalidation(const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses);
- void invalidateStyleWithRuleSets();
+ void invalidateBeforeChange();
+ void invalidateAfterChange();
const bool m_isEnabled;
Element& m_element;
- Invalidator::MatchElementRuleSets m_matchElementRuleSets;
+ Invalidator::MatchElementRuleSets m_beforeChangeRuleSets;
+ Invalidator::MatchElementRuleSets m_afterChangeRuleSets;
};
inline ClassChangeInvalidation::ClassChangeInvalidation(Element& element, const SpaceSplitString& oldClasses, const SpaceSplitString& newClasses)
@@ -58,7 +60,7 @@
if (!m_isEnabled)
return;
computeInvalidation(oldClasses, newClasses);
- invalidateStyleWithRuleSets();
+ invalidateBeforeChange();
}
inline ClassChangeInvalidation::~ClassChangeInvalidation()
@@ -65,7 +67,7 @@
{
if (!m_isEnabled)
return;
- invalidateStyleWithRuleSets();
+ invalidateAfterChange();
}
}
Modified: trunk/Source/WebCore/style/RuleFeature.cpp (287771 => 287772)
--- trunk/Source/WebCore/style/RuleFeature.cpp 2022-01-07 19:34:59 UTC (rev 287771)
+++ trunk/Source/WebCore/style/RuleFeature.cpp 2022-01-07 19:38:44 UTC (rev 287772)
@@ -84,12 +84,19 @@
}
-RuleFeature::RuleFeature(const RuleData& ruleData, MatchElement matchElement)
+RuleFeature::RuleFeature(const RuleData& ruleData, MatchElement matchElement, IsNegation isNegation)
: RuleAndSelector(ruleData)
, matchElement(matchElement)
+ , isNegation(isNegation)
{
}
+RuleFeatureWithInvalidationSelector::RuleFeatureWithInvalidationSelector(const RuleData& data, MatchElement matchElement, IsNegation isNegation, const CSSSelector* invalidationSelector)
+ : RuleFeature(data, matchElement, isNegation)
+ , invalidationSelector(invalidationSelector)
+{
+}
+
static MatchElement computeNextMatchElement(MatchElement matchElement, CSSSelector::RelationType relation)
{
if (isHasPseudoClassMatchElement(matchElement))
@@ -200,7 +207,7 @@
return matchElement;
};
-void RuleFeatureSet::recursivelyCollectFeaturesFromSelector(SelectorFeatures& selectorFeatures, const CSSSelector& firstSelector, MatchElement matchElement)
+void RuleFeatureSet::recursivelyCollectFeaturesFromSelector(SelectorFeatures& selectorFeatures, const CSSSelector& firstSelector, MatchElement matchElement, IsNegation isNegation)
{
const CSSSelector* selector = &firstSelector;
do {
@@ -209,18 +216,18 @@
if (matchElement == MatchElement::Parent || matchElement == MatchElement::Ancestor)
idsMatchingAncestorsInRules.add(selector->value());
else if (isHasPseudoClassMatchElement(matchElement))
- selectorFeatures.ids.append(std::make_pair(selector->value(), matchElement));
+ selectorFeatures.ids.append({ selector->value(), matchElement, isNegation });
} else if (selector->match() == CSSSelector::Class)
- selectorFeatures.classes.append(std::make_pair(selector->value(), matchElement));
+ selectorFeatures.classes.append({ selector->value(), matchElement, isNegation });
else if (selector->match() == CSSSelector::Tag) {
if (isHasPseudoClassMatchElement(matchElement))
- selectorFeatures.tags.append(std::make_pair(selector->tagLowercaseLocalName(), matchElement));
+ selectorFeatures.tags.append({ selector->tagLowercaseLocalName(), matchElement, isNegation });
} else if (selector->isAttributeSelector()) {
auto& canonicalLocalName = selector->attributeCanonicalLocalName();
auto& localName = selector->attribute().localName();
attributeCanonicalLocalNamesInRules.add(canonicalLocalName);
attributeLocalNamesInRules.add(localName);
- selectorFeatures.attributes.append(std::make_pair(selector, matchElement));
+ selectorFeatures.attributes.append({ selector, matchElement, isNegation });
} else if (selector->match() == CSSSelector::PseudoElement) {
switch (selector->pseudoElementType()) {
case CSSSelector::PseudoElementFirstLine:
@@ -234,7 +241,7 @@
}
} else if (selector->match() == CSSSelector::PseudoClass) {
if (!isLogicalCombinationPseudoClass(selector->pseudoClassType()))
- selectorFeatures.pseudoClasses.append(std::make_pair(selector, matchElement));
+ selectorFeatures.pseudoClasses.append({ selector, matchElement, isNegation });
}
if (!selectorFeatures.hasSiblingSelector && selector->isSiblingSelector())
@@ -241,11 +248,15 @@
selectorFeatures.hasSiblingSelector = true;
if (const CSSSelectorList* selectorList = selector->selectorList()) {
+ auto subSelectorIsNegation = isNegation;
+ if (selector->match() == CSSSelector::PseudoClass && selector->pseudoClassType() == CSSSelector::PseudoClassNot)
+ subSelectorIsNegation = isNegation == IsNegation::No ? IsNegation::Yes : IsNegation::No;
+
for (const CSSSelector* subSelector = selectorList->first(); subSelector; subSelector = CSSSelectorList::next(subSelector)) {
auto subSelectorMatchElement = computeSubSelectorMatchElement(matchElement, *selector, *subSelector);
if (!selectorFeatures.hasSiblingSelector && selector->isSiblingSelector())
selectorFeatures.hasSiblingSelector = true;
- recursivelyCollectFeaturesFromSelector(selectorFeatures, *subSelector, subSelectorMatchElement);
+ recursivelyCollectFeaturesFromSelector(selectorFeatures, *subSelector, subSelectorMatchElement, subSelectorIsNegation);
}
}
@@ -306,10 +317,10 @@
auto addToMap = [&](auto& map, auto& entries, auto hostAffectingNames) {
for (auto& entry : entries) {
- auto& [name, matchElement] = entry;
+ auto& [name, matchElement, isNegation] = entry;
map.ensure(name, [] {
return makeUnique<RuleFeatureVector>();
- }).iterator->value->append({ ruleData, matchElement });
+ }).iterator->value->append({ ruleData, matchElement, isNegation });
setUsesMatchElement(matchElement);
@@ -324,23 +335,21 @@
addToMap(idRules, selectorFeatures.ids, nullptr);
addToMap(classRules, selectorFeatures.classes, &classesAffectingHost);
- for (auto& selectorAndMatch : selectorFeatures.attributes) {
- auto* selector = selectorAndMatch.first;
- auto matchElement = selectorAndMatch.second;
+ for (auto& entry : selectorFeatures.attributes) {
+ auto [selector, matchElement, isNegation] = entry;
attributeRules.ensure(selector->attribute().localName().convertToASCIILowercase(), [] {
return makeUnique<Vector<RuleFeatureWithInvalidationSelector>>();
- }).iterator->value->append({ ruleData, matchElement, selector });
+ }).iterator->value->append({ ruleData, matchElement, isNegation, selector });
if (matchElement == MatchElement::Host)
attributesAffectingHost.add(selector->attribute().localName().convertToASCIILowercase());
setUsesMatchElement(matchElement);
}
- for (auto& selectorAndMatch : selectorFeatures.pseudoClasses) {
- auto* selector = selectorAndMatch.first;
- auto matchElement = selectorAndMatch.second;
+ for (auto& entry : selectorFeatures.pseudoClasses) {
+ auto [selector, matchElement, isNegation] = entry;
pseudoClassRules.ensure(makePseudoClassInvalidationKey(*selector), [] {
return makeUnique<Vector<RuleFeature>>();
- }).iterator->value->append({ ruleData, matchElement });
+ }).iterator->value->append({ ruleData, matchElement, isNegation });
if (matchElement == MatchElement::Host)
pseudoClassesAffectingHost.add(selector->pseudoClassType());
Modified: trunk/Source/WebCore/style/RuleFeature.h (287771 => 287772)
--- trunk/Source/WebCore/style/RuleFeature.h 2022-01-07 19:34:59 UTC (rev 287771)
+++ trunk/Source/WebCore/style/RuleFeature.h 2022-01-07 19:38:44 UTC (rev 287772)
@@ -55,6 +55,8 @@
};
constexpr unsigned matchElementCount = static_cast<unsigned>(MatchElement::Host) + 1;
+enum class IsNegation : bool { No, Yes };
+
// For MSVC.
#pragma pack(push, 4)
struct RuleAndSelector {
@@ -66,17 +68,15 @@
};
struct RuleFeature : public RuleAndSelector {
- RuleFeature(const RuleData&, MatchElement);
+ RuleFeature(const RuleData&, MatchElement, IsNegation);
MatchElement matchElement;
+ IsNegation isNegation; // Whether the selector is in a (non-paired) :not() context.
};
static_assert(sizeof(RuleFeature) <= 16, "RuleFeature is a frquently alocated object. Keep it small.");
struct RuleFeatureWithInvalidationSelector : public RuleFeature {
- RuleFeatureWithInvalidationSelector(const RuleData& data, MatchElement matchElement, const CSSSelector* invalidationSelector = nullptr)
- : RuleFeature(data, matchElement)
- , invalidationSelector(invalidationSelector)
- { }
+ RuleFeatureWithInvalidationSelector(const RuleData&, MatchElement, IsNegation, const CSSSelector* invalidationSelector);
const CSSSelector* invalidationSelector { nullptr };
};
@@ -124,13 +124,13 @@
struct SelectorFeatures {
bool hasSiblingSelector { false };
- Vector<std::pair<AtomString, MatchElement>, 32> tags;
- Vector<std::pair<AtomString, MatchElement>, 32> ids;
- Vector<std::pair<AtomString, MatchElement>, 32> classes;
- Vector<std::pair<const CSSSelector*, MatchElement>, 32> attributes;
- Vector<std::pair<const CSSSelector*, MatchElement>, 32> pseudoClasses;
+ Vector<std::tuple<AtomString, MatchElement, IsNegation>, 32> tags;
+ Vector<std::tuple<AtomString, MatchElement, IsNegation>, 32> ids;
+ Vector<std::tuple<AtomString, MatchElement, IsNegation>, 32> classes;
+ Vector<std::tuple<const CSSSelector*, MatchElement, IsNegation>, 32> attributes;
+ Vector<std::tuple<const CSSSelector*, MatchElement, IsNegation>, 32> pseudoClasses;
};
- void recursivelyCollectFeaturesFromSelector(SelectorFeatures&, const CSSSelector&, MatchElement = MatchElement::Subject);
+ void recursivelyCollectFeaturesFromSelector(SelectorFeatures&, const CSSSelector&, MatchElement = MatchElement::Subject, IsNegation = IsNegation::No);
};
bool isHasPseudoClassMatchElement(MatchElement);
Modified: trunk/Source/WebCore/style/StyleScopeRuleSets.cpp (287771 => 287772)
--- trunk/Source/WebCore/style/StyleScopeRuleSets.cpp 2022-01-07 19:34:59 UTC (rev 287771)
+++ trunk/Source/WebCore/style/StyleScopeRuleSets.cpp 2022-01-07 19:38:44 UTC (rev 287772)
@@ -240,37 +240,34 @@
if (!features)
return nullptr;
- std::array<RefPtr<RuleSet>, matchElementCount> matchElementArray;
- std::array<Vector<const CSSSelector*>, matchElementCount> invalidationSelectorArray;
+ HashMap<std::tuple<uint8_t, bool, bool>, InvalidationRuleSet> invalidationRuleSetMap;
+
for (auto& feature : *features) {
- auto arrayIndex = static_cast<unsigned>(feature.matchElement);
- RELEASE_ASSERT(arrayIndex < matchElementArray.size());
+ auto key = std::tuple { static_cast<uint8_t>(feature.matchElement), static_cast<bool>(feature.isNegation), true };
- auto& ruleSet = matchElementArray[arrayIndex];
- if (!ruleSet)
- ruleSet = RuleSet::create();
- ruleSet->addRule(*feature.styleRule, feature.selectorIndex, feature.selectorListIndex);
+ auto& invalidationRuleSet = invalidationRuleSetMap.ensure(key, [&] {
+ return InvalidationRuleSet {
+ RuleSet::create(),
+ { },
+ feature.matchElement,
+ feature.isNegation,
+ };
+ }).iterator->value;
+
+ invalidationRuleSet.ruleSet->addRule(*feature.styleRule, feature.selectorIndex, feature.selectorListIndex);
+
if constexpr (std::is_same<typename RuleFeatureVectorType::ValueType, RuleFeatureWithInvalidationSelector>::value) {
if (feature.invalidationSelector)
- invalidationSelectorArray[arrayIndex].append(feature.invalidationSelector);
+ invalidationRuleSet.invalidationSelectors.append(feature.invalidationSelector);
}
}
- unsigned ruleSetCount = 0;
- for (const auto& item : matchElementArray) {
- if (item)
- ++ruleSetCount;
- }
-
auto invalidationRuleSets = makeUnique<Vector<InvalidationRuleSet>>();
- invalidationRuleSets->reserveInitialCapacity(ruleSetCount);
+ invalidationRuleSets->reserveInitialCapacity(invalidationRuleSetMap.size());
- for (unsigned i = 0; i < matchElementArray.size(); ++i) {
- if (matchElementArray[i]) {
- matchElementArray[i]->shrinkToFit();
- invalidationRuleSets->uncheckedAppend({ static_cast<MatchElement>(i), matchElementArray[i].releaseNonNull(), WTFMove(invalidationSelectorArray[i]) });
- }
- }
+ for (auto& invalidationRuleSet : invalidationRuleSetMap.values())
+ invalidationRuleSets->uncheckedAppend(WTFMove(invalidationRuleSet));
+
return invalidationRuleSets;
}).iterator->value.get();
}
Modified: trunk/Source/WebCore/style/StyleScopeRuleSets.h (287771 => 287772)
--- trunk/Source/WebCore/style/StyleScopeRuleSets.h 2022-01-07 19:34:59 UTC (rev 287771)
+++ trunk/Source/WebCore/style/StyleScopeRuleSets.h 2022-01-07 19:38:44 UTC (rev 287772)
@@ -43,11 +43,10 @@
class Resolver;
struct InvalidationRuleSet {
+ RefPtr<RuleSet> ruleSet;
+ Vector<const CSSSelector*> invalidationSelectors;
MatchElement matchElement;
- Ref<RuleSet> ruleSet;
- Vector<const CSSSelector*> invalidationSelectors;
-
- WTF_MAKE_FAST_ALLOCATED;
+ IsNegation isNegation;
};
class ScopeRuleSets {
