src/reorder.rs

   1 // Copyright 2018 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 //! Reorder items.
  12 //!
  13 //! `mod`, `extern crate` and `use` declarations are reorderd in alphabetical
  14 //! order. Trait items are reordered in pre-determined order (associated types
  15 //! and constatns comes before methods).
  16
  17 // TODO(#2455): Reorder trait items.
  18
  19 use config::{Config, lists::*};
  20 use syntax::ast::UseTreeKind;
  21 use syntax::{ast, attr, codemap::Span};
  22
  23 use attr::filter_inline_attrs;
  24 use codemap::LineRangeUtils;
  25 use comment::combine_strs_with_missing_comments;
  26 use imports::{path_to_imported_ident, rewrite_import};
  27 use items::{is_mod_decl, rewrite_extern_crate, rewrite_mod};
  28 use lists::{itemize_list, write_list, ListFormatting};
  29 use rewrite::{Rewrite, RewriteContext};
  30 use shape::Shape;
  31 use spanned::Spanned;
  32 use utils::mk_sp;
  33 use visitor::FmtVisitor;
  34
  35 use std::cmp::{Ord, Ordering, PartialOrd};
  36
  37 fn compare_use_trees(a: &ast::UseTree, b: &ast::UseTree) -> Ordering {
  38     let aa = UseTree::from_ast(a).normalize();
  39     let bb = UseTree::from_ast(b).normalize();
  40     aa.cmp(&bb)
  41 }
  42
  43 /// Choose the ordering between the given two items.
  44 fn compare_items(a: &ast::Item, b: &ast::Item) -> Ordering {
  45     match (&a.node, &b.node) {
  46         (&ast::ItemKind::Mod(..), &ast::ItemKind::Mod(..)) => {
  47             a.ident.name.as_str().cmp(&b.ident.name.as_str())
  48         }
  49         (&ast::ItemKind::Use(ref a_tree), &ast::ItemKind::Use(ref b_tree)) => {
  50             compare_use_trees(a_tree, b_tree)
  51         }
  52         (&ast::ItemKind::ExternCrate(ref a_name), &ast::ItemKind::ExternCrate(ref b_name)) => {
  53             // `extern crate foo as bar;`
  54             //               ^^^ Comparing this.
  55             let a_orig_name =
  56                 a_name.map_or_else(|| a.ident.name.as_str(), |symbol| symbol.as_str());
  57             let b_orig_name =
  58                 b_name.map_or_else(|| b.ident.name.as_str(), |symbol| symbol.as_str());
  59             let result = a_orig_name.cmp(&b_orig_name);
  60             if result != Ordering::Equal {
  61                 return result;
  62             }
  63
  64             // `extern crate foo as bar;`
  65             //                      ^^^ Comparing this.
  66             match (a_name, b_name) {
  67                 (Some(..), None) => Ordering::Greater,
  68                 (None, Some(..)) => Ordering::Less,
  69                 (None, None) => Ordering::Equal,
  70                 (Some(..), Some(..)) => a.ident.name.as_str().cmp(&b.ident.name.as_str()),
  71             }
  72         }
  73         _ => unreachable!(),
  74     }
  75 }
  76
  77 /// Rewrite a list of items with reordering. Every item in `items` must have
  78 /// the same `ast::ItemKind`.
  79 fn rewrite_reorderable_items(
  80     context: &RewriteContext,
  81     reorderable_items: &[&ast::Item],
  82     shape: Shape,
  83     span: Span,
  84 ) -> Option<String> {
  85     let items = itemize_list(
  86         context.snippet_provider,
  87         reorderable_items.iter(),
  88         "",
  89         ";",
  90         |item| item.span().lo(),
  91         |item| item.span().hi(),
  92         |item| {
  93             let attrs = filter_inline_attrs(&item.attrs, item.span());
  94             let attrs_str = attrs.rewrite(context, shape)?;
  95
  96             let missed_span = if attrs.is_empty() {
  97                 mk_sp(item.span.lo(), item.span.lo())
  98             } else {
  99                 mk_sp(attrs.last().unwrap().span.hi(), item.span.lo())
 100             };
 101
 102             let item_str = match item.node {
 103                 ast::ItemKind::Use(ref tree) => {
 104                     rewrite_import(context, &item.vis, tree, &item.attrs, shape)?
 105                 }
 106                 ast::ItemKind::ExternCrate(..) => rewrite_extern_crate(context, item)?,
 107                 ast::ItemKind::Mod(..) => rewrite_mod(item),
 108                 _ => return None,
 109             };
 110
 111             combine_strs_with_missing_comments(
 112                 context,
 113                 &attrs_str,
 114                 &item_str,
 115                 missed_span,
 116                 shape,
 117                 false,
 118             )
 119         },
 120         span.lo(),
 121         span.hi(),
 122         false,
 123     );
 124
 125     let mut item_pair_vec: Vec<_> = items.zip(reorderable_items.iter()).collect();
 126     item_pair_vec.sort_by(|a, b| compare_items(a.1, b.1));
 127     let item_vec: Vec<_> = item_pair_vec.into_iter().map(|pair| pair.0).collect();
 128
 129     let fmt = ListFormatting {
 130         tactic: DefinitiveListTactic::Vertical,
 131         separator: "",
 132         trailing_separator: SeparatorTactic::Never,
 133         separator_place: SeparatorPlace::Back,
 134         shape,
 135         ends_with_newline: true,
 136         preserve_newline: false,
 137         config: context.config,
 138     };
 139
 140     write_list(&item_vec, &fmt)
 141 }
 142
 143 fn contains_macro_use_attr(item: &ast::Item) -> bool {
 144     attr::contains_name(&filter_inline_attrs(&item.attrs, item.span()), "macro_use")
 145 }
 146
 147 /// A simplified version of `ast::ItemKind`.
 148 #[derive(Debug, PartialEq, Eq, Copy, Clone)]
 149 enum ReorderableItemKind {
 150     ExternCrate,
 151     Mod,
 152     Use,
 153     /// An item that cannot be reordered. Either has an unreorderable item kind
 154     /// or an `macro_use` attribute.
 155     Other,
 156 }
 157
 158 impl ReorderableItemKind {
 159     pub fn from(item: &ast::Item) -> Self {
 160         match item.node {
 161             _ if contains_macro_use_attr(item) => ReorderableItemKind::Other,
 162             ast::ItemKind::ExternCrate(..) => ReorderableItemKind::ExternCrate,
 163             ast::ItemKind::Mod(..) if is_mod_decl(item) => ReorderableItemKind::Mod,
 164             ast::ItemKind::Use(..) => ReorderableItemKind::Use,
 165             _ => ReorderableItemKind::Other,
 166         }
 167     }
 168
 169     pub fn is_same_item_kind(&self, item: &ast::Item) -> bool {
 170         ReorderableItemKind::from(item) == *self
 171     }
 172
 173     pub fn is_reorderable(&self, config: &Config) -> bool {
 174         match *self {
 175             ReorderableItemKind::ExternCrate => config.reorder_extern_crates(),
 176             ReorderableItemKind::Mod => config.reorder_modules(),
 177             ReorderableItemKind::Use => config.reorder_imports(),
 178             ReorderableItemKind::Other => false,
 179         }
 180     }
 181
 182     pub fn in_group(&self, config: &Config) -> bool {
 183         match *self {
 184             ReorderableItemKind::ExternCrate => config.reorder_extern_crates_in_group(),
 185             ReorderableItemKind::Mod => config.reorder_modules(),
 186             ReorderableItemKind::Use => config.reorder_imports_in_group(),
 187             ReorderableItemKind::Other => false,
 188         }
 189     }
 190 }
 191
 192 impl<'b, 'a: 'b> FmtVisitor<'a> {
 193     /// Format items with the same item kind and reorder them. If `in_group` is
 194     /// `true`, then the items separated by an empty line will not be reordered
 195     /// together.
 196     fn walk_reorderable_items(
 197         &mut self,
 198         items: &[&ast::Item],
 199         item_kind: ReorderableItemKind,
 200         in_group: bool,
 201     ) -> usize {
 202         let mut last = self.codemap.lookup_line_range(items[0].span());
 203         let item_length = items
 204             .iter()
 205             .take_while(|ppi| {
 206                 item_kind.is_same_item_kind(&***ppi) && (!in_group || {
 207                     let current = self.codemap.lookup_line_range(ppi.span());
 208                     let in_same_group = current.lo < last.hi + 2;
 209                     last = current;
 210                     in_same_group
 211                 })
 212             })
 213             .count();
 214         let items = &items[..item_length];
 215
 216         let at_least_one_in_file_lines = items
 217             .iter()
 218             .any(|item| !out_of_file_lines_range!(self, item.span));
 219
 220         if at_least_one_in_file_lines && !items.is_empty() {
 221             let lo = items.first().unwrap().span().lo();
 222             let hi = items.last().unwrap().span().hi();
 223             let span = mk_sp(lo, hi);
 224             let rw = rewrite_reorderable_items(&self.get_context(), items, self.shape(), span);
 225             self.push_rewrite(span, rw);
 226         } else {
 227             for item in items {
 228                 self.push_rewrite(item.span, None);
 229             }
 230         }
 231
 232         item_length
 233     }
 234
 235     /// Visit and format the given items. Items are reordered If they are
 236     /// consecutive and reorderable.
 237     pub fn visit_items_with_reordering(&mut self, mut items: &[&ast::Item]) {
 238         while !items.is_empty() {
 239             // If the next item is a `use`, `extern crate` or `mod`, then extract it and any
 240             // subsequent items that have the same item kind to be reordered within
 241             // `walk_reorderable_items`. Otherwise, just format the next item for output.
 242             let item_kind = ReorderableItemKind::from(items[0]);
 243             if item_kind.is_reorderable(self.config) {
 244                 let visited_items_num =
 245                     self.walk_reorderable_items(items, item_kind, item_kind.in_group(self.config));
 246                 let (_, rest) = items.split_at(visited_items_num);
 247                 items = rest;
 248             } else {
 249                 // Reaching here means items were not reordered. There must be at least
 250                 // one item left in `items`, so calling `unwrap()` here is safe.
 251                 let (item, rest) = items.split_first().unwrap();
 252                 self.visit_item(item);
 253                 items = rest;
 254             }
 255         }
 256     }
 257 }
 258
 259 // Ordering of imports
 260
 261 // We order imports by translating to our own representation and then sorting.
 262 // The Rust AST data structures are really bad for this. Rustfmt applies a bunch
 263 // of normalisations to imports and since we want to sort based on the result
 264 // of these (and to maintain idempotence) we must apply the same normalisations
 265 // to the data structures for sorting.
 266 //
 267 // We sort `self` and `super` before other imports, then identifier imports,
 268 // then glob imports, then lists of imports. We do not take aliases into account
 269 // when ordering unless the imports are identical except for the alias (rare in
 270 // practice).
 271
 272 // FIXME(#2531) - we should unify the comparison code here with the formatting
 273 // code elsewhere since we are essentially string-ifying twice. Furthermore, by
 274 // parsing to our own format on comparison, we repeat a lot of work when
 275 // sorting.
 276
 277 // FIXME we do a lot of allocation to make our own representation.
 278 #[derive(Debug, Clone, Eq, PartialEq)]
 279 enum UseSegment {
 280     Ident(String, Option<String>),
 281     Slf(Option<String>),
 282     Super(Option<String>),
 283     Glob,
 284     List(Vec<UseTree>),
 285 }
 286
 287 #[derive(Debug, Clone, Eq, PartialEq)]
 288 struct UseTree {
 289     path: Vec<UseSegment>,
 290 }
 291
 292 impl UseSegment {
 293     // Clone a version of self with any top-level alias removed.
 294     fn remove_alias(&self) -> UseSegment {
 295         match *self {
 296             UseSegment::Ident(ref s, _) => UseSegment::Ident(s.clone(), None),
 297             UseSegment::Slf(_) => UseSegment::Slf(None),
 298             UseSegment::Super(_) => UseSegment::Super(None),
 299             _ => self.clone(),
 300         }
 301     }
 302 }
 303
 304 impl UseTree {
 305     fn from_ast(a: &ast::UseTree) -> UseTree {
 306         let mut result = UseTree { path: vec![] };
 307         for p in &a.prefix.segments {
 308             result.path.push(UseSegment::Ident(
 309                 (*p.identifier.name.as_str()).to_owned(),
 310                 None,
 311             ));
 312         }
 313         match a.kind {
 314             UseTreeKind::Glob => {
 315                 result.path.push(UseSegment::Glob);
 316             }
 317             UseTreeKind::Nested(ref list) => {
 318                 result.path.push(UseSegment::List(
 319                     list.iter().map(|t| Self::from_ast(&t.0)).collect(),
 320                 ));
 321             }
 322             UseTreeKind::Simple(ref rename) => {
 323                 let mut name = (*path_to_imported_ident(&a.prefix).name.as_str()).to_owned();
 324                 let alias = rename.and_then(|ident| {
 325                     if ident == path_to_imported_ident(&a.prefix) {
 326                         None
 327                     } else {
 328                         Some(ident.to_string())
 329                     }
 330                 });
 331
 332                 let segment = if &name == "self" {
 333                     UseSegment::Slf(alias)
 334                 } else if &name == "super" {
 335                     UseSegment::Super(alias)
 336                 } else {
 337                     UseSegment::Ident(name, alias)
 338                 };
 339
 340                 // `name` is already in result.
 341                 result.path.pop();
 342                 result.path.push(segment);
 343             }
 344         }
 345         result
 346     }
 347
 348     // Do the adjustments that rustfmt does elsewhere to use paths.
 349     fn normalize(mut self) -> UseTree {
 350         let mut last = self.path.pop().expect("Empty use tree?");
 351         // Hack around borrow checker.
 352         let mut normalize_sole_list = false;
 353         let mut aliased_self = false;
 354
 355         // Normalise foo::self -> foo.
 356         if let UseSegment::Slf(None) = last {
 357             return self;
 358         }
 359
 360         // Normalise foo::self as bar -> foo as bar.
 361         if let UseSegment::Slf(_) = last {
 362             match self.path.last() {
 363                 None => {}
 364                 Some(UseSegment::Ident(_, None)) => {
 365                     aliased_self = true;
 366                 }
 367                 _ => unreachable!(),
 368             }
 369         }
 370
 371         if aliased_self {
 372             match self.path.last() {
 373                 Some(UseSegment::Ident(_, ref mut old_rename)) => {
 374                     assert!(old_rename.is_none());
 375                     if let UseSegment::Slf(Some(rename)) = last {
 376                         *old_rename = Some(rename);
 377                         return self;
 378                     }
 379                 }
 380                 _ => unreachable!(),
 381             }
 382         }
 383
 384         // Normalise foo::{bar} -> foo::bar
 385         if let UseSegment::List(ref list) = last {
 386             if list.len() == 1 && list[0].path.len() == 1 {
 387                 normalize_sole_list = true;
 388             }
 389         }
 390
 391         if normalize_sole_list {
 392             match last {
 393                 UseSegment::List(list) => {
 394                     self.path.push(list[0].path[0].clone());
 395                     return self.normalize();
 396                 }
 397                 _ => unreachable!(),
 398             }
 399         }
 400
 401         // Recursively normalize elements of a list use (including sorting the list).
 402         if let UseSegment::List(list) = last {
 403             let mut list: Vec<_> = list.into_iter().map(|ut| ut.normalize()).collect();
 404             list.sort();
 405             last = UseSegment::List(list);
 406         }
 407
 408         self.path.push(last);
 409         self
 410     }
 411 }
 412
 413 impl PartialOrd for UseSegment {
 414     fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
 415         Some(self.cmp(other))
 416     }
 417 }
 418 impl PartialOrd for UseTree {
 419     fn partial_cmp(&self, other: &UseTree) -> Option<Ordering> {
 420         Some(self.cmp(other))
 421     }
 422 }
 423 impl Ord for UseSegment {
 424     fn cmp(&self, other: &UseSegment) -> Ordering {
 425         use self::UseSegment::*;
 426
 427         match (self, other) {
 428             (&Slf(ref a), &Slf(ref b)) | (&Super(ref a), &Super(ref b)) => a.cmp(b),
 429             (&Glob, &Glob) => Ordering::Equal,
 430             (&Ident(ref ia, ref aa), &Ident(ref ib, ref ab)) => {
 431                 let ident_ord = ia.cmp(ib);
 432                 if ident_ord != Ordering::Equal {
 433                     return ident_ord;
 434                 }
 435                 if aa.is_none() && ab.is_some() {
 436                     return Ordering::Less;
 437                 }
 438                 if aa.is_some() && ab.is_none() {
 439                     return Ordering::Greater;
 440                 }
 441                 aa.cmp(ab)
 442             }
 443             (&List(ref a), &List(ref b)) => {
 444                 for (a, b) in a.iter().zip(b.iter()) {
 445                     let ord = a.cmp(b);
 446                     if ord != Ordering::Equal {
 447                         return ord;
 448                     }
 449                 }
 450
 451                 a.len().cmp(&b.len())
 452             }
 453             (&Slf(_), _) => Ordering::Less,
 454             (_, &Slf(_)) => Ordering::Greater,
 455             (&Super(_), _) => Ordering::Less,
 456             (_, &Super(_)) => Ordering::Greater,
 457             (&Ident(..), _) => Ordering::Less,
 458             (_, &Ident(..)) => Ordering::Greater,
 459             (&Glob, _) => Ordering::Less,
 460             (_, &Glob) => Ordering::Greater,
 461         }
 462     }
 463 }
 464 impl Ord for UseTree {
 465     fn cmp(&self, other: &UseTree) -> Ordering {
 466         for (a, b) in self.path.iter().zip(other.path.iter()) {
 467             let ord = a.cmp(b);
 468             // The comparison without aliases is a hack to avoid situations like
 469             // comparing `a::b` to `a as c` - where the latter should be ordered
 470             // first since it is shorter.
 471             if ord != Ordering::Equal && a.remove_alias().cmp(&b.remove_alias()) != Ordering::Equal
 472             {
 473                 return ord;
 474             }
 475         }
 476
 477         self.path.len().cmp(&other.path.len())
 478     }
 479 }
 480
 481 #[cfg(test)]
 482 mod test {
 483     use super::*;
 484
 485     // Parse the path part of an import. This parser is not robust and is only
 486     // suitable for use in a test harness.
 487     fn parse_use_tree(s: &str) -> UseTree {
 488         use std::iter::Peekable;
 489         use std::mem::swap;
 490         use std::str::Chars;
 491
 492         struct Parser<'a> {
 493             input: Peekable<Chars<'a>>,
 494         }
 495
 496         impl<'a> Parser<'a> {
 497             fn bump(&mut self) {
 498                 self.input.next().unwrap();
 499             }
 500             fn eat(&mut self, c: char) {
 501                 assert!(self.input.next().unwrap() == c);
 502             }
 503             fn push_segment(
 504                 result: &mut Vec<UseSegment>,
 505                 buf: &mut String,
 506                 alias_buf: &mut Option<String>,
 507             ) {
 508                 if !buf.is_empty() {
 509                     let mut alias = None;
 510                     swap(alias_buf, &mut alias);
 511                     if buf == "self" {
 512                         result.push(UseSegment::Slf(alias));
 513                         *buf = String::new();
 514                         *alias_buf = None;
 515                     } else if buf == "super" {
 516                         result.push(UseSegment::Super(alias));
 517                         *buf = String::new();
 518                         *alias_buf = None;
 519                     } else {
 520                         let mut name = String::new();
 521                         swap(buf, &mut name);
 522                         result.push(UseSegment::Ident(name, alias));
 523                     }
 524                 }
 525             }
 526             fn parse_in_list(&mut self) -> UseTree {
 527                 let mut result = vec![];
 528                 let mut buf = String::new();
 529                 let mut alias_buf = None;
 530                 while let Some(&c) = self.input.peek() {
 531                     match c {
 532                         '{' => {
 533                             assert!(buf.is_empty());
 534                             self.bump();
 535                             result.push(UseSegment::List(self.parse_list()));
 536                             self.eat('}');
 537                         }
 538                         '*' => {
 539                             assert!(buf.is_empty());
 540                             self.bump();
 541                             result.push(UseSegment::Glob);
 542                         }
 543                         ':' => {
 544                             self.bump();
 545                             self.eat(':');
 546                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 547                         }
 548                         '}' | ',' => {
 549                             Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 550                             return UseTree { path: result };
 551                         }
 552                         ' ' => {
 553                             self.bump();
 554                             self.eat('a');
 555                             self.eat('s');
 556                             self.eat(' ');
 557                             alias_buf = Some(String::new());
 558                         }
 559                         c => {
 560                             self.bump();
 561                             if let Some(ref mut buf) = alias_buf {
 562                                 buf.push(c);
 563                             } else {
 564                                 buf.push(c);
 565                             }
 566                         }
 567                     }
 568                 }
 569                 Self::push_segment(&mut result, &mut buf, &mut alias_buf);
 570                 UseTree { path: result }
 571             }
 572
 573             fn parse_list(&mut self) -> Vec<UseTree> {
 574                 let mut result = vec![];
 575                 loop {
 576                     match self.input.peek().unwrap() {
 577                         ',' | ' ' => self.bump(),
 578                         '}' => {
 579                             return result;
 580                         }
 581                         _ => result.push(self.parse_in_list()),
 582                     }
 583                 }
 584             }
 585         }
 586
 587         let mut parser = Parser {
 588             input: s.chars().peekable(),
 589         };
 590         parser.parse_in_list()
 591     }
 592
 593     #[test]
 594     fn test_use_tree_normalize() {
 595         assert_eq!(parse_use_tree("a::self").normalize(), parse_use_tree("a"));
 596         assert_eq!(
 597             parse_use_tree("a::self as foo").normalize(),
 598             parse_use_tree("a as foo")
 599         );
 600         assert_eq!(parse_use_tree("a::{self}").normalize(), parse_use_tree("a"));
 601         assert_eq!(parse_use_tree("a::{b}").normalize(), parse_use_tree("a::b"));
 602         assert_eq!(
 603             parse_use_tree("a::{b, c::self}").normalize(),
 604             parse_use_tree("a::{b, c}")
 605         );
 606         assert_eq!(
 607             parse_use_tree("a::{b as bar, c::self}").normalize(),
 608             parse_use_tree("a::{b as bar, c}")
 609         );
 610     }
 611
 612     #[test]
 613     fn test_use_tree_ord() {
 614         assert!(parse_use_tree("a").normalize() < parse_use_tree("aa").normalize());
 615         assert!(parse_use_tree("a").normalize() < parse_use_tree("a::a").normalize());
 616         assert!(parse_use_tree("a").normalize() < parse_use_tree("*").normalize());
 617         assert!(parse_use_tree("a").normalize() < parse_use_tree("{a, b}").normalize());
 618         assert!(parse_use_tree("*").normalize() < parse_use_tree("{a, b}").normalize());
 619
 620         assert!(
 621             parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize()
 622                 < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize()
 623         );
 624         assert!(
 625             parse_use_tree("serde::de::{Deserialize}").normalize()
 626                 < parse_use_tree("serde_json").normalize()
 627         );
 628         assert!(parse_use_tree("a::b::c").normalize() < parse_use_tree("a::b::*").normalize());
 629         assert!(
 630             parse_use_tree("foo::{Bar, Baz}").normalize()
 631                 < parse_use_tree("{Bar, Baz}").normalize()
 632         );
 633
 634         assert!(
 635             parse_use_tree("foo::{self as bar}").normalize()
 636                 < parse_use_tree("foo::{qux as bar}").normalize()
 637         );
 638         assert!(
 639             parse_use_tree("foo::{qux as bar}").normalize()
 640                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
 641         );
 642         assert!(
 643             parse_use_tree("foo::{self as bar, baz}").normalize()
 644                 < parse_use_tree("foo::{baz, qux as bar}").normalize()
 645         );
 646
 647         assert!(parse_use_tree("Foo").normalize() < parse_use_tree("foo").normalize());
 648         assert!(parse_use_tree("foo").normalize() < parse_use_tree("foo::Bar").normalize());
 649
 650         assert!(
 651             parse_use_tree("std::cmp::{d, c, b, a}").normalize()
 652                 < parse_use_tree("std::cmp::{b, e, g, f}").normalize()
 653         );
 654     }
 655 }