clippy_lints/src/matches.rs

   1 use crate::consts::{constant, miri_to_const, Constant};
   2 use crate::utils::paths;
   3 use crate::utils::sugg::Sugg;
   4 use crate::utils::usage::is_unused;
   5 use crate::utils::{
   6     expr_block, get_arg_name, get_parent_expr, in_macro, indent_of, is_allowed, is_expn_of, is_refutable,
   7     is_type_diagnostic_item, is_wild, match_qpath, match_type, match_var, multispan_sugg, remove_blocks, snippet,
   8     snippet_block, snippet_with_applicability, span_lint_and_help, span_lint_and_note, span_lint_and_sugg,
   9     span_lint_and_then, walk_ptrs_ty,
  10 };
  11 use if_chain::if_chain;
  12 use rustc_ast::ast::LitKind;
  13 use rustc_errors::Applicability;
  14 use rustc_hir::def::CtorKind;
  15 use rustc_hir::{
  16     Arm, BindingAnnotation, Block, BorrowKind, Expr, ExprKind, Local, MatchSource, Mutability, Node, Pat, PatKind,
  17     QPath, RangeEnd,
  18 };
  19 use rustc_lint::{LateContext, LateLintPass, LintContext};
  20 use rustc_middle::lint::in_external_macro;
  21 use rustc_middle::ty::{self, Ty};
  22 use rustc_session::{declare_tool_lint, impl_lint_pass};
  23 use rustc_span::source_map::Span;
  24 use std::cmp::Ordering;
  25 use std::collections::Bound;
  26
  27 declare_clippy_lint! {
  28     /// **What it does:** Checks for matches with a single arm where an `if let`
  29     /// will usually suffice.
  30     ///
  31     /// **Why is this bad?** Just readability – `if let` nests less than a `match`.
  32     ///
  33     /// **Known problems:** None.
  34     ///
  35     /// **Example:**
  36     /// ```rust
  37     /// # fn bar(stool: &str) {}
  38     /// # let x = Some("abc");
  39     ///
  40     /// // Bad
  41     /// match x {
  42     ///     Some(ref foo) => bar(foo),
  43     ///     _ => (),
  44     /// }
  45     ///
  46     /// // Good
  47     /// if let Some(ref foo) = x {
  48     ///     bar(foo);
  49     /// }
  50     /// ```
  51     pub SINGLE_MATCH,
  52     style,
  53     "a `match` statement with a single nontrivial arm (i.e., where the other arm is `_ => {}`) instead of `if let`"
  54 }
  55
  56 declare_clippy_lint! {
  57     /// **What it does:** Checks for matches with two arms where an `if let else` will
  58     /// usually suffice.
  59     ///
  60     /// **Why is this bad?** Just readability – `if let` nests less than a `match`.
  61     ///
  62     /// **Known problems:** Personal style preferences may differ.
  63     ///
  64     /// **Example:**
  65     ///
  66     /// Using `match`:
  67     ///
  68     /// ```rust
  69     /// # fn bar(foo: &usize) {}
  70     /// # let other_ref: usize = 1;
  71     /// # let x: Option<&usize> = Some(&1);
  72     /// match x {
  73     ///     Some(ref foo) => bar(foo),
  74     ///     _ => bar(&other_ref),
  75     /// }
  76     /// ```
  77     ///
  78     /// Using `if let` with `else`:
  79     ///
  80     /// ```rust
  81     /// # fn bar(foo: &usize) {}
  82     /// # let other_ref: usize = 1;
  83     /// # let x: Option<&usize> = Some(&1);
  84     /// if let Some(ref foo) = x {
  85     ///     bar(foo);
  86     /// } else {
  87     ///     bar(&other_ref);
  88     /// }
  89     /// ```
  90     pub SINGLE_MATCH_ELSE,
  91     pedantic,
  92     "a `match` statement with two arms where the second arm's pattern is a placeholder instead of a specific match pattern"
  93 }
  94
  95 declare_clippy_lint! {
  96     /// **What it does:** Checks for matches where all arms match a reference,
  97     /// suggesting to remove the reference and deref the matched expression
  98     /// instead. It also checks for `if let &foo = bar` blocks.
  99     ///
 100     /// **Why is this bad?** It just makes the code less readable. That reference
 101     /// destructuring adds nothing to the code.
 102     ///
 103     /// **Known problems:** None.
 104     ///
 105     /// **Example:**
 106     /// ```rust,ignore
 107     /// // Bad
 108     /// match x {
 109     ///     &A(ref y) => foo(y),
 110     ///     &B => bar(),
 111     ///     _ => frob(&x),
 112     /// }
 113     ///
 114     /// // Good
 115     /// match *x {
 116     ///     A(ref y) => foo(y),
 117     ///     B => bar(),
 118     ///     _ => frob(x),
 119     /// }
 120     /// ```
 121     pub MATCH_REF_PATS,
 122     style,
 123     "a `match` or `if let` with all arms prefixed with `&` instead of deref-ing the match expression"
 124 }
 125
 126 declare_clippy_lint! {
 127     /// **What it does:** Checks for matches where match expression is a `bool`. It
 128     /// suggests to replace the expression with an `if...else` block.
 129     ///
 130     /// **Why is this bad?** It makes the code less readable.
 131     ///
 132     /// **Known problems:** None.
 133     ///
 134     /// **Example:**
 135     /// ```rust
 136     /// # fn foo() {}
 137     /// # fn bar() {}
 138     /// let condition: bool = true;
 139     /// match condition {
 140     ///     true => foo(),
 141     ///     false => bar(),
 142     /// }
 143     /// ```
 144     /// Use if/else instead:
 145     /// ```rust
 146     /// # fn foo() {}
 147     /// # fn bar() {}
 148     /// let condition: bool = true;
 149     /// if condition {
 150     ///     foo();
 151     /// } else {
 152     ///     bar();
 153     /// }
 154     /// ```
 155     pub MATCH_BOOL,
 156     pedantic,
 157     "a `match` on a boolean expression instead of an `if..else` block"
 158 }
 159
 160 declare_clippy_lint! {
 161     /// **What it does:** Checks for overlapping match arms.
 162     ///
 163     /// **Why is this bad?** It is likely to be an error and if not, makes the code
 164     /// less obvious.
 165     ///
 166     /// **Known problems:** None.
 167     ///
 168     /// **Example:**
 169     /// ```rust
 170     /// let x = 5;
 171     /// match x {
 172     ///     1...10 => println!("1 ... 10"),
 173     ///     5...15 => println!("5 ... 15"),
 174     ///     _ => (),
 175     /// }
 176     /// ```
 177     pub MATCH_OVERLAPPING_ARM,
 178     style,
 179     "a `match` with overlapping arms"
 180 }
 181
 182 declare_clippy_lint! {
 183     /// **What it does:** Checks for arm which matches all errors with `Err(_)`
 184     /// and take drastic actions like `panic!`.
 185     ///
 186     /// **Why is this bad?** It is generally a bad practice, similar to
 187     /// catching all exceptions in java with `catch(Exception)`
 188     ///
 189     /// **Known problems:** None.
 190     ///
 191     /// **Example:**
 192     /// ```rust
 193     /// let x: Result<i32, &str> = Ok(3);
 194     /// match x {
 195     ///     Ok(_) => println!("ok"),
 196     ///     Err(_) => panic!("err"),
 197     /// }
 198     /// ```
 199     pub MATCH_WILD_ERR_ARM,
 200     pedantic,
 201     "a `match` with `Err(_)` arm and take drastic actions"
 202 }
 203
 204 declare_clippy_lint! {
 205     /// **What it does:** Checks for match which is used to add a reference to an
 206     /// `Option` value.
 207     ///
 208     /// **Why is this bad?** Using `as_ref()` or `as_mut()` instead is shorter.
 209     ///
 210     /// **Known problems:** None.
 211     ///
 212     /// **Example:**
 213     /// ```rust
 214     /// let x: Option<()> = None;
 215     ///
 216     /// // Bad
 217     /// let r: Option<&()> = match x {
 218     ///     None => None,
 219     ///     Some(ref v) => Some(v),
 220     /// };
 221     ///
 222     /// // Good
 223     /// let r: Option<&()> = x.as_ref();
 224     /// ```
 225     pub MATCH_AS_REF,
 226     complexity,
 227     "a `match` on an Option value instead of using `as_ref()` or `as_mut`"
 228 }
 229
 230 declare_clippy_lint! {
 231     /// **What it does:** Checks for wildcard enum matches using `_`.
 232     ///
 233     /// **Why is this bad?** New enum variants added by library updates can be missed.
 234     ///
 235     /// **Known problems:** Suggested replacements may be incorrect if guards exhaustively cover some
 236     /// variants, and also may not use correct path to enum if it's not present in the current scope.
 237     ///
 238     /// **Example:**
 239     /// ```rust
 240     /// # enum Foo { A(usize), B(usize) }
 241     /// # let x = Foo::B(1);
 242     ///
 243     /// // Bad
 244     /// match x {
 245     ///     Foo::A(_) => {},
 246     ///     _ => {},
 247     /// }
 248     ///
 249     /// // Good
 250     /// match x {
 251     ///     Foo::A(_) => {},
 252     ///     Foo::B(_) => {},
 253     /// }
 254     /// ```
 255     pub WILDCARD_ENUM_MATCH_ARM,
 256     restriction,
 257     "a wildcard enum match arm using `_`"
 258 }
 259
 260 declare_clippy_lint! {
 261     /// **What it does:** Checks for wildcard enum matches for a single variant.
 262     ///
 263     /// **Why is this bad?** New enum variants added by library updates can be missed.
 264     ///
 265     /// **Known problems:** Suggested replacements may not use correct path to enum
 266     /// if it's not present in the current scope.
 267     ///
 268     /// **Example:**
 269     ///
 270     /// ```rust
 271     /// # enum Foo { A, B, C }
 272     /// # let x = Foo::B;
 273     ///
 274     /// // Bad
 275     /// match x {
 276     ///     Foo::A => {},
 277     ///     Foo::B => {},
 278     ///     _ => {},
 279     /// }
 280     ///
 281     /// // Good
 282     /// match x {
 283     ///     Foo::A => {},
 284     ///     Foo::B => {},
 285     ///     Foo::C => {},
 286     /// }
 287     /// ```
 288     pub MATCH_WILDCARD_FOR_SINGLE_VARIANTS,
 289     pedantic,
 290     "a wildcard enum match for a single variant"
 291 }
 292
 293 declare_clippy_lint! {
 294     /// **What it does:** Checks for wildcard pattern used with others patterns in same match arm.
 295     ///
 296     /// **Why is this bad?** Wildcard pattern already covers any other pattern as it will match anyway.
 297     /// It makes the code less readable, especially to spot wildcard pattern use in match arm.
 298     ///
 299     /// **Known problems:** None.
 300     ///
 301     /// **Example:**
 302     /// ```rust
 303     /// // Bad
 304     /// match "foo" {
 305     ///     "a" => {},
 306     ///     "bar" | _ => {},
 307     /// }
 308     ///
 309     /// // Good
 310     /// match "foo" {
 311     ///     "a" => {},
 312     ///     _ => {},
 313     /// }
 314     /// ```
 315     pub WILDCARD_IN_OR_PATTERNS,
 316     complexity,
 317     "a wildcard pattern used with others patterns in same match arm"
 318 }
 319
 320 declare_clippy_lint! {
 321     /// **What it does:** Checks for matches being used to destructure a single-variant enum
 322     /// or tuple struct where a `let` will suffice.
 323     ///
 324     /// **Why is this bad?** Just readability – `let` doesn't nest, whereas a `match` does.
 325     ///
 326     /// **Known problems:** None.
 327     ///
 328     /// **Example:**
 329     /// ```rust
 330     /// enum Wrapper {
 331     ///     Data(i32),
 332     /// }
 333     ///
 334     /// let wrapper = Wrapper::Data(42);
 335     ///
 336     /// let data = match wrapper {
 337     ///     Wrapper::Data(i) => i,
 338     /// };
 339     /// ```
 340     ///
 341     /// The correct use would be:
 342     /// ```rust
 343     /// enum Wrapper {
 344     ///     Data(i32),
 345     /// }
 346     ///
 347     /// let wrapper = Wrapper::Data(42);
 348     /// let Wrapper::Data(data) = wrapper;
 349     /// ```
 350     pub INFALLIBLE_DESTRUCTURING_MATCH,
 351     style,
 352     "a `match` statement with a single infallible arm instead of a `let`"
 353 }
 354
 355 declare_clippy_lint! {
 356     /// **What it does:** Checks for useless match that binds to only one value.
 357     ///
 358     /// **Why is this bad?** Readability and needless complexity.
 359     ///
 360     /// **Known problems:**  Suggested replacements may be incorrect when `match`
 361     /// is actually binding temporary value, bringing a 'dropped while borrowed' error.
 362     ///
 363     /// **Example:**
 364     /// ```rust
 365     /// # let a = 1;
 366     /// # let b = 2;
 367     ///
 368     /// // Bad
 369     /// match (a, b) {
 370     ///     (c, d) => {
 371     ///         // useless match
 372     ///     }
 373     /// }
 374     ///
 375     /// // Good
 376     /// let (c, d) = (a, b);
 377     /// ```
 378     pub MATCH_SINGLE_BINDING,
 379     complexity,
 380     "a match with a single binding instead of using `let` statement"
 381 }
 382
 383 declare_clippy_lint! {
 384     /// **What it does:** Checks for unnecessary '..' pattern binding on struct when all fields are explicitly matched.
 385     ///
 386     /// **Why is this bad?** Correctness and readability. It's like having a wildcard pattern after
 387     /// matching all enum variants explicitly.
 388     ///
 389     /// **Known problems:** None.
 390     ///
 391     /// **Example:**
 392     /// ```rust
 393     /// # struct A { a: i32 }
 394     /// let a = A { a: 5 };
 395     ///
 396     /// // Bad
 397     /// match a {
 398     ///     A { a: 5, .. } => {},
 399     ///     _ => {},
 400     /// }
 401     ///
 402     /// // Good
 403     /// match a {
 404     ///     A { a: 5 } => {},
 405     ///     _ => {},
 406     /// }
 407     /// ```
 408     pub REST_PAT_IN_FULLY_BOUND_STRUCTS,
 409     restriction,
 410     "a match on a struct that binds all fields but still uses the wildcard pattern"
 411 }
 412
 413 #[derive(Default)]
 414 pub struct Matches {
 415     infallible_destructuring_match_linted: bool,
 416 }
 417
 418 impl_lint_pass!(Matches => [
 419     SINGLE_MATCH,
 420     MATCH_REF_PATS,
 421     MATCH_BOOL,
 422     SINGLE_MATCH_ELSE,
 423     MATCH_OVERLAPPING_ARM,
 424     MATCH_WILD_ERR_ARM,
 425     MATCH_AS_REF,
 426     WILDCARD_ENUM_MATCH_ARM,
 427     MATCH_WILDCARD_FOR_SINGLE_VARIANTS,
 428     WILDCARD_IN_OR_PATTERNS,
 429     MATCH_SINGLE_BINDING,
 430     INFALLIBLE_DESTRUCTURING_MATCH,
 431     REST_PAT_IN_FULLY_BOUND_STRUCTS
 432 ]);
 433
 434 impl<'a, 'tcx> LateLintPass<'a, 'tcx> for Matches {
 435     fn check_expr(&mut self, cx: &LateContext<'a, 'tcx>, expr: &'tcx Expr<'_>) {
 436         if in_external_macro(cx.sess(), expr.span) {
 437             return;
 438         }
 439         if let ExprKind::Match(ref ex, ref arms, MatchSource::Normal) = expr.kind {
 440             check_single_match(cx, ex, arms, expr);
 441             check_match_bool(cx, ex, arms, expr);
 442             check_overlapping_arms(cx, ex, arms);
 443             check_wild_err_arm(cx, ex, arms);
 444             check_wild_enum_match(cx, ex, arms);
 445             check_match_as_ref(cx, ex, arms, expr);
 446             check_wild_in_or_pats(cx, arms);
 447
 448             if self.infallible_destructuring_match_linted {
 449                 self.infallible_destructuring_match_linted = false;
 450             } else {
 451                 check_match_single_binding(cx, ex, arms, expr);
 452             }
 453         }
 454         if let ExprKind::Match(ref ex, ref arms, _) = expr.kind {
 455             check_match_ref_pats(cx, ex, arms, expr);
 456         }
 457     }
 458
 459     fn check_local(&mut self, cx: &LateContext<'a, 'tcx>, local: &'tcx Local<'_>) {
 460         if_chain! {
 461             if !in_external_macro(cx.sess(), local.span);
 462             if !in_macro(local.span);
 463             if let Some(ref expr) = local.init;
 464             if let ExprKind::Match(ref target, ref arms, MatchSource::Normal) = expr.kind;
 465             if arms.len() == 1 && arms[0].guard.is_none();
 466             if let PatKind::TupleStruct(
 467                 QPath::Resolved(None, ref variant_name), ref args, _) = arms[0].pat.kind;
 468             if args.len() == 1;
 469             if let Some(arg) = get_arg_name(&args[0]);
 470             let body = remove_blocks(&arms[0].body);
 471             if match_var(body, arg);
 472
 473             then {
 474                 let mut applicability = Applicability::MachineApplicable;
 475                 self.infallible_destructuring_match_linted = true;
 476                 span_lint_and_sugg(
 477                     cx,
 478                     INFALLIBLE_DESTRUCTURING_MATCH,
 479                     local.span,
 480                     "you seem to be trying to use `match` to destructure a single infallible pattern. \
 481                     Consider using `let`",
 482                     "try this",
 483                     format!(
 484                         "let {}({}) = {};",
 485                         snippet_with_applicability(cx, variant_name.span, "..", &mut applicability),
 486                         snippet_with_applicability(cx, local.pat.span, "..", &mut applicability),
 487                         snippet_with_applicability(cx, target.span, "..", &mut applicability),
 488                     ),
 489                     applicability,
 490                 );
 491             }
 492         }
 493     }
 494
 495     fn check_pat(&mut self, cx: &LateContext<'a, 'tcx>, pat: &'tcx Pat<'_>) {
 496         if_chain! {
 497             if !in_external_macro(cx.sess(), pat.span);
 498             if !in_macro(pat.span);
 499             if let PatKind::Struct(ref qpath, fields, true) = pat.kind;
 500             if let QPath::Resolved(_, ref path) = qpath;
 501             if let Some(def_id) = path.res.opt_def_id();
 502             let ty = cx.tcx.type_of(def_id);
 503             if let ty::Adt(def, _) = ty.kind;
 504             if def.is_struct() || def.is_union();
 505             if fields.len() == def.non_enum_variant().fields.len();
 506
 507             then {
 508                 span_lint_and_help(
 509                     cx,
 510                     REST_PAT_IN_FULLY_BOUND_STRUCTS,
 511                     pat.span,
 512                     "unnecessary use of `..` pattern in struct binding. All fields were already bound",
 513                     None,
 514                     "consider removing `..` from this binding",
 515                 );
 516             }
 517         }
 518     }
 519 }
 520
 521 #[rustfmt::skip]
 522 fn check_single_match(cx: &LateContext<'_, '_>, ex: &Expr<'_>, arms: &[Arm<'_>], expr: &Expr<'_>) {
 523     if arms.len() == 2 && arms[0].guard.is_none() && arms[1].guard.is_none() {
 524         if in_macro(expr.span) {
 525             // Don't lint match expressions present in
 526             // macro_rules! block
 527             return;
 528         }
 529         if let PatKind::Or(..) = arms[0].pat.kind {
 530             // don't lint for or patterns for now, this makes
 531             // the lint noisy in unnecessary situations
 532             return;
 533         }
 534         let els = remove_blocks(&arms[1].body);
 535         let els = if is_unit_expr(els) {
 536             None
 537         } else if let ExprKind::Block(_, _) = els.kind {
 538             // matches with blocks that contain statements are prettier as `if let + else`
 539             Some(els)
 540         } else {
 541             // allow match arms with just expressions
 542             return;
 543         };
 544         let ty = cx.tables.expr_ty(ex);
 545         if ty.kind != ty::Bool || is_allowed(cx, MATCH_BOOL, ex.hir_id) {
 546             check_single_match_single_pattern(cx, ex, arms, expr, els);
 547             check_single_match_opt_like(cx, ex, arms, expr, ty, els);
 548         }
 549     }
 550 }
 551
 552 fn check_single_match_single_pattern(
 553     cx: &LateContext<'_, '_>,
 554     ex: &Expr<'_>,
 555     arms: &[Arm<'_>],
 556     expr: &Expr<'_>,
 557     els: Option<&Expr<'_>>,
 558 ) {
 559     if is_wild(&arms[1].pat) {
 560         report_single_match_single_pattern(cx, ex, arms, expr, els);
 561     }
 562 }
 563
 564 fn report_single_match_single_pattern(
 565     cx: &LateContext<'_, '_>,
 566     ex: &Expr<'_>,
 567     arms: &[Arm<'_>],
 568     expr: &Expr<'_>,
 569     els: Option<&Expr<'_>>,
 570 ) {
 571     let lint = if els.is_some() { SINGLE_MATCH_ELSE } else { SINGLE_MATCH };
 572     let els_str = els.map_or(String::new(), |els| {
 573         format!(" else {}", expr_block(cx, els, None, "..", Some(expr.span)))
 574     });
 575     span_lint_and_sugg(
 576         cx,
 577         lint,
 578         expr.span,
 579         "you seem to be trying to use match for destructuring a single pattern. Consider using `if \
 580          let`",
 581         "try this",
 582         format!(
 583             "if let {} = {} {}{}",
 584             snippet(cx, arms[0].pat.span, ".."),
 585             snippet(cx, ex.span, ".."),
 586             expr_block(cx, &arms[0].body, None, "..", Some(expr.span)),
 587             els_str,
 588         ),
 589         Applicability::HasPlaceholders,
 590     );
 591 }
 592
 593 fn check_single_match_opt_like(
 594     cx: &LateContext<'_, '_>,
 595     ex: &Expr<'_>,
 596     arms: &[Arm<'_>],
 597     expr: &Expr<'_>,
 598     ty: Ty<'_>,
 599     els: Option<&Expr<'_>>,
 600 ) {
 601     // list of candidate `Enum`s we know will never get any more members
 602     let candidates = &[
 603         (&paths::COW, "Borrowed"),
 604         (&paths::COW, "Cow::Borrowed"),
 605         (&paths::COW, "Cow::Owned"),
 606         (&paths::COW, "Owned"),
 607         (&paths::OPTION, "None"),
 608         (&paths::RESULT, "Err"),
 609         (&paths::RESULT, "Ok"),
 610     ];
 611
 612     let path = match arms[1].pat.kind {
 613         PatKind::TupleStruct(ref path, ref inner, _) => {
 614             // Contains any non wildcard patterns (e.g., `Err(err)`)?
 615             if !inner.iter().all(is_wild) {
 616                 return;
 617             }
 618             rustc_hir_pretty::to_string(rustc_hir_pretty::NO_ANN, |s| s.print_qpath(path, false))
 619         },
 620         PatKind::Binding(BindingAnnotation::Unannotated, .., ident, None) => ident.to_string(),
 621         PatKind::Path(ref path) => {
 622             rustc_hir_pretty::to_string(rustc_hir_pretty::NO_ANN, |s| s.print_qpath(path, false))
 623         },
 624         _ => return,
 625     };
 626
 627     for &(ty_path, pat_path) in candidates {
 628         if path == *pat_path && match_type(cx, ty, ty_path) {
 629             report_single_match_single_pattern(cx, ex, arms, expr, els);
 630         }
 631     }
 632 }
 633
 634 fn check_match_bool(cx: &LateContext<'_, '_>, ex: &Expr<'_>, arms: &[Arm<'_>], expr: &Expr<'_>) {
 635     // Type of expression is `bool`.
 636     if cx.tables.expr_ty(ex).kind == ty::Bool {
 637         span_lint_and_then(
 638             cx,
 639             MATCH_BOOL,
 640             expr.span,
 641             "you seem to be trying to match on a boolean expression",
 642             move |diag| {
 643                 if arms.len() == 2 {
 644                     // no guards
 645                     let exprs = if let PatKind::Lit(ref arm_bool) = arms[0].pat.kind {
 646                         if let ExprKind::Lit(ref lit) = arm_bool.kind {
 647                             match lit.node {
 648                                 LitKind::Bool(true) => Some((&*arms[0].body, &*arms[1].body)),
 649                                 LitKind::Bool(false) => Some((&*arms[1].body, &*arms[0].body)),
 650                                 _ => None,
 651                             }
 652                         } else {
 653                             None
 654                         }
 655                     } else {
 656                         None
 657                     };
 658
 659                     if let Some((true_expr, false_expr)) = exprs {
 660                         let sugg = match (is_unit_expr(true_expr), is_unit_expr(false_expr)) {
 661                             (false, false) => Some(format!(
 662                                 "if {} {} else {}",
 663                                 snippet(cx, ex.span, "b"),
 664                                 expr_block(cx, true_expr, None, "..", Some(expr.span)),
 665                                 expr_block(cx, false_expr, None, "..", Some(expr.span))
 666                             )),
 667                             (false, true) => Some(format!(
 668                                 "if {} {}",
 669                                 snippet(cx, ex.span, "b"),
 670                                 expr_block(cx, true_expr, None, "..", Some(expr.span))
 671                             )),
 672                             (true, false) => {
 673                                 let test = Sugg::hir(cx, ex, "..");
 674                                 Some(format!(
 675                                     "if {} {}",
 676                                     !test,
 677                                     expr_block(cx, false_expr, None, "..", Some(expr.span))
 678                                 ))
 679                             },
 680                             (true, true) => None,
 681                         };
 682
 683                         if let Some(sugg) = sugg {
 684                             diag.span_suggestion(
 685                                 expr.span,
 686                                 "consider using an `if`/`else` expression",
 687                                 sugg,
 688                                 Applicability::HasPlaceholders,
 689                             );
 690                         }
 691                     }
 692                 }
 693             },
 694         );
 695     }
 696 }
 697
 698 fn check_overlapping_arms<'a, 'tcx>(cx: &LateContext<'a, 'tcx>, ex: &'tcx Expr<'_>, arms: &'tcx [Arm<'_>]) {
 699     if arms.len() >= 2 && cx.tables.expr_ty(ex).is_integral() {
 700         let ranges = all_ranges(cx, arms, cx.tables.expr_ty(ex));
 701         let type_ranges = type_ranges(&ranges);
 702         if !type_ranges.is_empty() {
 703             if let Some((start, end)) = overlapping(&type_ranges) {
 704                 span_lint_and_note(
 705                     cx,
 706                     MATCH_OVERLAPPING_ARM,
 707                     start.span,
 708                     "some ranges overlap",
 709                     Some(end.span),
 710                     "overlaps with this",
 711                 );
 712             }
 713         }
 714     }
 715 }
 716
 717 fn check_wild_err_arm(cx: &LateContext<'_, '_>, ex: &Expr<'_>, arms: &[Arm<'_>]) {
 718     let ex_ty = walk_ptrs_ty(cx.tables.expr_ty(ex));
 719     if is_type_diagnostic_item(cx, ex_ty, sym!(result_type)) {
 720         for arm in arms {
 721             if let PatKind::TupleStruct(ref path, ref inner, _) = arm.pat.kind {
 722                 let path_str = rustc_hir_pretty::to_string(rustc_hir_pretty::NO_ANN, |s| s.print_qpath(path, false));
 723                 if path_str == "Err" {
 724                     let mut matching_wild = inner.iter().any(is_wild);
 725                     let mut ident_bind_name = String::from("_");
 726                     if !matching_wild {
 727                         // Looking for unused bindings (i.e.: `_e`)
 728                         inner.iter().for_each(|pat| {
 729                             if let PatKind::Binding(.., ident, None) = &pat.kind {
 730                                 if ident.as_str().starts_with('_') && is_unused(ident, arm.body) {
 731                                     ident_bind_name = (&ident.name.as_str()).to_string();
 732                                     matching_wild = true;
 733                                 }
 734                             }
 735                         });
 736                     }
 737                     if_chain! {
 738                         if matching_wild;
 739                         if let ExprKind::Block(ref block, _) = arm.body.kind;
 740                         if is_panic_block(block);
 741                         then {
 742                             // `Err(_)` or `Err(_e)` arm with `panic!` found
 743                             span_lint_and_note(cx,
 744                                 MATCH_WILD_ERR_ARM,
 745                                 arm.pat.span,
 746                                 &format!("`Err({})` matches all errors", &ident_bind_name),
 747                                 None,
 748                                 "match each error separately or use the error output, or use `.except(msg)` if the error case is unreachable",
 749                             );
 750                         }
 751                     }
 752                 }
 753             }
 754         }
 755     }
 756 }
 757
 758 fn check_wild_enum_match(cx: &LateContext<'_, '_>, ex: &Expr<'_>, arms: &[Arm<'_>]) {
 759     let ty = cx.tables.expr_ty(ex);
 760     if !ty.is_enum() {
 761         // If there isn't a nice closed set of possible values that can be conveniently enumerated,
 762         // don't complain about not enumerating the mall.
 763         return;
 764     }
 765
 766     // First pass - check for violation, but don't do much book-keeping because this is hopefully
 767     // the uncommon case, and the book-keeping is slightly expensive.
 768     let mut wildcard_span = None;
 769     let mut wildcard_ident = None;
 770     for arm in arms {
 771         if let PatKind::Wild = arm.pat.kind {
 772             wildcard_span = Some(arm.pat.span);
 773         } else if let PatKind::Binding(_, _, ident, None) = arm.pat.kind {
 774             wildcard_span = Some(arm.pat.span);
 775             wildcard_ident = Some(ident);
 776         }
 777     }
 778
 779     if let Some(wildcard_span) = wildcard_span {
 780         // Accumulate the variants which should be put in place of the wildcard because they're not
 781         // already covered.
 782
 783         let mut missing_variants = vec![];
 784         if let ty::Adt(def, _) = ty.kind {
 785             for variant in &def.variants {
 786                 missing_variants.push(variant);
 787             }
 788         }
 789
 790         for arm in arms {
 791             if arm.guard.is_some() {
 792                 // Guards mean that this case probably isn't exhaustively covered. Technically
 793                 // this is incorrect, as we should really check whether each variant is exhaustively
 794                 // covered by the set of guards that cover it, but that's really hard to do.
 795                 continue;
 796             }
 797             if let PatKind::Path(ref path) = arm.pat.kind {
 798                 if let QPath::Resolved(_, p) = path {
 799                     missing_variants.retain(|e| e.ctor_def_id != Some(p.res.def_id()));
 800                 }
 801             } else if let PatKind::TupleStruct(ref path, ref patterns, ..) = arm.pat.kind {
 802                 if let QPath::Resolved(_, p) = path {
 803                     // Some simple checks for exhaustive patterns.
 804                     // There is a room for improvements to detect more cases,
 805                     // but it can be more expensive to do so.
 806                     let is_pattern_exhaustive = |pat: &&Pat<'_>| {
 807                         if let PatKind::Wild | PatKind::Binding(.., None) = pat.kind {
 808                             true
 809                         } else {
 810                             false
 811                         }
 812                     };
 813                     if patterns.iter().all(is_pattern_exhaustive) {
 814                         missing_variants.retain(|e| e.ctor_def_id != Some(p.res.def_id()));
 815                     }
 816                 }
 817             }
 818         }
 819
 820         let mut suggestion: Vec<String> = missing_variants
 821             .iter()
 822             .map(|v| {
 823                 let suffix = match v.ctor_kind {
 824                     CtorKind::Fn => "(..)",
 825                     CtorKind::Const | CtorKind::Fictive => "",
 826                 };
 827                 let ident_str = if let Some(ident) = wildcard_ident {
 828                     format!("{} @ ", ident.name)
 829                 } else {
 830                     String::new()
 831                 };
 832                 // This path assumes that the enum type is imported into scope.
 833                 format!("{}{}{}", ident_str, cx.tcx.def_path_str(v.def_id), suffix)
 834             })
 835             .collect();
 836
 837         if suggestion.is_empty() {
 838             return;
 839         }
 840
 841         let mut message = "wildcard match will miss any future added variants";
 842
 843         if let ty::Adt(def, _) = ty.kind {
 844             if def.is_variant_list_non_exhaustive() {
 845                 message = "match on non-exhaustive enum doesn't explicitly match all known variants";
 846                 suggestion.push(String::from("_"));
 847             }
 848         }
 849
 850         if suggestion.len() == 1 {
 851             // No need to check for non-exhaustive enum as in that case len would be greater than 1
 852             span_lint_and_sugg(
 853                 cx,
 854                 MATCH_WILDCARD_FOR_SINGLE_VARIANTS,
 855                 wildcard_span,
 856                 message,
 857                 "try this",
 858                 suggestion[0].clone(),
 859                 Applicability::MaybeIncorrect,
 860             )
 861         };
 862
 863         span_lint_and_sugg(
 864             cx,
 865             WILDCARD_ENUM_MATCH_ARM,
 866             wildcard_span,
 867             message,
 868             "try this",
 869             suggestion.join(" | "),
 870             Applicability::MaybeIncorrect,
 871         )
 872     }
 873 }
 874
 875 // If the block contains only a `panic!` macro (as expression or statement)
 876 fn is_panic_block(block: &Block<'_>) -> bool {
 877     match (&block.expr, block.stmts.len(), block.stmts.first()) {
 878         (&Some(ref exp), 0, _) => {
 879             is_expn_of(exp.span, "panic").is_some() && is_expn_of(exp.span, "unreachable").is_none()
 880         },
 881         (&None, 1, Some(stmt)) => {
 882             is_expn_of(stmt.span, "panic").is_some() && is_expn_of(stmt.span, "unreachable").is_none()
 883         },
 884         _ => false,
 885     }
 886 }
 887
 888 fn check_match_ref_pats(cx: &LateContext<'_, '_>, ex: &Expr<'_>, arms: &[Arm<'_>], expr: &Expr<'_>) {
 889     if has_only_ref_pats(arms) {
 890         let mut suggs = Vec::with_capacity(arms.len() + 1);
 891         let (title, msg) = if let ExprKind::AddrOf(BorrowKind::Ref, Mutability::Not, ref inner) = ex.kind {
 892             let span = ex.span.source_callsite();
 893             suggs.push((span, Sugg::hir_with_macro_callsite(cx, inner, "..").to_string()));
 894             (
 895                 "you don't need to add `&` to both the expression and the patterns",
 896                 "try",
 897             )
 898         } else {
 899             let span = ex.span.source_callsite();
 900             suggs.push((span, Sugg::hir_with_macro_callsite(cx, ex, "..").deref().to_string()));
 901             (
 902                 "you don't need to add `&` to all patterns",
 903                 "instead of prefixing all patterns with `&`, you can dereference the expression",
 904             )
 905         };
 906
 907         suggs.extend(arms.iter().filter_map(|a| {
 908             if let PatKind::Ref(ref refp, _) = a.pat.kind {
 909                 Some((a.pat.span, snippet(cx, refp.span, "..").to_string()))
 910             } else {
 911                 None
 912             }
 913         }));
 914
 915         span_lint_and_then(cx, MATCH_REF_PATS, expr.span, title, |diag| {
 916             if !expr.span.from_expansion() {
 917                 multispan_sugg(diag, msg, suggs);
 918             }
 919         });
 920     }
 921 }
 922
 923 fn check_match_as_ref(cx: &LateContext<'_, '_>, ex: &Expr<'_>, arms: &[Arm<'_>], expr: &Expr<'_>) {
 924     if arms.len() == 2 && arms[0].guard.is_none() && arms[1].guard.is_none() {
 925         let arm_ref: Option<BindingAnnotation> = if is_none_arm(&arms[0]) {
 926             is_ref_some_arm(&arms[1])
 927         } else if is_none_arm(&arms[1]) {
 928             is_ref_some_arm(&arms[0])
 929         } else {
 930             None
 931         };
 932         if let Some(rb) = arm_ref {
 933             let suggestion = if rb == BindingAnnotation::Ref {
 934                 "as_ref"
 935             } else {
 936                 "as_mut"
 937             };
 938
 939             let output_ty = cx.tables.expr_ty(expr);
 940             let input_ty = cx.tables.expr_ty(ex);
 941
 942             let cast = if_chain! {
 943                 if let ty::Adt(_, substs) = input_ty.kind;
 944                 let input_ty = substs.type_at(0);
 945                 if let ty::Adt(_, substs) = output_ty.kind;
 946                 let output_ty = substs.type_at(0);
 947                 if let ty::Ref(_, output_ty, _) = output_ty.kind;
 948                 if input_ty != output_ty;
 949                 then {
 950                     ".map(|x| x as _)"
 951                 } else {
 952                     ""
 953                 }
 954             };
 955
 956             let mut applicability = Applicability::MachineApplicable;
 957             span_lint_and_sugg(
 958                 cx,
 959                 MATCH_AS_REF,
 960                 expr.span,
 961                 &format!("use `{}()` instead", suggestion),
 962                 "try this",
 963                 format!(
 964                     "{}.{}(){}",
 965                     snippet_with_applicability(cx, ex.span, "_", &mut applicability),
 966                     suggestion,
 967                     cast,
 968                 ),
 969                 applicability,
 970             )
 971         }
 972     }
 973 }
 974
 975 fn check_wild_in_or_pats(cx: &LateContext<'_, '_>, arms: &[Arm<'_>]) {
 976     for arm in arms {
 977         if let PatKind::Or(ref fields) = arm.pat.kind {
 978             // look for multiple fields in this arm that contains at least one Wild pattern
 979             if fields.len() > 1 && fields.iter().any(is_wild) {
 980                 span_lint_and_help(
 981                     cx,
 982                     WILDCARD_IN_OR_PATTERNS,
 983                     arm.pat.span,
 984                     "wildcard pattern covers any other pattern as it will match anyway.",
 985                     None,
 986                     "Consider handling `_` separately.",
 987                 );
 988             }
 989         }
 990     }
 991 }
 992
 993 fn check_match_single_binding<'a>(cx: &LateContext<'_, 'a>, ex: &Expr<'a>, arms: &[Arm<'_>], expr: &Expr<'_>) {
 994     if in_macro(expr.span) || arms.len() != 1 || is_refutable(cx, arms[0].pat) {
 995         return;
 996     }
 997     let matched_vars = ex.span;
 998     let bind_names = arms[0].pat.span;
 999     let match_body = remove_blocks(&arms[0].body);
1000     let mut snippet_body = if match_body.span.from_expansion() {
1001         Sugg::hir_with_macro_callsite(cx, match_body, "..").to_string()
1002     } else {
1003         snippet_block(cx, match_body.span, "..", Some(expr.span)).to_string()
1004     };
1005
1006     // Do we need to add ';' to suggestion ?
1007     match match_body.kind {
1008         ExprKind::Block(block, _) => {
1009             // macro + expr_ty(body) == ()
1010             if block.span.from_expansion() && cx.tables.expr_ty(&match_body).is_unit() {
1011                 snippet_body.push(';');
1012             }
1013         },
1014         _ => {
1015             // expr_ty(body) == ()
1016             if cx.tables.expr_ty(&match_body).is_unit() {
1017                 snippet_body.push(';');
1018             }
1019         },
1020     }
1021
1022     let mut applicability = Applicability::MaybeIncorrect;
1023     match arms[0].pat.kind {
1024         PatKind::Binding(..) | PatKind::Tuple(_, _) | PatKind::Struct(..) => {
1025             // If this match is in a local (`let`) stmt
1026             let (target_span, sugg) = if let Some(parent_let_node) = opt_parent_let(cx, ex) {
1027                 (
1028                     parent_let_node.span,
1029                     format!(
1030                         "let {} = {};\n{}let {} = {};",
1031                         snippet_with_applicability(cx, bind_names, "..", &mut applicability),
1032                         snippet_with_applicability(cx, matched_vars, "..", &mut applicability),
1033                         " ".repeat(indent_of(cx, expr.span).unwrap_or(0)),
1034                         snippet_with_applicability(cx, parent_let_node.pat.span, "..", &mut applicability),
1035                         snippet_body
1036                     ),
1037                 )
1038             } else {
1039                 // If we are in closure, we need curly braces around suggestion
1040                 let mut indent = " ".repeat(indent_of(cx, ex.span).unwrap_or(0));
1041                 let (mut cbrace_start, mut cbrace_end) = ("".to_string(), "".to_string());
1042                 if let Some(parent_expr) = get_parent_expr(cx, expr) {
1043                     if let ExprKind::Closure(..) = parent_expr.kind {
1044                         cbrace_end = format!("\n{}}}", indent);
1045                         // Fix body indent due to the closure
1046                         indent = " ".repeat(indent_of(cx, bind_names).unwrap_or(0));
1047                         cbrace_start = format!("{{\n{}", indent);
1048                     }
1049                 };
1050                 (
1051                     expr.span,
1052                     format!(
1053                         "{}let {} = {};\n{}{}{}",
1054                         cbrace_start,
1055                         snippet_with_applicability(cx, bind_names, "..", &mut applicability),
1056                         snippet_with_applicability(cx, matched_vars, "..", &mut applicability),
1057                         indent,
1058                         snippet_body,
1059                         cbrace_end
1060                     ),
1061                 )
1062             };
1063             span_lint_and_sugg(
1064                 cx,
1065                 MATCH_SINGLE_BINDING,
1066                 target_span,
1067                 "this match could be written as a `let` statement",
1068                 "consider using `let` statement",
1069                 sugg,
1070                 applicability,
1071             );
1072         },
1073         PatKind::Wild => {
1074             span_lint_and_sugg(
1075                 cx,
1076                 MATCH_SINGLE_BINDING,
1077                 expr.span,
1078                 "this match could be replaced by its body itself",
1079                 "consider using the match body instead",
1080                 snippet_body,
1081                 Applicability::MachineApplicable,
1082             );
1083         },
1084         _ => (),
1085     }
1086 }
1087
1088 /// Returns true if the `ex` match expression is in a local (`let`) statement
1089 fn opt_parent_let<'a>(cx: &LateContext<'_, 'a>, ex: &Expr<'a>) -> Option<&'a Local<'a>> {
1090     if_chain! {
1091         let map = &cx.tcx.hir();
1092         if let Some(Node::Expr(parent_arm_expr)) = map.find(map.get_parent_node(ex.hir_id));
1093         if let Some(Node::Local(parent_let_expr)) = map.find(map.get_parent_node(parent_arm_expr.hir_id));
1094         then {
1095             return Some(parent_let_expr);
1096         }
1097     }
1098     None
1099 }
1100
1101 /// Gets all arms that are unbounded `PatRange`s.
1102 fn all_ranges<'a, 'tcx>(
1103     cx: &LateContext<'a, 'tcx>,
1104     arms: &'tcx [Arm<'_>],
1105     ty: Ty<'tcx>,
1106 ) -> Vec<SpannedRange<Constant>> {
1107     arms.iter()
1108         .flat_map(|arm| {
1109             if let Arm {
1110                 ref pat, guard: None, ..
1111             } = *arm
1112             {
1113                 if let PatKind::Range(ref lhs, ref rhs, range_end) = pat.kind {
1114                     let lhs = match lhs {
1115                         Some(lhs) => constant(cx, cx.tables, lhs)?.0,
1116                         None => miri_to_const(ty.numeric_min_val(cx.tcx)?)?,
1117                     };
1118                     let rhs = match rhs {
1119                         Some(rhs) => constant(cx, cx.tables, rhs)?.0,
1120                         None => miri_to_const(ty.numeric_max_val(cx.tcx)?)?,
1121                     };
1122                     let rhs = match range_end {
1123                         RangeEnd::Included => Bound::Included(rhs),
1124                         RangeEnd::Excluded => Bound::Excluded(rhs),
1125                     };
1126                     return Some(SpannedRange {
1127                         span: pat.span,
1128                         node: (lhs, rhs),
1129                     });
1130                 }
1131
1132                 if let PatKind::Lit(ref value) = pat.kind {
1133                     let value = constant(cx, cx.tables, value)?.0;
1134                     return Some(SpannedRange {
1135                         span: pat.span,
1136                         node: (value.clone(), Bound::Included(value)),
1137                     });
1138                 }
1139             }
1140             None
1141         })
1142         .collect()
1143 }
1144
1145 #[derive(Debug, Eq, PartialEq)]
1146 pub struct SpannedRange<T> {
1147     pub span: Span,
1148     pub node: (T, Bound<T>),
1149 }
1150
1151 type TypedRanges = Vec<SpannedRange<u128>>;
1152
1153 /// Gets all `Int` ranges or all `Uint` ranges. Mixed types are an error anyway
1154 /// and other types than
1155 /// `Uint` and `Int` probably don't make sense.
1156 fn type_ranges(ranges: &[SpannedRange<Constant>]) -> TypedRanges {
1157     ranges
1158         .iter()
1159         .filter_map(|range| match range.node {
1160             (Constant::Int(start), Bound::Included(Constant::Int(end))) => Some(SpannedRange {
1161                 span: range.span,
1162                 node: (start, Bound::Included(end)),
1163             }),
1164             (Constant::Int(start), Bound::Excluded(Constant::Int(end))) => Some(SpannedRange {
1165                 span: range.span,
1166                 node: (start, Bound::Excluded(end)),
1167             }),
1168             (Constant::Int(start), Bound::Unbounded) => Some(SpannedRange {
1169                 span: range.span,
1170                 node: (start, Bound::Unbounded),
1171             }),
1172             _ => None,
1173         })
1174         .collect()
1175 }
1176
1177 fn is_unit_expr(expr: &Expr<'_>) -> bool {
1178     match expr.kind {
1179         ExprKind::Tup(ref v) if v.is_empty() => true,
1180         ExprKind::Block(ref b, _) if b.stmts.is_empty() && b.expr.is_none() => true,
1181         _ => false,
1182     }
1183 }
1184
1185 // Checks if arm has the form `None => None`
1186 fn is_none_arm(arm: &Arm<'_>) -> bool {
1187     match arm.pat.kind {
1188         PatKind::Path(ref path) if match_qpath(path, &paths::OPTION_NONE) => true,
1189         _ => false,
1190     }
1191 }
1192
1193 // Checks if arm has the form `Some(ref v) => Some(v)` (checks for `ref` and `ref mut`)
1194 fn is_ref_some_arm(arm: &Arm<'_>) -> Option<BindingAnnotation> {
1195     if_chain! {
1196         if let PatKind::TupleStruct(ref path, ref pats, _) = arm.pat.kind;
1197         if pats.len() == 1 && match_qpath(path, &paths::OPTION_SOME);
1198         if let PatKind::Binding(rb, .., ident, _) = pats[0].kind;
1199         if rb == BindingAnnotation::Ref || rb == BindingAnnotation::RefMut;
1200         if let ExprKind::Call(ref e, ref args) = remove_blocks(&arm.body).kind;
1201         if let ExprKind::Path(ref some_path) = e.kind;
1202         if match_qpath(some_path, &paths::OPTION_SOME) && args.len() == 1;
1203         if let ExprKind::Path(ref qpath) = args[0].kind;
1204         if let &QPath::Resolved(_, ref path2) = qpath;
1205         if path2.segments.len() == 1 && ident.name == path2.segments[0].ident.name;
1206         then {
1207             return Some(rb)
1208         }
1209     }
1210     None
1211 }
1212
1213 fn has_only_ref_pats(arms: &[Arm<'_>]) -> bool {
1214     let mapped = arms
1215         .iter()
1216         .map(|a| {
1217             match a.pat.kind {
1218                 PatKind::Ref(..) => Some(true), // &-patterns
1219                 PatKind::Wild => Some(false),   // an "anything" wildcard is also fine
1220                 _ => None,                      // any other pattern is not fine
1221             }
1222         })
1223         .collect::<Option<Vec<bool>>>();
1224     // look for Some(v) where there's at least one true element
1225     mapped.map_or(false, |v| v.iter().any(|el| *el))
1226 }
1227
1228 pub fn overlapping<T>(ranges: &[SpannedRange<T>]) -> Option<(&SpannedRange<T>, &SpannedRange<T>)>
1229 where
1230     T: Copy + Ord,
1231 {
1232     #[derive(Copy, Clone, Debug, Eq, PartialEq)]
1233     enum Kind<'a, T> {
1234         Start(T, &'a SpannedRange<T>),
1235         End(Bound<T>, &'a SpannedRange<T>),
1236     }
1237
1238     impl<'a, T: Copy> Kind<'a, T> {
1239         fn range(&self) -> &'a SpannedRange<T> {
1240             match *self {
1241                 Kind::Start(_, r) | Kind::End(_, r) => r,
1242             }
1243         }
1244
1245         fn value(self) -> Bound<T> {
1246             match self {
1247                 Kind::Start(t, _) => Bound::Included(t),
1248                 Kind::End(t, _) => t,
1249             }
1250         }
1251     }
1252
1253     impl<'a, T: Copy + Ord> PartialOrd for Kind<'a, T> {
1254         fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1255             Some(self.cmp(other))
1256         }
1257     }
1258
1259     impl<'a, T: Copy + Ord> Ord for Kind<'a, T> {
1260         fn cmp(&self, other: &Self) -> Ordering {
1261             match (self.value(), other.value()) {
1262                 (Bound::Included(a), Bound::Included(b)) | (Bound::Excluded(a), Bound::Excluded(b)) => a.cmp(&b),
1263                 // Range patterns cannot be unbounded (yet)
1264                 (Bound::Unbounded, _) | (_, Bound::Unbounded) => unimplemented!(),
1265                 (Bound::Included(a), Bound::Excluded(b)) => match a.cmp(&b) {
1266                     Ordering::Equal => Ordering::Greater,
1267                     other => other,
1268                 },
1269                 (Bound::Excluded(a), Bound::Included(b)) => match a.cmp(&b) {
1270                     Ordering::Equal => Ordering::Less,
1271                     other => other,
1272                 },
1273             }
1274         }
1275     }
1276
1277     let mut values = Vec::with_capacity(2 * ranges.len());
1278
1279     for r in ranges {
1280         values.push(Kind::Start(r.node.0, r));
1281         values.push(Kind::End(r.node.1, r));
1282     }
1283
1284     values.sort();
1285
1286     for (a, b) in values.iter().zip(values.iter().skip(1)) {
1287         match (a, b) {
1288             (&Kind::Start(_, ra), &Kind::End(_, rb)) => {
1289                 if ra.node != rb.node {
1290                     return Some((ra, rb));
1291                 }
1292             },
1293             (&Kind::End(a, _), &Kind::Start(b, _)) if a != Bound::Included(b) => (),
1294             _ => return Some((a.range(), b.range())),
1295         }
1296     }
1297
1298     None
1299 }
1300
1301 #[test]
1302 fn test_overlapping() {
1303     use rustc_span::source_map::DUMMY_SP;
1304
1305     let sp = |s, e| SpannedRange {
1306         span: DUMMY_SP,
1307         node: (s, e),
1308     };
1309
1310     assert_eq!(None, overlapping::<u8>(&[]));
1311     assert_eq!(None, overlapping(&[sp(1, Bound::Included(4))]));
1312     assert_eq!(
1313         None,
1314         overlapping(&[sp(1, Bound::Included(4)), sp(5, Bound::Included(6))])
1315     );
1316     assert_eq!(
1317         None,
1318         overlapping(&[
1319             sp(1, Bound::Included(4)),
1320             sp(5, Bound::Included(6)),
1321             sp(10, Bound::Included(11))
1322         ],)
1323     );
1324     assert_eq!(
1325         Some((&sp(1, Bound::Included(4)), &sp(3, Bound::Included(6)))),
1326         overlapping(&[sp(1, Bound::Included(4)), sp(3, Bound::Included(6))])
1327     );
1328     assert_eq!(
1329         Some((&sp(5, Bound::Included(6)), &sp(6, Bound::Included(11)))),
1330         overlapping(&[
1331             sp(1, Bound::Included(4)),
1332             sp(5, Bound::Included(6)),
1333             sp(6, Bound::Included(11))
1334         ],)
1335     );
1336 }