]> git.lizzy.rs Git - rust.git/blob - src/imports.rs
docs: update configuration info
[rust.git] / src / imports.rs
1 use std::borrow::Cow;
2 use std::cmp::Ordering;
3 use std::fmt;
4
5 use rustc_ast::ast::{self, UseTreeKind};
6 use rustc_span::{
7     symbol::{self, sym},
8     BytePos, Span, DUMMY_SP,
9 };
10
11 use crate::comment::combine_strs_with_missing_comments;
12 use crate::config::lists::*;
13 use crate::config::{Edition, IndentStyle};
14 use crate::lists::{
15     definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator,
16 };
17 use crate::rewrite::{Rewrite, RewriteContext};
18 use crate::shape::Shape;
19 use crate::source_map::SpanUtils;
20 use crate::spanned::Spanned;
21 use crate::utils::{is_same_visibility, mk_sp, rewrite_ident};
22 use crate::visitor::FmtVisitor;
23
24 /// Returns a name imported by a `use` declaration.
25 /// E.g., returns `Ordering` for `std::cmp::Ordering` and `self` for `std::cmp::self`.
26 pub(crate) fn path_to_imported_ident(path: &ast::Path) -> symbol::Ident {
27     path.segments.last().unwrap().ident
28 }
29
30 impl<'a> FmtVisitor<'a> {
31     pub(crate) fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) {
32         let span = item.span();
33         let shape = self.shape();
34         let rw = UseTree::from_ast(
35             &self.get_context(),
36             tree,
37             None,
38             Some(item.vis.clone()),
39             Some(item.span.lo()),
40             Some(item.attrs.clone()),
41         )
42         .rewrite_top_level(&self.get_context(), shape);
43         match rw {
44             Some(ref s) if s.is_empty() => {
45                 // Format up to last newline
46                 let prev_span = mk_sp(self.last_pos, source!(self, span).lo());
47                 let trimmed_snippet = self.snippet(prev_span).trim_end();
48                 let span_end = self.last_pos + BytePos(trimmed_snippet.len() as u32);
49                 self.format_missing(span_end);
50                 // We have an excessive newline from the removed import.
51                 if self.buffer.ends_with('\n') {
52                     self.buffer.pop();
53                     self.line_number -= 1;
54                 }
55                 self.last_pos = source!(self, span).hi();
56             }
57             Some(ref s) => {
58                 self.format_missing_with_indent(source!(self, span).lo());
59                 self.push_str(s);
60                 self.last_pos = source!(self, span).hi();
61             }
62             None => {
63                 self.format_missing_with_indent(source!(self, span).lo());
64                 self.format_missing(source!(self, span).hi());
65             }
66         }
67     }
68 }
69
70 // Ordering of imports
71
72 // We order imports by translating to our own representation and then sorting.
73 // The Rust AST data structures are really bad for this. Rustfmt applies a bunch
74 // of normalisations to imports and since we want to sort based on the result
75 // of these (and to maintain idempotence) we must apply the same normalisations
76 // to the data structures for sorting.
77 //
78 // We sort `self` and `super` before other imports, then identifier imports,
79 // then glob imports, then lists of imports. We do not take aliases into account
80 // when ordering unless the imports are identical except for the alias (rare in
81 // practice).
82
83 // FIXME(#2531): we should unify the comparison code here with the formatting
84 // code elsewhere since we are essentially string-ifying twice. Furthermore, by
85 // parsing to our own format on comparison, we repeat a lot of work when
86 // sorting.
87
88 // FIXME we do a lot of allocation to make our own representation.
89 #[derive(Clone, Eq, PartialEq)]
90 pub(crate) enum UseSegment {
91     Ident(String, Option<String>),
92     Slf(Option<String>),
93     Super(Option<String>),
94     Crate(Option<String>),
95     Glob,
96     List(Vec<UseTree>),
97 }
98
99 #[derive(Clone)]
100 pub(crate) struct UseTree {
101     pub(crate) path: Vec<UseSegment>,
102     pub(crate) span: Span,
103     // Comment information within nested use tree.
104     pub(crate) list_item: Option<ListItem>,
105     // Additional fields for top level use items.
106     // Should we have another struct for top-level use items rather than reusing this?
107     visibility: Option<ast::Visibility>,
108     attrs: Option<Vec<ast::Attribute>>,
109 }
110
111 impl PartialEq for UseTree {
112     fn eq(&self, other: &UseTree) -> bool {
113         self.path == other.path
114     }
115 }
116 impl Eq for UseTree {}
117
118 impl Spanned for UseTree {
119     fn span(&self) -> Span {
120         let lo = if let Some(ref attrs) = self.attrs {
121             attrs.iter().next().map_or(self.span.lo(), |a| a.span.lo())
122         } else {
123             self.span.lo()
124         };
125         mk_sp(lo, self.span.hi())
126     }
127 }
128
129 impl UseSegment {
130     // Clone a version of self with any top-level alias removed.
131     fn remove_alias(&self) -> UseSegment {
132         match *self {
133             UseSegment::Ident(ref s, _) => UseSegment::Ident(s.clone(), None),
134             UseSegment::Slf(_) => UseSegment::Slf(None),
135             UseSegment::Super(_) => UseSegment::Super(None),
136             UseSegment::Crate(_) => UseSegment::Crate(None),
137             _ => self.clone(),
138         }
139     }
140
141     fn from_path_segment(
142         context: &RewriteContext<'_>,
143         path_seg: &ast::PathSegment,
144         modsep: bool,
145     ) -> Option<UseSegment> {
146         let name = rewrite_ident(context, path_seg.ident);
147         if name.is_empty() || name == "{{root}}" {
148             return None;
149         }
150         Some(match name {
151             "self" => UseSegment::Slf(None),
152             "super" => UseSegment::Super(None),
153             "crate" => UseSegment::Crate(None),
154             _ => {
155                 let mod_sep = if modsep { "::" } else { "" };
156                 UseSegment::Ident(format!("{}{}", mod_sep, name), None)
157             }
158         })
159     }
160 }
161
162 pub(crate) fn merge_use_trees(use_trees: Vec<UseTree>, merge_by: SharedPrefix) -> Vec<UseTree> {
163     let mut result = Vec::with_capacity(use_trees.len());
164     for use_tree in use_trees {
165         if use_tree.has_comment() || use_tree.attrs.is_some() {
166             result.push(use_tree);
167             continue;
168         }
169
170         for flattened in use_tree.flatten() {
171             if let Some(tree) = result
172                 .iter_mut()
173                 .find(|tree| tree.share_prefix(&flattened, merge_by))
174             {
175                 tree.merge(&flattened, merge_by);
176             } else {
177                 result.push(flattened);
178             }
179         }
180     }
181     result
182 }
183
184 pub(crate) fn flatten_use_trees(use_trees: Vec<UseTree>) -> Vec<UseTree> {
185     use_trees
186         .into_iter()
187         .flat_map(UseTree::flatten)
188         .map(|mut tree| {
189             // If a path ends in `::self`, rewrite it to `::{self}`.
190             if let Some(UseSegment::Slf(..)) = tree.path.last() {
191                 let self_segment = tree.path.pop().unwrap();
192                 tree.path.push(UseSegment::List(vec![UseTree::from_path(
193                     vec![self_segment],
194                     DUMMY_SP,
195                 )]));
196             }
197             tree
198         })
199         .collect()
200 }
201
202 impl fmt::Debug for UseTree {
203     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
204         fmt::Display::fmt(self, f)
205     }
206 }
207
208 impl fmt::Debug for UseSegment {
209     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
210         fmt::Display::fmt(self, f)
211     }
212 }
213
214 impl fmt::Display for UseSegment {
215     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
216         match *self {
217             UseSegment::Glob => write!(f, "*"),
218             UseSegment::Ident(ref s, _) => write!(f, "{}", s),
219             UseSegment::Slf(..) => write!(f, "self"),
220             UseSegment::Super(..) => write!(f, "super"),
221             UseSegment::Crate(..) => write!(f, "crate"),
222             UseSegment::List(ref list) => {
223                 write!(f, "{{")?;
224                 for (i, item) in list.iter().enumerate() {
225                     if i != 0 {
226                         write!(f, ", ")?;
227                     }
228                     write!(f, "{}", item)?;
229                 }
230                 write!(f, "}}")
231             }
232         }
233     }
234 }
235 impl fmt::Display for UseTree {
236     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
237         for (i, segment) in self.path.iter().enumerate() {
238             if i != 0 {
239                 write!(f, "::")?;
240             }
241             write!(f, "{}", segment)?;
242         }
243         Ok(())
244     }
245 }
246
247 impl UseTree {
248     // Rewrite use tree with `use ` and a trailing `;`.
249     pub(crate) fn rewrite_top_level(
250         &self,
251         context: &RewriteContext<'_>,
252         shape: Shape,
253     ) -> Option<String> {
254         let vis = self.visibility.as_ref().map_or(Cow::from(""), |vis| {
255             crate::utils::format_visibility(context, &vis)
256         });
257         let use_str = self
258             .rewrite(context, shape.offset_left(vis.len())?)
259             .map(|s| {
260                 if s.is_empty() {
261                     s
262                 } else {
263                     format!("{}use {};", vis, s)
264                 }
265             })?;
266         match self.attrs {
267             Some(ref attrs) if !attrs.is_empty() => {
268                 let attr_str = attrs.rewrite(context, shape)?;
269                 let lo = attrs.last().as_ref()?.span.hi();
270                 let hi = self.span.lo();
271                 let span = mk_sp(lo, hi);
272
273                 let allow_extend = if attrs.len() == 1 {
274                     let line_len = attr_str.len() + 1 + use_str.len();
275                     !attrs.first().unwrap().is_doc_comment()
276                         && context.config.inline_attribute_width() >= line_len
277                 } else {
278                     false
279                 };
280
281                 combine_strs_with_missing_comments(
282                     context,
283                     &attr_str,
284                     &use_str,
285                     span,
286                     shape,
287                     allow_extend,
288                 )
289             }
290             _ => Some(use_str),
291         }
292     }
293
294     // FIXME: Use correct span?
295     // The given span is essentially incorrect, since we are reconstructing
296     // use-statements. This should not be a problem, though, since we have
297     // already tried to extract comment and observed that there are no comment
298     // around the given use item, and the span will not be used afterward.
299     fn from_path(path: Vec<UseSegment>, span: Span) -> UseTree {
300         UseTree {
301             path,
302             span,
303             list_item: None,
304             visibility: None,
305             attrs: None,
306         }
307     }
308
309     pub(crate) fn from_ast_with_normalization(
310         context: &RewriteContext<'_>,
311         item: &ast::Item,
312     ) -> Option<UseTree> {
313         match item.kind {
314             ast::ItemKind::Use(ref use_tree) => Some(
315                 UseTree::from_ast(
316                     context,
317                     use_tree,
318                     None,
319                     Some(item.vis.clone()),
320                     Some(item.span.lo()),
321                     if item.attrs.is_empty() {
322                         None
323                     } else {
324                         Some(item.attrs.clone())
325                     },
326                 )
327                 .normalize(),
328             ),
329             _ => None,
330         }
331     }
332
333     fn from_ast(
334         context: &RewriteContext<'_>,
335         a: &ast::UseTree,
336         list_item: Option<ListItem>,
337         visibility: Option<ast::Visibility>,
338         opt_lo: Option<BytePos>,
339         attrs: Option<Vec<ast::Attribute>>,
340     ) -> UseTree {
341         let span = if let Some(lo) = opt_lo {
342             mk_sp(lo, a.span.hi())
343         } else {
344             a.span
345         };
346         let mut result = UseTree {
347             path: vec![],
348             span,
349             list_item,
350             visibility,
351             attrs,
352         };
353
354         let leading_modsep =
355             context.config.edition() >= Edition::Edition2018 && a.prefix.is_global();
356
357         let mut modsep = leading_modsep;
358
359         for p in &a.prefix.segments {
360             if let Some(use_segment) = UseSegment::from_path_segment(context, p, modsep) {
361                 result.path.push(use_segment);
362                 modsep = false;
363             }
364         }
365
366         match a.kind {
367             UseTreeKind::Glob => {
368                 // in case of a global path and the glob starts at the root, e.g., "::*"
369                 if a.prefix.segments.len() == 1 && leading_modsep {
370                     result.path.push(UseSegment::Ident("".to_owned(), None));
371                 }
372                 result.path.push(UseSegment::Glob);
373             }
374             UseTreeKind::Nested(ref list) => {
375                 // Extract comments between nested use items.
376                 // This needs to be done before sorting use items.
377                 let items: Vec<_> = itemize_list(
378                     context.snippet_provider,
379                     list.iter().map(|(tree, _)| tree),
380                     "}",
381                     ",",
382                     |tree| tree.span.lo(),
383                     |tree| tree.span.hi(),
384                     |_| Some("".to_owned()), // We only need comments for now.
385                     context.snippet_provider.span_after(a.span, "{"),
386                     a.span.hi(),
387                     false,
388                 )
389                 .collect();
390                 // in case of a global path and the nested list starts at the root,
391                 // e.g., "::{foo, bar}"
392                 if a.prefix.segments.len() == 1 && leading_modsep {
393                     result.path.push(UseSegment::Ident("".to_owned(), None));
394                 }
395                 result.path.push(UseSegment::List(
396                     list.iter()
397                         .zip(items.into_iter())
398                         .map(|(t, list_item)| {
399                             Self::from_ast(context, &t.0, Some(list_item), None, None, None)
400                         })
401                         .collect(),
402                 ));
403             }
404             UseTreeKind::Simple(ref rename, ..) => {
405                 // If the path has leading double colons and is composed of only 2 segments, then we
406                 // bypass the call to path_to_imported_ident which would get only the ident and
407                 // lose the path root, e.g., `that` in `::that`.
408                 // The span of `a.prefix` contains the leading colons.
409                 let name = if a.prefix.segments.len() == 2 && leading_modsep {
410                     context.snippet(a.prefix.span).to_owned()
411                 } else {
412                     rewrite_ident(context, path_to_imported_ident(&a.prefix)).to_owned()
413                 };
414                 let alias = rename.and_then(|ident| {
415                     if ident.name == sym::underscore_imports {
416                         // for impl-only-use
417                         Some("_".to_owned())
418                     } else if ident == path_to_imported_ident(&a.prefix) {
419                         None
420                     } else {
421                         Some(rewrite_ident(context, ident).to_owned())
422                     }
423                 });
424                 let segment = match name.as_ref() {
425                     "self" => UseSegment::Slf(alias),
426                     "super" => UseSegment::Super(alias),
427                     "crate" => UseSegment::Crate(alias),
428                     _ => UseSegment::Ident(name, alias),
429                 };
430
431                 // `name` is already in result.
432                 result.path.pop();
433                 result.path.push(segment);
434             }
435         }
436         result
437     }
438
439     // Do the adjustments that rustfmt does elsewhere to use paths.
440     pub(crate) fn normalize(mut self) -> UseTree {
441         let mut last = self.path.pop().expect("Empty use tree?");
442         // Hack around borrow checker.
443         let mut normalize_sole_list = false;
444         let mut aliased_self = false;
445
446         // Remove foo::{} or self without attributes.
447         match last {
448             _ if self.attrs.is_some() => (),
449             UseSegment::List(ref list) if list.is_empty() => {
450                 self.path = vec![];
451                 return self;
452             }
453             UseSegment::Slf(None) if self.path.is_empty() && self.visibility.is_some() => {
454                 self.path = vec![];
455                 return self;
456             }
457             _ => (),
458         }
459
460         // Normalise foo::self -> foo.
461         if let UseSegment::Slf(None) = last {
462             if !self.path.is_empty() {
463                 return self;
464             }
465         }
466
467         // Normalise foo::self as bar -> foo as bar.
468         if let UseSegment::Slf(_) = last {
469             match self.path.last() {
470                 Some(UseSegment::Ident(_, None)) => {
471                     aliased_self = true;
472                 }
473                 _ => {}
474             }
475         }
476
477         let mut done = false;
478         if aliased_self {
479             match self.path.last_mut() {
480                 Some(UseSegment::Ident(_, ref mut old_rename)) => {
481                     assert!(old_rename.is_none());
482                     if let UseSegment::Slf(Some(rename)) = last.clone() {
483                         *old_rename = Some(rename);
484                         done = true;
485                     }
486                 }
487                 _ => unreachable!(),
488             }
489         }
490
491         if done {
492             return self;
493         }
494
495         // Normalise foo::{bar} -> foo::bar
496         if let UseSegment::List(ref list) = last {
497             if list.len() == 1 && list[0].to_string() != "self" {
498                 normalize_sole_list = true;
499             }
500         }
501
502         if normalize_sole_list {
503             match last {
504                 UseSegment::List(list) => {
505                     for seg in &list[0].path {
506                         self.path.push(seg.clone());
507                     }
508                     return self.normalize();
509                 }
510                 _ => unreachable!(),
511             }
512         }
513
514         // Recursively normalize elements of a list use (including sorting the list).
515         if let UseSegment::List(list) = last {
516             let mut list = list.into_iter().map(UseTree::normalize).collect::<Vec<_>>();
517             list.sort();
518             last = UseSegment::List(list);
519         }
520
521         self.path.push(last);
522         self
523     }
524
525     fn has_comment(&self) -> bool {
526         self.list_item.as_ref().map_or(false, ListItem::has_comment)
527     }
528
529     fn same_visibility(&self, other: &UseTree) -> bool {
530         match (&self.visibility, &other.visibility) {
531             (
532                 Some(ast::Visibility {
533                     kind: ast::VisibilityKind::Inherited,
534                     ..
535                 }),
536                 None,
537             )
538             | (
539                 None,
540                 Some(ast::Visibility {
541                     kind: ast::VisibilityKind::Inherited,
542                     ..
543                 }),
544             )
545             | (None, None) => true,
546             (Some(ref a), Some(ref b)) => is_same_visibility(a, b),
547             _ => false,
548         }
549     }
550
551     fn share_prefix(&self, other: &UseTree, shared_prefix: SharedPrefix) -> bool {
552         if self.path.is_empty()
553             || other.path.is_empty()
554             || self.attrs.is_some()
555             || !self.same_visibility(other)
556         {
557             false
558         } else {
559             match shared_prefix {
560                 SharedPrefix::Crate => self.path[0] == other.path[0],
561                 SharedPrefix::Module => {
562                     self.path[..self.path.len() - 1] == other.path[..other.path.len() - 1]
563                 }
564             }
565         }
566     }
567
568     fn flatten(self) -> Vec<UseTree> {
569         if self.path.is_empty() {
570             return vec![self];
571         }
572         match self.path.clone().last().unwrap() {
573             UseSegment::List(list) => {
574                 if list.len() == 1 && list[0].path.len() == 1 {
575                     match list[0].path[0] {
576                         UseSegment::Slf(..) => return vec![self],
577                         _ => (),
578                     };
579                 }
580                 let prefix = &self.path[..self.path.len() - 1];
581                 let mut result = vec![];
582                 for nested_use_tree in list {
583                     for flattend in &mut nested_use_tree.clone().flatten() {
584                         let mut new_path = prefix.to_vec();
585                         new_path.append(&mut flattend.path);
586                         result.push(UseTree {
587                             path: new_path,
588                             span: self.span,
589                             list_item: None,
590                             visibility: self.visibility.clone(),
591                             attrs: None,
592                         });
593                     }
594                 }
595
596                 result
597             }
598             _ => vec![self],
599         }
600     }
601
602     fn merge(&mut self, other: &UseTree, merge_by: SharedPrefix) {
603         let mut prefix = 0;
604         for (a, b) in self.path.iter().zip(other.path.iter()) {
605             if *a == *b {
606                 prefix += 1;
607             } else {
608                 break;
609             }
610         }
611         if let Some(new_path) = merge_rest(&self.path, &other.path, prefix, merge_by) {
612             self.path = new_path;
613             self.span = self.span.to(other.span);
614         }
615     }
616 }
617
618 fn merge_rest(
619     a: &[UseSegment],
620     b: &[UseSegment],
621     mut len: usize,
622     merge_by: SharedPrefix,
623 ) -> Option<Vec<UseSegment>> {
624     if a.len() == len && b.len() == len {
625         return None;
626     }
627     if a.len() != len && b.len() != len {
628         if let UseSegment::List(ref list) = a[len] {
629             let mut list = list.clone();
630             merge_use_trees_inner(
631                 &mut list,
632                 UseTree::from_path(b[len..].to_vec(), DUMMY_SP),
633                 merge_by,
634             );
635             let mut new_path = b[..len].to_vec();
636             new_path.push(UseSegment::List(list));
637             return Some(new_path);
638         }
639     } else if len == 1 {
640         let rest = if a.len() == len { &b[1..] } else { &a[1..] };
641         return Some(vec![
642             b[0].clone(),
643             UseSegment::List(vec![
644                 UseTree::from_path(vec![UseSegment::Slf(None)], DUMMY_SP),
645                 UseTree::from_path(rest.to_vec(), DUMMY_SP),
646             ]),
647         ]);
648     } else {
649         len -= 1;
650     }
651     let mut list = vec![
652         UseTree::from_path(a[len..].to_vec(), DUMMY_SP),
653         UseTree::from_path(b[len..].to_vec(), DUMMY_SP),
654     ];
655     list.sort();
656     let mut new_path = b[..len].to_vec();
657     new_path.push(UseSegment::List(list));
658     Some(new_path)
659 }
660
661 fn merge_use_trees_inner(trees: &mut Vec<UseTree>, use_tree: UseTree, merge_by: SharedPrefix) {
662     let similar_trees = trees
663         .iter_mut()
664         .filter(|tree| tree.share_prefix(&use_tree, merge_by));
665     if use_tree.path.len() == 1 && merge_by == SharedPrefix::Crate {
666         if let Some(tree) = similar_trees.min_by_key(|tree| tree.path.len()) {
667             if tree.path.len() == 1 {
668                 return;
669             }
670         }
671     } else if let Some(tree) = similar_trees.max_by_key(|tree| tree.path.len()) {
672         if tree.path.len() > 1 {
673             tree.merge(&use_tree, merge_by);
674             return;
675         }
676     }
677     trees.push(use_tree);
678     trees.sort();
679 }
680
681 impl PartialOrd for UseSegment {
682     fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
683         Some(self.cmp(other))
684     }
685 }
686 impl PartialOrd for UseTree {
687     fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> {
688         Some(self.cmp(other))
689     }
690 }
691 impl Ord for UseSegment {
692     fn cmp(&self, other: &UseSegment) -> Ordering {
693         use self::UseSegment::*;
694
695         fn is_upper_snake_case(s: &str) -> bool {
696             s.chars()
697                 .all(|c| c.is_uppercase() || c == '_' || c.is_numeric())
698         }
699
700         match (self, other) {
701             (&Slf(ref a), &Slf(ref b))
702             | (&Super(ref a), &Super(ref b))
703             | (&Crate(ref a), &Crate(ref b)) => a.cmp(b),
704             (&Glob, &Glob) => Ordering::Equal,
705             (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
706                 // snake_case < CamelCase < UPPER_SNAKE_CASE
707                 if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
708                     return Ordering::Greater;
709                 }
710                 if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) {
711                     return Ordering::Less;
712                 }
713                 if is_upper_snake_case(ia) && !is_upper_snake_case(ib) {
714                     return Ordering::Greater;
715                 }
716                 if !is_upper_snake_case(ia) && is_upper_snake_case(ib) {
717                     return Ordering::Less;
718                 }
719                 let ident_ord = ia.cmp(ib);
720                 if ident_ord != Ordering::Equal {
721                     return ident_ord;
722                 }
723                 if aa.is_none() && ab.is_some() {
724                     return Ordering::Less;
725                 }
726                 if aa.is_some() && ab.is_none() {
727                     return Ordering::Greater;
728                 }
729                 aa.cmp(ab)
730             }
731             (&List(ref a), &List(ref b)) => {
732                 for (a, b) in a.iter().zip(b.iter()) {
733                     let ord = a.cmp(b);
734                     if ord != Ordering::Equal {
735                         return ord;
736                     }
737                 }
738
739                 a.len().cmp(&b.len())
740             }
741             (&Slf(_), _) => Ordering::Less,
742             (_, &Slf(_)) => Ordering::Greater,
743             (&Super(_), _) => Ordering::Less,
744             (_, &Super(_)) => Ordering::Greater,
745             (&Crate(_), _) => Ordering::Less,
746             (_, &Crate(_)) => Ordering::Greater,
747             (&Ident(..), _) => Ordering::Less,
748             (_, &Ident(..)) => Ordering::Greater,
749             (&Glob, _) => Ordering::Less,
750             (_, &Glob) => Ordering::Greater,
751         }
752     }
753 }
754 impl Ord for UseTree {
755     fn cmp(&self, other: &UseTree) -> Ordering {
756         for (a, b) in self.path.iter().zip(other.path.iter()) {
757             let ord = a.cmp(b);
758             // The comparison without aliases is a hack to avoid situations like
759             // comparing `a::b` to `a as c` - where the latter should be ordered
760             // first since it is shorter.
761             if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal
762             {
763                 return ord;
764             }
765         }
766
767         self.path.len().cmp(&other.path.len())
768     }
769 }
770
771 fn rewrite_nested_use_tree(
772     context: &RewriteContext<'_>,
773     use_tree_list: &[UseTree],
774     shape: Shape,
775 ) -> Option<String> {
776     let mut list_items = Vec::with_capacity(use_tree_list.len());
777     let nested_shape = match context.config.imports_indent() {
778         IndentStyle::Block => shape
779             .block_indent(context.config.tab_spaces())
780             .with_max_width(context.config)
781             .sub_width(1)?,
782         IndentStyle::Visual => shape.visual_indent(0),
783     };
784     for use_tree in use_tree_list {
785         if let Some(mut list_item) = use_tree.list_item.clone() {
786             list_item.item = use_tree.rewrite(context, nested_shape);
787             list_items.push(list_item);
788         } else {
789             list_items.push(ListItem::from_str(use_tree.rewrite(context, nested_shape)?));
790         }
791     }
792     let has_nested_list = use_tree_list.iter().any(|use_segment| {
793         use_segment
794             .path
795             .last()
796             .map_or(false, |last_segment| match last_segment {
797                 UseSegment::List(..) => true,
798                 _ => false,
799             })
800     });
801
802     let remaining_width = if has_nested_list {
803         0
804     } else {
805         shape.width.saturating_sub(2)
806     };
807
808     let tactic = definitive_tactic(
809         &list_items,
810         context.config.imports_layout(),
811         Separator::Comma,
812         remaining_width,
813     );
814
815     let ends_with_newline = context.config.imports_indent() == IndentStyle::Block
816         && tactic != DefinitiveListTactic::Horizontal;
817     let trailing_separator = if ends_with_newline {
818         context.config.trailing_comma()
819     } else {
820         SeparatorTactic::Never
821     };
822     let fmt = ListFormatting::new(nested_shape, context.config)
823         .tactic(tactic)
824         .trailing_separator(trailing_separator)
825         .ends_with_newline(ends_with_newline)
826         .preserve_newline(true)
827         .nested(has_nested_list);
828
829     let list_str = write_list(&list_items, &fmt)?;
830
831     let result = if (list_str.contains('\n') || list_str.len() > remaining_width)
832         && context.config.imports_indent() == IndentStyle::Block
833     {
834         format!(
835             "{{\n{}{}\n{}}}",
836             nested_shape.indent.to_string(context.config),
837             list_str,
838             shape.indent.to_string(context.config)
839         )
840     } else {
841         format!("{{{}}}", list_str)
842     };
843
844     Some(result)
845 }
846
847 impl Rewrite for UseSegment {
848     fn rewrite(&self, context: &RewriteContext<'_>, shape: Shape) -> Option<String> {
849         Some(match self {
850             UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename),
851             UseSegment::Ident(ref ident, None) => ident.clone(),
852             UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename),
853             UseSegment::Slf(None) => "self".to_owned(),
854             UseSegment::Super(Some(ref rename)) => format!("super as {}", rename),
855             UseSegment::Super(None) => "super".to_owned(),
856             UseSegment::Crate(Some(ref rename)) => format!("crate as {}", rename),
857             UseSegment::Crate(None) => "crate".to_owned(),
858             UseSegment::Glob => "*".to_owned(),
859             UseSegment::List(ref use_tree_list) => rewrite_nested_use_tree(
860                 context,
861                 use_tree_list,
862                 // 1 = "{" and "}"
863                 shape.offset_left(1)?.sub_width(1)?,
864             )?,
865         })
866     }
867 }
868
869 impl Rewrite for UseTree {
870     // This does NOT format attributes and visibility or add a trailing `;`.
871     fn rewrite(&self, context: &RewriteContext<'_>, mut shape: Shape) -> Option<String> {
872         let mut result = String::with_capacity(256);
873         let mut iter = self.path.iter().peekable();
874         while let Some(ref segment) = iter.next() {
875             let segment_str = segment.rewrite(context, shape)?;
876             result.push_str(&segment_str);
877             if iter.peek().is_some() {
878                 result.push_str("::");
879                 // 2 = "::"
880                 shape = shape.offset_left(2 + segment_str.len())?;
881             }
882         }
883         Some(result)
884     }
885 }
886
887 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
888 pub(crate) enum SharedPrefix {
889     Crate,
890     Module,
891 }
892
893 #[cfg(test)]
894 mod test {
895     use super::*;
896     use rustc_span::DUMMY_SP;
897
898     // Parse the path part of an import. This parser is not robust and is only
899     // suitable for use in a test harness.
900     fn parse_use_tree(s: &str) -> UseTree {
901         use std::iter::Peekable;
902         use std::mem::swap;
903         use std::str::Chars;
904
905         struct Parser<'a> {
906             input: Peekable<Chars<'a>>,
907         }
908
909         impl<'a> Parser<'a> {
910             fn bump(&mut self) {
911                 self.input.next().unwrap();
912             }
913
914             fn eat(&mut self, c: char) {
915                 assert!(self.input.next().unwrap() == c);
916             }
917
918             fn push_segment(
919                 result: &mut Vec<UseSegment>,
920                 buf: &mut String,
921                 alias_buf: &mut Option<String>,
922             ) {
923                 if !buf.is_empty() {
924                     let mut alias = None;
925                     swap(alias_buf, &mut alias);
926
927                     match buf.as_ref() {
928                         "self" => {
929                             result.push(UseSegment::Slf(alias));
930                             *buf = String::new();
931                             *alias_buf = None;
932                         }
933                         "super" => {
934                             result.push(UseSegment::Super(alias));
935                             *buf = String::new();
936                             *alias_buf = None;
937                         }
938                         "crate" => {
939                             result.push(UseSegment::Crate(alias));
940                             *buf = String::new();
941                             *alias_buf = None;
942                         }
943                         _ => {
944                             let mut name = String::new();
945                             swap(buf, &mut name);
946                             result.push(UseSegment::Ident(name, alias));
947                         }
948                     }
949                 }
950             }
951
952             fn parse_in_list(&mut self) -> UseTree {
953                 let mut result = vec![];
954                 let mut buf = String::new();
955                 let mut alias_buf = None;
956                 while let Some(&c) = self.input.peek() {
957                     match c {
958                         '{' => {
959                             assert!(buf.is_empty());
960                             self.bump();
961                             result.push(UseSegment::List(self.parse_list()));
962                             self.eat('}');
963                         }
964                         '*' => {
965                             assert!(buf.is_empty());
966                             self.bump();
967                             result.push(UseSegment::Glob);
968                         }
969                         ':' => {
970                             self.bump();
971                             self.eat(':');
972                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
973                         }
974                         '}' | ',' => {
975                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
976                             return UseTree {
977                                 path: result,
978                                 span: DUMMY_SP,
979                                 list_item: None,
980                                 visibility: None,
981                                 attrs: None,
982                             };
983                         }
984                         ' ' => {
985                             self.bump();
986                             self.eat('a');
987                             self.eat('s');
988                             self.eat(' ');
989                             alias_buf = Some(String::new());
990                         }
991                         c => {
992                             self.bump();
993                             if let Some(ref mut buf) = alias_buf {
994                                 buf.push(c);
995                             } else {
996                                 buf.push(c);
997                             }
998                         }
999                     }
1000                 }
1001                 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
1002                 UseTree {
1003                     path: result,
1004                     span: DUMMY_SP,
1005                     list_item: None,
1006                     visibility: None,
1007                     attrs: None,
1008                 }
1009             }
1010
1011             fn parse_list(&mut self) -> Vec<UseTree> {
1012                 let mut result = vec![];
1013                 loop {
1014                     match self.input.peek().unwrap() {
1015                         ',' | ' ' => self.bump(),
1016                         '}' => {
1017                             return result;
1018                         }
1019                         _ => result.push(self.parse_in_list()),
1020                     }
1021                 }
1022             }
1023         }
1024
1025         let mut parser = Parser {
1026             input: s.chars().peekable(),
1027         };
1028         parser.parse_in_list()
1029     }
1030
1031     macro_rules! parse_use_trees {
1032         ($($s:expr),* $(,)*) => {
1033             vec![
1034                 $(parse_use_tree($s),)*
1035             ]
1036         }
1037     }
1038
1039     macro_rules! test_merge {
1040         ($by:ident, [$($input:expr),* $(,)*], [$($output:expr),* $(,)*]) => {
1041             assert_eq!(
1042                 merge_use_trees(parse_use_trees!($($input,)*), SharedPrefix::$by),
1043                 parse_use_trees!($($output,)*),
1044             );
1045         }
1046     }
1047
1048     #[test]
1049     fn test_use_tree_merge_crate() {
1050         test_merge!(
1051             Crate,
1052             ["a::b::{c, d}", "a::b::{e, f}"],
1053             ["a::b::{c, d, e, f}"]
1054         );
1055         test_merge!(Crate, ["a::b::c", "a::b"], ["a::{b, b::c}"]);
1056         test_merge!(Crate, ["a::b", "a::b"], ["a::b"]);
1057         test_merge!(Crate, ["a", "a::b", "a::b::c"], ["a::{self, b, b::c}"]);
1058         test_merge!(
1059             Crate,
1060             ["a", "a::b", "a::b::c", "a::b::c::d"],
1061             ["a::{self, b, b::{c, c::d}}"]
1062         );
1063         test_merge!(
1064             Crate,
1065             ["a", "a::b", "a::b::c", "a::b"],
1066             ["a::{self, b, b::c}"]
1067         );
1068         test_merge!(
1069             Crate,
1070             ["a::{b::{self, c}, d::e}", "a::d::f"],
1071             ["a::{b::{self, c}, d::{e, f}}"]
1072         );
1073         test_merge!(
1074             Crate,
1075             ["a::d::f", "a::{b::{self, c}, d::e}"],
1076             ["a::{b::{self, c}, d::{e, f}}"]
1077         );
1078         test_merge!(
1079             Crate,
1080             ["a::{c, d, b}", "a::{d, e, b, a, f}", "a::{f, g, c}"],
1081             ["a::{a, b, c, d, e, f, g}"]
1082         );
1083         test_merge!(
1084             Crate,
1085             ["a::{self}", "b::{self as foo}"],
1086             ["a::{self}", "b::{self as foo}"]
1087         );
1088     }
1089
1090     #[test]
1091     fn test_use_tree_merge_module() {
1092         test_merge!(
1093             Module,
1094             ["foo::b", "foo::{a, c, d::e}"],
1095             ["foo::{a, b, c}", "foo::d::e"]
1096         );
1097
1098         test_merge!(
1099             Module,
1100             ["foo::{a::b, a::c, d::e, d::f}"],
1101             ["foo::a::{b, c}", "foo::d::{e, f}"]
1102         );
1103     }
1104
1105     #[test]
1106     fn test_flatten_use_trees() {
1107         assert_eq!(
1108             flatten_use_trees(parse_use_trees!["foo::{a::{b, c}, d::e}"]),
1109             parse_use_trees!["foo::a::b", "foo::a::c", "foo::d::e"]
1110         );
1111
1112         assert_eq!(
1113             flatten_use_trees(parse_use_trees!["foo::{self, a, b::{c, d}, e::*}"]),
1114             parse_use_trees![
1115                 "foo::{self}",
1116                 "foo::a",
1117                 "foo::b::c",
1118                 "foo::b::d",
1119                 "foo::e::*"
1120             ]
1121         );
1122     }
1123
1124     #[test]
1125     fn test_use_tree_flatten() {
1126         assert_eq!(
1127             parse_use_tree("a::b::{c, d, e, f}").flatten(),
1128             parse_use_trees!("a::b::c", "a::b::d", "a::b::e", "a::b::f",)
1129         );
1130
1131         assert_eq!(
1132             parse_use_tree("a::b::{c::{d, e, f}, g, h::{i, j, k}}").flatten(),
1133             parse_use_trees![
1134                 "a::b::c::d",
1135                 "a::b::c::e",
1136                 "a::b::c::f",
1137                 "a::b::g",
1138                 "a::b::h::i",
1139                 "a::b::h::j",
1140                 "a::b::h::k",
1141             ]
1142         );
1143     }
1144
1145     #[test]
1146     fn test_use_tree_normalize() {
1147         assert_eq!(parse_use_tree("a::self").normalize(), parse_use_tree("a"));
1148         assert_eq!(
1149             parse_use_tree("a::self as foo").normalize(),
1150             parse_use_tree("a as foo")
1151         );
1152         assert_eq!(
1153             parse_use_tree("a::{self}").normalize(),
1154             parse_use_tree("a::{self}")
1155         );
1156         assert_eq!(parse_use_tree("a::{b}").normalize(), parse_use_tree("a::b"));
1157         assert_eq!(
1158             parse_use_tree("a::{b, c::self}").normalize(),
1159             parse_use_tree("a::{b, c}")
1160         );
1161         assert_eq!(
1162             parse_use_tree("a::{b as bar, c::self}").normalize(),
1163             parse_use_tree("a::{b as bar, c}")
1164         );
1165     }
1166
1167     #[test]
1168     fn test_use_tree_ord() {
1169         assert!(parse_use_tree("a").normalize() < parse_use_tree("aa").normalize());
1170         assert!(parse_use_tree("a").normalize() < parse_use_tree("a::a").normalize());
1171         assert!(parse_use_tree("a").normalize() < parse_use_tree("*").normalize());
1172         assert!(parse_use_tree("a").normalize() < parse_use_tree("{a, b}").normalize());
1173         assert!(parse_use_tree("*").normalize() < parse_use_tree("{a, b}").normalize());
1174
1175         assert!(
1176             parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize()
1177                 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize()
1178         );
1179         assert!(
1180             parse_use_tree("serde::de::{Deserialize}").normalize()
1181                 < parse_use_tree("serde_json").normalize()
1182         );
1183         assert!(parse_use_tree("a::b::c").normalize() < parse_use_tree("a::b::*").normalize());
1184         assert!(
1185             parse_use_tree("foo::{Bar, Baz}").normalize()
1186                 < parse_use_tree("{Bar, Baz}").normalize()
1187         );
1188
1189         assert!(
1190             parse_use_tree("foo::{qux as bar}").normalize()
1191                 < parse_use_tree("foo::{self as bar}").normalize()
1192         );
1193         assert!(
1194             parse_use_tree("foo::{qux as bar}").normalize()
1195                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
1196         );
1197         assert!(
1198             parse_use_tree("foo::{self as bar, baz}").normalize()
1199                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
1200         );
1201
1202         assert!(parse_use_tree("foo").normalize() < parse_use_tree("Foo").normalize());
1203         assert!(parse_use_tree("foo").normalize() < parse_use_tree("foo::Bar").normalize());
1204
1205         assert!(
1206             parse_use_tree("std::cmp::{d, c, b, a}").normalize()
1207                 < parse_use_tree("std::cmp::{b, e, g, f}").normalize()
1208         );
1209     }
1210 }