diff options
Diffstat (limited to 'compiler/rustc_ty_utils/src/representability.rs')
| -rw-r--r-- | compiler/rustc_ty_utils/src/representability.rs | 386 |
1 files changed, 386 insertions, 0 deletions
diff --git a/compiler/rustc_ty_utils/src/representability.rs b/compiler/rustc_ty_utils/src/representability.rs new file mode 100644 index 000000000..eded78916 --- /dev/null +++ b/compiler/rustc_ty_utils/src/representability.rs @@ -0,0 +1,386 @@ +//! Check whether a type is representable. +use rustc_data_structures::fx::FxHashMap; +use rustc_hir as hir; +use rustc_middle::ty::{self, Ty, TyCtxt}; +use rustc_span::Span; +use std::cmp; + +/// Describes whether a type is representable. For types that are not +/// representable, 'SelfRecursive' and 'ContainsRecursive' are used to +/// distinguish between types that are recursive with themselves and types that +/// contain a different recursive type. These cases can therefore be treated +/// differently when reporting errors. +/// +/// The ordering of the cases is significant. They are sorted so that cmp::max +/// will keep the "more erroneous" of two values. +#[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)] +pub enum Representability { + Representable, + ContainsRecursive, + /// Return a list of types that are included in themselves: + /// the spans where they are self-included, and (if found) + /// the HirId of the FieldDef that defines the self-inclusion. + SelfRecursive(Vec<(Span, Option<hir::HirId>)>), +} + +/// Check whether a type is representable. This means it cannot contain unboxed +/// structural recursion. This check is needed for structs and enums. +pub fn ty_is_representable<'tcx>( + tcx: TyCtxt<'tcx>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, +) -> Representability { + debug!("is_type_representable: {:?}", ty); + // To avoid a stack overflow when checking an enum variant or struct that + // contains a different, structurally recursive type, maintain a stack of + // seen types and check recursion for each of them (issues #3008, #3779, + // #74224, #84611). `shadow_seen` contains the full stack and `seen` only + // the one for the current type (e.g. if we have structs A and B, B contains + // a field of type A, and we're currently looking at B, then `seen` will be + // cleared when recursing to check A, but `shadow_seen` won't, so that we + // can catch cases of mutual recursion where A also contains B). + let mut seen: Vec<Ty<'_>> = Vec::new(); + let mut shadow_seen: Vec<ty::AdtDef<'tcx>> = Vec::new(); + let mut representable_cache = FxHashMap::default(); + let mut force_result = false; + let r = is_type_structurally_recursive( + tcx, + &mut seen, + &mut shadow_seen, + &mut representable_cache, + ty, + sp, + field_id, + &mut force_result, + ); + debug!("is_type_representable: {:?} is {:?}", ty, r); + r +} + +// Iterate until something non-representable is found +fn fold_repr<It: Iterator<Item = Representability>>(iter: It) -> Representability { + iter.fold(Representability::Representable, |r1, r2| match (r1, r2) { + (Representability::SelfRecursive(v1), Representability::SelfRecursive(v2)) => { + Representability::SelfRecursive(v1.into_iter().chain(v2).collect()) + } + (r1, r2) => cmp::max(r1, r2), + }) +} + +fn are_inner_types_recursive<'tcx>( + tcx: TyCtxt<'tcx>, + seen: &mut Vec<Ty<'tcx>>, + shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, + representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, + force_result: &mut bool, +) -> Representability { + debug!("are_inner_types_recursive({:?}, {:?}, {:?})", ty, seen, shadow_seen); + match ty.kind() { + ty::Tuple(fields) => { + // Find non representable + fold_repr(fields.iter().map(|ty| { + is_type_structurally_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ) + })) + } + // Fixed-length vectors. + // FIXME(#11924) Behavior undecided for zero-length vectors. + ty::Array(ty, _) => is_type_structurally_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + *ty, + sp, + field_id, + force_result, + ), + ty::Adt(def, substs) => { + // Find non representable fields with their spans + fold_repr(def.all_fields().map(|field| { + let ty = field.ty(tcx, substs); + let (sp, field_id) = match field + .did + .as_local() + .map(|id| tcx.hir().local_def_id_to_hir_id(id)) + .and_then(|id| tcx.hir().find(id)) + { + Some(hir::Node::Field(field)) => (field.ty.span, Some(field.hir_id)), + _ => (sp, field_id), + }; + + let mut result = None; + + // First, we check whether the field type per se is representable. + // This catches cases as in #74224 and #84611. There is a special + // case related to mutual recursion, though; consider this example: + // + // struct A<T> { + // z: T, + // x: B<T>, + // } + // + // struct B<T> { + // y: A<T> + // } + // + // Here, without the following special case, both A and B are + // ContainsRecursive, which is a problem because we only report + // errors for SelfRecursive. We fix this by detecting this special + // case (shadow_seen.first() is the type we are originally + // interested in, and if we ever encounter the same AdtDef again, + // we know that it must be SelfRecursive) and "forcibly" returning + // SelfRecursive (by setting force_result, which tells the calling + // invocations of are_inner_types_representable to forward the + // result without adjusting). + if shadow_seen.len() > seen.len() && shadow_seen.first() == Some(def) { + *force_result = true; + result = Some(Representability::SelfRecursive(vec![(sp, field_id)])); + } + + if result == None { + result = Some(Representability::Representable); + + // Now, we check whether the field types per se are representable, e.g. + // for struct Foo { x: Option<Foo> }, we first check whether Option<_> + // by itself is representable (which it is), and the nesting of Foo + // will be detected later. This is necessary for #74224 and #84611. + + // If we have encountered an ADT definition that we have not seen + // before (no need to check them twice), recurse to see whether that + // definition is SelfRecursive. If so, we must be ContainsRecursive. + if shadow_seen.len() > 1 + && !shadow_seen + .iter() + .take(shadow_seen.len() - 1) + .any(|seen_def| seen_def == def) + { + let adt_def_id = def.did(); + let raw_adt_ty = tcx.type_of(adt_def_id); + debug!("are_inner_types_recursive: checking nested type: {:?}", raw_adt_ty); + + // Check independently whether the ADT is SelfRecursive. If so, + // we must be ContainsRecursive (except for the special case + // mentioned above). + let mut nested_seen: Vec<Ty<'_>> = vec![]; + result = Some( + match is_type_structurally_recursive( + tcx, + &mut nested_seen, + shadow_seen, + representable_cache, + raw_adt_ty, + sp, + field_id, + force_result, + ) { + Representability::SelfRecursive(_) => { + if *force_result { + Representability::SelfRecursive(vec![(sp, field_id)]) + } else { + Representability::ContainsRecursive + } + } + x => x, + }, + ); + } + + // We only enter the following block if the type looks representable + // so far. This is necessary for cases such as this one (#74224): + // + // struct A<T> { + // x: T, + // y: A<A<T>>, + // } + // + // struct B { + // z: A<usize> + // } + // + // When checking B, we recurse into A and check field y of type + // A<A<usize>>. We haven't seen this exact type before, so we recurse + // into A<A<usize>>, which contains, A<A<A<usize>>>, and so forth, + // ad infinitum. We can prevent this from happening by first checking + // A separately (the code above) and only checking for nested Bs if + // A actually looks representable (which it wouldn't in this example). + if result == Some(Representability::Representable) { + // Now, even if the type is representable (e.g. Option<_>), + // it might still contribute to a recursive type, e.g.: + // struct Foo { x: Option<Option<Foo>> } + // These cases are handled by passing the full `seen` + // stack to is_type_structurally_recursive (instead of the + // empty `nested_seen` above): + result = Some( + match is_type_structurally_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ) { + Representability::SelfRecursive(_) => { + Representability::SelfRecursive(vec![(sp, field_id)]) + } + x => x, + }, + ); + } + } + + result.unwrap() + })) + } + ty::Closure(..) => { + // this check is run on type definitions, so we don't expect + // to see closure types + bug!("requires check invoked on inapplicable type: {:?}", ty) + } + _ => Representability::Representable, + } +} + +fn same_adt<'tcx>(ty: Ty<'tcx>, def: ty::AdtDef<'tcx>) -> bool { + match *ty.kind() { + ty::Adt(ty_def, _) => ty_def == def, + _ => false, + } +} + +// Does the type `ty` directly (without indirection through a pointer) +// contain any types on stack `seen`? +fn is_type_structurally_recursive<'tcx>( + tcx: TyCtxt<'tcx>, + seen: &mut Vec<Ty<'tcx>>, + shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, + representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, + force_result: &mut bool, +) -> Representability { + debug!("is_type_structurally_recursive: {:?} {:?} {:?}", ty, sp, field_id); + if let Some(representability) = representable_cache.get(&ty) { + debug!( + "is_type_structurally_recursive: {:?} {:?} {:?} - (cached) {:?}", + ty, sp, field_id, representability + ); + return representability.clone(); + } + + let representability = is_type_structurally_recursive_inner( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ); + + representable_cache.insert(ty, representability.clone()); + representability +} + +fn is_type_structurally_recursive_inner<'tcx>( + tcx: TyCtxt<'tcx>, + seen: &mut Vec<Ty<'tcx>>, + shadow_seen: &mut Vec<ty::AdtDef<'tcx>>, + representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>, + ty: Ty<'tcx>, + sp: Span, + field_id: Option<hir::HirId>, + force_result: &mut bool, +) -> Representability { + match ty.kind() { + ty::Adt(def, _) => { + { + debug!("is_type_structurally_recursive_inner: adt: {:?}, seen: {:?}", ty, seen); + + // Iterate through stack of previously seen types. + let mut iter = seen.iter(); + + // The first item in `seen` is the type we are actually curious about. + // We want to return SelfRecursive if this type contains itself. + // It is important that we DON'T take generic parameters into account + // for this check, so that Bar<T> in this example counts as SelfRecursive: + // + // struct Foo; + // struct Bar<T> { x: Bar<Foo> } + + if let Some(&seen_adt) = iter.next() { + if same_adt(seen_adt, *def) { + debug!("SelfRecursive: {:?} contains {:?}", seen_adt, ty); + return Representability::SelfRecursive(vec![(sp, field_id)]); + } + } + + // We also need to know whether the first item contains other types + // that are structurally recursive. If we don't catch this case, we + // will recurse infinitely for some inputs. + // + // It is important that we DO take generic parameters into account + // here, because nesting e.g. Options is allowed (as long as the + // definition of Option doesn't itself include an Option field, which + // would be a case of SelfRecursive above). The following, too, counts + // as SelfRecursive: + // + // struct Foo { Option<Option<Foo>> } + + for &seen_adt in iter { + if ty == seen_adt { + debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty); + return Representability::ContainsRecursive; + } + } + } + + // For structs and enums, track all previously seen types by pushing them + // onto the 'seen' stack. + seen.push(ty); + shadow_seen.push(*def); + let out = are_inner_types_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ); + shadow_seen.pop(); + seen.pop(); + out + } + _ => { + // No need to push in other cases. + are_inner_types_recursive( + tcx, + seen, + shadow_seen, + representable_cache, + ty, + sp, + field_id, + force_result, + ) + } + } +} |