Merge mozilla-central to autoland
authorDorel Luca <dluca@mozilla.com>
Tue, 23 Oct 2018 07:50:37 +0300
changeset 490847 cc96d514beb84065d58268555e4f988269fe772a
parent 490846 b7b09fca2cc5c9b06ecf3a4fb4494b9a867d4541 (current diff)
parent 490734 77f4c84bebf05b7fddb3f5bdb8e7de0d2eb3ebd6 (diff)
child 490848 8ad2b19be6b9f41fde82dc95a9ae71bced32e64c
push id247
push userfmarier@mozilla.com
push dateSat, 27 Oct 2018 01:06:44 +0000
milestone65.0a1
Merge mozilla-central to autoland
dom/xbl/builtin/android/jar.mn
dom/xbl/builtin/android/platformHTMLBindings.xml
dom/xbl/builtin/browser-base.inc
dom/xbl/builtin/editor-base.inc
dom/xbl/builtin/emacs/jar.mn
dom/xbl/builtin/emacs/platformHTMLBindings.xml
dom/xbl/builtin/input-fields-base.inc
dom/xbl/builtin/mac/jar.mn
dom/xbl/builtin/mac/platformHTMLBindings.xml
dom/xbl/builtin/textareas-base.inc
dom/xbl/builtin/unix/jar.mn
dom/xbl/builtin/unix/platformHTMLBindings.xml
dom/xbl/builtin/win/jar.mn
dom/xbl/builtin/win/platformHTMLBindings.xml
js/src/jit/arm64/CodeGenerator-arm64.cpp
js/src/jit/arm64/Trampoline-arm64.cpp
testing/web-platform/meta/dom/nodes/Node-replaceChild.html.ini
--- a/devtools/client/framework/toolbox.js
+++ b/devtools/client/framework/toolbox.js
@@ -3,16 +3,17 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 "use strict";
 
 const SOURCE_MAP_WORKER = "resource://devtools/client/shared/source-map/worker.js";
 const SOURCE_MAP_WORKER_ASSETS = "resource://devtools/client/shared/source-map/assets/";
 
 const MAX_ORDINAL = 99;
+const SHOW_ALL_ANONYMOUS_CONTENT_PREF = "devtools.inspector.showAllAnonymousContent";
 const SPLITCONSOLE_ENABLED_PREF = "devtools.toolbox.splitconsoleEnabled";
 const SPLITCONSOLE_HEIGHT_PREF = "devtools.toolbox.splitconsoleHeight";
 const DISABLE_AUTOHIDE_PREF = "ui.popup.disable_autohide";
 const HOST_HISTOGRAM = "DEVTOOLS_TOOLBOX_HOST";
 const CURRENT_THEME_SCALAR = "devtools.current_theme";
 const HTML_NS = "http://www.w3.org/1999/xhtml";
 
 var {Ci, Cc} = require("chrome");
@@ -1439,21 +1440,25 @@ Toolbox.prototype = {
       this.frameButton.disabled = true;
       this.frameButton.description = L10N.getStr("toolbox.frames.disabled.tooltip");
     } else {
       // Otherwise, enable the button and update the description.
       this.frameButton.disabled = false;
       this.frameButton.description = L10N.getStr("toolbox.frames.tooltip");
     }
 
-    // Highlight the button when a child frame is selected
+    // Highlight the button when a child frame is selected and visible.
     const selectedFrame = this.frameMap.get(this.selectedFrameId) || {};
