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 419834 bb3080bc1aad672b53575dc983f1bd2c3e1718a0
parent 419833 83a86d52b0388f1eae91109ce393a12bd4a0dd9e
child 419835 33bd454be96a44c66a1651f3e1b4d098e4f45f07
push id31023
push usercykesiopka.bmo@gmail.com
push dateSat, 01 Oct 2016 01:30:33 +0000
reviewersdholbert
bugs1151204
milestone52.0a1
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);