diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/librustc/dep_graph/dep_node.rs | 2 | ||||
| -rw-r--r-- | src/librustc/traits/select.rs | 155 | ||||
| -rw-r--r-- | src/librustc/ty/mod.rs | 151 |
3 files changed, 225 insertions, 83 deletions
diff --git a/src/librustc/dep_graph/dep_node.rs b/src/librustc/dep_graph/dep_node.rs index 536c739bf16..85b4b4f59c4 100644 --- a/src/librustc/dep_graph/dep_node.rs +++ b/src/librustc/dep_graph/dep_node.rs @@ -88,6 +88,7 @@ pub enum DepNode<D: Clone + Debug> { ImplOrTraitItems(D), ItemSignature(D), FieldTy(D), + SizedConstraint(D), TraitItemDefIds(D), InherentImpls(D), ImplItems(D), @@ -193,6 +194,7 @@ impl<D: Clone + Debug> DepNode<D> { ImplOrTraitItems(ref d) => op(d).map(ImplOrTraitItems), ItemSignature(ref d) => op(d).map(ItemSignature), FieldTy(ref d) => op(d).map(FieldTy), + SizedConstraint(ref d) => op(d).map(SizedConstraint), TraitItemDefIds(ref d) => op(d).map(TraitItemDefIds), InherentImpls(ref d) => op(d).map(InherentImpls), ImplItems(ref d) => op(d).map(ImplItems), diff --git a/src/librustc/traits/select.rs b/src/librustc/traits/select.rs index d7528fc3130..9267ea393ac 100644 --- a/src/librustc/traits/select.rs +++ b/src/librustc/traits/select.rs @@ -13,7 +13,6 @@ pub use self::MethodMatchResult::*; pub use self::MethodMatchedData::*; use self::SelectionCandidate::*; -use self::BuiltinBoundConditions::*; use self::EvaluationResult::*; use super::coherence; @@ -232,10 +231,18 @@ struct EvaluatedCandidate<'tcx> { evaluation: EvaluationResult, } -enum BuiltinBoundConditions<'tcx> { - If(ty::Binder<Vec<Ty<'tcx>>>), - ParameterBuiltin, - AmbiguousBuiltin +/// When does the builtin impl for `T: Trait` apply? +enum BuiltinImplConditions<'tcx> { + /// The impl is conditional on T1,T2,.. : Trait + Where(ty::Binder<Vec<Ty<'tcx>>>), + /// There is no built-in impl. There may be some other + /// candidate (a where-clause or user-defined impl). + None, + /// There is *no* impl for this, builtin or not. Ignore + /// all where-clauses. + Never(SelectionError<'tcx>), + /// It is unknown whether there is an impl. + Ambiguous } #[derive(Copy, Clone, Debug, PartialOrd, Ord, PartialEq, Eq)] @@ -1608,6 +1615,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // those will hopefully change to library-defined traits in the // future. + // HACK: if this returns an error, selection exits without considering + // other impls. fn assemble_builtin_bound_candidates<'o>(&mut self, bound: ty::BuiltinBound, obligation: &TraitObligation<'tcx>, @@ -1615,25 +1624,25 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { -> Result<(),SelectionError<'tcx>> { match self.builtin_bound(bound, obligation) { - Ok(If(..)) => { + BuiltinImplConditions::Where(..) => { debug!("builtin_bound: bound={:?}", bound); candidates.vec.push(BuiltinCandidate(bound)); Ok(()) } - Ok(ParameterBuiltin) => { Ok(()) } - Ok(AmbiguousBuiltin) => { + BuiltinImplConditions::None => { Ok(()) } + BuiltinImplConditions::Ambiguous => { debug!("assemble_builtin_bound_candidates: ambiguous builtin"); Ok(candidates.ambiguous = true) } - Err(e) => { Err(e) } + BuiltinImplConditions::Never(e) => { Err(e) } } } fn builtin_bound(&mut self, bound: ty::BuiltinBound, obligation: &TraitObligation<'tcx>) - -> Result<BuiltinBoundConditions<'tcx>,SelectionError<'tcx>> + -> BuiltinImplConditions<'tcx> { // Note: these tests operate on types that may contain bound // regions. To be proper, we ought to skolemize here, but we @@ -1641,6 +1650,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // confirmation step. let self_ty = self.infcx.shallow_resolve(obligation.predicate.0.self_ty()); + + let always = BuiltinImplConditions::Where(ty::Binder(Vec::new())); + let never = BuiltinImplConditions::Never(Unimplemented); + return match self_ty.sty { ty::TyInfer(ty::IntVar(_)) | ty::TyInfer(ty::FloatVar(_)) | @@ -1652,14 +1665,13 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ty::TyFnPtr(_) | ty::TyChar => { // safe for everything - ok_if(Vec::new()) + always } ty::TyBox(_) => { // Box<T> match bound { - ty::BoundCopy => Err(Unimplemented), - - ty::BoundSized => ok_if(Vec::new()), + ty::BoundCopy => never, + ty::BoundSized => always, ty::BoundSync | ty::BoundSend => { bug!("Send/Sync shouldn't occur in builtin_bounds()"); @@ -1669,7 +1681,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ty::TyRawPtr(..) => { // *const T, *mut T match bound { - ty::BoundCopy | ty::BoundSized => ok_if(Vec::new()), + ty::BoundCopy | ty::BoundSized => always, ty::BoundSync | ty::BoundSend => { bug!("Send/Sync shouldn't occur in builtin_bounds()"); @@ -1679,10 +1691,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ty::TyTrait(ref data) => { match bound { - ty::BoundSized => Err(Unimplemented), + ty::BoundSized => never, ty::BoundCopy => { + // FIXME(#32963): bit-rot fungus infestation if data.bounds.builtin_bounds.contains(&bound) { - ok_if(Vec::new()) + always } else { // Recursively check all supertraits to find out if any further // bounds are required and thus we must fulfill. @@ -1692,11 +1705,11 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { let copy_def_id = obligation.predicate.def_id(); for tr in util::supertraits(self.tcx(), principal) { if tr.def_id() == copy_def_id { - return ok_if(Vec::new()) + return always } } - Err(Unimplemented) + never } } ty::BoundSync | ty::BoundSend => { @@ -1711,14 +1724,14 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { ty::BoundCopy => { match mutbl { // &mut T is affine and hence never `Copy` - hir::MutMutable => Err(Unimplemented), + hir::MutMutable => never, // &T is always copyable - hir::MutImmutable => ok_if(Vec::new()), + hir::MutImmutable => always } } - ty::BoundSized => ok_if(Vec::new()), + ty::BoundSized => always, ty::BoundSync | ty::BoundSend => { bug!("Send/Sync shouldn't occur in builtin_bounds()"); @@ -1730,7 +1743,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // [T; n] match bound { ty::BoundCopy => ok_if(vec![element_ty]), - ty::BoundSized => ok_if(Vec::new()), + ty::BoundSized => always, ty::BoundSync | ty::BoundSend => { bug!("Send/Sync shouldn't occur in builtin_bounds()"); } @@ -1743,46 +1756,42 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { bug!("Send/Sync shouldn't occur in builtin_bounds()"); } - ty::BoundCopy | ty::BoundSized => Err(Unimplemented), + ty::BoundCopy | ty::BoundSized => never } } // (T1, ..., Tn) -- meets any bound that all of T1...Tn meet ty::TyTuple(ref tys) => ok_if(tys.clone()), - ty::TyClosure(_, ref substs) => { - // FIXME -- This case is tricky. In the case of by-ref - // closures particularly, we need the results of - // inference to decide how to reflect the type of each - // upvar (the upvar may have type `T`, but the runtime - // type could be `&mut`, `&`, or just `T`). For now, - // though, we'll do this unsoundly and assume that all - // captures are by value. Really what we ought to do - // is reserve judgement and then intertwine this - // analysis with closure inference. - - // Unboxed closures shouldn't be - // implicitly copyable - if bound == ty::BoundCopy { - return Ok(ParameterBuiltin); - } + ty::TyClosure(..) => { + match bound { + ty::BoundSync | ty::BoundSend => { + bug!("Send/Sync shouldn't occur in builtin_bounds()"); + } - // Upvars are always local variables or references to - // local variables, and local variables cannot be - // unsized, so the closure struct as a whole must be - // Sized. - if bound == ty::BoundSized { - return ok_if(Vec::new()); + ty::BoundCopy => never, + ty::BoundSized => always } - - ok_if(substs.upvar_tys.clone()) } ty::TyStruct(def, substs) | ty::TyEnum(def, substs) => { - let types: Vec<Ty> = def.all_fields().map(|f| { - f.ty(self.tcx(), substs) - }).collect(); - nominal(bound, types) + match bound { + // Fallback to whatever user-defined impls exist in this case. + ty::BoundCopy => BuiltinImplConditions::None, + + // Sized if all the component types are sized. + ty::BoundSized => { + let sized_crit = def.sized_constraint(self.tcx()); + if sized_crit == self.tcx().types.bool { + always + } else { + ok_if(vec![sized_crit.subst(self.tcx(), substs)]) + } + } + + // Shouldn't be coming through here. + ty::BoundSend | ty::BoundSync => bug!(), + } } ty::TyProjection(_) | ty::TyParam(_) => { @@ -1790,7 +1799,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // particular bound if there is a where clause telling // us that it does, and that case is handled by // `assemble_candidates_from_caller_bounds()`. - Ok(ParameterBuiltin) + BuiltinImplConditions::None } ty::TyInfer(ty::TyVar(_)) => { @@ -1798,10 +1807,10 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { // applicable impls and so forth, depending on what // those type variables wind up being bound to. debug!("assemble_builtin_bound_candidates: ambiguous builtin"); - Ok(AmbiguousBuiltin) + BuiltinImplConditions::Ambiguous } - ty::TyError => ok_if(Vec::new()), + ty::TyError => always, ty::TyInfer(ty::FreshTy(_)) | ty::TyInfer(ty::FreshIntTy(_)) @@ -1811,26 +1820,8 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { } }; - fn ok_if<'tcx>(v: Vec<Ty<'tcx>>) - -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>> { - Ok(If(ty::Binder(v))) - } - - fn nominal<'cx, 'tcx>(bound: ty::BuiltinBound, - types: Vec<Ty<'tcx>>) - -> Result<BuiltinBoundConditions<'tcx>, SelectionError<'tcx>> - { - // First check for markers and other nonsense. - match bound { - // Fallback to whatever user-defined impls exist in this case. - ty::BoundCopy => Ok(ParameterBuiltin), - - // Sized if all the component types are sized. - ty::BoundSized => ok_if(types), - - // Shouldn't be coming through here. - ty::BoundSend | ty::BoundSync => bug!(), - } + fn ok_if<'tcx>(v: Vec<Ty<'tcx>>) -> BuiltinImplConditions<'tcx> { + BuiltinImplConditions::Where(ty::Binder(v)) } } @@ -1999,7 +1990,7 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { match candidate { BuiltinCandidate(builtin_bound) => { Ok(VtableBuiltin( - self.confirm_builtin_candidate(obligation, builtin_bound)?)) + self.confirm_builtin_candidate(obligation, builtin_bound))) } ParamCandidate(param) => { @@ -2100,18 +2091,18 @@ impl<'cx, 'tcx> SelectionContext<'cx, 'tcx> { fn confirm_builtin_candidate(&mut self, obligation: &TraitObligation<'tcx>, bound: ty::BuiltinBound) - -> Result<VtableBuiltinData<PredicateObligation<'tcx>>, - SelectionError<'tcx>> + -> VtableBuiltinData<PredicateObligation<'tcx>> { debug!("confirm_builtin_candidate({:?})", obligation); - match self.builtin_bound(bound, obligation)? { - If(nested) => Ok(self.vtable_builtin_data(obligation, bound, nested)), - AmbiguousBuiltin | ParameterBuiltin => { + match self.builtin_bound(bound, obligation) { + BuiltinImplConditions::Where(nested) => + self.vtable_builtin_data(obligation, bound, nested), + _ => { span_bug!( obligation.cause.span, - "builtin bound for {:?} was ambig", + "confiriming builtin impl for {:?} where none exists", obligation); } } diff --git a/src/librustc/ty/mod.rs b/src/librustc/ty/mod.rs index bc342b235dd..b3ca120bd9f 100644 --- a/src/librustc/ty/mod.rs +++ b/src/librustc/ty/mod.rs @@ -1498,6 +1498,7 @@ pub struct AdtDefData<'tcx, 'container: 'tcx> { pub variants: Vec<VariantDefData<'tcx, 'container>>, destructor: Cell<Option<DefId>>, flags: Cell<AdtFlags>, + sized_constraint: ivar::TyIVar<'tcx, 'container>, } impl<'tcx, 'container> PartialEq for AdtDefData<'tcx, 'container> { @@ -1575,7 +1576,8 @@ impl<'tcx, 'container> AdtDefData<'tcx, 'container> { did: did, variants: variants, flags: Cell::new(flags), - destructor: Cell::new(None) + destructor: Cell::new(None), + sized_constraint: ivar::TyIVar::new(), } } @@ -1716,6 +1718,153 @@ impl<'tcx, 'container> AdtDefData<'tcx, 'container> { None => NoDtor, } } + + /// Returns a simpler type such that `Self: Sized` if and only + /// if that type is Sized, or `TyErr` if this type is recursive. + pub fn sized_constraint(&self, tcx: &ty::TyCtxt<'tcx>) -> Ty<'tcx> { + let dep_node = DepNode::SizedConstraint(self.did); + match self.sized_constraint.get(dep_node) { + None => { + let this = tcx.lookup_adt_def_master(self.did); + this.calculate_sized_constraint_inner(tcx, &mut Vec::new()); + self.sized_constraint.unwrap(dep_node) + } + Some(ty) => ty + } + } +} + +impl<'tcx> AdtDefData<'tcx, 'tcx> { + fn sized_constraint_for_tys<TYS>( + &'tcx self, + tcx: &ty::TyCtxt<'tcx>, + stack: &mut Vec<AdtDefMaster<'tcx>>, + tys: TYS + ) -> Ty<'tcx> + where TYS: IntoIterator<Item=Ty<'tcx>> + { + let tys : Vec<_> = tys.into_iter() + .map(|ty| self.sized_constraint_for_ty(tcx, stack, ty)) + .filter(|ty| *ty != tcx.types.bool) + .collect(); + + match tys.len() { + 0 => tcx.types.bool, + 1 => tys[0], + _ => tcx.mk_tup(tys) + } + } + fn sized_constraint_for_ty( + &'tcx self, + tcx: &ty::TyCtxt<'tcx>, + stack: &mut Vec<AdtDefMaster<'tcx>>, + ty: Ty<'tcx> + ) -> Ty<'tcx> { + let result = match ty.sty { + TyBool | TyChar | TyInt(..) | TyUint(..) | TyFloat(..) | + TyBox(..) | TyRawPtr(..) | TyRef(..) | TyFnDef(..) | TyFnPtr(_) | + TyArray(..) | TyClosure(..) => { + // these are always sized - return a primitive + tcx.types.bool + } + + TyStr | TyTrait(..) | TySlice(_) => { + // these are never sized - return the target type + ty + } + + TyTuple(ref tys) => { + self.sized_constraint_for_tys(tcx, stack, tys.iter().cloned()) + } + + TyEnum(adt, substs) | TyStruct(adt, substs) => { + // recursive case + let adt = tcx.lookup_adt_def_master(adt.did); + adt.calculate_sized_constraint_inner(tcx, stack); + let adt_ty = + adt.sized_constraint + .unwrap(DepNode::SizedConstraint(adt.did)) + .subst(tcx, substs); + debug!("sized_constraint_for_ty({:?}) intermediate = {:?}", + ty, adt_ty); + self.sized_constraint_for_ty(tcx, stack, adt_ty) + } + + TyProjection(..) => { + // must calculate explicitly. + // FIXME: consider special-casing always-Sized projections + ty + } + + TyParam(..) => { + let sized_trait = match tcx.lang_items.sized_trait() { + Some(x) => x, + _ => return ty + }; + let sized_predicate = Binder(TraitRef { + def_id: sized_trait, + substs: tcx.mk_substs(Substs::new_trait( + vec![], vec![], ty + )) + }).to_predicate(); + let predicates = tcx.lookup_predicates(self.did).predicates; + if predicates.into_iter().any(|p| p == sized_predicate) { + tcx.types.bool + } else { + ty + } + } + + TyInfer(..) | TyError => { + bug!("unexpected type `{:?}` in sized_constraint_for_ty", + ty) + } + }; + debug!("sized_constraint_for_ty({:?}) = {:?}", ty, result); + result + } + + /// Calculates the Sized-constraint. This replaces all always-Sized + /// types with bool. I could have made the TyIVar an Option, but that + /// would have been so much code. + fn calculate_sized_constraint_inner(&'tcx self, tcx: &ty::TyCtxt<'tcx>, + stack: &mut Vec<AdtDefMaster<'tcx>>) + { + + let dep_node = DepNode::SizedConstraint(self.did); + + if self.sized_constraint.get(dep_node).is_some() { + return; + } + + if stack.contains(&self) { + debug!("calculate_sized_constraint: {:?} is recursive", self); + self.sized_constraint.fulfill(dep_node, tcx.types.err); + return; + } + + stack.push(self); + let ty = self.sized_constraint_for_tys( + tcx, stack, + self.variants.iter().flat_map(|v| { + v.fields.last() + }).map(|f| f.unsubst_ty()) + ); + + let self_ = stack.pop().unwrap(); + assert_eq!(self_, self); + + match self.sized_constraint.get(dep_node) { + Some(old_ty) => { + debug!("calculate_sized_constraint: {:?} recurred", self); + assert_eq!(old_ty, tcx.types.err) + } + None => { + debug!("calculate_sized_constraint: {:?} => {:?}", self, ty); + self.sized_constraint.fulfill(dep_node, ty) + } + } + } } impl<'tcx, 'container> VariantDefData<'tcx, 'container> { |