fionn_diff/

tape_merge.rs

// SPDX-License-Identifier: MIT OR Apache-2.0
//! Tape-based merge operations
//!
//! This module provides merge operations for tape-parsed data, enabling
//! efficient cross-format merging without intermediate serialization.
//!
//! # Overview
//!
//! Merging works by:
//! 1. Converting source tape to a mutable Value
//! 2. Walking the target tape and applying merge rules
//! 3. Returning the merged Value
//!
//! This is more efficient than serialize→parse→merge→serialize because:
//! - Tape parsing is 10-100x faster than DOM parsing
//! - Direct tape walking avoids intermediate allocations
//! - Cross-format merges don't require format conversion
//!
//! # Example
//!
//! ```ignore
//! use fionn_diff::{merge_tapes, deep_merge_tapes};
//! use fionn_simd::transform::UnifiedTape;
//! use fionn_core::format::FormatKind;
//!
//! // Parse YAML and JSON
//! let yaml_tape = UnifiedTape::parse(yaml.as_bytes(), FormatKind::Yaml)?;
//! let json_tape = UnifiedTape::parse(json.as_bytes(), FormatKind::Json)?;
//!
//! // Merge JSON over YAML (JSON takes precedence)
//! let result = merge_tapes(&yaml_tape, &json_tape)?;
//! ```

use fionn_core::Result;
use fionn_core::tape_source::{TapeNodeKind, TapeSource, TapeValue};
use serde_json::{Map, Value};

use crate::tape_patch::tape_to_value;

// ============================================================================
// Tape Merge (RFC 7396 semantics)
// ============================================================================

/// Merge two tapes using RFC 7396 (JSON Merge Patch) semantics
///
/// The `overlay` tape's values take precedence:
/// - `null` values in overlay delete keys from target
/// - Objects are recursively merged
/// - Non-objects replace existing values
///
/// # Example
///
/// ```ignore
/// let base = parse_yaml("name: Alice\nage: 30");
/// let overlay = parse_json(r#"{"name": "Bob", "city": "NYC"}"#);
///
/// let result = merge_tapes(&base, &overlay)?;
/// // {"name": "Bob", "age": 30, "city": "NYC"}
/// ```
///
/// # Errors
///
/// Returns an error if either tape cannot be converted to a value.
pub fn merge_tapes<S: TapeSource, T: TapeSource>(base: &S, overlay: &T) -> Result<Value> {
    let mut base_value = tape_to_value(base)?;
    apply_tape_merge(&mut base_value, overlay)?;
    Ok(base_value)
}

/// Apply merge from a tape onto a mutable Value
fn apply_tape_merge<T: TapeSource>(target: &mut Value, overlay: &T) -> Result<()> {
    if overlay.is_empty() {
        return Ok(());
    }

    let overlay_value = tape_to_value(overlay)?;
    merge_value_into(target, &overlay_value);
    Ok(())
}

/// RFC 7396 merge implementation
fn merge_value_into(target: &mut Value, patch: &Value) {
    // If patch is not an object, it replaces target entirely
    if !patch.is_object() {
        *target = patch.clone();
        return;
    }

    // Ensure target is an object
    if !target.is_object() {
        *target = Value::Object(Map::new());
    }

    let target_obj = target.as_object_mut().expect("target should be object");
    let patch_obj = patch.as_object().expect("patch should be object");

    for (key, patch_value) in patch_obj {
        if patch_value.is_null() {
            // Null means delete
            target_obj.remove(key);
        } else if patch_value.is_object() {
            // Recursive merge for objects
            let target_value = target_obj
                .entry(key.clone())
                .or_insert_with(|| Value::Object(Map::new()));
            merge_value_into(target_value, patch_value);
        } else {
            // Replace/add for non-objects
            target_obj.insert(key.clone(), patch_value.clone());
        }
    }
}

// ============================================================================
// Deep Merge (null-preserving)
// ============================================================================

/// Deep merge two tapes (preserves null values)
///
/// Unlike `merge_tapes` (RFC 7396), this preserves null values
/// instead of treating them as deletions.
///
/// # Example
///
/// ```ignore
/// let base = parse_json(r#"{"a": 1, "b": 2}"#);
/// let overlay = parse_json(r#"{"b": null, "c": 3}"#);
///
/// let result = deep_merge_tapes(&base, &overlay)?;
/// // {"a": 1, "b": null, "c": 3}
/// ```
///
/// # Errors
///
/// Returns an error if either tape cannot be converted to a value.
pub fn deep_merge_tapes<S: TapeSource, T: TapeSource>(base: &S, overlay: &T) -> Result<Value> {
    let base_value = tape_to_value(base)?;
    let overlay_value = tape_to_value(overlay)?;
    Ok(deep_merge_values(&base_value, &overlay_value))
}

