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::{BytePos, Span};
  16
  17 use codemap::SpanUtils;
  18 use config::IndentStyle;
  19 use lists::{definitive_tactic, itemize_list, write_list, ListFormatting, ListItem, Separator};
  20 use rewrite::{Rewrite, RewriteContext};
  21 use shape::Shape;
  22 use spanned::Spanned;
  23 use utils::mk_sp;
  24 use visitor::FmtVisitor;
  25
  26 use std::borrow::Cow;
  27
  28 /// Returns a name imported by a `use` declaration. e.g. returns `Ordering`
  29 /// for `std::cmp::Ordering` and `self` for `std::cmp::self`.
  30 pub fn path_to_imported_ident(path: &ast::Path) -> ast::Ident {
  31     path.segments.last().unwrap().identifier
  32 }
  33
  34 impl<'a> FmtVisitor<'a> {
  35     pub fn format_import(&mut self, item: &ast::Item, tree: &ast::UseTree) {
  36         let span = item.span;
  37         let shape = self.shape();
  38         let rw = UseTree::from_ast(
  39             &self.get_context(),
  40             tree,
  41             None,
  42             Some(item.vis.clone()),
  43             Some(item.span.lo()),
  44             Some(item.attrs.clone()),
  45         ).rewrite_top_level(&self.get_context(), shape);
  46         match rw {
  47             Some(ref s) if s.is_empty() => {
  48                 // Format up to last newline
  49                 let prev_span = mk_sp(self.last_pos, source!(self, span).lo());
  50                 let trimmed_snippet = self.snippet(prev_span).trim_right();
  51                 let span_end = self.last_pos + BytePos(trimmed_snippet.len() as u32);
  52                 self.format_missing(span_end);
  53                 // We have an excessive newline from the removed import.
  54                 if self.buffer.ends_with('\n') {
  55                     self.buffer.pop();
  56                     self.line_number -= 1;
  57                 }
  58                 self.last_pos = source!(self, span).hi();
  59             }
  60             Some(ref s) => {
  61                 self.format_missing_with_indent(source!(self, span).lo());
  62                 self.push_str(s);
  63                 self.last_pos = source!(self, span).hi();
  64             }
  65             None => {
  66                 self.format_missing_with_indent(source!(self, span).lo());
  67                 self.format_missing(source!(self, span).hi());
  68             }
  69         }
  70     }
  71 }
  72
  73 // Ordering of imports
  74
  75 // We order imports by translating to our own representation and then sorting.
  76 // The Rust AST data structures are really bad for this. Rustfmt applies a bunch
  77 // of normalisations to imports and since we want to sort based on the result
  78 // of these (and to maintain idempotence) we must apply the same normalisations
  79 // to the data structures for sorting.
  80 //
  81 // We sort `self` and `super` before other imports, then identifier imports,
  82 // then glob imports, then lists of imports. We do not take aliases into account
  83 // when ordering unless the imports are identical except for the alias (rare in
  84 // practice).
  85
  86 // FIXME(#2531) - we should unify the comparison code here with the formatting
  87 // code elsewhere since we are essentially string-ifying twice. Furthermore, by
  88 // parsing to our own format on comparison, we repeat a lot of work when
  89 // sorting.
  90
  91 // FIXME we do a lot of allocation to make our own representation.
  92 #[derive(Debug, Clone, Eq, PartialEq)]
  93 pub enum UseSegment {
  94     Ident(String, Option<String>),
  95     Slf(Option<String>),
  96     Super(Option<String>),
  97     Glob,
  98     List(Vec<UseTree>),
  99 }
 100
 101 #[derive(Debug, Clone)]
 102 pub struct UseTree {
 103     pub path: Vec<UseSegment>,
 104     pub span: Span,
 105     // Comment information within nested use tree.
 106     list_item: Option<ListItem>,
 107     // Additional fields for top level use items.
 108     // Should we have another struct for top-level use items rather than reusing this?
 109     visibility: Option<ast::Visibility>,
 110     attrs: Option<Vec<ast::Attribute>>,
 111 }
 112
 113 impl PartialEq for UseTree {
 114     fn eq(&self, other: &UseTree) -> bool {
 115         self.path == other.path
 116     }
 117 }
 118 impl Eq for UseTree {}
 119
 120 impl UseSegment {
 121     // Clone a version of self with any top-level alias removed.
 122     fn remove_alias(&self) -> UseSegment {
 123         match *self {
 124             UseSegment::Ident(ref s, _) => UseSegment::Ident(s.clone(), None),
 125             UseSegment::Slf(_) => UseSegment::Slf(None),
 126             UseSegment::Super(_) => UseSegment::Super(None),
 127             _ => self.clone(),
 128         }
 129     }
 130
 131     fn from_path_segment(path_seg: &ast::PathSegment) -> Option<UseSegment> {
 132         let name = path_seg.identifier.name.as_str();
 133         if name == "{{root}}" {
 134             return None;
 135         }
 136         Some(if name == "self" {
 137             UseSegment::Slf(None)
 138         } else if name == "super" {
 139             UseSegment::Super(None)
 140         } else {
 141             UseSegment::Ident((*name).to_owned(), None)
 142         })
 143     }
 144 }
 145
 146 impl UseTree {
 147     // Rewrite use tree with `use ` and a trailing `;`.
 148     pub fn rewrite_top_level(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
 149         let mut result = String::with_capacity(256);
 150         if let Some(ref attrs) = self.attrs {
 151             result.push_str(&attrs.rewrite(context, shape)?);
 152             if !result.is_empty() {
 153                 result.push_str(&shape.indent.to_string_with_newline(context.config));
 154             }
 155         }
 156
 157         let vis = self.visibility
 158             .as_ref()
 159             .map_or(Cow::from(""), |vis| ::utils::format_visibility(&vis));
 160         result.push_str(&self.rewrite(context, shape.offset_left(vis.len())?)
 161             .map(|s| {
 162                 if s.is_empty() {
 163                     s.to_owned()
 164                 } else {
 165                     format!("{}use {};", vis, s)
 166                 }
 167             })?);
 168         Some(result)
 169     }
 170
 171     pub fn from_ast_with_normalization(
 172         context: &RewriteContext,
 173         item: &ast::Item,
 174     ) -> Option<UseTree> {
 175         match item.node {
 176             ast::ItemKind::Use(ref use_tree) => Some(
 177                 UseTree::from_ast(
 178                     context,
 179                     use_tree,
 180                     None,
 181                     Some(item.vis.clone()),
 182                     Some(item.span().lo()),
 183                     if item.attrs.is_empty() {
 184                         None
 185                     } else {
 186                         Some(item.attrs.clone())
 187                     },
 188                 ).normalize(context.config.reorder_imported_names()),
 189             ),
 190             _ => None,
 191         }
 192     }
 193
 194     fn from_ast(
 195         context: &RewriteContext,
 196         a: &ast::UseTree,
 197         list_item: Option<ListItem>,
 198         visibility: Option<ast::Visibility>,
 199         opt_lo: Option<BytePos>,
 200         attrs: Option<Vec<ast::Attribute>>,
 201     ) -> UseTree {
 202         let span = if let Some(lo) = opt_lo {
 203             mk_sp(lo, a.span.hi())
 204         } else {
 205             a.span
 206         };
 207         let mut result = UseTree {
 208             path: vec![],
 209             span,
 210             list_item,
 211             visibility,
 212             attrs,
 213         };
 214         for p in &a.prefix.segments {
 215             if let Some(use_segment) = UseSegment::from_path_segment(p) {
 216                 result.path.push(use_segment);
 217             }
 218         }
 219         match a.kind {
 220             UseTreeKind::Glob => {
 221                 result.path.push(UseSegment::Glob);
 222             }
 223             UseTreeKind::Nested(ref list) => {
 224                 // Extract comments between nested use items.
 225                 // This needs to be done before sorting use items.
 226                 let items: Vec<_> = itemize_list(
 227                     context.snippet_provider,
 228                     list.iter().map(|(tree, _)| tree),
 229                     "}",
 230                     ",",
 231                     |tree| tree.span.lo(),
 232                     |tree| tree.span.hi(),
 233                     |_| Some("".to_owned()), // We only need comments for now.
 234                     context.snippet_provider.span_after(a.span, "{"),
 235                     a.span.hi(),
 236                     false,
 237                 ).collect();
 238                 result.path.push(UseSegment::List(
 239                     list.iter()
 240                         .zip(items.into_iter())
 241                         .map(|(t, list_item)| {
 242                             Self::from_ast(context, &t.0, Some(list_item), None, None, None)
 243                         })
 244                         .collect(),
 245                 ));
 246             }
 247             UseTreeKind::Simple(ref rename) => {
 248                 let mut name = (*path_to_imported_ident(&a.prefix).name.as_str()).to_owned();
 249                 let alias = rename.and_then(|ident| {
 250                     if ident == path_to_imported_ident(&a.prefix) {
 251                         None
 252                     } else {
 253                         Some(ident.to_string())
 254                     }
 255                 });
 256
 257                 let segment = if &name == "self" {
 258                     UseSegment::Slf(alias)
 259                 } else if &name == "super" {
 260                     UseSegment::Super(alias)
 261                 } else {
 262                     UseSegment::Ident(name, alias)
 263                 };
 264
 265                 // `name` is already in result.
 266                 result.path.pop();
 267                 result.path.push(segment);
 268             }
 269         }
 270         result
 271     }
 272
 273     // Do the adjustments that rustfmt does elsewhere to use paths.
 274     pub fn normalize(mut self, do_sort: bool) -> UseTree {
 275         let mut last = self.path.pop().expect("Empty use tree?");
 276         // Hack around borrow checker.
 277         let mut normalize_sole_list = false;
 278         let mut aliased_self = false;
 279
 280         // Remove foo::{} or self without attributes.
 281         match last {
 282             _ if self.attrs.is_some() => (),
 283             UseSegment::List(ref list) if list.is_empty() => {
 284                 self.path = vec![];
 285                 return self;
 286             }
 287             UseSegment::Slf(None) if self.path.is_empty() && self.visibility.is_some() => {
 288                 self.path = vec![];
 289                 return self;
 290             }
 291             _ => (),
 292         }
 293
 294         // Normalise foo::self -> foo.
 295         if let UseSegment::Slf(None) = last {
 296             if self.path.len() > 0 {
 297                 return self;
 298             }
 299         }
 300
 301         // Normalise foo::self as bar -> foo as bar.
 302         if let UseSegment::Slf(_) = last {
 303             match self.path.last() {
 304                 None => {}
 305                 Some(UseSegment::Ident(_, None)) => {
 306                     aliased_self = true;
 307                 }
 308                 _ => unreachable!(),
 309             }
 310         }
 311
 312         if aliased_self {
 313             match self.path.last() {
 314                 Some(UseSegment::Ident(_, ref mut old_rename)) => {
 315                     assert!(old_rename.is_none());
 316                     if let UseSegment::Slf(Some(rename)) = last {
 317                         *old_rename = Some(rename);
 318                         return self;
 319                     }
 320                 }
 321                 _ => unreachable!(),
 322             }
 323         }
 324
 325         // Normalise foo::{bar} -> foo::bar
 326         if let UseSegment::List(ref list) = last {
 327             if list.len() == 1 {
 328                 normalize_sole_list = true;
 329             }
 330         }
 331
 332         if normalize_sole_list {
 333             match last {
 334                 UseSegment::List(list) => {
 335                     for seg in &list[0].path {
 336                         self.path.push(seg.clone());
 337                     }
 338                     return self.normalize(do_sort);
 339                 }
 340                 _ => unreachable!(),
 341             }
 342         }
 343
 344         // Recursively normalize elements of a list use (including sorting the list).
 345         if let UseSegment::List(list) = last {
 346             let mut list = list.into_iter()
 347                 .map(|ut| ut.normalize(do_sort))
 348                 .collect::<Vec<_>>();
 349             if do_sort {
 350                 list.sort();
 351             }
 352             last = UseSegment::List(list);
 353         }
 354
 355         self.path.push(last);
 356         self
 357     }
 358 }
 359
 360 impl PartialOrd for UseSegment {
 361     fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
 362         Some(self.cmp(other))
 363     }
 364 }
 365 impl PartialOrd for UseTree {
 366     fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> {
 367         Some(self.cmp(other))
 368     }
 369 }
 370 impl Ord for UseSegment {
 371     fn cmp(&self, other: &UseSegment) -> Ordering {
 372         use self::UseSegment::*;
 373
 374         fn is_upper_snake_case(s: &str) -> bool {
 375             s.chars().all(|c| c.is_uppercase() || c == '_')
 376         }
 377
 378         match (self, other) {
 379             (&Slf(ref a), &Slf(ref b)) | (&Super(ref a), &Super(ref b)) => a.cmp(b),
 380             (&Glob, &Glob) => Ordering::Equal,
 381             (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
 382                 // snake_case < CamelCase < UPPER_SNAKE_CASE
 383                 if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
 384                     return Ordering::Greater;
 385                 }
 386                 if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) {
 387                     return Ordering::Less;
 388                 }
 389                 if is_upper_snake_case(ia) && !is_upper_snake_case(ib) {
 390                     return Ordering::Greater;
 391                 }
 392                 if !is_upper_snake_case(ia) && is_upper_snake_case(ib) {
 393                     return Ordering::Less;
 394                 }
 395                 let ident_ord = ia.cmp(ib);
 396                 if ident_ord != Ordering::Equal {
 397                     return ident_ord;
 398                 }
 399                 if aa.is_none() && ab.is_some() {
 400                     return Ordering::Less;
 401                 }
 402                 if aa.is_some() && ab.is_none() {
 403                     return Ordering::Greater;
 404                 }
 405                 aa.cmp(ab)
 406             }
 407             (&List(ref a), &List(ref b)) => {
 408                 for (a, b) in a.iter().zip(b.iter()) {
 409                     let ord = a.cmp(b);
 410                     if ord != Ordering::Equal {
 411                         return ord;
 412                     }
 413                 }
 414
 415                 a.len().cmp(&b.len())
 416             }
 417             (&Slf(_), _) => Ordering::Less,
 418             (_, &Slf(_)) => Ordering::Greater,
 419             (&Super(_), _) => Ordering::Less,
 420             (_, &Super(_)) => Ordering::Greater,
 421             (&Ident(..), _) => Ordering::Less,
 422             (_, &Ident(..)) => Ordering::Greater,
 423             (&Glob, _) => Ordering::Less,
 424             (_, &Glob) => Ordering::Greater,
 425         }
 426     }
 427 }
 428 impl Ord for UseTree {
 429     fn cmp(&self, other: &UseTree) -> Ordering {
 430         for (a, b) in self.path.iter().zip(other.path.iter()) {
 431             let ord = a.cmp(b);
 432             // The comparison without aliases is a hack to avoid situations like
 433             // comparing `a::b` to `a as c` - where the latter should be ordered
 434             // first since it is shorter.
 435             if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal
 436             {
 437                 return ord;
 438             }
 439         }
 440
 441         self.path.len().cmp(&other.path.len())
 442     }
 443 }
 444
 445 fn rewrite_nested_use_tree(
 446     context: &RewriteContext,
 447     use_tree_list: &[UseTree],
 448     shape: Shape,
 449 ) -> Option<String> {
 450     let mut list_items = Vec::with_capacity(use_tree_list.len());
 451     let nested_shape = match context.config.imports_indent() {
 452         IndentStyle::Block => shape
 453             .block_indent(context.config.tab_spaces())
 454             .with_max_width(context.config)
 455             .sub_width(1)?,
 456         IndentStyle::Visual => shape.visual_indent(0),
 457     };
 458     for use_tree in use_tree_list {
 459         let mut list_item = use_tree.list_item.clone()?;
 460         list_item.item = use_tree.rewrite(context, nested_shape);
 461         list_items.push(list_item);
 462     }
 463     let tactic = if use_tree_list.iter().any(|use_segment| {
 464         use_segment
 465             .path
 466             .last()
 467             .map_or(false, |last_segment| match last_segment {
 468                 UseSegment::List(..) => true,
 469                 _ => false,
 470             })
 471     }) {
 472         DefinitiveListTactic::Vertical
 473     } else {
 474         definitive_tactic(
 475             &list_items,
 476             context.config.imports_layout(),
 477             Separator::Comma,
 478             shape.width.checked_sub(2).unwrap_or(0),
 479         )
 480     };
 481     let ends_with_newline = context.config.imports_indent() == IndentStyle::Block
 482         && tactic != DefinitiveListTactic::Horizontal;
 483     let fmt = ListFormatting {
 484         tactic,
 485         separator: ",",
 486         trailing_separator: if ends_with_newline {
 487             context.config.trailing_comma()
 488         } else {
 489             SeparatorTactic::Never
 490         },
 491         separator_place: SeparatorPlace::Back,
 492         shape: nested_shape,
 493         ends_with_newline,
 494         preserve_newline: true,
 495         config: context.config,
 496     };
 497
 498     let list_str = write_list(&list_items, &fmt)?;
 499
 500     let result = if (list_str.contains('\n') || list_str.len() > remaining_width)
 501         && context.config.imports_indent() == IndentStyle::Block
 502     {
 503         format!(
 504             "{{\n{}{}\n{}}}",
 505             nested_shape.indent.to_string(context.config),
 506             list_str,
 507             shape.indent.to_string(context.config)
 508         )
 509     } else {
 510         format!("{{{}}}", list_str)
 511     };
 512
 513     Some(result)
 514 }
 515
 516 impl Rewrite for UseSegment {
 517     fn rewrite(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
 518         Some(match *self {
 519             UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename),
 520             UseSegment::Ident(ref ident, None) => ident.clone(),
 521             UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename),
 522             UseSegment::Slf(None) => "self".to_owned(),
 523             UseSegment::Super(Some(ref rename)) => format!("super as {}", rename),
 524             UseSegment::Super(None) => "super".to_owned(),
 525             UseSegment::Glob => "*".to_owned(),
 526             UseSegment::List(ref use_tree_list) => rewrite_nested_use_tree(
 527                 context,
 528                 use_tree_list,
 529                 // 1 = "{" and "}"
 530                 shape.offset_left(1)?.sub_width(1)?,
 531             )?,
 532         })
 533     }
 534 }
 535
 536 impl Rewrite for UseTree {
 537     // This does NOT format attributes and visibility or add a trailing `;`.
 538     fn rewrite(&self, context: &RewriteContext, mut shape: Shape) -> Option<String> {
 539         let mut result = String::with_capacity(256);
 540         let mut iter = self.path.iter().peekable();
 541         while let Some(ref segment) = iter.next() {
 542             let segment_str = segment.rewrite(context, shape)?;
 543             result.push_str(&segment_str);
 544             if iter.peek().is_some() {
 545                 result.push_str("::");
 546                 // 2 = "::"
 547                 shape = shape.offset_left(2 + segment_str.len())?;
 548             }
 549         }
 550         Some(result)
 551     }
 552 }
 553
 554 #[cfg(test)]
 555 mod test {
 556     use super::*;
 557     use syntax::codemap::DUMMY_SP;
 558
 559     // Parse the path part of an import. This parser is not robust and is only
 560     // suitable for use in a test harness.
 561     fn parse_use_tree(s: &str) -> UseTree {
 562         use std::iter::Peekable;
 563         use std::mem::swap;
 564         use std::str::Chars;
 565
 566         struct Parser<'a> {
 567             input: Peekable<Chars<'a>>,
 568         }
 569
 570         impl<'a> Parser<'a> {
 571             fn bump(&mut self) {
 572                 self.input.next().unwrap();
 573             }
 574             fn eat(&mut self, c: char) {
 575                 assert!(self.input.next().unwrap() == c);
 576             }
 577             fn push_segment(
 578                 result: &mut Vec<UseSegment>,
 579                 buf: &mut String,
 580                 alias_buf: &mut Option<String>,
 581             ) {
 582                 if !buf.is_empty() {
 583                     let mut alias = None;
 584                     swap(alias_buf, &mut alias);
 585                     if buf == "self" {
 586                         result.push(UseSegment::Slf(alias));
 587                         *buf = String::new();
 588                         *alias_buf = None;
 589                     } else if buf == "super" {
 590                         result.push(UseSegment::Super(alias));
 591                         *buf = String::new();
 592                         *alias_buf = None;
 593                     } else {
 594                         let mut name = String::new();
 595                         swap(buf, &mut name);
 596                         result.push(UseSegment::Ident(name, alias));
 597                     }
 598                 }
 599             }
 600             fn parse_in_list(&mut self) -> UseTree {
 601                 let mut result = vec![];
 602                 let mut buf = String::new();
 603                 let mut alias_buf = None;
 604                 while let Some(&c) = self.input.peek() {
 605                     match c {
 606                         '{' => {
 607                             assert!(buf.is_empty());
 608                             self.bump();
 609                             result.push(UseSegment::List(self.parse_list()));
 610                             self.eat('}');
 611                         }
 612                         '*' => {
 613                             assert!(buf.is_empty());
 614                             self.bump();
 615                             result.push(UseSegment::Glob);
 616                         }
 617                         ':' => {
 618                             self.bump();
 619                             self.eat(':');
 620                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 621                         }
 622                         '}' | ',' => {
 623                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 624                             return UseTree {
 625                                 path: result,
 626                                 span: DUMMY_SP,
 627                                 list_item: None,
 628                                 visibility: None,
 629                                 attrs: None,
 630                             };
 631                         }
 632                         ' ' => {
 633                             self.bump();
 634                             self.eat('a');
 635                             self.eat('s');
 636                             self.eat(' ');
 637                             alias_buf = Some(String::new());
 638                         }
 639                         c => {
 640                             self.bump();
 641                             if let Some(ref mut buf) = alias_buf {
 642                                 buf.push(c);
 643                             } else {
 644                                 buf.push(c);
 645                             }
 646                         }
 647                     }
 648                 }
 649                 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 650                 UseTree {
 651                     path: result,
 652                     span: DUMMY_SP,
 653                     list_item: None,
 654                     visibility: None,
 655                     attrs: None,
 656                 }
 657             }
 658
 659             fn parse_list(&mut self) -> Vec<UseTree> {
 660                 let mut result = vec![];
 661                 loop {
 662                     match self.input.peek().unwrap() {
 663                         ',' | ' ' => self.bump(),
 664                         '}' => {
 665                             return result;
 666                         }
 667                         _ => result.push(self.parse_in_list()),
 668                     }
 669                 }
 670             }
 671         }
 672
 673         let mut parser = Parser {
 674             input: s.chars().peekable(),
 675         };
 676         parser.parse_in_list()
 677     }
 678
 679     #[test]
 680     fn test_use_tree_normalize() {
 681         assert_eq!(
 682             parse_use_tree("a::self").normalize(true),
 683             parse_use_tree("a")
 684         );
 685         assert_eq!(
 686             parse_use_tree("a::self as foo").normalize(true),
 687             parse_use_tree("a as foo")
 688         );
 689         assert_eq!(
 690             parse_use_tree("a::{self}").normalize(true),
 691             parse_use_tree("a")
 692         );
 693         assert_eq!(
 694             parse_use_tree("a::{b}").normalize(true),
 695             parse_use_tree("a::b")
 696         );
 697         assert_eq!(
 698             parse_use_tree("a::{b, c::self}").normalize(true),
 699             parse_use_tree("a::{b, c}")
 700         );
 701         assert_eq!(
 702             parse_use_tree("a::{b as bar, c::self}").normalize(true),
 703             parse_use_tree("a::{b as bar, c}")
 704         );
 705     }
 706
 707     #[test]
 708     fn test_use_tree_ord() {
 709         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("aa").normalize(true));
 710         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("a::a").normalize(true));
 711         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("*").normalize(true));
 712         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("{a, b}").normalize(true));
 713         assert!(parse_use_tree("*").normalize(true) < parse_use_tree("{a, b}").normalize(true));
 714
 715         assert!(
 716             parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize(true)
 717                 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize(true)
 718         );
 719         assert!(
 720             parse_use_tree("serde::de::{Deserialize}").normalize(true)
 721                 < parse_use_tree("serde_json").normalize(true)
 722         );
 723         assert!(
 724             parse_use_tree("a::b::c").normalize(true) < parse_use_tree("a::b::*").normalize(true)
 725         );
 726         assert!(
 727             parse_use_tree("foo::{Bar, Baz}").normalize(true)
 728                 < parse_use_tree("{Bar, Baz}").normalize(true)
 729         );
 730
 731         assert!(
 732             parse_use_tree("foo::{self as bar}").normalize(true)
 733                 < parse_use_tree("foo::{qux as bar}").normalize(true)
 734         );
 735         assert!(
 736             parse_use_tree("foo::{qux as bar}").normalize(true)
 737                 < parse_use_tree("foo::{baz, qux as bar}").normalize(true)
 738         );
 739         assert!(
 740             parse_use_tree("foo::{self as bar, baz}").normalize(true)
 741                 < parse_use_tree("foo::{baz, qux as bar}").normalize(true)
 742         );
 743
 744         assert!(parse_use_tree("foo").normalize(true) < parse_use_tree("Foo").normalize(true));
 745         assert!(parse_use_tree("foo").normalize(true) < parse_use_tree("foo::Bar").normalize(true));
 746
 747         assert!(
 748             parse_use_tree("std::cmp::{d, c, b, a}").normalize(true)
 749                 < parse_use_tree("std::cmp::{b, e, g, f}").normalize(true)
 750         );
 751     }
 752 }