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