LibWeb: Respect CSS z-index property while painting

To support z-ordering when painting, the layout tree now has a parallel
sparse tree of stacking contexts. The rules for which layout boxes
establish a stacking context are a bit complex, but the intent is to
encapsulate the decision making into establishes_stacking_context().

When we paint, we start from the ICB (LayoutDocument) who always has a
StackingContext and then paint the tree of StackingContexts where each
node has its children sorted by z-index.

This is pretty crude, but gets the basic job done. Note that this does
not yet support hit testing; hit testing is still done using a naive
treewalk from the root.

11 files changed, 222 insertions, 3 deletions

diff --git a/Libraries/LibWeb/CMakeLists.txt b/Libraries/LibWeb/CMakeLists.txt
index 138f737767..5ed0f65267 100644
--- a/Libraries/LibWeb/CMakeLists.txt
+++ b/Libraries/LibWeb/CMakeLists.txt
@@ -94,6 +94,7 @@ set(SOURCES
     Layout/LayoutWidget.cpp
     Layout/LineBox.cpp
     Layout/LineBoxFragment.cpp
+    Layout/StackingContext.cpp
     LayoutTreeModel.cpp
     Loader/FrameLoader.cpp
     Loader/ImageLoader.cpp
diff --git a/Libraries/LibWeb/CSS/StyleProperties.cpp b/Libraries/LibWeb/CSS/StyleProperties.cpp
index d146bd05b9..990392b052 100644
--- a/Libraries/LibWeb/CSS/StyleProperties.cpp
+++ b/Libraries/LibWeb/CSS/StyleProperties.cpp
@@ -185,6 +185,14 @@ float StyleProperties::line_height(const LayoutNode& layout_node) const
     return (float)font().glyph_height() * 1.4f;
 }
 
+Optional<int> StyleProperties::z_index() const
+{
+    auto value = property(CSS::PropertyID::ZIndex);
+    if (!value.has_value())
+        return {};
+    return static_cast<int>(value.value()->to_length().raw_value());
+}
+
 CSS::Position StyleProperties::position() const
 {
     if (property(CSS::PropertyID::Position).has_value()) {
diff --git a/Libraries/LibWeb/CSS/StyleProperties.h b/Libraries/LibWeb/CSS/StyleProperties.h
index 1a391fcf16..7838123ac2 100644
--- a/Libraries/LibWeb/CSS/StyleProperties.h
+++ b/Libraries/LibWeb/CSS/StyleProperties.h
@@ -74,6 +74,7 @@ public:
     bool operator!=(const StyleProperties& other) const { return !(*this == other); }
 
     CSS::Position position() const;
+    Optional<int> z_index() const;
 
 private:
     HashMap<unsigned, NonnullRefPtr<StyleValue>> m_property_values;
diff --git a/Libraries/LibWeb/Forward.h b/Libraries/LibWeb/Forward.h
index ee2a02b7cd..cc9cb8f1f4 100644
--- a/Libraries/LibWeb/Forward.h
+++ b/Libraries/LibWeb/Forward.h
@@ -64,6 +64,7 @@ class RenderingContext;
 class Resource;
 class ResourceLoader;
 class Selector;
+class StackingContext;
 class StyleResolver;
 class StyleRule;
 class StyleSheet;
diff --git a/Libraries/LibWeb/Layout/LayoutBox.cpp b/Libraries/LibWeb/Layout/LayoutBox.cpp
index 3d79cc6f0c..9324795206 100644
--- a/Libraries/LibWeb/Layout/LayoutBox.cpp
+++ b/Libraries/LibWeb/Layout/LayoutBox.cpp
@@ -310,4 +310,36 @@ void LayoutBox::set_containing_line_box_fragment(LineBoxFragment& fragment)
     m_containing_line_box_fragment = fragment.make_weak_ptr();
 }
 
+StackingContext* LayoutBox::enclosing_stacking_context()
+{
+    for (auto* ancestor = parent(); ancestor; ancestor = ancestor->parent()) {
+        if (!ancestor->is_box())
+            continue;
+        auto& ancestor_box = to<LayoutBox>(*ancestor);
+        if (!ancestor_box.establishes_stacking_context())
+            continue;
+        ASSERT(ancestor_box.stacking_context());
+        return ancestor_box.stacking_context();
+    }
+    // We should always reach the LayoutDocument stacking context.
+    ASSERT_NOT_REACHED();
+}
+
+bool LayoutBox::establishes_stacking_context() const
+{
+    if (!has_style())
+        return false;
+    if (node() == document().root())
+        return true;
+    auto position = style().position();
+    auto z_index = style().z_index();
+    if (position == CSS::Position::Absolute || position == CSS::Position::Relative) {
+        if (z_index.has_value())
+            return true;
+    }
+    if (position == CSS::Position::Fixed || position == CSS::Position::Sticky)
+        return true;
+    return false;
+}
+
 }