/// Deep merge two values (null-preserving)
fn deep_merge_values(base: &Value, overlay: &Value) -> Value {
    match (base, overlay) {
        (Value::Object(base_obj), Value::Object(overlay_obj)) => {
            let mut result = base_obj.clone();

            for (key, overlay_value) in overlay_obj {
                let merged = result.get(key).map_or_else(
                    || overlay_value.clone(),
                    |base_value| deep_merge_values(base_value, overlay_value),
                );
                result.insert(key.clone(), merged);
            }

            Value::Object(result)
        }
        // Non-objects: overlay wins
        (_, overlay) => overlay.clone(),
    }
}

// ============================================================================
// Merge Many
// ============================================================================

/// Merge multiple tapes left-to-right using RFC 7396 semantics
///
/// Each subsequent tape is merged onto the accumulated result.
///
/// # Example
///
/// ```ignore
/// let tapes: Vec<&dyn TapeSource> = vec![&base, &overlay1, &overlay2];
/// let result = merge_many_tapes(tapes)?;
/// ```
///
/// # Errors
///
/// Returns an error if any tape cannot be converted to a value.
pub fn merge_many_tapes<T: TapeSource>(tapes: &[&T]) -> Result<Value> {
    if tapes.is_empty() {
        return Ok(Value::Object(Map::new()));
    }

    let mut result = tape_to_value(tapes[0])?;

    for tape in &tapes[1..] {
        let overlay = tape_to_value(*tape)?;
        merge_value_into(&mut result, &overlay);
    }

    Ok(result)
}

// ============================================================================
// Cross-Format Merge Helpers
// ============================================================================

/// Merge a tape onto an existing Value
///
/// Useful when building up merged results from multiple tapes.
///
/// # Errors
///
/// Returns an error if the overlay tape cannot be converted to a value.
pub fn merge_tape_into_value<T: TapeSource>(target: &mut Value, overlay: &T) -> Result<()> {
    apply_tape_merge(target, overlay)
}

/// Deep merge a tape onto an existing Value
///
/// # Errors
///
/// Returns an error if the overlay tape cannot be converted to a value.
pub fn deep_merge_tape_into_value<T: TapeSource>(target: &mut Value, overlay: &T) -> Result<Value> {
    let overlay_value = tape_to_value(overlay)?;
    Ok(deep_merge_values(target, &overlay_value))
}

// ============================================================================
// Streaming Merge (Memory-Efficient)
// ============================================================================

/// Options for streaming merge operations
#[derive(Debug, Clone, Default)]
pub struct StreamingMergeOptions {
    /// Maximum depth for recursive merge (0 = unlimited)
    pub max_depth: usize,
    /// Stop merging after this many keys (0 = unlimited)
    pub max_keys: usize,
}

impl StreamingMergeOptions {
    /// Create default options
    #[must_use]
    pub fn new() -> Self {
        Self::default()
    }

    /// Set maximum depth
    #[must_use]
    pub const fn with_max_depth(mut self, depth: usize) -> Self {
        self.max_depth = depth;
        self
    }

    /// Set maximum keys
    #[must_use]
    pub const fn with_max_keys(mut self, keys: usize) -> Self {
        self.max_keys = keys;
        self
    }
}

/// Streaming merge that can be interrupted/resumed
///
/// Useful for very large documents where you want to:
/// - Limit memory usage
/// - Get partial results quickly
/// - Cancel long-running merges
///
/// # Errors
///
/// Returns an error if either tape cannot be converted to a value.
pub fn streaming_merge<S: TapeSource, T: TapeSource>(
    base: &S,
    overlay: &T,
    options: &StreamingMergeOptions,
) -> Result<Value> {
    let mut result = tape_to_value(base)?;
    streaming_merge_at(&mut result, overlay, 0, options, &mut 0)?;
    Ok(result)
}

