This is an automated email from the ASF dual-hosted git repository.
Jefffrey pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/arrow-rs.git
The following commit(s) were added to refs/heads/main by this push:
new aa60e22d60 fix(arrow-string): saturate the offset casts in substring
(#10995)
aa60e22d60 is described below
commit aa60e22d60bb9fa37d5bc550db11fc6e61033fa7
Author: pawan <[email protected]>
AuthorDate: Mon Sep 21 14:41:43 2026 +0530
fix(arrow-string): saturate the offset casts in substring (#10995)
# Which issue does this PR close?
- Closes #10983.
# Rationale for this change
substring takes start as i64 and length as Option<u64> and cast both
straight into
the offset type. on the Utf8 and Binary arms a start at or above 2^31
wrapped
negative, and `byte_substring` reads a negative start as counting from
the end of
the value, so the call did not fail, it quietly did something else.
LargeUtf8 and
LargeBinary narrow to i64 and were not affected, so the same call
returned
different data depending only on the offset width of the input.
saturating rather than rejecting, per the discussion on the issue. a
start past the
end of every value is what the caller asked for, and it is already what
the 64 bit
arms do.
# What changes are included in this PR?
start and length saturate into the offset type at the dispatch instead
of being
cast. inside `byte_substring` the two additions that can carry a
saturated value
past the offset type go through `checked_add` and clamp to the end of
the value.
one thing i did not expect. the length cast was wrong on all four arms,
not only
the 32 bit ones. `u64::MAX as i64` is -1, and a negative length puts the
end of a
substring before its start, which drives the output offsets negative and
then
allocates on the result of as_usize. i only found it because the test
compares the
narrow and wide arms against each other and the wide one panicked. so
LargeUtf8 and
LargeBinary are fixed here too.
the third addition, pair[1] + start on the negative branch, is left
alone. pair[1]
is non-negative and start is at worst i32::MIN, so it cannot overflow.
# Are these changes tested?
yes. out_of_range_start_and_length_match_the_64_bit_arms runs four out
of range
starts against three lengths, on Utf8 against LargeUtf8 and on Binary
against
LargeBinary, and asserts the pairs agree. it also pins the answer
itself, since
agreeing on the wrong result would still pass. skipping 2^31 characters
of a five
character string gives empty strings, and a start that already fits is
untouched.
on current main that test fails twice. Utf8 returns ["hello", "world"]
where
LargeUtf8 returns ["", ""], and Some(u64::MAX) panics inside
`MutableBuffer`.
arrow-string is 189 passed, and fmt and clippy with -D warnings are
clean.
# Are there any user-facing changes?
yes, for input that was previously wrong. a start or length outside the
offset type
now saturates, so Utf8 and Binary return what LargeUtf8 and LargeBinary
already
returned. values that fit are unaffected.
---
arrow-string/src/substring.rs | 106 ++++++++++++++++++++++++++++++++++++------
1 file changed, 93 insertions(+), 13 deletions(-)
diff --git a/arrow-string/src/substring.rs b/arrow-string/src/substring.rs
index 6422f7b167..82171b5a1d 100644
--- a/arrow-string/src/substring.rs
+++ b/arrow-string/src/substring.rs
@@ -26,7 +26,7 @@ use arrow_array::types::*;
use arrow_array::*;
use arrow_buffer::{ArrowNativeType, MutableBuffer, NullBuffer, OffsetBuffer};
use arrow_schema::{ArrowError, DataType};
-use num_traits::Zero;
+use num_traits::{CheckedAdd, Zero};
use std::cmp::Ordering;
use std::sync::Arc;
@@ -81,13 +81,17 @@ pub fn substring(
let values = substring(dictionary.values(), start, length)?;
Ok(Arc::new(dictionary.with_values(values)))
}
- DataType::LargeBinary => {
- byte_substring(array.as_binary::<i64>(), start, length.map(|e| e
as i64))
- }
+ DataType::LargeBinary => byte_substring(
+ array.as_binary::<i64>(),
+ start,
+ // ensure we saturate to not wrap around to a negative length
+ length.map(u64_to_i64_saturating),
+ ),
DataType::Binary => byte_substring(
array.as_binary::<i32>(),
- start as i32,
- length.map(|e| e as i32),
+ // ensure to saturate to avoid wrapping to negative which is a
different behaviour
+ i64_to_i32_saturating(start),
+ length.map(u64_to_i32_saturating),
),
DataType::FixedSizeBinary(old_len) => {
let old_len: usize = (*old_len)
@@ -95,13 +99,17 @@ pub fn substring(
.expect("negative FixedSizeBinary value length");
fixed_size_binary_substring(array.as_fixed_size_binary(), old_len,
start, length)
}
- DataType::LargeUtf8 => {
- byte_substring(array.as_string::<i64>(), start, length.map(|e| e
as i64))
- }
+ DataType::LargeUtf8 => byte_substring(
+ array.as_string::<i64>(),
+ start,
+ // ensure we saturate to not wrap around to a negative length
+ length.map(u64_to_i64_saturating),
+ ),
DataType::Utf8 => byte_substring(
array.as_string::<i32>(),
- start as i32,
- length.map(|e| e as i32),
+ // ensure to saturate to avoid wrapping to negative which is a
different behaviour
+ i64_to_i32_saturating(start),
+ length.map(u64_to_i32_saturating),
),
DataType::Utf8View => string_view_substring(array.as_string_view(),
start, length),
DataType::BinaryView => binary_view_substring(array.as_binary_view(),
start, length),
@@ -316,6 +324,18 @@ fn binary_view_substring(
Ok(Arc::new(builder.finish()))
}
+fn i64_to_i32_saturating(value: i64) -> i32 {
+ value.clamp(i32::MIN as i64, i32::MAX as i64) as i32
+}
+
+fn u64_to_i32_saturating(value: u64) -> i32 {
+ value.min(i32::MAX as u64) as i32
+}
+
+fn u64_to_i64_saturating(value: u64) -> i64 {
+ value.min(i64::MAX as u64) as i64
+}
+
fn byte_substring<T: ByteArrayType>(
array: &GenericByteArray<T>,
start: T::Offset,
@@ -357,12 +377,21 @@ where
.windows(2)
.try_for_each(|pair| -> Result<(), ArrowError> {
let new_start = match start.cmp(&zero) {
- Ordering::Greater => check_char_boundary((pair[0] +
start).min(pair[1]))?,
+ Ordering::Greater => {
+ // a saturated start can carry pair[0] + start past the
offset
+ // type. that means past the end of this value, so clamp
to the
+ // end rather than let the add wrap.
+ let shifted =
pair[0].checked_add(&start).unwrap_or(pair[1]);
+ check_char_boundary(shifted.min(pair[1]))?
+ }
Ordering::Equal => pair[0],
Ordering::Less => check_char_boundary((pair[1] +
start).max(pair[0]))?,
};
let new_end = match length {
- Some(length) => check_char_boundary((length +
new_start).min(pair[1]))?,
+ Some(length) => {
+ let end =
length.checked_add(&new_start).unwrap_or(pair[1]);
+ check_char_boundary(end.min(pair[1]))?
+ }
None => pair[1],
};
len_so_far += new_end - new_start;
@@ -1236,4 +1265,55 @@ mod tests {
vec![Some("hel"), Some("bye")]
);
}
+
+ #[test]
+ fn out_of_range_start_and_length_match_the_64_bit_arms() {
+ // use 64 bit offset versions as expected behaviour for extreme start
& length values
+ // which should saturate and not wrap
+ let values = vec![Some("hello"), Some("world"), None];
+ let utf8 = StringArray::from(values.clone());
+ let large = LargeStringArray::from(values.clone());
+ let binary = BinaryArray::from_iter(values.iter().map(|v| v.map(|s|
s.as_bytes())));
+ let large_binary =
+ LargeBinaryArray::from_iter(values.iter().map(|v| v.map(|s|
s.as_bytes())));
+
+ // starts and lengths that do not survive a cast to i32
+ let starts: [i64; 4] = [1 << 31, (1 << 31) + 5, 1 << 32, i64::MAX];
+ let lengths: [Option<u64>; 3] = [None, Some(1 << 31), Some(u64::MAX)];
+
+ for start in starts {
+ for length in lengths {
+ let narrow = substring(&utf8, start, length).unwrap();
+ let wide = substring(&large, start, length).unwrap();
+ assert_eq!(
+ narrow.as_string::<i32>().iter().collect::<Vec<_>>(),
+ wide.as_string::<i64>().iter().collect::<Vec<_>>(),
+ "Utf8 and LargeUtf8 disagree at start {start}, length
{length:?}"
+ );
+
+ let narrow = substring(&binary, start, length).unwrap();
+ let wide = substring(&large_binary, start, length).unwrap();
+ assert_eq!(
+ narrow.as_binary::<i32>().iter().collect::<Vec<_>>(),
+ wide.as_binary::<i64>().iter().collect::<Vec<_>>(),
+ "Binary and LargeBinary disagree at start {start}, length
{length:?}"
+ );
+ }
+ }
+
+ // and the answer itself is the sensible one: skipping more characters
+ // than the value holds leaves nothing behind.
+ let out = substring(&utf8, 1 << 31, None).unwrap();
+ assert_eq!(
+ out.as_string::<i32>().iter().collect::<Vec<_>>(),
+ vec![Some(""), Some(""), None]
+ );
+
+ // starts that already fit are untouched
+ let out = substring(&utf8, 3, None).unwrap();
+ assert_eq!(
+ out.as_string::<i32>().iter().collect::<Vec<_>>(),
+ vec![Some("lo"), Some("ld"), None]
+ );
+ }
}
