layout/generic/nsFrameList.h

   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)
  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;
  61   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:
  76   nsFrameList() : mFirstChild(nullptr), mLastChild(nullptr) {}
  77
  78   nsFrameList(nsIFrame* aFirstFrame, nsIFrame* aLastFrame)
  79       : mFirstChild(aFirstFrame), mLastChild(aLastFrame) {
  80     VerifyList();
  81   }
  82
  83   nsFrameList(const nsFrameList& aOther)
  84       : mFirstChild(aOther.mFirstChild), mLastChild(aOther.mLastChild) {}
  85
  86   /**
  87    * Infallibly allocate a nsFrameList from the shell arena.
  88    */
  89   void* operator new(size_t sz, mozilla::PresShell* aPresShell);
  90
  91   /**
  92    * Deallocate this list that was allocated from the shell arena.
  93    * The list is required to be empty.
  94    */
  95   void Delete(mozilla::PresShell* aPresShell);
  96
  97   /**
  98    * For each frame in this list: remove it from the list then call
  99    * Destroy() on it.
 100    */
 101   void DestroyFrames();
 102
 103   /**
 104    * For each frame in this list: remove it from the list then call
 105    * DestroyFrom(aDestructRoot, aPostDestroyData) on it.
 106    */
 107   void DestroyFramesFrom(
 108       nsIFrame* aDestructRoot,
 109       mozilla::layout::PostFrameDestroyData& aPostDestroyData);
 110
 111   void Clear() { mFirstChild = mLastChild = nullptr; }
 112
 113   void SetFrames(nsIFrame* aFrameList);
 114
 115   void SetFrames(nsFrameList& aFrameList) {
 116     MOZ_ASSERT(!mFirstChild, "Losing frames");
 117
 118     mFirstChild = aFrameList.FirstChild();
 119     mLastChild = aFrameList.LastChild();
 120     aFrameList.Clear();
 121   }
 122
 123   class Slice;
 124
 125   /**
 126    * Append aFrameList to this list.  If aParent is not null,
 127    * reparents the newly added frames.  Clears out aFrameList and
 128    * returns a list slice represening the newly-appended frames.
 129    */
 130   Slice AppendFrames(nsContainerFrame* aParent, nsFrameList& aFrameList) {
 131     return InsertFrames(aParent, LastChild(), aFrameList);
 132   }
 133
 134   /**
 135    * Append aFrame to this list.  If aParent is not null,
 136    * reparents the newly added frame.
 137    */
 138   void AppendFrame(nsContainerFrame* aParent, nsIFrame* aFrame) {
 139     nsFrameList temp(aFrame, aFrame);
 140     AppendFrames(aParent, temp);
 141   }
 142
 143   /**
 144    * Take aFrame out of the frame list. This also disconnects aFrame
 145    * from the sibling list. The frame must be non-null and present on
 146    * this list.
 147    */
 148   void RemoveFrame(nsIFrame* aFrame);
 149
 150   /**
 151    * Take the frames after aAfterFrame out of the frame list.  If
 152    * aAfterFrame is null, removes the entire list.
 153    * @param aAfterFrame a frame in this list, or null
 154    * @return the removed frames, if any
 155    */
 156   nsFrameList RemoveFramesAfter(nsIFrame* aAfterFrame);
 157
 158   /**
 159    * Take the first frame (if any) out of the frame list.
 160    * @return the first child, or nullptr if the list is empty
 161    */
 162   nsIFrame* RemoveFirstChild();
 163
 164   /**
 165    * The following two functions are intended to be used in concert for
 166    * removing a frame from its frame list when the set of possible frame
 167    * lists is known in advance, but the exact frame list is unknown.
 168    * aFrame must be non-null.
 169    * Example use:
 170    *   bool removed = frameList1.StartRemoveFrame(aFrame) ||
 171    *                  frameList2.ContinueRemoveFrame(aFrame) ||
 172    *                  frameList3.ContinueRemoveFrame(aFrame);
 173    *   MOZ_ASSERT(removed);
 174    *
 175    * @note One of the frame lists MUST contain aFrame, if it's on some other
 176    *       frame list then the example above will likely lead to crashes.
 177    * This function is O(1).
 178    * @return true iff aFrame was removed from /some/ list, not necessarily
 179    *         this one.  If it was removed from a different list then it is
 180    *         guaranteed that that list is still non-empty.
 181    * (this method is implemented in nsIFrame.h to be able to inline)
 182    */
 183   inline bool StartRemoveFrame(nsIFrame* aFrame);
 184
 185   /**
 186    * Precondition: StartRemoveFrame MUST be called before this.
 187    * This function is O(1).
 188    * @see StartRemoveFrame
 189    * @return true iff aFrame was removed from this list
 190    * (this method is implemented in nsIFrame.h to be able to inline)
 191    */
 192   inline bool ContinueRemoveFrame(nsIFrame* aFrame);
 193
 194   /**
 195    * Take aFrame out of the frame list and then destroy it.
 196    * The frame must be non-null and present on this list.
 197    */
 198   void DestroyFrame(nsIFrame* aFrame);
 199
 200   /**
 201    * Insert aFrame right after aPrevSibling, or prepend it to this
 202    * list if aPrevSibling is null. If aParent is not null, also
 203    * reparents newly-added frame. Note that this method always
 204    * sets the frame's nextSibling pointer.
 205    */
 206   void InsertFrame(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
 207                    nsIFrame* aFrame) {
 208     nsFrameList temp(aFrame, aFrame);
 209     InsertFrames(aParent, aPrevSibling, temp);
 210   }
 211
 212   /**
 213    * Inserts aFrameList into this list after aPrevSibling (at the beginning if
 214    * aPrevSibling is null).  If aParent is not null, reparents the newly added
 215    * frames.  Clears out aFrameList and returns a list slice representing the
 216    * newly-inserted frames.
 217    */
 218   Slice InsertFrames(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
 219                      nsFrameList& aFrameList);
 220
 221   class FrameLinkEnumerator;
 222
 223   /**
 224    * Split this list just before the first frame that matches aPredicate,
 225    * and return a nsFrameList containing all the frames before it. The
 226    * matched frame and all frames after it stay in this list. If no matched
 227    * frame exists, all the frames are drained into the returned list, and
 228    * this list ends up empty.
 229    *
 230    * aPredicate should be of this function signature: bool(nsIFrame*).
 231    */
 232   template <typename Predicate>
 233   nsFrameList Split(Predicate&& aPredicate) {
 234     static_assert(
 235         std::is_same<
 236             typename mozilla::FunctionTypeTraits<Predicate>::ReturnType,
 237             bool>::value &&
 238             mozilla::FunctionTypeTraits<Predicate>::arity == 1 &&
 239             std::is_same<typename mozilla::FunctionTypeTraits<
 240                              Predicate>::template ParameterType<0>,
 241                          nsIFrame*>::value,
 242         "aPredicate should be of this function signature: bool(nsIFrame*)");
 243
 244     FrameLinkEnumerator link(*this);
 245     link.Find(aPredicate);
 246     return ExtractHead(link);
 247   }
 248
 249   /**
 250    * Split this frame list such that all the frames before the link pointed to
 251    * by aLink end up in the returned list, while the remaining frames stay in
 252    * this list.  After this call, aLink points to the beginning of this list.
 253    */
 254   nsFrameList ExtractHead(FrameLinkEnumerator& aLink);
 255
 256   /**
 257    * Split this frame list such that all the frames coming after the link
 258    * pointed to by aLink end up in the returned list, while the frames before
 259    * that link stay in this list.  After this call, aLink is at end.
 260    */
 261   nsFrameList ExtractTail(FrameLinkEnumerator& aLink);
 262
 263   nsIFrame* FirstChild() const { return mFirstChild; }
 264
 265   nsIFrame* LastChild() const { return mLastChild; }
 266
 267   nsIFrame* FrameAt(int32_t aIndex) const;
 268   int32_t IndexOf(nsIFrame* aFrame) const;
 269
 270   bool IsEmpty() const { return nullptr == mFirstChild; }
 271
 272   bool NotEmpty() const { return nullptr != mFirstChild; }
 273
 274   /**
 275    * Return true if aFrame is on this list.
 276    * @note this method has O(n) time complexity over the length of the list
 277    * XXXmats: ideally, we should make this function #ifdef DEBUG
 278    */
 279   bool ContainsFrame(const nsIFrame* aFrame) const;
 280
 281   /**
 282    * Get the number of frames in this list. Note that currently the
 283    * implementation has O(n) time complexity. Do not call it repeatedly in hot
 284    * code.
 285    * XXXmats: ideally, we should make this function #ifdef DEBUG
 286    */
 287   int32_t GetLength() const;
 288
 289   /**
 290    * If this frame list has only one frame, return that frame.
 291    * Otherwise, return null.
 292    */
 293   nsIFrame* OnlyChild() const {
 294     if (FirstChild() == LastChild()) {
 295       return FirstChild();
 296     }
 297     return nullptr;
 298   }
 299
 300   /**
 301    * Call SetParent(aParent) for each frame in this list.
 302    * @param aParent the new parent frame, must be non-null
 303    */
 304   void ApplySetParent(nsContainerFrame* aParent) const;
 305
 306   /**
 307    * If this frame list is non-empty then append it to aLists as the
 308    * aListID child list.
 309    * (this method is implemented in FrameChildList.h for dependency reasons)
 310    */
 311   inline void AppendIfNonempty(
 312       nsTArray<mozilla::layout::FrameChildList>* aLists,
 313       mozilla::layout::FrameChildListID aListID) const;
 314
 315   /**
 316    * Return the frame before this frame in visual order (after Bidi reordering).
 317    * If aFrame is null, return the last frame in visual order.
 318    */
 319   nsIFrame* GetPrevVisualFor(nsIFrame* aFrame) const;
 320
 321   /**
 322    * Return the frame after this frame in visual order (after Bidi reordering).
 323    * If aFrame is null, return the first frame in visual order.
 324    */
 325   nsIFrame* GetNextVisualFor(nsIFrame* aFrame) const;
 326
 327 #ifdef DEBUG_FRAME_DUMP
 328   void List(FILE* out) const;
 329 #endif
 330
 331   static inline const nsFrameList& EmptyList();
 332
 333   class Enumerator;
 334
 335   /**
 336    * A class representing a slice of a frame list.
 337    */
 338   class Slice {
 339     friend class Enumerator;
 340
 341    public:
 342     // Implicit on purpose, so that we can easily create enumerators from
 343     // nsFrameList via this impicit constructor.
 344     MOZ_IMPLICIT Slice(const nsFrameList& aList)
 345         :
 346 #ifdef DEBUG
 347           mList(aList),
 348 #endif
 349           mStart(aList.FirstChild()),
 350           mEnd(nullptr) {
 351     }
 352
 353     Slice(const nsFrameList& aList, nsIFrame* aStart, nsIFrame* aEnd)
 354         :
 355 #ifdef DEBUG
 356           mList(aList),
 357 #endif
 358           mStart(aStart),
 359           mEnd(aEnd) {
 360     }
 361
 362     Slice(const Slice& aOther)
 363         :
 364 #ifdef DEBUG
 365           mList(aOther.mList),
 366 #endif
 367           mStart(aOther.mStart),
 368           mEnd(aOther.mEnd) {
 369     }
 370
 371    private:
 372 #ifdef DEBUG
 373     const nsFrameList& mList;
 374 #endif
 375     nsIFrame* const mStart;      // our starting frame
 376     const nsIFrame* const mEnd;  // The first frame that is NOT in the slice.
 377                                  // May be null.
 378   };
 379
 380   class Enumerator {
 381    public:
 382     explicit Enumerator(const Slice& aSlice)
 383         :
 384 #ifdef DEBUG
 385           mSlice(aSlice),
 386 #endif
 387           mFrame(aSlice.mStart),
 388           mEnd(aSlice.mEnd) {
 389     }
 390
 391     Enumerator(const Enumerator& aOther)
 392         :
 393 #ifdef DEBUG
 394           mSlice(aOther.mSlice),
 395 #endif
 396           mFrame(aOther.mFrame),
 397           mEnd(aOther.mEnd) {
 398     }
 399
 400     bool AtEnd() const {
 401       // Can't just check mEnd, because some table code goes and destroys the
 402       // tail of the frame list (including mEnd!) while iterating over the
 403       // frame list.
 404       return !mFrame || mFrame == mEnd;
 405     }
 406
 407     /* Next() needs to know about nsIFrame, and nsIFrame will need to
 408        know about nsFrameList methods, so in order to inline this put
 409        the implementation in nsIFrame.h */
 410     inline void Next();
 411
 412     /**
 413      * Get the current frame we're pointing to.  Do not call this on an
 414      * iterator that is at end!
 415      */
 416     nsIFrame* get() const {
 417       MOZ_ASSERT(!AtEnd(), "Enumerator is at end");
 418       return mFrame;
 419     }
 420
 421     /**
 422      * Get an enumerator that is just like this one, but not limited in terms of
 423      * the part of the list it will traverse.
 424      */
 425     Enumerator GetUnlimitedEnumerator() const {
 426       return Enumerator(*this, nullptr);
 427     }
 428
 429 #ifdef DEBUG
 430     const nsFrameList& List() const { return mSlice.mList; }
 431 #endif
 432
 433    protected:
 434     Enumerator(const Enumerator& aOther, const nsIFrame* const aNewEnd)
 435         :
 436 #ifdef DEBUG
 437           mSlice(aOther.mSlice),
 438 #endif
 439           mFrame(aOther.mFrame),
 440           mEnd(aNewEnd) {
 441     }
 442
 443 #ifdef DEBUG
 444     /* Has to be an object, not a reference, since the slice could
 445        well be a temporary constructed from an nsFrameList */
 446     const Slice mSlice;
 447 #endif
 448     nsIFrame* mFrame;            // our current frame.
 449     const nsIFrame* const mEnd;  // The first frame we should NOT enumerate.
 450                                  // May be null.
 451   };
 452
 453   /**
 454    * A class that can be used to enumerate links between frames.  When created
 455    * from an nsFrameList, it points to the "link" immediately before the first
 456    * frame.  It can then be advanced until it points to the "link" immediately
 457    * after the last frame.  At any position, PrevFrame() and NextFrame() are
 458    * the frames before and after the given link.  This means PrevFrame() is
 459    * null when the enumerator is at the beginning of the list and NextFrame()
 460    * is null when it's AtEnd().
 461    */
 462   class FrameLinkEnumerator : private Enumerator {
 463    public:
 464     friend class nsFrameList;
 465
 466     explicit FrameLinkEnumerator(const nsFrameList& aList)
 467         : Enumerator(aList), mPrev(nullptr) {}
 468
 469     FrameLinkEnumerator(const FrameLinkEnumerator& aOther)
 470         : Enumerator(aOther), mPrev(aOther.mPrev) {}
 471
 472     /* This constructor needs to know about nsIFrame, and nsIFrame will need to
 473        know about nsFrameList methods, so in order to inline this put
 474        the implementation in nsIFrame.h */
 475     inline FrameLinkEnumerator(const nsFrameList& aList, nsIFrame* aPrevFrame);
 476
 477     void operator=(const FrameLinkEnumerator& aOther) {
 478       MOZ_ASSERT(&List() == &aOther.List(), "Different lists?");
 479       mFrame = aOther.mFrame;
 480       mPrev = aOther.mPrev;
 481     }
 482
 483     inline void Next();
 484
 485     /**
 486      * Find the first frame from the current position that satisfies
 487      * aPredicate, and stop at it. If no such frame exists, then this method
 488      * advances to the end of the list.
 489      *
 490      * aPredicate should be of this function signature: bool(nsIFrame*).
 491      *
 492      * Note: Find() needs to see the definition of Next(), so put this
 493      * definition in nsIFrame.h.
 494      */
 495     template <typename Predicate>
 496     inline void Find(Predicate&& aPredicate);
 497
 498     bool AtEnd() const { return Enumerator::AtEnd(); }
 499
 500     nsIFrame* PrevFrame() const { return mPrev; }
 501     nsIFrame* NextFrame() const { return mFrame; }
 502
 503    protected:
 504     nsIFrame* mPrev;
 505   };
 506
 507   class Iterator {
 508    public:
 509     Iterator(const nsFrameList& aList, nsIFrame* aCurrent)
 510         : mList(aList), mCurrent(aCurrent) {}
 511
 512     Iterator(const Iterator& aOther)
 513         : mList(aOther.mList), mCurrent(aOther.mCurrent) {}
 514
 515     nsIFrame* operator*() const { return mCurrent; }
 516
 517     // The operators need to know about nsIFrame, hence the
 518     // implementations are in nsIFrame.h
 519     Iterator& operator++();
 520     Iterator& operator--();
 521
 522     Iterator operator++(int) {
 523       auto ret = *this;
 524       ++*this;
 525       return ret;
 526     }
 527     Iterator operator--(int) {
 528       auto ret = *this;
 529       --*this;
 530       return ret;
 531     }
 532
 533     friend bool operator==(const Iterator& aIter1, const Iterator& aIter2);
 534     friend bool operator!=(const Iterator& aIter1, const Iterator& aIter2);
 535
 536    private:
 537     const nsFrameList& mList;
 538     nsIFrame* mCurrent;
 539   };
 540
 541   typedef Iterator iterator;
 542   typedef Iterator const_iterator;
 543   typedef mozilla::ReverseIterator<Iterator> reverse_iterator;
 544   typedef mozilla::ReverseIterator<Iterator> const_reverse_iterator;
 545
 546   iterator begin() const { return iterator(*this, mFirstChild); }
 547   const_iterator cbegin() const { return begin(); }
 548   iterator end() const { return iterator(*this, nullptr); }
 549   const_iterator cend() const { return end(); }
 550   reverse_iterator rbegin() const { return reverse_iterator(end()); }
 551   const_reverse_iterator crbegin() const { return rbegin(); }
 552   reverse_iterator rend() const { return reverse_iterator(begin()); }
 553   const_reverse_iterator crend() const { return rend(); }
 554
 555  private:
 556   void operator delete(void*) = delete;
 557
 558 #ifdef DEBUG_FRAME_LIST
 559   void VerifyList() const;
 560 #else
 561   void VerifyList() const {}
 562 #endif
 563
 564  protected:
 565   /**
 566    * Disconnect aFrame from its siblings.  This must only be called if aFrame
 567    * is NOT the first or last sibling, because otherwise its nsFrameList will
 568    * have a stale mFirst/LastChild pointer.  This precondition is asserted.
 569    * This function is O(1).
 570    */
 571   static void UnhookFrameFromSiblings(nsIFrame* aFrame);
 572
 573   nsIFrame* mFirstChild;
 574   nsIFrame* mLastChild;
 575 };
 576
 577 inline bool operator==(const nsFrameList::Iterator& aIter1,
 578                        const nsFrameList::Iterator& aIter2) {
 579   MOZ_ASSERT(&aIter1.mList == &aIter2.mList,
 580              "must not compare iterator from different list");
 581   return aIter1.mCurrent == aIter2.mCurrent;
 582 }
 583
 584 inline bool operator!=(const nsFrameList::Iterator& aIter1,
 585                        const nsFrameList::Iterator& aIter2) {
 586   MOZ_ASSERT(&aIter1.mList == &aIter2.mList,
 587              "Must not compare iterator from different list");
 588   return aIter1.mCurrent != aIter2.mCurrent;
 589 }
 590
 591 namespace mozilla {
 592 namespace layout {
 593
 594 /**
 595  * Simple "auto_ptr" for nsFrameLists allocated from the shell arena.
 596  * The frame list given to the constructor will be deallocated (if non-null)
 597  * in the destructor.  The frame list must then be empty.
 598  */
 599 class AutoFrameListPtr {
 600  public:
 601   AutoFrameListPtr(nsPresContext* aPresContext, nsFrameList* aFrameList)
 602       : mPresContext(aPresContext), mFrameList(aFrameList) {}
 603   ~AutoFrameListPtr();
 604   operator nsFrameList*() const { return mFrameList; }
 605   nsFrameList* operator->() const { return mFrameList; }
 606
 607  private:
 608   nsPresContext* mPresContext;
 609   nsFrameList* mFrameList;
 610 };
 611
 612 namespace detail {
 613 union AlignedFrameListBytes {
 614   void* ptr;
 615   char bytes[sizeof(nsFrameList)];
 616 };
 617 extern const AlignedFrameListBytes gEmptyFrameListBytes;
 618 }  // namespace detail
 619
 620 }  // namespace layout
 621 }  // namespace mozilla
 622
 623 /* static */ inline const nsFrameList& nsFrameList::EmptyList() {
 624   return *reinterpret_cast<const nsFrameList*>(
 625       &mozilla::layout::detail::gEmptyFrameListBytes);
 626 }
 627
 628 #endif /* nsFrameList_h___ */