-    this.frameButton.isChecked = selectedFrame.parentID != null;
-
-    this.frameButton.isVisible = this._commandIsVisible(this.frameButton);
+    const isVisible = this._commandIsVisible(this.frameButton);
+
+    this.frameButton.isVisible = isVisible;
+
+    if (isVisible) {
+      this.frameButton.isChecked = selectedFrame.parentID != null;
+    }
   },
 
   /**
    * Ensure the visibility of each toolbox button matches the preference value.
    */
   _commandIsVisible: function(button) {
     const {
       isTargetSupported,
@@ -1683,17 +1688,17 @@ Toolbox.prototype = {
   /**
    * Ensure the tool with the given id is loaded.
    *
    * @param {string} id
    *        The id of the tool to load.
    */
   loadTool: function(id) {
     if (id === "inspector" && !this._inspector) {
-      return this.initInspector().then(() => this.loadTool(id));
+      this.initInspector();
     }
 
     let iframe = this.doc.getElementById("toolbox-panel-iframe-" + id);
     if (iframe) {
       const panel = this._toolPanels.get(id);
       return new Promise(resolve => {
         if (panel) {
           resolve(panel);
@@ -1727,17 +1732,29 @@ Toolbox.prototype = {
 
       // If no parent yet, append the frame into default location.
       if (!iframe.parentNode) {
         const vbox = this.doc.getElementById("toolbox-panel-" + id);
         vbox.appendChild(iframe);
         vbox.visibility = "visible";
       }
 
-      const onLoad = () => {
+      const onLoad = async () => {
+        if (id === "inspector") {
+          await this._initInspector;
+
+          // Stop loading the inspector if the toolbox is already being destroyed. This
+          // can happen in unit tests where the tests are rapidly opening and closing the
+          // toolbox and we encounter the scenario where the toolbox is closing as
+          // the inspector is still loading.
+          if (this._destroyingInspector) {
+            return;
+          }
+        }
+
         // Prevent flicker while loading by waiting to make visible until now.
         iframe.style.visibility = "visible";
 
         // Try to set the dir attribute as early as possible.
         this.setIframeDocumentDir(iframe);
 
         // The build method should return a panel instance, so events can
         // be fired with the panel as an argument. However, in order to keep
@@ -2669,32 +2686,43 @@ Toolbox.prototype = {
    */
   initInspector: function() {
     if (!this._initInspector) {
       this._initInspector = (async function() {
         // Temporary fix for bug #1493131 - inspector has a different life cycle
         // than most other fronts because it is closely related to the toolbox.
         // TODO: replace with getFront once inspector is separated from the toolbox
         this._inspector = this.target.getInspector();
-        const pref = "devtools.inspector.showAllAnonymousContent";
-        const showAllAnonymousContent = Services.prefs.getBoolPref(pref);
-        this._walker = await this._inspector.getWalker({ showAllAnonymousContent });
+
+        await Promise.all([
+          this._getWalker(),
+          this._getHighlighter(),
+        ]);
+
         this._selection = new Selection(this._walker);
+
         this._selection.on("new-node-front", this._onNewSelectedNodeFront);
-
         this.walker.on("highlighter-ready", this._highlighterReady);
         this.walker.on("highlighter-hide", this._highlighterHidden);
-
-        const autohide = !flags.testing;
-        this._highlighter = await this._inspector.getHighlighter(autohide);
       }.bind(this))();
     }
     return this._initInspector;
   },
 
+  _getWalker: async function() {
+    const showAllAnonymousContent = Services.prefs.getBoolPref(
+      SHOW_ALL_ANONYMOUS_CONTENT_PREF);
+    this._walker = await this._inspector.getWalker({ showAllAnonymousContent });
+  },
+
+  _getHighlighter: async function() {
+    const autohide = !flags.testing;
+    this._highlighter = await this._inspector.getHighlighter(autohide);
+  },
+
   _onNewSelectedNodeFront: function() {
     // Emit a "selection-changed" event when the toolbox.selection has been set
     // to a new node (or cleared). Currently used in the WebExtensions APIs (to
     // provide the `devtools.panels.elements.onSelectionChanged` event).
     this.emit("selection-changed");
   },
 
   _onInspectObject: function(packet) {
--- a/dom/base/nsContentUtils.cpp
+++ b/dom/base/nsContentUtils.cpp
@@ -7863,21 +7863,26 @@ nsresult
 nsContentUtils::CalculateBufferSizeForImage(const uint32_t& aStride,
                                             const IntSize& aImageSize,
                                             const SurfaceFormat& aFormat,
                                             size_t* aMaxBufferSize,
                                             size_t* aUsedBufferSize)
 {
   CheckedInt32 requiredBytes =
     CheckedInt32(aStride) * CheckedInt32(aImageSize.height);
-  if (!requiredBytes.isValid()) {
+
+  CheckedInt32 usedBytes = requiredBytes - aStride +
+    (CheckedInt32(aImageSize.width) * BytesPerPixel(aFormat));
+  if (!usedBytes.isValid()) {
     return NS_ERROR_FAILURE;
   }
+
+  MOZ_ASSERT(requiredBytes.isValid(), "usedBytes valid but not required?");
   *aMaxBufferSize = requiredBytes.value();
-  *aUsedBufferSize = *aMaxBufferSize - aStride + (aImageSize.width * BytesPerPixel(aFormat));
+  *aUsedBufferSize = usedBytes.value();
   return NS_OK;
 }
 
 nsresult
 nsContentUtils::DataTransferItemToImage(const IPCDataTransferItem& aItem,
                                         imgIContainer** aContainer)
 {
   MOZ_ASSERT(aItem.data().type() == IPCDataTransferData::TShmem);
--- a/dom/base/nsINode.cpp
+++ b/dom/base/nsINode.cpp
@@ -2042,247 +2042,289 @@ nsINode::RemoveChildNode(nsIContent* aKi
   }
 
   aKid->UnbindFromTree();
 }
 
 // When replacing, aRefChild is the content being replaced; when
 // inserting it's the content before which we're inserting.  In the
 // latter case it may be null.
+//
+// If aRv is a failure after this call, the insertion should not happen.
+//
+// This implements the parts of
+// https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity and
+// the checks in https://dom.spec.whatwg.org/#concept-node-replace that
+// depend on the child nodes or come after steps that depend on the child nodes
+// (steps 2-6 in both cases).
 static
-bool IsAllowedAsChild(nsIContent* aNewChild, nsINode* aParent,
-                      bool aIsReplace, nsINode* aRefChild)
+void EnsureAllowedAsChild(nsINode* aNewChild, nsINode* aParent,
+                          bool aIsReplace, nsINode* aRefChild,
+                          ErrorResult& aRv)
 {
   MOZ_ASSERT(aNewChild, "Must have new child");
   MOZ_ASSERT_IF(aIsReplace, aRefChild);
   MOZ_ASSERT(aParent);
   MOZ_ASSERT(aParent->IsDocument() ||
              aParent->IsDocumentFragment() ||
              aParent->IsElement(),
              "Nodes that are not documents, document fragments or elements "
              "can't be parents!");
 
+  // Step 2.
   // A common case is that aNewChild has no kids, in which case
   // aParent can't be a descendant of aNewChild unless they're
   // actually equal to each other.  Fast-path that case, since aParent
   // could be pretty deep in the DOM tree.
   if (aNewChild == aParent ||
       ((aNewChild->GetFirstChild() ||
         // HTML template elements and ShadowRoot hosts need
         // to be checked to ensure that they are not inserted into
         // the hosted content.
         aNewChild->NodeInfo()->NameAtom() == nsGkAtoms::_template ||
-        aNewChild->GetShadowRoot()) &&
+        (aNewChild->IsElement() && aNewChild->AsElement()->GetShadowRoot())) &&
        nsContentUtils::ContentIsHostIncludingDescendantOf(aParent,
                                                           aNewChild))) {
-    return false;
+    aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+    return;
+  }
+
+  // Step 3.
+  if (aRefChild && aRefChild->GetParentNode() != aParent) {
+    aRv.Throw(NS_ERROR_DOM_NOT_FOUND_ERR);
+    return;
   }
 
+  // Step 4.
+  if (!aNewChild->IsContent()) {
+    aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+    return;
+  }
+
+  // Steps 5 and 6 combined.
   // The allowed child nodes differ for documents and elements
   switch (aNewChild->NodeType()) {
   case nsINode::COMMENT_NODE :
   case nsINode::PROCESSING_INSTRUCTION_NODE :
     // OK in both cases
-    return true;
+    return;
   case nsINode::TEXT_NODE :
   case nsINode::CDATA_SECTION_NODE :
   case nsINode::ENTITY_REFERENCE_NODE :
     // Allowed under Elements and DocumentFragments
-    return aParent->NodeType() != nsINode::DOCUMENT_NODE;
+    if (aParent->NodeType() == nsINode::DOCUMENT_NODE) {
+      aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+    }
+    return;
   case nsINode::ELEMENT_NODE :
     {
       if (!aParent->IsDocument()) {
         // Always ok to have elements under other elements or document fragments
-        return true;
+        return;
       }
 
       nsIDocument* parentDocument = aParent->AsDocument();
       Element* rootElement = parentDocument->GetRootElement();
       if (rootElement) {
         // Already have a documentElement, so this is only OK if we're
         // replacing it.
-        return aIsReplace && rootElement == aRefChild;
+        if (!aIsReplace || rootElement != aRefChild) {
+          aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+        }
+        return;
       }
 
       // We don't have a documentElement yet.  Our one remaining constraint is
       // that the documentElement must come after the doctype.
       if (!aRefChild) {
         // Appending is just fine.
-        return true;
+        return;
       }
 
       nsIContent* docTypeContent = parentDocument->GetDoctype();
       if (!docTypeContent) {
         // It's all good.
-        return true;
+        return;
       }
 
       int32_t doctypeIndex = aParent->ComputeIndexOf(docTypeContent);
       int32_t insertIndex = aParent->ComputeIndexOf(aRefChild);
 
       // Now we're OK in the following two cases only:
       // 1) We're replacing something that's not before the doctype
       // 2) We're inserting before something that comes after the doctype
-      return aIsReplace ? (insertIndex >= doctypeIndex) :
+      bool ok = aIsReplace ? (insertIndex >= doctypeIndex) :
         insertIndex > doctypeIndex;
+      if (!ok) {
+        aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+      }
+      return;
     }
   case nsINode::DOCUMENT_TYPE_NODE :
     {
       if (!aParent->IsDocument()) {
         // doctypes only allowed under documents
-        return false;
+        aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+        return;
       }
 
       nsIDocument* parentDocument = aParent->AsDocument();
       nsIContent* docTypeContent = parentDocument->GetDoctype();
       if (docTypeContent) {
         // Already have a doctype, so this is only OK if we're replacing it
-        return aIsReplace && docTypeContent == aRefChild;
+        if (!aIsReplace || docTypeContent != aRefChild) {
+          aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+        }
+        return;
       }
 
       // We don't have a doctype yet.  Our one remaining constraint is
       // that the doctype must come before the documentElement.
       Element* rootElement = parentDocument->GetRootElement();
       if (!rootElement) {
         // It's all good
-        return true;
+        return;
       }
 
       if (!aRefChild) {
         // Trying to append a doctype, but have a documentElement
-        return false;
+        aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+        return;
       }
 
       int32_t rootIndex = aParent->ComputeIndexOf(rootElement);
       int32_t insertIndex = aParent->ComputeIndexOf(aRefChild);
 
       // Now we're OK if and only if insertIndex <= rootIndex.  Indeed, either
       // we end up replacing aRefChild or we end up before it.  Either one is
       // ok as long as aRefChild is not after rootElement.
-      return insertIndex <= rootIndex;
+      if (insertIndex > rootIndex) {
+        aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+      }
+      return;
     }
   case nsINode::DOCUMENT_FRAGMENT_NODE :
     {
       // Note that for now we only allow nodes inside document fragments if
       // they're allowed inside elements.  If we ever change this to allow
       // doctype nodes in document fragments, we'll need to update this code.
       // Also, there's a version of this code in ReplaceOrInsertBefore.  If you
       // change this code, change that too.
       if (!aParent->IsDocument()) {
         // All good here
-        return true;
+        return;
       }
 
       bool sawElement = false;
       for (nsIContent* child = aNewChild->GetFirstChild();
            child;
            child = child->GetNextSibling()) {
         if (child->IsElement()) {
           if (sawElement) {
             // Can't put two elements into a document
-            return false;
+            aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+            return;
           }
           sawElement = true;
         }
-        // If we can put this content at the the right place, we might be ok;
+        // If we can put this content at the right place, we might be ok;
         // if not, we bail out.
-        if (!IsAllowedAsChild(child, aParent, aIsReplace, aRefChild)) {
-          return false;
+        EnsureAllowedAsChild(child, aParent, aIsReplace, aRefChild, aRv);
+        if (aRv.Failed()) {
+          return;
         }
       }
 
       // Everything in the fragment checked out ok, so we can stick it in here
-      return true;
+      return;
     }
   default:
     /*
      * aNewChild is of invalid type.
      */
     break;
   }
 
-  return false;
+  aRv.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
 }
 
+// Implements https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity
 void
 nsINode::EnsurePreInsertionValidity(nsINode& aNewChild, nsINode* aRefChild,
                                     ErrorResult& aError)
 {
-  EnsurePreInsertionValidity1(aNewChild, aRefChild, aError);
+  EnsurePreInsertionValidity1(aError);
   if (aError.Failed()) {
     return;
   }
   EnsurePreInsertionValidity2(false, aNewChild, aRefChild, aError);
 }
 
+// Implements the parts of
+// https://dom.spec.whatwg.org/#concept-node-ensure-pre-insertion-validity and
+// the checks in https://dom.spec.whatwg.org/#concept-node-replace that can be
+// evaluated before ever looking at the child nodes (step 1 in both cases).
 void
-nsINode::EnsurePreInsertionValidity1(nsINode& aNewChild, nsINode* aRefChild,
-                                     ErrorResult& aError)
+nsINode::EnsurePreInsertionValidity1(ErrorResult& aError)
 {
-  if ((!IsDocument() && !IsDocumentFragment() && !IsElement()) ||
-      !aNewChild.IsContent()) {
+  if (!IsDocument() && !IsDocumentFragment() && !IsElement()) {
     aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
     return;
   }
 }
 
 void
 nsINode::EnsurePreInsertionValidity2(bool aReplace, nsINode& aNewChild,
                                      nsINode* aRefChild, ErrorResult& aError)
 {
-  nsIContent* newContent = aNewChild.AsContent();
-  if (newContent->IsRootOfAnonymousSubtree()) {
+  if (aNewChild.IsContent() &&
+      aNewChild.AsContent()->IsRootOfAnonymousSubtree()) {
     // This is anonymous content.  Don't allow its insertion
     // anywhere, since it might have UnbindFromTree calls coming
     // its way.
     aError.Throw(NS_ERROR_DOM_NOT_SUPPORTED_ERR);
     return;
   }
 
   // Make sure that the inserted node is allowed as a child of its new parent.
-  if (!IsAllowedAsChild(newContent, this, aReplace, aRefChild)) {
-    aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
-    return;
-  }
+  EnsureAllowedAsChild(&aNewChild, this, aReplace, aRefChild, aError);
 }
 
 nsINode*
 nsINode::ReplaceOrInsertBefore(bool aReplace, nsINode* aNewChild,
                                nsINode* aRefChild, ErrorResult& aError)
 {
   // XXXbz I wish I could assert that nsContentUtils::IsSafeToRunScript() so we
   // could rely on scriptblockers going out of scope to actually run XBL
   // teardown, but various crud adds nodes under scriptblockers (e.g. native
   // anonymous content).  The only good news is those insertions can't trigger
   // the bad XBL cases.
   MOZ_ASSERT_IF(aReplace, aRefChild);
 
-  EnsurePreInsertionValidity1(*aNewChild, aRefChild, aError);
+  // Before firing DOMNodeRemoved events, make sure this is actually an insert
+  // we plan to do.
+  EnsurePreInsertionValidity1(aError);
+  if (aError.Failed()) {
+    return nullptr;
+  }
+
+  EnsurePreInsertionValidity2(aReplace, *aNewChild, aRefChild, aError);
   if (aError.Failed()) {
     return nullptr;
   }
 
   uint16_t nodeType = aNewChild->NodeType();
 
   // Before we do anything else, fire all DOMNodeRemoved mutation events
   // We do this up front as to avoid having to deal with script running
   // at random places further down.
   // Scope firing mutation events so that we don't carry any state that
   // might be stale
   {
-    // This check happens again further down (though then using
-    // ComputeIndexOf).
-    // We're only checking this here to avoid firing mutation events when
-    // none should be fired.
-    // It's ok that we do the check twice in the case when firing mutation
-    // events as we need to recheck after running script anyway.
-    if (aRefChild && aRefChild->GetParentNode() != this) {
-      aError.Throw(NS_ERROR_DOM_NOT_FOUND_ERR);
-      return nullptr;
-    }
+    nsMutationGuard guard;
 
     // If we're replacing, fire for node-to-be-replaced.
     // If aRefChild == aNewChild then we'll fire for it in check below
     if (aReplace && aRefChild != aNewChild) {
       nsContentUtils::MaybeFireNodeRemoved(aRefChild, this);
     }
 
     // If the new node already has a parent, fire for removing from old
@@ -2292,28 +2334,27 @@ nsINode::ReplaceOrInsertBefore(bool aRep
       nsContentUtils::MaybeFireNodeRemoved(aNewChild, oldParent);
     }
 
     // If we're inserting a fragment, fire for all the children of the
     // fragment
     if (nodeType == DOCUMENT_FRAGMENT_NODE) {
       static_cast<FragmentOrElement*>(aNewChild)->FireNodeRemovedForChildren();
     }
-    // Verify that our aRefChild is still sensible
-    if (aRefChild && aRefChild->GetParentNode() != this) {
-      aError.Throw(NS_ERROR_DOM_NOT_FOUND_ERR);
-      return nullptr;
+
+    if (guard.Mutated(0)) {
+      // Re-check the parts of our pre-insertion validity that might depend on
+      // the tree shape.
+      EnsurePreInsertionValidity2(aReplace, *aNewChild, aRefChild, aError);
+      if (aError.Failed()) {
+        return nullptr;
+      }
     }
   }
 
-  EnsurePreInsertionValidity2(aReplace, *aNewChild, aRefChild, aError);
-  if (aError.Failed()) {
-    return nullptr;
-  }
-
   // Record the node to insert before, if any
   nsIContent* nodeToInsertBefore;
   if (aReplace) {
     nodeToInsertBefore = aRefChild->GetNextSibling();
   } else {
     // Since aRefChild is our child, it must be an nsIContent object.
     nodeToInsertBefore = aRefChild ? aRefChild->AsContent() : nullptr;
   }
@@ -2350,43 +2391,36 @@ nsINode::ReplaceOrInsertBefore(bool aRep
         mb.SetNextSibling(next);
       }
     }
 
     // We expect one mutation (the removal) to have happened.
     if (guard.Mutated(1)) {
       // XBL destructors, yuck.
 
-      // Verify that nodeToInsertBefore, if non-null, is still our child.  If
-      // it's not, there's no way we can do this insert sanely; just bail out.
-      if (nodeToInsertBefore && nodeToInsertBefore->GetParent() != this) {
-        aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
-        return nullptr;
-      }
-
       // Verify that newContent has no parent.
       if (newContent->GetParentNode()) {
         aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
         return nullptr;
       }
 
       // And verify that newContent is still allowed as our child.
       if (aNewChild == aRefChild) {
         // We've already removed aRefChild.  So even if we were doing a replace,
         // now we're doing a simple insert before nodeToInsertBefore.
-        if (!IsAllowedAsChild(newContent, this, false, nodeToInsertBefore)) {
-          aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+        EnsureAllowedAsChild(newContent, this, false, nodeToInsertBefore, aError);
+        if (aError.Failed()) {
           return nullptr;
         }
       } else {
-        if ((aRefChild && aRefChild->GetParent() != this) ||
-            !IsAllowedAsChild(newContent, this, aReplace, aRefChild)) {
-          aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+        EnsureAllowedAsChild(newContent, this, aReplace, aRefChild, aError);
+        if (aError.Failed()) {
           return nullptr;
         }
+
         // And recompute nodeToInsertBefore, just in case.
         if (aReplace) {
           nodeToInsertBefore = aRefChild->GetNextSibling();
         } else {
           nodeToInsertBefore = aRefChild ? aRefChild->AsContent() : nullptr;
         }
       }
     }
@@ -2442,17 +2476,17 @@ nsINode::ReplaceOrInsertBefore(bool aRep
         if (fragChildren->ElementAt(i)->GetParentNode()) {
           aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
           return nullptr;
         }
       }
 
       // Note that unlike the single-element case above, none of our kids can
       // be aRefChild, so we can always pass through aReplace in the
-      // IsAllowedAsChild checks below and don't have to worry about whether
+      // EnsureAllowedAsChild checks below and don't have to worry about whether
       // recomputing nodeToInsertBefore is OK.
 
       // Verify that our aRefChild is still sensible
       if (aRefChild && aRefChild->GetParent() != this) {
         aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
         return nullptr;
       }
 
@@ -2460,33 +2494,33 @@ nsINode::ReplaceOrInsertBefore(bool aRep
       if (aReplace) {
         nodeToInsertBefore = aRefChild->GetNextSibling();
       } else {
         // If aRefChild has 'this' as a parent, it must be an nsIContent.
         nodeToInsertBefore = aRefChild ? aRefChild->AsContent() : nullptr;
       }
 
       // And verify that newContent is still allowed as our child.  Sadly, we
-      // need to reimplement the relevant part of IsAllowedAsChild() because
+      // need to reimplement the relevant part of EnsureAllowedAsChild() because
       // now our nodes are in an array and all.  If you change this code,
       // change the code there.
       if (IsDocument()) {
         bool sawElement = false;
         for (uint32_t i = 0; i < count; ++i) {
           nsIContent* child = fragChildren->ElementAt(i);
           if (child->IsElement()) {
             if (sawElement) {
               // No good
               aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
               return nullptr;
             }
             sawElement = true;
           }
-          if (!IsAllowedAsChild(child, this, aReplace, aRefChild)) {
-            aError.Throw(NS_ERROR_DOM_HIERARCHY_REQUEST_ERR);
+          EnsureAllowedAsChild(child, this, aReplace, aRefChild, aError);
+          if (aError.Failed()) {
             return nullptr;
           }
         }
       }
     }
   }
 
   mozAutoDocUpdate batch(GetComposedDoc(), true);
--- a/dom/base/nsINode.h
+++ b/dom/base/nsINode.h
@@ -1965,18 +1965,17 @@ protected:
   }
 
 #ifdef DEBUG
   // Note: virtual so that IsInNativeAnonymousSubtree can be called accross
   // module boundaries.
   virtual void CheckNotNativeAnonymous() const;
 #endif
 
-  void EnsurePreInsertionValidity1(nsINode& aNewChild, nsINode* aRefChild,
-                                   mozilla::ErrorResult& aError);
+  void EnsurePreInsertionValidity1(mozilla::ErrorResult& aError);
   void EnsurePreInsertionValidity2(bool aReplace, nsINode& aNewChild,
                                    nsINode* aRefChild,
                                    mozilla::ErrorResult& aError);
   nsINode* ReplaceOrInsertBefore(bool aReplace, nsINode* aNewChild,
                                  nsINode* aRefChild,
                                  mozilla::ErrorResult& aError);
 
   /**
--- a/gfx/2d/Swizzle.cpp
+++ b/gfx/2d/Swizzle.cpp
@@ -82,17 +82,17 @@ AlphaByteIndex(SurfaceFormat aFormat)
 
 // The endian-dependent bit shift to access RGB of a UINT32 pixel.
 static constexpr uint32_t
 RGBBitShift(SurfaceFormat aFormat)
 {
 #if MOZ_LITTLE_ENDIAN
   return 8 * RGBByteIndex(aFormat);
 #else
-  return 24 - 8 * RGBByteIndex(aFormat);
+  return 8 - 8 * RGBByteIndex(aFormat);
 #endif
 }
 
 // The endian-dependent bit shift to access alpha of a UINT32 pixel.
 static constexpr uint32_t
 AlphaBitShift(SurfaceFormat aFormat)
 {
   return (RGBBitShift(aFormat) + 24) % 32;
--- a/gfx/thebes/gfxPrefs.h
+++ b/gfx/thebes/gfxPrefs.h
@@ -540,17 +540,18 @@ private:
 #if defined(XP_MACOSX)
   DECL_GFX_PREF(Live, "gl.multithreaded",                      GLMultithreaded, bool, false);
 #endif
   DECL_GFX_PREF(Live, "gl.require-hardware",                   RequireHardwareGL, bool, false);
   DECL_GFX_PREF(Live, "gl.use-tls-is-current",                 UseTLSIsCurrent, int32_t, 0);
 
   DECL_GFX_PREF(Live, "image.animated.decode-on-demand.threshold-kb", ImageAnimatedDecodeOnDemandThresholdKB, uint32_t, 20480);
   DECL_GFX_PREF(Live, "image.animated.decode-on-demand.batch-size", ImageAnimatedDecodeOnDemandBatchSize, uint32_t, 6);
-  DECL_GFX_PREF(Live, "image.animated.generate-full-frames",   ImageAnimatedGenerateFullFrames, bool, false);
+  DECL_GFX_PREF(Live, "image.animated.decode-on-demand.recycle", ImageAnimatedDecodeOnDemandRecycle, bool, false);
+  DECL_GFX_PREF(Once, "image.animated.generate-full-frames",   ImageAnimatedGenerateFullFrames, bool, false);
   DECL_GFX_PREF(Live, "image.animated.resume-from-last-displayed", ImageAnimatedResumeFromLastDisplayed, bool, false);
   DECL_GFX_PREF(Live, "image.cache.factor2.threshold-surfaces", ImageCacheFactor2ThresholdSurfaces, int32_t, -1);
   DECL_GFX_PREF(Live, "image.cache.max-rasterized-svg-threshold-kb", ImageCacheMaxRasterizedSVGThresholdKB, int32_t, 90*1024);
   DECL_GFX_PREF(Once, "image.cache.size",                      ImageCacheSize, int32_t, 5*1024*1024);
   DECL_GFX_PREF(Once, "image.cache.timeweight",                ImageCacheTimeWeight, int32_t, 500);
   DECL_GFX_PREF(Live, "image.decode-immediately.enabled",      ImageDecodeImmediatelyEnabled, bool, false);
   DECL_GFX_PREF(Live, "image.downscale-during-decode.enabled", ImageDownscaleDuringDecodeEnabled, bool, true);
   DECL_GFX_PREF(Live, "image.infer-src-animation.threshold-ms", ImageInferSrcAnimationThresholdMS, uint32_t, 2000);
--- a/image/AnimationFrameBuffer.cpp
+++ b/image/AnimationFrameBuffer.cpp
@@ -4,51 +4,22 @@
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "AnimationFrameBuffer.h"
 #include "mozilla/Move.h"             // for Move
 
 namespace mozilla {
 namespace image {
 
-AnimationFrameBuffer::AnimationFrameBuffer()
-  : mThreshold(0)
-  , mBatch(0)
-  , mPending(0)
-  , mAdvance(0)
-  , mInsertIndex(0)
-  , mGetIndex(0)
-  , mSizeKnown(false)
-  , mRedecodeError(false)
-{ }
-
-void
-AnimationFrameBuffer::Initialize(size_t aThreshold,
-                                 size_t aBatch,
-                                 size_t aStartFrame)
+AnimationFrameRetainedBuffer::AnimationFrameRetainedBuffer(size_t aThreshold,
+                                                           size_t aBatch,
+                                                           size_t aStartFrame)
+  : AnimationFrameBuffer(aBatch, aStartFrame)
+  , mThreshold(aThreshold)
 {
-  MOZ_ASSERT(mThreshold == 0);
-  MOZ_ASSERT(mBatch == 0);
-  MOZ_ASSERT(mPending == 0);
-  MOZ_ASSERT(mAdvance == 0);
-  MOZ_ASSERT(mFrames.IsEmpty());
-
-  mThreshold = aThreshold;
-  mBatch = aBatch;
-  mAdvance = aStartFrame;
-
-  if (mBatch > SIZE_MAX/4) {
-    // Batch size is so big, we will just end up decoding the whole animation.
-    mBatch = SIZE_MAX/4;
-  } else if (mBatch < 1) {
-    // Never permit a batch size smaller than 1. We always want to be asking for
-    // at least one frame to start.
-    mBatch = 1;
-  }
-
   // To simplify the code, we have the assumption that the threshold for
   // entering discard-after-display mode is at least twice the batch size (since
   // that is the most frames-pending-decode we will request) + 1 for the current
   // frame. That way the redecoded frames being inserted will never risk
   // overlapping the frames we will discard due to the animation progressing.
   // That may cause us to use a little more memory than we want but that is an
   // acceptable tradeoff for simplicity.
   size_t minThreshold = 2 * mBatch + 1;
@@ -57,268 +28,405 @@ AnimationFrameBuffer::Initialize(size_t 
   }
 
   // The maximum number of frames we should ever have decoded at one time is
   // twice the batch. That is a good as number as any to start our decoding at.
   mPending = mBatch * 2;
 }
 
 bool
-AnimationFrameBuffer::Insert(RawAccessFrameRef&& aFrame)
+AnimationFrameRetainedBuffer::InsertInternal(RefPtr<imgFrame>&& aFrame)
 {
   // We should only insert new frames if we actually asked for them.
-  MOZ_ASSERT(mPending > 0);
-
-  if (mSizeKnown) {
-    // We only insert after the size is known if we are repeating the animation
-    // and we did not keep all of the frames. Replace whatever is there
-    // (probably an empty frame) with the new frame.
-    MOZ_ASSERT(MayDiscard());
+  MOZ_ASSERT(!mSizeKnown);
+  MOZ_ASSERT(mFrames.Length() < mThreshold);
 
-    // The first decode produced fewer frames than the redecodes, presumably
-    // because it hit an out-of-memory error which later attempts avoided. Just
-    // stop the animation because we can't tell the image that we have more
-    // frames now.
-    if (mInsertIndex >= mFrames.Length()) {
-      mRedecodeError = true;
-      mPending = 0;
-      return false;
-    }
+  mFrames.AppendElement(std::move(aFrame));
+  MOZ_ASSERT(mSize == mFrames.Length());
+  return mSize < mThreshold;
+}
 
-    if (mInsertIndex > 0) {
-      MOZ_ASSERT(!mFrames[mInsertIndex]);
-      mFrames[mInsertIndex] = std::move(aFrame);
-    }
-  } else if (mInsertIndex == mFrames.Length()) {
-    // We are still on the first pass of the animation decoding, so this is
-    // the first time we have seen this frame.
-    mFrames.AppendElement(std::move(aFrame));
-
-    if (mInsertIndex == mThreshold) {
-      // We just tripped over the threshold for the first time. This is our
-      // chance to do any clearing of already displayed frames. After this,
-      // we only need to release as we advance or force a restart.
-      MOZ_ASSERT(MayDiscard());
-      MOZ_ASSERT(mGetIndex < mInsertIndex);
-      for (size_t i = 1; i < mGetIndex; ++i) {
-        RawAccessFrameRef discard = std::move(mFrames[i]);
-      }
-    }
-  } else if (mInsertIndex > 0) {
-    // We were forced to restart an animation before we decoded the last
-    // frame. If we were discarding frames, then we tossed what we had
-    // except for the first frame.
-    MOZ_ASSERT(mInsertIndex < mFrames.Length());
-    MOZ_ASSERT(!mFrames[mInsertIndex]);
-    MOZ_ASSERT(MayDiscard());
-    mFrames[mInsertIndex] = std::move(aFrame);
-  } else { // mInsertIndex == 0
-    // We were forced to restart an animation before we decoded the last
-    // frame. We don't need the redecoded first frame because we always keep
-    // the original.
-    MOZ_ASSERT(MayDiscard());
+bool
+AnimationFrameRetainedBuffer::ResetInternal()
+{
+  // If we haven't crossed the threshold, then we know by definition we have
+  // not discarded any frames. If we previously requested more frames, but
+  // it would have been more than we would have buffered otherwise, we can
+  // stop the decoding after one more frame.
+  if (mPending > 1 && mSize >= mBatch * 2 + 1) {
+    MOZ_ASSERT(!mSizeKnown);
+    mPending = 1;
   }
 
-  MOZ_ASSERT(mFrames[mInsertIndex]);
-  ++mInsertIndex;
-
-  // Ensure we only request more decoded frames if we actually need them. If we
-  // need to advance to a certain point in the animation on behalf of the owner,
-  // then do so. This ensures we keep decoding. If the batch size is really
-  // small (i.e. 1), it is possible advancing will request the decoder to
-  // "restart", but we haven't told it to stop yet. Note that we skip the first
-  // insert because we actually start "advanced" to the first frame anyways.
-  bool continueDecoding = --mPending > 0;
-  if (mAdvance > 0 && mInsertIndex > 1) {
-    continueDecoding |= AdvanceInternal();
-    --mAdvance;
-  }
-  return continueDecoding;
+  // Either the decoder is still running, or we have enough frames already.
+  // No need for us to restart it.
+  return false;
 }
 
 bool
-AnimationFrameBuffer::MarkComplete()
+AnimationFrameRetainedBuffer::MarkComplete(const gfx::IntRect& aFirstFrameRefreshArea)
+{
+  MOZ_ASSERT(!mSizeKnown);
+  mSizeKnown = true;
+  mPending = 0;
+  mFrames.Compact();
+  return false;
+}
+
+void
+AnimationFrameRetainedBuffer::AdvanceInternal()
 {
-  // We may have stopped decoding at a different point in the animation than we
-  // did previously. That means the decoder likely hit a new error, e.g. OOM.
-  // This will prevent us from advancing as well, because we are missing the
-  // required frames to blend.
-  //
-  // XXX(aosmond): In an ideal world, we would be generating full frames, and
-  // the consumer of our data doesn't care about our internal state. It simply
-  // knows about the first frame, the current frame, and how long to display the
-  // current frame.
-  if (NS_WARN_IF(mInsertIndex != mFrames.Length())) {
-    MOZ_ASSERT(mSizeKnown);
-    mRedecodeError = true;
-    mPending = 0;
-  }
-
-  // We reached the end of the animation, the next frame we get, if we get
-  // another, will be the first frame again.
-  mInsertIndex = 0;
-
-  // Since we only request advancing when we want to resume at a certain point
-  // in the animation, we should never exceed the number of frames.
-  MOZ_ASSERT(mAdvance == 0);
+  // We should not have advanced if we never inserted.
+  MOZ_ASSERT(!mFrames.IsEmpty());
+  // We only want to change the current frame index if we have advanced. This
+  // means either a higher frame index, or going back to the beginning.
+  size_t framesLength = mFrames.Length();
+  // We should never have advanced beyond the frame buffer.
+  MOZ_ASSERT(mGetIndex < framesLength);
+  // We should never advance if the current frame is null -- it needs to know
+  // the timeout from it at least to know when to advance.
+  MOZ_ASSERT_IF(mGetIndex > 0, mFrames[mGetIndex - 1]);
+  MOZ_ASSERT_IF(mGetIndex == 0, mFrames[framesLength - 1]);
+  // The owner should have already accessed the next frame, so it should also
+  // be available.
+  MOZ_ASSERT(mFrames[mGetIndex]);
 
   if (!mSizeKnown) {
-    // We just received the last frame in the animation. Compact the frame array
-    // because we know we won't need to grow beyond here.
-    mSizeKnown = true;
-    mFrames.Compact();
-
-    if (!MayDiscard()) {
-      // If we did not meet the threshold, then we know we want to keep all of the
-      // frames. If we also hit the last frame, we don't want to ask for more.
-      mPending = 0;
+    // Calculate how many frames we have requested ahead of the current frame.
+    size_t buffered = mPending + framesLength - mGetIndex - 1;
+    if (buffered < mBatch) {
+      // If we have fewer frames than the batch size, then ask for more. If we
+      // do not have any pending, then we know that there is no active decoding.
+      mPending += mBatch;
     }
   }
-
-  return mPending > 0;
 }
 
 imgFrame*
-AnimationFrameBuffer::Get(size_t aFrame)
+AnimationFrameRetainedBuffer::Get(size_t aFrame, bool aForDisplay)
 {
   // We should not have asked for a frame if we never inserted.
   if (mFrames.IsEmpty()) {
     MOZ_ASSERT_UNREACHABLE("Calling Get() when we have no frames");
     return nullptr;
   }
 
   // If we don't have that frame, return an empty frame ref.
   if (aFrame >= mFrames.Length()) {
     return nullptr;
   }
 
-  // We've got the requested frame because we are not discarding frames. While
-  // we typically should have not run out of frames since we ask for more before
-  // we want them, it is possible the decoder is behind.
+  // If we have space for the frame, it should always be available.
   if (!mFrames[aFrame]) {
-    MOZ_ASSERT(MayDiscard());
+    MOZ_ASSERT_UNREACHABLE("Calling Get() when frame is unavailable");
     return nullptr;
   }
 
   // If we are advancing on behalf of the animation, we don't expect it to be
   // getting any frames (besides the first) until we get the desired frame.
   MOZ_ASSERT(aFrame == 0 || mAdvance == 0);
   return mFrames[aFrame].get();
 }
 
 bool
-AnimationFrameBuffer::AdvanceTo(size_t aExpectedFrame)
+AnimationFrameRetainedBuffer::IsFirstFrameFinished() const
 {
-  // The owner should only be advancing once it has reached the requested frame
-  // in the animation.
-  MOZ_ASSERT(mAdvance == 0);
-  bool restartDecoder = AdvanceInternal();
-  // Advancing should always be successful, as it should only happen after the
-  // owner has accessed the next (now current) frame.
-  MOZ_ASSERT(mGetIndex == aExpectedFrame);
-  return restartDecoder;
+  return !mFrames.IsEmpty() && mFrames[0]->IsFinished();
 }
 
 bool
-AnimationFrameBuffer::AdvanceInternal()
+AnimationFrameRetainedBuffer::IsLastInsertedFrame(imgFrame* aFrame) const
 {
-  // We should not have advanced if we never inserted.
-  if (mFrames.IsEmpty()) {
-    MOZ_ASSERT_UNREACHABLE("Calling Advance() when we have no frames");
-    return false;
-  }
-
-  // We only want to change the current frame index if we have advanced. This
-  // means either a higher frame index, or going back to the beginning.
-  size_t framesLength = mFrames.Length();
-  // We should never have advanced beyond the frame buffer.
-  MOZ_ASSERT(mGetIndex < framesLength);
-  // We should never advance if the current frame is null -- it needs to know
-  // the timeout from it at least to know when to advance.
-  MOZ_ASSERT(mFrames[mGetIndex]);
-  if (++mGetIndex == framesLength) {
-    MOZ_ASSERT(mSizeKnown);
-    mGetIndex = 0;
-  }
-  // The owner should have already accessed the next frame, so it should also
-  // be available.
-  MOZ_ASSERT(mFrames[mGetIndex]);
+  return !mFrames.IsEmpty() && mFrames.LastElement().get() == aFrame;
+}
 
-  // If we moved forward, that means we can remove the previous frame, assuming
-  // that frame is not the first frame. If we looped and are back at the first
-  // frame, we can remove the last frame.
-  if (MayDiscard()) {
-    RawAccessFrameRef discard;
-    if (mGetIndex > 1) {
-      discard = std::move(mFrames[mGetIndex - 1]);
-    } else if (mGetIndex == 0) {
-      MOZ_ASSERT(mSizeKnown && framesLength > 1);
-      discard = std::move(mFrames[framesLength - 1]);
-    }
+void
+AnimationFrameRetainedBuffer::AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                                                     const AddSizeOfCb& aCallback)
+{
+  size_t i = 0;
+  for (const RefPtr<imgFrame>& frame : mFrames) {
+    ++i;
+    frame->AddSizeOfExcludingThis(aMallocSizeOf,
+      [&](AddSizeOfCbData& aMetadata) {
+        aMetadata.index = i;
+        aCallback(aMetadata);
+      }
+    );
   }
+}
 
-  if (!mRedecodeError && (!mSizeKnown || MayDiscard())) {
-    // Calculate how many frames we have requested ahead of the current frame.
-    size_t buffered = mPending;
-    if (mGetIndex > mInsertIndex) {
-      // It wrapped around and we are decoding the beginning again before the
-      // the display has finished the loop.
-      MOZ_ASSERT(mSizeKnown);
-      buffered += mInsertIndex + framesLength - mGetIndex - 1;
-    } else {
-      buffered += mInsertIndex - mGetIndex - 1;
-    }
+AnimationFrameDiscardingQueue::AnimationFrameDiscardingQueue(AnimationFrameRetainedBuffer&& aQueue)
+  : AnimationFrameBuffer(aQueue)
+  , mInsertIndex(aQueue.mFrames.Length())
+  , mFirstFrame(std::move(aQueue.mFrames[0]))
+{
+  MOZ_ASSERT(!mSizeKnown);
+  MOZ_ASSERT(!mRedecodeError);
+  MOZ_ASSERT(mInsertIndex > 0);
+  MOZ_ASSERT(mGetIndex > 0);
+  mMayDiscard = true;
 
-    if (buffered < mBatch) {
-      // If we have fewer frames than the batch size, then ask for more. If we
-      // do not have any pending, then we know that there is no active decoding.
-      mPending += mBatch;
-      return mPending == mBatch;
-    }
+  for (size_t i = aQueue.mGetIndex; i < mInsertIndex; ++i) {
+    MOZ_ASSERT(aQueue.mFrames[i]);
+    mDisplay.push_back(std::move(aQueue.mFrames[i]));
   }
-
-  return false;
 }
 
 bool
-AnimationFrameBuffer::Reset()
+AnimationFrameDiscardingQueue::InsertInternal(RefPtr<imgFrame>&& aFrame)
 {
-  // The animation needs to start back at the beginning.
-  mGetIndex = 0;
-  mAdvance = 0;
-
-  if (!MayDiscard()) {
-    // If we haven't crossed the threshold, then we know by definition we have
-    // not discarded any frames. If we previously requested more frames, but
-    // it would have been more than we would have buffered otherwise, we can
-    // stop the decoding after one more frame.
-    if (mPending > 1 && mInsertIndex - 1 >= mBatch * 2) {
-      MOZ_ASSERT(!mSizeKnown);
-      mPending = 1;
-    }
+  // Even though we don't use redecoded first frames for display purposes, we
+  // will still use them for recycling, so we still need to insert it.
+  mDisplay.push_back(std::move(aFrame));
+  ++mInsertIndex;
+  MOZ_ASSERT(mInsertIndex <= mSize);
+  return true;
+}
 
-    // Either the decoder is still running, or we have enough frames already.
-    // No need for us to restart it.
-    return false;
-  }
-
-  // Discard all frames besides the first, because the decoder always expects
-  // that when it re-inserts a frame, it is not present. (It doesn't re-insert
-  // the first frame.)
-  for (size_t i = 1; i < mFrames.Length(); ++i) {
-    RawAccessFrameRef discard = std::move(mFrames[i]);
-  }
-
+bool
+AnimationFrameDiscardingQueue::ResetInternal()
+{
+  mDisplay.clear();
   mInsertIndex = 0;
 
-  // If we hit an error after redecoding, we never want to restart decoding.
-  if (mRedecodeError) {
-    MOZ_ASSERT(mPending == 0);
-    return false;
-  }
-
   bool restartDecoder = mPending == 0;
   mPending = 2 * mBatch;
   return restartDecoder;
 }
 
+bool
+AnimationFrameDiscardingQueue::MarkComplete(const gfx::IntRect& aFirstFrameRefreshArea)
+{
+  if (NS_WARN_IF(mInsertIndex != mSize)) {
+    MOZ_ASSERT(mSizeKnown);
+    mRedecodeError = true;
+    mPending = 0;
+  }
+
+  // We reached the end of the animation, the next frame we get, if we get
+  // another, will be the first frame again.
+  mInsertIndex = 0;
+  mSizeKnown = true;
+
+  // Since we only request advancing when we want to resume at a certain point
+  // in the animation, we should never exceed the number of frames.
+  MOZ_ASSERT(mAdvance == 0);
+  return mPending > 0;
+}
+
+void
+AnimationFrameDiscardingQueue::AdvanceInternal()
+{
+  // We only want to change the current frame index if we have advanced. This
+  // means either a higher frame index, or going back to the beginning.
+  // We should never have advanced beyond the frame buffer.
+  MOZ_ASSERT(mGetIndex < mSize);
+
+  // Unless we are recycling, we should have the current frame still in the
+  // display queue. Either way, we should at least have an entry in the queue
+  // which we need to consume.
+  MOZ_ASSERT(mRecycling || bool(mDisplay.front()));
+  MOZ_ASSERT(!mDisplay.empty());
+  mDisplay.pop_front();
+  MOZ_ASSERT(!mDisplay.empty());
+  MOZ_ASSERT(mDisplay.front());
+
+  if (mDisplay.size() + mPending - 1 < mBatch) {
+    // If we have fewer frames than the batch size, then ask for more. If we
+    // do not have any pending, then we know that there is no active decoding.
+    mPending += mBatch;
+  }
+}
+
+imgFrame*
+AnimationFrameDiscardingQueue::Get(size_t aFrame, bool aForDisplay)
+{
+  // If we are advancing on behalf of the animation, we don't expect it to be
+  // getting any frames (besides the first) until we get the desired frame.
+  MOZ_ASSERT(aFrame == 0 || mAdvance == 0);
+
+  // The first frame is stored separately. If we only need the frame for
+  // display purposes, we can return it right away. If we need it for advancing
+  // the animation, we want to verify the recreated first frame is available
+  // before allowing it continue.
+  if (aForDisplay && aFrame == 0) {
+    return mFirstFrame.get();
+  }
+
+  // If we don't have that frame, return an empty frame ref.
+  if (aFrame >= mSize) {
+    return nullptr;
+  }
+
+  size_t offset;
+  if (aFrame >= mGetIndex) {
+    offset = aFrame - mGetIndex;
+  } else if (!mSizeKnown) {
+    MOZ_ASSERT_UNREACHABLE("Requesting previous frame after we have advanced!");
+    return nullptr;
+  } else {
+    offset = mSize - mGetIndex + aFrame;
+  }
+
+  if (offset >= mDisplay.size()) {
+    return nullptr;
+  }
+
+  // If we have space for the frame, it should always be available.
+  MOZ_ASSERT(mDisplay[offset]);
+  return mDisplay[offset].get();
+}
+
+bool
+AnimationFrameDiscardingQueue::IsFirstFrameFinished() const
+{
+  MOZ_ASSERT(mFirstFrame);
+  MOZ_ASSERT(mFirstFrame->IsFinished());
+  return true;
+}
+
+bool
+AnimationFrameDiscardingQueue::IsLastInsertedFrame(imgFrame* aFrame) const
+{
+  return !mDisplay.empty() && mDisplay.back().get() == aFrame;
+}
+
+void
+AnimationFrameDiscardingQueue::AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                                                      const AddSizeOfCb& aCallback)
+{
+  mFirstFrame->AddSizeOfExcludingThis(aMallocSizeOf,
+    [&](AddSizeOfCbData& aMetadata) {
+      aMetadata.index = 1;
+      aCallback(aMetadata);
+    }
+  );
+
+  size_t i = mGetIndex;
+  for (const RefPtr<imgFrame>& frame : mDisplay) {
+    ++i;
+    if (mSize < i) {
+      // First frame again, we already covered it above.
+      MOZ_ASSERT(mFirstFrame.get() == frame.get());
+      i = 1;
+      continue;
+    }
+
+    frame->AddSizeOfExcludingThis(aMallocSizeOf,
+      [&](AddSizeOfCbData& aMetadata) {
+        aMetadata.index = i;
+        aCallback(aMetadata);
+      }
+    );
+  }
+}
+
+AnimationFrameRecyclingQueue::AnimationFrameRecyclingQueue(AnimationFrameRetainedBuffer&& aQueue)
+  : AnimationFrameDiscardingQueue(std::move(aQueue))
+{
+  // In an ideal world, we would always save the already displayed frames for
+  // recycling but none of the frames were marked as recyclable. We will incur
+  // the extra allocation cost for a few more frames.
+  mRecycling = true;
+}
+
+void
+AnimationFrameRecyclingQueue::AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                                                     const AddSizeOfCb& aCallback)
+{
+  AnimationFrameDiscardingQueue::AddSizeOfExcludingThis(aMallocSizeOf,
+                                                        aCallback);
+
+  for (const RecycleEntry& entry : mRecycle) {
+    if (entry.mFrame) {
+      entry.mFrame->AddSizeOfExcludingThis(aMallocSizeOf,
+        [&](AddSizeOfCbData& aMetadata) {
+          aMetadata.index = 0; // Frame is not applicable
+          aCallback(aMetadata);
+        }
+      );
+    }
+  }
+}
+
+void
+AnimationFrameRecyclingQueue::AdvanceInternal()
+{
+  MOZ_ASSERT(!mDisplay.empty());
+  MOZ_ASSERT(mDisplay.front());
+
+  RefPtr<imgFrame>& front = mDisplay.front();
+
+  // The first frame should always have a dirty rect that matches the frame
+  // rect. As such, we should use mFirstFrameRefreshArea instead for recycle
+  // rect calculations.
+  MOZ_ASSERT_IF(mGetIndex == 1,
+                front->GetRect().IsEqualEdges(front->GetDirtyRect()));
+
+  RecycleEntry newEntry(mGetIndex == 1 ? mFirstFrameRefreshArea
+                                       : front->GetDirtyRect());
+
+  // If we are allowed to recycle the frame, then we should save it before the
+  // base class's AdvanceInternal discards it.
+  if (front->ShouldRecycle()) {
+    // Calculate the recycle rect for the recycled frame. This is the cumulative
+    // dirty rect of all of the frames ahead of us to be displayed, and to be
+    // used for recycling. Or in other words, the dirty rect between the
+    // recycled frame and the decoded frame which reuses the buffer.
+    for (const RefPtr<imgFrame>& frame : mDisplay) {
+      newEntry.mRecycleRect = newEntry.mRecycleRect.Union(frame->GetDirtyRect());
+    }
+    for (const RecycleEntry& entry : mRecycle) {
+      newEntry.mRecycleRect = newEntry.mRecycleRect.Union(entry.mDirtyRect);
+    }
+
+    newEntry.mFrame = std::move(front);
+  }
+
+  // Even if the frame itself isn't saved, we want the dirty rect to calculate
+  // the recycle rect for future recycled frames.
+  mRecycle.push_back(std::move(newEntry));
+  AnimationFrameDiscardingQueue::AdvanceInternal();
+}
+
+bool
+AnimationFrameRecyclingQueue::ResetInternal()
+{
+  mRecycle.clear();
+  return AnimationFrameDiscardingQueue::ResetInternal();
+}
+
+RawAccessFrameRef
+AnimationFrameRecyclingQueue::RecycleFrame(gfx::IntRect& aRecycleRect)
+{
+  if (mRecycle.empty()) {
+    return RawAccessFrameRef();
+  }
+
+  RawAccessFrameRef frame;
+  if (mRecycle.front().mFrame) {
+    frame = mRecycle.front().mFrame->RawAccessRef();
+    if (frame) {
+      aRecycleRect = mRecycle.front().mRecycleRect;
+    }
+  }
+
+  mRecycle.pop_front();
+  return frame;
+}
+
+bool
+AnimationFrameRecyclingQueue::MarkComplete(const gfx::IntRect& aFirstFrameRefreshArea)
+{
+  bool continueDecoding =
+    AnimationFrameDiscardingQueue::MarkComplete(aFirstFrameRefreshArea);
+
+  MOZ_ASSERT_IF(!mRedecodeError,
+                mFirstFrameRefreshArea.IsEmpty() ||
+                mFirstFrameRefreshArea.IsEqualEdges(aFirstFrameRefreshArea));
+
+  mFirstFrameRefreshArea = aFirstFrameRefreshArea;
+  return continueDecoding;
+}
+
 } // namespace image
 } // namespace mozilla
--- a/image/AnimationFrameBuffer.h
+++ b/image/AnimationFrameBuffer.h
@@ -2,139 +2,119 @@
 /* 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 mozilla_image_AnimationFrameBuffer_h
 #define mozilla_image_AnimationFrameBuffer_h
 
 #include "ISurfaceProvider.h"
+#include <deque>
 
 namespace mozilla {
 namespace image {
 
 /**
  * An AnimationFrameBuffer owns the frames outputted by an animated image
  * decoder as well as directing its owner on how to drive the decoder,
  * whether to produce more or to stop.
  *
- * Based upon its given configuration parameters, it will retain up to a
- * certain number of frames in the buffer before deciding to discard previous
- * frames, and relying upon the decoder to recreate older frames when the
- * animation loops. It will also request that the decoder stop producing more
- * frames when the display of the frames are far behind -- this allows other
- * tasks and images which require decoding to take execution priority.
- *
- * The desire is that smaller animated images should be kept completely in
- * memory while larger animated images should only keep a certain number of
- * frames to minimize our memory footprint at the cost of CPU.
+ * This should be subclassed by the different types of queues, depending on
+ * what behaviour is desired.
  */
-class AnimationFrameBuffer final
+class AnimationFrameBuffer
 {
 public:
-  AnimationFrameBuffer();
+  enum class InsertStatus : uint8_t
+  {
+    YIELD, // No more frames required at this time.
+    CONTINUE, // Continue decoding more frames.
+    DISCARD_YIELD, // Crossed threshold, switch to discarding structure
+                   // and stop decoding more frames.
+    DISCARD_CONTINUE // Crossed threshold, switch to discarding structure
+                     // and continue decoding more frames.
+  };
 
   /**
-   * Configure the frame buffer with a particular threshold and batch size. Note
-   * that the frame buffer may adjust the given values.
-   *
-   * @param aThreshold  Maximum number of frames that may be stored in the frame
-   *                    buffer before it may discard already displayed frames.
-   *                    Once exceeded, it will discard the previous frame to the
-   *                    current frame whenever Advance is called. It always
-   *                    retains the first frame.
-   *
    * @param aBatch      Number of frames we request to be decoded each time it
    *                    decides we need more.
    *
    * @param aStartFrame The starting frame for the animation. The frame buffer
    *                    will auto-advance (and thus keep the decoding pipeline
    *                    going) until it has reached this frame. Useful when the
    *                    animation was progressing, but the surface was
    *                    discarded, and we had to redecode.
    */
-  void Initialize(size_t aThreshold, size_t aBatch, size_t aStartFrame);
-
-  /**
-   * Access a specific frame from the frame buffer. It should generally access
-   * frames in sequential order, increasing in tandem with AdvanceTo calls. The
-   * first frame may be accessed at any time. The access order should start with
-   * the same value as that given in Initialize (aStartFrame).
-   *
-   * @param aFrame      The frame index to access.
-   *
-   * @returns The frame, if available.
-   */
-  imgFrame* Get(size_t aFrame);
-
-  /**
-   * Inserts a frame into the frame buffer. If it has yet to fully decode the
-   * animated image yet, then it will append the frame to its internal buffer.
-   * If it has been fully decoded, it will replace the next frame in its buffer
-   * with the given frame.
-   *
-   * Once we have a sufficient number of frames buffered relative to the
-   * currently displayed frame, it will return false to indicate the caller
-   * should stop decoding.
-   *
-   * @param aFrame      The frame to insert into the buffer.
-   *
-   * @returns True if the decoder should decode another frame.
-   */
-  bool Insert(RawAccessFrameRef&& aFrame);
+  AnimationFrameBuffer(size_t aBatch, size_t aStartFrame)
+    : mSize(0)
+    , mBatch(aBatch)
+    , mGetIndex(0)
+    , mAdvance(aStartFrame)
+    , mPending(0)
+    , mSizeKnown(false)
+    , mMayDiscard(false)
+    , mRedecodeError(false)
+    , mRecycling(false)
+  {
+    if (mBatch > SIZE_MAX/4) {
+      // Batch size is so big, we will just end up decoding the whole animation.
+      mBatch = SIZE_MAX/4;
+    } else if (mBatch < 1) {
+      // Never permit a batch size smaller than 1. We always want to be asking
+      // for at least one frame to start.
+      mBatch = 1;
+    }
+  }
 
-  /**
-   * This should be called after the last frame has been inserted. If the buffer
-   * is discarding old frames, it may request more frames to be decoded. In this
-   * case that means the decoder should start again from the beginning. This
-   * return value should be used in preference to that of the Insert call.
-   *
-   * @returns True if the decoder should decode another frame.
-   */
-  bool MarkComplete();
+  AnimationFrameBuffer(const AnimationFrameBuffer& aOther)
+    : mSize(aOther.mSize)
+    , mBatch(aOther.mBatch)
+    , mGetIndex(aOther.mGetIndex)
+    , mAdvance(aOther.mAdvance)
+    , mPending(aOther.mPending)
+    , mSizeKnown(aOther.mSizeKnown)
+    , mMayDiscard(aOther.mMayDiscard)
+    , mRedecodeError(aOther.mRedecodeError)
+    , mRecycling(aOther.mRecycling)
+  { }
 
-  /**
-   * Advance the currently displayed frame of the frame buffer. If it reaches
-   * the end, it will loop back to the beginning. It should not be called unless
-   * a call to Get has returned a valid frame for the next frame index.
-   *
-   * As we advance, the number of frames we have buffered ahead of the current
-   * will shrink. Once that becomes too few, we will request a batch-sized set
-   * of frames to be decoded from the decoder.
-   *
-   * @param aExpectedFrame  The frame we expect to have advanced to. This is
-   *                        used for confirmation purposes (e.g. asserts).
-   *
-   * @returns True if the caller should restart the decoder.
-   */
-  bool AdvanceTo(size_t aExpectedFrame);
-
-  /**
-   * Resets the currently displayed frame of the frame buffer to the beginning.
-   * If the buffer is discarding old frames, it will actually discard all frames
-   * besides the first.
-   *
-   * @returns True if the caller should restart the decoder.
-   */
-  bool Reset();
+  virtual ~AnimationFrameBuffer()
+  { }
 
   /**
    * @returns True if frames post-advance may be discarded and redecoded on
    *          demand, else false.
    */
-  bool MayDiscard() const { return mFrames.Length() > mThreshold; }
+  bool MayDiscard() const { return mMayDiscard; }
+
+  /**
+   * @returns True if frames post-advance may be reused after displaying, else
+   *          false. Implies MayDiscard().
+   */
+  bool IsRecycling() const
+  {
+    MOZ_ASSERT_IF(mRecycling, mMayDiscard);
+    return mRecycling;
+  }
 
   /**
    * @returns True if the frame buffer was ever marked as complete. This implies
    *          that the total number of frames is known and may be gotten from
    *          Frames().Length().
    */
   bool SizeKnown() const { return mSizeKnown; }
 
   /**
+   * @returns The total number of frames in the animation. If SizeKnown() is
+   *          true, then this is a constant, else it is just the total number of
+   *          frames we have decoded thus far.
+   */
+  size_t Size() const { return mSize; }
+
+  /**
    * @returns True if encountered an error during redecode which should cause
    *          the caller to stop inserting frames.
    */
   bool HasRedecodeError() const { return mRedecodeError; }
 
   /**
    * @returns The current frame index we have advanced to.
    */
@@ -152,53 +132,365 @@ public:
 
   /**
    * @returns Number of frames we request to be decoded each time it decides we
    *          need more.
    */
   size_t Batch() const { return mBatch; }
 
   /**
+   * Resets the currently displayed frame of the frame buffer to the beginning.
+   *
+   * @returns True if the caller should restart the decoder.
+   */
+  bool Reset()
+  {
+    mGetIndex = 0;
+    mAdvance = 0;
+    return ResetInternal();
+  }
+
+  /**
+   * Advance the currently displayed frame of the frame buffer. If it reaches
+   * the end, it will loop back to the beginning. It should not be called unless
+   * a call to Get has returned a valid frame for the next frame index.
+   *
+   * As we advance, the number of frames we have buffered ahead of the current
+   * will shrink. Once that becomes too few, we will request a batch-sized set
+   * of frames to be decoded from the decoder.
+   *
+   * @param aExpectedFrame  The frame we expect to have advanced to. This is
+   *                        used for confirmation purposes (e.g. asserts).
+   *
+   * @returns True if the caller should restart the decoder.
+   */
+  bool AdvanceTo(size_t aExpectedFrame)
+  {
+    MOZ_ASSERT(mAdvance == 0);
+
+    if (++mGetIndex == mSize && mSizeKnown) {
+      mGetIndex = 0;
+    }
+    MOZ_ASSERT(mGetIndex == aExpectedFrame);
+
+    bool hasPending = mPending > 0;
+    AdvanceInternal();
+    // Restart the decoder if we transitioned from no pending frames being
+    // decoded, to some pending frames to be decoded.
+    return !hasPending && mPending > 0;
+  }
+
+  /**
+   * Inserts a frame into the frame buffer.
+   *
+   * Once we have a sufficient number of frames buffered relative to the
+   * currently displayed frame, it will return YIELD to indicate the caller
+   * should stop decoding. Otherwise it will return CONTINUE.
+   *
+   * If we cross the threshold, it will return DISCARD_YIELD or DISCARD_CONTINUE
+   * to indicate that the caller should switch to a new queue type.
+   *
+   * @param aFrame      The frame to insert into the buffer.
+   *
+   * @returns True if the decoder should decode another frame.
+   */
+  InsertStatus Insert(RefPtr<imgFrame>&& aFrame)
+  {
+    MOZ_ASSERT(mPending > 0);
+    MOZ_ASSERT(aFrame);
+
+    --mPending;
+    if (!mSizeKnown) {
+      ++mSize;
+    }
+
+    bool retain = InsertInternal(std::move(aFrame));
+
+    if (mAdvance > 0 && mSize > 1) {
+      --mAdvance;
+      ++mGetIndex;
+      AdvanceInternal();
+    }
+
+    if (!retain) {
+      return mPending > 0 ? InsertStatus::DISCARD_CONTINUE
+                          : InsertStatus::DISCARD_YIELD;
+    }
+
+    return mPending > 0 ? InsertStatus::CONTINUE : InsertStatus::YIELD;
+  }
+
+  /**
+   * Access a specific frame from the frame buffer. It should generally access
+   * frames in sequential order, increasing in tandem with AdvanceTo calls. The
+   * first frame may be accessed at any time. The access order should start with
+   * the same value as that given in Initialize (aStartFrame).
+   *
+   * @param aFrame      The frame index to access.
+   *
+   * @returns The frame, if available.
+   */
+  virtual imgFrame* Get(size_t aFrame, bool aForDisplay) = 0;
+
+  /**
+   * @returns True if the first frame of the animation (not of the queue) is
+   *          available/finished, else false.
+   */
+  virtual bool IsFirstFrameFinished() const = 0;
+
+  /**
+   * @returns True if the last inserted frame matches the given frame, else
+   *          false.
+   */
+  virtual bool IsLastInsertedFrame(imgFrame* aFrame) const = 0;
+
+  /**
+   * This should be called after the last frame has been inserted. If the buffer
+   * is discarding old frames, it may request more frames to be decoded. In this
+   * case that means the decoder should start again from the beginning. This
+   * return value should be used in preference to that of the Insert call.
+   *
+   * @returns True if the decoder should decode another frame.
+   */
+  virtual bool MarkComplete(const gfx::IntRect& aFirstFrameRefreshArea) = 0;
+
+  typedef ISurfaceProvider::AddSizeOfCbData AddSizeOfCbData;
+  typedef ISurfaceProvider::AddSizeOfCb AddSizeOfCb;
+
+  /**
+   * Accumulate the total cost of all the frames in the buffer.
+   */
+  virtual void AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                                      const AddSizeOfCb& aCallback) = 0;
+
+  /**
+   * Request a recycled frame buffer, and if available, set aRecycleRect to be
+   * the dirty rect between the contents of the recycled frame, and the restore
+   * frame (e.g. what we composite on top of) for the next frame to be created.
+   *
+   * @returns The frame to be recycled, if available.
+   */
+  virtual RawAccessFrameRef RecycleFrame(gfx::IntRect& aRecycleRect)
+  {
+    MOZ_ASSERT(!mRecycling);
+    return RawAccessFrameRef();
+  }
+
+protected:
+  /**
+   * Perform the actual insertion of the given frame into the underlying buffer
+   * representation. mGetIndex shall be the index of the frame we are inserting,
+   * and mSize and mPending have already been adjusted as needed.
+   *
+   * @returns True if the caller should continue as normal, false if the discard
+   *          threshold was crossed and we should change queue types.
+   */
+  virtual bool InsertInternal(RefPtr<imgFrame>&& aFrame) = 0;
+
+  /**
+   * Advance from the current frame to the immediately adjacent next frame.
+   * mGetIndex shall be the the index of the new current frame after advancing.
+   * mPending may be adjusted to request more frames.
+   */
+  virtual void AdvanceInternal() = 0;
+
+  /**
+   * Discard any frames as necessary for the reset. mPending may be adjusted to
+   * request more frames.
+   *
+   * @returns True if the caller should resume decoding new frames, else false.
+   */
+  virtual bool ResetInternal() = 0;
+
+  // The total number of frames in the animation. If mSizeKnown is true, it is
+  // the actual total regardless of how many frames are available, otherwise it
+  // is the total number of inserted frames.
+  size_t mSize;
+
+  // The minimum number of frames that we want buffered ahead of the display.
+  size_t mBatch;
+
+  // The sequential index of the frame we have advanced to.
+  size_t mGetIndex;
+
+  // The number of frames we need to auto-advance to synchronize with the caller.
+  size_t mAdvance;
+
+  // The number of frames to decode before we stop.
+  size_t mPending;
+
+  // True if the total number of frames for the animation is known.
+  bool mSizeKnown;
+
+  // True if this buffer may discard frames.
+  bool mMayDiscard;
+
+  // True if we encountered an error while redecoding.
+  bool mRedecodeError;
+
+  // True if this buffer is recycling frames.
+  bool mRecycling;
+};
+
+/**
+ * An AnimationFrameRetainedBuffer will retain all of the frames inserted into
+ * it. Once it crosses its maximum number of frames, it will recommend
+ * conversion to a discarding queue.
+ */
+class AnimationFrameRetainedBuffer final : public AnimationFrameBuffer
+{
+public:
+
+  /**
+   * @param aThreshold  Maximum number of frames that may be stored in the frame
+   *                    buffer before it may discard already displayed frames.
+   *                    Once exceeded, it will discard the previous frame to the
+   *                    current frame whenever Advance is called. It always
+   *                    retains the first frame.
+   *
+   * @param aBatch      See AnimationFrameBuffer::AnimationFrameBuffer.
+   *
+   * @param aStartFrame See AnimationFrameBuffer::AnimationFrameBuffer.
+   */
+  AnimationFrameRetainedBuffer(size_t aThreshold, size_t aBatch, size_t aCurrentFrame);
+
+  /**
    * @returns Maximum number of frames before we start discarding previous
    *          frames post-advance.
    */
   size_t Threshold() const { return mThreshold; }
 
   /**
-   * @returns The frames of this animation, in order. May contain empty indices.
+   * @returns The frames of this animation, in order. Each element will always
+   *          contain a valid frame.
    */
-  const nsTArray<RawAccessFrameRef>& Frames() const { return mFrames; }
+  const nsTArray<RefPtr<imgFrame>>& Frames() const { return mFrames; }
+
+  imgFrame* Get(size_t aFrame, bool aForDisplay) override;
+  bool IsFirstFrameFinished() const override;
+  bool IsLastInsertedFrame(imgFrame* aFrame) const override;
+  bool MarkComplete(const gfx::IntRect& aFirstFrameRefreshArea) override;
+  void AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                              const AddSizeOfCb& aCallback) override;
 
 private:
-  bool AdvanceInternal();
+  friend class AnimationFrameDiscardingQueue;
+  friend class AnimationFrameRecyclingQueue;
 
-  /// The frames of this animation, in order, but may have holes if discarding.
-  nsTArray<RawAccessFrameRef> mFrames;
+  bool InsertInternal(RefPtr<imgFrame>&& aFrame) override;
+  void AdvanceInternal() override;
+  bool ResetInternal() override;
+
+  // The frames of this animation, in order.
+  nsTArray<RefPtr<imgFrame>> mFrames;
 
   // The maximum number of frames we can have before discarding.
   size_t mThreshold;
+};
 
-  // The minimum number of frames that we want buffered ahead of the display.
-  size_t mBatch;
+/**
+ * An AnimationFrameDiscardingQueue will only retain up to mBatch * 2 frames.
+ * When the animation advances, it will discard the old current frame.
+ */
+class AnimationFrameDiscardingQueue : public AnimationFrameBuffer
+{
+public:
+  explicit AnimationFrameDiscardingQueue(AnimationFrameRetainedBuffer&& aQueue);
 
-  // The number of frames to decode before we stop.
-  size_t mPending;
+  imgFrame* Get(size_t aFrame, bool aForDisplay) final;
+  bool IsFirstFrameFinished() const final;
+  bool IsLastInsertedFrame(imgFrame* aFrame) const final;
+  bool MarkComplete(const gfx::IntRect& aFirstFrameRefreshArea) override;
+  void AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                              const AddSizeOfCb& aCallback) override;
 
-  // The number of frames we need to auto-advance to synchronize with the caller.
-  size_t mAdvance;
+  const std::deque<RefPtr<imgFrame>>& Display() const { return mDisplay; }
+  const imgFrame* FirstFrame() const { return mFirstFrame; }
+  size_t PendingInsert() const { return mInsertIndex; }
 
-  // The mFrames index in which to insert the next decoded frame.
+protected:
+  bool InsertInternal(RefPtr<imgFrame>&& aFrame) override;
+  void AdvanceInternal() override;
+  bool ResetInternal() override;
+
+  /// The sequential index of the frame we inserting next.
   size_t mInsertIndex;
 
-  // The mFrames index that we have advanced to.
-  size_t mGetIndex;
+  /// Queue storing frames to be displayed by the animator. The first frame in
+  /// the queue is the currently displayed frame.
+  std::deque<RefPtr<imgFrame>> mDisplay;
+
+  /// The first frame which is never discarded, and preferentially reused.
+  RefPtr<imgFrame> mFirstFrame;
+};
+
+/**
+ * An AnimationFrameRecyclingQueue will only retain up to mBatch * 2 frames.
+ * When the animation advances, it will place the old current frame into a
+ * recycling queue to be reused for a future allocation. This only works for
+ * animated images where we decoded full sized frames into their own buffers,
+ * so that the buffers are all identically sized and contain the complete frame
+ * data.
+ */
+class AnimationFrameRecyclingQueue final : public AnimationFrameDiscardingQueue
+{
+public:
+  explicit AnimationFrameRecyclingQueue(AnimationFrameRetainedBuffer&& aQueue);
+
+  bool MarkComplete(const gfx::IntRect& aFirstFrameRefreshArea) override;
+  void AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                              const AddSizeOfCb& aCallback) override;
+
+  RawAccessFrameRef RecycleFrame(gfx::IntRect& aRecycleRect) override;
+
+  struct RecycleEntry {
+    explicit RecycleEntry(const gfx::IntRect &aDirtyRect)
+      : mDirtyRect(aDirtyRect)
+    { }
 
-  // True if the total number of frames is known.
-  bool mSizeKnown;
+    RecycleEntry(RecycleEntry&& aOther)
+      : mFrame(std::move(aOther.mFrame))
+      , mDirtyRect(aOther.mDirtyRect)
+      , mRecycleRect(aOther.mRecycleRect)
+    {
+    }
+
+    RecycleEntry& operator=(RecycleEntry&& aOther)
+    {
+      mFrame = std::move(aOther.mFrame);
+      mDirtyRect = aOther.mDirtyRect;
+      mRecycleRect = aOther.mRecycleRect;
+      return *this;
+    }
+
+    RecycleEntry(const RecycleEntry& aOther) = delete;
+    RecycleEntry& operator=(const RecycleEntry& aOther) = delete;
 
-  // True if we encountered an error while redecoding.
-  bool mRedecodeError;
+    RefPtr<imgFrame> mFrame;   // The frame containing the buffer to recycle.
+    gfx::IntRect mDirtyRect;   // The dirty rect of the frame itself.
+    gfx::IntRect mRecycleRect; // The dirty rect between the recycled frame and
+                               // the future frame that will be written to it.
+  };
+
+  const std::deque<RecycleEntry>& Recycle() const { return mRecycle; }
+  const gfx::IntRect& FirstFrameRefreshArea() const
+  {
+    return mFirstFrameRefreshArea;
+  }
+
+protected:
+  void AdvanceInternal() override;
+  bool ResetInternal() override;
+
+  /// Queue storing frames to be recycled by the decoder to produce its future
+  /// frames. May contain up to mBatch frames, where the last frame in the queue
+  /// is adjacent to the first frame in the mDisplay queue.
+  std::deque<RecycleEntry> mRecycle;
+
+  /// The first frame refresh area. This is used instead of the dirty rect for
+  /// the last frame when transitioning back to the first frame.
+  gfx::IntRect mFirstFrameRefreshArea;
 };
 
 } // namespace image
 } // namespace mozilla
 
 #endif // mozilla_image_AnimationFrameBuffer_h
--- a/image/AnimationSurfaceProvider.cpp
+++ b/image/AnimationSurfaceProvider.cpp
@@ -1,16 +1,17 @@
 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
 /* 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 "AnimationSurfaceProvider.h"
 
 #include "gfxPrefs.h"
+#include "mozilla/gfx/gfxVars.h"
 #include "nsProxyRelease.h"
 
 #include "DecodePool.h"
 #include "Decoder.h"
 
 using namespace mozilla::gfx;
 
 namespace mozilla {
@@ -41,22 +42,26 @@ AnimationSurfaceProvider::AnimationSurfa
   // Calculate how many frames we need to decode in this animation before we
   // enter decode-on-demand mode.
   IntSize frameSize = aSurfaceKey.Size();
   size_t threshold =
     (size_t(gfxPrefs::ImageAnimatedDecodeOnDemandThresholdKB()) * 1024) /
     (pixelSize * frameSize.width * frameSize.height);
   size_t batch = gfxPrefs::ImageAnimatedDecodeOnDemandBatchSize();
 
-  mFrames.Initialize(threshold, batch, aCurrentFrame);
+  mFrames.reset(new AnimationFrameRetainedBuffer(threshold, batch, aCurrentFrame));
 }
 
 AnimationSurfaceProvider::~AnimationSurfaceProvider()
 {
   DropImageReference();
+
+  if (mDecoder) {
+    mDecoder->SetFrameRecycler(nullptr);
+  }
 }
 
 void
 AnimationSurfaceProvider::DropImageReference()
 {
   if (!mImage) {
     return;  // Nothing to do.
   }
@@ -77,51 +82,51 @@ AnimationSurfaceProvider::Reset()
     MutexAutoLock lock(mFramesMutex);
 
     // If we have not crossed the threshold, we know we haven't discarded any
     // frames, and thus we know it is safe move our display index back to the
     // very beginning. It would be cleaner to let the frame buffer make this
     // decision inside the AnimationFrameBuffer::Reset method, but if we have
     // crossed the threshold, we need to hold onto the decoding mutex too. We
     // should avoid blocking the main thread on the decoder threads.
-    mayDiscard = mFrames.MayDiscard();
+    mayDiscard = mFrames->MayDiscard();
     if (!mayDiscard) {
-      restartDecoder = mFrames.Reset();
+      restartDecoder = mFrames->Reset();
     }
   }
 
   if (mayDiscard) {
     // We are over the threshold and have started discarding old frames. In
     // that case we need to seize the decoding mutex. Thankfully we know that
     // we are in the process of decoding at most the batch size frames, so
     // this should not take too long to acquire.
     MutexAutoLock lock(mDecodingMutex);
 
     // Recreate the decoder so we can regenerate the frames again.
     mDecoder = DecoderFactory::CloneAnimationDecoder(mDecoder);
     MOZ_ASSERT(mDecoder);
 
     MutexAutoLock lock2(mFramesMutex);
-    restartDecoder = mFrames.Reset();
+    restartDecoder = mFrames->Reset();
   }
 
   if (restartDecoder) {
     DecodePool::Singleton()->AsyncRun(this);
   }
 }
 
 void
 AnimationSurfaceProvider::Advance(size_t aFrame)
 {
   bool restartDecoder;
 
   {
     // Typical advancement of a frame.
     MutexAutoLock lock(mFramesMutex);
-    restartDecoder = mFrames.AdvanceTo(aFrame);
+    restartDecoder = mFrames->AdvanceTo(aFrame);
   }
 
   if (restartDecoder) {
     DecodePool::Singleton()->AsyncRun(this);
   }
 }
 
 DrawableFrameRef
@@ -129,66 +134,57 @@ AnimationSurfaceProvider::DrawableRef(si
 {
   MutexAutoLock lock(mFramesMutex);
 
   if (Availability().IsPlaceholder()) {
     MOZ_ASSERT_UNREACHABLE("Calling DrawableRef() on a placeholder");
     return DrawableFrameRef();
   }
 
-  imgFrame* frame = mFrames.Get(aFrame);
+  imgFrame* frame = mFrames->Get(aFrame, /* aForDisplay */ true);
   if (!frame) {
     return DrawableFrameRef();
   }
 
   return frame->DrawableRef();
 }
 
-RawAccessFrameRef
-AnimationSurfaceProvider::RawAccessRef(size_t aFrame)
+already_AddRefed<imgFrame>
+AnimationSurfaceProvider::GetFrame(size_t aFrame)
 {
   MutexAutoLock lock(mFramesMutex);
 
   if (Availability().IsPlaceholder()) {
-    MOZ_ASSERT_UNREACHABLE("Calling RawAccessRef() on a placeholder");
-    return RawAccessFrameRef();
+    MOZ_ASSERT_UNREACHABLE("Calling GetFrame() on a placeholder");
+    return nullptr;
   }
 
-  imgFrame* frame = mFrames.Get(aFrame);
-  if (!frame) {
-    return RawAccessFrameRef();
-  }
-
-  return frame->RawAccessRef(/* aOnlyFinished */ true);
+  RefPtr<imgFrame> frame = mFrames->Get(aFrame, /* aForDisplay */ false);
+  MOZ_ASSERT_IF(frame, frame->IsFinished());
+  return frame.forget();
 }
 
 bool
 AnimationSurfaceProvider::IsFinished() const
 {
   MutexAutoLock lock(mFramesMutex);
 
   if (Availability().IsPlaceholder()) {
     MOZ_ASSERT_UNREACHABLE("Calling IsFinished() on a placeholder");
     return false;
   }
 
-  if (mFrames.Frames().IsEmpty()) {
-    MOZ_ASSERT_UNREACHABLE("Calling IsFinished() when we have no frames");
-    return false;
-  }
-
-  // As long as we have at least one finished frame, we're finished.
-  return mFrames.Frames()[0]->IsFinished();
+  return mFrames->IsFirstFrameFinished();
 }
 
 bool
 AnimationSurfaceProvider::IsFullyDecoded() const
 {
   MutexAutoLock lock(mFramesMutex);
-  return mFrames.SizeKnown() && !mFrames.MayDiscard();
+  return mFrames->SizeKnown() && !mFrames->MayDiscard();
 }
 
 size_t
 AnimationSurfaceProvider::LogicalSizeInBytes() const
 {
   // When decoding animated images, we need at most three live surfaces: the
   // composited surface, the previous composited surface for
   // DisposalMethod::RESTORE_PREVIOUS, and the surface we're currently decoding
@@ -207,29 +203,17 @@ AnimationSurfaceProvider::LogicalSizeInB
 void
 AnimationSurfaceProvider::AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
                                                  const AddSizeOfCb& aCallback)
 {
   // Note that the surface cache lock is already held here, and then we acquire
   // mFramesMutex. For this method, this ordering is unavoidable, which means
   // that we must be careful to always use the same ordering elsewhere.
   MutexAutoLock lock(mFramesMutex);
-
-  size_t i = 0;
-  for (const RawAccessFrameRef& frame : mFrames.Frames()) {
-    ++i;
-    if (frame) {
-      frame->AddSizeOfExcludingThis(aMallocSizeOf,
-        [&](AddSizeOfCbData& aMetadata) {
-          aMetadata.index = i;
-          aCallback(aMetadata);
-        }
-      );
-    }
-  }
+  mFrames->AddSizeOfExcludingThis(aMallocSizeOf, aCallback);
 }
 
 void
 AnimationSurfaceProvider::Run()
 {
   MutexAutoLock lock(mDecodingMutex);
 
   if (!mDecoder) {
@@ -290,41 +274,57 @@ AnimationSurfaceProvider::Run()
 
 bool
 AnimationSurfaceProvider::CheckForNewFrameAtYield()
 {
   mDecodingMutex.AssertCurrentThreadOwns();
   MOZ_ASSERT(mDecoder);
 
   bool justGotFirstFrame = false;
-  bool continueDecoding;
+  bool continueDecoding = false;
 
   {
     MutexAutoLock lock(mFramesMutex);
 
     // Try to get the new frame from the decoder.
-    RawAccessFrameRef frame = mDecoder->GetCurrentFrameRef();
+    RefPtr<imgFrame> frame = mDecoder->GetCurrentFrame();
     MOZ_ASSERT(mDecoder->HasFrameToTake());
     mDecoder->ClearHasFrameToTake();
 
     if (!frame) {
       MOZ_ASSERT_UNREACHABLE("Decoder yielded but didn't produce a frame?");
       return true;
     }
 
     // We should've gotten a different frame than last time.
-    MOZ_ASSERT_IF(!mFrames.Frames().IsEmpty(),
-                  mFrames.Frames().LastElement().get() != frame.get());
+    MOZ_ASSERT(!mFrames->IsLastInsertedFrame(frame));
 
     // Append the new frame to the list.
-    continueDecoding = mFrames.Insert(std::move(frame));
+    AnimationFrameBuffer::InsertStatus status =
+      mFrames->Insert(std::move(frame));
+    switch (status) {
+      case AnimationFrameBuffer::InsertStatus::DISCARD_CONTINUE:
+        continueDecoding = true;
+        MOZ_FALLTHROUGH;
+      case AnimationFrameBuffer::InsertStatus::DISCARD_YIELD:
+        RequestFrameDiscarding();
+        break;
+      case AnimationFrameBuffer::InsertStatus::CONTINUE:
+        continueDecoding = true;
+        break;
+      case AnimationFrameBuffer::InsertStatus::YIELD:
+        break;
+      default:
+        MOZ_ASSERT_UNREACHABLE("Unhandled insert status!");
+        break;
+    }
 
     // We only want to handle the first frame if it is the first pass for the
     // animation decoder. The owning image will be cleared after that.
-    size_t frameCount = mFrames.Frames().Length();
+    size_t frameCount = mFrames->Size();
     if (frameCount == 1 && mImage) {
       justGotFirstFrame = true;
     }
   }
 
   if (justGotFirstFrame) {
     AnnounceSurfaceAvailable();
   }
@@ -341,53 +341,95 @@ AnimationSurfaceProvider::CheckForNewFra
   bool justGotFirstFrame = false;
   bool continueDecoding;
 
   {
     MutexAutoLock lock(mFramesMutex);
 
     // The decoder may or may not have a new frame for us at this point. Avoid
     // reinserting the same frame again.
-    RawAccessFrameRef frame = mDecoder->GetCurrentFrameRef();
+    RefPtr<imgFrame> frame = mDecoder->GetCurrentFrame();
 
     // If the decoder didn't finish a new frame (ie if, after starting the
     // frame, it got an error and aborted the frame and the rest of the decode)
     // that means it won't be reporting it to the image or FrameAnimator so we
     // should ignore it too, that's what HasFrameToTake tracks basically.
     if (!mDecoder->HasFrameToTake()) {
-      frame = RawAccessFrameRef();
+      frame = nullptr;
     } else {
       MOZ_ASSERT(frame);
       mDecoder->ClearHasFrameToTake();
     }
 
-    if (!frame || (!mFrames.Frames().IsEmpty() &&
-                   mFrames.Frames().LastElement().get() == frame.get())) {
-      return mFrames.MarkComplete();
+    if (!frame || mFrames->IsLastInsertedFrame(frame)) {
+      return mFrames->MarkComplete(mDecoder->GetFirstFrameRefreshArea());
     }
 
     // Append the new frame to the list.
-    mFrames.Insert(std::move(frame));
-    continueDecoding = mFrames.MarkComplete();
+    AnimationFrameBuffer::InsertStatus status = mFrames->Insert(std::move(frame));
+    switch (status) {
+      case AnimationFrameBuffer::InsertStatus::DISCARD_CONTINUE:
+      case AnimationFrameBuffer::InsertStatus::DISCARD_YIELD:
+        RequestFrameDiscarding();
+        break;
+      case AnimationFrameBuffer::InsertStatus::CONTINUE:
+      case AnimationFrameBuffer::InsertStatus::YIELD:
+        break;
+      default:
+        MOZ_ASSERT_UNREACHABLE("Unhandled insert status!");
+        break;
+    }
+
+    continueDecoding =
+      mFrames->MarkComplete(mDecoder->GetFirstFrameRefreshArea());
 
     // We only want to handle the first frame if it is the first pass for the
     // animation decoder. The owning image will be cleared after that.
-    if (mFrames.Frames().Length() == 1 && mImage) {
+    if (mFrames->Size() == 1 && mImage) {
       justGotFirstFrame = true;
     }
   }
 
   if (justGotFirstFrame) {
     AnnounceSurfaceAvailable();
   }
 
   return continueDecoding;
 }
 
 void
+AnimationSurfaceProvider::RequestFrameDiscarding()
+{
+  mDecodingMutex.AssertCurrentThreadOwns();
+  mFramesMutex.AssertCurrentThreadOwns();
+  MOZ_ASSERT(mDecoder);
+
+  if (mFrames->MayDiscard() || mFrames->IsRecycling()) {
+    MOZ_ASSERT_UNREACHABLE("Already replaced frame queue!");
+    return;
+  }
+
+  auto oldFrameQueue = static_cast<AnimationFrameRetainedBuffer*>(mFrames.get());
+
+  // We only recycle if it is a full frame. Partial frames may be sized
+  // differently from each other. We do not support recycling with WebRender
+  // and shared surfaces at this time as there is additional synchronization
+  // required to know when it is safe to recycle.
+  MOZ_ASSERT(!mDecoder->GetFrameRecycler());
+  if (gfxPrefs::ImageAnimatedDecodeOnDemandRecycle() &&
+      mDecoder->ShouldBlendAnimation() &&
+      (!gfxVars::GetUseWebRenderOrDefault() || !gfxPrefs::ImageMemShared())) {
+    mFrames.reset(new AnimationFrameRecyclingQueue(std::move(*oldFrameQueue)));
+    mDecoder->SetFrameRecycler(this);
+  } else {
+    mFrames.reset(new AnimationFrameDiscardingQueue(std::move(*oldFrameQueue)));
+  }
+}
+
+void
 AnimationSurfaceProvider::AnnounceSurfaceAvailable()
 {
   mFramesMutex.AssertNotCurrentThreadOwns();
   MOZ_ASSERT(mImage);
 
   // We just got the first frame; let the surface cache know. We deliberately do
   // this outside of mFramesMutex to avoid a potential deadlock with
   // AddSizeOfExcludingThis(), since otherwise we'd be acquiring mFramesMutex
@@ -407,17 +449,17 @@ AnimationSurfaceProvider::FinishDecoding
     NotifyDecodeComplete(WrapNotNull(mImage), WrapNotNull(mDecoder));
   }
 
   // Determine if we need to recreate the decoder, in case we are discarding
   // frames and need to loop back to the beginning.
   bool recreateDecoder;
   {
     MutexAutoLock lock(mFramesMutex);
-    recreateDecoder = !mFrames.HasRedecodeError() && mFrames.MayDiscard();
+    recreateDecoder = !mFrames->HasRedecodeError() && mFrames->MayDiscard();
   }
 
   if (recreateDecoder) {
     mDecoder = DecoderFactory::CloneAnimationDecoder(mDecoder);
     MOZ_ASSERT(mDecoder);
   } else {
     mDecoder = nullptr;
   }
@@ -435,10 +477,18 @@ bool
 AnimationSurfaceProvider::ShouldPreferSyncRun() const
 {
   MutexAutoLock lock(mDecodingMutex);
   MOZ_ASSERT(mDecoder);
 
   return mDecoder->ShouldSyncDecode(gfxPrefs::ImageMemDecodeBytesAtATime());
 }
 
+RawAccessFrameRef
+AnimationSurfaceProvider::RecycleFrame(gfx::IntRect& aRecycleRect)
+{
+  MutexAutoLock lock(mFramesMutex);
+  MOZ_ASSERT(mFrames->IsRecycling());
+  return mFrames->RecycleFrame(aRecycleRect);
+}
+
 } // namespace image
 } // namespace mozilla
--- a/image/AnimationSurfaceProvider.h
+++ b/image/AnimationSurfaceProvider.h
@@ -5,32 +5,36 @@
 
 /**
  * An ISurfaceProvider for animated images.
  */
 
 #ifndef mozilla_image_AnimationSurfaceProvider_h
 #define mozilla_image_AnimationSurfaceProvider_h
 
+#include "mozilla/UniquePtr.h"
+
+#include "Decoder.h"
 #include "FrameAnimator.h"
 #include "IDecodingTask.h"
 #include "ISurfaceProvider.h"
 #include "AnimationFrameBuffer.h"
 
 namespace mozilla {
 namespace image {
 
 /**
  * An ISurfaceProvider that manages the decoding of animated images and
  * dynamically generates surfaces for the current playback state of the
  * animation.
  */
 class AnimationSurfaceProvider final
   : public ISurfaceProvider
   , public IDecodingTask
+  , public IDecoderFrameRecycler
 {
 public:
   NS_INLINE_DECL_THREADSAFE_REFCOUNTING(AnimationSurfaceProvider, override)
 
   AnimationSurfaceProvider(NotNull<RasterImage*> aImage,
                            const SurfaceKey& aSurfaceKey,
                            NotNull<Decoder*> aDecoder,
                            size_t aCurrentFrame);
@@ -50,17 +54,17 @@ public:
   size_t LogicalSizeInBytes() const override;
   void AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
                               const AddSizeOfCb& aCallback) override;
   void Reset() override;
   void Advance(size_t aFrame) override;
 
 protected:
   DrawableFrameRef DrawableRef(size_t aFrame) override;
-  RawAccessFrameRef RawAccessRef(size_t aFrame) override;
+  already_AddRefed<imgFrame> GetFrame(size_t aFrame) override;
 
   // Animation frames are always locked. This is because we only want to release
   // their memory atomically (due to the surface cache discarding them). If they
   // were unlocked, the OS could end up releasing the memory of random frames
   // from the middle of the animation, which is not worth the complexity of
   // dealing with.
   bool IsLocked() const override { return true; }
   void SetLocked(bool) override { }
@@ -73,22 +77,30 @@ protected:
 public:
   void Run() override;
   bool ShouldPreferSyncRun() const override;
 
   // Full decodes are low priority compared to metadata decodes because they
   // don't block layout or page load.
   TaskPriority Priority() const override { return TaskPriority::eLow; }
 
+  //////////////////////////////////////////////////////////////////////////////
+  // IDecoderFrameRecycler implementation.
+  //////////////////////////////////////////////////////////////////////////////
+
+public:
+  RawAccessFrameRef RecycleFrame(gfx::IntRect& aRecycleRect) override;
+
 private:
   virtual ~AnimationSurfaceProvider();
 
   void DropImageReference();
   void AnnounceSurfaceAvailable();
   void FinishDecoding();
+  void RequestFrameDiscarding();
 
   // @returns Whether or not we should continue decoding.
   bool CheckForNewFrameAtYield();
 
   // @returns Whether or not we should restart decoding.
   bool CheckForNewFrameAtTerminalState();
 
   /// The image associated with our decoder.
@@ -99,15 +111,15 @@ private:
 
   /// The decoder used to decode this animation.
   RefPtr<Decoder> mDecoder;
 
   /// A mutex to protect mFrames. Always taken after mDecodingMutex.
   mutable Mutex mFramesMutex;
 
   /// The frames of this animation, in order.
-  AnimationFrameBuffer mFrames;
+  UniquePtr<AnimationFrameBuffer> mFrames;
 };
 
 } // namespace image
 } // namespace mozilla
 
 #endif // mozilla_image_AnimationSurfaceProvider_h
--- a/image/Decoder.cpp
+++ b/image/Decoder.cpp
@@ -48,16 +48,17 @@ private:
 };
 
 Decoder::Decoder(RasterImage* aImage)
   : mImageData(nullptr)
   , mImageDataLength(0)
   , mColormap(nullptr)
   , mColormapSize(0)
   , mImage(aImage)
+  , mFrameRecycler(nullptr)
   , mProgress(NoProgress)
   , mFrameCount(0)
   , mLoopLength(FrameTimeout::Zero())
   , mDecoderFlags(DefaultDecoderFlags())
   , mSurfaceFlags(DefaultSurfaceFlags())
   , mInitialized(false)
   , mMetadataDecode(false)
   , mHaveExplicitOutputSize(false)
@@ -334,54 +335,22 @@ Decoder::AllocateFrameInternal(const gfx
   }
 
   if (aOutputSize.width <= 0 || aOutputSize.height <= 0 ||
       aFrameRect.Width() <= 0 || aFrameRect.Height() <= 0) {
     NS_WARNING("Trying to add frame with zero or negative size");
     return RawAccessFrameRef();
   }
 
-  auto frame = MakeNotNull<RefPtr<imgFrame>>();
-  bool nonPremult = bool(mSurfaceFlags & SurfaceFlags::NO_PREMULTIPLY_ALPHA);
-  if (NS_FAILED(frame->InitForDecoder(aOutputSize, aFrameRect, aFormat,
-                                      aPaletteDepth, nonPremult,
-                                      aAnimParams, ShouldBlendAnimation()))) {
-    NS_WARNING("imgFrame::Init should succeed");
-    return RawAccessFrameRef();
-  }
-
-  RawAccessFrameRef ref = frame->RawAccessRef();
-  if (!ref) {
-    frame->Abort();
-    return RawAccessFrameRef();
-  }
-
   if (frameNum == 1) {
     MOZ_ASSERT(aPreviousFrame, "Must provide a previous frame when animated");
     aPreviousFrame->SetRawAccessOnly();
-
-    // If we dispose of the first frame by clearing it, then the first frame's
-    // refresh area is all of itself.
-    // RESTORE_PREVIOUS is invalid (assumed to be DISPOSE_CLEAR).
-    DisposalMethod prevDisposal = aPreviousFrame->GetDisposalMethod();
-    if (prevDisposal == DisposalMethod::CLEAR ||
-        prevDisposal == DisposalMethod::CLEAR_ALL ||
-        prevDisposal == DisposalMethod::RESTORE_PREVIOUS) {
-      mFirstFrameRefreshArea = aPreviousFrame->GetRect();
-    }
   }
 
   if (frameNum > 0) {
-    ref->SetRawAccessOnly();
-
-    // Some GIFs are huge but only have a small area that they animate. We only
-    // need to refresh that small area when frame 0 comes around again.
-    mFirstFrameRefreshArea.UnionRect(mFirstFrameRefreshArea,
-                                     ref->GetBoundedBlendRect());
-
     if (ShouldBlendAnimation()) {
       if (aPreviousFrame->GetDisposalMethod() !=
           DisposalMethod::RESTORE_PREVIOUS) {
         // If the new restore frame is the direct previous frame, then we know
         // the dirty rect is composed only of the current frame's blend rect and
         // the restore frame's clear rect (if applicable) which are handled in
         // filters.
         mRestoreFrame = std::move(aPreviousFrame);
@@ -392,16 +361,74 @@ Decoder::AllocateFrameInternal(const gfx
         // that changed are the restore frame's clear rect, the current frame
         // blending rect, and the previous frame's blending rect. All else is
         // forgotten due to us restoring the same frame again.
         mRestoreDirtyRect = aPreviousFrame->GetBoundedBlendRect();
       }
     }
   }
 
+  RawAccessFrameRef ref;
+
+  // If we have a frame recycler, it must be for an animated image producing
+  // full frames. If the higher layers are discarding frames because of the
+  // memory footprint, then the recycler will allow us to reuse the buffers.
+  // Each frame should be the same size and have mostly the same properties.
+  if (mFrameRecycler) {
+    MOZ_ASSERT(ShouldBlendAnimation());
+    MOZ_ASSERT(aPaletteDepth == 0);
+    MOZ_ASSERT(aAnimParams);
+    MOZ_ASSERT(aFrameRect.IsEqualEdges(IntRect(IntPoint(0, 0), aOutputSize)));
+
+    ref = mFrameRecycler->RecycleFrame(mRecycleRect);
+    if (ref) {
+      // If the recycled frame is actually the current restore frame, we cannot
+      // use it. If the next restore frame is the new frame we are creating, in
+      // theory we could reuse it, but we would need to store the restore frame
+      // animation parameters elsewhere. For now we just drop it.
+      bool blocked = ref.get() == mRestoreFrame.get();
+      if (!blocked) {
+        nsresult rv = ref->InitForDecoderRecycle(aAnimParams.ref());
+        blocked = NS_WARN_IF(NS_FAILED(rv));
+      }
+
+      if (blocked) {
+        ref.reset();
+      }
+    }
+  }
+
+  // Either the recycler had nothing to give us, or we don't have a recycler.
+  // Produce a new frame to store the data.
+  if (!ref) {
+    // There is no underlying data to reuse, so reset the recycle rect to be
+    // the full frame, to ensure the restore frame is fully copied.
+    mRecycleRect = IntRect(IntPoint(0, 0), aOutputSize);
+
+    bool nonPremult = bool(mSurfaceFlags & SurfaceFlags::NO_PREMULTIPLY_ALPHA);
+    auto frame = MakeNotNull<RefPtr<imgFrame>>();
+    if (NS_FAILED(frame->InitForDecoder(aOutputSize, aFrameRect, aFormat,
+                                        aPaletteDepth, nonPremult,
+                                        aAnimParams, ShouldBlendAnimation(),
+                                        bool(mFrameRecycler)))) {
+      NS_WARNING("imgFrame::Init should succeed");
+      return RawAccessFrameRef();
+    }
+
+    ref = frame->RawAccessRef();
+    if (!ref) {
+      frame->Abort();
+      return RawAccessFrameRef();
+    }
+
+    if (frameNum > 0) {
+      frame->SetRawAccessOnly();
+    }
+  }
+
   mFrameCount++;
 
   return ref;
 }
 
 /*
  * Hook stubs. Override these as necessary in decoder implementations.
  */
@@ -486,21 +513,44 @@ Decoder::PostFrameStop(Opacity aFrameOpa
   mFinishedNewFrame = true;
 
   mCurrentFrame->Finish(aFrameOpacity, mFinalizeFrames);
 
   mProgress |= FLAG_FRAME_COMPLETE;
 
   mLoopLength += mCurrentFrame->GetTimeout();
 
-  // If we're not sending partial invalidations, then we send an invalidation
-  // here when the first frame is complete.
-  if (!ShouldSendPartialInvalidations() && mFrameCount == 1) {
-    mInvalidRect.UnionRect(mInvalidRect,
-                           IntRect(IntPoint(), Size()));
+  if (mFrameCount == 1) {
+    // If we're not sending partial invalidations, then we send an invalidation
+    // here when the first frame is complete.
+    if (!ShouldSendPartialInvalidations()) {
+      mInvalidRect.UnionRect(mInvalidRect,
+                             IntRect(IntPoint(), Size()));
+    }
+
+    // If we dispose of the first frame by clearing it, then the first frame's
+    // refresh area is all of itself. RESTORE_PREVIOUS is invalid (assumed to
+    // be DISPOSE_CLEAR).
+    switch (mCurrentFrame->GetDisposalMethod()) {
+      default:
+        MOZ_FALLTHROUGH_ASSERT("Unexpected DisposalMethod");
+      case DisposalMethod::CLEAR:
+      case DisposalMethod::CLEAR_ALL:
+      case DisposalMethod::RESTORE_PREVIOUS:
+        mFirstFrameRefreshArea = IntRect(IntPoint(), Size());
+        break;
+      case DisposalMethod::KEEP:
+      case DisposalMethod::NOT_SPECIFIED:
+        break;
+    }
+  } else {
+    // Some GIFs are huge but only have a small area that they animate. We only
+    // need to refresh that small area when frame 0 comes around again.
+    mFirstFrameRefreshArea.UnionRect(mFirstFrameRefreshArea,
+                                     mCurrentFrame->GetBoundedBlendRect());
   }
 }
 
 void
 Decoder::PostInvalidation(const gfx::IntRect& aRect,
                           const Maybe<gfx::IntRect>& aRectAtOutputSize
                             /* = Nothing() */)
 {
--- a/image/Decoder.h
+++ b/image/Decoder.h
@@ -86,16 +86,36 @@ struct DecoderTelemetry final
 
   /// The number of chunks our decoder's input was divided into.
   const uint32_t mChunkCount;
 
   /// The amount of time our decoder spent inside DoDecode().
   const TimeDuration mDecodeTime;
 };
 
+/**
+ * Interface which owners of an animated Decoder object must implement in order
+ * to use recycling. It allows the decoder to get a handle to the recycled
+ * frames.
+ */
+class IDecoderFrameRecycler
+{
+public:
+  /**
+   * Request the next available recycled imgFrame from the recycler.
+   *
+   * @param aRecycleRect  If a frame is returned, this must be set to the
+   *                      accumulated dirty rect between the frame being
+   *                      recycled, and the frame being generated.
+   *
+   * @returns The recycled frame, if any is available.
+   */
+  virtual RawAccessFrameRef RecycleFrame(gfx::IntRect& aRecycleRect) = 0;
+};
+
 class Decoder
 {
 public:
   NS_INLINE_DECL_THREADSAFE_REFCOUNTING(Decoder)
 
   explicit Decoder(RasterImage* aImage);
 
   /**
@@ -420,17 +440,16 @@ public:
   }
 
   /**
    * For use during decoding only. Allows the BlendAnimationFilter to get the
    * current frame we are producing for its animation parameters.
    */
   imgFrame* GetCurrentFrame()
   {
-    MOZ_ASSERT(ShouldBlendAnimation());
     return mCurrentFrame.get();
   }
 
   /**
    * For use during decoding only. Allows the BlendAnimationFilter to get the
    * frame it should be pulling the previous frame data from.
    */
   const RawAccessFrameRef& GetRestoreFrameRef() const
@@ -440,22 +459,39 @@ public:
   }
 
   const gfx::IntRect& GetRestoreDirtyRect() const
   {
     MOZ_ASSERT(ShouldBlendAnimation());
     return mRestoreDirtyRect;
   }
 
+  const gfx::IntRect& GetRecycleRect() const
+  {
+    MOZ_ASSERT(ShouldBlendAnimation());
+    return mRecycleRect;
+  }
+
+  const gfx::IntRect& GetFirstFrameRefreshArea() const
+  {
+    return mFirstFrameRefreshArea;
+  }
+
   bool HasFrameToTake() const { return mHasFrameToTake; }
   void ClearHasFrameToTake() {
     MOZ_ASSERT(mHasFrameToTake);
     mHasFrameToTake = false;
   }
 
+  IDecoderFrameRecycler* GetFrameRecycler() const { return mFrameRecycler; }
+  void SetFrameRecycler(IDecoderFrameRecycler* aFrameRecycler)
+  {
+    mFrameRecycler = aFrameRecycler;
+  }
+
 protected:
   friend class AutoRecordDecoderTelemetry;
   friend class DecoderTestHelper;
   friend class nsICODecoder;
   friend class PalettedSurfaceSink;
   friend class SurfaceSink;
 
   virtual ~Decoder();
@@ -588,29 +624,32 @@ protected:
   uint8_t* mImageData;  // Pointer to image data in either Cairo or 8bit format
   uint32_t mImageDataLength;
   uint32_t* mColormap;  // Current colormap to be used in Cairo format
   uint32_t mColormapSize;
 
 private:
   RefPtr<RasterImage> mImage;
   Maybe<SourceBufferIterator> mIterator;
+  IDecoderFrameRecycler* mFrameRecycler;
 
   // The current frame the decoder is producing.
   RawAccessFrameRef mCurrentFrame;
 
   // The complete frame to combine with the current partial frame to produce
   // a complete current frame.
   RawAccessFrameRef mRestoreFrame;
 
   ImageMetadata mImageMetadata;
 
   gfx::IntRect mInvalidRect; // Tracks new rows as the current frame is decoded.
   gfx::IntRect mRestoreDirtyRect; // Tracks an invalidation region between the
                                   // restore frame and the previous frame.
+  gfx::IntRect mRecycleRect; // Tracks an invalidation region between the recycled
+                             // frame and the current frame.
   Maybe<gfx::IntSize> mOutputSize;  // The size of our output surface.
   Maybe<gfx::IntSize> mExpectedSize; // The expected size of the image.
   Progress mProgress;
 
   uint32_t mFrameCount; // Number of frames, including anything in-progress
   FrameTimeout mLoopLength;  // Length of a single loop of this image.
   gfx::IntRect mFirstFrameRefreshArea;  // The area of the image that needs to
                                         // be invalidated when the animation loops.
--- a/image/DecoderFactory.cpp
+++ b/image/DecoderFactory.cpp
@@ -241,16 +241,17 @@ DecoderFactory::CloneAnimationDecoder(De
   RefPtr<Decoder> decoder = GetDecoder(type, nullptr, /* aIsRedecode = */ true);
   MOZ_ASSERT(decoder, "Should have a decoder now");
 
   // Initialize the decoder.
   decoder->SetMetadataDecode(false);
   decoder->SetIterator(aDecoder->GetSourceBuffer()->Iterator());
   decoder->SetDecoderFlags(aDecoder->GetDecoderFlags());
   decoder->SetSurfaceFlags(aDecoder->GetSurfaceFlags());
+  decoder->SetFrameRecycler(aDecoder->GetFrameRecycler());
 
   if (NS_FAILED(decoder->Init())) {
     return nullptr;
   }
 
   return decoder.forget();
 }
 
--- a/image/FrameAnimator.cpp
+++ b/image/FrameAnimator.cpp
@@ -231,17 +231,17 @@ FrameAnimator::GetCurrentImgFrameEndTime
   TimeDuration durationOfTimeout =
     TimeDuration::FromMilliseconds(double(aCurrentTimeout.AsMilliseconds()));
   return aState.mCurrentAnimationFrameTime + durationOfTimeout;
 }
 
 RefreshResult
 FrameAnimator::AdvanceFrame(AnimationState& aState,
                             DrawableSurface& aFrames,
-                            RawAccessFrameRef& aCurrentFrame,
+                            RefPtr<imgFrame>& aCurrentFrame,
                             TimeStamp aTime)
 {
   AUTO_PROFILER_LABEL("FrameAnimator::AdvanceFrame", GRAPHICS);
 
   RefreshResult ret;
 
   // Determine what the next frame is, taking into account looping.
   uint32_t currentFrameIndex = aState.mCurrentAnimationFrameIndex;
@@ -290,17 +290,17 @@ FrameAnimator::AdvanceFrame(AnimationSta
   }
 
   // There can be frames in the surface cache with index >= KnownFrameCount()
   // which GetRawFrame() can access because an async decoder has decoded them,
   // but which AnimationState doesn't know about yet because we haven't received
   // the appropriate notification on the main thread. Make sure we stay in sync
   // with AnimationState.
   MOZ_ASSERT(nextFrameIndex < aState.KnownFrameCount());
-  RawAccessFrameRef nextFrame = aFrames.RawAccessRef(nextFrameIndex);
+  RefPtr<imgFrame> nextFrame = aFrames.GetFrame(nextFrameIndex);
 
   // We should always check to see if we have the next frame even if we have
   // previously finished decoding. If we needed to redecode (e.g. due to a draw
   // failure) we would have discarded all the old frames and may not yet have
   // the new ones. DrawableSurface::RawAccessRef promises to only return
   // finished frames.
   if (!nextFrame) {
     // Uh oh, the frame we want to show is currently being decoded (partial).
@@ -316,18 +316,23 @@ FrameAnimator::AdvanceFrame(AnimationSta
     ret.mAnimationFinished = true;
   }
 
   if (nextFrameIndex == 0) {
     MOZ_ASSERT(nextFrame->IsFullFrame());
     ret.mDirtyRect = aState.FirstFrameRefreshArea();
   } else if (!nextFrame->IsFullFrame()) {
     MOZ_ASSERT(nextFrameIndex == currentFrameIndex + 1);
+    RawAccessFrameRef currentRef =
+      aCurrentFrame->RawAccessRef(/* aFinished */ true);
+    RawAccessFrameRef nextRef =
+      nextFrame->RawAccessRef(/* aFinished */ true);
+
     // Change frame
-    if (!DoBlend(aCurrentFrame, nextFrame, nextFrameIndex, &ret.mDirtyRect)) {
+    if (!DoBlend(currentRef, nextRef, nextFrameIndex, &ret.mDirtyRect)) {
       // something went wrong, move on to next
       NS_WARNING("FrameAnimator::AdvanceFrame(): Compositing of frame failed");
       nextFrame->SetCompositingFailed(true);
       aState.mCurrentAnimationFrameTime =
         GetCurrentImgFrameEndTime(aState, aCurrentFrame->GetTimeout());
       aState.mCurrentAnimationFrameIndex = nextFrameIndex;
       aState.mCompositedFrameRequested = false;
       aCurrentFrame = std::move(nextFrame);
@@ -436,18 +441,18 @@ FrameAnimator::RequestRefresh(AnimationS
   if (aState.IsDiscarded() || !result) {
     aState.MaybeAdvanceAnimationFrameTime(aTime);
     if (!ret.mDirtyRect.IsEmpty()) {
       ret.mFrameAdvanced = true;
     }
     return ret;
   }
 
-  RawAccessFrameRef currentFrame =
-    result.Surface().RawAccessRef(aState.mCurrentAnimationFrameIndex);
+  RefPtr<imgFrame> currentFrame =
+    result.Surface().GetFrame(aState.mCurrentAnimationFrameIndex);
 
   // only advance the frame if the current time is greater than or
   // equal to the current frame's end time.
   if (!currentFrame) {
     MOZ_ASSERT(gfxPrefs::ImageMemAnimatedDiscardable());
     MOZ_ASSERT(aState.GetHasRequestedDecode() && !aState.GetIsCurrentlyDecoded());
     MOZ_ASSERT(aState.mCompositedFrameInvalid);
     // Nothing we can do but wait for our previous current frame to be decoded
@@ -609,17 +614,20 @@ FrameAnimator::CollectSizeOfCompositingS
 // DoBlend gets called when the timer for animation get fired and we have to
 // update the composited frame of the animation.
 bool
 FrameAnimator::DoBlend(const RawAccessFrameRef& aPrevFrame,
                        const RawAccessFrameRef& aNextFrame,
                        uint32_t aNextFrameIndex,
                        IntRect* aDirtyRect)
 {
-  MOZ_ASSERT(aPrevFrame && aNextFrame, "Should have frames here");
+  if (!aPrevFrame || !aNextFrame) {
+    MOZ_ASSERT_UNREACHABLE("Should have RawAccessFrameRefs to blend!");
+    return false;
+  }
 
   DisposalMethod prevDisposalMethod = aPrevFrame->GetDisposalMethod();
   bool prevHasAlpha = aPrevFrame->FormatHasAlpha();
   if (prevDisposalMethod == DisposalMethod::RESTORE_PREVIOUS &&
       !mCompositingPrevFrame) {
     prevDisposalMethod = DisposalMethod::CLEAR;
   }
 
--- a/image/FrameAnimator.h
+++ b/image/FrameAnimator.h
@@ -348,17 +348,17 @@ private: // methods
    *                      we advance, it will replace aCurrentFrame with the
    *                      new current frame we advanced to.
    *
    * @returns a RefreshResult that shows whether the frame was successfully
    *          advanced, and its resulting dirty rect.
    */
   RefreshResult AdvanceFrame(AnimationState& aState,
                              DrawableSurface& aFrames,
-                             RawAccessFrameRef& aCurrentFrame,
+                             RefPtr<imgFrame>& aCurrentFrame,
                              TimeStamp aTime);
 
   /**
    * Get the time the frame we're currently displaying is supposed to end.
    *
    * In the error case (like if the requested frame is not currently
    * decoded), returns None().
    */
--- a/image/ISurfaceProvider.h
+++ b/image/ISurfaceProvider.h
@@ -105,23 +105,22 @@ protected:
 
   virtual ~ISurfaceProvider() { }
 
   /// @return an eagerly computed drawable reference to a surface. For
   /// dynamically generated animation surfaces, @aFrame specifies the 0-based
   /// index of the desired frame.
   virtual DrawableFrameRef DrawableRef(size_t aFrame) = 0;
 
-  /// @return an eagerly computed raw access reference to a surface. For
-  /// dynamically generated animation surfaces, @aFrame specifies the 0-based
-  /// index of the desired frame.
-  virtual RawAccessFrameRef RawAccessRef(size_t aFrame)
+  /// @return an imgFrame at the 0-based index of the desired frame, as
+  /// specified by @aFrame. Only applies for animated images.
+  virtual already_AddRefed<imgFrame> GetFrame(size_t aFrame)
   {
-    MOZ_ASSERT_UNREACHABLE("Surface provider does not support raw access!");
-    return RawAccessFrameRef();
+    MOZ_ASSERT_UNREACHABLE("Surface provider does not support direct access!");
+    return nullptr;
   }
 
   /// @return true if this ISurfaceProvider is locked. (@see SetLocked())
   /// Should only be called from SurfaceCache code as it relies on SurfaceCache
   /// for synchronization.
   virtual bool IsLocked() const = 0;
 
   /// If @aLocked is true, hint that this ISurfaceProvider is in use and it
@@ -203,26 +202,26 @@ public:
       return NS_ERROR_FAILURE;
     }
 
     mDrawableRef = mProvider->DrawableRef(aFrame);
 
     return mDrawableRef ? NS_OK : NS_ERROR_FAILURE;
   }
 
-  RawAccessFrameRef RawAccessRef(size_t aFrame)
+  already_AddRefed<imgFrame> GetFrame(size_t aFrame)
   {
     MOZ_ASSERT(mHaveSurface, "Trying to get on an empty DrawableSurface?");
 
     if (!mProvider) {
       MOZ_ASSERT_UNREACHABLE("Trying to get on a static DrawableSurface?");
-      return RawAccessFrameRef();
+      return nullptr;
     }
 
-    return mProvider->RawAccessRef(aFrame);
+    return mProvider->GetFrame(aFrame);
   }
 
   void Reset()
   {
     if (!mProvider) {
       MOZ_ASSERT_UNREACHABLE("Trying to reset a static DrawableSurface?");
       return;
     }
new file mode 100644
--- /dev/null
+++ b/image/RecyclingSourceSurface.h
@@ -0,0 +1,66 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=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 mozilla_image_RecyclingSourceSurface_h
+#define mozilla_image_RecyclingSourceSurface_h
+
+#include "mozilla/gfx/2D.h"
+
+namespace mozilla {
+namespace image {
+
+class imgFrame;
+
+/**
+ * This surface subclass will prevent the underlying surface from being recycled
+ * as long as it is still alive. We will create this surface to wrap imgFrame's
+ * mLockedSurface, if we are accessing it on a path that will keep the surface
+ * alive for an indeterminate period of time (e.g. imgFrame::GetSourceSurface,
+ * imgFrame::Draw with a recording or capture DrawTarget).
+ */
+class RecyclingSourceSurface final : public gfx::DataSourceSurface
+{
+public:
+  RecyclingSourceSurface(imgFrame* aParent, gfx::DataSourceSurface* aSurface);
+
+  MOZ_DECLARE_REFCOUNTED_VIRTUAL_TYPENAME(RecyclingSourceSurface, override);
+
+  uint8_t* GetData() override { return mSurface->GetData(); }
+  int32_t Stride() override { return mSurface->Stride(); }
+  gfx::SurfaceType GetType() const override { return mType; }
+  gfx::IntSize GetSize() const override { return mSurface->GetSize(); }
+  gfx::SurfaceFormat GetFormat() const override { return mSurface->GetFormat(); }
+
+  void AddSizeOfExcludingThis(MallocSizeOf aMallocSizeOf,
+                              size_t& aHeapSizeOut,
+                              size_t& aNonHeapSizeOut,
+                              size_t& aExtHandlesOut,
+                              uint64_t& aExtIdOut) const override
+  { }
+
+  bool OnHeap() const override { return mSurface->OnHeap(); }
+  bool Map(MapType aType, MappedSurface* aMappedSurface) override
+  {
+    return mSurface->Map(aType, aMappedSurface);
+  }
+  void Unmap() override { mSurface->Unmap(); }
+
+  gfx::DataSourceSurface* GetChildSurface() const { return mSurface; }
+
+protected:
+  void GuaranteePersistance() override { }
+
+  ~RecyclingSourceSurface() override;
+
+  RefPtr<imgFrame> mParent;
+  RefPtr<DataSourceSurface> mSurface;
+  gfx::SurfaceType mType;
+};
+
+} // namespace image
+} // namespace mozilla
+
+#endif //mozilla_image_RecyclingSourceSurface_h
--- a/image/SurfaceFilters.h
+++ b/image/SurfaceFilters.h
@@ -359,16 +359,27 @@ struct BlendAnimationConfig
  */
 template <typename Next>
 class BlendAnimationFilter final : public SurfaceFilter
 {
 public:
   BlendAnimationFilter()
     : mRow(0)
     , mRowLength(0)
+    , mRecycleRow(0)
+    , mRecycleRowMost(0)
+    , mRecycleRowOffset(0)
+    , mRecycleRowLength(0)
+    , mClearRow(0)
+    , mClearRowMost(0)
+    , mClearPrefixLength(0)
+    , mClearInfixOffset(0)
+    , mClearInfixLength(0)
+    , mClearPostfixOffset(0)
+    , mClearPostfixLength(0)
     , mOverProc(nullptr)
     , mBaseFrameStartPtr(nullptr)
     , mBaseFrameRowPtr(nullptr)
   { }
 
   template <typename... Rest>
   nsresult Configure(const BlendAnimationConfig& aConfig, const Rest&... aRest)
   {
@@ -425,16 +436,17 @@ public:
         }
         break;
     }
 
     // Determine what we need to clear and what we need to copy. If this frame
     // is a full frame and uses source blending, there is no need to consider
     // the disposal method of the previous frame.
     gfx::IntRect dirtyRect(outputRect);
+    gfx::IntRect clearRect;
     if (!fullFrame || blendMethod != BlendMethod::SOURCE) {
       const RawAccessFrameRef& restoreFrame =
         aConfig.mDecoder->GetRestoreFrameRef();
       if (restoreFrame) {
         MOZ_ASSERT(restoreFrame->GetImageSize() == outputSize);
         MOZ_ASSERT(restoreFrame->IsFinished());
 
         // We can safely use this pointer without holding a RawAccessFrameRef
@@ -453,31 +465,65 @@ public:
             dirtyRect = mFrameRect.Union(restoreDirtyRect);
             break;
           case DisposalMethod::CLEAR:
             // We only need to clear if the rect is outside the frame rect (i.e.
             // overwrites a non-overlapping area) or the blend method may cause
             // us to combine old data and new.
             if (!mFrameRect.Contains(restoreBlendRect) ||
                 blendMethod == BlendMethod::OVER) {
-              mClearRect = restoreBlendRect;
+              clearRect = restoreBlendRect;
             }
 
             // If we are clearing the whole frame, we do not need to retain a
             // reference to the base frame buffer.
-            if (outputRect.IsEqualEdges(mClearRect)) {
+            if (outputRect.IsEqualEdges(clearRect)) {
               mBaseFrameStartPtr = nullptr;
             } else {
-              dirtyRect = mFrameRect.Union(restoreDirtyRect).Union(mClearRect);
+              dirtyRect = mFrameRect.Union(restoreDirtyRect).Union(clearRect);
             }
             break;
         }
       } else if (!fullFrame) {
         // This must be the first frame, clear everything.
-        mClearRect = outputRect;
+        clearRect = outputRect;
+      }
+    }
+
+    // We may be able to reuse parts of our underlying buffer that we are
+    // writing the new frame to. The recycle rect gives us the invalidation
+    // region which needs to be copied from the restore frame.
+    const gfx::IntRect& recycleRect = aConfig.mDecoder->GetRecycleRect();
+    mRecycleRow = recycleRect.y;
+    mRecycleRowMost = recycleRect.YMost();
+    mRecycleRowOffset = recycleRect.x * sizeof(uint32_t);
+    mRecycleRowLength = recycleRect.width * sizeof(uint32_t);
+
+    if (!clearRect.IsEmpty()) {
+      // The clear rect interacts with the recycle rect because we need to copy
+      // the prefix and postfix data from the base frame. The one thing we do
+      // know is that the infix area is always cleared explicitly.
+      mClearRow = clearRect.y;
+      mClearRowMost = clearRect.YMost();
+      mClearInfixOffset = clearRect.x * sizeof(uint32_t);
+      mClearInfixLength = clearRect.width * sizeof(uint32_t);
+
+      // The recycle row offset is where we need to begin copying base frame
+      // data for a row. If this offset begins after or at the clear infix
+      // offset, then there is no prefix data at all.
+      if (mClearInfixOffset > mRecycleRowOffset) {
+        mClearPrefixLength = mClearInfixOffset - mRecycleRowOffset;
+      }
+
+      // Similar to the prefix, if the postfix offset begins outside the recycle
+      // rect, then we know we already have all the data we need.
+      mClearPostfixOffset = mClearInfixOffset + mClearInfixLength;
+      size_t recycleRowEndOffset = mRecycleRowOffset + mRecycleRowLength;
+      if (mClearPostfixOffset < recycleRowEndOffset) {
+        mClearPostfixLength = recycleRowEndOffset - mClearPostfixOffset;
       }
     }
 
     // The dirty rect, or delta between the current frame and the previous frame
     // (chronologically, not necessarily the restore frame) is the last
     // animation parameter we need to initialize the new frame with.
     currentFrame->SetDirtyRect(dirtyRect);
 
@@ -623,34 +669,42 @@ private:
 
   void WriteBaseFrameRow()
   {
     uint8_t* dest = mNext.CurrentRowPointer();
     if (!dest) {
       return;
     }
 
+    // No need to copy pixels from the base frame for rows that will not change
+    // between the recycled frame and the new frame.
+    bool needBaseFrame = mRow >= mRecycleRow &&
+                         mRow < mRecycleRowMost;
+
     if (!mBaseFrameRowPtr) {
       // No base frame, so we are clearing everything.
-      memset(dest, 0, mRowLength);
-    } else if (mClearRect.height > 0 &&
-               mClearRect.y <= mRow &&
-               mClearRect.YMost() > mRow) {
+      if (needBaseFrame) {
+        memset(dest + mRecycleRowOffset, 0, mRecycleRowLength);
+      }
+    } else if (mClearRow <= mRow && mClearRowMost > mRow) {
       // We have a base frame, but we are inside the area to be cleared.
       // Only copy the data we need from the source.
-      size_t prefixLength = mClearRect.x * sizeof(uint32_t);
-      size_t clearLength = mClearRect.width * sizeof(uint32_t);
-      size_t postfixOffset = prefixLength + clearLength;
-      size_t postfixLength = mRowLength - postfixOffset;
-      MOZ_ASSERT(prefixLength + clearLength + postfixLength == mRowLength);
-      memcpy(dest, mBaseFrameRowPtr, prefixLength);
-      memset(dest + prefixLength, 0, clearLength);
-      memcpy(dest + postfixOffset, mBaseFrameRowPtr + postfixOffset, postfixLength);
-    } else {
-      memcpy(dest, mBaseFrameRowPtr, mRowLength);
+      if (needBaseFrame) {
+        memcpy(dest + mRecycleRowOffset,
+               mBaseFrameRowPtr + mRecycleRowOffset,
+               mClearPrefixLength);
+        memcpy(dest + mClearPostfixOffset,
+               mBaseFrameRowPtr + mClearPostfixOffset,
+               mClearPostfixLength);
+      }
+      memset(dest + mClearInfixOffset, 0, mClearInfixLength);
+    } else if (needBaseFrame) {
+      memcpy(dest + mRecycleRowOffset,
+             mBaseFrameRowPtr + mRecycleRowOffset,
+             mRecycleRowLength);
     }
   }
 
   bool AdvanceRowOutsideFrameRect()
   {
     // The unclamped frame rect may have a negative offset however we should
     // never be advancing the row via this path (otherwise mBaseFrameRowPtr
     // will be wrong.
@@ -689,23 +743,35 @@ private:
   gfx::IntRect mUnclampedFrameRect;    /// The frame rect before clamping.
   UniquePtr<uint8_t[]> mBuffer;        /// The intermediate buffer, if one is
                                        /// necessary because the frame rect width
                                        /// is larger than the image's logical width.
   int32_t  mRow;                       /// The row in unclamped frame rect space
                                        /// that we're currently writing.
   size_t mRowLength;                   /// Length in bytes of a row that is the input
                                        /// for the next filter.
+  int32_t mRecycleRow;                 /// The starting row of the recycle rect.
+  int32_t mRecycleRowMost;             /// The ending row of the recycle rect.
+  size_t mRecycleRowOffset;            /// Row offset in bytes of the recycle rect.
+  size_t mRecycleRowLength;            /// Row length in bytes of the recycle rect.
+
+  /// The frame area to clear before blending the current frame.
+  int32_t mClearRow;                   /// The starting row of the clear rect.
+  int32_t mClearRowMost;               /// The ending row of the clear rect.
+  size_t mClearPrefixLength;           /// Row length in bytes of clear prefix.
+  size_t mClearInfixOffset;            /// Row offset in bytes of clear area.
+  size_t mClearInfixLength;            /// Row length in bytes of clear area.
+  size_t mClearPostfixOffset;          /// Row offset in bytes of clear postfix.
+  size_t mClearPostfixLength;          /// Row length in bytes of clear postfix.
+
   SkBlitRow::Proc32 mOverProc;         /// Function pointer to perform over blending.
   const uint8_t* mBaseFrameStartPtr;   /// Starting row pointer to the base frame
                                        /// data from which we copy pixel data from.
   const uint8_t* mBaseFrameRowPtr;     /// Current row pointer to the base frame
                                        /// data.
-  gfx::IntRect mClearRect;             /// The frame area to clear before blending
-                                       /// the current frame.
 };
 
 //////////////////////////////////////////////////////////////////////////////
 // RemoveFrameRectFilter
 //////////////////////////////////////////////////////////////////////////////
 
 template <typename Next> class RemoveFrameRectFilter;
 
--- a/image/imgFrame.cpp
+++ b/image/imgFrame.cpp
@@ -17,21 +17,23 @@
 #include "gfxUtils.h"
 
 #include "GeckoProfiler.h"
 #include "MainThreadUtils.h"
 #include "mozilla/CheckedInt.h"
 #include "mozilla/gfx/gfxVars.h"
 #include "mozilla/gfx/Tools.h"
 #include "mozilla/gfx/SourceSurfaceRawData.h"
+#include "mozilla/image/RecyclingSourceSurface.h"
 #include "mozilla/layers/SourceSurfaceSharedData.h"
 #include "mozilla/layers/SourceSurfaceVolatileData.h"
 #include "mozilla/Likely.h"
 #include "mozilla/MemoryReporting.h"
 #include "nsMargin.h"
+#include "nsRefreshDriver.h"
 #include "nsThreadUtils.h"
 
 namespace mozilla {
 
 using namespace gfx;
 
 namespace image {
 
@@ -173,19 +175,21 @@ static bool AllowedImageAndFrameDimensio
   }
   return true;
 }
 
 imgFrame::imgFrame()
   : mMonitor("imgFrame")
   , mDecoded(0, 0, 0, 0)
   , mLockCount(0)
+  , mRecycleLockCount(0)
   , mAborted(false)
   , mFinished(false)
   , mOptimizable(false)
+  , mShouldRecycle(false)
   , mTimeout(FrameTimeout::FromRawMilliseconds(100))
   , mDisposalMethod(DisposalMethod::NOT_SPECIFIED)
   , mBlendMethod(BlendMethod::OVER)
   , mFormat(SurfaceFormat::UNKNOWN)
   , mPalettedImageData(nullptr)
   , mPaletteDepth(0)
   , mNonPremult(false)
   , mIsFullFrame(false)
@@ -204,20 +208,21 @@ imgFrame::~imgFrame()
   free(mPalettedImageData);
   mPalettedImageData = nullptr;
 }
 
 nsresult
 imgFrame::InitForDecoder(const nsIntSize& aImageSize,
                          const nsIntRect& aRect,
                          SurfaceFormat aFormat,
-                         uint8_t aPaletteDepth /* = 0 */,
-                         bool aNonPremult /* = false */,
-                         const Maybe<AnimationParams>& aAnimParams /* = Nothing() */,
-                         bool aIsFullFrame /* = false */)
+                         uint8_t aPaletteDepth,
+                         bool aNonPremult,
+                         const Maybe<AnimationParams>& aAnimParams,
+                         bool aIsFullFrame,
+                         bool aShouldRecycle)
 {
   // Assert for properties that should be verified by decoders,
   // warn for properties related to bad content.
   if (!AllowedImageAndFrameDimensions(aImageSize, aRect)) {
     NS_WARNING("Should have legal image size");
     mAborted = true;
     return NS_ERROR_FAILURE;
   }
@@ -249,19 +254,31 @@ imgFrame::InitForDecoder(const nsIntSize
   // frames, never has to deal with a non-trivial frame rect.
   if (aPaletteDepth == 0 &&
       !mFrameRect.IsEqualEdges(IntRect(IntPoint(), mImageSize))) {
     MOZ_ASSERT_UNREACHABLE("Creating a non-paletted imgFrame with a "
                            "non-trivial frame rect");
     return NS_ERROR_FAILURE;
   }
 
-  mFormat = aFormat;
+  if (aShouldRecycle) {
+    // If we are recycling then we should always use BGRA for the underlying
+    // surface because if we use BGRX, the next frame composited into the
+    // surface could be BGRA and cause rendering problems.
+    MOZ_ASSERT(mIsFullFrame);
+    MOZ_ASSERT(aPaletteDepth == 0);
+    MOZ_ASSERT(aAnimParams);
+    mFormat = SurfaceFormat::B8G8R8A8;
+  } else {
+    mFormat = aFormat;
+  }
+
   mPaletteDepth = aPaletteDepth;
   mNonPremult = aNonPremult;
+  mShouldRecycle = aShouldRecycle;
 
   if (aPaletteDepth != 0) {
     // We're creating for a paletted image.
     if (aPaletteDepth > 8) {
       NS_WARNING("Should have legal palette depth");
       NS_ERROR("This Depth is not supported");
       mAborted = true;
       return NS_ERROR_FAILURE;
@@ -299,16 +316,79 @@ imgFrame::InitForDecoder(const nsIntSize
       return NS_ERROR_OUT_OF_MEMORY;
     }
   }
 
   return NS_OK;
 }
 
 nsresult
+imgFrame::InitForDecoderRecycle(const AnimationParams& aAnimParams)
+{
+  // We want to recycle this frame, but there is no guarantee that consumers are
+  // done with it in a timely manner. Let's ensure they are done with it first.
+  MonitorAutoLock lock(mMonitor);
+
+  MOZ_ASSERT(mIsFullFrame);
+  MOZ_ASSERT(mLockCount > 0);
+  MOZ_ASSERT(mLockedSurface);
+  MOZ_ASSERT(mShouldRecycle);
+
+  if (mRecycleLockCount > 0) {
+    if (NS_IsMainThread()) {
+      // We should never be both decoding and recycling on the main thread. Sync
+      // decoding can only be used to produce the first set of frames. Those
+      // either never use recycling because advancing was blocked (main thread
+      // is busy) or we were auto-advancing (to seek to a frame) and the frames
+      // were never accessed (and thus cannot have recycle locks).
+      MOZ_ASSERT_UNREACHABLE("Recycling/decoding on the main thread?");
+      return NS_ERROR_NOT_AVAILABLE;
+    }
+
+    // We don't want to wait forever to reclaim the frame because we have no
+    // idea why it is still held. It is possibly due to OMTP. Since we are off
+    // the main thread, and we generally have frames already buffered for the
+    // animation, we can afford to wait a short period of time to hopefully
+    // complete the transaction and reclaim the buffer.
+    //
+    // We choose to wait for, at most, the refresh driver interval, so that we
+    // won't skip more than one frame. If the frame is still in use due to
+    // outstanding transactions, we are already skipping frames. If the frame
+    // is still in use for some other purpose, it won't be returned to the pool
+    // and its owner can hold onto it forever without additional impact here.
+    TimeDuration timeout =
+      TimeDuration::FromMilliseconds(nsRefreshDriver::DefaultInterval());
+    while (true) {
+      TimeStamp start = TimeStamp::Now();
+      mMonitor.Wait(timeout);
+      if (mRecycleLockCount == 0) {
+        break;
+      }
+
+      TimeDuration delta = TimeStamp::Now() - start;
+      if (delta >= timeout) {
+        // We couldn't secure the frame for recycling. It will allocate a new
+        // frame instead.
+        return NS_ERROR_NOT_AVAILABLE;
+      }
+
+      timeout -= delta;
+    }
+  }
+
+  mBlendRect = aAnimParams.mBlendRect;
+  mTimeout = aAnimParams.mTimeout;
+  mBlendMethod = aAnimParams.mBlendMethod;
+  mDisposalMethod = aAnimParams.mDisposalMethod;
+  mDirtyRect = mFrameRect;
+
+  return NS_OK;
+}
+
+nsresult
 imgFrame::InitWithDrawable(gfxDrawable* aDrawable,
                            const nsIntSize& aSize,
                            const SurfaceFormat aFormat,
                            SamplingFilter aSamplingFilter,
                            uint32_t aImageFlags,
                            gfx::BackendType aBackend)
 {
   // Assert for properties that should be verified by decoders,
@@ -557,36 +637,53 @@ bool imgFrame::Draw(gfxContext* aContext
   MOZ_ASSERT(mFrameRect.IsEqualEdges(IntRect(IntPoint(), mImageSize)),
              "Directly drawing an image with a non-trivial frame rect!");
 
   if (mPalettedImageData) {
     MOZ_ASSERT_UNREACHABLE("Directly drawing a paletted image!");
     return false;
   }
 
-  MonitorAutoLock lock(mMonitor);
+  // Perform the draw and freeing of the surface outside the lock. We want to
+  // avoid contention with the decoder if we can. The surface may also attempt
+  // to relock the monitor if it is freed (e.g. RecyclingSourceSurface).
+  RefPtr<SourceSurface> surf;
+  SurfaceWithFormat surfaceResult;
+  ImageRegion region(aRegion);
+  gfxRect imageRect(0, 0, mImageSize.width, mImageSize.height);
 
-  // Possibly convert this image into a GPU texture, this may also cause our
-  // mLockedSurface to be released and the OS to release the underlying memory.
-  Optimize(aContext->GetDrawTarget());
+  {
+    MonitorAutoLock lock(mMonitor);
 
-  bool doPartialDecode = !AreAllPixelsWritten();
+    // Possibly convert this image into a GPU texture, this may also cause our
+    // mLockedSurface to be released and the OS to release the underlying memory.
+    Optimize(aContext->GetDrawTarget());
+
+    bool doPartialDecode = !AreAllPixelsWritten();
 
-  RefPtr<SourceSurface> surf = GetSourceSurfaceInternal();
-  if (!surf) {
-    return false;
-  }
+    // Most draw targets will just use the surface only during DrawPixelSnapped
+    // but captures/recordings will retain a reference outside this stack
+    // context. While in theory a decoder thread could be trying to recycle this
+    // frame at this very moment, in practice the only way we can get here is if
+    // this frame is the current frame of the animation. Since we can only
+    // advance on the main thread, we know nothing else will try to use it.
+    DrawTarget* drawTarget = aContext->GetDrawTarget();
+    bool temporary = !drawTarget->IsCaptureDT() &&
+                    drawTarget->GetBackendType() != BackendType::RECORDING;
+    RefPtr<SourceSurface> surf = GetSourceSurfaceInternal(temporary);
+    if (!surf) {
+      return false;
+    }
 
-  gfxRect imageRect(0, 0, mImageSize.width, mImageSize.height);
-  bool doTile = !imageRect.Contains(aRegion.Rect()) &&
-                !(aImageFlags & imgIContainer::FLAG_CLAMP);
+    bool doTile = !imageRect.Contains(aRegion.Rect()) &&
+                  !(aImageFlags & imgIContainer::FLAG_CLAMP);
 
-  ImageRegion region(aRegion);
-  SurfaceWithFormat surfaceResult =
-    SurfaceForDrawing(doPartialDecode, doTile, region, surf);
+    surfaceResult =
+      SurfaceForDrawing(doPartialDecode, doTile, region, surf);
+  }
 
   if (surfaceResult.IsValid()) {
     gfxUtils::DrawPixelSnapped(aContext, surfaceResult.mDrawable,
                                imageRect.Size(), region, surfaceResult.mFormat,
                                aSamplingFilter, aImageFlags, aOpacity);
   }
 
   return true;
@@ -845,38 +942,48 @@ imgFrame::FinalizeSurfaceInternal()
   auto sharedSurf = static_cast<SourceSurfaceSharedData*>(mRawSurface.get());
   sharedSurf->Finalize();
 }
 
 already_AddRefed<SourceSurface>
 imgFrame::GetSourceSurface()
 {
   MonitorAutoLock lock(mMonitor);
-  return GetSourceSurfaceInternal();
+  return GetSourceSurfaceInternal(/* aTemporary */ false);
 }
 
 already_AddRefed<SourceSurface>
-imgFrame::GetSourceSurfaceInternal()
+imgFrame::GetSourceSurfaceInternal(bool aTemporary)
 {
   mMonitor.AssertCurrentThreadOwns();
 
   if (mOptSurface) {
     if (mOptSurface->IsValid()) {
       RefPtr<SourceSurface> surf(mOptSurface);
       return surf.forget();
     } else {
       mOptSurface = nullptr;
     }
   }
 
   if (mLockedSurface) {
+    // We don't need to create recycling wrapper for some callers because they
+    // promise to release the surface immediately after.
+    if (!aTemporary && mShouldRecycle) {
+      RefPtr<SourceSurface> surf =
+        new RecyclingSourceSurface(this, mLockedSurface);
+      return surf.forget();
+    }
+
     RefPtr<SourceSurface> surf(mLockedSurface);
     return surf.forget();
   }
 
+  MOZ_ASSERT(!mShouldRecycle, "Should recycle but no locked surface!");
+
   if (!mRawSurface) {
     return nullptr;
   }
 
   return CreateLockedSurface(mRawSurface, mFrameRect.Size(), mFormat);
 }
 
 void
@@ -961,10 +1068,28 @@ imgFrame::AddSizeOfExcludingThis(MallocS
     mRawSurface->AddSizeOfExcludingThis(aMallocSizeOf, metadata.heap,
                                         metadata.nonHeap, metadata.handles,
                                         metadata.externalId);
   }
 
   aCallback(metadata);
 }
 
+RecyclingSourceSurface::RecyclingSourceSurface(imgFrame* aParent, DataSourceSurface* aSurface)
+  : mParent(aParent)
+  , mSurface(aSurface)
+  , mType(SurfaceType::DATA)
+{
+  mParent->mMonitor.AssertCurrentThreadOwns();
+  ++mParent->mRecycleLockCount;
+}
+
+RecyclingSourceSurface::~RecyclingSourceSurface()
+{
+  MonitorAutoLock lock(mParent->mMonitor);
+  MOZ_ASSERT(mParent->mRecycleLockCount > 0);
+  if (--mParent->mRecycleLockCount == 0) {
+    mParent->mMonitor.NotifyAll();
+  }
+}
+
 } // namespace image
 } // namespace mozilla
--- a/image/imgFrame.h
+++ b/image/imgFrame.h
@@ -52,36 +52,46 @@ public:
    *
    * This is appropriate for use with decoded images, but it should not be used
    * when drawing content into an imgFrame, as it may use a different graphics
    * backend than normal content drawing.
    */
   nsresult InitForDecoder(const nsIntSize& aImageSize,
                           const nsIntRect& aRect,
                           SurfaceFormat aFormat,
-                          uint8_t aPaletteDepth = 0,
-                          bool aNonPremult = false,
-                          const Maybe<AnimationParams>& aAnimParams = Nothing(),
-                          bool aIsFullFrame = false);
+                          uint8_t aPaletteDepth,
+                          bool aNonPremult,
+                          const Maybe<AnimationParams>& aAnimParams,
+                          bool aIsFullFrame,
+                          bool aShouldRecycle);
 
   nsresult InitForAnimator(const nsIntSize& aSize,
                            SurfaceFormat aFormat)
   {
     nsIntRect frameRect(0, 0, aSize.width, aSize.height);
     AnimationParams animParams { frameRect, FrameTimeout::Forever(),
                                  /* aFrameNum */ 1, BlendMethod::OVER,
                                  DisposalMethod::NOT_SPECIFIED };
     // We set aIsFullFrame to false because we don't want the compositing frame
     // to be allocated into shared memory for WebRender. mIsFullFrame is only
     // otherwise used for frames produced by Decoder, so it isn't relevant.
     return InitForDecoder(aSize, frameRect, aFormat, /* aPaletteDepth */ 0,
                           /* aNonPremult */ false, Some(animParams),
-                          /* aIsFullFrame */ false);
+                          /* aIsFullFrame */ false, /* aShouldRecycle */ false);
   }
 
+  /**
+   * Reinitialize this imgFrame with the new parameters, but otherwise retain
+   * the underlying buffer.
+   *
+   * This is appropriate for use with animated images, where the decoder was
+   * given an IDecoderFrameRecycler object which may yield a recycled imgFrame
+   * that was discarded to save memory.
+   */
+  nsresult InitForDecoderRecycle(const AnimationParams& aAnimParams);
 
   /**
    * Initialize this imgFrame with a new surface and draw the provided
    * gfxDrawable into it.
    *
    * This is appropriate to use when drawing content into an imgFrame, as it
    * uses the same graphics backend as normal content drawing. The downside is
    * that the underlying surface may not be stored in a volatile buffer on all
@@ -196,16 +206,18 @@ public:
   const IntRect& GetDirtyRect() const { return mDirtyRect; }
   void SetDirtyRect(const IntRect& aDirtyRect) { mDirtyRect = aDirtyRect; }
 
   bool IsFullFrame() const { return mIsFullFrame; }
 
   bool GetCompositingFailed() const;
   void SetCompositingFailed(bool val);
 
+  bool ShouldRecycle() const { return mShouldRecycle; }
+
   void SetOptimizable();
 
   void FinalizeSurface();
   already_AddRefed<SourceSurface> GetSourceSurface();
 
   struct AddSizeOfCbData {
     AddSizeOfCbData()
       : heap(0), nonHeap(0), handles(0), index(0), externalId(0)
@@ -242,17 +254,24 @@ private: // methods
   void AssertImageDataLocked() const;
 
   bool AreAllPixelsWritten() const;
   nsresult ImageUpdatedInternal(const nsIntRect& aUpdateRect);
   void GetImageDataInternal(uint8_t** aData, uint32_t* length) const;
   uint32_t GetImageBytesPerRow() const;
   uint32_t GetImageDataLength() const;
   void FinalizeSurfaceInternal();
-  already_AddRefed<SourceSurface> GetSourceSurfaceInternal();
+
+  /**
+   * @param aTemporary  If true, it will assume the caller does not require a
+   *                    wrapping RecycleSourceSurface to protect the underlying
+   *                    surface from recycling. The reference to the surface
+   *                    must be freed before releasing the main thread context.
+   */
+  already_AddRefed<SourceSurface> GetSourceSurfaceInternal(bool aTemporary);
 
   uint32_t PaletteDataLength() const
   {
     return mPaletteDepth ? (size_t(1) << mPaletteDepth) * sizeof(uint32_t)
                          : 0;
   }
 
   struct SurfaceWithFormat {
@@ -260,27 +279,39 @@ private: // methods
     SurfaceFormat mFormat;
     SurfaceWithFormat()
       : mFormat(SurfaceFormat::UNKNOWN)
     {
     }
     SurfaceWithFormat(gfxDrawable* aDrawable, SurfaceFormat aFormat)
       : mDrawable(aDrawable), mFormat(aFormat)
     { }
+    SurfaceWithFormat(SurfaceWithFormat&& aOther)
+      : mDrawable(std::move(aOther.mDrawable)), mFormat(aOther.mFormat)
+    { }
+    SurfaceWithFormat& operator=(SurfaceWithFormat&& aOther)
+    {
+      mDrawable = std::move(aOther.mDrawable);
+      mFormat = aOther.mFormat;
+      return *this;
+    }
+    SurfaceWithFormat& operator=(const SurfaceWithFormat& aOther) = delete;
+    SurfaceWithFormat(const SurfaceWithFormat& aOther) = delete;
     bool IsValid() { return !!mDrawable; }
   };
 
   SurfaceWithFormat SurfaceForDrawing(bool               aDoPartialDecode,
                                       bool               aDoTile,
                                       ImageRegion&       aRegion,
                                       SourceSurface*     aSurface);
 
 private: // data
   friend class DrawableFrameRef;
   friend class RawAccessFrameRef;
+  friend class RecyclingSourceSurface;
   friend class UnlockImageDataRunnable;
 
   //////////////////////////////////////////////////////////////////////////////
   // Thread-safe mutable data, protected by mMonitor.
   //////////////////////////////////////////////////////////////////////////////
 
   mutable Monitor mMonitor;
 
@@ -302,21 +333,25 @@ private: // data
    * is unused if the DrawTarget is able to render DataSourceSurface buffers
    * directly.
    */
   RefPtr<SourceSurface> mOptSurface;
 
   nsIntRect mDecoded;
 
   //! Number of RawAccessFrameRefs currently alive for this imgFrame.
-  int32_t mLockCount;
+  int16_t mLockCount;
+
+  //! Number of RecyclingSourceSurface's currently alive for this imgFrame.
+  int16_t mRecycleLockCount;
 
   bool mAborted;
   bool mFinished;
   bool mOptimizable;
+  bool mShouldRecycle;
 
 
   //////////////////////////////////////////////////////////////////////////////
   // Effectively const data, only mutated in the Init methods.
   //////////////////////////////////////////////////////////////////////////////
 
   //! The size of the buffer we are decoding to.
   IntSize      mImageSize;
--- a/image/moz.build
+++ b/image/moz.build
@@ -50,16 +50,17 @@ EXPORTS += [
     'imgRequestProxy.h',
     'IProgressObserver.h',
     'Orientation.h',
     'SurfaceCacheUtils.h',
 ]
 
 EXPORTS.mozilla.image += [
     'ImageMemoryReporter.h',
+    'RecyclingSourceSurface.h',
 ]
 
 UNIFIED_SOURCES += [
     'AnimationFrameBuffer.cpp',
     'AnimationSurfaceProvider.cpp',
     'ClippedImage.cpp',
     'DecodedSurfaceProvider.cpp',
     'DecodePool.cpp',
--- a/image/test/gtest/TestAnimationFrameBuffer.cpp
+++ b/image/test/gtest/TestAnimationFrameBuffer.cpp
@@ -6,660 +6,635 @@
 #include "gtest/gtest.h"
 
 #include "mozilla/Move.h"
 #include "AnimationFrameBuffer.h"
 
 using namespace mozilla;
 using namespace mozilla::image;
 
-static RawAccessFrameRef
-CreateEmptyFrame()
+static already_AddRefed<imgFrame>
+CreateEmptyFrame(const IntSize& aSize = IntSize(1, 1),
+                 const IntRect& aFrameRect = IntRect(0, 0, 1, 1),
+                 bool aCanRecycle = true)
 {
   RefPtr<imgFrame> frame = new imgFrame();
-  nsresult rv = frame->InitForAnimator(nsIntSize(1, 1), SurfaceFormat::B8G8R8A8);
+  AnimationParams animParams { aFrameRect, FrameTimeout::Forever(),
+                               /* aFrameNum */ 1, BlendMethod::OVER,
+                               DisposalMethod::NOT_SPECIFIED };
+  nsresult rv =
+    frame->InitForDecoder(aSize, IntRect(IntPoint(0, 0), aSize),
+                          SurfaceFormat::B8G8R8A8, 0, false,
+                          Some(animParams), true, aCanRecycle);
   EXPECT_TRUE(NS_SUCCEEDED(rv));
   RawAccessFrameRef frameRef = frame->RawAccessRef();
+  frame->SetRawAccessOnly();
   frame->Finish();
-  return frameRef;
-}
-
-static bool
-Fill(AnimationFrameBuffer& buffer, size_t aLength)
-{
-  bool keepDecoding = false;
-  for (size_t i = 0; i < aLength; ++i) {
-    RawAccessFrameRef frame = CreateEmptyFrame();
-    keepDecoding = buffer.Insert(frame->RawAccessRef());
-  }
-  return keepDecoding;
+  return frame.forget();
 }
 
 static void
-CheckFrames(const AnimationFrameBuffer& buffer, size_t aStart, size_t aEnd, bool aExpected)
+PrepareForDiscardingQueue(AnimationFrameRetainedBuffer& aQueue)
 {
-  for (size_t i = aStart; i < aEnd; ++i) {
-    EXPECT_EQ(aExpected, !!buffer.Frames()[i]);
+  ASSERT_EQ(size_t(0), aQueue.Size());
+  ASSERT_LT(size_t(1), aQueue.Batch());
+
+  AnimationFrameBuffer::InsertStatus status =
+    aQueue.Insert(CreateEmptyFrame());
+  EXPECT_EQ(AnimationFrameBuffer::InsertStatus::CONTINUE, status);
+
+  while (true) {
+    status = aQueue.Insert(CreateEmptyFrame());
+    bool restartDecoder = aQueue.AdvanceTo(aQueue.Size() - 1);
+    EXPECT_FALSE(restartDecoder);
+
+    if (status == AnimationFrameBuffer::InsertStatus::DISCARD_CONTINUE) {
+      break;
+    }
+    EXPECT_EQ(AnimationFrameBuffer::InsertStatus::CONTINUE, status);
+  }
+
+  EXPECT_EQ(aQueue.Threshold(), aQueue.Size());
+}
+
+static void
+VerifyDiscardingQueueContents(AnimationFrameDiscardingQueue& aQueue)
+{
+  auto frames = aQueue.Display();
+  for (auto i : frames) {
+    EXPECT_TRUE(i != nullptr);
   }
 }
 
 static void
-CheckRemoved(const AnimationFrameBuffer& buffer, size_t aStart, size_t aEnd)
+VerifyInsertInternal(AnimationFrameBuffer& aQueue,
+                     imgFrame* aFrame)
+{
+  // Determine the frame index where we just inserted the frame.
+  size_t frameIndex;
+  if (aQueue.MayDiscard()) {
+    const AnimationFrameDiscardingQueue& queue =
+      *static_cast<AnimationFrameDiscardingQueue*>(&aQueue);
+    frameIndex = queue.PendingInsert() == 0 ? queue.Size() - 1
+                                            : queue.PendingInsert() - 1;
+  } else {
+    ASSERT_FALSE(aQueue.SizeKnown());
+    frameIndex = aQueue.Size() - 1;
+  }
+
+  // Make sure we can get the frame from that index.
+  RefPtr<imgFrame> frame = aQueue.Get(frameIndex, false);
+  EXPECT_EQ(aFrame, frame.get());
+}
+
+static void
+VerifyAdvance(AnimationFrameBuffer& aQueue,
+              size_t aExpectedFrame,
+              bool aExpectedRestartDecoder)
 {
-  CheckFrames(buffer, aStart, aEnd, false);
+  RefPtr<imgFrame> oldFrame;
+  size_t totalRecycled;
+  if (aQueue.IsRecycling()) {
+    AnimationFrameRecyclingQueue& queue =
+      *static_cast<AnimationFrameRecyclingQueue*>(&aQueue);
+    oldFrame = queue.Get(queue.Displayed(), false);
+    totalRecycled = queue.Recycle().size();
+  }
+
+  bool restartDecoder = aQueue.AdvanceTo(aExpectedFrame);
+  EXPECT_EQ(aExpectedRestartDecoder, restartDecoder);
+
+  if (aQueue.IsRecycling()) {
+    const AnimationFrameRecyclingQueue& queue =
+      *static_cast<AnimationFrameRecyclingQueue*>(&aQueue);
+    if (oldFrame->ShouldRecycle()) {
+      EXPECT_EQ(oldFrame.get(), queue.Recycle().back().mFrame.get());
+      EXPECT_FALSE(queue.Recycle().back().mDirtyRect.IsEmpty());
+      EXPECT_FALSE(queue.Recycle().back().mRecycleRect.IsEmpty());
+      EXPECT_EQ(totalRecycled + 1, queue.Recycle().size());
+    } else {
+      EXPECT_EQ(totalRecycled, queue.Recycle().size());
+      if (!queue.Recycle().empty()) {
+        EXPECT_NE(oldFrame.get(), queue.Recycle().back().mFrame.get());
+      }
+    }
+  }
 }
 
 static void
-CheckRetained(const AnimationFrameBuffer& buffer, size_t aStart, size_t aEnd)
+VerifyInsertAndAdvance(AnimationFrameBuffer& aQueue,
+                       size_t aExpectedFrame,
+                       AnimationFrameBuffer::InsertStatus aExpectedStatus)
+{
+  // Insert the decoded frame.
+  RefPtr<imgFrame> frame = CreateEmptyFrame();
+  AnimationFrameBuffer::InsertStatus status =
+    aQueue.Insert(RefPtr<imgFrame>(frame));
+  EXPECT_EQ(aExpectedStatus, status);
+  EXPECT_TRUE(aQueue.IsLastInsertedFrame(frame));
+  VerifyInsertInternal(aQueue, frame);
+
+  // Advance the display frame.
+  bool expectedRestartDecoder =
+    aExpectedStatus == AnimationFrameBuffer::InsertStatus::YIELD;
+  VerifyAdvance(aQueue, aExpectedFrame, expectedRestartDecoder);
+}
+
+static void
+VerifyMarkComplete(AnimationFrameBuffer& aQueue,
+                   bool aExpectedContinue,
+                   const IntRect& aRefreshArea = IntRect(0, 0, 1, 1))
 {
-  CheckFrames(buffer, aStart, aEnd, true);
+  if (aQueue.IsRecycling() && !aQueue.SizeKnown()) {
+    const AnimationFrameRecyclingQueue& queue =
+      *static_cast<AnimationFrameRecyclingQueue*>(&aQueue);
+    EXPECT_TRUE(queue.FirstFrameRefreshArea().IsEmpty());
+  }
+
+  bool keepDecoding = aQueue.MarkComplete(aRefreshArea);
+  EXPECT_EQ(aExpectedContinue, keepDecoding);
+
+  if (aQueue.IsRecycling()) {
+    const AnimationFrameRecyclingQueue& queue =
+      *static_cast<AnimationFrameRecyclingQueue*>(&aQueue);
+    EXPECT_EQ(aRefreshArea, queue.FirstFrameRefreshArea());
+  }
+}
+
+static void
+VerifyInsert(AnimationFrameBuffer& aQueue,
+             AnimationFrameBuffer::InsertStatus aExpectedStatus)
+{
+  RefPtr<imgFrame> frame = CreateEmptyFrame();
+  AnimationFrameBuffer::InsertStatus status =
+    aQueue.Insert(RefPtr<imgFrame>(frame));
+  EXPECT_EQ(aExpectedStatus, status);
+  EXPECT_TRUE(aQueue.IsLastInsertedFrame(frame));
+  VerifyInsertInternal(aQueue, frame);
+}
+
+static void
+VerifyReset(AnimationFrameBuffer& aQueue,
+            bool aExpectedContinue,
+            const imgFrame* aFirstFrame)
+{
+  bool keepDecoding = aQueue.Reset();
+  EXPECT_EQ(aExpectedContinue, keepDecoding);
+  EXPECT_EQ(aQueue.Batch() * 2, aQueue.PendingDecode());
+  EXPECT_EQ(aFirstFrame, aQueue.Get(0, true));
+
+  if (!aQueue.MayDiscard()) {
+    const AnimationFrameRetainedBuffer& queue =
+      *static_cast<AnimationFrameRetainedBuffer*>(&aQueue);
+    EXPECT_EQ(aFirstFrame, queue.Frames()[0].get());
+    EXPECT_EQ(aFirstFrame, aQueue.Get(0, false));
+  } else {
+    const AnimationFrameDiscardingQueue& queue =
+      *static_cast<AnimationFrameDiscardingQueue*>(&aQueue);
+    EXPECT_EQ(size_t(0), queue.PendingInsert());
+    EXPECT_EQ(size_t(0), queue.Display().size());
+    EXPECT_EQ(aFirstFrame, queue.FirstFrame());
+    EXPECT_EQ(nullptr, aQueue.Get(0, false));
+  }
+
+  if (aQueue.IsRecycling()) {
+    const AnimationFrameRecyclingQueue& queue =
+      *static_cast<AnimationFrameRecyclingQueue*>(&aQueue);
+    EXPECT_EQ(size_t(0), queue.Recycle().size());
+  }
 }
 
 class ImageAnimationFrameBuffer : public ::testing::Test
 {
 public:
   ImageAnimationFrameBuffer()
   { }
 
 private:
   AutoInitializeImageLib mInit;
 };
 
-TEST_F(ImageAnimationFrameBuffer, InitialState)
+TEST_F(ImageAnimationFrameBuffer, RetainedInitialState)
 {
   const size_t kThreshold = 800;
   const size_t kBatch = 100;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, 0);
 
   EXPECT_EQ(kThreshold, buffer.Threshold());
   EXPECT_EQ(kBatch, buffer.Batch());
   EXPECT_EQ(size_t(0), buffer.Displayed());
   EXPECT_EQ(kBatch * 2, buffer.PendingDecode());
   EXPECT_EQ(size_t(0), buffer.PendingAdvance());
   EXPECT_FALSE(buffer.MayDiscard());
   EXPECT_FALSE(buffer.SizeKnown());
-  EXPECT_TRUE(buffer.Frames().IsEmpty());
+  EXPECT_EQ(size_t(0), buffer.Size());
 }
 
 TEST_F(ImageAnimationFrameBuffer, ThresholdTooSmall)
 {
   const size_t kThreshold = 0;
   const size_t kBatch = 10;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, 0);
 
   EXPECT_EQ(kBatch * 2 + 1, buffer.Threshold());
   EXPECT_EQ(kBatch, buffer.Batch());
   EXPECT_EQ(kBatch * 2, buffer.PendingDecode());
   EXPECT_EQ(size_t(0), buffer.PendingAdvance());
 }
 
 TEST_F(ImageAnimationFrameBuffer, BatchTooSmall)
 {
   const size_t kThreshold = 10;
   const size_t kBatch = 0;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, 0);
 
   EXPECT_EQ(kThreshold, buffer.Threshold());
   EXPECT_EQ(size_t(1), buffer.Batch());
   EXPECT_EQ(size_t(2), buffer.PendingDecode());
   EXPECT_EQ(size_t(0), buffer.PendingAdvance());
 }
 
 TEST_F(ImageAnimationFrameBuffer, BatchTooBig)
 {
   const size_t kThreshold = 50;
   const size_t kBatch = SIZE_MAX;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, 0);
 
   // The rounding is important here (e.g. SIZE_MAX/4 * 2 != SIZE_MAX/2).
   EXPECT_EQ(SIZE_MAX/4, buffer.Batch());
   EXPECT_EQ(buffer.Batch() * 2 + 1, buffer.Threshold());
   EXPECT_EQ(buffer.Batch() * 2, buffer.PendingDecode());
   EXPECT_EQ(size_t(0), buffer.PendingAdvance());
 }
 
 TEST_F(ImageAnimationFrameBuffer, FinishUnderBatchAndThreshold)
 {
   const size_t kThreshold = 30;
   const size_t kBatch = 10;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, 0);
   const auto& frames = buffer.Frames();
 
   EXPECT_EQ(kBatch * 2, buffer.PendingDecode());
 
-  RawAccessFrameRef firstFrame;
+  RefPtr<imgFrame> firstFrame;
   for (size_t i = 0; i < 5; ++i) {
-    RawAccessFrameRef frame = CreateEmptyFrame();
-    bool keepDecoding = buffer.Insert(frame->RawAccessRef());
-    EXPECT_TRUE(keepDecoding);
+    RefPtr<imgFrame> frame = CreateEmptyFrame();
+    auto status = buffer.Insert(RefPtr<imgFrame>(frame));
+    EXPECT_EQ(status, AnimationFrameBuffer::InsertStatus::CONTINUE);
     EXPECT_FALSE(buffer.SizeKnown());
+    EXPECT_EQ(buffer.Size(), i + 1);
 
     if (i == 4) {
       EXPECT_EQ(size_t(15), buffer.PendingDecode());
-      keepDecoding = buffer.MarkComplete();
+      bool keepDecoding = buffer.MarkComplete(IntRect(0, 0, 1, 1));
       EXPECT_FALSE(keepDecoding);
       EXPECT_TRUE(buffer.SizeKnown());
       EXPECT_EQ(size_t(0), buffer.PendingDecode());
       EXPECT_FALSE(buffer.HasRedecodeError());
     }
 
     EXPECT_FALSE(buffer.MayDiscard());
 
-    imgFrame* gotFrame = buffer.Get(i);
+    imgFrame* gotFrame = buffer.Get(i, false);
     EXPECT_EQ(frame.get(), gotFrame);
     ASSERT_EQ(i + 1, frames.Length());
     EXPECT_EQ(frame.get(), frames[i].get());
 
     if (i == 0) {
       firstFrame = std::move(frame);
       EXPECT_EQ(size_t(0), buffer.Displayed());
     } else {
       EXPECT_EQ(i - 1, buffer.Displayed());
       bool restartDecoder = buffer.AdvanceTo(i);
       EXPECT_FALSE(restartDecoder);
       EXPECT_EQ(i, buffer.Displayed());
     }
 
-    gotFrame = buffer.Get(0);
+    gotFrame = buffer.Get(0, false);
     EXPECT_EQ(firstFrame.get(), gotFrame);
   }
 
   // Loop again over the animation and make sure it is still all there.
   for (size_t i = 0; i < frames.Length(); ++i) {
-    EXPECT_TRUE(buffer.Get(i) != nullptr);
+    EXPECT_TRUE(buffer.Get(i, false) != nullptr);
 
     bool restartDecoder = buffer.AdvanceTo(i);
     EXPECT_FALSE(restartDecoder);
   }
 }
 
 TEST_F(ImageAnimationFrameBuffer, FinishMultipleBatchesUnderThreshold)
 {
   const size_t kThreshold = 30;
   const size_t kBatch = 2;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, 0);
   const auto& frames = buffer.Frames();
 
   EXPECT_EQ(kBatch * 2, buffer.PendingDecode());
 
   // Add frames until it tells us to stop.
-  bool keepDecoding;
+  AnimationFrameBuffer::InsertStatus status;
   do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
+    status = buffer.Insert(CreateEmptyFrame());
     EXPECT_FALSE(buffer.SizeKnown());
     EXPECT_FALSE(buffer.MayDiscard());
-  } while (keepDecoding);
+  } while (status == AnimationFrameBuffer::InsertStatus::CONTINUE);
 
   EXPECT_EQ(size_t(0), buffer.PendingDecode());
   EXPECT_EQ(size_t(4), frames.Length());
+  EXPECT_EQ(status, AnimationFrameBuffer::InsertStatus::YIELD);
 
   // Progress through the animation until it lets us decode again.
   bool restartDecoder = false;
   size_t i = 0;
   do {
-    EXPECT_TRUE(buffer.Get(i) != nullptr);
+    EXPECT_TRUE(buffer.Get(i, false) != nullptr);
     if (i > 0) {
       restartDecoder = buffer.AdvanceTo(i);
     }
     ++i;
   } while (!restartDecoder);
 
   EXPECT_EQ(size_t(2), buffer.PendingDecode());
   EXPECT_EQ(size_t(2), buffer.Displayed());
 
   // Add the last frame.
-  keepDecoding = buffer.Insert(CreateEmptyFrame());
-  EXPECT_TRUE(keepDecoding);
-  keepDecoding = buffer.MarkComplete();
+  status = buffer.Insert(CreateEmptyFrame());
+  EXPECT_EQ(status, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  bool keepDecoding = buffer.MarkComplete(IntRect(0, 0, 1, 1));
   EXPECT_FALSE(keepDecoding);
   EXPECT_TRUE(buffer.SizeKnown());
   EXPECT_EQ(size_t(0), buffer.PendingDecode());
   EXPECT_EQ(size_t(5), frames.Length());
   EXPECT_FALSE(buffer.HasRedecodeError());
 
   // Finish progressing through the animation.
   for ( ; i < frames.Length(); ++i) {
-    EXPECT_TRUE(buffer.Get(i) != nullptr);
+    EXPECT_TRUE(buffer.Get(i, false) != nullptr);
     restartDecoder = buffer.AdvanceTo(i);
     EXPECT_FALSE(restartDecoder);
   }
 
   // Loop again over the animation and make sure it is still all there.
   for (i = 0; i < frames.Length(); ++i) {
-    EXPECT_TRUE(buffer.Get(i) != nullptr);
+    EXPECT_TRUE(buffer.Get(i, false) != nullptr);
     restartDecoder = buffer.AdvanceTo(i);
     EXPECT_FALSE(restartDecoder);
   }
 
   // Loop to the third frame and then reset the animation.
   for (i = 0; i < 3; ++i) {
-    EXPECT_TRUE(buffer.Get(i) != nullptr);
+    EXPECT_TRUE(buffer.Get(i, false) != nullptr);
     restartDecoder = buffer.AdvanceTo(i);
     EXPECT_FALSE(restartDecoder);
   }
 
   // Since we are below the threshold, we can reset the get index only.
   // Nothing else should have changed.
   restartDecoder = buffer.Reset();
   EXPECT_FALSE(restartDecoder);
-  CheckRetained(buffer, 0, 5);
+  for (i = 0; i < 5; ++i) {
+    EXPECT_TRUE(buffer.Get(i, false) != nullptr);
+  }
   EXPECT_EQ(size_t(0), buffer.PendingDecode());
   EXPECT_EQ(size_t(0), buffer.PendingAdvance());
   EXPECT_EQ(size_t(0), buffer.Displayed());
 }
 
-TEST_F(ImageAnimationFrameBuffer, MayDiscard)
-{
-  const size_t kThreshold = 8;
-  const size_t kBatch = 3;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
-  const auto& frames = buffer.Frames();
-
-  EXPECT_EQ(kBatch * 2, buffer.PendingDecode());
-
-  // Add frames until it tells us to stop.
-  bool keepDecoding;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_FALSE(buffer.SizeKnown());
-    EXPECT_FALSE(buffer.MayDiscard());
-  } while (keepDecoding);
-
-  EXPECT_EQ(size_t(0), buffer.PendingDecode());
-  EXPECT_EQ(size_t(6), frames.Length());
-
-  // Progress through the animation until it lets us decode again.
-  bool restartDecoder = false;
-  size_t i = 0;
-  do {
-    EXPECT_TRUE(buffer.Get(i) != nullptr);
-    if (i > 0) {
-      restartDecoder = buffer.AdvanceTo(i);
-    }
-    ++i;
-  } while (!restartDecoder);
-
-  EXPECT_EQ(size_t(3), buffer.PendingDecode());
-  EXPECT_EQ(size_t(3), buffer.Displayed());
-
-  // Add more frames.
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_FALSE(buffer.SizeKnown());
-  } while (keepDecoding);
-
-  EXPECT_TRUE(buffer.MayDiscard());
-  EXPECT_EQ(size_t(0), buffer.PendingDecode());
-  EXPECT_EQ(size_t(9), frames.Length());
-
-  // It should have be able to remove two frames given we have advanced to the
-  // fourth frame.
-  CheckRetained(buffer, 0, 1);
-  CheckRemoved(buffer, 1, 3);
-  CheckRetained(buffer, 3, 9);
-
-  // Progress through the animation so more. Make sure it removes frames as we
-  // go along.
-  do {
-    EXPECT_TRUE(buffer.Get(i) != nullptr);
-    restartDecoder = buffer.AdvanceTo(i);
-    EXPECT_FALSE(frames[i - 1]);
-    EXPECT_TRUE(frames[i]);
-    i++;
-  } while (!restartDecoder);
-
-  EXPECT_EQ(size_t(3), buffer.PendingDecode());
-  EXPECT_EQ(size_t(6), buffer.Displayed());
-
-  // Add the last frame. It should still let us add more frames, but the next
-  // frame will restart at the beginning.
-  keepDecoding = buffer.Insert(CreateEmptyFrame());
-  EXPECT_TRUE(keepDecoding);
-  keepDecoding = buffer.MarkComplete();
-  EXPECT_TRUE(keepDecoding);
-  EXPECT_TRUE(buffer.SizeKnown());
-  EXPECT_EQ(size_t(2), buffer.PendingDecode());
-  EXPECT_EQ(size_t(10), frames.Length());
-  EXPECT_FALSE(buffer.HasRedecodeError());
-
-  // Use remaining pending room. It shouldn't add new frames, only replace.
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-  } while (keepDecoding);
-
-  EXPECT_EQ(size_t(0), buffer.PendingDecode());
-  EXPECT_EQ(size_t(10), frames.Length());
-
-  // Advance as far as we can. This should require us to loop the animation to
-  // reach a missing frame.
-  do {
-    if (i == frames.Length()) {
-      i = 0;
-    }
-
-    if (!buffer.Get(i)) {
-      break;
-    }
-
-    restartDecoder = buffer.AdvanceTo(i);
-    ++i;
-  } while (true);
-
-  EXPECT_EQ(size_t(3), buffer.PendingDecode());
-  EXPECT_EQ(size_t(2), i);
-  EXPECT_EQ(size_t(1), buffer.Displayed());
-
-  // Decode some more.
-  keepDecoding = Fill(buffer, buffer.PendingDecode());
-  EXPECT_FALSE(keepDecoding);
-  EXPECT_EQ(size_t(0), buffer.PendingDecode());
-
-  // Can we retry advancing again?
-  EXPECT_TRUE(buffer.Get(i) != nullptr);
-  restartDecoder = buffer.AdvanceTo(i);
-  EXPECT_EQ(size_t(2), buffer.Displayed());
-  EXPECT_FALSE(frames[i - 1]);
-  EXPECT_TRUE(frames[i]);
-
-  // Since we are above the threshold, we must reset everything.
-  restartDecoder = buffer.Reset();
-  EXPECT_FALSE(restartDecoder);
-  CheckRetained(buffer, 0, 1);
-  CheckRemoved(buffer, 1, frames.Length());
-  EXPECT_EQ(kBatch * 2, buffer.PendingDecode());
-  EXPECT_EQ(size_t(0), buffer.PendingAdvance());
-  EXPECT_EQ(size_t(0), buffer.Displayed());
-}
-
-TEST_F(ImageAnimationFrameBuffer, ResetIncompleteAboveThreshold)
-{
-  const size_t kThreshold = 5;
-  const size_t kBatch = 2;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
-  const auto& frames = buffer.Frames();
-
-  // Add frames until we exceed the threshold.
-  bool keepDecoding;
-  bool restartDecoder;
-  size_t i = 0;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
-    if (i > 0) {
-      restartDecoder = buffer.AdvanceTo(i);
-      EXPECT_FALSE(restartDecoder);
-    }
-    ++i;
-  } while (!buffer.MayDiscard());
-
-  // Should have threshold + 1 frames, and still not complete.
-  EXPECT_EQ(size_t(6), frames.Length());
-  EXPECT_FALSE(buffer.SizeKnown());
-
-  // Restart the animation, we still had pending frames to decode since we
-  // advanced in lockstep, so it should not ask us to restart the decoder.
-  restartDecoder = buffer.Reset();
-  EXPECT_FALSE(restartDecoder);
-  CheckRetained(buffer, 0, 1);
-  CheckRemoved(buffer, 1, frames.Length());
-  EXPECT_EQ(kBatch * 2, buffer.PendingDecode());
-  EXPECT_EQ(size_t(0), buffer.PendingAdvance());
-  EXPECT_EQ(size_t(0), buffer.Displayed());
-
-  // Adding new frames should not grow the insertion array, but instead
-  // should reuse the space already allocated. Given that we are able to
-  // discard frames once we cross the threshold, we should confirm that
-  // we only do so if we have advanced beyond them.
-  size_t oldFramesLength = frames.Length();
-  size_t advanceUpTo = frames.Length() - kBatch;
-  for (i = 0; i < oldFramesLength; ++i) {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
-    EXPECT_TRUE(frames[i]);
-    EXPECT_EQ(oldFramesLength, frames.Length());
-    if (i > 0) {
-      // If we stop advancing, we should still retain the previous frames.
-      EXPECT_TRUE(frames[i-1]);
-      if (i <= advanceUpTo) {
-        restartDecoder = buffer.AdvanceTo(i);
-        EXPECT_FALSE(restartDecoder);
-      }
-    }
-  }
-
-  // Add one more frame. It should have grown the array this time.
-  keepDecoding = buffer.Insert(CreateEmptyFrame());
-  EXPECT_TRUE(keepDecoding);
-  ASSERT_EQ(i + 1, frames.Length());
-  EXPECT_TRUE(frames[i]);
-}
-
 TEST_F(ImageAnimationFrameBuffer, StartAfterBeginning)
 {
   const size_t kThreshold = 30;
   const size_t kBatch = 2;
   const size_t kStartFrame = 7;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, kStartFrame);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, kStartFrame);
 
   EXPECT_EQ(kStartFrame, buffer.PendingAdvance());
 
   // Add frames until it tells us to stop. It should be later than before,
   // because it auto-advances until its displayed frame is kStartFrame.
-  bool keepDecoding;
+  AnimationFrameBuffer::InsertStatus status;
   size_t i = 0;
   do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
+    status = buffer.Insert(CreateEmptyFrame());
     EXPECT_FALSE(buffer.SizeKnown());
     EXPECT_FALSE(buffer.MayDiscard());
 
     if (i <= kStartFrame) {
       EXPECT_EQ(i, buffer.Displayed());
       EXPECT_EQ(kStartFrame - i, buffer.PendingAdvance());
     } else {
       EXPECT_EQ(kStartFrame, buffer.Displayed());
       EXPECT_EQ(size_t(0), buffer.PendingAdvance());
     }
 
     i++;
-  } while (keepDecoding);
+  } while (status == AnimationFrameBuffer::InsertStatus::CONTINUE);
 
   EXPECT_EQ(size_t(0), buffer.PendingDecode());
   EXPECT_EQ(size_t(0), buffer.PendingAdvance());
-  EXPECT_EQ(size_t(10), buffer.Frames().Length());
+  EXPECT_EQ(size_t(10), buffer.Size());
 }
 
 TEST_F(ImageAnimationFrameBuffer, StartAfterBeginningAndReset)
 {
   const size_t kThreshold = 30;
   const size_t kBatch = 2;
   const size_t kStartFrame = 7;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, kStartFrame);
