Repository: ruffle-rs/ruffle (language: rust)

Issue:
[AS2] Array.sortOn: Uncaught RangeError: Maximum call stack size exceeded on large arrays
### Describe what you were doing

1. Launch test swf file:
[test.zip](https://github.com/user-attachments/files/17181061/test.zip)

Code:
```as
var arr = [];
for(var i = 0; i < 8000; i++) {
   arr.push({key: i});  
}
flash.external.ExternalInterface.call("console.log",arr[0]);
arr.sortOn("key",Array.DESCENDING | Array.NUMERIC);
flash.external.ExternalInterface.call("console.log",arr[0]);
```
2. Ruffle crashes after sort attempt (Flash sorts the array in < 1 sec)
3. Expected console.log output:
```
{key: 0}
{key: 7999}
```

### What does the crash message say?

Uncaught RangeError: Maximum call stack size exceeded
    at ruffle_web.wasm.ruffle_wstr::utils::swf_to_lowercase::h81d97944dc74cba0 (ruffle_web.wasm-0322297e:0x853402)
    at ruffle_web.wasm.indexmap::map::IndexMap<K,V,S>::get::hc93a8379153de48e (ruffle_web.wasm-0322297e:0x73f451)
    at ruffle_web.wasm.<ruffle_core::avm1::object::script_object::ScriptObject as ruffle_core::avm1::object::TObject>::get_local_stored::h6964997af4fe8582 (ruffle_web.wasm-0322297e:0x7b59dd)
    at ruffle_web.wasm.<ruffle_core::avm1::object::Object as ruffle_core::avm1::object::TObject>::get_local_stored::hca73950b602e76a1 (ruffle_web.wasm-0322297e:0x7d2855)
    at ruffle_web.wasm.ruffle_core::avm1::globals::array::sort_on_compare::{{closure}}::h71873913f8cb04bc (ruffle_web.wasm-0322297e:0x751aca)
    at ruffle_web.wasm.ruffle_core::avm1::globals::array::qsort::h73a5d043759b6b07 (ruffle_web.wasm-0322297e:0x5074d8)
    at ruffle_web.wasm.ruffle_core::avm1::globals::array::qsort::h73a5d043759b6b07 (ruffle_web.wasm-0322297e:0x507780)
    at ruffle_web.wasm.ruffle_core::avm1::globals::array::qsort::h73a5d043759b6b07 (ruffle_web.wasm-0322297e:0x50772e)
    at ruffle_web.wasm.ruffle_core::avm1::globals::array::qsort::h73a5d043759b6b07 (ruffle_web.wasm-0322297e:0x507780)
    at ruffle_web.wasm.ruffle_core::avm1::globals::array::qsort::h73a5d043759b6b07 (ruffle_web.wasm-0322297e:0x50772e)

### Ruffle Version

0.1.0 nightly 2024-09-29

### Affected platform

Self-hosted version

### Operating system

Windows 11

### Additional information

# Player Info
Allows script access: true
Renderer: wgpu
Adapter Backend: Gl
Adapter Name: "ANGLE (NVIDIA, NVIDIA GeForce RTX 3060 (0x00002504) Direct3D11 vs_5_0 ps_5_0, D3D11)"
Adapter Device Type: Other
Adapter Driver Name: ""
Adapter Driver Info: "WebGL 2.0 (OpenGL ES 3.0 Chromium)"
Enabled features: Features(TEXTURE_COMPRESSION_BC | FLOAT32_FILTERABLE | TEXTURE_ADAPTER_SPECIFIC_FORMAT_FEATURES)
Available features: Features(DEPTH32FLOAT_STENCIL8 | PUSH_CONSTANTS | CLEAR_TEXTURE | MULTIVIEW)
Current limits: Limits { max_texture_dimension_1d: 16384, max_texture_dimension_2d: 16384, max_texture_dimension_3d: 2048, max_texture_array_layers: 256, max_bind_groups: 4, max_bindings_per_bind_group: 1000, max_dynamic_uniform_buffers_per_pipeline_layout: 8, max_dynamic_storage_buffers_per_pipeline_layout: 0, max_sampled_textures_per_shader_stage: 16, max_samplers_per_shader_stage: 16, max_storage_buffers_per_shader_stage: 0, max_storage_textures_per_shader_stage: 0, max_uniform_buffers_per_shader_stage: 11, max_uniform_buffer_binding_size: 65536, max_storage_buffer_binding_size: 0, max_vertex_buffers: 8, max_buffer_size: 268435456, max_vertex_attributes: 16, max_vertex_buffer_array_stride: 255, min_uniform_buffer_offset_alignment: 256, min_storage_buffer_offset_alignment: 256, max_inter_stage_shader_components: 120, max_color_attachments: 8, max_color_attachment_bytes_per_sample: 32, max_compute_workgroup_storage_size: 0, max_compute_invocations_per_workgroup: 0, max_compute_workgroup_size_x: 0, max_compute_workgroup_size_y: 0, max_compute_workgroup_size_z: 0, max_compute_workgroups_per_dimension: 0, min_subgroup_size: 0, max_subgroup_size: 0, max_push_constant_size: 0, max_non_sampler_bindings: 1000000 }
Surface quality: high
Surface samples: 4
Surface size: (550, 400, 1)
Player type: Object
SWF URL: test.swf?v=14
Attribute 0: undefined
Attribute 1: undefined
Attribute 2: undefined
Attribute 3: undefined
Attribute 4: undefined
Attribute 5: undefined
Attribute 6: undefined
Attribute 7: undefined

# Page Info
Page URL: https://xarium.cc/test.html
SWF URL: https://xarium.cc/test.swf?v=14

# Browser Info
User Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/129.0.0.0 Safari/537.36
Platform: Win32
Has touch support: false

# Ruffle Info
Version: 0.1.0
Name: nightly 2024-09-29
Channel: nightly
Built: 2024-09-29T00:06:30.056Z
Commit: 877cfecfde02ff44f2647344f26cffda2c6eea61
Is extension: false

# Metadata
width: 1
height: 1
frameRate: 25
numFrames: 1
swfVersion: 8
backgroundColor: #000000
isActionScript3: false
uncompressedLength: 652



Discussion / hints:
Looks like the problem is in the recursive implementation of quicksort:
https://github.com/ruffle-rs/ruffle/blob/81a2222f4af8e942205c1f427341c84c748294b0/core/src/avm1/globals/array.rs#L667


Fix patch:
diff --git a/core/src/avm1/globals/array.rs b/core/src/avm1/globals/array.rs
index e8751e9d45ceb..920ee76e402d1 100644
--- a/core/src/avm1/globals/array.rs
+++ b/core/src/avm1/globals/array.rs
@@ -674,70 +674,61 @@ fn qsort<'gc>(
         return Ok(());
     }
 
