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