chalkify: Add Copy/Clone builtins

3 files changed, 192 insertions, 21 deletions

diff --git a/src/librustc_traits/chalk_context/program_clauses/builtin.rs b/src/librustc_traits/chalk_context/program_clauses/builtin.rs
index ae9f1a27b94..0c6e65d405a 100644
--- a/src/librustc_traits/chalk_context/program_clauses/builtin.rs
+++ b/src/librustc_traits/chalk_context/program_clauses/builtin.rs
@@ -6,10 +6,42 @@ use rustc::traits::{
 };
 use rustc::ty;
 use rustc::ty::subst::{InternalSubsts, Subst};
+use rustc::hir;
 use rustc::hir::def_id::DefId;
 use crate::lowering::Lower;
 use crate::generic_types;
 
+/// Returns a predicate of the form
+/// `Implemented(ty: Trait) :- Implemented(nested: Trait)...`
+/// where `Trait` is specified by `trait_def_id`.
+fn builtin_impl_clause(
+    tcx: ty::TyCtxt<'_, '_, 'tcx>,
+    ty: ty::Ty<'tcx>,
+    nested: &[ty::Ty<'tcx>],
+    trait_def_id: DefId
+) -> ProgramClause<'tcx> {
+    ProgramClause {
+        goal: ty::TraitPredicate {
+            trait_ref: ty::TraitRef {
+                def_id: trait_def_id,
+                substs: tcx.mk_substs_trait(ty, &[]),
+            },
+        }.lower(),
+        hypotheses: tcx.mk_goals(
+            nested.iter()
+                .cloned()
+                .map(|nested_ty| ty::TraitRef {
+                    def_id: trait_def_id,
+                    substs: tcx.mk_substs_trait(nested_ty, &[]),
+                })
+                .map(|trait_ref| ty::TraitPredicate { trait_ref })
+                .map(|pred| GoalKind::DomainGoal(pred.lower()))
+                .map(|goal_kind| tcx.mk_goal(goal_kind))
+        ),
+        category: ProgramClauseCategory::Other,
+    }
+}
+
 crate fn assemble_builtin_unsize_impls<'tcx>(
     tcx: ty::TyCtxt<'_, '_, 'tcx>,
     unsize_def_id: DefId,
@@ -93,26 +125,7 @@ crate fn assemble_builtin_sized_impls<'tcx>(
     clauses: &mut Vec<Clause<'tcx>>
 ) {
     let mut push_builtin_impl = |ty: ty::Ty<'tcx>, nested: &[ty::Ty<'tcx>]| {
-        let clause = ProgramClause {
-            goal: ty::TraitPredicate {
-                trait_ref: ty::TraitRef {
-                    def_id: sized_def_id,
-                    substs: tcx.mk_substs_trait(ty, &[]),
-                },
-            }.lower(),
-            hypotheses: tcx.mk_goals(
-                nested.iter()
-                    .cloned()
-                    .map(|nested_ty| ty::TraitRef {
-                        def_id: sized_def_id,
-                        substs: tcx.mk_substs_trait(nested_ty, &[]),
-                    })
-                    .map(|trait_ref| ty::TraitPredicate { trait_ref })
-                    .map(|pred| GoalKind::DomainGoal(pred.lower()))
-                    .map(|goal_kind| tcx.mk_goal(goal_kind))
-            ),
-            category: ProgramClauseCategory::Other,
-        };
+        let clause = builtin_impl_clause(tcx, ty, nested, sized_def_id);
         // Bind innermost bound vars that may exist in `ty` and `nested`.
         clauses.push(Clause::ForAll(ty::Binder::bind(clause)));
     };
@@ -206,3 +219,99 @@ crate fn assemble_builtin_sized_impls<'tcx>(
         ty::GeneratorWitness(..) => bug!("unexpected type {:?}", ty),
     }
 }
