/*
 * 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/ListItemBox.h>
#include <LibWeb/Layout/ListItemMarkerBox.h>
#include <LibWeb/Layout/SVGSVGBox.h>
#include <LibWeb/Layout/Viewport.h>
#include <LibWeb/Painting/AccumulatedVisualContext.h>
#include <LibWeb/Painting/PaintableWithLines.h>
#include <LibWeb/Painting/SVGForeignObjectPaintable.h>
#include <LibWeb/Painting/SVGGraphicsPaintable.h>
#include <LibWeb/Painting/SVGPathPaintable.h>
#include <LibWeb/Painting/SVGSVGPaintable.h>

namespace Web::Layout {

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

LayoutState::~LayoutState()
{
}

static Painting::LineBoxData line_box_data_for(LineBox const& line_box, size_t line_index)
{
    CSSPixelRect rect;
    bool saw_fragment = false;
    for (auto const& fragment : line_box.fragments()) {
        auto fragment_rect = CSSPixelRect { fragment.offset(), fragment.size() };
        if (saw_fragment)
            rect.unite(fragment_rect);
        else
            rect = fragment_rect;
        saw_fragment = true;
    }

    if (!saw_fragment)
        return { line_index, {} };

    auto writing_mode = line_box.fragments().first().writing_mode();
    if (writing_mode == CSS::WritingMode::HorizontalTb) {
        rect.set_y(line_box.bottom() - line_box.height());
        rect.set_height(line_box.height());
    }

    return { line_index, rect };
}

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

LayoutState::UsedValues& LayoutState::get_mutable(NodeWithStyle const& node)
{
    auto* used_values = m_used_values_store.get(node.layout_index());
    if (!used_values) {
        dbgln("LayoutState::get_mutable: no used values for {}; boxes must be created before their state is read", node.debug_description());
        VERIFY_NOT_REACHED();
    }
    return *used_values;
}

LayoutState::UsedValues const& LayoutState::get(NodeWithStyle const& node) const
{
    auto const* used_values = m_used_values_store.get(node.layout_index());
    if (!used_values) {
        dbgln("LayoutState::get: no used values for {}; boxes must be created before their state is read", node.debug_description());
        VERIFY_NOT_REACHED();
    }
    return *used_values;
}

LayoutState::UsedValues& LayoutState::create(NodeWithStyle const& node, Optional<CSSPixels> percentage_basis_width, Optional<CSSPixels> percentage_basis_height)
{
    auto index = node.layout_index();
    if (m_used_values_store.get(index)) {
        dbgln("LayoutState::create: used values for {} already exist", node.debug_description());
        VERIFY_NOT_REACHED();
    }

    VERIFY(!m_subtree_root || m_subtree_root == &node || m_subtree_root->is_inclusive_ancestor_of(node));

    auto& used_values = m_used_values_store.allocate(index);
    used_values.set_node(node, percentage_basis_width, percentage_basis_height);

    if (auto const* list_item_box = as_if<ListItemBox>(node); list_item_box && list_item_box->marker()) {
        auto const& marker = *list_item_box->marker();
        if (!m_used_values_store.get(marker.layout_index())) {
            auto& marker_used_values = m_used_values_store.allocate(marker.layout_index());
            marker_used_values.set_node(marker,
                used_values.has_definite_width() ? Optional<CSSPixels> { used_values.content_width() } : Optional<CSSPixels> {},
                used_values.has_definite_height() ? Optional<CSSPixels> { used_values.content_height() } : Optional<CSSPixels> {});
        }
    }

    return used_values;
}

void LayoutState::discard_used_values_for_descendants(Box const& root)
{
    root.for_each_in_subtree([&](auto const& descendant) {
        if (auto const* node_with_style = as_if<NodeWithStyle>(descendant))
            m_used_values_store.remove(node_with_style->layout_index());
        return TraversalDecision::Continue;
    });
}

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

    // NOTE: We skip set_node() here since it performs size resolution that requires percentage bases,
    //       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);
    return 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);
}

CSSPixelPoint LayoutState::cumulative_offset(UsedValues const& used_values) const
{
    if (used_values.m_cumulative_offset.has_value())
        return *used_values.m_cumulative_offset;
    if (auto const* containing_block = used_values.node().containing_block())
        return cumulative_offset(get(*containing_block)) + used_values.content_offset();
    return used_values.content_offset();
}

// 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 apply_css_transform_to_overflow_rect(Box const& box, CSSPixelRect const& rect)
{
    auto const& paintable_box = *box.paintable_box();
    auto transform_data = Painting::compute_transform(paintable_box, box.computed_values(), 1.0);
    if (!transform_data.has_value())
        return rect;

    auto affine = Gfx::extract_2d_affine_transform(transform_data->matrix);
    auto transformed_rect = rect.to_type<float>();
    transformed_rect.translate_by(-transform_data->origin);
    transformed_rect = affine.map(transformed_rect);
    transformed_rect.translate_by(transform_data->origin);
    return transformed_rect.to_type<CSSPixels>();
}

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 const paintable_absolute_content_box = paintable_box.absolute_rect();
    auto scrollable_overflow_rect = paintable_absolute_padding_box;

    // Replaced SVG viewports clip their content
    if (is<SVGSVGBox>(box)) {
        const_cast<Painting::Paintable&>(paintable_box).set_overflow_data({
            .scrollable_overflow_rect = scrollable_overflow_rect,
            .has_scrollable_overflow = false,
        });
        return scrollable_overflow_rect;
    }

    auto overflow_directions = physical_overflow_directions(box);
    auto content_overflows_content_box_in_x_axis = false;
    auto content_overflows_content_box_in_y_axis = false;
    auto content_overflows_content_box_on_right = false;
    auto content_overflows_content_box_on_bottom = false;

    auto update_content_overflow_x_axis = [&](CSSPixelRect const& rect) {
        if (rect.left() < paintable_absolute_content_box.left()
            || rect.right() > paintable_absolute_content_box.right()) {
            content_overflows_content_box_in_x_axis = true;
        }
        if (rect.right() > paintable_absolute_content_box.right())
            content_overflows_content_box_on_right = true;
    };

    auto update_content_overflow_y_axis = [&](CSSPixelRect const& rect) {
        if (rect.top() < paintable_absolute_content_box.top()
            || rect.bottom() > paintable_absolute_content_box.bottom()) {
            content_overflows_content_box_in_y_axis = true;
        }
        if (rect.bottom() > paintable_absolute_content_box.bottom())
            content_overflows_content_box_on_bottom = true;
    };

    auto update_content_overflow_axes = [&](CSSPixelRect const& rect) {
        update_content_overflow_x_axis(rect);
        update_content_overflow_y_axis(rect);
    };

    // - 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()) {
            auto fragment_rect = fragment.absolute_rect();
            scrollable_overflow_rect.unite(fragment_rect);
            update_content_overflow_axes(fragment_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 3D 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 = apply_css_transform_to_overflow_rect(child, 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);
                update_content_overflow_axes(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 = apply_css_transform_to_overflow_rect(child, 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);
                        update_content_overflow_x_axis(child_scrollable_overflow);
                    }
                    if (child.computed_values().overflow_y() == CSS::Overflow::Visible) {
                        scrollable_overflow_rect.unite_vertically(child_scrollable_overflow);
                        update_content_overflow_y_axis(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_in_x_axis = box.is_scroll_container()
        && (scrollable_overflow_rect.left() < paintable_absolute_padding_box.left()
            || scrollable_overflow_rect.right() > paintable_absolute_padding_box.right());
    auto has_scrollable_overflow_in_y_axis = box.is_scroll_container()
        && (scrollable_overflow_rect.top() < paintable_absolute_padding_box.top()
            || scrollable_overflow_rect.bottom() > paintable_absolute_padding_box.bottom());
    auto has_scrollable_overflow = has_scrollable_overflow_in_x_axis || has_scrollable_overflow_in_y_axis;
    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 (content_overflows_content_box_in_x_axis) {
            if (overflow_directions.x_positive && content_overflows_content_box_on_right)
                right = max(right, content_overflow_rect.right() + paintable_box.box_model().padding.right);
            else if (!overflow_directions.x_positive)
                left = min(left, content_overflow_rect.x() - paintable_box.box_model().padding.left);
        }

        if (content_overflows_content_box_in_y_axis) {
            if (overflow_directions.y_positive && content_overflows_content_box_on_bottom)
                bottom = max(bottom, content_overflow_rect.bottom() + paintable_box.box_model().padding.bottom);
            else if (!overflow_directions.y_positive)
                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::Paintable&>(paintable_box).set_overflow_data({
        .scrollable_overflow_rect = scrollable_overflow_rect,
        .has_scrollable_overflow = has_scrollable_overflow,
    });

    return scrollable_overflow_rect;
}

struct InlineAncestorChainRelativeOffset {
    CSSPixelPoint offset;
    bool found_inline_node { false };
};

// Accumulates relative position insets from a chain of inline-flow ancestors, starting at first_ancestor
// and walking up until stop_at or the first ancestor that is not inline-flow.
static InlineAncestorChainRelativeOffset accumulated_relative_insets_from_inline_ancestor_chain(Node const* first_ancestor, Node const* stop_at)
{
    InlineAncestorChainRelativeOffset result;
    for (auto const* ancestor = first_ancestor; ancestor && ancestor != stop_at; ancestor = ancestor->parent()) {
        if (!is<Layout::NodeWithStyleAndBoxModelMetrics>(*ancestor))
            break;
        if (!ancestor->display().is_inline_outside() || !ancestor->display().is_flow_inside())
            break;
        result.found_inline_node |= is<Layout::InlineNode>(*ancestor);
        if (ancestor->computed_values().position() == CSS::Positioning::Relative) {
            VERIFY(ancestor->first_paintable());
            auto const& ancestor_paintable_box = *ancestor->first_paintable();
            auto const& inset = ancestor_paintable_box.box_model().inset;
            result.offset.translate_by(inset.left, inset.top);
        }
    }
    return result;
}

void LayoutState::resolve_relative_positions()
{
    // This function resolves relative position offsets contributed by inline-flow ancestor chains, which
    // apply both to fragments that belong to inline paintables and to block-level boxes interrupting an
    // inline (block-in-inline). 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());

        if (auto const* box = as_if<Box>(node); box && box->is_in_flow() && box->display().is_block_outside()) {
            auto accumulated = accumulated_relative_insets_from_inline_ancestor_chain(box->parent(), box->containing_block());
            if (accumulated.found_inline_node) {
                for (auto& paintable : node.paintables()) {
                    auto& paintable_box = *paintable;
                    paintable_box.set_offset(paintable_box.offset().translated(accumulated.offset));
                }
            }
        }

        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 accumulated = accumulated_relative_insets_from_inline_ancestor_chain(fragment.layout_node().parent(), nullptr);
                if (!accumulated.offset.is_zero())
                    const_cast<Painting::PaintableFragment&>(fragment).set_offset(fragment.offset().translated(accumulated.offset));
            }
        }
    });
}

static Optional<size_t> line_index_for_paint_parent_matching(Painting::Paintable const& paintable)
{
    if (auto const* paintable_with_lines = as_if<Painting::PaintableWithLines>(paintable); paintable_with_lines && is<InlineNode>(paintable.layout_node()))
        return paintable_with_lines->line_index();

    if (paintable.containing_line_box_data().has_value())
        return paintable.containing_line_box_data()->index;

    return {};
}

// An InlineNode has one paintable per line it spans; a child paintable must be attached to the parent
// paintable for the line it belongs to, keyed by line index.
static void build_paint_tree(Node& node, Painting::Paintable* fallback_parent_paintable = nullptr, HashMap<size_t, Painting::Paintable*> const* parent_paintable_by_line_index = nullptr)
{
    for (auto& paintable : node.paintables()) {
        auto* parent_paintable = fallback_parent_paintable;
        if (parent_paintable_by_line_index) {
            if (auto line_index = line_index_for_paint_parent_matching(*paintable); line_index.has_value()) {
                if (auto matching_parent = parent_paintable_by_line_index->get(line_index.value()); matching_parent.has_value())
                    parent_paintable = matching_parent.value();
            }
        }
        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);
    }

    if (!node.first_child())
        return;

    HashMap<size_t, Painting::Paintable*> paintable_by_line_index;
    if (is<InlineNode>(node)) {
        for (auto& paintable : node.paintables()) {
            if (auto* paintable_with_lines = as_if<Painting::PaintableWithLines>(paintable.ptr()))
                paintable_by_line_index.set(paintable_with_lines->line_index(), paintable_with_lines);
        }
    }
    for (auto child = node.first_child(); child; child = child->next_sibling()) {
        // An InlineNode without paintables of its own (an anonymous inline whose only children are
        // out-of-flow boxes generates no line fragments) must not orphan its descendants' paintables;
        // pass the nearest ancestor paintable through. Other paintable-less nodes (e.g. non-rendered
        // SVG subtrees) keep their descendants disconnected on purpose.
        auto* fallback_for_children = node.first_paintable() ? node.first_paintable().ptr() : (is<InlineNode>(node) ? fallback_parent_paintable : nullptr);
        build_paint_tree(*child, fallback_for_children, is<InlineNode>(node) ? &paintable_by_line_index : nullptr);
    }
}

void LayoutState::commit(Box& root)
{
    RefPtr<Painting::Paintable> parent_paintable;
    if (!root.is_viewport()) {
        if (auto existing = root.first_paintable(); auto* existing_box = 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::Paintable>> paintable_cache;
    root.for_each_in_inclusive_subtree([&](Node& node) {
        if (auto paintable = node.first_paintable(); auto* paintable_box = 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.set(static_cast<InlineNode*>(&node));
        return TraversalDecision::Continue;
    });

    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, Painting::LineBoxData line_box_data, Painting::Paintable::FragmentationState fragmentation_state) -> bool {
        for (auto const* parent = fragment.layout_node().parent(); parent; parent = parent->parent()) {
            if (!parent->display().is_inline_outside() || !parent->display().is_flow_inside())
                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_box_data.index);
                line_paintable->add_fragment(fragment, line_box_data);
                line_paintable->set_fragmentation_state(fragmentation_state);
                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 = paintable.ptr()) {
            transfer_box_model_metrics(paintable_box->box_model(), used_values);

            paintable_box->set_offset(used_values.content_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];
                    auto line_box_data = line_box_data_for(line_box, line_index);
                    auto first_fragment_continues_last_line_box = false;
                    if (line_index > 0 && used_values.line_boxes[line_index - 1].fragments().size() > 0 && used_values.line_boxes[line_index].fragments().size() > 0) {
                        first_fragment_continues_last_line_box = &used_values.line_boxes[line_index - 1].fragments().last().layout_node() == &used_values.line_boxes[line_index].fragments().first().layout_node();
                    }
                    auto last_fragment_is_continued_in_next_line_box = false;
                    if (line_index < used_values.line_boxes.size() - 1 && used_values.line_boxes[line_index].fragments().size() > 0 && used_values.line_boxes[line_index + 1].fragments().size() > 0) {
                        last_fragment_is_continued_in_next_line_box = &used_values.line_boxes[line_index].fragments().last().layout_node() == &used_values.line_boxes[line_index + 1].fragments().first().layout_node();
                    }
                    for (auto const& fragment : line_box.fragments()) {
                        if (fragment.is_fully_truncated())
                            continue;
                        auto fragmentation_state = Painting::Paintable::FragmentationState::Unfragmented;
                        auto is_first_fragment = &line_box.fragments().first() == &fragment;
                        auto is_last_fragment = &line_box.fragments().last() == &fragment;
                        if (is_first_fragment && is_last_fragment && first_fragment_continues_last_line_box && last_fragment_is_continued_in_next_line_box) {
                            fragmentation_state = Painting::Paintable::FragmentationState::HorizontalMiddle;
                        } else if (is_first_fragment && first_fragment_continues_last_line_box) {
                            fragmentation_state = Painting::Paintable::FragmentationState::HorizontalEnd;
                        } else if (is_last_fragment && last_fragment_is_continued_in_next_line_box) {
                            fragmentation_state = Painting::Paintable::FragmentationState::HorizontalStart;
                        }

                        auto did_relocate_fragment = try_to_relocate_fragment_in_inline_node(fragment, line_box_data, fragmentation_state);
                        first_fragment_continues_last_line_box = false;
                        if (!did_relocate_fragment)
                            paintable_with_lines->add_fragment(fragment, line_box_data);
                    }
                }
            }

            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_foreign_object_paintable = as_if<Painting::SVGForeignObjectPaintable>(paintable.ptr());
                svg_foreign_object_paintable && used_values.computed_svg_transforms().has_value()) {
                svg_foreign_object_paintable->set_computed_transforms(*used_values.computed_svg_transforms());
            }
            if (auto* svg_svg_paintable = as_if<Painting::SVGSVGPaintable>(paintable.ptr());
                svg_svg_paintable && used_values.computed_svg_transforms().has_value()) {
                svg_svg_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());
                paintable_box->set_grid_layout_data(used_values.take_grid_layout_data());
            }

            if (node.display().is_flex_inside()) {
                paintable_box->set_flex_layout_data(used_values.take_flex_layout_data());
            }
        }
    });

    // 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);
    }

    // Ensure anonymous InlineNode ancestors of painted InlineNodes also get paintables. This handles cases like
    // ::first-letter inside ::before, where the first-letter wrapper has a paintable but the ::before InlineNode above
    // it does not.
    for (auto const& paintable : inline_node_paintables.values()) {
        for (auto const* ancestor = paintable->layout_node().parent(); ancestor; ancestor = ancestor->parent()) {
            if (!is<InlineNode>(*ancestor) || ancestor->dom_node())
                break;
            auto& inline_ancestor = const_cast<InlineNode&>(static_cast<InlineNode const&>(*ancestor));
            if (inline_ancestor.first_paintable())
                break;
            auto line_paintable = inline_ancestor.create_paintable_for_line_with_index(paintable->line_index());
            inline_ancestor.add_paintable(line_paintable);
            inline_node_paintables.set(line_paintable.ptr());
            if (auto const* used_values = try_get(inline_ancestor))
                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 = *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);

            // The fragment has the final offset for the atomic inline, so we just need to copy it from there.
            // However, line box post-processing may remove fragments after we record this coordinate.
            if (containing_line_box_fragment.line_box_index < containing_block_used_values.line_boxes.size()) {
                auto const& line_box = containing_block_used_values.line_boxes[containing_line_box_fragment.line_box_index];
                paintable.set_containing_line_box_data(line_box_data_for(line_box, containing_line_box_fragment.line_box_index));
                if (containing_line_box_fragment.fragment_index < line_box.fragments().size())
                    offset = line_box.fragments()[containing_line_box_fragment.fragment_index].offset();
                else
                    offset = used_values.content_offset();
            } else {
                offset = used_values.content_offset();
            }
        } else {
            // Not an atomic inline, much simpler case.
            offset = used_values.content_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);
    });

    build_paint_tree(root, parent_paintable.ptr());

    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;

        if (paintable_with_lines->has_only_block_level_fragments()) {
            paintable_with_lines->set_offset(paintable_with_lines->fragments().first().offset());
            paintable_with_lines->set_content_size({});
            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()) {
                auto use_fragment_offset = !offset.has_value() || (fragments.first().offset().x() < offset->x());
                if (use_fragment_offset) {
                    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 const* containing_block = box->containing_block())
            contained_boxes_map.ensure(containing_block).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::Paintable&>(*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 = 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(scrollport_size.height());
                if (!inset.right().is_auto())
                    sticky_insets->right = inset.right().to_px_or_zero(scrollport_size.width());
                if (!inset.bottom().is_auto())
                    sticky_insets->bottom = inset.bottom().to_px_or_zero(scrollport_size.height());
                if (!inset.left().is_auto())
                    sticky_insets->left = inset.left().to_px_or_zero(scrollport_size.width());
                paintable_box->set_sticky_insets(move(sticky_insets));
            }
        }
    });
}

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

    m_content_offset = other.m_content_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;
    first_baseline = other.first_baseline;
    last_baseline = other.last_baseline;
    containing_line_box_fragment = other.containing_line_box_fragment;

    m_node = other.m_node;
    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, Optional<CSSPixels> percentage_basis_width, Optional<CSSPixels> percentage_basis_height)
{
    m_node = &node;

    // 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 containing_block_size_for_axis = [&](bool width) {
        return width ? percentage_basis_width.value_or(0) : percentage_basis_height.value_or(0);
    };

    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(percentage_basis_width.value_or(0))
                + computed_values.border_right().width
                + computed_values.padding().right().to_px_or_zero(percentage_basis_width.value_or(0));
        } else {
            border_and_padding = computed_values.border_top().width
                + computed_values.padding().top().to_px_or_zero(percentage_basis_width.value_or(0))
                + computed_values.border_bottom().width
                + computed_values.padding().bottom().to_px_or_zero(percentage_basis_width.value_or(0));
        }

        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 = width ? percentage_basis_width.has_value() : percentage_basis_height.has_value();

        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_size_for_axis(true);
                    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_length_percentage()) {
            if (size.contains_percentage()) {
                if (!containing_block_has_definite_size)
                    return false;
                auto containing_block_size_as_length = containing_block_size_for_axis(width);
                resolved_definite_size = clamp_to_max_dimension_value(adjust_for_box_sizing(size.to_px(containing_block_size_as_length), size, width));
                return true;
            }

            resolved_definite_size = clamp_to_max_dimension_value(adjust_for_box_sizing(size.to_px(CSSPixels { 0 }), size, width));
            return true;
        }

        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::Paintable 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;

    m_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());
    if (auto const* svg_foreign_object_paintable = as_if<Painting::SVGForeignObjectPaintable>(paintable))
        set_computed_svg_transforms(svg_foreign_object_paintable->computed_transforms());
    if (auto const* svg_svg_paintable = as_if<Painting::SVGSVGPaintable>(paintable))
        set_computed_svg_transforms(svg_svg_paintable->computed_transforms());
}

void LayoutState::UsedValues::set_content_width(CSSPixels width)
{
    VERIFY(!is_placed());
    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)
{
    VERIFY(!is_placed());
    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;
}

void LayoutState::register_contained_abspos_child(Box const& target, Box const& child, StaticPositionRect const& static_position_rect)
{
    auto& children = m_contained_abspos_children.ensure(&target);
    // The same box can be encountered again when a subtree is intentionally laid out
    // twice (percentage-height table cells); the fresh static position replaces the
    // stale one instead of duplicating the entry. New entries are inserted in layout
    // index order so consumption follows document order.
    size_t insertion_index = children.size();
    for (size_t i = 0; i < children.size(); ++i) {
        if (children[i].box == &child) {
            children[i].static_position_rect = static_position_rect;
            return;
        }
        if (insertion_index == children.size() && child.layout_index() < children[i].box->layout_index())
            insertion_index = i;
    }
    children.insert(insertion_index, { &child, static_position_rect });
}

Optional<LayoutState::ContainedAbsposChild> LayoutState::take_next_contained_abspos_child(Box const& target)
{
    auto it = m_contained_abspos_children.find(&target);
    if (it == m_contained_abspos_children.end())
        return {};
    auto child = it->value.take_first();
    if (it->value.is_empty())
        m_contained_abspos_children.remove(it);
    return child;
}

}