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