X-Git-Url: https://git.lizzy.rs/?a=blobdiff_plain;f=src%2Fimports.rs;h=9fd844a2c35b6ceec489b43dec87a990969d7c22;hb=a159b64b0aea1b09ec0d677acebd3f666426e6bc;hp=9fbf814919a230e6148448b3307beae0f2264724;hpb=3ebe0543626111475a2658c544b6d582d199d147;p=rust.git diff --git a/src/imports.rs b/src/imports.rs index 9fbf814919a..9fd844a2c35 100644 --- a/src/imports.rs +++ b/src/imports.rs @@ -10,495 +10,695 @@ use std::cmp::Ordering; -use syntax::ast; -use syntax::codemap::{BytePos, Span}; +use config::lists::*; +use syntax::ast::{self, UseTreeKind}; +use syntax::codemap::{self, BytePos, Span, DUMMY_SP}; -use spanned::Spanned; use codemap::SpanUtils; use comment::combine_strs_with_missing_comments; use config::IndentStyle; -use lists::{definitive_tactic, itemize_list, write_list, DefinitiveListTactic, ListFormatting, - ListItem, Separator, SeparatorPlace, SeparatorTactic}; +use lists::{definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator}; use rewrite::{Rewrite, RewriteContext}; use shape::Shape; -use types::{rewrite_path, PathContext}; -use utils::{format_visibility, mk_sp}; -use visitor::{rewrite_extern_crate, FmtVisitor}; +use spanned::Spanned; +use utils::mk_sp; +use visitor::FmtVisitor; + +use std::borrow::Cow; +use std::fmt; -fn compare_path_segments(a: &ast::PathSegment, b: &ast::PathSegment) -> Ordering { - a.identifier.name.as_str().cmp(&b.identifier.name.as_str()) +/// Returns a name imported by a `use` declaration. e.g. returns `Ordering` +/// for `std::cmp::Ordering` and `self` for `std::cmp::self`. +pub fn path_to_imported_ident(path: &ast::Path) -> ast::Ident { + path.segments.last().unwrap().ident } -fn compare_paths(a: &ast::Path, b: &ast::Path) -> Ordering { - for segment in a.segments.iter().zip(b.segments.iter()) { - let ord = compare_path_segments(segment.0, segment.1); - if ord != Ordering::Equal { - return ord; +impl<'a> FmtVisitor<'a> { + pub 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_right(); + 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()); + } } } - a.segments.len().cmp(&b.segments.len()) } -fn compare_use_trees(a: &ast::UseTree, b: &ast::UseTree, nested: bool) -> Ordering { - use ast::UseTreeKind::*; +// Ordering of imports - // `use_nested_groups` is not yet supported, remove the `if !nested` when support will be - // fully added - if !nested { - let paths_cmp = compare_paths(&a.prefix, &b.prefix); - if paths_cmp != Ordering::Equal { - return paths_cmp; - } +// 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, PartialEq)] +pub enum UseSegment { + Ident(String, Option), + Slf(Option), + Super(Option), + Glob, + List(Vec), +} + +#[derive(Clone)] +pub struct UseTree { + pub path: Vec, + pub span: Span, + // Comment information within nested use tree. + pub list_item: Option, + // Additional fields for top level use items. + // Should we have another struct for top-level use items rather than reusing this? + visibility: Option, + attrs: Option>, +} + +impl PartialEq for UseTree { + fn eq(&self, other: &UseTree) -> bool { + self.path == other.path } +} +impl Eq for UseTree {} - match (&a.kind, &b.kind) { - (&Simple(ident_a), &Simple(ident_b)) => { - let name_a = &*a.prefix.segments.last().unwrap().identifier.name.as_str(); - let name_b = &*b.prefix.segments.last().unwrap().identifier.name.as_str(); - let name_ordering = if name_a == "self" { - if name_b == "self" { - Ordering::Equal - } else { - Ordering::Less - } - } else if name_b == "self" { - Ordering::Greater - } else { - name_a.cmp(name_b) - }; - if name_ordering == Ordering::Equal { - if ident_a.name.as_str() != name_a { - if ident_b.name.as_str() != name_b { - ident_a.name.as_str().cmp(&ident_b.name.as_str()) - } else { - Ordering::Greater - } - } else { - Ordering::Less - } - } else { - name_ordering - } +impl UseSegment { + // Clone a version of self with any top-level alias removed. + fn remove_alias(&self) -> UseSegment { + match *self { + UseSegment::Ident(ref s, _) => UseSegment::Ident(s.clone(), None), + UseSegment::Slf(_) => UseSegment::Slf(None), + UseSegment::Super(_) => UseSegment::Super(None), + _ => self.clone(), } - (&Glob, &Glob) => Ordering::Equal, - (&Simple(_), _) | (&Glob, &Nested(_)) => Ordering::Less, - (&Nested(ref a_items), &Nested(ref b_items)) => { - let mut a = a_items - .iter() - .map(|&(ref tree, _)| tree.clone()) - .collect::>(); - let mut b = b_items - .iter() - .map(|&(ref tree, _)| tree.clone()) - .collect::>(); - a.sort_by(|a, b| compare_use_trees(a, b, true)); - b.sort_by(|a, b| compare_use_trees(a, b, true)); - for comparison_pair in a.iter().zip(b.iter()) { - let ord = compare_use_trees(comparison_pair.0, comparison_pair.1, true); - if ord != Ordering::Equal { - return ord; - } - } - a.len().cmp(&b.len()) + } + + fn from_path_segment(path_seg: &ast::PathSegment) -> Option { + let name = path_seg.ident.name.as_str(); + if name == "{{root}}" { + return None; } - (&Glob, &Simple(_)) | (&Nested(_), _) => Ordering::Greater, + Some(if name == "self" { + UseSegment::Slf(None) + } else if name == "super" { + UseSegment::Super(None) + } else { + UseSegment::Ident((*name).to_owned(), None) + }) } } -fn compare_use_items(context: &RewriteContext, a: &ast::Item, b: &ast::Item) -> Option { - match (&a.node, &b.node) { - (&ast::ItemKind::Use(ref a_tree), &ast::ItemKind::Use(ref b_tree)) => { - Some(compare_use_trees(&a_tree, &b_tree, false)) +pub fn merge_use_trees(use_trees: Vec) -> Vec { + let mut result = Vec::with_capacity(use_trees.len()); + for use_tree in use_trees { + if use_tree.has_comment() || use_tree.attrs.is_some() { + result.push(use_tree); + continue; } - (&ast::ItemKind::ExternCrate(..), &ast::ItemKind::ExternCrate(..)) => { - Some(context.snippet(a.span).cmp(&context.snippet(b.span))) + + for flattened in use_tree.flatten() { + merge_use_trees_inner(&mut result, flattened); } - _ => None, } + result } -// TODO (some day) remove unused imports, expand globs, compress many single -// imports into a list import. +fn merge_use_trees_inner(trees: &mut Vec, use_tree: UseTree) { + for tree in trees.iter_mut() { + if tree.share_prefix(&use_tree) { + tree.merge(use_tree); + return; + } + } -fn rewrite_prefix(path: &ast::Path, context: &RewriteContext, shape: Shape) -> Option { - let path_str = if path.segments.last().unwrap().identifier.to_string() == "self" - && path.segments.len() > 1 - { - let path = &ast::Path { - span: path.span, - segments: path.segments[..path.segments.len() - 1].to_owned(), - }; - rewrite_path(context, PathContext::Import, None, path, shape)? - } else { - rewrite_path(context, PathContext::Import, None, path, shape)? - }; - Some(path_str) + trees.push(use_tree); } -impl Rewrite for ast::UseTree { - fn rewrite(&self, context: &RewriteContext, shape: Shape) -> Option { - match self.kind { - ast::UseTreeKind::Nested(ref items) => { - rewrite_nested_use_tree(shape, &self.prefix, items, self.span, context) - } - ast::UseTreeKind::Glob => { - let prefix_shape = shape.sub_width(3)?; - - if self.prefix.segments.len() > 0 { - let path_str = rewrite_prefix(&self.prefix, context, prefix_shape)?; - Some(format!("{}::*", path_str)) - } else { - Some("*".to_owned()) - } - } - ast::UseTreeKind::Simple(ident) => { - let ident_str = ident.to_string(); +impl fmt::Debug for UseTree { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + fmt::Display::fmt(self, f) + } +} - // 4 = " as ".len() - let prefix_shape = shape.sub_width(ident_str.len() + 4)?; - let path_str = rewrite_prefix(&self.prefix, context, prefix_shape)?; +impl fmt::Debug for UseSegment { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + fmt::Display::fmt(self, f) + } +} - if self.prefix.segments.last().unwrap().identifier == ident { - Some(path_str) - } else { - Some(format!("{} as {}", path_str, ident_str)) +impl fmt::Display for UseSegment { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + match *self { + UseSegment::Glob => write!(f, "*"), + UseSegment::Ident(ref s, _) => write!(f, "{}", s), + UseSegment::Slf(..) => write!(f, "self"), + UseSegment::Super(..) => write!(f, "super"), + UseSegment::List(ref list) => { + write!(f, "{{")?; + for (i, item) in list.iter().enumerate() { + let is_last = i == list.len() - 1; + write!(f, "{}", item)?; + if !is_last { + write!(f, ", ")?; + } } + write!(f, "}}") } } } } - -// Rewrite `use foo;` WITHOUT attributes. -fn rewrite_import( - context: &RewriteContext, - vis: &ast::Visibility, - tree: &ast::UseTree, - attrs: &[ast::Attribute], - shape: Shape, -) -> Option { - let vis = format_visibility(vis); - // 4 = `use `, 1 = `;` - let rw = shape - .offset_left(vis.len() + 4) - .and_then(|shape| shape.sub_width(1)) - .and_then(|shape| match tree.kind { - // If we have an empty nested group with no attributes, we erase it - ast::UseTreeKind::Nested(ref items) if items.is_empty() && attrs.is_empty() => { - Some("".to_owned()) +impl fmt::Display for UseTree { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + for (i, segment) in self.path.iter().enumerate() { + let is_last = i == self.path.len() - 1; + write!(f, "{}", segment)?; + if !is_last { + write!(f, "::")?; } - _ => tree.rewrite(context, shape), - }); - match rw { - Some(ref s) if !s.is_empty() => Some(format!("{}use {};", vis, s)), - _ => rw, + } + write!(f, "") } } -fn rewrite_imports( - context: &RewriteContext, - use_items: &[&ast::Item], - shape: Shape, - span: Span, -) -> Option { - let items = itemize_list( - context.codemap, - use_items.iter(), - "", - ";", - |item| item.span().lo(), - |item| item.span().hi(), - |item| { - let attrs_str = item.attrs.rewrite(context, shape)?; - - let missed_span = if item.attrs.is_empty() { - mk_sp(item.span.lo(), item.span.lo()) - } else { - mk_sp(item.attrs.last().unwrap().span.hi(), item.span.lo()) - }; - - let item_str = match item.node { - ast::ItemKind::Use(ref tree) => { - rewrite_import(context, &item.vis, tree, &item.attrs, shape)? +impl UseTree { + // Rewrite use tree with `use ` and a trailing `;`. + pub fn rewrite_top_level(&self, context: &RewriteContext, shape: Shape) -> Option { + let vis = self.visibility + .as_ref() + .map_or(Cow::from(""), |vis| ::utils::format_visibility(&vis)); + let use_str = self.rewrite(context, shape.offset_left(vis.len())?) + .map(|s| { + if s.is_empty() { + s.to_owned() + } else { + format!("{}use {};", vis, s) } - ast::ItemKind::ExternCrate(..) => rewrite_extern_crate(context, item)?, - _ => return None, - }; - - combine_strs_with_missing_comments( - context, - &attrs_str, - &item_str, - missed_span, - shape, - false, - ) - }, - span.lo(), - span.hi(), - false, - ); - let mut item_pair_vec: Vec<_> = items.zip(use_items.iter()).collect(); - item_pair_vec.sort_by(|a, b| compare_use_items(context, a.1, b.1).unwrap()); - let item_vec: Vec<_> = item_pair_vec.into_iter().map(|pair| pair.0).collect(); + })?; + if let Some(ref attrs) = self.attrs { + 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); + combine_strs_with_missing_comments(context, &attr_str, &use_str, span, shape, false) + } else { + Some(use_str) + } + } - let fmt = ListFormatting { - tactic: DefinitiveListTactic::Vertical, - separator: "", - trailing_separator: SeparatorTactic::Never, - separator_place: SeparatorPlace::Back, - shape: shape, - ends_with_newline: true, - preserve_newline: false, - config: context.config, - }; + // 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, span: Span) -> UseTree { + UseTree { + path, + span, + list_item: None, + visibility: None, + attrs: None, + } + } - write_list(&item_vec, &fmt) -} + pub fn from_ast_with_normalization( + context: &RewriteContext, + item: &ast::Item, + ) -> Option { + match item.node { + 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, + } + } -impl<'a> FmtVisitor<'a> { - pub fn format_imports(&mut self, use_items: &[&ast::Item]) { - if use_items.is_empty() { - return; + fn from_ast( + context: &RewriteContext, + a: &ast::UseTree, + list_item: Option, + visibility: Option, + opt_lo: Option, + attrs: Option>, + ) -> 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, + }; + for p in &a.prefix.segments { + if let Some(use_segment) = UseSegment::from_path_segment(p) { + result.path.push(use_segment); + } } + match a.kind { + UseTreeKind::Glob => { + result.path.push(UseSegment::Glob); + } + UseTreeKind::Nested(ref list) => { + // Extract comments between nested use items. + // This needs to be done before sorting use items. + let items: Vec<_> = 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, + ).collect(); + result.path.push(UseSegment::List( + list.iter() + .zip(items.into_iter()) + .map(|(t, list_item)| { + Self::from_ast(context, &t.0, Some(list_item), None, None, None) + }) + .collect(), + )); + } + UseTreeKind::Simple(ref rename) => { + let mut name = (*path_to_imported_ident(&a.prefix).name.as_str()).to_owned(); + let alias = rename.and_then(|ident| { + if ident == path_to_imported_ident(&a.prefix) { + None + } else { + Some(ident.to_string()) + } + }); - let lo = use_items.first().unwrap().span().lo(); - let hi = use_items.last().unwrap().span().hi(); - let span = mk_sp(lo, hi); - let rw = rewrite_imports(&self.get_context(), use_items, self.shape(), span); - self.push_rewrite(span, rw); + let segment = if &name == "self" { + UseSegment::Slf(alias) + } else if &name == "super" { + UseSegment::Super(alias) + } else { + UseSegment::Ident(name, alias) + }; + + // `name` is already in result. + result.path.pop(); + result.path.push(segment); + } + } + result } - pub fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) { - let span = item.span; - let shape = self.shape(); - let rw = rewrite_import(&self.get_context(), &item.vis, tree, &item.attrs, 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 span_end = match self.snippet(prev_span).rfind('\n') { - Some(offset) => self.last_pos + BytePos(offset as u32), - None => source!(self, span).lo(), - }; - self.format_missing(span_end); - self.last_pos = source!(self, span).hi(); + // Do the adjustments that rustfmt does elsewhere to use paths. + pub 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 { + _ if self.attrs.is_some() => (), + UseSegment::List(ref list) if list.is_empty() => { + self.path = vec![]; + return self; } - Some(ref s) => { - self.format_missing_with_indent(source!(self, span).lo()); - self.buffer.push_str(s); - self.last_pos = source!(self, span).hi(); + UseSegment::Slf(None) if self.path.is_empty() && self.visibility.is_some() => { + self.path = vec![]; + return self; } - None => { - self.format_missing_with_indent(source!(self, span).lo()); - self.format_missing(source!(self, span).hi()); + _ => (), + } + + // Normalise foo::self -> foo. + if let UseSegment::Slf(None) = last { + if !self.path.is_empty() { + return self; } } - } -} -fn rewrite_nested_use_tree_single(path_str: String, tree: &ast::UseTree) -> String { - if let ast::UseTreeKind::Simple(rename) = tree.kind { - let ident = tree.prefix.segments.last().unwrap().identifier; - let mut item_str = ident.name.to_string(); - if item_str == "self" { - item_str = "".to_owned(); + // Normalise foo::self as bar -> foo as bar. + if let UseSegment::Slf(_) = last { + match self.path.last() { + None => {} + Some(UseSegment::Ident(_, None)) => { + aliased_self = true; + } + _ => unreachable!(), + } } - let path_item_str = if path_str.is_empty() { - if item_str.is_empty() { - "self".to_owned() - } else { - item_str + let mut done = false; + if aliased_self { + match self.path.last_mut() { + Some(UseSegment::Ident(_, ref mut old_rename)) => { + assert!(old_rename.is_none()); + if let UseSegment::Slf(Some(rename)) = last.clone() { + *old_rename = Some(rename); + done = true; + } + } + _ => unreachable!(), } - } else if item_str.is_empty() { - path_str - } else { - format!("{}::{}", path_str, item_str) - }; + } - if ident == rename { - path_item_str - } else { - format!("{} as {}", path_item_str, rename) + if done { + return self; } - } else { - unimplemented!("`use_nested_groups` is not yet fully supported"); - } -} -fn rewrite_nested_use_tree_item(tree: &&ast::UseTree) -> Option { - Some(if let ast::UseTreeKind::Simple(rename) = tree.kind { - let ident = tree.prefix.segments.last().unwrap().identifier; + // Normalise foo::{bar} -> foo::bar + if let UseSegment::List(ref list) = last { + if list.len() == 1 { + normalize_sole_list = true; + } + } - if ident == rename { - ident.name.to_string() - } else { - format!("{} as {}", ident.name.to_string(), rename) + if normalize_sole_list { + match last { + UseSegment::List(list) => { + for seg in &list[0].path { + self.path.push(seg.clone()); + } + return self.normalize(); + } + _ => unreachable!(), + } } - } else { - unimplemented!("`use_nested_groups` is not yet fully supported"); - }) -} -#[derive(Eq, PartialEq)] -enum ImportItem<'a> { - // `self` or `self as a` - SelfImport(&'a str), - // name_one, name_two, ... - SnakeCase(&'a str), - // NameOne, NameTwo, ... - CamelCase(&'a str), - // NAME_ONE, NAME_TWO, ... - AllCaps(&'a str), - // Failed to format the import item - Invalid, -} + // Recursively normalize elements of a list use (including sorting the list). + if let UseSegment::List(list) = last { + let mut list = list.into_iter() + .map(|ut| ut.normalize()) + .collect::>(); + list.sort(); + last = UseSegment::List(list); + } -impl<'a> ImportItem<'a> { - fn from_str(s: &str) -> ImportItem { - if s == "self" || s.starts_with("self as") { - ImportItem::SelfImport(s) - } else if s.chars().all(|c| c.is_lowercase() || c == '_' || c == ' ') { - ImportItem::SnakeCase(s) - } else if s.chars().all(|c| c.is_uppercase() || c == '_' || c == ' ') { - ImportItem::AllCaps(s) - } else { - ImportItem::CamelCase(s) + self.path.push(last); + self + } + + fn has_comment(&self) -> bool { + self.list_item.as_ref().map_or(false, ListItem::has_comment) + } + + fn same_visibility(&self, other: &UseTree) -> bool { + match (&self.visibility, &other.visibility) { + ( + Some(codemap::Spanned { + node: ast::VisibilityKind::Inherited, + .. + }), + None, + ) + | ( + None, + Some(codemap::Spanned { + node: ast::VisibilityKind::Inherited, + .. + }), + ) + | (None, None) => true, + ( + Some(codemap::Spanned { node: lnode, .. }), + Some(codemap::Spanned { node: rnode, .. }), + ) => lnode == rnode, + _ => false, } } - fn from_opt_str(s: Option<&String>) -> ImportItem { - s.map_or(ImportItem::Invalid, |s| ImportItem::from_str(s)) + fn share_prefix(&self, other: &UseTree) -> bool { + if self.path.is_empty() || other.path.is_empty() || self.attrs.is_some() + || !self.same_visibility(other) + { + false + } else { + self.path[0] == other.path[0] + } } - fn to_str(&self) -> Option<&str> { - match *self { - ImportItem::SelfImport(s) - | ImportItem::SnakeCase(s) - | ImportItem::CamelCase(s) - | ImportItem::AllCaps(s) => Some(s), - ImportItem::Invalid => None, + fn flatten(self) -> Vec { + if self.path.is_empty() { + return vec![self]; + } + match self.path.clone().last().unwrap() { + UseSegment::List(list) => { + let prefix = &self.path[..self.path.len() - 1]; + let mut result = vec![]; + for nested_use_tree in list { + for mut flattend in &mut nested_use_tree.clone().flatten() { + 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(), + attrs: None, + }); + } + } + + result + } + _ => vec![self], } } - fn to_u32(&self) -> u32 { - match *self { - ImportItem::SelfImport(..) => 0, - ImportItem::SnakeCase(..) => 1, - ImportItem::CamelCase(..) => 2, - ImportItem::AllCaps(..) => 3, - ImportItem::Invalid => 4, + fn merge(&mut self, other: UseTree) { + let mut new_path = vec![]; + for (mut a, b) in self.path + .clone() + .iter_mut() + .zip(other.path.clone().into_iter()) + { + if *a == b { + new_path.push(b); + } else { + break; + } + } + if let Some(merged) = merge_rest(&self.path, &other.path, new_path.len()) { + new_path.push(merged); + self.span = self.span.to(other.span); } + self.path = new_path; } } -impl<'a> PartialOrd for ImportItem<'a> { - fn partial_cmp(&self, other: &ImportItem<'a>) -> Option { +fn merge_rest(a: &[UseSegment], b: &[UseSegment], len: usize) -> Option { + let a_rest = &a[len..]; + let b_rest = &b[len..]; + if a_rest.is_empty() && b_rest.is_empty() { + return None; + } + if a_rest.is_empty() { + return Some(UseSegment::List(vec![ + UseTree::from_path(vec![UseSegment::Slf(None)], DUMMY_SP), + UseTree::from_path(b_rest.to_vec(), DUMMY_SP), + ])); + } + if b_rest.is_empty() { + return Some(UseSegment::List(vec![ + UseTree::from_path(vec![UseSegment::Slf(None)], DUMMY_SP), + UseTree::from_path(a_rest.to_vec(), DUMMY_SP), + ])); + } + if let UseSegment::List(mut list) = a_rest[0].clone() { + merge_use_trees_inner(&mut list, UseTree::from_path(b_rest.to_vec(), DUMMY_SP)); + list.sort(); + return Some(UseSegment::List(list.clone())); + } + let mut list = vec![ + UseTree::from_path(a_rest.to_vec(), DUMMY_SP), + UseTree::from_path(b_rest.to_vec(), DUMMY_SP), + ]; + list.sort(); + Some(UseSegment::List(list)) +} + +impl PartialOrd for UseSegment { + fn partial_cmp(&self, other: &UseSegment) -> Option { + Some(self.cmp(other)) + } +} +impl PartialOrd for UseTree { + fn partial_cmp(&self, other: &UseTree) -> Option { Some(self.cmp(other)) } } +impl Ord for UseSegment { + fn cmp(&self, other: &UseSegment) -> Ordering { + use self::UseSegment::*; -impl<'a> Ord for ImportItem<'a> { - fn cmp(&self, other: &ImportItem<'a>) -> Ordering { - let res = self.to_u32().cmp(&other.to_u32()); - if res != Ordering::Equal { - return res; + fn is_upper_snake_case(s: &str) -> bool { + s.chars().all(|c| c.is_uppercase() || c == '_') + } + + match (self, other) { + (&Slf(ref a), &Slf(ref b)) | (&Super(ref a), &Super(ref b)) => a.cmp(b), + (&Glob, &Glob) => Ordering::Equal, + (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => { + // 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; + } + if aa.is_none() && ab.is_some() { + return Ordering::Less; + } + if aa.is_some() && ab.is_none() { + return Ordering::Greater; + } + aa.cmp(ab) + } + (&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, + (&Ident(..), _) => Ordering::Less, + (_, &Ident(..)) => Ordering::Greater, + (&Glob, _) => Ordering::Less, + (_, &Glob) => Ordering::Greater, } - self.to_str().map_or(Ordering::Greater, |self_str| { - other - .to_str() - .map_or(Ordering::Less, |other_str| self_str.cmp(other_str)) - }) + } +} +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()) } } -// Pretty prints a multi-item import. -// If the path list is empty, it leaves the braces empty. fn rewrite_nested_use_tree( - shape: Shape, - path: &ast::Path, - trees: &[(ast::UseTree, ast::NodeId)], - span: Span, context: &RewriteContext, + use_tree_list: &[UseTree], + shape: Shape, ) -> Option { - // Returns a different option to distinguish `::foo` and `foo` - let path_str = rewrite_path(context, PathContext::Import, None, path, shape)?; - - match trees.len() { - 0 => { - return rewrite_path(context, PathContext::Import, None, path, shape) - .map(|path_str| format!("{}::{{}}", path_str)); + 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)?)); } - // TODO: fix this - 1 => return Some(rewrite_nested_use_tree_single(path_str, &trees[0].0)), - _ => (), } - - let path_str = if path_str.is_empty() { - path_str + let has_nested_list = use_tree_list.iter().any(|use_segment| { + use_segment + .path + .last() + .map_or(false, |last_segment| match last_segment { + UseSegment::List(..) => true, + _ => false, + }) + }); + let (tactic, remaining_width) = if has_nested_list { + (DefinitiveListTactic::Vertical, 0) } else { - format!("{}::", path_str) - }; - - // 2 = "{}" - let remaining_width = shape.width.checked_sub(path_str.len() + 2).unwrap_or(0); - - let mut items = { - // Dummy value, see explanation below. - let mut items = vec![ListItem::from_str("")]; - let iter = itemize_list( - context.codemap, - trees.iter().map(|ref tree| &tree.0), - "}", - ",", - |tree| tree.span.lo(), - |tree| tree.span.hi(), - rewrite_nested_use_tree_item, - context.codemap.span_after(span, "{"), - span.hi(), - false, + let remaining_width = shape.width.checked_sub(2).unwrap_or(0); + let tactic = definitive_tactic( + &list_items, + context.config.imports_layout(), + Separator::Comma, + remaining_width, ); - items.extend(iter); - items - }; - - // We prefixed the item list with a dummy value so that we can - // potentially move "self" to the front of the vector without touching - // the rest of the items. - let has_self = move_self_to_front(&mut items); - let first_index = if has_self { 0 } else { 1 }; - - if context.config.reorder_imported_names() { - items[1..].sort_by(|a, b| { - let a = ImportItem::from_opt_str(a.item.as_ref()); - let b = ImportItem::from_opt_str(b.item.as_ref()); - a.cmp(&b) - }); - } - - let tactic = definitive_tactic( - &items[first_index..], - context.config.imports_layout(), - Separator::Comma, - remaining_width, - ); - - let nested_indent = match context.config.imports_indent() { - IndentStyle::Block => shape.indent.block_indent(context.config), - // 1 = `{` - IndentStyle::Visual => shape.visual_indent(path_str.len() + 1).indent, - }; - - let nested_shape = match context.config.imports_indent() { - IndentStyle::Block => Shape::indented(nested_indent, context.config), - IndentStyle::Visual => Shape::legacy(remaining_width, nested_indent), + (tactic, remaining_width) }; let ends_with_newline = context.config.imports_indent() == IndentStyle::Block && tactic != DefinitiveListTactic::Horizontal; - let fmt = ListFormatting { - tactic: tactic, + tactic, separator: ",", trailing_separator: if ends_with_newline { context.config.trailing_comma() @@ -507,37 +707,306 @@ fn rewrite_nested_use_tree( }, separator_place: SeparatorPlace::Back, shape: nested_shape, - ends_with_newline: ends_with_newline, + ends_with_newline, preserve_newline: true, config: context.config, }; - let list_str = write_list(&items[first_index..], &fmt)?; - let result = if list_str.contains('\n') && context.config.imports_indent() == IndentStyle::Block + 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{}}}", - path_str, + "{{\n{}{}\n{}}}", nested_shape.indent.to_string(context.config), list_str, shape.indent.to_string(context.config) ) } else { - format!("{}{{{}}}", path_str, list_str) + format!("{{{}}}", list_str) }; + Some(result) } -// Returns true when self item was found. -fn move_self_to_front(items: &mut Vec) -> bool { - match items - .iter() - .position(|item| item.item.as_ref().map(|x| &x[..]) == Some("self")) - { - Some(pos) => { - items[0] = items.remove(pos); - true +impl Rewrite for UseSegment { + fn rewrite(&self, context: &RewriteContext, shape: Shape) -> Option { + Some(match *self { + UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename), + UseSegment::Ident(ref ident, None) => ident.clone(), + UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename), + UseSegment::Slf(None) => "self".to_owned(), + UseSegment::Super(Some(ref rename)) => format!("super as {}", rename), + UseSegment::Super(None) => "super".to_owned(), + UseSegment::Glob => "*".to_owned(), + UseSegment::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 { + let mut result = String::with_capacity(256); + let mut iter = self.path.iter().peekable(); + while let Some(ref 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) + } +} + +#[cfg(test)] +mod test { + use super::*; + use syntax::codemap::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>, + } + + impl<'a> Parser<'a> { + fn bump(&mut self) { + self.input.next().unwrap(); + } + fn eat(&mut self, c: char) { + assert!(self.input.next().unwrap() == c); + } + fn push_segment( + result: &mut Vec, + buf: &mut String, + alias_buf: &mut Option, + ) { + if !buf.is_empty() { + let mut alias = None; + swap(alias_buf, &mut alias); + if buf == "self" { + result.push(UseSegment::Slf(alias)); + *buf = String::new(); + *alias_buf = None; + } else if buf == "super" { + result.push(UseSegment::Super(alias)); + *buf = String::new(); + *alias_buf = None; + } else { + let mut name = String::new(); + swap(buf, &mut name); + result.push(UseSegment::Ident(name, alias)); + } + } + } + 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(); + result.push(UseSegment::List(self.parse_list())); + self.eat('}'); + } + '*' => { + assert!(buf.is_empty()); + self.bump(); + result.push(UseSegment::Glob); + } + ':' => { + 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 { + 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(), + }; + parser.parse_in_list() + } + + macro parse_use_trees($($s:expr),* $(,)*) { + vec![ + $(parse_use_tree($s),)* + ] + } + + #[test] + fn test_use_tree_merge() { + macro test_merge([$($input:expr),* $(,)*], [$($output:expr),* $(,)*]) { + assert_eq!( + merge_use_trees(parse_use_trees!($($input,)*)), + parse_use_trees!($($output,)*), + ); } - None => false, + + test_merge!(["a::b::{c, d}", "a::b::{e, f}"], ["a::b::{c, d, e, f}"]); + test_merge!(["a::b::c", "a::b"], ["a::b::{self, c}"]); + test_merge!(["a::b", "a::b"], ["a::b"]); + test_merge!(["a", "a::b", "a::b::c"], ["a::{self, b::{self, c}}"]); + test_merge!( + ["a::{b::{self, c}, d::e}", "a::d::f"], + ["a::{b::{self, c}, d::{e, f}}"] + ); + test_merge!( + ["a::d::f", "a::{b::{self, c}, d::e}"], + ["a::{b::{self, c}, d::{e, f}}"] + ); + test_merge!( + ["a::{c, d, b}", "a::{d, e, b, a, f}", "a::{f, g, c}"], + ["a::{a, b, c, d, e, f, g}"] + ); + } + + #[test] + fn test_use_tree_flatten() { + assert_eq!( + parse_use_tree("a::b::{c, d, e, f}").flatten(), + 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(), + 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")); + 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::{self as bar}").normalize() + < parse_use_tree("foo::{qux 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() + ); } }