nsTableFrame.cpp

/* 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/. */

#include "nsTableFrame.h"

#include <algorithm>

#include "BasicTableLayoutStrategy.h"
#include "FixedTableLayoutStrategy.h"
#include "gfxContext.h"
#include "mozilla/ComputedStyle.h"
#include "mozilla/IntegerRange.h"
#include "mozilla/Likely.h"
#include "mozilla/PresShell.h"
#include "mozilla/PresShellInlines.h"
#include "mozilla/Range.h"
#include "mozilla/ReflowInput.h"
#include "mozilla/RestyleManager.h"
#include "mozilla/ServoStyleSet.h"
#include "mozilla/WritingModes.h"
#include "mozilla/gfx/2D.h"
#include "mozilla/gfx/Helpers.h"
#include "mozilla/layers/RenderRootStateManager.h"
#include "mozilla/layers/StackingContextHelper.h"
#include "nsCOMPtr.h"
#include "nsCSSFrameConstructor.h"
#include "nsCSSProps.h"
#include "nsCSSRendering.h"
#include "nsCellMap.h"
#include "nsContentUtils.h"
#include "nsDisplayList.h"
#include "nsError.h"
#include "nsFrameList.h"
#include "nsFrameManager.h"
#include "nsHTMLParts.h"
#include "nsIContent.h"
#include "nsIFrameInlines.h"
#include "nsIScriptError.h"
#include "nsLayoutUtils.h"
#include "nsPresContext.h"
#include "nsStyleChangeList.h"
#include "nsStyleConsts.h"
#include "nsTableCellFrame.h"
#include "nsTableColFrame.h"
#include "nsTableColGroupFrame.h"
#include "nsTableRowFrame.h"
#include "nsTableRowGroupFrame.h"
#include "nsTableWrapperFrame.h"

using namespace mozilla;
using namespace mozilla::image;
using namespace mozilla::layout;

using mozilla::gfx::AutoRestoreTransform;
using mozilla::gfx::DrawTarget;
using mozilla::gfx::Float;
using mozilla::gfx::ToDeviceColor;

namespace mozilla {

struct TableReflowInput final {
  TableReflowInput(const ReflowInput& aReflowInput,
                   const LogicalMargin& aBorderPadding, TableReflowMode aMode)
      : mReflowInput(aReflowInput),
        mWM(aReflowInput.GetWritingMode()),
        mAvailSize(mWM) {
    MOZ_ASSERT(mReflowInput.mFrame->IsTableFrame(),
               "TableReflowInput should only be created for nsTableFrame");
    auto* table = static_cast<nsTableFrame*>(mReflowInput.mFrame);

    mICoord = aBorderPadding.IStart(mWM) + table->GetColSpacing(-1);
    mAvailSize.ISize(mWM) =
        std::max(0, mReflowInput.ComputedISize() - table->GetColSpacing(-1) -
                        table->GetColSpacing(table->GetColCount()));

    mAvailSize.BSize(mWM) = aMode == TableReflowMode::Measuring
                                ? NS_UNCONSTRAINEDSIZE
                                : mReflowInput.AvailableBSize();
    AdvanceBCoord(aBorderPadding.BStart(mWM) +
                  (!table->GetPrevInFlow() ? table->GetRowSpacing(-1) : 0));
    if (aReflowInput.mStyleBorder->mBoxDecorationBreak ==
        StyleBoxDecorationBreak::Clone) {
      // At this point, we're assuming we won't be the last fragment, so we only
      // reserve space for block-end border-padding if we're cloning it on each
      // fragment; and we don't need to reserve any row-spacing for this
      // hypothetical fragmentation, either.
      ReduceAvailableBSizeBy(aBorderPadding.BEnd(mWM));
    }
  }

  // Advance to the next block-offset and reduce the available block-size.
  void AdvanceBCoord(nscoord aAmount) {
    mBCoord += aAmount;
    ReduceAvailableBSizeBy(aAmount);
  }

  const LogicalSize& AvailableSize() const { return mAvailSize; }

  // The real reflow input of the table frame.
  const ReflowInput& mReflowInput;

  // Stationary inline-offset, which won't change after the constructor.
  nscoord mICoord = 0;

  // Running block-offset, which will be adjusted as we reflow children.
  nscoord mBCoord = 0;

 private:
  void ReduceAvailableBSizeBy(nscoord aAmount) {
    if (mAvailSize.BSize(mWM) == NS_UNCONSTRAINEDSIZE) {
      return;
    }
    mAvailSize.BSize(mWM) -= aAmount;
    mAvailSize.BSize(mWM) = std::max(0, mAvailSize.BSize(mWM));
  }

  // mReflowInput's (i.e. table frame's) writing-mode.
  WritingMode mWM;

  // The available size for children. The inline-size is stationary after the
  // constructor, but the block-size will be adjusted as we reflow children.
  LogicalSize mAvailSize;
};

struct TableBCData final {
  TableArea mDamageArea;
  nscoord mBStartBorderWidth = 0;
  nscoord mIEndBorderWidth = 0;
  nscoord mBEndBorderWidth = 0;
  nscoord mIStartBorderWidth = 0;
};

}  // namespace mozilla

/********************************************************************************
 ** nsTableFrame **
 ********************************************************************************/

