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/FunctionTypeTraits.h"
14 #include "mozilla/RefPtr.h"
15 #include "mozilla/ReverseIterator.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
;
32 enum FrameChildListID
{
33 // The individual concrete child lists.
42 kOverflowContainersList
,
43 kExcessOverflowContainersList
,
44 kOverflowOutOfFlowList
,
49 // A special alias for kPrincipalList that suppress the reflow request that
50 // is normally done when manipulating child lists.
51 kNoReflowPrincipalList
,
54 // A helper class for nsIFrame::Destroy[From]. It's defined here because
55 // nsFrameList needs it and we can't use nsIFrame here.
56 struct PostFrameDestroyData
{
57 PostFrameDestroyData(const PostFrameDestroyData
&) = delete;
58 PostFrameDestroyData() = default;
60 AutoTArray
<RefPtr
<nsIContent
>, 100> mAnonymousContent
;
61 void AddAnonymousContent(already_AddRefed
<nsIContent
>&& aContent
) {
62 mAnonymousContent
.AppendElement(aContent
);
66 } // namespace mozilla
68 // Uncomment this to enable expensive frame-list integrity checking
69 // #define DEBUG_FRAME_LIST
72 * A class for managing a list of frames.
76 nsFrameList() : mFirstChild(nullptr), mLastChild(nullptr) {}
78 nsFrameList(nsIFrame
* aFirstFrame
, nsIFrame
* aLastFrame
)
79 : mFirstChild(aFirstFrame
), mLastChild(aLastFrame
) {
83 // XXX: Ideally, copy constructor should be removed because a frame should be
85 nsFrameList(const nsFrameList
& aOther
) = default;
87 // XXX: ideally, copy assignment should be removed because we should use move
88 // assignment to transfer the ownership.
89 nsFrameList
& operator=(const nsFrameList
& aOther
) = default;
92 * Move the frames in aOther to this list. aOther becomes empty after this
95 nsFrameList(nsFrameList
&& aOther
)
96 : mFirstChild(aOther
.mFirstChild
), mLastChild(aOther
.mLastChild
) {
100 nsFrameList
& operator=(nsFrameList
&& aOther
) {
106 * Infallibly allocate a nsFrameList from the shell arena.
108 void* operator new(size_t sz
, mozilla::PresShell
* aPresShell
);
111 * Deallocate this list that was allocated from the shell arena.
112 * The list is required to be empty.
114 void Delete(mozilla::PresShell
* aPresShell
);
117 * For each frame in this list: remove it from the list then call
120 void DestroyFrames();
123 * For each frame in this list: remove it from the list then call
124 * DestroyFrom(aDestructRoot, aPostDestroyData) on it.
126 void DestroyFramesFrom(
127 nsIFrame
* aDestructRoot
,
128 mozilla::layout::PostFrameDestroyData
& aPostDestroyData
);
130 void Clear() { mFirstChild
= mLastChild
= nullptr; }
132 void SetFrames(nsIFrame
* aFrameList
);
134 void SetFrames(nsFrameList
& aFrameList
) {
135 MOZ_ASSERT(!mFirstChild
, "Losing frames");
137 mFirstChild
= aFrameList
.FirstChild();
138 mLastChild
= aFrameList
.LastChild();
145 * Append aFrameList to this list. If aParent is not null,
146 * reparents the newly added frames. Clears out aFrameList and
147 * returns a list slice represening the newly-appended frames.
149 Slice
AppendFrames(nsContainerFrame
* aParent
, nsFrameList
& aFrameList
) {
150 return InsertFrames(aParent
, LastChild(), aFrameList
);
154 * Append aFrame to this list. If aParent is not null,
155 * reparents the newly added frame.
157 void AppendFrame(nsContainerFrame
* aParent
, nsIFrame
* aFrame
) {
158 nsFrameList
temp(aFrame
, aFrame
);
159 AppendFrames(aParent
, temp
);
163 * Take aFrame out of the frame list. This also disconnects aFrame
164 * from the sibling list. The frame must be non-null and present on
167 void RemoveFrame(nsIFrame
* aFrame
);
170 * Take the frames after aAfterFrame out of the frame list. If
171 * aAfterFrame is null, removes the entire list.
172 * @param aAfterFrame a frame in this list, or null
173 * @return the removed frames, if any
175 nsFrameList
RemoveFramesAfter(nsIFrame
* aAfterFrame
);
178 * Take the first frame (if any) out of the frame list.
179 * @return the first child, or nullptr if the list is empty
181 nsIFrame
* RemoveFirstChild();
184 * The following two functions are intended to be used in concert for
185 * removing a frame from its frame list when the set of possible frame
186 * lists is known in advance, but the exact frame list is unknown.
187 * aFrame must be non-null.
189 * bool removed = frameList1.StartRemoveFrame(aFrame) ||
190 * frameList2.ContinueRemoveFrame(aFrame) ||
191 * frameList3.ContinueRemoveFrame(aFrame);
192 * MOZ_ASSERT(removed);
194 * @note One of the frame lists MUST contain aFrame, if it's on some other
195 * frame list then the example above will likely lead to crashes.
196 * This function is O(1).
197 * @return true iff aFrame was removed from /some/ list, not necessarily
198 * this one. If it was removed from a different list then it is
199 * guaranteed that that list is still non-empty.
200 * (this method is implemented in nsIFrame.h to be able to inline)
202 inline bool StartRemoveFrame(nsIFrame
* aFrame
);
205 * Precondition: StartRemoveFrame MUST be called before this.
206 * This function is O(1).
207 * @see StartRemoveFrame
208 * @return true iff aFrame was removed from this list
209 * (this method is implemented in nsIFrame.h to be able to inline)
211 inline bool ContinueRemoveFrame(nsIFrame
* aFrame
);
214 * Take aFrame out of the frame list and then destroy it.
215 * The frame must be non-null and present on this list.
217 void DestroyFrame(nsIFrame
* aFrame
);
220 * Insert aFrame right after aPrevSibling, or prepend it to this
221 * list if aPrevSibling is null. If aParent is not null, also
222 * reparents newly-added frame. Note that this method always
223 * sets the frame's nextSibling pointer.
225 void InsertFrame(nsContainerFrame
* aParent
, nsIFrame
* aPrevSibling
,
227 nsFrameList
temp(aFrame
, aFrame
);
228 InsertFrames(aParent
, aPrevSibling
, temp
);
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
);
240 class FrameLinkEnumerator
;
243 * Split this list just before the first frame that matches aPredicate,
244 * and return a nsFrameList containing all the frames before it. The
245 * matched frame and all frames after it stay in this list. If no matched
246 * frame exists, all the frames are drained into the returned list, and
247 * this list ends up empty.
249 * aPredicate should be of this function signature: bool(nsIFrame*).
251 template <typename Predicate
>
252 nsFrameList
Split(Predicate
&& aPredicate
) {
255 typename
mozilla::FunctionTypeTraits
<Predicate
>::ReturnType
,
257 mozilla::FunctionTypeTraits
<Predicate
>::arity
== 1 &&
258 std::is_same
<typename
mozilla::FunctionTypeTraits
<
259 Predicate
>::template ParameterType
<0>,
261 "aPredicate should be of this function signature: bool(nsIFrame*)");
263 FrameLinkEnumerator
link(*this);
264 link
.Find(aPredicate
);
265 return ExtractHead(link
);
269 * Split this frame list such that all the frames before the link pointed to
270 * by aLink end up in the returned list, while the remaining frames stay in
271 * this list. After this call, aLink points to the beginning of this list.
273 nsFrameList
ExtractHead(FrameLinkEnumerator
& aLink
);
276 * Split this frame list such that all the frames coming after the link
277 * pointed to by aLink end up in the returned list, while the frames before
278 * that link stay in this list. After this call, aLink is at end.
280 nsFrameList
ExtractTail(FrameLinkEnumerator
& aLink
);
282 nsIFrame
* FirstChild() const { return mFirstChild
; }
284 nsIFrame
* LastChild() const { return mLastChild
; }
286 nsIFrame
* FrameAt(int32_t aIndex
) const;
287 int32_t IndexOf(nsIFrame
* aFrame
) const;
289 bool IsEmpty() const { return nullptr == mFirstChild
; }
291 bool NotEmpty() const { return nullptr != mFirstChild
; }
294 * Return true if aFrame is on this list.
295 * @note this method has O(n) time complexity over the length of the list
296 * XXXmats: ideally, we should make this function #ifdef DEBUG
298 bool ContainsFrame(const nsIFrame
* aFrame
) const;
301 * Get the number of frames in this list. Note that currently the
302 * implementation has O(n) time complexity. Do not call it repeatedly in hot
304 * XXXmats: ideally, we should make this function #ifdef DEBUG
306 int32_t GetLength() const;
309 * If this frame list has only one frame, return that frame.
310 * Otherwise, return null.
312 nsIFrame
* OnlyChild() const {
313 if (FirstChild() == LastChild()) {
320 * Call SetParent(aParent) for each frame in this list.
321 * @param aParent the new parent frame, must be non-null
323 void ApplySetParent(nsContainerFrame
* aParent
) const;
326 * If this frame list is non-empty then append it to aLists as the
327 * aListID child list.
328 * (this method is implemented in FrameChildList.h for dependency reasons)
330 inline void AppendIfNonempty(
331 nsTArray
<mozilla::layout::FrameChildList
>* aLists
,
332 mozilla::layout::FrameChildListID aListID
) const;
335 * Return the frame before this frame in visual order (after Bidi reordering).
336 * If aFrame is null, return the last frame in visual order.
338 nsIFrame
* GetPrevVisualFor(nsIFrame
* aFrame
) const;
341 * Return the frame after this frame in visual order (after Bidi reordering).
342 * If aFrame is null, return the first frame in visual order.
344 nsIFrame
* GetNextVisualFor(nsIFrame
* aFrame
) const;
346 #ifdef DEBUG_FRAME_DUMP
347 void List(FILE* out
) const;
350 static inline const nsFrameList
& EmptyList();
355 * A class representing a slice of a frame list.
358 friend class Enumerator
;
361 // Implicit on purpose, so that we can easily create enumerators from
362 // nsFrameList via this impicit constructor.
363 MOZ_IMPLICIT
Slice(const nsFrameList
& aList
)
368 mStart(aList
.FirstChild()),
372 Slice(const nsFrameList
& aList
, nsIFrame
* aStart
, nsIFrame
* aEnd
)
381 Slice(const Slice
& aOther
) = default;
385 const nsFrameList
& mList
;
387 nsIFrame
* const mStart
; // our starting frame
388 const nsIFrame
* const mEnd
; // The first frame that is NOT in the slice.
394 explicit Enumerator(const Slice
& aSlice
)
399 mFrame(aSlice
.mStart
),
403 Enumerator(const Enumerator
& aOther
) = default;
406 // Can't just check mEnd, because some table code goes and destroys the
407 // tail of the frame list (including mEnd!) while iterating over the
409 return !mFrame
|| mFrame
== mEnd
;
412 /* Next() needs to know about nsIFrame, and nsIFrame will need to
413 know about nsFrameList methods, so in order to inline this put
414 the implementation in nsIFrame.h */
418 * Get the current frame we're pointing to. Do not call this on an
419 * iterator that is at end!
421 nsIFrame
* get() const {
422 MOZ_ASSERT(!AtEnd(), "Enumerator is at end");
427 * Get an enumerator that is just like this one, but not limited in terms of
428 * the part of the list it will traverse.
430 Enumerator
GetUnlimitedEnumerator() const {
431 return Enumerator(*this, nullptr);
435 const nsFrameList
& List() const { return mSlice
.mList
; }
439 Enumerator(const Enumerator
& aOther
, const nsIFrame
* const aNewEnd
)
442 mSlice(aOther
.mSlice
),
444 mFrame(aOther
.mFrame
),
449 /* Has to be an object, not a reference, since the slice could
450 well be a temporary constructed from an nsFrameList */
453 nsIFrame
* mFrame
; // our current frame.
454 const nsIFrame
* const mEnd
; // The first frame we should NOT enumerate.
459 * A class that can be used to enumerate links between frames. When created
460 * from an nsFrameList, it points to the "link" immediately before the first
461 * frame. It can then be advanced until it points to the "link" immediately
462 * after the last frame. At any position, PrevFrame() and NextFrame() are
463 * the frames before and after the given link. This means PrevFrame() is
464 * null when the enumerator is at the beginning of the list and NextFrame()
465 * is null when it's AtEnd().
467 class FrameLinkEnumerator
: private Enumerator
{
469 friend class nsFrameList
;
471 explicit FrameLinkEnumerator(const nsFrameList
& aList
)
472 : Enumerator(aList
), mPrev(nullptr) {}
474 FrameLinkEnumerator(const FrameLinkEnumerator
& aOther
) = default;
476 /* This constructor needs to know about nsIFrame, and nsIFrame will need to
477 know about nsFrameList methods, so in order to inline this put
478 the implementation in nsIFrame.h */
479 inline FrameLinkEnumerator(const nsFrameList
& aList
, nsIFrame
* aPrevFrame
);
481 void operator=(const FrameLinkEnumerator
& aOther
) {
482 MOZ_ASSERT(&List() == &aOther
.List(), "Different lists?");
483 mFrame
= aOther
.mFrame
;
484 mPrev
= aOther
.mPrev
;
490 * Find the first frame from the current position that satisfies
491 * aPredicate, and stop at it. If no such frame exists, then this method
492 * advances to the end of the list.
494 * aPredicate should be of this function signature: bool(nsIFrame*).
496 * Note: Find() needs to see the definition of Next(), so put this
497 * definition in nsIFrame.h.
499 template <typename Predicate
>
500 inline void Find(Predicate
&& aPredicate
);
502 bool AtEnd() const { return Enumerator::AtEnd(); }
504 nsIFrame
* PrevFrame() const { return mPrev
; }
505 nsIFrame
* NextFrame() const { return mFrame
; }
513 // It is disputable whether these type definitions are correct, since
514 // operator* doesn't return a reference at all. Also, the iterator_category
515 // can be at most std::input_iterator_tag (rather than
516 // std::bidrectional_iterator_tag, as it might seem), because it is a
517 // stashing iterator. See also, e.g.,
518 // https://stackoverflow.com/questions/50909701/what-should-be-iterator-category-for-a-stashing-iterator
519 using value_type
= nsIFrame
* const;
520 using pointer
= value_type
*;
521 using reference
= value_type
&;
522 using difference_type
= ptrdiff_t;
523 using iterator_category
= std::input_iterator_tag
;
525 Iterator(const nsFrameList
& aList
, nsIFrame
* aCurrent
)
526 : mList(aList
), mCurrent(aCurrent
) {}
528 Iterator(const Iterator
& aOther
) = default;
530 nsIFrame
* operator*() const { return mCurrent
; }
532 // The operators need to know about nsIFrame, hence the
533 // implementations are in nsIFrame.h
534 Iterator
& operator++();
535 Iterator
& operator--();
537 Iterator
operator++(int) {
542 Iterator
operator--(int) {
548 friend bool operator==(const Iterator
& aIter1
, const Iterator
& aIter2
);
549 friend bool operator!=(const Iterator
& aIter1
, const Iterator
& aIter2
);
552 const nsFrameList
& mList
;
556 typedef Iterator iterator
;
557 typedef Iterator const_iterator
;
558 typedef mozilla::ReverseIterator
<Iterator
> reverse_iterator
;
559 typedef mozilla::ReverseIterator
<Iterator
> const_reverse_iterator
;
561 iterator
begin() const { return iterator(*this, mFirstChild
); }
562 const_iterator
cbegin() const { return begin(); }
563 iterator
end() const { return iterator(*this, nullptr); }
564 const_iterator
cend() const { return end(); }
565 reverse_iterator
rbegin() const { return reverse_iterator(end()); }
566 const_reverse_iterator
crbegin() const { return rbegin(); }
567 reverse_iterator
rend() const { return reverse_iterator(begin()); }
568 const_reverse_iterator
crend() const { return rend(); }
571 void operator delete(void*) = delete;
573 #ifdef DEBUG_FRAME_LIST
574 void VerifyList() const;
576 void VerifyList() const {}
581 * Disconnect aFrame from its siblings. This must only be called if aFrame
582 * is NOT the first or last sibling, because otherwise its nsFrameList will
583 * have a stale mFirst/LastChild pointer. This precondition is asserted.
584 * This function is O(1).
586 static void UnhookFrameFromSiblings(nsIFrame
* aFrame
);
588 nsIFrame
* mFirstChild
;
589 nsIFrame
* mLastChild
;
592 inline bool operator==(const nsFrameList::Iterator
& aIter1
,
593 const nsFrameList::Iterator
& aIter2
) {
594 MOZ_ASSERT(&aIter1
.mList
== &aIter2
.mList
,
595 "must not compare iterator from different list");
596 return aIter1
.mCurrent
== aIter2
.mCurrent
;
599 inline bool operator!=(const nsFrameList::Iterator
& aIter1
,
600 const nsFrameList::Iterator
& aIter2
) {
601 MOZ_ASSERT(&aIter1
.mList
== &aIter2
.mList
,
602 "Must not compare iterator from different list");
603 return aIter1
.mCurrent
!= aIter2
.mCurrent
;
609 * Simple "auto_ptr" for nsFrameLists allocated from the shell arena.
610 * The frame list given to the constructor will be deallocated (if non-null)
611 * in the destructor. The frame list must then be empty.
613 class MOZ_RAII AutoFrameListPtr final
{
615 AutoFrameListPtr(nsPresContext
* aPresContext
, nsFrameList
* aFrameList
)
616 : mPresContext(aPresContext
), mFrameList(aFrameList
) {}
618 operator nsFrameList
*() const { return mFrameList
; }
619 nsFrameList
* operator->() const { return mFrameList
; }
622 nsPresContext
* mPresContext
;
623 nsFrameList
* mFrameList
;
626 namespace layout::detail
{
627 union AlignedFrameListBytes
{
629 char bytes
[sizeof(nsFrameList
)];
631 extern const AlignedFrameListBytes gEmptyFrameListBytes
;
632 } // namespace layout::detail
634 } // namespace mozilla
636 /* static */ inline const nsFrameList
& nsFrameList::EmptyList() {
637 return *reinterpret_cast<const nsFrameList
*>(
638 &mozilla::layout::detail::gEmptyFrameListBytes
);
641 #endif /* nsFrameList_h___ */