KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > tc > util > DeepCloner


1 /**
2  * All content copyright (c) 2003-2006 Terracotta, Inc., except as may otherwise be noted in a separate copyright notice. All rights reserved.
3  */

4 package com.tc.util;
5
6 import com.tc.exception.TCRuntimeException;
7
8 import java.lang.reflect.Array JavaDoc;
9 import java.lang.reflect.InvocationTargetException JavaDoc;
10 import java.lang.reflect.Method JavaDoc;
11 import java.util.Collection JavaDoc;
12 import java.util.Date JavaDoc;
13 import java.util.IdentityHashMap JavaDoc;
14 import java.util.Iterator JavaDoc;
15 import java.util.Map JavaDoc;
16
17 /**
18  * Allows for deep cloning of objects: to deep clone an object, call {@link #deepClone(Object)}. This object must
19  * either be one of the 'built-in' types this class knows about (like a {@link Cloneable}{@link Collection}or
20  * {@link Map}, an array, or certain value types, like the object wrappers for primitives, {@link String}s,
21  * {@link Date}s, and so on), or it must implement the {@link DeepCloneable}interface itself.
22  * </p>
23  * <p>
24  * <strong>FROM WITHIN A {@link com.tc.util.DeepCloneable#deepClone(DeepCloner)}METHOD </strong>, you must <strong>NOT
25  * </strong> use the {@link #deepClone(Object)}method. The reason for this is a little subtle. Consider a set of
26  * objects A, B, and C, where A and B both hold references to C. A 'naive' deep-cloning implementation will go to A and
27  * deep-clone it, which will make a copy of A that points to a new copy of C; it will then deep-clone B, which will
28  * point to a new, <em>separate</em> copy of C. This is bad, and will break your system in strange and wondrous ways.
29  * </p>
30  * <p>
31  * The solution to this is embedded in this class: a {@link DeepCloner}uses an {@link IdentityHashMap}that maps
32  * existing objects to their new clones. When cloning an object in {@link #subClone(Object)}, if we've already created
33  * a clone for that object, we simply return the existing clone, rather than creating a new one. Thus, in the situation
34  * above, when B goes to deep-clone C, the call to {@link DeepCloner#subClone(OBject)}will look up the original C in
35  * its map, find that it already has a clone, and return that; thus the clones of A and B will get hooked up to a single
36  * clone of C, rather than two different copies.
37  * </p>
38  * <p>
39  * Because of this, it is <em>critical</em> that, within a {@link DeepCloneable}'s
40  * {@link DeepCloneable#deepClone(DeepCloner)}method, you clone sub-objects by calling {@link #subClone(Object)}on the
41  * passed-in {@link DeepCloner}, rather than calling {@link #deepClone(Object)}yourself &mdash; otherwise, yes, your
42  * deep clone will break in strange and wondrous ways.
43  * </p>
44  * <p>
45  * (Note that we can and do prevent external clients &mdash; <em>i.e.</em>, code that isn't within a
46  * {@link DeepCloneable#deepClone(DeepCloner)}method &mdash; from calling {@link #subClone}directly, because that's an
47  * instance method, and the constructor of this class is private. Thus, the only way to do a deep clone &mdash; if
48  * you're not already in one &mdash; is to call {@link #deepClone(Object}directly.
49  * </p>
50  * <p>
51  * Finally, a note: object graphs that have a complete cycle of {@link DeepCloneable}objects that aren't value types (
52  * <em>i.e.</em>, which don't just <code>return this</code> in their {@link DeepCloneable}methods) cause problems
53  * if you don't additionally add a call to {@link #setClone(Object, Object)}in their methods. See the documentation for
54  * {@link #setClone(Object, Object)}for details.
55  */

