LibWeb: Add a simple StyleInvalidator class

This patch adds a simple, naive & inefficient class for document-wide
style invalidation, e.g. after element attribute updates. During
construction it collects a HashMap of a document's elements and their
matching rules, during destruction it does the same and then compares
the results; dirtying all elements that have a different number or order
of matching rules afterwards.

Much room for improvement, but it solves the problem of stale element
styling after attribute updates for now :^)

Fixes #4404.

6 files changed, 142 insertions, 16 deletions

diff --git a/Libraries/LibWeb/CMakeLists.txt b/Libraries/LibWeb/CMakeLists.txt
index be8563cad5..a7cba5633b 100644
--- a/Libraries/LibWeb/CMakeLists.txt
+++ b/Libraries/LibWeb/CMakeLists.txt
@@ -23,6 +23,7 @@ set(SOURCES
     CSS/Selector.cpp
     CSS/SelectorEngine.cpp
     CSS/StyleDeclaration.cpp
+    CSS/StyleInvalidator.cpp
     CSS/StyleProperties.cpp
     CSS/StyleResolver.cpp
     CSS/StyleRule.cpp
diff --git a/Libraries/LibWeb/CSS/StyleInvalidator.cpp b/Libraries/LibWeb/CSS/StyleInvalidator.cpp
new file mode 100644
index 0000000000..0dd48840d5
--- /dev/null
+++ b/Libraries/LibWeb/CSS/StyleInvalidator.cpp
@@ -0,0 +1,70 @@
+/*
+ * Copyright (c) 2020, Linus Groh <mail@linusgroh.de>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <LibWeb/CSS/StyleInvalidator.h>
+#include <LibWeb/DOM/Document.h>
+#include <LibWeb/DOM/Element.h>
+
+namespace Web::CSS {
+
+StyleInvalidator::StyleInvalidator(DOM::Document& document)
+    : m_document(document)
+{
+    auto& style_resolver = m_document.style_resolver();
+    m_document.for_each_in_subtree_of_type<DOM::Element>([&](auto& element) {
+        m_elements_and_matching_rules_before.set(&element, style_resolver.collect_matching_rules(element));
+        return IterationDecision::Continue;
+    });
+}
+
+StyleInvalidator::~StyleInvalidator()
+{
+    auto& style_resolver = m_document.style_resolver();
+    m_document.for_each_in_subtree_of_type<DOM::Element>([&](auto& element) {
+        auto maybe_matching_rules_before = m_elements_and_matching_rules_before.get(&element);
+        if (!maybe_matching_rules_before.has_value()) {
+            element.set_needs_style_update(true);
+            return IterationDecision::Continue;
+        }
+        auto& matching_rules_before = maybe_matching_rules_before.value();
+        auto matching_rules_after = style_resolver.collect_matching_rules(element);
+        if (matching_rules_before.size() != matching_rules_after.size()) {
+            element.set_needs_style_update(true);
+            return IterationDecision::Continue;
+        }
+        style_resolver.sort_matching_rules(matching_rules_before);
+        style_resolver.sort_matching_rules(matching_rules_after);
+        for (size_t i = 0; i < matching_rules_before.size(); ++i) {
+            if (matching_rules_before[i].rule != matching_rules_after[i].rule) {
+                element.set_needs_style_update(true);
+                break;
+            }
+        }
+        return IterationDecision::Continue;
+    });
+}
+
+}
diff --git a/Libraries/LibWeb/CSS/StyleInvalidator.h b/Libraries/LibWeb/CSS/StyleInvalidator.h
new file mode 100644
index 0000000000..aea59c8e65
--- /dev/null
+++ b/Libraries/LibWeb/CSS/StyleInvalidator.h
@@ -0,0 +1,46 @@
+/*
+ * Copyright (c) 2020, Linus Groh <mail@linusgroh.de>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are met:
+ *
+ * 1. Redistributions of source code must retain the above copyright notice, this
+ *    list of conditions and the following disclaimer.
+ *
+ * 2. Redistributions in binary form must reproduce the above copyright notice,
+ *    this list of conditions and the following disclaimer in the documentation
+ *    and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
+ * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
+ * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
+ * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
+ * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
+ * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
+ * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
+ * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#pragma once
+
+#include <AK/HashMap.h>
+#include <LibWeb/CSS/StyleResolver.h>
+#include <LibWeb/DOM/Document.h>
+#include <LibWeb/DOM/Element.h>
+
+namespace Web::CSS {
+
+class StyleInvalidator {
+public:
+    explicit StyleInvalidator(DOM::Document&);
+    ~StyleInvalidator();
+
+private:
+    DOM::Document& m_document;
+    HashMap<DOM::Element*, Vector<MatchingRule>> m_elements_and_matching_rules_before;
+};
+
+}
diff --git a/Libraries/LibWeb/CSS/StyleResolver.cpp b/Libraries/LibWeb/CSS/StyleResolver.cpp
index eee46797d3..f0bf42782e 100644
--- a/Libraries/LibWeb/CSS/StyleResolver.cpp
+++ b/Libraries/LibWeb/CSS/StyleResolver.cpp
@@ -103,6 +103,22 @@ Vector<MatchingRule> StyleResolver::collect_matching_rules(const DOM::Element& e
     return matching_rules;
 }
 
+void StyleResolver::sort_matching_rules(Vector<MatchingRule>& matching_rules) const
+{
+    quick_sort(matching_rules, [&](MatchingRule& a, MatchingRule& b) {
+        auto& a_selector = a.rule->selectors()[a.selector_index];
+        auto& b_selector = b.rule->selectors()[b.selector_index];
+        auto a_specificity = a_selector.specificity();
+        auto b_specificity = b_selector.specificity();
+        if (a_selector.specificity() == b_selector.specificity()) {
+            if (a.style_sheet_index == b.style_sheet_index)
+                return a.rule_index < b.rule_index;
+            return a.style_sheet_index < b.style_sheet_index;
+        }
+        return a_specificity < b_specificity;
+    });
+}
+
 bool StyleResolver::is_inherited_property(CSS::PropertyID property_id)
 {
     static HashTable<CSS::PropertyID> inherited_properties;
@@ -547,19 +563,7 @@ NonnullRefPtr<StyleProperties> StyleResolver::resolve_style(const DOM::Element&
     element.apply_presentational_hints(*style);
 
     auto matching_rules = collect_matching_rules(element);
-
-    quick_sort(matching_rules, [&](MatchingRule& a, MatchingRule& b) {
-        auto& a_selector = a.rule->selectors()[a.selector_index];
-        auto& b_selector = b.rule->selectors()[b.selector_index];
-        auto a_specificity = a_selector.specificity();
-        auto b_specificity = b_selector.specificity();
-        if (a_selector.specificity() == b_selector.specificity()) {
-            if (a.style_sheet_index == b.style_sheet_index)
-                return a.rule_index < b.rule_index;
-            return a.style_sheet_index < b.style_sheet_index;
-        }
-        return a_specificity < b_specificity;
-    });
+    sort_matching_rules(matching_rules);
 
     for (auto& match : matching_rules) {
         for (auto& property : match.rule->declaration().properties()) {
diff --git a/Libraries/LibWeb/CSS/StyleResolver.h b/Libraries/LibWeb/CSS/StyleResolver.h
index 4a9ab55441..1682cf9b74 100644
--- a/Libraries/LibWeb/CSS/StyleResolver.h
+++ b/Libraries/LibWeb/CSS/StyleResolver.h
@@ -51,6 +51,7 @@ public:
     NonnullRefPtr<StyleProperties> resolve_style(const DOM::Element&, const StyleProperties* parent_style) const;
 
     Vector<MatchingRule> collect_matching_rules(const DOM::Element&) const;
+    void sort_matching_rules(Vector<MatchingRule>&) const;
 
     static bool is_inherited_property(CSS::PropertyID);
 
diff --git a/Libraries/LibWeb/DOM/Element.cpp b/Libraries/LibWeb/DOM/Element.cpp
index d36e85f4f2..97691c2a6b 100644
--- a/Libraries/LibWeb/DOM/Element.cpp
+++ b/Libraries/LibWeb/DOM/Element.cpp
@@ -28,6 +28,7 @@
 #include <LibWeb/CSS/Length.h>
 #include <LibWeb/CSS/Parser/CSSParser.h>
 #include <LibWeb/CSS/PropertyID.h>
+#include <LibWeb/CSS/StyleInvalidator.h>
 #include <LibWeb/CSS/StyleResolver.h>
 #include <LibWeb/DOM/Document.h>
 #include <LibWeb/DOM/DocumentFragment.h>
@@ -83,6 +84,8 @@ String Element::attribute(const FlyString& name) const
 
 void Element::set_attribute(const FlyString& name, const String& value)
 {
+    CSS::StyleInvalidator style_invalidator(document());
+
     if (auto* attribute = find_attribute(name))
         attribute->set_value(value);
     else
@@ -93,11 +96,15 @@ void Element::set_attribute(const FlyString& name, const String& value)
 
 void Element::remove_attribute(const FlyString& name)
 {
+    CSS::StyleInvalidator style_invalidator(document());
+
     m_attributes.remove_first_matching([&](auto& attribute) { return attribute.name() == name; });
 }
 
 void Element::set_attributes(Vector<Attribute>&& attributes)
 {
+    CSS::StyleInvalidator style_invalidator(document());
+
     m_attributes = move(attributes);
 
     for (auto& attribute : m_attributes)
@@ -161,12 +168,9 @@ void Element::parse_attribute(const FlyString& name, const String& value)
         for (auto& new_class : new_classes) {
             m_classes.unchecked_append(new_class);
         }
-        set_needs_style_update(true);
     } else if (name == HTML::AttributeNames::style) {
         m_inline_style = parse_css_declaration(CSS::ParsingContext(document()), value);
         set_needs_style_update(true);
-    } else if (name == HTML::AttributeNames::id) {
-        set_needs_style_update(true);
     }
 }