+  AnimationFrameRetainedBuffer buffer(kThreshold, kBatch, kStartFrame);
 
   EXPECT_EQ(kStartFrame, buffer.PendingAdvance());
 
   // Add frames until it tells us to stop. It should be later than before,
   // because it auto-advances until its displayed frame is kStartFrame.
   for (size_t i = 0; i < 5; ++i) {
-    bool keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
+    AnimationFrameBuffer::InsertStatus status =
+      buffer.Insert(CreateEmptyFrame());
+    EXPECT_EQ(status, AnimationFrameBuffer::InsertStatus::CONTINUE);
     EXPECT_FALSE(buffer.SizeKnown());
     EXPECT_FALSE(buffer.MayDiscard());
     EXPECT_EQ(i, buffer.Displayed());
     EXPECT_EQ(kStartFrame - i, buffer.PendingAdvance());
   }
 
   // When we reset the animation, it goes back to the beginning. That means
   // we can forget about what we were told to advance to at the start. While
   // we have plenty of frames in our buffer, we still need one more because
   // in the real scenario, the decoder thread is still running and it is easier
   // to let it insert its last frame than to coordinate quitting earlier.
   buffer.Reset();
   EXPECT_EQ(size_t(0), buffer.Displayed());
   EXPECT_EQ(size_t(1), buffer.PendingDecode());
   EXPECT_EQ(size_t(0), buffer.PendingAdvance());
