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