Skip to content

Commit 1c43063

Browse files
authored
fix: stop treating arithmetic negation as bitwise NOT (apache#24668)
## Which issue does this PR address? - Addresses the arithmetic-negation/bitwise portion of apache#24665. - The remaining checked-negation and ordering work stays open in apache#24665 and apache#24683. ## Rationale for this change `Expr::Negative` represents arithmetic unary minus, but the simplifier applied identities for bitwise complement. That changes valid results for expressions combining unary minus with bitwise AND, OR, and XOR. This PR is intentionally narrow. It preserves the existing generic `-(-x) -> x` simplification and does not change physical negation, bounds, pruning, ordering equivalence, or SQL unparsing. ## What changes are included in this PR? - Remove the six bitwise-complement identities that treated `-x` as `~x`. - Stop applying bitwise De Morgan rewrites to arithmetic unary minus. - Retain the existing exact double-negation simplification. ## Are these changes tested? Yes. - Optimizer unit tests cover both operand orders for AND, OR, and XOR, both invalid De Morgan shapes, and unchanged double-negation cancellation. - A SQL logic test verifies the corrected integer results. - `cargo clippy --all-targets --all-features -- -D warnings` passes. - `./dev/rust_lint.sh` passes. - The extended workspace suite passes, including all 505 SQL logic-test files. ## Are there any user-facing changes? Yes. Unary minus in bitwise expressions now keeps arithmetic-negation semantics and returns the correct values. There are no API changes. Signed-off-by: Amogh Ramesh <[email protected]>
1 parent f9b7f34 commit 1c43063

3 files changed

Lines changed: 39 additions & 171 deletions

File tree

‎datafusion/optimizer/src/simplify_expressions/expr_simplifier.rs‎

Lines changed: 23 additions & 126 deletions
Original file line numberDiff line numberDiff line change
@@ -1267,30 +1267,6 @@ impl TreeNodeRewriter for Simplifier<'_> {
12671267
right,
12681268
}) if !info.nullable(&right)? && is_zero(&left) => Transformed::yes(*left),
12691269

1270-
// !A & A -> 0 (if A not nullable)
1271-
Expr::BinaryExpr(BinaryExpr {
1272-
left,
1273-
op: BitwiseAnd,
1274-
right,
1275-
}) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
1276-
Transformed::yes(Expr::Literal(
1277-
ScalarValue::new_zero(&info.get_data_type(&left)?)?,
1278-
None,
1279-
))
1280-
}
1281-
1282-
// A & !A -> 0 (if A not nullable)
1283-
Expr::BinaryExpr(BinaryExpr {
1284-
left,
1285-
op: BitwiseAnd,
1286-
right,
1287-
}) if is_negative_of(&right, &left) && !info.nullable(&left)? => {
1288-
Transformed::yes(Expr::Literal(
1289-
ScalarValue::new_zero(&info.get_data_type(&left)?)?,
1290-
None,
1291-
))
1292-
}
1293-
12941270
// (..A..) & A --> (..A..)
12951271
Expr::BinaryExpr(BinaryExpr {
12961272
left,
@@ -1341,30 +1317,6 @@ impl TreeNodeRewriter for Simplifier<'_> {
13411317
right,
13421318
}) if is_zero(&left) => Transformed::yes(*right),
13431319

1344-
// !A | A -> -1 (if A not nullable)
1345-
Expr::BinaryExpr(BinaryExpr {
1346-
left,
1347-
op: BitwiseOr,
1348-
right,
1349-
}) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
1350-
Transformed::yes(Expr::Literal(
1351-
ScalarValue::new_negative_one(&info.get_data_type(&left)?)?,
1352-
None,
1353-
))
1354-
}
1355-
1356-
// A | !A -> -1 (if A not nullable)
1357-
Expr::BinaryExpr(BinaryExpr {
1358-
left,
1359-
op: BitwiseOr,
1360-
right,
1361-
}) if is_negative_of(&right, &left) && !info.nullable(&left)? => {
1362-
Transformed::yes(Expr::Literal(
1363-
ScalarValue::new_negative_one(&info.get_data_type(&left)?)?,
1364-
None,
1365-
))
1366-
}
1367-
13681320
// (..A..) | A --> (..A..)
13691321
Expr::BinaryExpr(BinaryExpr {
13701322
left,
@@ -1415,30 +1367,6 @@ impl TreeNodeRewriter for Simplifier<'_> {
14151367
right,
14161368
}) if !info.nullable(&right)? && is_zero(&left) => Transformed::yes(*right),
14171369

