Skip to main content

vortex_array/arrays/chunked/compute/
take.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use itertools::Itertools;
5use num_traits::AsPrimitive;
6use vortex_buffer::Buffer;
7use vortex_buffer::BufferAllocatorRef;
8use vortex_buffer::BufferMut;
9use vortex_error::VortexResult;
10use vortex_error::vortex_bail;
11use vortex_error::vortex_ensure_eq;
12use vortex_error::vortex_err;
13use vortex_mask::Mask;
14
15use crate::ArrayRef;
16use crate::Canonical;
17use crate::Columnar;
18use crate::IntoArray;
19use crate::array::ArrayView;
20use crate::arrays::Chunked;
21use crate::arrays::ChunkedArray;
22use crate::arrays::ConstantArray;
23use crate::arrays::FixedSizeListArray;
24use crate::arrays::PiecewiseSequence;
25use crate::arrays::PiecewiseSequenceArray;
26use crate::arrays::PrimitiveArray;
27use crate::arrays::chunked::ChunkedArrayExt;
28use crate::arrays::dict::TakeExecute;
29use crate::arrays::piecewise_sequence::constant_unsigned_usize;
30use crate::arrays::piecewise_sequence::maybe_contiguous_slices;
31use crate::arrays::primitive::PrimitiveArrayExt;
32use crate::builders::ArrayBuilder;
33use crate::builders::builder_with_capacity_in;
34use crate::builtins::ArrayBuiltins;
35use crate::dtype::DType;
36use crate::dtype::PType;
37use crate::executor::ExecutionCtx;
38use crate::match_each_unsigned_integer_ptype;
39use crate::validity::Validity;
40
41/// Flattens per-chunk take/filter results into a single array. Flat dtypes append directly into
42/// a canonical builder; nested dtypes collect the chunks and canonicalize them as a chunked
43/// array, which reuses the chunks' children zero-copy.
44enum ChunkFlattener {
45    Builder(Box<dyn ArrayBuilder>),
46    Chunks(Vec<ArrayRef>),
47}
48
49impl ChunkFlattener {
50    fn new(dtype: &DType, capacity: usize, allocator: &BufferAllocatorRef) -> Self {
51        if dtype.is_nested() {
52            Self::Chunks(Vec::new())
53        } else {
54            Self::Builder(builder_with_capacity_in(dtype, capacity, allocator))
55        }
56    }
57
58    fn push(&mut self, chunk: ArrayRef, ctx: &mut ExecutionCtx) -> VortexResult<()> {
59        match self {
60            Self::Builder(builder) => chunk.append_to_builder(builder.as_mut(), ctx),
61            Self::Chunks(chunks) => {
62                chunks.push(chunk);
63                Ok(())
64            }
65        }
66    }
67
68    fn finish(self, dtype: &DType, ctx: &mut ExecutionCtx) -> VortexResult<ArrayRef> {
69        match self {
70            Self::Builder(mut builder) => Ok(builder.finish()),
71            // SAFETY: every chunk is a filter or take of a chunk of a chunked array with `dtype`,
72            // which leaves the dtype unchanged.
73            Self::Chunks(chunks) => unsafe { ChunkedArray::new_unchecked(chunks, dtype.clone()) }
74                .into_array()
75                .execute::<Canonical>(ctx)
76                .map(IntoArray::into_array),
77        }
78    }
79}
80
81fn take_chunked_via_sort(
82    array: ArrayView<'_, Chunked>,
83    indices: &PrimitiveArray,
84    indices_mask: Mask,
85    ctx: &mut ExecutionCtx,
86) -> VortexResult<ArrayRef> {
87    let indices_values = indices.as_slice::<u64>();
88    let n = indices_values.len();
89    let mut pairs: Vec<(u64, usize)> = indices_values
90        .iter()
91        .enumerate()
92        .filter(|&(position, _)| indices_mask.value(position))
93        .map(|(position, &index)| (index, position))
94        .collect();
95    pairs.sort_unstable();
96
97    if let Some(&(index, _)) = pairs.last() {
98        let index = usize::try_from(index)?;
99        if index >= array.len() {
100            vortex_bail!(
101                "index {} out of bounds from {} to {}",
102                index,
103                0,
104                array.len()
105            );
106        }
107    }
108
109    let chunk_offsets = array.chunk_offset_values();
110    let nchunks = array.nchunks();
111    let mut flattener = ChunkFlattener::new(array.dtype(), pairs.len(), ctx.allocator());
112    let mut final_take = BufferMut::<u64>::zeroed(n);
113    let mut cursor = 0usize;
114    let mut dedup_idx = 0u64;
115
116    for chunk_idx in 0..nchunks {
117        let chunk_start = chunk_offsets[chunk_idx];
118        let chunk_end = chunk_offsets[chunk_idx + 1];
119        let chunk_len = chunk_end - chunk_start;
120        let chunk_end_u64 = u64::try_from(chunk_end)?;
121        let range_end = cursor + pairs[cursor..].partition_point(|&(v, _)| v < chunk_end_u64);
122        let chunk_pairs = &pairs[cursor..range_end];
123
124        if !chunk_pairs.is_empty() {
125            let mut local_indices = Vec::new();
126            for (i, &(value, original_position)) in chunk_pairs.iter().enumerate() {
127                if cursor + i > 0 && value != pairs[cursor + i - 1].0 {
128                    dedup_idx += 1;
129                }
130                let local_index = usize::try_from(value)? - chunk_start;
131                if local_indices.last() != Some(&local_index) {
132                    local_indices.push(local_index);
133                }
134                final_take[original_position] = dedup_idx;
135            }
136
137            flattener.push(
138                array
139                    .chunk(chunk_idx)
140                    .filter(Mask::from_indices(chunk_len, local_indices))?,
141                ctx,
142            )?;
143        }
144
145        cursor = range_end;
146    }
147
148    let flat = flattener.finish(array.dtype(), ctx)?;
149    let take_validity = Validity::from_mask(indices_mask, indices.dtype().nullability());
150    flat.take(PrimitiveArray::new(final_take.freeze(), take_validity).into_array())
151}
152
153fn valid_indices_are_monotonic(indices: &[u64], indices_mask: &Mask) -> bool {
154    let mut previous = None;
155    for (position, &index) in indices.iter().enumerate() {
156        if !indices_mask.value(position) {
157            continue;
158        }
159        if previous.is_some_and(|previous| index < previous) {
160            return false;
161        }
162        previous = Some(index);
163    }
164    true
165}
166
167// TODO(joe): we want to return a chunked array ideally.
168fn take_chunked(
169    array: ArrayView<'_, Chunked>,
170    indices: &ArrayRef,
171    ctx: &mut ExecutionCtx,
172) -> VortexResult<ArrayRef> {
173    let indices = indices
174        .cast(DType::Primitive(PType::U64, indices.dtype().nullability()))?
175        .execute::<PrimitiveArray>(ctx)?;
176
177    let indices_mask = indices
178        .as_ref()
179        .validity()?
180        .execute_mask(indices.as_ref().len(), ctx)?;
181    let indices_values = indices.as_slice::<u64>();
182    let n = indices_values.len();
183    let chunk_offsets = array.chunk_offset_values();
184    let nchunks = array.nchunks();
185
186    // Strictly increasing non-nullable indices select every row at most once and in order, so the
187    // per-chunk gathers concatenate straight into the result with no dedup or reorder take.
188    if !indices.as_ref().dtype().is_nullable() && indices_values.is_sorted_by(|a, b| a < b) {
189        return take_chunked_sorted(array, indices_values);
190    }
191
192    // For a small unsorted fixed-size-list take over a small number of chunks, sorting has lower
193    // fixed overhead and lets the nested elements filter in source order. Larger, monotonic, and
194    // non-nested takes use bucketing.
195    if matches!(array.dtype(), DType::FixedSizeList(..))
196        && n <= 64
197        && nchunks <= 16
198        && !valid_indices_are_monotonic(indices_values, &indices_mask)
199    {
200        return take_chunked_via_sort(array, &indices, indices_mask, ctx);
201    }
202
203    // Route each valid index into its source chunk. Within each bucket, preserve the request order
204    // so the taken chunks can be assembled and then restored to the original cross-chunk order.
205    let mut buckets = vec![Vec::<(u64, usize)>::new(); nchunks];
206    let mut monotonic = true;
207    let mut last_index = None;
208    let mut sorted_chunk_idx = 0;
209
210    for (original_position, &index) in indices_values.iter().enumerate() {
211        if !indices_mask.value(original_position) {
212            continue;
213        }
214
215        let index = usize::try_from(index)?;
216        if index >= array.len() {
217            vortex_bail!(
218                "index {} out of bounds from {} to {}",
219                index,
220                0,
221                array.len()
222            );
223        }
224
225        let still_sorted = last_index.is_none_or(|last_index| index >= last_index);
226        let chunk_idx = if monotonic && still_sorted {
227            while chunk_offsets[sorted_chunk_idx + 1] <= index {
228                sorted_chunk_idx += 1;
229            }
230            sorted_chunk_idx
231        } else {
232            monotonic = false;
233            chunk_offsets.partition_point(|&offset| offset <= index) - 1
234        };
235        last_index = Some(index);
236
237        let local_index = u64::try_from(index - chunk_offsets[chunk_idx])?;
238        buckets[chunk_idx].push((local_index, original_position));
239    }
240
241    let mut flattener =
242        ChunkFlattener::new(array.dtype(), indices_mask.true_count(), ctx.allocator());
243    let mut final_take =
244        (!monotonic || indices.dtype().is_nullable()).then(|| BufferMut::<u64>::zeroed(n));
245    let mut grouped_position = 0u64;
246
247    for (chunk_idx, bucket) in buckets.into_iter().enumerate() {
248        if bucket.is_empty() {
249            continue;
250        }
251
252        let mut local_indices = BufferMut::<u64>::with_capacity(bucket.len());
253        for (local_index, original_position) in bucket {
254            local_indices.push(local_index);
255            if let Some(final_take) = &mut final_take {
256                final_take[original_position] = grouped_position;
257            }
258            grouped_position += 1;
259        }
260
261        let local_indices =
262            PrimitiveArray::new(local_indices.freeze(), Validity::NonNullable).into_array();
263        flattener.push(array.chunk(chunk_idx).take(local_indices)?, ctx)?;
264    }
265
266    // TODO(joe): can we relax this.
267    let flat = flattener.finish(array.dtype(), ctx)?;
268
269    // Non-nullable monotonic indices are already in the same order as the assembled chunks, so no
270    // final reorder is needed.
271    let Some(final_take) = final_take else {
272        return Ok(flat);
273    };
274
275    // A single take restores original order and expands duplicates. Carrying the original index
276    // validity makes null indices produce null outputs.
277    let take_validity = Validity::from_mask(indices_mask, indices.dtype().nullability());
278    flat.take(PrimitiveArray::new(final_take.freeze(), take_validity).into_array())
279}
280
281/// Take for strictly increasing, non-nullable indices: every row is selected at most once and in
282/// order, so the per-chunk gathers concatenate directly into the result with no bucketing, dedup,
283/// or reorder take.
284fn take_chunked_sorted(
285    array: ArrayView<'_, Chunked>,
286    indices_values: &[u64],
287) -> VortexResult<ArrayRef> {
288    let chunk_offsets = array.chunk_offset_values();
289    let mut chunks = Vec::new();
290    let mut cursor = 0usize;
291
292    // Skip straight to the chunk holding the first index instead of walking every leading chunk;
293    // `<=` steps past empty chunks sharing the same offset.
294    let first_chunk = match indices_values.first() {
295        Some(&first) => {
296            let first = usize::try_from(first)?;
297            chunk_offsets
298                .partition_point(|&offset| offset <= first)
299                .saturating_sub(1)
300        }
301        None => 0,
302    };
303
304    for chunk_idx in first_chunk..array.nchunks() {
305        if cursor == indices_values.len() {
306            break;
307        }
308        let chunk_start = chunk_offsets[chunk_idx];
309        let chunk_end = chunk_offsets[chunk_idx + 1];
310        let chunk_end_u64 = u64::try_from(chunk_end)?;
311
312        let range_end = cursor + indices_values[cursor..].partition_point(|&v| v < chunk_end_u64);
313        if range_end > cursor {
314            let chunk_start_u64 = u64::try_from(chunk_start)?;
315            let mut local_indices = BufferMut::<u64>::with_capacity(range_end - cursor);
316            for &val in &indices_values[cursor..range_end] {
317                local_indices.push(val - chunk_start_u64);
318            }
319            let local_indices =
320                PrimitiveArray::new(local_indices.freeze(), Validity::NonNullable).into_array();
321            chunks.push(array.chunk(chunk_idx).take(local_indices)?);
322        }
323        cursor = range_end;
324    }
325    if cursor != indices_values.len() {
326        vortex_bail!(
327            "index {} out of bounds from {} to {}",
328            usize::try_from(indices_values[cursor])?,
329            0,
330            array.as_ref().len()
331        );
332    }
333
334    if chunks.len() == 1 {
335        return Ok(chunks.swap_remove(0));
336    }
337    // SAFETY: every chunk is a take of a chunk of `array` with non-nullable indices, which
338    // leaves the dtype unchanged.
339    Ok(unsafe { ChunkedArray::new_unchecked(chunks, array.dtype().clone()) }.into_array())
340}
341
342impl TakeExecute for Chunked {
343    fn take(
344        array: ArrayView<'_, Chunked>,
345        indices: &ArrayRef,
346        ctx: &mut ExecutionCtx,
347    ) -> VortexResult<Option<ArrayRef>> {
348        if array.nchunks() == 1 {
349            return array.chunk(0).take(indices.clone()).map(Some);
350        }
351
352        if let Some(taken) = take_chunked_fsl(array, indices, ctx)? {
353            return Ok(Some(taken));
354        }
355
356        if let Some(piecewise_indices) = indices.as_opt::<PiecewiseSequence>()
357            && let Some(taken) = take_piecewise_chunked(array, piecewise_indices, ctx)?
358        {
359            return Ok(Some(taken));
360        }
361
362        take_chunked(array, indices, ctx).map(Some)
363    }
364}
365
366/// Rewrites take over a chunked fixed-size list array as take over a single
367/// [`FixedSizeListArray`]. The swizzle is structural: FSL-encoded chunks execute to themselves,
368/// so their elements chain zero-copy, and the FSL take then gathers per-chunk element runs
369/// instead of taking each chunk.
370fn take_chunked_fsl(
371    array: ArrayView<'_, Chunked>,
372    indices: &ArrayRef,
373    ctx: &mut ExecutionCtx,
374) -> VortexResult<Option<ArrayRef>> {
375    if !matches!(array.dtype(), DType::FixedSizeList(..)) {
376        return Ok(None);
377    }
378
379    let fsl = array.as_ref().clone().execute::<FixedSizeListArray>(ctx)?;
380    fsl.into_array().take(indices.clone()).map(Some)
381}
382
383/// A per-chunk gather plan: chunk-local sub-piece runs to take from one chunk, in output order.
384#[derive(Default)]
385struct ChunkGather {
386    starts: Vec<u64>,
387    lengths: Vec<u64>,
388    total: usize,
389}
390
391/// Take for [`PiecewiseSequence`] indices with unit multipliers.
392///
393/// Each piece is a contiguous index run, so instead of expanding one index per element, pieces
394/// are split at chunk boundaries and gathered from each chunk with a chunk-local
395/// `PiecewiseSequenceArray`. Sub-pieces that visit chunks in non-decreasing order concatenate
396/// directly into the result; otherwise the gathered chunks are flattened once and a second
397/// piecewise take restores output order.
398fn take_piecewise_chunked(
399    array: ArrayView<'_, Chunked>,
400    indices: ArrayView<'_, PiecewiseSequence>,
401    ctx: &mut ExecutionCtx,
402) -> VortexResult<Option<ArrayRef>> {
403    let Some((starts, lengths)) = maybe_contiguous_slices(indices, ctx)? else {
404        return Ok(None);
405    };
406
407    let output_len = indices.as_ref().len();
408    let starts: Vec<usize> = match_each_unsigned_integer_ptype!(starts.ptype(), |S| {
409        starts
410            .as_slice::<S>()
411            .iter()
412            .map(|&start| start.as_())
413            .collect()
414    });
415    let lengths: Vec<usize> = match lengths {
416        Columnar::Constant(lengths) => vec![constant_unsigned_usize(&lengths); starts.len()],
417        Columnar::Canonical(lengths) => {
418            let lengths = lengths.into_primitive();
419            match_each_unsigned_integer_ptype!(lengths.ptype(), |L| {
420                lengths
421                    .as_slice::<L>()
422                    .iter()
423                    .map(|&length| length.as_())
424                    .collect()
425            })
426        }
427    };
428
429    let array_len = array.as_ref().len();
430    let chunk_offsets = array.chunk_offset_values();
431    let nchunks = array.nchunks();
432
433    let mut plans: Vec<ChunkGather> = Vec::new();
434    plans.resize_with(nchunks, ChunkGather::default);
435    // Sub-pieces in output order: (chunk index, offset within that chunk's gathered output, run
436    // length).
437    let mut sub_pieces: Vec<(usize, usize, usize)> = Vec::with_capacity(starts.len());
438    let mut monotonic = true;
439    let mut prev_chunk = 0usize;
440    let mut total_len = 0usize;
441
442    for (&start, &length) in starts.iter().zip_eq(&lengths) {
443        if length == 0 {
444            continue;
445        }
446        let end = start
447            .checked_add(length)
448            .ok_or_else(|| vortex_err!("PiecewiseSequenceArray range overflows usize"))?;
449        if end > array_len {
450            vortex_bail!(
451                "index {} out of bounds from {} to {}",
452                end - 1,
453                0,
454                array_len
455            );
456        }
457        total_len = total_len
458            .checked_add(length)
459            .ok_or_else(|| vortex_err!("PiecewiseSequenceArray output length overflows usize"))?;
460
461        // Locate the chunk containing `start`; `<=` skips empty chunks sharing the same offset.
462        let mut chunk_idx = chunk_offsets.partition_point(|&offset| offset <= start) - 1;
463        let mut cursor = start;
464        let mut remaining = length;
465        while remaining > 0 {
466            while chunk_offsets[chunk_idx + 1] <= cursor {
467                chunk_idx += 1;
468            }
469            let run = remaining.min(chunk_offsets[chunk_idx + 1] - cursor);
470            monotonic &= chunk_idx >= prev_chunk;
471            prev_chunk = chunk_idx;
472
473            let plan = &mut plans[chunk_idx];
474            // Consecutive sub-pieces in the same chunk stay adjacent in its gathered output, so
475            // they merge into one reorder run.
476            match sub_pieces.last_mut() {
477                Some((last_chunk, _, last_run)) if *last_chunk == chunk_idx => *last_run += run,
478                _ => sub_pieces.push((chunk_idx, plan.total, run)),
479            }
480            // A run that continues exactly where the chunk's previous run ended extends it, so
481            // contiguous spans gather as one run.
482            let local_start = (cursor - chunk_offsets[chunk_idx]) as u64;
483            match (plan.starts.last(), plan.lengths.last_mut()) {
484                (Some(&prev_start), Some(prev_len)) if prev_start + *prev_len == local_start => {
485                    *prev_len += run as u64;
486                }
487                _ => {
488                    plan.starts.push(local_start);
489                    plan.lengths.push(run as u64);
490                }
491            }
492            plan.total += run;
493
494            cursor += run;
495            remaining -= run;
496        }
497    }
498
499    vortex_ensure_eq!(
500        total_len,
501        output_len,
502        "PiecewiseSequenceArray expanded length does not match declared length",
503    );
504
505    // Chunks visited in order: the per-chunk gathers already concatenate into the result.
506    if monotonic {
507        let mut gathered = Vec::new();
508        for (chunk_idx, plan) in plans.into_iter().enumerate() {
509            if plan.starts.is_empty() {
510                continue;
511            }
512            gathered.push(gather_chunk(array.chunk(chunk_idx), plan)?);
513        }
514        let result = if gathered.len() == 1 {
515            gathered.swap_remove(0)
516        } else {
517            // SAFETY: every gathered chunk is a take of a chunk with dtype `array.dtype()`, and
518            // the non-nullable piecewise indices leave the dtype unchanged.
519            unsafe { ChunkedArray::new_unchecked(gathered, array.dtype().clone()) }.into_array()
520        };
521        return Ok(Some(result));
522    }
523
524    // Out-of-order sub-pieces: flatten the per-chunk gathers, then take the sub-piece runs from
525    // the flattened result in output order.
526    let mut bases = vec![0usize; nchunks];
527    let mut running = 0usize;
528    let mut flattener = ChunkFlattener::new(array.dtype(), output_len, ctx.allocator());
529    for (chunk_idx, plan) in plans.into_iter().enumerate() {
530        if plan.starts.is_empty() {
531            continue;
532        }
533        bases[chunk_idx] = running;
534        running += plan.total;
535        flattener.push(gather_chunk(array.chunk(chunk_idx), plan)?, ctx)?;
536    }
537    let flat = flattener.finish(array.dtype(), ctx)?;
538
539    let mut reorder_starts = Vec::with_capacity(sub_pieces.len());
540    let mut reorder_lengths = Vec::with_capacity(sub_pieces.len());
541    for &(chunk_idx, offset, run) in &sub_pieces {
542        reorder_starts.push((bases[chunk_idx] + offset) as u64);
543        reorder_lengths.push(run as u64);
544    }
545    flat.take(contiguous_runs(reorder_starts, reorder_lengths, output_len))
546        .map(Some)
547}
548
549/// Gathers a chunk's planned runs: a single run is a zero-copy slice, multiple runs become a
550/// chunk-local piecewise take.
551fn gather_chunk(chunk: &ArrayRef, plan: ChunkGather) -> VortexResult<ArrayRef> {
552    if let [start] = plan.starts.as_slice() {
553        let start = usize::try_from(*start)?;
554        return chunk.slice(start..start + plan.total);
555    }
556    chunk.take(contiguous_runs(plan.starts, plan.lengths, plan.total))
557}
558
559/// Builds a `PiecewiseSequenceArray` of contiguous (unit multiplier) runs whose lengths sum to
560/// `total`.
561fn contiguous_runs(starts: Vec<u64>, lengths: Vec<u64>, total: usize) -> ArrayRef {
562    let count = starts.len();
563    debug_assert_eq!(count, lengths.len());
564    let starts = PrimitiveArray::new(Buffer::from(starts), Validity::NonNullable).into_array();
565    let lengths = match lengths.first() {
566        Some(&first) if lengths.iter().all(|&length| length == first) => {
567            ConstantArray::new(first, count).into_array()
568        }
569        _ => PrimitiveArray::new(Buffer::from(lengths), Validity::NonNullable).into_array(),
570    };
571    let multipliers = ConstantArray::new(1u64, count).into_array();
572    // SAFETY: starts, lengths, and multipliers are non-nullable u64 arrays of equal length, and
573    // `total` is the sum of the lengths.
574    unsafe { PiecewiseSequenceArray::new_unchecked(starts, lengths, multipliers, total) }
575        .into_array()
576}
577
578#[cfg(test)]
579mod tests {
580    use std::sync::LazyLock;
581
582    use vortex_buffer::Buffer;
583    use vortex_buffer::bitbuffer;
584    use vortex_buffer::buffer;
585    use vortex_error::VortexResult;
586    use vortex_session::VortexSession;
587
588    use crate::ArrayRef;
589    use crate::Canonical;
590    use crate::IntoArray;
591    use crate::VortexSessionExecute;
592    use crate::arrays::BoolArray;
593    use crate::arrays::ChunkedArray;
594    use crate::arrays::ConstantArray;
595    use crate::arrays::FixedSizeListArray;
596    use crate::arrays::PiecewiseSequenceArray;
597    use crate::arrays::PrimitiveArray;
598    use crate::arrays::StructArray;
599    use crate::arrays::chunked::ChunkedArrayExt;
600    use crate::assert_arrays_eq;
601    use crate::compute::conformance::take::test_take_conformance;
602    use crate::dtype::DType;
603    use crate::dtype::FieldNames;
604    use crate::dtype::Nullability;
605    use crate::dtype::PType;
606    use crate::scalar::Scalar;
607    use crate::validity::Validity;
608
609    static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
610
611    fn chunked_i32() -> VortexResult<ChunkedArray> {
612        ChunkedArray::try_new(
613            vec![
614                buffer![0i32, 1, 2, 3, 4].into_array(),
615                buffer![5i32, 6, 7, 8, 9].into_array(),
616                buffer![10i32, 11, 12, 13, 14].into_array(),
617            ],
618            DType::Primitive(PType::I32, Nullability::NonNullable),
619        )
620    }
621
622    fn contiguous_pieces(starts: &[u64], lengths: &[u64]) -> VortexResult<ArrayRef> {
623        let len = usize::try_from(lengths.iter().sum::<u64>())?;
624        Ok(PiecewiseSequenceArray::try_new(
625            starts.iter().copied().collect::<Buffer<u64>>().into_array(),
626            lengths
627                .iter()
628                .copied()
629                .collect::<Buffer<u64>>()
630                .into_array(),
631            ConstantArray::new(1u64, starts.len()).into_array(),
632            len,
633        )?
634        .into_array())
635    }
636
637    #[test]
638    fn test_take_piecewise_monotonic_spanning_chunks() -> VortexResult<()> {
639        let mut ctx = SESSION.create_execution_ctx();
640        let arr = chunked_i32()?;
641
642        // The second piece crosses the first chunk boundary, the third spans the last two chunks.
643        let indices = contiguous_pieces(&[1, 4, 9], &[3, 4, 6])?;
644        let result = arr.take(indices)?;
645
646        assert_arrays_eq!(
647            result,
648            PrimitiveArray::from_iter([1i32, 2, 3, 4, 5, 6, 7, 9, 10, 11, 12, 13, 14]),
649            &mut ctx
650        );
651        Ok(())
652    }
653
654    #[test]
655    fn test_take_piecewise_interleaved() -> VortexResult<()> {
656        let mut ctx = SESSION.create_execution_ctx();
657        let arr = chunked_i32()?;
658
659        // Pieces visit chunks out of order, forcing the reorder take.
660        let indices = contiguous_pieces(&[12, 2, 7, 0], &[3, 2, 3, 1])?;
661        let result = arr.take(indices)?;
662
663        assert_arrays_eq!(
664            result,
665            PrimitiveArray::from_iter([12i32, 13, 14, 2, 3, 7, 8, 9, 0]),
666            &mut ctx
667        );
668        Ok(())
669    }
670
671    #[test]
672    fn test_take_piecewise_whole_array() -> VortexResult<()> {
673        let mut ctx = SESSION.create_execution_ctx();
674        let arr = chunked_i32()?;
675
676        let indices = contiguous_pieces(&[0], &[15])?;
677        let result = arr.take(indices)?;
678
679        assert_arrays_eq!(result, PrimitiveArray::from_iter(0i32..15), &mut ctx);
680        Ok(())
681    }
682
683    #[test]
684    fn test_take_piecewise_across_empty_chunk() -> VortexResult<()> {
685        let mut ctx = SESSION.create_execution_ctx();
686        let arr = ChunkedArray::try_new(
687            vec![
688                buffer![0i32, 1, 2, 3, 4].into_array(),
689                PrimitiveArray::empty::<i32>(Nullability::NonNullable).into_array(),
690                buffer![5i32, 6, 7, 8, 9].into_array(),
691            ],
692            DType::Primitive(PType::I32, Nullability::NonNullable),
693        )?;
694
695        let indices = contiguous_pieces(&[3], &[4])?;
696        let result = arr.take(indices)?;
697
698        assert_arrays_eq!(result, PrimitiveArray::from_iter([3i32, 4, 5, 6]), &mut ctx);
699        Ok(())
700    }
701
702    #[test]
703    fn test_take_piecewise_adjacent_pieces_merge() -> VortexResult<()> {
704        let mut ctx = SESSION.create_execution_ctx();
705        let arr = chunked_i32()?;
706
707        // The first two pieces are contiguous within one chunk, so they merge into a single run
708        // that gathers as a zero-copy slice.
709        let indices = contiguous_pieces(&[0, 2, 7], &[2, 2, 2])?;
710        let result = arr.take(indices)?;
711
712        assert_arrays_eq!(
713            result,
714            PrimitiveArray::from_iter([0i32, 1, 2, 3, 7, 8]),
715            &mut ctx
716        );
717        Ok(())
718    }
719
720    #[test]
721    fn test_take_piecewise_same_chunk_out_of_order() -> VortexResult<()> {
722        let mut ctx = SESSION.create_execution_ctx();
723        let arr = chunked_i32()?;
724
725        // Non-contiguous pieces in the same chunk must stay separate runs in piece order.
726        let indices = contiguous_pieces(&[2, 0], &[2, 2])?;
727        let result = arr.take(indices)?;
728
729        assert_arrays_eq!(result, PrimitiveArray::from_iter([2i32, 3, 0, 1]), &mut ctx);
730        Ok(())
731    }
732
733    #[test]
734    fn test_take_piecewise_zero_length_pieces() -> VortexResult<()> {
735        let mut ctx = SESSION.create_execution_ctx();
736        let arr = chunked_i32()?;
737
738        let indices = contiguous_pieces(&[5, 0, 2], &[0, 4, 0])?;
739        let result = arr.take(indices)?;
740
741        assert_arrays_eq!(result, PrimitiveArray::from_iter([0i32, 1, 2, 3]), &mut ctx);
742        Ok(())
743    }
744
745    #[test]
746    fn test_take_piecewise_out_of_bounds() -> VortexResult<()> {
747        let mut ctx = SESSION.create_execution_ctx();
748        let arr = chunked_i32()?;
749
750        let indices = contiguous_pieces(&[12], &[5])?;
751        let result = arr
752            .take(indices)
753            .and_then(|taken| taken.execute::<Canonical>(&mut ctx));
754
755        assert!(result.is_err());
756        Ok(())
757    }
758
759    #[test]
760    fn test_take_piecewise_non_unit_multiplier() -> VortexResult<()> {
761        let mut ctx = SESSION.create_execution_ctx();
762        let arr = chunked_i32()?;
763
764        // Multiplier 2 falls back to the generic path but must stay correct.
765        let indices = PiecewiseSequenceArray::try_new(
766            buffer![0u64, 1].into_array(),
767            buffer![5u64, 3].into_array(),
768            buffer![2u64, 4].into_array(),
769            8,
770        )?
771        .into_array();
772        let result = arr.take(indices)?;
773
774        assert_arrays_eq!(
775            result,
776            PrimitiveArray::from_iter([0i32, 2, 4, 6, 8, 1, 5, 9]),
777            &mut ctx
778        );
779        Ok(())
780    }
781
782    #[test]
783    fn test_take_piecewise_nullable_values() -> VortexResult<()> {
784        let mut ctx = SESSION.create_execution_ctx();
785        let arr = ChunkedArray::try_new(
786            vec![
787                PrimitiveArray::from_option_iter([Some(0i32), None, Some(2)]).into_array(),
788                PrimitiveArray::from_option_iter([None, Some(4i32), Some(5)]).into_array(),
789            ],
790            DType::Primitive(PType::I32, Nullability::Nullable),
791        )?;
792
793        let indices = contiguous_pieces(&[4, 1], &[2, 3])?;
794        let result = arr.take(indices)?;
795
796        assert_arrays_eq!(
797            result,
798            PrimitiveArray::from_option_iter([Some(4i32), Some(5), None, Some(2), None]),
799            &mut ctx
800        );
801        Ok(())
802    }
803
804    #[test]
805    fn test_take_fsl_over_chunked_elements() -> VortexResult<()> {
806        let mut ctx = SESSION.create_execution_ctx();
807        // Chunk boundaries at 8 and 13 do not line up with the list size of 3.
808        let elements = ChunkedArray::try_new(
809            vec![
810                PrimitiveArray::from_iter(0i32..8).into_array(),
811                PrimitiveArray::from_iter(8i32..13).into_array(),
812                PrimitiveArray::from_iter(13i32..18).into_array(),
813            ],
814            DType::Primitive(PType::I32, Nullability::NonNullable),
815        )?
816        .into_array();
817        let fsl = FixedSizeListArray::try_new(elements, 3, Validity::NonNullable, 6)?;
818
819        let indices = buffer![4u64, 0, 2, 5, 1, 4].into_array();
820        let result = fsl.take(indices)?;
821        let expected = FixedSizeListArray::try_new(
822            PrimitiveArray::from_iter([
823                12i32, 13, 14, 0, 1, 2, 6, 7, 8, 15, 16, 17, 3, 4, 5, 12, 13, 14,
824            ])
825            .into_array(),
826            3,
827            Validity::NonNullable,
828            6,
829        )?;
830
831        assert_arrays_eq!(result, expected, &mut ctx);
832        Ok(())
833    }
834
835    #[test]
836    fn test_take_fsl_over_chunked_elements_conformance() -> VortexResult<()> {
837        let elements = ChunkedArray::try_new(
838            vec![
839                PrimitiveArray::from_iter(0i32..8).into_array(),
840                PrimitiveArray::from_iter(8i32..13).into_array(),
841                PrimitiveArray::from_iter(13i32..18).into_array(),
842            ],
843            DType::Primitive(PType::I32, Nullability::NonNullable),
844        )?
845        .into_array();
846        let fsl = FixedSizeListArray::try_new(elements, 3, Validity::NonNullable, 6)?;
847        test_take_conformance(&fsl.into_array(), &mut SESSION.create_execution_ctx());
848        Ok(())
849    }
850
851    #[test]
852    fn test_take_chunked_fsl() -> VortexResult<()> {
853        let mut ctx = SESSION.create_execution_ctx();
854        let c0 = FixedSizeListArray::try_new(
855            PrimitiveArray::from_iter(0i32..6).into_array(),
856            2,
857            Validity::NonNullable,
858            3,
859        )?;
860        let c1 = FixedSizeListArray::try_new(
861            PrimitiveArray::from_iter(6i32..10).into_array(),
862            2,
863            Validity::NonNullable,
864            2,
865        )?;
866        let dtype = c0.dtype().clone();
867        let arr = ChunkedArray::try_new(vec![c0.into_array(), c1.into_array()], dtype)?;
868
869        let indices = buffer![4u64, 0, 3, 3, 1].into_array();
870        let result = arr.take(indices)?;
871        let expected = FixedSizeListArray::try_new(
872            PrimitiveArray::from_iter([8i32, 9, 0, 1, 6, 7, 6, 7, 2, 3]).into_array(),
873            2,
874            Validity::NonNullable,
875            5,
876        )?;
877
878        assert_arrays_eq!(result, expected, &mut ctx);
879        Ok(())
880    }
881
882    #[test]
883    fn test_take_chunked_fsl_nullable() -> VortexResult<()> {
884        let mut ctx = SESSION.create_execution_ctx();
885        let c0 = FixedSizeListArray::try_new(
886            PrimitiveArray::from_iter(0i32..6).into_array(),
887            2,
888            Validity::Array(bitbuffer![1 0 1].into_array()),
889            3,
890        )?;
891        let c1 = FixedSizeListArray::try_new(
892            PrimitiveArray::from_iter(6i32..10).into_array(),
893            2,
894            Validity::AllValid,
895            2,
896        )?;
897        let dtype = c0.dtype().clone();
898        let arr = ChunkedArray::try_new(vec![c0.into_array(), c1.into_array()], dtype)?;
899
900        let indices =
901            PrimitiveArray::from_option_iter([Some(4u64), None, Some(0), Some(1)]).into_array();
902        let result = arr.take(indices)?;
903        let expected = FixedSizeListArray::try_new(
904            PrimitiveArray::from_iter([8i32, 9, 0, 0, 0, 1, 0, 0]).into_array(),
905            2,
906            Validity::Array(bitbuffer![1 0 1 0].into_array()),
907            4,
908        )?;
909
910        assert_arrays_eq!(result, expected, &mut ctx);
911        Ok(())
912    }
913
914    #[test]
915    fn test_take_chunked_fsl_non_fsl_chunk() -> VortexResult<()> {
916        let mut ctx = SESSION.create_execution_ctx();
917        let c0 = FixedSizeListArray::try_new(
918            PrimitiveArray::from_iter(0i32..6).into_array(),
919            2,
920            Validity::NonNullable,
921            3,
922        )?;
923        let c1 = FixedSizeListArray::try_new(
924            PrimitiveArray::from_iter(6i32..10).into_array(),
925            2,
926            Validity::NonNullable,
927            2,
928        )?;
929        let dtype = c0.dtype().clone();
930        // Wrap one chunk in a nested chunked array so it is not FSL-encoded; the dtype-based
931        // swizzle must still handle it.
932        let nested = ChunkedArray::try_new(vec![c1.into_array()], dtype.clone())?;
933        let arr = ChunkedArray::try_new(vec![c0.into_array(), nested.into_array()], dtype)?;
934
935        let indices = buffer![4u64, 0, 3, 1].into_array();
936        let result = arr.take(indices)?;
937        let expected = FixedSizeListArray::try_new(
938            PrimitiveArray::from_iter([8i32, 9, 0, 1, 6, 7, 2, 3]).into_array(),
939            2,
940            Validity::NonNullable,
941            4,
942        )?;
943
944        assert_arrays_eq!(result, expected, &mut ctx);
945        Ok(())
946    }
947
948    #[test]
949    fn test_take_chunked_fsl_constant_chunk() -> VortexResult<()> {
950        let mut ctx = SESSION.create_execution_ctx();
951        let c0 = FixedSizeListArray::try_new(
952            PrimitiveArray::from_iter(0i32..6).into_array(),
953            2,
954            Validity::AllValid,
955            3,
956        )?;
957        let dtype = c0.dtype().clone();
958        // A constant chunk is only logically FSL; the swizzle canonicalizes it in place.
959        let c1 = ConstantArray::new(Scalar::null(dtype.clone()), 2).into_array();
960        let arr = ChunkedArray::try_new(vec![c0.into_array(), c1], dtype)?;
961
962        let indices = buffer![4u64, 0, 3, 1].into_array();
963        let result = arr.take(indices)?;
964        let expected = FixedSizeListArray::try_new(
965            PrimitiveArray::from_iter([0i32, 0, 0, 1, 0, 0, 2, 3]).into_array(),
966            2,
967            Validity::Array(bitbuffer![0 1 0 1].into_array()),
968            4,
969        )?;
970
971        assert_arrays_eq!(result, expected, &mut ctx);
972        Ok(())
973    }
974
975    #[test]
976    fn test_take_piecewise_chunked_fsl() -> VortexResult<()> {
977        let mut ctx = SESSION.create_execution_ctx();
978        let c0 = FixedSizeListArray::try_new(
979            PrimitiveArray::from_iter(0i32..6).into_array(),
980            2,
981            Validity::NonNullable,
982            3,
983        )?;
984        let c1 = FixedSizeListArray::try_new(
985            PrimitiveArray::from_iter(6i32..10).into_array(),
986            2,
987            Validity::NonNullable,
988            2,
989        )?;
990        let dtype = c0.dtype().clone();
991        let arr = ChunkedArray::try_new(vec![c0.into_array(), c1.into_array()], dtype)?;
992        let reference = FixedSizeListArray::try_new(
993            PrimitiveArray::from_iter(0i32..10).into_array(),
994            2,
995            Validity::NonNullable,
996            5,
997        )?;
998
999        // A monotonic run crossing the chunk boundary.
1000        let indices = contiguous_pieces(&[1], &[3])?;
1001        let result = arr.take(indices.clone())?;
1002        assert_arrays_eq!(&result, reference.take(indices)?, &mut ctx);
1003        let expected = FixedSizeListArray::try_new(
1004            PrimitiveArray::from_iter([2i32, 3, 4, 5, 6, 7]).into_array(),
1005            2,
1006            Validity::NonNullable,
1007            3,
1008        )?;
1009        assert_arrays_eq!(result, expected, &mut ctx);
1010
1011        // Out-of-order pieces forcing the reorder take.
1012        let indices = contiguous_pieces(&[3, 0], &[2, 2])?;
1013        let result = arr.take(indices.clone())?;
1014        assert_arrays_eq!(&result, reference.take(indices)?, &mut ctx);
1015        let expected = FixedSizeListArray::try_new(
1016            PrimitiveArray::from_iter([6i32, 7, 8, 9, 0, 1, 2, 3]).into_array(),
1017            2,
1018            Validity::NonNullable,
1019            4,
1020        )?;
1021        assert_arrays_eq!(result, expected, &mut ctx);
1022        Ok(())
1023    }
1024
1025    #[test]
1026    fn test_take_chunked_struct_nested_flatten() -> VortexResult<()> {
1027        let mut ctx = SESSION.create_execution_ctx();
1028        let s0 = StructArray::try_new(
1029            ["a"].into(),
1030            vec![buffer![0i32, 1, 2].into_array()],
1031            3,
1032            Validity::NonNullable,
1033        )?;
1034        let s1 = StructArray::try_new(
1035            ["a"].into(),
1036            vec![buffer![3i32, 4].into_array()],
1037            2,
1038            Validity::NonNullable,
1039        )?;
1040        let dtype = s0.dtype().clone();
1041        let arr = ChunkedArray::try_new(vec![s0.into_array(), s1.into_array()], dtype)?;
1042
1043        let result = arr.take(buffer![4u64, 0, 2, 4].into_array())?;
1044        let expected = StructArray::try_new(
1045            ["a"].into(),
1046            vec![buffer![4i32, 0, 2, 4].into_array()],
1047            4,
1048            Validity::NonNullable,
1049        )?;
1050
1051        assert_arrays_eq!(result, expected, &mut ctx);
1052        Ok(())
1053    }
1054
1055    #[test]
1056    fn test_take_chunked_fsl_conformance() -> VortexResult<()> {
1057        let c0 = FixedSizeListArray::try_new(
1058            PrimitiveArray::from_iter(0i32..6).into_array(),
1059            2,
1060            Validity::NonNullable,
1061            3,
1062        )?;
1063        let c1 = FixedSizeListArray::try_new(
1064            PrimitiveArray::from_iter(6i32..10).into_array(),
1065            2,
1066            Validity::NonNullable,
1067            2,
1068        )?;
1069        let dtype = c0.dtype().clone();
1070        let arr = ChunkedArray::try_new(vec![c0.into_array(), c1.into_array()], dtype)?;
1071        test_take_conformance(&arr.into_array(), &mut SESSION.create_execution_ctx());
1072        Ok(())
1073    }
1074
1075    #[test]
1076    fn test_take() {
1077        let mut ctx = SESSION.create_execution_ctx();
1078        let a = buffer![1i32, 2, 3].into_array();
1079        let arr = ChunkedArray::try_new(vec![a.clone(), a.clone(), a.clone()], a.dtype().clone())
1080            .unwrap();
1081        assert_eq!(arr.nchunks(), 3);
1082        assert_eq!(arr.len(), 9);
1083        let indices = buffer![0u64, 0, 6, 4].into_array();
1084
1085        let result = arr.take(indices).unwrap();
1086        assert_arrays_eq!(result, PrimitiveArray::from_iter([1i32, 1, 1, 2]), &mut ctx);
1087    }
1088
1089    #[test]
1090    fn test_take_nullable_values() {
1091        let mut ctx = SESSION.create_execution_ctx();
1092        let a = PrimitiveArray::new(buffer![1i32, 2, 3], Validity::AllValid).into_array();
1093        let arr = ChunkedArray::try_new(vec![a.clone(), a.clone(), a.clone()], a.dtype().clone())
1094            .unwrap();
1095        assert_eq!(arr.nchunks(), 3);
1096        assert_eq!(arr.len(), 9);
1097        let indices = PrimitiveArray::new(buffer![0u64, 0, 6, 4], Validity::NonNullable);
1098
1099        let result = arr.take(indices.into_array()).unwrap();
1100        assert_arrays_eq!(
1101            result,
1102            PrimitiveArray::from_option_iter([1i32, 1, 1, 2].map(Some)),
1103            &mut ctx
1104        );
1105    }
1106
1107    #[test]
1108    fn test_take_nullable_indices() {
1109        let mut ctx = SESSION.create_execution_ctx();
1110        let a = buffer![1i32, 2, 3].into_array();
1111        let arr = ChunkedArray::try_new(vec![a.clone(), a.clone(), a.clone()], a.dtype().clone())
1112            .unwrap();
1113        assert_eq!(arr.nchunks(), 3);
1114        assert_eq!(arr.len(), 9);
1115        let indices = PrimitiveArray::new(
1116            buffer![0u64, 0, 6, 4],
1117            Validity::Array(bitbuffer![1 0 0 1].into_array()),
1118        );
1119
1120        let result = arr.take(indices.into_array()).unwrap();
1121        assert_arrays_eq!(
1122            result,
1123            PrimitiveArray::from_option_iter([Some(1i32), None, None, Some(2)]),
1124            &mut ctx
1125        );
1126    }
1127
1128    #[test]
1129    fn test_take_nullable_struct() {
1130        let mut ctx = SESSION.create_execution_ctx();
1131        let struct_array =
1132            StructArray::try_new(FieldNames::default(), vec![], 100, Validity::NonNullable)
1133                .unwrap();
1134
1135        let arr = ChunkedArray::from_iter(vec![
1136            struct_array.clone().into_array(),
1137            struct_array.into_array(),
1138        ]);
1139
1140        let result = arr
1141            .take(PrimitiveArray::from_option_iter(vec![Some(0), None, Some(101)]).into_array())
1142            .unwrap();
1143
1144        let expect = StructArray::try_new(
1145            FieldNames::default(),
1146            vec![],
1147            3,
1148            Validity::Array(BoolArray::from_iter(vec![true, false, true]).into_array()),
1149        )
1150        .unwrap();
1151        assert_arrays_eq!(result, expect, &mut ctx);
1152    }
1153
1154    #[test]
1155    fn test_empty_take() {
1156        let mut ctx = SESSION.create_execution_ctx();
1157        let a = buffer![1i32, 2, 3].into_array();
1158        let arr = ChunkedArray::try_new(vec![a.clone(), a.clone(), a.clone()], a.dtype().clone())
1159            .unwrap();
1160        assert_eq!(arr.nchunks(), 3);
1161        assert_eq!(arr.len(), 9);
1162
1163        let indices = PrimitiveArray::empty::<u64>(Nullability::NonNullable);
1164        let result = arr.take(indices.into_array()).unwrap();
1165
1166        assert!(result.is_empty());
1167        assert_eq!(result.dtype(), arr.dtype());
1168        assert_arrays_eq!(
1169            result,
1170            PrimitiveArray::empty::<i32>(Nullability::NonNullable),
1171            &mut ctx
1172        );
1173    }
1174
1175    #[test]
1176    fn test_take_shuffled_indices() -> VortexResult<()> {
1177        let mut ctx = SESSION.create_execution_ctx();
1178        let c0 = buffer![0i32, 1, 2].into_array();
1179        let c1 = buffer![3i32, 4, 5].into_array();
1180        let c2 = buffer![6i32, 7, 8].into_array();
1181        let arr = ChunkedArray::try_new(
1182            vec![c0, c1, c2],
1183            PrimitiveArray::empty::<i32>(Nullability::NonNullable)
1184                .dtype()
1185                .clone(),
1186        )?;
1187
1188        // Fully shuffled indices that cross every chunk boundary.
1189        let indices = buffer![8u64, 0, 5, 3, 2, 7, 1, 6, 4].into_array();
1190        let result = arr.take(indices)?;
1191
1192        assert_arrays_eq!(
1193            result,
1194            PrimitiveArray::from_iter([8i32, 0, 5, 3, 2, 7, 1, 6, 4]),
1195            &mut ctx
1196        );
1197        Ok(())
1198    }
1199
1200    #[test]
1201    fn test_take_shuffled_duplicates_with_empty_chunks() -> VortexResult<()> {
1202        let mut ctx = SESSION.create_execution_ctx();
1203        let empty = PrimitiveArray::empty::<i32>(Nullability::NonNullable).into_array();
1204        let arr = ChunkedArray::try_new(
1205            vec![
1206                empty.clone(),
1207                buffer![0i32, 1].into_array(),
1208                empty.clone(),
1209                buffer![2i32, 3].into_array(),
1210                empty,
1211            ],
1212            PrimitiveArray::empty::<i32>(Nullability::NonNullable)
1213                .dtype()
1214                .clone(),
1215        )?;
1216
1217        let result = arr.take(buffer![3u64, 0, 2, 0, 3, 1, 2].into_array())?;
1218
1219        assert_arrays_eq!(
1220            result,
1221            PrimitiveArray::from_iter([3i32, 0, 2, 0, 3, 1, 2]),
1222            &mut ctx
1223        );
1224        Ok(())
1225    }
1226
1227    #[test]
1228    fn test_take_small_shuffled_fixed_size_lists() -> VortexResult<()> {
1229        let mut ctx = SESSION.create_execution_ctx();
1230        let first = FixedSizeListArray::new(
1231            buffer![0i32, 1, 2, 3].into_array(),
1232            2,
1233            Validity::NonNullable,
1234            2,
1235        )
1236        .into_array();
1237        let second = FixedSizeListArray::new(
1238            buffer![4i32, 5, 6, 7].into_array(),
1239            2,
1240            Validity::NonNullable,
1241            2,
1242        )
1243        .into_array();
1244        let dtype = first.dtype().clone();
1245        let array = ChunkedArray::try_new(vec![first, second], dtype)?;
1246
1247        let result = array.take(buffer![3u64, 0, 2, 1, 3].into_array())?;
1248        let expected = FixedSizeListArray::new(
1249            buffer![6i32, 7, 0, 1, 4, 5, 2, 3, 6, 7].into_array(),
1250            2,
1251            Validity::NonNullable,
1252            5,
1253        );
1254
1255        assert_arrays_eq!(result, expected, &mut ctx);
1256        Ok(())
1257    }
1258
1259    #[test]
1260    fn test_take_shuffled_large() -> VortexResult<()> {
1261        let mut ctx = SESSION.create_execution_ctx();
1262        let nchunks: i32 = 100;
1263        let chunk_len: i32 = 1_000;
1264        let total = nchunks * chunk_len;
1265
1266        let chunks: Vec<_> = (0..nchunks)
1267            .map(|c| {
1268                let start = c * chunk_len;
1269                PrimitiveArray::from_iter(start..start + chunk_len).into_array()
1270            })
1271            .collect();
1272        let dtype = chunks[0].dtype().clone();
1273        let arr = ChunkedArray::try_new(chunks, dtype)?;
1274
1275        // Fisher-Yates shuffle with a fixed seed for determinism.
1276        let mut indices: Vec<u64> = (0..u64::try_from(total)?).collect();
1277        let mut seed: u64 = 0xdeadbeef;
1278        for i in (1..indices.len()).rev() {
1279            seed = seed.wrapping_mul(6364136223846793005).wrapping_add(1);
1280            let j = (seed >> 33) as usize % (i + 1);
1281            indices.swap(i, j);
1282        }
1283
1284        let indices_arr = PrimitiveArray::new(Buffer::from(indices.clone()), Validity::NonNullable);
1285        let result = arr.take(indices_arr.into_array())?;
1286
1287        // Verify every element.
1288        let result = result.execute::<PrimitiveArray>(&mut ctx)?;
1289        assert_eq!(
1290            result.dtype(),
1291            &DType::Primitive(PType::I32, Nullability::NonNullable)
1292        );
1293        assert_eq!(result.len(), indices.len());
1294        let result_vals = result.as_slice::<i32>();
1295        for (pos, &idx) in indices.iter().enumerate() {
1296            assert_eq!(
1297                result_vals[pos],
1298                i32::try_from(idx)?,
1299                "mismatch at position {pos}"
1300            );
1301        }
1302        Ok(())
1303    }
1304
1305    #[test]
1306    fn test_take_null_indices() -> VortexResult<()> {
1307        let mut ctx = SESSION.create_execution_ctx();
1308        let c0 = buffer![10i32, 20, 30].into_array();
1309        let c1 = buffer![40i32, 50, 60].into_array();
1310        let arr = ChunkedArray::try_new(
1311            vec![c0, c1],
1312            PrimitiveArray::empty::<i32>(Nullability::NonNullable)
1313                .dtype()
1314                .clone(),
1315        )?;
1316
1317        // Indices with nulls scattered across chunk boundaries.
1318        let indices =
1319            PrimitiveArray::from_option_iter([Some(5u64), None, Some(0), Some(3), None, Some(2)]);
1320        let result = arr.take(indices.into_array())?;
1321
1322        assert_arrays_eq!(
1323            result,
1324            PrimitiveArray::from_option_iter([
1325                Some(60i32),
1326                None,
1327                Some(10),
1328                Some(40),
1329                None,
1330                Some(30)
1331            ]),
1332            &mut ctx
1333        );
1334        Ok(())
1335    }
1336
1337    #[test]
1338    fn test_take_sorted_indices() -> VortexResult<()> {
1339        let mut ctx = SESSION.create_execution_ctx();
1340        let arr = chunked_i32()?;
1341
1342        // Strictly increasing indices spanning chunks hit the sorted fast path.
1343        let indices = buffer![1u64, 4, 5, 9, 10, 14].into_array();
1344        let result = arr.take(indices)?;
1345
1346        assert_arrays_eq!(
1347            result,
1348            PrimitiveArray::from_iter([1i32, 4, 5, 9, 10, 14]),
1349            &mut ctx
1350        );
1351        Ok(())
1352    }
1353
1354    #[test]
1355    fn test_take_out_of_bounds() -> VortexResult<()> {
1356        let mut ctx = SESSION.create_execution_ctx();
1357        let arr = chunked_i32()?;
1358
1359        // Sorted indices hit the fast path, unsorted the generic path; both must fail.
1360        for indices in [buffer![0u64, 100], buffer![100u64, 0]] {
1361            let result = arr
1362                .take(indices.into_array())
1363                .and_then(|taken| taken.execute::<Canonical>(&mut ctx));
1364            assert!(result.is_err(), "expected out-of-bounds error");
1365        }
1366        Ok(())
1367    }
1368
1369    #[test]
1370    fn test_take_all_null_indices() -> VortexResult<()> {
1371        let mut ctx = SESSION.create_execution_ctx();
1372        let arr = chunked_i32()?;
1373
1374        let indices = PrimitiveArray::from_option_iter([None::<u64>, None]).into_array();
1375        let result = arr.take(indices)?;
1376
1377        assert_arrays_eq!(
1378            result,
1379            PrimitiveArray::from_option_iter([None::<i32>, None]),
1380            &mut ctx
1381        );
1382        Ok(())
1383    }
1384
1385    #[test]
1386    fn test_take_chunked_conformance() {
1387        let a = buffer![1i32, 2, 3].into_array();
1388        let b = buffer![4i32, 5].into_array();
1389        let arr = ChunkedArray::try_new(
1390            vec![a, b],
1391            PrimitiveArray::empty::<i32>(Nullability::NonNullable)
1392                .dtype()
1393                .clone(),
1394        )
1395        .unwrap();
1396        test_take_conformance(&arr.into_array(), &mut SESSION.create_execution_ctx());
1397
1398        // Test with nullable chunked array
1399        let a = PrimitiveArray::from_option_iter([Some(1i32), None, Some(3)]);
1400        let b = PrimitiveArray::from_option_iter([Some(4i32), Some(5)]);
1401        let dtype = a.dtype().clone();
1402        let arr = ChunkedArray::try_new(vec![a.into_array(), b.into_array()], dtype).unwrap();
1403        test_take_conformance(&arr.into_array(), &mut SESSION.create_execution_ctx());
1404
1405        // Test with multiple identical chunks
1406        let chunk = buffer![10i32, 20, 30, 40, 50].into_array();
1407        let arr = ChunkedArray::try_new(
1408            vec![chunk.clone(), chunk.clone(), chunk.clone()],
1409            chunk.dtype().clone(),
1410        )
1411        .unwrap();
1412        test_take_conformance(&arr.into_array(), &mut SESSION.create_execution_ctx());
1413    }
1414}