ComputedStyle* nsTableFrame::GetParentComputedStyle(
    nsIFrame** aProviderFrame) const {
  // Since our parent, the table wrapper frame, returned this frame, we
  // must return whatever our parent would normally have returned.

  MOZ_ASSERT(GetParent(), "table constructed without table wrapper");
  if (!mContent->GetParent() && !Style()->IsPseudoOrAnonBox()) {
    // We're the root.  We have no ComputedStyle parent.
    *aProviderFrame = nullptr;
    return nullptr;
  }

  return GetParent()->DoGetParentComputedStyle(aProviderFrame);
}

nsTableFrame::nsTableFrame(ComputedStyle* aStyle, nsPresContext* aPresContext,
                           ClassID aID)
    : nsContainerFrame(aStyle, aPresContext, aID) {
  memset(&mBits, 0, sizeof(mBits));
}

void nsTableFrame::Init(nsIContent* aContent, nsContainerFrame* aParent,
                        nsIFrame* aPrevInFlow) {
  MOZ_ASSERT(!mCellMap, "Init called twice");
  MOZ_ASSERT(!mTableLayoutStrategy, "Init called twice");
  MOZ_ASSERT(!aPrevInFlow || aPrevInFlow->IsTableFrame(),
             "prev-in-flow must be of same type");

  // Let the base class do its processing
  nsContainerFrame::Init(aContent, aParent, aPrevInFlow);

  // see if border collapse is on, if so set it
  const nsStyleTableBorder* tableStyle = StyleTableBorder();
  bool borderCollapse =
      (StyleBorderCollapse::Collapse == tableStyle->mBorderCollapse);
  SetBorderCollapse(borderCollapse);
  if (borderCollapse) {
    SetNeedToCalcHasBCBorders(true);
  }

  if (!aPrevInFlow) {
    // If we're the first-in-flow, we manage the cell map & layout strategy that
    // get used by our continuation chain:
    mCellMap = MakeUnique<nsTableCellMap>(*this, borderCollapse);
    if (IsAutoLayout()) {
      mTableLayoutStrategy = MakeUnique<BasicTableLayoutStrategy>(this);
    } else {
      mTableLayoutStrategy = MakeUnique<FixedTableLayoutStrategy>(this);
    }
  } else {
    // Set my isize, because all frames in a table flow are the same isize and
    // code in nsTableWrapperFrame depends on this being set.
    WritingMode wm = GetWritingMode();
    SetSize(LogicalSize(wm, aPrevInFlow->ISize(wm), BSize(wm)));
  }
}

// Define here (Rather than in the header), even if it's trival, to avoid
// UniquePtr members causing compile errors when their destructors are
// implicitly inserted into this destructor. Destruction requires
// the full definition of types that these UniquePtrs are managing, and
// the header only has forward declarations of them.
nsTableFrame::~nsTableFrame() = default;

void nsTableFrame::Destroy(DestroyContext& aContext) {
  MOZ_ASSERT(!mBits.mIsDestroying);
  mBits.mIsDestroying = true;
  nsContainerFrame::Destroy(aContext);
}

static bool IsRepeatedFrame(nsIFrame* kidFrame) {
  return (kidFrame->IsTableRowFrame() || kidFrame->IsTableRowGroupFrame()) &&
         kidFrame->HasAnyStateBits(NS_REPEATED_ROW_OR_ROWGROUP);
}

bool nsTableFrame::PageBreakAfter(nsIFrame* aSourceFrame,
                                  nsIFrame* aNextFrame) {
  const nsStyleDisplay* display = aSourceFrame->StyleDisplay();
  nsTableRowGroupFrame* prevRg = do_QueryFrame(aSourceFrame);
  // don't allow a page break after a repeated element ...
  if ((display->BreakAfter() || (prevRg && prevRg->HasInternalBreakAfter())) &&
      !IsRepeatedFrame(aSourceFrame)) {
    return !(aNextFrame && IsRepeatedFrame(aNextFrame));  // or before
  }

  if (aNextFrame) {
    display = aNextFrame->StyleDisplay();
    // don't allow a page break before a repeated element ...
    nsTableRowGroupFrame* nextRg = do_QueryFrame(aNextFrame);
    if ((display->BreakBefore() ||
         (nextRg && nextRg->HasInternalBreakBefore())) &&
        !IsRepeatedFrame(aNextFrame)) {
      return !IsRepeatedFrame(aSourceFrame);  // or after
    }
  }
  return false;
}

/* static */
void nsTableFrame::PositionedTablePartMaybeChanged(nsContainerFrame* aFrame,
                                                   ComputedStyle* aOldStyle) {
  const bool wasPositioned =
      aOldStyle && aOldStyle->IsAbsPosContainingBlock(aFrame);
  const bool isPositioned = aFrame->IsAbsPosContainingBlock();
  MOZ_ASSERT(isPositioned == aFrame->Style()->IsAbsPosContainingBlock(aFrame));
  if (wasPositioned == isPositioned) {
    return;
  }

  nsTableFrame* tableFrame = GetTableFrame(aFrame);
  MOZ_ASSERT(tableFrame, "Should have a table frame here");
  tableFrame = static_cast<nsTableFrame*>(tableFrame->FirstContinuation());

  // Retrieve the positioned parts array for this table (lazily creating it
  // if it doesn't exist yet).
  TablePartsArray* positionedParts =
      tableFrame->GetOrCreateDeletableProperty(PositionedTablePartsProperty());

  if (isPositioned) {
    // Add this frame to the list.
    positionedParts->AppendElement(aFrame);
  } else {
    positionedParts->RemoveElement(aFrame);
  }
}

