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/. */
7 #ifndef nsFrameList_h___
8 #define nsFrameList_h___
10 #include <stdio.h> /* for FILE* */
13 #include "mozilla/EnumSet.h"
14 #include "mozilla/FunctionTypeTraits.h"
15 #include "mozilla/RefPtr.h"
17 #if defined(DEBUG) || defined(MOZ_DUMP_PAINTING) || defined(MOZ_LAYOUT_DEBUGGER)
18 // DEBUG_FRAME_DUMP enables nsIFrame::List and related methods.
19 // You can also define this in a non-DEBUG build if you need frame dumps.
20 # define DEBUG_FRAME_DUMP 1
23 class nsContainerFrame
;
30 struct FrameDestroyContext
;
34 enum class FrameChildListID
{
35 // The individual concrete child lists.
44 ExcessOverflowContainers
,
50 // A special alias for FrameChildListID::Principal that suppress the reflow
51 // request that is normally done when manipulating child lists.
55 } // namespace mozilla
57 // Uncomment this to enable expensive frame-list integrity checking
58 // #define DEBUG_FRAME_LIST
61 * A class for managing a list of frames.
64 // Next()/Prev() need to know about nsIFrame. To make them inline, their
65 // implementations are in nsIFrame.h.
66 struct ForwardFrameTraversal final
{
67 static inline nsIFrame
* Next(nsIFrame
*);
68 static inline nsIFrame
* Prev(nsIFrame
*);
70 struct BackwardFrameTraversal final
{
71 static inline nsIFrame
* Next(nsIFrame
*);
72 static inline nsIFrame
* Prev(nsIFrame
*);
76 template <typename FrameTraversal
>
80 using iterator
= Iterator
<ForwardFrameTraversal
>;
81 using const_iterator
= Iterator
<ForwardFrameTraversal
>;
82 using reverse_iterator
= Iterator
<BackwardFrameTraversal
>;
83 using const_reverse_iterator
= Iterator
<BackwardFrameTraversal
>;
85 nsFrameList() : mFirstChild(nullptr), mLastChild(nullptr) {}
87 nsFrameList(nsIFrame
* aFirstFrame
, nsIFrame
* aLastFrame
)
88 : mFirstChild(aFirstFrame
), mLastChild(aLastFrame
) {
92 // nsFrameList is a move-only class by default. Use Clone() if you really want
93 // a copy of this list.
94 nsFrameList(const nsFrameList
& aOther
) = delete;
95 nsFrameList
& operator=(const nsFrameList
& aOther
) = delete;
96 nsFrameList
Clone() const { return nsFrameList(mFirstChild
, mLastChild
); }
99 * Transfer frames in aOther to this list. aOther becomes empty after this
102 nsFrameList(nsFrameList
&& aOther
)
103 : mFirstChild(aOther
.mFirstChild
), mLastChild(aOther
.mLastChild
) {
107 nsFrameList
& operator=(nsFrameList
&& aOther
) {
108 if (this != &aOther
) {
109 MOZ_ASSERT(IsEmpty(), "Assigning to a non-empty list will lose frames!");
110 mFirstChild
= aOther
.FirstChild();
111 mLastChild
= aOther
.LastChild();
118 * Infallibly allocate a nsFrameList from the shell arena.
120 void* operator new(size_t sz
, mozilla::PresShell
* aPresShell
);
123 * Deallocate this list that was allocated from the shell arena.
124 * The list is required to be empty.
126 void Delete(mozilla::PresShell
* aPresShell
);
129 * For each frame in this list: remove it from the list then call
130 * Destroy() on it with the passed context as an argument.
132 void DestroyFrames(mozilla::FrameDestroyContext
&);
134 void Clear() { mFirstChild
= mLastChild
= nullptr; }
137 * Append aFrameList to this list. If aParent is not null,
138 * reparents the newly added frames. Clears out aFrameList and
139 * returns a list slice represening the newly-appended frames.
141 Slice
AppendFrames(nsContainerFrame
* aParent
, nsFrameList
&& aFrameList
) {
142 return InsertFrames(aParent
, LastChild(), std::move(aFrameList
));
146 * Append aFrame to this list. If aParent is not null,
147 * reparents the newly added frame.
149 void AppendFrame(nsContainerFrame
* aParent
, nsIFrame
* aFrame
) {
150 AppendFrames(aParent
, nsFrameList(aFrame
, aFrame
));
154 * Take aFrame out of the frame list. This also disconnects aFrame
155 * from the sibling list. The frame must be non-null and present on
158 void RemoveFrame(nsIFrame
* aFrame
);
161 * Take all the frames before aFrame out of the frame list; aFrame and all the
162 * frames after it stay in this list. If aFrame is nullptr, remove the entire
164 * @param aFrame a frame in this frame list, or nullptr.
165 * @return the removed frames, if any.
167 [[nodiscard
]] nsFrameList
TakeFramesBefore(nsIFrame
* aFrame
);
170 * Take all the frames after aFrame out of the frame list; aFrame and all the
171 * frames before it stay in this list. If aFrame is nullptr, removes the
173 * @param aFrame a frame in this list, or nullptr.
174 * @return the removed frames, if any.
176 [[nodiscard
]] nsFrameList
TakeFramesAfter(nsIFrame
* aFrame
);
179 * Take the first frame (if any) out of the frame list.
180 * @return the first child, or nullptr if the list is empty
182 nsIFrame
* RemoveFirstChild();
185 * The following two functions are intended to be used in concert for
186 * removing a frame from its frame list when the set of possible frame
187 * lists is known in advance, but the exact frame list is unknown.
188 * aFrame must be non-null.
190 * bool removed = frameList1.StartRemoveFrame(aFrame) ||
191 * frameList2.ContinueRemoveFrame(aFrame) ||
192 * frameList3.ContinueRemoveFrame(aFrame);
193 * MOZ_ASSERT(removed);
195 * @note One of the frame lists MUST contain aFrame, if it's on some other
196 * frame list then the example above will likely lead to crashes.
197 * This function is O(1).
198 * @return true iff aFrame was removed from /some/ list, not necessarily
199 * this one. If it was removed from a different list then it is
200 * guaranteed that that list is still non-empty.
201 * (this method is implemented in nsIFrame.h to be able to inline)
203 inline bool StartRemoveFrame(nsIFrame
* aFrame
);
206 * Precondition: StartRemoveFrame MUST be called before this.
207 * This function is O(1).
208 * @see StartRemoveFrame
209 * @return true iff aFrame was removed from this list
210 * (this method is implemented in nsIFrame.h to be able to inline)
212 inline bool ContinueRemoveFrame(nsIFrame
* aFrame
);
215 * Take a frame out of the frame list and then destroy it.
216 * The frame must be non-null and present on this list.
218 void DestroyFrame(mozilla::FrameDestroyContext
&, nsIFrame
*);
221 * Insert aFrame right after aPrevSibling, or prepend it to this
222 * list if aPrevSibling is null. If aParent is not null, also
223 * reparents newly-added frame. Note that this method always
224 * sets the frame's nextSibling pointer.
226 void InsertFrame(nsContainerFrame
* aParent
, nsIFrame
* aPrevSibling
,
228 InsertFrames(aParent
, aPrevSibling
, nsFrameList(aFrame
, aFrame
));
232 * Inserts aFrameList into this list after aPrevSibling (at the beginning if
233 * aPrevSibling is null). If aParent is not null, reparents the newly added
234 * frames. Clears out aFrameList and returns a list slice representing the
235 * newly-inserted frames.
237 Slice
InsertFrames(nsContainerFrame
* aParent
, nsIFrame
* aPrevSibling
,
238 nsFrameList
&& aFrameList
);
241 * Split this list just before the first frame that matches aPredicate,
242 * and return a nsFrameList containing all the frames before it. The
243 * matched frame and all frames after it stay in this list. If no matched
244 * frame exists, all the frames are drained into the returned list, and
245 * this list ends up empty.
247 * aPredicate should be of this function signature: bool(nsIFrame*).
249 template <typename Predicate
>
250 nsFrameList
Split(Predicate
&& aPredicate
) {
253 typename
mozilla::FunctionTypeTraits
<Predicate
>::ReturnType
,
255 mozilla::FunctionTypeTraits
<Predicate
>::arity
== 1 &&
256 std::is_same
<typename
mozilla::FunctionTypeTraits
<
257 Predicate
>::template ParameterType
<0>,
259 "aPredicate should be of this function signature: bool(nsIFrame*)");
261 for (nsIFrame
* f
: *this) {
263 return TakeFramesBefore(f
);
266 return std::move(*this);
269 nsIFrame
* FirstChild() const { return mFirstChild
; }
271 nsIFrame
* LastChild() const { return mLastChild
; }
273 nsIFrame
* FrameAt(int32_t aIndex
) const;
274 int32_t IndexOf(nsIFrame
* aFrame
) const;
276 bool IsEmpty() const { return nullptr == mFirstChild
; }
278 bool NotEmpty() const { return nullptr != mFirstChild
; }
281 * Return true if aFrame is on this list.
282 * @note this method has O(n) time complexity over the length of the list
283 * XXXmats: ideally, we should make this function #ifdef DEBUG
285 bool ContainsFrame(const nsIFrame
* aFrame
) const;
288 * Get the number of frames in this list. Note that currently the
289 * implementation has O(n) time complexity. Do not call it repeatedly in hot
291 * XXXmats: ideally, we should make this function #ifdef DEBUG
293 int32_t GetLength() const;
296 * If this frame list has only one frame, return that frame.
297 * Otherwise, return null.
299 nsIFrame
* OnlyChild() const {
300 if (FirstChild() == LastChild()) {
307 * Call SetParent(aParent) for each frame in this list.
308 * @param aParent the new parent frame, must be non-null
310 void ApplySetParent(nsContainerFrame
* aParent
) const;
313 * If this frame list is non-empty then append it to aLists as the
314 * aListID child list.
316 inline void AppendIfNonempty(nsTArray
<mozilla::FrameChildList
>* aLists
,
317 mozilla::FrameChildListID aListID
) const {
319 aLists
->EmplaceBack(*this, aListID
);
324 * Return the frame before this frame in visual order (after Bidi reordering).
325 * If aFrame is null, return the last frame in visual order.
327 nsIFrame
* GetPrevVisualFor(nsIFrame
* aFrame
) const;
330 * Return the frame after this frame in visual order (after Bidi reordering).
331 * If aFrame is null, return the first frame in visual order.
333 nsIFrame
* GetNextVisualFor(nsIFrame
* aFrame
) const;
335 #ifdef DEBUG_FRAME_DUMP
336 void List(FILE* out
) const;
339 static inline const nsFrameList
& EmptyList();
342 * A class representing a slice of a frame list.
346 // Implicit on purpose, so that we can easily create Slice from nsFrameList
347 // via this impicit constructor.
348 MOZ_IMPLICIT
Slice(const nsFrameList
& aList
)
349 : mStart(aList
.FirstChild()), mEnd(nullptr) {}
350 Slice(nsIFrame
* aStart
, nsIFrame
* aEnd
) : mStart(aStart
), mEnd(aEnd
) {}
352 iterator
begin() const { return iterator(mStart
); }
353 const_iterator
cbegin() const { return begin(); }
354 iterator
end() const { return iterator(mEnd
); }
355 const_iterator
cend() const { return end(); }
358 // Our starting frame.
359 nsIFrame
* const mStart
;
361 // The first frame that is NOT in the slice. May be null.
362 nsIFrame
* const mEnd
;
365 template <typename FrameTraversal
>
366 class Iterator final
{
368 // It is disputable whether these type definitions are correct, since
369 // operator* doesn't return a reference at all. Also, the iterator_category
370 // can be at most std::input_iterator_tag (rather than
371 // std::bidrectional_iterator_tag, as it might seem), because it is a
372 // stashing iterator. See also, e.g.,
373 // https://stackoverflow.com/questions/50909701/what-should-be-iterator-category-for-a-stashing-iterator
374 using value_type
= nsIFrame
* const;
375 using pointer
= value_type
*;
376 using reference
= value_type
&;
377 using difference_type
= ptrdiff_t;
378 using iterator_category
= std::input_iterator_tag
;
380 explicit constexpr Iterator(nsIFrame
* aCurrent
) : mCurrent(aCurrent
) {}
382 nsIFrame
* operator*() const { return mCurrent
; }
384 Iterator
& operator++() {
385 mCurrent
= FrameTraversal::Next(mCurrent
);
388 Iterator
& operator--() {
389 mCurrent
= FrameTraversal::Prev(mCurrent
);
393 Iterator
operator++(int) {
398 Iterator
operator--(int) {
404 bool operator==(const Iterator
<FrameTraversal
>& aOther
) const {
405 return mCurrent
== aOther
.mCurrent
;
408 bool operator!=(const Iterator
<FrameTraversal
>& aOther
) const {
409 return !(*this == aOther
);
416 iterator
begin() const { return iterator(mFirstChild
); }
417 const_iterator
cbegin() const { return begin(); }
418 iterator
end() const { return iterator(nullptr); }
419 const_iterator
cend() const { return end(); }
420 reverse_iterator
rbegin() const { return reverse_iterator(mLastChild
); }
421 const_reverse_iterator
crbegin() const { return rbegin(); }
422 reverse_iterator
rend() const { return reverse_iterator(nullptr); }
423 const_reverse_iterator
crend() const { return rend(); }
426 void operator delete(void*) = delete;
428 #ifdef DEBUG_FRAME_LIST
429 void VerifyList() const;
431 void VerifyList() const {}
436 * Disconnect aFrame from its siblings. This must only be called if aFrame
437 * is NOT the first or last sibling, because otherwise its nsFrameList will
438 * have a stale mFirst/LastChild pointer. This precondition is asserted.
439 * This function is O(1).
441 static void UnhookFrameFromSiblings(nsIFrame
* aFrame
);
443 nsIFrame
* mFirstChild
;
444 nsIFrame
* mLastChild
;
449 #ifdef DEBUG_FRAME_DUMP
450 extern const char* ChildListName(FrameChildListID aListID
);
453 using FrameChildListIDs
= EnumSet
<FrameChildListID
>;
455 class FrameChildList
{
457 FrameChildList(const nsFrameList
& aList
, FrameChildListID aID
)
458 : mList(aList
.Clone()), mID(aID
) {}
460 FrameChildListID mID
;
464 * Simple "auto_ptr" for nsFrameLists allocated from the shell arena.
465 * The frame list given to the constructor will be deallocated (if non-null)
466 * in the destructor. The frame list must then be empty.
468 class MOZ_RAII AutoFrameListPtr final
{
470 AutoFrameListPtr(nsPresContext
* aPresContext
, nsFrameList
* aFrameList
)
471 : mPresContext(aPresContext
), mFrameList(aFrameList
) {}
473 operator nsFrameList
*() const { return mFrameList
; }
474 nsFrameList
* operator->() const { return mFrameList
; }
477 nsPresContext
* mPresContext
;
478 nsFrameList
* mFrameList
;
482 union AlignedFrameListBytes
{
484 char bytes
[sizeof(nsFrameList
)];
486 extern const AlignedFrameListBytes gEmptyFrameListBytes
;
487 } // namespace detail
489 } // namespace mozilla
491 /* static */ inline const nsFrameList
& nsFrameList::EmptyList() {
492 return *reinterpret_cast<const nsFrameList
*>(
493 &mozilla::detail::gEmptyFrameListBytes
);
496 #endif /* nsFrameList_h___ */