src/tools/rustfmt/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     // Check if self == other with their aliases removed.
 142     fn equal_except_alias(&self, other: &Self) -> bool {
 143         match (self, other) {
 144             (UseSegment::Ident(ref s1, _), UseSegment::Ident(ref s2, _)) => s1 == s2,
 145             (UseSegment::Slf(_), UseSegment::Slf(_))
 146             | (UseSegment::Super(_), UseSegment::Super(_))
 147             | (UseSegment::Crate(_), UseSegment::Crate(_))
 148             | (UseSegment::Glob, UseSegment::Glob) => true,
 149             (UseSegment::List(ref list1), UseSegment::List(ref list2)) => list1 == list2,
 150             _ => false,
 151         }
 152     }
 153
 154     fn get_alias(&self) -> Option<&str> {
 155         match self {
 156             UseSegment::Ident(_, a)
 157             | UseSegment::Slf(a)
 158             | UseSegment::Super(a)
 159             | UseSegment::Crate(a) => a.as_deref(),
 160             _ => None,
 161         }
 162     }
 163
 164     fn from_path_segment(
 165         context: &RewriteContext<'_>,
 166         path_seg: &ast::PathSegment,
 167         modsep: bool,
 168     ) -> Option<UseSegment> {
 169         let name = rewrite_ident(context, path_seg.ident);
 170         if name.is_empty() || name == "{{root}}" {
 171             return None;
 172         }
 173         Some(match name {
 174             "self" => UseSegment::Slf(None),
 175             "super" => UseSegment::Super(None),
 176             "crate" => UseSegment::Crate(None),
 177             _ => {
 178                 let mod_sep = if modsep { "::" } else { "" };
 179                 UseSegment::Ident(format!("{}{}", mod_sep, name), None)
 180             }
 181         })
 182     }
 183 }
 184
 185 pub(crate) fn merge_use_trees(use_trees: Vec<UseTree>, merge_by: SharedPrefix) -> Vec<UseTree> {
 186     let mut result = Vec::with_capacity(use_trees.len());
 187     for use_tree in use_trees {
 188         if use_tree.has_comment() || use_tree.attrs.is_some() {
 189             result.push(use_tree);
 190             continue;
 191         }
 192
 193         for flattened in use_tree.flatten() {
 194             if let Some(tree) = result
 195                 .iter_mut()
 196                 .find(|tree| tree.share_prefix(&flattened, merge_by))
 197             {
 198                 tree.merge(&flattened, merge_by);
 199             } else {
 200                 result.push(flattened);
 201             }
 202         }
 203     }
 204     result
 205 }
 206
 207 pub(crate) fn flatten_use_trees(use_trees: Vec<UseTree>) -> Vec<UseTree> {
 208     use_trees
 209         .into_iter()
 210         .flat_map(UseTree::flatten)
 211         .map(|mut tree| {
 212             // If a path ends in `::self`, rewrite it to `::{self}`.
 213             if let Some(UseSegment::Slf(..)) = tree.path.last() {
 214                 let self_segment = tree.path.pop().unwrap();
 215                 tree.path.push(UseSegment::List(vec![UseTree::from_path(
 216                     vec![self_segment],
 217                     DUMMY_SP,
 218                 )]));
 219             }
 220             tree
 221         })
 222         .collect()
 223 }
 224
 225 impl fmt::Debug for UseTree {
 226     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 227         fmt::Display::fmt(self, f)
 228     }
 229 }
 230
 231 impl fmt::Debug for UseSegment {
 232     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 233         fmt::Display::fmt(self, f)
 234     }
 235 }
 236
 237 impl fmt::Display for UseSegment {
 238     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 239         match *self {
 240             UseSegment::Glob => write!(f, "*"),
 241             UseSegment::Ident(ref s, _) => write!(f, "{}", s),
 242             UseSegment::Slf(..) => write!(f, "self"),
 243             UseSegment::Super(..) => write!(f, "super"),
 244             UseSegment::Crate(..) => write!(f, "crate"),
 245             UseSegment::List(ref list) => {
 246                 write!(f, "{{")?;
 247                 for (i, item) in list.iter().enumerate() {
 248                     if i != 0 {
 249                         write!(f, ", ")?;
 250                     }
 251                     write!(f, "{}", item)?;
 252                 }
 253                 write!(f, "}}")
 254             }
 255         }
 256     }
 257 }
 258 impl fmt::Display for UseTree {
 259     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 260         for (i, segment) in self.path.iter().enumerate() {
 261             if i != 0 {
 262                 write!(f, "::")?;
 263             }
 264             write!(f, "{}", segment)?;
 265         }
 266         Ok(())
 267     }
 268 }
 269
 270 impl UseTree {
 271     // Rewrite use tree with `use ` and a trailing `;`.
 272     pub(crate) fn rewrite_top_level(
 273         &self,
 274         context: &RewriteContext<'_>,
 275         shape: Shape,
 276     ) -> Option<String> {
 277         let vis = self.visibility.as_ref().map_or(Cow::from(""), |vis| {
 278             crate::utils::format_visibility(context, vis)
 279         });
 280         let use_str = self
 281             .rewrite(context, shape.offset_left(vis.len())?)
 282             .map(|s| {
 283                 if s.is_empty() {
 284                     s
 285                 } else {
 286                     format!("{}use {};", vis, s)
 287                 }
 288             })?;
 289         match self.attrs {
 290             Some(ref attrs) if !attrs.is_empty() => {
 291                 let attr_str = attrs.rewrite(context, shape)?;
 292                 let lo = attrs.last().as_ref()?.span.hi();
 293                 let hi = self.span.lo();
 294                 let span = mk_sp(lo, hi);
 295
 296                 let allow_extend = if attrs.len() == 1 {
 297                     let line_len = attr_str.len() + 1 + use_str.len();
 298                     !attrs.first().unwrap().is_doc_comment()
 299                         && context.config.inline_attribute_width() >= line_len
 300                 } else {
 301                     false
 302                 };
 303
 304                 combine_strs_with_missing_comments(
 305                     context,
 306                     &attr_str,
 307                     &use_str,
 308                     span,
 309                     shape,
 310                     allow_extend,
 311                 )
 312             }
 313             _ => Some(use_str),
 314         }
 315     }
 316
 317     // FIXME: Use correct span?
 318     // The given span is essentially incorrect, since we are reconstructing
 319     // use-statements. This should not be a problem, though, since we have
 320     // already tried to extract comment and observed that there are no comment
 321     // around the given use item, and the span will not be used afterward.
 322     fn from_path(path: Vec<UseSegment>, span: Span) -> UseTree {
 323         UseTree {
 324             path,
 325             span,
 326             list_item: None,
 327             visibility: None,
 328             attrs: None,
 329         }
 330     }
 331
 332     pub(crate) fn from_ast_with_normalization(
 333         context: &RewriteContext<'_>,
 334         item: &ast::Item,
 335     ) -> Option<UseTree> {
 336         match item.kind {
 337             ast::ItemKind::Use(ref use_tree) => Some(
 338                 UseTree::from_ast(
 339                     context,
 340                     use_tree,
 341                     None,
 342                     Some(item.vis.clone()),
 343                     Some(item.span.lo()),
 344                     if item.attrs.is_empty() {
 345                         None
 346                     } else {
 347                         Some(item.attrs.clone())
 348                     },
 349                 )
 350                 .normalize(),
 351             ),
 352             _ => None,
 353         }
 354     }
 355
 356     fn from_ast(
 357         context: &RewriteContext<'_>,
 358         a: &ast::UseTree,
 359         list_item: Option<ListItem>,
 360         visibility: Option<ast::Visibility>,
 361         opt_lo: Option<BytePos>,
 362         attrs: Option<Vec<ast::Attribute>>,
 363     ) -> UseTree {
 364         let span = if let Some(lo) = opt_lo {
 365             mk_sp(lo, a.span.hi())
 366         } else {
 367             a.span
 368         };
 369         let mut result = UseTree {
 370             path: vec![],
 371             span,
 372             list_item,
 373             visibility,
 374             attrs,
 375         };
 376
 377         let leading_modsep =
 378             context.config.edition() >= Edition::Edition2018 && a.prefix.is_global();
 379
 380         let mut modsep = leading_modsep;
 381
 382         for p in &a.prefix.segments {
 383             if let Some(use_segment) = UseSegment::from_path_segment(context, p, modsep) {
 384                 result.path.push(use_segment);
 385                 modsep = false;
 386             }
 387         }
 388
 389         match a.kind {
 390             UseTreeKind::Glob => {
 391                 // in case of a global path and the glob starts at the root, e.g., "::*"
 392                 if a.prefix.segments.len() == 1 && leading_modsep {
 393                     result.path.push(UseSegment::Ident("".to_owned(), None));
 394                 }
 395                 result.path.push(UseSegment::Glob);
 396             }
 397             UseTreeKind::Nested(ref list) => {
 398                 // Extract comments between nested use items.
 399                 // This needs to be done before sorting use items.
 400                 let items = itemize_list(
 401                     context.snippet_provider,
 402                     list.iter().map(|(tree, _)| tree),
 403                     "}",
 404                     ",",
 405                     |tree| tree.span.lo(),
 406                     |tree| tree.span.hi(),
 407                     |_| Some("".to_owned()), // We only need comments for now.
 408                     context.snippet_provider.span_after(a.span, "{"),
 409                     a.span.hi(),
 410                     false,
 411                 );
 412
 413                 // in case of a global path and the nested list starts at the root,
 414                 // e.g., "::{foo, bar}"
 415                 if a.prefix.segments.len() == 1 && leading_modsep {
 416                     result.path.push(UseSegment::Ident("".to_owned(), None));
 417                 }
 418                 result.path.push(UseSegment::List(
 419                     list.iter()
 420                         .zip(items)
 421                         .map(|(t, list_item)| {
 422                             Self::from_ast(context, &t.0, Some(list_item), None, None, None)
 423                         })
 424                         .collect(),
 425                 ));
 426             }
 427             UseTreeKind::Simple(ref rename, ..) => {
 428                 // If the path has leading double colons and is composed of only 2 segments, then we
 429                 // bypass the call to path_to_imported_ident which would get only the ident and
 430                 // lose the path root, e.g., `that` in `::that`.
 431                 // The span of `a.prefix` contains the leading colons.
 432                 let name = if a.prefix.segments.len() == 2 && leading_modsep {
 433                     context.snippet(a.prefix.span).to_owned()
 434                 } else {
 435                     rewrite_ident(context, path_to_imported_ident(&a.prefix)).to_owned()
 436                 };
 437                 let alias = rename.and_then(|ident| {
 438                     if ident.name == sym::underscore_imports {
 439                         // for impl-only-use
 440                         Some("_".to_owned())
 441                     } else if ident == path_to_imported_ident(&a.prefix) {
 442                         None
 443                     } else {
 444                         Some(rewrite_ident(context, ident).to_owned())
 445                     }
 446                 });
 447                 let segment = match name.as_ref() {
 448                     "self" => UseSegment::Slf(alias),
 449                     "super" => UseSegment::Super(alias),
 450                     "crate" => UseSegment::Crate(alias),
 451                     _ => UseSegment::Ident(name, alias),
 452                 };
 453
 454                 // `name` is already in result.
 455                 result.path.pop();
 456                 result.path.push(segment);
 457             }
 458         }
 459         result
 460     }
 461
 462     // Do the adjustments that rustfmt does elsewhere to use paths.
 463     pub(crate) fn normalize(mut self) -> UseTree {
 464         let mut last = self.path.pop().expect("Empty use tree?");
 465         // Hack around borrow checker.
 466         let mut normalize_sole_list = false;
 467         let mut aliased_self = false;
 468
 469         // Remove foo::{} or self without attributes.
 470         match last {
 471             _ if self.attrs.is_some() => (),
 472             UseSegment::List(ref list) if list.is_empty() => {
 473                 self.path = vec![];
 474                 return self;
 475             }
 476             UseSegment::Slf(None) if self.path.is_empty() && self.visibility.is_some() => {
 477                 self.path = vec![];
 478                 return self;
 479             }
 480             _ => (),
 481         }
 482
 483         // Normalise foo::self -> foo.
 484         if let UseSegment::Slf(None) = last {
 485             if !self.path.is_empty() {
 486                 return self;
 487             }
 488         }
 489
 490         // Normalise foo::self as bar -> foo as bar.
 491         if let UseSegment::Slf(_) = last {
 492             if let Some(UseSegment::Ident(_, None)) = self.path.last() {
 493                 aliased_self = true;
 494             }
 495         }
 496
 497         let mut done = false;
 498         if aliased_self {
 499             match self.path.last_mut() {
 500                 Some(UseSegment::Ident(_, ref mut old_rename)) => {
 501                     assert!(old_rename.is_none());
 502                     if let UseSegment::Slf(Some(rename)) = last.clone() {
 503                         *old_rename = Some(rename);
 504                         done = true;
 505                     }
 506                 }
 507                 _ => unreachable!(),
 508             }
 509         }
 510
 511         if done {
 512             return self;
 513         }
 514
 515         // Normalise foo::{bar} -> foo::bar
 516         if let UseSegment::List(ref list) = last {
 517             if list.len() == 1 && list[0].to_string() != "self" {
 518                 normalize_sole_list = true;
 519             }
 520         }
 521
 522         if normalize_sole_list {
 523             match last {
 524                 UseSegment::List(list) => {
 525                     for seg in &list[0].path {
 526                         self.path.push(seg.clone());
 527                     }
 528                     return self.normalize();
 529                 }
 530                 _ => unreachable!(),
 531             }
 532         }
 533
 534         // Recursively normalize elements of a list use (including sorting the list).
 535         if let UseSegment::List(list) = last {
 536             let mut list = list.into_iter().map(UseTree::normalize).collect::<Vec<_>>();
 537             list.sort();
 538             last = UseSegment::List(list);
 539         }
 540
 541         self.path.push(last);
 542         self
 543     }
 544
 545     fn has_comment(&self) -> bool {
 546         self.list_item.as_ref().map_or(false, ListItem::has_comment)
 547     }
 548
 549     fn same_visibility(&self, other: &UseTree) -> bool {
 550         match (&self.visibility, &other.visibility) {
 551             (
 552                 Some(ast::Visibility {
 553                     kind: ast::VisibilityKind::Inherited,
 554                     ..
 555                 }),
 556                 None,
 557             )
 558             | (
 559                 None,
 560                 Some(ast::Visibility {
 561                     kind: ast::VisibilityKind::Inherited,
 562                     ..
 563                 }),
 564             )
 565             | (None, None) => true,
 566             (Some(ref a), Some(ref b)) => is_same_visibility(a, b),
 567             _ => false,
 568         }
 569     }
 570
 571     fn share_prefix(&self, other: &UseTree, shared_prefix: SharedPrefix) -> bool {
 572         if self.path.is_empty()
 573             || other.path.is_empty()
 574             || self.attrs.is_some()
 575             || !self.same_visibility(other)
 576         {
 577             false
 578         } else {
 579             match shared_prefix {
 580                 SharedPrefix::Crate => self.path[0] == other.path[0],
 581                 SharedPrefix::Module => {
 582                     self.path[..self.path.len() - 1] == other.path[..other.path.len() - 1]
 583                 }
 584                 SharedPrefix::One => true,
 585             }
 586         }
 587     }
 588
 589     fn flatten(self) -> Vec<UseTree> {
 590         if self.path.is_empty() {
 591             return vec![self];
 592         }
 593         match self.path.clone().last().unwrap() {
 594             UseSegment::List(list) => {
 595                 if list.len() == 1 && list[0].path.len() == 1 {
 596                     if let UseSegment::Slf(..) = list[0].path[0] {
 597                         return vec![self];
 598                     };
 599                 }
 600                 let prefix = &self.path[..self.path.len() - 1];
 601                 let mut result = vec![];
 602                 for nested_use_tree in list {
 603                     for flattend in &mut nested_use_tree.clone().flatten() {
 604                         let mut new_path = prefix.to_vec();
 605                         new_path.append(&mut flattend.path);
 606                         result.push(UseTree {
 607                             path: new_path,
 608                             span: self.span,
 609                             list_item: None,
 610                             visibility: self.visibility.clone(),
 611                             attrs: None,
 612                         });
 613                     }
 614                 }
 615
 616                 result
 617             }
 618             _ => vec![self],
 619         }
 620     }
 621
 622     fn merge(&mut self, other: &UseTree, merge_by: SharedPrefix) {
 623         let mut prefix = 0;
 624         for (a, b) in self.path.iter().zip(other.path.iter()) {
 625             if a.equal_except_alias(b) {
 626                 prefix += 1;
 627             } else {
 628                 break;
 629             }
 630         }
 631         if let Some(new_path) = merge_rest(&self.path, &other.path, prefix, merge_by) {
 632             self.path = new_path;
 633             self.span = self.span.to(other.span);
 634         }
 635     }
 636 }
 637
 638 fn merge_rest(
 639     a: &[UseSegment],
 640     b: &[UseSegment],
 641     mut len: usize,
 642     merge_by: SharedPrefix,
 643 ) -> Option<Vec<UseSegment>> {
 644     if a.len() == len && b.len() == len {
 645         return None;
 646     }
 647     if a.len() != len && b.len() != len {
 648         if let UseSegment::List(ref list) = a[len] {
 649             let mut list = list.clone();
 650             merge_use_trees_inner(
 651                 &mut list,
 652                 UseTree::from_path(b[len..].to_vec(), DUMMY_SP),
 653                 merge_by,
 654             );
 655             let mut new_path = b[..len].to_vec();
 656             new_path.push(UseSegment::List(list));
 657             return Some(new_path);
 658         }
 659     } else if len == 1 {
 660         let (common, rest) = if a.len() == len {
 661             (&a[0], &b[1..])
 662         } else {
 663             (&b[0], &a[1..])
 664         };
 665         let mut list = vec![UseTree::from_path(
 666             vec![UseSegment::Slf(common.get_alias().map(ToString::to_string))],
 667             DUMMY_SP,
 668         )];
 669         match rest {
 670             [UseSegment::List(rest_list)] => list.extend(rest_list.clone()),
 671             _ => list.push(UseTree::from_path(rest.to_vec(), DUMMY_SP)),
 672         }
 673         return Some(vec![b[0].clone(), UseSegment::List(list)]);
 674     } else {
 675         len -= 1;
 676     }
 677     let mut list = vec![
 678         UseTree::from_path(a[len..].to_vec(), DUMMY_SP),
 679         UseTree::from_path(b[len..].to_vec(), DUMMY_SP),
 680     ];
 681     list.sort();
 682     let mut new_path = b[..len].to_vec();
 683     new_path.push(UseSegment::List(list));
 684     Some(new_path)
 685 }
 686
 687 fn merge_use_trees_inner(trees: &mut Vec<UseTree>, use_tree: UseTree, merge_by: SharedPrefix) {
 688     struct SimilarTree<'a> {
 689         similarity: usize,
 690         path_len: usize,
 691         tree: &'a mut UseTree,
 692     }
 693
 694     let similar_trees = trees.iter_mut().filter_map(|tree| {
 695         if tree.share_prefix(&use_tree, merge_by) {
 696             // In the case of `SharedPrefix::One`, `similarity` is used for deciding with which
 697             // tree `use_tree` should be merge.
 698             // In other cases `similarity` won't be used, so set it to `0` as a dummy value.
 699             let similarity = if merge_by == SharedPrefix::One {
 700                 tree.path
 701                     .iter()
 702                     .zip(&use_tree.path)
 703                     .take_while(|(a, b)| a.equal_except_alias(b))
 704                     .count()
 705             } else {
 706                 0
 707             };
 708
 709             let path_len = tree.path.len();
 710             Some(SimilarTree {
 711                 similarity,
 712                 tree,
 713                 path_len,
 714             })
 715         } else {
 716             None
 717         }
 718     });
 719
 720     if use_tree.path.len() == 1 && merge_by == SharedPrefix::Crate {
 721         if let Some(tree) = similar_trees.min_by_key(|tree| tree.path_len) {
 722             if tree.path_len == 1 {
 723                 return;
 724             }
 725         }
 726     } else if merge_by == SharedPrefix::One {
 727         if let Some(sim_tree) = similar_trees.max_by_key(|tree| tree.similarity) {
 728             if sim_tree.similarity > 0 {
 729                 sim_tree.tree.merge(&use_tree, merge_by);
 730                 return;
 731             }
 732         }
 733     } else if let Some(sim_tree) = similar_trees.max_by_key(|tree| tree.path_len) {
 734         if sim_tree.path_len > 1 {
 735             sim_tree.tree.merge(&use_tree, merge_by);
 736             return;
 737         }
 738     }
 739     trees.push(use_tree);
 740     trees.sort();
 741 }
 742
 743 impl PartialOrd for UseSegment {
 744     fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
 745         Some(self.cmp(other))
 746     }
 747 }
 748 impl PartialOrd for UseTree {
 749     fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> {
 750         Some(self.cmp(other))
 751     }
 752 }
 753 impl Ord for UseSegment {
 754     fn cmp(&self, other: &UseSegment) -> Ordering {
 755         use self::UseSegment::*;
 756
 757         fn is_upper_snake_case(s: &str) -> bool {
 758             s.chars()
 759                 .all(|c| c.is_uppercase() || c == '_' || c.is_numeric())
 760         }
 761
 762         match (self, other) {
 763             (&Slf(ref a), &Slf(ref b))
 764             | (&Super(ref a), &Super(ref b))
 765             | (&Crate(ref a), &Crate(ref b)) => a.cmp(b),
 766             (&Glob, &Glob) => Ordering::Equal,
 767             (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
 768                 // snake_case < CamelCase < UPPER_SNAKE_CASE
 769                 if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
 770                     return Ordering::Greater;
 771                 }
 772                 if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) {
 773                     return Ordering::Less;
 774                 }
 775                 if is_upper_snake_case(ia) && !is_upper_snake_case(ib) {
 776                     return Ordering::Greater;
 777                 }
 778                 if !is_upper_snake_case(ia) && is_upper_snake_case(ib) {
 779                     return Ordering::Less;
 780                 }
 781                 let ident_ord = ia.cmp(ib);
 782                 if ident_ord != Ordering::Equal {
 783                     return ident_ord;
 784                 }
 785                 if aa.is_none() && ab.is_some() {
 786                     return Ordering::Less;
 787                 }
 788                 if aa.is_some() && ab.is_none() {
 789                     return Ordering::Greater;
 790                 }
 791                 aa.cmp(ab)
 792             }
 793             (&List(ref a), &List(ref b)) => {
 794                 for (a, b) in a.iter().zip(b.iter()) {
 795                     let ord = a.cmp(b);
 796                     if ord != Ordering::Equal {
 797                         return ord;
 798                     }
 799                 }
 800
 801                 a.len().cmp(&b.len())
 802             }
 803             (&Slf(_), _) => Ordering::Less,
 804             (_, &Slf(_)) => Ordering::Greater,
 805             (&Super(_), _) => Ordering::Less,
 806             (_, &Super(_)) => Ordering::Greater,
 807             (&Crate(_), _) => Ordering::Less,
 808             (_, &Crate(_)) => Ordering::Greater,
 809             (&Ident(..), _) => Ordering::Less,
 810             (_, &Ident(..)) => Ordering::Greater,
 811             (&Glob, _) => Ordering::Less,
 812             (_, &Glob) => Ordering::Greater,
 813         }
 814     }
 815 }
 816 impl Ord for UseTree {
 817     fn cmp(&self, other: &UseTree) -> Ordering {
 818         for (a, b) in self.path.iter().zip(other.path.iter()) {
 819             let ord = a.cmp(b);
 820             // The comparison without aliases is a hack to avoid situations like
 821             // comparing `a::b` to `a as c` - where the latter should be ordered
 822             // first since it is shorter.
 823             if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal
 824             {
 825                 return ord;
 826             }
 827         }
 828
 829         self.path.len().cmp(&other.path.len())
 830     }
 831 }
 832
 833 fn rewrite_nested_use_tree(
 834     context: &RewriteContext<'_>,
 835     use_tree_list: &[UseTree],
 836     shape: Shape,
 837 ) -> Option<String> {
 838     let mut list_items = Vec::with_capacity(use_tree_list.len());
 839     let nested_shape = match context.config.imports_indent() {
 840         IndentStyle::Block => shape
 841             .block_indent(context.config.tab_spaces())
 842             .with_max_width(context.config)
 843             .sub_width(1)?,
 844         IndentStyle::Visual => shape.visual_indent(0),
 845     };
 846     for use_tree in use_tree_list {
 847         if let Some(mut list_item) = use_tree.list_item.clone() {
 848             list_item.item = use_tree.rewrite(context, nested_shape);
 849             list_items.push(list_item);
 850         } else {
 851             list_items.push(ListItem::from_str(use_tree.rewrite(context, nested_shape)?));
 852         }
 853     }
 854     let has_nested_list = use_tree_list.iter().any(|use_segment| {
 855         use_segment.path.last().map_or(false, |last_segment| {
 856             matches!(last_segment, UseSegment::List(..))
 857         })
 858     });
 859
 860     let remaining_width = if has_nested_list {
 861         0
 862     } else {
 863         shape.width.saturating_sub(2)
 864     };
 865
 866     let tactic = definitive_tactic(
 867         &list_items,
 868         context.config.imports_layout(),
 869         Separator::Comma,
 870         remaining_width,
 871     );
 872
 873     let ends_with_newline = context.config.imports_indent() == IndentStyle::Block
 874         && tactic != DefinitiveListTactic::Horizontal;
 875     let trailing_separator = if ends_with_newline {
 876         context.config.trailing_comma()
 877     } else {
 878         SeparatorTactic::Never
 879     };
 880     let fmt = ListFormatting::new(nested_shape, context.config)
 881         .tactic(tactic)
 882         .trailing_separator(trailing_separator)
 883         .ends_with_newline(ends_with_newline)
 884         .preserve_newline(true)
 885         .nested(has_nested_list);
 886
 887     let list_str = write_list(&list_items, &fmt)?;
 888
 889     let result = if (list_str.contains('\n') || list_str.len() > remaining_width)
 890         && context.config.imports_indent() == IndentStyle::Block
 891     {
 892         format!(
 893             "{{\n{}{}\n{}}}",
 894             nested_shape.indent.to_string(context.config),
 895             list_str,
 896             shape.indent.to_string(context.config)
 897         )
 898     } else {
 899         format!("{{{}}}", list_str)
 900     };
 901
 902     Some(result)
 903 }
 904
 905 impl Rewrite for UseSegment {
 906     fn rewrite(&self, context: &RewriteContext<'_>, shape: Shape) -> Option<String> {
 907         Some(match self {
 908             UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename),
 909             UseSegment::Ident(ref ident, None) => ident.clone(),
 910             UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename),
 911             UseSegment::Slf(None) => "self".to_owned(),
 912             UseSegment::Super(Some(ref rename)) => format!("super as {}", rename),
 913             UseSegment::Super(None) => "super".to_owned(),
 914             UseSegment::Crate(Some(ref rename)) => format!("crate as {}", rename),
 915             UseSegment::Crate(None) => "crate".to_owned(),
 916             UseSegment::Glob => "*".to_owned(),
 917             UseSegment::List(ref use_tree_list) => rewrite_nested_use_tree(
 918                 context,
 919                 use_tree_list,
 920                 // 1 = "{" and "}"
 921                 shape.offset_left(1)?.sub_width(1)?,
 922             )?,
 923         })
 924     }
 925 }
 926
 927 impl Rewrite for UseTree {
 928     // This does NOT format attributes and visibility or add a trailing `;`.
 929     fn rewrite(&self, context: &RewriteContext<'_>, mut shape: Shape) -> Option<String> {
 930         let mut result = String::with_capacity(256);
 931         let mut iter = self.path.iter().peekable();
 932         while let Some(segment) = iter.next() {
 933             let segment_str = segment.rewrite(context, shape)?;
 934             result.push_str(&segment_str);
 935             if iter.peek().is_some() {
 936                 result.push_str("::");
 937                 // 2 = "::"
 938                 shape = shape.offset_left(2 + segment_str.len())?;
 939             }
 940         }
 941         Some(result)
 942     }
 943 }
 944
 945 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 946 pub(crate) enum SharedPrefix {
 947     Crate,
 948     Module,
 949     One,
 950 }
 951
 952 #[cfg(test)]
 953 mod test {
 954     use super::*;
 955     use rustc_span::DUMMY_SP;
 956
 957     // Parse the path part of an import. This parser is not robust and is only
 958     // suitable for use in a test harness.
 959     fn parse_use_tree(s: &str) -> UseTree {
 960         use std::iter::Peekable;
 961         use std::mem::swap;
 962         use std::str::Chars;
 963
 964         struct Parser<'a> {
 965             input: Peekable<Chars<'a>>,
 966         }
 967
 968         impl<'a> Parser<'a> {
 969             fn bump(&mut self) {
 970                 self.input.next().unwrap();
 971             }
 972
 973             fn eat(&mut self, c: char) {
 974                 assert_eq!(self.input.next().unwrap(), c);
 975             }
 976
 977             fn push_segment(
 978                 result: &mut Vec<UseSegment>,
 979                 buf: &mut String,
 980                 alias_buf: &mut Option<String>,
 981             ) {
 982                 if !buf.is_empty() {
 983                     let mut alias = None;
 984                     swap(alias_buf, &mut alias);
 985
 986                     match buf.as_ref() {
 987                         "self" => {
 988                             result.push(UseSegment::Slf(alias));
 989                             *buf = String::new();
 990                             *alias_buf = None;
 991                         }
 992                         "super" => {
 993                             result.push(UseSegment::Super(alias));
 994                             *buf = String::new();
 995                             *alias_buf = None;
 996                         }
 997                         "crate" => {
 998                             result.push(UseSegment::Crate(alias));
 999                             *buf = String::new();
1000                             *alias_buf = None;
1001                         }
1002                         _ => {
1003                             let mut name = String::new();
1004                             swap(buf, &mut name);
1005                             result.push(UseSegment::Ident(name, alias));
1006                         }
1007                     }
1008                 }
1009             }
1010
1011             fn parse_in_list(&mut self) -> UseTree {
1012                 let mut result = vec![];
1013                 let mut buf = String::new();
1014                 let mut alias_buf = None;
1015                 while let Some(&c) = self.input.peek() {
1016                     match c {
1017                         '{' => {
1018                             assert!(buf.is_empty());
1019                             self.bump();
1020                             result.push(UseSegment::List(self.parse_list()));
1021                             self.eat('}');
1022                         }
1023                         '*' => {
1024                             assert!(buf.is_empty());
1025                             self.bump();
1026                             result.push(UseSegment::Glob);
1027                         }
1028                         ':' => {
1029                             self.bump();
1030                             self.eat(':');
1031                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
1032                         }
1033                         '}' | ',' => {
1034                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
1035                             return UseTree {
1036                                 path: result,
1037                                 span: DUMMY_SP,
1038                                 list_item: None,
1039                                 visibility: None,
1040                                 attrs: None,
1041                             };
1042                         }
1043                         ' ' => {
1044                             self.bump();
1045                             self.eat('a');
1046                             self.eat('s');
1047                             self.eat(' ');
1048                             alias_buf = Some(String::new());
1049                         }
1050                         c => {
1051                             self.bump();
1052                             if let Some(ref mut buf) = alias_buf {
1053                                 buf.push(c);
1054                             } else {
1055                                 buf.push(c);
1056                             }
1057                         }
1058                     }
1059                 }
1060                 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
1061                 UseTree {
1062                     path: result,
1063                     span: DUMMY_SP,
1064                     list_item: None,
1065                     visibility: None,
1066                     attrs: None,
1067                 }
1068             }
1069
1070             fn parse_list(&mut self) -> Vec<UseTree> {
1071                 let mut result = vec![];
1072                 loop {
1073                     match self.input.peek().unwrap() {
1074                         ',' | ' ' => self.bump(),
1075                         '}' => {
1076                             return result;
1077                         }
1078                         _ => result.push(self.parse_in_list()),
1079                     }
1080                 }
1081             }
1082         }
1083
1084         let mut parser = Parser {
1085             input: s.chars().peekable(),
1086         };
1087         parser.parse_in_list()
1088     }
1089
1090     macro_rules! parse_use_trees {
1091         ($($s:expr),* $(,)*) => {
1092             vec![
1093                 $(parse_use_tree($s),)*
1094             ]
1095         }
1096     }
1097
1098     macro_rules! test_merge {
1099         ($by:ident, [$($input:expr),* $(,)*], [$($output:expr),* $(,)*]) => {
1100             assert_eq!(
1101                 merge_use_trees(parse_use_trees!($($input,)*), SharedPrefix::$by),
1102                 parse_use_trees!($($output,)*),
1103             );
1104         }
1105     }
1106
1107     #[test]
1108     fn test_use_tree_merge_crate() {
1109         test_merge!(
1110             Crate,
1111             ["a::b::{c, d}", "a::b::{e, f}"],
1112             ["a::b::{c, d, e, f}"]
1113         );
1114         test_merge!(Crate, ["a::b::c", "a::b"], ["a::{b, b::c}"]);
1115         test_merge!(Crate, ["a::b", "a::b"], ["a::b"]);
1116         test_merge!(Crate, ["a", "a::b", "a::b::c"], ["a::{self, b, b::c}"]);
1117         test_merge!(
1118             Crate,
1119             ["a", "a::b", "a::b::c", "a::b::c::d"],
1120             ["a::{self, b, b::{c, c::d}}"]
1121         );
1122         test_merge!(
1123             Crate,
1124             ["a", "a::b", "a::b::c", "a::b"],
1125             ["a::{self, b, b::c}"]
1126         );
1127         test_merge!(
1128             Crate,
1129             ["a::{b::{self, c}, d::e}", "a::d::f"],
1130             ["a::{b::{self, c}, d::{e, f}}"]
1131         );
1132         test_merge!(
1133             Crate,
1134             ["a::d::f", "a::{b::{self, c}, d::e}"],
1135             ["a::{b::{self, c}, d::{e, f}}"]
1136         );
1137         test_merge!(
1138             Crate,
1139             ["a::{c, d, b}", "a::{d, e, b, a, f}", "a::{f, g, c}"],
1140             ["a::{a, b, c, d, e, f, g}"]
1141         );
1142         test_merge!(
1143             Crate,
1144             ["a::{self}", "b::{self as foo}"],
1145             ["a::{self}", "b::{self as foo}"]
1146         );
1147     }
1148
1149     #[test]
1150     fn test_use_tree_merge_module() {
1151         test_merge!(
1152             Module,
1153             ["foo::b", "foo::{a, c, d::e}"],
1154             ["foo::{a, b, c}", "foo::d::e"]
1155         );
1156
1157         test_merge!(
1158             Module,
1159             ["foo::{a::b, a::c, d::e, d::f}"],
1160             ["foo::a::{b, c}", "foo::d::{e, f}"]
1161         );
1162     }
1163
1164     #[test]
1165     fn test_use_tree_merge_one() {
1166         test_merge!(One, ["a", "b"], ["{a, b}"]);
1167
1168         test_merge!(One, ["a::{aa, ab}", "b", "a"], ["{a::{self, aa, ab}, b}"]);
1169
1170         test_merge!(One, ["a as x", "b as y"], ["{a as x, b as y}"]);
1171
1172         test_merge!(
1173             One,
1174             ["a::{aa as xa, ab}", "b", "a"],
1175             ["{a::{self, aa as xa, ab}, b}"]
1176         );
1177
1178         test_merge!(
1179             One,
1180             ["a", "a::{aa, ab::{aba, abb}}"],
1181             ["a::{self, aa, ab::{aba, abb}}"]
1182         );
1183
1184         test_merge!(One, ["a", "b::{ba, *}"], ["{a, b::{ba, *}}"]);
1185
1186         test_merge!(One, ["a", "b", "a::aa"], ["{a::{self, aa}, b}"]);
1187
1188         test_merge!(
1189             One,
1190             ["a::aa::aaa", "a::ac::aca", "a::aa::*"],
1191             ["a::{aa::{aaa, *}, ac::aca}"]
1192         );
1193
1194         test_merge!(
1195             One,
1196             ["a", "b::{ba, bb}", "a::{aa::*, ab::aba}"],
1197             ["{a::{self, aa::*, ab::aba}, b::{ba, bb}}"]
1198         );
1199
1200         test_merge!(
1201             One,
1202             ["b", "a::ac::{aca, acb}", "a::{aa::*, ab}"],
1203             ["{a::{aa::*, ab, ac::{aca, acb}}, b}"]
1204         );
1205     }
1206
1207     #[test]
1208     fn test_flatten_use_trees() {
1209         assert_eq!(
1210             flatten_use_trees(parse_use_trees!["foo::{a::{b, c}, d::e}"]),
1211             parse_use_trees!["foo::a::b", "foo::a::c", "foo::d::e"]
1212         );
1213
1214         assert_eq!(
1215             flatten_use_trees(parse_use_trees!["foo::{self, a, b::{c, d}, e::*}"]),
1216             parse_use_trees![
1217                 "foo::{self}",
1218                 "foo::a",
1219                 "foo::b::c",
1220                 "foo::b::d",
1221                 "foo::e::*"
1222             ]
1223         );
1224     }
1225
1226     #[test]
1227     fn test_use_tree_flatten() {
1228         assert_eq!(
1229             parse_use_tree("a::b::{c, d, e, f}").flatten(),
1230             parse_use_trees!("a::b::c", "a::b::d", "a::b::e", "a::b::f",)
1231         );
1232
1233         assert_eq!(
1234             parse_use_tree("a::b::{c::{d, e, f}, g, h::{i, j, k}}").flatten(),
1235             parse_use_trees![
1236                 "a::b::c::d",
1237                 "a::b::c::e",
1238                 "a::b::c::f",
1239                 "a::b::g",
1240                 "a::b::h::i",
1241                 "a::b::h::j",
1242                 "a::b::h::k",
1243             ]
1244         );
1245     }
1246
1247     #[test]
1248     fn test_use_tree_normalize() {
1249         assert_eq!(parse_use_tree("a::self").normalize(), parse_use_tree("a"));
1250         assert_eq!(
1251             parse_use_tree("a::self as foo").normalize(),
1252             parse_use_tree("a as foo")
1253         );
1254         assert_eq!(
1255             parse_use_tree("a::{self}").normalize(),
1256             parse_use_tree("a::{self}")
1257         );
1258         assert_eq!(parse_use_tree("a::{b}").normalize(), parse_use_tree("a::b"));
1259         assert_eq!(
1260             parse_use_tree("a::{b, c::self}").normalize(),
1261             parse_use_tree("a::{b, c}")
1262         );
1263         assert_eq!(
1264             parse_use_tree("a::{b as bar, c::self}").normalize(),
1265             parse_use_tree("a::{b as bar, c}")
1266         );
1267     }
1268
1269     #[test]
1270     fn test_use_tree_ord() {
1271         assert!(parse_use_tree("a").normalize() < parse_use_tree("aa").normalize());
1272         assert!(parse_use_tree("a").normalize() < parse_use_tree("a::a").normalize());
1273         assert!(parse_use_tree("a").normalize() < parse_use_tree("*").normalize());
1274         assert!(parse_use_tree("a").normalize() < parse_use_tree("{a, b}").normalize());
1275         assert!(parse_use_tree("*").normalize() < parse_use_tree("{a, b}").normalize());
1276
1277         assert!(
1278             parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize()
1279                 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize()
1280         );
1281         assert!(
1282             parse_use_tree("serde::de::{Deserialize}").normalize()
1283                 < parse_use_tree("serde_json").normalize()
1284         );
1285         assert!(parse_use_tree("a::b::c").normalize() < parse_use_tree("a::b::*").normalize());
1286         assert!(
1287             parse_use_tree("foo::{Bar, Baz}").normalize()
1288                 < parse_use_tree("{Bar, Baz}").normalize()
1289         );
1290
1291         assert!(
1292             parse_use_tree("foo::{qux as bar}").normalize()
1293                 < parse_use_tree("foo::{self as bar}").normalize()
1294         );
1295         assert!(
1296             parse_use_tree("foo::{qux as bar}").normalize()
1297                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
1298         );
1299         assert!(
1300             parse_use_tree("foo::{self as bar, baz}").normalize()
1301                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
1302         );
1303
1304         assert!(parse_use_tree("foo").normalize() < parse_use_tree("Foo").normalize());
1305         assert!(parse_use_tree("foo").normalize() < parse_use_tree("foo::Bar").normalize());
1306
1307         assert!(
1308             parse_use_tree("std::cmp::{d, c, b, a}").normalize()
1309                 < parse_use_tree("std::cmp::{b, e, g, f}").normalize()
1310         );
1311     }
1312 }