path: root/layout/generic/CSSOrderAwareFrameIterator.h

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

/* Iterator class for frame lists that respect CSS "order" during layout */

#ifndef mozilla_CSSOrderAwareFrameIterator_h
#define mozilla_CSSOrderAwareFrameIterator_h

#include <limits>
#include "nsFrameList.h"
#include "nsIFrame.h"
#include "mozilla/Maybe.h"
#include "mozilla/Assertions.h"

namespace mozilla {

/**
 * CSSOrderAwareFrameIteratorT is a base class for iterators that traverse
 * child frame lists in a way that respects their CSS "order" property.
 *   https://drafts.csswg.org/css-flexbox-1/#order-property
 * This class isn't meant to be directly used; instead, use its specializations
 * CSSOrderAwareFrameIterator and ReverseCSSOrderAwareFrameIterator.
 *
 * Client code can use a CSSOrderAwareFrameIterator to traverse lower-"order"
 * frames before higher-"order" ones (as required for correct flex/grid
 * layout), without modifying the frames' actual ordering within the frame
 * tree. Any frames with equal "order" values will be traversed consecutively,
 * in frametree order (which is generally equivalent to DOM order).
 *
 * By default, the iterator will skip past placeholder frames during
 * iteration. You can adjust this behavior via the ChildFilter constructor arg.
 *
 * By default, the iterator will use the frames' CSS "order" property to
 * determine its traversal order. However, it can be customized to instead use
 * the (prefixed) legacy "box-ordinal-group" CSS property instead, as part of
 * emulating "display:-webkit-box" containers. This behavior can be customized
 * using the OrderingProperty constructor arg.
 *
 * A few notes on performance:
 *  - If you're iterating multiple times in a row, it's a good idea to reuse
 * the same iterator (calling Reset() to start each new iteration), rather than
 * instantiating a new one each time.
 *  - If you have foreknowledge of the list's orderedness, you can save some
 * time by passing eKnownOrdered or eKnownUnordered to the constructor (which
 * will skip some checks during construction).
 *
 * Warning: if the given frame list changes, it makes the iterator invalid and
 * bad things will happen if it's used further.
 */
template <typename Iterator>
class CSSOrderAwareFrameIteratorT {
 public:
  enum class OrderState { Unknown, Ordered, Unordered };
  enum class ChildFilter { SkipPlaceholders, IncludeAll };
  enum class OrderingProperty {
    Order,           // Default behavior: use "order".
    BoxOrdinalGroup  // Legacy behavior: use prefixed "box-ordinal-group".
  };
  CSSOrderAwareFrameIteratorT(
      nsIFrame* aContainer, FrameChildListID aListID,
      ChildFilter aFilter = ChildFilter::SkipPlaceholders,
      OrderState aState = OrderState::Unknown,
      OrderingProperty aOrderProp = OrderingProperty::Order)
      : mChildren(aContainer->GetChildList(aListID)),
        mArrayIndex(0),
        mItemIndex(0),
        mSkipPlaceholders(aFilter == ChildFilter::SkipPlaceholders)
#ifdef DEBUG
        ,
        mContainer(aContainer),
        mListID(aListID)
#endif
  {
    MOZ_ASSERT(CanUse(aContainer),
               "Only use this iterator in a container that honors 'order'");

    size_t count = 0;
    bool isOrdered = aState != OrderState::Unordered;
    if (aState == OrderState::Unknown) {
      auto maxOrder = std::numeric_limits<int32_t>::min();
      for (auto* child : mChildren) {
        ++count;

        int32_t order = aOrderProp == OrderingProperty::BoxOrdinalGroup
                            ? child->StyleXUL()->mBoxOrdinal
                            : child->StylePosition()->mOrder;

        if (order < maxOrder) {
          isOrdered = false;
          break;
        }
        maxOrder = order;
      }
    }
    if (isOrdered) {
      mIter.emplace(begin(mChildren));
      mIterEnd.emplace(end(mChildren));
    } else {
      count *= 2;  // XXX somewhat arbitrary estimate for now...
      mArray.emplace(count);
      for (Iterator i(begin(mChildren)), iEnd(end(mChildren)); i != iEnd; ++i) {
        mArray->AppendElement(*i);
      }
      auto comparator = aOrderProp == OrderingProperty::BoxOrdinalGroup
                            ? CSSBoxOrdinalGroupComparator
                            : CSSOrderComparator;
      mArray->StableSort(comparator);
    }

    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }

