1use 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
20pub 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 length.map(u64_to_i64_saturating),
76 ),
77 DataType::Binary => byte_substring(
78 array.as_binary::<i32>(),
79 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 length.map(u64_to_i64_saturating),
94 ),
95 DataType::Utf8 => byte_substring(
96 array.as_string::<i32>(),
97 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
110pub 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 Ok(substring_by_char_impl(array, length, |val| {
149 ascii_bounds(val, start, length)
150 }))
151 } else {
152 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
160fn 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#[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#[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 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 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
248fn 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 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 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 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 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 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 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 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 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 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 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 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 (0, None, input.clone()),
549 (0, Some(0), vec![Some(&[]), None, Some(&[])]),
551 (1000, Some(0), vec![Some(&[]), None, Some(&[])]),
553 (-1000, None, input.clone()),
555 (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 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 (0, None, input.clone()),
587 (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 (-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 (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 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 let array = GenericBinaryArray::<O>::new(offsets, values, nulls).slice(1, 2);
645 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 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 (0, None, input.clone()),
676 (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 (-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 (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 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 (0, None, input.clone()),
715 (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 (-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 (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 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 let array = FixedSizeBinaryArray::new(5, Buffer::from(values), nulls).slice(1, 2);
755 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 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 (0, None, input.clone()),
777 (0, Some(0), vec![Some(""), None, Some("")]),
779 (1000, Some(0), vec![Some(""), None, Some("")]),
781 (-1000, None, input.clone()),
783 (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 let base_case = gen_test_cases!(vec!["", "", ""], (0, None, vec!["", "", ""]));
808 let cases = gen_test_cases!(
809 input,
810 (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 (-1, None, vec!["o", "", "d"]),
818 (-2, None, vec!["lo", "", "rd"]),
819 (-3, None, vec!["llo", "", "ord"]),
820 (-10, None, input.clone()),
821 (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 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 let array = GenericStringArray::<O>::new(offsets, values, nulls).slice(1, 2);
869 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 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 (0, None, input.clone()),
897 (0, Some(0), vec![Some(""), None, Some("")]),
899 (1000, Some(0), vec![Some(""), None, Some("")]),
901 (-1000, None, input.clone()),
903 (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 let base_case = gen_test_cases!(vec!["", "", ""], (0, None, vec!["", "", ""]));
928 let cases = gen_test_cases!(
929 input,
930 (0, None, input.clone()),
932 (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 (-1, None, vec!["o", "", "T"]),
939 (-2, None, vec!["lo", "", ":T"]),
940 (-4, None, vec!["ello", "", "⊢x:T"]),
941 (-10, None, input.clone()),
942 (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 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 (0, None, input.clone()),
977 (1, None, vec![Some("ello"), None, Some(""), Some("ust")]),
979 (4, None, vec![Some("o"), None, Some(""), Some("")]),
980 (1000, None, vec![Some(""), None, Some(""), Some("")]),
982 (-1, None, vec![Some("o"), None, Some(""), Some("t")]),
984 (-4, None, vec![Some("ello"), None, Some(""), Some("rust")]),
985 (-1000, None, input.clone()),
987 (0, Some(0), vec![Some(""), None, Some(""), Some("")]),
989 (1, Some(2), vec![Some("el"), None, Some(""), Some("us")]),
991 (-4, Some(2), vec![Some("el"), None, Some(""), Some("ru")]),
992 (0, Some(1000), input.clone()),
994 (
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 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 let array = GenericStringArray::<O>::new(offsets, values, nulls).slice(1, 2);
1035 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 #[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 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 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 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 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 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 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 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 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}