diff --git a/Libraries/LibWeb/Layout/LayoutBox.h b/Libraries/LibWeb/Layout/LayoutBox.h
index 516a19b2f3..652e04b041 100644
--- a/Libraries/LibWeb/Layout/LayoutBox.h
+++ b/Libraries/LibWeb/Layout/LayoutBox.h
@@ -26,8 +26,10 @@
 
 #pragma once
 
+#include <AK/OwnPtr.h>
 #include <LibGfx/FloatRect.h>
 #include <LibWeb/Layout/LayoutNode.h>
+#include <LibWeb/Layout/StackingContext.h>
 
 namespace Web {
 
@@ -60,14 +62,19 @@ public:
 
     void set_containing_line_box_fragment(LineBoxFragment&);
 
+    bool establishes_stacking_context() const;
+    StackingContext* stacking_context() { return m_stacking_context; }
+    void set_stacking_context(NonnullOwnPtr<StackingContext> context) { m_stacking_context = move(context); }
+    StackingContext* enclosing_stacking_context();
+
+    virtual void render(RenderingContext&) override;
+
 protected:
     LayoutBox(const Node* node, NonnullRefPtr<StyleProperties> style)
         : LayoutNodeWithStyleAndBoxModelMetrics(node, move(style))
     {
     }
 
-    virtual void render(RenderingContext&) override;
-
     virtual void did_set_rect() { }
 
 private:
@@ -86,6 +93,8 @@ private:
 
     // Some boxes hang off of line box fragments. (inline-block, inline-table, replaced, etc)
     WeakPtr<LineBoxFragment> m_containing_line_box_fragment;
+
+    OwnPtr<StackingContext> m_stacking_context;
 };
 
 template<>
diff --git a/Libraries/LibWeb/Layout/LayoutDocument.cpp b/Libraries/LibWeb/Layout/LayoutDocument.cpp
index e49807e82f..8dd4f2db2c 100644
--- a/Libraries/LibWeb/Layout/LayoutDocument.cpp
+++ b/Libraries/LibWeb/Layout/LayoutDocument.cpp
@@ -29,6 +29,7 @@
 #include <LibWeb/Layout/LayoutDocument.h>
 #include <LibWeb/Layout/LayoutImage.h>
 #include <LibWeb/Layout/LayoutWidget.h>
+#include <LibWeb/Layout/StackingContext.h>
 
 namespace Web {
 
@@ -41,8 +42,31 @@ LayoutDocument::~LayoutDocument()
 {
 }
 
+void LayoutDocument::build_stacking_context_tree()
+{
+    if (stacking_context())
+        return;
+
+    set_stacking_context(make<StackingContext>(*this, nullptr));
+
+    for_each_in_subtree_of_type<LayoutBox>([&](LayoutBox& box) {
+        if (&box == this)
+            return IterationDecision::Continue;
+        if (!box.establishes_stacking_context()) {
+            ASSERT(!box.stacking_context());
+            return IterationDecision::Continue;
+        }
+        auto* parent_context = box.enclosing_stacking_context();
+        ASSERT(parent_context);
+        box.set_stacking_context(make<StackingContext>(box, parent_context));
+        return IterationDecision::Continue;
+    });
+}
+
 void LayoutDocument::layout(LayoutMode layout_mode)
 {
+    build_stacking_context_tree();
+
     set_width(frame().size().width());
 
     LayoutNode::layout(layout_mode);
@@ -76,4 +100,9 @@ void LayoutDocument::did_set_viewport_rect(Badge<Frame>, const Gfx::IntRect& a_v
     });
 }
 
+void LayoutDocument::render(RenderingContext& context)
+{
+    stacking_context()->render(context);
+}
+
 }
diff --git a/Libraries/LibWeb/Layout/LayoutDocument.h b/Libraries/LibWeb/Layout/LayoutDocument.h
index 025d178b51..0527d7feec 100644
--- a/Libraries/LibWeb/Layout/LayoutDocument.h
+++ b/Libraries/LibWeb/Layout/LayoutDocument.h
@@ -40,6 +40,8 @@ public:
     virtual const char* class_name() const override { return "LayoutDocument"; }
     virtual void layout(LayoutMode = LayoutMode::Default) override;
 
