Bug 1107786 - part 1, [css-grid] Implement layout and painting per the CSS 'order' property for normal flow grid items. r=dholbert
authorMats Palmgren <mats@mozilla.com>
Thu, 26 Mar 2015 18:57:39 +0000
changeset 266284 b41915b3c38be487eb54742253341e7a11ea31b1
parent 266283 13f447b5f8c2d960551fd855670ea77a5733fff9
child 266285 33d6a3e888a8aa2e6ac5ee2635123cc0d4a40448
push id830
push userraliiev@mozilla.com
push dateFri, 19 Jun 2015 19:24:37 +0000
treeherdermozilla-release@932614382a68 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdholbert
bugs1107786
milestone39.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1107786 - part 1, [css-grid] Implement layout and painting per the CSS 'order' property for normal flow grid items. r=dholbert
layout/generic/nsGridContainerFrame.cpp
layout/generic/nsGridContainerFrame.h
--- a/layout/generic/nsGridContainerFrame.cpp
+++ b/layout/generic/nsGridContainerFrame.cpp
@@ -3,32 +3,135 @@
 /* This Source Code is subject to the terms of the Mozilla Public License
  * version 2.0 (the "License"). You can obtain a copy of the License at
  * http://mozilla.org/MPL/2.0/. */
 
 /* rendering object for CSS "display: grid | inline-grid" */
 
 #include "nsGridContainerFrame.h"
 
+#include <algorithm> // for std::stable_sort
+#include <limits>
 #include "mozilla/Maybe.h"
 #include "nsAbsoluteContainingBlock.h"
 #include "nsAlgorithm.h" // for clamped()
+#include "nsAutoPtr.h"
 #include "nsCSSAnonBoxes.h"
 #include "nsDataHashtable.h"
 #include "nsDisplayList.h"
 #include "nsHashKeys.h"
 #include "nsIFrameInlines.h"
 #include "nsPresContext.h"
 #include "nsReadableUtils.h"
 #include "nsRuleNode.h"
 #include "nsStyleContext.h"
 
 using namespace mozilla;
 typedef nsGridContainerFrame::TrackSize TrackSize;
 
+class nsGridContainerFrame::GridItemCSSOrderIterator
+{
+public:
+  enum OrderState { eUnknownOrder, eKnownOrdered, eKnownUnordered };
+  GridItemCSSOrderIterator(nsIFrame* aGridContainer,
+                           nsIFrame::ChildListID aListID,
+                           OrderState aState = eUnknownOrder)
+    : mChildren(aGridContainer->GetChildList(aListID))
+    , mArrayIndex(0)
+#ifdef DEBUG
+    , mGridContainer(aGridContainer)
+    , mListID(aListID)
+#endif
+  {
+    size_t count = 0;
+    bool isOrdered = aState != eKnownUnordered;
+    if (aState == eUnknownOrder) {
+      auto maxOrder = std::numeric_limits<int32_t>::min();
+      for (nsFrameList::Enumerator e(mChildren); !e.AtEnd(); e.Next()) {
+        ++count;
+        int32_t order = e.get()->StylePosition()->mOrder;
+        if (order < maxOrder) {
+          isOrdered = false;
+          break;
+        }
+        maxOrder = order;
+      }
+    }
+    if (isOrdered) {
+      mEnumerator.emplace(mChildren);
+    } else {
+      count *= 2; // XXX somewhat arbitrary estimate for now...
+      mArray.emplace(count);
+      for (nsFrameList::Enumerator e(mChildren); !e.AtEnd(); e.Next()) {
+        mArray->AppendElement(e.get());
+      }
+      // XXX replace this with nsTArray::StableSort when bug 1147091 is fixed.
+      std::stable_sort(mArray->begin(), mArray->end(), IsCSSOrderLessThan);
+    }
+  }
+
+  nsIFrame* operator*() const
+  {
+    MOZ_ASSERT(!AtEnd());
+    if (mEnumerator) {
+      return mEnumerator->get();
+    }
+    return (*mArray)[mArrayIndex];
+  }
+
+  bool AtEnd() const
+  {
+    MOZ_ASSERT(mEnumerator || mArrayIndex <= mArray->Length());
+    return mEnumerator ? mEnumerator->AtEnd() : mArrayIndex >= mArray->Length();
+  }
+
+  void Next()
+  {
+#ifdef DEBUG
+    nsFrameList list = mGridContainer->GetChildList(mListID);
+    MOZ_ASSERT(list.FirstChild() == mChildren.FirstChild() &&
+               list.LastChild() == mChildren.LastChild(),
+               "the list of child frames must not change while iterating!");
+#endif
+    if (mEnumerator) {
+      mEnumerator->Next();
+    } else {
+      MOZ_ASSERT(mArrayIndex < mArray->Length(), "iterating past end");
+      ++mArrayIndex;
+    }
+  }
+
+  void Reset()
+  {
+    if (mEnumerator) {
+      mEnumerator.reset();
+      mEnumerator.emplace(mChildren);
+    } else {
+      mArrayIndex = 0;
+    }
+  }
+
+  bool ItemsAreAlreadyInOrder() const { return mEnumerator.isSome(); }
+
+private:
+  static bool IsCSSOrderLessThan(nsIFrame* const& a, nsIFrame* const& b)
+    { return a->StylePosition()->mOrder < b->StylePosition()->mOrder; }
+
+  nsFrameList mChildren;
+  // Used if child list is already in ascending 'order'.
+  Maybe<nsFrameList::Enumerator> mEnumerator;
+  // Used if child list is *not* in ascending 'order'.
+  Maybe<nsTArray<nsIFrame*>> mArray;
+  size_t mArrayIndex;
+#ifdef DEBUG
+  nsIFrame* mGridContainer;
+  nsIFrame::ChildListID mListID;
+#endif
+};
+
 /**
  * Search for the aNth occurrence of aName in aNameList (forward), starting at
  * the zero-based aFromIndex, and return the 1-based index (line number).
  * Also take into account there is an unconditional match at aImplicitLine
  * unless it's zero.
  * Return the last match if aNth occurrences can't be found, or zero if no
  * occurrence can be found.
  */
