]>
Commit | Line | Data |
---|---|---|
f20569fa XL |
1 | use crate::utils::{is_slice_of_primitives, span_lint_and_then, sugg::Sugg}; |
2 | ||
3 | use if_chain::if_chain; | |
4 | ||
5 | use rustc_errors::Applicability; | |
6 | use rustc_hir::{Expr, ExprKind}; | |
7 | use rustc_lint::{LateContext, LateLintPass}; | |
8 | use rustc_session::{declare_lint_pass, declare_tool_lint}; | |
9 | ||
10 | declare_clippy_lint! { | |
11 | /// **What it does:** | |
12 | /// When sorting primitive values (integers, bools, chars, as well | |
13 | /// as arrays, slices, and tuples of such items), it is better to | |
14 | /// use an unstable sort than a stable sort. | |
15 | /// | |
16 | /// **Why is this bad?** | |
17 | /// Using a stable sort consumes more memory and cpu cycles. Because | |
18 | /// values which compare equal are identical, preserving their | |
19 | /// relative order (the guarantee that a stable sort provides) means | |
20 | /// nothing, while the extra costs still apply. | |
21 | /// | |
22 | /// **Known problems:** | |
23 | /// None | |
24 | /// | |
25 | /// **Example:** | |
26 | /// | |
27 | /// ```rust | |
28 | /// let mut vec = vec![2, 1, 3]; | |
29 | /// vec.sort(); | |
30 | /// ``` | |
31 | /// Use instead: | |
32 | /// ```rust | |
33 | /// let mut vec = vec![2, 1, 3]; | |
34 | /// vec.sort_unstable(); | |
35 | /// ``` | |
36 | pub STABLE_SORT_PRIMITIVE, | |
37 | perf, | |
38 | "use of sort() when sort_unstable() is equivalent" | |
39 | } | |
40 | ||
41 | declare_lint_pass!(StableSortPrimitive => [STABLE_SORT_PRIMITIVE]); | |
42 | ||
43 | /// The three "kinds" of sorts | |
44 | enum SortingKind { | |
45 | Vanilla, | |
46 | /* The other kinds of lint are currently commented out because they | |
47 | * can map distinct values to equal ones. If the key function is | |
48 | * provably one-to-one, or if the Cmp function conserves equality, | |
49 | * then they could be linted on, but I don't know if we can check | |
50 | * for that. */ | |
51 | ||
52 | /* ByKey, | |
53 | * ByCmp, */ | |
54 | } | |
55 | impl SortingKind { | |
56 | /// The name of the stable version of this kind of sort | |
57 | fn stable_name(&self) -> &str { | |
58 | match self { | |
59 | SortingKind::Vanilla => "sort", | |
60 | /* SortingKind::ByKey => "sort_by_key", | |
61 | * SortingKind::ByCmp => "sort_by", */ | |
62 | } | |
63 | } | |
64 | /// The name of the unstable version of this kind of sort | |
65 | fn unstable_name(&self) -> &str { | |
66 | match self { | |
67 | SortingKind::Vanilla => "sort_unstable", | |
68 | /* SortingKind::ByKey => "sort_unstable_by_key", | |
69 | * SortingKind::ByCmp => "sort_unstable_by", */ | |
70 | } | |
71 | } | |
72 | /// Takes the name of a function call and returns the kind of sort | |
73 | /// that corresponds to that function name (or None if it isn't) | |
74 | fn from_stable_name(name: &str) -> Option<SortingKind> { | |
75 | match name { | |
76 | "sort" => Some(SortingKind::Vanilla), | |
77 | // "sort_by" => Some(SortingKind::ByCmp), | |
78 | // "sort_by_key" => Some(SortingKind::ByKey), | |
79 | _ => None, | |
80 | } | |
81 | } | |
82 | } | |
83 | ||
84 | /// A detected instance of this lint | |
85 | struct LintDetection { | |
86 | slice_name: String, | |
87 | method: SortingKind, | |
88 | method_args: String, | |
89 | slice_type: String, | |
90 | } | |
91 | ||
92 | fn detect_stable_sort_primitive(cx: &LateContext<'_>, expr: &Expr<'_>) -> Option<LintDetection> { | |
93 | if_chain! { | |
94 | if let ExprKind::MethodCall(method_name, _, args, _) = &expr.kind; | |
95 | if let Some(slice) = &args.get(0); | |
96 | if let Some(method) = SortingKind::from_stable_name(&method_name.ident.name.as_str()); | |
97 | if let Some(slice_type) = is_slice_of_primitives(cx, slice); | |
98 | then { | |
99 | let args_str = args.iter().skip(1).map(|arg| Sugg::hir(cx, arg, "..").to_string()).collect::<Vec<String>>().join(", "); | |
100 | Some(LintDetection { slice_name: Sugg::hir(cx, slice, "..").to_string(), method, method_args: args_str, slice_type }) | |
101 | } else { | |
102 | None | |
103 | } | |
104 | } | |
105 | } | |
106 | ||
107 | impl LateLintPass<'_> for StableSortPrimitive { | |
108 | fn check_expr(&mut self, cx: &LateContext<'_>, expr: &Expr<'_>) { | |
109 | if let Some(detection) = detect_stable_sort_primitive(cx, expr) { | |
110 | span_lint_and_then( | |
111 | cx, | |
112 | STABLE_SORT_PRIMITIVE, | |
113 | expr.span, | |
114 | format!( | |
115 | "used `{}` on primitive type `{}`", | |
116 | detection.method.stable_name(), | |
117 | detection.slice_type, | |
118 | ) | |
119 | .as_str(), | |
120 | |diag| { | |
121 | diag.span_suggestion( | |
122 | expr.span, | |
123 | "try", | |
124 | format!( | |
125 | "{}.{}({})", | |
126 | detection.slice_name, | |
127 | detection.method.unstable_name(), | |
128 | detection.method_args, | |
129 | ), | |
130 | Applicability::MachineApplicable, | |
131 | ); | |
132 | diag.note( | |
133 | "an unstable sort would perform faster without any observable difference for this data type", | |
134 | ); | |
135 | }, | |
136 | ); | |
137 | } | |
138 | } | |
139 | } |