]>
Commit | Line | Data |
---|---|---|
064997fb | 1 | use clippy_utils::diagnostics::{span_lint_and_sugg, span_lint_hir_and_then}; |
cdc7bbd5 XL |
2 | use clippy_utils::source::snippet_opt; |
3 | use clippy_utils::ty::{implements_trait, is_type_diagnostic_item}; | |
a2a8927a | 4 | use clippy_utils::{eq_expr_value, get_trait_def_id, paths}; |
f20569fa XL |
5 | use if_chain::if_chain; |
6 | use rustc_ast::ast::LitKind; | |
7 | use rustc_errors::Applicability; | |
5099ac24 | 8 | use rustc_hir::intravisit::{walk_expr, FnKind, Visitor}; |
f20569fa XL |
9 | use rustc_hir::{BinOpKind, Body, Expr, ExprKind, FnDecl, HirId, UnOp}; |
10 | use rustc_lint::{LateContext, LateLintPass}; | |
f20569fa XL |
11 | use rustc_session::{declare_lint_pass, declare_tool_lint}; |
12 | use rustc_span::source_map::Span; | |
13 | use rustc_span::sym; | |
14 | ||
15 | declare_clippy_lint! { | |
94222f64 XL |
16 | /// ### What it does |
17 | /// Checks for boolean expressions that can be written more | |
f20569fa XL |
18 | /// concisely. |
19 | /// | |
94222f64 XL |
20 | /// ### Why is this bad? |
21 | /// Readability of boolean expressions suffers from | |
f20569fa XL |
22 | /// unnecessary duplication. |
23 | /// | |
94222f64 XL |
24 | /// ### Known problems |
25 | /// Ignores short circuiting behavior of `||` and | |
f20569fa XL |
26 | /// `&&`. Ignores `|`, `&` and `^`. |
27 | /// | |
94222f64 | 28 | /// ### Example |
f20569fa | 29 | /// ```ignore |
923072b8 FG |
30 | /// if a && true {} |
31 | /// if !(a == b) {} | |
32 | /// ``` | |
33 | /// | |
34 | /// Use instead: | |
35 | /// ```rust,ignore | |
36 | /// if a {} | |
37 | /// if a != b {} | |
f20569fa | 38 | /// ``` |
a2a8927a | 39 | #[clippy::version = "pre 1.29.0"] |
f20569fa XL |
40 | pub NONMINIMAL_BOOL, |
41 | complexity, | |
42 | "boolean expressions that can be written more concisely" | |
43 | } | |
44 | ||
45 | declare_clippy_lint! { | |
94222f64 XL |
46 | /// ### What it does |
47 | /// Checks for boolean expressions that contain terminals that | |
f20569fa XL |
48 | /// can be eliminated. |
49 | /// | |
94222f64 XL |
50 | /// ### Why is this bad? |
51 | /// This is most likely a logic bug. | |
f20569fa | 52 | /// |
94222f64 XL |
53 | /// ### Known problems |
54 | /// Ignores short circuiting behavior. | |
f20569fa | 55 | /// |
94222f64 | 56 | /// ### Example |
923072b8 FG |
57 | /// ```rust,ignore |
58 | /// // The `b` is unnecessary, the expression is equivalent to `if a`. | |
f20569fa XL |
59 | /// if a && b || a { ... } |
60 | /// ``` | |
923072b8 FG |
61 | /// |
62 | /// Use instead: | |
63 | /// ```rust,ignore | |
64 | /// if a {} | |
65 | /// ``` | |
a2a8927a | 66 | #[clippy::version = "pre 1.29.0"] |
f2b60f7d | 67 | pub OVERLY_COMPLEX_BOOL_EXPR, |
f20569fa XL |
68 | correctness, |
69 | "boolean expressions that contain terminals which can be eliminated" | |
70 | } | |
71 | ||
72 | // For each pairs, both orders are considered. | |
73 | const METHODS_WITH_NEGATION: [(&str, &str); 2] = [("is_some", "is_none"), ("is_err", "is_ok")]; | |
74 | ||
f2b60f7d | 75 | declare_lint_pass!(NonminimalBool => [NONMINIMAL_BOOL, OVERLY_COMPLEX_BOOL_EXPR]); |
f20569fa XL |
76 | |
77 | impl<'tcx> LateLintPass<'tcx> for NonminimalBool { | |
78 | fn check_fn( | |
79 | &mut self, | |
80 | cx: &LateContext<'tcx>, | |
81 | _: FnKind<'tcx>, | |
82 | _: &'tcx FnDecl<'_>, | |
83 | body: &'tcx Body<'_>, | |
84 | _: Span, | |
85 | _: HirId, | |
86 | ) { | |
17df50a5 | 87 | NonminimalBoolVisitor { cx }.visit_body(body); |
f20569fa XL |
88 | } |
89 | } | |
90 | ||
91 | struct NonminimalBoolVisitor<'a, 'tcx> { | |
92 | cx: &'a LateContext<'tcx>, | |
93 | } | |
94 | ||
95 | use quine_mc_cluskey::Bool; | |
96 | struct Hir2Qmm<'a, 'tcx, 'v> { | |
97 | terminals: Vec<&'v Expr<'v>>, | |
98 | cx: &'a LateContext<'tcx>, | |
99 | } | |
100 | ||
101 | impl<'a, 'tcx, 'v> Hir2Qmm<'a, 'tcx, 'v> { | |
102 | fn extract(&mut self, op: BinOpKind, a: &[&'v Expr<'_>], mut v: Vec<Bool>) -> Result<Vec<Bool>, String> { | |
103 | for a in a { | |
104 | if let ExprKind::Binary(binop, lhs, rhs) = &a.kind { | |
105 | if binop.node == op { | |
106 | v = self.extract(op, &[lhs, rhs], v)?; | |
107 | continue; | |
108 | } | |
109 | } | |
110 | v.push(self.run(a)?); | |
111 | } | |
112 | Ok(v) | |
113 | } | |
114 | ||
115 | fn run(&mut self, e: &'v Expr<'_>) -> Result<Bool, String> { | |
116 | fn negate(bin_op_kind: BinOpKind) -> Option<BinOpKind> { | |
117 | match bin_op_kind { | |
118 | BinOpKind::Eq => Some(BinOpKind::Ne), | |
119 | BinOpKind::Ne => Some(BinOpKind::Eq), | |
120 | BinOpKind::Gt => Some(BinOpKind::Le), | |
121 | BinOpKind::Ge => Some(BinOpKind::Lt), | |
122 | BinOpKind::Lt => Some(BinOpKind::Ge), | |
123 | BinOpKind::Le => Some(BinOpKind::Gt), | |
124 | _ => None, | |
125 | } | |
126 | } | |
127 | ||
128 | // prevent folding of `cfg!` macros and the like | |
129 | if !e.span.from_expansion() { | |
130 | match &e.kind { | |
94222f64 | 131 | ExprKind::Unary(UnOp::Not, inner) => return Ok(Bool::Not(Box::new(self.run(inner)?))), |
f20569fa XL |
132 | ExprKind::Binary(binop, lhs, rhs) => match &binop.node { |
133 | BinOpKind::Or => { | |
134 | return Ok(Bool::Or(self.extract(BinOpKind::Or, &[lhs, rhs], Vec::new())?)); | |
135 | }, | |
136 | BinOpKind::And => { | |
137 | return Ok(Bool::And(self.extract(BinOpKind::And, &[lhs, rhs], Vec::new())?)); | |
138 | }, | |
139 | _ => (), | |
140 | }, | |
141 | ExprKind::Lit(lit) => match lit.node { | |
142 | LitKind::Bool(true) => return Ok(Bool::True), | |
143 | LitKind::Bool(false) => return Ok(Bool::False), | |
144 | _ => (), | |
145 | }, | |
146 | _ => (), | |
147 | } | |
148 | } | |
149 | for (n, expr) in self.terminals.iter().enumerate() { | |
150 | if eq_expr_value(self.cx, e, expr) { | |
923072b8 | 151 | #[expect(clippy::cast_possible_truncation)] |
f20569fa XL |
152 | return Ok(Bool::Term(n as u8)); |
153 | } | |
154 | ||
155 | if_chain! { | |
156 | if let ExprKind::Binary(e_binop, e_lhs, e_rhs) = &e.kind; | |
157 | if implements_ord(self.cx, e_lhs); | |
158 | if let ExprKind::Binary(expr_binop, expr_lhs, expr_rhs) = &expr.kind; | |
159 | if negate(e_binop.node) == Some(expr_binop.node); | |
160 | if eq_expr_value(self.cx, e_lhs, expr_lhs); | |
161 | if eq_expr_value(self.cx, e_rhs, expr_rhs); | |
162 | then { | |
923072b8 | 163 | #[expect(clippy::cast_possible_truncation)] |
f20569fa XL |
164 | return Ok(Bool::Not(Box::new(Bool::Term(n as u8)))); |
165 | } | |
166 | } | |
167 | } | |
168 | let n = self.terminals.len(); | |
169 | self.terminals.push(e); | |
170 | if n < 32 { | |
923072b8 | 171 | #[expect(clippy::cast_possible_truncation)] |
f20569fa XL |
172 | Ok(Bool::Term(n as u8)) |
173 | } else { | |
174 | Err("too many literals".to_owned()) | |
175 | } | |
176 | } | |
177 | } | |
178 | ||
179 | struct SuggestContext<'a, 'tcx, 'v> { | |
180 | terminals: &'v [&'v Expr<'v>], | |
181 | cx: &'a LateContext<'tcx>, | |
182 | output: String, | |
183 | } | |
184 | ||
185 | impl<'a, 'tcx, 'v> SuggestContext<'a, 'tcx, 'v> { | |
186 | fn recurse(&mut self, suggestion: &Bool) -> Option<()> { | |
187 | use quine_mc_cluskey::Bool::{And, False, Not, Or, Term, True}; | |
188 | match suggestion { | |
189 | True => { | |
190 | self.output.push_str("true"); | |
191 | }, | |
192 | False => { | |
193 | self.output.push_str("false"); | |
194 | }, | |
195 | Not(inner) => match **inner { | |
196 | And(_) | Or(_) => { | |
197 | self.output.push('!'); | |
198 | self.output.push('('); | |
199 | self.recurse(inner); | |
200 | self.output.push(')'); | |
201 | }, | |
202 | Term(n) => { | |
203 | let terminal = self.terminals[n as usize]; | |
204 | if let Some(str) = simplify_not(self.cx, terminal) { | |
17df50a5 | 205 | self.output.push_str(&str); |
f20569fa XL |
206 | } else { |
207 | self.output.push('!'); | |
208 | let snip = snippet_opt(self.cx, terminal.span)?; | |
209 | self.output.push_str(&snip); | |
210 | } | |
211 | }, | |
212 | True | False | Not(_) => { | |
213 | self.output.push('!'); | |
214 | self.recurse(inner)?; | |
215 | }, | |
216 | }, | |
217 | And(v) => { | |
218 | for (index, inner) in v.iter().enumerate() { | |
219 | if index > 0 { | |
220 | self.output.push_str(" && "); | |
221 | } | |
222 | if let Or(_) = *inner { | |
223 | self.output.push('('); | |
224 | self.recurse(inner); | |
225 | self.output.push(')'); | |
226 | } else { | |
227 | self.recurse(inner); | |
228 | } | |
229 | } | |
230 | }, | |
231 | Or(v) => { | |
232 | for (index, inner) in v.iter().rev().enumerate() { | |
233 | if index > 0 { | |
234 | self.output.push_str(" || "); | |
235 | } | |
236 | self.recurse(inner); | |
237 | } | |
238 | }, | |
239 | &Term(n) => { | |
240 | let snip = snippet_opt(self.cx, self.terminals[n as usize].span)?; | |
241 | self.output.push_str(&snip); | |
242 | }, | |
243 | } | |
244 | Some(()) | |
245 | } | |
246 | } | |
247 | ||
248 | fn simplify_not(cx: &LateContext<'_>, expr: &Expr<'_>) -> Option<String> { | |
249 | match &expr.kind { | |
250 | ExprKind::Binary(binop, lhs, rhs) => { | |
251 | if !implements_ord(cx, lhs) { | |
252 | return None; | |
253 | } | |
254 | ||
255 | match binop.node { | |
256 | BinOpKind::Eq => Some(" != "), | |
257 | BinOpKind::Ne => Some(" == "), | |
258 | BinOpKind::Lt => Some(" >= "), | |
259 | BinOpKind::Gt => Some(" <= "), | |
260 | BinOpKind::Le => Some(" > "), | |
261 | BinOpKind::Ge => Some(" < "), | |
262 | _ => None, | |
263 | } | |
264 | .and_then(|op| { | |
265 | Some(format!( | |
266 | "{}{}{}", | |
267 | snippet_opt(cx, lhs.span)?, | |
268 | op, | |
269 | snippet_opt(cx, rhs.span)? | |
270 | )) | |
271 | }) | |
272 | }, | |
f2b60f7d FG |
273 | ExprKind::MethodCall(path, receiver, [], _) => { |
274 | let type_of_receiver = cx.typeck_results().expr_ty(receiver); | |
c295e0f8 XL |
275 | if !is_type_diagnostic_item(cx, type_of_receiver, sym::Option) |
276 | && !is_type_diagnostic_item(cx, type_of_receiver, sym::Result) | |
f20569fa XL |
277 | { |
278 | return None; | |
279 | } | |
280 | METHODS_WITH_NEGATION | |
281 | .iter() | |
cdc7bbd5 | 282 | .copied() |
f20569fa XL |
283 | .flat_map(|(a, b)| vec![(a, b), (b, a)]) |
284 | .find(|&(a, _)| { | |
a2a8927a | 285 | let path: &str = path.ident.name.as_str(); |
f20569fa XL |
286 | a == path |
287 | }) | |
f2b60f7d | 288 | .and_then(|(_, neg_method)| Some(format!("{}.{}()", snippet_opt(cx, receiver.span)?, neg_method))) |
f20569fa XL |
289 | }, |
290 | _ => None, | |
291 | } | |
292 | } | |
293 | ||
294 | fn suggest(cx: &LateContext<'_>, suggestion: &Bool, terminals: &[&Expr<'_>]) -> String { | |
295 | let mut suggest_context = SuggestContext { | |
296 | terminals, | |
297 | cx, | |
298 | output: String::new(), | |
299 | }; | |
300 | suggest_context.recurse(suggestion); | |
301 | suggest_context.output | |
302 | } | |
303 | ||
304 | fn simple_negate(b: Bool) -> Bool { | |
305 | use quine_mc_cluskey::Bool::{And, False, Not, Or, Term, True}; | |
306 | match b { | |
307 | True => False, | |
308 | False => True, | |
309 | t @ Term(_) => Not(Box::new(t)), | |
310 | And(mut v) => { | |
311 | for el in &mut v { | |
312 | *el = simple_negate(::std::mem::replace(el, True)); | |
313 | } | |
314 | Or(v) | |
315 | }, | |
316 | Or(mut v) => { | |
317 | for el in &mut v { | |
318 | *el = simple_negate(::std::mem::replace(el, True)); | |
319 | } | |
320 | And(v) | |
321 | }, | |
322 | Not(inner) => *inner, | |
323 | } | |
324 | } | |
325 | ||
326 | #[derive(Default)] | |
327 | struct Stats { | |
328 | terminals: [usize; 32], | |
329 | negations: usize, | |
330 | ops: usize, | |
331 | } | |
332 | ||
333 | fn terminal_stats(b: &Bool) -> Stats { | |
334 | fn recurse(b: &Bool, stats: &mut Stats) { | |
335 | match b { | |
336 | True | False => stats.ops += 1, | |
337 | Not(inner) => { | |
338 | match **inner { | |
339 | And(_) | Or(_) => stats.ops += 1, // brackets are also operations | |
340 | _ => stats.negations += 1, | |
341 | } | |
342 | recurse(inner, stats); | |
343 | }, | |
344 | And(v) | Or(v) => { | |
345 | stats.ops += v.len() - 1; | |
346 | for inner in v { | |
347 | recurse(inner, stats); | |
348 | } | |
349 | }, | |
350 | &Term(n) => stats.terminals[n as usize] += 1, | |
351 | } | |
352 | } | |
353 | use quine_mc_cluskey::Bool::{And, False, Not, Or, Term, True}; | |
354 | let mut stats = Stats::default(); | |
355 | recurse(b, &mut stats); | |
356 | stats | |
357 | } | |
358 | ||
359 | impl<'a, 'tcx> NonminimalBoolVisitor<'a, 'tcx> { | |
360 | fn bool_expr(&self, e: &'tcx Expr<'_>) { | |
361 | let mut h2q = Hir2Qmm { | |
362 | terminals: Vec::new(), | |
363 | cx: self.cx, | |
364 | }; | |
365 | if let Ok(expr) = h2q.run(e) { | |
366 | if h2q.terminals.len() > 8 { | |
367 | // QMC has exponentially slow behavior as the number of terminals increases | |
368 | // 8 is reasonable, it takes approximately 0.2 seconds. | |
369 | // See #825 | |
370 | return; | |
371 | } | |
372 | ||
373 | let stats = terminal_stats(&expr); | |
374 | let mut simplified = expr.simplify(); | |
375 | for simple in Bool::Not(Box::new(expr)).simplify() { | |
376 | match simple { | |
377 | Bool::Not(_) | Bool::True | Bool::False => {}, | |
378 | _ => simplified.push(Bool::Not(Box::new(simple.clone()))), | |
379 | } | |
380 | let simple_negated = simple_negate(simple); | |
381 | if simplified.iter().any(|s| *s == simple_negated) { | |
382 | continue; | |
383 | } | |
384 | simplified.push(simple_negated); | |
385 | } | |
386 | let mut improvements = Vec::with_capacity(simplified.len()); | |
387 | 'simplified: for suggestion in &simplified { | |
388 | let simplified_stats = terminal_stats(suggestion); | |
389 | let mut improvement = false; | |
390 | for i in 0..32 { | |
391 | // ignore any "simplifications" that end up requiring a terminal more often | |
392 | // than in the original expression | |
393 | if stats.terminals[i] < simplified_stats.terminals[i] { | |
394 | continue 'simplified; | |
395 | } | |
396 | if stats.terminals[i] != 0 && simplified_stats.terminals[i] == 0 { | |
064997fb | 397 | span_lint_hir_and_then( |
f20569fa | 398 | self.cx, |
f2b60f7d | 399 | OVERLY_COMPLEX_BOOL_EXPR, |
064997fb | 400 | e.hir_id, |
f20569fa XL |
401 | e.span, |
402 | "this boolean expression contains a logic bug", | |
403 | |diag| { | |
404 | diag.span_help( | |
405 | h2q.terminals[i].span, | |
406 | "this expression can be optimized out by applying boolean operations to the \ | |
407 | outer expression", | |
408 | ); | |
409 | diag.span_suggestion( | |
410 | e.span, | |
411 | "it would look like the following", | |
412 | suggest(self.cx, suggestion, &h2q.terminals), | |
413 | // nonminimal_bool can produce minimal but | |
414 | // not human readable expressions (#3141) | |
415 | Applicability::Unspecified, | |
416 | ); | |
417 | }, | |
418 | ); | |
419 | // don't also lint `NONMINIMAL_BOOL` | |
420 | return; | |
421 | } | |
422 | // if the number of occurrences of a terminal decreases or any of the stats | |
423 | // decreases while none increases | |
424 | improvement |= (stats.terminals[i] > simplified_stats.terminals[i]) | |
425 | || (stats.negations > simplified_stats.negations && stats.ops == simplified_stats.ops) | |
426 | || (stats.ops > simplified_stats.ops && stats.negations == simplified_stats.negations); | |
427 | } | |
428 | if improvement { | |
429 | improvements.push(suggestion); | |
430 | } | |
431 | } | |
432 | let nonminimal_bool_lint = |suggestions: Vec<_>| { | |
064997fb | 433 | span_lint_hir_and_then( |
f20569fa XL |
434 | self.cx, |
435 | NONMINIMAL_BOOL, | |
064997fb | 436 | e.hir_id, |
f20569fa XL |
437 | e.span, |
438 | "this boolean expression can be simplified", | |
439 | |diag| { | |
440 | diag.span_suggestions( | |
441 | e.span, | |
442 | "try", | |
443 | suggestions.into_iter(), | |
444 | // nonminimal_bool can produce minimal but | |
445 | // not human readable expressions (#3141) | |
446 | Applicability::Unspecified, | |
447 | ); | |
448 | }, | |
449 | ); | |
450 | }; | |
451 | if improvements.is_empty() { | |
452 | let mut visitor = NotSimplificationVisitor { cx: self.cx }; | |
453 | visitor.visit_expr(e); | |
454 | } else { | |
455 | nonminimal_bool_lint( | |
456 | improvements | |
457 | .into_iter() | |
458 | .map(|suggestion| suggest(self.cx, suggestion, &h2q.terminals)) | |
459 | .collect(), | |
460 | ); | |
461 | } | |
462 | } | |
463 | } | |
464 | } | |
465 | ||
466 | impl<'a, 'tcx> Visitor<'tcx> for NonminimalBoolVisitor<'a, 'tcx> { | |
f20569fa | 467 | fn visit_expr(&mut self, e: &'tcx Expr<'_>) { |
a2a8927a XL |
468 | if !e.span.from_expansion() { |
469 | match &e.kind { | |
470 | ExprKind::Binary(binop, _, _) if binop.node == BinOpKind::Or || binop.node == BinOpKind::And => { | |
f20569fa | 471 | self.bool_expr(e); |
a2a8927a XL |
472 | }, |
473 | ExprKind::Unary(UnOp::Not, inner) => { | |
474 | if self.cx.typeck_results().node_types()[inner.hir_id].is_bool() { | |
475 | self.bool_expr(e); | |
476 | } | |
477 | }, | |
478 | _ => {}, | |
479 | } | |
f20569fa | 480 | } |
a2a8927a | 481 | walk_expr(self, e); |
f20569fa | 482 | } |
f20569fa XL |
483 | } |
484 | ||
485 | fn implements_ord<'tcx>(cx: &LateContext<'tcx>, expr: &Expr<'_>) -> bool { | |
486 | let ty = cx.typeck_results().expr_ty(expr); | |
487 | get_trait_def_id(cx, &paths::ORD).map_or(false, |id| implements_trait(cx, ty, id, &[])) | |
488 | } | |
489 | ||
490 | struct NotSimplificationVisitor<'a, 'tcx> { | |
491 | cx: &'a LateContext<'tcx>, | |
492 | } | |
493 | ||
494 | impl<'a, 'tcx> Visitor<'tcx> for NotSimplificationVisitor<'a, 'tcx> { | |
f20569fa XL |
495 | fn visit_expr(&mut self, expr: &'tcx Expr<'_>) { |
496 | if let ExprKind::Unary(UnOp::Not, inner) = &expr.kind { | |
497 | if let Some(suggestion) = simplify_not(self.cx, inner) { | |
498 | span_lint_and_sugg( | |
499 | self.cx, | |
500 | NONMINIMAL_BOOL, | |
501 | expr.span, | |
502 | "this boolean expression can be simplified", | |
503 | "try", | |
504 | suggestion, | |
505 | Applicability::MachineApplicable, | |
506 | ); | |
507 | } | |
508 | } | |
509 | ||
510 | walk_expr(self, expr); | |
511 | } | |
f20569fa | 512 | } |