  CSSOrderAwareFrameIteratorT(CSSOrderAwareFrameIteratorT&&) = default;

  ~CSSOrderAwareFrameIteratorT() {
    MOZ_ASSERT(IsForward() == mItemCount.isNothing());
  }

  bool IsForward() const;

  nsIFrame* get() const {
    MOZ_ASSERT(!AtEnd());
    if (mIter.isSome()) {
      return **mIter;
    }
    return (*mArray)[mArrayIndex];
  }

  nsIFrame* operator*() const { return get(); }

  /**
   * 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 ItemIndex() const {
    MOZ_ASSERT(!AtEnd());
    MOZ_ASSERT(!(**this)->IsPlaceholderFrame(),
               "MUST not call this when at a placeholder");
    MOZ_ASSERT(IsForward() || mItemIndex < *mItemCount,
               "Returning an out-of-range mItemIndex...");
    return mItemIndex;
  }

  void SetItemCount(size_t aItemCount) {
    MOZ_ASSERT(mIter.isSome() || aItemCount <= mArray->Length(),
               "item count mismatch");
    mItemCount.emplace(aItemCount);
    // Note: it's OK if mItemIndex underflows -- ItemIndex()
    // will not be called unless there is at least one item.
    mItemIndex = IsForward() ? 0 : *mItemCount - 1;
  }

  /**
   * Skip over placeholder children.
   */
  void SkipPlaceholders() {
    if (mIter.isSome()) {
      for (; *mIter != *mIterEnd; ++*mIter) {
        nsIFrame* child = **mIter;
        if (!child->IsPlaceholderFrame()) {
          return;
        }
      }
    } else {
      for (; mArrayIndex < mArray->Length(); ++mArrayIndex) {
        nsIFrame* child = (*mArray)[mArrayIndex];
        if (!child->IsPlaceholderFrame()) {
          return;
        }
      }
    }
  }

  bool AtEnd() const {
    MOZ_ASSERT(mIter.isSome() || mArrayIndex <= mArray->Length());
    return mIter ? (*mIter == *mIterEnd) : mArrayIndex >= mArray->Length();
  }

  void Next() {
#ifdef DEBUG
    MOZ_ASSERT(!AtEnd());
    const nsFrameList& list = mContainer->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)->IsPlaceholderFrame()) {
      IsForward() ? ++mItemIndex : --mItemIndex;
    }
    if (mIter.isSome()) {
      ++*mIter;
    } else {
      ++mArrayIndex;
    }
    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }

  void Reset(ChildFilter aFilter = ChildFilter::SkipPlaceholders) {
    if (mIter.isSome()) {
      mIter.reset();
      mIter.emplace(begin(mChildren));
      mIterEnd.reset();
      mIterEnd.emplace(end(mChildren));
    } else {
      mArrayIndex = 0;
    }
    mItemIndex = IsForward() ? 0 : *mItemCount - 1;
    mSkipPlaceholders = aFilter == ChildFilter::SkipPlaceholders;
    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }

  bool IsValid() const { return mIter.isSome() || mArray.isSome(); }

  void Invalidate() {
    mIter.reset();
    mArray.reset();
  }

  bool ItemsAreAlreadyInOrder() const { return mIter.isSome(); }

 private:
  static bool CanUse(const nsIFrame*);

  Iterator begin(const nsFrameList& aList);
  Iterator end(const nsFrameList& aList);

  static int CSSOrderComparator(nsIFrame* const& a, nsIFrame* const& b);
  static int CSSBoxOrdinalGroupComparator(nsIFrame* const& a,
                                          nsIFrame* const& b);

  const nsFrameList& mChildren;
  // Used if child list is already in ascending 'order'.
  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 item (placeholders excluded).
  size_t mItemIndex;
  // The number of items (placeholders excluded).
  // It's only initialized and used in a reverse iterator.
  Maybe<size_t> mItemCount;
  // Skip placeholder children in the iteration?
  bool mSkipPlaceholders;
#ifdef DEBUG
  nsIFrame* mContainer;
  FrameChildListID mListID;
#endif
};

using CSSOrderAwareFrameIterator =
    CSSOrderAwareFrameIteratorT<nsFrameList::iterator>;
using ReverseCSSOrderAwareFrameIterator =
    CSSOrderAwareFrameIteratorT<nsFrameList::reverse_iterator>;

}  // namespace mozilla

#endif  // mozilla_CSSOrderAwareFrameIterator_h