1 /*
<lambda>null2 * Copyright (C) 2017 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 com.android.tools.metalava
18
19 import com.android.tools.metalava.model.CallableItem
20 import com.android.tools.metalava.model.ClassItem
21 import com.android.tools.metalava.model.Codebase
22 import com.android.tools.metalava.model.ConstructorItem
23 import com.android.tools.metalava.model.FieldItem
24 import com.android.tools.metalava.model.FilterPredicate
25 import com.android.tools.metalava.model.Item
26 import com.android.tools.metalava.model.MergedCodebase
27 import com.android.tools.metalava.model.MethodItem
28 import com.android.tools.metalava.model.PackageItem
29 import com.android.tools.metalava.model.ParameterItem
30 import com.android.tools.metalava.model.PropertyItem
31 import com.android.tools.metalava.model.SelectableItem
32 import com.android.tools.metalava.model.visitors.ApiFilters
33 import com.android.tools.metalava.model.visitors.ApiVisitor
34
35 /**
36 * Visitor which visits all items in two matching codebases and matches up the items and invokes
37 * [compareItems] on each pair, or [addedItem] or [removedItem] when items are not matched
38 */
39 open class ComparisonVisitor {
40 open fun compareItems(old: Item, new: Item) {}
41
42 open fun addedItem(new: SelectableItem) {}
43
44 open fun removedItem(old: SelectableItem, from: SelectableItem?) {}
45
46 open fun comparePackageItems(old: PackageItem, new: PackageItem) {}
47
48 open fun compareClassItems(old: ClassItem, new: ClassItem) {}
49
50 open fun compareCallableItems(old: CallableItem, new: CallableItem) {}
51
52 open fun compareConstructorItems(old: ConstructorItem, new: ConstructorItem) {}
53
54 open fun compareMethodItems(old: MethodItem, new: MethodItem) {}
55
56 open fun compareFieldItems(old: FieldItem, new: FieldItem) {}
57
58 open fun comparePropertyItems(old: PropertyItem, new: PropertyItem) {}
59
60 open fun compareParameterItems(old: ParameterItem, new: ParameterItem) {}
61
62 open fun addedPackageItem(new: PackageItem) {}
63
64 open fun addedClassItem(new: ClassItem) {}
65
66 open fun addedCallableItem(new: CallableItem) {}
67
68 open fun addedConstructorItem(new: ConstructorItem) {}
69
70 open fun addedMethodItem(new: MethodItem) {}
71
72 open fun addedFieldItem(new: FieldItem) {}
73
74 open fun addedPropertyItem(new: PropertyItem) {}
75
76 open fun removedPackageItem(old: PackageItem, from: PackageItem?) {}
77
78 open fun removedClassItem(old: ClassItem, from: SelectableItem) {}
79
80 open fun removedCallableItem(old: CallableItem, from: ClassItem) {}
81
82 open fun removedConstructorItem(old: ConstructorItem, from: ClassItem) {}
83
84 open fun removedMethodItem(old: MethodItem, from: ClassItem) {}
85
86 open fun removedFieldItem(old: FieldItem, from: ClassItem) {}
87
88 open fun removedPropertyItem(old: PropertyItem, from: ClassItem) {}
89 }
90
91 /** Simple stack type built on top of an [ArrayList]. */
92 private typealias Stack<E> = ArrayList<E>
93
pushnull94 private fun <E> Stack<E>.push(e: E) {
95 add(e)
96 }
97
popnull98 private fun <E> Stack<E>.pop(): E = removeAt(lastIndex)
99
100 private fun <E> Stack<E>.peek(): E = last()
101
102 class CodebaseComparator {
103 /**
104 * Visits this codebase and compares it with another codebase, informing the visitors about the
105 * correlations and differences that it finds
106 */
107 fun compare(
108 visitor: ComparisonVisitor,
109 old: Codebase,
110 new: Codebase,
111 filter: FilterPredicate? = null
112 ) {
113 // Algorithm: build up two trees (by nesting level); then visit the
114 // two trees
115 val oldTree = createTree(old, filter)
116 val newTree = createTree(new, filter)
117
118 /* Debugging:
119 println("Old:\n${ItemTree.prettyPrint(oldTree)}")
120 println("New:\n${ItemTree.prettyPrint(newTree)}")
121 */
122
123 compare(visitor, oldTree, newTree, null, null, filter)
124 }
125
126 fun compare(
127 visitor: ComparisonVisitor,
128 old: MergedCodebase,
129 new: MergedCodebase,
130 filter: FilterPredicate? = null
131 ) {
132 // Algorithm: build up two trees (by nesting level); then visit the
133 // two trees
134 val oldTree = createTree(old, filter)
135 val newTree = createTree(new, filter)
136
137 /* Debugging:
138 println("Old:\n${ItemTree.prettyPrint(oldTree)}")
139 println("New:\n${ItemTree.prettyPrint(newTree)}")
140 */
141
142 compare(visitor, oldTree, newTree, null, null, filter)
143 }
144
145 private fun compare(
146 visitor: ComparisonVisitor,
147 oldList: List<ItemTree>,
148 newList: List<ItemTree>,
149 newParent: SelectableItem?,
150 oldParent: SelectableItem?,
151 filter: FilterPredicate?
152 ) {
153 // Debugging tip: You can print out a tree like this: ItemTree.prettyPrint(list)
154 var index1 = 0
155 var index2 = 0
156 val length1 = oldList.size
157 val length2 = newList.size
158
159 while (true) {
160 if (index1 < length1) {
161 if (index2 < length2) {
162 // Compare the items
163 val oldTree = oldList[index1]
164 val newTree = newList[index2]
165 val old = oldTree.item()
166 val new = newTree.item()
167
168 val compare = compare(old, new)
169 when {
170 compare > 0 -> {
171 index2++
172 if (new.emit) {
173 dispatchToAddedOrCompareIfItemWasMoved(
174 new,
175 oldParent,
176 visitor,
177 )
178 }
179 }
180 compare < 0 -> {
181 index1++
182 if (old.emit) {
183 dispatchToRemovedOrCompareIfItemWasMoved(
184 old,
185 visitor,
186 newParent,
187 filter,
188 )
189 }
190 }
191 else -> {
192 if (new.emit) {
193 if (old.emit) {
194 dispatchToCompare(visitor, old, new)
195 } else {
196 dispatchToAddedOrCompareIfItemWasMoved(
197 new,
198 oldParent,
199 visitor,
200 )
201 }
202 } else {
203 if (old.emit) {
204 dispatchToRemovedOrCompareIfItemWasMoved(
205 old,
206 visitor,
207 newParent,
208 filter,
209 )
210 }
211 }
212
213 // Compare the children (recurse)
214 compare(
215 visitor,
216 oldTree.children,
217 newTree.children,
218 newTree.item(),
219 oldTree.item(),
220 filter
221 )
222
223 index1++
224 index2++
225 }
226 }
227 } else {
228 // All the remaining items in oldList have been deleted
229 while (index1 < length1) {
230 val oldTree = oldList[index1++]
231 val old = oldTree.item()
232 dispatchToRemovedOrCompareIfItemWasMoved(
233 old,
234 visitor,
235 newParent,
236 filter,
237 )
238 }
239 }
240 } else if (index2 < length2) {
241 // All the remaining items in newList have been added
242 while (index2 < length2) {
243 val newTree = newList[index2++]
244 val new = newTree.item()
245
246 dispatchToAddedOrCompareIfItemWasMoved(new, oldParent, visitor)
247 }
248 } else {
249 break
250 }
251 }
252 }
253
254 /**
255 * Dispatch calls to [ComparisonVisitor.compareParameterItems] for each pair of [ParameterItem]s
256 * in [oldParameters] and [newParameters].
257 *
258 * The [oldParameters] and [newParameters] are guaranteed to have the same number of parameters
259 * as they come from two [MethodItem]s that compare equal according to [comparator].
260 */
261 private fun dispatchCompareParameters(
262 visitor: ComparisonVisitor,
263 oldParameters: List<ParameterItem>,
264 newParameters: List<ParameterItem>,
265 ) {
266 require(oldParameters.size == newParameters.size)
267 for ((oldParameter, newParameter) in oldParameters.zip(newParameters)) {
268 visitor.compareItems(oldParameter, newParameter)
269 visitor.compareParameterItems(oldParameter, newParameter)
270 }
271 }
272
273 /**
274 * Checks to see whether [new] has actually been added or if it was just moved from elsewhere
275 * and dispatch to the appropriate method.
276 */
277 private fun dispatchToAddedOrCompareIfItemWasMoved(
278 new: SelectableItem,
279 oldParent: SelectableItem?,
280 visitor: ComparisonVisitor,
281 ) {
282 // If it's a method, we may not have added a new method,
283 // we may simply have inherited it previously and overriding
284 // it now (or in the case of signature files, identical overrides
285 // are not explicitly listed and therefore not added to the model)
286 val inherited =
287 if (new is MethodItem && oldParent is ClassItem) {
288 oldParent
289 .findMethod(
290 template = new,
291 includeSuperClasses = true,
292 includeInterfaces = true
293 )
294 ?.duplicate(oldParent)
295 } else {
296 null
297 }
298
299 if (inherited != null) {
300 dispatchToCompare(visitor, inherited, new)
301 } else {
302 dispatchToAdded(visitor, new)
303 }
304 }
305
306 /** Dispatch to the [Item] specific `added(...)` method. */
307 private fun dispatchToAdded(visitor: ComparisonVisitor, item: SelectableItem) {
308 visitor.addedItem(item)
309
310 if (item is CallableItem) {
311 visitor.addedCallableItem(item)
312 }
313
314 when (item) {
315 is PackageItem -> visitor.addedPackageItem(item)
316 is ClassItem -> visitor.addedClassItem(item)
317 is ConstructorItem -> visitor.addedConstructorItem(item)
318 is MethodItem -> visitor.addedMethodItem(item)
319 is FieldItem -> visitor.addedFieldItem(item)
320 is PropertyItem -> visitor.addedPropertyItem(item)
321 else -> error("unexpected addition of $item")
322 }
323 }
324
325 /**
326 * Checks to see whether [old] has actually been removed or if it was just moved from elsewhere
327 * and dispatch to the appropriate method.
328 */
329 private fun dispatchToRemovedOrCompareIfItemWasMoved(
330 old: SelectableItem,
331 visitor: ComparisonVisitor,
332 newParent: SelectableItem?,
333 filter: FilterPredicate?
334 ) {
335 // If it's a method, we may not have removed the method, we may have simply
336 // removed an override and are now inheriting the method from a superclass.
337 // Alternatively, it may have always truly been an inherited method, but if the base
338 // class was hidden then the signature file may have listed the method as being
339 // declared on the subclass
340 val inheritedMethod =
341 if (old is MethodItem && newParent is ClassItem) {
342 val superMethod = newParent.findPredicateMethodWithSuper(old, filter)
343
344 if (superMethod != null && (filter == null || filter.test(superMethod))) {
345 superMethod.duplicate(newParent)
346 } else {
347 null
348 }
349 } else {
350 null
351 }
352
353 if (inheritedMethod != null) {
354 dispatchToCompare(visitor, old, inheritedMethod)
355 return
356 }
357
358 // fields may also be moved to superclasses like methods may
359 val inheritedField =
360 if (old is FieldItem && newParent is ClassItem) {
361 val superField =
362 newParent.findField(
363 fieldName = old.name(),
364 includeSuperClasses = true,
365 includeInterfaces = true
366 )
367
368 if (superField != null && (filter == null || filter.test(superField))) {
369 superField.duplicate(newParent)
370 } else {
371 null
372 }
373 } else {
374 null
375 }
376
377 if (inheritedField != null) {
378 dispatchToCompare(visitor, old, inheritedField)
379 return
380 }
381 dispatchToRemoved(visitor, old, newParent)
382 }
383
384 /** Dispatch to the [Item] specific `removed(...)` method. */
385 private fun dispatchToRemoved(
386 visitor: ComparisonVisitor,
387 item: SelectableItem,
388 from: SelectableItem?
389 ) {
390 visitor.removedItem(item, from)
391
392 if (item is CallableItem) {
393 visitor.removedCallableItem(item, from as ClassItem)
394 }
395
396 when (item) {
397 is PackageItem -> visitor.removedPackageItem(item, from as PackageItem?)
398 is ClassItem -> visitor.removedClassItem(item, from as SelectableItem)
399 is ConstructorItem -> visitor.removedConstructorItem(item, from as ClassItem)
400 is MethodItem -> visitor.removedMethodItem(item, from as ClassItem)
401 is FieldItem -> visitor.removedFieldItem(item, from as ClassItem)
402 is PropertyItem -> visitor.removedPropertyItem(item, from as ClassItem)
403 else -> error("unexpected removal of $item")
404 }
405 }
406
407 /** Dispatch to the [Item] specific `compare(...)` method. */
408 private fun dispatchToCompare(
409 visitor: ComparisonVisitor,
410 old: SelectableItem,
411 new: SelectableItem
412 ) {
413 visitor.compareItems(old, new)
414
415 if (old is CallableItem) {
416 visitor.compareCallableItems(old, new as CallableItem)
417 }
418
419 when (old) {
420 is PackageItem -> visitor.comparePackageItems(old, new as PackageItem)
421 is ClassItem -> visitor.compareClassItems(old, new as ClassItem)
422 is ConstructorItem -> visitor.compareConstructorItems(old, new as ConstructorItem)
423 is MethodItem -> visitor.compareMethodItems(old, new as MethodItem)
424 is FieldItem -> visitor.compareFieldItems(old, new as FieldItem)
425 is PropertyItem -> visitor.comparePropertyItems(old, new as PropertyItem)
426 else -> error("unexpected comparison of $old and $new")
427 }
428
429 // If this is comparing two [CallableItem]s then compare their [ParameterItem]s too.
430 if (old is CallableItem) {
431 dispatchCompareParameters(visitor, old.parameters(), (new as CallableItem).parameters())
432 }
433 }
434
435 private fun compare(item1: SelectableItem, item2: SelectableItem): Int =
436 comparator.compare(item1, item2)
437
438 companion object {
439 /** Sorting rank for types */
440 private fun typeRank(item: Item): Int {
441 return when (item) {
442 is PackageItem -> 0
443 is ConstructorItem -> 1
444 is MethodItem -> 2
445 is FieldItem -> 3
446 is ClassItem -> 4
447 is PropertyItem -> 5
448 else -> error("Unexpected item $item of ${item.javaClass}")
449 }
450 }
451
452 val comparator: Comparator<SelectableItem> = Comparator { item1, item2 ->
453 val typeSort = typeRank(item1) - typeRank(item2)
454 when {
455 typeSort != 0 -> typeSort
456 item1 == item2 -> 0
457 else ->
458 when (item1) {
459 is PackageItem -> {
460 item1.qualifiedName().compareTo((item2 as PackageItem).qualifiedName())
461 }
462 is ClassItem -> {
463 item1.qualifiedName().compareTo((item2 as ClassItem).qualifiedName())
464 }
465 is CallableItem -> {
466 // Try to incrementally match aspects of the method until you can
467 // conclude
468 // whether they are the same or different.
469 // delta is 0 when the methods are the same, else not 0
470 // Start by comparing the names
471 var delta = item1.name().compareTo((item2 as CallableItem).name())
472 if (delta == 0) {
473 // If the names are the same then compare the number of parameters
474 val parameters1 = item1.parameters()
475 val parameters2 = item2.parameters()
476 val parameterCount1 = parameters1.size
477 val parameterCount2 = parameters2.size
478 delta = parameterCount1 - parameterCount2
479 if (delta == 0) {
480 // If the parameter count is the same, compare the parameter
481 // types
482 for (i in 0 until parameterCount1) {
483 val parameter1 = parameters1[i]
484 val parameter2 = parameters2[i]
485 val type1 = parameter1.type().toTypeString()
486 val type2 = parameter2.type().toTypeString()
487 delta = type1.compareTo(type2)
488 if (delta != 0) {
489 // If the parameter types aren't the same, try a little
490 // harder:
491 // (1) treat varargs and arrays the same, and
492 // (2) drop java.lang. prefixes from comparisons in
493 // wildcard
494 // signatures since older signature files may have
495 // removed
496 // those
497 val simpleType1 = parameter1.type().toCanonicalType()
498 val simpleType2 = parameter2.type().toCanonicalType()
499 delta = simpleType1.compareTo(simpleType2)
500 if (delta != 0) {
501 // If still not the same, check the special case for
502 // Kotlin coroutines: It's possible one has
503 // "experimental"
504 // when fully qualified while the other does not.
505 // We treat these the same, so strip the prefix and
506 // strip
507 // "experimental", then compare.
508 if (
509 simpleType1.startsWith("kotlin.coroutines.") &&
510 simpleType2.startsWith("kotlin.coroutines.")
511 ) {
512 val t1 =
513 simpleType1
514 .removePrefix("kotlin.coroutines.")
515 .removePrefix("experimental.")
516 val t2 =
517 simpleType2
518 .removePrefix("kotlin.coroutines.")
519 .removePrefix("experimental.")
520 delta = t1.compareTo(t2)
521 if (delta != 0) {
522 // They're not the same
523 break
524 }
525 } else {
526 // They're not the same
527 break
528 }
529 }
530 }
531 }
532 }
533 }
534 // The method names are different, return the result of the compareTo
535 delta
536 }
537 is FieldItem -> {
538 item1.name().compareTo((item2 as FieldItem).name())
539 }
540 is PropertyItem -> {
541 item1.name().compareTo((item2 as PropertyItem).name())
542 }
543 else -> error("Unexpected item $item1 of ${item1.javaClass}")
544 }
545 }
546 }
547
548 val treeComparator: Comparator<ItemTree> = Comparator { item1, item2 ->
549 comparator.compare(item1.item, item2.item())
550 }
551 }
552
553 private fun ensureSorted(item: ItemTree) {
554 item.children.sortWith(treeComparator)
555 for (child in item.children) {
556 ensureSorted(child)
557 }
558 }
559
560 /**
561 * Sorts and removes duplicate items. The kept item will be an unhidden item if possible. Ties
562 * are broken in favor of keeping children having lower indices
563 */
564 private fun removeDuplicates(item: ItemTree) {
565 item.children.sortWith(treeComparator)
566 val children = item.children
567 var i = children.count() - 2
568 while (i >= 0) {
569 val child = children[i]
570 val prev = children[i + 1]
571 if (comparator.compare(child.item, prev.item) == 0) {
572 if (prev.item!!.emit && !child.item!!.emit) {
573 // merge child into prev because prev is emitted
574 val prevChildren = prev.children.toList()
575 prev.children.clear()
576 prev.children += child.children
577 prev.children += prevChildren
578 children.removeAt(i)
579 } else {
580 // merge prev into child because child was specified first
581 child.children += prev.children
582 children.removeAt(i + 1)
583 }
584 }
585 i--
586 }
587 for (child in children) {
588 removeDuplicates(child)
589 }
590 }
591
592 private fun createTree(
593 codebase: MergedCodebase,
594 filter: FilterPredicate? = null
595 ): List<ItemTree> {
596 return createTree(codebase.children, filter)
597 }
598
599 private fun createTree(codebase: Codebase, filter: FilterPredicate? = null): List<ItemTree> {
600 return createTree(listOf(codebase), filter)
601 }
602
603 private fun createTree(
604 codebases: List<Codebase>,
605 filter: FilterPredicate? = null
606 ): List<ItemTree> {
607 val stack = Stack<ItemTree>()
608 val root = ItemTree(null)
609 stack.push(root)
610
611 for (codebase in codebases) {
612 val acceptAll = codebase.preFiltered || filter == null
613 val predicate = if (acceptAll) FilterPredicate { true } else filter!!
614 val apiFilters = ApiFilters(emit = predicate, reference = predicate)
615 codebase.accept(
616 object :
617 ApiVisitor(
618 preserveClassNesting = true,
619 // Do not visit [ParameterItem]s, as they will be compared in
620 // [dispatchToCompare].
621 visitParameterItems = false,
622 inlineInheritedFields = true,
623 apiFilters = apiFilters,
624 // Whenever a caller passes arguments of "--show-annotation 'SomeAnnotation'
625 // --check-compatibility:api:released $oldApi",
626 // really what they mean is:
627 // 1. Definitions:
628 // 1.1 Define the SomeAnnotation API as the set of APIs that are either
629 // public or are annotated with @SomeAnnotation
630 // 1.2 $oldApi was previously the difference between the SomeAnnotation api
631 // and the public api
632 // 2. The caller would like Metalava to verify that all APIs that are known
633 // to have previously been part of the SomeAnnotation api remain part of the
634 // SomeAnnotation api
635 // So, when doing compatibility checking we want to consider public APIs
636 // even if the caller didn't explicitly pass --show-unannotated
637 showUnannotated = true,
638 ) {
639
640 /**
641 * Construct an [ItemTree] for [item] and push it onto the stack.
642 *
643 * This will not be called for [ParameterItem]s as it is not a [SelectableItem]
644 * and they are compared when comparing callables in [dispatchToCompare].
645 */
646 override fun visitSelectableItem(item: SelectableItem) {
647 val node = ItemTree(item)
648 val parent = stack.peek()
649 parent.children += node
650
651 stack.push(node)
652 }
653
654 override fun include(cls: ClassItem): Boolean =
655 if (acceptAll) true else super.include(cls)
656
657 /**
658 * Pop the [ItemTree] for [item] constructed in [visitSelectableItem] off the
659 * stack.
660 *
661 * This will not be called for [ParameterItem]s as it is not a [SelectableItem]
662 * and they are compared when comparing callables in [dispatchToCompare].
663 */
664 override fun afterVisitSelectableItem(item: SelectableItem) {
665 stack.pop()
666 }
667 }
668 )
669 }
670
671 if (codebases.count() >= 2) {
672 removeDuplicates(root)
673 // removeDuplicates will also sort the items
674 } else {
675 ensureSorted(root)
676 }
677
678 return root.children
679 }
680
681 data class ItemTree(val item: SelectableItem?) : Comparable<ItemTree> {
682 val children: MutableList<ItemTree> = mutableListOf()
683
684 fun item(): SelectableItem =
685 item!! // Only the root note can be null, and this method should never be called on it
686
687 override fun compareTo(other: ItemTree): Int {
688 return comparator.compare(item(), other.item())
689 }
690
691 override fun toString(): String {
692 return item.toString()
693 }
694
695 @Suppress("unused") // Left for debugging
696 fun prettyPrint(): String {
697 val sb = StringBuilder(1000)
698 prettyPrint(sb, 0)
699 return sb.toString()
700 }
701
702 private fun prettyPrint(sb: StringBuilder, depth: Int) {
703 for (i in 0 until depth) {
704 sb.append(" ")
705 }
706 sb.append(toString())
707 sb.append('\n')
708 for (child in children) {
709 child.prettyPrint(sb, depth + 1)
710 }
711 }
712
713 companion object {
714 @Suppress("unused") // Left for debugging
715 fun prettyPrint(list: List<ItemTree>): String {
716 val sb = StringBuilder(1000)
717 for (child in list) {
718 child.prettyPrint(sb, 0)
719 }
720 return sb.toString()
721 }
722 }
723 }
724 }
725