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