tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

CSSOrderAwareFrameIterator.h (9031B)

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