src/imports.rs

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