1use crate::{
6 BASIC_TYPE_BITS, BuilderSpecificState, ParentState, ValueBuilder, Variant, VariantBuilderExt,
7 builder::{metadata::MetadataBuilder, object::ObjectBuilder},
8 decoder::VariantBasicType,
9 int_size,
10};
11use arrow_schema::ArrowError;
12
13fn array_header(large: bool, offset_size: u8) -> u8 {
14 let large_bit = u8::from(large);
15 (large_bit << (BASIC_TYPE_BITS + 2))
16 | ((offset_size - 1) << BASIC_TYPE_BITS)
17 | VariantBasicType::Array as u8
18}
19
20fn append_packed_u32(dest: &mut Vec<u8>, value: u32, value_size: usize) {
22 let n = dest.len() + value_size;
23 dest.extend(value.to_le_bytes());
24 dest.truncate(n);
25}
26
27#[derive(Debug)]
33pub struct ListBuilder<'a, S: BuilderSpecificState> {
34 parent_state: ParentState<'a, S>,
35 offsets: Vec<usize>,
36 validate_unique_fields: bool,
37}
38
39impl<'a, S: BuilderSpecificState> ListBuilder<'a, S> {
40 pub fn new(parent_state: ParentState<'a, S>, validate_unique_fields: bool) -> Self {
42 Self {
43 parent_state,
44 offsets: vec![],
45 validate_unique_fields,
46 }
47 }
48
49 pub fn with_validate_unique_fields(mut self, validate_unique_fields: bool) -> Self {
54 self.validate_unique_fields = validate_unique_fields;
55 self
56 }
57
58 fn parent_state(&mut self) -> (ParentState<'_, ListState<'_>>, bool) {
60 let state = ParentState::list(
61 self.parent_state.value_builder,
62 self.parent_state.metadata_builder,
63 &mut self.offsets,
64 self.parent_state.saved_value_builder_offset,
65 );
66 (state, self.validate_unique_fields)
67 }
68
69 pub fn new_object(&mut self) -> ObjectBuilder<'_, ListState<'_>> {
73 let (parent_state, validate_unique_fields) = self.parent_state();
74 ObjectBuilder::new(parent_state, validate_unique_fields)
75 }
76
77 pub fn new_list(&mut self) -> ListBuilder<'_, ListState<'_>> {
81 let (parent_state, validate_unique_fields) = self.parent_state();
82 ListBuilder::new(parent_state, validate_unique_fields)
83 }
84
85 pub fn append_value<'m, 'd, T: Into<Variant<'m, 'd>>>(&mut self, value: T) {
92 let (state, _) = self.parent_state();
93 ValueBuilder::append_variant(state, value.into())
94 }
95
96 pub fn try_append_value<'m, 'd, T: Into<Variant<'m, 'd>>>(
98 &mut self,
99 value: T,
100 ) -> Result<(), ArrowError> {
101 let (state, _) = self.parent_state();
102 ValueBuilder::try_append_variant(state, value.into())
103 }
104
105 pub fn append_value_bytes<'m, 'd>(&mut self, value: impl Into<Variant<'m, 'd>>) {
114 let (state, _) = self.parent_state();
115 ValueBuilder::append_variant_bytes(state, value.into())
116 }
117
118 pub fn with_value<'m, 'd, T: Into<Variant<'m, 'd>>>(mut self, value: T) -> Self {
125 self.append_value(value);
126 self
127 }
128
129 pub fn try_with_value<'m, 'd, T: Into<Variant<'m, 'd>>>(
133 mut self,
134 value: T,
135 ) -> Result<Self, ArrowError> {
136 self.try_append_value(value)?;
137 Ok(self)
138 }
139
140 pub fn finish(mut self) {
142 let starting_offset = self.parent_state.saved_value_builder_offset;
143 let value_builder = self.parent_state.value_builder();
144
145 let data_size = value_builder
146 .offset()
147 .checked_sub(starting_offset)
148 .expect("Data size overflowed usize");
149
150 let num_elements = self.offsets.len();
151 let is_large = num_elements > u8::MAX as usize;
152 let offset_size = int_size(data_size);
153
154 let num_elements_size = if is_large { 4 } else { 1 }; let num_elements = self.offsets.len();
156 let header_size = 1 + num_elements_size + (num_elements + 1) * offset_size as usize; let mut bytes_to_splice = Vec::with_capacity(header_size + 3);
163 let header = array_header(is_large, offset_size as _);
165 bytes_to_splice.push(header);
166
167 append_packed_u32(&mut bytes_to_splice, num_elements as u32, num_elements_size);
168
169 for offset in &self.offsets {
170 append_packed_u32(&mut bytes_to_splice, *offset as u32, offset_size as usize);
171 }
172
173 append_packed_u32(&mut bytes_to_splice, data_size as u32, offset_size as usize);
174
175 value_builder
176 .inner_mut()
177 .splice(starting_offset..starting_offset, bytes_to_splice);
178
179 self.parent_state.finish();
180 }
181}
182
183impl<S: BuilderSpecificState> VariantBuilderExt for ListBuilder<'_, S> {
184 type State<'s>
185 = ListState<'s>
186 where
187 Self: 's;
188
189 fn append_null(&mut self) {
191 self.append_value(Variant::Null);
192 }
193 fn append_value<'m, 'v>(&mut self, value: impl Into<Variant<'m, 'v>>) {
194 self.append_value(value);
195 }
196
197 fn try_new_list(&mut self) -> Result<ListBuilder<'_, Self::State<'_>>, ArrowError> {
198 Ok(self.new_list())
199 }
200
201 fn try_new_object(&mut self) -> Result<ObjectBuilder<'_, Self::State<'_>>, ArrowError> {
202 Ok(self.new_object())
203 }
204}
205
206impl<'m, 'v, S, V> Extend<V> for ListBuilder<'_, S>
207where
208 S: BuilderSpecificState,
209 V: Into<Variant<'m, 'v>>,
210{
211 fn extend<T: IntoIterator<Item = V>>(&mut self, iter: T) {
212 for v in iter {
213 self.append_value(v);
214 }
215 }
216}
217
218#[derive(Debug)]
220pub struct ListState<'a> {
221 offsets: &'a mut Vec<usize>,
222 saved_offsets_size: usize,
223}
224
225impl BuilderSpecificState for ListState<'_> {
227 fn rollback(&mut self) {
228 self.offsets.truncate(self.saved_offsets_size);
229 }
230}
231
232impl<'a> ParentState<'a, ListState<'a>> {
233 pub fn list(
237 value_builder: &'a mut ValueBuilder,
238 metadata_builder: &'a mut dyn MetadataBuilder,
239 offsets: &'a mut Vec<usize>,
240 saved_parent_value_builder_offset: usize,
241 ) -> Self {
242 let saved_value_builder_offset = value_builder.offset();
246 let saved_offsets_size = offsets.len();
247 offsets.push(saved_value_builder_offset - saved_parent_value_builder_offset);
248
249 let builder_state = ListState {
250 offsets,
251 saved_offsets_size,
252 };
253 Self {
254 saved_metadata_builder_dict_size: metadata_builder.num_field_names(),
255 saved_value_builder_offset,
256 metadata_builder,
257 value_builder,
258 builder_state,
259 finished: false,
260 }
261 }
262}
263
264#[cfg(test)]
265mod tests {
266 use crate::{
267 ShortString, ValueBuilder, VariantBuilder, VariantMetadata,
268 builder::metadata::ReadOnlyMetadataBuilder,
269 };
270
271 use super::*;
272
273 #[test]
274 fn test_list() {
275 let mut builder = VariantBuilder::new();
276
277 builder
278 .new_list()
279 .with_value(1i8)
280 .with_value(2i8)
281 .with_value("test")
282 .finish();
283
284 let (metadata, value) = builder.finish();
285 assert!(!metadata.is_empty());
286 assert!(!value.is_empty());
287
288 let variant = Variant::try_new(&metadata, &value).unwrap();
289
290 match variant {
291 Variant::List(list) => {
292 let val0 = list.get(0).unwrap();
293 assert_eq!(val0, Variant::Int8(1));
294
295 let val1 = list.get(1).unwrap();
296 assert_eq!(val1, Variant::Int8(2));
297
298 let val2 = list.get(2).unwrap();
299 assert_eq!(val2, Variant::ShortString(ShortString("test")));
300 }
301 _ => panic!("Expected an array variant, got: {variant:?}"),
302 }
303 }
304
305 #[test]
306 fn test_nested_list() {
307 let mut builder = VariantBuilder::new();
308
309 let mut outer_list_builder = builder.new_list();
310
311 outer_list_builder
313 .new_list()
314 .with_value("a")
315 .with_value("b")
316 .with_value("c")
317 .with_value("d")
318 .finish();
319
320 outer_list_builder.finish();
321
322 let (metadata, value) = builder.finish();
323
324 let variant = Variant::try_new(&metadata, &value).unwrap();
325 let outer_list = variant.as_list().unwrap();
326
327 assert_eq!(outer_list.len(), 1);
328
329 let inner_variant = outer_list.get(0).unwrap();
330 let inner_list = inner_variant.as_list().unwrap();
331
332 assert_eq!(
333 vec![
334 Variant::from("a"),
335 Variant::from("b"),
336 Variant::from("c"),
337 Variant::from("d"),
338 ],
339 inner_list.iter().collect::<Vec<_>>()
340 );
341 }
342
343 #[test]
344 fn test_super_nested_list() {
345 let mut builder = VariantBuilder::new();
350 {
351 let mut list_builder1 = builder.new_list();
352 {
353 let mut list_builder2 = list_builder1.new_list();
354 {
355 let mut list_builder3 = list_builder2.new_list();
356 {
357 let mut list_builder4 = list_builder3.new_list();
358 {
359 let mut list_builder5 = list_builder4.new_list();
360 list_builder5.append_value(1);
361 list_builder5.finish();
362 }
363 list_builder4.finish();
364 }
365 list_builder3.finish();
366 }
367 list_builder2.finish();
368 }
369 list_builder1.finish();
370 }
371
372 let (metadata, value) = builder.finish();
373
374 let variant = Variant::try_new(&metadata, &value).unwrap();
375 let list1 = variant.as_list().unwrap();
376 assert_eq!(list1.len(), 1);
377
378 let list2_variant = list1.get(0).unwrap();
379 let list2 = list2_variant.as_list().unwrap();
380 assert_eq!(list2.len(), 1);
381
382 let list3_variant = list2.get(0).unwrap();
383 let list3 = list3_variant.as_list().unwrap();
384 assert_eq!(list3.len(), 1);
385
386 let list4_variant = list3.get(0).unwrap();
387 let list4 = list4_variant.as_list().unwrap();
388 assert_eq!(list4.len(), 1);
389
390 let list5_variant = list4.get(0).unwrap();
391 let list5 = list5_variant.as_list().unwrap();
392 assert_eq!(list5.len(), 1);
393
394 assert_eq!(list5.len(), 1);
395
396 assert_eq!(list5.get(0).unwrap(), Variant::from(1));
397 }
398
399 #[test]
400 fn test_list_append_bytes_subset() {
401 let mut builder = VariantBuilder::new();
403 {
404 let mut list = builder.new_list();
405 list.append_value("item1");
406 list.append_value(42i32);
407 list.append_value(true);
408 list.append_value("item4");
409 list.append_value(1.234f64);
410 list.finish();
411 }
412 let (metadata1, value1) = builder.finish();
413 let original_variant = Variant::try_new(&metadata1, &value1).unwrap();
414 let original_list = original_variant.as_list().unwrap();
415
416 let metadata2 = VariantMetadata::new(&metadata1);
418 let mut metadata2 = ReadOnlyMetadataBuilder::new(&metadata2);
419 let mut builder2 = ValueBuilder::new();
420 let state = ParentState::variant(&mut builder2, &mut metadata2);
421 {
422 let mut list = ListBuilder::new(state, true);
423
424 list.append_value_bytes(original_list.get(0).unwrap());
426
427 list.append_value("new_item");
429
430 list.append_value_bytes(original_list.get(2).unwrap());
432
433 list.append_value(99i32);
435
436 list.append_value_bytes(original_list.get(4).unwrap());
438
439 list.finish();
440 }
441 let value2 = builder2.into_inner();
442 let result_variant = Variant::try_new(&metadata1, &value2).unwrap();
443 let result_list = result_variant.as_list().unwrap();
444
445 assert_eq!(result_list.len(), 5);
447 assert_eq!(result_list.get(0).unwrap().as_string().unwrap(), "item1");
448 assert_eq!(result_list.get(1).unwrap().as_string().unwrap(), "new_item");
449 assert!(result_list.get(2).unwrap().as_boolean().unwrap());
450 assert_eq!(result_list.get(3).unwrap().as_int32().unwrap(), 99);
451 assert_eq!(result_list.get(4).unwrap().as_f64().unwrap(), 1.234);
452 }
453
454 #[test]
455 fn test_append_list() {
456 let (m1, v1) = make_list();
457 let variant = Variant::new(&m1, &v1);
458 let mut builder = VariantBuilder::new();
459 builder.append_value(variant.clone());
460 let (metadata, value) = builder.finish();
461 assert_eq!(variant, Variant::new(&metadata, &value));
462 }
463
464 fn make_list() -> (Vec<u8>, Vec<u8>) {
466 let mut builder = VariantBuilder::new();
467
468 builder
469 .new_list()
470 .with_value(1234)
471 .with_value("a string value")
472 .finish();
473
474 builder.finish()
475 }
476
477 #[test]
478 fn test_append_nested_list() {
479 let (m1, v1) = make_nested_list();
480 let variant = Variant::new(&m1, &v1);
481 let mut builder = VariantBuilder::new();
482 builder.append_value(variant.clone());
483 let (metadata, value) = builder.finish();
484 assert_eq!(variant, Variant::new(&metadata, &value));
485 }
486
487 fn make_nested_list() -> (Vec<u8>, Vec<u8>) {
488 let mut builder = VariantBuilder::new();
489 let mut list = builder.new_list();
490
491 list.new_list()
493 .with_value("the dog licked the oil")
494 .with_value(4.3)
495 .finish();
496
497 list.finish();
498
499 builder.finish()
500 }
501
502 #[test]
503 fn test_object_list() {
504 let mut builder = VariantBuilder::new();
505
506 let mut list_builder = builder.new_list();
507
508 list_builder
509 .new_object()
510 .with_field("id", 1)
511 .with_field("type", "Cauliflower")
512 .finish();
513
514 list_builder
515 .new_object()
516 .with_field("id", 2)
517 .with_field("type", "Beets")
518 .finish();
519
520 list_builder.finish();
521
522 let (metadata, value) = builder.finish();
523
524 let variant = Variant::try_new(&metadata, &value).unwrap();
525 let list = variant.as_list().unwrap();
526
527 assert_eq!(list.len(), 2);
528
529 let obj1_variant = list.get(0).unwrap();
530 let obj1 = obj1_variant.as_object().unwrap();
531
532 assert_eq!(
533 vec![
534 ("id", Variant::from(1)),
535 ("type", Variant::from("Cauliflower")),
536 ],
537 obj1.iter().collect::<Vec<_>>()
538 );
539
540 let obj2_variant = list.get(1).unwrap();
541 let obj2 = obj2_variant.as_object().unwrap();
542
543 assert_eq!(
544 vec![("id", Variant::from(2)), ("type", Variant::from("Beets")),],
545 obj2.iter().collect::<Vec<_>>()
546 );
547 }
548
549 #[test]
550 fn test_object_list2() {
551 let mut builder = VariantBuilder::new();
552
553 let mut list_builder = builder.new_list();
554
555 list_builder.new_object().with_field("a", 1).finish();
556
557 list_builder.new_object().with_field("b", 2).finish();
558
559 list_builder.finish();
560
561 let (metadata, value) = builder.finish();
562
563 let variant = Variant::try_new(&metadata, &value).unwrap();
564 let list = variant.as_list().unwrap();
565 assert_eq!(list.len(), 2);
566
567 let obj1_variant = list.get(0).unwrap();
568 let obj1 = obj1_variant.as_object().unwrap();
569 assert_eq!(
570 vec![("a", Variant::from(1)),],
571 obj1.iter().collect::<Vec<_>>()
572 );
573
574 let obj2_variant = list.get(1).unwrap();
575 let obj2 = obj2_variant.as_object().unwrap();
576 assert_eq!(
577 vec![("b", Variant::from(2)),],
578 obj2.iter().collect::<Vec<_>>()
579 );
580 }
581
582 #[test]
583 fn test_hetergenous_list() {
584 let mut builder = VariantBuilder::new();
595
596 let mut list_builder = builder.new_list();
597
598 list_builder.append_value(1);
599
600 {
601 let mut object_builder = list_builder.new_object();
602 object_builder.insert("a", 1);
603 object_builder.finish();
604 }
605
606 list_builder.append_value(2);
607
608 {
609 let mut object_builder = list_builder.new_object();
610 object_builder.insert("b", 2);
611 object_builder.finish();
612 }
613
614 list_builder.append_value(3);
615
616 list_builder.finish();
617
618 let (metadata, value) = builder.finish();
619
620 let variant = Variant::try_new(&metadata, &value).unwrap();
621 let list = variant.as_list().unwrap();
622 assert_eq!(list.len(), 5);
623 assert_eq!(list.get(0).unwrap(), Variant::from(1));
624
625 let obj1_variant = list.get(1).unwrap();
626 let obj1 = obj1_variant.as_object().unwrap();
627 assert_eq!(
628 vec![("a", Variant::from(1)),],
629 obj1.iter().collect::<Vec<_>>()
630 );
631
632 assert_eq!(list.get(2).unwrap(), Variant::from(2));
633
634 let obj2_variant = list.get(3).unwrap();
635 let obj2 = obj2_variant.as_object().unwrap();
636 assert_eq!(
637 vec![("b", Variant::from(2)),],
638 obj2.iter().collect::<Vec<_>>()
639 );
640
641 assert_eq!(list.get(4).unwrap(), Variant::from(3));
642 }
643
644 #[test]
648 fn test_nested_list_with_heterogeneous_fields_for_buffer_reuse() {
649 let mut builder = VariantBuilder::new();
650
651 {
652 let mut outer_list_builder = builder.new_list();
653
654 outer_list_builder.append_value("apple");
655 outer_list_builder.append_value(false);
656
657 {
658 let mut inner_list_builder = outer_list_builder.new_list();
660
661 {
662 let mut inner_object_builder = inner_list_builder.new_object();
663 inner_object_builder.insert("a", "b");
664 inner_object_builder.insert("b", "c");
665 inner_object_builder.finish();
666 }
667
668 {
669 let mut inner_object_builder = inner_list_builder.new_object();
672 inner_object_builder.insert("c", "d");
673 inner_object_builder.insert("d", "e");
674 inner_object_builder.finish();
675 }
676
677 inner_list_builder.finish();
678 }
679
680 {
681 let mut inner_list_builder = outer_list_builder.new_list();
683
684 {
685 let mut double_inner_list_builder = inner_list_builder.new_list();
686 double_inner_list_builder.append_value(1);
687 double_inner_list_builder.append_value(true);
688
689 double_inner_list_builder.finish();
690 }
691
692 {
693 let mut double_inner_list_builder = inner_list_builder.new_list();
694 double_inner_list_builder.append_value("tree");
695 double_inner_list_builder.append_value(false);
696
697 double_inner_list_builder.finish();
698 }
699 inner_list_builder.finish();
700 }
701
702 outer_list_builder.append_value(1);
703
704 outer_list_builder.finish();
705 }
706
707 let (metadata, value) = builder.finish();
708
709 let variant = Variant::try_new(&metadata, &value).unwrap();
710 let outer_list = variant.as_list().unwrap();
711
712 assert_eq!(5, outer_list.len());
713
714 assert_eq!(Variant::from("apple"), outer_list.get(0).unwrap());
716 assert_eq!(Variant::from(false), outer_list.get(1).unwrap());
717 assert_eq!(Variant::from(1), outer_list.get(4).unwrap());
718
719 let list1_variant = outer_list.get(2).unwrap();
721 let list1 = list1_variant.as_list().unwrap();
722 assert_eq!(2, list1.len());
723
724 let list1_obj1_variant = list1.get(0).unwrap();
725 let list1_obj1 = list1_obj1_variant.as_object().unwrap();
726 assert_eq!("a", list1_obj1.field_name(0).unwrap());
727 assert_eq!(Variant::from("b"), list1_obj1.field(0).unwrap());
728
729 assert_eq!("b", list1_obj1.field_name(1).unwrap());
730 assert_eq!(Variant::from("c"), list1_obj1.field(1).unwrap());
731
732 let list2_variant = outer_list.get(3).unwrap();
734 let list2 = list2_variant.as_list().unwrap();
735 assert_eq!(2, list2.len());
736
737 let list2_list1_variant = list2.get(0).unwrap();
739 let list2_list1 = list2_list1_variant.as_list().unwrap();
740 assert_eq!(2, list2_list1.len());
741 assert_eq!(Variant::from(1), list2_list1.get(0).unwrap());
742 assert_eq!(Variant::from(true), list2_list1.get(1).unwrap());
743
744 let list2_list2_variant = list2.get(1).unwrap();
746 let list2_list2 = list2_list2_variant.as_list().unwrap();
747 assert_eq!(2, list2_list2.len());
748 assert_eq!(Variant::from("tree"), list2_list2.get(0).unwrap());
749 assert_eq!(Variant::from(false), list2_list2.get(1).unwrap());
750 }
751}