diff options
Diffstat (limited to 'src/tools/rustfmt/src/imports.rs')
| -rw-r--r-- | src/tools/rustfmt/src/imports.rs | 1506 |
1 files changed, 1506 insertions, 0 deletions
diff --git a/src/tools/rustfmt/src/imports.rs b/src/tools/rustfmt/src/imports.rs new file mode 100644 index 000000000..8d41c8815 --- /dev/null +++ b/src/tools/rustfmt/src/imports.rs @@ -0,0 +1,1506 @@ +use std::borrow::Cow; +use std::cmp::Ordering; +use std::fmt; + +use core::hash::{Hash, Hasher}; + +use itertools::Itertools; + +use rustc_ast::ast::{self, UseTreeKind}; +use rustc_span::{ + symbol::{self, sym}, + BytePos, Span, DUMMY_SP, +}; + +use crate::comment::combine_strs_with_missing_comments; +use crate::config::lists::*; +use crate::config::ImportGranularity; +use crate::config::{Edition, IndentStyle, Version}; +use crate::lists::{ + definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator, +}; +use crate::rewrite::{Rewrite, RewriteContext}; +use crate::shape::Shape; +use crate::source_map::SpanUtils; +use crate::spanned::Spanned; +use crate::utils::{is_same_visibility, mk_sp, rewrite_ident}; +use crate::visitor::FmtVisitor; + +/// Returns a name imported by a `use` declaration. +/// E.g., returns `Ordering` for `std::cmp::Ordering` and `self` for `std::cmp::self`. +pub(crate) fn path_to_imported_ident(path: &ast::Path) -> symbol::Ident { + path.segments.last().unwrap().ident +} + +impl<'a> FmtVisitor<'a> { + pub(crate) fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) { + let span = item.span(); + let shape = self.shape(); + let rw = UseTree::from_ast( + &self.get_context(), + tree, + None, + Some(item.vis.clone()), + Some(item.span.lo()), + Some(item.attrs.clone()), + ) + .rewrite_top_level(&self.get_context(), shape); + match rw { + Some(ref s) if s.is_empty() => { + // Format up to last newline + let prev_span = mk_sp(self.last_pos, source!(self, span).lo()); + let trimmed_snippet = self.snippet(prev_span).trim_end(); + let span_end = self.last_pos + BytePos(trimmed_snippet.len() as u32); + self.format_missing(span_end); + // We have an excessive newline from the removed import. + if self.buffer.ends_with('\n') { + self.buffer.pop(); + self.line_number -= 1; + } + self.last_pos = source!(self, span).hi(); + } + Some(ref s) => { + self.format_missing_with_indent(source!(self, span).lo()); + self.push_str(s); + self.last_pos = source!(self, span).hi(); + } + None => { + self.format_missing_with_indent(source!(self, span).lo()); + self.format_missing(source!(self, span).hi()); + } + } + } +} + +// Ordering of imports + +// We order imports by translating to our own representation and then sorting. +// The Rust AST data structures are really bad for this. Rustfmt applies a bunch +// of normalisations to imports and since we want to sort based on the result +// of these (and to maintain idempotence) we must apply the same normalisations +// to the data structures for sorting. +// +// We sort `self` and `super` before other imports, then identifier imports, +// then glob imports, then lists of imports. We do not take aliases into account +// when ordering unless the imports are identical except for the alias (rare in +// practice). + +// FIXME(#2531): we should unify the comparison code here with the formatting +// code elsewhere since we are essentially string-ifying twice. Furthermore, by +// parsing to our own format on comparison, we repeat a lot of work when +// sorting. + +// FIXME we do a lot of allocation to make our own representation. +#[derive(Clone, Eq, Hash, PartialEq)] +pub(crate) enum UseSegmentKind { + Ident(String, Option<String>), + Slf(Option<String>), + Super(Option<String>), + Crate(Option<String>), + Glob, + List(Vec<UseTree>), +} + +#[derive(Clone, Eq, PartialEq)] +pub(crate) struct UseSegment { + pub(crate) kind: UseSegmentKind, + pub(crate) version: Version, +} + +#[derive(Clone)] +pub(crate) struct UseTree { + pub(crate) path: Vec<UseSegment>, + pub(crate) span: Span, + // Comment information within nested use tree. + pub(crate) list_item: Option<ListItem>, + // Additional fields for top level use items. + // Should we have another struct for top-level use items rather than reusing this? + visibility: Option<ast::Visibility>, + attrs: Option<Vec<ast::Attribute>>, +} + +impl PartialEq for UseTree { + fn eq(&self, other: &UseTree) -> bool { + self.path == other.path + } +} +impl Eq for UseTree {} + +impl Spanned for UseTree { + fn span(&self) -> Span { + let lo = if let Some(ref attrs) = self.attrs { + attrs.iter().next().map_or(self.span.lo(), |a| a.span.lo()) + } else { + self.span.lo() + }; + mk_sp(lo, self.span.hi()) + } +} + +impl UseSegment { + // Clone a version of self with any top-level alias removed. + fn remove_alias(&self) -> UseSegment { + let kind = match self.kind { + UseSegmentKind::Ident(ref s, _) => UseSegmentKind::Ident(s.clone(), None), + UseSegmentKind::Slf(_) => UseSegmentKind::Slf(None), + UseSegmentKind::Super(_) => UseSegmentKind::Super(None), + UseSegmentKind::Crate(_) => UseSegmentKind::Crate(None), + _ => return self.clone(), + }; + UseSegment { + kind, + version: self.version, + } + } + + // Check if self == other with their aliases removed. + fn equal_except_alias(&self, other: &Self) -> bool { + match (&self.kind, &other.kind) { + (UseSegmentKind::Ident(ref s1, _), UseSegmentKind::Ident(ref s2, _)) => s1 == s2, + (UseSegmentKind::Slf(_), UseSegmentKind::Slf(_)) + | (UseSegmentKind::Super(_), UseSegmentKind::Super(_)) + | (UseSegmentKind::Crate(_), UseSegmentKind::Crate(_)) + | (UseSegmentKind::Glob, UseSegmentKind::Glob) => true, + (UseSegmentKind::List(ref list1), UseSegmentKind::List(ref list2)) => list1 == list2, + _ => false, + } + } + + fn get_alias(&self) -> Option<&str> { + match &self.kind { + UseSegmentKind::Ident(_, a) + | UseSegmentKind::Slf(a) + | UseSegmentKind::Super(a) + | UseSegmentKind::Crate(a) => a.as_deref(), + _ => None, + } + } + + fn from_path_segment( + context: &RewriteContext<'_>, + path_seg: &ast::PathSegment, + modsep: bool, + ) -> Option<UseSegment> { + let name = rewrite_ident(context, path_seg.ident); + if name.is_empty() || name == "{{root}}" { + return None; + } + let kind = match name { + "self" => UseSegmentKind::Slf(None), + "super" => UseSegmentKind::Super(None), + "crate" => UseSegmentKind::Crate(None), + _ => { + let mod_sep = if modsep { "::" } else { "" }; + UseSegmentKind::Ident(format!("{}{}", mod_sep, name), None) + } + }; + + Some(UseSegment { + kind, + version: context.config.version(), + }) + } + + fn contains_comment(&self) -> bool { + if let UseSegmentKind::List(list) = &self.kind { + list.iter().any(|subtree| subtree.contains_comment()) + } else { + false + } + } +} + +pub(crate) fn normalize_use_trees_with_granularity( + use_trees: Vec<UseTree>, + import_granularity: ImportGranularity, +) -> Vec<UseTree> { + let merge_by = match import_granularity { + ImportGranularity::Item => return flatten_use_trees(use_trees, ImportGranularity::Item), + ImportGranularity::Preserve => return use_trees, + ImportGranularity::Crate => SharedPrefix::Crate, + ImportGranularity::Module => SharedPrefix::Module, + ImportGranularity::One => SharedPrefix::One, + }; + + let mut result = Vec::with_capacity(use_trees.len()); + for use_tree in use_trees { + if use_tree.contains_comment() || use_tree.attrs.is_some() { + result.push(use_tree); + continue; + } + + for mut flattened in use_tree.flatten(import_granularity) { + if let Some(tree) = result + .iter_mut() + .find(|tree| tree.share_prefix(&flattened, merge_by)) + { + tree.merge(&flattened, merge_by); + } else { + // If this is the first tree with this prefix, handle potential trailing ::self + if merge_by == SharedPrefix::Module { + flattened = flattened.nest_trailing_self(); + } + result.push(flattened); + } + } + } + result +} + +fn flatten_use_trees( + use_trees: Vec<UseTree>, + import_granularity: ImportGranularity, +) -> Vec<UseTree> { + // Return non-sorted single occurance of the use-trees text string; + // order is by first occurance of the use-tree. + use_trees + .into_iter() + .flat_map(|tree| tree.flatten(import_granularity)) + .map(UseTree::nest_trailing_self) + .unique() + .collect() +} + +impl fmt::Debug for UseTree { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(self, f) + } +} + +impl fmt::Debug for UseSegment { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.kind, f) + } +} + +impl fmt::Display for UseSegment { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(&self.kind, f) + } +} + +impl Hash for UseSegment { + fn hash<H: Hasher>(&self, state: &mut H) { + self.kind.hash(state); + } +} + +impl fmt::Debug for UseSegmentKind { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + fmt::Display::fmt(self, f) + } +} + +impl fmt::Display for UseSegmentKind { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + match *self { + UseSegmentKind::Glob => write!(f, "*"), + UseSegmentKind::Ident(ref s, Some(ref alias)) => write!(f, "{} as {}", s, alias), + UseSegmentKind::Ident(ref s, None) => write!(f, "{}", s), + UseSegmentKind::Slf(..) => write!(f, "self"), + UseSegmentKind::Super(..) => write!(f, "super"), + UseSegmentKind::Crate(..) => write!(f, "crate"), + UseSegmentKind::List(ref list) => { + write!(f, "{{")?; + for (i, item) in list.iter().enumerate() { + if i != 0 { + write!(f, ", ")?; + } + write!(f, "{}", item)?; + } + write!(f, "}}") + } + } + } +} +impl fmt::Display for UseTree { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + for (i, segment) in self.path.iter().enumerate() { + if i != 0 { + write!(f, "::")?; + } + write!(f, "{}", segment)?; + } + Ok(()) + } +} + +impl UseTree { + // Rewrite use tree with `use ` and a trailing `;`. + pub(crate) fn rewrite_top_level( + &self, + context: &RewriteContext<'_>, + shape: Shape, + ) -> Option<String> { + let vis = self.visibility.as_ref().map_or(Cow::from(""), |vis| { + crate::utils::format_visibility(context, vis) + }); + let use_str = self + .rewrite(context, shape.offset_left(vis.len())?) + .map(|s| { + if s.is_empty() { + s + } else { + format!("{}use {};", vis, s) + } + })?; + match self.attrs { + Some(ref attrs) if !attrs.is_empty() => { + let attr_str = attrs.rewrite(context, shape)?; + let lo = attrs.last().as_ref()?.span.hi(); + let hi = self.span.lo(); + let span = mk_sp(lo, hi); + + let allow_extend = if attrs.len() == 1 { + let line_len = attr_str.len() + 1 + use_str.len(); + !attrs.first().unwrap().is_doc_comment() + && context.config.inline_attribute_width() >= line_len + } else { + false + }; + + combine_strs_with_missing_comments( + context, + &attr_str, + &use_str, + span, + shape, + allow_extend, + ) + } + _ => Some(use_str), + } + } + + // FIXME: Use correct span? + // The given span is essentially incorrect, since we are reconstructing + // use-statements. This should not be a problem, though, since we have + // already tried to extract comment and observed that there are no comment + // around the given use item, and the span will not be used afterward. + fn from_path(path: Vec<UseSegment>, span: Span) -> UseTree { + UseTree { + path, + span, + list_item: None, + visibility: None, + attrs: None, + } + } + + pub(crate) fn from_ast_with_normalization( + context: &RewriteContext<'_>, + item: &ast::Item, + ) -> Option<UseTree> { + match item.kind { + ast::ItemKind::Use(ref use_tree) => Some( + UseTree::from_ast( + context, + use_tree, + None, + Some(item.vis.clone()), + Some(item.span.lo()), + if item.attrs.is_empty() { + None + } else { + Some(item.attrs.clone()) + }, + ) + .normalize(), + ), + _ => None, + } + } + + fn from_ast( + context: &RewriteContext<'_>, + a: &ast::UseTree, + list_item: Option<ListItem>, + visibility: Option<ast::Visibility>, + opt_lo: Option<BytePos>, + attrs: Option<Vec<ast::Attribute>>, + ) -> UseTree { + let span = if let Some(lo) = opt_lo { + mk_sp(lo, a.span.hi()) + } else { + a.span + }; + let mut result = UseTree { + path: vec![], + span, + list_item, + visibility, + attrs, + }; + + let leading_modsep = + context.config.edition() >= Edition::Edition2018 && a.prefix.is_global(); + + let mut modsep = leading_modsep; + + for p in &a.prefix.segments { + if let Some(use_segment) = UseSegment::from_path_segment(context, p, modsep) { + result.path.push(use_segment); + modsep = false; + } + } + + let version = context.config.version(); + + match a.kind { + UseTreeKind::Glob => { + // in case of a global path and the glob starts at the root, e.g., "::*" + if a.prefix.segments.len() == 1 && leading_modsep { + let kind = UseSegmentKind::Ident("".to_owned(), None); + result.path.push(UseSegment { kind, version }); + } + result.path.push(UseSegment { + kind: UseSegmentKind::Glob, + version, + }); + } + UseTreeKind::Nested(ref list) => { + // Extract comments between nested use items. + // This needs to be done before sorting use items. + let items = itemize_list( + context.snippet_provider, + list.iter().map(|(tree, _)| tree), + "}", + ",", + |tree| tree.span.lo(), + |tree| tree.span.hi(), + |_| Some("".to_owned()), // We only need comments for now. + context.snippet_provider.span_after(a.span, "{"), + a.span.hi(), + false, + ); + + // in case of a global path and the nested list starts at the root, + // e.g., "::{foo, bar}" + if a.prefix.segments.len() == 1 && leading_modsep { + let kind = UseSegmentKind::Ident("".to_owned(), None); + result.path.push(UseSegment { kind, version }); + } + let kind = UseSegmentKind::List( + list.iter() + .zip(items) + .map(|(t, list_item)| { + Self::from_ast(context, &t.0, Some(list_item), None, None, None) + }) + .collect(), + ); + result.path.push(UseSegment { kind, version }); + } + UseTreeKind::Simple(ref rename, ..) => { + // If the path has leading double colons and is composed of only 2 segments, then we + // bypass the call to path_to_imported_ident which would get only the ident and + // lose the path root, e.g., `that` in `::that`. + // The span of `a.prefix` contains the leading colons. + let name = if a.prefix.segments.len() == 2 && leading_modsep { + context.snippet(a.prefix.span).to_owned() + } else { + rewrite_ident(context, path_to_imported_ident(&a.prefix)).to_owned() + }; + let alias = rename.and_then(|ident| { + if ident.name == sym::underscore_imports { + // for impl-only-use + Some("_".to_owned()) + } else if ident == path_to_imported_ident(&a.prefix) { + None + } else { + Some(rewrite_ident(context, ident).to_owned()) + } + }); + let kind = match name.as_ref() { + "self" => UseSegmentKind::Slf(alias), + "super" => UseSegmentKind::Super(alias), + "crate" => UseSegmentKind::Crate(alias), + _ => UseSegmentKind::Ident(name, alias), + }; + + let segment = UseSegment { kind, version }; + + // `name` is already in result. + result.path.pop(); + result.path.push(segment); + } + } + result + } + + // Do the adjustments that rustfmt does elsewhere to use paths. + pub(crate) fn normalize(mut self) -> UseTree { + let mut last = self.path.pop().expect("Empty use tree?"); + // Hack around borrow checker. + let mut normalize_sole_list = false; + let mut aliased_self = false; + + // Remove foo::{} or self without attributes. + match last.kind { + _ if self.attrs.is_some() => (), + UseSegmentKind::List(ref list) if list.is_empty() => { + self.path = vec![]; + return self; + } + UseSegmentKind::Slf(None) if self.path.is_empty() && self.visibility.is_some() => { + self.path = vec![]; + return self; + } + _ => (), + } + + // Normalise foo::self -> foo. + if let UseSegmentKind::Slf(None) = last.kind { + if !self.path.is_empty() { + return self; + } + } + + // Normalise foo::self as bar -> foo as bar. + if let UseSegmentKind::Slf(_) = last.kind { + if let Some(UseSegment { + kind: UseSegmentKind::Ident(_, None), + .. + }) = self.path.last() + { + aliased_self = true; + } + } + + let mut done = false; + if aliased_self { + match self.path.last_mut() { + Some(UseSegment { + kind: UseSegmentKind::Ident(_, ref mut old_rename), + .. + }) => { + assert!(old_rename.is_none()); + if let UseSegmentKind::Slf(Some(rename)) = last.clone().kind { + *old_rename = Some(rename); + done = true; + } + } + _ => unreachable!(), + } + } + + if done { + return self; + } + + // Normalise foo::{bar} -> foo::bar + if let UseSegmentKind::List(ref list) = last.kind { + if list.len() == 1 && list[0].to_string() != "self" { + normalize_sole_list = true; + } + } + + if normalize_sole_list { + match last.kind { + UseSegmentKind::List(list) => { + for seg in &list[0].path { + self.path.push(seg.clone()); + } + return self.normalize(); + } + _ => unreachable!(), + } + } + + // Recursively normalize elements of a list use (including sorting the list). + if let UseSegmentKind::List(list) = last.kind { + let mut list = list.into_iter().map(UseTree::normalize).collect::<Vec<_>>(); + list.sort(); + last = UseSegment { + kind: UseSegmentKind::List(list), + version: last.version, + }; + } + + self.path.push(last); + self + } + + fn has_comment(&self) -> bool { + self.list_item.as_ref().map_or(false, ListItem::has_comment) + } + + fn contains_comment(&self) -> bool { + self.has_comment() || self.path.iter().any(|path| path.contains_comment()) + } + + fn same_visibility(&self, other: &UseTree) -> bool { + match (&self.visibility, &other.visibility) { + ( + Some(ast::Visibility { + kind: ast::VisibilityKind::Inherited, + .. + }), + None, + ) + | ( + None, + Some(ast::Visibility { + kind: ast::VisibilityKind::Inherited, + .. + }), + ) + | (None, None) => true, + (Some(ref a), Some(ref b)) => is_same_visibility(a, b), + _ => false, + } + } + + fn share_prefix(&self, other: &UseTree, shared_prefix: SharedPrefix) -> bool { + if self.path.is_empty() + || other.path.is_empty() + || self.attrs.is_some() + || self.contains_comment() + || !self.same_visibility(other) + { + false + } else { + match shared_prefix { + SharedPrefix::Crate => self.path[0] == other.path[0], + SharedPrefix::Module => { + self.path[..self.path.len() - 1] == other.path[..other.path.len() - 1] + } + SharedPrefix::One => true, + } + } + } + + fn flatten(self, import_granularity: ImportGranularity) -> Vec<UseTree> { + if self.path.is_empty() || self.contains_comment() { + return vec![self]; + } + match &self.path.clone().last().unwrap().kind { + UseSegmentKind::List(list) => { + if list.len() == 1 && list[0].path.len() == 1 { + if let UseSegmentKind::Slf(..) = list[0].path[0].kind { + return vec![self]; + }; + } + let prefix = &self.path[..self.path.len() - 1]; + let mut result = vec![]; + for nested_use_tree in list { + for flattend in &mut nested_use_tree.clone().flatten(import_granularity) { + let mut new_path = prefix.to_vec(); + new_path.append(&mut flattend.path); + result.push(UseTree { + path: new_path, + span: self.span, + list_item: None, + visibility: self.visibility.clone(), + // only retain attributes for `ImportGranularity::Item` + attrs: match import_granularity { + ImportGranularity::Item => self.attrs.clone(), + _ => None, + }, + }); + } + } + + result + } + _ => vec![self], + } + } + + fn merge(&mut self, other: &UseTree, merge_by: SharedPrefix) { + let mut prefix = 0; + for (a, b) in self.path.iter().zip(other.path.iter()) { + // only discard the alias at the root of the tree + if (prefix == 0 && a.equal_except_alias(b)) || a == b { + prefix += 1; + } else { + break; + } + } + if let Some(new_path) = merge_rest(&self.path, &other.path, prefix, merge_by) { + self.path = new_path; + self.span = self.span.to(other.span); + } + } + + /// If this tree ends in `::self`, rewrite it to `::{self}`. + fn nest_trailing_self(mut self) -> UseTree { + if let Some(UseSegment { + kind: UseSegmentKind::Slf(..), + .. + }) = self.path.last() + { + let self_segment = self.path.pop().unwrap(); + let version = self_segment.version; + let kind = UseSegmentKind::List(vec![UseTree::from_path(vec![self_segment], DUMMY_SP)]); + self.path.push(UseSegment { kind, version }); + } + self + } +} + +fn merge_rest( + a: &[UseSegment], + b: &[UseSegment], + mut len: usize, + merge_by: SharedPrefix, +) -> Option<Vec<UseSegment>> { + if a.len() == len && b.len() == len { + return None; + } + if a.len() != len && b.len() != len { + let version = a[len].version; + if let UseSegmentKind::List(ref list) = a[len].kind { + let mut list = list.clone(); + merge_use_trees_inner( + &mut list, + UseTree::from_path(b[len..].to_vec(), DUMMY_SP), + merge_by, + ); + let mut new_path = b[..len].to_vec(); + let kind = UseSegmentKind::List(list); + new_path.push(UseSegment { kind, version }); + return Some(new_path); + } + } else if len == 1 { + let (common, rest) = if a.len() == len { + (&a[0], &b[1..]) + } else { + (&b[0], &a[1..]) + }; + let kind = UseSegmentKind::Slf(common.get_alias().map(ToString::to_string)); + let version = a[0].version; + let mut list = vec![UseTree::from_path( + vec![UseSegment { kind, version }], + DUMMY_SP, + )]; + match rest { + [ + UseSegment { + kind: UseSegmentKind::List(rest_list), + .. + }, + ] => list.extend(rest_list.clone()), + _ => list.push(UseTree::from_path(rest.to_vec(), DUMMY_SP)), + } + return Some(vec![ + b[0].clone(), + UseSegment { + kind: UseSegmentKind::List(list), + version, + }, + ]); + } else { + len -= 1; + } + let mut list = vec![ + UseTree::from_path(a[len..].to_vec(), DUMMY_SP), + UseTree::from_path(b[len..].to_vec(), DUMMY_SP), + ]; + list.sort(); + let mut new_path = b[..len].to_vec(); + let kind = UseSegmentKind::List(list); + let version = a[0].version; + new_path.push(UseSegment { kind, version }); + Some(new_path) +} + +fn merge_use_trees_inner(trees: &mut Vec<UseTree>, use_tree: UseTree, merge_by: SharedPrefix) { + struct SimilarTree<'a> { + similarity: usize, + path_len: usize, + tree: &'a mut UseTree, + } + + let similar_trees = trees.iter_mut().filter_map(|tree| { + if tree.share_prefix(&use_tree, merge_by) { + // In the case of `SharedPrefix::One`, `similarity` is used for deciding with which + // tree `use_tree` should be merge. + // In other cases `similarity` won't be used, so set it to `0` as a dummy value. + let similarity = if merge_by == SharedPrefix::One { + tree.path + .iter() + .zip(&use_tree.path) + .take_while(|(a, b)| a.equal_except_alias(b)) + .count() + } else { + 0 + }; + + let path_len = tree.path.len(); + Some(SimilarTree { + similarity, + tree, + path_len, + }) + } else { + None + } + }); + + if use_tree.path.len() == 1 && merge_by == SharedPrefix::Crate { + if let Some(tree) = similar_trees.min_by_key(|tree| tree.path_len) { + if tree.path_len == 1 { + return; + } + } + } else if merge_by == SharedPrefix::One { + if let Some(sim_tree) = similar_trees.max_by_key(|tree| tree.similarity) { + if sim_tree.similarity > 0 { + sim_tree.tree.merge(&use_tree, merge_by); + return; + } + } + } else if let Some(sim_tree) = similar_trees.max_by_key(|tree| tree.path_len) { + if sim_tree.path_len > 1 { + sim_tree.tree.merge(&use_tree, merge_by); + return; + } + } + trees.push(use_tree); + trees.sort(); +} + +impl Hash for UseTree { + fn hash<H: Hasher>(&self, state: &mut H) { + self.path.hash(state); + } +} + +impl PartialOrd for UseSegment { + fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> { + Some(self.cmp(other)) + } +} +impl PartialOrd for UseTree { + fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> { + Some(self.cmp(other)) + } +} +impl Ord for UseSegment { + fn cmp(&self, other: &UseSegment) -> Ordering { + use self::UseSegmentKind::*; + + fn is_upper_snake_case(s: &str) -> bool { + s.chars() + .all(|c| c.is_uppercase() || c == '_' || c.is_numeric()) + } + + match (&self.kind, &other.kind) { + (Slf(ref a), Slf(ref b)) + | (Super(ref a), Super(ref b)) + | (Crate(ref a), Crate(ref b)) => match (a, b) { + (Some(sa), Some(sb)) => { + if self.version == Version::Two { + sa.trim_start_matches("r#").cmp(sb.trim_start_matches("r#")) + } else { + a.cmp(b) + } + } + (_, _) => a.cmp(b), + }, + (Glob, Glob) => Ordering::Equal, + (Ident(ref pia, ref aa), Ident(ref pib, ref ab)) => { + let (ia, ib) = if self.version == Version::Two { + (pia.trim_start_matches("r#"), pib.trim_start_matches("r#")) + } else { + (pia.as_str(), pib.as_str()) + }; + // snake_case < CamelCase < UPPER_SNAKE_CASE + if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) { + return Ordering::Greater; + } + if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) { + return Ordering::Less; + } + if is_upper_snake_case(ia) && !is_upper_snake_case(ib) { + return Ordering::Greater; + } + if !is_upper_snake_case(ia) && is_upper_snake_case(ib) { + return Ordering::Less; + } + let ident_ord = ia.cmp(ib); + if ident_ord != Ordering::Equal { + return ident_ord; + } + match (aa, ab) { + (None, Some(_)) => Ordering::Less, + (Some(_), None) => Ordering::Greater, + (Some(aas), Some(abs)) => { + if self.version == Version::Two { + aas.trim_start_matches("r#") + .cmp(abs.trim_start_matches("r#")) + } else { + aas.cmp(abs) + } + } + (None, None) => Ordering::Equal, + } + } + (List(ref a), List(ref b)) => { + for (a, b) in a.iter().zip(b.iter()) { + let ord = a.cmp(b); + if ord != Ordering::Equal { + return ord; + } + } + + a.len().cmp(&b.len()) + } + (Slf(_), _) => Ordering::Less, + (_, Slf(_)) => Ordering::Greater, + (Super(_), _) => Ordering::Less, + (_, Super(_)) => Ordering::Greater, + (Crate(_), _) => Ordering::Less, + (_, Crate(_)) => Ordering::Greater, + (Ident(..), _) => Ordering::Less, + (_, Ident(..)) => Ordering::Greater, + (Glob, _) => Ordering::Less, + (_, Glob) => Ordering::Greater, + } + } +} +impl Ord for UseTree { + fn cmp(&self, other: &UseTree) -> Ordering { + for (a, b) in self.path.iter().zip(other.path.iter()) { + let ord = a.cmp(b); + // The comparison without aliases is a hack to avoid situations like + // comparing `a::b` to `a as c` - where the latter should be ordered + // first since it is shorter. + if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal + { + return ord; + } + } + + self.path.len().cmp(&other.path.len()) + } +} + +fn rewrite_nested_use_tree( + context: &RewriteContext<'_>, + use_tree_list: &[UseTree], + shape: Shape, +) -> Option<String> { + let mut list_items = Vec::with_capacity(use_tree_list.len()); + let nested_shape = match context.config.imports_indent() { + IndentStyle::Block => shape + .block_indent(context.config.tab_spaces()) + .with_max_width(context.config) + .sub_width(1)?, + IndentStyle::Visual => shape.visual_indent(0), + }; + for use_tree in use_tree_list { + if let Some(mut list_item) = use_tree.list_item.clone() { + list_item.item = use_tree.rewrite(context, nested_shape); + list_items.push(list_item); + } else { + list_items.push(ListItem::from_str(use_tree.rewrite(context, nested_shape)?)); + } + } + let has_nested_list = use_tree_list.iter().any(|use_segment| { + use_segment.path.last().map_or(false, |last_segment| { + matches!(last_segment.kind, UseSegmentKind::List(..)) + }) + }); + + let remaining_width = if has_nested_list { + 0 + } else { + shape.width.saturating_sub(2) + }; + + let tactic = definitive_tactic( + &list_items, + context.config.imports_layout(), + Separator::Comma, + remaining_width, + ); + + let ends_with_newline = context.config.imports_indent() == IndentStyle::Block + && tactic != DefinitiveListTactic::Horizontal; + let trailing_separator = if ends_with_newline { + context.config.trailing_comma() + } else { + SeparatorTactic::Never + }; + let fmt = ListFormatting::new(nested_shape, context.config) + .tactic(tactic) + .trailing_separator(trailing_separator) + .ends_with_newline(ends_with_newline) + .preserve_newline(true) + .nested(has_nested_list); + + let list_str = write_list(&list_items, &fmt)?; + + let result = if (list_str.contains('\n') || list_str.len() > remaining_width) + && context.config.imports_indent() == IndentStyle::Block + { + format!( + "{{\n{}{}\n{}}}", + nested_shape.indent.to_string(context.config), + list_str, + shape.indent.to_string(context.config) + ) + } else { + format!("{{{}}}", list_str) + }; + + Some(result) +} + +impl Rewrite for UseSegment { + fn rewrite(&self, context: &RewriteContext<'_>, shape: Shape) -> Option<String> { + Some(match self.kind { + UseSegmentKind::Ident(ref ident, Some(ref rename)) => { + format!("{} as {}", ident, rename) + } + UseSegmentKind::Ident(ref ident, None) => ident.clone(), + UseSegmentKind::Slf(Some(ref rename)) => format!("self as {}", rename), + UseSegmentKind::Slf(None) => "self".to_owned(), + UseSegmentKind::Super(Some(ref rename)) => format!("super as {}", rename), + UseSegmentKind::Super(None) => "super".to_owned(), + UseSegmentKind::Crate(Some(ref rename)) => format!("crate as {}", rename), + UseSegmentKind::Crate(None) => "crate".to_owned(), + UseSegmentKind::Glob => "*".to_owned(), + UseSegmentKind::List(ref use_tree_list) => rewrite_nested_use_tree( + context, + use_tree_list, + // 1 = "{" and "}" + shape.offset_left(1)?.sub_width(1)?, + )?, + }) + } +} + +impl Rewrite for UseTree { + // This does NOT format attributes and visibility or add a trailing `;`. + fn rewrite(&self, context: &RewriteContext<'_>, mut shape: Shape) -> Option<String> { + let mut result = String::with_capacity(256); + let mut iter = self.path.iter().peekable(); + while let Some(segment) = iter.next() { + let segment_str = segment.rewrite(context, shape)?; + result.push_str(&segment_str); + if iter.peek().is_some() { + result.push_str("::"); + // 2 = "::" + shape = shape.offset_left(2 + segment_str.len())?; + } + } + Some(result) + } +} + +#[derive(Copy, Clone, Debug, PartialEq, Eq)] +enum SharedPrefix { + Crate, + Module, + One, +} + +#[cfg(test)] +mod test { + use super::*; + use rustc_span::DUMMY_SP; + + // Parse the path part of an import. This parser is not robust and is only + // suitable for use in a test harness. + fn parse_use_tree(s: &str) -> UseTree { + use std::iter::Peekable; + use std::mem::swap; + use std::str::Chars; + + struct Parser<'a> { + input: Peekable<Chars<'a>>, + version: Version, + } + + impl<'a> Parser<'a> { + fn bump(&mut self) { + self.input.next().unwrap(); + } + + fn eat(&mut self, c: char) { + assert_eq!(self.input.next().unwrap(), c); + } + + fn push_segment( + &self, + result: &mut Vec<UseSegment>, + buf: &mut String, + alias_buf: &mut Option<String>, + ) { + let version = self.version; + if !buf.is_empty() { + let mut alias = None; + swap(alias_buf, &mut alias); + + match buf.as_ref() { + "self" => { + let kind = UseSegmentKind::Slf(alias); + result.push(UseSegment { kind, version }); + *buf = String::new(); + *alias_buf = None; + } + "super" => { + let kind = UseSegmentKind::Super(alias); + result.push(UseSegment { kind, version }); + *buf = String::new(); + *alias_buf = None; + } + "crate" => { + let kind = UseSegmentKind::Crate(alias); + result.push(UseSegment { kind, version }); + *buf = String::new(); + *alias_buf = None; + } + _ => { + let mut name = String::new(); + swap(buf, &mut name); + let kind = UseSegmentKind::Ident(name, alias); + result.push(UseSegment { kind, version }); + } + } + } + } + + fn parse_in_list(&mut self) -> UseTree { + let mut result = vec![]; + let mut buf = String::new(); + let mut alias_buf = None; + while let Some(&c) = self.input.peek() { + match c { + '{' => { + assert!(buf.is_empty()); + self.bump(); + let kind = UseSegmentKind::List(self.parse_list()); + result.push(UseSegment { + kind, + version: self.version, + }); + self.eat('}'); + } + '*' => { + assert!(buf.is_empty()); + self.bump(); + let kind = UseSegmentKind::Glob; + result.push(UseSegment { + kind, + version: self.version, + }); + } + ':' => { + self.bump(); + self.eat(':'); + self.push_segment(&mut result, &mut buf, &mut alias_buf); + } + '}' | ',' => { + self.push_segment(&mut result, &mut buf, &mut alias_buf); + return UseTree { + path: result, + span: DUMMY_SP, + list_item: None, + visibility: None, + attrs: None, + }; + } + ' ' => { + self.bump(); + self.eat('a'); + self.eat('s'); + self.eat(' '); + alias_buf = Some(String::new()); + } + c => { + self.bump(); + if let Some(ref mut buf) = alias_buf { + buf.push(c); + } else { + buf.push(c); + } + } + } + } + self.push_segment(&mut result, &mut buf, &mut alias_buf); + UseTree { + path: result, + span: DUMMY_SP, + list_item: None, + visibility: None, + attrs: None, + } + } + + fn parse_list(&mut self) -> Vec<UseTree> { + let mut result = vec![]; + loop { + match self.input.peek().unwrap() { + ',' | ' ' => self.bump(), + '}' => { + return result; + } + _ => result.push(self.parse_in_list()), + } + } + } + } + + let mut parser = Parser { + input: s.chars().peekable(), + version: Version::One, + }; + parser.parse_in_list() + } + + macro_rules! parse_use_trees { + ($($s:expr),* $(,)*) => { + vec![ + $(parse_use_tree($s),)* + ] + } + } + + macro_rules! test_merge { + ($by:ident, [$($input:expr),* $(,)*], [$($output:expr),* $(,)*]) => { + assert_eq!( + normalize_use_trees_with_granularity( + parse_use_trees!($($input,)*), + ImportGranularity::$by, + ), + parse_use_trees!($($output,)*), + ); + } + } + + #[test] + fn test_use_tree_merge_crate() { + test_merge!( + Crate, + ["a::b::{c, d}", "a::b::{e, f}"], + ["a::b::{c, d, e, f}"] + ); + test_merge!(Crate, ["a::b::c", "a::b"], ["a::{b, b::c}"]); + test_merge!(Crate, ["a::b", "a::b"], ["a::b"]); + test_merge!(Crate, ["a", "a::b", "a::b::c"], ["a::{self, b, b::c}"]); + test_merge!( + Crate, + ["a", "a::b", "a::b::c", "a::b::c::d"], + ["a::{self, b, b::{c, c::d}}"] + ); + test_merge!( + Crate, + ["a", "a::b", "a::b::c", "a::b"], + ["a::{self, b, b::c}"] + ); + test_merge!( + Crate, + ["a::{b::{self, c}, d::e}", "a::d::f"], + ["a::{b::{self, c}, d::{e, f}}"] + ); + test_merge!( + Crate, + ["a::d::f", "a::{b::{self, c}, d::e}"], + ["a::{b::{self, c}, d::{e, f}}"] + ); + test_merge!( + Crate, + ["a::{c, d, b}", "a::{d, e, b, a, f}", "a::{f, g, c}"], + ["a::{a, b, c, d, e, f, g}"] + ); + test_merge!( + Crate, + ["a::{self}", "b::{self as foo}"], + ["a::{self}", "b::{self as foo}"] + ); + } + + #[test] + fn test_use_tree_merge_module() { + test_merge!( + Module, + ["foo::b", "foo::{a, c, d::e}"], + ["foo::{a, b, c}", "foo::d::e"] + ); + + test_merge!( + Module, + ["foo::{a::b, a::c, d::e, d::f}"], + ["foo::a::{b, c}", "foo::d::{e, f}"] + ); + } + + #[test] + fn test_use_tree_merge_one() { + test_merge!(One, ["a", "b"], ["{a, b}"]); + + test_merge!(One, ["a::{aa, ab}", "b", "a"], ["{a::{self, aa, ab}, b}"]); + + test_merge!(One, ["a as x", "b as y"], ["{a as x, b as y}"]); + + test_merge!( + One, + ["a::{aa as xa, ab}", "b", "a"], + ["{a::{self, aa as xa, ab}, b}"] + ); + + test_merge!( + One, + ["a", "a::{aa, ab::{aba, abb}}"], + ["a::{self, aa, ab::{aba, abb}}"] + ); + + test_merge!(One, ["a", "b::{ba, *}"], ["{a, b::{ba, *}}"]); + + test_merge!(One, ["a", "b", "a::aa"], ["{a::{self, aa}, b}"]); + + test_merge!( + One, + ["a::aa::aaa", "a::ac::aca", "a::aa::*"], + ["a::{aa::{aaa, *}, ac::aca}"] + ); + + test_merge!( + One, + ["a", "b::{ba, bb}", "a::{aa::*, ab::aba}"], + ["{a::{self, aa::*, ab::aba}, b::{ba, bb}}"] + ); + + test_merge!( + One, + ["b", "a::ac::{aca, acb}", "a::{aa::*, ab}"], + ["{a::{aa::*, ab, ac::{aca, acb}}, b}"] + ); + } + + #[test] + fn test_flatten_use_trees() { + assert_eq!( + flatten_use_trees( + parse_use_trees!["foo::{a::{b, c}, d::e}"], + ImportGranularity::Item + ), + parse_use_trees!["foo::a::b", "foo::a::c", "foo::d::e"] + ); + + assert_eq!( + flatten_use_trees( + parse_use_trees!["foo::{self, a, b::{c, d}, e::*}"], + ImportGranularity::Item + ), + parse_use_trees![ + "foo::{self}", + "foo::a", + "foo::b::c", + "foo::b::d", + "foo::e::*" + ] + ); + } + + #[test] + fn test_use_tree_flatten() { + assert_eq!( + parse_use_tree("a::b::{c, d, e, f}").flatten(ImportGranularity::Item), + parse_use_trees!("a::b::c", "a::b::d", "a::b::e", "a::b::f",) + ); + + assert_eq!( + parse_use_tree("a::b::{c::{d, e, f}, g, h::{i, j, k}}") + .flatten(ImportGranularity::Item), + parse_use_trees![ + "a::b::c::d", + "a::b::c::e", + "a::b::c::f", + "a::b::g", + "a::b::h::i", + "a::b::h::j", + "a::b::h::k", + ] + ); + } + + #[test] + fn test_use_tree_normalize() { + assert_eq!(parse_use_tree("a::self").normalize(), parse_use_tree("a")); + assert_eq!( + parse_use_tree("a::self as foo").normalize(), + parse_use_tree("a as foo") + ); + assert_eq!( + parse_use_tree("a::{self}").normalize(), + parse_use_tree("a::{self}") + ); + assert_eq!(parse_use_tree("a::{b}").normalize(), parse_use_tree("a::b")); + assert_eq!( + parse_use_tree("a::{b, c::self}").normalize(), + parse_use_tree("a::{b, c}") + ); + assert_eq!( + parse_use_tree("a::{b as bar, c::self}").normalize(), + parse_use_tree("a::{b as bar, c}") + ); + } + + #[test] + fn test_use_tree_ord() { + assert!(parse_use_tree("a").normalize() < parse_use_tree("aa").normalize()); + assert!(parse_use_tree("a").normalize() < parse_use_tree("a::a").normalize()); + assert!(parse_use_tree("a").normalize() < parse_use_tree("*").normalize()); + assert!(parse_use_tree("a").normalize() < parse_use_tree("{a, b}").normalize()); + assert!(parse_use_tree("*").normalize() < parse_use_tree("{a, b}").normalize()); + + assert!( + parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize() + < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize() + ); + assert!( + parse_use_tree("serde::de::{Deserialize}").normalize() + < parse_use_tree("serde_json").normalize() + ); + assert!(parse_use_tree("a::b::c").normalize() < parse_use_tree("a::b::*").normalize()); + assert!( + parse_use_tree("foo::{Bar, Baz}").normalize() + < parse_use_tree("{Bar, Baz}").normalize() + ); + + assert!( + parse_use_tree("foo::{qux as bar}").normalize() + < parse_use_tree("foo::{self as bar}").normalize() + ); + assert!( + parse_use_tree("foo::{qux as bar}").normalize() + < parse_use_tree("foo::{baz, qux as bar}").normalize() + ); + assert!( + parse_use_tree("foo::{self as bar, baz}").normalize() + < parse_use_tree("foo::{baz, qux as bar}").normalize() + ); + + assert!(parse_use_tree("foo").normalize() < parse_use_tree("Foo").normalize()); + assert!(parse_use_tree("foo").normalize() < parse_use_tree("foo::Bar").normalize()); + + assert!( + parse_use_tree("std::cmp::{d, c, b, a}").normalize() + < parse_use_tree("std::cmp::{b, e, g, f}").normalize() + ); + } + + #[test] + fn test_use_tree_nest_trailing_self() { + assert_eq!( + parse_use_tree("a::b::self").nest_trailing_self(), + parse_use_tree("a::b::{self}") + ); + assert_eq!( + parse_use_tree("a::b::c").nest_trailing_self(), + parse_use_tree("a::b::c") + ); + assert_eq!( + parse_use_tree("a::b::{c, d}").nest_trailing_self(), + parse_use_tree("a::b::{c, d}") + ); + assert_eq!( + parse_use_tree("a::b::{self, c}").nest_trailing_self(), + parse_use_tree("a::b::{self, c}") + ); + } +} |