+  EXPECT_EQ(size_t(5), buffer.Size());
 }
 
-TEST_F(ImageAnimationFrameBuffer, RedecodeMoreFrames)
+static void TestDiscardingQueueLoop(AnimationFrameDiscardingQueue& aQueue,
+                                    const imgFrame* aFirstFrame,
+                                    size_t aThreshold,
+                                    size_t aBatch,
+                                    size_t aStartFrame)
 {
-  const size_t kThreshold = 5;
-  const size_t kBatch = 2;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
-  const auto& frames = buffer.Frames();
+  // We should be advanced right up to the last decoded frame.
+  EXPECT_TRUE(aQueue.MayDiscard());
+  EXPECT_FALSE(aQueue.SizeKnown());
+  EXPECT_EQ(aBatch, aQueue.Batch());
+  EXPECT_EQ(aThreshold, aQueue.PendingInsert());
+  EXPECT_EQ(aThreshold, aQueue.Size());
+  EXPECT_EQ(aFirstFrame, aQueue.FirstFrame());
+  EXPECT_EQ(size_t(1), aQueue.Display().size());
+  EXPECT_EQ(size_t(3), aQueue.PendingDecode());
+  VerifyDiscardingQueueContents(aQueue);
 
-  // Add frames until we exceed the threshold.
-  bool keepDecoding;
-  bool restartDecoder;
-  size_t i = 0;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
-    if (i > 0) {
-      restartDecoder = buffer.AdvanceTo(i);
-      EXPECT_FALSE(restartDecoder);
-    }
-    ++i;
-  } while (!buffer.MayDiscard());
+  // Make sure frames get removed as we advance.
+  VerifyInsertAndAdvance(aQueue, 5, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  EXPECT_EQ(size_t(1), aQueue.Display().size());
+  VerifyInsertAndAdvance(aQueue, 6, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  EXPECT_EQ(size_t(1), aQueue.Display().size());
+  VerifyInsertAndAdvance(aQueue, 7, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  EXPECT_EQ(size_t(1), aQueue.Display().size());
+
+  // We should get throttled if we insert too much.
+  VerifyInsert(aQueue, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  EXPECT_EQ(size_t(2), aQueue.Display().size());
+  EXPECT_EQ(size_t(1), aQueue.PendingDecode());
+  VerifyInsert(aQueue, AnimationFrameBuffer::InsertStatus::YIELD);
+  EXPECT_EQ(size_t(3), aQueue.Display().size());
+  EXPECT_EQ(size_t(0), aQueue.PendingDecode());
+
+  // We should get restarted if we advance.
+  VerifyAdvance(aQueue, 8, true);
+  EXPECT_EQ(size_t(2), aQueue.PendingDecode());
+  VerifyAdvance(aQueue, 9, false);
+  EXPECT_EQ(size_t(2), aQueue.PendingDecode());
 
-  // Should have threshold + 1 frames, and still not complete.
-  EXPECT_EQ(size_t(6), frames.Length());
-  EXPECT_FALSE(buffer.SizeKnown());
+  // We should continue decoding if we completed, since we are discarding.
+  VerifyMarkComplete(aQueue, true);
+  EXPECT_EQ(size_t(2), aQueue.PendingDecode());
+  EXPECT_EQ(size_t(10), aQueue.Size());
+  EXPECT_TRUE(aQueue.SizeKnown());
+  EXPECT_FALSE(aQueue.HasRedecodeError());
 
-  // Now we lock in at 6 frames.
-  keepDecoding = buffer.MarkComplete();
-  EXPECT_TRUE(keepDecoding);
-  EXPECT_TRUE(buffer.SizeKnown());
-  EXPECT_FALSE(buffer.HasRedecodeError());
+  // Insert the first frames of the animation.
+  VerifyInsert(aQueue, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  VerifyInsert(aQueue, AnimationFrameBuffer::InsertStatus::YIELD);
+  EXPECT_EQ(size_t(0), aQueue.PendingDecode());
+  EXPECT_EQ(size_t(10), aQueue.Size());
 
-  // Reinsert 6 frames first.
-  i = 0;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
-    restartDecoder = buffer.AdvanceTo(i);
-    EXPECT_FALSE(restartDecoder);
-    ++i;
-  } while (i < 6);
+  // Advance back at the beginning. The first frame should only match for
+  // display purposes.
+  VerifyAdvance(aQueue, 0, true);
+  EXPECT_EQ(size_t(2), aQueue.PendingDecode());
+  EXPECT_TRUE(aQueue.FirstFrame() != nullptr);
+  EXPECT_TRUE(aQueue.Get(0, false) != nullptr);
+  EXPECT_NE(aQueue.FirstFrame(), aQueue.Get(0, false));
+  EXPECT_EQ(aQueue.FirstFrame(), aQueue.Get(0, true));
 
-  // We should now encounter an error and shutdown further decodes.
-  keepDecoding = buffer.Insert(CreateEmptyFrame());
-  EXPECT_FALSE(keepDecoding);
-  EXPECT_EQ(size_t(0), buffer.PendingDecode());
-  EXPECT_TRUE(buffer.HasRedecodeError());
+  // Reiterate one more time and make it loops back.
+  VerifyInsertAndAdvance(aQueue, 1, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  VerifyInsertAndAdvance(aQueue, 2, AnimationFrameBuffer::InsertStatus::YIELD);
+  VerifyInsertAndAdvance(aQueue, 3, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  VerifyInsertAndAdvance(aQueue, 4, AnimationFrameBuffer::InsertStatus::YIELD);
+  VerifyInsertAndAdvance(aQueue, 5, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  VerifyInsertAndAdvance(aQueue, 6, AnimationFrameBuffer::InsertStatus::YIELD);
+  VerifyInsertAndAdvance(aQueue, 7, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  VerifyInsertAndAdvance(aQueue, 8, AnimationFrameBuffer::InsertStatus::YIELD);
+
+  EXPECT_EQ(size_t(10), aQueue.PendingInsert());
+  VerifyMarkComplete(aQueue, true);
+  EXPECT_EQ(size_t(0), aQueue.PendingInsert());
+
+  VerifyInsertAndAdvance(aQueue, 9, AnimationFrameBuffer::InsertStatus::CONTINUE);
+  VerifyInsertAndAdvance(aQueue, 0, AnimationFrameBuffer::InsertStatus::YIELD);
+  VerifyInsertAndAdvance(aQueue, 1, AnimationFrameBuffer::InsertStatus::CONTINUE);
 }
 
-TEST_F(ImageAnimationFrameBuffer, RedecodeFewerFrames)
+TEST_F(ImageAnimationFrameBuffer, DiscardingLoop)
 {
   const size_t kThreshold = 5;
   const size_t kBatch = 2;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
-  const auto& frames = buffer.Frames();
-
-  // Add frames until we exceed the threshold.
-  bool keepDecoding;
-  bool restartDecoder;
-  size_t i = 0;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
-    if (i > 0) {
-      restartDecoder = buffer.AdvanceTo(i);
-      EXPECT_FALSE(restartDecoder);
-    }
-    ++i;
-  } while (!buffer.MayDiscard());
-
-  // Should have threshold + 1 frames, and still not complete.
-  EXPECT_EQ(size_t(6), frames.Length());
-  EXPECT_FALSE(buffer.SizeKnown());
-
-  // Now we lock in at 6 frames.
-  keepDecoding = buffer.MarkComplete();
-  EXPECT_TRUE(keepDecoding);
-  EXPECT_TRUE(buffer.SizeKnown());
-  EXPECT_FALSE(buffer.HasRedecodeError());
-
-  // Reinsert 5 frames before marking complete.
-  i = 0;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
-    restartDecoder = buffer.AdvanceTo(i);
-    EXPECT_FALSE(restartDecoder);
-    ++i;
-  } while (i < 5);
-
-  // We should now encounter an error and shutdown further decodes.
-  keepDecoding = buffer.MarkComplete();
-  EXPECT_FALSE(keepDecoding);
-  EXPECT_EQ(size_t(0), buffer.PendingDecode());
-  EXPECT_TRUE(buffer.HasRedecodeError());
+  const size_t kStartFrame = 0;
+  AnimationFrameRetainedBuffer retained(kThreshold, kBatch, kStartFrame);
+  PrepareForDiscardingQueue(retained);
+  const imgFrame* firstFrame = retained.Frames()[0].get();
+  AnimationFrameDiscardingQueue buffer(std::move(retained));
+  TestDiscardingQueueLoop(buffer, firstFrame, kThreshold, kBatch, kStartFrame);
 }
 
-TEST_F(ImageAnimationFrameBuffer, RedecodeFewerFramesAndBehindAdvancing)
+TEST_F(ImageAnimationFrameBuffer, RecyclingLoop)
 {
   const size_t kThreshold = 5;
   const size_t kBatch = 2;
-  AnimationFrameBuffer buffer;
-  buffer.Initialize(kThreshold, kBatch, 0);
-  const auto& frames = buffer.Frames();
+  const size_t kStartFrame = 0;
+  AnimationFrameRetainedBuffer retained(kThreshold, kBatch, kStartFrame);
+  PrepareForDiscardingQueue(retained);
+  const imgFrame* firstFrame = retained.Frames()[0].get();
+  AnimationFrameRecyclingQueue buffer(std::move(retained));
 
-  // Add frames until we exceed the threshold.
-  bool keepDecoding;
-  bool restartDecoder;
-  size_t i = 0;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    EXPECT_TRUE(keepDecoding);
-    if (i > 0) {
-      restartDecoder = buffer.AdvanceTo(i);
-      EXPECT_FALSE(restartDecoder);
-    }
-    ++i;
-  } while (!buffer.MayDiscard());
+  // We should not start with any recycled frames.
+  ASSERT_TRUE(buffer.Recycle().empty());
 
-  // Should have threshold + 1 frames, and still not complete.
-  EXPECT_EQ(size_t(6), frames.Length());
-  EXPECT_FALSE(buffer.SizeKnown());
+  TestDiscardingQueueLoop(buffer, firstFrame, kThreshold, kBatch, kStartFrame);
 
-  // Now we lock in at 6 frames.
-  keepDecoding = buffer.MarkComplete();
-  EXPECT_TRUE(keepDecoding);
-  EXPECT_TRUE(buffer.SizeKnown());
-  EXPECT_FALSE(buffer.HasRedecodeError());
-
-  // Reinsert frames without advancing until we exhaust our pending space. This
-  // should be less than the current buffer length by definition.
-  i = 0;
-  do {
-    keepDecoding = buffer.Insert(CreateEmptyFrame());
-    ++i;
-  } while (keepDecoding);
+  // All the frames we inserted should have been recycleable.
+  ASSERT_FALSE(buffer.Recycle().empty());
+  while (!buffer.Recycle().empty()) {
+    IntRect expectedRect = buffer.Recycle().front().mRecycleRect;
+    RefPtr<imgFrame> expectedFrame = buffer.Recycle().front().mFrame;
+    EXPECT_FALSE(expectedRect.IsEmpty());
+    EXPECT_TRUE(expectedFrame.get() != nullptr);
 
-  EXPECT_EQ(size_t(2), i);
-
-  // We should now encounter an error and shutdown further decodes.
-  keepDecoding = buffer.MarkComplete();
-  EXPECT_FALSE(keepDecoding);
-  EXPECT_EQ(size_t(0), buffer.PendingDecode());
-  EXPECT_TRUE(buffer.HasRedecodeError());
+    IntRect gotRect;
+    RawAccessFrameRef gotFrame = buffer.RecycleFrame(gotRect);
+    EXPECT_EQ(expectedFrame.get(), gotFrame.get());
+    EXPECT_EQ(expectedRect, gotRect);
+  }
 
-  // We should however be able to continue advancing to the last decoded frame
-  // without it requesting the decoder to restart.
-  i = 0;
-  do {
-    restartDecoder = buffer.AdvanceTo(i);
-    EXPECT_FALSE(restartDecoder);
-    ++i;
-  } while (i < 2);
+  // Trying to pull a recycled frame when we have nothing should be safe too.
+  IntRect gotRect;
+  RawAccessFrameRef gotFrame = buffer.RecycleFrame(gotRect);
+  EXPECT_TRUE(gotFrame.get() == nullptr);
+  EXPECT_TRUE(gotRect.IsEmpty());
 }
 
+static void TestDiscardingQueueReset(AnimationFrameDiscardingQueue& aQueue,
+                                     const imgFrame* aFirstFrame,
+                                     size_t aThreshold,
+                                     size_t aBatch,
+                                     size_t aStartFrame)
+{
+  // We should be advanced right up to the last decoded frame.
+  EXPECT_TRUE(aQueue.MayDiscard());
+  EXPECT_FALSE(aQueue.SizeKnown());
+  EXPECT_EQ(aBatch, aQueue.Batch());
+  EXPECT_EQ(aThreshold, aQueue.PendingInsert());
+  EXPECT_EQ(aThreshold, aQueue.Size());
+  EXPECT_EQ(aFirstFrame, aQueue.FirstFrame());
+  EXPECT_EQ(size_t(1), aQueue.Display().size());
+  EXPECT_EQ(size_t(4), aQueue.PendingDecode());
+  VerifyDiscardingQueueContents(aQueue);
+
+  // Reset should clear everything except the first frame.
+  VerifyReset(aQueue, false, aFirstFrame);
+}
+
+TEST_F(ImageAnimationFrameBuffer, DiscardingReset)
+{
+  const size_t kThreshold = 8;
+  const size_t kBatch = 3;
+  const size_t kStartFrame = 0;
+  AnimationFrameRetainedBuffer retained(kThreshold, kBatch, kStartFrame);
+  PrepareForDiscardingQueue(retained);
+  const imgFrame* firstFrame = retained.Frames()[0].get();
+  AnimationFrameDiscardingQueue buffer(std::move(retained));
+  TestDiscardingQueueReset(buffer, firstFrame, kThreshold, kBatch, kStartFrame);
+}
+
+TEST_F(ImageAnimationFrameBuffer, RecyclingReset)
+{
+  const size_t kThreshold = 8;
+  const size_t kBatch = 3;
+  const size_t kStartFrame = 0;
+  AnimationFrameRetainedBuffer retained(kThreshold, kBatch, kStartFrame);
+  PrepareForDiscardingQueue(retained);
+  const imgFrame* firstFrame = retained.Frames()[0].get();
+  AnimationFrameRecyclingQueue buffer(std::move(retained));
+  TestDiscardingQueueReset(buffer, firstFrame, kThreshold, kBatch, kStartFrame);
+}
--- a/image/test/gtest/TestDecoders.cpp
+++ b/image/test/gtest/TestDecoders.cpp
@@ -604,17 +604,17 @@ TEST_F(ImageDecoders, AnimatedGIFWithFRA
                                             DefaultSurfaceFlags(),
                                             PlaybackType::eAnimated),
                            /* aMarkUsed = */ true);
     ASSERT_EQ(MatchType::EXACT, result.Type());
 
     EXPECT_TRUE(NS_SUCCEEDED(result.Surface().Seek(0)));
     EXPECT_TRUE(bool(result.Surface()));
 
-    RawAccessFrameRef partialFrame = result.Surface().RawAccessRef(1);
+    RefPtr<imgFrame> partialFrame = result.Surface().GetFrame(1);
     EXPECT_TRUE(bool(partialFrame));
   }
 
   // Ensure that the static version is still around.
   {
     LookupResult result =
       SurfaceCache::Lookup(ImageKey(image.get()),
                            RasterSurfaceKey(imageSize,
@@ -692,17 +692,17 @@ TEST_F(ImageDecoders, AnimatedGIFWithFRA
                                             DefaultSurfaceFlags(),
                                             PlaybackType::eAnimated),
                            /* aMarkUsed = */ true);
     ASSERT_EQ(MatchType::EXACT, result.Type());
 
     EXPECT_TRUE(NS_SUCCEEDED(result.Surface().Seek(0)));
     EXPECT_TRUE(bool(result.Surface()));
 
-    RawAccessFrameRef partialFrame = result.Surface().RawAccessRef(1);
+    RefPtr<imgFrame> partialFrame = result.Surface().GetFrame(1);
     EXPECT_TRUE(bool(partialFrame));
   }
 
   // Ensure that we didn't decode the static version of the image.
   {
     LookupResult result =
       SurfaceCache::Lookup(ImageKey(image.get()),
                            RasterSurfaceKey(imageSize,
@@ -738,17 +738,17 @@ TEST_F(ImageDecoders, AnimatedGIFWithFRA
                                             DefaultSurfaceFlags(),
                                             PlaybackType::eAnimated),
                            /* aMarkUsed = */ true);
     ASSERT_EQ(MatchType::EXACT, result.Type());
 
     EXPECT_TRUE(NS_SUCCEEDED(result.Surface().Seek(0)));
     EXPECT_TRUE(bool(result.Surface()));
 
-    RawAccessFrameRef partialFrame = result.Surface().RawAccessRef(1);
+    RefPtr<imgFrame> partialFrame = result.Surface().GetFrame(1);
     EXPECT_TRUE(bool(partialFrame));
   }
 }
 
 TEST_F(ImageDecoders, AnimatedGIFWithExtraImageSubBlocks)
 {
   ImageTestCase testCase = ExtraImageSubBlocksAnimatedGIFTestCase();
 
@@ -808,17 +808,17 @@ TEST_F(ImageDecoders, AnimatedGIFWithExt
                                           DefaultSurfaceFlags(),
                                           PlaybackType::eAnimated),
                          /* aMarkUsed = */ true);
   ASSERT_EQ(MatchType::EXACT, result.Type());
 
   EXPECT_TRUE(NS_SUCCEEDED(result.Surface().Seek(0)));
   EXPECT_TRUE(bool(result.Surface()));
 
-  RawAccessFrameRef partialFrame = result.Surface().RawAccessRef(1);
+  RefPtr<imgFrame> partialFrame = result.Surface().GetFrame(1);
   EXPECT_TRUE(bool(partialFrame));
 }
 
 TEST_F(ImageDecoders, TruncatedSmallGIFSingleChunk)
 {
   CheckDecoderSingleChunk(TruncatedSmallGIFTestCase());
 }
 
--- a/image/test/gtest/TestMetadata.cpp
+++ b/image/test/gtest/TestMetadata.cpp
@@ -252,11 +252,11 @@ TEST_F(ImageDecoderMetadata, NoFrameDela
                                           DefaultSurfaceFlags(),
                                           PlaybackType::eAnimated),
                          /* aMarkUsed = */ true);
   ASSERT_EQ(MatchType::EXACT, result.Type());
 
   EXPECT_TRUE(NS_SUCCEEDED(result.Surface().Seek(0)));
   EXPECT_TRUE(bool(result.Surface()));
 
-  RawAccessFrameRef partialFrame = result.Surface().RawAccessRef(1);
+  RefPtr<imgFrame> partialFrame = result.Surface().GetFrame(1);
   EXPECT_TRUE(bool(partialFrame));
 }
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/bug1493900-1.js
@@ -0,0 +1,17 @@
+function f() {
+    var objs = [];
+    for (var i = 0; i < 100; i++) {
+        objs[i] = {};
+    }
+    var o = objs[0];
+    var a = new Float64Array(1024);
+    function g(a, b) {
+        let p = b;
+        for (; p.x < 0; p = p.x) {
+            while (p === p) {}
+        }
+        for (var i = 0; i < 10000; ++i) {}
+    }
+    g(a, o);
+}
+f();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/ion/bug1493900-2.js
@@ -0,0 +1,7 @@
+function f(a, b) {
+    for (; b.x < 0; b = b.x) {
+        while (b === b) {};
+    }
+    for (var i = 0; i < 99999; ++i) {}
+}
+f(0, 0);
--- a/js/src/jit/BacktrackingAllocator.cpp
+++ b/js/src/jit/BacktrackingAllocator.cpp
@@ -1948,16 +1948,28 @@ BacktrackingAllocator::deadRange(LiveRan
     if (reg.usedByPhi()) {
         return false;
     }
 
     return true;
 }
 
 bool
