LibWeb: Avoid rebuilding layout tree unless CSS display property changes

Before this, any style change that mutated a property we consider
"layout-affecting" would trigger a complete teardown and rebuild of the
layout tree.

This isn't actually necessary for the vast majority of CSS properties,
so this patch makes the invalidation a bit finer, and we now only
rebuild the layout tree when the CSS display property changes.

For other layout-affecting properties, we keep the old layout tree (if
we have one) and run the layout algorithms over that once again.
This is significantly faster, since we don't have to run all the CSS
selectors all over again.

3 files changed, 66 insertions, 53 deletions

diff --git a/Userland/Libraries/LibWeb/DOM/Document.cpp b/Userland/Libraries/LibWeb/DOM/Document.cpp
index 1e9fe1c875..ab9ee2df27 100644
--- a/Userland/Libraries/LibWeb/DOM/Document.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Document.cpp
@@ -908,13 +908,13 @@ void Document::update_layout()
     m_layout_update_timer->stop();
 }
 
-[[nodiscard]] static bool update_style_recursively(DOM::Node& node)
+[[nodiscard]] static Element::RequiredInvalidationAfterStyleChange update_style_recursively(DOM::Node& node)
 {
     bool const needs_full_style_update = node.document().needs_full_style_update();
-    bool needs_relayout = false;
+    Element::RequiredInvalidationAfterStyleChange invalidation;
 
     if (is<Element>(node)) {
-        needs_relayout |= static_cast<Element&>(node).recompute_style() == Element::NeedsRelayout::Yes;
+        invalidation |= static_cast<Element&>(node).recompute_style();
     }
     node.set_needs_style_update(false);
 
@@ -922,18 +922,18 @@ void Document::update_layout()
         if (node.is_element()) {
             if (auto* shadow_root = static_cast<DOM::Element&>(node).shadow_root_internal()) {
                 if (needs_full_style_update || shadow_root->needs_style_update() || shadow_root->child_needs_style_update())
-                    needs_relayout |= update_style_recursively(*shadow_root);
+                    invalidation |= update_style_recursively(*shadow_root);
             }
         }
         node.for_each_child([&](auto& child) {
             if (needs_full_style_update || child.needs_style_update() || child.child_needs_style_update())
-                needs_relayout |= update_style_recursively(child);
+                invalidation |= update_style_recursively(child);
             return IterationDecision::Continue;
         });
     }
 
     node.set_child_needs_style_update(false);
-    return needs_relayout;
+    return invalidation;
 }
 
 void Document::update_style()
@@ -948,8 +948,16 @@ void Document::update_style()
         return;
 
     evaluate_media_rules();
-    if (update_style_recursively(*this))
+
+    auto invalidation = update_style_recursively(*this);
+    if (invalidation.rebuild_layout_tree) {
         invalidate_layout();
+    } else {
+        if (invalidation.relayout)
+            set_needs_layout();
+        if (invalidation.rebuild_stacking_context_tree)
+            invalidate_stacking_context_tree();
+    }
     m_needs_full_style_update = false;
     m_style_update_timer->stop();
 }
diff --git a/Userland/Libraries/LibWeb/DOM/Element.cpp b/Userland/Libraries/LibWeb/DOM/Element.cpp
index 1f0d441ee8..7d5e38ee53 100644
--- a/Userland/Libraries/LibWeb/DOM/Element.cpp
+++ b/Userland/Libraries/LibWeb/DOM/Element.cpp
@@ -395,52 +395,48 @@ void Element::did_remove_attribute(DeprecatedFlyString const& name)
     }
 }
 
-enum class RequiredInvalidation {
-    None,
-    RepaintOnly,
-    RebuildStackingContextTree,
-    Relayout,
-};
-
-static RequiredInvalidation compute_required_invalidation(CSS::StyleProperties const& old_style, CSS::StyleProperties const& new_style)
+static Element::RequiredInvalidationAfterStyleChange compute_required_invalidation(CSS::StyleProperties const& old_style, CSS::StyleProperties const& new_style)
 {
+    Element::RequiredInvalidationAfterStyleChange invalidation;
+
     if (&old_style.computed_font() != &new_style.computed_font())
-        return RequiredInvalidation::Relayout;
-    bool requires_repaint = false;
-    bool requires_stacking_context_tree_rebuild = false;
+        invalidation.relayout = true;
+
     for (auto i = to_underlying(CSS::first_property_id); i <= to_underlying(CSS::last_property_id); ++i) {
         auto property_id = static_cast<CSS::PropertyID>(i);
         auto const& old_value = old_style.properties()[i];
         auto const& new_value = new_style.properties()[i];
         if (!old_value && !new_value)
             continue;
-        if (!old_value || !new_value)
-            return RequiredInvalidation::Relayout;
-        if (*old_value == *new_value)
+
+        bool const property_value_changed = (!old_value || !new_value) || *old_value != *new_value;
+        if (!property_value_changed)
             continue;
 
+        // NOTE: If the computed CSS display property changes, we have to rebuild the entire layout tree.
+        //       In the future, we should figure out ways to rebuild a smaller part of the tree.
+        if (property_id == CSS::PropertyID::Display) {
+            return Element::RequiredInvalidationAfterStyleChange::full();
+        }
+
         // OPTIMIZATION: Special handling for CSS `visibility`:
         if (property_id == CSS::PropertyID::Visibility) {
             // We don't need to relayout if the visibility changes from visible to hidden or vice versa. Only collapse requires relayout.
-            if ((old_value->to_identifier() == CSS::ValueID::Collapse) != (new_value->to_identifier() == CSS::ValueID::Collapse))
-                return RequiredInvalidation::Relayout;
+            if ((old_value && old_value->to_identifier() == CSS::ValueID::Collapse) != (new_value && new_value->to_identifier() == CSS::ValueID::Collapse))
+                invalidation.relayout = true;
             // Of course, we still have to repaint on any visibility change.
-            requires_repaint = true;
+            invalidation.repaint = true;
         } else if (CSS::property_affects_layout(property_id)) {
-            return RequiredInvalidation::Relayout;
+            invalidation.relayout = true;
         }
         if (CSS::property_affects_stacking_context(property_id))
-            requires_stacking_context_tree_rebuild = true;
-        requires_repaint = true;
+            invalidation.rebuild_stacking_context_tree = true;
+        invalidation.repaint = true;
     }
-    if (requires_stacking_context_tree_rebuild)
-        return RequiredInvalidation::RebuildStackingContextTree;
-    if (requires_repaint)
-        return RequiredInvalidation::RepaintOnly;
-    return RequiredInvalidation::None;
+    return invalidation;
 }
 
