| #![allow(dead_code, unreachable_pub)] | |
| use rustc_pattern_analysis::constructor::{ | |
| Constructor, ConstructorSet, IntRange, MaybeInfiniteInt, RangeEnd, VariantVisibility, | |
| }; | |
| use rustc_pattern_analysis::pat::DeconstructedPat; | |
| use rustc_pattern_analysis::usefulness::{PlaceValidity, UsefulnessReport}; | |
| use rustc_pattern_analysis::{MatchArm, PatCx, PrivateUninhabitedField}; | |
| /// Sets up `tracing` for easier debugging. Tries to look like the `rustc` setup. | |
| fn init_tracing() { | |
| use tracing_subscriber::Layer; | |
| use tracing_subscriber::layer::SubscriberExt; | |
| use tracing_subscriber::util::SubscriberInitExt; | |
| let _ = tracing_tree::HierarchicalLayer::default() | |
| .with_writer(std::io::stderr) | |
| .with_ansi(true) | |
| .with_targets(true) | |
| .with_indent_amount(2) | |
| .with_subscriber( | |
| tracing_subscriber::Registry::default() | |
| .with(tracing_subscriber::EnvFilter::from_default_env()), | |
| ) | |
| .try_init(); | |
| } | |
| pub(super) const UNIT: Ty = Ty::Tuple(&[]); | |
| pub(super) const NEVER: Ty = Ty::Enum(&[]); | |
| /// A simple set of types. | |
| #[derive(Debug, Copy, Clone, PartialEq, Eq)] | |
| pub(super) enum Ty { | |
| /// Booleans | |
| Bool, | |
| /// 8-bit unsigned integers | |
| U8, | |
| /// Tuples. | |
| Tuple(&'static [Ty]), | |
| /// Enum with one variant of each given type. | |
| Enum(&'static [Ty]), | |
| /// A struct with `arity` fields of type `ty`. | |
| BigStruct { arity: usize, ty: &'static Ty }, | |
| /// A enum with `arity` variants of type `ty`. | |
| BigEnum { arity: usize, ty: &'static Ty }, | |
| /// Like `Enum` but non-exhaustive. | |
| NonExhaustiveEnum(&'static [Ty]), | |
| } | |
| /// The important logic. | |
| impl Ty { | |
| pub(super) fn sub_tys(&self, ctor: &Constructor<Cx>) -> Vec<Self> { | |
| use Constructor::*; | |
| match (ctor, *self) { | |
| (Struct, Ty::Tuple(tys)) => tys.iter().copied().collect(), | |
| (Struct, Ty::BigStruct { arity, ty }) => (0..arity).map(|_| *ty).collect(), | |
| (Variant(i), Ty::Enum(tys) | Ty::NonExhaustiveEnum(tys)) => vec![tys[*i]], | |
| (Variant(_), Ty::BigEnum { ty, .. }) => vec![*ty], | |
| (Bool(..) | IntRange(..) | NonExhaustive | Missing | Wildcard, _) => vec![], | |
| _ => panic!("Unexpected ctor {ctor:?} for type {self:?}"), | |
| } | |
| } | |
| fn is_empty(&self) -> bool { | |
| match *self { | |
| Ty::Bool | Ty::U8 => false, | |
| Ty::Tuple(tys) => tys.iter().any(|ty| ty.is_empty()), | |
| Ty::Enum(tys) => tys.iter().all(|ty| ty.is_empty()), | |
| Ty::BigStruct { arity, ty } => arity != 0 && ty.is_empty(), | |
| Ty::BigEnum { arity, ty } => arity == 0 || ty.is_empty(), | |
| Ty::NonExhaustiveEnum(..) => false, | |
| } | |
| } | |
| fn ctor_set(&self) -> ConstructorSet<Cx> { | |
| match *self { | |
| Ty::Bool => ConstructorSet::Bool, | |
| Ty::U8 => ConstructorSet::Integers { | |
| range_1: IntRange::from_range( | |
| MaybeInfiniteInt::new_finite_uint(0), | |
| MaybeInfiniteInt::new_finite_uint(255), | |
| RangeEnd::Included, | |
| ), | |
| range_2: None, | |
| }, | |
| Ty::Tuple(..) | Ty::BigStruct { .. } => ConstructorSet::Struct { empty: false }, | |
| Ty::Enum(tys) if tys.is_empty() => ConstructorSet::NoConstructors, | |
| Ty::Enum(tys) => ConstructorSet::Variants { | |
| variants: tys | |
| .iter() | |
| .map(|ty| { | |
| if ty.is_empty() { | |
| VariantVisibility::Empty | |
| } else { | |
| VariantVisibility::Visible | |
| } | |
| }) | |
| .collect(), | |
| non_exhaustive: false, | |
| }, | |
| Ty::NonExhaustiveEnum(tys) => ConstructorSet::Variants { | |
| variants: tys | |
| .iter() | |
| .map(|ty| { | |
| if ty.is_empty() { | |
| VariantVisibility::Empty | |
| } else { | |
| VariantVisibility::Visible | |
| } | |
| }) | |
| .collect(), | |
| non_exhaustive: true, | |
| }, | |
| Ty::BigEnum { arity: 0, .. } => ConstructorSet::NoConstructors, | |
| Ty::BigEnum { arity, ty } => { | |
| let vis = if ty.is_empty() { | |
| VariantVisibility::Empty | |
| } else { | |
| VariantVisibility::Visible | |
| }; | |
| ConstructorSet::Variants { | |
| variants: (0..arity).map(|_| vis).collect(), | |
| non_exhaustive: false, | |
| } | |
| } | |
| } | |
| } | |
| fn write_variant_name( | |
| &self, | |
| f: &mut std::fmt::Formatter<'_>, | |
| ctor: &Constructor<Cx>, | |
| ) -> std::fmt::Result { | |
| match (*self, ctor) { | |
| (Ty::Tuple(..), _) => Ok(()), | |
| (Ty::BigStruct { .. }, _) => write!(f, "BigStruct"), | |
| (Ty::Enum(..) | Ty::NonExhaustiveEnum(..), Constructor::Variant(i)) => { | |
| write!(f, "Enum::Variant{i}") | |
| } | |
| (Ty::BigEnum { .. }, Constructor::Variant(i)) => write!(f, "BigEnum::Variant{i}"), | |
| _ => write!(f, "{:?}::{:?}", self, ctor), | |
| } | |
| } | |
| } | |
| /// Compute usefulness in our simple context (and set up tracing for easier debugging). | |
| pub(super) fn compute_match_usefulness<'p>( | |
| arms: &[MatchArm<'p, Cx>], | |
| ty: Ty, | |
| scrut_validity: PlaceValidity, | |
| complexity_limit: usize, | |
| exhaustive_witnesses: bool, | |
| ) -> Result<UsefulnessReport<'p, Cx>, ()> { | |
| init_tracing(); | |
| rustc_pattern_analysis::usefulness::compute_match_usefulness( | |
| &Cx { exhaustive_witnesses }, | |
| arms, | |
| ty, | |
| scrut_validity, | |
| complexity_limit, | |
| ) | |
| } | |
| #[derive(Debug)] | |
| pub(super) struct Cx { | |
| exhaustive_witnesses: bool, | |
| } | |
| /// The context for pattern analysis. Forwards anything interesting to `Ty` methods. | |
| impl PatCx for Cx { | |
| type Ty = Ty; | |
| type Error = (); | |
| type VariantIdx = usize; | |
| type StrLit = (); | |
| type ArmData = (); | |
| type PatData = (); | |
| fn is_exhaustive_patterns_feature_on(&self) -> bool { | |
| false | |
| } | |
| fn exhaustive_witnesses(&self) -> bool { | |
| self.exhaustive_witnesses | |
| } | |
| fn ctor_arity(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> usize { | |
| ty.sub_tys(ctor).len() | |
| } | |
| fn ctor_sub_tys( | |
| &self, | |
| ctor: &Constructor<Self>, | |
| ty: &Self::Ty, | |
| ) -> impl Iterator<Item = (Self::Ty, PrivateUninhabitedField)> + ExactSizeIterator { | |
| ty.sub_tys(ctor).into_iter().map(|ty| (ty, PrivateUninhabitedField(false))) | |
| } | |
| fn ctors_for_ty(&self, ty: &Self::Ty) -> Result<ConstructorSet<Self>, Self::Error> { | |
| Ok(ty.ctor_set()) | |
| } | |
| fn write_variant_name( | |
| f: &mut std::fmt::Formatter<'_>, | |
| ctor: &Constructor<Self>, | |
| ty: &Self::Ty, | |
| ) -> std::fmt::Result { | |
| ty.write_variant_name(f, ctor) | |
| } | |
| fn bug(&self, fmt: std::fmt::Arguments<'_>) -> Self::Error { | |
| panic!("{}", fmt) | |
| } | |
| /// Abort when reaching the complexity limit. This is what we'll check in tests. | |
| fn complexity_exceeded(&self) -> Result<(), Self::Error> { | |
| Err(()) | |
| } | |
| fn report_mixed_deref_pat_ctors( | |
| &self, | |
| _deref_pat: &DeconstructedPat<Self>, | |
| _normal_pat: &DeconstructedPat<Self>, | |
| ) -> Self::Error { | |
| panic!("`rustc_pattern_analysis::tests` currently doesn't test deref pattern errors") | |
| } | |
| } | |
| /// Construct a single pattern; see `pats!()`. | |
| #[allow(unused_macros)] | |
| macro_rules! pat { | |
| ($($rest:tt)*) => {{ | |
| let mut vec = pats!($($rest)*); | |
| vec.pop().unwrap() | |
| }}; | |
| } | |
| /// A macro to construct patterns. Called like `pats!(type_expr; pattern, pattern, ..)` and returns | |
| /// a `Vec<DeconstructedPat>`. A pattern can be nested and looks like `Constructor(pat, pat)` or | |
| /// `Constructor { .i: pat, .j: pat }`, where `Constructor` is `Struct`, `Variant.i` (with index | |
| /// `i`), as well as booleans and integer ranges. | |
| /// | |
| /// The general structure of the macro is a tt-muncher with several stages identified with | |
| /// `@something(args)`. The args are a key-value list (the keys ensure we don't mix the arguments | |
| /// around) which is passed down and modified as needed. We then parse token-trees from | |
| /// left-to-right. Non-trivial recursion happens when we parse the arguments to a pattern: we | |
| /// recurse to parse the tokens inside `{..}`/`(..)`, and then we continue parsing anything that | |
| /// follows. | |
| macro_rules! pats { | |
| // Entrypoint | |
| // Parse `type; ..` | |
| ($ty:expr; $($rest:tt)*) => {{ | |
| #[allow(unused)] | |
| use rustc_pattern_analysis::{ | |
| constructor::{Constructor, IntRange, MaybeInfiniteInt, RangeEnd}, | |
| pat::{DeconstructedPat, IndexedPat}, | |
| }; | |
| let ty = $ty; | |
| // The heart of the macro is designed to push `IndexedPat`s into a `Vec`, so we work around | |
| // that. | |
| #[allow(unused)] | |
| let sub_tys = ::std::iter::repeat(&ty); | |
| #[allow(unused)] | |
| let mut vec: Vec<IndexedPat<_>> = Vec::new(); | |
| pats!(@ctor(vec:vec, sub_tys:sub_tys, idx:0) $($rest)*); | |
| vec.into_iter().map(|ipat| ipat.pat).collect::<Vec<_>>() | |
| }}; | |
| // Parse `constructor ..` | |
| (@ctor($($args:tt)*) true $($rest:tt)*) => {{ | |
| let ctor = Constructor::Bool(true); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) false $($rest:tt)*) => {{ | |
| let ctor = Constructor::Bool(false); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) Struct $($rest:tt)*) => {{ | |
| let ctor = Constructor::Struct; | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) ( $($fields:tt)* ) $($rest:tt)*) => {{ | |
| let ctor = Constructor::Struct; // tuples | |
| pats!(@pat($($args)*, ctor:ctor) ( $($fields)* ) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) Variant.$variant:ident $($rest:tt)*) => {{ | |
| let ctor = Constructor::Variant($variant); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) Variant.$variant:literal $($rest:tt)*) => {{ | |
| let ctor = Constructor::Variant($variant); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) _ $($rest:tt)*) => {{ | |
| let ctor = Constructor::Wildcard; | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| // Nothing | |
| (@ctor($($args:tt)*)) => {}; | |
| // Integers and int ranges | |
| (@ctor($($args:tt)*) $($start:literal)?..$end:literal $($rest:tt)*) => {{ | |
| let ctor = Constructor::IntRange(IntRange::from_range( | |
| pats!(@rangeboundary- $($start)?), | |
| pats!(@rangeboundary+ $end), | |
| RangeEnd::Excluded, | |
| )); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) $($start:literal)?.. $($rest:tt)*) => {{ | |
| let ctor = Constructor::IntRange(IntRange::from_range( | |
| pats!(@rangeboundary- $($start)?), | |
| pats!(@rangeboundary+), | |
| RangeEnd::Excluded, | |
| )); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) $($start:literal)?..=$end:literal $($rest:tt)*) => {{ | |
| let ctor = Constructor::IntRange(IntRange::from_range( | |
| pats!(@rangeboundary- $($start)?), | |
| pats!(@rangeboundary+ $end), | |
| RangeEnd::Included, | |
| )); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| (@ctor($($args:tt)*) $int:literal $($rest:tt)*) => {{ | |
| let ctor = Constructor::IntRange(IntRange::from_range( | |
| pats!(@rangeboundary- $int), | |
| pats!(@rangeboundary+ $int), | |
| RangeEnd::Included, | |
| )); | |
| pats!(@pat($($args)*, ctor:ctor) $($rest)*) | |
| }}; | |
| // Utility to manage range boundaries. | |
| (@rangeboundary $sign:tt $int:literal) => { MaybeInfiniteInt::new_finite_uint($int) }; | |
| (@rangeboundary -) => { MaybeInfiniteInt::NegInfinity }; | |
| (@rangeboundary +) => { MaybeInfiniteInt::PosInfinity }; | |
| // Parse subfields: `(..)` or `{..}` | |
| // Constructor with no fields, e.g. `bool` or `Variant.1`. | |
| (@pat($($args:tt)*) $(,)?) => { | |
| pats!(@pat($($args)*) {}) | |
| }; | |
| (@pat($($args:tt)*) , $($rest:tt)*) => { | |
| pats!(@pat($($args)*) {}, $($rest)*) | |
| }; | |
| // `(..)` and `{..}` are treated the same. | |
| (@pat($($args:tt)*) ( $($subpat:tt)* ) $($rest:tt)*) => {{ | |
| pats!(@pat($($args)*) { $($subpat)* } $($rest)*) | |
| }}; | |
| (@pat(vec:$vec:expr, sub_tys:$sub_tys:expr, idx:$idx:expr, ctor:$ctor:expr) { $($fields:tt)* } $($rest:tt)*) => {{ | |
| let sub_tys = $sub_tys; | |
| let index = $idx; | |
| // Silly dance to work with both a vec and `iter::repeat()`. | |
| let ty = *(&sub_tys).clone().into_iter().nth(index).unwrap(); | |
| let ctor = $ctor; | |
| let ctor_sub_tys = &ty.sub_tys(&ctor); | |
| #[allow(unused_mut)] | |
| let mut fields = Vec::new(); | |
| // Parse subpatterns (note the leading comma). | |
| pats!(@fields(idx:0, vec:fields, sub_tys:ctor_sub_tys) ,$($fields)*); | |
| let arity = ctor_sub_tys.len(); | |
| let pat = DeconstructedPat::new(ctor, fields, arity, ty, ()).at_index(index); | |
| $vec.push(pat); | |
| // Continue parsing further patterns. | |
| pats!(@fields(idx:index+1, vec:$vec, sub_tys:sub_tys) $($rest)*); | |
| }}; | |
| // Parse fields one by one. | |
| // No fields left. | |
| (@fields($($args:tt)*) $(,)?) => {}; | |
| // `.i: pat` sets the current index to `i`. | |
| (@fields(idx:$_idx:expr, $($args:tt)*) , .$idx:literal : $($rest:tt)*) => {{ | |
| pats!(@ctor($($args)*, idx:$idx) $($rest)*); | |
| }}; | |
| (@fields(idx:$_idx:expr, $($args:tt)*) , .$idx:ident : $($rest:tt)*) => {{ | |
| pats!(@ctor($($args)*, idx:$idx) $($rest)*); | |
| }}; | |
| // Field without an explicit index; we use the current index which gets incremented above. | |
| (@fields(idx:$idx:expr, $($args:tt)*) , $($rest:tt)*) => {{ | |
| pats!(@ctor($($args)*, idx:$idx) $($rest)*); | |
| }}; | |
| } |