[K/JS, Gradle] Introduce `sourceRoot` in the generated source maps

Set `sourceRoot` to the longest common prefix of all source paths.

Reduces sourcemap file size on larger codebases by shrinking
common source files paths.

^KT-19819 Fixed
diff --git a/compiler/testData/cli/js/sourceMap.test b/compiler/testData/cli/js/sourceMap.test
index 3e377c7..7b8fb34 100644
--- a/compiler/testData/cli/js/sourceMap.test
+++ b/compiler/testData/cli/js/sourceMap.test
@@ -1,2 +1,3 @@
 // EXISTS: out.js
-// CONTAINS: out.js.map, "./sourceMap.kt"
+// CONTAINS: out.js.map, "sourceRoot":"./"
+// CONTAINS: out.js.map, "sourceMap.kt"
diff --git a/compiler/testData/cli/js/sourceMapEmbedSources.test b/compiler/testData/cli/js/sourceMapEmbedSources.test
index b6b8637..bd4a032 100644
--- a/compiler/testData/cli/js/sourceMapEmbedSources.test
+++ b/compiler/testData/cli/js/sourceMapEmbedSources.test
@@ -1,4 +1,5 @@
 // EXISTS: out.js
-// CONTAINS: out.js.map, "./sourceMap.kt"
+// CONTAINS: out.js.map, "sourceRoot":"./"
+// CONTAINS: out.js.map, "sourceMap.kt"
 // CONTAINS: out.js.map, "var log = \"\"
 // CONTAINS: out.js.map, fun foo(x: String) {
diff --git a/compiler/testData/cli/js/sourceMapPrefix.test b/compiler/testData/cli/js/sourceMapPrefix.test
index a3502d5..e5498b2 100644
--- a/compiler/testData/cli/js/sourceMapPrefix.test
+++ b/compiler/testData/cli/js/sourceMapPrefix.test
@@ -1,2 +1,3 @@
 // EXISTS: out.js
-// CONTAINS: out.js.map, "/localhost/src/sourceMap.kt"
+// CONTAINS: out.js.map, "sourceRoot":"/localhost/src/"
+// CONTAINS: out.js.map, "sourceMap.kt"
diff --git a/compiler/testData/cli/js/sourceMapSourceRoot.args b/compiler/testData/cli/js/sourceMapSourceRoot.args
new file mode 100644
index 0000000..841696d
--- /dev/null
+++ b/compiler/testData/cli/js/sourceMapSourceRoot.args
@@ -0,0 +1,23 @@
+$TESTDATA_DIR$/sourceMapRoot/foo/file1.kt
+$TESTDATA_DIR$/sourceMapRoot/bar/file2.kt
+$TESTDATA_DIR$/sourceMapRoot/bar/baz/file3.kt
+$TESTDATA_DIR$/sourceMapRoot/foo/baz/file4.kt
+-Xir-produce-klib-dir
+-libraries
+$STDLIB_JS$
+-ir-output-dir
+$TEMP_DIR$/klib
+-ir-output-name
+out
+---
+-Xir-produce-js
+-libraries
+$STDLIB_JS$
+-Xinclude=$TEMP_DIR$/klib
+-source-map
+-source-map-prefix
+/common/sources/folder/
+-ir-output-dir
+$TEMP_DIR$
+-ir-output-name
+out
diff --git a/compiler/testData/cli/js/sourceMapSourceRoot.out b/compiler/testData/cli/js/sourceMapSourceRoot.out
new file mode 100644
index 0000000..d86bac9
--- /dev/null
+++ b/compiler/testData/cli/js/sourceMapSourceRoot.out
@@ -0,0 +1 @@
+OK
diff --git a/compiler/testData/cli/js/sourceMapSourceRoot.test b/compiler/testData/cli/js/sourceMapSourceRoot.test
new file mode 100644
index 0000000..28362e25
--- /dev/null
+++ b/compiler/testData/cli/js/sourceMapSourceRoot.test
@@ -0,0 +1,17 @@
+// EXISTS: out.js
+// CONTAINS: out.js.map, "sourceRoot":"/common/sources/folder/"
+
+// CONTAINS: out.js.map, "file1.kt"
+// CONTAINS: out.js.map, "file2.kt"
+// CONTAINS: out.js.map, "file3.kt"
+// CONTAINS: out.js.map, "file4.kt"
+
+// NOT_CONTAINS: out.js.map, "sourceMapRoot/file1.kt"
+// NOT_CONTAINS: out.js.map, "sourceMapRoot/file2.kt"
+// NOT_CONTAINS: out.js.map, "sourceMapRoot/file3.kt"
+// NOT_CONTAINS: out.js.map, "sourceMapRoot/file4.kt"
+
+// NOT_CONTAINS: out.js.map, "/common/sources/folder/file1.kt"
+// NOT_CONTAINS: out.js.map, "/common/sources/folder/file2.kt"
+// NOT_CONTAINS: out.js.map, "/common/sources/folder/file3.kt"
+// NOT_CONTAINS: out.js.map, "/common/sources/folder/file4.kt"
diff --git a/compiler/tests-integration/tests-gen/org/jetbrains/kotlin/cli/CliTestGenerated.java b/compiler/tests-integration/tests-gen/org/jetbrains/kotlin/cli/CliTestGenerated.java
index 4007bcd..d51d8a9 100644
--- a/compiler/tests-integration/tests-gen/org/jetbrains/kotlin/cli/CliTestGenerated.java
+++ b/compiler/tests-integration/tests-gen/org/jetbrains/kotlin/cli/CliTestGenerated.java
@@ -2204,6 +2204,11 @@
       runTest("compiler/testData/cli/js/sourceMapRootMultiple.args");
     }
 
