16597135877

Committed 29 Jul 2025 01:13PM UTC coverage: 82.703% (+0.5%) from 82.251%

Build # 16597135877

Build Type

Pull #4043

github

Committed by

web-flow

Commit Message

Merge 8bd111805 into ac81ed44f

Pull Request Pull Request #4043: [chore] conformance testing for TakeFn

Run Details

373 of 390 new or added lines in 10 files covered. (95.64%)

110 existing lines in 12 files now uncovered.

45233 of 54693 relevant lines covered (82.7%)

184858.26 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

76.07

/vortex-array/src/compute/take.rs

// SPDX-License-Identifier: Apache-2.0
// SPDX-FileCopyrightText: Copyright the Vortex contributors

use std::sync::LazyLock;

use arcref::ArcRef;
use vortex_dtype::DType;
use vortex_error::{VortexError, VortexResult, vortex_bail, vortex_err};
use vortex_scalar::Scalar;

use crate::arrays::ConstantArray;
use crate::compute::{ComputeFn, ComputeFnVTable, InvocationArgs, Kernel, Output};
use crate::stats::{Precision, Stat, StatsProviderExt, StatsSet};
use crate::vtable::VTable;
use crate::{Array, ArrayRef, Canonical, IntoArray};

static TAKE_FN: LazyLock<ComputeFn> = LazyLock::new(|| {
    let compute = ComputeFn::new("take".into(), ArcRef::new_ref(&Take));
    for kernel in inventory::iter::<TakeKernelRef> {
        compute.register_kernel(kernel.0.clone());
    }
    compute
});

pub fn take(array: &dyn Array, indices: &dyn Array) -> VortexResult<ArrayRef> {
    if indices.is_empty() {
        return Ok(Canonical::empty(
            &array
                .dtype()
                .union_nullability(indices.dtype().nullability()),
        )
        .into_array());
    }

    TAKE_FN
        .invoke(&InvocationArgs {
            inputs: &[array.into(), indices.into()],
            options: &(),
        })?
        .unwrap_array()
}

pub struct Take;

impl ComputeFnVTable for Take {
    fn invoke(
        &self,
        args: &InvocationArgs,
        kernels: &[ArcRef<dyn Kernel>],
    ) -> VortexResult<Output> {
        let TakeArgs { array, indices } = TakeArgs::try_from(args)?;

        // TODO(ngates): if indices are sorted and unique (strict-sorted), then we should delegate to
        //  the filter function since they're typically optimised for this case.
        // TODO(ngates): if indices min is quite high, we could slice self and offset the indices
        //  such that canonicalize does less work.

        if indices.all_invalid()? {
            return Ok(ConstantArray::new(
                Scalar::null(array.dtype().as_nullable()),
                indices.len(),
            )
            .into_array()
            .into());
        }

        // We know that constant array don't need stats propagation, so we can avoid the overhead of
        // computing derived stats and merging them in.
        let derived_stats = (!array.is_constant()).then(|| derive_take_stats(array));

        let taken = take_impl(array, indices, kernels)?;

        if let Some(derived_stats) = derived_stats {
            let mut stats = taken.statistics().to_owned();
            stats.combine_sets(&derived_stats, array.dtype())?;
            for (stat, val) in stats.into_iter() {
                taken.statistics().set(stat, val)
            }
        }

        Ok(taken.into())
    }

    fn return_dtype(&self, args: &InvocationArgs) -> VortexResult<DType> {
        let TakeArgs { array, indices } = TakeArgs::try_from(args)?;

        if !indices.dtype().is_int() {
            vortex_bail!(
                "Take indices must be an integer type, got {}",
                indices.dtype()
            );
        }

        Ok(array
            .dtype()
            .union_nullability(indices.dtype().nullability()))
    }

    fn return_len(&self, args: &InvocationArgs) -> VortexResult<usize> {
        let TakeArgs { indices, .. } = TakeArgs::try_from(args)?;
        Ok(indices.len())
    }

    fn is_elementwise(&self) -> bool {
        false
    }
}

fn derive_take_stats(arr: &dyn Array) -> StatsSet {
    let stats = arr.statistics().to_owned();

    let is_constant = stats.get_as::<bool>(Stat::IsConstant);

    let mut stats = stats.keep_inexact_stats(&[
        // Cannot create values smaller than min or larger than max
        Stat::Min,
        Stat::Max,
    ]);

    if is_constant == Some(Precision::Exact(true)) {
        // Any combination of elements from a constant array is still const
        stats.set(Stat::IsConstant, Precision::exact(true));
    }

    stats
}

