datalogic-rs 5.3.0

//! Dead code elimination pass.
//!
//! Eliminates unreachable branches when conditions are compile-time constants:
//! - `{"if": [true, A, B]}` → `A` (also handles `?:`, which normalizes to `if`)
//! - `{"and": [true, X]}` → `X` (strip identity elements)
//! - `{"and": [false, X]}` → `false` (absorbing element)
//! - `{"or": [true, X]}` → `true` (absorbing element)
//! - `{"or": [false, X]}` → `X` (strip identity elements)

use crate::Engine;
use crate::node::CompiledNode;
use crate::opcode::OpCode;

use super::helpers::is_truthy_literal;

/// Eliminate dead branches from a compiled node tree.
///
/// Returns `(node, changed)` where `changed` is `true` if the pass rewrote
/// the input. Only transforms the top-level node — recursive application
/// is driven by the optimiser pipeline's fixpoint loop.
pub(crate) fn eliminate(node: CompiledNode, engine: &Engine) -> (CompiledNode, bool) {
    match &node {
        CompiledNode::BuiltinOperator {
            id, opcode, args, ..
        } => {
            let rewritten = match opcode {
                OpCode::If => eliminate_if(*id, args, engine),
                // `and` short-circuits on a falsy literal (absorbing = false);
                // `or` short-circuits on a truthy literal (absorbing = true).
                OpCode::And => eliminate_bool_chain(*id, args, engine, false, OpCode::And),
                OpCode::Or => eliminate_bool_chain(*id, args, engine, true, OpCode::Or),
                _ => None,
            };
            match rewritten {
                Some(new_node) => (new_node, true),
                None => (node, false),
            }
        }
        _ => (node, false),
    }
}

/// Eliminate dead branches in if/elseif/else chains.
/// Returns `Some(new_node)` if the input was rewritten, `None` otherwise.
fn eliminate_if(
    outer_id: crate::node::NodeId,
    args: &[CompiledNode],
    engine: &Engine,
) -> Option<CompiledNode> {
    if args.is_empty() {
        return Some(CompiledNode::synthetic_value(
            datavalue::OwnedDataValue::Null,
        ));
    }

    // For a 2+ arg chain, the only rewrite is when some condition position
    // (even index with a following then-branch) is a static literal;
    // otherwise the walk just rebuilds the same arg list and returns None.
    // Bail before that cloning. The single-arg `{"if":[else]}` unwrap below
    // does not need a static condition, so it is excluded from the guard.
    if args.len() >= 2
        && !(0..args.len())
            .step_by(2)
            .filter(|&i| i + 1 < args.len())
            .any(|i| is_truthy_literal(&args[i], engine).is_some())
    {
        return None;
    }

    let mut i = 0;
    let mut new_args: Vec<CompiledNode> = Vec::new();
    let mut skipped_any = false;

    while i < args.len() {
        if i == args.len() - 1 {
            // Final else clause — keep it
            if new_args.is_empty() {
                // All previous conditions were false → this is the result
                return Some(args[i].clone());
            }
            new_args.push(args[i].clone());
            break;
        }

        // Check if condition is a static value
        match is_truthy_literal(&args[i], engine) {
            Some(true) => {
                // Condition is statically true → return the then-branch
                if i + 1 < args.len() {
                    if new_args.is_empty() {
                        return Some(args[i + 1].clone());
                    }
                    // We had prior non-static conditions; this becomes the else
                    new_args.push(args[i + 1].clone());
                    skipped_any = true;
                    break;
                }
                return Some(args[i].clone());
            }
            Some(false) => {
                // Condition is statically false → skip this condition+then pair
                skipped_any = true;
                i += 2;
                continue;
            }
            None => {
                // Non-static condition — keep it
                new_args.push(args[i].clone());
                if i + 1 < args.len() {
                    new_args.push(args[i + 1].clone());
                }
                i += 2;
            }
        }
    }

    if new_args.is_empty() {
        // All conditions were statically false, no else clause
        return Some(CompiledNode::synthetic_value(
            datavalue::OwnedDataValue::Null,
        ));
    }

    if new_args.len() == 1 {
        // Single remaining element is the else clause
        return Some(new_args.into_iter().next().unwrap());
    }

    if !skipped_any && new_args.len() == args.len() {
        // No-op rebuild — leave input untouched
        return None;
    }

    Some(CompiledNode::BuiltinOperator {
        id: outer_id,
        opcode: OpCode::If,
        args: new_args.into_boxed_slice(),
        predicate_hint: None,
        iter_arg_kind: crate::operators::array::IterArgKind::General,
    })
}

