clippy_lints/src/unnested_or_patterns.rs

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