layout/generic/CSSOrderAwareFrameIterator.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /* Iterator class for frame lists that respect CSS "order" during layout */
   8
   9 #ifndef mozilla_CSSOrderAwareFrameIterator_h
  10 #define mozilla_CSSOrderAwareFrameIterator_h
  11
  12 #include <algorithm>
  13 #include "nsFrameList.h"
  14 #include "nsIFrame.h"
  15 #include "mozilla/Maybe.h"
  16 #include "mozilla/Assertions.h"
  17
  18 #if defined(__clang__) && __clang_major__ == 3 && __clang_minor__ <= 9
  19 #  define CLANG_CRASH_BUG 1
  20 #endif
  21
  22 namespace mozilla {
  23
  24 /**
  25  * CSSOrderAwareFrameIteratorT is a base class for iterators that traverse
  26  * child frame lists in a way that respects their CSS "order" property.
  27  *   https://drafts.csswg.org/css-flexbox-1/#order-property
  28  * This class isn't meant to be directly used; instead, use its specializations
  29  * CSSOrderAwareFrameIterator and ReverseCSSOrderAwareFrameIterator.
  30  *
  31  * Client code can use a CSSOrderAwareFrameIterator to traverse lower-"order"
  32  * frames before higher-"order" ones (as required for correct flex/grid
  33  * layout), without modifying the frames' actual ordering within the frame
  34  * tree. Any frames with equal "order" values will be traversed consecutively,
  35  * in frametree order (which is generally equivalent to DOM order).
  36  *
  37  * By default, the iterator will skip past placeholder frames during
  38  * iteration. You can adjust this behavior via the ChildFilter constructor arg.
  39  *
  40  * By default, the iterator will use the frames' CSS "order" property to
  41  * determine its traversal order. However, it can be customized to instead use
  42  * the (prefixed) legacy "box-ordinal-group" CSS property instead, as part of
  43  * emulating "display:-webkit-box" containers. This behavior can be customized
  44  * using the OrderingProperty constructor arg.
  45  *
  46  * A few notes on performance:
  47  *  - If you're iterating multiple times in a row, it's a good idea to reuse
  48  * the same iterator (calling Reset() to start each new iteration), rather than
  49  * instantiating a new one each time.
  50  *  - If you have foreknowledge of the list's orderedness, you can save some
  51  * time by passing eKnownOrdered or eKnownUnordered to the constructor (which
  52  * will skip some checks during construction).
  53  *
  54  * Warning: if the given frame list changes, it makes the iterator invalid and
  55  * bad things will happen if it's used further.
  56  */
  57 template <typename Iterator>
  58 class CSSOrderAwareFrameIteratorT {
  59  public:
  60   enum OrderState { eUnknownOrder, eKnownOrdered, eKnownUnordered };
  61   enum ChildFilter { eSkipPlaceholders, eIncludeAll };
  62   enum OrderingProperty {
  63     eUseOrder,           // Default behavior: use "order".
  64     eUseBoxOrdinalGroup  // Legacy behavior: use prefixed "box-ordinal-group".
  65   };
  66   CSSOrderAwareFrameIteratorT(nsIFrame* aContainer,
  67                               nsIFrame::ChildListID aListID,
  68                               ChildFilter aFilter = eSkipPlaceholders,
  69                               OrderState aState = eUnknownOrder,
  70                               OrderingProperty aOrderProp = eUseOrder)
  71       : mChildren(aContainer->GetChildList(aListID)),
  72         mArrayIndex(0),
  73         mItemIndex(0),
  74         mSkipPlaceholders(aFilter == eSkipPlaceholders)
  75 #ifdef DEBUG
  76         ,
  77         mContainer(aContainer),
  78         mListID(aListID)
  79 #endif
  80   {
  81     MOZ_ASSERT(aContainer->IsFlexOrGridContainer(),
  82                "Only use this iterator in a container that honors 'order'");
  83
  84     size_t count = 0;
  85     bool isOrdered = aState != eKnownUnordered;
  86     if (aState == eUnknownOrder) {
  87       auto maxOrder = std::numeric_limits<int32_t>::min();
  88       for (auto child : mChildren) {
  89         ++count;
  90
  91         int32_t order;
  92         if (aOrderProp == eUseBoxOrdinalGroup) {
  93           // We'll be using mBoxOrdinal, which has type uint32_t. However, the
  94           // modern 'order' property (whose functionality we're co-opting) has
  95           // type int32_t.  So: if we happen to have a uint32_t value that's
  96           // greater than INT32_MAX, we clamp it rather than letting it
  97           // overflow. Chances are, this is just an author using BIG_VALUE
  98           // anyway, so the clamped value should be fine.
  99           uint32_t clampedBoxOrdinal = std::min(
 100               child->StyleXUL()->mBoxOrdinal, static_cast<uint32_t>(INT32_MAX));
 101           order = static_cast<int32_t>(clampedBoxOrdinal);
 102         } else {
 103           order = child->StylePosition()->mOrder;
 104         }
 105
 106         if (order < maxOrder) {
 107           isOrdered = false;
 108           break;
 109         }
 110         maxOrder = order;
 111       }
 112     }
 113     if (isOrdered) {
 114       mIter.emplace(begin(mChildren));
 115       mIterEnd.emplace(end(mChildren));
 116     } else {
 117       count *= 2;  // XXX somewhat arbitrary estimate for now...
 118       mArray.emplace(count);
 119       for (Iterator i(begin(mChildren)), iEnd(end(mChildren)); i != iEnd; ++i) {
 120         mArray->AppendElement(*i);
 121       }
 122       auto comparator = (aOrderProp == eUseBoxOrdinalGroup)
 123                             ? CSSBoxOrdinalGroupComparator
 124                             : CSSOrderComparator;
 125
 126       // XXX replace this with nsTArray::StableSort when bug 1147091 is fixed.
 127       std::stable_sort(mArray->begin(), mArray->end(), comparator);
 128     }
 129
 130     if (mSkipPlaceholders) {
 131       SkipPlaceholders();
 132     }
 133   }
 134   ~CSSOrderAwareFrameIteratorT() {
 135     MOZ_ASSERT(IsForward() == mItemCount.isNothing());
 136   }
 137
 138   bool IsForward() const;
 139   Iterator begin(const nsFrameList& aList);
 140   Iterator end(const nsFrameList& aList);
 141
 142   nsIFrame* operator*() const {
 143     MOZ_ASSERT(!AtEnd());
 144     if (mIter.isSome()) {
 145       return **mIter;
 146     }
 147     return (*mArray)[mArrayIndex];
 148   }
 149
 150   /**
 151    * Return the child index of the current item, placeholders not counted.
 152    * It's forbidden to call this method when the current frame is placeholder.
 153    */
 154   size_t ItemIndex() const {
 155     MOZ_ASSERT(!AtEnd());
 156     MOZ_ASSERT(!(**this)->IsPlaceholderFrame(),
 157                "MUST not call this when at a placeholder");
 158     MOZ_ASSERT(IsForward() || mItemIndex < *mItemCount,
 159                "Returning an out-of-range mItemIndex...");
 160     return mItemIndex;
 161   }
 162
 163   void SetItemCount(size_t aItemCount) {
 164 #ifndef CLANG_CRASH_BUG
 165     MOZ_ASSERT(mIter.isSome() || aItemCount <= mArray->Length(),
 166                "item count mismatch");
 167 #endif
 168     mItemCount.emplace(aItemCount);
 169     // Note: it's OK if mItemIndex underflows -- ItemIndex()
 170     // will not be called unless there is at least one item.
 171     mItemIndex = IsForward() ? 0 : *mItemCount - 1;
 172   }
 173
 174   /**
 175    * Skip over placeholder children.
 176    */
 177   void SkipPlaceholders() {
 178     if (mIter.isSome()) {
 179       for (; *mIter != *mIterEnd; ++*mIter) {
 180         nsIFrame* child = **mIter;
 181         if (!child->IsPlaceholderFrame()) {
 182           return;
 183         }
 184       }
 185     } else {
 186       for (; mArrayIndex < mArray->Length(); ++mArrayIndex) {
 187         nsIFrame* child = (*mArray)[mArrayIndex];
 188         if (!child->IsPlaceholderFrame()) {
 189           return;
 190         }
 191       }
 192     }
 193   }
 194
 195   bool AtEnd() const {
 196 #ifndef CLANG_CRASH_BUG
 197     // Clang 3.6.2 crashes when compiling this assertion:
 198     MOZ_ASSERT(mIter.isSome() || mArrayIndex <= mArray->Length());
 199 #endif
 200     return mIter ? (*mIter == *mIterEnd) : mArrayIndex >= mArray->Length();
 201   }
 202
 203   void Next() {
 204 #ifdef DEBUG
 205     MOZ_ASSERT(!AtEnd());
 206     nsFrameList list = mContainer->GetChildList(mListID);
 207     MOZ_ASSERT(list.FirstChild() == mChildren.FirstChild() &&
 208                    list.LastChild() == mChildren.LastChild(),
 209                "the list of child frames must not change while iterating!");
 210 #endif
 211     if (mSkipPlaceholders || !(**this)->IsPlaceholderFrame()) {
 212       IsForward() ? ++mItemIndex : --mItemIndex;
 213     }
 214     if (mIter.isSome()) {
 215       ++*mIter;
 216     } else {
 217       ++mArrayIndex;
 218     }
 219     if (mSkipPlaceholders) {
 220       SkipPlaceholders();
 221     }
 222   }
 223
 224   void Reset(ChildFilter aFilter = eSkipPlaceholders) {
 225     if (mIter.isSome()) {
 226       mIter.reset();
 227       mIter.emplace(begin(mChildren));
 228       mIterEnd.reset();
 229       mIterEnd.emplace(end(mChildren));
 230     } else {
 231       mArrayIndex = 0;
 232     }
 233     mItemIndex = IsForward() ? 0 : *mItemCount - 1;
 234     mSkipPlaceholders = aFilter == eSkipPlaceholders;
 235     if (mSkipPlaceholders) {
 236       SkipPlaceholders();
 237     }
 238   }
 239
 240   bool IsValid() const { return mIter.isSome() || mArray.isSome(); }
 241
 242   void Invalidate() {
 243     mIter.reset();
 244     mArray.reset();
 245     mozWritePoison(&mChildren, sizeof(mChildren));
 246   }
 247
 248   bool ItemsAreAlreadyInOrder() const { return mIter.isSome(); }
 249
 250   static bool CSSOrderComparator(nsIFrame* const& a, nsIFrame* const& b);
 251   static bool CSSBoxOrdinalGroupComparator(nsIFrame* const& a,
 252                                            nsIFrame* const& b);
 253
 254  private:
 255   nsFrameList mChildren;
 256   // Used if child list is already in ascending 'order'.
 257   Maybe<Iterator> mIter;
 258   Maybe<Iterator> mIterEnd;
 259   // Used if child list is *not* in ascending 'order'.
 260   // This array is pre-sorted in reverse order for a reverse iterator.
 261   Maybe<nsTArray<nsIFrame*>> mArray;
 262   size_t mArrayIndex;
 263   // The index of the current item (placeholders excluded).
 264   size_t mItemIndex;
 265   // The number of items (placeholders excluded).
 266   // It's only initialized and used in a reverse iterator.
 267   Maybe<size_t> mItemCount;
 268   // Skip placeholder children in the iteration?
 269   bool mSkipPlaceholders;
 270 #ifdef DEBUG
 271   nsIFrame* mContainer;
 272   nsIFrame::ChildListID mListID;
 273 #endif
 274 };
 275
 276 typedef CSSOrderAwareFrameIteratorT<nsFrameList::iterator>
 277     CSSOrderAwareFrameIterator;
 278 typedef CSSOrderAwareFrameIteratorT<nsFrameList::reverse_iterator>
 279     ReverseCSSOrderAwareFrameIterator;
 280
 281 }  // namespace mozilla
 282
 283 #endif  // mozilla_CSSOrderAwareFrameIterator_h