|
| 1 | +use rustc_pattern_analysis::{ |
| 2 | + constructor::{ |
| 3 | + Constructor, ConstructorSet, IntRange, MaybeInfiniteInt, RangeEnd, VariantVisibility, |
| 4 | + }, |
| 5 | + usefulness::{PlaceValidity, UsefulnessReport}, |
| 6 | + Captures, MatchArm, PatCx, PrivateUninhabitedField, |
| 7 | +}; |
| 8 | + |
| 9 | +/// Sets up `tracing` for easier debugging. Tries to look like the `rustc` setup. |
| 10 | +pub fn init_tracing() { |
| 11 | + use tracing_subscriber::layer::SubscriberExt; |
| 12 | + use tracing_subscriber::util::SubscriberInitExt; |
| 13 | + use tracing_subscriber::Layer; |
| 14 | + let _ = tracing_tree::HierarchicalLayer::default() |
| 15 | + .with_writer(std::io::stderr) |
| 16 | + .with_indent_lines(true) |
| 17 | + .with_ansi(true) |
| 18 | + .with_targets(true) |
| 19 | + .with_indent_amount(2) |
| 20 | + .with_subscriber( |
| 21 | + tracing_subscriber::Registry::default() |
| 22 | + .with(tracing_subscriber::EnvFilter::from_default_env()), |
| 23 | + ) |
| 24 | + .try_init(); |
| 25 | +} |
| 26 | + |
| 27 | +/// A simple set of types. |
| 28 | +#[allow(dead_code)] |
| 29 | +#[derive(Debug, Copy, Clone)] |
| 30 | +pub enum Ty { |
| 31 | + /// Booleans |
| 32 | + Bool, |
| 33 | + /// 8-bit unsigned integers |
| 34 | + U8, |
| 35 | + /// Tuples. |
| 36 | + Tuple(&'static [Ty]), |
| 37 | + /// A struct with `arity` fields of type `ty`. |
| 38 | + BigStruct { arity: usize, ty: &'static Ty }, |
| 39 | + /// A enum with `arity` variants of type `ty`. |
| 40 | + BigEnum { arity: usize, ty: &'static Ty }, |
| 41 | +} |
| 42 | + |
| 43 | +/// The important logic. |
| 44 | +impl Ty { |
| 45 | + pub fn sub_tys(&self, ctor: &Constructor<Cx>) -> Vec<Self> { |
| 46 | + use Constructor::*; |
| 47 | + match (ctor, *self) { |
| 48 | + (Struct, Ty::Tuple(tys)) => tys.iter().copied().collect(), |
| 49 | + (Struct, Ty::BigStruct { arity, ty }) => (0..arity).map(|_| *ty).collect(), |
| 50 | + (Variant(_), Ty::BigEnum { ty, .. }) => vec![*ty], |
| 51 | + (Bool(..) | IntRange(..) | NonExhaustive | Missing | Wildcard, _) => vec![], |
| 52 | + _ => panic!("Unexpected ctor {ctor:?} for type {self:?}"), |
| 53 | + } |
| 54 | + } |
| 55 | + |
| 56 | + pub fn ctor_set(&self) -> ConstructorSet<Cx> { |
| 57 | + match *self { |
| 58 | + Ty::Bool => ConstructorSet::Bool, |
| 59 | + Ty::U8 => ConstructorSet::Integers { |
| 60 | + range_1: IntRange::from_range( |
| 61 | + MaybeInfiniteInt::new_finite_uint(0), |
| 62 | + MaybeInfiniteInt::new_finite_uint(255), |
| 63 | + RangeEnd::Included, |
| 64 | + ), |
| 65 | + range_2: None, |
| 66 | + }, |
| 67 | + Ty::Tuple(..) | Ty::BigStruct { .. } => ConstructorSet::Struct { empty: false }, |
| 68 | + Ty::BigEnum { arity, .. } => ConstructorSet::Variants { |
| 69 | + variants: (0..arity).map(|_| VariantVisibility::Visible).collect(), |
| 70 | + non_exhaustive: false, |
| 71 | + }, |
| 72 | + } |
| 73 | + } |
| 74 | + |
| 75 | + pub fn write_variant_name( |
| 76 | + &self, |
| 77 | + f: &mut std::fmt::Formatter<'_>, |
| 78 | + ctor: &Constructor<Cx>, |
| 79 | + ) -> std::fmt::Result { |
| 80 | + match (*self, ctor) { |
| 81 | + (Ty::Tuple(..), _) => Ok(()), |
| 82 | + (Ty::BigStruct { .. }, _) => write!(f, "BigStruct"), |
| 83 | + (Ty::BigEnum { .. }, Constructor::Variant(i)) => write!(f, "BigEnum::Variant{i}"), |
| 84 | + _ => write!(f, "{:?}::{:?}", self, ctor), |
| 85 | + } |
| 86 | + } |
| 87 | +} |
| 88 | + |
| 89 | +/// Compute usefulness in our simple context (and set up tracing for easier debugging). |
| 90 | +pub fn compute_match_usefulness<'p>( |
| 91 | + arms: &[MatchArm<'p, Cx>], |
| 92 | + ty: Ty, |
| 93 | + scrut_validity: PlaceValidity, |
| 94 | + complexity_limit: Option<usize>, |
| 95 | +) -> Result<UsefulnessReport<'p, Cx>, ()> { |
| 96 | + init_tracing(); |
| 97 | + rustc_pattern_analysis::usefulness::compute_match_usefulness( |
| 98 | + &Cx, |
| 99 | + arms, |
| 100 | + ty, |
| 101 | + scrut_validity, |
| 102 | + complexity_limit, |
| 103 | + ) |
| 104 | +} |
| 105 | + |
| 106 | +#[derive(Debug)] |
| 107 | +pub struct Cx; |
| 108 | + |
| 109 | +/// The context for pattern analysis. Forwards anything interesting to `Ty` methods. |
| 110 | +impl PatCx for Cx { |
| 111 | + type Ty = Ty; |
| 112 | + type Error = (); |
| 113 | + type VariantIdx = usize; |
| 114 | + type StrLit = (); |
| 115 | + type ArmData = (); |
| 116 | + type PatData = (); |
| 117 | + |
| 118 | + fn is_exhaustive_patterns_feature_on(&self) -> bool { |
| 119 | + false |
| 120 | + } |
| 121 | + |
| 122 | + fn is_min_exhaustive_patterns_feature_on(&self) -> bool { |
| 123 | + false |
| 124 | + } |
| 125 | + |
| 126 | + fn ctor_arity(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> usize { |
| 127 | + ty.sub_tys(ctor).len() |
| 128 | + } |
| 129 | + |
| 130 | + fn ctor_sub_tys<'a>( |
| 131 | + &'a self, |
| 132 | + ctor: &'a Constructor<Self>, |
| 133 | + ty: &'a Self::Ty, |
| 134 | + ) -> impl Iterator<Item = (Self::Ty, PrivateUninhabitedField)> + ExactSizeIterator + Captures<'a> |
| 135 | + { |
| 136 | + ty.sub_tys(ctor).into_iter().map(|ty| (ty, PrivateUninhabitedField(false))) |
| 137 | + } |
| 138 | + |
| 139 | + fn ctors_for_ty(&self, ty: &Self::Ty) -> Result<ConstructorSet<Self>, Self::Error> { |
| 140 | + Ok(ty.ctor_set()) |
| 141 | + } |
| 142 | + |
| 143 | + fn write_variant_name( |
| 144 | + f: &mut std::fmt::Formatter<'_>, |
| 145 | + ctor: &Constructor<Self>, |
| 146 | + ty: &Self::Ty, |
| 147 | + ) -> std::fmt::Result { |
| 148 | + ty.write_variant_name(f, ctor) |
| 149 | + } |
| 150 | + |
| 151 | + fn bug(&self, fmt: std::fmt::Arguments<'_>) -> Self::Error { |
| 152 | + panic!("{}", fmt) |
| 153 | + } |
| 154 | + |
| 155 | + /// Abort when reaching the complexity limit. This is what we'll check in tests. |
| 156 | + fn complexity_exceeded(&self) -> Result<(), Self::Error> { |
| 157 | + Err(()) |
| 158 | + } |
| 159 | +} |
| 160 | + |
| 161 | +/// Construct a single pattern; see `pats!()`. |
| 162 | +#[allow(unused_macros)] |
| 163 | +macro_rules! pat { |
| 164 | + ($($rest:tt)*) => {{ |
| 165 | + let mut vec = pats!($($rest)*); |
| 166 | + vec.pop().unwrap() |
| 167 | + }}; |
| 168 | +} |
| 169 | + |
| 170 | +/// A macro to construct patterns. Called like `pats!(type_expr; pattern, pattern, ..)` and returns |
| 171 | +/// a `Vec<DeconstructedPat>`. A pattern can be nested and looks like `Constructor(pat, pat)` or |
| 172 | +/// `Constructor { .i: pat, .j: pat }`, where `Constructor` is `Struct`, `Variant.i` (with index |
| 173 | +/// `i`), as well as booleans and integer ranges. |
| 174 | +/// |
| 175 | +/// The general structure of the macro is a tt-muncher with several stages identified with |
| 176 | +/// `@something(args)`. The args are a key-value list (the keys ensure we don't mix the arguments |
| 177 | +/// around) which is passed down and modified as needed. We then parse token-trees from |
| 178 | +/// left-to-right. Non-trivial recursion happens when we parse the arguments to a pattern: we |
| 179 | +/// recurse to parse the tokens inside `{..}`/`(..)`, and then we continue parsing anything that |
| 180 | +/// follows. |
| 181 | +macro_rules! pats { |
| 182 | + // Entrypoint |
| 183 | + // Parse `type; ..` |
| 184 | + ($ty:expr; $($rest:tt)*) => {{ |
| 185 | + #[allow(unused_imports)] |
| 186 | + use rustc_pattern_analysis::{ |
| 187 | + constructor::{Constructor, IntRange, MaybeInfiniteInt, RangeEnd}, |
| 188 | + pat::DeconstructedPat, |
| 189 | + }; |
| 190 | + let ty = $ty; |
| 191 | + // The heart of the macro is designed to push `IndexedPat`s into a `Vec`, so we work around |
| 192 | + // that. |
| 193 | + let sub_tys = ::std::iter::repeat(&ty); |
| 194 | + let mut vec = Vec::new(); |
| 195 | + pats!(@ctor(vec:vec, sub_tys:sub_tys, idx:0) $($rest)*); |
| 196 | + vec.into_iter().map(|ipat| ipat.pat).collect::<Vec<_>>() |
| 197 | + }}; |
| 198 | + |
| 199 | + // Parse `constructor ..` |
| 200 | + |
| 201 | + (@ctor($($args:tt)*) true $($rest:tt)*) => {{ |
| 202 | + let ctor = Constructor::Bool(true); |
| 203 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 204 | + }}; |
| 205 | + (@ctor($($args:tt)*) false $($rest:tt)*) => {{ |
| 206 | + let ctor = Constructor::Bool(false); |
| 207 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 208 | + }}; |
| 209 | + (@ctor($($args:tt)*) Struct $($rest:tt)*) => {{ |
| 210 | + let ctor = Constructor::Struct; |
| 211 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 212 | + }}; |
| 213 | + (@ctor($($args:tt)*) ( $($fields:tt)* ) $($rest:tt)*) => {{ |
| 214 | + let ctor = Constructor::Struct; // tuples |
| 215 | + pats!(@pat($($args)*, ctor:ctor) ( $($fields)* ) $($rest)*) |
| 216 | + }}; |
| 217 | + (@ctor($($args:tt)*) Variant.$variant:ident $($rest:tt)*) => {{ |
| 218 | + let ctor = Constructor::Variant($variant); |
| 219 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 220 | + }}; |
| 221 | + (@ctor($($args:tt)*) Variant.$variant:literal $($rest:tt)*) => {{ |
| 222 | + let ctor = Constructor::Variant($variant); |
| 223 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 224 | + }}; |
| 225 | + (@ctor($($args:tt)*) _ $($rest:tt)*) => {{ |
| 226 | + let ctor = Constructor::Wildcard; |
| 227 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 228 | + }}; |
| 229 | + |
| 230 | + // Integers and int ranges |
| 231 | + (@ctor($($args:tt)*) $($start:literal)?..$end:literal $($rest:tt)*) => {{ |
| 232 | + let ctor = Constructor::IntRange(IntRange::from_range( |
| 233 | + pats!(@rangeboundary- $($start)?), |
| 234 | + pats!(@rangeboundary+ $end), |
| 235 | + RangeEnd::Excluded, |
| 236 | + )); |
| 237 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 238 | + }}; |
| 239 | + (@ctor($($args:tt)*) $($start:literal)?.. $($rest:tt)*) => {{ |
| 240 | + let ctor = Constructor::IntRange(IntRange::from_range( |
| 241 | + pats!(@rangeboundary- $($start)?), |
| 242 | + pats!(@rangeboundary+), |
| 243 | + RangeEnd::Excluded, |
| 244 | + )); |
| 245 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 246 | + }}; |
| 247 | + (@ctor($($args:tt)*) $($start:literal)?..=$end:literal $($rest:tt)*) => {{ |
| 248 | + let ctor = Constructor::IntRange(IntRange::from_range( |
| 249 | + pats!(@rangeboundary- $($start)?), |
| 250 | + pats!(@rangeboundary+ $end), |
| 251 | + RangeEnd::Included, |
| 252 | + )); |
| 253 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 254 | + }}; |
| 255 | + (@ctor($($args:tt)*) $int:literal $($rest:tt)*) => {{ |
| 256 | + let ctor = Constructor::IntRange(IntRange::from_range( |
| 257 | + pats!(@rangeboundary- $int), |
| 258 | + pats!(@rangeboundary+ $int), |
| 259 | + RangeEnd::Included, |
| 260 | + )); |
| 261 | + pats!(@pat($($args)*, ctor:ctor) $($rest)*) |
| 262 | + }}; |
| 263 | + // Utility to manage range boundaries. |
| 264 | + (@rangeboundary $sign:tt $int:literal) => { MaybeInfiniteInt::new_finite_uint($int) }; |
| 265 | + (@rangeboundary -) => { MaybeInfiniteInt::NegInfinity }; |
| 266 | + (@rangeboundary +) => { MaybeInfiniteInt::PosInfinity }; |
| 267 | + |
| 268 | + // Parse subfields: `(..)` or `{..}` |
| 269 | + |
| 270 | + // Constructor with no fields, e.g. `bool` or `Variant.1`. |
| 271 | + (@pat($($args:tt)*) $(,)?) => { |
| 272 | + pats!(@pat($($args)*) {}) |
| 273 | + }; |
| 274 | + (@pat($($args:tt)*) , $($rest:tt)*) => { |
| 275 | + pats!(@pat($($args)*) {}, $($rest)*) |
| 276 | + }; |
| 277 | + // `(..)` and `{..}` are treated the same. |
| 278 | + (@pat($($args:tt)*) ( $($subpat:tt)* ) $($rest:tt)*) => {{ |
| 279 | + pats!(@pat($($args)*) { $($subpat)* } $($rest)*) |
| 280 | + }}; |
| 281 | + (@pat(vec:$vec:expr, sub_tys:$sub_tys:expr, idx:$idx:expr, ctor:$ctor:expr) { $($fields:tt)* } $($rest:tt)*) => {{ |
| 282 | + let sub_tys = $sub_tys; |
| 283 | + let index = $idx; |
| 284 | + // Silly dance to work with both a vec and `iter::repeat()`. |
| 285 | + let ty = *(&sub_tys).clone().into_iter().nth(index).unwrap(); |
| 286 | + let ctor = $ctor; |
| 287 | + let ctor_sub_tys = &ty.sub_tys(&ctor); |
| 288 | + #[allow(unused_mut)] |
| 289 | + let mut fields = Vec::new(); |
| 290 | + // Parse subpatterns (note the leading comma). |
| 291 | + pats!(@fields(idx:0, vec:fields, sub_tys:ctor_sub_tys) ,$($fields)*); |
| 292 | + let arity = ctor_sub_tys.len(); |
| 293 | + let pat = DeconstructedPat::new(ctor, fields, arity, ty, ()).at_index(index); |
| 294 | + $vec.push(pat); |
| 295 | + |
| 296 | + // Continue parsing further patterns. |
| 297 | + pats!(@fields(idx:index+1, vec:$vec, sub_tys:sub_tys) $($rest)*); |
| 298 | + }}; |
| 299 | + |
| 300 | + // Parse fields one by one. |
| 301 | + |
| 302 | + // No fields left. |
| 303 | + (@fields($($args:tt)*) $(,)?) => {}; |
| 304 | + // `.i: pat` sets the current index to `i`. |
| 305 | + (@fields(idx:$_idx:expr, $($args:tt)*) , .$idx:literal : $($rest:tt)*) => {{ |
| 306 | + pats!(@ctor($($args)*, idx:$idx) $($rest)*); |
| 307 | + }}; |
| 308 | + (@fields(idx:$_idx:expr, $($args:tt)*) , .$idx:ident : $($rest:tt)*) => {{ |
| 309 | + pats!(@ctor($($args)*, idx:$idx) $($rest)*); |
| 310 | + }}; |
| 311 | + // Field without an explicit index; we use the current index which gets incremented above. |
| 312 | + (@fields(idx:$idx:expr, $($args:tt)*) , $($rest:tt)*) => {{ |
| 313 | + pats!(@ctor($($args)*, idx:$idx) $($rest)*); |
| 314 | + }}; |
| 315 | +} |
0 commit comments