1 /*
2  * Copyright (C) 2009 The Android Open Source Project
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *      http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 
17 package signature.compare;
18 
19 import signature.compare.model.IAnnotationDelta;
20 import signature.compare.model.IAnnotationElementDelta;
21 import signature.compare.model.IAnnotationFieldDelta;
22 import signature.compare.model.IApiDelta;
23 import signature.compare.model.IClassDefinitionDelta;
24 import signature.compare.model.IConstructorDelta;
25 import signature.compare.model.IDelta;
26 import signature.compare.model.IEnumConstantDelta;
27 import signature.compare.model.IFieldDelta;
28 import signature.compare.model.IGenericDeclarationDelta;
29 import signature.compare.model.IMethodDelta;
30 import signature.compare.model.IModifierDelta;
31 import signature.compare.model.IPackageDelta;
32 import signature.compare.model.IParameterDelta;
33 import signature.compare.model.IParameterizedTypeDelta;
34 import signature.compare.model.IPrimitiveTypeDelta;
35 import signature.compare.model.ITypeReferenceDelta;
36 import signature.compare.model.ITypeVariableDefinitionDelta;
37 import signature.compare.model.IUpperBoundsDelta;
38 import signature.compare.model.IValueDelta;
39 import signature.compare.model.IWildcardTypeDelta;
40 import signature.compare.model.impl.SigAnnotationDelta;
41 import signature.compare.model.impl.SigAnnotationElementDelta;
42 import signature.compare.model.impl.SigAnnotationFieldDelta;
43 import signature.compare.model.impl.SigApiDelta;
44 import signature.compare.model.impl.SigArrayTypeDelta;
45 import signature.compare.model.impl.SigClassDefinitionDelta;
46 import signature.compare.model.impl.SigClassReferenceDelta;
47 import signature.compare.model.impl.SigConstructorDelta;
48 import signature.compare.model.impl.SigEnumConstantDelta;
49 import signature.compare.model.impl.SigFieldDelta;
50 import signature.compare.model.impl.SigGenericDeclarationDelta;
51 import signature.compare.model.impl.SigMethodDelta;
52 import signature.compare.model.impl.SigModifierDelta;
53 import signature.compare.model.impl.SigPackageDelta;
54 import signature.compare.model.impl.SigParameterDelta;
55 import signature.compare.model.impl.SigParameterizedTypeDelta;
56 import signature.compare.model.impl.SigPrimitiveTypeDelta;
57 import signature.compare.model.impl.SigTypeDelta;
58 import signature.compare.model.impl.SigTypeVariableDefinitionDelta;
59 import signature.compare.model.impl.SigTypeVariableReferenceDelta;
60 import signature.compare.model.impl.SigUpperBoundsDelta;
61 import signature.compare.model.impl.SigValueDelta;
62 import signature.compare.model.impl.SigWildcardTypeDelta;
63 import signature.compare.model.subst.ClassProjection;
64 import signature.compare.model.subst.ViewpointAdapter;
65 import signature.model.IAnnotation;
66 import signature.model.IAnnotationElement;
67 import signature.model.IAnnotationField;
68 import signature.model.IApi;
69 import signature.model.IArrayType;
70 import signature.model.IClassDefinition;
71 import signature.model.IClassReference;
72 import signature.model.IConstructor;
73 import signature.model.IEnumConstant;
74 import signature.model.IExecutableMember;
75 import signature.model.IField;
76 import signature.model.IGenericDeclaration;
77 import signature.model.IMethod;
78 import signature.model.IPackage;
79 import signature.model.IParameter;
80 import signature.model.IParameterizedType;
81 import signature.model.IPrimitiveType;
82 import signature.model.ITypeReference;
83 import signature.model.ITypeVariableDefinition;
84 import signature.model.ITypeVariableReference;
85 import signature.model.IWildcardType;
86 import signature.model.Kind;
87 import signature.model.Modifier;
88 import signature.model.impl.SigAnnotationElement;
89 import signature.model.impl.SigArrayType;
90 
91 import java.util.Arrays;
92 import java.util.HashMap;
93 import java.util.HashSet;
94 import java.util.Iterator;
95 import java.util.LinkedList;
96 import java.util.List;
97 import java.util.Set;
98 
99 /**
100  * {@code ApiComparator} takes two signature models as input and creates a delta
101  * model describing the differences between those.
102  */
103 public class ApiComparator implements IApiComparator {
104 
compare(IApi from, IApi to)105     public IApiDelta compare(IApi from, IApi to) {
106         assert from.getVisibility() == to.getVisibility();
107 
108         Set<IPackage> fromPackages = from.getPackages();
109         Set<IPackage> toPackages = to.getPackages();
110 
111         Set<IPackageDelta> packageDeltas = compareSets(fromPackages,
112                 toPackages, new SigComparator<IPackage, IPackageDelta>() {
113                     public IPackageDelta createChangedDelta(IPackage from,
114                             IPackage to) {
115                         return comparePackage(from, to);
116                     }
117 
118                     public IPackageDelta createAddRemoveDelta(IPackage from,
119                             IPackage to) {
120                         return new SigPackageDelta(from, to);
121                     }
122 
123                     public boolean considerEqualElement(IPackage from,
124                             IPackage to) {
125                         return from.getName().equals(to.getName());
126                     }
127                 });
128 
129         SigApiDelta delta = null;
130         if (packageDeltas != null) {
131             delta = new SigApiDelta(from, to);
132             delta.setPackageDeltas(packageDeltas);
133         }
134         return delta;
135     }
136 
comparePackage(IPackage from, IPackage to)137     private IPackageDelta comparePackage(IPackage from, IPackage to) {
138         assert from.getName().equals(to.getName());
139 
140         Set<IClassDefinition> fromClasses = from.getClasses();
141         Set<IClassDefinition> toClasses = to.getClasses();
142 
143         Set<IClassDefinitionDelta> classDeltas = compareSets(fromClasses,
144                 toClasses,
145                 new SigComparator<IClassDefinition, IClassDefinitionDelta>() {
146                     public boolean considerEqualElement(IClassDefinition from,
147                             IClassDefinition to) {
148                         return sameClassDefinition(from, to);
149                     }
150 
151                     public IClassDefinitionDelta createChangedDelta(
152                             IClassDefinition from, IClassDefinition to) {
153                         return compareClass(from, to);
154                     }
155 
156                     public IClassDefinitionDelta createAddRemoveDelta(
157                             IClassDefinition from, IClassDefinition to) {
158                         return new SigClassDefinitionDelta(from, to);
159                     }
160                 });
161 
162         SigPackageDelta delta = null;
163         if (classDeltas != null) {
164             delta = new SigPackageDelta(from, to);
165             delta.setClassDeltas(classDeltas);
166         }
167 
168         // Annotations
169         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
170                 .getAnnotations(), to.getAnnotations());
171         if (annotationDeltas != null) {
172             if (delta != null) {
173                 delta = new SigPackageDelta(from, to);
174             }
175             delta.setAnnotationDeltas(annotationDeltas);
176         }
177         return delta;
178     }
179 
compareClass(IClassDefinition from, IClassDefinition to)180     private IClassDefinitionDelta compareClass(IClassDefinition from,
181             IClassDefinition to) {
182         assert from.getKind() == to.getKind();
183         assert from.getName().equals(to.getName());
184         assert from.getPackageName().equals(to.getPackageName());
185 
186         SigClassDefinitionDelta classDelta = null;
187 
188         // modifiers
189         Set<IModifierDelta> modifierDeltas = compareModifiers(from
190                 .getModifiers(), to.getModifiers());
191         if (modifierDeltas != null) {
192             if (classDelta == null) {
193                 classDelta = new SigClassDefinitionDelta(from, to);
194             }
195             classDelta.setModifierDeltas(modifierDeltas);
196         }
197 
198         // super class
199         ITypeReferenceDelta<?> superTypeDelta = compareType(from
200                 .getSuperClass(), to.getSuperClass(), false);
201         if (superTypeDelta != null) {
202             if (classDelta == null) {
203                 classDelta = new SigClassDefinitionDelta(from, to);
204             }
205             classDelta.setSuperClassDelta(superTypeDelta);
206         }
207 
208         // interfaces
209         Set<ITypeReferenceDelta<?>> interfaceDeltas = compareInterfaces(from,
210                 to);
211         if (interfaceDeltas != null) {
212             if (classDelta == null) {
213                 classDelta = new SigClassDefinitionDelta(from, to);
214             }
215             classDelta.setInterfaceDeltas(interfaceDeltas);
216         }
217 
218         // type variables
219         Set<ITypeVariableDefinitionDelta> typeVariableDeltas =
220                 compareTypeVariableSequence(from.getTypeParameters(),
221                         to.getTypeParameters());
222         if (typeVariableDeltas != null) {
223             if (classDelta == null) {
224                 classDelta = new SigClassDefinitionDelta(from, to);
225             }
226             classDelta.setTypeVariableDeltas(typeVariableDeltas);
227         }
228 
229         // constructors
230         Set<IConstructorDelta> constructorDeltas = compareConstructors(from
231                 .getConstructors(), to.getConstructors());
232         if (constructorDeltas != null) {
233             if (classDelta == null) {
234                 classDelta = new SigClassDefinitionDelta(from, to);
235             }
236             classDelta.setConstructorDeltas(constructorDeltas);
237         }
238 
239         // methods
240         Set<IMethodDelta> methodDeltas = compareMethods(from, to);
241         if (methodDeltas != null) {
242             if (classDelta == null) {
243                 classDelta = new SigClassDefinitionDelta(from, to);
244             }
245             classDelta.setMethodDeltas(methodDeltas);
246         }
247 
248         // fields
249         Set<IFieldDelta> fieldDeltas = compareFields(from.getFields(), to
250                 .getFields());
251         if (fieldDeltas != null) {
252             if (classDelta == null) {
253                 classDelta = new SigClassDefinitionDelta(from, to);
254             }
255             classDelta.setFieldDeltas(fieldDeltas);
256         }
257 
258         // enum constants
259         if (from.getKind() == Kind.ENUM) {
260             Set<IEnumConstantDelta> enumDeltas = compareEnumConstants(from
261                     .getEnumConstants(), to.getEnumConstants());
262             if (enumDeltas != null) {
263                 if (classDelta == null) {
264                     classDelta = new SigClassDefinitionDelta(from, to);
265                 }
266                 classDelta.setEnumConstantDeltas(enumDeltas);
267             }
268         } else if (from.getKind() == Kind.ANNOTATION) {
269             Set<IAnnotationFieldDelta> annotationFieldDeltas =
270                     compareAnnotationFields(from.getAnnotationFields(),
271                             to.getAnnotationFields());
272             if (annotationFieldDeltas != null) {
273                 if (classDelta == null) {
274                     classDelta = new SigClassDefinitionDelta(from, to);
275                 }
276                 classDelta.setAnnotationFieldDeltas(annotationFieldDeltas);
277             }
278         }
279 
280         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
281                 .getAnnotations(), to.getAnnotations());
282         if (annotationDeltas != null) {
283             if (classDelta == null) {
284                 classDelta = new SigClassDefinitionDelta(from, to);
285             }
286             classDelta.setAnnotationDeltas(annotationDeltas);
287         }
288         return classDelta;
289     }
290 
compareInterfaces( IClassDefinition from, IClassDefinition to)291     private Set<ITypeReferenceDelta<?>> compareInterfaces(
292             IClassDefinition from, IClassDefinition to) {
293         Set<ITypeReference> fromClosure = getInterfaceClosure(from);
294         Set<ITypeReference> toClosure = getInterfaceClosure(to);
295 
296         Set<ITypeReference> fromInterfaces = from.getInterfaces();
297         Set<ITypeReference> toInterfaces = to.getInterfaces();
298 
299         Set<ITypeReferenceDelta<?>> deltas =
300                 new HashSet<ITypeReferenceDelta<?>>();
301 
302         // check whether all from interfaces are directly or indirectly
303         // implemented by the to method
304         for (ITypeReference type : fromInterfaces) {
305             if (!containsType(type, toInterfaces)) {
306                 if (!(containsType(type, toClosure) /*
307                                                      * && !containsType(type,
308                                                      * toInterfaces)
309                                                      */)) {
310                     deltas.add(new SigTypeDelta<ITypeReference>(type, null));
311                 }
312             }
313         }
314 
315         // check whether all interfaces to are directly or indirectly
316         // implemented by the from method
317         for (ITypeReference type : toInterfaces) {
318             if (!containsType(type, fromInterfaces)) {
319                 if (!(containsType(type, fromClosure) /*
320                                                        * && !containsType(type,
321                                                        * fromInterfaces)
322                                                        */)) {
323                     deltas.add(new SigTypeDelta<ITypeReference>(null, type));
324                 }
325             }
326         }
327         return deltas.isEmpty() ? null : deltas;
328     }
329 
330 
containsType(ITypeReference type, Set<ITypeReference> setOfTypes)331     private boolean containsType(ITypeReference type,
332             Set<ITypeReference> setOfTypes) {
333         for (ITypeReference other : setOfTypes) {
334             if (compareType(type, other, false) == null) {
335                 return true;
336             }
337         }
338         return false;
339     }
340 
getInterfaceClosure(IClassDefinition clazz)341     private Set<ITypeReference> getInterfaceClosure(IClassDefinition clazz) {
342         Set<ITypeReference> closure = new HashSet<ITypeReference>();
343         collectInterfaceClosure(ViewpointAdapter.getReferenceTo(clazz),
344                 closure);
345         return closure;
346     }
347 
collectInterfaceClosure(ITypeReference clazz, Set<ITypeReference> closure)348     private void collectInterfaceClosure(ITypeReference clazz,
349             Set<ITypeReference> closure) {
350 
351         IClassDefinition classDefinition = getClassDefinition(clazz);
352         Set<ITypeReference> interfaces = classDefinition.getInterfaces();
353         if (interfaces == null) {
354             return;
355         }
356         for (ITypeReference interfaze : interfaces) {
357             closure.add(interfaze);
358         }
359 
360         ITypeReference superclass = classDefinition.getSuperClass();
361         if (superclass != null) {
362             if (superclass instanceof IParameterizedType) {
363                 collectInterfaceClosure(((IParameterizedType) superclass)
364                         .getRawType(), closure);
365             } else {
366                 collectInterfaceClosure(superclass, closure);
367             }
368         }
369         for (ITypeReference interfaze : interfaces) {
370             if (interfaze instanceof IParameterizedType) {
371                 collectInterfaceClosure(((IParameterizedType) interfaze)
372                         .getRawType(), closure);
373             } else {
374                 collectInterfaceClosure(interfaze, closure);
375             }
376         }
377     }
378 
compareAnnotations(Set<IAnnotation> from, Set<IAnnotation> to)379     private Set<IAnnotationDelta> compareAnnotations(Set<IAnnotation> from,
380             Set<IAnnotation> to) {
381         return compareSets(from, to,
382                 new SigComparator<IAnnotation, IAnnotationDelta>() {
383                     public IAnnotationDelta createAddRemoveDelta(
384                             IAnnotation from, IAnnotation to) {
385                         return new SigAnnotationDelta(from, to);
386                     }
387 
388                     public boolean considerEqualElement(IAnnotation from,
389                             IAnnotation to) {
390                         return sameClassDefinition(from.getType()
391                                 .getClassDefinition(), to.getType()
392                                 .getClassDefinition());
393                     }
394 
395                     public IAnnotationDelta createChangedDelta(
396                             IAnnotation from, IAnnotation to) {
397                         return compareAnnotation(from, to);
398                     }
399                 });
400     }
401 
402     private Set<IAnnotationFieldDelta> compareAnnotationFields(
403             Set<IAnnotationField> from, Set<IAnnotationField> to) {
404         return compareSets(from, to,
405                 new SigComparator<IAnnotationField, IAnnotationFieldDelta>() {
406                     public boolean considerEqualElement(IAnnotationField from,
407                             IAnnotationField to) {
408                         return from.getName().equals(to.getName());
409                     }
410 
411                     public IAnnotationFieldDelta createAddRemoveDelta(
412                             IAnnotationField from, IAnnotationField to) {
413                         return new SigAnnotationFieldDelta(from, to);
414                     }
415 
416                     public IAnnotationFieldDelta createChangedDelta(
417                             IAnnotationField from, IAnnotationField to) {
418                         return compareAnnotationField(from, to);
419                     }
420                 });
421     }
422 
423     private Set<IEnumConstantDelta> compareEnumConstants(
424             Set<IEnumConstant> from, Set<IEnumConstant> to) {
425         return compareSets(from, to,
426                 new SigComparator<IEnumConstant, IEnumConstantDelta>() {
427                     public boolean considerEqualElement(IEnumConstant from,
428                             IEnumConstant to) {
429                         return from.getName().equals(to.getName());
430                     }
431 
432                     public IEnumConstantDelta createAddRemoveDelta(
433                             IEnumConstant from, IEnumConstant to) {
434                         return new SigEnumConstantDelta(from, to);
435                     }
436 
437                     public IEnumConstantDelta createChangedDelta(
438                             IEnumConstant from, IEnumConstant to) {
439                         return compareEnumConstant(from, to);
440                     }
441                 });
442     }
443 
444     private Set<IFieldDelta> compareFields(Set<IField> from, Set<IField> to) {
445         return compareSets(from, to, new SigComparator<IField, IFieldDelta>() {
446             public boolean considerEqualElement(IField from, IField to) {
447                 return from.getName().equals(to.getName());
448             }
449 
450             public IFieldDelta createAddRemoveDelta(IField from, IField to) {
451                 return new SigFieldDelta(from, to);
452             }
453 
454             public IFieldDelta createChangedDelta(IField from, IField to) {
455                 return compareField(from, to);
456             }
457         });
458     }
459 
460     private Set<IMethodDelta> compareMethods(IClassDefinition from,
461             IClassDefinition to) {
462         assert from != null;
463         assert to != null;
464 
465         Set<IMethod> toMethods = new HashSet<IMethod>(to.getMethods());
466         Set<IMethod> toClosure = getMethodClosure(to);
467         Set<IMethod> fromMethods = new HashSet<IMethod>(from.getMethods());
468         Set<IMethod> fromClosure = getMethodClosure(from);
469 
470         Set<IMethodDelta> deltas = new HashSet<IMethodDelta>();
471 
472         for (IMethod method : fromMethods) {
473             IMethod compatibleMethod = findCompatibleMethod(method, toMethods);
474             if (compatibleMethod == null) {
475                 compatibleMethod = findCompatibleMethod(method, toClosure);
476                 if (compatibleMethod == null) {
477                     deltas.add(new SigMethodDelta(method, null));
478                 }
479             }
480 
481             if (compatibleMethod != null) {
482                 IMethodDelta delta = compareMethod(method, compatibleMethod);
483                 if (delta != null) {
484                     deltas.add(delta);
485                 }
486             }
487         }
488 
489         for (IMethod method : toMethods) {
490             IMethod compatibleMethod = findCompatibleMethod(method, fromMethods);
491             if (compatibleMethod == null) {
492                 compatibleMethod = findCompatibleMethod(method, fromClosure);
493                 if (compatibleMethod == null) {
494                     deltas.add(new SigMethodDelta(null, method));
495                 }
496             }
497         }
498         return deltas.isEmpty() ? null : deltas;
499     }
500 
501     private IMethod findCompatibleMethod(IMethod method, Set<IMethod> set) {
502         for (IMethod methodFromSet : set) {
503             if (equalsSignature(method, methodFromSet)) {
504                 return methodFromSet;
505             }
506         }
507         return null;
508     }
509 
510 
511     private Set<IMethod> getMethodClosure(IClassDefinition clazz) {
512         Set<IMethod> closure = new HashSet<IMethod>();
513         collectMethods(new ClassProjection(clazz,
514                 new HashMap<ITypeVariableDefinition, ITypeReference>()),
515                 closure);
516         return closure;
517     }
518 
519     private void collectMethods(IClassDefinition clazz, Set<IMethod> closure) {
520         if (clazz == null) {
521             return;
522         }
523         if (clazz.getMethods() != null) {
524             closure.addAll(clazz.getMethods());
525         }
526         if (clazz.getSuperClass() != null) {
527             collectMethods(getClassDefinition(clazz.getSuperClass()), closure);
528         }
529         if (clazz.getInterfaces() != null) {
530             for (ITypeReference interfaze : clazz.getInterfaces()) {
531                 collectMethods(getClassDefinition(interfaze), closure);
532             }
533         }
534     }
535 
536     private Set<IConstructorDelta> compareConstructors(Set<IConstructor> from,
537             Set<IConstructor> to) {
538         return compareSets(from, to,
539                 new SigComparator<IConstructor, IConstructorDelta>() {
540                     public boolean considerEqualElement(IConstructor from,
541                             IConstructor to) {
542                         return equalsSignature(from, to);
543                     }
544 
545                     public IConstructorDelta createAddRemoveDelta(
546                             IConstructor from, IConstructor to) {
547                         return new SigConstructorDelta(from, to);
548                     }
549 
550                     public IConstructorDelta createChangedDelta(
551                             IConstructor from, IConstructor to) {
552                         return compareConstructor(from, to);
553                     }
554                 });
555     }
556 
557     // compares names and parameter types
558     private boolean equalsSignature(IExecutableMember from,
559             IExecutableMember to) {
560         if (from.getName().equals(to.getName())) {
561             return compareTypeSequence(getParameterList(from.getParameters()),
562                     getParameterList(to.getParameters()), true) == null;
563         }
564         return false;
565     }
566 
567     private List<ITypeReference> getParameterList(List<IParameter> parameters) {
568         List<ITypeReference> parameterTypes = new LinkedList<ITypeReference>();
569         for (IParameter parameter : parameters) {
570             parameterTypes.add(parameter.getType());
571         }
572         return parameterTypes;
573     }
574 
575     private IAnnotationDelta compareAnnotation(IAnnotation from,
576             IAnnotation to) {
577         assert sameClassDefinition(from.getType().getClassDefinition(), to
578                 .getType().getClassDefinition());
579 
580         Set<IAnnotationElement> fromAnnotationElement =
581                 getNormalizedAnnotationElements(from);
582         Set<IAnnotationElement> toAnnotationElement =
583                 getNormalizedAnnotationElements(to);
584 
585         Set<IAnnotationElementDelta> annotationElementDeltas =
586                 compareAnnotationElements(
587                         fromAnnotationElement, toAnnotationElement);
588         SigAnnotationDelta delta = null;
589 
590         if (annotationElementDeltas != null) {
591             delta = new SigAnnotationDelta(from, to);
592             delta.setAnnotationElementDeltas(annotationElementDeltas);
593         }
594         return delta;
595     }
596 
597     /**
598      * Returns the annotation elements for the given annotation. The returned
599      * set contains all declared elements plus all elements with default values.
600      *
601      * @param annotation
602      *            the annotation to return the elements for
603      * @return the default enriched annotation elements
604      */
605     private Set<IAnnotationElement> getNormalizedAnnotationElements(
606             IAnnotation annotation) {
607         Set<IAnnotationElement> elements = new HashSet<IAnnotationElement>(
608                 annotation.getElements());
609 
610         Set<String> names = new HashSet<String>();
611         for (IAnnotationElement annotationElement : elements) {
612             names.add(annotationElement.getDeclaringField().getName());
613         }
614 
615         for (IAnnotationField field : annotation.getType().getClassDefinition()
616                 .getAnnotationFields()) {
617             if (!names.contains(field.getName())) {
618                 SigAnnotationElement sigAnnotationElement =
619                         new SigAnnotationElement();
620                 sigAnnotationElement.setDeclaringField(field);
621                 sigAnnotationElement.setValue(field.getDefaultValue());
622                 elements.add(sigAnnotationElement);
623             }
624         }
625         return elements;
626     }
627 
628     private Set<IAnnotationElementDelta> compareAnnotationElements(
629             Set<IAnnotationElement> from, Set<IAnnotationElement> to) {
630         return compareSets(from, to,
631                 new SigComparator<IAnnotationElement, IAnnotationElementDelta>() {
632                     public boolean considerEqualElement(
633                             IAnnotationElement from, IAnnotationElement to) {
634                         return from.getDeclaringField().getName().equals(
635                                 to.getDeclaringField().getName());
636                     }
637 
638                     public IAnnotationElementDelta createAddRemoveDelta(
639                             IAnnotationElement from, IAnnotationElement to) {
640                         return new SigAnnotationElementDelta(from, to);
641                     }
642 
643                     public IAnnotationElementDelta createChangedDelta(
644                             IAnnotationElement from, IAnnotationElement to) {
645                         return compareAnnotationElement(from, to);
646                     }
647                 });
648     }
649 
650     private IAnnotationElementDelta compareAnnotationElement(
651             IAnnotationElement from, IAnnotationElement to) {
652         SigAnnotationElementDelta delta = null;
653         SigValueDelta valueDelta = compareValue(from.getValue(), to.getValue());
654 
655         if (valueDelta != null) {
656             delta = new SigAnnotationElementDelta(from, to);
657             delta.setValueDelta(valueDelta);
658         }
659         return delta;
660     }
661 
662     /**
663      * Removes the {@link Modifier#ABSTRACT} modifier.
664      */
665     private Set<Modifier> prepareMethodModifiers(IMethod method) {
666         Set<Modifier> modifierCopy = new HashSet<Modifier>(method
667                 .getModifiers());
668         modifierCopy.remove(Modifier.ABSTRACT);
669         return modifierCopy;
670     }
671 
672     private IMethodDelta compareMethod(IMethod from, IMethod to) {
673         assert from != null && to != null;
674 
675         SigMethodDelta methodDelta = null;
676         Set<IModifierDelta> modiferDeltas = compareModifiers(
677                 prepareMethodModifiers(from), prepareMethodModifiers(to));
678         if (modiferDeltas != null) {
679             methodDelta = new SigMethodDelta(from, to);
680             methodDelta.setModifierDeltas(modiferDeltas);
681         }
682 
683         Set<IParameterDelta> parameterDeltas = compareParameterSequence(from
684                 .getParameters(), to.getParameters());
685         if (parameterDeltas != null) {
686             if (methodDelta == null) {
687                 methodDelta = new SigMethodDelta(from, to);
688             }
689             methodDelta.setParameterDeltas(parameterDeltas);
690         }
691 
692         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
693                 .getAnnotations(), to.getAnnotations());
694         if (annotationDeltas != null) {
695             if (methodDelta == null) {
696                 methodDelta = new SigMethodDelta(from, to);
697             }
698             methodDelta.setAnnotationDeltas(annotationDeltas);
699         }
700 
701         Set<ITypeVariableDefinitionDelta> typeParameterDeltas =
702                 compareTypeVariableSequence(from.getTypeParameters(),
703                         to.getTypeParameters());
704         if (typeParameterDeltas != null) {
705             if (methodDelta == null) {
706                 methodDelta = new SigMethodDelta(from, to);
707             }
708             methodDelta.setTypeVariableDeltas(typeParameterDeltas);
709         }
710 
711         Set<ITypeReferenceDelta<?>> exceptionDeltas = compareTypes(
712                 normalizeExceptions(from.getExceptions()),
713                 normalizeExceptions(to.getExceptions()));
714         if (exceptionDeltas != null) {
715             if (methodDelta == null) {
716                 methodDelta = new SigMethodDelta(from, to);
717             }
718             methodDelta.setExceptionDeltas(exceptionDeltas);
719         }
720 
721         ITypeReferenceDelta<?> returnTypeDelta = compareType(from
722                 .getReturnType(), to.getReturnType(), false);
723         if (returnTypeDelta != null) {
724             if (methodDelta == null) {
725                 methodDelta = new SigMethodDelta(from, to);
726             }
727             methodDelta.setReturnTypeDelta(returnTypeDelta);
728         }
729 
730         return methodDelta;
731     }
732 
733     // remove runtime exceptions,
734     // remove sub types of containing exception
735     private Set<ITypeReference> normalizeExceptions(
736             Set<ITypeReference> exceptions) {
737         Set<ITypeReference> exceptionCopy = new HashSet<ITypeReference>(
738                 exceptions);
739 
740         Iterator<ITypeReference> iterator = exceptionCopy.iterator();
741         while (iterator.hasNext()) {
742             ITypeReference exception = iterator.next();
743             if (isRuntimeExceptionOrErrorSubtype(exception)) {
744                 iterator.remove();
745             }
746         }
747         exceptionCopy = removeSpecializations(exceptionCopy);
748         return exceptionCopy;
749     }
750 
751     private Set<ITypeReference> removeSpecializations(
752             Set<ITypeReference> exceptions) {
753         Set<ITypeReference> exceptionCopy = new HashSet<ITypeReference>(
754                 exceptions);
755         for (ITypeReference type : exceptions) {
756             Iterator<ITypeReference> it = exceptionCopy.iterator();
757             while (it.hasNext()) {
758                 ITypeReference subType = it.next();
759                 if (isSuperClass(getClassDefinition(type),
760                         getClassDefinition(subType))) {
761                     it.remove();
762                 }
763             }
764         }
765         return exceptionCopy;
766     }
767 
768     /**
769      * Returns true if superC is a super class of subC.
770      */
771     private boolean isSuperClass(IClassDefinition superC,
772             IClassDefinition subC) {
773         if (superC == null || subC == null) {
774             return false;
775         }
776 
777         if (subC.getSuperClass() == null) {
778             return false;
779         } else {
780             if (getClassDefinition(subC.getSuperClass()).equals(superC)) {
781                 return true;
782             } else {
783                 return isSuperClass(superC, getClassDefinition(subC
784                         .getSuperClass()));
785             }
786         }
787     }
788 
789     private boolean isSuperInterface(IClassDefinition superClass,
790             IClassDefinition subClass) {
791         if (superClass == null || subClass == null) {
792             return false;
793         }
794 
795         if (subClass.getInterfaces() == null) {
796             return false;
797         } else {
798             if (getClassDefinitions(subClass.getInterfaces()).contains(
799                     superClass)) {
800                 return true;
801             } else {
802                 for (ITypeReference subType : subClass.getInterfaces()) {
803                     if (isSuperInterface(superClass,
804                             getClassDefinition(subType))) {
805                         return true;
806                     }
807                 }
808                 return false;
809             }
810         }
811     }
812 
813     private Set<IClassDefinition> getClassDefinitions(
814             Set<ITypeReference> references) {
815         Set<IClassDefinition> definitions = new HashSet<IClassDefinition>();
816         for (ITypeReference ref : references) {
817             definitions.add(getClassDefinition(ref));
818         }
819         return definitions;
820     }
821 
822     /**
823      * Returns null if type is not one of:
824      * <ul>
825      * <li>IClassReference</li>
826      * <li>IParameterizedType</li>
827      * </ul>
828      */
829     private IClassDefinition getClassDefinition(ITypeReference type) {
830         assert type != null;
831 
832         IClassDefinition returnValue = null;
833         if (type instanceof IClassReference) {
834             returnValue = ((IClassReference) type).getClassDefinition();
835         } else if (type instanceof IParameterizedType) {
836             returnValue = ((IParameterizedType) type).getRawType()
837                     .getClassDefinition();
838         }
839         return returnValue;
840     }
841 
842     private boolean isRuntimeExceptionOrErrorSubtype(ITypeReference exception) {
843 
844         IClassDefinition clazz = getClassDefinition(exception);
845         if (clazz != null) {
846             if (isRuntimeExceptionOrError(clazz)) {
847                 return true;
848             } else if (clazz.getSuperClass() != null) {
849                 return isRuntimeExceptionOrErrorSubtype(clazz.getSuperClass());
850             } else {
851                 return false;
852             }
853         }
854         return false;
855     }
856 
857     private boolean isRuntimeExceptionOrError(IClassDefinition exception) {
858         if (exception == null) {
859             return false;
860         }
861         String packageName = exception.getPackageName();
862         String className = exception.getName();
863 
864         if (packageName != null && className != null
865                 && "java.lang".equals(packageName)) {
866             return "RuntimeException".equals(className)
867                     || "Error".equals(className);
868         }
869         return false;
870     }
871 
872     private IConstructorDelta compareConstructor(IConstructor from,
873             IConstructor to) {
874         SigConstructorDelta constructorDelta = null;
875         Set<IModifierDelta> modiferDeltas = compareModifiers(from
876                 .getModifiers(), to.getModifiers());
877         if (modiferDeltas != null) {
878             constructorDelta = new SigConstructorDelta(from, to);
879             constructorDelta.setModifierDeltas(modiferDeltas);
880         }
881 
882         Set<IParameterDelta> parameterDeltas = compareParameterSequence(from
883                 .getParameters(), to.getParameters());
884         if (parameterDeltas != null) {
885             if (constructorDelta == null) {
886                 constructorDelta = new SigConstructorDelta(from, to);
887             }
888             constructorDelta.setParameterDeltas(parameterDeltas);
889         }
890 
891         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
892                 .getAnnotations(), to.getAnnotations());
893         if (annotationDeltas != null) {
894             if (constructorDelta == null) {
895                 constructorDelta = new SigConstructorDelta(from, to);
896             }
897             constructorDelta.setAnnotationDeltas(annotationDeltas);
898         }
899 
900         Set<ITypeVariableDefinitionDelta> typeParameterDeltas =
901                 compareTypeVariableSequence(from.getTypeParameters(),
902                         to.getTypeParameters());
903         if (typeParameterDeltas != null) {
904             if (constructorDelta == null) {
905                 constructorDelta = new SigConstructorDelta(from, to);
906             }
907             constructorDelta.setTypeVariableDeltas(typeParameterDeltas);
908         }
909 
910         Set<ITypeReferenceDelta<?>> exceptionDeltas = compareTypes(
911                 normalizeExceptions(from.getExceptions()),
912                 normalizeExceptions(to.getExceptions()));
913         if (exceptionDeltas != null) {
914             if (constructorDelta == null) {
915                 constructorDelta = new SigConstructorDelta(from, to);
916             }
917             constructorDelta.setExceptionDeltas(exceptionDeltas);
918         }
919         return constructorDelta;
920     }
921 
922     private Set<IParameterDelta> compareParameterSequence(
923             List<IParameter> from, List<IParameter> to) {
924         assert from.size() == to.size();
925         Set<IParameterDelta> deltas = new HashSet<IParameterDelta>();
926         Iterator<IParameter> fromIterator = from.iterator();
927         Iterator<IParameter> toIterator = to.iterator();
928         while (fromIterator.hasNext() && toIterator.hasNext()) {
929             IParameterDelta delta = compareParameter(fromIterator.next(),
930                     toIterator.next());
931             if (delta != null) {
932                 deltas.add(delta);
933             }
934         }
935         return deltas.isEmpty() ? null : deltas;
936     }
937 
938     private IParameterDelta compareParameter(IParameter from, IParameter to) {
939         SigParameterDelta delta = null;
940         ITypeReferenceDelta<?> typeDelta = compareType(from.getType(), to
941                 .getType(), false);
942         if (typeDelta != null) {
943             if (delta == null) {
944                 delta = new SigParameterDelta(from, to);
945             }
946             delta.setTypeDelta(typeDelta);
947         }
948 
949         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
950                 .getAnnotations(), to.getAnnotations());
951         if (annotationDeltas != null) {
952             if (delta == null) {
953                 delta = new SigParameterDelta(from, to);
954             }
955             delta.setAnnotationDeltas(annotationDeltas);
956         }
957         return delta;
958     }
959 
960     private Set<ITypeVariableDefinitionDelta> compareTypeVariableSequence(
961             List<ITypeVariableDefinition> from,
962             List<ITypeVariableDefinition> to) {
963         Set<ITypeVariableDefinitionDelta> deltas =
964                 new HashSet<ITypeVariableDefinitionDelta>();
965         if (from.size() != to.size()) {
966             for (ITypeVariableDefinition fromVariable : from) {
967                 deltas.add(new SigTypeVariableDefinitionDelta(fromVariable,
968                         null));
969             }
970             for (ITypeVariableDefinition toVariable : to) {
971                 deltas
972                         .add(new SigTypeVariableDefinitionDelta(null,
973                                 toVariable));
974             }
975         }
976 
977         Iterator<ITypeVariableDefinition> fromIterator = from.iterator();
978         Iterator<ITypeVariableDefinition> toIterator = to.iterator();
979         while (fromIterator.hasNext() && toIterator.hasNext()) {
980             ITypeVariableDefinitionDelta delta = compareTypeVariableDefinition(
981                     fromIterator.next(), toIterator.next());
982             if (delta != null) {
983                 deltas.add(delta);
984             }
985         }
986         return deltas.isEmpty() ? null : deltas;
987     }
988 
989     private ITypeVariableDefinitionDelta compareTypeVariableDefinition(
990             ITypeVariableDefinition from, ITypeVariableDefinition to) {
991         IGenericDeclarationDelta declarationDelta = compareGenericDeclaration(
992                 from, to);
993 
994         if (declarationDelta != null) {
995             SigTypeVariableDefinitionDelta delta =
996                     new SigTypeVariableDefinitionDelta(from, to);
997             delta.setGenericDeclarationDelta(declarationDelta);
998             return delta;
999         }
1000         IUpperBoundsDelta upperBoundDelta = compareUpperBounds(from
1001                 .getUpperBounds(), to.getUpperBounds());
1002 
1003         if (upperBoundDelta != null) {
1004             SigTypeVariableDefinitionDelta delta =
1005                     new SigTypeVariableDefinitionDelta(from, to);
1006             delta.setUpperBoundsDelta(upperBoundDelta);
1007             return delta;
1008         }
1009         return null;
1010     }
1011 
1012     private ITypeReferenceDelta<ITypeVariableReference> compareTypeVariableReference(
1013             ITypeVariableReference from, ITypeVariableReference to) {
1014         IGenericDeclarationDelta declarationDelta = compareGenericDeclaration(
1015                 from.getTypeVariableDefinition(), to
1016                         .getTypeVariableDefinition());
1017         if (declarationDelta != null) {
1018             SigTypeVariableReferenceDelta delta =
1019                     new SigTypeVariableReferenceDelta(from, to);
1020             delta.setGenericDeclarationDelta(declarationDelta);
1021             return delta;
1022         }
1023         return null;
1024     }
1025 
1026     private Set<IModifierDelta> compareModifiers(Set<Modifier> from,
1027             Set<Modifier> to) {
1028         return compareSets(from, to,
1029                 new SigComparator<Modifier, IModifierDelta>() {
1030                     public boolean considerEqualElement(Modifier from,
1031                             Modifier to) {
1032                         return from.equals(to);
1033                     }
1034 
1035                     public IModifierDelta createAddRemoveDelta(Modifier from,
1036                             Modifier to) {
1037                         return new SigModifierDelta(from, to);
1038                     }
1039 
1040                     public IModifierDelta createChangedDelta(Modifier from,
1041                             Modifier to) {
1042                         return null;
1043                     }
1044                 });
1045     }
1046 
1047 
1048     private IFieldDelta compareField(IField from, IField to) {
1049         SigFieldDelta fieldDelta = null;
1050 
1051         Set<IModifierDelta> modiferDeltas = compareModifiers(from
1052                 .getModifiers(), to.getModifiers());
1053         if (modiferDeltas != null) {
1054             fieldDelta = new SigFieldDelta(from, to);
1055             fieldDelta.setModifierDeltas(modiferDeltas);
1056         }
1057 
1058         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
1059                 .getAnnotations(), to.getAnnotations());
1060         if (annotationDeltas != null) {
1061             if (fieldDelta == null) {
1062                 fieldDelta = new SigFieldDelta(from, to);
1063             }
1064             fieldDelta.setAnnotationDeltas(annotationDeltas);
1065         }
1066 
1067         ITypeReferenceDelta<?> typeDelta = compareType(from.getType(), to
1068                 .getType(), false);
1069         if (typeDelta != null) {
1070             if (fieldDelta == null) {
1071                 fieldDelta = new SigFieldDelta(from, to);
1072             }
1073             fieldDelta.setTypeDelta(typeDelta);
1074         }
1075         return fieldDelta;
1076     }
1077 
1078     private IEnumConstantDelta compareEnumConstant(IEnumConstant from,
1079             IEnumConstant to) {
1080         SigEnumConstantDelta enumConstantDelta = null;
1081 
1082         Set<IModifierDelta> modiferDeltas = compareModifiers(from
1083                 .getModifiers(), to.getModifiers());
1084         if (modiferDeltas != null) {
1085             enumConstantDelta = new SigEnumConstantDelta(from, to);
1086             enumConstantDelta.setModifierDeltas(modiferDeltas);
1087         }
1088 
1089         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
1090                 .getAnnotations(), to.getAnnotations());
1091         if (annotationDeltas != null) {
1092             if (enumConstantDelta == null) {
1093                 enumConstantDelta = new SigEnumConstantDelta(from, to);
1094             }
1095             enumConstantDelta.setAnnotationDeltas(annotationDeltas);
1096         }
1097 
1098         ITypeReferenceDelta<?> typeDelta = compareType(from.getType(), to
1099                 .getType(), false);
1100         if (typeDelta != null) {
1101             if (enumConstantDelta == null) {
1102                 enumConstantDelta = new SigEnumConstantDelta(from, to);
1103             }
1104             enumConstantDelta.setTypeDelta(typeDelta);
1105         }
1106 
1107         // FIXME ordinal not supported in dex
1108         // ValueDelta ordinalDelta = compareValue(from.getOrdinal(),
1109         // to.getOrdinal());
1110         // if (ordinalDelta != null) {
1111         // if (enumConstantDelta == null) {
1112         // enumConstantDelta = new SigEnumConstantDelta(from, to);
1113         // }
1114         // enumConstantDelta.setOrdinalDelta(ordinalDelta);
1115         // }
1116 
1117         return enumConstantDelta;
1118     }
1119 
1120     private IAnnotationFieldDelta compareAnnotationField(IAnnotationField from,
1121             IAnnotationField to) {
1122         SigAnnotationFieldDelta annotationFieldDelta = null;
1123 
1124         Set<IModifierDelta> modiferDeltas = compareModifiers(from
1125                 .getModifiers(), to.getModifiers());
1126         if (modiferDeltas != null) {
1127             annotationFieldDelta = new SigAnnotationFieldDelta(from, to);
1128             annotationFieldDelta.setModifierDeltas(modiferDeltas);
1129         }
1130 
1131         Set<IAnnotationDelta> annotationDeltas = compareAnnotations(from
1132                 .getAnnotations(), to.getAnnotations());
1133         if (annotationDeltas != null) {
1134             if (annotationFieldDelta == null) {
1135                 annotationFieldDelta = new SigAnnotationFieldDelta(from, to);
1136             }
1137             annotationFieldDelta.setAnnotationDeltas(annotationDeltas);
1138         }
1139 
1140         ITypeReferenceDelta<?> typeDelta = compareType(from.getType(), to
1141                 .getType(), false);
1142         if (typeDelta != null) {
1143             if (annotationFieldDelta == null) {
1144                 annotationFieldDelta = new SigAnnotationFieldDelta(from, to);
1145             }
1146             annotationFieldDelta.setTypeDelta(typeDelta);
1147         }
1148 
1149         IValueDelta defaultValueDelta = compareValue(from.getDefaultValue(), to
1150                 .getDefaultValue());
1151         if (defaultValueDelta != null) {
1152             if (annotationFieldDelta == null) {
1153                 annotationFieldDelta = new SigAnnotationFieldDelta(from, to);
1154             }
1155             annotationFieldDelta.setDefaultValueDelta(defaultValueDelta);
1156         }
1157 
1158         return annotationFieldDelta;
1159     }
1160 
1161     private SigValueDelta compareValue(Object from, Object to) {
1162         // same value
1163         if (from == null && to == null) {
1164             return null;
1165         }
1166 
1167         // one of both is null and other is not
1168         if (from == null || to == null) {
1169             return new SigValueDelta(from, to);
1170         }
1171 
1172         SigValueDelta delta = null;
1173         // different types
1174         if (from.getClass() == to.getClass()) {
1175             if (from.getClass().isArray()) {
1176                 Object[] fromArray = (Object[]) from;
1177                 Object[] toArray = (Object[]) from;
1178                 if (!Arrays.equals(fromArray, toArray)) {
1179                     delta = new SigValueDelta(from, to);
1180                 }
1181             } else if (from instanceof IEnumConstant) {
1182                 IEnumConstantDelta enumConstantDelta = compareEnumConstant(
1183                         (IEnumConstant) from, (IEnumConstant) to);
1184                 if (enumConstantDelta != null) {
1185                     delta = new SigValueDelta(from, to);
1186                 }
1187             } else if (from instanceof IAnnotation) {
1188                 IAnnotationDelta annotationDelta = compareAnnotation(
1189                         (IAnnotation) from, (IAnnotation) to);
1190                 if (annotationDelta != null) {
1191                     delta = new SigValueDelta(from, to);
1192                 }
1193             } else if (from instanceof IField) {
1194                 IFieldDelta fieldDelta = compareField((IField) from,
1195                         (IField) to);
1196                 if (fieldDelta != null) {
1197                     delta = new SigValueDelta(from, to);
1198                 }
1199             } else if (from instanceof ITypeReference) {
1200                 ITypeReferenceDelta<? extends ITypeReference> typeDelta =
1201                         compareType((ITypeReference) from, (ITypeReference) to,
1202                                 false);
1203                 if (typeDelta != null) {
1204                     delta = new SigValueDelta(from, to);
1205                 }
1206             } else if (!from.equals(to)) {
1207                 delta = new SigValueDelta(from, to);
1208             }
1209 
1210         } else if (!(from == null && to == null)) {
1211             delta = new SigValueDelta(from, to);
1212         }
1213         return delta;
1214     }
1215 
1216     private boolean considerEqualTypes(ITypeReference from, ITypeReference to) {
1217         assert from != null && to != null;
1218 
1219         if (implementInterface(from, to, IPrimitiveType.class)) {
1220             return comparePrimitiveType((IPrimitiveType) from,
1221                     (IPrimitiveType) to) == null;
1222         }
1223         if (implementInterface(from, to, IClassReference.class)) {
1224             return sameClassDefinition(((IClassReference) from)
1225                     .getClassDefinition(), ((IClassReference) to)
1226                     .getClassDefinition());
1227         }
1228         if (implementInterface(from, to, IArrayType.class)) {
1229             return considerEqualTypes(((IArrayType) from).getComponentType(),
1230                     ((IArrayType) to).getComponentType());
1231         }
1232         if (implementInterface(from, to, IParameterizedType.class)) {
1233             return compareClassReference(((IParameterizedType) from)
1234                     .getRawType(), ((IParameterizedType) to)
1235                     .getRawType()) == null;
1236         }
1237         if (implementInterface(from, to, ITypeVariableReference.class)) {
1238             return compareTypeVariableReference((ITypeVariableReference) from,
1239                     (ITypeVariableReference) to) == null;
1240         }
1241 
1242         return false;
1243     }
1244 
1245     private Set<ITypeReference> fromComparison = new HashSet<ITypeReference>();
1246     private Set<ITypeReference> toComparison = new HashSet<ITypeReference>();
1247 
1248 
1249     private boolean areInComparison(ITypeReference from, ITypeReference to) {
1250         return fromComparison.contains(from) && toComparison.contains(to);
1251     }
1252 
1253     private void markInComparison(ITypeReference from, ITypeReference to) {
1254         fromComparison.add(from);
1255         toComparison.add(to);
1256     }
1257 
1258     private void markFinishedComparison(ITypeReference from,
1259             ITypeReference to) {
1260         fromComparison.remove(from);
1261         toComparison.remove(to);
1262     }
1263 
1264     private ITypeReferenceDelta<? extends ITypeReference> compareType(
1265             ITypeReference from, ITypeReference to, boolean acceptErasedTypes) {
1266 
1267         if (from == null && to == null) {
1268             return null;
1269         }
1270         if ((from == null && to != null) || (from != null && to == null)) {
1271             return new SigTypeDelta<ITypeReference>(from, to);
1272         }
1273         if (areInComparison(from, to)) {
1274             return null;
1275         }
1276         try {
1277             markInComparison(from, to);
1278 
1279             if (implementInterface(from, to, IPrimitiveType.class)) {
1280                 return comparePrimitiveType((IPrimitiveType) from,
1281                         (IPrimitiveType) to);
1282             }
1283             if (implementInterface(from, to, IClassReference.class)) {
1284                 return compareClassReference((IClassReference) from,
1285                         (IClassReference) to);
1286             }
1287             if (implementInterface(from, to, IArrayType.class)) {
1288                 return compareArrayType((IArrayType) from, (IArrayType) to);
1289             }
1290             if (implementInterface(from, to, IParameterizedType.class)) {
1291                 return compareParameterizedType((IParameterizedType) from,
1292                         (IParameterizedType) to, acceptErasedTypes);
1293             }
1294             if (implementInterface(from, to, ITypeVariableReference.class)) {
1295                 return compareTypeVariableReference(
1296                         (ITypeVariableReference) from,
1297                         (ITypeVariableReference) to);
1298             }
1299             if (implementInterface(from, to, IWildcardType.class)) {
1300                 return compareWildcardType((IWildcardType) from,
1301                         (IWildcardType) to);
1302             }
1303 
1304             if (acceptErasedTypes) {
1305                 if (isGeneric(from) && !isGeneric(to)) {
1306                     return compareType(getErasedType(from), to, false);
1307                 }
1308 
1309                 if (!isGeneric(from) && isGeneric(to)) {
1310                     return compareType(from, getErasedType(to), false);
1311                 }
1312             }
1313             return new SigTypeDelta<ITypeReference>(from, to);
1314         } finally {
1315             markFinishedComparison(from, to);
1316         }
1317     }
1318 
1319     private boolean isGeneric(ITypeReference reference) {
1320         if (reference instanceof IParameterizedType
1321                 || reference instanceof ITypeVariableReference
1322                 || reference instanceof IWildcardType) {
1323             return true;
1324         }
1325         if (reference instanceof IArrayType) {
1326             return isGeneric(((IArrayType) reference).getComponentType());
1327         }
1328         return false;
1329     }
1330 
1331     private ITypeReference getErasedType(ITypeReference reference) {
1332 
1333         if (reference instanceof IParameterizedType) {
1334             return ((IParameterizedType) reference).getRawType();
1335         }
1336         if (reference instanceof ITypeVariableReference) {
1337             ITypeVariableDefinition typeVariableDefinition =
1338                     ((ITypeVariableReference) reference)
1339                             .getTypeVariableDefinition();
1340             return getErasedType(
1341                     typeVariableDefinition.getUpperBounds().get(0));
1342         }
1343         if (reference instanceof IWildcardType) {
1344             return getErasedType(((IWildcardType) reference).getUpperBounds()
1345                     .get(0));
1346         }
1347         if (reference instanceof IArrayType) {
1348             // FIXME implement with erasure projection?
1349             return new SigArrayType(getErasedType(((IArrayType) reference)
1350                     .getComponentType()));
1351         }
1352         if (reference instanceof IPrimitiveType) {
1353             return reference;
1354         }
1355         if (reference instanceof IClassReference) {
1356             return reference;
1357         }
1358         throw new IllegalArgumentException("Unexpected type: " + reference);
1359     }
1360 
1361     private boolean implementInterface(ITypeReference from, ITypeReference to,
1362             Class<?> check) {
1363         return check.isAssignableFrom(from.getClass())
1364                 && check.isAssignableFrom(to.getClass());
1365     }
1366 
1367     private IWildcardTypeDelta compareWildcardType(IWildcardType from,
1368             IWildcardType to) {
1369         SigWildcardTypeDelta delta = null;
1370 
1371         ITypeReference fromLowerBound = from.getLowerBound();
1372         ITypeReference toLowerBound = to.getLowerBound();
1373 
1374         ITypeReferenceDelta<?> lowerBoundDelta = compareType(fromLowerBound,
1375                 toLowerBound, false);
1376         if (lowerBoundDelta != null) {
1377             delta = new SigWildcardTypeDelta(from, to);
1378             delta.setLowerBoundDelta(lowerBoundDelta);
1379         }
1380 
1381         IUpperBoundsDelta upperBoundsDelta = compareUpperBounds(from
1382                 .getUpperBounds(), to.getUpperBounds());
1383         if (upperBoundsDelta != null) {
1384             if (delta == null) {
1385                 delta = new SigWildcardTypeDelta(from, to);
1386             }
1387             delta.setUpperBoundDelta(upperBoundsDelta);
1388         }
1389         return delta;
1390     }
1391 
1392     private IGenericDeclarationDelta compareGenericDeclaration(
1393             ITypeVariableDefinition fromVariable,
1394             ITypeVariableDefinition toVariable) {
1395         IGenericDeclarationDelta delta = null;
1396 
1397         IGenericDeclaration from = fromVariable.getGenericDeclaration();
1398         IGenericDeclaration to = toVariable.getGenericDeclaration();
1399 
1400         if (from != null && to != null) {
1401 
1402             if (from.getClass() != to.getClass()) {
1403                 delta = new SigGenericDeclarationDelta(from, to);
1404             } else if (from instanceof IClassDefinition) {
1405                 IClassDefinition fromDeclaringClass = (IClassDefinition) from;
1406                 IClassDefinition toDeclaringClass = (IClassDefinition) to;
1407 
1408                 if (!sameClassDefinition(fromDeclaringClass,
1409                         toDeclaringClass)) {
1410                     delta = new SigGenericDeclarationDelta(from, to);
1411                 }
1412 
1413             } else if (from instanceof IConstructor) {
1414                 IConstructor fromConstructor = (IConstructor) from;
1415                 IConstructor toConstructor = (IConstructor) from;
1416 
1417                 String fromConstructorName = fromConstructor.getName();
1418                 String fromClassName = fromConstructor.getDeclaringClass()
1419                         .getQualifiedName();
1420 
1421                 String toConstructorName = toConstructor.getName();
1422                 String toClassName = toConstructor.getDeclaringClass()
1423                         .getQualifiedName();
1424 
1425                 if ((!fromConstructorName.equals(toConstructorName))
1426                         || (!fromClassName.equals(toClassName))) {
1427                     delta = new SigGenericDeclarationDelta(from, to);
1428                 }
1429 
1430             } else if (from instanceof IMethod) {
1431                 IMethod fromMethod = (IMethod) from;
1432                 IMethod toMethod = (IMethod) from;
1433 
1434                 String fromConstructorName = fromMethod.getName();
1435                 String fromClassName = fromMethod.getDeclaringClass()
1436                         .getQualifiedName();
1437 
1438                 String toConstructorName = toMethod.getName();
1439                 String toClassName = toMethod.getDeclaringClass()
1440                         .getQualifiedName();
1441 
1442                 if ((!fromConstructorName.equals(toConstructorName))
1443                         || (!fromClassName.equals(toClassName))) {
1444                     delta = new SigGenericDeclarationDelta(from, to);
1445                 }
1446             } else {
1447                 throw new IllegalStateException("Invlaid eclaration site: "
1448                         + from);
1449             }
1450 
1451             // check position
1452             int fromPosition = getPositionOf(fromVariable, from);
1453             int toPosition = getPositionOf(toVariable, to);
1454 
1455             if (fromPosition != toPosition) {
1456                 delta = new SigGenericDeclarationDelta(from, to);
1457             }
1458 
1459 
1460         } else {
1461             // one of both is null
1462             delta = new SigGenericDeclarationDelta(from, to);
1463         }
1464         return delta;
1465     }
1466 
1467     private int getPositionOf(ITypeVariableDefinition variable,
1468             IGenericDeclaration declaration) {
1469         return declaration.getTypeParameters().indexOf(variable);
1470     }
1471 
1472     private IUpperBoundsDelta compareUpperBounds(List<ITypeReference> from,
1473             List<ITypeReference> to) {
1474         if (from.isEmpty() && to.isEmpty()) {
1475             return null;
1476         }
1477         SigUpperBoundsDelta delta = null;
1478 
1479         ITypeReference fromFirstUpperBound = from.get(0);
1480         ITypeReference toFirstUpperBound = to.get(0);
1481 
1482         ITypeReferenceDelta<?> firstUpperBoundDelta = compareType(
1483                 fromFirstUpperBound, toFirstUpperBound, false);
1484         if (firstUpperBoundDelta != null) {
1485             delta = new SigUpperBoundsDelta(from, to);
1486             delta.setFirstUpperBoundDelta(firstUpperBoundDelta);
1487         } else {
1488             // normalize
1489             Set<ITypeReference> normalizedfrom = removeGeneralizations(
1490                     new HashSet<ITypeReference>(from));
1491             Set<ITypeReference> normalizedto = removeGeneralizations(
1492                     new HashSet<ITypeReference>(to));
1493 
1494             Set<ITypeReferenceDelta<?>> remainingUpperBoundsDelta =
1495                     compareTypes(normalizedfrom, normalizedto);
1496             if (remainingUpperBoundsDelta != null) {
1497                 delta = new SigUpperBoundsDelta(from, to);
1498                 delta.setRemainingUpperBoundDeltas(remainingUpperBoundsDelta);
1499             }
1500         }
1501         return delta;
1502     }
1503 
1504     private Set<ITypeReference> removeGeneralizations(
1505             Set<ITypeReference> bounds) {
1506         Set<ITypeReference> boundsCopy = new HashSet<ITypeReference>(bounds);
1507         for (ITypeReference type : bounds) {
1508             Iterator<ITypeReference> it = boundsCopy.iterator();
1509             while (it.hasNext()) {
1510                 ITypeReference superType = it.next();
1511                 if (isSuperClass(getClassDefinition(superType),
1512                         getClassDefinition(type))
1513                         || isSuperInterface(getClassDefinition(superType),
1514                                 getClassDefinition(type))) {
1515                     it.remove();
1516                 }
1517             }
1518         }
1519         return boundsCopy;
1520     }
1521 
1522     private IParameterizedTypeDelta compareParameterizedType(
1523             IParameterizedType from, IParameterizedType to,
1524             boolean ignoreTypeArguments) {
1525 
1526         SigParameterizedTypeDelta delta = null;
1527         // check raw type
1528         ITypeReferenceDelta<?> rawTypeDelta = compareType(from.getRawType(), to
1529                 .getRawType(), false);
1530         if (rawTypeDelta != null) {
1531             delta = new SigParameterizedTypeDelta(from, to);
1532             delta.setRawTypeDelta(rawTypeDelta);
1533         } else {
1534             // check owner type
1535             ITypeReferenceDelta<?> ownerTypeDelta = compareType(from
1536                     .getOwnerType(), to.getOwnerType(), false);
1537             if (ownerTypeDelta != null) {
1538                 delta = new SigParameterizedTypeDelta(from, to);
1539                 delta.setOwnerTypeDelta(ownerTypeDelta);
1540             } else {
1541                 // check argument type
1542                 if (!ignoreTypeArguments) {
1543                     Set<ITypeReferenceDelta<?>> argumentTypeDeltas =
1544                             compareTypeSequence(from.getTypeArguments(),
1545                                     to.getTypeArguments(), false);
1546                     if (argumentTypeDeltas != null) {
1547                         delta = new SigParameterizedTypeDelta(from, to);
1548                         delta.setArgumentTypeDeltas(argumentTypeDeltas);
1549                     }
1550                 }
1551             }
1552         }
1553         return delta;
1554     }
1555 
1556     private Set<ITypeReferenceDelta<? extends ITypeReference>> compareTypeSequence(
1557             List<ITypeReference> from, List<ITypeReference> to,
1558             boolean ignoreTypeArguments) {
1559         Set<ITypeReferenceDelta<?>> deltas =
1560                 new HashSet<ITypeReferenceDelta<?>>();
1561         if (from.size() != to.size()) {
1562 
1563             for (ITypeReference type : from) {
1564                 deltas.add(new SigTypeDelta<ITypeReference>(type, null));
1565             }
1566             for (ITypeReference type : to) {
1567                 deltas.add(new SigTypeDelta<ITypeReference>(null, type));
1568             }
1569             return deltas;
1570         }
1571 
1572         Iterator<? extends ITypeReference> fromIterator = from.iterator();
1573         Iterator<? extends ITypeReference> toIterator = to.iterator();
1574         while (fromIterator.hasNext() && toIterator.hasNext()) {
1575             ITypeReferenceDelta<?> delta = compareType(fromIterator.next(),
1576                     toIterator.next(), ignoreTypeArguments);
1577             if (delta != null) {
1578                 deltas.add(delta);
1579             }
1580         }
1581         return deltas.isEmpty() ? null : deltas;
1582     }
1583 
1584     private Set<ITypeReferenceDelta<? extends ITypeReference>> compareTypes(
1585             Set<ITypeReference> from, Set<ITypeReference> to) {
1586         return compareSets(from, to,
1587                 new SigComparator<ITypeReference, ITypeReferenceDelta<? extends ITypeReference>>() {
1588                     public ITypeReferenceDelta<? extends ITypeReference> createAddRemoveDelta(
1589                             ITypeReference from, ITypeReference to) {
1590                         return new SigTypeDelta<ITypeReference>(from, to);
1591                     }
1592 
1593                     public boolean considerEqualElement(ITypeReference from,
1594                             ITypeReference to) {
1595                         return considerEqualTypes(from, to);
1596                     }
1597 
1598                     public ITypeReferenceDelta<? extends ITypeReference> createChangedDelta(
1599                             ITypeReference from, ITypeReference to) {
1600                         return compareType(from, to, false);
1601                     }
1602                 });
1603     }
1604 
1605     private static interface SigComparator<T, S extends IDelta<? extends T>> {
1606         boolean considerEqualElement(T from, T to);
1607 
1608         S createChangedDelta(T from, T to);
1609 
1610         /**
1611          * If null is returned, it will be ignored.
1612          */
1613         S createAddRemoveDelta(T from, T to);
1614     }
1615 
1616 
1617     private <T, S extends IDelta<? extends T>> Set<S> compareSets(Set<T> from,
1618             Set<T> to, SigComparator<T, S> comparator) {
1619 
1620         Set<T> toCopy = new HashSet<T>(to);
1621         Set<S> deltas = new HashSet<S>();
1622 
1623         for (T fromType : from) {
1624             Iterator<T> toIterator = toCopy.iterator();
1625             boolean equals = false;
1626             boolean hasNext = toIterator.hasNext();
1627 
1628             while (hasNext && !equals) {
1629                 T toElement = toIterator.next();
1630                 equals = comparator.considerEqualElement(fromType, toElement);
1631                 if (equals) {
1632                     S compare = comparator.createChangedDelta(fromType,
1633                             toElement);
1634                     if (compare != null) {
1635                         deltas.add(compare);
1636                     }
1637                 }
1638                 hasNext = toIterator.hasNext();
1639             }
1640 
1641             if (equals) {
1642                 toIterator.remove();
1643             } else {
1644                 S delta = comparator.createAddRemoveDelta(fromType, null);
1645                 if (delta != null) {
1646                     deltas.add(delta);
1647                 }
1648             }
1649         }
1650 
1651         for (T type : toCopy) {
1652             S delta = comparator.createAddRemoveDelta(null, type);
1653             if (delta != null) {
1654                 deltas.add(delta);
1655             }
1656         }
1657         return deltas.isEmpty() ? null : deltas;
1658     }
1659 
1660 
1661     private ITypeReferenceDelta<?> compareArrayType(IArrayType from,
1662             IArrayType to) {
1663         ITypeReferenceDelta<?> componentTypeDelta = compareType(from
1664                 .getComponentType(), to.getComponentType(), false);
1665         if (componentTypeDelta != null) {
1666             SigArrayTypeDelta delta = new SigArrayTypeDelta(from, to);
1667             delta.setComponentTypeDelta(componentTypeDelta);
1668             return delta;
1669         }
1670         return null;
1671     }
1672 
1673     private ITypeReferenceDelta<IClassReference> compareClassReference(
1674             IClassReference fromRef, IClassReference toRef) {
1675         IClassDefinition from = fromRef.getClassDefinition();
1676         IClassDefinition to = toRef.getClassDefinition();
1677 
1678         if (!sameClassDefinition(from, to)) {
1679             return new SigClassReferenceDelta(fromRef, toRef);
1680         }
1681         return null;
1682     }
1683 
1684 
1685     private boolean sameClassDefinition(IClassDefinition from,
1686             IClassDefinition to) {
1687         boolean sameName = from.getName().equals(to.getName());
1688         boolean samePackage = from.getPackageName().equals(to.getPackageName());
1689 
1690         Kind fromKind = from.getKind();
1691         Kind toKind = to.getKind();
1692         boolean sameKind = (fromKind == null || toKind == null)
1693                 || fromKind.equals(toKind);
1694 
1695         return sameName && samePackage && sameKind;
1696     }
1697 
1698     private IPrimitiveTypeDelta comparePrimitiveType(IPrimitiveType from,
1699             IPrimitiveType to) {
1700         if (!from.equals(to)) {
1701             return new SigPrimitiveTypeDelta(from, to);
1702         }
1703         return null;
1704     }
1705 }
1706