--- a/servo/components/style/gecko/data.rs
+++ b/servo/components/style/gecko/data.rs
@@ -13,17 +13,17 @@ use gecko_bindings::sugar::ownership::{H
 use media_queries::Device;
 use parking_lot::RwLock;
 use properties::ComputedValues;
 use shared_lock::{Locked, StylesheetGuards, SharedRwLockReadGuard};
 use std::collections::HashMap;
 use std::sync::Arc;
 use std::sync::mpsc::{Receiver, Sender, channel};
 use stylesheet_set::StylesheetSet;
-use stylesheets::{FontFaceRule, Origin};
+use stylesheets::{FontFaceRule, Origin, Stylesheet};
 use stylist::{ExtraStyleData, Stylist};
 
 /// The container for data that a Servo-backed Gecko document needs to style
 /// itself.
 pub struct PerDocumentStyleDataImpl {
     /// Rule processor.
     pub stylist: Arc<Stylist>,
 
@@ -101,18 +101,19 @@ impl PerDocumentStyleDataImpl {
         }
 
         let mut stylist = Arc::get_mut(&mut self.stylist).unwrap();
         let mut extra_data = ExtraStyleData {
             font_faces: &mut self.font_faces,
         };
 
         let author_style_disabled = self.stylesheets.author_style_disabled();
-        let stylesheets = self.stylesheets.flush();
-        stylist.update(stylesheets,
+        let mut stylesheets = Vec::<Arc<Stylesheet>>::new();
+        self.stylesheets.flush(&mut stylesheets);
+        stylist.update(stylesheets.as_slice(),
                        &StylesheetGuards::same(guard),
                        /* ua_sheets = */ None,
                        /* stylesheets_changed = */ true,
                        author_style_disabled,
                        &mut extra_data);
     }
 
     /// Get the default computed values for this document.

--- a/servo/components/style/gecko_bindings/bindings.rs
+++ b/servo/components/style/gecko_bindings/bindings.rs
@@ -1565,35 +1565,37 @@ extern "C" {
      -> RawServoStyleSetOwned;
 }
 extern "C" {
     pub fn Servo_StyleSet_RebuildData(set: RawServoStyleSetBorrowed);
 }
 extern "C" {
     pub fn Servo_StyleSet_AppendStyleSheet(set: RawServoStyleSetBorrowed,
                                            sheet: RawServoStyleSheetBorrowed,
+                                           unique_id: u32,
                                            flush: bool);
 }
 extern "C" {
     pub fn Servo_StyleSet_PrependStyleSheet(set: RawServoStyleSetBorrowed,
                                             sheet: RawServoStyleSheetBorrowed,
+                                            unique_id: u32,
                                             flush: bool);
 }
 extern "C" {
     pub fn Servo_StyleSet_RemoveStyleSheet(set: RawServoStyleSetBorrowed,
-                                           sheet: RawServoStyleSheetBorrowed,
+                                           unique_id: u32,
                                            flush: bool);
 }
 extern "C" {
     pub fn Servo_StyleSet_InsertStyleSheetBefore(set:
                                                      RawServoStyleSetBorrowed,
                                                  sheet:
                                                      RawServoStyleSheetBorrowed,
-                                                 reference:
-                                                     RawServoStyleSheetBorrowed,
+                                                 unique_id: u32,
+                                                 before_unique_id: u32,
                                                  flush: bool);
 }
 extern "C" {
     pub fn Servo_StyleSet_FlushStyleSheets(set: RawServoStyleSetBorrowed);
 }
 extern "C" {
     pub fn Servo_StyleSet_NoteStyleSheetsChanged(set:
                                                      RawServoStyleSetBorrowed,

--- a/servo/components/style/stylesheet_set.rs
+++ b/servo/components/style/stylesheet_set.rs
@@ -1,82 +1,101 @@
 /* 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/. */
 
 //! A centralized set of stylesheets for a document.
 
-use arc_ptr_eq;
 use std::sync::Arc;
 use stylesheets::Stylesheet;
 
+/// Entry for a StylesheetSet. We don't bother creating a constructor, because
+/// there's no sensible defaults for the member variables.
+pub struct StylesheetSetEntry {
+    unique_id: u32,
+    sheet: Arc<Stylesheet>,
+}
+
 /// The set of stylesheets effective for a given document.
 pub struct StylesheetSet {
-    /// The actual list of all the stylesheets that apply to the given document.
+    /// The actual list of all the stylesheets that apply to the given document,
+    /// each stylesheet associated with a unique ID.
     ///
     /// This is only a list of top-level stylesheets, and as such it doesn't
     /// include recursive `@import` rules.
-    stylesheets: Vec<Arc<Stylesheet>>,
+    entries: Vec<StylesheetSetEntry>,
 
-    /// Whether the stylesheets list above has changed since the last restyle.
+    /// Whether the entries list above has changed since the last restyle.
     dirty: bool,
 
     /// Has author style been disabled?
     author_style_disabled: bool,
 }
 
 impl StylesheetSet {
     /// Create a new empty StylesheetSet.
     pub fn new() -> Self {
         StylesheetSet {
-            stylesheets: vec![],
+            entries: vec![],
             dirty: false,
             author_style_disabled: false,
         }
     }
 
     /// Returns whether author styles have been disabled for the current
     /// stylesheet set.
     pub fn author_style_disabled(&self) -> bool {
         self.author_style_disabled
     }
 
-    fn remove_stylesheet_if_present(&mut self, sheet: &Arc<Stylesheet>) {
-        self.stylesheets.retain(|x| !arc_ptr_eq(x, sheet));
+    fn remove_stylesheet_if_present(&mut self, unique_id: u32) {
+        self.entries.retain(|x| x.unique_id != unique_id);
     }
 
     /// Appends a new stylesheet to the current set.
-    pub fn append_stylesheet(&mut self, sheet: &Arc<Stylesheet>) {
-        self.remove_stylesheet_if_present(sheet);
-        self.stylesheets.push(sheet.clone());
+    pub fn append_stylesheet(&mut self, sheet: &Arc<Stylesheet>,
+                             unique_id: u32) {
+        self.remove_stylesheet_if_present(unique_id);
+        self.entries.push(StylesheetSetEntry {
+            unique_id: unique_id,
+            sheet: sheet.clone(),
+        });
         self.dirty = true;
     }
 
     /// Prepend a new stylesheet to the current set.
-    pub fn prepend_stylesheet(&mut self, sheet: &Arc<Stylesheet>) {
-        self.remove_stylesheet_if_present(sheet);
-        self.stylesheets.insert(0, sheet.clone());
+    pub fn prepend_stylesheet(&mut self, sheet: &Arc<Stylesheet>,
+                              unique_id: u32) {
+        self.remove_stylesheet_if_present(unique_id);
+        self.entries.insert(0, StylesheetSetEntry {
+            unique_id: unique_id,
+            sheet: sheet.clone(),
+        });
         self.dirty = true;
     }
 
     /// Insert a given stylesheet before another stylesheet in the document.
     pub fn insert_stylesheet_before(&mut self,
                                     sheet: &Arc<Stylesheet>,
-                                    before: &Arc<Stylesheet>) {
-        self.remove_stylesheet_if_present(sheet);
-        let index = self.stylesheets.iter().position(|x| {
-            arc_ptr_eq(x, before)
-        }).expect("`before` stylesheet not found");
-        self.stylesheets.insert(index, sheet.clone());
+                                    unique_id: u32,
+                                    before_unique_id: u32) {
+        self.remove_stylesheet_if_present(unique_id);
+        let index = self.entries.iter().position(|x| {
+            x.unique_id == before_unique_id
+        }).expect("`before_unique_id` stylesheet not found");
+        self.entries.insert(index, StylesheetSetEntry {
+            unique_id: unique_id,
+            sheet: sheet.clone(),
+        });
         self.dirty = true;
     }
 
     /// Remove a given stylesheet from the set.
-    pub fn remove_stylesheet(&mut self, sheet: &Arc<Stylesheet>) {
-        self.remove_stylesheet_if_present(sheet);
+    pub fn remove_stylesheet(&mut self, unique_id: u32) {
+        self.remove_stylesheet_if_present(unique_id);
         self.dirty = true;
     }
 
     /// Notes that the author style has been disabled for this document.
     pub fn set_author_style_disabled(&mut self, disabled: bool) {
         if self.author_style_disabled == disabled {
             return;
         }
@@ -85,19 +104,21 @@ impl StylesheetSet {
     }
 
     /// Returns whether the given set has changed from the last flush.
     pub fn has_changed(&self) -> bool {
         self.dirty
     }
 
     /// Flush the current set, unmarking it as dirty.
-    pub fn flush(&mut self) -> &[Arc<Stylesheet>] {
+    pub fn flush(&mut self, sheets: &mut Vec<Arc<Stylesheet>>) {
         self.dirty = false;
-        &self.stylesheets
+        for entry in &self.entries {
+            sheets.push(entry.sheet.clone())
+        }
     }
 
     /// Mark the stylesheets as dirty, because something external may have
     /// invalidated it.
     ///
     /// FIXME(emilio): Make this more granular.
     pub fn force_dirty(&mut self) {
         self.dirty = true;

--- a/servo/ports/geckolib/glue.rs
+++ b/servo/ports/geckolib/glue.rs
@@ -588,66 +588,67 @@ pub extern "C" fn Servo_StyleSheet_Clear
     let sheet = Stylesheet::as_arc(&stylesheet);
     Stylesheet::update_from_str(&sheet, input, url_data,
                                 loader, &RustLogReporter);
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_AppendStyleSheet(raw_data: RawServoStyleSetBorrowed,
                                                   raw_sheet: RawServoStyleSheetBorrowed,
+                                                  unique_id: u32,
                                                   flush: bool) {
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
     let sheet = HasArcFFI::as_arc(&raw_sheet);
-    data.stylesheets.append_stylesheet(sheet);
+    data.stylesheets.append_stylesheet(sheet, unique_id);
     if flush {
         data.flush_stylesheets(&guard);
     }
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_PrependStyleSheet(raw_data: RawServoStyleSetBorrowed,
                                                    raw_sheet: RawServoStyleSheetBorrowed,
+                                                   unique_id: u32,
                                                    flush: bool) {
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
     let sheet = HasArcFFI::as_arc(&raw_sheet);
-    data.stylesheets.prepend_stylesheet(sheet);
+    data.stylesheets.prepend_stylesheet(sheet, unique_id);
     if flush {
         data.flush_stylesheets(&guard);
     }
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_InsertStyleSheetBefore(raw_data: RawServoStyleSetBorrowed,
                                                         raw_sheet: RawServoStyleSheetBorrowed,
-                                                        raw_reference: RawServoStyleSheetBorrowed,
+                                                        unique_id: u32,
+                                                        before_unique_id: u32,
                                                         flush: bool) {
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
     let sheet = HasArcFFI::as_arc(&raw_sheet);
-    let reference = HasArcFFI::as_arc(&raw_reference);
-    data.stylesheets.insert_stylesheet_before(sheet, reference);
+    data.stylesheets.insert_stylesheet_before(sheet, unique_id, before_unique_id);
     if flush {
         data.flush_stylesheets(&guard);
     }
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_RemoveStyleSheet(raw_data: RawServoStyleSetBorrowed,
-                                                  raw_sheet: RawServoStyleSheetBorrowed,
+                                                  unique_id: u32,
                                                   flush: bool) {
     let global_style_data = &*GLOBAL_STYLE_DATA;
     let guard = global_style_data.shared_lock.read();
     let mut data = PerDocumentStyleData::from_ffi(raw_data).borrow_mut();
-    let sheet = HasArcFFI::as_arc(&raw_sheet);
-    data.stylesheets.remove_stylesheet(sheet);
+    data.stylesheets.remove_stylesheet(unique_id);
     if flush {
         data.flush_stylesheets(&guard);
     }
 }
 
 #[no_mangle]
 pub extern "C" fn Servo_StyleSet_FlushStyleSheets(raw_data: RawServoStyleSetBorrowed) {
     let global_style_data = &*GLOBAL_STYLE_DATA;