[K/N][build] Use stable input order in NativePlugin

For reproducibility it's important to give the compilers inputs
in a stable order.

This commit makes sure all inputs are sorted in NativePlugin.

^KT-81500
diff --git a/kotlin-native/Interop/Runtime/build.gradle.kts b/kotlin-native/Interop/Runtime/build.gradle.kts
index 556fd4d..d1624fa 100644
--- a/kotlin-native/Interop/Runtime/build.gradle.kts
+++ b/kotlin-native/Interop/Runtime/build.gradle.kts
@@ -9,7 +9,6 @@
 import org.jetbrains.kotlin.konan.target.HostManager
 import org.jetbrains.kotlin.konan.target.TargetWithSanitizer
 import org.jetbrains.kotlin.tools.ToolExecutionTask
-import org.jetbrains.kotlin.tools.libname
 
 plugins {
     id("org.jetbrains.kotlin.jvm")
@@ -56,17 +55,10 @@
 
     target(library, objSet) {
         tool(*hostPlatform.clangForJni.clangCXX("").toTypedArray())
-        val dynamicLibs = buildList {
-            cppLink.incoming.artifactView {
-                attributes {
-                    attribute(LibraryElements.LIBRARY_ELEMENTS_ATTRIBUTE, objects.named(LibraryElements.DYNAMIC_LIB))
-                }
-            }.files.flatMapTo(this) { listOf("-L${it.parentFile.toRelativeString(workingDir.asFile.get())}", "-l${libname(it)}") }
-        }
         flags("-shared",
-              "-o",ruleOut(), *ruleInAll(),
-              "${nativeDependencies.libffiPath}/lib/libffi.$lib",
-                *dynamicLibs.toTypedArray())
+                "-o",ruleOut(), *ruleInAll(),
+                "${nativeDependencies.libffiPath}/lib/libffi.$lib",
+                *asLinkFlags(cppLink, reproducibilityPathsMap).toTypedArray())
 
         if (HostManager.hostIsMac) {
             // Set install_name to a non-absolute path.
diff --git a/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/Utils.kt b/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/Utils.kt
index 99be525..a35ce02 100644
--- a/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/Utils.kt
+++ b/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/Utils.kt
@@ -7,13 +7,13 @@
 
 import com.google.gson.GsonBuilder
 import org.gradle.api.Project
-import org.gradle.api.Task
+import org.gradle.api.artifacts.Configuration
+import org.gradle.api.attributes.LibraryElements
 import org.gradle.api.file.FileCollection
-import org.gradle.api.plugins.ExtraPropertiesExtension
-import org.gradle.api.provider.Provider
-import org.gradle.api.tasks.TaskProvider
 import org.gradle.kotlin.dsl.*
+import org.jetbrains.kotlin.cpp.CppUsage
 import org.jetbrains.kotlin.konan.target.*
+import org.jetbrains.kotlin.tools.libname
 import java.io.File
 
 //region Project properties.
@@ -55,3 +55,63 @@
 
 internal val FileCollection.isNotEmpty: Boolean
     get() = !isEmpty
+
+/**
+ * Given a [FileCollection] and [rootsMap]: a map from directory roots to their names,
+ * return a sorted list of files.
+ *
+ * `.` is a special "default" root. All files that are under that root, or not under
+ * any root at all, will be returned as relative to the "default" root. All other files
+ * are returned as absolute files.
+ *
+ * This is useful for generating stable order of files for build reproducibility.
+ */
+fun FileCollection.stableSortedForReproducibility(rootsMap: Map<File, String>): List<File> = files.map {
+    val file = it.canonicalFile.normalize()
+    val defaultRootName = "."
+    val defaultRoot = rootsMap.entries.find { (_, rootName) -> rootName == defaultRootName }
+    checkNotNull(defaultRoot) {
+        "$rootsMap must contain a root named $defaultRootName"
+    }
+    rootsMap.firstNotNullOfOrNull { (root, rootName) ->
+        if (rootName != defaultRootName && file.startsWith(root)) {
+            file to "${rootName}${File.separator}${file.toRelativeString(root)}"
+        } else {
+            null
+        }
+    } ?: run {
+        val result = file.relativeTo(defaultRoot.key)
+        result to result.path
+    }
+}.sortedBy { it.second }.map { it.first }
+
+/**
+ * Interpret [configuration] of [CppUsage.LIBRARY_LINK] as a combination of `-L` and `-l` flags for the compiler.
+ *
+ * The output will be in stable order as by [stableSortedForReproducibility], and files relative to the root named `.`
+ * will be passed as relative paths, others as absolute.
+ */
+fun Project.asLinkFlags(configuration: Configuration, rootsMap: Map<File, String>): List<String> {
+    val attr = configuration.attributes.getAttribute(CppUsage.USAGE_ATTRIBUTE)?.name
+    require(attr == CppUsage.LIBRARY_LINK) {
+        "Expected ${CppUsage.LIBRARY_LINK}, but $this is $attr"
+    }
+    val dynamicLibraries = configuration.incoming.artifactView {
+        attributes {
+            attribute(LibraryElements.LIBRARY_ELEMENTS_ATTRIBUTE, objects.named(LibraryElements.DYNAMIC_LIB))
+        }
+    }.files
+    val staticLibraries = configuration.incoming.artifactView {
+        attributes {
+            attribute(LibraryElements.LIBRARY_ELEMENTS_ATTRIBUTE, objects.named(LibraryElements.LINK_ARCHIVE))
+        }
+    }.files
+    return buildList {
+        dynamicLibraries.stableSortedForReproducibility(rootsMap).flatMapTo(this) {
+            listOf("-L${it.parentFile.path}", "-l${libname(it)}")
+        }
+        staticLibraries.stableSortedForReproducibility(rootsMap).flatMapTo(this) {
+            listOf("-L${it.parentFile.path}", "-l${libname(it)}")
+        }
+    }
+}
diff --git a/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/interop/NativeInteropPlugin.kt b/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/interop/NativeInteropPlugin.kt
index 044d20b..d38d194 100644
--- a/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/interop/NativeInteropPlugin.kt
+++ b/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/interop/NativeInteropPlugin.kt
@@ -16,6 +16,7 @@
 import org.gradle.api.tasks.testing.Test
 import org.gradle.kotlin.dsl.*
 import org.jetbrains.kotlin.PlatformInfo
+import org.jetbrains.kotlin.asLinkFlags
 import org.jetbrains.kotlin.cpp.CppUsage
 import org.jetbrains.kotlin.dependencies.NativeDependenciesExtension
 import org.jetbrains.kotlin.dependencies.NativeDependenciesPlugin
@@ -23,10 +24,10 @@
 import org.jetbrains.kotlin.gradle.plugin.konan.tasks.KonanJvmInteropTask
 import org.jetbrains.kotlin.konan.target.HostManager
 import org.jetbrains.kotlin.konan.target.TargetWithSanitizer
+import org.jetbrains.kotlin.stableSortedForReproducibility
 import org.jetbrains.kotlin.tools.NativePlugin
 import org.jetbrains.kotlin.tools.NativeToolsExtension
 import org.jetbrains.kotlin.tools.ToolExecutionTask
-import org.jetbrains.kotlin.tools.libname
 import org.jetbrains.kotlin.tools.obj
 import org.jetbrains.kotlin.tools.solib
 import java.io.File
@@ -224,21 +225,17 @@
         val cppImplementation = configurations.getByName(CPP_IMPLEMENTATION_CONFIGURATION)
         val cppLink = configurations.getByName(CPP_LINK_CONFIGURATION)
 
-        val includeDirsAbsolutePaths = project.files(*systemIncludeDirs.toTypedArray())
-        val includeDirsRelativePaths = project.files(*selfHeaders.toTypedArray(), cppImplementation)
+        val nativeToolsExtension = extensions.getByType<NativeToolsExtension>()
+        val includeDirs = project.files(*systemIncludeDirs.toTypedArray(), *selfHeaders.toTypedArray(), cppImplementation)
+                .stableSortedForReproducibility(nativeToolsExtension.reproducibilityPathsMap)
 
         val stubsName = "${defFileName.removeSuffix(".def").split(".").reversed().joinToString(separator = "")}stubs"
         val library = solib(stubsName)
 
-        val linkedStaticLibrariesRelativePaths = cppLink.incoming.artifactView {
-            attributes {
-                attribute(LibraryElements.LIBRARY_ELEMENTS_ATTRIBUTE, objects.named(LibraryElements.LINK_ARCHIVE))
-            }
-        }.files
-        val linkedStaticLibrariesAbsolutePaths = project.files(*additionalLinkedStaticLibraries.toTypedArray())
+        val linkedStaticLibraries = project.files(*additionalLinkedStaticLibraries.toTypedArray())
+                .stableSortedForReproducibility(nativeToolsExtension.reproducibilityPathsMap)
 
-        extensions.getByType<NativeToolsExtension>().apply {
-            val workingDir = this.workingDir.asFile.get()
+        nativeToolsExtension.apply {
             val obj = if (HostManager.hostIsMingw) "obj" else "o"
             suffixes {
                 (".c" to ".$obj") {
@@ -268,8 +265,7 @@
                             reproducibilityCompilerFlags +
                             ignoreWarningFlags +
                             "-Werror" +
-                            includeDirsAbsolutePaths.map { "-I${it.absolutePath}" } +
-                            includeDirsRelativePaths.map { "-I${it.toRelativeString(workingDir)}" } +
+                            includeDirs.map { "-I${it.path}" } +
                             hostPlatform.clangForJni.hostCompilerArgsForJni
 
                     flags(*cflags.toTypedArray(), "-c", "-o", ruleOut(), ruleInFirst())
@@ -280,8 +276,7 @@
                             commonCompilerArgs +
                             reproducibilityCompilerFlags +
                             "-Werror" +
-                            includeDirsAbsolutePaths.map { "-I${it.absolutePath}" } +
-                            includeDirsRelativePaths.map { "-I${it.toRelativeString(workingDir)}" }
+                            includeDirs.map { "-I${it.path}" }
                     flags(*cxxflags.toTypedArray(), "-c", "-o", ruleOut(), ruleInFirst())
                 }
             }
@@ -299,16 +294,8 @@
             target(library, *objSet) {
                 tool(*hostPlatform.clangForJni.clangCXX("").toTypedArray())
                 val ldflags = buildList {
-                    addAll(linkedStaticLibrariesRelativePaths.map {
-                        it.toRelativeString(workingDir)
-                    })
-                    addAll(linkedStaticLibrariesAbsolutePaths.map { it.absolutePath })
-                    cppLink.incoming.artifactView {
-                        attributes {
-                            attribute(LibraryElements.LIBRARY_ELEMENTS_ATTRIBUTE, objects.named(LibraryElements.DYNAMIC_LIB))
-                        }
-                    }.files.flatMapTo(this) { listOf("-L${it.parentFile.toRelativeString(workingDir)}", "-l${libname(it)}") }
-                    addAll(linkerArgs)
+                    addAll(asLinkFlags(cppLink, reproducibilityPathsMap))
+                    addAll(linkedStaticLibraries.map { it.absolutePath }.sorted())
 
                     if (HostManager.hostIsMac) {
                         // Set install_name to a non-absolute path.
@@ -324,13 +311,16 @@
         }
 
         tasks.named(library).configure {
-            inputs.files(linkedStaticLibrariesRelativePaths).withPathSensitivity(PathSensitivity.NONE)
-            inputs.files(linkedStaticLibrariesAbsolutePaths).withPathSensitivity(PathSensitivity.NONE)
+            inputs.files(cppLink.incoming.artifactView {
+                attributes {
+                    attribute(LibraryElements.LIBRARY_ELEMENTS_ATTRIBUTE, objects.named(LibraryElements.LINK_ARCHIVE))
+                }
+            }.files).withPathSensitivity(PathSensitivity.NONE)
+            inputs.files(linkedStaticLibraries).withPathSensitivity(PathSensitivity.NONE)
         }
         tasks.named(obj(stubsName)).configure {
             inputs.dir(bindingsRoot.map { it.dir("c") }).withPathSensitivity(PathSensitivity.RELATIVE) // if C file was generated, need to set up task dependency
-            includeDirsRelativePaths.forEach { inputs.dir(it).withPathSensitivity(PathSensitivity.RELATIVE) }
-            includeDirsAbsolutePaths.forEach { inputs.dir(it).withPathSensitivity(PathSensitivity.RELATIVE) }
+            includeDirs.forEach { inputs.dir(it).withPathSensitivity(PathSensitivity.RELATIVE) }
         }
 
         artifacts {
diff --git a/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/tools/NativePlugin.kt b/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/tools/NativePlugin.kt
index c93ef5d..f9c2402 100644
--- a/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/tools/NativePlugin.kt
+++ b/kotlin-native/build-tools/src/main/kotlin/org/jetbrains/kotlin/tools/NativePlugin.kt
@@ -76,7 +76,7 @@
         val inputRelativePaths = files.elements.zip(workingDir) { files, base ->
             files.map {
                 it.asFile.toRelativeString(base.asFile)
-            }
+            }.sorted()
         }
 
         override fun render() = inputRelativePaths.get()
@@ -264,13 +264,16 @@
             }
         }
 
-    val reproducibilityCompilerFlags: Array<String>
-        get() = arrayOf(
-                "-ffile-prefix-map=${workingDir.asFile.get()}=.",
-                "-ffile-prefix-map=${nativeDependenciesExtension.nativeDependenciesRoot}=NATIVE_DEPS",
-                "-ffile-prefix-map=${jdkDir}=JDK", // Not all users depend on it, but keep it just in case.
+    val reproducibilityPathsMap: Map<File, String>
+        get() = mapOf(
+                workingDir.asFile.get() to ".",
+                nativeDependenciesExtension.nativeDependenciesRoot to "NATIVE_DEPS",
+                jdkDir to "JDK", // Not all users depend on it, but keep it just in case.
         )
 
+    val reproducibilityCompilerFlags: Array<String>
+        get() = reproducibilityPathsMap.map { "-ffile-prefix-map=${it.key}=${it.value}" }.toTypedArray()
+
     val sourceSets = SourceSets(project, this, mutableMapOf<String, SourceSet>())
     val toolPatterns = ToolConfigurationPatterns(this, mutableMapOf<Pair<String, String>, ToolPatternConfiguration>())
     val cleanupFiles = mutableListOf<String>()