--- a/dom/animation/test/chrome/test_animation_observers_async.html
+++ b/dom/animation/test/chrome/test_animation_observers_async.html
@@ -139,16 +139,56 @@ function assert_records(expected, desc) 
   }
   for (var i = 0; i < records.length; i++) {
     assert_record_list(records[i].addedAnimations, expected[i].added, desc, i, "addedAnimations");
     assert_record_list(records[i].changedAnimations, expected[i].changed, desc, i, "changedAnimations");
     assert_record_list(records[i].removedAnimations, expected[i].removed, desc, i, "removedAnimations");
   }
 }
 
+function assert_records_any_order(expected, desc) {
+  // Generate a unique label for each Animation object.
+  let animation_labels = new Map();
+  let animation_counter = 0;
+  for (let record of gRecords) {
+    for (let a of [...record.addedAnimations, ...record.changedAnimations, ...record.removedAnimations]) {
+      if (!animation_labels.has(a)) {
+        animation_labels.set(a, ++animation_counter);
+      }
+    }
+  }
+  for (let record of expected) {
+    for (let a of [...record.added, ...record.changed, ...record.removed]) {
+      if (!animation_labels.has(a)) {
+        animation_labels.set(a, ++animation_counter);
+      }
+    }
+  }
+
+  function record_label(record) {
+    // Generate a label of the form:
+    //
+    //   <added-animations>:<changed-animations>:<removed-animations>
+    let added   = record.addedAnimations   || record.added;
+    let changed = record.changedAnimations || record.changed;
+    let removed = record.removedAnimations || record.removed;
+    return [added  .map(a => animation_labels.get(a)).sort().join(),
+            changed.map(a => animation_labels.get(a)).sort().join(),
+            removed.map(a => animation_labels.get(a)).sort().join()]
+           .join(":");
+  }
+
+  // Sort records by their label.
+  gRecords.sort((a, b) => record_label(a) < record_label(b));
+  expected.sort((a, b) => record_label(a) < record_label(b));
+
+  // Assert the sorted record lists are equal.
+  assert_records(expected, desc);
+}
+
 // -- Tests ------------------------------------------------------------------
 
 // We run all tests first targeting the div and observing the div, then again
 // targeting the div and observing its parent while using the subtree:true
 // MutationObserver option.
 
 [
   { observe: div,            target: div, subtree: false },
@@ -1109,29 +1149,27 @@ addAsyncAnimTest("tree_ordering", { obse
   var childBPseudoAnimations =
     [ for (x of docAnims) if (x.effect.target.parentElement == childB) x ];
 
   // The order in which we get the corresponding records is currently
   // based on the order we visit these nodes when updating styles.
   //
   // That is because we don't do any document-level batching of animation
   // mutation records when we flush styles. We may introduce that in the
-  // future but for now all we are interested in testing here is that the order
-  // these records are dispatched is consistent between runs.
-  //
-  // We currently expect to get records in order div::after, childA, childB,
-  // childB::before, div, div::before
+  // future but for now all we are interested in testing here is that the
+  // right records are generated, but we allow them to occur in any order.
   yield waitForFrame();
-  assert_records([{ added: divAfterAnimations, changed: [], removed: [] },
-                  { added: childAAnimations, changed: [], removed: [] },
-                  { added: childBAnimations, changed: [], removed: [] },
-                  { added: childBPseudoAnimations, changed: [], removed: [] },
-                  { added: divAnimations, changed: [], removed: [] },
-                  { added: divBeforeAnimations, changed: [], removed: [] }],
-                 "records after simultaneous animation start");
+  assert_records_any_order(
+    [{ added: divAfterAnimations, changed: [], removed: [] },
+     { added: childAAnimations, changed: [], removed: [] },
+     { added: childBAnimations, changed: [], removed: [] },
+     { added: childBPseudoAnimations, changed: [], removed: [] },
+     { added: divAnimations, changed: [], removed: [] },
+     { added: divBeforeAnimations, changed: [], removed: [] }],
+    "records after simultaneous animation start");
 
   // The one case where we *do* currently perform document-level (or actually
   // timeline-level) batching is when animations are updated from a refresh
   // driver tick. In particular, this means that when animations finish
   // naturally the removed records should be dispatched according to the
   // position of the elements in the tree.
 
   // First, flatten the set of animations. we put the animations targeting to