layout/generic/nsGridContainerFrame.cpp
author Matt Woodrow <mwoodrow@mozilla.com>
Sat, 08 May 2021 05:52:19 +0000
changeset 579122 f9bdd1b929f234f4defb8c2344c24d4e3b2547bc
parent 572896 e1624e209c4351f294728557ffe72097021eabc2
permissions -rw-r--r--
Bug 1707513 - Add reftest-snapshot task using the 'drawSnapshot' reftest mode. r=ahal Differential Revision: https://phabricator.services.mozilla.com/D114189

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/* rendering object for CSS "display: grid | inline-grid" */

#include "nsGridContainerFrame.h"

#include <functional>
#include <limits>
#include <stdlib.h>  // for div()
#include <type_traits>
#include "gfxContext.h"
#include "mozilla/AutoRestore.h"
#include "mozilla/ComputedStyle.h"
#include "mozilla/CSSAlignUtils.h"
#include "mozilla/dom/GridBinding.h"
#include "mozilla/IntegerRange.h"
#include "mozilla/Maybe.h"
#include "mozilla/PodOperations.h"  // for PodZero
#include "mozilla/Poison.h"
#include "mozilla/PresShell.h"
#include "nsAbsoluteContainingBlock.h"
#include "nsAlgorithm.h"  // for clamped()
#include "nsBoxLayoutState.h"
#include "nsCSSAnonBoxes.h"
#include "nsCSSFrameConstructor.h"
#include "nsTHashMap.h"
#include "nsDisplayList.h"
#include "nsHashKeys.h"
#include "nsFieldSetFrame.h"
#include "nsIFrameInlines.h"
#include "nsPlaceholderFrame.h"
#include "nsPresContext.h"
#include "nsReadableUtils.h"
#include "nsTableWrapperFrame.h"

using namespace mozilla;

typedef nsAbsoluteContainingBlock::AbsPosReflowFlags AbsPosReflowFlags;
typedef nsGridContainerFrame::TrackSize TrackSize;
typedef mozilla::CSSAlignUtils::AlignJustifyFlags AlignJustifyFlags;

using GridTemplate = StyleGridTemplateComponent;
using TrackListValue =
    StyleGenericTrackListValue<LengthPercentage, StyleInteger>;
using TrackRepeat = StyleGenericTrackRepeat<LengthPercentage, StyleInteger>;
using NameList = StyleOwnedSlice<StyleCustomIdent>;
using SizingConstraint = nsGridContainerFrame::SizingConstraint;

static const int32_t kMaxLine = StyleMAX_GRID_LINE;
static const int32_t kMinLine = StyleMIN_GRID_LINE;
// The maximum line number, in the zero-based translated grid.
static const uint32_t kTranslatedMaxLine = uint32_t(kMaxLine - kMinLine);
static const uint32_t kAutoLine = kTranslatedMaxLine + 3457U;

static const nsFrameState kIsSubgridBits =
    (NS_STATE_GRID_IS_COL_SUBGRID | NS_STATE_GRID_IS_ROW_SUBGRID);

namespace mozilla {

template <>
inline Span<const StyleOwnedSlice<StyleCustomIdent>>
GridTemplate::LineNameLists(bool aIsSubgrid) const {
  if (IsTrackList()) {
    return AsTrackList()->line_names.AsSpan();
  }
  if (IsSubgrid() && aIsSubgrid) {
    return AsSubgrid()->names.AsSpan();
  }
  MOZ_ASSERT(IsNone() || IsMasonry() || (IsSubgrid() && !aIsSubgrid));
  return {};
}

template <>
inline const StyleTrackBreadth& StyleTrackSize::GetMax() const {
  if (IsBreadth()) {
    return AsBreadth();
  }
  if (IsMinmax()) {
    return AsMinmax()._1;
  }
  MOZ_ASSERT(IsFitContent());
  return AsFitContent();
}

template <>
inline const StyleTrackBreadth& StyleTrackSize::GetMin() const {
  static const StyleTrackBreadth kAuto = StyleTrackBreadth::Auto();
  if (IsBreadth()) {
    // <flex> behaves like minmax(auto, <flex>)
    return AsBreadth().IsFr() ? kAuto : AsBreadth();
  }
  if (IsMinmax()) {
    return AsMinmax()._0;
  }
  MOZ_ASSERT(IsFitContent());
  return kAuto;
}

}  // namespace mozilla

static nscoord ClampToCSSMaxBSize(nscoord aSize,
                                  const ReflowInput* aReflowInput) {
  auto maxSize = aReflowInput->ComputedMaxBSize();
  if (MOZ_UNLIKELY(maxSize != NS_UNCONSTRAINEDSIZE)) {
    MOZ_ASSERT(aReflowInput->ComputedMinBSize() <= maxSize);
    aSize = std::min(aSize, maxSize);
  }
  return aSize;
}

// Same as above and set aStatus INCOMPLETE if aSize wasn't clamped.
// (If we clamp aSize it means our size is less than the break point,
// i.e. we're effectively breaking in our overflow, so we should leave
// aStatus as is (it will likely be set to OVERFLOW_INCOMPLETE later)).
static nscoord ClampToCSSMaxBSize(nscoord aSize,
                                  const ReflowInput* aReflowInput,
                                  nsReflowStatus* aStatus) {
  auto maxSize = aReflowInput->ComputedMaxBSize();
  if (MOZ_UNLIKELY(maxSize != NS_UNCONSTRAINEDSIZE)) {
    MOZ_ASSERT(aReflowInput->ComputedMinBSize() <= maxSize);
    if (aSize < maxSize) {
      aStatus->SetIncomplete();
    } else {
      aSize = maxSize;
    }
  } else {
    aStatus->SetIncomplete();
  }
  return aSize;
}

template <typename Size>
static bool IsPercentOfIndefiniteSize(const Size& aCoord,
                                      nscoord aPercentBasis) {
  return aPercentBasis == NS_UNCONSTRAINEDSIZE && aCoord.HasPercent();
}

static nscoord ResolveToDefiniteSize(const StyleTrackBreadth& aBreadth,
                                     nscoord aPercentBasis) {
  MOZ_ASSERT(aBreadth.IsBreadth());
  if (::IsPercentOfIndefiniteSize(aBreadth.AsBreadth(), aPercentBasis)) {
    return nscoord(0);
  }
  return std::max(nscoord(0), aBreadth.AsBreadth().Resolve(aPercentBasis));
}

// Synthesize a baseline from a border box.  For an alphabetical baseline
// this is the end edge of the border box.  For a central baseline it's
// the center of the border box.
// https://drafts.csswg.org/css-align-3/#synthesize-baselines
// For a 'first baseline' the measure is from the border-box start edge and
// for a 'last baseline' the measure is from the border-box end edge.
static nscoord SynthesizeBaselineFromBorderBox(BaselineSharingGroup aGroup,
                                               WritingMode aWM,
                                               nscoord aBorderBoxSize) {
  if (aGroup == BaselineSharingGroup::First) {
    return aWM.IsAlphabeticalBaseline() ? aBorderBoxSize : aBorderBoxSize / 2;
  }
  MOZ_ASSERT(aGroup == BaselineSharingGroup::Last);
  // Round up for central baseline offset, to be consistent with eFirst.
  return aWM.IsAlphabeticalBaseline()
             ? 0
             : (aBorderBoxSize / 2) + (aBorderBoxSize % 2);
}

// The input sizes for calculating the number of repeat(auto-fill/fit) tracks.
// https://drafts.csswg.org/css-grid/#auto-repeat
struct RepeatTrackSizingInput {
  explicit RepeatTrackSizingInput(WritingMode aWM)
      : mMin(aWM, 0, 0),
        mSize(aWM, NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE),
        mMax(aWM, NS_UNCONSTRAINEDSIZE, NS_UNCONSTRAINEDSIZE) {}
  RepeatTrackSizingInput(const LogicalSize& aMin, const LogicalSize& aSize,
                         const LogicalSize& aMax)
      : mMin(aMin), mSize(aSize), mMax(aMax) {}

  // This should be used in intrinsic sizing (i.e. when we can't initialize
  // the sizes directly from ReflowInput values).
  void InitFromStyle(LogicalAxis aAxis, WritingMode aWM,
                     const ComputedStyle* aStyle) {
    const auto& pos = aStyle->StylePosition();
    const bool borderBoxSizing = pos->mBoxSizing == StyleBoxSizing::Border;
    nscoord bp = NS_UNCONSTRAINEDSIZE;  // a sentinel to calculate it only once
    auto adjustForBoxSizing = [borderBoxSizing, aWM, aAxis, aStyle,
                               &bp](nscoord aSize) {
      if (!borderBoxSizing) {
        return aSize;
      }
      if (bp == NS_UNCONSTRAINEDSIZE) {
        const auto& padding = aStyle->StylePadding()->mPadding;
        LogicalMargin border(aWM, aStyle->StyleBorder()->GetComputedBorder());
        // We can use zero percentage basis since this is only called from
        // intrinsic sizing code.
        const nscoord percentageBasis = 0;
        if (aAxis == eLogicalAxisInline) {
          bp = std::max(padding.GetIStart(aWM).Resolve(percentageBasis), 0) +
               std::max(padding.GetIEnd(aWM).Resolve(percentageBasis), 0) +
               border.IStartEnd(aWM);
        } else {
          bp = std::max(padding.GetBStart(aWM).Resolve(percentageBasis), 0) +
               std::max(padding.GetBEnd(aWM).Resolve(percentageBasis), 0) +
               border.BStartEnd(aWM);
        }
      }
      return std::max(aSize - bp, 0);
    };
    nscoord& min = mMin.Size(aAxis, aWM);
    nscoord& size = mSize.Size(aAxis, aWM);
    nscoord& max = mMax.Size(aAxis, aWM);
    const auto& minCoord =
        aAxis == eLogicalAxisInline ? pos->MinISize(aWM) : pos->MinBSize(aWM);
    if (minCoord.ConvertsToLength()) {
      min = adjustForBoxSizing(minCoord.ToLength());
    }
    const auto& maxCoord =
        aAxis == eLogicalAxisInline ? pos->MaxISize(aWM) : pos->MaxBSize(aWM);
    if (maxCoord.ConvertsToLength()) {
      max = std::max(min, adjustForBoxSizing(maxCoord.ToLength()));
    }
    const auto& sizeCoord =
        aAxis == eLogicalAxisInline ? pos->ISize(aWM) : pos->BSize(aWM);
    if (sizeCoord.ConvertsToLength()) {
      size = Clamp(adjustForBoxSizing(sizeCoord.ToLength()), min, max);
    }
  }

  LogicalSize mMin;
  LogicalSize mSize;
  LogicalSize mMax;
};

enum class GridLineSide {
  BeforeGridGap,
  AfterGridGap,
};

struct nsGridContainerFrame::TrackSize {
  enum StateBits : uint16_t {
    // clang-format off
    eAutoMinSizing =              0x1,
    eMinContentMinSizing =        0x2,
    eMaxContentMinSizing =        0x4,
    eMinOrMaxContentMinSizing = eMinContentMinSizing | eMaxContentMinSizing,
    eIntrinsicMinSizing = eMinOrMaxContentMinSizing | eAutoMinSizing,
    eModified =                   0x8,
    eAutoMaxSizing =             0x10,
    eMinContentMaxSizing =       0x20,
    eMaxContentMaxSizing =       0x40,
    eAutoOrMaxContentMaxSizing = eAutoMaxSizing | eMaxContentMaxSizing,
    eIntrinsicMaxSizing = eAutoOrMaxContentMaxSizing | eMinContentMaxSizing,
    eFlexMaxSizing =             0x80,
    eFrozen =                   0x100,
    eSkipGrowUnlimited1 =       0x200,
    eSkipGrowUnlimited2 =       0x400,
    eSkipGrowUnlimited = eSkipGrowUnlimited1 | eSkipGrowUnlimited2,
    eBreakBefore =              0x800,
    eFitContent =              0x1000,
    eInfinitelyGrowable =      0x2000,

    // These are only used in the masonry axis.  They share the same value
    // as *MinSizing above, but that's OK because we don't use those in
    // the masonry axis.
    //
    // This track corresponds to an item margin-box size that is stretching.
    eItemStretchSize =            0x1,
    // This bit says that we should clamp that size to mLimit.
    eClampToLimit =               0x2,
    // This bit says that the corresponding item has `auto` margin(s).
    eItemHasAutoMargin =          0x4,
    // clang-format on
  };

  StateBits Initialize(nscoord aPercentageBasis, const StyleTrackSize&);
  bool IsFrozen() const { return mState & eFrozen; }
#ifdef DEBUG
  static void DumpStateBits(StateBits aState);
  void Dump() const;
#endif

  static bool IsDefiniteMaxSizing(StateBits aStateBits) {
    return (aStateBits & (eIntrinsicMaxSizing | eFlexMaxSizing)) == 0;
  }

  nscoord mBase;
  nscoord mLimit;
  nscoord mPosition;  // zero until we apply 'align/justify-content'
  // mBaselineSubtreeSize is the size of a baseline-aligned subtree within
  // this track.  One subtree per baseline-sharing group (per track).
  PerBaseline<nscoord> mBaselineSubtreeSize;
  StateBits mState;
};

MOZ_MAKE_ENUM_CLASS_BITWISE_OPERATORS(TrackSize::StateBits)

namespace mozilla {
template <>
struct IsPod<nsGridContainerFrame::TrackSize> : std::true_type {};
}  // namespace mozilla

TrackSize::StateBits nsGridContainerFrame::TrackSize::Initialize(
    nscoord aPercentageBasis, const StyleTrackSize& aSize) {
  using Tag = StyleTrackBreadth::Tag;

  MOZ_ASSERT(mBase == 0 && mLimit == 0 && mState == 0,
             "track size data is expected to be initialized to zero");
  mBaselineSubtreeSize[BaselineSharingGroup::First] = nscoord(0);
  mBaselineSubtreeSize[BaselineSharingGroup::Last] = nscoord(0);

  auto& min = aSize.GetMin();
  auto& max = aSize.GetMax();

  Tag minSizeTag = min.tag;
  Tag maxSizeTag = max.tag;
  if (aSize.IsFitContent()) {
    // In layout, fit-content(size) behaves as minmax(auto, max-content), with
    // 'size' as an additional upper-bound.
    mState = eFitContent;
    minSizeTag = Tag::Auto;
    maxSizeTag = Tag::MaxContent;
  }
  if (::IsPercentOfIndefiniteSize(min, aPercentageBasis)) {
    // https://drafts.csswg.org/css-grid/#valdef-grid-template-columns-percentage
    // "If the inline or block size of the grid container is indefinite,
    //  <percentage> values relative to that size are treated as 'auto'."
    minSizeTag = Tag::Auto;
  }
  if (::IsPercentOfIndefiniteSize(max, aPercentageBasis)) {
    maxSizeTag = Tag::Auto;
  }

  // http://dev.w3.org/csswg/css-grid/#algo-init
  switch (minSizeTag) {
    case Tag::Auto:
      mState |= eAutoMinSizing;
      break;
    case Tag::MinContent:
      mState |= eMinContentMinSizing;
      break;
    case Tag::MaxContent:
      mState |= eMaxContentMinSizing;
      break;
    default:
      MOZ_ASSERT(!min.IsFr(), "<flex> min-sizing is invalid as a track size");
      mBase = ::ResolveToDefiniteSize(min, aPercentageBasis);
  }
  switch (maxSizeTag) {
    case Tag::Auto:
      mState |= eAutoMaxSizing;
      mLimit = NS_UNCONSTRAINEDSIZE;
      break;
    case Tag::MinContent:
    case Tag::MaxContent:
      mState |= maxSizeTag == Tag::MinContent ? eMinContentMaxSizing
                                              : eMaxContentMaxSizing;
      mLimit = NS_UNCONSTRAINEDSIZE;
      break;
    case Tag::Fr:
      mState |= eFlexMaxSizing;
      mLimit = mBase;
      break;
    default:
      mLimit = ::ResolveToDefiniteSize(max, aPercentageBasis);
      if (mLimit < mBase) {
        mLimit = mBase;
      }
  }
  return mState;
}

/**
 * A LineRange can be definite or auto - when it's definite it represents
 * a consecutive set of tracks between a starting line and an ending line.
 * Before it's definite it can also represent an auto position with a span,
 * where mStart == kAutoLine and mEnd is the (non-zero positive) span.
 * For normal-flow items, the invariant mStart < mEnd holds when both
 * lines are definite.
 *
 * For abs.pos. grid items, mStart and mEnd may both be kAutoLine, meaning
 * "attach this side to the grid container containing block edge".
 * Additionally, mStart <= mEnd holds when both are definite (non-kAutoLine),
 * i.e. the invariant is slightly relaxed compared to normal flow items.
 */
struct nsGridContainerFrame::LineRange {
  LineRange(int32_t aStart, int32_t aEnd)
      : mUntranslatedStart(aStart), mUntranslatedEnd(aEnd) {
#ifdef DEBUG
    if (!IsAutoAuto()) {
      if (IsAuto()) {
        MOZ_ASSERT(aEnd >= kMinLine && aEnd <= kMaxLine, "invalid span");
      } else {
        MOZ_ASSERT(aStart >= kMinLine && aStart <= kMaxLine,
                   "invalid start line");
        MOZ_ASSERT(aEnd == int32_t(kAutoLine) ||
                       (aEnd >= kMinLine && aEnd <= kMaxLine),
                   "invalid end line");
      }
    }
#endif
  }
  bool IsAutoAuto() const { return mStart == kAutoLine && mEnd == kAutoLine; }
  bool IsAuto() const { return mStart == kAutoLine; }
  bool IsDefinite() const { return mStart != kAutoLine; }
  uint32_t Extent() const {
    MOZ_ASSERT(mEnd != kAutoLine, "Extent is undefined for abs.pos. 'auto'");
    if (IsAuto()) {
      MOZ_ASSERT(mEnd >= 1 && mEnd < uint32_t(kMaxLine), "invalid span");
      return mEnd;
    }
    return mEnd - mStart;
  }

  /**
   * Return an object suitable for iterating this range.
   */
  auto Range() const { return IntegerRange<uint32_t>(mStart, mEnd); }

  /**
   * Resolve this auto range to start at aStart, making it definite.
   * @param aClampMaxLine the maximum allowed line number (zero-based)
   * Precondition: this range IsAuto()
   */
  void ResolveAutoPosition(uint32_t aStart, uint32_t aClampMaxLine) {
    MOZ_ASSERT(IsAuto(), "Why call me?");
    mStart = aStart;
    mEnd += aStart;
    // Clamp to aClampMaxLine, which is where kMaxLine is in the explicit
    // grid in a non-subgrid axis; this implements clamping per
    // http://dev.w3.org/csswg/css-grid/#overlarge-grids
    // In a subgrid axis it's the end of the grid in that axis.
    if (MOZ_UNLIKELY(mStart >= aClampMaxLine)) {
      mEnd = aClampMaxLine;
      mStart = mEnd - 1;
    } else if (MOZ_UNLIKELY(mEnd > aClampMaxLine)) {
      mEnd = aClampMaxLine;
    }
  }
  /**
   * Translate the lines to account for (empty) removed tracks.  This method
   * is only for grid items and should only be called after placement.
   * aNumRemovedTracks contains a count for each line in the grid how many
   * tracks were removed between the start of the grid and that line.
   */
  void AdjustForRemovedTracks(const nsTArray<uint32_t>& aNumRemovedTracks) {
    MOZ_ASSERT(mStart != kAutoLine, "invalid resolved line for a grid item");
    MOZ_ASSERT(mEnd != kAutoLine, "invalid resolved line for a grid item");
    uint32_t numRemovedTracks = aNumRemovedTracks[mStart];
    MOZ_ASSERT(numRemovedTracks == aNumRemovedTracks[mEnd],
               "tracks that a grid item spans can't be removed");
    mStart -= numRemovedTracks;
    mEnd -= numRemovedTracks;
  }
  /**
   * Translate the lines to account for (empty) removed tracks.  This method
   * is only for abs.pos. children and should only be called after placement.
   * Same as for in-flow items, but we don't touch 'auto' lines here and we
   * also need to adjust areas that span into the removed tracks.
   */
  void AdjustAbsPosForRemovedTracks(
      const nsTArray<uint32_t>& aNumRemovedTracks) {
    if (mStart != kAutoLine) {
      mStart -= aNumRemovedTracks[mStart];
    }
    if (mEnd != kAutoLine) {
      MOZ_ASSERT(mStart == kAutoLine || mEnd > mStart, "invalid line range");
      mEnd -= aNumRemovedTracks[mEnd];
    }
  }
  /**
   * Return the contribution of this line range for step 2 in
   * http://dev.w3.org/csswg/css-grid/#auto-placement-algo
   */
  uint32_t HypotheticalEnd() const { return mEnd; }
  /**
   * Given an array of track sizes, return the starting position and length
   * of the tracks in this line range.
   */
  void ToPositionAndLength(const nsTArray<TrackSize>& aTrackSizes,
                           nscoord* aPos, nscoord* aLength) const;
  /**
   * Given an array of track sizes, return the length of the tracks in this
   * line range.
   */
  nscoord ToLength(const nsTArray<TrackSize>& aTrackSizes) const;
  /**
   * Given an array of track sizes and a grid origin coordinate, adjust the
   * abs.pos. containing block along an axis given by aPos and aLength.
   * aPos and aLength should already be initialized to the grid container
   * containing block for this axis before calling this method.
   */
  void ToPositionAndLengthForAbsPos(const Tracks& aTracks, nscoord aGridOrigin,
                                    nscoord* aPos, nscoord* aLength) const;

  void Translate(int32_t aOffset) {
    MOZ_ASSERT(IsDefinite());
    mStart += aOffset;
    mEnd += aOffset;
  }

  /** Swap the start/end sides of this range. */
  void ReverseDirection(uint32_t aGridEnd) {
    MOZ_ASSERT(IsDefinite());
    MOZ_ASSERT(aGridEnd >= mEnd);
    uint32_t newStart = aGridEnd - mEnd;
    mEnd = aGridEnd - mStart;
    mStart = newStart;
  }

  /**
   * @note We'll use the signed member while resolving definite positions
   * to line numbers (1-based), which may become negative for implicit lines
   * to the top/left of the explicit grid.  PlaceGridItems() then translates
   * the whole grid to a 0,0 origin and we'll use the unsigned member from
   * there on.
   */
  union {
    uint32_t mStart;
    int32_t mUntranslatedStart;
  };
  union {
    uint32_t mEnd;
    int32_t mUntranslatedEnd;
  };

 protected:
  LineRange() : mStart(0), mEnd(0) {}
};

/**
 * Helper class to construct a LineRange from translated lines.
 * The ctor only accepts translated definite line numbers.
 */
struct nsGridContainerFrame::TranslatedLineRange : public LineRange {
  TranslatedLineRange(uint32_t aStart, uint32_t aEnd) {
    MOZ_ASSERT(aStart < aEnd && aEnd <= kTranslatedMaxLine);
    mStart = aStart;
    mEnd = aEnd;
  }
};

/**
 * A GridArea is the area in the grid for a grid item.
 * The area is represented by two LineRanges, both of which can be auto
 * (@see LineRange) in intermediate steps while the item is being placed.
 * @see PlaceGridItems
 */
struct nsGridContainerFrame::GridArea {
  GridArea(const LineRange& aCols, const LineRange& aRows)
      : mCols(aCols), mRows(aRows) {}
  bool IsDefinite() const { return mCols.IsDefinite() && mRows.IsDefinite(); }
  LineRange& LineRangeForAxis(LogicalAxis aAxis) {
    return aAxis == eLogicalAxisInline ? mCols : mRows;
  }
  const LineRange& LineRangeForAxis(LogicalAxis aAxis) const {
    return aAxis == eLogicalAxisInline ? mCols : mRows;
  }
  LineRange mCols;
  LineRange mRows;
};

struct nsGridContainerFrame::GridItemInfo {
  /**
   * Item state per axis.
   */
  enum StateBits : uint16_t {
    // clang-format off
    eIsFlexing =              0x1, // does the item span a flex track?
    eFirstBaseline =          0x2, // participate in 'first baseline' alignment?
    // ditto 'last baseline', mutually exclusive w. eFirstBaseline
    eLastBaseline =           0x4,
    eIsBaselineAligned = eFirstBaseline | eLastBaseline,
    // One of e[Self|Content]Baseline is set when eIsBaselineAligned is true
    eSelfBaseline =           0x8, // is it *-self:[last ]baseline alignment?
    // Ditto *-content:[last ]baseline. Mutually exclusive w. eSelfBaseline.
    eContentBaseline =       0x10,
    // The baseline affects the margin or padding on the item's end side when
    // this bit is set.  In a grid-axis it's always set for eLastBaseline and
    // always unset for eFirstBaseline.  In a masonry-axis, it's set for
    // baseline groups in the EndStretch set and unset for the StartStretch set.
    eEndSideBaseline =       0x20,
    eAllBaselineBits = eIsBaselineAligned | eSelfBaseline | eContentBaseline |
                       eEndSideBaseline,
    // Should apply Automatic Minimum Size per:
    // https://drafts.csswg.org/css-grid/#min-size-auto
    eApplyAutoMinSize =      0x40,
    // Clamp per https://drafts.csswg.org/css-grid/#min-size-auto
    eClampMarginBoxMinSize = 0x80,
    eIsSubgrid =            0x100,
    // set on subgrids and items in subgrids if they are adjacent to the grid
    // start/end edge (excluding grid-aligned abs.pos. frames)
    eStartEdge =            0x200,
    eEndEdge =              0x400,
    eEdgeBits = eStartEdge | eEndEdge,
    // Set if this item was auto-placed in this axis.
    eAutoPlacement =        0x800,
    // Set if this item is the last item in its track (masonry layout only)
    eIsLastItemInMasonryTrack =   0x1000,
    // clang-format on
  };

  GridItemInfo(nsIFrame* aFrame, const GridArea& aArea);

  static bool BaselineAlignmentAffectsEndSide(StateBits state) {
    return state & StateBits::eEndSideBaseline;
  }

  /**
   * Inhibit subgrid layout unless the item is placed in the first "track" in
   * a parent masonry-axis, or has definite placement or spans all tracks in
   * the parent grid-axis.
   * TODO: this is stricter than what the Masonry proposal currently states
   *       (bug 1627581)
   */
  void MaybeInhibitSubgridInMasonry(nsGridContainerFrame* aParent,
                                    uint32_t aGridAxisTrackCount);

  /**
   * Inhibit subgridding in aAxis for this item.
   */
  void InhibitSubgrid(nsGridContainerFrame* aParent, LogicalAxis aAxis);

  /**
   * Return a copy of this item with its row/column data swapped.
   */
  GridItemInfo Transpose() const {
    GridItemInfo info(mFrame, GridArea(mArea.mRows, mArea.mCols));
    info.mState[0] = mState[1];
    info.mState[1] = mState[0];
    info.mBaselineOffset[0] = mBaselineOffset[1];
    info.mBaselineOffset[1] = mBaselineOffset[0];
    return info;
  }

  /** Swap the start/end sides in aAxis. */
  inline void ReverseDirection(LogicalAxis aAxis, uint32_t aGridEnd);

  // Is this item a subgrid in the given container axis?
  bool IsSubgrid(LogicalAxis aAxis) const {
    return mState[aAxis] & StateBits::eIsSubgrid;
  }

  // Is this item a subgrid in either axis?
  bool IsSubgrid() const {
    return IsSubgrid(eLogicalAxisInline) || IsSubgrid(eLogicalAxisBlock);
  }

  // Return the (inner) grid container frame associated with this subgrid item.
  nsGridContainerFrame* SubgridFrame() const {
    MOZ_ASSERT(IsSubgrid());
    nsGridContainerFrame* gridFrame = GetGridContainerFrame(mFrame);
    MOZ_ASSERT(gridFrame && gridFrame->IsSubgrid());
    return gridFrame;
  }

  /**
   * Adjust our grid areas to account for removed auto-fit tracks in aAxis.
   */
  void AdjustForRemovedTracks(LogicalAxis aAxis,
                              const nsTArray<uint32_t>& aNumRemovedTracks);

  /**
   * If the item is [align|justify]-self:[last ]baseline aligned in the given
   * axis then set aBaselineOffset to the baseline offset and return aAlign.
   * Otherwise, return a fallback alignment.
   */
  StyleAlignFlags GetSelfBaseline(StyleAlignFlags aAlign, LogicalAxis aAxis,
                                  nscoord* aBaselineOffset) const {
    MOZ_ASSERT(aAlign == StyleAlignFlags::BASELINE ||
               aAlign == StyleAlignFlags::LAST_BASELINE);
    if (!(mState[aAxis] & eSelfBaseline)) {
      return aAlign == StyleAlignFlags::BASELINE ? StyleAlignFlags::SELF_START
                                                 : StyleAlignFlags::SELF_END;
    }
    *aBaselineOffset = mBaselineOffset[aAxis];
    return aAlign;
  }

