Bug 1151204 part 1 - [css-grid] Make GridItemCSSOrderIterator use nsFrameList iterators internally and make the specific type (forward/reverse) a template param. r=dholbert
authorMats Palmgren <mats@mozilla.com>
Sat, 01 Oct 2016 02:26:39 +0200
changeset 316101 bb3080bc1aad672b53575dc983f1bd2c3e1718a0
parent 316100 83a86d52b0388f1eae91109ce393a12bd4a0dd9e
child 316102 33bd454be96a44c66a1651f3e1b4d098e4f45f07
push id30759
push userphilringnalda@gmail.com
push dateSat, 01 Oct 2016 06:25:09 +0000
treeherdermozilla-central@fcc62bbf09ee [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersdholbert
bugs1151204
milestone52.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 1151204 part 1 - [css-grid] Make GridItemCSSOrderIterator use nsFrameList iterators internally and make the specific type (forward/reverse) a template param. r=dholbert
layout/generic/nsGridContainerFrame.cpp
layout/generic/nsGridContainerFrame.h
--- a/layout/generic/nsGridContainerFrame.cpp
+++ b/layout/generic/nsGridContainerFrame.cpp
@@ -8,31 +8,36 @@
 
 #include "nsGridContainerFrame.h"
 
 #include <algorithm> // for std::stable_sort
 #include <limits>
 #include "mozilla/Function.h"
 #include "mozilla/Maybe.h"
 #include "mozilla/PodOperations.h" // for PodZero
+#include "mozilla/Poison.h"
 #include "nsAbsoluteContainingBlock.h"
 #include "nsAlgorithm.h" // for clamped()
 #include "nsCSSAnonBoxes.h"
 #include "nsCSSFrameConstructor.h"
 #include "nsDataHashtable.h"
 #include "nsDisplayList.h"
 #include "nsHashKeys.h"
 #include "nsIFrameInlines.h"
 #include "nsPresContext.h"
 #include "nsRenderingContext.h"
 #include "nsReadableUtils.h"
 #include "nsRuleNode.h"
 #include "nsStyleContext.h"
 #include "mozilla/dom/GridBinding.h"
 
+#if defined(__clang__) && __clang_major__ == 3 && __clang_minor__  == 6
+#define CLANG_CRASH_BUG 1
+#endif
+
 using namespace mozilla;
 typedef nsAbsoluteContainingBlock::AbsPosReflowFlags AbsPosReflowFlags;
 typedef nsGridContainerFrame::TrackSize TrackSize;
 const uint32_t nsGridContainerFrame::kTranslatedMaxLine =
   uint32_t(nsStyleGridLine::kMaxLine - nsStyleGridLine::kMinLine);
 const uint32_t nsGridContainerFrame::kAutoLine = kTranslatedMaxLine + 3457U;
 typedef nsTHashtable< nsPtrHashKey<nsIFrame> > FrameHashtable;
 
@@ -314,174 +319,255 @@ MergeSortedFrameLists(nsFrameList& aDest
 
 static void
 MergeSortedFrameListsFor(nsFrameList& aDest, nsFrameList& aSrc,
                          nsContainerFrame* aParent)
 {
   MergeSortedFrameLists(aDest, aSrc, aParent->GetContent());
 }
 
-class nsGridContainerFrame::GridItemCSSOrderIterator
+template<typename Iterator>
+class nsGridContainerFrame::GridItemCSSOrderIteratorT
 {
 public:
   enum OrderState { eUnknownOrder, eKnownOrdered, eKnownUnordered };
   enum ChildFilter { eSkipPlaceholders, eIncludeAll };
-  GridItemCSSOrderIterator(nsIFrame* aGridContainer,
-                           nsIFrame::ChildListID aListID,
-                           ChildFilter aFilter = eSkipPlaceholders,
-                           OrderState aState = eUnknownOrder)
+  GridItemCSSOrderIteratorT(nsIFrame* aGridContainer,
+                            nsIFrame::ChildListID aListID,
+                            ChildFilter aFilter = eSkipPlaceholders,
+                            OrderState aState = eUnknownOrder)
     : mChildren(aGridContainer->GetChildList(aListID))
     , mArrayIndex(0)
     , mGridItemIndex(0)
     , mSkipPlaceholders(aFilter == eSkipPlaceholders)
 #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()) {
+      for (auto child : mChildren) {
         ++count;
-        int32_t order = e.get()->StylePosition()->mOrder;
+        int32_t order = child->StylePosition()->mOrder;
         if (order < maxOrder) {
           isOrdered = false;
           break;
         }
         maxOrder = order;
       }
     }
     if (isOrdered) {
-      mEnumerator.emplace(mChildren);
+      mIter.emplace(begin(mChildren));
+      mIterEnd.emplace(end(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());
+      for (Iterator i(begin(mChildren)), iEnd(end(mChildren)); i != iEnd; ++i) {
+        mArray->AppendElement(*i);
       }
       // XXX replace this with nsTArray::StableSort when bug 1147091 is fixed.
-      std::stable_sort(mArray->begin(), mArray->end(), IsCSSOrderLessThan);
+      std::stable_sort(mArray->begin(), mArray->end(), CSSOrderComparator);
     }
 
     if (mSkipPlaceholders) {
       SkipPlaceholders();
     }
   }
+  ~GridItemCSSOrderIteratorT()
+  {
+    MOZ_ASSERT(IsForward() == mGridItemCount.isNothing());
+  }
+
+  bool IsForward() const;
+  Iterator begin(const nsFrameList& aList);
+  Iterator end(const nsFrameList& aList);
 
   nsIFrame* operator*() const
   {
     MOZ_ASSERT(!AtEnd());
-    if (mEnumerator) {
-      return mEnumerator->get();
+    if (mIter.isSome()) {
+      return **mIter;
     }
     return (*mArray)[mArrayIndex];
   }
 
   /**
    * Return the child index of the current item, placeholders not counted.
    * It's forbidden to call this method when the current frame is placeholder.
    */
   size_t GridItemIndex() const
   {
     MOZ_ASSERT(!AtEnd());
     MOZ_ASSERT((**this)->GetType() != nsGkAtoms::placeholderFrame,
                "MUST not call this when at a placeholder");
+    MOZ_ASSERT(IsForward() || mGridItemIndex < *mGridItemCount,
+               "Returning an out-of-range mGridItemIndex...");
     return mGridItemIndex;
   }
 
+  void SetGridItemCount(size_t aGridItemCount)
+  {
+    MOZ_ASSERT(mIter.isSome() || mArray->Length() == aGridItemCount,
+               "grid item count mismatch");
+    mGridItemCount.emplace(aGridItemCount);
+    // Note: it's OK if mGridItemIndex underflows -- GridItemIndex()
+    // will not be called unless there is at least one item.
+    mGridItemIndex = IsForward() ? 0 : *mGridItemCount - 1;
+  }
+
   /**
    * Skip over placeholder children.
    */
   void SkipPlaceholders()
   {
-    if (mEnumerator) {
-      for (; !mEnumerator->AtEnd(); mEnumerator->Next()) {
-        nsIFrame* child = mEnumerator->get();
+    if (mIter.isSome()) {
+      for (; *mIter != *mIterEnd; ++*mIter) {
+        nsIFrame* child = **mIter;
         if (child->GetType() != nsGkAtoms::placeholderFrame) {
           return;
         }
       }
     } else {
       for (; mArrayIndex < mArray->Length(); ++mArrayIndex) {
         nsIFrame* child = (*mArray)[mArrayIndex];
         if (child->GetType() != nsGkAtoms::placeholderFrame) {
           return;
         }
       }
     }
   }
 
   bool AtEnd() const
   {
-    MOZ_ASSERT(mEnumerator || mArrayIndex <= mArray->Length());
-    return mEnumerator ? mEnumerator->AtEnd() : mArrayIndex >= mArray->Length();
+#ifndef CLANG_CRASH_BUG
+    // Clang 3.6.2 crashes when compiling this assertion:
+    MOZ_ASSERT(mIter.isSome() || mArrayIndex <= mArray->Length());
+#endif
+    return mIter ? (*mIter == *mIterEnd) : mArrayIndex >= mArray->Length();
   }
 
   void Next()
   {
 #ifdef DEBUG
     MOZ_ASSERT(!AtEnd());
     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 (mSkipPlaceholders ||
         (**this)->GetType() != nsGkAtoms::placeholderFrame) {
-      ++mGridItemIndex;
-    }
-    if (mEnumerator) {
-      mEnumerator->Next();
+      IsForward() ? ++mGridItemIndex : --mGridItemIndex;
+    }
+    if (mIter.isSome()) {
+      ++*mIter;
     } else {
       ++mArrayIndex;
     }
     if (mSkipPlaceholders) {
       SkipPlaceholders();
     }
   }
 
   void Reset(ChildFilter aFilter = eSkipPlaceholders)
   {
-    if (mEnumerator) {
-      mEnumerator.reset();
-      mEnumerator.emplace(mChildren);
+    if (mIter.isSome()) {
+      mIter.reset();
+      mIter.emplace(begin(mChildren));
+      mIterEnd.reset();
+      mIterEnd.emplace(end(mChildren));
     } else {
       mArrayIndex = 0;
     }
-    mGridItemIndex = 0;
+    mGridItemIndex = IsForward() ? 0 : *mGridItemCount - 1;
     mSkipPlaceholders = aFilter == eSkipPlaceholders;
     if (mSkipPlaceholders) {
       SkipPlaceholders();
     }
   }
 
-  bool ItemsAreAlreadyInOrder() const { return mEnumerator.isSome(); }
-
+  bool IsValid() const { return mIter.isSome() || mArray.isSome(); }
+
+  void Invalidate()
+  {
+    mIter.reset();
+    mArray.reset();
+    mozWritePoison(&mChildren, sizeof(mChildren));
+  }
+
+  bool ItemsAreAlreadyInOrder() const { return mIter.isSome(); }
+
+  static bool CSSOrderComparator(nsIFrame* const& a, nsIFrame* const& b);
 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;
+  Maybe<Iterator> mIter;
+  Maybe<Iterator> mIterEnd;
   // Used if child list is *not* in ascending 'order'.
+  // This array is pre-sorted in reverse order for a reverse iterator.
   Maybe<nsTArray<nsIFrame*>> mArray;
   size_t mArrayIndex;
   // The index of the current grid item (placeholders excluded).
   size_t mGridItemIndex;
+  // The number of grid items (placeholders excluded).
+  // It's only initialized and used in a reverse iterator.
+  Maybe<size_t> mGridItemCount;
   // Skip placeholder children in the iteration?
   bool mSkipPlaceholders;
 #ifdef DEBUG
   nsIFrame* mGridContainer;
   nsIFrame::ChildListID mListID;
 #endif
 };
 
+using GridItemCSSOrderIterator = nsGridContainerFrame::GridItemCSSOrderIterator;
+using ReverseGridItemCSSOrderIterator = nsGridContainerFrame::ReverseGridItemCSSOrderIterator;
+
+template<>
+bool
+GridItemCSSOrderIterator::CSSOrderComparator(nsIFrame* const& a,
+                                             nsIFrame* const& b)
+{ return a->StylePosition()->mOrder < b->StylePosition()->mOrder; }
+
+template<>
+bool
+GridItemCSSOrderIterator::IsForward() const { return true; }
+
+template<>
+nsFrameList::iterator
+GridItemCSSOrderIterator::begin(const nsFrameList& aList)
+{ return aList.begin(); }
+
+template<>
+nsFrameList::iterator GridItemCSSOrderIterator::end(const nsFrameList& aList)
+{ return aList.end(); }
+
+template<>
+bool
+ReverseGridItemCSSOrderIterator::CSSOrderComparator(nsIFrame* const& a,
+                                                    nsIFrame* const& b)
+{ return a->StylePosition()->mOrder > b->StylePosition()->mOrder; }
+
+template<>
+bool
+ReverseGridItemCSSOrderIterator::IsForward() const
+{ return false; }
+
+template<>
+nsFrameList::reverse_iterator
+ReverseGridItemCSSOrderIterator::begin(const nsFrameList& aList)
+{ return aList.rbegin(); }
+
+template<>
+nsFrameList::reverse_iterator
+ReverseGridItemCSSOrderIterator::end(const nsFrameList& aList)
+{ return aList.rend(); }
 
 /**
  * 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.
@@ -5431,19 +5517,25 @@ nsGridContainerFrame::ReflowRowsInFragme
       }
       child = next;
     }
 
     // Merge the results into our respective overflow child lists.
     if (!pushedList.IsEmpty()) {
       MergeSortedOverflow(pushedList);
       AddStateBits(NS_STATE_GRID_DID_PUSH_ITEMS);
+      // NOTE since we messed with our child list here, we intentionally
+      // make aState.mIter invalid to avoid any use of it after this point.
+      aState.mIter.Invalidate();
     }
     if (!incompleteList.IsEmpty()) {
       MergeSortedOverflow(incompleteList);
+      // NOTE since we messed with our child list here, we intentionally
+      // make aState.mIter invalid to avoid any use of it after this point.
+      aState.mIter.Invalidate();
     }
     if (!overflowIncompleteList.IsEmpty()) {
       MergeSortedExcessOverflowContainers(overflowIncompleteList);
     }
   }
   return aBSize;
 }
 
--- a/layout/generic/nsGridContainerFrame.h
+++ b/layout/generic/nsGridContainerFrame.h
@@ -184,30 +184,34 @@ public:
    * @return nullptr if aFrame has no grid container, or frame was destroyed
    * @note this might destroy layout/style data since it may flush layout
    */
   static nsGridContainerFrame* GetGridFrameWithComputedInfo(nsIFrame* aFrame);
 
   struct TrackSize;
   struct GridItemInfo;
   struct GridReflowInput;
+  template<typename Iterator> class GridItemCSSOrderIteratorT;
+  typedef GridItemCSSOrderIteratorT<nsFrameList::iterator>
+    GridItemCSSOrderIterator;
+  typedef GridItemCSSOrderIteratorT<nsFrameList::reverse_iterator>
+    ReverseGridItemCSSOrderIterator;
 protected:
   static const uint32_t kAutoLine;
   // The maximum line number, in the zero-based translated grid.
   static const uint32_t kTranslatedMaxLine;
   typedef mozilla::LogicalPoint LogicalPoint;
   typedef mozilla::LogicalRect LogicalRect;
   typedef mozilla::LogicalSize LogicalSize;
   typedef mozilla::WritingMode WritingMode;
   typedef mozilla::css::GridNamedArea GridNamedArea;
   typedef mozilla::layout::AutoFrameListPtr AutoFrameListPtr;
   typedef nsLayoutUtils::IntrinsicISizeType IntrinsicISizeType;
   struct Grid;
   struct GridArea;
-  class GridItemCSSOrderIterator;
   class LineNameMap;
   struct LineRange;
   struct SharedGridData;
   struct TrackSizingFunctions;
   struct Tracks;
   struct TranslatedLineRange;
   friend nsContainerFrame* NS_NewGridContainerFrame(nsIPresShell* aPresShell,
                                                     nsStyleContext* aContext);