1#![doc(
151 html_logo_url = "https://arrow.apache.org/img/arrow-logo_chevrons_black-txt_white-bg.svg",
152 html_favicon_url = "https://arrow.apache.org/img/arrow-logo_chevrons_black-txt_transparent-bg.svg"
153)]
154#![cfg_attr(docsrs, feature(doc_cfg))]
155#![warn(missing_docs)]
156use std::cmp::Ordering;
157use std::hash::{Hash, Hasher};
158use std::iter::Map;
159use std::slice::Windows;
160use std::sync::Arc;
161
162use arrow_array::cast::*;
163use arrow_array::types::{
164 ArrowDictionaryKeyType, BinaryType, ByteArrayType, ByteViewType, LargeBinaryType,
165 LargeUtf8Type, Utf8Type,
166};
167use arrow_array::*;
168use arrow_buffer::{ArrowNativeType, Buffer, NullBufferBuilder, OffsetBuffer, ScalarBuffer};
169use arrow_data::transform::MutableArrayData;
170use arrow_schema::*;
171use variable::{decode_binary_view, decode_string_view};
172
173use crate::fixed::{try_decode_bool, try_decode_fixed_size_binary, try_decode_primitive};
174use crate::list::{compute_lengths_fixed_size_list, encode_fixed_size_list};
175use crate::variable::{decode_binary, decode_string};
176use arrow_array::types::{Int16Type, Int32Type, Int64Type};
177
178mod fixed;
179mod list;
180mod run;
181mod variable;
182
183const DICTIONARY_GATHER_MIN_VALUES: usize = 32 * 1024;
186const DICTIONARY_GATHER_RATIO: usize = 4;
187
188#[derive(Debug)]
571pub struct RowConverter {
572 fields: Arc<[SortField]>,
573 codecs: Vec<Codec>,
575}
576
577#[derive(Debug)]
578enum Codec {
579 Stateless,
581 Dictionary(RowConverter, OwnedRow),
584 Struct(RowConverter, OwnedRow),
587 List(RowConverter),
589 Map(RowConverter),
591 RunEndEncoded(RowConverter),
593 Union(Vec<RowConverter>, Vec<i8>, Vec<OwnedRow>),
596}
597
598fn compute_list_view_bounds<O: OffsetSizeTrait>(array: &GenericListViewArray<O>) -> (usize, usize) {
601 if array.is_empty() {
602 return (0, 0);
603 }
604
605 let offsets = array.value_offsets();
606 let sizes = array.value_sizes();
607 let values_len = array.values().len();
608
609 let mut min_offset = usize::MAX;
610 let mut max_end = 0usize;
611
612 for i in 0..array.len() {
613 let offset = offsets[i].as_usize();
614 let size = sizes[i].as_usize();
615 let end = offset + size;
616
617 if size > 0 {
618 min_offset = min_offset.min(offset);
619 max_end = max_end.max(end);
620 }
621
622 if min_offset == 0 && max_end == values_len {
626 break;
627 }
628 }
629
630 if min_offset == usize::MAX {
631 (0, 0)
633 } else {
634 (min_offset, max_end)
635 }
636}
637
638impl Codec {
639 fn new(sort_field: &SortField) -> Result<Self, ArrowError> {
640 match &sort_field.data_type {
641 DataType::Dictionary(_, values) => {
642 let sort_field =
643 SortField::new_with_options(values.as_ref().clone(), sort_field.options);
644
645 let converter = RowConverter::new(vec![sort_field])?;
646 let null_array = new_null_array(values.as_ref(), 1);
647 let nulls = converter.convert_columns(&[null_array])?;
648
649 let owned = OwnedRow {
650 data: nulls.buffer.into(),
651 config: nulls.config,
652 };
653 Ok(Self::Dictionary(converter, owned))
654 }
655 DataType::RunEndEncoded(_, values) => {
656 let options = SortOptions {
658 descending: false,
659 nulls_first: sort_field.options.nulls_first != sort_field.options.descending,
660 };
661
662 let field = SortField::new_with_options(values.data_type().clone(), options);
663 let converter = RowConverter::new(vec![field])?;
664 Ok(Self::RunEndEncoded(converter))
665 }
666 d if !d.is_nested() => Ok(Self::Stateless),
667 DataType::List(f)
668 | DataType::LargeList(f)
669 | DataType::ListView(f)
670 | DataType::LargeListView(f) => {
671 let options = SortOptions {
675 descending: false,
676 nulls_first: sort_field.options.nulls_first != sort_field.options.descending,
677 };
678
679 let field = SortField::new_with_options(f.data_type().clone(), options);
680 let converter = RowConverter::new(vec![field])?;
681 Ok(Self::List(converter))
682 }
683 DataType::Map(f, _) => {
684 let options = SortOptions {
688 descending: false,
689 nulls_first: sort_field.options.nulls_first != sort_field.options.descending,
690 };
691
692 let DataType::Struct(fields) = f.data_type() else {
693 return Err(ArrowError::InvalidArgumentError(format!(
694 "expected struct field in map, got {:?}",
695 f.data_type()
696 )));
697 };
698
699 let fields = fields
701 .iter()
702 .map(|struct_field| {
703 SortField::new_with_options(struct_field.data_type().clone(), options)
704 })
705 .collect::<Vec<_>>();
706 assert_eq!(fields.len(), 2);
707 let converter = RowConverter::new(fields)?;
708 Ok(Self::Map(converter))
709 }
710 DataType::FixedSizeList(f, _) => {
711 let field = SortField::new_with_options(f.data_type().clone(), sort_field.options);
712 let converter = RowConverter::new(vec![field])?;
713 Ok(Self::List(converter))
714 }
715 DataType::Struct(f) => {
716 let sort_fields = f
717 .iter()
718 .map(|x| SortField::new_with_options(x.data_type().clone(), sort_field.options))
719 .collect();
720
721 let converter = RowConverter::new(sort_fields)?;
722 let nulls: Vec<_> = f.iter().map(|x| new_null_array(x.data_type(), 1)).collect();
723
724 let nulls = converter.convert_columns(&nulls)?;
725 let owned = OwnedRow {
726 data: nulls.buffer.into(),
727 config: nulls.config,
728 };
729
730 Ok(Self::Struct(converter, owned))
731 }
732 DataType::Union(fields, _mode) => {
733 let options = SortOptions {
736 descending: false,
737 nulls_first: sort_field.options.nulls_first != sort_field.options.descending,
738 };
739
740 let mut converters = Vec::with_capacity(fields.len());
741 let mut type_ids = Vec::with_capacity(fields.len());
742 let mut null_rows = Vec::with_capacity(fields.len());
743
744 for (type_id, field) in fields.iter() {
745 let sort_field =
746 SortField::new_with_options(field.data_type().clone(), options);
747 let converter = RowConverter::new(vec![sort_field])?;
748
749 let null_array = new_null_array(field.data_type(), 1);
750 let nulls = converter.convert_columns(&[null_array])?;
751 let owned = OwnedRow {
752 data: nulls.buffer.into(),
753 config: nulls.config,
754 };
755
756 converters.push(converter);
757 type_ids.push(type_id);
758 null_rows.push(owned);
759 }
760
761 Ok(Self::Union(converters, type_ids, null_rows))
762 }
763 _ => Err(ArrowError::NotYetImplemented(format!(
764 "not yet implemented: {:?}",
765 sort_field.data_type
766 ))),
767 }
768 }
769
770 fn encoder(&self, array: &dyn Array) -> Result<Encoder<'_>, ArrowError> {
771 match self {
772 Codec::Stateless => Ok(Encoder::Stateless),
773 Codec::Dictionary(converter, nulls) => {
774 let dictionary = array.as_any_dictionary();
775 let values = dictionary.values();
776 if values.len() >= DICTIONARY_GATHER_MIN_VALUES
777 && values.len() >= dictionary.len().saturating_mul(DICTIONARY_GATHER_RATIO)
778 {
779 let values = downcast_dictionary_array! {
780 array => gather_dictionary_values(array),
781 _ => unreachable!(),
782 };
783 if let Ok(values) = values {
786 let rows = converter.convert_columns(&[values])?;
787 return Ok(Encoder::DictionaryRows(rows, nulls.row()));
788 }
789 }
790
791 let values = Arc::clone(values);
792 let rows = converter.convert_columns(&[values])?;
793 Ok(Encoder::Dictionary(rows, nulls.row()))
794 }
795 Codec::Struct(converter, null) => {
796 let v = as_struct_array(array);
797 let rows = converter.convert_columns(v.columns())?;
798 Ok(Encoder::Struct(rows, null.row()))
799 }
800 Codec::List(converter) => {
801 let values = match array.data_type() {
802 DataType::List(_) => {
803 let list_array = as_list_array(array);
804 let first_offset = list_array.offsets()[0] as usize;
805 let last_offset =
806 list_array.offsets()[list_array.offsets().len() - 1] as usize;
807
808 list_array
811 .values()
812 .slice(first_offset, last_offset - first_offset)
813 }
814 DataType::LargeList(_) => {
815 let list_array = as_large_list_array(array);
816
817 let first_offset = list_array.offsets()[0] as usize;
818 let last_offset =
819 list_array.offsets()[list_array.offsets().len() - 1] as usize;
820
821 list_array
824 .values()
825 .slice(first_offset, last_offset - first_offset)
826 }
827 DataType::ListView(_) => {
828 let list_view_array = array.as_list_view::<i32>();
829 let (min_offset, max_end) = compute_list_view_bounds(list_view_array);
830 list_view_array
831 .values()
832 .slice(min_offset, max_end - min_offset)
833 }
834 DataType::LargeListView(_) => {
835 let list_view_array = array.as_list_view::<i64>();
836 let (min_offset, max_end) = compute_list_view_bounds(list_view_array);
837 list_view_array
838 .values()
839 .slice(min_offset, max_end - min_offset)
840 }
841 DataType::FixedSizeList(_, _) => {
842 as_fixed_size_list_array(array).values().clone()
843 }
844 _ => unreachable!(),
845 };
846 let rows = converter.convert_columns(&[values])?;
847 Ok(Encoder::List(rows))
848 }
849 Codec::Map(converter) => {
850 let map_array = as_map_array(array);
851
852 let first_offset = map_array.offsets()[0] as usize;
853 let last_offset = map_array.offsets()[map_array.offsets().len() - 1] as usize;
854
855 let sliced_entries = map_array
858 .entries()
859 .slice(first_offset, last_offset - first_offset);
860
861 let rows = converter.convert_columns(sliced_entries.columns())?;
863 Ok(Encoder::Map(rows))
864 }
865 Codec::RunEndEncoded(converter) => {
866 let values = match array.data_type() {
867 DataType::RunEndEncoded(r, _) => match r.data_type() {
868 DataType::Int16 => array.as_run::<Int16Type>().values_slice(),
869 DataType::Int32 => array.as_run::<Int32Type>().values_slice(),
870 DataType::Int64 => array.as_run::<Int64Type>().values_slice(),
871 _ => unreachable!("Unsupported run end index type: {r:?}"),
872 },
873 _ => unreachable!(),
874 };
875 let rows = converter.convert_columns(std::slice::from_ref(&values))?;
876 Ok(Encoder::RunEndEncoded(rows))
877 }
878 Codec::Union(converters, field_to_type_ids, _) => {
879 let union_array = array
880 .as_any()
881 .downcast_ref::<UnionArray>()
882 .expect("expected Union array");
883
884 let type_ids = union_array.type_ids().clone();
885 let offsets = union_array.offsets().cloned();
886
887 let mut child_rows = Vec::with_capacity(converters.len());
888 for (field_idx, converter) in converters.iter().enumerate() {
889 let type_id = field_to_type_ids[field_idx];
890 let child_array = union_array.child(type_id);
891 let rows = converter.convert_columns(std::slice::from_ref(child_array))?;
892 child_rows.push(rows);
893 }
894
895 Ok(Encoder::Union {
896 child_rows,
897 field_to_type_ids: field_to_type_ids.clone(),
898 type_ids,
899 offsets,
900 })
901 }
902 }
903 }
904
905 fn size(&self) -> usize {
906 match self {
907 Codec::Stateless => 0,
908 Codec::Dictionary(converter, nulls) => converter.size() + nulls.data.len(),
909 Codec::Struct(converter, nulls) => converter.size() + nulls.data.len(),
910 Codec::List(converter) => converter.size(),
911 Codec::Map(converter) => converter.size(),
912 Codec::RunEndEncoded(converter) => converter.size(),
913 Codec::Union(converters, _, null_rows) => {
914 converters.iter().map(|c| c.size()).sum::<usize>()
915 + null_rows.iter().map(|n| n.data.len()).sum::<usize>()
916 }
917 }
918 }
919}
920
921#[derive(Debug)]
922enum Encoder<'a> {
923 Stateless,
925 Dictionary(Rows, Row<'a>),
927 DictionaryRows(Rows, Row<'a>),
929 Struct(Rows, Row<'a>),
935 List(Rows),
937 Map(Rows),
939 RunEndEncoded(Rows),
941 Union {
943 child_rows: Vec<Rows>,
944 field_to_type_ids: Vec<i8>,
945 type_ids: ScalarBuffer<i8>,
946 offsets: Option<ScalarBuffer<i32>>,
947 },
948}
949
950#[derive(Debug, Clone, PartialEq, Eq)]
952pub struct SortField {
953 options: SortOptions,
955 data_type: DataType,
957}
958
959impl SortField {
960 pub fn new(data_type: DataType) -> Self {
962 Self::new_with_options(data_type, Default::default())
963 }
964
965 pub fn new_with_options(data_type: DataType, options: SortOptions) -> Self {
967 Self { options, data_type }
968 }
969
970 pub fn size(&self) -> usize {
974 self.data_type.size() + std::mem::size_of::<Self>() - std::mem::size_of::<DataType>()
975 }
976}
977
978impl RowConverter {
979 pub fn new(fields: Vec<SortField>) -> Result<Self, ArrowError> {
981 if !Self::supports_fields(&fields) {
982 return Err(ArrowError::NotYetImplemented(format!(
983 "Row format support not yet implemented for: {fields:?}"
984 )));
985 }
986
987 let codecs = fields.iter().map(Codec::new).collect::<Result<_, _>>()?;
988 Ok(Self {
989 fields: fields.into(),
990 codecs,
991 })
992 }
993
994 pub fn supports_fields(fields: &[SortField]) -> bool {
996 fields.iter().all(|x| Self::supports_datatype(&x.data_type))
997 }
998
999 fn supports_datatype(d: &DataType) -> bool {
1000 match d {
1001 _ if !d.is_nested() => true,
1002 DataType::List(f)
1003 | DataType::LargeList(f)
1004 | DataType::ListView(f)
1005 | DataType::LargeListView(f)
1006 | DataType::FixedSizeList(f, _)
1007 | DataType::Map(f, _) => Self::supports_datatype(f.data_type()),
1008 DataType::Struct(f) => f.iter().all(|x| Self::supports_datatype(x.data_type())),
1009 DataType::RunEndEncoded(_, values) => Self::supports_datatype(values.data_type()),
1010 DataType::Union(fs, _mode) => fs
1011 .iter()
1012 .all(|(_, f)| Self::supports_datatype(f.data_type())),
1013 _ => false,
1014 }
1015 }
1016
1017 pub fn convert_columns(&self, columns: &[ArrayRef]) -> Result<Rows, ArrowError> {
1027 let num_rows = columns.first().map(|x| x.len()).unwrap_or(0);
1028 let mut rows = self.empty_rows(num_rows, 0);
1029 self.append(&mut rows, columns)?;
1030 Ok(rows)
1031 }
1032
1033 pub fn append(&self, rows: &mut Rows, columns: &[ArrayRef]) -> Result<(), ArrowError> {
1064 assert!(
1065 Arc::ptr_eq(&rows.config.fields, &self.fields),
1066 "rows were not produced by this RowConverter"
1067 );
1068
1069 if columns.len() != self.fields.len() {
1070 return Err(ArrowError::InvalidArgumentError(format!(
1071 "Incorrect number of arrays provided to RowConverter, expected {} got {}",
1072 self.fields.len(),
1073 columns.len()
1074 )));
1075 }
1076 for column in columns.iter().skip(1) {
1077 if column.len() != columns[0].len() {
1078 return Err(ArrowError::InvalidArgumentError(format!(
1079 "RowConverter columns must all have the same length, expected {} got {}",
1080 columns[0].len(),
1081 column.len()
1082 )));
1083 }
1084 }
1085
1086 let encoders = columns
1087 .iter()
1088 .zip(&self.codecs)
1089 .zip(self.fields.iter())
1090 .map(|((column, codec), field)| {
1091 if !column.data_type().equals_datatype(&field.data_type) {
1092 return Err(ArrowError::InvalidArgumentError(format!(
1093 "RowConverter column schema mismatch, expected {} got {}",
1094 field.data_type,
1095 column.data_type()
1096 )));
1097 }
1098 codec.encoder(column.as_ref())
1099 })
1100 .collect::<Result<Vec<_>, _>>()?;
1101
1102 let write_offset = rows.num_rows();
1103 let lengths = row_lengths(columns, &encoders);
1104 let total = lengths.extend_offsets(rows.offsets[write_offset], &mut rows.offsets);
1105 rows.buffer.resize(total, 0);
1106
1107 for ((column, field), encoder) in columns.iter().zip(self.fields.iter()).zip(encoders) {
1108 encode_column(
1110 &mut rows.buffer,
1111 &mut rows.offsets[write_offset..],
1112 column.as_ref(),
1113 field.options,
1114 &encoder,
1115 )
1116 }
1117
1118 if cfg!(debug_assertions) {
1119 assert_eq!(*rows.offsets.last().unwrap(), rows.buffer.len());
1120 rows.offsets
1121 .windows(2)
1122 .for_each(|w| assert!(w[0] <= w[1], "offsets should be monotonic"));
1123 }
1124
1125 Ok(())
1126 }
1127
1128 pub fn convert_rows<'a, I>(&self, rows: I) -> Result<Vec<ArrayRef>, ArrowError>
1136 where
1137 I: IntoIterator<Item = Row<'a>>,
1138 {
1139 let mut validate_utf8 = false;
1140 let mut rows: Vec<_> = rows
1141 .into_iter()
1142 .map(|row| {
1143 assert!(
1144 Arc::ptr_eq(&row.config.fields, &self.fields),
1145 "rows were not produced by this RowConverter"
1146 );
1147 validate_utf8 |= row.config.validate_utf8;
1148 row.data
1149 })
1150 .collect();
1151
1152 let result = unsafe { self.convert_raw(&mut rows, validate_utf8) }?;
1156
1157 if cfg!(debug_assertions) {
1158 for (i, row) in rows.iter().enumerate() {
1159 if !row.is_empty() {
1160 return Err(ArrowError::InvalidArgumentError(format!(
1161 "Codecs {codecs:?} did not consume all bytes for row {i}, remaining bytes: {row:?}",
1162 codecs = self.codecs
1163 )));
1164 }
1165 }
1166 }
1167
1168 Ok(result)
1169 }
1170
1171 pub fn empty_rows(&self, row_capacity: usize, data_capacity: usize) -> Rows {
1200 let mut offsets = Vec::with_capacity(row_capacity.saturating_add(1));
1201 offsets.push(0);
1202
1203 Rows {
1204 offsets,
1205 buffer: Vec::with_capacity(data_capacity),
1206 config: RowConfig {
1207 fields: self.fields.clone(),
1208 validate_utf8: false,
1209 },
1210 }
1211 }
1212
1213 pub fn from_binary(&self, array: BinaryArray) -> Rows {
1240 assert_eq!(
1241 array.null_count(),
1242 0,
1243 "can't construct Rows instance from array with nulls"
1244 );
1245 let (offsets, values, _) = array.into_parts();
1246 let offsets = offsets.iter().map(|&i| i.as_usize()).collect();
1247 let buffer = values.into_vec().unwrap_or_else(|values| values.to_vec());
1249 Rows {
1250 buffer,
1251 offsets,
1252 config: RowConfig {
1253 fields: Arc::clone(&self.fields),
1254 validate_utf8: true,
1255 },
1256 }
1257 }
1258
1259 unsafe fn convert_raw(
1265 &self,
1266 rows: &mut [&[u8]],
1267 validate_utf8: bool,
1268 ) -> Result<Vec<ArrayRef>, ArrowError> {
1269 self.fields
1270 .iter()
1271 .zip(&self.codecs)
1272 .map(|(field, codec)| unsafe { decode_column(field, rows, codec, validate_utf8) })
1273 .collect()
1274 }
1275
1276 pub fn parser(&self) -> RowParser {
1278 RowParser::new(Arc::clone(&self.fields))
1279 }
1280
1281 pub unsafe fn parser_skip_utf8_validation(&self) -> RowParser {
1286 unsafe { RowParser::with_skip_utf8_validate(Arc::clone(&self.fields)) }
1287 }
1288
1289 pub fn size(&self) -> usize {
1293 std::mem::size_of::<Self>()
1294 + self.fields.iter().map(|x| x.size()).sum::<usize>()
1295 + self.codecs.capacity() * std::mem::size_of::<Codec>()
1296 + self.codecs.iter().map(Codec::size).sum::<usize>()
1297 }
1298}
1299
1300#[derive(Debug)]
1302pub struct RowParser {
1303 config: RowConfig,
1304}
1305
1306impl RowParser {
1307 fn new(fields: Arc<[SortField]>) -> Self {
1308 Self {
1309 config: RowConfig {
1310 fields,
1311 validate_utf8: true,
1312 },
1313 }
1314 }
1315 unsafe fn with_skip_utf8_validate(fields: Arc<[SortField]>) -> Self {
1320 Self {
1321 config: RowConfig {
1322 fields,
1323 validate_utf8: false,
1324 },
1325 }
1326 }
1327
1328 pub fn parse<'a>(&'a self, bytes: &'a [u8]) -> Row<'a> {
1333 Row {
1334 data: bytes,
1335 config: &self.config,
1336 }
1337 }
1338}
1339
1340#[derive(Debug, Clone)]
1342struct RowConfig {
1343 fields: Arc<[SortField]>,
1345 validate_utf8: bool,
1347}
1348
1349#[derive(Debug, Clone)]
1353pub struct Rows {
1354 buffer: Vec<u8>,
1356 offsets: Vec<usize>,
1358 config: RowConfig,
1360}
1361
1362pub type RowLengthIter<'a> = Map<Windows<'a, usize>, fn(&'a [usize]) -> usize>;
1364
1365impl Rows {
1366 pub fn push(&mut self, row: Row<'_>) {
1372 assert!(
1373 Arc::ptr_eq(&row.config.fields, &self.config.fields),
1374 "row was not produced by this RowConverter"
1375 );
1376 self.config.validate_utf8 |= row.config.validate_utf8;
1377 self.buffer.extend_from_slice(row.data);
1378 self.offsets.push(self.buffer.len())
1379 }
1380
1381 pub fn reserve(&mut self, row_capacity: usize, data_capacity: usize) {
1383 self.buffer.reserve(data_capacity);
1384 self.offsets.reserve(row_capacity);
1385 }
1386
1387 pub fn row(&self, row: usize) -> Row<'_> {
1393 self.checked_row_end(row);
1394 unsafe { self.row_unchecked(row) }
1395 }
1396
1397 fn checked_row_end(&self, row: usize) -> usize {
1398 row.checked_add(1)
1399 .filter(|end| *end < self.offsets.len())
1400 .expect("row index out of bounds")
1401 }
1402
1403 pub unsafe fn row_unchecked(&self, index: usize) -> Row<'_> {
1408 let end = unsafe { self.offsets.get_unchecked(index + 1) };
1409 let start = unsafe { self.offsets.get_unchecked(index) };
1410 let data = unsafe { self.buffer.get_unchecked(*start..*end) };
1411 Row {
1412 data,
1413 config: &self.config,
1414 }
1415 }
1416
1417 pub fn row_len(&self, row: usize) -> usize {
1420 let end = self.checked_row_end(row);
1421
1422 self.offsets[end] - self.offsets[row]
1423 }
1424
1425 pub fn lengths(&self) -> RowLengthIter<'_> {
1427 self.offsets.windows(2).map(|w| w[1] - w[0])
1428 }
1429
1430 pub fn clear(&mut self) {
1432 self.offsets.truncate(1);
1433 self.buffer.clear();
1434 }
1435
1436 pub fn num_rows(&self) -> usize {
1438 self.offsets.len() - 1
1439 }
1440
1441 pub fn iter(&self) -> RowsIter<'_> {
1443 self.into_iter()
1444 }
1445
1446 pub fn size(&self) -> usize {
1450 std::mem::size_of::<Self>()
1452 + self.buffer.capacity()
1453 + self.offsets.capacity() * std::mem::size_of::<usize>()
1454 }
1455
1456 pub fn try_into_binary(self) -> Result<BinaryArray, ArrowError> {
1486 if self.buffer.len() > i32::MAX as usize {
1487 return Err(ArrowError::InvalidArgumentError(format!(
1488 "{}-byte rows buffer too long to convert into a i32-indexed BinaryArray",
1489 self.buffer.len()
1490 )));
1491 }
1492 let offsets_scalar = ScalarBuffer::from_iter(self.offsets.into_iter().map(i32::usize_as));
1494 let array = unsafe {
1496 BinaryArray::new_unchecked(
1497 OffsetBuffer::new_unchecked(offsets_scalar),
1498 Buffer::from_vec(self.buffer),
1499 None,
1500 )
1501 };
1502 Ok(array)
1503 }
1504}
1505
1506impl<'a> IntoIterator for &'a Rows {
1507 type Item = Row<'a>;
1508 type IntoIter = RowsIter<'a>;
1509
1510 fn into_iter(self) -> Self::IntoIter {
1511 RowsIter {
1512 rows: self,
1513 start: 0,
1514 end: self.num_rows(),
1515 }
1516 }
1517}
1518
1519#[derive(Debug, Clone)]
1521pub struct RowsIter<'a> {
1522 rows: &'a Rows,
1523 start: usize,
1524 end: usize,
1525}
1526
1527impl<'a> Iterator for RowsIter<'a> {
1528 type Item = Row<'a>;
1529
1530 fn next(&mut self) -> Option<Self::Item> {
1531 if self.end == self.start {
1532 return None;
1533 }
1534
1535 let row = unsafe { self.rows.row_unchecked(self.start) };
1537 self.start += 1;
1538 Some(row)
1539 }
1540
1541 fn size_hint(&self) -> (usize, Option<usize>) {
1542 let len = self.len();
1543 (len, Some(len))
1544 }
1545
1546 fn count(self) -> usize
1547 where
1548 Self: Sized,
1549 {
1550 self.len()
1551 }
1552
1553 #[inline]
1554 fn nth(&mut self, n: usize) -> Option<Self::Item> {
1555 match self.start.checked_add(n) {
1560 Some(new_offset) if new_offset < self.end => {
1562 self.start = new_offset;
1563 }
1564
1565 _ => {
1567 self.start = self.end;
1568 return None;
1569 }
1570 }
1571
1572 self.next()
1573 }
1574
1575 fn last(mut self) -> Option<Self::Item> {
1576 if self.start == self.end {
1578 return None;
1579 }
1580
1581 self.start = self.end - 1;
1583
1584 self.next()
1586 }
1587}
1588
1589impl ExactSizeIterator for RowsIter<'_> {
1590 fn len(&self) -> usize {
1591 self.end - self.start
1592 }
1593}
1594
1595impl DoubleEndedIterator for RowsIter<'_> {
1596 fn next_back(&mut self) -> Option<Self::Item> {
1597 if self.end == self.start {
1598 return None;
1599 }
1600
1601 self.end -= 1;
1602
1603 let row = unsafe { self.rows.row_unchecked(self.end) };
1606 Some(row)
1607 }
1608
1609 fn nth_back(&mut self, n: usize) -> Option<Self::Item> {
1610 match self.end.checked_sub(n) {
1615 Some(new_offset) if self.start < new_offset => {
1617 self.end = new_offset;
1618 }
1619
1620 _ => {
1622 self.start = self.end;
1623 return None;
1624 }
1625 }
1626
1627 self.next_back()
1628 }
1629}
1630
1631#[derive(Debug, Copy, Clone)]
1640pub struct Row<'a> {
1641 data: &'a [u8],
1642 config: &'a RowConfig,
1643}
1644
1645impl<'a> Row<'a> {
1646 pub fn owned(&self) -> OwnedRow {
1648 OwnedRow {
1649 data: self.data.into(),
1650 config: self.config.clone(),
1651 }
1652 }
1653
1654 pub fn data(&self) -> &'a [u8] {
1656 self.data
1657 }
1658}
1659
1660impl PartialEq for Row<'_> {
1663 #[inline]
1664 fn eq(&self, other: &Self) -> bool {
1665 self.data.eq(other.data)
1666 }
1667}
1668
1669impl Eq for Row<'_> {}
1670
1671impl PartialOrd for Row<'_> {
1672 #[inline]
1673 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1674 Some(self.cmp(other))
1675 }
1676}
1677
1678impl Ord for Row<'_> {
1679 #[inline]
1680 fn cmp(&self, other: &Self) -> Ordering {
1681 self.data.cmp(other.data)
1682 }
1683}
1684
1685impl Hash for Row<'_> {
1686 #[inline]
1687 fn hash<H: Hasher>(&self, state: &mut H) {
1688 self.data.hash(state)
1689 }
1690}
1691
1692impl AsRef<[u8]> for Row<'_> {
1693 #[inline]
1694 fn as_ref(&self) -> &[u8] {
1695 self.data
1696 }
1697}
1698
1699#[derive(Debug, Clone)]
1703pub struct OwnedRow {
1704 data: Box<[u8]>,
1705 config: RowConfig,
1706}
1707
1708impl OwnedRow {
1709 pub fn row(&self) -> Row<'_> {
1713 Row {
1714 data: &self.data,
1715 config: &self.config,
1716 }
1717 }
1718}
1719
1720impl PartialEq for OwnedRow {
1723 #[inline]
1724 fn eq(&self, other: &Self) -> bool {
1725 self.row().eq(&other.row())
1726 }
1727}
1728
1729impl Eq for OwnedRow {}
1730
1731impl PartialOrd for OwnedRow {
1732 #[inline]
1733 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
1734 Some(self.cmp(other))
1735 }
1736}
1737
1738impl Ord for OwnedRow {
1739 #[inline]
1740 fn cmp(&self, other: &Self) -> Ordering {
1741 self.row().cmp(&other.row())
1742 }
1743}
1744
1745impl Hash for OwnedRow {
1746 #[inline]
1747 fn hash<H: Hasher>(&self, state: &mut H) {
1748 self.row().hash(state)
1749 }
1750}
1751
1752impl AsRef<[u8]> for OwnedRow {
1753 #[inline]
1754 fn as_ref(&self) -> &[u8] {
1755 &self.data
1756 }
1757}
1758
1759#[inline]
1761fn null_sentinel(options: SortOptions) -> u8 {
1762 match options.nulls_first {
1763 true => 0,
1764 false => 0xFF,
1765 }
1766}
1767
1768enum LengthTracker {
1770 Fixed { length: usize, num_rows: usize },
1772 Variable {
1774 fixed_length: usize,
1775 lengths: Vec<usize>,
1776 },
1777}
1778
1779impl LengthTracker {
1780 fn new(num_rows: usize) -> Self {
1781 Self::Fixed {
1782 length: 0,
1783 num_rows,
1784 }
1785 }
1786
1787 fn push_fixed(&mut self, new_length: usize) {
1789 match self {
1790 LengthTracker::Fixed { length, .. } => *length += new_length,
1791 LengthTracker::Variable { fixed_length, .. } => *fixed_length += new_length,
1792 }
1793 }
1794
1795 fn push_variable(&mut self, new_lengths: impl ExactSizeIterator<Item = usize>) {
1797 match self {
1798 LengthTracker::Fixed { length, .. } => {
1799 *self = LengthTracker::Variable {
1800 fixed_length: *length,
1801 lengths: new_lengths.collect(),
1802 }
1803 }
1804 LengthTracker::Variable { lengths, .. } => {
1805 assert_eq!(lengths.len(), new_lengths.len());
1806 lengths
1807 .iter_mut()
1808 .zip(new_lengths)
1809 .for_each(|(length, new_length)| *length += new_length);
1810 }
1811 }
1812 }
1813
1814 fn materialized(&mut self) -> &mut [usize] {
1816 if let LengthTracker::Fixed { length, num_rows } = *self {
1817 *self = LengthTracker::Variable {
1818 fixed_length: length,
1819 lengths: vec![0; num_rows],
1820 };
1821 }
1822
1823 match self {
1824 LengthTracker::Variable { lengths, .. } => lengths,
1825 LengthTracker::Fixed { .. } => unreachable!(),
1826 }
1827 }
1828
1829 fn extend_offsets(&self, initial_offset: usize, offsets: &mut Vec<usize>) -> usize {
1847 match self {
1848 LengthTracker::Fixed { length, num_rows } => {
1849 offsets.extend((0..*num_rows).map(|i| initial_offset + i * length));
1850
1851 initial_offset + num_rows * length
1852 }
1853 LengthTracker::Variable {
1854 fixed_length,
1855 lengths,
1856 } => {
1857 let mut acc = initial_offset;
1858
1859 offsets.extend(lengths.iter().map(|length| {
1860 let current = acc;
1861 acc += length + fixed_length;
1862 current
1863 }));
1864
1865 acc
1866 }
1867 }
1868 }
1869}
1870
1871fn row_lengths(cols: &[ArrayRef], encoders: &[Encoder]) -> LengthTracker {
1873 use fixed::FixedLengthEncoding;
1874
1875 let num_rows = cols.first().map(|x| x.len()).unwrap_or(0);
1876 let mut tracker = LengthTracker::new(num_rows);
1877
1878 for (array, encoder) in cols.iter().zip(encoders) {
1879 match encoder {
1880 Encoder::Stateless => {
1881 downcast_primitive_array! {
1882 array => tracker.push_fixed(fixed::encoded_len(array)),
1883 DataType::Null => tracker.push_fixed(2)
1884 DataType::Boolean => tracker.push_fixed(bool::ENCODED_LEN),
1885 DataType::Binary => push_generic_byte_array_lengths(&mut tracker, as_generic_binary_array::<i32>(array)),
1886 DataType::LargeBinary => push_generic_byte_array_lengths(&mut tracker, as_generic_binary_array::<i64>(array)),
1887 DataType::BinaryView => push_byte_view_array_lengths(&mut tracker, array.as_binary_view()),
1888 DataType::Utf8 => push_generic_byte_array_lengths(&mut tracker, array.as_string::<i32>()),
1889 DataType::LargeUtf8 => push_generic_byte_array_lengths(&mut tracker, array.as_string::<i64>()),
1890 DataType::Utf8View => push_byte_view_array_lengths(&mut tracker, array.as_string_view()),
1891 DataType::FixedSizeBinary(len) => {
1892 let len = len.to_usize().unwrap();
1893 tracker.push_fixed(1 + len)
1894 }
1895 _ => unimplemented!("unsupported data type: {}", array.data_type()),
1896 }
1897 }
1898 Encoder::Dictionary(values, null) => {
1899 downcast_dictionary_array! {
1900 array => {
1901 tracker.push_variable(
1902 array.keys().iter().map(|v| match v {
1903 Some(k) => values.row_len(k.as_usize()),
1904 None => null.data.len(),
1905 })
1906 )
1907 }
1908 _ => unreachable!(),
1909 }
1910 }
1911 Encoder::DictionaryRows(values, null) => {
1912 downcast_dictionary_array! {
1913 array => tracker.push_variable(
1914 array.keys().iter().enumerate().map(|(row, key)| match key {
1915 Some(_) => values.row_len(row),
1916 None => null.data.len(),
1917 })
1918 ),
1919 _ => unreachable!(),
1920 }
1921 }
1922 Encoder::Struct(rows, null) => {
1923 let array = as_struct_array(array);
1924 if rows.num_rows() > 0 {
1925 tracker.push_variable((0..array.len()).map(|idx| match array.is_valid(idx) {
1927 true => 1 + rows.row_len(idx),
1928 false => 1 + null.data.len(),
1929 }));
1930 } else {
1931 tracker.push_variable((0..array.len()).map(|idx| match array.is_valid(idx) {
1933 true => 1,
1934 false => 1 + null.data.len(),
1935 }));
1936 }
1937 }
1938 Encoder::List(rows) => match array.data_type() {
1939 DataType::List(_) => {
1940 list::compute_lengths(tracker.materialized(), rows, as_list_array(array))
1941 }
1942 DataType::LargeList(_) => {
1943 list::compute_lengths(tracker.materialized(), rows, as_large_list_array(array))
1944 }
1945 DataType::ListView(_) => {
1946 let list_view = array.as_list_view::<i32>();
1947 let (min_offset, _) = compute_list_view_bounds(list_view);
1948 list::compute_lengths_list_view(
1949 tracker.materialized(),
1950 rows,
1951 list_view,
1952 min_offset,
1953 )
1954 }
1955 DataType::LargeListView(_) => {
1956 let list_view = array.as_list_view::<i64>();
1957 let (min_offset, _) = compute_list_view_bounds(list_view);
1958 list::compute_lengths_list_view(
1959 tracker.materialized(),
1960 rows,
1961 list_view,
1962 min_offset,
1963 )
1964 }
1965 DataType::FixedSizeList(_, _) => compute_lengths_fixed_size_list(
1966 &mut tracker,
1967 rows,
1968 as_fixed_size_list_array(array),
1969 ),
1970 _ => unreachable!(),
1971 },
1972 Encoder::Map(rows) => {
1973 list::compute_lengths(tracker.materialized(), rows, as_map_array(array))
1974 }
1975 Encoder::RunEndEncoded(rows) => match array.data_type() {
1976 DataType::RunEndEncoded(r, _) => match r.data_type() {
1977 DataType::Int16 => run::compute_lengths(
1978 tracker.materialized(),
1979 rows,
1980 array.as_run::<Int16Type>(),
1981 ),
1982 DataType::Int32 => run::compute_lengths(
1983 tracker.materialized(),
1984 rows,
1985 array.as_run::<Int32Type>(),
1986 ),
1987 DataType::Int64 => run::compute_lengths(
1988 tracker.materialized(),
1989 rows,
1990 array.as_run::<Int64Type>(),
1991 ),
1992 _ => unreachable!("Unsupported run end index type: {r:?}"),
1993 },
1994 _ => unreachable!(),
1995 },
1996 Encoder::Union {
1997 child_rows,
1998 field_to_type_ids,
1999 type_ids,
2000 offsets,
2001 } => {
2002 let union_array = array
2003 .as_any()
2004 .downcast_ref::<UnionArray>()
2005 .expect("expected UnionArray");
2006
2007 let mut type_id_to_field_idx = [0usize; 128];
2008 for (field_idx, &type_id) in field_to_type_ids.iter().enumerate() {
2009 type_id_to_field_idx[type_id as usize] = field_idx;
2010 }
2011
2012 let lengths = (0..union_array.len()).map(|i| {
2013 let type_id = type_ids[i];
2014 let field_idx = type_id_to_field_idx[type_id as usize];
2015 let child_row_i = offsets.as_ref().map(|o| o[i] as usize).unwrap_or(i);
2016 let child_row_len = child_rows[field_idx].row_len(child_row_i);
2017
2018 1 + child_row_len
2020 });
2021
2022 tracker.push_variable(lengths);
2023 }
2024 }
2025 }
2026
2027 tracker
2028}
2029
2030fn push_generic_byte_array_lengths<T: ByteArrayType>(
2032 tracker: &mut LengthTracker,
2033 array: &GenericByteArray<T>,
2034) {
2035 if let Some(nulls) = array.nulls().filter(|n| n.null_count() > 0) {
2036 tracker.push_variable(
2037 array
2038 .offsets()
2039 .lengths()
2040 .zip(nulls.iter())
2041 .map(|(length, is_valid)| if is_valid { Some(length) } else { None })
2042 .map(variable::padded_length),
2043 )
2044 } else {
2045 tracker.push_variable(
2046 array
2047 .offsets()
2048 .lengths()
2049 .map(variable::non_null_padded_length),
2050 )
2051 }
2052}
2053
2054fn push_byte_view_array_lengths<T: ByteViewType>(
2056 tracker: &mut LengthTracker,
2057 array: &GenericByteViewArray<T>,
2058) {
2059 if let Some(nulls) = array.nulls().filter(|n| n.null_count() > 0) {
2060 tracker.push_variable(
2061 array
2062 .lengths()
2063 .zip(nulls.iter())
2064 .map(|(length, is_valid)| {
2065 if is_valid {
2066 Some(length as usize)
2067 } else {
2068 None
2069 }
2070 })
2071 .map(variable::padded_length),
2072 )
2073 } else {
2074 tracker.push_variable(
2075 array
2076 .lengths()
2077 .map(|len| variable::padded_length(Some(len as usize))),
2078 )
2079 }
2080}
2081
2082fn encode_column(
2084 data: &mut [u8],
2085 offsets: &mut [usize],
2086 column: &dyn Array,
2087 opts: SortOptions,
2088 encoder: &Encoder<'_>,
2089) {
2090 match encoder {
2091 Encoder::Stateless => {
2092 downcast_primitive_array! {
2093 column => {
2094 if let Some(nulls) = column.nulls().filter(|n| n.null_count() > 0){
2095 fixed::encode(data, offsets, column.values(), nulls, opts)
2096 } else {
2097 fixed::encode_not_null(data, offsets, column.values(), opts)
2098 }
2099 }
2100 DataType::Null => {
2101 for offset in offsets.iter_mut().skip(1) {
2102 variable::encode_null_value(&mut data[*offset..], opts);
2103 *offset += 2;
2104 }
2105 }
2106 DataType::Boolean => {
2107 if let Some(nulls) = column.nulls().filter(|n| n.null_count() > 0){
2108 fixed::encode_boolean(data, offsets, column.as_boolean().values(), nulls, opts)
2109 } else {
2110 fixed::encode_boolean_not_null(data, offsets, column.as_boolean().values(), opts)
2111 }
2112 }
2113 DataType::Binary => {
2114 variable::encode_generic_byte_array(data, offsets, as_generic_binary_array::<i32>(column), opts)
2115 }
2116 DataType::BinaryView => {
2117 variable::encode(data, offsets, column.as_binary_view().iter(), opts)
2118 }
2119 DataType::LargeBinary => {
2120 variable::encode_generic_byte_array(data, offsets, as_generic_binary_array::<i64>(column), opts)
2121 }
2122 DataType::Utf8 => variable::encode_generic_byte_array(
2123 data, offsets,
2124 column.as_string::<i32>(),
2125 opts,
2126 ),
2127 DataType::LargeUtf8 => variable::encode_generic_byte_array(
2128 data, offsets,
2129 column.as_string::<i64>(),
2130 opts,
2131 ),
2132 DataType::Utf8View => variable::encode(
2133 data, offsets,
2134 column.as_string_view().iter().map(|x| x.map(|x| x.as_bytes())),
2135 opts,
2136 ),
2137 DataType::FixedSizeBinary(_) => {
2138 let array = column.as_any().downcast_ref().unwrap();
2139 fixed::encode_fixed_size_binary(data, offsets, array, opts)
2140 }
2141 _ => unimplemented!("unsupported data type: {}", column.data_type()),
2142 }
2143 }
2144 Encoder::Dictionary(values, nulls) => {
2145 downcast_dictionary_array! {
2146 column => encode_dictionary_values(data, offsets, column, values, nulls),
2147 _ => unreachable!()
2148 }
2149 }
2150 Encoder::DictionaryRows(values, nulls) => {
2151 downcast_dictionary_array! {
2152 column => encode_dictionary_rows(data, offsets, column, values, nulls),
2153 _ => unreachable!()
2154 }
2155 }
2156 Encoder::Struct(rows, null) => {
2157 fn struct_encode_helper<const NO_CHILD_FIELDS: bool>(
2158 array: &StructArray,
2159 offsets: &mut [usize],
2160 null_sentinel: u8,
2161 rows: &Rows,
2162 null: &Row<'_>,
2163 data: &mut [u8],
2164 ) {
2165 let empty_row = Row {
2166 data: &[],
2167 config: &rows.config,
2168 };
2169
2170 offsets
2171 .iter_mut()
2172 .skip(1)
2173 .enumerate()
2174 .for_each(|(idx, offset)| {
2175 let (row, sentinel) = match array.is_valid(idx) {
2176 true => (
2177 if NO_CHILD_FIELDS {
2178 empty_row
2179 } else {
2180 rows.row(idx)
2181 },
2182 0x01,
2183 ),
2184 false => (*null, null_sentinel),
2185 };
2186 let end_offset = *offset + 1 + row.as_ref().len();
2187 data[*offset] = sentinel;
2188 data[*offset + 1..end_offset].copy_from_slice(row.as_ref());
2189 *offset = end_offset;
2190 })
2191 }
2192
2193 let array = as_struct_array(column);
2194 let null_sentinel = null_sentinel(opts);
2195 if rows.num_rows() == 0 {
2196 struct_encode_helper::<true>(array, offsets, null_sentinel, rows, null, data);
2198 } else {
2199 struct_encode_helper::<false>(array, offsets, null_sentinel, rows, null, data);
2200 }
2201 }
2202 Encoder::List(rows) => match column.data_type() {
2203 DataType::List(_) => list::encode(data, offsets, rows, opts, as_list_array(column)),
2204 DataType::LargeList(_) => {
2205 list::encode(data, offsets, rows, opts, as_large_list_array(column))
2206 }
2207 DataType::ListView(_) => {
2208 let list_view = column.as_list_view::<i32>();
2209 let (min_offset, _) = compute_list_view_bounds(list_view);
2210 list::encode_list_view(data, offsets, rows, opts, list_view, min_offset)
2211 }
2212 DataType::LargeListView(_) => {
2213 let list_view = column.as_list_view::<i64>();
2214 let (min_offset, _) = compute_list_view_bounds(list_view);
2215 list::encode_list_view(data, offsets, rows, opts, list_view, min_offset)
2216 }
2217 DataType::FixedSizeList(_, _) => {
2218 encode_fixed_size_list(data, offsets, rows, opts, as_fixed_size_list_array(column))
2219 }
2220 _ => unreachable!(),
2221 },
2222 Encoder::Map(rows) => list::encode(data, offsets, rows, opts, as_map_array(column)),
2223 Encoder::RunEndEncoded(rows) => match column.data_type() {
2224 DataType::RunEndEncoded(r, _) => match r.data_type() {
2225 DataType::Int16 => {
2226 run::encode(data, offsets, rows, opts, column.as_run::<Int16Type>())
2227 }
2228 DataType::Int32 => {
2229 run::encode(data, offsets, rows, opts, column.as_run::<Int32Type>())
2230 }
2231 DataType::Int64 => {
2232 run::encode(data, offsets, rows, opts, column.as_run::<Int64Type>())
2233 }
2234 _ => unreachable!("Unsupported run end index type: {r:?}"),
2235 },
2236 _ => unreachable!(),
2237 },
2238 Encoder::Union {
2239 child_rows,
2240 field_to_type_ids,
2241 type_ids,
2242 offsets: offsets_buf,
2243 } => {
2244 let mut type_id_to_field_idx = [0usize; 128];
2245 for (field_idx, &type_id) in field_to_type_ids.iter().enumerate() {
2246 type_id_to_field_idx[type_id as usize] = field_idx;
2247 }
2248
2249 offsets
2250 .iter_mut()
2251 .skip(1)
2252 .enumerate()
2253 .for_each(|(i, offset)| {
2254 let type_id = type_ids[i];
2255 let field_idx = type_id_to_field_idx[type_id as usize];
2256
2257 let child_row_idx = offsets_buf.as_ref().map(|o| o[i] as usize).unwrap_or(i);
2258 let child_row = child_rows[field_idx].row(child_row_idx);
2259 let child_bytes = child_row.as_ref();
2260
2261 let type_id_byte = if opts.descending {
2262 !(type_id as u8)
2263 } else {
2264 type_id as u8
2265 };
2266 data[*offset] = type_id_byte;
2267
2268 let child_start = *offset + 1;
2269 let child_end = child_start + child_bytes.len();
2270 data[child_start..child_end].copy_from_slice(child_bytes);
2271
2272 *offset = child_end;
2273 });
2274 }
2275 }
2276}
2277
2278pub fn encode_dictionary_values<K: ArrowDictionaryKeyType>(
2280 data: &mut [u8],
2281 offsets: &mut [usize],
2282 column: &DictionaryArray<K>,
2283 values: &Rows,
2284 null: &Row<'_>,
2285) {
2286 for (offset, k) in offsets.iter_mut().skip(1).zip(column.keys()) {
2287 let row = match k {
2288 Some(k) => values.row(k.as_usize()).data,
2289 None => null.data,
2290 };
2291 let end_offset = *offset + row.len();
2292 data[*offset..end_offset].copy_from_slice(row);
2293 *offset = end_offset;
2294 }
2295}
2296
2297fn gather_dictionary_values<K: ArrowDictionaryKeyType>(
2298 array: &DictionaryArray<K>,
2299) -> Result<ArrayRef, ArrowError> {
2300 let values = array.values();
2301 match values.data_type() {
2302 DataType::Utf8 => gather_dictionary_byte_values::<K, Utf8Type>(
2303 array,
2304 values.as_any().downcast_ref::<StringArray>().unwrap(),
2305 ),
2306 DataType::LargeUtf8 => gather_dictionary_byte_values::<K, LargeUtf8Type>(
2307 array,
2308 values.as_any().downcast_ref::<LargeStringArray>().unwrap(),
2309 ),
2310 DataType::Binary => gather_dictionary_byte_values::<K, BinaryType>(
2311 array,
2312 values.as_any().downcast_ref::<BinaryArray>().unwrap(),
2313 ),
2314 DataType::LargeBinary => gather_dictionary_byte_values::<K, LargeBinaryType>(
2315 array,
2316 values.as_any().downcast_ref::<LargeBinaryArray>().unwrap(),
2317 ),
2318 _ => gather_dictionary_values_generic(array),
2319 }
2320}
2321
2322fn gather_dictionary_byte_values<K: ArrowDictionaryKeyType, T: ByteArrayType>(
2325 array: &DictionaryArray<K>,
2326 values: &GenericByteArray<T>,
2327) -> Result<ArrayRef, ArrowError> {
2328 let mut offsets = Vec::with_capacity(array.len() + 1);
2329 offsets.push(T::Offset::from_usize(0).unwrap());
2330 let mut bytes = Vec::new();
2331 let mut nulls = NullBufferBuilder::new(array.len());
2332
2333 for key in array.keys() {
2334 match key {
2335 Some(key) if values.is_valid(key.as_usize()) => {
2336 let index = key.as_usize();
2337 let start = values.value_offsets()[index].as_usize();
2338 let end = values.value_offsets()[index + 1].as_usize();
2339 let value = &values.value_data()[start..end];
2340 let end = bytes
2341 .len()
2342 .checked_add(value.len())
2343 .ok_or(ArrowError::OffsetOverflowError(usize::MAX))?;
2344 let offset =
2345 T::Offset::from_usize(end).ok_or(ArrowError::OffsetOverflowError(end))?;
2346 bytes.extend_from_slice(value);
2347 offsets.push(offset);
2348 nulls.append(true);
2349 }
2350 _ => {
2351 offsets.push(*offsets.last().unwrap());
2352 nulls.append(false);
2353 }
2354 }
2355 }
2356
2357 let offsets = OffsetBuffer::new(ScalarBuffer::from(offsets));
2358 Ok(Arc::new(GenericByteArray::<T>::try_new(
2359 offsets,
2360 Buffer::from_vec(bytes),
2361 nulls.finish(),
2362 )?))
2363}
2364
2365fn gather_dictionary_values_generic<K: ArrowDictionaryKeyType>(
2366 array: &DictionaryArray<K>,
2367) -> Result<ArrayRef, ArrowError> {
2368 let data = array.values().to_data();
2369 let mut mutable = MutableArrayData::new(vec![&data], false, array.len());
2370 for key in array.keys() {
2371 let index = key.map(|key| key.as_usize()).unwrap_or_default();
2372 mutable.try_extend(0, index, index + 1)?;
2373 }
2374 Ok(make_array(mutable.freeze()))
2375}
2376
2377fn encode_dictionary_rows<K: ArrowDictionaryKeyType>(
2378 data: &mut [u8],
2379 offsets: &mut [usize],
2380 column: &DictionaryArray<K>,
2381 values: &Rows,
2382 null: &Row<'_>,
2383) {
2384 for (row, (offset, key)) in offsets.iter_mut().skip(1).zip(column.keys()).enumerate() {
2385 let value = match key {
2386 Some(_) => values.row(row).data,
2387 None => null.data,
2388 };
2389 let end_offset = *offset + value.len();
2390 data[*offset..end_offset].copy_from_slice(value);
2391 *offset = end_offset;
2392 }
2393}
2394
2395macro_rules! decode_primitive_helper {
2396 ($t:ty, $rows:ident, $data_type:ident, $options:ident) => {
2397 Arc::new(try_decode_primitive::<$t>($rows, $data_type, $options)?)
2398 };
2399}
2400
2401unsafe fn decode_column(
2407 field: &SortField,
2408 rows: &mut [&[u8]],
2409 codec: &Codec,
2410 validate_utf8: bool,
2411) -> Result<ArrayRef, ArrowError> {
2412 let options = field.options;
2413
2414 let array: ArrayRef = match codec {
2415 Codec::Stateless => {
2416 let data_type = field.data_type.clone();
2417 downcast_primitive! {
2418 data_type => (decode_primitive_helper, rows, data_type, options),
2419 DataType::Null => {
2420 variable::decode_null_value(rows, options);
2421 Arc::new(NullArray::new(rows.len()))
2422 }
2423 DataType::Boolean => Arc::new(try_decode_bool(rows, options)?),
2424 DataType::Binary => Arc::new(decode_binary::<i32>(rows, options)?),
2425 DataType::LargeBinary => Arc::new(decode_binary::<i64>(rows, options)?),
2426 DataType::BinaryView => Arc::new(decode_binary_view(rows, options)?),
2427 DataType::FixedSizeBinary(size) => Arc::new(try_decode_fixed_size_binary(rows, size, options)?),
2428 DataType::Utf8 => Arc::new(unsafe{ decode_string::<i32>(rows, options, validate_utf8) }?),
2429 DataType::LargeUtf8 => Arc::new(unsafe { decode_string::<i64>(rows, options, validate_utf8) }?),
2430 DataType::Utf8View => Arc::new(unsafe { decode_string_view(rows, options, validate_utf8) }?),
2431 _ => return Err(ArrowError::NotYetImplemented(format!("unsupported data type: {data_type}" )))
2432 }
2433 }
2434 Codec::Dictionary(converter, _) => {
2435 let cols = unsafe { converter.convert_raw(rows, validate_utf8) }?;
2436 cols.into_iter().next().unwrap()
2437 }
2438 Codec::Struct(converter, _) => {
2439 let nulls = fixed::try_decode_nulls(rows)?;
2440 rows.iter_mut().for_each(|row| *row = &row[1..]);
2441 let children = unsafe { converter.convert_raw(rows, validate_utf8) }?;
2442
2443 let corrected_fields: Vec<Field> = match &field.data_type {
2446 DataType::Struct(struct_fields) => struct_fields
2447 .iter()
2448 .zip(children.iter())
2449 .map(|(orig_field, child_array)| {
2450 orig_field
2451 .as_ref()
2452 .clone()
2453 .with_data_type(child_array.data_type().clone())
2454 })
2455 .collect(),
2456 _ => unreachable!("Only Struct types should be corrected here"),
2457 };
2458
2459 Arc::new(unsafe {
2460 StructArray::new_unchecked_with_length(
2461 corrected_fields.into(),
2462 children,
2463 nulls,
2464 rows.len(),
2465 )
2466 })
2467 }
2468 Codec::List(converter) => match &field.data_type {
2469 DataType::List(_) => Arc::new(unsafe {
2470 list::decode::<GenericListArray<i32>>(converter, rows, field, validate_utf8)
2471 }?),
2472 DataType::LargeList(_) => Arc::new(unsafe {
2473 list::decode::<GenericListArray<i64>>(converter, rows, field, validate_utf8)
2474 }?),
2475 DataType::ListView(_) => Arc::new(unsafe {
2476 list::decode_list_view::<i32>(converter, rows, field, validate_utf8)
2477 }?),
2478 DataType::LargeListView(_) => Arc::new(unsafe {
2479 list::decode_list_view::<i64>(converter, rows, field, validate_utf8)
2480 }?),
2481 DataType::FixedSizeList(_, value_length) => Arc::new(unsafe {
2482 list::decode_fixed_size_list(
2483 converter,
2484 rows,
2485 field,
2486 validate_utf8,
2487 value_length.as_usize(),
2488 )
2489 }?),
2490 _ => unreachable!(),
2491 },
2492 Codec::Map(converter) => {
2493 Arc::new(unsafe { list::decode::<MapArray>(converter, rows, field, validate_utf8) }?)
2494 }
2495 Codec::RunEndEncoded(converter) => match &field.data_type {
2496 DataType::RunEndEncoded(run_ends, _) => match run_ends.data_type() {
2497 DataType::Int16 => Arc::new(unsafe {
2498 run::decode::<Int16Type>(converter, rows, field, validate_utf8)
2499 }?),
2500 DataType::Int32 => Arc::new(unsafe {
2501 run::decode::<Int32Type>(converter, rows, field, validate_utf8)
2502 }?),
2503 DataType::Int64 => Arc::new(unsafe {
2504 run::decode::<Int64Type>(converter, rows, field, validate_utf8)
2505 }?),
2506 _ => unreachable!(),
2507 },
2508 _ => unreachable!(),
2509 },
2510 Codec::Union(converters, field_to_type_ids, null_rows) => {
2511 let len = rows.len();
2512
2513 let DataType::Union(union_fields, mode) = &field.data_type else {
2514 unreachable!()
2515 };
2516
2517 let mut type_id_to_field_idx = [0usize; 128];
2518 for (field_idx, &type_id) in field_to_type_ids.iter().enumerate() {
2519 type_id_to_field_idx[type_id as usize] = field_idx;
2520 }
2521
2522 let mut type_ids = Vec::with_capacity(len);
2523 let mut rows_by_field: Vec<Vec<(usize, &[u8])>> = vec![Vec::new(); converters.len()];
2524
2525 for (idx, row) in rows.iter_mut().enumerate() {
2526 let type_id_byte = {
2527 let id = row[0];
2528 if options.descending { !id } else { id }
2529 };
2530
2531 let type_id = type_id_byte as i8;
2532 type_ids.push(type_id);
2533
2534 let field_idx = type_id_to_field_idx[type_id as usize];
2535
2536 let child_row = &row[1..];
2537 rows_by_field[field_idx].push((idx, child_row));
2538 }
2539
2540 let mut child_arrays: Vec<ArrayRef> = Vec::with_capacity(converters.len());
2541 let mut offsets = (*mode == UnionMode::Dense).then(|| Vec::with_capacity(len));
2542
2543 for (field_idx, converter) in converters.iter().enumerate() {
2544 let field_rows = &rows_by_field[field_idx];
2545
2546 match &mode {
2547 UnionMode::Dense => {
2548 if field_rows.is_empty() {
2549 let (_, field) = union_fields.iter().nth(field_idx).unwrap();
2550 child_arrays.push(arrow_array::new_empty_array(field.data_type()));
2551 continue;
2552 }
2553
2554 let mut child_data = field_rows
2555 .iter()
2556 .map(|(_, bytes)| *bytes)
2557 .collect::<Vec<_>>();
2558
2559 let child_array =
2560 unsafe { converter.convert_raw(&mut child_data, validate_utf8) }?;
2561
2562 for ((row_idx, original_bytes), remaining_bytes) in
2564 field_rows.iter().zip(child_data)
2565 {
2566 let consumed_length = 1 + original_bytes.len() - remaining_bytes.len();
2567 rows[*row_idx] = &rows[*row_idx][consumed_length..];
2568 }
2569
2570 child_arrays.push(child_array.into_iter().next().unwrap());
2571 }
2572 UnionMode::Sparse => {
2573 let mut sparse_data: Vec<&[u8]> = Vec::with_capacity(len);
2574 let mut field_row_iter = field_rows.iter().peekable();
2575 let null_row_bytes: &[u8] = &null_rows[field_idx].data;
2576
2577 for idx in 0..len {
2578 if let Some((next_idx, bytes)) = field_row_iter.peek()
2579 && *next_idx == idx
2580 {
2581 sparse_data.push(*bytes);
2582
2583 field_row_iter.next();
2584 continue;
2585 }
2586 sparse_data.push(null_row_bytes);
2587 }
2588
2589 let child_array =
2590 unsafe { converter.convert_raw(&mut sparse_data, validate_utf8) }?;
2591
2592 for (row_idx, child_row) in field_rows {
2594 let remaining_len = sparse_data[*row_idx].len();
2595 let consumed_length = 1 + child_row.len() - remaining_len;
2596 rows[*row_idx] = &rows[*row_idx][consumed_length..];
2597 }
2598
2599 child_arrays.push(child_array.into_iter().next().unwrap());
2600 }
2601 }
2602 }
2603
2604 if let Some(ref mut offsets_vec) = offsets {
2606 let mut count = vec![0i32; converters.len()];
2607 for type_id in &type_ids {
2608 let field_idx = type_id_to_field_idx[*type_id as usize];
2609 offsets_vec.push(count[field_idx]);
2610
2611 count[field_idx] += 1;
2612 }
2613 }
2614
2615 let type_ids_buffer = ScalarBuffer::from(type_ids);
2616 let offsets_buffer = offsets.map(ScalarBuffer::from);
2617
2618 let union_array = UnionArray::try_new(
2619 union_fields.clone(),
2620 type_ids_buffer,
2621 offsets_buffer,
2622 child_arrays,
2623 )?;
2624
2625 Arc::new(union_array)
2628 }
2629 };
2630 Ok(array)
2631}
2632
2633#[cfg(test)]
2634mod tests {
2635 use super::*;
2636 use arrow_array::builder::*;
2637 use arrow_array::types::*;
2638 use arrow_buffer::{Buffer, OffsetBuffer};
2639 use arrow_buffer::{NullBuffer, i256};
2640 use arrow_cast::display::{ArrayFormatter, FormatOptions};
2641 use arrow_ord::sort::{LexicographicalComparator, SortColumn};
2642 use rand::distr::uniform::SampleUniform;
2643 use rand::distr::{Distribution, StandardUniform};
2644 use rand::prelude::StdRng;
2645 use rand::{RngExt, SeedableRng};
2646 use std::fmt::Debug;
2647 use std::iter::Copied;
2648 use std::slice::Iter;
2649
2650 fn all_sort_options() -> [SortOptions; 4] {
2651 [
2652 SortOptions {
2653 descending: false,
2654 nulls_first: false,
2655 },
2656 SortOptions {
2657 descending: false,
2658 nulls_first: true,
2659 },
2660 SortOptions {
2661 descending: true,
2662 nulls_first: false,
2663 },
2664 SortOptions {
2665 descending: true,
2666 nulls_first: true,
2667 },
2668 ]
2669 }
2670
2671 #[test]
2672 fn test_fixed_width() {
2673 let cols = [
2674 Arc::new(Int16Array::from_iter([
2675 Some(1),
2676 Some(2),
2677 None,
2678 Some(-5),
2679 Some(2),
2680 Some(2),
2681 Some(0),
2682 ])) as ArrayRef,
2683 Arc::new(Float32Array::from_iter([
2684 Some(1.3),
2685 Some(2.5),
2686 None,
2687 Some(4.),
2688 Some(0.1),
2689 Some(-4.),
2690 Some(-0.),
2691 ])) as ArrayRef,
2692 ];
2693
2694 let converter = RowConverter::new(vec![
2695 SortField::new(DataType::Int16),
2696 SortField::new(DataType::Float32),
2697 ])
2698 .unwrap();
2699 let rows = converter.convert_columns(&cols).unwrap();
2700
2701 assert_eq!(rows.offsets, &[0, 8, 16, 24, 32, 40, 48, 56]);
2702 assert_eq!(
2703 rows.buffer,
2704 &[
2705 1, 128, 1, 1, 191, 166, 102, 102, 1, 128, 2, 1, 192, 32, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 127, 251, 1, 192, 128, 0, 0, 1, 128, 2, 1, 189, 204, 204, 205, 1, 128, 2, 1, 63, 127, 255, 255, 1, 128, 0, 1, 127, 255, 255, 255 ]
2720 );
2721
2722 assert!(rows.row(3) < rows.row(6));
2723 assert!(rows.row(0) < rows.row(1));
2724 assert!(rows.row(3) < rows.row(0));
2725 assert!(rows.row(4) < rows.row(1));
2726 assert!(rows.row(5) < rows.row(4));
2727
2728 let back = converter.convert_rows(&rows).unwrap();
2729 for (expected, actual) in cols.iter().zip(&back) {
2730 assert_eq!(expected, actual);
2731 }
2732 }
2733
2734 fn test_roundtrip(sort_option: SortOptions, col: ArrayRef) {
2735 let converter = RowConverter::new(vec![SortField::new_with_options(
2736 col.data_type().clone(),
2737 sort_option,
2738 )])
2739 .unwrap();
2740 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
2741 let back = converter.convert_rows(&rows).unwrap();
2742 assert_eq!(back.len(), 1);
2743 assert_eq!(&back[0], &col);
2744 back[0].to_data().validate_full().unwrap();
2745 }
2746
2747 #[test]
2748 fn test_zero_width_fixed_size_binary_roundtrip() {
2749 for sort_option in all_sort_options() {
2750 for with_null in [true, false] {
2753 let nulls = if with_null {
2754 Some(NullBuffer::from(vec![true, false, true, false, true]))
2755 } else {
2756 None
2757 };
2758 let col: ArrayRef = Arc::new(
2759 FixedSizeBinaryArray::try_new_with_len(0, Buffer::default(), nulls, 5).unwrap(),
2760 );
2761
2762 test_roundtrip(sort_option, col);
2763 }
2764 }
2765 }
2766
2767 #[test]
2768 fn test_zero_width_fixed_size_list_roundtrip() {
2769 for sort_option in all_sort_options() {
2770 for with_null in [true, false] {
2773 let nulls = if with_null {
2774 Some(NullBuffer::from(vec![true, false, true, false, true]))
2775 } else {
2776 None
2777 };
2778 let col: ArrayRef = Arc::new(
2779 FixedSizeListArray::try_new_with_length(
2780 Arc::new(Field::new("item", DataType::Boolean, false)),
2781 0,
2782 new_empty_array(&DataType::Boolean),
2783 nulls,
2784 5,
2785 )
2786 .unwrap(),
2787 );
2788
2789 test_roundtrip(sort_option, col);
2790 }
2791 }
2792 }
2793
2794 #[test]
2795 fn test_decimal32() {
2796 let converter = RowConverter::new(vec![SortField::new(DataType::Decimal32(
2797 DECIMAL32_MAX_PRECISION,
2798 7,
2799 ))])
2800 .unwrap();
2801 let col = Arc::new(
2802 Decimal32Array::from_iter([
2803 None,
2804 Some(i32::MIN),
2805 Some(-13),
2806 Some(46_i32),
2807 Some(5456_i32),
2808 Some(i32::MAX),
2809 ])
2810 .with_precision_and_scale(9, 7)
2811 .unwrap(),
2812 ) as ArrayRef;
2813
2814 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
2815 for i in 0..rows.num_rows() - 1 {
2816 assert!(rows.row(i) < rows.row(i + 1));
2817 }
2818
2819 let back = converter.convert_rows(&rows).unwrap();
2820 assert_eq!(back.len(), 1);
2821 assert_eq!(col.as_ref(), back[0].as_ref())
2822 }
2823
2824 #[test]
2825 fn test_decimal64() {
2826 let converter = RowConverter::new(vec![SortField::new(DataType::Decimal64(
2827 DECIMAL64_MAX_PRECISION,
2828 7,
2829 ))])
2830 .unwrap();
2831 let col = Arc::new(
2832 Decimal64Array::from_iter([
2833 None,
2834 Some(i64::MIN),
2835 Some(-13),
2836 Some(46_i64),
2837 Some(5456_i64),
2838 Some(i64::MAX),
2839 ])
2840 .with_precision_and_scale(18, 7)
2841 .unwrap(),
2842 ) as ArrayRef;
2843
2844 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
2845 for i in 0..rows.num_rows() - 1 {
2846 assert!(rows.row(i) < rows.row(i + 1));
2847 }
2848
2849 let back = converter.convert_rows(&rows).unwrap();
2850 assert_eq!(back.len(), 1);
2851 assert_eq!(col.as_ref(), back[0].as_ref())
2852 }
2853
2854 #[test]
2855 fn test_decimal128() {
2856 let converter = RowConverter::new(vec![SortField::new(DataType::Decimal128(
2857 DECIMAL128_MAX_PRECISION,
2858 7,
2859 ))])
2860 .unwrap();
2861 let col = Arc::new(
2862 Decimal128Array::from_iter([
2863 None,
2864 Some(i128::MIN),
2865 Some(-13),
2866 Some(46_i128),
2867 Some(5456_i128),
2868 Some(i128::MAX),
2869 ])
2870 .with_precision_and_scale(38, 7)
2871 .unwrap(),
2872 ) as ArrayRef;
2873
2874 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
2875 for i in 0..rows.num_rows() - 1 {
2876 assert!(rows.row(i) < rows.row(i + 1));
2877 }
2878
2879 let back = converter.convert_rows(&rows).unwrap();
2880 assert_eq!(back.len(), 1);
2881 assert_eq!(col.as_ref(), back[0].as_ref())
2882 }
2883
2884 #[test]
2885 fn test_decimal256() {
2886 let converter = RowConverter::new(vec![SortField::new(DataType::Decimal256(
2887 DECIMAL256_MAX_PRECISION,
2888 7,
2889 ))])
2890 .unwrap();
2891 let col = Arc::new(
2892 Decimal256Array::from_iter([
2893 None,
2894 Some(i256::MIN),
2895 Some(i256::from_parts(0, -1)),
2896 Some(i256::from_parts(u128::MAX, -1)),
2897 Some(i256::from_parts(u128::MAX, 0)),
2898 Some(i256::from_parts(0, 46_i128)),
2899 Some(i256::from_parts(5, 46_i128)),
2900 Some(i256::MAX),
2901 ])
2902 .with_precision_and_scale(DECIMAL256_MAX_PRECISION, 7)
2903 .unwrap(),
2904 ) as ArrayRef;
2905
2906 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
2907 for i in 0..rows.num_rows() - 1 {
2908 assert!(rows.row(i) < rows.row(i + 1));
2909 }
2910
2911 let back = converter.convert_rows(&rows).unwrap();
2912 assert_eq!(back.len(), 1);
2913 assert_eq!(col.as_ref(), back[0].as_ref())
2914 }
2915
2916 #[test]
2917 fn test_bool() {
2918 let converter = RowConverter::new(vec![SortField::new(DataType::Boolean)]).unwrap();
2919
2920 let col = Arc::new(BooleanArray::from_iter([None, Some(false), Some(true)])) as ArrayRef;
2921
2922 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
2923 assert!(rows.row(2) > rows.row(1));
2924 assert!(rows.row(2) > rows.row(0));
2925 assert!(rows.row(1) > rows.row(0));
2926
2927 let cols = converter.convert_rows(&rows).unwrap();
2928 assert_eq!(&cols[0], &col);
2929
2930 let converter = RowConverter::new(vec![SortField::new_with_options(
2931 DataType::Boolean,
2932 SortOptions::default().desc().with_nulls_first(false),
2933 )])
2934 .unwrap();
2935
2936 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
2937 assert!(rows.row(2) < rows.row(1));
2938 assert!(rows.row(2) < rows.row(0));
2939 assert!(rows.row(1) < rows.row(0));
2940 let cols = converter.convert_rows(&rows).unwrap();
2941 assert_eq!(&cols[0], &col);
2942 }
2943
2944 #[test]
2945 fn test_timezone() {
2946 let a =
2947 TimestampNanosecondArray::from(vec![1, 2, 3, 4, 5]).with_timezone("+01:00".to_string());
2948 let d = a.data_type().clone();
2949
2950 let converter = RowConverter::new(vec![SortField::new(a.data_type().clone())]).unwrap();
2951 let rows = converter.convert_columns(&[Arc::new(a) as _]).unwrap();
2952 let back = converter.convert_rows(&rows).unwrap();
2953 assert_eq!(back.len(), 1);
2954 assert_eq!(back[0].data_type(), &d);
2955
2956 let mut a = PrimitiveDictionaryBuilder::<Int32Type, TimestampNanosecondType>::new();
2958 a.append(34).unwrap();
2959 a.append_null();
2960 a.append(345).unwrap();
2961
2962 let dict = a.finish();
2964 let values = TimestampNanosecondArray::from(dict.values().to_data());
2965 let dict_with_tz = dict.with_values(Arc::new(values.with_timezone("+02:00")));
2966 let v = DataType::Timestamp(TimeUnit::Nanosecond, Some("+02:00".into()));
2967 let d = DataType::Dictionary(Box::new(DataType::Int32), Box::new(v.clone()));
2968
2969 assert_eq!(dict_with_tz.data_type(), &d);
2970 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
2971 let rows = converter
2972 .convert_columns(&[Arc::new(dict_with_tz) as _])
2973 .unwrap();
2974 let back = converter.convert_rows(&rows).unwrap();
2975 assert_eq!(back.len(), 1);
2976 assert_eq!(back[0].data_type(), &v);
2977 }
2978
2979 #[test]
2980 fn test_null_encoding() {
2981 let col = Arc::new(NullArray::new(10));
2982 let converter = RowConverter::new(vec![SortField::new(DataType::Null)]).unwrap();
2983 let rows = converter.convert_columns(&[col]).unwrap();
2984 assert_eq!(rows.num_rows(), 10);
2985 assert_eq!(rows.row(1).data.len(), 2);
2987 }
2988
2989 #[test]
2990 fn test_variable_width() {
2991 let col = Arc::new(StringArray::from_iter([
2992 Some("hello"),
2993 Some("he"),
2994 None,
2995 Some("foo"),
2996 Some(""),
2997 ])) as ArrayRef;
2998
2999 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
3000 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
3001
3002 assert!(rows.row(1) < rows.row(0));
3003 assert!(rows.row(2) < rows.row(4));
3004 assert!(rows.row(3) < rows.row(0));
3005 assert!(rows.row(3) < rows.row(1));
3006
3007 let cols = converter.convert_rows(&rows).unwrap();
3008 assert_eq!(&cols[0], &col);
3009
3010 let col = Arc::new(BinaryArray::from_iter([
3011 None,
3012 Some(vec![0_u8; 0]),
3013 Some(vec![0_u8; 6]),
3014 Some(vec![0_u8; variable::MINI_BLOCK_SIZE]),
3015 Some(vec![0_u8; variable::MINI_BLOCK_SIZE + 1]),
3016 Some(vec![0_u8; variable::BLOCK_SIZE]),
3017 Some(vec![0_u8; variable::BLOCK_SIZE + 1]),
3018 Some(vec![1_u8; 6]),
3019 Some(vec![1_u8; variable::MINI_BLOCK_SIZE]),
3020 Some(vec![1_u8; variable::MINI_BLOCK_SIZE + 1]),
3021 Some(vec![1_u8; variable::BLOCK_SIZE]),
3022 Some(vec![1_u8; variable::BLOCK_SIZE + 1]),
3023 Some(vec![0xFF_u8; 6]),
3024 Some(vec![0xFF_u8; variable::MINI_BLOCK_SIZE]),
3025 Some(vec![0xFF_u8; variable::MINI_BLOCK_SIZE + 1]),
3026 Some(vec![0xFF_u8; variable::BLOCK_SIZE]),
3027 Some(vec![0xFF_u8; variable::BLOCK_SIZE + 1]),
3028 ])) as ArrayRef;
3029
3030 let converter = RowConverter::new(vec![SortField::new(DataType::Binary)]).unwrap();
3031 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
3032
3033 for i in 0..rows.num_rows() {
3034 for j in i + 1..rows.num_rows() {
3035 assert!(
3036 rows.row(i) < rows.row(j),
3037 "{} < {} - {:?} < {:?}",
3038 i,
3039 j,
3040 rows.row(i),
3041 rows.row(j)
3042 );
3043 }
3044 }
3045
3046 let cols = converter.convert_rows(&rows).unwrap();
3047 assert_eq!(&cols[0], &col);
3048
3049 let converter = RowConverter::new(vec![SortField::new_with_options(
3050 DataType::Binary,
3051 SortOptions::default().desc().with_nulls_first(false),
3052 )])
3053 .unwrap();
3054 let rows = converter.convert_columns(&[Arc::clone(&col)]).unwrap();
3055
3056 for i in 0..rows.num_rows() {
3057 for j in i + 1..rows.num_rows() {
3058 assert!(
3059 rows.row(i) > rows.row(j),
3060 "{} > {} - {:?} > {:?}",
3061 i,
3062 j,
3063 rows.row(i),
3064 rows.row(j)
3065 );
3066 }
3067 }
3068
3069 let cols = converter.convert_rows(&rows).unwrap();
3070 assert_eq!(&cols[0], &col);
3071 }
3072
3073 fn dictionary_eq(a: &dyn Array, b: &dyn Array) {
3075 match b.data_type() {
3076 DataType::Dictionary(_, v) => {
3077 assert_eq!(a.data_type(), v.as_ref());
3078 let b = arrow_cast::cast(b, v).unwrap();
3079 assert_eq!(a, b.as_ref())
3080 }
3081 _ => assert_eq!(a, b),
3082 }
3083 }
3084
3085 #[test]
3086 fn test_string_dictionary() {
3087 let a = Arc::new(DictionaryArray::<Int32Type>::from_iter([
3088 Some("foo"),
3089 Some("hello"),
3090 Some("he"),
3091 None,
3092 Some("hello"),
3093 Some(""),
3094 Some("hello"),
3095 Some("hello"),
3096 ])) as ArrayRef;
3097
3098 let field = SortField::new(a.data_type().clone());
3099 let converter = RowConverter::new(vec![field]).unwrap();
3100 let rows_a = converter.convert_columns(&[Arc::clone(&a)]).unwrap();
3101
3102 assert!(rows_a.row(3) < rows_a.row(5));
3103 assert!(rows_a.row(2) < rows_a.row(1));
3104 assert!(rows_a.row(0) < rows_a.row(1));
3105 assert!(rows_a.row(3) < rows_a.row(0));
3106
3107 assert_eq!(rows_a.row(1), rows_a.row(4));
3108 assert_eq!(rows_a.row(1), rows_a.row(6));
3109 assert_eq!(rows_a.row(1), rows_a.row(7));
3110
3111 let cols = converter.convert_rows(&rows_a).unwrap();
3112 dictionary_eq(&cols[0], &a);
3113
3114 let b = Arc::new(DictionaryArray::<Int32Type>::from_iter([
3115 Some("hello"),
3116 None,
3117 Some("cupcakes"),
3118 ])) as ArrayRef;
3119
3120 let rows_b = converter.convert_columns(&[Arc::clone(&b)]).unwrap();
3121 assert_eq!(rows_a.row(1), rows_b.row(0));
3122 assert_eq!(rows_a.row(3), rows_b.row(1));
3123 assert!(rows_b.row(2) < rows_a.row(0));
3124
3125 let cols = converter.convert_rows(&rows_b).unwrap();
3126 dictionary_eq(&cols[0], &b);
3127
3128 let converter = RowConverter::new(vec![SortField::new_with_options(
3129 a.data_type().clone(),
3130 SortOptions::default().desc().with_nulls_first(false),
3131 )])
3132 .unwrap();
3133
3134 let rows_c = converter.convert_columns(&[Arc::clone(&a)]).unwrap();
3135 assert!(rows_c.row(3) > rows_c.row(5));
3136 assert!(rows_c.row(2) > rows_c.row(1));
3137 assert!(rows_c.row(0) > rows_c.row(1));
3138 assert!(rows_c.row(3) > rows_c.row(0));
3139
3140 let cols = converter.convert_rows(&rows_c).unwrap();
3141 dictionary_eq(&cols[0], &a);
3142
3143 let converter = RowConverter::new(vec![SortField::new_with_options(
3144 a.data_type().clone(),
3145 SortOptions::default().desc().with_nulls_first(true),
3146 )])
3147 .unwrap();
3148
3149 let rows_c = converter.convert_columns(&[Arc::clone(&a)]).unwrap();
3150 assert!(rows_c.row(3) < rows_c.row(5));
3151 assert!(rows_c.row(2) > rows_c.row(1));
3152 assert!(rows_c.row(0) > rows_c.row(1));
3153 assert!(rows_c.row(3) < rows_c.row(0));
3154
3155 let cols = converter.convert_rows(&rows_c).unwrap();
3156 dictionary_eq(&cols[0], &a);
3157 }
3158
3159 #[test]
3160 fn test_struct() {
3161 let a = Arc::new(Int32Array::from(vec![1, 1, 2, 2])) as ArrayRef;
3163 let a_f = Arc::new(Field::new("int", DataType::Int32, false));
3164 let u = Arc::new(StringArray::from(vec!["a", "b", "c", "d"])) as ArrayRef;
3165 let u_f = Arc::new(Field::new("s", DataType::Utf8, false));
3166 let s1 = Arc::new(StructArray::from(vec![(a_f, a), (u_f, u)])) as ArrayRef;
3167
3168 let sort_fields = vec![SortField::new(s1.data_type().clone())];
3169 let converter = RowConverter::new(sort_fields).unwrap();
3170 let r1 = converter.convert_columns(&[Arc::clone(&s1)]).unwrap();
3171
3172 for (a, b) in r1.iter().zip(r1.iter().skip(1)) {
3173 assert!(a < b);
3174 }
3175
3176 let back = converter.convert_rows(&r1).unwrap();
3177 assert_eq!(back.len(), 1);
3178 assert_eq!(&back[0], &s1);
3179
3180 let data = s1
3182 .to_data()
3183 .into_builder()
3184 .null_bit_buffer(Some(Buffer::from_slice_ref([0b00001010])))
3185 .null_count(2)
3186 .build()
3187 .unwrap();
3188
3189 let s2 = Arc::new(StructArray::from(data)) as ArrayRef;
3190 let r2 = converter.convert_columns(&[Arc::clone(&s2)]).unwrap();
3191 assert_eq!(r2.row(0), r2.row(2)); assert!(r2.row(0) < r2.row(1)); assert_ne!(r1.row(0), r2.row(0)); assert_eq!(r1.row(1), r2.row(1)); let back = converter.convert_rows(&r2).unwrap();
3197 assert_eq!(back.len(), 1);
3198 assert_eq!(&back[0], &s2);
3199
3200 back[0].to_data().validate_full().unwrap();
3201 }
3202
3203 #[test]
3204 fn test_dictionary_in_struct() {
3205 let builder = StringDictionaryBuilder::<Int32Type>::new();
3206 let mut struct_builder = StructBuilder::new(
3207 vec![Field::new_dictionary(
3208 "foo",
3209 DataType::Int32,
3210 DataType::Utf8,
3211 true,
3212 )],
3213 vec![Box::new(builder)],
3214 );
3215
3216 let dict_builder = struct_builder
3217 .field_builder::<StringDictionaryBuilder<Int32Type>>(0)
3218 .unwrap();
3219
3220 dict_builder.append_value("a");
3222 dict_builder.append_null();
3223 dict_builder.append_value("a");
3224 dict_builder.append_value("b");
3225
3226 for _ in 0..4 {
3227 struct_builder.append(true);
3228 }
3229
3230 let s = Arc::new(struct_builder.finish()) as ArrayRef;
3231 let sort_fields = vec![SortField::new(s.data_type().clone())];
3232 let converter = RowConverter::new(sort_fields).unwrap();
3233 let r = converter.convert_columns(&[Arc::clone(&s)]).unwrap();
3234
3235 let back = converter.convert_rows(&r).unwrap();
3236 let [s2] = back.try_into().unwrap();
3237
3238 assert_ne!(&s.data_type(), &s2.data_type());
3241 s2.to_data().validate_full().unwrap();
3242
3243 let s1_struct = s.as_struct();
3247 let s1_0 = s1_struct.column(0);
3248 let s1_idx_0 = s1_0.as_dictionary::<Int32Type>();
3249 let keys = s1_idx_0.keys();
3250 let values = s1_idx_0.values().as_string::<i32>();
3251 let s2_struct = s2.as_struct();
3253 let s2_0 = s2_struct.column(0);
3254 let s2_idx_0 = s2_0.as_string::<i32>();
3255
3256 for i in 0..keys.len() {
3257 if keys.is_null(i) {
3258 assert!(s2_idx_0.is_null(i));
3259 } else {
3260 let dict_index = keys.value(i) as usize;
3261 assert_eq!(values.value(dict_index), s2_idx_0.value(i));
3262 }
3263 }
3264 }
3265
3266 #[test]
3267 fn test_dictionary_in_struct_empty() {
3268 let ty = DataType::Struct(
3269 vec![Field::new_dictionary(
3270 "foo",
3271 DataType::Int32,
3272 DataType::Int32,
3273 false,
3274 )]
3275 .into(),
3276 );
3277 let s = arrow_array::new_empty_array(&ty);
3278
3279 let sort_fields = vec![SortField::new(s.data_type().clone())];
3280 let converter = RowConverter::new(sort_fields).unwrap();
3281 let r = converter.convert_columns(&[Arc::clone(&s)]).unwrap();
3282
3283 let back = converter.convert_rows(&r).unwrap();
3284 let [s2] = back.try_into().unwrap();
3285
3286 assert_ne!(&s.data_type(), &s2.data_type());
3289 s2.to_data().validate_full().unwrap();
3290 assert_eq!(s.len(), 0);
3291 assert_eq!(s2.len(), 0);
3292 }
3293
3294 #[test]
3295 fn test_list_of_string_dictionary() {
3296 let mut builder = ListBuilder::<StringDictionaryBuilder<Int32Type>>::default();
3297 builder.values().append("a").unwrap();
3299 builder.values().append("b").unwrap();
3300 builder.values().append("zero").unwrap();
3301 builder.values().append_null();
3302 builder.values().append("c").unwrap();
3303 builder.values().append("b").unwrap();
3304 builder.values().append("d").unwrap();
3305 builder.append(true);
3306 builder.append(false);
3308 builder.values().append("e").unwrap();
3310 builder.values().append("zero").unwrap();
3311 builder.values().append("a").unwrap();
3312 builder.append(true);
3313
3314 let a = Arc::new(builder.finish()) as ArrayRef;
3315 let data_type = a.data_type().clone();
3316
3317 let field = SortField::new(data_type.clone());
3318 let converter = RowConverter::new(vec![field]).unwrap();
3319 let rows = converter.convert_columns(&[Arc::clone(&a)]).unwrap();
3320
3321 let back = converter.convert_rows(&rows).unwrap();
3322 assert_eq!(back.len(), 1);
3323 let [a2] = back.try_into().unwrap();
3324
3325 assert_ne!(&a.data_type(), &a2.data_type());
3328
3329 a2.to_data().validate_full().unwrap();
3330
3331 let a2_list = a2.as_list::<i32>();
3332 let a1_list = a.as_list::<i32>();
3333
3334 let a1_0 = a1_list.value(0);
3337 let a1_idx_0 = a1_0.as_dictionary::<Int32Type>();
3338 let keys = a1_idx_0.keys();
3339 let values = a1_idx_0.values().as_string::<i32>();
3340 let a2_0 = a2_list.value(0);
3341 let a2_idx_0 = a2_0.as_string::<i32>();
3342
3343 for i in 0..keys.len() {
3344 if keys.is_null(i) {
3345 assert!(a2_idx_0.is_null(i));
3346 } else {
3347 let dict_index = keys.value(i) as usize;
3348 assert_eq!(values.value(dict_index), a2_idx_0.value(i));
3349 }
3350 }
3351
3352 assert!(a1_list.is_null(1));
3354 assert!(a2_list.is_null(1));
3355
3356 let a1_2 = a1_list.value(2);
3358 let a1_idx_2 = a1_2.as_dictionary::<Int32Type>();
3359 let keys = a1_idx_2.keys();
3360 let values = a1_idx_2.values().as_string::<i32>();
3361 let a2_2 = a2_list.value(2);
3362 let a2_idx_2 = a2_2.as_string::<i32>();
3363
3364 for i in 0..keys.len() {
3365 if keys.is_null(i) {
3366 assert!(a2_idx_2.is_null(i));
3367 } else {
3368 let dict_index = keys.value(i) as usize;
3369 assert_eq!(values.value(dict_index), a2_idx_2.value(i));
3370 }
3371 }
3372 }
3373
3374 #[test]
3375 fn test_primitive_dictionary() {
3376 let mut builder = PrimitiveDictionaryBuilder::<Int32Type, Int32Type>::new();
3377 builder.append(2).unwrap();
3378 builder.append(3).unwrap();
3379 builder.append(0).unwrap();
3380 builder.append_null();
3381 builder.append(5).unwrap();
3382 builder.append(3).unwrap();
3383 builder.append(-1).unwrap();
3384
3385 let a = builder.finish();
3386 let data_type = a.data_type().clone();
3387 let columns = [Arc::new(a) as ArrayRef];
3388
3389 let field = SortField::new(data_type.clone());
3390 let converter = RowConverter::new(vec![field]).unwrap();
3391 let rows = converter.convert_columns(&columns).unwrap();
3392 assert!(rows.row(0) < rows.row(1));
3393 assert!(rows.row(2) < rows.row(0));
3394 assert!(rows.row(3) < rows.row(2));
3395 assert!(rows.row(6) < rows.row(2));
3396 assert!(rows.row(3) < rows.row(6));
3397
3398 let back = converter.convert_rows(&rows).unwrap();
3399 assert_eq!(back.len(), 1);
3400 back[0].to_data().validate_full().unwrap();
3401 }
3402
3403 #[test]
3404 fn test_dictionary_nulls() {
3405 let values = Int32Array::from_iter([Some(1), Some(-1), None, Some(4), None]).into_data();
3406 let keys =
3407 Int32Array::from_iter([Some(0), Some(0), Some(1), Some(2), Some(4), None]).into_data();
3408
3409 let data_type = DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Int32));
3410 let data = keys
3411 .into_builder()
3412 .data_type(data_type.clone())
3413 .child_data(vec![values])
3414 .build()
3415 .unwrap();
3416
3417 let columns = [Arc::new(DictionaryArray::<Int32Type>::from(data)) as ArrayRef];
3418 let field = SortField::new(data_type.clone());
3419 let converter = RowConverter::new(vec![field]).unwrap();
3420 let rows = converter.convert_columns(&columns).unwrap();
3421
3422 assert_eq!(rows.row(0), rows.row(1));
3423 assert_eq!(rows.row(3), rows.row(4));
3424 assert_eq!(rows.row(4), rows.row(5));
3425 assert!(rows.row(3) < rows.row(0));
3426 }
3427
3428 #[test]
3429 fn test_sparse_dictionary_values() {
3430 let values = StringArray::from_iter_values((0..100_000).map(|i| format!("value-{i}")));
3431 let keys = Int32Array::from(vec![
3432 Some(0),
3433 Some(99_999),
3434 None,
3435 Some(7),
3436 Some(99_999),
3437 Some(3),
3438 ]);
3439 let dictionary = DictionaryArray::<Int32Type>::try_new(keys, Arc::new(values)).unwrap();
3440 let sparse = Arc::new(dictionary.slice(1, 4)) as ArrayRef;
3441
3442 let expected = Arc::new(DictionaryArray::<Int32Type>::from_iter([
3443 Some("value-99999"),
3444 None,
3445 Some("value-7"),
3446 Some("value-99999"),
3447 ])) as ArrayRef;
3448
3449 let converter =
3450 RowConverter::new(vec![SortField::new(sparse.data_type().clone())]).unwrap();
3451 let actual_rows = converter.convert_columns(&[sparse]).unwrap();
3452 let expected_rows = converter.convert_columns(&[Arc::clone(&expected)]).unwrap();
3453
3454 for (actual, expected) in actual_rows.iter().zip(&expected_rows) {
3455 assert_eq!(actual, expected);
3456 }
3457 let decoded = converter.convert_rows(&actual_rows).unwrap();
3458 dictionary_eq(&decoded[0], &expected);
3459 }
3460
3461 #[test]
3462 fn test_gather_dictionary_byte_values() {
3463 let keys = Int8Array::from(vec![Some(0), Some(3), None, Some(1), Some(3), Some(2)]);
3464 let values = Arc::new(StringArray::from(vec![
3465 Some("unused"),
3466 None,
3467 Some("é"),
3468 Some("selected"),
3469 ]));
3470 let dictionary = DictionaryArray::<Int8Type>::try_new(keys, values).unwrap();
3471 let sliced = dictionary.slice(1, 4);
3472 let gathered = gather_dictionary_values(&sliced).unwrap();
3473 let expected = StringArray::from(vec![Some("selected"), None, None, Some("selected")]);
3474 assert_eq!(gathered.as_ref(), &expected as &dyn Array);
3475 }
3476
3477 #[test]
3478 fn test_gather_dictionary_generic_values() {
3479 let keys = UInt8Array::from(vec![Some(2), None, Some(0), Some(1), Some(2)]);
3480 let values = Arc::new(Int32Array::from(vec![Some(1), None, Some(3)]));
3481 let dictionary = DictionaryArray::<UInt8Type>::try_new(keys, values).unwrap();
3482 let sliced = dictionary.slice(1, 4);
3483 let gathered = gather_dictionary_values(&sliced).unwrap();
3484 let expected = Int32Array::from(vec![Some(1), Some(1), None, Some(3)]);
3485 assert_eq!(gathered.as_ref(), &expected as &dyn Array);
3486 }
3487
3488 #[test]
3489 fn test_sparse_binary_dictionary_with_null_values() {
3490 let values = BinaryArray::from_iter((0..DICTIONARY_GATHER_MIN_VALUES).map(|index| {
3491 if index == 0 {
3492 None
3493 } else {
3494 Some(&b"value"[..])
3495 }
3496 }));
3497 let keys = UInt64Array::from(vec![Some(0), Some(32_767), None]);
3498 let dictionary = DictionaryArray::<UInt64Type>::try_new(keys, Arc::new(values)).unwrap();
3499 let input = Arc::new(dictionary) as ArrayRef;
3500 let expected =
3501 Arc::new(BinaryArray::from(vec![None, Some(&b"value"[..]), None])) as ArrayRef;
3502 let converter = RowConverter::new(vec![SortField::new(input.data_type().clone())]).unwrap();
3503 let actual_rows = converter.convert_columns(&[input]).unwrap();
3504 let expected_converter = RowConverter::new(vec![SortField::new(DataType::Binary)]).unwrap();
3505 let expected_rows = expected_converter
3506 .convert_columns(&[Arc::clone(&expected)])
3507 .unwrap();
3508 for (actual, expected) in actual_rows.iter().zip(&expected_rows) {
3509 assert_eq!(actual, expected);
3510 }
3511 let decoded = converter.convert_rows(&actual_rows).unwrap();
3512 assert_eq!(decoded[0].as_ref(), expected.as_ref());
3513 }
3514
3515 #[test]
3516 fn test_sparse_dictionary_gather_overflow_falls_back() {
3517 let inner = RunArray::<Int16Type>::try_new(
3518 &PrimitiveArray::from(vec![1_i16]),
3519 &Int32Array::from(vec![1]),
3520 )
3521 .unwrap();
3522 let values = RunArray::<Int64Type>::try_new(
3523 &PrimitiveArray::from(vec![
3524 (DICTIONARY_GATHER_MIN_VALUES * DICTIONARY_GATHER_RATIO) as i64,
3525 ]),
3526 &inner,
3527 )
3528 .unwrap();
3529 let keys = Int32Array::from(vec![0; DICTIONARY_GATHER_MIN_VALUES]);
3530 let dictionary = DictionaryArray::<Int32Type>::try_new(keys, Arc::new(values)).unwrap();
3531
3532 let input = Arc::new(dictionary) as ArrayRef;
3533 let converter = RowConverter::new(vec![SortField::new(input.data_type().clone())]).unwrap();
3534 let rows = converter.convert_columns(&[input]).unwrap();
3535
3536 assert_eq!(rows.num_rows(), DICTIONARY_GATHER_MIN_VALUES);
3537 let first = rows.row(0);
3538 assert!(rows.iter().all(|row| row == first));
3539 }
3540
3541 #[test]
3542 fn test_from_binary_shared_buffer() {
3543 let converter = RowConverter::new(vec![SortField::new(DataType::Binary)]).unwrap();
3544 let array = Arc::new(BinaryArray::from_iter_values([&[0xFF]])) as _;
3545 let rows = converter.convert_columns(&[array]).unwrap();
3546 let binary_rows = rows.try_into_binary().expect("known-small rows");
3547 let _binary_rows_shared_buffer = binary_rows.clone();
3548
3549 let parsed = converter.from_binary(binary_rows);
3550
3551 converter.convert_rows(parsed.iter()).unwrap();
3552 }
3553
3554 #[test]
3555 #[should_panic(expected = "Encountered non UTF-8 data")]
3556 fn test_invalid_utf8() {
3557 let converter = RowConverter::new(vec![SortField::new(DataType::Binary)]).unwrap();
3558 let array = Arc::new(BinaryArray::from_iter_values([&[0xFF]])) as _;
3559 let rows = converter.convert_columns(&[array]).unwrap();
3560 let binary_row = rows.row(0);
3561
3562 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
3563 let parser = converter.parser();
3564 let utf8_row = parser.parse(binary_row.as_ref());
3565
3566 converter.convert_rows(std::iter::once(utf8_row)).unwrap();
3567 }
3568
3569 #[test]
3570 #[should_panic(expected = "Encountered non UTF-8 data")]
3571 fn test_invalid_utf8_array() {
3572 let converter = RowConverter::new(vec![SortField::new(DataType::Binary)]).unwrap();
3573 let array = Arc::new(BinaryArray::from_iter_values([&[0xFF]])) as _;
3574 let rows = converter.convert_columns(&[array]).unwrap();
3575 let binary_rows = rows.try_into_binary().expect("known-small rows");
3576
3577 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
3578 let parsed = converter.from_binary(binary_rows);
3579
3580 converter.convert_rows(parsed.iter()).unwrap();
3581 }
3582
3583 #[test]
3584 #[should_panic(expected = "index out of bounds")]
3585 fn test_invalid_empty() {
3586 let binary_row: &[u8] = &[];
3587
3588 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
3589 let parser = converter.parser();
3590 let utf8_row = parser.parse(binary_row.as_ref());
3591
3592 converter.convert_rows(std::iter::once(utf8_row)).unwrap();
3593 }
3594
3595 #[test]
3596 #[should_panic(expected = "index out of bounds")]
3597 fn test_invalid_empty_array() {
3598 let row: &[u8] = &[];
3599 let binary_rows = BinaryArray::from(vec![row]);
3600
3601 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
3602 let parsed = converter.from_binary(binary_rows);
3603
3604 converter.convert_rows(parsed.iter()).unwrap();
3605 }
3606
3607 #[test]
3608 #[should_panic(expected = "index out of bounds")]
3609 fn test_invalid_truncated() {
3610 let binary_row: &[u8] = &[0x02];
3611
3612 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
3613 let parser = converter.parser();
3614 let utf8_row = parser.parse(binary_row.as_ref());
3615
3616 converter.convert_rows(std::iter::once(utf8_row)).unwrap();
3617 }
3618
3619 #[test]
3620 #[should_panic(expected = "index out of bounds")]
3621 fn test_invalid_truncated_array() {
3622 let row: &[u8] = &[0x02];
3623 let binary_rows = BinaryArray::from(vec![row]);
3624
3625 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
3626 let parsed = converter.from_binary(binary_rows);
3627
3628 converter.convert_rows(parsed.iter()).unwrap();
3629 }
3630
3631 #[test]
3632 #[should_panic(expected = "rows were not produced by this RowConverter")]
3633 fn test_different_converter() {
3634 let values = Arc::new(Int32Array::from_iter([Some(1), Some(-1)]));
3635 let converter = RowConverter::new(vec![SortField::new(DataType::Int32)]).unwrap();
3636 let rows = converter.convert_columns(&[values]).unwrap();
3637
3638 let converter = RowConverter::new(vec![SortField::new(DataType::Int32)]).unwrap();
3639 let _ = converter.convert_rows(&rows);
3640 }
3641
3642 fn test_single_list<O: OffsetSizeTrait>() {
3643 let mut builder = GenericListBuilder::<O, _>::new(Int32Builder::new());
3644 builder.values().append_value(32);
3645 builder.values().append_value(52);
3646 builder.values().append_value(32);
3647 builder.append(true);
3648 builder.values().append_value(32);
3649 builder.values().append_value(52);
3650 builder.values().append_value(12);
3651 builder.append(true);
3652 builder.values().append_value(32);
3653 builder.values().append_value(52);
3654 builder.append(true);
3655 builder.values().append_value(32); builder.values().append_value(52); builder.append(false);
3658 builder.values().append_value(32);
3659 builder.values().append_null();
3660 builder.append(true);
3661 builder.append(true);
3662 builder.values().append_value(17); builder.values().append_null(); builder.append(false);
3665
3666 let list = Arc::new(builder.finish()) as ArrayRef;
3667 let d = list.data_type().clone();
3668
3669 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
3670
3671 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3672 assert!(rows.row(0) > rows.row(1)); assert!(rows.row(2) < rows.row(1)); assert!(rows.row(3) < rows.row(2)); assert!(rows.row(4) < rows.row(2)); assert!(rows.row(5) < rows.row(2)); assert!(rows.row(3) < rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3681 assert_eq!(back.len(), 1);
3682 back[0].to_data().validate_full().unwrap();
3683 assert_eq!(&back[0], &list);
3684
3685 let options = SortOptions::default().asc().with_nulls_first(false);
3686 let field = SortField::new_with_options(d.clone(), options);
3687 let converter = RowConverter::new(vec![field]).unwrap();
3688 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3689
3690 assert!(rows.row(0) > rows.row(1)); assert!(rows.row(2) < rows.row(1)); assert!(rows.row(3) > rows.row(2)); assert!(rows.row(4) > rows.row(2)); assert!(rows.row(5) < rows.row(2)); assert!(rows.row(3) > rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3699 assert_eq!(back.len(), 1);
3700 back[0].to_data().validate_full().unwrap();
3701 assert_eq!(&back[0], &list);
3702
3703 let options = SortOptions::default().desc().with_nulls_first(false);
3704 let field = SortField::new_with_options(d.clone(), options);
3705 let converter = RowConverter::new(vec![field]).unwrap();
3706 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3707
3708 assert!(rows.row(0) < rows.row(1)); assert!(rows.row(2) > rows.row(1)); assert!(rows.row(3) > rows.row(2)); assert!(rows.row(4) > rows.row(2)); assert!(rows.row(5) > rows.row(2)); assert!(rows.row(3) > rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3717 assert_eq!(back.len(), 1);
3718 back[0].to_data().validate_full().unwrap();
3719 assert_eq!(&back[0], &list);
3720
3721 let options = SortOptions::default().desc().with_nulls_first(true);
3722 let field = SortField::new_with_options(d, options);
3723 let converter = RowConverter::new(vec![field]).unwrap();
3724 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3725
3726 assert!(rows.row(0) < rows.row(1)); assert!(rows.row(2) > rows.row(1)); assert!(rows.row(3) < rows.row(2)); assert!(rows.row(4) < rows.row(2)); assert!(rows.row(5) > rows.row(2)); assert!(rows.row(3) < rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3735 assert_eq!(back.len(), 1);
3736 back[0].to_data().validate_full().unwrap();
3737 assert_eq!(&back[0], &list);
3738
3739 let sliced_list = list.slice(1, 5);
3740 let rows_on_sliced_list = converter
3741 .convert_columns(&[Arc::clone(&sliced_list)])
3742 .unwrap();
3743
3744 assert!(rows_on_sliced_list.row(1) > rows_on_sliced_list.row(0)); assert!(rows_on_sliced_list.row(2) < rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(3) < rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(4) > rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(2) < rows_on_sliced_list.row(4)); let back = converter.convert_rows(&rows_on_sliced_list).unwrap();
3751 assert_eq!(back.len(), 1);
3752 back[0].to_data().validate_full().unwrap();
3753 assert_eq!(&back[0], &sliced_list);
3754 }
3755
3756 fn test_nested_list<O: OffsetSizeTrait>() {
3757 let mut builder =
3758 GenericListBuilder::<O, _>::new(GenericListBuilder::<O, _>::new(Int32Builder::new()));
3759
3760 builder.values().values().append_value(1);
3761 builder.values().values().append_value(2);
3762 builder.values().append(true);
3763 builder.values().values().append_value(1);
3764 builder.values().values().append_null();
3765 builder.values().append(true);
3766 builder.append(true);
3767
3768 builder.values().values().append_value(1);
3769 builder.values().values().append_null();
3770 builder.values().append(true);
3771 builder.values().values().append_value(1);
3772 builder.values().values().append_null();
3773 builder.values().append(true);
3774 builder.append(true);
3775
3776 builder.values().values().append_value(1);
3777 builder.values().values().append_null();
3778 builder.values().append(true);
3779 builder.values().append(false);
3780 builder.append(true);
3781 builder.append(false);
3782
3783 builder.values().values().append_value(1);
3784 builder.values().values().append_value(2);
3785 builder.values().append(true);
3786 builder.append(true);
3787
3788 let list = Arc::new(builder.finish()) as ArrayRef;
3789 let d = list.data_type().clone();
3790
3791 let options = SortOptions::default().asc().with_nulls_first(true);
3799 let field = SortField::new_with_options(d.clone(), options);
3800 let converter = RowConverter::new(vec![field]).unwrap();
3801 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3802
3803 assert!(rows.row(0) > rows.row(1));
3804 assert!(rows.row(1) > rows.row(2));
3805 assert!(rows.row(2) > rows.row(3));
3806 assert!(rows.row(4) < rows.row(0));
3807 assert!(rows.row(4) > rows.row(1));
3808
3809 let back = converter.convert_rows(&rows).unwrap();
3810 assert_eq!(back.len(), 1);
3811 back[0].to_data().validate_full().unwrap();
3812 assert_eq!(&back[0], &list);
3813
3814 let options = SortOptions::default().desc().with_nulls_first(true);
3815 let field = SortField::new_with_options(d.clone(), options);
3816 let converter = RowConverter::new(vec![field]).unwrap();
3817 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3818
3819 assert!(rows.row(0) > rows.row(1));
3820 assert!(rows.row(1) > rows.row(2));
3821 assert!(rows.row(2) > rows.row(3));
3822 assert!(rows.row(4) > rows.row(0));
3823 assert!(rows.row(4) > rows.row(1));
3824
3825 let back = converter.convert_rows(&rows).unwrap();
3826 assert_eq!(back.len(), 1);
3827 back[0].to_data().validate_full().unwrap();
3828 assert_eq!(&back[0], &list);
3829
3830 let options = SortOptions::default().desc().with_nulls_first(false);
3831 let field = SortField::new_with_options(d, options);
3832 let converter = RowConverter::new(vec![field]).unwrap();
3833 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3834
3835 assert!(rows.row(0) < rows.row(1));
3836 assert!(rows.row(1) < rows.row(2));
3837 assert!(rows.row(2) < rows.row(3));
3838 assert!(rows.row(4) > rows.row(0));
3839 assert!(rows.row(4) < rows.row(1));
3840
3841 let back = converter.convert_rows(&rows).unwrap();
3842 assert_eq!(back.len(), 1);
3843 back[0].to_data().validate_full().unwrap();
3844 assert_eq!(&back[0], &list);
3845
3846 let sliced_list = list.slice(1, 3);
3847 let rows = converter
3848 .convert_columns(&[Arc::clone(&sliced_list)])
3849 .unwrap();
3850
3851 assert!(rows.row(0) < rows.row(1));
3852 assert!(rows.row(1) < rows.row(2));
3853
3854 let back = converter.convert_rows(&rows).unwrap();
3855 assert_eq!(back.len(), 1);
3856 back[0].to_data().validate_full().unwrap();
3857 assert_eq!(&back[0], &sliced_list);
3858 }
3859
3860 #[test]
3861 fn test_list() {
3862 test_single_list::<i32>();
3863 test_nested_list::<i32>();
3864 }
3865
3866 #[test]
3867 fn test_large_list() {
3868 test_single_list::<i64>();
3869 test_nested_list::<i64>();
3870 }
3871
3872 fn test_single_list_view<O: OffsetSizeTrait>() {
3873 let mut builder = GenericListViewBuilder::<O, _>::new(Int32Builder::new());
3874 builder.values().append_value(32);
3875 builder.values().append_value(52);
3876 builder.values().append_value(32);
3877 builder.append(true);
3878 builder.values().append_value(32);
3879 builder.values().append_value(52);
3880 builder.values().append_value(12);
3881 builder.append(true);
3882 builder.values().append_value(32);
3883 builder.values().append_value(52);
3884 builder.append(true);
3885 builder.values().append_value(32); builder.values().append_value(52); builder.append(false);
3888 builder.values().append_value(32);
3889 builder.values().append_null();
3890 builder.append(true);
3891 builder.append(true);
3892 builder.values().append_value(17); builder.values().append_null(); builder.append(false);
3895
3896 let list = Arc::new(builder.finish()) as ArrayRef;
3897 let d = list.data_type().clone();
3898
3899 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
3900
3901 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3902 assert!(rows.row(0) > rows.row(1)); assert!(rows.row(2) < rows.row(1)); assert!(rows.row(3) < rows.row(2)); assert!(rows.row(4) < rows.row(2)); assert!(rows.row(5) < rows.row(2)); assert!(rows.row(3) < rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3911 assert_eq!(back.len(), 1);
3912 back[0].to_data().validate_full().unwrap();
3913
3914 let back_list_view = back[0]
3916 .as_any()
3917 .downcast_ref::<GenericListViewArray<O>>()
3918 .unwrap();
3919 let orig_list_view = list
3920 .as_any()
3921 .downcast_ref::<GenericListViewArray<O>>()
3922 .unwrap();
3923
3924 assert_eq!(back_list_view.len(), orig_list_view.len());
3925 for i in 0..back_list_view.len() {
3926 assert_eq!(back_list_view.is_valid(i), orig_list_view.is_valid(i));
3927 if back_list_view.is_valid(i) {
3928 assert_eq!(&back_list_view.value(i), &orig_list_view.value(i));
3929 }
3930 }
3931
3932 let options = SortOptions::default().asc().with_nulls_first(false);
3933 let field = SortField::new_with_options(d.clone(), options);
3934 let converter = RowConverter::new(vec![field]).unwrap();
3935 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3936
3937 assert!(rows.row(0) > rows.row(1)); assert!(rows.row(2) < rows.row(1)); assert!(rows.row(3) > rows.row(2)); assert!(rows.row(4) > rows.row(2)); assert!(rows.row(5) < rows.row(2)); assert!(rows.row(3) > rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3946 assert_eq!(back.len(), 1);
3947 back[0].to_data().validate_full().unwrap();
3948
3949 let options = SortOptions::default().desc().with_nulls_first(false);
3950 let field = SortField::new_with_options(d.clone(), options);
3951 let converter = RowConverter::new(vec![field]).unwrap();
3952 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3953
3954 assert!(rows.row(0) < rows.row(1)); assert!(rows.row(2) > rows.row(1)); assert!(rows.row(3) > rows.row(2)); assert!(rows.row(4) > rows.row(2)); assert!(rows.row(5) > rows.row(2)); assert!(rows.row(3) > rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3963 assert_eq!(back.len(), 1);
3964 back[0].to_data().validate_full().unwrap();
3965
3966 let options = SortOptions::default().desc().with_nulls_first(true);
3967 let field = SortField::new_with_options(d, options);
3968 let converter = RowConverter::new(vec![field]).unwrap();
3969 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
3970
3971 assert!(rows.row(0) < rows.row(1)); assert!(rows.row(2) > rows.row(1)); assert!(rows.row(3) < rows.row(2)); assert!(rows.row(4) < rows.row(2)); assert!(rows.row(5) > rows.row(2)); assert!(rows.row(3) < rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
3980 assert_eq!(back.len(), 1);
3981 back[0].to_data().validate_full().unwrap();
3982
3983 let sliced_list = list.slice(1, 5);
3984 let rows_on_sliced_list = converter
3985 .convert_columns(&[Arc::clone(&sliced_list)])
3986 .unwrap();
3987
3988 assert!(rows_on_sliced_list.row(1) > rows_on_sliced_list.row(0)); assert!(rows_on_sliced_list.row(2) < rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(3) < rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(4) > rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(2) < rows_on_sliced_list.row(4)); let back = converter.convert_rows(&rows_on_sliced_list).unwrap();
3995 assert_eq!(back.len(), 1);
3996 back[0].to_data().validate_full().unwrap();
3997 }
3998
3999 fn test_nested_list_view<O: OffsetSizeTrait>() {
4000 let mut builder = GenericListViewBuilder::<O, _>::new(GenericListViewBuilder::<O, _>::new(
4001 Int32Builder::new(),
4002 ));
4003
4004 builder.values().values().append_value(1);
4006 builder.values().values().append_value(2);
4007 builder.values().append(true);
4008 builder.values().values().append_value(1);
4009 builder.values().values().append_null();
4010 builder.values().append(true);
4011 builder.append(true);
4012
4013 builder.values().values().append_value(1);
4015 builder.values().values().append_null();
4016 builder.values().append(true);
4017 builder.values().values().append_value(1);
4018 builder.values().values().append_null();
4019 builder.values().append(true);
4020 builder.append(true);
4021
4022 builder.values().values().append_value(1);
4024 builder.values().values().append_null();
4025 builder.values().append(true);
4026 builder.values().append(false);
4027 builder.append(true);
4028
4029 builder.append(false);
4031
4032 builder.values().values().append_value(1);
4034 builder.values().values().append_value(2);
4035 builder.values().append(true);
4036 builder.append(true);
4037
4038 let list = Arc::new(builder.finish()) as ArrayRef;
4039 let d = list.data_type().clone();
4040
4041 let options = SortOptions::default().asc().with_nulls_first(true);
4049 let field = SortField::new_with_options(d.clone(), options);
4050 let converter = RowConverter::new(vec![field]).unwrap();
4051 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4052
4053 assert!(rows.row(0) > rows.row(1));
4054 assert!(rows.row(1) > rows.row(2));
4055 assert!(rows.row(2) > rows.row(3));
4056 assert!(rows.row(4) < rows.row(0));
4057 assert!(rows.row(4) > rows.row(1));
4058
4059 let back = converter.convert_rows(&rows).unwrap();
4060 assert_eq!(back.len(), 1);
4061 back[0].to_data().validate_full().unwrap();
4062
4063 let back_list_view = back[0]
4065 .as_any()
4066 .downcast_ref::<GenericListViewArray<O>>()
4067 .unwrap();
4068 let orig_list_view = list
4069 .as_any()
4070 .downcast_ref::<GenericListViewArray<O>>()
4071 .unwrap();
4072
4073 assert_eq!(back_list_view.len(), orig_list_view.len());
4074 for i in 0..back_list_view.len() {
4075 assert_eq!(back_list_view.is_valid(i), orig_list_view.is_valid(i));
4076 if back_list_view.is_valid(i) {
4077 assert_eq!(&back_list_view.value(i), &orig_list_view.value(i));
4078 }
4079 }
4080
4081 let options = SortOptions::default().desc().with_nulls_first(true);
4082 let field = SortField::new_with_options(d.clone(), options);
4083 let converter = RowConverter::new(vec![field]).unwrap();
4084 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4085
4086 assert!(rows.row(0) > rows.row(1));
4087 assert!(rows.row(1) > rows.row(2));
4088 assert!(rows.row(2) > rows.row(3));
4089 assert!(rows.row(4) > rows.row(0));
4090 assert!(rows.row(4) > rows.row(1));
4091
4092 let back = converter.convert_rows(&rows).unwrap();
4093 assert_eq!(back.len(), 1);
4094 back[0].to_data().validate_full().unwrap();
4095
4096 let back_list_view = back[0]
4098 .as_any()
4099 .downcast_ref::<GenericListViewArray<O>>()
4100 .unwrap();
4101
4102 assert_eq!(back_list_view.len(), orig_list_view.len());
4103 for i in 0..back_list_view.len() {
4104 assert_eq!(back_list_view.is_valid(i), orig_list_view.is_valid(i));
4105 if back_list_view.is_valid(i) {
4106 assert_eq!(&back_list_view.value(i), &orig_list_view.value(i));
4107 }
4108 }
4109
4110 let options = SortOptions::default().desc().with_nulls_first(false);
4111 let field = SortField::new_with_options(d.clone(), options);
4112 let converter = RowConverter::new(vec![field]).unwrap();
4113 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4114
4115 assert!(rows.row(0) < rows.row(1));
4116 assert!(rows.row(1) < rows.row(2));
4117 assert!(rows.row(2) < rows.row(3));
4118 assert!(rows.row(4) > rows.row(0));
4119 assert!(rows.row(4) < rows.row(1));
4120
4121 let back = converter.convert_rows(&rows).unwrap();
4122 assert_eq!(back.len(), 1);
4123 back[0].to_data().validate_full().unwrap();
4124
4125 let back_list_view = back[0]
4127 .as_any()
4128 .downcast_ref::<GenericListViewArray<O>>()
4129 .unwrap();
4130
4131 assert_eq!(back_list_view.len(), orig_list_view.len());
4132 for i in 0..back_list_view.len() {
4133 assert_eq!(back_list_view.is_valid(i), orig_list_view.is_valid(i));
4134 if back_list_view.is_valid(i) {
4135 assert_eq!(&back_list_view.value(i), &orig_list_view.value(i));
4136 }
4137 }
4138
4139 let sliced_list = list.slice(1, 3);
4140 let rows = converter
4141 .convert_columns(&[Arc::clone(&sliced_list)])
4142 .unwrap();
4143
4144 assert!(rows.row(0) < rows.row(1));
4145 assert!(rows.row(1) < rows.row(2));
4146
4147 let back = converter.convert_rows(&rows).unwrap();
4148 assert_eq!(back.len(), 1);
4149 back[0].to_data().validate_full().unwrap();
4150 }
4151
4152 #[test]
4153 fn test_list_view() {
4154 test_single_list_view::<i32>();
4155 test_nested_list_view::<i32>();
4156 }
4157
4158 #[test]
4159 fn test_large_list_view() {
4160 test_single_list_view::<i64>();
4161 test_nested_list_view::<i64>();
4162 }
4163
4164 fn test_list_view_with_shared_values<O: OffsetSizeTrait>() {
4165 let values = Int32Array::from(vec![1, 2, 3, 4, 5, 6, 7, 8]);
4167 let field = Arc::new(Field::new_list_field(DataType::Int32, true));
4168
4169 let offsets = ScalarBuffer::<O>::from(vec![
4177 O::from_usize(0).unwrap(),
4178 O::from_usize(0).unwrap(),
4179 O::from_usize(5).unwrap(),
4180 O::from_usize(2).unwrap(),
4181 O::from_usize(1).unwrap(),
4182 O::from_usize(2).unwrap(),
4183 ]);
4184 let sizes = ScalarBuffer::<O>::from(vec![
4185 O::from_usize(3).unwrap(),
4186 O::from_usize(3).unwrap(),
4187 O::from_usize(2).unwrap(),
4188 O::from_usize(2).unwrap(),
4189 O::from_usize(4).unwrap(),
4190 O::from_usize(1).unwrap(),
4191 ]);
4192
4193 let list_view: GenericListViewArray<O> =
4194 GenericListViewArray::try_new(field, offsets, sizes, Arc::new(values), None).unwrap();
4195
4196 let d = list_view.data_type().clone();
4197 let list = Arc::new(list_view) as ArrayRef;
4198
4199 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4200 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4201
4202 assert_eq!(rows.row(0), rows.row(1));
4204
4205 assert!(rows.row(0) < rows.row(2));
4207
4208 assert!(rows.row(3) > rows.row(0));
4210
4211 assert!(rows.row(4) > rows.row(0));
4213
4214 assert!(rows.row(5) < rows.row(3));
4216
4217 assert!(rows.row(5) > rows.row(4));
4219
4220 let back = converter.convert_rows(&rows).unwrap();
4222 assert_eq!(back.len(), 1);
4223 back[0].to_data().validate_full().unwrap();
4224
4225 let back_list_view = back[0]
4227 .as_any()
4228 .downcast_ref::<GenericListViewArray<O>>()
4229 .unwrap();
4230 let orig_list_view = list
4231 .as_any()
4232 .downcast_ref::<GenericListViewArray<O>>()
4233 .unwrap();
4234
4235 assert_eq!(back_list_view.len(), orig_list_view.len());
4236 for i in 0..back_list_view.len() {
4237 assert_eq!(back_list_view.is_valid(i), orig_list_view.is_valid(i));
4238 if back_list_view.is_valid(i) {
4239 assert_eq!(&back_list_view.value(i), &orig_list_view.value(i));
4240 }
4241 }
4242
4243 let options = SortOptions::default().desc();
4245 let field = SortField::new_with_options(d, options);
4246 let converter = RowConverter::new(vec![field]).unwrap();
4247 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4248
4249 assert_eq!(rows.row(0), rows.row(1)); assert!(rows.row(0) > rows.row(2)); assert!(rows.row(3) < rows.row(0)); let back = converter.convert_rows(&rows).unwrap();
4255 assert_eq!(back.len(), 1);
4256 back[0].to_data().validate_full().unwrap();
4257 }
4258
4259 #[test]
4260 fn test_list_view_shared_values() {
4261 test_list_view_with_shared_values::<i32>();
4262 }
4263
4264 #[test]
4265 fn test_large_list_view_shared_values() {
4266 test_list_view_with_shared_values::<i64>();
4267 }
4268
4269 #[test]
4270 fn test_fixed_size_list() {
4271 let mut builder = FixedSizeListBuilder::new(Int32Builder::new(), 3);
4272 builder.values().append_value(32);
4273 builder.values().append_value(52);
4274 builder.values().append_value(32);
4275 builder.append(true);
4276 builder.values().append_value(32);
4277 builder.values().append_value(52);
4278 builder.values().append_value(12);
4279 builder.append(true);
4280 builder.values().append_value(32);
4281 builder.values().append_value(52);
4282 builder.values().append_null();
4283 builder.append(true);
4284 builder.values().append_value(32); builder.values().append_value(52); builder.values().append_value(13); builder.append(false);
4288 builder.values().append_value(32);
4289 builder.values().append_null();
4290 builder.values().append_null();
4291 builder.append(true);
4292 builder.values().append_null();
4293 builder.values().append_null();
4294 builder.values().append_null();
4295 builder.append(true);
4296 builder.values().append_value(17); builder.values().append_null(); builder.values().append_value(77); builder.append(false);
4300
4301 let list = Arc::new(builder.finish()) as ArrayRef;
4302 let d = list.data_type().clone();
4303
4304 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4306
4307 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4308 assert!(rows.row(0) > rows.row(1)); assert!(rows.row(2) < rows.row(1)); assert!(rows.row(3) < rows.row(2)); assert!(rows.row(4) < rows.row(2)); assert!(rows.row(5) < rows.row(2)); assert!(rows.row(3) < rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
4317 assert_eq!(back.len(), 1);
4318 back[0].to_data().validate_full().unwrap();
4319 assert_eq!(&back[0], &list);
4320
4321 let options = SortOptions::default().asc().with_nulls_first(false);
4323 let field = SortField::new_with_options(d.clone(), options);
4324 let converter = RowConverter::new(vec![field]).unwrap();
4325 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4326 assert!(rows.row(0) > rows.row(1)); assert!(rows.row(2) > rows.row(1)); assert!(rows.row(3) > rows.row(2)); assert!(rows.row(4) > rows.row(2)); assert!(rows.row(5) > rows.row(2)); assert!(rows.row(3) > rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
4335 assert_eq!(back.len(), 1);
4336 back[0].to_data().validate_full().unwrap();
4337 assert_eq!(&back[0], &list);
4338
4339 let options = SortOptions::default().desc().with_nulls_first(false);
4341 let field = SortField::new_with_options(d.clone(), options);
4342 let converter = RowConverter::new(vec![field]).unwrap();
4343 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4344 assert!(rows.row(0) < rows.row(1)); assert!(rows.row(2) > rows.row(1)); assert!(rows.row(3) > rows.row(2)); assert!(rows.row(4) > rows.row(2)); assert!(rows.row(5) > rows.row(2)); assert!(rows.row(3) > rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
4353 assert_eq!(back.len(), 1);
4354 back[0].to_data().validate_full().unwrap();
4355 assert_eq!(&back[0], &list);
4356
4357 let options = SortOptions::default().desc().with_nulls_first(true);
4359 let field = SortField::new_with_options(d, options);
4360 let converter = RowConverter::new(vec![field]).unwrap();
4361 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
4362
4363 assert!(rows.row(0) < rows.row(1)); assert!(rows.row(2) < rows.row(1)); assert!(rows.row(3) < rows.row(2)); assert!(rows.row(4) < rows.row(2)); assert!(rows.row(5) < rows.row(2)); assert!(rows.row(3) < rows.row(5)); assert_eq!(rows.row(3), rows.row(6)); let back = converter.convert_rows(&rows).unwrap();
4372 assert_eq!(back.len(), 1);
4373 back[0].to_data().validate_full().unwrap();
4374 assert_eq!(&back[0], &list);
4375
4376 let sliced_list = list.slice(1, 5);
4377 let rows_on_sliced_list = converter
4378 .convert_columns(&[Arc::clone(&sliced_list)])
4379 .unwrap();
4380
4381 assert!(rows_on_sliced_list.row(2) < rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(3) < rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(4) < rows_on_sliced_list.row(1)); assert!(rows_on_sliced_list.row(2) < rows_on_sliced_list.row(4)); let back = converter.convert_rows(&rows_on_sliced_list).unwrap();
4387 assert_eq!(back.len(), 1);
4388 back[0].to_data().validate_full().unwrap();
4389 assert_eq!(&back[0], &sliced_list);
4390 }
4391
4392 #[test]
4393 fn test_two_fixed_size_lists() {
4394 let mut first = FixedSizeListBuilder::new(UInt8Builder::new(), 1);
4395 first.values().append_value(100);
4397 first.append(true);
4398 first.values().append_value(101);
4400 first.append(true);
4401 first.values().append_value(102);
4403 first.append(true);
4404 first.values().append_null();
4406 first.append(true);
4407 first.values().append_null(); first.append(false);
4410 let first = Arc::new(first.finish()) as ArrayRef;
4411 let first_type = first.data_type().clone();
4412
4413 let mut second = FixedSizeListBuilder::new(UInt8Builder::new(), 1);
4414 second.values().append_value(200);
4416 second.append(true);
4417 second.values().append_value(201);
4419 second.append(true);
4420 second.values().append_value(202);
4422 second.append(true);
4423 second.values().append_null();
4425 second.append(true);
4426 second.values().append_null(); second.append(false);
4429 let second = Arc::new(second.finish()) as ArrayRef;
4430 let second_type = second.data_type().clone();
4431
4432 let converter = RowConverter::new(vec![
4433 SortField::new(first_type.clone()),
4434 SortField::new(second_type.clone()),
4435 ])
4436 .unwrap();
4437
4438 let rows = converter
4439 .convert_columns(&[Arc::clone(&first), Arc::clone(&second)])
4440 .unwrap();
4441
4442 let back = converter.convert_rows(&rows).unwrap();
4443 assert_eq!(back.len(), 2);
4444 back[0].to_data().validate_full().unwrap();
4445 assert_eq!(&back[0], &first);
4446 back[1].to_data().validate_full().unwrap();
4447 assert_eq!(&back[1], &second);
4448 }
4449
4450 #[test]
4451 fn test_fixed_size_list_with_variable_width_content() {
4452 let mut first = FixedSizeListBuilder::new(
4453 StructBuilder::from_fields(
4454 vec![
4455 Field::new(
4456 "timestamp",
4457 DataType::Timestamp(TimeUnit::Microsecond, Some(Arc::from("UTC"))),
4458 false,
4459 ),
4460 Field::new("offset_minutes", DataType::Int16, false),
4461 Field::new("time_zone", DataType::Utf8, false),
4462 ],
4463 1,
4464 ),
4465 1,
4466 );
4467 first
4469 .values()
4470 .field_builder::<TimestampMicrosecondBuilder>(0)
4471 .unwrap()
4472 .append_null();
4473 first
4474 .values()
4475 .field_builder::<Int16Builder>(1)
4476 .unwrap()
4477 .append_null();
4478 first
4479 .values()
4480 .field_builder::<StringBuilder>(2)
4481 .unwrap()
4482 .append_null();
4483 first.values().append(false);
4484 first.append(false);
4485 first
4487 .values()
4488 .field_builder::<TimestampMicrosecondBuilder>(0)
4489 .unwrap()
4490 .append_null();
4491 first
4492 .values()
4493 .field_builder::<Int16Builder>(1)
4494 .unwrap()
4495 .append_null();
4496 first
4497 .values()
4498 .field_builder::<StringBuilder>(2)
4499 .unwrap()
4500 .append_null();
4501 first.values().append(false);
4502 first.append(true);
4503 first
4505 .values()
4506 .field_builder::<TimestampMicrosecondBuilder>(0)
4507 .unwrap()
4508 .append_value(0);
4509 first
4510 .values()
4511 .field_builder::<Int16Builder>(1)
4512 .unwrap()
4513 .append_value(0);
4514 first
4515 .values()
4516 .field_builder::<StringBuilder>(2)
4517 .unwrap()
4518 .append_value("UTC");
4519 first.values().append(true);
4520 first.append(true);
4521 first
4523 .values()
4524 .field_builder::<TimestampMicrosecondBuilder>(0)
4525 .unwrap()
4526 .append_value(1126351800123456);
4527 first
4528 .values()
4529 .field_builder::<Int16Builder>(1)
4530 .unwrap()
4531 .append_value(120);
4532 first
4533 .values()
4534 .field_builder::<StringBuilder>(2)
4535 .unwrap()
4536 .append_value("Europe/Warsaw");
4537 first.values().append(true);
4538 first.append(true);
4539 let first = Arc::new(first.finish()) as ArrayRef;
4540 let first_type = first.data_type().clone();
4541
4542 let mut second = StringBuilder::new();
4543 second.append_value("somewhere near");
4544 second.append_null();
4545 second.append_value("Greenwich");
4546 second.append_value("Warsaw");
4547 let second = Arc::new(second.finish()) as ArrayRef;
4548 let second_type = second.data_type().clone();
4549
4550 let converter = RowConverter::new(vec![
4551 SortField::new(first_type.clone()),
4552 SortField::new(second_type.clone()),
4553 ])
4554 .unwrap();
4555
4556 let rows = converter
4557 .convert_columns(&[Arc::clone(&first), Arc::clone(&second)])
4558 .unwrap();
4559
4560 let back = converter.convert_rows(&rows).unwrap();
4561 assert_eq!(back.len(), 2);
4562 back[0].to_data().validate_full().unwrap();
4563 assert_eq!(&back[0], &first);
4564 back[1].to_data().validate_full().unwrap();
4565 assert_eq!(&back[1], &second);
4566 }
4567
4568 #[test]
4569 fn test_single_map() {
4570 let mut builder = MapBuilder::new(None, StringBuilder::new(), Int32Builder::new());
4571 builder.keys().append_value("hello");
4573 builder.values().append_value(1);
4574 builder.keys().append_value("world");
4575 builder.values().append_value(2);
4576 builder.append(true).unwrap();
4577
4578 builder.keys().append_value("foo");
4580 builder.values().append_value(3);
4581 builder.append(true).unwrap();
4582
4583 builder.append(true).unwrap();
4585
4586 builder.keys().append_value("masked_key");
4588 builder.values().append_value(999);
4589 builder.append(false).unwrap();
4590
4591 builder.append(false).unwrap();
4593
4594 builder.keys().append_value("bar");
4596 builder.values().append_null();
4597 builder.append(true).unwrap();
4598
4599 builder.keys().append_value("other_masked");
4601 builder.values().append_value(0);
4602 builder.append(false).unwrap();
4603
4604 builder.keys().append_value("a");
4606 builder.values().append_value(10);
4607 builder.keys().append_value("b");
4608 builder.values().append_value(20);
4609 builder.keys().append_value("c");
4610 builder.values().append_value(30);
4611 builder.append(true).unwrap();
4612
4613 let map = Arc::new(builder.finish()) as ArrayRef;
4614 let d = map.data_type().clone();
4615
4616 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4617
4618 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
4619
4620 assert_eq!(rows.row(3), rows.row(4));
4622 assert_eq!(rows.row(4), rows.row(6));
4623
4624 let back = converter.convert_rows(&rows).unwrap();
4625 assert_eq!(back.len(), 1);
4626 back[0].to_data().validate_full().unwrap();
4627 assert_eq!(&back[0], &map);
4628
4629 let sliced_map = map.slice(1, map.len() - 2);
4630 let rows_on_sliced = converter
4631 .convert_columns(&[Arc::clone(&sliced_map)])
4632 .unwrap();
4633
4634 let back = converter.convert_rows(&rows_on_sliced).unwrap();
4635 assert_eq!(back.len(), 1);
4636 back[0].to_data().validate_full().unwrap();
4637 assert_eq!(&back[0], &sliced_map);
4638 }
4639
4640 #[test]
4641 fn two_maps_with_different_keys_order_should_sort_by_entry_order() {
4642 let map_1: ArrayRef =
4643 Arc::new(MapArray::from_vec_of_maps::<StringArray, Int32Array, _, _>(
4644 vec![Some(vec![("hello", Some(1)), ("world", Some(2))])],
4645 false,
4646 ));
4647 let map_2: ArrayRef =
4649 Arc::new(MapArray::from_vec_of_maps::<StringArray, Int32Array, _, _>(
4650 vec![Some(vec![("world", Some(2)), ("hello", Some(1))])],
4651 false,
4652 ));
4653
4654 let converter = RowConverter::new(vec![SortField::new(map_1.data_type().clone())]).unwrap();
4655
4656 let map_1_rows = converter.convert_columns(&[Arc::clone(&map_1)]).unwrap();
4657 let map_2_rows = converter.convert_columns(&[Arc::clone(&map_2)]).unwrap();
4658
4659 assert_ne!(map_1_rows.row(0), map_2_rows.row(0));
4660 assert!(map_1_rows.row(0) < map_2_rows.row(0));
4661
4662 let back_1 = converter.convert_rows(&map_1_rows).unwrap();
4663 let back_2 = converter.convert_rows(&map_2_rows).unwrap();
4664 assert_eq!(&back_1[0], &map_1);
4665 assert_eq!(&back_2[0], &map_2);
4666 }
4667
4668 #[test]
4669 fn test_nested_map() {
4670 let mut builder = MapBuilder::new(
4672 None,
4673 StringBuilder::new(),
4674 MapBuilder::new(None, StringBuilder::new(), Int32Builder::new()),
4675 );
4676
4677 builder.keys().append_value("outer1");
4679 builder.values().keys().append_value("inner_a");
4680 builder.values().values().append_value(1);
4681 builder.values().keys().append_value("inner_b");
4682 builder.values().values().append_value(2);
4683 builder.values().append(true).unwrap();
4684 builder.keys().append_value("outer2");
4685 builder.values().keys().append_value("inner_c");
4686 builder.values().values().append_value(3);
4687 builder.values().append(true).unwrap();
4688 builder.append(true).unwrap();
4689
4690 builder.keys().append_value("x");
4692 builder.values().append(true).unwrap();
4693 builder.append(true).unwrap();
4694
4695 builder.keys().append_value("y");
4697 builder.values().keys().append_value("masked"); builder.values().values().append_value(0); builder.values().append(false).unwrap();
4700 builder.append(true).unwrap();
4701
4702 builder.keys().append_value("y");
4704 builder.values().append(false).unwrap(); builder.append(true).unwrap();
4706
4707 builder.keys().append_value("masked_outer"); builder.values().keys().append_value("masked_inner"); builder.values().values().append_value(0); builder.values().append(true).unwrap(); builder.append(false).unwrap();
4713
4714 builder.keys().append_value("masked_outer"); builder.values().append(false).unwrap(); builder.append(false).unwrap();
4718
4719 builder.append(false).unwrap(); builder.append(true).unwrap();
4724
4725 let map = Arc::new(builder.finish()) as ArrayRef;
4726 let d = map.data_type().clone();
4727
4728 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4729
4730 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
4731
4732 let back = converter.convert_rows(&rows).unwrap();
4733 assert_eq!(back.len(), 1);
4734 back[0].to_data().validate_full().unwrap();
4735 assert_eq!(&back[0], &map);
4736
4737 let sliced_map = map.slice(1, 3);
4738 let rows_on_sliced = converter
4739 .convert_columns(&[Arc::clone(&sliced_map)])
4740 .unwrap();
4741
4742 let back = converter.convert_rows(&rows_on_sliced).unwrap();
4743 assert_eq!(back.len(), 1);
4744 back[0].to_data().validate_full().unwrap();
4745 assert_eq!(&back[0], &sliced_map);
4746 }
4747
4748 #[test]
4749 fn test_single_map_with_non_nullable_values() {
4750 let value_field = Arc::new(Field::new(
4752 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
4753 DataType::Int32,
4754 false,
4755 ));
4756 let mut builder = MapBuilder::new(None, StringBuilder::new(), Int32Builder::new())
4757 .with_values_field(value_field);
4758 builder.keys().append_value("a");
4760 builder.values().append_value(1);
4761 builder.keys().append_value("b");
4762 builder.values().append_value(2);
4763 builder.append(true).unwrap();
4764 builder.append(false).unwrap();
4766 builder.keys().append_value("c");
4768 builder.values().append_value(3);
4769 builder.append(true).unwrap();
4770 builder.append(true).unwrap();
4772 builder.keys().append_value("masked"); builder.values().append_value(0); builder.append(false).unwrap();
4776
4777 let map = Arc::new(builder.finish()) as ArrayRef;
4778 let d = map.data_type().clone();
4779
4780 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4781
4782 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
4783
4784 let back = converter.convert_rows(&rows).unwrap();
4785 assert_eq!(back.len(), 1);
4786 back[0].to_data().validate_full().unwrap();
4787 assert_eq!(&back[0], &map);
4788 }
4789
4790 #[test]
4791 fn test_single_map_with_non_nullable_map_but_with_nullable_values() {
4792 let value_field = Arc::new(Field::new(
4794 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
4795 DataType::Int32,
4796 true,
4797 ));
4798 let mut builder = MapBuilder::new(None, StringBuilder::new(), Int32Builder::new())
4799 .with_values_field(value_field);
4800
4801 builder.keys().append_value("a");
4803 builder.values().append_value(1);
4804 builder.keys().append_value("b");
4805 builder.values().append_null();
4806 builder.append(true).unwrap();
4807 builder.keys().append_value("c");
4809 builder.values().append_null();
4810 builder.keys().append_value("d");
4811 builder.values().append_null();
4812 builder.append(true).unwrap();
4813 builder.append(true).unwrap();
4815 builder.keys().append_value("e");
4817 builder.values().append_value(5);
4818 builder.append(true).unwrap();
4819
4820 let map = Arc::new(builder.finish()) as ArrayRef;
4821 let d = map.data_type().clone();
4822
4823 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4824
4825 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
4826
4827 let back = converter.convert_rows(&rows).unwrap();
4828 assert_eq!(back.len(), 1);
4829 back[0].to_data().validate_full().unwrap();
4830 assert_eq!(&back[0], &map);
4831 }
4832
4833 #[test]
4834 fn test_map_all_nulls() {
4835 let mut builder = MapBuilder::new(None, StringBuilder::new(), Int32Builder::new());
4836 builder.keys().append_value("m1"); builder.values().append_value(1); builder.append(false).unwrap();
4840 builder.keys().append_value("m2"); builder.values().append_value(2); builder.append(false).unwrap();
4843
4844 builder.append(false).unwrap(); builder.keys().append_value("m3"); builder.values().append_value(3); builder.append(false).unwrap();
4849
4850 let map = Arc::new(builder.finish()) as ArrayRef;
4851 let d = map.data_type().clone();
4852
4853 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4854
4855 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
4856
4857 rows.iter().for_each(|row| assert_eq!(row, rows.row(0)));
4859
4860 let back = converter.convert_rows(&rows).unwrap();
4861 assert_eq!(back.len(), 1);
4862 back[0].to_data().validate_full().unwrap();
4863 assert_eq!(&back[0], &map);
4864 }
4865
4866 #[test]
4867 fn test_map_all_empty() {
4868 let mut builder = MapBuilder::new(None, StringBuilder::new(), Int32Builder::new());
4869 builder.append(true).unwrap();
4871 builder.append(true).unwrap();
4872 builder.append(true).unwrap();
4873
4874 let map = Arc::new(builder.finish()) as ArrayRef;
4875 let d = map.data_type().clone();
4876
4877 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4878
4879 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
4880
4881 rows.iter().for_each(|row| assert_eq!(row, rows.row(0)));
4883
4884 let back = converter.convert_rows(&rows).unwrap();
4885 assert_eq!(back.len(), 1);
4886 back[0].to_data().validate_full().unwrap();
4887 assert_eq!(&back[0], &map);
4888 }
4889
4890 #[test]
4891 fn test_map_empty_array() {
4892 let builder = MapBuilder::new(None, StringBuilder::new(), Int32Builder::new());
4894 let map = Arc::new(builder.finish_cloned()) as ArrayRef;
4895 let d = map.data_type().clone();
4896
4897 let converter = RowConverter::new(vec![SortField::new(d.clone())]).unwrap();
4898
4899 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
4900
4901 let back = converter.convert_rows(&rows).unwrap();
4902 assert_eq!(back.len(), 1);
4903 back[0].to_data().validate_full().unwrap();
4904 assert_eq!(&back[0], &map);
4905 }
4906
4907 fn generate_primitive_array<K>(
4908 rng: &mut StdRng,
4909 len: usize,
4910 valid_percent: f64,
4911 ) -> PrimitiveArray<K>
4912 where
4913 K: ArrowPrimitiveType,
4914 StandardUniform: Distribution<K::Native>,
4915 {
4916 (0..len)
4917 .map(|_| rng.random_bool(valid_percent).then(|| rng.random()))
4918 .collect()
4919 }
4920
4921 fn generate_all_unique_primitive_array<K>(rng: &mut StdRng, len: usize) -> PrimitiveArray<K>
4922 where
4923 K: ArrowPrimitiveType,
4924 K::Native: Hash + Eq,
4925 StandardUniform: Distribution<K::Native>,
4926 {
4927 let possible_number_of_values = 2i32.saturating_pow(size_of::<K::Native>() as u32 * 8);
4928 assert!(
4929 len <= possible_number_of_values as usize,
4930 "len {len} is larger than the number of possible values {possible_number_of_values}"
4931 );
4932
4933 let mut seen = std::collections::HashSet::new();
4934 (0..len)
4935 .map(|_| {
4936 let mut value;
4937 loop {
4938 value = rng.random();
4939
4940 if seen.insert(value) {
4941 break;
4942 }
4943 }
4944
4945 Some(value)
4946 })
4947 .collect()
4948 }
4949
4950 fn generate_boolean_array(rng: &mut StdRng, len: usize, valid_percent: f64) -> BooleanArray {
4951 (0..len)
4952 .map(|_| rng.random_bool(valid_percent).then(|| rng.random_bool(0.5)))
4953 .collect()
4954 }
4955
4956 fn generate_strings<O: OffsetSizeTrait>(
4957 rng: &mut StdRng,
4958 len: usize,
4959 valid_percent: f64,
4960 ) -> GenericStringArray<O> {
4961 (0..len)
4962 .map(|_| {
4963 rng.random_bool(valid_percent).then(|| {
4964 let len = rng.random_range(0..100);
4965 let bytes = (0..len).map(|_| rng.random_range(0..128)).collect();
4966 String::from_utf8(bytes).unwrap()
4967 })
4968 })
4969 .collect()
4970 }
4971
4972 fn generate_string_view(rng: &mut StdRng, len: usize, valid_percent: f64) -> StringViewArray {
4973 (0..len)
4974 .map(|_| {
4975 rng.random_bool(valid_percent).then(|| {
4976 let len = rng.random_range(0..100);
4977 let bytes = (0..len).map(|_| rng.random_range(0..128)).collect();
4978 String::from_utf8(bytes).unwrap()
4979 })
4980 })
4981 .collect()
4982 }
4983
4984 fn generate_byte_view(rng: &mut StdRng, len: usize, valid_percent: f64) -> BinaryViewArray {
4985 (0..len)
4986 .map(|_| {
4987 rng.random_bool(valid_percent).then(|| {
4988 let len = rng.random_range(0..100);
4989 let bytes: Vec<_> = (0..len).map(|_| rng.random_range(0..128)).collect();
4990 bytes
4991 })
4992 })
4993 .collect()
4994 }
4995
4996 fn generate_fixed_stringview_column(len: usize) -> StringViewArray {
4997 let edge_cases = vec![
4998 Some("bar".to_string()),
4999 Some("bar\0".to_string()),
5000 Some("LongerThan12Bytes".to_string()),
5001 Some("LongerThan12Bytez".to_string()),
5002 Some("LongerThan12Bytes\0".to_string()),
5003 Some("LongerThan12Byt".to_string()),
5004 Some("backend one".to_string()),
5005 Some("backend two".to_string()),
5006 Some("a".repeat(257)),
5007 Some("a".repeat(300)),
5008 ];
5009
5010 let mut values = Vec::with_capacity(len);
5012 for i in 0..len {
5013 values.push(
5014 edge_cases
5015 .get(i % edge_cases.len())
5016 .cloned()
5017 .unwrap_or(None),
5018 );
5019 }
5020
5021 StringViewArray::from(values)
5022 }
5023
5024 fn generate_dictionary<K>(
5025 rng: &mut StdRng,
5026 values: ArrayRef,
5027 len: usize,
5028 valid_percent: f64,
5029 ) -> DictionaryArray<K>
5030 where
5031 K: ArrowDictionaryKeyType,
5032 K::Native: SampleUniform,
5033 {
5034 let min_key = K::Native::from_usize(0).unwrap();
5035 let max_key = K::Native::from_usize(values.len()).unwrap();
5036 let keys: PrimitiveArray<K> = (0..len)
5037 .map(|_| {
5038 rng.random_bool(valid_percent)
5039 .then(|| rng.random_range(min_key..max_key))
5040 })
5041 .collect();
5042
5043 let data_type =
5044 DataType::Dictionary(Box::new(K::DATA_TYPE), Box::new(values.data_type().clone()));
5045
5046 let data = keys
5047 .into_data()
5048 .into_builder()
5049 .data_type(data_type)
5050 .add_child_data(values.to_data())
5051 .build()
5052 .unwrap();
5053
5054 DictionaryArray::from(data)
5055 }
5056
5057 fn generate_fixed_size_binary(
5058 rng: &mut StdRng,
5059 len: usize,
5060 valid_percent: f64,
5061 ) -> FixedSizeBinaryArray {
5062 let width = rng.random_range(0..20);
5063 let mut builder = FixedSizeBinaryBuilder::new(width);
5064
5065 let mut b = vec![0; width as usize];
5066 for _ in 0..len {
5067 match rng.random_bool(valid_percent) {
5068 true => {
5069 b.iter_mut().for_each(|x| *x = rng.random());
5070 builder.append_value(&b).unwrap();
5071 }
5072 false => builder.append_null(),
5073 }
5074 }
5075
5076 builder.finish()
5077 }
5078
5079 fn generate_struct(rng: &mut StdRng, len: usize, valid_percent: f64) -> StructArray {
5080 let nulls = NullBuffer::from_iter((0..len).map(|_| rng.random_bool(valid_percent)));
5081 let a = generate_primitive_array::<Int32Type>(rng, len, valid_percent);
5082 let b = generate_strings::<i32>(rng, len, valid_percent);
5083 let fields = Fields::from(vec![
5084 Field::new("a", DataType::Int32, true),
5085 Field::new("b", DataType::Utf8, true),
5086 ]);
5087 let values = vec![Arc::new(a) as _, Arc::new(b) as _];
5088 StructArray::new(fields, values, Some(nulls))
5089 }
5090
5091 fn generate_list<F>(rng: &mut StdRng, len: usize, valid_percent: f64, values: F) -> ListArray
5092 where
5093 F: FnOnce(&mut StdRng, usize) -> ArrayRef,
5094 {
5095 let offsets = OffsetBuffer::<i32>::from_lengths((0..len).map(|_| rng.random_range(0..10)));
5096 let values_len = offsets.last().as_usize();
5097 let values = values(rng, values_len);
5098 let nulls = NullBuffer::from_iter((0..len).map(|_| rng.random_bool(valid_percent)));
5099 let field = Arc::new(Field::new_list_field(values.data_type().clone(), true));
5100 ListArray::new(field, offsets, values, Some(nulls))
5101 }
5102
5103 fn generate_list_view<F>(
5104 rng: &mut StdRng,
5105 len: usize,
5106 valid_percent: f64,
5107 values: F,
5108 ) -> ListViewArray
5109 where
5110 F: FnOnce(&mut StdRng, usize) -> ArrayRef,
5111 {
5112 let sizes: Vec<i32> = (0..len).map(|_| rng.random_range(0..10)).collect();
5114 let values_len: usize = sizes.iter().map(|s| *s as usize).sum::<usize>().max(1);
5115 let values = values(rng, values_len);
5116
5117 let offsets: Vec<i32> = sizes
5119 .iter()
5120 .map(|&size| {
5121 if size == 0 {
5122 0
5123 } else {
5124 rng.random_range(0..=(values_len as i32 - size))
5125 }
5126 })
5127 .collect();
5128
5129 let nulls = NullBuffer::from_iter((0..len).map(|_| rng.random_bool(valid_percent)));
5130 let field = Arc::new(Field::new_list_field(values.data_type().clone(), true));
5131 ListViewArray::new(
5132 field,
5133 ScalarBuffer::from(offsets),
5134 ScalarBuffer::from(sizes),
5135 values,
5136 Some(nulls),
5137 )
5138 }
5139
5140 fn generate_map<KeysFn, ValuesFn>(
5141 rng: &mut StdRng,
5142 len: usize,
5143 valid_percent: f64,
5144 gen_keys: KeysFn,
5145 gen_values: ValuesFn,
5146 ) -> MapArray
5147 where
5148 KeysFn: FnOnce(&mut StdRng, usize) -> ArrayRef,
5149 ValuesFn: FnOnce(&mut StdRng, usize) -> ArrayRef,
5150 {
5151 let offsets = OffsetBuffer::<i32>::from_lengths((0..len).map(|_| rng.random_range(0..10)));
5152 let entries_len = offsets.last().as_usize();
5153 let keys = gen_keys(rng, entries_len);
5154 let values = gen_values(rng, entries_len);
5155 let nulls = NullBuffer::from_iter((0..len).map(|_| rng.random_bool(valid_percent)));
5156 let field = Arc::new(Field::new_map(
5157 "",
5158 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
5159 Field::new(
5160 Field::MAP_KEY_FIELD_DEFAULT_NAME,
5161 keys.data_type().clone(),
5162 false,
5163 ),
5164 Field::new(
5165 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
5166 values.data_type().clone(),
5167 true,
5168 ),
5169 false,
5170 true,
5171 ));
5172 let DataType::Map(struct_field, _) = field.data_type() else {
5173 unreachable!();
5174 };
5175
5176 let DataType::Struct(fields) = struct_field.data_type() else {
5177 unreachable!();
5178 };
5179
5180 let entries = StructArray::new(fields.clone(), vec![keys, values], None);
5181
5182 let map_array = MapArray::new(struct_field.clone(), offsets, entries, Some(nulls), false);
5183
5184 assert_valid_map(&map_array);
5185
5186 map_array
5187 }
5188
5189 fn assert_valid_map(array: &MapArray) {
5199 let keys_arrow_row_converter =
5200 RowConverter::new(vec![SortField::new(array.key_type().clone())]).unwrap();
5201
5202 array.iter().enumerate().filter_map(|(index, entry)| entry.map(|entry| (index, Arc::clone(entry.column(0))))).for_each(|(entry_index, keys)| {
5203 let keys_as_rows = keys_arrow_row_converter.convert_columns(&[Arc::clone(&keys)]).expect("should be able to convert keys");
5204
5205 for i in 0..keys_as_rows.num_rows() {
5206 for j in (i + 1)..keys_as_rows.num_rows() {
5207 if keys_as_rows.row(i) == keys_as_rows.row(j) {
5208 let key_i = keys.slice(i, 1);
5209 let key_j = keys.slice(j, 1);
5210
5211 assert_ne!(keys_as_rows.row(i), keys_as_rows.row(j), "map keys should be unique, but key {i} and key {j} are equal in entry {entry_index}. key {i} value is {key_i:?} and key {j} value is {key_j:?}");
5212 }
5213 }
5214 }
5215 })
5216 }
5217
5218 fn generate_nulls(rng: &mut StdRng, len: usize) -> Option<NullBuffer> {
5219 Some(NullBuffer::from_iter(
5220 (0..len).map(|_| rng.random_bool(0.8)),
5221 ))
5222 }
5223
5224 fn change_underlying_null_values_for_primitive<T: ArrowPrimitiveType>(
5225 array: &PrimitiveArray<T>,
5226 ) -> PrimitiveArray<T> {
5227 let (dt, values, nulls) = array.clone().into_parts();
5228
5229 let new_values = ScalarBuffer::<T::Native>::from_iter(
5230 values
5231 .iter()
5232 .zip(nulls.as_ref().unwrap().iter())
5233 .map(|(val, is_valid)| {
5234 if is_valid {
5235 *val
5236 } else {
5237 val.add_wrapping(T::Native::usize_as(1))
5238 }
5239 }),
5240 );
5241
5242 PrimitiveArray::new(new_values, nulls).with_data_type(dt)
5243 }
5244
5245 fn change_underline_null_values_for_byte_array<T: ByteArrayType>(
5246 array: &GenericByteArray<T>,
5247 ) -> GenericByteArray<T> {
5248 let (offsets, values, nulls) = array.clone().into_parts();
5249
5250 let new_offsets = OffsetBuffer::<T::Offset>::from_lengths(
5251 offsets
5252 .lengths()
5253 .zip(nulls.as_ref().unwrap().iter())
5254 .map(|(len, is_valid)| if is_valid { len } else { len + 1 }),
5255 );
5256
5257 let mut new_bytes = Vec::<u8>::with_capacity(new_offsets[new_offsets.len() - 1].as_usize());
5258
5259 offsets
5260 .windows(2)
5261 .zip(nulls.as_ref().unwrap().iter())
5262 .for_each(|(start_and_end, is_valid)| {
5263 let start = start_and_end[0].as_usize();
5264 let end = start_and_end[1].as_usize();
5265 new_bytes.extend_from_slice(&values.as_slice()[start..end]);
5266
5267 if !is_valid {
5269 new_bytes.push(b'c');
5270 }
5271 });
5272
5273 GenericByteArray::<T>::new(new_offsets, Buffer::from_vec(new_bytes), nulls)
5274 }
5275
5276 fn change_underline_null_values_for_list_array<O: OffsetSizeTrait>(
5277 array: &GenericListArray<O>,
5278 ) -> GenericListArray<O> {
5279 let (field, offsets, values, nulls) = array.clone().into_parts();
5280
5281 let (new_values, new_offsets) = {
5282 let concat_values = offsets
5283 .windows(2)
5284 .zip(nulls.as_ref().unwrap().iter())
5285 .map(|(start_and_end, is_valid)| {
5286 let start = start_and_end[0].as_usize();
5287 let end = start_and_end[1].as_usize();
5288 if is_valid {
5289 return (start, end - start);
5290 }
5291
5292 if end == values.len() {
5294 (start, (end - start).saturating_sub(1))
5295 } else {
5296 (start, end - start + 1)
5297 }
5298 })
5299 .map(|(start, length)| values.slice(start, length))
5300 .collect::<Vec<_>>();
5301
5302 let new_offsets =
5303 OffsetBuffer::<O>::from_lengths(concat_values.iter().map(|s| s.len()));
5304
5305 let new_values = {
5306 let values = concat_values.iter().map(|a| a.as_ref()).collect::<Vec<_>>();
5307 arrow_select::concat::concat(&values).expect("should be able to concat")
5308 };
5309
5310 (new_values, new_offsets)
5311 };
5312
5313 GenericListArray::<O>::new(field, new_offsets, new_values, nulls)
5314 }
5315
5316 fn change_underline_null_values_for_map_array(array: &MapArray) -> MapArray {
5317 let (field, offsets, entries, nulls, ordered) = array.clone().into_parts();
5318 assert!(
5319 !ordered,
5320 "can't replace underlying null values for ordered map array as this can violate the ordering"
5321 );
5322
5323 let (new_entries, new_offsets) = {
5324 let concat_values = offsets
5325 .windows(2)
5326 .zip(nulls.as_ref().unwrap().iter())
5327 .map(|(start_and_end, is_valid)| {
5328 let start = start_and_end[0].as_usize();
5329 let end = start_and_end[1].as_usize();
5330 if is_valid {
5331 return (start, end - start);
5332 }
5333
5334 if end == entries.len() {
5336 (start, (end - start).saturating_sub(1))
5337 } else {
5338 (start, end - start + 1)
5340 }
5341 })
5342 .map(|(start, length)| entries.slice(start, length))
5343 .collect::<Vec<_>>();
5344
5345 let new_offsets = OffsetBuffer::from_lengths(concat_values.iter().map(|s| s.len()));
5346
5347 let new_values = {
5348 let values = concat_values
5349 .iter()
5350 .map(|a| a as &dyn Array)
5351 .collect::<Vec<_>>();
5352 arrow_select::concat::concat(&values).expect("should be able to concat")
5353 };
5354
5355 (new_values.as_struct().clone(), new_offsets)
5356 };
5357
5358 let new_map = MapArray::new(field, new_offsets, new_entries, nulls, ordered);
5359
5360 assert_valid_map(&new_map);
5361
5362 new_map
5363 }
5364
5365 fn change_underline_null_values(array: &ArrayRef) -> ArrayRef {
5366 if array.null_count() == 0 {
5367 return Arc::clone(array);
5368 }
5369
5370 downcast_primitive_array!(
5371 array => {
5372 let output = change_underlying_null_values_for_primitive(array);
5373
5374 Arc::new(output)
5375 }
5376
5377 DataType::Utf8 => {
5378 Arc::new(change_underline_null_values_for_byte_array(array.as_string::<i32>()))
5379 }
5380 DataType::LargeUtf8 => {
5381 Arc::new(change_underline_null_values_for_byte_array(array.as_string::<i64>()))
5382 }
5383 DataType::Binary => {
5384 Arc::new(change_underline_null_values_for_byte_array(array.as_binary::<i32>()))
5385 }
5386 DataType::LargeBinary => {
5387 Arc::new(change_underline_null_values_for_byte_array(array.as_binary::<i64>()))
5388 }
5389 DataType::List(_) => {
5390 Arc::new(change_underline_null_values_for_list_array(array.as_list::<i32>()))
5391 }
5392 DataType::LargeList(_) => {
5393 Arc::new(change_underline_null_values_for_list_array(array.as_list::<i64>()))
5394 }
5395 DataType::Map(_, _) => {
5396 Arc::new(change_underline_null_values_for_map_array(array.as_map()))
5397 }
5398 _ => {
5399 Arc::clone(array)
5400 }
5401 )
5402 }
5403
5404 fn generate_column(rng: &mut StdRng, len: usize) -> ArrayRef {
5405 match rng.random_range(0..24) {
5406 0 => Arc::new(generate_primitive_array::<Int32Type>(rng, len, 0.8)),
5407 1 => Arc::new(generate_primitive_array::<UInt32Type>(rng, len, 0.8)),
5408 2 => Arc::new(generate_primitive_array::<Int64Type>(rng, len, 0.8)),
5409 3 => Arc::new(generate_primitive_array::<UInt64Type>(rng, len, 0.8)),
5410 4 => Arc::new(generate_primitive_array::<Float32Type>(rng, len, 0.8)),
5411 5 => Arc::new(generate_primitive_array::<Float64Type>(rng, len, 0.8)),
5412 6 => Arc::new(generate_strings::<i32>(rng, len, 0.8)),
5413 7 => {
5414 let dict_values_len = rng.random_range(1..len);
5415 let strings = Arc::new(generate_strings::<i32>(rng, dict_values_len, 1.0));
5417 Arc::new(generate_dictionary::<Int64Type>(rng, strings, len, 0.8))
5418 }
5419 8 => {
5420 let dict_values_len = rng.random_range(1..len);
5421 let values = Arc::new(generate_primitive_array::<Int64Type>(
5423 rng,
5424 dict_values_len,
5425 1.0,
5426 ));
5427 Arc::new(generate_dictionary::<Int64Type>(rng, values, len, 0.8))
5428 }
5429 9 => Arc::new(generate_fixed_size_binary(rng, len, 0.8)),
5430 10 => Arc::new(generate_struct(rng, len, 0.8)),
5431 11 => Arc::new(generate_list(rng, len, 0.8, |rng, values_len| {
5432 Arc::new(generate_primitive_array::<Int64Type>(rng, values_len, 0.8))
5433 })),
5434 12 => Arc::new(generate_list(rng, len, 0.8, |rng, values_len| {
5435 Arc::new(generate_strings::<i32>(rng, values_len, 0.8))
5436 })),
5437 13 => Arc::new(generate_list(rng, len, 0.8, |rng, values_len| {
5438 Arc::new(generate_struct(rng, values_len, 0.8))
5439 })),
5440 14 => Arc::new(generate_string_view(rng, len, 0.8)),
5441 15 => Arc::new(generate_byte_view(rng, len, 0.8)),
5442 16 => Arc::new(generate_fixed_stringview_column(len)),
5443 17 => Arc::new(
5444 generate_list(rng, len + 1000, 0.8, |rng, values_len| {
5445 Arc::new(generate_primitive_array::<Int64Type>(rng, values_len, 0.8))
5446 })
5447 .slice(500, len),
5448 ),
5449 18 => Arc::new(generate_boolean_array(rng, len, 0.8)),
5450 19 => Arc::new(generate_list_view(rng, len, 0.8, |rng, values_len| {
5451 Arc::new(generate_primitive_array::<Int64Type>(rng, values_len, 0.8))
5452 })),
5453 20 => Arc::new(generate_list_view(rng, len, 0.8, |rng, values_len| {
5454 Arc::new(generate_strings::<i32>(rng, values_len, 0.8))
5455 })),
5456 21 => Arc::new(generate_list_view(rng, len, 0.8, |rng, values_len| {
5457 Arc::new(generate_struct(rng, values_len, 0.8))
5458 })),
5459 22 => Arc::new(
5460 generate_list_view(rng, len + 1000, 0.8, |rng, values_len| {
5461 Arc::new(generate_primitive_array::<Int64Type>(rng, values_len, 0.8))
5462 })
5463 .slice(500, len),
5464 ),
5465 23 => Arc::new(generate_map(
5466 rng,
5467 len,
5468 0.9,
5469 |rng, keys_len| {
5471 Arc::new(generate_all_unique_primitive_array::<Int64Type>(
5472 rng, keys_len,
5473 ))
5474 },
5475 |rng, values_len| Arc::new(generate_strings::<i32>(rng, values_len, 0.7)),
5476 )),
5477 _ => unreachable!(),
5478 }
5479 }
5480
5481 fn print_row(cols: &[SortColumn], row: usize) -> String {
5482 let t: Vec<_> = cols
5483 .iter()
5484 .map(|x| match x.values.is_valid(row) {
5485 true => {
5486 let opts = FormatOptions::default().with_null("NULL");
5487 let formatter = ArrayFormatter::try_new(x.values.as_ref(), &opts).unwrap();
5488 formatter.value(row).to_string()
5489 }
5490 false => "NULL".to_string(),
5491 })
5492 .collect();
5493 t.join(",")
5494 }
5495
5496 fn print_col_types(cols: &[SortColumn]) -> String {
5497 let t: Vec<_> = cols
5498 .iter()
5499 .map(|x| x.values.data_type().to_string())
5500 .collect();
5501 t.join(",")
5502 }
5503
5504 #[derive(Debug, PartialEq)]
5505 enum Nulls {
5506 AsIs,
5508
5509 Different,
5511
5512 None,
5514 }
5515
5516 #[test]
5517 #[cfg_attr(miri, ignore)] fn fuzz_test() {
5519 let mut rng = StdRng::seed_from_u64(42);
5520 for _ in 0..100 {
5521 for null_behavior in [Nulls::AsIs, Nulls::Different, Nulls::None] {
5522 let num_columns = rng.random_range(1..5);
5523 let len = rng.random_range(5..100);
5524 let mut arrays: Vec<_> = (0..num_columns)
5525 .map(|_| generate_column(&mut rng, len))
5526 .collect();
5527
5528 match null_behavior {
5529 Nulls::AsIs => {
5530 }
5532 Nulls::Different => {
5533 arrays = arrays
5535 .into_iter()
5536 .map(|a| replace_array_nulls(a, generate_nulls(&mut rng, len)))
5537 .collect()
5538 }
5539 Nulls::None => {
5540 arrays = arrays
5542 .into_iter()
5543 .map(|a| replace_array_nulls(a, None))
5544 .collect()
5545 }
5546 }
5547
5548 let options: Vec<_> = (0..num_columns)
5549 .map(|_| SortOptions {
5550 descending: rng.random_bool(0.5),
5551 nulls_first: rng.random_bool(0.5),
5552 })
5553 .collect();
5554
5555 let sort_columns: Vec<_> = options
5556 .iter()
5557 .zip(&arrays)
5558 .map(|(o, c)| SortColumn {
5559 values: Arc::clone(c),
5560 options: Some(*o),
5561 })
5562 .collect();
5563
5564 let comparator = LexicographicalComparator::try_new(&sort_columns).unwrap();
5565
5566 let columns: Vec<SortField> = options
5567 .into_iter()
5568 .zip(&arrays)
5569 .map(|(o, a)| SortField::new_with_options(a.data_type().clone(), o))
5570 .collect();
5571
5572 let converter = RowConverter::new(columns).unwrap();
5573 let rows = converter.convert_columns(&arrays).unwrap();
5574
5575 if !matches!(null_behavior, Nulls::None) {
5578 assert_same_rows_when_changing_input_underlying_null_values(
5579 &arrays, &converter, &rows,
5580 );
5581 }
5582
5583 for i in 0..len {
5584 for j in 0..len {
5585 let row_i = rows.row(i);
5586 let row_j = rows.row(j);
5587 let row_cmp = row_i.cmp(&row_j);
5588 let lex_cmp = comparator.compare(i, j);
5589 assert_eq!(
5590 row_cmp,
5591 lex_cmp,
5592 "({:?} vs {:?}) vs ({:?} vs {:?}) for types {}",
5593 print_row(&sort_columns, i),
5594 print_row(&sort_columns, j),
5595 row_i,
5596 row_j,
5597 print_col_types(&sort_columns)
5598 );
5599 }
5600 }
5601
5602 {
5604 let mut rows_iter = rows.iter();
5605 let mut rows_lengths_iter = rows.lengths();
5606 for (index, row) in rows_iter.by_ref().enumerate() {
5607 let len = rows_lengths_iter
5608 .next()
5609 .expect("Reached end of length iterator while still have rows");
5610 assert_eq!(
5611 row.data.len(),
5612 len,
5613 "Row length mismatch: {} vs {}",
5614 row.data.len(),
5615 len
5616 );
5617 assert_eq!(
5618 len,
5619 rows.row_len(index),
5620 "Row length mismatch at index {}: {} vs {}",
5621 index,
5622 len,
5623 rows.row_len(index)
5624 );
5625 }
5626
5627 assert_eq!(
5628 rows_lengths_iter.next(),
5629 None,
5630 "Length iterator did not reach end"
5631 );
5632 }
5633
5634 let back = converter.convert_rows(&rows).unwrap();
5637 for (actual, expected) in back.iter().zip(&arrays) {
5638 actual.to_data().validate_full().unwrap();
5639 dictionary_eq(actual, expected)
5640 }
5641
5642 let rows = rows.try_into_binary().expect("reasonable size");
5645 let parser = converter.parser();
5646 let back = converter
5647 .convert_rows(rows.iter().map(|b| parser.parse(b.expect("valid bytes"))))
5648 .unwrap();
5649 for (actual, expected) in back.iter().zip(&arrays) {
5650 actual.to_data().validate_full().unwrap();
5651 dictionary_eq(actual, expected)
5652 }
5653
5654 let rows = converter.from_binary(rows);
5655 let back = converter.convert_rows(&rows).unwrap();
5656 for (actual, expected) in back.iter().zip(&arrays) {
5657 actual.to_data().validate_full().unwrap();
5658 dictionary_eq(actual, expected)
5659 }
5660 }
5661 }
5662 }
5663
5664 fn replace_array_nulls(array: ArrayRef, new_nulls: Option<NullBuffer>) -> ArrayRef {
5665 make_array(
5666 array
5667 .into_data()
5668 .into_builder()
5669 .nulls(new_nulls)
5671 .build()
5672 .unwrap(),
5673 )
5674 }
5675
5676 fn assert_same_rows_when_changing_input_underlying_null_values(
5677 arrays: &[ArrayRef],
5678 converter: &RowConverter,
5679 rows: &Rows,
5680 ) {
5681 let arrays_with_different_data_behind_nulls = arrays
5682 .iter()
5683 .map(|arr| change_underline_null_values(arr))
5684 .collect::<Vec<_>>();
5685
5686 if arrays
5688 .iter()
5689 .zip(arrays_with_different_data_behind_nulls.iter())
5690 .all(|(a, b)| Arc::ptr_eq(a, b))
5691 {
5692 return;
5693 }
5694
5695 let rows_with_different_nulls = converter
5696 .convert_columns(&arrays_with_different_data_behind_nulls)
5697 .unwrap();
5698
5699 assert_eq!(
5700 rows.iter().collect::<Vec<_>>(),
5701 rows_with_different_nulls.iter().collect::<Vec<_>>(),
5702 "Different underlying nulls should not output different rows"
5703 )
5704 }
5705
5706 #[test]
5707 fn test_clear() {
5708 let converter = RowConverter::new(vec![SortField::new(DataType::Int32)]).unwrap();
5709 let mut rows = converter.empty_rows(3, 128);
5710
5711 let first = Int32Array::from(vec![None, Some(2), Some(4)]);
5712 let second = Int32Array::from(vec![Some(2), None, Some(4)]);
5713 let arrays = [Arc::new(first) as ArrayRef, Arc::new(second) as ArrayRef];
5714
5715 for array in &arrays {
5716 rows.clear();
5717 converter
5718 .append(&mut rows, std::slice::from_ref(array))
5719 .unwrap();
5720 let back = converter.convert_rows(&rows).unwrap();
5721 assert_eq!(&back[0], array);
5722 }
5723
5724 let mut rows_expected = converter.empty_rows(3, 128);
5725 converter.append(&mut rows_expected, &arrays[1..]).unwrap();
5726
5727 for (i, (actual, expected)) in rows.iter().zip(rows_expected.iter()).enumerate() {
5728 assert_eq!(
5729 actual, expected,
5730 "For row {i}: expected {expected:?}, actual: {actual:?}",
5731 );
5732 }
5733 }
5734
5735 #[test]
5736 fn test_append_codec_dictionary_binary() {
5737 use DataType::*;
5738 let converter = RowConverter::new(vec![SortField::new(Dictionary(
5740 Box::new(Int32),
5741 Box::new(Binary),
5742 ))])
5743 .unwrap();
5744 let mut rows = converter.empty_rows(4, 128);
5745
5746 let keys = Int32Array::from_iter_values([0, 1, 2, 3]);
5747 let values = BinaryArray::from(vec![
5748 Some(b"a".as_slice()),
5749 Some(b"b"),
5750 Some(b"c"),
5751 Some(b"d"),
5752 ]);
5753 let dict_array = DictionaryArray::new(keys, Arc::new(values));
5754
5755 rows.clear();
5756 let array = Arc::new(dict_array) as ArrayRef;
5757 converter
5758 .append(&mut rows, std::slice::from_ref(&array))
5759 .unwrap();
5760 let back = converter.convert_rows(&rows).unwrap();
5761
5762 dictionary_eq(&back[0], &array);
5763 }
5764
5765 #[test]
5766 fn test_list_prefix() {
5767 let mut a = ListBuilder::new(Int8Builder::new());
5768 a.append_value([None]);
5769 a.append_value([None, None]);
5770 let a = a.finish();
5771
5772 let converter = RowConverter::new(vec![SortField::new(a.data_type().clone())]).unwrap();
5773 let rows = converter.convert_columns(&[Arc::new(a) as _]).unwrap();
5774 assert_eq!(rows.row(0).cmp(&rows.row(1)), Ordering::Less);
5775 }
5776
5777 #[test]
5778 fn test_utf8_validation_doesnt_affect_values_buffer_size() {
5779 fn assert_values_buffer_lens(col: ArrayRef) -> usize {
5780 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8View)]).unwrap();
5782
5783 let rows = converter.convert_columns(&[col]).unwrap();
5785 let converted = converter.convert_rows(&rows).unwrap();
5786 let unchecked_values_len = converted[0].as_string_view().data_buffers()[0].len();
5787
5788 let rows = rows.try_into_binary().expect("reasonable size");
5790 let parser = converter.parser();
5791 let converted = converter
5792 .convert_rows(rows.iter().map(|b| parser.parse(b.expect("valid bytes"))))
5793 .unwrap();
5794 let checked_values_len = converted[0].as_string_view().data_buffers()[0].len();
5795 assert_eq!(unchecked_values_len, checked_values_len);
5797 checked_values_len
5798 }
5799
5800 let col = Arc::new(StringViewArray::from_iter([
5802 Some("hello"), None, Some("short"), Some("tiny"), ])) as ArrayRef;
5807
5808 let values_len = assert_values_buffer_lens(col);
5809 assert_eq!(values_len, 0);
5811
5812 let col = Arc::new(StringViewArray::from_iter([
5814 Some("1234567890123"), Some("12345678901234"), ])) as ArrayRef;
5817
5818 let values_len = assert_values_buffer_lens(col);
5819 assert_eq!(values_len, 13 + 14);
5820
5821 let col = Arc::new(StringViewArray::from_iter([
5823 Some("tiny"), Some("thisisexact13"), None,
5826 Some("short"), ])) as ArrayRef;
5828
5829 let values_len = assert_values_buffer_lens(col);
5830 assert_eq!(values_len, 13);
5832 }
5833
5834 #[test]
5835 fn test_sparse_union() {
5836 let int_array = Int32Array::from(vec![Some(1), None, Some(3), None, Some(5)]);
5838 let str_array = StringArray::from(vec![None, Some("b"), None, Some("d"), None]);
5839
5840 let type_ids = vec![0, 1, 0, 1, 0].into();
5842
5843 let union_fields = [
5844 (0, Arc::new(Field::new("int", DataType::Int32, false))),
5845 (1, Arc::new(Field::new("str", DataType::Utf8, false))),
5846 ]
5847 .into_iter()
5848 .collect();
5849
5850 let union_array = UnionArray::try_new(
5851 union_fields,
5852 type_ids,
5853 None,
5854 vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)],
5855 )
5856 .unwrap();
5857
5858 let union_type = union_array.data_type().clone();
5859 let converter = RowConverter::new(vec![SortField::new(union_type)]).unwrap();
5860
5861 let rows = converter
5862 .convert_columns(&[Arc::new(union_array.clone())])
5863 .unwrap();
5864
5865 let back = converter.convert_rows(&rows).unwrap();
5867 let back_union = back[0].as_any().downcast_ref::<UnionArray>().unwrap();
5868
5869 assert_eq!(union_array.len(), back_union.len());
5870 for i in 0..union_array.len() {
5871 assert_eq!(union_array.type_id(i), back_union.type_id(i));
5872 }
5873 }
5874
5875 #[test]
5876 fn test_sparse_union_with_nulls() {
5877 let int_array = Int32Array::from(vec![Some(1), None, Some(3), None, Some(5)]);
5879 let str_array = StringArray::from(vec![None::<&str>; 5]);
5880
5881 let type_ids = vec![0, 1, 0, 1, 0].into();
5883
5884 let union_fields = [
5885 (0, Arc::new(Field::new("int", DataType::Int32, true))),
5886 (1, Arc::new(Field::new("str", DataType::Utf8, true))),
5887 ]
5888 .into_iter()
5889 .collect();
5890
5891 let union_array = UnionArray::try_new(
5892 union_fields,
5893 type_ids,
5894 None,
5895 vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)],
5896 )
5897 .unwrap();
5898
5899 let union_type = union_array.data_type().clone();
5900 let converter = RowConverter::new(vec![SortField::new(union_type)]).unwrap();
5901
5902 let rows = converter
5903 .convert_columns(&[Arc::new(union_array.clone())])
5904 .unwrap();
5905
5906 let back = converter.convert_rows(&rows).unwrap();
5908 let back_union = back[0].as_any().downcast_ref::<UnionArray>().unwrap();
5909
5910 assert_eq!(union_array.len(), back_union.len());
5911 for i in 0..union_array.len() {
5912 let expected_null = union_array.is_null(i);
5913 let actual_null = back_union.is_null(i);
5914 assert_eq!(expected_null, actual_null, "Null mismatch at index {i}");
5915 if !expected_null {
5916 assert_eq!(union_array.type_id(i), back_union.type_id(i));
5917 }
5918 }
5919 }
5920
5921 #[test]
5922 fn test_dense_union() {
5923 let int_array = Int32Array::from(vec![1, 3, 5]);
5925 let str_array = StringArray::from(vec!["a", "b"]);
5926
5927 let type_ids = vec![0, 1, 0, 1, 0].into();
5928
5929 let offsets = vec![0, 0, 1, 1, 2].into();
5931
5932 let union_fields = [
5933 (0, Arc::new(Field::new("int", DataType::Int32, false))),
5934 (1, Arc::new(Field::new("str", DataType::Utf8, false))),
5935 ]
5936 .into_iter()
5937 .collect();
5938
5939 let union_array = UnionArray::try_new(
5940 union_fields,
5941 type_ids,
5942 Some(offsets), vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)],
5944 )
5945 .unwrap();
5946
5947 let union_type = union_array.data_type().clone();
5948 let converter = RowConverter::new(vec![SortField::new(union_type)]).unwrap();
5949
5950 let rows = converter
5951 .convert_columns(&[Arc::new(union_array.clone())])
5952 .unwrap();
5953
5954 let back = converter.convert_rows(&rows).unwrap();
5956 let back_union = back[0].as_any().downcast_ref::<UnionArray>().unwrap();
5957
5958 assert_eq!(union_array.len(), back_union.len());
5959 for i in 0..union_array.len() {
5960 assert_eq!(union_array.type_id(i), back_union.type_id(i));
5961 }
5962 }
5963
5964 #[test]
5965 fn test_dense_union_type_ids_not_below_field_count() {
5966 let union_fields = [
5968 (2, Arc::new(Field::new("int", DataType::Int32, false))),
5969 (7, Arc::new(Field::new("str", DataType::Utf8, false))),
5970 ]
5971 .into_iter()
5972 .collect();
5973
5974 let union_array: ArrayRef = Arc::new(
5975 UnionArray::try_new(
5976 union_fields,
5977 vec![2, 7, 2, 7].into(),
5978 Some(vec![0, 0, 1, 1].into()),
5979 vec![
5980 Arc::new(Int32Array::from(vec![1, 3])) as ArrayRef,
5981 Arc::new(StringArray::from(vec!["a", "b"])),
5982 ],
5983 )
5984 .unwrap(),
5985 );
5986
5987 let converter =
5988 RowConverter::new(vec![SortField::new(union_array.data_type().clone())]).unwrap();
5989 let rows = converter
5990 .convert_columns(std::slice::from_ref(&union_array))
5991 .unwrap();
5992 let back = converter.convert_rows(&rows).unwrap();
5993
5994 assert_eq!(back[0].to_data(), union_array.to_data());
5995 }
5996
5997 #[test]
5998 fn test_dense_union_with_nulls() {
5999 let int_array = Int32Array::from(vec![Some(1), None, Some(5)]);
6001 let str_array = StringArray::from(vec![Some("a"), None]);
6002
6003 let type_ids = vec![0, 1, 0, 1, 0].into();
6005 let offsets = vec![0, 0, 1, 1, 2].into();
6006
6007 let union_fields = [
6008 (0, Arc::new(Field::new("int", DataType::Int32, true))),
6009 (1, Arc::new(Field::new("str", DataType::Utf8, true))),
6010 ]
6011 .into_iter()
6012 .collect();
6013
6014 let union_array = UnionArray::try_new(
6015 union_fields,
6016 type_ids,
6017 Some(offsets),
6018 vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)],
6019 )
6020 .unwrap();
6021
6022 let union_type = union_array.data_type().clone();
6023 let converter = RowConverter::new(vec![SortField::new(union_type)]).unwrap();
6024
6025 let rows = converter
6026 .convert_columns(&[Arc::new(union_array.clone())])
6027 .unwrap();
6028
6029 let back = converter.convert_rows(&rows).unwrap();
6031 let back_union = back[0].as_any().downcast_ref::<UnionArray>().unwrap();
6032
6033 assert_eq!(union_array.len(), back_union.len());
6034 for i in 0..union_array.len() {
6035 let expected_null = union_array.is_null(i);
6036 let actual_null = back_union.is_null(i);
6037 assert_eq!(expected_null, actual_null, "Null mismatch at index {i}");
6038 if !expected_null {
6039 assert_eq!(union_array.type_id(i), back_union.type_id(i));
6040 }
6041 }
6042 }
6043
6044 #[test]
6045 fn test_union_ordering() {
6046 let int_array = Int32Array::from(vec![100, 5, 20]);
6047 let str_array = StringArray::from(vec!["z", "a"]);
6048
6049 let type_ids = vec![0, 1, 0, 1, 0].into();
6051 let offsets = vec![0, 0, 1, 1, 2].into();
6052
6053 let union_fields = [
6054 (0, Arc::new(Field::new("int", DataType::Int32, false))),
6055 (1, Arc::new(Field::new("str", DataType::Utf8, false))),
6056 ]
6057 .into_iter()
6058 .collect();
6059
6060 let union_array = UnionArray::try_new(
6061 union_fields,
6062 type_ids,
6063 Some(offsets),
6064 vec![Arc::new(int_array) as ArrayRef, Arc::new(str_array)],
6065 )
6066 .unwrap();
6067
6068 let union_type = union_array.data_type().clone();
6069 let converter = RowConverter::new(vec![SortField::new(union_type)]).unwrap();
6070
6071 let rows = converter.convert_columns(&[Arc::new(union_array)]).unwrap();
6072
6073 assert!(rows.row(2) < rows.row(1));
6085
6086 assert!(rows.row(0) < rows.row(3));
6088
6089 assert!(rows.row(2) < rows.row(4));
6092 assert!(rows.row(4) < rows.row(0));
6094
6095 assert!(rows.row(3) < rows.row(1));
6098 }
6099
6100 #[test]
6101 fn test_row_converter_roundtrip_with_many_union_columns() {
6102 let fields1 = UnionFields::try_new(
6104 vec![0, 1],
6105 vec![
6106 Field::new("int", DataType::Int32, true),
6107 Field::new("string", DataType::Utf8, true),
6108 ],
6109 )
6110 .unwrap();
6111
6112 let int_array1 = Int32Array::from(vec![Some(67), None]);
6113 let string_array1 = StringArray::from(vec![None::<&str>, Some("hello")]);
6114 let type_ids1 = vec![0i8, 1].into();
6115
6116 let union_array1 = UnionArray::try_new(
6117 fields1.clone(),
6118 type_ids1,
6119 None,
6120 vec![
6121 Arc::new(int_array1) as ArrayRef,
6122 Arc::new(string_array1) as ArrayRef,
6123 ],
6124 )
6125 .unwrap();
6126
6127 let fields2 = UnionFields::try_new(
6129 vec![0, 1],
6130 vec![
6131 Field::new("int", DataType::Int32, true),
6132 Field::new("string", DataType::Utf8, true),
6133 ],
6134 )
6135 .unwrap();
6136
6137 let int_array2 = Int32Array::from(vec![Some(100), None]);
6138 let string_array2 = StringArray::from(vec![None::<&str>, Some("world")]);
6139 let type_ids2 = vec![0i8, 1].into();
6140
6141 let union_array2 = UnionArray::try_new(
6142 fields2.clone(),
6143 type_ids2,
6144 None,
6145 vec![
6146 Arc::new(int_array2) as ArrayRef,
6147 Arc::new(string_array2) as ArrayRef,
6148 ],
6149 )
6150 .unwrap();
6151
6152 let field1 = Field::new("col1", DataType::Union(fields1, UnionMode::Sparse), true);
6154 let field2 = Field::new("col2", DataType::Union(fields2, UnionMode::Sparse), true);
6155
6156 let sort_field1 = SortField::new(field1.data_type().clone());
6157 let sort_field2 = SortField::new(field2.data_type().clone());
6158
6159 let converter = RowConverter::new(vec![sort_field1, sort_field2]).unwrap();
6160
6161 let rows = converter
6162 .convert_columns(&[
6163 Arc::new(union_array1.clone()) as ArrayRef,
6164 Arc::new(union_array2.clone()) as ArrayRef,
6165 ])
6166 .unwrap();
6167
6168 let out = converter.convert_rows(&rows).unwrap();
6170
6171 let [col1, col2] = out.as_slice() else {
6172 panic!("expected 2 columns")
6173 };
6174
6175 let col1 = col1.as_any().downcast_ref::<UnionArray>().unwrap();
6176 let col2 = col2.as_any().downcast_ref::<UnionArray>().unwrap();
6177
6178 for (expected, got) in [union_array1, union_array2].iter().zip([col1, col2]) {
6179 assert_eq!(expected.len(), got.len());
6180 assert_eq!(expected.type_ids(), got.type_ids());
6181
6182 for i in 0..expected.len() {
6183 assert_eq!(expected.value(i).as_ref(), got.value(i).as_ref());
6184 }
6185 }
6186 }
6187
6188 #[test]
6189 fn test_row_converter_roundtrip_with_one_union_column() {
6190 let fields = UnionFields::try_new(
6191 vec![0, 1],
6192 vec![
6193 Field::new("int", DataType::Int32, true),
6194 Field::new("string", DataType::Utf8, true),
6195 ],
6196 )
6197 .unwrap();
6198
6199 let int_array = Int32Array::from(vec![Some(67), None]);
6200 let string_array = StringArray::from(vec![None::<&str>, Some("hello")]);
6201 let type_ids = vec![0i8, 1].into();
6202
6203 let union_array = UnionArray::try_new(
6204 fields.clone(),
6205 type_ids,
6206 None,
6207 vec![
6208 Arc::new(int_array) as ArrayRef,
6209 Arc::new(string_array) as ArrayRef,
6210 ],
6211 )
6212 .unwrap();
6213
6214 let field = Field::new("col", DataType::Union(fields, UnionMode::Sparse), true);
6215 let sort_field = SortField::new(field.data_type().clone());
6216 let converter = RowConverter::new(vec![sort_field]).unwrap();
6217
6218 let rows = converter
6219 .convert_columns(&[Arc::new(union_array.clone()) as ArrayRef])
6220 .unwrap();
6221
6222 let out = converter.convert_rows(&rows).unwrap();
6224
6225 let [col1] = out.as_slice() else {
6226 panic!("expected 1 column")
6227 };
6228
6229 let col = col1.as_any().downcast_ref::<UnionArray>().unwrap();
6230 assert_eq!(col.len(), union_array.len());
6231 assert_eq!(col.type_ids(), union_array.type_ids());
6232
6233 for i in 0..col.len() {
6234 assert_eq!(col.value(i).as_ref(), union_array.value(i).as_ref());
6235 }
6236 }
6237
6238 #[test]
6239 fn test_row_converter_roundtrip_with_non_default_union_type_ids() {
6240 let fields = UnionFields::try_new(
6242 vec![70, 85],
6243 vec![
6244 Field::new("int", DataType::Int32, true),
6245 Field::new("string", DataType::Utf8, true),
6246 ],
6247 )
6248 .unwrap();
6249
6250 let int_array = Int32Array::from(vec![Some(67), None]);
6251 let string_array = StringArray::from(vec![None::<&str>, Some("hello")]);
6252 let type_ids = vec![70i8, 85].into();
6253
6254 let union_array = UnionArray::try_new(
6255 fields.clone(),
6256 type_ids,
6257 None,
6258 vec![
6259 Arc::new(int_array) as ArrayRef,
6260 Arc::new(string_array) as ArrayRef,
6261 ],
6262 )
6263 .unwrap();
6264
6265 let field = Field::new("col", DataType::Union(fields, UnionMode::Sparse), true);
6266 let sort_field = SortField::new(field.data_type().clone());
6267 let converter = RowConverter::new(vec![sort_field]).unwrap();
6268
6269 let rows = converter
6270 .convert_columns(&[Arc::new(union_array.clone()) as ArrayRef])
6271 .unwrap();
6272
6273 let out = converter.convert_rows(&rows).unwrap();
6275
6276 let [col1] = out.as_slice() else {
6277 panic!("expected 1 column")
6278 };
6279
6280 let col = col1.as_any().downcast_ref::<UnionArray>().unwrap();
6281 assert_eq!(col.len(), union_array.len());
6282 assert_eq!(col.type_ids(), union_array.type_ids());
6283
6284 for i in 0..col.len() {
6285 assert_eq!(col.value(i).as_ref(), union_array.value(i).as_ref());
6286 }
6287 }
6288
6289 #[test]
6290 fn rows_size_should_count_for_capacity() {
6291 let row_converter = RowConverter::new(vec![SortField::new(DataType::UInt8)]).unwrap();
6292
6293 let empty_rows_size_with_preallocate_rows_and_data = {
6294 let rows = row_converter.empty_rows(1000, 1000);
6295
6296 rows.size()
6297 };
6298 let empty_rows_size_with_preallocate_rows = {
6299 let rows = row_converter.empty_rows(1000, 0);
6300
6301 rows.size()
6302 };
6303 let empty_rows_size_with_preallocate_data = {
6304 let rows = row_converter.empty_rows(0, 1000);
6305
6306 rows.size()
6307 };
6308 let empty_rows_size_without_preallocate = {
6309 let rows = row_converter.empty_rows(0, 0);
6310
6311 rows.size()
6312 };
6313
6314 assert!(
6315 empty_rows_size_with_preallocate_rows_and_data > empty_rows_size_with_preallocate_rows,
6316 "{empty_rows_size_with_preallocate_rows_and_data} should be larger than {empty_rows_size_with_preallocate_rows}"
6317 );
6318 assert!(
6319 empty_rows_size_with_preallocate_rows_and_data > empty_rows_size_with_preallocate_data,
6320 "{empty_rows_size_with_preallocate_rows_and_data} should be larger than {empty_rows_size_with_preallocate_data}"
6321 );
6322 assert!(
6323 empty_rows_size_with_preallocate_rows > empty_rows_size_without_preallocate,
6324 "{empty_rows_size_with_preallocate_rows} should be larger than {empty_rows_size_without_preallocate}"
6325 );
6326 assert!(
6327 empty_rows_size_with_preallocate_data > empty_rows_size_without_preallocate,
6328 "{empty_rows_size_with_preallocate_data} should be larger than {empty_rows_size_without_preallocate}"
6329 );
6330 }
6331
6332 #[test]
6333 fn test_struct_no_child_fields() {
6334 fn run_test(array: ArrayRef) {
6335 let sort_fields = vec![SortField::new(array.data_type().clone())];
6336 let converter = RowConverter::new(sort_fields).unwrap();
6337 let r = converter.convert_columns(&[Arc::clone(&array)]).unwrap();
6338
6339 let back = converter.convert_rows(&r).unwrap();
6340 assert_eq!(back.len(), 1);
6341 assert_eq!(&back[0], &array);
6342 }
6343
6344 let s = Arc::new(StructArray::new_empty_fields(5, None)) as ArrayRef;
6345 run_test(s);
6346
6347 let s = Arc::new(StructArray::new_empty_fields(
6348 5,
6349 Some(vec![true, false, true, false, false].into()),
6350 )) as ArrayRef;
6351 run_test(s);
6352 }
6353
6354 #[test]
6355 fn reserve_should_increase_capacity_to_the_requested_size() {
6356 let row_converter = RowConverter::new(vec![SortField::new(DataType::UInt8)]).unwrap();
6357 let mut empty_rows = row_converter.empty_rows(0, 0);
6358 empty_rows.reserve(50, 50);
6359 let before_size = empty_rows.size();
6360 empty_rows.reserve(50, 50);
6361 assert_eq!(
6362 empty_rows.size(),
6363 before_size,
6364 "Size should not change when reserving already reserved space"
6365 );
6366 empty_rows.reserve(10, 20);
6367 assert_eq!(
6368 empty_rows.size(),
6369 before_size,
6370 "Size should not change when already have space for the expected reserved data"
6371 );
6372
6373 empty_rows.reserve(100, 20);
6374 assert!(
6375 empty_rows.size() > before_size,
6376 "Size should increase when reserving more space than previously reserved"
6377 );
6378
6379 let before_size = empty_rows.size();
6380
6381 empty_rows.reserve(20, 100);
6382 assert!(
6383 empty_rows.size() > before_size,
6384 "Size should increase when reserving more space than previously reserved"
6385 );
6386 }
6387
6388 #[test]
6389 fn empty_rows_should_return_empty_lengths_iterator() {
6390 let rows = RowConverter::new(vec![SortField::new(DataType::UInt8)])
6391 .unwrap()
6392 .empty_rows(0, 0);
6393 let mut lengths_iter = rows.lengths();
6394 assert_eq!(lengths_iter.next(), None);
6395 }
6396
6397 #[test]
6398 #[should_panic(expected = "row index out of bounds")]
6399 fn row_should_panic_on_overflowing_index() {
6400 let rows = RowConverter::new(vec![SortField::new(DataType::Int32)])
6401 .unwrap()
6402 .empty_rows(0, 0);
6403 rows.row(usize::MAX);
6404 }
6405
6406 #[test]
6407 #[should_panic(expected = "row index out of bounds")]
6408 fn row_len_should_panic_on_overflowing_index() {
6409 let rows = RowConverter::new(vec![SortField::new(DataType::Int32)])
6410 .unwrap()
6411 .empty_rows(0, 0);
6412 rows.row_len(usize::MAX);
6413 }
6414
6415 #[test]
6416 fn test_nested_null_list() {
6417 let null_array = Arc::new(NullArray::new(3));
6418 let list: ArrayRef = Arc::new(ListArray::new(
6420 Field::new_list_field(DataType::Null, true).into(),
6421 OffsetBuffer::from_lengths(vec![1, 0, 2]),
6422 null_array,
6423 None,
6424 ));
6425
6426 let converter = RowConverter::new(vec![SortField::new(list.data_type().clone())]).unwrap();
6427 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6428 let back = converter.convert_rows(&rows).unwrap();
6429
6430 assert_eq!(&list, &back[0]);
6431 }
6432
6433 #[test]
6435 fn test_double_nested_null_list() {
6436 let null_array = Arc::new(NullArray::new(1));
6437 let nested_field = Arc::new(Field::new_list_field(DataType::Null, true));
6439 let nested_list = Arc::new(ListArray::new(
6440 nested_field.clone(),
6441 OffsetBuffer::from_lengths(vec![1]),
6442 null_array,
6443 None,
6444 ));
6445 let list = Arc::new(ListArray::new(
6447 Field::new_list_field(DataType::List(nested_field), true).into(),
6448 OffsetBuffer::from_lengths(vec![1]),
6449 nested_list,
6450 None,
6451 )) as ArrayRef;
6452
6453 let converter = RowConverter::new(vec![SortField::new(list.data_type().clone())]).unwrap();
6454 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6455 let back = converter.convert_rows(&rows).unwrap();
6456
6457 assert_eq!(&list, &back[0]);
6458 }
6459
6460 #[test]
6462 fn test_large_list_null() {
6463 let null_array = Arc::new(NullArray::new(3));
6464 let list: ArrayRef = Arc::new(LargeListArray::new(
6466 Field::new_list_field(DataType::Null, true).into(),
6467 OffsetBuffer::from_lengths(vec![1, 0, 2]),
6468 null_array,
6469 None,
6470 ));
6471
6472 let converter = RowConverter::new(vec![SortField::new(list.data_type().clone())]).unwrap();
6473 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6474 let back = converter.convert_rows(&rows).unwrap();
6475
6476 assert_eq!(&list, &back[0]);
6477 }
6478
6479 #[test]
6481 fn test_fixed_size_list_null() {
6482 let null_array = Arc::new(NullArray::new(6));
6483 let list: ArrayRef = Arc::new(FixedSizeListArray::new(
6485 Arc::new(Field::new_list_field(DataType::Null, true)),
6486 2,
6487 null_array,
6488 None,
6489 ));
6490
6491 let converter = RowConverter::new(vec![SortField::new(list.data_type().clone())]).unwrap();
6492 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6493 let back = converter.convert_rows(&rows).unwrap();
6494
6495 assert_eq!(&list, &back[0]);
6496 }
6497
6498 #[test]
6500 fn test_fixed_size_list_of_dictionaries_round_trips() {
6501 let dict_dt = DataType::Dictionary(Box::new(DataType::Int32), Box::new(DataType::Utf8));
6504 let element_field = Arc::new(Field::new("item", dict_dt.clone(), true));
6505 let fsl_dt = DataType::FixedSizeList(Arc::clone(&element_field), 2);
6506
6507 let values = Arc::new(StringArray::from(vec!["a", "b"]));
6508 let keys = Int32Array::from(vec![0, 1]);
6509 let dict = DictionaryArray::<Int32Type>::try_new(keys, values).unwrap();
6510 let fsl: ArrayRef = Arc::new(FixedSizeListArray::new(
6511 Arc::clone(&element_field),
6512 2,
6513 Arc::new(dict),
6514 None,
6515 ));
6516
6517 assert!(RowConverter::supports_fields(&[SortField::new(
6518 fsl_dt.clone()
6519 )]));
6520
6521 let converter = RowConverter::new(vec![SortField::new(fsl_dt.clone())]).unwrap();
6522 let rows = converter.convert_columns(&[Arc::clone(&fsl)]).unwrap();
6523
6524 let back = converter.convert_rows(&rows).unwrap();
6527 assert_eq!(back.len(), 1);
6528
6529 let out = back[0]
6533 .as_any()
6534 .downcast_ref::<FixedSizeListArray>()
6535 .expect("decoded array must be a FixedSizeListArray");
6536 assert_eq!(out.len(), 1);
6537 assert_eq!(out.value_length(), 2);
6538 assert_eq!(out.values().data_type(), &DataType::Utf8);
6542
6543 let values = out
6545 .values()
6546 .as_any()
6547 .downcast_ref::<StringArray>()
6548 .expect("child must be a StringArray after flattening");
6549 assert_eq!(values.value(0), "a");
6550 assert_eq!(values.value(1), "b");
6551 }
6552
6553 #[test]
6555 fn test_list_null_variations() {
6556 let null_array = Arc::new(NullArray::new(3));
6558 let list: ArrayRef = Arc::new(ListArray::new(
6559 Field::new_list_field(DataType::Null, true).into(),
6560 OffsetBuffer::from_lengths(vec![1, 0, 2]),
6561 null_array,
6562 None,
6563 ));
6564
6565 let converter = RowConverter::new(vec![SortField::new(list.data_type().clone())]).unwrap();
6566 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6567 let back = converter.convert_rows(&rows).unwrap();
6568 assert_eq!(&list, &back[0]);
6569
6570 let null_array = Arc::new(NullArray::new(3));
6572 let list: ArrayRef = Arc::new(ListArray::new(
6573 Field::new_list_field(DataType::Null, true).into(),
6574 OffsetBuffer::from_lengths(vec![1, 0, 2]),
6575 null_array,
6576 Some(vec![true, false, true].into()),
6577 ));
6578
6579 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6580 let back = converter.convert_rows(&rows).unwrap();
6581 assert_eq!(&list, &back[0]);
6582
6583 let null_array = Arc::new(NullArray::new(0));
6585 let list: ArrayRef = Arc::new(ListArray::new(
6586 Field::new_list_field(DataType::Null, true).into(),
6587 OffsetBuffer::from_lengths(vec![]),
6588 null_array,
6589 None,
6590 ));
6591
6592 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6593 let back = converter.convert_rows(&rows).unwrap();
6594 assert_eq!(&list, &back[0]);
6595
6596 let null_array = Arc::new(NullArray::new(0));
6598 let list: ArrayRef = Arc::new(ListArray::new(
6599 Field::new_list_field(DataType::Null, true).into(),
6600 OffsetBuffer::from_lengths(vec![0, 0, 0]),
6601 null_array,
6602 None,
6603 ));
6604
6605 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6606 let back = converter.convert_rows(&rows).unwrap();
6607 assert_eq!(&list, &back[0]);
6608 }
6609
6610 #[test]
6612 fn test_list_null_descending() {
6613 let null_array = Arc::new(NullArray::new(3));
6614 let list: ArrayRef = Arc::new(ListArray::new(
6616 Field::new_list_field(DataType::Null, true).into(),
6617 OffsetBuffer::from_lengths(vec![1, 0, 2]),
6618 null_array,
6619 None,
6620 ));
6621
6622 let options = SortOptions::default().with_descending(true);
6623 let field = SortField::new_with_options(list.data_type().clone(), options);
6624 let converter = RowConverter::new(vec![field]).unwrap();
6625 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
6626 let back = converter.convert_rows(&rows).unwrap();
6627
6628 assert_eq!(&list, &back[0]);
6629 }
6630
6631 #[test]
6633 fn test_struct_with_null_field() {
6634 let null_array = Arc::new(NullArray::new(3));
6636 let int_array = Arc::new(Int32Array::from(vec![1, 2, 3]));
6637
6638 let struct_array: ArrayRef = Arc::new(StructArray::new(
6639 vec![
6640 Arc::new(Field::new("a", DataType::Null, true)),
6641 Arc::new(Field::new("b", DataType::Int32, true)),
6642 ]
6643 .into(),
6644 vec![null_array, int_array],
6645 Some(vec![true, true, false].into()), ));
6647
6648 let converter =
6649 RowConverter::new(vec![SortField::new(struct_array.data_type().clone())]).unwrap();
6650 let rows = converter
6651 .convert_columns(&[Arc::clone(&struct_array)])
6652 .unwrap();
6653 let back = converter.convert_rows(&rows).unwrap();
6654
6655 assert_eq!(&struct_array, &back[0]);
6656 }
6657
6658 #[test]
6660 fn test_nested_struct_with_null() {
6661 let inner_null = Arc::new(NullArray::new(2));
6663 let inner_struct = Arc::new(StructArray::new(
6664 vec![Arc::new(Field::new("x", DataType::Null, true))].into(),
6665 vec![inner_null],
6666 None,
6667 ));
6668
6669 let y_array = Arc::new(Int32Array::from(vec![10, 20]));
6671 let outer_struct: ArrayRef = Arc::new(StructArray::new(
6672 vec![
6673 Arc::new(Field::new("inner", inner_struct.data_type().clone(), true)),
6674 Arc::new(Field::new("y", DataType::Int32, true)),
6675 ]
6676 .into(),
6677 vec![inner_struct, y_array],
6678 None,
6679 ));
6680
6681 let converter =
6682 RowConverter::new(vec![SortField::new(outer_struct.data_type().clone())]).unwrap();
6683 let rows = converter
6684 .convert_columns(&[Arc::clone(&outer_struct)])
6685 .unwrap();
6686 let back = converter.convert_rows(&rows).unwrap();
6687
6688 assert_eq!(&outer_struct, &back[0]);
6689 }
6690
6691 #[test]
6693 fn test_map_null_variations() {
6694 let keys = Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef;
6696 let null_values = Arc::new(NullArray::new(3)) as ArrayRef;
6697
6698 let offsets = OffsetBuffer::new(vec![0, 1, 1, 3].into());
6699 let entries_fields = vec![
6700 Arc::new(Field::new(
6701 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6702 DataType::Utf8,
6703 false,
6704 )),
6705 Arc::new(Field::new(
6706 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6707 DataType::Null,
6708 true,
6709 )),
6710 ];
6711 let struct_field = Arc::new(Field::new(
6712 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6713 DataType::Struct(entries_fields.clone().into()),
6714 false,
6715 ));
6716 let entries = StructArray::new(entries_fields.into(), vec![keys, null_values], None);
6717
6718 let map: ArrayRef = Arc::new(MapArray::new(
6719 struct_field.clone(),
6720 offsets,
6721 entries,
6722 None,
6723 false,
6724 ));
6725
6726 let converter = RowConverter::new(vec![SortField::new(map.data_type().clone())]).unwrap();
6727 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
6728 let back = converter.convert_rows(&rows).unwrap();
6729 assert_eq!(back.len(), 1);
6730 back[0].to_data().validate_full().unwrap();
6731 assert_eq!(&map, &back[0]);
6732
6733 let keys = Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef;
6735 let null_values = Arc::new(NullArray::new(3)) as ArrayRef;
6736
6737 let offsets = OffsetBuffer::new(vec![0, 1, 1, 3].into());
6738 let entries_fields = vec![
6739 Arc::new(Field::new(
6740 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6741 DataType::Utf8,
6742 false,
6743 )),
6744 Arc::new(Field::new(
6745 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6746 DataType::Null,
6747 true,
6748 )),
6749 ];
6750 let struct_field = Arc::new(Field::new(
6751 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6752 DataType::Struct(entries_fields.clone().into()),
6753 false,
6754 ));
6755 let entries = StructArray::new(entries_fields.into(), vec![keys, null_values], None);
6756
6757 let map: ArrayRef = Arc::new(MapArray::new(
6758 struct_field.clone(),
6759 offsets,
6760 entries,
6761 Some(vec![true, false, true].into()),
6762 false,
6763 ));
6764
6765 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
6766 let back = converter.convert_rows(&rows).unwrap();
6767 assert_eq!(back.len(), 1);
6768 back[0].to_data().validate_full().unwrap();
6769 assert_eq!(&map, &back[0]);
6770
6771 let keys = Arc::new(StringArray::from(Vec::<&str>::new())) as ArrayRef;
6773 let null_values = Arc::new(NullArray::new(0)) as ArrayRef;
6774
6775 let offsets = OffsetBuffer::new(vec![0i32].into());
6776 let entries_fields = vec![
6777 Arc::new(Field::new(
6778 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6779 DataType::Utf8,
6780 false,
6781 )),
6782 Arc::new(Field::new(
6783 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6784 DataType::Null,
6785 true,
6786 )),
6787 ];
6788 let struct_field = Arc::new(Field::new(
6789 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6790 DataType::Struct(entries_fields.clone().into()),
6791 false,
6792 ));
6793 let entries = StructArray::new(entries_fields.into(), vec![keys, null_values], None);
6794
6795 let map: ArrayRef = Arc::new(MapArray::new(struct_field, offsets, entries, None, false));
6796
6797 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
6798 let back = converter.convert_rows(&rows).unwrap();
6799 assert_eq!(back.len(), 1);
6800 back[0].to_data().validate_full().unwrap();
6801 assert_eq!(&map, &back[0]);
6802 }
6803
6804 #[test]
6806 fn test_map_null_descending() {
6807 let keys = Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef;
6809 let null_values = Arc::new(NullArray::new(3)) as ArrayRef;
6810
6811 let offsets = OffsetBuffer::new(vec![0, 1, 1, 3].into());
6812 let entries_fields = vec![
6813 Arc::new(Field::new(
6814 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6815 DataType::Utf8,
6816 false,
6817 )),
6818 Arc::new(Field::new(
6819 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6820 DataType::Null,
6821 true,
6822 )),
6823 ];
6824 let struct_field = Arc::new(Field::new(
6825 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6826 DataType::Struct(entries_fields.clone().into()),
6827 false,
6828 ));
6829 let entries = StructArray::new(entries_fields.into(), vec![keys, null_values], None);
6830
6831 let map: ArrayRef = Arc::new(MapArray::new(struct_field, offsets, entries, None, false));
6832
6833 let options = SortOptions::default().with_descending(true);
6834 let field = SortField::new_with_options(map.data_type().clone(), options);
6835 let converter = RowConverter::new(vec![field]).unwrap();
6836 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
6837 let back = converter.convert_rows(&rows).unwrap();
6838 assert_eq!(back.len(), 1);
6839 back[0].to_data().validate_full().unwrap();
6840 assert_eq!(&map, &back[0]);
6841 }
6842
6843 #[test]
6845 fn test_map_null_all_empty() {
6846 let keys = Arc::new(StringArray::from(Vec::<&str>::new())) as ArrayRef;
6847 let null_values = Arc::new(NullArray::new(0)) as ArrayRef;
6848
6849 let offsets = OffsetBuffer::new(vec![0, 0, 0, 0].into());
6850 let entries_fields = vec![
6851 Arc::new(Field::new(
6852 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6853 DataType::Utf8,
6854 false,
6855 )),
6856 Arc::new(Field::new(
6857 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6858 DataType::Null,
6859 true,
6860 )),
6861 ];
6862 let struct_field = Arc::new(Field::new(
6863 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6864 DataType::Struct(entries_fields.clone().into()),
6865 false,
6866 ));
6867 let entries = StructArray::new(entries_fields.into(), vec![keys, null_values], None);
6868
6869 let map: ArrayRef = Arc::new(MapArray::new(struct_field, offsets, entries, None, false));
6870
6871 let converter = RowConverter::new(vec![SortField::new(map.data_type().clone())]).unwrap();
6872 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
6873
6874 assert_eq!(rows.row(0), rows.row(1));
6876 assert_eq!(rows.row(1), rows.row(2));
6877
6878 let back = converter.convert_rows(&rows).unwrap();
6879 assert_eq!(back.len(), 1);
6880 back[0].to_data().validate_full().unwrap();
6881 assert_eq!(&map, &back[0]);
6882 }
6883
6884 #[test]
6886 fn test_nested_map_null() {
6887 let inner_keys = Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef;
6889 let inner_null_values = Arc::new(NullArray::new(3)) as ArrayRef;
6890
6891 let inner_entries_fields = vec![
6892 Arc::new(Field::new(
6893 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6894 DataType::Utf8,
6895 false,
6896 )),
6897 Arc::new(Field::new(
6898 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6899 DataType::Null,
6900 true,
6901 )),
6902 ];
6903 let inner_struct_field = Arc::new(Field::new(
6904 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6905 DataType::Struct(inner_entries_fields.clone().into()),
6906 false,
6907 ));
6908 let inner_entries = StructArray::new(
6909 inner_entries_fields.clone().into(),
6910 vec![inner_keys, inner_null_values],
6911 None,
6912 );
6913
6914 let inner_map = Arc::new(MapArray::new(
6916 inner_struct_field.clone(),
6917 OffsetBuffer::new(vec![0, 1, 3].into()),
6918 inner_entries,
6919 None,
6920 false,
6921 )) as ArrayRef;
6922
6923 let outer_keys = Arc::new(StringArray::from(vec!["x", "y"])) as ArrayRef;
6925
6926 let inner_map_type = DataType::Map(inner_struct_field.clone(), false);
6927 let outer_entries_fields = vec![
6928 Arc::new(Field::new(
6929 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6930 DataType::Utf8,
6931 false,
6932 )),
6933 Arc::new(Field::new(
6934 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6935 inner_map_type,
6936 true,
6937 )),
6938 ];
6939 let outer_struct_field = Arc::new(Field::new(
6940 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6941 DataType::Struct(outer_entries_fields.clone().into()),
6942 false,
6943 ));
6944 let outer_entries = StructArray::new(
6945 outer_entries_fields.into(),
6946 vec![outer_keys, inner_map],
6947 None,
6948 );
6949
6950 let map: ArrayRef = Arc::new(MapArray::new(
6952 outer_struct_field,
6953 OffsetBuffer::new(vec![0, 1, 2].into()),
6954 outer_entries,
6955 None,
6956 false,
6957 ));
6958
6959 let converter = RowConverter::new(vec![SortField::new(map.data_type().clone())]).unwrap();
6960 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
6961 let back = converter.convert_rows(&rows).unwrap();
6962 assert_eq!(back.len(), 1);
6963 back[0].to_data().validate_full().unwrap();
6964 assert_eq!(&map, &back[0]);
6965 }
6966
6967 #[test]
6969 fn test_list_of_map_null() {
6970 let keys = Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef;
6972 let null_values = Arc::new(NullArray::new(3)) as ArrayRef;
6973
6974 let entries_fields = vec![
6975 Arc::new(Field::new(
6976 Field::MAP_KEY_FIELD_DEFAULT_NAME,
6977 DataType::Utf8,
6978 false,
6979 )),
6980 Arc::new(Field::new(
6981 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
6982 DataType::Null,
6983 true,
6984 )),
6985 ];
6986 let struct_field = Arc::new(Field::new(
6987 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
6988 DataType::Struct(entries_fields.clone().into()),
6989 false,
6990 ));
6991 let entries = StructArray::new(entries_fields.into(), vec![keys, null_values], None);
6992
6993 let map_array = Arc::new(MapArray::new(
6995 struct_field.clone(),
6996 OffsetBuffer::new(vec![0, 1, 1, 3].into()),
6997 entries,
6998 None,
6999 false,
7000 )) as ArrayRef;
7001
7002 let map_type = DataType::Map(struct_field, false);
7003 let list: ArrayRef = Arc::new(ListArray::new(
7005 Arc::new(Field::new_list_field(map_type, true)),
7006 OffsetBuffer::new(vec![0, 1, 3].into()),
7007 map_array,
7008 None,
7009 ));
7010
7011 let converter = RowConverter::new(vec![SortField::new(list.data_type().clone())]).unwrap();
7012 let rows = converter.convert_columns(&[Arc::clone(&list)]).unwrap();
7013 let back = converter.convert_rows(&rows).unwrap();
7014 assert_eq!(&list, &back[0]);
7015 }
7016
7017 #[test]
7019 fn test_map_of_list_null() {
7020 let null_array = Arc::new(NullArray::new(3)) as ArrayRef;
7022 let list_array = Arc::new(ListArray::new(
7024 Arc::new(Field::new_list_field(DataType::Null, true)),
7025 OffsetBuffer::from_lengths(vec![1, 0, 2]),
7026 null_array,
7027 None,
7028 )) as ArrayRef;
7029
7030 let keys = Arc::new(StringArray::from(vec!["a", "b", "c"])) as ArrayRef;
7031
7032 let list_type = list_array.data_type().clone();
7033 let entries_fields = vec![
7034 Arc::new(Field::new(
7035 Field::MAP_KEY_FIELD_DEFAULT_NAME,
7036 DataType::Utf8,
7037 false,
7038 )),
7039 Arc::new(Field::new(
7040 Field::MAP_VALUE_FIELD_DEFAULT_NAME,
7041 list_type,
7042 true,
7043 )),
7044 ];
7045 let struct_field = Arc::new(Field::new(
7046 Field::MAP_ENTRIES_FIELD_DEFAULT_NAME,
7047 DataType::Struct(entries_fields.clone().into()),
7048 false,
7049 ));
7050 let entries = StructArray::new(entries_fields.into(), vec![keys, list_array], None);
7051
7052 let map: ArrayRef = Arc::new(MapArray::new(
7054 struct_field,
7055 OffsetBuffer::new(vec![0, 3].into()),
7056 entries,
7057 None,
7058 false,
7059 ));
7060
7061 let converter = RowConverter::new(vec![SortField::new(map.data_type().clone())]).unwrap();
7062 let rows = converter.convert_columns(&[Arc::clone(&map)]).unwrap();
7063 let back = converter.convert_rows(&rows).unwrap();
7064 assert_eq!(back.len(), 1);
7065 back[0].to_data().validate_full().unwrap();
7066 assert_eq!(&map, &back[0]);
7067 }
7068
7069 #[test]
7070 fn empty_row_iter_next_back() {
7071 let rows = RowConverter::new(vec![SortField::new(DataType::UInt8)])
7072 .unwrap()
7073 .empty_rows(0, 0);
7074 let mut rows_iter = rows.iter();
7075 assert_eq!(rows_iter.next_back(), None);
7076 assert_eq!(rows_iter.next_back(), None);
7077 assert_eq!(rows_iter.next_back(), None);
7078 }
7079
7080 #[test]
7082 fn test_row_parser_skip_utf8_validation_roundtrip() {
7083 let converter = RowConverter::new(vec![SortField::new(DataType::Utf8)]).unwrap();
7084 let array = StringArray::from(vec!["arrow", "rust"]);
7085 let rows = converter.convert_columns(&[Arc::new(array) as _]).unwrap();
7086 let binary = rows.try_into_binary().expect("fits in i32 offsets");
7087
7088 let parser = unsafe { RowParser::with_skip_utf8_validate(Arc::clone(&converter.fields)) };
7090
7091 let decoded = converter
7092 .convert_rows(binary.iter().map(|b| parser.parse(b.unwrap())))
7093 .unwrap();
7094 let got: Vec<_> = decoded[0].as_string::<i32>().iter().flatten().collect();
7095 assert_eq!(got, vec!["arrow", "rust"]);
7096 }
7097
7098 #[test]
7099 fn row_iter_next_back() {
7100 let row_converter = RowConverter::new(vec![SortField::new(DataType::UInt8)]).unwrap();
7101 let mut rng = StdRng::seed_from_u64(42);
7102 let array = generate_primitive_array::<UInt8Type>(&mut rng, 100, 0.8);
7103 let rows = row_converter.convert_columns(&[Arc::new(array)]).unwrap();
7104
7105 let mut rows_iter = rows.iter();
7106 let mut bytes: Vec<u8> = vec![];
7107
7108 while let Some(row) = rows_iter.next_back() {
7109 bytes.extend(row.data.iter().rev());
7110 }
7111
7112 bytes.reverse();
7113
7114 assert_eq!(
7115 bytes,
7116 &rows.buffer.as_slice()[..*rows.offsets.last().unwrap()]
7117 );
7118
7119 assert_eq!(rows_iter.next_back(), None);
7120 assert_eq!(rows_iter.next(), None);
7121 }
7122
7123 trait SharedBetweenRowsIteratorAndSliceIter<'a>:
7124 ExactSizeIterator<Item = Row<'a>> + DoubleEndedIterator<Item = Row<'a>>
7125 {
7126 }
7127 impl<'a, T: ?Sized + ExactSizeIterator<Item = Row<'a>> + DoubleEndedIterator<Item = Row<'a>>>
7128 SharedBetweenRowsIteratorAndSliceIter<'a> for T
7129 {
7130 }
7131
7132 fn get_rows_iterator_cases() -> impl Iterator<Item = Rows> {
7133 let rows_converter = RowConverter::new(vec![SortField::new(DataType::Int32)]).unwrap();
7134
7135 [0, 1, 6, 8, 100, 164]
7136 .map(|len| {
7137 let source = (0..).take(len).collect::<Vec<i32>>();
7138
7139 let source = Int32Array::from(source);
7140
7141 rows_converter.convert_columns(&[Arc::new(source)]).unwrap()
7142 })
7143 .into_iter()
7144 }
7145
7146 fn setup_and_assert(
7147 setup_iters: impl Fn(&mut dyn SharedBetweenRowsIteratorAndSliceIter),
7148 assert_fn: impl Fn(RowsIter, Copied<Iter<Row>>),
7149 ) {
7150 for rows in get_rows_iterator_cases() {
7151 let expected = (0..rows.num_rows())
7152 .map(|i| rows.row(i))
7153 .collect::<Vec<_>>();
7154 let mut expected_iter = expected.iter().copied();
7155
7156 let mut actual = rows.iter();
7157
7158 setup_iters(&mut actual);
7159 setup_iters(&mut expected_iter);
7160
7161 assert_fn(actual, expected_iter);
7162 }
7163 }
7164
7165 trait RowsIteratorOp {
7168 type Output<'a>: PartialEq + Debug;
7170
7171 const NAME: &'static str;
7173
7174 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(iter: T)
7177 -> Self::Output<'a>;
7178 }
7179
7180 fn assert_rows_iterator_cases<O: RowsIteratorOp>() {
7184 setup_and_assert(
7185 |_iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {},
7186 |actual, expected| {
7187 let current_iterator_values: Vec<Row> = expected.clone().collect();
7188 assert_eq!(
7189 O::get_value(actual),
7190 O::get_value(expected),
7191 "Failed on op {} for new iter (left actual, right expected) ({current_iterator_values:?})",
7192 O::NAME
7193 );
7194 },
7195 );
7196
7197 setup_and_assert(
7198 |iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {
7199 iter.next();
7200 },
7201 |actual, expected| {
7202 let current_iterator_values: Vec<Row> = expected.clone().collect();
7203
7204 assert_eq!(
7205 O::get_value(actual),
7206 O::get_value(expected),
7207 "Failed on op {} for new iter after consuming 1 element from the start (left actual, right expected) ({current_iterator_values:?})",
7208 O::NAME
7209 );
7210 },
7211 );
7212
7213 setup_and_assert(
7214 |iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {
7215 iter.next_back();
7216 },
7217 |actual, expected| {
7218 let current_iterator_values: Vec<Row> = expected.clone().collect();
7219
7220 assert_eq!(
7221 O::get_value(actual),
7222 O::get_value(expected),
7223 "Failed on op {} for new iter after consuming 1 element from the end (left actual, right expected) ({current_iterator_values:?})",
7224 O::NAME
7225 );
7226 },
7227 );
7228
7229 setup_and_assert(
7230 |iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {
7231 iter.next();
7232 iter.next_back();
7233 },
7234 |actual, expected| {
7235 let current_iterator_values: Vec<Row> = expected.clone().collect();
7236
7237 assert_eq!(
7238 O::get_value(actual),
7239 O::get_value(expected),
7240 "Failed on op {} for new iter after consuming 1 element from start and end (left actual, right expected) ({current_iterator_values:?})",
7241 O::NAME
7242 );
7243 },
7244 );
7245
7246 setup_and_assert(
7247 |iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {
7248 while iter.len() > 1 {
7249 iter.next();
7250 }
7251 },
7252 |actual, expected| {
7253 let current_iterator_values: Vec<Row> = expected.clone().collect();
7254
7255 assert_eq!(
7256 O::get_value(actual),
7257 O::get_value(expected),
7258 "Failed on op {} for new iter after consuming all from the start but 1 (left actual, right expected) ({current_iterator_values:?})",
7259 O::NAME
7260 );
7261 },
7262 );
7263
7264 setup_and_assert(
7265 |iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {
7266 while iter.len() > 1 {
7267 iter.next_back();
7268 }
7269 },
7270 |actual, expected| {
7271 let current_iterator_values: Vec<Row> = expected.clone().collect();
7272
7273 assert_eq!(
7274 O::get_value(actual),
7275 O::get_value(expected),
7276 "Failed on op {} for new iter after consuming all from the end but 1 (left actual, right expected) ({current_iterator_values:?})",
7277 O::NAME
7278 );
7279 },
7280 );
7281
7282 setup_and_assert(
7283 |iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {
7284 while iter.next().is_some() {}
7285 },
7286 |actual, expected| {
7287 let current_iterator_values: Vec<Row> = expected.clone().collect();
7288
7289 assert_eq!(
7290 O::get_value(actual),
7291 O::get_value(expected),
7292 "Failed on op {} for new iter after consuming all from the start (left actual, right expected) ({current_iterator_values:?})",
7293 O::NAME
7294 );
7295 },
7296 );
7297
7298 setup_and_assert(
7299 |iter: &mut dyn SharedBetweenRowsIteratorAndSliceIter| {
7300 while iter.next_back().is_some() {}
7301 },
7302 |actual, expected| {
7303 let current_iterator_values: Vec<Row> = expected.clone().collect();
7304
7305 assert_eq!(
7306 O::get_value(actual),
7307 O::get_value(expected),
7308 "Failed on op {} for new iter after consuming all from the end (left actual, right expected) ({current_iterator_values:?})",
7309 O::NAME
7310 );
7311 },
7312 );
7313 }
7314
7315 #[test]
7316 fn assert_rows_iterator_count() {
7317 struct CountOp;
7318
7319 impl RowsIteratorOp for CountOp {
7320 type Output<'a> = usize;
7321 const NAME: &'static str = "count";
7322
7323 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(
7324 iter: T,
7325 ) -> Self::Output<'a> {
7326 iter.count()
7327 }
7328 }
7329
7330 assert_rows_iterator_cases::<CountOp>()
7331 }
7332
7333 #[test]
7334 fn assert_rows_iterator_last() {
7335 struct LastOp;
7336
7337 impl RowsIteratorOp for LastOp {
7338 type Output<'a> = Option<Row<'a>>;
7339 const NAME: &'static str = "last";
7340
7341 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(
7342 iter: T,
7343 ) -> Self::Output<'a> {
7344 iter.last()
7345 }
7346 }
7347
7348 assert_rows_iterator_cases::<LastOp>()
7349 }
7350
7351 #[test]
7352 fn assert_rows_iterator_nth_0() {
7353 struct NthOp<const BACK: bool>;
7354
7355 impl<const BACK: bool> RowsIteratorOp for NthOp<BACK> {
7356 type Output<'a> = Option<Row<'a>>;
7357 const NAME: &'static str = if BACK { "nth_back(0)" } else { "nth(0)" };
7358
7359 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(
7360 mut iter: T,
7361 ) -> Self::Output<'a> {
7362 if BACK { iter.nth_back(0) } else { iter.nth(0) }
7363 }
7364 }
7365
7366 assert_rows_iterator_cases::<NthOp<false>>();
7367 assert_rows_iterator_cases::<NthOp<true>>();
7368 }
7369
7370 #[test]
7371 fn assert_rows_iterator_nth_1() {
7372 struct NthOp<const BACK: bool>;
7373
7374 impl<const BACK: bool> RowsIteratorOp for NthOp<BACK> {
7375 type Output<'a> = Option<Row<'a>>;
7376 const NAME: &'static str = if BACK { "nth_back(1)" } else { "nth(1)" };
7377
7378 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(
7379 mut iter: T,
7380 ) -> Self::Output<'a> {
7381 if BACK { iter.nth_back(1) } else { iter.nth(1) }
7382 }
7383 }
7384
7385 assert_rows_iterator_cases::<NthOp<false>>();
7386 assert_rows_iterator_cases::<NthOp<true>>();
7387 }
7388
7389 #[test]
7390 fn assert_rows_iterator_nth_after_end() {
7391 struct NthOp<const BACK: bool>;
7392
7393 impl<const BACK: bool> RowsIteratorOp for NthOp<BACK> {
7394 type Output<'a> = Option<Row<'a>>;
7395 const NAME: &'static str = if BACK {
7396 "nth_back(iter.len() + 1)"
7397 } else {
7398 "nth(iter.len() + 1)"
7399 };
7400
7401 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(
7402 mut iter: T,
7403 ) -> Self::Output<'a> {
7404 if BACK {
7405 iter.nth_back(iter.len() + 1)
7406 } else {
7407 iter.nth(iter.len() + 1)
7408 }
7409 }
7410 }
7411
7412 assert_rows_iterator_cases::<NthOp<false>>();
7413 assert_rows_iterator_cases::<NthOp<true>>();
7414 }
7415
7416 #[test]
7417 fn assert_rows_iterator_nth_len() {
7418 struct NthOp<const BACK: bool>;
7419
7420 impl<const BACK: bool> RowsIteratorOp for NthOp<BACK> {
7421 type Output<'a> = Option<Row<'a>>;
7422 const NAME: &'static str = if BACK {
7423 "nth_back(iter.len())"
7424 } else {
7425 "nth(iter.len())"
7426 };
7427
7428 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(
7429 mut iter: T,
7430 ) -> Self::Output<'a> {
7431 if BACK {
7432 iter.nth_back(iter.len())
7433 } else {
7434 iter.nth(iter.len())
7435 }
7436 }
7437 }
7438
7439 assert_rows_iterator_cases::<NthOp<false>>();
7440 assert_rows_iterator_cases::<NthOp<true>>();
7441 }
7442
7443 #[test]
7444 fn assert_rows_iterator_nth_last() {
7445 struct NthOp<const BACK: bool>;
7446
7447 impl<const BACK: bool> RowsIteratorOp for NthOp<BACK> {
7448 type Output<'a> = Option<Row<'a>>;
7449 const NAME: &'static str = if BACK {
7450 "nth_back(iter.len().saturating_sub(1))"
7451 } else {
7452 "nth(iter.len().saturating_sub(1))"
7453 };
7454
7455 fn get_value<'a, T: SharedBetweenRowsIteratorAndSliceIter<'a>>(
7456 mut iter: T,
7457 ) -> Self::Output<'a> {
7458 if BACK {
7459 iter.nth_back(iter.len().saturating_sub(1))
7460 } else {
7461 iter.nth(iter.len().saturating_sub(1))
7462 }
7463 }
7464 }
7465
7466 assert_rows_iterator_cases::<NthOp<false>>();
7467 assert_rows_iterator_cases::<NthOp<true>>();
7468 }
7469
7470 #[test]
7471 fn assert_rows_iterator_nth_and_reuse() {
7472 setup_and_assert(
7473 |_| {},
7474 |actual, expected| {
7475 {
7476 let mut actual = actual.clone();
7477 let mut expected = expected.clone();
7478 for _ in 0..expected.len() {
7479 #[expect(clippy::iter_nth_zero)]
7480 let actual_val = actual.nth(0);
7481 #[expect(clippy::iter_nth_zero)]
7482 let expected_val = expected.nth(0);
7483 assert_eq!(actual_val, expected_val, "Failed on nth(0)");
7484 }
7485 }
7486
7487 {
7488 let mut actual = actual.clone();
7489 let mut expected = expected.clone();
7490 for _ in 0..expected.len() {
7491 let actual_val = actual.nth(1);
7492 let expected_val = expected.nth(1);
7493 assert_eq!(actual_val, expected_val, "Failed on nth(1)");
7494 }
7495 }
7496
7497 {
7498 let mut actual = actual.clone();
7499 let mut expected = expected.clone();
7500 for _ in 0..expected.len() {
7501 let actual_val = actual.nth(2);
7502 let expected_val = expected.nth(2);
7503 assert_eq!(actual_val, expected_val, "Failed on nth(2)");
7504 }
7505 }
7506 },
7507 );
7508 }
7509
7510 #[test]
7511 fn assert_rows_iterator_nth_back_and_reuse() {
7512 setup_and_assert(
7513 |_| {},
7514 |actual, expected| {
7515 {
7516 let mut actual = actual.clone();
7517 let mut expected = expected.clone();
7518 for _ in 0..expected.len() {
7519 let actual_val = actual.nth_back(0);
7520 let expected_val = expected.nth_back(0);
7521 assert_eq!(actual_val, expected_val, "Failed on nth_back(0)");
7522 }
7523 }
7524
7525 {
7526 let mut actual = actual.clone();
7527 let mut expected = expected.clone();
7528 for _ in 0..expected.len() {
7529 let actual_val = actual.nth_back(1);
7530 let expected_val = expected.nth_back(1);
7531 assert_eq!(actual_val, expected_val, "Failed on nth_back(1)");
7532 }
7533 }
7534
7535 {
7536 let mut actual = actual.clone();
7537 let mut expected = expected.clone();
7538 for _ in 0..expected.len() {
7539 let actual_val = actual.nth_back(2);
7540 let expected_val = expected.nth_back(2);
7541 assert_eq!(actual_val, expected_val, "Failed on nth_back(2)");
7542 }
7543 }
7544 },
7545 );
7546 }
7547}