/* static */
void nsTableFrame::MaybeUnregisterPositionedTablePart(
    nsContainerFrame* aFrame) {
  if (!aFrame->IsAbsPosContainingBlock()) {
    return;
  }
  nsTableFrame* tableFrame = GetTableFrame(aFrame);
  tableFrame = static_cast<nsTableFrame*>(tableFrame->FirstContinuation());

  if (tableFrame->IsDestroying()) {
    return;  // We're throwing the table away anyways.
  }

  // Retrieve the positioned parts array for this table.
  TablePartsArray* positionedParts =
      tableFrame->GetProperty(PositionedTablePartsProperty());

  // Remove the frame.
  MOZ_ASSERT(
      positionedParts && positionedParts->Contains(aFrame),
      "Asked to unregister a positioned table part that wasn't registered");
  if (positionedParts) {
    positionedParts->RemoveElement(aFrame);
  }
}

void nsTableFrame::SetInitialChildList(ChildListID aListID,
                                       nsFrameList&& aChildList) {
  nsContainerFrame::SetInitialChildList(aListID, std::move(aChildList));
  if (aListID != FrameChildListID::Principal) {
    return;
  }

  // If we have a prev-in-flow, then we're a table that has been split and
  // so don't treat this like an append
  if (!GetPrevInFlow()) {
    // process col groups first so that real cols get constructed before
    // anonymous ones due to cells in rows.
    InsertColGroups(0, mFrames);
    InsertRowGroups(mFrames);
    // calc collapsing borders
    if (IsBorderCollapse()) {
      SetFullBCDamageArea();
    }
  }
}

void nsTableFrame::RowOrColSpanChanged(nsTableCellFrame* aCellFrame) {
  if (!aCellFrame) {
    return;
  }
  nsTableCellMap* cellMap = GetCellMap();
  if (!cellMap) {
    return;
  }
  // for now just remove the cell from the map and reinsert it
  uint32_t rowIndex = aCellFrame->RowIndex();
  uint32_t colIndex = aCellFrame->ColIndex();
  RemoveCell(aCellFrame, rowIndex);
  AutoTArray<nsTableCellFrame*, 1> cells;
  cells.AppendElement(aCellFrame);
  InsertCells(cells, rowIndex, colIndex - 1);

  // XXX Should this use IntrinsicDirty::FrameAncestorsAndDescendants? It
  // currently doesn't need to, but it might given more optimization.
  PresShell()->FrameNeedsReflow(this, IntrinsicDirty::FrameAndAncestors,
                                NS_FRAME_IS_DIRTY);
}

/* ****** CellMap methods ******* */

/* return the effective col count */
int32_t nsTableFrame::GetEffectiveColCount() const {
  int32_t colCount = GetColCount();
  if (LayoutStrategy()->GetType() == nsITableLayoutStrategy::Auto) {
    nsTableCellMap* cellMap = GetCellMap();
    if (!cellMap) {
      return 0;
    }
    // don't count cols at the end that don't have originating cells
    for (int32_t colIdx = colCount - 1; colIdx >= 0; colIdx--) {
      if (cellMap->GetNumCellsOriginatingInCol(colIdx) > 0) {
        break;
      }
      colCount--;
    }
  }
  return colCount;
}

int32_t nsTableFrame::GetIndexOfLastRealCol() {
  int32_t numCols = mColFrames.Length();
  if (numCols > 0) {
    for (int32_t colIdx = numCols - 1; colIdx >= 0; colIdx--) {
      nsTableColFrame* colFrame = GetColFrame(colIdx);
      if (colFrame) {
        if (eColAnonymousCell != colFrame->GetColType()) {
          return colIdx;
        }
      }
    }
  }
  return -1;
}

nsTableColFrame* nsTableFrame::GetColFrame(int32_t aColIndex) const {
  MOZ_ASSERT(!GetPrevInFlow(), "GetColFrame called on next in flow");
  int32_t numCols = mColFrames.Length();
  if ((aColIndex >= 0) && (aColIndex < numCols)) {
    MOZ_ASSERT(mColFrames.ElementAt(aColIndex));
    return mColFrames.ElementAt(aColIndex);
  } else {
    MOZ_ASSERT_UNREACHABLE("invalid col index");
    return nullptr;
  }
}

int32_t nsTableFrame::GetEffectiveRowSpan(int32_t aRowIndex,
                                          const nsTableCellFrame& aCell) const {
  nsTableCellMap* cellMap = GetCellMap();
  MOZ_ASSERT(nullptr != cellMap, "bad call, cellMap not yet allocated.");

  return cellMap->GetEffectiveRowSpan(aRowIndex, aCell.ColIndex());
}

int32_t nsTableFrame::GetEffectiveRowSpan(const nsTableCellFrame& aCell,
                                          nsCellMap* aCellMap) {
  nsTableCellMap* tableCellMap = GetCellMap();
  if (!tableCellMap) ABORT1(1);

  uint32_t colIndex = aCell.ColIndex();
  uint32_t rowIndex = aCell.RowIndex();

  if (aCellMap) {
    return aCellMap->GetRowSpan(rowIndex, colIndex, true);
  }
  return tableCellMap->GetEffectiveRowSpan(rowIndex, colIndex);
}

int32_t nsTableFrame::GetEffectiveColSpan(const nsTableCellFrame& aCell,
                                          nsCellMap* aCellMap) const {
  nsTableCellMap* tableCellMap = GetCellMap();
  if (!tableCellMap) ABORT1(1);

  uint32_t colIndex = aCell.ColIndex();
  uint32_t rowIndex = aCell.RowIndex();

  if (aCellMap) {
    return aCellMap->GetEffectiveColSpan(*tableCellMap, rowIndex, colIndex);
  }
  return tableCellMap->GetEffectiveColSpan(rowIndex, colIndex);
}

bool nsTableFrame::HasMoreThanOneCell(int32_t aRowIndex) const {
  nsTableCellMap* tableCellMap = GetCellMap();
  if (!tableCellMap) ABORT1(1);
  return tableCellMap->HasMoreThanOneCell(aRowIndex);
}

void nsTableFrame::AdjustRowIndices(int32_t aRowIndex, int32_t aAdjustment) {
  // Iterate over the row groups and adjust the row indices of all rows
  // whose index is >= aRowIndex.
  for (nsTableRowGroupFrame* rg : OrderedGroups().mRowGroups) {
    rg->AdjustRowIndices(aRowIndex, aAdjustment);
  }
}

void nsTableFrame::ResetRowIndices(
    const nsFrameList::Slice& aRowGroupsToExclude) {
  // Iterate over the row groups and adjust the row indices of all rows
  // omit the rowgroups that will be inserted later
  mDeletedRowIndexRanges.clear();

  RowGroupArray rowGroups = OrderedRowGroups();

  nsTHashSet<nsTableRowGroupFrame*> excludeRowGroups;
  for (nsIFrame* excludeRowGroup : aRowGroupsToExclude) {
    if (nsTableRowGroupFrame* rg = do_QueryFrame(excludeRowGroup)) {
      excludeRowGroups.Insert(rg);
#ifdef DEBUG
      {
        // Check to make sure that the row indices of all rows in excluded row
        // groups are '0' (i.e. the initial value since they haven't been added
        // yet)
        const nsFrameList& rowFrames = excludeRowGroup->PrincipalChildList();
        for (nsIFrame* r : rowFrames) {
          auto* row = static_cast<nsTableRowFrame*>(r);
          MOZ_ASSERT(
              row->GetRowIndex() == 0,
              "exclusions cannot be used for rows that were already added,"
              "because we'd need to process mDeletedRowIndexRanges");
        }
      }
#endif
    }
  }

  int32_t rowIndex = 0;
  for (uint32_t rgIdx = 0; rgIdx < rowGroups.Length(); rgIdx++) {
    nsTableRowGroupFrame* rgFrame = rowGroups[rgIdx];
    if (!excludeRowGroups.Contains(rgFrame)) {
      const nsFrameList& rowFrames = rgFrame->PrincipalChildList();
      for (nsIFrame* r : rowFrames) {
        if (mozilla::StyleDisplay::TableRow == r->StyleDisplay()->mDisplay) {
          auto* row = static_cast<nsTableRowFrame*>(r);
          row->SetRowIndex(rowIndex);
          rowIndex++;
        }
      }
    }
  }
}

void nsTableFrame::InsertColGroups(int32_t aStartColIndex,
                                   const nsFrameList::Slice& aNewFrames) {
  auto colIndex = aStartColIndex;
  nsIFrame* lastFrame = nullptr;
  for (nsIFrame* f : aNewFrames) {
    lastFrame = f;
    nsTableColGroupFrame* cg = do_QueryFrame(f);
    if (!cg || cg->IsSynthetic()) {
      continue;
    }
    cg->SetStartColumnIndex(colIndex);
    cg->AddColsToTable(colIndex, false, cg->PrincipalChildList());
    int32_t numCols = cg->GetColCount();
    colIndex += numCols;
  }
  auto* next = lastFrame ? lastFrame->GetNextSibling() : nullptr;
  nsTableColGroupFrame::ResetColIndices(next, GetSyntheticColGroup(), colIndex);
#ifdef DEBUG
  VerifyColFrames();
#endif
}

void nsTableFrame::InsertCol(nsTableColFrame& aColFrame, int32_t aColIndex) {
  mColFrames.InsertElementAt(aColIndex, &aColFrame);
  nsTableColType insertedColType = aColFrame.GetColType();
  int32_t numCacheCols = mColFrames.Length();
  if (nsTableCellMap* cellMap = GetCellMap()) {
    int32_t numMapCols = cellMap->GetColCount();
    if (numCacheCols > numMapCols) {
      bool removedFromCache = false;
      if (eColAnonymousCell != insertedColType) {
        if (nsTableColFrame* lastCol = mColFrames.ElementAt(numCacheCols - 1)) {
          nsTableColType lastColType = lastCol->GetColType();
          if (eColAnonymousCell == lastColType) {
            // remove the col from the cache
            mColFrames.RemoveLastElement();
            if (mSyntheticColGroup) {
              MOZ_ASSERT(mSyntheticColGroup->IsSynthetic());
              DestroyContext context(PresShell());
              mSyntheticColGroup->RemoveChild(context, *lastCol, false);

              // remove the col group if it is empty
              if (mSyntheticColGroup->GetColCount() <= 0) {
                mFrames.DestroyFrame(context, mSyntheticColGroup);
                mSyntheticColGroup = nullptr;
              }
            }
            removedFromCache = true;
          }
        }
      }
      if (!removedFromCache) {
        cellMap->AddColsAtEnd(1);
      }
    }
  }
  // for now, just bail and recalc all of the collapsing borders
  if (IsBorderCollapse()) {
    TableArea damageArea(aColIndex, 0, GetColCount() - aColIndex,
                         GetRowCount());
    AddBCDamageArea(damageArea);
  }
}

void nsTableFrame::RemoveCol(int32_t aColIndex, bool aRemoveFromCache,
                             bool aRemoveFromCellMap) {
  if (aRemoveFromCache) {
    mColFrames.RemoveElementAt(aColIndex);
  }
  if (aRemoveFromCellMap) {
    nsTableCellMap* cellMap = GetCellMap();
    if (cellMap) {
      // If we have some anonymous cols at the end already, we just
      // add a new anonymous col.
      if (!mColFrames.IsEmpty() &&
          mColFrames.LastElement() &&  // XXXbz is this ever null?
          mColFrames.LastElement()->GetColType() == eColAnonymousCell) {
        AppendAnonymousColFrames(1);
      } else {
        // All of our colframes correspond to actual <col> tags.  It's possible
        // that we still have at least as many <col> tags as we have logical
        // columns from cells, but we might have one less.  Handle the latter
        // case as follows: First ask the cellmap to drop its last col if it
        // doesn't have any actual cells in it.  Then call
        // MatchCellMapToColCache to append an anonymous column if it's needed;
        // this needs to be after RemoveColsAtEnd, since it will determine the
        // need for a new column frame based on the width of the cell map.
        cellMap->RemoveColsAtEnd();
        MatchCellMapToColCache(cellMap);
      }
    }
  }
  // for now, just bail and recalc all of the collapsing borders
  if (IsBorderCollapse()) {
    SetFullBCDamageArea();
  }
}

/** Get the cell map for this table frame.  It is not always mCellMap.
 * Only the first-in-flow has a legit cell map.
 */
nsTableCellMap* nsTableFrame::GetCellMap() const {
  return static_cast<nsTableFrame*>(FirstInFlow())->mCellMap.get();
}

nsTableColGroupFrame* nsTableFrame::CreateSyntheticColGroupFrame() {
  nsIContent* colGroupContent = GetContent();
  mozilla::PresShell* presShell = PresShell();

  RefPtr<ComputedStyle> colGroupStyle;
  colGroupStyle = presShell->StyleSet()->ResolveNonInheritingAnonymousBoxStyle(
      PseudoStyleType::MozTableColumnGroup);
  // Create a col group frame
  nsTableColGroupFrame* newFrame =
      NS_NewTableColGroupFrame(presShell, colGroupStyle);
  newFrame->SetIsSynthetic();
  newFrame->Init(colGroupContent, this, nullptr);
  return newFrame;
}

int32_t nsTableFrame::GetRealColEnd() const {
  for (auto* col : Reversed(mColFrames)) {
    auto* cg = static_cast<nsTableColGroupFrame*>(col->GetParent());
    if (!cg->IsSynthetic()) {
      return col->GetColIndex() + 1;
    }
  }
  return 0;
}

static int32_t GetColStartAfter(nsIFrame* aPrevSibling) {
  for (nsIFrame* f = aPrevSibling; f; f = f->GetPrevSibling()) {
    if (nsTableColGroupFrame* cg = do_QueryFrame(f)) {
      if (!cg->IsSynthetic()) {
        return cg->GetStartColumnIndex() + cg->GetColCount();
      }
    }
  }
  return 0;
}

void nsTableFrame::AppendAnonymousColFrames(int32_t aNumColsToAdd) {
  MOZ_ASSERT(aNumColsToAdd > 0, "We should be adding _something_.");
  if (!mSyntheticColGroup) {
    int32_t colIndex = GetRealColEnd();
    mSyntheticColGroup = CreateSyntheticColGroupFrame();
    // add the new frame to the child list
    mFrames.AppendFrame(this, mSyntheticColGroup);
    mSyntheticColGroup->SetStartColumnIndex(colIndex);
  }
  AppendAnonymousColFrames(mSyntheticColGroup, aNumColsToAdd, eColAnonymousCell,
                           true);
}

// XXX this needs to be moved to nsCSSFrameConstructor
// Right now it only creates the col frames at the end
void nsTableFrame::AppendAnonymousColFrames(
    nsTableColGroupFrame* aColGroupFrame, int32_t aNumColsToAdd,
    nsTableColType aColType, bool aAddToTable) {
  MOZ_ASSERT(aColGroupFrame, "null frame");
  MOZ_ASSERT(aColType != eColAnonymousCol, "Shouldn't happen");
  MOZ_ASSERT(aNumColsToAdd > 0, "We should be adding _something_.");

  mozilla::PresShell* presShell = PresShell();

  // Get the last col frame
  nsFrameList newColFrames;

  int32_t startIndex = mColFrames.Length();
  int32_t lastIndex = startIndex + aNumColsToAdd - 1;

  for (int32_t childX = startIndex; childX <= lastIndex; childX++) {
    // all anonymous cols that we create here use a pseudo ComputedStyle of the
    // col group
    nsIContent* iContent = aColGroupFrame->GetContent();
    RefPtr<ComputedStyle> computedStyle =
        presShell->StyleSet()->ResolveNonInheritingAnonymousBoxStyle(
            PseudoStyleType::MozTableColumn);
    // ASSERTION to check for bug 54454 sneaking back in...
    NS_ASSERTION(iContent, "null content in CreateAnonymousColFrames");

    // create the new col frame
    nsIFrame* colFrame = NS_NewTableColFrame(presShell, computedStyle);
    ((nsTableColFrame*)colFrame)->SetColType(aColType);
    colFrame->Init(iContent, aColGroupFrame, nullptr);

    newColFrames.AppendFrame(nullptr, colFrame);
  }
  nsFrameList& cols = aColGroupFrame->GetWritableChildList();
  nsIFrame* oldLastCol = cols.LastChild();
  const nsFrameList::Slice& newCols =
      cols.InsertFrames(nullptr, oldLastCol, std::move(newColFrames));
  if (aAddToTable) {
    // get the starting col index in the cache
    int32_t startColIndex;
    if (oldLastCol) {
      startColIndex =
          static_cast<nsTableColFrame*>(oldLastCol)->GetColIndex() + 1;
    } else {
      startColIndex = aColGroupFrame->GetStartColumnIndex();
    }

    aColGroupFrame->AddColsToTable(startColIndex, true, newCols);
  }
}

void nsTableFrame::MatchCellMapToColCache(nsTableCellMap* aCellMap) {
  int32_t numColsInMap = GetColCount();
  int32_t numColsInCache = mColFrames.Length();
  int32_t numColsToAdd = numColsInMap - numColsInCache;
  if (numColsToAdd > 0) {
    // this sets the child list, updates the col cache and cell map
    AppendAnonymousColFrames(numColsToAdd);
  }
  if (numColsToAdd < 0) {
    int32_t numColsNotRemoved = DestroyAnonymousColFrames(-numColsToAdd);
    // if the cell map has fewer cols than the cache, correct it
    if (numColsNotRemoved > 0) {
      aCellMap->AddColsAtEnd(numColsNotRemoved);
    }
  }
}

void nsTableFrame::DidResizeColumns() {
  MOZ_ASSERT(!GetPrevInFlow(), "should only be called on first-in-flow");

  if (mBits.mResizedColumns) {
    return;  // already marked
  }

  for (nsTableFrame* f = this; f;
       f = static_cast<nsTableFrame*>(f->GetNextInFlow())) {
    f->mBits.mResizedColumns = true;
  }
}

void nsTableFrame::AppendCell(nsTableCellFrame& aCellFrame, int32_t aRowIndex) {
  nsTableCellMap* cellMap = GetCellMap();
  if (cellMap) {
    TableArea damageArea(0, 0, 0, 0);
    cellMap->AppendCell(aCellFrame, aRowIndex, true, damageArea);
    MatchCellMapToColCache(cellMap);
    if (IsBorderCollapse()) {
      AddBCDamageArea(damageArea);
    }
  }
}

void nsTableFrame::InsertCells(nsTArray<nsTableCellFrame*>& aCellFrames,
                               int32_t aRowIndex, int32_t aColIndexBefore) {
  nsTableCellMap* cellMap = GetCellMap();
  if (cellMap) {
    TableArea damageArea(0, 0, 0, 0);
    cellMap->InsertCells(aCellFrames, aRowIndex, aColIndexBefore, damageArea);
    MatchCellMapToColCache(cellMap);
    if (IsBorderCollapse()) {
      AddBCDamageArea(damageArea);
    }
  }
}

// this removes the frames from the col group and table, but not the cell map
int32_t nsTableFrame::DestroyAnonymousColFrames(int32_t aNumFrames) {
  // only remove cols that are of type eTypeAnonymous cell (they are at the end)
  int32_t endIndex = mColFrames.Length() - 1;
  int32_t startIndex = (endIndex - aNumFrames) + 1;
  int32_t numColsRemoved = 0;
  DestroyContext context(PresShell());
  for (int32_t colIdx = endIndex; colIdx >= startIndex; colIdx--) {
    nsTableColFrame* colFrame = GetColFrame(colIdx);
    if (colFrame && (eColAnonymousCell == colFrame->GetColType())) {
      auto* cgFrame = static_cast<nsTableColGroupFrame*>(colFrame->GetParent());
      // remove the frame from the colgroup
      cgFrame->RemoveChild(context, *colFrame, false);
      // remove the frame from the cache, but not the cell map
      RemoveCol(colIdx, true, false);
      numColsRemoved++;
    } else {
      break;
    }
  }
  return (aNumFrames - numColsRemoved);
}