/// Eliminate identity/absorbing elements in a boolean chain (`and` / `or`).
///
/// `absorbing` is the literal truthiness that short-circuits the chain and is
/// returned as-is (`false` for `and`, `true` for `or`); the opposite literal
/// is the identity element and gets stripped. `opcode` is the operator to
/// rebuild when only some elements were stripped.
fn eliminate_bool_chain(
    outer_id: crate::node::NodeId,
    args: &[CompiledNode],
    engine: &Engine,
    absorbing: bool,
    opcode: OpCode,
) -> Option<CompiledNode> {
    if args.is_empty() {
        return None;
    }

    // Bail before any cloning unless at least one arg is a boolean literal:
    // with no literals every arg is "remaining" and the function would just
    // clone them all and return None.
    if !args.iter().any(|a| is_truthy_literal(a, engine).is_some()) {
        return None;
    }

    let mut remaining: Vec<CompiledNode> = Vec::new();

    let last_idx = args.len() - 1;
    for (i, arg) in args.iter().enumerate() {
        match is_truthy_literal(arg, engine) {
            Some(b) if b == absorbing => {
                // Absorbing element. The chain can never get past it, so
                // everything after it is dead. But the args *before* it
                // still run first (and may themselves short-circuit, or
                // throw), so the literal only replaces the whole chain when
                // nothing dynamic precedes it. Otherwise it stays in place
                // as the chain's final element.
                if remaining.is_empty() {
                    return Some(arg.clone());
                }
                remaining.push(arg.clone());
                break;
            }
            Some(_) if i < last_idx => {
                // Identity element with something after it: skip (the op
                // returns the value, not a bool, so the next arg takes over).
                continue;
            }
            Some(_) => {
                // Identity element in tail position: `and` / `or` return the
                // last evaluated value when nothing short-circuits, so this
                // literal is the chain's result and must stay.
                remaining.push(arg.clone());
            }
            None => {
                remaining.push(arg.clone());
            }
        }
    }

    if remaining.len() == 1 {
        return Some(remaining.into_iter().next().unwrap());
    }

    if remaining.len() == args.len() {
        // Nothing stripped — no change.
        return None;
    }

    Some(CompiledNode::BuiltinOperator {
        id: outer_id,
        opcode,
        args: remaining.into_boxed_slice(),
        predicate_hint: None,
        iter_arg_kind: crate::operators::array::IterArgKind::General,
    })
}

#[cfg(all(test, feature = "serde_json"))]
mod tests {
    use super::super::test_helpers::{builtin, val, var_node};
    use super::*;

    #[test]
    fn test_if_true_condition() {
        let engine = Engine::new();
        let node = builtin(
            OpCode::If,
            vec![
                val(datavalue::OwnedDataValue::Bool(true)),
                var_node("x"),
                var_node("y"),
            ],
        );
        let (result, _changed) = eliminate(node, &engine);
        assert!(matches!(result, CompiledNode::Var { .. }));
    }

    #[test]
    fn test_if_false_condition() {
        let engine = Engine::new();
        let node = builtin(
            OpCode::If,
            vec![
                val(datavalue::OwnedDataValue::Bool(false)),
                var_node("x"),
                var_node("y"),
            ],
        );
        let (result, _changed) = eliminate(node, &engine);
        // Should return "y" (the else branch)
        assert!(matches!(result, CompiledNode::Var { .. }));
    }

    #[test]
    fn test_and_with_true_prefix() {
        let engine = Engine::new();
        let node = builtin(
            OpCode::And,
            vec![val(datavalue::OwnedDataValue::Bool(true)), var_node("x")],
        );
        let (result, _changed) = eliminate(node, &engine);
        assert!(matches!(result, CompiledNode::Var { .. }));
    }

    #[test]
    fn test_and_with_false() {
        let engine = Engine::new();
        let node = builtin(
            OpCode::And,
            vec![val(datavalue::OwnedDataValue::Bool(false)), var_node("x")],
        );
        let (result, _changed) = eliminate(node, &engine);
        assert!(matches!(result, CompiledNode::Value { .. }));
    }

    #[test]
    fn test_or_with_true() {
        let engine = Engine::new();
        let node = builtin(
            OpCode::Or,
            vec![val(datavalue::OwnedDataValue::Bool(true)), var_node("x")],
        );
        let (result, _changed) = eliminate(node, &engine);
        assert!(matches!(result, CompiledNode::Value { .. }));
    }

    #[test]
    fn test_or_with_false_prefix() {
        let engine = Engine::new();
        let node = builtin(
            OpCode::Or,
            vec![val(datavalue::OwnedDataValue::Bool(false)), var_node("x")],
        );
        let (result, _changed) = eliminate(node, &engine);
        assert!(matches!(result, CompiledNode::Var { .. }));
    }

