)]}'
{
  "commit": "29d679ee98094162dc4a3aaadf66b4931a815dd3",
  "tree": "aff704117e9d63d8256c1458b52498629dc98515",
  "parents": [
    "1fd69442c3afe111cae4f52e03b8ea73e81a8d70"
  ],
  "author": {
    "name": "Nikita Bobko",
    "email": "nikita.bobko@jetbrains.com",
    "time": "Tue Jul 23 15:30:59 2024 +0200"
  },
  "committer": {
    "name": "Nikita Bobko",
    "email": "nikita.bobko@jetbrains.com",
    "time": "Wed Jul 24 13:01:28 2024 +0200"
  },
  "message": "[Native, Wasm, stdlib] Fix bug in quickSort for primitive arrays\n\n^KT-70005 Fixed\n\nIt took 7 years, 3 months, 13 days; 3 project managers; 2 developers;\n2 language designers; 2 fixup commits; 1 code reviewer; 1 sedative pill\nto fix this bug\n\nCo-authored-by: Igor Yakovlev \u003cigor.yakovlev@jetbrains.com\u003e\nCo-authored-by: marat.akhin \u003cmarat.akhin@jetbrains.com\u003e\nCo-authored-by: Mikhail Zarechenskiy \u003cmikhail.zarechenskiy@jetbrains.com\u003e\n\nJokes aside, the alternative fixes are:\n         private fun quickSort(\n                 array: LongArray, left: Int, right: Int) {\n        +    if (left \u003e\u003d right) return\n             val index \u003d partition(array, left, right)\n             if (left \u003c index - 1)\n                 quickSort(array, left, index - 1)\n    OR:\n         private fun quickSort(\n                 array: LongArray, left: Int, right: Int) {\n        +    if (left \u003e\u003d right) return\n             val index \u003d partition(array, left, right)\n        -    if (left \u003c index - 1)\n        -        quickSort(array, left, index - 1)\n        -    if (index \u003c right)\n        -        quickSort(array, index, right)\n        +    quickSort(array, left, index - 1)\n        +    quickSort(array, index, right)\n         }\n\nThe first fix is bad because `left \u003e\u003d right` will never be `true` inside\nthe recursion. (quickSort is recursively invoked only when\n`left \u003c index - 1`) So we are doing a redundant check on every level of\nthe recursion\n\nThe second fix doesn\u0027t have the redundant boolean check, but in the\nworst case it will increase the recursion by one, which might be just\nenough to cause stack overflow and break code that worked before. Not to\nmention, that in the recursion tree every recursion will take one more\nrecursion call to complete.\n",
  "tree_diff": [
    {
      "type": "modify",
      "old_id": "720249b5f679d58a5d68163f70224bd73a62f42b",
      "old_mode": 33188,
      "old_path": "kotlin-native/runtime/src/main/kotlin/generated/_ArraysNative.kt",
      "new_id": "d93a00289858de9be3de6d0d666f16a4effe4519",
      "new_mode": 33188,
      "new_path": "kotlin-native/runtime/src/main/kotlin/generated/_ArraysNative.kt"
    },
    {
      "type": "modify",
      "old_id": "944583dddb9b2ea7ba7656a38fd7b9a682d718c6",
      "old_mode": 33188,
      "old_path": "libraries/stdlib/test/collections/ArraysTest.kt",
      "new_id": "a76c0f5cc1c7cd5d95f5974c09e8749f85ed79d1",
      "new_mode": 33188,
      "new_path": "libraries/stdlib/test/collections/ArraysTest.kt"
    },
    {
      "type": "modify",
      "old_id": "135bb65e688ee6422de457b9446de83d174aef41",
      "old_mode": 33188,
      "old_path": "libraries/stdlib/wasm/src/generated/_ArraysWasm.kt",
      "new_id": "62f75c04f9d09b2e250c54f0f17c724d85c610a0",
      "new_mode": 33188,
      "new_path": "libraries/stdlib/wasm/src/generated/_ArraysWasm.kt"
    }
  ]
}