--- a/js/xpconnect/src/XPCWrappedNative.cpp
+++ b/js/xpconnect/src/XPCWrappedNative.cpp
@@ -427,17 +427,18 @@ XPCWrappedNative::GetNewOrUsed(xpcObject
 
         wrapper = new XPCWrappedNative(helper.forgetCanonical(), proto);
     } else {
         RefPtr<XPCNativeInterface> iface = Interface;
         if (!iface)
             iface = XPCNativeInterface::GetISupports();
 
         AutoMarkingNativeSetPtr set(cx);
-        set = XPCNativeSet::GetNewOrUsed(nullptr, iface, 0);
+        XPCNativeSetKey key(nullptr, iface, 0);
+        set = XPCNativeSet::GetNewOrUsed(&key);
 
         if (!set)
             return NS_ERROR_FAILURE;
 
         wrapper =
             new XPCWrappedNative(helper.forgetCanonical(), Scope, set);
     }
 
@@ -1012,18 +1013,18 @@ private:
 
 bool
 XPCWrappedNative::ExtendSet(XPCNativeInterface* aInterface)
 {
     AutoJSContext cx;
 
     if (!mSet->HasInterface(aInterface)) {
         AutoMarkingNativeSetPtr newSet(cx);
-        newSet = XPCNativeSet::GetNewOrUsed(mSet, aInterface,
-                                            mSet->GetInterfaceCount());
+        XPCNativeSetKey key(mSet, aInterface, mSet->GetInterfaceCount());
+        newSet = XPCNativeSet::GetNewOrUsed(&key);
         if (!newSet)
             return false;
 
         mSet = newSet;
     }
     return true;
 }
 

--- a/js/xpconnect/src/XPCWrappedNativeInfo.cpp
+++ b/js/xpconnect/src/XPCWrappedNativeInfo.cpp
@@ -608,43 +608,39 @@ XPCNativeSet::ClearCacheEntryForClassInf
     XPCJSRuntime* rt = nsXPConnect::GetRuntimeInstance();
     ClassInfo2NativeSetMap* map = rt->GetClassInfo2NativeSetMap();
     if (map)
         map->Remove(classInfo);
 }
 
 // static
 XPCNativeSet*
-XPCNativeSet::GetNewOrUsed(XPCNativeSet* otherSet,
-                           XPCNativeInterface* newInterface,
-                           uint16_t position)
+XPCNativeSet::GetNewOrUsed(XPCNativeSetKey* key)
 {
     AutoJSContext cx;
     AutoMarkingNativeSetPtr set(cx);
     XPCJSRuntime* rt = XPCJSRuntime::Get();
     NativeSetMap* map = rt->GetNativeSetMap();
     if (!map)
         return nullptr;
 
-    XPCNativeSetKey key(otherSet, newInterface, position);
-
-    set = map->Find(&key);
+    set = map->Find(key);
 
     if (set)
         return set;
 
-    if (otherSet)
-        set = NewInstanceMutate(otherSet, newInterface, position);
+    if (key->GetBaseSet())
+        set = NewInstanceMutate(key);
     else
-        set = NewInstance({newInterface});
+        set = NewInstance({key->GetAddition()});
 
     if (!set)
         return nullptr;
 
-    XPCNativeSet* set2 = map->Add(&key, set);
+    XPCNativeSet* set2 = map->Add(key, set);
     if (!set2) {
         NS_ERROR("failed to add our set!");
         DestroyInstance(set);
         set = nullptr;
     } else if (set2 != set) {
         DestroyInstance(set);
         set = set2;
     }
@@ -683,17 +679,18 @@ XPCNativeSet::GetNewOrUsed(XPCNativeSet*
     // existing set. So let's just do the slow and easy thing and hope that the
     // above optimizations handle the common cases.
     XPCNativeSet* currentSet = firstSet;
     for (uint32_t i = 0; i < secondSet->mInterfaceCount; ++i) {
         XPCNativeInterface* iface = secondSet->mInterfaces[i];
         if (!currentSet->HasInterface(iface)) {
             // Create a new augmented set, inserting this interface at the end.
             uint32_t pos = currentSet->mInterfaceCount;
-            currentSet = XPCNativeSet::GetNewOrUsed(currentSet, iface, pos);
+            XPCNativeSetKey key(currentSet, iface, pos);
+            currentSet = XPCNativeSet::GetNewOrUsed(&key);
             if (!currentSet)
                 return nullptr;
         }
     }
 
     // We've got the union set. Hand it back to the caller.
     MOZ_ASSERT(currentSet->mInterfaceCount == uniqueCount);
     return currentSet;
@@ -743,20 +740,22 @@ XPCNativeSet::NewInstance(nsTArray<RefPt
     obj->mMemberCount = memberCount;
     obj->mInterfaceCount = slots;
 
     return obj;
 }
 
 // static
 XPCNativeSet*
-XPCNativeSet::NewInstanceMutate(XPCNativeSet* otherSet,
-                                XPCNativeInterface* newInterface,
-                                uint16_t position)
+XPCNativeSet::NewInstanceMutate(XPCNativeSetKey* key)
 {
+    XPCNativeSet* otherSet = key->GetBaseSet();
+    XPCNativeInterface* newInterface = key->GetAddition();
+    uint16_t position = key->GetPosition();
+
     MOZ_ASSERT(otherSet);
 
     if (!newInterface)
         return nullptr;
     if (position > otherSet->mInterfaceCount)
         return nullptr;
 
     // Use placement new to create an object with the right amount of space

--- a/js/xpconnect/src/xpcprivate.h
+++ b/js/xpconnect/src/xpcprivate.h
@@ -1296,19 +1296,17 @@ private:
 /***************************************************************************/
 // XPCNativeSet represents an ordered collection of XPCNativeInterface pointers.
 
 class XPCNativeSet final
 {
   public:
     static XPCNativeSet* GetNewOrUsed(const nsIID* iid);
     static XPCNativeSet* GetNewOrUsed(nsIClassInfo* classInfo);
-    static XPCNativeSet* GetNewOrUsed(XPCNativeSet* otherSet,
-                                      XPCNativeInterface* newInterface,
-                                      uint16_t position);
+    static XPCNativeSet* GetNewOrUsed(XPCNativeSetKey* key);
 
     // This generates a union set.
     //
     // If preserveFirstSetOrder is true, the elements from |firstSet| come first,
     // followed by any non-duplicate items from |secondSet|. If false, the same
     // algorithm is applied; but if we detect that |secondSet| is a superset of
     // |firstSet|, we return |secondSet| without worrying about whether the
     // ordering might differ from |firstSet|.
@@ -1375,19 +1373,17 @@ class XPCNativeSet final
     void DebugDump(int16_t depth);
 
     static void DestroyInstance(XPCNativeSet* inst);
 
     size_t SizeOfIncludingThis(mozilla::MallocSizeOf mallocSizeOf);
 
   protected:
     static XPCNativeSet* NewInstance(nsTArray<RefPtr<XPCNativeInterface>>&& array);
-    static XPCNativeSet* NewInstanceMutate(XPCNativeSet*       otherSet,
-                                           XPCNativeInterface* newInterface,
-                                           uint16_t            position);
+    static XPCNativeSet* NewInstanceMutate(XPCNativeSetKey* key);
     XPCNativeSet()
       : mMemberCount(0), mInterfaceCount(0), mMarked(0)
     {
         MOZ_COUNT_CTOR(XPCNativeSet);
     }
     ~XPCNativeSet() {
         for (int i = 0; i < mInterfaceCount; i++) {
             NS_RELEASE(mInterfaces[i]);