  // Return true if we should apply Automatic Minimum Size to this item.
  // https://drafts.csswg.org/css-grid/#min-size-auto
  // @note the caller should also check that the item spans at least one track
  // that has a min track sizing function that is 'auto' before applying it.
  bool ShouldApplyAutoMinSize(WritingMode aContainerWM,
                              LogicalAxis aContainerAxis,
                              nscoord aPercentageBasis) const {
    const bool isInlineAxis = aContainerAxis == eLogicalAxisInline;
    const auto* pos =
        mFrame->IsTableWrapperFrame()
            ? mFrame->PrincipalChildList().FirstChild()->StylePosition()
            : mFrame->StylePosition();
    const auto& size =
        isInlineAxis ? pos->ISize(aContainerWM) : pos->BSize(aContainerWM);
    // max-content and min-content should behave as initial value in block axis.
    // FIXME: Bug 567039: moz-fit-content and -moz-available are not supported
    // for block size dimension on sizing properties (e.g. height), so we
    // treat it as `auto`.
    bool isAuto = size.IsAuto() ||
                  (isInlineAxis ==
                       aContainerWM.IsOrthogonalTo(mFrame->GetWritingMode()) &&
                   size.BehavesLikeInitialValueOnBlockAxis());
    // NOTE: if we have a definite size then our automatic minimum size
    // can't affect our size.  Excluding these simplifies applying
    // the clamping in the right cases later.
    if (!isAuto && !::IsPercentOfIndefiniteSize(size, aPercentageBasis)) {
      return false;
    }
    const auto& minSize = isInlineAxis ? pos->MinISize(aContainerWM)
                                       : pos->MinBSize(aContainerWM);
    // max-content and min-content should behave as initial value in block axis.
    // FIXME: Bug 567039: moz-fit-content and -moz-available are not supported
    // for block size dimension on sizing properties (e.g. height), so we
    // treat it as `auto`.
    isAuto = minSize.IsAuto() ||
             (isInlineAxis ==
                  aContainerWM.IsOrthogonalTo(mFrame->GetWritingMode()) &&
              minSize.BehavesLikeInitialValueOnBlockAxis());
    return isAuto &&
           mFrame->StyleDisplay()->mOverflowX == StyleOverflow::Visible;
  }

#ifdef DEBUG
  void Dump() const;
#endif

  static bool IsStartRowLessThan(const GridItemInfo* a, const GridItemInfo* b) {
    return a->mArea.mRows.mStart < b->mArea.mRows.mStart;
  }

  // Sorting functions for 'masonry-auto-flow:next'.  We sort the items that
  // were placed into the first track by the Grid placement algorithm first
  // (to honor that placement).  All other items will be placed by the Masonry
  // layout algorithm (their Grid placement in the masonry axis is irrelevant).
  static bool RowMasonryOrdered(const GridItemInfo* a, const GridItemInfo* b) {
    return a->mArea.mRows.mStart == 0 && b->mArea.mRows.mStart != 0 &&
           !a->mFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW);
  }
  static bool ColMasonryOrdered(const GridItemInfo* a, const GridItemInfo* b) {
    return a->mArea.mCols.mStart == 0 && b->mArea.mCols.mStart != 0 &&
           !a->mFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW);
  }

  // Sorting functions for 'masonry-auto-flow:definite-first'.  Similar to
  // the above, but here we also sort items with a definite item placement in
  // the grid axis in track order before 'auto'-placed items. We also sort all
  // continuations first since they use the same placement as their
  // first-in-flow (we treat them as "definite" regardless of eAutoPlacement).
  static bool RowMasonryDefiniteFirst(const GridItemInfo* a,
                                      const GridItemInfo* b) {
    bool isContinuationA = a->mFrame->GetPrevInFlow();
    bool isContinuationB = b->mFrame->GetPrevInFlow();
    if (isContinuationA != isContinuationB) {
      return isContinuationA;
    }
    auto masonryA = a->mArea.mRows.mStart;
    auto gridA = a->mState[eLogicalAxisInline] & StateBits::eAutoPlacement;
    auto masonryB = b->mArea.mRows.mStart;
    auto gridB = b->mState[eLogicalAxisInline] & StateBits::eAutoPlacement;
    return (masonryA == 0 ? masonryB != 0 : (masonryB != 0 && gridA < gridB)) &&
           !a->mFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW);
  }
  static bool ColMasonryDefiniteFirst(const GridItemInfo* a,
                                      const GridItemInfo* b) {
    MOZ_ASSERT(!a->mFrame->GetPrevInFlow() && !b->mFrame->GetPrevInFlow(),
               "fragmentation not supported in inline axis");
    auto masonryA = a->mArea.mCols.mStart;
    auto gridA = a->mState[eLogicalAxisBlock] & StateBits::eAutoPlacement;
    auto masonryB = b->mArea.mCols.mStart;
    auto gridB = b->mState[eLogicalAxisBlock] & StateBits::eAutoPlacement;
    return (masonryA == 0 ? masonryB != 0 : (masonryB != 0 && gridA < gridB)) &&
           !a->mFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW);
  }

  nsIFrame* const mFrame;
  GridArea mArea;
  // Offset from the margin edge to the baseline (LogicalAxis index).  It's from
  // the start edge when eFirstBaseline is set, end edge otherwise. It's mutable
  // since we update the value fairly late (just before reflowing the item).
  mutable nscoord mBaselineOffset[2];
  mutable StateBits mState[2];  // state bits per axis (LogicalAxis index)
  static_assert(mozilla::eLogicalAxisBlock == 0, "unexpected index value");
  static_assert(mozilla::eLogicalAxisInline == 1, "unexpected index value");
};

using GridItemInfo = nsGridContainerFrame::GridItemInfo;
using ItemState = GridItemInfo::StateBits;
MOZ_MAKE_ENUM_CLASS_BITWISE_OPERATORS(ItemState)

GridItemInfo::GridItemInfo(nsIFrame* aFrame, const GridArea& aArea)
    : mFrame(aFrame), mArea(aArea) {
  mState[eLogicalAxisBlock] =
      StateBits(mArea.mRows.mStart == kAutoLine ? eAutoPlacement : 0);
  mState[eLogicalAxisInline] =
      StateBits(mArea.mCols.mStart == kAutoLine ? eAutoPlacement : 0);
  if (auto* gridFrame = GetGridContainerFrame(mFrame)) {
    auto parentWM = aFrame->GetParent()->GetWritingMode();
    bool isOrthogonal = parentWM.IsOrthogonalTo(gridFrame->GetWritingMode());
    if (gridFrame->IsColSubgrid()) {
      mState[isOrthogonal ? eLogicalAxisBlock : eLogicalAxisInline] |=
          StateBits::eIsSubgrid;
    }
    if (gridFrame->IsRowSubgrid()) {
      mState[isOrthogonal ? eLogicalAxisInline : eLogicalAxisBlock] |=
          StateBits::eIsSubgrid;
    }
  }
  mBaselineOffset[eLogicalAxisBlock] = nscoord(0);
  mBaselineOffset[eLogicalAxisInline] = nscoord(0);
}

void GridItemInfo::ReverseDirection(LogicalAxis aAxis, uint32_t aGridEnd) {
  mArea.LineRangeForAxis(aAxis).ReverseDirection(aGridEnd);
  ItemState& state = mState[aAxis];
  ItemState newState = state & ~ItemState::eEdgeBits;
  if (state & ItemState::eStartEdge) {
    newState |= ItemState::eEndEdge;
  }
  if (state & ItemState::eEndEdge) {
    newState |= ItemState::eStartEdge;
  }
  state = newState;
}

void GridItemInfo::InhibitSubgrid(nsGridContainerFrame* aParent,
                                  LogicalAxis aAxis) {
  MOZ_ASSERT(IsSubgrid(aAxis));
  auto bit = NS_STATE_GRID_IS_COL_SUBGRID;
  if (aParent->GetWritingMode().IsOrthogonalTo(mFrame->GetWritingMode()) !=
      (aAxis == eLogicalAxisBlock)) {
    bit = NS_STATE_GRID_IS_ROW_SUBGRID;
  }
  MOZ_ASSERT(SubgridFrame()->HasAnyStateBits(bit));
  SubgridFrame()->RemoveStateBits(bit);
  mState[aAxis] &= StateBits(~StateBits::eIsSubgrid);
}

void GridItemInfo::MaybeInhibitSubgridInMasonry(nsGridContainerFrame* aParent,
                                                uint32_t aGridAxisTrackCount) {
  if (IsSubgrid(eLogicalAxisInline) && aParent->IsMasonry(eLogicalAxisBlock) &&
      mArea.mRows.mStart != 0 && mArea.mCols.Extent() != aGridAxisTrackCount &&
      (mState[eLogicalAxisInline] & eAutoPlacement)) {
    InhibitSubgrid(aParent, eLogicalAxisInline);
    return;
  }
  if (IsSubgrid(eLogicalAxisBlock) && aParent->IsMasonry(eLogicalAxisInline) &&
      mArea.mCols.mStart != 0 && mArea.mRows.Extent() != aGridAxisTrackCount &&
      (mState[eLogicalAxisBlock] & eAutoPlacement)) {
    InhibitSubgrid(aParent, eLogicalAxisBlock);
  }
}

// Each subgrid stores this data about its items etc on a frame property.
struct nsGridContainerFrame::Subgrid {
  Subgrid(const GridArea& aArea, bool aIsOrthogonal, WritingMode aCBWM)
      : mArea(aArea),
        mGridColEnd(0),
        mGridRowEnd(0),
        mMarginBorderPadding(aCBWM),
        mIsOrthogonal(aIsOrthogonal) {}

  // Return the relevant line range for the subgrid column axis.
  const LineRange& SubgridCols() const {
    return mIsOrthogonal ? mArea.mRows : mArea.mCols;
  }
  // Return the relevant line range for the subgrid row axis.
  const LineRange& SubgridRows() const {
    return mIsOrthogonal ? mArea.mCols : mArea.mRows;
  }

  // The subgrid's items.
  nsTArray<GridItemInfo> mGridItems;
  // The subgrid's abs.pos. items.
  nsTArray<GridItemInfo> mAbsPosItems;
  // The subgrid's area as a grid item, i.e. in its parent's grid space.
  GridArea mArea;
  // The (inner) grid size for the subgrid, zero-based.
  uint32_t mGridColEnd;
  uint32_t mGridRowEnd;
  // The margin+border+padding for the subgrid box in its parent grid's WM.
  // (This also includes the size of any scrollbars.)
  LogicalMargin mMarginBorderPadding;
  // Does the subgrid frame have orthogonal writing-mode to its parent grid
  // container?
  bool mIsOrthogonal;

  NS_DECLARE_FRAME_PROPERTY_DELETABLE(Prop, Subgrid)
};
using Subgrid = nsGridContainerFrame::Subgrid;

void GridItemInfo::AdjustForRemovedTracks(
    LogicalAxis aAxis, const nsTArray<uint32_t>& aNumRemovedTracks) {
  const bool abspos = mFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW);
  auto& lines = mArea.LineRangeForAxis(aAxis);
  if (abspos) {
    lines.AdjustAbsPosForRemovedTracks(aNumRemovedTracks);
  } else {
    lines.AdjustForRemovedTracks(aNumRemovedTracks);
  }
  if (IsSubgrid()) {
    auto* subgrid = SubgridFrame()->GetProperty(Subgrid::Prop());
    if (subgrid) {
      auto& lines = subgrid->mArea.LineRangeForAxis(aAxis);
      if (abspos) {
        lines.AdjustAbsPosForRemovedTracks(aNumRemovedTracks);
      } else {
        lines.AdjustForRemovedTracks(aNumRemovedTracks);
      }
    }
  }
}

/**
 * Track size data for use by subgrids (which don't do sizing of their own
 * in a subgridded axis).  A non-subgrid container stores its resolved sizes,
 * but only if it has any subgrid children.  A subgrid always stores one.
 * In a subgridded axis, we copy the parent's sizes (see CopyUsedTrackSizes).
 *
 * This struct us stored on a frame property, which may be null before the track
 * sizing step for the given container.  A null property is semantically
 * equivalent to mCanResolveLineRangeSize being false in both axes.
 * @note the axis used to access this data is in the grid container's own
 * writing-mode, same as in other track-sizing functions.
 */
struct nsGridContainerFrame::UsedTrackSizes {
  UsedTrackSizes() : mCanResolveLineRangeSize{false, false} {}

  /**
   * Setup mSizes by copying track sizes from aFrame's grid container
   * parent when aAxis is subgridded (and recurse if the parent is a subgrid
   * that doesn't have sizes yet), or by running the Track Sizing Algo when
   * the axis is not subgridded (for a subgrid).
   * Set mCanResolveLineRangeSize[aAxis] to true once we have obtained
   * sizes for an axis (if it's already true then this method is a NOP).
   */
  void ResolveTrackSizesForAxis(nsGridContainerFrame* aFrame, LogicalAxis aAxis,
                                gfxContext& aRC);

  /** Helper function for the above method */
  void ResolveSubgridTrackSizesForAxis(nsGridContainerFrame* aFrame,
                                       LogicalAxis aAxis, Subgrid* aSubgrid,
                                       gfxContext& aRC,
                                       nscoord aContentBoxSize);

  // This only has valid sizes when mCanResolveLineRangeSize is true in
  // the same axis.  It may have zero tracks (a grid with only abs.pos.
  // subgrids/items may have zero tracks).
  PerLogicalAxis<nsTArray<TrackSize>> mSizes;
  // True if mSizes can be used to resolve line range sizes in an axis.
  PerLogicalAxis<bool> mCanResolveLineRangeSize;

  NS_DECLARE_FRAME_PROPERTY_DELETABLE(Prop, UsedTrackSizes)
};
using UsedTrackSizes = nsGridContainerFrame::UsedTrackSizes;

#ifdef DEBUG
void nsGridContainerFrame::GridItemInfo::Dump() const {
  auto Dump1 = [this](const char* aMsg, LogicalAxis aAxis) {
    auto state = mState[aAxis];
    if (!state) {
      return;
    }
    printf("%s", aMsg);
    if (state & ItemState::eEdgeBits) {
      printf("subgrid-adjacent-edges(");
      if (state & ItemState::eStartEdge) {
        printf("start ");
      }
      if (state & ItemState::eEndEdge) {
        printf("end");
      }
      printf(") ");
    }
    if (state & ItemState::eAutoPlacement) {
      printf("masonry-auto ");
    }
    if (state & ItemState::eIsSubgrid) {
      printf("subgrid ");
    }
    if (state & ItemState::eIsFlexing) {
      printf("flexing ");
    }
    if (state & ItemState::eApplyAutoMinSize) {
      printf("auto-min-size ");
    }
    if (state & ItemState::eClampMarginBoxMinSize) {
      printf("clamp ");
    }
    if (state & ItemState::eIsLastItemInMasonryTrack) {
      printf("last-in-track ");
    }
    if (state & ItemState::eFirstBaseline) {
      printf("first baseline %s-alignment ",
             (state & ItemState::eSelfBaseline) ? "self" : "content");
    }
    if (state & ItemState::eLastBaseline) {
      printf("last baseline %s-alignment ",
             (state & ItemState::eSelfBaseline) ? "self" : "content");
    }
    if (state & ItemState::eIsBaselineAligned) {
      printf("%.2fpx", NSAppUnitsToFloatPixels(mBaselineOffset[aAxis],
                                               AppUnitsPerCSSPixel()));
    }
    printf("\n");
  };
  printf("grid-row: %d %d\n", mArea.mRows.mStart, mArea.mRows.mEnd);
  Dump1("  grid block-axis: ", eLogicalAxisBlock);
  printf("grid-column: %d %d\n", mArea.mCols.mStart, mArea.mCols.mEnd);
  Dump1("  grid inline-axis: ", eLogicalAxisInline);
}
#endif

/**
 * Encapsulates CSS track-sizing functions.
 */
struct nsGridContainerFrame::TrackSizingFunctions {
 private:
  TrackSizingFunctions(const GridTemplate& aTemplate,
                       const StyleImplicitGridTracks& aAutoSizing,
                       const Maybe<size_t>& aRepeatAutoIndex, bool aIsSubgrid)
      : mTemplate(aTemplate),
        mTrackListValues(aTemplate.TrackListValues()),
        mAutoSizing(aAutoSizing),
        mExplicitGridOffset(0),
        mRepeatAutoStart(aRepeatAutoIndex.valueOr(0)),
        mRepeatAutoEnd(mRepeatAutoStart),
        mHasRepeatAuto(aRepeatAutoIndex.isSome()) {
    MOZ_ASSERT(!mHasRepeatAuto || !aIsSubgrid,
               "a track-list for a subgrid can't have an <auto-repeat> track");
    if (!aIsSubgrid) {
      ExpandNonRepeatAutoTracks();
    }

#ifdef DEBUG
    if (mHasRepeatAuto) {
      MOZ_ASSERT(mExpandedTracks.Length() >= 1);
      const unsigned maxTrack = kMaxLine - 1;
      // If the exanded tracks are out of range of the maximum track, we
      // can't compare the repeat-auto start. It will be removed later during
      // grid item placement in that situation.
      if (mExpandedTracks.Length() < maxTrack) {
        MOZ_ASSERT(mRepeatAutoStart < mExpandedTracks.Length());
      }
    }
#endif
  }

 public:
  TrackSizingFunctions(const GridTemplate& aGridTemplate,
                       const StyleImplicitGridTracks& aAutoSizing,
                       bool aIsSubgrid)
      : TrackSizingFunctions(aGridTemplate, aAutoSizing,
                             aGridTemplate.RepeatAutoIndex(), aIsSubgrid) {}

 private:
  enum { ForSubgridFallbackTag };
  TrackSizingFunctions(const GridTemplate& aGridTemplate,
                       const StyleImplicitGridTracks& aAutoSizing,
                       decltype(ForSubgridFallbackTag))
      : TrackSizingFunctions(aGridTemplate, aAutoSizing, Nothing(),
                             /* aIsSubgrid */ true) {}

 public:
  /**
   * This is used in a subgridded axis to resolve sizes before its parent's
   * sizes are known for intrinsic sizing purposes.  It copies the slice of
   * the nearest non-subgridded axis' track sizing functions spanned by
   * the subgrid.
   *
   * FIXME: this was written before there was a spec... the spec now says:
   * "If calculating the layout of a grid item in this step depends on
   *  the available space in the block axis, assume the available space
   *  that it would have if any row with a definite max track sizing
   *  function had that size and all other rows were infinite."
   * https://drafts.csswg.org/css-grid-2/#subgrid-sizing
   */
  static TrackSizingFunctions ForSubgridFallback(
      nsGridContainerFrame* aSubgridFrame, const Subgrid* aSubgrid,
      nsGridContainerFrame* aParentGridContainer, LogicalAxis aParentAxis) {
    MOZ_ASSERT(aSubgrid);
    MOZ_ASSERT(aSubgridFrame->IsSubgrid(aSubgrid->mIsOrthogonal
                                            ? GetOrthogonalAxis(aParentAxis)
                                            : aParentAxis));
    nsGridContainerFrame* parent = aParentGridContainer;
    auto parentAxis = aParentAxis;
    LineRange range = aSubgrid->mArea.LineRangeForAxis(parentAxis);
    // Find our nearest non-subgridded axis and use its track sizing functions.
    while (parent->IsSubgrid(parentAxis)) {
      const auto* parentSubgrid = parent->GetProperty(Subgrid::Prop());
      auto* grandParent = parent->ParentGridContainerForSubgrid();
      auto grandParentWM = grandParent->GetWritingMode();
      bool isSameDirInAxis =
          parent->GetWritingMode().ParallelAxisStartsOnSameSide(parentAxis,
                                                                grandParentWM);
      if (MOZ_UNLIKELY(!isSameDirInAxis)) {
        auto end = parentAxis == eLogicalAxisBlock ? parentSubgrid->mGridRowEnd
                                                   : parentSubgrid->mGridColEnd;
        range.ReverseDirection(end);
        // range is now in the same direction as the grand-parent's axis
      }
      auto grandParentAxis = parentSubgrid->mIsOrthogonal
                                 ? GetOrthogonalAxis(parentAxis)
                                 : parentAxis;
      const auto& parentRange =
          parentSubgrid->mArea.LineRangeForAxis(grandParentAxis);
      range.Translate(parentRange.mStart);
      // range is now in the grand-parent's coordinates
      parentAxis = grandParentAxis;
      parent = grandParent;
    }
    const auto* pos = parent->StylePosition();
    const auto isInlineAxis = parentAxis == eLogicalAxisInline;
    const auto& szf =
        isInlineAxis ? pos->mGridTemplateRows : pos->mGridTemplateColumns;
    const auto& autoSizing =
        isInlineAxis ? pos->mGridAutoColumns : pos->mGridAutoRows;
    return TrackSizingFunctions(szf, autoSizing, ForSubgridFallbackTag);
  }

  /**
   * Initialize the number of auto-fill/fit tracks to use.
   * This can be zero if no auto-fill/fit track was specified, or if the repeat
   * begins after the maximum allowed track.
   */
  void InitRepeatTracks(const NonNegativeLengthPercentageOrNormal& aGridGap,
                        nscoord aMinSize, nscoord aSize, nscoord aMaxSize) {
    const uint32_t maxTrack = kMaxLine - 1;
    // Check for a repeat after the maximum allowed track.
    if (MOZ_UNLIKELY(mRepeatAutoStart >= maxTrack)) {
      mHasRepeatAuto = false;
      mRepeatAutoStart = 0;
      mRepeatAutoEnd = 0;
      return;
    }
    uint32_t repeatTracks =
        CalculateRepeatFillCount(aGridGap, aMinSize, aSize, aMaxSize) *
        NumRepeatTracks();
    // Clamp the number of repeat tracks to the maximum possible track.
    repeatTracks = std::min(repeatTracks, maxTrack - mRepeatAutoStart);
    SetNumRepeatTracks(repeatTracks);
    // Blank out the removed flags for each of these tracks.
    mRemovedRepeatTracks.SetLength(repeatTracks);
    for (auto& track : mRemovedRepeatTracks) {
      track = false;
    }
  }

  uint32_t CalculateRepeatFillCount(
      const NonNegativeLengthPercentageOrNormal& aGridGap, nscoord aMinSize,
      nscoord aSize, nscoord aMaxSize) const {
    if (!mHasRepeatAuto) {
      return 0;
    }
    // At this point no tracks will have been collapsed, so the RepeatEndDelta
    // should not be negative.
    MOZ_ASSERT(RepeatEndDelta() >= 0);
    // Note that this uses NumRepeatTracks and mRepeatAutoStart/End, although
    // the result of this method is used to change those values to a fully
    // expanded value. Spec quotes are from
    // https://drafts.csswg.org/css-grid/#repeat-notation
    const uint32_t numTracks = mExpandedTracks.Length() + RepeatEndDelta();
    MOZ_ASSERT(numTracks >= 1, "expected at least the repeat() track");
    if (MOZ_UNLIKELY(numTracks >= kMaxLine)) {
      // The fixed tracks plus an entire repetition is either larger or as
      // large as the maximum track, so we do not need to measure how many
      // repetitions will fit. This also avoids needing to check for if
      // kMaxLine - numTracks would underflow at the end where we clamp the
      // result.
      return 1;
    }
    nscoord maxFill = aSize != NS_UNCONSTRAINEDSIZE ? aSize : aMaxSize;
    if (maxFill == NS_UNCONSTRAINEDSIZE && aMinSize == 0) {
      // "Otherwise, the specified track list repeats only once."
      return 1;
    }
    nscoord repeatTrackSum = 0;
    // Note that one repeat() track size is included in |sum| in this loop.
    nscoord sum = 0;
    const nscoord percentBasis = aSize;
    for (uint32_t i = 0; i < numTracks; ++i) {
      // "treating each track as its max track sizing function if that is
      // definite or as its minimum track sizing function otherwise"
      // https://drafts.csswg.org/css-grid/#valdef-repeat-auto-fill
      const auto& sizingFunction = SizingFor(i);
      const auto& maxCoord = sizingFunction.GetMax();
      const auto* coord = &maxCoord;
      if (!coord->IsBreadth()) {
        coord = &sizingFunction.GetMin();
        if (!coord->IsBreadth()) {
          return 1;
        }
      }
      nscoord trackSize = ::ResolveToDefiniteSize(*coord, percentBasis);
      if (i >= mRepeatAutoStart && i < mRepeatAutoEnd) {
        // Use a minimum 1px for the repeat() track-size.
        if (trackSize < AppUnitsPerCSSPixel()) {
          trackSize = AppUnitsPerCSSPixel();
        }
        repeatTrackSum += trackSize;
      }
      sum += trackSize;
    }
    nscoord gridGap = nsLayoutUtils::ResolveGapToLength(aGridGap, aSize);
    if (numTracks > 1) {
      // Add grid-gaps for all the tracks including the repeat() track.
      sum += gridGap * (numTracks - 1);
    }
    // Calculate the max number of tracks that fits without overflow.
    nscoord available = maxFill != NS_UNCONSTRAINEDSIZE ? maxFill : aMinSize;
    nscoord spaceToFill = available - sum;
    if (spaceToFill <= 0) {
      // "if any number of repetitions would overflow, then 1 repetition"
      return 1;
    }
    // Calculate the max number of tracks that fits without overflow.
    // Since we already have one repetition in sum, we can simply add one grid
    // gap for each element in the repeat.
    div_t q = div(spaceToFill, repeatTrackSum + gridGap * NumRepeatTracks());
    // The +1 here is for the one repeat track we already accounted for above.
    uint32_t numRepeatTracks = q.quot + 1;
    if (q.rem != 0 && maxFill == NS_UNCONSTRAINEDSIZE) {
      // "Otherwise, if the grid container has a definite min size in
      // the relevant axis, the number of repetitions is the largest possible
      // positive integer that fulfills that minimum requirement."
      ++numRepeatTracks;  // one more to ensure the grid is at least min-size
    }
    // Clamp the number of repeat tracks so that the last line <= kMaxLine.
    // (note that |numTracks| already includes one repeat() track)
    MOZ_ASSERT(numTracks >= NumRepeatTracks());
    const uint32_t maxRepeatTrackCount = kMaxLine - numTracks;
    const uint32_t maxRepetitions = maxRepeatTrackCount / NumRepeatTracks();
    return std::min(numRepeatTracks, maxRepetitions);
  }

  /**
   * Compute the explicit grid end line number (in a zero-based grid).
   * @param aGridTemplateAreasEnd 'grid-template-areas' end line in this axis
   */
  uint32_t ComputeExplicitGridEnd(uint32_t aGridTemplateAreasEnd) {
    uint32_t end = NumExplicitTracks() + 1;
    end = std::max(end, aGridTemplateAreasEnd);
    end = std::min(end, uint32_t(kMaxLine));
    return end;
  }
  const StyleTrackSize& SizingFor(uint32_t aTrackIndex) const {
    static const StyleTrackSize kAutoTrackSize =
        StyleTrackSize::Breadth(StyleTrackBreadth::Auto());
    // |aIndex| is the relative index to mAutoSizing. A negative value means it
    // is the last Nth element.
    auto getImplicitSize = [this](int32_t aIndex) -> const StyleTrackSize& {
      MOZ_ASSERT(!(mAutoSizing.Length() == 1 &&
                   mAutoSizing.AsSpan()[0] == kAutoTrackSize),
                 "It's impossible to have one track with auto value because we "
                 "filter out this case during parsing");

      if (mAutoSizing.IsEmpty()) {
        return kAutoTrackSize;
      }

      // If multiple track sizes are given, the pattern is repeated as necessary
      // to find the size of the implicit tracks.
      int32_t i = aIndex % int32_t(mAutoSizing.Length());
      if (i < 0) {
        i += mAutoSizing.Length();
      }
      return mAutoSizing.AsSpan()[i];
    };

    if (MOZ_UNLIKELY(aTrackIndex < mExplicitGridOffset)) {
      // The last implicit grid track before the explicit grid receives the
      // last specified size, and so on backwards. Therefore we pass the
      // negative relative index to imply that we should get the implicit size
      // from the last Nth specified grid auto size.
      return getImplicitSize(int32_t(aTrackIndex) -
                             int32_t(mExplicitGridOffset));
    }
    uint32_t index = aTrackIndex - mExplicitGridOffset;
    MOZ_ASSERT(mRepeatAutoStart <= mRepeatAutoEnd);

    if (index >= mRepeatAutoStart) {
      if (index < mRepeatAutoEnd) {
        // Expand the repeat tracks.
        const auto& indices = mExpandedTracks[mRepeatAutoStart];
        const TrackListValue& value = mTrackListValues[indices.first];

        // We expect the default to be used for all track repeats.
        MOZ_ASSERT(indices.second == 0);

        const auto& repeatTracks = value.AsTrackRepeat().track_sizes.AsSpan();

        // Find the repeat track to use, skipping over any collapsed tracks.
        const uint32_t finalRepeatIndex = (index - mRepeatAutoStart);
        uint32_t repeatWithCollapsed = 0;
        // NOTE: We need SizingFor before the final collapsed tracks are known.
        // We know that it's invalid to have empty mRemovedRepeatTracks when
        // there are any repeat tracks, so we can detect that situation here.
        if (mRemovedRepeatTracks.IsEmpty()) {
          repeatWithCollapsed = finalRepeatIndex;
        } else {
          // Count up through the repeat tracks, until we have seen
          // finalRepeatIndex number of non-collapsed tracks.
          for (uint32_t repeatNoCollapsed = 0;
               repeatNoCollapsed < finalRepeatIndex; repeatWithCollapsed++) {
            if (!mRemovedRepeatTracks[repeatWithCollapsed]) {
              repeatNoCollapsed++;
            }
          }
          // If we stopped iterating on a collapsed track, continue to the next
          // non-collapsed track.
          while (mRemovedRepeatTracks[repeatWithCollapsed]) {
            repeatWithCollapsed++;
          }
        }
        return repeatTracks[repeatWithCollapsed % repeatTracks.Length()];
      } else {
        // The index is after the repeat auto range, adjust it to skip over the
        // repeat value. This will have no effect if there is no auto repeat,
        // since then RepeatEndDelta will return zero.
        index -= RepeatEndDelta();
      }
    }
    if (index >= mExpandedTracks.Length()) {
      return getImplicitSize(index - mExpandedTracks.Length());
    }
    auto& indices = mExpandedTracks[index];
    const TrackListValue& value = mTrackListValues[indices.first];
    if (value.IsTrackSize()) {
      MOZ_ASSERT(indices.second == 0);
      return value.AsTrackSize();
    }
    return value.AsTrackRepeat().track_sizes.AsSpan()[indices.second];
  }
  const StyleTrackBreadth& MaxSizingFor(uint32_t aTrackIndex) const {
    return SizingFor(aTrackIndex).GetMax();
  }
  const StyleTrackBreadth& MinSizingFor(uint32_t aTrackIndex) const {
    return SizingFor(aTrackIndex).GetMin();
  }
  uint32_t NumExplicitTracks() const {
    return mExpandedTracks.Length() + RepeatEndDelta();
  }
  uint32_t NumRepeatTracks() const { return mRepeatAutoEnd - mRepeatAutoStart; }
  // The difference between mExplicitGridEnd and mSizingFunctions.Length().
  int32_t RepeatEndDelta() const {
    return mHasRepeatAuto ? int32_t(NumRepeatTracks()) - 1 : 0;
  }
  void SetNumRepeatTracks(uint32_t aNumRepeatTracks) {
    MOZ_ASSERT(mHasRepeatAuto || aNumRepeatTracks == 0);
    mRepeatAutoEnd = mRepeatAutoStart + aNumRepeatTracks;
  }

