mod.rs

use rustc_pattern_analysis::constructor::{
    Constructor, ConstructorSet, IntRange, MaybeInfiniteInt, RangeEnd, VariantVisibility,
};
use rustc_pattern_analysis::usefulness::{PlaceValidity, UsefulnessReport};
use rustc_pattern_analysis::{Captures, MatchArm, PatCx, PrivateUninhabitedField};

/// Sets up `tracing` for easier debugging. Tries to look like the `rustc` setup.
pub 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();
}

/// A simple set of types.
#[allow(dead_code)]
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
pub 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 },
}

/// The important logic.
impl Ty {
    pub 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)) => 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(),
        }
    }

    pub 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::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,
                }
            }
        }
    }

    pub 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(..), 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 fn compute_match_usefulness<'p>(
    arms: &[MatchArm<'p, Cx>],
    ty: Ty,
    scrut_validity: PlaceValidity,
    complexity_limit: Option<usize>,
) -> Result<UsefulnessReport<'p, Cx>, ()> {
    init_tracing();
    rustc_pattern_analysis::usefulness::compute_match_usefulness(
        &Cx,
        arms,
        ty,
        scrut_validity,
        complexity_limit,
    )
}

#[derive(Debug)]
pub struct Cx;

/// 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 ctor_arity(&self, ctor: &Constructor<Self>, ty: &Self::Ty) -> usize {
        ty.sub_tys(ctor).len()
    }

    fn ctor_sub_tys<'a>(
        &'a self,
        ctor: &'a Constructor<Self>,
        ty: &'a Self::Ty,
    ) -> impl Iterator<Item = (Self::Ty, PrivateUninhabitedField)> + ExactSizeIterator + Captures<'a>
    {
        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(())
    }
}

/// 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_imports)]
        use rustc_pattern_analysis::{
            constructor::{Constructor, IntRange, MaybeInfiniteInt, RangeEnd},
            pat::DeconstructedPat,
        };
        let ty = $ty;
        // The heart of the macro is designed to push `IndexedPat`s into a `Vec`, so we work around
        // that.
        let sub_tys = ::std::iter::repeat(&ty);
        let mut vec = 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)*)
    }};

    // 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)*);
    }};
}