jarq 0.7.5

use rayon::prelude::*;
use simd_json::OwnedValue as Value;
use simd_json::StaticNode;
use simd_json::prelude::*;

use super::ast::{BoolOp, CompareOp, Filter, FilterKind, FunctionCall, ObjectKey};
use super::builtins;
use crate::error::EvalError;
use crate::utils::type_name;

/// Threshold for parallel array operations
const PARALLEL_THRESHOLD: usize = 10_000;

pub fn eval(filter: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    match &filter.kind {
        FilterKind::Identity => Ok(vec![value.clone()]),
        FilterKind::Field(name) => match value {
            Value::Object(map) => Ok(vec![
                map.get(name)
                    .cloned()
                    .unwrap_or(Value::Static(StaticNode::Null)),
            ]),
            _ => Ok(vec![Value::Static(StaticNode::Null)]),
        },
        FilterKind::Index(n) => match value {
            Value::Array(arr) => {
                let idx = if *n >= 0 {
                    *n as usize
                } else {
                    arr.len().checked_sub((-*n) as usize).unwrap_or(usize::MAX)
                };
                Ok(vec![
                    arr.get(idx)
                        .cloned()
                        .unwrap_or(Value::Static(StaticNode::Null)),
                ])
            }
            _ => Ok(vec![Value::Static(StaticNode::Null)]),
        },
        FilterKind::Slice(start, end) => match value {
            Value::Array(arr) => {
                let len = arr.len() as i64;

                // Resolve start index (default 0)
                let start_idx = match start {
                    Some(s) if *s >= 0 => (*s as usize).min(arr.len()),
                    Some(s) => (len + *s).max(0) as usize,
                    None => 0,
                };

                // Resolve end index (default len)
                let end_idx = match end {
                    Some(e) if *e >= 0 => (*e as usize).min(arr.len()),
                    Some(e) => (len + *e).max(0) as usize,
                    None => arr.len(),
                };

                // Handle case where start > end
                if start_idx >= end_idx {
                    Ok(vec![Value::Array(Box::default())])
                } else {
                    Ok(vec![Value::Array(Box::new(
                        arr[start_idx..end_idx].to_vec(),
                    ))])
                }
            }
            Value::String(s) => {
                let chars: Vec<char> = s.chars().collect();
                let len = chars.len() as i64;

                let start_idx = match start {
                    Some(st) if *st >= 0 => (*st as usize).min(chars.len()),
                    Some(st) => (len + *st).max(0) as usize,
                    None => 0,
                };

                let end_idx = match end {
                    Some(e) if *e >= 0 => (*e as usize).min(chars.len()),
                    Some(e) => (len + *e).max(0) as usize,
                    None => chars.len(),
                };

                if start_idx >= end_idx {
                    Ok(vec![Value::String(String::new())])
                } else {
                    Ok(vec![Value::String(
                        chars[start_idx..end_idx].iter().collect(),
                    )])
                }
            }
            _ => Ok(vec![Value::Static(StaticNode::Null)]),
        },
        FilterKind::Iterate => match value {
            Value::Array(arr) if arr.len() >= PARALLEL_THRESHOLD => {
                Ok(arr.par_iter().cloned().collect())
            }
            Value::Array(arr) => Ok(arr.to_vec()),
            Value::Object(map) => Ok(map.values().cloned().collect()),
            _ => Err(EvalError::CannotIterate {
                value: value.clone(),
                position: filter.span.start,
            }),
        },
        FilterKind::Optional(inner) => {
            // Try to evaluate, suppress errors by returning empty
            match eval(inner, value) {
                Ok(results) => Ok(results),
                Err(_) => Ok(vec![]),
            }
        }
        FilterKind::Pipe(left, right) => {
            let left_results = eval(left, value)?;
            let mut results = Vec::new();
            for v in left_results {
                results.extend(eval(right, &v)?);
            }
            Ok(results)
        }
        FilterKind::Builtin(b) => builtins::eval(b, value).map_err(|mut e| {
            e.set_position(filter.span.start);
            e
        }),
        FilterKind::Function(func) => eval_function(func, value).map_err(|mut e| {
            e.set_position(filter.span.start);
            e
        }),
        FilterKind::Literal(lit) => Ok(vec![lit.clone()]),
        FilterKind::Compare(left, op, right) => eval_compare(left, *op, right, value),
        FilterKind::BoolOp(left, op, right) => eval_bool_op(left, *op, right, value),
        FilterKind::Array(element_filters) => {
            let mut array_elements = Vec::new();
            for elem_filter in element_filters {
                let results = eval(elem_filter, value)?;
                // Collect all results (handles .[] producing multiple values)
                array_elements.extend(results);
            }
            Ok(vec![Value::Array(Box::new(array_elements))])
        }
        FilterKind::Object(pairs) => {
            let mut obj = simd_json::owned::Object::new();
            for (key, value_filter) in pairs {
                // Resolve key (static or dynamic)
                let key_str = match key {
                    ObjectKey::Static(s) => s.clone(),
                    ObjectKey::Dynamic(key_filter) => {
                        let key_results = eval(key_filter, value)?;
                        match key_results.into_iter().next() {
                            Some(Value::String(s)) => s,
                            Some(other) => {
                                return Err(EvalError::TypeError {
                                    message: format!(
                                        "object key must be string, got {}",
                                        type_name(&other)
                                    ),
                                    position: key_filter.span.start,
                                });
                            }
                            None => {
                                return Err(EvalError::TypeError {
                                    message: "object key expression produced no value".to_string(),
                                    position: key_filter.span.start,
                                });
                            }
                        }
                    }
                };

                let results = eval(value_filter, value)?;
                // Take first result for object values
                let val = results
                    .into_iter()
                    .next()
                    .unwrap_or(Value::Static(StaticNode::Null));
                obj.insert(key_str, val);
            }
            Ok(vec![Value::Object(Box::new(obj))])
        }
        FilterKind::IfThenElse {
            condition,
            then_branch,
            else_branch,
        } => {
            let cond_results = eval(condition, value)?;
            let is_truthy = cond_results.iter().any(|v| {
                !matches!(
                    v,
                    Value::Static(StaticNode::Null) | Value::Static(StaticNode::Bool(false))
                )
            });

            if is_truthy {
                eval(then_branch, value)
            } else {
                eval(else_branch, value)
            }
        }
        FilterKind::Alternative(left, right) => {
            let left_results = eval(left, value)?;

            // Check if left produced any non-false, non-null value
            let has_value = left_results.iter().any(|v| {
                !matches!(
                    v,
                    Value::Static(StaticNode::Null) | Value::Static(StaticNode::Bool(false))
                )
            });

            if has_value {
                // Filter out false/null from results
                let filtered: Vec<Value> = left_results
                    .into_iter()
                    .filter(|v| {
                        !matches!(
                            v,
                            Value::Static(StaticNode::Null)
                                | Value::Static(StaticNode::Bool(false))
                        )
                    })
                    .collect();
                if filtered.is_empty() {
                    eval(right, value)
                } else {
                    Ok(filtered)
                }
            } else {
                eval(right, value)
            }
        }
    }
}

