16440250234

Committed 22 Jul 2025 09:25AM UTC coverage: 81.473% (-0.07%) from 81.54%

Build # 16440250234

Build Type

push

github

Committed by

web-flow

Commit Message

feat: Refactor traversal logic (#3926)

The main rationale for this change is that I would like to use this
logic elsewhere, but it wasn't touched in a while and needed some
polishing.

I've moved most of the code that deals with actually applying operations
in a certain order into the default implementation of `Node::accept`,
`Node::rewrite` and the `transform_` functions.
A future user of `Node` will only need to fill in the structure of their
tree, getting the fiddly bits OOTB.

This is not a fully-fledged solution for any possible usecase, but its
an attempt at tightening the existing abstractions and leaving something
that could be extended to new or more advanced patterns.

---------

Signed-off-by: Adam Gutglick <adam@spiraldb.com>

Run Details

254 of 298 new or added lines in 8 files covered. (85.23%)

8 existing lines in 3 files now uncovered.

41953 of 51493 relevant lines covered (81.47%)

171685.53 hits per line

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

87.5

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

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

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

use crate::traversal::{Node as _, NodeRewriter, NodeVisitor, Transformed, TraversalOrder};
use crate::{
    BinaryExpr, BinaryVTable, ExprRef, GetItemVTable, IntoExpr, LiteralVTable, NotVTable, Operator,
    not,
};

/// Return an equivalent expression in Negative Normal Form ([NNF](https://en.wikipedia.org/wiki/Negation_normal_form)).
///
/// 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 rewriter = NNFRewriter::default();
    expr.rewrite(&mut rewriter)
        .vortex_expect("cannot fail")
        .value
}

/// Verifies whether the expression is in Negative Normal Form ([NNF](https://en.wikipedia.org/wiki/Negation_normal_form)).
///
/// Note that NNF isn't canonical, different expressions might be logically equivalent but different.
pub fn is_nnf(expr: &ExprRef) -> bool {
    let mut visitor = NNFValidationVisitor::default();
    expr.accept(&mut visitor).vortex_expect("never fails");
    visitor.is_nnf
}

#[derive(Default)]
struct NNFRewriter {}

impl NodeRewriter for NNFRewriter {
    type NodeTy = ExprRef;

    fn visit_down(&mut self, node: Self::NodeTy) -> VortexResult<Transformed<Self::NodeTy>> {
        match node.as_opt::<NotVTable>() {
            None => Ok(Transformed::no(node)),
            Some(not_expr) => {
                let child = not_expr.child();
                if let Some(binary_expr) = child.as_opt::<BinaryVTable>() {
                    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 => (
                            not(binary_expr.lhs().clone()),
                            not(binary_expr.rhs().clone()),
                        ),
                        _ => (binary_expr.lhs().clone(), binary_expr.rhs().clone()),
                    };

                    Ok(Transformed::yes(
                        BinaryExpr::new(lhs, new_op, rhs).into_expr(),
                    ))
                } else if let Some(inner_not_expr) = child.as_opt::<NotVTable>() {
                    Ok(Transformed::yes(inner_not_expr.child().clone()))
                } else {
                    Ok(Transformed::no(node))
                }
            }
        }
    }
}

struct NNFValidationVisitor {
    is_nnf: bool,
}

impl Default for NNFValidationVisitor {
    fn default() -> Self {
        Self { is_nnf: true }
    }
}

impl<'a> NodeVisitor<'a> for NNFValidationVisitor {
    type NodeTy = ExprRef;

    fn visit_down(&mut self, node: &'a Self::NodeTy) -> VortexResult<TraversalOrder> {
        fn expr_is_var(expr: &ExprRef) -> bool {
            expr.is::<LiteralVTable>() || expr.is::<GetItemVTable>()
        }

        if let Some(not_expr) = node.as_opt::<NotVTable>() {
            let is_var = expr_is_var(not_expr.child());
            self.is_nnf &= is_var;
            if !is_var {
                return Ok(TraversalOrder::Stop);
            }
        }

        Ok(TraversalOrder::Continue)
    }
}

#[cfg(test)]
mod tests {
    use rstest::rstest;

    use super::*;
    use crate::{and, col, gt_eq, lit, lt, or};

