Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices. r=dbaron
authorNeerja Pancholi <npancholi@mozilla.com>
Thu, 02 Mar 2017 15:09:30 -0800
changeset 374772 85613fa0c5fec9e51f428debcb1d05aaa33f73da
parent 374771 ae20c5a91d7b76b8e872c2fa4d8d95583e8c52f9
child 374773 d2ad3e67b80b59188baa34f981dc2d267490efe0
push id10863
push userjlorenzo@mozilla.com
push dateMon, 06 Mar 2017 23:02:23 +0000
treeherdermozilla-aurora@0931190cd725 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdbaron
bugs1285874
milestone54.0a1
Bug 1285874 - Maintain a map of removed table-rows and use it to lazily recalculate row indices. r=dbaron MozReview-Commit-ID: Jt6QJTp0YGe
layout/tables/nsTableFrame.cpp
layout/tables/nsTableFrame.h
layout/tables/nsTableRowFrame.h
layout/tables/nsTableRowGroupFrame.cpp
layout/tables/nsTableRowGroupFrame.h
--- a/layout/tables/nsTableFrame.cpp
+++ b/layout/tables/nsTableFrame.cpp
@@ -911,46 +911,153 @@ nsTableFrame::InsertRows(nsTableRowGroup
   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 didRecalculate = RecalculateRowIndices();
     int32_t origNumRows = cellMap->GetRowCount();
     int32_t numNewRows = aRowFrames.Length();
     cellMap->InsertRows(aRowGroupFrame, aRowFrames, aRowIndex, aConsiderSpans, damageArea);
     MatchCellMapToColCache(cellMap);
-    if (aRowIndex < origNumRows) {
-      AdjustRowIndices(aRowIndex, numNewRows);
-    }
-    // assign the correct row indices to the new rows. If they were adjusted 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 (!didRecalculate) {
+      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;
 }
 
+bool
+nsTableFrame::RecalculateRowIndices()
+{
+  if (mDeletedRowIndexRanges.size() == 0) {
+    return false;
+  }
+  mDeletedRowIndexRanges.clear();
+
+  RowGroupArray rowGroups;
+  OrderRowGroups(rowGroups);
+
+  int32_t rowIndex = 0;
+  for (uint32_t rgIdx = 0; rgIdx < rowGroups.Length(); rgIdx++) {
+    nsTableRowGroupFrame* rgFrame = rowGroups[rgIdx];
+    const nsFrameList& rowFrames = rgFrame->PrincipalChildList();
+    for (nsFrameList::Enumerator rEnum(rowFrames); !rEnum.AtEnd(); rEnum.Next()) {
+      if (mozilla::StyleDisplay::TableRow == rEnum.get()->StyleDisplay()->mDisplay) {
+        nsTableRowFrame *row = static_cast<nsTableRowFrame*>(rEnum.get());
+        row->SetRowIndex(rowIndex);
+        rowIndex++;
+      }
+    }
+  }
+  return true;
+}
+
+void
+nsTableFrame::AddDeletedRowIndex(int32_t aDeletedRowStoredIndex)
+{
+  if (mDeletedRowIndexRanges.size() == 0) {
+    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--;
+  }
+
+  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.size() == 0)
+    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)
+                         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);
@@ -966,23 +1073,29 @@ nsTableFrame::RemoveRows(nsTableRowFrame
   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);
     }
   }
-  AdjustRowIndices(firstRowIndex, -aNumRowsToRemove);
+
 #ifdef DEBUG_TABLE_CELLMAP
   printf("=== removeRowsAfter\n");
   Dump(true, true, true);
 #endif
 }
 
 // collect the rows ancestors of aFrame
 int32_t
