compiler/rustc_ty_utils/src/representability.rs

   1 //! Check whether a type is representable.
   2 use rustc_data_structures::stable_map::FxHashMap;
   3 use rustc_hir as hir;
   4 use rustc_middle::ty::{self, Ty, TyCtxt};
   5 use rustc_span::Span;
   6 use std::cmp;
   7
   8 /// Describes whether a type is representable. For types that are not
   9 /// representable, 'SelfRecursive' and 'ContainsRecursive' are used to
  10 /// distinguish between types that are recursive with themselves and types that
  11 /// contain a different recursive type. These cases can therefore be treated
  12 /// differently when reporting errors.
  13 ///
  14 /// The ordering of the cases is significant. They are sorted so that cmp::max
  15 /// will keep the "more erroneous" of two values.
  16 #[derive(Clone, PartialOrd, Ord, Eq, PartialEq, Debug)]
  17 pub enum Representability {
  18     Representable,
  19     ContainsRecursive,
  20     SelfRecursive(Vec<Span>),
  21 }
  22
  23 /// Check whether a type is representable. This means it cannot contain unboxed
  24 /// structural recursion. This check is needed for structs and enums.
  25 pub fn ty_is_representable<'tcx>(tcx: TyCtxt<'tcx>, ty: Ty<'tcx>, sp: Span) -> Representability {
  26     debug!("is_type_representable: {:?}", ty);
  27     // To avoid a stack overflow when checking an enum variant or struct that
  28     // contains a different, structurally recursive type, maintain a stack
  29     // of seen types and check recursion for each of them (issues #3008, #3779).
  30     let mut seen: Vec<Ty<'_>> = Vec::new();
  31     let mut shadow_seen: Vec<Ty<'_>> = Vec::new();
  32     let mut representable_cache = FxHashMap::default();
  33     let mut f_res = false;
  34     let r = is_type_structurally_recursive(
  35         tcx,
  36         sp,
  37         &mut seen,
  38         &mut shadow_seen,
  39         &mut representable_cache,
  40         ty,
  41         &mut f_res,
  42     );
  43     debug!("is_type_representable: {:?} is {:?}", ty, r);
  44     r
  45 }
  46
  47 // Iterate until something non-representable is found
  48 fn fold_repr<It: Iterator<Item = Representability>>(iter: It) -> Representability {
  49     iter.fold(Representability::Representable, |r1, r2| match (r1, r2) {
  50         (Representability::SelfRecursive(v1), Representability::SelfRecursive(v2)) => {
  51             Representability::SelfRecursive(v1.into_iter().chain(v2).collect())
  52         }
  53         (r1, r2) => cmp::max(r1, r2),
  54     })
  55 }
  56
  57 fn are_inner_types_recursive<'tcx>(
  58     tcx: TyCtxt<'tcx>,
  59     sp: Span,
  60     seen: &mut Vec<Ty<'tcx>>,
  61     shadow_seen: &mut Vec<Ty<'tcx>>,
  62     representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
  63     ty: Ty<'tcx>,
  64     f_res: &mut bool,
  65 ) -> Representability {
  66     debug!("are_inner_types_recursive({:?}, {:?}, {:?})", ty, seen, shadow_seen);
  67     match ty.kind() {
  68         ty::Tuple(..) => {
  69             // Find non representable
  70             fold_repr(ty.tuple_fields().map(|ty| {
  71                 is_type_structurally_recursive(
  72                     tcx,
  73                     sp,
  74                     seen,
  75                     shadow_seen,
  76                     representable_cache,
  77                     ty,
  78                     f_res,
  79                 )
  80             }))
  81         }
  82         // Fixed-length vectors.
  83         // FIXME(#11924) Behavior undecided for zero-length vectors.
  84         ty::Array(ty, _) => is_type_structurally_recursive(
  85             tcx,
  86             sp,
  87             seen,
  88             shadow_seen,
  89             representable_cache,
  90             ty,
  91             f_res,
  92         ),
  93         ty::Adt(def, substs) => {
  94             // Find non representable fields with their spans
  95             fold_repr(def.all_fields().map(|field| {
  96                 let ty = field.ty(tcx, substs);
  97                 let span = match field
  98                     .did
  99                     .as_local()
 100                     .map(|id| tcx.hir().local_def_id_to_hir_id(id))
 101                     .and_then(|id| tcx.hir().find(id))
 102                 {
 103                     Some(hir::Node::Field(field)) => field.ty.span,
 104                     _ => sp,
 105                 };
 106
 107                 let mut result = None;
 108
 109                 // First, we check whether the field type per se is representable.
 110                 // This catches cases as in #74224 and #84611. There is a special
 111                 // case related to mutual recursion, though; consider this example:
 112                 //
 113                 //   struct A<T> {
 114                 //       z: T,
 115                 //       x: B<T>,
 116                 //   }
 117                 //
 118                 //   struct B<T> {
 119                 //       y: A<T>
 120                 //   }
 121                 //
 122                 // Here, without the following special case, both A and B are
 123                 // ContainsRecursive, which is a problem because we only report
 124                 // errors for SelfRecursive. We fix this by detecting this special
 125                 // case (shadow_seen.first() is the type we are originally
 126                 // interested in, and if we ever encounter the same AdtDef again,
 127                 // we know that it must be SelfRecursive) and "forcibly" returning
 128                 // SelfRecursive (by setting f_res, which tells the calling
 129                 // invocations of are_inner_types_representable to forward the
 130                 // result without adjusting).
 131                 if shadow_seen.len() > 1 && shadow_seen.len() > seen.len() {
 132                     match shadow_seen.first().map(|ty| ty.kind()) {
 133                         Some(ty::Adt(f_def, _)) => {
 134                             if f_def == def {
 135                                 *f_res = true;
 136                                 result = Some(Representability::SelfRecursive(vec![span]));
 137                             }
 138                         }
 139                         Some(_) => {
 140                             bug!("shadow_seen stack contains non-ADT type: {:?}", ty);
 141                         }
 142                         None => unreachable!(),
 143                     }
 144                 }
 145
 146                 if result == None {
 147                     result = Some(Representability::Representable);
 148
 149                     // Now, we check whether the field types per se are representable, e.g.
 150                     // for struct Foo { x: Option<Foo> }, we first check whether Option<_>
 151                     // by itself is representable (which it is), and the nesting of Foo
 152                     // will be detected later. This is necessary for #74224 and #84611.
 153
 154                     // If we have encountered an ADT definition that we have not seen
 155                     // before (no need to check them twice), recurse to see whether that
 156                     // definition is SelfRecursive. If so, we must be ContainsRecursive.
 157                     if shadow_seen.iter().len() > 1
 158                         && !shadow_seen.iter().take(shadow_seen.iter().len() - 1).any(|seen_ty| {
 159                             match seen_ty.kind() {
 160                                 ty::Adt(seen_def, _) => seen_def == def,
 161                                 _ => {
 162                                     bug!("seen stack contains non-ADT type: {:?}", seen_ty);
 163                                 }
 164                             }
 165                         })
 166                     {
 167                         let adt_def_id = def.did;
 168                         let raw_adt_ty = tcx.type_of(adt_def_id);
 169                         debug!("are_inner_types_recursive: checking nested type: {:?}", raw_adt_ty);
 170
 171                         // Check independently whether the ADT is SelfRecursive. If so,
 172                         // we must be ContainsRecursive (except for the special case
 173                         // mentioned above).
 174                         let mut nested_seen: Vec<Ty<'_>> = vec![];
 175                         result = Some(
 176                             match is_type_structurally_recursive(
 177                                 tcx,
 178                                 span,
 179                                 &mut nested_seen,
 180                                 shadow_seen,
 181                                 representable_cache,
 182                                 raw_adt_ty,
 183                                 f_res,
 184                             ) {
 185                                 Representability::SelfRecursive(_) => {
 186                                     if *f_res {
 187                                         Representability::SelfRecursive(vec![span])
 188                                     } else {
 189                                         Representability::ContainsRecursive
 190                                     }
 191                                 }
 192                                 x => x,
 193                             },
 194                         );
 195                     }
 196
 197                     // We only enter the following block if the type looks representable
 198                     // so far. This is necessary for cases such as this one (#74224):
 199                     //
 200                     //   struct A<T> {
 201                     //       x: T,
 202                     //       y: A<A<T>>,
 203                     //   }
 204                     //
 205                     //   struct B {
 206                     //       z: A<usize>
 207                     //   }
 208                     //
 209                     // When checking B, we recurse into A and check field y of type
 210                     // A<A<usize>>. We haven't seen this exact type before, so we recurse
 211                     // into A<A<usize>>, which contains, A<A<A<usize>>>, and so forth,
 212                     // ad infinitum. We can prevent this from happening by first checking
 213                     // A separately (the code above) and only checking for nested Bs if
 214                     // A actually looks representable (which it wouldn't in this example).
 215                     if result == Some(Representability::Representable) {
 216                         // Now, even if the type is representable (e.g. Option<_>),
 217                         // it might still contribute to a recursive type, e.g.:
 218                         //   struct Foo { x: Option<Option<Foo>> }
 219                         // These cases are handled by passing the full `seen`
 220                         // stack to is_type_structurally_recursive (instead of the
 221                         // empty `nested_seen` above):
 222                         result = Some(
 223                             match is_type_structurally_recursive(
 224                                 tcx,
 225                                 span,
 226                                 seen,
 227                                 shadow_seen,
 228                                 representable_cache,
 229                                 ty,
 230                                 f_res,
 231                             ) {
 232                                 Representability::SelfRecursive(_) => {
 233                                     Representability::SelfRecursive(vec![span])
 234                                 }
 235                                 x => x,
 236                             },
 237                         );
 238                     }
 239                 }
 240
 241                 result.unwrap()
 242             }))
 243         }
 244         ty::Closure(..) => {
 245             // this check is run on type definitions, so we don't expect
 246             // to see closure types
 247             bug!("requires check invoked on inapplicable type: {:?}", ty)
 248         }
 249         _ => Representability::Representable,
 250     }
 251 }
 252
 253 fn same_adt<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
 254     match *ty.kind() {
 255         ty::Adt(ty_def, _) => ty_def == def,
 256         _ => false,
 257     }
 258 }
 259
 260 // Does the type `ty` directly (without indirection through a pointer)
 261 // contain any types on stack `seen`?
 262 fn is_type_structurally_recursive<'tcx>(
 263     tcx: TyCtxt<'tcx>,
 264     sp: Span,
 265     seen: &mut Vec<Ty<'tcx>>,
 266     shadow_seen: &mut Vec<Ty<'tcx>>,
 267     representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
 268     ty: Ty<'tcx>,
 269     f_res: &mut bool,
 270 ) -> Representability {
 271     debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
 272     if let Some(representability) = representable_cache.get(ty) {
 273         debug!(
 274             "is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
 275             ty, sp, representability
 276         );
 277         return representability.clone();
 278     }
 279
 280     let representability = is_type_structurally_recursive_inner(
 281         tcx,
 282         sp,
 283         seen,
 284         shadow_seen,
 285         representable_cache,
 286         ty,
 287         f_res,
 288     );
 289
 290     representable_cache.insert(ty, representability.clone());
 291     representability
 292 }
 293
 294 fn is_type_structurally_recursive_inner<'tcx>(
 295     tcx: TyCtxt<'tcx>,
 296     sp: Span,
 297     seen: &mut Vec<Ty<'tcx>>,
 298     shadow_seen: &mut Vec<Ty<'tcx>>,
 299     representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
 300     ty: Ty<'tcx>,
 301     f_res: &mut bool,
 302 ) -> Representability {
 303     match ty.kind() {
 304         ty::Adt(def, _) => {
 305             {
 306                 debug!("is_type_structurally_recursive_inner: adt: {:?}, seen: {:?}", ty, seen);
 307
 308                 // Iterate through stack of previously seen types.
 309                 let mut iter = seen.iter();
 310
 311                 // The first item in `seen` is the type we are actually curious about.
 312                 // We want to return SelfRecursive if this type contains itself.
 313                 // It is important that we DON'T take generic parameters into account
 314                 // for this check, so that Bar<T> in this example counts as SelfRecursive:
 315                 //
 316                 // struct Foo;
 317                 // struct Bar<T> { x: Bar<Foo> }
 318
 319                 if let Some(&seen_adt) = iter.next() {
 320                     if same_adt(seen_adt, *def) {
 321                         debug!("SelfRecursive: {:?} contains {:?}", seen_adt, ty);
 322                         return Representability::SelfRecursive(vec![sp]);
 323                     }
 324                 }
 325
 326                 // We also need to know whether the first item contains other types
 327                 // that are structurally recursive. If we don't catch this case, we
 328                 // will recurse infinitely for some inputs.
 329                 //
 330                 // It is important that we DO take generic parameters into account
 331                 // here, because nesting e.g. Options is allowed (as long as the
 332                 // definition of Option doesn't itself include an Option field, which
 333                 // would be a case of SelfRecursive above). The following, too, counts
 334                 // as SelfRecursive:
 335                 //
 336                 // struct Foo { Option<Option<Foo>> }
 337
 338                 for &seen_adt in iter {
 339                     if ty::TyS::same_type(ty, seen_adt) {
 340                         debug!("ContainsRecursive: {:?} contains {:?}", seen_adt, ty);
 341                         return Representability::ContainsRecursive;
 342                     }
 343                 }
 344             }
 345
 346             // For structs and enums, track all previously seen types by pushing them
 347             // onto the 'seen' stack.
 348             seen.push(ty);
 349             shadow_seen.push(ty);
 350             let out = are_inner_types_recursive(
 351                 tcx,
 352                 sp,
 353                 seen,
 354                 shadow_seen,
 355                 representable_cache,
 356                 ty,
 357                 f_res,
 358             );
 359             shadow_seen.pop();
 360             seen.pop();
 361             out
 362         }
 363         _ => {
 364             // No need to push in other cases.
 365             are_inner_types_recursive(tcx, sp, seen, shadow_seen, representable_cache, ty, f_res)
 366         }
 367     }
 368 }