fn eval_function(func: &FunctionCall, value: &Value) -> Result<Vec<Value>, EvalError> {
    match func {
        FunctionCall::Map(inner) => eval_map(inner, value),
        FunctionCall::Select(inner) => eval_select(inner, value),
        FunctionCall::SortBy(inner) => eval_sort_by(inner, value),
        FunctionCall::GroupBy(inner) => eval_group_by(inner, value),
        FunctionCall::UniqueBy(inner) => eval_unique_by(inner, value),
        FunctionCall::MinBy(inner) => eval_min_by(inner, value),
        FunctionCall::MaxBy(inner) => eval_max_by(inner, value),
        FunctionCall::Has(key) => eval_has(key, value),
        FunctionCall::Split(delim) => eval_split(delim, value),
        FunctionCall::Join(sep) => eval_join(sep, value),
        FunctionCall::StartsWith(prefix) => eval_startswith(prefix, value),
        FunctionCall::EndsWith(suffix) => eval_endswith(suffix, value),
        FunctionCall::Contains(inner) => eval_contains(inner, value),
        FunctionCall::WithEntries(inner) => eval_with_entries(inner, value),
    }
}

fn eval_has(key: &str, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::Object(map) => Ok(vec![Value::Static(StaticNode::Bool(map.contains_key(key)))]),
        Value::Array(arr) => {
            // has(n) for arrays checks if index exists
            if let Ok(idx) = key.parse::<usize>() {
                Ok(vec![Value::Static(StaticNode::Bool(idx < arr.len()))])
            } else {
                Ok(vec![Value::Static(StaticNode::Bool(false))])
            }
        }
        _ => Ok(vec![Value::Static(StaticNode::Bool(false))]),
    }
}

