LibHTML: Batch style updates and make them start from the root

Use a zero-timer to schedule a style update after invalidating style
on any node. Nodes now have a needs_style_update flag which helps us
batch and coalesce the work.

We also start style updates at the root and work our way through the
document, updating any node that has the needs_style_update flag set.
This is slower than what we were doing before, but far more correct.

There is a ton of room for improvement here. :^)

5 files changed, 46 insertions, 10 deletions

diff --git a/Libraries/LibHTML/DOM/Document.cpp b/Libraries/LibHTML/DOM/Document.cpp
index 9a6c991160..ad2a552cfd 100644
--- a/Libraries/LibHTML/DOM/Document.cpp
+++ b/Libraries/LibHTML/DOM/Document.cpp
@@ -1,5 +1,6 @@
 #include <AK/FileSystemPath.h>
 #include <AK/StringBuilder.h>
+#include <LibCore/CTimer.h>
 #include <LibHTML/CSS/StyleResolver.h>
 #include <LibHTML/DOM/Document.h>
 #include <LibHTML/DOM/DocumentType.h>
@@ -18,12 +19,25 @@ Document::Document()
     : ParentNode(*this, NodeType::DOCUMENT_NODE)
     , m_style_resolver(make<StyleResolver>(*this))
 {
+    m_style_update_timer = CTimer::construct();
+    m_style_update_timer->set_single_shot(true);
+    m_style_update_timer->set_interval(0);
+    m_style_update_timer->on_timeout = [this] {
+        update_style();
+    };
 }
 
 Document::~Document()
 {
 }
 
+void Document::schedule_style_update()
+{
+    if (m_style_update_timer->is_active())
+        return;
+    m_style_update_timer->start();
+}
+
 bool Document::is_child_allowed(const Node& node) const
 {
     switch (node.type()) {
@@ -178,7 +192,11 @@ void Document::layout()
 
 void Document::update_style()
 {
-    m_layout_root = nullptr;
+    for_each_in_subtree([&](Node& node) {
+        if (!node.needs_style_update())
+            return;
+        to<Element>(node).recompute_style();
+    });
     update_layout();
 }
 
@@ -222,8 +240,5 @@ void Document::set_hovered_node(Node* node)
     RefPtr<Node> old_hovered_node = move(m_hovered_node);
     m_hovered_node = node;
 
-    if (old_hovered_node)
-        old_hovered_node->invalidate_style();
-    if (m_hovered_node)
-        m_hovered_node->invalidate_style();
+    invalidate_style();
 }
diff --git a/Libraries/LibHTML/DOM/Document.h b/Libraries/LibHTML/DOM/Document.h
index 94fb6ff49d..dc3c6c625e 100644
--- a/Libraries/LibHTML/DOM/Document.h
+++ b/Libraries/LibHTML/DOM/Document.h
@@ -10,6 +10,7 @@
 #include <LibHTML/CSS/StyleSheet.h>
 #include <LibHTML/DOM/ParentNode.h>
 
+class CTimer;
 class Frame;
 class HTMLBodyElement;
 class HTMLHtmlElement;
@@ -77,6 +78,8 @@ public:
 
     const LayoutDocument* layout_node() const;
 
+    void schedule_style_update();
+
 private:
     virtual RefPtr<LayoutNode> create_layout_node(const StyleProperties* parent_style) const override;
 
@@ -91,6 +94,8 @@ private:
     Color m_link_color { Color::Blue };
     Color m_active_link_color { Color::Red };
     Color m_visited_link_color { Color::Magenta };
+
+    RefPtr<CTimer> m_style_update_timer;
 };
 
 template<>
diff --git a/Libraries/LibHTML/DOM/Element.cpp b/Libraries/LibHTML/DOM/Element.cpp
index 4ad220860f..c93536104b 100644
--- a/Libraries/LibHTML/DOM/Element.cpp
+++ b/Libraries/LibHTML/DOM/Element.cpp
@@ -7,6 +7,7 @@
 #include <LibHTML/Layout/LayoutTable.h>
 #include <LibHTML/Layout/LayoutTableCell.h>
 #include <LibHTML/Layout/LayoutTableRow.h>
+#include <LibHTML/Layout/LayoutTreeBuilder.h>
 
 Element::Element(Document& document, const String& tag_name)
     : ParentNode(document, NodeType::ELEMENT_NODE)
@@ -129,11 +130,21 @@ static StyleDifference compute_style_difference(const StyleProperties& old_style
 
 void Element::recompute_style()
 {
+    set_needs_style_update(false);
     ASSERT(parent());
     auto* parent_layout_node = parent()->layout_node();
+    if (!parent_layout_node)
+        return;
     ASSERT(parent_layout_node);
     auto style = document().style_resolver().resolve_style(*this, &parent_layout_node->style());
-    ASSERT(layout_node());
+    if (!layout_node()) {
+        if (style->string_or_fallback(CSS::PropertyID::Display, "inline") == "none")
+            return;
+        // We need a new layout tree here!
+        LayoutTreeBuilder tree_builder;
+        tree_builder.build(*this);
+        return;
+    }
     auto diff = compute_style_difference(layout_node()->style(), *style, document());
     if (diff == StyleDifference::None)
         return;
diff --git a/Libraries/LibHTML/DOM/Node.cpp b/Libraries/LibHTML/DOM/Node.cpp
index f6880c7075..ef03875d98 100644
--- a/Libraries/LibHTML/DOM/Node.cpp
+++ b/Libraries/LibHTML/DOM/Node.cpp
@@ -70,8 +70,9 @@ RefPtr<LayoutNode> Node::create_layout_node(const StyleProperties*) const
 
 void Node::invalidate_style()
 {
-    for (auto* node = this; node; node = node->parent()) {
-        if (is<Element>(*node))
-            to<Element>(*node).recompute_style();
-    }
+    for_each_in_subtree([&](auto& node) {
+        if (is<Element>(node))
+            node.set_needs_style_update(true);
+    });
+    document().schedule_style_update();
 }
diff --git a/Libraries/LibHTML/DOM/Node.h b/Libraries/LibHTML/DOM/Node.h
index a32f631092..326f619670 100644
--- a/Libraries/LibHTML/DOM/Node.h
+++ b/Libraries/LibHTML/DOM/Node.h
@@ -70,6 +70,9 @@ public:
 
     virtual bool is_child_allowed(const Node&) const { return true; }
 
+    bool needs_style_update() const { return m_needs_style_update; }
+    void set_needs_style_update(bool value) { m_needs_style_update = value; }
+
     void invalidate_style();
 
 protected:
@@ -78,6 +81,7 @@ protected:
     Document& m_document;
     mutable LayoutNode* m_layout_node { nullptr };
     NodeType m_type { NodeType::INVALID };
+    bool m_needs_style_update { false };
 };
 
 template<typename T>