]>
Commit | Line | Data |
---|---|---|
064997fb | 1 | use clippy_utils::diagnostics::{span_lint_and_sugg, span_lint_hir_and_then}; |
2b03887a | 2 | use clippy_utils::eq_expr_value; |
cdc7bbd5 XL |
3 | use clippy_utils::source::snippet_opt; |
4 | use clippy_utils::ty::{implements_trait, is_type_diagnostic_item}; | |
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}; |
9ffffee4 | 9 | use rustc_hir::{BinOpKind, Body, Expr, ExprKind, FnDecl, UnOp}; |
f20569fa | 10 | use rustc_lint::{LateContext, LateLintPass}; |
f20569fa | 11 | use rustc_session::{declare_lint_pass, declare_tool_lint}; |
9ffffee4 | 12 | use rustc_span::def_id::LocalDefId; |
f20569fa XL |
13 | use rustc_span::source_map::Span; |
14 | use rustc_span::sym; | |
15 | ||
16 | declare_clippy_lint! { | |
94222f64 XL |
17 | /// ### What it does |
18 | /// Checks for boolean expressions that can be written more | |
f20569fa XL |
19 | /// concisely. |
20 | /// | |
94222f64 XL |
21 | /// ### Why is this bad? |
22 | /// Readability of boolean expressions suffers from | |
f20569fa XL |
23 | /// unnecessary duplication. |
24 | /// | |
94222f64 XL |
25 | /// ### Known problems |
26 | /// Ignores short circuiting behavior of `||` and | |
f20569fa XL |
27 | /// `&&`. Ignores `|`, `&` and `^`. |
28 | /// | |
94222f64 | 29 | /// ### Example |
f20569fa | 30 | /// ```ignore |
923072b8 FG |
31 | /// if a && true {} |
32 | /// if !(a == b) {} | |
33 | /// ``` | |
34 | /// | |
35 | /// Use instead: | |
36 | /// ```rust,ignore | |
37 | /// if a {} | |
38 | /// if a != b {} | |
f20569fa | 39 | /// ``` |
a2a8927a | 40 | #[clippy::version = "pre 1.29.0"] |
f20569fa XL |
41 | pub NONMINIMAL_BOOL, |
42 | complexity, | |
43 | "boolean expressions that can be written more concisely" | |
44 | } | |
45 | ||
46 | declare_clippy_lint! { | |
94222f64 XL |
47 | /// ### What it does |
48 | /// Checks for boolean expressions that contain terminals that | |
f20569fa XL |
49 | /// can be eliminated. |
50 | /// | |
94222f64 XL |
51 | /// ### Why is this bad? |
52 | /// This is most likely a logic bug. | |
f20569fa | 53 | /// |
94222f64 XL |
54 | /// ### Known problems |
55 | /// Ignores short circuiting behavior. | |
f20569fa | 56 | /// |
94222f64 | 57 | /// ### Example |
923072b8 FG |
58 | /// ```rust,ignore |
59 | /// // The `b` is unnecessary, the expression is equivalent to `if a`. | |
f20569fa XL |
60 | /// if a && b || a { ... } |
61 | /// ``` | |
923072b8 FG |
62 | /// |
63 | /// Use instead: | |
64 | /// ```rust,ignore | |
65 | /// if a {} | |
66 | /// ``` | |
a2a8927a | 67 | #[clippy::version = "pre 1.29.0"] |
f2b60f7d | 68 | pub OVERLY_COMPLEX_BOOL_EXPR, |
f20569fa XL |
69 | correctness, |
70 | "boolean expressions that contain terminals which can be eliminated" | |
71 | } | |
72 | ||
73 | // For each pairs, both orders are considered. | |
74 | const METHODS_WITH_NEGATION: [(&str, &str); 2] = [("is_some", "is_none"), ("is_err", "is_ok")]; | |
75 | ||
f2b60f7d | 76 | declare_lint_pass!(NonminimalBool => [NONMINIMAL_BOOL, OVERLY_COMPLEX_BOOL_EXPR]); |
f20569fa XL |
77 | |
78 | impl<'tcx> LateLintPass<'tcx> for NonminimalBool { | |
79 | fn check_fn( | |
80 | &mut self, | |
81 | cx: &LateContext<'tcx>, | |
82 | _: FnKind<'tcx>, | |
83 | _: &'tcx FnDecl<'_>, | |
84 | body: &'tcx Body<'_>, | |
85 | _: Span, | |
9ffffee4 | 86 | _: LocalDefId, |
f20569fa | 87 | ) { |
17df50a5 | 88 | NonminimalBoolVisitor { cx }.visit_body(body); |
f20569fa XL |
89 | } |
90 | } | |
91 | ||
92 | struct NonminimalBoolVisitor<'a, 'tcx> { | |
93 | cx: &'a LateContext<'tcx>, | |
94 | } | |
95 | ||
96 | use quine_mc_cluskey::Bool; | |
97 | struct Hir2Qmm<'a, 'tcx, 'v> { | |
98 | terminals: Vec<&'v Expr<'v>>, | |
99 | cx: &'a LateContext<'tcx>, | |
100 | } | |
101 | ||
102 | impl<'a, 'tcx, 'v> Hir2Qmm<'a, 'tcx, 'v> { | |
103 | fn extract(&mut self, op: BinOpKind, a: &[&'v Expr<'_>], mut v: Vec<Bool>) -> Result<Vec<Bool>, String> { | |
104 | for a in a { | |
105 | if let ExprKind::Binary(binop, lhs, rhs) = &a.kind { | |
106 | if binop.node == op { | |
107 | v = self.extract(op, &[lhs, rhs], v)?; | |
108 | continue; | |
109 | } | |
110 | } | |
111 | v.push(self.run(a)?); | |
112 | } | |
113 | Ok(v) | |
114 | } | |
115 | ||
116 | fn run(&mut self, e: &'v Expr<'_>) -> Result<Bool, String> { | |
117 | fn negate(bin_op_kind: BinOpKind) -> Option<BinOpKind> { | |
118 | match bin_op_kind { | |
119 | BinOpKind::Eq => Some(BinOpKind::Ne), | |
120 | BinOpKind::Ne => Some(BinOpKind::Eq), | |
121 | BinOpKind::Gt => Some(BinOpKind::Le), | |
122 | BinOpKind::Ge => Some(BinOpKind::Lt), | |
123 | BinOpKind::Lt => Some(BinOpKind::Ge), | |
124 | BinOpKind::Le => Some(BinOpKind::Gt), | |
125 | _ => None, | |
126 | } | |
127 | } | |
128 | ||
129 | // prevent folding of `cfg!` macros and the like | |
130 | if !e.span.from_expansion() { | |
131 | match &e.kind { | |
94222f64 | 132 | ExprKind::Unary(UnOp::Not, inner) => return Ok(Bool::Not(Box::new(self.run(inner)?))), |
f20569fa XL |
133 | ExprKind::Binary(binop, lhs, rhs) => match &binop.node { |
134 | BinOpKind::Or => { | |
135 | return Ok(Bool::Or(self.extract(BinOpKind::Or, &[lhs, rhs], Vec::new())?)); | |
136 | }, | |
137 | BinOpKind::And => { | |
138 | return Ok(Bool::And(self.extract(BinOpKind::And, &[lhs, rhs], Vec::new())?)); | |
139 | }, | |
140 | _ => (), | |
141 | }, | |
142 | ExprKind::Lit(lit) => match lit.node { | |
143 | LitKind::Bool(true) => return Ok(Bool::True), | |
144 | LitKind::Bool(false) => return Ok(Bool::False), | |
145 | _ => (), | |
146 | }, | |
147 | _ => (), | |
148 | } | |
149 | } | |
150 | for (n, expr) in self.terminals.iter().enumerate() { | |
151 | if eq_expr_value(self.cx, e, expr) { | |
923072b8 | 152 | #[expect(clippy::cast_possible_truncation)] |
f20569fa XL |
153 | return Ok(Bool::Term(n as u8)); |
154 | } | |
155 | ||
156 | if_chain! { | |
157 | if let ExprKind::Binary(e_binop, e_lhs, e_rhs) = &e.kind; | |
158 | if implements_ord(self.cx, e_lhs); | |
159 | if let ExprKind::Binary(expr_binop, expr_lhs, expr_rhs) = &expr.kind; | |
160 | if negate(e_binop.node) == Some(expr_binop.node); | |
161 | if eq_expr_value(self.cx, e_lhs, expr_lhs); | |
162 | if eq_expr_value(self.cx, e_rhs, expr_rhs); | |
163 | then { | |
923072b8 | 164 | #[expect(clippy::cast_possible_truncation)] |
f20569fa XL |
165 | return Ok(Bool::Not(Box::new(Bool::Term(n as u8)))); |
166 | } | |
167 | } | |
168 | } | |
169 | let n = self.terminals.len(); | |
170 | self.terminals.push(e); | |
171 | if n < 32 { | |
923072b8 | 172 | #[expect(clippy::cast_possible_truncation)] |
f20569fa XL |
173 | Ok(Bool::Term(n as u8)) |
174 | } else { | |
175 | Err("too many literals".to_owned()) | |
176 | } | |
177 | } | |
178 | } | |
179 | ||
180 | struct SuggestContext<'a, 'tcx, 'v> { | |
181 | terminals: &'v [&'v Expr<'v>], | |
182 | cx: &'a LateContext<'tcx>, | |
183 | output: String, | |
184 | } | |
185 | ||
186 | impl<'a, 'tcx, 'v> SuggestContext<'a, 'tcx, 'v> { | |
187 | fn recurse(&mut self, suggestion: &Bool) -> Option<()> { | |
188 | use quine_mc_cluskey::Bool::{And, False, Not, Or, Term, True}; | |
189 | match suggestion { | |
190 | True => { | |
191 | self.output.push_str("true"); | |
192 | }, | |
193 | False => { | |
194 | self.output.push_str("false"); | |
195 | }, | |
196 | Not(inner) => match **inner { | |
197 | And(_) | Or(_) => { | |
198 | self.output.push('!'); | |
199 | self.output.push('('); | |
200 | self.recurse(inner); | |
201 | self.output.push(')'); | |
202 | }, | |
203 | Term(n) => { | |
204 | let terminal = self.terminals[n as usize]; | |
205 | if let Some(str) = simplify_not(self.cx, terminal) { | |
17df50a5 | 206 | self.output.push_str(&str); |
f20569fa XL |
207 | } else { |
208 | self.output.push('!'); | |
209 | let snip = snippet_opt(self.cx, terminal.span)?; | |
210 | self.output.push_str(&snip); | |
211 | } | |
212 | }, | |
213 | True | False | Not(_) => { | |
214 | self.output.push('!'); | |
215 | self.recurse(inner)?; | |
216 | }, | |
217 | }, | |
218 | And(v) => { | |
219 | for (index, inner) in v.iter().enumerate() { | |
220 | if index > 0 { | |
221 | self.output.push_str(" && "); | |
222 | } | |
223 | if let Or(_) = *inner { | |
224 | self.output.push('('); | |
225 | self.recurse(inner); | |
226 | self.output.push(')'); | |
227 | } else { | |
228 | self.recurse(inner); | |
229 | } | |
230 | } | |
231 | }, | |
232 | Or(v) => { | |
233 | for (index, inner) in v.iter().rev().enumerate() { | |
234 | if index > 0 { | |
235 | self.output.push_str(" || "); | |
236 | } | |
237 | self.recurse(inner); | |
238 | } | |
239 | }, | |
240 | &Term(n) => { | |
2b03887a | 241 | let snip = snippet_opt(self.cx, self.terminals[n as usize].span.source_callsite())?; |
f20569fa XL |
242 | self.output.push_str(&snip); |
243 | }, | |
244 | } | |
245 | Some(()) | |
246 | } | |
247 | } | |
248 | ||
249 | fn simplify_not(cx: &LateContext<'_>, expr: &Expr<'_>) -> Option<String> { | |
250 | match &expr.kind { | |
251 | ExprKind::Binary(binop, lhs, rhs) => { | |
252 | if !implements_ord(cx, lhs) { | |
253 | return None; | |
254 | } | |
255 | ||
256 | match binop.node { | |
257 | BinOpKind::Eq => Some(" != "), | |
258 | BinOpKind::Ne => Some(" == "), | |
259 | BinOpKind::Lt => Some(" >= "), | |
260 | BinOpKind::Gt => Some(" <= "), | |
261 | BinOpKind::Le => Some(" > "), | |
262 | BinOpKind::Ge => Some(" < "), | |
263 | _ => None, | |
264 | } | |
265 | .and_then(|op| { | |
266 | Some(format!( | |
2b03887a | 267 | "{}{op}{}", |
f20569fa | 268 | snippet_opt(cx, lhs.span)?, |
f20569fa XL |
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 | }) | |
2b03887a | 288 | .and_then(|(_, neg_method)| Some(format!("{}.{neg_method}()", snippet_opt(cx, receiver.span)?))) |
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 | ||
487cf647 | 485 | fn implements_ord(cx: &LateContext<'_>, expr: &Expr<'_>) -> bool { |
f20569fa | 486 | let ty = cx.typeck_results().expr_ty(expr); |
2b03887a FG |
487 | cx.tcx |
488 | .get_diagnostic_item(sym::Ord) | |
489 | .map_or(false, |id| implements_trait(cx, ty, id, &[])) | |
f20569fa XL |
490 | } |
491 | ||
492 | struct NotSimplificationVisitor<'a, 'tcx> { | |
493 | cx: &'a LateContext<'tcx>, | |
494 | } | |
495 | ||
496 | impl<'a, 'tcx> Visitor<'tcx> for NotSimplificationVisitor<'a, 'tcx> { | |
f20569fa XL |
497 | fn visit_expr(&mut self, expr: &'tcx Expr<'_>) { |
498 | if let ExprKind::Unary(UnOp::Not, inner) = &expr.kind { | |
499 | if let Some(suggestion) = simplify_not(self.cx, inner) { | |
500 | span_lint_and_sugg( | |
501 | self.cx, | |
502 | NONMINIMAL_BOOL, | |
503 | expr.span, | |
504 | "this boolean expression can be simplified", | |
505 | "try", | |
506 | suggestion, | |
507 | Applicability::MachineApplicable, | |
508 | ); | |
509 | } | |
510 | } | |
511 | ||
512 | walk_expr(self, expr); | |
513 | } | |
f20569fa | 514 | } |