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