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, nsIFrame::ChildListID 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 ~CSSOrderAwareFrameIteratorT()120 ~CSSOrderAwareFrameIteratorT() { 121 MOZ_ASSERT(IsForward() == mItemCount.isNothing()); 122 } 123 124 bool IsForward() const; 125 get()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 */ ItemIndex()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 SetItemCount(size_t aItemCount)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 */ SkipPlaceholders()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 AtEnd()179 bool AtEnd() const { 180 MOZ_ASSERT(mIter.isSome() || mArrayIndex <= mArray->Length()); 181 return mIter ? (*mIter == *mIterEnd) : mArrayIndex >= mArray->Length(); 182 } 183 Next()184 void Next() { 185 #ifdef DEBUG 186 MOZ_ASSERT(!AtEnd()); 187 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 IsValid()221 bool IsValid() const { return mIter.isSome() || mArray.isSome(); } 222 Invalidate()223 void Invalidate() { 224 mIter.reset(); 225 mArray.reset(); 226 mozWritePoison(&mChildren, sizeof(mChildren)); 227 } 228 ItemsAreAlreadyInOrder()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 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 nsIFrame::ChildListID 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 270