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/EnumSet.h"
  14 #include "mozilla/FunctionTypeTraits.h"
  15 #include "mozilla/RefPtr.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
  30 struct FrameDestroyContext;
  31
  32 class PresShell;
  33 class FrameChildList;
  34 enum class FrameChildListID {
  35   // The individual concrete child lists.
  36   Principal,
  37   Popup,
  38   Caption,
  39   ColGroup,
  40   Absolute,
  41   Fixed,
  42   Overflow,
  43   OverflowContainers,
  44   ExcessOverflowContainers,
  45   OverflowOutOfFlow,
  46   Float,
  47   Bullet,
  48   PushedFloats,
  49   Backdrop,
  50   // A special alias for FrameChildListID::Principal that suppress the reflow
  51   // request that is normally done when manipulating child lists.
  52   NoReflowPrincipal,
  53 };
  54
  55 }  // namespace mozilla
  56
  57 // Uncomment this to enable expensive frame-list integrity checking
  58 // #define DEBUG_FRAME_LIST
  59
  60 /**
  61  * A class for managing a list of frames.
  62  */
  63 class nsFrameList {
  64   // Next()/Prev() need to know about nsIFrame. To make them inline, their
  65   // implementations are in nsIFrame.h.
  66   struct ForwardFrameTraversal final {
  67     static inline nsIFrame* Next(nsIFrame*);
  68     static inline nsIFrame* Prev(nsIFrame*);
  69   };
  70   struct BackwardFrameTraversal final {
  71     static inline nsIFrame* Next(nsIFrame*);
  72     static inline nsIFrame* Prev(nsIFrame*);
  73   };
  74
  75  public:
  76   template <typename FrameTraversal>
  77   class Iterator;
  78   class Slice;
  79
  80   using iterator = Iterator<ForwardFrameTraversal>;
  81   using const_iterator = Iterator<ForwardFrameTraversal>;
  82   using reverse_iterator = Iterator<BackwardFrameTraversal>;
  83   using const_reverse_iterator = Iterator<BackwardFrameTraversal>;
  84
  85   nsFrameList() : mFirstChild(nullptr), mLastChild(nullptr) {}
  86
  87   nsFrameList(nsIFrame* aFirstFrame, nsIFrame* aLastFrame)
  88       : mFirstChild(aFirstFrame), mLastChild(aLastFrame) {
  89     VerifyList();
  90   }
  91
  92   // nsFrameList is a move-only class by default. Use Clone() if you really want
  93   // a copy of this list.
  94   nsFrameList(const nsFrameList& aOther) = delete;
  95   nsFrameList& operator=(const nsFrameList& aOther) = delete;
  96   nsFrameList Clone() const { return nsFrameList(mFirstChild, mLastChild); }
  97
  98   /**
  99    * Transfer frames in aOther to this list. aOther becomes empty after this
 100    * operation.
 101    */
 102   nsFrameList(nsFrameList&& aOther)
 103       : mFirstChild(aOther.mFirstChild), mLastChild(aOther.mLastChild) {
 104     aOther.Clear();
 105     VerifyList();
 106   }
 107   nsFrameList& operator=(nsFrameList&& aOther) {
 108     if (this != &aOther) {
 109       MOZ_ASSERT(IsEmpty(), "Assigning to a non-empty list will lose frames!");
 110       mFirstChild = aOther.FirstChild();
 111       mLastChild = aOther.LastChild();
 112       aOther.Clear();
 113     }
 114     return *this;
 115   }
 116
 117   /**
 118    * Infallibly allocate a nsFrameList from the shell arena.
 119    */
 120   void* operator new(size_t sz, mozilla::PresShell* aPresShell);
 121
 122   /**
 123    * Deallocate this list that was allocated from the shell arena.
 124    * The list is required to be empty.
 125    */
 126   void Delete(mozilla::PresShell* aPresShell);
 127
 128   /**
 129    * For each frame in this list: remove it from the list then call
 130    * Destroy() on it with the passed context as an argument.
 131    */
 132   void DestroyFrames(mozilla::FrameDestroyContext&);
 133
 134   void Clear() { mFirstChild = mLastChild = nullptr; }
 135
 136   /**
 137    * Append aFrameList to this list.  If aParent is not null,
 138    * reparents the newly added frames.  Clears out aFrameList and
 139    * returns a list slice represening the newly-appended frames.
 140    */
 141   Slice AppendFrames(nsContainerFrame* aParent, nsFrameList&& aFrameList) {
 142     return InsertFrames(aParent, LastChild(), std::move(aFrameList));
 143   }
 144
 145   /**
 146    * Append aFrame to this list.  If aParent is not null,
 147    * reparents the newly added frame.
 148    */
 149   void AppendFrame(nsContainerFrame* aParent, nsIFrame* aFrame) {
 150     AppendFrames(aParent, nsFrameList(aFrame, aFrame));
 151   }
 152
 153   /**
 154    * Take aFrame out of the frame list. This also disconnects aFrame
 155    * from the sibling list. The frame must be non-null and present on
 156    * this list.
 157    */
 158   void RemoveFrame(nsIFrame* aFrame);
 159
 160   /**
 161    * Take all the frames before aFrame out of the frame list; aFrame and all the
 162    * frames after it stay in this list. If aFrame is nullptr, remove the entire
 163    * frame list.
 164    * @param aFrame a frame in this frame list, or nullptr.
 165    * @return the removed frames, if any.
 166    */
 167   [[nodiscard]] nsFrameList TakeFramesBefore(nsIFrame* aFrame);
 168
 169   /**
 170    * Take all the frames after aFrame out of the frame list; aFrame and all the
 171    * frames before it stay in this list. If aFrame is nullptr, removes the
 172    * entire list.
 173    * @param aFrame a frame in this list, or nullptr.
 174    * @return the removed frames, if any.
 175    */
 176   [[nodiscard]] nsFrameList TakeFramesAfter(nsIFrame* aFrame);
 177
 178   /**
 179    * Take the first frame (if any) out of the frame list.
 180    * @return the first child, or nullptr if the list is empty
 181    */
 182   nsIFrame* RemoveFirstChild();
 183
 184   /**
 185    * The following two functions are intended to be used in concert for
 186    * removing a frame from its frame list when the set of possible frame
 187    * lists is known in advance, but the exact frame list is unknown.
 188    * aFrame must be non-null.
 189    * Example use:
 190    *   bool removed = frameList1.StartRemoveFrame(aFrame) ||
 191    *                  frameList2.ContinueRemoveFrame(aFrame) ||
 192    *                  frameList3.ContinueRemoveFrame(aFrame);
 193    *   MOZ_ASSERT(removed);
 194    *
 195    * @note One of the frame lists MUST contain aFrame, if it's on some other
 196    *       frame list then the example above will likely lead to crashes.
 197    * This function is O(1).
 198    * @return true iff aFrame was removed from /some/ list, not necessarily
 199    *         this one.  If it was removed from a different list then it is
 200    *         guaranteed that that list is still non-empty.
 201    * (this method is implemented in nsIFrame.h to be able to inline)
 202    */
 203   inline bool StartRemoveFrame(nsIFrame* aFrame);
 204
 205   /**
 206    * Precondition: StartRemoveFrame MUST be called before this.
 207    * This function is O(1).
 208    * @see StartRemoveFrame
 209    * @return true iff aFrame was removed from this list
 210    * (this method is implemented in nsIFrame.h to be able to inline)
 211    */
 212   inline bool ContinueRemoveFrame(nsIFrame* aFrame);
 213
 214   /**
 215    * Take a frame out of the frame list and then destroy it.
 216    * The frame must be non-null and present on this list.
 217    */
 218   void DestroyFrame(mozilla::FrameDestroyContext&, nsIFrame*);
 219
 220   /**
 221    * Insert aFrame right after aPrevSibling, or prepend it to this
 222    * list if aPrevSibling is null. If aParent is not null, also
 223    * reparents newly-added frame. Note that this method always
 224    * sets the frame's nextSibling pointer.
 225    */
 226   void InsertFrame(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
 227                    nsIFrame* aFrame) {
 228     InsertFrames(aParent, aPrevSibling, nsFrameList(aFrame, aFrame));
 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   /**
 241    * Split this list just before the first frame that matches aPredicate,
 242    * and return a nsFrameList containing all the frames before it. The
 243    * matched frame and all frames after it stay in this list. If no matched
 244    * frame exists, all the frames are drained into the returned list, and
 245    * this list ends up empty.
 246    *
 247    * aPredicate should be of this function signature: bool(nsIFrame*).
 248    */
 249   template <typename Predicate>
 250   nsFrameList Split(Predicate&& aPredicate) {
 251     static_assert(
 252         std::is_same<
 253             typename mozilla::FunctionTypeTraits<Predicate>::ReturnType,
 254             bool>::value &&
 255             mozilla::FunctionTypeTraits<Predicate>::arity == 1 &&
 256             std::is_same<typename mozilla::FunctionTypeTraits<
 257                              Predicate>::template ParameterType<0>,
 258                          nsIFrame*>::value,
 259         "aPredicate should be of this function signature: bool(nsIFrame*)");
 260
 261     for (nsIFrame* f : *this) {
 262       if (aPredicate(f)) {
 263         return TakeFramesBefore(f);
 264       }
 265     }
 266     return std::move(*this);
 267   }
 268
 269   nsIFrame* FirstChild() const { return mFirstChild; }
 270
 271   nsIFrame* LastChild() const { return mLastChild; }
 272
 273   nsIFrame* FrameAt(int32_t aIndex) const;
 274   int32_t IndexOf(nsIFrame* aFrame) const;
 275
 276   bool IsEmpty() const { return nullptr == mFirstChild; }
 277
 278   bool NotEmpty() const { return nullptr != mFirstChild; }
 279
 280   /**
 281    * Return true if aFrame is on this list.
 282    * @note this method has O(n) time complexity over the length of the list
 283    * XXXmats: ideally, we should make this function #ifdef DEBUG
 284    */
 285   bool ContainsFrame(const nsIFrame* aFrame) const;
 286
 287   /**
 288    * Get the number of frames in this list. Note that currently the
 289    * implementation has O(n) time complexity. Do not call it repeatedly in hot
 290    * code.
 291    * XXXmats: ideally, we should make this function #ifdef DEBUG
 292    */
 293   int32_t GetLength() const;
 294
 295   /**
 296    * If this frame list has only one frame, return that frame.
 297    * Otherwise, return null.
 298    */
 299   nsIFrame* OnlyChild() const {
 300     if (FirstChild() == LastChild()) {
 301       return FirstChild();
 302     }
 303     return nullptr;
 304   }
 305
 306   /**
 307    * Call SetParent(aParent) for each frame in this list.
 308    * @param aParent the new parent frame, must be non-null
 309    */
 310   void ApplySetParent(nsContainerFrame* aParent) const;
 311
 312   /**
 313    * If this frame list is non-empty then append it to aLists as the
 314    * aListID child list.
 315    */
 316   inline void AppendIfNonempty(nsTArray<mozilla::FrameChildList>* aLists,
 317                                mozilla::FrameChildListID aListID) const {
 318     if (NotEmpty()) {
 319       aLists->EmplaceBack(*this, aListID);
 320     }
 321   }
 322
 323   /**
 324    * Return the frame before this frame in visual order (after Bidi reordering).
 325    * If aFrame is null, return the last frame in visual order.
 326    */
 327   nsIFrame* GetPrevVisualFor(nsIFrame* aFrame) const;
 328
 329   /**
 330    * Return the frame after this frame in visual order (after Bidi reordering).
 331    * If aFrame is null, return the first frame in visual order.
 332    */
 333   nsIFrame* GetNextVisualFor(nsIFrame* aFrame) const;
 334
 335 #ifdef DEBUG_FRAME_DUMP
 336   void List(FILE* out) const;
 337 #endif
 338
 339   static inline const nsFrameList& EmptyList();
 340
 341   /**
 342    * A class representing a slice of a frame list.
 343    */
 344   class Slice {
 345    public:
 346     // Implicit on purpose, so that we can easily create Slice from nsFrameList
 347     // via this impicit constructor.
 348     MOZ_IMPLICIT Slice(const nsFrameList& aList)
 349         : mStart(aList.FirstChild()), mEnd(nullptr) {}
 350     Slice(nsIFrame* aStart, nsIFrame* aEnd) : mStart(aStart), mEnd(aEnd) {}
 351
 352     iterator begin() const { return iterator(mStart); }
 353     const_iterator cbegin() const { return begin(); }
 354     iterator end() const { return iterator(mEnd); }
 355     const_iterator cend() const { return end(); }
 356
 357    private:
 358     // Our starting frame.
 359     nsIFrame* const mStart;
 360
 361     // The first frame that is NOT in the slice. May be null.
 362     nsIFrame* const mEnd;
 363   };
 364
 365   template <typename FrameTraversal>
 366   class Iterator final {
 367    public:
 368     // It is disputable whether these type definitions are correct, since
 369     // operator* doesn't return a reference at all. Also, the iterator_category
 370     // can be at most std::input_iterator_tag (rather than
 371     // std::bidrectional_iterator_tag, as it might seem), because it is a
 372     // stashing iterator. See also, e.g.,
 373     // https://stackoverflow.com/questions/50909701/what-should-be-iterator-category-for-a-stashing-iterator
 374     using value_type = nsIFrame* const;
 375     using pointer = value_type*;
 376     using reference = value_type&;
 377     using difference_type = ptrdiff_t;
 378     using iterator_category = std::input_iterator_tag;
 379
 380     explicit constexpr Iterator(nsIFrame* aCurrent) : mCurrent(aCurrent) {}
 381
 382     nsIFrame* operator*() const { return mCurrent; }
 383
 384     Iterator& operator++() {
 385       mCurrent = FrameTraversal::Next(mCurrent);
 386       return *this;
 387     }
 388     Iterator& operator--() {
 389       mCurrent = FrameTraversal::Prev(mCurrent);
 390       return *this;
 391     }
 392
 393     Iterator operator++(int) {
 394       auto ret = *this;
 395       ++*this;
 396       return ret;
 397     }
 398     Iterator operator--(int) {
 399       auto ret = *this;
 400       --*this;
 401       return ret;
 402     }
 403
 404     bool operator==(const Iterator<FrameTraversal>& aOther) const {
 405       return mCurrent == aOther.mCurrent;
 406     }
 407
 408     bool operator!=(const Iterator<FrameTraversal>& aOther) const {
 409       return !(*this == aOther);
 410     }
 411
 412    private:
 413     nsIFrame* mCurrent;
 414   };
 415
 416   iterator begin() const { return iterator(mFirstChild); }
 417   const_iterator cbegin() const { return begin(); }
 418   iterator end() const { return iterator(nullptr); }
 419   const_iterator cend() const { return end(); }
 420   reverse_iterator rbegin() const { return reverse_iterator(mLastChild); }
 421   const_reverse_iterator crbegin() const { return rbegin(); }
 422   reverse_iterator rend() const { return reverse_iterator(nullptr); }
 423   const_reverse_iterator crend() const { return rend(); }
 424
 425  private:
 426   void operator delete(void*) = delete;
 427
 428 #ifdef DEBUG_FRAME_LIST
 429   void VerifyList() const;
 430 #else
 431   void VerifyList() const {}
 432 #endif
 433
 434  protected:
 435   /**
 436    * Disconnect aFrame from its siblings.  This must only be called if aFrame
 437    * is NOT the first or last sibling, because otherwise its nsFrameList will
 438    * have a stale mFirst/LastChild pointer.  This precondition is asserted.
 439    * This function is O(1).
 440    */
 441   static void UnhookFrameFromSiblings(nsIFrame* aFrame);
 442
 443   nsIFrame* mFirstChild;
 444   nsIFrame* mLastChild;
 445 };
 446
 447 namespace mozilla {
 448
 449 #ifdef DEBUG_FRAME_DUMP
 450 extern const char* ChildListName(FrameChildListID aListID);
 451 #endif
 452
 453 using FrameChildListIDs = EnumSet<FrameChildListID>;
 454
 455 class FrameChildList {
 456  public:
 457   FrameChildList(const nsFrameList& aList, FrameChildListID aID)
 458       : mList(aList.Clone()), mID(aID) {}
 459   nsFrameList mList;
 460   FrameChildListID mID;
 461 };
 462
 463 /**
 464  * Simple "auto_ptr" for nsFrameLists allocated from the shell arena.
 465  * The frame list given to the constructor will be deallocated (if non-null)
 466  * in the destructor.  The frame list must then be empty.
 467  */
 468 class MOZ_RAII AutoFrameListPtr final {
 469  public:
 470   AutoFrameListPtr(nsPresContext* aPresContext, nsFrameList* aFrameList)
 471       : mPresContext(aPresContext), mFrameList(aFrameList) {}
 472   ~AutoFrameListPtr();
 473   operator nsFrameList*() const { return mFrameList; }
 474   nsFrameList* operator->() const { return mFrameList; }
 475
 476  private:
 477   nsPresContext* mPresContext;
 478   nsFrameList* mFrameList;
 479 };
 480
 481 namespace detail {
 482 union AlignedFrameListBytes {
 483   void* ptr;
 484   char bytes[sizeof(nsFrameList)];
 485 };
 486 extern const AlignedFrameListBytes gEmptyFrameListBytes;
 487 }  // namespace detail
 488
 489 }  // namespace mozilla
 490
 491 /* static */ inline const nsFrameList& nsFrameList::EmptyList() {
 492   return *reinterpret_cast<const nsFrameList*>(
 493       &mozilla::detail::gEmptyFrameListBytes);
 494 }
 495
 496 #endif /* nsFrameList_h___ */