michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #ifndef nsFrameList_h___
michael@0: #define nsFrameList_h___
michael@0: 
michael@0: #include <stdio.h> /* for FILE* */
michael@0: #include "nsDebug.h"
michael@0: #include "nsTArrayForwardDeclare.h"
michael@0: 
michael@0: #if defined(DEBUG) || defined(MOZ_DUMP_PAINTING)
michael@0: // DEBUG_FRAME_DUMP enables nsIFrame::List and related methods.
michael@0: // You can also define this in a non-DEBUG build if you need frame dumps.
michael@0: #define DEBUG_FRAME_DUMP 1
michael@0: #endif
michael@0: 
michael@0: class nsIFrame;
michael@0: class nsIPresShell;
michael@0: class nsPresContext;
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace layout {
michael@0:   class FrameChildList;
michael@0:   enum FrameChildListID {
michael@0:       // The individual concrete child lists.
michael@0:       kPrincipalList                = 0x1,
michael@0:       kPopupList                    = 0x2,
michael@0:       kCaptionList                  = 0x4,
michael@0:       kColGroupList                 = 0x8,
michael@0:       kSelectPopupList              = 0x10,
michael@0:       kAbsoluteList                 = 0x20,
michael@0:       kFixedList                    = 0x40,
michael@0:       kOverflowList                 = 0x80,
michael@0:       kOverflowContainersList       = 0x100,
michael@0:       kExcessOverflowContainersList = 0x200,
michael@0:       kOverflowOutOfFlowList        = 0x400,
michael@0:       kFloatList                    = 0x800,
michael@0:       kBulletList                   = 0x1000,
michael@0:       kPushedFloatsList             = 0x2000,
michael@0:       // A special alias for kPrincipalList that suppress the reflow request that
michael@0:       // is normally done when manipulating child lists.
michael@0:       kNoReflowPrincipalList        = 0x4000
michael@0:   };
michael@0: }
michael@0: }
michael@0: 
michael@0: // Uncomment this to enable expensive frame-list integrity checking
michael@0: // #define DEBUG_FRAME_LIST
michael@0: 
michael@0: /**
michael@0:  * A class for managing a list of frames.
michael@0:  */
michael@0: class nsFrameList {
michael@0: public:
michael@0:   nsFrameList() :
michael@0:     mFirstChild(nullptr), mLastChild(nullptr)
michael@0:   {
michael@0:   }
michael@0: 
michael@0:   nsFrameList(nsIFrame* aFirstFrame, nsIFrame* aLastFrame) :
michael@0:     mFirstChild(aFirstFrame), mLastChild(aLastFrame)
michael@0:   {
michael@0:     VerifyList();
michael@0:   }
michael@0: 
michael@0:   nsFrameList(const nsFrameList& aOther) :
michael@0:     mFirstChild(aOther.mFirstChild), mLastChild(aOther.mLastChild)
michael@0:   {
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Allocate a nsFrameList from the shell arena.
michael@0:    */
michael@0:   void* operator new(size_t sz, nsIPresShell* aPresShell) CPP_THROW_NEW;
michael@0: 
michael@0:   /**
michael@0:    * Deallocate this list that was allocated from the shell arena.
michael@0:    * The list is required to be empty.
michael@0:    */
michael@0:   void Delete(nsIPresShell* aPresShell);
michael@0: 
michael@0:   /**
michael@0:    * For each frame in this list: remove it from the list then call
michael@0:    * Destroy() on it.
michael@0:    */
michael@0:   void DestroyFrames();
michael@0: 
michael@0:   /**
michael@0:    * For each frame in this list: remove it from the list then call
michael@0:    * DestroyFrom(aDestructRoot) on it.
michael@0:    */
michael@0:   void DestroyFramesFrom(nsIFrame* aDestructRoot);
michael@0: 
michael@0:   void Clear() { mFirstChild = mLastChild = nullptr; }
michael@0: 
michael@0:   void SetFrames(nsIFrame* aFrameList);
michael@0: 
michael@0:   void SetFrames(nsFrameList& aFrameList) {
michael@0:     NS_PRECONDITION(!mFirstChild, "Losing frames");
michael@0: 
michael@0:     mFirstChild = aFrameList.FirstChild();
michael@0:     mLastChild = aFrameList.LastChild();
michael@0:     aFrameList.Clear();
michael@0:   }
michael@0: 
michael@0:   class Slice;
michael@0: 
michael@0:   /**
michael@0:    * Append aFrameList to this list.  If aParent is not null,
michael@0:    * reparents the newly added frames.  Clears out aFrameList and
michael@0:    * returns a list slice represening the newly-appended frames.
michael@0:    */
michael@0:   Slice AppendFrames(nsIFrame* aParent, nsFrameList& aFrameList) {
michael@0:     return InsertFrames(aParent, LastChild(), aFrameList);
michael@0:   }
michael@0: 
michael@0: 
michael@0:   /**
michael@0:    * Append aFrame to this list.  If aParent is not null,
michael@0:    * reparents the newly added frame.
michael@0:    */
michael@0:   void AppendFrame(nsIFrame* aParent, nsIFrame* aFrame) {
michael@0:     nsFrameList temp(aFrame, aFrame);
michael@0:     AppendFrames(aParent, temp);
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Take aFrame out of the frame list. This also disconnects aFrame
michael@0:    * from the sibling list. The frame must be non-null and present on
michael@0:    * this list.
michael@0:    */
michael@0:   void RemoveFrame(nsIFrame* aFrame);
michael@0: 
michael@0:   /**
michael@0:    * Take the frames after aAfterFrame out of the frame list.  If
michael@0:    * aAfterFrame is null, removes the entire list.
michael@0:    * @param aAfterFrame a frame in this list, or null
michael@0:    * @return the removed frames, if any
michael@0:    */
michael@0:   nsFrameList RemoveFramesAfter(nsIFrame* aAfterFrame);
michael@0: 
michael@0:   /**
michael@0:    * Take the first frame (if any) out of the frame list.
michael@0:    * @return the first child, or nullptr if the list is empty
michael@0:    */
michael@0:   nsIFrame* RemoveFirstChild();
michael@0: 
michael@0:   /**
michael@0:    * The following two functions are intended to be used in concert for
michael@0:    * removing a frame from its frame list when the set of possible frame
michael@0:    * lists is known in advance, but the exact frame list is unknown.
michael@0:    * aFrame must be non-null.
michael@0:    * Example use:
michael@0:    *   bool removed = frameList1.StartRemoveFrame(aFrame) ||
michael@0:    *                  frameList2.ContinueRemoveFrame(aFrame) ||
michael@0:    *                  frameList3.ContinueRemoveFrame(aFrame);
michael@0:    *   MOZ_ASSERT(removed);
michael@0:    *
michael@0:    * @note One of the frame lists MUST contain aFrame, if it's on some other
michael@0:    *       frame list then the example above will likely lead to crashes.
michael@0:    * This function is O(1).
michael@0:    * @return true iff aFrame was removed from /some/ list, not necessarily
michael@0:    *         this one.  If it was removed from a different list then it is
michael@0:    *         guaranteed that that list is still non-empty.
michael@0:    * (this method is implemented in nsIFrame.h to be able to inline)
michael@0:    */
michael@0:   inline bool StartRemoveFrame(nsIFrame* aFrame);
michael@0: 
michael@0:   /**
michael@0:    * Precondition: StartRemoveFrame MUST be called before this.
michael@0:    * This function is O(1).
michael@0:    * @see StartRemoveFrame
michael@0:    * @return true iff aFrame was removed from this list
michael@0:    * (this method is implemented in nsIFrame.h to be able to inline)
michael@0:    */
michael@0:   inline bool ContinueRemoveFrame(nsIFrame* aFrame);
michael@0: 
michael@0:   /**
michael@0:    * Take aFrame out of the frame list and then destroy it.
michael@0:    * The frame must be non-null and present on this list.
michael@0:    */
michael@0:   void DestroyFrame(nsIFrame* aFrame);
michael@0: 
michael@0:   /**
michael@0:    * Insert aFrame right after aPrevSibling, or prepend it to this
michael@0:    * list if aPrevSibling is null. If aParent is not null, also
michael@0:    * reparents newly-added frame. Note that this method always
michael@0:    * sets the frame's nextSibling pointer.
michael@0:    */
michael@0:   void InsertFrame(nsIFrame* aParent, nsIFrame* aPrevSibling,
michael@0:                    nsIFrame* aFrame) {
michael@0:     nsFrameList temp(aFrame, aFrame);
michael@0:     InsertFrames(aParent, aPrevSibling, temp);
michael@0:   }
michael@0: 
michael@0: 
michael@0:   /**
michael@0:    * Inserts aFrameList into this list after aPrevSibling (at the beginning if
michael@0:    * aPrevSibling is null).  If aParent is not null, reparents the newly added
michael@0:    * frames.  Clears out aFrameList and returns a list slice representing the
michael@0:    * newly-inserted frames.
michael@0:    */
michael@0:   Slice InsertFrames(nsIFrame* aParent, nsIFrame* aPrevSibling,
michael@0:                      nsFrameList& aFrameList);
michael@0: 
michael@0:   class FrameLinkEnumerator;
michael@0: 
michael@0:   /**
michael@0:    * Split this frame list such that all the frames before the link pointed to
michael@0:    * by aLink end up in the returned list, while the remaining frames stay in
michael@0:    * this list.  After this call, aLink points to the beginning of this list.
michael@0:    */
michael@0:   nsFrameList ExtractHead(FrameLinkEnumerator& aLink);
michael@0: 
michael@0:   /**
michael@0:    * Split this frame list such that all the frames coming after the link
michael@0:    * pointed to by aLink end up in the returned list, while the frames before
michael@0:    * that link stay in this list.  After this call, aLink is at end.
michael@0:    */
michael@0:   nsFrameList ExtractTail(FrameLinkEnumerator& aLink);
michael@0: 
michael@0:   nsIFrame* FirstChild() const {
michael@0:     return mFirstChild;
michael@0:   }
michael@0: 
michael@0:   nsIFrame* LastChild() const {
michael@0:     return mLastChild;
michael@0:   }
michael@0: 
michael@0:   nsIFrame* FrameAt(int32_t aIndex) const;
michael@0:   int32_t IndexOf(nsIFrame* aFrame) const;
michael@0: 
michael@0:   bool IsEmpty() const {
michael@0:     return nullptr == mFirstChild;
michael@0:   }
michael@0: 
michael@0:   bool NotEmpty() const {
michael@0:     return nullptr != mFirstChild;
michael@0:   }
michael@0: 
michael@0:   bool ContainsFrame(const nsIFrame* aFrame) const;
michael@0: 
michael@0:   int32_t GetLength() const;
michael@0: 
michael@0:   /**
michael@0:    * If this frame list has only one frame, return that frame.
michael@0:    * Otherwise, return null.
michael@0:    */
michael@0:   nsIFrame* OnlyChild() const {
michael@0:     if (FirstChild() == LastChild()) {
michael@0:       return FirstChild();
michael@0:     }
michael@0:     return nullptr;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Call SetParent(aParent) for each frame in this list.
michael@0:    * @param aParent the new parent frame, must be non-null
michael@0:    */
michael@0:   void ApplySetParent(nsIFrame* aParent) const;
michael@0: 
michael@0:   /**
michael@0:    * If this frame list is non-empty then append it to aLists as the
michael@0:    * aListID child list.
michael@0:    * (this method is implemented in FrameChildList.h for dependency reasons)
michael@0:    */
michael@0:   inline void AppendIfNonempty(nsTArray<mozilla::layout::FrameChildList>* aLists,
michael@0:                                mozilla::layout::FrameChildListID aListID) const;
michael@0: 
michael@0:   /**
michael@0:    * Return the frame before this frame in visual order (after Bidi reordering).
michael@0:    * If aFrame is null, return the last frame in visual order.
michael@0:    */
michael@0:   nsIFrame* GetPrevVisualFor(nsIFrame* aFrame) const;
michael@0: 
michael@0:   /**
michael@0:    * Return the frame after this frame in visual order (after Bidi reordering).
michael@0:    * If aFrame is null, return the first frame in visual order.
michael@0:    */
michael@0:   nsIFrame* GetNextVisualFor(nsIFrame* aFrame) const;
michael@0: 
michael@0: #ifdef DEBUG_FRAME_DUMP
michael@0:   void List(FILE* out) const;
michael@0: #endif
michael@0: 
michael@0:   static inline const nsFrameList& EmptyList();
michael@0: 
michael@0:   class Enumerator;
michael@0: 
michael@0:   /**
michael@0:    * A class representing a slice of a frame list.
michael@0:    */
michael@0:   class Slice {
michael@0:     friend class Enumerator;
michael@0: 
michael@0:   public:
michael@0:     // Implicit on purpose, so that we can easily create enumerators from
michael@0:     // nsFrameList via this impicit constructor.
michael@0:     Slice(const nsFrameList& aList) :
michael@0: #ifdef DEBUG
michael@0:       mList(aList),
michael@0: #endif
michael@0:       mStart(aList.FirstChild()),
michael@0:       mEnd(nullptr)
michael@0:     {}
michael@0: 
michael@0:     Slice(const nsFrameList& aList, nsIFrame* aStart, nsIFrame* aEnd) :
michael@0: #ifdef DEBUG
michael@0:       mList(aList),
michael@0: #endif
michael@0:       mStart(aStart),
michael@0:       mEnd(aEnd)
michael@0:     {}
michael@0: 
michael@0:     Slice(const Slice& aOther) :
michael@0: #ifdef DEBUG
michael@0:       mList(aOther.mList),
michael@0: #endif
michael@0:       mStart(aOther.mStart),
michael@0:       mEnd(aOther.mEnd)
michael@0:     {}
michael@0: 
michael@0:   private:
michael@0: #ifdef DEBUG
michael@0:     const nsFrameList& mList;
michael@0: #endif
michael@0:     nsIFrame* const mStart; // our starting frame
michael@0:     const nsIFrame* const mEnd; // The first frame that is NOT in the slice.
michael@0:                                 // May be null.
michael@0:   };
michael@0: 
michael@0:   class Enumerator {
michael@0:   public:
michael@0:     Enumerator(const Slice& aSlice) :
michael@0: #ifdef DEBUG
michael@0:       mSlice(aSlice),
michael@0: #endif
michael@0:       mFrame(aSlice.mStart),
michael@0:       mEnd(aSlice.mEnd)
michael@0:     {}
michael@0: 
michael@0:     Enumerator(const Enumerator& aOther) :
michael@0: #ifdef DEBUG
michael@0:       mSlice(aOther.mSlice),
michael@0: #endif
michael@0:       mFrame(aOther.mFrame),
michael@0:       mEnd(aOther.mEnd)
michael@0:     {}
michael@0: 
michael@0:     bool AtEnd() const {
michael@0:       // Can't just check mEnd, because some table code goes and destroys the
michael@0:       // tail of the frame list (including mEnd!) while iterating over the
michael@0:       // frame list.
michael@0:       return !mFrame || mFrame == mEnd;
michael@0:     }
michael@0: 
michael@0:     /* Next() needs to know about nsIFrame, and nsIFrame will need to
michael@0:        know about nsFrameList methods, so in order to inline this put
michael@0:        the implementation in nsIFrame.h */
michael@0:     inline void Next();
michael@0: 
michael@0:     /**
michael@0:      * Get the current frame we're pointing to.  Do not call this on an
michael@0:      * iterator that is at end!
michael@0:      */
michael@0:     nsIFrame* get() const {
michael@0:       NS_PRECONDITION(!AtEnd(), "Enumerator is at end");
michael@0:       return mFrame;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Get an enumerator that is just like this one, but not limited in terms of
michael@0:      * the part of the list it will traverse.
michael@0:      */
michael@0:     Enumerator GetUnlimitedEnumerator() const {
michael@0:       return Enumerator(*this, nullptr);
michael@0:     }
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     const nsFrameList& List() const { return mSlice.mList; }
michael@0: #endif
michael@0: 
michael@0:   protected:
michael@0:     Enumerator(const Enumerator& aOther, const nsIFrame* const aNewEnd):
michael@0: #ifdef DEBUG
michael@0:       mSlice(aOther.mSlice),
michael@0: #endif
michael@0:       mFrame(aOther.mFrame),
michael@0:       mEnd(aNewEnd)
michael@0:     {}
michael@0: 
michael@0: #ifdef DEBUG
michael@0:     /* Has to be an object, not a reference, since the slice could
michael@0:        well be a temporary constructed from an nsFrameList */
michael@0:     const Slice mSlice;
michael@0: #endif
michael@0:     nsIFrame* mFrame; // our current frame.
michael@0:     const nsIFrame* const mEnd; // The first frame we should NOT enumerate.
michael@0:                                 // May be null.
michael@0:   };
michael@0: 
michael@0:   /**
michael@0:    * A class that can be used to enumerate links between frames.  When created
michael@0:    * from an nsFrameList, it points to the "link" immediately before the first
michael@0:    * frame.  It can then be advanced until it points to the "link" immediately
michael@0:    * after the last frame.  At any position, PrevFrame() and NextFrame() are
michael@0:    * the frames before and after the given link.  This means PrevFrame() is
michael@0:    * null when the enumerator is at the beginning of the list and NextFrame()
michael@0:    * is null when it's AtEnd().
michael@0:    */
michael@0:   class FrameLinkEnumerator : private Enumerator {
michael@0:   public:
michael@0:     friend class nsFrameList;
michael@0: 
michael@0:     FrameLinkEnumerator(const nsFrameList& aList) :
michael@0:       Enumerator(aList),
michael@0:       mPrev(nullptr)
michael@0:     {}
michael@0: 
michael@0:     FrameLinkEnumerator(const FrameLinkEnumerator& aOther) :
michael@0:       Enumerator(aOther),
michael@0:       mPrev(aOther.mPrev)
michael@0:     {}
michael@0: 
michael@0:     /* This constructor needs to know about nsIFrame, and nsIFrame will need to
michael@0:        know about nsFrameList methods, so in order to inline this put
michael@0:        the implementation in nsIFrame.h */
michael@0:     inline FrameLinkEnumerator(const nsFrameList& aList, nsIFrame* aPrevFrame);
michael@0: 
michael@0:     void operator=(const FrameLinkEnumerator& aOther) {
michael@0:       NS_PRECONDITION(&List() == &aOther.List(), "Different lists?");
michael@0:       mFrame = aOther.mFrame;
michael@0:       mPrev = aOther.mPrev;
michael@0:     }
michael@0: 
michael@0:     inline void Next();
michael@0: 
michael@0:     bool AtEnd() const { return Enumerator::AtEnd(); }
michael@0: 
michael@0:     nsIFrame* PrevFrame() const { return mPrev; }
michael@0:     nsIFrame* NextFrame() const { return mFrame; }
michael@0: 
michael@0:   protected:
michael@0:     nsIFrame* mPrev;
michael@0:   };
michael@0: 
michael@0: private:
michael@0:   void operator delete(void*) MOZ_DELETE;
michael@0: 
michael@0: #ifdef DEBUG_FRAME_LIST
michael@0:   void VerifyList() const;
michael@0: #else
michael@0:   void VerifyList() const {}
michael@0: #endif
michael@0: 
michael@0: protected:
michael@0:   /**
michael@0:    * Disconnect aFrame from its siblings.  This must only be called if aFrame
michael@0:    * is NOT the first or last sibling, because otherwise its nsFrameList will
michael@0:    * have a stale mFirst/LastChild pointer.  This precondition is asserted.
michael@0:    * This function is O(1).
michael@0:    */
michael@0:   static void UnhookFrameFromSiblings(nsIFrame* aFrame);
michael@0: 
michael@0:   nsIFrame* mFirstChild;
michael@0:   nsIFrame* mLastChild;
michael@0: };
michael@0: 
michael@0: namespace mozilla {
michael@0: namespace layout {
michael@0: 
michael@0: /**
michael@0:  * Simple "auto_ptr" for nsFrameLists allocated from the shell arena.
michael@0:  * The frame list given to the constructor will be deallocated (if non-null)
michael@0:  * in the destructor.  The frame list must then be empty.
michael@0:  */
michael@0: class AutoFrameListPtr {
michael@0: public:
michael@0:   AutoFrameListPtr(nsPresContext* aPresContext, nsFrameList* aFrameList)
michael@0:     : mPresContext(aPresContext), mFrameList(aFrameList) {}
michael@0:   ~AutoFrameListPtr();
michael@0:   operator nsFrameList*() const { return mFrameList; }
michael@0:   nsFrameList* operator->() const { return mFrameList; }
michael@0: private:
michael@0:   nsPresContext* mPresContext;
michael@0:   nsFrameList* mFrameList;
michael@0: };
michael@0: 
michael@0: namespace detail {
michael@0: union AlignedFrameListBytes {
michael@0:   void* ptr;
michael@0:   char bytes[sizeof(nsFrameList)];
michael@0: };
michael@0: extern const AlignedFrameListBytes gEmptyFrameListBytes;
michael@0: }
michael@0: }
michael@0: }
michael@0: 
michael@0: /* static */ inline const nsFrameList&
michael@0: nsFrameList::EmptyList()
michael@0: {
michael@0:   return *reinterpret_cast<const nsFrameList*>(&mozilla::layout::detail::gEmptyFrameListBytes);
michael@0: }
michael@0: 
michael@0: #endif /* nsFrameList_h___ */