@@ -685,25 +788,26 @@ nsGridContainerFrame::InitializeGridBoun
   auto areas = aStyle->mGridTemplateAreas.get();
   mExplicitGridColEnd = std::max(colEnd, areas ? areas->mNColumns + 1 : 1);
   mExplicitGridRowEnd = std::max(rowEnd, areas ? areas->NRows() + 1 : 1);
   mGridColEnd = mExplicitGridColEnd;
   mGridRowEnd = mExplicitGridRowEnd;
 }
 
 void
-nsGridContainerFrame::PlaceGridItems(const nsStylePosition* aStyle)
+nsGridContainerFrame::PlaceGridItems(GridItemCSSOrderIterator& aIter,
+                                     const nsStylePosition*    aStyle)
 {
   mCellMap.ClearOccupied();
   InitializeGridBounds(aStyle);
 
   // http://dev.w3.org/csswg/css-grid/#line-placement
   // Resolve definite positions per spec chap 9.2.
-  for (nsFrameList::Enumerator e(PrincipalChildList()); !e.AtEnd(); e.Next()) {
-    nsIFrame* child = e.get();
+  for (; !aIter.AtEnd(); aIter.Next()) {
+    nsIFrame* child = *aIter;
     const GridArea& area = PlaceDefinite(child, aStyle);
     GridArea* prop = GetGridAreaForChild(child);
     if (prop) {
       *prop = area;
     } else {
       child->Properties().Set(GridAreaProperty(), new GridArea(area));
     }
     if (area.IsDefinite()) {
@@ -721,18 +825,19 @@ nsGridContainerFrame::PlaceGridItems(con
   // We need 1 cursor per row (or column) if placement is sparse.
   {
     Maybe<nsDataHashtable<nsUint32HashKey, uint32_t>> cursors;
     if (isSparse) {
       cursors.emplace();
     }
     auto placeAutoMinorFunc = isRowOrder ? &nsGridContainerFrame::PlaceAutoCol
                                          : &nsGridContainerFrame::PlaceAutoRow;
-    for (nsFrameList::Enumerator e(PrincipalChildList()); !e.AtEnd(); e.Next()) {
-      nsIFrame* child = e.get();
+    aIter.Reset();
+    for (; !aIter.AtEnd(); aIter.Next()) {
+      nsIFrame* child = *aIter;
       GridArea* area = GetGridAreaForChild(child);
       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.
         uint32_t cursor = 1;
         if (isSparse) {
           cursors->Get(major.mStart, &cursor);
@@ -755,18 +860,19 @@ nsGridContainerFrame::PlaceGridItems(con
   // 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 = 1; // for 'dense' these two cursors will stay at 1,1
   uint32_t cursorMinor = 1;
   auto placeAutoMajorFunc = isRowOrder ? &nsGridContainerFrame::PlaceAutoRow
                                        : &nsGridContainerFrame::PlaceAutoCol;
-  for (nsFrameList::Enumerator e(PrincipalChildList()); !e.AtEnd(); e.Next()) {
-    nsIFrame* child = e.get();
+  aIter.Reset();
+  for (; !aIter.AtEnd(); aIter.Next()) {
+    nsIFrame* child = *aIter;
     GridArea* area = GetGridAreaForChild(child);
     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) {
@@ -983,29 +1089,30 @@ nsGridContainerFrame::ContainingBlockFor
   aArea.mCols.ToPositionAndLengthForAbsPos(aColSizes, aGridOrigin.I(aWM),
                                            &i, &iSize);
   aArea.mRows.ToPositionAndLengthForAbsPos(aRowSizes, aGridOrigin.B(aWM),
                                            &b, &bSize);
   return LogicalRect(aWM, i, b, iSize, bSize);
 }
 
 void
-nsGridContainerFrame::ReflowChildren(const LogicalRect&         aContentArea,
+nsGridContainerFrame::ReflowChildren(GridItemCSSOrderIterator&  aIter,
+                                     const LogicalRect&         aContentArea,
                                      const nsTArray<TrackSize>& aColSizes,
                                      const nsTArray<TrackSize>& aRowSizes,
                                      nsHTMLReflowMetrics&       aDesiredSize,
                                      const nsHTMLReflowState&   aReflowState,
                                      nsReflowStatus&            aStatus)
 {
   WritingMode wm = aReflowState.GetWritingMode();
   const LogicalPoint gridOrigin(aContentArea.Origin(wm));
   const nscoord gridWidth = aContentArea.Width(wm);
   nsPresContext* pc = PresContext();
-  for (nsFrameList::Enumerator e(PrincipalChildList()); !e.AtEnd(); e.Next()) {
-    nsIFrame* child = e.get();
+  for (; !aIter.AtEnd(); aIter.Next()) {
+    nsIFrame* child = *aIter;
     GridArea* area = GetGridAreaForChild(child);
     MOZ_ASSERT(area && area->IsDefinite());
     LogicalRect cb = ContainingBlockFor(wm, *area, aColSizes, aRowSizes);
     cb += gridOrigin;
     nsHTMLReflowState childRS(pc, aReflowState, child, cb.Size(wm));
     const LogicalMargin margin = childRS.ComputedLogicalMargin();
     if (childRS.ComputedBSize() == NS_AUTOHEIGHT) {
       // XXX the start of an align-self:stretch impl.  Needs min-/max-bsize
@@ -1083,17 +1190,19 @@ nsGridContainerFrame::Reflow(nsPresConte
 #ifdef DEBUG
   SanityCheckAnonymousGridItems();
 #endif // DEBUG
 
   LogicalMargin bp = aReflowState.ComputedLogicalBorderPadding();
   bp.ApplySkipSides(GetLogicalSkipSides());
   const nsStylePosition* stylePos = aReflowState.mStylePosition;
   InitImplicitNamedAreas(stylePos);
-  PlaceGridItems(stylePos);
+  GridItemCSSOrderIterator normalFlowIter(this, kPrincipalList);
+  mIsNormalFlowInCSSOrder = normalFlowIter.ItemsAreAlreadyInOrder();
+  PlaceGridItems(normalFlowIter, stylePos);
 
   nsAutoTArray<TrackSize, 32> colSizes;
   nsAutoTArray<TrackSize, 32> rowSizes;
   WritingMode wm = aReflowState.GetWritingMode();
   const nscoord computedBSize = aReflowState.ComputedBSize();
   const nscoord computedISize = aReflowState.ComputedISize();
   LogicalSize percentageBasis(wm, computedISize,
       computedBSize == NS_AUTOHEIGHT ? 0 : computedBSize);
@@ -1110,17 +1219,18 @@ nsGridContainerFrame::Reflow(nsPresConte
   bSize = std::max(bSize - GetConsumedBSize(), 0);
   LogicalSize desiredSize(wm, computedISize + bp.IStartEnd(wm),
                           bSize + bp.BStartEnd(wm));
   aDesiredSize.SetSize(wm, desiredSize);
   aDesiredSize.SetOverflowAreasToDesiredBounds();
 
   LogicalRect contentArea(wm, bp.IStart(wm), bp.BStart(wm),
                           computedISize, bSize);
-  ReflowChildren(contentArea, colSizes, rowSizes, aDesiredSize,
+  normalFlowIter.Reset();
+  ReflowChildren(normalFlowIter, contentArea, colSizes, rowSizes, aDesiredSize,
                  aReflowState, aStatus);
 
   FinishAndStoreOverflow(&aDesiredSize);
   aStatus = NS_FRAME_COMPLETE;
   NS_FRAME_SET_TRUNCATION(aStatus, aReflowState, aDesiredSize);
 }
 
 nsIAtom*
@@ -1135,18 +1245,22 @@ nsGridContainerFrame::BuildDisplayList(n
                                        const nsDisplayListSet& aLists)
 {
   DisplayBorderBackgroundOutline(aBuilder, aLists);
 
   // Our children are all grid-level boxes, which behave the same as
   // inline-blocks in painting, so their borders/backgrounds all go on
   // the BlockBorderBackgrounds list.
   nsDisplayListSet childLists(aLists, aLists.BlockBorderBackgrounds());
-  for (nsFrameList::Enumerator e(PrincipalChildList()); !e.AtEnd(); e.Next()) {
-    nsIFrame* child = e.get();
+  typedef GridItemCSSOrderIterator::OrderState OrderState;
+  OrderState order = mIsNormalFlowInCSSOrder ? OrderState::eKnownOrdered
+                                             : OrderState::eKnownUnordered;
+  GridItemCSSOrderIterator iter(this, kPrincipalList, order);
+  for (; !iter.AtEnd(); iter.Next()) {
+    nsIFrame* child = *iter;
     BuildDisplayListForChild(aBuilder, child, aDirtyRect, childLists,
                              ::GetDisplayFlagsForGridItem(child));
   }
 }
 
 #ifdef DEBUG_FRAME_DUMP
 nsresult
 nsGridContainerFrame::GetFrameName(nsAString& aResult) const
--- a/layout/generic/nsGridContainerFrame.h
+++ b/layout/generic/nsGridContainerFrame.h
@@ -59,16 +59,17 @@ public:
 
   NS_DECLARE_FRAME_PROPERTY(GridItemContainingBlockRect, DeleteValue<nsRect>)
 
 protected:
   typedef mozilla::LogicalPoint LogicalPoint;
   typedef mozilla::LogicalRect LogicalRect;
   typedef mozilla::WritingMode WritingMode;
   typedef mozilla::css::GridNamedArea GridNamedArea;
+  class GridItemCSSOrderIterator;
   friend nsContainerFrame* NS_NewGridContainerFrame(nsIPresShell* aPresShell,
                                                     nsStyleContext* aContext);
   explicit nsGridContainerFrame(nsStyleContext* aContext) : nsContainerFrame(aContext) {}
 
   /**
    * 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
    * (both 1-based) where mStart < mEnd.  Before it's definite it can also
@@ -298,19 +299,21 @@ protected:
    * @param aStyle the StylePosition() for the grid container
    */
   GridArea PlaceAbsPos(nsIFrame* aChild, const nsStylePosition* aStyle);
 
   /**
    * 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 aIter a grid item iterator
    * @param aStyle the StylePosition() for the grid container
    */
-  void PlaceGridItems(const nsStylePosition* aStyle);
+  void PlaceGridItems(GridItemCSSOrderIterator& aIter,
+                      const nsStylePosition* aStyle);
 
   /**
    * 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.
    * @param aStyle the StylePosition() for the grid container
    */
@@ -400,17 +403,18 @@ protected:
                                        const nsTArray<TrackSize>& aColSizes,
                                        const nsTArray<TrackSize>& aRowSizes,
                                        const LogicalPoint& aGridOrigin,
                                        const LogicalRect& aGridCB) const;
 
   /**
    * Reflow and place our children.
    */
-  void ReflowChildren(const LogicalRect&          aContentArea,
+  void ReflowChildren(GridItemCSSOrderIterator&   aIter,
+                      const LogicalRect&          aContentArea,
                       const nsTArray<TrackSize>&  aColSizes,
                       const nsTArray<TrackSize>&  aRowSizes,
                       nsHTMLReflowMetrics&        aDesiredSize,
                       const nsHTMLReflowState&    aReflowState,
                       nsReflowStatus&             aStatus);
 
 #ifdef DEBUG
   void SanityCheckAnonymousGridItems() const;
@@ -430,11 +434,16 @@ private:
   /**
    * 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
   uint32_t mGridColEnd; // always >= mExplicitGridColEnd
   uint32_t mGridRowEnd; // always >= mExplicitGridRowEnd
+  /**
+   * True iff the normal flow children are already in CSS 'order' in the
+   * order they occur in the child frame list.
+   */
+  bool mIsNormalFlowInCSSOrder : 1;
 };
 
 #endif /* nsGridContainerFrame_h___ */