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