Dedup `imports_granularity = "Item"` (#4737)

* Fix for issue 4725 - dedup Item imports_granularity (2nd version)

* Use unique() instead of unique_by()

27 files changed, 62 insertions, 1 deletions

diff --git a/src/imports.rs b/src/imports.rs
index 962f2126c66..559ed3917db 100644
--- a/src/imports.rs
+++ b/src/imports.rs
@@ -2,6 +2,10 @@ use std::borrow::Cow;
 use std::cmp::Ordering;
 use std::fmt;
 
+use core::hash::{Hash, Hasher};
+
+use itertools::Itertools;
+
 use rustc_ast::ast::{self, UseTreeKind};
 use rustc_span::{
     symbol::{self, sym},
@@ -87,7 +91,7 @@ impl<'a> FmtVisitor<'a> {
 // sorting.
 
 // FIXME we do a lot of allocation to make our own representation.
-#[derive(Clone, Eq, PartialEq)]
+#[derive(Clone, Eq, Hash, PartialEq)]
 pub(crate) enum UseSegment {
     Ident(String, Option<String>),
     Slf(Option<String>),
@@ -232,10 +236,13 @@ fn flatten_use_trees(
     use_trees: Vec<UseTree>,
     import_granularity: ImportGranularity,
 ) -> Vec<UseTree> {
+    // Return non-sorted single occurance of the use-trees text string;
+    // order is by first occurance of the use-tree.
     use_trees
         .into_iter()
         .flat_map(|tree| tree.flatten(import_granularity))
         .map(UseTree::nest_trailing_self)
+        .unique()
         .collect()
 }
 
@@ -780,6 +787,12 @@ fn merge_use_trees_inner(trees: &mut Vec<UseTree>, use_tree: UseTree, merge_by:
     trees.sort();
 }
 
+impl Hash for UseTree {
+    fn hash<H: Hasher>(&self, state: &mut H) {
+        self.path.hash(state);
+    }
+}
+
 impl PartialOrd for UseSegment {
     fn partial_cmp(&self, other: &UseSegment) -> Option<Ordering> {
         Some(self.cmp(other))
diff --git a/tests/source/imports-impl-only-use.rs b/tests/source/imports/imports-impl-only-use.rs
index d290d8d9185..d290d8d9185 100644
--- a/tests/source/imports-impl-only-use.rs
+++ b/tests/source/imports/imports-impl-only-use.rs
diff --git a/tests/source/imports-reorder-lines-and-items.rs b/tests/source/imports/imports-reorder-lines-and-items.rs
index b6380f31c61..b6380f31c61 100644
--- a/tests/source/imports-reorder-lines-and-items.rs
+++ b/tests/source/imports/imports-reorder-lines-and-items.rs
diff --git a/tests/source/imports-reorder-lines.rs b/tests/source/imports/imports-reorder-lines.rs
index 2b018544eae..2b018544eae 100644
--- a/tests/source/imports-reorder-lines.rs
+++ b/tests/source/imports/imports-reorder-lines.rs
diff --git a/tests/source/imports-reorder.rs b/tests/source/imports/imports-reorder.rs
index cbe9d6ca78a..cbe9d6ca78a 100644
--- a/tests/source/imports-reorder.rs
+++ b/tests/source/imports/imports-reorder.rs
diff --git a/tests/source/imports.rs b/tests/source/imports/imports.rs
index 4dfc6ed94e3..4dfc6ed94e3 100644
--- a/tests/source/imports.rs
+++ b/tests/source/imports/imports.rs
diff --git a/tests/source/imports_block_indent.rs b/tests/source/imports/imports_block_indent.rs
index 016deefe58c..016deefe58c 100644
--- a/tests/source/imports_block_indent.rs
+++ b/tests/source/imports/imports_block_indent.rs
diff --git a/tests/source/imports_granularity_crate.rs b/tests/source/imports/imports_granularity_crate.rs
index f6f7761e82e..f6f7761e82e 100644
--- a/tests/source/imports_granularity_crate.rs
+++ b/tests/source/imports/imports_granularity_crate.rs
diff --git a/tests/source/imports/imports_granularity_default-with-dups.rs b/tests/source/imports/imports_granularity_default-with-dups.rs
new file mode 100644
index 00000000000..cbb21a9f1b3
--- /dev/null
+++ b/tests/source/imports/imports_granularity_default-with-dups.rs
@@ -0,0 +1,6 @@
+use crate::lexer;
+use crate::lexer::tokens::TokenData;
+use crate::lexer::{tokens::TokenData};
+use crate::lexer::self;
+use crate::lexer::{self};
+use crate::lexer::{self, tokens::TokenData};
diff --git a/tests/source/imports/imports_granularity_item-with-dups-StdExternalCrate-no-reorder.rs b/tests/source/imports/imports_granularity_item-with-dups-StdExternalCrate-no-reorder.rs
new file mode 100644
index 00000000000..e23705a884f
--- /dev/null
+++ b/tests/source/imports/imports_granularity_item-with-dups-StdExternalCrate-no-reorder.rs
@@ -0,0 +1,13 @@
+// rustfmt-imports_granularity: Item
+// rustfmt-reorder_imports: false
+// rustfmt-group_imports: StdExternalCrate
+
+use crate::lexer;
+use crate::lexer;
+use crate::lexer::tokens::TokenData;
+use crate::lexer::{tokens::TokenData};
+use crate::lexer::self;
+use crate::lexer;
+use crate::lexer;
+use crate::lexer::{self};
+use crate::lexer::{self, tokens::TokenData};
diff --git a/tests/source/imports/imports_granularity_item-with-dups.rs b/tests/source/imports/imports_granularity_item-with-dups.rs
new file mode 100644
index 00000000000..3e9589c299f
--- /dev/null
+++ b/tests/source/imports/imports_granularity_item-with-dups.rs
@@ -0,0 +1,11 @@
+// rustfmt-imports_granularity: Item
+
+use crate::lexer;
+use crate::lexer;
+use crate::lexer::tokens::TokenData;
+use crate::lexer::{tokens::TokenData};
+use crate::lexer::self;
+use crate::lexer;
+use crate::lexer;
+use crate::lexer::{self};
+use crate::lexer::{self, tokens::TokenData};
diff --git a/tests/source/imports_granularity_item.rs b/tests/source/imports/imports_granularity_item.rs
index b82c0d33caf..b82c0d33caf 100644
--- a/tests/source/imports_granularity_item.rs
+++ b/tests/source/imports/imports_granularity_item.rs
diff --git a/tests/source/imports_granularity_module.rs b/tests/source/imports/imports_granularity_module.rs
index c7f68cea6d4..c7f68cea6d4 100644
--- a/tests/source/imports_granularity_module.rs
+++ b/tests/source/imports/imports_granularity_module.rs
diff --git a/tests/target/import-fencepost-length.rs b/tests/target/imports/import-fencepost-length.rs
index fd09d50d72d..fd09d50d72d 100644
--- a/tests/target/import-fencepost-length.rs
+++ b/tests/target/imports/import-fencepost-length.rs
diff --git a/tests/target/imports-impl-only-use.rs b/tests/target/imports/imports-impl-only-use.rs
index d290d8d9185..d290d8d9185 100644
--- a/tests/target/imports-impl-only-use.rs
+++ b/tests/target/imports/imports-impl-only-use.rs
diff --git a/tests/target/imports-reorder-lines-and-items.rs b/tests/target/imports/imports-reorder-lines-and-items.rs
index 98a5afe4348..98a5afe4348 100644
--- a/tests/target/imports-reorder-lines-and-items.rs
+++ b/tests/target/imports/imports-reorder-lines-and-items.rs
diff --git a/tests/target/imports-reorder-lines.rs b/tests/target/imports/imports-reorder-lines.rs
index 5b85503b55d..5b85503b55d 100644
--- a/tests/target/imports-reorder-lines.rs
+++ b/tests/target/imports/imports-reorder-lines.rs
diff --git a/tests/target/imports-reorder.rs b/tests/target/imports/imports-reorder.rs
index 84e97c0224f..84e97c0224f 100644
--- a/tests/target/imports-reorder.rs
+++ b/tests/target/imports/imports-reorder.rs
diff --git a/tests/target/imports.rs b/tests/target/imports/imports.rs
index 87584d89f66..87584d89f66 100644
--- a/tests/target/imports.rs
+++ b/tests/target/imports/imports.rs
diff --git a/tests/target/imports_2021_edition.rs b/tests/target/imports/imports_2021_edition.rs
index 34dcc866a0b..34dcc866a0b 100644
--- a/tests/target/imports_2021_edition.rs
+++ b/tests/target/imports/imports_2021_edition.rs
diff --git a/tests/target/imports_block_indent.rs b/tests/target/imports/imports_block_indent.rs
index 8c90f7ce29c..8c90f7ce29c 100644
--- a/tests/target/imports_block_indent.rs
+++ b/tests/target/imports/imports_block_indent.rs
diff --git a/tests/target/imports_granularity_crate.rs b/tests/target/imports/imports_granularity_crate.rs
index 36e01558ff0..36e01558ff0 100644
--- a/tests/target/imports_granularity_crate.rs
+++ b/tests/target/imports/imports_granularity_crate.rs
diff --git a/tests/target/imports/imports_granularity_default-with-dups.rs b/tests/target/imports/imports_granularity_default-with-dups.rs
new file mode 100644
index 00000000000..5da6d588e6d
--- /dev/null
+++ b/tests/target/imports/imports_granularity_default-with-dups.rs
@@ -0,0 +1,6 @@
+use crate::lexer;
+use crate::lexer;
+use crate::lexer::tokens::TokenData;
+use crate::lexer::tokens::TokenData;
+use crate::lexer::{self};
+use crate::lexer::{self, tokens::TokenData};
diff --git a/tests/target/imports/imports_granularity_item-with-dups-StdExternalCrate-no-reorder.rs b/tests/target/imports/imports_granularity_item-with-dups-StdExternalCrate-no-reorder.rs
new file mode 100644
index 00000000000..ed4df544d6f
--- /dev/null
+++ b/tests/target/imports/imports_granularity_item-with-dups-StdExternalCrate-no-reorder.rs
@@ -0,0 +1,7 @@
+// rustfmt-imports_granularity: Item
+// rustfmt-reorder_imports: false
+// rustfmt-group_imports: StdExternalCrate
+
+use crate::lexer;
+use crate::lexer::tokens::TokenData;
+use crate::lexer::{self};
diff --git a/tests/target/imports/imports_granularity_item-with-dups.rs b/tests/target/imports/imports_granularity_item-with-dups.rs
new file mode 100644
index 00000000000..00df37f9332
--- /dev/null
+++ b/tests/target/imports/imports_granularity_item-with-dups.rs
@@ -0,0 +1,5 @@
+// rustfmt-imports_granularity: Item
+
+use crate::lexer;
+use crate::lexer::tokens::TokenData;
+use crate::lexer::{self};
diff --git a/tests/target/imports_granularity_item.rs b/tests/target/imports/imports_granularity_item.rs
index d2f5496fdac..d2f5496fdac 100644
--- a/tests/target/imports_granularity_item.rs
+++ b/tests/target/imports/imports_granularity_item.rs
diff --git a/tests/target/imports_granularity_module.rs b/tests/target/imports/imports_granularity_module.rs
index 14f341016ff..14f341016ff 100644
--- a/tests/target/imports_granularity_module.rs
+++ b/tests/target/imports/imports_granularity_module.rs