hashmark/

diff.rs

use crate::merkle::{Merkle, Node};
use crate::path::{FieldPath, PathSegment};

/// Result of comparing two Merkle trees.
#[derive(Debug, Clone, PartialEq)]
pub enum Diff {
    /// The two trees are identical.
    Same,
    /// The two trees differ.
    Different(DiffDetail),
}

/// Details about how two Merkle trees differ.
#[derive(Debug, Clone, PartialEq)]
pub enum DiffDetail {
    /// A leaf value changed.
    Value,

    /// Struct fields changed.
    Struct {
        /// Name of the struct
        name: String,
        /// Changed fields with their names and diffs
        changed_fields: Vec<(String, Diff)>,
    },

    /// Sequence elements changed.
    Seq {
        /// Indices of added elements
        added: Vec<usize>,
        /// Indices of removed elements
        removed: Vec<usize>,
        /// Modified elements with their diffs
        modified: Vec<(usize, Diff)>,
    },

    /// Enum variant changed.
    Enum {
        /// Name of the enum
        name: String,
        /// Old variant name
        old_variant: String,
        /// New variant name
        new_variant: String,
        /// If same variant, the inner diff
        inner: Option<Box<Diff>>,
    },

    /// Map entries changed.
    Map {
        /// Keys of added entries
        added_keys: Vec<String>,
        /// Keys of removed entries
        removed_keys: Vec<String>,
        /// Modified entries with their diffs
        modified: Vec<(String, Diff)>,
    },

    /// Node types don't match.
    TypeMismatch,
}

impl DiffDetail {
    /// Get all changed paths with their change type.
    pub fn changed_paths(&self) -> Vec<(FieldPath, ChangeType)> {
        let mut paths = Vec::new();
        self.collect_paths(FieldPath::new(), &mut paths);
        paths
    }

    fn collect_paths(&self, current: FieldPath, paths: &mut Vec<(FieldPath, ChangeType)>) {
        match self {
            DiffDetail::Value => {
                paths.push((current, ChangeType::Modified));
            }
            DiffDetail::Struct { changed_fields, .. } => {
                for (field_name, diff) in changed_fields {
                    let mut path = current.clone();
                    path.push(PathSegment::Field(field_name.clone()));
                    if let Diff::Different(detail) = diff {
                        detail.collect_paths(path, paths);
                    }
                }
            }
            DiffDetail::Seq {
                added,
                removed,
                modified,
            } => {
                for &idx in added {
                    let mut path = current.clone();
                    path.push(PathSegment::Index(idx));
                    paths.push((path, ChangeType::Added));
                }
                for &idx in removed {
                    let mut path = current.clone();
                    path.push(PathSegment::Index(idx));
                    paths.push((path, ChangeType::Removed));
                }
                for (idx, diff) in modified {
                    let mut path = current.clone();
                    path.push(PathSegment::Index(*idx));
                    if let Diff::Different(detail) = diff {
                        detail.collect_paths(path, paths);
                    }
                }
            }
            DiffDetail::Enum {
                old_variant,
                new_variant,
                inner,
                ..
            } => {
                if old_variant != new_variant {
                    paths.push((current.clone(), ChangeType::VariantChanged));
                }
                if let Some(inner_diff) = inner {
                    if let Diff::Different(detail) = inner_diff.as_ref() {
                        let mut path = current;
                        path.push(PathSegment::Variant(new_variant.clone()));
                        detail.collect_paths(path, paths);
                    }
                }
            }
            DiffDetail::Map {
                added_keys,
                removed_keys,
                modified,
            } => {
                for key in added_keys {
                    let mut path = current.clone();
                    path.push(PathSegment::MapKey(key.clone()));
                    paths.push((path, ChangeType::Added));
                }
                for key in removed_keys {
                    let mut path = current.clone();
                    path.push(PathSegment::MapKey(key.clone()));
                    paths.push((path, ChangeType::Removed));
                }
                for (key, diff) in modified {
                    let mut path = current.clone();
                    path.push(PathSegment::MapKey(key.clone()));
                    if let Diff::Different(detail) = diff {
                        detail.collect_paths(path, paths);
                    }
                }
            }
            DiffDetail::TypeMismatch => {
                paths.push((current, ChangeType::TypeChanged));
            }
        }
    }
}

