16139349253

Committed 08 Jul 2025 09:26AM UTC coverage: 78.057% (-0.2%) from 78.253%

Build # 16139349253

Build Type

push

github

Committed by

web-flow

Commit Message

VortexExpr VTables (#3713)

Adds the same vtable machinery as arrays and layouts already use. It
uses the "Encoding" naming scheme from arrays and layouts. I don't
particularly like it, but it's consistent. Open to renames later.

Further, adds an expression registry to the Vortex session that will be
used for deserialization.

Expressions only decide their "options" serialization. So in theory, can
support many container formats, not just proto, provided each expression
can deserialize their own options format.

---------

Signed-off-by: Nicholas Gates <nick@nickgates.com>

Run Details

800 of 1190 new or added lines in 38 files covered. (67.23%)

40 existing lines in 13 files now uncovered.

44100 of 56497 relevant lines covered (78.06%)

54989.55 hits per line

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

94.91

/vortex-expr/src/transform/match_between.rs

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

use vortex_array::compute::{BetweenOptions, StrictComparison};

use crate::forms::cnf::cnf;
use crate::{
    BetweenExpr, BinaryVTable, ExprRef, GetItemExpr, IntoExpr, LiteralExpr, Operator, and, lit,
};

/// This pass looks for expression of the form
///      `x >= a && x < b` and converts them into x between a and b`
pub fn find_between(expr: ExprRef) -> ExprRef {
    // We search all pairs of cnfs to find any pair of expressions can be converted into a between
    // expression.
    let mut conjuncts = cnf(expr.clone());
    let mut rest = vec![];

    for idx in 0..conjuncts.len() {
        let Some(c) = conjuncts.get(idx).cloned() else {
            continue;
        };
        let mut matched = false;
        for idx2 in (idx + 1)..conjuncts.len() {
            // Since values are removed in iterations there might not be a value at idx2,
            // but all values will have been considered.
            let Some(c2) = conjuncts.get(idx2) else {
                continue;
            };
            if let Some(expr) = maybe_match(&c, c2) {
                rest.push(expr);
                conjuncts.remove(idx2);
                matched = true;
                break;
            }
        }
        if !matched {
            rest.push(c.clone())
        }
    }

    rest.into_iter().reduce(and).unwrap_or_else(|| lit(true))
}

fn maybe_match(lhs: &ExprRef, rhs: &ExprRef) -> Option<ExprRef> {
    let (Some(lhs), Some(rhs)) = (lhs.as_opt::<BinaryVTable>(), rhs.as_opt::<BinaryVTable>())
    else {
        return None;
    };

    // Cannot compare to self
    if lhs.lhs().eq(lhs.rhs()) || rhs.lhs().eq(rhs.rhs()) {
        return None;
    }

    // Extract pairs of comparison of the form (left left_op eq) and (eq right_op right)
    let (eq, left, left_op, right, right_op) =
        if GetItemExpr::is(lhs.lhs()) && lhs.lhs().eq(rhs.lhs()) {
            (
                lhs.lhs().clone(),
                lhs.rhs().clone(),
                lhs.op().swap(),
                rhs.rhs().clone(),
                rhs.op(),
            )
        } else if GetItemExpr::is(lhs.lhs()) && lhs.lhs().eq(rhs.rhs()) {
            (
                lhs.lhs().clone(),
                lhs.rhs().clone(),
                lhs.op().swap(),
                rhs.lhs().clone(),
                rhs.op().swap(),
            )
        } else if GetItemExpr::is(lhs.rhs()) && lhs.rhs().eq(rhs.lhs()) {
            (
                lhs.rhs().clone(),
                lhs.lhs().clone(),
                lhs.op(),
                rhs.rhs().clone(),
                rhs.op(),
            )
        } else if GetItemExpr::is(lhs.rhs()) && lhs.rhs().eq(rhs.rhs()) {
            (
                lhs.rhs().clone(),
                lhs.lhs().clone(),
                lhs.op(),
                rhs.lhs().clone(),
                rhs.op().swap(),
            )
        } else {
            return None;
        };

    // Find the greater op.
    let (Some(left_lit), Some(right_lit)) = (
        LiteralExpr::maybe_from(&left),
        LiteralExpr::maybe_from(&right),
    ) else {
        return None;
    };

    let (left, left_op, right, right_op) = if left_lit.value() > right_lit.value() {
        (right, right_op, left, left_op)
    } else {
        (left, left_op, right, right_op)
    };

    // Check if the operators form an inequality.
    let (left_op, right_op) = if let (Some(left_op), Some(right_op)) = (
        maybe_strict_comparison(left_op),
        maybe_strict_comparison(right_op),
    ) {
        (left_op, right_op)
    } else if let (Some(left_op), Some(right_op)) = (
        maybe_strict_comparison(left_op.swap()),
        maybe_strict_comparison(right_op.swap()),
    ) {
        (left_op, right_op)
    } else {
        return None;
    };

    let expr = BetweenExpr::new(
        eq.clone(),
        left,
        right,
        BetweenOptions {
            lower_strict: left_op,
            upper_strict: right_op,
        },
    );
    Some(expr.into_expr())
}

fn maybe_strict_comparison(op: Operator) -> Option<StrictComparison> {
    match op {
        Operator::Lt => Some(StrictComparison::Strict),
        Operator::Lte => Some(StrictComparison::NonStrict),
        _ => None,
    }
}

#[cfg(test)]
mod tests {
    use vortex_array::compute::{BetweenOptions, StrictComparison};

    use crate::transform::match_between::find_between;
    use crate::{and, between, col, gt_eq, lit, lt};

    #[test]
    fn test_match_between() {
        let expr = and(lt(lit(2), col("x")), gt_eq(lit(5), col("x")));
        let find = find_between(expr);

        // 2 < x <= 5
        assert_eq!(
            &between(
                col("x"),
                lit(2),
                lit(5),
                BetweenOptions {
                    lower_strict: StrictComparison::Strict,
                    upper_strict: StrictComparison::NonStrict,
                }
            ),
            &find
        );
    }

    #[test]
    fn test_match_2_between() {
        let expr = and(gt_eq(col("x"), lit(2)), lt(col("x"), lit(5)));
        let find = find_between(expr);

        // 2 <= x < 5
        assert_eq!(
            &between(
                col("x"),
                lit(2),
                lit(5),
                BetweenOptions {
                    lower_strict: StrictComparison::NonStrict,
                    upper_strict: StrictComparison::Strict,
                }
            ),
            &find
        );
    }

    #[test]
    fn test_match_3_between() {
        let expr = and(gt_eq(col("x"), lit(2)), gt_eq(lit(5), col("x")));
        let find = find_between(expr);

        // 2 <= x < 5
        assert_eq!(
            &between(
                col("x"),
                lit(2),
                lit(5),
                BetweenOptions {
                    lower_strict: StrictComparison::NonStrict,
                    upper_strict: StrictComparison::NonStrict,
                }
            ),
            &find
        );
    }

    #[test]
    fn test_match_4_between() {
        let expr = and(gt_eq(lit(5), col("x")), lt(lit(2), col("x")));
        let find = find_between(expr);

        // 2 < x <= 5
        assert_eq!(
            &between(
                col("x"),
                lit(2),
                lit(5),
                BetweenOptions {
                    lower_strict: StrictComparison::Strict,
                    upper_strict: StrictComparison::NonStrict,
                }
            ),
            &find
        );
    }

    #[test]
    fn test_match_5_between() {
        let expr = and(
            and(gt_eq(col("y"), lit(10)), gt_eq(lit(5), col("x"))),
            lt(lit(2), col("x")),
        );
        let find = find_between(expr);

        // $.y >= 10 /\ 2 < $.x <= 5
        assert_eq!(
            &and(
                gt_eq(col("y"), lit(10)),
                between(
                    col("x"),
                    lit(2),
                    lit(5),
                    BetweenOptions {
                        lower_strict: StrictComparison::Strict,
                        upper_strict: StrictComparison::NonStrict,
                    }
                )
            ),
            &find
        );
    }

    #[test]
    fn test_match_6_between() {
        let expr = and(
            and(gt_eq(lit(5), col("x")), gt_eq(col("y"), lit(10))),
            lt(lit(2), col("x")),
        );
        let find = find_between(expr);

        // $.y >= 10 /\ 2 < $.x <= 5
        assert_eq!(
            &and(
                between(
                    col("x"),
                    lit(2),
                    lit(5),
                    BetweenOptions {
                        lower_strict: StrictComparison::Strict,
                        upper_strict: StrictComparison::NonStrict,
                    }
                ),
                gt_eq(col("y"), lit(10)),
            ),
            &find
        );
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use vortex_array::compute::{BetweenOptions, StrictComparison};
5
6	use crate::forms::cnf::cnf;
7	use crate::{
8	BetweenExpr, BinaryVTable, ExprRef, GetItemExpr, IntoExpr, LiteralExpr, Operator, and, lit,
9	};
10
11	/// This pass looks for expression of the form
12	/// `x >= a && x < b` and converts them into x between a and b`
13	pub fn find_between(expr: ExprRef) -> ExprRef {	7,864✔
14	// We search all pairs of cnfs to find any pair of expressions can be converted into a between	7,864✔
15	// expression.	7,864✔
16	let mut conjuncts = cnf(expr.clone());	7,864✔
17	let mut rest = vec![];	7,864✔
18
19	for idx in 0..conjuncts.len() {	7,873✔
20	let Some(c) = conjuncts.get(idx).cloned() else {	7,733✔
21	continue;	27✔
22	};
23	let mut matched = false;	7,706✔
24	for idx2 in (idx + 1)..conjuncts.len() {	7,706✔
25	// Since values are removed in iterations there might not be a value at idx2,
26	// but all values will have been considered.
27	let Some(c2) = conjuncts.get(idx2) else {	122✔
28	continue;	×
29	};
30	if let Some(expr) = maybe_match(&c, c2) {	122✔
31	rest.push(expr);	27✔
32	conjuncts.remove(idx2);	27✔
33	matched = true;	27✔
34	break;	27✔
35	}	95✔
36	}
37	if !matched {	7,706✔
38	rest.push(c.clone())	7,679✔
39	}	27✔
40	}
41
42	rest.into_iter().reduce(and).unwrap_or_else(\|\| lit(true))	7,864✔
43	}	7,864✔
44
45	fn maybe_match(lhs: &ExprRef, rhs: &ExprRef) -> Option<ExprRef> {	122✔
46	let (Some(lhs), Some(rhs)) = (lhs.as_opt::<BinaryVTable>(), rhs.as_opt::<BinaryVTable>())	122✔
47	else {
48	return None;	8✔
49	};
50
51	// Cannot compare to self
52	if lhs.lhs().eq(lhs.rhs()) \|\| rhs.lhs().eq(rhs.rhs()) {	114✔
53	return None;	×
54	}	114✔
55
56	// Extract pairs of comparison of the form (left left_op eq) and (eq right_op right)
57	let (eq, left, left_op, right, right_op) =	27✔
58	if GetItemExpr::is(lhs.lhs()) && lhs.lhs().eq(rhs.lhs()) {	114✔
59	(	22✔
60	lhs.lhs().clone(),	22✔
61	lhs.rhs().clone(),	22✔
62	lhs.op().swap(),	22✔
63	rhs.rhs().clone(),	22✔
64	rhs.op(),	22✔
65	)	22✔
66	} else if GetItemExpr::is(lhs.lhs()) && lhs.lhs().eq(rhs.rhs()) {	92✔
67	(	1✔
68	lhs.lhs().clone(),	1✔
69	lhs.rhs().clone(),	1✔
70	lhs.op().swap(),	1✔
71	rhs.lhs().clone(),	1✔
72	rhs.op().swap(),	1✔
73	)	1✔
74	} else if GetItemExpr::is(lhs.rhs()) && lhs.rhs().eq(rhs.lhs()) {	91✔
NEW 75	(	×
NEW 76	lhs.rhs().clone(),	×
NEW 77	lhs.lhs().clone(),	×
NEW 78	lhs.op(),	×
NEW 79	rhs.rhs().clone(),	×
NEW 80	rhs.op(),	×
NEW 81	)	×
82	} else if GetItemExpr::is(lhs.rhs()) && lhs.rhs().eq(rhs.rhs()) {	91✔
83	(	4✔
84	lhs.rhs().clone(),	4✔
85	lhs.lhs().clone(),	4✔
86	lhs.op(),	4✔
87	rhs.lhs().clone(),	4✔
88	rhs.op().swap(),	4✔
89	)	4✔
90	} else {
91	return None;	87✔
92	};
93
94	// Find the greater op.
95	let (Some(left_lit), Some(right_lit)) = (	27✔
96	LiteralExpr::maybe_from(&left),	27✔
97	LiteralExpr::maybe_from(&right),	27✔
98	) else {
UNCOV 99	return None;	×
100	};
101
102	let (left, left_op, right, right_op) = if left_lit.value() > right_lit.value() {	27✔
103	(right, right_op, left, left_op)	3✔
104	} else {
105	(left, left_op, right, right_op)	24✔
106	};
107
108	// Check if the operators form an inequality.
109	let (left_op, right_op) = if let (Some(left_op), Some(right_op)) = (	27✔
110	maybe_strict_comparison(left_op),	27✔
111	maybe_strict_comparison(right_op),	27✔
112	) {
113	(left_op, right_op)	24✔
114	} else if let (Some(left_op), Some(right_op)) = (	3✔
115	maybe_strict_comparison(left_op.swap()),	3✔
116	maybe_strict_comparison(right_op.swap()),	3✔
117	) {
118	(left_op, right_op)	3✔
119	} else {
120	return None;	×
121	};
122
123	let expr = BetweenExpr::new(	27✔
124	eq.clone(),	27✔
125	left,	27✔
126	right,	27✔
127	BetweenOptions {	27✔
128	lower_strict: left_op,	27✔
129	upper_strict: right_op,	27✔
130	},	27✔
131	);	27✔
132	Some(expr.into_expr())	27✔
133	}	122✔
134
135	fn maybe_strict_comparison(op: Operator) -> Option<StrictComparison> {	60✔
136	match op {	60✔
137	Operator::Lt => Some(StrictComparison::Strict),	26✔
138	Operator::Lte => Some(StrictComparison::NonStrict),	28✔
139	_ => None,	6✔
140	}
141	}	60✔
142
143	#[cfg(test)]
144	mod tests {
145	use vortex_array::compute::{BetweenOptions, StrictComparison};
146
147	use crate::transform::match_between::find_between;
148	use crate::{and, between, col, gt_eq, lit, lt};
149
150	#[test]
151	fn test_match_between() {	1✔
152	let expr = and(lt(lit(2), col("x")), gt_eq(lit(5), col("x")));	1✔
153	let find = find_between(expr);	1✔
154		1✔
155	// 2 < x <= 5	1✔
156	assert_eq!(	1✔
157	&between(	1✔
158	col("x"),	1✔
159	lit(2),	1✔
160	lit(5),	1✔
161	BetweenOptions {	1✔
162	lower_strict: StrictComparison::Strict,	1✔
163	upper_strict: StrictComparison::NonStrict,	1✔
164	}	1✔
165	),	1✔
166	&find	1✔
167	);	1✔
168	}	1✔
169
170	#[test]
171	fn test_match_2_between() {	1✔
172	let expr = and(gt_eq(col("x"), lit(2)), lt(col("x"), lit(5)));	1✔
173	let find = find_between(expr);	1✔
174		1✔
175	// 2 <= x < 5	1✔
176	assert_eq!(	1✔
177	&between(	1✔
178	col("x"),	1✔
179	lit(2),	1✔
180	lit(5),	1✔
181	BetweenOptions {	1✔
182	lower_strict: StrictComparison::NonStrict,	1✔
183	upper_strict: StrictComparison::Strict,	1✔
184	}	1✔
185	),	1✔
186	&find	1✔
187	);	1✔
188	}	1✔
189
190	#[test]
191	fn test_match_3_between() {	1✔
192	let expr = and(gt_eq(col("x"), lit(2)), gt_eq(lit(5), col("x")));	1✔
193	let find = find_between(expr);	1✔
194		1✔
195	// 2 <= x < 5	1✔
196	assert_eq!(	1✔
197	&between(	1✔
198	col("x"),	1✔
199	lit(2),	1✔
200	lit(5),	1✔
201	BetweenOptions {	1✔
202	lower_strict: StrictComparison::NonStrict,	1✔
203	upper_strict: StrictComparison::NonStrict,	1✔
204	}	1✔
205	),	1✔
206	&find	1✔
207	);	1✔
208	}	1✔
209
210	#[test]
211	fn test_match_4_between() {	1✔
212	let expr = and(gt_eq(lit(5), col("x")), lt(lit(2), col("x")));	1✔
213	let find = find_between(expr);	1✔
214		1✔
215	// 2 < x <= 5	1✔
216	assert_eq!(	1✔
217	&between(	1✔
218	col("x"),	1✔
219	lit(2),	1✔
220	lit(5),	1✔
221	BetweenOptions {	1✔
222	lower_strict: StrictComparison::Strict,	1✔
223	upper_strict: StrictComparison::NonStrict,	1✔
224	}	1✔
225	),	1✔
226	&find	1✔
227	);	1✔
228	}	1✔
229
230	#[test]
231	fn test_match_5_between() {	1✔
232	let expr = and(	1✔
233	and(gt_eq(col("y"), lit(10)), gt_eq(lit(5), col("x"))),	1✔
234	lt(lit(2), col("x")),	1✔
235	);	1✔
236	let find = find_between(expr);	1✔
237		1✔
238	// $.y >= 10 /\ 2 < $.x <= 5	1✔
239	assert_eq!(	1✔
240	&and(	1✔
241	gt_eq(col("y"), lit(10)),	1✔
242	between(	1✔
243	col("x"),	1✔
244	lit(2),	1✔
245	lit(5),	1✔
246	BetweenOptions {	1✔
247	lower_strict: StrictComparison::Strict,	1✔
248	upper_strict: StrictComparison::NonStrict,	1✔
249	}	1✔
250	)	1✔
251	),	1✔
252	&find	1✔
253	);	1✔
254	}	1✔
255
256	#[test]
257	fn test_match_6_between() {	1✔
258	let expr = and(	1✔
259	and(gt_eq(lit(5), col("x")), gt_eq(col("y"), lit(10))),	1✔
260	lt(lit(2), col("x")),	1✔
261	);	1✔
262	let find = find_between(expr);	1✔
263		1✔
264	// $.y >= 10 /\ 2 < $.x <= 5	1✔
265	assert_eq!(	1✔
266	&and(	1✔
267	between(	1✔
268	col("x"),	1✔
269	lit(2),	1✔
270	lit(5),	1✔
271	BetweenOptions {	1✔
272	lower_strict: StrictComparison::Strict,	1✔
273	upper_strict: StrictComparison::NonStrict,	1✔
274	}	1✔
275	),	1✔
276	gt_eq(col("y"), lit(10)),	1✔
277	),	1✔
278	&find	1✔
279	);	1✔
280	}	1✔
281	}

vortex-data / vortex / 16139349253

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