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