-Element::NeedsRelayout Element::recompute_style()
+Element::RequiredInvalidationAfterStyleChange Element::recompute_style()
 {
     set_needs_style_update(false);
     VERIFY(parent());
@@ -448,30 +444,25 @@ Element::NeedsRelayout Element::recompute_style()
     // FIXME propagate errors
     auto new_computed_css_values = MUST(document().style_computer().compute_style(*this));
 
-    auto required_invalidation = RequiredInvalidation::Relayout;
-
+    RequiredInvalidationAfterStyleChange invalidation;
     if (m_computed_css_values)
-        required_invalidation = compute_required_invalidation(*m_computed_css_values, *new_computed_css_values);
+        invalidation = compute_required_invalidation(*m_computed_css_values, *new_computed_css_values);
+    else
+        invalidation = RequiredInvalidationAfterStyleChange::full();
 
-    if (required_invalidation == RequiredInvalidation::None)
-        return NeedsRelayout::No;
+    if (invalidation.is_none())
+        return invalidation;
 
     m_computed_css_values = move(new_computed_css_values);
 
-    if (required_invalidation == RequiredInvalidation::RepaintOnly && layout_node()) {
-        layout_node()->apply_style(*m_computed_css_values);
-        layout_node()->set_needs_display();
-        return NeedsRelayout::No;
-    }
-
-    if (required_invalidation == RequiredInvalidation::RebuildStackingContextTree && layout_node()) {
+    if (!invalidation.rebuild_layout_tree && layout_node()) {
+        // If we're keeping the layout tree, we can just apply the new style to the existing layout tree.
         layout_node()->apply_style(*m_computed_css_values);
-        document().invalidate_stacking_context_tree();
-        layout_node()->set_needs_display();
-        return NeedsRelayout::No;
+        if (invalidation.repaint)
+            layout_node()->set_needs_display();
     }
 
-    return NeedsRelayout::Yes;
+    return invalidation;
 }
 
 NonnullRefPtr<CSS::StyleProperties> Element::resolved_css_values()
diff --git a/Userland/Libraries/LibWeb/DOM/Element.h b/Userland/Libraries/LibWeb/DOM/Element.h
index 533dd3b716..667e2365ac 100644
--- a/Userland/Libraries/LibWeb/DOM/Element.h
+++ b/Userland/Libraries/LibWeb/DOM/Element.h
@@ -123,11 +123,25 @@ public:
     virtual void parse_attribute(DeprecatedFlyString const& name, DeprecatedString const& value);
     virtual void did_remove_attribute(DeprecatedFlyString const&);
 
-    enum class NeedsRelayout {
-        No = 0,
-        Yes = 1,
+    struct [[nodiscard]] RequiredInvalidationAfterStyleChange {
+        bool repaint { false };
+        bool rebuild_stacking_context_tree { false };
+        bool relayout { false };
+        bool rebuild_layout_tree { false };
+
+        void operator|=(RequiredInvalidationAfterStyleChange const& other)
+        {
+            repaint |= other.repaint;
+            rebuild_stacking_context_tree |= other.rebuild_stacking_context_tree;
+            relayout |= other.relayout;
+            rebuild_layout_tree |= other.rebuild_layout_tree;
+        }
+
+        [[nodiscard]] bool is_none() const { return !repaint && !rebuild_stacking_context_tree && !relayout && !rebuild_layout_tree; }
+        static RequiredInvalidationAfterStyleChange full() { return { true, true, true, true }; }
     };
-    NeedsRelayout recompute_style();
+
+    RequiredInvalidationAfterStyleChange recompute_style();
 
     Layout::NodeWithStyle* layout_node();
     Layout::NodeWithStyle const* layout_node() const;