fn streaming_merge_at<T: TapeSource>(
    target: &mut Value,
    overlay: &T,
    idx: usize,
    options: &StreamingMergeOptions,
    keys_processed: &mut usize,
) -> Result<usize> {
    if options.max_keys > 0 && *keys_processed >= options.max_keys {
        // Skip remaining merge
        return overlay.skip_value(idx);
    }

    let node = overlay.node_at(idx);

    let Some(n) = node else {
        return Ok(idx + 1);
    };

    if let TapeNodeKind::ObjectStart { count } = n.kind {
        // Check depth limit
        if options.max_depth > 0 {
            // Would need depth tracking - skip for now
        }

        // Ensure target is object
        if !target.is_object() {
            *target = Value::Object(Map::new());
        }

        let target_obj = target.as_object_mut().unwrap();
        let mut current_idx = idx + 1;

        for _ in 0..count {
            if options.max_keys > 0 && *keys_processed >= options.max_keys {
                break;
            }

            // Get key
            let key = overlay
                .key_at(current_idx)
                .map(std::borrow::Cow::into_owned)
                .unwrap_or_default();
            current_idx += 1;

            *keys_processed += 1;

            // Check for null (deletion)
            if overlay.value_at(current_idx) == Some(TapeValue::Null) {
                target_obj.remove(&key);
                current_idx += 1;
            } else if let Some(inner_node) = overlay.node_at(current_idx) {
                if matches!(inner_node.kind, TapeNodeKind::ObjectStart { .. }) {
                    // Recursive merge
                    let entry = target_obj
                        .entry(key)
                        .or_insert_with(|| Value::Object(Map::new()));
                    current_idx =
                        streaming_merge_at(entry, overlay, current_idx, options, keys_processed)?;
                } else {
                    // Convert and replace
                    let (value, next) = convert_tape_value(overlay, current_idx)?;
                    target_obj.insert(key, value);
                    current_idx = next;
                }
            } else {
                current_idx = overlay.skip_value(current_idx)?;
            }
        }

        Ok(current_idx)
    } else {
        // Non-object overlay replaces target
        let (value, next) = convert_tape_value(overlay, idx)?;
        *target = value;
        Ok(next)
    }
}

/// Convert a tape node to a Value
fn convert_tape_value<T: TapeSource>(tape: &T, idx: usize) -> Result<(Value, usize)> {
    let node = tape.node_at(idx);

    match node {
        Some(n) => match n.kind {
            TapeNodeKind::ObjectStart { count } => {
                let mut map = Map::with_capacity(count);
                let mut current_idx = idx + 1;

                for _ in 0..count {
                    let key = tape
                        .key_at(current_idx)
                        .map(std::borrow::Cow::into_owned)
                        .unwrap_or_default();
                    current_idx += 1;

                    let (value, next_idx) = convert_tape_value(tape, current_idx)?;
                    map.insert(key, value);
                    current_idx = next_idx;
                }

                Ok((Value::Object(map), current_idx))
            }

            TapeNodeKind::ArrayStart { count } => {
                let mut arr = Vec::with_capacity(count);
                let mut current_idx = idx + 1;

                for _ in 0..count {
                    let (value, next_idx) = convert_tape_value(tape, current_idx)?;
                    arr.push(value);
                    current_idx = next_idx;
                }

                Ok((Value::Array(arr), current_idx))
            }

            TapeNodeKind::Value | TapeNodeKind::Key => {
                let value = n.value.map_or(Value::Null, tape_value_to_json);
                Ok((value, idx + 1))
            }

            TapeNodeKind::ObjectEnd | TapeNodeKind::ArrayEnd => Ok((Value::Null, idx + 1)),
        },
        None => Ok((Value::Null, idx + 1)),
    }
}

fn tape_value_to_json(val: TapeValue<'_>) -> Value {
    match val {
        TapeValue::Null => Value::Null,
        TapeValue::Bool(b) => Value::Bool(b),
        TapeValue::Int(n) => Value::Number(n.into()),
        TapeValue::Float(f) => serde_json::Number::from_f64(f).map_or(Value::Null, Value::Number),
        TapeValue::String(s) => Value::String(s.into_owned()),
        TapeValue::RawNumber(s) => {
            // Try parsing as i64 first, then f64, falling back to string
            #[allow(clippy::option_if_let_else)]
            // Chained if-let-else is clearer for fallback parsing
            if let Ok(n) = s.parse::<i64>() {
                Value::Number(n.into())
            } else if let Ok(f) = s.parse::<f64>() {
                serde_json::Number::from_f64(f)
                    .map_or_else(|| Value::String(s.into_owned()), Value::Number)
            } else {
                Value::String(s.into_owned())
            }
        }
    }
}

// ============================================================================
// Tests
// ============================================================================

#[cfg(test)]
mod tests {
    use super::*;
    use fionn_tape::DsonTape;

    fn parse_json(s: &str) -> DsonTape {
        DsonTape::parse(s).expect("valid JSON")
    }

