--- a/servo/components/style/gecko/selector_parser.rs
+++ b/servo/components/style/gecko/selector_parser.rs
@@ -184,16 +184,24 @@ impl NonTSPseudoClass {
                     $(NonTSPseudoClass::$name => gecko_type!($gecko_type),)*
                     $(NonTSPseudoClass::$s_name(..) => gecko_type!($s_gecko_type),)*
                     NonTSPseudoClass::MozAny(_) => gecko_type!(any),
                 }
             }
         }
         apply_non_ts_list!(pseudo_class_geckotype)
     }
+
+    /// Returns true if the evaluation of the pseudo-class depends on the
+    /// element's attributes.
+    pub fn is_attr_based(&self) -> bool {
+        matches!(*self,
+                 NonTSPseudoClass::MozTableBorderNonzero |
+                 NonTSPseudoClass::MozBrowserFrame)
+    }
 }
 
 /// The dummy struct we use to implement our selector parsing.
 #[derive(Clone, Debug, PartialEq, Eq)]
 pub struct SelectorImpl;
 
 impl ::selectors::SelectorImpl for SelectorImpl {
     type AttrValue = Atom;

--- a/servo/components/style/gecko/snapshot.rs
+++ b/servo/components/style/gecko/snapshot.rs
@@ -50,16 +50,23 @@ impl GeckoElementSnapshot {
     fn has_any(&self, flags: Flags) -> bool {
         (self.mContains as u8 & flags as u8) != 0
     }
 
     fn as_ptr(&self) -> *const Self {
         self
     }
 
+    /// Returns true if the snapshot has stored state for pseudo-classes
+    /// that depend on things other than `ElementState`.
+    #[inline]
+    pub fn has_other_pseudo_class_state(&self) -> bool {
+        self.has_any(Flags::OtherPseudoClassState)
+    }
+
     /// selectors::Element::attr_matches
     pub fn attr_matches(&self,
                         ns: &NamespaceConstraint<&Namespace>,
                         local_name: &Atom,
                         operation: &AttrSelectorOperation<&Atom>)
                         -> bool {
         unsafe {
             match *operation {

--- a/servo/components/style/restyle_hints.rs
+++ b/servo/components/style/restyle_hints.rs
@@ -673,16 +673,34 @@ impl<'a, E> Element for ElementWrapper<'
             // they match.
             NonTSPseudoClass::Link => {
                 return relevant_link.is_unvisited(self, context);
             }
             NonTSPseudoClass::Visited => {
                 return relevant_link.is_visited(self, context);
             }
 
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::MozTableBorderNonzero => {
+                if let Some(snapshot) = self.snapshot() {
+                    if snapshot.has_other_pseudo_class_state() {
+                        return snapshot.mIsTableBorderNonzero();
+                    }
+                }
+            }
+
+            #[cfg(feature = "gecko")]
+            NonTSPseudoClass::MozBrowserFrame => {
+                if let Some(snapshot) = self.snapshot() {
+                    if snapshot.has_other_pseudo_class_state() {
+                        return snapshot.mIsMozBrowserFrame();
+                    }
+                }
+            }
+
             _ => {}
         }
 
         let flag = pseudo_class.state_flag();
         if flag.is_empty() {
             return self.element.match_non_ts_pseudo_class(pseudo_class,
                                                           context,
                                                           relevant_link,
@@ -801,23 +819,24 @@ fn selector_to_state(sel: &Component<Sel
         // don't forget to update this code?
         #[cfg(feature = "gecko")]
         Component::NonTSPseudoClass(NonTSPseudoClass::Dir(ref s)) => dir_selector_to_state(s),
         Component::NonTSPseudoClass(ref pc) => pc.state_flag(),
         _ => ElementState::empty(),
     }
 }
 
-fn is_attr_selector(sel: &Component<SelectorImpl>) -> bool {
+fn is_attr_based_selector(sel: &Component<SelectorImpl>) -> bool {
     match *sel {
         Component::ID(_) |
         Component::Class(_) |
         Component::AttributeInNoNamespaceExists { .. } |
         Component::AttributeInNoNamespace { .. } |
         Component::AttributeOther(_) => true,
+        Component::NonTSPseudoClass(ref pc) => pc.is_attr_based(),
         _ => false,
     }
 }
 
 #[derive(Clone, Debug)]
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 /// The characteristics that a selector is sensitive to.
 pub struct Sensitivities {
@@ -885,17 +904,17 @@ impl SelectorMapEntry for Dependency {
 struct SensitivitiesVisitor {
     sensitivities: Sensitivities,
 }
 
 impl SelectorVisitor for SensitivitiesVisitor {
     type Impl = SelectorImpl;
     fn visit_simple_selector(&mut self, s: &Component<SelectorImpl>) -> bool {
         self.sensitivities.states.insert(selector_to_state(s));
-        self.sensitivities.attrs |= is_attr_selector(s);
+        self.sensitivities.attrs |= is_attr_based_selector(s);
         true
     }
 }
 
 /// A set of dependencies for a given stylist.
 ///
 /// Note that we can have many dependencies, often more than the total number
 /// of selectors given that we can get multiple partial selectors for a given

--- a/servo/components/style/servo/selector_parser.rs
+++ b/servo/components/style/servo/selector_parser.rs
@@ -263,16 +263,22 @@ impl NonTSPseudoClass {
             ServoCaseSensitiveTypeAttr(_) => ElementState::empty(),
         }
     }
 
     /// Returns true if the given pseudoclass should trigger style sharing cache revalidation.
     pub fn needs_cache_revalidation(&self) -> bool {
         self.state_flag().is_empty()
     }
+
+    /// Returns true if the evaluation of the pseudo-class depends on the
+    /// element's attributes.
+    pub fn is_attr_based(&self) -> bool {
+        false
+    }
 }
 
 /// The abstract struct we implement the selector parser implementation on top
 /// of.
 #[derive(Clone, Debug, PartialEq)]
 #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
 pub struct SelectorImpl;