+BacktrackingAllocator::moveAtEdge(LBlock* predecessor, LBlock* successor, LiveRange* from,
+                                  LiveRange* to, LDefinition::Type type)
+{
+    if (successor->mir()->numPredecessors() > 1) {
+        MOZ_ASSERT(predecessor->mir()->numSuccessors() == 1);
+        return moveAtExit(predecessor, from, to, type);
+    }
+
+    return moveAtEntry(successor, from, to, type);
+}
+
+bool
 BacktrackingAllocator::resolveControlFlow()
 {
     // Add moves to handle changing assignments for vregs over their lifetime.
     JitSpew(JitSpew_RegAlloc, "Resolving control flow (vreg loop)");
 
     // Look for places where a register's assignment changes in the middle of a
     // basic block.
     MOZ_ASSERT(!vregs[0u].hasRanges());
@@ -2065,25 +2077,21 @@ BacktrackingAllocator::resolveControlFlo
 
                 LAllocation* input = phi->getOperand(k);
                 LiveRange* from = vreg(input).rangeFor(exitOf(predecessor), /* preferRegister = */ true);
                 MOZ_ASSERT(from);
 
                 if (!alloc().ensureBallast()) {
                     return false;
                 }
-                if (mSuccessor->numPredecessors() > 1) {
-                    MOZ_ASSERT(predecessor->mir()->numSuccessors() == 1);
-                    if (!moveAtExit(predecessor, from, to, def->type())) {
-                        return false;
-                    }
-                } else {
-                    if (!moveAtEntry(successor, from, to, def->type())) {
-                        return false;
-                    }
+
+                // Note: we have to use moveAtEdge both here and below (for edge
+                // resolution) to avoid conflicting moves. See bug 1493900.
+                if (!moveAtEdge(predecessor, successor, from, to, def->type())) {
+                    return false;
                 }
             }
         }
     }
 
     // Add moves to resolve graph edges with different allocations at their
     // source and target.
     for (size_t i = 1; i < graph.numVirtualRegisters(); i++) {
@@ -2111,25 +2119,18 @@ BacktrackingAllocator::resolveControlFlo
                     if (targetRange->covers(exitOf(predecessor))) {
                         continue;
                     }
 
                     if (!alloc().ensureBallast()) {
                         return false;
                     }
                     LiveRange* from = reg.rangeFor(exitOf(predecessor), true);
-                    if (successor->mir()->numPredecessors() > 1) {
-                        MOZ_ASSERT(predecessor->mir()->numSuccessors() == 1);
-                        if (!moveAtExit(predecessor, from, targetRange, reg.type())) {
-                            return false;
-                        }
-                    } else {
-                        if (!moveAtEntry(successor, from, targetRange, reg.type())) {
-                            return false;
-                        }
+                    if (!moveAtEdge(predecessor, successor, from, targetRange, reg.type())) {
+                        return false;
                     }
                 }
             }
         }
     }
 
     return true;
 }
