add iter_over_hash_type lint

7 files changed, 167 insertions, 0 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 87a96bdeba6..5448b1267be 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -5123,6 +5123,7 @@ Released 2018-09-13
 [`iter_on_empty_collections`]: https://rust-lang.github.io/rust-clippy/master/index.html#iter_on_empty_collections
 [`iter_on_single_items`]: https://rust-lang.github.io/rust-clippy/master/index.html#iter_on_single_items
 [`iter_out_of_bounds`]: https://rust-lang.github.io/rust-clippy/master/index.html#iter_out_of_bounds
+[`iter_over_hash_type`]: https://rust-lang.github.io/rust-clippy/master/index.html#iter_over_hash_type
 [`iter_overeager_cloned`]: https://rust-lang.github.io/rust-clippy/master/index.html#iter_overeager_cloned
 [`iter_skip_next`]: https://rust-lang.github.io/rust-clippy/master/index.html#iter_skip_next
 [`iter_skip_zero`]: https://rust-lang.github.io/rust-clippy/master/index.html#iter_skip_zero
diff --git a/clippy_lints/src/declared_lints.rs b/clippy_lints/src/declared_lints.rs
index 04dcccede08..b4d5e074cdd 100644
--- a/clippy_lints/src/declared_lints.rs
+++ b/clippy_lints/src/declared_lints.rs
@@ -230,6 +230,7 @@ pub(crate) static LINTS: &[&crate::LintInfo] = &[
     crate::items_after_statements::ITEMS_AFTER_STATEMENTS_INFO,
     crate::items_after_test_module::ITEMS_AFTER_TEST_MODULE_INFO,
     crate::iter_not_returning_iterator::ITER_NOT_RETURNING_ITERATOR_INFO,
+    crate::iter_over_hash_type::ITER_OVER_HASH_TYPE_INFO,
     crate::iter_without_into_iter::INTO_ITER_WITHOUT_ITER_INFO,
     crate::iter_without_into_iter::ITER_WITHOUT_INTO_ITER_INFO,
     crate::large_const_arrays::LARGE_CONST_ARRAYS_INFO,
diff --git a/clippy_lints/src/iter_over_hash_type.rs b/clippy_lints/src/iter_over_hash_type.rs
new file mode 100644
index 00000000000..554790ac61b
--- /dev/null
+++ b/clippy_lints/src/iter_over_hash_type.rs
@@ -0,0 +1,63 @@
+use clippy_utils::paths::{HASHMAP_KEYS, HASHMAP_VALUES, HASHSET_ITER_TY};
+use clippy_utils::{diagnostics::span_lint, match_def_path};
+use clippy_utils::higher::ForLoop;
+use clippy_utils::ty::is_type_diagnostic_item;
+use rustc_lint::{LateContext, LateLintPass};
+use rustc_session::{declare_lint_pass, declare_tool_lint};
+use rustc_span::sym;
+
+declare_clippy_lint! {
+    /// ### What it does
+    /// This is a restriction lint which prevents the use of hash types (i.e., `HashSet` and `HashMap`) in for loops.
+    ///
+    /// ### Why is this bad?
+    /// Because hash types are unordered, when iterated through such as in a for loop, the values are returned in
+    /// a pseudo-random order. As a result, on redundant systems this may cause inconsistencies and anomalies.
+    /// In addition, the unknown order of the elements may reduce readability or introduce other undesired
+    /// side effects.
+    ///
+    /// ### Example
+    /// ```no_run
+    ///     let my_map = new Hashmap<i32, String>();
+    ///     for (key, value) in my_map { /* ... */ }
+    /// ```
+    /// Use instead:
+    /// ```no_run
+    ///     let my_map = new Hashmap<i32, String>();
+    ///     let mut keys = my_map.keys().clone().collect::<Vec<_>();
+    ///     keys.sort();
+    ///     for key in keys {
+    ///         let value = &my_map[value];
+    ///     }
+    /// ```
+    #[clippy::version = "1.75.0"]
+    pub ITER_OVER_HASH_TYPE,
+    restriction,
+    "iterating over unordered hash-based types (`HashMap` and `HashSet`)"
+}
+
+declare_lint_pass!(IterOverHashType => [ITER_OVER_HASH_TYPE]);
+
+impl LateLintPass<'_> for IterOverHashType {
+    fn check_expr(&mut self, cx: &LateContext<'_>, expr: &'_ rustc_hir::Expr<'_>) {
+        if let Some(for_loop) = ForLoop::hir(expr)
+            && !for_loop.body.span.from_expansion()
+            && let ty = cx.typeck_results().expr_ty(for_loop.arg).peel_refs()
+            && let Some(adt) = ty.ty_adt_def()
+            && let did = adt.did()
+            && (match_def_path(cx, did, &HASHMAP_KEYS) 
+                || match_def_path(cx, did, &HASHMAP_VALUES)
+                || match_def_path(cx, did, &HASHSET_ITER_TY)
+                || is_type_diagnostic_item(cx, ty, sym::HashMap) 
+                || is_type_diagnostic_item(cx, ty, sym::HashSet))
+        {
+            span_lint(
+                cx,
+                ITER_OVER_HASH_TYPE,
+                expr.span,
+                "iterating over unordered hash-based type",
+            );
+        };
+    }
+}
+
diff --git a/clippy_lints/src/lib.rs b/clippy_lints/src/lib.rs
index e5f8bd5c471..9bdf6b0224d 100644
--- a/clippy_lints/src/lib.rs
+++ b/clippy_lints/src/lib.rs
@@ -165,6 +165,7 @@ mod item_name_repetitions;
 mod items_after_statements;
 mod items_after_test_module;
 mod iter_not_returning_iterator;