    #[rstest]
    #[case(
        and(not(and(lit(true), lit(true))), and(lit(true), lit(true))),
        and(or(not(lit(true)), not(lit(true))), and(lit(true), lit(true)))
    )]
    #[case(not(and(col("a"), col("b"))), or(not(col("a")), not(col("b"))))]
    #[case(
        not(and(gt_eq(col("a"), lit(3)), col("b"))),
        or(lt(col("a"), lit(3)), not(col("b")))
    )]
    #[case::double_negation(not(not(col("a"))), col("a"))]
    #[case::triple_negation(not(not(not(col("a")))), not(col("a")))]
    #[case(
        not(and(not(gt_eq(col("a"), lit(3))), col("b"))),
        or(gt_eq(col("a"), lit(3)), not(col("b")))
    )]
    #[case(
        not(and(and(not(gt_eq(col("a"), lit(3))), col("c")), col("b"))),
        or(or(gt_eq(col("a"), lit(3)), not(col("c"))), not(col("b")))
    )]
    fn basic_nnf_test(#[case] input: ExprRef, #[case] expected: ExprRef) {
        let output = nnf(input.clone());

        assert_eq!(
            &output, &expected,
            "\nOriginal expr: {input}\nRewritten expr: {output}\nexpected expr: {expected}"
        );
        assert!(is_nnf(&output));
    }

    #[rstest]
    #[case(not(not(col("a"))), false)]
    #[case(not(not(not(col("a")))), false)]
    #[case(not(col("a")), true)]
    #[case(col("a"), true)]
    fn test_nnf_validation(#[case] expr: ExprRef, #[case] valid: bool) {
        assert_eq!(is_nnf(&expr), valid);
    }
}

