new file mode 100644
--- /dev/null
+++ b/js/public/TraceableFifo.h
@@ -0,0 +1,130 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+ * vim: set ts=8 sts=4 et sw=4 tw=99:
+ * 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 js_TraceableFifo_h
+#define js_TraceableFifo_h
+
+#include "js/RootingAPI.h"
+#include "js/Fifo.h"
+
+namespace js {
+
+template <typename, typename> struct DefaultTracer;
+
+// A TraceableFifo is a Fifo with an additional trace method that knows how to
+// visit all of the items stored in the Fifo. For Fifos that contain GC things,
+// this is usually more convenient than manually iterating and marking the
+// contents.
+//
+// Most types of GC pointers as keys and values can be traced with no extra
+// infrastructure. For structs and non-gc-pointer members, ensure that there is
+// a specialization of DefaultTracer<T> with an appropriate trace method
+// available to handle the custom type.
+//
+// Note that although this Fifo's trace will deal correctly with moved items, it
+// does not itself know when to barrier or trace items. To function properly it
+// must either be used with Rooted, or barriered and traced manually.
+template <typename T,
+          size_t MinInlineCapacity = 0,
+          typename AllocPolicy = TempAllocPolicy,
+          typename TraceFunc = DefaultTracer<T>>
+class TraceableFifo
+  : public js::Fifo<T, MinInlineCapacity, AllocPolicy>,
+    public JS::Traceable
+{
+    using Base = js::Fifo<T, MinInlineCapacity, AllocPolicy>;
+
+  public:
+    explicit TraceableFifo(AllocPolicy alloc = AllocPolicy()) : Base(alloc) {}
+
+    TraceableFifo(TraceableFifo&& rhs) : Base(mozilla::Move(rhs)) { }
+    TraceableFifo& operator=(TraceableFifo&& rhs) { return Base::operator=(mozilla::Move(rhs)); }
+
+    TraceableFifo(const TraceableFifo&) = delete;
+    TraceableFifo& operator=(const TraceableFifo&) = delete;
+
+    static void trace(TraceableFifo* tf, JSTracer* trc) {
+        for (size_t i = 0; i < tf->front_.length(); ++i)
+            TraceFunc::trace(trc, &tf->front_[i], "fifo element");
+        for (size_t i = 0; i < tf->rear_.length(); ++i)
+            TraceFunc::trace(trc, &tf->rear_[i], "fifo element");
+    }
+};
+
+template <typename Outer, typename T, size_t Capacity, typename AllocPolicy, typename TraceFunc>
+class TraceableFifoOperations
+{
+    using TF = TraceableFifo<T, Capacity, AllocPolicy, TraceFunc>;
+    const TF& fifo() const { return static_cast<const Outer*>(this)->extract(); }
+
+  public:
+    size_t length() const { return fifo().length(); }
+    bool empty() const { return fifo().empty(); }
+    const T& front() const { return fifo().front(); }
+};
+
+template <typename Outer, typename T, size_t Capacity, typename AllocPolicy, typename TraceFunc>
+class MutableTraceableFifoOperations
+  : public TraceableFifoOperations<Outer, T, Capacity, AllocPolicy, TraceFunc>
+{
+    using TF = TraceableFifo<T, Capacity, AllocPolicy, TraceFunc>;
+    TF& fifo() { return static_cast<Outer*>(this)->extract(); }
+
+  public:
+    T& front() { return fifo().front(); }
+
+    template<typename U> bool pushBack(U&& u) { return fifo().pushBack(mozilla::Forward<U>(u)); }
+    template<typename... Args> bool emplaceBack(Args&&... args) {
+        return fifo().emplaceBack(mozilla::Forward<Args...>(args...));
+    }
+
+    bool popFront() { return fifo().popFront(); }
+    void clear() { fifo().clear(); }
+};
+
+template <typename A, size_t B, typename C, typename D>
+class RootedBase<TraceableFifo<A,B,C,D>>
+  : public MutableTraceableFifoOperations<JS::Rooted<TraceableFifo<A,B,C,D>>, A,B,C,D>
+{
+    using TF = TraceableFifo<A,B,C,D>;
+
+    friend class TraceableFifoOperations<JS::Rooted<TF>, A,B,C,D>;
+    const TF& extract() const { return *static_cast<const JS::Rooted<TF>*>(this)->address(); }
+
+    friend class MutableTraceableFifoOperations<JS::Rooted<TF>, A,B,C,D>;
+    TF& extract() { return *static_cast<JS::Rooted<TF>*>(this)->address(); }
+};
+
+template <typename A, size_t B, typename C, typename D>
+class MutableHandleBase<TraceableFifo<A,B,C,D>>
+  : public MutableTraceableFifoOperations<JS::MutableHandle<TraceableFifo<A,B,C,D>>, A,B,C,D>
+{
+    using TF = TraceableFifo<A,B,C,D>;
+
+    friend class TraceableFifoOperations<JS::MutableHandle<TF>, A,B,C,D>;
+    const TF& extract() const {
+        return *static_cast<const JS::MutableHandle<TF>*>(this)->address();
+    }
+
+    friend class MutableTraceableFifoOperations<JS::MutableHandle<TF>, A,B,C,D>;
+    TF& extract() { return *static_cast<JS::MutableHandle<TF>*>(this)->address(); }
+};
+
+template <typename A, size_t B, typename C, typename D>
+class HandleBase<TraceableFifo<A,B,C,D>>
+  : public TraceableFifoOperations<JS::Handle<TraceableFifo<A,B,C,D>>, A,B,C,D>
+{
+    using TF = TraceableFifo<A,B,C,D>;
+
+    friend class TraceableFifoOperations<JS::Handle<TF>, A,B,C,D>;
+    const TF& extract() const {
+        return *static_cast<const JS::Handle<TF>*>(this)->address();
+    }
+};
+
+} // namespace js
+
+#endif // js_TraceableFifo_h

