summaryrefslogtreecommitdiffstats
path: root/layout/generic/nsFrameList.h
diff options
context:
space:
mode:
Diffstat (limited to 'layout/generic/nsFrameList.h')
-rw-r--r--layout/generic/nsFrameList.h496
1 files changed, 496 insertions, 0 deletions
diff --git a/layout/generic/nsFrameList.h b/layout/generic/nsFrameList.h
new file mode 100644
index 0000000000..9b31455cae
--- /dev/null
+++ b/layout/generic/nsFrameList.h
@@ -0,0 +1,496 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#ifndef nsFrameList_h___
+#define nsFrameList_h___
+
+#include <stdio.h> /* for FILE* */
+#include "nsDebug.h"
+#include "nsTArray.h"
+#include "mozilla/EnumSet.h"
+#include "mozilla/FunctionTypeTraits.h"
+#include "mozilla/RefPtr.h"
+
+#if defined(DEBUG) || defined(MOZ_DUMP_PAINTING) || defined(MOZ_LAYOUT_DEBUGGER)
+// DEBUG_FRAME_DUMP enables nsIFrame::List and related methods.
+// You can also define this in a non-DEBUG build if you need frame dumps.
+# define DEBUG_FRAME_DUMP 1
+#endif
+
+class nsContainerFrame;
+class nsIContent;
+class nsIFrame;
+class nsPresContext;
+
+namespace mozilla {
+
+struct FrameDestroyContext;
+
+class PresShell;
+class FrameChildList;
+enum class FrameChildListID {
+ // The individual concrete child lists.
+ Principal,
+ Popup,
+ Caption,
+ ColGroup,
+ Absolute,
+ Fixed,
+ Overflow,
+ OverflowContainers,
+ ExcessOverflowContainers,
+ OverflowOutOfFlow,
+ Float,
+ Bullet,
+ PushedFloats,
+ Backdrop,
+ // A special alias for FrameChildListID::Principal that suppress the reflow
+ // request that is normally done when manipulating child lists.
+ NoReflowPrincipal,
+};
+
+} // namespace mozilla
+
+// Uncomment this to enable expensive frame-list integrity checking
+// #define DEBUG_FRAME_LIST
+
+/**
+ * A class for managing a list of frames.
+ */
+class nsFrameList {
+ // Next()/Prev() need to know about nsIFrame. To make them inline, their
+ // implementations are in nsIFrame.h.
+ struct ForwardFrameTraversal final {
+ static inline nsIFrame* Next(nsIFrame*);
+ static inline nsIFrame* Prev(nsIFrame*);
+ };
+ struct BackwardFrameTraversal final {
+ static inline nsIFrame* Next(nsIFrame*);
+ static inline nsIFrame* Prev(nsIFrame*);
+ };
+
+ public:
+ template <typename FrameTraversal>
+ class Iterator;
+ class Slice;
+
+ using iterator = Iterator<ForwardFrameTraversal>;
+ using const_iterator = Iterator<ForwardFrameTraversal>;
+ using reverse_iterator = Iterator<BackwardFrameTraversal>;
+ using const_reverse_iterator = Iterator<BackwardFrameTraversal>;
+
+ nsFrameList() : mFirstChild(nullptr), mLastChild(nullptr) {}
+
+ nsFrameList(nsIFrame* aFirstFrame, nsIFrame* aLastFrame)
+ : mFirstChild(aFirstFrame), mLastChild(aLastFrame) {
+ VerifyList();
+ }
+
+ // nsFrameList is a move-only class by default. Use Clone() if you really want
+ // a copy of this list.
+ nsFrameList(const nsFrameList& aOther) = delete;
+ nsFrameList& operator=(const nsFrameList& aOther) = delete;
+ nsFrameList Clone() const { return nsFrameList(mFirstChild, mLastChild); }
+
+ /**
+ * Transfer frames in aOther to this list. aOther becomes empty after this
+ * operation.
+ */
+ nsFrameList(nsFrameList&& aOther)
+ : mFirstChild(aOther.mFirstChild), mLastChild(aOther.mLastChild) {
+ aOther.Clear();
+ VerifyList();
+ }
+ nsFrameList& operator=(nsFrameList&& aOther) {
+ if (this != &aOther) {
+ MOZ_ASSERT(IsEmpty(), "Assigning to a non-empty list will lose frames!");
+ mFirstChild = aOther.FirstChild();
+ mLastChild = aOther.LastChild();
+ aOther.Clear();
+ }
+ return *this;
+ }
+
+ /**
+ * Infallibly allocate a nsFrameList from the shell arena.
+ */
+ void* operator new(size_t sz, mozilla::PresShell* aPresShell);
+
+ /**
+ * Deallocate this list that was allocated from the shell arena.
+ * The list is required to be empty.
+ */
+ void Delete(mozilla::PresShell* aPresShell);
+
+ /**
+ * For each frame in this list: remove it from the list then call
+ * Destroy() on it with the passed context as an argument.
+ */
+ void DestroyFrames(mozilla::FrameDestroyContext&);
+
+ void Clear() { mFirstChild = mLastChild = nullptr; }
+
+ /**
+ * Append aFrameList to this list. If aParent is not null,
+ * reparents the newly added frames. Clears out aFrameList and
+ * returns a list slice represening the newly-appended frames.
+ */
+ Slice AppendFrames(nsContainerFrame* aParent, nsFrameList&& aFrameList) {
+ return InsertFrames(aParent, LastChild(), std::move(aFrameList));
+ }
+
+ /**
+ * Append aFrame to this list. If aParent is not null,
+ * reparents the newly added frame.
+ */
+ void AppendFrame(nsContainerFrame* aParent, nsIFrame* aFrame) {
+ AppendFrames(aParent, nsFrameList(aFrame, aFrame));
+ }
+
+ /**
+ * Take aFrame out of the frame list. This also disconnects aFrame
+ * from the sibling list. The frame must be non-null and present on
+ * this list.
+ */
+ void RemoveFrame(nsIFrame* aFrame);
+
+ /**
+ * Take all the frames before aFrame out of the frame list; aFrame and all the
+ * frames after it stay in this list. If aFrame is nullptr, remove the entire
+ * frame list.
+ * @param aFrame a frame in this frame list, or nullptr.
+ * @return the removed frames, if any.
+ */
+ [[nodiscard]] nsFrameList TakeFramesBefore(nsIFrame* aFrame);
+
+ /**
+ * Take all the frames after aFrame out of the frame list; aFrame and all the
+ * frames before it stay in this list. If aFrame is nullptr, removes the
+ * entire list.
+ * @param aFrame a frame in this list, or nullptr.
+ * @return the removed frames, if any.
+ */
+ [[nodiscard]] nsFrameList TakeFramesAfter(nsIFrame* aFrame);
+
+ /**
+ * Take the first frame (if any) out of the frame list.
+ * @return the first child, or nullptr if the list is empty
+ */
+ nsIFrame* RemoveFirstChild();
+
+ /**
+ * The following two functions are intended to be used in concert for
+ * removing a frame from its frame list when the set of possible frame
+ * lists is known in advance, but the exact frame list is unknown.
+ * aFrame must be non-null.
+ * Example use:
+ * bool removed = frameList1.StartRemoveFrame(aFrame) ||
+ * frameList2.ContinueRemoveFrame(aFrame) ||
+ * frameList3.ContinueRemoveFrame(aFrame);
+ * MOZ_ASSERT(removed);
+ *
+ * @note One of the frame lists MUST contain aFrame, if it's on some other
+ * frame list then the example above will likely lead to crashes.
+ * This function is O(1).
+ * @return true iff aFrame was removed from /some/ list, not necessarily
+ * this one. If it was removed from a different list then it is
+ * guaranteed that that list is still non-empty.
+ * (this method is implemented in nsIFrame.h to be able to inline)
+ */
+ inline bool StartRemoveFrame(nsIFrame* aFrame);
+
+ /**
+ * Precondition: StartRemoveFrame MUST be called before this.
+ * This function is O(1).
+ * @see StartRemoveFrame
+ * @return true iff aFrame was removed from this list
+ * (this method is implemented in nsIFrame.h to be able to inline)
+ */
+ inline bool ContinueRemoveFrame(nsIFrame* aFrame);
+
+ /**
+ * Take a frame out of the frame list and then destroy it.
+ * The frame must be non-null and present on this list.
+ */
+ void DestroyFrame(mozilla::FrameDestroyContext&, nsIFrame*);
+
+ /**
+ * Insert aFrame right after aPrevSibling, or prepend it to this
+ * list if aPrevSibling is null. If aParent is not null, also
+ * reparents newly-added frame. Note that this method always
+ * sets the frame's nextSibling pointer.
+ */
+ void InsertFrame(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
+ nsIFrame* aFrame) {
+ InsertFrames(aParent, aPrevSibling, nsFrameList(aFrame, aFrame));
+ }
+
+ /**
+ * Inserts aFrameList into this list after aPrevSibling (at the beginning if
+ * aPrevSibling is null). If aParent is not null, reparents the newly added
+ * frames. Clears out aFrameList and returns a list slice representing the
+ * newly-inserted frames.
+ */
+ Slice InsertFrames(nsContainerFrame* aParent, nsIFrame* aPrevSibling,
+ nsFrameList&& aFrameList);
+
+ /**
+ * Split this list just before the first frame that matches aPredicate,
+ * and return a nsFrameList containing all the frames before it. The
+ * matched frame and all frames after it stay in this list. If no matched
+ * frame exists, all the frames are drained into the returned list, and
+ * this list ends up empty.
+ *
+ * aPredicate should be of this function signature: bool(nsIFrame*).
+ */
+ template <typename Predicate>
+ nsFrameList Split(Predicate&& aPredicate) {
+ static_assert(
+ std::is_same<
+ typename mozilla::FunctionTypeTraits<Predicate>::ReturnType,
+ bool>::value &&
+ mozilla::FunctionTypeTraits<Predicate>::arity == 1 &&
+ std::is_same<typename mozilla::FunctionTypeTraits<
+ Predicate>::template ParameterType<0>,
+ nsIFrame*>::value,
+ "aPredicate should be of this function signature: bool(nsIFrame*)");
+
+ for (nsIFrame* f : *this) {
+ if (aPredicate(f)) {
+ return TakeFramesBefore(f);
+ }
+ }
+ return std::move(*this);
+ }
+
+ nsIFrame* FirstChild() const { return mFirstChild; }
+
+ nsIFrame* LastChild() const { return mLastChild; }
+
+ nsIFrame* FrameAt(int32_t aIndex) const;
+ int32_t IndexOf(nsIFrame* aFrame) const;
+
+ bool IsEmpty() const { return nullptr == mFirstChild; }
+
+ bool NotEmpty() const { return nullptr != mFirstChild; }
+
+ /**
+ * Return true if aFrame is on this list.
+ * @note this method has O(n) time complexity over the length of the list
+ * XXXmats: ideally, we should make this function #ifdef DEBUG
+ */
+ bool ContainsFrame(const nsIFrame* aFrame) const;
+
+ /**
+ * Get the number of frames in this list. Note that currently the
+ * implementation has O(n) time complexity. Do not call it repeatedly in hot
+ * code.
+ * XXXmats: ideally, we should make this function #ifdef DEBUG
+ */
+ int32_t GetLength() const;
+
+ /**
+ * If this frame list has only one frame, return that frame.
+ * Otherwise, return null.
+ */
+ nsIFrame* OnlyChild() const {
+ if (FirstChild() == LastChild()) {
+ return FirstChild();
+ }
+ return nullptr;
+ }
+
+ /**
+ * Call SetParent(aParent) for each frame in this list.
+ * @param aParent the new parent frame, must be non-null
+ */
+ void ApplySetParent(nsContainerFrame* aParent) const;
+
+ /**
+ * If this frame list is non-empty then append it to aLists as the
+ * aListID child list.
+ */
+ inline void AppendIfNonempty(nsTArray<mozilla::FrameChildList>* aLists,
+ mozilla::FrameChildListID aListID) const {
+ if (NotEmpty()) {
+ aLists->EmplaceBack(*this, aListID);
+ }
+ }
+
+ /**
+ * Return the frame before this frame in visual order (after Bidi reordering).
+ * If aFrame is null, return the last frame in visual order.
+ */
+ nsIFrame* GetPrevVisualFor(nsIFrame* aFrame) const;
+
+ /**
+ * Return the frame after this frame in visual order (after Bidi reordering).
+ * If aFrame is null, return the first frame in visual order.
+ */
+ nsIFrame* GetNextVisualFor(nsIFrame* aFrame) const;
+
+#ifdef DEBUG_FRAME_DUMP
+ void List(FILE* out) const;
+#endif
+
+ static inline const nsFrameList& EmptyList();
+
+ /**
+ * A class representing a slice of a frame list.
+ */
+ class Slice {
+ public:
+ // Implicit on purpose, so that we can easily create Slice from nsFrameList
+ // via this impicit constructor.
+ MOZ_IMPLICIT Slice(const nsFrameList& aList)
+ : mStart(aList.FirstChild()), mEnd(nullptr) {}
+ Slice(nsIFrame* aStart, nsIFrame* aEnd) : mStart(aStart), mEnd(aEnd) {}
+
+ iterator begin() const { return iterator(mStart); }
+ const_iterator cbegin() const { return begin(); }
+ iterator end() const { return iterator(mEnd); }
+ const_iterator cend() const { return end(); }
+
+ private:
+ // Our starting frame.
+ nsIFrame* const mStart;
+
+ // The first frame that is NOT in the slice. May be null.
+ nsIFrame* const mEnd;
+ };
+
+ template <typename FrameTraversal>
+ class Iterator final {
+ public:
+ // It is disputable whether these type definitions are correct, since
+ // operator* doesn't return a reference at all. Also, the iterator_category
+ // can be at most std::input_iterator_tag (rather than
+ // std::bidrectional_iterator_tag, as it might seem), because it is a
+ // stashing iterator. See also, e.g.,
+ // https://stackoverflow.com/questions/50909701/what-should-be-iterator-category-for-a-stashing-iterator
+ using value_type = nsIFrame* const;
+ using pointer = value_type*;
+ using reference = value_type&;
+ using difference_type = ptrdiff_t;
+ using iterator_category = std::input_iterator_tag;
+
+ explicit constexpr Iterator(nsIFrame* aCurrent) : mCurrent(aCurrent) {}
+
+ nsIFrame* operator*() const { return mCurrent; }
+
+ Iterator& operator++() {
+ mCurrent = FrameTraversal::Next(mCurrent);
+ return *this;
+ }
+ Iterator& operator--() {
+ mCurrent = FrameTraversal::Prev(mCurrent);
+ return *this;
+ }
+
+ Iterator operator++(int) {
+ auto ret = *this;
+ ++*this;
+ return ret;
+ }
+ Iterator operator--(int) {
+ auto ret = *this;
+ --*this;
+ return ret;
+ }
+
+ bool operator==(const Iterator<FrameTraversal>& aOther) const {
+ return mCurrent == aOther.mCurrent;
+ }
+
+ bool operator!=(const Iterator<FrameTraversal>& aOther) const {
+ return !(*this == aOther);
+ }
+
+ private:
+ nsIFrame* mCurrent;
+ };
+
+ iterator begin() const { return iterator(mFirstChild); }
+ const_iterator cbegin() const { return begin(); }
+ iterator end() const { return iterator(nullptr); }
+ const_iterator cend() const { return end(); }
+ reverse_iterator rbegin() const { return reverse_iterator(mLastChild); }
+ const_reverse_iterator crbegin() const { return rbegin(); }
+ reverse_iterator rend() const { return reverse_iterator(nullptr); }
+ const_reverse_iterator crend() const { return rend(); }
+
+ private:
+ void operator delete(void*) = delete;
+
+#ifdef DEBUG_FRAME_LIST
+ void VerifyList() const;
+#else
+ void VerifyList() const {}
+#endif
+
+ protected:
+ /**
+ * Disconnect aFrame from its siblings. This must only be called if aFrame
+ * is NOT the first or last sibling, because otherwise its nsFrameList will
+ * have a stale mFirst/LastChild pointer. This precondition is asserted.
+ * This function is O(1).
+ */
+ static void UnhookFrameFromSiblings(nsIFrame* aFrame);
+
+ nsIFrame* mFirstChild;
+ nsIFrame* mLastChild;
+};
+
+namespace mozilla {
+
+#ifdef DEBUG_FRAME_DUMP
+extern const char* ChildListName(FrameChildListID aListID);
+#endif
+
+using FrameChildListIDs = EnumSet<FrameChildListID>;
+
+class FrameChildList {
+ public:
+ FrameChildList(const nsFrameList& aList, FrameChildListID aID)
+ : mList(aList.Clone()), mID(aID) {}
+ nsFrameList mList;
+ FrameChildListID mID;
+};
+
+/**
+ * Simple "auto_ptr" for nsFrameLists allocated from the shell arena.
+ * The frame list given to the constructor will be deallocated (if non-null)
+ * in the destructor. The frame list must then be empty.
+ */
+class MOZ_RAII AutoFrameListPtr final {
+ public:
+ AutoFrameListPtr(nsPresContext* aPresContext, nsFrameList* aFrameList)
+ : mPresContext(aPresContext), mFrameList(aFrameList) {}
+ ~AutoFrameListPtr();
+ operator nsFrameList*() const { return mFrameList; }
+ nsFrameList* operator->() const { return mFrameList; }
+
+ private:
+ nsPresContext* mPresContext;
+ nsFrameList* mFrameList;
+};
+
+namespace detail {
+union AlignedFrameListBytes {
+ void* ptr;
+ char bytes[sizeof(nsFrameList)];
+};
+extern const AlignedFrameListBytes gEmptyFrameListBytes;
+} // namespace detail
+
+} // namespace mozilla
+
+/* static */ inline const nsFrameList& nsFrameList::EmptyList() {
+ return *reinterpret_cast<const nsFrameList*>(
+ &mozilla::detail::gEmptyFrameListBytes);
+}
+
+#endif /* nsFrameList_h___ */