LibWeb: Make StackingContext sorting a lot faster

Stacking contexts are sorted after building a tree of them. They are
sorted by z-index first, DOM tree order second.

Sorting was previously *very* slow on pages with many stacking contexts.
That was because the sort() function used Node::is_before() in the
quick_sort comparator to see if one StackingContext was before another.
is_before() does tree traversal and can take quite a long time per call.

This patch avoids all that by letting StackingContext know its index
among all StackingContexts within the same document in tree order.
There's a noticeable snappiness increase on the CSS-FLEXBOX-1 spec page,
for instance. :^)

3 files changed, 8 insertions, 5 deletions

diff --git a/Userland/Libraries/LibWeb/Layout/Viewport.cpp b/Userland/Libraries/LibWeb/Layout/Viewport.cpp
index 1326f5a30b..02d933d9c1 100644
--- a/Userland/Libraries/LibWeb/Layout/Viewport.cpp
+++ b/Userland/Libraries/LibWeb/Layout/Viewport.cpp
@@ -33,8 +33,9 @@ void Viewport::build_stacking_context_tree_if_needed()
 
 void Viewport::build_stacking_context_tree()
 {
-    const_cast<Painting::PaintableBox*>(paintable_box())->set_stacking_context(make<Painting::StackingContext>(*this, nullptr));
+    const_cast<Painting::PaintableBox*>(paintable_box())->set_stacking_context(make<Painting::StackingContext>(*this, nullptr, 0));
 
+    size_t index_in_tree_order = 1;
     for_each_in_subtree_of_type<Box>([&](Box& box) {
         if (!box.paintable_box())
             return IterationDecision::Continue;
@@ -45,7 +46,7 @@ void Viewport::build_stacking_context_tree()
         }
         auto* parent_context = const_cast<Painting::PaintableBox*>(box.paintable_box())->enclosing_stacking_context();
         VERIFY(parent_context);
-        const_cast<Painting::PaintableBox*>(box.paintable_box())->set_stacking_context(make<Painting::StackingContext>(box, parent_context));
+        const_cast<Painting::PaintableBox*>(box.paintable_box())->set_stacking_context(make<Painting::StackingContext>(box, parent_context, index_in_tree_order++));
         return IterationDecision::Continue;
     });
 
diff --git a/Userland/Libraries/LibWeb/Painting/StackingContext.cpp b/Userland/Libraries/LibWeb/Painting/StackingContext.cpp
index 3150a4d40d..0792535a99 100644
--- a/Userland/Libraries/LibWeb/Painting/StackingContext.cpp
+++ b/Userland/Libraries/LibWeb/Painting/StackingContext.cpp
@@ -28,11 +28,12 @@ static void paint_node(Layout::Node const& layout_node, PaintContext& context, P
         paintable->paint(context, phase);
 }
 
-StackingContext::StackingContext(Layout::Box& box, StackingContext* parent)
+StackingContext::StackingContext(Layout::Box& box, StackingContext* parent, size_t index_in_tree_order)
     : m_box(box)
     , m_transform(combine_transformations(m_box->computed_values().transformations()))
     , m_transform_origin(compute_transform_origin())
     , m_parent(parent)
+    , m_index_in_tree_order(index_in_tree_order)
 {
     VERIFY(m_parent != this);
     if (m_parent)
@@ -45,7 +46,7 @@ void StackingContext::sort()
         auto a_z_index = a->m_box->computed_values().z_index().value_or(0);
         auto b_z_index = b->m_box->computed_values().z_index().value_or(0);
         if (a_z_index == b_z_index)
-            return a->m_box->is_before(b->m_box);
+            return a->m_index_in_tree_order < b->m_index_in_tree_order;
         return a_z_index < b_z_index;
     });
 
diff --git a/Userland/Libraries/LibWeb/Painting/StackingContext.h b/Userland/Libraries/LibWeb/Painting/StackingContext.h
index 4720712b51..7016862f92 100644
--- a/Userland/Libraries/LibWeb/Painting/StackingContext.h
+++ b/Userland/Libraries/LibWeb/Painting/StackingContext.h
@@ -15,7 +15,7 @@ namespace Web::Painting {
 
 class StackingContext {
 public:
-    StackingContext(Layout::Box&, StackingContext* parent);
+    StackingContext(Layout::Box&, StackingContext* parent, size_t index_in_tree_order);
 
     StackingContext* parent() { return m_parent; }
     StackingContext const* parent() const { return m_parent; }
@@ -47,6 +47,7 @@ private:
     Gfx::FloatPoint m_transform_origin;
     StackingContext* const m_parent { nullptr };
     Vector<StackingContext*> m_children;
+    size_t m_index_in_tree_order { 0 };
 
     void paint_internal(PaintContext&) const;
     Gfx::FloatMatrix4x4 get_transformation_matrix(CSS::Transformation const& transformation) const;