Improve polymorphic deserialization optimization: (#2481)

Previously, when discriminator was found as the first key in Json, but there was no deserializer for it, we still fell back to a slow path with JsonTree.
It was actually meaningless because a slow path always throws exception when a serializer is not found.
Such behavior led to unnecessary memory pressure & consumption in exceptional cases (see linked ticket for details).

Also make polymorphic deserialization exception messages more meaningful and make them more consistent with serialization ones.

Also fix behavior when the actual discriminator value is JsonNull (it should be treated as missing, not as "null" string).

Fixes #2478

9 files changed, 134 insertions, 59 deletions

diff --git a/core/commonMain/src/kotlinx/serialization/internal/AbstractPolymorphicSerializer.kt b/core/commonMain/src/kotlinx/serialization/internal/AbstractPolymorphicSerializer.kt
index 8604bbc9..26d3b5e2 100644
--- a/core/commonMain/src/kotlinx/serialization/internal/AbstractPolymorphicSerializer.kt
+++ b/core/commonMain/src/kotlinx/serialization/internal/AbstractPolymorphicSerializer.kt
@@ -58,8 +58,8 @@ public abstract class AbstractPolymorphicSerializer<T : Any> internal constructo
                 }
                 else -> throw SerializationException(
                     "Invalid index in polymorphic deserialization of " +
-                            (klassName ?: "unknown class") +
-                            "\n Expected 0, 1 or DECODE_DONE(-1), but found $index"
+                        (klassName ?: "unknown class") +
+                        "\n Expected 0, 1 or DECODE_DONE(-1), but found $index"
                 )
             }
         }
@@ -98,14 +98,14 @@ public abstract class AbstractPolymorphicSerializer<T : Any> internal constructo
 
 @JvmName("throwSubtypeNotRegistered")
 internal fun throwSubtypeNotRegistered(subClassName: String?, baseClass: KClass<*>): Nothing {
-    val scope = "in the scope of '${baseClass.simpleName}'"
+    val scope = "in the polymorphic scope of '${baseClass.simpleName}'"
     throw SerializationException(
         if (subClassName == null)
-            "Class discriminator was missing and no default polymorphic serializers were registered $scope"
+            "Class discriminator was missing and no default serializers were registered $scope."
         else
-            "Class '$subClassName' is not registered for polymorphic serialization $scope.\n" +
-            "To be registered automatically, class '$subClassName' has to be '@Serializable', and the base class '${baseClass.simpleName}' has to be sealed and '@Serializable'.\n" +
-            "Alternatively, register the serializer for '$subClassName' explicitly in a corresponding SerializersModule."
+            "Serializer for subclass '$subClassName' is not found $scope.\n" +
+                "Check if class with serial name '$subClassName' exists and serializer is registered in a corresponding SerializersModule.\n" +
+                "To be registered automatically, class '$subClassName' has to be '@Serializable', and the base class '${baseClass.simpleName}' has to be sealed and '@Serializable'."
     )
 }
 
