layout/generic/nsFrameList.h

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