+mod iter_over_hash_type;
 mod iter_without_into_iter;
 mod large_const_arrays;
 mod large_enum_variant;
@@ -1065,6 +1066,7 @@ pub fn register_plugins(store: &mut rustc_lint::LintStore, sess: &Session, conf:
     });
     store.register_late_pass(move |_| Box::new(manual_hash_one::ManualHashOne::new(msrv())));
     store.register_late_pass(|_| Box::new(iter_without_into_iter::IterWithoutIntoIter));
+    store.register_late_pass(|_| Box::new(iter_over_hash_type::IterOverHashType));
     // add lints here, do not remove this comment, it's used in `new_lint`
 }
 
diff --git a/clippy_utils/src/paths.rs b/clippy_utils/src/paths.rs
index 859bffd6c9c..9c9fb381e54 100644
--- a/clippy_utils/src/paths.rs
+++ b/clippy_utils/src/paths.rs
@@ -32,6 +32,9 @@ pub const FUTURES_IO_ASYNCREADEXT: [&str; 3] = ["futures_util", "io", "AsyncRead
 pub const FUTURES_IO_ASYNCWRITEEXT: [&str; 3] = ["futures_util", "io", "AsyncWriteExt"];
 pub const HASHMAP_CONTAINS_KEY: [&str; 6] = ["std", "collections", "hash", "map", "HashMap", "contains_key"];
 pub const HASHMAP_INSERT: [&str; 6] = ["std", "collections", "hash", "map", "HashMap", "insert"];
+pub const HASHMAP_KEYS: [&str; 5] = ["std", "collections", "hash", "map", "Keys"];
+pub const HASHMAP_VALUES: [&str; 5] = ["std", "collections", "hash", "map", "Values"];
+pub const HASHSET_ITER_TY: [&str; 5] = ["std", "collections", "hash", "set", "Iter"];
 pub const HASHSET_ITER: [&str; 6] = ["std", "collections", "hash", "set", "HashSet", "iter"];
 pub const IDENT: [&str; 3] = ["rustc_span", "symbol", "Ident"];
 pub const IDENT_AS_STR: [&str; 4] = ["rustc_span", "symbol", "Ident", "as_str"];
diff --git a/tests/ui/iter_over_hash_type.rs b/tests/ui/iter_over_hash_type.rs
new file mode 100644
index 00000000000..fc340abf146
--- /dev/null
+++ b/tests/ui/iter_over_hash_type.rs
@@ -0,0 +1,44 @@
+//@aux-build:proc_macros.rs
+
+#![warn(clippy::iter_over_hash_type)]
+use std::collections::{HashMap, HashSet};
+
+extern crate proc_macros;
+
+fn main() {
+    let hash_set = HashSet::<i32>::new();
+    let hash_map = HashMap::<i32, i32>::new();
+    let vec = Vec::<i32>::new();
+
+    for x in &hash_set {
+        let _ = x;
+    }
+    for x in hash_set.iter() {
+        let _ = x;
+    }
+    for x in hash_set {
+        let _ = x;
+    }
+    for (x, y) in &hash_map {
+        let _ = (x, y);
+    }
+    for x in hash_map.keys() {
+        let _ = x;
+    }
+    for x in hash_map.values() {
+        let _ = x;
+    }
+
+    // shouldnt fire
+    for x in &vec {
+        let _ = x;
+    }
+    for x in vec {
+        let _ = x;
+    }
+
+    // should not lint, this comes from an external crate
+    proc_macros::external! {
+      for _ in HashMap::<i32, i32>::new() {}
+    }
+}
diff --git a/tests/ui/iter_over_hash_type.stderr b/tests/ui/iter_over_hash_type.stderr
new file mode 100644
index 00000000000..72d621c7b59
--- /dev/null
+++ b/tests/ui/iter_over_hash_type.stderr
@@ -0,0 +1,53 @@
+error: iterating over unordered hash-based type
+  --> $DIR/iter_over_hash_type.rs:13:5
+   |
+LL | /     for x in &hash_set {
+LL | |         let _ = x;
+LL | |     }
+   | |_____^
+   |
+   = note: `-D clippy::iter-over-hash-type` implied by `-D warnings`
+   = help: to override `-D warnings` add `#[allow(clippy::iter_over_hash_type)]`
+
+error: iterating over unordered hash-based type
+  --> $DIR/iter_over_hash_type.rs:16:5
+   |
+LL | /     for x in hash_set.iter() {
+LL | |         let _ = x;
+LL | |     }
+   | |_____^
+
+error: iterating over unordered hash-based type
+  --> $DIR/iter_over_hash_type.rs:19:5
+   |
+LL | /     for x in hash_set {
+LL | |         let _ = x;
+LL | |     }
+   | |_____^
+
+error: iterating over unordered hash-based type
+  --> $DIR/iter_over_hash_type.rs:22:5
+   |
+LL | /     for (x, y) in &hash_map {
+LL | |         let _ = (x, y);
+LL | |     }
+   | |_____^
+
+error: iterating over unordered hash-based type
+  --> $DIR/iter_over_hash_type.rs:25:5
+   |
+LL | /     for x in hash_map.keys() {
+LL | |         let _ = x;
+LL | |     }
+   | |_____^
+
+error: iterating over unordered hash-based type
+  --> $DIR/iter_over_hash_type.rs:28:5
+   |
+LL | /     for x in hash_map.values() {
+LL | |         let _ = x;
+LL | |     }
+   | |_____^
+
+error: aborting due to 6 previous errors
+