src/imports.rs

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