--- a/js/src/jit/BacktrackingAllocator.h
+++ b/js/src/jit/BacktrackingAllocator.h
@@ -825,16 +825,19 @@ class BacktrackingAllocator : protected 
                                   LDefinition::Type type) {
         if (from->bundle()->allocation() == to->bundle()->allocation()) {
             return true;
         }
         LMoveGroup* moves = block->getEntryMoveGroup(alloc());
         return addMove(moves, from, to, type);
     }
 
+    MOZ_MUST_USE bool moveAtEdge(LBlock* predecessor, LBlock* successor, LiveRange* from,
+                                 LiveRange* to, LDefinition::Type type);
+
     // Debugging methods.
     void dumpAllocations();
 
     struct PrintLiveRange;
 
     bool minimalDef(LiveRange* range, LNode* ins);
     bool minimalUse(LiveRange* range, UsePosition* use);
     bool minimalBundle(LiveBundle* bundle, bool* pfixed = nullptr);
--- a/modules/libpref/init/all.js
+++ b/modules/libpref/init/all.js
@@ -4637,16 +4637,21 @@ pref("toolkit.zoomManager.zoomValues", "
 // before it starts to discard already displayed frames and redecode them as
 // necessary.
 pref("image.animated.decode-on-demand.threshold-kb", 20480);
 
 // The minimum number of frames we want to have buffered ahead of an
 // animation's currently displayed frame.
 pref("image.animated.decode-on-demand.batch-size", 6);
 
+// Whether we should recycle already displayed frames instead of discarding
+// them. This saves on the allocation itself, and may be able to reuse the
+// contents as well. Only applies if generating full frames.
+pref("image.animated.decode-on-demand.recycle", true);
+
 // Whether we should generate full frames at decode time or partial frames which
 // are combined at display time (historical behavior and default).
 pref("image.animated.generate-full-frames", false);
 
 // Resume an animated image from the last displayed frame rather than
 // advancing when out of view.
 pref("image.animated.resume-from-last-displayed", true);
 
--- a/services/settings/dumps/main/moz.build
+++ b/services/settings/dumps/main/moz.build
@@ -1,12 +1,13 @@
 # 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/.
 
 FINAL_TARGET_FILES.defaults.settings.main += [
     'example.json',
     'language-dictionaries.json',
     'onboarding.json',
+    'sites-classification.json',
 ]
 
 if CONFIG['MOZ_BUILD_APP'] == 'browser':
     DIST_SUBDIR = 'browser'
new file mode 100644
--- /dev/null
+++ b/services/settings/dumps/main/sites-classification.json
@@ -0,0 +1,271 @@
+{
+  "data": [
+    {
+      "type": "search-engine-mozilla-tag",
+      "weight": 4,
+      "criteria": [
+        {
+          "sld": "google",
+          "params": [
+            {
+              "key": "client",
+              "prefix": "firefox"
+            }
+          ]
+        },
+        {
+          "params": [
+            {
+              "key": "t",
+              "prefix": "ff"
+            }
+          ],
+          "hostname": "duckduckgo.com"
+        },
+        {
+          "params": [
+            {
+              "key": "tn",
+              "prefix": "monline_dg"
+            }
+          ],
+          "hostname": "baidu.com"
+        },
+        {
+          "params": [
+            {
+              "key": "pc",
+              "prefix": "MOZ"
+            }
+          ],
+          "hostname": "bing.com"
+        },
+        {
+          "params": [
+            {
+              "key": "pc",
+              "prefix": "MZ"
+            }
+          ],
+          "hostname": "bing.com"
+        }
+      ],
+      "id": "351864eb-eca8-4c84-b036-b847d046c864",
+      "last_modified": 1539907365852
+    },
+    {
+      "type": "search-engine-other-tag",
+      "weight": 3,
+      "criteria": [
+        {
+          "sld": "google",
+          "params": [
+            {
+              "key": "client"
+            }
+          ]
+        },
+        {
+          "params": [
+            {
+              "key": "t"
+            }
+          ],
+          "hostname": "duckduckgo.com"
+        },
+        {
+          "params": [
+            {
+              "key": "tn"
+            }
+          ],
+          "hostname": "baidu.com"
+        },
+        {
+          "params": [
+            {
+              "key": "pc"
+            }
+          ],
+          "hostname": "bing.com"
+        },
+        {
+          "params": [
+            {
+              "key": "fr"
+            }
+          ],
+          "hostname": "search.yahoo.com"
+        },
+        {
+          "params": [
+            {
+              "key": "hsimp"
+            }
+          ],
+          "hostname": "search.yahoo.com"
+        }
+      ],
+      "id": "9a3ed0f2-4207-4d03-8bed-6c38242dbdbd",
+      "last_modified": 1539907352029
+    },
+    {
+      "type": "search-engine",
+      "weight": 2,
+      "criteria": [
+        {
+          "sld": "google"
+        },
+        {
+          "hostname": "duckduckgo.com"
+        },
+        {
+          "hostname": "baidu.com"
+        },
+        {
+          "hostname": "bing.com"
+        },
+        {
+          "hostname": "search.yahoo.com"
+        },
+        {
+          "sld": "yandex"
+        }
+      ],
+      "id": "c32a3278-e9ba-4090-8269-49d262fdea04",
+      "last_modified": 1539907334747
+    },
+    {
+      "type": "news-portal",
+      "weight": 1,
+      "criteria": [
+        {
+          "sld": "yahoo"
+        },
+        {
+          "hostname": "msn.com"
+        },
+        {
+          "hostname": "digg.com"
+        },
+        {
+          "hostname": "aol.com"
+        },
+        {
+          "hostname": "cnn.com"
+        },
+        {
+          "hostname": "bbc.com"
+        },
+        {
+          "hostname": "bbc.co.uk"
+        },
+        {
+          "hostname": "nytimes.com"
+        },
+        {
+          "hostname": "qq.com"
+        },
+        {
+          "hostname": "sohu.com"
+        }
+      ],
+      "id": "12743b39-7f79-4620-bc37-a87b8ab2ba46",
+      "last_modified": 1539907318995
+    },
+    {
+      "type": "social-media",
+      "weight": 1,
+      "criteria": [
+        {
+          "hostname": "facebook.com"
+        },
+        {
+          "hostname": "twitter.com"
+        },
+        {
+          "hostname": "instagram.com"
+        },
+        {
+          "hostname": "reddit.com"
+        },
+        {
+          "hostname": "myspace.com"
+        },
+        {
+          "hostname": "linkedin.com"
+        },
+        {
+          "hostname": "pinterest.com"
+        },
+        {
+          "hostname": "quora.com"
+        },
+        {
+          "hostname": "tuenti.com"
+        },
+        {
+          "hostname": "tumblr.com"
+        },
+        {
+          "hostname": "untappd.com"
+        },
+        {
+          "hostname": "yammer.com"
+        },
+        {
+          "hostname": "slack.com"
+        },
+        {
+          "hostname": "youtube.com"
+        },
+        {
+          "hostname": "vk.com"
+        },
+        {
+          "hostname": "twitch.tv"
+        }
+      ],
+      "id": "bdde6edd-83a5-4c34-b302-4810e9d10d04",
+      "last_modified": 1539907302037
+    },
+    {
+      "type": "ecommerce",
+      "weight": 1,
+      "criteria": [
+        {
+          "sld": "amazon"
+        },
+        {
+          "sld": "ebay"
+        },
+        {
+          "hostname": "alibaba.com"
+        },
+        {
+          "hostname": "walmart.com"
+        },
+        {
+          "hostname": "taobao.com"
+        },
+        {
+          "hostname": "tmall.com"
+        },
+        {
+          "hostname": "flipkart.com"
+        },
+        {
+          "hostname": "snapdeal.com"
+        },
+        {
+          "hostname": "bestbuy.com"
+        },
+        {
+          "hostname": "jabong.com"
+        }
+      ],
+      "id": "48ec9db9-0de1-49aa-9b82-1a2372dce31e",
+      "last_modified": 1539907283705
+    }
+  ]
+}
--- a/taskcluster/taskgraph/actions/retrigger.py
+++ b/taskcluster/taskgraph/actions/retrigger.py
@@ -34,18 +34,16 @@ logger = logging.getLogger(__name__)
     order=11,
     context=[
         {'kind': 'decision-task'},
         {'kind': 'action-callback'},
         {'kind': 'cron-task'},
     ],
 )
 def retrigger_decision_action(parameters, graph_config, input, task_group_id, task_id, task):