+    virtual void render(RenderingContext&) override;
+
     const LayoutRange& selection() const { return m_selection; }
     LayoutRange& selection() { return m_selection; }
 
@@ -47,8 +49,17 @@ public:
 
     virtual bool is_root() const override { return true; }
 
+    void build_stacking_context_tree();
+
 private:
     LayoutRange m_selection;
 };
 
+template<>
+inline bool is<LayoutDocument>(const LayoutNode& node)
+{
+    return node.is_root();
+}
+
+
 }
diff --git a/Libraries/LibWeb/Layout/LayoutNode.cpp b/Libraries/LibWeb/Layout/LayoutNode.cpp
index 75708df343..018be1ef71 100644
--- a/Libraries/LibWeb/Layout/LayoutNode.cpp
+++ b/Libraries/LibWeb/Layout/LayoutNode.cpp
@@ -94,8 +94,9 @@ void LayoutNode::render(RenderingContext& context)
     if (!is_visible())
         return;
 
-    // TODO: render our border
     for_each_child([&](auto& child) {
+        if (child.is_box() && to<LayoutBox>(child).stacking_context())
+            return;
         child.render(context);
     });
 }
diff --git a/Libraries/LibWeb/Layout/StackingContext.cpp b/Libraries/LibWeb/Layout/StackingContext.cpp
new file mode 100644
index 0000000000..a95ff04dfa
--- /dev/null
+++ b/Libraries/LibWeb/Layout/StackingContext.cpp
@@ -0,0 +1,73 @@
+/*
+ * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ * 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 <AK/QuickSort.h>
+#include <LibWeb/DOM/Node.h>
+#include <LibWeb/Layout/LayoutBox.h>
+#include <LibWeb/Layout/LayoutDocument.h>
+#include <LibWeb/Layout/StackingContext.h>
+
+namespace Web {
+
+StackingContext::StackingContext(LayoutBox& box, StackingContext* parent)
+    : m_box(box)
+    , m_parent(parent)
+{
+    ASSERT(m_parent != this);
+    if (m_parent) {
+        m_parent->m_children.append(this);
+
+        // FIXME: Don't sort on every append..
+        quick_sort(m_children, [](auto& a, auto& b) {
+            return a->m_box.style().z_index().value_or(0) < b->m_box.style().z_index().value_or(0);
+        });
+    }
+}
+
+void StackingContext::render(RenderingContext& context)
+{
+    if (!m_box.is_root()) {
+        m_box.render(context);
+    } else {
+        // NOTE: LayoutDocument::render() merely calls StackingContext::render()
+        //       so we call its base class instead.
+        to<LayoutDocument>(m_box).LayoutBlock::render(context);
+    }
+    for (auto* child : m_children) {
+        child->render(context);
+    }
+}
+
+void StackingContext::dump(int indent) const
+{
+    for (int i = 0; i < indent; ++i)
+        dbgprintf(" ");
+    dbgprintf("SC for %s{%s} %s [children: %zu]\n", m_box.class_name(), m_box.node() ? m_box.node()->tag_name().characters() : "(anonymous)", m_box.absolute_rect().to_string().characters(), m_children.size());
+    for (auto& child : m_children)
+        child->dump(indent + 1);
+}
+
+}
diff --git a/Libraries/LibWeb/Layout/StackingContext.h b/Libraries/LibWeb/Layout/StackingContext.h
new file mode 100644
index 0000000000..6b11cba5cb
--- /dev/null
+++ b/Libraries/LibWeb/Layout/StackingContext.h
@@ -0,0 +1,53 @@
+/*
+ * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
+ * 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/Vector.h>
+#include <LibWeb/Forward.h>
+
+namespace Web {
+
+class LayoutBox;
+
+class StackingContext {
+public:
+    StackingContext(LayoutBox&, StackingContext* parent);
+
+    StackingContext* parent() { return m_parent; }
+    const StackingContext* parent() const { return m_parent; }
+
+    void render(RenderingContext&);
+
+    void dump(int indent = 0) const;
+
+private:
+    LayoutBox& m_box;
+    StackingContext* const m_parent { nullptr };
+    Vector<StackingContext*> m_children;
+};
+
+}