56 public class DeepCloner {
57
58   /**
59    * The list of immutable 'value types' we know about. These are types for which we can simply return the original,
60    * rather than making a copy, because they're immutable and cannot possibly have an outbound reference to any other
61    * object that itself is not a value type. (Note that we consider objects of any subtype of these types to also be a
62    * value type.)
63    * </p>
64    * <p>
65    * (In other words, the entire transitive closure under object reference of any object of any of these types, or a
66    * subtype of any of these types, is immutable.)
67    */

68   private static final Class JavaDoc[] IMMUTABLE_VALUE_TYPES = new Class JavaDoc[] { Boolean JavaDoc.class, Character JavaDoc.class, Byte JavaDoc.class,
69       Short JavaDoc.class, Integer JavaDoc.class, Long JavaDoc.class, Float JavaDoc.class, Double JavaDoc.class, String JavaDoc.class, Date JavaDoc.class };
70
71   private static final Object JavaDoc DUMMY_VALUE = new Object JavaDoc();
72
73   private final Map JavaDoc clones;
74   private final Map JavaDoc pendingClones;
75
76   private DeepCloner() {
77     this.clones = new IdentityHashMap JavaDoc();
78     this.pendingClones = new IdentityHashMap JavaDoc();
79   }
80
81   /**
82    * Deep-clones an object: that is, returns an object <code>out</code> such that <code>source != out</code>,
83    * <code>out.equals(source)</code> (assuming <code>source</code>'s{@link Object#equals(Object}method works
84    * correctly and the {@link DeepCloneable#deepClone(DeepCloner)}method is implemented correctly on
85    * <code>source</code> and all referred-to classes), and &mdash; again, assuming <code>source</code>'s
86    * {@link DeepCloneable#deepClone(DeepCloner)}method is implemented correctly &mdash; <code>source</code> and
87    * <code>out</code> share no structure other than sub-trees that consist of entirely immutable objects.
88    * </p>
89    * <p>
90    * This method <strong>MUST NOT BE CALLED </strong> from within an object's
91    * {@link DeepCloneable#deepClone(DeepCloner)}method; see the class comments for why. You must use
92    * {@link #subClone(Object}instead.
93    *
94    * @param source The object to clone
95    * @return The deep clone
96    * @throws UnsupportedOperationException if <code>source</code> does not implement {@link DeepCloneable}and is not
97    * one of the object types that {@link DeepCloner}knows how to clone itself &mdash; currently,
98    * {@link Cloneable}{@link Collection}s,{@link Map}s, and arrays (of objects or primitives).
99    */

100   public static Object JavaDoc deepClone(Object JavaDoc source) {
101     if (source == null) return null;
102     return new DeepCloner().subClone(source);
103   }
104
105   /**
106    * Deep-clones an object. This method works exactly the same as {@link #deepClone(Object)}, except that it's smart
107    * enough to handle object graphs with multiple references to the same object. (That is, in such cases, the object
108    * that's referred to multiple times gets deep-cloned exactly once, and all references point to the same object.) See
109    * the class comment for more details.
110    * </p>
111    * <p>
112    * (This method cannot be called from anywhere else, because there's no way to create an instance of
113    * {@link DeepCloner}to call it on other than via {@link #deepClone(Object}).
114    *
115    * @param source The object to clone
116    * @return The deep clone; this will always be a different object from <code>source</code>, but may not be a
117    * brand-new object (<em>i.e.</em>, created by this method), for the reasons given in the class comment.
118    * @throws UnsupportedOperationException if <code>source</code> does not implement {@link DeepCloneable}and is not
119    * one of the object types that {@link DeepCloner}knows how to clone itself &mdash; currently,
120    * {@link Cloneable}{@link Collection}s,{@link Map}s, and arrays (of objects or primitives).
121    */

122   public Object JavaDoc subClone(Object JavaDoc source) {
123     if (source == null) return null;
124
125     Object JavaDoc out = this.clones.get(source);
126
127     if (out == null) {
128       Assert
129           .eval(
130                 "You're trying to clone an object that's currently being cloned -- in other words, someone tried "
131                                 + "to clone some object A, and, somewhere in the set of calls that generated, some other object went back "
132                                 + "and tried to clone A again. (Any kind of cycle in an object graph will typically generate this problem.) "
133                                 + "To fix this, you need to break the chain: call the DeepCloner.setClone(Object, Object) method somewhere "
134                                 + "*after* the original object A is created, but *before* the call to some other object's deepClone() method "
135                                 + "that leads back to A. (This is often in the 'cloning constructor' of A.) See the JavaDoc for "
136                                 + "DeepCloner.subClone() for details.", !this.pendingClones.containsKey(source));
137       this.pendingClones.put(source, DUMMY_VALUE);
138
139       out = doDeepClone(source);
140       this.clones.put(source, out);
141
142       this.pendingClones.remove(source);
143     }
144
145     return out;
146   }
147
148   /**
149    * This method is used to break circular reference graphs. For example, if you have two {@link DeepCloneable}objects,
150    * <code>A</code> and <code>B</code>, each of which contain a reference to each other, here's what will happen
151    * when someone calls {@link #deepClone(Object)}on <code>A</code>:
152    * <ol>
153    * <li>{@link #deepClone(Object)}creates a new {@link DeepCloner}, and calls {@link #subClone(Object)}on it,
154    * passing it <code>A</code>.</li>
155    * <li>{@link #subClone(Object)}looks for <code>A</code> in its map, doesn't find it, and so calls
156    * {@link DeepCloneable#deepClone(DeepCloner)}on <code>A</code>.</li>
157    * <li><code>A</code>'s{@link DeepCloneable#deepClone(Object)}method typically just does
158    * <code>return new A(this, deepCloner)</code>.</li>
159    * <li>This constructor on <code>A</code> then typically says
160    * <code>this.b = deepCloner.subClone(originalA.b)</code>.</li>
161    * <li>{#link #subClone(Object)} looks for <code>B</code> in its map, doesn't find it, and so calls
162    * {@link DeepCloneable#deepClone(DeepCloner)}on <code>B</code>.</li>
163    * <li><code>B</code>'s{@link DeepCloneable#deepClone(Object)}method typically just does
164    * <code>return new B(this, deepCloner)</code>.</li>
165    * <li>This constructor on <code>B</code> then typically says
166    * <code>this.a = deepCloner.subClone(originalB.a)</code>.</li>
167    * <li>We return to step 2.</li>
168    * <li>Eventually, get a {@link StackOverflowError}. Baboom.</li>
169    * </ol>
170    * Obviously, this is a problem. Further, it will occur in any object graph that has a full cycle composed solely of
171    * {@link DeepCloneable}objects that aren't value types (<em>i.e.</em>, those that don't just return
172    * <code>this</code> from their {@link DeepCloneable#deepClone(DeepCloner)}methods).
173    * </p>
174    * <p>
175    * To avoid this, we use this method. As an example, the proper use above is to add a call to this method in both A's
176    * 'deep cloning' constructor, and B's 'deep cloning' constructor, <em>before</em> the call to
177    * {@link #subClone(Object)}in each of them that clones the other object. For example, A's 'deep cloning' constructor
178    * might look like:
179    *
180    * <pre>
181    * private A(A source, DeepCloner cloner) {
182    * cloner.setClone(source, this);
183    * this.b = cloner.subClone(source.b);
184    * }
185    * </pre>
186    *
187    * This way, the {@link DeepCloner}will know what <code>A</code>'s correct clone is <em>before</em> <code>B</code>
188    * 's call to {@link #subClone(Object)}that clones it &mdash; so the {@link DeepCloner}will return the correct
189    * object, rather than getting a {@link StackOverflowError}.
190    * </p>
191    * <p>
192    * (Of note: there is actually a mechanism &mdash; the {@link #pendingClones}{@link Map}&mdash; that prevents the
193    * above scenario from actually playing out. Basically, we take note of which objects we're working on cloning just
194    * before we actually clone them, and if, before their clone completes, someone asks for them to be cloned, we throw a
195    * {@link TCAssertionError}describing the problem and what the solution is.)
196    */

197   public void setClone(Object JavaDoc original, Object JavaDoc clone) {
198     Assert.eval("You're trying to set the clone of an object that isn't currently being cloned. Perhaps you passed " +
199         "your arguments backwards?", this.pendingClones.containsKey(original));
200     this.clones.put(original, clone);
201   }
202
203   private Object JavaDoc doDeepClone(Object JavaDoc source) {
204     if (source instanceof DeepCloneable) {
205       Object JavaDoc out = ((DeepCloneable) source).deepClone(this);
206       Assert
207           .eval("You've returned an object from deepClone() that is of a DIFFERENT class than the source object; "
208                 + "this almost certainly means you forgot to override deepClone() on a subclass. You should fix this.",
209                 out.getClass().equals(source.getClass()));
210       return out;
211     } else if (isValueType(source.getClass())) {
212       return source;
213     } else if (source instanceof Collection JavaDoc && source instanceof Cloneable JavaDoc) {
214       return deepClone((Collection JavaDoc) source);
215     } else if (source instanceof Map JavaDoc && source instanceof Cloneable JavaDoc) {
216       return deepClone((Map JavaDoc) source);
217     } else if (source instanceof Object JavaDoc[]) {
218       return deepClone((Object JavaDoc[]) source);
219     } else if (source instanceof boolean[]) {
220       return deepClone((boolean[]) source);
221     } else if (source instanceof char[]) {
222       return deepClone((char[]) source);
223     } else if (source instanceof byte[]) {
224       return deepClone((byte[]) source);
225     } else if (source instanceof short[]) {
226       return deepClone((short[]) source);
227     } else if (source instanceof int[]) {
228       return deepClone((int[]) source);
229     } else if (source instanceof long[]) {
230       return deepClone((long[]) source);
231     } else if (source instanceof float[]) {
232       return deepClone((float[]) source);
233     } else if (source instanceof double[]) {
234       return deepClone((double[]) source);
235     } else {
236       throw new UnsupportedOperationException JavaDoc("You can't deep-clone " + source + ", a " + source.getClass().getName()
237                                               + "; it does not implement DeepCloneable, and is not one of the "
238                                               + "predefined 'known' classes.");
239     }
240   }
241
242   private boolean isValueType(Class JavaDoc c) {
243     for (int i = 0; i < IMMUTABLE_VALUE_TYPES.length; ++i) {
244       if (IMMUTABLE_VALUE_TYPES[i].isAssignableFrom(c)) return true;
245     }
246
247     return false;
248   }
249
250   private Object JavaDoc deepClone(Collection JavaDoc source) {
251     Collection JavaDoc out = (Collection JavaDoc) doShallowClone(source);
252     out.clear();
253
254     Iterator JavaDoc iter = source.iterator();
255     while (iter.hasNext()) {
256       out.add(subClone(iter.next()));
257     }
258
259     return out;
260   }
261
262   private Object JavaDoc deepClone(Map JavaDoc source) {
263     Map JavaDoc out = (Map JavaDoc) doShallowClone(source);
264     out.clear();
265
266     Iterator JavaDoc iter = source.entrySet().iterator();
267     while (iter.hasNext()) {
268       Map.Entry JavaDoc entry = (Map.Entry JavaDoc) iter.next();
269       out.put(subClone(entry.getKey()), subClone(entry.getValue()));
270     }
271
272     return out;
273   }
274
275   private Object JavaDoc deepClone(Object JavaDoc[] source) {
276     Object JavaDoc[] out = (Object JavaDoc[]) Array.newInstance(source.getClass().getComponentType(), source.length);
277     for (int i = 0; i < out.length; ++i) {
278       out[i] = subClone(source[i]);
279     }
280     return out;
281   }
282
283   private Object JavaDoc deepClone(boolean[] source) {
284     boolean[] out = new boolean[source.length];
285     System.arraycopy(source, 0, out, 0, source.length);
286     return out;
287   }
288
289   private Object JavaDoc deepClone(char[] source) {
290     char[] out = new char[source.length];
291     System.arraycopy(source, 0, out, 0, source.length);
292     return out;
293   }
294
295   private Object JavaDoc deepClone(short[] source) {
296     short[] out = new short[source.length];
297     System.arraycopy(source, 0, out, 0, source.length);
298     return out;
299   }
300
301   private Object JavaDoc deepClone(int[] source) {
302     int[] out = new int[source.length];
303     System.arraycopy(source, 0, out, 0, source.length);
304     return out;
305   }
306
307   private Object JavaDoc deepClone(byte[] source) {
308     byte[] out = new byte[source.length];
309     System.arraycopy(source, 0, out, 0, source.length);
310     return out;
311   }
312
313   private Object JavaDoc deepClone(long[] source) {
314     long[] out = new long[source.length];
315     System.arraycopy(source, 0, out, 0, source.length);
316     return out;
317   }
318
319   private Object JavaDoc deepClone(float[] source) {
320     float[] out = new float[source.length];
321     System.arraycopy(source, 0, out, 0, source.length);
322     return out;
323   }
324
325   private Object JavaDoc deepClone(double[] source) {
326     double[] out = new double[source.length];
327     System.arraycopy(source, 0, out, 0, source.length);
328     return out;
329   }
330
331   private Object JavaDoc doShallowClone(Object JavaDoc source) {
332     Class JavaDoc c = source.getClass();
333     Method JavaDoc cloneMethod;
334     try {
335       cloneMethod = c.getMethod("clone", null);
336       return cloneMethod.invoke(source, null);
337     } catch (SecurityException JavaDoc se) {
338       throw new TCRuntimeException("Unexpected exception when trying to clone a " + source.getClass(), se);
339     } catch (NoSuchMethodException JavaDoc nsme) {
340       throw new TCRuntimeException("Unexpected exception when trying to clone a " + source.getClass(), nsme);
341     } catch (IllegalArgumentException JavaDoc iae) {
342       throw new TCRuntimeException("Unexpected exception when trying to clone a " + source.getClass(), iae);
343     } catch (IllegalAccessException JavaDoc iae) {
344       throw new TCRuntimeException("Unexpected exception when trying to clone a " + source.getClass(), iae);
345     } catch (InvocationTargetException JavaDoc ite) {
346       throw new TCRuntimeException("Unexpected exception when trying to clone a " + source.getClass(), ite);
347     }
348   }
349
350 }
Popular Tags