fn take_impl(
    array: &dyn Array,
    indices: &dyn Array,
    kernels: &[ArcRef<dyn Kernel>],
) -> VortexResult<ArrayRef> {
    let args = InvocationArgs {
        inputs: &[array.into(), indices.into()],
        options: &(),
    };

    // First look for a TakeFrom specialized on the indices.
    for kernel in TAKE_FROM_FN.kernels() {
        if let Some(output) = kernel.invoke(&args)? {
            return output.unwrap_array();
        }
    }
    if let Some(output) = indices.invoke(&TAKE_FROM_FN, &args)? {
        return output.unwrap_array();
    }

    // Then look for a Take kernel
    for kernel in kernels {
        if let Some(output) = kernel.invoke(&args)? {
            return output.unwrap_array();
        }
    }
    if let Some(output) = array.invoke(&TAKE_FN, &args)? {
        return output.unwrap_array();
    }

    // Otherwise, canonicalize and try again.
    if !array.is_canonical() {
        log::debug!("No take implementation found for {}", array.encoding_id());
        let canonical = array.to_canonical()?;
        return take(canonical.as_ref(), indices);
    }

    vortex_bail!("No take implementation found for {}", array.encoding_id());
}

struct TakeArgs<'a> {
    array: &'a dyn Array,
    indices: &'a dyn Array,
}

impl<'a> TryFrom<&InvocationArgs<'a>> for TakeArgs<'a> {
    type Error = VortexError;

    fn try_from(value: &InvocationArgs<'a>) -> Result<Self, Self::Error> {
        if value.inputs.len() != 2 {
            vortex_bail!("Expected 2 inputs, found {}", value.inputs.len());
        }
        let array = value.inputs[0]
            .array()
            .ok_or_else(|| vortex_err!("Expected first input to be an array"))?;
        let indices = value.inputs[1]
            .array()
            .ok_or_else(|| vortex_err!("Expected second input to be an array"))?;
        Ok(Self { array, indices })
    }
}

pub trait TakeKernel: VTable {
    /// Create a new array by taking the values from the `array` at the
    /// given `indices`.
    ///
    /// # Panics
    ///
    /// Using `indices` that are invalid for the given `array` will cause a panic.
    fn take(&self, array: &Self::Array, indices: &dyn Array) -> VortexResult<ArrayRef>;
}

/// A kernel that implements the filter function.
pub struct TakeKernelRef(pub ArcRef<dyn Kernel>);
inventory::collect!(TakeKernelRef);

#[derive(Debug)]
pub struct TakeKernelAdapter<V: VTable>(pub V);

impl<V: VTable + TakeKernel> TakeKernelAdapter<V> {
    pub const fn lift(&'static self) -> TakeKernelRef {
        TakeKernelRef(ArcRef::new_ref(self))
    }
}

impl<V: VTable + TakeKernel> Kernel for TakeKernelAdapter<V> {
    fn invoke(&self, args: &InvocationArgs) -> VortexResult<Option<Output>> {
        let inputs = TakeArgs::try_from(args)?;
        let Some(array) = inputs.array.as_opt::<V>() else {
            return Ok(None);
        };
        Ok(Some(V::take(&self.0, array, inputs.indices)?.into()))
    }
}

static TAKE_FROM_FN: LazyLock<ComputeFn> = LazyLock::new(|| {
    let compute = ComputeFn::new("take_from".into(), ArcRef::new_ref(&TakeFrom));
    for kernel in inventory::iter::<TakeFromKernelRef> {
        compute.register_kernel(kernel.0.clone());
    }
    compute
});

pub struct TakeFrom;

impl ComputeFnVTable for TakeFrom {
    fn invoke(
        &self,
        _args: &InvocationArgs,
        _kernels: &[ArcRef<dyn Kernel>],
    ) -> VortexResult<Output> {
        vortex_bail!(
            "TakeFrom should not be invoked directly. Its kernels are used to accelerated the Take function"
        )
    }

    fn return_dtype(&self, args: &InvocationArgs) -> VortexResult<DType> {
        Take.return_dtype(args)
    }

    fn return_len(&self, args: &InvocationArgs) -> VortexResult<usize> {
        Take.return_len(args)
    }

    fn is_elementwise(&self) -> bool {
        Take.is_elementwise()
    }
}