--- a/layout/tables/nsTableFrame.h
+++ b/layout/tables/nsTableFrame.h
@@ -775,20 +775,20 @@ public:
   bool IsGeometryDirty() const { return mBits.mGeometryDirty; }
 
   /** Get the cell map for this table frame.  It is not always mCellMap.
     * Only the firstInFlow has a legit cell map
     */
   nsTableCellMap* GetCellMap() const;
 
   /** Iterate over the row groups and adjust the row indices of all rows
-    * whose index is >= aRowIndex.
-    * @param aRowIndex   - start adjusting with this index
-    * @param aAdjustment - shift the row index by this amount
-    */
+   * whose index is >= aRowIndex.
+   * @param aRowIndex   - start adjusting with this index
+   * @param aAdjustment - shift the row index by this amount
+   */
   void AdjustRowIndices(int32_t aRowIndex,
                         int32_t aAdjustment);
 
   /** Reset the rowindices of all rows as they might have changed due to
     * rowgroup reordering, exclude new row group frames that show in the
     * reordering but are not yet inserted into the cellmap
     * @param aRowGroupsToExclude - an iterator that will produce the row groups
     *                              to exclude.
@@ -839,16 +839,53 @@ public: /* ----- Cell Map public methods
   // return the last col index which isn't of type eColAnonymousCell
   int32_t GetIndexOfLastRealCol();
 
   /** returns true if table-layout:auto  */
   bool IsAutoLayout();
 
 public:
 
+  /* ---------- Row index management methods ------------ */
+
+  /** Add the given index to the existing ranges of
+   *  deleted row indices and merge ranges if, with the addition of the new
+   *  index, they become consecutive.
+   *  @param aDeletedRowStoredIndex - index of the row that was deleted
+   *  Note - 'stored' index here refers to the index that was assigned to
+   *  the row before any remove row operations were performed i.e. the
+   *  value of mRowIndex and not the value returned by GetRowIndex()
+   */
+  void AddDeletedRowIndex(int32_t aDeletedRowStoredIndex);
+
+  /** Calculate the change that aStoredIndex must be increased/decreased by
+   *  to get new index.
+   *  Note that aStoredIndex is always the index of an undeleted row (since
+   *  rows that have already been deleted can never call this method).
+   *  @param aStoredIndex - The stored index value that must be adjusted
+   *  Note - 'stored' index here refers to the index that was assigned to
+   *  the row before any remove row operations were performed i.e. the
+   *  value of mRowIndex and not the value returned by GetRowIndex()
+   */
+  int32_t GetAdjustmentForStoredIndex(int32_t aStoredIndex);
+
+  /** Recalculate the row indices of all rows (if needed) and overwrite
+   *  the value of the stored index with this newly calculated index.
+   *  Returns whether recalculation was performed.
+   */
+  bool RecalculateRowIndices();
+
+  /** Returns whether mDeletedRowIndexRanges is empty
+   */
+  bool IsDeletedRowIndexRangesEmpty() const {
+    return mDeletedRowIndexRanges.empty();
+  }
+
+public:
+
 #ifdef DEBUG
   void Dump(bool            aDumpRows,
             bool            aDumpCols,
             bool            aDumpCellMap);
 #endif
 
 protected:
   /**
@@ -869,16 +906,18 @@ protected:
     uint32_t mRowInserted:1;
     uint32_t mNeedToCalcBCBorders:1;
     uint32_t mGeometryDirty:1;
     uint32_t mIStartContBCBorder:8;
     uint32_t mNeedToCollapse:1;        // rows, cols that have visibility:collapse need to be collapsed
     uint32_t mResizedColumns:1;        // have we resized columns since last reflow?
   } mBits;
 
+  std::map<int32_t, int32_t> mDeletedRowIndexRanges; // maintains ranges of row
+                                                     // indices of deleted rows
   nsTableCellMap*         mCellMap;            // maintains the relationships between rows, cols, and cells
   nsITableLayoutStrategy* mTableLayoutStrategy;// the layout strategy for this frame
   nsFrameList             mColGroups;          // the list of colgroup frames
 };
 
 
 inline bool nsTableFrame::IsRowGroup(mozilla::StyleDisplay aDisplayType) const
 {
--- a/layout/tables/nsTableRowFrame.h
+++ b/layout/tables/nsTableRowFrame.h
@@ -135,23 +135,29 @@ public:
    * 'vertical-align: baseline', *including* cells with rowspans.
    * returns 0 if we don't have any cell with 'vertical-align: baseline'
    */
   nscoord GetMaxCellAscent() const;
 
   /* return the row ascent
    */
   nscoord GetRowBaseline(mozilla::WritingMode aWritingMode);
