From 25abd7ae76e2a708dda5487119c20af3be64edb7 Mon Sep 17 00:00:00 2001 From: JarredAllen Date: Wed, 8 Jul 2020 20:29:56 -0700 Subject: [PATCH] Create stable_sort_primitive lint --- CHANGELOG.md | 1 + clippy_lints/src/lib.rs | 5 + clippy_lints/src/stable_sort_primitive.rs | 130 ++++++++++++++++++++++ clippy_lints/src/utils/mod.rs | 30 +++++ src/lintlist/mod.rs | 7 ++ tests/ui/stable_sort_primitive.fixed | 32 ++++++ tests/ui/stable_sort_primitive.rs | 32 ++++++ tests/ui/stable_sort_primitive.stderr | 46 ++++++++ tests/ui/unnecessary_sort_by.fixed | 2 + tests/ui/unnecessary_sort_by.rs | 2 + tests/ui/unnecessary_sort_by.stderr | 14 +-- 11 files changed, 294 insertions(+), 7 deletions(-) create mode 100644 clippy_lints/src/stable_sort_primitive.rs create mode 100644 tests/ui/stable_sort_primitive.fixed create mode 100644 tests/ui/stable_sort_primitive.rs create mode 100644 tests/ui/stable_sort_primitive.stderr diff --git a/CHANGELOG.md b/CHANGELOG.md index 776b04295f9..43a32e828d8 100644 --- a/CHANGELOG.md +++ b/CHANGELOG.md @@ -1701,6 +1701,7 @@ Released 2018-09-13 [`single_match_else`]: https://rust-lang.github.io/rust-clippy/master/index.html#single_match_else [`skip_while_next`]: https://rust-lang.github.io/rust-clippy/master/index.html#skip_while_next [`slow_vector_initialization`]: https://rust-lang.github.io/rust-clippy/master/index.html#slow_vector_initialization +[`stable_sort_primitive`]: https://rust-lang.github.io/rust-clippy/master/index.html#stable_sort_primitive [`str_to_string`]: https://rust-lang.github.io/rust-clippy/master/index.html#str_to_string [`string_add`]: https://rust-lang.github.io/rust-clippy/master/index.html#string_add [`string_add_assign`]: https://rust-lang.github.io/rust-clippy/master/index.html#string_add_assign diff --git a/clippy_lints/src/lib.rs b/clippy_lints/src/lib.rs index f371942dbee..9fc07e07fd3 100644 --- a/clippy_lints/src/lib.rs +++ b/clippy_lints/src/lib.rs @@ -288,6 +288,7 @@ macro_rules! declare_clippy_lint { mod shadow; mod single_component_path_imports; mod slow_vector_initialization; +mod stable_sort_primitive; mod strings; mod suspicious_trait_impl; mod swap; @@ -776,6 +777,7 @@ pub fn register_plugins(store: &mut rustc_lint::LintStore, sess: &Session, conf: &shadow::SHADOW_UNRELATED, &single_component_path_imports::SINGLE_COMPONENT_PATH_IMPORTS, &slow_vector_initialization::SLOW_VECTOR_INITIALIZATION, + &stable_sort_primitive::STABLE_SORT_PRIMITIVE, &strings::STRING_ADD, &strings::STRING_ADD_ASSIGN, &strings::STRING_LIT_AS_BYTES, @@ -1078,6 +1080,7 @@ pub fn register_plugins(store: &mut rustc_lint::LintStore, sess: &Session, conf: store.register_late_pass(|| box macro_use::MacroUseImports::default()); store.register_late_pass(|| box map_identity::MapIdentity); store.register_late_pass(|| box pattern_type_mismatch::PatternTypeMismatch); + store.register_late_pass(|| box stable_sort_primitive::StableSortPrimitive); store.register_late_pass(|| box repeat_once::RepeatOnce); store.register_group(true, "clippy::restriction", Some("clippy_restriction"), vec![ @@ -1408,6 +1411,7 @@ pub fn register_plugins(store: &mut rustc_lint::LintStore, sess: &Session, conf: LintId::of(&serde_api::SERDE_API_MISUSE), LintId::of(&single_component_path_imports::SINGLE_COMPONENT_PATH_IMPORTS), LintId::of(&slow_vector_initialization::SLOW_VECTOR_INITIALIZATION), + LintId::of(&stable_sort_primitive::STABLE_SORT_PRIMITIVE), LintId::of(&strings::STRING_LIT_AS_BYTES), LintId::of(&suspicious_trait_impl::SUSPICIOUS_ARITHMETIC_IMPL), LintId::of(&suspicious_trait_impl::SUSPICIOUS_OP_ASSIGN_IMPL), @@ -1723,6 +1727,7 @@ pub fn register_plugins(store: &mut rustc_lint::LintStore, sess: &Session, conf: LintId::of(&mutex_atomic::MUTEX_ATOMIC), LintId::of(&redundant_clone::REDUNDANT_CLONE), LintId::of(&slow_vector_initialization::SLOW_VECTOR_INITIALIZATION), + LintId::of(&stable_sort_primitive::STABLE_SORT_PRIMITIVE), LintId::of(&types::BOX_VEC), LintId::of(&types::REDUNDANT_ALLOCATION), LintId::of(&vec::USELESS_VEC), diff --git a/clippy_lints/src/stable_sort_primitive.rs b/clippy_lints/src/stable_sort_primitive.rs new file mode 100644 index 00000000000..c48da004a60 --- /dev/null +++ b/clippy_lints/src/stable_sort_primitive.rs @@ -0,0 +1,130 @@ +use crate::utils::{is_slice_of_primitives, span_lint_and_sugg, sugg::Sugg}; + +use if_chain::if_chain; + +use rustc_errors::Applicability; +use rustc_hir::{Expr, ExprKind}; +use rustc_lint::{LateContext, LateLintPass}; +use rustc_session::{declare_lint_pass, declare_tool_lint}; + +declare_clippy_lint! { + /// **What it does:** + /// When sorting primitive values (integers, bools, chars, as well + /// as arrays, slices, and tuples of such items), it is better to + /// use an unstable sort than a stable sort. + /// + /// **Why is this bad?** + /// Using a stable sort consumes more memory and cpu cycles. Because + /// values which compare equal are identical, preserving their + /// relative order (the guarantee that a stable sort provides) means + /// nothing, while the extra costs still apply. + /// + /// **Known problems:** + /// None + /// + /// **Example:** + /// + /// ```rust + /// let mut vec = vec![2, 1, 3]; + /// vec.sort(); + /// ``` + /// Use instead: + /// ```rust + /// let mut vec = vec![2, 1, 3]; + /// vec.sort_unstable(); + /// ``` + pub STABLE_SORT_PRIMITIVE, + perf, + "use of sort() when sort_unstable() is equivalent" +} + +declare_lint_pass!(StableSortPrimitive => [STABLE_SORT_PRIMITIVE]); + +/// The three "kinds" of sorts +enum SortingKind { + Vanilla, + // The other kinds of lint are currently commented out because they + // can map distinct values to equal ones. If the key function is + // provably one-to-one, or if the Cmp function conserves equality, + // then they could be linted on, but I don't know if we can check + // for that. + + // ByKey, + // ByCmp, +} +impl SortingKind { + /// The name of the stable version of this kind of sort + fn stable_name(&self) -> &str { + match self { + SortingKind::Vanilla => "sort", + // SortingKind::ByKey => "sort_by_key", + // SortingKind::ByCmp => "sort_by", + } + } + /// The name of the unstable version of this kind of sort + fn unstable_name(&self) -> &str { + match self { + SortingKind::Vanilla => "sort_unstable", + // SortingKind::ByKey => "sort_unstable_by_key", + // SortingKind::ByCmp => "sort_unstable_by", + } + } + /// Takes the name of a function call and returns the kind of sort + /// that corresponds to that function name (or None if it isn't) + fn from_stable_name(name: &str) -> Option { + match name { + "sort" => Some(SortingKind::Vanilla), + // "sort_by" => Some(SortingKind::ByCmp), + // "sort_by_key" => Some(SortingKind::ByKey), + _ => None, + } + } +} + +/// A detected instance of this lint +struct LintDetection { + slice_name: String, + method: SortingKind, + method_args: String, +} + +fn detect_stable_sort_primitive(cx: &LateContext<'_>, expr: &Expr<'_>) -> Option { + if_chain! { + if let ExprKind::MethodCall(method_name, _, args, _) = &expr.kind; + if let Some(slice) = &args.get(0); + if let Some(method) = SortingKind::from_stable_name(&method_name.ident.name.as_str()); + if is_slice_of_primitives(cx, slice); + then { + let args_str = args.iter().skip(1).map(|arg| Sugg::hir(cx, arg, "..").to_string()).collect::>().join(", "); + Some(LintDetection { slice_name: Sugg::hir(cx, slice, "..").to_string(), method, method_args: args_str }) + } else { + None + } + } +} + +impl LateLintPass<'_> for StableSortPrimitive { + fn check_expr(&mut self, cx: &LateContext<'_>, expr: &Expr<'_>) { + if let Some(detection) = detect_stable_sort_primitive(cx, expr) { + span_lint_and_sugg( + cx, + STABLE_SORT_PRIMITIVE, + expr.span, + format!( + "Use {} instead of {}", + detection.method.unstable_name(), + detection.method.stable_name() + ) + .as_str(), + "try", + format!( + "{}.{}({})", + detection.slice_name, + detection.method.unstable_name(), + detection.method_args + ), + Applicability::MachineApplicable, + ); + } + } +} diff --git a/clippy_lints/src/utils/mod.rs b/clippy_lints/src/utils/mod.rs index 655b1133cf7..c75f8042907 100644 --- a/clippy_lints/src/utils/mod.rs +++ b/clippy_lints/src/utils/mod.rs @@ -1378,6 +1378,36 @@ pub fn run_lints(cx: &LateContext<'_>, lints: &[&'static Lint], id: HirId) -> bo }) } +/// Returns true iff the given type is a primitive (a bool or char, any integer or floating-point +/// number type, a str, or an array, slice, or tuple of those types). +pub fn is_recursively_primitive_type(ty: Ty<'_>) -> bool { + match ty.kind { + ty::Bool | ty::Char | ty::Int(_) | ty::Uint(_) | ty::Float(_) | ty::Str => true, + ty::Ref(_, inner, _) if inner.kind == ty::Str => true, + ty::Array(inner_type, _) | ty::Slice(inner_type) => is_recursively_primitive_type(inner_type), + ty::Tuple(inner_types) => inner_types.types().all(is_recursively_primitive_type), + _ => false, + } +} + +/// Returns true iff the given expression is a slice of primitives (as defined in the +/// `is_recursively_primitive_type` function). +pub fn is_slice_of_primitives(cx: &LateContext<'_>, expr: &Expr<'_>) -> bool { + let expr_type = cx.typeck_results().expr_ty_adjusted(expr); + match expr_type.kind { + ty::Slice(ref element_type) + | ty::Ref( + _, + ty::TyS { + kind: ty::Slice(ref element_type), + .. + }, + _, + ) => is_recursively_primitive_type(element_type), + _ => false, + } +} + #[macro_export] macro_rules! unwrap_cargo_metadata { ($cx: ident, $lint: ident, $deps: expr) => {{ diff --git a/src/lintlist/mod.rs b/src/lintlist/mod.rs index 1879aae77fb..41d06a67881 100644 --- a/src/lintlist/mod.rs +++ b/src/lintlist/mod.rs @@ -2026,6 +2026,13 @@ deprecation: None, module: "slow_vector_initialization", }, + Lint { + name: "stable_sort_primitive", + group: "perf", + desc: "use of sort() when sort_unstable() is equivalent", + deprecation: None, + module: "stable_sort_primitive", + }, Lint { name: "string_add", group: "restriction", diff --git a/tests/ui/stable_sort_primitive.fixed b/tests/ui/stable_sort_primitive.fixed new file mode 100644 index 00000000000..8f8f5665931 --- /dev/null +++ b/tests/ui/stable_sort_primitive.fixed @@ -0,0 +1,32 @@ +// run-rustfix +#![warn(clippy::stable_sort_primitive)] + +fn main() { + // positive examples + let mut vec = vec![1, 3, 2]; + vec.sort_unstable(); + let mut vec = vec![false, false, true]; + vec.sort_unstable(); + let mut vec = vec!['a', 'A', 'c']; + vec.sort_unstable(); + let mut vec = vec!["ab", "cd", "ab", "bc"]; + vec.sort_unstable(); + let mut vec = vec![(2, 1), (1, 2), (2, 5)]; + vec.sort_unstable(); + let mut vec = vec![[2, 1], [1, 2], [2, 5]]; + vec.sort_unstable(); + let mut arr = [1, 3, 2]; + arr.sort_unstable(); + // Negative examples: behavior changes if made unstable + let mut vec = vec![1, 3, 2]; + vec.sort_by_key(|i| i / 2); + vec.sort_by(|a, b| (a + b).cmp(&b)); + // negative examples - Not of a primitive type + let mut vec_of_complex = vec![String::from("hello"), String::from("world!")]; + vec_of_complex.sort(); + vec_of_complex.sort_by_key(String::len); + let mut vec = vec![(String::from("hello"), String::from("world"))]; + vec.sort(); + let mut vec = vec![[String::from("hello"), String::from("world")]]; + vec.sort(); +} diff --git a/tests/ui/stable_sort_primitive.rs b/tests/ui/stable_sort_primitive.rs new file mode 100644 index 00000000000..f9bd9779067 --- /dev/null +++ b/tests/ui/stable_sort_primitive.rs @@ -0,0 +1,32 @@ +// run-rustfix +#![warn(clippy::stable_sort_primitive)] + +fn main() { + // positive examples + let mut vec = vec![1, 3, 2]; + vec.sort(); + let mut vec = vec![false, false, true]; + vec.sort(); + let mut vec = vec!['a', 'A', 'c']; + vec.sort(); + let mut vec = vec!["ab", "cd", "ab", "bc"]; + vec.sort(); + let mut vec = vec![(2, 1), (1, 2), (2, 5)]; + vec.sort(); + let mut vec = vec![[2, 1], [1, 2], [2, 5]]; + vec.sort(); + let mut arr = [1, 3, 2]; + arr.sort(); + // Negative examples: behavior changes if made unstable + let mut vec = vec![1, 3, 2]; + vec.sort_by_key(|i| i / 2); + vec.sort_by(|a, b| (a + b).cmp(&b)); + // negative examples - Not of a primitive type + let mut vec_of_complex = vec![String::from("hello"), String::from("world!")]; + vec_of_complex.sort(); + vec_of_complex.sort_by_key(String::len); + let mut vec = vec![(String::from("hello"), String::from("world"))]; + vec.sort(); + let mut vec = vec![[String::from("hello"), String::from("world")]]; + vec.sort(); +} diff --git a/tests/ui/stable_sort_primitive.stderr b/tests/ui/stable_sort_primitive.stderr new file mode 100644 index 00000000000..b0b729ede48 --- /dev/null +++ b/tests/ui/stable_sort_primitive.stderr @@ -0,0 +1,46 @@ +error: Use sort_unstable instead of sort + --> $DIR/stable_sort_primitive.rs:7:5 + | +LL | vec.sort(); + | ^^^^^^^^^^ help: try: `vec.sort_unstable()` + | + = note: `-D clippy::stable-sort-primitive` implied by `-D warnings` + +error: Use sort_unstable instead of sort + --> $DIR/stable_sort_primitive.rs:9:5 + | +LL | vec.sort(); + | ^^^^^^^^^^ help: try: `vec.sort_unstable()` + +error: Use sort_unstable instead of sort + --> $DIR/stable_sort_primitive.rs:11:5 + | +LL | vec.sort(); + | ^^^^^^^^^^ help: try: `vec.sort_unstable()` + +error: Use sort_unstable instead of sort + --> $DIR/stable_sort_primitive.rs:13:5 + | +LL | vec.sort(); + | ^^^^^^^^^^ help: try: `vec.sort_unstable()` + +error: Use sort_unstable instead of sort + --> $DIR/stable_sort_primitive.rs:15:5 + | +LL | vec.sort(); + | ^^^^^^^^^^ help: try: `vec.sort_unstable()` + +error: Use sort_unstable instead of sort + --> $DIR/stable_sort_primitive.rs:17:5 + | +LL | vec.sort(); + | ^^^^^^^^^^ help: try: `vec.sort_unstable()` + +error: Use sort_unstable instead of sort + --> $DIR/stable_sort_primitive.rs:19:5 + | +LL | arr.sort(); + | ^^^^^^^^^^ help: try: `arr.sort_unstable()` + +error: aborting due to 7 previous errors + diff --git a/tests/ui/unnecessary_sort_by.fixed b/tests/ui/unnecessary_sort_by.fixed index c017d1cf9a4..31c2ba0f9c5 100644 --- a/tests/ui/unnecessary_sort_by.fixed +++ b/tests/ui/unnecessary_sort_by.fixed @@ -1,5 +1,7 @@ // run-rustfix +#![allow(clippy::stable_sort_primitive)] + use std::cmp::Reverse; fn unnecessary_sort_by() { diff --git a/tests/ui/unnecessary_sort_by.rs b/tests/ui/unnecessary_sort_by.rs index 1929c72b2f2..a3c8ae468ed 100644 --- a/tests/ui/unnecessary_sort_by.rs +++ b/tests/ui/unnecessary_sort_by.rs @@ -1,5 +1,7 @@ // run-rustfix +#![allow(clippy::stable_sort_primitive)] + use std::cmp::Reverse; fn unnecessary_sort_by() { diff --git a/tests/ui/unnecessary_sort_by.stderr b/tests/ui/unnecessary_sort_by.stderr index 903b6e5099c..70c6cf0a3b6 100644 --- a/tests/ui/unnecessary_sort_by.stderr +++ b/tests/ui/unnecessary_sort_by.stderr @@ -1,5 +1,5 @@ error: use Vec::sort here instead - --> $DIR/unnecessary_sort_by.rs:12:5 + --> $DIR/unnecessary_sort_by.rs:14:5 | LL | vec.sort_by(|a, b| a.cmp(b)); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `vec.sort()` @@ -7,37 +7,37 @@ LL | vec.sort_by(|a, b| a.cmp(b)); = note: `-D clippy::unnecessary-sort-by` implied by `-D warnings` error: use Vec::sort here instead - --> $DIR/unnecessary_sort_by.rs:13:5 + --> $DIR/unnecessary_sort_by.rs:15:5 | LL | vec.sort_unstable_by(|a, b| a.cmp(b)); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `vec.sort_unstable()` error: use Vec::sort_by_key here instead - --> $DIR/unnecessary_sort_by.rs:14:5 + --> $DIR/unnecessary_sort_by.rs:16:5 | LL | vec.sort_by(|a, b| (a + 5).abs().cmp(&(b + 5).abs())); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `vec.sort_by_key(|&a| (a + 5).abs())` error: use Vec::sort_by_key here instead - --> $DIR/unnecessary_sort_by.rs:15:5 + --> $DIR/unnecessary_sort_by.rs:17:5 | LL | vec.sort_unstable_by(|a, b| id(-a).cmp(&id(-b))); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `vec.sort_unstable_by_key(|&a| id(-a))` error: use Vec::sort_by_key here instead - --> $DIR/unnecessary_sort_by.rs:17:5 + --> $DIR/unnecessary_sort_by.rs:19:5 | LL | vec.sort_by(|a, b| b.cmp(a)); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `vec.sort_by_key(|&b| Reverse(b))` error: use Vec::sort_by_key here instead - --> $DIR/unnecessary_sort_by.rs:18:5 + --> $DIR/unnecessary_sort_by.rs:20:5 | LL | vec.sort_by(|a, b| (b + 5).abs().cmp(&(a + 5).abs())); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `vec.sort_by_key(|&b| Reverse((b + 5).abs()))` error: use Vec::sort_by_key here instead - --> $DIR/unnecessary_sort_by.rs:19:5 + --> $DIR/unnecessary_sort_by.rs:21:5 | LL | vec.sort_unstable_by(|a, b| id(-b).cmp(&id(-a))); | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ help: try: `vec.sort_unstable_by_key(|&b| Reverse(id(-b)))` -- 2.44.0