pub fn is_representable(&'tcx self,
                            tcx: TyCtxt<'a, 'tcx, 'tcx>,
                            sp: Span)
                            -> Representability {

        // 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.iter().map(|s| *s).chain(v2).collect())
                    }
                    (r1, r2) => cmp::max(r1, r2)
                }
            })
        }

        fn are_inner_types_recursive<'a, 'tcx>(
            tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span,
            seen: &mut Vec<Ty<'tcx>>,
            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
            ty: Ty<'tcx>)
            -> Representability
        {
            match ty.sty {
                TyTuple(ref ts) => {
                    // Find non representable
                    fold_repr(ts.iter().map(|ty| {
                        is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
                    }))
                }
                // Fixed-length vectors.
                // FIXME(#11924) Behavior undecided for zero-length vectors.
                TyArray(ty, _) => {
                    is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
                }
                TyAdt(def, substs) => {
                    // Find non representable fields with their spans
                    fold_repr(def.all_fields().map(|field| {
                        let ty = field.ty(tcx, substs);
                        let span = tcx.hir.span_if_local(field.did).unwrap_or(sp);
                        match is_type_structurally_recursive(tcx, span, seen,
                                                             representable_cache, ty)
                        {
                            Representability::SelfRecursive(_) => {
                                Representability::SelfRecursive(vec![span])
                            }
                            x => x,
                        }
                    }))
                }
                TyClosure(..) => {
                    // 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_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
            match ty.sty {
                TyAdt(ty_def, _) => {
                     ty_def == def
                }
                _ => false
            }
        }

        fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
            match (&a.sty, &b.sty) {
                (&TyAdt(did_a, substs_a), &TyAdt(did_b, substs_b)) => {
                    if did_a != did_b {
                        return false;
                    }

                    substs_a.types().zip(substs_b.types()).all(|(a, b)| same_type(a, b))
                }
                _ => a == b,
            }
        }

        // Does the type `ty` directly (without indirection through a pointer)
        // contain any types on stack `seen`?
        fn is_type_structurally_recursive<'a, 'tcx>(
            tcx: TyCtxt<'a, 'tcx, 'tcx>,
            sp: Span,
            seen: &mut Vec<Ty<'tcx>>,
            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
            ty: Ty<'tcx>) -> Representability
        {
            debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
            if let Some(representability) = representable_cache.get(ty) {
                debug!("is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
                       ty, sp, representability);
                return representability.clone();
            }

            let representability = is_type_structurally_recursive_inner(
                tcx, sp, seen, representable_cache, ty);

            representable_cache.insert(ty, representability.clone());
            representability
        }

        fn is_type_structurally_recursive_inner<'a, 'tcx>(
            tcx: TyCtxt<'a, 'tcx, 'tcx>,
            sp: Span,
            seen: &mut Vec<Ty<'tcx>>,
            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
            ty: Ty<'tcx>) -> Representability
        {
            match ty.sty {
                TyAdt(def, _) => {
                    {
                        // 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_type) = iter.next() {
                            if same_struct_or_enum(seen_type, def) {
                                debug!("SelfRecursive: {:?} contains {:?}",
                                       seen_type,
                                       ty);
                                return Representability::SelfRecursive(vec![sp]);
                            }
                        }

                        // 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, so that code like this is considered SelfRecursive, not
                        // ContainsRecursive:
                        //
                        // struct Foo { Option<Option<Foo>> }

                        for &seen_type in iter {
                            if same_type(ty, seen_type) {
                                debug!("ContainsRecursive: {:?} contains {:?}",
                                       seen_type,
                                       ty);
                                return Representability::ContainsRecursive;
                            }
                        }
                    }

                    // For structs and enums, track all previously seen types by pushing them
                    // onto the 'seen' stack.
                    seen.push(ty);
                    let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty);
                    seen.pop();
                    out
                }
                _ => {
                    // No need to push in other cases.
                    are_inner_types_recursive(tcx, sp, seen, representable_cache, ty)
                }
            }
        }

        debug!("is_type_representable: {:?}", self);

        // 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).
        let mut seen: Vec<Ty> = Vec::new();
        let mut representable_cache = FxHashMap();
        let r = is_type_structurally_recursive(
            tcx, sp, &mut seen, &mut representable_cache, self);
        debug!("is_type_representable: {:?} is {:?}", self, r);
        r
    }
/// Check whether a type is representable. This means it cannot contain unboxed
/// structural recursion. This check is needed for structs and enums.
Check whether a type is representable. This means it cannot contain unboxed
structural recursion. This check is needed for structs and enums.
Check whether a type is representable . This means it cannot contain unboxed structural recursion . This check is needed for structs and enums .
pub fn is_representable(&'tcx self,
                            tcx: TyCtxt<'a, 'tcx, 'tcx>,
                            sp: Span)
                            -> Representability {
        // 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.iter().map(|s| *s).chain(v2).collect())
                    }
                    (r1, r2) => cmp::max(r1, r2)
                }
            })
        }
        fn are_inner_types_recursive<'a, 'tcx>(
            tcx: TyCtxt<'a, 'tcx, 'tcx>, sp: Span,
            seen: &mut Vec<Ty<'tcx>>,
            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
            ty: Ty<'tcx>)
            -> Representability
        {
            match ty.sty {
                TyTuple(ref ts) => {
                    // Find non representable
                    fold_repr(ts.iter().map(|ty| {
                        is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
                    }))
                }
                // Fixed-length vectors.
                // FIXME(#11924) Behavior undecided for zero-length vectors.
                TyArray(ty, _) => {
                    is_type_structurally_recursive(tcx, sp, seen, representable_cache, ty)
                }
                TyAdt(def, substs) => {
                    // Find non representable fields with their spans
                    fold_repr(def.all_fields().map(|field| {
                        let ty = field.ty(tcx, substs);
                        let span = tcx.hir.span_if_local(field.did).unwrap_or(sp);
                        match is_type_structurally_recursive(tcx, span, seen,
                                                             representable_cache, ty)
                        {
                            Representability::SelfRecursive(_) => {
                                Representability::SelfRecursive(vec![span])
                            }
                            x => x,
                        }
                    }))
                }
                TyClosure(..) => {
                    // 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_struct_or_enum<'tcx>(ty: Ty<'tcx>, def: &'tcx ty::AdtDef) -> bool {
            match ty.sty {
                TyAdt(ty_def, _) => {
                     ty_def == def
                }
                _ => false
            }
        }
        fn same_type<'tcx>(a: Ty<'tcx>, b: Ty<'tcx>) -> bool {
            match (&a.sty, &b.sty) {
                (&TyAdt(did_a, substs_a), &TyAdt(did_b, substs_b)) => {
                    if did_a != did_b {
                        return false;
                    }
                    substs_a.types().zip(substs_b.types()).all(|(a, b)| same_type(a, b))
                }
                _ => a == b,
            }
        }
        // Does the type `ty` directly (without indirection through a pointer)
        // contain any types on stack `seen`?
        fn is_type_structurally_recursive<'a, 'tcx>(
            tcx: TyCtxt<'a, 'tcx, 'tcx>,
            sp: Span,
            seen: &mut Vec<Ty<'tcx>>,
            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
            ty: Ty<'tcx>) -> Representability
        {
            debug!("is_type_structurally_recursive: {:?} {:?}", ty, sp);
            if let Some(representability) = representable_cache.get(ty) {
                debug!("is_type_structurally_recursive: {:?} {:?} - (cached) {:?}",
                       ty, sp, representability);
                return representability.clone();
            }
            let representability = is_type_structurally_recursive_inner(
                tcx, sp, seen, representable_cache, ty);
            representable_cache.insert(ty, representability.clone());
            representability
        }
        fn is_type_structurally_recursive_inner<'a, 'tcx>(
            tcx: TyCtxt<'a, 'tcx, 'tcx>,
            sp: Span,
            seen: &mut Vec<Ty<'tcx>>,
            representable_cache: &mut FxHashMap<Ty<'tcx>, Representability>,
            ty: Ty<'tcx>) -> Representability
        {
            match ty.sty {
                TyAdt(def, _) => {
                    {
                        // 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_type) = iter.next() {
                            if same_struct_or_enum(seen_type, def) {
                                debug!("SelfRecursive: {:?} contains {:?}",
                                       seen_type,
                                       ty);
                                return Representability::SelfRecursive(vec![sp]);
                            }
                        }
                        // 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, so that code like this is considered SelfRecursive, not
                        // ContainsRecursive:
                        //
                        // struct Foo { Option<Option<Foo>> }
                        for &seen_type in iter {
                            if same_type(ty, seen_type) {
                                debug!("ContainsRecursive: {:?} contains {:?}",
                                       seen_type,
                                       ty);
                                return Representability::ContainsRecursive;
                            }
                        }
                    }
                    // For structs and enums, track all previously seen types by pushing them
                    // onto the 'seen' stack.
                    seen.push(ty);
                    let out = are_inner_types_recursive(tcx, sp, seen, representable_cache, ty);
                    seen.pop();
                    out
                }
                _ => {
                    // No need to push in other cases.
                    are_inner_types_recursive(tcx, sp, seen, representable_cache, ty)
                }
            }
        }
        debug!("is_type_representable: {:?}", self);
        // 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).
        let mut seen: Vec<Ty> = Vec::new();
        let mut representable_cache = FxHashMap();
        let r = is_type_structurally_recursive(
            tcx, sp, &mut seen, &mut representable_cache, self);
        debug!("is_type_representable: {:?} is {:?}", self, r);
        r
    }
pub fn is_representable ( & ' tcx self , tcx : TyCtxt < ' a , ' tcx , ' tcx > , sp : Span ) -> Representability { // 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 . iter ( ) . map ( | s | * s ) . chain ( v2 ) . collect ( ) ) } ( r1 , r2 ) => cmp :: max ( r1 , r2 ) } } ) } fn are_inner_types_recursive < ' a , ' tcx > ( tcx : TyCtxt < ' a , ' tcx , ' tcx > , sp : Span , seen : & mut Vec < Ty < ' tcx > > , representable_cache : & mut FxHashMap < Ty < ' tcx > , Representability > , ty : Ty < ' tcx > ) -> Representability { match ty . sty { TyTuple ( ref ts ) => { // Find non representable fold_repr ( ts . iter ( ) . map ( | ty | { is_type_structurally_recursive ( tcx , sp , seen , representable_cache , ty ) } ) ) } // Fixed-length vectors. // FIXME(#11924) Behavior undecided for zero-length vectors. TyArray ( ty , _ ) => { is_type_structurally_recursive ( tcx , sp , seen , representable_cache , ty ) } TyAdt ( def , substs ) => { // Find non representable fields with their spans fold_repr ( def . all_fields ( ) . map ( | field | { let ty = field . ty ( tcx , substs ) ; let span = tcx . hir . span_if_local ( field . did ) . unwrap_or ( sp ) ; match is_type_structurally_recursive ( tcx , span , seen , representable_cache , ty ) { Representability :: SelfRecursive ( _ ) => { Representability :: SelfRecursive ( vec ! [ span ] ) } x => x , } } ) ) } TyClosure ( .. ) => { // this check is run on type definitions, so we don't expect // to see closure types bug ! ( " " ty ) } _ => Representability :: Representable , } } fn same_struct_or_enum < ' tcx > ( ty : Ty < ' tcx > , def : & ' tcx ty :: AdtDef ) -> bool { match ty . sty { TyAdt ( ty_def , _ ) => { ty_def == def } _ => false } } fn same_type < ' tcx > ( a : Ty < ' tcx > , b : Ty < ' tcx > ) -> bool { match ( & a . sty , & b . sty ) { ( & TyAdt ( did_a , substs_a ) , & TyAdt ( did_b , substs_b ) ) => { if did_a != did_b { return false ; } substs_a . types ( ) . zip ( substs_b . types ( ) ) . all ( | ( a , b ) | same_type ( a , b ) ) } _ => a == b , } } // Does the type `ty` directly (without indirection through a pointer) // contain any types on stack `seen`? fn is_type_structurally_recursive < ' a , ' tcx > ( tcx : TyCtxt < ' a , ' tcx , ' tcx > , sp : Span , seen : & mut Vec < Ty < ' tcx > > , representable_cache : & mut FxHashMap < Ty < ' tcx > , Representability > , ty : Ty < ' tcx > ) -> Representability { debug ! ( " " ty sp ) ; if let Some ( representability ) = representable_cache . get ( ty ) { debug ! ( " " ty sp representability ) ; return representability . clone ( ) ; } let representability = is_type_structurally_recursive_inner ( tcx , sp , seen , representable_cache , ty ) ; representable_cache . insert ( ty , representability . clone ( ) ) ; representability } fn is_type_structurally_recursive_inner < ' a , ' tcx > ( tcx : TyCtxt < ' a , ' tcx , ' tcx > , sp : Span , seen : & mut Vec < Ty < ' tcx > > , representable_cache : & mut FxHashMap < Ty < ' tcx > , Representability > , ty : Ty < ' tcx > ) -> Representability { match ty . sty { TyAdt ( def , _ ) => { { // 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_type ) = iter . next ( ) { if same_struct_or_enum ( seen_type , def ) { debug ! ( " " seen_type ty ) ; return Representability :: SelfRecursive ( vec ! [ sp ] ) ; } } // 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, so that code like this is considered SelfRecursive, not // ContainsRecursive: // // struct Foo { Option<Option<Foo>> } for & seen_type in iter { if same_type ( ty , seen_type ) { debug ! ( " " seen_type ty ) ; return Representability :: ContainsRecursive ; } } } // For structs and enums, track all previously seen types by pushing them // onto the 'seen' stack. seen . push ( ty ) ; let out = are_inner_types_recursive ( tcx , sp , seen , representable_cache , ty ) ; seen . pop ( ) ; out } _ => { // No need to push in other cases. are_inner_types_recursive ( tcx , sp , seen , representable_cache , ty ) } } } debug ! ( " " self ) ; // 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). let mut seen : Vec < Ty > = Vec :: new ( ) ; let mut representable_cache = FxHashMap ( ) ; let r = is_type_structurally_recursive ( tcx , sp , & mut seen , & mut representable_cache , self ) ; debug ! ( " " self r ) ; r }
Check whether a type is representable.
Check whether a type is representable .
&'tcx self
tcx
TyCtxt<'a, 'tcx, 'tcx>
sp
Span