  // Store mTrackListValues into mExpandedTracks with `repeat(INTEGER, ...)`
  // tracks expanded.
  void ExpandNonRepeatAutoTracks() {
    for (size_t i = 0; i < mTrackListValues.Length(); ++i) {
      auto& value = mTrackListValues[i];
      if (value.IsTrackSize()) {
        mExpandedTracks.EmplaceBack(i, 0);
        continue;
      }
      auto& repeat = value.AsTrackRepeat();
      if (!repeat.count.IsNumber()) {
        MOZ_ASSERT(i == mRepeatAutoStart);
        mRepeatAutoStart = mExpandedTracks.Length();
        mRepeatAutoEnd = mRepeatAutoStart + repeat.track_sizes.Length();
        mExpandedTracks.EmplaceBack(i, 0);
        continue;
      }
      for (auto j : IntegerRange(repeat.count.AsNumber())) {
        Unused << j;
        size_t trackSizesCount = repeat.track_sizes.Length();
        for (auto k : IntegerRange(trackSizesCount)) {
          mExpandedTracks.EmplaceBack(i, k);
        }
      }
    }
    if (MOZ_UNLIKELY(mExpandedTracks.Length() > kMaxLine - 1)) {
      mExpandedTracks.TruncateLength(kMaxLine - 1);
      if (mHasRepeatAuto && mRepeatAutoStart > kMaxLine - 1) {
        // The `repeat(auto-fill/fit)` track is outside the clamped grid.
        mHasRepeatAuto = false;
      }
    }
  }

  // Some style data references, for easy access.
  const GridTemplate& mTemplate;
  const Span<const TrackListValue> mTrackListValues;
  const StyleImplicitGridTracks& mAutoSizing;
  // An array from expanded track sizes (without expanding auto-repeat, which is
  // included just once at `mRepeatAutoStart`).
  //
  // Each entry contains two indices, the first into mTrackListValues, and a
  // second one inside mTrackListValues' repeat value, if any, or zero
  // otherwise.
  nsTArray<std::pair<size_t, size_t>> mExpandedTracks;
  // Offset from the start of the implicit grid to the first explicit track.
  uint32_t mExplicitGridOffset;
  // The index of the repeat(auto-fill/fit) track, or zero if there is none.
  // Relative to mExplicitGridOffset (repeat tracks are explicit by definition).
  uint32_t mRepeatAutoStart;
  // The (hypothetical) index of the last such repeat() track.
  uint32_t mRepeatAutoEnd;
  // True if there is a specified repeat(auto-fill/fit) track.
  bool mHasRepeatAuto;
  // True if this track (relative to mRepeatAutoStart) is a removed auto-fit.
  // Indexed relative to mExplicitGridOffset + mRepeatAutoStart.
  nsTArray<bool> mRemovedRepeatTracks;
};

/**
 * Utility class to find line names.  It provides an interface to lookup line
 * names with a dynamic number of repeat(auto-fill/fit) tracks taken into
 * account.
 */
class MOZ_STACK_CLASS nsGridContainerFrame::LineNameMap {
 public:
  /**
   * Create a LineNameMap.
   * @param aStylePosition the style for the grid container
   * @param aImplicitNamedAreas the implicit areas for the grid container
   * @param aGridTemplate is the grid-template-rows/columns data for this axis
   * @param aParentLineNameMap the parent grid's map parallel to this map, or
   *                           null if this map isn't for a subgrid
   * @param aRange the subgrid's range in the parent grid, or null
   * @param aIsSameDirection true if our axis progresses in the same direction
   *                              in the subgrid and parent
   */
  LineNameMap(const nsStylePosition* aStylePosition,
              const ImplicitNamedAreas* aImplicitNamedAreas,
              const TrackSizingFunctions& aTracks,
              const LineNameMap* aParentLineNameMap, const LineRange* aRange,
              bool aIsSameDirection)
      : mStylePosition(aStylePosition),
        mAreas(aImplicitNamedAreas),
        mRepeatAutoStart(aTracks.mRepeatAutoStart),
        mRepeatAutoEnd(aTracks.mRepeatAutoEnd),
        mRepeatEndDelta(aTracks.RepeatEndDelta()),
        mParentLineNameMap(aParentLineNameMap),
        mRange(aRange),
        mIsSameDirection(aIsSameDirection),
        mHasRepeatAuto(aTracks.mHasRepeatAuto) {
    if (MOZ_UNLIKELY(aRange)) {  // subgrid case
      mClampMinLine = 1;
      mClampMaxLine = 1 + aRange->Extent();
      mRepeatAutoEnd = mRepeatAutoStart;
      const auto& styleSubgrid = aTracks.mTemplate.AsSubgrid();
      const auto fillLen = styleSubgrid->fill_len;
      mHasRepeatAuto = fillLen != 0;
      if (mHasRepeatAuto) {
        const auto& lineNameLists = styleSubgrid->names;
        const int32_t extraAutoFillLineCount =
            mClampMaxLine - lineNameLists.Length();
        // Maximum possible number of repeat name lists. This must be reduced
        // to a whole number of repetitions of the fill length.
        const uint32_t possibleRepeatLength =
            std::max<int32_t>(0, extraAutoFillLineCount + fillLen);
        const uint32_t repeatRemainder = possibleRepeatLength % fillLen;
        mRepeatAutoStart = styleSubgrid->fill_start;
        mRepeatAutoEnd =
            mRepeatAutoStart + possibleRepeatLength - repeatRemainder;
      }
    } else {
      mClampMinLine = kMinLine;
      mClampMaxLine = kMaxLine;
      if (mHasRepeatAuto) {
        mTrackAutoRepeatLineNames =
            aTracks.mTemplate.GetRepeatAutoValue()->line_names.AsSpan();
      }
    }
    ExpandRepeatLineNames(!!aRange, aTracks);
    if (mHasRepeatAuto) {
      // We need mTemplateLinesEnd to be after all line names.
      // mExpandedLineNames has one repetition of the repeat(auto-fit/fill)
      // track name lists already, so we must subtract the number of repeat
      // track name lists to get to the number of non-repeat tracks, minus 2
      // because the first and last line name lists are shared with the
      // preceding and following non-repeat line name lists. We then add
      // mRepeatEndDelta to include the interior line name lists from repeat
      // tracks.
      mTemplateLinesEnd = mExpandedLineNames.Length() -
                          (mTrackAutoRepeatLineNames.Length() - 2) +
                          mRepeatEndDelta;
    } else {
      mTemplateLinesEnd = mExpandedLineNames.Length();
    }
    MOZ_ASSERT(mHasRepeatAuto || mRepeatEndDelta <= 0);
    MOZ_ASSERT(!mHasRepeatAuto || aRange ||
               (mExpandedLineNames.Length() >= 2 &&
                mRepeatAutoStart <= mExpandedLineNames.Length()));
  }

  // Store line names into mExpandedLineNames with `repeat(INTEGER, ...)`
  // expanded (for non-subgrid), and all `repeat(...)` expanded (for subgrid).
  void ExpandRepeatLineNames(bool aIsSubgrid,
                             const TrackSizingFunctions& aTracks) {
    auto lineNameLists = aTracks.mTemplate.LineNameLists(aIsSubgrid);

    const auto& trackListValues = aTracks.mTrackListValues;
    const NameList* nameListToMerge = nullptr;
    // NOTE(emilio): We rely on std::move clearing out the array.
    SmallPointerArray<const NameList> names;
    // This adjusts for outputting the repeat auto names in subgrid. In that
    // case, all of the repeat values are handled in a single iteration.
    const uint32_t subgridRepeatDelta =
        (aIsSubgrid && mHasRepeatAuto)
            ? (aTracks.mTemplate.AsSubgrid()->fill_len - 1)
            : 0;
    const uint32_t end = std::min<uint32_t>(
        lineNameLists.Length() - subgridRepeatDelta, mClampMaxLine + 1);
    for (uint32_t i = 0; i < end; ++i) {
      if (aIsSubgrid) {
        if (MOZ_UNLIKELY(mHasRepeatAuto && i == mRepeatAutoStart)) {
          // XXX expand 'auto-fill' names for subgrid for now since HasNameAt()
          // only deals with auto-repeat **tracks** currently.
          const auto& styleSubgrid = aTracks.mTemplate.AsSubgrid();
          MOZ_ASSERT(styleSubgrid->fill_len > 0);
          for (auto j = i; j < mRepeatAutoEnd; ++j) {
            const auto repeatIndex = (j - i) % styleSubgrid->fill_len;
            names.AppendElement(
                &lineNameLists[styleSubgrid->fill_start + repeatIndex]);
            mExpandedLineNames.AppendElement(std::move(names));
          }
        } else if (mHasRepeatAuto && i > mRepeatAutoStart) {
          const auto& styleSubgrid = aTracks.mTemplate.AsSubgrid();
          names.AppendElement(&lineNameLists[i + styleSubgrid->fill_len - 1]);
          mExpandedLineNames.AppendElement(std::move(names));
        } else {
          names.AppendElement(&lineNameLists[i]);
          mExpandedLineNames.AppendElement(std::move(names));
        }
        // XXX expand repeat(<integer>, ...) line names here (bug 1583429)
        continue;
      }

      if (nameListToMerge) {
        names.AppendElement(nameListToMerge);
        nameListToMerge = nullptr;
      }
      names.AppendElement(&lineNameLists[i]);
      if (i >= trackListValues.Length()) {
        mExpandedLineNames.AppendElement(std::move(names));
        continue;
      }
      const auto& value = trackListValues[i];
      if (value.IsTrackSize()) {
        mExpandedLineNames.AppendElement(std::move(names));
        continue;
      }
      const auto& repeat = value.AsTrackRepeat();
      if (!repeat.count.IsNumber()) {
        const auto repeatNames = repeat.line_names.AsSpan();
        // If the repeat was truncated due to more than kMaxLine tracks, then
        // the repeat will no longer be set on mRepeatAutoStart).
        MOZ_ASSERT(!mHasRepeatAuto ||
                   mRepeatAutoStart == mExpandedLineNames.Length());
        MOZ_ASSERT(repeatNames.Length() >= 2);
        for (const auto j : IntegerRange(repeatNames.Length() - 1)) {
          names.AppendElement(&repeatNames[j]);
          mExpandedLineNames.AppendElement(std::move(names));
        }
        nameListToMerge = &repeatNames[repeatNames.Length() - 1];
        continue;
      }
      for (auto j : IntegerRange(repeat.count.AsNumber())) {
        Unused << j;
        if (nameListToMerge) {
          names.AppendElement(nameListToMerge);
          nameListToMerge = nullptr;
        }
        size_t trackSizesCount = repeat.track_sizes.Length();
        auto repeatLineNames = repeat.line_names.AsSpan();
        MOZ_ASSERT(repeatLineNames.Length() == trackSizesCount ||
                   repeatLineNames.Length() == trackSizesCount + 1);
        for (auto k : IntegerRange(trackSizesCount)) {
          names.AppendElement(&repeatLineNames[k]);
          mExpandedLineNames.AppendElement(std::move(names));
        }
        if (repeatLineNames.Length() == trackSizesCount + 1) {
          nameListToMerge = &repeatLineNames[trackSizesCount];
        }
      }
    }

    if (MOZ_UNLIKELY(mExpandedLineNames.Length() > uint32_t(mClampMaxLine))) {
      mExpandedLineNames.TruncateLength(mClampMaxLine);
    }
    if (MOZ_UNLIKELY(mHasRepeatAuto && aIsSubgrid)) {
      mHasRepeatAuto = false;  // we've expanded all subgrid auto-fill lines
    }
  }

  /**
   * Find the aNth occurrence of aName, searching forward if aNth is positive,
   * and in reverse if aNth is negative (aNth == 0 is invalid), starting from
   * aFromIndex (not inclusive), and return a 1-based line number.
   * Also take into account there is an unconditional match at the lines in
   * aImplicitLines.
   * Return zero if aNth occurrences can't be found.  In that case, aNth has
   * been decremented with the number of occurrences that were found (if any).
   *
   * E.g. to search for "A 2" forward from the start of the grid: aName is "A"
   * aNth is 2 and aFromIndex is zero.  To search for "A -2", aNth is -2 and
   * aFromIndex is ExplicitGridEnd + 1 (which is the line "before" the last
   * line when we're searching in reverse).  For "span A 2", aNth is 2 when
   * used on a grid-[row|column]-end property and -2 for a *-start property,
   * and aFromIndex is the line (which we should skip) on the opposite property.
   */
  uint32_t FindNamedLine(nsAtom* aName, int32_t* aNth, uint32_t aFromIndex,
                         const nsTArray<uint32_t>& aImplicitLines) const {
    MOZ_ASSERT(aName);
    MOZ_ASSERT(!aName->IsEmpty());
    MOZ_ASSERT(aNth && *aNth != 0);
    if (*aNth > 0) {
      return FindLine(aName, aNth, aFromIndex, aImplicitLines);
    }
    int32_t nth = -*aNth;
    int32_t line = RFindLine(aName, &nth, aFromIndex, aImplicitLines);
    *aNth = -nth;
    return line;
  }

  /**
   * Return a set of lines in aImplicitLines which matches the area name aName
   * on aSide.  For example, for aName "a" and aSide being an end side, it
   * returns the line numbers which would match "a-end" in the relevant axis.
   * For subgrids it includes searching the relevant axis in all ancestor
   * grids too (within this subgrid's spanned area).  If an ancestor has
   * opposite direction, we switch aSide to the opposite logical side so we
   * match on the same physical side as the original subgrid we're resolving
   * the name for.
   */
  void FindNamedAreas(nsAtom* aName, LogicalSide aSide,
                      nsTArray<uint32_t>& aImplicitLines) const {
    // True if we're currently in a map that has the same direction as 'this'.
    bool sameDirectionAsThis = true;
    uint32_t min = !mParentLineNameMap ? 1 : mClampMinLine;
    uint32_t max = mClampMaxLine;
    for (auto* map = this; true;) {
      uint32_t line = map->FindNamedArea(aName, aSide, min, max);
      if (line > 0) {
        if (MOZ_LIKELY(sameDirectionAsThis)) {
          line -= min - 1;
        } else {
          line = max - line + 1;
        }
        aImplicitLines.AppendElement(line);
      }
      auto* parent = map->mParentLineNameMap;
      if (!parent) {
        if (MOZ_UNLIKELY(aImplicitLines.Length() > 1)) {
          // Remove duplicates and sort in ascending order.
          aImplicitLines.Sort();
          for (size_t i = 0; i < aImplicitLines.Length(); ++i) {
            uint32_t prev = aImplicitLines[i];
            auto j = i + 1;
            const auto start = j;
            while (j < aImplicitLines.Length() && aImplicitLines[j] == prev) {
              ++j;
            }
            if (j != start) {
              aImplicitLines.RemoveElementsAt(start, j - start);
            }
          }
        }
        return;
      }
      if (MOZ_UNLIKELY(!map->mIsSameDirection)) {
        aSide = GetOppositeSide(aSide);
        sameDirectionAsThis = !sameDirectionAsThis;
      }
      min = map->TranslateToParentMap(min);
      max = map->TranslateToParentMap(max);
      if (min > max) {
        MOZ_ASSERT(!map->mIsSameDirection);
        std::swap(min, max);
      }
      map = parent;
    }
  }

  /**
   * Return true if any implicit named areas match aName, in this map or
   * in any of our ancestor maps.
   */
  bool HasImplicitNamedArea(nsAtom* aName) const {
    const auto* map = this;
    do {
      if (map->mAreas && map->mAreas->has(aName)) {
        return true;
      }
      map = map->mParentLineNameMap;
    } while (map);
    return false;
  }

  // For generating line name data for devtools.
  nsTArray<nsTArray<StyleCustomIdent>>
  GetResolvedLineNamesForComputedGridTrackInfo() const {
    nsTArray<nsTArray<StyleCustomIdent>> result;
    for (auto& expandedLine : mExpandedLineNames) {
      nsTArray<StyleCustomIdent> line;
      for (auto* chunk : expandedLine) {
        for (auto& name : chunk->AsSpan()) {
          line.AppendElement(name);
        }
      }
      result.AppendElement(std::move(line));
    }
    return result;
  }

  nsTArray<RefPtr<nsAtom>> GetExplicitLineNamesAtIndex(uint32_t aIndex) const {
    nsTArray<RefPtr<nsAtom>> lineNames;
    if (aIndex < mTemplateLinesEnd) {
      const auto nameLists = GetLineNamesAt(aIndex);
      for (const NameList* nameList : nameLists) {
        for (const auto& name : nameList->AsSpan()) {
          lineNames.AppendElement(name.AsAtom());
        }
      }
    }
    return lineNames;
  }

  const nsTArray<SmallPointerArray<const NameList>>& ExpandedLineNames() const {
    return mExpandedLineNames;
  }
  const Span<const StyleOwnedSlice<StyleCustomIdent>>&
  TrackAutoRepeatLineNames() const {
    return mTrackAutoRepeatLineNames;
  }
  bool HasRepeatAuto() const { return mHasRepeatAuto; }
  uint32_t NumRepeatTracks() const { return mRepeatAutoEnd - mRepeatAutoStart; }
  uint32_t RepeatAutoStart() const { return mRepeatAutoStart; }

  // The min/max line number (1-based) for clamping.
  int32_t mClampMinLine;
  int32_t mClampMaxLine;

 private:
  // Return true if this map represents a subgridded axis.
  bool IsSubgridded() const { return mParentLineNameMap != nullptr; }

  /**
   * @see FindNamedLine, this function searches forward.
   */
  uint32_t FindLine(nsAtom* aName, int32_t* aNth, uint32_t aFromIndex,
                    const nsTArray<uint32_t>& aImplicitLines) const {
    MOZ_ASSERT(aNth && *aNth > 0);
    int32_t nth = *aNth;
    // For a subgrid we need to search to the end of the grid rather than
    // the end of the local name list, since ancestors might match.
    const uint32_t end = IsSubgridded() ? mClampMaxLine : mTemplateLinesEnd;
    uint32_t line;
    uint32_t i = aFromIndex;
    for (; i < end; i = line) {
      line = i + 1;
      if (Contains(i, aName) || aImplicitLines.Contains(line)) {
        if (--nth == 0) {
          return line;
        }
      }
    }
    for (auto implicitLine : aImplicitLines) {
      if (implicitLine > i) {
        // implicitLine is after the lines we searched above so it's last.
        // (grid-template-areas has more tracks than
        // grid-template-[rows|columns])
        if (--nth == 0) {
          return implicitLine;
        }
      }
    }
    MOZ_ASSERT(nth > 0, "should have returned a valid line above already");
    *aNth = nth;
    return 0;
  }

  /**
   * @see FindNamedLine, this function searches in reverse.
   */
  uint32_t RFindLine(nsAtom* aName, int32_t* aNth, uint32_t aFromIndex,
                     const nsTArray<uint32_t>& aImplicitLines) const {
    MOZ_ASSERT(aNth && *aNth > 0);
    if (MOZ_UNLIKELY(aFromIndex == 0)) {
      return 0;  // There are no named lines beyond the start of the explicit
                 // grid.
    }
    --aFromIndex;  // (shift aFromIndex so we can treat it as inclusive)
    int32_t nth = *aNth;
    // Implicit lines may be beyond the explicit grid so we match those
    // first if it's within the mTemplateLinesEnd..aFromIndex range.
    // aImplicitLines is presumed sorted.
    // For a subgrid we need to search to the end of the grid rather than
    // the end of the local name list, since ancestors might match.
    const uint32_t end = IsSubgridded() ? mClampMaxLine : mTemplateLinesEnd;
    for (auto implicitLine : Reversed(aImplicitLines)) {
      if (implicitLine <= end) {
        break;
      }
      if (implicitLine < aFromIndex) {
        if (--nth == 0) {
          return implicitLine;
        }
      }
    }
    for (uint32_t i = std::min(aFromIndex, end); i; --i) {
      if (Contains(i - 1, aName) || aImplicitLines.Contains(i)) {
        if (--nth == 0) {
          return i;
        }
      }
    }
    MOZ_ASSERT(nth > 0, "should have returned a valid line above already");
    *aNth = nth;
    return 0;
  }

  // Return true if aName exists at aIndex in this map or any parent map.
  bool Contains(uint32_t aIndex, nsAtom* aName) const {
    const auto* map = this;
    while (true) {
      if (aIndex < map->mTemplateLinesEnd && map->HasNameAt(aIndex, aName)) {
        return true;
      }
      auto* parent = map->mParentLineNameMap;
      if (!parent) {
        return false;
      }
      uint32_t line = map->TranslateToParentMap(aIndex + 1);
      MOZ_ASSERT(line >= 1, "expected a 1-based line number");
      aIndex = line - 1;
      map = parent;
    }
    MOZ_ASSERT_UNREACHABLE("we always return from inside the loop above");
  }

  static bool Contains(Span<const StyleCustomIdent> aNames, nsAtom* aName) {
    for (auto& name : aNames) {
      if (name.AsAtom() == aName) {
        return true;
      }
    }
    return false;
  }

  // Return true if aName exists at aIndex in this map.
  bool HasNameAt(const uint32_t aIndex, nsAtom* const aName) const {
    const auto nameLists = GetLineNamesAt(aIndex);
    for (const NameList* nameList : nameLists) {
      if (Contains(nameList->AsSpan(), aName)) {
        return true;
      }
    }
    return false;
  }

  // Get the line names at an index.
  // This accounts for auto repeat. The results may be spread over multiple name
  // lists returned in the array, which is done to avoid unneccessarily copying
  // the arrays to concatenate them.
  SmallPointerArray<const NameList> GetLineNamesAt(
      const uint32_t aIndex) const {
    SmallPointerArray<const NameList> names;
    // The index into mExpandedLineNames to use, if aIndex doesn't point to a
    // name inside of a auto repeat.
    uint32_t repeatAdjustedIndex = aIndex;
    if (mHasRepeatAuto) {
      // If the index is inside of the auto repeat, use the repeat line
      // names. Otherwise, if the index is past the end of the repeat it must
      // be adjusted to acount for the repeat tracks.
      // mExpandedLineNames has the first and last line name lists from the
      // repeat in it already, so we can just ignore aIndex == mRepeatAutoStart
      // and treat when aIndex == mRepeatAutoEnd the same as any line after the
      // the repeat.
      const uint32_t maxRepeatLine = mTrackAutoRepeatLineNames.Length() - 1;
      if (aIndex > mRepeatAutoStart && aIndex < mRepeatAutoEnd) {
        // The index is inside the auto repeat. Calculate the lines to use,
        // including the previous repetitions final names when we roll over
        // from one repetition to the next.
        const uint32_t repeatIndex =
            (aIndex - mRepeatAutoStart) % maxRepeatLine;
        if (repeatIndex == 0) {
          // The index is at the start of a new repetition. The start of the
          // first repetition is intentionally ignored above, so this will
          // consider both the end of the previous repetition and the start
          // the one that contains aIndex.
          names.AppendElement(&mTrackAutoRepeatLineNames[maxRepeatLine]);
        }
        names.AppendElement(&mTrackAutoRepeatLineNames[repeatIndex]);
        return names;
      }
      if (aIndex != mRepeatAutoStart && aIndex >= mRepeatAutoEnd) {
        // Adjust the index to account for the line names of the repeat.
        repeatAdjustedIndex -= mRepeatEndDelta;
        repeatAdjustedIndex += mTrackAutoRepeatLineNames.Length() - 2;
      }
    }
    MOZ_ASSERT(names.IsEmpty());
    // The index is not inside the repeat tracks, or no repeat tracks exist.
    const auto& nameLists = mExpandedLineNames[repeatAdjustedIndex];
    for (const NameList* nameList : nameLists) {
      names.AppendElement(nameList);
    }
    return names;
  }

  // Translate a subgrid line (1-based) to a parent line (1-based).
  uint32_t TranslateToParentMap(uint32_t aLine) const {
    if (MOZ_LIKELY(mIsSameDirection)) {
      return aLine + mRange->mStart;
    }
    MOZ_ASSERT(mRange->mEnd + 1 >= aLine);
    return mRange->mEnd - (aLine - 1) + 1;
  }

  /**
   * Return the 1-based line that match aName in 'grid-template-areas'
   * on the side aSide.  Clamp the result to aMin..aMax but require
   * that some part of the area is inside for it to match.
   * Return zero if there is no match.
   */
  uint32_t FindNamedArea(nsAtom* aName, LogicalSide aSide, int32_t aMin,
                         int32_t aMax) const {
    if (const NamedArea* area = FindNamedArea(aName)) {
      int32_t start = IsBlock(aSide) ? area->rows.start : area->columns.start;
      int32_t end = IsBlock(aSide) ? area->rows.end : area->columns.end;
      if (IsStart(aSide)) {
        if (start >= aMin) {
          if (start <= aMax) {
            return start;
          }
        } else if (end >= aMin) {
          return aMin;
        }
      } else {
        if (end <= aMax) {
          if (end >= aMin) {
            return end;
          }
        } else if (start <= aMax) {
          return aMax;
        }
      }
    }
    return 0;  // no match
  }

  /**
   * A convenience method to lookup a name in 'grid-template-areas'.
   * @return null if not found
   */
  const NamedArea* FindNamedArea(nsAtom* aName) const {
    if (mStylePosition->mGridTemplateAreas.IsNone()) {
      return nullptr;
    }
    const auto areas = mStylePosition->mGridTemplateAreas.AsAreas();
    for (const NamedArea& area : areas->areas.AsSpan()) {
      if (area.name.AsAtom() == aName) {
        return &area;
      }
    }
    return nullptr;
  }

  // Some style data references, for easy access.
  const nsStylePosition* mStylePosition;
  const ImplicitNamedAreas* mAreas;
  // The expanded list of line-names. Each entry is usually a single NameList,
  // but can be multiple in the case where repeat() expands to something that
  // has a line name list at the end.
  nsTArray<SmallPointerArray<const NameList>> mExpandedLineNames;
  // The repeat(auto-fill/fit) track value, if any. (always empty for subgrid)
  Span<const StyleOwnedSlice<StyleCustomIdent>> mTrackAutoRepeatLineNames;
  // The index of the repeat(auto-fill/fit) track, or zero if there is none.
  uint32_t mRepeatAutoStart;
  // The index one past the end of the repeat(auto-fill/fit) tracks. Equal to
  // mRepeatAutoStart if there are no repeat(auto-fill/fit) tracks.
  uint32_t mRepeatAutoEnd;
  // The total number of repeat tracks minus 1.
  int32_t mRepeatEndDelta;
  // The end of the line name lists with repeat(auto-fill/fit) tracks accounted
  // for.
  uint32_t mTemplateLinesEnd;

  // The parent line map, or null if this map isn't for a subgrid.
  const LineNameMap* mParentLineNameMap;
  // The subgrid's range, or null if this map isn't for a subgrid.
  const LineRange* mRange;
  // True if the subgrid/parent axes progresses in the same direction.
  const bool mIsSameDirection;

  // True if there is a specified repeat(auto-fill/fit) track.
  bool mHasRepeatAuto;
};

/**
 * State for the tracks in one dimension.
 */
struct nsGridContainerFrame::Tracks {
  explicit Tracks(LogicalAxis aAxis)
      : mContentBoxSize(NS_UNCONSTRAINEDSIZE),
        mGridGap(NS_UNCONSTRAINEDSIZE),
        mStateUnion(TrackSize::StateBits(0)),
        mAxis(aAxis),
        mCanResolveLineRangeSize(false),
        mIsMasonry(false) {
    mBaselineSubtreeAlign[BaselineSharingGroup::First] = StyleAlignFlags::AUTO;
    mBaselineSubtreeAlign[BaselineSharingGroup::Last] = StyleAlignFlags::AUTO;
    mBaseline[BaselineSharingGroup::First] = NS_INTRINSIC_ISIZE_UNKNOWN;
    mBaseline[BaselineSharingGroup::Last] = NS_INTRINSIC_ISIZE_UNKNOWN;
  }

  void Initialize(const TrackSizingFunctions& aFunctions,
                  const NonNegativeLengthPercentageOrNormal& aGridGap,
                  uint32_t aNumTracks, nscoord aContentBoxSize);

  /**
   * Return the union of the state bits for the tracks in aRange.
   */
  TrackSize::StateBits StateBitsForRange(const LineRange& aRange) const;

  // Some data we collect for aligning baseline-aligned items.
  struct ItemBaselineData {
    uint32_t mBaselineTrack;
    nscoord mBaseline;
    nscoord mSize;
    GridItemInfo* mGridItem;
    static bool IsBaselineTrackLessThan(const ItemBaselineData& a,
                                        const ItemBaselineData& b) {
      return a.mBaselineTrack < b.mBaselineTrack;
    }
  };

  /**
   * Calculate baseline offsets for the given set of items.
   * Helper for InitialzeItemBaselines.
   */
  void CalculateItemBaselines(nsTArray<ItemBaselineData>& aBaselineItems,
                              BaselineSharingGroup aBaselineGroup);

  /**
   * Initialize grid item baseline state and offsets.
   */
  void InitializeItemBaselines(GridReflowInput& aState,
                               nsTArray<GridItemInfo>& aGridItems);

