16353301015

Committed 17 Jul 2025 06:43PM UTC coverage: 80.979% (+0.3%) from 80.704%

Build # 16353301015

Build Type

Pull #3901

github

Committed by

web-flow

Commit Message

Merge db42d2b1b into ac7014e8c

Pull Request Pull Request #3901: feat: duckdb global conversion cache

Run Details

44 of 47 new or added lines in 6 files covered. (93.62%)

566 existing lines in 16 files now uncovered.

41908 of 51752 relevant lines covered (80.98%)

157964.78 hits per line

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

85.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));
        }

        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.with_children(new_children)?
            } 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))
    }
}

#[cfg(test)]
mod tests {
    use crate::{and, lit, or};

    use super::*;

    #[test]
    fn basic_nnf_test() {
        let expr = and(not(and(lit(true), lit(true))), and(lit(true), lit(true)));
        let expected = and(
            or(not(lit(true)), not(lit(true))),
            and(lit(true), lit(true)),
        );
        let mut rewriter = NNFVisitor::default();
        let value = expr
            .transform_with_context(&mut rewriter, false)
            .unwrap()
            .result();

        assert_eq!(&value, &expected);
    }
}

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 {	33,008✔
62	let mut visitor = NNFVisitor::default();	33,008✔
63
64	expr.transform_with_context(&mut visitor, false)	33,008✔
65	.vortex_expect("cannot fail")	33,008✔
66	.result()	33,008✔
67	}	33,008✔
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(	149,399✔
78	&mut self,	149,399✔
79	node: &ExprRef,	149,399✔
80	negating: bool,	149,399✔
81	) -> VortexResult<FoldDown<ExprRef, bool>> {	149,399✔
82	if node.is::<NotVTable>() {	149,399✔
83	return Ok(FoldDown::Continue(!negating));	1✔
84	}	149,398✔
85
86	Ok(FoldDown::Continue(negating))	149,398✔
87	}	149,399✔
88
89	fn visit_up(	149,399✔
90	&mut self,	149,399✔
91	node: ExprRef,	149,399✔
92	negating: bool,	149,399✔
93	mut new_children: Vec<ExprRef>,	149,399✔
94	) -> VortexResult<FoldUp<ExprRef>> {	149,399✔
95	let new_node = if node.is::<NotVTable>() {	149,399✔
96	debug_assert_eq!(new_children.len(), 1);	1✔
97	new_children.remove(0)	1✔
98	} else if let Some(binary_expr) = node.as_opt::<BinaryVTable>() {	149,398✔
99	if !negating {	12,051✔
100	node.with_children(new_children)?	12,050✔
101	} else {
102	let new_op = match binary_expr.op() {	1✔
103	Operator::Eq => Operator::NotEq,	×
104	Operator::NotEq => Operator::Eq,	×
UNCOV 105	Operator::Gt => Operator::Lte,	×
UNCOV 106	Operator::Gte => Operator::Lt,	×
UNCOV 107	Operator::Lt => Operator::Gte,	×
UNCOV 108	Operator::Lte => Operator::Gt,	×
109	Operator::And => Operator::Or,	1✔
110	Operator::Or => Operator::And,	×
111	Operator::Add => {
112	vortex_bail!("nnf: type mismatch: cannot negate addition")	×
113	}
114	};
115	let (lhs, rhs) = match binary_expr.op() {	1✔
116	Operator::Or \| Operator::And => {
117	let mut negated_children = new_children;	1✔
118	debug_assert_eq!(negated_children.len(), 2);	1✔
119	let rhs = negated_children.remove(1);	1✔
120	let lhs = negated_children.remove(0);	1✔
121	(lhs, rhs)	1✔
122	}
UNCOV 123	_ => (binary_expr.lhs().clone(), binary_expr.rhs().clone()),	×
124	};
125	BinaryExpr::new(lhs, new_op, rhs).into_expr()	1✔
126	}
127	} else if negating {	137,347✔
128	not(node)	2✔
129	} else {
130	node	137,345✔
131	};
132
133	Ok(FoldUp::Continue(new_node))	149,399✔
134	}	149,399✔
135	}
136
137	#[cfg(test)]
138	mod tests {
139	use crate::{and, lit, or};
140
141	use super::*;
142
143	#[test]
144	fn basic_nnf_test() {	1✔
145	let expr = and(not(and(lit(true), lit(true))), and(lit(true), lit(true)));	1✔
146	let expected = and(	1✔
147	or(not(lit(true)), not(lit(true))),	1✔
148	and(lit(true), lit(true)),	1✔
149	);
150	let mut rewriter = NNFVisitor::default();	1✔
151	let value = expr	1✔
152	.transform_with_context(&mut rewriter, false)	1✔
153	.unwrap()	1✔
154	.result();	1✔
155
156	assert_eq!(&value, &expected);	1✔
157	}	1✔
158	}

vortex-data / vortex / 16353301015

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