Skip to main content

vortex_array/arrays/runend/
arbitrary.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use arbitrary::Arbitrary;
5use arbitrary::Result;
6use arbitrary::Unstructured;
7use arbitrary::unstructured::Int;
8use vortex_buffer::Buffer;
9use vortex_error::VortexExpect;
10
11use crate::ArrayRef;
12use crate::IntoArray;
13use crate::arrays::PrimitiveArray;
14use crate::arrays::arbitrary::ArbitraryArray;
15use crate::arrays::arbitrary::ArbitraryArrayConfig;
16use crate::arrays::arbitrary::ArbitraryWith;
17use crate::arrays::runend::RunEnd;
18use crate::arrays::runend::RunEndArray;
19use crate::dtype::DType;
20use crate::dtype::Nullability;
21use crate::dtype::PType;
22use crate::dtype::UnsignedPType;
23use crate::validity::Validity;
24
25/// A wrapper type to implement `Arbitrary` for `RunEndArray`.
26#[derive(Clone, Debug)]
27pub struct ArbitraryRunEndArray(pub RunEndArray);
28
29impl<'a> Arbitrary<'a> for ArbitraryRunEndArray {
30    fn arbitrary(u: &mut Unstructured<'a>) -> Result<Self> {
31        // Pick a random primitive type for values.
32        let ptype: PType = u.arbitrary()?;
33        let nullability: Nullability = u.arbitrary()?;
34        let dtype = DType::Primitive(ptype, nullability);
35        Self::with_dtype(u, &dtype)
36    }
37}
38
39impl ArbitraryRunEndArray {
40    /// Generate an arbitrary RunEndArray with the given dtype for values.
41    ///
42    /// The dtype must be a primitive or boolean type.
43    pub fn with_dtype(u: &mut Unstructured, dtype: &DType) -> Result<Self> {
44        // Number of runs (values/ends pairs)
45        let num_runs = u.int_in_range(0..=20)?;
46
47        if num_runs == 0 {
48            // Empty RunEndArray
49            let ends = unsafe {
50                PrimitiveArray::new_unchecked(Buffer::<u32>::empty(), Validity::NonNullable)
51                    .into_array()
52            };
53            let values = ArbitraryArray::arbitrary_with_config(
54                u,
55                &ArbitraryArrayConfig {
56                    dtype: Some(dtype.clone()),
57                    len: 0..=0,
58                },
59            )?
60            .0;
61            let runend_array = unsafe { RunEnd::new_unchecked(ends, values, 0, 0) };
62            return Ok(ArbitraryRunEndArray(runend_array));
63        }
64
65        // Generate arbitrary values for each run
66        let values = ArbitraryArray::arbitrary_with_config(
67            u,
68            &ArbitraryArrayConfig {
69                dtype: Some(dtype.clone()),
70                len: num_runs..=num_runs,
71            },
72        )?
73        .0;
74
75        let len = u.int_in_range(0..=2048)?;
76        // Generate strictly increasing ends
77        // Each end must be > previous end, and first end must be >= 1
78        let ends = random_strictly_sorted_ends(u, num_runs, len)?;
79
80        let runend_array = unsafe { RunEnd::new_unchecked(ends, values, 0, len) };
81
82        Ok(ArbitraryRunEndArray(runend_array))
83    }
84}
85
86/// Generate a strictly sorted array of run ends.
87///
88/// Returns an array of `num_runs` strictly increasing unsigned integers.
89/// If `target_len` is provided, the last end will be exactly that value.
90fn random_strictly_sorted_ends(
91    u: &mut Unstructured,
92    num_runs: usize,
93    target_len: usize,
94) -> Result<ArrayRef> {
95    // Choose a random unsigned PType for ends
96    let mut ends_ptypes = vec![PType::U8, PType::U16, PType::U32, PType::U64];
97    if target_len >= u8::MAX as usize {
98        ends_ptypes.remove(0);
99    }
100    if target_len >= u16::MAX as usize {
101        ends_ptypes.remove(0);
102    }
103    if target_len >= u32::MAX as usize {
104        ends_ptypes.remove(0);
105    }
106    let ends_ptype = *u.choose(&ends_ptypes)?;
107
108    match ends_ptype {
109        PType::U8 => random_strictly_sorted(
110            u,
111            num_runs,
112            u8::try_from(target_len).vortex_expect("must fit in u8"),
113        ),
114        PType::U16 => random_strictly_sorted(
115            u,
116            num_runs,
117            u16::try_from(target_len).vortex_expect("must fit in u16"),
118        ),
119        PType::U32 => random_strictly_sorted(
120            u,
121            num_runs,
122            u32::try_from(target_len).vortex_expect("must fit in u32"),
123        ),
124        PType::U64 => random_strictly_sorted(
125            u,
126            num_runs,
127            u64::try_from(target_len).vortex_expect("must fit in u64"),
128        ),
129        _ => unreachable!("Only unsigned integer types are valid for ends"),
130    }
131}
132
133fn random_strictly_sorted<T: UnsignedPType + Int>(
134    u: &mut Unstructured,
135    num_runs: usize,
136    target: T,
137) -> Result<ArrayRef> {
138    // Generate strictly increasing values
139    // Start from 0, increment by at least 1 each time
140    let mut ends: Vec<T> = Vec::with_capacity(num_runs);
141    let mut current = T::zero();
142
143    for i in 0..num_runs {
144        // Each run must have at least length 1, so increment by at least 1
145        let increment = match i == num_runs - 1 {
146            true => {
147                // Last element should reach target_len
148                if target > current {
149                    target - current
150                } else {
151                    T::one()
152                }
153            }
154            false => {
155                // Random increment between 1 and 10
156                u.int_in_range(T::one()..=T::from(10).vortex_expect("10 will fit in all T"))?
157            }
158        };
159        current += increment;
160        ends.push(current);
161    }
162
163    Ok(PrimitiveArray::new(Buffer::copy_from(ends), Validity::NonNullable).into_array())
164}