  /**
   * A masonry axis has four baseline alignment sets and each set can have
   * a first- and last-baseline alignment group, for a total of eight possible
   * baseline alignment groups, as follows:
   *   set 1: the first item in each `start` or `stretch` grid track
   *   set 2: the last item in each `start` grid track
   *   set 3: the last item in each `end` or `stretch` grid track
   *   set 4: the first item in each `end` grid track
   * (`start`/`end`/`stretch` refers to the relevant `align/justify-tracks`
   * value of the (grid-axis) start track for the item) Baseline-alignment for
   * set 1 and 2 always adjusts the item's padding or margin on the start side,
   * and set 3 and 4 on the end side, for both first- and last-baseline groups
   * in the set. (This is similar to regular grid which always adjusts
   * first-baseline groups on the start side and last-baseline groups on the
   * end-side.  The crux is that those groups are always aligned to the track's
   * start/end side respectively.)
   */
  struct BaselineAlignmentSet {
    bool MatchTrackAlignment(StyleAlignFlags aTrackAlignment) const {
      if (mTrackAlignmentSet == BaselineAlignmentSet::StartStretch) {
        return aTrackAlignment == StyleAlignFlags::START ||
               (aTrackAlignment == StyleAlignFlags::STRETCH &&
                mItemSet == BaselineAlignmentSet::FirstItems);
      }
      return aTrackAlignment == StyleAlignFlags::END ||
             (aTrackAlignment == StyleAlignFlags::STRETCH &&
              mItemSet == BaselineAlignmentSet::LastItems);
    }

    enum ItemSet { FirstItems, LastItems };
    ItemSet mItemSet = FirstItems;
    enum TrackAlignmentSet { StartStretch, EndStretch };
    TrackAlignmentSet mTrackAlignmentSet = StartStretch;
  };
  void InitializeItemBaselinesInMasonryAxis(
      GridReflowInput& aState, nsTArray<GridItemInfo>& aGridItems,
      BaselineAlignmentSet aSet, const nsSize& aContainerSize,
      nsTArray<nscoord>& aTrackSizes,
      nsTArray<ItemBaselineData>& aFirstBaselineItems,
      nsTArray<ItemBaselineData>& aLastBaselineItems);

  /**
   * Apply the additional alignment needed to align the baseline-aligned subtree
   * the item belongs to within its baseline track.
   */
  void AlignBaselineSubtree(const GridItemInfo& aGridItem) const;

  enum class TrackSizingPhase {
    IntrinsicMinimums,
    ContentBasedMinimums,
    MaxContentMinimums,
    IntrinsicMaximums,
    MaxContentMaximums,
  };

  // Some data we collect on each item for Step 2 of the Track Sizing Algorithm
  // in ResolveIntrinsicSize below.
  struct Step2ItemData final {
    uint32_t mSpan;
    TrackSize::StateBits mState;
    LineRange mLineRange;
    nscoord mMinSize;
    nscoord mMinContentContribution;
    nscoord mMaxContentContribution;
    nsIFrame* mFrame;
    static bool IsSpanLessThan(const Step2ItemData& a, const Step2ItemData& b) {
      return a.mSpan < b.mSpan;
    }

    template <TrackSizingPhase phase>
    nscoord SizeContributionForPhase() const {
      switch (phase) {
        case TrackSizingPhase::IntrinsicMinimums:
          return mMinSize;
        case TrackSizingPhase::ContentBasedMinimums:
        case TrackSizingPhase::IntrinsicMaximums:
          return mMinContentContribution;
        case TrackSizingPhase::MaxContentMinimums:
        case TrackSizingPhase::MaxContentMaximums:
          return mMaxContentContribution;
      }
      MOZ_MAKE_COMPILER_ASSUME_IS_UNREACHABLE("Unexpected phase");
    }
  };

  using FitContentClamper =
      std::function<bool(uint32_t aTrack, nscoord aMinSize, nscoord* aSize)>;

  // Helper method for ResolveIntrinsicSize.
  template <TrackSizingPhase phase>
  bool GrowSizeForSpanningItems(nsTArray<Step2ItemData>::iterator aIter,
                                const nsTArray<Step2ItemData>::iterator aEnd,
                                nsTArray<uint32_t>& aTracks,
                                nsTArray<TrackSize>& aPlan,
                                nsTArray<TrackSize>& aItemPlan,
                                TrackSize::StateBits aSelector,
                                const FitContentClamper& aClamper = nullptr,
                                bool aNeedInfinitelyGrowableFlag = false);
  /**
   * Resolve Intrinsic Track Sizes.
   * http://dev.w3.org/csswg/css-grid/#algo-content
   */
  void ResolveIntrinsicSize(GridReflowInput& aState,
                            nsTArray<GridItemInfo>& aGridItems,
                            const TrackSizingFunctions& aFunctions,
                            LineRange GridArea::*aRange,
                            nscoord aPercentageBasis,
                            SizingConstraint aConstraint);

  /**
   * Helper for ResolveIntrinsicSize.  It implements step 1 "size tracks to fit
   * non-spanning items" in the spec.  Return true if the track has a <flex>
   * max-sizing function, false otherwise.
   */
  bool ResolveIntrinsicSizeStep1(GridReflowInput& aState,
                                 const TrackSizingFunctions& aFunctions,
                                 nscoord aPercentageBasis,
                                 SizingConstraint aConstraint,
                                 const LineRange& aRange,
                                 const GridItemInfo& aGridItem);

  // Helper method that returns the track size to use in §11.5.1.2
  // https://drafts.csswg.org/css-grid/#extra-space
  template <TrackSizingPhase phase>
  static nscoord StartSizeInDistribution(const TrackSize& aSize) {
    switch (phase) {
      case TrackSizingPhase::IntrinsicMinimums:
      case TrackSizingPhase::ContentBasedMinimums:
      case TrackSizingPhase::MaxContentMinimums:
        return aSize.mBase;
      case TrackSizingPhase::IntrinsicMaximums:
      case TrackSizingPhase::MaxContentMaximums:
        if (aSize.mLimit == NS_UNCONSTRAINEDSIZE) {
          return aSize.mBase;
        }
        return aSize.mLimit;
    }
    MOZ_MAKE_COMPILER_ASSUME_IS_UNREACHABLE("Unexpected phase");
  }

  /**
   * Collect the tracks which are growable (matching aSelector) into
   * aGrowableTracks, and return the amount of space that can be used
   * to grow those tracks.  This method implements CSS Grid §11.5.1.2.
   * https://drafts.csswg.org/css-grid/#extra-space
   */
  template <TrackSizingPhase phase>
  nscoord CollectGrowable(nscoord aAvailableSpace, const LineRange& aRange,
                          TrackSize::StateBits aSelector,
                          nsTArray<uint32_t>& aGrowableTracks) const {
    MOZ_ASSERT(aAvailableSpace > 0, "why call me?");
    nscoord space = aAvailableSpace - mGridGap * (aRange.Extent() - 1);
    for (auto i : aRange.Range()) {
      const TrackSize& sz = mSizes[i];
      space -= StartSizeInDistribution<phase>(sz);
      if (space <= 0) {
        return 0;
      }
      if (sz.mState & aSelector) {
        aGrowableTracks.AppendElement(i);
      }
    }
    return aGrowableTracks.IsEmpty() ? 0 : space;
  }

  template <TrackSizingPhase phase>
  void InitializeItemPlan(nsTArray<TrackSize>& aItemPlan,
                          const nsTArray<uint32_t>& aTracks) const {
    for (uint32_t track : aTracks) {
      auto& plan = aItemPlan[track];
      const TrackSize& sz = mSizes[track];
      plan.mBase = StartSizeInDistribution<phase>(sz);
      bool unlimited = sz.mState & TrackSize::eInfinitelyGrowable;
      plan.mLimit = unlimited ? NS_UNCONSTRAINEDSIZE : sz.mLimit;
      plan.mState = sz.mState;
    }
  }

  template <TrackSizingPhase phase>
  void InitializePlan(nsTArray<TrackSize>& aPlan) const {
    for (size_t i = 0, len = aPlan.Length(); i < len; ++i) {
      auto& plan = aPlan[i];
      const auto& sz = mSizes[i];
      plan.mBase = StartSizeInDistribution<phase>(sz);
      MOZ_ASSERT(phase == TrackSizingPhase::MaxContentMaximums ||
                     !(sz.mState & TrackSize::eInfinitelyGrowable),
                 "forgot to reset the eInfinitelyGrowable bit?");
      plan.mState = sz.mState;
    }
  }

  template <TrackSizingPhase phase>
  void CopyPlanToSize(const nsTArray<TrackSize>& aPlan,
                      bool aNeedInfinitelyGrowableFlag = false) {
    for (size_t i = 0, len = mSizes.Length(); i < len; ++i) {
      const auto& plan = aPlan[i];
      MOZ_ASSERT(plan.mBase >= 0);
      auto& sz = mSizes[i];
      switch (phase) {
        case TrackSizingPhase::IntrinsicMinimums:
        case TrackSizingPhase::ContentBasedMinimums:
        case TrackSizingPhase::MaxContentMinimums:
          sz.mBase = plan.mBase;
          break;
        case TrackSizingPhase::IntrinsicMaximums:
          if (plan.mState & TrackSize::eModified) {
            if (sz.mLimit == NS_UNCONSTRAINEDSIZE &&
                aNeedInfinitelyGrowableFlag) {
              sz.mState |= TrackSize::eInfinitelyGrowable;
            }
            sz.mLimit = plan.mBase;
          }
          break;
        case TrackSizingPhase::MaxContentMaximums:
          if (plan.mState & TrackSize::eModified) {
            sz.mLimit = plan.mBase;
          }
          sz.mState &= ~TrackSize::eInfinitelyGrowable;
          break;
      }
    }
  }

  /**
   * Grow the planned size for tracks in aGrowableTracks up to their limit
   * and then freeze them (all aGrowableTracks must be unfrozen on entry).
   * Subtract the space added from aAvailableSpace and return that.
   */
  nscoord GrowTracksToLimit(nscoord aAvailableSpace, nsTArray<TrackSize>& aPlan,
                            const nsTArray<uint32_t>& aGrowableTracks,
                            const FitContentClamper& aFitContentClamper) const {
    MOZ_ASSERT(aAvailableSpace > 0 && aGrowableTracks.Length() > 0);
    nscoord space = aAvailableSpace;
    uint32_t numGrowable = aGrowableTracks.Length();
    while (true) {
      nscoord spacePerTrack = std::max<nscoord>(space / numGrowable, 1);
      for (uint32_t track : aGrowableTracks) {
        TrackSize& sz = aPlan[track];
        if (sz.IsFrozen()) {
          continue;
        }
        nscoord newBase = sz.mBase + spacePerTrack;
        nscoord limit = sz.mLimit;
        if (MOZ_UNLIKELY((sz.mState & TrackSize::eFitContent) &&
                         aFitContentClamper)) {
          // Clamp the limit to the fit-content() size, for §12.5.2 step 5/6.
          aFitContentClamper(track, sz.mBase, &limit);
        }
        if (newBase > limit) {
          nscoord consumed = limit - sz.mBase;
          if (consumed > 0) {
            space -= consumed;
            sz.mBase = limit;
          }
          sz.mState |= TrackSize::eFrozen;
          if (--numGrowable == 0) {
            return space;
          }
        } else {
          sz.mBase = newBase;
          space -= spacePerTrack;
        }
        MOZ_ASSERT(space >= 0);
        if (space == 0) {
          return 0;
        }
      }
    }
    MOZ_ASSERT_UNREACHABLE("we don't exit the loop above except by return");
    return 0;
  }

  /**
   * Helper for GrowSelectedTracksUnlimited.  For the set of tracks (S) that
   * match aMinSizingSelector: if a track in S doesn't match aMaxSizingSelector
   * then mark it with aSkipFlag.  If all tracks in S were marked then unmark
   * them.  Return aNumGrowable minus the number of tracks marked.  It is
   * assumed that aPlan have no aSkipFlag set for tracks in aGrowableTracks
   * on entry to this method.
   */
  static uint32_t MarkExcludedTracks(nsTArray<TrackSize>& aPlan,
                                     uint32_t aNumGrowable,
                                     const nsTArray<uint32_t>& aGrowableTracks,
                                     TrackSize::StateBits aMinSizingSelector,
                                     TrackSize::StateBits aMaxSizingSelector,
                                     TrackSize::StateBits aSkipFlag) {
    bool foundOneSelected = false;
    bool foundOneGrowable = false;
    uint32_t numGrowable = aNumGrowable;
    for (uint32_t track : aGrowableTracks) {
      TrackSize& sz = aPlan[track];
      const auto state = sz.mState;
      if (state & aMinSizingSelector) {
        foundOneSelected = true;
        if (state & aMaxSizingSelector) {
          foundOneGrowable = true;
          continue;
        }
        sz.mState |= aSkipFlag;
        MOZ_ASSERT(numGrowable != 0);
        --numGrowable;
      }
    }
    // 12.5 "if there are no such tracks, then all affected tracks"
    if (foundOneSelected && !foundOneGrowable) {
      for (uint32_t track : aGrowableTracks) {
        aPlan[track].mState &= ~aSkipFlag;
      }
      numGrowable = aNumGrowable;
    }
    return numGrowable;
  }

  /**
   * Mark all tracks in aGrowableTracks with an eSkipGrowUnlimited bit if
   * they *shouldn't* grow unlimited in §11.5.1.2.3 "Distribute space beyond
   * growth limits" https://drafts.csswg.org/css-grid/#extra-space
   * Return the number of tracks that are still growable.
   */
  template <TrackSizingPhase phase>
  static uint32_t MarkExcludedTracks(nsTArray<TrackSize>& aPlan,
                                     const nsTArray<uint32_t>& aGrowableTracks,
                                     TrackSize::StateBits aSelector) {
    uint32_t numGrowable = aGrowableTracks.Length();
    if (phase == TrackSizingPhase::IntrinsicMaximums ||
        phase == TrackSizingPhase::MaxContentMaximums) {
      // "when handling any intrinsic growth limit: all affected tracks"
      return numGrowable;
    }
    MOZ_ASSERT(aSelector == (aSelector & TrackSize::eIntrinsicMinSizing) &&
                   (aSelector & TrackSize::eMaxContentMinSizing),
               "Should only get here for track sizing steps 2.1 to 2.3");
    // Note that eMaxContentMinSizing is always included. We do those first:
    numGrowable = MarkExcludedTracks(
        aPlan, numGrowable, aGrowableTracks, TrackSize::eMaxContentMinSizing,
        TrackSize::eMaxContentMaxSizing, TrackSize::eSkipGrowUnlimited1);
    // Now mark min-content/auto min-sizing tracks if requested.
    auto minOrAutoSelector = aSelector & ~TrackSize::eMaxContentMinSizing;
    if (minOrAutoSelector) {
      numGrowable = MarkExcludedTracks(
          aPlan, numGrowable, aGrowableTracks, minOrAutoSelector,
          TrackSize::eIntrinsicMaxSizing, TrackSize::eSkipGrowUnlimited2);
    }
    return numGrowable;
  }

  /**
   * Increase the planned size for tracks in aGrowableTracks that aren't
   * marked with a eSkipGrowUnlimited flag beyond their limit.
   * This implements the "Distribute space beyond growth limits" step in
   * https://drafts.csswg.org/css-grid/#distribute-extra-space
   */
  void GrowSelectedTracksUnlimited(
      nscoord aAvailableSpace, nsTArray<TrackSize>& aPlan,
      const nsTArray<uint32_t>& aGrowableTracks, uint32_t aNumGrowable,
      const FitContentClamper& aFitContentClamper) const {
    MOZ_ASSERT(aAvailableSpace > 0 && aGrowableTracks.Length() > 0 &&
               aNumGrowable <= aGrowableTracks.Length());
    nscoord space = aAvailableSpace;
    DebugOnly<bool> didClamp = false;
    while (aNumGrowable) {
      nscoord spacePerTrack = std::max<nscoord>(space / aNumGrowable, 1);
      for (uint32_t track : aGrowableTracks) {
        TrackSize& sz = aPlan[track];
        if (sz.mState & TrackSize::eSkipGrowUnlimited) {
          continue;  // an excluded track
        }
        nscoord delta = spacePerTrack;
        nscoord newBase = sz.mBase + delta;
        if (MOZ_UNLIKELY((sz.mState & TrackSize::eFitContent) &&
                         aFitContentClamper)) {
          // Clamp newBase to the fit-content() size, for §12.5.2 step 5/6.
          if (aFitContentClamper(track, sz.mBase, &newBase)) {
            didClamp = true;
            delta = newBase - sz.mBase;
            MOZ_ASSERT(delta >= 0, "track size shouldn't shrink");
            sz.mState |= TrackSize::eSkipGrowUnlimited1;
            --aNumGrowable;
          }
        }
        sz.mBase = newBase;
        space -= delta;
        MOZ_ASSERT(space >= 0);
        if (space == 0) {
          return;
        }
      }
    }
    MOZ_ASSERT(didClamp,
               "we don't exit the loop above except by return, "
               "unless we clamped some track's size");
  }

  /**
   * Distribute aAvailableSpace to the planned base size for aGrowableTracks
   * up to their limits, then distribute the remaining space beyond the limits.
   */
  template <TrackSizingPhase phase>
  void DistributeToTrackSizes(nscoord aAvailableSpace,
                              nsTArray<TrackSize>& aPlan,
                              nsTArray<TrackSize>& aItemPlan,
                              nsTArray<uint32_t>& aGrowableTracks,
                              TrackSize::StateBits aSelector,
                              const FitContentClamper& aFitContentClamper) {
    InitializeItemPlan<phase>(aItemPlan, aGrowableTracks);
    nscoord space = GrowTracksToLimit(aAvailableSpace, aItemPlan,
                                      aGrowableTracks, aFitContentClamper);
    if (space > 0) {
      uint32_t numGrowable =
          MarkExcludedTracks<phase>(aItemPlan, aGrowableTracks, aSelector);
      GrowSelectedTracksUnlimited(space, aItemPlan, aGrowableTracks,
                                  numGrowable, aFitContentClamper);
    }
    for (uint32_t track : aGrowableTracks) {
      nscoord& plannedSize = aPlan[track].mBase;
      nscoord itemIncurredSize = aItemPlan[track].mBase;
      if (plannedSize < itemIncurredSize) {
        plannedSize = itemIncurredSize;
      }
    }
  }

  /**
   * Distribute aAvailableSize to the tracks.  This implements 12.6 at:
   * http://dev.w3.org/csswg/css-grid/#algo-grow-tracks
   */
  void DistributeFreeSpace(nscoord aAvailableSize) {
    const uint32_t numTracks = mSizes.Length();
    if (MOZ_UNLIKELY(numTracks == 0 || aAvailableSize <= 0)) {
      return;
    }
    if (aAvailableSize == NS_UNCONSTRAINEDSIZE) {
      for (TrackSize& sz : mSizes) {
        sz.mBase = sz.mLimit;
      }
    } else {
      // Compute free space and count growable tracks.
      nscoord space = aAvailableSize;
      uint32_t numGrowable = numTracks;
      for (const TrackSize& sz : mSizes) {
        space -= sz.mBase;
        MOZ_ASSERT(sz.mBase <= sz.mLimit);
        if (sz.mBase == sz.mLimit) {
          --numGrowable;
        }
      }
      // Distribute the free space evenly to the growable tracks. If not exactly
      // divisable the remainder is added to the leading tracks.
      while (space > 0 && numGrowable) {
        nscoord spacePerTrack = std::max<nscoord>(space / numGrowable, 1);
        for (uint32_t i = 0; i < numTracks && space > 0; ++i) {
          TrackSize& sz = mSizes[i];
          if (sz.mBase == sz.mLimit) {
            continue;
          }
          nscoord newBase = sz.mBase + spacePerTrack;
          if (newBase >= sz.mLimit) {
            space -= sz.mLimit - sz.mBase;
            sz.mBase = sz.mLimit;
            --numGrowable;
          } else {
            space -= spacePerTrack;
            sz.mBase = newBase;
          }
        }
      }
    }
  }

  /**
   * Implements "12.7.1. Find the Size of an 'fr'".
   * http://dev.w3.org/csswg/css-grid/#algo-find-fr-size
   * (The returned value is a 'nscoord' divided by a factor - a floating type
   * is used to avoid intermediary rounding errors.)
   */
  float FindFrUnitSize(const LineRange& aRange,
                       const nsTArray<uint32_t>& aFlexTracks,
                       const TrackSizingFunctions& aFunctions,
                       nscoord aSpaceToFill) const;

  /**
   * Implements the "find the used flex fraction" part of StretchFlexibleTracks.
   * (The returned value is a 'nscoord' divided by a factor - a floating type
   * is used to avoid intermediary rounding errors.)
   */
  float FindUsedFlexFraction(GridReflowInput& aState,
                             nsTArray<GridItemInfo>& aGridItems,
                             const nsTArray<uint32_t>& aFlexTracks,
                             const TrackSizingFunctions& aFunctions,
                             nscoord aAvailableSize) const;

  /**
   * Implements "12.7. Stretch Flexible Tracks"
   * http://dev.w3.org/csswg/css-grid/#algo-flex-tracks
   */
  void StretchFlexibleTracks(GridReflowInput& aState,
                             nsTArray<GridItemInfo>& aGridItems,
                             const TrackSizingFunctions& aFunctions,
                             nscoord aAvailableSize);

  /**
   * Implements "12.3. Track Sizing Algorithm"
   * http://dev.w3.org/csswg/css-grid/#algo-track-sizing
   */
  void CalculateSizes(GridReflowInput& aState,
                      nsTArray<GridItemInfo>& aGridItems,
                      const TrackSizingFunctions& aFunctions,
                      nscoord aContentBoxSize, LineRange GridArea::*aRange,
                      SizingConstraint aConstraint);

  /**
   * Apply 'align/justify-content', whichever is relevant for this axis.
   * https://drafts.csswg.org/css-align-3/#propdef-align-content
   */
  void AlignJustifyContent(const nsStylePosition* aStyle,
                           StyleContentDistribution aAligmentStyleValue,
                           WritingMode aWM, nscoord aContentBoxSize,
                           bool aIsSubgridded);

  nscoord GridLineEdge(uint32_t aLine, GridLineSide aSide) const {
    if (MOZ_UNLIKELY(mSizes.IsEmpty())) {
      // https://drafts.csswg.org/css-grid/#grid-definition
      // "... the explicit grid still contains one grid line in each axis."
      MOZ_ASSERT(aLine == 0, "We should only resolve line 1 in an empty grid");
      return nscoord(0);
    }
    MOZ_ASSERT(aLine <= mSizes.Length(), "mSizes is too small");
    if (aSide == GridLineSide::BeforeGridGap) {
      if (aLine == 0) {
        return nscoord(0);
      }
      const TrackSize& sz = mSizes[aLine - 1];
      return sz.mPosition + sz.mBase;
    }
    if (aLine == mSizes.Length()) {
      return mContentBoxSize;
    }
    return mSizes[aLine].mPosition;
  }

  nscoord SumOfGridGaps() const {
    auto len = mSizes.Length();
    return MOZ_LIKELY(len > 1) ? (len - 1) * mGridGap : 0;
  }

  /**
   * Break before aRow, i.e. set the eBreakBefore flag on aRow and set the grid
   * gap before aRow to zero (and shift all rows after it by the removed gap).
   */
  void BreakBeforeRow(uint32_t aRow) {
    MOZ_ASSERT(mAxis == eLogicalAxisBlock,
               "Should only be fragmenting in the block axis (between rows)");
    nscoord prevRowEndPos = 0;
    if (aRow != 0) {
      auto& prevSz = mSizes[aRow - 1];
      prevRowEndPos = prevSz.mPosition + prevSz.mBase;
    }
    auto& sz = mSizes[aRow];
    const nscoord gap = sz.mPosition - prevRowEndPos;
    sz.mState |= TrackSize::eBreakBefore;
    if (gap != 0) {
      for (uint32_t i = aRow, len = mSizes.Length(); i < len; ++i) {
        mSizes[i].mPosition -= gap;
      }
    }
  }

  /**
   * Set the size of aRow to aSize and adjust the position of all rows after it.
   */
  void ResizeRow(uint32_t aRow, nscoord aNewSize) {
    MOZ_ASSERT(mAxis == eLogicalAxisBlock,
               "Should only be fragmenting in the block axis (between rows)");
    MOZ_ASSERT(aNewSize >= 0);
    auto& sz = mSizes[aRow];
    nscoord delta = aNewSize - sz.mBase;
    NS_WARNING_ASSERTION(delta != nscoord(0), "Useless call to ResizeRow");
    sz.mBase = aNewSize;
    const uint32_t numRows = mSizes.Length();
    for (uint32_t r = aRow + 1; r < numRows; ++r) {
      mSizes[r].mPosition += delta;
    }
  }

  nscoord ResolveSize(const LineRange& aRange) const {
    MOZ_ASSERT(mCanResolveLineRangeSize);
    MOZ_ASSERT(aRange.Extent() > 0, "grid items cover at least one track");
    nscoord pos, size;
    aRange.ToPositionAndLength(mSizes, &pos, &size);
    return size;
  }

#ifdef DEBUG
  void Dump() const;
#endif

  CopyableAutoTArray<TrackSize, 32> mSizes;
  nscoord mContentBoxSize;
  nscoord mGridGap;
  // The first(last)-baseline for the first(last) track in this axis.
  PerBaseline<nscoord> mBaseline;
  // The union of the track min/max-sizing state bits in this axis.
  TrackSize::StateBits mStateUnion;
  LogicalAxis mAxis;
  // Used for aligning a baseline-aligned subtree of items.  The only possible
  // values are StyleAlignFlags::{START,END,CENTER,AUTO}.  AUTO means there are
  // no baseline-aligned items in any track in that axis.
  // There is one alignment value for each BaselineSharingGroup.
  PerBaseline<StyleAlignFlags> mBaselineSubtreeAlign;
  // True if track positions and sizes are final in this axis.
  bool mCanResolveLineRangeSize;
  // True if this axis has masonry layout.
  bool mIsMasonry;
};

#ifdef DEBUG
void nsGridContainerFrame::Tracks::Dump() const {
  printf("%zu %s %s ", mSizes.Length(), mIsMasonry ? "masonry" : "grid",
         mAxis == eLogicalAxisBlock ? "rows" : "columns");
  TrackSize::DumpStateBits(mStateUnion);
  printf("\n");
  for (uint32_t i = 0, len = mSizes.Length(); i < len; ++i) {
    printf("  %d: ", i);
    mSizes[i].Dump();
    printf("\n");
  }
  double px = AppUnitsPerCSSPixel();
  printf("Baselines: %.2fpx %2fpx\n",
         mBaseline[BaselineSharingGroup::First] / px,
         mBaseline[BaselineSharingGroup::Last] / px);
  printf("Gap: %.2fpx\n", mGridGap / px);
  printf("ContentBoxSize: %.2fpx\n", mContentBoxSize / px);
}
#endif

/**
 * Grid data shared by all continuations, owned by the first-in-flow.
 * The data is initialized from the first-in-flow's GridReflowInput at
 * the end of its reflow.  Fragmentation will modify mRows.mSizes -
 * the mPosition to remove the row gap at the break boundary, the mState
 * by setting the eBreakBefore flag, and mBase is modified when we decide
 * to grow a row.  mOriginalRowData is setup by the first-in-flow and
 * not modified after that.  It's used for undoing the changes to mRows.
 * mCols, mGridItems, mAbsPosItems are used for initializing the grid
 * reflow input for continuations, see GridReflowInput::Initialize below.
 */
struct nsGridContainerFrame::SharedGridData {
  SharedGridData()
      : mCols(eLogicalAxisInline),
        mRows(eLogicalAxisBlock),
        mGenerateComputedGridInfo(false) {}
  Tracks mCols;
  Tracks mRows;
  struct RowData {
    nscoord mBase;  // the original track size
    nscoord mGap;   // the original gap before a track
  };
  nsTArray<RowData> mOriginalRowData;
  nsTArray<GridItemInfo> mGridItems;
  nsTArray<GridItemInfo> mAbsPosItems;
  bool mGenerateComputedGridInfo;

  /**
   * Only set on the first-in-flow.  Continuations will Initialize() their
   * GridReflowInput from it.
   */
  NS_DECLARE_FRAME_PROPERTY_DELETABLE(Prop, SharedGridData)
};

struct MOZ_STACK_CLASS nsGridContainerFrame::GridReflowInput {
  GridReflowInput(nsGridContainerFrame* aFrame, const ReflowInput& aRI)
      : GridReflowInput(aFrame, *aRI.mRenderingContext, &aRI,
                        aRI.mStylePosition, aRI.GetWritingMode()) {}
  GridReflowInput(nsGridContainerFrame* aFrame, gfxContext& aRC)
      : GridReflowInput(aFrame, aRC, nullptr, aFrame->StylePosition(),
                        aFrame->GetWritingMode()) {}