-    decision_task_id, full_task_graph, label_to_taskid = fetch_graph_and_labels(
-        parameters, graph_config)
     """For a single task, we try to just run exactly the same task once more.
     It's quite possible that we don't have the scopes to do so (especially for
     an action), but this is best-effort."""
 
     # make all of the timestamps relative; they will then be turned back into
     # absolute timestamps relative to the current time.
     task = relativize_datestamps(task)
     create_task_from_def(slugid(), task, parameters['level'])
deleted file mode 100644
--- a/testing/web-platform/meta/dom/nodes/Node-replaceChild.html.ini
+++ /dev/null
@@ -1,4 +0,0 @@
-[Node-replaceChild.html]
-  [If node is an inclusive ancestor of the context node, a HierarchyRequestError should be thrown.]
-    expected: FAIL
-
--- a/testing/web-platform/tests/dom/nodes/Node-insertBefore.html
+++ b/testing/web-platform/tests/dom/nodes/Node-insertBefore.html
@@ -1,13 +1,19 @@
 <!DOCTYPE html>
 <title>Node.insertBefore</title>
 <script src="/resources/testharness.js"></script>
 <script src="/resources/testharnessreport.js"></script>
 <div id="log"></div>
+<!-- First test shared pre-insertion checks that work similarly for replaceChild
+     and insertBefore -->
+<script>
+  var insertFunc = Node.prototype.insertBefore;
+</script>
+<script src="pre-insertion-checks.js"></script>
 <script>
 function testLeafNode(nodeName, createNodeFunction) {
   test(function() {
     var node = createNodeFunction();
     assert_throws(new TypeError(), function() { node.insertBefore(null, null) })
   }, "Calling insertBefore with a non-Node first argument on a leaf node " + nodeName + " must throw TypeError.")
   test(function() {
     var node = createNodeFunction();
--- a/testing/web-platform/tests/dom/nodes/Node-replaceChild.html
+++ b/testing/web-platform/tests/dom/nodes/Node-replaceChild.html
@@ -1,15 +1,21 @@
 <!DOCTYPE html>
 <meta charset=utf-8>
 <title>Node.replaceChild</title>
 <script src="/resources/testharness.js"></script>
 <script src="/resources/testharnessreport.js"></script>
 <body><a><b></b><c></c></a>
 <div id="log"></div>
+<!-- First test shared pre-insertion checks that work similarly for replaceChild
+     and insertBefore -->
+<script>
+  var insertFunc = Node.prototype.replaceChild;
+</script>
+<script src="pre-insertion-checks.js"></script>
 <script>
 // IDL.
 test(function() {
   var a = document.createElement("div");
   assert_throws(new TypeError(), function() {
     a.replaceChild(null, null);
   });
 
@@ -17,50 +23,47 @@ test(function() {
   assert_throws(new TypeError(), function() {
     a.replaceChild(b, null);
   });
   assert_throws(new TypeError(), function() {
     a.replaceChild(null, b);
   });
 }, "Passing null to replaceChild should throw a TypeError.")
 
-// Step 1.
+// Step 3.
 test(function() {
   var a = document.createElement("div");
   var b = document.createElement("div");
   var c = document.createElement("div");
   assert_throws("NotFoundError", function() {
     a.replaceChild(b, c);
   });
 
   var d = document.createElement("div");
   d.appendChild(b);
   assert_throws("NotFoundError", function() {
     a.replaceChild(b, c);
   });
   assert_throws("NotFoundError", function() {
     a.replaceChild(b, a);
   });
-}, "If child's parent is not the context node, a NotFoundError exception should be thrown")
+}, "If child's parent is not the context node, a NotFoundError exception should be thrown");
+
+// Step 1.
 test(function() {
-  var nodes = [
-    document.implementation.createDocumentType("html", "", ""),
-    document.createTextNode("text"),
-    document.implementation.createDocument(null, "foo", null).createProcessingInstruction("foo", "bar"),
-    document.createComment("comment")
-  ];
+  var nodes = getNonParentNodes();
 
   var a = document.createElement("div");
   var b = document.createElement("div");
   nodes.forEach(function(node) {
     assert_throws("HierarchyRequestError", function() {
       node.replaceChild(a, b);
     });
   });
-}, "If the context node is not a node that can contain children, a NotFoundError exception should be thrown")
+}, "If the context node is not a node that can contain children, a HierarchyRequestError exception should be thrown")
 
 // Step 2.
 test(function() {
   var a = document.createElement("div");
   var b = document.createElement("div");
 
   assert_throws("HierarchyRequestError", function() {
     a.replaceChild(a, a);
@@ -73,30 +76,30 @@ test(function() {
 
   var c = document.createElement("div");
   c.appendChild(a);
   assert_throws("HierarchyRequestError", function() {
     a.replaceChild(c, b);
   });
 }, "If node is an inclusive ancestor of the context node, a HierarchyRequestError should be thrown.")
 
-// Step 3.1.
+// Steps 4/5.
 test(function() {
   var doc = document.implementation.createHTMLDocument("title");
   var doc2 = document.implementation.createHTMLDocument("title2");
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(doc2, doc.documentElement);
   });
 
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(doc.createTextNode("text"), doc.documentElement);
   });
 }, "If the context node is a document, inserting a document or text node should throw a HierarchyRequestError.")
 
-// Step 3.2.1.
+// Step 6.1.
 test(function() {
   var doc = document.implementation.createHTMLDocument("title");
 
   var df = doc.createDocumentFragment();
   df.appendChild(doc.createElement("a"));
   df.appendChild(doc.createElement("b"));
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(df, doc.documentElement);
@@ -122,17 +125,17 @@ test(function() {
   var df = doc.createDocumentFragment();
   df.appendChild(doc.createElement("a"));
   df.appendChild(doc.createElement("b"));
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(df, doc.doctype);
   });
 }, "If the context node is a document (without element children), inserting a DocumentFragment that contains multiple elements should throw a HierarchyRequestError.")
 
-// Step 3.2.2.
+// Step 6.1.
 test(function() {
   // The context node has an element child that is not /child/.
   var doc = document.implementation.createHTMLDocument("title");
   var comment = doc.appendChild(doc.createComment("foo"));
   assert_array_equals(doc.childNodes, [doc.doctype, doc.documentElement, comment]);
 
   var df = doc.createDocumentFragment();
   df.appendChild(doc.createElement("a"));
@@ -152,17 +155,17 @@ test(function() {
 
   var df = doc.createDocumentFragment();
   df.appendChild(doc.createElement("a"));
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(df, comment);
   });
 }, "If the context node is a document, inserting a DocumentFragment with an element before the doctype should throw a HierarchyRequestError.")
 
-// Step 3.3.
+// Step 6.2.
 test(function() {
   var doc = document.implementation.createHTMLDocument("title");
   var comment = doc.appendChild(doc.createComment("foo"));
   assert_array_equals(doc.childNodes, [doc.doctype, doc.documentElement, comment]);
 
   var a = doc.createElement("a");
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(a, comment);
@@ -178,17 +181,17 @@ test(function() {
   assert_array_equals(doc.childNodes, [comment, doc.doctype]);
 
   var a = doc.createElement("a");
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(a, comment);
   });
 }, "If the context node is a document, inserting an element before the doctype should throw a HierarchyRequestError.")
 
-// Step 3.4.
+// Step 6.3.
 test(function() {
   var doc = document.implementation.createHTMLDocument("title");
   var comment = doc.insertBefore(doc.createComment("foo"), doc.firstChild);
   assert_array_equals(doc.childNodes, [comment, doc.doctype, doc.documentElement]);
 
   var doctype = document.implementation.createDocumentType("html", "", "");
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(doctype, comment);
@@ -204,17 +207,17 @@ test(function() {
   assert_array_equals(doc.childNodes, [doc.documentElement, comment]);
 
   var doctype = document.implementation.createDocumentType("html", "", "");
   assert_throws("HierarchyRequestError", function() {
     doc.replaceChild(doctype, comment);
   });
 }, "If the context node is a document, inserting a doctype after the document element should throw a HierarchyRequestError.")
 
-// Step 4.
+// Steps 4/5.
 test(function() {
   var df = document.createDocumentFragment();
   var a = df.appendChild(document.createElement("a"));
 
   var doc = document.implementation.createHTMLDocument("title");
   assert_throws("HierarchyRequestError", function() {
     df.replaceChild(doc, a);
   });
@@ -337,9 +340,10 @@ test(function() {
   var child = document.createElement("div");
   parent.appendChild(child);
   var df = document.createDocumentFragment();
   var fragChild = df.appendChild(document.createElement("div"));
   fragChild.setAttribute("id", TEST_ID);
   parent.replaceChild(df, child);
   assert_equals(document.getElementById(TEST_ID), fragChild, "should not be null");
 }, "Replacing an element with a DocumentFragment should allow a child of the DocumentFragment to be found by Id.")
+
 </script>
new file mode 100644
--- /dev/null
+++ b/testing/web-platform/tests/dom/nodes/pre-insertion-checks.js
@@ -0,0 +1,108 @@
+function getNonParentNodes() {
+  return [
+    document.implementation.createDocumentType("html", "", ""),
+    document.createTextNode("text"),
+    document.implementation.createDocument(null, "foo", null).createProcessingInstruction("foo", "bar"),
+    document.createComment("comment"),
+    document.implementation.createDocument(null, "foo", null).createCDATASection("data"),
+  ];
+}
+
+function getNonInsertableNodes() {
+  return [
+    document.implementation.createHTMLDocument("title")
+  ];
+}
+
+function getNonDocumentParentNodes() {
+  return [
+    document.createElement("div"),
+    document.createDocumentFragment(),
+  ];
+}
+
+// Test that the steps happen in the right order, to the extent that it's
+// observable.   The variable names "parent", "child", and "node" match the
+// corresponding variables in the replaceChild algorithm in these tests.
+
+// Step 1 happens before step 3.
+test(function() {
+  var illegalParents = getNonParentNodes();
+  var child = document.createElement("div");
+  var node = document.createElement("div");
+  illegalParents.forEach(function (parent) {
+    assert_throws("HierarchyRequestError", function() {
+      insertFunc.call(parent, node, child);
+    });
+  });
+}, "Should check the 'parent' type before checking whether 'child' is a child of 'parent'");
+
+// Step 2 happens before step 3.
+test(function() {
+  var parent = document.createElement("div");
+  var child = document.createElement("div");
+  var node = document.createElement("div");
+
+  node.appendChild(parent);
+  assert_throws("HierarchyRequestError", function() {
+    insertFunc.call(parent, node, child);
+  });
+}, "Should check that 'node' is not an ancestor of 'parent' before checking whether 'child' is a child of 'parent'");
+
+// Step 3 happens before step 4.
+test(function() {
+  var parent = document.createElement("div");
+  var child = document.createElement("div");
+
+  var illegalChildren = getNonInsertableNodes();
+  illegalChildren.forEach(function (node) {
+    assert_throws("NotFoundError", function() {
+      insertFunc.call(parent, node, child);
+    });
+  });
+}, "Should check whether 'child' is a child of 'parent' before checking whether 'node' is of a type that can have a parent.");
+
+
+// Step 3 happens before step 5.
+test(function() {
+  var child = document.createElement("div");
+
+  var node = document.createTextNode("");
+  var parent = document.implementation.createDocument(null, "foo", null);
+  assert_throws("NotFoundError", function() {
+    insertFunc.call(parent, node, child);
+  });
+
+  node = document.implementation.createDocumentType("html", "", "");
+  getNonDocumentParentNodes().forEach(function (parent) {
+    assert_throws("NotFoundError", function() {
+      insertFunc.call(parent, node, child);
+    });
+  });
+}, "Should check whether 'child' is a child of 'parent' before checking whether 'node' is of a type that can have a parent of the type that 'parent' is.");
+
+// Step 3 happens before step 6.
+test(function() {
+  var child = document.createElement("div");
+  var parent = document.implementation.createDocument(null, null, null);
+
+  var node = document.createDocumentFragment();
+  node.appendChild(document.createElement("div"));
+  node.appendChild(document.createElement("div"));
+  assert_throws("NotFoundError", function() {
+    insertFunc.call(parent, node, child);
+  });
+
+  node = document.createElement("div");
+  parent.appendChild(document.createElement("div"));
+  assert_throws("NotFoundError", function() {
+    insertFunc.call(parent, node, child);
+  });
+
+  parent.firstChild.remove();
+  parent.appendChild(document.implementation.createDocumentType("html", "", ""));
+  node = document.implementation.createDocumentType("html", "", "")
+  assert_throws("NotFoundError", function() {
+    insertFunc.call(parent, node, child);
+  });
+}, "Should check whether 'child' is a child of 'parent' before checking whether 'node' can be inserted into the document given the kids the document has right now.");