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 #ifndef nsFrameList_h___
8 #define nsFrameList_h___
9
10 #include <stdio.h> /* for FILE* */
11 #include "nsDebug.h"
12 #include "nsTArray.h"
13 #include "mozilla/FunctionTypeTraits.h"
14 #include "mozilla/RefPtr.h"
15 #include "mozilla/ReverseIterator.h"
16
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
21 #endif
22
23 class nsContainerFrame;
24 class nsIContent;
25 class nsIFrame;
26 class nsPresContext;
27
28 namespace mozilla {
29 class PresShell;
30 namespace layout {
31 class FrameChildList;
32 enum FrameChildListID {
33 // The individual concrete child lists.
34 kPrincipalList,
35 kPopupList,
36 kCaptionList,
37 kColGroupList,
38 kSelectPopupList,
39 kAbsoluteList,
40 kFixedList,
41 kOverflowList,
42 kOverflowContainersList,
43 kExcessOverflowContainersList,
44 kOverflowOutOfFlowList,
45 kFloatList,
46 kBulletList,
47 kPushedFloatsList,
48 kBackdropList,
49 // A special alias for kPrincipalList that suppress the reflow request that
50 // is normally done when manipulating child lists.
51 kNoReflowPrincipalList,
52 };
53
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;
59
60 AutoTArray<RefPtr<nsIContent>, 100> mAnonymousContent;
AddAnonymousContentPostFrameDestroyData61 void AddAnonymousContent(already_AddRefed<nsIContent>&& aContent) {
62 mAnonymousContent.AppendElement(aContent);
63 }
64 };
65 } // namespace layout
66 } // namespace mozilla
67
68 // Uncomment this to enable expensive frame-list integrity checking
69 // #define DEBUG_FRAME_LIST
70
71 /**
72 * A class for managing a list of frames.
73 */
74 class nsFrameList {
75 public:
nsFrameList()76 nsFrameList() : mFirstChild(nullptr), mLastChild(nullptr) {}
77
nsFrameList(nsIFrame * aFirstFrame,nsIFrame * aLastFrame)78 nsFrameList(nsIFrame* aFirstFrame, nsIFrame* aLastFrame)
79 : mFirstChild(aFirstFrame), mLastChild(aLastFrame) {
80 VerifyList();
81 }
82
83 // XXX: Ideally, copy constructor should be removed because a frame should be
84 // owned by one list.
85 nsFrameList(const nsFrameList& aOther) = default;
86
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;
90
91 /**
92 * Move the frames in aOther to this list. aOther becomes empty after this
93 * operation.
94 */
nsFrameList(nsFrameList && aOther)95 nsFrameList(nsFrameList&& aOther)
96 : mFirstChild(aOther.mFirstChild), mLastChild(aOther.mLastChild) {
97 aOther.Clear();
98 VerifyList();
99 }
100 nsFrameList& operator=(nsFrameList&& aOther) {
101 SetFrames(aOther);
102 return *this;
103 }
104
105 /**
106 * Infallibly allocate a nsFrameList from the shell arena.
107 */
108 void* operator new(size_t sz, mozilla::PresShell* aPresShell);
109
110 /**
111 * Deallocate this list that was allocated from the shell arena.
112 * The list is required to be empty.
113 */
114 void Delete(mozilla::PresShell* aPresShell);
115
116 /**
117 * For each frame in this list: remove it from the list then call
118 * Destroy() on it.
119 */
120 void DestroyFrames();
121
122 /**
123 * For each frame in this list: remove it from the list then call
124 * DestroyFrom(aDestructRoot, aPostDestroyData) on it.
125 */
126 void DestroyFramesFrom(
127 nsIFrame* aDestructRoot,
128 mozilla::layout::PostFrameDestroyData& aPostDestroyData);
129
Clear()130 void Clear() { mFirstChild = mLastChild = nullptr; }
131
132 void SetFrames(nsIFrame* aFrameList);
133
SetFrames(nsFrameList & aFrameList)134 void SetFrames(nsFrameList& aFrameList) {
135 MOZ_ASSERT(!mFirstChild, "Losing frames");
136
137 mFirstChild = aFrameList.FirstChild();
138 mLastChild = aFrameList.LastChild();
139 aFrameList.Clear();
140 }
141
142 class Slice;
143
144 /**
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.
148 */
AppendFrames(nsContainerFrame * aParent,nsFrameList & aFrameList)149 Slice AppendFrames(nsContainerFrame* aParent, nsFrameList& aFrameList) {
150 return InsertFrames(aParent, LastChild(), aFrameList);
151 }
152
153 /**
154 * Append aFrame to this list. If aParent is not null,
155 * reparents the newly added frame.
156 */
AppendFrame(nsContainerFrame * aParent,nsIFrame * aFrame)157 void AppendFrame(nsContainerFrame* aParent, nsIFrame* aFrame) {
158 nsFrameList temp(aFrame, aFrame);
159 AppendFrames(aParent, temp);
160 }
161
162 /**
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
165 * this list.
166 */
167 void RemoveFrame(nsIFrame* aFrame);
168
169 /**
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
174 */
175 nsFrameList RemoveFramesAfter(nsIFrame* aAfterFrame);
176
177 /**
178 * Take the first frame (if any) out of the frame list.
179 * @return the first child, or nullptr if the list is empty
180 */
181 nsIFrame* RemoveFirstChild();
182
183 /**
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.
188 * Example use:
189 * bool removed = frameList1.StartRemoveFrame(aFrame) ||
190 * frameList2.ContinueRemoveFrame(aFrame) ||
191 * frameList3.ContinueRemoveFrame(aFrame);
192 * MOZ_ASSERT(removed);
193 *
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)
201 */
202 inline bool StartRemoveFrame(nsIFrame* aFrame);
203
204 /**
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)
210 */
211 inline bool ContinueRemoveFrame(nsIFrame* aFrame);
212
213 /**
214 * Take aFrame out of the frame list and then destroy it.
215 * The frame must be non-null and present on this list.
216 */
217 void DestroyFrame(nsIFrame* aFrame);
218
219 /**
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.
224 */
InsertFrame(nsContainerFrame * aParent,nsIFrame * aPrevSibling,nsIFrame * aFrame)225 void InsertFrame(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
226 nsIFrame* aFrame) {
227 nsFrameList temp(aFrame, aFrame);
228 InsertFrames(aParent, aPrevSibling, temp);
229 }
230
231 /**
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.
236 */
237 Slice InsertFrames(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
238 nsFrameList& aFrameList);
239
240 class FrameLinkEnumerator;
241
242 /**
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.
248 *
249 * aPredicate should be of this function signature: bool(nsIFrame*).
250 */
251 template <typename Predicate>
Split(Predicate && aPredicate)252 nsFrameList Split(Predicate&& aPredicate) {
253 static_assert(
254 std::is_same<
255 typename mozilla::FunctionTypeTraits<Predicate>::ReturnType,
256 bool>::value &&
257 mozilla::FunctionTypeTraits<Predicate>::arity == 1 &&
258 std::is_same<typename mozilla::FunctionTypeTraits<
259 Predicate>::template ParameterType<0>,
260 nsIFrame*>::value,
261 "aPredicate should be of this function signature: bool(nsIFrame*)");
262
263 FrameLinkEnumerator link(*this);
264 link.Find(aPredicate);
265 return ExtractHead(link);
266 }
267
268 /**
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.
272 */
273 nsFrameList ExtractHead(FrameLinkEnumerator& aLink);
274
275 /**
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.
279 */
280 nsFrameList ExtractTail(FrameLinkEnumerator& aLink);
281
FirstChild()282 nsIFrame* FirstChild() const { return mFirstChild; }
283
LastChild()284 nsIFrame* LastChild() const { return mLastChild; }
285
286 nsIFrame* FrameAt(int32_t aIndex) const;
287 int32_t IndexOf(nsIFrame* aFrame) const;
288
IsEmpty()289 bool IsEmpty() const { return nullptr == mFirstChild; }
290
NotEmpty()291 bool NotEmpty() const { return nullptr != mFirstChild; }
292
293 /**
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
297 */
298 bool ContainsFrame(const nsIFrame* aFrame) const;
299
300 /**
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
303 * code.
304 * XXXmats: ideally, we should make this function #ifdef DEBUG
305 */
306 int32_t GetLength() const;
307
308 /**
309 * If this frame list has only one frame, return that frame.
310 * Otherwise, return null.
311 */
OnlyChild()312 nsIFrame* OnlyChild() const {
313 if (FirstChild() == LastChild()) {
314 return FirstChild();
315 }
316 return nullptr;
317 }
318
319 /**
320 * Call SetParent(aParent) for each frame in this list.
321 * @param aParent the new parent frame, must be non-null
322 */
323 void ApplySetParent(nsContainerFrame* aParent) const;
324
325 /**
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)
329 */
330 inline void AppendIfNonempty(
331 nsTArray<mozilla::layout::FrameChildList>* aLists,
332 mozilla::layout::FrameChildListID aListID) const;
333
334 /**
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.
337 */
338 nsIFrame* GetPrevVisualFor(nsIFrame* aFrame) const;
339
340 /**
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.
343 */
344 nsIFrame* GetNextVisualFor(nsIFrame* aFrame) const;
345
346 #ifdef DEBUG_FRAME_DUMP
347 void List(FILE* out) const;
348 #endif
349
350 static inline const nsFrameList& EmptyList();
351
352 class Enumerator;
353
354 /**
355 * A class representing a slice of a frame list.
356 */
357 class Slice {
358 friend class Enumerator;
359
360 public:
361 // Implicit on purpose, so that we can easily create enumerators from
362 // nsFrameList via this impicit constructor.
Slice(const nsFrameList & aList)363 MOZ_IMPLICIT Slice(const nsFrameList& aList)
364 :
365 #ifdef DEBUG
366 mList(aList),
367 #endif
368 mStart(aList.FirstChild()),
369 mEnd(nullptr) {
370 }
371
Slice(const nsFrameList & aList,nsIFrame * aStart,nsIFrame * aEnd)372 Slice(const nsFrameList& aList, nsIFrame* aStart, nsIFrame* aEnd)
373 :
374 #ifdef DEBUG
375 mList(aList),
376 #endif
377 mStart(aStart),
378 mEnd(aEnd) {
379 }
380
381 Slice(const Slice& aOther) = default;
382
383 private:
384 #ifdef DEBUG
385 const nsFrameList& mList;
386 #endif
387 nsIFrame* const mStart; // our starting frame
388 const nsIFrame* const mEnd; // The first frame that is NOT in the slice.
389 // May be null.
390 };
391
392 class Enumerator {
393 public:
Enumerator(const Slice & aSlice)394 explicit Enumerator(const Slice& aSlice)
395 :
396 #ifdef DEBUG
397 mSlice(aSlice),
398 #endif
399 mFrame(aSlice.mStart),
400 mEnd(aSlice.mEnd) {
401 }
402
403 Enumerator(const Enumerator& aOther) = default;
404
AtEnd()405 bool AtEnd() const {
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
408 // frame list.
409 return !mFrame || mFrame == mEnd;
410 }
411
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 */
415 inline void Next();
416
417 /**
418 * Get the current frame we're pointing to. Do not call this on an
419 * iterator that is at end!
420 */
get()421 nsIFrame* get() const {
422 MOZ_ASSERT(!AtEnd(), "Enumerator is at end");
423 return mFrame;
424 }
425
426 /**
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.
429 */
GetUnlimitedEnumerator()430 Enumerator GetUnlimitedEnumerator() const {
431 return Enumerator(*this, nullptr);
432 }
433
434 #ifdef DEBUG
List()435 const nsFrameList& List() const { return mSlice.mList; }
436 #endif
437
438 protected:
Enumerator(const Enumerator & aOther,const nsIFrame * const aNewEnd)439 Enumerator(const Enumerator& aOther, const nsIFrame* const aNewEnd)
440 :
441 #ifdef DEBUG
442 mSlice(aOther.mSlice),
443 #endif
444 mFrame(aOther.mFrame),
445 mEnd(aNewEnd) {
446 }
447
448 #ifdef DEBUG
449 /* Has to be an object, not a reference, since the slice could
450 well be a temporary constructed from an nsFrameList */
451 const Slice mSlice;
452 #endif
453 nsIFrame* mFrame; // our current frame.
454 const nsIFrame* const mEnd; // The first frame we should NOT enumerate.
455 // May be null.
456 };
457
458 /**
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().
466 */
467 class FrameLinkEnumerator : private Enumerator {
468 public:
469 friend class nsFrameList;
470
FrameLinkEnumerator(const nsFrameList & aList)471 explicit FrameLinkEnumerator(const nsFrameList& aList)
472 : Enumerator(aList), mPrev(nullptr) {}
473
474 FrameLinkEnumerator(const FrameLinkEnumerator& aOther) = default;
475
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);
480
481 void operator=(const FrameLinkEnumerator& aOther) {
482 MOZ_ASSERT(&List() == &aOther.List(), "Different lists?");
483 mFrame = aOther.mFrame;
484 mPrev = aOther.mPrev;
485 }
486
487 inline void Next();
488
489 /**
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.
493 *
494 * aPredicate should be of this function signature: bool(nsIFrame*).
495 *
496 * Note: Find() needs to see the definition of Next(), so put this
497 * definition in nsIFrame.h.
498 */
499 template <typename Predicate>
500 inline void Find(Predicate&& aPredicate);
501
AtEnd()502 bool AtEnd() const { return Enumerator::AtEnd(); }
503
PrevFrame()504 nsIFrame* PrevFrame() const { return mPrev; }
NextFrame()505 nsIFrame* NextFrame() const { return mFrame; }
506
507 protected:
508 nsIFrame* mPrev;
509 };
510
511 class Iterator {
512 public:
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;
524
Iterator(const nsFrameList & aList,nsIFrame * aCurrent)525 Iterator(const nsFrameList& aList, nsIFrame* aCurrent)
526 : mList(aList), mCurrent(aCurrent) {}
527
528 Iterator(const Iterator& aOther) = default;
529
530 nsIFrame* operator*() const { return mCurrent; }
531
532 // The operators need to know about nsIFrame, hence the
533 // implementations are in nsIFrame.h
534 Iterator& operator++();
535 Iterator& operator--();
536
537 Iterator operator++(int) {
538 auto ret = *this;
539 ++*this;
540 return ret;
541 }
542 Iterator operator--(int) {
543 auto ret = *this;
544 --*this;
545 return ret;
546 }
547
548 friend bool operator==(const Iterator& aIter1, const Iterator& aIter2);
549 friend bool operator!=(const Iterator& aIter1, const Iterator& aIter2);
550
551 private:
552 const nsFrameList& mList;
553 nsIFrame* mCurrent;
554 };
555
556 typedef Iterator iterator;
557 typedef Iterator const_iterator;
558 typedef mozilla::ReverseIterator<Iterator> reverse_iterator;
559 typedef mozilla::ReverseIterator<Iterator> const_reverse_iterator;
560
begin()561 iterator begin() const { return iterator(*this, mFirstChild); }
cbegin()562 const_iterator cbegin() const { return begin(); }
end()563 iterator end() const { return iterator(*this, nullptr); }
cend()564 const_iterator cend() const { return end(); }
rbegin()565 reverse_iterator rbegin() const { return reverse_iterator(end()); }
crbegin()566 const_reverse_iterator crbegin() const { return rbegin(); }
rend()567 reverse_iterator rend() const { return reverse_iterator(begin()); }
crend()568 const_reverse_iterator crend() const { return rend(); }
569
570 private:
571 void operator delete(void*) = delete;
572
573 #ifdef DEBUG_FRAME_LIST
574 void VerifyList() const;
575 #else
VerifyList()576 void VerifyList() const {}
577 #endif
578
579 protected:
580 /**
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).
585 */
586 static void UnhookFrameFromSiblings(nsIFrame* aFrame);
587
588 nsIFrame* mFirstChild;
589 nsIFrame* mLastChild;
590 };
591
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;
597 }
598
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;
604 }
605
606 namespace mozilla {
607
608 /**
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.
612 */
613 class MOZ_RAII AutoFrameListPtr final {
614 public:
AutoFrameListPtr(nsPresContext * aPresContext,nsFrameList * aFrameList)615 AutoFrameListPtr(nsPresContext* aPresContext, nsFrameList* aFrameList)
616 : mPresContext(aPresContext), mFrameList(aFrameList) {}
617 ~AutoFrameListPtr();
618 operator nsFrameList*() const { return mFrameList; }
619 nsFrameList* operator->() const { return mFrameList; }
620
621 private:
622 nsPresContext* mPresContext;
623 nsFrameList* mFrameList;
624 };
625
626 namespace layout::detail {
627 union AlignedFrameListBytes {
628 void* ptr;
629 char bytes[sizeof(nsFrameList)];
630 };
631 extern const AlignedFrameListBytes gEmptyFrameListBytes;
632 } // namespace layout::detail
633
634 } // namespace mozilla
635
EmptyList()636 /* static */ inline const nsFrameList& nsFrameList::EmptyList() {
637 return *reinterpret_cast<const nsFrameList*>(
638 &mozilla::layout::detail::gEmptyFrameListBytes);
639 }
640
641 #endif /* nsFrameList_h___ */
642