/*
 * Copyright (c) 2022-2024, Andreas Kling <andreas@ladybird.org>
 * Copyright (c) 2024, Sam Atkins <atkinssj@serenityos.org>
 * Copyright (c) 2024, Aliaksandr Kalenik <kalenik.aliaksandr@gmail.com>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 */

#include <AK/Debug.h>
#include <AK/HashMap.h>
#include <AK/Tuple.h>
#include <LibWeb/DOM/Document.h>
#include <LibWeb/DOM/ShadowRoot.h>
#include <LibWeb/Layout/AvailableSpace.h>
#include <LibWeb/Layout/InlineNode.h>
#include <LibWeb/Layout/LayoutState.h>
#include <LibWeb/Layout/Viewport.h>
#include <LibWeb/Painting/PaintableWithLines.h>
#include <LibWeb/Painting/SVGPathPaintable.h>
#include <LibWeb/Painting/TextPaintable.h>

namespace Web::Layout {

LayoutState::LayoutState(NodeWithStyle const& subtree_root)
    : m_subtree_root(&subtree_root)
{
}

LayoutState::~LayoutState()
{
}

void LayoutState::ensure_capacity(u32 node_count)
{
    m_used_values_store.ensure_capacity(node_count);
}

LayoutState::UsedValues& LayoutState::get_mutable(NodeWithStyle const& node)
{
    return ensure_used_values_for(node);
}

LayoutState::UsedValues const& LayoutState::get(NodeWithStyle const& node) const
{
    return const_cast<LayoutState*>(this)->ensure_used_values_for(node);
}

LayoutState::UsedValues& LayoutState::populate_from_paintable(NodeWithStyle const& node, Painting::PaintableBox const& paintable)
{
    VERIFY(m_subtree_root);
    auto index = node.layout_index();

    // NOTE: We skip set_node() here since it performs size resolution that requires a containing block,
    //       and materialize_from_paintable() overwrites all computed sizes immediately after.
    auto& used_values = m_used_values_store.allocate(index);
    used_values.m_node = &node;
    used_values.materialize_from_paintable(paintable);
    return used_values;
}

LayoutState::UsedValues& LayoutState::populate_node_from(LayoutState const& source, NodeWithStyle const& node)
{
    VERIFY(m_subtree_root);
    auto index = node.layout_index();
    VERIFY(!m_used_values_store.get(index));

    auto& values = m_used_values_store.allocate(index);
    values = source.get(node);
    values.m_containing_block_used_values = nullptr;
    return values;
}

LayoutState::UsedValues& LayoutState::ensure_used_values_for(NodeWithStyle const& node)
{
    auto index = node.layout_index();

    if (auto* used_values = m_used_values_store.get(index))
        return *used_values;

    // During subtree layout, only the subtree root and nodes inside the subtree are allowed.
    VERIFY(!m_subtree_root || m_subtree_root == &node || m_subtree_root->is_inclusive_ancestor_of(node));

    UsedValues const* containing_block_used_values = nullptr;
    if (m_subtree_root == &node) {
        // For the subtree root, ancestor values are not available in the throwaway state.
        containing_block_used_values = try_get(*node.containing_block());
    } else if (!node.is_viewport()) {
        containing_block_used_values = &get(*node.containing_block());
    }

    auto& used_values = m_used_values_store.allocate(index);
    used_values.set_node(node, containing_block_used_values);
    return used_values;
}

LayoutState::UsedValues const* LayoutState::try_get(NodeWithStyle const& node) const
{
    return m_used_values_store.get(node.layout_index());
}

LayoutState::UsedValues* LayoutState::try_get_mutable(NodeWithStyle const& node)
{
    return m_used_values_store.get(node.layout_index());
}

LayoutState::UsedValues const* LayoutState::try_get(Node const& node) const
{
    auto* node_with_style = as_if<NodeWithStyle>(node);
    if (!node_with_style)
        return nullptr;
    return try_get(*node_with_style);
}

// https://drafts.csswg.org/css-overflow-3/#scrollable-overflow-region
using ContainedBoxesMap = HashMap<Box const*, Vector<Box const*>>;

struct PhysicalOverflowDirections {
    bool x_positive { true };
    bool y_positive { true };
};

struct LogicalAxis {
    bool is_horizontal { false };
    bool is_reverse { false };
};

static bool inline_axis_is_horizontal(CSS::WritingMode writing_mode)
{
    return writing_mode == CSS::WritingMode::HorizontalTb;
}

static PhysicalOverflowDirections physical_overflow_directions(Box const& box)
{
    auto const& computed_values = box.computed_values();
    LogicalAxis inline_axis {
        .is_horizontal = inline_axis_is_horizontal(computed_values.writing_mode()),
        .is_reverse = computed_values.inline_axis_is_reverse(),
    };
    LogicalAxis block_axis {
        .is_horizontal = !inline_axis.is_horizontal,
        .is_reverse = computed_values.block_axis_is_reverse(),
    };

    auto horizontal_and_vertical_axes = [&]() {
        if (!box.display().is_flex_inside())
            return AK::Tuple { inline_axis.is_horizontal ? inline_axis : block_axis, inline_axis.is_horizontal ? block_axis : inline_axis };

        auto is_row_layout = computed_values.flex_direction() == CSS::FlexDirection::Row
            || computed_values.flex_direction() == CSS::FlexDirection::RowReverse;

        auto main_axis = is_row_layout ? inline_axis : block_axis;
        if (computed_values.flex_direction() == CSS::FlexDirection::RowReverse
            || computed_values.flex_direction() == CSS::FlexDirection::ColumnReverse) {
            main_axis.is_reverse = !main_axis.is_reverse;
        }

        auto cross_axis = is_row_layout ? block_axis : inline_axis;
        if (computed_values.flex_wrap() == CSS::FlexWrap::WrapReverse)
            cross_axis.is_reverse = !cross_axis.is_reverse;

        return AK::Tuple { main_axis.is_horizontal ? main_axis : cross_axis, main_axis.is_horizontal ? cross_axis : main_axis };
    };

    auto axes = horizontal_and_vertical_axes();
    auto horizontal_axis = axes.get<0>();
    auto vertical_axis = axes.get<1>();
    return {
        .x_positive = !horizontal_axis.is_reverse,
        .y_positive = !vertical_axis.is_reverse,
    };
}

static CSSPixelRect measure_scrollable_overflow(Box const& box, ContainedBoxesMap const& contained_boxes_map)
{
    if (!box.paintable_box())
        return {};

    auto const& paintable_box = *box.paintable_box();

    if (paintable_box.scrollable_overflow_rect().has_value())
        return paintable_box.scrollable_overflow_rect().value();

    // The scrollable overflow area is the union of:

    // - The scroll container’s own padding box.
    auto const paintable_absolute_padding_box = paintable_box.absolute_padding_box_rect();
    auto scrollable_overflow_rect = paintable_absolute_padding_box;
    auto overflow_directions = physical_overflow_directions(box);

    // - All line boxes directly contained by the scroll container.
    if (auto first_paintable = box.first_paintable(); auto const* paintable_with_lines = as_if<Painting::PaintableWithLines>(first_paintable.ptr())) {
        for (auto const& fragment : paintable_with_lines->fragments())
            scrollable_overflow_rect.unite(fragment.absolute_rect());
    }

    auto content_overflow_rect = scrollable_overflow_rect;

    // - The border boxes of all boxes for which it is the containing block and whose border boxes are positioned not
    //   wholly in the negative scrollable overflow region,
    //   FIXME: accounting for transforms by projecting each box onto the plane of the element that establishes its 3D rendering context. [CSS3-TRANSFORMS]
    if (auto it = contained_boxes_map.find(&box); it != contained_boxes_map.end()) {
        for (auto const* child_ptr : it->value) {
            auto const& child = *child_ptr;

            // https://drafts.csswg.org/css-position/#fixed-positioning-containing-block
            // [..] As a result, parts of fixed-positioned boxes that extend outside the layout viewport/page area
            //      cannot be scrolled to and will not print.
            // FIXME: Properly establish the fixed positioning containing block for `position: fixed`
            if (child.is_fixed_position())
                continue;

            auto child_border_box = child.paintable_box()->absolute_border_box_rect();

            // NOTE: Only boxes that are not wholly in the unreachable scrollable overflow region contribute.
            auto wholly_in_unreachable_x = overflow_directions.x_positive
                ? child_border_box.right() < paintable_absolute_padding_box.x()
                : child_border_box.x() > paintable_absolute_padding_box.right();
            auto wholly_in_unreachable_y = overflow_directions.y_positive
                ? child_border_box.bottom() < paintable_absolute_padding_box.y()
                : child_border_box.y() > paintable_absolute_padding_box.bottom();
            if (wholly_in_unreachable_x || wholly_in_unreachable_y)
                continue;

            // Border boxes with zero area do not affect the scrollable overflow area.
            if (!child_border_box.is_empty()) {
                scrollable_overflow_rect.unite(child_border_box);
                content_overflow_rect.unite(child_border_box);
            }

            // - The scrollable overflow areas of all of the above boxes (including zero-area boxes and accounting for
            //   transforms as described above), provided they themselves have overflow: visible (i.e. do not themselves
            //   trap the overflow) and that scrollable overflow is not already clipped (e.g. by the clip property or the
            //   contain property).
            // Scrollable overflow is already clipped by the contain property.
            if (child.has_layout_containment() || child.has_paint_containment())
                continue;

            if (child.computed_values().overflow_x() == CSS::Overflow::Visible || child.computed_values().overflow_y() == CSS::Overflow::Visible) {
                auto child_scrollable_overflow = measure_scrollable_overflow(child, contained_boxes_map);
                if (!child_scrollable_overflow.is_empty()) {
                    if (child.computed_values().overflow_x() == CSS::Overflow::Visible)
                        scrollable_overflow_rect.unite_horizontally(child_scrollable_overflow);
                    if (child.computed_values().overflow_y() == CSS::Overflow::Visible)
                        scrollable_overflow_rect.unite_vertically(child_scrollable_overflow);
                }
            }
        }
    }

    // FIXME: - The margin areas of grid item and flex item boxes for which the box establishes a containing block.

    // - Additional padding added to the scrollable overflow rectangle as necessary to enable scroll positions that
    //   satisfy the requirements of both place-content: start and place-content: end alignment.
    auto has_scrollable_overflow = !paintable_absolute_padding_box.contains(scrollable_overflow_rect) && box.is_scroll_container();
    if (has_scrollable_overflow) {
        auto left = scrollable_overflow_rect.x();
        auto top = scrollable_overflow_rect.y();
        auto right = scrollable_overflow_rect.right();
        auto bottom = scrollable_overflow_rect.bottom();

        if (overflow_directions.x_positive)
            right = max(right, content_overflow_rect.right() + paintable_box.box_model().padding.right);
        else
            left = min(left, content_overflow_rect.x() - paintable_box.box_model().padding.left);

        if (overflow_directions.y_positive)
            bottom = max(bottom, content_overflow_rect.bottom() + paintable_box.box_model().padding.bottom);
        else
            top = min(top, content_overflow_rect.y() - paintable_box.box_model().padding.top);

        scrollable_overflow_rect = {
            left,
            top,
            max(right - left, CSSPixels { 0 }),
            max(bottom - top, CSSPixels { 0 }),
        };
    }

    // Additionally, due to Web-compatibility constraints (caused by authors exploiting legacy bugs to surreptitiously
    // hide content from visual readers but not search engines and/or speech output), UAs must clip any content in the
    // unreachable scrollable overflow region.
    //
    // https://drafts.csswg.org/css-overflow-3/#unreachable-scrollable-overflow-region
    // Unless otherwise adjusted (e.g. by content alignment [css-align-3]), the area beyond the scroll origin in either
    // axis is considered the unreachable scrollable overflow region: content rendered here is not accessible to the
    // reader, see § 2.2 Scrollable Overflow.
    auto left = overflow_directions.x_positive ? max(scrollable_overflow_rect.x(), paintable_absolute_padding_box.x()) : scrollable_overflow_rect.x();
    auto top = overflow_directions.y_positive ? max(scrollable_overflow_rect.y(), paintable_absolute_padding_box.y()) : scrollable_overflow_rect.y();
    auto right = overflow_directions.x_positive ? scrollable_overflow_rect.right() : min(scrollable_overflow_rect.right(), paintable_absolute_padding_box.right());
    auto bottom = overflow_directions.y_positive ? scrollable_overflow_rect.bottom() : min(scrollable_overflow_rect.bottom(), paintable_absolute_padding_box.bottom());
    if (left != scrollable_overflow_rect.x() || top != scrollable_overflow_rect.y() || right != scrollable_overflow_rect.right() || bottom != scrollable_overflow_rect.bottom()) {
        scrollable_overflow_rect = {
            left,
            top,
            max(right - left, CSSPixels { 0 }),
            max(bottom - top, CSSPixels { 0 }),
        };
        has_scrollable_overflow = !paintable_absolute_padding_box.contains(scrollable_overflow_rect) && box.is_scroll_container();
    }

    const_cast<Painting::PaintableBox&>(paintable_box).set_overflow_data({
        .scrollable_overflow_rect = scrollable_overflow_rect,
        .has_scrollable_overflow = has_scrollable_overflow,
    });

    return scrollable_overflow_rect;
}

void LayoutState::resolve_relative_positions()
{
    // This function resolves relative position offsets of fragments that belong to inline paintables.
    // It runs *after* the paint tree has been constructed, so it modifies paintable node & fragment offsets directly.
    m_used_values_store.for_each([&](UsedValues& used_values) {
        auto& node = const_cast<NodeWithStyle&>(used_values.node());

        for (auto& paintable : node.paintables()) {
            auto* inline_paintable = as_if<Painting::PaintableWithLines>(paintable.ptr());
            if (!inline_paintable || !is<Layout::InlineNode>(inline_paintable->layout_node()))
                continue;

            for (auto& fragment : inline_paintable->fragments()) {
                auto const& fragment_node = fragment.layout_node();
                if (!is<Layout::NodeWithStyleAndBoxModelMetrics>(*fragment_node.parent()))
                    continue;
                // Collect effective relative position offset from inline-flow parent chain.
                CSSPixelPoint offset;
                for (auto* ancestor = fragment_node.parent(); ancestor; ancestor = ancestor->parent()) {
                    if (!is<Layout::NodeWithStyleAndBoxModelMetrics>(*ancestor))
                        break;
                    if (!ancestor->display().is_inline_outside() || !ancestor->display().is_flow_inside())
                        break;
                    if (ancestor->computed_values().position() == CSS::Positioning::Relative) {
                        VERIFY(ancestor->first_paintable());
                        auto ancestor_paintable = ancestor->first_paintable();
                        auto const& ancestor_node = as<Painting::PaintableBox>(*ancestor_paintable);
                        auto const& inset = ancestor_node.box_model().inset;
                        offset.translate_by(inset.left, inset.top);
                    }
                }
                const_cast<Painting::PaintableFragment&>(fragment).set_offset(fragment.offset().translated(offset));
            }
        }
    });
}

static void build_paint_tree(Node& node, RefPtr<Painting::Paintable> parent_paintable = nullptr)
{
    for (auto& paintable : node.paintables()) {
        if (parent_paintable && !paintable->forms_unconnected_subtree()) {
            VERIFY(!paintable->parent());
            parent_paintable->append_child(paintable);
        }
        paintable->set_dom_node(node.dom_node());
        if (node.dom_node())
            node.dom_node()->set_paintable(paintable);
    }
    for (auto* child = node.first_child(); child; child = child->next_sibling()) {
        build_paint_tree(*child, node.first_paintable());
    }
}

void LayoutState::commit(Box& root)
{
    RefPtr<Painting::Paintable> parent_paintable;
    if (!root.is_viewport()) {
        if (auto existing = root.first_paintable(); auto* existing_box = as_if<Painting::PaintableBox>(existing.ptr())) {
            parent_paintable = existing_box->parent();
            if (parent_paintable)
                parent_paintable->remove_child(*existing_box);
        }
    }

    // Cache existing paintables before clearing.
    HashMap<Node const*, NonnullRefPtr<Painting::PaintableBox>> paintable_cache;
    root.for_each_in_inclusive_subtree([&](Node& node) {
        if (auto paintable = node.first_paintable(); auto* paintable_box = as_if<Painting::PaintableBox>(paintable.ptr())) {
            // InlineNodes are excluded because they can span multiple lines, with a separate
            // InlinePaintable created for each line via create_paintable_for_line_with_index().
            // This 1:N relationship between layout node and paintables, combined with the
            // dynamic nature of fragment relocation, makes simple 1:1 caching inapplicable.
            if (!is<InlineNode>(node))
                paintable_cache.set(&node, *paintable_box);
        }
        return TraversalDecision::Continue;
    });

    // Go through the layout tree and detach all paintables. The layout tree should only point to the new paintable tree
    // which we're about to build.
    root.for_each_in_inclusive_subtree([](Node& node) {
        node.clear_paintables();
        return TraversalDecision::Continue;
    });

    // After this point, we should have a clean slate to build the new paint tree.

    HashTable<Layout::InlineNode*> inline_nodes;

    root.for_each_in_inclusive_subtree([&](Node& node) {
        if (auto* dom_node = node.dom_node())
            dom_node->clear_paintable();
        if (is<InlineNode>(node) && node.dom_node()) {
            // Inline nodes might have a continuation chain; add all inline nodes that are part of it.
            for (GC::Ptr inline_node = static_cast<NodeWithStyleAndBoxModelMetrics*>(&node);
                inline_node; inline_node = inline_node->continuation_of_node()) {
                if (is<InlineNode>(*inline_node))
                    inline_nodes.set(static_cast<InlineNode*>(inline_node.ptr()));
            }
        }
        return TraversalDecision::Continue;
    });

    HashTable<Layout::TextNode*> text_nodes;
    HashTable<WeakPtr<Painting::PaintableWithLines>> inline_node_paintables;

    auto transfer_box_model_metrics = [](Painting::BoxModelMetrics& box_model, UsedValues const& used_values) {
        box_model.inset = { used_values.inset_top, used_values.inset_right, used_values.inset_bottom, used_values.inset_left };
        box_model.padding = { used_values.padding_top, used_values.padding_right, used_values.padding_bottom, used_values.padding_left };
        box_model.border = { used_values.border_top, used_values.border_right, used_values.border_bottom, used_values.border_left };
        box_model.margin = { used_values.margin_top, used_values.margin_right, used_values.margin_bottom, used_values.margin_left };
    };

    auto try_to_relocate_fragment_in_inline_node = [&](auto& fragment, size_t line_index) -> bool {
        for (auto const* parent = fragment.layout_node().parent(); parent; parent = parent->parent()) {
            if (parent->is_atomic_inline())
                break;
            if (is<InlineNode>(*parent)) {
                auto& inline_node = const_cast<InlineNode&>(static_cast<InlineNode const&>(*parent));
                auto line_paintable = inline_node.create_paintable_for_line_with_index(line_index);
                line_paintable->add_fragment(fragment);
                if (auto const* used_values = try_get(inline_node))
                    transfer_box_model_metrics(line_paintable->box_model(), *used_values);
                if (!inline_node_paintables.contains(line_paintable.ptr())) {
                    inline_node_paintables.set(line_paintable);
                    inline_node.add_paintable(line_paintable);
                }
                return true;
            }
        }
        return false;
    };

    m_used_values_store.for_each([&](UsedValues& used_values) {
        auto& node = used_values.node();

        if (m_subtree_root && !m_subtree_root->is_inclusive_ancestor_of(node))
            return;

        RefPtr<Painting::Paintable> paintable;

        // Try to reuse cached paintable for Box nodes
        if (auto cached = paintable_cache.get(&node); cached.has_value()) {
            auto cached_paintable = cached.value();
            cached_paintable->reset_for_relayout();
            paintable = cached_paintable;
        }

        // Fall back to creating new if no reusable paintable
        if (!paintable)
            paintable = node.create_paintable();

        node.add_paintable(paintable);

        // For boxes, transfer all the state needed for painting.
        if (auto* paintable_box = as_if<Painting::PaintableBox>(paintable.ptr())) {
            transfer_box_model_metrics(paintable_box->box_model(), used_values);

            paintable_box->set_offset(used_values.offset);
            paintable_box->set_content_size(used_values.content_width(), used_values.content_height());
            if (used_values.override_borders_data().has_value())
                paintable_box->set_override_borders_data(used_values.override_borders_data().value());
            if (used_values.table_cell_coordinates().has_value())
                paintable_box->set_table_cell_coordinates(used_values.table_cell_coordinates().value());

            if (auto* paintable_with_lines = as_if<Painting::PaintableWithLines>(*paintable_box)) {
                for (size_t line_index = 0; line_index < used_values.line_boxes.size(); ++line_index) {
                    auto& line_box = used_values.line_boxes[line_index];
                    for (auto const& fragment : line_box.fragments()) {
                        if (fragment.is_fully_truncated())
                            continue;
                        if (auto const* text_node = as_if<TextNode>(fragment.layout_node()))
                            text_nodes.set(const_cast<TextNode*>(text_node));
                        auto did_relocate_fragment = try_to_relocate_fragment_in_inline_node(fragment, line_index);
                        if (!did_relocate_fragment)
                            paintable_with_lines->add_fragment(fragment);
                    }
                }
            }

            if (auto* svg_graphics_paintable = as_if<Painting::SVGGraphicsPaintable>(paintable.ptr());
                svg_graphics_paintable && used_values.computed_svg_transforms().has_value()) {
                svg_graphics_paintable->set_computed_transforms(*used_values.computed_svg_transforms());
            }

            if (auto* svg_path_paintable = as_if<Painting::SVGPathPaintable>(paintable.ptr())) {
                if (auto* path = used_values.computed_svg_path())
                    svg_path_paintable->set_computed_path(move(*path));
            }

            if (node.display().is_grid_inside()) {
                paintable_box->set_used_values_for_grid_template_columns(used_values.grid_template_columns());
                paintable_box->set_used_values_for_grid_template_rows(used_values.grid_template_rows());
            }
        }
    });

    // Create paintables for inline nodes without fragments to make possible querying their geometry.
    for (auto& inline_node : inline_nodes) {
        if (inline_node->first_paintable())
            continue;

        auto line_paintable = inline_node->create_paintable_for_line_with_index(0);
        inline_node->add_paintable(line_paintable);
        inline_node_paintables.set(line_paintable.ptr());
        if (auto const* used_values = try_get(*inline_node))
            transfer_box_model_metrics(line_paintable->box_model(), *used_values);
    }

    // Resolve relative positions for regular boxes (not line box fragments):
    // NOTE: This needs to occur before fragments are transferred into the corresponding inline paintables, because
    //       after this transfer, the containing_line_box_fragment will no longer be valid.
    m_used_values_store.for_each([&](UsedValues& used_values) {
        auto& node = const_cast<NodeWithStyle&>(used_values.node());

        if (!node.is_box())
            return;

        auto paintable_ref = node.first_paintable();
        auto& paintable = as<Painting::PaintableBox>(*paintable_ref);
        CSSPixelPoint offset;

        if (used_values.containing_line_box_fragment.has_value()) {
            // Atomic inline case:
            // We know that `node` is an atomic inline because `containing_line_box_fragments` refers to the
            // line box fragment in the parent block container that contains it.
            auto const& containing_line_box_fragment = used_values.containing_line_box_fragment.value();
            auto const& containing_block = *node.containing_block();
            auto const& containing_block_used_values = get(containing_block);
            auto const& fragment = containing_block_used_values.line_boxes[containing_line_box_fragment.line_box_index].fragments()[containing_line_box_fragment.fragment_index];

            // The fragment has the final offset for the atomic inline, so we just need to copy it from there.
            offset = fragment.offset();
        } else {
            // Not an atomic inline, much simpler case.
            offset = used_values.offset;
        }

        // Apply relative position inset if appropriate.
        if (node.computed_values().position() == CSS::Positioning::Relative && is<NodeWithStyleAndBoxModelMetrics>(node)) {
            auto const& inset = paintable.box_model().inset;
            offset.translate_by(inset.left, inset.top);
        }
        paintable.set_offset(offset);
    });

    for (auto* text_node : text_nodes)
        text_node->add_paintable(text_node->create_paintable());

    build_paint_tree(root, parent_paintable);

    resolve_relative_positions();

    // Measure size of paintables created for inline nodes.
    for (auto const& weak_paintable_with_lines : inline_node_paintables) {
        auto paintable_with_lines = weak_paintable_with_lines.strong_ref();
        if (!paintable_with_lines)
            continue;
        if (!is<InlineNode>(paintable_with_lines->layout_node()))
            continue;

        Optional<CSSPixelPoint> offset;
        CSSPixelSize size;
        auto line_index = paintable_with_lines->line_index();
        paintable_with_lines->for_each_in_inclusive_subtree_of_type<Painting::PaintableWithLines>([&](auto& paintable) {
            if (paintable.line_index() != line_index)
                return TraversalDecision::Continue;
            if (is<BlockContainer>(paintable.layout_node()))
                return TraversalDecision::SkipChildrenAndContinue;

            auto const* used_values = try_get(paintable.layout_node_with_style_and_box_metrics());
            if (&paintable != paintable_with_lines && used_values)
                size.set_width(size.width() + used_values->margin_box_left() + used_values->margin_box_right());

            auto const& fragments = paintable.fragments();
            if (!fragments.is_empty()) {
                if (!offset.has_value() || (fragments.first().offset().x() < offset->x()))
                    offset = fragments.first().offset();
                if (&paintable == paintable_with_lines->first_child() && used_values)
                    offset->translate_by(-used_values->margin_box_left(), 0);
            }
            for (auto const& fragment : fragments)
                size.set_width(size.width() + fragment.width());

            return TraversalDecision::Continue;
        });

        if (offset.has_value()) {
            if (!paintable_with_lines->fragments().is_empty())
                offset.value().set_y(paintable_with_lines->fragments().first().offset().y());

            // FIXME: If this paintable does not have any fragment we do no know the y offset. It should be where text should
            // start if there had been any for this node. Pick y offset of the leftmost fragment in the inclusive subtree in the meantime.
            paintable_with_lines->set_offset(offset.value());
        }

        if (!paintable_with_lines->fragments().is_empty()) {
            for (auto const& fragment : paintable_with_lines->fragments())
                size.set_height(max(size.height(), fragment.height()));
        } else {
            size.set_height(paintable_with_lines->layout_node().computed_values().line_height());
        }

        paintable_with_lines->set_content_size(size);
    }

    // Build a map from each containing block to the boxes it contains.
    ContainedBoxesMap contained_boxes_map;
    m_used_values_store.for_each([&](UsedValues& used_values) {
        auto const* box = as_if<Box>(used_values.node());
        if (!box || !box->paintable_box())
            return;
        if (auto containing_block = box->containing_block())
            contained_boxes_map.ensure(containing_block.ptr()).append(box);
    });

    // Measure overflow in scroll containers.
    m_used_values_store.for_each([&](UsedValues& used_values) {
        auto const* box = as_if<Box>(used_values.node());
        if (!box)
            return;
        measure_scrollable_overflow(*box, contained_boxes_map);

        // The scroll offset can become invalid if the scrollable overflow rectangle has changed after layout.
        // For example, if the scroll container has been scrolled to the very end and is then resized to become larger
        // (scrollable overflow rect become smaller), the scroll offset would be out of bounds.
        auto& paintable_box = const_cast<Painting::PaintableBox&>(*box->paintable_box());
        if (!paintable_box.scroll_offset().is_zero())
            paintable_box.set_scroll_offset(paintable_box.scroll_offset());
    });

    m_used_values_store.for_each([&](UsedValues& used_values) {
        auto& node = used_values.node();
        for (auto& paintable : node.paintables()) {
            auto* paintable_box = as_if<Painting::PaintableBox>(paintable.ptr());
            if (!paintable_box)
                continue;

            if (node.is_sticky_position()) {
                // https://drafts.csswg.org/css-position/#insets
                // For sticky positioned boxes, the inset is instead relative to the relevant scrollport’s size.
                // Negative values are allowed.

                auto sticky_insets = make<Painting::StickyInsets>();
                auto const& inset = node.computed_values().inset();

                auto nearest_scrollable_ancestor = paintable_box->nearest_scrollable_ancestor();
                CSSPixelSize scrollport_size;
                if (nearest_scrollable_ancestor)
                    scrollport_size = nearest_scrollable_ancestor->absolute_rect().size();

                if (!inset.top().is_auto())
                    sticky_insets->top = inset.top().to_px_or_zero(node, scrollport_size.height());
                if (!inset.right().is_auto())
                    sticky_insets->right = inset.right().to_px_or_zero(node, scrollport_size.width());
                if (!inset.bottom().is_auto())
                    sticky_insets->bottom = inset.bottom().to_px_or_zero(node, scrollport_size.height());
                if (!inset.left().is_auto())
                    sticky_insets->left = inset.left().to_px_or_zero(node, scrollport_size.width());
                paintable_box->set_sticky_insets(move(sticky_insets));
            }
        }
    });
}

LayoutState::UsedValues& LayoutState::UsedValues::operator=(UsedValues const& other)
{
    if (this == &other)
        return *this;

    offset = other.offset;
    width_constraint = other.width_constraint;
    height_constraint = other.height_constraint;
    margin_left = other.margin_left;
    margin_right = other.margin_right;
    margin_top = other.margin_top;
    margin_bottom = other.margin_bottom;
    border_left = other.border_left;
    border_right = other.border_right;
    border_top = other.border_top;
    border_bottom = other.border_bottom;
    padding_left = other.padding_left;
    padding_right = other.padding_right;
    padding_top = other.padding_top;
    padding_bottom = other.padding_bottom;
    inset_left = other.inset_left;
    inset_right = other.inset_right;
    inset_top = other.inset_top;
    inset_bottom = other.inset_bottom;
    line_boxes = other.line_boxes;
    containing_line_box_fragment = other.containing_line_box_fragment;

    m_node = other.m_node;
    m_containing_block_used_values = other.m_containing_block_used_values;
    m_cumulative_offset = other.m_cumulative_offset;
    m_content_width = other.m_content_width;
    m_content_height = other.m_content_height;
    m_has_definite_width = other.m_has_definite_width;
    m_has_definite_height = other.m_has_definite_height;

    if (other.m_rare)
        m_rare = make<RareData>(*other.m_rare);
    else
        m_rare = nullptr;

    return *this;
}

void LayoutState::UsedValues::set_node(NodeWithStyle const& node, UsedValues const* containing_block_used_values)
{
    m_node = &node;
    m_containing_block_used_values = containing_block_used_values;

    // NOTE: In the code below, we decide if `node` has definite width and/or height.
    //       This attempts to cover all the *general* cases where CSS considers sizes to be definite.
    //       If `node` has definite values for min/max-width or min/max-height and a definite
    //       preferred size in the same axis, we clamp the preferred size here as well.
    //
    //       There are additional cases where CSS considers values to be definite. We model all of
    //       those by having our engine consider sizes to be definite *once they are assigned to
    //       the UsedValues by calling set_content_width() or set_content_height().

    auto const& computed_values = node.computed_values();

    auto adjust_for_box_sizing = [&](CSSPixels unadjusted_pixels, CSS::Size const& computed_size, bool width) -> CSSPixels {
        // box-sizing: content-box and/or automatic size don't require any adjustment.
        if (computed_values.box_sizing() == CSS::BoxSizing::ContentBox || computed_size.is_auto())
            return unadjusted_pixels;

        // box-sizing: border-box requires us to subtract the relevant border and padding from the size.
        CSSPixels border_and_padding;

        if (width) {
            border_and_padding = computed_values.border_left().width
                + computed_values.padding().left().to_px_or_zero(*m_node, containing_block_used_values->content_width())
                + computed_values.border_right().width
                + computed_values.padding().right().to_px_or_zero(*m_node, containing_block_used_values->content_width());
        } else {
            border_and_padding = computed_values.border_top().width
                + computed_values.padding().top().to_px_or_zero(*m_node, containing_block_used_values->content_width())
                + computed_values.border_bottom().width
                + computed_values.padding().bottom().to_px_or_zero(*m_node, containing_block_used_values->content_width());
        }

        return unadjusted_pixels - border_and_padding;
    };

    auto is_definite_size = [&](CSS::Size const& size, CSSPixels& resolved_definite_size, bool width) {
        // A size that can be determined without performing layout; that is,
        // a <length>,
        // a measure of text (without consideration of line-wrapping),
        // a size of the initial containing block,
        // or a <percentage> or other formula (such as the “stretch-fit” sizing of non-replaced blocks [CSS2]) that is resolved solely against definite sizes.

        auto containing_block_has_definite_size = containing_block_used_values ? (width ? containing_block_used_values->has_definite_width() : containing_block_used_values->has_definite_height()) : false;

        if (size.is_auto()) {
            // NOTE: The width of a non-flex-item block is considered definite if it's auto and the containing block has definite width.
            if (width
                && !node.is_floating()
                && !node.is_absolutely_positioned()
                && node.display().is_block_outside()
                && node.parent()
                && !node.parent()->is_floating()
                && (node.parent()->display().is_flow_root_inside()
                    || node.parent()->display().is_flow_inside())) {
                if (containing_block_has_definite_size) {
                    CSSPixels available_width = containing_block_used_values->content_width();
                    resolved_definite_size = clamp_to_max_dimension_value(
                        available_width
                        - margin_left
                        - margin_right
                        - padding_left
                        - padding_right
                        - border_left
                        - border_right);
                    return true;
                }
                return false;
            }
            return false;
        }

        if (size.is_calculated()) {
            CSS::CalculationResolutionContext context {
                .length_resolution_context = CSS::Length::ResolutionContext::for_layout_node(node),
            };
            if (size.calculated().contains_percentage()) {
                if (!containing_block_has_definite_size)
                    return false;
                auto containing_block_size_as_length = width ? containing_block_used_values->content_width() : containing_block_used_values->content_height();
                context.percentage_basis = CSS::Length::make_px(containing_block_size_as_length);
            }
            resolved_definite_size = clamp_to_max_dimension_value(adjust_for_box_sizing(size.calculated().resolve_length(context)->to_px(node), size, width));
            return true;
        }

        if (size.is_length()) {
            VERIFY(!size.is_auto()); // This should have been covered by the Size::is_auto() branch above.
            resolved_definite_size = clamp_to_max_dimension_value(adjust_for_box_sizing(size.length().to_px(node), size, width));
            return true;
        }
        if (size.is_percentage()) {
            if (containing_block_has_definite_size) {
                auto containing_block_size = width ? containing_block_used_values->content_width() : containing_block_used_values->content_height();
                resolved_definite_size = clamp_to_max_dimension_value(adjust_for_box_sizing(containing_block_size.scaled(size.percentage().as_fraction()), size, width));
                return true;
            }
            return false;
        }
        return false;
    };

    CSSPixels min_width = 0;
    bool has_definite_min_width = is_definite_size(computed_values.min_width(), min_width, true);
    CSSPixels max_width = 0;
    bool has_definite_max_width = is_definite_size(computed_values.max_width(), max_width, true);

    CSSPixels min_height = 0;
    bool has_definite_min_height = is_definite_size(computed_values.min_height(), min_height, false);
    CSSPixels max_height = 0;
    bool has_definite_max_height = is_definite_size(computed_values.max_height(), max_height, false);

    m_has_definite_width = is_definite_size(computed_values.width(), m_content_width, true);
    m_has_definite_height = is_definite_size(computed_values.height(), m_content_height, false);

    if (m_has_definite_width) {
        if (has_definite_min_width)
            m_content_width = clamp_to_max_dimension_value(max(min_width, m_content_width));
        if (has_definite_max_width)
            m_content_width = clamp_to_max_dimension_value(min(max_width, m_content_width));
    }

    if (m_has_definite_height) {
        if (has_definite_min_height)
            m_content_height = clamp_to_max_dimension_value(max(min_height, m_content_height));
        if (has_definite_max_height)
            m_content_height = clamp_to_max_dimension_value(min(max_height, m_content_height));
    }
}

void LayoutState::UsedValues::materialize_from_paintable(Painting::PaintableBox const& paintable)
{
    auto const& box_model = paintable.box_model();

    set_content_width(paintable.content_width());
    set_content_height(paintable.content_height());
    m_has_definite_width = true;
    m_has_definite_height = true;

    set_content_offset(paintable.offset());
    m_cumulative_offset = paintable.absolute_rect().location();

    margin_left = box_model.margin.left;
    margin_right = box_model.margin.right;
    margin_top = box_model.margin.top;
    margin_bottom = box_model.margin.bottom;

    padding_left = box_model.padding.left;
    padding_right = box_model.padding.right;
    padding_top = box_model.padding.top;
    padding_bottom = box_model.padding.bottom;

    border_left = box_model.border.left;
    border_right = box_model.border.right;
    border_top = box_model.border.top;
    border_bottom = box_model.border.bottom;

    inset_left = box_model.inset.left;
    inset_right = box_model.inset.right;
    inset_top = box_model.inset.top;
    inset_bottom = box_model.inset.bottom;

    if (auto const* svg_graphics_paintable = as_if<Painting::SVGGraphicsPaintable>(paintable))
        set_computed_svg_transforms(svg_graphics_paintable->computed_transforms());
}

void LayoutState::UsedValues::set_content_width(CSSPixels width)
{
    if (width < 0) {
        // Negative widths are not allowed in CSS. We have a bug somewhere! Clamp to 0 to avoid doing too much damage.
        dbgln_if(LIBWEB_CSS_DEBUG, "FIXME: Layout calculated a negative width for {}: {}", m_node->debug_description(), width);
        width = 0;
    }
    m_content_width = clamp_to_max_dimension_value(width);
    // FIXME: We should not do this! Definiteness of widths should be determined early,
    //        and not changed later (except for some special cases in flex layout..)
    m_has_definite_width = true;
}

void LayoutState::UsedValues::set_content_height(CSSPixels height)
{
    if (height < 0) {
        // Negative heights are not allowed in CSS. We have a bug somewhere! Clamp to 0 to avoid doing too much damage.
        dbgln_if(LIBWEB_CSS_DEBUG, "FIXME: Layout calculated a negative height for {}: {}", m_node->debug_description(), height);
        height = 0;
    }
    m_content_height = clamp_to_max_dimension_value(height);
}

AvailableSize LayoutState::UsedValues::available_width_inside() const
{
    if (width_constraint == SizeConstraint::MinContent)
        return AvailableSize::make_min_content();
    if (width_constraint == SizeConstraint::MaxContent)
        return AvailableSize::make_max_content();
    if (has_definite_width())
        return AvailableSize::make_definite(m_content_width);
    return AvailableSize::make_indefinite();
}

AvailableSize LayoutState::UsedValues::available_height_inside() const
{
    if (height_constraint == SizeConstraint::MinContent)
        return AvailableSize::make_min_content();
    if (height_constraint == SizeConstraint::MaxContent)
        return AvailableSize::make_max_content();
    if (has_definite_height())
        return AvailableSize::make_definite(m_content_height);
    return AvailableSize::make_indefinite();
}

AvailableSpace LayoutState::UsedValues::available_inner_space_or_constraints_from(AvailableSpace const& outer_space) const
{
    auto inner_width = available_width_inside();
    auto inner_height = available_height_inside();

    if (inner_width.is_indefinite() && outer_space.width.is_intrinsic_sizing_constraint())
        inner_width = outer_space.width;
    if (inner_height.is_indefinite() && outer_space.height.is_intrinsic_sizing_constraint())
        inner_height = outer_space.height;
    return AvailableSpace(inner_width, inner_height);
}

void LayoutState::UsedValues::set_indefinite_content_width()
{
    m_has_definite_width = false;
}

void LayoutState::UsedValues::set_indefinite_content_height()
{
    m_has_definite_height = false;
}

}