--- a/servo/components/style/context.rs
+++ b/servo/components/style/context.rs
@@ -226,17 +226,17 @@ impl Clone for EagerPseudoCascadeInputs 
         }
         EagerPseudoCascadeInputs(Some(inputs))
     }
 }
 
 impl EagerPseudoCascadeInputs {
     /// Construct inputs from previous cascade results, if any.
     fn new_from_style(styles: &EagerPseudoStyles) -> Self {
-        EagerPseudoCascadeInputs(styles.as_array().map(|styles| {
+        EagerPseudoCascadeInputs(styles.as_optional_array().map(|styles| {
             let mut inputs: [Option<CascadeInputs>; EAGER_PSEUDO_COUNT] = Default::default();
             for i in 0..EAGER_PSEUDO_COUNT {
                 inputs[i] = styles[i].as_ref().map(|s| CascadeInputs::new_from_style(s));
             }
             inputs
         }))
     }
 

--- a/servo/components/style/data.rs
+++ b/servo/components/style/data.rs
@@ -157,30 +157,40 @@ impl fmt::Debug for EagerPseudoArray {
             if let Some(ref values) = self[i] {
                 write!(f, "{:?}: {:?}, ", PseudoElement::from_eager_index(i), &values.rules)?;
             }
         }
         write!(f, "}}")
     }
 }
 
+// Can't use [None; EAGER_PSEUDO_COUNT] here because it complains
+// about Copy not being implemented for our Arc type.
+const EMPTY_PSEUDO_ARRAY: &'static EagerPseudoArrayInner = &[None, None, None, None];
+
 impl EagerPseudoStyles {
     /// Returns whether there are any pseudo styles.
     pub fn is_empty(&self) -> bool {
         self.0.is_none()
     }
 
     /// Grabs a reference to the list of styles, if they exist.
-    pub fn as_array(&self) -> Option<&EagerPseudoArrayInner> {
+    pub fn as_optional_array(&self) -> Option<&EagerPseudoArrayInner> {
         match self.0 {
             None => None,
             Some(ref x) => Some(&x.0),
         }
     }
 
+    /// Grabs a reference to the list of styles or a list of None if
+    /// there are no styles to be had.
+    pub fn as_array(&self) -> &EagerPseudoArrayInner {
+        self.as_optional_array().unwrap_or(EMPTY_PSEUDO_ARRAY)
+    }
+
     /// Returns a reference to the style for a given eager pseudo, if it exists.
     pub fn get(&self, pseudo: &PseudoElement) -> Option<&Arc<ComputedValues>> {
         debug_assert!(pseudo.is_eager());
         self.0.as_ref().and_then(|p| p[pseudo.eager_index()].as_ref())
     }
 
     /// Sets the style for the eager pseudo.
     pub fn set(&mut self, pseudo: &PseudoElement, value: Arc<ComputedValues>) {

--- a/servo/components/style/gecko/pseudo_element.rs
+++ b/servo/components/style/gecko/pseudo_element.rs
@@ -7,16 +7,18 @@
 //! Note that a few autogenerated bits of this live in
 //! `pseudo_element_definition.mako.rs`. If you touch that file, you probably
 //! need to update the checked-in files for Servo.
 
 use cssparser::{ToCss, serialize_identifier};
 use gecko_bindings::structs::{self, CSSPseudoElementType};
 use properties::{PropertyFlags, APPLIES_TO_FIRST_LETTER, APPLIES_TO_FIRST_LINE};
 use properties::APPLIES_TO_PLACEHOLDER;
+use properties::ComputedValues;
+use properties::longhands::display::computed_value as display;
 use selector_parser::{NonTSPseudoClass, PseudoElementCascadeType, SelectorImpl};
 use std::fmt;
 use string_cache::Atom;
 
 include!(concat!(env!("OUT_DIR"), "/gecko/pseudo_element_definition.rs"));
 
 impl ::selectors::parser::PseudoElement for PseudoElement {
     type Impl = SelectorImpl;
@@ -133,9 +135,19 @@ impl PseudoElement {
     pub fn property_restriction(&self) -> Option<PropertyFlags> {
         match *self {
             PseudoElement::FirstLetter => Some(APPLIES_TO_FIRST_LETTER),
             PseudoElement::FirstLine => Some(APPLIES_TO_FIRST_LINE),
             PseudoElement::Placeholder => Some(APPLIES_TO_PLACEHOLDER),
             _ => None,
         }
     }
+
+    /// Whether this pseudo-element should actually exist if it has
+    /// the given styles.
+    pub fn should_exist(&self,
+                        style: &ComputedValues) -> bool
+    {
+        let display = style.get_box().clone_display();
+        display != display::T::none &&
+            (!self.is_before_or_after() || !style.ineffective_content_property())
+    }
 }

--- a/servo/components/style/matching.rs
+++ b/servo/components/style/matching.rs
@@ -516,44 +516,49 @@ pub trait MatchMethods : TElement {
                 &mut data.restyle,
                 &old_primary_style,
                 new_primary_style,
                 None,
             )
         );
 
         if data.styles.pseudos.is_empty() && old_styles.pseudos.is_empty() {
-            return cascade_requirement;
-        }
-
-        // If it matched a different number of pseudos, reconstruct.
-        if data.styles.pseudos.is_empty() != old_styles.pseudos.is_empty() {
-            data.restyle.damage |= RestyleDamage::reconstruct();
+            // This is the common case; no need to examine pseudos here.
             return cascade_requirement;
         }
 
         let pseudo_styles =
-            old_styles.pseudos.as_array().unwrap().iter().zip(
-            data.styles.pseudos.as_array().unwrap().iter());
+            old_styles.pseudos.as_array().iter().zip(
+            data.styles.pseudos.as_array().iter());
 
         for (i, (old, new)) in pseudo_styles.enumerate() {
             match (old, new) {
                 (&Some(ref old), &Some(ref new)) => {
                     self.accumulate_damage_for(
                         context.shared,
                         &mut data.restyle,
                         old,
                         new,
                         Some(&PseudoElement::from_eager_index(i)),
                     );
                 }
                 (&None, &None) => {},
                 _ => {
-                    data.restyle.damage |= RestyleDamage::reconstruct();
-                    return cascade_requirement;
+                    // It's possible that we're switching from not having
+                    // ::before/::after at all to having styles for them but not
+                    // actually having a useful pseudo-element.  Check for that
+                    // case.
+                    let pseudo = PseudoElement::from_eager_index(i);
+                    if old.as_ref().map_or(false,
+                                           |s| pseudo.should_exist(s)) !=
+                        new.as_ref().map_or(false,
+                                            |s| pseudo.should_exist(s)) {
+                        data.restyle.damage |= RestyleDamage::reconstruct();
+                        return cascade_requirement;
+                    }
                 }
             }
         }
 
         cascade_requirement
     }
 
 
@@ -786,16 +791,19 @@ pub trait MatchMethods : TElement {
             // The style remains display:none.  The only case we need to care
             // about is if -moz-binding changed, and to generate a reconstruct
             // so that we can start the binding load.  Otherwise, there is no
             // need for damage.
             return RestyleDamage::compute_undisplayed_style_difference(old_values, new_values);
         }
 
         if pseudo.map_or(false, |p| p.is_before_or_after()) {
+            // FIXME(bz) This duplicates some of the logic in
+            // PseudoElement::should_exist, but it's not clear how best to share
+            // that logic without redoing the "get the display" work.
             let old_style_generates_no_pseudo =
                 old_style_is_display_none ||
                 old_values.ineffective_content_property();
 
             let new_style_generates_no_pseudo =
                 new_style_is_display_none ||
                 new_values.ineffective_content_property();
 

--- a/servo/components/style/servo/selector_parser.rs
+++ b/servo/components/style/servo/selector_parser.rs
@@ -8,17 +8,19 @@
 
 use {Atom, Prefix, Namespace, LocalName, CaseSensitivityExt};
 use attr::{AttrIdentifier, AttrValue};
 use cssparser::{Parser as CssParser, ToCss, serialize_identifier, CowRcStr};
 use dom::{OpaqueNode, TElement, TNode};
 use element_state::ElementState;
 use fnv::FnvHashMap;
 use invalidation::element::element_wrapper::ElementSnapshot;
+use properties::ComputedValues;
 use properties::PropertyFlags;
+use properties::longhands::display::computed_value as display;
 use selector_parser::{AttrValue as SelectorAttrValue, ElementExt, PseudoElementCascadeType, SelectorParser};
 use selectors::Element;
 use selectors::attr::{AttrSelectorOperation, NamespaceConstraint, CaseSensitivity};
 use selectors::parser::{SelectorMethods, SelectorParseError};
 use selectors::visitor::SelectorVisitor;
 use std::ascii::AsciiExt;
 use std::fmt;
 use std::fmt::Debug;
@@ -184,16 +186,26 @@ impl PseudoElement {
     /// Stub, only Gecko needs this
     pub fn pseudo_info(&self) { () }
 
     /// Property flag that properties must have to apply to this pseudo-element.
     #[inline]
     pub fn property_restriction(&self) -> Option<PropertyFlags> {
         None
     }
+
+    /// Whether this pseudo-element should actually exist if it has
+    /// the given styles.
+    pub fn should_exist(&self,
+                        style: &ComputedValues)
+    {
+        let display = style.get_box().clone_display();
+        display != display::T::none &&
+            (!self.is_before_or_after() || !style.ineffective_content_property())
+    }
 }
 
 /// The type used for storing pseudo-class string arguments.
 pub type PseudoClassStringArg = Box<str>;
 
 /// A non tree-structural pseudo-class.
 /// See https://drafts.csswg.org/selectors-4/#structural-pseudos
 #[derive(Clone, Debug, PartialEq, Eq, Hash)]