-    // Fast-path for 2 elements.
-    if let [(_, a), (_, b)] = &elements {
-        if compare_fn(activation, a, b, options)?.is_gt() {
-            elements.swap(0, 1);
+    // Stack for storing inclusive subarray boundaries (start and end).
+    let mut stack: Vec<(usize, usize)> = Vec::new();
+
+    stack.push((0, elements.len() - 1));
+
+    while let Some((low, high)) = stack.pop() {
+        if low >= high {
+            continue;
         }
-        return Ok(());
-    }
 
-    // Flash always chooses the leftmost element as the pivot.
-    let (_, pivot) = elements[0];
-
-    // Order the elements (excluding the pivot) such that all elements lower
-    // than the pivot come before all elements greater than the pivot.
-    //
-    // This is done by iterating from both ends, swapping greater elements with
-    // lower ones along the way.
-    let mut left = 1;
-    let mut right = elements.len() - 1;
-    loop {
-        // Find an element greater than the pivot from the left.
-        while left < elements.len() - 1 {
-            let (_, item) = &elements[left];
-            if compare_fn(activation, &pivot, item, options)?.is_le() {
-                break;
+        // Flash always chooses the leftmost element as the pivot.
+        let pivot = elements[low].1;
+
+        let mut left = low + 1;
+        let mut right = high;
+
+        loop {
+            // Find an element greater than the pivot from the left.
+            while left <= high {
+                let (_, item) = &elements[left];
+                if compare_fn(activation, &pivot, item, options)?.is_le() {
+                    break;
+                }
+                left += 1;
             }
-            left += 1;
-        }
 
-        // Find an element lower than the pivot from the right.
-        while right > 0 {
-            let (_, item) = &elements[right];
-            if compare_fn(activation, &pivot, item, options)?.is_gt() {
+            // Find an element lower than the pivot from the right.
+            while right > low {
+                let (_, item) = &elements[right];
+                if compare_fn(activation, &pivot, item, options)?.is_gt() {
+                    break;
+                }
+                right -= 1;
+            }
+
+            // When left and right cross, then no element greater than
+            // the pivot comes before an element lower than the pivot.
+            if left >= right {
                 break;
             }
-            right -= 1;
-        }
 
-        // When left and right cross, then no element greater than
-        // the pivot comes before an element lower than the pivot.
-        if left >= right {
-            break;
+            // Otherwise, swap left and right, and keep going.
+            elements.swap(left, right);
         }
 
-        // Otherwise, swap left and right, and keep going.
-        elements.swap(left, right);
-    }
+        // Move the pivot element to its position between the partitions.
+        elements.swap(low, right);
 
-    // The elements are now ordered as follows:
-    // [0]: pivot
-    // [1..=right]: lower partition (empty if right == 0)
-    // [right + 1..]: higher partition
-
-    // Swap the pivot with the last element in the lower partition,
-    // moving it in between the lower and higher partitions.
-    elements.swap(0, right);
-
-    // The elements are now ordered as follows:
-    // [..right]: lower partition
-    // [right]: pivot
-    // [right + 1..]: higher partition
+        // Push subarrays onto the stack for further sorting.
+        if right > 0 {
+            stack.push((low, right - 1));
+        }
+        stack.push((right + 1, high));
+    }
 
-    // Recursively sort the lower and higher partitions.
-    qsort(activation, &mut elements[..right], compare_fn, options)?;
-    qsort(activation, &mut elements[right + 1..], compare_fn, options)?;
     Ok(())
 }
 


Test patch: