src/imports.rs

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