[librsvg: 2/26] Temporary snapshot of various servo crates
- From: Federico Mena Quintero <federico src gnome org>
- To: commits-list gnome org
- Cc:
- Subject: [librsvg: 2/26] Temporary snapshot of various servo crates
- Date: Sun, 10 Nov 2019 20:16:52 +0000 (UTC)
commit 440656872ec74762ae41a8c54ba5b8369c873e95
Author: Federico Mena Quintero <federico gnome org>
Date: Thu Nov 7 11:36:02 2019 -0600
Temporary snapshot of various servo crates
These are the servo/components/selectors crate and its dependencies,
all from within servo/components.
This is a snapshot of servo's git master as of today. We do this to
avoid having Cargo fetch all of servo's source tree.
servo_crates/derive_common/Cargo.toml | 16 +
servo_crates/derive_common/cg.rs | 350 ++++
servo_crates/derive_common/lib.rs | 13 +
servo_crates/selectors/Cargo.toml | 38 +
servo_crates/selectors/README.md | 25 +
servo_crates/selectors/attr.rs | 207 ++
servo_crates/selectors/bloom.rs | 422 ++++
servo_crates/selectors/build.rs | 77 +
servo_crates/selectors/builder.rs | 349 ++++
servo_crates/selectors/context.rs | 291 +++
servo_crates/selectors/lib.rs | 41 +
servo_crates/selectors/matching.rs | 977 +++++++++
servo_crates/selectors/nth_index_cache.rs | 52 +
servo_crates/selectors/parser.rs | 3144 +++++++++++++++++++++++++++++
servo_crates/selectors/sink.rs | 31 +
servo_crates/selectors/tree.rs | 140 ++
servo_crates/selectors/visitor.rs | 72 +
servo_crates/servo_arc/Cargo.toml | 20 +
servo_crates/servo_arc/lib.rs | 1490 ++++++++++++++
servo_crates/to_shmem/Cargo.toml | 22 +
servo_crates/to_shmem/lib.rs | 543 +++++
servo_crates/to_shmem_derive/Cargo.toml | 18 +
servo_crates/to_shmem_derive/lib.rs | 26 +
servo_crates/to_shmem_derive/to_shmem.rs | 68 +
24 files changed, 8432 insertions(+)
---
diff --git a/servo_crates/derive_common/Cargo.toml b/servo_crates/derive_common/Cargo.toml
new file mode 100644
index 00000000..41121981
--- /dev/null
+++ b/servo_crates/derive_common/Cargo.toml
@@ -0,0 +1,16 @@
+[package]
+name = "derive_common"
+version = "0.0.1"
+authors = ["The Servo Project Developers"]
+license = "MPL-2.0"
+publish = false
+
+[lib]
+path = "lib.rs"
+
+[dependencies]
+darling = { version = "0.10", default-features = false }
+proc-macro2 = "1"
+quote = "1"
+syn = { version = "1", default-features = false, features = ["clone-impls", "parsing"] }
+synstructure = "0.12"
diff --git a/servo_crates/derive_common/cg.rs b/servo_crates/derive_common/cg.rs
new file mode 100644
index 00000000..7a8fbc24
--- /dev/null
+++ b/servo_crates/derive_common/cg.rs
@@ -0,0 +1,350 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+use darling::{FromDeriveInput, FromField, FromVariant};
+use proc_macro2::{Span, TokenStream};
+use quote::TokenStreamExt;
+use syn::{self, AngleBracketedGenericArguments, Binding, DeriveInput, Field};
+use syn::{GenericArgument, GenericParam, Ident, Path};
+use syn::{PathArguments, PathSegment, QSelf, Type, TypeArray};
+use syn::{TypeParam, TypeParen, TypePath, TypeSlice, TypeTuple};
+use syn::{Variant, WherePredicate};
+use synstructure::{self, BindStyle, BindingInfo, VariantAst, VariantInfo};
+
+/// Given an input type which has some where clauses already, like:
+///
+/// struct InputType<T>
+/// where
+/// T: Zero,
+/// {
+/// ...
+/// }
+///
+/// Add the necessary `where` clauses so that the output type of a trait
+/// fulfils them.
+///
+/// For example:
+///
+/// <T as ToComputedValue>::ComputedValue: Zero,
+///
+/// This needs to run before adding other bounds to the type parameters.
+pub fn propagate_clauses_to_output_type(
+ where_clause: &mut Option<syn::WhereClause>,
+ generics: &syn::Generics,
+ trait_path: &Path,
+ trait_output: &Ident,
+) {
+ let where_clause = match *where_clause {
+ Some(ref mut clause) => clause,
+ None => return,
+ };
+ let mut extra_bounds = vec![];
+ for pred in &where_clause.predicates {
+ let ty = match *pred {
+ syn::WherePredicate::Type(ref ty) => ty,
+ ref predicate => panic!("Unhanded complex where predicate: {:?}", predicate),
+ };
+
+ let path = match ty.bounded_ty {
+ syn::Type::Path(ref p) => &p.path,
+ ref ty => panic!("Unhanded complex where type: {:?}", ty),
+ };
+
+ assert!(
+ ty.lifetimes.is_none(),
+ "Unhanded complex lifetime bound: {:?}",
+ ty,
+ );
+
+ let ident = match path_to_ident(path) {
+ Some(i) => i,
+ None => panic!("Unhanded complex where type path: {:?}", path),
+ };
+
+ if generics.type_params().any(|param| param.ident == *ident) {
+ extra_bounds.push(ty.clone());
+ }
+ }
+
+ for bound in extra_bounds {
+ let ty = bound.bounded_ty;
+ let bounds = bound.bounds;
+ where_clause
+ .predicates
+ .push(parse_quote!(<#ty as #trait_path>::#trait_output: #bounds))
+ }
+}
+
+pub fn add_predicate(where_clause: &mut Option<syn::WhereClause>, pred: WherePredicate) {
+ where_clause
+ .get_or_insert(parse_quote!(where))
+ .predicates
+ .push(pred);
+}
+
+pub fn fmap_match<F>(input: &DeriveInput, bind_style: BindStyle, mut f: F) -> TokenStream
+where
+ F: FnMut(BindingInfo) -> TokenStream,
+{
+ let mut s = synstructure::Structure::new(input);
+ s.variants_mut().iter_mut().for_each(|v| {
+ v.bind_with(|_| bind_style);
+ });
+ s.each_variant(|variant| {
+ let (mapped, mapped_fields) = value(variant, "mapped");
+ let fields_pairs = variant.bindings().iter().zip(mapped_fields);
+ let mut computations = quote!();
+ computations.append_all(fields_pairs.map(|(field, mapped_field)| {
+ let expr = f(field.clone());
+ quote! { let #mapped_field = #expr; }
+ }));
+ computations.append_all(mapped);
+ Some(computations)
+ })
+}
+
+pub fn fmap_trait_output(input: &DeriveInput, trait_path: &Path, trait_output: &Ident) -> Path {
+ let segment = PathSegment {
+ ident: input.ident.clone(),
+ arguments: PathArguments::AngleBracketed(AngleBracketedGenericArguments {
+ args: input
+ .generics
+ .params
+ .iter()
+ .map(|arg| match arg {
+ &GenericParam::Lifetime(ref data) => {
+ GenericArgument::Lifetime(data.lifetime.clone())
+ },
+ &GenericParam::Type(ref data) => {
+ let ident = &data.ident;
+ GenericArgument::Type(parse_quote!(<#ident as #trait_path>::#trait_output))
+ },
+ ref arg => panic!("arguments {:?} cannot be mapped yet", arg),
+ })
+ .collect(),
+ colon2_token: Default::default(),
+ gt_token: Default::default(),
+ lt_token: Default::default(),
+ }),
+ };
+ segment.into()
+}
+
+pub fn map_type_params<F>(ty: &Type, params: &[&TypeParam], f: &mut F) -> Type
+where
+ F: FnMut(&Ident) -> Type,
+{
+ match *ty {
+ Type::Slice(ref inner) => Type::from(TypeSlice {
+ elem: Box::new(map_type_params(&inner.elem, params, f)),
+ ..inner.clone()
+ }),
+ Type::Array(ref inner) => {
+ //ref ty, ref expr) => {
+ Type::from(TypeArray {
+ elem: Box::new(map_type_params(&inner.elem, params, f)),
+ ..inner.clone()
+ })
+ },
+ ref ty @ Type::Never(_) => ty.clone(),
+ Type::Tuple(ref inner) => Type::from(TypeTuple {
+ elems: inner
+ .elems
+ .iter()
+ .map(|ty| map_type_params(&ty, params, f))
+ .collect(),
+ ..inner.clone()
+ }),
+ Type::Path(TypePath {
+ qself: None,
+ ref path,
+ }) => {
+ if let Some(ident) = path_to_ident(path) {
+ if params.iter().any(|ref param| ¶m.ident == ident) {
+ return f(ident);
+ }
+ }
+ Type::from(TypePath {
+ qself: None,
+ path: map_type_params_in_path(path, params, f),
+ })
+ },
+ Type::Path(TypePath {
+ ref qself,
+ ref path,
+ }) => Type::from(TypePath {
+ qself: qself.as_ref().map(|qself| QSelf {
+ ty: Box::new(map_type_params(&qself.ty, params, f)),
+ position: qself.position,
+ ..qself.clone()
+ }),
+ path: map_type_params_in_path(path, params, f),
+ }),
+ Type::Paren(ref inner) => Type::from(TypeParen {
+ elem: Box::new(map_type_params(&inner.elem, params, f)),
+ ..inner.clone()
+ }),
+ ref ty => panic!("type {:?} cannot be mapped yet", ty),
+ }
+}
+
+fn map_type_params_in_path<F>(path: &Path, params: &[&TypeParam], f: &mut F) -> Path
+where
+ F: FnMut(&Ident) -> Type,
+{
+ Path {
+ leading_colon: path.leading_colon,
+ segments: path
+ .segments
+ .iter()
+ .map(|segment| PathSegment {
+ ident: segment.ident.clone(),
+ arguments: match segment.arguments {
+ PathArguments::AngleBracketed(ref data) => {
+ PathArguments::AngleBracketed(AngleBracketedGenericArguments {
+ args: data
+ .args
+ .iter()
+ .map(|arg| match arg {
+ ty @ &GenericArgument::Lifetime(_) => ty.clone(),
+ &GenericArgument::Type(ref data) => {
+ GenericArgument::Type(map_type_params(data, params, f))
+ },
+ &GenericArgument::Binding(ref data) => {
+ GenericArgument::Binding(Binding {
+ ty: map_type_params(&data.ty, params, f),
+ ..data.clone()
+ })
+ },
+ ref arg => panic!("arguments {:?} cannot be mapped yet", arg),
+ })
+ .collect(),
+ ..data.clone()
+ })
+ },
+ ref arg @ PathArguments::None => arg.clone(),
+ ref parameters => panic!("parameters {:?} cannot be mapped yet", parameters),
+ },
+ })
+ .collect(),
+ }
+}
+
+fn path_to_ident(path: &Path) -> Option<&Ident> {
+ match *path {
+ Path {
+ leading_colon: None,
+ ref segments,
+ } if segments.len() == 1 => {
+ if segments[0].arguments.is_empty() {
+ Some(&segments[0].ident)
+ } else {
+ None
+ }
+ },
+ _ => None,
+ }
+}
+
+pub fn parse_field_attrs<A>(field: &Field) -> A
+where
+ A: FromField,
+{
+ match A::from_field(field) {
+ Ok(attrs) => attrs,
+ Err(e) => panic!("failed to parse field attributes: {}", e),
+ }
+}
+
+pub fn parse_input_attrs<A>(input: &DeriveInput) -> A
+where
+ A: FromDeriveInput,
+{
+ match A::from_derive_input(input) {
+ Ok(attrs) => attrs,
+ Err(e) => panic!("failed to parse input attributes: {}", e),
+ }
+}
+
+pub fn parse_variant_attrs_from_ast<A>(variant: &VariantAst) -> A
+where
+ A: FromVariant,
+{
+ let v = Variant {
+ ident: variant.ident.clone(),
+ attrs: variant.attrs.to_vec(),
+ fields: variant.fields.clone(),
+ discriminant: variant.discriminant.clone(),
+ };
+ parse_variant_attrs(&v)
+}
+
+pub fn parse_variant_attrs<A>(variant: &Variant) -> A
+where
+ A: FromVariant,
+{
+ match A::from_variant(variant) {
+ Ok(attrs) => attrs,
+ Err(e) => panic!("failed to parse variant attributes: {}", e),
+ }
+}
+
+pub fn ref_pattern<'a>(
+ variant: &'a VariantInfo,
+ prefix: &str,
+) -> (TokenStream, Vec<BindingInfo<'a>>) {
+ let mut v = variant.clone();
+ v.bind_with(|_| BindStyle::Ref);
+ v.bindings_mut().iter_mut().for_each(|b| {
+ b.binding = Ident::new(&format!("{}_{}", b.binding, prefix), Span::call_site())
+ });
+ (v.pat(), v.bindings().to_vec())
+}
+
+pub fn value<'a>(variant: &'a VariantInfo, prefix: &str) -> (TokenStream, Vec<BindingInfo<'a>>) {
+ let mut v = variant.clone();
+ v.bindings_mut().iter_mut().for_each(|b| {
+ b.binding = Ident::new(&format!("{}_{}", b.binding, prefix), Span::call_site())
+ });
+ v.bind_with(|_| BindStyle::Move);
+ (v.pat(), v.bindings().to_vec())
+}
+
+/// Transforms "FooBar" to "foo-bar".
+///
+/// If the first Camel segment is "Moz", "Webkit", or "Servo", the result string
+/// is prepended with "-".
+pub fn to_css_identifier(mut camel_case: &str) -> String {
+ camel_case = camel_case.trim_end_matches('_');
+ let mut first = true;
+ let mut result = String::with_capacity(camel_case.len());
+ while let Some(segment) = split_camel_segment(&mut camel_case) {
+ if first {
+ match segment {
+ "Moz" | "Webkit" | "Servo" => first = false,
+ _ => {},
+ }
+ }
+ if !first {
+ result.push_str("-");
+ }
+ first = false;
+ result.push_str(&segment.to_lowercase());
+ }
+ result
+}
+
+/// Given "FooBar", returns "Foo" and sets `camel_case` to "Bar".
+fn split_camel_segment<'input>(camel_case: &mut &'input str) -> Option<&'input str> {
+ let index = match camel_case.chars().next() {
+ None => return None,
+ Some(ch) => ch.len_utf8(),
+ };
+ let end_position = camel_case[index..]
+ .find(char::is_uppercase)
+ .map_or(camel_case.len(), |pos| index + pos);
+ let result = &camel_case[..end_position];
+ *camel_case = &camel_case[end_position..];
+ Some(result)
+}
diff --git a/servo_crates/derive_common/lib.rs b/servo_crates/derive_common/lib.rs
new file mode 100644
index 00000000..14415351
--- /dev/null
+++ b/servo_crates/derive_common/lib.rs
@@ -0,0 +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 https://mozilla.org/MPL/2.0/. */
+
+extern crate darling;
+extern crate proc_macro2;
+#[macro_use]
+extern crate quote;
+#[macro_use]
+extern crate syn;
+extern crate synstructure;
+
+pub mod cg;
diff --git a/servo_crates/selectors/Cargo.toml b/servo_crates/selectors/Cargo.toml
new file mode 100644
index 00000000..d3dda6cb
--- /dev/null
+++ b/servo_crates/selectors/Cargo.toml
@@ -0,0 +1,38 @@
+[package]
+
+name = "selectors"
+version = "0.21.0"
+authors = ["The Servo Project Developers"]
+documentation = "https://docs.rs/selectors/";
+
+description = "CSS Selectors matching for Rust"
+repository = "https://github.com/servo/servo";
+readme = "README.md"
+keywords = ["css", "selectors"]
+license = "MPL-2.0"
+build = "build.rs"
+
+[lib]
+name = "selectors"
+path = "lib.rs"
+
+[features]
+bench = []
+
+[dependencies]
+bitflags = "1.0"
+matches = "0.1"
+cssparser = "0.27.1"
+derive_more = "0.13"
+log = "0.4"
+fxhash = "0.2"
+phf = "0.8"
+precomputed-hash = "0.1"
+servo_arc = { version = "0.1", path = "../servo_arc" }
+smallvec = "0.6"
+thin-slice = "0.1.0"
+to_shmem = { path = "../to_shmem" }
+to_shmem_derive = { path = "../to_shmem_derive" }
+
+[build-dependencies]
+phf_codegen = "0.8"
diff --git a/servo_crates/selectors/README.md b/servo_crates/selectors/README.md
new file mode 100644
index 00000000..51cfda81
--- /dev/null
+++ b/servo_crates/selectors/README.md
@@ -0,0 +1,25 @@
+rust-selectors
+==============
+
+* [](
+ https://travis-ci.com/servo/rust-selectors)
+* [Documentation](https://docs.rs/selectors/)
+* [crates.io](https://crates.io/crates/selectors)
+
+CSS Selectors library for Rust.
+Includes parsing and serilization of selectors,
+as well as matching against a generic tree of elements.
+Pseudo-elements and most pseudo-classes are generic as well.
+
+**Warning:** breaking changes are made to this library fairly frequently
+(13 times in 2016, for example).
+However you can use this crate without updating it that often,
+old versions stay available on crates.io and Cargo will only automatically update
+to versions that are numbered as compatible.
+
+To see how to use this library with your own tree representation,
+see [Kuchiki’s `src/select.rs`](https://github.com/SimonSapin/kuchiki/blob/master/src/select.rs).
+(Note however that Kuchiki is not always up to date with the latest rust-selectors version,
+so that code may need to be tweaked.)
+If you don’t already have a tree data structure,
+consider using [Kuchiki](https://github.com/SimonSapin/kuchiki) itself.
diff --git a/servo_crates/selectors/attr.rs b/servo_crates/selectors/attr.rs
new file mode 100644
index 00000000..96abbe1c
--- /dev/null
+++ b/servo_crates/selectors/attr.rs
@@ -0,0 +1,207 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+use crate::parser::SelectorImpl;
+use cssparser::ToCss;
+use std::fmt;
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub struct AttrSelectorWithOptionalNamespace<Impl: SelectorImpl> {
+ #[shmem(field_bound)]
+ pub namespace: Option<NamespaceConstraint<(Impl::NamespacePrefix, Impl::NamespaceUrl)>>,
+ #[shmem(field_bound)]
+ pub local_name: Impl::LocalName,
+ pub local_name_lower: Impl::LocalName,
+ #[shmem(field_bound)]
+ pub operation: ParsedAttrSelectorOperation<Impl::AttrValue>,
+ pub never_matches: bool,
+}
+
+impl<Impl: SelectorImpl> AttrSelectorWithOptionalNamespace<Impl> {
+ pub fn namespace(&self) -> Option<NamespaceConstraint<&Impl::NamespaceUrl>> {
+ self.namespace.as_ref().map(|ns| match ns {
+ NamespaceConstraint::Any => NamespaceConstraint::Any,
+ NamespaceConstraint::Specific((_, ref url)) => NamespaceConstraint::Specific(url),
+ })
+ }
+}
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+pub enum NamespaceConstraint<NamespaceUrl> {
+ Any,
+
+ /// Empty string for no namespace
+ Specific(NamespaceUrl),
+}
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+pub enum ParsedAttrSelectorOperation<AttrValue> {
+ Exists,
+ WithValue {
+ operator: AttrSelectorOperator,
+ case_sensitivity: ParsedCaseSensitivity,
+ expected_value: AttrValue,
+ },
+}
+
+#[derive(Clone, Eq, PartialEq)]
+pub enum AttrSelectorOperation<AttrValue> {
+ Exists,
+ WithValue {
+ operator: AttrSelectorOperator,
+ case_sensitivity: CaseSensitivity,
+ expected_value: AttrValue,
+ },
+}
+
+impl<AttrValue> AttrSelectorOperation<AttrValue> {
+ pub fn eval_str(&self, element_attr_value: &str) -> bool
+ where
+ AttrValue: AsRef<str>,
+ {
+ match *self {
+ AttrSelectorOperation::Exists => true,
+ AttrSelectorOperation::WithValue {
+ operator,
+ case_sensitivity,
+ ref expected_value,
+ } => operator.eval_str(
+ element_attr_value,
+ expected_value.as_ref(),
+ case_sensitivity,
+ ),
+ }
+ }
+}
+
+#[derive(Clone, Copy, Eq, PartialEq, ToShmem)]
+pub enum AttrSelectorOperator {
+ Equal,
+ Includes,
+ DashMatch,
+ Prefix,
+ Substring,
+ Suffix,
+}
+
+impl ToCss for AttrSelectorOperator {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ // https://drafts.csswg.org/cssom/#serializing-selectors
+ // See "attribute selector".
+ dest.write_str(match *self {
+ AttrSelectorOperator::Equal => "=",
+ AttrSelectorOperator::Includes => "~=",
+ AttrSelectorOperator::DashMatch => "|=",
+ AttrSelectorOperator::Prefix => "^=",
+ AttrSelectorOperator::Substring => "*=",
+ AttrSelectorOperator::Suffix => "$=",
+ })
+ }
+}
+
+impl AttrSelectorOperator {
+ pub fn eval_str(
+ self,
+ element_attr_value: &str,
+ attr_selector_value: &str,
+ case_sensitivity: CaseSensitivity,
+ ) -> bool {
+ let e = element_attr_value.as_bytes();
+ let s = attr_selector_value.as_bytes();
+ let case = case_sensitivity;
+ match self {
+ AttrSelectorOperator::Equal => case.eq(e, s),
+ AttrSelectorOperator::Prefix => e.len() >= s.len() && case.eq(&e[..s.len()], s),
+ AttrSelectorOperator::Suffix => {
+ e.len() >= s.len() && case.eq(&e[(e.len() - s.len())..], s)
+ },
+ AttrSelectorOperator::Substring => {
+ case.contains(element_attr_value, attr_selector_value)
+ },
+ AttrSelectorOperator::Includes => element_attr_value
+ .split(SELECTOR_WHITESPACE)
+ .any(|part| case.eq(part.as_bytes(), s)),
+ AttrSelectorOperator::DashMatch => {
+ case.eq(e, s) || (e.get(s.len()) == Some(&b'-') && case.eq(&e[..s.len()], s))
+ },
+ }
+ }
+}
+
+/// The definition of whitespace per CSS Selectors Level 3 § 4.
+pub static SELECTOR_WHITESPACE: &'static [char] = &[' ', '\t', '\n', '\r', '\x0C'];
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq, ToShmem)]
+pub enum ParsedCaseSensitivity {
+ // 's' was specified.
+ ExplicitCaseSensitive,
+ // 'i' was specified.
+ AsciiCaseInsensitive,
+ // No flags were specified and HTML says this is a case-sensitive attribute.
+ CaseSensitive,
+ // No flags were specified and HTML says this is a case-insensitive attribute.
+ AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument,
+}
+
+impl ParsedCaseSensitivity {
+ pub fn to_unconditional(self, is_html_element_in_html_document: bool) -> CaseSensitivity {
+ match self {
+ ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument
+ if is_html_element_in_html_document =>
+ {
+ CaseSensitivity::AsciiCaseInsensitive
+ },
+ ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {
+ CaseSensitivity::CaseSensitive
+ },
+ ParsedCaseSensitivity::CaseSensitive | ParsedCaseSensitivity::ExplicitCaseSensitive => {
+ CaseSensitivity::CaseSensitive
+ },
+ ParsedCaseSensitivity::AsciiCaseInsensitive => CaseSensitivity::AsciiCaseInsensitive,
+ }
+ }
+}
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum CaseSensitivity {
+ CaseSensitive,
+ AsciiCaseInsensitive,
+}
+
+impl CaseSensitivity {
+ pub fn eq(self, a: &[u8], b: &[u8]) -> bool {
+ match self {
+ CaseSensitivity::CaseSensitive => a == b,
+ CaseSensitivity::AsciiCaseInsensitive => a.eq_ignore_ascii_case(b),
+ }
+ }
+
+ pub fn contains(self, haystack: &str, needle: &str) -> bool {
+ match self {
+ CaseSensitivity::CaseSensitive => haystack.contains(needle),
+ CaseSensitivity::AsciiCaseInsensitive => {
+ if let Some((&n_first_byte, n_rest)) = needle.as_bytes().split_first() {
+ haystack.bytes().enumerate().any(|(i, byte)| {
+ if !byte.eq_ignore_ascii_case(&n_first_byte) {
+ return false;
+ }
+ let after_this_byte = &haystack.as_bytes()[i + 1..];
+ match after_this_byte.get(..n_rest.len()) {
+ None => false,
+ Some(haystack_slice) => haystack_slice.eq_ignore_ascii_case(n_rest),
+ }
+ })
+ } else {
+ // any_str.contains("") == true,
+ // though these cases should be handled with *NeverMatches and never go here.
+ true
+ }
+ },
+ }
+ }
+}
diff --git a/servo_crates/selectors/bloom.rs b/servo_crates/selectors/bloom.rs
new file mode 100644
index 00000000..98461d1b
--- /dev/null
+++ b/servo_crates/selectors/bloom.rs
@@ -0,0 +1,422 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+//! Counting and non-counting Bloom filters tuned for use as ancestor filters
+//! for selector matching.
+
+use std::fmt::{self, Debug};
+
+// The top 8 bits of the 32-bit hash value are not used by the bloom filter.
+// Consumers may rely on this to pack hashes more efficiently.
+pub const BLOOM_HASH_MASK: u32 = 0x00ffffff;
+const KEY_SIZE: usize = 12;
+
+const ARRAY_SIZE: usize = 1 << KEY_SIZE;
+const KEY_MASK: u32 = (1 << KEY_SIZE) - 1;
+
+/// A counting Bloom filter with 8-bit counters.
+pub type BloomFilter = CountingBloomFilter<BloomStorageU8>;
+
+/// A counting Bloom filter with parameterized storage to handle
+/// counters of different sizes. For now we assume that having two hash
+/// functions is enough, but we may revisit that decision later.
+///
+/// The filter uses an array with 2**KeySize entries.
+///
+/// Assuming a well-distributed hash function, a Bloom filter with
+/// array size M containing N elements and
+/// using k hash function has expected false positive rate exactly
+///
+/// $ (1 - (1 - 1/M)^{kN})^k $
+///
+/// because each array slot has a
+///
+/// $ (1 - 1/M)^{kN} $
+///
+/// chance of being 0, and the expected false positive rate is the
+/// probability that all of the k hash functions will hit a nonzero
+/// slot.
+///
+/// For reasonable assumptions (M large, kN large, which should both
+/// hold if we're worried about false positives) about M and kN this
+/// becomes approximately
+///
+/// $$ (1 - \exp(-kN/M))^k $$
+///
+/// For our special case of k == 2, that's $(1 - \exp(-2N/M))^2$,
+/// or in other words
+///
+/// $$ N/M = -0.5 * \ln(1 - \sqrt(r)) $$
+///
+/// where r is the false positive rate. This can be used to compute
+/// the desired KeySize for a given load N and false positive rate r.
+///
+/// If N/M is assumed small, then the false positive rate can
+/// further be approximated as 4*N^2/M^2. So increasing KeySize by
+/// 1, which doubles M, reduces the false positive rate by about a
+/// factor of 4, and a false positive rate of 1% corresponds to
+/// about M/N == 20.
+///
+/// What this means in practice is that for a few hundred keys using a
+/// KeySize of 12 gives false positive rates on the order of 0.25-4%.
+///
+/// Similarly, using a KeySize of 10 would lead to a 4% false
+/// positive rate for N == 100 and to quite bad false positive
+/// rates for larger N.
+#[derive(Clone, Default)]
+pub struct CountingBloomFilter<S>
+where
+ S: BloomStorage,
+{
+ storage: S,
+}
+
+impl<S> CountingBloomFilter<S>
+where
+ S: BloomStorage,
+{
+ /// Creates a new bloom filter.
+ #[inline]
+ pub fn new() -> Self {
+ Default::default()
+ }
+
+ #[inline]
+ pub fn clear(&mut self) {
+ self.storage = Default::default();
+ }
+
+ // Slow linear accessor to make sure the bloom filter is zeroed. This should
+ // never be used in release builds.
+ #[cfg(debug_assertions)]
+ pub fn is_zeroed(&self) -> bool {
+ self.storage.is_zeroed()
+ }
+
+ #[cfg(not(debug_assertions))]
+ pub fn is_zeroed(&self) -> bool {
+ unreachable!()
+ }
+
+ /// Inserts an item with a particular hash into the bloom filter.
+ #[inline]
+ pub fn insert_hash(&mut self, hash: u32) {
+ self.storage.adjust_first_slot(hash, true);
+ self.storage.adjust_second_slot(hash, true);
+ }
+
+ /// Removes an item with a particular hash from the bloom filter.
+ #[inline]
+ pub fn remove_hash(&mut self, hash: u32) {
+ self.storage.adjust_first_slot(hash, false);
+ self.storage.adjust_second_slot(hash, false);
+ }
+
+ /// Check whether the filter might contain an item with the given hash.
+ /// This can sometimes return true even if the item is not in the filter,
+ /// but will never return false for items that are actually in the filter.
+ #[inline]
+ pub fn might_contain_hash(&self, hash: u32) -> bool {
+ !self.storage.first_slot_is_empty(hash) && !self.storage.second_slot_is_empty(hash)
+ }
+}
+
+impl<S> Debug for CountingBloomFilter<S>
+where
+ S: BloomStorage,
+{
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let mut slots_used = 0;
+ for i in 0..ARRAY_SIZE {
+ if !self.storage.slot_is_empty(i) {
+ slots_used += 1;
+ }
+ }
+ write!(f, "BloomFilter({}/{})", slots_used, ARRAY_SIZE)
+ }
+}
+
+pub trait BloomStorage: Clone + Default {
+ fn slot_is_empty(&self, index: usize) -> bool;
+ fn adjust_slot(&mut self, index: usize, increment: bool);
+ fn is_zeroed(&self) -> bool;
+
+ #[inline]
+ fn first_slot_is_empty(&self, hash: u32) -> bool {
+ self.slot_is_empty(Self::first_slot_index(hash))
+ }
+
+ #[inline]
+ fn second_slot_is_empty(&self, hash: u32) -> bool {
+ self.slot_is_empty(Self::second_slot_index(hash))
+ }
+
+ #[inline]
+ fn adjust_first_slot(&mut self, hash: u32, increment: bool) {
+ self.adjust_slot(Self::first_slot_index(hash), increment)
+ }
+
+ #[inline]
+ fn adjust_second_slot(&mut self, hash: u32, increment: bool) {
+ self.adjust_slot(Self::second_slot_index(hash), increment)
+ }
+
+ #[inline]
+ fn first_slot_index(hash: u32) -> usize {
+ hash1(hash) as usize
+ }
+
+ #[inline]
+ fn second_slot_index(hash: u32) -> usize {
+ hash2(hash) as usize
+ }
+}
+
+/// Storage class for a CountingBloomFilter that has 8-bit counters.
+pub struct BloomStorageU8 {
+ counters: [u8; ARRAY_SIZE],
+}
+
+impl BloomStorage for BloomStorageU8 {
+ #[inline]
+ fn adjust_slot(&mut self, index: usize, increment: bool) {
+ let slot = &mut self.counters[index];
+ if *slot != 0xff {
+ // full
+ if increment {
+ *slot += 1;
+ } else {
+ *slot -= 1;
+ }
+ }
+ }
+
+ #[inline]
+ fn slot_is_empty(&self, index: usize) -> bool {
+ self.counters[index] == 0
+ }
+
+ #[inline]
+ fn is_zeroed(&self) -> bool {
+ self.counters.iter().all(|x| *x == 0)
+ }
+}
+
+impl Default for BloomStorageU8 {
+ fn default() -> Self {
+ BloomStorageU8 {
+ counters: [0; ARRAY_SIZE],
+ }
+ }
+}
+
+impl Clone for BloomStorageU8 {
+ fn clone(&self) -> Self {
+ BloomStorageU8 {
+ counters: self.counters,
+ }
+ }
+}
+
+/// Storage class for a CountingBloomFilter that has 1-bit counters.
+pub struct BloomStorageBool {
+ counters: [u8; ARRAY_SIZE / 8],
+}
+
+impl BloomStorage for BloomStorageBool {
+ #[inline]
+ fn adjust_slot(&mut self, index: usize, increment: bool) {
+ let bit = 1 << (index % 8);
+ let byte = &mut self.counters[index / 8];
+
+ // Since we have only one bit for storage, decrementing it
+ // should never do anything. Assert against an accidental
+ // decrementing of a bit that was never set.
+ assert!(
+ increment || (*byte & bit) != 0,
+ "should not decrement if slot is already false"
+ );
+
+ if increment {
+ *byte |= bit;
+ }
+ }
+
+ #[inline]
+ fn slot_is_empty(&self, index: usize) -> bool {
+ let bit = 1 << (index % 8);
+ (self.counters[index / 8] & bit) == 0
+ }
+
+ #[inline]
+ fn is_zeroed(&self) -> bool {
+ self.counters.iter().all(|x| *x == 0)
+ }
+}
+
+impl Default for BloomStorageBool {
+ fn default() -> Self {
+ BloomStorageBool {
+ counters: [0; ARRAY_SIZE / 8],
+ }
+ }
+}
+
+impl Clone for BloomStorageBool {
+ fn clone(&self) -> Self {
+ BloomStorageBool {
+ counters: self.counters,
+ }
+ }
+}
+
+#[inline]
+fn hash1(hash: u32) -> u32 {
+ hash & KEY_MASK
+}
+
+#[inline]
+fn hash2(hash: u32) -> u32 {
+ (hash >> KEY_SIZE) & KEY_MASK
+}
+
+#[test]
+fn create_and_insert_some_stuff() {
+ use fxhash::FxHasher;
+ use std::hash::{Hash, Hasher};
+ use std::mem::transmute;
+
+ fn hash_as_str(i: usize) -> u32 {
+ let mut hasher = FxHasher::default();
+ let s = i.to_string();
+ s.hash(&mut hasher);
+ let hash: u64 = hasher.finish();
+ (hash >> 32) as u32 ^ (hash as u32)
+ }
+
+ let mut bf = BloomFilter::new();
+
+ // Statically assert that ARRAY_SIZE is a multiple of 8, which
+ // BloomStorageBool relies on.
+ unsafe {
+ transmute::<[u8; ARRAY_SIZE % 8], [u8; 0]>([]);
+ }
+
+ for i in 0_usize..1000 {
+ bf.insert_hash(hash_as_str(i));
+ }
+
+ for i in 0_usize..1000 {
+ assert!(bf.might_contain_hash(hash_as_str(i)));
+ }
+
+ let false_positives = (1001_usize..2000)
+ .filter(|i| bf.might_contain_hash(hash_as_str(*i)))
+ .count();
+
+ assert!(false_positives < 190, "{} is not < 190", false_positives); // 19%.
+
+ for i in 0_usize..100 {
+ bf.remove_hash(hash_as_str(i));
+ }
+
+ for i in 100_usize..1000 {
+ assert!(bf.might_contain_hash(hash_as_str(i)));
+ }
+
+ let false_positives = (0_usize..100)
+ .filter(|i| bf.might_contain_hash(hash_as_str(*i)))
+ .count();
+
+ assert!(false_positives < 20, "{} is not < 20", false_positives); // 20%.
+
+ bf.clear();
+
+ for i in 0_usize..2000 {
+ assert!(!bf.might_contain_hash(hash_as_str(i)));
+ }
+}
+
+#[cfg(feature = "bench")]
+#[cfg(test)]
+mod bench {
+ extern crate test;
+ use super::BloomFilter;
+
+ #[derive(Default)]
+ struct HashGenerator(u32);
+
+ impl HashGenerator {
+ fn next(&mut self) -> u32 {
+ // Each hash is split into two twelve-bit segments, which are used
+ // as an index into an array. We increment each by 64 so that we
+ // hit the next cache line, and then another 1 so that our wrapping
+ // behavior leads us to different entries each time.
+ //
+ // Trying to simulate cold caches is rather difficult with the cargo
+ // benchmarking setup, so it may all be moot depending on the number
+ // of iterations that end up being run. But we might as well.
+ self.0 += (65) + (65 << super::KEY_SIZE);
+ self.0
+ }
+ }
+
+ #[bench]
+ fn create_insert_1000_remove_100_lookup_100(b: &mut test::Bencher) {
+ b.iter(|| {
+ let mut gen1 = HashGenerator::default();
+ let mut gen2 = HashGenerator::default();
+ let mut bf = BloomFilter::new();
+ for _ in 0_usize..1000 {
+ bf.insert_hash(gen1.next());
+ }
+ for _ in 0_usize..100 {
+ bf.remove_hash(gen2.next());
+ }
+ for _ in 100_usize..200 {
+ test::black_box(bf.might_contain_hash(gen2.next()));
+ }
+ });
+ }
+
+ #[bench]
+ fn might_contain_10(b: &mut test::Bencher) {
+ let bf = BloomFilter::new();
+ let mut gen = HashGenerator::default();
+ b.iter(|| {
+ for _ in 0..10 {
+ test::black_box(bf.might_contain_hash(gen.next()));
+ }
+ });
+ }
+
+ #[bench]
+ fn clear(b: &mut test::Bencher) {
+ let mut bf = Box::new(BloomFilter::new());
+ b.iter(|| test::black_box(&mut bf).clear());
+ }
+
+ #[bench]
+ fn insert_10(b: &mut test::Bencher) {
+ let mut bf = BloomFilter::new();
+ let mut gen = HashGenerator::default();
+ b.iter(|| {
+ for _ in 0..10 {
+ test::black_box(bf.insert_hash(gen.next()));
+ }
+ });
+ }
+
+ #[bench]
+ fn remove_10(b: &mut test::Bencher) {
+ let mut bf = BloomFilter::new();
+ let mut gen = HashGenerator::default();
+ // Note: this will underflow, and that's ok.
+ b.iter(|| {
+ for _ in 0..10 {
+ bf.remove_hash(gen.next())
+ }
+ });
+ }
+}
diff --git a/servo_crates/selectors/build.rs b/servo_crates/selectors/build.rs
new file mode 100644
index 00000000..264c2da6
--- /dev/null
+++ b/servo_crates/selectors/build.rs
@@ -0,0 +1,77 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+extern crate phf_codegen;
+
+use std::env;
+use std::fs::File;
+use std::io::{BufWriter, Write};
+use std::path::Path;
+
+fn main() {
+ let path = Path::new(&env::var_os("OUT_DIR").unwrap())
+ .join("ascii_case_insensitive_html_attributes.rs");
+ let mut file = BufWriter::new(File::create(&path).unwrap());
+
+ let mut set = phf_codegen::Set::new();
+ for name in ASCII_CASE_INSENSITIVE_HTML_ATTRIBUTES.split_whitespace() {
+ set.entry(name);
+ }
+ write!(
+ &mut file,
+ "{{ static SET: ::phf::Set<&'static str> = {}; &SET }}",
+ set.build(),
+ )
+ .unwrap();
+}
+
+/// <https://html.spec.whatwg.org/multipage/#selectors>
+static ASCII_CASE_INSENSITIVE_HTML_ATTRIBUTES: &'static str = r#"
+ accept
+ accept-charset
+ align
+ alink
+ axis
+ bgcolor
+ charset
+ checked
+ clear
+ codetype
+ color
+ compact
+ declare
+ defer
+ dir
+ direction
+ disabled
+ enctype
+ face
+ frame
+ hreflang
+ http-equiv
+ lang
+ language
+ link
+ media
+ method
+ multiple
+ nohref
+ noresize
+ noshade
+ nowrap
+ readonly
+ rel
+ rev
+ rules
+ scope
+ scrolling
+ selected
+ shape
+ target
+ text
+ type
+ valign
+ valuetype
+ vlink
+"#;
diff --git a/servo_crates/selectors/builder.rs b/servo_crates/selectors/builder.rs
new file mode 100644
index 00000000..41b83b0c
--- /dev/null
+++ b/servo_crates/selectors/builder.rs
@@ -0,0 +1,349 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+//! Helper module to build up a selector safely and efficiently.
+//!
+//! Our selector representation is designed to optimize matching, and has
+//! several requirements:
+//! * All simple selectors and combinators are stored inline in the same buffer
+//! as Component instances.
+//! * We store the top-level compound selectors from right to left, i.e. in
+//! matching order.
+//! * We store the simple selectors for each combinator from left to right, so
+//! that we match the cheaper simple selectors first.
+//!
+//! Meeting all these constraints without extra memmove traffic during parsing
+//! is non-trivial. This module encapsulates those details and presents an
+//! easy-to-use API for the parser.
+
+use crate::parser::{Combinator, Component, SelectorImpl};
+use crate::sink::Push;
+use servo_arc::{Arc, HeaderWithLength, ThinArc};
+use smallvec::{self, SmallVec};
+use std::cmp;
+use std::iter;
+use std::ptr;
+use std::slice;
+
+/// Top-level SelectorBuilder struct. This should be stack-allocated by the
+/// consumer and never moved (because it contains a lot of inline data that
+/// would be slow to memmov).
+///
+/// After instantation, callers may call the push_simple_selector() and
+/// push_combinator() methods to append selector data as it is encountered
+/// (from left to right). Once the process is complete, callers should invoke
+/// build(), which transforms the contents of the SelectorBuilder into a heap-
+/// allocated Selector and leaves the builder in a drained state.
+#[derive(Debug)]
+pub struct SelectorBuilder<Impl: SelectorImpl> {
+ /// The entire sequence of simple selectors, from left to right, without combinators.
+ ///
+ /// We make this large because the result of parsing a selector is fed into a new
+ /// Arc-ed allocation, so any spilled vec would be a wasted allocation. Also,
+ /// Components are large enough that we don't have much cache locality benefit
+ /// from reserving stack space for fewer of them.
+ simple_selectors: SmallVec<[Component<Impl>; 32]>,
+ /// The combinators, and the length of the compound selector to their left.
+ combinators: SmallVec<[(Combinator, usize); 16]>,
+ /// The length of the current compount selector.
+ current_len: usize,
+}
+
+impl<Impl: SelectorImpl> Default for SelectorBuilder<Impl> {
+ #[inline(always)]
+ fn default() -> Self {
+ SelectorBuilder {
+ simple_selectors: SmallVec::new(),
+ combinators: SmallVec::new(),
+ current_len: 0,
+ }
+ }
+}
+
+impl<Impl: SelectorImpl> Push<Component<Impl>> for SelectorBuilder<Impl> {
+ fn push(&mut self, value: Component<Impl>) {
+ self.push_simple_selector(value);
+ }
+}
+
+impl<Impl: SelectorImpl> SelectorBuilder<Impl> {
+ /// Pushes a simple selector onto the current compound selector.
+ #[inline(always)]
+ pub fn push_simple_selector(&mut self, ss: Component<Impl>) {
+ assert!(!ss.is_combinator());
+ self.simple_selectors.push(ss);
+ self.current_len += 1;
+ }
+
+ /// Completes the current compound selector and starts a new one, delimited
+ /// by the given combinator.
+ #[inline(always)]
+ pub fn push_combinator(&mut self, c: Combinator) {
+ self.combinators.push((c, self.current_len));
+ self.current_len = 0;
+ }
+
+ /// Returns true if combinators have ever been pushed to this builder.
+ #[inline(always)]
+ pub fn has_combinators(&self) -> bool {
+ !self.combinators.is_empty()
+ }
+
+ /// Consumes the builder, producing a Selector.
+ #[inline(always)]
+ pub fn build(
+ &mut self,
+ parsed_pseudo: bool,
+ parsed_slotted: bool,
+ parsed_part: bool,
+ ) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
+ // Compute the specificity and flags.
+ let specificity = specificity(self.simple_selectors.iter());
+ let mut flags = SelectorFlags::empty();
+ if parsed_pseudo {
+ flags |= SelectorFlags::HAS_PSEUDO;
+ }
+ if parsed_slotted {
+ flags |= SelectorFlags::HAS_SLOTTED;
+ }
+ if parsed_part {
+ flags |= SelectorFlags::HAS_PART;
+ }
+ self.build_with_specificity_and_flags(SpecificityAndFlags { specificity, flags })
+ }
+
+ /// Builds with an explicit SpecificityAndFlags. This is separated from build() so
+ /// that unit tests can pass an explicit specificity.
+ #[inline(always)]
+ pub fn build_with_specificity_and_flags(
+ &mut self,
+ spec: SpecificityAndFlags,
+ ) -> ThinArc<SpecificityAndFlags, Component<Impl>> {
+ // First, compute the total number of Components we'll need to allocate
+ // space for.
+ let full_len = self.simple_selectors.len() + self.combinators.len();
+
+ // Create the header.
+ let header = HeaderWithLength::new(spec, full_len);
+
+ // Create the Arc using an iterator that drains our buffers.
+
+ // Use a raw pointer to be able to call set_len despite "borrowing" the slice.
+ // This is similar to SmallVec::drain, but we use a slice here because
+ // we’re gonna traverse it non-linearly.
+ let raw_simple_selectors: *const [Component<Impl>] = &*self.simple_selectors;
+ unsafe {
+ // Panic-safety: if SelectorBuilderIter is not iterated to the end,
+ // some simple selectors will safely leak.
+ self.simple_selectors.set_len(0)
+ }
+ let (rest, current) = split_from_end(unsafe { &*raw_simple_selectors }, self.current_len);
+ let iter = SelectorBuilderIter {
+ current_simple_selectors: current.iter(),
+ rest_of_simple_selectors: rest,
+ combinators: self.combinators.drain().rev(),
+ };
+
+ Arc::into_thin(Arc::from_header_and_iter(header, iter))
+ }
+}
+
+struct SelectorBuilderIter<'a, Impl: SelectorImpl> {
+ current_simple_selectors: slice::Iter<'a, Component<Impl>>,
+ rest_of_simple_selectors: &'a [Component<Impl>],
+ combinators: iter::Rev<smallvec::Drain<'a, (Combinator, usize)>>,
+}
+
+impl<'a, Impl: SelectorImpl> ExactSizeIterator for SelectorBuilderIter<'a, Impl> {
+ fn len(&self) -> usize {
+ self.current_simple_selectors.len() +
+ self.rest_of_simple_selectors.len() +
+ self.combinators.len()
+ }
+}
+
+impl<'a, Impl: SelectorImpl> Iterator for SelectorBuilderIter<'a, Impl> {
+ type Item = Component<Impl>;
+ #[inline(always)]
+ fn next(&mut self) -> Option<Self::Item> {
+ if let Some(simple_selector_ref) = self.current_simple_selectors.next() {
+ // Move a simple selector out of this slice iterator.
+ // This is safe because we’ve called SmallVec::set_len(0) above,
+ // so SmallVec::drop won’t drop this simple selector.
+ unsafe { Some(ptr::read(simple_selector_ref)) }
+ } else {
+ self.combinators.next().map(|(combinator, len)| {
+ let (rest, current) = split_from_end(self.rest_of_simple_selectors, len);
+ self.rest_of_simple_selectors = rest;
+ self.current_simple_selectors = current.iter();
+ Component::Combinator(combinator)
+ })
+ }
+ }
+
+ fn size_hint(&self) -> (usize, Option<usize>) {
+ (self.len(), Some(self.len()))
+ }
+}
+
+fn split_from_end<T>(s: &[T], at: usize) -> (&[T], &[T]) {
+ s.split_at(s.len() - at)
+}
+
+bitflags! {
+ /// Flags that indicate at which point of parsing a selector are we.
+ #[derive(Default, ToShmem)]
+ pub (crate) struct SelectorFlags : u8 {
+ const HAS_PSEUDO = 1 << 0;
+ const HAS_SLOTTED = 1 << 1;
+ const HAS_PART = 1 << 2;
+ }
+}
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq, ToShmem)]
+pub struct SpecificityAndFlags {
+ /// There are two free bits here, since we use ten bits for each specificity
+ /// kind (id, class, element).
+ pub(crate) specificity: u32,
+ /// There's padding after this field due to the size of the flags.
+ pub(crate) flags: SelectorFlags,
+}
+
+impl SpecificityAndFlags {
+ #[inline]
+ pub fn specificity(&self) -> u32 {
+ self.specificity
+ }
+
+ #[inline]
+ pub fn has_pseudo_element(&self) -> bool {
+ self.flags.intersects(SelectorFlags::HAS_PSEUDO)
+ }
+
+ #[inline]
+ pub fn is_slotted(&self) -> bool {
+ self.flags.intersects(SelectorFlags::HAS_SLOTTED)
+ }
+
+ #[inline]
+ pub fn is_part(&self) -> bool {
+ self.flags.intersects(SelectorFlags::HAS_PART)
+ }
+}
+
+const MAX_10BIT: u32 = (1u32 << 10) - 1;
+
+#[derive(Add, AddAssign, Clone, Copy, Default, Eq, Ord, PartialEq, PartialOrd)]
+struct Specificity {
+ id_selectors: u32,
+ class_like_selectors: u32,
+ element_selectors: u32,
+}
+
+impl From<u32> for Specificity {
+ #[inline]
+ fn from(value: u32) -> Specificity {
+ assert!(value <= MAX_10BIT << 20 | MAX_10BIT << 10 | MAX_10BIT);
+ Specificity {
+ id_selectors: value >> 20,
+ class_like_selectors: (value >> 10) & MAX_10BIT,
+ element_selectors: value & MAX_10BIT,
+ }
+ }
+}
+
+impl From<Specificity> for u32 {
+ #[inline]
+ fn from(specificity: Specificity) -> u32 {
+ cmp::min(specificity.id_selectors, MAX_10BIT) << 20 |
+ cmp::min(specificity.class_like_selectors, MAX_10BIT) << 10 |
+ cmp::min(specificity.element_selectors, MAX_10BIT)
+ }
+}
+
+fn specificity<Impl>(iter: slice::Iter<Component<Impl>>) -> u32
+where
+ Impl: SelectorImpl,
+{
+ complex_selector_specificity(iter).into()
+}
+
+fn complex_selector_specificity<Impl>(iter: slice::Iter<Component<Impl>>) -> Specificity
+where
+ Impl: SelectorImpl,
+{
+ fn simple_selector_specificity<Impl>(
+ simple_selector: &Component<Impl>,
+ specificity: &mut Specificity,
+ ) where
+ Impl: SelectorImpl,
+ {
+ match *simple_selector {
+ Component::Combinator(..) => {
+ unreachable!("Found combinator in simple selectors vector?");
+ },
+ Component::Part(..) | Component::PseudoElement(..) | Component::LocalName(..) => {
+ specificity.element_selectors += 1
+ },
+ Component::Slotted(ref selector) => {
+ specificity.element_selectors += 1;
+ // Note that due to the way ::slotted works we only compete with
+ // other ::slotted rules, so the above rule doesn't really
+ // matter, but we do it still for consistency with other
+ // pseudo-elements.
+ //
+ // See: https://github.com/w3c/csswg-drafts/issues/1915
+ *specificity += Specificity::from(selector.specificity());
+ },
+ Component::Host(ref selector) => {
+ specificity.class_like_selectors += 1;
+ if let Some(ref selector) = *selector {
+ // See: https://github.com/w3c/csswg-drafts/issues/1915
+ *specificity += Specificity::from(selector.specificity());
+ }
+ },
+ Component::ID(..) => {
+ specificity.id_selectors += 1;
+ },
+ Component::Class(..) |
+ Component::AttributeInNoNamespace { .. } |
+ Component::AttributeInNoNamespaceExists { .. } |
+ Component::AttributeOther(..) |
+ Component::FirstChild |
+ Component::LastChild |
+ Component::OnlyChild |
+ Component::Root |
+ Component::Empty |
+ Component::Scope |
+ Component::NthChild(..) |
+ Component::NthLastChild(..) |
+ Component::NthOfType(..) |
+ Component::NthLastOfType(..) |
+ Component::FirstOfType |
+ Component::LastOfType |
+ Component::OnlyOfType |
+ Component::NonTSPseudoClass(..) => {
+ specificity.class_like_selectors += 1;
+ },
+ Component::ExplicitUniversalType |
+ Component::ExplicitAnyNamespace |
+ Component::ExplicitNoNamespace |
+ Component::DefaultNamespace(..) |
+ Component::Namespace(..) => {
+ // Does not affect specificity
+ },
+ Component::Negation(ref negated) => {
+ for ss in negated.iter() {
+ simple_selector_specificity(&ss, specificity);
+ }
+ },
+ }
+ }
+
+ let mut specificity = Default::default();
+ for simple_selector in iter {
+ simple_selector_specificity(&simple_selector, &mut specificity);
+ }
+ specificity
+}
diff --git a/servo_crates/selectors/context.rs b/servo_crates/selectors/context.rs
new file mode 100644
index 00000000..44d586c8
--- /dev/null
+++ b/servo_crates/selectors/context.rs
@@ -0,0 +1,291 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+use crate::attr::CaseSensitivity;
+use crate::bloom::BloomFilter;
+use crate::nth_index_cache::NthIndexCache;
+use crate::parser::SelectorImpl;
+use crate::tree::{Element, OpaqueElement};
+
+/// What kind of selector matching mode we should use.
+///
+/// There are two modes of selector matching. The difference is only noticeable
+/// in presence of pseudo-elements.
+#[derive(Clone, Copy, Debug, PartialEq)]
+pub enum MatchingMode {
+ /// Don't ignore any pseudo-element selectors.
+ Normal,
+
+ /// Ignores any stateless pseudo-element selectors in the rightmost sequence
+ /// of simple selectors.
+ ///
+ /// This is useful, for example, to match against ::before when you aren't a
+ /// pseudo-element yourself.
+ ///
+ /// For example, in presence of `::before:hover`, it would never match, but
+ /// `::before` would be ignored as in "matching".
+ ///
+ /// It's required for all the selectors you match using this mode to have a
+ /// pseudo-element.
+ ForStatelessPseudoElement,
+}
+
+/// The mode to use when matching unvisited and visited links.
+#[derive(Clone, Copy, Debug, Eq, PartialEq)]
+pub enum VisitedHandlingMode {
+ /// All links are matched as if they are unvisted.
+ AllLinksUnvisited,
+ /// All links are matched as if they are visited and unvisited (both :link
+ /// and :visited match).
+ ///
+ /// This is intended to be used from invalidation code, to be conservative
+ /// about whether we need to restyle a link.
+ AllLinksVisitedAndUnvisited,
+ /// A element's "relevant link" is the element being matched if it is a link
+ /// or the nearest ancestor link. The relevant link is matched as though it
+ /// is visited, and all other links are matched as if they are unvisited.
+ RelevantLinkVisited,
+}
+
+impl VisitedHandlingMode {
+ #[inline]
+ pub fn matches_visited(&self) -> bool {
+ matches!(
+ *self,
+ VisitedHandlingMode::RelevantLinkVisited |
+ VisitedHandlingMode::AllLinksVisitedAndUnvisited
+ )
+ }
+
+ #[inline]
+ pub fn matches_unvisited(&self) -> bool {
+ matches!(
+ *self,
+ VisitedHandlingMode::AllLinksUnvisited |
+ VisitedHandlingMode::AllLinksVisitedAndUnvisited
+ )
+ }
+}
+
+/// Which quirks mode is this document in.
+///
+/// See: https://quirks.spec.whatwg.org/
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+pub enum QuirksMode {
+ /// Quirks mode.
+ Quirks,
+ /// Limited quirks mode.
+ LimitedQuirks,
+ /// No quirks mode.
+ NoQuirks,
+}
+
+impl QuirksMode {
+ #[inline]
+ pub fn classes_and_ids_case_sensitivity(self) -> CaseSensitivity {
+ match self {
+ QuirksMode::NoQuirks | QuirksMode::LimitedQuirks => CaseSensitivity::CaseSensitive,
+ QuirksMode::Quirks => CaseSensitivity::AsciiCaseInsensitive,
+ }
+ }
+}
+
+/// Data associated with the matching process for a element. This context is
+/// used across many selectors for an element, so it's not appropriate for
+/// transient data that applies to only a single selector.
+pub struct MatchingContext<'a, Impl>
+where
+ Impl: SelectorImpl,
+{
+ /// Input with the matching mode we should use when matching selectors.
+ matching_mode: MatchingMode,
+ /// Input with the bloom filter used to fast-reject selectors.
+ pub bloom_filter: Option<&'a BloomFilter>,
+ /// An optional cache to speed up nth-index-like selectors.
+ pub nth_index_cache: Option<&'a mut NthIndexCache>,
+ /// The element which is going to match :scope pseudo-class. It can be
+ /// either one :scope element, or the scoping element.
+ ///
+ /// Note that, although in theory there can be multiple :scope elements,
+ /// in current specs, at most one is specified, and when there is one,
+ /// scoping element is not relevant anymore, so we use a single field for
+ /// them.
+ ///
+ /// When this is None, :scope will match the root element.
+ ///
+ /// See https://drafts.csswg.org/selectors-4/#scope-pseudo
+ pub scope_element: Option<OpaqueElement>,
+
+ /// The current shadow host we're collecting :host rules for.
+ pub current_host: Option<OpaqueElement>,
+
+ /// Controls how matching for links is handled.
+ visited_handling: VisitedHandlingMode,
+
+ /// The current nesting level of selectors that we're matching.
+ ///
+ /// FIXME(emilio): Consider putting the mutable stuff in a Cell, then make
+ /// MatchingContext immutable again.
+ nesting_level: usize,
+
+ /// Whether we're inside a negation or not.
+ in_negation: bool,
+
+ /// An optional hook function for checking whether a pseudo-element
+ /// should match when matching_mode is ForStatelessPseudoElement.
+ pub pseudo_element_matching_fn: Option<&'a dyn Fn(&Impl::PseudoElement) -> bool>,
+
+ /// Extra implementation-dependent matching data.
+ pub extra_data: Impl::ExtraMatchingData,
+
+ quirks_mode: QuirksMode,
+ classes_and_ids_case_sensitivity: CaseSensitivity,
+ _impl: ::std::marker::PhantomData<Impl>,
+}
+
+impl<'a, Impl> MatchingContext<'a, Impl>
+where
+ Impl: SelectorImpl,
+{
+ /// Constructs a new `MatchingContext`.
+ pub fn new(
+ matching_mode: MatchingMode,
+ bloom_filter: Option<&'a BloomFilter>,
+ nth_index_cache: Option<&'a mut NthIndexCache>,
+ quirks_mode: QuirksMode,
+ ) -> Self {
+ Self::new_for_visited(
+ matching_mode,
+ bloom_filter,
+ nth_index_cache,
+ VisitedHandlingMode::AllLinksUnvisited,
+ quirks_mode,
+ )
+ }
+
+ /// Constructs a new `MatchingContext` for use in visited matching.
+ pub fn new_for_visited(
+ matching_mode: MatchingMode,
+ bloom_filter: Option<&'a BloomFilter>,
+ nth_index_cache: Option<&'a mut NthIndexCache>,
+ visited_handling: VisitedHandlingMode,
+ quirks_mode: QuirksMode,
+ ) -> Self {
+ Self {
+ matching_mode,
+ bloom_filter,
+ visited_handling,
+ nth_index_cache,
+ quirks_mode,
+ classes_and_ids_case_sensitivity: quirks_mode.classes_and_ids_case_sensitivity(),
+ scope_element: None,
+ current_host: None,
+ nesting_level: 0,
+ in_negation: false,
+ pseudo_element_matching_fn: None,
+ extra_data: Default::default(),
+ _impl: ::std::marker::PhantomData,
+ }
+ }
+
+ /// Whether we're matching a nested selector.
+ #[inline]
+ pub fn is_nested(&self) -> bool {
+ self.nesting_level != 0
+ }
+
+ /// Whether we're matching inside a :not(..) selector.
+ #[inline]
+ pub fn in_negation(&self) -> bool {
+ self.in_negation
+ }
+
+ /// The quirks mode of the document.
+ #[inline]
+ pub fn quirks_mode(&self) -> QuirksMode {
+ self.quirks_mode
+ }
+
+ /// The matching-mode for this selector-matching operation.
+ #[inline]
+ pub fn matching_mode(&self) -> MatchingMode {
+ self.matching_mode
+ }
+
+ /// The case-sensitivity for class and ID selectors
+ #[inline]
+ pub fn classes_and_ids_case_sensitivity(&self) -> CaseSensitivity {
+ self.classes_and_ids_case_sensitivity
+ }
+
+ /// Runs F with a deeper nesting level.
+ #[inline]
+ pub fn nest<F, R>(&mut self, f: F) -> R
+ where
+ F: FnOnce(&mut Self) -> R,
+ {
+ self.nesting_level += 1;
+ let result = f(self);
+ self.nesting_level -= 1;
+ result
+ }
+
+ /// Runs F with a deeper nesting level, and marking ourselves in a negation,
+ /// for a :not(..) selector, for example.
+ #[inline]
+ pub fn nest_for_negation<F, R>(&mut self, f: F) -> R
+ where
+ F: FnOnce(&mut Self) -> R,
+ {
+ debug_assert!(!self.in_negation, "Someone messed up parsing?");
+ self.in_negation = true;
+ let result = self.nest(f);
+ self.in_negation = false;
+ result
+ }
+
+ #[inline]
+ pub fn visited_handling(&self) -> VisitedHandlingMode {
+ self.visited_handling
+ }
+
+ /// Runs F with a different VisitedHandlingMode.
+ #[inline]
+ pub fn with_visited_handling_mode<F, R>(
+ &mut self,
+ handling_mode: VisitedHandlingMode,
+ f: F,
+ ) -> R
+ where
+ F: FnOnce(&mut Self) -> R,
+ {
+ let original_handling_mode = self.visited_handling;
+ self.visited_handling = handling_mode;
+ let result = f(self);
+ self.visited_handling = original_handling_mode;
+ result
+ }
+
+ /// Runs F with a given shadow host which is the root of the tree whose
+ /// rules we're matching.
+ #[inline]
+ pub fn with_shadow_host<F, E, R>(&mut self, host: Option<E>, f: F) -> R
+ where
+ E: Element,
+ F: FnOnce(&mut Self) -> R,
+ {
+ let original_host = self.current_host.take();
+ self.current_host = host.map(|h| h.opaque());
+ let result = f(self);
+ self.current_host = original_host;
+ result
+ }
+
+ /// Returns the current shadow host whose shadow root we're matching rules
+ /// against.
+ #[inline]
+ pub fn shadow_host(&self) -> Option<OpaqueElement> {
+ self.current_host.clone()
+ }
+}
diff --git a/servo_crates/selectors/lib.rs b/servo_crates/selectors/lib.rs
new file mode 100644
index 00000000..e8d8062d
--- /dev/null
+++ b/servo_crates/selectors/lib.rs
@@ -0,0 +1,41 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+// Make |cargo bench| work.
+#![cfg_attr(feature = "bench", feature(test))]
+
+#[macro_use]
+extern crate bitflags;
+#[macro_use]
+extern crate cssparser;
+#[macro_use]
+extern crate derive_more;
+extern crate fxhash;
+#[macro_use]
+extern crate log;
+#[macro_use]
+extern crate matches;
+extern crate phf;
+extern crate precomputed_hash;
+extern crate servo_arc;
+extern crate smallvec;
+extern crate thin_slice;
+extern crate to_shmem;
+#[macro_use]
+extern crate to_shmem_derive;
+
+pub mod attr;
+pub mod bloom;
+mod builder;
+pub mod context;
+pub mod matching;
+mod nth_index_cache;
+pub mod parser;
+pub mod sink;
+mod tree;
+pub mod visitor;
+
+pub use crate::nth_index_cache::NthIndexCache;
+pub use crate::parser::{Parser, SelectorImpl, SelectorList};
+pub use crate::tree::{Element, OpaqueElement};
diff --git a/servo_crates/selectors/matching.rs b/servo_crates/selectors/matching.rs
new file mode 100644
index 00000000..49b7f3db
--- /dev/null
+++ b/servo_crates/selectors/matching.rs
@@ -0,0 +1,977 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+use crate::attr::{AttrSelectorOperation, NamespaceConstraint, ParsedAttrSelectorOperation};
+use crate::bloom::{BloomFilter, BLOOM_HASH_MASK};
+use crate::nth_index_cache::NthIndexCacheInner;
+use crate::parser::{AncestorHashes, Combinator, Component, LocalName};
+use crate::parser::{NonTSPseudoClass, Selector, SelectorImpl, SelectorIter, SelectorList};
+use crate::tree::Element;
+use std::borrow::Borrow;
+use std::iter;
+
+pub use crate::context::*;
+
+// The bloom filter for descendant CSS selectors will have a <1% false
+// positive rate until it has this many selectors in it, then it will
+// rapidly increase.
+pub static RECOMMENDED_SELECTOR_BLOOM_FILTER_SIZE: usize = 4096;
+
+bitflags! {
+ /// Set of flags that are set on either the element or its parent (depending
+ /// on the flag) if the element could potentially match a selector.
+ pub struct ElementSelectorFlags: usize {
+ /// When a child is added or removed from the parent, all the children
+ /// must be restyled, because they may match :nth-last-child,
+ /// :last-of-type, :nth-last-of-type, or :only-of-type.
+ const HAS_SLOW_SELECTOR = 1 << 0;
+
+ /// When a child is added or removed from the parent, any later
+ /// children must be restyled, because they may match :nth-child,
+ /// :first-of-type, or :nth-of-type.
+ const HAS_SLOW_SELECTOR_LATER_SIBLINGS = 1 << 1;
+
+ /// When a child is added or removed from the parent, the first and
+ /// last children must be restyled, because they may match :first-child,
+ /// :last-child, or :only-child.
+ const HAS_EDGE_CHILD_SELECTOR = 1 << 2;
+
+ /// The element has an empty selector, so when a child is appended we
+ /// might need to restyle the parent completely.
+ const HAS_EMPTY_SELECTOR = 1 << 3;
+ }
+}
+
+impl ElementSelectorFlags {
+ /// Returns the subset of flags that apply to the element.
+ pub fn for_self(self) -> ElementSelectorFlags {
+ self & (ElementSelectorFlags::HAS_EMPTY_SELECTOR)
+ }
+
+ /// Returns the subset of flags that apply to the parent.
+ pub fn for_parent(self) -> ElementSelectorFlags {
+ self & (ElementSelectorFlags::HAS_SLOW_SELECTOR |
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS |
+ ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR)
+ }
+}
+
+/// Holds per-compound-selector data.
+struct LocalMatchingContext<'a, 'b: 'a, Impl: SelectorImpl> {
+ shared: &'a mut MatchingContext<'b, Impl>,
+ matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk,
+}
+
+#[inline(always)]
+pub fn matches_selector_list<E>(
+ selector_list: &SelectorList<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+) -> bool
+where
+ E: Element,
+{
+ // This is pretty much any(..) but manually inlined because the compiler
+ // refuses to do so from querySelector / querySelectorAll.
+ for selector in &selector_list.0 {
+ let matches = matches_selector(selector, 0, None, element, context, &mut |_, _| {});
+
+ if matches {
+ return true;
+ }
+ }
+
+ false
+}
+
+#[inline(always)]
+fn may_match(hashes: &AncestorHashes, bf: &BloomFilter) -> bool {
+ // Check the first three hashes. Note that we can check for zero before
+ // masking off the high bits, since if any of the first three hashes is
+ // zero the fourth will be as well. We also take care to avoid the
+ // special-case complexity of the fourth hash until we actually reach it,
+ // because we usually don't.
+ //
+ // To be clear: this is all extremely hot.
+ for i in 0..3 {
+ let packed = hashes.packed_hashes[i];
+ if packed == 0 {
+ // No more hashes left - unable to fast-reject.
+ return true;
+ }
+
+ if !bf.might_contain_hash(packed & BLOOM_HASH_MASK) {
+ // Hooray! We fast-rejected on this hash.
+ return false;
+ }
+ }
+
+ // Now do the slighty-more-complex work of synthesizing the fourth hash,
+ // and check it against the filter if it exists.
+ let fourth = hashes.fourth_hash();
+ fourth == 0 || bf.might_contain_hash(fourth)
+}
+
+/// A result of selector matching, includes 3 failure types,
+///
+/// NotMatchedAndRestartFromClosestLaterSibling
+/// NotMatchedAndRestartFromClosestDescendant
+/// NotMatchedGlobally
+///
+/// When NotMatchedGlobally appears, stop selector matching completely since
+/// the succeeding selectors never matches.
+/// It is raised when
+/// Child combinator cannot find the candidate element.
+/// Descendant combinator cannot find the candidate element.
+///
+/// When NotMatchedAndRestartFromClosestDescendant appears, the selector
+/// matching does backtracking and restarts from the closest Descendant
+/// combinator.
+/// It is raised when
+/// NextSibling combinator cannot find the candidate element.
+/// LaterSibling combinator cannot find the candidate element.
+/// Child combinator doesn't match on the found element.
+///
+/// When NotMatchedAndRestartFromClosestLaterSibling appears, the selector
+/// matching does backtracking and restarts from the closest LaterSibling
+/// combinator.
+/// It is raised when
+/// NextSibling combinator doesn't match on the found element.
+///
+/// For example, when the selector "d1 d2 a" is provided and we cannot *find*
+/// an appropriate ancestor element for "d1", this selector matching raises
+/// NotMatchedGlobally since even if "d2" is moved to more upper element, the
+/// candidates for "d1" becomes less than before and d1 .
+///
+/// The next example is siblings. When the selector "b1 + b2 ~ d1 a" is
+/// provided and we cannot *find* an appropriate brother element for b1,
+/// the selector matching raises NotMatchedAndRestartFromClosestDescendant.
+/// The selectors ("b1 + b2 ~") doesn't match and matching restart from "d1".
+///
+/// The additional example is child and sibling. When the selector
+/// "b1 + c1 > b2 ~ d1 a" is provided and the selector "b1" doesn't match on
+/// the element, this "b1" raises NotMatchedAndRestartFromClosestLaterSibling.
+/// However since the selector "c1" raises
+/// NotMatchedAndRestartFromClosestDescendant. So the selector
+/// "b1 + c1 > b2 ~ " doesn't match and restart matching from "d1".
+#[derive(Clone, Copy, Eq, PartialEq)]
+enum SelectorMatchingResult {
+ Matched,
+ NotMatchedAndRestartFromClosestLaterSibling,
+ NotMatchedAndRestartFromClosestDescendant,
+ NotMatchedGlobally,
+}
+
+/// Whether the :hover and :active quirk applies.
+///
+/// https://quirks.spec.whatwg.org/#the-active-and-hover-quirk
+#[derive(Clone, Copy, Debug, PartialEq)]
+enum MatchesHoverAndActiveQuirk {
+ Yes,
+ No,
+}
+
+/// Matches a selector, fast-rejecting against a bloom filter.
+///
+/// We accept an offset to allow consumers to represent and match against
+/// partial selectors (indexed from the right). We use this API design, rather
+/// than having the callers pass a SelectorIter, because creating a SelectorIter
+/// requires dereferencing the selector to get the length, which adds an
+/// unncessary cache miss for cases when we can fast-reject with AncestorHashes
+/// (which the caller can store inline with the selector pointer).
+#[inline(always)]
+pub fn matches_selector<E, F>(
+ selector: &Selector<E::Impl>,
+ offset: usize,
+ hashes: Option<&AncestorHashes>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ flags_setter: &mut F,
+) -> bool
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ // Use the bloom filter to fast-reject.
+ if let Some(hashes) = hashes {
+ if let Some(filter) = context.bloom_filter {
+ if !may_match(hashes, filter) {
+ return false;
+ }
+ }
+ }
+
+ matches_complex_selector(selector.iter_from(offset), element, context, flags_setter)
+}
+
+/// Whether a compound selector matched, and whether it was the rightmost
+/// selector inside the complex selector.
+pub enum CompoundSelectorMatchingResult {
+ /// The selector was fully matched.
+ FullyMatched,
+ /// The compound selector matched, and the next combinator offset is
+ /// `next_combinator_offset`.
+ Matched { next_combinator_offset: usize },
+ /// The selector didn't match.
+ NotMatched,
+}
+
+/// Matches a compound selector belonging to `selector`, starting at offset
+/// `from_offset`, matching left to right.
+///
+/// Requires that `from_offset` points to a `Combinator`.
+///
+/// NOTE(emilio): This doesn't allow to match in the leftmost sequence of the
+/// complex selector, but it happens to be the case we don't need it.
+pub fn matches_compound_selector_from<E>(
+ selector: &Selector<E::Impl>,
+ mut from_offset: usize,
+ context: &mut MatchingContext<E::Impl>,
+ element: &E,
+) -> CompoundSelectorMatchingResult
+where
+ E: Element,
+{
+ if cfg!(debug_assertions) && from_offset != 0 {
+ selector.combinator_at_parse_order(from_offset - 1); // This asserts.
+ }
+
+ let mut local_context = LocalMatchingContext {
+ shared: context,
+ matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk::No,
+ };
+
+ // Find the end of the selector or the next combinator, then match
+ // backwards, so that we match in the same order as
+ // matches_complex_selector, which is usually faster.
+ let start_offset = from_offset;
+ for component in selector.iter_raw_parse_order_from(from_offset) {
+ if matches!(*component, Component::Combinator(..)) {
+ debug_assert_ne!(from_offset, 0, "Selector started with a combinator?");
+ break;
+ }
+
+ from_offset += 1;
+ }
+
+ debug_assert!(from_offset >= 1);
+ debug_assert!(from_offset <= selector.len());
+
+ let iter = selector.iter_from(selector.len() - from_offset);
+ debug_assert!(
+ iter.clone().next().is_some() ||
+ (from_offset != selector.len() &&
+ matches!(
+ selector.combinator_at_parse_order(from_offset),
+ Combinator::SlotAssignment | Combinator::PseudoElement
+ )),
+ "Got the math wrong: {:?} | {:?} | {} {}",
+ selector,
+ selector.iter_raw_match_order().as_slice(),
+ from_offset,
+ start_offset
+ );
+
+ for component in iter {
+ if !matches_simple_selector(component, element, &mut local_context, &mut |_, _| {}) {
+ return CompoundSelectorMatchingResult::NotMatched;
+ }
+ }
+
+ if from_offset != selector.len() {
+ return CompoundSelectorMatchingResult::Matched {
+ next_combinator_offset: from_offset,
+ };
+ }
+
+ CompoundSelectorMatchingResult::FullyMatched
+}
+
+/// Matches a complex selector.
+#[inline(always)]
+pub fn matches_complex_selector<E, F>(
+ mut iter: SelectorIter<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ flags_setter: &mut F,
+) -> bool
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ // If this is the special pseudo-element mode, consume the ::pseudo-element
+ // before proceeding, since the caller has already handled that part.
+ if context.matching_mode() == MatchingMode::ForStatelessPseudoElement && !context.is_nested() {
+ // Consume the pseudo.
+ match *iter.next().unwrap() {
+ Component::PseudoElement(ref pseudo) => {
+ if let Some(ref f) = context.pseudo_element_matching_fn {
+ if !f(pseudo) {
+ return false;
+ }
+ }
+ },
+ _ => {
+ debug_assert!(
+ false,
+ "Used MatchingMode::ForStatelessPseudoElement \
+ in a non-pseudo selector"
+ );
+ },
+ }
+
+ // The only other parser-allowed Component in this sequence is a state
+ // class. We just don't match in that case.
+ if let Some(s) = iter.next() {
+ debug_assert!(
+ matches!(*s, Component::NonTSPseudoClass(..)),
+ "Someone messed up pseudo-element parsing"
+ );
+ return false;
+ }
+
+ // Advance to the non-pseudo-element part of the selector.
+ let next_sequence = iter.next_sequence().unwrap();
+ debug_assert_eq!(next_sequence, Combinator::PseudoElement);
+ }
+
+ let result =
+ matches_complex_selector_internal(iter, element, context, flags_setter, Rightmost::Yes);
+
+ match result {
+ SelectorMatchingResult::Matched => true,
+ _ => false,
+ }
+}
+
+#[inline]
+fn matches_hover_and_active_quirk<Impl: SelectorImpl>(
+ selector_iter: &SelectorIter<Impl>,
+ context: &MatchingContext<Impl>,
+ rightmost: Rightmost,
+) -> MatchesHoverAndActiveQuirk {
+ if context.quirks_mode() != QuirksMode::Quirks {
+ return MatchesHoverAndActiveQuirk::No;
+ }
+
+ if context.is_nested() {
+ return MatchesHoverAndActiveQuirk::No;
+ }
+
+ // This compound selector had a pseudo-element to the right that we
+ // intentionally skipped.
+ if rightmost == Rightmost::Yes &&
+ context.matching_mode() == MatchingMode::ForStatelessPseudoElement
+ {
+ return MatchesHoverAndActiveQuirk::No;
+ }
+
+ let all_match = selector_iter.clone().all(|simple| match *simple {
+ Component::LocalName(_) |
+ Component::AttributeInNoNamespaceExists { .. } |
+ Component::AttributeInNoNamespace { .. } |
+ Component::AttributeOther(_) |
+ Component::ID(_) |
+ Component::Class(_) |
+ Component::PseudoElement(_) |
+ Component::Negation(_) |
+ Component::FirstChild |
+ Component::LastChild |
+ Component::OnlyChild |
+ Component::Empty |
+ Component::NthChild(_, _) |
+ Component::NthLastChild(_, _) |
+ Component::NthOfType(_, _) |
+ Component::NthLastOfType(_, _) |
+ Component::FirstOfType |
+ Component::LastOfType |
+ Component::OnlyOfType => false,
+ Component::NonTSPseudoClass(ref pseudo_class) => pseudo_class.is_active_or_hover(),
+ _ => true,
+ });
+
+ if all_match {
+ MatchesHoverAndActiveQuirk::Yes
+ } else {
+ MatchesHoverAndActiveQuirk::No
+ }
+}
+
+#[derive(Clone, Copy, PartialEq)]
+enum Rightmost {
+ Yes,
+ No,
+}
+
+#[inline(always)]
+fn next_element_for_combinator<E>(
+ element: &E,
+ combinator: Combinator,
+ selector: &SelectorIter<E::Impl>,
+ context: &MatchingContext<E::Impl>,
+) -> Option<E>
+where
+ E: Element,
+{
+ match combinator {
+ Combinator::NextSibling | Combinator::LaterSibling => element.prev_sibling_element(),
+ Combinator::Child | Combinator::Descendant => {
+ match element.parent_element() {
+ Some(e) => return Some(e),
+ None => {},
+ }
+
+ if !element.parent_node_is_shadow_root() {
+ return None;
+ }
+
+ // https://drafts.csswg.org/css-scoping/#host-element-in-tree:
+ //
+ // For the purpose of Selectors, a shadow host also appears in
+ // its shadow tree, with the contents of the shadow tree treated
+ // as its children. (In other words, the shadow host is treated as
+ // replacing the shadow root node.)
+ //
+ // and also:
+ //
+ // When considered within its own shadow trees, the shadow host is
+ // featureless. Only the :host, :host(), and :host-context()
+ // pseudo-classes are allowed to match it.
+ //
+ // Since we know that the parent is a shadow root, we necessarily
+ // are in a shadow tree of the host, and the next selector will only
+ // match if the selector is a featureless :host selector.
+ if !selector.clone().is_featureless_host_selector() {
+ return None;
+ }
+
+ element.containing_shadow_host()
+ },
+ Combinator::Part => element.containing_shadow_host(),
+ Combinator::SlotAssignment => {
+ debug_assert!(element
+ .assigned_slot()
+ .map_or(true, |s| s.is_html_slot_element()));
+ let scope = context.current_host?;
+ let mut current_slot = element.assigned_slot()?;
+ while current_slot.containing_shadow_host().unwrap().opaque() != scope {
+ current_slot = current_slot.assigned_slot()?;
+ }
+ Some(current_slot)
+ },
+ Combinator::PseudoElement => element.pseudo_element_originating_element(),
+ }
+}
+
+fn matches_complex_selector_internal<E, F>(
+ mut selector_iter: SelectorIter<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ flags_setter: &mut F,
+ rightmost: Rightmost,
+) -> SelectorMatchingResult
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ debug!(
+ "Matching complex selector {:?} for {:?}",
+ selector_iter, element
+ );
+
+ let matches_compound_selector = matches_compound_selector(
+ &mut selector_iter,
+ element,
+ context,
+ flags_setter,
+ rightmost,
+ );
+
+ let combinator = selector_iter.next_sequence();
+ if combinator.map_or(false, |c| c.is_sibling()) {
+ flags_setter(
+ element,
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS,
+ );
+ }
+
+ if !matches_compound_selector {
+ return SelectorMatchingResult::NotMatchedAndRestartFromClosestLaterSibling;
+ }
+
+ let combinator = match combinator {
+ None => return SelectorMatchingResult::Matched,
+ Some(c) => c,
+ };
+
+ let candidate_not_found = match combinator {
+ Combinator::NextSibling | Combinator::LaterSibling => {
+ SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant
+ },
+ Combinator::Child |
+ Combinator::Descendant |
+ Combinator::SlotAssignment |
+ Combinator::Part |
+ Combinator::PseudoElement => SelectorMatchingResult::NotMatchedGlobally,
+ };
+
+ let mut next_element =
+ next_element_for_combinator(element, combinator, &selector_iter, &context);
+
+ // Stop matching :visited as soon as we find a link, or a combinator for
+ // something that isn't an ancestor.
+ let mut visited_handling = if element.is_link() || combinator.is_sibling() {
+ VisitedHandlingMode::AllLinksUnvisited
+ } else {
+ context.visited_handling()
+ };
+
+ loop {
+ let element = match next_element {
+ None => return candidate_not_found,
+ Some(next_element) => next_element,
+ };
+
+ let result = context.with_visited_handling_mode(visited_handling, |context| {
+ matches_complex_selector_internal(
+ selector_iter.clone(),
+ &element,
+ context,
+ flags_setter,
+ Rightmost::No,
+ )
+ });
+
+ match (result, combinator) {
+ // Return the status immediately.
+ (SelectorMatchingResult::Matched, _) |
+ (SelectorMatchingResult::NotMatchedGlobally, _) |
+ (_, Combinator::NextSibling) => {
+ return result;
+ },
+
+ // Upgrade the failure status to
+ // NotMatchedAndRestartFromClosestDescendant.
+ (_, Combinator::PseudoElement) | (_, Combinator::Child) => {
+ return SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant;
+ },
+
+ // If the failure status is
+ // NotMatchedAndRestartFromClosestDescendant and combinator is
+ // Combinator::LaterSibling, give up this Combinator::LaterSibling
+ // matching and restart from the closest descendant combinator.
+ (
+ SelectorMatchingResult::NotMatchedAndRestartFromClosestDescendant,
+ Combinator::LaterSibling,
+ ) => {
+ return result;
+ },
+
+ // The Combinator::Descendant combinator and the status is
+ // NotMatchedAndRestartFromClosestLaterSibling or
+ // NotMatchedAndRestartFromClosestDescendant, or the
+ // Combinator::LaterSibling combinator and the status is
+ // NotMatchedAndRestartFromClosestDescendant, we can continue to
+ // matching on the next candidate element.
+ _ => {},
+ }
+
+ if element.is_link() {
+ visited_handling = VisitedHandlingMode::AllLinksUnvisited;
+ }
+
+ next_element = next_element_for_combinator(&element, combinator, &selector_iter, &context);
+ }
+}
+
+#[inline]
+fn matches_local_name<E>(element: &E, local_name: &LocalName<E::Impl>) -> bool
+where
+ E: Element,
+{
+ let name = select_name(
+ element.is_html_element_in_html_document(),
+ &local_name.name,
+ &local_name.lower_name,
+ )
+ .borrow();
+ element.has_local_name(name)
+}
+
+/// Determines whether the given element matches the given compound selector.
+#[inline]
+fn matches_compound_selector<E, F>(
+ selector_iter: &mut SelectorIter<E::Impl>,
+ element: &E,
+ context: &mut MatchingContext<E::Impl>,
+ flags_setter: &mut F,
+ rightmost: Rightmost,
+) -> bool
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ let matches_hover_and_active_quirk =
+ matches_hover_and_active_quirk(&selector_iter, context, rightmost);
+
+ // Handle some common cases first.
+ // We may want to get rid of this at some point if we can make the
+ // generic case fast enough.
+ let mut selector = selector_iter.next();
+ if let Some(&Component::LocalName(ref local_name)) = selector {
+ if !matches_local_name(element, local_name) {
+ return false;
+ }
+ selector = selector_iter.next();
+ }
+ let class_and_id_case_sensitivity = context.classes_and_ids_case_sensitivity();
+ if let Some(&Component::ID(ref id)) = selector {
+ if !element.has_id(id, class_and_id_case_sensitivity) {
+ return false;
+ }
+ selector = selector_iter.next();
+ }
+ while let Some(&Component::Class(ref class)) = selector {
+ if !element.has_class(class, class_and_id_case_sensitivity) {
+ return false;
+ }
+ selector = selector_iter.next();
+ }
+ let selector = match selector {
+ Some(s) => s,
+ None => return true,
+ };
+
+ let mut local_context = LocalMatchingContext {
+ shared: context,
+ matches_hover_and_active_quirk,
+ };
+ iter::once(selector)
+ .chain(selector_iter)
+ .all(|simple| matches_simple_selector(simple, element, &mut local_context, flags_setter))
+}
+
+/// Determines whether the given element matches the given single selector.
+fn matches_simple_selector<E, F>(
+ selector: &Component<E::Impl>,
+ element: &E,
+ context: &mut LocalMatchingContext<E::Impl>,
+ flags_setter: &mut F,
+) -> bool
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ debug_assert!(context.shared.is_nested() || !context.shared.in_negation());
+
+ match *selector {
+ Component::Combinator(_) => unreachable!(),
+ Component::Part(ref parts) => parts.iter().all(|part| element.is_part(part)),
+ Component::Slotted(ref selector) => {
+ // <slots> are never flattened tree slottables.
+ !element.is_html_slot_element() &&
+ context.shared.nest(|context| {
+ matches_complex_selector(selector.iter(), element, context, flags_setter)
+ })
+ },
+ Component::PseudoElement(ref pseudo) => {
+ element.match_pseudo_element(pseudo, context.shared)
+ },
+ Component::LocalName(ref local_name) => matches_local_name(element, local_name),
+ Component::ExplicitUniversalType | Component::ExplicitAnyNamespace => true,
+ Component::Namespace(_, ref url) | Component::DefaultNamespace(ref url) => {
+ element.has_namespace(&url.borrow())
+ },
+ Component::ExplicitNoNamespace => {
+ let ns = crate::parser::namespace_empty_string::<E::Impl>();
+ element.has_namespace(&ns.borrow())
+ },
+ Component::ID(ref id) => {
+ element.has_id(id, context.shared.classes_and_ids_case_sensitivity())
+ },
+ Component::Class(ref class) => {
+ element.has_class(class, context.shared.classes_and_ids_case_sensitivity())
+ },
+ Component::AttributeInNoNamespaceExists {
+ ref local_name,
+ ref local_name_lower,
+ } => {
+ let is_html = element.is_html_element_in_html_document();
+ element.attr_matches(
+ &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
+ select_name(is_html, local_name, local_name_lower),
+ &AttrSelectorOperation::Exists,
+ )
+ },
+ Component::AttributeInNoNamespace {
+ ref local_name,
+ ref value,
+ operator,
+ case_sensitivity,
+ never_matches,
+ } => {
+ if never_matches {
+ return false;
+ }
+ let is_html = element.is_html_element_in_html_document();
+ element.attr_matches(
+ &NamespaceConstraint::Specific(&crate::parser::namespace_empty_string::<E::Impl>()),
+ local_name,
+ &AttrSelectorOperation::WithValue {
+ operator: operator,
+ case_sensitivity: case_sensitivity.to_unconditional(is_html),
+ expected_value: value,
+ },
+ )
+ },
+ Component::AttributeOther(ref attr_sel) => {
+ if attr_sel.never_matches {
+ return false;
+ }
+ let is_html = element.is_html_element_in_html_document();
+ let empty_string;
+ let namespace = match attr_sel.namespace() {
+ Some(ns) => ns,
+ None => {
+ empty_string = crate::parser::namespace_empty_string::<E::Impl>();
+ NamespaceConstraint::Specific(&empty_string)
+ },
+ };
+ element.attr_matches(
+ &namespace,
+ select_name(is_html, &attr_sel.local_name, &attr_sel.local_name_lower),
+ &match attr_sel.operation {
+ ParsedAttrSelectorOperation::Exists => AttrSelectorOperation::Exists,
+ ParsedAttrSelectorOperation::WithValue {
+ operator,
+ case_sensitivity,
+ ref expected_value,
+ } => AttrSelectorOperation::WithValue {
+ operator: operator,
+ case_sensitivity: case_sensitivity.to_unconditional(is_html),
+ expected_value: expected_value,
+ },
+ },
+ )
+ },
+ Component::NonTSPseudoClass(ref pc) => {
+ if context.matches_hover_and_active_quirk == MatchesHoverAndActiveQuirk::Yes &&
+ !context.shared.is_nested() &&
+ pc.is_active_or_hover() &&
+ !element.is_link()
+ {
+ return false;
+ }
+
+ element.match_non_ts_pseudo_class(pc, &mut context.shared, flags_setter)
+ },
+ Component::FirstChild => matches_first_child(element, flags_setter),
+ Component::LastChild => matches_last_child(element, flags_setter),
+ Component::OnlyChild => {
+ matches_first_child(element, flags_setter) && matches_last_child(element, flags_setter)
+ },
+ Component::Root => element.is_root(),
+ Component::Empty => {
+ flags_setter(element, ElementSelectorFlags::HAS_EMPTY_SELECTOR);
+ element.is_empty()
+ },
+ Component::Host(ref selector) => {
+ context
+ .shared
+ .shadow_host()
+ .map_or(false, |host| host == element.opaque()) &&
+ selector.as_ref().map_or(true, |selector| {
+ context.shared.nest(|context| {
+ matches_complex_selector(selector.iter(), element, context, flags_setter)
+ })
+ })
+ },
+ Component::Scope => match context.shared.scope_element {
+ Some(ref scope_element) => element.opaque() == *scope_element,
+ None => element.is_root(),
+ },
+ Component::NthChild(a, b) => {
+ matches_generic_nth_child(element, context, a, b, false, false, flags_setter)
+ },
+ Component::NthLastChild(a, b) => {
+ matches_generic_nth_child(element, context, a, b, false, true, flags_setter)
+ },
+ Component::NthOfType(a, b) => {
+ matches_generic_nth_child(element, context, a, b, true, false, flags_setter)
+ },
+ Component::NthLastOfType(a, b) => {
+ matches_generic_nth_child(element, context, a, b, true, true, flags_setter)
+ },
+ Component::FirstOfType => {
+ matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter)
+ },
+ Component::LastOfType => {
+ matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
+ },
+ Component::OnlyOfType => {
+ matches_generic_nth_child(element, context, 0, 1, true, false, flags_setter) &&
+ matches_generic_nth_child(element, context, 0, 1, true, true, flags_setter)
+ },
+ Component::Negation(ref negated) => context.shared.nest_for_negation(|context| {
+ let mut local_context = LocalMatchingContext {
+ matches_hover_and_active_quirk: MatchesHoverAndActiveQuirk::No,
+ shared: context,
+ };
+ !negated
+ .iter()
+ .all(|ss| matches_simple_selector(ss, element, &mut local_context, flags_setter))
+ }),
+ }
+}
+
+#[inline(always)]
+fn select_name<'a, T>(is_html: bool, local_name: &'a T, local_name_lower: &'a T) -> &'a T {
+ if is_html {
+ local_name_lower
+ } else {
+ local_name
+ }
+}
+
+#[inline]
+fn matches_generic_nth_child<E, F>(
+ element: &E,
+ context: &mut LocalMatchingContext<E::Impl>,
+ a: i32,
+ b: i32,
+ is_of_type: bool,
+ is_from_end: bool,
+ flags_setter: &mut F,
+) -> bool
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ if element.ignores_nth_child_selectors() {
+ return false;
+ }
+
+ flags_setter(
+ element,
+ if is_from_end {
+ ElementSelectorFlags::HAS_SLOW_SELECTOR
+ } else {
+ ElementSelectorFlags::HAS_SLOW_SELECTOR_LATER_SIBLINGS
+ },
+ );
+
+ // Grab a reference to the appropriate cache.
+ let mut cache = context
+ .shared
+ .nth_index_cache
+ .as_mut()
+ .map(|c| c.get(is_of_type, is_from_end));
+
+ // Lookup or compute the index.
+ let index = if let Some(i) = cache.as_mut().and_then(|c| c.lookup(element.opaque())) {
+ i
+ } else {
+ let i = nth_child_index(
+ element,
+ is_of_type,
+ is_from_end,
+ cache.as_mut().map(|s| &mut **s),
+ );
+ cache.as_mut().map(|c| c.insert(element.opaque(), i));
+ i
+ };
+ debug_assert_eq!(
+ index,
+ nth_child_index(element, is_of_type, is_from_end, None),
+ "invalid cache"
+ );
+
+ // Is there a non-negative integer n such that An+B=index?
+ match index.checked_sub(b) {
+ None => false,
+ Some(an) => match an.checked_div(a) {
+ Some(n) => n >= 0 && a * n == an,
+ None /* a == 0 */ => an == 0,
+ },
+ }
+}
+
+#[inline]
+fn nth_child_index<E>(
+ element: &E,
+ is_of_type: bool,
+ is_from_end: bool,
+ mut cache: Option<&mut NthIndexCacheInner>,
+) -> i32
+where
+ E: Element,
+{
+ // The traversal mostly processes siblings left to right. So when we walk
+ // siblings to the right when computing NthLast/NthLastOfType we're unlikely
+ // to get cache hits along the way. As such, we take the hit of walking the
+ // siblings to the left checking the cache in the is_from_end case (this
+ // matches what Gecko does). The indices-from-the-left is handled during the
+ // regular look further below.
+ if let Some(ref mut c) = cache {
+ if is_from_end && !c.is_empty() {
+ let mut index: i32 = 1;
+ let mut curr = element.clone();
+ while let Some(e) = curr.prev_sibling_element() {
+ curr = e;
+ if !is_of_type || element.is_same_type(&curr) {
+ if let Some(i) = c.lookup(curr.opaque()) {
+ return i - index;
+ }
+ index += 1;
+ }
+ }
+ }
+ }
+
+ let mut index: i32 = 1;
+ let mut curr = element.clone();
+ let next = |e: E| {
+ if is_from_end {
+ e.next_sibling_element()
+ } else {
+ e.prev_sibling_element()
+ }
+ };
+ while let Some(e) = next(curr) {
+ curr = e;
+ if !is_of_type || element.is_same_type(&curr) {
+ // If we're computing indices from the left, check each element in the
+ // cache. We handle the indices-from-the-right case at the top of this
+ // function.
+ if !is_from_end {
+ if let Some(i) = cache.as_mut().and_then(|c| c.lookup(curr.opaque())) {
+ return i + index;
+ }
+ }
+ index += 1;
+ }
+ }
+
+ index
+}
+
+#[inline]
+fn matches_first_child<E, F>(element: &E, flags_setter: &mut F) -> bool
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ flags_setter(element, ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR);
+ element.prev_sibling_element().is_none()
+}
+
+#[inline]
+fn matches_last_child<E, F>(element: &E, flags_setter: &mut F) -> bool
+where
+ E: Element,
+ F: FnMut(&E, ElementSelectorFlags),
+{
+ flags_setter(element, ElementSelectorFlags::HAS_EDGE_CHILD_SELECTOR);
+ element.next_sibling_element().is_none()
+}
diff --git a/servo_crates/selectors/nth_index_cache.rs b/servo_crates/selectors/nth_index_cache.rs
new file mode 100644
index 00000000..8d1d4792
--- /dev/null
+++ b/servo_crates/selectors/nth_index_cache.rs
@@ -0,0 +1,52 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+use crate::tree::OpaqueElement;
+use fxhash::FxHashMap;
+
+/// A cache to speed up matching of nth-index-like selectors.
+///
+/// See [1] for some discussion around the design tradeoffs.
+///
+/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1401855#c3
+#[derive(Default)]
+pub struct NthIndexCache {
+ nth: NthIndexCacheInner,
+ nth_last: NthIndexCacheInner,
+ nth_of_type: NthIndexCacheInner,
+ nth_last_of_type: NthIndexCacheInner,
+}
+
+impl NthIndexCache {
+ /// Gets the appropriate cache for the given parameters.
+ pub fn get(&mut self, is_of_type: bool, is_from_end: bool) -> &mut NthIndexCacheInner {
+ match (is_of_type, is_from_end) {
+ (false, false) => &mut self.nth,
+ (false, true) => &mut self.nth_last,
+ (true, false) => &mut self.nth_of_type,
+ (true, true) => &mut self.nth_last_of_type,
+ }
+ }
+}
+
+/// The concrete per-pseudo-class cache.
+#[derive(Default)]
+pub struct NthIndexCacheInner(FxHashMap<OpaqueElement, i32>);
+
+impl NthIndexCacheInner {
+ /// Does a lookup for a given element in the cache.
+ pub fn lookup(&mut self, el: OpaqueElement) -> Option<i32> {
+ self.0.get(&el).map(|x| *x)
+ }
+
+ /// Inserts an entry into the cache.
+ pub fn insert(&mut self, element: OpaqueElement, index: i32) {
+ self.0.insert(element, index);
+ }
+
+ /// Returns whether the cache is empty.
+ pub fn is_empty(&self) -> bool {
+ self.0.is_empty()
+ }
+}
diff --git a/servo_crates/selectors/parser.rs b/servo_crates/selectors/parser.rs
new file mode 100644
index 00000000..507121bb
--- /dev/null
+++ b/servo_crates/selectors/parser.rs
@@ -0,0 +1,3144 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+use crate::attr::{AttrSelectorOperator, AttrSelectorWithOptionalNamespace};
+use crate::attr::{NamespaceConstraint, ParsedAttrSelectorOperation};
+use crate::attr::{ParsedCaseSensitivity, SELECTOR_WHITESPACE};
+use crate::bloom::BLOOM_HASH_MASK;
+use crate::builder::{SelectorBuilder, SelectorFlags, SpecificityAndFlags};
+use crate::context::QuirksMode;
+use crate::sink::Push;
+pub use crate::visitor::{SelectorVisitor, Visit};
+use cssparser::{parse_nth, serialize_identifier};
+use cssparser::{BasicParseError, BasicParseErrorKind, ParseError, ParseErrorKind};
+use cssparser::{CowRcStr, Delimiter, SourceLocation};
+use cssparser::{CssStringWriter, Parser as CssParser, ToCss, Token};
+use precomputed_hash::PrecomputedHash;
+use servo_arc::ThinArc;
+use smallvec::SmallVec;
+use std::borrow::{Borrow, Cow};
+use std::fmt::{self, Debug, Display, Write};
+use std::iter::Rev;
+use std::slice;
+use thin_slice::ThinBoxedSlice;
+
+/// A trait that represents a pseudo-element.
+pub trait PseudoElement: Sized + ToCss {
+ /// The `SelectorImpl` this pseudo-element is used for.
+ type Impl: SelectorImpl;
+
+ /// Whether the pseudo-element supports a given state selector to the right
+ /// of it.
+ fn accepts_state_pseudo_classes(&self) -> bool {
+ false
+ }
+
+ /// Whether this pseudo-element is valid after a ::slotted(..) pseudo.
+ fn valid_after_slotted(&self) -> bool {
+ false
+ }
+}
+
+/// A trait that represents a pseudo-class.
+pub trait NonTSPseudoClass: Sized + ToCss {
+ /// The `SelectorImpl` this pseudo-element is used for.
+ type Impl: SelectorImpl;
+
+ /// Whether this pseudo-class is :active or :hover.
+ fn is_active_or_hover(&self) -> bool;
+
+ /// Whether this pseudo-class belongs to:
+ ///
+ /// https://drafts.csswg.org/selectors-4/#useraction-pseudos
+ fn is_user_action_state(&self) -> bool;
+}
+
+/// Returns a Cow::Borrowed if `s` is already ASCII lowercase, and a
+/// Cow::Owned if `s` had to be converted into ASCII lowercase.
+fn to_ascii_lowercase(s: &str) -> Cow<str> {
+ if let Some(first_uppercase) = s.bytes().position(|byte| byte >= b'A' && byte <= b'Z') {
+ let mut string = s.to_owned();
+ string[first_uppercase..].make_ascii_lowercase();
+ string.into()
+ } else {
+ s.into()
+ }
+}
+
+bitflags! {
+ /// Flags that indicate at which point of parsing a selector are we.
+ struct SelectorParsingState: u8 {
+ /// Whether we're inside a negation. If we're inside a negation, we're
+ /// not allowed to add another negation or such, for example.
+ const INSIDE_NEGATION = 1 << 0;
+ /// Whether we've parsed a ::slotted() pseudo-element already.
+ ///
+ /// If so, then we can only parse a subset of pseudo-elements, and
+ /// whatever comes after them if so.
+ const AFTER_SLOTTED = 1 << 1;
+ /// Whether we've parsed a ::part() pseudo-element already.
+ ///
+ /// If so, then we can only parse a subset of pseudo-elements, and
+ /// whatever comes after them if so.
+ const AFTER_PART = 1 << 2;
+ /// Whether we've parsed a pseudo-element (as in, an
+ /// `Impl::PseudoElement` thus not accounting for `::slotted` or
+ /// `::part`) already.
+ ///
+ /// If so, then other pseudo-elements and most other selectors are
+ /// disallowed.
+ const AFTER_PSEUDO_ELEMENT = 1 << 3;
+ /// Whether we've parsed a non-stateful pseudo-element (again, as-in
+ /// `Impl::PseudoElement`) already. If so, then other pseudo-classes are
+ /// disallowed. If this flag is set, `AFTER_PSEUDO_ELEMENT` must be set
+ /// as well.
+ const AFTER_NON_STATEFUL_PSEUDO_ELEMENT = 1 << 4;
+ /// Whether we are after any of the pseudo-like things.
+ const AFTER_PSEUDO = Self::AFTER_PART.bits | Self::AFTER_SLOTTED.bits |
Self::AFTER_PSEUDO_ELEMENT.bits;
+ }
+}
+
+impl SelectorParsingState {
+ #[inline]
+ fn allows_functional_pseudo_classes(self) -> bool {
+ !self.intersects(SelectorParsingState::AFTER_PSEUDO)
+ }
+
+ #[inline]
+ fn allows_slotted(self) -> bool {
+ !self.intersects(SelectorParsingState::AFTER_PSEUDO)
+ }
+
+ // TODO(emilio): Should we allow other ::part()s after ::part()?
+ //
+ // See https://github.com/w3c/csswg-drafts/issues/3841
+ #[inline]
+ fn allows_part(self) -> bool {
+ !self.intersects(SelectorParsingState::AFTER_PSEUDO)
+ }
+
+ #[inline]
+ fn allows_non_functional_pseudo_classes(self) -> bool {
+ !self.intersects(
+ SelectorParsingState::AFTER_SLOTTED |
+ SelectorParsingState::AFTER_NON_STATEFUL_PSEUDO_ELEMENT,
+ )
+ }
+
+ #[inline]
+ fn allows_tree_structural_pseudo_classes(self) -> bool {
+ !self.intersects(SelectorParsingState::AFTER_PSEUDO)
+ }
+}
+
+pub type SelectorParseError<'i> = ParseError<'i, SelectorParseErrorKind<'i>>;
+
+#[derive(Clone, Debug, PartialEq)]
+pub enum SelectorParseErrorKind<'i> {
+ PseudoElementInComplexSelector,
+ NoQualifiedNameInAttributeSelector(Token<'i>),
+ EmptySelector,
+ DanglingCombinator,
+ NonSimpleSelectorInNegation,
+ NonCompoundSelector,
+ NonPseudoElementAfterSlotted,
+ InvalidPseudoElementAfterSlotted,
+ InvalidState,
+ UnexpectedTokenInAttributeSelector(Token<'i>),
+ PseudoElementExpectedColon(Token<'i>),
+ PseudoElementExpectedIdent(Token<'i>),
+ NoIdentForPseudo(Token<'i>),
+ UnsupportedPseudoClassOrElement(CowRcStr<'i>),
+ UnexpectedIdent(CowRcStr<'i>),
+ ExpectedNamespace(CowRcStr<'i>),
+ ExpectedBarInAttr(Token<'i>),
+ BadValueInAttr(Token<'i>),
+ InvalidQualNameInAttr(Token<'i>),
+ ExplicitNamespaceUnexpectedToken(Token<'i>),
+ ClassNeedsIdent(Token<'i>),
+ EmptyNegation,
+}
+
+macro_rules! with_all_bounds {
+ (
+ [ $( $InSelector: tt )* ]
+ [ $( $CommonBounds: tt )* ]
+ [ $( $FromStr: tt )* ]
+ ) => {
+ /// This trait allows to define the parser implementation in regards
+ /// of pseudo-classes/elements
+ ///
+ /// NB: We need Clone so that we can derive(Clone) on struct with that
+ /// are parameterized on SelectorImpl. See
+ /// <https://github.com/rust-lang/rust/issues/26925>
+ pub trait SelectorImpl: Clone + Debug + Sized + 'static {
+ type ExtraMatchingData: Sized + Default + 'static;
+ type AttrValue: $($InSelector)*;
+ type Identifier: $($InSelector)*;
+ type ClassName: $($InSelector)*;
+ type PartName: $($InSelector)*;
+ type LocalName: $($InSelector)* + Borrow<Self::BorrowedLocalName>;
+ type NamespaceUrl: $($CommonBounds)* + Default + Borrow<Self::BorrowedNamespaceUrl>;
+ type NamespacePrefix: $($InSelector)* + Default;
+ type BorrowedNamespaceUrl: ?Sized + Eq;
+ type BorrowedLocalName: ?Sized + Eq;
+
+ /// non tree-structural pseudo-classes
+ /// (see: https://drafts.csswg.org/selectors/#structural-pseudos)
+ type NonTSPseudoClass: $($CommonBounds)* + NonTSPseudoClass<Impl = Self>;
+
+ /// pseudo-elements
+ type PseudoElement: $($CommonBounds)* + PseudoElement<Impl = Self>;
+ }
+ }
+}
+
+macro_rules! with_bounds {
+ ( [ $( $CommonBounds: tt )* ] [ $( $FromStr: tt )* ]) => {
+ with_all_bounds! {
+ [$($CommonBounds)* + $($FromStr)* + Display]
+ [$($CommonBounds)*]
+ [$($FromStr)*]
+ }
+ }
+}
+
+with_bounds! {
+ [Clone + Eq]
+ [for<'a> From<&'a str>]
+}
+
+pub trait Parser<'i> {
+ type Impl: SelectorImpl;
+ type Error: 'i + From<SelectorParseErrorKind<'i>>;
+
+ /// Whether to parse the `::slotted()` pseudo-element.
+ fn parse_slotted(&self) -> bool {
+ false
+ }
+
+ /// Whether to parse the `::part()` pseudo-element.
+ fn parse_part(&self) -> bool {
+ false
+ }
+
+ /// Whether to parse the `:host` pseudo-class.
+ fn parse_host(&self) -> bool {
+ false
+ }
+
+ /// This function can return an "Err" pseudo-element in order to support CSS2.1
+ /// pseudo-elements.
+ fn parse_non_ts_pseudo_class(
+ &self,
+ location: SourceLocation,
+ name: CowRcStr<'i>,
+ ) -> Result<<Self::Impl as SelectorImpl>::NonTSPseudoClass, ParseError<'i, Self::Error>> {
+ Err(
+ location.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+ name,
+ )),
+ )
+ }
+
+ fn parse_non_ts_functional_pseudo_class<'t>(
+ &self,
+ name: CowRcStr<'i>,
+ arguments: &mut CssParser<'i, 't>,
+ ) -> Result<<Self::Impl as SelectorImpl>::NonTSPseudoClass, ParseError<'i, Self::Error>> {
+ Err(
+ arguments.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+ name,
+ )),
+ )
+ }
+
+ fn parse_pseudo_element(
+ &self,
+ location: SourceLocation,
+ name: CowRcStr<'i>,
+ ) -> Result<<Self::Impl as SelectorImpl>::PseudoElement, ParseError<'i, Self::Error>> {
+ Err(
+ location.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+ name,
+ )),
+ )
+ }
+
+ fn parse_functional_pseudo_element<'t>(
+ &self,
+ name: CowRcStr<'i>,
+ arguments: &mut CssParser<'i, 't>,
+ ) -> Result<<Self::Impl as SelectorImpl>::PseudoElement, ParseError<'i, Self::Error>> {
+ Err(
+ arguments.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+ name,
+ )),
+ )
+ }
+
+ fn default_namespace(&self) -> Option<<Self::Impl as SelectorImpl>::NamespaceUrl> {
+ None
+ }
+
+ fn namespace_for_prefix(
+ &self,
+ _prefix: &<Self::Impl as SelectorImpl>::NamespacePrefix,
+ ) -> Option<<Self::Impl as SelectorImpl>::NamespaceUrl> {
+ None
+ }
+}
+
+#[derive(Clone, Debug, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub struct SelectorList<Impl: SelectorImpl>(
+ #[shmem(field_bound)] pub SmallVec<[Selector<Impl>; 1]>,
+);
+
+impl<Impl: SelectorImpl> SelectorList<Impl> {
+ /// Parse a comma-separated list of Selectors.
+ /// <https://drafts.csswg.org/selectors/#grouping>
+ ///
+ /// Return the Selectors or Err if there is an invalid selector.
+ pub fn parse<'i, 't, P>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+ ) -> Result<Self, ParseError<'i, P::Error>>
+ where
+ P: Parser<'i, Impl = Impl>,
+ {
+ let mut values = SmallVec::new();
+ loop {
+ values.push(
+ input
+ .parse_until_before(Delimiter::Comma, |input| parse_selector(parser, input))?,
+ );
+ match input.next() {
+ Err(_) => return Ok(SelectorList(values)),
+ Ok(&Token::Comma) => continue,
+ Ok(_) => unreachable!(),
+ }
+ }
+ }
+
+ /// Creates a SelectorList from a Vec of selectors. Used in tests.
+ pub fn from_vec(v: Vec<Selector<Impl>>) -> Self {
+ SelectorList(SmallVec::from_vec(v))
+ }
+}
+
+/// Parses one compound selector suitable for nested stuff like ::-moz-any, etc.
+fn parse_inner_compound_selector<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+) -> Result<Selector<Impl>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ let location = input.current_source_location();
+ let selector = parse_selector(parser, input)?;
+
+ // Ensure they're actually all compound selectors without pseudo-elements.
+ if selector.has_pseudo_element() {
+ return Err(
+ location.new_custom_error(SelectorParseErrorKind::PseudoElementInComplexSelector)
+ );
+ }
+
+ if selector.iter_raw_match_order().any(|s| s.is_combinator()) {
+ return Err(location.new_custom_error(SelectorParseErrorKind::NonCompoundSelector));
+ }
+
+ Ok(selector)
+}
+
+/// Parse a comma separated list of compound selectors.
+pub fn parse_compound_selector_list<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+) -> Result<Box<[Selector<Impl>]>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ input
+ .parse_comma_separated(|input| parse_inner_compound_selector(parser, input))
+ .map(|selectors| selectors.into_boxed_slice())
+}
+
+/// Ancestor hashes for the bloom filter. We precompute these and store them
+/// inline with selectors to optimize cache performance during matching.
+/// This matters a lot.
+///
+/// We use 4 hashes, which is copied from Gecko, who copied it from WebKit.
+/// Note that increasing the number of hashes here will adversely affect the
+/// cache hit when fast-rejecting long lists of Rules with inline hashes.
+///
+/// Because the bloom filter only uses the bottom 24 bits of the hash, we pack
+/// the fourth hash into the upper bits of the first three hashes in order to
+/// shrink Rule (whose size matters a lot). This scheme minimizes the runtime
+/// overhead of the packing for the first three hashes (we just need to mask
+/// off the upper bits) at the expense of making the fourth somewhat more
+/// complicated to assemble, because we often bail out before checking all the
+/// hashes.
+#[derive(Clone, Debug, Eq, PartialEq)]
+pub struct AncestorHashes {
+ pub packed_hashes: [u32; 3],
+}
+
+impl AncestorHashes {
+ pub fn new<Impl: SelectorImpl>(selector: &Selector<Impl>, quirks_mode: QuirksMode) -> Self
+ where
+ Impl::Identifier: PrecomputedHash,
+ Impl::ClassName: PrecomputedHash,
+ Impl::LocalName: PrecomputedHash,
+ Impl::NamespaceUrl: PrecomputedHash,
+ {
+ Self::from_iter(selector.iter(), quirks_mode)
+ }
+
+ fn from_iter<Impl: SelectorImpl>(iter: SelectorIter<Impl>, quirks_mode: QuirksMode) -> Self
+ where
+ Impl::Identifier: PrecomputedHash,
+ Impl::ClassName: PrecomputedHash,
+ Impl::LocalName: PrecomputedHash,
+ Impl::NamespaceUrl: PrecomputedHash,
+ {
+ // Compute ancestor hashes for the bloom filter.
+ let mut hashes = [0u32; 4];
+ let mut hash_iter = AncestorIter::new(iter).filter_map(|x| x.ancestor_hash(quirks_mode));
+ for i in 0..4 {
+ hashes[i] = match hash_iter.next() {
+ Some(x) => x & BLOOM_HASH_MASK,
+ None => break,
+ }
+ }
+
+ // Now, pack the fourth hash (if it exists) into the upper byte of each of
+ // the other three hashes.
+ let fourth = hashes[3];
+ if fourth != 0 {
+ hashes[0] |= (fourth & 0x000000ff) << 24;
+ hashes[1] |= (fourth & 0x0000ff00) << 16;
+ hashes[2] |= (fourth & 0x00ff0000) << 8;
+ }
+
+ AncestorHashes {
+ packed_hashes: [hashes[0], hashes[1], hashes[2]],
+ }
+ }
+
+ /// Returns the fourth hash, reassembled from parts.
+ pub fn fourth_hash(&self) -> u32 {
+ ((self.packed_hashes[0] & 0xff000000) >> 24) |
+ ((self.packed_hashes[1] & 0xff000000) >> 16) |
+ ((self.packed_hashes[2] & 0xff000000) >> 8)
+ }
+}
+
+impl<Impl: SelectorImpl> Visit for Selector<Impl>
+where
+ Impl::NonTSPseudoClass: Visit<Impl = Impl>,
+{
+ type Impl = Impl;
+
+ fn visit<V>(&self, visitor: &mut V) -> bool
+ where
+ V: SelectorVisitor<Impl = Impl>,
+ {
+ let mut current = self.iter();
+ let mut combinator = None;
+ loop {
+ if !visitor.visit_complex_selector(combinator) {
+ return false;
+ }
+
+ for selector in &mut current {
+ if !selector.visit(visitor) {
+ return false;
+ }
+ }
+
+ combinator = current.next_sequence();
+ if combinator.is_none() {
+ break;
+ }
+ }
+
+ true
+ }
+}
+
+impl<Impl: SelectorImpl> Visit for Component<Impl>
+where
+ Impl::NonTSPseudoClass: Visit<Impl = Impl>,
+{
+ type Impl = Impl;
+
+ fn visit<V>(&self, visitor: &mut V) -> bool
+ where
+ V: SelectorVisitor<Impl = Impl>,
+ {
+ use self::Component::*;
+ if !visitor.visit_simple_selector(self) {
+ return false;
+ }
+
+ match *self {
+ Slotted(ref selector) => {
+ if !selector.visit(visitor) {
+ return false;
+ }
+ },
+ Host(Some(ref selector)) => {
+ if !selector.visit(visitor) {
+ return false;
+ }
+ },
+ Negation(ref negated) => {
+ for component in negated.iter() {
+ if !component.visit(visitor) {
+ return false;
+ }
+ }
+ },
+
+ AttributeInNoNamespaceExists {
+ ref local_name,
+ ref local_name_lower,
+ } => {
+ if !visitor.visit_attribute_selector(
+ &NamespaceConstraint::Specific(&namespace_empty_string::<Impl>()),
+ local_name,
+ local_name_lower,
+ ) {
+ return false;
+ }
+ },
+ AttributeInNoNamespace {
+ ref local_name,
+ never_matches,
+ ..
+ } if !never_matches => {
+ if !visitor.visit_attribute_selector(
+ &NamespaceConstraint::Specific(&namespace_empty_string::<Impl>()),
+ local_name,
+ local_name,
+ ) {
+ return false;
+ }
+ },
+ AttributeOther(ref attr_selector) if !attr_selector.never_matches => {
+ let empty_string;
+ let namespace = match attr_selector.namespace() {
+ Some(ns) => ns,
+ None => {
+ empty_string = crate::parser::namespace_empty_string::<Impl>();
+ NamespaceConstraint::Specific(&empty_string)
+ },
+ };
+ if !visitor.visit_attribute_selector(
+ &namespace,
+ &attr_selector.local_name,
+ &attr_selector.local_name_lower,
+ ) {
+ return false;
+ }
+ },
+
+ NonTSPseudoClass(ref pseudo_class) => {
+ if !pseudo_class.visit(visitor) {
+ return false;
+ }
+ },
+ _ => {},
+ }
+
+ true
+ }
+}
+
+pub fn namespace_empty_string<Impl: SelectorImpl>() -> Impl::NamespaceUrl {
+ // Rust type’s default, not default namespace
+ Impl::NamespaceUrl::default()
+}
+
+/// A Selector stores a sequence of simple selectors and combinators. The
+/// iterator classes allow callers to iterate at either the raw sequence level or
+/// at the level of sequences of simple selectors separated by combinators. Most
+/// callers want the higher-level iterator.
+///
+/// We store compound selectors internally right-to-left (in matching order).
+/// Additionally, we invert the order of top-level compound selectors so that
+/// each one matches left-to-right. This is because matching namespace, local name,
+/// id, and class are all relatively cheap, whereas matching pseudo-classes might
+/// be expensive (depending on the pseudo-class). Since authors tend to put the
+/// pseudo-classes on the right, it's faster to start matching on the left.
+///
+/// This reordering doesn't change the semantics of selector matching, and we
+/// handle it in to_css to make it invisible to serialization.
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub struct Selector<Impl: SelectorImpl>(
+ #[shmem(field_bound)] ThinArc<SpecificityAndFlags, Component<Impl>>,
+);
+
+impl<Impl: SelectorImpl> Selector<Impl> {
+ #[inline]
+ pub fn specificity(&self) -> u32 {
+ self.0.header.header.specificity()
+ }
+
+ #[inline]
+ pub fn has_pseudo_element(&self) -> bool {
+ self.0.header.header.has_pseudo_element()
+ }
+
+ #[inline]
+ pub fn is_slotted(&self) -> bool {
+ self.0.header.header.is_slotted()
+ }
+
+ #[inline]
+ pub fn is_part(&self) -> bool {
+ self.0.header.header.is_part()
+ }
+
+ #[inline]
+ pub fn parts(&self) -> Option<&[Impl::PartName]> {
+ if !self.is_part() {
+ return None;
+ }
+
+ let mut iter = self.iter();
+ if self.has_pseudo_element() {
+ // Skip the pseudo-element.
+ for _ in &mut iter {}
+
+ let combinator = iter.next_sequence()?;
+ debug_assert_eq!(combinator, Combinator::PseudoElement);
+ }
+
+ for component in iter {
+ if let Component::Part(ref part) = *component {
+ return Some(part);
+ }
+ }
+
+ debug_assert!(false, "is_part() lied somehow?");
+ None
+ }
+
+ #[inline]
+ pub fn pseudo_element(&self) -> Option<&Impl::PseudoElement> {
+ if !self.has_pseudo_element() {
+ return None;
+ }
+
+ for component in self.iter() {
+ if let Component::PseudoElement(ref pseudo) = *component {
+ return Some(pseudo);
+ }
+ }
+
+ debug_assert!(false, "has_pseudo_element lied!");
+ None
+ }
+
+ /// Whether this selector (pseudo-element part excluded) matches every element.
+ ///
+ /// Used for "pre-computed" pseudo-elements in components/style/stylist.rs
+ #[inline]
+ pub fn is_universal(&self) -> bool {
+ self.iter_raw_match_order().all(|c| {
+ matches!(
+ *c,
+ Component::ExplicitUniversalType |
+ Component::ExplicitAnyNamespace |
+ Component::Combinator(Combinator::PseudoElement) |
+ Component::PseudoElement(..)
+ )
+ })
+ }
+
+ /// Returns an iterator over this selector in matching order (right-to-left).
+ /// When a combinator is reached, the iterator will return None, and
+ /// next_sequence() may be called to continue to the next sequence.
+ #[inline]
+ pub fn iter(&self) -> SelectorIter<Impl> {
+ SelectorIter {
+ iter: self.iter_raw_match_order(),
+ next_combinator: None,
+ }
+ }
+
+ /// Whether this selector is a featureless :host selector, with no
+ /// combinators to the left, and optionally has a pseudo-element to the
+ /// right.
+ #[inline]
+ pub fn is_featureless_host_selector_or_pseudo_element(&self) -> bool {
+ let mut iter = self.iter();
+ if !self.has_pseudo_element() {
+ return iter.is_featureless_host_selector();
+ }
+
+ // Skip the pseudo-element.
+ for _ in &mut iter {}
+
+ match iter.next_sequence() {
+ None => return false,
+ Some(combinator) => {
+ debug_assert_eq!(combinator, Combinator::PseudoElement);
+ },
+ }
+
+ iter.is_featureless_host_selector()
+ }
+
+ /// Returns an iterator over this selector in matching order (right-to-left),
+ /// skipping the rightmost |offset| Components.
+ #[inline]
+ pub fn iter_from(&self, offset: usize) -> SelectorIter<Impl> {
+ let iter = self.0.slice[offset..].iter();
+ SelectorIter {
+ iter: iter,
+ next_combinator: None,
+ }
+ }
+
+ /// Returns the combinator at index `index` (zero-indexed from the right),
+ /// or panics if the component is not a combinator.
+ #[inline]
+ pub fn combinator_at_match_order(&self, index: usize) -> Combinator {
+ match self.0.slice[index] {
+ Component::Combinator(c) => c,
+ ref other => panic!(
+ "Not a combinator: {:?}, {:?}, index: {}",
+ other, self, index
+ ),
+ }
+ }
+
+ /// Returns an iterator over the entire sequence of simple selectors and
+ /// combinators, in matching order (from right to left).
+ #[inline]
+ pub fn iter_raw_match_order(&self) -> slice::Iter<Component<Impl>> {
+ self.0.slice.iter()
+ }
+
+ /// Returns the combinator at index `index` (zero-indexed from the left),
+ /// or panics if the component is not a combinator.
+ #[inline]
+ pub fn combinator_at_parse_order(&self, index: usize) -> Combinator {
+ match self.0.slice[self.len() - index - 1] {
+ Component::Combinator(c) => c,
+ ref other => panic!(
+ "Not a combinator: {:?}, {:?}, index: {}",
+ other, self, index
+ ),
+ }
+ }
+
+ /// Returns an iterator over the sequence of simple selectors and
+ /// combinators, in parse order (from left to right), starting from
+ /// `offset`.
+ #[inline]
+ pub fn iter_raw_parse_order_from(&self, offset: usize) -> Rev<slice::Iter<Component<Impl>>> {
+ self.0.slice[..self.len() - offset].iter().rev()
+ }
+
+ /// Creates a Selector from a vec of Components, specified in parse order. Used in tests.
+ #[allow(unused)]
+ pub(crate) fn from_vec(
+ vec: Vec<Component<Impl>>,
+ specificity: u32,
+ flags: SelectorFlags,
+ ) -> Self {
+ let mut builder = SelectorBuilder::default();
+ for component in vec.into_iter() {
+ if let Some(combinator) = component.as_combinator() {
+ builder.push_combinator(combinator);
+ } else {
+ builder.push_simple_selector(component);
+ }
+ }
+ let spec = SpecificityAndFlags { specificity, flags };
+ Selector(builder.build_with_specificity_and_flags(spec))
+ }
+
+ /// Returns count of simple selectors and combinators in the Selector.
+ #[inline]
+ pub fn len(&self) -> usize {
+ self.0.slice.len()
+ }
+
+ /// Returns the address on the heap of the ThinArc for memory reporting.
+ pub fn thin_arc_heap_ptr(&self) -> *const ::std::os::raw::c_void {
+ self.0.heap_ptr()
+ }
+}
+
+#[derive(Clone)]
+pub struct SelectorIter<'a, Impl: 'a + SelectorImpl> {
+ iter: slice::Iter<'a, Component<Impl>>,
+ next_combinator: Option<Combinator>,
+}
+
+impl<'a, Impl: 'a + SelectorImpl> SelectorIter<'a, Impl> {
+ /// Prepares this iterator to point to the next sequence to the left,
+ /// returning the combinator if the sequence was found.
+ #[inline]
+ pub fn next_sequence(&mut self) -> Option<Combinator> {
+ self.next_combinator.take()
+ }
+
+ /// Whether this selector is a featureless host selector, with no
+ /// combinators to the left.
+ #[inline]
+ pub(crate) fn is_featureless_host_selector(&mut self) -> bool {
+ self.selector_length() > 0 &&
+ self.all(|component| matches!(*component, Component::Host(..))) &&
+ self.next_sequence().is_none()
+ }
+
+ /// Returns remaining count of the simple selectors and combinators in the Selector.
+ #[inline]
+ pub fn selector_length(&self) -> usize {
+ self.iter.len()
+ }
+}
+
+impl<'a, Impl: SelectorImpl> Iterator for SelectorIter<'a, Impl> {
+ type Item = &'a Component<Impl>;
+
+ #[inline]
+ fn next(&mut self) -> Option<Self::Item> {
+ debug_assert!(
+ self.next_combinator.is_none(),
+ "You should call next_sequence!"
+ );
+ match *self.iter.next()? {
+ Component::Combinator(c) => {
+ self.next_combinator = Some(c);
+ None
+ },
+ ref x => Some(x),
+ }
+ }
+}
+
+impl<'a, Impl: SelectorImpl> fmt::Debug for SelectorIter<'a, Impl> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ let iter = self.iter.clone().rev();
+ for component in iter {
+ component.to_css(f)?
+ }
+ Ok(())
+ }
+}
+
+/// An iterator over all simple selectors belonging to ancestors.
+struct AncestorIter<'a, Impl: 'a + SelectorImpl>(SelectorIter<'a, Impl>);
+impl<'a, Impl: 'a + SelectorImpl> AncestorIter<'a, Impl> {
+ /// Creates an AncestorIter. The passed-in iterator is assumed to point to
+ /// the beginning of the child sequence, which will be skipped.
+ fn new(inner: SelectorIter<'a, Impl>) -> Self {
+ let mut result = AncestorIter(inner);
+ result.skip_until_ancestor();
+ result
+ }
+
+ /// Skips a sequence of simple selectors and all subsequent sequences until
+ /// a non-pseudo-element ancestor combinator is reached.
+ fn skip_until_ancestor(&mut self) {
+ loop {
+ while self.0.next().is_some() {}
+ // If this is ever changed to stop at the "pseudo-element"
+ // combinator, we will need to fix the way we compute hashes for
+ // revalidation selectors.
+ if self.0.next_sequence().map_or(true, |x| {
+ matches!(x, Combinator::Child | Combinator::Descendant)
+ }) {
+ break;
+ }
+ }
+ }
+}
+
+impl<'a, Impl: SelectorImpl> Iterator for AncestorIter<'a, Impl> {
+ type Item = &'a Component<Impl>;
+ fn next(&mut self) -> Option<Self::Item> {
+ // Grab the next simple selector in the sequence if available.
+ let next = self.0.next();
+ if next.is_some() {
+ return next;
+ }
+
+ // See if there are more sequences. If so, skip any non-ancestor sequences.
+ if let Some(combinator) = self.0.next_sequence() {
+ if !matches!(combinator, Combinator::Child | Combinator::Descendant) {
+ self.skip_until_ancestor();
+ }
+ }
+
+ self.0.next()
+ }
+}
+
+#[derive(Clone, Copy, Debug, Eq, PartialEq, ToShmem)]
+pub enum Combinator {
+ Child, // >
+ Descendant, // space
+ NextSibling, // +
+ LaterSibling, // ~
+ /// A dummy combinator we use to the left of pseudo-elements.
+ ///
+ /// It serializes as the empty string, and acts effectively as a child
+ /// combinator in most cases. If we ever actually start using a child
+ /// combinator for this, we will need to fix up the way hashes are computed
+ /// for revalidation selectors.
+ PseudoElement,
+ /// Another combinator used for ::slotted(), which represent the jump from
+ /// a node to its assigned slot.
+ SlotAssignment,
+ /// Another combinator used for `::part()`, which represents the jump from
+ /// the part to the containing shadow host.
+ Part,
+}
+
+impl Combinator {
+ /// Returns true if this combinator is a child or descendant combinator.
+ #[inline]
+ pub fn is_ancestor(&self) -> bool {
+ matches!(
+ *self,
+ Combinator::Child |
+ Combinator::Descendant |
+ Combinator::PseudoElement |
+ Combinator::SlotAssignment
+ )
+ }
+
+ /// Returns true if this combinator is a pseudo-element combinator.
+ #[inline]
+ pub fn is_pseudo_element(&self) -> bool {
+ matches!(*self, Combinator::PseudoElement)
+ }
+
+ /// Returns true if this combinator is a next- or later-sibling combinator.
+ #[inline]
+ pub fn is_sibling(&self) -> bool {
+ matches!(*self, Combinator::NextSibling | Combinator::LaterSibling)
+ }
+}
+
+/// A CSS simple selector or combinator. We store both in the same enum for
+/// optimal packing and cache performance, see [1].
+///
+/// [1] https://bugzilla.mozilla.org/show_bug.cgi?id=1357973
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub enum Component<Impl: SelectorImpl> {
+ Combinator(Combinator),
+
+ ExplicitAnyNamespace,
+ ExplicitNoNamespace,
+ DefaultNamespace(#[shmem(field_bound)] Impl::NamespaceUrl),
+ Namespace(
+ #[shmem(field_bound)] Impl::NamespacePrefix,
+ #[shmem(field_bound)] Impl::NamespaceUrl,
+ ),
+
+ ExplicitUniversalType,
+ LocalName(LocalName<Impl>),
+
+ ID(#[shmem(field_bound)] Impl::Identifier),
+ Class(#[shmem(field_bound)] Impl::ClassName),
+
+ AttributeInNoNamespaceExists {
+ #[shmem(field_bound)]
+ local_name: Impl::LocalName,
+ local_name_lower: Impl::LocalName,
+ },
+ // Used only when local_name is already lowercase.
+ AttributeInNoNamespace {
+ local_name: Impl::LocalName,
+ operator: AttrSelectorOperator,
+ #[shmem(field_bound)]
+ value: Impl::AttrValue,
+ case_sensitivity: ParsedCaseSensitivity,
+ never_matches: bool,
+ },
+ // Use a Box in the less common cases with more data to keep size_of::<Component>() small.
+ AttributeOther(Box<AttrSelectorWithOptionalNamespace<Impl>>),
+
+ /// Pseudo-classes
+ ///
+ /// CSS3 Negation only takes a simple simple selector, but we still need to
+ /// treat it as a compound selector because it might be a type selector
+ /// which we represent as a namespace and a localname.
+ ///
+ /// Note: if/when we upgrade this to CSS4, which supports combinators, we
+ /// need to think about how this should interact with
+ /// visit_complex_selector, and what the consumers of those APIs should do
+ /// about the presence of combinators in negation.
+ Negation(ThinBoxedSlice<Component<Impl>>),
+ FirstChild,
+ LastChild,
+ OnlyChild,
+ Root,
+ Empty,
+ Scope,
+ NthChild(i32, i32),
+ NthLastChild(i32, i32),
+ NthOfType(i32, i32),
+ NthLastOfType(i32, i32),
+ FirstOfType,
+ LastOfType,
+ OnlyOfType,
+ NonTSPseudoClass(#[shmem(field_bound)] Impl::NonTSPseudoClass),
+ /// The ::slotted() pseudo-element:
+ ///
+ /// https://drafts.csswg.org/css-scoping/#slotted-pseudo
+ ///
+ /// The selector here is a compound selector, that is, no combinators.
+ ///
+ /// NOTE(emilio): This should support a list of selectors, but as of this
+ /// writing no other browser does, and that allows them to put ::slotted()
+ /// in the rule hash, so we do that too.
+ ///
+ /// See https://github.com/w3c/csswg-drafts/issues/2158
+ Slotted(Selector<Impl>),
+ /// The `::part` pseudo-element.
+ /// https://drafts.csswg.org/css-shadow-parts/#part
+ Part(#[shmem(field_bound)] Box<[Impl::PartName]>),
+ /// The `:host` pseudo-class:
+ ///
+ /// https://drafts.csswg.org/css-scoping/#host-selector
+ ///
+ /// NOTE(emilio): This should support a list of selectors, but as of this
+ /// writing no other browser does, and that allows them to put :host()
+ /// in the rule hash, so we do that too.
+ ///
+ /// See https://github.com/w3c/csswg-drafts/issues/2158
+ Host(Option<Selector<Impl>>),
+ PseudoElement(#[shmem(field_bound)] Impl::PseudoElement),
+}
+
+impl<Impl: SelectorImpl> Component<Impl> {
+ /// Compute the ancestor hash to check against the bloom filter.
+ fn ancestor_hash(&self, quirks_mode: QuirksMode) -> Option<u32>
+ where
+ Impl::Identifier: PrecomputedHash,
+ Impl::ClassName: PrecomputedHash,
+ Impl::LocalName: PrecomputedHash,
+ Impl::NamespaceUrl: PrecomputedHash,
+ {
+ match *self {
+ Component::LocalName(LocalName {
+ ref name,
+ ref lower_name,
+ }) => {
+ // Only insert the local-name into the filter if it's all
+ // lowercase. Otherwise we would need to test both hashes, and
+ // our data structures aren't really set up for that.
+ if name == lower_name {
+ Some(name.precomputed_hash())
+ } else {
+ None
+ }
+ },
+ Component::DefaultNamespace(ref url) | Component::Namespace(_, ref url) => {
+ Some(url.precomputed_hash())
+ },
+ // In quirks mode, class and id selectors should match
+ // case-insensitively, so just avoid inserting them into the filter.
+ Component::ID(ref id) if quirks_mode != QuirksMode::Quirks => {
+ Some(id.precomputed_hash())
+ },
+ Component::Class(ref class) if quirks_mode != QuirksMode::Quirks => {
+ Some(class.precomputed_hash())
+ },
+ _ => None,
+ }
+ }
+
+ /// Returns true if this is a combinator.
+ pub fn is_combinator(&self) -> bool {
+ matches!(*self, Component::Combinator(_))
+ }
+
+ /// Returns the value as a combinator if applicable, None otherwise.
+ pub fn as_combinator(&self) -> Option<Combinator> {
+ match *self {
+ Component::Combinator(c) => Some(c),
+ _ => None,
+ }
+ }
+}
+
+#[derive(Clone, Eq, PartialEq, ToShmem)]
+#[shmem(no_bounds)]
+pub struct LocalName<Impl: SelectorImpl> {
+ #[shmem(field_bound)]
+ pub name: Impl::LocalName,
+ pub lower_name: Impl::LocalName,
+}
+
+impl<Impl: SelectorImpl> Debug for Selector<Impl> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ f.write_str("Selector(")?;
+ self.to_css(f)?;
+ write!(f, ", specificity = 0x{:x})", self.specificity())
+ }
+}
+
+impl<Impl: SelectorImpl> Debug for Component<Impl> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ self.to_css(f)
+ }
+}
+impl<Impl: SelectorImpl> Debug for AttrSelectorWithOptionalNamespace<Impl> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ self.to_css(f)
+ }
+}
+impl<Impl: SelectorImpl> Debug for LocalName<Impl> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ self.to_css(f)
+ }
+}
+
+impl<Impl: SelectorImpl> ToCss for SelectorList<Impl> {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ let mut iter = self.0.iter();
+ let first = iter
+ .next()
+ .expect("Empty SelectorList, should contain at least one selector");
+ first.to_css(dest)?;
+ for selector in iter {
+ dest.write_str(", ")?;
+ selector.to_css(dest)?;
+ }
+ Ok(())
+ }
+}
+
+impl<Impl: SelectorImpl> ToCss for Selector<Impl> {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ // Compound selectors invert the order of their contents, so we need to
+ // undo that during serialization.
+ //
+ // This two-iterator strategy involves walking over the selector twice.
+ // We could do something more clever, but selector serialization probably
+ // isn't hot enough to justify it, and the stringification likely
+ // dominates anyway.
+ //
+ // NB: A parse-order iterator is a Rev<>, which doesn't expose as_slice(),
+ // which we need for |split|. So we split by combinators on a match-order
+ // sequence and then reverse.
+
+ let mut combinators = self
+ .iter_raw_match_order()
+ .rev()
+ .filter_map(|x| x.as_combinator());
+ let compound_selectors = self
+ .iter_raw_match_order()
+ .as_slice()
+ .split(|x| x.is_combinator())
+ .rev();
+
+ let mut combinators_exhausted = false;
+ for compound in compound_selectors {
+ debug_assert!(!combinators_exhausted);
+
+ // https://drafts.csswg.org/cssom/#serializing-selectors
+ if compound.is_empty() {
+ continue;
+ }
+
+ // 1. If there is only one simple selector in the compound selectors
+ // which is a universal selector, append the result of
+ // serializing the universal selector to s.
+ //
+ // Check if `!compound.empty()` first--this can happen if we have
+ // something like `... > ::before`, because we store `>` and `::`
+ // both as combinators internally.
+ //
+ // If we are in this case, after we have serialized the universal
+ // selector, we skip Step 2 and continue with the algorithm.
+ let (can_elide_namespace, first_non_namespace) = match compound[0] {
+ Component::ExplicitAnyNamespace |
+ Component::ExplicitNoNamespace |
+ Component::Namespace(..) => (false, 1),
+ Component::DefaultNamespace(..) => (true, 1),
+ _ => (true, 0),
+ };
+ let mut perform_step_2 = true;
+ let next_combinator = combinators.next();
+ if first_non_namespace == compound.len() - 1 {
+ match (next_combinator, &compound[first_non_namespace]) {
+ // We have to be careful here, because if there is a
+ // pseudo element "combinator" there isn't really just
+ // the one simple selector. Technically this compound
+ // selector contains the pseudo element selector as well
+ // -- Combinator::PseudoElement, just like
+ // Combinator::SlotAssignment, don't exist in the
+ // spec.
+ (Some(Combinator::PseudoElement), _) |
+ (Some(Combinator::SlotAssignment), _) => (),
+ (_, &Component::ExplicitUniversalType) => {
+ // Iterate over everything so we serialize the namespace
+ // too.
+ for simple in compound.iter() {
+ simple.to_css(dest)?;
+ }
+ // Skip step 2, which is an "otherwise".
+ perform_step_2 = false;
+ },
+ _ => (),
+ }
+ }
+
+ // 2. Otherwise, for each simple selector in the compound selectors
+ // that is not a universal selector of which the namespace prefix
+ // maps to a namespace that is not the default namespace
+ // serialize the simple selector and append the result to s.
+ //
+ // See https://github.com/w3c/csswg-drafts/issues/1606, which is
+ // proposing to change this to match up with the behavior asserted
+ // in cssom/serialize-namespaced-type-selectors.html, which the
+ // following code tries to match.
+ if perform_step_2 {
+ for simple in compound.iter() {
+ if let Component::ExplicitUniversalType = *simple {
+ // Can't have a namespace followed by a pseudo-element
+ // selector followed by a universal selector in the same
+ // compound selector, so we don't have to worry about the
+ // real namespace being in a different `compound`.
+ if can_elide_namespace {
+ continue;
+ }
+ }
+ simple.to_css(dest)?;
+ }
+ }
+
+ // 3. If this is not the last part of the chain of the selector
+ // append a single SPACE (U+0020), followed by the combinator
+ // ">", "+", "~", ">>", "||", as appropriate, followed by another
+ // single SPACE (U+0020) if the combinator was not whitespace, to
+ // s.
+ match next_combinator {
+ Some(c) => c.to_css(dest)?,
+ None => combinators_exhausted = true,
+ };
+
+ // 4. If this is the last part of the chain of the selector and
+ // there is a pseudo-element, append "::" followed by the name of
+ // the pseudo-element, to s.
+ //
+ // (we handle this above)
+ }
+
+ Ok(())
+ }
+}
+
+impl ToCss for Combinator {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ match *self {
+ Combinator::Child => dest.write_str(" > "),
+ Combinator::Descendant => dest.write_str(" "),
+ Combinator::NextSibling => dest.write_str(" + "),
+ Combinator::LaterSibling => dest.write_str(" ~ "),
+ Combinator::PseudoElement | Combinator::Part | Combinator::SlotAssignment => Ok(()),
+ }
+ }
+}
+
+impl<Impl: SelectorImpl> ToCss for Component<Impl> {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ use self::Component::*;
+
+ /// Serialize <an+b> values (part of the CSS Syntax spec, but currently only used here).
+ /// <https://drafts.csswg.org/css-syntax-3/#serialize-an-anb-value>
+ fn write_affine<W>(dest: &mut W, a: i32, b: i32) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ match (a, b) {
+ (0, 0) => dest.write_char('0'),
+
+ (1, 0) => dest.write_char('n'),
+ (-1, 0) => dest.write_str("-n"),
+ (_, 0) => write!(dest, "{}n", a),
+
+ (0, _) => write!(dest, "{}", b),
+ (1, _) => write!(dest, "n{:+}", b),
+ (-1, _) => write!(dest, "-n{:+}", b),
+ (_, _) => write!(dest, "{}n{:+}", a, b),
+ }
+ }
+
+ match *self {
+ Combinator(ref c) => c.to_css(dest),
+ Slotted(ref selector) => {
+ dest.write_str("::slotted(")?;
+ selector.to_css(dest)?;
+ dest.write_char(')')
+ },
+ Part(ref part_names) => {
+ dest.write_str("::part(")?;
+ for (i, name) in part_names.iter().enumerate() {
+ if i != 0 {
+ dest.write_char(' ')?;
+ }
+ display_to_css_identifier(name, dest)?;
+ }
+ dest.write_char(')')
+ },
+ PseudoElement(ref p) => p.to_css(dest),
+ ID(ref s) => {
+ dest.write_char('#')?;
+ display_to_css_identifier(s, dest)
+ },
+ Class(ref s) => {
+ dest.write_char('.')?;
+ display_to_css_identifier(s, dest)
+ },
+ LocalName(ref s) => s.to_css(dest),
+ ExplicitUniversalType => dest.write_char('*'),
+
+ DefaultNamespace(_) => Ok(()),
+ ExplicitNoNamespace => dest.write_char('|'),
+ ExplicitAnyNamespace => dest.write_str("*|"),
+ Namespace(ref prefix, _) => {
+ display_to_css_identifier(prefix, dest)?;
+ dest.write_char('|')
+ },
+
+ AttributeInNoNamespaceExists { ref local_name, .. } => {
+ dest.write_char('[')?;
+ display_to_css_identifier(local_name, dest)?;
+ dest.write_char(']')
+ },
+ AttributeInNoNamespace {
+ ref local_name,
+ operator,
+ ref value,
+ case_sensitivity,
+ ..
+ } => {
+ dest.write_char('[')?;
+ display_to_css_identifier(local_name, dest)?;
+ operator.to_css(dest)?;
+ dest.write_char('"')?;
+ write!(CssStringWriter::new(dest), "{}", value)?;
+ dest.write_char('"')?;
+ match case_sensitivity {
+ ParsedCaseSensitivity::CaseSensitive |
+ ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {},
+ ParsedCaseSensitivity::AsciiCaseInsensitive => dest.write_str(" i")?,
+ ParsedCaseSensitivity::ExplicitCaseSensitive => dest.write_str(" s")?,
+ }
+ dest.write_char(']')
+ },
+ AttributeOther(ref attr_selector) => attr_selector.to_css(dest),
+
+ // Pseudo-classes
+ Negation(ref arg) => {
+ dest.write_str(":not(")?;
+ for component in arg.iter() {
+ component.to_css(dest)?;
+ }
+ dest.write_str(")")
+ },
+
+ FirstChild => dest.write_str(":first-child"),
+ LastChild => dest.write_str(":last-child"),
+ OnlyChild => dest.write_str(":only-child"),
+ Root => dest.write_str(":root"),
+ Empty => dest.write_str(":empty"),
+ Scope => dest.write_str(":scope"),
+ Host(ref selector) => {
+ dest.write_str(":host")?;
+ if let Some(ref selector) = *selector {
+ dest.write_char('(')?;
+ selector.to_css(dest)?;
+ dest.write_char(')')?;
+ }
+ Ok(())
+ },
+ FirstOfType => dest.write_str(":first-of-type"),
+ LastOfType => dest.write_str(":last-of-type"),
+ OnlyOfType => dest.write_str(":only-of-type"),
+ NthChild(a, b) | NthLastChild(a, b) | NthOfType(a, b) | NthLastOfType(a, b) => {
+ match *self {
+ NthChild(_, _) => dest.write_str(":nth-child(")?,
+ NthLastChild(_, _) => dest.write_str(":nth-last-child(")?,
+ NthOfType(_, _) => dest.write_str(":nth-of-type(")?,
+ NthLastOfType(_, _) => dest.write_str(":nth-last-of-type(")?,
+ _ => unreachable!(),
+ }
+ write_affine(dest, a, b)?;
+ dest.write_char(')')
+ },
+ NonTSPseudoClass(ref pseudo) => pseudo.to_css(dest),
+ }
+ }
+}
+
+impl<Impl: SelectorImpl> ToCss for AttrSelectorWithOptionalNamespace<Impl> {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ dest.write_char('[')?;
+ match self.namespace {
+ Some(NamespaceConstraint::Specific((ref prefix, _))) => {
+ display_to_css_identifier(prefix, dest)?;
+ dest.write_char('|')?
+ },
+ Some(NamespaceConstraint::Any) => dest.write_str("*|")?,
+ None => {},
+ }
+ display_to_css_identifier(&self.local_name, dest)?;
+ match self.operation {
+ ParsedAttrSelectorOperation::Exists => {},
+ ParsedAttrSelectorOperation::WithValue {
+ operator,
+ case_sensitivity,
+ ref expected_value,
+ } => {
+ operator.to_css(dest)?;
+ dest.write_char('"')?;
+ write!(CssStringWriter::new(dest), "{}", expected_value)?;
+ dest.write_char('"')?;
+ match case_sensitivity {
+ ParsedCaseSensitivity::CaseSensitive |
+ ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument => {},
+ ParsedCaseSensitivity::AsciiCaseInsensitive => dest.write_str(" i")?,
+ ParsedCaseSensitivity::ExplicitCaseSensitive => dest.write_str(" s")?,
+ }
+ },
+ }
+ dest.write_char(']')
+ }
+}
+
+impl<Impl: SelectorImpl> ToCss for LocalName<Impl> {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ display_to_css_identifier(&self.name, dest)
+ }
+}
+
+/// Serialize the output of Display as a CSS identifier
+fn display_to_css_identifier<T: Display, W: fmt::Write>(x: &T, dest: &mut W) -> fmt::Result {
+ // FIXME(SimonSapin): it is possible to avoid this heap allocation
+ // by creating a stream adapter like cssparser::CssStringWriter
+ // that holds and writes to `&mut W` and itself implements `fmt::Write`.
+ //
+ // I haven’t done this yet because it would require somewhat complex and fragile state machine
+ // to support in `fmt::Write::write_char` cases that,
+ // in `serialize_identifier` (which has the full value as a `&str` slice),
+ // can be expressed as
+ // `string.starts_with("--")`, `string == "-"`, `string.starts_with("-")`, etc.
+ //
+ // And I don’t even know if this would be a performance win: jemalloc is good at what it does
+ // and the state machine might be slower than `serialize_identifier` as currently written.
+ let string = x.to_string();
+
+ serialize_identifier(&string, dest)
+}
+
+/// Build up a Selector.
+/// selector : simple_selector_sequence [ combinator simple_selector_sequence ]* ;
+///
+/// `Err` means invalid selector.
+fn parse_selector<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+) -> Result<Selector<Impl>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ let mut builder = SelectorBuilder::default();
+
+ let mut has_pseudo_element = false;
+ let mut slotted = false;
+ let mut part = false;
+ 'outer_loop: loop {
+ // Parse a sequence of simple selectors.
+ let state = match parse_compound_selector(parser, input, &mut builder)? {
+ Some(state) => state,
+ None => {
+ return Err(input.new_custom_error(if builder.has_combinators() {
+ SelectorParseErrorKind::DanglingCombinator
+ } else {
+ SelectorParseErrorKind::EmptySelector
+ }));
+ },
+ };
+
+ if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+ has_pseudo_element = state.intersects(SelectorParsingState::AFTER_PSEUDO_ELEMENT);
+ slotted = state.intersects(SelectorParsingState::AFTER_SLOTTED);
+ part = state.intersects(SelectorParsingState::AFTER_PART);
+ debug_assert!(has_pseudo_element || slotted || part);
+ break;
+ }
+
+ // Parse a combinator.
+ let combinator;
+ let mut any_whitespace = false;
+ loop {
+ let before_this_token = input.state();
+ match input.next_including_whitespace() {
+ Err(_e) => break 'outer_loop,
+ Ok(&Token::WhiteSpace(_)) => any_whitespace = true,
+ Ok(&Token::Delim('>')) => {
+ combinator = Combinator::Child;
+ break;
+ },
+ Ok(&Token::Delim('+')) => {
+ combinator = Combinator::NextSibling;
+ break;
+ },
+ Ok(&Token::Delim('~')) => {
+ combinator = Combinator::LaterSibling;
+ break;
+ },
+ Ok(_) => {
+ input.reset(&before_this_token);
+ if any_whitespace {
+ combinator = Combinator::Descendant;
+ break;
+ } else {
+ break 'outer_loop;
+ }
+ },
+ }
+ }
+ builder.push_combinator(combinator);
+ }
+
+ Ok(Selector(builder.build(has_pseudo_element, slotted, part)))
+}
+
+impl<Impl: SelectorImpl> Selector<Impl> {
+ /// Parse a selector, without any pseudo-element.
+ #[inline]
+ pub fn parse<'i, 't, P>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+ ) -> Result<Self, ParseError<'i, P::Error>>
+ where
+ P: Parser<'i, Impl = Impl>,
+ {
+ parse_selector(parser, input)
+ }
+}
+
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(false)`: Not a type selector, could be something else. `input` was not consumed.
+/// * `Ok(true)`: Length 0 (`*|*`), 1 (`*|E` or `ns|*`) or 2 (`|E` or `ns|E`)
+fn parse_type_selector<'i, 't, P, Impl, S>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+ sink: &mut S,
+) -> Result<bool, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+ S: Push<Component<Impl>>,
+{
+ match parse_qualified_name(parser, input, /* in_attr_selector = */ false) {
+ Err(ParseError {
+ kind: ParseErrorKind::Basic(BasicParseErrorKind::EndOfInput),
+ ..
+ }) |
+ Ok(OptionalQName::None(_)) => Ok(false),
+ Ok(OptionalQName::Some(namespace, local_name)) => {
+ match namespace {
+ QNamePrefix::ImplicitAnyNamespace => {},
+ QNamePrefix::ImplicitDefaultNamespace(url) => {
+ sink.push(Component::DefaultNamespace(url))
+ },
+ QNamePrefix::ExplicitNamespace(prefix, url) => {
+ sink.push(match parser.default_namespace() {
+ Some(ref default_url) if url == *default_url => {
+ Component::DefaultNamespace(url)
+ },
+ _ => Component::Namespace(prefix, url),
+ })
+ },
+ QNamePrefix::ExplicitNoNamespace => sink.push(Component::ExplicitNoNamespace),
+ QNamePrefix::ExplicitAnyNamespace => {
+ match parser.default_namespace() {
+ // Element type selectors that have no namespace
+ // component (no namespace separator) represent elements
+ // without regard to the element's namespace (equivalent
+ // to "*|") unless a default namespace has been declared
+ // for namespaced selectors (e.g. in CSS, in the style
+ // sheet). If a default namespace has been declared,
+ // such selectors will represent only elements in the
+ // default namespace.
+ // -- Selectors § 6.1.1
+ // So we'll have this act the same as the
+ // QNamePrefix::ImplicitAnyNamespace case.
+ None => {},
+ Some(_) => sink.push(Component::ExplicitAnyNamespace),
+ }
+ },
+ QNamePrefix::ImplicitNoNamespace => {
+ unreachable!() // Not returned with in_attr_selector = false
+ },
+ }
+ match local_name {
+ Some(name) => sink.push(Component::LocalName(LocalName {
+ lower_name: to_ascii_lowercase(&name).as_ref().into(),
+ name: name.as_ref().into(),
+ })),
+ None => sink.push(Component::ExplicitUniversalType),
+ }
+ Ok(true)
+ },
+ Err(e) => Err(e),
+ }
+}
+
+#[derive(Debug)]
+enum SimpleSelectorParseResult<Impl: SelectorImpl> {
+ SimpleSelector(Component<Impl>),
+ PseudoElement(Impl::PseudoElement),
+ SlottedPseudo(Selector<Impl>),
+ PartPseudo(Box<[Impl::PartName]>),
+}
+
+#[derive(Debug)]
+enum QNamePrefix<Impl: SelectorImpl> {
+ ImplicitNoNamespace, // `foo` in attr selectors
+ ImplicitAnyNamespace, // `foo` in type selectors, without a default ns
+ ImplicitDefaultNamespace(Impl::NamespaceUrl), // `foo` in type selectors, with a default ns
+ ExplicitNoNamespace, // `|foo`
+ ExplicitAnyNamespace, // `*|foo`
+ ExplicitNamespace(Impl::NamespacePrefix, Impl::NamespaceUrl), // `prefix|foo`
+}
+
+enum OptionalQName<'i, Impl: SelectorImpl> {
+ Some(QNamePrefix<Impl>, Option<CowRcStr<'i>>),
+ None(Token<'i>),
+}
+
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(None(token))`: Not a simple selector, could be something else. `input` was not consumed,
+/// but the token is still returned.
+/// * `Ok(Some(namespace, local_name))`: `None` for the local name means a `*` universal selector
+fn parse_qualified_name<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+ in_attr_selector: bool,
+) -> Result<OptionalQName<'i, Impl>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ let default_namespace = |local_name| {
+ let namespace = match parser.default_namespace() {
+ Some(url) => QNamePrefix::ImplicitDefaultNamespace(url),
+ None => QNamePrefix::ImplicitAnyNamespace,
+ };
+ Ok(OptionalQName::Some(namespace, local_name))
+ };
+
+ let explicit_namespace = |input: &mut CssParser<'i, 't>, namespace| {
+ let location = input.current_source_location();
+ match input.next_including_whitespace() {
+ Ok(&Token::Delim('*')) if !in_attr_selector => Ok(OptionalQName::Some(namespace, None)),
+ Ok(&Token::Ident(ref local_name)) => {
+ Ok(OptionalQName::Some(namespace, Some(local_name.clone())))
+ },
+ Ok(t) if in_attr_selector => {
+ let e = SelectorParseErrorKind::InvalidQualNameInAttr(t.clone());
+ Err(location.new_custom_error(e))
+ },
+ Ok(t) => Err(location.new_custom_error(
+ SelectorParseErrorKind::ExplicitNamespaceUnexpectedToken(t.clone()),
+ )),
+ Err(e) => Err(e.into()),
+ }
+ };
+
+ let start = input.state();
+ // FIXME: remove clone() when lifetimes are non-lexical
+ match input.next_including_whitespace().map(|t| t.clone()) {
+ Ok(Token::Ident(value)) => {
+ let after_ident = input.state();
+ match input.next_including_whitespace() {
+ Ok(&Token::Delim('|')) => {
+ let prefix = value.as_ref().into();
+ let result = parser.namespace_for_prefix(&prefix);
+ let url = result.ok_or(
+ after_ident
+ .source_location()
+ .new_custom_error(SelectorParseErrorKind::ExpectedNamespace(value)),
+ )?;
+ explicit_namespace(input, QNamePrefix::ExplicitNamespace(prefix, url))
+ },
+ _ => {
+ input.reset(&after_ident);
+ if in_attr_selector {
+ Ok(OptionalQName::Some(
+ QNamePrefix::ImplicitNoNamespace,
+ Some(value),
+ ))
+ } else {
+ default_namespace(Some(value))
+ }
+ },
+ }
+ },
+ Ok(Token::Delim('*')) => {
+ let after_star = input.state();
+ // FIXME: remove clone() when lifetimes are non-lexical
+ match input.next_including_whitespace().map(|t| t.clone()) {
+ Ok(Token::Delim('|')) => {
+ explicit_namespace(input, QNamePrefix::ExplicitAnyNamespace)
+ },
+ result => {
+ input.reset(&after_star);
+ if in_attr_selector {
+ match result {
+ Ok(t) => Err(after_star
+ .source_location()
+ .new_custom_error(SelectorParseErrorKind::ExpectedBarInAttr(t))),
+ Err(e) => Err(e.into()),
+ }
+ } else {
+ default_namespace(None)
+ }
+ },
+ }
+ },
+ Ok(Token::Delim('|')) => explicit_namespace(input, QNamePrefix::ExplicitNoNamespace),
+ Ok(t) => {
+ input.reset(&start);
+ Ok(OptionalQName::None(t))
+ },
+ Err(e) => {
+ input.reset(&start);
+ Err(e.into())
+ },
+ }
+}
+
+fn parse_attribute_selector<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ let namespace;
+ let local_name;
+
+ input.skip_whitespace();
+
+ match parse_qualified_name(parser, input, /* in_attr_selector = */ true)? {
+ OptionalQName::None(t) => {
+ return Err(input.new_custom_error(
+ SelectorParseErrorKind::NoQualifiedNameInAttributeSelector(t),
+ ));
+ },
+ OptionalQName::Some(_, None) => unreachable!(),
+ OptionalQName::Some(ns, Some(ln)) => {
+ local_name = ln;
+ namespace = match ns {
+ QNamePrefix::ImplicitNoNamespace | QNamePrefix::ExplicitNoNamespace => None,
+ QNamePrefix::ExplicitNamespace(prefix, url) => {
+ Some(NamespaceConstraint::Specific((prefix, url)))
+ },
+ QNamePrefix::ExplicitAnyNamespace => Some(NamespaceConstraint::Any),
+ QNamePrefix::ImplicitAnyNamespace | QNamePrefix::ImplicitDefaultNamespace(_) => {
+ unreachable!() // Not returned with in_attr_selector = true
+ },
+ }
+ },
+ }
+
+ let location = input.current_source_location();
+ let operator = match input.next() {
+ // [foo]
+ Err(_) => {
+ let local_name_lower = to_ascii_lowercase(&local_name).as_ref().into();
+ let local_name = local_name.as_ref().into();
+ if let Some(namespace) = namespace {
+ return Ok(Component::AttributeOther(Box::new(
+ AttrSelectorWithOptionalNamespace {
+ namespace: Some(namespace),
+ local_name: local_name,
+ local_name_lower: local_name_lower,
+ operation: ParsedAttrSelectorOperation::Exists,
+ never_matches: false,
+ },
+ )));
+ } else {
+ return Ok(Component::AttributeInNoNamespaceExists {
+ local_name: local_name,
+ local_name_lower: local_name_lower,
+ });
+ }
+ },
+
+ // [foo=bar]
+ Ok(&Token::Delim('=')) => AttrSelectorOperator::Equal,
+ // [foo~=bar]
+ Ok(&Token::IncludeMatch) => AttrSelectorOperator::Includes,
+ // [foo|=bar]
+ Ok(&Token::DashMatch) => AttrSelectorOperator::DashMatch,
+ // [foo^=bar]
+ Ok(&Token::PrefixMatch) => AttrSelectorOperator::Prefix,
+ // [foo*=bar]
+ Ok(&Token::SubstringMatch) => AttrSelectorOperator::Substring,
+ // [foo$=bar]
+ Ok(&Token::SuffixMatch) => AttrSelectorOperator::Suffix,
+ Ok(t) => {
+ return Err(location.new_custom_error(
+ SelectorParseErrorKind::UnexpectedTokenInAttributeSelector(t.clone()),
+ ));
+ },
+ };
+
+ let value = match input.expect_ident_or_string() {
+ Ok(t) => t.clone(),
+ Err(BasicParseError {
+ kind: BasicParseErrorKind::UnexpectedToken(t),
+ location,
+ }) => return Err(location.new_custom_error(SelectorParseErrorKind::BadValueInAttr(t))),
+ Err(e) => return Err(e.into()),
+ };
+ let never_matches = match operator {
+ AttrSelectorOperator::Equal | AttrSelectorOperator::DashMatch => false,
+
+ AttrSelectorOperator::Includes => value.is_empty() || value.contains(SELECTOR_WHITESPACE),
+
+ AttrSelectorOperator::Prefix |
+ AttrSelectorOperator::Substring |
+ AttrSelectorOperator::Suffix => value.is_empty(),
+ };
+
+ let attribute_flags = parse_attribute_flags(input)?;
+
+ let value = value.as_ref().into();
+ let local_name_lower;
+ let local_name_is_ascii_lowercase;
+ let case_sensitivity;
+ {
+ let local_name_lower_cow = to_ascii_lowercase(&local_name);
+ case_sensitivity =
+ attribute_flags.to_case_sensitivity(local_name_lower_cow.as_ref(), namespace.is_some());
+ local_name_lower = local_name_lower_cow.as_ref().into();
+ local_name_is_ascii_lowercase = matches!(local_name_lower_cow, Cow::Borrowed(..));
+ }
+ let local_name = local_name.as_ref().into();
+ if namespace.is_some() || !local_name_is_ascii_lowercase {
+ Ok(Component::AttributeOther(Box::new(
+ AttrSelectorWithOptionalNamespace {
+ namespace,
+ local_name,
+ local_name_lower,
+ never_matches,
+ operation: ParsedAttrSelectorOperation::WithValue {
+ operator: operator,
+ case_sensitivity: case_sensitivity,
+ expected_value: value,
+ },
+ },
+ )))
+ } else {
+ Ok(Component::AttributeInNoNamespace {
+ local_name: local_name,
+ operator: operator,
+ value: value,
+ case_sensitivity: case_sensitivity,
+ never_matches: never_matches,
+ })
+ }
+}
+
+/// An attribute selector can have 's' or 'i' as flags, or no flags at all.
+enum AttributeFlags {
+ // Matching should be case-sensitive ('s' flag).
+ CaseSensitive,
+ // Matching should be case-insensitive ('i' flag).
+ AsciiCaseInsensitive,
+ // No flags. Matching behavior depends on the name of the attribute.
+ CaseSensitivityDependsOnName,
+}
+
+impl AttributeFlags {
+ fn to_case_sensitivity(self, local_name: &str, have_namespace: bool) -> ParsedCaseSensitivity {
+ match self {
+ AttributeFlags::CaseSensitive => ParsedCaseSensitivity::ExplicitCaseSensitive,
+ AttributeFlags::AsciiCaseInsensitive => ParsedCaseSensitivity::AsciiCaseInsensitive,
+ AttributeFlags::CaseSensitivityDependsOnName => {
+ if !have_namespace &&
+ include!(concat!(
+ env!("OUT_DIR"),
+ "/ascii_case_insensitive_html_attributes.rs"
+ ))
+ .contains(local_name)
+ {
+ ParsedCaseSensitivity::AsciiCaseInsensitiveIfInHtmlElementInHtmlDocument
+ } else {
+ ParsedCaseSensitivity::CaseSensitive
+ }
+ },
+ }
+ }
+}
+
+fn parse_attribute_flags<'i, 't>(
+ input: &mut CssParser<'i, 't>,
+) -> Result<AttributeFlags, BasicParseError<'i>> {
+ let location = input.current_source_location();
+ let token = match input.next() {
+ Ok(t) => t,
+ Err(..) => {
+ // Selectors spec says language-defined; HTML says it depends on the
+ // exact attribute name.
+ return Ok(AttributeFlags::CaseSensitivityDependsOnName);
+ },
+ };
+
+ let ident = match *token {
+ Token::Ident(ref i) => i,
+ ref other => return Err(location.new_basic_unexpected_token_error(other.clone())),
+ };
+
+ Ok(match_ignore_ascii_case! {
+ ident,
+ "i" => AttributeFlags::AsciiCaseInsensitive,
+ "s" => AttributeFlags::CaseSensitive,
+ _ => return Err(location.new_basic_unexpected_token_error(token.clone())),
+ })
+}
+
+/// Level 3: Parse **one** simple_selector. (Though we might insert a second
+/// implied "<defaultns>|*" type selector.)
+fn parse_negation<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ // We use a sequence because a type selector may be represented as two Components.
+ let mut sequence = SmallVec::<[Component<Impl>; 2]>::new();
+
+ input.skip_whitespace();
+
+ // Get exactly one simple selector. The parse logic in the caller will verify
+ // that there are no trailing tokens after we're done.
+ let is_type_sel = match parse_type_selector(parser, input, &mut sequence) {
+ Ok(result) => result,
+ Err(ParseError {
+ kind: ParseErrorKind::Basic(BasicParseErrorKind::EndOfInput),
+ ..
+ }) => return Err(input.new_custom_error(SelectorParseErrorKind::EmptyNegation)),
+ Err(e) => return Err(e.into()),
+ };
+ if !is_type_sel {
+ match parse_one_simple_selector(parser, input, SelectorParsingState::INSIDE_NEGATION)? {
+ Some(SimpleSelectorParseResult::SimpleSelector(s)) => {
+ sequence.push(s);
+ },
+ None => {
+ return Err(input.new_custom_error(SelectorParseErrorKind::EmptyNegation));
+ },
+ Some(SimpleSelectorParseResult::PseudoElement(_)) |
+ Some(SimpleSelectorParseResult::PartPseudo(_)) |
+ Some(SimpleSelectorParseResult::SlottedPseudo(_)) => {
+ let e = SelectorParseErrorKind::NonSimpleSelectorInNegation;
+ return Err(input.new_custom_error(e));
+ },
+ }
+ }
+
+ // Success.
+ Ok(Component::Negation(
+ sequence.into_vec().into_boxed_slice().into(),
+ ))
+}
+
+/// simple_selector_sequence
+/// : [ type_selector | universal ] [ HASH | class | attrib | pseudo | negation ]*
+/// | [ HASH | class | attrib | pseudo | negation ]+
+///
+/// `Err(())` means invalid selector.
+/// `Ok(None)` is an empty selector
+fn parse_compound_selector<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+ builder: &mut SelectorBuilder<Impl>,
+) -> Result<Option<SelectorParsingState>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ input.skip_whitespace();
+
+ let mut empty = true;
+ if !parse_type_selector(parser, input, builder)? {
+ if let Some(url) = parser.default_namespace() {
+ // If there was no explicit type selector, but there is a
+ // default namespace, there is an implicit "<defaultns>|*" type
+ // selector.
+ builder.push_simple_selector(Component::DefaultNamespace(url))
+ }
+ } else {
+ empty = false;
+ }
+
+ let mut state = SelectorParsingState::empty();
+ loop {
+ let parse_result = match parse_one_simple_selector(parser, input, state)? {
+ None => break,
+ Some(result) => result,
+ };
+
+ empty = false;
+
+ match parse_result {
+ SimpleSelectorParseResult::SimpleSelector(s) => {
+ builder.push_simple_selector(s);
+ },
+ SimpleSelectorParseResult::PartPseudo(part_names) => {
+ state.insert(SelectorParsingState::AFTER_PART);
+ builder.push_combinator(Combinator::Part);
+ builder.push_simple_selector(Component::Part(part_names));
+ },
+ SimpleSelectorParseResult::SlottedPseudo(selector) => {
+ state.insert(SelectorParsingState::AFTER_SLOTTED);
+ builder.push_combinator(Combinator::SlotAssignment);
+ builder.push_simple_selector(Component::Slotted(selector));
+ },
+ SimpleSelectorParseResult::PseudoElement(p) => {
+ state.insert(SelectorParsingState::AFTER_PSEUDO_ELEMENT);
+ if !p.accepts_state_pseudo_classes() {
+ state.insert(SelectorParsingState::AFTER_NON_STATEFUL_PSEUDO_ELEMENT);
+ }
+ builder.push_combinator(Combinator::PseudoElement);
+ builder.push_simple_selector(Component::PseudoElement(p));
+ },
+ }
+ }
+ if empty {
+ // An empty selector is invalid.
+ Ok(None)
+ } else {
+ Ok(Some(state))
+ }
+}
+
+fn parse_functional_pseudo_class<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+ name: CowRcStr<'i>,
+ state: SelectorParsingState,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ if !state.allows_functional_pseudo_classes() {
+ return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+ debug_assert!(state.allows_tree_structural_pseudo_classes());
+ match_ignore_ascii_case! { &name,
+ "nth-child" => return Ok(parse_nth_pseudo_class(input, Component::NthChild)?),
+ "nth-of-type" => return Ok(parse_nth_pseudo_class(input, Component::NthOfType)?),
+ "nth-last-child" => return Ok(parse_nth_pseudo_class(input, Component::NthLastChild)?),
+ "nth-last-of-type" => return Ok(parse_nth_pseudo_class(input, Component::NthLastOfType)?),
+ "host" => return Ok(Component::Host(Some(parse_inner_compound_selector(parser, input)?))),
+ "not" => {
+ if state.intersects(SelectorParsingState::INSIDE_NEGATION) {
+ return Err(input.new_custom_error(
+ SelectorParseErrorKind::UnexpectedIdent("not".into())
+ ));
+ }
+ debug_assert!(state.is_empty());
+ return parse_negation(parser, input)
+ },
+ _ => {}
+ }
+ P::parse_non_ts_functional_pseudo_class(parser, name, input).map(Component::NonTSPseudoClass)
+}
+
+fn parse_nth_pseudo_class<'i, 't, Impl, F>(
+ input: &mut CssParser<'i, 't>,
+ selector: F,
+) -> Result<Component<Impl>, BasicParseError<'i>>
+where
+ Impl: SelectorImpl,
+ F: FnOnce(i32, i32) -> Component<Impl>,
+{
+ let (a, b) = parse_nth(input)?;
+ Ok(selector(a, b))
+}
+
+/// Returns whether the name corresponds to a CSS2 pseudo-element that
+/// can be specified with the single colon syntax (in addition to the
+/// double-colon syntax, which can be used for all pseudo-elements).
+fn is_css2_pseudo_element(name: &str) -> bool {
+ // ** Do not add to this list! **
+ match_ignore_ascii_case! { name,
+ "before" | "after" | "first-line" | "first-letter" => true,
+ _ => false,
+ }
+}
+
+/// Parse a simple selector other than a type selector.
+///
+/// * `Err(())`: Invalid selector, abort
+/// * `Ok(None)`: Not a simple selector, could be something else. `input` was not consumed.
+/// * `Ok(Some(_))`: Parsed a simple selector or pseudo-element
+fn parse_one_simple_selector<'i, 't, P, Impl>(
+ parser: &P,
+ input: &mut CssParser<'i, 't>,
+ state: SelectorParsingState,
+) -> Result<Option<SimpleSelectorParseResult<Impl>>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ let start = input.state();
+ let token = match input.next_including_whitespace().map(|t| t.clone()) {
+ Ok(t) => t,
+ Err(..) => {
+ input.reset(&start);
+ return Ok(None);
+ },
+ };
+
+ Ok(Some(match token {
+ Token::IDHash(id) => {
+ if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+ return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+ let id = Component::ID(id.as_ref().into());
+ SimpleSelectorParseResult::SimpleSelector(id)
+ },
+ Token::Delim('.') => {
+ if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+ return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+ let location = input.current_source_location();
+ let class = match *input.next_including_whitespace()? {
+ Token::Ident(ref class) => class,
+ ref t => {
+ let e = SelectorParseErrorKind::ClassNeedsIdent(t.clone());
+ return Err(location.new_custom_error(e));
+ },
+ };
+ let class = Component::Class(class.as_ref().into());
+ SimpleSelectorParseResult::SimpleSelector(class)
+ },
+ Token::SquareBracketBlock => {
+ if state.intersects(SelectorParsingState::AFTER_PSEUDO) {
+ return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+ let attr = input.parse_nested_block(|input| parse_attribute_selector(parser, input))?;
+ SimpleSelectorParseResult::SimpleSelector(attr)
+ },
+ Token::Colon => {
+ let location = input.current_source_location();
+ let (is_single_colon, next_token) = match input.next_including_whitespace()?.clone() {
+ Token::Colon => (false, input.next_including_whitespace()?.clone()),
+ t => (true, t),
+ };
+ let (name, is_functional) = match next_token {
+ Token::Ident(name) => (name, false),
+ Token::Function(name) => (name, true),
+ t => {
+ let e = SelectorParseErrorKind::PseudoElementExpectedIdent(t);
+ return Err(input.new_custom_error(e));
+ },
+ };
+ let is_pseudo_element = !is_single_colon || is_css2_pseudo_element(&name);
+ if is_pseudo_element {
+ if state.intersects(SelectorParsingState::AFTER_PSEUDO_ELEMENT) {
+ return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+ let pseudo_element = if is_functional {
+ if P::parse_part(parser) && name.eq_ignore_ascii_case("part") {
+ if !state.allows_part() {
+ return Err(
+ input.new_custom_error(SelectorParseErrorKind::InvalidState)
+ );
+ }
+ let names = input.parse_nested_block(|input| {
+ let mut result = Vec::with_capacity(1);
+ result.push(input.expect_ident()?.as_ref().into());
+ while !input.is_exhausted() {
+ result.push(input.expect_ident()?.as_ref().into());
+ }
+ Ok(result.into_boxed_slice())
+ })?;
+ return Ok(Some(SimpleSelectorParseResult::PartPseudo(names)));
+ }
+ if P::parse_slotted(parser) && name.eq_ignore_ascii_case("slotted") {
+ if !state.allows_slotted() {
+ return Err(
+ input.new_custom_error(SelectorParseErrorKind::InvalidState)
+ );
+ }
+ let selector = input.parse_nested_block(|input| {
+ parse_inner_compound_selector(parser, input)
+ })?;
+ return Ok(Some(SimpleSelectorParseResult::SlottedPseudo(selector)));
+ }
+ input.parse_nested_block(|input| {
+ P::parse_functional_pseudo_element(parser, name, input)
+ })?
+ } else {
+ P::parse_pseudo_element(parser, location, name)?
+ };
+
+ if state.intersects(SelectorParsingState::AFTER_SLOTTED) &&
+ !pseudo_element.valid_after_slotted()
+ {
+ return Err(input.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+ SimpleSelectorParseResult::PseudoElement(pseudo_element)
+ } else {
+ let pseudo_class = if is_functional {
+ input.parse_nested_block(|input| {
+ parse_functional_pseudo_class(parser, input, name, state)
+ })?
+ } else {
+ parse_simple_pseudo_class(parser, location, name, state)?
+ };
+ SimpleSelectorParseResult::SimpleSelector(pseudo_class)
+ }
+ },
+ _ => {
+ input.reset(&start);
+ return Ok(None);
+ },
+ }))
+}
+
+fn parse_simple_pseudo_class<'i, P, Impl>(
+ parser: &P,
+ location: SourceLocation,
+ name: CowRcStr<'i>,
+ state: SelectorParsingState,
+) -> Result<Component<Impl>, ParseError<'i, P::Error>>
+where
+ P: Parser<'i, Impl = Impl>,
+ Impl: SelectorImpl,
+{
+ if !state.allows_non_functional_pseudo_classes() {
+ return Err(location.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+
+ if state.allows_tree_structural_pseudo_classes() {
+ match_ignore_ascii_case! { &name,
+ "first-child" => return Ok(Component::FirstChild),
+ "last-child" => return Ok(Component::LastChild),
+ "only-child" => return Ok(Component::OnlyChild),
+ "root" => return Ok(Component::Root),
+ "empty" => return Ok(Component::Empty),
+ "scope" => return Ok(Component::Scope),
+ "host" if P::parse_host(parser) => return Ok(Component::Host(None)),
+ "first-of-type" => return Ok(Component::FirstOfType),
+ "last-of-type" => return Ok(Component::LastOfType),
+ "only-of-type" => return Ok(Component::OnlyOfType),
+ _ => {},
+ }
+ }
+
+ let pseudo_class = P::parse_non_ts_pseudo_class(parser, location, name)?;
+ if state.intersects(SelectorParsingState::AFTER_PSEUDO_ELEMENT) &&
+ !pseudo_class.is_user_action_state()
+ {
+ return Err(location.new_custom_error(SelectorParseErrorKind::InvalidState));
+ }
+ Ok(Component::NonTSPseudoClass(pseudo_class))
+}
+
+// NB: pub module in order to access the DummyParser
+#[cfg(test)]
+pub mod tests {
+ use super::*;
+ use crate::builder::SelectorFlags;
+ use crate::parser;
+ use cssparser::{serialize_identifier, Parser as CssParser, ParserInput, ToCss};
+ use std::collections::HashMap;
+ use std::fmt;
+
+ #[derive(Clone, Debug, Eq, PartialEq)]
+ pub enum PseudoClass {
+ Hover,
+ Active,
+ Lang(String),
+ }
+
+ #[derive(Clone, Debug, Eq, PartialEq)]
+ pub enum PseudoElement {
+ Before,
+ After,
+ }
+
+ impl parser::PseudoElement for PseudoElement {
+ type Impl = DummySelectorImpl;
+
+ fn accepts_state_pseudo_classes(&self) -> bool {
+ true
+ }
+
+ fn valid_after_slotted(&self) -> bool {
+ true
+ }
+ }
+
+ impl parser::NonTSPseudoClass for PseudoClass {
+ type Impl = DummySelectorImpl;
+
+ #[inline]
+ fn is_active_or_hover(&self) -> bool {
+ matches!(*self, PseudoClass::Active | PseudoClass::Hover)
+ }
+
+ #[inline]
+ fn is_user_action_state(&self) -> bool {
+ self.is_active_or_hover()
+ }
+ }
+
+ impl ToCss for PseudoClass {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ match *self {
+ PseudoClass::Hover => dest.write_str(":hover"),
+ PseudoClass::Active => dest.write_str(":active"),
+ PseudoClass::Lang(ref lang) => {
+ dest.write_str(":lang(")?;
+ serialize_identifier(lang, dest)?;
+ dest.write_char(')')
+ },
+ }
+ }
+ }
+
+ impl ToCss for PseudoElement {
+ fn to_css<W>(&self, dest: &mut W) -> fmt::Result
+ where
+ W: fmt::Write,
+ {
+ match *self {
+ PseudoElement::Before => dest.write_str("::before"),
+ PseudoElement::After => dest.write_str("::after"),
+ }
+ }
+ }
+
+ impl Visit for PseudoClass {
+ type Impl = DummySelectorImpl;
+
+ fn visit<V>(&self, _visitor: &mut V) -> bool
+ where
+ V: SelectorVisitor<Impl = Self::Impl>,
+ {
+ true
+ }
+ }
+
+ #[derive(Clone, Debug, PartialEq)]
+ pub struct DummySelectorImpl;
+
+ #[derive(Default)]
+ pub struct DummyParser {
+ default_ns: Option<DummyAtom>,
+ ns_prefixes: HashMap<DummyAtom, DummyAtom>,
+ }
+
+ impl DummyParser {
+ fn default_with_namespace(default_ns: DummyAtom) -> DummyParser {
+ DummyParser {
+ default_ns: Some(default_ns),
+ ns_prefixes: Default::default(),
+ }
+ }
+ }
+
+ impl SelectorImpl for DummySelectorImpl {
+ type ExtraMatchingData = ();
+ type AttrValue = DummyAtom;
+ type Identifier = DummyAtom;
+ type ClassName = DummyAtom;
+ type PartName = DummyAtom;
+ type LocalName = DummyAtom;
+ type NamespaceUrl = DummyAtom;
+ type NamespacePrefix = DummyAtom;
+ type BorrowedLocalName = DummyAtom;
+ type BorrowedNamespaceUrl = DummyAtom;
+ type NonTSPseudoClass = PseudoClass;
+ type PseudoElement = PseudoElement;
+ }
+
+ #[derive(Clone, Debug, Default, Eq, Hash, PartialEq)]
+ pub struct DummyAtom(String);
+
+ impl fmt::Display for DummyAtom {
+ fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
+ <String as fmt::Display>::fmt(&self.0, fmt)
+ }
+ }
+
+ impl From<String> for DummyAtom {
+ fn from(string: String) -> Self {
+ DummyAtom(string)
+ }
+ }
+
+ impl<'a> From<&'a str> for DummyAtom {
+ fn from(string: &'a str) -> Self {
+ DummyAtom(string.into())
+ }
+ }
+
+ impl<'i> Parser<'i> for DummyParser {
+ type Impl = DummySelectorImpl;
+ type Error = SelectorParseErrorKind<'i>;
+
+ fn parse_slotted(&self) -> bool {
+ true
+ }
+
+ fn parse_part(&self) -> bool {
+ true
+ }
+
+ fn parse_non_ts_pseudo_class(
+ &self,
+ location: SourceLocation,
+ name: CowRcStr<'i>,
+ ) -> Result<PseudoClass, SelectorParseError<'i>> {
+ match_ignore_ascii_case! { &name,
+ "hover" => return Ok(PseudoClass::Hover),
+ "active" => return Ok(PseudoClass::Active),
+ _ => {}
+ }
+ Err(
+ location.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+ name,
+ )),
+ )
+ }
+
+ fn parse_non_ts_functional_pseudo_class<'t>(
+ &self,
+ name: CowRcStr<'i>,
+ parser: &mut CssParser<'i, 't>,
+ ) -> Result<PseudoClass, SelectorParseError<'i>> {
+ match_ignore_ascii_case! { &name,
+ "lang" => {
+ let lang = parser.expect_ident_or_string()?.as_ref().to_owned();
+ return Ok(PseudoClass::Lang(lang));
+ },
+ _ => {}
+ }
+ Err(
+ parser.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+ name,
+ )),
+ )
+ }
+
+ fn parse_pseudo_element(
+ &self,
+ location: SourceLocation,
+ name: CowRcStr<'i>,
+ ) -> Result<PseudoElement, SelectorParseError<'i>> {
+ match_ignore_ascii_case! { &name,
+ "before" => return Ok(PseudoElement::Before),
+ "after" => return Ok(PseudoElement::After),
+ _ => {}
+ }
+ Err(
+ location.new_custom_error(SelectorParseErrorKind::UnsupportedPseudoClassOrElement(
+ name,
+ )),
+ )
+ }
+
+ fn default_namespace(&self) -> Option<DummyAtom> {
+ self.default_ns.clone()
+ }
+
+ fn namespace_for_prefix(&self, prefix: &DummyAtom) -> Option<DummyAtom> {
+ self.ns_prefixes.get(prefix).cloned()
+ }
+ }
+
+ fn parse<'i>(
+ input: &'i str,
+ ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+ parse_ns(input, &DummyParser::default())
+ }
+
+ fn parse_expected<'i, 'a>(
+ input: &'i str,
+ expected: Option<&'a str>,
+ ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+ parse_ns_expected(input, &DummyParser::default(), expected)
+ }
+
+ fn parse_ns<'i>(
+ input: &'i str,
+ parser: &DummyParser,
+ ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+ parse_ns_expected(input, parser, None)
+ }
+
+ fn parse_ns_expected<'i, 'a>(
+ input: &'i str,
+ parser: &DummyParser,
+ expected: Option<&'a str>,
+ ) -> Result<SelectorList<DummySelectorImpl>, SelectorParseError<'i>> {
+ let mut parser_input = ParserInput::new(input);
+ let result = SelectorList::parse(parser, &mut CssParser::new(&mut parser_input));
+ if let Ok(ref selectors) = result {
+ assert_eq!(selectors.0.len(), 1);
+ // We can't assume that the serialized parsed selector will equal
+ // the input; for example, if there is no default namespace, '*|foo'
+ // should serialize to 'foo'.
+ assert_eq!(
+ selectors.0[0].to_css_string(),
+ match expected {
+ Some(x) => x,
+ None => input,
+ }
+ );
+ }
+ result
+ }
+
+ fn specificity(a: u32, b: u32, c: u32) -> u32 {
+ a << 20 | b << 10 | c
+ }
+
+ #[test]
+ fn test_empty() {
+ let mut input = ParserInput::new(":empty");
+ let list = SelectorList::parse(&DummyParser::default(), &mut CssParser::new(&mut input));
+ assert!(list.is_ok());
+ }
+
+ const MATHML: &'static str = "http://www.w3.org/1998/Math/MathML";;
+ const SVG: &'static str = "http://www.w3.org/2000/svg";;
+
+ #[test]
+ fn test_parsing() {
+ assert!(parse("").is_err());
+ assert!(parse(":lang(4)").is_err());
+ assert!(parse(":lang(en US)").is_err());
+ assert_eq!(
+ parse("EeÉ"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::LocalName(LocalName {
+ name: DummyAtom::from("EeÉ"),
+ lower_name: DummyAtom::from("eeÉ"),
+ })],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse("|e"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::ExplicitNoNamespace,
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("e"),
+ lower_name: DummyAtom::from("e"),
+ }),
+ ],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ // When the default namespace is not set, *| should be elided.
+ // https://github.com/servo/servo/pull/17537
+ assert_eq!(
+ parse_expected("*|e", Some("e")),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::LocalName(LocalName {
+ name: DummyAtom::from("e"),
+ lower_name: DummyAtom::from("e"),
+ })],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ // When the default namespace is set, *| should _not_ be elided (as foo
+ // is no longer equivalent to *|foo--the former is only for foo in the
+ // default namespace).
+ // https://github.com/servo/servo/issues/16020
+ assert_eq!(
+ parse_ns(
+ "*|e",
+ &DummyParser::default_with_namespace(DummyAtom::from("https://mozilla.org";))
+ ),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::ExplicitAnyNamespace,
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("e"),
+ lower_name: DummyAtom::from("e"),
+ }),
+ ],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse("*"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::ExplicitUniversalType],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse("|*"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::ExplicitNoNamespace,
+ Component::ExplicitUniversalType,
+ ],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_expected("*|*", Some("*")),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::ExplicitUniversalType],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns(
+ "*|*",
+ &DummyParser::default_with_namespace(DummyAtom::from("https://mozilla.org";))
+ ),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::ExplicitAnyNamespace,
+ Component::ExplicitUniversalType,
+ ],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse(".foo:lang(en-US)"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::Class(DummyAtom::from("foo")),
+ Component::NonTSPseudoClass(PseudoClass::Lang("en-US".to_owned())),
+ ],
+ specificity(0, 2, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse("#bar"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::ID(DummyAtom::from("bar"))],
+ specificity(1, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse("e.foo#bar"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("e"),
+ lower_name: DummyAtom::from("e"),
+ }),
+ Component::Class(DummyAtom::from("foo")),
+ Component::ID(DummyAtom::from("bar")),
+ ],
+ specificity(1, 1, 1),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse("e.foo #bar"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("e"),
+ lower_name: DummyAtom::from("e"),
+ }),
+ Component::Class(DummyAtom::from("foo")),
+ Component::Combinator(Combinator::Descendant),
+ Component::ID(DummyAtom::from("bar")),
+ ],
+ specificity(1, 1, 1),
+ Default::default(),
+ )]))
+ );
+ // Default namespace does not apply to attribute selectors
+ // https://github.com/mozilla/servo/pull/1652
+ let mut parser = DummyParser::default();
+ assert_eq!(
+ parse_ns("[Foo]", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::AttributeInNoNamespaceExists {
+ local_name: DummyAtom::from("Foo"),
+ local_name_lower: DummyAtom::from("foo"),
+ }],
+ specificity(0, 1, 0),
+ Default::default(),
+ )]))
+ );
+ assert!(parse_ns("svg|circle", &parser).is_err());
+ parser
+ .ns_prefixes
+ .insert(DummyAtom("svg".into()), DummyAtom(SVG.into()));
+ assert_eq!(
+ parse_ns("svg|circle", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("circle"),
+ lower_name: DummyAtom::from("circle"),
+ }),
+ ],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns("svg|*", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+ Component::ExplicitUniversalType,
+ ],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ // Default namespace does not apply to attribute selectors
+ // https://github.com/mozilla/servo/pull/1652
+ // but it does apply to implicit type selectors
+ // https://github.com/servo/rust-selectors/pull/82
+ parser.default_ns = Some(MATHML.into());
+ assert_eq!(
+ parse_ns("[Foo]", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::AttributeInNoNamespaceExists {
+ local_name: DummyAtom::from("Foo"),
+ local_name_lower: DummyAtom::from("foo"),
+ },
+ ],
+ specificity(0, 1, 0),
+ Default::default(),
+ )]))
+ );
+ // Default namespace does apply to type selectors
+ assert_eq!(
+ parse_ns("e", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("e"),
+ lower_name: DummyAtom::from("e"),
+ }),
+ ],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns("*", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::ExplicitUniversalType,
+ ],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns("*|*", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::ExplicitAnyNamespace,
+ Component::ExplicitUniversalType,
+ ],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ // Default namespace applies to universal and type selectors inside :not and :matches,
+ // but not otherwise.
+ assert_eq!(
+ parse_ns(":not(.cl)", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::Negation(
+ vec![Component::Class(DummyAtom::from("cl"))]
+ .into_boxed_slice()
+ .into(),
+ ),
+ ],
+ specificity(0, 1, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns(":not(*)", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::Negation(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::ExplicitUniversalType,
+ ]
+ .into_boxed_slice()
+ .into(),
+ ),
+ ],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns(":not(e)", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::Negation(
+ vec![
+ Component::DefaultNamespace(MATHML.into()),
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("e"),
+ lower_name: DummyAtom::from("e"),
+ }),
+ ]
+ .into_boxed_slice()
+ .into(),
+ ),
+ ],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse("[attr|=\"foo\"]"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::AttributeInNoNamespace {
+ local_name: DummyAtom::from("attr"),
+ operator: AttrSelectorOperator::DashMatch,
+ value: DummyAtom::from("foo"),
+ never_matches: false,
+ case_sensitivity: ParsedCaseSensitivity::CaseSensitive,
+ }],
+ specificity(0, 1, 0),
+ Default::default(),
+ )]))
+ );
+ // https://github.com/mozilla/servo/issues/1723
+ assert_eq!(
+ parse("::before"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::Combinator(Combinator::PseudoElement),
+ Component::PseudoElement(PseudoElement::Before),
+ ],
+ specificity(0, 0, 1),
+ SelectorFlags::HAS_PSEUDO,
+ )]))
+ );
+ assert_eq!(
+ parse("::before:hover"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::Combinator(Combinator::PseudoElement),
+ Component::PseudoElement(PseudoElement::Before),
+ Component::NonTSPseudoClass(PseudoClass::Hover),
+ ],
+ specificity(0, 1, 1),
+ SelectorFlags::HAS_PSEUDO,
+ )]))
+ );
+ assert_eq!(
+ parse("::before:hover:hover"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::Combinator(Combinator::PseudoElement),
+ Component::PseudoElement(PseudoElement::Before),
+ Component::NonTSPseudoClass(PseudoClass::Hover),
+ Component::NonTSPseudoClass(PseudoClass::Hover),
+ ],
+ specificity(0, 2, 1),
+ SelectorFlags::HAS_PSEUDO,
+ )]))
+ );
+ assert!(parse("::before:hover:lang(foo)").is_err());
+ assert!(parse("::before:hover .foo").is_err());
+ assert!(parse("::before .foo").is_err());
+ assert!(parse("::before ~ bar").is_err());
+ assert!(parse("::before:active").is_ok());
+
+ // https://github.com/servo/servo/issues/15335
+ assert!(parse(":: before").is_err());
+ assert_eq!(
+ parse("div ::after"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("div"),
+ lower_name: DummyAtom::from("div"),
+ }),
+ Component::Combinator(Combinator::Descendant),
+ Component::Combinator(Combinator::PseudoElement),
+ Component::PseudoElement(PseudoElement::After),
+ ],
+ specificity(0, 0, 2),
+ SelectorFlags::HAS_PSEUDO,
+ )]))
+ );
+ assert_eq!(
+ parse("#d1 > .ok"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![
+ Component::ID(DummyAtom::from("d1")),
+ Component::Combinator(Combinator::Child),
+ Component::Class(DummyAtom::from("ok")),
+ ],
+ (1 << 20) + (1 << 10) + (0 << 0),
+ Default::default(),
+ )]))
+ );
+ parser.default_ns = None;
+ assert!(parse(":not(#provel.old)").is_err());
+ assert!(parse(":not(#provel > old)").is_err());
+ assert!(parse("table[rules]:not([rules=\"none\"]):not([rules=\"\"])").is_ok());
+ assert_eq!(
+ parse(":not(#provel)"),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::Negation(
+ vec![Component::ID(DummyAtom::from("provel"))]
+ .into_boxed_slice()
+ .into(),
+ )],
+ specificity(1, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns(":not(svg|circle)", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::Negation(
+ vec![
+ Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+ Component::LocalName(LocalName {
+ name: DummyAtom::from("circle"),
+ lower_name: DummyAtom::from("circle"),
+ }),
+ ]
+ .into_boxed_slice()
+ .into(),
+ )],
+ specificity(0, 0, 1),
+ Default::default(),
+ )]))
+ );
+ // https://github.com/servo/servo/issues/16017
+ assert_eq!(
+ parse_ns(":not(*)", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::Negation(
+ vec![Component::ExplicitUniversalType]
+ .into_boxed_slice()
+ .into(),
+ )],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ assert_eq!(
+ parse_ns(":not(|*)", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::Negation(
+ vec![
+ Component::ExplicitNoNamespace,
+ Component::ExplicitUniversalType,
+ ]
+ .into_boxed_slice()
+ .into(),
+ )],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+ // *| should be elided if there is no default namespace.
+ // https://github.com/servo/servo/pull/17537
+ assert_eq!(
+ parse_ns_expected(":not(*|*)", &parser, Some(":not(*)")),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::Negation(
+ vec![Component::ExplicitUniversalType]
+ .into_boxed_slice()
+ .into(),
+ )],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+
+ assert_eq!(
+ parse_ns(":not(svg|*)", &parser),
+ Ok(SelectorList::from_vec(vec![Selector::from_vec(
+ vec![Component::Negation(
+ vec![
+ Component::Namespace(DummyAtom("svg".into()), SVG.into()),
+ Component::ExplicitUniversalType,
+ ]
+ .into_boxed_slice()
+ .into(),
+ )],
+ specificity(0, 0, 0),
+ Default::default(),
+ )]))
+ );
+
+ assert!(parse("::slotted()").is_err());
+ assert!(parse("::slotted(div)").is_ok());
+ assert!(parse("::slotted(div).foo").is_err());
+ assert!(parse("::slotted(div + bar)").is_err());
+ assert!(parse("::slotted(div) + foo").is_err());
+
+ assert!(parse("::part()").is_err());
+ assert!(parse("::part(42)").is_err());
+ assert!(parse("::part(foo bar)").is_ok());
+ assert!(parse("::part(foo):hover").is_ok());
+ assert!(parse("::part(foo) + bar").is_err());
+
+ assert!(parse("div ::slotted(div)").is_ok());
+ assert!(parse("div + slot::slotted(div)").is_ok());
+ assert!(parse("div + slot::slotted(div.foo)").is_ok());
+ assert!(parse("slot::slotted(div,foo)::first-line").is_err());
+ assert!(parse("::slotted(div)::before").is_ok());
+ assert!(parse("slot::slotted(div,foo)").is_err());
+ }
+
+ #[test]
+ fn test_pseudo_iter() {
+ let selector = &parse("q::before").unwrap().0[0];
+ assert!(!selector.is_universal());
+ let mut iter = selector.iter();
+ assert_eq!(
+ iter.next(),
+ Some(&Component::PseudoElement(PseudoElement::Before))
+ );
+ assert_eq!(iter.next(), None);
+ let combinator = iter.next_sequence();
+ assert_eq!(combinator, Some(Combinator::PseudoElement));
+ assert!(matches!(iter.next(), Some(&Component::LocalName(..))));
+ assert_eq!(iter.next(), None);
+ assert_eq!(iter.next_sequence(), None);
+ }
+
+ #[test]
+ fn test_universal() {
+ let selector = &parse_ns(
+ "*|*::before",
+ &DummyParser::default_with_namespace(DummyAtom::from("https://mozilla.org";)),
+ )
+ .unwrap()
+ .0[0];
+ assert!(selector.is_universal());
+ }
+
+ #[test]
+ fn test_empty_pseudo_iter() {
+ let selector = &parse("::before").unwrap().0[0];
+ assert!(selector.is_universal());
+ let mut iter = selector.iter();
+ assert_eq!(
+ iter.next(),
+ Some(&Component::PseudoElement(PseudoElement::Before))
+ );
+ assert_eq!(iter.next(), None);
+ assert_eq!(iter.next_sequence(), Some(Combinator::PseudoElement));
+ assert_eq!(iter.next(), None);
+ assert_eq!(iter.next_sequence(), None);
+ }
+
+ struct TestVisitor {
+ seen: Vec<String>,
+ }
+
+ impl SelectorVisitor for TestVisitor {
+ type Impl = DummySelectorImpl;
+
+ fn visit_simple_selector(&mut self, s: &Component<DummySelectorImpl>) -> bool {
+ let mut dest = String::new();
+ s.to_css(&mut dest).unwrap();
+ self.seen.push(dest);
+ true
+ }
+ }
+
+ #[test]
+ fn visitor() {
+ let mut test_visitor = TestVisitor { seen: vec![] };
+ parse(":not(:hover) ~ label").unwrap().0[0].visit(&mut test_visitor);
+ assert!(test_visitor.seen.contains(&":hover".into()));
+
+ let mut test_visitor = TestVisitor { seen: vec![] };
+ parse("::before:hover").unwrap().0[0].visit(&mut test_visitor);
+ assert!(test_visitor.seen.contains(&":hover".into()));
+ }
+}
diff --git a/servo_crates/selectors/sink.rs b/servo_crates/selectors/sink.rs
new file mode 100644
index 00000000..dcdd7ff2
--- /dev/null
+++ b/servo_crates/selectors/sink.rs
@@ -0,0 +1,31 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+//! Small helpers to abstract over different containers.
+#![deny(missing_docs)]
+
+use smallvec::{Array, SmallVec};
+
+/// A trait to abstract over a `push` method that may be implemented for
+/// different kind of types.
+///
+/// Used to abstract over `Array`, `SmallVec` and `Vec`, and also to implement a
+/// type which `push` method does only tweak a byte when we only need to check
+/// for the presence of something.
+pub trait Push<T> {
+ /// Push a value into self.
+ fn push(&mut self, value: T);
+}
+
+impl<T> Push<T> for Vec<T> {
+ fn push(&mut self, value: T) {
+ Vec::push(self, value);
+ }
+}
+
+impl<A: Array> Push<A::Item> for SmallVec<A> {
+ fn push(&mut self, value: A::Item) {
+ SmallVec::push(self, value);
+ }
+}
diff --git a/servo_crates/selectors/tree.rs b/servo_crates/selectors/tree.rs
new file mode 100644
index 00000000..f892abd4
--- /dev/null
+++ b/servo_crates/selectors/tree.rs
@@ -0,0 +1,140 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+//! Traits that nodes must implement. Breaks the otherwise-cyclic dependency
+//! between layout and style.
+
+use crate::attr::{AttrSelectorOperation, CaseSensitivity, NamespaceConstraint};
+use crate::matching::{ElementSelectorFlags, MatchingContext};
+use crate::parser::SelectorImpl;
+use std::fmt::Debug;
+use std::ptr::NonNull;
+
+/// Opaque representation of an Element, for identity comparisons.
+#[derive(Clone, Copy, Debug, Eq, Hash, PartialEq)]
+pub struct OpaqueElement(NonNull<()>);
+
+unsafe impl Send for OpaqueElement {}
+
+impl OpaqueElement {
+ /// Creates a new OpaqueElement from an arbitrarily-typed pointer.
+ pub fn new<T>(ptr: &T) -> Self {
+ unsafe {
+ OpaqueElement(NonNull::new_unchecked(
+ ptr as *const T as *const () as *mut (),
+ ))
+ }
+ }
+}
+
+pub trait Element: Sized + Clone + Debug {
+ type Impl: SelectorImpl;
+
+ /// Converts self into an opaque representation.
+ fn opaque(&self) -> OpaqueElement;
+
+ fn parent_element(&self) -> Option<Self>;
+
+ /// Whether the parent node of this element is a shadow root.
+ fn parent_node_is_shadow_root(&self) -> bool;
+
+ /// The host of the containing shadow root, if any.
+ fn containing_shadow_host(&self) -> Option<Self>;
+
+ /// The parent of a given pseudo-element, after matching a pseudo-element
+ /// selector.
+ ///
+ /// This is guaranteed to be called in a pseudo-element.
+ fn pseudo_element_originating_element(&self) -> Option<Self> {
+ debug_assert!(self.is_pseudo_element());
+ self.parent_element()
+ }
+
+ /// Whether we're matching on a pseudo-element.
+ fn is_pseudo_element(&self) -> bool;
+
+ /// Skips non-element nodes
+ fn prev_sibling_element(&self) -> Option<Self>;
+
+ /// Skips non-element nodes
+ fn next_sibling_element(&self) -> Option<Self>;
+
+ fn is_html_element_in_html_document(&self) -> bool;
+
+ fn has_local_name(&self, local_name: &<Self::Impl as SelectorImpl>::BorrowedLocalName) -> bool;
+
+ /// Empty string for no namespace
+ fn has_namespace(&self, ns: &<Self::Impl as SelectorImpl>::BorrowedNamespaceUrl) -> bool;
+
+ /// Whether this element and the `other` element have the same local name and namespace.
+ fn is_same_type(&self, other: &Self) -> bool;
+
+ fn attr_matches(
+ &self,
+ ns: &NamespaceConstraint<&<Self::Impl as SelectorImpl>::NamespaceUrl>,
+ local_name: &<Self::Impl as SelectorImpl>::LocalName,
+ operation: &AttrSelectorOperation<&<Self::Impl as SelectorImpl>::AttrValue>,
+ ) -> bool;
+
+ fn match_non_ts_pseudo_class<F>(
+ &self,
+ pc: &<Self::Impl as SelectorImpl>::NonTSPseudoClass,
+ context: &mut MatchingContext<Self::Impl>,
+ flags_setter: &mut F,
+ ) -> bool
+ where
+ F: FnMut(&Self, ElementSelectorFlags);
+
+ fn match_pseudo_element(
+ &self,
+ pe: &<Self::Impl as SelectorImpl>::PseudoElement,
+ context: &mut MatchingContext<Self::Impl>,
+ ) -> bool;
+
+ /// Whether this element is a `link`.
+ fn is_link(&self) -> bool;
+
+ /// Returns whether the element is an HTML <slot> element.
+ fn is_html_slot_element(&self) -> bool;
+
+ /// Returns the assigned <slot> element this element is assigned to.
+ ///
+ /// Necessary for the `::slotted` pseudo-class.
+ fn assigned_slot(&self) -> Option<Self> {
+ None
+ }
+
+ fn has_id(
+ &self,
+ id: &<Self::Impl as SelectorImpl>::Identifier,
+ case_sensitivity: CaseSensitivity,
+ ) -> bool;
+
+ fn has_class(
+ &self,
+ name: &<Self::Impl as SelectorImpl>::ClassName,
+ case_sensitivity: CaseSensitivity,
+ ) -> bool;
+
+ fn is_part(&self, name: &<Self::Impl as SelectorImpl>::PartName) -> bool;
+
+ /// Returns whether this element matches `:empty`.
+ ///
+ /// That is, whether it does not contain any child element or any non-zero-length text node.
+ /// See http://dev.w3.org/csswg/selectors-3/#empty-pseudo
+ fn is_empty(&self) -> bool;
+
+ /// Returns whether this element matches `:root`,
+ /// i.e. whether it is the root element of a document.
+ ///
+ /// Note: this can be false even if `.parent_element()` is `None`
+ /// if the parent node is a `DocumentFragment`.
+ fn is_root(&self) -> bool;
+
+ /// Returns whether this element should ignore matching nth child
+ /// selector.
+ fn ignores_nth_child_selectors(&self) -> bool {
+ false
+ }
+}
diff --git a/servo_crates/selectors/visitor.rs b/servo_crates/selectors/visitor.rs
new file mode 100644
index 00000000..60d118d3
--- /dev/null
+++ b/servo_crates/selectors/visitor.rs
@@ -0,0 +1,72 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+//! Visitor traits for selectors.
+
+#![deny(missing_docs)]
+
+use crate::attr::NamespaceConstraint;
+use crate::parser::{Combinator, Component, SelectorImpl};
+
+/// A trait to visit selector properties.
+///
+/// All the `visit_foo` methods return a boolean indicating whether the
+/// traversal should continue or not.
+pub trait SelectorVisitor {
+ /// The selector implementation this visitor wants to visit.
+ type Impl: SelectorImpl;
+
+ /// Visit an attribute selector that may match (there are other selectors
+ /// that may never match, like those containing whitespace or the empty
+ /// string).
+ fn visit_attribute_selector(
+ &mut self,
+ _namespace: &NamespaceConstraint<&<Self::Impl as SelectorImpl>::NamespaceUrl>,
+ _local_name: &<Self::Impl as SelectorImpl>::LocalName,
+ _local_name_lower: &<Self::Impl as SelectorImpl>::LocalName,
+ ) -> bool {
+ true
+ }
+
+ /// Visit a simple selector.
+ fn visit_simple_selector(&mut self, _: &Component<Self::Impl>) -> bool {
+ true
+ }
+
+ /// Visits a complex selector.
+ ///
+ /// Gets the combinator to the right of the selector, or `None` if the
+ /// selector is the rightmost one.
+ fn visit_complex_selector(&mut self, _combinator_to_right: Option<Combinator>) -> bool {
+ true
+ }
+}
+
+/// Enables traversing selector components stored in various types
+pub trait Visit {
+ /// The type parameter of selector component types.
+ type Impl: SelectorImpl;
+
+ /// Traverse selector components inside `self`.
+ ///
+ /// Implementations of this method should call `SelectorVisitor` methods
+ /// or other impls of `Visit` as appropriate based on the fields of `Self`.
+ ///
+ /// A return value of `false` indicates terminating the traversal.
+ /// It should be propagated with an early return.
+ /// On the contrary, `true` indicates that all fields of `self` have been traversed:
+ ///
+ /// ```rust,ignore
+ /// if !visitor.visit_simple_selector(&self.some_simple_selector) {
+ /// return false;
+ /// }
+ /// if !self.some_component.visit(visitor) {
+ /// return false;
+ /// }
+ /// true
+ /// ```
+ fn visit<V>(&self, visitor: &mut V) -> bool
+ where
+ V: SelectorVisitor<Impl = Self::Impl>;
+}
diff --git a/servo_crates/servo_arc/Cargo.toml b/servo_crates/servo_arc/Cargo.toml
new file mode 100644
index 00000000..3581210c
--- /dev/null
+++ b/servo_crates/servo_arc/Cargo.toml
@@ -0,0 +1,20 @@
+[package]
+name = "servo_arc"
+version = "0.1.1"
+authors = ["The Servo Project Developers"]
+license = "MIT/Apache-2.0"
+repository = "https://github.com/servo/servo";
+description = "A fork of std::sync::Arc with some extra functionality and without weak references"
+
+[lib]
+name = "servo_arc"
+path = "lib.rs"
+
+[features]
+servo = ["serde"]
+gecko_refcount_logging = []
+
+[dependencies]
+nodrop = {version = "0.1.8"}
+serde = {version = "1.0", optional = true}
+stable_deref_trait = "1.0.0"
diff --git a/servo_crates/servo_arc/lib.rs b/servo_crates/servo_arc/lib.rs
new file mode 100644
index 00000000..ad4489c1
--- /dev/null
+++ b/servo_crates/servo_arc/lib.rs
@@ -0,0 +1,1490 @@
+// Copyright 2012-2014 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+//! Fork of Arc for Servo. This has the following advantages over std::sync::Arc:
+//!
+//! * We don't waste storage on the weak reference count.
+//! * We don't do extra RMU operations to handle the possibility of weak references.
+//! * We can experiment with arena allocation (todo).
+//! * We can add methods to support our custom use cases [1].
+//! * We have support for dynamically-sized types (see from_header_and_iter).
+//! * We have support for thin arcs to unsized types (see ThinArc).
+//! * We have support for references to static data, which don't do any
+//! refcounting.
+//!
+//! [1]: https://bugzilla.mozilla.org/show_bug.cgi?id=1360883
+
+// The semantics of `Arc` are already documented in the Rust docs, so we don't
+// duplicate those here.
+#![allow(missing_docs)]
+
+extern crate nodrop;
+#[cfg(feature = "servo")]
+extern crate serde;
+extern crate stable_deref_trait;
+
+use nodrop::NoDrop;
+#[cfg(feature = "servo")]
+use serde::{Deserialize, Serialize};
+use stable_deref_trait::{CloneStableDeref, StableDeref};
+use std::alloc::{self, Layout};
+use std::borrow;
+use std::cmp::Ordering;
+use std::convert::From;
+use std::fmt;
+use std::hash::{Hash, Hasher};
+use std::iter::{ExactSizeIterator, Iterator};
+use std::marker::PhantomData;
+use std::mem::{self, align_of, size_of};
+use std::ops::{Deref, DerefMut};
+use std::os::raw::c_void;
+use std::process;
+use std::ptr;
+use std::slice;
+use std::sync::atomic;
+use std::sync::atomic::Ordering::{Acquire, Relaxed, Release};
+use std::{isize, usize};
+
+/// A soft limit on the amount of references that may be made to an `Arc`.
+///
+/// Going above this limit will abort your program (although not
+/// necessarily) at _exactly_ `MAX_REFCOUNT + 1` references.
+const MAX_REFCOUNT: usize = (isize::MAX) as usize;
+
+/// Special refcount value that means the data is not reference counted,
+/// and that the `Arc` is really acting as a read-only static reference.
+const STATIC_REFCOUNT: usize = usize::MAX;
+
+/// An atomically reference counted shared pointer
+///
+/// See the documentation for [`Arc`] in the standard library. Unlike the
+/// standard library `Arc`, this `Arc` does not support weak reference counting.
+///
+/// See the discussion in https://github.com/rust-lang/rust/pull/60594 for the
+/// usage of PhantomData.
+///
+/// [`Arc`]: https://doc.rust-lang.org/stable/std/sync/struct.Arc.html
+///
+/// cbindgen:derive-eq=false
+/// cbindgen:derive-neq=false
+#[repr(C)]
+pub struct Arc<T: ?Sized> {
+ p: ptr::NonNull<ArcInner<T>>,
+ phantom: PhantomData<T>,
+}
+
+/// An `Arc` that is known to be uniquely owned
+///
+/// When `Arc`s are constructed, they are known to be
+/// uniquely owned. In such a case it is safe to mutate
+/// the contents of the `Arc`. Normally, one would just handle
+/// this by mutating the data on the stack before allocating the
+/// `Arc`, however it's possible the data is large or unsized
+/// and you need to heap-allocate it earlier in such a way
+/// that it can be freely converted into a regular `Arc` once you're
+/// done.
+///
+/// `UniqueArc` exists for this purpose, when constructed it performs
+/// the same allocations necessary for an `Arc`, however it allows mutable access.
+/// Once the mutation is finished, you can call `.shareable()` and get a regular `Arc`
+/// out of it.
+///
+/// Ignore the doctest below there's no way to skip building with refcount
+/// logging during doc tests (see rust-lang/rust#45599).
+///
+/// ```rust,ignore
+/// # use servo_arc::UniqueArc;
+/// let data = [1, 2, 3, 4, 5];
+/// let mut x = UniqueArc::new(data);
+/// x[4] = 7; // mutate!
+/// let y = x.shareable(); // y is an Arc<T>
+/// ```
+pub struct UniqueArc<T: ?Sized>(Arc<T>);
+
+impl<T> UniqueArc<T> {
+ #[inline]
+ /// Construct a new UniqueArc
+ pub fn new(data: T) -> Self {
+ UniqueArc(Arc::new(data))
+ }
+
+ /// Construct an uninitialized arc
+ #[inline]
+ pub fn new_uninit() -> UniqueArc<mem::MaybeUninit<T>> {
+ unsafe {
+ let layout = Layout::new::<ArcInner<mem::MaybeUninit<T>>>();
+ let ptr = alloc::alloc(layout);
+ let mut p = ptr::NonNull::new(ptr)
+ .unwrap_or_else(|| alloc::handle_alloc_error(layout))
+ .cast::<ArcInner<mem::MaybeUninit<T>>>();
+ ptr::write(&mut p.as_mut().count, atomic::AtomicUsize::new(1));
+
+ #[cfg(feature = "gecko_refcount_logging")]
+ {
+ NS_LogCtor(p.as_ptr() as *mut _, b"ServoArc\0".as_ptr() as *const _, 8)
+ }
+
+ UniqueArc(Arc {
+ p,
+ phantom: PhantomData,
+ })
+ }
+ }
+
+ #[inline]
+ /// Convert to a shareable Arc<T> once we're done mutating it
+ pub fn shareable(self) -> Arc<T> {
+ self.0
+ }
+}
+
+impl<T> UniqueArc<mem::MaybeUninit<T>> {
+ /// Convert to an initialized Arc.
+ #[inline]
+ pub unsafe fn assume_init(this: Self) -> UniqueArc<T> {
+ UniqueArc(Arc {
+ p: mem::ManuallyDrop::new(this).0.p.cast(),
+ phantom: PhantomData,
+ })
+ }
+}
+
+impl<T> Deref for UniqueArc<T> {
+ type Target = T;
+ fn deref(&self) -> &T {
+ &*self.0
+ }
+}
+
+impl<T> DerefMut for UniqueArc<T> {
+ fn deref_mut(&mut self) -> &mut T {
+ // We know this to be uniquely owned
+ unsafe { &mut (*self.0.ptr()).data }
+ }
+}
+
+unsafe impl<T: ?Sized + Sync + Send> Send for Arc<T> {}
+unsafe impl<T: ?Sized + Sync + Send> Sync for Arc<T> {}
+
+/// The object allocated by an Arc<T>
+#[repr(C)]
+struct ArcInner<T: ?Sized> {
+ count: atomic::AtomicUsize,
+ data: T,
+}
+
+unsafe impl<T: ?Sized + Sync + Send> Send for ArcInner<T> {}
+unsafe impl<T: ?Sized + Sync + Send> Sync for ArcInner<T> {}
+
+/// Computes the offset of the data field within ArcInner.
+fn data_offset<T>() -> usize {
+ let size = size_of::<ArcInner<()>>();
+ let align = align_of::<T>();
+ // https://github.com/rust-lang/rust/blob/1.36.0/src/libcore/alloc.rs#L187-L207
+ size.wrapping_add(align).wrapping_sub(1) & !align.wrapping_sub(1)
+}
+
+impl<T> Arc<T> {
+ /// Construct an `Arc<T>`
+ #[inline]
+ pub fn new(data: T) -> Self {
+ let ptr = Box::into_raw(Box::new(ArcInner {
+ count: atomic::AtomicUsize::new(1),
+ data,
+ }));
+
+ #[cfg(feature = "gecko_refcount_logging")]
+ unsafe {
+ // FIXME(emilio): Would be so amazing to have
+ // std::intrinsics::type_name() around, so that we could also report
+ // a real size.
+ NS_LogCtor(ptr as *mut _, b"ServoArc\0".as_ptr() as *const _, 8);
+ }
+
+ unsafe {
+ Arc {
+ p: ptr::NonNull::new_unchecked(ptr),
+ phantom: PhantomData,
+ }
+ }
+ }
+
+ /// Construct an intentionally-leaked arc.
+ #[inline]
+ pub fn new_leaked(data: T) -> Self {
+ let arc = Self::new(data);
+ arc.mark_as_intentionally_leaked();
+ arc
+ }
+
+ /// Convert the Arc<T> to a raw pointer, suitable for use across FFI
+ ///
+ /// Note: This returns a pointer to the data T, which is offset in the allocation.
+ ///
+ /// It is recommended to use RawOffsetArc for this.
+ #[inline]
+ fn into_raw(this: Self) -> *const T {
+ let ptr = unsafe { &((*this.ptr()).data) as *const _ };
+ mem::forget(this);
+ ptr
+ }
+
+ /// Reconstruct the Arc<T> from a raw pointer obtained from into_raw()
+ ///
+ /// Note: This raw pointer will be offset in the allocation and must be preceded
+ /// by the atomic count.
+ ///
+ /// It is recommended to use RawOffsetArc for this
+ #[inline]
+ unsafe fn from_raw(ptr: *const T) -> Self {
+ // To find the corresponding pointer to the `ArcInner` we need
+ // to subtract the offset of the `data` field from the pointer.
+ let ptr = (ptr as *const u8).sub(data_offset::<T>());
+ Arc {
+ p: ptr::NonNull::new_unchecked(ptr as *mut ArcInner<T>),
+ phantom: PhantomData,
+ }
+ }
+
+ /// Create a new static Arc<T> (one that won't reference count the object)
+ /// and place it in the allocation provided by the specified `alloc`
+ /// function.
+ ///
+ /// `alloc` must return a pointer into a static allocation suitable for
+ /// storing data with the `Layout` passed into it. The pointer returned by
+ /// `alloc` will not be freed.
+ #[inline]
+ pub unsafe fn new_static<F>(alloc: F, data: T) -> Arc<T>
+ where
+ F: FnOnce(Layout) -> *mut u8,
+ {
+ let ptr = alloc(Layout::new::<ArcInner<T>>()) as *mut ArcInner<T>;
+
+ let x = ArcInner {
+ count: atomic::AtomicUsize::new(STATIC_REFCOUNT),
+ data,
+ };
+
+ ptr::write(ptr, x);
+
+ Arc {
+ p: ptr::NonNull::new_unchecked(ptr),
+ phantom: PhantomData,
+ }
+ }
+
+ /// Produce a pointer to the data that can be converted back
+ /// to an Arc. This is basically an `&Arc<T>`, without the extra indirection.
+ /// It has the benefits of an `&T` but also knows about the underlying refcount
+ /// and can be converted into more `Arc<T>`s if necessary.
+ #[inline]
+ pub fn borrow_arc<'a>(&'a self) -> ArcBorrow<'a, T> {
+ ArcBorrow(&**self)
+ }
+
+ /// Temporarily converts |self| into a bonafide RawOffsetArc and exposes it to the
+ /// provided callback. The refcount is not modified.
+ #[inline(always)]
+ pub fn with_raw_offset_arc<F, U>(&self, f: F) -> U
+ where
+ F: FnOnce(&RawOffsetArc<T>) -> U,
+ {
+ // Synthesize transient Arc, which never touches the refcount of the ArcInner.
+ let transient = unsafe { NoDrop::new(Arc::into_raw_offset(ptr::read(self))) };
+
+ // Expose the transient Arc to the callback, which may clone it if it wants.
+ let result = f(&transient);
+
+ // Forget the transient Arc to leave the refcount untouched.
+ mem::forget(transient);
+
+ // Forward the result.
+ result
+ }
+
+ /// Returns the address on the heap of the Arc itself -- not the T within it -- for memory
+ /// reporting.
+ ///
+ /// If this is a static reference, this returns null.
+ pub fn heap_ptr(&self) -> *const c_void {
+ if self.inner().count.load(Relaxed) == STATIC_REFCOUNT {
+ ptr::null()
+ } else {
+ self.p.as_ptr() as *const ArcInner<T> as *const c_void
+ }
+ }
+}
+
+impl<T: ?Sized> Arc<T> {
+ #[inline]
+ fn inner(&self) -> &ArcInner<T> {
+ // This unsafety is ok because while this arc is alive we're guaranteed
+ // that the inner pointer is valid. Furthermore, we know that the
+ // `ArcInner` structure itself is `Sync` because the inner data is
+ // `Sync` as well, so we're ok loaning out an immutable pointer to these
+ // contents.
+ unsafe { &*self.ptr() }
+ }
+
+ #[inline(always)]
+ fn record_drop(&self) {
+ #[cfg(feature = "gecko_refcount_logging")]
+ unsafe {
+ NS_LogDtor(self.ptr() as *mut _, b"ServoArc\0".as_ptr() as *const _, 8);
+ }
+ }
+
+ /// Marks this `Arc` as intentionally leaked for the purposes of refcount
+ /// logging.
+ ///
+ /// It's a logic error to call this more than once, but it's not unsafe, as
+ /// it'd just report negative leaks.
+ #[inline(always)]
+ pub fn mark_as_intentionally_leaked(&self) {
+ self.record_drop();
+ }
+
+ // Non-inlined part of `drop`. Just invokes the destructor and calls the
+ // refcount logging machinery if enabled.
+ #[inline(never)]
+ unsafe fn drop_slow(&mut self) {
+ self.record_drop();
+ let _ = Box::from_raw(self.ptr());
+ }
+
+ /// Test pointer equality between the two Arcs, i.e. they must be the _same_
+ /// allocation
+ #[inline]
+ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
+ this.ptr() == other.ptr()
+ }
+
+ fn ptr(&self) -> *mut ArcInner<T> {
+ self.p.as_ptr()
+ }
+}
+
+#[cfg(feature = "gecko_refcount_logging")]
+extern "C" {
+ fn NS_LogCtor(
+ aPtr: *mut std::os::raw::c_void,
+ aTypeName: *const std::os::raw::c_char,
+ aSize: u32,
+ );
+ fn NS_LogDtor(
+ aPtr: *mut std::os::raw::c_void,
+ aTypeName: *const std::os::raw::c_char,
+ aSize: u32,
+ );
+}
+
+impl<T: ?Sized> Clone for Arc<T> {
+ #[inline]
+ fn clone(&self) -> Self {
+ // NOTE(emilio): If you change anything here, make sure that the
+ // implementation in layout/style/ServoStyleConstsInlines.h matches!
+ //
+ // Using a relaxed ordering to check for STATIC_REFCOUNT is safe, since
+ // `count` never changes between STATIC_REFCOUNT and other values.
+ if self.inner().count.load(Relaxed) != STATIC_REFCOUNT {
+ // Using a relaxed ordering is alright here, as knowledge of the
+ // original reference prevents other threads from erroneously deleting
+ // the object.
+ //
+ // As explained in the [Boost documentation][1], Increasing the
+ // reference counter can always be done with memory_order_relaxed: New
+ // references to an object can only be formed from an existing
+ // reference, and passing an existing reference from one thread to
+ // another must already provide any required synchronization.
+ //
+ // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
+ let old_size = self.inner().count.fetch_add(1, Relaxed);
+
+ // However we need to guard against massive refcounts in case someone
+ // is `mem::forget`ing Arcs. If we don't do this the count can overflow
+ // and users will use-after free. We racily saturate to `isize::MAX` on
+ // the assumption that there aren't ~2 billion threads incrementing
+ // the reference count at once. This branch will never be taken in
+ // any realistic program.
+ //
+ // We abort because such a program is incredibly degenerate, and we
+ // don't care to support it.
+ if old_size > MAX_REFCOUNT {
+ process::abort();
+ }
+ }
+
+ unsafe {
+ Arc {
+ p: ptr::NonNull::new_unchecked(self.ptr()),
+ phantom: PhantomData,
+ }
+ }
+ }
+}
+
+impl<T: ?Sized> Deref for Arc<T> {
+ type Target = T;
+
+ #[inline]
+ fn deref(&self) -> &T {
+ &self.inner().data
+ }
+}
+
+impl<T: Clone> Arc<T> {
+ /// Makes a mutable reference to the `Arc`, cloning if necessary
+ ///
+ /// This is functionally equivalent to [`Arc::make_mut`][mm] from the standard library.
+ ///
+ /// If this `Arc` is uniquely owned, `make_mut()` will provide a mutable
+ /// reference to the contents. If not, `make_mut()` will create a _new_ `Arc`
+ /// with a copy of the contents, update `this` to point to it, and provide
+ /// a mutable reference to its contents.
+ ///
+ /// This is useful for implementing copy-on-write schemes where you wish to
+ /// avoid copying things if your `Arc` is not shared.
+ ///
+ /// [mm]: https://doc.rust-lang.org/stable/std/sync/struct.Arc.html#method.make_mut
+ #[inline]
+ pub fn make_mut(this: &mut Self) -> &mut T {
+ if !this.is_unique() {
+ // Another pointer exists; clone
+ *this = Arc::new((**this).clone());
+ }
+
+ unsafe {
+ // This unsafety is ok because we're guaranteed that the pointer
+ // returned is the *only* pointer that will ever be returned to T. Our
+ // reference count is guaranteed to be 1 at this point, and we required
+ // the Arc itself to be `mut`, so we're returning the only possible
+ // reference to the inner data.
+ &mut (*this.ptr()).data
+ }
+ }
+}
+
+impl<T: ?Sized> Arc<T> {
+ /// Provides mutable access to the contents _if_ the `Arc` is uniquely owned.
+ #[inline]
+ pub fn get_mut(this: &mut Self) -> Option<&mut T> {
+ if this.is_unique() {
+ unsafe {
+ // See make_mut() for documentation of the threadsafety here.
+ Some(&mut (*this.ptr()).data)
+ }
+ } else {
+ None
+ }
+ }
+
+ /// Whether or not the `Arc` is uniquely owned (is the refcount 1?) and not
+ /// a static reference.
+ #[inline]
+ pub fn is_unique(&self) -> bool {
+ // See the extensive discussion in [1] for why this needs to be Acquire.
+ //
+ // [1] https://github.com/servo/servo/issues/21186
+ self.inner().count.load(Acquire) == 1
+ }
+}
+
+impl<T: ?Sized> Drop for Arc<T> {
+ #[inline]
+ fn drop(&mut self) {
+ // NOTE(emilio): If you change anything here, make sure that the
+ // implementation in layout/style/ServoStyleConstsInlines.h matches!
+ //
+ // Using a relaxed ordering to check for STATIC_REFCOUNT is safe, since
+ // `count` never changes between STATIC_REFCOUNT and other values.
+ if self.inner().count.load(Relaxed) == STATIC_REFCOUNT {
+ return;
+ }
+
+ // Because `fetch_sub` is already atomic, we do not need to synchronize
+ // with other threads unless we are going to delete the object.
+ if self.inner().count.fetch_sub(1, Release) != 1 {
+ return;
+ }
+
+ // FIXME(bholley): Use the updated comment when [2] is merged.
+ //
+ // This load is needed to prevent reordering of use of the data and
+ // deletion of the data. Because it is marked `Release`, the decreasing
+ // of the reference count synchronizes with this `Acquire` load. This
+ // means that use of the data happens before decreasing the reference
+ // count, which happens before this load, which happens before the
+ // deletion of the data.
+ //
+ // As explained in the [Boost documentation][1],
+ //
+ // > It is important to enforce any possible access to the object in one
+ // > thread (through an existing reference) to *happen before* deleting
+ // > the object in a different thread. This is achieved by a "release"
+ // > operation after dropping a reference (any access to the object
+ // > through this reference must obviously happened before), and an
+ // > "acquire" operation before deleting the object.
+ //
+ // [1]: (www.boost.org/doc/libs/1_55_0/doc/html/atomic/usage_examples.html)
+ // [2]: https://github.com/rust-lang/rust/pull/41714
+ self.inner().count.load(Acquire);
+
+ unsafe {
+ self.drop_slow();
+ }
+ }
+}
+
+impl<T: ?Sized + PartialEq> PartialEq for Arc<T> {
+ fn eq(&self, other: &Arc<T>) -> bool {
+ Self::ptr_eq(self, other) || *(*self) == *(*other)
+ }
+
+ fn ne(&self, other: &Arc<T>) -> bool {
+ !Self::ptr_eq(self, other) && *(*self) != *(*other)
+ }
+}
+
+impl<T: ?Sized + PartialOrd> PartialOrd for Arc<T> {
+ fn partial_cmp(&self, other: &Arc<T>) -> Option<Ordering> {
+ (**self).partial_cmp(&**other)
+ }
+
+ fn lt(&self, other: &Arc<T>) -> bool {
+ *(*self) < *(*other)
+ }
+
+ fn le(&self, other: &Arc<T>) -> bool {
+ *(*self) <= *(*other)
+ }
+
+ fn gt(&self, other: &Arc<T>) -> bool {
+ *(*self) > *(*other)
+ }
+
+ fn ge(&self, other: &Arc<T>) -> bool {
+ *(*self) >= *(*other)
+ }
+}
+impl<T: ?Sized + Ord> Ord for Arc<T> {
+ fn cmp(&self, other: &Arc<T>) -> Ordering {
+ (**self).cmp(&**other)
+ }
+}
+impl<T: ?Sized + Eq> Eq for Arc<T> {}
+
+impl<T: ?Sized + fmt::Display> fmt::Display for Arc<T> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fmt::Display::fmt(&**self, f)
+ }
+}
+
+impl<T: ?Sized + fmt::Debug> fmt::Debug for Arc<T> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fmt::Debug::fmt(&**self, f)
+ }
+}
+
+impl<T: ?Sized> fmt::Pointer for Arc<T> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fmt::Pointer::fmt(&self.ptr(), f)
+ }
+}
+
+impl<T: Default> Default for Arc<T> {
+ fn default() -> Arc<T> {
+ Arc::new(Default::default())
+ }
+}
+
+impl<T: ?Sized + Hash> Hash for Arc<T> {
+ fn hash<H: Hasher>(&self, state: &mut H) {
+ (**self).hash(state)
+ }
+}
+
+impl<T> From<T> for Arc<T> {
+ #[inline]
+ fn from(t: T) -> Self {
+ Arc::new(t)
+ }
+}
+
+impl<T: ?Sized> borrow::Borrow<T> for Arc<T> {
+ #[inline]
+ fn borrow(&self) -> &T {
+ &**self
+ }
+}
+
+impl<T: ?Sized> AsRef<T> for Arc<T> {
+ #[inline]
+ fn as_ref(&self) -> &T {
+ &**self
+ }
+}
+
+unsafe impl<T: ?Sized> StableDeref for Arc<T> {}
+unsafe impl<T: ?Sized> CloneStableDeref for Arc<T> {}
+
+#[cfg(feature = "servo")]
+impl<'de, T: Deserialize<'de>> Deserialize<'de> for Arc<T> {
+ fn deserialize<D>(deserializer: D) -> Result<Arc<T>, D::Error>
+ where
+ D: ::serde::de::Deserializer<'de>,
+ {
+ T::deserialize(deserializer).map(Arc::new)
+ }
+}
+
+#[cfg(feature = "servo")]
+impl<T: Serialize> Serialize for Arc<T> {
+ fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
+ where
+ S: ::serde::ser::Serializer,
+ {
+ (**self).serialize(serializer)
+ }
+}
+
+/// Structure to allow Arc-managing some fixed-sized data and a variably-sized
+/// slice in a single allocation.
+#[derive(Debug, Eq, PartialEq, PartialOrd)]
+#[repr(C)]
+pub struct HeaderSlice<H, T: ?Sized> {
+ /// The fixed-sized data.
+ pub header: H,
+
+ /// The dynamically-sized data.
+ pub slice: T,
+}
+
+#[inline(always)]
+fn divide_rounding_up(dividend: usize, divisor: usize) -> usize {
+ (dividend + divisor - 1) / divisor
+}
+
+impl<H, T> Arc<HeaderSlice<H, [T]>> {
+ /// Creates an Arc for a HeaderSlice using the given header struct and
+ /// iterator to generate the slice.
+ ///
+ /// `is_static` indicates whether to create a static Arc.
+ ///
+ /// `alloc` is used to get a pointer to the memory into which the
+ /// dynamically sized ArcInner<HeaderSlice<H, T>> value will be
+ /// written. If `is_static` is true, then `alloc` must return a
+ /// pointer into some static memory allocation. If it is false,
+ /// then `alloc` must return an allocation that can be dellocated
+ /// by calling Box::from_raw::<ArcInner<HeaderSlice<H, T>>> on it.
+ #[inline]
+ fn from_header_and_iter_alloc<F, I>(alloc: F, header: H, mut items: I, is_static: bool) -> Self
+ where
+ F: FnOnce(Layout) -> *mut u8,
+ I: Iterator<Item = T> + ExactSizeIterator,
+ {
+ assert_ne!(size_of::<T>(), 0, "Need to think about ZST");
+
+ let inner_align = align_of::<ArcInner<HeaderSlice<H, [T; 0]>>>();
+ debug_assert!(inner_align >= align_of::<T>());
+
+ // Compute the required size for the allocation.
+ let num_items = items.len();
+ let size = {
+ // Next, synthesize a totally garbage (but properly aligned) pointer
+ // to a sequence of T.
+ let fake_slice_ptr = inner_align as *const T;
+
+ // Convert that sequence to a fat pointer. The address component of
+ // the fat pointer will be garbage, but the length will be correct.
+ let fake_slice = unsafe { slice::from_raw_parts(fake_slice_ptr, num_items) };
+
+ // Pretend the garbage address points to our allocation target (with
+ // a trailing sequence of T), rather than just a sequence of T.
+ let fake_ptr = fake_slice as *const [T] as *const ArcInner<HeaderSlice<H, [T]>>;
+ let fake_ref: &ArcInner<HeaderSlice<H, [T]>> = unsafe { &*fake_ptr };
+
+ // Use size_of_val, which will combine static information about the
+ // type with the length from the fat pointer. The garbage address
+ // will not be used.
+ mem::size_of_val(fake_ref)
+ };
+
+ let ptr: *mut ArcInner<HeaderSlice<H, [T]>>;
+ unsafe {
+ // Allocate the buffer.
+ let layout = if inner_align <= align_of::<usize>() {
+ Layout::from_size_align_unchecked(size, align_of::<usize>())
+ } else if inner_align <= align_of::<u64>() {
+ // On 32-bit platforms <T> may have 8 byte alignment while usize
+ // has 4 byte aligment. Use u64 to avoid over-alignment.
+ // This branch will compile away in optimized builds.
+ Layout::from_size_align_unchecked(size, align_of::<u64>())
+ } else {
+ panic!("Over-aligned type not handled");
+ };
+
+ let buffer = alloc(layout);
+
+ // Synthesize the fat pointer. We do this by claiming we have a direct
+ // pointer to a [T], and then changing the type of the borrow. The key
+ // point here is that the length portion of the fat pointer applies
+ // only to the number of elements in the dynamically-sized portion of
+ // the type, so the value will be the same whether it points to a [T]
+ // or something else with a [T] as its last member.
+ let fake_slice: &mut [T] = slice::from_raw_parts_mut(buffer as *mut T, num_items);
+ ptr = fake_slice as *mut [T] as *mut ArcInner<HeaderSlice<H, [T]>>;
+
+ // Write the data.
+ //
+ // Note that any panics here (i.e. from the iterator) are safe, since
+ // we'll just leak the uninitialized memory.
+ let count = if is_static {
+ atomic::AtomicUsize::new(STATIC_REFCOUNT)
+ } else {
+ atomic::AtomicUsize::new(1)
+ };
+ ptr::write(&mut ((*ptr).count), count);
+ ptr::write(&mut ((*ptr).data.header), header);
+ if num_items != 0 {
+ let mut current: *mut T = &mut (*ptr).data.slice[0];
+ for _ in 0..num_items {
+ ptr::write(
+ current,
+ items
+ .next()
+ .expect("ExactSizeIterator over-reported length"),
+ );
+ current = current.offset(1);
+ }
+ // We should have consumed the buffer exactly, maybe accounting
+ // for some padding from the alignment.
+ debug_assert!(
+ (buffer.offset(size as isize) as usize - current as *mut u8 as usize) <
+ inner_align
+ );
+ }
+ assert!(
+ items.next().is_none(),
+ "ExactSizeIterator under-reported length"
+ );
+ }
+
+ #[cfg(feature = "gecko_refcount_logging")]
+ unsafe {
+ if !is_static {
+ // FIXME(emilio): Would be so amazing to have
+ // std::intrinsics::type_name() around.
+ NS_LogCtor(ptr as *mut _, b"ServoArc\0".as_ptr() as *const _, 8)
+ }
+ }
+
+ // Return the fat Arc.
+ assert_eq!(
+ size_of::<Self>(),
+ size_of::<usize>() * 2,
+ "The Arc will be fat"
+ );
+ unsafe {
+ Arc {
+ p: ptr::NonNull::new_unchecked(ptr),
+ phantom: PhantomData,
+ }
+ }
+ }
+
+ /// Creates an Arc for a HeaderSlice using the given header struct and
+ /// iterator to generate the slice. The resulting Arc will be fat.
+ #[inline]
+ pub fn from_header_and_iter<I>(header: H, items: I) -> Self
+ where
+ I: Iterator<Item = T> + ExactSizeIterator,
+ {
+ Arc::from_header_and_iter_alloc(
+ |layout| {
+ // align will only ever be align_of::<usize>() or align_of::<u64>()
+ let align = layout.align();
+ unsafe {
+ if align == mem::align_of::<usize>() {
+ Self::allocate_buffer::<usize>(layout.size())
+ } else {
+ assert_eq!(align, mem::align_of::<u64>());
+ Self::allocate_buffer::<u64>(layout.size())
+ }
+ }
+ },
+ header,
+ items,
+ /* is_static = */ false,
+ )
+ }
+
+ #[inline]
+ unsafe fn allocate_buffer<W>(size: usize) -> *mut u8 {
+ // We use Vec because the underlying allocation machinery isn't
+ // available in stable Rust. To avoid alignment issues, we allocate
+ // words rather than bytes, rounding up to the nearest word size.
+ let words_to_allocate = divide_rounding_up(size, mem::size_of::<W>());
+ let mut vec = Vec::<W>::with_capacity(words_to_allocate);
+ vec.set_len(words_to_allocate);
+ Box::into_raw(vec.into_boxed_slice()) as *mut W as *mut u8
+ }
+}
+
+/// Header data with an inline length. Consumers that use HeaderWithLength as the
+/// Header type in HeaderSlice can take advantage of ThinArc.
+#[derive(Debug, Eq, PartialEq, PartialOrd)]
+#[repr(C)]
+pub struct HeaderWithLength<H> {
+ /// The fixed-sized data.
+ pub header: H,
+
+ /// The slice length.
+ length: usize,
+}
+
+impl<H> HeaderWithLength<H> {
+ /// Creates a new HeaderWithLength.
+ pub fn new(header: H, length: usize) -> Self {
+ HeaderWithLength {
+ header: header,
+ length: length,
+ }
+ }
+}
+
+type HeaderSliceWithLength<H, T> = HeaderSlice<HeaderWithLength<H>, T>;
+
+/// A "thin" `Arc` containing dynamically sized data
+///
+/// This is functionally equivalent to Arc<(H, [T])>
+///
+/// When you create an `Arc` containing a dynamically sized type
+/// like `HeaderSlice<H, [T]>`, the `Arc` is represented on the stack
+/// as a "fat pointer", where the length of the slice is stored
+/// alongside the `Arc`'s pointer. In some situations you may wish to
+/// have a thin pointer instead, perhaps for FFI compatibility
+/// or space efficiency.
+///
+/// Note that we use `[T; 0]` in order to have the right alignment for `T`.
+///
+/// `ThinArc` solves this by storing the length in the allocation itself,
+/// via `HeaderSliceWithLength`.
+#[repr(C)]
+pub struct ThinArc<H, T> {
+ ptr: ptr::NonNull<ArcInner<HeaderSliceWithLength<H, [T; 0]>>>,
+ phantom: PhantomData<(H, T)>,
+}
+
+impl<H: fmt::Debug, T: fmt::Debug> fmt::Debug for ThinArc<H, T> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fmt::Debug::fmt(self.deref(), f)
+ }
+}
+
+unsafe impl<H: Sync + Send, T: Sync + Send> Send for ThinArc<H, T> {}
+unsafe impl<H: Sync + Send, T: Sync + Send> Sync for ThinArc<H, T> {}
+
+// Synthesize a fat pointer from a thin pointer.
+//
+// See the comment around the analogous operation in from_header_and_iter.
+fn thin_to_thick<H, T>(
+ thin: *mut ArcInner<HeaderSliceWithLength<H, [T; 0]>>,
+) -> *mut ArcInner<HeaderSliceWithLength<H, [T]>> {
+ let len = unsafe { (*thin).data.header.length };
+ let fake_slice: *mut [T] = unsafe { slice::from_raw_parts_mut(thin as *mut T, len) };
+
+ fake_slice as *mut ArcInner<HeaderSliceWithLength<H, [T]>>
+}
+
+impl<H, T> ThinArc<H, T> {
+ /// Temporarily converts |self| into a bonafide Arc and exposes it to the
+ /// provided callback. The refcount is not modified.
+ #[inline]
+ pub fn with_arc<F, U>(&self, f: F) -> U
+ where
+ F: FnOnce(&Arc<HeaderSliceWithLength<H, [T]>>) -> U,
+ {
+ // Synthesize transient Arc, which never touches the refcount of the ArcInner.
+ let transient = unsafe {
+ NoDrop::new(Arc {
+ p: ptr::NonNull::new_unchecked(thin_to_thick(self.ptr.as_ptr())),
+ phantom: PhantomData,
+ })
+ };
+
+ // Expose the transient Arc to the callback, which may clone it if it wants.
+ let result = f(&transient);
+
+ // Forget the transient Arc to leave the refcount untouched.
+ // XXXManishearth this can be removed when unions stabilize,
+ // since then NoDrop becomes zero overhead
+ mem::forget(transient);
+
+ // Forward the result.
+ result
+ }
+
+ /// Creates a `ThinArc` for a HeaderSlice using the given header struct and
+ /// iterator to generate the slice.
+ pub fn from_header_and_iter<I>(header: H, items: I) -> Self
+ where
+ I: Iterator<Item = T> + ExactSizeIterator,
+ {
+ let header = HeaderWithLength::new(header, items.len());
+ Arc::into_thin(Arc::from_header_and_iter(header, items))
+ }
+
+ /// Create a static `ThinArc` for a HeaderSlice using the given header
+ /// struct and iterator to generate the slice, placing it in the allocation
+ /// provided by the specified `alloc` function.
+ ///
+ /// `alloc` must return a pointer into a static allocation suitable for
+ /// storing data with the `Layout` passed into it. The pointer returned by
+ /// `alloc` will not be freed.
+ pub unsafe fn static_from_header_and_iter<F, I>(alloc: F, header: H, items: I) -> Self
+ where
+ F: FnOnce(Layout) -> *mut u8,
+ I: Iterator<Item = T> + ExactSizeIterator,
+ {
+ let header = HeaderWithLength::new(header, items.len());
+ Arc::into_thin(Arc::from_header_and_iter_alloc(
+ alloc, header, items, /* is_static = */ true,
+ ))
+ }
+
+ /// Returns the address on the heap of the ThinArc itself -- not the T
+ /// within it -- for memory reporting, and bindings.
+ #[inline]
+ pub fn ptr(&self) -> *const c_void {
+ self.ptr.as_ptr() as *const ArcInner<T> as *const c_void
+ }
+
+ /// If this is a static ThinArc, this returns null.
+ #[inline]
+ pub fn heap_ptr(&self) -> *const c_void {
+ let is_static =
+ ThinArc::with_arc(self, |a| a.inner().count.load(Relaxed) == STATIC_REFCOUNT);
+ if is_static {
+ ptr::null()
+ } else {
+ self.ptr()
+ }
+ }
+}
+
+impl<H, T> Deref for ThinArc<H, T> {
+ type Target = HeaderSliceWithLength<H, [T]>;
+
+ #[inline]
+ fn deref(&self) -> &Self::Target {
+ unsafe { &(*thin_to_thick(self.ptr.as_ptr())).data }
+ }
+}
+
+impl<H, T> Clone for ThinArc<H, T> {
+ #[inline]
+ fn clone(&self) -> Self {
+ ThinArc::with_arc(self, |a| Arc::into_thin(a.clone()))
+ }
+}
+
+impl<H, T> Drop for ThinArc<H, T> {
+ #[inline]
+ fn drop(&mut self) {
+ let _ = Arc::from_thin(ThinArc {
+ ptr: self.ptr,
+ phantom: PhantomData,
+ });
+ }
+}
+
+impl<H, T> Arc<HeaderSliceWithLength<H, [T]>> {
+ /// Converts an `Arc` into a `ThinArc`. This consumes the `Arc`, so the refcount
+ /// is not modified.
+ #[inline]
+ pub fn into_thin(a: Self) -> ThinArc<H, T> {
+ assert_eq!(
+ a.header.length,
+ a.slice.len(),
+ "Length needs to be correct for ThinArc to work"
+ );
+ let fat_ptr: *mut ArcInner<HeaderSliceWithLength<H, [T]>> = a.ptr();
+ mem::forget(a);
+ let thin_ptr = fat_ptr as *mut [usize] as *mut usize;
+ ThinArc {
+ ptr: unsafe {
+ ptr::NonNull::new_unchecked(
+ thin_ptr as *mut ArcInner<HeaderSliceWithLength<H, [T; 0]>>,
+ )
+ },
+ phantom: PhantomData,
+ }
+ }
+
+ /// Converts a `ThinArc` into an `Arc`. This consumes the `ThinArc`, so the refcount
+ /// is not modified.
+ #[inline]
+ pub fn from_thin(a: ThinArc<H, T>) -> Self {
+ let ptr = thin_to_thick(a.ptr.as_ptr());
+ mem::forget(a);
+ unsafe {
+ Arc {
+ p: ptr::NonNull::new_unchecked(ptr),
+ phantom: PhantomData,
+ }
+ }
+ }
+}
+
+impl<H: PartialEq, T: PartialEq> PartialEq for ThinArc<H, T> {
+ #[inline]
+ fn eq(&self, other: &ThinArc<H, T>) -> bool {
+ ThinArc::with_arc(self, |a| ThinArc::with_arc(other, |b| *a == *b))
+ }
+}
+
+impl<H: Eq, T: Eq> Eq for ThinArc<H, T> {}
+
+/// An `Arc`, except it holds a pointer to the T instead of to the
+/// entire ArcInner. This struct is FFI-compatible.
+///
+/// ```text
+/// Arc<T> RawOffsetArc<T>
+/// | |
+/// v v
+/// ---------------------
+/// | RefCount | T (data) | [ArcInner<T>]
+/// ---------------------
+/// ```
+///
+/// This means that this is a direct pointer to
+/// its contained data (and can be read from by both C++ and Rust),
+/// but we can also convert it to a "regular" Arc<T> by removing the offset.
+///
+/// This is very useful if you have an Arc-containing struct shared between Rust and C++,
+/// and wish for C++ to be able to read the data behind the `Arc` without incurring
+/// an FFI call overhead.
+#[derive(Eq)]
+#[repr(C)]
+pub struct RawOffsetArc<T> {
+ ptr: ptr::NonNull<T>,
+}
+
+unsafe impl<T: Sync + Send> Send for RawOffsetArc<T> {}
+unsafe impl<T: Sync + Send> Sync for RawOffsetArc<T> {}
+
+impl<T> Deref for RawOffsetArc<T> {
+ type Target = T;
+ fn deref(&self) -> &Self::Target {
+ unsafe { &*self.ptr.as_ptr() }
+ }
+}
+
+impl<T> Clone for RawOffsetArc<T> {
+ #[inline]
+ fn clone(&self) -> Self {
+ Arc::into_raw_offset(self.clone_arc())
+ }
+}
+
+impl<T> Drop for RawOffsetArc<T> {
+ fn drop(&mut self) {
+ let _ = Arc::from_raw_offset(RawOffsetArc {
+ ptr: self.ptr.clone(),
+ });
+ }
+}
+
+impl<T: fmt::Debug> fmt::Debug for RawOffsetArc<T> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fmt::Debug::fmt(&**self, f)
+ }
+}
+
+impl<T: PartialEq> PartialEq for RawOffsetArc<T> {
+ fn eq(&self, other: &RawOffsetArc<T>) -> bool {
+ *(*self) == *(*other)
+ }
+
+ fn ne(&self, other: &RawOffsetArc<T>) -> bool {
+ *(*self) != *(*other)
+ }
+}
+
+impl<T> RawOffsetArc<T> {
+ /// Temporarily converts |self| into a bonafide Arc and exposes it to the
+ /// provided callback. The refcount is not modified.
+ #[inline]
+ pub fn with_arc<F, U>(&self, f: F) -> U
+ where
+ F: FnOnce(&Arc<T>) -> U,
+ {
+ // Synthesize transient Arc, which never touches the refcount of the ArcInner.
+ let transient = unsafe { NoDrop::new(Arc::from_raw(self.ptr.as_ptr())) };
+
+ // Expose the transient Arc to the callback, which may clone it if it wants.
+ let result = f(&transient);
+
+ // Forget the transient Arc to leave the refcount untouched.
+ // XXXManishearth this can be removed when unions stabilize,
+ // since then NoDrop becomes zero overhead
+ mem::forget(transient);
+
+ // Forward the result.
+ result
+ }
+
+ /// If uniquely owned, provide a mutable reference
+ /// Else create a copy, and mutate that
+ ///
+ /// This is functionally the same thing as `Arc::make_mut`
+ #[inline]
+ pub fn make_mut(&mut self) -> &mut T
+ where
+ T: Clone,
+ {
+ unsafe {
+ // extract the RawOffsetArc as an owned variable
+ let this = ptr::read(self);
+ // treat it as a real Arc
+ let mut arc = Arc::from_raw_offset(this);
+ // obtain the mutable reference. Cast away the lifetime
+ // This may mutate `arc`
+ let ret = Arc::make_mut(&mut arc) as *mut _;
+ // Store the possibly-mutated arc back inside, after converting
+ // it to a RawOffsetArc again
+ ptr::write(self, Arc::into_raw_offset(arc));
+ &mut *ret
+ }
+ }
+
+ /// Clone it as an `Arc`
+ #[inline]
+ pub fn clone_arc(&self) -> Arc<T> {
+ RawOffsetArc::with_arc(self, |a| a.clone())
+ }
+
+ /// Produce a pointer to the data that can be converted back
+ /// to an `Arc`
+ #[inline]
+ pub fn borrow_arc<'a>(&'a self) -> ArcBorrow<'a, T> {
+ ArcBorrow(&**self)
+ }
+}
+
+impl<T> Arc<T> {
+ /// Converts an `Arc` into a `RawOffsetArc`. This consumes the `Arc`, so the refcount
+ /// is not modified.
+ #[inline]
+ pub fn into_raw_offset(a: Self) -> RawOffsetArc<T> {
+ unsafe {
+ RawOffsetArc {
+ ptr: ptr::NonNull::new_unchecked(Arc::into_raw(a) as *mut T),
+ }
+ }
+ }
+
+ /// Converts a `RawOffsetArc` into an `Arc`. This consumes the `RawOffsetArc`, so the refcount
+ /// is not modified.
+ #[inline]
+ pub fn from_raw_offset(a: RawOffsetArc<T>) -> Self {
+ let ptr = a.ptr.as_ptr();
+ mem::forget(a);
+ unsafe { Arc::from_raw(ptr) }
+ }
+}
+
+/// A "borrowed `Arc`". This is a pointer to
+/// a T that is known to have been allocated within an
+/// `Arc`.
+///
+/// This is equivalent in guarantees to `&Arc<T>`, however it is
+/// a bit more flexible. To obtain an `&Arc<T>` you must have
+/// an `Arc<T>` instance somewhere pinned down until we're done with it.
+/// It's also a direct pointer to `T`, so using this involves less pointer-chasing
+///
+/// However, C++ code may hand us refcounted things as pointers to T directly,
+/// so we have to conjure up a temporary `Arc` on the stack each time. The
+/// same happens for when the object is managed by a `RawOffsetArc`.
+///
+/// `ArcBorrow` lets us deal with borrows of known-refcounted objects
+/// without needing to worry about where the `Arc<T>` is.
+#[derive(Debug, Eq, PartialEq)]
+pub struct ArcBorrow<'a, T: 'a>(&'a T);
+
+impl<'a, T> Copy for ArcBorrow<'a, T> {}
+impl<'a, T> Clone for ArcBorrow<'a, T> {
+ #[inline]
+ fn clone(&self) -> Self {
+ *self
+ }
+}
+
+impl<'a, T> ArcBorrow<'a, T> {
+ /// Clone this as an `Arc<T>`. This bumps the refcount.
+ #[inline]
+ pub fn clone_arc(&self) -> Arc<T> {
+ let arc = unsafe { Arc::from_raw(self.0) };
+ // addref it!
+ mem::forget(arc.clone());
+ arc
+ }
+
+ /// For constructing from a reference known to be Arc-backed,
+ /// e.g. if we obtain such a reference over FFI
+ #[inline]
+ pub unsafe fn from_ref(r: &'a T) -> Self {
+ ArcBorrow(r)
+ }
+
+ /// Compare two `ArcBorrow`s via pointer equality. Will only return
+ /// true if they come from the same allocation
+ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
+ this.0 as *const T == other.0 as *const T
+ }
+
+ /// Temporarily converts |self| into a bonafide Arc and exposes it to the
+ /// provided callback. The refcount is not modified.
+ #[inline]
+ pub fn with_arc<F, U>(&self, f: F) -> U
+ where
+ F: FnOnce(&Arc<T>) -> U,
+ T: 'static,
+ {
+ // Synthesize transient Arc, which never touches the refcount.
+ let transient = unsafe { NoDrop::new(Arc::from_raw(self.0)) };
+
+ // Expose the transient Arc to the callback, which may clone it if it wants.
+ let result = f(&transient);
+
+ // Forget the transient Arc to leave the refcount untouched.
+ // XXXManishearth this can be removed when unions stabilize,
+ // since then NoDrop becomes zero overhead
+ mem::forget(transient);
+
+ // Forward the result.
+ result
+ }
+
+ /// Similar to deref, but uses the lifetime |a| rather than the lifetime of
+ /// self, which is incompatible with the signature of the Deref trait.
+ #[inline]
+ pub fn get(&self) -> &'a T {
+ self.0
+ }
+}
+
+impl<'a, T> Deref for ArcBorrow<'a, T> {
+ type Target = T;
+
+ #[inline]
+ fn deref(&self) -> &T {
+ self.0
+ }
+}
+
+/// A tagged union that can represent `Arc<A>` or `Arc<B>` while only consuming a
+/// single word. The type is also `NonNull`, and thus can be stored in an Option
+/// without increasing size.
+///
+/// This is functionally equivalent to
+/// `enum ArcUnion<A, B> { First(Arc<A>), Second(Arc<B>)` but only takes up
+/// up a single word of stack space.
+///
+/// This could probably be extended to support four types if necessary.
+pub struct ArcUnion<A, B> {
+ p: ptr::NonNull<()>,
+ phantom_a: PhantomData<A>,
+ phantom_b: PhantomData<B>,
+}
+
+unsafe impl<A: Sync + Send, B: Send + Sync> Send for ArcUnion<A, B> {}
+unsafe impl<A: Sync + Send, B: Send + Sync> Sync for ArcUnion<A, B> {}
+
+impl<A: PartialEq, B: PartialEq> PartialEq for ArcUnion<A, B> {
+ fn eq(&self, other: &Self) -> bool {
+ use crate::ArcUnionBorrow::*;
+ match (self.borrow(), other.borrow()) {
+ (First(x), First(y)) => x == y,
+ (Second(x), Second(y)) => x == y,
+ (_, _) => false,
+ }
+ }
+}
+
+/// This represents a borrow of an `ArcUnion`.
+#[derive(Debug)]
+pub enum ArcUnionBorrow<'a, A: 'a, B: 'a> {
+ First(ArcBorrow<'a, A>),
+ Second(ArcBorrow<'a, B>),
+}
+
+impl<A, B> ArcUnion<A, B> {
+ unsafe fn new(ptr: *mut ()) -> Self {
+ ArcUnion {
+ p: ptr::NonNull::new_unchecked(ptr),
+ phantom_a: PhantomData,
+ phantom_b: PhantomData,
+ }
+ }
+
+ /// Returns true if the two values are pointer-equal.
+ #[inline]
+ pub fn ptr_eq(this: &Self, other: &Self) -> bool {
+ this.p == other.p
+ }
+
+ #[inline]
+ pub fn ptr(&self) -> ptr::NonNull<()> {
+ self.p
+ }
+
+ /// Returns an enum representing a borrow of either A or B.
+ #[inline]
+ pub fn borrow(&self) -> ArcUnionBorrow<A, B> {
+ if self.is_first() {
+ let ptr = self.p.as_ptr() as *const A;
+ let borrow = unsafe { ArcBorrow::from_ref(&*ptr) };
+ ArcUnionBorrow::First(borrow)
+ } else {
+ let ptr = ((self.p.as_ptr() as usize) & !0x1) as *const B;
+ let borrow = unsafe { ArcBorrow::from_ref(&*ptr) };
+ ArcUnionBorrow::Second(borrow)
+ }
+ }
+
+ /// Creates an `ArcUnion` from an instance of the first type.
+ pub fn from_first(other: Arc<A>) -> Self {
+ unsafe { Self::new(Arc::into_raw(other) as *mut _) }
+ }
+
+ /// Creates an `ArcUnion` from an instance of the second type.
+ pub fn from_second(other: Arc<B>) -> Self {
+ unsafe { Self::new(((Arc::into_raw(other) as usize) | 0x1) as *mut _) }
+ }
+
+ /// Returns true if this `ArcUnion` contains the first type.
+ pub fn is_first(&self) -> bool {
+ self.p.as_ptr() as usize & 0x1 == 0
+ }
+
+ /// Returns true if this `ArcUnion` contains the second type.
+ pub fn is_second(&self) -> bool {
+ !self.is_first()
+ }
+
+ /// Returns a borrow of the first type if applicable, otherwise `None`.
+ pub fn as_first(&self) -> Option<ArcBorrow<A>> {
+ match self.borrow() {
+ ArcUnionBorrow::First(x) => Some(x),
+ ArcUnionBorrow::Second(_) => None,
+ }
+ }
+
+ /// Returns a borrow of the second type if applicable, otherwise None.
+ pub fn as_second(&self) -> Option<ArcBorrow<B>> {
+ match self.borrow() {
+ ArcUnionBorrow::First(_) => None,
+ ArcUnionBorrow::Second(x) => Some(x),
+ }
+ }
+}
+
+impl<A, B> Clone for ArcUnion<A, B> {
+ fn clone(&self) -> Self {
+ match self.borrow() {
+ ArcUnionBorrow::First(x) => ArcUnion::from_first(x.clone_arc()),
+ ArcUnionBorrow::Second(x) => ArcUnion::from_second(x.clone_arc()),
+ }
+ }
+}
+
+impl<A, B> Drop for ArcUnion<A, B> {
+ fn drop(&mut self) {
+ match self.borrow() {
+ ArcUnionBorrow::First(x) => unsafe {
+ let _ = Arc::from_raw(&*x);
+ },
+ ArcUnionBorrow::Second(x) => unsafe {
+ let _ = Arc::from_raw(&*x);
+ },
+ }
+ }
+}
+
+impl<A: fmt::Debug, B: fmt::Debug> fmt::Debug for ArcUnion<A, B> {
+ fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+ fmt::Debug::fmt(&self.borrow(), f)
+ }
+}
+
+#[cfg(test)]
+mod tests {
+ use super::{Arc, HeaderWithLength, ThinArc};
+ use std::clone::Clone;
+ use std::ops::Drop;
+ use std::sync::atomic;
+ use std::sync::atomic::Ordering::{Acquire, SeqCst};
+
+ #[derive(PartialEq)]
+ struct Canary(*mut atomic::AtomicUsize);
+
+ impl Drop for Canary {
+ fn drop(&mut self) {
+ unsafe {
+ (*self.0).fetch_add(1, SeqCst);
+ }
+ }
+ }
+
+ #[test]
+ fn empty_thin() {
+ let header = HeaderWithLength::new(100u32, 0);
+ let x = Arc::from_header_and_iter(header, std::iter::empty::<i32>());
+ let y = Arc::into_thin(x.clone());
+ assert_eq!(y.header.header, 100);
+ assert!(y.slice.is_empty());
+ assert_eq!(x.header.header, 100);
+ assert!(x.slice.is_empty());
+ }
+
+ #[test]
+ fn thin_assert_padding() {
+ #[derive(Clone, Default)]
+ #[repr(C)]
+ struct Padded {
+ i: u16,
+ }
+
+ // The header will have more alignment than `Padded`
+ let header = HeaderWithLength::new(0i32, 2);
+ let items = vec![Padded { i: 0xdead }, Padded { i: 0xbeef }];
+ let a = ThinArc::from_header_and_iter(header, items.into_iter());
+ assert_eq!(a.slice.len(), 2);
+ assert_eq!(a.slice[0].i, 0xdead);
+ assert_eq!(a.slice[1].i, 0xbeef);
+ }
+
+ #[test]
+ fn slices_and_thin() {
+ let mut canary = atomic::AtomicUsize::new(0);
+ let c = Canary(&mut canary as *mut atomic::AtomicUsize);
+ let v = vec![5, 6];
+ let header = HeaderWithLength::new(c, v.len());
+ {
+ let x = Arc::into_thin(Arc::from_header_and_iter(header, v.into_iter()));
+ let y = ThinArc::with_arc(&x, |q| q.clone());
+ let _ = y.clone();
+ let _ = x == x;
+ Arc::from_thin(x.clone());
+ }
+ assert_eq!(canary.load(Acquire), 1);
+ }
+}
diff --git a/servo_crates/to_shmem/Cargo.toml b/servo_crates/to_shmem/Cargo.toml
new file mode 100644
index 00000000..71426507
--- /dev/null
+++ b/servo_crates/to_shmem/Cargo.toml
@@ -0,0 +1,22 @@
+[package]
+name = "to_shmem"
+version = "0.0.1"
+authors = ["The Servo Project Developers"]
+license = "MPL-2.0"
+publish = false
+
+[lib]
+name = "to_shmem"
+path = "lib.rs"
+
+[features]
+servo = ["cssparser/serde", "string_cache"]
+gecko = []
+
+[dependencies]
+cssparser = "0.27.1"
+servo_arc = { path = "../servo_arc" }
+smallbitvec = "2.1.1"
+smallvec = "0.6.6"
+string_cache = { version = "0.8", optional = true }
+thin-slice = "0.1.0"
diff --git a/servo_crates/to_shmem/lib.rs b/servo_crates/to_shmem/lib.rs
new file mode 100644
index 00000000..22b86087
--- /dev/null
+++ b/servo_crates/to_shmem/lib.rs
@@ -0,0 +1,543 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+//! Trait for cloning data into a shared memory buffer.
+//!
+//! This module contains the SharedMemoryBuilder type and ToShmem trait.
+//!
+//! We put them here (and not in style_traits) so that we can derive ToShmem
+//! from the selectors and style crates.
+
+#![crate_name = "to_shmem"]
+#![crate_type = "rlib"]
+
+extern crate cssparser;
+extern crate servo_arc;
+extern crate smallbitvec;
+extern crate smallvec;
+#[cfg(feature = "string_cache")]
+extern crate string_cache;
+extern crate thin_slice;
+
+use servo_arc::{Arc, ThinArc};
+use smallbitvec::{InternalStorage, SmallBitVec};
+use smallvec::{Array, SmallVec};
+use std::alloc::Layout;
+#[cfg(debug_assertions)]
+use std::any::TypeId;
+#[cfg(debug_assertions)]
+use std::collections::HashSet;
+use std::ffi::CString;
+use std::isize;
+use std::marker::PhantomData;
+use std::mem::{self, ManuallyDrop};
+use std::num::Wrapping;
+use std::ops::Range;
+use std::os::raw::c_char;
+#[cfg(debug_assertions)]
+use std::os::raw::c_void;
+use std::ptr::{self, NonNull};
+use std::slice;
+use std::str;
+use thin_slice::ThinBoxedSlice;
+
+// Various pointer arithmetic functions in this file can be replaced with
+// functions on `Layout` once they have stabilized:
+//
+// https://github.com/rust-lang/rust/issues/55724
+
+/// A builder object that transforms and copies values into a fixed size buffer.
+pub struct SharedMemoryBuilder {
+ /// The buffer into which values will be copied.
+ buffer: *mut u8,
+ /// The size of the buffer.
+ capacity: usize,
+ /// The current position in the buffer, where the next value will be written
+ /// at.
+ index: usize,
+ /// Pointers to every sharable value that we store in the shared memory
+ /// buffer. We use this to assert against encountering the same value
+ /// twice, e.g. through another Arc reference, so that we don't
+ /// inadvertently store duplicate copies of values.
+ #[cfg(debug_assertions)]
+ shared_values: HashSet<*const c_void>,
+ /// Types of values that we may duplicate in the shared memory buffer when
+ /// there are shared references to them, such as in Arcs.
+ #[cfg(debug_assertions)]
+ allowed_duplication_types: HashSet<TypeId>,
+}
+
+/// Amount of padding needed after `size` bytes to ensure that the following
+/// address will satisfy `align`.
+fn padding_needed_for(size: usize, align: usize) -> usize {
+ padded_size(size, align).wrapping_sub(size)
+}
+
+/// Rounds up `size` so that the following address will satisfy `align`.
+fn padded_size(size: usize, align: usize) -> usize {
+ size.wrapping_add(align).wrapping_sub(1) & !align.wrapping_sub(1)
+}
+
+impl SharedMemoryBuilder {
+ /// Creates a new SharedMemoryBuilder using the specified buffer.
+ pub unsafe fn new(buffer: *mut u8, capacity: usize) -> SharedMemoryBuilder {
+ SharedMemoryBuilder {
+ buffer,
+ capacity,
+ index: 0,
+ #[cfg(debug_assertions)]
+ shared_values: HashSet::new(),
+ #[cfg(debug_assertions)]
+ allowed_duplication_types: HashSet::new(),
+ }
+ }
+
+ /// Notes a type as being allowed for duplication when being copied to the
+ /// shared memory buffer, such as Arcs referencing the same value.
+ #[inline]
+ pub fn add_allowed_duplication_type<T: 'static>(&mut self) {
+ #[cfg(debug_assertions)]
+ self.allowed_duplication_types.insert(TypeId::of::<T>());
+ }
+
+ /// Returns the number of bytes currently used in the buffer.
+ #[inline]
+ pub fn len(&self) -> usize {
+ self.index
+ }
+
+ /// Writes a value into the shared memory buffer and returns a pointer to
+ /// it in the buffer.
+ ///
+ /// The value is cloned and converted into a form suitable for placing into
+ /// a shared memory buffer by calling ToShmem::to_shmem on it.
+ ///
+ /// Panics if there is insufficient space in the buffer.
+ pub fn write<T: ToShmem>(&mut self, value: &T) -> *mut T {
+ // Reserve space for the value.
+ let dest: *mut T = self.alloc_value();
+
+ // Make a clone of the value with all of its heap allocations
+ // placed in the shared memory buffer.
+ let value = value.to_shmem(self);
+
+ unsafe {
+ // Copy the value into the buffer.
+ ptr::write(dest, ManuallyDrop::into_inner(value));
+ }
+
+ // Return a pointer to the shared value.
+ dest
+ }
+
+ /// Reserves space in the shared memory buffer to fit a value of type T,
+ /// and returns a pointer to that reserved space.
+ ///
+ /// Panics if there is insufficient space in the buffer.
+ pub fn alloc_value<T>(&mut self) -> *mut T {
+ self.alloc(Layout::new::<T>())
+ }
+
+ /// Reserves space in the shared memory buffer to fit an array of values of
+ /// type T, and returns a pointer to that reserved space.
+ ///
+ /// Panics if there is insufficient space in the buffer.
+ pub fn alloc_array<T>(&mut self, len: usize) -> *mut T {
+ if len == 0 {
+ return NonNull::dangling().as_ptr();
+ }
+
+ let size = mem::size_of::<T>();
+ let align = mem::align_of::<T>();
+
+ self.alloc(Layout::from_size_align(padded_size(size, align) * len, align).unwrap())
+ }
+
+ /// Reserves space in the shared memory buffer that conforms to the
+ /// specified layout, and returns a pointer to that reserved space.
+ ///
+ /// Panics if there is insufficient space in the buffer.
+ pub fn alloc<T>(&mut self, layout: Layout) -> *mut T {
+ // Amount of padding to align the value.
+ //
+ // The addition can't overflow, since self.index <= self.capacity, and
+ // for us to have successfully allocated the buffer, `buffer + capacity`
+ // can't overflow.
+ let padding = padding_needed_for(self.buffer as usize + self.index, layout.align());
+
+ // Reserve space for the padding.
+ let start = self.index.checked_add(padding).unwrap();
+ assert!(start <= std::isize::MAX as usize); // for the cast below
+
+ // Reserve space for the value.
+ let end = start.checked_add(layout.size()).unwrap();
+ assert!(end <= self.capacity);
+
+ self.index = end;
+ unsafe { self.buffer.offset(start as isize) as *mut T }
+ }
+}
+
+/// A type that can be copied into a SharedMemoryBuilder.
+pub trait ToShmem: Sized {
+ /// Clones this value into a form suitable for writing into a
+ /// SharedMemoryBuilder.
+ ///
+ /// If this value owns any heap allocations, they should be written into
+ /// `builder` so that the return value of this function can point to the
+ /// copy in the shared memory buffer.
+ ///
+ /// The return type is wrapped in ManuallyDrop to make it harder to
+ /// accidentally invoke the destructor of the value that is produced.
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self>;
+}
+
+#[macro_export]
+macro_rules! impl_trivial_to_shmem {
+ ($($ty:ty),*) => {
+ $(
+ impl $crate::ToShmem for $ty {
+ fn to_shmem(
+ &self,
+ _builder: &mut $crate::SharedMemoryBuilder,
+ ) -> ::std::mem::ManuallyDrop<Self> {
+ ::std::mem::ManuallyDrop::new(*self)
+ }
+ }
+ )*
+ };
+}
+
+impl_trivial_to_shmem!(
+ (),
+ bool,
+ f32,
+ f64,
+ i8,
+ i16,
+ i32,
+ i64,
+ u8,
+ u16,
+ u32,
+ u64,
+ isize,
+ usize
+);
+
+impl_trivial_to_shmem!(cssparser::RGBA);
+impl_trivial_to_shmem!(cssparser::SourceLocation);
+impl_trivial_to_shmem!(cssparser::TokenSerializationType);
+
+impl<T> ToShmem for PhantomData<T> {
+ fn to_shmem(&self, _builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ ManuallyDrop::new(*self)
+ }
+}
+
+impl<T: ToShmem> ToShmem for Range<T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ ManuallyDrop::new(Range {
+ start: ManuallyDrop::into_inner(self.start.to_shmem(builder)),
+ end: ManuallyDrop::into_inner(self.end.to_shmem(builder)),
+ })
+ }
+}
+
+impl ToShmem for cssparser::UnicodeRange {
+ fn to_shmem(&self, _builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ ManuallyDrop::new(cssparser::UnicodeRange {
+ start: self.start,
+ end: self.end,
+ })
+ }
+}
+
+impl<T: ToShmem, U: ToShmem> ToShmem for (T, U) {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ ManuallyDrop::new((
+ ManuallyDrop::into_inner(self.0.to_shmem(builder)),
+ ManuallyDrop::into_inner(self.1.to_shmem(builder)),
+ ))
+ }
+}
+
+impl<T: ToShmem> ToShmem for Wrapping<T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ ManuallyDrop::new(Wrapping(ManuallyDrop::into_inner(self.0.to_shmem(builder))))
+ }
+}
+
+impl<T: ToShmem> ToShmem for Box<T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ // Reserve space for the boxed value.
+ let dest: *mut T = builder.alloc_value();
+
+ // Make a clone of the boxed value with all of its heap allocations
+ // placed in the shared memory buffer.
+ let value = (**self).to_shmem(builder);
+
+ unsafe {
+ // Copy the value into the buffer.
+ ptr::write(dest, ManuallyDrop::into_inner(value));
+
+ ManuallyDrop::new(Box::from_raw(dest))
+ }
+ }
+}
+
+/// Converts all the items in `src` into shared memory form, writes them into
+/// the specified buffer, and returns a pointer to the slice.
+unsafe fn to_shmem_slice_ptr<'a, T, I>(
+ src: I,
+ dest: *mut T,
+ builder: &mut SharedMemoryBuilder,
+) -> *mut [T]
+where
+ T: 'a + ToShmem,
+ I: ExactSizeIterator<Item = &'a T>,
+{
+ let dest = slice::from_raw_parts_mut(dest, src.len());
+
+ // Make a clone of each element from the iterator with its own heap
+ // allocations placed in the buffer, and copy that clone into the buffer.
+ for (src, dest) in src.zip(dest.iter_mut()) {
+ ptr::write(dest, ManuallyDrop::into_inner(src.to_shmem(builder)));
+ }
+
+ dest
+}
+
+/// Writes all the items in `src` into a slice in the shared memory buffer and
+/// returns a pointer to the slice.
+pub unsafe fn to_shmem_slice<'a, T, I>(src: I, builder: &mut SharedMemoryBuilder) -> *mut [T]
+where
+ T: 'a + ToShmem,
+ I: ExactSizeIterator<Item = &'a T>,
+{
+ let dest = builder.alloc_array(src.len());
+ to_shmem_slice_ptr(src, dest, builder)
+}
+
+impl<T: ToShmem> ToShmem for Box<[T]> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ unsafe {
+ let dest = to_shmem_slice(self.iter(), builder);
+ ManuallyDrop::new(Box::from_raw(dest))
+ }
+ }
+}
+
+impl<T: ToShmem> ToShmem for ThinBoxedSlice<T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ // We could support this if we needed but in practice we will never
+ // need to handle such big ThinBoxedSlices.
+ assert!(
+ self.spilled_storage().is_none(),
+ "ToShmem failed for ThinBoxedSlice: too many entries ({})",
+ self.len(),
+ );
+
+ unsafe {
+ let dest = to_shmem_slice(self.iter(), builder);
+ ManuallyDrop::new(ThinBoxedSlice::from_raw(dest))
+ }
+ }
+}
+
+impl ToShmem for Box<str> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ // Reserve space for the string bytes.
+ let dest: *mut u8 = builder.alloc_array(self.len());
+
+ unsafe {
+ // Copy the value into the buffer.
+ ptr::copy(self.as_ptr(), dest, self.len());
+
+ ManuallyDrop::new(Box::from_raw(str::from_utf8_unchecked_mut(
+ slice::from_raw_parts_mut(dest, self.len()),
+ )))
+ }
+ }
+}
+
+impl ToShmem for String {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ // Reserve space for the string bytes.
+ let dest: *mut u8 = builder.alloc_array(self.len());
+
+ unsafe {
+ // Copy the value into the buffer.
+ ptr::copy(self.as_ptr(), dest, self.len());
+
+ ManuallyDrop::new(String::from_raw_parts(dest, self.len(), self.len()))
+ }
+ }
+}
+
+impl ToShmem for CString {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ let len = self.as_bytes_with_nul().len();
+
+ // Reserve space for the string bytes.
+ let dest: *mut c_char = builder.alloc_array(len);
+
+ unsafe {
+ // Copy the value into the buffer.
+ ptr::copy(self.as_ptr(), dest, len);
+
+ ManuallyDrop::new(CString::from_raw(dest))
+ }
+ }
+}
+
+impl<T: ToShmem> ToShmem for Vec<T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ unsafe {
+ let dest = to_shmem_slice(self.iter(), builder) as *mut T;
+ let dest_vec = Vec::from_raw_parts(dest, self.len(), self.len());
+ ManuallyDrop::new(dest_vec)
+ }
+ }
+}
+
+impl<T: ToShmem, A: Array<Item = T>> ToShmem for SmallVec<A> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ let dest_vec = unsafe {
+ if self.spilled() {
+ // Place the items in a separate allocation in the shared memory
+ // buffer.
+ let dest = to_shmem_slice(self.iter(), builder) as *mut T;
+ SmallVec::from_raw_parts(dest, self.len(), self.len())
+ } else {
+ // Place the items inline.
+ let mut s = SmallVec::new();
+ to_shmem_slice_ptr(self.iter(), s.as_mut_ptr(), builder);
+ s.set_len(self.len());
+ s
+ }
+ };
+
+ ManuallyDrop::new(dest_vec)
+ }
+}
+
+impl<T: ToShmem> ToShmem for Option<T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ ManuallyDrop::new(
+ self.as_ref()
+ .map(|v| ManuallyDrop::into_inner(v.to_shmem(builder))),
+ )
+ }
+}
+
+impl<T: 'static + ToShmem> ToShmem for Arc<T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ // Assert that we don't encounter any shared references to values we
+ // don't expect. Those we expect are those noted by calling
+ // add_allowed_duplication_type, and should be types where we're fine
+ // with duplicating any shared references in the shared memory buffer.
+ //
+ // Unfortunately there's no good way to print out the exact type of T
+ // in the assertion message.
+ #[cfg(debug_assertions)]
+ assert!(
+ !builder.shared_values.contains(&self.heap_ptr()) ||
+ builder
+ .allowed_duplication_types
+ .contains(&TypeId::of::<T>()),
+ "ToShmem failed for Arc<T>: encountered a value of type T with multiple references \
+ and which has not been explicitly allowed with an add_allowed_duplication_type call",
+ );
+
+ // Make a clone of the Arc-owned value with all of its heap allocations
+ // placed in the shared memory buffer.
+ let value = (**self).to_shmem(builder);
+
+ // Create a new Arc with the shared value and have it place its
+ // ArcInner in the shared memory buffer.
+ unsafe {
+ let static_arc = Arc::new_static(
+ |layout| builder.alloc(layout),
+ ManuallyDrop::into_inner(value),
+ );
+
+ #[cfg(debug_assertions)]
+ builder.shared_values.insert(self.heap_ptr());
+
+ ManuallyDrop::new(static_arc)
+ }
+ }
+}
+
+impl<H: 'static + ToShmem, T: 'static + ToShmem> ToShmem for ThinArc<H, T> {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ // We don't currently have any shared ThinArc values in stylesheets,
+ // so don't support them for now.
+ #[cfg(debug_assertions)]
+ assert!(
+ !builder.shared_values.contains(&self.heap_ptr()),
+ "ToShmem failed for ThinArc<T>: encountered a value with multiple references, which \
+ is not currently supported",
+ );
+
+ // Make a clone of the Arc-owned header and slice values with all of
+ // their heap allocations placed in the shared memory buffer.
+ let header = self.header.header.to_shmem(builder);
+ let values: Vec<ManuallyDrop<T>> = self.slice.iter().map(|v| v.to_shmem(builder)).collect();
+
+ // Create a new ThinArc with the shared value and have it place
+ // its ArcInner in the shared memory buffer.
+ unsafe {
+ let static_arc = ThinArc::static_from_header_and_iter(
+ |layout| builder.alloc(layout),
+ ManuallyDrop::into_inner(header),
+ values.into_iter().map(ManuallyDrop::into_inner),
+ );
+
+ #[cfg(debug_assertions)]
+ builder.shared_values.insert(self.heap_ptr());
+
+ ManuallyDrop::new(static_arc)
+ }
+ }
+}
+
+impl ToShmem for SmallBitVec {
+ fn to_shmem(&self, builder: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ let storage = match self.clone().into_storage() {
+ InternalStorage::Spilled(vs) => {
+ // Reserve space for the boxed slice values.
+ let len = vs.len();
+ let dest: *mut usize = builder.alloc_array(len);
+
+ unsafe {
+ // Copy the value into the buffer.
+ let src = vs.as_ptr() as *const usize;
+ ptr::copy(src, dest, len);
+
+ let dest_slice =
+ Box::from_raw(slice::from_raw_parts_mut(dest, len) as *mut [usize]);
+ InternalStorage::Spilled(dest_slice)
+ }
+ },
+ InternalStorage::Inline(x) => InternalStorage::Inline(x),
+ };
+ ManuallyDrop::new(unsafe { SmallBitVec::from_storage(storage) })
+ }
+}
+
+#[cfg(feature = "string_cache")]
+impl<Static: string_cache::StaticAtomSet> ToShmem for string_cache::Atom<Static> {
+ fn to_shmem(&self, _: &mut SharedMemoryBuilder) -> ManuallyDrop<Self> {
+ // NOTE(emilio): In practice, this can be implemented trivially if
+ // string_cache could expose the implementation detail of static atoms
+ // being an index into the static table (and panicking in the
+ // non-static, non-inline cases).
+ unimplemented!(
+ "If servo wants to share stylesheets across processes, \
+ then ToShmem for Atom needs to be implemented"
+ )
+ }
+}
diff --git a/servo_crates/to_shmem_derive/Cargo.toml b/servo_crates/to_shmem_derive/Cargo.toml
new file mode 100644
index 00000000..1ddb0974
--- /dev/null
+++ b/servo_crates/to_shmem_derive/Cargo.toml
@@ -0,0 +1,18 @@
+[package]
+name = "to_shmem_derive"
+version = "0.0.1"
+authors = ["The Servo Project Developers"]
+license = "MPL-2.0"
+publish = false
+
+[lib]
+path = "lib.rs"
+proc-macro = true
+
+[dependencies]
+darling = { version = "0.10", default-features = false }
+derive_common = { path = "../derive_common" }
+proc-macro2 = "1"
+quote = "1"
+syn = { version = "1", default-features = false, features = ["derive", "parsing"] }
+synstructure = "0.12"
diff --git a/servo_crates/to_shmem_derive/lib.rs b/servo_crates/to_shmem_derive/lib.rs
new file mode 100644
index 00000000..b820e7f8
--- /dev/null
+++ b/servo_crates/to_shmem_derive/lib.rs
@@ -0,0 +1,26 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+#![recursion_limit = "128"]
+
+#[macro_use]
+extern crate darling;
+extern crate derive_common;
+extern crate proc_macro;
+extern crate proc_macro2;
+#[macro_use]
+extern crate quote;
+#[macro_use]
+extern crate syn;
+extern crate synstructure;
+
+use proc_macro::TokenStream;
+
+mod to_shmem;
+
+#[proc_macro_derive(ToShmem, attributes(shmem))]
+pub fn derive_to_shmem(stream: TokenStream) -> TokenStream {
+ let input = syn::parse(stream).unwrap();
+ to_shmem::derive(input).into()
+}
diff --git a/servo_crates/to_shmem_derive/to_shmem.rs b/servo_crates/to_shmem_derive/to_shmem.rs
new file mode 100644
index 00000000..01ba308e
--- /dev/null
+++ b/servo_crates/to_shmem_derive/to_shmem.rs
@@ -0,0 +1,68 @@
+/* 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 https://mozilla.org/MPL/2.0/. */
+
+use derive_common::cg;
+use proc_macro2::TokenStream;
+use syn;
+use synstructure::{BindStyle, Structure};
+
+pub fn derive(mut input: syn::DeriveInput) -> TokenStream {
+ let mut where_clause = input.generics.where_clause.take();
+ let attrs = cg::parse_input_attrs::<ShmemInputAttrs>(&input);
+ if !attrs.no_bounds {
+ for param in input.generics.type_params() {
+ cg::add_predicate(&mut where_clause, parse_quote!(#param: ::to_shmem::ToShmem));
+ }
+ }
+ for variant in Structure::new(&input).variants() {
+ for binding in variant.bindings() {
+ let attrs = cg::parse_field_attrs::<ShmemFieldAttrs>(&binding.ast());
+ if attrs.field_bound {
+ let ty = &binding.ast().ty;
+ cg::add_predicate(&mut where_clause, parse_quote!(#ty: ::to_shmem::ToShmem))
+ }
+ }
+ }
+
+ input.generics.where_clause = where_clause;
+
+ let match_body = cg::fmap_match(&input, BindStyle::Ref, |binding| {
+ quote! {
+ ::std::mem::ManuallyDrop::into_inner(
+ ::to_shmem::ToShmem::to_shmem(#binding, builder)
+ )
+ }
+ });
+
+ let name = &input.ident;
+ let (impl_generics, ty_generics, where_clause) = input.generics.split_for_impl();
+
+ quote! {
+ impl #impl_generics ::to_shmem::ToShmem for #name #ty_generics #where_clause {
+ #[allow(unused_variables, unreachable_code)]
+ fn to_shmem(
+ &self,
+ builder: &mut ::to_shmem::SharedMemoryBuilder,
+ ) -> ::std::mem::ManuallyDrop<Self> {
+ ::std::mem::ManuallyDrop::new(
+ match *self {
+ #match_body
+ }
+ )
+ }
+ }
+ }
+}
+
+#[darling(attributes(shmem), default)]
+#[derive(Default, FromDeriveInput)]
+pub struct ShmemInputAttrs {
+ pub no_bounds: bool,
+}
+
+#[darling(attributes(shmem), default)]
+#[derive(Default, FromField)]
+pub struct ShmemFieldAttrs {
+ pub field_bound: bool,
+}
[
Date Prev][
Date Next] [
Thread Prev][
Thread Next]
[
Thread Index]
[
Date Index]
[
Author Index]
