From 975109051caf05de6d166779589e299d9aca9cd5 Mon Sep 17 00:00:00 2001 From: Dawer <7803845+iDawer@users.noreply.github.com> Date: Thu, 6 May 2021 09:42:00 +0500 Subject: Basic lowering hir_def::exrp::Pat -> typed HIR. Pattern arena is broken --- .../src/diagnostics/pattern/deconstruct_pat.rs | 188 +++++++++------------ crates/hir_ty/src/diagnostics/pattern/pat_util.rs | 52 ++++++ .../hir_ty/src/diagnostics/pattern/usefulness.rs | 81 ++++----- 3 files changed, 166 insertions(+), 155 deletions(-) create mode 100644 crates/hir_ty/src/diagnostics/pattern/pat_util.rs (limited to 'crates/hir_ty/src/diagnostics/pattern') diff --git a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs index 248a379b3..479e0dc73 100644 --- a/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs +++ b/crates/hir_ty/src/diagnostics/pattern/deconstruct_pat.rs @@ -5,18 +5,18 @@ use std::{ }; use hir_def::{ - expr::{Expr, Literal, Pat, PatId, RecordFieldPat}, - find_path::find_path, - item_scope::ItemInNs, - path::Path, + expr::{Expr, Literal, RecordFieldPat}, type_ref::Mutability, - AttrDefId, EnumVariantId, HasModule, VariantId, + AttrDefId, EnumVariantId, HasModule, LocalFieldId, VariantId, }; use smallvec::{smallvec, SmallVec}; use crate::{AdtId, Interner, Scalar, Ty, TyExt, TyKind}; -use super::usefulness::{MatchCheckCtx, PatCtxt}; +use super::{ + usefulness::{MatchCheckCtx, PatCtxt}, + FieldPat, Pat, PatId, PatKind, +}; use self::Constructor::*; @@ -271,29 +271,18 @@ impl Constructor { /// Determines the constructor that the given pattern can be specialized to. pub(super) fn from_pat(cx: &MatchCheckCtx<'_>, pat: PatId) -> Self { let ty = cx.type_of(pat); - match &cx.pattern_arena.borrow()[pat] { - Pat::Bind { .. } | Pat::Wild => Wildcard, - Pat::Tuple { .. } | Pat::Ref { .. } | Pat::Box { .. } => Single, - Pat::Record { .. } | Pat::Path(_) | Pat::TupleStruct { .. } => { - // TODO: path to const - let variant_id = - cx.infer.variant_resolution_for_pat(pat).unwrap_or_else(|| todo!()); - match variant_id { - VariantId::EnumVariantId(id) => Variant(id), - VariantId::StructId(_) | VariantId::UnionId(_) => Single, - } - } - &Pat::Lit(expr_id) => match cx.body[expr_id] { - Expr::Literal(Literal::Bool(val)) => IntRange(IntRange::from_bool(val)), - _ => todo!(), - }, - - Pat::Or(..) => panic!("bug: Or-pattern should have been expanded earlier on."), - Pat::Missing => todo!("Fail gracefully when there is an error in a pattern"), + match cx.pattern_arena.borrow()[pat].kind.as_ref() { + PatKind::Binding { .. } | PatKind::Wild => Wildcard, + PatKind::Leaf { .. } | PatKind::Deref { .. } => Single, + &PatKind::Variant { enum_variant, .. } => Variant(enum_variant), + + //Todo + // &Pat::Lit(expr_id) => match cx.body[expr_id] { + // Expr::Literal(Literal::Bool(val)) => IntRange(IntRange::from_bool(val)), + // _ => todo!(), + // }, + PatKind::Or { .. } => panic!("bug: Or-pattern should have been expanded earlier on."), pat => todo!("Constructor::from_pat {:?}", pat), - // Pat::Range { start, end } => {} - // Pat::Slice { prefix, slice, suffix } => {} - // Pat::ConstBlock(_) => {} } } @@ -620,15 +609,15 @@ impl Fields { cx: &MatchCheckCtx<'_>, tys: impl IntoIterator, ) -> Self { - let wilds = tys.into_iter().map(|ty| (Pat::Wild, ty)); - let pats = wilds.map(|(pat, ty)| cx.alloc_pat(pat, ty)).collect(); + let wilds = tys.into_iter().map(Pat::wildcard_from_ty); + let pats = wilds.map(|pat| cx.alloc_pat(pat)).collect(); Fields::Vec(pats) } pub(crate) fn wildcards(pcx: PatCtxt<'_>, constructor: &Constructor) -> Self { let ty = pcx.ty; let cx = pcx.cx; - let wildcard_from_ty = |ty| cx.alloc_pat(Pat::Wild, ty); + let wildcard_from_ty = |ty| cx.alloc_pat(Pat::wildcard_from_ty(ty)); let ret = match constructor { Single | Variant(_) => match ty.kind(&Interner) { @@ -696,64 +685,60 @@ impl Fields { /// returns `Some(false)` pub(super) fn apply(self, pcx: PatCtxt<'_>, ctor: &Constructor) -> Pat { let subpatterns_and_indices = self.patterns_and_indices(); - let mut subpatterns = subpatterns_and_indices.iter().map(|&(_, p)| p); - // TODO witnesses are not yet used - const TODO: Pat = Pat::Wild; + let mut subpatterns = + subpatterns_and_indices.iter().map(|&(_, p)| pcx.cx.pattern_arena.borrow()[p].clone()); + // FIXME(iDawer) witnesses are not yet used + const UNIMPLEMENTED: PatKind = PatKind::Wild; - match ctor { + let pat = match ctor { Single | Variant(_) => match pcx.ty.kind(&Interner) { TyKind::Adt(..) | TyKind::Tuple(..) => { // We want the real indices here. - // TODO indices and ellipsis interaction, tests - let subpatterns = subpatterns_and_indices.iter().map(|&(_, pat)| pat).collect(); + let subpatterns = subpatterns_and_indices + .iter() + .map(|&(field, pat)| FieldPat { + field, + pattern: pcx.cx.pattern_arena.borrow()[pat].clone(), + }) + .collect(); if let Some((adt, substs)) = pcx.ty.as_adt() { - let item = ItemInNs::Types(adt.into()); - let path = find_path(pcx.cx.db.upcast(), item, pcx.cx.module) - .map(|mpath| Path::from_known_path(mpath, Vec::new()).into()); - match adt { - hir_def::AdtId::EnumId(id) => TODO, - hir_def::AdtId::StructId(id) => { - let variant_data = &pcx.cx.db.struct_data(id).variant_data; - let args = subpatterns_and_indices - .iter() - .zip(variant_data.fields().iter()) - .map(|(&(_, pat), (_, field_data))| RecordFieldPat { - name: field_data.name.clone(), - pat, - }) - .collect(); - Pat::Record { path, args, ellipsis: false } - } - hir_def::AdtId::UnionId(_) => Pat::Wild, + if let hir_def::AdtId::EnumId(_) = adt { + let enum_variant = match ctor { + &Variant(id) => id, + _ => unreachable!(), + }; + PatKind::Variant { substs: substs.clone(), enum_variant, subpatterns } + } else { + PatKind::Leaf { subpatterns } } } else { - Pat::Tuple { args: subpatterns, ellipsis: None } + PatKind::Leaf { subpatterns } } } // Note: given the expansion of `&str` patterns done in `expand_pattern`, we should // be careful to reconstruct the correct constant pattern here. However a string // literal pattern will never be reported as a non-exhaustiveness witness, so we // can ignore this issue. - TyKind::Ref(..) => { - Pat::Ref { pat: subpatterns.next().unwrap(), mutability: Mutability::Shared } - } + TyKind::Ref(..) => PatKind::Deref { subpattern: subpatterns.next().unwrap() }, TyKind::Slice(..) | TyKind::Array(..) => { panic!("bug: bad slice pattern {:?} {:?}", ctor, pcx.ty) } - _ => Pat::Wild, + _ => PatKind::Wild, }, - Constructor::Slice(slice) => TODO, - Str(_) => TODO, - FloatRange(..) => TODO, - Constructor::IntRange(_) => TODO, - NonExhaustive => Pat::Wild, - Wildcard => Pat::Wild, + Constructor::Slice(slice) => UNIMPLEMENTED, + Str(_) => UNIMPLEMENTED, + FloatRange(..) => UNIMPLEMENTED, + Constructor::IntRange(_) => UNIMPLEMENTED, + NonExhaustive => PatKind::Wild, + Wildcard => return Pat::wildcard_from_ty(pcx.ty), Opaque => panic!("bug: we should not try to apply an opaque constructor"), Missing => { panic!("bug: trying to apply the `Missing` constructor; this should have been done in `apply_constructors`") } - } + }; + + Pat { ty: pcx.ty.clone(), kind: Box::new(pat) } } /// Returns the number of patterns. This is the same as the arity of the constructor used to @@ -765,9 +750,14 @@ impl Fields { } /// Returns the list of patterns along with the corresponding field indices. - fn patterns_and_indices(&self) -> SmallVec<[(usize, PatId); 2]> { + fn patterns_and_indices(&self) -> SmallVec<[(LocalFieldId, PatId); 2]> { match self { - Fields::Vec(pats) => pats.iter().copied().enumerate().collect(), + Fields::Vec(pats) => pats + .iter() + .copied() + .enumerate() + .map(|(i, p)| (LocalFieldId::from_raw((i as u32).into()), p)) + .collect(), } } @@ -779,8 +769,13 @@ impl Fields { /// Overrides some of the fields with the provided patterns. Exactly like /// `replace_fields_indexed`, except that it takes `FieldPat`s as input. - fn replace_with_fieldpats(&self, new_pats: impl IntoIterator) -> Self { - self.replace_fields_indexed(new_pats.into_iter().enumerate()) + fn replace_with_fieldpats( + &self, + new_pats: impl IntoIterator, + ) -> Self { + self.replace_fields_indexed( + new_pats.into_iter().map(|(field, pat)| (u32::from(field.into_raw()) as usize, pat)), + ) } /// Overrides some of the fields with the provided patterns. This is used when a pattern @@ -814,10 +809,7 @@ impl Fields { let tys: SmallVec<[Ty; 2]> = match self { Fields::Vec(pats) => pats.iter().copied().map(|pat| cx.type_of(pat)).collect(), }; - pats.into_iter() - .zip(tys.into_iter()) - .map(move |(pat, ty)| cx.alloc_pat(pat, &ty)) - .collect() + pats.into_iter().zip(tys.into_iter()).map(move |(pat, ty)| cx.alloc_pat(pat)).collect() }; match self { @@ -845,42 +837,24 @@ impl Fields { pat: PatId, cx: &MatchCheckCtx<'_>, ) -> Self { - match &cx.pattern_arena.borrow()[pat] { - Pat::Ref { pat: subpattern, .. } | Pat::Box { inner: subpattern } => { + // TODO: these alocations are so unfortunate (+1 for switching to references) + match cx.pattern_arena.borrow()[pat].kind.as_ref() { + PatKind::Deref { subpattern } => { assert_eq!(self.len(), 1); - Fields::from_single_pattern(*subpattern) + let subpattern = cx.pattern_arena.borrow_mut().alloc(subpattern.clone()); + Fields::from_single_pattern(subpattern) } - Pat::Tuple { args, ellipsis } | Pat::TupleStruct { args, ellipsis, .. } => { - // FIXME(iDawer) handle ellipsis. - // XXX(iDawer): in rustc, this is handled by HIR->TypedHIR lowering - // rustc_mir_build::thir::pattern::PatCtxt::lower_tuple_subpats(..) - self.replace_with_fieldpats(args.iter().copied()) - } - Pat::Record { args, ellipsis, .. } => { - let variant_id = - cx.infer.variant_resolution_for_pat(pat).unwrap_or_else(|| todo!()); - let variant_data = variant_id.variant_data(cx.db.upcast()); - - let new_pats = args.iter().map(|field_pat| { - // TODO: field lookup is inefficient - let raw = - variant_data.field(&field_pat.name).unwrap_or_else(|| todo!()).into_raw(); - let idx = u32::from(raw) as usize; - (idx, field_pat.pat) + PatKind::Leaf { subpatterns } | PatKind::Variant { subpatterns, .. } => { + let subpatterns = subpatterns.iter().map(|field_pat| { + ( + field_pat.field, + cx.pattern_arena.borrow_mut().alloc(field_pat.pattern.clone()), + ) }); - self.replace_fields_indexed(new_pats) - } - Pat::Slice { .. } => { - todo!() + self.replace_with_fieldpats(subpatterns) } - Pat::Missing - | Pat::Wild - | Pat::Or(_) - | Pat::Range { .. } - | Pat::Path(_) - | Pat::Lit(_) - | Pat::Bind { .. } - | Pat::ConstBlock(_) => self.clone(), + + PatKind::Wild | PatKind::Binding { .. } | PatKind::Or { .. } => self.clone(), } } } diff --git a/crates/hir_ty/src/diagnostics/pattern/pat_util.rs b/crates/hir_ty/src/diagnostics/pattern/pat_util.rs new file mode 100644 index 000000000..f8ad4e7c6 --- /dev/null +++ b/crates/hir_ty/src/diagnostics/pattern/pat_util.rs @@ -0,0 +1,52 @@ +use std::iter::{Enumerate, ExactSizeIterator}; + +pub struct EnumerateAndAdjust { + enumerate: Enumerate, + gap_pos: usize, + gap_len: usize, +} + +impl Iterator for EnumerateAndAdjust +where + I: Iterator, +{ + type Item = (usize, ::Item); + + fn next(&mut self) -> Option<(usize, ::Item)> { + self.enumerate + .next() + .map(|(i, elem)| (if i < self.gap_pos { i } else { i + self.gap_len }, elem)) + } + + fn size_hint(&self) -> (usize, Option) { + self.enumerate.size_hint() + } +} + +pub trait EnumerateAndAdjustIterator { + fn enumerate_and_adjust( + self, + expected_len: usize, + gap_pos: Option, + ) -> EnumerateAndAdjust + where + Self: Sized; +} + +impl EnumerateAndAdjustIterator for T { + fn enumerate_and_adjust( + self, + expected_len: usize, + gap_pos: Option, + ) -> EnumerateAndAdjust + where + Self: Sized, + { + let actual_len = self.len(); + EnumerateAndAdjust { + enumerate: self.enumerate(), + gap_pos: gap_pos.unwrap_or(expected_len), + gap_len: expected_len - actual_len, + } + } +} diff --git a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs index 2df87ccea..28b9e71f8 100644 --- a/crates/hir_ty/src/diagnostics/pattern/usefulness.rs +++ b/crates/hir_ty/src/diagnostics/pattern/usefulness.rs @@ -3,11 +3,7 @@ use std::{cell::RefCell, iter::FromIterator, ops::Index, sync::Arc}; -use hir_def::{ - body::Body, - expr::{ExprId, Pat, PatId}, - HasModule, ModuleId, -}; +use hir_def::{body::Body, expr::ExprId, HasModule, ModuleId}; use la_arena::Arena; use once_cell::unsync::OnceCell; use rustc_hash::FxHashMap; @@ -15,7 +11,10 @@ use smallvec::{smallvec, SmallVec}; use crate::{db::HirDatabase, InferenceResult, Ty}; -use super::deconstruct_pat::{Constructor, Fields, SplitWildcard}; +use super::{ + deconstruct_pat::{Constructor, Fields, SplitWildcard}, + Pat, PatId, PatKind, +}; use self::{ helper::{Captures, PatIdExt}, @@ -55,14 +54,13 @@ impl<'a> MatchCheckCtx<'a> { false } - pub(super) fn alloc_pat(&self, pat: Pat, ty: &Ty) -> PatId { - self.pattern_arena.borrow_mut().alloc(pat, ty) + pub(super) fn alloc_pat(&self, pat: Pat) -> PatId { + self.pattern_arena.borrow_mut().alloc(pat) } /// Get type of a pattern. Handles expanded patterns. pub(super) fn type_of(&self, pat: PatId) -> Ty { - let type_of_expanded_pat = self.pattern_arena.borrow().type_of_epat.get(&pat).cloned(); - type_of_expanded_pat.unwrap_or_else(|| self.infer[pat].clone()) + self.pattern_arena.borrow()[pat].ty.clone() } } @@ -76,30 +74,40 @@ pub(super) struct PatCtxt<'a> { pub(super) is_top_level: bool, } -impl PatIdExt for PatId { - fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool { - matches!(cx.pattern_arena.borrow()[self], Pat::Bind { subpat: None, .. } | Pat::Wild) +pub(crate) fn expand_pattern(pat: Pat) -> Pat { + // TODO: LiteralExpander, it is about string literal patterns + pat +} + +impl Pat { + fn is_wildcard(&self) -> bool { + matches!(*self.kind, PatKind::Binding { subpattern: None, .. } | PatKind::Wild) } +} +impl PatIdExt for PatId { fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool { - matches!(cx.pattern_arena.borrow()[self], Pat::Or(..)) + matches!(*cx.pattern_arena.borrow()[self].kind, PatKind::Or { .. }) } /// Recursively expand this pattern into its subpatterns. Only useful for or-patterns. fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec { - fn expand(pat: PatId, vec: &mut Vec, pat_arena: &PatternArena) { - if let Pat::Or(pats) = &pat_arena[pat] { - for &pat in pats { - expand(pat, vec, pat_arena); - } + fn expand(pat: PatId, vec: &mut Vec, mut pat_arena: &mut PatternArena) { + if let PatKind::Or { pats } = pat_arena[pat].kind.as_ref() { + // for pat in pats { + // // TODO(iDawer): Ugh, I want to go back to references (PatId -> &Pat) + // let pat = pat_arena.alloc(pat.clone()); + // expand(pat, vec, pat_arena); + // } + todo!() } else { vec.push(pat) } } - let pat_arena = cx.pattern_arena.borrow(); + let mut pat_arena = cx.pattern_arena.borrow_mut(); let mut pats = Vec::new(); - expand(self, &mut pats, &pat_arena); + expand(self, &mut pats, &mut pat_arena); pats } } @@ -866,7 +874,8 @@ pub(crate) fn compute_match_usefulness( }) .collect(); - let wild_pattern = cx.pattern_arena.borrow_mut().alloc(Pat::Wild, &cx.infer[cx.match_expr]); + let wild_pattern = + cx.pattern_arena.borrow_mut().alloc(Pat::wildcard_from_ty(&cx.infer[cx.match_expr])); let v = PatStack::from_pattern(wild_pattern); let usefulness = is_useful(cx, &matrix, &v, ConstructWitness, false, true); let non_exhaustiveness_witnesses = match usefulness { @@ -876,31 +885,7 @@ pub(crate) fn compute_match_usefulness( UsefulnessReport { arm_usefulness, non_exhaustiveness_witnesses } } -pub(crate) struct PatternArena { - arena: Arena, - /// Types of expanded patterns. - type_of_epat: FxHashMap, -} - -impl PatternArena { - pub(crate) fn clone_from(pats: &Arena) -> RefCell { - PatternArena { arena: pats.clone(), type_of_epat: Default::default() }.into() - } - - fn alloc(&mut self, pat: Pat, ty: &Ty) -> PatId { - let id = self.arena.alloc(pat); - self.type_of_epat.insert(id, ty.clone()); - id - } -} - -impl Index for PatternArena { - type Output = Pat; - - fn index(&self, pat: PatId) -> &Pat { - &self.arena[pat] - } -} +pub(crate) type PatternArena = Arena; mod helper { use hir_def::expr::{Pat, PatId}; @@ -908,7 +893,7 @@ mod helper { use super::MatchCheckCtx; pub(super) trait PatIdExt: Sized { - fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool; + // fn is_wildcard(self, cx: &MatchCheckCtx<'_>) -> bool; fn is_or_pat(self, cx: &MatchCheckCtx<'_>) -> bool; fn expand_or_pat(self, cx: &MatchCheckCtx<'_>) -> Vec; } -- cgit v1.2.3