Sort divergent elements deterministically (#2846)

Fixes #2784

2 files changed, 316 insertions, 55 deletions

diff --git a/plugins/base/src/main/kotlin/translators/documentables/DefaultPageCreator.kt b/plugins/base/src/main/kotlin/translators/documentables/DefaultPageCreator.kt
index b8bf87a4..25f3c450 100644
--- a/plugins/base/src/main/kotlin/translators/documentables/DefaultPageCreator.kt
+++ b/plugins/base/src/main/kotlin/translators/documentables/DefaultPageCreator.kt
@@ -9,6 +9,7 @@ import org.jetbrains.dokka.base.transformers.documentables.ClashingDriIdentifier
 import org.jetbrains.dokka.base.transformers.pages.comments.CommentsToContentConverter
 import org.jetbrains.dokka.base.transformers.pages.tags.CustomTagContentProvider
 import org.jetbrains.dokka.base.translators.documentables.PageContentBuilder.DocumentableContentBuilder
+import org.jetbrains.dokka.links.Callable
 import org.jetbrains.dokka.links.DRI
 import org.jetbrains.dokka.model.*
 import org.jetbrains.dokka.model.doc.*
@@ -524,30 +525,31 @@ open class DefaultPageCreator(
                     .groupBy { it.name } // This groupBy should probably use LocationProvider
                     // This hacks displaying actual typealias signatures along classlike ones
                     .mapValues { if (it.value.any { it is DClasslike }) it.value.filter { it !is DTypeAlias } else it.value }
-                    .toSortedMap(compareBy(nullsLast(String.CASE_INSENSITIVE_ORDER)) { it })
+                    .entries.sortedBy { it.key }
                     .forEach { (elementName, elements) -> // This groupBy should probably use LocationProvider
+                        val sortedElements = sortDivergentElementsDeterministically(elements)
                         row(
-                            dri = elements.map { it.dri }.toSet(),
-                            sourceSets = elements.flatMap { it.sourceSets }.toSet(),
+                            dri = sortedElements.map { it.dri }.toSet(),
+                            sourceSets = sortedElements.flatMap { it.sourceSets }.toSet(),
                             kind = kind,
                             styles = emptySet(),
                             extra = elementName?.let { name -> extra + SymbolAnchorHint(name, kind) } ?: extra
                         ) {
                             link(
                                 text = elementName.orEmpty(),
-                                address = elements.first().dri,
+                                address = sortedElements.first().dri,
                                 kind = kind,
                                 styles = setOf(ContentStyle.RowTitle),
-                                sourceSets = elements.sourceSets.toSet(),
+                                sourceSets = sortedElements.sourceSets.toSet(),
                                 extra = extra
                             )
                             divergentGroup(
                                 ContentDivergentGroup.GroupID(name),
-                                elements.map { it.dri }.toSet(),
+                                sortedElements.map { it.dri }.toSet(),
                                 kind = kind,
                                 extra = extra
                             ) {
-                                elements.map {
+                                sortedElements.map {
                                     instance(
                                         setOf(it.dri),
                                         it.sourceSets.toSet(),
@@ -571,6 +573,26 @@ open class DefaultPageCreator(
         }
     }
 
+    /**
+     * Divergent elements, such as extensions for the same receiver, can have identical signatures
+     * if they are declared in different places. If such elements are shown on the same page together,
+     * they need to be rendered deterministically to have reproducible builds.
+     *
+     * For example, you can have three identical extensions, if they are declared as:
+     * 1) top-level in package A
+     * 2) top-level in package B
+     * 3) inside a companion object in package A/B
+     *
+     * @see divergentBlock
+     *
+     * @param elements can contain types (annotation/class/interface/object/typealias), functions and properties
+     * @return the original list if it has one or zero elements
+     */
+    private fun sortDivergentElementsDeterministically(elements: List<Documentable>): List<Documentable> =
+        elements.takeIf { it.size > 1 } // the majority are single-element lists, but no real benchmarks done
+            ?.sortedWith(divergentDocumentableComparator)
+            ?: elements
+
     private fun DocumentableContentBuilder.contentForCustomTagsBrief(documentable: Documentable) {
         val customTags = documentable.customTags
         if (customTags.isEmpty()) return
@@ -611,6 +633,19 @@ internal val Documentable.customTags: Map<String, SourceSetDependent<CustomTagWr
 private val Documentable.hasSeparatePage: Boolean
     get() = this !is DTypeAlias
 
+/**
+ * @see DefaultPageCreator.sortDivergentElementsDeterministically for usage
+ */
+private val divergentDocumentableComparator =
+    compareBy<Documentable, String?>(nullsLast()) { it.dri.packageName }
+        .thenBy(nullsFirst()) { it.dri.classNames } // nullsFirst for top level to be first
+        .thenBy(
+            nullsLast(
+                compareBy<Callable> { it.params.size }
+                    .thenBy { it.signature() }
+            )
+        ) { it.dri.callable }
+
 @Suppress("UNCHECKED_CAST")
 private fun <T : Documentable> T.nameAfterClash(): String =
     ((this as? WithExtraProperties<out Documentable>)?.extra?.get(DriClashAwareName)?.value ?: name).orEmpty()
@@ -624,4 +659,4 @@ internal inline fun <reified T : NamedTagWrapper> GroupedTags.withTypeNamed(): M
     (this[T::class] as List<Pair<DokkaSourceSet, T>>?)
         ?.groupByTo(linkedMapOf()) { it.second.name }
         ?.mapValues { (_, v) -> v.toMap() }
-        .orEmpty()
\ No newline at end of file
+        .orEmpty()
diff --git a/plugins/base/src/test/kotlin/pageMerger/PageNodeMergerTest.kt b/plugins/base/src/test/kotlin/pageMerger/PageNodeMergerTest.kt
index 46b13763..05ff55ee 100644
--- a/plugins/base/src/test/kotlin/pageMerger/PageNodeMergerTest.kt
+++ b/plugins/base/src/test/kotlin/pageMerger/PageNodeMergerTest.kt
@@ -1,52 +1,28 @@
 package pageMerger
 
-import org.jetbrains.dokka.pages.ClasslikePageNode
-import org.jetbrains.dokka.pages.ContentPage
-import org.jetbrains.dokka.pages.PageNode
 import org.junit.jupiter.api.Assertions.assertTrue
 import org.junit.jupiter.api.Disabled
 import org.junit.jupiter.api.Test
 import org.jetbrains.dokka.base.testApi.testRunner.BaseAbstractTest
+import org.jetbrains.dokka.model.dfs
+import org.jetbrains.dokka.model.withDescendants
+import org.jetbrains.dokka.pages.*
+import org.junit.jupiter.api.RepeatedTest
+import java.lang.IllegalArgumentException
+import kotlin.test.assertEquals
 
 class PageNodeMergerTest : BaseAbstractTest() {
 
-    /* object SameNameStrategy : DokkaPlugin() {
-        val strategy by extending { CoreExtensions.pageMergerStrategy with SameMethodNamePageMergerStrategy }
-    }
-
-    class DefaultStrategy(val strList: MutableList<String> = mutableListOf()) : DokkaPlugin(), DokkaLogger {
-        val strategy by extending { CoreExtensions.pageMergerStrategy with DefaultPageMergerStrategy(this@DefaultStrategy) }
-
-        override var warningsCount: Int = 0
-        override var errorsCount: Int = 0
-
-        override fun debug(message: String) = TODO()
-
-        override fun info(message: String) = TODO()
-
-        override fun progress(message: String) = TODO()
-
-        override fun warn(message: String) {
-            strList += message
+    private val defaultConfiguration = dokkaConfiguration {
+        sourceSets {
+            sourceSet {
+                sourceRoots = listOf("src/main/kotlin")
+            }
         }
-
-        override fun error(message: String) = TODO()
-
-        override fun report() = TODO()
     }
-     */
 
     @Test
     fun sameNameStrategyTest() {
-
-        val configuration = dokkaConfiguration {
-            sourceSets {
-                sourceSet {
-                    sourceRoots = listOf("src/main/kotlin/pageMerger/Test.kt")
-                }
-            }
-        }
-
         testInline(
             """
             |/src/main/kotlin/pageMerger/Test.kt
@@ -60,8 +36,7 @@ class PageNodeMergerTest : BaseAbstractTest() {
             |   fun test(str: String): String = str
             |}
         """.trimMargin(),
-            configuration/*,
-            pluginOverrides = listOf(SameNameStrategy)*/
+            defaultConfiguration
         ) {
             pagesTransformationStage = {
                 val allChildren = it.childrenRec().filterIsInstance<ContentPage>()
@@ -82,14 +57,6 @@ class PageNodeMergerTest : BaseAbstractTest() {
     fun defaultStrategyTest() {
         val strList: MutableList<String> = mutableListOf()
 
-        val configuration = dokkaConfiguration {
-            sourceSets {
-                sourceSet {
-                    sourceRoots = listOf("src/main/kotlin/pageMerger/Test.kt")
-                }
-            }
-        }
-
         testInline(
             """
             |/src/main/kotlin/pageMerger/Test.kt
@@ -103,8 +70,7 @@ class PageNodeMergerTest : BaseAbstractTest() {
             |   fun test(str: String): String = str
             |}
         """.trimMargin(),
-            configuration/*,
-            pluginOverrides = listOf(DefaultStrategy(strList)) */
+            defaultConfiguration
         ) {
             pagesTransformationStage = { root ->
                 val allChildren = root.childrenRec().filterIsInstance<ContentPage>()
@@ -187,4 +153,264 @@ class PageNodeMergerTest : BaseAbstractTest() {
             }
         }
     }
+
+    @RepeatedTest(3)
+    fun `should deterministically render same name property extensions`() {
+        testInline(
+            """
+            |/src/main/kotlin/test/Test.kt
+            |package test
+            |
+            |class ExtensionReceiver
+            |
+            |/**
+            | * Top level val extension
+            | */
+            |val ExtensionReceiver.foo: String get() = "bar"
+            |
+            |class Obj {
+            |    companion object {
+            |        /**
+            |         * Companion val extension
+            |         */
+            |        val ExtensionReceiver.foo: String get() = "bar"
+            |    }
+            |}
+            |
+            |/src/main/kotlin/test/nestedpackage/Pckg.kt
+            |package test.nestedpackage
+            |
+            |import test.ExtensionReceiver
+            |
+            |/**
+            | * From nested package int val extension
+            | */
+            |val ExtensionReceiver.foo: Int get() = 42
+        """.trimMargin(),
+            defaultConfiguration
+        ) {
+            renderingStage = { rootPageNode, _ ->
+                val extensions = rootPageNode.findExtensionsOfClass("ExtensionReceiver")
+
+                extensions.assertContainsKDocsInOrder(
+                    "Top level val extension",
+                    "Companion val extension",
+                    "From nested package int val extension"
+                )
+            }
+        }
+    }
+
+    @RepeatedTest(3)
+    fun `should deterministically render parameterless same name function extensions`() {
+        testInline(
+            """
+            |/src/main/kotlin/test/Test.kt
+            |package test
+            |
+            |class ExtensionReceiver
+            |
+            |/**
+            | * Top level fun extension
+            | */
+            |fun ExtensionReceiver.bar(): String = "bar"
+            |
+            |class Obj {
+            |
+            |    companion object {
+            |        /**
+            |         * Companion fun extension
+            |         */
+            |        fun ExtensionReceiver.bar(): String = "bar"
+            |    }
+            |}
+            |
+            |/src/main/kotlin/test/nestedpackage/Pckg.kt
+            |package test.nestedpackage
+            |
+            |import test.ExtensionReceiver
+            |
+            |/**
+            | * From nested package fun extension
+            | */
+            |fun ExtensionReceiver.bar(): String = "bar"
+        """.trimMargin(),
+            defaultConfiguration
+        ) {
+            renderingStage = { rootPageNode, _ ->
+                val extensions = rootPageNode.findExtensionsOfClass("ExtensionReceiver")
+                extensions.assertContainsKDocsInOrder(
+                    "Top level fun extension",
+                    "Companion fun extension",
+                    "From nested package fun extension"
+                )
+            }
+        }
+    }
+
+    @RepeatedTest(3)
+    fun `should deterministically render same name function extensions with parameters`() {
+        testInline(
+            """
+            |/src/main/kotlin/test/Test.kt
+            |package test
+            |
+            |class ExtensionReceiver
+            |
+            |/**
+            | * Top level fun extension with one string param
+            | */
+            |fun ExtensionReceiver.bar(one: String): String = "bar"
+            |
+            |/**
+            | * Top level fun extension with one int param
+            | */
+            |fun ExtensionReceiver.bar(one: Int): Int = 42
+            |
+            |class Obj {
+            |
+            |    companion object {
+            |        /**
+            |         * Companion fun extension with two params
+            |         */
+            |        fun ExtensionReceiver.bar(one: String, two: String): String = "bar"
+            |    }
+            |}
+            |
+            |/src/main/kotlin/test/nestedpackage/Pckg.kt
+            |package test.nestedpackage
+            |
+            |import test.ExtensionReceiver
+            |
+            |/**
+            | * From nested package fun extension with two params
+            | */
+            |fun ExtensionReceiver.bar(one: String, two: String): String = "bar"
+            |
+            |/**
+            | * From nested package fun extension with three params
+            | */
+            |fun ExtensionReceiver.bar(one: String, two: String, three: String): String = "bar"
+            |
+            |/**
+            | * From nested package fun extension with four params
+            | */
+            |fun ExtensionReceiver.bar(one: String, two: String, three: String, four: String): String = "bar"
+        """.trimMargin(),
+            defaultConfiguration
+        ) {
+            renderingStage = { rootPageNode, _ ->
+                val extensions = rootPageNode.findExtensionsOfClass("ExtensionReceiver")
+                extensions.assertContainsKDocsInOrder(
+                    "Top level fun extension with one int param",
+                    "Top level fun extension with one string param",
+                    "Companion fun extension with two params",
+                    "From nested package fun extension with two params",
+                    "From nested package fun extension with three params",
+                    "From nested package fun extension with four params"
+                )
+            }
+        }
+    }
+
+    @RepeatedTest(3)
+    fun `should deterministically render same name function extensions with different receiver and return type`() {
+        testInline(
+            """
+            |/src/main/kotlin/test/Test.kt
+            |package test
+            |
+            |/**
+            | * Top level fun extension string
+            | */
+            |fun Int.bar(): String = "bar"
+            |
+            |/**
+            | * Top level fun extension int
+            | */
+            |fun String.bar(): Int = 42
+        """.trimMargin(),
+            defaultConfiguration
+        ) {
+            renderingStage = { rootPageNode, _ ->
+                val packageFunctionBlocks = rootPageNode.findPackageFunctionBlocks(packageName = "test")
+                assertEquals(1, packageFunctionBlocks.size, "Expected to find only one group for the functions")
+
+                val functionsBlock = packageFunctionBlocks[0]
+                functionsBlock.assertContainsKDocsInOrder(
+                    "Top level fun extension string",
+                    "Top level fun extension int"
+                )
+            }
+        }
+    }
+
+    @Test
+    fun `should not ignore case when grouping by name`() {
+        testInline(
+            """
+            |/src/main/kotlin/test/Test.kt
+            |package test
+            |
+            |/**
+            | * Top level fun bAr
+            | */
+            |fun Int.bAr(): String = "bar"
+            |
+            |/**
+            | * Top level fun BaR
+            | */
+            |fun String.BaR(): Int = 42
+        """.trimMargin(),
+            defaultConfiguration
+        ) {
+            renderingStage = { rootPageNode, _ ->
+                val packageFunctionBlocks = rootPageNode.findPackageFunctionBlocks(packageName = "test")
+                assertEquals(2, packageFunctionBlocks.size, "Expected two separate function groups")
+
+                val firstGroup = packageFunctionBlocks[0]
+                firstGroup.assertContainsKDocsInOrder(
+                    "Top level fun BaR",
+                )
+
+                val secondGroup = packageFunctionBlocks[1]
+                secondGroup.assertContainsKDocsInOrder(
+                    "Top level fun bAr",
+                )
+            }
+        }
+    }
+
+    private fun RootPageNode.findExtensionsOfClass(name: String): ContentDivergentGroup {
+        val extensionReceiverPage = this.dfs { it is ClasslikePageNode && it.name == name } as ClasslikePageNode
+        return extensionReceiverPage.content
+            .dfs { it is ContentDivergentGroup && it.groupID.name == "Extensions" } as ContentDivergentGroup
+    }
+
+    private fun RootPageNode.findPackageFunctionBlocks(packageName: String): List<ContentDivergentGroup> {
+        val packagePage = this.dfs { it is PackagePage && it.name == packageName } as PackagePage
+        val packageFunctionTable = packagePage.content.dfs {
+            it is ContentTable && it.dci.kind == ContentKind.Functions
+        } as ContentTable
+
+        return packageFunctionTable.children.map { packageGroup ->
+            packageGroup.dfs { it is ContentDivergentGroup } as ContentDivergentGroup
+        }
+    }
+
+    private fun ContentDivergentGroup.assertContainsKDocsInOrder(vararg expectedKDocs: String) {
+        expectedKDocs.forEachIndexed { index, expectedKDoc ->
+            assertEquals(expectedKDoc, this.getElementKDocText(index))
+        }
+    }
+
+    private fun ContentDivergentGroup.getElementKDocText(index: Int): String {
+        val element = this.children.getOrNull(index) ?: throw IllegalArgumentException("No element with index $index")
+        val commentNode = element.after
+            ?.withDescendants()
+            ?.singleOrNull { it is ContentText && it.dci.kind == ContentKind.Comment }
+            ?: throw IllegalStateException("Expected the element to contain a single paragraph of text / comment")
+
+        return (commentNode as ContentText).text
+    }
 }