  /**
   * Initialize our track sizes and grid item info using the shared
   * state from aGridContainerFrame first-in-flow.
   */
  void InitializeForContinuation(nsGridContainerFrame* aGridContainerFrame,
                                 nscoord aConsumedBSize) {
    MOZ_ASSERT(aGridContainerFrame->GetPrevInFlow(),
               "don't call this on the first-in-flow");
    MOZ_ASSERT(mGridItems.IsEmpty() && mAbsPosItems.IsEmpty(),
               "shouldn't have any item data yet");

    // Get the SharedGridData from the first-in-flow. Also calculate the number
    // of fragments before this so that we can figure out our start row below.
    uint32_t fragment = 0;
    nsIFrame* firstInFlow = aGridContainerFrame;
    for (auto pif = aGridContainerFrame->GetPrevInFlow(); pif;
         pif = pif->GetPrevInFlow()) {
      ++fragment;
      firstInFlow = pif;
    }
    mSharedGridData = firstInFlow->GetProperty(SharedGridData::Prop());
    MOZ_ASSERT(mSharedGridData, "first-in-flow must have SharedGridData");

    // Find the start row for this fragment and undo breaks after that row
    // since the breaks might be different from the last reflow.
    auto& rowSizes = mSharedGridData->mRows.mSizes;
    const uint32_t numRows = rowSizes.Length();
    mStartRow = numRows;
    for (uint32_t row = 0, breakCount = 0; row < numRows; ++row) {
      if (rowSizes[row].mState & TrackSize::eBreakBefore) {
        if (fragment == ++breakCount) {
          mStartRow = row;
          mFragBStart = rowSizes[row].mPosition;
          // Restore the original size for |row| and grid gaps / state after it.
          const auto& origRowData = mSharedGridData->mOriginalRowData;
          rowSizes[row].mBase = origRowData[row].mBase;
          nscoord prevEndPos = rowSizes[row].mPosition + rowSizes[row].mBase;
          while (++row < numRows) {
            auto& sz = rowSizes[row];
            const auto& orig = origRowData[row];
            sz.mPosition = prevEndPos + orig.mGap;
            sz.mBase = orig.mBase;
            sz.mState &= ~TrackSize::eBreakBefore;
            prevEndPos = sz.mPosition + sz.mBase;
          }
          break;
        }
      }
    }
    if (mStartRow == numRows ||
        aGridContainerFrame->IsMasonry(eLogicalAxisBlock)) {
      // All of the grid's rows fit inside of previous grid-container fragments,
      // or it's a masonry axis.
      mFragBStart = aConsumedBSize;
    }

    // Copy the shared track state.
    // XXX consider temporarily swapping the array elements instead and swapping
    // XXX them back after we're done reflowing, for better performance.
    // XXX (bug 1252002)
    mCols = mSharedGridData->mCols;
    mRows = mSharedGridData->mRows;

    if (firstInFlow->GetProperty(UsedTrackSizes::Prop())) {
      auto* prop = aGridContainerFrame->GetProperty(UsedTrackSizes::Prop());
      if (!prop) {
        prop = new UsedTrackSizes();
        aGridContainerFrame->SetProperty(UsedTrackSizes::Prop(), prop);
      }
      prop->mCanResolveLineRangeSize = {true, true};
      prop->mSizes[eLogicalAxisInline].Assign(mCols.mSizes);
      prop->mSizes[eLogicalAxisBlock].Assign(mRows.mSizes);
    }

    // Copy item data from each child's first-in-flow data in mSharedGridData.
    // XXX NOTE: This is O(n^2) in the number of items. (bug 1252186)
    mIter.Reset();
    for (; !mIter.AtEnd(); mIter.Next()) {
      nsIFrame* child = *mIter;
      nsIFrame* childFirstInFlow = child->FirstInFlow();
      DebugOnly<size_t> len = mGridItems.Length();
      for (auto& itemInfo : mSharedGridData->mGridItems) {
        if (itemInfo.mFrame == childFirstInFlow) {
          auto item =
              mGridItems.AppendElement(GridItemInfo(child, itemInfo.mArea));
          // Copy the item's baseline data so that the item's last fragment can
          // do 'last baseline' alignment if necessary.
          item->mState[0] |= itemInfo.mState[0] & ItemState::eAllBaselineBits;
          item->mState[1] |= itemInfo.mState[1] & ItemState::eAllBaselineBits;
          item->mBaselineOffset[0] = itemInfo.mBaselineOffset[0];
          item->mBaselineOffset[1] = itemInfo.mBaselineOffset[1];
          item->mState[0] |= itemInfo.mState[0] & ItemState::eAutoPlacement;
          item->mState[1] |= itemInfo.mState[1] & ItemState::eAutoPlacement;
          break;
        }
      }
      MOZ_ASSERT(mGridItems.Length() == len + 1, "can't find GridItemInfo");
    }

    // XXX NOTE: This is O(n^2) in the number of abs.pos. items. (bug 1252186)
    nsFrameList absPosChildren(aGridContainerFrame->GetChildList(
        aGridContainerFrame->GetAbsoluteListID()));
    for (auto f : absPosChildren) {
      nsIFrame* childFirstInFlow = f->FirstInFlow();
      DebugOnly<size_t> len = mAbsPosItems.Length();
      for (auto& itemInfo : mSharedGridData->mAbsPosItems) {
        if (itemInfo.mFrame == childFirstInFlow) {
          mAbsPosItems.AppendElement(GridItemInfo(f, itemInfo.mArea));
          break;
        }
      }
      MOZ_ASSERT(mAbsPosItems.Length() == len + 1, "can't find GridItemInfo");
    }

    // Copy in the computed grid info state bit
    if (mSharedGridData->mGenerateComputedGridInfo) {
      aGridContainerFrame->SetShouldGenerateComputedInfo(true);
    }
  }

  /**
   * Calculate our track sizes in the given axis.
   */
  void CalculateTrackSizesForAxis(LogicalAxis aAxis, const Grid& aGrid,
                                  nscoord aCBSize,
                                  SizingConstraint aConstraint);

  /**
   * Calculate our track sizes.
   */
  void CalculateTrackSizes(const Grid& aGrid, const LogicalSize& aContentBox,
                           SizingConstraint aConstraint);

  /**
   * Return the percentage basis for a grid item in its writing-mode.
   * If aAxis is eLogicalAxisInline then we return NS_UNCONSTRAINEDSIZE in
   * both axes since we know all track sizes are indefinite at this point
   * (we calculate column sizes before row sizes).  Otherwise, assert that
   * column sizes are known and calculate the size for aGridItem.mArea.mCols
   * and use NS_UNCONSTRAINEDSIZE in the other axis.
   * @param aAxis the axis we're currently calculating track sizes for
   */
  LogicalSize PercentageBasisFor(LogicalAxis aAxis,
                                 const GridItemInfo& aGridItem) const;

  /**
   * Return the containing block for a grid item occupying aArea.
   */
  LogicalRect ContainingBlockFor(const GridArea& aArea) const;

  /**
   * Return the containing block for an abs.pos. grid item occupying aArea.
   * Any 'auto' lines in the grid area will be aligned with grid container
   * containing block on that side.
   * @param aGridOrigin the origin of the grid
   * @param aGridCB the grid container containing block (its padding area)
   */
  LogicalRect ContainingBlockForAbsPos(const GridArea& aArea,
                                       const LogicalPoint& aGridOrigin,
                                       const LogicalRect& aGridCB) const;

  /**
   * Apply `align/justify-content` alignment in our masonry axis.
   * This aligns the "masonry box" within our content box size.
   */
  void AlignJustifyContentInMasonryAxis(nscoord aMasonryBoxSize,
                                        nscoord aContentBoxSize);
  /**
   * Apply `align/justify-tracks` alignment in our masonry axis.
   */
  void AlignJustifyTracksInMasonryAxis(const LogicalSize& aContentSize,
                                       const nsSize& aContainerSize);

  // Helper for CollectSubgridItemsForAxis.
  static void CollectSubgridForAxis(LogicalAxis aAxis, WritingMode aContainerWM,
                                    const LineRange& aRangeInAxis,
                                    const LineRange& aRangeInOppositeAxis,
                                    const GridItemInfo& aItem,
                                    const nsTArray<GridItemInfo>& aItems,
                                    nsTArray<GridItemInfo>& aResult) {
    const auto oppositeAxis = GetOrthogonalAxis(aAxis);
    bool itemIsSubgridInOppositeAxis = aItem.IsSubgrid(oppositeAxis);
    auto subgridWM = aItem.mFrame->GetWritingMode();
    bool isOrthogonal = subgridWM.IsOrthogonalTo(aContainerWM);
    bool isSameDirInAxis =
        subgridWM.ParallelAxisStartsOnSameSide(aAxis, aContainerWM);
    bool isSameDirInOppositeAxis =
        subgridWM.ParallelAxisStartsOnSameSide(oppositeAxis, aContainerWM);
    if (isOrthogonal) {
      // We'll Transpose the area below so these needs to be transposed as well.
      std::swap(isSameDirInAxis, isSameDirInOppositeAxis);
    }
    uint32_t offsetInAxis = aRangeInAxis.mStart;
    uint32_t gridEndInAxis = aRangeInAxis.Extent();
    uint32_t offsetInOppositeAxis = aRangeInOppositeAxis.mStart;
    uint32_t gridEndInOppositeAxis = aRangeInOppositeAxis.Extent();
    for (const auto& subgridItem : aItems) {
      auto newItem = aResult.AppendElement(
          isOrthogonal ? subgridItem.Transpose() : subgridItem);
      if (MOZ_UNLIKELY(!isSameDirInAxis)) {
        newItem->ReverseDirection(aAxis, gridEndInAxis);
      }
      newItem->mArea.LineRangeForAxis(aAxis).Translate(offsetInAxis);
      if (itemIsSubgridInOppositeAxis) {
        if (MOZ_UNLIKELY(!isSameDirInOppositeAxis)) {
          newItem->ReverseDirection(oppositeAxis, gridEndInOppositeAxis);
        }
        LineRange& range = newItem->mArea.LineRangeForAxis(oppositeAxis);
        range.Translate(offsetInOppositeAxis);
      }
      if (newItem->IsSubgrid(aAxis)) {
        auto* subgrid =
            subgridItem.SubgridFrame()->GetProperty(Subgrid::Prop());
        CollectSubgridForAxis(aAxis, aContainerWM,
                              newItem->mArea.LineRangeForAxis(aAxis),
                              newItem->mArea.LineRangeForAxis(oppositeAxis),
                              *newItem, subgrid->mGridItems, aResult);
      }
    }
  }

  // Copy all descendant items from all our subgrid children that are subgridded
  // in aAxis recursively into aResult.  All item grid area's and state are
  // translated to our coordinates.
  void CollectSubgridItemsForAxis(LogicalAxis aAxis,
                                  nsTArray<GridItemInfo>& aResult) const {
    for (const auto& item : mGridItems) {
      if (item.IsSubgrid(aAxis)) {
        const auto oppositeAxis = GetOrthogonalAxis(aAxis);
        auto* subgrid = item.SubgridFrame()->GetProperty(Subgrid::Prop());
        CollectSubgridForAxis(aAxis, mWM, item.mArea.LineRangeForAxis(aAxis),
                              item.mArea.LineRangeForAxis(oppositeAxis), item,
                              subgrid->mGridItems, aResult);
      }
    }
  }

  Tracks& TracksFor(LogicalAxis aAxis) {
    return aAxis == eLogicalAxisBlock ? mRows : mCols;
  }
  const Tracks& TracksFor(LogicalAxis aAxis) const {
    return aAxis == eLogicalAxisBlock ? mRows : mCols;
  }

  CSSOrderAwareFrameIterator mIter;
  const nsStylePosition* const mGridStyle;
  Tracks mCols;
  Tracks mRows;
  TrackSizingFunctions mColFunctions;
  TrackSizingFunctions mRowFunctions;
  /**
   * Info about each (normal flow) grid item.
   */
  nsTArray<GridItemInfo> mGridItems;
  /**
   * Info about each grid-aligned abs.pos. child.
   */
  nsTArray<GridItemInfo> mAbsPosItems;

  /**
   * @note mReflowInput may be null when using the 2nd ctor above. In this case
   * we'll construct a dummy parent reflow input if we need it to calculate
   * min/max-content contributions when sizing tracks.
   */
  const ReflowInput* const mReflowInput;
  gfxContext& mRenderingContext;
  nsGridContainerFrame* const mFrame;
  SharedGridData* mSharedGridData;  // [weak] owned by mFrame's first-in-flow.
  /** Computed border+padding with mSkipSides applied. */
  LogicalMargin mBorderPadding;
  /**
   * BStart of this fragment in "grid space" (i.e. the concatenation of content
   * areas of all fragments).  Equal to mRows.mSizes[mStartRow].mPosition,
   * or, if this fragment starts after the last row, the ConsumedBSize().
   */
  nscoord mFragBStart;
  /** The start row for this fragment. */
  uint32_t mStartRow;
  /**
   * The start row for the next fragment, if any.  If mNextFragmentStartRow ==
   * mStartRow then there are no rows in this fragment.
   */
  uint32_t mNextFragmentStartRow;
  /** Our tentative ApplySkipSides bits. */
  LogicalSides mSkipSides;
  const WritingMode mWM;
  /** Initialized lazily, when we find the fragmentainer. */
  bool mInFragmentainer;

 private:
  GridReflowInput(nsGridContainerFrame* aFrame, gfxContext& aRenderingContext,
                  const ReflowInput* aReflowInput,
                  const nsStylePosition* aGridStyle, const WritingMode& aWM)
      : mIter(aFrame, kPrincipalList),
        mGridStyle(aGridStyle),
        mCols(eLogicalAxisInline),
        mRows(eLogicalAxisBlock),
        mColFunctions(mGridStyle->mGridTemplateColumns,
                      mGridStyle->mGridAutoColumns,
                      aFrame->IsSubgrid(eLogicalAxisInline)),
        mRowFunctions(mGridStyle->mGridTemplateRows, mGridStyle->mGridAutoRows,
                      aFrame->IsSubgrid(eLogicalAxisBlock)),
        mReflowInput(aReflowInput),
        mRenderingContext(aRenderingContext),
        mFrame(aFrame),
        mSharedGridData(nullptr),
        mBorderPadding(aWM),
        mFragBStart(0),
        mStartRow(0),
        mNextFragmentStartRow(0),
        mSkipSides(aFrame->GetWritingMode()),
        mWM(aWM),
        mInFragmentainer(false) {
    MOZ_ASSERT(!aReflowInput || aReflowInput->mFrame == mFrame);
    if (aReflowInput) {
      mBorderPadding = aReflowInput->ComputedLogicalBorderPadding(mWM);
      mSkipSides = aFrame->PreReflowBlockLevelLogicalSkipSides();
      mBorderPadding.ApplySkipSides(mSkipSides);
    }
    mCols.mIsMasonry = aFrame->IsMasonry(eLogicalAxisInline);
    mRows.mIsMasonry = aFrame->IsMasonry(eLogicalAxisBlock);
    MOZ_ASSERT(!(mCols.mIsMasonry && mRows.mIsMasonry),
               "can't have masonry layout in both axes");
  }
};

using GridReflowInput = nsGridContainerFrame::GridReflowInput;

/**
 * The Grid implements grid item placement and the state of the grid -
 * the size of the explicit/implicit grid, which cells are occupied etc.
 */
struct MOZ_STACK_CLASS nsGridContainerFrame::Grid {
  explicit Grid(const Grid* aParentGrid = nullptr) : mParentGrid(aParentGrid) {}

  /**
   * Place all child frames into the grid and expand the (implicit) grid as
   * needed.  The allocated GridAreas are stored in the GridAreaProperty
   * frame property on the child frame.
   * @param aRepeatSizing the container's [min-|max-]*size - used to determine
   *   the number of repeat(auto-fill/fit) tracks.
   */
  void PlaceGridItems(GridReflowInput& aState,
                      const RepeatTrackSizingInput& aRepeatSizing);

  void SubgridPlaceGridItems(GridReflowInput& aParentState, Grid* aParentGrid,
                             const GridItemInfo& aGridItem);

  /**
   * As above but for an abs.pos. child.  Any 'auto' lines will be represented
   * by kAutoLine in the LineRange result.
   * @param aGridStart the first line in the final, but untranslated grid
   * @param aGridEnd the last line in the final, but untranslated grid
   */
  LineRange ResolveAbsPosLineRange(const StyleGridLine& aStart,
                                   const StyleGridLine& aEnd,
                                   const LineNameMap& aNameMap,
                                   LogicalAxis aAxis, uint32_t aExplicitGridEnd,
                                   int32_t aGridStart, int32_t aGridEnd,
                                   const nsStylePosition* aStyle);

  /**
   * Return a GridArea for abs.pos. item with non-auto lines placed at
   * a definite line (1-based) with placement errors resolved.  One or both
   * positions may still be 'auto'.
   * @param aChild the abs.pos. grid item to place
   * @param aStyle the StylePosition() for the grid container
   */
  GridArea PlaceAbsPos(nsIFrame* aChild, const LineNameMap& aColLineNameMap,
                       const LineNameMap& aRowLineNameMap,
                       const nsStylePosition* aStyle);

  /**
   * Find the first column in row aLockedRow starting at aStartCol where aArea
   * could be placed without overlapping other items.  The returned column may
   * cause aArea to overflow the current implicit grid bounds if placed there.
   */
  uint32_t FindAutoCol(uint32_t aStartCol, uint32_t aLockedRow,
                       const GridArea* aArea) const;

  /**
   * Place aArea in the first column (in row aArea->mRows.mStart) starting at
   * aStartCol without overlapping other items.  The resulting aArea may
   * overflow the current implicit grid bounds.
   * @param aClampMaxColLine the maximum allowed column line number (zero-based)
   * Pre-condition: aArea->mRows.IsDefinite() is true.
   * Post-condition: aArea->IsDefinite() is true.
   */
  void PlaceAutoCol(uint32_t aStartCol, GridArea* aArea,
                    uint32_t aClampMaxColLine) const;

  /**
   * Find the first row in column aLockedCol starting at aStartRow where aArea
   * could be placed without overlapping other items.  The returned row may
   * cause aArea to overflow the current implicit grid bounds if placed there.
   */
  uint32_t FindAutoRow(uint32_t aLockedCol, uint32_t aStartRow,
                       const GridArea* aArea) const;

  /**
   * Place aArea in the first row (in column aArea->mCols.mStart) starting at
   * aStartRow without overlapping other items. The resulting aArea may
   * overflow the current implicit grid bounds.
   * @param aClampMaxRowLine the maximum allowed row line number (zero-based)
   * Pre-condition: aArea->mCols.IsDefinite() is true.
   * Post-condition: aArea->IsDefinite() is true.
   */
  void PlaceAutoRow(uint32_t aStartRow, GridArea* aArea,
                    uint32_t aClampMaxRowLine) const;

  /**
   * Place aArea in the first column starting at aStartCol,aStartRow without
   * causing it to overlap other items or overflow mGridColEnd.
   * If there's no such column in aStartRow, continue in position 1,aStartRow+1.
   * @param aClampMaxColLine the maximum allowed column line number (zero-based)
   * @param aClampMaxRowLine the maximum allowed row line number (zero-based)
   * Pre-condition: aArea->mCols.IsAuto() && aArea->mRows.IsAuto() is true.
   * Post-condition: aArea->IsDefinite() is true.
   */
  void PlaceAutoAutoInRowOrder(uint32_t aStartCol, uint32_t aStartRow,
                               GridArea* aArea, uint32_t aClampMaxColLine,
                               uint32_t aClampMaxRowLine) const;

  /**
   * Place aArea in the first row starting at aStartCol,aStartRow without
   * causing it to overlap other items or overflow mGridRowEnd.
   * If there's no such row in aStartCol, continue in position aStartCol+1,1.
   * @param aClampMaxColLine the maximum allowed column line number (zero-based)
   * @param aClampMaxRowLine the maximum allowed row line number (zero-based)
   * Pre-condition: aArea->mCols.IsAuto() && aArea->mRows.IsAuto() is true.
   * Post-condition: aArea->IsDefinite() is true.
   */
  void PlaceAutoAutoInColOrder(uint32_t aStartCol, uint32_t aStartRow,
                               GridArea* aArea, uint32_t aClampMaxColLine,
                               uint32_t aClampMaxRowLine) const;

  /**
   * Return aLine if it's inside the aMin..aMax range (inclusive),
   * otherwise return kAutoLine.
   */
  static int32_t AutoIfOutside(int32_t aLine, int32_t aMin, int32_t aMax) {
    MOZ_ASSERT(aMin <= aMax);
    if (aLine < aMin || aLine > aMax) {
      return kAutoLine;
    }
    return aLine;
  }

  /**
   * Inflate the implicit grid to include aArea.
   * @param aArea may be definite or auto
   */
  void InflateGridFor(const GridArea& aArea) {
    mGridColEnd = std::max(mGridColEnd, aArea.mCols.HypotheticalEnd());
    mGridRowEnd = std::max(mGridRowEnd, aArea.mRows.HypotheticalEnd());
    MOZ_ASSERT(mGridColEnd <= kTranslatedMaxLine &&
               mGridRowEnd <= kTranslatedMaxLine);
  }

  /**
   * Calculates the empty tracks in a repeat(auto-fit).
   * @param aOutNumEmptyLines Outputs the number of tracks which are empty.
   * @param aSizingFunctions Sizing functions for the relevant axis.
   * @param aNumGridLines Number of grid lines for the relevant axis.
   * @param aIsEmptyFunc Functor to check if a cell is empty. This should be
   * mCellMap.IsColEmpty or mCellMap.IsRowEmpty, depending on the axis.
   */
  template <typename IsEmptyFuncT>
  static Maybe<nsTArray<uint32_t>> CalculateAdjustForAutoFitElements(
      uint32_t* aOutNumEmptyTracks, TrackSizingFunctions& aSizingFunctions,
      uint32_t aNumGridLines, IsEmptyFuncT aIsEmptyFunc);

  /**
   * Return a line number for (non-auto) aLine, per:
   * http://dev.w3.org/csswg/css-grid/#line-placement
   * @param aLine style data for the line (must be non-auto)
   * @param aNth a number of lines to find from aFromIndex, negative if the
   *             search should be in reverse order.  In the case aLine has
   *             a specified line name, it's permitted to pass in zero which
   *             will be treated as one.
   * @param aFromIndex the zero-based index to start counting from
   * @param aLineNameList the explicit named lines
   * @param aSide the axis+edge we're resolving names for (e.g. if we're
                  resolving a grid-row-start line, pass eLogicalSideBStart)
   * @param aExplicitGridEnd the last line in the explicit grid
   * @param aStyle the StylePosition() for the grid container
   * @return a definite line (1-based), clamped to
   *   the mClampMinLine..mClampMaxLine range
   */
  int32_t ResolveLine(const StyleGridLine& aLine, int32_t aNth,
                      uint32_t aFromIndex, const LineNameMap& aNameMap,
                      LogicalSide aSide, uint32_t aExplicitGridEnd,
                      const nsStylePosition* aStyle);

  /**
   * Helper method for ResolveLineRange.
   * @see ResolveLineRange
   * @return a pair (start,end) of lines
   */
  typedef std::pair<int32_t, int32_t> LinePair;
  LinePair ResolveLineRangeHelper(const StyleGridLine& aStart,
                                  const StyleGridLine& aEnd,
                                  const LineNameMap& aNameMap,
                                  LogicalAxis aAxis, uint32_t aExplicitGridEnd,
                                  const nsStylePosition* aStyle);

  /**
   * Return a LineRange based on the given style data. Non-auto lines
   * are resolved to a definite line number (1-based) per:
   * http://dev.w3.org/csswg/css-grid/#line-placement
   * with placement errors corrected per:
   * http://dev.w3.org/csswg/css-grid/#grid-placement-errors
   * @param aStyle the StylePosition() for the grid container
   * @param aStart style data for the start line
   * @param aEnd style data for the end line
   * @param aLineNameList the explicit named lines
   * @param aAxis the axis we're resolving names in
   * @param aExplicitGridEnd the last line in the explicit grid
   * @param aStyle the StylePosition() for the grid container
   */
  LineRange ResolveLineRange(const StyleGridLine& aStart,
                             const StyleGridLine& aEnd,
                             const LineNameMap& aNameMap, LogicalAxis aAxis,
                             uint32_t aExplicitGridEnd,
                             const nsStylePosition* aStyle);

  /**
   * Return a GridArea with non-auto lines placed at a definite line (1-based)
   * with placement errors resolved.  One or both positions may still
   * be 'auto'.
   * @param aChild the grid item
   * @param aStyle the StylePosition() for the grid container
   */
  GridArea PlaceDefinite(nsIFrame* aChild, const LineNameMap& aColLineNameMap,
                         const LineNameMap& aRowLineNameMap,
                         const nsStylePosition* aStyle);

  bool HasImplicitNamedArea(nsAtom* aName) const {
    return mAreas && mAreas->has(aName);
  }

  // Return true if aString ends in aSuffix and has at least one character
  // before the suffix. Assign aIndex to where the suffix starts.
  static bool IsNameWithSuffix(nsAtom* aString, const nsString& aSuffix,
                               uint32_t* aIndex) {
    if (StringEndsWith(nsDependentAtomString(aString), aSuffix)) {
      *aIndex = aString->GetLength() - aSuffix.Length();
      return *aIndex != 0;
    }
    return false;
  }

  static bool IsNameWithEndSuffix(nsAtom* aString, uint32_t* aIndex) {
    return IsNameWithSuffix(aString, u"-end"_ns, aIndex);
  }

  static bool IsNameWithStartSuffix(nsAtom* aString, uint32_t* aIndex) {
    return IsNameWithSuffix(aString, u"-start"_ns, aIndex);
  }

  // Return the relevant parent LineNameMap for the given subgrid axis aAxis.
  const LineNameMap* ParentLineMapForAxis(bool aIsOrthogonal,
                                          LogicalAxis aAxis) const {
    if (!mParentGrid) {
      return nullptr;
    }
    bool isRows = aIsOrthogonal == (aAxis == eLogicalAxisInline);
    return isRows ? mParentGrid->mRowNameMap : mParentGrid->mColNameMap;
  }

  void SetLineMaps(const LineNameMap* aColNameMap,
                   const LineNameMap* aRowNameMap) {
    mColNameMap = aColNameMap;
    mRowNameMap = aRowNameMap;
  }

  /**
   * A CellMap holds state for each cell in the grid.
   * It's row major.  It's sparse in the sense that it only has enough rows to
   * cover the last row that has a grid item.  Each row only has enough entries
   * to cover columns that are occupied *on that row*, i.e. it's not a full
   * matrix covering the entire implicit grid.  An absent Cell means that it's
   * unoccupied by any grid item.
   */
  struct CellMap {
    struct Cell {
      constexpr Cell() : mIsOccupied(false) {}
      bool mIsOccupied : 1;
    };

    void Fill(const GridArea& aGridArea) {
      MOZ_ASSERT(aGridArea.IsDefinite());
      MOZ_ASSERT(aGridArea.mRows.mStart < aGridArea.mRows.mEnd);
      MOZ_ASSERT(aGridArea.mCols.mStart < aGridArea.mCols.mEnd);
      const auto numRows = aGridArea.mRows.mEnd;
      const auto numCols = aGridArea.mCols.mEnd;
      mCells.EnsureLengthAtLeast(numRows);
      for (auto i = aGridArea.mRows.mStart; i < numRows; ++i) {
        nsTArray<Cell>& cellsInRow = mCells[i];
        cellsInRow.EnsureLengthAtLeast(numCols);
        for (auto j = aGridArea.mCols.mStart; j < numCols; ++j) {
          cellsInRow[j].mIsOccupied = true;
        }
      }
    }

    uint32_t IsEmptyCol(uint32_t aCol) const {
      for (auto& row : mCells) {
        if (aCol < row.Length() && row[aCol].mIsOccupied) {
          return false;
        }
      }
      return true;
    }
    uint32_t IsEmptyRow(uint32_t aRow) const {
      if (aRow >= mCells.Length()) {
        return true;
      }
      for (const Cell& cell : mCells[aRow]) {
        if (cell.mIsOccupied) {
          return false;
        }
      }
      return true;
    }
#ifdef DEBUG
    void Dump() const {
      const size_t numRows = mCells.Length();
      for (size_t i = 0; i < numRows; ++i) {
        const nsTArray<Cell>& cellsInRow = mCells[i];
        const size_t numCols = cellsInRow.Length();
        printf("%lu:\t", (unsigned long)i + 1);
        for (size_t j = 0; j < numCols; ++j) {
          printf(cellsInRow[j].mIsOccupied ? "X " : ". ");
        }
        printf("\n");
      }
    }
#endif

    nsTArray<nsTArray<Cell>> mCells;
  };

  /**
   * State for each cell in the grid.
   */
  CellMap mCellMap;
  /**
   * @see HasImplicitNamedArea.
   */
  ImplicitNamedAreas* mAreas;
  /**
   * The last column grid line (1-based) in the explicit grid.
   * (i.e. the number of explicit columns + 1)
   */
  uint32_t mExplicitGridColEnd;
  /**
   * The last row grid line (1-based) in the explicit grid.
   * (i.e. the number of explicit rows + 1)
   */
  uint32_t mExplicitGridRowEnd;
  // Same for the implicit grid, except these become zero-based after
  // resolving definite lines.
  uint32_t mGridColEnd;
  uint32_t mGridRowEnd;

  /**
   * Offsets from the start of the implicit grid to the start of the translated
   * explicit grid.  They are zero if there are no implicit lines before 1,1.
   * e.g. "grid-column: span 3 / 1" makes mExplicitGridOffsetCol = 3 and the
   * corresponding GridArea::mCols will be 0 / 3 in the zero-based translated
   * grid.
   */
  uint32_t mExplicitGridOffsetCol;
  uint32_t mExplicitGridOffsetRow;

  /**
   * Our parent grid if any.
   */
  const Grid* mParentGrid;

  /**
   * Our LineNameMaps.
   */
  const LineNameMap* mColNameMap;
  const LineNameMap* mRowNameMap;
};

/**
 * Compute margin+border+padding for aGridItem.mFrame (a subgrid) and store it
 * on its Subgrid property (and return that property).
 * aPercentageBasis is in the grid item's writing-mode.
 */
