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            "invalid array type for list: {}",
254            array.array_type
255        );
256        let bitmap: Bitmap = array.get_null_bitmap()?.into();
257        let array_data = array.get_list_array_data()?.to_owned();
258        let flatten_len = match array_data.offsets.last() {
259            Some(&n) => n as usize,
260            None => bail!("Must have at least one element in offsets"),
261        };
262        let value = ArrayImpl::from_protobuf(array_data.value.as_ref().unwrap(), flatten_len)?;
263        let arr = ListArray {
264            bitmap,
265            offsets: array_data.offsets.into(),
266            value: Box::new(value),
267        };
268        Ok(arr.into())
269    }
270
271    /// Apply the function on the underlying elements.
272    /// e.g. `map_inner([[1,2,3],NULL,[4,5]], DOUBLE) = [[2,4,6],NULL,[8,10]]`
273    pub async fn map_inner<E, Fut, F>(self, f: F) -> std::result::Result<ListArray, E>
274    where
275        F: FnOnce(ArrayImpl) -> Fut,
276        Fut: Future<Output = std::result::Result<ArrayImpl, E>>,
277    {
278        let new_value = (f)(*self.value).await?;
279
280        Ok(Self {
281            offsets: self.offsets,
282            bitmap: self.bitmap,
283            value: Box::new(new_value),
284        })
285    }
286
287    /// Returns the offsets of this list.
288    ///
289    /// # Example
290    /// ```text
291    /// list    = [[a, b, c], [], NULL, [d], [NULL, f]]
292    /// offsets = [0, 3, 3, 3, 4, 6]
293    /// ```
294    pub fn offsets(&self) -> &[u32] {
295        &self.offsets
296    }
297}
298
299impl<T, L> FromIterator<Option<L>> for ListArray
300where
301    T: PrimitiveArrayItemType,
302    L: IntoIterator<Item = T>,
303{
304    fn from_iter<I: IntoIterator<Item = Option<L>>>(iter: I) -> Self {
305        let iter = iter.into_iter();
306        let mut builder = ListArrayBuilder::with_type(
307            iter.size_hint().0,
308            DataType::List(Box::new(T::DATA_TYPE.clone())),
309        );
310        for v in iter {
311            match v {
312                None => builder.append(None),
313                Some(v) => {
314                    builder.append(Some(v.into_iter().collect::<ListValue>().as_scalar_ref()))
315                }
316            }
317        }
318        builder.finish()
319    }
320}
321
322impl FromIterator<ListValue> for ListArray {
323    fn from_iter<I: IntoIterator<Item = ListValue>>(iter: I) -> Self {
324        let mut iter = iter.into_iter();
325        let first = iter.next().expect("empty iterator");
326        let mut builder = ListArrayBuilder::with_type(
327            iter.size_hint().0,
328            DataType::List(Box::new(first.data_type())),
329        );
330        builder.append(Some(first.as_scalar_ref()));
331        for v in iter {
332            builder.append(Some(v.as_scalar_ref()));
333        }
334        builder.finish()
335    }
336}
337
338#[derive(Clone, PartialEq, Eq, EstimateSize)]
339pub struct ListValue {
340    values: Box<ArrayImpl>,
341}
342
343impl Debug for ListValue {
344    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
345        self.as_scalar_ref().fmt(f)
346    }
347}
348
349impl Display for ListValue {
350    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
351        self.as_scalar_ref().write(f)
352    }
353}
354
355impl ListValue {
356    pub fn new(values: ArrayImpl) -> Self {
357        Self {
358            values: Box::new(values),
359        }
360    }
361
362    pub fn into_array(self) -> ArrayImpl {
363        *self.values
364    }
365
366    pub fn empty(datatype: &DataType) -> Self {
367        Self::new(datatype.create_array_builder(0).finish())
368    }
369
370    /// Creates a new `ListValue` from an iterator of `Datum`.
371    pub fn from_datum_iter<T: ToDatumRef>(
372        elem_datatype: &DataType,
373        iter: impl IntoIterator<Item = T>,
374    ) -> Self {
375        let iter = iter.into_iter();
376        let mut builder = elem_datatype.create_array_builder(iter.size_hint().0);
377        for datum in iter {
378            builder.append(datum);
379        }
380        Self::new(builder.finish())
381    }
382
383    /// Returns the length of the list.
384    pub fn len(&self) -> usize {
385        self.values.len()
386    }
387
388    /// Returns `true` if the list has a length of 0.
389    pub fn is_empty(&self) -> bool {
390        self.values.is_empty()
391    }
392
393    /// Iterates over the elements of the list.
394    pub fn iter(&self) -> impl DoubleEndedIterator + ExactSizeIterator<Item = DatumRef<'_>> {
395        self.values.iter()
396    }
397
398    /// Get the element at the given index. Returns `None` if the index is out of bounds.
399    pub fn get(&self, index: usize) -> Option<DatumRef<'_>> {
400        if index < self.len() {
401            Some(self.values.value_at(index))
402        } else {
403            None
404        }
405    }
406
407    /// Returns the data type of the elements in the list.
408    pub fn data_type(&self) -> DataType {
409        self.values.data_type()
410    }
411
412    pub fn memcmp_deserialize(
413        item_datatype: &DataType,
414        deserializer: &mut memcomparable::Deserializer<impl Buf>,
415    ) -> memcomparable::Result<Self> {
416        let bytes = serde_bytes::ByteBuf::deserialize(deserializer)?;
417        let mut inner_deserializer = memcomparable::Deserializer::new(bytes.as_slice());
418        let mut builder = item_datatype.create_array_builder(0);
419        while inner_deserializer.has_remaining() {
420            builder.append(memcmp_encoding::deserialize_datum_in_composite(
421                item_datatype,
422                &mut inner_deserializer,
423            )?)
424        }
425        Ok(Self::new(builder.finish()))
426    }
427
428    // Used to display ListValue in explain for better readibilty.
429    pub fn display_for_explain(&self) -> String {
430        // Example of ListValue display: ARRAY[1, 2, null]
431        format!(
432            "ARRAY[{}]",
433            self.iter()
434                .map(|v| {
435                    match v.as_ref() {
436                        None => "null".into(),
437                        Some(scalar) => scalar.to_text(),
438                    }
439                })
440                .format(", ")
441        )
442    }
443
444    /// Returns a mutable slice if the list is of type `int64[]`.
445    pub fn as_i64_mut_slice(&mut self) -> Option<&mut [i64]> {
446        match self.values.as_mut() {
447            ArrayImpl::Int64(array) => Some(array.as_mut_slice()),
448            _ => None,
449        }
450    }
451}
452
453impl PartialOrd for ListValue {
454    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
455        Some(self.cmp(other))
456    }
457}
458
459impl Ord for ListValue {
460    fn cmp(&self, other: &Self) -> Ordering {
461        self.as_scalar_ref().cmp(&other.as_scalar_ref())
462    }
463}
464
465impl<T: PrimitiveArrayItemType> FromIterator<Option<T>> for ListValue {
466    fn from_iter<I: IntoIterator<Item = Option<T>>>(iter: I) -> Self {
467        Self::new(iter.into_iter().collect::<PrimitiveArray<T>>().into())
468    }
469}
470
471impl<T: PrimitiveArrayItemType> FromIterator<T> for ListValue {
472    fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self {
473        Self::new(iter.into_iter().collect::<PrimitiveArray<T>>().into())
474    }
475}
476
477impl FromIterator<bool> for ListValue {
478    fn from_iter<I: IntoIterator<Item = bool>>(iter: I) -> Self {
479        Self::new(iter.into_iter().collect::<BoolArray>().into())
480    }
481}
482
483impl<'a> FromIterator<Option<&'a str>> for ListValue {
484    fn from_iter<I: IntoIterator<Item = Option<&'a str>>>(iter: I) -> Self {
485        Self::new(iter.into_iter().collect::<Utf8Array>().into())
486    }
487}
488
489impl<'a> FromIterator<&'a str> for ListValue {
490    fn from_iter<I: IntoIterator<Item = &'a str>>(iter: I) -> Self {
491        Self::new(iter.into_iter().collect::<Utf8Array>().into())
492    }
493}
494
495impl FromIterator<ListValue> for ListValue {
496    fn from_iter<I: IntoIterator<Item = ListValue>>(iter: I) -> Self {
497        Self::new(iter.into_iter().collect::<ListArray>().into())
498    }
499}
500
501impl From<ListValue> for ArrayImpl {
502    fn from(value: ListValue) -> Self {
503        *value.values
504    }
505}
506
507/// A slice of an array
508#[derive(Copy, Clone)]
509pub struct ListRef<'a> {
510    array: &'a ArrayImpl,
511    start: u32,
512    end: u32,
513}
514
515impl<'a> ListRef<'a> {
516    /// Returns the length of the list.
517    pub fn len(&self) -> usize {
518        (self.end - self.start) as usize
519    }
520
521    /// Returns `true` if the list has a length of 0.
522    pub fn is_empty(&self) -> bool {
523        self.start == self.end
524    }
525
526    /// Returns the data type of the elements in the list.
527    pub fn data_type(&self) -> DataType {
528        self.array.data_type()
529    }
530
531    /// Returns the elements in the flattened list.
532    pub fn flatten(self) -> ListRef<'a> {
533        match self.array {
534            ArrayImpl::List(inner) => ListRef {
535                array: &inner.value,
536                start: inner.offsets[self.start as usize],
537                end: inner.offsets[self.end as usize],
538            }
539            .flatten(),
540            _ => self,
541        }
542    }
543
544    /// Iterates over the elements of the list.
545    pub fn iter(self) -> impl DoubleEndedIterator + ExactSizeIterator<Item = DatumRef<'a>> + 'a {
546        (self.start..self.end).map(|i| self.array.value_at(i as usize))
547    }
548
549    /// Get the element at the given index. Returns `None` if the index is out of bounds.
550    pub fn get(self, index: usize) -> Option<DatumRef<'a>> {
551        if index < self.len() {
552            Some(self.array.value_at(self.start as usize + index))
553        } else {
554            None
555        }
556    }
557
558    pub fn memcmp_serialize(
559        self,
560        serializer: &mut memcomparable::Serializer<impl BufMut>,
561    ) -> memcomparable::Result<()> {
562        let mut inner_serializer = memcomparable::Serializer::new(vec![]);
563        for datum_ref in self.iter() {
564            memcmp_encoding::serialize_datum_in_composite(datum_ref, &mut inner_serializer)?
565        }
566        serializer.serialize_bytes(&inner_serializer.into_inner())
567    }
568
569    pub fn hash_scalar_inner<H: std::hash::Hasher>(self, state: &mut H) {
570        for datum_ref in self.iter() {
571            hash_datum(datum_ref, state);
572        }
573    }
574
575    /// estimate the serialized size with value encoding
576    pub fn estimate_serialize_size_inner(self) -> usize {
577        self.iter().map(estimate_serialize_datum_size).sum()
578    }
579
580    pub fn to_owned(self) -> ListValue {
581        let mut builder = self.array.create_builder(self.len());
582        for datum_ref in self.iter() {
583            builder.append(datum_ref);
584        }
585        ListValue::new(builder.finish())
586    }
587
588    pub fn as_primitive_slice<T: PrimitiveArrayItemType>(self) -> Option<&'a [T]> {
589        T::try_into_array_ref(self.array)
590            .map(|prim_arr| &prim_arr.as_slice()[self.start as usize..self.end as usize])
591    }
592
593    /// Returns a slice if the list is of type `int64[]`.
594    pub fn as_i64_slice(&self) -> Option<&[i64]> {
595        self.as_primitive_slice()
596    }
597
598    /// # Panics
599    /// Panics if the list is not a map's internal representation (See [`super::MapArray`]).
600    pub(super) fn as_map_kv(self) -> (ListRef<'a>, ListRef<'a>) {
601        let (k, v) = self.array.as_struct().fields().collect_tuple().unwrap();
602        (
603            ListRef {
604                array: k,
605                start: self.start,
606                end: self.end,
607            },
608            ListRef {
609                array: v,
610                start: self.start,
611                end: self.end,
612            },
613        )
614    }
615}
616
617impl PartialEq for ListRef<'_> {
618    fn eq(&self, other: &Self) -> bool {
619        self.iter().eq(other.iter())
620    }
621}
622
623impl Eq for ListRef<'_> {}
624
625impl PartialOrd for ListRef<'_> {
626    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
627        Some(self.cmp(other))
628    }
629}
630
631impl Ord for ListRef<'_> {
632    fn cmp(&self, other: &Self) -> Ordering {
633        self.iter().cmp_by(other.iter(), |a, b| a.default_cmp(&b))
634    }
635}
636
637impl Debug for ListRef<'_> {
638    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
639        f.debug_list().entries(self.iter()).finish()
640    }
641}
642
643impl Row for ListRef<'_> {
644    fn datum_at(&self, index: usize) -> DatumRef<'_> {
645        self.array.value_at(self.start as usize + index)
646    }
647
648    unsafe fn datum_at_unchecked(&self, index: usize) -> DatumRef<'_> {
649        unsafe { self.array.value_at_unchecked(self.start as usize + index) }
650    }
651
652    fn len(&self) -> usize {
653        self.len()
654    }
655
656    fn iter(&self) -> impl Iterator<Item = DatumRef<'_>> {
657        (*self).iter()
658    }
659}
660
661impl ToText for ListRef<'_> {
662    // This function will be invoked when pgwire prints a list value in string.
663    // Refer to PostgreSQL `array_out` or `appendPGArray`.
664    fn write<W: std::fmt::Write>(&self, f: &mut W) -> std::fmt::Result {
665        write!(
666            f,
667            "{{{}}}",
668            self.iter().format_with(",", |datum_ref, f| {
669                let s = datum_ref.to_text();
670                // Never quote null or inner list, but quote empty, verbatim 'null', special
671                // chars and whitespaces.
672                let need_quote = !matches!(datum_ref, None | Some(ScalarRefImpl::List(_)))
673                    && (s.is_empty()
674                        || s.eq_ignore_ascii_case("null")
675                        || s.contains([
676                            '"', '\\', ',',
677                            // whilespace:
678                            // PostgreSQL `array_isspace` includes '\x0B' but rust
679                            // [`char::is_ascii_whitespace`] does not.
680                            ' ', '\t', '\n', '\r', '\x0B', '\x0C', // list-specific:
681                            '{', '}',
682                        ]));
683                if need_quote {
684                    f(&"\"")?;
685                    s.chars().try_for_each(|c| {
686                        if c == '"' || c == '\\' {
687                            f(&"\\")?;
688                        }
689                        f(&c)
690                    })?;
691                    f(&"\"")
692                } else {
693                    f(&s)
694                }
695            })
696        )
697    }
698
699    fn write_with_type<W: std::fmt::Write>(&self, ty: &DataType, f: &mut W) -> std::fmt::Result {
700        match ty {
701            DataType::List { .. } => self.write(f),
702            _ => unreachable!(),
703        }
704    }
705}
706
707impl<'a> From<&'a ListValue> for ListRef<'a> {
708    fn from(value: &'a ListValue) -> Self {
709        ListRef {
710            array: &value.values,
711            start: 0,
712            end: value.len() as u32,
713        }
714    }
715}
716
717impl From<ListRef<'_>> for ListValue {
718    fn from(value: ListRef<'_>) -> Self {
719        value.to_owned()
720    }
721}
722
723impl ListValue {
724    /// Construct an array from literal string.
725    pub fn from_str(input: &str, data_type: &DataType) -> Result<Self, String> {
726        struct Parser<'a> {
727            input: &'a str,
728            data_type: &'a DataType,
729        }
730
731        impl Parser<'_> {
732            /// Parse a datum.
733            fn parse(&mut self) -> Result<Datum, String> {
734                self.skip_whitespace();
735                if self.data_type.is_array() {
736                    if self.try_parse_null() {
737                        return Ok(None);
738                    }
739                    Ok(Some(self.parse_array()?.into()))
740                } else {
741                    self.parse_value()
742                }
743            }
744
745            /// Parse an array.
746            fn parse_array(&mut self) -> Result<ListValue, String> {
747                self.skip_whitespace();
748                if !self.try_consume('{') {
749                    return Err("Array value must start with \"{\"".to_owned());
750                }
751                self.skip_whitespace();
752                if self.try_consume('}') {
753                    return Ok(ListValue::empty(self.data_type.as_list_element_type()));
754                }
755                let mut builder =
756                    ArrayBuilderImpl::with_type(0, self.data_type.as_list_element_type().clone());
757                loop {
758                    let mut parser = Self {
759                        input: self.input,
760                        data_type: self.data_type.as_list_element_type(),
761                    };
762                    builder.append(parser.parse()?);
763                    self.input = parser.input;
764
765                    // expect ',' or '}'
766                    self.skip_whitespace();
767                    match self.peek() {
768                        Some(',') => {
769                            self.try_consume(',');
770                        }
771                        Some('}') => {
772                            self.try_consume('}');
773                            break;
774                        }
775                        None => return Err(Self::eoi()),
776                        _ => return Err("Unexpected array element.".to_owned()),
777                    }
778                }
779                Ok(ListValue::new(builder.finish()))
780            }
781
782            /// Parse a non-array value.
783            fn parse_value(&mut self) -> Result<Datum, String> {
784                if self.peek() == Some('"') {
785                    return Ok(Some(self.parse_quoted()?));
786                }
787                // peek until the next unescaped ',' or '}'
788                let mut chars = self.input.char_indices();
789                let mut has_escape = false;
790                let s = loop {
791                    match chars.next().ok_or_else(Self::eoi)? {
792                        (_, '\\') => {
793                            has_escape = true;
794                            chars.next().ok_or_else(Self::eoi)?;
795                        }
796                        (i, c @ ',' | c @ '}') => {
797                            let s = &self.input[..i];
798                            // consume the value and leave the ',' or '}' for parent
799                            self.input = &self.input[i..];
800
801                            break if has_escape {
802                                Cow::Owned(Self::unescape_trim_end(s))
803                            } else {
804                                let trimmed = s.trim_end();
805                                if trimmed.is_empty() {
806                                    return Err(format!("Unexpected \"{c}\" character."));
807                                }
808                                if trimmed.eq_ignore_ascii_case("null") {
809                                    return Ok(None);
810                                }
811                                Cow::Borrowed(trimmed)
812                            };
813                        }
814                        (_, '{') => return Err("Unexpected \"{\" character.".to_owned()),
815                        (_, '"') => return Err("Unexpected array element.".to_owned()),
816                        _ => {}
817                    }
818                };
819                Ok(Some(
820                    ScalarImpl::from_text(&s, self.data_type).map_err(|e| e.to_report_string())?,
821                ))
822            }
823
824            /// Parse a double quoted non-array value.
825            fn parse_quoted(&mut self) -> Result<ScalarImpl, String> {
826                assert!(self.try_consume('"'));
827                // peek until the next unescaped '"'
828                let mut chars = self.input.char_indices();
829                let mut has_escape = false;
830                let s = loop {
831                    match chars.next().ok_or_else(Self::eoi)? {
832                        (_, '\\') => {
833                            has_escape = true;
834                            chars.next().ok_or_else(Self::eoi)?;
835                        }
836                        (i, '"') => {
837                            let s = &self.input[..i];
838                            self.input = &self.input[i + 1..];
839                            break if has_escape {
840                                Cow::Owned(Self::unescape(s))
841                            } else {
842                                Cow::Borrowed(s)
843                            };
844                        }
845                        _ => {}
846                    }
847                };
848                ScalarImpl::from_text(&s, self.data_type).map_err(|e| e.to_report_string())
849            }
850
851            /// Unescape a string.
852            fn unescape(s: &str) -> String {
853                let mut unescaped = String::with_capacity(s.len());
854                let mut chars = s.chars();
855                while let Some(mut c) = chars.next() {
856                    if c == '\\' {
857                        c = chars.next().unwrap();
858                    }
859                    unescaped.push(c);
860                }
861                unescaped
862            }
863
864            /// Unescape a string and trim the trailing whitespaces.
865            ///
866            /// Example: `"\  " -> " "`
867            fn unescape_trim_end(s: &str) -> String {
868                let mut unescaped = String::with_capacity(s.len());
869                let mut chars = s.chars();
870                let mut len_after_last_escaped_char = 0;
871                while let Some(mut c) = chars.next() {
872                    if c == '\\' {
873                        c = chars.next().unwrap();
874                        unescaped.push(c);
875                        len_after_last_escaped_char = unescaped.len();
876                    } else {
877                        unescaped.push(c);
878                    }
879                }
880                let l = unescaped[len_after_last_escaped_char..].trim_end().len();
881                unescaped.truncate(len_after_last_escaped_char + l);
882                unescaped
883            }
884
885            /// Consume the next 4 characters if it matches "null".
886            ///
887            /// Note: We don't use this function when parsing non-array values.
888            ///       Because we can't decide whether it is a null value or a string starts with "null".
889            ///       Consider this case: `{null value}` => `["null value"]`
890            fn try_parse_null(&mut self) -> bool {
891                if let Some(s) = self.input.get(..4)
892                    && s.eq_ignore_ascii_case("null")
893                {
894                    let next_char = self.input[4..].chars().next();
895                    match next_char {
896                        None | Some(',' | '}') => {}
897                        Some(c) if c.is_ascii_whitespace() => {}
898                        // following normal characters
899                        _ => return false,
900                    }
901                    self.input = &self.input[4..];
902                    true
903                } else {
904                    false
905                }
906            }
907
908            /// Consume the next character if it matches `c`.
909            fn try_consume(&mut self, c: char) -> bool {
910                if self.peek() == Some(c) {
911                    self.input = &self.input[c.len_utf8()..];
912                    true
913                } else {
914                    false
915                }
916            }
917
918            /// Expect end of input.
919            fn expect_end(&mut self) -> Result<(), String> {
920                self.skip_whitespace();
921                match self.peek() {
922                    Some(_) => Err("Junk after closing right brace.".to_owned()),
923                    None => Ok(()),
924                }
925            }
926
927            /// Skip whitespaces.
928            fn skip_whitespace(&mut self) {
929                self.input = match self
930                    .input
931                    .char_indices()
932                    .find(|(_, c)| !c.is_ascii_whitespace())
933                {
934                    Some((i, _)) => &self.input[i..],
935                    None => "",
936                };
937            }
938
939            /// Peek the next character.
940            fn peek(&self) -> Option<char> {
941                self.input.chars().next()
942            }
943
944            /// Return the error message for unexpected end of input.
945            fn eoi() -> String {
946                "Unexpected end of input.".into()
947            }
948        }
949
950        let mut parser = Parser { input, data_type };
951        let array = parser.parse_array()?;
952        parser.expect_end()?;
953        Ok(array)
954    }
955}
956
957#[cfg(test)]
958mod tests {
959    use more_asserts::{assert_gt, assert_lt};
960
961    use super::*;
962
963    #[test]
964    fn test_protobuf() {
965        use crate::array::*;
966        let array = ListArray::from_iter([
967            Some(vec![12i32, -7, 25]),
968            None,
969            Some(vec![0, -127, 127, 50]),
970            Some(vec![]),
971        ]);
972        let actual = ListArray::from_protobuf(&array.to_protobuf()).unwrap();
973        assert_eq!(actual, ArrayImpl::List(array));
974    }
975
976    #[test]
977    fn test_append_array() {
978        let part1 = ListArray::from_iter([Some([12i32, -7, 25]), None]);
979        let part2 = ListArray::from_iter([Some(vec![0, -127, 127, 50]), Some(vec![])]);
980
981        let mut builder = ListArrayBuilder::with_type(4, DataType::List(Box::new(DataType::Int32)));
982        builder.append_array(&part1);
983        builder.append_array(&part2);
984
985        let expected = ListArray::from_iter([
986            Some(vec![12i32, -7, 25]),
987            None,
988            Some(vec![0, -127, 127, 50]),
989            Some(vec![]),
990        ]);
991        assert_eq!(builder.finish(), expected);
992    }
993
994    // Ensure `create_builder` exactly copies the same metadata.
995    #[test]
996    fn test_list_create_builder() {
997        use crate::array::*;
998        let arr = ListArray::from_iter([Some([F32::from(2.0), F32::from(42.0), F32::from(1.0)])]);
999        let arr2 = arr.create_builder(0).finish();
1000        assert_eq!(arr.data_type(), arr2.data_type());
1001    }
1002
1003    #[test]
1004    fn test_builder_pop() {
1005        use crate::array::*;
1006
1007        {
1008            let mut builder =
1009                ListArrayBuilder::with_type(1, DataType::List(Box::new(DataType::Int32)));
1010            let val = ListValue::from_iter([1i32, 2, 3]);
1011            builder.append(Some(val.as_scalar_ref()));
1012            assert!(builder.pop().is_some());
1013            assert!(builder.pop().is_none());
1014            let arr = builder.finish();
1015            assert!(arr.is_empty());
1016        }
1017
1018        {
1019            let data_type = DataType::List(Box::new(DataType::List(Box::new(DataType::Int32))));
1020            let mut builder = ListArrayBuilder::with_type(2, data_type);
1021            let val1 = ListValue::from_iter([1, 2, 3]);
1022            let val2 = ListValue::from_iter([1, 2, 3]);
1023            let list1 = ListValue::from_iter([val1, val2]);
1024            builder.append(Some(list1.as_scalar_ref()));
1025
1026            let val3 = ListValue::from_iter([1, 2, 3]);
1027            let val4 = ListValue::from_iter([1, 2, 3]);
1028            let list2 = ListValue::from_iter([val3, val4]);
1029
1030            builder.append(Some(list2.as_scalar_ref()));
1031
1032            assert!(builder.pop().is_some());
1033
1034            let arr = builder.finish();
1035            assert_eq!(arr.len(), 1);
1036            assert_eq!(arr.value_at(0).unwrap(), list1.as_scalar_ref());
1037        }
1038    }
1039
1040    #[test]
1041    fn test_list_nested_layout() {
1042        use crate::array::*;
1043
1044        let listarray1 = ListArray::from_iter([Some([1i32, 2]), Some([3, 4])]);
1045        let listarray2 = ListArray::from_iter([Some(vec![5, 6, 7]), None, Some(vec![8])]);
1046        let listarray3 = ListArray::from_iter([Some([9, 10])]);
1047
1048        let nestarray = ListArray::from_iter(
1049            [listarray1, listarray2, listarray3]
1050                .into_iter()
1051                .map(|l| ListValue::new(l.into())),
1052        );
1053        let actual = ListArray::from_protobuf(&nestarray.to_protobuf()).unwrap();
1054        assert_eq!(ArrayImpl::List(nestarray), actual);
1055    }
1056
1057    #[test]
1058    fn test_list_value_cmp() {
1059        // ARRAY[1, 1] < ARRAY[1, 2, 1]
1060        assert_lt!(
1061            ListValue::from_iter([1, 1]),
1062            ListValue::from_iter([1, 2, 1]),
1063        );
1064        // ARRAY[1, 2] < ARRAY[1, 2, 1]
1065        assert_lt!(
1066            ListValue::from_iter([1, 2]),
1067            ListValue::from_iter([1, 2, 1]),
1068        );
1069        // ARRAY[1, 3] > ARRAY[1, 2, 1]
1070        assert_gt!(
1071            ListValue::from_iter([1, 3]),
1072            ListValue::from_iter([1, 2, 1]),
1073        );
1074        // null > 1
1075        assert_gt!(
1076            ListValue::from_iter([None::<i32>]),
1077            ListValue::from_iter([1]),
1078        );
1079        // ARRAY[1, 2, null] > ARRAY[1, 2, 1]
1080        assert_gt!(
1081            ListValue::from_iter([Some(1), Some(2), None]),
1082            ListValue::from_iter([Some(1), Some(2), Some(1)]),
1083        );
1084        // Null value in first ARRAY results into a Greater ordering regardless of the smaller ARRAY
1085        // length. ARRAY[1, null] > ARRAY[1, 2, 3]
1086        assert_gt!(
1087            ListValue::from_iter([Some(1), None]),
1088            ListValue::from_iter([Some(1), Some(2), Some(3)]),
1089        );
1090        // ARRAY[1, null] == ARRAY[1, null]
1091        assert_eq!(
1092            ListValue::from_iter([Some(1), None]),
1093            ListValue::from_iter([Some(1), None]),
1094        );
1095    }
1096
1097    #[test]
1098    fn test_list_ref_display() {
1099        let v = ListValue::from_iter([Some(1), None]);
1100        assert_eq!(v.to_string(), "{1,NULL}");
1101    }
1102
1103    #[test]
1104    fn test_serialize_deserialize() {
1105        let value = ListValue::from_iter([Some("abcd"), Some(""), None, Some("a")]);
1106        let list_ref = value.as_scalar_ref();
1107        let mut serializer = memcomparable::Serializer::new(vec![]);
1108        serializer.set_reverse(true);
1109        list_ref.memcmp_serialize(&mut serializer).unwrap();
1110        let buf = serializer.into_inner();
1111        let mut deserializer = memcomparable::Deserializer::new(&buf[..]);
1112        deserializer.set_reverse(true);
1113        assert_eq!(
1114            ListValue::memcmp_deserialize(&DataType::Varchar, &mut deserializer).unwrap(),
1115            value
1116        );
1117
1118        let mut builder =
1119            ListArrayBuilder::with_type(0, DataType::List(Box::new(DataType::Varchar)));
1120        builder.append(Some(list_ref));
1121        let array = builder.finish();
1122        let list_ref = array.value_at(0).unwrap();
1123        let mut serializer = memcomparable::Serializer::new(vec![]);
1124        list_ref.memcmp_serialize(&mut serializer).unwrap();
1125        let buf = serializer.into_inner();
1126        let mut deserializer = memcomparable::Deserializer::new(&buf[..]);
1127        assert_eq!(
1128            ListValue::memcmp_deserialize(&DataType::Varchar, &mut deserializer).unwrap(),
1129            value
1130        );
1131    }
1132
1133    #[test]
1134    fn test_memcomparable() {
1135        let cases = [
1136            (
1137                ListValue::from_iter([123, 456]),
1138                ListValue::from_iter([123, 789]),
1139            ),
1140            (
1141                ListValue::from_iter([123, 456]),
1142                ListValue::from_iter([123]),
1143            ),
1144            (
1145                ListValue::from_iter([None, Some("")]),
1146                ListValue::from_iter([None, None::<&str>]),
1147            ),
1148            (
1149                ListValue::from_iter([Some(2)]),
1150                ListValue::from_iter([Some(1), None, Some(3)]),
1151            ),
1152        ];
1153
1154        for (lhs, rhs) in cases {
1155            let lhs_serialized = {
1156                let mut serializer = memcomparable::Serializer::new(vec![]);
1157                lhs.as_scalar_ref()
1158                    .memcmp_serialize(&mut serializer)
1159                    .unwrap();
1160                serializer.into_inner()
1161            };
1162            let rhs_serialized = {
1163                let mut serializer = memcomparable::Serializer::new(vec![]);
1164                rhs.as_scalar_ref()
1165                    .memcmp_serialize(&mut serializer)
1166                    .unwrap();
1167                serializer.into_inner()
1168            };
1169            assert_eq!(lhs_serialized.cmp(&rhs_serialized), lhs.cmp(&rhs));
1170        }
1171    }
1172
1173    #[test]
1174    fn test_listref() {
1175        use crate::array::*;
1176        use crate::types;
1177
1178        let arr = ListArray::from_iter([Some(vec![1, 2, 3]), None, Some(vec![4, 5, 6, 7])]);
1179
1180        // get 3rd ListRef from ListArray
1181        let list_ref = arr.value_at(2).unwrap();
1182        assert_eq!(list_ref, ListValue::from_iter([4, 5, 6, 7]).as_scalar_ref());
1183
1184        // Get 2nd value from ListRef
1185        let scalar = list_ref.get(1).unwrap();
1186        assert_eq!(scalar, Some(types::ScalarRefImpl::Int32(5)));
1187    }
1188
1189    #[test]
1190    fn test_from_to_literal() {
1191        #[track_caller]
1192        fn test(typestr: &str, input: &str, output: Option<&str>) {
1193            let datatype: DataType = typestr.parse().unwrap();
1194            let list = ListValue::from_str(input, &datatype).unwrap();
1195            let actual = list.as_scalar_ref().to_text();
1196            let output = output.unwrap_or(input);
1197            assert_eq!(actual, output);
1198        }
1199
1200        #[track_caller]
1201        fn test_err(typestr: &str, input: &str, err: &str) {
1202            let datatype: DataType = typestr.parse().unwrap();
1203            let actual_err = ListValue::from_str(input, &datatype).unwrap_err();
1204            assert_eq!(actual_err, err);
1205        }
1206
1207        test("varchar[]", "{}", None);
1208        test("varchar[]", "{1 2}", Some(r#"{"1 2"}"#));
1209        test("varchar[]", "{🥵,🤡}", None);
1210        test("varchar[]", r#"{aa\\bb}"#, Some(r#"{"aa\\bb"}"#));
1211        test("int[]", "{1,2,3}", None);
1212        test("varchar[]", r#"{"1,2"}"#, None);
1213        test("varchar[]", r#"{1, ""}"#, Some(r#"{1,""}"#));
1214        test("varchar[]", r#"{"\""}"#, None);
1215        test("varchar[]", r#"{\   }"#, Some(r#"{" "}"#));
1216        test("varchar[]", r#"{\\  }"#, Some(r#"{"\\"}"#));
1217        test("varchar[]", "{nulla}", None);
1218        test("varchar[]", "{null a}", Some(r#"{"null a"}"#));
1219        test(
1220            "varchar[]",
1221            r#"{"null", "NULL", null, NuLL}"#,
1222            Some(r#"{"null","NULL",NULL,NULL}"#),
1223        );
1224        test("varchar[][]", "{{1, 2, 3}, null }", Some("{{1,2,3},NULL}"));
1225        test(
1226            "varchar[][][]",
1227            "{{{1, 2, 3}}, {{4, 5, 6}}}",
1228            Some("{{{1,2,3}},{{4,5,6}}}"),
1229        );
1230        test_err("varchar[]", "()", r#"Array value must start with "{""#);
1231        test_err("varchar[]", "{1,", r#"Unexpected end of input."#);
1232        test_err("varchar[]", "{1,}", r#"Unexpected "}" character."#);
1233        test_err("varchar[]", "{1,,3}", r#"Unexpected "," character."#);
1234        test_err("varchar[]", r#"{"a""b"}"#, r#"Unexpected array element."#);
1235        test_err("varchar[]", r#"{}{"#, r#"Junk after closing right brace."#);
1236    }
1237}
risingwave_common/array/list_array.rs

risingwave_common/array/
list_array.rs
