layout/painting/RetainedDisplayListHelpers.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 RETAINEDDISPLAYLISTHELPERS_H_
   8 #define RETAINEDDISPLAYLISTHELPERS_H_
   9
  10 #include "mozilla/Span.h"
  11 #include "PLDHashTable.h"
  12
  13 class nsIFrame;
  14
  15 namespace mozilla {
  16
  17 struct DisplayItemKey {
  18   bool operator==(const DisplayItemKey& aOther) const {
  19     return mFrame == aOther.mFrame && mPerFrameKey == aOther.mPerFrameKey;
  20   }
  21
  22   nsIFrame* mFrame;
  23   uint32_t mPerFrameKey;
  24 };
  25
  26 class DisplayItemHashEntry : public PLDHashEntryHdr {
  27  public:
  28   typedef DisplayItemKey KeyType;
  29   typedef const DisplayItemKey* KeyTypePointer;
  30
  31   explicit DisplayItemHashEntry(KeyTypePointer aKey) : mKey(*aKey) {}
  32   DisplayItemHashEntry(DisplayItemHashEntry&&) = default;
  33
  34   ~DisplayItemHashEntry() = default;
  35
  36   KeyType GetKey() const { return mKey; }
  37   bool KeyEquals(KeyTypePointer aKey) const { return mKey == *aKey; }
  38
  39   static KeyTypePointer KeyToPointer(KeyType& aKey) { return &aKey; }
  40   static PLDHashNumber HashKey(KeyTypePointer aKey) {
  41     if (!aKey) {
  42       return 0;
  43     }
  44
  45     return mozilla::HashGeneric(aKey->mFrame, aKey->mPerFrameKey);
  46   }
  47   enum { ALLOW_MEMMOVE = true };
  48
  49   DisplayItemKey mKey;
  50 };
  51
  52 template <typename T>
  53 bool SpanContains(mozilla::Span<const T>& aSpan, T aItem) {
  54   for (const T& i : aSpan) {
  55     if (i == aItem) {
  56       return true;
  57     }
  58   }
  59   return false;
  60 }
  61
  62 class OldListUnits {};
  63 class MergedListUnits {};
  64
  65 template <typename Units>
  66 struct Index {
  67   Index() : val(0) {}
  68   explicit Index(size_t aVal) : val(aVal) {
  69     MOZ_RELEASE_ASSERT(aVal < std::numeric_limits<uint32_t>::max(),
  70                        "List index overflowed");
  71   }
  72
  73   bool operator==(const Index<Units>& aOther) const {
  74     return val == aOther.val;
  75   }
  76
  77   uint32_t val;
  78 };
  79 typedef Index<OldListUnits> OldListIndex;
  80 typedef Index<MergedListUnits> MergedListIndex;
  81
  82 template <typename T>
  83 class DirectedAcyclicGraph {
  84  public:
  85   DirectedAcyclicGraph() = default;
  86   DirectedAcyclicGraph(DirectedAcyclicGraph&& aOther)
  87       : mNodesInfo(std::move(aOther.mNodesInfo)),
  88         mDirectPredecessorList(std::move(aOther.mDirectPredecessorList)) {}
  89
  90   DirectedAcyclicGraph& operator=(DirectedAcyclicGraph&& aOther) {
  91     mNodesInfo = std::move(aOther.mNodesInfo);
  92     mDirectPredecessorList = std::move(aOther.mDirectPredecessorList);
  93     return *this;
  94   }
  95
  96   Index<T> AddNode(
  97       mozilla::Span<const Index<T>> aDirectPredecessors,
  98       const mozilla::Maybe<Index<T>>& aExtraPredecessor = mozilla::Nothing()) {
  99     size_t index = mNodesInfo.Length();
 100     mNodesInfo.AppendElement(NodeInfo(mDirectPredecessorList.Length(),
 101                                       aDirectPredecessors.Length()));
 102     if (aExtraPredecessor &&
 103         !SpanContains(aDirectPredecessors, aExtraPredecessor.value())) {
 104       mNodesInfo.LastElement().mDirectPredecessorCount++;
 105       mDirectPredecessorList.SetCapacity(mDirectPredecessorList.Length() +
 106                                          aDirectPredecessors.Length() + 1);
 107       mDirectPredecessorList.AppendElements(aDirectPredecessors);
 108       mDirectPredecessorList.AppendElement(aExtraPredecessor.value());
 109     } else {
 110       mDirectPredecessorList.AppendElements(aDirectPredecessors);
 111     }
 112     return Index<T>(index);
 113   }
 114
 115   size_t Length() { return mNodesInfo.Length(); }
 116
 117   mozilla::Span<Index<T>> GetDirectPredecessors(Index<T> aNodeIndex) {
 118     NodeInfo& node = mNodesInfo[aNodeIndex.val];
 119     const auto span = mozilla::Span{mDirectPredecessorList};
 120     return span.Subspan(node.mIndexInDirectPredecessorList,
 121                         node.mDirectPredecessorCount);
 122   }
 123
 124   template <typename OtherUnits>
 125   void EnsureCapacityFor(const DirectedAcyclicGraph<OtherUnits>& aOther) {
 126     mNodesInfo.SetCapacity(aOther.mNodesInfo.Length());
 127     mDirectPredecessorList.SetCapacity(aOther.mDirectPredecessorList.Length());
 128   }
 129
 130   void Clear() {
 131     mNodesInfo.Clear();
 132     mDirectPredecessorList.Clear();
 133   }
 134
 135   struct NodeInfo {
 136     NodeInfo(size_t aIndexInDirectPredecessorList,
 137              size_t aDirectPredecessorCount)
 138         : mIndexInDirectPredecessorList(aIndexInDirectPredecessorList),
 139           mDirectPredecessorCount(aDirectPredecessorCount) {}
 140     size_t mIndexInDirectPredecessorList;
 141     size_t mDirectPredecessorCount;
 142   };
 143
 144   nsTArray<NodeInfo> mNodesInfo;
 145   nsTArray<Index<T>> mDirectPredecessorList;
 146 };
 147
 148 class RetainedDisplayListBuilder;
 149 class nsDisplayItem;
 150
 151 struct OldItemInfo {
 152   explicit OldItemInfo(nsDisplayItem* aItem);
 153
 154   void AddedToMergedList(MergedListIndex aIndex) {
 155     MOZ_ASSERT(!IsUsed());
 156     mUsed = true;
 157     mIndex = aIndex;
 158     mItem = nullptr;
 159   }
 160
 161   void AddedMatchToMergedList(RetainedDisplayListBuilder* aBuilder,
 162                               MergedListIndex aIndex);
 163   void Discard(RetainedDisplayListBuilder* aBuilder,
 164                nsTArray<MergedListIndex>&& aDirectPredecessors);
 165   bool IsUsed() { return mUsed; }
 166
 167   bool IsDiscarded() {
 168     MOZ_ASSERT(IsUsed());
 169     return mDiscarded;
 170   }
 171
 172   bool IsChanged();
 173
 174   nsDisplayItem* mItem;
 175   nsTArray<MergedListIndex> mDirectPredecessors;
 176   MergedListIndex mIndex;
 177   bool mUsed;
 178   bool mDiscarded;
 179   bool mOwnsItem;
 180 };
 181
 182 bool AnyContentAncestorModified(nsIFrame* aFrame,
 183                                 nsIFrame* aStopAtFrame = nullptr);
 184
 185 }  // namespace mozilla
 186
 187 #endif  // RETAINEDDISPLAYLISTHELPERS_H_