001    /*--------------------------------------------------------------------------+
002    $Id: DeepCloneTestUtils.java 27815 2010-05-20 16:11:32Z hummelb $
003    |                                                                          |
004    | Copyright 2005-2010 Technische Universitaet Muenchen                     |
005    |                                                                          |
006    | Licensed under the Apache License, Version 2.0 (the "License");          |
007    | you may not use this file except in compliance with the License.         |
008    | You may obtain a copy of the License at                                  |
009    |                                                                          |
010    |    http://www.apache.org/licenses/LICENSE-2.0                            |
011    |                                                                          |
012    | Unless required by applicable law or agreed to in writing, software      |
013    | distributed under the License is distributed on an "AS IS" BASIS,        |
014    | WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
015    | See the License for the specific language governing permissions and      |
016    | limitations under the License.                                           |
017    +--------------------------------------------------------------------------*/
018    package edu.tum.cs.commons.test;
019    
020    import java.lang.reflect.InvocationTargetException;
021    import java.lang.reflect.Method;
022    import java.lang.reflect.ParameterizedType;
023    import java.lang.reflect.Type;
024    import java.util.ArrayList;
025    import java.util.Arrays;
026    import java.util.Collection;
027    import java.util.Collections;
028    import java.util.Comparator;
029    import java.util.IdentityHashMap;
030    import java.util.List;
031    
032    import edu.tum.cs.commons.assertion.CCSMAssert;
033    import edu.tum.cs.commons.collections.AllEqualComparator;
034    import edu.tum.cs.commons.collections.CollectionUtils;
035    import edu.tum.cs.commons.collections.IIdProvider;
036    import edu.tum.cs.commons.collections.IdComparator;
037    import edu.tum.cs.commons.collections.IdentityHashSet;
038    import edu.tum.cs.commons.reflect.MethodNameComparator;
039    import edu.tum.cs.commons.string.StringUtils;
040    
041    /**
042     * This class provides various utility methods used to test deep cloning
043     * implementations
044     * 
045     * 
046     * @author deissenb
047     * @author $Author: hummelb $
048     * @version $Rev: 27815 $
049     * @levd.rating GREEN Hash: ED526603069BA695A145272D022B02D1
050     */
051    public class DeepCloneTestUtils {
052    
053            /** Name of the deep clone method. */
054            private static final String DEEP_CLONE_METHOD_NAME = "deepClone";
055    
056            /** Name of the clone method. */
057            private static final String CLONE_METHOD_NAME = "clone";
058    
059            /**
060             * This method is used to test deep cloning implementations. Provided with
061             * two object, the original and the clone, it automatically traverses the
062             * networks attached to both objects and establishes a mapping between the
063             * objects of both networks.
064             * <p>
065             * To achieve this, the method uses reflection to determine the methods that
066             * define the object networks, typically examples are
067             * <code>getChildren()</code> or <code>getParent()</code>. To limit the
068             * selection of methods, a list of package prefixes may specified. Only
069             * methods that do return a type matched by one of the prefixes are taken
070             * into account. Additionally all methods that return an implementation of
071             * {@link Collection} are considered. However, we currently do not consider
072             * nested collections like <code>Set<Set<K></code>.
073             * <p>
074             * To establish the mapping between the networks a comparator is needed to
075             * order members of object in both networks in the same way. This comparator
076             * must not be capable of comparing all possible types but must support
077             * ordering possible member type combinations of the object network under
078             * investigation. Usually, the object already provide some means of
079             * identification via IDs or full qualified names. These can be used to
080             * implement the comparator.
081             * 
082             * @param orig
083             *            point of entry for the original network
084             * @param clone
085             *            point of entry for the clone network
086             * @param comparator
087             *            the comparator is needed to compare the two networks
088             * @param packagePrefixes
089             *            list of package prefixes to take into account
090             */
091            public static IdentityHashMap<Object, Object> buildCloneMap(Object orig,
092                            Object clone, Comparator<Object> comparator,
093                            String... packagePrefixes) {
094                    IdentityHashMap<Object, Object> map = new IdentityHashMap<Object, Object>();
095                    buildCloneMap(orig, clone, map, comparator, packagePrefixes);
096                    return map;
097            }
098    
099            /**
100             * This works analogous to
101             * {@link #getAllReferencedObjects(Object, String...)} but allows to limit
102             * the results to a certain type.
103             */
104            public static <T> IdentityHashSet<T> getAllReferencedObjects(Object root,
105                            Class<T> type, String... packagePrefixes) {
106                    IdentityHashSet<T> result = new IdentityHashSet<T>();
107                    for (Object object : getAllReferencedObjects(root, packagePrefixes)) {
108                            if (type.isAssignableFrom(object.getClass())) {
109                                    @SuppressWarnings("unchecked")
110                                    T object2 = (T) object;
111                                    result.add(object2);
112                            }
113                    }
114                    return result;
115            }
116    
117            /**
118             * Get all objects an object references. To to find the objects, this method
119             * uses reflection to determine the methods that define the object networks,
120             * typically examples are <code>getChildren()</code> or
121             * <code>getParent()</code>. To limit the selection of methods, a list of
122             * package prefixes must be specified. Only methods that do return a type
123             * matched by one of the prefixes are taken into account. Additionally all
124             * methods that return an implementation of {@link Collection} are
125             * considered.
126             * 
127             * @param root
128             *            root of the object network
129             * @param packagePrefixes
130             *            list of package prefixes to take into account
131             */
132            public static IdentityHashSet<Object> getAllReferencedObjects(Object root,
133                            String... packagePrefixes) {
134                    IdentityHashSet<Object> result = new IdentityHashSet<Object>();
135                    buildReferenceSet(root, result, packagePrefixes);
136                    return result;
137            }
138    
139            /**
140             * This method uses
141             * {@link #buildCloneMap(Object, Object, Comparator, String...)} to build a
142             * map between the original object network and clone network. Based on this
143             * map it performs the following checks:
144             * <ul>
145             * <li>Checks if objects are not same.</li>
146             * <li>Checks if objects are of same type.</li>
147             * <li>Checks if object and clone network are disjoint.</li>
148             * </ul>
149             * 
150             * @param orig
151             *            point of entry for the original network
152             * @param clone
153             *            point of entry for the clone network
154             * @param idProvider
155             *            an id provider that generates an id for all objects in the
156             *            networks. This is necessary to establish comparable orderings.
157             * @param packagePrefixes
158             *            list of package prefixes to take into account
159             * @return the map to allow further tests.
160             */
161            public static <I extends Comparable<I>> IdentityHashMap<Object, Object> testDeepCloning(
162                            Object orig, Object clone, IIdProvider<I, Object> idProvider,
163                            String... packagePrefixes) {
164    
165                    IdentityHashMap<Object, Object> map = buildCloneMap(orig, clone,
166                                    new IdComparator<I, Object>(idProvider), packagePrefixes);
167    
168                    for (Object origObject : map.keySet()) {
169                            Object cloneObject = map.get(origObject);
170    
171                            CCSMAssert.isTrue(orig.getClass().equals(clone.getClass()),
172                                            "Objects " + origObject + " and " + cloneObject
173                                                            + " have different types.");
174    
175                            // no need to check this for enums.
176                            if (origObject.getClass().isEnum()) {
177                                    continue;
178                            }
179    
180                            CCSMAssert.isFalse(origObject == cloneObject, "Objects "
181                                            + origObject + " and " + cloneObject + " are same.");
182    
183                            CCSMAssert.isFalse(map.values().contains(origObject),
184                                            "Clone network contains original object: " + origObject);
185                            CCSMAssert.isFalse(map.keySet().contains(cloneObject),
186                                            "Orig network contains clone object: " + origObject);
187    
188                    }
189    
190                    return map;
191            }
192    
193            /**
194             * Recursively build clone map. See
195             * {@link #buildCloneMap(Object, Object, Comparator, String...)} for
196             * details.
197             */
198            private static void buildCloneMap(Object orig, Object clone,
199                            IdentityHashMap<Object, Object> map, Comparator<Object> comparator,
200                            String... packagePrefixes) {
201    
202                    if (!orig.getClass().equals(clone.getClass())) {
203                            throw new RuntimeException("Objects " + orig + " and " + clone
204                                            + " are of different tpye [orig: "
205                                            + orig.getClass().getName() + "][clone:"
206                                            + orig.getClass().getName() + "]");
207                    }
208    
209                    map.put(orig, clone);
210    
211                    // get all objects referenced by the original
212                    ArrayList<Object> origRefObjects = getReferencedObjects(orig,
213                                    comparator, packagePrefixes);
214    
215                    // get all objects referenced by the clone
216                    ArrayList<Object> cloneRefObjects = getReferencedObjects(clone,
217                                    comparator, packagePrefixes);
218    
219                    if (origRefObjects.size() != cloneRefObjects.size()) {
220                            throw new RuntimeException("Objects " + orig + " and " + clone
221                                            + " have unequal numbers of referenced objects [orig: "
222                                            + origRefObjects + "][clone:" + cloneRefObjects + "]");
223                    }
224    
225                    // traverse recursively
226                    for (int i = 0; i < origRefObjects.size(); i++) {
227                            Object key = origRefObjects.get(i);
228                            Object value = cloneRefObjects.get(i);
229    
230                            // do not traverse objects already visited, but ensure that we have
231                            // an unambiguous mapping
232                            if (map.containsKey(key)) {
233                                    if (!(map.get(key) == value)) {
234                                            throw new RuntimeException("Object " + key
235                                                            + " appears to be cloned to " + map.get(key)
236                                                            + " and to " + value);
237                                    }
238                            } else if (key != null) {
239                                    buildCloneMap(key, value, map, comparator, packagePrefixes);
240                            }
241                    }
242            }
243    
244            /** Recursively build set of all referenced objects. */
245            private static void buildReferenceSet(Object object,
246                            IdentityHashSet<Object> set, String[] packagePrefixes) {
247    
248                    set.add(object);
249                    for (Object item : getReferencedObjects(object,
250                                    AllEqualComparator.OBJECT_INSTANCE, packagePrefixes)) {
251                            if (item != null && !set.contains(item)) {
252                                    buildReferenceSet(item, set, packagePrefixes);
253                            }
254                    }
255            }
256    
257            /**
258             * Get all objects referenced by an object through methods that do return
259             * arrays.
260             */
261            private static ArrayList<Object> getArrayObjects(Object object,
262                            Comparator<Object> comparator, String... packagePrefixes) {
263    
264                    ArrayList<Object> result = new ArrayList<Object>();
265    
266                    for (Method method : object.getClass().getMethods()) {
267                            if (method.getParameterTypes().length == 0
268                                            && hasArrayReturnType(method, packagePrefixes)) {
269                                    Object returnValue = invoke(object, method);
270                                    if (returnValue != null) {
271                                            Object[] array = (Object[]) returnValue;
272                                            List<Object> list = Arrays.asList(array);
273    
274                                            Collections.sort(list, comparator);
275                                            result.addAll(list);
276                                    }
277                            }
278                    }
279    
280                    return result;
281            }
282    
283            /**
284             * Get all objects referenced by an object through methods that do return
285             * collections.
286             */
287            private static ArrayList<Object> getCollectionObjects(Object object,
288                            Comparator<Object> comparator, String... packagePrefixes) {
289    
290                    ArrayList<Object> result = new ArrayList<Object>();
291    
292                    for (Method method : object.getClass().getMethods()) {
293                            if (method.getParameterTypes().length == 0
294                                            && hasCollectionReturnType(method, packagePrefixes)) {
295                                    Object returnValue = invoke(object, method);
296    
297                                    if (returnValue != null) {
298                                            Collection<?> collection = (Collection<?>) returnValue;
299                                            List<?> list = CollectionUtils.sort(collection, comparator);
300                                            result.addAll(list);
301                                    }
302                            }
303    
304                    }
305    
306                    return result;
307            }
308    
309            /**
310             * Get list of methods that (1) do not have parameters, (2) whose return
311             * type starts with one of the given prefixes and whose names is not
312             * <code>deepClone()</code>. The methods are ordered by name.
313             */
314            private static ArrayList<Method> getMethods(Object object,
315                            String[] packagePrefixes) {
316                    ArrayList<Method> methods = new ArrayList<Method>();
317                    for (Method method : object.getClass().getMethods()) {
318                            if (method.getName().equals(CLONE_METHOD_NAME)) {
319                                    continue;
320                            }
321                            if (method.getName().equals(DEEP_CLONE_METHOD_NAME)) {
322                                    continue;
323                            }
324                            if (method.getParameterTypes().length > 0) {
325                                    continue;
326                            }
327                            Class<?> returnType = method.getReturnType();
328                            if (StringUtils.startsWithOneOf(returnType.getName(),
329                                            packagePrefixes)) {
330                                    methods.add(method);
331                            }
332                    }
333    
334                    Collections.sort(methods, MethodNameComparator.INSTANCE);
335    
336                    return methods;
337            }
338    
339            /**
340             * Get all objects referenced by an object through methods that do
341             * <em>not</em> return collections.
342             */
343            private static ArrayList<Object> getNonCollectionObjects(Object object,
344                            String... packagePrefixes) {
345    
346                    ArrayList<Object> objects = new ArrayList<Object>();
347    
348                    for (Method method : getMethods(object, packagePrefixes)) {
349                            objects.add(invoke(object, method));
350                    }
351                    return objects;
352            }
353    
354            /**
355             * Get all objects an object references in an order defined by the
356             * comparator.
357             */
358            private static ArrayList<Object> getReferencedObjects(Object object,
359                            Comparator<Object> comparator, String... packagePrefixes) {
360    
361                    ArrayList<Object> result = new ArrayList<Object>();
362    
363                    ArrayList<Object> nonCollectionObjects = getNonCollectionObjects(
364                                    object, packagePrefixes);
365                    result.addAll(nonCollectionObjects);
366    
367                    ArrayList<Object> collectionObjects = getCollectionObjects(object,
368                                    comparator, packagePrefixes);
369                    result.addAll(collectionObjects);
370    
371                    ArrayList<Object> arrayObjects = getArrayObjects(object, comparator,
372                                    packagePrefixes);
373                    result.addAll(arrayObjects);
374    
375                    return result;
376            }
377    
378            /**
379             * Checks if a method returns an array with type that starts with one of the
380             * provided prefixes.
381             */
382            private static boolean hasArrayReturnType(Method method,
383                            String... packagePrefixes) {
384                    Class<?> returnType = method.getReturnType();
385                    if (!returnType.isArray()) {
386                            return false;
387                    }
388                    Class<?> actualType = returnType.getComponentType();
389                    return StringUtils.startsWithOneOf(actualType.getName(),
390                                    packagePrefixes);
391            }
392    
393            /**
394             * Checks if a method returns an collection whose generic type that starts
395             * with one of the provided prefixes.
396             */
397            private static boolean hasCollectionReturnType(Method method,
398                            String... packagePrefixes) {
399                    Class<?> returnType = method.getReturnType();
400    
401                    if (!Collection.class.isAssignableFrom(returnType)) {
402                            return false;
403                    }
404    
405                    Type genericReturnType = method.getGenericReturnType();
406                    // Raw type
407                    if (returnType == genericReturnType) {
408                            return false;
409                    }
410    
411                    ParameterizedType type = (ParameterizedType) method
412                                    .getGenericReturnType();
413    
414                    // Collections have only one type parameter
415                    Type typeArg = type.getActualTypeArguments()[0];
416    
417                    // potentially this can be another parameterized type, e.g. for
418                    // Set<Set<K>> or a wildcard type. Handling these is very tricky and is
419                    // currently not supported. Hence, we silently ignore these.
420                    if (!(typeArg instanceof Class<?>)) {
421                            return false;
422                    }
423    
424                    Class<?> actualType = (Class<?>) typeArg;
425    
426                    return StringUtils.startsWithOneOf(actualType.getName(),
427                                    packagePrefixes);
428            }
429    
430            /**
431             * This simpy calls {@link Method#invoke(Object, Object...)}. If the called
432             * method throws an exception, this returns <code>null</code>. A possible
433             * {@link IllegalAccessException} is converted to a {@link RuntimeException}
434             * .
435             */
436            private static Object invoke(Object object, Method method) {
437                    try {
438                            return method.invoke(object);
439                    } catch (RuntimeException e) {
440                            return null;
441                    } catch (IllegalAccessException e) {
442                            throw new RuntimeException(e);
443                    } catch (InvocationTargetException e) {
444                            return null;
445                    }
446            }
447    }