+    @TestMetadata("sourceMapSourceRoot.args")
+    public void testSourceMapSourceRoot() {
+      runTest("compiler/testData/cli/js/sourceMapSourceRoot.args");
+    }
+
     @TestMetadata("successfulHmpp.args")
     public void testSuccessfulHmpp() {
       runTest("compiler/testData/cli/js/successfulHmpp.args");
diff --git a/js/js.sourcemap/src/org/jetbrains/kotlin/js/sourceMap/SourceMap3Builder.kt b/js/js.sourcemap/src/org/jetbrains/kotlin/js/sourceMap/SourceMap3Builder.kt
index 0488cff..895bdcd 100644
--- a/js/js.sourcemap/src/org/jetbrains/kotlin/js/sourceMap/SourceMap3Builder.kt
+++ b/js/js.sourcemap/src/org/jetbrains/kotlin/js/sourceMap/SourceMap3Builder.kt
@@ -55,8 +55,53 @@
     }
 
     private fun appendSources(json: JsonObject) {
+        /**
+         * Calculates the length of the common directory prefix for given Unix-style paths,
+         * including the trailing '/' separator.
+         *
+         * Returns 0 if:
+         * - Paths list is empty or contains less than 2 entries
+         * - There is no common directory prefix, i.e. paths have no shared '/'-separated segments
+         *
+         * Example:
+         * For paths
+         * ```
+         * foo/bar.kt
+         * foo/bar/a.kt
+         * ```
+         * Returns 4 (the length of 'foo/').
+         */
+        fun commonUnixPathPrefixLength(paths: List<String>): Int {
+            // There is no sense in calculating common parent for the single directory, we will save it as is
+            if (paths.size < 2) return 0
+
+            // The idea is to find common directory between least common paths - first one and last one of sorted paths list.
+            val sortedPaths = paths.sortedDescending()
+
+            val (first, last) = sortedPaths.first() to sortedPaths.last()
+            val (shorter, longer) = if (first.length < last.length) first to last else last to first
+
+            var latestSeparatorIndex = -1
+
+            for (i in shorter.indices) {
+                if (shorter[i] == '/') latestSeparatorIndex = i
+                if (shorter[i] != longer[i]) break
+            }
+
+            return latestSeparatorIndex + 1
+        }
+
+        var prefixedPaths = orderedSources.map { pathPrefix + it }
+        val sourceRootLength = commonUnixPathPrefixLength(prefixedPaths)
+
+        if (sourceRootLength > 0) {
+            // Source root should contain the leading '/', so upper index also includes it
+            json.properties["sourceRoot"] = JsonString(prefixedPaths[0].substring(0, sourceRootLength))
+            prefixedPaths = prefixedPaths.map { it.substring(sourceRootLength) }
+        }
+
         json.properties["sources"] = JsonArray(
-            orderedSources.mapTo(mutableListOf()) { JsonString(pathPrefix + it) }
+            prefixedPaths.mapTo(mutableListOf()) { JsonString(it) }
         )
     }
 
diff --git a/libraries/tools/kotlin-gradle-plugin-integration-tests/src/test/kotlin/org/jetbrains/kotlin/gradle/Kotlin2JsGradlePluginIT.kt b/libraries/tools/kotlin-gradle-plugin-integration-tests/src/test/kotlin/org/jetbrains/kotlin/gradle/Kotlin2JsGradlePluginIT.kt
index def773c..07f016f 100644
--- a/libraries/tools/kotlin-gradle-plugin-integration-tests/src/test/kotlin/org/jetbrains/kotlin/gradle/Kotlin2JsGradlePluginIT.kt
+++ b/libraries/tools/kotlin-gradle-plugin-integration-tests/src/test/kotlin/org/jetbrains/kotlin/gradle/Kotlin2JsGradlePluginIT.kt
@@ -1179,8 +1179,9 @@
                     .resolve("build/compileSync/js/main/developmentExecutable/kotlin/$projectName-app.js.map")
                 assertFileContains(
                     appSourceMap,
-                    "\"../../../../../../src/jsMain/kotlin/main.kt\"",
-                    "\"../../../../../../../lib/src/jsMain/kotlin/foo.kt\"",
+                    "\"sourceRoot\":\"../../../../../../\"",
+                    "\"src/jsMain/kotlin/main.kt\"",
+                    "\"../lib/src/jsMain/kotlin/foo.kt\"",
                     "\"sourcesContent\":[null",
                 )
 
