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