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