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().ident
  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.ident.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, remaining_width) = 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, 0)
 473     } else {
 474         let remaining_width = shape.width.checked_sub(2).unwrap_or(0);
 475         let tactic = definitive_tactic(
 476             &list_items,
 477             context.config.imports_layout(),
 478             Separator::Comma,
 479             remaining_width,
 480         );
 481         (tactic, remaining_width)
 482     };
 483     let ends_with_newline = context.config.imports_indent() == IndentStyle::Block
 484         && tactic != DefinitiveListTactic::Horizontal;
 485     let fmt = ListFormatting {
 486         tactic,
 487         separator: ",",
 488         trailing_separator: if ends_with_newline {
 489             context.config.trailing_comma()
 490         } else {
 491             SeparatorTactic::Never
 492         },
 493         separator_place: SeparatorPlace::Back,
 494         shape: nested_shape,
 495         ends_with_newline,
 496         preserve_newline: true,
 497         config: context.config,
 498     };
 499
 500     let list_str = write_list(&list_items, &fmt)?;
 501
 502     let result = if (list_str.contains('\n') || list_str.len() > remaining_width)
 503         && context.config.imports_indent() == IndentStyle::Block
 504     {
 505         format!(
 506             "{{\n{}{}\n{}}}",
 507             nested_shape.indent.to_string(context.config),
 508             list_str,
 509             shape.indent.to_string(context.config)
 510         )
 511     } else {
 512         format!("{{{}}}", list_str)
 513     };
 514
 515     Some(result)
 516 }
 517
 518 impl Rewrite for UseSegment {
 519     fn rewrite(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
 520         Some(match *self {
 521             UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename),
 522             UseSegment::Ident(ref ident, None) => ident.clone(),
 523             UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename),
 524             UseSegment::Slf(None) => "self".to_owned(),
 525             UseSegment::Super(Some(ref rename)) => format!("super as {}", rename),
 526             UseSegment::Super(None) => "super".to_owned(),
 527             UseSegment::Glob => "*".to_owned(),
 528             UseSegment::List(ref use_tree_list) => rewrite_nested_use_tree(
 529                 context,
 530                 use_tree_list,
 531                 // 1 = "{" and "}"
 532                 shape.offset_left(1)?.sub_width(1)?,
 533             )?,
 534         })
 535     }
 536 }
 537
 538 impl Rewrite for UseTree {
 539     // This does NOT format attributes and visibility or add a trailing `;`.
 540     fn rewrite(&self, context: &RewriteContext, mut shape: Shape) -> Option<String> {
 541         let mut result = String::with_capacity(256);
 542         let mut iter = self.path.iter().peekable();
 543         while let Some(ref segment) = iter.next() {
 544             let segment_str = segment.rewrite(context, shape)?;
 545             result.push_str(&segment_str);
 546             if iter.peek().is_some() {
 547                 result.push_str("::");
 548                 // 2 = "::"
 549                 shape = shape.offset_left(2 + segment_str.len())?;
 550             }
 551         }
 552         Some(result)
 553     }
 554 }
 555
 556 #[cfg(test)]
 557 mod test {
 558     use super::*;
 559     use syntax::codemap::DUMMY_SP;
 560
 561     // Parse the path part of an import. This parser is not robust and is only
 562     // suitable for use in a test harness.
 563     fn parse_use_tree(s: &str) -> UseTree {
 564         use std::iter::Peekable;
 565         use std::mem::swap;
 566         use std::str::Chars;
 567
 568         struct Parser<'a> {
 569             input: Peekable<Chars<'a>>,
 570         }
 571
 572         impl<'a> Parser<'a> {
 573             fn bump(&mut self) {
 574                 self.input.next().unwrap();
 575             }
 576             fn eat(&mut self, c: char) {
 577                 assert!(self.input.next().unwrap() == c);
 578             }
 579             fn push_segment(
 580                 result: &mut Vec<UseSegment>,
 581                 buf: &mut String,
 582                 alias_buf: &mut Option<String>,
 583             ) {
 584                 if !buf.is_empty() {
 585                     let mut alias = None;
 586                     swap(alias_buf, &mut alias);
 587                     if buf == "self" {
 588                         result.push(UseSegment::Slf(alias));
 589                         *buf = String::new();
 590                         *alias_buf = None;
 591                     } else if buf == "super" {
 592                         result.push(UseSegment::Super(alias));
 593                         *buf = String::new();
 594                         *alias_buf = None;
 595                     } else {
 596                         let mut name = String::new();
 597                         swap(buf, &mut name);
 598                         result.push(UseSegment::Ident(name, alias));
 599                     }
 600                 }
 601             }
 602             fn parse_in_list(&mut self) -> UseTree {
 603                 let mut result = vec![];
 604                 let mut buf = String::new();
 605                 let mut alias_buf = None;
 606                 while let Some(&c) = self.input.peek() {
 607                     match c {
 608                         '{' => {
 609                             assert!(buf.is_empty());
 610                             self.bump();
 611                             result.push(UseSegment::List(self.parse_list()));
 612                             self.eat('}');
 613                         }
 614                         '*' => {
 615                             assert!(buf.is_empty());
 616                             self.bump();
 617                             result.push(UseSegment::Glob);
 618                         }
 619                         ':' => {
 620                             self.bump();
 621                             self.eat(':');
 622                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 623                         }
 624                         '}' | ',' => {
 625                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 626                             return UseTree {
 627                                 path: result,
 628                                 span: DUMMY_SP,
 629                                 list_item: None,
 630                                 visibility: None,
 631                                 attrs: None,
 632                             };
 633                         }
 634                         ' ' => {
 635                             self.bump();
 636                             self.eat('a');
 637                             self.eat('s');
 638                             self.eat(' ');
 639                             alias_buf = Some(String::new());
 640                         }
 641                         c => {
 642                             self.bump();
 643                             if let Some(ref mut buf) = alias_buf {
 644                                 buf.push(c);
 645                             } else {
 646                                 buf.push(c);
 647                             }
 648                         }
 649                     }
 650                 }
 651                 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 652                 UseTree {
 653                     path: result,
 654                     span: DUMMY_SP,
 655                     list_item: None,
 656                     visibility: None,
 657                     attrs: None,
 658                 }
 659             }
 660
 661             fn parse_list(&mut self) -> Vec<UseTree> {
 662                 let mut result = vec![];
 663                 loop {
 664                     match self.input.peek().unwrap() {
 665                         ',' | ' ' => self.bump(),
 666                         '}' => {
 667                             return result;
 668                         }
 669                         _ => result.push(self.parse_in_list()),
 670                     }
 671                 }
 672             }
 673         }
 674
 675         let mut parser = Parser {
 676             input: s.chars().peekable(),
 677         };
 678         parser.parse_in_list()
 679     }
 680
 681     #[test]
 682     fn test_use_tree_normalize() {
 683         assert_eq!(
 684             parse_use_tree("a::self").normalize(true),
 685             parse_use_tree("a")
 686         );
 687         assert_eq!(
 688             parse_use_tree("a::self as foo").normalize(true),
 689             parse_use_tree("a as foo")
 690         );
 691         assert_eq!(
 692             parse_use_tree("a::{self}").normalize(true),
 693             parse_use_tree("a")
 694         );
 695         assert_eq!(
 696             parse_use_tree("a::{b}").normalize(true),
 697             parse_use_tree("a::b")
 698         );
 699         assert_eq!(
 700             parse_use_tree("a::{b, c::self}").normalize(true),
 701             parse_use_tree("a::{b, c}")
 702         );
 703         assert_eq!(
 704             parse_use_tree("a::{b as bar, c::self}").normalize(true),
 705             parse_use_tree("a::{b as bar, c}")
 706         );
 707     }
 708
 709     #[test]
 710     fn test_use_tree_ord() {
 711         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("aa").normalize(true));
 712         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("a::a").normalize(true));
 713         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("*").normalize(true));
 714         assert!(parse_use_tree("a").normalize(true) < parse_use_tree("{a, b}").normalize(true));
 715         assert!(parse_use_tree("*").normalize(true) < parse_use_tree("{a, b}").normalize(true));
 716
 717         assert!(
 718             parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize(true)
 719                 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize(true)
 720         );
 721         assert!(
 722             parse_use_tree("serde::de::{Deserialize}").normalize(true)
 723                 < parse_use_tree("serde_json").normalize(true)
 724         );
 725         assert!(
 726             parse_use_tree("a::b::c").normalize(true) < parse_use_tree("a::b::*").normalize(true)
 727         );
 728         assert!(
 729             parse_use_tree("foo::{Bar, Baz}").normalize(true)
 730                 < parse_use_tree("{Bar, Baz}").normalize(true)
 731         );
 732
 733         assert!(
 734             parse_use_tree("foo::{self as bar}").normalize(true)
 735                 < parse_use_tree("foo::{qux as bar}").normalize(true)
 736         );
 737         assert!(
 738             parse_use_tree("foo::{qux as bar}").normalize(true)
 739                 < parse_use_tree("foo::{baz, qux as bar}").normalize(true)
 740         );
 741         assert!(
 742             parse_use_tree("foo::{self as bar, baz}").normalize(true)
 743                 < parse_use_tree("foo::{baz, qux as bar}").normalize(true)
 744         );
 745
 746         assert!(parse_use_tree("foo").normalize(true) < parse_use_tree("Foo").normalize(true));
 747         assert!(parse_use_tree("foo").normalize(true) < parse_use_tree("foo::Bar").normalize(true));
 748
 749         assert!(
 750             parse_use_tree("std::cmp::{d, c, b, a}").normalize(true)
 751                 < parse_use_tree("std::cmp::{b, e, g, f}").normalize(true)
 752         );
 753     }
 754 }