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

60.71

/vortex-expr/src/forms/nnf.rs

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

use vortex_error::{VortexExpect, VortexResult, vortex_bail};

use crate::traversal::{FoldDown, FoldUp, FolderMut, Node as _};
use crate::{BinaryExpr, BinaryVTable, ExprRef, IntoExpr, NotVTable, Operator, not};

/// Return an equivalent expression in Negative Normal Form (NNF).
///
/// In NNF, [crate::NotExpr] expressions may only contain terminal nodes such as [Literal](crate::LiteralExpr) or
/// [GetItem](crate::GetItemExpr). They *may not* contain [crate::BinaryExpr], [crate::NotExpr], etc.
///
/// # Examples
///
/// Double negation is removed entirely:
///
/// ```
/// use vortex_expr::{not, col};
/// use vortex_expr::forms::nnf::nnf;
///
/// let double_negation = not(not(col("a")));
/// let nnfed = nnf(double_negation);
/// assert_eq!(&nnfed, &col("a"));
/// ```
///
/// Triple negation becomes single negation:
///
/// ```
/// use vortex_expr::{not, col};
/// use vortex_expr::forms::nnf::nnf;
///
/// let triple_negation = not(not(not(col("a"))));
/// let nnfed = nnf(triple_negation);
/// assert_eq!(&nnfed, &not(col("a")));
/// ```
///
/// Negation at a high-level is pushed to the leaves, likely increasing the total number nodes:
///
/// ```
/// use vortex_expr::{not, col, and, or};
/// use vortex_expr::forms::nnf::nnf;
///
/// assert_eq!(
///     &nnf(not(and(col("a"), col("b")))),
///     &or(not(col("a")), not(col("b")))
/// );
/// ```
///
/// In Vortex, NNF is extended beyond simple Boolean operators to any Boolean-valued operator:
///
/// ```
/// use vortex_expr::{not, col, and, or, lt, lit, gt_eq};
/// use vortex_expr::forms::nnf::nnf;
///
/// assert_eq!(
///     &nnf(not(and(gt_eq(col("a"), lit(3)), col("b")))),
///     &or(lt(col("a"), lit(3)), not(col("b")))
/// );
/// ```
pub fn nnf(expr: ExprRef) -> ExprRef {
    let mut visitor = NNFVisitor::default();

    expr.transform_with_context(&mut visitor, false)
        .vortex_expect("cannot fail")
        .result()
}

#[derive(Default)]
struct NNFVisitor {}

impl FolderMut for NNFVisitor {
    type NodeTy = ExprRef;
    type Out = ExprRef;
    type Context = bool;

    fn visit_down(
        &mut self,
        node: &ExprRef,
        negating: bool,
    ) -> VortexResult<FoldDown<ExprRef, bool>> {
        if node.is::<NotVTable>() {
            return Ok(FoldDown::Continue(!negating));
        } else if let Some(binary_expr) = node.as_opt::<BinaryVTable>() {
            match binary_expr.op() {
                Operator::And | Operator::Or => {
                    return Ok(FoldDown::Continue(negating));
                }
                _ => {}
            }
        }

        Ok(FoldDown::Continue(negating))
    }

