Skip to main content

arrow_string/
substring.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! Defines kernel to extract a substring of an Array
6//! Supported array types:
7//! [GenericStringArray], [GenericBinaryArray], [GenericByteViewArray],
8//! [FixedSizeBinaryArray], [DictionaryArray]
9
10use arrow_array::builder::{BinaryViewBuilder, StringViewBuilder};
11use arrow_array::cast::AsArray;
12use arrow_array::types::*;
13use arrow_array::*;
14use arrow_buffer::{ArrowNativeType, MutableBuffer, NullBuffer, OffsetBuffer};
15use arrow_schema::{ArrowError, DataType};
16use num_traits::{CheckedAdd, Zero};
17use std::cmp::Ordering;
18use std::sync::Arc;
19
20/// Returns an [`ArrayRef`] with substrings of all the elements in `array`.
21///
22/// # Arguments
23///
24/// * `start` - The start index of all substrings.
25///   If `start >= 0`, then count from the start of the string,
26///   otherwise count from the end of the string.
27///
28/// * `length`(option) - The length of all substrings.
29///   If `length` is [None], then the substring is from `start` to the end of the string.
30///
31/// Attention: Both `start` and `length` are counted by byte, not by char.
32///
33/// # Basic usage
34/// ```
35/// # use arrow_array::StringArray;
36/// # use arrow_string::substring::substring;
37/// let array = StringArray::from(vec![Some("arrow"), None, Some("rust")]);
38/// let result = substring(&array, 1, Some(4)).unwrap();
39/// let result = result.as_any().downcast_ref::<StringArray>().unwrap();
40/// assert_eq!(result, &StringArray::from(vec![Some("rrow"), None, Some("ust")]));
41/// ```
42///
43/// # Error
44/// - The function errors when the passed array is not a [`GenericStringArray`],
45///   [`GenericBinaryArray`], [`FixedSizeBinaryArray`] or [`DictionaryArray`]
46///   with supported array type as its value type.
47/// - The function errors if the offset of a substring in the input array is
48///   at invalid char boundary (only for \[Large\]String array).
49///   It is recommended to use [`substring_by_char`] if the input array may
50///   contain non-ASCII chars.
51///
52/// ## Example of trying to get an invalid utf-8 format substring
53/// ```
54/// # use arrow_array::StringArray;
55/// # use arrow_string::substring::substring;
56/// let array = StringArray::from(vec![Some("E=mc²")]);
57/// let error = substring(&array, 0, Some(5)).unwrap_err().to_string();
58/// assert!(error.contains("invalid utf-8 boundary"));
59/// ```
60pub fn substring(
61    array: &dyn Array,
62    start: i64,
63    length: Option<u64>,
64) -> Result<ArrayRef, ArrowError> {
65    match array.data_type() {
66        DataType::Dictionary(_, _) => {
67            let dictionary = array.as_any_dictionary();
68            let values = substring(dictionary.values(), start, length)?;
69            Ok(Arc::new(dictionary.with_values(values)))
70        }
71        DataType::LargeBinary => byte_substring(
72            array.as_binary::<i64>(),
73            start,
74            // ensure we saturate to not wrap around to a negative length
75            length.map(u64_to_i64_saturating),
76        ),
77        DataType::Binary => byte_substring(
78            array.as_binary::<i32>(),
79            // ensure to saturate to avoid wrapping to negative which is a different behaviour
80            i64_to_i32_saturating(start),
81            length.map(u64_to_i32_saturating),
82        ),
83        DataType::FixedSizeBinary(old_len) => {
84            let old_len: usize = (*old_len)
85                .try_into()
86                .expect("negative FixedSizeBinary value length");
87            fixed_size_binary_substring(array.as_fixed_size_binary(), old_len, start, length)
88        }
89        DataType::LargeUtf8 => byte_substring(
90            array.as_string::<i64>(),
91            start,
92            // ensure we saturate to not wrap around to a negative length
93            length.map(u64_to_i64_saturating),
94        ),
95        DataType::Utf8 => byte_substring(
96            array.as_string::<i32>(),
97            // ensure to saturate to avoid wrapping to negative which is a different behaviour
98            i64_to_i32_saturating(start),
99            length.map(u64_to_i32_saturating),
100        ),
101        DataType::Utf8View => string_view_substring(array.as_string_view(), start, length),
102        DataType::BinaryView => binary_view_substring(array.as_binary_view(), start, length),
103        _ => Err(ArrowError::ComputeError(format!(
104            "substring does not support type {:?}",
105            array.data_type()
106        ))),
107    }
108}
109
110/// Substrings based on character index
111///
112/// # Arguments
113/// * `array` - The input string array
114///
115/// * `start` - The start index of all substrings.
116///   If `start >= 0`, then count from the start of the string,
117///   otherwise count from the end of the string.
118///
119/// * `length`(option) - The length of all substrings.
120///   If `length` is `None`, then the substring is from `start` to the end of the string.
121///
122/// Attention: Both `start` and `length` are counted by char.
123///
124/// # Performance
125///
126/// This function is slower than [substring]. Theoretically, the time complexity
127/// is `O(n)` where `n` is the length of the value buffer. If the array only
128/// contains ASCII chars, a fast path avoids decoding UTF-8 altogether and the
129/// performance is comparable to [substring].
130///
131/// # Basic usage
132/// ```
133/// # use arrow_array::StringArray;
134/// # use arrow_string::substring::substring_by_char;
135/// let array = StringArray::from(vec![Some("arrow"), None, Some("Γ ⊢x:T")]);
136/// let result = substring_by_char(&array, 1, Some(4)).unwrap();
137/// assert_eq!(result, StringArray::from(vec![Some("rrow"), None, Some(" ⊢x:")]));
138/// ```
139pub fn substring_by_char<OffsetSize: OffsetSizeTrait>(
140    array: &GenericStringArray<OffsetSize>,
141    start: i64,
142    length: Option<u64>,
143) -> Result<GenericStringArray<OffsetSize>, ArrowError> {
144    let length = length.map(|len| usize::try_from(len).unwrap_or(usize::MAX));
145
146    if array.is_ascii() {
147        // One char is one byte, so the byte offsets can be computed arithmetically.
148        Ok(substring_by_char_impl(array, length, |val| {
149            ascii_bounds(val, start, length)
150        }))
151    } else {
152        // A char occupies at most 4 bytes.
153        let max_element_len = length.map(|len| len.saturating_mul(4));
154        Ok(substring_by_char_impl(array, max_element_len, |val| {
155            utf8_bounds(val, start, length)
156        }))
157    }
158}
159
160/// Builds the output of [`substring_by_char`], delegating to `bounds` to locate the
161/// substring of each value.
162///
163/// * `max_element_len` - an upper bound, in bytes, on the size of a single output
164///   element, used to avoid over-allocating the value buffer. [None] if unbounded.
165fn substring_by_char_impl<OffsetSize: OffsetSizeTrait, F: Fn(&str) -> (usize, usize)>(
166    array: &GenericStringArray<OffsetSize>,
167    max_element_len: Option<usize>,
168    bounds: F,
169) -> GenericStringArray<OffsetSize> {
170    let mut vals = Vec::with_capacity({
171        let offsets = array.value_offsets();
172        let input_len = (offsets[array.len()] - offsets[0]).to_usize().unwrap();
173        match max_element_len {
174            Some(len) => input_len.min(array.len().saturating_mul(len)),
175            None => input_len,
176        }
177    });
178    let mut new_offsets = Vec::with_capacity(array.len() + 1);
179    new_offsets.push(OffsetSize::zero());
180
181    array.iter().for_each(|val| {
182        if let Some(val) = val {
183            let (start_offset, end_offset) = bounds(val);
184            vals.extend_from_slice(&val.as_bytes()[start_offset..end_offset]);
185        }
186        new_offsets.push(OffsetSize::from_usize(vals.len()).unwrap());
187    });
188
189    let offsets = OffsetBuffer::new(new_offsets.into());
190    let values = vals.into();
191    let nulls = array
192        .nulls()
193        .map(|n| n.inner().sliced())
194        .and_then(|b| NullBuffer::from_unsliced_buffer(b, array.len()));
195    GenericStringArray::<OffsetSize>::new(offsets, values, nulls)
196}
197
198/// Returns the `start` and `end` byte offset of the substring of an ASCII `val`, where
199/// one char is one byte.
200///
201/// * `start` - the start char index of the substring, counted from the end if negative
202/// * `length` - the char length of the substring, or [None] to take the rest of `val`
203#[inline]
204fn ascii_bounds(val: &str, start: i64, length: Option<usize>) -> (usize, usize) {
205    let len = val.len();
206    let start_offset = if start >= 0 {
207        usize::try_from(start).unwrap_or(usize::MAX).min(len)
208    } else {
209        len.saturating_sub(usize::try_from(start.unsigned_abs()).unwrap_or(usize::MAX))
210    };
211    let end_offset = length.map_or(len, |length| start_offset.saturating_add(length).min(len));
212    (start_offset, end_offset)
213}
214
215/// Returns the `start` and `end` byte offset of the substring of an arbitrary UTF-8 `val`.
216///
217/// * `start` - the start char index of the substring, counted from the end if negative
218/// * `length` - the char length of the substring, or [None] to take the rest of `val`
219#[inline]
220fn utf8_bounds(val: &str, start: i64, length: Option<usize>) -> (usize, usize) {
221    let len = val.len();
222    let start_offset = if start >= 0 {
223        val.char_indices()
224            .nth(usize::try_from(start).unwrap_or(usize::MAX))
225            .map_or(len, |(offset, _)| offset)
226    } else {
227        // `start` is negative, so `nth_back` counts back from the last char. Strings with
228        // fewer than `-start` chars start at 0.
229        let back = usize::try_from(start.unsigned_abs()).unwrap_or(usize::MAX);
230        val.char_indices()
231            .nth_back(back - 1)
232            .map_or(0, |(offset, _)| offset)
233    };
234    let end_offset = length.map_or(len, |length| {
235        // Every char is at least one byte, so the rest of `val` is shorter than `length`
236        // chars and there is nothing to scan for.
237        if length >= len - start_offset {
238            return len;
239        }
240        val[start_offset..]
241            .char_indices()
242            .nth(length)
243            .map_or(len, |(offset, _)| start_offset + offset)
244    });
245    (start_offset, end_offset)
246}
247
248/// Byte range of one element, following the same rules as [`byte_substring`].
249fn view_substring_range(
250    original_length: usize,
251    start: i64,
252    substring_length: Option<u64>,
253) -> (usize, usize) {
254    let original_length = original_length as i64;
255    let new_start = match start.cmp(&0) {
256        Ordering::Greater => start.min(original_length),
257        Ordering::Equal => 0,
258        Ordering::Less => (original_length + start).max(0),
259    };
260    let new_end = match substring_length {
261        Some(length) => new_start
262            .saturating_add(u64_to_i64_saturating(length))
263            .min(original_length),
264        None => original_length,
265    };
266    (new_start as usize, new_end as usize)
267}
268
269fn string_view_substring(
270    array: &StringViewArray,
271    start: i64,
272    length: Option<u64>,
273) -> Result<ArrayRef, ArrowError> {
274    let mut builder = StringViewBuilder::with_capacity(array.len());
275
276    for idx in 0..array.len() {
277        if array.is_null(idx) {
278            builder.append_null();
279            continue;
280        }
281        let value = array.value(idx);
282        let (new_start, new_end) = view_substring_range(value.len(), start, length);
283        for offset in [new_start, new_end] {
284            if !value.is_char_boundary(offset) {
285                return Err(ArrowError::ComputeError(format!(
286                    "The offset {offset} is at an invalid utf-8 boundary."
287                )));
288            }
289        }
290        builder.append_value(&value[new_start..new_end]);
291    }
292
293    Ok(Arc::new(builder.finish()))
294}
295
296fn binary_view_substring(
297    array: &BinaryViewArray,
298    start: i64,
299    length: Option<u64>,
300) -> Result<ArrayRef, ArrowError> {
301    let mut builder = BinaryViewBuilder::with_capacity(array.len());
302
303    for idx in 0..array.len() {
304        if array.is_null(idx) {
305            builder.append_null();
306            continue;
307        }
308        let value = array.value(idx);
309        let (new_start, new_end) = view_substring_range(value.len(), start, length);
310        builder.append_value(&value[new_start..new_end]);
311    }
312
313    Ok(Arc::new(builder.finish()))
314}
315
316fn i64_to_i32_saturating(value: i64) -> i32 {
317    value.clamp(i32::MIN as i64, i32::MAX as i64) as i32
318}
319
320fn u64_to_i32_saturating(value: u64) -> i32 {
321    value.min(i32::MAX as u64) as i32
322}
323
324fn u64_to_i64_saturating(value: u64) -> i64 {
325    value.min(i64::MAX as u64) as i64
326}
327
328fn byte_substring<T: ByteArrayType>(
329    array: &GenericByteArray<T>,
330    start: T::Offset,
331    length: Option<T::Offset>,
332) -> Result<ArrayRef, ArrowError>
333where
334    <T as ByteArrayType>::Native: PartialEq,
335{
336    let offsets = array.value_offsets();
337    let data = array.value_data();
338    let zero = <T::Offset as Zero>::zero();
339
340    // When array is [Large]StringArray, we will check whether `offset` is at a valid char boundary.
341    let check_char_boundary = {
342        let first = array.offsets().first().as_usize();
343        let last = array.offsets().last().as_usize();
344        move |offset: T::Offset| {
345            if !matches!(T::DATA_TYPE, DataType::Utf8 | DataType::LargeUtf8) {
346                return Ok(offset);
347            }
348            // Safety: in a StringArray, the bytes between the first and last offsets
349            // are valid UTF-8. The bytes outside that range need not be.
350            let data_str = unsafe { std::str::from_utf8_unchecked(&data[first..last]) };
351            let offset_usize = offset.as_usize();
352            if data_str.is_char_boundary(offset_usize - first) {
353                Ok(offset)
354            } else {
355                Err(ArrowError::ComputeError(format!(
356                    "The offset {offset_usize} is at an invalid utf-8 boundary."
357                )))
358            }
359        }
360    };
361
362    // start and end offsets of all substrings
363    let mut new_starts_ends: Vec<(T::Offset, T::Offset)> = Vec::with_capacity(array.len());
364    let mut new_offsets: Vec<T::Offset> = Vec::with_capacity(array.len() + 1);
365    let mut len_so_far = zero;
366    new_offsets.push(zero);
367
368    offsets
369        .windows(2)
370        .try_for_each(|pair| -> Result<(), ArrowError> {
371            let new_start = match start.cmp(&zero) {
372                Ordering::Greater => {
373                    // a saturated start can carry pair[0] + start past the offset
374                    // type. that means past the end of this value, so clamp to the
375                    // end rather than let the add wrap.
376                    let shifted = pair[0].checked_add(&start).unwrap_or(pair[1]);
377                    check_char_boundary(shifted.min(pair[1]))?
378                }
379                Ordering::Equal => pair[0],
380                Ordering::Less => check_char_boundary((pair[1] + start).max(pair[0]))?,
381            };
382            let new_end = match length {
383                Some(length) => {
384                    let end = length.checked_add(&new_start).unwrap_or(pair[1]);
385                    check_char_boundary(end.min(pair[1]))?
386                }
387                None => pair[1],
388            };
389            len_so_far += new_end - new_start;
390            new_starts_ends.push((new_start, new_end));
391            new_offsets.push(len_so_far);
392            Ok(())
393        })?;
394
395    // concatenate substrings into a buffer
396    let mut new_values = MutableBuffer::try_with_capacity(new_offsets.last().unwrap().as_usize())
397        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
398
399    new_starts_ends.iter().for_each(|(start, end)| {
400        let start = start.as_usize();
401        let end = end.as_usize();
402        new_values.extend_from_slice(&data[start..end]);
403    });
404
405    let offsets = OffsetBuffer::new(new_offsets.into());
406    let values = new_values.into();
407    let nulls = array
408        .nulls()
409        .map(|n| n.inner().sliced())
410        .and_then(|b| NullBuffer::from_unsliced_buffer(b, array.len()));
411    Ok(Arc::new(GenericByteArray::<T>::new(offsets, values, nulls)))
412}
413
414fn fixed_size_binary_substring(
415    array: &FixedSizeBinaryArray,
416    old_len: usize,
417    start: i64,
418    length: Option<u64>,
419) -> Result<ArrayRef, ArrowError> {
420    let new_start = match start.cmp(&0) {
421        Ordering::Greater => usize::try_from(start).unwrap_or(usize::MAX).min(old_len),
422        Ordering::Equal => 0,
423        Ordering::Less => {
424            let offset = usize::try_from(start.unsigned_abs()).unwrap_or(usize::MAX);
425            old_len.saturating_sub(offset)
426        }
427    };
428
429    let new_len = match length {
430        Some(len) => usize::try_from(len)
431            .unwrap_or(usize::MAX)
432            .min(old_len - new_start),
433        None => old_len - new_start,
434    };
435
436    // build value buffer
437    let num_of_elements = array.len();
438    let data = array.value_data();
439    let capacity = num_of_elements
440        .checked_mul(new_len)
441        .ok_or_else(|| ArrowError::MemoryError("substring output size overflow".into()))?;
442    let mut new_values = MutableBuffer::try_with_capacity(capacity)
443        .map_err(|e| ArrowError::MemoryError(e.to_string()))?;
444    (0..num_of_elements)
445        .map(|idx| {
446            let offset = idx * array.value_size();
447            (offset + new_start, offset + new_start + new_len)
448        })
449        .for_each(|(start, end)| new_values.extend_from_slice(&data[start..end]));
450
451    let mut nulls = array
452        .nulls()
453        .map(|n| n.inner().sliced())
454        .and_then(|b| NullBuffer::from_unsliced_buffer(b, num_of_elements));
455
456    if new_len == 0 && nulls.is_none() {
457        // FixedSizeBinaryArray::new takes length from the values buffer, except when size == 0.
458        // In that case it uses the null buffer length, so preserve the original length here.
459        // Example: ["", "", ""] -> substring(..., 1, Some(2)) should keep len=3;
460        // otherwise it collapses to an empty array (len=0).
461        nulls = Some(NullBuffer::new_valid(num_of_elements));
462    }
463
464    let new_len: i32 = new_len.try_into().expect("new_len overflow");
465
466    Ok(Arc::new(FixedSizeBinaryArray::new(
467        new_len,
468        new_values.into(),
469        nulls,
470    )))
471}
472
473#[cfg(test)]
474mod tests {
475    use super::*;
476    use arrow_buffer::BooleanBuffer;
477    use arrow_buffer::Buffer;
478
479    /// A helper macro to generate test cases.
480    /// # Arguments
481    /// * `input` - A vector which array can be built from.
482    /// * `start` - The start index of the substring.
483    /// * `len` - The length of the substring.
484    /// * `result` - The expected result of substring, which is a vector that array can be built from.
485    /// # Return
486    /// A vector of `(input, start, len, result)`.
487    ///
488    /// Users can provide any number of `(start, len, result)` to generate test cases for one `input`.
489    macro_rules! gen_test_cases {
490        ($input:expr, $(($start:expr, $len:expr, $result:expr)), *) => {
491            [
492                $(
493                    ($input.clone(), $start, $len, $result),
494                )*
495            ]
496        };
497    }
498
499    /// A helper macro to test the substring functions.
500    /// # Arguments
501    /// * `cases` - The test cases which is a vector of `(input, start, len, result)`.
502    ///   Please look at [`gen_test_cases`] to find how to generate it.
503    /// * `array_ty` - The array type.
504    /// * `substring_fn` - Either [`substring`] or [`substring_by_char`].
505    macro_rules! do_test {
506        ($cases:expr, $array_ty:ty, $substring_fn:ident) => {
507            $cases
508                .into_iter()
509                .for_each(|(array, start, length, expected)| {
510                    let array = <$array_ty>::from(array);
511                    let result = $substring_fn(&array, start, length).unwrap();
512                    let result = result.as_any().downcast_ref::<$array_ty>().unwrap();
513                    let expected = <$array_ty>::from(expected);
514                    assert_eq!(&expected, result);
515                })
516        };
517    }
518
519    /// A helper macro to test the substring functions for array types only implementing TryFrom.
520    macro_rules! do_test_tryfrom {
521        ($cases:expr, $array_ty:ty, $substring_fn:ident) => {
522            $cases
523                .into_iter()
524                .for_each(|(array, start, length, expected)| {
525                    let array = <$array_ty>::try_from(array).unwrap();
526                    let result = $substring_fn(&array, start, length).unwrap();
527                    let result = result.as_any().downcast_ref::<$array_ty>().unwrap();
528                    let expected = <$array_ty>::try_from(expected).unwrap();
529                    assert_eq!(&expected, result);
530                })
531        };
532    }
533
534    fn with_nulls_generic_binary<O: OffsetSizeTrait>() {
535        let input = vec![
536            Some(b"hello".as_slice()),
537            None,
538            Some(&[0xf8, 0xf9, 0xff, 0xfa]),
539        ];
540        // all-nulls array is always identical
541        let base_case = gen_test_cases!(
542            vec![None, None, None],
543            (-1, Some(1), vec![None, None, None])
544        );
545        let cases = gen_test_cases!(
546            input,
547            // identity
548            (0, None, input.clone()),
549            // 0 length -> Nothing
550            (0, Some(0), vec![Some(&[]), None, Some(&[])]),
551            // high start -> Nothing
552            (1000, Some(0), vec![Some(&[]), None, Some(&[])]),
553            // high negative start -> identity
554            (-1000, None, input.clone()),
555            // high length -> identity
556            (0, Some(1000), input.clone())
557        );
558
559        do_test!(
560            [&base_case[..], &cases[..]].concat(),
561            GenericBinaryArray<O>,
562            substring
563        );
564    }
565
566    #[test]
567    fn with_nulls_binary() {
568        with_nulls_generic_binary::<i32>()
569    }
570
571    #[test]
572    fn with_nulls_large_binary() {
573        with_nulls_generic_binary::<i64>()
574    }
575
576    fn without_nulls_generic_binary<O: OffsetSizeTrait>() {
577        let input = vec![b"hello".as_slice(), b"", &[0xf8, 0xf9, 0xff, 0xfa]];
578        // empty array is always identical
579        let base_case = gen_test_cases!(
580            vec![b"".as_slice(), b"", b""],
581            (2, Some(1), vec![b"".as_slice(), b"", b""])
582        );
583        let cases = gen_test_cases!(
584            input,
585            // identity
586            (0, None, input.clone()),
587            // increase start
588            (1, None, vec![b"ello", b"", &[0xf9, 0xff, 0xfa]]),
589            (2, None, vec![b"llo", b"", &[0xff, 0xfa]]),
590            (3, None, vec![b"lo", b"", &[0xfa]]),
591            (10, None, vec![b"", b"", b""]),
592            // increase start negatively
593            (-1, None, vec![b"o", b"", &[0xfa]]),
594            (-2, None, vec![b"lo", b"", &[0xff, 0xfa]]),
595            (-3, None, vec![b"llo", b"", &[0xf9, 0xff, 0xfa]]),
596            (-10, None, input.clone()),
597            // increase length
598            (1, Some(1), vec![b"e", b"", &[0xf9]]),
599            (1, Some(2), vec![b"el", b"", &[0xf9, 0xff]]),
600            (1, Some(3), vec![b"ell", b"", &[0xf9, 0xff, 0xfa]]),
601            (1, Some(4), vec![b"ello", b"", &[0xf9, 0xff, 0xfa]]),
602            (-3, Some(1), vec![b"l", b"", &[0xf9]]),
603            (-3, Some(2), vec![b"ll", b"", &[0xf9, 0xff]]),
604            (-3, Some(3), vec![b"llo", b"", &[0xf9, 0xff, 0xfa]]),
605            (-3, Some(4), vec![b"llo", b"", &[0xf9, 0xff, 0xfa]])
606        );
607
608        do_test!(
609            [&base_case[..], &cases[..]].concat(),
610            GenericBinaryArray<O>,
611            substring
612        );
613    }
614
615    #[test]
616    fn without_nulls_binary() {
617        without_nulls_generic_binary::<i32>()
618    }
619
620    #[test]
621    fn without_nulls_large_binary() {
622        without_nulls_generic_binary::<i64>()
623    }
624
625    fn generic_binary_with_non_zero_offset<O: OffsetSizeTrait>() {
626        let values = 0_u8..15;
627        let offsets = &[
628            O::zero(),
629            O::from_usize(5).unwrap(),
630            O::from_usize(10).unwrap(),
631            O::from_usize(15).unwrap(),
632        ];
633        // set the first and third element to be valid
634        let bitmap = [0b101_u8];
635
636        let offsets = OffsetBuffer::new(Buffer::from_slice_ref(offsets).into());
637        let values = Buffer::from_iter(values);
638        let nulls = Some(NullBuffer::new(BooleanBuffer::new(
639            Buffer::from(bitmap),
640            0,
641            3,
642        )));
643        // array is `[null, [10, 11, 12, 13, 14]]`
644        let array = GenericBinaryArray::<O>::new(offsets, values, nulls).slice(1, 2);
645        // result is `[null, [11, 12, 13, 14]]`
646        let result = substring(&array, 1, None).unwrap();
647        let result = result
648            .as_any()
649            .downcast_ref::<GenericBinaryArray<O>>()
650            .unwrap();
651        let expected =
652            GenericBinaryArray::<O>::from_opt_vec(vec![None, Some(&[11_u8, 12, 13, 14])]);
653        assert_eq!(result, &expected);
654    }
655
656    #[test]
657    fn binary_with_non_zero_offset() {
658        generic_binary_with_non_zero_offset::<i32>()
659    }
660
661    #[test]
662    fn large_binary_with_non_zero_offset() {
663        generic_binary_with_non_zero_offset::<i64>()
664    }
665
666    #[test]
667    fn with_nulls_fixed_size_binary() {
668        let input = vec![Some(b"cat".as_slice()), None, Some(&[0xf8, 0xf9, 0xff])];
669        // all-nulls array is always identical
670        let base_case =
671            gen_test_cases!(vec![None, None, None], (3, Some(2), vec![None, None, None]));
672        let cases = gen_test_cases!(
673            input,
674            // identity
675            (0, None, input.clone()),
676            // increase start
677            (1, None, vec![Some(b"at"), None, Some(&[0xf9, 0xff])]),
678            (2, None, vec![Some(b"t"), None, Some(&[0xff])]),
679            (3, None, vec![Some(b""), None, Some(b"")]),
680            (10, None, vec![Some(b""), None, Some(b"")]),
681            // increase start negatively
682            (-1, None, vec![Some(b"t"), None, Some(&[0xff])]),
683            (-2, None, vec![Some(b"at"), None, Some(&[0xf9, 0xff])]),
684            (-3, None, input.clone()),
685            (-10, None, input.clone()),
686            // increase length
687            (1, Some(1), vec![Some(b"a"), None, Some(&[0xf9])]),
688            (1, Some(2), vec![Some(b"at"), None, Some(&[0xf9, 0xff])]),
689            (1, Some(3), vec![Some(b"at"), None, Some(&[0xf9, 0xff])]),
690            (-3, Some(1), vec![Some(b"c"), None, Some(&[0xf8])]),
691            (-3, Some(2), vec![Some(b"ca"), None, Some(&[0xf8, 0xf9])]),
692            (-3, Some(3), input.clone()),
693            (-3, Some(4), input.clone())
694        );
695
696        do_test_tryfrom!(
697            [&base_case[..], &cases[..]].concat(),
698            FixedSizeBinaryArray,
699            substring
700        );
701    }
702
703    #[test]
704    fn without_nulls_fixed_size_binary() {
705        let input = vec![b"cat".as_slice(), b"dog", &[0xf8, 0xf9, 0xff]];
706        // empty array is always identical
707        let base_case = gen_test_cases!(
708            vec![b"".as_slice(), &[], &[]],
709            (1, Some(2), vec![b"".as_slice(), &[], &[]])
710        );
711        let cases = gen_test_cases!(
712            input,
713            // identity
714            (0, None, input.clone()),
715            // increase start
716            (1, None, vec![b"at", b"og", &[0xf9, 0xff]]),
717            (2, None, vec![b"t", b"g", &[0xff]]),
718            (3, None, vec![&[], &[], &[]]),
719            (10, None, vec![&[], &[], &[]]),
720            // increase start negatively
721            (-1, None, vec![b"t", b"g", &[0xff]]),
722            (-2, None, vec![b"at", b"og", &[0xf9, 0xff]]),
723            (-3, None, input.clone()),
724            (-10, None, input.clone()),
725            // increase length
726            (1, Some(1), vec![b"a", b"o", &[0xf9]]),
727            (1, Some(2), vec![b"at", b"og", &[0xf9, 0xff]]),
728            (1, Some(3), vec![b"at", b"og", &[0xf9, 0xff]]),
729            (-3, Some(1), vec![b"c", b"d", &[0xf8]]),
730            (-3, Some(2), vec![b"ca", b"do", &[0xf8, 0xf9]]),
731            (-3, Some(3), input.clone()),
732            (-3, Some(4), input.clone())
733        );
734
735        do_test_tryfrom!(
736            [&base_case[..], &cases[..]].concat(),
737            FixedSizeBinaryArray,
738            substring
739        );
740    }
741
742    #[test]
743    fn fixed_size_binary_with_non_zero_offset() {
744        let values = b"hellotherearrow";
745        // set the first and third element to be valid
746        let bits_v = [0b101_u8];
747
748        let nulls = Some(NullBuffer::new(BooleanBuffer::new(
749            Buffer::from(bits_v),
750            0,
751            3,
752        )));
753        // array is `[null, "arrow"]`
754        let array = FixedSizeBinaryArray::new(5, Buffer::from(values), nulls).slice(1, 2);
755        // result is `[null, "rrow"]`
756        let result = substring(&array, 1, None).unwrap();
757        let result = result
758            .as_any()
759            .downcast_ref::<FixedSizeBinaryArray>()
760            .unwrap();
761        let expected = FixedSizeBinaryArray::try_from_sparse_iter_with_size(
762            vec![None, Some(b"rrow")].into_iter(),
763            4,
764        )
765        .unwrap();
766        assert_eq!(result, &expected);
767    }
768
769    fn with_nulls_generic_string<O: OffsetSizeTrait>() {
770        let input = vec![Some("hello"), None, Some("word")];
771        // all-nulls array is always identical
772        let base_case = gen_test_cases!(vec![None, None, None], (0, None, vec![None, None, None]));
773        let cases = gen_test_cases!(
774            input,
775            // identity
776            (0, None, input.clone()),
777            // 0 length -> Nothing
778            (0, Some(0), vec![Some(""), None, Some("")]),
779            // high start -> Nothing
780            (1000, Some(0), vec![Some(""), None, Some("")]),
781            // high negative start -> identity
782            (-1000, None, input.clone()),
783            // high length -> identity
784            (0, Some(1000), input.clone())
785        );
786
787        do_test!(
788            [&base_case[..], &cases[..]].concat(),
789            GenericStringArray<O>,
790            substring
791        );
792    }
793
794    #[test]
795    fn with_nulls_string() {
796        with_nulls_generic_string::<i32>()
797    }
798
799    #[test]
800    fn with_nulls_large_string() {
801        with_nulls_generic_string::<i64>()
802    }
803
804    fn without_nulls_generic_string<O: OffsetSizeTrait>() {
805        let input = vec!["hello", "", "word"];
806        // empty array is always identical
807        let base_case = gen_test_cases!(vec!["", "", ""], (0, None, vec!["", "", ""]));
808        let cases = gen_test_cases!(
809            input,
810            // identity
811            (0, None, input.clone()),
812            (1, None, vec!["ello", "", "ord"]),
813            (2, None, vec!["llo", "", "rd"]),
814            (3, None, vec!["lo", "", "d"]),
815            (10, None, vec!["", "", ""]),
816            // increase start negatively
817            (-1, None, vec!["o", "", "d"]),
818            (-2, None, vec!["lo", "", "rd"]),
819            (-3, None, vec!["llo", "", "ord"]),
820            (-10, None, input.clone()),
821            // increase length
822            (1, Some(1), vec!["e", "", "o"]),
823            (1, Some(2), vec!["el", "", "or"]),
824            (1, Some(3), vec!["ell", "", "ord"]),
825            (1, Some(4), vec!["ello", "", "ord"]),
826            (-3, Some(1), vec!["l", "", "o"]),
827            (-3, Some(2), vec!["ll", "", "or"]),
828            (-3, Some(3), vec!["llo", "", "ord"]),
829            (-3, Some(4), vec!["llo", "", "ord"])
830        );
831
832        do_test!(
833            [&base_case[..], &cases[..]].concat(),
834            GenericStringArray<O>,
835            substring
836        );
837    }
838
839    #[test]
840    fn without_nulls_string() {
841        without_nulls_generic_string::<i32>()
842    }
843
844    #[test]
845    fn without_nulls_large_string() {
846        without_nulls_generic_string::<i64>()
847    }
848
849    fn generic_string_with_non_zero_offset<O: OffsetSizeTrait>() {
850        let values = b"hellotherearrow";
851        let offsets = &[
852            O::zero(),
853            O::from_usize(5).unwrap(),
854            O::from_usize(10).unwrap(),
855            O::from_usize(15).unwrap(),
856        ];
857        // set the first and third element to be valid
858        let bitmap = [0b101_u8];
859
860        let offsets = OffsetBuffer::new(Buffer::from_slice_ref(offsets).into());
861        let values = Buffer::from(values);
862        let nulls = Some(NullBuffer::new(BooleanBuffer::new(
863            Buffer::from(bitmap),
864            0,
865            3,
866        )));
867        // array is `[null, "arrow"]`
868        let array = GenericStringArray::<O>::new(offsets, values, nulls).slice(1, 2);
869        // result is `[null, "rrow"]`
870        let result = substring(&array, 1, None).unwrap();
871        let result = result
872            .as_any()
873            .downcast_ref::<GenericStringArray<O>>()
874            .unwrap();
875        let expected = GenericStringArray::<O>::from(vec![None, Some("rrow")]);
876        assert_eq!(result, &expected);
877    }
878
879    #[test]
880    fn string_with_non_zero_offset() {
881        generic_string_with_non_zero_offset::<i32>()
882    }
883
884    #[test]
885    fn large_string_with_non_zero_offset() {
886        generic_string_with_non_zero_offset::<i64>()
887    }
888
889    fn with_nulls_generic_string_by_char<O: OffsetSizeTrait>() {
890        let input = vec![Some("hello"), None, Some("Γ ⊢x:T")];
891        // all-nulls array is always identical
892        let base_case = gen_test_cases!(vec![None, None, None], (0, None, vec![None, None, None]));
893        let cases = gen_test_cases!(
894            input,
895            // identity
896            (0, None, input.clone()),
897            // 0 length -> Nothing
898            (0, Some(0), vec![Some(""), None, Some("")]),
899            // high start -> Nothing
900            (1000, Some(0), vec![Some(""), None, Some("")]),
901            // high negative start -> identity
902            (-1000, None, input.clone()),
903            // high length -> identity
904            (0, Some(1000), input.clone())
905        );
906
907        do_test!(
908            [&base_case[..], &cases[..]].concat(),
909            GenericStringArray<O>,
910            substring_by_char
911        );
912    }
913
914    #[test]
915    fn with_nulls_string_by_char() {
916        with_nulls_generic_string_by_char::<i32>()
917    }
918
919    #[test]
920    fn with_nulls_large_string_by_char() {
921        with_nulls_generic_string_by_char::<i64>()
922    }
923
924    fn without_nulls_generic_string_by_char<O: OffsetSizeTrait>() {
925        let input = vec!["hello", "", "Γ ⊢x:T"];
926        // empty array is always identical
927        let base_case = gen_test_cases!(vec!["", "", ""], (0, None, vec!["", "", ""]));
928        let cases = gen_test_cases!(
929            input,
930            //identity
931            (0, None, input.clone()),
932            // increase start
933            (1, None, vec!["ello", "", " ⊢x:T"]),
934            (2, None, vec!["llo", "", "⊢x:T"]),
935            (3, None, vec!["lo", "", "x:T"]),
936            (10, None, vec!["", "", ""]),
937            // increase start negatively
938            (-1, None, vec!["o", "", "T"]),
939            (-2, None, vec!["lo", "", ":T"]),
940            (-4, None, vec!["ello", "", "⊢x:T"]),
941            (-10, None, input.clone()),
942            // increase length
943            (1, Some(1), vec!["e", "", " "]),
944            (1, Some(2), vec!["el", "", " ⊢"]),
945            (1, Some(3), vec!["ell", "", " ⊢x"]),
946            (1, Some(6), vec!["ello", "", " ⊢x:T"]),
947            (-4, Some(1), vec!["e", "", "⊢"]),
948            (-4, Some(2), vec!["el", "", "⊢x"]),
949            (-4, Some(3), vec!["ell", "", "⊢x:"]),
950            (-4, Some(4), vec!["ello", "", "⊢x:T"])
951        );
952
953        do_test!(
954            [&base_case[..], &cases[..]].concat(),
955            GenericStringArray<O>,
956            substring_by_char
957        );
958    }
959
960    #[test]
961    fn without_nulls_string_by_char() {
962        without_nulls_generic_string_by_char::<i32>()
963    }
964
965    #[test]
966    fn without_nulls_large_string_by_char() {
967        without_nulls_generic_string_by_char::<i64>()
968    }
969
970    /// The array is all-ASCII, which takes the fast path of [`substring_by_char`].
971    fn ascii_generic_string_by_char<O: OffsetSizeTrait>() {
972        let input = vec![Some("hello"), None, Some(""), Some("rust")];
973        let cases = gen_test_cases!(
974            input,
975            // identity
976            (0, None, input.clone()),
977            // increase start
978            (1, None, vec![Some("ello"), None, Some(""), Some("ust")]),
979            (4, None, vec![Some("o"), None, Some(""), Some("")]),
980            // high start -> nothing
981            (1000, None, vec![Some(""), None, Some(""), Some("")]),
982            // increase start negatively
983            (-1, None, vec![Some("o"), None, Some(""), Some("t")]),
984            (-4, None, vec![Some("ello"), None, Some(""), Some("rust")]),
985            // high negative start -> identity
986            (-1000, None, input.clone()),
987            // 0 length -> nothing
988            (0, Some(0), vec![Some(""), None, Some(""), Some("")]),
989            // increase length
990            (1, Some(2), vec![Some("el"), None, Some(""), Some("us")]),
991            (-4, Some(2), vec![Some("el"), None, Some(""), Some("ru")]),
992            // high length -> identity
993            (0, Some(1000), input.clone()),
994            // length past the end is clamped, including when it would overflow
995            (
996                1,
997                Some(u64::MAX),
998                vec![Some("ello"), None, Some(""), Some("ust")]
999            )
1000        );
1001
1002        do_test!(cases, GenericStringArray<O>, substring_by_char);
1003    }
1004
1005    #[test]
1006    fn ascii_string_by_char() {
1007        ascii_generic_string_by_char::<i32>()
1008    }
1009
1010    #[test]
1011    fn ascii_large_string_by_char() {
1012        ascii_generic_string_by_char::<i64>()
1013    }
1014
1015    fn generic_string_by_char_with_non_zero_offset<O: OffsetSizeTrait>() {
1016        let values = "S→T = Πx:S.T";
1017        let offsets = &[
1018            O::zero(),
1019            O::from_usize(values.char_indices().nth(3).map(|(pos, _)| pos).unwrap()).unwrap(),
1020            O::from_usize(values.char_indices().nth(6).map(|(pos, _)| pos).unwrap()).unwrap(),
1021            O::from_usize(values.len()).unwrap(),
1022        ];
1023        // set the first and third element to be valid
1024        let bitmap = [0b101_u8];
1025
1026        let offsets = OffsetBuffer::new(Buffer::from_slice_ref(offsets).into());
1027        let values = Buffer::from(values.as_bytes());
1028        let nulls = Some(NullBuffer::new(BooleanBuffer::new(
1029            Buffer::from(bitmap),
1030            0,
1031            3,
1032        )));
1033        // array is `[null, "Πx:S.T"]`
1034        let array = GenericStringArray::<O>::new(offsets, values, nulls).slice(1, 2);
1035        // result is `[null, "x:S.T"]`
1036        let result = substring_by_char(&array, 1, None).unwrap();
1037        let expected = GenericStringArray::<O>::from(vec![None, Some("x:S.T")]);
1038        assert_eq!(result, expected);
1039    }
1040
1041    #[test]
1042    fn string_with_non_zero_offset_by_char() {
1043        generic_string_by_char_with_non_zero_offset::<i32>()
1044    }
1045
1046    #[test]
1047    fn large_string_with_non_zero_offset_by_char() {
1048        generic_string_by_char_with_non_zero_offset::<i64>()
1049    }
1050
1051    #[test]
1052    fn dictionary() {
1053        _dictionary::<Int8Type>();
1054        _dictionary::<Int16Type>();
1055        _dictionary::<Int32Type>();
1056        _dictionary::<Int64Type>();
1057        _dictionary::<UInt8Type>();
1058        _dictionary::<UInt16Type>();
1059        _dictionary::<UInt32Type>();
1060        _dictionary::<UInt64Type>();
1061    }
1062
1063    fn _dictionary<K: ArrowDictionaryKeyType>() {
1064        const TOTAL: i32 = 100;
1065
1066        let v = ["aaa", "bbb", "ccc", "ddd", "eee"];
1067        let data: Vec<Option<&str>> = (0..TOTAL)
1068            .map(|n| {
1069                let i = n % 5;
1070                if i == 3 { None } else { Some(v[i as usize]) }
1071            })
1072            .collect();
1073
1074        let dict_array: DictionaryArray<K> = data.clone().into_iter().collect();
1075
1076        let expected: Vec<Option<&str>> = data.iter().map(|opt| opt.map(|s| &s[1..3])).collect();
1077
1078        let res = substring(&dict_array, 1, Some(2)).unwrap();
1079        let actual = res.as_any().downcast_ref::<DictionaryArray<K>>().unwrap();
1080        let actual: Vec<Option<&str>> = actual
1081            .values()
1082            .as_any()
1083            .downcast_ref::<GenericStringArray<i32>>()
1084            .unwrap()
1085            .take_iter(actual.keys_iter())
1086            .collect();
1087
1088        for i in 0..TOTAL as usize {
1089            assert_eq!(expected[i], actual[i],);
1090        }
1091    }
1092
1093    #[test]
1094    fn check_invalid_array_type() {
1095        let array = Int32Array::from(vec![Some(1), Some(2), Some(3)]);
1096        let err = substring(&array, 0, None).unwrap_err().to_string();
1097        assert!(err.contains("substring does not support type"));
1098    }
1099
1100    // tests for the utf-8 validation checking
1101    #[test]
1102    fn check_start_index() {
1103        let array = StringArray::from(vec![Some("E=mc²"), Some("ascii")]);
1104        let err = substring(&array, -1, None).unwrap_err().to_string();
1105        assert!(err.contains("invalid utf-8 boundary"));
1106    }
1107
1108    #[test]
1109    fn check_length() {
1110        let array = StringArray::from(vec![Some("E=mc²"), Some("ascii")]);
1111        let err = substring(&array, 0, Some(5)).unwrap_err().to_string();
1112        assert!(err.contains("invalid utf-8 boundary"));
1113    }
1114
1115    #[test]
1116    fn check_invalid_bytes_outside_offsets() {
1117        // The values buffer holds invalid UTF-8 before and after the visible values
1118        let values = Buffer::from_slice_ref(b"\xFFab\x80");
1119        let array = StringArray::new(OffsetBuffer::new(vec![1, 3].into()), values, None);
1120        let result = substring(&array, 0, Some(5)).unwrap();
1121        assert_eq!(result.as_string::<i32>(), &StringArray::from(vec!["ab"]));
1122    }
1123
1124    #[test]
1125    fn non_utf8_bytes() {
1126        // non-utf8 bytes
1127        let bytes: &[u8] = &[0xE4, 0xBD, 0xA0, 0xE5, 0xA5, 0xBD, 0xE8, 0xAF, 0xAD];
1128        let array = BinaryArray::from(vec![Some(bytes)]);
1129        let arr = substring(&array, 0, Some(5)).unwrap();
1130        let actual = arr.as_any().downcast_ref::<BinaryArray>().unwrap();
1131
1132        let expected_bytes: &[u8] = &[0xE4, 0xBD, 0xA0, 0xE5, 0xA5];
1133        let expected = BinaryArray::from(vec![Some(expected_bytes)]);
1134        assert_eq!(expected, *actual);
1135    }
1136
1137    #[test]
1138    fn string_view_matches_utf8() {
1139        let values = vec![
1140            Some("hello world"),
1141            Some(""),
1142            None,
1143            Some("a"),
1144            Some("this one is definitely longer than twelve bytes"),
1145        ];
1146        let utf8 = StringArray::from(values.clone());
1147        let view = StringViewArray::from(values);
1148
1149        for (start, length) in [
1150            (0, None),
1151            (0, Some(0)),
1152            (0, Some(5)),
1153            (0, Some(1000)),
1154            (1, Some(3)),
1155            (5, None),
1156            (100, Some(2)),
1157            (100, None),
1158            (-3, None),
1159            (-3, Some(2)),
1160            (-100, Some(4)),
1161            (-100, None),
1162        ] {
1163            let expected = substring(&utf8, start, length).unwrap();
1164            let expected = expected.as_string::<i32>();
1165            let actual = substring(&view, start, length).unwrap();
1166            let actual = actual.as_string_view();
1167            assert_eq!(
1168                expected.iter().collect::<Vec<_>>(),
1169                actual.iter().collect::<Vec<_>>(),
1170                "start={start} length={length:?}"
1171            );
1172        }
1173    }
1174
1175    #[test]
1176    fn binary_view_matches_binary() {
1177        let values: Vec<Option<&[u8]>> = vec![
1178            Some(b"hello world"),
1179            Some(b""),
1180            None,
1181            Some(b"abc"),
1182            Some(b"this one is definitely longer than twelve bytes"),
1183        ];
1184        let binary = BinaryArray::from(values.clone());
1185        let view = BinaryViewArray::from(values);
1186
1187        for (start, length) in [
1188            (0, None),
1189            (0, Some(5)),
1190            (2, Some(3)),
1191            (-3, None),
1192            (100, Some(2)),
1193        ] {
1194            let expected = substring(&binary, start, length).unwrap();
1195            let expected = expected.as_binary::<i32>();
1196            let actual = substring(&view, start, length).unwrap();
1197            let actual = actual.as_binary_view();
1198            assert_eq!(
1199                expected.iter().collect::<Vec<_>>(),
1200                actual.iter().collect::<Vec<_>>(),
1201                "start={start} length={length:?}"
1202            );
1203        }
1204    }
1205
1206    #[test]
1207    fn string_view_slices_on_a_multi_byte_boundary() {
1208        // "é" and "ö" are two bytes, the CJK chars three, so 0/3/6 are the offsets that land
1209        // on a char boundary in both values.
1210        let values = vec![Some("héllo wörld"), Some("日本語"), None];
1211        let utf8 = StringArray::from(values.clone());
1212        let view = StringViewArray::from(values);
1213
1214        for (start, length) in [
1215            (0, Some(3)),
1216            (3, Some(3)),
1217            (0, Some(6)),
1218            (3, None),
1219            (-3, None),
1220            (-6, None),
1221        ] {
1222            let expected = substring(&utf8, start, length).unwrap();
1223            let expected = expected.as_string::<i32>();
1224            let actual = substring(&view, start, length).unwrap();
1225            let actual = actual.as_string_view();
1226            assert_eq!(
1227                expected.iter().collect::<Vec<_>>(),
1228                actual.iter().collect::<Vec<_>>(),
1229                "start={start} length={length:?}"
1230            );
1231        }
1232
1233        let actual = substring(&view, 0, Some(3)).unwrap();
1234        let actual = actual.as_string_view();
1235        assert_eq!(actual.value(0), "hé");
1236        assert_eq!(actual.value(1), "日");
1237    }
1238
1239    #[test]
1240    fn string_view_rejects_an_invalid_char_boundary() {
1241        let view = StringViewArray::from(vec![Some("E=mc²")]);
1242        let err = substring(&view, 0, Some(5)).unwrap_err().to_string();
1243        assert!(err.contains("invalid utf-8 boundary"), "{err}");
1244    }
1245
1246    #[test]
1247    fn dictionary_of_string_view() {
1248        let view = StringViewArray::from(vec![Some("hello world"), Some("bye")]);
1249        let dict = DictionaryArray::new(Int32Array::from(vec![0, 1, 0]), Arc::new(view));
1250
1251        let actual = substring(&dict, 0, Some(3)).unwrap();
1252        let actual = actual.as_any_dictionary();
1253
1254        let values = actual.values().as_string_view();
1255        assert_eq!(
1256            values.iter().collect::<Vec<_>>(),
1257            vec![Some("hel"), Some("bye")]
1258        );
1259    }
1260
1261    #[test]
1262    fn out_of_range_start_and_length_match_the_64_bit_arms() {
1263        // use 64 bit offset versions as expected behaviour for extreme start & length values
1264        // which should saturate and not wrap
1265        let values = vec![Some("hello"), Some("world"), None];
1266        let utf8 = StringArray::from(values.clone());
1267        let large = LargeStringArray::from(values.clone());
1268        let binary = BinaryArray::from_iter(values.iter().map(|v| v.map(|s| s.as_bytes())));
1269        let large_binary =
1270            LargeBinaryArray::from_iter(values.iter().map(|v| v.map(|s| s.as_bytes())));
1271
1272        // starts and lengths that do not survive a cast to i32
1273        let starts: [i64; 4] = [1 << 31, (1 << 31) + 5, 1 << 32, i64::MAX];
1274        let lengths: [Option<u64>; 3] = [None, Some(1 << 31), Some(u64::MAX)];
1275
1276        for start in starts {
1277            for length in lengths {
1278                let narrow = substring(&utf8, start, length).unwrap();
1279                let wide = substring(&large, start, length).unwrap();
1280                assert_eq!(
1281                    narrow.as_string::<i32>().iter().collect::<Vec<_>>(),
1282                    wide.as_string::<i64>().iter().collect::<Vec<_>>(),
1283                    "Utf8 and LargeUtf8 disagree at start {start}, length {length:?}"
1284                );
1285
1286                let narrow = substring(&binary, start, length).unwrap();
1287                let wide = substring(&large_binary, start, length).unwrap();
1288                assert_eq!(
1289                    narrow.as_binary::<i32>().iter().collect::<Vec<_>>(),
1290                    wide.as_binary::<i64>().iter().collect::<Vec<_>>(),
1291                    "Binary and LargeBinary disagree at start {start}, length {length:?}"
1292                );
1293            }
1294        }
1295
1296        // and the answer itself is the sensible one: skipping more characters
1297        // than the value holds leaves nothing behind.
1298        let out = substring(&utf8, 1 << 31, None).unwrap();
1299        assert_eq!(
1300            out.as_string::<i32>().iter().collect::<Vec<_>>(),
1301            vec![Some(""), Some(""), None]
1302        );
1303
1304        // starts that already fit are untouched
1305        let out = substring(&utf8, 3, None).unwrap();
1306        assert_eq!(
1307            out.as_string::<i32>().iter().collect::<Vec<_>>(),
1308            vec![Some("lo"), Some("ld"), None]
1309        );
1310    }
1311
1312    #[test]
1313    fn view_lengths_beyond_i64_max_match_the_64_bit_arms() {
1314        // a length that does not fit in an i64 must saturate, not wrap to a
1315        // negative length that puts the end before the start
1316        let values = vec![
1317            Some("hello"),
1318            Some("this one is longer than twelve bytes"),
1319            None,
1320        ];
1321        let large = LargeStringArray::from(values.clone());
1322        let view = StringViewArray::from(values.clone());
1323        let large_binary =
1324            LargeBinaryArray::from_iter(values.iter().map(|v| v.map(|s| s.as_bytes())));
1325        let binary_view =
1326            BinaryViewArray::from_iter(values.iter().map(|v| v.map(|s| s.as_bytes())));
1327
1328        for start in [0, 1, 3, -2, 100] {
1329            for length in [Some(i64::MAX as u64 + 1), Some(u64::MAX)] {
1330                let expected = substring(&large, start, length).unwrap();
1331                let actual = substring(&view, start, length).unwrap();
1332                assert_eq!(
1333                    expected.as_string::<i64>().iter().collect::<Vec<_>>(),
1334                    actual.as_string_view().iter().collect::<Vec<_>>(),
1335                    "LargeUtf8 and Utf8View disagree at start {start}, length {length:?}"
1336                );
1337
1338                let expected = substring(&large_binary, start, length).unwrap();
1339                let actual = substring(&binary_view, start, length).unwrap();
1340                assert_eq!(
1341                    expected.as_binary::<i64>().iter().collect::<Vec<_>>(),
1342                    actual.as_binary_view().iter().collect::<Vec<_>>(),
1343                    "LargeBinary and BinaryView disagree at start {start}, length {length:?}"
1344                );
1345            }
1346        }
1347    }
1348}