/// Type of change detected.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
pub enum ChangeType {
    Modified,
    Added,
    Removed,
    VariantChanged,
    TypeChanged,
}

/// Compare two Merkle trees and return their differences.
pub fn merkle_diff(old: &Merkle, new: &Merkle) -> Diff {
    // Fast path: identical digests
    if old.digest == new.digest {
        return Diff::Same;
    }

    match (&old.node, &new.node) {
        // Leaf nodes
        (Node::Leaf(_), Node::Leaf(_)) => Diff::Different(DiffDetail::Value),
        (Node::Unit, Node::Unit) => Diff::Different(DiffDetail::Value),
        (Node::None, Node::None) => Diff::Different(DiffDetail::Value),

        // Struct nodes
        (Node::Struct(old_s), Node::Struct(new_s)) => {
            let changed_fields: Vec<_> = old_s
                .fields
                .iter()
                .zip(&new_s.fields)
                .filter_map(|((old_name, old_m), (new_name, new_m))| {
                    debug_assert_eq!(old_name, new_name);
                    let diff = merkle_diff(old_m, new_m);
                    if diff != Diff::Same {
                        Some((old_name.clone(), diff))
                    } else {
                        None
                    }
                })
                .collect();

            Diff::Different(DiffDetail::Struct {
                name: old_s.name.clone(),
                changed_fields,
            })
        }

        // Sequence nodes
        (Node::Seq(old_s), Node::Seq(new_s)) => {
            let old_len = old_s.elements.len();
            let new_len = new_s.elements.len();
            let common_len = old_len.min(new_len);

            let modified: Vec<_> = old_s.elements[..common_len]
                .iter()
                .zip(&new_s.elements[..common_len])
                .enumerate()
                .filter_map(|(i, (o, n))| {
                    let diff = merkle_diff(o, n);
                    if diff != Diff::Same {
                        Some((i, diff))
                    } else {
                        None
                    }
                })
                .collect();

            let added: Vec<_> = (old_len..new_len).collect();
            let removed: Vec<_> = (new_len..old_len).collect();

            Diff::Different(DiffDetail::Seq {
                added,
                removed,
                modified,
            })
        }

        // Enum nodes
        (Node::Enum(old_e), Node::Enum(new_e)) => {
            if old_e.variant != new_e.variant {
                Diff::Different(DiffDetail::Enum {
                    name: old_e.name.clone(),
                    old_variant: old_e.variant.clone(),
                    new_variant: new_e.variant.clone(),
                    inner: None,
                })
            } else {
                let inner = match (&old_e.data, &new_e.data) {
                    (Some(o), Some(n)) => {
                        let diff = merkle_diff(o, n);
                        if diff != Diff::Same {
                            Some(Box::new(diff))
                        } else {
                            None
                        }
                    }
                    _ => None,
                };

                if inner.is_some() {
                    Diff::Different(DiffDetail::Enum {
                        name: old_e.name.clone(),
                        old_variant: old_e.variant.clone(),
                        new_variant: new_e.variant.clone(),
                        inner,
                    })
                } else {
                    Diff::Different(DiffDetail::Value)
                }
            }
        }

        // Map nodes
        (Node::Map(old_m), Node::Map(new_m)) => {
            let old_keys: std::collections::HashSet<_> =
                old_m.entries.iter().map(|(k, _)| k).collect();
            let new_keys: std::collections::HashSet<_> =
                new_m.entries.iter().map(|(k, _)| k).collect();

            let added_keys: Vec<_> = new_keys
                .difference(&old_keys)
                .map(|k| (*k).clone())
                .collect();
            let removed_keys: Vec<_> = old_keys
                .difference(&new_keys)
                .map(|k| (*k).clone())
                .collect();

            let old_map: std::collections::HashMap<_, _> =
                old_m.entries.iter().map(|(k, v)| (k, v)).collect();
            let new_map: std::collections::HashMap<_, _> =
                new_m.entries.iter().map(|(k, v)| (k, v)).collect();

            let modified: Vec<_> = old_keys
                .intersection(&new_keys)
                .filter_map(|k| {
                    let old_v = old_map.get(*k).unwrap();
                    let new_v = new_map.get(*k).unwrap();
                    let diff = merkle_diff(old_v, new_v);
                    if diff != Diff::Same {
                        Some(((*k).clone(), diff))
                    } else {
                        None
                    }
                })
                .collect();

            Diff::Different(DiffDetail::Map {
                added_keys,
                removed_keys,
                modified,
            })
        }

        // Type mismatch
        _ => Diff::Different(DiffDetail::TypeMismatch),
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    use crate::serializer::tree_hash;
    use serde::Serialize;

    #[test]
    fn test_struct_diff_with_field_names() {
        #[derive(Serialize)]
        struct User {
            name: String,
            age: u32,
            active: bool,
        }

        let u1 = User {
            name: "Alice".into(),
            age: 30,
            active: true,
        };
        let u2 = User {
            name: "Alice".into(),
            age: 31,
            active: true,
        };

        let m1 = tree_hash(&u1).unwrap();
        let m2 = tree_hash(&u2).unwrap();

        let diff = merkle_diff(&m1, &m2);

        if let Diff::Different(DiffDetail::Struct { changed_fields, .. }) = diff {
            assert_eq!(changed_fields.len(), 1);
            assert_eq!(changed_fields[0].0, "age");
        } else {
            panic!("Expected Struct diff");
        }
    }

    #[test]
    fn test_nested_struct_paths() {
        #[derive(Serialize)]
        struct Address {
            city: String,
            zip: String,
        }

        #[derive(Serialize)]
        struct User {
            name: String,
            address: Address,
        }

        let u1 = User {
            name: "Alice".into(),
            address: Address {
                city: "NYC".into(),
                zip: "10001".into(),
            },
        };
        let u2 = User {
            name: "Alice".into(),
            address: Address {
                city: "LA".into(),
                zip: "10001".into(),
            },
        };

        let m1 = tree_hash(&u1).unwrap();
        let m2 = tree_hash(&u2).unwrap();

        let diff = merkle_diff(&m1, &m2);

        if let Diff::Different(detail) = diff {
            let paths = detail.changed_paths();
            assert_eq!(paths.len(), 1);
            assert_eq!(paths[0].0.to_string(), "address.city");
        } else {
            panic!("Expected Different");
        }
    }

    #[test]
    fn test_vec_diff_paths() {
        let v1: Vec<i32> = vec![1, 2, 3];
        let v2: Vec<i32> = vec![1, 5, 3, 4];

        let m1 = tree_hash(&v1).unwrap();
        let m2 = tree_hash(&v2).unwrap();

        let diff = merkle_diff(&m1, &m2);

        if let Diff::Different(detail) = diff {
            let paths = detail.changed_paths();
            // [1] modified, [3] added
            assert!(paths.iter().any(|(p, _)| p.to_string() == "[1]"));
            assert!(paths
                .iter()
                .any(|(p, c)| p.to_string() == "[3]" && *c == ChangeType::Added));
        } else {
            panic!("Expected Different");
        }
    }

    #[test]
    fn test_enum_variant_change() {
        #[derive(Serialize)]
        enum Status {
            Active,
            Suspended { reason: String },
        }

        let s1 = Status::Active;
        let s2 = Status::Suspended {
            reason: "test".into(),
        };

        let m1 = tree_hash(&s1).unwrap();
        let m2 = tree_hash(&s2).unwrap();

        let diff = merkle_diff(&m1, &m2);

        if let Diff::Different(DiffDetail::Enum {
            old_variant,
            new_variant,
            ..
        }) = diff
        {
            assert_eq!(old_variant, "Active");
            assert_eq!(new_variant, "Suspended");
        } else {
            panic!("Expected Enum diff");
        }
    }
}