alamb commented on code in PR #7860:
URL: https://github.com/apache/arrow-rs/pull/7860#discussion_r2257413770
##########
arrow-ord/src/sort.rs:
##########
@@ -4841,4 +4917,301 @@ mod tests {
assert_eq!(valid, vec![0, 2]);
assert_eq!(nulls, vec![1, 3]);
}
+
+ // Test specific edge case strings that exercise the 4-byte prefix logic
+ #[test]
+ fn test_specific_edge_cases() {
+ let test_cases = vec![
+ // Key test cases for lengths 1-4 that test prefix padding
+ "a", "ab", "ba", "baa", "abba", "abbc", "abc", "cda",
+ // Test cases where first 4 bytes are same but subsequent bytes
differ
+ "abcd", "abcde", "abcdf", "abcdaaa", "abcdbbb",
+ // Test cases with length < 4 that require padding
+ "z", "za", "zaa", "zaaa", "zaaab", // Empty string
+ "", // Test various length combinations with same prefix
+ "test", "test1", "test12", "test123", "test1234",
+ ];
+
+ // Use standard library sort as reference
+ let mut expected = test_cases.clone();
+ expected.sort();
+
+ // Use our sorting algorithm
+ let string_array = StringArray::from(test_cases.clone());
+ let indices: Vec<u32> = (0..test_cases.len() as u32).collect();
+ let result = sort_bytes(
+ &string_array,
+ indices,
+ vec![], // no nulls
+ SortOptions::default(),
+ None,
+ );
+
+ // Verify results
+ let sorted_strings: Vec<&str> = result
+ .values()
+ .iter()
+ .map(|&idx| test_cases[idx as usize])
+ .collect();
+
+ assert_eq!(sorted_strings, expected);
+ }
+
+ // Test sorting correctness for different length combinations
+ #[test]
+ fn test_length_combinations() {
+ let test_cases = vec![
+ // Focus on testing strings of length 1-4, as these affect padding
logic
+ ("", 0),
+ ("a", 1),
+ ("ab", 2),
+ ("abc", 3),
+ ("abcd", 4),
+ ("abcde", 5),
+ ("b", 1),
+ ("ba", 2),
+ ("bab", 3),
+ ("babc", 4),
+ ("babcd", 5),
+ // Test same prefix with different lengths
+ ("test", 4),
+ ("test1", 5),
+ ("test12", 6),
+ ("test123", 7),
+ ];
+
+ let strings: Vec<&str> = test_cases.iter().map(|(s, _)| *s).collect();
+ let mut expected = strings.clone();
+ expected.sort();
+
+ let string_array = StringArray::from(strings.clone());
+ let indices: Vec<u32> = (0..strings.len() as u32).collect();
+ let result = sort_bytes(&string_array, indices, vec![],
SortOptions::default(), None);
+
+ let sorted_strings: Vec<&str> = result
+ .values()
+ .iter()
+ .map(|&idx| strings[idx as usize])
+ .collect();
+
+ assert_eq!(sorted_strings, expected);
+ }
+
+ // Test UTF-8 string handling
+ #[test]
+ fn test_utf8_strings() {
+ let test_cases = vec![
+ "a",
+ "你", // 3-byte UTF-8 character
+ "你好", // 6 bytes
+ "你好世界", // 12 bytes
+ "🎉", // 4-byte emoji
+ "🎉🎊", // 8 bytes
+ "café", // Contains accent character
+ "naïve",
+ "Москва", // Cyrillic script
+ "東京", // Japanese kanji
+ "한국", // Korean
+ ];
+
+ let mut expected = test_cases.clone();
+ expected.sort();
+
+ let string_array = StringArray::from(test_cases.clone());
+ let indices: Vec<u32> = (0..test_cases.len() as u32).collect();
+ let result = sort_bytes(&string_array, indices, vec![],
SortOptions::default(), None);
+
+ let sorted_strings: Vec<&str> = result
+ .values()
+ .iter()
+ .map(|&idx| test_cases[idx as usize])
+ .collect();
+
+ assert_eq!(sorted_strings, expected);
+ }
+
+ // Fuzz testing: generate random UTF-8 strings and verify sort correctness
+ #[test]
+ fn test_fuzz_random_strings() {
+ let mut rng = StdRng::seed_from_u64(42); // Fixed seed for
reproducibility
+
+ for _ in 0..100 {
+ // Run 100 rounds of fuzz testing
+ let mut test_strings = Vec::new();
+
+ // Generate 20-50 random strings
+ let num_strings = rng.random_range(20..=50);
+
+ for _ in 0..num_strings {
+ let string = generate_random_string(&mut rng);
+ test_strings.push(string);
+ }
+
+ // Use standard library sort as reference
+ let mut expected = test_strings.clone();
+ expected.sort();
+
+ // Use our sorting algorithm
+ let string_array = StringArray::from(test_strings.clone());
+ let indices: Vec<u32> = (0..test_strings.len() as u32).collect();
+ let result = sort_bytes(&string_array, indices, vec![],
SortOptions::default(), None);
+
+ let sorted_strings: Vec<String> = result
+ .values()
+ .iter()
+ .map(|&idx| test_strings[idx as usize].clone())
+ .collect();
+
+ assert_eq!(
+ sorted_strings, expected,
+ "Fuzz test failed with input: {test_strings:?}"
+ );
+ }
+ }
+
+ // Helper function to generate random UTF-8 strings
+ fn generate_random_string(rng: &mut StdRng) -> String {
+ // Bias towards generating short strings, especially length 1-4
+ let length = if rng.random_bool(0.6) {
+ rng.random_range(0..=4) // 60% probability for 0-4 length strings
+ } else {
+ rng.random_range(5..=20) // 40% probability for longer strings
+ };
+
+ if length == 0 {
+ return String::new();
+ }
+
+ let mut result = String::new();
+ let mut current_len = 0;
+
+ while current_len < length {
+ let c = generate_random_char(rng);
+ let char_len = c.len_utf8();
+
+ // Ensure we don't exceed target length
+ if current_len + char_len <= length {
+ result.push(c);
+ current_len += char_len;
+ } else {
+ // If adding this character would exceed length, fill with
ASCII
+ let remaining = length - current_len;
+ for _ in 0..remaining {
+ result.push(rng.random_range('a'..='z'));
+ current_len += 1;
+ }
+ break;
+ }
+ }
+
+ result
+ }
+
+ // Generate random characters (including various UTF-8 characters)
+ fn generate_random_char(rng: &mut StdRng) -> char {
+ match rng.random_range(0..10) {
+ 0..=5 => rng.random_range('a'..='z'), // 60% ASCII lowercase
+ 6 => rng.random_range('A'..='Z'), // 10% ASCII uppercase
+ 7 => rng.random_range('0'..='9'), // 10% digits
+ 8 => {
+ // 10% Chinese characters
+ let chinese_chars = ['你', '好', '世', '界', '测', '试', '中', '文'];
+ chinese_chars[rng.random_range(0..chinese_chars.len())]
+ }
+ 9 => {
+ // 10% other Unicode characters (single `char`s)
+ let special_chars = ['é', 'ï', '🎉', '🎊', 'α', 'β', 'γ'];
+ special_chars[rng.random_range(0..special_chars.len())]
+ }
+ _ => unreachable!(),
+ }
+ }
+
+ // Test descending sort order
Review Comment:
nice
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
