Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Exhaustiveness: remove the need for arena-allocation within the algorithm #119581

Merged
merged 1 commit into from
Jan 15, 2024
Merged

Exhaustiveness: remove the need for arena-allocation within the algorithm #119581

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
1 commit
Select commit
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
7 changes: 0 additions & 7 deletions Cargo.lock
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -4366,7 4366,6 @@ dependencies = [
"rustc_target",
"smallvec",
"tracing",
"typed-arena",
]

[[package]]
Expand Down Expand Up @@ -5705,12 5704,6 @@ dependencies = [
"rustc-hash",
]

[[package]]
name = "typed-arena"
version = "2.0.2"
source = "registry https://github.com/rust-lang/crates.io-index"
checksum = "6af6ae20167a9ece4bcb41af5b80f8a1f1df981f6391189ce00fd257af04126a"

[[package]]
name = "typenum"
version = "1.16.0"
Expand Down
6 changes: 0 additions & 6 deletions compiler/rustc_pattern_analysis/Cargo.toml
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -20,13 20,10 @@ rustc_span = { path = "../rustc_span", optional = true }
rustc_target = { path = "../rustc_target", optional = true }
smallvec = { version = "1.8.1", features = ["union"] }
tracing = "0.1"
typed-arena = { version = "2.0.2", optional = true }
# tidy-alphabetical-end

