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