static Subgrid* SubgridComputeMarginBorderPadding(
    const GridItemInfo& aGridItem, const LogicalSize& aPercentageBasis) {
  auto* subgridFrame = aGridItem.SubgridFrame();
  auto cbWM = aGridItem.mFrame->GetParent()->GetWritingMode();
  nsMargin physicalMBP;
  {
    auto wm = subgridFrame->GetWritingMode();
    auto pmPercentageBasis = cbWM.IsOrthogonalTo(wm)
                                 ? aPercentageBasis.BSize(wm)
                                 : aPercentageBasis.ISize(wm);
    SizeComputationInput sz(subgridFrame, nullptr, cbWM, pmPercentageBasis);
    physicalMBP =
        sz.ComputedPhysicalMargin() + sz.ComputedPhysicalBorderPadding();
  }
  auto* subgrid = subgridFrame->GetProperty(Subgrid::Prop());
  subgrid->mMarginBorderPadding = LogicalMargin(cbWM, physicalMBP);
  if (aGridItem.mFrame != subgridFrame) {
    nsIScrollableFrame* scrollFrame = aGridItem.mFrame->GetScrollTargetFrame();
    if (scrollFrame) {
      nsMargin ssz = scrollFrame->GetActualScrollbarSizes();
      subgrid->mMarginBorderPadding += LogicalMargin(cbWM, ssz);
    }

    if (aGridItem.mFrame->IsFieldSetFrame()) {
      const auto* f = static_cast<nsFieldSetFrame*>(aGridItem.mFrame);
      const auto* inner = f->GetInner();
      auto wm = inner->GetWritingMode();
      LogicalPoint pos = inner->GetLogicalPosition(aGridItem.mFrame->GetSize());
      // The legend is always on the BStart side and it inflates the fieldset's
      // "border area" size.  The inner frame's b-start pos equals that size.
      LogicalMargin offsets(wm, pos.B(wm), 0, 0, 0);
      subgrid->mMarginBorderPadding += offsets.ConvertTo(cbWM, wm);
    }
  }
  return subgrid;
}

static void CopyUsedTrackSizes(nsTArray<TrackSize>& aResult,
                               const nsGridContainerFrame* aUsedTrackSizesFrame,
                               const UsedTrackSizes* aUsedTrackSizes,
                               const nsGridContainerFrame* aSubgridFrame,
                               const Subgrid* aSubgrid,
                               LogicalAxis aSubgridAxis) {
  MOZ_ASSERT(aSubgridFrame->ParentGridContainerForSubgrid() ==
             aUsedTrackSizesFrame);
  aResult.SetLength(aSubgridAxis == eLogicalAxisInline ? aSubgrid->mGridColEnd
                                                       : aSubgrid->mGridRowEnd);
  auto parentAxis =
      aSubgrid->mIsOrthogonal ? GetOrthogonalAxis(aSubgridAxis) : aSubgridAxis;
  const auto& parentSizes = aUsedTrackSizes->mSizes[parentAxis];
  MOZ_ASSERT(aUsedTrackSizes->mCanResolveLineRangeSize[parentAxis]);
  if (parentSizes.IsEmpty()) {
    return;
  }
  const auto& range = aSubgrid->mArea.LineRangeForAxis(parentAxis);
  const auto cbwm = aUsedTrackSizesFrame->GetWritingMode();
  const auto wm = aSubgridFrame->GetWritingMode();
  // Recompute the MBP to resolve percentages against the resolved track sizes.
  if (parentAxis == eLogicalAxisInline) {
    // Find the subgrid's grid item frame in its parent grid container.  This
    // is usually the same as aSubgridFrame but it may also have a ScrollFrame,
    // FieldSetFrame etc.  We just loop until we see the first ancestor
    // GridContainerFrame and pick the last frame we saw before that.
    // Note that all subgrids are inside a parent (sub)grid container.
    const nsIFrame* outerGridItemFrame = aSubgridFrame;
    for (nsIFrame* parent = aSubgridFrame->GetParent();
         parent != aUsedTrackSizesFrame; parent = parent->GetParent()) {
      MOZ_ASSERT(!parent->IsGridContainerFrame());
      outerGridItemFrame = parent;
    }
    auto sizeInAxis = range.ToLength(aUsedTrackSizes->mSizes[parentAxis]);
    LogicalSize pmPercentageBasis =
        aSubgrid->mIsOrthogonal ? LogicalSize(wm, nscoord(0), sizeInAxis)
                                : LogicalSize(wm, sizeInAxis, nscoord(0));
    GridItemInfo info(const_cast<nsIFrame*>(outerGridItemFrame),
                      aSubgrid->mArea);
    SubgridComputeMarginBorderPadding(info, pmPercentageBasis);
  }
  const LogicalMargin& mbp = aSubgrid->mMarginBorderPadding;
  nscoord startMBP;
  nscoord endMBP;
  if (MOZ_LIKELY(cbwm.ParallelAxisStartsOnSameSide(parentAxis, wm))) {
    startMBP = mbp.Start(parentAxis, cbwm);
    endMBP = mbp.End(parentAxis, cbwm);
    uint32_t i = range.mStart;
    nscoord startPos = parentSizes[i].mPosition + startMBP;
    for (auto& sz : aResult) {
      sz = parentSizes[i++];
      sz.mPosition -= startPos;
    }
  } else {
    startMBP = mbp.End(parentAxis, cbwm);
    endMBP = mbp.Start(parentAxis, cbwm);
    uint32_t i = range.mEnd - 1;
    const auto& parentEnd = parentSizes[i];
    nscoord parentEndPos = parentEnd.mPosition + parentEnd.mBase - startMBP;
    for (auto& sz : aResult) {
      sz = parentSizes[i--];
      sz.mPosition = parentEndPos - (sz.mPosition + sz.mBase);
    }
  }
  auto& startTrack = aResult[0];
  startTrack.mPosition = 0;
  startTrack.mBase -= startMBP;
  if (MOZ_UNLIKELY(startTrack.mBase < nscoord(0))) {
    // Our MBP doesn't fit in the start track.  Adjust the track position
    // to maintain track alignment with our parent.
    startTrack.mPosition = startTrack.mBase;
    startTrack.mBase = nscoord(0);
  }
  auto& endTrack = aResult.LastElement();
  endTrack.mBase -= endMBP;
  if (MOZ_UNLIKELY(endTrack.mBase < nscoord(0))) {
    endTrack.mBase = nscoord(0);
  }
}

void nsGridContainerFrame::UsedTrackSizes::ResolveTrackSizesForAxis(
    nsGridContainerFrame* aFrame, LogicalAxis aAxis, gfxContext& aRC) {
  if (mCanResolveLineRangeSize[aAxis]) {
    return;
  }
  if (!aFrame->IsSubgrid()) {
    // We can't resolve sizes in this axis at this point. aFrame is the top grid
    // container, which will store its final track sizes later once they're
    // resolved in this axis (in GridReflowInput::CalculateTrackSizesForAxis).
    // The single caller of this method only needs track sizes for
    // calculating a CB size and it will treat it as indefinite when
    // this happens.
    return;
  }
  auto* parent = aFrame->ParentGridContainerForSubgrid();
  auto* parentSizes = parent->GetUsedTrackSizes();
  if (!parentSizes) {
    parentSizes = new UsedTrackSizes();
    parent->SetProperty(UsedTrackSizes::Prop(), parentSizes);
  }
  auto* subgrid = aFrame->GetProperty(Subgrid::Prop());
  const auto parentAxis =
      subgrid->mIsOrthogonal ? GetOrthogonalAxis(aAxis) : aAxis;
  parentSizes->ResolveTrackSizesForAxis(parent, parentAxis, aRC);
  if (!parentSizes->mCanResolveLineRangeSize[parentAxis]) {
    if (aFrame->IsSubgrid(aAxis)) {
      ResolveSubgridTrackSizesForAxis(aFrame, aAxis, subgrid, aRC,
                                      NS_UNCONSTRAINEDSIZE);
    }
    return;
  }
  if (aFrame->IsSubgrid(aAxis)) {
    CopyUsedTrackSizes(mSizes[aAxis], parent, parentSizes, aFrame, subgrid,
                       aAxis);
    mCanResolveLineRangeSize[aAxis] = true;
  } else {
    const auto& range = subgrid->mArea.LineRangeForAxis(parentAxis);
    nscoord contentBoxSize = range.ToLength(parentSizes->mSizes[parentAxis]);
    auto parentWM = aFrame->GetParent()->GetWritingMode();
    contentBoxSize -=
        subgrid->mMarginBorderPadding.StartEnd(parentAxis, parentWM);
    contentBoxSize = std::max(nscoord(0), contentBoxSize);
    ResolveSubgridTrackSizesForAxis(aFrame, aAxis, subgrid, aRC,
                                    contentBoxSize);
  }
}

void nsGridContainerFrame::UsedTrackSizes::ResolveSubgridTrackSizesForAxis(
    nsGridContainerFrame* aFrame, LogicalAxis aAxis, Subgrid* aSubgrid,
    gfxContext& aRC, nscoord aContentBoxSize) {
  GridReflowInput state(aFrame, aRC);
  state.mGridItems = aSubgrid->mGridItems.Clone();
  Grid grid;
  grid.mGridColEnd = aSubgrid->mGridColEnd;
  grid.mGridRowEnd = aSubgrid->mGridRowEnd;
  state.CalculateTrackSizesForAxis(aAxis, grid, aContentBoxSize,
                                   SizingConstraint::NoConstraint);
  const auto& tracks = aAxis == eLogicalAxisInline ? state.mCols : state.mRows;
  mSizes[aAxis].Assign(tracks.mSizes);
  mCanResolveLineRangeSize[aAxis] = tracks.mCanResolveLineRangeSize;
  MOZ_ASSERT(mCanResolveLineRangeSize[aAxis]);
}

void nsGridContainerFrame::GridReflowInput::CalculateTrackSizesForAxis(
    LogicalAxis aAxis, const Grid& aGrid, nscoord aContentBoxSize,
    SizingConstraint aConstraint) {
  auto& tracks = aAxis == eLogicalAxisInline ? mCols : mRows;
  const auto& sizingFunctions =
      aAxis == eLogicalAxisInline ? mColFunctions : mRowFunctions;
  const auto& gapStyle = aAxis == eLogicalAxisInline ? mGridStyle->mColumnGap
                                                     : mGridStyle->mRowGap;
  if (tracks.mIsMasonry) {
    // See comment on nsGridContainerFrame::MasonryLayout().
    tracks.Initialize(sizingFunctions, gapStyle, 2, aContentBoxSize);
    tracks.mCanResolveLineRangeSize = true;
    return;
  }
  uint32_t gridEnd =
      aAxis == eLogicalAxisInline ? aGrid.mGridColEnd : aGrid.mGridRowEnd;
  Maybe<TrackSizingFunctions> fallbackTrackSizing;

  bool useParentGaps = false;
  const bool isSubgriddedAxis = mFrame->IsSubgrid(aAxis);
  if (MOZ_LIKELY(!isSubgriddedAxis)) {
    tracks.Initialize(sizingFunctions, gapStyle, gridEnd, aContentBoxSize);
  } else {
    tracks.mGridGap =
        nsLayoutUtils::ResolveGapToLength(gapStyle, aContentBoxSize);
    tracks.mContentBoxSize = aContentBoxSize;
    const auto* subgrid = mFrame->GetProperty(Subgrid::Prop());
    tracks.mSizes.SetLength(gridEnd);
    auto* parent = mFrame->ParentGridContainerForSubgrid();
    auto parentAxis = subgrid->mIsOrthogonal ? GetOrthogonalAxis(aAxis) : aAxis;
    const auto* parentSizes = parent->GetUsedTrackSizes();
    if (parentSizes && parentSizes->mCanResolveLineRangeSize[parentAxis]) {
      CopyUsedTrackSizes(tracks.mSizes, parent, parentSizes, mFrame, subgrid,
                         aAxis);
      useParentGaps = gapStyle.IsNormal();
    } else {
      fallbackTrackSizing.emplace(TrackSizingFunctions::ForSubgridFallback(
          mFrame, subgrid, parent, parentAxis));
      tracks.Initialize(*fallbackTrackSizing, gapStyle, gridEnd,
                        aContentBoxSize);
    }
  }

  // We run the Track Sizing Algorithm in non-subgridded axes, and in some
  // cases in a subgridded axis when our parent track sizes aren't resolved yet.
  if (MOZ_LIKELY(!isSubgriddedAxis) || fallbackTrackSizing.isSome()) {
    const size_t origGridItemCount = mGridItems.Length();
    if (mFrame->HasSubgridItems(aAxis)) {
      CollectSubgridItemsForAxis(aAxis, mGridItems);
    }
    tracks.CalculateSizes(
        *this, mGridItems,
        fallbackTrackSizing ? *fallbackTrackSizing : sizingFunctions,
        aContentBoxSize,
        aAxis == eLogicalAxisInline ? &GridArea::mCols : &GridArea::mRows,
        aConstraint);
    // XXXmats we're losing the baseline state of subgrid descendants that
    // CollectSubgridItemsForAxis added here.  We need to propagate that
    // state into the subgrid's Reflow somehow...
    mGridItems.TruncateLength(origGridItemCount);
  }

  if (aContentBoxSize != NS_UNCONSTRAINEDSIZE) {
    auto alignment = mGridStyle->UsedContentAlignment(tracks.mAxis);
    tracks.AlignJustifyContent(mGridStyle, alignment, mWM, aContentBoxSize,
                               isSubgriddedAxis);
  } else if (!useParentGaps) {
    const nscoord gridGap = tracks.mGridGap;
    nscoord pos = 0;
    for (TrackSize& sz : tracks.mSizes) {
      sz.mPosition = pos;
      pos += sz.mBase + gridGap;
    }
  }

  if (aConstraint == SizingConstraint::NoConstraint &&
      (mFrame->HasSubgridItems() || mFrame->IsSubgrid())) {
    mFrame->StoreUsedTrackSizes(aAxis, tracks.mSizes);
  }

  // positions and sizes are now final
  tracks.mCanResolveLineRangeSize = true;
}

void nsGridContainerFrame::GridReflowInput::CalculateTrackSizes(
    const Grid& aGrid, const LogicalSize& aContentBox,
    SizingConstraint aConstraint) {
  CalculateTrackSizesForAxis(eLogicalAxisInline, aGrid, aContentBox.ISize(mWM),
                             aConstraint);
  CalculateTrackSizesForAxis(eLogicalAxisBlock, aGrid, aContentBox.BSize(mWM),
                             aConstraint);
}

// Align an item's margin box in its aAxis inside aCBSize.
static void AlignJustifySelf(StyleAlignFlags aAlignment, LogicalAxis aAxis,
                             AlignJustifyFlags aFlags, nscoord aBaselineAdjust,
                             nscoord aCBSize, const ReflowInput& aRI,
                             const LogicalSize& aChildSize,
                             LogicalPoint* aPos) {
  MOZ_ASSERT(aAlignment != StyleAlignFlags::AUTO,
             "unexpected 'auto' "
             "computed value for normal flow grid item");

  // NOTE: this is the resulting frame offset (border box).
  nscoord offset = CSSAlignUtils::AlignJustifySelf(
      aAlignment, aAxis, aFlags, aBaselineAdjust, aCBSize, aRI, aChildSize);

  // Set the position (aPos) for the requested alignment.
  if (offset != 0) {
    WritingMode wm = aRI.GetWritingMode();
    nscoord& pos = aAxis == eLogicalAxisBlock ? aPos->B(wm) : aPos->I(wm);
    pos += MOZ_LIKELY(aFlags & AlignJustifyFlags::SameSide) ? offset : -offset;
  }
}

static void AlignSelf(const nsGridContainerFrame::GridItemInfo& aGridItem,
                      StyleAlignFlags aAlignSelf, nscoord aCBSize,
                      const WritingMode aCBWM, const ReflowInput& aRI,
                      const LogicalSize& aSize, AlignJustifyFlags aFlags,
                      LogicalPoint* aPos) {
  AlignJustifyFlags flags = aFlags;
  if (aAlignSelf & StyleAlignFlags::SAFE) {
    flags |= AlignJustifyFlags::OverflowSafe;
  }
  aAlignSelf &= ~StyleAlignFlags::FLAG_BITS;

  WritingMode childWM = aRI.GetWritingMode();
  if (aCBWM.ParallelAxisStartsOnSameSide(eLogicalAxisBlock, childWM)) {
    flags |= AlignJustifyFlags::SameSide;
  }

  // Grid's 'align-self' axis is never parallel to the container's inline axis.
  if (aAlignSelf == StyleAlignFlags::LEFT ||
      aAlignSelf == StyleAlignFlags::RIGHT) {
    aAlignSelf = StyleAlignFlags::START;
  }
  if (MOZ_LIKELY(aAlignSelf == StyleAlignFlags::NORMAL)) {
    aAlignSelf = StyleAlignFlags::STRETCH;
  }

  nscoord baselineAdjust = 0;
  if (aAlignSelf == StyleAlignFlags::BASELINE ||
      aAlignSelf == StyleAlignFlags::LAST_BASELINE) {
    aAlignSelf = aGridItem.GetSelfBaseline(aAlignSelf, eLogicalAxisBlock,
                                           &baselineAdjust);
    // Adjust the baseline alignment value if the baseline affects the opposite
    // side of what AlignJustifySelf expects.
    auto state = aGridItem.mState[eLogicalAxisBlock];
    if (aAlignSelf == StyleAlignFlags::LAST_BASELINE &&
        !GridItemInfo::BaselineAlignmentAffectsEndSide(state)) {
      aAlignSelf = StyleAlignFlags::BASELINE;
    } else if (aAlignSelf == StyleAlignFlags::BASELINE &&
               GridItemInfo::BaselineAlignmentAffectsEndSide(state)) {
      aAlignSelf = StyleAlignFlags::LAST_BASELINE;
    }
  }

  bool isOrthogonal = aCBWM.IsOrthogonalTo(childWM);
  LogicalAxis axis = isOrthogonal ? eLogicalAxisInline : eLogicalAxisBlock;
  AlignJustifySelf(aAlignSelf, axis, flags, baselineAdjust, aCBSize, aRI, aSize,
                   aPos);
}

static void JustifySelf(const nsGridContainerFrame::GridItemInfo& aGridItem,
                        StyleAlignFlags aJustifySelf, nscoord aCBSize,
                        const WritingMode aCBWM, const ReflowInput& aRI,
                        const LogicalSize& aSize, AlignJustifyFlags aFlags,
                        LogicalPoint* aPos) {
  AlignJustifyFlags flags = aFlags;
  if (aJustifySelf & StyleAlignFlags::SAFE) {
    flags |= AlignJustifyFlags::OverflowSafe;
  }
  aJustifySelf &= ~StyleAlignFlags::FLAG_BITS;

  WritingMode childWM = aRI.GetWritingMode();
  if (aCBWM.ParallelAxisStartsOnSameSide(eLogicalAxisInline, childWM)) {
    flags |= AlignJustifyFlags::SameSide;
  }

  if (MOZ_LIKELY(aJustifySelf == StyleAlignFlags::NORMAL)) {
    aJustifySelf = StyleAlignFlags::STRETCH;
  }

  nscoord baselineAdjust = 0;
  // Grid's 'justify-self' axis is always parallel to the container's inline
  // axis, so justify-self:left|right always applies.
  if (aJustifySelf == StyleAlignFlags::LEFT) {
    aJustifySelf =
        aCBWM.IsBidiLTR() ? StyleAlignFlags::START : StyleAlignFlags::END;
  } else if (aJustifySelf == StyleAlignFlags::RIGHT) {
    aJustifySelf =
        aCBWM.IsBidiLTR() ? StyleAlignFlags::END : StyleAlignFlags::START;
  } else if (aJustifySelf == StyleAlignFlags::BASELINE ||
             aJustifySelf == StyleAlignFlags::LAST_BASELINE) {
    aJustifySelf = aGridItem.GetSelfBaseline(aJustifySelf, eLogicalAxisInline,
                                             &baselineAdjust);
    // Adjust the baseline alignment value if the baseline affects the opposite
    // side of what AlignJustifySelf expects.
    auto state = aGridItem.mState[eLogicalAxisInline];
    if (aJustifySelf == StyleAlignFlags::LAST_BASELINE &&
        !GridItemInfo::BaselineAlignmentAffectsEndSide(state)) {
      aJustifySelf = StyleAlignFlags::BASELINE;
    } else if (aJustifySelf == StyleAlignFlags::BASELINE &&
               GridItemInfo::BaselineAlignmentAffectsEndSide(state)) {
      aJustifySelf = StyleAlignFlags::LAST_BASELINE;
    }
  }

  bool isOrthogonal = aCBWM.IsOrthogonalTo(childWM);
  LogicalAxis axis = isOrthogonal ? eLogicalAxisBlock : eLogicalAxisInline;
  AlignJustifySelf(aJustifySelf, axis, flags, baselineAdjust, aCBSize, aRI,
                   aSize, aPos);
}

static StyleAlignFlags GetAlignJustifyValue(StyleAlignFlags aAlignment,
                                            const WritingMode aWM,
                                            const bool aIsAlign,
                                            bool* aOverflowSafe) {
  *aOverflowSafe = bool(aAlignment & StyleAlignFlags::SAFE);
  aAlignment &= ~StyleAlignFlags::FLAG_BITS;

  // Map some alignment values to 'start' / 'end'.
  if (aAlignment == StyleAlignFlags::LEFT ||
      aAlignment == StyleAlignFlags::RIGHT) {
    if (aIsAlign) {
      // Grid's 'align-content' axis is never parallel to the inline axis.
      return StyleAlignFlags::START;
    }
    bool isStart = aWM.IsBidiLTR() == (aAlignment == StyleAlignFlags::LEFT);
    return isStart ? StyleAlignFlags::START : StyleAlignFlags::END;
  }
  if (aAlignment == StyleAlignFlags::FLEX_START) {
    return StyleAlignFlags::START;  // same as 'start' for Grid
  }
  if (aAlignment == StyleAlignFlags::FLEX_END) {
    return StyleAlignFlags::END;  // same as 'end' for Grid
  }
  return aAlignment;
}

static Maybe<StyleAlignFlags> GetAlignJustifyFallbackIfAny(
    const StyleContentDistribution& aDistribution, const WritingMode aWM,
    const bool aIsAlign, bool* aOverflowSafe) {
  // TODO: Eventually this should look at aDistribution's fallback alignment,
  // see https://github.com/w3c/csswg-drafts/issues/1002.
  if (aDistribution.primary == StyleAlignFlags::STRETCH ||
      aDistribution.primary == StyleAlignFlags::SPACE_BETWEEN) {
    return Some(StyleAlignFlags::START);
  }
  if (aDistribution.primary == StyleAlignFlags::SPACE_AROUND ||
      aDistribution.primary == StyleAlignFlags::SPACE_EVENLY) {
    return Some(StyleAlignFlags::CENTER);
  }
  return Nothing();
}

//----------------------------------------------------------------------

// Frame class boilerplate
// =======================

NS_QUERYFRAME_HEAD(nsGridContainerFrame)
  NS_QUERYFRAME_ENTRY(nsGridContainerFrame)
NS_QUERYFRAME_TAIL_INHERITING(nsContainerFrame)

NS_IMPL_FRAMEARENA_HELPERS(nsGridContainerFrame)

nsContainerFrame* NS_NewGridContainerFrame(PresShell* aPresShell,
                                           ComputedStyle* aStyle) {
  return new (aPresShell)
      nsGridContainerFrame(aStyle, aPresShell->GetPresContext());
}

//----------------------------------------------------------------------

// nsGridContainerFrame Method Implementations
// ===========================================

/*static*/ const nsRect& nsGridContainerFrame::GridItemCB(nsIFrame* aChild) {
  MOZ_ASSERT(aChild->IsAbsolutelyPositioned());
  nsRect* cb = aChild->GetProperty(GridItemContainingBlockRect());
  MOZ_ASSERT(cb,
             "this method must only be called on grid items, and the grid "
             "container should've reflowed this item by now and set up cb");
  return *cb;
}

void nsGridContainerFrame::AddImplicitNamedAreas(
    Span<LineNameList> aLineNameLists) {
  // http://dev.w3.org/csswg/css-grid/#implicit-named-areas
  // Note: recording these names for fast lookup later is just an optimization.
  const uint32_t len = std::min(aLineNameLists.Length(), size_t(kMaxLine));
  nsTHashSet<nsString> currentStarts;
  ImplicitNamedAreas* areas = GetImplicitNamedAreas();
  for (uint32_t i = 0; i < len; ++i) {
    for (const auto& nameIdent : aLineNameLists[i].AsSpan()) {
      nsAtom* name = nameIdent.AsAtom();
      uint32_t indexOfSuffix;
      if (Grid::IsNameWithStartSuffix(name, &indexOfSuffix) ||
          Grid::IsNameWithEndSuffix(name, &indexOfSuffix)) {
        // Extract the name that was found earlier.
        nsDependentSubstring areaName(nsDependentAtomString(name), 0,
                                      indexOfSuffix);

        // Lazily create the ImplicitNamedAreas.
        if (!areas) {
          areas = new ImplicitNamedAreas;
          SetProperty(ImplicitNamedAreasProperty(), areas);
        }

        RefPtr<nsAtom> name = NS_Atomize(areaName);
        auto addPtr = areas->lookupForAdd(name);
        if (!addPtr) {
          if (!areas->add(
                  addPtr, name,
                  NamedArea{StyleAtom(do_AddRef(name)), {0, 0}, {0, 0}})) {
            MOZ_CRASH("OOM while adding grid name lists");
          }
        }
      }
    }
  }
}

void nsGridContainerFrame::InitImplicitNamedAreas(
    const nsStylePosition* aStyle) {
  ImplicitNamedAreas* areas = GetImplicitNamedAreas();
  if (areas) {
    // Clear it, but reuse the hashtable itself for now.  We'll remove it
    // below if it isn't needed anymore.
    areas->clear();
  }
  auto Add = [&](const GridTemplate& aTemplate, bool aIsSubgrid) {
    AddImplicitNamedAreas(aTemplate.LineNameLists(aIsSubgrid));
    for (auto& value : aTemplate.TrackListValues()) {
      if (value.IsTrackRepeat()) {
        AddImplicitNamedAreas(value.AsTrackRepeat().line_names.AsSpan());
      }
    }
  };
  Add(aStyle->mGridTemplateColumns, IsSubgrid(eLogicalAxisInline));
  Add(aStyle->mGridTemplateRows, IsSubgrid(eLogicalAxisBlock));
  if (areas && areas->count() == 0) {
    RemoveProperty(ImplicitNamedAreasProperty());
  }
}

int32_t nsGridContainerFrame::Grid::ResolveLine(
    const StyleGridLine& aLine, int32_t aNth, uint32_t aFromIndex,
    const LineNameMap& aNameMap, LogicalSide aSide, uint32_t aExplicitGridEnd,
    const nsStylePosition* aStyle) {
  MOZ_ASSERT(!aLine.IsAuto());
  int32_t line = 0;
  if (aLine.LineName()->IsEmpty()) {
    MOZ_ASSERT(aNth != 0, "css-grid 9.2: <integer> must not be zero.");
    line = int32_t(aFromIndex) + aNth;
  } else {
    if (aNth == 0) {
      // <integer> was omitted; treat it as 1.
      aNth = 1;
    }
    bool isNameOnly = !aLine.is_span && aLine.line_num == 0;
    if (isNameOnly) {
      AutoTArray<uint32_t, 16> implicitLines;
      aNameMap.FindNamedAreas(aLine.ident.AsAtom(), aSide, implicitLines);
      if (!implicitLines.IsEmpty() ||
          aNameMap.HasImplicitNamedArea(aLine.LineName())) {
        // aName is a named area - look for explicit lines named
        // <name>-start/-end depending on which side we're resolving.
        // http://dev.w3.org/csswg/css-grid/#grid-placement-slot
        nsAutoString lineName(nsDependentAtomString(aLine.LineName()));
        if (IsStart(aSide)) {
          lineName.AppendLiteral("-start");
        } else {
          lineName.AppendLiteral("-end");
        }
        RefPtr<nsAtom> name = NS_Atomize(lineName);
        line = aNameMap.FindNamedLine(name, &aNth, aFromIndex, implicitLines);
      }
    }

    if (line == 0) {
      // If LineName() ends in -start/-end, try the prefix as a named area.
      AutoTArray<uint32_t, 16> implicitLines;
      uint32_t index;
      bool useStart = IsNameWithStartSuffix(aLine.LineName(), &index);
      if (useStart || IsNameWithEndSuffix(aLine.LineName(), &index)) {
        auto side = MakeLogicalSide(
            GetAxis(aSide), useStart ? eLogicalEdgeStart : eLogicalEdgeEnd);
        RefPtr<nsAtom> name = NS_Atomize(nsDependentSubstring(
            nsDependentAtomString(aLine.LineName()), 0, index));
        aNameMap.FindNamedAreas(name, side, implicitLines);
      }
      line = aNameMap.FindNamedLine(aLine.LineName(), &aNth, aFromIndex,
                                    implicitLines);
    }

    if (line == 0) {
      MOZ_ASSERT(aNth != 0, "we found all N named lines but 'line' is zero!");
      int32_t edgeLine;
      if (aLine.is_span) {
        // http://dev.w3.org/csswg/css-grid/#grid-placement-span-int
        // 'span <custom-ident> N'
        edgeLine = IsStart(aSide) ? 1 : aExplicitGridEnd;
      } else {
        // http://dev.w3.org/csswg/css-grid/#grid-placement-int
        // '<custom-ident> N'
        edgeLine = aNth < 0 ? 1 : aExplicitGridEnd;
      }
      // "If not enough lines with that name exist, all lines in the implicit
      // grid are assumed to have that name..."
      line = edgeLine + aNth;
    }
  }
  return clamped(line, aNameMap.mClampMinLine, aNameMap.mClampMaxLine);
}

