src/imports.rs

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