/*
 * Copyright (C) 2017 Igalia S.L.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "GridTrackSizingAlgorithm.h"

#include "Grid.h"
#include "GridArea.h"
#include "RenderGrid.h"

namespace WebCore {

const LayoutUnit& GridTrack::baseSize() const
{
    ASSERT(isGrowthLimitBiggerThanBaseSize());
    return m_baseSize;
}

const LayoutUnit& GridTrack::growthLimit() const
{
    ASSERT(isGrowthLimitBiggerThanBaseSize());
    ASSERT(!m_growthLimitCap || m_growthLimitCap.value() >= m_growthLimit || m_baseSize >= m_growthLimitCap.value());
    return m_growthLimit;
}

void GridTrack::setBaseSize(LayoutUnit baseSize)
{
    m_baseSize = baseSize;
    ensureGrowthLimitIsBiggerThanBaseSize();
}

void GridTrack::setGrowthLimit(LayoutUnit growthLimit)
{
    m_growthLimit = growthLimit == infinity ? growthLimit : std::min(growthLimit, m_growthLimitCap.value_or(growthLimit));
    ensureGrowthLimitIsBiggerThanBaseSize();
}

const LayoutUnit& GridTrack::growthLimitIfNotInfinite() const
{
    ASSERT(isGrowthLimitBiggerThanBaseSize());
    return m_growthLimit == infinity ? m_baseSize : m_growthLimit;
}

void GridTrack::setTempSize(const LayoutUnit& tempSize)
{
    ASSERT(tempSize >= 0);
    ASSERT(growthLimitIsInfinite() || growthLimit() >= tempSize);
    m_tempSize = tempSize;
}

void GridTrack::growTempSize(const LayoutUnit& tempSize)
{
    ASSERT(tempSize >= 0);
    m_tempSize += tempSize;
}

void GridTrack::setGrowthLimitCap(std::optional<LayoutUnit> growthLimitCap)
{
    ASSERT(!growthLimitCap || growthLimitCap.value() >= 0);
    m_growthLimitCap = growthLimitCap;
}

void GridTrack::ensureGrowthLimitIsBiggerThanBaseSize()
{
    if (m_growthLimit != infinity && m_growthLimit < m_baseSize)
        m_growthLimit = m_baseSize;
}

// Static helper methods.

static bool shouldClearOverrideContainingBlockContentSizeForChild(const RenderBox& child, GridTrackSizingDirection direction)
{
    if (direction == ForColumns)
        return child.hasRelativeLogicalWidth() || child.style().logicalWidth().isIntrinsicOrAuto();
    return child.hasRelativeLogicalHeight() || child.style().logicalHeight().isIntrinsicOrAuto();
}

static bool hasOverrideContainingBlockContentSizeForChild(const RenderBox& child, GridTrackSizingDirection direction)
{
    return direction == ForColumns ? child.hasOverrideContainingBlockLogicalWidth() : child.hasOverrideContainingBlockLogicalHeight();
}

static void setOverrideContainingBlockContentSizeForChild(RenderBox& child, GridTrackSizingDirection direction, std::optional<LayoutUnit> size)
{
    if (direction == ForColumns)
        child.setOverrideContainingBlockContentLogicalWidth(size);
    else
        child.setOverrideContainingBlockContentLogicalHeight(size);
}

static GridTrackSizingDirection flowAwareDirectionForChild(const RenderGrid* grid, const RenderBox& child, GridTrackSizingDirection direction)
{
    ASSERT(grid);
    return !grid->isOrthogonalChild(child) ? direction : (direction == ForColumns ? ForRows : ForColumns);
}

static std::optional<LayoutUnit> overrideContainingBlockContentSizeForChild(const RenderBox& child, GridTrackSizingDirection direction)
{
    return direction == ForColumns ? child.overrideContainingBlockContentLogicalWidth() : child.overrideContainingBlockContentLogicalHeight();
}

static LayoutUnit computeMarginLogicalSizeForChild(GridTrackSizingDirection direction, const RenderGrid& renderGrid, const RenderBox& child)
{
    if (!child.style().hasMargin())
        return 0;

    LayoutUnit marginStart;
    LayoutUnit marginEnd;
    if (direction == ForColumns)
        child.computeInlineDirectionMargins(renderGrid, child.containingBlockLogicalWidthForContentInRegion(nullptr), child.logicalWidth(), marginStart, marginEnd);
    else
        child.computeBlockDirectionMargins(renderGrid, marginStart, marginEnd);

    return marginStart + marginEnd;
}

// FIXME: we borrowed this from RenderBlock. We cannot call it from here because it's protected for RenderObjects.
static LayoutUnit marginIntrinsicLogicalWidthForChild(const RenderGrid* renderGrid, RenderBox& child)
{
    // A margin has three types: fixed, percentage, and auto (variable).
    // Auto and percentage margins become 0 when computing min/max width.
    // Fixed margins can be added in as is.
    Length marginLeft = child.style().marginStartUsing(&renderGrid->style());
    Length marginRight = child.style().marginEndUsing(&renderGrid->style());
    LayoutUnit margin = 0;
    if (marginLeft.isFixed())
        margin += marginLeft.value();
    if (marginRight.isFixed())
        margin += marginRight.value();
    return margin;
}

// GridTrackSizingAlgorithm private.

void GridTrackSizingAlgorithm::setFreeSpace(GridTrackSizingDirection direction, std::optional<LayoutUnit> freeSpace)
{
    if (direction == ForColumns)
        m_freeSpaceColumns = freeSpace;
    else
        m_freeSpaceRows = freeSpace;
}

const GridTrackSize& GridTrackSizingAlgorithm::rawGridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex) const
{
    bool isRowAxis = direction == ForColumns;
    auto& renderStyle = m_renderGrid->style();
    auto& trackStyles = isRowAxis ? renderStyle.gridColumns() : renderStyle.gridRows();
    auto& autoRepeatTrackStyles = isRowAxis ? renderStyle.gridAutoRepeatColumns() : renderStyle.gridAutoRepeatRows();
    auto& autoTrackStyles = isRowAxis ? renderStyle.gridAutoColumns() : renderStyle.gridAutoRows();
    unsigned insertionPoint = isRowAxis ? renderStyle.gridAutoRepeatColumnsInsertionPoint() : renderStyle.gridAutoRepeatRowsInsertionPoint();
    unsigned autoRepeatTracksCount = m_grid.autoRepeatTracks(direction);

    // We should not use GridPositionsResolver::explicitGridXXXCount() for this because the
    // explicit grid might be larger than the number of tracks in grid-template-rows|columns (if
    // grid-template-areas is specified for example).
    unsigned explicitTracksCount = trackStyles.size() + autoRepeatTracksCount;

    int untranslatedIndexAsInt = translatedIndex + m_grid.smallestTrackStart(direction);
    unsigned autoTrackStylesSize = autoTrackStyles.size();
    if (untranslatedIndexAsInt < 0) {
        int index = untranslatedIndexAsInt % static_cast<int>(autoTrackStylesSize);
        // We need to traspose the index because the first negative implicit line will get the last defined auto track and so on.
        index += index ? autoTrackStylesSize : 0;
        ASSERT(index >= 0);
        return autoTrackStyles[index];
    }

    unsigned untranslatedIndex = static_cast<unsigned>(untranslatedIndexAsInt);
    if (untranslatedIndex >= explicitTracksCount)
        return autoTrackStyles[(untranslatedIndex - explicitTracksCount) % autoTrackStylesSize];

    if (!autoRepeatTracksCount || untranslatedIndex < insertionPoint)
        return trackStyles[untranslatedIndex];

    if (untranslatedIndex < (insertionPoint + autoRepeatTracksCount)) {
        unsigned autoRepeatLocalIndex = untranslatedIndexAsInt - insertionPoint;
        return autoRepeatTrackStyles[autoRepeatLocalIndex % autoRepeatTrackStyles.size()];
    }

    return trackStyles[untranslatedIndex - autoRepeatTracksCount];
}

LayoutUnit GridTrackSizingAlgorithm::computeTrackBasedSize() const
{
    LayoutUnit size;
    auto& allTracks = tracks(m_direction);
    for (auto& track : allTracks)
        size += track.baseSize();

    size += m_renderGrid->guttersSize(m_grid, m_direction, 0, allTracks.size());

    return size;
}

LayoutUnit GridTrackSizingAlgorithm::initialBaseSize(const GridTrackSize& trackSize) const
{
    const GridLength& gridLength = trackSize.minTrackBreadth();
    if (gridLength.isFlex())
        return 0;

    const Length& trackLength = gridLength.length();
    if (trackLength.isSpecified())
        return valueForLength(trackLength, std::max<LayoutUnit>(m_availableSpace.value_or(0), 0));

    ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
    return 0;
}

LayoutUnit GridTrackSizingAlgorithm::initialGrowthLimit(const GridTrackSize& trackSize, LayoutUnit baseSize) const
{
    const GridLength& gridLength = trackSize.maxTrackBreadth();
    if (gridLength.isFlex())
        return baseSize;

    const Length& trackLength = gridLength.length();
    if (trackLength.isSpecified())
        return valueForLength(trackLength, std::max<LayoutUnit>(m_availableSpace.value_or(0), 0));

    ASSERT(trackLength.isMinContent() || trackLength.isAuto() || trackLength.isMaxContent());
    return infinity;
}

void GridTrackSizingAlgorithm::sizeTrackToFitNonSpanningItem(const GridSpan& span, RenderBox& gridItem, GridTrack& track)
{
    unsigned trackPosition = span.startLine();
    GridTrackSize trackSize = gridTrackSize(m_direction, trackPosition);

    if (trackSize.hasMinContentMinTrackBreadth())
        track.setBaseSize(std::max(track.baseSize(), m_strategy->minContentForChild(gridItem)));
    else if (trackSize.hasMaxContentMinTrackBreadth())
        track.setBaseSize(std::max(track.baseSize(), m_strategy->maxContentForChild(gridItem)));
    else if (trackSize.hasAutoMinTrackBreadth())
        track.setBaseSize(std::max(track.baseSize(), m_strategy->minSizeForChild(gridItem)));

    if (trackSize.hasMinContentMaxTrackBreadth()) {
        track.setGrowthLimit(std::max(track.growthLimit(), m_strategy->minContentForChild(gridItem)));
    } else if (trackSize.hasMaxContentOrAutoMaxTrackBreadth()) {
        LayoutUnit growthLimit = m_strategy->maxContentForChild(gridItem);
        if (trackSize.isFitContent())
            growthLimit = std::min(growthLimit, valueForLength(trackSize.fitContentTrackBreadth().length(), m_availableSpace.value_or(0)));
        track.setGrowthLimit(std::max(track.growthLimit(), growthLimit));
    }
}

bool GridTrackSizingAlgorithm::spanningItemCrossesFlexibleSizedTracks(const GridSpan& itemSpan) const
{
    for (auto trackPosition : itemSpan) {
        const GridTrackSize& trackSize = gridTrackSize(m_direction, trackPosition);
        if (trackSize.minTrackBreadth().isFlex() || trackSize.maxTrackBreadth().isFlex())
            return true;
    }

    return false;
}

class GridItemWithSpan {
public:
    GridItemWithSpan(RenderBox& gridItem, GridSpan span)
        : m_gridItem(gridItem)
        , m_span(span)
    {
    }

    RenderBox& gridItem() const { return m_gridItem; }
    GridSpan span() const { return m_span; }

    bool operator<(const GridItemWithSpan other) const { return m_span.integerSpan() < other.m_span.integerSpan(); }

private:
    std::reference_wrapper<RenderBox> m_gridItem;
    GridSpan m_span;
};

struct GridItemsSpanGroupRange {
    Vector<GridItemWithSpan>::iterator rangeStart;
    Vector<GridItemWithSpan>::iterator rangeEnd;
};

enum TrackSizeRestriction {
    AllowInfinity,
    ForbidInfinity,
};

LayoutUnit GridTrackSizingAlgorithm::itemSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, RenderBox& gridItem) const
{
    switch (phase) {
    case ResolveIntrinsicMinimums:
    case ResolveIntrinsicMaximums:
        return m_strategy->minSizeForChild(gridItem);
    case ResolveContentBasedMinimums:
        return m_strategy->minContentForChild(gridItem);
    case ResolveMaxContentMinimums:
    case ResolveMaxContentMaximums:
        return m_strategy->maxContentForChild(gridItem);
    case MaximizeTracks:
        ASSERT_NOT_REACHED();
        return 0;
    }

    ASSERT_NOT_REACHED();
    return 0;
}

static bool shouldProcessTrackForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
{
    switch (phase) {
    case ResolveIntrinsicMinimums:
        return trackSize.hasIntrinsicMinTrackBreadth();
    case ResolveContentBasedMinimums:
        return trackSize.hasMinOrMaxContentMinTrackBreadth();
    case ResolveMaxContentMinimums:
        return trackSize.hasMaxContentMinTrackBreadth();
    case ResolveIntrinsicMaximums:
        return trackSize.hasIntrinsicMaxTrackBreadth();
    case ResolveMaxContentMaximums:
        return trackSize.hasMaxContentOrAutoMaxTrackBreadth();
    case MaximizeTracks:
        ASSERT_NOT_REACHED();
        return false;
    }

    ASSERT_NOT_REACHED();
    return false;
}

static LayoutUnit trackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track, TrackSizeRestriction restriction)
{
    switch (phase) {
    case ResolveIntrinsicMinimums:
    case ResolveContentBasedMinimums:
    case ResolveMaxContentMinimums:
    case MaximizeTracks:
        return track.baseSize();
    case ResolveIntrinsicMaximums:
    case ResolveMaxContentMaximums:
        return restriction == AllowInfinity ? track.growthLimit() : track.growthLimitIfNotInfinite();
    }

    ASSERT_NOT_REACHED();
    return track.baseSize();
}

static void updateTrackSizeForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
{
    switch (phase) {
    case ResolveIntrinsicMinimums:
    case ResolveContentBasedMinimums:
    case ResolveMaxContentMinimums:
        track.setBaseSize(track.plannedSize());
        return;
    case ResolveIntrinsicMaximums:
    case ResolveMaxContentMaximums:
        track.setGrowthLimit(track.plannedSize());
        return;
    case MaximizeTracks:
        ASSERT_NOT_REACHED();
        return;
    }

    ASSERT_NOT_REACHED();
}

static bool trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(TrackSizeComputationPhase phase, const GridTrackSize& trackSize)
{
    switch (phase) {
    case ResolveIntrinsicMinimums:
    case ResolveContentBasedMinimums:
        return trackSize.hasAutoOrMinContentMinTrackBreadthAndIntrinsicMaxTrackBreadth();
    case ResolveMaxContentMinimums:
        return trackSize.hasMaxContentMinTrackBreadthAndMaxContentMaxTrackBreadth();
    case ResolveIntrinsicMaximums:
    case ResolveMaxContentMaximums:
        return true;
    case MaximizeTracks:
        ASSERT_NOT_REACHED();
        return false;
    }

    ASSERT_NOT_REACHED();
    return false;
}

static void markAsInfinitelyGrowableForTrackSizeComputationPhase(TrackSizeComputationPhase phase, GridTrack& track)
{
    switch (phase) {
    case ResolveIntrinsicMinimums:
    case ResolveContentBasedMinimums:
    case ResolveMaxContentMinimums:
        return;
    case ResolveIntrinsicMaximums:
        if (trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity) == infinity  && track.plannedSize() != infinity)
            track.setInfinitelyGrowable(true);
        return;
    case ResolveMaxContentMaximums:
        if (track.infinitelyGrowable())
            track.setInfinitelyGrowable(false);
        return;
    case MaximizeTracks:
        ASSERT_NOT_REACHED();
        return;
    }

    ASSERT_NOT_REACHED();
}

template <TrackSizeComputationPhase phase>
void GridTrackSizingAlgorithm::increaseSizesToAccommodateSpanningItems(const GridItemsSpanGroupRange& gridItemsWithSpan)
{
    Vector<GridTrack>& allTracks = tracks(m_direction);
    for (const auto& trackIndex : m_contentSizedTracksIndex) {
        GridTrack& track = allTracks[trackIndex];
        track.setPlannedSize(trackSizeForTrackSizeComputationPhase(phase, track, AllowInfinity));
    }

    Vector<GridTrack*> growBeyondGrowthLimitsTracks;
    Vector<GridTrack*> filteredTracks;
    for (auto it = gridItemsWithSpan.rangeStart; it != gridItemsWithSpan.rangeEnd; ++it) {
        GridItemWithSpan& gridItemWithSpan = *it;
        ASSERT(gridItemWithSpan.span().integerSpan() > 1);
        const GridSpan& itemSpan = gridItemWithSpan.span();

        filteredTracks.shrink(0);
        growBeyondGrowthLimitsTracks.shrink(0);
        LayoutUnit spanningTracksSize;
        for (auto trackPosition : itemSpan) {
            const GridTrackSize& trackSize = gridTrackSize(m_direction, trackPosition);
            GridTrack& track = tracks(m_direction)[trackPosition];
            spanningTracksSize += trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
            if (!shouldProcessTrackForTrackSizeComputationPhase(phase, trackSize))
                continue;

            filteredTracks.append(&track);

            if (trackShouldGrowBeyondGrowthLimitsForTrackSizeComputationPhase(phase, trackSize))
                growBeyondGrowthLimitsTracks.append(&track);
        }

        if (filteredTracks.isEmpty())
            continue;

        spanningTracksSize += m_renderGrid->guttersSize(m_grid, m_direction, itemSpan.startLine(), itemSpan.integerSpan());

        LayoutUnit extraSpace = itemSizeForTrackSizeComputationPhase(phase, gridItemWithSpan.gridItem()) - spanningTracksSize;
        extraSpace = std::max<LayoutUnit>(extraSpace, 0);
        auto& tracksToGrowBeyondGrowthLimits = growBeyondGrowthLimitsTracks.isEmpty() ? filteredTracks : growBeyondGrowthLimitsTracks;
        distributeSpaceToTracks<phase>(filteredTracks, &tracksToGrowBeyondGrowthLimits, extraSpace);
    }

    for (const auto& trackIndex : m_contentSizedTracksIndex) {
        GridTrack& track = allTracks[trackIndex];
        markAsInfinitelyGrowableForTrackSizeComputationPhase(phase, track);
        updateTrackSizeForTrackSizeComputationPhase(phase, track);
    }
}

static bool sortByGridTrackGrowthPotential(const GridTrack* track1, const GridTrack* track2)
{
    // This check ensures that we respect the irreflexivity property of the strict weak ordering required by std::sort
    // (forall x: NOT x < x).
    bool track1HasInfiniteGrowthPotentialWithoutCap = track1->infiniteGrowthPotential() && !track1->growthLimitCap();
    bool track2HasInfiniteGrowthPotentialWithoutCap = track2->infiniteGrowthPotential() && !track2->growthLimitCap();

    if (track1HasInfiniteGrowthPotentialWithoutCap && track2HasInfiniteGrowthPotentialWithoutCap)
        return false;

    if (track1HasInfiniteGrowthPotentialWithoutCap || track2HasInfiniteGrowthPotentialWithoutCap)
        return track2HasInfiniteGrowthPotentialWithoutCap;

    LayoutUnit track1Limit = track1->growthLimitCap().value_or(track1->growthLimit());
    LayoutUnit track2Limit = track2->growthLimitCap().value_or(track2->growthLimit());
    return (track1Limit - track1->baseSize()) < (track2Limit - track2->baseSize());
}

static void clampGrowthShareIfNeeded(TrackSizeComputationPhase phase, const GridTrack& track, LayoutUnit& growthShare)
{
    if (phase != ResolveMaxContentMaximums || !track.growthLimitCap())
        return;

    LayoutUnit distanceToCap = track.growthLimitCap().value() - track.tempSize();
    if (distanceToCap <= 0)
        return;

    growthShare = std::min(growthShare, distanceToCap);
}

template <TrackSizeComputationPhase phase>
void GridTrackSizingAlgorithm::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* growBeyondGrowthLimitsTracks, LayoutUnit& freeSpace) const
{
    ASSERT(freeSpace >= 0);

    for (auto* track : tracks)
        track->setTempSize(trackSizeForTrackSizeComputationPhase(phase, *track, ForbidInfinity));

    if (freeSpace > 0) {
        std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);

        unsigned tracksSize = tracks.size();
        for (unsigned i = 0; i < tracksSize; ++i) {
            GridTrack& track = *tracks[i];
            const LayoutUnit& trackBreadth = trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
            bool infiniteGrowthPotential = track.infiniteGrowthPotential();
            LayoutUnit trackGrowthPotential = infiniteGrowthPotential ? track.growthLimit() : track.growthLimit() - trackBreadth;
            // Let's avoid computing availableLogicalSpaceShare as much as possible as it's a hot spot in performance tests.
            if (trackGrowthPotential > 0 || infiniteGrowthPotential) {
                LayoutUnit availableLogicalSpaceShare = freeSpace / (tracksSize - i);
                LayoutUnit growthShare = infiniteGrowthPotential ? availableLogicalSpaceShare : std::min(availableLogicalSpaceShare, trackGrowthPotential);
                clampGrowthShareIfNeeded(phase, track, growthShare);
                ASSERT_WITH_MESSAGE(growthShare >= 0, "We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function. We can still have 0 as growthShare if the amount of tracks greatly exceeds the freeSpace.");
                track.growTempSize(growthShare);
                freeSpace -= growthShare;
            }
        }
    }

    if (freeSpace > 0 && growBeyondGrowthLimitsTracks) {
        // We need to sort them because there might be tracks with growth limit caps (like the ones
        // with fit-content()) which cannot indefinitely grow over the limits.
        if (phase == ResolveMaxContentMaximums)
            std::sort(growBeyondGrowthLimitsTracks->begin(), growBeyondGrowthLimitsTracks->end(), sortByGridTrackGrowthPotential);

        unsigned tracksGrowingBeyondGrowthLimitsSize = growBeyondGrowthLimitsTracks->size();
        for (unsigned i = 0; i < tracksGrowingBeyondGrowthLimitsSize; ++i) {
            GridTrack* track = growBeyondGrowthLimitsTracks->at(i);
            LayoutUnit growthShare = freeSpace / (tracksGrowingBeyondGrowthLimitsSize - i);
            clampGrowthShareIfNeeded(phase, *track, growthShare);
            track->growTempSize(growthShare);
            freeSpace -= growthShare;
        }
    }

    for (auto* track : tracks)
        track->setPlannedSize(track->plannedSize() == infinity ? track->tempSize() : std::max(track->plannedSize(), track->tempSize()));
}

LayoutUnit GridTrackSizingAlgorithm::assumedRowsSizeForOrthogonalChild(const RenderBox& child) const
{
    ASSERT(m_renderGrid->isOrthogonalChild(child));
    const GridSpan& span = m_grid.gridItemSpan(child, ForRows);
    LayoutUnit gridAreaSize;
    bool gridAreaIsIndefinite = false;
    LayoutUnit containingBlockAvailableSize = m_renderGrid->containingBlockLogicalHeightForContent(ExcludeMarginBorderPadding);
    for (auto trackPosition : span) {
        GridLength maxTrackSize = gridTrackSize(ForRows, trackPosition).maxTrackBreadth();
        if (maxTrackSize.isContentSized() || maxTrackSize.isFlex())
            gridAreaIsIndefinite = true;
        else
            gridAreaSize += valueForLength(maxTrackSize.length(), containingBlockAvailableSize);
    }

    gridAreaSize += m_renderGrid->guttersSize(m_grid, ForRows, span.startLine(), span.integerSpan());

    return gridAreaIsIndefinite ? std::max(child.maxPreferredLogicalWidth(), gridAreaSize) : gridAreaSize;
}

LayoutUnit GridTrackSizingAlgorithm::gridAreaBreadthForChild(const RenderBox& child, GridTrackSizingDirection direction) const
{
    // To determine the column track's size based on an orthogonal grid item we need it's logical
    // height, which may depend on the row track's size. It's possible that the row tracks sizing
    // logic has not been performed yet, so we will need to do an estimation.
    if (direction == ForRows && m_sizingState == ColumnSizingFirstIteration)
        return assumedRowsSizeForOrthogonalChild(child);

    const Vector<GridTrack>& allTracks = tracks(direction);
    const GridSpan& span = m_grid.gridItemSpan(child, direction);
    LayoutUnit gridAreaBreadth = 0;
    for (auto trackPosition : span)
        gridAreaBreadth += allTracks[trackPosition].baseSize();

    gridAreaBreadth += m_renderGrid->guttersSize(m_grid, direction, span.startLine(), span.integerSpan());

    return gridAreaBreadth;
}

GridTrackSize GridTrackSizingAlgorithm::gridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex, SizingOperation sizingOperation) const
{
    // Collapse empty auto repeat tracks if auto-fit.
    if (m_grid.hasAutoRepeatEmptyTracks(direction) && m_grid.isEmptyAutoRepeatTrack(direction, translatedIndex))
        return { Length(Fixed), LengthTrackSizing };

    auto& trackSize = rawGridTrackSize(direction, translatedIndex);
    if (trackSize.isFitContent())
        return trackSize;

    GridLength minTrackBreadth = trackSize.minTrackBreadth();
    GridLength maxTrackBreadth = trackSize.maxTrackBreadth();

    // FIXME: Ensure this condition for determining whether a size is indefinite or not is working
    // correctly for orthogonal flows.
    if (minTrackBreadth.isPercentage() || maxTrackBreadth.isPercentage()) {
        // If the logical width/height of the grid container is indefinite, percentage values are
        // treated as <auto>. For the inline axis this only happens when we're computing the
        // intrinsic sizes (IntrinsicSizeComputation).
        if (sizingOperation == IntrinsicSizeComputation || (direction == ForRows && !m_renderGrid->hasDefiniteLogicalHeight())) {
            if (minTrackBreadth.isPercentage())
                minTrackBreadth = Length(Auto);
            if (maxTrackBreadth.isPercentage())
                maxTrackBreadth = Length(Auto);
        }
    }

    // Flex sizes are invalid as a min sizing function. However we still can have a flexible |minTrackBreadth|
    // if the track size is just a flex size (e.g. "1fr"), the spec says that in this case it implies an automatic minimum.
    if (minTrackBreadth.isFlex())
        minTrackBreadth = Length(Auto);

    return GridTrackSize(minTrackBreadth, maxTrackBreadth);
}

double GridTrackSizingAlgorithm::computeFlexFactorUnitSize(const Vector<GridTrack>& tracks, double flexFactorSum, LayoutUnit& leftOverSpace, const Vector<unsigned, 8>& flexibleTracksIndexes, std::unique_ptr<TrackIndexSet> tracksToTreatAsInflexible) const
{
    // We want to avoid the effect of flex factors sum below 1 making the factor unit size to grow exponentially.
    double hypotheticalFactorUnitSize = leftOverSpace / std::max<double>(1, flexFactorSum);

    // product of the hypothetical "flex factor unit" and any flexible track's "flex factor" must be grater than such track's "base size".
    bool validFlexFactorUnit = true;
    for (auto index : flexibleTracksIndexes) {
        if (tracksToTreatAsInflexible && tracksToTreatAsInflexible->contains(index))
            continue;
        LayoutUnit baseSize = tracks[index].baseSize();
        double flexFactor = gridTrackSize(m_direction, index).maxTrackBreadth().flex();
        // treating all such tracks as inflexible.
        if (baseSize > hypotheticalFactorUnitSize * flexFactor) {
            leftOverSpace -= baseSize;
            flexFactorSum -= flexFactor;
            if (!tracksToTreatAsInflexible)
                tracksToTreatAsInflexible = std::unique_ptr<TrackIndexSet>(new TrackIndexSet());
            tracksToTreatAsInflexible->add(index);
            validFlexFactorUnit = false;
        }
    }
    if (!validFlexFactorUnit)
        return computeFlexFactorUnitSize(tracks, flexFactorSum, leftOverSpace, flexibleTracksIndexes, WTFMove(tracksToTreatAsInflexible));
    return hypotheticalFactorUnitSize;
}

void GridTrackSizingAlgorithm::computeFlexSizedTracksGrowth(double flexFraction, Vector<LayoutUnit>& increments, LayoutUnit& totalGrowth) const
{
    size_t numFlexTracks = m_flexibleSizedTracksIndex.size();
    ASSERT(increments.size() == numFlexTracks);
    const Vector<GridTrack>& allTracks = tracks(m_direction);
    for (size_t i = 0; i < numFlexTracks; ++i) {
        unsigned trackIndex = m_flexibleSizedTracksIndex[i];
        auto trackSize = gridTrackSize(m_direction, trackIndex);
        ASSERT(trackSize.maxTrackBreadth().isFlex());
        LayoutUnit oldBaseSize = allTracks[trackIndex].baseSize();
        LayoutUnit newBaseSize = std::max(oldBaseSize, LayoutUnit(flexFraction * trackSize.maxTrackBreadth().flex()));
        increments[i] = newBaseSize - oldBaseSize;
        totalGrowth += increments[i];
    }
}

double GridTrackSizingAlgorithm::findFrUnitSize(const GridSpan& tracksSpan, LayoutUnit leftOverSpace) const
{
    if (leftOverSpace <= 0)
        return 0;

    const Vector<GridTrack>& allTracks = tracks(m_direction);
    double flexFactorSum = 0;
    Vector<unsigned, 8> flexibleTracksIndexes;
    for (auto trackIndex : tracksSpan) {
        GridTrackSize trackSize = gridTrackSize(m_direction, trackIndex);
        if (!trackSize.maxTrackBreadth().isFlex())
            leftOverSpace -= allTracks[trackIndex].baseSize();
        else {
            double flexFactor = trackSize.maxTrackBreadth().flex();
            flexibleTracksIndexes.append(trackIndex);
            flexFactorSum += flexFactor;
        }
    }

    // The function is not called if we don't have <flex> grid tracks.
    ASSERT(!flexibleTracksIndexes.isEmpty());

    return computeFlexFactorUnitSize(allTracks, flexFactorSum, leftOverSpace, flexibleTracksIndexes);
}

void GridTrackSizingAlgorithm::computeGridContainerIntrinsicSizes()
{
    m_minContentSize = m_maxContentSize = LayoutUnit();

    Vector<GridTrack>& allTracks = tracks(m_direction);
    for (auto& track : allTracks) {
        ASSERT(!track.infiniteGrowthPotential());
        m_minContentSize += track.baseSize();
        m_maxContentSize += track.growthLimit();
        // The growth limit caps must be cleared now in order to properly sort
        // tracks by growth potential on an eventual "Maximize Tracks".
        track.setGrowthLimitCap(std::nullopt);
    }
}

// GridTrackSizingAlgorithmStrategy.
LayoutUnit GridTrackSizingAlgorithmStrategy::logicalHeightForChild(RenderBox& child) const
{
    GridTrackSizingDirection childBlockDirection = flowAwareDirectionForChild(renderGrid(), child, ForRows);
    // If |child| has a relative logical height, we shouldn't let it override its intrinsic height, which is
    // what we are interested in here. Thus we need to set the block-axis override size to -1 (no possible resolution).
    if (shouldClearOverrideContainingBlockContentSizeForChild(child, ForRows)) {
        setOverrideContainingBlockContentSizeForChild(child, childBlockDirection, std::nullopt);
        child.setNeedsLayout(MarkOnlyThis);
    }

    // We need to clear the stretched height to properly compute logical height during layout.
    if (child.needsLayout())
        child.clearOverrideLogicalContentHeight();

    child.layoutIfNeeded();
    return child.logicalHeight() + child.marginLogicalHeight();
}

LayoutUnit GridTrackSizingAlgorithmStrategy::minContentForChild(RenderBox& child) const
{
    GridTrackSizingDirection childInlineDirection = flowAwareDirectionForChild(renderGrid(), child, ForColumns);
    if (direction() == childInlineDirection) {
        // If |child| has a relative logical width, we shouldn't let it override its intrinsic width, which is
        // what we are interested in here. Thus we need to set the override logical width to std::nullopt (no possible resolution).
        if (shouldClearOverrideContainingBlockContentSizeForChild(child, ForColumns))
            setOverrideContainingBlockContentSizeForChild(child, childInlineDirection, std::nullopt);

        // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
        // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
        return child.minPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(renderGrid(), child);
    }

    // All orthogonal flow boxes were already laid out during an early layout phase performed in FrameView::performLayout.
    // It's true that grid track sizing was not completed at that time and it may afffect the final height of a
    // grid item, but since it's forbidden to perform a layout during intrinsic width computation, we have to use
    // that computed height for now.
    if (direction() == ForColumns && m_algorithm.m_sizingOperation == IntrinsicSizeComputation) {
        ASSERT(renderGrid()->isOrthogonalChild(child));
        return child.logicalHeight() + child.marginLogicalHeight();
    }

    if (updateOverrideContainingBlockContentSizeForChild(child, childInlineDirection))
        child.setNeedsLayout(MarkOnlyThis);
    return logicalHeightForChild(child);
}

LayoutUnit GridTrackSizingAlgorithmStrategy::maxContentForChild(RenderBox& child) const
{
    GridTrackSizingDirection childInlineDirection = flowAwareDirectionForChild(renderGrid(), child, ForColumns);
    if (direction() == childInlineDirection) {
        // If |child| has a relative logical width, we shouldn't let it override its intrinsic width, which is
        // what we are interested in here. Thus we need to set the inline-axis override size to -1 (no possible resolution).
        if (shouldClearOverrideContainingBlockContentSizeForChild(child, ForColumns))
            setOverrideContainingBlockContentSizeForChild(child, childInlineDirection, std::nullopt);

        // FIXME: It's unclear if we should return the intrinsic width or the preferred width.
        // See http://lists.w3.org/Archives/Public/www-style/2013Jan/0245.html
        return child.maxPreferredLogicalWidth() + marginIntrinsicLogicalWidthForChild(renderGrid(), child);
        return child.maxPreferredLogicalWidth();
    }

    // All orthogonal flow boxes were already laid out during an early layout phase performed in
    // FrameView::performLayout. It's true that grid track sizing was not completed at that time
    // and it may afffect the final height of a grid item, but since it's forbidden to perform a
    // layout during intrinsic width computation, we have to use that computed height for now.
    if (direction() == ForColumns && m_algorithm.m_sizingOperation == IntrinsicSizeComputation) {
        ASSERT(renderGrid()->isOrthogonalChild(child));
        return child.logicalHeight() + child.marginLogicalHeight();
    }

    if (updateOverrideContainingBlockContentSizeForChild(child, childInlineDirection))
        child.setNeedsLayout(MarkOnlyThis);
    return logicalHeightForChild(child);
}

LayoutUnit GridTrackSizingAlgorithmStrategy::minSizeForChild(RenderBox& child) const
{
    GridTrackSizingDirection childInlineDirection = flowAwareDirectionForChild(renderGrid(), child, ForColumns);
    bool isRowAxis = direction() == childInlineDirection;
    const Length& childMinSize = isRowAxis ? child.style().logicalMinWidth() : child.style().logicalMinHeight();
    const Length& childSize = isRowAxis ? child.style().logicalWidth() : child.style().logicalHeight();
    if (!childSize.isAuto() || childMinSize.isAuto())
        return minContentForChild(child);

    bool overrideSizeHasChanged = updateOverrideContainingBlockContentSizeForChild(child, childInlineDirection);

    if (isRowAxis)
        return minLogicalWidthForChild(child, childMinSize, childInlineDirection);

    layoutGridItemForMinSizeComputation(child, overrideSizeHasChanged);

    return child.computeLogicalHeightUsing(MinSize, childMinSize, std::nullopt).value_or(0) + child.marginLogicalHeight() + child.scrollbarLogicalHeight();
}

bool GridTrackSizingAlgorithmStrategy::updateOverrideContainingBlockContentSizeForChild(RenderBox& child, GridTrackSizingDirection direction) const
{
    LayoutUnit overrideSize = m_algorithm.gridAreaBreadthForChild(child, direction);
    if (hasOverrideContainingBlockContentSizeForChild(child, direction) && overrideContainingBlockContentSizeForChild(child, direction) == overrideSize)
        return false;

    setOverrideContainingBlockContentSizeForChild(child, direction, overrideSize);
    return true;
}

class IndefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
public:
    IndefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
        : GridTrackSizingAlgorithmStrategy(algorithm) { }

private:
    LayoutUnit minLogicalWidthForChild(RenderBox&, Length childMinSize, GridTrackSizingDirection) const override;
    void layoutGridItemForMinSizeComputation(RenderBox&, bool overrideSizeHasChanged) const override;
    void maximizeTracks(Vector<GridTrack>&, std::optional<LayoutUnit>& freeSpace) override;
    double findUsedFlexFraction(Vector<unsigned>& flexibleSizedTracksIndex, GridTrackSizingDirection, std::optional<LayoutUnit> freeSpace) const override;
    bool recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const override;
};

LayoutUnit IndefiniteSizeStrategy::minLogicalWidthForChild(RenderBox& child, Length childMinSize, GridTrackSizingDirection childInlineDirection) const
{
    return child.computeLogicalWidthInRegionUsing(MinSize, childMinSize, overrideContainingBlockContentSizeForChild(child, childInlineDirection).value_or(0), *renderGrid(), nullptr) + marginIntrinsicLogicalWidthForChild(renderGrid(), child);
}

void IndefiniteSizeStrategy::layoutGridItemForMinSizeComputation(RenderBox& child, bool overrideSizeHasChanged) const
{
    if (overrideSizeHasChanged && direction() != ForColumns)
        child.setNeedsLayout(MarkOnlyThis);
    child.layoutIfNeeded();
}

void IndefiniteSizeStrategy::maximizeTracks(Vector<GridTrack>& tracks, std::optional<LayoutUnit>& freeSpace)
{
    UNUSED_PARAM(freeSpace);
    for (auto& track : tracks)
        track.setBaseSize(track.growthLimit());
}


static inline double normalizedFlexFraction(const GridTrack& track, double flexFactor)
{
    return track.baseSize() / std::max<double>(1, flexFactor);
}

double IndefiniteSizeStrategy::findUsedFlexFraction(Vector<unsigned>& flexibleSizedTracksIndex, GridTrackSizingDirection direction, std::optional<LayoutUnit> freeSpace) const
{
    UNUSED_PARAM(freeSpace);
    auto allTracks = m_algorithm.tracks(direction);

    double flexFraction = 0;
    for (const auto& trackIndex : flexibleSizedTracksIndex) {
        // FIXME: we pass TrackSizing to gridTrackSize() because it does not really matter
        // as we know the track is a flex sized track. It'd be nice not to have to do that.
        flexFraction = std::max(flexFraction, normalizedFlexFraction(allTracks[trackIndex], m_algorithm.gridTrackSize(direction, trackIndex, TrackSizing).maxTrackBreadth().flex()));
    }

    const Grid& grid = m_algorithm.grid();
    if (!grid.hasGridItems())
        return flexFraction;

    for (unsigned i = 0; i < flexibleSizedTracksIndex.size(); ++i) {
        GridIterator iterator(grid, direction, flexibleSizedTracksIndex[i]);
        while (auto* gridItem = iterator.nextGridItem()) {
            const GridSpan& span = grid.gridItemSpan(*gridItem, direction);

            // Do not include already processed items.
            if (i > 0 && span.startLine() <= flexibleSizedTracksIndex[i - 1])
                continue;

            flexFraction = std::max(flexFraction, findFrUnitSize(span, maxContentForChild(*gridItem)));
        }
    }

    return flexFraction;
}

bool IndefiniteSizeStrategy::recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const
{
    if (direction() == ForColumns)
        return false;

    const RenderGrid* renderGrid = this->renderGrid();

    auto minSize = renderGrid->computeContentLogicalHeight(MinSize, renderGrid->style().logicalMinHeight(), std::nullopt);
    auto maxSize = renderGrid->computeContentLogicalHeight(MaxSize, renderGrid->style().logicalMaxHeight(), std::nullopt);

    // Redo the flex fraction computation using min|max-height as definite available space in case
    // the total height is smaller than min-height or larger than max-height.
    LayoutUnit rowsSize = totalGrowth + computeTrackBasedSize();
    bool checkMinSize = minSize && rowsSize < minSize.value();
    bool checkMaxSize = maxSize && rowsSize > maxSize.value();
    if (!checkMinSize && !checkMaxSize)
        return false;

    LayoutUnit freeSpace = checkMaxSize ? maxSize.value() : LayoutUnit(-1);
    const Grid& grid = m_algorithm.grid();
    freeSpace = std::max(freeSpace, minSize.value()) - renderGrid->guttersSize(grid, ForRows, 0, grid.numTracks(ForRows));

    size_t numberOfTracks = m_algorithm.tracks(ForRows).size();
    flexFraction = findFrUnitSize(GridSpan::translatedDefiniteGridSpan(0, numberOfTracks), freeSpace);
    return true;
}

class DefiniteSizeStrategy final : public GridTrackSizingAlgorithmStrategy {
public:
    DefiniteSizeStrategy(GridTrackSizingAlgorithm& algorithm)
        : GridTrackSizingAlgorithmStrategy(algorithm) { }

private:
    LayoutUnit minLogicalWidthForChild(RenderBox&, Length childMinSize, GridTrackSizingDirection) const override;
    void layoutGridItemForMinSizeComputation(RenderBox&, bool overrideSizeHasChanged) const override;
    void maximizeTracks(Vector<GridTrack>&, std::optional<LayoutUnit>& freeSpace) override;
    double findUsedFlexFraction(Vector<unsigned>& flexibleSizedTracksIndex, GridTrackSizingDirection, std::optional<LayoutUnit> freeSpace) const override;
    bool recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const override;
};

LayoutUnit DefiniteSizeStrategy::minLogicalWidthForChild(RenderBox& child, Length childMinSize, GridTrackSizingDirection childInlineDirection) const
{
    LayoutUnit marginLogicalWidth =
        computeMarginLogicalSizeForChild(childInlineDirection, *renderGrid(), child);
    return child.computeLogicalWidthInRegionUsing(MinSize, childMinSize, overrideContainingBlockContentSizeForChild(child, childInlineDirection).value_or(0), *renderGrid(), nullptr) + marginLogicalWidth;
}

void DefiniteSizeStrategy::maximizeTracks(Vector<GridTrack>& tracks, std::optional<LayoutUnit>& freeSpace)
{
    size_t tracksSize = tracks.size();
    Vector<GridTrack*> tracksForDistribution(tracksSize);
    for (size_t i = 0; i < tracksSize; ++i) {
        tracksForDistribution[i] = tracks.data() + i;
        tracksForDistribution[i]->setPlannedSize(tracksForDistribution[i]->baseSize());
    }

    ASSERT(freeSpace);
    distributeSpaceToTracks(tracksForDistribution, freeSpace.value());

    for (auto* track : tracksForDistribution)
        track->setBaseSize(track->plannedSize());
}


void DefiniteSizeStrategy::layoutGridItemForMinSizeComputation(RenderBox& child, bool overrideSizeHasChanged) const
{
    if (overrideSizeHasChanged)
        child.setNeedsLayout(MarkOnlyThis);
    child.layoutIfNeeded();
}

double DefiniteSizeStrategy::findUsedFlexFraction(Vector<unsigned>&, GridTrackSizingDirection direction, std::optional<LayoutUnit> freeSpace) const
{
    GridSpan allTracksSpan = GridSpan::translatedDefiniteGridSpan(0, m_algorithm.tracks(direction).size());
    ASSERT(freeSpace);
    return findFrUnitSize(allTracksSpan, freeSpace.value());
}

bool DefiniteSizeStrategy::recomputeUsedFlexFractionIfNeeded(double& flexFraction, LayoutUnit& totalGrowth) const
{
    UNUSED_PARAM(flexFraction);
    UNUSED_PARAM(totalGrowth);
    return false;
}

// GridTrackSizingAlgorithm steps.

void GridTrackSizingAlgorithm::initializeTrackSizes()
{
    ASSERT(m_contentSizedTracksIndex.isEmpty());
    ASSERT(m_flexibleSizedTracksIndex.isEmpty());

    Vector<GridTrack>& allTracks = tracks(m_direction);
    const bool hasDefiniteFreeSpace = !!m_availableSpace;
    LayoutUnit maxSize = std::max(LayoutUnit(), m_availableSpace.value_or(LayoutUnit()));
    // 1. Initialize per Grid track variables.
    for (unsigned i = 0; i < allTracks.size(); ++i) {
        GridTrack& track = allTracks[i];
        const GridTrackSize& trackSize = gridTrackSize(m_direction, i);

        track.setBaseSize(initialBaseSize(trackSize));
        track.setGrowthLimit(initialGrowthLimit(trackSize, track.baseSize()));
        track.setInfinitelyGrowable(false);

        if (trackSize.isFitContent()) {
            GridLength gridLength = trackSize.fitContentTrackBreadth();
            if (!gridLength.isPercentage() || hasDefiniteFreeSpace)
                track.setGrowthLimitCap(valueForLength(gridLength.length(), maxSize));
        }
        if (trackSize.isContentSized())
            m_contentSizedTracksIndex.append(i);
        if (trackSize.maxTrackBreadth().isFlex())
            m_flexibleSizedTracksIndex.append(i);
    }
}

void GridTrackSizingAlgorithm::resolveIntrinsicTrackSizes()
{
    Vector<GridItemWithSpan> itemsSortedByIncreasingSpan;
    HashSet<RenderBox*> itemsSet;
    Vector<GridTrack>& allTracks = tracks(m_direction);
    if (m_grid.hasGridItems()) {
        for (auto trackIndex : m_contentSizedTracksIndex) {
            GridIterator iterator(m_grid, m_direction, trackIndex);
            GridTrack& track = allTracks[trackIndex];

            while (auto* gridItem = iterator.nextGridItem()) {
                if (itemsSet.add(gridItem).isNewEntry) {
                    const GridSpan& span = m_grid.gridItemSpan(*gridItem, m_direction);
                    if (span.integerSpan() == 1)
                        sizeTrackToFitNonSpanningItem(span, *gridItem, track);
                    else if (!spanningItemCrossesFlexibleSizedTracks(span))
                        itemsSortedByIncreasingSpan.append(GridItemWithSpan(*gridItem, span));
                }
            }
        }
        std::sort(itemsSortedByIncreasingSpan.begin(), itemsSortedByIncreasingSpan.end());
    }

    auto it = itemsSortedByIncreasingSpan.begin();
    auto end = itemsSortedByIncreasingSpan.end();
    while (it != end) {
        GridItemsSpanGroupRange spanGroupRange = { it, std::upper_bound(it, end, *it) };
        increaseSizesToAccommodateSpanningItems<ResolveIntrinsicMinimums>(spanGroupRange);
        increaseSizesToAccommodateSpanningItems<ResolveContentBasedMinimums>(spanGroupRange);
        increaseSizesToAccommodateSpanningItems<ResolveMaxContentMinimums>(spanGroupRange);
        increaseSizesToAccommodateSpanningItems<ResolveIntrinsicMaximums>(spanGroupRange);
        increaseSizesToAccommodateSpanningItems<ResolveMaxContentMaximums>(spanGroupRange);
        it = spanGroupRange.rangeEnd;
    }

    for (auto trackIndex : m_contentSizedTracksIndex) {
        GridTrack& track = allTracks[trackIndex];
        if (track.growthLimit() == infinity)
            track.setGrowthLimit(track.baseSize());
    }
}

void GridTrackSizingAlgorithm::stretchFlexibleTracks(std::optional<LayoutUnit> freeSpace)
{
    double flexFraction = m_strategy->findUsedFlexFraction(m_flexibleSizedTracksIndex, m_direction, freeSpace);

    LayoutUnit totalGrowth;
    Vector<LayoutUnit> increments;
    increments.grow(m_flexibleSizedTracksIndex.size());
    computeFlexSizedTracksGrowth(flexFraction, increments, totalGrowth);

    if (m_strategy->recomputeUsedFlexFractionIfNeeded(flexFraction, totalGrowth)) {
        totalGrowth = LayoutUnit();
        computeFlexSizedTracksGrowth(flexFraction, increments, totalGrowth);
    }

    size_t i = 0;
    Vector<GridTrack>& allTracks = tracks(m_direction);
    for (auto trackIndex : m_flexibleSizedTracksIndex) {
        auto& track = allTracks[trackIndex];
        if (LayoutUnit increment = increments[i++])
            track.setBaseSize(track.baseSize() + increment);
    }
    if (this->freeSpace(m_direction))
        setFreeSpace(m_direction, this->freeSpace(m_direction).value() - totalGrowth);
    m_maxContentSize += totalGrowth;
}

void GridTrackSizingAlgorithm::advanceNextState()
{
    switch (m_sizingState) {
    case ColumnSizingFirstIteration:
        m_sizingState = RowSizingFirstIteration;
        return;
    case RowSizingFirstIteration:
        m_sizingState = ColumnSizingSecondIteration;
        return;
    case ColumnSizingSecondIteration:
        m_sizingState = RowSizingSecondIteration;
        return;
    case RowSizingSecondIteration:
        m_sizingState = ColumnSizingFirstIteration;
        return;
    }
    ASSERT_NOT_REACHED();
    m_sizingState = ColumnSizingFirstIteration;
}

bool GridTrackSizingAlgorithm::isValidTransition() const
{
    switch (m_sizingState) {
    case ColumnSizingFirstIteration:
    case ColumnSizingSecondIteration:
        return m_direction == ForColumns;
    case RowSizingFirstIteration:
    case RowSizingSecondIteration:
        return m_direction == ForRows;
    }
    ASSERT_NOT_REACHED();
    return false;
}

// GridTrackSizingAlgorithm API.

void GridTrackSizingAlgorithm::setup(GridTrackSizingDirection direction, unsigned numTracks, SizingOperation sizingOperation, std::optional<LayoutUnit> availableSpace, std::optional<LayoutUnit> freeSpace)
{
    ASSERT(m_needsSetup);
    m_direction = direction;
    m_availableSpace = availableSpace;

    m_sizingOperation = sizingOperation;
    switch (m_sizingOperation) {
    case IntrinsicSizeComputation:
        m_strategy = std::make_unique<IndefiniteSizeStrategy>(*this);
        break;
    case TrackSizing:
        m_strategy = std::make_unique<DefiniteSizeStrategy>(*this);
        break;
    }

    m_contentSizedTracksIndex.shrink(0);
    m_flexibleSizedTracksIndex.shrink(0);

    setFreeSpace(direction, freeSpace);
    tracks(direction).resize(numTracks);

    m_needsSetup = false;
}

void GridTrackSizingAlgorithm::run()
{
    StateMachine stateMachine(*this);

    // Step 1.
    const std::optional<LayoutUnit> initialFreeSpace = freeSpace(m_direction);
    initializeTrackSizes();

    // Step 2.
    if (!m_contentSizedTracksIndex.isEmpty())
        resolveIntrinsicTrackSizes();

    // This is not exactly a step of the track sizing algorithm, but we use the track sizes computed
    // up to this moment (before maximization) to calculate the grid container intrinsic sizes.
    computeGridContainerIntrinsicSizes();

    if (freeSpace(m_direction)) {
        LayoutUnit updatedFreeSpace = freeSpace(m_direction).value() - m_minContentSize;
        setFreeSpace(m_direction, updatedFreeSpace);
        if (updatedFreeSpace <= 0)
            return;
    }

    // Step 3.
    m_strategy->maximizeTracks(tracks(m_direction), m_direction == ForColumns ? m_freeSpaceColumns : m_freeSpaceRows);

    if (m_flexibleSizedTracksIndex.isEmpty())
        return;

    // Step 4.
    stretchFlexibleTracks(initialFreeSpace);
}

void GridTrackSizingAlgorithm::reset()
{
    m_sizingState = ColumnSizingFirstIteration;
    m_columns.shrink(0);
    m_rows.shrink(0);
    m_contentSizedTracksIndex.shrink(0);
    m_flexibleSizedTracksIndex.shrink(0);
}

#ifndef NDEBUG
bool GridTrackSizingAlgorithm::tracksAreWiderThanMinTrackBreadth() const
{
    const Vector<GridTrack>& allTracks = tracks(m_direction);
    for (size_t i = 0; i < allTracks.size(); ++i) {
        GridTrackSize trackSize = gridTrackSize(m_direction, i);
        if (initialBaseSize(trackSize) > allTracks[i].baseSize())
            return false;
    }
    return true;
}
#endif

GridTrackSizingAlgorithm::StateMachine::StateMachine(GridTrackSizingAlgorithm& algorithm)
    : m_algorithm(algorithm)
{
    ASSERT(m_algorithm.isValidTransition());
    ASSERT(!m_algorithm.m_needsSetup);
}

GridTrackSizingAlgorithm::StateMachine::~StateMachine()
{
    m_algorithm.advanceNextState();
    m_algorithm.m_needsSetup = true;
}

} // namespace WebCore