nsGridContainerFrame::Grid::LinePair
nsGridContainerFrame::Grid::ResolveLineRangeHelper(
    const StyleGridLine& aStart, const StyleGridLine& aEnd,
    const LineNameMap& aNameMap, LogicalAxis aAxis, uint32_t aExplicitGridEnd,
    const nsStylePosition* aStyle) {
  MOZ_ASSERT(int32_t(kAutoLine) > kMaxLine);

  if (aStart.is_span) {
    if (aEnd.is_span || aEnd.IsAuto()) {
      // http://dev.w3.org/csswg/css-grid/#grid-placement-errors
      if (aStart.LineName()->IsEmpty()) {
        // span <integer> / span *
        // span <integer> / auto
        return LinePair(kAutoLine, aStart.line_num);
      }
      // span <custom-ident> / span *
      // span <custom-ident> / auto
      return LinePair(kAutoLine, 1);  // XXX subgrid explicit size instead of 1?
    }

    uint32_t from = aEnd.line_num < 0 ? aExplicitGridEnd + 1 : 0;
    auto end = ResolveLine(aEnd, aEnd.line_num, from, aNameMap,
                           MakeLogicalSide(aAxis, eLogicalEdgeEnd),
                           aExplicitGridEnd, aStyle);
    int32_t span = aStart.line_num == 0 ? 1 : aStart.line_num;
    if (end <= 1) {
      // The end is at or before the first explicit line, thus all lines before
      // it match <custom-ident> since they're implicit.
      int32_t start = std::max(end - span, aNameMap.mClampMinLine);
      return LinePair(start, end);
    }
    auto start = ResolveLine(aStart, -span, end, aNameMap,
                             MakeLogicalSide(aAxis, eLogicalEdgeStart),
                             aExplicitGridEnd, aStyle);
    return LinePair(start, end);
  }

  int32_t start = kAutoLine;
  if (aStart.IsAuto()) {
    if (aEnd.IsAuto()) {
      // auto / auto
      return LinePair(start, 1);  // XXX subgrid explicit size instead of 1?
    }
    if (aEnd.is_span) {
      if (aEnd.LineName()->IsEmpty()) {
        // auto / span <integer>
        MOZ_ASSERT(aEnd.line_num != 0);
        return LinePair(start, aEnd.line_num);
      }
      // http://dev.w3.org/csswg/css-grid/#grid-placement-errors
      // auto / span <custom-ident>
      return LinePair(start, 1);  // XXX subgrid explicit size instead of 1?
    }
  } else {
    uint32_t from = aStart.line_num < 0 ? aExplicitGridEnd + 1 : 0;
    start = ResolveLine(aStart, aStart.line_num, from, aNameMap,
                        MakeLogicalSide(aAxis, eLogicalEdgeStart),
                        aExplicitGridEnd, aStyle);
    if (aEnd.IsAuto()) {
      // A "definite line / auto" should resolve the auto to 'span 1'.
      // The error handling in ResolveLineRange will make that happen and also
      // clamp the end line correctly if we return "start / start".
      return LinePair(start, start);
    }
  }

  uint32_t from;
  int32_t nth = aEnd.line_num == 0 ? 1 : aEnd.line_num;
  if (aEnd.is_span) {
    if (MOZ_UNLIKELY(start < 0)) {
      if (aEnd.LineName()->IsEmpty()) {
        return LinePair(start, start + nth);
      }
      from = 0;
    } else {
      if (start >= int32_t(aExplicitGridEnd)) {
        // The start is at or after the last explicit line, thus all lines
        // after it match <custom-ident> since they're implicit.
        return LinePair(start, std::min(start + nth, aNameMap.mClampMaxLine));
      }
      from = start;
    }
  } else {
    from = aEnd.line_num < 0 ? aExplicitGridEnd + 1 : 0;
  }
  auto end = ResolveLine(aEnd, nth, from, aNameMap,
                         MakeLogicalSide(aAxis, eLogicalEdgeEnd),
                         aExplicitGridEnd, aStyle);
  if (start == int32_t(kAutoLine)) {
    // auto / definite line
    start = std::max(aNameMap.mClampMinLine, end - 1);
  }
  return LinePair(start, end);
}

nsGridContainerFrame::LineRange nsGridContainerFrame::Grid::ResolveLineRange(
    const StyleGridLine& aStart, const StyleGridLine& aEnd,
    const LineNameMap& aNameMap, LogicalAxis aAxis, uint32_t aExplicitGridEnd,
    const nsStylePosition* aStyle) {
  LinePair r = ResolveLineRangeHelper(aStart, aEnd, aNameMap, aAxis,
                                      aExplicitGridEnd, aStyle);
  MOZ_ASSERT(r.second != int32_t(kAutoLine));

  if (r.first == int32_t(kAutoLine)) {
    // r.second is a span, clamp it to aNameMap.mClampMaxLine - 1 so that
    // the returned range has a HypotheticalEnd <= aNameMap.mClampMaxLine.
    // http://dev.w3.org/csswg/css-grid/#overlarge-grids
    r.second = std::min(r.second, aNameMap.mClampMaxLine - 1);
  } else {
    // http://dev.w3.org/csswg/css-grid/#grid-placement-errors
    if (r.first > r.second) {
      std::swap(r.first, r.second);
    } else if (r.first == r.second) {
      if (MOZ_UNLIKELY(r.first == aNameMap.mClampMaxLine)) {
        r.first = aNameMap.mClampMaxLine - 1;
      }
      r.second = r.first + 1;  // XXX subgrid explicit size instead of 1?
    }
  }
  return LineRange(r.first, r.second);
}

nsGridContainerFrame::GridArea nsGridContainerFrame::Grid::PlaceDefinite(
    nsIFrame* aChild, const LineNameMap& aColLineNameMap,
    const LineNameMap& aRowLineNameMap, const nsStylePosition* aStyle) {
  const nsStylePosition* itemStyle = aChild->StylePosition();
  return GridArea(
      ResolveLineRange(itemStyle->mGridColumnStart, itemStyle->mGridColumnEnd,
                       aColLineNameMap, eLogicalAxisInline, mExplicitGridColEnd,
                       aStyle),
      ResolveLineRange(itemStyle->mGridRowStart, itemStyle->mGridRowEnd,
                       aRowLineNameMap, eLogicalAxisBlock, mExplicitGridRowEnd,
                       aStyle));
}

nsGridContainerFrame::LineRange
nsGridContainerFrame::Grid::ResolveAbsPosLineRange(
    const StyleGridLine& aStart, const StyleGridLine& aEnd,
    const LineNameMap& aNameMap, LogicalAxis aAxis, uint32_t aExplicitGridEnd,
    int32_t aGridStart, int32_t aGridEnd, const nsStylePosition* aStyle) {
  if (aStart.IsAuto()) {
    if (aEnd.IsAuto()) {
      return LineRange(kAutoLine, kAutoLine);
    }
    uint32_t from = aEnd.line_num < 0 ? aExplicitGridEnd + 1 : 0;
    int32_t end = ResolveLine(aEnd, aEnd.line_num, from, aNameMap,
                              MakeLogicalSide(aAxis, eLogicalEdgeEnd),
                              aExplicitGridEnd, aStyle);
    if (aEnd.is_span) {
      ++end;
    }
    // A line outside the existing grid is treated as 'auto' for abs.pos (10.1).
    end = AutoIfOutside(end, aGridStart, aGridEnd);
    return LineRange(kAutoLine, end);
  }

  if (aEnd.IsAuto()) {
    uint32_t from = aStart.line_num < 0 ? aExplicitGridEnd + 1 : 0;
    int32_t start = ResolveLine(aStart, aStart.line_num, from, aNameMap,
                                MakeLogicalSide(aAxis, eLogicalEdgeStart),
                                aExplicitGridEnd, aStyle);
    if (aStart.is_span) {
      start = std::max(aGridEnd - start, aGridStart);
    }
    start = AutoIfOutside(start, aGridStart, aGridEnd);
    return LineRange(start, kAutoLine);
  }

  LineRange r =
      ResolveLineRange(aStart, aEnd, aNameMap, aAxis, aExplicitGridEnd, aStyle);
  if (r.IsAuto()) {
    MOZ_ASSERT(aStart.is_span && aEnd.is_span,
               "span / span is the only case "
               "leading to IsAuto here -- we dealt with the other cases above");
    // The second span was ignored per 9.2.1.  For abs.pos., 10.1 says that this
    // case should result in "auto / auto" unlike normal flow grid items.
    return LineRange(kAutoLine, kAutoLine);
  }

  return LineRange(AutoIfOutside(r.mUntranslatedStart, aGridStart, aGridEnd),
                   AutoIfOutside(r.mUntranslatedEnd, aGridStart, aGridEnd));
}

nsGridContainerFrame::GridArea nsGridContainerFrame::Grid::PlaceAbsPos(
    nsIFrame* aChild, const LineNameMap& aColLineNameMap,
    const LineNameMap& aRowLineNameMap, const nsStylePosition* aStyle) {
  const nsStylePosition* itemStyle = aChild->StylePosition();
  int32_t gridColStart = 1 - mExplicitGridOffsetCol;
  int32_t gridRowStart = 1 - mExplicitGridOffsetRow;
  return GridArea(ResolveAbsPosLineRange(
                      itemStyle->mGridColumnStart, itemStyle->mGridColumnEnd,
                      aColLineNameMap, eLogicalAxisInline, mExplicitGridColEnd,
                      gridColStart, mGridColEnd, aStyle),
                  ResolveAbsPosLineRange(
                      itemStyle->mGridRowStart, itemStyle->mGridRowEnd,
                      aRowLineNameMap, eLogicalAxisBlock, mExplicitGridRowEnd,
                      gridRowStart, mGridRowEnd, aStyle));
}

uint32_t nsGridContainerFrame::Grid::FindAutoCol(uint32_t aStartCol,
                                                 uint32_t aLockedRow,
                                                 const GridArea* aArea) const {
  const uint32_t extent = aArea->mCols.Extent();
  const uint32_t iStart = aLockedRow;
  const uint32_t iEnd = iStart + aArea->mRows.Extent();
  uint32_t candidate = aStartCol;
  for (uint32_t i = iStart; i < iEnd;) {
    if (i >= mCellMap.mCells.Length()) {
      break;
    }
    const nsTArray<CellMap::Cell>& cellsInRow = mCellMap.mCells[i];
    const uint32_t len = cellsInRow.Length();
    const uint32_t lastCandidate = candidate;
    // Find the first gap in the current row that's at least 'extent' wide.
    // ('gap' tracks how wide the current column gap is.)
    for (uint32_t j = candidate, gap = 0; j < len && gap < extent; ++j) {
      if (!cellsInRow[j].mIsOccupied) {
        ++gap;
        continue;
      }
      candidate = j + 1;
      gap = 0;
    }
    if (lastCandidate < candidate && i != iStart) {
      // Couldn't fit 'extent' tracks at 'lastCandidate' here so we must
      // restart from the beginning with the new 'candidate'.
      i = iStart;
    } else {
      ++i;
    }
  }
  return candidate;
}

void nsGridContainerFrame::Grid::PlaceAutoCol(uint32_t aStartCol,
                                              GridArea* aArea,
                                              uint32_t aClampMaxColLine) const {
  MOZ_ASSERT(aArea->mRows.IsDefinite() && aArea->mCols.IsAuto());
  uint32_t col = FindAutoCol(aStartCol, aArea->mRows.mStart, aArea);
  aArea->mCols.ResolveAutoPosition(col, aClampMaxColLine);
  MOZ_ASSERT(aArea->IsDefinite());
}

uint32_t nsGridContainerFrame::Grid::FindAutoRow(uint32_t aLockedCol,
                                                 uint32_t aStartRow,
                                                 const GridArea* aArea) const {
  const uint32_t extent = aArea->mRows.Extent();
  const uint32_t jStart = aLockedCol;
  const uint32_t jEnd = jStart + aArea->mCols.Extent();
  const uint32_t iEnd = mCellMap.mCells.Length();
  uint32_t candidate = aStartRow;
  // Find the first gap in the rows that's at least 'extent' tall.
  // ('gap' tracks how tall the current row gap is.)
  for (uint32_t i = candidate, gap = 0; i < iEnd && gap < extent; ++i) {
    ++gap;  // tentative, but we may reset it below if a column is occupied
    const nsTArray<CellMap::Cell>& cellsInRow = mCellMap.mCells[i];
    const uint32_t clampedJEnd = std::min<uint32_t>(jEnd, cellsInRow.Length());
    // Check if the current row is unoccupied from jStart to jEnd.
    for (uint32_t j = jStart; j < clampedJEnd; ++j) {
      if (cellsInRow[j].mIsOccupied) {
        // Couldn't fit 'extent' rows at 'candidate' here; we hit something
        // at row 'i'.  So, try the row after 'i' as our next candidate.
        candidate = i + 1;
        gap = 0;
        break;
      }
    }
  }
  return candidate;
}

void nsGridContainerFrame::Grid::PlaceAutoRow(uint32_t aStartRow,
                                              GridArea* aArea,
                                              uint32_t aClampMaxRowLine) const {
  MOZ_ASSERT(aArea->mCols.IsDefinite() && aArea->mRows.IsAuto());
  uint32_t row = FindAutoRow(aArea->mCols.mStart, aStartRow, aArea);
  aArea->mRows.ResolveAutoPosition(row, aClampMaxRowLine);
  MOZ_ASSERT(aArea->IsDefinite());
}

void nsGridContainerFrame::Grid::PlaceAutoAutoInRowOrder(
    uint32_t aStartCol, uint32_t aStartRow, GridArea* aArea,
    uint32_t aClampMaxColLine, uint32_t aClampMaxRowLine) const {
  MOZ_ASSERT(aArea->mCols.IsAuto() && aArea->mRows.IsAuto());
  const uint32_t colExtent = aArea->mCols.Extent();
  const uint32_t gridRowEnd = mGridRowEnd;
  const uint32_t gridColEnd = mGridColEnd;
  uint32_t col = aStartCol;
  uint32_t row = aStartRow;
  for (; row < gridRowEnd; ++row) {
    col = FindAutoCol(col, row, aArea);
    if (col + colExtent <= gridColEnd) {
      break;
    }
    col = 0;
  }
  MOZ_ASSERT(row < gridRowEnd || col == 0,
             "expected column 0 for placing in a new row");
  aArea->mCols.ResolveAutoPosition(col, aClampMaxColLine);
  aArea->mRows.ResolveAutoPosition(row, aClampMaxRowLine);
  MOZ_ASSERT(aArea->IsDefinite());
}

void nsGridContainerFrame::Grid::PlaceAutoAutoInColOrder(
    uint32_t aStartCol, uint32_t aStartRow, GridArea* aArea,
    uint32_t aClampMaxColLine, uint32_t aClampMaxRowLine) const {
  MOZ_ASSERT(aArea->mCols.IsAuto() && aArea->mRows.IsAuto());
  const uint32_t rowExtent = aArea->mRows.Extent();
  const uint32_t gridRowEnd = mGridRowEnd;
  const uint32_t gridColEnd = mGridColEnd;
  uint32_t col = aStartCol;
  uint32_t row = aStartRow;
  for (; col < gridColEnd; ++col) {
    row = FindAutoRow(col, row, aArea);
    if (row + rowExtent <= gridRowEnd) {
      break;
    }
    row = 0;
  }
  MOZ_ASSERT(col < gridColEnd || row == 0,
             "expected row 0 for placing in a new column");
  aArea->mCols.ResolveAutoPosition(col, aClampMaxColLine);
  aArea->mRows.ResolveAutoPosition(row, aClampMaxRowLine);
  MOZ_ASSERT(aArea->IsDefinite());
}

template <typename IsEmptyFuncT>
Maybe<nsTArray<uint32_t>>
nsGridContainerFrame::Grid::CalculateAdjustForAutoFitElements(
    uint32_t* const aOutNumEmptyLines, TrackSizingFunctions& aSizingFunctions,
    uint32_t aNumGridLines, IsEmptyFuncT aIsEmptyFunc) {
  Maybe<nsTArray<uint32_t>> trackAdjust;
  uint32_t& numEmptyLines = *aOutNumEmptyLines;
  numEmptyLines = 0;
  if (aSizingFunctions.NumRepeatTracks() > 0) {
    MOZ_ASSERT(aSizingFunctions.mHasRepeatAuto);
    // Since this loop is concerned with just the repeat tracks, we
    // iterate from 0..NumRepeatTracks() which is the natural range of
    // mRemoveRepeatTracks. This means we have to add
    // (mExplicitGridOffset + mRepeatAutoStart) to get a zero-based
    // index for arrays like mCellMap/aIsEmptyFunc and trackAdjust. We'll then
    // fill out the trackAdjust array for all the remaining lines.
    const uint32_t repeatStart = (aSizingFunctions.mExplicitGridOffset +
                                  aSizingFunctions.mRepeatAutoStart);
    const uint32_t numRepeats = aSizingFunctions.NumRepeatTracks();
    for (uint32_t i = 0; i < numRepeats; ++i) {
      if (numEmptyLines) {
        MOZ_ASSERT(trackAdjust.isSome());
        (*trackAdjust)[repeatStart + i] = numEmptyLines;
      }
      if (aIsEmptyFunc(repeatStart + i)) {
        ++numEmptyLines;
        if (trackAdjust.isNothing()) {
          trackAdjust.emplace(aNumGridLines);
          trackAdjust->SetLength(aNumGridLines);
          PodZero(trackAdjust->Elements(), trackAdjust->Length());
        }

        aSizingFunctions.mRemovedRepeatTracks[i] = true;
      }
    }
    // Fill out the trackAdjust array for all the tracks after the repeats.
    if (numEmptyLines) {
      for (uint32_t line = repeatStart + numRepeats; line < aNumGridLines;
           ++line) {
        (*trackAdjust)[line] = numEmptyLines;
      }
    }
  }

  return trackAdjust;
}

void nsGridContainerFrame::Grid::SubgridPlaceGridItems(
    GridReflowInput& aParentState, Grid* aParentGrid,
    const GridItemInfo& aGridItem) {
  MOZ_ASSERT(aGridItem.mArea.IsDefinite() ||
                 aGridItem.mFrame->HasAnyStateBits(NS_FRAME_OUT_OF_FLOW),
             "the subgrid's lines should be resolved by now");
  if (aGridItem.IsSubgrid(eLogicalAxisInline)) {
    aParentState.mFrame->AddStateBits(NS_STATE_GRID_HAS_COL_SUBGRID_ITEM);
  }
  if (aGridItem.IsSubgrid(eLogicalAxisBlock)) {
    aParentState.mFrame->AddStateBits(NS_STATE_GRID_HAS_ROW_SUBGRID_ITEM);
  }
  auto* childGrid = aGridItem.SubgridFrame();
  const auto* pos = childGrid->StylePosition();
  childGrid->NormalizeChildLists();
  GridReflowInput state(childGrid, aParentState.mRenderingContext);
  childGrid->InitImplicitNamedAreas(pos);

  const bool isOrthogonal = aParentState.mWM.IsOrthogonalTo(state.mWM);
  // Record the subgrid's GridArea in a frame property.
  auto* subgrid = childGrid->GetProperty(Subgrid::Prop());
  if (!subgrid) {
    subgrid = new Subgrid(aGridItem.mArea, isOrthogonal, aParentState.mWM);
    childGrid->SetProperty(Subgrid::Prop(), subgrid);
  } else {
    subgrid->mArea = aGridItem.mArea;
    subgrid->mIsOrthogonal = isOrthogonal;
    subgrid->mGridItems.Clear();
    subgrid->mAbsPosItems.Clear();
  }

  // Abs.pos. subgrids may have kAutoLine in their area.  Map those to the edge
  // line in the parent's grid (zero-based line numbers).
  if (MOZ_UNLIKELY(subgrid->mArea.mCols.mStart == kAutoLine)) {
    subgrid->mArea.mCols.mStart = 0;
  }
  if (MOZ_UNLIKELY(subgrid->mArea.mCols.mEnd == kAutoLine)) {
    subgrid->mArea.mCols.mEnd = aParentGrid->mGridColEnd - 1;
  }
  if (MOZ_UNLIKELY(subgrid->mArea.mRows.mStart == kAutoLine)) {
    subgrid->mArea.mRows.mStart = 0;
  }
  if (MOZ_UNLIKELY(subgrid->mArea.mRows.mEnd == kAutoLine)) {
    subgrid->mArea.mRows.mEnd = aParentGrid->mGridRowEnd - 1;
  }

  MOZ_ASSERT((subgrid->mArea.mCols.Extent() > 0 &&
              subgrid->mArea.mRows.Extent() > 0) ||
                 state.mGridItems.IsEmpty(),
             "subgrid needs at least one track for its items");

  // The min/sz/max sizes are the input to the "repeat-to-fill" algorithm:
  // https://drafts.csswg.org/css-grid/#auto-repeat
  // They're only used for auto-repeat in a non-subgridded axis so we skip
  // computing them otherwise.
  RepeatTrackSizingInput repeatSizing(state.mWM);
  if (!childGrid->IsColSubgrid() && state.mColFunctions.mHasRepeatAuto) {
    repeatSizing.InitFromStyle(eLogicalAxisInline, state.mWM,
                               state.mFrame->Style());
  }
  if (!childGrid->IsRowSubgrid() && state.mRowFunctions.mHasRepeatAuto) {
    repeatSizing.InitFromStyle(eLogicalAxisBlock, state.mWM,
                               state.mFrame->Style());
  }

  PlaceGridItems(state, repeatSizing);

  subgrid->mGridItems = std::move(state.mGridItems);
  subgrid->mAbsPosItems = std::move(state.mAbsPosItems);
  subgrid->mGridColEnd = mGridColEnd;
  subgrid->mGridRowEnd = mGridRowEnd;
}

