src/tools/clippy/clippy_lints/src/unnested_or_patterns.rs

   1 #![allow(clippy::wildcard_imports, clippy::enum_glob_use)]
   2
   3 use clippy_utils::ast_utils::{eq_field_pat, eq_id, eq_maybe_qself, eq_pat, eq_path};
   4 use clippy_utils::diagnostics::span_lint_and_then;
   5 use clippy_utils::msrvs::{self, Msrv};
   6 use clippy_utils::over;
   7 use rustc_ast::mut_visit::*;
   8 use rustc_ast::ptr::P;
   9 use rustc_ast::{self as ast, Mutability, Pat, PatKind, PatKind::*, DUMMY_NODE_ID};
  10 use rustc_ast_pretty::pprust;
  11 use rustc_errors::Applicability;
  12 use rustc_lint::{EarlyContext, EarlyLintPass};
  13 use rustc_session::{declare_tool_lint, impl_lint_pass};
  14 use rustc_span::DUMMY_SP;
  15 use std::cell::Cell;
  16 use std::mem;
  17 use thin_vec::{thin_vec, ThinVec};
  18
  19 declare_clippy_lint! {
  20     /// ### What it does
  21     /// Checks for unnested or-patterns, e.g., `Some(0) | Some(2)` and
  22     /// suggests replacing the pattern with a nested one, `Some(0 | 2)`.
  23     ///
  24     /// Another way to think of this is that it rewrites patterns in
  25     /// *disjunctive normal form (DNF)* into *conjunctive normal form (CNF)*.
  26     ///
  27     /// ### Why is this bad?
  28     /// In the example above, `Some` is repeated, which unnecessarily complicates the pattern.
  29     ///
  30     /// ### Example
  31     /// ```rust
  32     /// fn main() {
  33     ///     if let Some(0) | Some(2) = Some(0) {}
  34     /// }
  35     /// ```
  36     /// Use instead:
  37     /// ```rust
  38     /// fn main() {
  39     ///     if let Some(0 | 2) = Some(0) {}
  40     /// }
  41     /// ```
  42     #[clippy::version = "1.46.0"]
  43     pub UNNESTED_OR_PATTERNS,
  44     pedantic,
  45     "unnested or-patterns, e.g., `Foo(Bar) | Foo(Baz) instead of `Foo(Bar | Baz)`"
  46 }
  47
  48 pub struct UnnestedOrPatterns {
  49     msrv: Msrv,
  50 }
  51
  52 impl UnnestedOrPatterns {
  53     #[must_use]
  54     pub fn new(msrv: Msrv) -> Self {
  55         Self { msrv }
  56     }
  57 }
  58
  59 impl_lint_pass!(UnnestedOrPatterns => [UNNESTED_OR_PATTERNS]);
  60
  61 impl EarlyLintPass for UnnestedOrPatterns {
  62     fn check_arm(&mut self, cx: &EarlyContext<'_>, a: &ast::Arm) {
  63         if self.msrv.meets(msrvs::OR_PATTERNS) {
  64             lint_unnested_or_patterns(cx, &a.pat);
  65         }
  66     }
  67
  68     fn check_expr(&mut self, cx: &EarlyContext<'_>, e: &ast::Expr) {
  69         if self.msrv.meets(msrvs::OR_PATTERNS) {
  70             if let ast::ExprKind::Let(pat, _, _) = &e.kind {
  71                 lint_unnested_or_patterns(cx, pat);
  72             }
  73         }
  74     }
  75
  76     fn check_param(&mut self, cx: &EarlyContext<'_>, p: &ast::Param) {
  77         if self.msrv.meets(msrvs::OR_PATTERNS) {
  78             lint_unnested_or_patterns(cx, &p.pat);
  79         }
  80     }
  81
  82     fn check_local(&mut self, cx: &EarlyContext<'_>, l: &ast::Local) {
  83         if self.msrv.meets(msrvs::OR_PATTERNS) {
  84             lint_unnested_or_patterns(cx, &l.pat);
  85         }
  86     }
  87
  88     extract_msrv_attr!(EarlyContext);
  89 }
  90
  91 fn lint_unnested_or_patterns(cx: &EarlyContext<'_>, pat: &Pat) {
  92     if let Ident(.., None) | Lit(_) | Wild | Path(..) | Range(..) | Rest | MacCall(_) = pat.kind {
  93         // This is a leaf pattern, so cloning is unprofitable.
  94         return;
  95     }
  96
  97     let mut pat = P(pat.clone());
  98
  99     // Nix all the paren patterns everywhere so that they aren't in our way.
 100     remove_all_parens(&mut pat);
 101
 102     // Transform all unnested or-patterns into nested ones, and if there were none, quit.
 103     if !unnest_or_patterns(&mut pat) {
 104         return;
 105     }
 106
 107     span_lint_and_then(cx, UNNESTED_OR_PATTERNS, pat.span, "unnested or-patterns", |db| {
 108         insert_necessary_parens(&mut pat);
 109         db.span_suggestion_verbose(
 110             pat.span,
 111             "nest the patterns",
 112             pprust::pat_to_string(&pat),
 113             Applicability::MachineApplicable,
 114         );
 115     });
 116 }
 117
 118 /// Remove all `(p)` patterns in `pat`.
 119 fn remove_all_parens(pat: &mut P<Pat>) {
 120     struct Visitor;
 121     impl MutVisitor for Visitor {
 122         fn visit_pat(&mut self, pat: &mut P<Pat>) {
 123             noop_visit_pat(pat, self);
 124             let inner = match &mut pat.kind {
 125                 Paren(i) => mem::replace(&mut i.kind, Wild),
 126                 _ => return,
 127             };
 128             pat.kind = inner;
 129         }
 130     }
 131     Visitor.visit_pat(pat);
 132 }
 133
 134 /// Insert parens where necessary according to Rust's precedence rules for patterns.
 135 fn insert_necessary_parens(pat: &mut P<Pat>) {
 136     struct Visitor;
 137     impl MutVisitor for Visitor {
 138         fn visit_pat(&mut self, pat: &mut P<Pat>) {
 139             use ast::BindingAnnotation;
 140             noop_visit_pat(pat, self);
 141             let target = match &mut pat.kind {
 142                 // `i @ a | b`, `box a | b`, and `& mut? a | b`.
 143                 Ident(.., Some(p)) | Box(p) | Ref(p, _) if matches!(&p.kind, Or(ps) if ps.len() > 1) => p,
 144                 Ref(p, Mutability::Not) if matches!(p.kind, Ident(BindingAnnotation::MUT, ..)) => p, // `&(mut x)`
 145                 _ => return,
 146             };
 147             target.kind = Paren(P(take_pat(target)));
 148         }
 149     }
 150     Visitor.visit_pat(pat);
 151 }
 152
 153 /// Unnest or-patterns `p0 | ... | p1` in the pattern `pat`.
 154 /// For example, this would transform `Some(0) | FOO | Some(2)` into `Some(0 | 2) | FOO`.
 155 fn unnest_or_patterns(pat: &mut P<Pat>) -> bool {
 156     struct Visitor {
 157         changed: bool,
 158     }
 159     impl MutVisitor for Visitor {
 160         fn visit_pat(&mut self, p: &mut P<Pat>) {
 161             // This is a bottom up transformation, so recurse first.
 162             noop_visit_pat(p, self);
 163
 164             // Don't have an or-pattern? Just quit early on.
 165             let Or(alternatives) = &mut p.kind else {
 166                 return
 167             };
 168
 169             // Collapse or-patterns directly nested in or-patterns.
 170             let mut idx = 0;
 171             let mut this_level_changed = false;
 172             while idx < alternatives.len() {
 173                 let inner = if let Or(ps) = &mut alternatives[idx].kind {
 174                     mem::take(ps)
 175                 } else {
 176                     idx += 1;
 177                     continue;
 178                 };
 179                 this_level_changed = true;
 180                 alternatives.splice(idx..=idx, inner);
 181             }
 182
 183             // Focus on `p_n` and then try to transform all `p_i` where `i > n`.
 184             let mut focus_idx = 0;
 185             while focus_idx < alternatives.len() {
 186                 this_level_changed |= transform_with_focus_on_idx(alternatives, focus_idx);
 187                 focus_idx += 1;
 188             }
 189             self.changed |= this_level_changed;
 190
 191             // Deal with `Some(Some(0)) | Some(Some(1))`.
 192             if this_level_changed {
 193                 noop_visit_pat(p, self);
 194             }
 195         }
 196     }
 197
 198     let mut visitor = Visitor { changed: false };
 199     visitor.visit_pat(pat);
 200     visitor.changed
 201 }
 202
 203 /// Match `$scrutinee` against `$pat` and extract `$then` from it.
 204 /// Panics if there is no match.
 205 macro_rules! always_pat {
 206     ($scrutinee:expr, $pat:pat => $then:expr) => {
 207         match $scrutinee {
 208             $pat => $then,
 209             _ => unreachable!(),
 210         }
 211     };
 212 }
 213
 214 /// Focus on `focus_idx` in `alternatives`,
 215 /// attempting to extend it with elements of the same constructor `C`
 216 /// in `alternatives[focus_idx + 1..]`.
 217 fn transform_with_focus_on_idx(alternatives: &mut ThinVec<P<Pat>>, focus_idx: usize) -> bool {
 218     // Extract the kind; we'll need to make some changes in it.
 219     let mut focus_kind = mem::replace(&mut alternatives[focus_idx].kind, PatKind::Wild);
 220     // We'll focus on `alternatives[focus_idx]`,
 221     // so we're draining from `alternatives[focus_idx + 1..]`.
 222     let start = focus_idx + 1;
 223
 224     // We're trying to find whatever kind (~"constructor") we found in `alternatives[start..]`.
 225     let changed = match &mut focus_kind {
 226         // These pattern forms are "leafs" and do not have sub-patterns.
 227         // Therefore they are not some form of constructor `C`,
 228         // with which a pattern `C(p_0)` may be formed,
 229         // which we would want to join with other `C(p_j)`s.
 230         Ident(.., None) | Lit(_) | Wild | Path(..) | Range(..) | Rest | MacCall(_)
 231         // Skip immutable refs, as grouping them saves few characters,
 232         // and almost always requires adding parens (increasing noisiness).
 233         // In the case of only two patterns, replacement adds net characters.
 234         | Ref(_, Mutability::Not)
 235         // Dealt with elsewhere.
 236         | Or(_) | Paren(_) => false,
 237         // Transform `box x | ... | box y` into `box (x | y)`.
 238         //
 239         // The cases below until `Slice(...)` deal with *singleton* products.
 240         // These patterns have the shape `C(p)`, and not e.g., `C(p0, ..., pn)`.
 241         Box(target) => extend_with_matching(
 242             target, start, alternatives,
 243             |k| matches!(k, Box(_)),
 244             |k| always_pat!(k, Box(p) => p),
 245         ),
 246         // Transform `&mut x | ... | &mut y` into `&mut (x | y)`.
 247         Ref(target, Mutability::Mut) => extend_with_matching(
 248             target, start, alternatives,
 249             |k| matches!(k, Ref(_, Mutability::Mut)),
 250             |k| always_pat!(k, Ref(p, _) => p),
 251         ),
 252         // Transform `b @ p0 | ... b @ p1` into `b @ (p0 | p1)`.
 253         Ident(b1, i1, Some(target)) => extend_with_matching(
 254             target, start, alternatives,
 255             // Binding names must match.
 256             |k| matches!(k, Ident(b2, i2, Some(_)) if b1 == b2 && eq_id(*i1, *i2)),
 257             |k| always_pat!(k, Ident(_, _, Some(p)) => p),
 258         ),
 259         // Transform `[pre, x, post] | ... | [pre, y, post]` into `[pre, x | y, post]`.
 260         Slice(ps1) => extend_with_matching_product(
 261             ps1, start, alternatives,
 262             |k, ps1, idx| matches!(k, Slice(ps2) if eq_pre_post(ps1, ps2, idx)),
 263             |k| always_pat!(k, Slice(ps) => ps),
 264         ),
 265         // Transform `(pre, x, post) | ... | (pre, y, post)` into `(pre, x | y, post)`.
 266         Tuple(ps1) => extend_with_matching_product(
 267             ps1, start, alternatives,
 268             |k, ps1, idx| matches!(k, Tuple(ps2) if eq_pre_post(ps1, ps2, idx)),
 269             |k| always_pat!(k, Tuple(ps) => ps),
 270         ),
 271         // Transform `S(pre, x, post) | ... | S(pre, y, post)` into `S(pre, x | y, post)`.
 272         TupleStruct(qself1, path1, ps1) => extend_with_matching_product(
 273             ps1, start, alternatives,
 274             |k, ps1, idx| matches!(
 275                 k,
 276                 TupleStruct(qself2, path2, ps2)
 277                     if eq_maybe_qself(qself1, qself2) && eq_path(path1, path2) && eq_pre_post(ps1, ps2, idx)
 278             ),
 279             |k| always_pat!(k, TupleStruct(_, _, ps) => ps),
 280         ),
 281         // Transform a record pattern `S { fp_0, ..., fp_n }`.
 282         Struct(qself1, path1, fps1, rest1) => extend_with_struct_pat(qself1, path1, fps1, *rest1, start, alternatives),
 283     };
 284
 285     alternatives[focus_idx].kind = focus_kind;
 286     changed
 287 }
 288
 289 /// Here we focusing on a record pattern `S { fp_0, ..., fp_n }`.
 290 /// In particular, for a record pattern, the order in which the field patterns is irrelevant.
 291 /// So when we fixate on some `ident_k: pat_k`, we try to find `ident_k` in the other pattern
 292 /// and check that all `fp_i` where `i ∈ ((0...n) \ k)` between two patterns are equal.
 293 fn extend_with_struct_pat(
 294     qself1: &Option<P<ast::QSelf>>,
 295     path1: &ast::Path,
 296     fps1: &mut [ast::PatField],
 297     rest1: bool,
 298     start: usize,
 299     alternatives: &mut ThinVec<P<Pat>>,
 300 ) -> bool {
 301     (0..fps1.len()).any(|idx| {
 302         let pos_in_2 = Cell::new(None); // The element `k`.
 303         let tail_or = drain_matching(
 304             start,
 305             alternatives,
 306             |k| {
 307                 matches!(k, Struct(qself2, path2, fps2, rest2)
 308                 if rest1 == *rest2 // If one struct pattern has `..` so must the other.
 309                 && eq_maybe_qself(qself1, qself2)
 310                 && eq_path(path1, path2)
 311                 && fps1.len() == fps2.len()
 312                 && fps1.iter().enumerate().all(|(idx_1, fp1)| {
 313                     if idx_1 == idx {
 314                         // In the case of `k`, we merely require identical field names
 315                         // so that we will transform into `ident_k: p1_k | p2_k`.
 316                         let pos = fps2.iter().position(|fp2| eq_id(fp1.ident, fp2.ident));
 317                         pos_in_2.set(pos);
 318                         pos.is_some()
 319                     } else {
 320                         fps2.iter().any(|fp2| eq_field_pat(fp1, fp2))
 321                     }
 322                 }))
 323             },
 324             // Extract `p2_k`.
 325             |k| always_pat!(k, Struct(_, _, mut fps, _) => fps.swap_remove(pos_in_2.take().unwrap()).pat),
 326         );
 327         extend_with_tail_or(&mut fps1[idx].pat, tail_or)
 328     })
 329 }
 330
 331 /// Like `extend_with_matching` but for products with > 1 factor, e.g., `C(p_0, ..., p_n)`.
 332 /// Here, the idea is that we fixate on some `p_k` in `C`,
 333 /// allowing it to vary between two `targets` and `ps2` (returned by `extract`),
 334 /// while also requiring `ps1[..n] ~ ps2[..n]` (pre) and `ps1[n + 1..] ~ ps2[n + 1..]` (post),
 335 /// where `~` denotes semantic equality.
 336 fn extend_with_matching_product(
 337     targets: &mut [P<Pat>],
 338     start: usize,
 339     alternatives: &mut ThinVec<P<Pat>>,
 340     predicate: impl Fn(&PatKind, &[P<Pat>], usize) -> bool,
 341     extract: impl Fn(PatKind) -> ThinVec<P<Pat>>,
 342 ) -> bool {
 343     (0..targets.len()).any(|idx| {
 344         let tail_or = drain_matching(
 345             start,
 346             alternatives,
 347             |k| predicate(k, targets, idx),
 348             |k| extract(k).swap_remove(idx),
 349         );
 350         extend_with_tail_or(&mut targets[idx], tail_or)
 351     })
 352 }
 353
 354 /// Extract the pattern from the given one and replace it with `Wild`.
 355 /// This is meant for temporarily swapping out the pattern for manipulation.
 356 fn take_pat(from: &mut Pat) -> Pat {
 357     let dummy = Pat {
 358         id: DUMMY_NODE_ID,
 359         kind: Wild,
 360         span: DUMMY_SP,
 361         tokens: None,
 362     };
 363     mem::replace(from, dummy)
 364 }
 365
 366 /// Extend `target` as an or-pattern with the alternatives
 367 /// in `tail_or` if there are any and return if there were.
 368 fn extend_with_tail_or(target: &mut Pat, tail_or: ThinVec<P<Pat>>) -> bool {
 369     fn extend(target: &mut Pat, mut tail_or: ThinVec<P<Pat>>) {
 370         match target {
 371             // On an existing or-pattern in the target, append to it.
 372             Pat { kind: Or(ps), .. } => ps.append(&mut tail_or),
 373             // Otherwise convert the target to an or-pattern.
 374             target => {
 375                 let mut init_or = thin_vec![P(take_pat(target))];
 376                 init_or.append(&mut tail_or);
 377                 target.kind = Or(init_or);
 378             },
 379         }
 380     }
 381
 382     let changed = !tail_or.is_empty();
 383     if changed {
 384         // Extend the target.
 385         extend(target, tail_or);
 386     }
 387     changed
 388 }
 389
 390 // Extract all inner patterns in `alternatives` matching our `predicate`.
 391 // Only elements beginning with `start` are considered for extraction.
 392 fn drain_matching(
 393     start: usize,
 394     alternatives: &mut ThinVec<P<Pat>>,
 395     predicate: impl Fn(&PatKind) -> bool,
 396     extract: impl Fn(PatKind) -> P<Pat>,
 397 ) -> ThinVec<P<Pat>> {
 398     let mut tail_or = ThinVec::new();
 399     let mut idx = 0;
 400
 401     // If `ThinVec` had the `drain_filter` method, this loop could be rewritten
 402     // like so:
 403     //
 404     //   for pat in alternatives.drain_filter(|p| {
 405     //       // Check if we should extract, but only if `idx >= start`.
 406     //       idx += 1;
 407     //       idx > start && predicate(&p.kind)
 408     //   }) {
 409     //       tail_or.push(extract(pat.into_inner().kind));
 410     //   }
 411     let mut i = 0;
 412     while i < alternatives.len() {
 413         idx += 1;
 414         // Check if we should extract, but only if `idx >= start`.
 415         if idx > start && predicate(&alternatives[i].kind) {
 416             let pat = alternatives.remove(i);
 417             tail_or.push(extract(pat.into_inner().kind));
 418         } else {
 419             i += 1;
 420         }
 421     }
 422
 423     tail_or
 424 }
 425
 426 fn extend_with_matching(
 427     target: &mut Pat,
 428     start: usize,
 429     alternatives: &mut ThinVec<P<Pat>>,
 430     predicate: impl Fn(&PatKind) -> bool,
 431     extract: impl Fn(PatKind) -> P<Pat>,
 432 ) -> bool {
 433     extend_with_tail_or(target, drain_matching(start, alternatives, predicate, extract))
 434 }
 435
 436 /// Are the patterns in `ps1` and `ps2` equal save for `ps1[idx]` compared to `ps2[idx]`?
 437 fn eq_pre_post(ps1: &[P<Pat>], ps2: &[P<Pat>], idx: usize) -> bool {
 438     ps1.len() == ps2.len()
 439         && ps1[idx].is_rest() == ps2[idx].is_rest() // Avoid `[x, ..] | [x, 0]` => `[x, .. | 0]`.
 440         && over(&ps1[..idx], &ps2[..idx], |l, r| eq_pat(l, r))
 441         && over(&ps1[idx + 1..], &ps2[idx + 1..], |l, r| eq_pat(l, r))
 442 }