fn eval_split(delim: &str, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::String(s) => {
            // jq special cases
            if s.is_empty() {
                // Empty string split returns empty array
                return Ok(vec![Value::Array(Box::default())]);
            }
            if delim.is_empty() {
                // Empty delimiter splits into characters
                let parts: Vec<Value> = s.chars().map(|c| Value::String(c.to_string())).collect();
                return Ok(vec![Value::Array(Box::new(parts))]);
            }
            let parts: Vec<Value> = s
                .split(delim)
                .map(|p| Value::String(p.to_string()))
                .collect();
            Ok(vec![Value::Array(Box::new(parts))])
        }
        _ => Err(EvalError::TypeError {
            message: format!("split requires string, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_join(sep: &str, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::Array(arr) => {
            let mut strings = Vec::new();
            for v in arr.iter() {
                match v {
                    Value::String(s) => strings.push(s.clone()),
                    Value::Static(StaticNode::Null) => strings.push(String::new()), // jq treats null as empty string
                    _ => {
                        return Err(EvalError::TypeError {
                            message: format!(
                                "join requires array of strings, got {} in array",
                                type_name(v)
                            ),
                            position: 0,
                        });
                    }
                }
            }
            Ok(vec![Value::String(strings.join(sep))])
        }
        _ => Err(EvalError::TypeError {
            message: format!("join requires array, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_startswith(prefix: &str, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::String(s) => Ok(vec![Value::Static(StaticNode::Bool(s.starts_with(prefix)))]),
        _ => Err(EvalError::TypeError {
            message: format!("startswith requires string, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_endswith(suffix: &str, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::String(s) => Ok(vec![Value::Static(StaticNode::Bool(s.ends_with(suffix)))]),
        _ => Err(EvalError::TypeError {
            message: format!("endswith requires string, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_contains(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    let needle_results = eval(inner, value)?;
    let needle = needle_results
        .into_iter()
        .next()
        .unwrap_or(Value::Static(StaticNode::Null));

    Ok(vec![Value::Static(StaticNode::Bool(value_contains(
        value, &needle,
    )))])
}

/// Recursive contains check following jq semantics:
/// - strings: b is substring of a
/// - arrays: all elements of b are contained in some element of a
/// - objects: all key-value pairs of b have matching keys in a with contained values
/// - scalars: equality
fn value_contains(a: &Value, b: &Value) -> bool {
    match (a, b) {
        (Value::String(haystack), Value::String(needle)) => haystack.contains(needle.as_str()),
        (Value::Array(arr), Value::Array(needle_arr)) => {
            // All elements of needle must be contained in some element of arr
            needle_arr
                .iter()
                .all(|needle_elem| arr.iter().any(|elem| value_contains(elem, needle_elem)))
        }
        (Value::Object(obj), Value::Object(needle_obj)) => needle_obj
            .iter()
            .all(|(k, v)| obj.get(k).map(|ov| value_contains(ov, v)).unwrap_or(false)),
        _ => compare_values(a, b) == Some(std::cmp::Ordering::Equal),
    }
}

/// with_entries(f) is equivalent to: to_entries | map(f) | from_entries
fn eval_with_entries(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::Object(obj) => {
            // Convert to entries
            let entries: Vec<Value> = obj
                .iter()
                .map(|(k, v)| {
                    let mut entry = simd_json::owned::Object::new();
                    entry.insert("key".to_string(), Value::String(k.clone()));
                    entry.insert("value".to_string(), v.clone());
                    Value::Object(Box::new(entry))
                })
                .collect();

            // Apply filter to each entry
            let mut transformed = Vec::new();
            for entry in entries {
                transformed.extend(eval(inner, &entry)?);
            }

            // Convert back to object
            let mut result = simd_json::owned::Object::new();
            for entry in transformed {
                // Extract key: try "key", "k", "name"
                let key = entry
                    .get("key")
                    .or_else(|| entry.get("k"))
                    .or_else(|| entry.get("name"))
                    .and_then(|k| k.as_str())
                    .ok_or_else(|| EvalError::TypeError {
                        message: "Cannot use null as object key".to_string(),
                        position: 0,
                    })?;

                // Extract value: try "value", "v" (default to null)
                let val = entry
                    .get("value")
                    .or_else(|| entry.get("v"))
                    .cloned()
                    .unwrap_or(Value::Static(StaticNode::Null));

                result.insert(key.to_string(), val);
            }

            Ok(vec![Value::Object(Box::new(result))])
        }
        _ => Err(EvalError::TypeError {
            message: format!("with_entries requires object, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_map(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::Array(arr) => {
            let mut results = Vec::new();
            for elem in arr.iter() {
                results.extend(eval(inner, elem)?);
            }
            Ok(vec![Value::Array(Box::new(results))])
        }
        _ => Err(EvalError::TypeError {
            message: format!("map requires array, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_select(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    let results = eval(inner, value)?;
    // In jq, select keeps values where the condition is truthy
    // Falsy values are: false and null
    // Everything else (including 0, "", [], {}) is truthy
    let is_truthy = results.iter().any(|v| {
        !matches!(
            v,
            Value::Static(StaticNode::Null) | Value::Static(StaticNode::Bool(false))
        )
    });

    if is_truthy {
        Ok(vec![value.clone()])
    } else {
        Ok(vec![]) // No output
    }
}

fn eval_sort_by(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::Array(arr) => {
            // Extract keys and pair with elements
            let mut keyed: Vec<(Value, Value)> = arr
                .iter()
                .map(|elem| {
                    let key = eval(inner, elem)?
                        .into_iter()
                        .next()
                        .unwrap_or(Value::Static(StaticNode::Null));
                    Ok((key, elem.clone()))
                })
                .collect::<Result<Vec<_>, EvalError>>()?;

            // Sort by key using existing compare_values (stable sort)
            keyed.sort_by(|(a, _), (b, _)| {
                compare_values(a, b).unwrap_or(std::cmp::Ordering::Equal)
            });

            let sorted: Vec<Value> = keyed.into_iter().map(|(_, v)| v).collect();
            Ok(vec![Value::Array(Box::new(sorted))])
        }
        _ => Err(EvalError::TypeError {
            message: format!("sort_by requires array, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_group_by(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::Array(arr) => {
            // Extract keys and group elements
            let mut groups: Vec<(Value, Vec<Value>)> = vec![];

            for elem in arr.iter() {
                let key = eval(inner, elem)?
                    .into_iter()
                    .next()
                    .unwrap_or(Value::Static(StaticNode::Null));

                // Find existing group with same key
                if let Some((_, group)) = groups
                    .iter_mut()
                    .find(|(k, _)| compare_values(k, &key) == Some(std::cmp::Ordering::Equal))
                {
                    group.push(elem.clone());
                } else {
                    groups.push((key, vec![elem.clone()]));
                }
            }

            // Sort groups by key (jq behavior)
            groups.sort_by(|(a, _), (b, _)| {
                compare_values(a, b).unwrap_or(std::cmp::Ordering::Equal)
            });

            // Return array of arrays
            let result: Vec<Value> = groups
                .into_iter()
                .map(|(_, group)| Value::Array(Box::new(group)))
                .collect();
            Ok(vec![Value::Array(Box::new(result))])
        }
        _ => Err(EvalError::TypeError {
            message: format!("group_by requires array, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_unique_by(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    match value {
        Value::Array(arr) => {
            let mut seen: Vec<Value> = vec![];
            let mut result: Vec<Value> = vec![];

            for elem in arr.iter() {
                let key = eval(inner, elem)?
                    .into_iter()
                    .next()
                    .unwrap_or(Value::Static(StaticNode::Null));

                // Check if we've seen this key
                let is_new = !seen
                    .iter()
                    .any(|k| compare_values(k, &key) == Some(std::cmp::Ordering::Equal));

                if is_new {
                    seen.push(key);
                    result.push(elem.clone());
                }
            }

            Ok(vec![Value::Array(Box::new(result))])
        }
        _ => Err(EvalError::TypeError {
            message: format!("unique_by requires array, got {}", type_name(value)),
            position: 0,
        }),
    }
}

fn eval_min_by(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    eval_extremum_by(inner, value, true)
}

fn eval_max_by(inner: &Filter, value: &Value) -> Result<Vec<Value>, EvalError> {
    eval_extremum_by(inner, value, false)
}

fn eval_extremum_by(inner: &Filter, value: &Value, is_min: bool) -> Result<Vec<Value>, EvalError> {
    let func_name = if is_min { "min_by" } else { "max_by" };

    match value {
        Value::Array(arr) if arr.is_empty() => Ok(vec![Value::Static(StaticNode::Null)]),
        Value::Array(arr) => {
            let mut best_elem = &arr[0];
            let mut best_key = eval(inner, best_elem)?
                .into_iter()
                .next()
                .unwrap_or(Value::Static(StaticNode::Null));

            for elem in arr.iter().skip(1) {
                let key = eval(inner, elem)?
                    .into_iter()
                    .next()
                    .unwrap_or(Value::Static(StaticNode::Null));

                let cmp = compare_values(&key, &best_key);
                let should_replace = if is_min {
                    cmp == Some(std::cmp::Ordering::Less)
                } else {
                    cmp == Some(std::cmp::Ordering::Greater)
                };

                if should_replace {
                    best_elem = elem;
                    best_key = key;
                }
            }

            Ok(vec![best_elem.clone()])
        }
        _ => Err(EvalError::TypeError {
            message: format!("{} requires array, got {}", func_name, type_name(value)),
            position: 0,
        }),
    }
}

fn eval_compare(
    left: &Filter,
    op: CompareOp,
    right: &Filter,
    value: &Value,
) -> Result<Vec<Value>, EvalError> {
    let left_results = eval(left, value)?;
    let right_results = eval(right, value)?;

    // Take first result from each side
    let left_val = left_results
        .into_iter()
        .next()
        .unwrap_or(Value::Static(StaticNode::Null));
    let right_val = right_results
        .into_iter()
        .next()
        .unwrap_or(Value::Static(StaticNode::Null));

    let result = match op {
        CompareOp::Eq => compare_values(&left_val, &right_val) == Some(std::cmp::Ordering::Equal),
        CompareOp::Ne => compare_values(&left_val, &right_val) != Some(std::cmp::Ordering::Equal),
        CompareOp::Lt => compare_values(&left_val, &right_val) == Some(std::cmp::Ordering::Less),
        CompareOp::Le => matches!(
            compare_values(&left_val, &right_val),
            Some(std::cmp::Ordering::Less | std::cmp::Ordering::Equal)
        ),
        CompareOp::Gt => compare_values(&left_val, &right_val) == Some(std::cmp::Ordering::Greater),
        CompareOp::Ge => matches!(
            compare_values(&left_val, &right_val),
            Some(std::cmp::Ordering::Greater | std::cmp::Ordering::Equal)
        ),
    };

    Ok(vec![Value::Static(StaticNode::Bool(result))])
}

fn eval_bool_op(
    left: &Filter,
    op: BoolOp,
    right: &Filter,
    value: &Value,
) -> Result<Vec<Value>, EvalError> {
    // Evaluate left side first
    let left_results = eval(left, value)?;
    let left_truthy = left_results.iter().any(|v| {
        !matches!(
            v,
            Value::Static(StaticNode::Null) | Value::Static(StaticNode::Bool(false))
        )
    });

    // Short-circuit evaluation
    match op {
        BoolOp::And => {
            if !left_truthy {
                // Short-circuit: false and X = false
                Ok(vec![Value::Static(StaticNode::Bool(false))])
            } else {
                // Evaluate right side
                let right_results = eval(right, value)?;
                let right_truthy = right_results.iter().any(|v| {
                    !matches!(
                        v,
                        Value::Static(StaticNode::Null) | Value::Static(StaticNode::Bool(false))
                    )
                });
                Ok(vec![Value::Static(StaticNode::Bool(right_truthy))])
            }
        }
        BoolOp::Or => {
            if left_truthy {
                // Short-circuit: true or X = true
                Ok(vec![Value::Static(StaticNode::Bool(true))])
            } else {
                // Evaluate right side
                let right_results = eval(right, value)?;
                let right_truthy = right_results.iter().any(|v| {
                    !matches!(
                        v,
                        Value::Static(StaticNode::Null) | Value::Static(StaticNode::Bool(false))
                    )
                });
                Ok(vec![Value::Static(StaticNode::Bool(right_truthy))])
            }
        }
    }
}

/// Compare two JSON values following jq semantics.
/// Returns None if values are not comparable (different types for ordering).
fn compare_values(a: &Value, b: &Value) -> Option<std::cmp::Ordering> {
    use std::cmp::Ordering;

    match (a, b) {
        // Null
        (Value::Static(StaticNode::Null), Value::Static(StaticNode::Null)) => Some(Ordering::Equal),

        // Booleans: false < true
        (Value::Static(StaticNode::Bool(a)), Value::Static(StaticNode::Bool(b))) => Some(a.cmp(b)),

        // Numbers
        (Value::Static(StaticNode::I64(a)), Value::Static(StaticNode::I64(b))) => Some(a.cmp(b)),
        (Value::Static(StaticNode::U64(a)), Value::Static(StaticNode::U64(b))) => Some(a.cmp(b)),
        (Value::Static(StaticNode::F64(a)), Value::Static(StaticNode::F64(b))) => a.partial_cmp(b),
        (Value::Static(StaticNode::I64(a)), Value::Static(StaticNode::U64(b))) => {
            Some((*a as i128).cmp(&(*b as i128)))
        }
        (Value::Static(StaticNode::U64(a)), Value::Static(StaticNode::I64(b))) => {
            Some((*a as i128).cmp(&(*b as i128)))
        }
        (Value::Static(StaticNode::I64(a)), Value::Static(StaticNode::F64(b))) => {
            (*a as f64).partial_cmp(b)
        }
        (Value::Static(StaticNode::F64(a)), Value::Static(StaticNode::I64(b))) => {
            a.partial_cmp(&(*b as f64))
        }
        (Value::Static(StaticNode::U64(a)), Value::Static(StaticNode::F64(b))) => {
            (*a as f64).partial_cmp(b)
        }
        (Value::Static(StaticNode::F64(a)), Value::Static(StaticNode::U64(b))) => {
            a.partial_cmp(&(*b as f64))
        }

        // Strings: lexicographic
        (Value::String(a), Value::String(b)) => Some(a.cmp(b)),

        // Arrays: lexicographic comparison
        (Value::Array(a), Value::Array(b)) => {
            for (av, bv) in a.iter().zip(b.iter()) {
                match compare_values(av, bv) {
                    Some(Ordering::Equal) => continue,
                    other => return other,
                }
            }
            Some(a.len().cmp(&b.len()))
        }

        // Objects: compare by sorted keys, then values
        (Value::Object(a), Value::Object(b)) => {
            let mut a_keys: Vec<_> = a.keys().collect();
            let mut b_keys: Vec<_> = b.keys().collect();
            a_keys.sort();
            b_keys.sort();

            // First compare keys
            for (ak, bk) in a_keys.iter().zip(b_keys.iter()) {
                match ak.cmp(bk) {
                    Ordering::Equal => continue,
                    other => return Some(other),
                }
            }
            if a_keys.len() != b_keys.len() {
                return Some(a_keys.len().cmp(&b_keys.len()));
            }

            // Keys are equal, compare values
            for k in a_keys {
                match compare_values(&a[k], &b[k]) {
                    Some(Ordering::Equal) => continue,
                    other => return other,
                }
            }
            Some(Ordering::Equal)
        }

        // Different types: only equality is well-defined (and it's false)
        _ => None,
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::filter::ast::Span;
    use simd_json::json;

    // Helper to create Filter with default span for tests
    fn f(kind: FilterKind) -> Filter {
        Filter::new(kind, Span::default())
    }

    // Helper to create a boxed filter
    fn bf(kind: FilterKind) -> Box<Filter> {
        Box::new(f(kind))
    }

    // Identity tests
    #[test]
    fn test_identity() {
        let value = json!({"name": "alice"});
        let result = eval(&f(FilterKind::Identity), &value).unwrap();
        assert_eq!(result, vec![value]);
    }

    // Field access tests
    #[test]
    fn test_field_access() {
        let value = json!({"name": "alice", "age": 30});
        let result = eval(&f(FilterKind::Field("name".to_string())), &value).unwrap();
        assert_eq!(result, vec![json!("alice")]);
    }

    #[test]
    fn test_field_missing() {
        let value = json!({"name": "alice"});
        let result = eval(&f(FilterKind::Field("missing".to_string())), &value).unwrap();
        assert_eq!(result, vec![Value::Static(StaticNode::Null)]);
    }

    #[test]
    fn test_field_on_non_object() {
        let result = eval(&f(FilterKind::Field("foo".to_string())), &json!("string")).unwrap();
        assert_eq!(result, vec![Value::Static(StaticNode::Null)]);

        let result = eval(&f(FilterKind::Field("foo".to_string())), &json!(123)).unwrap();
        assert_eq!(result, vec![Value::Static(StaticNode::Null)]);

        let result = eval(&f(FilterKind::Field("foo".to_string())), &json!(null)).unwrap();
        assert_eq!(result, vec![Value::Static(StaticNode::Null)]);

        let result = eval(&f(FilterKind::Field("foo".to_string())), &json!([1, 2, 3])).unwrap();
        assert_eq!(result, vec![Value::Static(StaticNode::Null)]);
    }

    #[test]
    fn test_nested_field() {
        let value = json!({"user": {"name": "alice", "address": {"city": "NYC"}}});
        let filter = f(FilterKind::Pipe(
            bf(FilterKind::Field("user".to_string())),
            bf(FilterKind::Field("name".to_string())),
        ));
        let result = eval(&filter, &value).unwrap();
        assert_eq!(result, vec![json!("alice")]);
    }

    #[test]
    fn test_deeply_nested_field() {
        let value = json!({"user": {"address": {"city": "NYC"}}});
        let filter = f(FilterKind::Pipe(
            bf(FilterKind::Pipe(
                bf(FilterKind::Field("user".to_string())),
                bf(FilterKind::Field("address".to_string())),
            )),
            bf(FilterKind::Field("city".to_string())),
        ));
        let result = eval(&filter, &value).unwrap();
        assert_eq!(result, vec![json!("NYC")]);
    }

    #[test]
    fn test_nested_field_missing() {
        let value = json!({"user": {}});
        let filter = f(FilterKind::Pipe(
            bf(FilterKind::Field("user".to_string())),
            bf(FilterKind::Field("name".to_string())),
        ));
        let result = eval(&filter, &value).unwrap();
        assert_eq!(result, vec![Value::Static(StaticNode::Null)]);
    }

    #[test]
    fn test_field_on_nested_null() {
        let value = json!({"user": null});
        let filter = f(FilterKind::Pipe(
            bf(FilterKind::Field("user".to_string())),
            bf(FilterKind::Field("name".to_string())),
        ));
        let result = eval(&filter, &value).unwrap();
        assert_eq!(result, vec![Value::Static(StaticNode::Null)]);
    }

    // Index tests
    #[test]
    fn test_index_positive() {
        let value = json!([10, 20, 30]);
        assert_eq!(
            eval(&f(FilterKind::Index(0)), &value).unwrap(),
            vec![json!(10)]
        );
        assert_eq!(
            eval(&f(FilterKind::Index(1)), &value).unwrap(),
            vec![json!(20)]
        );
        assert_eq!(
            eval(&f(FilterKind::Index(2)), &value).unwrap(),
            vec![json!(30)]
        );
    }

    #[test]
    fn test_index_negative() {
        let value = json!([10, 20, 30]);
        assert_eq!(
            eval(&f(FilterKind::Index(-1)), &value).unwrap(),
            vec![json!(30)]
        );
        assert_eq!(
            eval(&f(FilterKind::Index(-2)), &value).unwrap(),
            vec![json!(20)]
        );
        assert_eq!(
            eval(&f(FilterKind::Index(-3)), &value).unwrap(),
            vec![json!(10)]
        );
    }

    #[test]
    fn test_index_out_of_bounds() {
        let value = json!([10, 20, 30]);
        assert_eq!(
            eval(&f(FilterKind::Index(10)), &value).unwrap(),
            vec![Value::Static(StaticNode::Null)]
        );
        assert_eq!(
            eval(&f(FilterKind::Index(-10)), &value).unwrap(),
            vec![Value::Static(StaticNode::Null)]
        );
    }

    #[test]
    fn test_index_on_non_array() {
        assert_eq!(
            eval(&f(FilterKind::Index(0)), &json!("string")).unwrap(),
            vec![Value::Static(StaticNode::Null)]
        );
        assert_eq!(
            eval(&f(FilterKind::Index(0)), &json!({"a": 1})).unwrap(),
            vec![Value::Static(StaticNode::Null)]
        );
        assert_eq!(
            eval(&f(FilterKind::Index(0)), &json!(null)).unwrap(),
            vec![Value::Static(StaticNode::Null)]
        );
    }

    // Iterate tests
    #[test]
    fn test_iterate_array() {
        let value = json!([1, 2, 3]);
        let result = eval(&f(FilterKind::Iterate), &value).unwrap();
        assert_eq!(result, vec![json!(1), json!(2), json!(3)]);
    }

    #[test]
    fn test_iterate_object() {
        let value = json!({"a": 1, "b": 2});
        let result = eval(&f(FilterKind::Iterate), &value).unwrap();
        assert_eq!(result.len(), 2);
        assert!(result.contains(&json!(1)));
        assert!(result.contains(&json!(2)));
    }

    #[test]
    fn test_iterate_on_string_fails() {
        let result = eval(&f(FilterKind::Iterate), &json!("string"));
        assert!(result.is_err());
    }

    // Slice tests
    #[test]
    fn test_slice_both_indices() {
        let value = json!([0, 1, 2, 3, 4, 5]);
        let result = eval(&f(FilterKind::Slice(Some(1), Some(4))), &value).unwrap();
        assert_eq!(result, vec![json!([1, 2, 3])]);
    }

    #[test]
    fn test_slice_start_only() {
        let value = json!([0, 1, 2, 3, 4]);
        let result = eval(&f(FilterKind::Slice(Some(2), None)), &value).unwrap();
        assert_eq!(result, vec![json!([2, 3, 4])]);
    }

    #[test]
    fn test_slice_end_only() {
        let value = json!([0, 1, 2, 3, 4]);
        let result = eval(&f(FilterKind::Slice(None, Some(3))), &value).unwrap();
        assert_eq!(result, vec![json!([0, 1, 2])]);
    }

    #[test]
    fn test_slice_negative() {
        let value = json!([0, 1, 2, 3, 4]);
        let result = eval(&f(FilterKind::Slice(Some(-2), None)), &value).unwrap();
        assert_eq!(result, vec![json!([3, 4])]);
    }

    // Pipe tests
    #[test]
    fn test_pipe_chain() {
        let value = json!({"items": [{"id": 1}, {"id": 2}]});
        let filter = f(FilterKind::Pipe(
            bf(FilterKind::Field("items".to_string())),
            bf(FilterKind::Index(0)),
        ));
        let result = eval(&filter, &value).unwrap();
        assert_eq!(result, vec![json!({"id": 1})]);
    }

    // Optional tests
    #[test]
    fn test_optional_iterate_on_non_iterable() {
        let filter = f(FilterKind::Optional(bf(FilterKind::Iterate)));
        let result = eval(&filter, &json!("string")).unwrap();
        let empty: Vec<Value> = vec![];
        assert_eq!(result, empty);
    }

    #[test]
    fn test_optional_iterate_on_array() {
        let filter = f(FilterKind::Optional(bf(FilterKind::Iterate)));
        let result = eval(&filter, &json!([1, 2])).unwrap();
        assert_eq!(result, vec![json!(1), json!(2)]);
    }

    #[test]
    fn test_optional_field_succeeds() {
        let filter = f(FilterKind::Optional(bf(FilterKind::Field(
            "foo".to_string(),
        ))));
        let result = eval(&filter, &json!({"foo": 42})).unwrap();
        assert_eq!(result, vec![json!(42)]);
    }

    // Literal tests
    #[test]
    fn test_literal_number() {
        let filter = f(FilterKind::Literal(json!(42)));
        let result = eval(&filter, &json!(null)).unwrap();
        assert_eq!(result, vec![json!(42)]);
    }

    #[test]
    fn test_literal_string() {
        let filter = f(FilterKind::Literal(json!("hello")));
        let result = eval(&filter, &json!(null)).unwrap();
        assert_eq!(result, vec![json!("hello")]);
    }

    // Comparison tests
    #[test]
    fn test_compare_eq() {
        let filter = f(FilterKind::Compare(
            bf(FilterKind::Identity),
            CompareOp::Eq,
            bf(FilterKind::Literal(json!(5))),
        ));
        assert_eq!(eval(&filter, &json!(5)).unwrap(), vec![json!(true)]);
        assert_eq!(eval(&filter, &json!(3)).unwrap(), vec![json!(false)]);
    }

    #[test]
    fn test_compare_lt() {
        let filter = f(FilterKind::Compare(
            bf(FilterKind::Identity),
            CompareOp::Lt,
            bf(FilterKind::Literal(json!(10))),
        ));
        assert_eq!(eval(&filter, &json!(5)).unwrap(), vec![json!(true)]);
        assert_eq!(eval(&filter, &json!(15)).unwrap(), vec![json!(false)]);
    }

    // Bool op tests
    #[test]
    fn test_bool_and() {
        let filter = f(FilterKind::BoolOp(
            bf(FilterKind::Literal(json!(true))),
            BoolOp::And,
            bf(FilterKind::Literal(json!(false))),
        ));
        assert_eq!(eval(&filter, &json!(null)).unwrap(), vec![json!(false)]);
    }

    #[test]
    fn test_bool_or() {
        let filter = f(FilterKind::BoolOp(
            bf(FilterKind::Literal(json!(false))),
            BoolOp::Or,
            bf(FilterKind::Literal(json!(true))),
        ));
        assert_eq!(eval(&filter, &json!(null)).unwrap(), vec![json!(true)]);
    }

    // Array construction tests
    #[test]
    fn test_array_construction() {
        let filter = f(FilterKind::Array(vec![
            f(FilterKind::Field("a".to_string())),
            f(FilterKind::Field("b".to_string())),
        ]));
        let result = eval(&filter, &json!({"a": 1, "b": 2})).unwrap();
        assert_eq!(result, vec![json!([1, 2])]);
    }

    // Object construction tests
    #[test]
    fn test_object_construction() {
        let filter = f(FilterKind::Object(vec![
            (
                ObjectKey::Static("x".to_string()),
                f(FilterKind::Field("a".to_string())),
            ),
            (
                ObjectKey::Static("y".to_string()),
                f(FilterKind::Field("b".to_string())),
            ),
        ]));
        let result = eval(&filter, &json!({"a": 1, "b": 2})).unwrap();
        assert_eq!(result, vec![json!({"x": 1, "y": 2})]);
    }

    // If-then-else tests
    #[test]
    fn test_if_then_else_true() {
        let filter = f(FilterKind::IfThenElse {
            condition: bf(FilterKind::Literal(json!(true))),
            then_branch: bf(FilterKind::Literal(json!("yes"))),
            else_branch: bf(FilterKind::Literal(json!("no"))),
        });
        assert_eq!(eval(&filter, &json!(null)).unwrap(), vec![json!("yes")]);
    }

    #[test]
    fn test_if_then_else_false() {
        let filter = f(FilterKind::IfThenElse {
            condition: bf(FilterKind::Literal(json!(false))),
            then_branch: bf(FilterKind::Literal(json!("yes"))),
            else_branch: bf(FilterKind::Literal(json!("no"))),
        });
        assert_eq!(eval(&filter, &json!(null)).unwrap(), vec![json!("no")]);
    }

    // Alternative tests
    #[test]
    fn test_alternative_left_truthy() {
        let filter = f(FilterKind::Alternative(
            bf(FilterKind::Literal(json!(42))),
            bf(FilterKind::Literal(json!(0))),
        ));
        assert_eq!(eval(&filter, &json!(null)).unwrap(), vec![json!(42)]);
    }

    #[test]
    fn test_alternative_left_null() {
        let filter = f(FilterKind::Alternative(
            bf(FilterKind::Literal(json!(null))),
            bf(FilterKind::Literal(json!("default"))),
        ));
        assert_eq!(eval(&filter, &json!(null)).unwrap(), vec![json!("default")]);
    }

    // Function tests
    #[test]
    fn test_map() {
        let filter = f(FilterKind::Function(FunctionCall::Map(bf(
            FilterKind::Field("x".to_string()),
        ))));
        let result = eval(&filter, &json!([{"x": 1}, {"x": 2}])).unwrap();
        assert_eq!(result, vec![json!([1, 2])]);
    }

    #[test]
    fn test_select() {
        let filter = f(FilterKind::Function(FunctionCall::Select(bf(
            FilterKind::Compare(
                bf(FilterKind::Identity),
                CompareOp::Gt,
                bf(FilterKind::Literal(json!(2))),
            ),
        ))));
        assert_eq!(eval(&filter, &json!(5)).unwrap(), vec![json!(5)]);
        let empty: Vec<Value> = vec![];
        assert_eq!(eval(&filter, &json!(1)).unwrap(), empty);
    }
}