diff --git a/docs/polymorphism.md b/docs/polymorphism.md
index 29d023b6..b7ea31f4 100644
--- a/docs/polymorphism.md
+++ b/docs/polymorphism.md
@@ -123,9 +123,9 @@ fun main() {
 This is close to the best design for a serializable hierarchy of classes, but running it produces the following error:
 
 ```text 
-Exception in thread "main" kotlinx.serialization.SerializationException: Class 'OwnedProject' is not registered for polymorphic serialization in the scope of 'Project'.
+Exception in thread "main" kotlinx.serialization.SerializationException: Serializer for subclass 'OwnedProject' is not found in the polymorphic scope of 'Project'.
+Check if class with serial name 'OwnedProject' exists and serializer is registered in a corresponding SerializersModule.
 To be registered automatically, class 'OwnedProject' has to be '@Serializable', and the base class 'Project' has to be sealed and '@Serializable'.
-Alternatively, register the serializer for 'OwnedProject' explicitly in a corresponding SerializersModule.
 ```         
 
 <!--- TEST LINES_START -->
@@ -832,7 +832,8 @@ fun main() {
 We get the following exception.
 
 ```text 
-Exception in thread "main" kotlinx.serialization.json.internal.JsonDecodingException: Polymorphic serializer was not found for class discriminator 'unknown'
+Exception in thread "main" kotlinx.serialization.json.internal.JsonDecodingException: Unexpected JSON token at offset 0: Serializer for subclass 'unknown' is not found in the polymorphic scope of 'Project' at path: $
+Check if class with serial name 'unknown' exists and serializer is registered in a corresponding SerializersModule.
 ```
 
 <!--- TEST LINES_START -->
diff --git a/formats/json-tests/commonTest/src/kotlinx/serialization/features/PolymorphicDeserializationErrorMessagesTest.kt b/formats/json-tests/commonTest/src/kotlinx/serialization/features/PolymorphicDeserializationErrorMessagesTest.kt
new file mode 100644
index 00000000..2b2f1f70
--- /dev/null
+++ b/formats/json-tests/commonTest/src/kotlinx/serialization/features/PolymorphicDeserializationErrorMessagesTest.kt
@@ -0,0 +1,60 @@
+/*
+ * Copyright 2017-2023 JetBrains s.r.o. Use of this source code is governed by the Apache 2.0 license.
+ */
+
+package kotlinx.serialization.features
+
+import kotlinx.serialization.*
+import kotlinx.serialization.json.*
+import kotlin.test.*
+
+class PolymorphicDeserializationErrorMessagesTest : JsonTestBase() {
+    @Serializable
+    class DummyData(@Polymorphic val a: Any)
+
+    @Serializable
+    class Holder(val d: DummyData)
+
+    // TODO: remove this after #2480 is merged
+    private fun checkSerializationException(action: () -> Unit, assertions: SerializationException.(String) -> Unit) {
+        val e = assertFailsWith(SerializationException::class, action)
+        assertNotNull(e.message)
+        e.assertions(e.message!!)
+    }
+
+    @Test
+    fun testNotRegisteredMessage() = parametrizedTest { mode ->
+        val input = """{"d":{"a":{"type":"my.Class", "value":42}}}"""
+        checkSerializationException({
+            default.decodeFromString<Holder>(input, mode)
+        }, { message ->
+            // ReaderJsonLexer.peekLeadingMatchingValue is not implemented, so first-key optimization is not working for streaming yet.
+            if (mode == JsonTestingMode.STREAMING)
+                assertContains(message, "Unexpected JSON token at offset 10: Serializer for subclass 'my.Class' is not found in the polymorphic scope of 'Any' at path: \$.d.a")
+            else
+                assertContains(message, "Serializer for subclass 'my.Class' is not found in the polymorphic scope of 'Any'")
+        })
+    }
+
+    @Test
+    fun testDiscriminatorMissingNoDefaultMessage() = parametrizedTest { mode ->
+        val input = """{"d":{"a":{"value":42}}}"""
+        checkSerializationException({
+            default.decodeFromString<Holder>(input, mode)
+        }, { message ->
+            // Always slow path when discriminator is missing, so no position and path
+            assertContains(message, "Class discriminator was missing and no default serializers were registered in the polymorphic scope of 'Any'")
+        })
+    }
+
+    @Test
+    fun testClassDiscriminatorIsNull() = parametrizedTest { mode ->
+        val input = """{"d":{"a":{"type":null, "value":42}}}"""
+        checkSerializationException({
+            default.decodeFromString<Holder>(input, mode)
+        }, { message ->
+            // Always slow path when discriminator is missing, so no position and path
+            assertContains(message, "Class discriminator was missing and no default serializers were registered in the polymorphic scope of 'Any'")
+        })
+    }
+}
diff --git a/formats/json-tests/commonTest/src/kotlinx/serialization/features/PolymorphismWithAnyTest.kt b/formats/json-tests/commonTest/src/kotlinx/serialization/features/PolymorphismWithAnyTest.kt
index e1d38fdd..07b6e31a 100644
--- a/formats/json-tests/commonTest/src/kotlinx/serialization/features/PolymorphismWithAnyTest.kt
+++ b/formats/json-tests/commonTest/src/kotlinx/serialization/features/PolymorphismWithAnyTest.kt
@@ -5,13 +5,13 @@
 package kotlinx.serialization.features
 
 import kotlinx.serialization.*
-import kotlinx.serialization.json.Json
+import kotlinx.serialization.json.*
 import kotlinx.serialization.modules.*
 import kotlinx.serialization.modules.plus
 import kotlinx.serialization.test.assertStringFormAndRestored
 import kotlin.test.*
 
-class PolymorphismWithAnyTest {
+class PolymorphismWithAnyTest: JsonTestBase() {
 
     @Serializable
     data class MyPolyData(val data: Map<String, @Polymorphic Any>)
@@ -28,19 +28,20 @@ class PolymorphismWithAnyTest {
         val className = className.substringAfterLast('.')
         val scopeName = scopeName.substringAfterLast('.')
         val expectedText =
-            "Class '$className' is not registered for polymorphic serialization in the scope of '$scopeName'"
+            "Serializer for subclass '$className' is not found in the polymorphic scope of '$scopeName'"
         assertTrue(exception.message!!.startsWith(expectedText),
             "Found $exception, but expected to start with: $expectedText")
     }
 
     @Test
-    fun testFailWithoutModulesWithCustomClass() {
+    fun testFailWithoutModulesWithCustomClass() = parametrizedTest { mode ->
         checkNotRegisteredMessage(
             "kotlinx.serialization.IntData", "kotlin.Any",
             assertFailsWith<SerializationException>("not registered") {
                 Json.encodeToString(
                     MyPolyData.serializer(),
-                    MyPolyData(mapOf("a" to IntData(42)))
+                    MyPolyData(mapOf("a" to IntData(42))),
+                    mode
                 )
             }
         )
@@ -51,11 +52,11 @@ class PolymorphismWithAnyTest {
         val json = Json {
             serializersModule = SerializersModule { polymorphic(Any::class) { subclass(IntData.serializer()) } }
         }
-        assertStringFormAndRestored(
+        assertJsonFormAndRestored(
             expected = """{"data":{"a":{"type":"kotlinx.serialization.IntData","intV":42}}}""",
-            original = MyPolyData(mapOf("a" to IntData(42))),
+            data = MyPolyData(mapOf("a" to IntData(42))),
             serializer = MyPolyData.serializer(),
-            format = json
+            json = json
         )
     }
 
@@ -63,14 +64,15 @@ class PolymorphismWithAnyTest {
      * This test should fail because PolyDerived registered in the scope of PolyBase, not kotlin.Any
      */
     @Test
-    fun testFailWithModulesNotInAnyScope() {
+    fun testFailWithModulesNotInAnyScope() = parametrizedTest { mode ->
         val json = Json { serializersModule = BaseAndDerivedModule }
         checkNotRegisteredMessage(
             "kotlinx.serialization.PolyDerived", "kotlin.Any",
             assertFailsWith<SerializationException> {
                 json.encodeToString(
                     MyPolyData.serializer(),
-                    MyPolyData(mapOf("a" to PolyDerived("foo")))
+                    MyPolyData(mapOf("a" to PolyDerived("foo"))),
+                    mode
                 )
             }
         )
@@ -86,11 +88,11 @@ class PolymorphismWithAnyTest {
     @Test
     fun testRebindModules() {
         val json = Json { serializersModule = baseAndDerivedModuleAtAny }
-        assertStringFormAndRestored(
+        assertJsonFormAndRestored(
             expected = """{"data":{"a":{"type":"kotlinx.serialization.PolyDerived","id":1,"s":"foo"}}}""",
-            original = MyPolyData(mapOf("a" to PolyDerived("foo"))),
+            data = MyPolyData(mapOf("a" to PolyDerived("foo"))),
             serializer = MyPolyData.serializer(),
-            format = json
+            json = json
         )
     }
 
@@ -98,7 +100,7 @@ class PolymorphismWithAnyTest {
      * This test should fail because PolyDerived registered in the scope of kotlin.Any, not PolyBase
      */
     @Test
-    fun testFailWithModulesNotInParticularScope() {
+    fun testFailWithModulesNotInParticularScope() = parametrizedTest { mode ->
         val json = Json { serializersModule = baseAndDerivedModuleAtAny }
         checkNotRegisteredMessage(
             "kotlinx.serialization.PolyDerived", "kotlinx.serialization.PolyBase",
@@ -108,7 +110,8 @@ class PolymorphismWithAnyTest {
                     MyPolyDataWithPolyBase(
                         mapOf("a" to PolyDerived("foo")),
                         PolyDerived("foo")
-                    )
+                    ),
+                    mode
                 )
             }
         )
@@ -117,17 +120,30 @@ class PolymorphismWithAnyTest {
     @Test
     fun testBindModules() {
         val json = Json { serializersModule = (baseAndDerivedModuleAtAny + BaseAndDerivedModule) }
-        assertStringFormAndRestored(
+        assertJsonFormAndRestored(
             expected = """{"data":{"a":{"type":"kotlinx.serialization.PolyDerived","id":1,"s":"foo"}},
                 |"polyBase":{"type":"kotlinx.serialization.PolyDerived","id":1,"s":"foo"}}""".trimMargin().lines().joinToString(
                 ""
             ),
-            original = MyPolyDataWithPolyBase(
+            data = MyPolyDataWithPolyBase(
                 mapOf("a" to PolyDerived("foo")),
                 PolyDerived("foo")
             ),
             serializer = MyPolyDataWithPolyBase.serializer(),
-            format = json
+            json = json
         )
     }
+
+    @Test
+    fun testTypeKeyLastInInput() = parametrizedTest { mode ->
+        val json = Json { serializersModule = (baseAndDerivedModuleAtAny + BaseAndDerivedModule) }
+        val input = """{"data":{"a":{"id":1,"s":"foo","type":"kotlinx.serialization.PolyDerived"}},
+                |"polyBase":{"id":1,"s":"foo","type":"kotlinx.serialization.PolyDerived"}}""".trimMargin().lines().joinToString(
+            "")
+        val data = MyPolyDataWithPolyBase(
+            mapOf("a" to PolyDerived("foo")),
+            PolyDerived("foo")
+        )
+        assertEquals(data, json.decodeFromString(MyPolyDataWithPolyBase.serializer(), input, mode))
+    }
 }
diff --git a/formats/json/commonMain/src/kotlinx/serialization/json/internal/JsonExceptions.kt b/formats/json/commonMain/src/kotlinx/serialization/json/internal/JsonExceptions.kt
index 2eaa377e..c6098dd4 100644
--- a/formats/json/commonMain/src/kotlinx/serialization/json/internal/JsonExceptions.kt
+++ b/formats/json/commonMain/src/kotlinx/serialization/json/internal/JsonExceptions.kt
@@ -82,7 +82,7 @@ internal fun UnknownKeyException(key: String, input: String) = JsonDecodingExcep
             "Current input: ${input.minify()}"
 )
 
-private fun CharSequence.minify(offset: Int = -1): CharSequence {
+internal fun CharSequence.minify(offset: Int = -1): CharSequence {
     if (length < 200) return this
     if (offset == -1) {
         val start = this.length - 60
diff --git a/formats/json/commonMain/src/kotlinx/serialization/json/internal/Polymorphic.kt b/formats/json/commonMain/src/kotlinx/serialization/json/internal/Polymorphic.kt
index c1c91264..bd658fc1 100644
--- a/formats/json/commonMain/src/kotlinx/serialization/json/internal/Polymorphic.kt
+++ b/formats/json/commonMain/src/kotlinx/serialization/json/internal/Polymorphic.kt
@@ -63,20 +63,15 @@ internal fun <T> JsonDecoder.decodeSerializableValuePolymorphic(deserializer: De
     val discriminator = deserializer.descriptor.classDiscriminator(json)
 
     val jsonTree = cast<JsonObject>(decodeJsonElement(), deserializer.descriptor)
-    val type = jsonTree[discriminator]?.jsonPrimitive?.content
-    val actualSerializer = deserializer.findPolymorphicSerializerOrNull(this, type)
-        ?: throwSerializerNotFound(type, jsonTree)
-
+    val type = jsonTree[discriminator]?.jsonPrimitive?.contentOrNull // differentiate between `"type":"null"` and `"type":null`.
     @Suppress("UNCHECKED_CAST")
-    return json.readPolymorphicJson(discriminator, jsonTree, actualSerializer as DeserializationStrategy<T>)
-}
-
-@JvmName("throwSerializerNotFound")
-internal fun throwSerializerNotFound(type: String?, jsonTree: JsonObject): Nothing {
-    val suffix =
-        if (type == null) "missing class discriminator ('null')"
-        else "class discriminator '$type'"
-    throw JsonDecodingException(-1, "Polymorphic serializer was not found for $suffix", jsonTree.toString())
+    val actualSerializer =
+        try {
+            deserializer.findPolymorphicSerializer(this, type)
+        } catch (it: SerializationException) { //  Wrap SerializationException into JsonDecodingException to preserve input
+            throw JsonDecodingException(-1, it.message!!, jsonTree.toString())
+        } as DeserializationStrategy<T>
+    return json.readPolymorphicJson(discriminator, jsonTree, actualSerializer)
 }
 
 internal fun SerialDescriptor.classDiscriminator(json: Json): String {
diff --git a/formats/json/commonMain/src/kotlinx/serialization/json/internal/StreamingJsonDecoder.kt b/formats/json/commonMain/src/kotlinx/serialization/json/internal/StreamingJsonDecoder.kt
index ca79e152..0018fce1 100644
--- a/formats/json/commonMain/src/kotlinx/serialization/json/internal/StreamingJsonDecoder.kt
+++ b/formats/json/commonMain/src/kotlinx/serialization/json/internal/StreamingJsonDecoder.kt
@@ -71,19 +71,22 @@ internal open class StreamingJsonDecoder(
 
             val discriminator = deserializer.descriptor.classDiscriminator(json)
             val type = lexer.peekLeadingMatchingValue(discriminator, configuration.isLenient)
-            var actualSerializer: DeserializationStrategy<Any>? = null
-            if (type != null) {
-                actualSerializer = deserializer.findPolymorphicSerializerOrNull(this, type)
-            }
-            if (actualSerializer == null) {
-                // Fallback if we haven't found discriminator or serializer
+                ?: // Fallback to slow path if we haven't found discriminator on first try
                 return decodeSerializableValuePolymorphic<T>(deserializer as DeserializationStrategy<T>)
-            }
 
-            discriminatorHolder = DiscriminatorHolder(discriminator)
             @Suppress("UNCHECKED_CAST")
-            val result = actualSerializer.deserialize(this) as T
-            return result
+            val actualSerializer = try {
+                    deserializer.findPolymorphicSerializer(this, type)
+                } catch (it: SerializationException) { // Wrap SerializationException into JsonDecodingException to preserve position, path, and input.
+                    // Split multiline message from private core function:
+                    // core/commonMain/src/kotlinx/serialization/internal/AbstractPolymorphicSerializer.kt:102
+                    val message = it.message!!.substringBefore('\n').removeSuffix(".")
+                    val hint = it.message!!.substringAfter('\n', missingDelimiterValue = "")
+                    lexer.fail(message, hint = hint)
+                } as DeserializationStrategy<T>
+
+            discriminatorHolder = DiscriminatorHolder(discriminator)
+            return actualSerializer.deserialize(this)
 
         } catch (e: MissingFieldException) {
             // Add "at path" if and only if we've just caught an exception and it hasn't been augmented yet
diff --git a/guide/test/PolymorphismTest.kt b/guide/test/PolymorphismTest.kt
index f6147634..344ed24d 100644
--- a/guide/test/PolymorphismTest.kt
+++ b/guide/test/PolymorphismTest.kt
@@ -23,9 +23,9 @@ class PolymorphismTest {
     @Test
     fun testExamplePoly03() {
         captureOutput("ExamplePoly03") { example.examplePoly03.main() }.verifyOutputLinesStart(
-            "Exception in thread \"main\" kotlinx.serialization.SerializationException: Class 'OwnedProject' is not registered for polymorphic serialization in the scope of 'Project'.",
-            "To be registered automatically, class 'OwnedProject' has to be '@Serializable', and the base class 'Project' has to be sealed and '@Serializable'.",
-            "Alternatively, register the serializer for 'OwnedProject' explicitly in a corresponding SerializersModule."
+            "Exception in thread \"main\" kotlinx.serialization.SerializationException: Serializer for subclass 'OwnedProject' is not found in the polymorphic scope of 'Project'.",
+            "Check if class with serial name 'OwnedProject' exists and serializer is registered in a corresponding SerializersModule.",
+            "To be registered automatically, class 'OwnedProject' has to be '@Serializable', and the base class 'Project' has to be sealed and '@Serializable'."
         )
     }
 
@@ -133,7 +133,8 @@ class PolymorphismTest {
     @Test
     fun testExamplePoly18() {
         captureOutput("ExamplePoly18") { example.examplePoly18.main() }.verifyOutputLinesStart(
-            "Exception in thread \"main\" kotlinx.serialization.json.internal.JsonDecodingException: Polymorphic serializer was not found for class discriminator 'unknown'"
+            "Exception in thread \"main\" kotlinx.serialization.json.internal.JsonDecodingException: Unexpected JSON token at offset 0: Serializer for subclass 'unknown' is not found in the polymorphic scope of 'Project' at path: $",
+            "Check if class with serial name 'unknown' exists and serializer is registered in a corresponding SerializersModule."
         )
     }
 
diff --git a/integration-test/src/commonTest/kotlin/sample/JsonTest.kt b/integration-test/src/commonTest/kotlin/sample/JsonTest.kt
index 6b704354..88a7a0d7 100644
--- a/integration-test/src/commonTest/kotlin/sample/JsonTest.kt
+++ b/integration-test/src/commonTest/kotlin/sample/JsonTest.kt
@@ -12,7 +12,7 @@ import kotlinx.serialization.modules.*
 import kotlin.reflect.*
 import kotlin.test.*
 
-public val jsonWithDefaults = Json { encodeDefaults = true }
+val jsonWithDefaults = Json { encodeDefaults = true }
 
 class JsonTest {
 
@@ -129,10 +129,9 @@ class JsonTest {
         assertEquals("""Derived2(state1='foo')""", restored2.toString())
     }
 
-    @Suppress("NAME_SHADOWING")
     private fun checkNotRegisteredMessage(exception: SerializationException) {
         val expectedText =
-            "is not registered for polymorphic serialization in the scope of"
+            "is not found in the polymorphic scope of"
         assertEquals(true, exception.message?.contains(expectedText))
     }