--- a/js/src/jsapi-tests/testGCExactRooting.cpp
+++ b/js/src/jsapi-tests/testGCExactRooting.cpp
@@ -1,16 +1,17 @@
 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 * vim: set ts=8 sts=4 et sw=4 tw=99:
 */
 /* 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/. */
 
 #include "js/RootingAPI.h"
+#include "js/TraceableFifo.h"
 #include "js/TraceableHashTable.h"
 #include "js/TraceableVector.h"
 
 #include "jsapi-tests/tests.h"
 
 BEGIN_TEST(testGCExactRooting)
 {
     JS::RootedObject rootCx(cx, JS_NewPlainObject(cx));
@@ -271,16 +272,57 @@ receiveMutableHandleToShapeVector(JS::Mu
     // Ensure range enumeration works through the handle.
     for (auto shape : handle) {
         CHECK(shape);
     }
     return true;
 }
 END_TEST(testGCRootedVector)
 
+BEGIN_TEST(testTraceableFifo)
+{
+    using ShapeFifo = TraceableFifo<Shape*>;
+    JS::Rooted<ShapeFifo> shapes(cx, ShapeFifo(cx));
+    CHECK(shapes.empty());
+
+    for (size_t i = 0; i < 10; ++i) {
+        RootedObject obj(cx, JS_NewObject(cx, nullptr));
+        RootedValue val(cx, UndefinedValue());
+        // Construct a unique property name to ensure that the object creates a
+        // new shape.
+        char buffer[2];
+        buffer[0] = 'a' + i;
+        buffer[1] = '\0';
+        CHECK(JS_SetProperty(cx, obj, buffer, val));
+        CHECK(shapes.pushBack(obj->as<NativeObject>().lastProperty()));
+    }
+
+    CHECK(shapes.length() == 10);
+
+    JS_GC(rt);
+    JS_GC(rt);
+
+    for (size_t i = 0; i < 10; ++i) {
+        // Check the shape to ensure it did not get collected.
+        char buffer[2];
+        buffer[0] = 'a' + i;
+        buffer[1] = '\0';
+        bool match;
+        CHECK(JS_StringEqualsAscii(cx, JSID_TO_STRING(shapes.front()->propid()), buffer, &match));
+        CHECK(match);
+        CHECK(shapes.popFront());
+    }
+
+    CHECK(shapes.empty());
+    return true;
+}
+END_TEST(testTraceableFifo)
+
+using ShapeVec = TraceableVector<Shape*>;
+
 static bool
 FillVector(JSContext* cx, MutableHandle<ShapeVec> shapes)
 {
     for (size_t i = 0; i < 10; ++i) {
         RootedObject obj(cx, JS_NewObject(cx, nullptr));
         RootedValue val(cx, UndefinedValue());
         // Construct a unique property name to ensure that the object creates a
         // new shape.

--- a/js/src/moz.build
+++ b/js/src/moz.build
@@ -118,16 +118,17 @@ EXPORTS.js += [
     '../public/Principals.h',
     '../public/ProfilingFrameIterator.h',
     '../public/ProfilingStack.h',
     '../public/Proxy.h',
     '../public/RequiredDefines.h',
     '../public/RootingAPI.h',
     '../public/SliceBudget.h',
     '../public/StructuredClone.h',
+    '../public/TraceableFifo.h',
     '../public/TraceableHashTable.h',
     '../public/TraceableVector.h',
     '../public/TraceKind.h',
     '../public/TracingAPI.h',
     '../public/TrackedOptimizationInfo.h',
     '../public/TypeDecls.h',
     '../public/UbiNode.h',
     '../public/UbiNodeTraverse.h',