+
+crate fn assemble_builtin_copy_clone_impls<'tcx>(
+    tcx: ty::TyCtxt<'_, '_, 'tcx>,
+    trait_def_id: DefId,
+    ty: ty::Ty<'tcx>,
+    clauses: &mut Vec<Clause<'tcx>>
+) {
+    let mut push_builtin_impl = |ty: ty::Ty<'tcx>, nested: &[ty::Ty<'tcx>]| {
+        let clause = builtin_impl_clause(tcx, ty, nested, trait_def_id);
+        // Bind innermost bound vars that may exist in `ty` and `nested`.
+        clauses.push(Clause::ForAll(ty::Binder::bind(clause)));
+    };
+
+    match &ty.sty {
+        // Implementations provided in libcore.
+        ty::Bool |
+        ty::Char |
+        ty::Int(..) |
+        ty::Uint(..) |
+        ty::Float(..) |
+        ty::RawPtr(..) |
+        ty::Never |
+        ty::Ref(_, _, hir::MutImmutable) => (),
+
+        // Non parametric primitive type.
+        ty::Error => push_builtin_impl(ty, &[]),
+
+        // These implement `Copy`/`Clone` if their element types do.
+        &ty::Array(_, length) => {
+            let element_ty = generic_types::bound(tcx, 0);
+            push_builtin_impl(tcx.mk_ty(ty::Array(element_ty, length)), &[element_ty]);
+        }
+        &ty::Tuple(type_list) => {
+            let type_list = generic_types::type_list(tcx, type_list.len());
+            push_builtin_impl(tcx.mk_ty(ty::Tuple(type_list)), &**type_list);
+        }
+        &ty::Closure(def_id, ..) => {
+            let closure_ty = generic_types::closure(tcx, def_id);
+            let upvar_tys: Vec<_> = match &closure_ty.sty {
+                ty::Closure(_, substs) => substs.upvar_tys(def_id, tcx).collect(),
+                _ => bug!(),
+            };
+            push_builtin_impl(closure_ty, &upvar_tys);
+        }
+
+        // These ones are always `Clone`.
+        ty::FnPtr(fn_ptr) => {
+            let fn_ptr = fn_ptr.skip_binder();
+            let fn_ptr = generic_types::fn_ptr(
+                tcx,
+                fn_ptr.inputs_and_output.len(),
+                fn_ptr.c_variadic,
+                fn_ptr.unsafety,
+                fn_ptr.abi
+            );
+            push_builtin_impl(fn_ptr, &[]);
+        }
+        &ty::FnDef(def_id, ..) => {
+            push_builtin_impl(generic_types::fn_def(tcx, def_id), &[]);
+        }
+
+        // These depend on whatever user-defined impls might exist.
+        ty::Adt(_, _) => (),
+
+        // int vars and float vars are always `Copy`.
+        // Other vars will trigger an ambiguity.
+        ty::Infer(..) => {
+            push_builtin_impl(tcx.types.i32, &[]);
+            push_builtin_impl(tcx.types.u32, &[]);
+            push_builtin_impl(tcx.types.f32, &[]);
+            push_builtin_impl(tcx.types.f64, &[]);
+        }
+
+        ty::Projection(_projection_ty) => {
+            // FIXME: add builtin impls from the associated type values found in
+            // trait impls of `projection_ty.trait_ref(tcx)`.
+        }
+
+        // The `Copy`/`Clone` bound can only come from the environment.
+        ty::Param(..) |
+        ty::Placeholder(..) |
+        ty::UnnormalizedProjection(..) |
+        ty::Opaque(..) => (),
+
+        // Definitely not `Copy`/`Clone`.
+        ty::Dynamic(..) |
+        ty::Foreign(..) |
+        ty::Generator(..) |
+        ty::Str |
+        ty::Slice(..) |
+        ty::Ref(_, _, hir::MutMutable) => (),
+
+        ty::Bound(..) |
+        ty::GeneratorWitness(..) => bug!("unexpected type {:?}", ty),
+    }
+}
diff --git a/src/librustc_traits/chalk_context/program_clauses/mod.rs b/src/librustc_traits/chalk_context/program_clauses/mod.rs
index 80fbd97c587..7feb63bb100 100644
--- a/src/librustc_traits/chalk_context/program_clauses/mod.rs
+++ b/src/librustc_traits/chalk_context/program_clauses/mod.rs
@@ -96,8 +96,27 @@ impl ChalkInferenceContext<'cx, 'gcx, 'tcx> {
                     );
                 }
 
+                if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().copy_trait() {
+                    assemble_builtin_copy_clone_impls(
+                        self.infcx.tcx,
+                        trait_predicate.def_id(),
+                        trait_predicate.self_ty(),
+                        &mut clauses
+                    );
+                }
+
+                if Some(trait_predicate.def_id()) == self.infcx.tcx.lang_items().clone_trait() {
+                    // For all builtin impls, the conditions for `Copy` and
+                    // `Clone` are the same.
+                    assemble_builtin_copy_clone_impls(
+                        self.infcx.tcx,
+                        trait_predicate.def_id(),
+                        trait_predicate.self_ty(),
+                        &mut clauses
+                    );
+                }
+
                 // FIXME: we need to add special rules for other builtin impls:
-                // * `Copy` / `Clone`
                 // * `Generator`
                 // * `FnOnce` / `FnMut` / `Fn`
                 // * trait objects
diff --git a/src/test/run-pass/chalkify/builtin-copy-clone.rs b/src/test/run-pass/chalkify/builtin-copy-clone.rs
new file mode 100644
index 00000000000..4f69714bc74
--- /dev/null
+++ b/src/test/run-pass/chalkify/builtin-copy-clone.rs
@@ -0,0 +1,43 @@
+// compile-flags: -Z chalk
+
+// Test that `Clone` is correctly implemented for builtin types.
+
+#[derive(Copy, Clone)]
+struct S(i32);
+
+fn test_clone<T: Clone>(arg: T) {
+    let _ = arg.clone();
+}
+
+fn test_copy<T: Copy>(arg: T) {
+    let _ = arg;
+    let _ = arg;
+}
+
+fn test_copy_clone<T: Copy + Clone>(arg: T) {
+    test_copy(arg);
+    test_clone(arg);
+}
+
+fn foo() { }
+
+fn main() {
+    test_copy_clone(foo);
+    let f: fn() = foo;
+    test_copy_clone(f);
+    // FIXME: add closures when they're considered WF
+    test_copy_clone([1; 56]);
+    test_copy_clone((1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1));
+    test_copy_clone((1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, true, 'a', 1.1));
+    test_copy_clone(());
+    test_copy_clone(((1, 1), (1, 1, 1), (1.1, 1, 1, 'a'), ()));
+
+    let a = (
+        (S(1), S(0)),
+        (
+            (S(0), S(0), S(1)),
+            S(0)
+        )
+    );
+    test_copy_clone(a);
+}