@@ -1213,8 +1214,9 @@
                 assertFileContains(
                     projectPath
                         .resolve("build/js/packages/$projectName-app/kotlin/$projectName-app.js.map"),
-                    "\"../../../../../app/src/jsMain/kotlin/main.kt\"",
-                    "\"../../../../../lib/src/jsMain/kotlin/foo.kt\"",
+                    "\"sourceRoot\":\"../../../../../app\"",
+                    "\"src/jsMain/kotlin/main.kt\"",
+                    "\"../lib/src/jsMain/kotlin/foo.kt\"",
                     "\"sourcesContent\":[null",
                 )
             }
@@ -1289,9 +1291,10 @@
             build("compileDevelopmentExecutableKotlinJs") {
                 val mapFilePath = subProject("app").projectPath
                     .resolve("build/kotlin2js/app.js.map")
-                assertFileContains(mapFilePath, "\"../../src/jsMain/kotlin/main.kt\"")
+                assertFileContains(mapFilePath, "\"sourceRoot\":\"../../\"")
+                assertFileContains(mapFilePath, "\"src/jsMain/kotlin/main.kt\"")
                 // The IR BE generates correct paths for dependencies
-                assertFileContains(mapFilePath, "\"../../../lib/src/jsMain/kotlin/foo.kt\"")
+                assertFileContains(mapFilePath, "\"../lib/src/jsMain/kotlin/foo.kt\"")
             }
         }
     }
diff --git a/libraries/tools/kotlin-gradle-plugin/src/common/kotlin/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReader.kt b/libraries/tools/kotlin-gradle-plugin/src/common/kotlin/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReader.kt
index 3270d9c..95336ff 100644
--- a/libraries/tools/kotlin-gradle-plugin/src/common/kotlin/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReader.kt
+++ b/libraries/tools/kotlin-gradle-plugin/src/common/kotlin/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReader.kt
@@ -90,6 +90,7 @@
 
         // parse json in prolog and write it back to bufferJsonWriter with transformed source paths
         val json = JsonReader(StringReader(jsonString.toString()))
+        var sourceRootSpecified = false
         try {
             json.beginObject()
             bufferJsonWriter.beginObject()
@@ -99,12 +100,18 @@
                 check(token == JsonToken.NAME) { "JSON key expected, but $token found" }
                 val key = json.nextName()
                 when (key) {
+                    "sourceRoot" -> {
+                        val srcSourceRootPath = transformString(json.nextString())
+                        bufferJsonWriter.name(key).value(srcSourceRootPath)
+                        sourceRootSpecified = true
+                    }
                     "sources" -> {
                         json.beginArray()
                         bufferJsonWriter.name("sources").beginArray()
                         while (json.peek() != JsonToken.END_ARRAY) {
                             val path = json.nextString()
-                            bufferJsonWriter.value(transformString(path))
+                            val transformed = if (sourceRootSpecified) path else transformString(path)
+                            bufferJsonWriter.value(transformed)
                         }
                         json.endArray()
                     }
diff --git a/libraries/tools/kotlin-gradle-plugin/src/test/kotlin/org/jetbrains/kotlin/gradle/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReaderTest.kt b/libraries/tools/kotlin-gradle-plugin/src/test/kotlin/org/jetbrains/kotlin/gradle/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReaderTest.kt
index 4aa551d..d1034b4 100644
--- a/libraries/tools/kotlin-gradle-plugin/src/test/kotlin/org/jetbrains/kotlin/gradle/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReaderTest.kt
+++ b/libraries/tools/kotlin-gradle-plugin/src/test/kotlin/org/jetbrains/kotlin/gradle/org/jetbrains/kotlin/gradle/targets/js/internal/RewriteSourceMapFilterReaderTest.kt
@@ -53,6 +53,25 @@
     }
 
     @Test
+    fun testSourceRootSpecified() {
+        val filter =
+            RewriteSourceMapFilterReaderMock(
+                StringReader(
+                    //language=JSON
+                    """{"version":3,"file":"single-platform.js","sourceRoot":"../../../../","sources":["src/main/kotlin/main.kt","src/main/kotlin/lib.kt"],"sourcesContent":[null],"names":[],"mappings":""}"""
+                ),
+                "/root/build/classes/kotlin/test/",
+                "/root/build/test_node_modules/"
+            )
+
+        assertEquals(
+            //language=JSON
+            """{"version":3,"file":"single-platform.js","sourceRoot":"TRANSFORMED(../../../../)","sources":["src/main/kotlin/main.kt","src/main/kotlin/lib.kt"],"sourcesContent":[null],"names":[],"mappings":""}""",
+            filter.readText()
+        )
+    }
+
+    @Test
     fun testPrologWithoutSourcesContent() {
         val filter =
             RewriteSourceMapFilterReaderMock(