1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 /* This Source Code Form is subject to the terms of the Mozilla Public
3 * License, v. 2.0. If a copy of the MPL was not distributed with this
4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
5
6 #ifndef nsFrameList_h___
7 #define nsFrameList_h___
8
9 #include <stdio.h> /* for FILE* */
10 #include "nsDebug.h"
11 #include "nsTArrayForwardDeclare.h"
12 #include "mozilla/ReverseIterator.h"
13
14 #if defined(DEBUG) || defined(MOZ_DUMP_PAINTING)
15 // DEBUG_FRAME_DUMP enables nsIFrame::List and related methods.
16 // You can also define this in a non-DEBUG build if you need frame dumps.
17 #define DEBUG_FRAME_DUMP 1
18 #endif
19
20 class nsContainerFrame;
21 class nsIFrame;
22 class nsIPresShell;
23 class nsPresContext;
24
25 namespace mozilla {
26 namespace layout {
27 class FrameChildList;
28 enum FrameChildListID {
29 // The individual concrete child lists.
30 kPrincipalList = 0x1,
31 kPopupList = 0x2,
32 kCaptionList = 0x4,
33 kColGroupList = 0x8,
34 kSelectPopupList = 0x10,
35 kAbsoluteList = 0x20,
36 kFixedList = 0x40,
37 kOverflowList = 0x80,
38 kOverflowContainersList = 0x100,
39 kExcessOverflowContainersList = 0x200,
40 kOverflowOutOfFlowList = 0x400,
41 kFloatList = 0x800,
42 kBulletList = 0x1000,
43 kPushedFloatsList = 0x2000,
44 kBackdropList = 0x4000,
45 // A special alias for kPrincipalList that suppress the reflow request that
46 // is normally done when manipulating child lists.
47 kNoReflowPrincipalList = 0x8000
48 };
49 } // namespace layout
50 } // namespace mozilla
51
52 // Uncomment this to enable expensive frame-list integrity checking
53 // #define DEBUG_FRAME_LIST
54
55 /**
56 * A class for managing a list of frames.
57 */
58 class nsFrameList {
59 public:
nsFrameList()60 nsFrameList() :
61 mFirstChild(nullptr), mLastChild(nullptr)
62 {
63 }
64
nsFrameList(nsIFrame * aFirstFrame,nsIFrame * aLastFrame)65 nsFrameList(nsIFrame* aFirstFrame, nsIFrame* aLastFrame) :
66 mFirstChild(aFirstFrame), mLastChild(aLastFrame)
67 {
68 VerifyList();
69 }
70
nsFrameList(const nsFrameList & aOther)71 nsFrameList(const nsFrameList& aOther) :
72 mFirstChild(aOther.mFirstChild), mLastChild(aOther.mLastChild)
73 {
74 }
75
76 /**
77 * Infallibly allocate a nsFrameList from the shell arena.
78 */
79 void* operator new(size_t sz, nsIPresShell* aPresShell);
80
81 /**
82 * Deallocate this list that was allocated from the shell arena.
83 * The list is required to be empty.
84 */
85 void Delete(nsIPresShell* aPresShell);
86
87 /**
88 * For each frame in this list: remove it from the list then call
89 * Destroy() on it.
90 */
91 void DestroyFrames();
92
93 /**
94 * For each frame in this list: remove it from the list then call
95 * DestroyFrom(aDestructRoot) on it.
96 */
97 void DestroyFramesFrom(nsIFrame* aDestructRoot);
98
Clear()99 void Clear() { mFirstChild = mLastChild = nullptr; }
100
101 void SetFrames(nsIFrame* aFrameList);
102
SetFrames(nsFrameList & aFrameList)103 void SetFrames(nsFrameList& aFrameList) {
104 NS_PRECONDITION(!mFirstChild, "Losing frames");
105
106 mFirstChild = aFrameList.FirstChild();
107 mLastChild = aFrameList.LastChild();
108 aFrameList.Clear();
109 }
110
111 class Slice;
112
113 /**
114 * Append aFrameList to this list. If aParent is not null,
115 * reparents the newly added frames. Clears out aFrameList and
116 * returns a list slice represening the newly-appended frames.
117 */
AppendFrames(nsContainerFrame * aParent,nsFrameList & aFrameList)118 Slice AppendFrames(nsContainerFrame* aParent, nsFrameList& aFrameList) {
119 return InsertFrames(aParent, LastChild(), aFrameList);
120 }
121
122
123 /**
124 * Append aFrame to this list. If aParent is not null,
125 * reparents the newly added frame.
126 */
AppendFrame(nsContainerFrame * aParent,nsIFrame * aFrame)127 void AppendFrame(nsContainerFrame* aParent, nsIFrame* aFrame) {
128 nsFrameList temp(aFrame, aFrame);
129 AppendFrames(aParent, temp);
130 }
131
132 /**
133 * Take aFrame out of the frame list. This also disconnects aFrame
134 * from the sibling list. The frame must be non-null and present on
135 * this list.
136 */
137 void RemoveFrame(nsIFrame* aFrame);
138
139 /**
140 * Take the frames after aAfterFrame out of the frame list. If
141 * aAfterFrame is null, removes the entire list.
142 * @param aAfterFrame a frame in this list, or null
143 * @return the removed frames, if any
144 */
145 nsFrameList RemoveFramesAfter(nsIFrame* aAfterFrame);
146
147 /**
148 * Take the first frame (if any) out of the frame list.
149 * @return the first child, or nullptr if the list is empty
150 */
151 nsIFrame* RemoveFirstChild();
152
153 /**
154 * The following two functions are intended to be used in concert for
155 * removing a frame from its frame list when the set of possible frame
156 * lists is known in advance, but the exact frame list is unknown.
157 * aFrame must be non-null.
158 * Example use:
159 * bool removed = frameList1.StartRemoveFrame(aFrame) ||
160 * frameList2.ContinueRemoveFrame(aFrame) ||
161 * frameList3.ContinueRemoveFrame(aFrame);
162 * MOZ_ASSERT(removed);
163 *
164 * @note One of the frame lists MUST contain aFrame, if it's on some other
165 * frame list then the example above will likely lead to crashes.
166 * This function is O(1).
167 * @return true iff aFrame was removed from /some/ list, not necessarily
168 * this one. If it was removed from a different list then it is
169 * guaranteed that that list is still non-empty.
170 * (this method is implemented in nsIFrame.h to be able to inline)
171 */
172 inline bool StartRemoveFrame(nsIFrame* aFrame);
173
174 /**
175 * Precondition: StartRemoveFrame MUST be called before this.
176 * This function is O(1).
177 * @see StartRemoveFrame
178 * @return true iff aFrame was removed from this list
179 * (this method is implemented in nsIFrame.h to be able to inline)
180 */
181 inline bool ContinueRemoveFrame(nsIFrame* aFrame);
182
183 /**
184 * Take aFrame out of the frame list and then destroy it.
185 * The frame must be non-null and present on this list.
186 */
187 void DestroyFrame(nsIFrame* aFrame);
188
189 /**
190 * Insert aFrame right after aPrevSibling, or prepend it to this
191 * list if aPrevSibling is null. If aParent is not null, also
192 * reparents newly-added frame. Note that this method always
193 * sets the frame's nextSibling pointer.
194 */
InsertFrame(nsContainerFrame * aParent,nsIFrame * aPrevSibling,nsIFrame * aFrame)195 void InsertFrame(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
196 nsIFrame* aFrame) {
197 nsFrameList temp(aFrame, aFrame);
198 InsertFrames(aParent, aPrevSibling, temp);
199 }
200
201
202 /**
203 * Inserts aFrameList into this list after aPrevSibling (at the beginning if
204 * aPrevSibling is null). If aParent is not null, reparents the newly added
205 * frames. Clears out aFrameList and returns a list slice representing the
206 * newly-inserted frames.
207 */
208 Slice InsertFrames(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
209 nsFrameList& aFrameList);
210
211 class FrameLinkEnumerator;
212
213 /**
214 * Split this frame list such that all the frames before the link pointed to
215 * by aLink end up in the returned list, while the remaining frames stay in
216 * this list. After this call, aLink points to the beginning of this list.
217 */
218 nsFrameList ExtractHead(FrameLinkEnumerator& aLink);
219
220 /**
221 * Split this frame list such that all the frames coming after the link
222 * pointed to by aLink end up in the returned list, while the frames before
223 * that link stay in this list. After this call, aLink is at end.
224 */
225 nsFrameList ExtractTail(FrameLinkEnumerator& aLink);
226
FirstChild()227 nsIFrame* FirstChild() const {
228 return mFirstChild;
229 }
230
LastChild()231 nsIFrame* LastChild() const {
232 return mLastChild;
233 }
234
235 nsIFrame* FrameAt(int32_t aIndex) const;
236 int32_t IndexOf(nsIFrame* aFrame) const;
237
IsEmpty()238 bool IsEmpty() const {
239 return nullptr == mFirstChild;
240 }
241
NotEmpty()242 bool NotEmpty() const {
243 return nullptr != mFirstChild;
244 }
245
246 bool ContainsFrame(const nsIFrame* aFrame) const;
247
248 /**
249 * Get the number of frames in this list. Note that currently the
250 * implementation has O(n) time complexity. Do not call it repeatedly in hot
251 * code.
252 */
253 int32_t GetLength() const;
254
255 /**
256 * If this frame list has only one frame, return that frame.
257 * Otherwise, return null.
258 */
OnlyChild()259 nsIFrame* OnlyChild() const {
260 if (FirstChild() == LastChild()) {
261 return FirstChild();
262 }
263 return nullptr;
264 }
265
266 /**
267 * Call SetParent(aParent) for each frame in this list.
268 * @param aParent the new parent frame, must be non-null
269 */
270 void ApplySetParent(nsContainerFrame* aParent) const;
271
272 /**
273 * If this frame list is non-empty then append it to aLists as the
274 * aListID child list.
275 * (this method is implemented in FrameChildList.h for dependency reasons)
276 */
277 inline void AppendIfNonempty(nsTArray<mozilla::layout::FrameChildList>* aLists,
278 mozilla::layout::FrameChildListID aListID) const;
279
280 /**
281 * Return the frame before this frame in visual order (after Bidi reordering).
282 * If aFrame is null, return the last frame in visual order.
283 */
284 nsIFrame* GetPrevVisualFor(nsIFrame* aFrame) const;
285
286 /**
287 * Return the frame after this frame in visual order (after Bidi reordering).
288 * If aFrame is null, return the first frame in visual order.
289 */
290 nsIFrame* GetNextVisualFor(nsIFrame* aFrame) const;
291
292 #ifdef DEBUG_FRAME_DUMP
293 void List(FILE* out) const;
294 #endif
295
296 static inline const nsFrameList& EmptyList();
297
298 class Enumerator;
299
300 /**
301 * A class representing a slice of a frame list.
302 */
303 class Slice {
304 friend class Enumerator;
305
306 public:
307 // Implicit on purpose, so that we can easily create enumerators from
308 // nsFrameList via this impicit constructor.
Slice(const nsFrameList & aList)309 MOZ_IMPLICIT Slice(const nsFrameList& aList) :
310 #ifdef DEBUG
311 mList(aList),
312 #endif
313 mStart(aList.FirstChild()),
314 mEnd(nullptr)
315 {}
316
Slice(const nsFrameList & aList,nsIFrame * aStart,nsIFrame * aEnd)317 Slice(const nsFrameList& aList, nsIFrame* aStart, nsIFrame* aEnd) :
318 #ifdef DEBUG
319 mList(aList),
320 #endif
321 mStart(aStart),
322 mEnd(aEnd)
323 {}
324
Slice(const Slice & aOther)325 Slice(const Slice& aOther) :
326 #ifdef DEBUG
327 mList(aOther.mList),
328 #endif
329 mStart(aOther.mStart),
330 mEnd(aOther.mEnd)
331 {}
332
333 private:
334 #ifdef DEBUG
335 const nsFrameList& mList;
336 #endif
337 nsIFrame* const mStart; // our starting frame
338 const nsIFrame* const mEnd; // The first frame that is NOT in the slice.
339 // May be null.
340 };
341
342 class Enumerator {
343 public:
Enumerator(const Slice & aSlice)344 explicit Enumerator(const Slice& aSlice) :
345 #ifdef DEBUG
346 mSlice(aSlice),
347 #endif
348 mFrame(aSlice.mStart),
349 mEnd(aSlice.mEnd)
350 {}
351
Enumerator(const Enumerator & aOther)352 Enumerator(const Enumerator& aOther) :
353 #ifdef DEBUG
354 mSlice(aOther.mSlice),
355 #endif
356 mFrame(aOther.mFrame),
357 mEnd(aOther.mEnd)
358 {}
359
AtEnd()360 bool AtEnd() const {
361 // Can't just check mEnd, because some table code goes and destroys the
362 // tail of the frame list (including mEnd!) while iterating over the
363 // frame list.
364 return !mFrame || mFrame == mEnd;
365 }
366
367 /* Next() needs to know about nsIFrame, and nsIFrame will need to
368 know about nsFrameList methods, so in order to inline this put
369 the implementation in nsIFrame.h */
370 inline void Next();
371
372 /**
373 * Get the current frame we're pointing to. Do not call this on an
374 * iterator that is at end!
375 */
get()376 nsIFrame* get() const {
377 NS_PRECONDITION(!AtEnd(), "Enumerator is at end");
378 return mFrame;
379 }
380
381 /**
382 * Get an enumerator that is just like this one, but not limited in terms of
383 * the part of the list it will traverse.
384 */
GetUnlimitedEnumerator()385 Enumerator GetUnlimitedEnumerator() const {
386 return Enumerator(*this, nullptr);
387 }
388
389 #ifdef DEBUG
List()390 const nsFrameList& List() const { return mSlice.mList; }
391 #endif
392
393 protected:
Enumerator(const Enumerator & aOther,const nsIFrame * const aNewEnd)394 Enumerator(const Enumerator& aOther, const nsIFrame* const aNewEnd):
395 #ifdef DEBUG
396 mSlice(aOther.mSlice),
397 #endif
398 mFrame(aOther.mFrame),
399 mEnd(aNewEnd)
400 {}
401
402 #ifdef DEBUG
403 /* Has to be an object, not a reference, since the slice could
404 well be a temporary constructed from an nsFrameList */
405 const Slice mSlice;
406 #endif
407 nsIFrame* mFrame; // our current frame.
408 const nsIFrame* const mEnd; // The first frame we should NOT enumerate.
409 // May be null.
410 };
411
412 /**
413 * A class that can be used to enumerate links between frames. When created
414 * from an nsFrameList, it points to the "link" immediately before the first
415 * frame. It can then be advanced until it points to the "link" immediately
416 * after the last frame. At any position, PrevFrame() and NextFrame() are
417 * the frames before and after the given link. This means PrevFrame() is
418 * null when the enumerator is at the beginning of the list and NextFrame()
419 * is null when it's AtEnd().
420 */
421 class FrameLinkEnumerator : private Enumerator {
422 public:
423 friend class nsFrameList;
424
FrameLinkEnumerator(const nsFrameList & aList)425 explicit FrameLinkEnumerator(const nsFrameList& aList) :
426 Enumerator(aList),
427 mPrev(nullptr)
428 {}
429
FrameLinkEnumerator(const FrameLinkEnumerator & aOther)430 FrameLinkEnumerator(const FrameLinkEnumerator& aOther) :
431 Enumerator(aOther),
432 mPrev(aOther.mPrev)
433 {}
434
435 /* This constructor needs to know about nsIFrame, and nsIFrame will need to
436 know about nsFrameList methods, so in order to inline this put
437 the implementation in nsIFrame.h */
438 inline FrameLinkEnumerator(const nsFrameList& aList, nsIFrame* aPrevFrame);
439
440 void operator=(const FrameLinkEnumerator& aOther) {
441 NS_PRECONDITION(&List() == &aOther.List(), "Different lists?");
442 mFrame = aOther.mFrame;
443 mPrev = aOther.mPrev;
444 }
445
446 inline void Next();
447
AtEnd()448 bool AtEnd() const { return Enumerator::AtEnd(); }
449
PrevFrame()450 nsIFrame* PrevFrame() const { return mPrev; }
NextFrame()451 nsIFrame* NextFrame() const { return mFrame; }
452
453 protected:
454 nsIFrame* mPrev;
455 };
456
457 class Iterator
458 {
459 public:
Iterator(const nsFrameList & aList,nsIFrame * aCurrent)460 Iterator(const nsFrameList& aList, nsIFrame* aCurrent)
461 : mList(aList)
462 , mCurrent(aCurrent)
463 {}
464
Iterator(const Iterator & aOther)465 Iterator(const Iterator& aOther)
466 : mList(aOther.mList)
467 , mCurrent(aOther.mCurrent)
468 {}
469
470 nsIFrame* operator*() const { return mCurrent; }
471
472 // The operators need to know about nsIFrame, hence the
473 // implementations are in nsIFrame.h
474 Iterator& operator++();
475 Iterator& operator--();
476
477 Iterator operator++(int) { auto ret = *this; ++*this; return ret; }
478 Iterator operator--(int) { auto ret = *this; --*this; return ret; }
479
480 friend bool operator==(const Iterator& aIter1, const Iterator& aIter2);
481 friend bool operator!=(const Iterator& aIter1, const Iterator& aIter2);
482
483 private:
484 const nsFrameList& mList;
485 nsIFrame* mCurrent;
486 };
487
488 typedef Iterator iterator;
489 typedef Iterator const_iterator;
490 typedef mozilla::ReverseIterator<Iterator> reverse_iterator;
491 typedef mozilla::ReverseIterator<Iterator> const_reverse_iterator;
492
begin()493 iterator begin() const { return iterator(*this, mFirstChild); }
cbegin()494 const_iterator cbegin() const { return begin(); }
end()495 iterator end() const { return iterator(*this, nullptr); }
cend()496 const_iterator cend() const { return end(); }
rbegin()497 reverse_iterator rbegin() const { return reverse_iterator(end()); }
crbegin()498 const_reverse_iterator crbegin() const { return rbegin(); }
rend()499 reverse_iterator rend() const { return reverse_iterator(begin()); }
crend()500 const_reverse_iterator crend() const { return rend(); }
501
502 private:
503 void operator delete(void*) = delete;
504
505 #ifdef DEBUG_FRAME_LIST
506 void VerifyList() const;
507 #else
VerifyList()508 void VerifyList() const {}
509 #endif
510
511 protected:
512 /**
513 * Disconnect aFrame from its siblings. This must only be called if aFrame
514 * is NOT the first or last sibling, because otherwise its nsFrameList will
515 * have a stale mFirst/LastChild pointer. This precondition is asserted.
516 * This function is O(1).
517 */
518 static void UnhookFrameFromSiblings(nsIFrame* aFrame);
519
520 nsIFrame* mFirstChild;
521 nsIFrame* mLastChild;
522 };
523
524 inline bool
525 operator==(const nsFrameList::Iterator& aIter1,
526 const nsFrameList::Iterator& aIter2)
527 {
528 MOZ_ASSERT(&aIter1.mList == &aIter2.mList,
529 "must not compare iterator from different list");
530 return aIter1.mCurrent == aIter2.mCurrent;
531 }
532
533 inline bool
534 operator!=(const nsFrameList::Iterator& aIter1,
535 const nsFrameList::Iterator& aIter2)
536 {
537 MOZ_ASSERT(&aIter1.mList == &aIter2.mList,
538 "Must not compare iterator from different list");
539 return aIter1.mCurrent != aIter2.mCurrent;
540 }
541
542 namespace mozilla {
543 namespace layout {
544
545 /**
546 * Simple "auto_ptr" for nsFrameLists allocated from the shell arena.
547 * The frame list given to the constructor will be deallocated (if non-null)
548 * in the destructor. The frame list must then be empty.
549 */
550 class AutoFrameListPtr {
551 public:
AutoFrameListPtr(nsPresContext * aPresContext,nsFrameList * aFrameList)552 AutoFrameListPtr(nsPresContext* aPresContext, nsFrameList* aFrameList)
553 : mPresContext(aPresContext), mFrameList(aFrameList) {}
554 ~AutoFrameListPtr();
555 operator nsFrameList*() const { return mFrameList; }
556 nsFrameList* operator->() const { return mFrameList; }
557 private:
558 nsPresContext* mPresContext;
559 nsFrameList* mFrameList;
560 };
561
562 namespace detail {
563 union AlignedFrameListBytes {
564 void* ptr;
565 char bytes[sizeof(nsFrameList)];
566 };
567 extern const AlignedFrameListBytes gEmptyFrameListBytes;
568 } // namespace detail
569
570 } // namespace layout
571 } // namespace mozilla
572
573 /* static */ inline const nsFrameList&
EmptyList()574 nsFrameList::EmptyList()
575 {
576 return *reinterpret_cast<const nsFrameList*>(&mozilla::layout::detail::gEmptyFrameListBytes);
577 }
578
579 #endif /* nsFrameList_h___ */
580