void nsTableFrame::RemoveCell(nsTableCellFrame* aCellFrame, int32_t aRowIndex) {
  nsTableCellMap* cellMap = GetCellMap();
  if (cellMap) {
    TableArea damageArea(0, 0, 0, 0);
    cellMap->RemoveCell(aCellFrame, aRowIndex, damageArea);
    MatchCellMapToColCache(cellMap);
    if (IsBorderCollapse()) {
      AddBCDamageArea(damageArea);
    }
  }
}

int32_t nsTableFrame::GetStartRowIndex(
    const nsTableRowGroupFrame* aRowGroupFrame) const {
  RowGroupArray orderedRowGroups = OrderedRowGroups();

  int32_t rowIndex = 0;
  for (uint32_t rgIndex = 0; rgIndex < orderedRowGroups.Length(); rgIndex++) {
    nsTableRowGroupFrame* rgFrame = orderedRowGroups[rgIndex];
    if (rgFrame == aRowGroupFrame) {
      break;
    }
    int32_t numRows = rgFrame->GetRowCount();
    rowIndex += numRows;
  }
  return rowIndex;
}

// this cannot extend beyond a single row group
void nsTableFrame::AppendRows(nsTableRowGroupFrame* aRowGroupFrame,
                              int32_t aRowIndex,
                              nsTArray<nsTableRowFrame*>& aRowFrames) {
  nsTableCellMap* cellMap = GetCellMap();
  if (cellMap) {
    int32_t absRowIndex = GetStartRowIndex(aRowGroupFrame) + aRowIndex;
    InsertRows(aRowGroupFrame, aRowFrames, absRowIndex, true);
  }
}

// this cannot extend beyond a single row group
int32_t nsTableFrame::InsertRows(nsTableRowGroupFrame* aRowGroupFrame,
                                 nsTArray<nsTableRowFrame*>& aRowFrames,
                                 int32_t aRowIndex, bool aConsiderSpans) {
#ifdef DEBUG_TABLE_CELLMAP
  printf("=== insertRowsBefore firstRow=%d \n", aRowIndex);
  Dump(true, false, true);
#endif

  int32_t numColsToAdd = 0;
  nsTableCellMap* cellMap = GetCellMap();
  if (cellMap) {
    TableArea damageArea(0, 0, 0, 0);
    bool shouldRecalculateIndex = !IsDeletedRowIndexRangesEmpty();
    if (shouldRecalculateIndex) {
      ResetRowIndices(nsFrameList::Slice(nullptr, nullptr));
    }
    int32_t origNumRows = cellMap->GetRowCount();
    int32_t numNewRows = aRowFrames.Length();
    cellMap->InsertRows(aRowGroupFrame, aRowFrames, aRowIndex, aConsiderSpans,
                        damageArea);
    MatchCellMapToColCache(cellMap);

    // Perform row index adjustment only if row indices were not
    // reset above
    if (!shouldRecalculateIndex) {
      if (aRowIndex < origNumRows) {
        AdjustRowIndices(aRowIndex, numNewRows);
      }

      // assign the correct row indices to the new rows. If they were
      // recalculated above it may not have been done correctly because each row
      // is constructed with index 0
      for (int32_t rowB = 0; rowB < numNewRows; rowB++) {
        nsTableRowFrame* rowFrame = aRowFrames.ElementAt(rowB);
        rowFrame->SetRowIndex(aRowIndex + rowB);
      }
    }

    if (IsBorderCollapse()) {
      AddBCDamageArea(damageArea);
    }
  }
#ifdef DEBUG_TABLE_CELLMAP
  printf("=== insertRowsAfter \n");
  Dump(true, false, true);
#endif

  return numColsToAdd;
}