void nsGridContainerFrame::Grid::PlaceGridItems(
    GridReflowInput& aState, const RepeatTrackSizingInput& aSizes) {
  MOZ_ASSERT(mCellMap.mCells.IsEmpty(), "unexpected entries in cell map");

  mAreas = aState.mFrame->GetImplicitNamedAreas();

  if (aState.mFrame->HasSubgridItems() || aState.mFrame->IsSubgrid()) {
    if (auto* uts = aState.mFrame->GetUsedTrackSizes()) {
      uts->mCanResolveLineRangeSize = {false, false};
      uts->mSizes[eLogicalAxisInline].ClearAndRetainStorage();
      uts->mSizes[eLogicalAxisBlock].ClearAndRetainStorage();
    }
  }

  // SubgridPlaceGridItems will set these if we find any subgrid items.
  aState.mFrame->RemoveStateBits(NS_STATE_GRID_HAS_COL_SUBGRID_ITEM |
                                 NS_STATE_GRID_HAS_ROW_SUBGRID_ITEM);

  // http://dev.w3.org/csswg/css-grid/#grid-definition
  // Initialize the end lines of the Explicit Grid (mExplicitGridCol[Row]End).
  // This is determined by the larger of the number of rows/columns defined
  // by 'grid-template-areas' and the 'grid-template-rows'/'-columns', plus one.
  // Also initialize the Implicit Grid (mGridCol[Row]End) to the same values.
  // Note that this is for a grid with a 1,1 origin.  We'll change that
  // to a 0,0 based grid after placing definite lines.
  const nsStylePosition* const gridStyle = aState.mGridStyle;
  const auto* areas = gridStyle->mGridTemplateAreas.IsNone()
                          ? nullptr
                          : &*gridStyle->mGridTemplateAreas.AsAreas();
  const LineNameMap* parentLineNameMap = nullptr;
  const LineRange* subgridRange = nullptr;
  bool subgridAxisIsSameDirection = true;
  if (!aState.mFrame->IsColSubgrid()) {
    aState.mColFunctions.InitRepeatTracks(
        gridStyle->mColumnGap, aSizes.mMin.ISize(aState.mWM),
        aSizes.mSize.ISize(aState.mWM), aSizes.mMax.ISize(aState.mWM));
    uint32_t areaCols = areas ? areas->width + 1 : 1;
    mExplicitGridColEnd = aState.mColFunctions.ComputeExplicitGridEnd(areaCols);
  } else {
    const auto* subgrid = aState.mFrame->GetProperty(Subgrid::Prop());
    subgridRange = &subgrid->SubgridCols();
    uint32_t extent = subgridRange->Extent();
    mExplicitGridColEnd = extent + 1;  // the grid is 1-based at this point
    parentLineNameMap =
        ParentLineMapForAxis(subgrid->mIsOrthogonal, eLogicalAxisInline);
    auto parentWM =
        aState.mFrame->ParentGridContainerForSubgrid()->GetWritingMode();
    subgridAxisIsSameDirection =
        aState.mWM.ParallelAxisStartsOnSameSide(eLogicalAxisInline, parentWM);
  }
  mGridColEnd = mExplicitGridColEnd;
  LineNameMap colLineNameMap(gridStyle, mAreas, aState.mColFunctions,
                             parentLineNameMap, subgridRange,
                             subgridAxisIsSameDirection);

  if (!aState.mFrame->IsRowSubgrid()) {
    aState.mRowFunctions.InitRepeatTracks(
        gridStyle->mRowGap, aSizes.mMin.BSize(aState.mWM),
        aSizes.mSize.BSize(aState.mWM), aSizes.mMax.BSize(aState.mWM));
    uint32_t areaRows = areas ? areas->strings.Length() + 1 : 1;
    mExplicitGridRowEnd = aState.mRowFunctions.ComputeExplicitGridEnd(areaRows);
    parentLineNameMap = nullptr;
    subgridRange = nullptr;
  } else {
    const auto* subgrid = aState.mFrame->GetProperty(Subgrid::Prop());
    subgridRange = &subgrid->SubgridRows();
    uint32_t extent = subgridRange->Extent();
    mExplicitGridRowEnd = extent + 1;  // the grid is 1-based at this point
    parentLineNameMap =
        ParentLineMapForAxis(subgrid->mIsOrthogonal, eLogicalAxisBlock);
    auto parentWM =
        aState.mFrame->ParentGridContainerForSubgrid()->GetWritingMode();
    subgridAxisIsSameDirection =
        aState.mWM.ParallelAxisStartsOnSameSide(eLogicalAxisBlock, parentWM);
  }
  mGridRowEnd = mExplicitGridRowEnd;
  LineNameMap rowLineNameMap(gridStyle, mAreas, aState.mRowFunctions,
                             parentLineNameMap, subgridRange,
                             subgridAxisIsSameDirection);

  const bool isSubgridOrItemInSubgrid =
      aState.mFrame->IsSubgrid() || !!mParentGrid;
  auto SetSubgridChildEdgeBits =
      [this, isSubgridOrItemInSubgrid](GridItemInfo& aItem) -> void {
    if (isSubgridOrItemInSubgrid) {
      const auto& area = aItem.mArea;
      if (area.mCols.mStart == 0) {
        aItem.mState[eLogicalAxisInline] |= ItemState::eStartEdge;
      }
      if (area.mCols.mEnd == mGridColEnd) {
        aItem.mState[eLogicalAxisInline] |= ItemState::eEndEdge;
      }
      if (area.mRows.mStart == 0) {
        aItem.mState[eLogicalAxisBlock] |= ItemState::eStartEdge;
      }
      if (area.mRows.mEnd == mGridRowEnd) {
        aItem.mState[eLogicalAxisBlock] |= ItemState::eEndEdge;
      }
    }
  };

  SetLineMaps(&colLineNameMap, &rowLineNameMap);

  // http://dev.w3.org/csswg/css-grid/#line-placement
  // Resolve definite positions per spec chap 9.2.
  int32_t minCol = 1;
  int32_t minRow = 1;
  aState.mGridItems.ClearAndRetainStorage();
  aState.mIter.Reset();
  for (; !aState.mIter.AtEnd(); aState.mIter.Next()) {
    nsIFrame* child = *aState.mIter;
    GridItemInfo* info = aState.mGridItems.AppendElement(GridItemInfo(
        child,
        PlaceDefinite(child, colLineNameMap, rowLineNameMap, gridStyle)));
    MOZ_ASSERT(aState.mIter.ItemIndex() == aState.mGridItems.Length() - 1,
               "ItemIndex() is broken");
    GridArea& area = info->mArea;
    if (area.mCols.IsDefinite()) {
      minCol = std::min(minCol, area.mCols.mUntranslatedStart);
    }
    if (area.mRows.IsDefinite()) {
      minRow = std::min(minRow, area.mRows.mUntranslatedStart);
    }
  }

  // Translate the whole grid so that the top-/left-most area is at 0,0.
  mExplicitGridOffsetCol = 1 - minCol;  // minCol/Row is always <= 1, see above
  mExplicitGridOffsetRow = 1 - minRow;
  aState.mColFunctions.mExplicitGridOffset = mExplicitGridOffsetCol;
  aState.mRowFunctions.mExplicitGridOffset = mExplicitGridOffsetRow;
  const int32_t offsetToColZero = int32_t(mExplicitGridOffsetCol) - 1;
  const int32_t offsetToRowZero = int32_t(mExplicitGridOffsetRow) - 1;
  const bool isRowMasonry = aState.mFrame->IsMasonry(eLogicalAxisBlock);
  const bool isColMasonry = aState.mFrame->IsMasonry(eLogicalAxisInline);
  const bool isMasonry = isColMasonry || isRowMasonry;
  mGridColEnd += offsetToColZero;
  mGridRowEnd += offsetToRowZero;
  const uint32_t gridAxisTrackCount = isRowMasonry ? mGridColEnd : mGridRowEnd;
  aState.mIter.Reset();
  for (; !aState.mIter.AtEnd(); aState.mIter.Next()) {
    auto& item = aState.mGridItems[aState.mIter.ItemIndex()];
    GridArea& area = item.mArea;
    if (area.mCols.IsDefinite()) {
      area.mCols.mStart = area.mCols.mUntranslatedStart + offsetToColZero;
      area.mCols.mEnd = area.mCols.mUntranslatedEnd + offsetToColZero;
    }
    if (area.mRows.IsDefinite()) {
      area.mRows.mStart = area.mRows.mUntranslatedStart + offsetToRowZero;
      area.mRows.mEnd = area.mRows.mUntranslatedEnd + offsetToRowZero;
    }
    if (area.IsDefinite()) {
      if (isMasonry) {
        item.MaybeInhibitSubgridInMasonry(aState.mFrame, gridAxisTrackCount);
      }
      if (item.IsSubgrid()) {
        Grid grid(this);
        grid.SubgridPlaceGridItems(aState, this, item);
      }
      mCellMap.Fill(area);
      InflateGridFor(area);
      SetSubgridChildEdgeBits(item);
    }
  }

  // http://dev.w3.org/csswg/css-grid/#auto-placement-algo
  // Step 1, place 'auto' items that have one definite position -
  // definite row (column) for grid-auto-flow:row (column).
  auto flowStyle = gridStyle->mGridAutoFlow;
  const bool isRowOrder =
      isMasonry ? isRowMasonry : !!(flowStyle & StyleGridAutoFlow::ROW);
  const bool isSparse = !(flowStyle & StyleGridAutoFlow::DENSE);
  uint32_t clampMaxColLine = colLineNameMap.mClampMaxLine + offsetToColZero;
  uint32_t clampMaxRowLine = rowLineNameMap.mClampMaxLine + offsetToRowZero;
  // We need 1 cursor per row (or column) if placement is sparse.
  {
    Maybe<nsTHashMap<nsUint32HashKey, uint32_t>> cursors;
    if (isSparse) {
      cursors.emplace();
    }
    auto placeAutoMinorFunc =
        isRowOrder ? &Grid::PlaceAutoCol : &Grid::PlaceAutoRow;
    uint32_t clampMaxLine = isRowOrder ? clampMaxColLine : clampMaxRowLine;
    aState.mIter.Reset();
    for (; !aState.mIter.AtEnd(); aState.mIter.Next()) {
      auto& item = aState.mGridItems[aState.mIter.ItemIndex()];
      GridArea& area = item.mArea;
      LineRange& major = isRowOrder ? area.mRows : area.mCols;
      LineRange& minor = isRowOrder ? area.mCols : area.mRows;
      if (major.IsDefinite() && minor.IsAuto()) {
        // Items with 'auto' in the minor dimension only.
        const uint32_t cursor = isSparse ? cursors->Get(major.mStart) : 0;
        (this->*placeAutoMinorFunc)(cursor, &area, clampMaxLine);
        if (isMasonry) {
          item.MaybeInhibitSubgridInMasonry(aState.mFrame, gridAxisTrackCount);
        }
        if (item.IsSubgrid()) {
          Grid grid(this);
          grid.SubgridPlaceGridItems(aState, this, item);
        }
        mCellMap.Fill(area);
        SetSubgridChildEdgeBits(item);
        if (isSparse) {
          cursors->InsertOrUpdate(major.mStart, minor.mEnd);
        }
      }
      InflateGridFor(area);  // Step 2, inflating for auto items too
    }
  }

  // XXX NOTE possible spec issue.
  // XXX It's unclear if the remaining major-dimension auto and
  // XXX auto in both dimensions should use the same cursor or not,
  // XXX https://www.w3.org/Bugs/Public/show_bug.cgi?id=16044
  // XXX seems to indicate it shouldn't.
  // XXX http://dev.w3.org/csswg/css-grid/#auto-placement-cursor
  // XXX now says it should (but didn't in earlier versions)

  // Step 3, place the remaining grid items
  uint32_t cursorMajor = 0;  // for 'dense' these two cursors will stay at 0,0
  uint32_t cursorMinor = 0;
  auto placeAutoMajorFunc =
      isRowOrder ? &Grid::PlaceAutoRow : &Grid::PlaceAutoCol;
  uint32_t clampMaxMajorLine = isRowOrder ? clampMaxRowLine : clampMaxColLine;
  aState.mIter.Reset();
  for (; !aState.mIter.AtEnd(); aState.mIter.Next()) {
    auto& item = aState.mGridItems[aState.mIter.ItemIndex()];
    GridArea& area = item.mArea;
    MOZ_ASSERT(*aState.mIter == item.mFrame,
               "iterator out of sync with aState.mGridItems");
    LineRange& major = isRowOrder ? area.mRows : area.mCols;
    LineRange& minor = isRowOrder ? area.mCols : area.mRows;
    if (major.IsAuto()) {
      if (minor.IsDefinite()) {
        // Items with 'auto' in the major dimension only.
        if (isSparse) {
          if (minor.mStart < cursorMinor) {
            ++cursorMajor;
          }
          cursorMinor = minor.mStart;
        }
        (this->*placeAutoMajorFunc)(cursorMajor, &area, clampMaxMajorLine);
        if (isSparse) {
          cursorMajor = major.mStart;
        }
      } else {
        // Items with 'auto' in both dimensions.
        if (isRowOrder) {
          PlaceAutoAutoInRowOrder(cursorMinor, cursorMajor, &area,
                                  clampMaxColLine, clampMaxRowLine);
        } else {
          PlaceAutoAutoInColOrder(cursorMajor, cursorMinor, &area,
                                  clampMaxColLine, clampMaxRowLine);
        }
        if (isSparse) {
          cursorMajor = major.mStart;
          cursorMinor = minor.mEnd;
#ifdef DEBUG
          uint32_t gridMajorEnd = isRowOrder ? mGridRowEnd : mGridColEnd;
          uint32_t gridMinorEnd = isRowOrder ? mGridColEnd : mGridRowEnd;
          MOZ_ASSERT(cursorMajor <= gridMajorEnd,
                     "we shouldn't need to place items further than 1 track "
                     "past the current end of the grid, in major dimension");
          MOZ_ASSERT(cursorMinor <= gridMinorEnd,
                     "we shouldn't add implicit minor tracks for auto/auto");
#endif
        }
      }
      if (isMasonry) {
        item.MaybeInhibitSubgridInMasonry(aState.mFrame, gridAxisTrackCount);
      }
      if (item.IsSubgrid()) {
        Grid grid(this);
        grid.SubgridPlaceGridItems(aState, this, item);
      }
      mCellMap.Fill(area);
      InflateGridFor(area);
      SetSubgridChildEdgeBits(item);
      // XXXmats it might be possible to optimize this a bit for masonry layout
      // if this item was placed in the 2nd row && !isSparse, or the 1st row
      // is full.  Still gotta inflate the grid for all items though to make
      // the grid large enough...
    }
  }

  // Force all items into the 1st/2nd track and have span 1 in the masonry axis.
  // (See comment on nsGridContainerFrame::MasonryLayout().)
  if (isMasonry) {
    auto masonryAxis = isRowMasonry ? eLogicalAxisBlock : eLogicalAxisInline;
    aState.mIter.Reset();
    for (; !aState.mIter.AtEnd(); aState.mIter.Next()) {
      auto& item = aState.mGridItems[aState.mIter.ItemIndex()];
      auto& masonryRange = item.mArea.LineRangeForAxis(masonryAxis);
      masonryRange.mStart = std::min(masonryRange.mStart, 1U);
      masonryRange.mEnd = masonryRange.mStart + 1U;
    }
  }

  if (aState.mFrame->IsAbsoluteContainer()) {
    // 9.4 Absolutely-positioned Grid Items
    // http://dev.w3.org/csswg/css-grid/#abspos-items
    // We only resolve definite lines here; we'll align auto positions to the
    // grid container later during reflow.
    nsFrameList children(
        aState.mFrame->GetChildList(aState.mFrame->GetAbsoluteListID()));
    const int32_t offsetToColZero = int32_t(mExplicitGridOffsetCol) - 1;
    const int32_t offsetToRowZero = int32_t(mExplicitGridOffsetRow) - 1;
    // Untranslate the grid again temporarily while resolving abs.pos. lines.
    AutoRestore<uint32_t> zeroOffsetGridColEnd(mGridColEnd);
    AutoRestore<uint32_t> zeroOffsetGridRowEnd(mGridRowEnd);
    mGridColEnd -= offsetToColZero;
    mGridRowEnd -= offsetToRowZero;
    aState.mAbsPosItems.ClearAndRetainStorage();
    size_t i = 0;
    for (nsFrameList::Enumerator e(children); !e.AtEnd(); e.Next(), ++i) {
      nsIFrame* child = e.get();
      GridItemInfo* info = aState.mAbsPosItems.AppendElement(GridItemInfo(
          child,
          PlaceAbsPos(child, colLineNameMap, rowLineNameMap, gridStyle)));
      GridArea& area = info->mArea;
      if (area.mCols.mUntranslatedStart != int32_t(kAutoLine)) {
        area.mCols.mStart = area.mCols.mUntranslatedStart + offsetToColZero;
        if (isColMasonry) {
          // XXXmats clamp any non-auto line to 0 or 1. This is intended to
          // allow authors to address the start/end of the masonry box.
          // This is experimental at this point though and needs author feedback
          // and spec work to sort out what is desired and how it should work.
          // See https://github.com/w3c/csswg-drafts/issues/4650
          area.mCols.mStart = std::min(area.mCols.mStart, 1U);
        }
      }
      if (area.mCols.mUntranslatedEnd != int32_t(kAutoLine)) {
        area.mCols.mEnd = area.mCols.mUntranslatedEnd + offsetToColZero;
        if (isColMasonry) {
          // ditto
          area.mCols.mEnd = std::min(area.mCols.mEnd, 1U);
        }
      }
      if (area.mRows.mUntranslatedStart != int32_t(kAutoLine)) {
        area.mRows.mStart = area.mRows.mUntranslatedStart + offsetToRowZero;
        if (isRowMasonry) {
          // ditto
          area.mRows.mStart = std::min(area.mRows.mStart, 1U);
        }
      }
      if (area.mRows.mUntranslatedEnd != int32_t(kAutoLine)) {
        area.mRows.mEnd = area.mRows.mUntranslatedEnd + offsetToRowZero;
        if (isRowMasonry) {
          // ditto
          area.mRows.mEnd = std::min(area.mRows.mEnd, 1U);
        }
      }
      if (isMasonry) {
        info->MaybeInhibitSubgridInMasonry(aState.mFrame, gridAxisTrackCount);
      }

      // An abs.pos. subgrid with placement auto/1 or -1/auto technically
      // doesn't span any parent tracks.  Inhibit subgridding in this case.
      if (info->IsSubgrid(eLogicalAxisInline)) {
        if (info->mArea.mCols.mStart == zeroOffsetGridColEnd.SavedValue() ||
            info->mArea.mCols.mEnd == 0) {
          info->InhibitSubgrid(aState.mFrame, eLogicalAxisInline);
        }
      }
      if (info->IsSubgrid(eLogicalAxisBlock)) {
        if (info->mArea.mRows.mStart == zeroOffsetGridRowEnd.SavedValue() ||
            info->mArea.mRows.mEnd == 0) {
          info->InhibitSubgrid(aState.mFrame, eLogicalAxisBlock);
        }
      }

      if (info->IsSubgrid()) {
        Grid grid(this);
        grid.SubgridPlaceGridItems(aState, this, *info);
      }
    }
  }

  // Count empty 'auto-fit' tracks in the repeat() range.
  // |colAdjust| will have a count for each line in the grid of how many
  // tracks were empty between the start of the grid and that line.

  Maybe<nsTArray<uint32_t>> colAdjust;
  uint32_t numEmptyCols = 0;
  if (aState.mColFunctions.mHasRepeatAuto &&
      gridStyle->mGridTemplateColumns.GetRepeatAutoValue()->count.IsAutoFit()) {
    const auto& cellMap = mCellMap;
    colAdjust = CalculateAdjustForAutoFitElements(
        &numEmptyCols, aState.mColFunctions, mGridColEnd + 1,
        [&cellMap](uint32_t i) -> bool { return cellMap.IsEmptyCol(i); });
  }

  // Do similar work for the row tracks, with the same logic.
  Maybe<nsTArray<uint32_t>> rowAdjust;
  uint32_t numEmptyRows = 0;
  if (aState.mRowFunctions.mHasRepeatAuto &&
      gridStyle->mGridTemplateRows.GetRepeatAutoValue()->count.IsAutoFit()) {
    const auto& cellMap = mCellMap;
    rowAdjust = CalculateAdjustForAutoFitElements(
        &numEmptyRows, aState.mRowFunctions, mGridRowEnd + 1,
        [&cellMap](uint32_t i) -> bool { return cellMap.IsEmptyRow(i); });
  }
  MOZ_ASSERT((numEmptyCols > 0) == colAdjust.isSome());
  MOZ_ASSERT((numEmptyRows > 0) == rowAdjust.isSome());
  // Remove the empty 'auto-fit' tracks we found above, if any.
  if (numEmptyCols || numEmptyRows) {
    // Adjust the line numbers in the grid areas.
    for (auto& item : aState.mGridItems) {
      if (numEmptyCols) {
        item.AdjustForRemovedTracks(eLogicalAxisInline, *colAdjust);
      }
      if (numEmptyRows) {
        item.AdjustForRemovedTracks(eLogicalAxisBlock, *rowAdjust);
      }
    }
    for (auto& item : aState.mAbsPosItems) {
      if (numEmptyCols) {
        item.AdjustForRemovedTracks(eLogicalAxisInline, *colAdjust);
      }
      if (numEmptyRows) {
        item.AdjustForRemovedTracks(eLogicalAxisBlock, *rowAdjust);
      }
    }
    // Adjust the grid size.
    mGridColEnd -= numEmptyCols;
    mExplicitGridColEnd -= numEmptyCols;
    mGridRowEnd -= numEmptyRows;
    mExplicitGridRowEnd -= numEmptyRows;
    // Adjust the track mapping to unmap the removed tracks.
    auto colRepeatCount = aState.mColFunctions.NumRepeatTracks();
    aState.mColFunctions.SetNumRepeatTracks(colRepeatCount - numEmptyCols);
    auto rowRepeatCount = aState.mRowFunctions.NumRepeatTracks();
    aState.mRowFunctions.SetNumRepeatTracks(rowRepeatCount - numEmptyRows);
  }

  // Update the line boundaries of the implicit grid areas, if needed.
  if (mAreas && aState.mFrame->ShouldGenerateComputedInfo()) {
    for (auto iter = mAreas->iter(); !iter.done(); iter.next()) {
      auto& areaInfo = iter.get().value();

      // Resolve the lines for the area. We use the name of the area as the
      // name of the lines, knowing that the line placement algorithm will
      // add the -start and -end suffixes as appropriate for layout.
      StyleGridLine lineStartAndEnd;
      lineStartAndEnd.ident = areaInfo.name;

      LineRange columnLines =
          ResolveLineRange(lineStartAndEnd, lineStartAndEnd, colLineNameMap,
                           eLogicalAxisInline, mExplicitGridColEnd, gridStyle);

      LineRange rowLines =
          ResolveLineRange(lineStartAndEnd, lineStartAndEnd, rowLineNameMap,
                           eLogicalAxisBlock, mExplicitGridRowEnd, gridStyle);

      // Put the resolved line indices back into the area structure.
      areaInfo.columns.start = columnLines.mStart + mExplicitGridOffsetCol;
      areaInfo.columns.end = columnLines.mEnd + mExplicitGridOffsetCol;
      areaInfo.rows.start = rowLines.mStart + mExplicitGridOffsetRow;
      areaInfo.rows.end = rowLines.mEnd + mExplicitGridOffsetRow;
    }
  }
}

void nsGridContainerFrame::Tracks::Initialize(
    const TrackSizingFunctions& aFunctions,
    const NonNegativeLengthPercentageOrNormal& aGridGap, uint32_t aNumTracks,
    nscoord aContentBoxSize) {
  mSizes.SetLength(aNumTracks);
  PodZero(mSizes.Elements(), mSizes.Length());
  for (uint32_t i = 0, len = mSizes.Length(); i < len; ++i) {
    auto& sz = mSizes[i];
    mStateUnion |= sz.Initialize(aContentBoxSize, aFunctions.SizingFor(i));
    if (mIsMasonry) {
      sz.mBase = aContentBoxSize;
      sz.mLimit = aContentBoxSize;
    }
  }
  mGridGap = nsLayoutUtils::ResolveGapToLength(aGridGap, aContentBoxSize);
  mContentBoxSize = aContentBoxSize;
}

/**
 * Reflow aChild in the given aAvailableSize.
 */
static nscoord MeasuringReflow(nsIFrame* aChild,
                               const ReflowInput* aReflowInput, gfxContext* aRC,
                               const LogicalSize& aAvailableSize,
                               const LogicalSize& aCBSize,
                               nscoord aIMinSizeClamp = NS_MAXSIZE,
                               nscoord aBMinSizeClamp = NS_MAXSIZE) {
  nsContainerFrame* parent = aChild->GetParent();
  nsPresContext* pc = aChild->PresContext();
  Maybe<ReflowInput> dummyParentState;
  const ReflowInput* rs = aReflowInput;
  if (!aReflowInput) {
    MOZ_ASSERT(!parent->HasAnyStateBits(NS_FRAME_IN_REFLOW));
    dummyParentState.emplace(
        pc, parent, aRC,
        LogicalSize(parent->GetWritingMode(), 0, NS_UNCONSTRAINEDSIZE),
        ReflowInput::InitFlag::DummyParentReflowInput);
    rs = dummyParentState.ptr();
  }
#ifdef DEBUG
  // This will suppress various ABSURD_SIZE warnings for this reflow.
  parent->SetProperty(nsContainerFrame::DebugReflowingWithInfiniteISize(),
                      true);
#endif
  auto wm = aChild->GetWritingMode();
  ComputeSizeFlags csFlags = ComputeSizeFlag::UseAutoBSize;
  if (aAvailableSize.ISize(wm) == INFINITE_ISIZE_COORD) {
    csFlags += ComputeSizeFlag::ShrinkWrap;
  }
  if (aIMinSizeClamp != NS_MAXSIZE) {
    csFlags += ComputeSizeFlag::IClampMarginBoxMinSize;
  }
  if (aBMinSizeClamp != NS_MAXSIZE) {
    csFlags += ComputeSizeFlag::BClampMarginBoxMinSize;
    aChild->SetProperty(nsIFrame::BClampMarginBoxMinSizeProperty(),
                        aBMinSizeClamp);
  } else {
    aChild->RemoveProperty(nsIFrame::BClampMarginBoxMinSizeProperty());
  }
  ReflowInput childRI(pc, *rs, aChild, aAvailableSize, Some(aCBSize), {}, {},
                      csFlags);

  // Because we pass ComputeSizeFlag::UseAutoBSize, and the
  // previous reflow of the child might not have, set the child's
  // block-resize flag to true.
  // FIXME (perf): It would be faster to do this only if the previous
  // reflow of the child was not a measuring reflow, and only if the
  // child does some of the things that are affected by
  // ComputeSizeFlag::UseAutoBSize.
  childRI.SetBResize(true);
  // Not 100% sure this is needed, but be conservative for now:
  childRI.mFlags.mIsBResizeForPercentages = true;

  ReflowOutput childSize(childRI);
  nsReflowStatus childStatus;
  const nsIFrame::ReflowChildFlags flags =
      nsIFrame::ReflowChildFlags::NoMoveFrame |
      nsIFrame::ReflowChildFlags::NoSizeView |
      nsIFrame::ReflowChildFlags::NoDeleteNextInFlowChild;
  parent->ReflowChild(aChild, pc, childSize, childRI, wm, LogicalPoint(wm),
                      nsSize(), flags, childStatus);
  nsContainerFrame::FinishReflowChild(aChild, pc, childSize, &childRI, wm,
                                      LogicalPoint(wm), nsSize(), flags);
#ifdef DEBUG
  parent->RemoveProperty(nsContainerFrame::DebugReflowingWithInfiniteISize());
#endif
  return childSize.BSize(wm);
}

/**
 * Reflow aChild in the given aAvailableSize, using aNewContentBoxSize as its
 * computed size in aChildAxis.
 */
static void PostReflowStretchChild(
    nsIFrame* aChild, const ReflowInput& aReflowInput,
    const LogicalSize& aAvailableSize, const LogicalSize& aCBSize,
    LogicalAxis aChildAxis, const nscoord aNewContentBoxSize,
    nscoord aIMinSizeClamp = NS_MAXSIZE, nscoord aBMinSizeClamp = NS_MAXSIZE) {
  nsPresContext* pc = aChild->PresContext();
  ComputeSizeFlags csFlags;
  if (aIMinSizeClamp != NS_MAXSIZE) {
    csFlags += ComputeSizeFlag::IClampMarginBoxMinSize;
  }
  if (aBMinSizeClamp != NS_MAXSIZE) {
    csFlags += ComputeSizeFlag::BClampMarginBoxMinSize;
    aChild->SetProperty(nsIFrame::BClampMarginBoxMinSizeProperty(),
                        aBMinSizeClamp);
  } else {
    aChild->RemoveProperty(nsIFrame::BClampMarginBoxMinSizeProperty());
  }
  ReflowInput ri(pc, aReflowInput, aChild, aAvailableSize, Some(aCBSize), {},
                 {}, csFlags);
  if (aChildAxis == eLogicalAxisBlock) {
    ri.SetComputedBSize(ri.ApplyMinMaxBSize(aNewContentBoxSize));
  } else {
    ri.SetComputedISize(ri.ApplyMinMaxISize(aNewContentBoxSize));
  }
  ReflowOutput childSize(ri);
  nsReflowStatus childStatus;
  const nsIFrame::ReflowChildFlags flags =
      nsIFrame::ReflowChildFlags::NoMoveFrame |
      nsIFrame::ReflowChildFlags::NoDeleteNextInFlowChild;
  auto wm = aChild->GetWritingMode();
  nsContainerFrame* parent = aChild->GetParent();
  parent->ReflowChild(aChild, pc, childSize, ri, wm, LogicalPoint(wm), nsSize(),
                      flags, childStatus);
  nsContainerFrame::FinishReflowChild(aChild, pc, childSize, &ri, wm,
                                      LogicalPoint(wm), nsSize(), flags);
}

/**
 * Return the accumulated margin+border+padding in aAxis for aFrame (a subgrid)
 * and its ancestor subgrids.
 */
static LogicalMargin SubgridAccumulatedMarginBorderPadding(
    nsIFrame* aFrame, const Subgrid* aSubgrid, WritingMode aResultWM,
    LogicalAxis aAxis) {
  MOZ_ASSERT(aFrame->IsGridContainerFrame());
  auto* subgridFrame = static_cast<nsGridContainerFrame*>(aFrame);
  LogicalMargin result(aSubgrid->mMarginBorderPadding);
  auto* parent = subgridFrame->ParentGridContainerForSubgrid();
  auto subgridCBWM = parent->GetWritingMode();
  auto childRange = aSubgrid->mArea.LineRangeForAxis(aAxis);
  bool skipStartSide = false;
  bool skipEndSide = false;
  auto axis = aSubgrid->mIsOrthogonal ? GetOrthogonalAxis(aAxis) : aAxis;
  // If aFrame's parent is also a subgrid, then add its MBP on the edges that
  // are adjacent (i.e. start or end in the same track), recursively.
  // ("parent" refers to the grid-frame we're currently adding MBP for,
  // and "grandParent" its parent, as we walk up the chain.)
  while (parent->IsSubgrid(axis)) {
    auto* parentSubgrid = parent->GetProperty(Subgrid::Prop());
    auto* grandParent = parent->ParentGridContainerForSubgrid();
    auto parentCBWM = grandParent->GetWritingMode();
    if (parentCBWM.IsOrthogonalTo(subgridCBWM)) {
      axis = GetOrthogonalAxis(axis);
    }
    const auto& parentRange = parentSubgrid->mArea.LineRangeForAxis(axis);
    bool sameDir = parentCBWM.ParallelAxisStartsOnSameSide(axis, subgridCBWM);
    if (sameDir) {
      skipStartSide |= childRange.mStart != 0;
      skipEndSide |= childRange.mEnd != parentRange.Extent();
    } else {
      skipEndSide |= childRange.mStart != 0;
      skipStartSide |= childRange.mEnd != parentRange.Extent();
    }
    if (skipStartSide && skipEndSide) {
      break;
    }
    auto mbp =
        parentSubgrid->mMarginBorderPadding.ConvertTo(subgridCBWM, parentCBWM);
    if (skipStartSide) {
      mbp.Start(aAxis, subgridCBWM) = nscoord(0);
    }
    if (skipEndSide) {
      mbp.End(aAxis, subgridCBWM) = nscoord(0);
    }
    result += mbp;
    parent = grandParent;
    childRange = parentRange;
  }
  return result.ConvertTo(aResultWM, subgridCBWM);
}

/**
 * Return the [min|max]-content contribution of aChild to its parent (i.e.
 * the child's margin-box) in aAxis.
 */
static nscoord ContentContribution(
    const GridItemInfo& aGridItem, const GridReflowInput& aState,
    gfxContext* aRC, WritingMode aCBWM, LogicalAxis aAxis,
    const Maybe<LogicalSize>& aPercentageBasis, IntrinsicISizeType aConstraint,
    nscoord aMinSizeClamp = NS_MAXSIZE, uint32_t aFlags = 0) {
  nsIFrame* child = aGridItem.mFrame;

  nscoord extraMargin = 0;
  nsGridContainerFrame::Subgrid* subgrid = nullptr;
  if (child->GetParent() != aState.mFrame) {
    // |child| is a subgrid descendant, so it contributes its subgrids'
    // margin+border+padding for any edge tracks that it spans.
    auto* subgridFrame = child->GetParent();
    subgrid = subgridFrame->GetProperty(Subgrid::Prop());
    const auto itemEdgeBits = aGridItem.mState[aAxis] & ItemState::eEdgeBits;
    if (itemEdgeBits) {
      LogicalMargin mbp = SubgridAccumulatedMarginBorderPadding(
          subgridFrame, subgrid, aCBWM, aAxis);
      if (itemEdgeBits & ItemState::eStartEdge) {
        extraMargin += mbp.Start(aAxis, aCBWM);
      }
      if (itemEdgeBits & ItemState::eEndEdge) {
        extraMargin += mbp.End(aAxis, aCBWM);
      }
    }
    // It also contributes (half of) the subgrid's gap on its edges (if any)
    // subtracted by the non-subgrid ancestor grid container's gap.
    // Note that this can also be negative since it's considered a margin.
    if (itemEdgeBits != ItemState::eEdgeBits) {
      auto subgridAxis = aCBWM.IsOrthogonalTo(subgridFrame->GetWritingMode())
                             ? GetOrthogonalAxis(aAxis)
                             : aAxis;
      auto& gapStyle = subgridAxis == eLogicalAxisBlock
                           ? subgridFrame->StylePosition()->mRowGap
                           : subgridFrame->StylePosition()->mColumnGap;
      if (!gapStyle.IsNormal()) {
        auto subgridExtent = subgridAxis == eLogicalAxisBlock
                                 ? subgrid->mGridRowEnd
                                 : subgrid->mGridColEnd;
        if (subgridExtent > 1) {
          nscoord subgridGap =
              nsLayoutUtils::ResolveGapToLength(gapStyle, NS_UNCONSTRAINEDSIZE);
          auto& tracks =
              aAxis == eLogicalAxisBlock ? aState.mRows : aState.mCols;
          auto gapDelta = subgridGap - tracks.mGridGap;
          if (!itemEdgeBits) {
            extraMargin += gapDelta;
          } else {
            extraMargin += gapDelta / 2;
          }
        }
      }
    }
  }

  PhysicalAxis axis(aCBWM.PhysicalAxis(aAxis));
  nscoord size = nsLayoutUtils::IntrinsicForAxis(
      axis, aRC, child, aConstraint, aPercentageBasis,
      aFlags | nsLayoutUtils::BAIL_IF_REFLOW_NEEDED, aMinSizeClamp);
  auto childWM = child->GetWritingMode();
  const bool isOrthogonal = childWM.IsOrthogonalTo(aCBWM);
  auto childAxis = isOrthogonal ? GetOrthogonalAxis(aAxis) : aAxis;
  if (size == NS_INTRINSIC_ISIZE_UNKNOWN && childAxis == eLogicalAxisBlock) {
    // We need to reflow the child to find its BSize contribution.
    // XXX this will give mostly correct results for now (until bug 1174569).
    nscoord availISize = INFINITE_ISIZE_COORD;
    nscoord availBSize = NS_UNCONSTRAINEDSIZE;
    // The next two variables are MinSizeClamp values in the child's axes.
    nscoord iMinSizeClamp = NS_MAXSIZE;
    nscoord bMinSizeClamp = NS_MAXSIZE;
    LogicalSize cbSize(childWM, 0, NS_UNCONSTRAINEDSIZE);
    // Below, we try to resolve the child's grid-area size in its inline-axis
    // to use as the CB/Available size in the MeasuringReflow that follows.
    if (child->GetParent() != aState.mFrame) {
      // This item is a child of a subgrid descendant.
      auto* subgridFrame =
          static_cast<nsGridContainerFrame*>(child->GetParent());
      MOZ_ASSERT(subgridFrame->IsGridContainerFrame());
      auto* uts = subgridFrame->GetProperty(UsedTrackSizes::Prop());
      if (!uts) {
        uts = new UsedTrackSizes();
        subgridFrame->SetProperty(UsedTrackSizes::Prop(), uts);
      }
      // The grid-item's inline-axis as expressed in the subgrid's WM.
      auto subgridAxis = childWM.IsOrthogonalTo(subgridFrame->GetWritingMode())
                             ? eLogicalAxisBlock
                             : eLogicalAxisInline;
      uts->ResolveTrackSizesForAxis(subgridFrame, subgridAxis, *aRC);
      if (uts->mCanResolveLineRangeSize[subgridAxis]) {
        auto* subgrid =
            subgridFrame->GetProperty(nsGridContainerFrame::Subgrid::Prop());
        const GridItemInfo* originalItem = nullptr;
        for (const auto& item : subgrid->mGridItems) {
          if (item.mFrame == child) {
            originalItem = &item;
            break;
          }
        }
        MOZ_ASSERT(originalItem, "huh?");
        const auto& range = originalItem->mArea.LineRangeForAxis(subgridAxis);
        nscoord pos, sz;
        range.ToPositionAndLength(uts->mSizes[subgridAxis], &pos, &sz);
        if (childWM.IsOrthogonalTo(subgridFrame->GetWritingMode())) {
          availBSize = sz;
          cbSize.BSize(childWM) = sz;
          if (aGridItem.mState[aAxis] & ItemState::eClampMarginBoxMinSize) {
            bMinSizeClamp = sz;
          }
        } else {
          availISize = sz;
          cbSize.ISize(childWM) = sz;
          if (aGridItem.mState[aAxis] & ItemState::eClampMarginBoxMinSize) {
            iMinSizeClamp = sz;
          }
        }
      }
    } else if (aState.mCols.mCanResolveLineRangeSize