    fn visit_up(
        &mut self,
        node: ExprRef,
        negating: bool,
        mut new_children: Vec<ExprRef>,
    ) -> VortexResult<FoldUp<ExprRef>> {
        let new_node = if node.is::<NotVTable>() {
            debug_assert_eq!(new_children.len(), 1);
            new_children.remove(0)
        } else if let Some(binary_expr) = node.as_opt::<BinaryVTable>() {
            if !negating {
                node
            } else {
                let new_op = match binary_expr.op() {
                    Operator::Eq => Operator::NotEq,
                    Operator::NotEq => Operator::Eq,
                    Operator::Gt => Operator::Lte,
                    Operator::Gte => Operator::Lt,
                    Operator::Lt => Operator::Gte,
                    Operator::Lte => Operator::Gt,
                    Operator::And => Operator::Or,
                    Operator::Or => Operator::And,
                    Operator::Add => {
                        vortex_bail!("nnf: type mismatch: cannot negate addition")
                    }
                };
                let (lhs, rhs) = match binary_expr.op() {
                    Operator::Or | Operator::And => {
                        let mut negated_children = new_children;
                        debug_assert_eq!(negated_children.len(), 2);
                        let rhs = negated_children.remove(1);
                        let lhs = negated_children.remove(0);
                        (lhs, rhs)
                    }
                    _ => (binary_expr.lhs().clone(), binary_expr.rhs().clone()),
                };
                BinaryExpr::new(lhs, new_op, rhs).into_expr()
            }
        } else if negating {
            not(node)
        } else {
            node
        };

        Ok(FoldUp::Continue(new_node))
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use vortex_error::{VortexExpect, VortexResult, vortex_bail};
5
6	use crate::traversal::{FoldDown, FoldUp, FolderMut, Node as _};
7	use crate::{BinaryExpr, BinaryVTable, ExprRef, IntoExpr, NotVTable, Operator, not};
8
9	/// Return an equivalent expression in Negative Normal Form (NNF).
10	///
11	/// In NNF, [crate::NotExpr] expressions may only contain terminal nodes such as [Literal](crate::LiteralExpr) or
12	/// [GetItem](crate::GetItemExpr). They may not contain [crate::BinaryExpr], [crate::NotExpr], etc.
13	///
14	/// # Examples
15	///
16	/// Double negation is removed entirely:
17	///
18	/// ```
19	/// use vortex_expr::{not, col};
20	/// use vortex_expr::forms::nnf::nnf;
21	///
22	/// let double_negation = not(not(col("a")));
23	/// let nnfed = nnf(double_negation);
24	/// assert_eq!(&nnfed, &col("a"));
25	/// ```
26	///
27	/// Triple negation becomes single negation:
28	///
29	/// ```
30	/// use vortex_expr::{not, col};
31	/// use vortex_expr::forms::nnf::nnf;
32	///
33	/// let triple_negation = not(not(not(col("a"))));
34	/// let nnfed = nnf(triple_negation);
35	/// assert_eq!(&nnfed, &not(col("a")));
36	/// ```
37	///
38	/// Negation at a high-level is pushed to the leaves, likely increasing the total number nodes:
39	///
40	/// ```
41	/// use vortex_expr::{not, col, and, or};
42	/// use vortex_expr::forms::nnf::nnf;
43	///
44	/// assert_eq!(
45	/// &nnf(not(and(col("a"), col("b")))),
46	/// &or(not(col("a")), not(col("b")))
47	/// );
48	/// ```
49	///
50	/// In Vortex, NNF is extended beyond simple Boolean operators to any Boolean-valued operator:
51	///
52	/// ```
53	/// use vortex_expr::{not, col, and, or, lt, lit, gt_eq};
54	/// use vortex_expr::forms::nnf::nnf;
55	///
56	/// assert_eq!(
57	/// &nnf(not(and(gt_eq(col("a"), lit(3)), col("b")))),
58	/// &or(lt(col("a"), lit(3)), not(col("b")))
59	/// );
60	/// ```
61	pub fn nnf(expr: ExprRef) -> ExprRef {	7,969✔
62	let mut visitor = NNFVisitor::default();	7,969✔
63		7,969✔
64	expr.transform_with_context(&mut visitor, false)	7,969✔
65	.vortex_expect("cannot fail")	7,969✔
66	.result()	7,969✔
67	}	7,969✔
68
69	#[derive(Default)]
70	struct NNFVisitor {}
71
72	impl FolderMut for NNFVisitor {
73	type NodeTy = ExprRef;
74	type Out = ExprRef;
75	type Context = bool;
76
77	fn visit_down(	22,440✔
78	&mut self,	22,440✔
79	node: &ExprRef,	22,440✔
80	negating: bool,	22,440✔
81	) -> VortexResult<FoldDown<ExprRef, bool>> {	22,440✔
82	if node.is::<NotVTable>() {	22,440✔
UNCOV 83	return Ok(FoldDown::Continue(!negating));	×
84	} else if let Some(binary_expr) = node.as_opt::<BinaryVTable>() {	22,440✔
85	match binary_expr.op() {	2,781✔
86	Operator::And \| Operator::Or => {
87	return Ok(FoldDown::Continue(negating));	730✔
88	}
89	_ => {}	2,051✔
90	}
91	}	19,659✔
92
93	Ok(FoldDown::Continue(negating))	21,710✔
94	}	22,440✔
95
96	fn visit_up(	22,440✔
97	&mut self,	22,440✔
98	node: ExprRef,	22,440✔
99	negating: bool,	22,440✔
100	mut new_children: Vec<ExprRef>,	22,440✔
101	) -> VortexResult<FoldUp<ExprRef>> {	22,440✔
102	let new_node = if node.is::<NotVTable>() {	22,440✔
UNCOV 103	debug_assert_eq!(new_children.len(), 1);	×
104	new_children.remove(0)	×
105	} else if let Some(binary_expr) = node.as_opt::<BinaryVTable>() {	22,440✔
106	if !negating {	2,781✔
107	node	2,781✔
108	} else {
109	let new_op = match binary_expr.op() {	×
110	Operator::Eq => Operator::NotEq,	×
111	Operator::NotEq => Operator::Eq,	×
112	Operator::Gt => Operator::Lte,	×
113	Operator::Gte => Operator::Lt,	×
114	Operator::Lt => Operator::Gte,	×
115	Operator::Lte => Operator::Gt,	×
116	Operator::And => Operator::Or,	×
117	Operator::Or => Operator::And,	×
118	Operator::Add => {
119	vortex_bail!("nnf: type mismatch: cannot negate addition")	×
120	}
121	};
122	let (lhs, rhs) = match binary_expr.op() {	×
123	Operator::Or \| Operator::And => {
124	let mut negated_children = new_children;	×
125	debug_assert_eq!(negated_children.len(), 2);	×
126	let rhs = negated_children.remove(1);	×
127	let lhs = negated_children.remove(0);	×
128	(lhs, rhs)	×
129	}
130	_ => (binary_expr.lhs().clone(), binary_expr.rhs().clone()),	×
131	};
NEW 132	BinaryExpr::new(lhs, new_op, rhs).into_expr()	×
133	}
134	} else if negating {	19,659✔
135	not(node)	×
136	} else {
137	node	19,659✔
138	};
139
140	Ok(FoldUp::Continue(new_node))	22,440✔
141	}	22,440✔
142	}

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