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___ */