2 use std::cmp::Ordering;
5 use core::hash::{Hash, Hasher};
7 use itertools::Itertools;
9 use rustc_ast::ast::{self, UseTreeKind};
12 BytePos, Span, DUMMY_SP,
15 use crate::comment::combine_strs_with_missing_comments;
16 use crate::config::lists::*;
17 use crate::config::ImportGranularity;
18 use crate::config::{Edition, IndentStyle, Version};
20 definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator,
22 use crate::rewrite::{Rewrite, RewriteContext};
23 use crate::shape::Shape;
24 use crate::source_map::SpanUtils;
25 use crate::spanned::Spanned;
26 use crate::utils::{is_same_visibility, mk_sp, rewrite_ident};
27 use crate::visitor::FmtVisitor;
29 /// Returns a name imported by a `use` declaration.
30 /// E.g., returns `Ordering` for `std::cmp::Ordering` and `self` for `std::cmp::self`.
31 pub(crate) fn path_to_imported_ident(path: &ast::Path) -> symbol::Ident {
32 path.segments.last().unwrap().ident
35 impl<'a> FmtVisitor<'a> {
36 pub(crate) fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) {
37 let span = item.span();
38 let shape = self.shape();
39 let rw = UseTree::from_ast(
43 Some(item.vis.clone()),
45 Some(item.attrs.clone()),
47 .rewrite_top_level(&self.get_context(), shape);
49 Some(ref s) if s.is_empty() => {
50 // Format up to last newline
51 let prev_span = mk_sp(self.last_pos, source!(self, span).lo());
52 let trimmed_snippet = self.snippet(prev_span).trim_end();
53 let span_end = self.last_pos + BytePos(trimmed_snippet.len() as u32);
54 self.format_missing(span_end);
55 // We have an excessive newline from the removed import.
56 if self.buffer.ends_with('\n') {
58 self.line_number -= 1;
60 self.last_pos = source!(self, span).hi();
63 self.format_missing_with_indent(source!(self, span).lo());
65 self.last_pos = source!(self, span).hi();
68 self.format_missing_with_indent(source!(self, span).lo());
69 self.format_missing(source!(self, span).hi());
75 // Ordering of imports
77 // We order imports by translating to our own representation and then sorting.
78 // The Rust AST data structures are really bad for this. Rustfmt applies a bunch
79 // of normalisations to imports and since we want to sort based on the result
80 // of these (and to maintain idempotence) we must apply the same normalisations
81 // to the data structures for sorting.
83 // We sort `self` and `super` before other imports, then identifier imports,
84 // then glob imports, then lists of imports. We do not take aliases into account
85 // when ordering unless the imports are identical except for the alias (rare in
88 // FIXME(#2531): we should unify the comparison code here with the formatting
89 // code elsewhere since we are essentially string-ifying twice. Furthermore, by
90 // parsing to our own format on comparison, we repeat a lot of work when
93 // FIXME we do a lot of allocation to make our own representation.
94 #[derive(Clone, Eq, Hash, PartialEq)]
95 pub(crate) enum UseSegmentKind {
96 Ident(String, Option<String>),
98 Super(Option<String>),
99 Crate(Option<String>),
104 #[derive(Clone, Eq, PartialEq)]
105 pub(crate) struct UseSegment {
106 pub(crate) kind: UseSegmentKind,
107 pub(crate) version: Version,
111 pub(crate) struct UseTree {
112 pub(crate) path: Vec<UseSegment>,
113 pub(crate) span: Span,
114 // Comment information within nested use tree.
115 pub(crate) list_item: Option<ListItem>,
116 // Additional fields for top level use items.
117 // Should we have another struct for top-level use items rather than reusing this?
118 visibility: Option<ast::Visibility>,
119 attrs: Option<Vec<ast::Attribute>>,
122 impl PartialEq for UseTree {
123 fn eq(&self, other: &UseTree) -> bool {
124 self.path == other.path
127 impl Eq for UseTree {}
129 impl Spanned for UseTree {
130 fn span(&self) -> Span {
131 let lo = if let Some(ref attrs) = self.attrs {
132 attrs.iter().next().map_or(self.span.lo(), |a| a.span.lo())
136 mk_sp(lo, self.span.hi())
141 // Clone a version of self with any top-level alias removed.
142 fn remove_alias(&self) -> UseSegment {
143 let kind = match self.kind {
144 UseSegmentKind::Ident(ref s, _) => UseSegmentKind::Ident(s.clone(), None),
145 UseSegmentKind::Slf(_) => UseSegmentKind::Slf(None),
146 UseSegmentKind::Super(_) => UseSegmentKind::Super(None),
147 UseSegmentKind::Crate(_) => UseSegmentKind::Crate(None),
148 _ => return self.clone(),
152 version: self.version,
156 // Check if self == other with their aliases removed.
157 fn equal_except_alias(&self, other: &Self) -> bool {
158 match (&self.kind, &other.kind) {
159 (UseSegmentKind::Ident(ref s1, _), UseSegmentKind::Ident(ref s2, _)) => s1 == s2,
160 (UseSegmentKind::Slf(_), UseSegmentKind::Slf(_))
161 | (UseSegmentKind::Super(_), UseSegmentKind::Super(_))
162 | (UseSegmentKind::Crate(_), UseSegmentKind::Crate(_))
163 | (UseSegmentKind::Glob, UseSegmentKind::Glob) => true,
164 (UseSegmentKind::List(ref list1), UseSegmentKind::List(ref list2)) => list1 == list2,
169 fn get_alias(&self) -> Option<&str> {
171 UseSegmentKind::Ident(_, a)
172 | UseSegmentKind::Slf(a)
173 | UseSegmentKind::Super(a)
174 | UseSegmentKind::Crate(a) => a.as_deref(),
179 fn from_path_segment(
180 context: &RewriteContext<'_>,
181 path_seg: &ast::PathSegment,
183 ) -> Option<UseSegment> {
184 let name = rewrite_ident(context, path_seg.ident);
185 if name.is_empty() || name == "{{root}}" {
188 let kind = match name {
189 "self" => UseSegmentKind::Slf(None),
190 "super" => UseSegmentKind::Super(None),
191 "crate" => UseSegmentKind::Crate(None),
193 let mod_sep = if modsep { "::" } else { "" };
194 UseSegmentKind::Ident(format!("{}{}", mod_sep, name), None)
200 version: context.config.version(),
204 fn contains_comment(&self) -> bool {
205 if let UseSegmentKind::List(list) = &self.kind {
206 list.iter().any(|subtree| subtree.contains_comment())
213 pub(crate) fn normalize_use_trees_with_granularity(
214 use_trees: Vec<UseTree>,
215 import_granularity: ImportGranularity,
217 let merge_by = match import_granularity {
218 ImportGranularity::Item => return flatten_use_trees(use_trees, ImportGranularity::Item),
219 ImportGranularity::Preserve => return use_trees,
220 ImportGranularity::Crate => SharedPrefix::Crate,
221 ImportGranularity::Module => SharedPrefix::Module,
222 ImportGranularity::One => SharedPrefix::One,
225 let mut result = Vec::with_capacity(use_trees.len());
226 for use_tree in use_trees {
227 if use_tree.contains_comment() || use_tree.attrs.is_some() {
228 result.push(use_tree);
232 for mut flattened in use_tree.flatten(import_granularity) {
233 if let Some(tree) = result
235 .find(|tree| tree.share_prefix(&flattened, merge_by))
237 tree.merge(&flattened, merge_by);
239 // If this is the first tree with this prefix, handle potential trailing ::self
240 if merge_by == SharedPrefix::Module {
241 flattened = flattened.nest_trailing_self();
243 result.push(flattened);
250 fn flatten_use_trees(
251 use_trees: Vec<UseTree>,
252 import_granularity: ImportGranularity,
254 // Return non-sorted single occurance of the use-trees text string;
255 // order is by first occurance of the use-tree.
258 .flat_map(|tree| tree.flatten(import_granularity))
259 .map(UseTree::nest_trailing_self)
264 impl fmt::Debug for UseTree {
265 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
266 fmt::Display::fmt(self, f)
270 impl fmt::Debug for UseSegment {
271 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
272 fmt::Display::fmt(&self.kind, f)
276 impl fmt::Display for UseSegment {
277 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
278 fmt::Display::fmt(&self.kind, f)
282 impl Hash for UseSegment {
283 fn hash<H: Hasher>(&self, state: &mut H) {
284 self.kind.hash(state);
288 impl fmt::Debug for UseSegmentKind {
289 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
290 fmt::Display::fmt(self, f)
294 impl fmt::Display for UseSegmentKind {
295 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
297 UseSegmentKind::Glob => write!(f, "*"),
298 UseSegmentKind::Ident(ref s, Some(ref alias)) => write!(f, "{} as {}", s, alias),
299 UseSegmentKind::Ident(ref s, None) => write!(f, "{}", s),
300 UseSegmentKind::Slf(..) => write!(f, "self"),
301 UseSegmentKind::Super(..) => write!(f, "super"),
302 UseSegmentKind::Crate(..) => write!(f, "crate"),
303 UseSegmentKind::List(ref list) => {
305 for (i, item) in list.iter().enumerate() {
309 write!(f, "{}", item)?;
316 impl fmt::Display for UseTree {
317 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
318 for (i, segment) in self.path.iter().enumerate() {
322 write!(f, "{}", segment)?;
329 // Rewrite use tree with `use ` and a trailing `;`.
330 pub(crate) fn rewrite_top_level(
332 context: &RewriteContext<'_>,
334 ) -> Option<String> {
335 let vis = self.visibility.as_ref().map_or(Cow::from(""), |vis| {
336 crate::utils::format_visibility(context, vis)
339 .rewrite(context, shape.offset_left(vis.len())?)
344 format!("{}use {};", vis, s)
348 Some(ref attrs) if !attrs.is_empty() => {
349 let attr_str = attrs.rewrite(context, shape)?;
350 let lo = attrs.last().as_ref()?.span.hi();
351 let hi = self.span.lo();
352 let span = mk_sp(lo, hi);
354 let allow_extend = if attrs.len() == 1 {
355 let line_len = attr_str.len() + 1 + use_str.len();
356 !attrs.first().unwrap().is_doc_comment()
357 && context.config.inline_attribute_width() >= line_len
362 combine_strs_with_missing_comments(
375 // FIXME: Use correct span?
376 // The given span is essentially incorrect, since we are reconstructing
377 // use-statements. This should not be a problem, though, since we have
378 // already tried to extract comment and observed that there are no comment
379 // around the given use item, and the span will not be used afterward.
380 fn from_path(path: Vec<UseSegment>, span: Span) -> UseTree {
390 pub(crate) fn from_ast_with_normalization(
391 context: &RewriteContext<'_>,
393 ) -> Option<UseTree> {
395 ast::ItemKind::Use(ref use_tree) => Some(
400 Some(item.vis.clone()),
401 Some(item.span.lo()),
402 if item.attrs.is_empty() {
405 Some(item.attrs.clone())
415 context: &RewriteContext<'_>,
417 list_item: Option<ListItem>,
418 visibility: Option<ast::Visibility>,
419 opt_lo: Option<BytePos>,
420 attrs: Option<Vec<ast::Attribute>>,
422 let span = if let Some(lo) = opt_lo {
423 mk_sp(lo, a.span.hi())
427 let mut result = UseTree {
436 context.config.edition() >= Edition::Edition2018 && a.prefix.is_global();
438 let mut modsep = leading_modsep;
440 for p in &a.prefix.segments {
441 if let Some(use_segment) = UseSegment::from_path_segment(context, p, modsep) {
442 result.path.push(use_segment);
447 let version = context.config.version();
450 UseTreeKind::Glob => {
451 // in case of a global path and the glob starts at the root, e.g., "::*"
452 if a.prefix.segments.len() == 1 && leading_modsep {
453 let kind = UseSegmentKind::Ident("".to_owned(), None);
454 result.path.push(UseSegment { kind, version });
456 result.path.push(UseSegment {
457 kind: UseSegmentKind::Glob,
461 UseTreeKind::Nested(ref list) => {
462 // Extract comments between nested use items.
463 // This needs to be done before sorting use items.
464 let items = itemize_list(
465 context.snippet_provider,
466 list.iter().map(|(tree, _)| tree),
469 |tree| tree.span.lo(),
470 |tree| tree.span.hi(),
471 |_| Some("".to_owned()), // We only need comments for now.
472 context.snippet_provider.span_after(a.span, "{"),
477 // in case of a global path and the nested list starts at the root,
478 // e.g., "::{foo, bar}"
479 if a.prefix.segments.len() == 1 && leading_modsep {
480 let kind = UseSegmentKind::Ident("".to_owned(), None);
481 result.path.push(UseSegment { kind, version });
483 let kind = UseSegmentKind::List(
486 .map(|(t, list_item)| {
487 Self::from_ast(context, &t.0, Some(list_item), None, None, None)
491 result.path.push(UseSegment { kind, version });
493 UseTreeKind::Simple(ref rename, ..) => {
494 // If the path has leading double colons and is composed of only 2 segments, then we
495 // bypass the call to path_to_imported_ident which would get only the ident and
496 // lose the path root, e.g., `that` in `::that`.
497 // The span of `a.prefix` contains the leading colons.
498 let name = if a.prefix.segments.len() == 2 && leading_modsep {
499 context.snippet(a.prefix.span).to_owned()
501 rewrite_ident(context, path_to_imported_ident(&a.prefix)).to_owned()
503 let alias = rename.and_then(|ident| {
504 if ident.name == sym::underscore_imports {
507 } else if ident == path_to_imported_ident(&a.prefix) {
510 Some(rewrite_ident(context, ident).to_owned())
513 let kind = match name.as_ref() {
514 "self" => UseSegmentKind::Slf(alias),
515 "super" => UseSegmentKind::Super(alias),
516 "crate" => UseSegmentKind::Crate(alias),
517 _ => UseSegmentKind::Ident(name, alias),
520 let segment = UseSegment { kind, version };
522 // `name` is already in result.
524 result.path.push(segment);
530 // Do the adjustments that rustfmt does elsewhere to use paths.
531 pub(crate) fn normalize(mut self) -> UseTree {
532 let mut last = self.path.pop().expect("Empty use tree?");
533 // Hack around borrow checker.
534 let mut normalize_sole_list = false;
535 let mut aliased_self = false;
537 // Remove foo::{} or self without attributes.
539 _ if self.attrs.is_some() => (),
540 UseSegmentKind::List(ref list) if list.is_empty() => {
544 UseSegmentKind::Slf(None) if self.path.is_empty() && self.visibility.is_some() => {
551 // Normalise foo::self -> foo.
552 if let UseSegmentKind::Slf(None) = last.kind {
553 if !self.path.is_empty() {
558 // Normalise foo::self as bar -> foo as bar.
559 if let UseSegmentKind::Slf(_) = last.kind {
560 if let Some(UseSegment {
561 kind: UseSegmentKind::Ident(_, None),
563 }) = self.path.last()
569 let mut done = false;
571 match self.path.last_mut() {
573 kind: UseSegmentKind::Ident(_, ref mut old_rename),
576 assert!(old_rename.is_none());
577 if let UseSegmentKind::Slf(Some(rename)) = last.clone().kind {
578 *old_rename = Some(rename);
590 // Normalise foo::{bar} -> foo::bar
591 if let UseSegmentKind::List(ref list) = last.kind {
592 if list.len() == 1 && list[0].to_string() != "self" {
593 normalize_sole_list = true;
597 if normalize_sole_list {
599 UseSegmentKind::List(list) => {
600 for seg in &list[0].path {
601 self.path.push(seg.clone());
603 return self.normalize();
609 // Recursively normalize elements of a list use (including sorting the list).
610 if let UseSegmentKind::List(list) = last.kind {
611 let mut list = list.into_iter().map(UseTree::normalize).collect::<Vec<_>>();
614 kind: UseSegmentKind::List(list),
615 version: last.version,
619 self.path.push(last);
623 fn has_comment(&self) -> bool {
624 self.list_item.as_ref().map_or(false, ListItem::has_comment)
627 fn contains_comment(&self) -> bool {
628 self.has_comment() || self.path.iter().any(|path| path.contains_comment())
631 fn same_visibility(&self, other: &UseTree) -> bool {
632 match (&self.visibility, &other.visibility) {
634 Some(ast::Visibility {
635 kind: ast::VisibilityKind::Inherited,
642 Some(ast::Visibility {
643 kind: ast::VisibilityKind::Inherited,
647 | (None, None) => true,
648 (Some(ref a), Some(ref b)) => is_same_visibility(a, b),
653 fn share_prefix(&self, other: &UseTree, shared_prefix: SharedPrefix) -> bool {
654 if self.path.is_empty()
655 || other.path.is_empty()
656 || self.attrs.is_some()
657 || self.contains_comment()
658 || !self.same_visibility(other)
662 match shared_prefix {
663 SharedPrefix::Crate => self.path[0] == other.path[0],
664 SharedPrefix::Module => {
665 self.path[..self.path.len() - 1] == other.path[..other.path.len() - 1]
667 SharedPrefix::One => true,
672 fn flatten(self, import_granularity: ImportGranularity) -> Vec<UseTree> {
673 if self.path.is_empty() || self.contains_comment() {
676 match &self.path.clone().last().unwrap().kind {
677 UseSegmentKind::List(list) => {
678 if list.len() == 1 && list[0].path.len() == 1 {
679 if let UseSegmentKind::Slf(..) = list[0].path[0].kind {
683 let prefix = &self.path[..self.path.len() - 1];
684 let mut result = vec![];
685 for nested_use_tree in list {
686 for flattend in &mut nested_use_tree.clone().flatten(import_granularity) {
687 let mut new_path = prefix.to_vec();
688 new_path.append(&mut flattend.path);
689 result.push(UseTree {
693 visibility: self.visibility.clone(),
694 // only retain attributes for `ImportGranularity::Item`
695 attrs: match import_granularity {
696 ImportGranularity::Item => self.attrs.clone(),
709 fn merge(&mut self, other: &UseTree, merge_by: SharedPrefix) {
711 for (a, b) in self.path.iter().zip(other.path.iter()) {
712 // only discard the alias at the root of the tree
713 if (prefix == 0 && a.equal_except_alias(b)) || a == b {
719 if let Some(new_path) = merge_rest(&self.path, &other.path, prefix, merge_by) {
720 self.path = new_path;
721 self.span = self.span.to(other.span);
725 /// If this tree ends in `::self`, rewrite it to `::{self}`.
726 fn nest_trailing_self(mut self) -> UseTree {
727 if let Some(UseSegment {
728 kind: UseSegmentKind::Slf(..),
730 }) = self.path.last()
732 let self_segment = self.path.pop().unwrap();
733 let version = self_segment.version;
734 let kind = UseSegmentKind::List(vec![UseTree::from_path(vec![self_segment], DUMMY_SP)]);
735 self.path.push(UseSegment { kind, version });
745 merge_by: SharedPrefix,
746 ) -> Option<Vec<UseSegment>> {
747 if a.len() == len && b.len() == len {
750 if a.len() != len && b.len() != len {
751 let version = a[len].version;
752 if let UseSegmentKind::List(ref list) = a[len].kind {
753 let mut list = list.clone();
754 merge_use_trees_inner(
756 UseTree::from_path(b[len..].to_vec(), DUMMY_SP),
759 let mut new_path = b[..len].to_vec();
760 let kind = UseSegmentKind::List(list);
761 new_path.push(UseSegment { kind, version });
762 return Some(new_path);
765 let (common, rest) = if a.len() == len {
770 let kind = UseSegmentKind::Slf(common.get_alias().map(ToString::to_string));
771 let version = a[0].version;
772 let mut list = vec![UseTree::from_path(
773 vec![UseSegment { kind, version }],
779 kind: UseSegmentKind::List(rest_list),
782 ] => list.extend(rest_list.clone()),
783 _ => list.push(UseTree::from_path(rest.to_vec(), DUMMY_SP)),
788 kind: UseSegmentKind::List(list),
796 UseTree::from_path(a[len..].to_vec(), DUMMY_SP),
797 UseTree::from_path(b[len..].to_vec(), DUMMY_SP),
800 let mut new_path = b[..len].to_vec();
801 let kind = UseSegmentKind::List(list);
802 let version = a[0].version;
803 new_path.push(UseSegment { kind, version });
807 fn merge_use_trees_inner(trees: &mut Vec<UseTree>, use_tree: UseTree, merge_by: SharedPrefix) {
808 struct SimilarTree<'a> {
811 tree: &'a mut UseTree,
814 let similar_trees = trees.iter_mut().filter_map(|tree| {
815 if tree.share_prefix(&use_tree, merge_by) {
816 // In the case of `SharedPrefix::One`, `similarity` is used for deciding with which
817 // tree `use_tree` should be merge.
818 // In other cases `similarity` won't be used, so set it to `0` as a dummy value.
819 let similarity = if merge_by == SharedPrefix::One {
823 .take_while(|(a, b)| a.equal_except_alias(b))
829 let path_len = tree.path.len();
840 if use_tree.path.len() == 1 && merge_by == SharedPrefix::Crate {
841 if let Some(tree) = similar_trees.min_by_key(|tree| tree.path_len) {
842 if tree.path_len == 1 {
846 } else if merge_by == SharedPrefix::One {
847 if let Some(sim_tree) = similar_trees.max_by_key(|tree| tree.similarity) {
848 if sim_tree.similarity > 0 {
849 sim_tree.tree.merge(&use_tree, merge_by);
853 } else if let Some(sim_tree) = similar_trees.max_by_key(|tree| tree.path_len) {
854 if sim_tree.path_len > 1 {
855 sim_tree.tree.merge(&use_tree, merge_by);
859 trees.push(use_tree);
863 impl Hash for UseTree {
864 fn hash<H: Hasher>(&self, state: &mut H) {
865 self.path.hash(state);
869 impl PartialOrd for UseSegment {
870 fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
871 Some(self.cmp(other))
874 impl PartialOrd for UseTree {
875 fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> {
876 Some(self.cmp(other))
879 impl Ord for UseSegment {
880 fn cmp(&self, other: &UseSegment) -> Ordering {
881 use self::UseSegmentKind::*;
883 fn is_upper_snake_case(s: &str) -> bool {
885 .all(|c| c.is_uppercase() || c == '_' || c.is_numeric())
888 match (&self.kind, &other.kind) {
889 (Slf(ref a), Slf(ref b))
890 | (Super(ref a), Super(ref b))
891 | (Crate(ref a), Crate(ref b)) => match (a, b) {
892 (Some(sa), Some(sb)) => {
893 if self.version == Version::Two {
894 sa.trim_start_matches("r#").cmp(sb.trim_start_matches("r#"))
901 (Glob, Glob) => Ordering::Equal,
902 (Ident(ref pia, ref aa), Ident(ref pib, ref ab)) => {
903 let (ia, ib) = if self.version == Version::Two {
904 (pia.trim_start_matches("r#"), pib.trim_start_matches("r#"))
906 (pia.as_str(), pib.as_str())
908 // snake_case < CamelCase < UPPER_SNAKE_CASE
909 if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
910 return Ordering::Greater;
912 if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) {
913 return Ordering::Less;
915 if is_upper_snake_case(ia) && !is_upper_snake_case(ib) {
916 return Ordering::Greater;
918 if !is_upper_snake_case(ia) && is_upper_snake_case(ib) {
919 return Ordering::Less;
921 let ident_ord = ia.cmp(ib);
922 if ident_ord != Ordering::Equal {
926 (None, Some(_)) => Ordering::Less,
927 (Some(_), None) => Ordering::Greater,
928 (Some(aas), Some(abs)) => {
929 if self.version == Version::Two {
930 aas.trim_start_matches("r#")
931 .cmp(abs.trim_start_matches("r#"))
936 (None, None) => Ordering::Equal,
939 (List(ref a), List(ref b)) => {
940 for (a, b) in a.iter().zip(b.iter()) {
942 if ord != Ordering::Equal {
947 a.len().cmp(&b.len())
949 (Slf(_), _) => Ordering::Less,
950 (_, Slf(_)) => Ordering::Greater,
951 (Super(_), _) => Ordering::Less,
952 (_, Super(_)) => Ordering::Greater,
953 (Crate(_), _) => Ordering::Less,
954 (_, Crate(_)) => Ordering::Greater,
955 (Ident(..), _) => Ordering::Less,
956 (_, Ident(..)) => Ordering::Greater,
957 (Glob, _) => Ordering::Less,
958 (_, Glob) => Ordering::Greater,
962 impl Ord for UseTree {
963 fn cmp(&self, other: &UseTree) -> Ordering {
964 for (a, b) in self.path.iter().zip(other.path.iter()) {
966 // The comparison without aliases is a hack to avoid situations like
967 // comparing `a::b` to `a as c` - where the latter should be ordered
968 // first since it is shorter.
969 if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal
975 self.path.len().cmp(&other.path.len())
979 fn rewrite_nested_use_tree(
980 context: &RewriteContext<'_>,
981 use_tree_list: &[UseTree],
983 ) -> Option<String> {
984 let mut list_items = Vec::with_capacity(use_tree_list.len());
985 let nested_shape = match context.config.imports_indent() {
986 IndentStyle::Block => shape
987 .block_indent(context.config.tab_spaces())
988 .with_max_width(context.config)
990 IndentStyle::Visual => shape.visual_indent(0),
992 for use_tree in use_tree_list {
993 if let Some(mut list_item) = use_tree.list_item.clone() {
994 list_item.item = use_tree.rewrite(context, nested_shape);
995 list_items.push(list_item);
997 list_items.push(ListItem::from_str(use_tree.rewrite(context, nested_shape)?));
1000 let has_nested_list = use_tree_list.iter().any(|use_segment| {
1001 use_segment.path.last().map_or(false, |last_segment| {
1002 matches!(last_segment.kind, UseSegmentKind::List(..))
1006 let remaining_width = if has_nested_list {
1009 shape.width.saturating_sub(2)
1012 let tactic = definitive_tactic(
1014 context.config.imports_layout(),
1019 let ends_with_newline = context.config.imports_indent() == IndentStyle::Block
1020 && tactic != DefinitiveListTactic::Horizontal;
1021 let trailing_separator = if ends_with_newline {
1022 context.config.trailing_comma()
1024 SeparatorTactic::Never
1026 let fmt = ListFormatting::new(nested_shape, context.config)
1028 .trailing_separator(trailing_separator)
1029 .ends_with_newline(ends_with_newline)
1030 .preserve_newline(true)
1031 .nested(has_nested_list);
1033 let list_str = write_list(&list_items, &fmt)?;
1035 let result = if (list_str.contains('\n') || list_str.len() > remaining_width)
1036 && context.config.imports_indent() == IndentStyle::Block
1040 nested_shape.indent.to_string(context.config),
1042 shape.indent.to_string(context.config)
1045 format!("{{{}}}", list_str)
1051 impl Rewrite for UseSegment {
1052 fn rewrite(&self, context: &RewriteContext<'_>, shape: Shape) -> Option<String> {
1053 Some(match self.kind {
1054 UseSegmentKind::Ident(ref ident, Some(ref rename)) => {
1055 format!("{} as {}", ident, rename)
1057 UseSegmentKind::Ident(ref ident, None) => ident.clone(),
1058 UseSegmentKind::Slf(Some(ref rename)) => format!("self as {}", rename),
1059 UseSegmentKind::Slf(None) => "self".to_owned(),
1060 UseSegmentKind::Super(Some(ref rename)) => format!("super as {}", rename),
1061 UseSegmentKind::Super(None) => "super".to_owned(),
1062 UseSegmentKind::Crate(Some(ref rename)) => format!("crate as {}", rename),
1063 UseSegmentKind::Crate(None) => "crate".to_owned(),
1064 UseSegmentKind::Glob => "*".to_owned(),
1065 UseSegmentKind::List(ref use_tree_list) => rewrite_nested_use_tree(
1069 shape.offset_left(1)?.sub_width(1)?,
1075 impl Rewrite for UseTree {
1076 // This does NOT format attributes and visibility or add a trailing `;`.
1077 fn rewrite(&self, context: &RewriteContext<'_>, mut shape: Shape) -> Option<String> {
1078 let mut result = String::with_capacity(256);
1079 let mut iter = self.path.iter().peekable();
1080 while let Some(segment) = iter.next() {
1081 let segment_str = segment.rewrite(context, shape)?;
1082 result.push_str(&segment_str);
1083 if iter.peek().is_some() {
1084 result.push_str("::");
1086 shape = shape.offset_left(2 + segment_str.len())?;
1093 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
1103 use rustc_span::DUMMY_SP;
1105 // Parse the path part of an import. This parser is not robust and is only
1106 // suitable for use in a test harness.
1107 fn parse_use_tree(s: &str) -> UseTree {
1108 use std::iter::Peekable;
1110 use std::str::Chars;
1113 input: Peekable<Chars<'a>>,
1117 impl<'a> Parser<'a> {
1118 fn bump(&mut self) {
1119 self.input.next().unwrap();
1122 fn eat(&mut self, c: char) {
1123 assert_eq!(self.input.next().unwrap(), c);
1128 result: &mut Vec<UseSegment>,
1130 alias_buf: &mut Option<String>,
1132 let version = self.version;
1133 if !buf.is_empty() {
1134 let mut alias = None;
1135 swap(alias_buf, &mut alias);
1137 match buf.as_ref() {
1139 let kind = UseSegmentKind::Slf(alias);
1140 result.push(UseSegment { kind, version });
1141 *buf = String::new();
1145 let kind = UseSegmentKind::Super(alias);
1146 result.push(UseSegment { kind, version });
1147 *buf = String::new();
1151 let kind = UseSegmentKind::Crate(alias);
1152 result.push(UseSegment { kind, version });
1153 *buf = String::new();
1157 let mut name = String::new();
1158 swap(buf, &mut name);
1159 let kind = UseSegmentKind::Ident(name, alias);
1160 result.push(UseSegment { kind, version });
1166 fn parse_in_list(&mut self) -> UseTree {
1167 let mut result = vec![];
1168 let mut buf = String::new();
1169 let mut alias_buf = None;
1170 while let Some(&c) = self.input.peek() {
1173 assert!(buf.is_empty());
1175 let kind = UseSegmentKind::List(self.parse_list());
1176 result.push(UseSegment {
1178 version: self.version,
1183 assert!(buf.is_empty());
1185 let kind = UseSegmentKind::Glob;
1186 result.push(UseSegment {
1188 version: self.version,
1194 self.push_segment(&mut result, &mut buf, &mut alias_buf);
1197 self.push_segment(&mut result, &mut buf, &mut alias_buf);
1211 alias_buf = Some(String::new());
1215 if let Some(ref mut buf) = alias_buf {
1223 self.push_segment(&mut result, &mut buf, &mut alias_buf);
1233 fn parse_list(&mut self) -> Vec<UseTree> {
1234 let mut result = vec![];
1236 match self.input.peek().unwrap() {
1237 ',' | ' ' => self.bump(),
1241 _ => result.push(self.parse_in_list()),
1247 let mut parser = Parser {
1248 input: s.chars().peekable(),
1249 version: Version::One,
1251 parser.parse_in_list()
1254 macro_rules! parse_use_trees {
1255 ($($s:expr),* $(,)*) => {
1257 $(parse_use_tree($s),)*
1262 macro_rules! test_merge {
1263 ($by:ident, [$($input:expr),* $(,)*], [$($output:expr),* $(,)*]) => {
1265 normalize_use_trees_with_granularity(
1266 parse_use_trees!($($input,)*),
1267 ImportGranularity::$by,
1269 parse_use_trees!($($output,)*),
1275 fn test_use_tree_merge_crate() {
1278 ["a::b::{c, d}", "a::b::{e, f}"],
1279 ["a::b::{c, d, e, f}"]
1281 test_merge!(Crate, ["a::b::c", "a::b"], ["a::{b, b::c}"]);
1282 test_merge!(Crate, ["a::b", "a::b"], ["a::b"]);
1283 test_merge!(Crate, ["a", "a::b", "a::b::c"], ["a::{self, b, b::c}"]);
1286 ["a", "a::b", "a::b::c", "a::b::c::d"],
1287 ["a::{self, b, b::{c, c::d}}"]
1291 ["a", "a::b", "a::b::c", "a::b"],
1292 ["a::{self, b, b::c}"]
1296 ["a::{b::{self, c}, d::e}", "a::d::f"],
1297 ["a::{b::{self, c}, d::{e, f}}"]
1301 ["a::d::f", "a::{b::{self, c}, d::e}"],
1302 ["a::{b::{self, c}, d::{e, f}}"]
1306 ["a::{c, d, b}", "a::{d, e, b, a, f}", "a::{f, g, c}"],
1307 ["a::{a, b, c, d, e, f, g}"]
1311 ["a::{self}", "b::{self as foo}"],
1312 ["a::{self}", "b::{self as foo}"]
1317 fn test_use_tree_merge_module() {
1320 ["foo::b", "foo::{a, c, d::e}"],
1321 ["foo::{a, b, c}", "foo::d::e"]
1326 ["foo::{a::b, a::c, d::e, d::f}"],
1327 ["foo::a::{b, c}", "foo::d::{e, f}"]
1332 fn test_use_tree_merge_one() {
1333 test_merge!(One, ["a", "b"], ["{a, b}"]);
1335 test_merge!(One, ["a::{aa, ab}", "b", "a"], ["{a::{self, aa, ab}, b}"]);
1337 test_merge!(One, ["a as x", "b as y"], ["{a as x, b as y}"]);
1341 ["a::{aa as xa, ab}", "b", "a"],
1342 ["{a::{self, aa as xa, ab}, b}"]
1347 ["a", "a::{aa, ab::{aba, abb}}"],
1348 ["a::{self, aa, ab::{aba, abb}}"]
1351 test_merge!(One, ["a", "b::{ba, *}"], ["{a, b::{ba, *}}"]);
1353 test_merge!(One, ["a", "b", "a::aa"], ["{a::{self, aa}, b}"]);
1357 ["a::aa::aaa", "a::ac::aca", "a::aa::*"],
1358 ["a::{aa::{aaa, *}, ac::aca}"]
1363 ["a", "b::{ba, bb}", "a::{aa::*, ab::aba}"],
1364 ["{a::{self, aa::*, ab::aba}, b::{ba, bb}}"]
1369 ["b", "a::ac::{aca, acb}", "a::{aa::*, ab}"],
1370 ["{a::{aa::*, ab, ac::{aca, acb}}, b}"]
1375 fn test_flatten_use_trees() {
1378 parse_use_trees!["foo::{a::{b, c}, d::e}"],
1379 ImportGranularity::Item
1381 parse_use_trees!["foo::a::b", "foo::a::c", "foo::d::e"]
1386 parse_use_trees!["foo::{self, a, b::{c, d}, e::*}"],
1387 ImportGranularity::Item
1400 fn test_use_tree_flatten() {
1402 parse_use_tree("a::b::{c, d, e, f}").flatten(ImportGranularity::Item),
1403 parse_use_trees!("a::b::c", "a::b::d", "a::b::e", "a::b::f",)
1407 parse_use_tree("a::b::{c::{d, e, f}, g, h::{i, j, k}}")
1408 .flatten(ImportGranularity::Item),
1422 fn test_use_tree_normalize() {
1423 assert_eq!(parse_use_tree("a::self").normalize(), parse_use_tree("a"));
1425 parse_use_tree("a::self as foo").normalize(),
1426 parse_use_tree("a as foo")
1429 parse_use_tree("a::{self}").normalize(),
1430 parse_use_tree("a::{self}")
1432 assert_eq!(parse_use_tree("a::{b}").normalize(), parse_use_tree("a::b"));
1434 parse_use_tree("a::{b, c::self}").normalize(),
1435 parse_use_tree("a::{b, c}")
1438 parse_use_tree("a::{b as bar, c::self}").normalize(),
1439 parse_use_tree("a::{b as bar, c}")
1444 fn test_use_tree_ord() {
1445 assert!(parse_use_tree("a").normalize() < parse_use_tree("aa").normalize());
1446 assert!(parse_use_tree("a").normalize() < parse_use_tree("a::a").normalize());
1447 assert!(parse_use_tree("a").normalize() < parse_use_tree("*").normalize());
1448 assert!(parse_use_tree("a").normalize() < parse_use_tree("{a, b}").normalize());
1449 assert!(parse_use_tree("*").normalize() < parse_use_tree("{a, b}").normalize());
1452 parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize()
1453 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize()
1456 parse_use_tree("serde::de::{Deserialize}").normalize()
1457 < parse_use_tree("serde_json").normalize()
1459 assert!(parse_use_tree("a::b::c").normalize() < parse_use_tree("a::b::*").normalize());
1461 parse_use_tree("foo::{Bar, Baz}").normalize()
1462 < parse_use_tree("{Bar, Baz}").normalize()
1466 parse_use_tree("foo::{qux as bar}").normalize()
1467 < parse_use_tree("foo::{self as bar}").normalize()
1470 parse_use_tree("foo::{qux as bar}").normalize()
1471 < parse_use_tree("foo::{baz, qux as bar}").normalize()
1474 parse_use_tree("foo::{self as bar, baz}").normalize()
1475 < parse_use_tree("foo::{baz, qux as bar}").normalize()
1478 assert!(parse_use_tree("foo").normalize() < parse_use_tree("Foo").normalize());
1479 assert!(parse_use_tree("foo").normalize() < parse_use_tree("foo::Bar").normalize());
1482 parse_use_tree("std::cmp::{d, c, b, a}").normalize()
1483 < parse_use_tree("std::cmp::{b, e, g, f}").normalize()
1488 fn test_use_tree_nest_trailing_self() {
1490 parse_use_tree("a::b::self").nest_trailing_self(),
1491 parse_use_tree("a::b::{self}")
1494 parse_use_tree("a::b::c").nest_trailing_self(),
1495 parse_use_tree("a::b::c")
1498 parse_use_tree("a::b::{c, d}").nest_trailing_self(),
1499 parse_use_tree("a::b::{c, d}")
1502 parse_use_tree("a::b::{self, c}").nest_trailing_self(),
1503 parse_use_tree("a::b::{self, c}")