--- solutions.m.orig	2011-11-29 16:07:47.000000000 -0500
+++ solutions.m	2011-11-29 16:21:49.000000000 -0500
@@ -786,7 +786,10 @@
   #define MR_PARTIAL_DEEP_COPY(SolutionsHeapPtr,                        \\
         OldVar, NewVal, TypeInfo_for_T)                                 \\
     do {                                                                \\
-        NewVal = OldVal;                                                \\
+        MR_save_transient_hp();                                         \\
+        NewVal = MR_deep_copy(OldVal, (MR_TypeInfo) TypeInfo_for_T,     \\
+            NULL, NULL);                                                \\
+        MR_restore_transient_hp();                                      \\
     } while (0)
 #else
   /*
@@ -803,7 +806,6 @@
         MR_restore_transient_hp();                                      \\
     } while (0)
 #endif
-
 ").
 
 :- pragma foreign_proc("C",
@@ -829,59 +831,62 @@
     partial_deep_copy(_SolutionsHeapPtr::in, OldVal::in, NewVal::out),
     [will_not_call_mercury, thread_safe],
 "
-    //
-    // For the IL back-end, we don't do heap reclamation on failure,
-    // so we don't need to worry about making deep copies here.
-    // Shallow copies will suffice.
-    //
-    NewVal = OldVal;
+    NewVal = builtin.deep_copy(OldVal);
 ").
 :- pragma foreign_proc("C#",
     partial_deep_copy(_SolutionsHeapPtr::in, OldVal::mdi, NewVal::muo),
     [will_not_call_mercury, thread_safe],
 "
-    NewVal = OldVal;
+    NewVal = builtin.deep_copy(OldVal);
 ").
 :- pragma foreign_proc("C#",
     partial_deep_copy(_SolutionsHeapPtr::in, OldVal::di, NewVal::uo),
     [will_not_call_mercury, thread_safe],
 "
-    NewVal = OldVal;
+    NewVal = builtin.deep_copy(OldVal);
 ").
 
 :- pragma foreign_proc("Java",
     partial_deep_copy(_SolutionsHeapPtr::in, OldVal::in, NewVal::out),
     [will_not_call_mercury, thread_safe],
 "
-    /*
-    ** For the Java back-end, as for the .NET implementation,
-    ** we don't do heap reclamation on failure,
-    ** so we don't need to worry about making deep copies here.
-    ** Shallow copies will suffice.
-    */
-    NewVal = OldVal;
+    try {
+        NewVal = builtin.deep_copy(OldVal);
+    } catch (java.lang.InstantiationException E) {
+        throw new RuntimeException(E);
+    } catch (java.lang.IllegalAccessException E) {
+        throw new RuntimeException(E);
+    }
 ").
 :- pragma foreign_proc("Java",
     partial_deep_copy(_SolutionsHeapPtr::in, OldVal::mdi, NewVal::muo),
     [will_not_call_mercury, thread_safe],
 "
-    NewVal = OldVal;
+    try {
+        NewVal = builtin.deep_copy(OldVal);
+    } catch (java.lang.InstantiationException E) {
+        throw new RuntimeException(E);
+    } catch (java.lang.IllegalAccessException E) {
+        throw new RuntimeException(E);
+    }
 ").
 :- pragma foreign_proc("Java",
     partial_deep_copy(_SolutionsHeapPtr::in, OldVal::di, NewVal::uo),
     [will_not_call_mercury, thread_safe],
 "
-    NewVal = OldVal;
+    try {
+        NewVal = builtin.deep_copy(OldVal);
+    } catch (java.lang.InstantiationException E) {
+        throw new RuntimeException(E);
+    } catch (java.lang.IllegalAccessException E) {
+        throw new RuntimeException(E);
+    }
 ").
 
 :- pragma foreign_proc("Erlang",
     partial_deep_copy(_SolutionsHeapPtr::in, OldVal::in, NewVal::out),
     [will_not_call_mercury, thread_safe],
 "
-    % For the Erlang back-end, as for the .NET implementation,
-    % we don't do heap reclamation on failure,
-    % so we don't need to worry about making deep copies here.
-    % Shallow copies will suffice.
     NewVal = OldVal
 ").
 :- pragma foreign_proc("Erlang",