summaryrefslogtreecommitdiffstats
path: root/layout/generic/CSSOrderAwareFrameIterator.h
diff options
context:
space:
mode:
Diffstat (limited to 'layout/generic/CSSOrderAwareFrameIterator.h')
-rw-r--r--layout/generic/CSSOrderAwareFrameIterator.h268
1 files changed, 268 insertions, 0 deletions
diff --git a/layout/generic/CSSOrderAwareFrameIterator.h b/layout/generic/CSSOrderAwareFrameIterator.h
new file mode 100644
index 0000000000..8ad5cb65b2
--- /dev/null
+++ b/layout/generic/CSSOrderAwareFrameIterator.h
@@ -0,0 +1,268 @@
+/* -*- 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