[features]
default = ["rustc"]
# It's not possible to only enable the `typed_arena` dependency when the `rustc` feature is off, so
# we use another feature instead. The crate won't compile if one of these isn't enabled.
rustc = [
"dep:rustc_arena",
"dep:rustc_data_structures",
Expand All @@ -41,6 38,3 @@ rustc = [
"smallvec/may_dangle",
"rustc_index/nightly",
]
stable = [
"dep:typed-arena",
]
6 changes: 3 additions & 3 deletions compiler/rustc_pattern_analysis/src/constructor.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -718,7 718,7 @@ impl<Cx: TypeCx> Constructor<Cx> {

/// The number of fields for this constructor. This must be kept in sync with
/// `Fields::wildcards`.
pub(crate) fn arity(&self, pcx: &PlaceCtxt<'_, '_, Cx>) -> usize {
pub(crate) fn arity(&self, pcx: &PlaceCtxt<'_, Cx>) -> usize {
pcx.ctor_arity(self)
}

Expand All @@ -727,7 727,7 @@ impl<Cx: TypeCx> Constructor<Cx> {
/// this checks for inclusion.
// We inline because this has a single call site in `Matrix::specialize_constructor`.
#[inline]
pub(crate) fn is_covered_by<'p>(&self, pcx: &PlaceCtxt<'_, 'p, Cx>, other: &Self) -> bool {
pub(crate) fn is_covered_by(&self, pcx: &PlaceCtxt<'_, Cx>, other: &Self) -> bool {
match (self, other) {
(Wildcard, _) => pcx
.mcx
Expand Down Expand Up @@ -861,7 861,7 @@ impl<Cx: TypeCx> ConstructorSet<Cx> {
#[instrument(level = "debug", skip(self, pcx, ctors), ret)]
pub(crate) fn split<'a>(
&self,
pcx: &PlaceCtxt<'a, '_, Cx>,
pcx: &PlaceCtxt<'a, Cx>,
ctors: impl Iterator<Item = &'a Constructor<Cx>> Clone,
) -> SplitConstructorSet<Cx> {
let mut present: SmallVec<[_; 1]> = SmallVec::new();
Expand Down
15 changes: 2 additions & 13 deletions compiler/rustc_pattern_analysis/src/lib.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -38,13 38,6 @@ use crate::rustc::RustcMatchCheckCtxt;
#[cfg(feature = "rustc")]
use crate::usefulness::{compute_match_usefulness, ValidityConstraint};

// It's not possible to only enable the `typed_arena` dependency when the `rustc` feature is off, so
// we use another feature instead. The crate won't compile if one of these isn't enabled.
#[cfg(feature = "rustc")]
pub(crate) use rustc_arena::TypedArena;
#[cfg(feature = "stable")]
pub(crate) use typed_arena::Arena as TypedArena;

pub trait Captures<'a> {}
impl<'a, T: ?Sized> Captures<'a> for T {}

Expand Down Expand Up @@ -89,11 82,9 @@ pub trait TypeCx: Sized fmt::Debug {
/// Context that provides information global to a match.
#[derive(derivative::Derivative)]
#[derivative(Clone(bound = ""), Copy(bound = ""))]
pub struct MatchCtxt<'a, 'p, Cx: TypeCx> {
pub struct MatchCtxt<'a, Cx: TypeCx> {
Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Can you replace MatchCtxt<'a, Cx> with &'a Cx in all of its usages?

Copy link
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No, there are other things I'll need to put in there later

Copy link
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Like what?

Copy link
Member Author

@Nadrieril Nadrieril Jan 4, 2024 •
edited
Loading

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Currently planning:

/// The context for type information.
pub tycx: &'a Cx,
/// An arena to store the wildcards we produce during analysis.
pub wildcard_arena: &'p TypedArena<DeconstructedPat<'p, Cx>>,
}

/// The arm of a match expression.
Expand All @@ -114,11 105,9 @@ pub fn analyze_match<'p, 'tcx>(
arms: &[rustc::MatchArm<'p, 'tcx>],
scrut_ty: Ty<'tcx>,
) -> Result<rustc::UsefulnessReport<'p, 'tcx>, ErrorGuaranteed> {
// Arena to store the extra wildcards we construct during analysis.
let wildcard_arena = tycx.pattern_arena;
let scrut_ty = tycx.reveal_opaque_ty(scrut_ty);
let scrut_validity = ValidityConstraint::from_bool(tycx.known_valid_scrutinee);
let cx = MatchCtxt { tycx, wildcard_arena };
let cx = MatchCtxt { tycx };

let report = compute_match_usefulness(cx, arms, scrut_ty, scrut_validity)?;

Expand Down
2 changes: 1 addition & 1 deletion compiler/rustc_pattern_analysis/src/pat.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -240,7 240,7 @@ impl<Cx: TypeCx> WitnessPat<Cx> {
/// Construct a pattern that matches everything that starts with this constructor.
/// For example, if `ctor` is a `Constructor::Variant` for `Option::Some`, we get the pattern
/// `Some(_)`.
pub(crate) fn wild_from_ctor(pcx: &PlaceCtxt<'_, '_, Cx>, ctor: Constructor<Cx>) -> Self {
pub(crate) fn wild_from_ctor(pcx: &PlaceCtxt<'_, Cx>, ctor: Constructor<Cx>) -> Self {
let field_tys = pcx.ctor_sub_tys(&ctor);
let fields = field_tys.iter().map(|ty| Self::wildcard(*ty)).collect();
Self::new(ctor, fields, pcx.ty)
Expand Down
6 changes: 4 additions & 2 deletions compiler/rustc_pattern_analysis/src/rustc.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -33,11 33,11 @@ pub type ConstructorSet<'p, 'tcx> =
pub type DeconstructedPat<'p, 'tcx> =
crate::pat::DeconstructedPat<'p, RustcMatchCheckCtxt<'p, 'tcx>>;
pub type MatchArm<'p, 'tcx> = crate::MatchArm<'p, RustcMatchCheckCtxt<'p, 'tcx>>;
pub type MatchCtxt<'a, 'p, 'tcx> = crate::MatchCtxt<'a, 'p, RustcMatchCheckCtxt<'p, 'tcx>>;
pub type MatchCtxt<'a, 'p, 'tcx> = crate::MatchCtxt<'a, RustcMatchCheckCtxt<'p, 'tcx>>;
pub type OverlappingRanges<'p, 'tcx> =
crate::usefulness::OverlappingRanges<'p, RustcMatchCheckCtxt<'p, 'tcx>>;
pub(crate) type PlaceCtxt<'a, 'p, 'tcx> =
crate::usefulness::PlaceCtxt<'a, 'p, RustcMatchCheckCtxt<'p, 'tcx>>;
crate::usefulness::PlaceCtxt<'a, RustcMatchCheckCtxt<'p, 'tcx>>;
pub(crate) type SplitConstructorSet<'p, 'tcx> =
crate::constructor::SplitConstructorSet<RustcMatchCheckCtxt<'p, 'tcx>>;
pub type Usefulness<'p, 'tcx> = crate::usefulness::Usefulness<'p, RustcMatchCheckCtxt<'p, 'tcx>>;
Expand Down Expand Up @@ -80,7 80,9 @@ pub struct RustcMatchCheckCtxt<'p, 'tcx> {
/// outside its module and should not be matchable with an empty match statement.
pub module: DefId,
pub param_env: ty::ParamEnv<'tcx>,
/// To allocate lowered patterns
pub pattern_arena: &'p TypedArena<DeconstructedPat<'p, 'tcx>>,
/// To allocate the result of `self.ctor_sub_tys()`
pub dropless_arena: &'p DroplessArena,
/// Lint level at the match.
pub match_lint_level: HirId,
Expand Down
18 changes: 9 additions & 9 deletions compiler/rustc_pattern_analysis/src/usefulness.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -732,19 732,19 @@ pub fn ensure_sufficient_stack<R>(f: impl FnOnce() -> R) -> R {
/// Context that provides information local to a place under investigation.
#[derive(derivative::Derivative)]
#[derivative(Debug(bound = ""), Clone(bound = ""), Copy(bound = ""))]
pub(crate) struct PlaceCtxt<'a, 'p, Cx: TypeCx> {
pub(crate) struct PlaceCtxt<'a, Cx: TypeCx> {
#[derivative(Debug = "ignore")]
pub(crate) mcx: MatchCtxt<'a, 'p, Cx>,
pub(crate) mcx: MatchCtxt<'a, Cx>,
/// Type of the place under investigation.
pub(crate) ty: Cx::Ty,
/// Whether the place is the original scrutinee place, as opposed to a subplace of it.
pub(crate) is_scrutinee: bool,
}

impl<'a, 'p, Cx: TypeCx> PlaceCtxt<'a, 'p, Cx> {
impl<'a, Cx: TypeCx> PlaceCtxt<'a, Cx> {
/// A `PlaceCtxt` when code other than `is_useful` needs one.
#[cfg_attr(not(feature = "rustc"), allow(dead_code))]
pub(crate) fn new_dummy(mcx: MatchCtxt<'a, 'p, Cx>, ty: Cx::Ty) -> Self {
pub(crate) fn new_dummy(mcx: MatchCtxt<'a, Cx>, ty: Cx::Ty) -> Self {
PlaceCtxt { mcx, ty, is_scrutinee: false }
}

Expand Down Expand Up @@ -1067,7 1067,7 @@ impl<'p, Cx: TypeCx> Matrix<'p, Cx> {
/// This computes `specialize(ctor, self)`. See top of the file for explanations.
fn specialize_constructor(
&self,
pcx: &PlaceCtxt<'_, 'p, Cx>,
pcx: &PlaceCtxt<'_, Cx>,
ctor: &Constructor<Cx>,
ctor_is_relevant: bool,
) -> Matrix<'p, Cx> {
Expand Down Expand Up @@ -1226,7 1226,7 @@ impl<Cx: TypeCx> WitnessStack<Cx> {
/// pats: [(false, "foo"), _, true]
/// result: [Enum::Variant { a: (false, "foo"), b: _ }, true]
/// ```
fn apply_constructor(&mut self, pcx: &PlaceCtxt<'_, '_, Cx>, ctor: &Constructor<Cx>) {
fn apply_constructor(&mut self, pcx: &PlaceCtxt<'_, Cx>, ctor: &Constructor<Cx>) {
let len = self.0.len();
let arity = ctor.arity(pcx);
let fields = self.0.drain((len - arity)..).rev().collect();
Expand Down Expand Up @@ -1277,7 1277,7 @@ impl<Cx: TypeCx> WitnessMatrix<Cx> {
/// Reverses specialization by `ctor`. See the section on `unspecialize` at the top of the file.
fn apply_constructor(
&mut self,
pcx: &PlaceCtxt<'_, '_, Cx>,
pcx: &PlaceCtxt<'_, Cx>,
missing_ctors: &[Constructor<Cx>],
ctor: &Constructor<Cx>,
report_individual_missing_ctors: bool,
Expand Down Expand Up @@ -1421,7 1421,7 @@ fn collect_overlapping_range_endpoints<'p, Cx: TypeCx>(
/// This is all explained at the top of the file.
#[instrument(level = "debug", skip(mcx, is_top_level), ret)]
fn compute_exhaustiveness_and_usefulness<'a, 'p, Cx: TypeCx>(
mcx: MatchCtxt<'a, 'p, Cx>,
mcx: MatchCtxt<'a, Cx>,
matrix: &mut Matrix<'p, Cx>,
overlapping_range_endpoints: &mut Vec<OverlappingRanges<'p, Cx>>,
is_top_level: bool,
Expand Down Expand Up @@ -1591,7 1591,7 @@ pub struct UsefulnessReport<'p, Cx: TypeCx> {
/// Computes whether a match is exhaustive and which of its arms are useful.
#[instrument(skip(cx, arms), level = "debug")]
pub fn compute_match_usefulness<'p, Cx: TypeCx>(
cx: MatchCtxt<'_, 'p, Cx>,
cx: MatchCtxt<'_, Cx>,
arms: &[MatchArm<'p, Cx>],
scrut_ty: Cx::Ty,
scrut_validity: ValidityConstraint,
Expand Down
1 change: 0 additions & 1 deletion src/tools/tidy/src/deps.rs
View file
Open in desktop
Original file line number Diff line number Diff line change
Expand Up @@ -359,7 359,6 @@ const PERMITTED_RUSTC_DEPENDENCIES: &[&str] = &[
"tracing-tree",
"twox-hash",
"type-map",
"typed-arena",
"typenum",
"unic-langid",
"unic-langid-impl",
Expand Down
Loading