1 use clippy_utils::diagnostics::span_lint_and_then;
2 use clippy_utils::{is_slice_of_primitives, sugg::Sugg};
3 use if_chain::if_chain;
4 use rustc_errors::Applicability;
5 use rustc_hir::{Expr, ExprKind};
6 use rustc_lint::{LateContext, LateLintPass};
7 use rustc_session::{declare_lint_pass, declare_tool_lint};
11 /// When sorting primitive values (integers, bools, chars, as well
12 /// as arrays, slices, and tuples of such items), it is typically better to
13 /// use an unstable sort than a stable sort.
15 /// ### Why is this bad?
16 /// Typically, using a stable sort consumes more memory and cpu cycles.
17 /// Because values which compare equal are identical, preserving their
18 /// relative order (the guarantee that a stable sort provides) means
19 /// nothing, while the extra costs still apply.
21 /// ### Known problems
24 /// [issue #8241](https://github.com/rust-lang/rust-clippy/issues/8241),
25 /// a stable sort can instead be significantly faster for certain scenarios
26 /// (eg. when a sorted vector is extended with new data and resorted).
28 /// For more information and benchmarking results, please refer to the
29 /// issue linked above.
33 /// let mut vec = vec![2, 1, 3];
38 /// let mut vec = vec![2, 1, 3];
39 /// vec.sort_unstable();
41 #[clippy::version = "1.47.0"]
42 pub STABLE_SORT_PRIMITIVE,
44 "use of sort() when sort_unstable() is equivalent"
47 declare_lint_pass!(StableSortPrimitive => [STABLE_SORT_PRIMITIVE]);
49 /// The three "kinds" of sorts
52 /* The other kinds of lint are currently commented out because they
53 * can map distinct values to equal ones. If the key function is
54 * provably one-to-one, or if the Cmp function conserves equality,
55 * then they could be linted on, but I don't know if we can check
62 /// The name of the stable version of this kind of sort
63 fn stable_name(&self) -> &str {
65 SortingKind::Vanilla => "sort",
66 /* SortingKind::ByKey => "sort_by_key",
67 * SortingKind::ByCmp => "sort_by", */
70 /// The name of the unstable version of this kind of sort
71 fn unstable_name(&self) -> &str {
73 SortingKind::Vanilla => "sort_unstable",
74 /* SortingKind::ByKey => "sort_unstable_by_key",
75 * SortingKind::ByCmp => "sort_unstable_by", */
78 /// Takes the name of a function call and returns the kind of sort
79 /// that corresponds to that function name (or None if it isn't)
80 fn from_stable_name(name: &str) -> Option<SortingKind> {
82 "sort" => Some(SortingKind::Vanilla),
83 // "sort_by" => Some(SortingKind::ByCmp),
84 // "sort_by_key" => Some(SortingKind::ByKey),
90 /// A detected instance of this lint
91 struct LintDetection {
98 fn detect_stable_sort_primitive(cx: &LateContext<'_>, expr: &Expr<'_>) -> Option<LintDetection> {
100 if let ExprKind::MethodCall(method_name, args, _) = &expr.kind;
101 if let Some(slice) = &args.get(0);
102 if let Some(method) = SortingKind::from_stable_name(method_name.ident.name.as_str());
103 if let Some(slice_type) = is_slice_of_primitives(cx, slice);
105 let args_str = args.iter().skip(1).map(|arg| Sugg::hir(cx, arg, "..").to_string()).collect::<Vec<String>>().join(", ");
106 Some(LintDetection { slice_name: Sugg::hir(cx, slice, "..").to_string(), method, method_args: args_str, slice_type })
113 impl LateLintPass<'_> for StableSortPrimitive {
114 fn check_expr(&mut self, cx: &LateContext<'_>, expr: &Expr<'_>) {
115 if let Some(detection) = detect_stable_sort_primitive(cx, expr) {
118 STABLE_SORT_PRIMITIVE,
121 "used `{}` on primitive type `{}`",
122 detection.method.stable_name(),
123 detection.slice_type,
127 diag.span_suggestion(
132 detection.slice_name,
133 detection.method.unstable_name(),
134 detection.method_args,
136 Applicability::MachineApplicable,
139 "an unstable sort typically performs faster without any observable difference for this data type",