1	// SPDX-License-Identifier: Apache-2.0
2	// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4	use vortex_error::{VortexExpect as _, VortexResult, vortex_bail};
5
6	use crate::traversal::{Node as _, NodeRewriter, NodeVisitor, Transformed, TraversalOrder};
7	use crate::{
8	BinaryExpr, BinaryVTable, ExprRef, GetItemVTable, IntoExpr, LiteralVTable, NotVTable, Operator,
9	not,
10	};
11
12	/// Return an equivalent expression in Negative Normal Form ([NNF](https://en.wikipedia.org/wiki/Negation_normal_form)).
13	///
14	/// In NNF, [crate::NotExpr] expressions may only contain terminal nodes such as [Literal](crate::LiteralExpr) or
15	/// [GetItem](crate::GetItemExpr). They may not contain [crate::BinaryExpr], [crate::NotExpr], etc.
16	///
17	/// # Examples
18	///
19	/// Double negation is removed entirely:
20	///
21	/// ```
22	/// use vortex_expr::{not, col};
23	/// use vortex_expr::forms::nnf::nnf;
24	///
25	/// let double_negation = not(not(col("a")));
26	/// let nnfed = nnf(double_negation);
27	/// assert_eq!(&nnfed, &col("a"));
28	/// ```
29	///
30	/// Triple negation becomes single negation:
31	///
32	/// ```
33	/// use vortex_expr::{not, col};
34	/// use vortex_expr::forms::nnf::nnf;
35	///
36	/// let triple_negation = not(not(not(col("a"))));
37	/// let nnfed = nnf(triple_negation);
38	/// assert_eq!(&nnfed, &not(col("a")));
39	/// ```
40	///
41	/// Negation at a high-level is pushed to the leaves, likely increasing the total number nodes:
42	///
43	/// ```
44	/// use vortex_expr::{not, col, and, or};
45	/// use vortex_expr::forms::nnf::nnf;
46	///
47	/// assert_eq!(
48	/// &nnf(not(and(col("a"), col("b")))),
49	/// &or(not(col("a")), not(col("b")))
50	/// );
51	/// ```
52	///
53	/// In Vortex, NNF is extended beyond simple Boolean operators to any Boolean-valued operator:
54	///
55	/// ```
56	/// use vortex_expr::{not, col, and, or, lt, lit, gt_eq};
57	/// use vortex_expr::forms::nnf::nnf;
58	///
59	/// assert_eq!(
60	/// &nnf(not(and(gt_eq(col("a"), lit(3)), col("b")))),
61	/// &or(lt(col("a"), lit(3)), not(col("b")))
62	/// );
63	/// ```
64	pub fn nnf(expr: ExprRef) -> ExprRef {	32,484✔
65	let mut rewriter = NNFRewriter::default();	32,484✔
66	expr.rewrite(&mut rewriter)	32,484✔
67	.vortex_expect("cannot fail")	32,484✔
68	.value	32,484✔
69	}	32,484✔
70
71	/// Verifies whether the expression is in Negative Normal Form ([NNF](https://en.wikipedia.org/wiki/Negation_normal_form)).
72	///
73	/// Note that NNF isn't canonical, different expressions might be logically equivalent but different.
74	pub fn is_nnf(expr: &ExprRef) -> bool {	11✔
75	let mut visitor = NNFValidationVisitor::default();	11✔
76	expr.accept(&mut visitor).vortex_expect("never fails");	11✔
77	visitor.is_nnf	11✔
78	}	11✔
79
80	#[derive(Default)]
81	struct NNFRewriter {}
82
83	impl NodeRewriter for NNFRewriter {
84	type NodeTy = ExprRef;
85
86	fn visit_down(&mut self, node: Self::NodeTy) -> VortexResult<Transformed<Self::NodeTy>> {	147,534✔
87	match node.as_opt::<NotVTable>() {	147,534✔
88	None => Ok(Transformed::no(node)),	147,515✔
89	Some(not_expr) => {	19✔
90	let child = not_expr.child();	19✔
91	if let Some(binary_expr) = child.as_opt::<BinaryVTable>() {	19✔
92	let new_op = match binary_expr.op() {	7✔
NEW 93	Operator::Eq => Operator::NotEq,	×
NEW 94	Operator::NotEq => Operator::Eq,	×
NEW 95	Operator::Gt => Operator::Lte,	×
96	Operator::Gte => Operator::Lt,	1✔
NEW 97	Operator::Lt => Operator::Gte,	×
NEW 98	Operator::Lte => Operator::Gt,	×
99	Operator::And => Operator::Or,	6✔
NEW 100	Operator::Or => Operator::And,	×
101	Operator::Add => {
NEW 102	vortex_bail!("nnf: type mismatch: cannot negate addition")	×
103	}
104	};
105	let (lhs, rhs) = match binary_expr.op() {	7✔
106	Operator::Or \| Operator::And => (	6✔
107	not(binary_expr.lhs().clone()),	6✔
108	not(binary_expr.rhs().clone()),	6✔
109	),	6✔
110	_ => (binary_expr.lhs().clone(), binary_expr.rhs().clone()),	1✔
111	};
112
113	Ok(Transformed::yes(	7✔
114	BinaryExpr::new(lhs, new_op, rhs).into_expr(),	7✔
115	))	7✔
116	} else if let Some(inner_not_expr) = child.as_opt::<NotVTable>() {	12✔
117	Ok(Transformed::yes(inner_not_expr.child().clone()))	4✔
118	} else {
119	Ok(Transformed::no(node))	8✔
120	}
121	}
122	}
123	}	147,534✔
124	}
125
126	struct NNFValidationVisitor {
127	is_nnf: bool,
128	}
129
130	impl Default for NNFValidationVisitor {
131	fn default() -> Self {	11✔
132	Self { is_nnf: true }	11✔
133	}	11✔
134	}
135
136	impl<'a> NodeVisitor<'a> for NNFValidationVisitor {
137	type NodeTy = ExprRef;
138
139	fn visit_down(&mut self, node: &'a Self::NodeTy) -> VortexResult<TraversalOrder> {	56✔
140	fn expr_is_var(expr: &ExprRef) -> bool {	12✔
141	expr.is::<LiteralVTable>() \|\| expr.is::<GetItemVTable>()	12✔
142	}	12✔
143
144	if let Some(not_expr) = node.as_opt::<NotVTable>() {	56✔
145	let is_var = expr_is_var(not_expr.child());	12✔
146	self.is_nnf &= is_var;	12✔
147	if !is_var {	12✔
148	return Ok(TraversalOrder::Stop);	2✔
149	}	10✔
150	}	44✔
151
152	Ok(TraversalOrder::Continue)	54✔
153	}	56✔
154	}
155
156	#[cfg(test)]
157	mod tests {
158	use rstest::rstest;
159
160	use super::*;
161	use crate::{and, col, gt_eq, lit, lt, or};
162
163	#[rstest]
164	#[case(
165	and(not(and(lit(true), lit(true))), and(lit(true), lit(true))),
166	and(or(not(lit(true)), not(lit(true))), and(lit(true), lit(true)))
167	)]
168	#[case(not(and(col("a"), col("b"))), or(not(col("a")), not(col("b"))))]
169	#[case(
170	not(and(gt_eq(col("a"), lit(3)), col("b"))),
171	or(lt(col("a"), lit(3)), not(col("b")))
172	)]
173	#[case::double_negation(not(not(col("a"))), col("a"))]
174	#[case::triple_negation(not(not(not(col("a")))), not(col("a")))]
175	#[case(
176	not(and(not(gt_eq(col("a"), lit(3))), col("b"))),
177	or(gt_eq(col("a"), lit(3)), not(col("b")))
178	)]
179	#[case(
180	not(and(and(not(gt_eq(col("a"), lit(3))), col("c")), col("b"))),
181	or(or(gt_eq(col("a"), lit(3)), not(col("c"))), not(col("b")))
182	)]
183	fn basic_nnf_test(#[case] input: ExprRef, #[case] expected: ExprRef) {
184	let output = nnf(input.clone());
185
186	assert_eq!(
187	&output, &expected,
188	"\nOriginal expr: {input}\nRewritten expr: {output}\nexpected expr: {expected}"
189	);
190	assert!(is_nnf(&output));
191	}
192
193	#[rstest]
194	#[case(not(not(col("a"))), false)]
195	#[case(not(not(not(col("a")))), false)]
196	#[case(not(col("a")), true)]
197	#[case(col("a"), true)]
198	fn test_nnf_validation(#[case] expr: ExprRef, #[case] valid: bool) {
199	assert_eq!(is_nnf(&expr), valid);
200	}
201	}

vortex-data / vortex / 16440250234

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