- 
+
   /** returns the ordinal position of this row in its table */
   virtual int32_t GetRowIndex() const;
 
   /** set this row's starting row index */
   void SetRowIndex (int aRowIndex);
 
+  // See nsTableFrame.h
+  int32_t GetAdjustmentForStoredIndex(int32_t aStoredIndex) const;
+
+  // See nsTableFrame.h
+  void AddDeletedRowIndex();
+
   /** used by row group frame code */
   nscoord ReflowCellFrame(nsPresContext*           aPresContext,
                           const ReflowInput& aReflowInput,
                           bool                     aIsTopOfPage,
                           nsTableCellFrame*        aCellFrame,
                           nscoord                  aAvailableBSize,
                           nsReflowStatus&          aStatus);
   /**
@@ -314,23 +320,44 @@ private:
    * Sets the NS_ROW_HAS_CELL_WITH_STYLE_BSIZE bit to indicate whether
    * this row has any cells that have non-auto-bsize.  (Row-spanning
    * cells are ignored.)
    */
   void InitHasCellWithStyleBSize(nsTableFrame* aTableFrame);
 
 };
 
+inline int32_t
+nsTableRowFrame::GetAdjustmentForStoredIndex(int32_t aStoredIndex) const
+{
+  nsTableRowGroupFrame* parentFrame = GetTableRowGroupFrame();
+  return parentFrame->GetAdjustmentForStoredIndex(aStoredIndex);
+}
+
+inline void nsTableRowFrame::AddDeletedRowIndex()
+{
+  nsTableRowGroupFrame* parentFrame = GetTableRowGroupFrame();
+  parentFrame->AddDeletedRowIndex(int32_t(mBits.mRowIndex));
+}
+
 inline int32_t nsTableRowFrame::GetRowIndex() const
 {
-  return int32_t(mBits.mRowIndex);
+  int32_t storedRowIndex = int32_t(mBits.mRowIndex);
+  int32_t rowIndexAdjustment = GetAdjustmentForStoredIndex(storedRowIndex);
+  return (storedRowIndex - rowIndexAdjustment);
 }
 
 inline void nsTableRowFrame::SetRowIndex (int aRowIndex)
 {
+  // Note: Setting the index of a row (as in the case of adding new rows) should
+  // be preceded by a call to nsTableFrame::RecalculateRowIndices()
+  // so as to correctly clear mDeletedRowIndexRanges.
+  MOZ_ASSERT(GetTableRowGroupFrame()->
+               GetTableFrame()->IsDeletedRowIndexRangesEmpty(),
+             "mDeletedRowIndexRanges should be empty here!");
   mBits.mRowIndex = aRowIndex;
 }
 
 inline bool nsTableRowFrame::IsFirstInserted() const
 {
   return bool(mBits.mFirstInserted);
 }
 
--- a/layout/tables/nsTableRowGroupFrame.cpp
+++ b/layout/tables/nsTableRowGroupFrame.cpp
@@ -115,16 +115,61 @@ void  nsTableRowGroupFrame::AdjustRowInd
   for (nsIFrame* rowFrame : mFrames) {
     if (mozilla::StyleDisplay::TableRow == rowFrame->StyleDisplay()->mDisplay) {
       int32_t index = ((nsTableRowFrame*)rowFrame)->GetRowIndex();
       if (index >= aRowIndex)
         ((nsTableRowFrame *)rowFrame)->SetRowIndex(index+anAdjustment);
     }
   }
 }
