Bug 1396723 - Simplify the trait users of DoublyLinkedList need to define. r=froydnj draft
authorMike Hommey <mh+mozilla@glandium.org>
Sat, 02 Sep 2017 08:09:58 +0900
changeset 662658 d18a5f78a39fdc797551e56b0322de16ce07de8a
parent 662657 3603a8d57e837679dfc3349738d9f6f67575658f
child 662659 bf83cfa076a886055b80992173544615f0e57821
push id79156
push userbmo:mh+mozilla@glandium.org
push dateMon, 11 Sep 2017 23:09:24 +0000
reviewersfroydnj
bugs1396723
milestone57.0a1
Bug 1396723 - Simplify the trait users of DoublyLinkedList need to define. r=froydnj While the flexibility of the current trait is nice, it's actually not used to its fullest anywhere, and is boilerplate-y. While it is useful to be able to put the links anywhere, there's not much usefulness from being able to split mNext and mPrev. So instead of a trait that allows to get/set mNext and mPrev independently, we just use a trait that tells how to get a reference to a DoublyLinkedListElement from a list element itself.
js/src/vm/Debugger.h
js/src/vm/Runtime.h
mfbt/DoublyLinkedList.h
mfbt/tests/TestDoublyLinkedList.cpp
--- a/js/src/vm/Debugger.h
+++ b/js/src/vm/Debugger.h
@@ -254,17 +254,17 @@ typedef mozilla::Variant<ScriptSourceObj
 // Either a AbstractFramePtr, for ordinary JS, or a wasm::DebugFrame,
 // for synthesized frame of a wasm code.
 typedef mozilla::Variant<AbstractFramePtr, wasm::DebugFrame*> DebuggerFrameReferent;
 
 class Debugger : private mozilla::LinkedListElement<Debugger>
 {
     friend class Breakpoint;
     friend class DebuggerMemory;
-    friend struct JSRuntime::GlobalObjectWatchersSiblingAccess<Debugger>;
+    friend struct JSRuntime::GlobalObjectWatchersLinkAccess<Debugger>;
     friend class SavedStacks;
     friend class ScriptedOnStepHandler;
     friend class ScriptedOnPopHandler;
     friend class mozilla::LinkedListElement<Debugger>;
     friend class mozilla::LinkedList<Debugger>;
     friend bool (::JS_DefineDebuggerObject)(JSContext* cx, JS::HandleObject obj);
     friend bool (::JS::dbg::IsDebugger)(JSObject&);
     friend bool (::JS::dbg::GetDebuggeeGlobals)(JSContext*, JSObject&, AutoObjectVector&);
@@ -384,36 +384,27 @@ class Debugger : private mozilla::Linked
     js::GCPtrObject uncaughtExceptionHook; /* Strong reference. */
     bool enabled;
     bool allowUnobservedAsmJS;
     bool allowWasmBinarySource;
 
     // Whether to enable code coverage on the Debuggee.
     bool collectCoverageInfo;
 
-    template<typename T>
-    struct DebuggerSiblingAccess {
-      static T* GetNext(T* elm) {
-        return elm->debuggerLink.mNext;
-      }
-      static void SetNext(T* elm, T* next) {
-        elm->debuggerLink.mNext = next;
-      }
-      static T* GetPrev(T* elm) {
-        return elm->debuggerLink.mPrev;
-      }
-      static void SetPrev(T* elm, T* prev) {
-        elm->debuggerLink.mPrev = prev;
+    template <typename T>
+    struct DebuggerLinkAccess {
+      static mozilla::DoublyLinkedListElement<T>& Get(T* aThis) {
+        return aThis->debuggerLink;
       }
     };
 
     // List of all js::Breakpoints in this debugger.
     using BreakpointList =
         mozilla::DoublyLinkedList<js::Breakpoint,
-                                  DebuggerSiblingAccess<js::Breakpoint>>;
+                                  DebuggerLinkAccess<js::Breakpoint>>;
     BreakpointList breakpoints;
 
     // The set of GC numbers for which one or more of this Debugger's observed
     // debuggees participated in.
     using GCNumberSet = HashSet<uint64_t, DefaultHasher<uint64_t>, RuntimeAllocPolicy>;
     GCNumberSet observedGCs;
 
     using AllocationsLog = js::TraceableFifo<AllocationsLogEntry>;
@@ -1590,36 +1581,27 @@ class BreakpointSite {
     friend class Debugger;
 
   public:
     enum class Type { JS, Wasm };
 
   private:
     Type type_;
 
-    template<typename T>
-    struct SiteSiblingAccess {
-      static T* GetNext(T* elm) {
-        return elm->siteLink.mNext;
-      }
-      static void SetNext(T* elm, T* next) {
-        elm->siteLink.mNext = next;
-      }
-      static T* GetPrev(T* elm) {
-        return elm->siteLink.mPrev;
-      }
-      static void SetPrev(T* elm, T* prev) {
-        elm->siteLink.mPrev = prev;
+    template <typename T>
+    struct SiteLinkAccess {
+      static mozilla::DoublyLinkedListElement<T>& Get(T* aThis) {
+        return aThis->siteLink;
       }
     };
 
     // List of all js::Breakpoints at this instruction.
     using BreakpointList =
         mozilla::DoublyLinkedList<js::Breakpoint,
-                                  SiteSiblingAccess<js::Breakpoint>>;
+                                  SiteLinkAccess<js::Breakpoint>>;
     BreakpointList breakpoints;
     size_t enabledCount;  /* number of breakpoints in the list that are enabled */
 
   protected:
     virtual void recompile(FreeOp* fop) = 0;
     bool isEmpty() const;
     inline bool isEnabled() const { return enabledCount > 0; }
 
--- a/js/src/vm/Runtime.h
+++ b/js/src/vm/Runtime.h
@@ -577,34 +577,25 @@ struct JSRuntime : public js::MallocProv
     js::ActiveThreadData<mozilla::LinkedList<JS::detail::WeakCacheBase>> weakCaches_;
   public:
     mozilla::LinkedList<JS::detail::WeakCacheBase>& weakCaches() { return weakCaches_.ref(); }
     void registerWeakCache(JS::detail::WeakCacheBase* cachep) {
         weakCaches().insertBack(cachep);
     }
 
     template <typename T>
-    struct GlobalObjectWatchersSiblingAccess {
-      static T* GetNext(T* elm) {
-        return elm->onNewGlobalObjectWatchersLink.mNext;
-      }
-      static void SetNext(T* elm, T* next) {
-        elm->onNewGlobalObjectWatchersLink.mNext = next;
-      }
-      static T* GetPrev(T* elm) {
-        return elm->onNewGlobalObjectWatchersLink.mPrev;
-      }
-      static void SetPrev(T* elm, T* prev) {
-        elm->onNewGlobalObjectWatchersLink.mPrev = prev;
+    struct GlobalObjectWatchersLinkAccess {
+      static mozilla::DoublyLinkedListElement<T>& Get(T* aThis) {
+        return aThis->onNewGlobalObjectWatchersLink;
       }
     };
 
     using WatchersList =
         mozilla::DoublyLinkedList<js::Debugger,
-                                  GlobalObjectWatchersSiblingAccess<js::Debugger>>;
+                                  GlobalObjectWatchersLinkAccess<js::Debugger>>;
   private:
     /*
      * List of all enabled Debuggers that have onNewGlobalObject handler
      * methods established.
      */
     js::ActiveThreadData<WatchersList> onNewGlobalObjectWatchers_;
 
   public:
--- a/mfbt/DoublyLinkedList.h
+++ b/mfbt/DoublyLinkedList.h
@@ -60,70 +60,76 @@
  *       }
  *     }
  *   };
  */
 
 namespace mozilla {
 
 /**
- * Provides access to a next and previous element pointer named |mNext| and
- * |mPrev| respectively. This class is the default and will work if the list
- * element derives from DoublyLinkedListElement.
- *
- * Although designed to work with DoublyLinkedListElement this will als work
- * with any class that defines |mNext| and |mPrev| members with the correct
- * type.
- */
-template <typename T>
-struct DoublyLinkedSiblingAccess {
-  static void SetNext(T* aElm, T* aNext) { aElm->mNext = aNext; }
-  static T* GetNext(T* aElm) { return aElm->mNext; }
-  static void SetPrev(T* aElm, T* aPrev) { aElm->mPrev = aPrev; }
-  static T* GetPrev(T* aElm) { return aElm->mPrev; }
-};
-
-/**
  *  Deriving from this will allow T to be inserted into and removed from a
  *  DoublyLinkedList.
  */
 template <typename T>
-struct DoublyLinkedListElement
+class DoublyLinkedListElement
 {
-  friend struct DoublyLinkedSiblingAccess<T>;
+  template<typename U, typename E> friend class DoublyLinkedList;
+  friend T;
   T* mNext;
   T* mPrev;
 
 public:
   DoublyLinkedListElement() : mNext(nullptr), mPrev(nullptr) {}
 };
 
 /**
+ * Provides access to a DoublyLinkedListElement within T.
+ *
+ * The default implementation of this template works for types that derive
+ * from DoublyLinkedListElement, but one can specialize for their class so
+ * that some appropriate DoublyLinkedListElement reference is returned.
+ *
+ * For more complex cases (multiple DoublyLinkedListElements, for example),
+ * one can define their own trait class and use that as ElementAccess for
+ * DoublyLinkedList. See TestDoublyLinkedList.cpp for an example.
+ */
+template <typename T>
+struct GetDoublyLinkedListElement
+{
+  static_assert(mozilla::IsBaseOf<DoublyLinkedListElement<T>, T>::value,
+                "You need your own specialization of GetDoublyLinkedListElement"
+                " or use a separate Trait.");
+  static DoublyLinkedListElement<T>& Get(T* aThis)
+  {
+    return *aThis;
+  }
+};
+
+/**
  * A doubly linked list. |T| is the type of element stored in this list. |T|
  * must contain or have access to unique next and previous element pointers.
- * The template argument |SiblingAccess| provides code to tell this list how to
- * get and set the next and previous pointers. The actual storage of next/prev
- * links may reside anywhere and be encoded in any way.
+ * The template argument |ElementAccess| provides code to tell this list how to
+ * get a reference to a DoublyLinkedListElement that may reside anywhere.
  */
-template <typename T, typename SiblingAccess = DoublyLinkedSiblingAccess<T>>
+template <typename T, typename ElementAccess = GetDoublyLinkedListElement<T>>
 class DoublyLinkedList final
 {
   T* mHead;
   T* mTail;
 
   /**
    * Checks that either the list is empty and both mHead and mTail are nullptr
    * or the list has entries and both mHead and mTail are non-null.
    */
   bool isStateValid() const {
     return (mHead != nullptr) == (mTail != nullptr);
   }
 
   bool ElementNotInList(T* aElm) {
-    if (!SiblingAccess::GetNext(aElm) && !SiblingAccess::GetPrev(aElm)) {
+    if (!ElementAccess::Get(aElm).mNext && !ElementAccess::Get(aElm).mPrev) {
       // Both mNext and mPrev being NULL can mean two things:
       // - the element is not in the list.
       // - the element is the first and only element in the list.
       // So check for the latter.
       return mHead != aElm;
     }
     return false;
   }
@@ -143,28 +149,28 @@ public:
 
     Iterator() : mCurrent(nullptr) {}
     explicit Iterator(T* aCurrent) : mCurrent(aCurrent) {}
 
     T& operator *() const { return *mCurrent; }
     T* operator ->() const { return mCurrent; }
 
     Iterator& operator++() {
-      mCurrent = SiblingAccess::GetNext(mCurrent);
+      mCurrent = ElementAccess::Get(mCurrent).mNext;
       return *this;
     }
 
     Iterator operator++(int) {
       Iterator result = *this;
       ++(*this);
       return result;
     }
 
     Iterator& operator--() {
-      mCurrent = SiblingAccess::GetPrev(mCurrent);
+      mCurrent = ElementAccess::Get(mCurrent).mPrev;
       return *this;
     }
 
     Iterator operator--(int) {
       Iterator result = *this;
       --(*this);
       return result;
     }
@@ -202,20 +208,20 @@ public:
    * Inserts aElm into the list at the head position. |aElm| must not already
    * be in a list.
    */
   void pushFront(T* aElm) {
     MOZ_ASSERT(aElm);
     MOZ_ASSERT(ElementNotInList(aElm));
     MOZ_ASSERT(isStateValid());
 
-    SiblingAccess::SetNext(aElm, mHead);
+    ElementAccess::Get(aElm).mNext = mHead;
     if (mHead) {
-      MOZ_ASSERT(!SiblingAccess::GetPrev(mHead));
-      SiblingAccess::SetPrev(mHead, aElm);
+      MOZ_ASSERT(!ElementAccess::Get(mHead).mPrev);
+      ElementAccess::Get(mHead).mPrev = aElm;
     }
 
     mHead = aElm;
     if (!mTail) {
       mTail = aElm;
     }
   }
 
@@ -223,47 +229,47 @@ public:
    * Remove the head of the list and return it. Calling this on an empty list
    * will assert.
    */
   T* popFront() {
     MOZ_ASSERT(!isEmpty());
     MOZ_ASSERT(isStateValid());
 
     T* result = mHead;
-    mHead = result ? SiblingAccess::GetNext(result) : nullptr;
+    mHead = result ? ElementAccess::Get(result).mNext : nullptr;
     if (mHead) {
-      SiblingAccess::SetPrev(mHead, nullptr);
+      ElementAccess::Get(mHead).mPrev = nullptr;
     }
 
     if (mTail == result) {
       mTail = nullptr;
     }
 
     if (result) {
-      SiblingAccess::SetNext(result, nullptr);
-      SiblingAccess::SetPrev(result, nullptr);
+      ElementAccess::Get(result).mNext = nullptr;
+      ElementAccess::Get(result).mPrev = nullptr;
     }
 
     return result;
   }
 
   /**
    * Inserts aElm into the list at the tail position. |aElm| must not already
    * be in a list.
    */
   void pushBack(T* aElm) {
     MOZ_ASSERT(aElm);
     MOZ_ASSERT(ElementNotInList(aElm));
     MOZ_ASSERT(isStateValid());
 
-    SiblingAccess::SetNext(aElm, nullptr);
-    SiblingAccess::SetPrev(aElm, mTail);
+    ElementAccess::Get(aElm).mNext = nullptr;
+    ElementAccess::Get(aElm).mPrev = mTail;
     if (mTail) {
-      MOZ_ASSERT(!SiblingAccess::GetNext(mTail));
-      SiblingAccess::SetNext(mTail, aElm);
+      MOZ_ASSERT(!ElementAccess::Get(mTail).mNext);
+      ElementAccess::Get(mTail).mNext = aElm;
     }
 
     mTail = aElm;
     if (!mHead) {
       mHead = aElm;
     }
   }
 
@@ -271,28 +277,28 @@ public:
    * Remove the tail of the list and return it. Calling this on an empty list
    * will assert.
    */
   T* popBack() {
     MOZ_ASSERT(!isEmpty());
     MOZ_ASSERT(isStateValid());
 
     T* result = mTail;
-    mTail = result ? SiblingAccess::GetPrev(result) : nullptr;
+    mTail = result ? ElementAccess::Get(result).mPrev : nullptr;
     if (mTail) {
-      SiblingAccess::SetNext(mTail, nullptr);
+      ElementAccess::Get(mTail).mNext = nullptr;
     }
 
     if (mHead == result) {
       mHead = nullptr;
     }
 
     if (result) {
-      SiblingAccess::SetNext(result, nullptr);
-      SiblingAccess::SetPrev(result, nullptr);
+      ElementAccess::Get(result).mNext = nullptr;
+      ElementAccess::Get(result).mPrev = nullptr;
     }
 
     return result;
   }
 
   /**
    * Insert the given |aElm| *before* |aIter|.
    */
@@ -303,50 +309,50 @@ public:
 
     if (!aIter) {
       return pushBack(aElm);
     } else if (aIter == begin()) {
       return pushFront(aElm);
     }
 
     T* after = &(*aIter);
-    T* before = SiblingAccess::GetPrev(after);
+    T* before = ElementAccess::Get(after).mPrev;
     MOZ_ASSERT(before);
 
-    SiblingAccess::SetNext(before, aElm);
-    SiblingAccess::SetPrev(aElm, before);
-    SiblingAccess::SetNext(aElm, after);
-    SiblingAccess::SetPrev(after, aElm);
+    ElementAccess::Get(before).mNext = aElm;
+    ElementAccess::Get(aElm).mPrev = before;
+    ElementAccess::Get(aElm).mNext = after;
+    ElementAccess::Get(after).mPrev = aElm;
   }
 
   /**
    * Removes the given element from the list. The element must be in this list.
    */
   void remove(T* aElm) {
     MOZ_ASSERT(aElm);
-    MOZ_ASSERT(SiblingAccess::GetNext(aElm) || SiblingAccess::GetPrev(aElm) ||
+    MOZ_ASSERT(ElementAccess::Get(aElm).mNext || ElementAccess::Get(aElm).mPrev ||
                (aElm == mHead && aElm == mTail),
                "Attempted to remove element not in this list");
 
-    if (T* prev = SiblingAccess::GetPrev(aElm)) {
-      SiblingAccess::SetNext(prev, SiblingAccess::GetNext(aElm));
+    if (T* prev = ElementAccess::Get(aElm).mPrev) {
+      ElementAccess::Get(prev).mNext = ElementAccess::Get(aElm).mNext;
     } else {
       MOZ_ASSERT(mHead == aElm);
-      mHead = SiblingAccess::GetNext(aElm);
+      mHead = ElementAccess::Get(aElm).mNext;
     }
 
-    if (T* next = SiblingAccess::GetNext(aElm)) {
-      SiblingAccess::SetPrev(next, SiblingAccess::GetPrev(aElm));
+    if (T* next = ElementAccess::Get(aElm).mNext) {
+      ElementAccess::Get(next).mPrev = ElementAccess::Get(aElm).mPrev;
     } else {
       MOZ_ASSERT(mTail == aElm);
-      mTail = SiblingAccess::GetPrev(aElm);
+      mTail = ElementAccess::Get(aElm).mPrev;
     }
 
-    SiblingAccess::SetNext(aElm, nullptr);
-    SiblingAccess::SetPrev(aElm, nullptr);
+    ElementAccess::Get(aElm).mNext = nullptr;
+    ElementAccess::Get(aElm).mPrev = nullptr;
   }
 
   /**
    * Returns an iterator referencing the first found element whose value matches
    * the given element according to operator==.
    */
   Iterator find(const T& aElm) {
     return std::find(begin(), end(), aElm);
--- a/mfbt/tests/TestDoublyLinkedList.cpp
+++ b/mfbt/tests/TestDoublyLinkedList.cpp
@@ -116,42 +116,41 @@ TestDoublyLinkedList()
 
   MOZ_RELEASE_ASSERT(*list.begin() == two);
   MOZ_RELEASE_ASSERT(*++list.begin() == three);
 
   SomeClass four(4);
   MOZ_RELEASE_ASSERT(++list.begin() == list.find(four));
 }
 
+struct InTwoLists {
+  explicit InTwoLists(unsigned int aValue) : mValue(aValue) {}
+  DoublyLinkedListElement<InTwoLists> mListOne;
+  DoublyLinkedListElement<InTwoLists> mListTwo;
+  unsigned int mValue;
+
+  struct GetListOneTrait {
+    static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists *aThis) { return aThis->mListOne; }
+  };
+};
+
+namespace mozilla {
+
+template<>
+struct GetDoublyLinkedListElement<InTwoLists> {
+  static DoublyLinkedListElement<InTwoLists>& Get(InTwoLists* aThis) { return aThis->mListTwo; }
+};
+
+}
+
 static void
 TestCustomAccessor()
 {
-  struct InTwoLists {
-    explicit InTwoLists(unsigned int aValue) : mValue(aValue) {}
-    DoublyLinkedListElement<InTwoLists> mListOne;
-    DoublyLinkedListElement<InTwoLists> mListTwo;
-    unsigned int mValue;
-  };
-
-  struct ListOneSiblingAccess {
-    static void SetNext(InTwoLists* aElm, InTwoLists* aNext) { aElm->mListOne.mNext = aNext; }
-    static InTwoLists* GetNext(InTwoLists* aElm) { return aElm->mListOne.mNext; }
-    static void SetPrev(InTwoLists* aElm, InTwoLists* aPrev) { aElm->mListOne.mPrev = aPrev; }
-    static InTwoLists* GetPrev(InTwoLists* aElm) { return aElm->mListOne.mPrev; }
-  };
-
-  struct ListTwoSiblingAccess {
-    static void SetNext(InTwoLists* aElm, InTwoLists* aNext) { aElm->mListTwo.mNext = aNext; }
-    static InTwoLists* GetNext(InTwoLists* aElm) { return aElm->mListTwo.mNext; }
-    static void SetPrev(InTwoLists* aElm, InTwoLists* aPrev) { aElm->mListTwo.mPrev = aPrev; }
-    static InTwoLists* GetPrev(InTwoLists* aElm) { return aElm->mListTwo.mPrev; }
-  };
-
-  DoublyLinkedList<InTwoLists, ListOneSiblingAccess> listOne;
-  DoublyLinkedList<InTwoLists, ListTwoSiblingAccess> listTwo;
+  DoublyLinkedList<InTwoLists, InTwoLists::GetListOneTrait> listOne;
+  DoublyLinkedList<InTwoLists> listTwo;
 
   InTwoLists one(1);
   InTwoLists two(2);
 
   listOne.pushBack(&one);
   listOne.pushBack(&two);
   { unsigned int check[] { 1, 2 }; CheckListValues(listOne, check); }