Line data Source code
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:
60 3398 : nsFrameList() :
61 3398 : mFirstChild(nullptr), mLastChild(nullptr)
62 : {
63 3398 : }
64 :
65 130 : nsFrameList(nsIFrame* aFirstFrame, nsIFrame* aLastFrame) :
66 130 : mFirstChild(aFirstFrame), mLastChild(aLastFrame)
67 : {
68 130 : VerifyList();
69 130 : }
70 :
71 11446 : nsFrameList(const nsFrameList& aOther) :
72 11446 : mFirstChild(aOther.mFirstChild), mLastChild(aOther.mLastChild)
73 : {
74 11446 : }
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 :
99 832 : void Clear() { mFirstChild = mLastChild = nullptr; }
100 :
101 : void SetFrames(nsIFrame* aFrameList);
102 :
103 415 : void SetFrames(nsFrameList& aFrameList) {
104 415 : NS_PRECONDITION(!mFirstChild, "Losing frames");
105 :
106 415 : mFirstChild = aFrameList.FirstChild();
107 415 : mLastChild = aFrameList.LastChild();
108 415 : aFrameList.Clear();
109 415 : }
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 : */
118 45 : Slice AppendFrames(nsContainerFrame* aParent, nsFrameList& aFrameList) {
119 45 : 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 : */
127 0 : void AppendFrame(nsContainerFrame* aParent, nsIFrame* aFrame) {
128 0 : nsFrameList temp(aFrame, aFrame);
129 0 : AppendFrames(aParent, temp);
130 0 : }
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 : */
195 0 : void InsertFrame(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
196 : nsIFrame* aFrame) {
197 0 : nsFrameList temp(aFrame, aFrame);
198 0 : InsertFrames(aParent, aPrevSibling, temp);
199 0 : }
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 :
227 16835 : nsIFrame* FirstChild() const {
228 16835 : return mFirstChild;
229 : }
230 :
231 1043 : nsIFrame* LastChild() const {
232 1043 : return mLastChild;
233 : }
234 :
235 : nsIFrame* FrameAt(int32_t aIndex) const;
236 : int32_t IndexOf(nsIFrame* aFrame) const;
237 :
238 2538 : bool IsEmpty() const {
239 2538 : return nullptr == mFirstChild;
240 : }
241 :
242 7123 : bool NotEmpty() const {
243 7123 : 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 : */
259 58 : nsIFrame* OnlyChild() const {
260 58 : if (FirstChild() == LastChild()) {
261 58 : return FirstChild();
262 : }
263 0 : 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.
309 4519 : MOZ_IMPLICIT Slice(const nsFrameList& aList) :
310 : #ifdef DEBUG
311 : mList(aList),
312 : #endif
313 4519 : mStart(aList.FirstChild()),
314 9038 : mEnd(nullptr)
315 4519 : {}
316 :
317 120 : Slice(const nsFrameList& aList, nsIFrame* aStart, nsIFrame* aEnd) :
318 : #ifdef DEBUG
319 : mList(aList),
320 : #endif
321 : mStart(aStart),
322 120 : mEnd(aEnd)
323 120 : {}
324 :
325 4552 : Slice(const Slice& aOther) :
326 : #ifdef DEBUG
327 4552 : mList(aOther.mList),
328 : #endif
329 4552 : mStart(aOther.mStart),
330 9104 : mEnd(aOther.mEnd)
331 4552 : {}
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:
344 4552 : explicit Enumerator(const Slice& aSlice) :
345 : #ifdef DEBUG
346 : mSlice(aSlice),
347 : #endif
348 4552 : mFrame(aSlice.mStart),
349 9104 : mEnd(aSlice.mEnd)
350 4552 : {}
351 :
352 : Enumerator(const Enumerator& aOther) :
353 : #ifdef DEBUG
354 : mSlice(aOther.mSlice),
355 : #endif
356 : mFrame(aOther.mFrame),
357 : mEnd(aOther.mEnd)
358 : {}
359 :
360 25122 : 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 25122 : 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 : */
376 6886 : nsIFrame* get() const {
377 6886 : NS_PRECONDITION(!AtEnd(), "Enumerator is at end");
378 6886 : 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 : */
385 0 : Enumerator GetUnlimitedEnumerator() const {
386 0 : return Enumerator(*this, nullptr);
387 : }
388 :
389 : #ifdef DEBUG
390 0 : const nsFrameList& List() const { return mSlice.mList; }
391 : #endif
392 :
393 : protected:
394 0 : Enumerator(const Enumerator& aOther, const nsIFrame* const aNewEnd):
395 : #ifdef DEBUG
396 : mSlice(aOther.mSlice),
397 : #endif
398 0 : mFrame(aOther.mFrame),
399 0 : mEnd(aNewEnd)
400 0 : {}
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 :
425 0 : explicit FrameLinkEnumerator(const nsFrameList& aList) :
426 : Enumerator(aList),
427 0 : mPrev(nullptr)
428 0 : {}
429 :
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 :
448 0 : bool AtEnd() const { return Enumerator::AtEnd(); }
449 :
450 0 : nsIFrame* PrevFrame() const { return mPrev; }
451 0 : nsIFrame* NextFrame() const { return mFrame; }
452 :
453 : protected:
454 : nsIFrame* mPrev;
455 : };
456 :
457 : class Iterator
458 : {
459 : public:
460 6380 : Iterator(const nsFrameList& aList, nsIFrame* aCurrent)
461 6380 : : mList(aList)
462 6380 : , mCurrent(aCurrent)
463 6380 : {}
464 :
465 0 : Iterator(const Iterator& aOther)
466 0 : : mList(aOther.mList)
467 0 : , mCurrent(aOther.mCurrent)
468 0 : {}
469 :
470 3086 : 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 :
493 3190 : iterator begin() const { return iterator(*this, mFirstChild); }
494 : const_iterator cbegin() const { return begin(); }
495 3190 : iterator end() const { return iterator(*this, nullptr); }
496 : const_iterator cend() const { return end(); }
497 0 : reverse_iterator rbegin() const { return reverse_iterator(end()); }
498 : const_reverse_iterator crbegin() const { return rbegin(); }
499 0 : reverse_iterator rend() const { return reverse_iterator(begin()); }
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
508 250 : 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 0 : operator==(const nsFrameList::Iterator& aIter1,
526 : const nsFrameList::Iterator& aIter2)
527 : {
528 0 : MOZ_ASSERT(&aIter1.mList == &aIter2.mList,
529 : "must not compare iterator from different list");
530 0 : return aIter1.mCurrent == aIter2.mCurrent;
531 : }
532 :
533 : inline bool
534 6276 : operator!=(const nsFrameList::Iterator& aIter1,
535 : const nsFrameList::Iterator& aIter2)
536 : {
537 6276 : MOZ_ASSERT(&aIter1.mList == &aIter2.mList,
538 : "Must not compare iterator from different list");
539 6276 : 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:
552 32 : AutoFrameListPtr(nsPresContext* aPresContext, nsFrameList* aFrameList)
553 32 : : mPresContext(aPresContext), mFrameList(aFrameList) {}
554 : ~AutoFrameListPtr();
555 32 : operator nsFrameList*() const { return mFrameList; }
556 0 : 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&
574 485 : nsFrameList::EmptyList()
575 : {
576 485 : return *reinterpret_cast<const nsFrameList*>(&mozilla::layout::detail::gEmptyFrameListBytes);
577 : }
578 :
579 : #endif /* nsFrameList_h___ */
|