void nsTableFrame::AddDeletedRowIndex(int32_t aDeletedRowStoredIndex) {
  if (mDeletedRowIndexRanges.empty()) {
    mDeletedRowIndexRanges.insert(std::pair<int32_t, int32_t>(
        aDeletedRowStoredIndex, aDeletedRowStoredIndex));
    return;
  }

  // Find the position of the current deleted row's stored index
  // among the previous deleted row index ranges and merge ranges if
  // they are consecutive, else add a new (disjoint) range to the map.
  // Call to mDeletedRowIndexRanges.upper_bound is
  // O(log(mDeletedRowIndexRanges.size())) therefore call to
  // AddDeletedRowIndex is also ~O(log(mDeletedRowIndexRanges.size()))

  // greaterIter = will point to smallest range in the map with lower value
  //              greater than the aDeletedRowStoredIndex.
  //              If no such value exists, point to end of map.
  // smallerIter = will point to largest range in the map with higher value
  //              smaller than the aDeletedRowStoredIndex
  //              If no such value exists, point to beginning of map.
  // i.e. when both values exist below is true:
  // smallerIter->second < aDeletedRowStoredIndex < greaterIter->first
  auto greaterIter = mDeletedRowIndexRanges.upper_bound(aDeletedRowStoredIndex);
  auto smallerIter = greaterIter;

  if (smallerIter != mDeletedRowIndexRanges.begin()) {
    smallerIter--;
    // While greaterIter might be out-of-bounds (by being equal to end()),
    // smallerIter now cannot be, since we returned early above for a 0-size
    // map.
  }

  // Note: smallerIter can only be equal to greaterIter when both
  // of them point to the beginning of the map and in that case smallerIter
  // does not "exist" but we clip smallerIter to point to beginning of map
  // so that it doesn't point to something unknown or outside the map boundry.
  // Note: When greaterIter is not the end (i.e. it "exists") upper_bound()
  // ensures aDeletedRowStoredIndex < greaterIter->first so no need to
  // assert that.
  MOZ_ASSERT(smallerIter == greaterIter ||
                 aDeletedRowStoredIndex > smallerIter->second,
             "aDeletedRowIndexRanges already contains aDeletedRowStoredIndex! "
             "Trying to delete an already deleted row?");

  if (smallerIter->second == aDeletedRowStoredIndex - 1) {
    if (greaterIter != mDeletedRowIndexRanges.end() &&
        greaterIter->first == aDeletedRowStoredIndex + 1) {
      // merge current index with smaller and greater range as they are
      // consecutive
      smallerIter->second = greaterIter->second;
      mDeletedRowIndexRanges.erase(greaterIter);
    } else {
      // add aDeletedRowStoredIndex in the smaller range as it is consecutive
      smallerIter->second = aDeletedRowStoredIndex;
    }
  } else if (greaterIter != mDeletedRowIndexRanges.end() &&
             greaterIter->first == aDeletedRowStoredIndex + 1) {
    // add aDeletedRowStoredIndex in the greater range as it is consecutive
    mDeletedRowIndexRanges.insert(std::pair<int32_t, int32_t>(
        aDeletedRowStoredIndex, greaterIter->second));
    mDeletedRowIndexRanges.erase(greaterIter);
  } else {
    // add new range as aDeletedRowStoredIndex is disjoint from existing ranges
    mDeletedRowIndexRanges.insert(std::pair<int32_t, int32_t>(
        aDeletedRowStoredIndex, aDeletedRowStoredIndex));
  }
}

int32_t nsTableFrame::GetAdjustmentForStoredIndex(int32_t aStoredIndex) {
  if (mDeletedRowIndexRanges.empty()) {
    return 0;
  }

  int32_t adjustment = 0;

  // O(log(mDeletedRowIndexRanges.size()))
  auto endIter = mDeletedRowIndexRanges.upper_bound(aStoredIndex);
  for (auto iter = mDeletedRowIndexRanges.begin(); iter != endIter; ++iter) {
    adjustment += iter->second - iter->first + 1;
  }

  return adjustment;
}

// this cannot extend beyond a single row group
void nsTableFrame::RemoveRows(nsTableRowFrame& aFirstRowFrame,
                              int32_t aNumRowsToRemove, bool aConsiderSpans) {
#ifdef TBD_OPTIMIZATION
  // decide if we need to rebalance. we have to do this here because the row
  // group cannot do it when it gets the dirty reflow corresponding to the frame
  // being destroyed
  bool stopTelling = false;
  for (nsIFrame* kidFrame = aFirstFrame.FirstChild(); (kidFrame && !stopAsking);
       kidFrame = kidFrame->GetNextSibling()) {
    nsTableCellFrame* cellFrame = do_QueryFrame(kidFrame);
    if (cellFrame) {
      stopTelling = tableFrame->CellChangedWidth(
          *cellFrame, cellFrame->GetPass1MaxElementWidth(),
          cellFrame->GetMaximumWidth(), true);
    }
  }
  // XXX need to consider what happens if there are cells that have rowspans
  // into the deleted row. Need to consider moving rows if a rebalance doesn't
  // happen
#endif

  int32_t firstRowIndex = aFirstRowFrame.GetRowIndex();
#ifdef DEBUG_TABLE_CELLMAP
  printf("=== removeRowsBefore firstRow=%d numRows=%d\n", firstRowIndex,
         aNumRowsToRemove);
  Dump(true, false, true);
#endif
  nsTableCellMap* cellMap = GetCellMap();
  if (cellMap) {
    TableArea damageArea(0, 0, 0, 0);

    // Mark rows starting from aFirstRowFrame to the next 'aNumRowsToRemove-1'
    // number of rows as deleted.
    nsTableRowGroupFrame* parentFrame = aFirstRowFrame.GetTableRowGroupFrame();
    parentFrame->MarkRowsAsDeleted(aFirstRowFrame, aNumRowsToRemove);

    cellMap->RemoveRows(firstRowIndex, aNumRowsToRemove, aConsiderSpans,
                        damageArea);
    MatchCellMapToColCache(cellMap);
    if (IsBorderCollapse()) {
      AddBCDamageArea(damageArea);
    }
  }

#ifdef DEBUG_TABLE_CELLMAP
  printf("=== removeRowsAfter\n");
  Dump(true, true, true);
#endif
}

// collect the rows ancestors of aFrame
int32_t nsTableFrame::CollectRows(nsIFrame* aFrame,
                                  nsTArray<nsTableRowFrame*>& aCollection) {
  MOZ_ASSERT(aFrame, "null frame");
  int32_t numRows = 0;
  for (nsIFrame* childFrame : aFrame->PrincipalChildList()) {
    aCollection.AppendElement(static_cast<nsTableRowFrame*>(childFrame));
    numRows++;
  }
  return numRows;
}

void nsTableFrame::InsertRowGroups(const nsFrameList::Slice& aRowGroups) {