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(),
 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) -> 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         let mut done = false;
 313         if aliased_self {
 314             match self.path.last_mut() {
 315                 Some(UseSegment::Ident(_, ref mut old_rename)) => {
 316                     assert!(old_rename.is_none());
 317                     if let UseSegment::Slf(Some(rename)) = last.clone() {
 318                         *old_rename = Some(rename);
 319                         done = true;
 320                     }
 321                 }
 322                 _ => unreachable!(),
 323             }
 324         }
 325
 326         if done {
 327             return self;
 328         }
 329
 330         // Normalise foo::{bar} -> foo::bar
 331         if let UseSegment::List(ref list) = last {
 332             if list.len() == 1 {
 333                 normalize_sole_list = true;
 334             }
 335         }
 336
 337         if normalize_sole_list {
 338             match last {
 339                 UseSegment::List(list) => {
 340                     for seg in &list[0].path {
 341                         self.path.push(seg.clone());
 342                     }
 343                     return self.normalize();
 344                 }
 345                 _ => unreachable!(),
 346             }
 347         }
 348
 349         // Recursively normalize elements of a list use (including sorting the list).
 350         if let UseSegment::List(list) = last {
 351             let mut list = list.into_iter()
 352                 .map(|ut| ut.normalize())
 353                 .collect::<Vec<_>>();
 354             list.sort();
 355             last = UseSegment::List(list);
 356         }
 357
 358         self.path.push(last);
 359         self
 360     }
 361 }
 362
 363 impl PartialOrd for UseSegment {
 364     fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
 365         Some(self.cmp(other))
 366     }
 367 }
 368 impl PartialOrd for UseTree {
 369     fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> {
 370         Some(self.cmp(other))
 371     }
 372 }
 373 impl Ord for UseSegment {
 374     fn cmp(&self, other: &UseSegment) -> Ordering {
 375         use self::UseSegment::*;
 376
 377         fn is_upper_snake_case(s: &str) -> bool {
 378             s.chars().all(|c| c.is_uppercase() || c == '_')
 379         }
 380
 381         match (self, other) {
 382             (&Slf(ref a), &Slf(ref b)) | (&Super(ref a), &Super(ref b)) => a.cmp(b),
 383             (&Glob, &Glob) => Ordering::Equal,
 384             (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
 385                 // snake_case < CamelCase < UPPER_SNAKE_CASE
 386                 if ia.starts_with(char::is_uppercase) && ib.starts_with(char::is_lowercase) {
 387                     return Ordering::Greater;
 388                 }
 389                 if ia.starts_with(char::is_lowercase) && ib.starts_with(char::is_uppercase) {
 390                     return Ordering::Less;
 391                 }
 392                 if is_upper_snake_case(ia) && !is_upper_snake_case(ib) {
 393                     return Ordering::Greater;
 394                 }
 395                 if !is_upper_snake_case(ia) && is_upper_snake_case(ib) {
 396                     return Ordering::Less;
 397                 }
 398                 let ident_ord = ia.cmp(ib);
 399                 if ident_ord != Ordering::Equal {
 400                     return ident_ord;
 401                 }
 402                 if aa.is_none() && ab.is_some() {
 403                     return Ordering::Less;
 404                 }
 405                 if aa.is_some() && ab.is_none() {
 406                     return Ordering::Greater;
 407                 }
 408                 aa.cmp(ab)
 409             }
 410             (&List(ref a), &List(ref b)) => {
 411                 for (a, b) in a.iter().zip(b.iter()) {
 412                     let ord = a.cmp(b);
 413                     if ord != Ordering::Equal {
 414                         return ord;
 415                     }
 416                 }
 417
 418                 a.len().cmp(&b.len())
 419             }
 420             (&Slf(_), _) => Ordering::Less,
 421             (_, &Slf(_)) => Ordering::Greater,
 422             (&Super(_), _) => Ordering::Less,
 423             (_, &Super(_)) => Ordering::Greater,
 424             (&Ident(..), _) => Ordering::Less,
 425             (_, &Ident(..)) => Ordering::Greater,
 426             (&Glob, _) => Ordering::Less,
 427             (_, &Glob) => Ordering::Greater,
 428         }
 429     }
 430 }
 431 impl Ord for UseTree {
 432     fn cmp(&self, other: &UseTree) -> Ordering {
 433         for (a, b) in self.path.iter().zip(other.path.iter()) {
 434             let ord = a.cmp(b);
 435             // The comparison without aliases is a hack to avoid situations like
 436             // comparing `a::b` to `a as c` - where the latter should be ordered
 437             // first since it is shorter.
 438             if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal
 439             {
 440                 return ord;
 441             }
 442         }
 443
 444         self.path.len().cmp(&other.path.len())
 445     }
 446 }
 447
 448 fn rewrite_nested_use_tree(
 449     context: &RewriteContext,
 450     use_tree_list: &[UseTree],
 451     shape: Shape,
 452 ) -> Option<String> {
 453     let mut list_items = Vec::with_capacity(use_tree_list.len());
 454     let nested_shape = match context.config.imports_indent() {
 455         IndentStyle::Block => shape
 456             .block_indent(context.config.tab_spaces())
 457             .with_max_width(context.config)
 458             .sub_width(1)?,
 459         IndentStyle::Visual => shape.visual_indent(0),
 460     };
 461     for use_tree in use_tree_list {
 462         let mut list_item = use_tree.list_item.clone()?;
 463         list_item.item = use_tree.rewrite(context, nested_shape);
 464         list_items.push(list_item);
 465     }
 466     let (tactic, remaining_width) = if use_tree_list.iter().any(|use_segment| {
 467         use_segment
 468             .path
 469             .last()
 470             .map_or(false, |last_segment| match last_segment {
 471                 UseSegment::List(..) => true,
 472                 _ => false,
 473             })
 474     }) {
 475         (DefinitiveListTactic::Vertical, 0)
 476     } else {
 477         let remaining_width = shape.width.checked_sub(2).unwrap_or(0);
 478         let tactic = definitive_tactic(
 479             &list_items,
 480             context.config.imports_layout(),
 481             Separator::Comma,
 482             remaining_width,
 483         );
 484         (tactic, remaining_width)
 485     };
 486
 487     let ends_with_newline = context.config.imports_indent() == IndentStyle::Block
 488         && tactic != DefinitiveListTactic::Horizontal;
 489     let fmt = ListFormatting {
 490         tactic,
 491         separator: ",",
 492         trailing_separator: if ends_with_newline {
 493             context.config.trailing_comma()
 494         } else {
 495             SeparatorTactic::Never
 496         },
 497         separator_place: SeparatorPlace::Back,
 498         shape: nested_shape,
 499         ends_with_newline,
 500         preserve_newline: true,
 501         config: context.config,
 502     };
 503
 504     let list_str = write_list(&list_items, &fmt)?;
 505
 506     let result = if (list_str.contains('\n') || list_str.len() > remaining_width)
 507         && context.config.imports_indent() == IndentStyle::Block
 508     {
 509         format!(
 510             "{{\n{}{}\n{}}}",
 511             nested_shape.indent.to_string(context.config),
 512             list_str,
 513             shape.indent.to_string(context.config)
 514         )
 515     } else {
 516         format!("{{{}}}", list_str)
 517     };
 518
 519     Some(result)
 520 }
 521
 522 impl Rewrite for UseSegment {
 523     fn rewrite(&self, context: &RewriteContext, shape: Shape) -> Option<String> {
 524         Some(match *self {
 525             UseSegment::Ident(ref ident, Some(ref rename)) => format!("{} as {}", ident, rename),
 526             UseSegment::Ident(ref ident, None) => ident.clone(),
 527             UseSegment::Slf(Some(ref rename)) => format!("self as {}", rename),
 528             UseSegment::Slf(None) => "self".to_owned(),
 529             UseSegment::Super(Some(ref rename)) => format!("super as {}", rename),
 530             UseSegment::Super(None) => "super".to_owned(),
 531             UseSegment::Glob => "*".to_owned(),
 532             UseSegment::List(ref use_tree_list) => rewrite_nested_use_tree(
 533                 context,
 534                 use_tree_list,
 535                 // 1 = "{" and "}"
 536                 shape.offset_left(1)?.sub_width(1)?,
 537             )?,
 538         })
 539     }
 540 }
 541
 542 impl Rewrite for UseTree {
 543     // This does NOT format attributes and visibility or add a trailing `;`.
 544     fn rewrite(&self, context: &RewriteContext, mut shape: Shape) -> Option<String> {
 545         let mut result = String::with_capacity(256);
 546         let mut iter = self.path.iter().peekable();
 547         while let Some(ref segment) = iter.next() {
 548             let segment_str = segment.rewrite(context, shape)?;
 549             result.push_str(&segment_str);
 550             if iter.peek().is_some() {
 551                 result.push_str("::");
 552                 // 2 = "::"
 553                 shape = shape.offset_left(2 + segment_str.len())?;
 554             }
 555         }
 556         Some(result)
 557     }
 558 }
 559
 560 #[cfg(test)]
 561 mod test {
 562     use super::*;
 563     use syntax::codemap::DUMMY_SP;
 564
 565     // Parse the path part of an import. This parser is not robust and is only
 566     // suitable for use in a test harness.
 567     fn parse_use_tree(s: &str) -> UseTree {
 568         use std::iter::Peekable;
 569         use std::mem::swap;
 570         use std::str::Chars;
 571
 572         struct Parser<'a> {
 573             input: Peekable<Chars<'a>>,
 574         }
 575
 576         impl<'a> Parser<'a> {
 577             fn bump(&mut self) {
 578                 self.input.next().unwrap();
 579             }
 580             fn eat(&mut self, c: char) {
 581                 assert!(self.input.next().unwrap() == c);
 582             }
 583             fn push_segment(
 584                 result: &mut Vec<UseSegment>,
 585                 buf: &mut String,
 586                 alias_buf: &mut Option<String>,
 587             ) {
 588                 if !buf.is_empty() {
 589                     let mut alias = None;
 590                     swap(alias_buf, &mut alias);
 591                     if buf == "self" {
 592                         result.push(UseSegment::Slf(alias));
 593                         *buf = String::new();
 594                         *alias_buf = None;
 595                     } else if buf == "super" {
 596                         result.push(UseSegment::Super(alias));
 597                         *buf = String::new();
 598                         *alias_buf = None;
 599                     } else {
 600                         let mut name = String::new();
 601                         swap(buf, &mut name);
 602                         result.push(UseSegment::Ident(name, alias));
 603                     }
 604                 }
 605             }
 606             fn parse_in_list(&mut self) -> UseTree {
 607                 let mut result = vec![];
 608                 let mut buf = String::new();
 609                 let mut alias_buf = None;
 610                 while let Some(&c) = self.input.peek() {
 611                     match c {
 612                         '{' => {
 613                             assert!(buf.is_empty());
 614                             self.bump();
 615                             result.push(UseSegment::List(self.parse_list()));
 616                             self.eat('}');
 617                         }
 618                         '*' => {
 619                             assert!(buf.is_empty());
 620                             self.bump();
 621                             result.push(UseSegment::Glob);
 622                         }
 623                         ':' => {
 624                             self.bump();
 625                             self.eat(':');
 626                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 627                         }
 628                         '}' | ',' => {
 629                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 630                             return UseTree {
 631                                 path: result,
 632                                 span: DUMMY_SP,
 633                                 list_item: None,
 634                                 visibility: None,
 635                                 attrs: None,
 636                             };
 637                         }
 638                         ' ' => {
 639                             self.bump();
 640                             self.eat('a');
 641                             self.eat('s');
 642                             self.eat(' ');
 643                             alias_buf = Some(String::new());
 644                         }
 645                         c => {
 646                             self.bump();
 647                             if let Some(ref mut buf) = alias_buf {
 648                                 buf.push(c);
 649                             } else {
 650                                 buf.push(c);
 651                             }
 652                         }
 653                     }
 654                 }
 655                 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 656                 UseTree {
 657                     path: result,
 658                     span: DUMMY_SP,
 659                     list_item: None,
 660                     visibility: None,
 661                     attrs: None,
 662                 }
 663             }
 664
 665             fn parse_list(&mut self) -> Vec<UseTree> {
 666                 let mut result = vec![];
 667                 loop {
 668                     match self.input.peek().unwrap() {
 669                         ',' | ' ' => self.bump(),
 670                         '}' => {
 671                             return result;
 672                         }
 673                         _ => result.push(self.parse_in_list()),
 674                     }
 675                 }
 676             }
 677         }
 678
 679         let mut parser = Parser {
 680             input: s.chars().peekable(),
 681         };
 682         parser.parse_in_list()
 683     }
 684
 685     #[test]
 686     fn test_use_tree_normalize() {
 687         assert_eq!(parse_use_tree("a::self").normalize(), parse_use_tree("a"));
 688         assert_eq!(
 689             parse_use_tree("a::self as foo").normalize(),
 690             parse_use_tree("a as foo")
 691         );
 692         assert_eq!(parse_use_tree("a::{self}").normalize(), parse_use_tree("a"));
 693         assert_eq!(parse_use_tree("a::{b}").normalize(), parse_use_tree("a::b"));
 694         assert_eq!(
 695             parse_use_tree("a::{b, c::self}").normalize(),
 696             parse_use_tree("a::{b, c}")
 697         );
 698         assert_eq!(
 699             parse_use_tree("a::{b as bar, c::self}").normalize(),
 700             parse_use_tree("a::{b as bar, c}")
 701         );
 702     }
 703
 704     #[test]
 705     fn test_use_tree_ord() {
 706         assert!(parse_use_tree("a").normalize() < parse_use_tree("aa").normalize());
 707         assert!(parse_use_tree("a").normalize() < parse_use_tree("a::a").normalize());
 708         assert!(parse_use_tree("a").normalize() < parse_use_tree("*").normalize());
 709         assert!(parse_use_tree("a").normalize() < parse_use_tree("{a, b}").normalize());
 710         assert!(parse_use_tree("*").normalize() < parse_use_tree("{a, b}").normalize());
 711
 712         assert!(
 713             parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize()
 714                 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize()
 715         );
 716         assert!(
 717             parse_use_tree("serde::de::{Deserialize}").normalize()
 718                 < parse_use_tree("serde_json").normalize()
 719         );
 720         assert!(parse_use_tree("a::b::c").normalize() < parse_use_tree("a::b::*").normalize());
 721         assert!(
 722             parse_use_tree("foo::{Bar, Baz}").normalize()
 723                 < parse_use_tree("{Bar, Baz}").normalize()
 724         );
 725
 726         assert!(
 727             parse_use_tree("foo::{self as bar}").normalize()
 728                 < parse_use_tree("foo::{qux as bar}").normalize()
 729         );
 730         assert!(
 731             parse_use_tree("foo::{qux as bar}").normalize()
 732                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
 733         );
 734         assert!(
 735             parse_use_tree("foo::{self as bar, baz}").normalize()
 736                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
 737         );
 738
 739         assert!(parse_use_tree("foo").normalize() < parse_use_tree("Foo").normalize());
 740         assert!(parse_use_tree("foo").normalize() < parse_use_tree("foo::Bar").normalize());
 741
 742         assert!(
 743             parse_use_tree("std::cmp::{d, c, b, a}").normalize()
 744                 < parse_use_tree("std::cmp::{b, e, g, f}").normalize()
 745         );
 746     }
 747 }