    #[test]
    fn test_or_dynamic_then_absorbing_keeps_dynamic_prefix() {
        // `{"or": [{"var": "x"}, "fallback"]}` must NOT fold to "fallback":
        // the var runs first and wins when truthy.
        let engine = Engine::new();
        let node = builtin(
            OpCode::Or,
            vec![var_node("x"), val(datavalue::OwnedDataValue::Bool(true))],
        );
        let (result, changed) = eliminate(node, &engine);
        assert!(!changed);
        match result {
            CompiledNode::BuiltinOperator { args, .. } => assert_eq!(args.len(), 2),
            other => panic!("expected the chain to be kept, got {other:?}"),
        }
    }

    #[test]
    fn test_or_truncates_after_absorbing_literal() {
        // `{"or": [{"var": "x"}, true, {"var": "y"}]}` -> `{"or": [{"var": "x"}, true]}`
        let engine = Engine::new();
        let node = builtin(
            OpCode::Or,
            vec![
                var_node("x"),
                val(datavalue::OwnedDataValue::Bool(true)),
                var_node("y"),
            ],
        );
        let (result, changed) = eliminate(node, &engine);
        assert!(changed);
        match result {
            CompiledNode::BuiltinOperator { args, .. } => {
                assert_eq!(args.len(), 2);
                assert!(matches!(args[0], CompiledNode::Var { .. }));
                assert!(matches!(args[1], CompiledNode::Value { .. }));
            }
            other => panic!("expected a 2-arg chain, got {other:?}"),
        }
    }

    #[test]
    fn test_and_dynamic_then_absorbing_keeps_dynamic_prefix() {
        // `{"and": [{"var": "x"}, false]}` must return x when x is falsy.
        let engine = Engine::new();
        let node = builtin(
            OpCode::And,
            vec![var_node("x"), val(datavalue::OwnedDataValue::Bool(false))],
        );
        let (result, changed) = eliminate(node, &engine);
        assert!(!changed);
        assert!(matches!(result, CompiledNode::BuiltinOperator { .. }));
    }

    #[test]
    fn test_and_keeps_tail_identity_literal() {
        // `{"and": [{"var": "x"}, true]}` returns true when x is truthy, so
        // the trailing identity literal is the result and must be kept.
        let engine = Engine::new();
        let node = builtin(
            OpCode::And,
            vec![var_node("x"), val(datavalue::OwnedDataValue::Bool(true))],
        );
        let (result, changed) = eliminate(node, &engine);
        assert!(!changed);
        match result {
            CompiledNode::BuiltinOperator { args, .. } => assert_eq!(args.len(), 2),
            other => panic!("expected the chain to be kept, got {other:?}"),
        }
    }

    #[test]
    fn test_and_strips_middle_identity_literal() {
        // `{"and": [{"var": "x"}, true, {"var": "y"}]}` -> `{"and": [x, y]}`
        let engine = Engine::new();
        let node = builtin(
            OpCode::And,
            vec![
                var_node("x"),
                val(datavalue::OwnedDataValue::Bool(true)),
                var_node("y"),
            ],
        );
        let (result, changed) = eliminate(node, &engine);
        assert!(changed);
        match result {
            CompiledNode::BuiltinOperator { args, .. } => {
                assert_eq!(args.len(), 2);
                assert!(args.iter().all(|a| matches!(a, CompiledNode::Var { .. })));
            }
            other => panic!("expected a 2-arg chain, got {other:?}"),
        }
    }

    #[test]
    fn test_all_identity_literals_returns_last() {
        // `{"or": [false, null]}` -> null (the last value)
        let engine = Engine::new();
        let node = builtin(
            OpCode::Or,
            vec![
                val(datavalue::OwnedDataValue::Bool(false)),
                val(datavalue::OwnedDataValue::Null),
            ],
        );
        let (result, _changed) = eliminate(node, &engine);
        assert!(matches!(result, CompiledNode::Value { .. }));
    }

    #[test]
    fn test_ternary_true() {
        // `?:` normalizes to OpCode::If at FromStr; eliminate_if handles
        // the 3-arg case identically to a ternary.
        let engine = Engine::new();
        let node = builtin(
            OpCode::If,
            vec![
                val(datavalue::OwnedDataValue::Bool(true)),
                var_node("x"),
                var_node("y"),
            ],
        );
        let (result, _changed) = eliminate(node, &engine);
        assert!(matches!(result, CompiledNode::Var { .. }));
    }
}