1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 436 437 438 439 440 441 442 443 444 445 446 447 448 449 450 451 452 453 454 455 456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 482 483 484 485 486 487 488 489 490 491 492 493 494 495 496 497 498 499 500 501 502 503 504 505 506 507 508 509 510 511 512 513 514 515 516 517 518 519 520 521 522 523 524 525 526 527 528 529 530 531 532 533 534 535 536 537 538 539 540 541 542 543 544 545 546 547 548 549 550 551 552 553 554 555 556 557 558 559 560 561 562 563 564 565 566 567 568 569 570 571 572 573 574 575 576 577 578 579 580 581 582 583 584 585 586 587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637 638 639 640 641 642 643 644 645 646 647 648 649 650 651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015
//! Note: tests specific to this file can be found in:
//!
//! - `ui/pattern/usefulness`
//! - `ui/or-patterns`
//! - `ui/consts/const_in_pattern`
//! - `ui/rfc-2008-non-exhaustive`
//! - `ui/half-open-range-patterns`
//! - probably many others
//!
//! I (Nadrieril) prefer to put new tests in `ui/pattern/usefulness` unless there's a specific
//! reason not to, for example if they depend on a particular feature like `or_patterns`.
//!
//! -----
//!
//! This file includes the logic for exhaustiveness and reachability checking for pattern-matching.
//! Specifically, given a list of patterns for a type, we can tell whether:
//! (a) each pattern is reachable (reachability)
//! (b) the patterns cover every possible value for the type (exhaustiveness)
//!
//! The algorithm implemented here is a modified version of the one described in [this
//! paper](http://moscova.inria.fr/~maranget/papers/warn/index.html). We have however generalized
//! it to accommodate the variety of patterns that Rust supports. We thus explain our version here,
//! without being as rigorous.
//!
//!
//! # Summary
//!
//! The core of the algorithm is the notion of "usefulness". A pattern `q` is said to be *useful*
//! relative to another pattern `p` of the same type if there is a value that is matched by `q` and
//! not matched by `p`. This generalizes to many `p`s: `q` is useful w.r.t. a list of patterns
//! `p_1 .. p_n` if there is a value that is matched by `q` and by none of the `p_i`. We write
//! `usefulness(p_1 .. p_n, q)` for a function that returns a list of such values. The aim of this
//! file is to compute it efficiently.
//!
//! This is enough to compute reachability: a pattern in a `match` expression is reachable iff it
//! is useful w.r.t. the patterns above it:
//! ```rust
//! # fn foo(x: Option<i32>) {
//! match x {
//! Some(_) => {},
//! None => {}, // reachable: `None` is matched by this but not the branch above
//! Some(0) => {}, // unreachable: all the values this matches are already matched by
//! // `Some(_)` above
//! }
//! # }
//! ```
//!
//! This is also enough to compute exhaustiveness: a match is exhaustive iff the wildcard `_`
//! pattern is _not_ useful w.r.t. the patterns in the match. The values returned by `usefulness`
//! are used to tell the user which values are missing.
//! ```compile_fail,E0004
//! # fn foo(x: Option<i32>) {
//! match x {
//! Some(0) => {},
//! None => {},
//! // not exhaustive: `_` is useful because it matches `Some(1)`
//! }
//! # }
//! ```
//!
//! The entrypoint of this file is the [`compute_match_usefulness`] function, which computes
//! reachability for each match branch and exhaustiveness for the whole match.
//!
//!
//! # Constructors and fields
//!
//! Note: we will often abbreviate "constructor" as "ctor".
//!
//! The idea that powers everything that is done in this file is the following: a (matchable)
//! value is made from a constructor applied to a number of subvalues. Examples of constructors are
//! `Some`, `None`, `(,)` (the 2-tuple constructor), `Foo {..}` (the constructor for a struct
//! `Foo`), and `2` (the constructor for the number `2`). This is natural when we think of
//! pattern-matching, and this is the basis for what follows.
//!
//! Some of the ctors listed above might feel weird: `None` and `2` don't take any arguments.
//! That's ok: those are ctors that take a list of 0 arguments; they are the simplest case of
//! ctors. We treat `2` as a ctor because `u64` and other number types behave exactly like a huge
//! `enum`, with one variant for each number. This allows us to see any matchable value as made up
//! from a tree of ctors, each having a set number of children. For example: `Foo { bar: None,
//! baz: Ok(0) }` is made from 4 different ctors, namely `Foo{..}`, `None`, `Ok` and `0`.
//!
//! This idea can be extended to patterns: they are also made from constructors applied to fields.
//! A pattern for a given type is allowed to use all the ctors for values of that type (which we
//! call "value constructors"), but there are also pattern-only ctors. The most important one is
//! the wildcard (`_`), and the others are integer ranges (`0..=10`), variable-length slices (`[x,
//! ..]`), and or-patterns (`Ok(0) | Err(_)`). Examples of valid patterns are `42`, `Some(_)`, `Foo
//! { bar: Some(0) | None, baz: _ }`. Note that a binder in a pattern (e.g. `Some(x)`) matches the
//! same values as a wildcard (e.g. `Some(_)`), so we treat both as wildcards.
//!
//! From this deconstruction we can compute whether a given value matches a given pattern; we
//! simply look at ctors one at a time. Given a pattern `p` and a value `v`, we want to compute
//! `matches!(v, p)`. It's mostly straightforward: we compare the head ctors and when they match
//! we compare their fields recursively. A few representative examples:
//!
//! - `matches!(v, _) := true`
//! - `matches!((v0, v1), (p0, p1)) := matches!(v0, p0) && matches!(v1, p1)`
//! - `matches!(Foo { bar: v0, baz: v1 }, Foo { bar: p0, baz: p1 }) := matches!(v0, p0) && matches!(v1, p1)`
//! - `matches!(Ok(v0), Ok(p0)) := matches!(v0, p0)`
//! - `matches!(Ok(v0), Err(p0)) := false` (incompatible variants)
//! - `matches!(v, 1..=100) := matches!(v, 1) || ... || matches!(v, 100)`
//! - `matches!([v0], [p0, .., p1]) := false` (incompatible lengths)
//! - `matches!([v0, v1, v2], [p0, .., p1]) := matches!(v0, p0) && matches!(v2, p1)`
//! - `matches!(v, p0 | p1) := matches!(v, p0) || matches!(v, p1)`
//!
//! Constructors, fields and relevant operations are defined in the [`super::deconstruct_pat`] module.
//!
//! Note: this constructors/fields distinction may not straightforwardly apply to every Rust type.
//! For example a value of type `Rc<u64>` can't be deconstructed that way, and `&str` has an
//! infinitude of constructors. There are also subtleties with visibility of fields and
//! uninhabitedness and various other things. The constructors idea can be extended to handle most
//! of these subtleties though; caveats are documented where relevant throughout the code.
//!
//! Whether constructors cover each other is computed by [`Constructor::is_covered_by`].
//!
//!
//! # Specialization
//!
//! Recall that we wish to compute `usefulness(p_1 .. p_n, q)`: given a list of patterns `p_1 ..
//! p_n` and a pattern `q`, all of the same type, we want to find a list of values (called
//! "witnesses") that are matched by `q` and by none of the `p_i`. We obviously don't just
//! enumerate all possible values. From the discussion above we see that we can proceed
//! ctor-by-ctor: for each value ctor of the given type, we ask "is there a value that starts with
//! this constructor and matches `q` and none of the `p_i`?". As we saw above, there's a lot we can
//! say from knowing only the first constructor of our candidate value.
//!
//! Let's take the following example:
//! ```compile_fail,E0004
//! # enum Enum { Variant1(()), Variant2(Option<bool>, u32)}
//! # fn foo(x: Enum) {
//! match x {
//! Enum::Variant1(_) => {} // `p1`
//! Enum::Variant2(None, 0) => {} // `p2`
//! Enum::Variant2(Some(_), 0) => {} // `q`
//! }
//! # }
//! ```
//!
//! We can easily see that if our candidate value `v` starts with `Variant1` it will not match `q`.
//! If `v = Variant2(v0, v1)` however, whether or not it matches `p2` and `q` will depend on `v0`
//! and `v1`. In fact, such a `v` will be a witness of usefulness of `q` exactly when the tuple
//! `(v0, v1)` is a witness of usefulness of `q'` in the following reduced match:
//!
//! ```compile_fail,E0004
//! # fn foo(x: (Option<bool>, u32)) {
//! match x {
//! (None, 0) => {} // `p2'`
//! (Some(_), 0) => {} // `q'`
//! }
//! # }
//! ```
//!
//! This motivates a new step in computing usefulness, that we call _specialization_.
//! Specialization consist of filtering a list of patterns for those that match a constructor, and
//! then looking into the constructor's fields. This enables usefulness to be computed recursively.
//!
//! Instead of acting on a single pattern in each row, we will consider a list of patterns for each
//! row, and we call such a list a _pattern-stack_. The idea is that we will specialize the
//! leftmost pattern, which amounts to popping the constructor and pushing its fields, which feels
//! like a stack. We note a pattern-stack simply with `[p_1 ... p_n]`.
//! Here's a sequence of specializations of a list of pattern-stacks, to illustrate what's
//! happening:
//! ```ignore (illustrative)
//! [Enum::Variant1(_)]
//! [Enum::Variant2(None, 0)]
//! [Enum::Variant2(Some(_), 0)]
//! //==>> specialize with `Variant2`
//! [None, 0]
//! [Some(_), 0]
//! //==>> specialize with `Some`
//! [_, 0]
//! //==>> specialize with `true` (say the type was `bool`)
//! [0]
//! //==>> specialize with `0`
//! []
//! ```
//!
//! The function `specialize(c, p)` takes a value constructor `c` and a pattern `p`, and returns 0
//! or more pattern-stacks. If `c` does not match the head constructor of `p`, it returns nothing;
//! otherwise if returns the fields of the constructor. This only returns more than one
//! pattern-stack if `p` has a pattern-only constructor.
//!
//! - Specializing for the wrong constructor returns nothing
//!
//! `specialize(None, Some(p0)) := []`
//!
//! - Specializing for the correct constructor returns a single row with the fields
//!
//! `specialize(Variant1, Variant1(p0, p1, p2)) := [[p0, p1, p2]]`
//!
//! `specialize(Foo{..}, Foo { bar: p0, baz: p1 }) := [[p0, p1]]`
//!
//! - For or-patterns, we specialize each branch and concatenate the results
//!
//! `specialize(c, p0 | p1) := specialize(c, p0) ++ specialize(c, p1)`
//!
//! - We treat the other pattern constructors as if they were a large or-pattern of all the
//! possibilities:
//!
//! `specialize(c, _) := specialize(c, Variant1(_) | Variant2(_, _) | ...)`
//!
//! `specialize(c, 1..=100) := specialize(c, 1 | ... | 100)`
//!
//! `specialize(c, [p0, .., p1]) := specialize(c, [p0, p1] | [p0, _, p1] | [p0, _, _, p1] | ...)`
//!
//! - If `c` is a pattern-only constructor, `specialize` is defined on a case-by-case basis. See
//! the discussion about constructor splitting in [`super::deconstruct_pat`].
//!
//!
//! We then extend this function to work with pattern-stacks as input, by acting on the first
//! column and keeping the other columns untouched.
//!
//! Specialization for the whole matrix is done in [`Matrix::specialize_constructor`]. Note that
//! or-patterns in the first column are expanded before being stored in the matrix. Specialization
//! for a single patstack is done from a combination of [`Constructor::is_covered_by`] and
//! [`PatStack::pop_head_constructor`]. The internals of how it's done mostly live in the
//! [`Fields`] struct.
//!
//!
//! # Computing usefulness
//!
//! We now have all we need to compute usefulness. The inputs to usefulness are a list of
//! pattern-stacks `p_1 ... p_n` (one per row), and a new pattern_stack `q`. The paper and this
//! file calls the list of patstacks a _matrix_. They must all have the same number of columns and
//! the patterns in a given column must all have the same type. `usefulness` returns a (possibly
//! empty) list of witnesses of usefulness. These witnesses will also be pattern-stacks.
//!
//! - base case: `n_columns == 0`.
//! Since a pattern-stack functions like a tuple of patterns, an empty one functions like the
//! unit type. Thus `q` is useful iff there are no rows above it, i.e. if `n == 0`.
//!
//! - inductive case: `n_columns > 0`.
//! We need a way to list the constructors we want to try. We will be more clever in the next
//! section but for now assume we list all value constructors for the type of the first column.
//!
//! - for each such ctor `c`:
//!
//! - for each `q'` returned by `specialize(c, q)`:
//!
//! - we compute `usefulness(specialize(c, p_1) ... specialize(c, p_n), q')`
//!
//! - for each witness found, we revert specialization by pushing the constructor `c` on top.
//!
//! - We return the concatenation of all the witnesses found, if any.
//!
//! Example:
//! ```ignore (illustrative)
//! [Some(true)] // p_1
//! [None] // p_2
//! [Some(_)] // q
//! //==>> try `None`: `specialize(None, q)` returns nothing
//! //==>> try `Some`: `specialize(Some, q)` returns a single row
//! [true] // p_1'
//! [_] // q'
//! //==>> try `true`: `specialize(true, q')` returns a single row
//! [] // p_1''
//! [] // q''
//! //==>> base case; `n != 0` so `q''` is not useful.
//! //==>> go back up a step
//! [true] // p_1'
//! [_] // q'
//! //==>> try `false`: `specialize(false, q')` returns a single row
//! [] // q''
//! //==>> base case; `n == 0` so `q''` is useful. We return the single witness `[]`
//! witnesses:
//! []
//! //==>> undo the specialization with `false`
//! witnesses:
//! [false]
//! //==>> undo the specialization with `Some`
//! witnesses:
//! [Some(false)]
//! //==>> we have tried all the constructors. The output is the single witness `[Some(false)]`.
//! ```
//!
//! This computation is done in [`is_useful`]. In practice we don't care about the list of
//! witnesses when computing reachability; we only need to know whether any exist. We do keep the
//! witnesses when computing exhaustiveness to report them to the user.
//!
//!
//! # Making usefulness tractable: constructor splitting
//!
//! We're missing one last detail: which constructors do we list? Naively listing all value
//! constructors cannot work for types like `u64` or `&str`, so we need to be more clever. The
//! first obvious insight is that we only want to list constructors that are covered by the head
//! constructor of `q`. If it's a value constructor, we only try that one. If it's a pattern-only
//! constructor, we use the final clever idea for this algorithm: _constructor splitting_, where we
//! group together constructors that behave the same.
//!
//! The details are not necessary to understand this file, so we explain them in
//! [`super::deconstruct_pat`]. Splitting is done by the [`Constructor::split`] function.
//!
//! # Constants in patterns
//!
//! There are two kinds of constants in patterns:
//!
//! * literals (`1`, `true`, `"foo"`)
//! * named or inline consts (`FOO`, `const { 5 + 6 }`)
//!
//! The latter are converted into other patterns with literals at the leaves. For example
//! `const_to_pat(const { [1, 2, 3] })` becomes an `Array(vec![Const(1), Const(2), Const(3)])`
//! pattern. This gets problematic when comparing the constant via `==` would behave differently
//! from matching on the constant converted to a pattern. Situations like that can occur, when
//! the user implements `PartialEq` manually, and thus could make `==` behave arbitrarily different.
//! In order to honor the `==` implementation, constants of types that implement `PartialEq` manually
//! stay as a full constant and become an `Opaque` pattern. These `Opaque` patterns do not participate
//! in exhaustiveness, specialization or overlap checking.
use self::ArmType::*;
use self::Usefulness::*;
use super::deconstruct_pat::{Constructor, DeconstructedPat, Fields, SplitWildcard};
use crate::errors::{NonExhaustiveOmittedPattern, Uncovered};
use rustc_data_structures::captures::Captures;
use rustc_arena::TypedArena;
use rustc_data_structures::stack::ensure_sufficient_stack;
use rustc_hir::def_id::DefId;
use rustc_hir::HirId;
use rustc_middle::ty::{self, Ty, TyCtxt};
use rustc_session::lint::builtin::NON_EXHAUSTIVE_OMITTED_PATTERNS;
use rustc_span::{Span, DUMMY_SP};
use smallvec::{smallvec, SmallVec};
use std::fmt;
use std::iter::once;
pub(crate) struct MatchCheckCtxt<'p, 'tcx> {
pub(crate) tcx: TyCtxt<'tcx>,
/// The module in which the match occurs. This is necessary for
/// checking inhabited-ness of types because whether a type is (visibly)
/// inhabited can depend on whether it was defined in the current module or
/// not. E.g., `struct Foo { _private: ! }` cannot be seen to be empty
/// outside its module and should not be matchable with an empty match statement.
pub(crate) module: DefId,
pub(crate) param_env: ty::ParamEnv<'tcx>,
pub(crate) pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>,
/// Only produce `NON_EXHAUSTIVE_OMITTED_PATTERNS` lint on refutable patterns.
pub(crate) refutable: bool,
}
impl<'a, 'tcx> MatchCheckCtxt<'a, 'tcx> {
pub(super) fn is_uninhabited(&self, ty: Ty<'tcx>) -> bool {
if self.tcx.features().exhaustive_patterns {
!ty.is_inhabited_from(self.tcx, self.module, self.param_env)
} else {
false
}
}
/// Returns whether the given type is an enum from another crate declared `#[non_exhaustive]`.
pub(super) fn is_foreign_non_exhaustive_enum(&self, ty: Ty<'tcx>) -> bool {
match ty.kind() {
ty::Adt(def, ..) => {
def.is_enum() && def.is_variant_list_non_exhaustive() && !def.did().is_local()
}
_ => false,
}
}
}
#[derive(Copy, Clone)]
pub(super) struct PatCtxt<'a, 'p, 'tcx> {
pub(super) cx: &'a MatchCheckCtxt<'p, 'tcx>,
/// Type of the current column under investigation.
pub(super) ty: Ty<'tcx>,
/// Span of the current pattern under investigation.
pub(super) span: Span,
/// Whether the current pattern is the whole pattern as found in a match arm, or if it's a
/// subpattern.
pub(super) is_top_level: bool,
/// Whether the current pattern is from a `non_exhaustive` enum.
pub(super) is_non_exhaustive: bool,
}
impl<'a, 'p, 'tcx> fmt::Debug for PatCtxt<'a, 'p, 'tcx> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_struct("PatCtxt").field("ty", &self.ty).finish()
}
}
/// A row of a matrix. Rows of len 1 are very common, which is why `SmallVec[_; 2]`
/// works well.
#[derive(Clone)]
pub(crate) struct PatStack<'p, 'tcx> {
pub(crate) pats: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>,
}
impl<'p, 'tcx> PatStack<'p, 'tcx> {
fn from_pattern(pat: &'p DeconstructedPat<'p, 'tcx>) -> Self {
Self::from_vec(smallvec![pat])
}
fn from_vec(vec: SmallVec<[&'p DeconstructedPat<'p, 'tcx>; 2]>) -> Self {
PatStack { pats: vec }
}
fn is_empty(&self) -> bool {
self.pats.is_empty()
}
fn len(&self) -> usize {
self.pats.len()
}
fn head(&self) -> &'p DeconstructedPat<'p, 'tcx> {
self.pats[0]
}
fn iter(&self) -> impl Iterator<Item = &DeconstructedPat<'p, 'tcx>> {
self.pats.iter().copied()
}
// Recursively expand the first pattern into its subpatterns. Only useful if the pattern is an
// or-pattern. Panics if `self` is empty.
fn expand_or_pat<'a>(&'a self) -> impl Iterator<Item = PatStack<'p, 'tcx>> + Captures<'a> {
self.head().iter_fields().map(move |pat| {
let mut new_patstack = PatStack::from_pattern(pat);
new_patstack.pats.extend_from_slice(&self.pats[1..]);
new_patstack
})
}
// Recursively expand all patterns into their subpatterns and push each `PatStack` to matrix.
fn expand_and_extend<'a>(&'a self, matrix: &mut Matrix<'p, 'tcx>) {
if !self.is_empty() && self.head().is_or_pat() {
for pat in self.head().iter_fields() {
let mut new_patstack = PatStack::from_pattern(pat);
new_patstack.pats.extend_from_slice(&self.pats[1..]);
if !new_patstack.is_empty() && new_patstack.head().is_or_pat() {
new_patstack.expand_and_extend(matrix);
} else if !new_patstack.is_empty() {
matrix.push(new_patstack);
}
}
}
}
/// This computes `S(self.head().ctor(), self)`. See top of the file for explanations.
///
/// Structure patterns with a partial wild pattern (Foo { a: 42, .. }) have their missing
/// fields filled with wild patterns.
///
/// This is roughly the inverse of `Constructor::apply`.
fn pop_head_constructor(
&self,
pcx: &PatCtxt<'_, 'p, 'tcx>,
ctor: &Constructor<'tcx>,
) -> PatStack<'p, 'tcx> {
// We pop the head pattern and push the new fields extracted from the arguments of
// `self.head()`.
let mut new_fields: SmallVec<[_; 2]> = self.head().specialize(pcx, ctor);
new_fields.extend_from_slice(&self.pats[1..]);
PatStack::from_vec(new_fields)
}
}
/// Pretty-printing for matrix row.
impl<'p, 'tcx> fmt::Debug for PatStack<'p, 'tcx> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "+")?;
for pat in self.iter() {
write!(f, " {pat:?} +")?;
}
Ok(())
}
}
/// A 2D matrix.
#[derive(Clone)]
pub(super) struct Matrix<'p, 'tcx> {
pub patterns: Vec<PatStack<'p, 'tcx>>,
}
impl<'p, 'tcx> Matrix<'p, 'tcx> {
fn empty() -> Self {
Matrix { patterns: vec![] }
}
/// Number of columns of this matrix. `None` is the matrix is empty.
pub(super) fn column_count(&self) -> Option<usize> {
self.patterns.get(0).map(|r| r.len())
}
/// Pushes a new row to the matrix. If the row starts with an or-pattern, this recursively
/// expands it.
fn push(&mut self, row: PatStack<'p, 'tcx>) {
if !row.is_empty() && row.head().is_or_pat() {
row.expand_and_extend(self);
} else {
self.patterns.push(row);
}
}
/// Iterate over the first component of each row
fn heads<'a>(
&'a self,
) -> impl Iterator<Item = &'p DeconstructedPat<'p, 'tcx>> + Clone + Captures<'a> {
self.patterns.iter().map(|r| r.head())
}
/// This computes `S(constructor, self)`. See top of the file for explanations.
fn specialize_constructor(
&self,
pcx: &PatCtxt<'_, 'p, 'tcx>,
ctor: &Constructor<'tcx>,
) -> Matrix<'p, 'tcx> {
let mut matrix = Matrix::empty();
for row in &self.patterns {
if ctor.is_covered_by(pcx, row.head().ctor()) {
let new_row = row.pop_head_constructor(pcx, ctor);
matrix.push(new_row);
}
}
matrix
}
}
/// Pretty-printer for matrices of patterns, example:
///
/// ```text
/// + _ + [] +
/// + true + [First] +
/// + true + [Second(true)] +
/// + false + [_] +
/// + _ + [_, _, tail @ ..] +
/// ```
impl<'p, 'tcx> fmt::Debug for Matrix<'p, 'tcx> {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
write!(f, "\n")?;
let Matrix { patterns: m, .. } = self;
let pretty_printed_matrix: Vec<Vec<String>> =
m.iter().map(|row| row.iter().map(|pat| format!("{pat:?}")).collect()).collect();
let column_count = m.iter().map(|row| row.len()).next().unwrap_or(0);
assert!(m.iter().all(|row| row.len() == column_count));
let column_widths: Vec<usize> = (0..column_count)
.map(|col| pretty_printed_matrix.iter().map(|row| row[col].len()).max().unwrap_or(0))
.collect();
for row in pretty_printed_matrix {
write!(f, "+")?;
for (column, pat_str) in row.into_iter().enumerate() {
write!(f, " ")?;
write!(f, "{:1$}", pat_str, column_widths[column])?;
write!(f, " +")?;
}
write!(f, "\n")?;
}
Ok(())
}
}
/// This carries the results of computing usefulness, as described at the top of the file. When
/// checking usefulness of a match branch, we use the `NoWitnesses` variant, which also keeps track
/// of potential unreachable sub-patterns (in the presence of or-patterns). When checking
/// exhaustiveness of a whole match, we use the `WithWitnesses` variant, which carries a list of
/// witnesses of non-exhaustiveness when there are any.
/// Which variant to use is dictated by `ArmType`.
#[derive(Debug)]
enum Usefulness<'p, 'tcx> {
/// If we don't care about witnesses, simply remember if the pattern was useful.
NoWitnesses { useful: bool },
/// Carries a list of witnesses of non-exhaustiveness. If empty, indicates that the whole
/// pattern is unreachable.
WithWitnesses(Vec<Witness<'p, 'tcx>>),
}
impl<'p, 'tcx> Usefulness<'p, 'tcx> {
fn new_useful(preference: ArmType) -> Self {
match preference {
// A single (empty) witness of reachability.
FakeExtraWildcard => WithWitnesses(vec![Witness(vec![])]),
RealArm => NoWitnesses { useful: true },
}
}
fn new_not_useful(preference: ArmType) -> Self {
match preference {
FakeExtraWildcard => WithWitnesses(vec![]),
RealArm => NoWitnesses { useful: false },
}
}
fn is_useful(&self) -> bool {
match self {
Usefulness::NoWitnesses { useful } => *useful,
Usefulness::WithWitnesses(witnesses) => !witnesses.is_empty(),
}
}
/// Combine usefulnesses from two branches. This is an associative operation.
fn extend(&mut self, other: Self) {
match (&mut *self, other) {
(WithWitnesses(_), WithWitnesses(o)) if o.is_empty() => {}
(WithWitnesses(s), WithWitnesses(o)) if s.is_empty() => *self = WithWitnesses(o),
(WithWitnesses(s), WithWitnesses(o)) => s.extend(o),
(NoWitnesses { useful: s_useful }, NoWitnesses { useful: o_useful }) => {
*s_useful = *s_useful || o_useful
}
_ => unreachable!(),
}
}
/// After calculating usefulness after a specialization, call this to reconstruct a usefulness
/// that makes sense for the matrix pre-specialization. This new usefulness can then be merged
/// with the results of specializing with the other constructors.
fn apply_constructor(
self,
pcx: &PatCtxt<'_, 'p, 'tcx>,
matrix: &Matrix<'p, 'tcx>, // used to compute missing ctors
ctor: &Constructor<'tcx>,
) -> Self {
match self {
NoWitnesses { .. } => self,
WithWitnesses(ref witnesses) if witnesses.is_empty() => self,
WithWitnesses(witnesses) => {
let new_witnesses = if let Constructor::Missing { .. } = ctor {
// We got the special `Missing` constructor, so each of the missing constructors
// gives a new pattern that is not caught by the match. We list those patterns.
if pcx.is_non_exhaustive {
witnesses
.into_iter()
// Here we don't want the user to try to list all variants, we want them to add
// a wildcard, so we only suggest that.
.map(|witness| {
witness.apply_constructor(pcx, &Constructor::NonExhaustive)
})
.collect()
} else {
let mut split_wildcard = SplitWildcard::new(pcx);
split_wildcard.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
// This lets us know if we skipped any variants because they are marked
// `doc(hidden)` or they are unstable feature gate (only stdlib types).
let mut hide_variant_show_wild = false;
// Construct for each missing constructor a "wild" version of this
// constructor, that matches everything that can be built with
// it. For example, if `ctor` is a `Constructor::Variant` for
// `Option::Some`, we get the pattern `Some(_)`.
let mut new_patterns: Vec<DeconstructedPat<'_, '_>> = split_wildcard
.iter_missing(pcx)
.filter_map(|missing_ctor| {
// Check if this variant is marked `doc(hidden)`
if missing_ctor.is_doc_hidden_variant(pcx)
|| missing_ctor.is_unstable_variant(pcx)
{
hide_variant_show_wild = true;
return None;
}
Some(DeconstructedPat::wild_from_ctor(pcx, missing_ctor.clone()))
})
.collect();
if hide_variant_show_wild {
new_patterns.push(DeconstructedPat::wildcard(pcx.ty, pcx.span));
}
witnesses
.into_iter()
.flat_map(|witness| {
new_patterns.iter().map(move |pat| {
Witness(
witness
.0
.iter()
.chain(once(pat))
.map(DeconstructedPat::clone_and_forget_reachability)
.collect(),
)
})
})
.collect()
}
} else {
witnesses
.into_iter()
.map(|witness| witness.apply_constructor(pcx, &ctor))
.collect()
};
WithWitnesses(new_witnesses)
}
}
}
}
#[derive(Copy, Clone, Debug)]
enum ArmType {
FakeExtraWildcard,
RealArm,
}
/// A witness of non-exhaustiveness for error reporting, represented
/// as a list of patterns (in reverse order of construction) with
/// wildcards inside to represent elements that can take any inhabitant
/// of the type as a value.
///
/// A witness against a list of patterns should have the same types
/// and length as the pattern matched against. Because Rust `match`
/// is always against a single pattern, at the end the witness will
/// have length 1, but in the middle of the algorithm, it can contain
/// multiple patterns.
///
/// For example, if we are constructing a witness for the match against
///
/// ```compile_fail,E0004
/// struct Pair(Option<(u32, u32)>, bool);
/// # fn foo(p: Pair) {
/// match p {
/// Pair(None, _) => {}
/// Pair(_, false) => {}
/// }
/// # }
/// ```
///
/// We'll perform the following steps:
/// 1. Start with an empty witness
/// `Witness(vec![])`
/// 2. Push a witness `true` against the `false`
/// `Witness(vec![true])`
/// 3. Push a witness `Some(_)` against the `None`
/// `Witness(vec![true, Some(_)])`
/// 4. Apply the `Pair` constructor to the witnesses
/// `Witness(vec![Pair(Some(_), true)])`
///
/// The final `Pair(Some(_), true)` is then the resulting witness.
#[derive(Debug)]
pub(crate) struct Witness<'p, 'tcx>(Vec<DeconstructedPat<'p, 'tcx>>);
impl<'p, 'tcx> Witness<'p, 'tcx> {
/// Asserts that the witness contains a single pattern, and returns it.
fn single_pattern(self) -> DeconstructedPat<'p, 'tcx> {
assert_eq!(self.0.len(), 1);
self.0.into_iter().next().unwrap()
}
/// Constructs a partial witness for a pattern given a list of
/// patterns expanded by the specialization step.
///
/// When a pattern P is discovered to be useful, this function is used bottom-up
/// to reconstruct a complete witness, e.g., a pattern P' that covers a subset
/// of values, V, where each value in that set is not covered by any previously
/// used patterns and is covered by the pattern P'. Examples:
///
/// left_ty: tuple of 3 elements
/// pats: [10, 20, _] => (10, 20, _)
///
/// left_ty: struct X { a: (bool, &'static str), b: usize}
/// pats: [(false, "foo"), 42] => X { a: (false, "foo"), b: 42 }
fn apply_constructor(mut self, pcx: &PatCtxt<'_, 'p, 'tcx>, ctor: &Constructor<'tcx>) -> Self {
let pat = {
let len = self.0.len();
let arity = ctor.arity(pcx);
let pats = self.0.drain((len - arity)..).rev();
let fields = Fields::from_iter(pcx.cx, pats);
DeconstructedPat::new(ctor.clone(), fields, pcx.ty, pcx.span)
};
self.0.push(pat);
self
}
}
/// Algorithm from <http://moscova.inria.fr/~maranget/papers/warn/index.html>.
/// The algorithm from the paper has been modified to correctly handle empty
/// types. The changes are:
/// (0) We don't exit early if the pattern matrix has zero rows. We just
/// continue to recurse over columns.
/// (1) all_constructors will only return constructors that are statically
/// possible. E.g., it will only return `Ok` for `Result<T, !>`.
///
/// This finds whether a (row) vector `v` of patterns is 'useful' in relation
/// to a set of such vectors `m` - this is defined as there being a set of
/// inputs that will match `v` but not any of the sets in `m`.
///
/// All the patterns at each column of the `matrix ++ v` matrix must have the same type.
///
/// This is used both for reachability checking (if a pattern isn't useful in
/// relation to preceding patterns, it is not reachable) and exhaustiveness
/// checking (if a wildcard pattern is useful in relation to a matrix, the
/// matrix isn't exhaustive).
///
/// `is_under_guard` is used to inform if the pattern has a guard. If it
/// has one it must not be inserted into the matrix. This shouldn't be
/// relied on for soundness.
#[instrument(level = "debug", skip(cx, matrix, lint_root), ret)]
fn is_useful<'p, 'tcx>(
cx: &MatchCheckCtxt<'p, 'tcx>,
matrix: &Matrix<'p, 'tcx>,
v: &PatStack<'p, 'tcx>,
witness_preference: ArmType,
lint_root: HirId,
is_under_guard: bool,
is_top_level: bool,
) -> Usefulness<'p, 'tcx> {
debug!(?matrix, ?v);
let Matrix { patterns: rows, .. } = matrix;
// The base case. We are pattern-matching on () and the return value is
// based on whether our matrix has a row or not.
// NOTE: This could potentially be optimized by checking rows.is_empty()
// first and then, if v is non-empty, the return value is based on whether
// the type of the tuple we're checking is inhabited or not.
if v.is_empty() {
let ret = if rows.is_empty() {
Usefulness::new_useful(witness_preference)
} else {
Usefulness::new_not_useful(witness_preference)
};
debug!(?ret);
return ret;
}
debug_assert!(rows.iter().all(|r| r.len() == v.len()));
// If the first pattern is an or-pattern, expand it.
let mut ret = Usefulness::new_not_useful(witness_preference);
if v.head().is_or_pat() {
debug!("expanding or-pattern");
// We try each or-pattern branch in turn.
let mut matrix = matrix.clone();
for v in v.expand_or_pat() {
debug!(?v);
let usefulness = ensure_sufficient_stack(|| {
is_useful(cx, &matrix, &v, witness_preference, lint_root, is_under_guard, false)
});
debug!(?usefulness);
ret.extend(usefulness);
// If pattern has a guard don't add it to the matrix.
if !is_under_guard {
// We push the already-seen patterns into the matrix in order to detect redundant
// branches like `Some(_) | Some(0)`.
matrix.push(v);
}
}
} else {
let mut ty = v.head().ty();
// Opaque types can't get destructured/split, but the patterns can
// actually hint at hidden types, so we use the patterns' types instead.
if let ty::Alias(ty::Opaque, ..) = ty.kind() {
if let Some(row) = rows.first() {
ty = row.head().ty();
}
}
let is_non_exhaustive = cx.is_foreign_non_exhaustive_enum(ty);
debug!("v.head: {:?}, v.span: {:?}", v.head(), v.head().span());
let pcx = &PatCtxt { cx, ty, span: v.head().span(), is_top_level, is_non_exhaustive };
let v_ctor = v.head().ctor();
debug!(?v_ctor);
if let Constructor::IntRange(ctor_range) = &v_ctor {
// Lint on likely incorrect range patterns (#63987)
ctor_range.lint_overlapping_range_endpoints(
pcx,
matrix.heads(),
matrix.column_count().unwrap_or(0),
lint_root,
)
}
// We split the head constructor of `v`.
let split_ctors = v_ctor.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
let is_non_exhaustive_and_wild = is_non_exhaustive && v_ctor.is_wildcard();
// For each constructor, we compute whether there's a value that starts with it that would
// witness the usefulness of `v`.
let start_matrix = &matrix;
for ctor in split_ctors {
debug!("specialize({:?})", ctor);
// We cache the result of `Fields::wildcards` because it is used a lot.
let spec_matrix = start_matrix.specialize_constructor(pcx, &ctor);
let v = v.pop_head_constructor(pcx, &ctor);
let usefulness = ensure_sufficient_stack(|| {
is_useful(
cx,
&spec_matrix,
&v,
witness_preference,
lint_root,
is_under_guard,
false,
)
});
let usefulness = usefulness.apply_constructor(pcx, start_matrix, &ctor);
// When all the conditions are met we have a match with a `non_exhaustive` enum
// that has the potential to trigger the `non_exhaustive_omitted_patterns` lint.
// To understand the workings checkout `Constructor::split` and `SplitWildcard::new/into_ctors`
if is_non_exhaustive_and_wild
// Only emit a lint on refutable patterns.
&& cx.refutable
// We check that the match has a wildcard pattern and that wildcard is useful,
// meaning there are variants that are covered by the wildcard. Without the check
// for `witness_preference` the lint would trigger on `if let NonExhaustiveEnum::A = foo {}`
&& usefulness.is_useful() && matches!(witness_preference, RealArm)
&& matches!(
&ctor,
Constructor::Missing { nonexhaustive_enum_missing_real_variants: true }
)
{
let patterns = {
let mut split_wildcard = SplitWildcard::new(pcx);
split_wildcard.split(pcx, matrix.heads().map(DeconstructedPat::ctor));
// Construct for each missing constructor a "wild" version of this
// constructor, that matches everything that can be built with
// it. For example, if `ctor` is a `Constructor::Variant` for
// `Option::Some`, we get the pattern `Some(_)`.
split_wildcard
.iter_missing(pcx)
// Filter out the `NonExhaustive` because we want to list only real
// variants. Also remove any unstable feature gated variants.
// Because of how we computed `nonexhaustive_enum_missing_real_variants`,
// this will not return an empty `Vec`.
.filter(|c| !(c.is_non_exhaustive() || c.is_unstable_variant(pcx)))
.cloned()
.map(|missing_ctor| DeconstructedPat::wild_from_ctor(pcx, missing_ctor))
.collect::<Vec<_>>()
};
// Report that a match of a `non_exhaustive` enum marked with `non_exhaustive_omitted_patterns`
// is not exhaustive enough.
//
// NB: The partner lint for structs lives in `compiler/rustc_hir_analysis/src/check/pat.rs`.
cx.tcx.emit_spanned_lint(
NON_EXHAUSTIVE_OMITTED_PATTERNS,
lint_root,
pcx.span,
NonExhaustiveOmittedPattern {
scrut_ty: pcx.ty,
uncovered: Uncovered::new(pcx.span, pcx.cx, patterns),
},
);
}
ret.extend(usefulness);
}
}
if ret.is_useful() {
v.head().set_reachable();
}
ret
}
/// The arm of a match expression.
#[derive(Clone, Copy, Debug)]
pub(crate) struct MatchArm<'p, 'tcx> {
/// The pattern must have been lowered through `check_match::MatchVisitor::lower_pattern`.
pub(crate) pat: &'p DeconstructedPat<'p, 'tcx>,
pub(crate) hir_id: HirId,
pub(crate) has_guard: bool,
}
/// Indicates whether or not a given arm is reachable.
#[derive(Clone, Debug)]
pub(crate) enum Reachability {
/// The arm is reachable. This additionally carries a set of or-pattern branches that have been
/// found to be unreachable despite the overall arm being reachable. Used only in the presence
/// of or-patterns, otherwise it stays empty.
Reachable(Vec<Span>),
/// The arm is unreachable.
Unreachable,
}
/// The output of checking a match for exhaustiveness and arm reachability.
pub(crate) struct UsefulnessReport<'p, 'tcx> {
/// For each arm of the input, whether that arm is reachable after the arms above it.
pub(crate) arm_usefulness: Vec<(MatchArm<'p, 'tcx>, Reachability)>,
/// If the match is exhaustive, this is empty. If not, this contains witnesses for the lack of
/// exhaustiveness.
pub(crate) non_exhaustiveness_witnesses: Vec<DeconstructedPat<'p, 'tcx>>,
}
/// The entrypoint for the usefulness algorithm. Computes whether a match is exhaustive and which
/// of its arms are reachable.
///
/// Note: the input patterns must have been lowered through
/// `check_match::MatchVisitor::lower_pattern`.
#[instrument(skip(cx, arms), level = "debug")]
pub(crate) fn compute_match_usefulness<'p, 'tcx>(
cx: &MatchCheckCtxt<'p, 'tcx>,
arms: &[MatchArm<'p, 'tcx>],
lint_root: HirId,
scrut_ty: Ty<'tcx>,
) -> UsefulnessReport<'p, 'tcx> {
let mut matrix = Matrix::empty();
let arm_usefulness: Vec<_> = arms
.iter()
.copied()
.map(|arm| {
debug!(?arm);
let v = PatStack::from_pattern(arm.pat);
is_useful(cx, &matrix, &v, RealArm, arm.hir_id, arm.has_guard, true);
if !arm.has_guard {
matrix.push(v);
}
let reachability = if arm.pat.is_reachable() {
Reachability::Reachable(arm.pat.unreachable_spans())
} else {
Reachability::Unreachable
};
(arm, reachability)
})
.collect();
let wild_pattern = cx.pattern_arena.alloc(DeconstructedPat::wildcard(scrut_ty, DUMMY_SP));
let v = PatStack::from_pattern(wild_pattern);
let usefulness = is_useful(cx, &matrix, &v, FakeExtraWildcard, lint_root, false, true);
let non_exhaustiveness_witnesses = match usefulness {
WithWitnesses(pats) => pats.into_iter().map(|w| w.single_pattern()).collect(),
NoWitnesses { .. } => bug!(),
};
UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses }
}