risingwave_common/array/
list_array.rs

1// Copyright 2025 RisingWave Labs
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7//     http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15use std::borrow::Cow;
16use std::cmp::Ordering;
17use std::fmt::{self, Debug, Display};
18use std::future::Future;
19use std::mem::size_of;
20
21use bytes::{Buf, BufMut};
22use itertools::Itertools;
23use risingwave_common_estimate_size::EstimateSize;
24use risingwave_pb::data::{ListArrayData, PbArray, PbArrayType};
25use serde::{Deserialize, Serializer};
26use thiserror_ext::AsReport;
27
28use super::{
29    Array, ArrayBuilder, ArrayBuilderImpl, ArrayImpl, ArrayResult, BoolArray, PrimitiveArray,
30    PrimitiveArrayItemType, RowRef, Utf8Array,
31};
32use crate::bitmap::{Bitmap, BitmapBuilder};
33use crate::row::Row;
34use crate::types::{
35    DataType, Datum, DatumRef, DefaultOrd, Scalar, ScalarImpl, ScalarRefImpl, ToDatumRef, ToText,
36    hash_datum,
37};
38use crate::util::memcmp_encoding;
39use crate::util::value_encoding::estimate_serialize_datum_size;
40
41#[derive(Debug, Clone, EstimateSize)]
42pub struct ListArrayBuilder {
43    bitmap: BitmapBuilder,
44    offsets: Vec<u32>,
45    value: Box<ArrayBuilderImpl>,
46}
47
48impl ArrayBuilder for ListArrayBuilder {
49    type ArrayType = ListArray;
50
51    #[cfg(not(test))]
52    fn new(_capacity: usize) -> Self {
53        panic!("please use `ListArrayBuilder::with_type` instead");
54    }
55
56    #[cfg(test)]
57    fn new(capacity: usize) -> Self {
58        // TODO: deprecate this
59        Self::with_type(
60            capacity,
61            // Default datatype
62            DataType::List(Box::new(DataType::Int16)),
63        )
64    }
65
66    fn with_type(capacity: usize, ty: DataType) -> Self {
67        let DataType::List(value_type) = ty else {
68            panic!("data type must be DataType::List");
69        };
70        let mut offsets = Vec::with_capacity(capacity + 1);
71        offsets.push(0);
72        Self {
73            bitmap: BitmapBuilder::with_capacity(capacity),
74            offsets,
75            value: Box::new(value_type.create_array_builder(capacity)),
76        }
77    }
78
79    fn append_n(&mut self, n: usize, value: Option<ListRef<'_>>) {
80        match value {
81            None => {
82                self.bitmap.append_n(n, false);
83                let last = *self.offsets.last().unwrap();
84                for _ in 0..n {
85                    self.offsets.push(last);
86                }
87            }
88            Some(v) => {
89                self.bitmap.append_n(n, true);
90                for _ in 0..n {
91                    let last = *self.offsets.last().unwrap();
92                    let elems = v.iter();
93                    self.offsets.push(
94                        last.checked_add(elems.len() as u32)
95                            .expect("offset overflow"),
96                    );
97                    for elem in elems {
98                        self.value.append(elem);
99                    }
100                }
101            }
102        }
103    }
104
105    fn append_array(&mut self, other: &ListArray) {
106        self.bitmap.append_bitmap(&other.bitmap);
107        let last = *self.offsets.last().unwrap();
108        self.offsets
109            .append(&mut other.offsets[1..].iter().map(|o| *o + last).collect());
110        self.value.append_array(&other.value);
111    }
112
113    fn pop(&mut self) -> Option<()> {
114        self.bitmap.pop()?;
115        let start = self.offsets.pop().unwrap();
116        let end = *self.offsets.last().unwrap();
117        for _ in end..start {
118            self.value.pop().unwrap();
119        }
120        Some(())
121    }
122
123    fn len(&self) -> usize {
124        self.bitmap.len()
125    }
126
127    fn finish(self) -> ListArray {
128        ListArray {
129            bitmap: self.bitmap.finish(),
130            offsets: self.offsets.into(),
131            value: Box::new(self.value.finish()),
132        }
133    }
134}
135
136impl ListArrayBuilder {
137    pub fn append_row_ref(&mut self, row: RowRef<'_>) {
138        self.bitmap.append(true);
139        let last = *self.offsets.last().unwrap();
140        self.offsets
141            .push(last.checked_add(row.len() as u32).expect("offset overflow"));
142        for v in row.iter() {
143            self.value.append(v);
144        }
145    }
146}
147
148/// Each item of this `ListArray` is a `List<T>`, or called `T[]` (T array).
149///
150/// * As other arrays, there is a null bitmap, with `1` meaning nonnull and `0` meaning null.
151/// * As [`super::BytesArray`], there is an offsets `Vec` and a value `Array`. The value `Array` has
152///   all items concatenated, and the offsets `Vec` stores start and end indices into it for
153///   slicing. Effectively, the inner array is the flattened form, and `offsets.len() == n + 1`.
154///
155/// For example, `values (array[1]), (array[]::int[]), (null), (array[2, 3]);` stores an inner
156///  `I32Array` with `[1, 2, 3]`, along with offsets `[0, 1, 1, 1, 3]` and null bitmap `TTFT`.
157#[derive(Debug, Clone, PartialEq, Eq)]
158pub struct ListArray {
159    pub(super) bitmap: Bitmap,
160    pub(super) offsets: Box<[u32]>,
161    pub(super) value: Box<ArrayImpl>,
162}
163
164impl EstimateSize for ListArray {
165    fn estimated_heap_size(&self) -> usize {
166        self.bitmap.estimated_heap_size()
167            + self.offsets.len() * size_of::<u32>()
168            + self.value.estimated_size()
169    }
170}
171
172impl Array for ListArray {
173    type Builder = ListArrayBuilder;
174    type OwnedItem = ListValue;
175    type RefItem<'a> = ListRef<'a>;
176
177    unsafe fn raw_value_at_unchecked(&self, idx: usize) -> Self::RefItem<'_> {
178        unsafe {
179            ListRef {
180                array: &self.value,
181                start: *self.offsets.get_unchecked(idx),
182                end: *self.offsets.get_unchecked(idx + 1),
183            }
184        }
185    }
186
187    fn len(&self) -> usize {
188        self.bitmap.len()
189    }
190
191    fn to_protobuf(&self) -> PbArray {
192        let value = self.value.to_protobuf();
193        PbArray {
194            array_type: PbArrayType::List as i32,
195            struct_array_data: None,
196            list_array_data: Some(Box::new(ListArrayData {
197                offsets: self.offsets.to_vec(),
198                value: Some(Box::new(value)),
199                value_type: Some(self.value.data_type().to_protobuf()),
200                elem_size: None,
201            })),
202            null_bitmap: Some(self.bitmap.to_protobuf()),
203            values: vec![],
204        }
205    }
206
207    fn null_bitmap(&self) -> &Bitmap {
208        &self.bitmap
209    }
210
211    fn into_null_bitmap(self) -> Bitmap {
212        self.bitmap
213    }
214
215    fn set_bitmap(&mut self, bitmap: Bitmap) {
216        self.bitmap = bitmap;
217    }
218
219    fn data_type(&self) -> DataType {
220        DataType::List(Box::new(self.value.data_type()))
221    }
222}
223
224impl ListArray {
225    /// Flatten the list array into a single array.
226    ///
227    /// # Example
228    ///
229    /// ```text
230    /// [[1,2,3],NULL,[4,5]] => [1,2,3,4,5]
231    /// [[[1],[2]],[[3],[4]]] => [1,2,3,4]
232    /// ```
233    pub fn flatten(&self) -> ArrayImpl {
234        match &*self.value {
235            ArrayImpl::List(inner) => inner.flatten(),
236            a => a.clone(),
237        }
238    }
239
240    /// Return the inner array of the list array.
241    pub fn values(&self) -> &ArrayImpl {
242        &self.value
243    }
244
245    pub fn from_protobuf(array: &PbArray) -> ArrayResult<ArrayImpl> {
246        ensure!(
247            array.values.is_empty(),
248            "Must have no buffer in a list array"
249        );
250        debug_assert!(
251            (array.array_type == PbArrayType::List as i32)
252                || (array.array_type == PbArrayType::Map as i32)
253                || (array.array_type == PbArrayType::Vector as i32),
254            "invalid array type for list: {}",
255            array.array_type
256        );
257        let bitmap: Bitmap = array.get_null_bitmap()?.into();
258        let array_data = array.get_list_array_data()?.to_owned();
259        let flatten_len = match array_data.offsets.last() {
260            Some(&n) => n as usize,
261            None => bail!("Must have at least one element in offsets"),
262        };
263        let value = ArrayImpl::from_protobuf(array_data.value.as_ref().unwrap(), flatten_len)?;
264        let arr = ListArray {
265            bitmap,
266            offsets: array_data.offsets.into(),
267            value: Box::new(value),
268        };
269        Ok(arr.into())
270    }
271
272    /// Apply the function on the underlying elements.
273    /// e.g. `map_inner([[1,2,3],NULL,[4,5]], DOUBLE) = [[2,4,6],NULL,[8,10]]`
274    pub async fn map_inner<E, Fut, F>(self, f: F) -> std::result::Result<ListArray, E>
275    where
276        F: FnOnce(ArrayImpl) -> Fut,
277        Fut: Future<Output = std::result::Result<ArrayImpl, E>>,
278    {
279        let new_value = (f)(*self.value).await?;
280
281        Ok(Self {
282            offsets: self.offsets,
283            bitmap: self.bitmap,
284            value: Box::new(new_value),
285        })
286    }
287
288    /// Returns the offsets of this list.
289    ///
290    /// # Example
291    /// ```text
292    /// list    = [[a, b, c], [], NULL, [d], [NULL, f]]
293    /// offsets = [0, 3, 3, 3, 4, 6]
294    /// ```
295    pub fn offsets(&self) -> &[u32] {
296        &self.offsets
297    }
298}
299
300impl<T, L> FromIterator<Option<L>> for ListArray
301where
302    T: PrimitiveArrayItemType,
303    L: IntoIterator<Item = T>,
304{
305    fn from_iter<I: IntoIterator<Item = Option<L>>>(iter: I) -> Self {
306        let iter = iter.into_iter();
307        let mut builder = ListArrayBuilder::with_type(
308            iter.size_hint().0,
309            DataType::List(Box::new(T::DATA_TYPE.clone())),
310        );
311        for v in iter {
312            match v {
313                None => builder.append(None),
314                Some(v) => {
315                    builder.append(Some(v.into_iter().collect::<ListValue>().as_scalar_ref()))
316                }
317            }
318        }
319        builder.finish()
320    }
321}
322
323impl FromIterator<ListValue> for ListArray {
324    fn from_iter<I: IntoIterator<Item = ListValue>>(iter: I) -> Self {
325        let mut iter = iter.into_iter();
326        let first = iter.next().expect("empty iterator");
327        let mut builder = ListArrayBuilder::with_type(
328            iter.size_hint().0,
329            DataType::List(Box::new(first.data_type())),
330        );
331        builder.append(Some(first.as_scalar_ref()));
332        for v in iter {
333            builder.append(Some(v.as_scalar_ref()));
334        }
335        builder.finish()
336    }
337}
338
339#[derive(Clone, PartialEq, Eq, EstimateSize)]
340pub struct ListValue {
341    values: Box<ArrayImpl>,
342}
343
344impl Debug for ListValue {
345    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
346        self.as_scalar_ref().fmt(f)
347    }
348}
349
350impl Display for ListValue {
351    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
352        self.as_scalar_ref().write(f)
353    }
354}
355
356impl ListValue {
357    pub fn new(values: ArrayImpl) -> Self {
358        Self {
359            values: Box::new(values),
360        }
361    }
362
363    pub fn into_array(self) -> ArrayImpl {
364        *self.values
365    }
366
367    pub fn empty(datatype: &DataType) -> Self {
368        Self::new(datatype.create_array_builder(0).finish())
369    }
370
371    /// Creates a new `ListValue` from an iterator of `Datum`.
372    pub fn from_datum_iter<T: ToDatumRef>(
373        elem_datatype: &DataType,
374        iter: impl IntoIterator<Item = T>,
375    ) -> Self {
376        let iter = iter.into_iter();
377        let mut builder = elem_datatype.create_array_builder(iter.size_hint().0);
378        for datum in iter {
379            builder.append(datum);
380        }
381        Self::new(builder.finish())
382    }
383
384    /// Returns the length of the list.
385    pub fn len(&self) -> usize {
386        self.values.len()
387    }
388
389    /// Returns `true` if the list has a length of 0.
390    pub fn is_empty(&self) -> bool {
391        self.values.is_empty()
392    }
393
394    /// Iterates over the elements of the list.
395    pub fn iter(&self) -> impl DoubleEndedIterator + ExactSizeIterator<Item = DatumRef<'_>> {
396        self.values.iter()
397    }
398
399    /// Get the element at the given index. Returns `None` if the index is out of bounds.
400    pub fn get(&self, index: usize) -> Option<DatumRef<'_>> {
401        if index < self.len() {
402            Some(self.values.value_at(index))
403        } else {
404            None
405        }
406    }
407
408    /// Returns the data type of the elements in the list.
409    pub fn data_type(&self) -> DataType {
410        self.values.data_type()
411    }
412
413    pub fn memcmp_deserialize(
414        item_datatype: &DataType,
415        deserializer: &mut memcomparable::Deserializer<impl Buf>,
416    ) -> memcomparable::Result<Self> {
417        let bytes = serde_bytes::ByteBuf::deserialize(deserializer)?;
418        let mut inner_deserializer = memcomparable::Deserializer::new(bytes.as_slice());
419        let mut builder = item_datatype.create_array_builder(0);
420        while inner_deserializer.has_remaining() {
421            builder.append(memcmp_encoding::deserialize_datum_in_composite(
422                item_datatype,
423                &mut inner_deserializer,
424            )?)
425        }
426        Ok(Self::new(builder.finish()))
427    }
428
429    // Used to display ListValue in explain for better readibilty.
430    pub fn display_for_explain(&self) -> String {
431        // Example of ListValue display: ARRAY[1, 2, null]
432        format!(
433            "ARRAY[{}]",
434            self.iter()
435                .map(|v| {
436                    match v.as_ref() {
437                        None => "null".into(),
438                        Some(scalar) => scalar.to_text(),
439                    }
440                })
441                .format(", ")
442        )
443    }
444
445    /// Returns a mutable slice if the list is of type `int64[]`.
446    pub fn as_i64_mut_slice(&mut self) -> Option<&mut [i64]> {
447        match self.values.as_mut() {
448            ArrayImpl::Int64(array) => Some(array.as_mut_slice()),
449            _ => None,
450        }
451    }
452}
453
454impl PartialOrd for ListValue {
455    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
456        Some(self.cmp(other))
457    }
458}
459
460impl Ord for ListValue {
461    fn cmp(&self, other: &Self) -> Ordering {
462        self.as_scalar_ref().cmp(&other.as_scalar_ref())
463    }
464}
465
466impl<T: PrimitiveArrayItemType> FromIterator<Option<T>> for ListValue {
467    fn from_iter<I: IntoIterator<Item = Option<T>>>(iter: I) -> Self {
468        Self::new(iter.into_iter().collect::<PrimitiveArray<T>>().into())
469    }
470}
471
472impl<T: PrimitiveArrayItemType> FromIterator<T> for ListValue {
473    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
474        Self::new(iter.into_iter().collect::<PrimitiveArray<T>>().into())
475    }
476}
477
478impl FromIterator<bool> for ListValue {
479    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
480        Self::new(iter.into_iter().collect::<BoolArray>().into())
481    }
482}
483
484impl<'a> FromIterator<Option<&'a str>> for ListValue {
485    fn from_iter<I: IntoIterator<Item = Option<&'a str>>>(iter: I) -> Self {
486        Self::new(iter.into_iter().collect::<Utf8Array>().into())
487    }
488}
489
490impl<'a> FromIterator<&'a str> for ListValue {
491    fn from_iter<I: IntoIterator<Item = &'a str>>(iter: I) -> Self {
492        Self::new(iter.into_iter().collect::<Utf8Array>().into())
493    }
494}
495
496impl FromIterator<ListValue> for ListValue {
497    fn from_iter<I: IntoIterator<Item = ListValue>>(iter: I) -> Self {
498        Self::new(iter.into_iter().collect::<ListArray>().into())
499    }
500}
501
502impl From<ListValue> for ArrayImpl {
503    fn from(value: ListValue) -> Self {
504        *value.values
505    }
506}
507
508/// A slice of an array
509#[derive(Copy, Clone)]
510pub struct ListRef<'a> {
511    array: &'a ArrayImpl,
512    start: u32,
513    end: u32,
514}
515
516impl<'a> ListRef<'a> {
517    /// Returns the length of the list.
518    pub fn len(&self) -> usize {
519        (self.end - self.start) as usize
520    }
521
522    /// Returns `true` if the list has a length of 0.
523    pub fn is_empty(&self) -> bool {
524        self.start == self.end
525    }
526
527    /// Returns the data type of the elements in the list.
528    pub fn data_type(&self) -> DataType {
529        self.array.data_type()
530    }
531
532    /// Returns the elements in the flattened list.
533    pub fn flatten(self) -> ListRef<'a> {
534        match self.array {
535            ArrayImpl::List(inner) => ListRef {
536                array: &inner.value,
537                start: inner.offsets[self.start as usize],
538                end: inner.offsets[self.end as usize],
539            }
540            .flatten(),
541            _ => self,
542        }
543    }
544
545    /// Iterates over the elements of the list.
546    pub fn iter(self) -> impl DoubleEndedIterator + ExactSizeIterator<Item = DatumRef<'a>> + 'a {
547        (self.start..self.end).map(|i| self.array.value_at(i as usize))
548    }
549
550    /// Get the element at the given index. Returns `None` if the index is out of bounds.
551    pub fn get(self, index: usize) -> Option<DatumRef<'a>> {
552        if index < self.len() {
553            Some(self.array.value_at(self.start as usize + index))
554        } else {
555            None
556        }
557    }
558
559    pub fn memcmp_serialize(
560        self,
561        serializer: &mut memcomparable::Serializer<impl BufMut>,
562    ) -> memcomparable::Result<()> {
563        let mut inner_serializer = memcomparable::Serializer::new(vec![]);
564        for datum_ref in self.iter() {
565            memcmp_encoding::serialize_datum_in_composite(datum_ref, &mut inner_serializer)?
566        }
567        serializer.serialize_bytes(&inner_serializer.into_inner())
568    }
569
570    pub fn hash_scalar_inner<H: std::hash::Hasher>(self, state: &mut H) {
571        for datum_ref in self.iter() {
572            hash_datum(datum_ref, state);
573        }
574    }
575
576    /// estimate the serialized size with value encoding
577    pub fn estimate_serialize_size_inner(self) -> usize {
578        self.iter().map(estimate_serialize_datum_size).sum()
579    }
580
581    pub fn to_owned(self) -> ListValue {
582        let mut builder = self.array.create_builder(self.len());
583        for datum_ref in self.iter() {
584            builder.append(datum_ref);
585        }
586        ListValue::new(builder.finish())
587    }
588
589    pub fn as_primitive_slice<T: PrimitiveArrayItemType>(self) -> Option<&'a [T]> {
590        T::try_into_array_ref(self.array)
591            .map(|prim_arr| &prim_arr.as_slice()[self.start as usize..self.end as usize])
592    }
593
594    /// Returns a slice if the list is of type `int64[]`.
595    pub fn as_i64_slice(&self) -> Option<&[i64]> {
596        self.as_primitive_slice()
597    }
598
599    /// # Panics
600    /// Panics if the list is not a map's internal representation (See [`super::MapArray`]).
601    pub(super) fn as_map_kv(self) -> (ListRef<'a>, ListRef<'a>) {
602        let (k, v) = self.array.as_struct().fields().collect_tuple().unwrap();
603        (
604            ListRef {
605                array: k,
606                start: self.start,
607                end: self.end,
608            },
609            ListRef {
610                array: v,
611                start: self.start,
612                end: self.end,
613            },
614        )
615    }
616}
617
618impl PartialEq for ListRef<'_> {
619    fn eq(&self, other: &Self) -> bool {
620        self.iter().eq(other.iter())
621    }
622}
623
624impl Eq for ListRef<'_> {}
625
626impl PartialOrd for ListRef<'_> {
627    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
628        Some(self.cmp(other))
629    }
630}
631
632impl Ord for ListRef<'_> {
633    fn cmp(&self, other: &Self) -> Ordering {
634        self.iter().cmp_by(other.iter(), |a, b| a.default_cmp(&b))
635    }
636}
637
638impl Debug for ListRef<'_> {
639    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
640        f.debug_list().entries(self.iter()).finish()
641    }
642}
643
644impl Row for ListRef<'_> {
645    fn datum_at(&self, index: usize) -> DatumRef<'_> {
646        self.array.value_at(self.start as usize + index)
647    }
648
649    unsafe fn datum_at_unchecked(&self, index: usize) -> DatumRef<'_> {
650        unsafe { self.array.value_at_unchecked(self.start as usize + index) }
651    }
652
653    fn len(&self) -> usize {
654        self.len()
655    }
656
657    fn iter(&self) -> impl Iterator<Item = DatumRef<'_>> {
658        (*self).iter()
659    }
660}
661
662impl ToText for ListRef<'_> {
663    // This function will be invoked when pgwire prints a list value in string.
664    // Refer to PostgreSQL `array_out` or `appendPGArray`.
665    fn write<W: std::fmt::Write>(&self, f: &mut W) -> std::fmt::Result {
666        write!(
667            f,
668            "{{{}}}",
669            self.iter().format_with(",", |datum_ref, f| {
670                let s = datum_ref.to_text();
671                // Never quote null or inner list, but quote empty, verbatim 'null', special
672                // chars and whitespaces.
673                let need_quote = !matches!(datum_ref, None | Some(ScalarRefImpl::List(_)))
674                    && (s.is_empty()
675                        || s.eq_ignore_ascii_case("null")
676                        || s.contains([
677                            '"', '\\', ',',
678                            // whilespace:
679                            // PostgreSQL `array_isspace` includes '\x0B' but rust
680                            // [`char::is_ascii_whitespace`] does not.
681                            ' ', '\t', '\n', '\r', '\x0B', '\x0C', // list-specific:
682                            '{', '}',
683                        ]));
684                if need_quote {
685                    f(&"\"")?;
686                    s.chars().try_for_each(|c| {
687                        if c == '"' || c == '\\' {
688                            f(&"\\")?;
689                        }
690                        f(&c)
691                    })?;
692                    f(&"\"")
693                } else {
694                    f(&s)
695                }
696            })
697        )
698    }
699
700    fn write_with_type<W: std::fmt::Write>(&self, ty: &DataType, f: &mut W) -> std::fmt::Result {
701        match ty {
702            DataType::List { .. } => self.write(f),
703            _ => unreachable!(),
704        }
705    }
706}
707
708impl<'a> From<&'a ListValue> for ListRef<'a> {
709    fn from(value: &'a ListValue) -> Self {
710        ListRef {
711            array: &value.values,
712            start: 0,
713            end: value.len() as u32,
714        }
715    }
716}
717
718impl From<ListRef<'_>> for ListValue {
719    fn from(value: ListRef<'_>) -> Self {
720        value.to_owned()
721    }
722}
723
724impl ListValue {
725    /// Construct an array from literal string.
726    pub fn from_str(input: &str, data_type: &DataType) -> Result<Self, String> {
727        struct Parser<'a> {
728            input: &'a str,
729            data_type: &'a DataType,
730        }
731
732        impl Parser<'_> {
733            /// Parse a datum.
734            fn parse(&mut self) -> Result<Datum, String> {
735                self.skip_whitespace();
736                if self.data_type.is_array() {
737                    if self.try_parse_null() {
738                        return Ok(None);
739                    }
740                    Ok(Some(self.parse_array()?.into()))
741                } else {
742                    self.parse_value()
743                }
744            }
745
746            /// Parse an array.
747            fn parse_array(&mut self) -> Result<ListValue, String> {
748                self.skip_whitespace();
749                if !self.try_consume('{') {
750                    return Err("Array value must start with \"{\"".to_owned());
751                }
752                self.skip_whitespace();
753                if self.try_consume('}') {
754                    return Ok(ListValue::empty(self.data_type.as_list_element_type()));
755                }
756                let mut builder =
757                    ArrayBuilderImpl::with_type(0, self.data_type.as_list_element_type().clone());
758                loop {
759                    let mut parser = Self {
760                        input: self.input,
761                        data_type: self.data_type.as_list_element_type(),
762                    };
763                    builder.append(parser.parse()?);
764                    self.input = parser.input;
765
766                    // expect ',' or '}'
767                    self.skip_whitespace();
768                    match self.peek() {
769                        Some(',') => {
770                            self.try_consume(',');
771                        }
772                        Some('}') => {
773                            self.try_consume('}');
774                            break;
775                        }
776                        None => return Err(Self::eoi()),
777                        _ => return Err("Unexpected array element.".to_owned()),
778                    }
779                }
780                Ok(ListValue::new(builder.finish()))
781            }
782
783            /// Parse a non-array value.
784            fn parse_value(&mut self) -> Result<Datum, String> {
785                if self.peek() == Some('"') {
786                    return Ok(Some(self.parse_quoted()?));
787                }
788                // peek until the next unescaped ',' or '}'
789                let mut chars = self.input.char_indices();
790                let mut has_escape = false;
791                let s = loop {
792                    match chars.next().ok_or_else(Self::eoi)? {
793                        (_, '\\') => {
794                            has_escape = true;
795                            chars.next().ok_or_else(Self::eoi)?;
796                        }
797                        (i, c @ ',' | c @ '}') => {
798                            let s = &self.input[..i];
799                            // consume the value and leave the ',' or '}' for parent
800                            self.input = &self.input[i..];
801
802                            break if has_escape {
803                                Cow::Owned(Self::unescape_trim_end(s))
804                            } else {
805                                let trimmed = s.trim_end();
806                                if trimmed.is_empty() {
807                                    return Err(format!("Unexpected \"{c}\" character."));
808                                }
809                                if trimmed.eq_ignore_ascii_case("null") {
810                                    return Ok(None);
811                                }
812                                Cow::Borrowed(trimmed)
813                            };
814                        }
815                        (_, '{') => return Err("Unexpected \"{\" character.".to_owned()),
816                        (_, '"') => return Err("Unexpected array element.".to_owned()),
817                        _ => {}
818                    }
819                };
820                Ok(Some(
821                    ScalarImpl::from_text(&s, self.data_type).map_err(|e| e.to_report_string())?,
822                ))
823            }
824
825            /// Parse a double quoted non-array value.
826            fn parse_quoted(&mut self) -> Result<ScalarImpl, String> {
827                assert!(self.try_consume('"'));
828                // peek until the next unescaped '"'
829                let mut chars = self.input.char_indices();
830                let mut has_escape = false;
831                let s = loop {
832                    match chars.next().ok_or_else(Self::eoi)? {
833                        (_, '\\') => {
834                            has_escape = true;
835                            chars.next().ok_or_else(Self::eoi)?;
836                        }
837                        (i, '"') => {
838                            let s = &self.input[..i];
839                            self.input = &self.input[i + 1..];
840                            break if has_escape {
841                                Cow::Owned(Self::unescape(s))
842                            } else {
843                                Cow::Borrowed(s)
844                            };
845                        }
846                        _ => {}
847                    }
848                };
849                ScalarImpl::from_text(&s, self.data_type).map_err(|e| e.to_report_string())
850            }
851
852            /// Unescape a string.
853            fn unescape(s: &str) -> String {
854                let mut unescaped = String::with_capacity(s.len());
855                let mut chars = s.chars();
856                while let Some(mut c) = chars.next() {
857                    if c == '\\' {
858                        c = chars.next().unwrap();
859                    }
860                    unescaped.push(c);
861                }
862                unescaped
863            }
864
865            /// Unescape a string and trim the trailing whitespaces.
866            ///
867            /// Example: `"\  " -> " "`
868            fn unescape_trim_end(s: &str) -> String {
869                let mut unescaped = String::with_capacity(s.len());
870                let mut chars = s.chars();
871                let mut len_after_last_escaped_char = 0;
872                while let Some(mut c) = chars.next() {
873                    if c == '\\' {
874                        c = chars.next().unwrap();
875                        unescaped.push(c);
876                        len_after_last_escaped_char = unescaped.len();
877                    } else {
878                        unescaped.push(c);
879                    }
880                }
881                let l = unescaped[len_after_last_escaped_char..].trim_end().len();
882                unescaped.truncate(len_after_last_escaped_char + l);
883                unescaped
884            }
885
886            /// Consume the next 4 characters if it matches "null".
887            ///
888            /// Note: We don't use this function when parsing non-array values.
889            ///       Because we can't decide whether it is a null value or a string starts with "null".
890            ///       Consider this case: `{null value}` => `["null value"]`
891            fn try_parse_null(&mut self) -> bool {
892                if let Some(s) = self.input.get(..4)
893                    && s.eq_ignore_ascii_case("null")
894                {
895                    let next_char = self.input[4..].chars().next();
896                    match next_char {
897                        None | Some(',' | '}') => {}
898                        Some(c) if c.is_ascii_whitespace() => {}
899                        // following normal characters
900                        _ => return false,
901                    }
902                    self.input = &self.input[4..];
903                    true
904                } else {
905                    false
906                }
907            }
908
909            /// Consume the next character if it matches `c`.
910            fn try_consume(&mut self, c: char) -> bool {
911                if self.peek() == Some(c) {
912                    self.input = &self.input[c.len_utf8()..];
913                    true
914                } else {
915                    false
916                }
917            }
918
919            /// Expect end of input.
920            fn expect_end(&mut self) -> Result<(), String> {
921                self.skip_whitespace();
922                match self.peek() {
923                    Some(_) => Err("Junk after closing right brace.".to_owned()),
924                    None => Ok(()),
925                }
926            }
927
928            /// Skip whitespaces.
929            fn skip_whitespace(&mut self) {
930                self.input = match self
931                    .input
932                    .char_indices()
933                    .find(|(_, c)| !c.is_ascii_whitespace())
934                {
935                    Some((i, _)) => &self.input[i..],
936                    None => "",
937                };
938            }
939
940            /// Peek the next character.
941            fn peek(&self) -> Option<char> {
942                self.input.chars().next()
943            }
944
945            /// Return the error message for unexpected end of input.
946            fn eoi() -> String {
947                "Unexpected end of input.".into()
948            }
949        }
950
951        let mut parser = Parser { input, data_type };
952        let array = parser.parse_array()?;
953        parser.expect_end()?;
954        Ok(array)
955    }
956}
957
958#[cfg(test)]
959mod tests {
960    use more_asserts::{assert_gt, assert_lt};
961
962    use super::*;
963
964    #[test]
965    fn test_protobuf() {
966        use crate::array::*;
967        let array = ListArray::from_iter([
968            Some(vec![12i32, -7, 25]),
969            None,
970            Some(vec![0, -127, 127, 50]),
971            Some(vec![]),
972        ]);
973        let actual = ListArray::from_protobuf(&array.to_protobuf()).unwrap();
974        assert_eq!(actual, ArrayImpl::List(array));
975    }
976
977    #[test]
978    fn test_append_array() {
979        let part1 = ListArray::from_iter([Some([12i32, -7, 25]), None]);
980        let part2 = ListArray::from_iter([Some(vec![0, -127, 127, 50]), Some(vec![])]);
981
982        let mut builder = ListArrayBuilder::with_type(4, DataType::List(Box::new(DataType::Int32)));
983        builder.append_array(&part1);
984        builder.append_array(&part2);
985
986        let expected = ListArray::from_iter([
987            Some(vec![12i32, -7, 25]),
988            None,
989            Some(vec![0, -127, 127, 50]),
990            Some(vec![]),
991        ]);
992        assert_eq!(builder.finish(), expected);
993    }
994
995    // Ensure `create_builder` exactly copies the same metadata.
996    #[test]
997    fn test_list_create_builder() {
998        use crate::array::*;
999        let arr = ListArray::from_iter([Some([F32::from(2.0), F32::from(42.0), F32::from(1.0)])]);
1000        let arr2 = arr.create_builder(0).finish();
1001        assert_eq!(arr.data_type(), arr2.data_type());
1002    }
1003
1004    #[test]
1005    fn test_builder_pop() {
1006        use crate::array::*;
1007
1008        {
1009            let mut builder =
1010                ListArrayBuilder::with_type(1, DataType::List(Box::new(DataType::Int32)));
1011            let val = ListValue::from_iter([1i32, 2, 3]);
1012            builder.append(Some(val.as_scalar_ref()));
1013            assert!(builder.pop().is_some());
1014            assert!(builder.pop().is_none());
1015            let arr = builder.finish();
1016            assert!(arr.is_empty());
1017        }
1018
1019        {
1020            let data_type = DataType::List(Box::new(DataType::List(Box::new(DataType::Int32))));
1021            let mut builder = ListArrayBuilder::with_type(2, data_type);
1022            let val1 = ListValue::from_iter([1, 2, 3]);
1023            let val2 = ListValue::from_iter([1, 2, 3]);
1024            let list1 = ListValue::from_iter([val1, val2]);
1025            builder.append(Some(list1.as_scalar_ref()));
1026
1027            let val3 = ListValue::from_iter([1, 2, 3]);
1028            let val4 = ListValue::from_iter([1, 2, 3]);
1029            let list2 = ListValue::from_iter([val3, val4]);
1030
1031            builder.append(Some(list2.as_scalar_ref()));
1032
1033            assert!(builder.pop().is_some());
1034
1035            let arr = builder.finish();
1036            assert_eq!(arr.len(), 1);
1037            assert_eq!(arr.value_at(0).unwrap(), list1.as_scalar_ref());
1038        }
1039    }
1040
1041    #[test]
1042    fn test_list_nested_layout() {
1043        use crate::array::*;
1044
1045        let listarray1 = ListArray::from_iter([Some([1i32, 2]), Some([3, 4])]);
1046        let listarray2 = ListArray::from_iter([Some(vec![5, 6, 7]), None, Some(vec![8])]);
1047        let listarray3 = ListArray::from_iter([Some([9, 10])]);
1048
1049        let nestarray = ListArray::from_iter(
1050            [listarray1, listarray2, listarray3]
1051                .into_iter()
1052                .map(|l| ListValue::new(l.into())),
1053        );
1054        let actual = ListArray::from_protobuf(&nestarray.to_protobuf()).unwrap();
1055        assert_eq!(ArrayImpl::List(nestarray), actual);
1056    }
1057
1058    #[test]
1059    fn test_list_value_cmp() {
1060        // ARRAY[1, 1] < ARRAY[1, 2, 1]
1061        assert_lt!(
1062            ListValue::from_iter([1, 1]),
1063            ListValue::from_iter([1, 2, 1]),
1064        );
1065        // ARRAY[1, 2] < ARRAY[1, 2, 1]
1066        assert_lt!(
1067            ListValue::from_iter([1, 2]),
1068            ListValue::from_iter([1, 2, 1]),
1069        );
1070        // ARRAY[1, 3] > ARRAY[1, 2, 1]
1071        assert_gt!(
1072            ListValue::from_iter([1, 3]),
1073            ListValue::from_iter([1, 2, 1]),
1074        );
1075        // null > 1
1076        assert_gt!(
1077            ListValue::from_iter([None::<i32>]),
1078            ListValue::from_iter([1]),
1079        );
1080        // ARRAY[1, 2, null] > ARRAY[1, 2, 1]
1081        assert_gt!(
1082            ListValue::from_iter([Some(1), Some(2), None]),
1083            ListValue::from_iter([Some(1), Some(2), Some(1)]),
1084        );
1085        // Null value in first ARRAY results into a Greater ordering regardless of the smaller ARRAY
1086        // length. ARRAY[1, null] > ARRAY[1, 2, 3]
1087        assert_gt!(
1088            ListValue::from_iter([Some(1), None]),
1089            ListValue::from_iter([Some(1), Some(2), Some(3)]),
1090        );
1091        // ARRAY[1, null] == ARRAY[1, null]
1092        assert_eq!(
1093            ListValue::from_iter([Some(1), None]),
1094            ListValue::from_iter([Some(1), None]),
1095        );
1096    }
1097
1098    #[test]
1099    fn test_list_ref_display() {
1100        let v = ListValue::from_iter([Some(1), None]);
1101        assert_eq!(v.to_string(), "{1,NULL}");
1102    }
1103
1104    #[test]
1105    fn test_serialize_deserialize() {
1106        let value = ListValue::from_iter([Some("abcd"), Some(""), None, Some("a")]);
1107        let list_ref = value.as_scalar_ref();
1108        let mut serializer = memcomparable::Serializer::new(vec![]);
1109        serializer.set_reverse(true);
1110        list_ref.memcmp_serialize(&mut serializer).unwrap();
1111        let buf = serializer.into_inner();
1112        let mut deserializer = memcomparable::Deserializer::new(&buf[..]);
1113        deserializer.set_reverse(true);
1114        assert_eq!(
1115            ListValue::memcmp_deserialize(&DataType::Varchar, &mut deserializer).unwrap(),
1116            value
1117        );
1118
1119        let mut builder =
1120            ListArrayBuilder::with_type(0, DataType::List(Box::new(DataType::Varchar)));
1121        builder.append(Some(list_ref));
1122        let array = builder.finish();
1123        let list_ref = array.value_at(0).unwrap();
1124        let mut serializer = memcomparable::Serializer::new(vec![]);
1125        list_ref.memcmp_serialize(&mut serializer).unwrap();
1126        let buf = serializer.into_inner();
1127        let mut deserializer = memcomparable::Deserializer::new(&buf[..]);
1128        assert_eq!(
1129            ListValue::memcmp_deserialize(&DataType::Varchar, &mut deserializer).unwrap(),
1130            value
1131        );
1132    }
1133
1134    #[test]
1135    fn test_memcomparable() {
1136        let cases = [
1137            (
1138                ListValue::from_iter([123, 456]),
1139                ListValue::from_iter([123, 789]),
1140            ),
1141            (
1142                ListValue::from_iter([123, 456]),
1143                ListValue::from_iter([123]),
1144            ),
1145            (
1146                ListValue::from_iter([None, Some("")]),
1147                ListValue::from_iter([None, None::<&str>]),
1148            ),
1149            (
1150                ListValue::from_iter([Some(2)]),
1151                ListValue::from_iter([Some(1), None, Some(3)]),
1152            ),
1153        ];
1154
1155        for (lhs, rhs) in cases {
1156            let lhs_serialized = {
1157                let mut serializer = memcomparable::Serializer::new(vec![]);
1158                lhs.as_scalar_ref()
1159                    .memcmp_serialize(&mut serializer)
1160                    .unwrap();
1161                serializer.into_inner()
1162            };
1163            let rhs_serialized = {
1164                let mut serializer = memcomparable::Serializer::new(vec![]);
1165                rhs.as_scalar_ref()
1166                    .memcmp_serialize(&mut serializer)
1167                    .unwrap();
1168                serializer.into_inner()
1169            };
1170            assert_eq!(lhs_serialized.cmp(&rhs_serialized), lhs.cmp(&rhs));
1171        }
1172    }
1173
1174    #[test]
1175    fn test_listref() {
1176        use crate::array::*;
1177        use crate::types;
1178
1179        let arr = ListArray::from_iter([Some(vec![1, 2, 3]), None, Some(vec![4, 5, 6, 7])]);
1180
1181        // get 3rd ListRef from ListArray
1182        let list_ref = arr.value_at(2).unwrap();
1183        assert_eq!(list_ref, ListValue::from_iter([4, 5, 6, 7]).as_scalar_ref());
1184
1185        // Get 2nd value from ListRef
1186        let scalar = list_ref.get(1).unwrap();
1187        assert_eq!(scalar, Some(types::ScalarRefImpl::Int32(5)));
1188    }
1189
1190    #[test]
1191    fn test_from_to_literal() {
1192        #[track_caller]
1193        fn test(typestr: &str, input: &str, output: Option<&str>) {
1194            let datatype: DataType = typestr.parse().unwrap();
1195            let list = ListValue::from_str(input, &datatype).unwrap();
1196            let actual = list.as_scalar_ref().to_text();
1197            let output = output.unwrap_or(input);
1198            assert_eq!(actual, output);
1199        }
1200
1201        #[track_caller]
1202        fn test_err(typestr: &str, input: &str, err: &str) {
1203            let datatype: DataType = typestr.parse().unwrap();
1204            let actual_err = ListValue::from_str(input, &datatype).unwrap_err();
1205            assert_eq!(actual_err, err);
1206        }
1207
1208        test("varchar[]", "{}", None);
1209        test("varchar[]", "{1 2}", Some(r#"{"1 2"}"#));
1210        test("varchar[]", "{🥵,🤡}", None);
1211        test("varchar[]", r#"{aa\\bb}"#, Some(r#"{"aa\\bb"}"#));
1212        test("int[]", "{1,2,3}", None);
1213        test("varchar[]", r#"{"1,2"}"#, None);
1214        test("varchar[]", r#"{1, ""}"#, Some(r#"{1,""}"#));
1215        test("varchar[]", r#"{"\""}"#, None);
1216        test("varchar[]", r#"{\   }"#, Some(r#"{" "}"#));
1217        test("varchar[]", r#"{\\  }"#, Some(r#"{"\\"}"#));
1218        test("varchar[]", "{nulla}", None);
1219        test("varchar[]", "{null a}", Some(r#"{"null a"}"#));
1220        test(
1221            "varchar[]",
1222            r#"{"null", "NULL", null, NuLL}"#,
1223            Some(r#"{"null","NULL",NULL,NULL}"#),
1224        );
1225        test("varchar[][]", "{{1, 2, 3}, null }", Some("{{1,2,3},NULL}"));
1226        test(
1227            "varchar[][][]",
1228            "{{{1, 2, 3}}, {{4, 5, 6}}}",
1229            Some("{{{1,2,3}},{{4,5,6}}}"),
1230        );
1231        test_err("varchar[]", "()", r#"Array value must start with "{""#);
1232        test_err("varchar[]", "{1,", r#"Unexpected end of input."#);
1233        test_err("varchar[]", "{1,}", r#"Unexpected "}" character."#);
1234        test_err("varchar[]", "{1,,3}", r#"Unexpected "," character."#);
1235        test_err("varchar[]", r#"{"a""b"}"#, r#"Unexpected array element."#);
1236        test_err("varchar[]", r#"{}{"#, r#"Junk after closing right brace."#);
1237    }
1238}
risingwave_common/array/list_array.rs

risingwave_common/array/
list_array.rs