+
+int32_t
+nsTableRowGroupFrame::GetAdjustmentForStoredIndex(int32_t aStoredIndex)
+{
+  nsTableFrame* tableFrame = GetTableFrame();
+  return tableFrame->GetAdjustmentForStoredIndex(aStoredIndex);
+}
+
+void
+nsTableRowGroupFrame::MarkRowsAsDeleted(nsTableRowFrame& aStartRowFrame,
+                                        int32_t          aNumRowsToDelete)
+{
+  nsTableRowFrame* currentRowFrame = &aStartRowFrame;
+  for (;;) {
+    // XXXneerja - Instead of calling AddDeletedRowIndex() per row frame
+    // it is possible to change AddDeleteRowIndex to instead take
+    // <start row index> and <num of rows to mark for deletion> as arguments.
+    // The problem that emerges here is mDeletedRowIndexRanges only stores
+    // disjoint index ranges and since AddDeletedRowIndex() must operate on
+    // the "stored" index, in some cases it is possible that the range
+    // of indices to delete becomes overlapping EG: Deleting rows 9 - 11 and
+    // then from the remaining rows deleting the *new* rows 7 to 20.
+    // Handling these overlapping ranges is much more complicated to
+    // implement and so I opted to add the deleted row index of one row at a
+    // time and maintain the invariant that the range of deleted row indices
+    // is always disjoint.
+    currentRowFrame->AddDeletedRowIndex();
+    if (--aNumRowsToDelete == 0) {
+      break;
+    }
+    currentRowFrame = do_QueryFrame(currentRowFrame->GetNextSibling());
+    if (!currentRowFrame) {
+      MOZ_ASSERT_UNREACHABLE("expected another row frame");
+      break;
+    }
+  }
+}
+
+void
+nsTableRowGroupFrame::AddDeletedRowIndex(int32_t aDeletedRowStoredIndex)
+{
+  nsTableFrame* tableFrame = GetTableFrame();
+  return tableFrame->AddDeletedRowIndex(aDeletedRowStoredIndex);
+}
+
 nsresult
 nsTableRowGroupFrame::InitRepeatedFrame(nsTableRowGroupFrame* aHeaderFooterFrame)
 {
   nsTableRowFrame* copyRowFrame = GetFirstRow();
   nsTableRowFrame* originalRowFrame = aHeaderFooterFrame->GetFirstRow();
   AddStateBits(NS_REPEATED_ROW_OR_ROWGROUP);
   while (copyRowFrame && originalRowFrame) {
     copyRowFrame->AddStateBits(NS_REPEATED_ROW_OR_ROWGROUP);
--- a/layout/tables/nsTableRowGroupFrame.h
+++ b/layout/tables/nsTableRowGroupFrame.h
@@ -130,16 +130,29 @@ public:
 
   /** Adjust the row indices of all rows  whose index is >= aRowIndex.
     * @param aRowIndex   - start adjusting with this index
     * @param aAdjustment - shift the row index by this amount
     */
   void AdjustRowIndices(int32_t   aRowIndex,
                         int32_t   anAdjustment);
 
+  // See nsTableFrame.h
+  int32_t GetAdjustmentForStoredIndex(int32_t aStoredIndex);
+
+  /* mark rows starting from aStartRowFrame to the next 'aNumRowsToRemove-1'
+   * number of rows as deleted
+   */
+  void MarkRowsAsDeleted(nsTableRowFrame& aStartRowFrame,
+                         int32_t          aNumRowsToDelete);
+
+  // See nsTableFrame.h
+  void AddDeletedRowIndex(int32_t aDeletedRowStoredIndex);
+
+
   /**
    * Used for header and footer row group frames that are repeated when
    * splitting a table frame.
    *
    * Performs any table specific initialization
    *
    * @param aHeaderFooterFrame the original header or footer row group frame
    * that was repeated