    #[test]
    fn test_merge_tapes_add_field() {
        let base = parse_json(r#"{"a": 1}"#);
        let overlay = parse_json(r#"{"b": 2}"#);

        let result = merge_tapes(&base, &overlay).unwrap();

        assert_eq!(result["a"], 1);
        assert_eq!(result["b"], 2);
    }

    #[test]
    fn test_merge_tapes_replace_field() {
        let base = parse_json(r#"{"a": 1}"#);
        let overlay = parse_json(r#"{"a": 2}"#);

        let result = merge_tapes(&base, &overlay).unwrap();

        assert_eq!(result["a"], 2);
    }

    #[test]
    fn test_merge_tapes_delete_field() {
        let base = parse_json(r#"{"a": 1, "b": 2}"#);
        let overlay = parse_json(r#"{"a": null}"#);

        let result = merge_tapes(&base, &overlay).unwrap();

        assert!(result.get("a").is_none());
        assert_eq!(result["b"], 2);
    }

    #[test]
    fn test_merge_tapes_nested() {
        let base = parse_json(r#"{"user": {"name": "Alice", "age": 30}}"#);
        let overlay = parse_json(r#"{"user": {"age": null, "city": "NYC"}}"#);

        let result = merge_tapes(&base, &overlay).unwrap();

        assert_eq!(result["user"]["name"], "Alice");
        assert!(result["user"].get("age").is_none());
        assert_eq!(result["user"]["city"], "NYC");
    }

    #[test]
    fn test_deep_merge_tapes_preserves_null() {
        let base = parse_json(r#"{"a": 1}"#);
        let overlay = parse_json(r#"{"a": null, "b": 2}"#);

        let result = deep_merge_tapes(&base, &overlay).unwrap();

        assert!(result["a"].is_null());
        assert_eq!(result["b"], 2);
    }

    #[test]
    fn test_deep_merge_tapes_nested() {
        let base = parse_json(r#"{"outer": {"x": 1, "y": 2}}"#);
        let overlay = parse_json(r#"{"outer": {"y": 20, "z": 3}}"#);

        let result = deep_merge_tapes(&base, &overlay).unwrap();

        assert_eq!(result["outer"]["x"], 1);
        assert_eq!(result["outer"]["y"], 20);
        assert_eq!(result["outer"]["z"], 3);
    }

    #[test]
    fn test_merge_tapes_array_replacement() {
        let base = parse_json(r#"{"arr": [1, 2, 3]}"#);
        let overlay = parse_json(r#"{"arr": [4, 5]}"#);

        let result = merge_tapes(&base, &overlay).unwrap();

        let arr = result["arr"].as_array().unwrap();
        assert_eq!(arr.len(), 2);
        assert_eq!(arr[0], 4);
        assert_eq!(arr[1], 5);
    }

    #[test]
    fn test_merge_tape_into_value() {
        let mut value = serde_json::json!({"a": 1});
        let overlay = parse_json(r#"{"b": 2, "c": 3}"#);

        merge_tape_into_value(&mut value, &overlay).unwrap();

        assert_eq!(value["a"], 1);
        assert_eq!(value["b"], 2);
        assert_eq!(value["c"], 3);
    }

    #[test]
    fn test_streaming_merge_basic() {
        let base = parse_json(r#"{"a": 1}"#);
        let overlay = parse_json(r#"{"b": 2}"#);
        let options = StreamingMergeOptions::new();

        let result = streaming_merge(&base, &overlay, &options).unwrap();

        assert_eq!(result["a"], 1);
        assert_eq!(result["b"], 2);
    }

    #[test]
    fn test_streaming_merge_with_max_keys() {
        let base = parse_json(r#"{"a": 1}"#);
        let overlay = parse_json(r#"{"b": 2, "c": 3, "d": 4}"#);
        let options = StreamingMergeOptions::new().with_max_keys(2);

        let result = streaming_merge(&base, &overlay, &options).unwrap();

        // Should have base + limited overlay keys
        assert_eq!(result["a"], 1);
        // Only some overlay keys should be merged due to limit
    }

    #[test]
    fn test_merge_empty_tapes() {
        let base = parse_json(r"{}");
        let overlay = parse_json(r"{}");

        let result = merge_tapes(&base, &overlay).unwrap();

        assert!(result.is_object());
        assert!(result.as_object().unwrap().is_empty());
    }

    #[test]
    fn test_merge_into_empty_base() {
        let base = parse_json(r"{}");
        let overlay = parse_json(r#"{"a": 1, "b": 2}"#);

        let result = merge_tapes(&base, &overlay).unwrap();

        assert_eq!(result["a"], 1);
        assert_eq!(result["b"], 2);
    }

    #[test]
    fn test_merge_complex_nested() {
        let base = parse_json(
            r#"{"config": {"server": {"host": "localhost", "port": 8080}, "database": {"url": "db://local"}}}"#,
        );
        let overlay =
            parse_json(r#"{"config": {"server": {"port": 9000}, "logging": {"level": "debug"}}}"#);

        let result = merge_tapes(&base, &overlay).unwrap();

        assert_eq!(result["config"]["server"]["host"], "localhost");
        assert_eq!(result["config"]["server"]["port"], 9000);
        assert_eq!(result["config"]["database"]["url"], "db://local");
        assert_eq!(result["config"]["logging"]["level"], "debug");
    }
}