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