+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub(crate) enum SharedPrefix {
+ Crate,
+ Module,
+}
+
+#[cfg(test)]
+mod test {
+ use super::*;
+ use rustc_span::DUMMY_SP;
+
+ // Parse the path part of an import. This parser is not robust and is only
+ // suitable for use in a test harness.
+ fn parse_use_tree(s: &str) -> UseTree {
+ use std::iter::Peekable;
+ use std::mem::swap;
+ use std::str::Chars;
+
+ struct Parser<'a> {
+ input: Peekable<Chars<'a>>,
+ }
+
+ impl<'a> Parser<'a> {
+ fn bump(&mut self) {
+ self.input.next().unwrap();
+ }
+
+ fn eat(&mut self, c: char) {
+ assert!(self.input.next().unwrap() == c);
+ }
+
+ fn push_segment(
+ result: &mut Vec<UseSegment>,
+ buf: &mut String,
+ alias_buf: &mut Option<String>,
+ ) {
+ if !buf.is_empty() {
+ let mut alias = None;
+ swap(alias_buf, &mut alias);
+
+ match buf.as_ref() {
+ "self" => {
+ result.push(UseSegment::Slf(alias));
+ *buf = String::new();
+ *alias_buf = None;
+ }
+ "super" => {
+ result.push(UseSegment::Super(alias));
+ *buf = String::new();
+ *alias_buf = None;
+ }
+ "crate" => {
+ result.push(UseSegment::Crate(alias));
+ *buf = String::new();
+ *alias_buf = None;
+ }
+ _ => {
+ let mut name = String::new();
+ swap(buf, &mut name);
+ result.push(UseSegment::Ident(name, alias));
+ }
+ }
+ }
+ }
+
+ fn parse_in_list(&mut self) -> UseTree {
+ let mut result = vec![];
+ let mut buf = String::new();
+ let mut alias_buf = None;
+ while let Some(&c) = self.input.peek() {
+ match c {
+ '{' => {
+ assert!(buf.is_empty());
+ self.bump();
+ result.push(UseSegment::List(self.parse_list()));
+ self.eat('}');
+ }
+ '*' => {
+ assert!(buf.is_empty());
+ self.bump();
+ result.push(UseSegment::Glob);
+ }
+ ':' => {
+ self.bump();
+ self.eat(':');
+ Self::push_segment(&mut result, &mut buf, &mut alias_buf);
+ }
+ '}' | ',' => {
+ Self::push_segment(&mut result, &mut buf, &mut alias_buf);
+ return UseTree {
+ path: result,
+ span: DUMMY_SP,
+ list_item: None,
+ visibility: None,
+ attrs: None,
+ };
+ }
+ ' ' => {
+ self.bump();
+ self.eat('a');
+ self.eat('s');
+ self.eat(' ');
+ alias_buf = Some(String::new());
+ }
+ c => {
+ self.bump();
+ if let Some(ref mut buf) = alias_buf {
+ buf.push(c);
+ } else {
+ buf.push(c);
+ }
+ }
+ }
+ }
+ Self::push_segment(&mut result, &mut buf, &mut alias_buf);
+ UseTree {
+ path: result,
+ span: DUMMY_SP,
+ list_item: None,
+ visibility: None,
+ attrs: None,
+ }
+ }
+
+ fn parse_list(&mut self) -> Vec<UseTree> {
+ let mut result = vec![];
+ loop {
+ match self.input.peek().unwrap() {
+ ',' | ' ' => self.bump(),
+ '}' => {
+ return result;
+ }
+ _ => result.push(self.parse_in_list()),
+ }
+ }
+ }
+ }
+
+ let mut parser = Parser {
+ input: s.chars().peekable(),
+ };
+ parser.parse_in_list()
+ }
+
+ macro_rules! parse_use_trees {
+ ($($s:expr),* $(,)*) => {
+ vec![
+ $(parse_use_tree($s),)*
+ ]
+ }
+ }
+
+ macro_rules! test_merge {
+ ($by:ident, [$($input:expr),* $(,)*], [$($output:expr),* $(,)*]) => {
+ assert_eq!(
+ merge_use_trees(parse_use_trees!($($input,)*), SharedPrefix::$by),
+ parse_use_trees!($($output,)*),
+ );
+ }
+ }
+
+ #[test]
+ fn test_use_tree_merge_crate() {
+ test_merge!(
+ Crate,
+ ["a::b::{c, d}", "a::b::{e, f}"],
+ ["a::b::{c, d, e, f}"]
+ );
+ test_merge!(Crate, ["a::b::c", "a::b"], ["a::{b, b::c}"]);
+ test_merge!(Crate, ["a::b", "a::b"], ["a::b"]);
+ test_merge!(Crate, ["a", "a::b", "a::b::c"], ["a::{self, b, b::c}"]);
+ test_merge!(
+ Crate,
+ ["a", "a::b", "a::b::c", "a::b::c::d"],
+ ["a::{self, b, b::{c, c::d}}"]
+ );
+ test_merge!(
+ Crate,
+ ["a", "a::b", "a::b::c", "a::b"],
+ ["a::{self, b, b::c}"]
+ );
+ test_merge!(
+ Crate,
+ ["a::{b::{self, c}, d::e}", "a::d::f"],
+ ["a::{b::{self, c}, d::{e, f}}"]
+ );
+ test_merge!(
+ Crate,
+ ["a::d::f", "a::{b::{self, c}, d::e}"],
+ ["a::{b::{self, c}, d::{e, f}}"]
+ );
+ test_merge!(
+ Crate,
+ ["a::{c, d, b}", "a::{d, e, b, a, f}", "a::{f, g, c}"],
+ ["a::{a, b, c, d, e, f, g}"]
+ );
+ test_merge!(
+ Crate,
+ ["a::{self}", "b::{self as foo}"],
+ ["a::{self}", "b::{self as foo}"]
+ );
+ }
+
+ #[test]
+ fn test_use_tree_merge_module() {
+ test_merge!(
+ Module,
+ ["foo::b", "foo::{a, c, d::e}"],
+ ["foo::{a, b, c}", "foo::d::e"]
+ );
+
+ test_merge!(
+ Module,
+ ["foo::{a::b, a::c, d::e, d::f}"],
+ ["foo::a::{b, c}", "foo::d::{e, f}"]
+ );
+ }
+
+ #[test]
+ fn test_flatten_use_trees() {
+ assert_eq!(
+ flatten_use_trees(parse_use_trees!["foo::{a::{b, c}, d::e}"]),
+ parse_use_trees!["foo::a::b", "foo::a::c", "foo::d::e"]
+ );
+
+ assert_eq!(
+ flatten_use_trees(parse_use_trees!["foo::{self, a, b::{c, d}, e::*}"]),
+ parse_use_trees![
+ "foo::{self}",
+ "foo::a",
+ "foo::b::c",
+ "foo::b::d",
+ "foo::e::*"
+ ]
+ );
+ }
+
+ #[test]
+ fn test_use_tree_flatten() {
+ assert_eq!(
+ parse_use_tree("a::b::{c, d, e, f}").flatten(),
+ parse_use_trees!("a::b::c", "a::b::d", "a::b::e", "a::b::f",)
+ );
+
+ assert_eq!(
+ parse_use_tree("a::b::{c::{d, e, f}, g, h::{i, j, k}}").flatten(),
+ parse_use_trees![
+ "a::b::c::d",
+ "a::b::c::e",
+ "a::b::c::f",
+ "a::b::g",
+ "a::b::h::i",
+ "a::b::h::j",
+ "a::b::h::k",
+ ]
+ );
+ }
+
+ #[test]
+ fn test_use_tree_normalize() {
+ assert_eq!(parse_use_tree("a::self").normalize(), parse_use_tree("a"));
+ assert_eq!(
+ parse_use_tree("a::self as foo").normalize(),
+ parse_use_tree("a as foo")
+ );
+ assert_eq!(
+ parse_use_tree("a::{self}").normalize(),
+ parse_use_tree("a::{self}")
+ );
+ assert_eq!(parse_use_tree("a::{b}").normalize(), parse_use_tree("a::b"));
+ assert_eq!(
+ parse_use_tree("a::{b, c::self}").normalize(),
+ parse_use_tree("a::{b, c}")
+ );
+ assert_eq!(
+ parse_use_tree("a::{b as bar, c::self}").normalize(),
+ parse_use_tree("a::{b as bar, c}")
+ );
+ }
+
+ #[test]
+ fn test_use_tree_ord() {
+ assert!(parse_use_tree("a").normalize() < parse_use_tree("aa").normalize());
+ assert!(parse_use_tree("a").normalize() < parse_use_tree("a::a").normalize());
+ assert!(parse_use_tree("a").normalize() < parse_use_tree("*").normalize());
+ assert!(parse_use_tree("a").normalize() < parse_use_tree("{a, b}").normalize());
+ assert!(parse_use_tree("*").normalize() < parse_use_tree("{a, b}").normalize());
+
+ assert!(
+ parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, dddddddd}").normalize()
+ < parse_use_tree("aaaaaaaaaaaaaaa::{bb, cc, ddddddddd}").normalize()
+ );
+ assert!(
+ parse_use_tree("serde::de::{Deserialize}").normalize()
+ < parse_use_tree("serde_json").normalize()
+ );
+ assert!(parse_use_tree("a::b::c").normalize() < parse_use_tree("a::b::*").normalize());
+ assert!(
+ parse_use_tree("foo::{Bar, Baz}").normalize()
+ < parse_use_tree("{Bar, Baz}").normalize()
+ );
+
+ assert!(
+ parse_use_tree("foo::{qux as bar}").normalize()
+ < parse_use_tree("foo::{self as bar}").normalize()
+ );
+ assert!(
+ parse_use_tree("foo::{qux as bar}").normalize()
+ < parse_use_tree("foo::{baz, qux as bar}").normalize()
+ );
+ assert!(
+ parse_use_tree("foo::{self as bar, baz}").normalize()
+ < parse_use_tree("foo::{baz, qux as bar}").normalize()
+ );
+
+ assert!(parse_use_tree("foo").normalize() < parse_use_tree("Foo").normalize());
+ assert!(parse_use_tree("foo").normalize() < parse_use_tree("foo::Bar").normalize());
+
+ assert!(
+ parse_use_tree("std::cmp::{d, c, b, a}").normalize()
+ < parse_use_tree("std::cmp::{b, e, g, f}").normalize()
+ );
+ }