src/imports.rs

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