1418-
// !A ^ A -> -1 (if A not nullable)
1419-
Expr::BinaryExpr(BinaryExpr {
1420-
left,
1421-
op: BitwiseXor,
1422-
right,
1423-
}) if is_negative_of(&left, &right) && !info.nullable(&right)? => {
1424-
Transformed::yes(Expr::Literal(
1425-
ScalarValue::new_negative_one(&info.get_data_type(&left)?)?,
1426-
None,
1427-
))
1428-
}
1429-
1430-
// A ^ !A -> -1 (if A not nullable)
1431-
Expr::BinaryExpr(BinaryExpr {
1432-
left,
1433-
op: BitwiseXor,
1434-
right,
1435-
}) if is_negative_of(&right, &left) && !info.nullable(&left)? => {
1436-
Transformed::yes(Expr::Literal(
1437-
ScalarValue::new_negative_one(&info.get_data_type(&left)?)?,
1438-
None,
1439-
))
1440-
}
1441-
14421370
// (..A..) ^ A --> (the expression without A, if number of A is odd, otherwise one A)
14431371
Expr::BinaryExpr(BinaryExpr {
14441372
left,
@@ -1503,7 +1431,12 @@ impl TreeNodeRewriter for Simplifier<'_> {
15031431
//
15041432
// Rules for Negative
15051433
//
1506-
Expr::Negative(inner) => Transformed::yes(distribute_negation(*inner)),
1434+
// Preserve the existing double-negation simplification without
1435+
// applying bitwise-complement identities to arithmetic negation.
1436+
Expr::Negative(inner) => match *inner {
1437+
Expr::Negative(inner) => Transformed::yes(*inner),
1438+
inner => Transformed::no(Expr::Negative(Box::new(inner))),
1439+
},
15071440

15081441
//
15091442
// Rules for Case
@@ -3449,47 +3382,25 @@ mod tests {
34493382
}
34503383

34513384
#[test]
3452-
fn test_simplify_negated_bitwise_and() {
3453-
// !c3 & c3 --> 0
3454-
let expr = (-col("c3_non_null")) & col("c3_non_null");
3455-
let expected = lit(0i64);
3456-
3457-
assert_eq!(simplify(expr), expected);
3458-
// c3 & !c3 --> 0
3459-
let expr = col("c3_non_null") & (-col("c3_non_null"));
3460-
let expected = lit(0i64);
3461-
3462-
assert_eq!(simplify(expr), expected);
3463-
}
3464-
3465-
#[test]
3466-
fn test_simplify_negated_bitwise_or() {
3467-
// !c3 | c3 --> -1
3468-
let expr = (-col("c3_non_null")) | col("c3_non_null");
3469-
let expected = lit(-1i64);
3470-
3471-
assert_eq!(simplify(expr), expected);
3472-
3473-
// c3 | !c3 --> -1
3474-
let expr = col("c3_non_null") | (-col("c3_non_null"));
3475-
let expected = lit(-1i64);
3476-
3477-
assert_eq!(simplify(expr), expected);
3478-
}
3479-
3480-
#[test]
3481-
fn test_simplify_negated_bitwise_xor() {
3482-
// !c3 ^ c3 --> -1
3483-
let expr = (-col("c3_non_null")) ^ col("c3_non_null");
3484-
let expected = lit(-1i64);
3485-
3486-
assert_eq!(simplify(expr), expected);
3385+
fn test_preserve_arithmetic_negation() {
3386+
let c3 = col("c3_non_null");
3387+
let expressions = [
3388+
(-c3.clone()) & c3.clone(),
3389+
c3.clone() & (-c3.clone()),
3390+
(-c3.clone()) | c3.clone(),
3391+
c3.clone() | (-c3.clone()),
3392+
(-c3.clone()) ^ c3.clone(),
3393+
c3.clone() ^ (-c3.clone()),
3394+
-bitwise_and(col("c3"), c3.clone()),
3395+
-bitwise_or(col("c3"), c3.clone()),
3396+
];
34873397

3488-
// c3 ^ !c3 --> -1
3489-
let expr = col("c3_non_null") ^ (-col("c3_non_null"));
3490-
let expected = lit(-1i64);
3398+
for expr in expressions {
3399+
assert_eq!(simplify(expr.clone()), expr);
3400+
}
34913401

3492-
assert_eq!(simplify(expr), expected);
3402+
// Keep the pre-existing arithmetic double-negation simplification.
3403+
assert_eq!(simplify(-(-c3.clone())), c3);
34933404
}
34943405

34953406
#[test]
@@ -3674,20 +3585,6 @@ mod tests {
36743585
let expr = col("c3").not().not();
36753586
let expected = col("c3");
36763587
assert_eq!(simplify(expr), expected);
3677-
3678-
// Laws with bitwise operations
3679-
// !(c3 & c4) --> !c3 | !c4
3680-
let expr = -bitwise_and(col("c3"), col("c4"));
3681-
let expected = bitwise_or(-col("c3"), -col("c4"));
3682-
assert_eq!(simplify(expr), expected);
3683-
// !(c3 | c4) --> !c3 & !c4
3684-
let expr = -bitwise_or(col("c3"), col("c4"));
3685-
let expected = bitwise_and(-col("c3"), -col("c4"));
3686-
assert_eq!(simplify(expr), expected);
3687-
// !(!c3) --> c3
3688-
let expr = -(-col("c3"));
3689-
let expected = col("c3");
3690-
assert_eq!(simplify(expr), expected);
36913588
}
36923589

36933590
#[test]

‎datafusion/optimizer/src/simplify_expressions/utils.rs‎

Lines changed: 1 addition & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@ use datafusion_common::{Result, ScalarValue, internal_err};
2323
use datafusion_expr::{
2424
Case, Expr, Like, Operator,
2525
expr::{Between, BinaryExpr, InList},
26-
expr_fn::{and, bitwise_and, bitwise_or, or},
26+
expr_fn::{and, or},
2727
};
2828

2929
/// returns true if `needle` is found in a chain of search_op
@@ -194,11 +194,6 @@ pub fn is_not_of(not_expr: &Expr, expr: &Expr) -> bool {
194194
matches!(not_expr, Expr::Not(inner) if expr == inner.as_ref())
195195
}
196196

197-
/// returns true if `not_expr` is !`expr` (bitwise not)
198-
pub fn is_negative_of(not_expr: &Expr, expr: &Expr) -> bool {
199-
matches!(not_expr, Expr::Negative(inner) if expr == inner.as_ref())
200-
}
201-
202197
/// returns the contained boolean value in `expr` as
203198
/// `Expr::Literal(ScalarValue::Boolean(v))`.
204199
pub fn as_bool_lit(expr: &Expr) -> Result<Option<bool>> {
@@ -370,45 +365,6 @@ pub fn negate_clause(expr: Expr) -> Expr {
370365
}
371366
}
372367

373-
/// bitwise negate a Negative clause
374-
/// input is the clause to be bitwise negated.(args for Negative clause)
375-
/// For BinaryExpr:
376-
/// ~(A & B) ===> ~A | ~B
377-
/// ~(A | B) ===> ~A & ~B
378-
/// For Negative:
379-
/// ~(~A) ===> A
380-
/// For others, use Negative clause
381-
pub fn distribute_negation(expr: Expr) -> Expr {
382-
match expr {
383-
Expr::BinaryExpr(BinaryExpr { left, op, right }) => {
384-
match op {
385-
// ~(A & B) ===> ~A | ~B
386-
Operator::BitwiseAnd => {
387-
let left = distribute_negation(*left);
388-
let right = distribute_negation(*right);
389-
390-
bitwise_or(left, right)
391-
}
392-
// ~(A | B) ===> ~A & ~B
393-
Operator::BitwiseOr => {
394-
let left = distribute_negation(*left);
395-
let right = distribute_negation(*right);
396-
397-
bitwise_and(left, right)
398-
}
399-
// use negative clause
400-
_ => Expr::Negative(Box::new(Expr::BinaryExpr(BinaryExpr::new(
401-
left, op, right,
402-
)))),
403-
}
404-
}
405-
// ~(~A) ===> A
406-
Expr::Negative(expr) => *expr,
407-
// use negative clause
408-
_ => Expr::Negative(Box::new(expr)),
409-
}
410-
}
411-
412368
#[cfg(test)]
413369
mod tests {
414370
use super::{is_one, is_zero};

‎datafusion/sqllogictest/test_files/scalar.slt‎

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1479,6 +1479,21 @@ from (values (NULL::INT, 7), (3, 7)) as t(a, b);
14791479
7 7 0
14801480
NULL NULL NULL
14811481

1482+
# arithmetic negation is not bitwise NOT
1483+
query IIIIII
1484+
select
1485+
i,
1486+
(-i) & i,
1487+
i | (-i),
1488+
(-i) ^ i,
1489+
-(i & j),
1490+
-(i | j)
1491+
from (values (5, 3), (6, 3)) as t(i, j)
1492+
order by i;
1493+
----
1494+
5 1 -1 -2 -1 -7
1495+
6 2 -2 -4 -2 -7
1496+
14821497
# bitwise xor with other operators
14831498
query II rowsort
14841499
select 2 * c - 1 ^ 856 + d + 3, d ^ 7 >> 4 from signed_integers;

0 commit comments

Comments
 (0)