pub trait TakeFromKernel: VTable {
    /// Create a new array by taking the values from the `array` at the
    /// given `indices`.
    fn take_from(&self, indices: &Self::Array, array: &dyn Array)
    -> VortexResult<Option<ArrayRef>>;
}

pub struct TakeFromKernelRef(pub ArcRef<dyn Kernel>);
inventory::collect!(TakeFromKernelRef);

#[derive(Debug)]
pub struct TakeFromKernelAdapter<V: VTable>(pub V);

impl<V: VTable + TakeFromKernel> TakeFromKernelAdapter<V> {
    pub const fn lift(&'static self) -> TakeFromKernelRef {
        TakeFromKernelRef(ArcRef::new_ref(self))
    }
}

impl<V: VTable + TakeFromKernel> Kernel for TakeFromKernelAdapter<V> {
    fn invoke(&self, args: &InvocationArgs) -> VortexResult<Option<Output>> {
        let inputs = TakeArgs::try_from(args)?;
        let Some(indices) = inputs.indices.as_opt::<V>() else {
            return Ok(None);
        };
        Ok(V::take_from(&self.0, indices, inputs.array)?.map(Output::from))
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use std::sync::LazyLock;
5
6	use arcref::ArcRef;
7	use vortex_dtype::DType;
8	use vortex_error::{VortexError, VortexResult, vortex_bail, vortex_err};
9	use vortex_scalar::Scalar;
10
11	use crate::arrays::ConstantArray;
12	use crate::compute::{ComputeFn, ComputeFnVTable, InvocationArgs, Kernel, Output};
13	use crate::stats::{Precision, Stat, StatsProviderExt, StatsSet};
14	use crate::vtable::VTable;
15	use crate::{Array, ArrayRef, Canonical, IntoArray};
16
17	static TAKE_FN: LazyLock<ComputeFn> = LazyLock::new(\|\| {	3,430✔
18	let compute = ComputeFn::new("take".into(), ArcRef::new_ref(&Take));	3,430✔
19	for kernel in inventory::iter::<TakeKernelRef> {	48,858✔
20	compute.register_kernel(kernel.0.clone());	45,428✔
21	}	45,428✔
22	compute	3,430✔
23	});	3,430✔
24
25	pub fn take(array: &dyn Array, indices: &dyn Array) -> VortexResult<ArrayRef> {	55,266✔
26	if indices.is_empty() {	55,266✔
27	return Ok(Canonical::empty(	3,766✔
28	&array	3,766✔
29	.dtype()	3,766✔
30	.union_nullability(indices.dtype().nullability()),	3,766✔
31	)	3,766✔
32	.into_array());	3,766✔
33	}	51,500✔
34
35	TAKE_FN	51,500✔
36	.invoke(&InvocationArgs {	51,500✔
37	inputs: &[array.into(), indices.into()],	51,500✔
38	options: &(),	51,500✔
39	})?	51,500✔
40	.unwrap_array()	51,462✔
41	}	55,266✔
42
43	pub struct Take;
44
45	impl ComputeFnVTable for Take {
46	fn invoke(	51,500✔
47	&self,	51,500✔
48	args: &InvocationArgs,	51,500✔
49	kernels: &[ArcRef<dyn Kernel>],	51,500✔
50	) -> VortexResult<Output> {	51,500✔
51	let TakeArgs { array, indices } = TakeArgs::try_from(args)?;	51,500✔
52
53	// TODO(ngates): if indices are sorted and unique (strict-sorted), then we should delegate to
54	// the filter function since they're typically optimised for this case.
55	// TODO(ngates): if indices min is quite high, we could slice self and offset the indices
56	// such that canonicalize does less work.
57
58	if indices.all_invalid()? {	51,500✔
59	return Ok(ConstantArray::new(	355✔
60	Scalar::null(array.dtype().as_nullable()),	355✔
61	indices.len(),	355✔
62	)	355✔
63	.into_array()	355✔
64	.into());	355✔
65	}	51,145✔
66
67	// We know that constant array don't need stats propagation, so we can avoid the overhead of
68	// computing derived stats and merging them in.
69	let derived_stats = (!array.is_constant()).then(\|\| derive_take_stats(array));	51,145✔
70
71	let taken = take_impl(array, indices, kernels)?;	51,145✔
72
73	if let Some(derived_stats) = derived_stats {	51,107✔
74	let mut stats = taken.statistics().to_owned();	43,802✔
75	stats.combine_sets(&derived_stats, array.dtype())?;	43,802✔
76	for (stat, val) in stats.into_iter() {	44,002✔
77	taken.statistics().set(stat, val)	3,596✔
78	}
79	}	7,305✔
80
81	Ok(taken.into())	51,107✔
82	}	51,500✔
83
84	fn return_dtype(&self, args: &InvocationArgs) -> VortexResult<DType> {	51,500✔
85	let TakeArgs { array, indices } = TakeArgs::try_from(args)?;	51,500✔
86
87	if !indices.dtype().is_int() {	51,500✔
88	vortex_bail!(	×
89	"Take indices must be an integer type, got {}",	×
90	indices.dtype()	×
91	);
92	}	51,500✔
93
94	Ok(array	51,500✔
95	.dtype()	51,500✔
96	.union_nullability(indices.dtype().nullability()))	51,500✔
97	}	51,500✔
98
99	fn return_len(&self, args: &InvocationArgs) -> VortexResult<usize> {	51,500✔
100	let TakeArgs { indices, .. } = TakeArgs::try_from(args)?;	51,500✔
101	Ok(indices.len())	51,500✔
102	}	51,500✔
103
104	fn is_elementwise(&self) -> bool {	51,500✔
105	false	51,500✔
106	}	51,500✔
107	}
108
109	fn derive_take_stats(arr: &dyn Array) -> StatsSet {	43,840✔
110	let stats = arr.statistics().to_owned();	43,840✔
111
112	let is_constant = stats.get_as::<bool>(Stat::IsConstant);	43,840✔
113
114	let mut stats = stats.keep_inexact_stats(&[	43,840✔
115	// Cannot create values smaller than min or larger than max	43,840✔
116	Stat::Min,	43,840✔
117	Stat::Max,	43,840✔
118	]);	43,840✔
119
120	if is_constant == Some(Precision::Exact(true)) {	43,840✔
121	// Any combination of elements from a constant array is still const	×
122	stats.set(Stat::IsConstant, Precision::exact(true));	×
123	}	43,840✔
124
125	stats	43,840✔
126	}	43,840✔
127
128	fn take_impl(	51,145✔
129	array: &dyn Array,	51,145✔
130	indices: &dyn Array,	51,145✔
131	kernels: &[ArcRef<dyn Kernel>],	51,145✔
132	) -> VortexResult<ArrayRef> {	51,145✔
133	let args = InvocationArgs {	51,145✔
134	inputs: &[array.into(), indices.into()],	51,145✔
135	options: &(),	51,145✔
136	};	51,145✔
137
138	// First look for a TakeFrom specialized on the indices.
139	for kernel in TAKE_FROM_FN.kernels() {	51,145✔
140	if let Some(output) = kernel.invoke(&args)? {	7,190✔
141	return output.unwrap_array();	16✔
142	}	7,174✔
143	}
144	if let Some(output) = indices.invoke(&TAKE_FROM_FN, &args)? {	51,129✔
145	return output.unwrap_array();	×
146	}	51,129✔
147
148	// Then look for a Take kernel
149	for kernel in kernels {	517,724✔
150	if let Some(output) = kernel.invoke(&args)? {	517,724✔
151	return output.unwrap_array();	51,091✔
152	}	466,595✔
153	}
UNCOV 154	if let Some(output) = array.invoke(&TAKE_FN, &args)? {	×
155	return output.unwrap_array();	×
UNCOV 156	}	×
157
158	// Otherwise, canonicalize and try again.
UNCOV 159	if !array.is_canonical() {	×
UNCOV 160	log::debug!("No take implementation found for {}", array.encoding_id());	×
UNCOV 161	let canonical = array.to_canonical()?;	×
UNCOV 162	return take(canonical.as_ref(), indices);	×
163	}	×
164
165	vortex_bail!("No take implementation found for {}", array.encoding_id());	×
166	}	51,145✔
167
168	struct TakeArgs<'a> {
169	array: &'a dyn Array,
170	indices: &'a dyn Array,
171	}
172
173	impl<'a> TryFrom<&InvocationArgs<'a>> for TakeArgs<'a> {
174	type Error = VortexError;
175
176	fn try_from(value: &InvocationArgs<'a>) -> Result<Self, Self::Error> {	679,414✔
177	if value.inputs.len() != 2 {	679,414✔
178	vortex_bail!("Expected 2 inputs, found {}", value.inputs.len());	×
179	}	679,414✔
180	let array = value.inputs[0]	679,414✔
181	.array()	679,414✔
182	.ok_or_else(\|\| vortex_err!("Expected first input to be an array"))?;	679,414✔
183	let indices = value.inputs[1]	679,414✔
184	.array()	679,414✔
185	.ok_or_else(\|\| vortex_err!("Expected second input to be an array"))?;	679,414✔
186	Ok(Self { array, indices })	679,414✔
187	}	679,414✔
188	}
189
190	pub trait TakeKernel: VTable {
191	/// Create a new array by taking the values from the `array` at the
192	/// given `indices`.
193	///
194	/// # Panics
195	///
196	/// Using `indices` that are invalid for the given `array` will cause a panic.
197	fn take(&self, array: &Self::Array, indices: &dyn Array) -> VortexResult<ArrayRef>;
198	}
199
200	/// A kernel that implements the filter function.
201	pub struct TakeKernelRef(pub ArcRef<dyn Kernel>);
202	inventory::collect!(TakeKernelRef);
203
204	#[derive(Debug)]
205	pub struct TakeKernelAdapter<V: VTable>(pub V);
206
207	impl<V: VTable + TakeKernel> TakeKernelAdapter<V> {
208	pub const fn lift(&'static self) -> TakeKernelRef {	×
209	TakeKernelRef(ArcRef::new_ref(self))	×
210	}	×
211	}
212
213	impl<V: VTable + TakeKernel> Kernel for TakeKernelAdapter<V> {
214	fn invoke(&self, args: &InvocationArgs) -> VortexResult<Option<Output>> {	491,473✔
215	let inputs = TakeArgs::try_from(args)?;	491,473✔
216	let Some(array) = inputs.array.as_opt::<V>() else {	491,473✔
217	return Ok(None);	459,040✔
218	};
219	Ok(Some(V::take(&self.0, array, inputs.indices)?.into()))	32,433✔
220	}	491,473✔
221	}
222
223	static TAKE_FROM_FN: LazyLock<ComputeFn> = LazyLock::new(\|\| {	3,390✔
224	let compute = ComputeFn::new("take_from".into(), ArcRef::new_ref(&TakeFrom));	3,390✔
225	for kernel in inventory::iter::<TakeFromKernelRef> {	4,076✔
226	compute.register_kernel(kernel.0.clone());	686✔
227	}	686✔
228	compute	3,390✔
229	});	3,390✔
230
231	pub struct TakeFrom;
232
233	impl ComputeFnVTable for TakeFrom {
234	fn invoke(	×
235	&self,	×
236	_args: &InvocationArgs,	×
237	_kernels: &[ArcRef<dyn Kernel>],	×
238	) -> VortexResult<Output> {	×
239	vortex_bail!(	×
240	"TakeFrom should not be invoked directly. Its kernels are used to accelerated the Take function"	×
241	)
242	}	×
243
244	fn return_dtype(&self, args: &InvocationArgs) -> VortexResult<DType> {	×
245	Take.return_dtype(args)	×
246	}	×
247
248	fn return_len(&self, args: &InvocationArgs) -> VortexResult<usize> {	×
249	Take.return_len(args)	×
250	}	×
251
252	fn is_elementwise(&self) -> bool {	×
253	Take.is_elementwise()	×
254	}	×
255	}
256
257	pub trait TakeFromKernel: VTable {
258	/// Create a new array by taking the values from the `array` at the
259	/// given `indices`.
260	fn take_from(&self, indices: &Self::Array, array: &dyn Array)
261	-> VortexResult<Option<ArrayRef>>;
262	}
263
264	pub struct TakeFromKernelRef(pub ArcRef<dyn Kernel>);
265	inventory::collect!(TakeFromKernelRef);
266
267	#[derive(Debug)]
268	pub struct TakeFromKernelAdapter<V: VTable>(pub V);
269
270	impl<V: VTable + TakeFromKernel> TakeFromKernelAdapter<V> {
271	pub const fn lift(&'static self) -> TakeFromKernelRef {	×
272	TakeFromKernelRef(ArcRef::new_ref(self))	×
273	}	×
274	}
275
276	impl<V: VTable + TakeFromKernel> Kernel for TakeFromKernelAdapter<V> {
277	fn invoke(&self, args: &InvocationArgs) -> VortexResult<Option<Output>> {	699✔
278	let inputs = TakeArgs::try_from(args)?;	699✔
279	let Some(indices) = inputs.indices.as_opt::<V>() else {	699✔
280	return Ok(None);	683✔
281	};
282	Ok(V::take_from(&self.0, indices, inputs.array)?.map(Output::from))	16✔
283	}	699✔
284	}

vortex-data / vortex / 16597135877

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous