20074615249

Committed 09 Dec 2025 06:40PM UTC coverage: 58.494% (+0.2%) from 58.279%

Build # 20074615249

Build Type

push

github

Committed by

fasterthanlime

Commit Message

feat(facet-core): add #[facet(metadata = kind)] field attribute

Adds a new `metadata` field attribute for marking fields that contain
auxiliary information (like source spans) that should be excluded from
structural equality and hashing.

Changes:
- Add `metadata: Option<&'static str>` field to `Field` struct
- Add `is_metadata()` and `metadata_kind()` helper methods
- Add `.metadata(kind)` builder method to `FieldBuilder`
- Handle `#[facet(metadata = kind)]` in derive macro
- Update `structural_hash` to skip metadata fields
- Update `Spanned<T>` to use `#[facet(metadata = span)]` on span field
- Update `is_spanned_shape()` to detect via metadata field
- Add `find_span_metadata_field()` helper function
- Update facet-json deserializer to use new metadata detection

This allows any struct to have span tracking by adding the metadata
attribute, not just the built-in `Spanned<T>` wrapper. Deserializers
can check `field.metadata_kind() == Some("span")` to know which field
to populate with source location information.

Also includes preparatory work for GumTree-style tree diffing:
- Add tree.rs module with tree building and diff algorithm
- Update showcase to demonstrate new tree diff output

Run Details

359 of 495 new or added lines in 7 files covered. (72.53%)

1 existing line in 1 file now uncovered.

26860 of 45919 relevant lines covered (58.49%)

619.28 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

77.11

/facet-diff/src/tree.rs

//! GumTree-style tree diffing algorithm.
//!
//! This module implements a tree diff algorithm based on the GumTree paper
//! (ICSE 2014). It works in phases:
//!
//! 1. **Build trees**: Convert Peek values into a tree representation with hashes
//! 2. **Top-down matching**: Match nodes with identical hashes (identical subtrees)
//! 3. **Bottom-up matching**: Match remaining nodes by similarity
//! 4. **Edit script**: Generate insert/delete/update/move operations

use std::collections::{HashMap, HashSet};
use std::hash::{DefaultHasher, Hasher};

use facet_reflect::Peek;

/// Unique identifier for a node in the tree
#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
pub struct NodeId(usize);

/// A path segment describing how to reach a child
#[derive(Debug, Clone, PartialEq, Eq)]
pub enum PathSegment {
    /// A named field in a struct
    Field(&'static str),
    /// An index in a list/array
    Index(usize),
    /// A key in a map
    Key(String),
    /// An enum variant
    Variant(&'static str),
}

/// A path from root to a node
#[derive(Debug, Clone, PartialEq, Eq, Default)]
pub struct Path(pub Vec<PathSegment>);

impl Path {
    /// Create a new empty path
    pub fn new() -> Self {
        Self(Vec::new())
    }

    /// Append a segment to this path
    pub fn push(&mut self, segment: PathSegment) {
        self.0.push(segment);
    }

    /// Create a new path with an additional segment
    pub fn with(&self, segment: PathSegment) -> Self {
        let mut new = self.clone();
        new.push(segment);
        new
    }
}

impl std::fmt::Display for Path {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        for (i, segment) in self.0.iter().enumerate() {
            if i > 0 {
                write!(f, ".")?;
            }
            match segment {
                PathSegment::Field(name) => write!(f, "{}", name)?,
                PathSegment::Index(idx) => write!(f, "[{}]", idx)?,
                PathSegment::Key(key) => write!(f, "[{:?}]", key)?,
                PathSegment::Variant(name) => write!(f, "::{}", name)?,
            }
        }
        Ok(())
    }
}

/// The kind of node (for type-based matching)
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
pub enum NodeKind {
    /// A struct with the given type name
    Struct(&'static str),
    /// An enum variant
    EnumVariant(&'static str, &'static str), // (enum_name, variant_name)
    /// A list/array element
    ListElement,
    /// A map entry
    MapEntry,
    /// A scalar value
    Scalar(&'static str),
    /// Root node
    Root,
}

/// A node in the tree representation
#[derive(Debug)]
pub struct TreeNode {
    /// Unique identifier
    pub id: NodeId,
    /// The kind of this node
    pub kind: NodeKind,
    /// Structural hash of this node and all descendants
    pub hash: u64,
    /// Height of this node (leaves = 0, internal = max child height + 1)
    pub height: usize,
    /// Path from root to this node
    pub path: Path,
    /// Children of this node
    pub children: Vec<NodeId>,
    /// Parent of this node (None for root)
    pub parent: Option<NodeId>,
}

/// A tree built from a Peek value
#[derive(Debug)]
pub struct Tree {
    /// All nodes in the tree
    nodes: Vec<TreeNode>,
    /// The root node ID
    pub root: NodeId,
}

impl Tree {
    /// Get a node by ID
    pub fn get(&self, id: NodeId) -> &TreeNode {
        &self.nodes[id.0]
    }

    /// Get all nodes
    pub fn nodes(&self) -> impl Iterator<Item = &TreeNode> {
        self.nodes.iter()
    }

    /// Get nodes in post-order (children before parents)
    pub fn post_order(&self) -> impl Iterator<Item = &TreeNode> {
        PostOrderIter::new(self)
    }

    /// Get the number of nodes
    pub fn len(&self) -> usize {
        self.nodes.len()
    }

    /// Check if the tree is empty
    pub fn is_empty(&self) -> bool {
        self.nodes.is_empty()
    }

    /// Get all descendants of a node (including the node itself)
    pub fn descendants(&self, id: NodeId) -> HashSet<NodeId> {
        let mut result = HashSet::new();
        self.collect_descendants(id, &mut result);
        result
    }

    fn collect_descendants(&self, id: NodeId, result: &mut HashSet<NodeId>) {
        result.insert(id);
        for &child_id in &self.nodes[id.0].children {
            self.collect_descendants(child_id, result);
        }
    }
}

/// Post-order iterator over tree nodes
struct PostOrderIter<'a> {
    tree: &'a Tree,
    stack: Vec<(NodeId, bool)>, // (node_id, children_visited)
}

impl<'a> PostOrderIter<'a> {
    fn new(tree: &'a Tree) -> Self {
        let mut stack = Vec::new();
        if !tree.nodes.is_empty() {
            stack.push((tree.root, false));
        }
        Self { tree, stack }
    }
}

impl<'a> Iterator for PostOrderIter<'a> {
    type Item = &'a TreeNode;

    fn next(&mut self) -> Option<Self::Item> {
        while let Some((id, children_visited)) = self.stack.pop() {
            if children_visited {
                return Some(&self.tree.nodes[id.0]);
            }
            // Push this node back with children_visited = true
            self.stack.push((id, true));
            // Push children (in reverse order so they come out in order)
            for &child_id in self.tree.nodes[id.0].children.iter().rev() {
                self.stack.push((child_id, false));
            }
        }
        None
    }
}

/// Builder for constructing a Tree from a Peek value
pub struct TreeBuilder {
    nodes: Vec<TreeNode>,
}

impl TreeBuilder {
    /// Build a tree from a Peek value
    pub fn build<'mem, 'facet>(peek: Peek<'mem, 'facet>) -> Tree {
        let mut builder = TreeBuilder { nodes: Vec::new() };
        let root = builder.build_node(peek, None, Path::new());
        Tree {
            nodes: builder.nodes,
            root,
        }
    }

    fn build_node<'mem, 'facet>(
        &mut self,
        peek: Peek<'mem, 'facet>,
        parent: Option<NodeId>,
        path: Path,
    ) -> NodeId {
        use facet_core::{Def, StructKind, Type, UserType};
        use facet_reflect::HasFields;

        let id = NodeId(self.nodes.len());

        // Determine the kind based on the shape
        let kind = match peek.shape().ty {
            Type::User(UserType::Struct(_)) => NodeKind::Struct(peek.shape().type_identifier),
            Type::User(UserType::Enum(_)) => {
                if let Ok(e) = peek.into_enum() {
                    if let Ok(variant) = e.active_variant() {
                        NodeKind::EnumVariant(peek.shape().type_identifier, variant.name)
                    } else {
                        NodeKind::Scalar(peek.shape().type_identifier)
                    }
                } else {
                    NodeKind::Scalar(peek.shape().type_identifier)
                }
            }
            _ => match peek.shape().def {
                Def::List(_) | Def::Array(_) | Def::Slice(_) => {
                    NodeKind::Scalar(peek.shape().type_identifier)
                }
                Def::Map(_) => NodeKind::Scalar(peek.shape().type_identifier),
                _ => NodeKind::Scalar(peek.shape().type_identifier),
            },
        };

        // Create placeholder node (we'll fill in hash and height after children)
        self.nodes.push(TreeNode {
            id,
            kind: kind.clone(),
            hash: 0,
            height: 0,
            path: path.clone(),
            children: Vec::new(),
            parent,
        });

        // Build children and collect their info
        let mut children = Vec::new();
        let mut max_child_height = 0;

        match peek.shape().ty {
            Type::User(UserType::Struct(_)) => {
                // Struct: add each field as a child
                if let Ok(s) = peek.into_struct() {
                    for (field, field_peek) in s.fields() {
                        let child_path = path.with(PathSegment::Field(field.name));
                        let child_id = self.build_node(field_peek, Some(id), child_path);
                        children.push(child_id);
                        max_child_height = max_child_height.max(self.nodes[child_id.0].height);
                    }
                }
            }
            Type::User(UserType::Enum(_)) => {
                // Enum: add variant fields as children
                if let Ok(e) = peek.into_enum()
                    && let Ok(variant) = e.active_variant()
                {
                    let variant_path = path.with(PathSegment::Variant(variant.name));
                    for (i, (field, field_peek)) in e.fields().enumerate() {
                        let child_path = if variant.data.kind == StructKind::Struct {
                            variant_path.with(PathSegment::Field(field.name))
                        } else {
                            variant_path.with(PathSegment::Index(i))
                        };
                        let child_id = self.build_node(field_peek, Some(id), child_path);
                        children.push(child_id);
                        max_child_height = max_child_height.max(self.nodes[child_id.0].height);
                    }
                }
            }
            _ => {
                // Handle Def-based types
                match peek.shape().def {
                    Def::List(_) | Def::Array(_) | Def::Slice(_) => {
                        if let Ok(list) = peek.into_list_like() {
                            for (i, elem) in list.iter().enumerate() {
                                let child_path = path.with(PathSegment::Index(i));
                                let child_id = self.build_node(elem, Some(id), child_path);
                                children.push(child_id);
                                max_child_height =
                                    max_child_height.max(self.nodes[child_id.0].height);
                            }
                        }
                    }
                    Def::Map(_) => {
                        if let Ok(map) = peek.into_map() {
                            for (key, value) in map.iter() {
                                // Use the key's string representation
                                let key_str = format!("{:?}", key);
                                let child_path = path.with(PathSegment::Key(key_str));
                                let child_id = self.build_node(value, Some(id), child_path);
                                children.push(child_id);
                                max_child_height =
                                    max_child_height.max(self.nodes[child_id.0].height);
                            }
                        }
                    }
                    Def::Option(_) => {
                        if let Ok(opt) = peek.into_option()
                            && let Some(inner) = opt.value()
                        {
                            let child_id = self.build_node(inner, Some(id), path.clone());
                            children.push(child_id);
                            max_child_height = max_child_height.max(self.nodes[child_id.0].height);
                        }
                    }
                    _ => {
                        // Scalar or other leaf node - no children
                    }
                }
            }
        }

        // Compute hash using structural_hash from Peek
        let mut hasher = DefaultHasher::new();
        peek.structural_hash(&mut hasher);
        let hash = hasher.finish();

        // Update node with computed values
        let node = &mut self.nodes[id.0];
        node.children = children;
        node.hash = hash;
        node.height = if node.children.is_empty() {
            0
        } else {
            max_child_height + 1
        };

        id
    }
}

/// A mapping between nodes in two trees
#[derive(Debug, Default)]
pub struct Matching {
    /// Map from tree A node to tree B node
    a_to_b: HashMap<NodeId, NodeId>,
    /// Map from tree B node to tree A node
    b_to_a: HashMap<NodeId, NodeId>,
}

impl Matching {
    /// Create a new empty matching
    pub fn new() -> Self {
        Self::default()
    }

    /// Add a match between two nodes
    pub fn add(&mut self, a: NodeId, b: NodeId) {
        self.a_to_b.insert(a, b);
        self.b_to_a.insert(b, a);
    }

    /// Check if a node from tree A is matched
    pub fn contains_a(&self, a: NodeId) -> bool {
        self.a_to_b.contains_key(&a)
    }

    /// Check if a node from tree B is matched
    pub fn contains_b(&self, b: NodeId) -> bool {
        self.b_to_a.contains_key(&b)
    }

    /// Get the match for a node from tree A
    pub fn get_b(&self, a: NodeId) -> Option<NodeId> {
        self.a_to_b.get(&a).copied()
    }

    /// Get the match for a node from tree B
    pub fn get_a(&self, b: NodeId) -> Option<NodeId> {
        self.b_to_a.get(&b).copied()
    }

    /// Get all matched pairs
    pub fn pairs(&self) -> impl Iterator<Item = (NodeId, NodeId)> + '_ {
        self.a_to_b.iter().map(|(&a, &b)| (a, b))
    }
}

/// Phase 1 & 2: Top-down matching based on hash equality
pub fn top_down_match(tree_a: &Tree, tree_b: &Tree) -> Matching {
    let mut matching = Matching::new();

    // Build hash -> nodes index for tree B
    let mut b_by_hash: HashMap<u64, Vec<NodeId>> = HashMap::new();
    for node in tree_b.nodes() {
        b_by_hash.entry(node.hash).or_default().push(node.id);
    }

    // Priority queue: process higher nodes first (by height, descending)
    let mut queue: Vec<(NodeId, NodeId)> = vec![(tree_a.root, tree_b.root)];

    // Sort by height descending
    queue.sort_by(|a, b| {
        let ha = tree_a.get(a.0).height;
        let hb = tree_a.get(b.0).height;
        hb.cmp(&ha)
    });

    while let Some((a_id, b_id)) = queue.pop() {
        let a_node = tree_a.get(a_id);
        let b_node = tree_b.get(b_id);

        // If already matched, skip
        if matching.contains_a(a_id) || matching.contains_b(b_id) {
            continue;
        }

        // If hashes match, these subtrees are identical
        if a_node.hash == b_node.hash {
            // Match this node and all descendants
            match_subtrees(tree_a, tree_b, a_id, b_id, &mut matching);
        } else {
            // Hashes differ - try to match children
            for &a_child in &a_node.children {
                let a_child_node = tree_a.get(a_child);

                // Find candidates in B with matching hash
                if let Some(b_candidates) = b_by_hash.get(&a_child_node.hash) {
                    for &b_candidate in b_candidates {
                        if !matching.contains_b(b_candidate) {
                            queue.push((a_child, b_candidate));
                        }
                    }
                }

                // Also try matching with children of b_id that have same kind
                for &b_child in &b_node.children {
                    if !matching.contains_b(b_child) {
                        let b_child_node = tree_b.get(b_child);
                        if a_child_node.kind == b_child_node.kind {
                            queue.push((a_child, b_child));
                        }
                    }
                }
            }
        }
    }

    matching
}

/// Match two subtrees recursively (when hashes match)
fn match_subtrees(
    tree_a: &Tree,
    tree_b: &Tree,
    a_id: NodeId,
    b_id: NodeId,
    matching: &mut Matching,
) {
    matching.add(a_id, b_id);

    let a_node = tree_a.get(a_id);
    let b_node = tree_b.get(b_id);

    // Match children in order (they should be identical if hashes match)
    for (a_child, b_child) in a_node.children.iter().zip(b_node.children.iter()) {
        match_subtrees(tree_a, tree_b, *a_child, *b_child, matching);
    }
}

/// Phase 3: Bottom-up matching for unmatched nodes
pub fn bottom_up_match(tree_a: &Tree, tree_b: &Tree, matching: &mut Matching) {
    const SIMILARITY_THRESHOLD: f64 = 0.5;

    // Build kind -> nodes index for tree B (unmatched only)
    let mut b_by_kind: HashMap<NodeKind, Vec<NodeId>> = HashMap::new();
    for node in tree_b.nodes() {
        if !matching.contains_b(node.id) {
            b_by_kind
                .entry(node.kind.clone())
                .or_default()
                .push(node.id);
        }
    }

    // Process tree A in post-order (children before parents)
    for a_node in tree_a.post_order() {
        if matching.contains_a(a_node.id) {
            continue;
        }

        // Find candidates with same kind
        let candidates = b_by_kind.get(&a_node.kind).cloned().unwrap_or_default();

        // Score candidates by dice coefficient
        let mut best: Option<(NodeId, f64)> = None;
        for b_id in candidates {
            if matching.contains_b(b_id) {
                continue;
            }

            let score = dice_coefficient(tree_a, tree_b, a_node.id, b_id, matching);
            if score >= SIMILARITY_THRESHOLD && (best.is_none() || score > best.unwrap().1) {
                best = Some((b_id, score));
            }
        }

        if let Some((b_id, _)) = best {
            matching.add(a_node.id, b_id);
        }
    }
}

/// Compute dice coefficient between two nodes based on matched descendants
fn dice_coefficient(
    tree_a: &Tree,
    tree_b: &Tree,
    a_id: NodeId,
    b_id: NodeId,
    matching: &Matching,
) -> f64 {
    let desc_a = tree_a.descendants(a_id);
    let desc_b = tree_b.descendants(b_id);

    let common = desc_a
        .iter()
        .filter(|&&a| {
            matching
                .get_b(a)
                .map(|b| desc_b.contains(&b))
                .unwrap_or(false)
        })
        .count();

    if desc_a.is_empty() && desc_b.is_empty() {
        1.0 // Both are leaves with no descendants
    } else {
        2.0 * common as f64 / (desc_a.len() + desc_b.len()) as f64
    }
}

/// An edit operation in the diff
#[derive(Debug, Clone, PartialEq, Eq)]
#[non_exhaustive]
pub enum EditOp {
    /// A value was updated (matched but content differs)
    Update {
        /// The path to the updated node
        path: Path,
        /// Hash of the old value
        old_hash: u64,
        /// Hash of the new value
        new_hash: u64,
    },
    /// A node was inserted in tree B
    Insert {
        /// The path where the node was inserted
        path: Path,
        /// Hash of the inserted value
        hash: u64,
    },
    /// A node was deleted from tree A
    Delete {
        /// The path where the node was deleted
        path: Path,
        /// Hash of the deleted value
        hash: u64,
    },
    /// A node was moved from one location to another
    Move {
        /// The original path
        old_path: Path,
        /// The new path
        new_path: Path,
        /// Hash of the moved value
        hash: u64,
    },
}

/// Phase 4: Generate edit script from matching
pub fn generate_edit_script(tree_a: &Tree, tree_b: &Tree, matching: &Matching) -> Vec<EditOp> {
    let mut ops = Vec::new();

    // Deletions: nodes in A that are not matched
    for a_node in tree_a.nodes() {
        if !matching.contains_a(a_node.id) {
            ops.push(EditOp::Delete {
                path: a_node.path.clone(),
                hash: a_node.hash,
            });
        }
    }

    // Insertions: nodes in B that are not matched
    for b_node in tree_b.nodes() {
        if !matching.contains_b(b_node.id) {
            ops.push(EditOp::Insert {
                path: b_node.path.clone(),
                hash: b_node.hash,
            });
        }
    }

    // Updates and Moves: matched nodes where something changed
    for (a_id, b_id) in matching.pairs() {
        let a_node = tree_a.get(a_id);
        let b_node = tree_b.get(b_id);

        // Check if path changed (move)
        if a_node.path != b_node.path {
            ops.push(EditOp::Move {
                old_path: a_node.path.clone(),
                new_path: b_node.path.clone(),
                hash: b_node.hash,
            });
        }
        // Check if hash changed (update) - note: if subtrees matched by hash, they're identical
        // But if matched by similarity, content may differ
        else if a_node.hash != b_node.hash {
            ops.push(EditOp::Update {
                path: a_node.path.clone(),
                old_hash: a_node.hash,
                new_hash: b_node.hash,
            });
        }
    }

    ops
}

/// Compute the tree diff between two values
pub fn tree_diff<'a, 'f, A: facet_core::Facet<'f>, B: facet_core::Facet<'f>>(
    a: &'a A,
    b: &'a B,
) -> Vec<EditOp> {
    let peek_a = Peek::new(a);
    let peek_b = Peek::new(b);

    let tree_a = TreeBuilder::build(peek_a);
    let tree_b = TreeBuilder::build(peek_b);

    let mut matching = top_down_match(&tree_a, &tree_b);
    bottom_up_match(&tree_a, &tree_b, &mut matching);

    generate_edit_script(&tree_a, &tree_b, &matching)
}

#[cfg(test)]
mod tests {
    use super::*;
    use facet::Facet;

    #[derive(Debug, Clone, PartialEq, Facet)]
    struct Person {
        name: String,
        age: u32,
    }

    #[test]
    fn test_identical_trees() {
        let a = Person {
            name: "Alice".into(),
            age: 30,
        };
        let b = a.clone();

        let ops = tree_diff(&a, &b);
        assert!(ops.is_empty(), "Identical trees should have no edits");
    }

    #[test]
    fn test_simple_update() {
        let a = Person {
            name: "Alice".into(),
            age: 30,
        };
        let b = Person {
            name: "Alice".into(),
            age: 31,
        };

        let ops = tree_diff(&a, &b);
        // Should have some update operations
        assert!(!ops.is_empty(), "Changed values should have edits");
    }

    #[test]
    fn test_tree_building() {
        let person = Person {
            name: "Alice".into(),
            age: 30,
        };

        let peek = Peek::new(&person);
        let tree = TreeBuilder::build(peek);

        // Should have root + 2 fields
        assert!(tree.len() >= 3, "Tree should have root and field nodes");
    }
}

1	//! GumTree-style tree diffing algorithm.
2	//!
3	//! This module implements a tree diff algorithm based on the GumTree paper
4	//! (ICSE 2014). It works in phases:
5	//!
6	//! 1. Build trees: Convert Peek values into a tree representation with hashes
7	//! 2. Top-down matching: Match nodes with identical hashes (identical subtrees)
8	//! 3. Bottom-up matching: Match remaining nodes by similarity
9	//! 4. Edit script: Generate insert/delete/update/move operations
10
11	use std::collections::{HashMap, HashSet};
12	use std::hash::{DefaultHasher, Hasher};
13
14	use facet_reflect::Peek;
15
16	/// Unique identifier for a node in the tree
17	#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
18	pub struct NodeId(usize);
19
20	/// A path segment describing how to reach a child
21	#[derive(Debug, Clone, PartialEq, Eq)]
22	pub enum PathSegment {
23	/// A named field in a struct
24	Field(&'static str),
25	/// An index in a list/array
26	Index(usize),
27	/// A key in a map
28	Key(String),
29	/// An enum variant
30	Variant(&'static str),
31	}
32
33	/// A path from root to a node
34	#[derive(Debug, Clone, PartialEq, Eq, Default)]
35	pub struct Path(pub Vec<PathSegment>);
36
37	impl Path {
38	/// Create a new empty path
39	pub fn new() -> Self {	5✔
40	Self(Vec::new())	5✔
41	}	5✔
42
43	/// Append a segment to this path
44	pub fn push(&mut self, segment: PathSegment) {	10✔
45	self.0.push(segment);	10✔
46	}	10✔
47
48	/// Create a new path with an additional segment
49	pub fn with(&self, segment: PathSegment) -> Self {	10✔
50	let mut new = self.clone();	10✔
51	new.push(segment);	10✔
52	new	10✔
53	}	10✔
54	}
55
56	impl std::fmt::Display for Path {
NEW 57	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {	×
NEW 58	for (i, segment) in self.0.iter().enumerate() {	×
NEW 59	if i > 0 {	×
NEW 60	write!(f, ".")?;	×
NEW 61	}	×
NEW 62	match segment {	×
NEW 63	PathSegment::Field(name) => write!(f, "{}", name)?,	×
NEW 64	PathSegment::Index(idx) => write!(f, "[{}]", idx)?,	×
NEW 65	PathSegment::Key(key) => write!(f, "[{:?}]", key)?,	×
NEW 66	PathSegment::Variant(name) => write!(f, "::{}", name)?,	×
67	}
68	}
NEW 69	Ok(())	×
NEW 70	}	×
71	}
72
73	/// The kind of node (for type-based matching)
74	#[derive(Debug, Clone, PartialEq, Eq, Hash)]
75	pub enum NodeKind {
76	/// A struct with the given type name
77	Struct(&'static str),
78	/// An enum variant
79	EnumVariant(&'static str, &'static str), // (enum_name, variant_name)
80	/// A list/array element
81	ListElement,
82	/// A map entry
83	MapEntry,
84	/// A scalar value
85	Scalar(&'static str),
86	/// Root node
87	Root,
88	}
89
90	/// A node in the tree representation
91	#[derive(Debug)]
92	pub struct TreeNode {
93	/// Unique identifier
94	pub id: NodeId,
95	/// The kind of this node
96	pub kind: NodeKind,
97	/// Structural hash of this node and all descendants
98	pub hash: u64,
99	/// Height of this node (leaves = 0, internal = max child height + 1)
100	pub height: usize,
101	/// Path from root to this node
102	pub path: Path,
103	/// Children of this node
104	pub children: Vec<NodeId>,
105	/// Parent of this node (None for root)
106	pub parent: Option<NodeId>,
107	}
108
109	/// A tree built from a Peek value
110	#[derive(Debug)]
111	pub struct Tree {
112	/// All nodes in the tree
113	nodes: Vec<TreeNode>,
114	/// The root node ID
115	pub root: NodeId,
116	}
117
118	impl Tree {
119	/// Get a node by ID
120	pub fn get(&self, id: NodeId) -> &TreeNode {	32✔
121	&self.nodes[id.0]	32✔
122	}	32✔
123
124	/// Get all nodes
125	pub fn nodes(&self) -> impl Iterator<Item = &TreeNode> {	8✔
126	self.nodes.iter()	8✔
127	}	8✔
128
129	/// Get nodes in post-order (children before parents)
130	pub fn post_order(&self) -> impl Iterator<Item = &TreeNode> {	2✔
131	PostOrderIter::new(self)	2✔
132	}	2✔
133
134	/// Get the number of nodes
135	pub fn len(&self) -> usize {	1✔
136	self.nodes.len()	1✔
137	}	1✔
138
139	/// Check if the tree is empty
NEW 140	pub fn is_empty(&self) -> bool {	×
NEW 141	self.nodes.is_empty()	×
NEW 142	}	×
143
144	/// Get all descendants of a node (including the node itself)
145	pub fn descendants(&self, id: NodeId) -> HashSet<NodeId> {	4✔
146	let mut result = HashSet::new();	4✔
147	self.collect_descendants(id, &mut result);	4✔
148	result	4✔
149	}	4✔
150
151	fn collect_descendants(&self, id: NodeId, result: &mut HashSet<NodeId>) {	8✔
152	result.insert(id);	8✔
153	for &child_id in &self.nodes[id.0].children {	8✔
154	self.collect_descendants(child_id, result);	4✔
155	}	4✔
156	}	8✔
157	}
158
159	/// Post-order iterator over tree nodes
160	struct PostOrderIter<'a> {
161	tree: &'a Tree,
162	stack: Vec<(NodeId, bool)>, // (node_id, children_visited)
163	}
164
165	impl<'a> PostOrderIter<'a> {
166	fn new(tree: &'a Tree) -> Self {	2✔
167	let mut stack = Vec::new();	2✔
168	if !tree.nodes.is_empty() {	2✔
169	stack.push((tree.root, false));	2✔
170	}	2✔
171	Self { tree, stack }	2✔
172	}	2✔
173	}
174
175	impl<'a> Iterator for PostOrderIter<'a> {
176	type Item = &'a TreeNode;
177
178	fn next(&mut self) -> Option<Self::Item> {	8✔
179	while let Some((id, children_visited)) = self.stack.pop() {	14✔
180	if children_visited {	12✔
181	return Some(&self.tree.nodes[id.0]);	6✔
182	}	6✔
183	// Push this node back with children_visited = true
184	self.stack.push((id, true));	6✔
185	// Push children (in reverse order so they come out in order)
186	for &child_id in self.tree.nodes[id.0].children.iter().rev() {	6✔
187	self.stack.push((child_id, false));	4✔
188	}	4✔
189	}
190	None	2✔
191	}	8✔
192	}
193
194	/// Builder for constructing a Tree from a Peek value
195	pub struct TreeBuilder {
196	nodes: Vec<TreeNode>,
197	}
198
199	impl TreeBuilder {
200	/// Build a tree from a Peek value
201	pub fn build<'mem, 'facet>(peek: Peek<'mem, 'facet>) -> Tree {	5✔
202	let mut builder = TreeBuilder { nodes: Vec::new() };	5✔
203	let root = builder.build_node(peek, None, Path::new());	5✔
204	Tree {	5✔
205	nodes: builder.nodes,	5✔
206	root,	5✔
207	}	5✔
208	}	5✔
209
210	fn build_node<'mem, 'facet>(	15✔
211	&mut self,	15✔
212	peek: Peek<'mem, 'facet>,	15✔
213	parent: Option<NodeId>,	15✔
214	path: Path,	15✔
215	) -> NodeId {	15✔
216	use facet_core::{Def, StructKind, Type, UserType};
217	use facet_reflect::HasFields;
218
219	let id = NodeId(self.nodes.len());	15✔
220
221	// Determine the kind based on the shape
222	let kind = match peek.shape().ty {	15✔
223	Type::User(UserType::Struct(_)) => NodeKind::Struct(peek.shape().type_identifier),	5✔
224	Type::User(UserType::Enum(_)) => {
NEW 225	if let Ok(e) = peek.into_enum() {	×
NEW 226	if let Ok(variant) = e.active_variant() {	×
NEW 227	NodeKind::EnumVariant(peek.shape().type_identifier, variant.name)	×
228	} else {
NEW 229	NodeKind::Scalar(peek.shape().type_identifier)	×
230	}
231	} else {
NEW 232	NodeKind::Scalar(peek.shape().type_identifier)	×
233	}
234	}
235	_ => match peek.shape().def {	10✔
236	Def::List(_) \| Def::Array(_) \| Def::Slice(_) => {
NEW 237	NodeKind::Scalar(peek.shape().type_identifier)	×
238	}
NEW 239	Def::Map(_) => NodeKind::Scalar(peek.shape().type_identifier),	×
240	_ => NodeKind::Scalar(peek.shape().type_identifier),	10✔
241	},
242	};
243
244	// Create placeholder node (we'll fill in hash and height after children)
245	self.nodes.push(TreeNode {	15✔
246	id,	15✔
247	kind: kind.clone(),	15✔
248	hash: 0,	15✔
249	height: 0,	15✔
250	path: path.clone(),	15✔
251	children: Vec::new(),	15✔
252	parent,	15✔
253	});	15✔
254
255	// Build children and collect their info
256	let mut children = Vec::new();	15✔
257	let mut max_child_height = 0;	15✔
258
259	match peek.shape().ty {	15✔
260	Type::User(UserType::Struct(_)) => {
261	// Struct: add each field as a child
262	if let Ok(s) = peek.into_struct() {	5✔
263	for (field, field_peek) in s.fields() {	10✔
264	let child_path = path.with(PathSegment::Field(field.name));	10✔
265	let child_id = self.build_node(field_peek, Some(id), child_path);	10✔
266	children.push(child_id);	10✔
267	max_child_height = max_child_height.max(self.nodes[child_id.0].height);	10✔
268	}	10✔
NEW 269	}	×
270	}
271	Type::User(UserType::Enum(_)) => {
272	// Enum: add variant fields as children
NEW 273	if let Ok(e) = peek.into_enum()	×
NEW 274	&& let Ok(variant) = e.active_variant()	×
275	{
NEW 276	let variant_path = path.with(PathSegment::Variant(variant.name));	×
NEW 277	for (i, (field, field_peek)) in e.fields().enumerate() {	×
NEW 278	let child_path = if variant.data.kind == StructKind::Struct {	×
NEW 279	variant_path.with(PathSegment::Field(field.name))	×
280	} else {
NEW 281	variant_path.with(PathSegment::Index(i))	×
282	};
NEW 283	let child_id = self.build_node(field_peek, Some(id), child_path);	×
NEW 284	children.push(child_id);	×
NEW 285	max_child_height = max_child_height.max(self.nodes[child_id.0].height);	×
286	}
NEW 287	}	×
288	}
289	_ => {
290	// Handle Def-based types
291	match peek.shape().def {	10✔
292	Def::List(_) \| Def::Array(_) \| Def::Slice(_) => {
NEW 293	if let Ok(list) = peek.into_list_like() {	×
NEW 294	for (i, elem) in list.iter().enumerate() {	×
NEW 295	let child_path = path.with(PathSegment::Index(i));	×
NEW 296	let child_id = self.build_node(elem, Some(id), child_path);	×
NEW 297	children.push(child_id);	×
NEW 298	max_child_height =	×
NEW 299	max_child_height.max(self.nodes[child_id.0].height);	×
NEW 300	}	×
NEW 301	}	×
302	}
303	Def::Map(_) => {
NEW 304	if let Ok(map) = peek.into_map() {	×
NEW 305	for (key, value) in map.iter() {	×
NEW 306	// Use the key's string representation	×
NEW 307	let key_str = format!("{:?}", key);	×
NEW 308	let child_path = path.with(PathSegment::Key(key_str));	×
NEW 309	let child_id = self.build_node(value, Some(id), child_path);	×
NEW 310	children.push(child_id);	×
NEW 311	max_child_height =	×
NEW 312	max_child_height.max(self.nodes[child_id.0].height);	×
NEW 313	}	×
NEW 314	}	×
315	}
316	Def::Option(_) => {
NEW 317	if let Ok(opt) = peek.into_option()	×
NEW 318	&& let Some(inner) = opt.value()	×
NEW 319	{	×
NEW 320	let child_id = self.build_node(inner, Some(id), path.clone());	×
NEW 321	children.push(child_id);	×
NEW 322	max_child_height = max_child_height.max(self.nodes[child_id.0].height);	×
NEW 323	}	×
324	}
325	_ => {	10✔
326	// Scalar or other leaf node - no children	10✔
327	}	10✔
328	}
329	}
330	}
331
332	// Compute hash using structural_hash from Peek
333	let mut hasher = DefaultHasher::new();	15✔
334	peek.structural_hash(&mut hasher);	15✔
335	let hash = hasher.finish();	15✔
336
337	// Update node with computed values
338	let node = &mut self.nodes[id.0];	15✔
339	node.children = children;	15✔
340	node.hash = hash;	15✔
341	node.height = if node.children.is_empty() {	15✔
342	0	10✔
343	} else {
344	max_child_height + 1	5✔
345	};
346
347	id	15✔
348	}	15✔
349	}
350
351	/// A mapping between nodes in two trees
352	#[derive(Debug, Default)]
353	pub struct Matching {
354	/// Map from tree A node to tree B node
355	a_to_b: HashMap<NodeId, NodeId>,
356	/// Map from tree B node to tree A node
357	b_to_a: HashMap<NodeId, NodeId>,
358	}
359
360	impl Matching {
361	/// Create a new empty matching
362	pub fn new() -> Self {	2✔
363	Self::default()	2✔
364	}	2✔
365
366	/// Add a match between two nodes
367	pub fn add(&mut self, a: NodeId, b: NodeId) {	4✔
368	self.a_to_b.insert(a, b);	4✔
369	self.b_to_a.insert(b, a);	4✔
370	}	4✔
371
372	/// Check if a node from tree A is matched
373	pub fn contains_a(&self, a: NodeId) -> bool {	17✔
374	self.a_to_b.contains_key(&a)	17✔
375	}	17✔
376
377	/// Check if a node from tree B is matched
378	pub fn contains_b(&self, b: NodeId) -> bool {	23✔
379	self.b_to_a.contains_key(&b)	23✔
380	}	23✔
381
382	/// Get the match for a node from tree A
383	pub fn get_b(&self, a: NodeId) -> Option<NodeId> {	4✔
384	self.a_to_b.get(&a).copied()	4✔
385	}	4✔
386
387	/// Get the match for a node from tree B
NEW 388	pub fn get_a(&self, b: NodeId) -> Option<NodeId> {	×
NEW 389	self.b_to_a.get(&b).copied()	×
NEW 390	}	×
391
392	/// Get all matched pairs
393	pub fn pairs(&self) -> impl Iterator<Item = (NodeId, NodeId)> + '_ {	2✔
394	self.a_to_b.iter().map(\|(&a, &b)\| (a, b))	4✔
395	}	2✔
396	}
397
398	/// Phase 1 & 2: Top-down matching based on hash equality
399	pub fn top_down_match(tree_a: &Tree, tree_b: &Tree) -> Matching {	2✔
400	let mut matching = Matching::new();	2✔
401
402	// Build hash -> nodes index for tree B
403	let mut b_by_hash: HashMap<u64, Vec<NodeId>> = HashMap::new();	2✔
404	for node in tree_b.nodes() {	6✔
405	b_by_hash.entry(node.hash).or_default().push(node.id);	6✔
406	}	6✔
407
408	// Priority queue: process higher nodes first (by height, descending)
409	let mut queue: Vec<(NodeId, NodeId)> = vec![(tree_a.root, tree_b.root)];	2✔
410
411	// Sort by height descending
412	queue.sort_by(\|a, b\| {	2✔
NEW 413	let ha = tree_a.get(a.0).height;	×
NEW 414	let hb = tree_a.get(b.0).height;	×
NEW 415	hb.cmp(&ha)	×
NEW 416	});	×
417
418	while let Some((a_id, b_id)) = queue.pop() {	7✔
419	let a_node = tree_a.get(a_id);	5✔
420	let b_node = tree_b.get(b_id);	5✔
421
422	// If already matched, skip
423	if matching.contains_a(a_id) \|\| matching.contains_b(b_id) {	5✔
424	continue;	1✔
425	}	4✔
426
427	// If hashes match, these subtrees are identical
428	if a_node.hash == b_node.hash {	4✔
429	// Match this node and all descendants	2✔
430	match_subtrees(tree_a, tree_b, a_id, b_id, &mut matching);	2✔
431	} else {	2✔
432	// Hashes differ - try to match children
433	for &a_child in &a_node.children {	2✔
434	let a_child_node = tree_a.get(a_child);	2✔
435
436	// Find candidates in B with matching hash
437	if let Some(b_candidates) = b_by_hash.get(&a_child_node.hash) {	2✔
438	for &b_candidate in b_candidates {	1✔
439	if !matching.contains_b(b_candidate) {	1✔
440	queue.push((a_child, b_candidate));	1✔
441	}	1✔
442	}
443	}	1✔
444
445	// Also try matching with children of b_id that have same kind
446	for &b_child in &b_node.children {	4✔
447	if !matching.contains_b(b_child) {	4✔
448	let b_child_node = tree_b.get(b_child);	4✔
449	if a_child_node.kind == b_child_node.kind {	4✔
450	queue.push((a_child, b_child));	2✔
451	}	2✔
NEW 452	}	×
453	}
454	}
455	}
456	}
457
458	matching	2✔
459	}	2✔
460
461	/// Match two subtrees recursively (when hashes match)
462	fn match_subtrees(	4✔
463	tree_a: &Tree,	4✔
464	tree_b: &Tree,	4✔
465	a_id: NodeId,	4✔
466	b_id: NodeId,	4✔
467	matching: &mut Matching,	4✔
468	) {	4✔
469	matching.add(a_id, b_id);	4✔
470
471	let a_node = tree_a.get(a_id);	4✔
472	let b_node = tree_b.get(b_id);	4✔
473
474	// Match children in order (they should be identical if hashes match)
475	for (a_child, b_child) in a_node.children.iter().zip(b_node.children.iter()) {	4✔
476	match_subtrees(tree_a, tree_b, a_child, b_child, matching);	2✔
477	}	2✔
478	}	4✔
479
480	/// Phase 3: Bottom-up matching for unmatched nodes
481	pub fn bottom_up_match(tree_a: &Tree, tree_b: &Tree, matching: &mut Matching) {	2✔
482	const SIMILARITY_THRESHOLD: f64 = 0.5;
483
484	// Build kind -> nodes index for tree B (unmatched only)
485	let mut b_by_kind: HashMap<NodeKind, Vec<NodeId>> = HashMap::new();	2✔
486	for node in tree_b.nodes() {	6✔
487	if !matching.contains_b(node.id) {	6✔
488	b_by_kind	2✔
489	.entry(node.kind.clone())	2✔
490	.or_default()	2✔
491	.push(node.id);	2✔
492	}	4✔
493	}
494
495	// Process tree A in post-order (children before parents)
496	for a_node in tree_a.post_order() {	6✔
497	if matching.contains_a(a_node.id) {	6✔
498	continue;	4✔
499	}	2✔
500
501	// Find candidates with same kind
502	let candidates = b_by_kind.get(&a_node.kind).cloned().unwrap_or_default();	2✔
503
504	// Score candidates by dice coefficient
505	let mut best: Option<(NodeId, f64)> = None;	2✔
506	for b_id in candidates {	2✔
507	if matching.contains_b(b_id) {	2✔
NEW 508	continue;	×
509	}	2✔
510
511	let score = dice_coefficient(tree_a, tree_b, a_node.id, b_id, matching);	2✔
512	if score >= SIMILARITY_THRESHOLD && (best.is_none() \|\| score > best.unwrap().1) {	2✔
NEW 513	best = Some((b_id, score));	×
514	}	2✔
515	}
516
517	if let Some((b_id, _)) = best {	2✔
NEW 518	matching.add(a_node.id, b_id);	×
519	}	2✔
520	}
521	}	2✔
522
523	/// Compute dice coefficient between two nodes based on matched descendants
524	fn dice_coefficient(	2✔
525	tree_a: &Tree,	2✔
526	tree_b: &Tree,	2✔
527	a_id: NodeId,	2✔
528	b_id: NodeId,	2✔
529	matching: &Matching,	2✔
530	) -> f64 {	2✔
531	let desc_a = tree_a.descendants(a_id);	2✔
532	let desc_b = tree_b.descendants(b_id);	2✔
533
534	let common = desc_a	2✔
535	.iter()	2✔
536	.filter(\|&&a\| {	4✔
537	matching	4✔
538	.get_b(a)	4✔
539	.map(\|b\| desc_b.contains(&b))	4✔
540	.unwrap_or(false)	4✔
541	})	4✔
542	.count();	2✔
543
544	if desc_a.is_empty() && desc_b.is_empty() {	2✔
NEW 545	1.0 // Both are leaves with no descendants	×
546	} else {
547	2.0 * common as f64 / (desc_a.len() + desc_b.len()) as f64	2✔
548	}
549	}	2✔
550
551	/// An edit operation in the diff
552	#[derive(Debug, Clone, PartialEq, Eq)]
553	#[non_exhaustive]
554	pub enum EditOp {
555	/// A value was updated (matched but content differs)
556	Update {
557	/// The path to the updated node
558	path: Path,
559	/// Hash of the old value
560	old_hash: u64,
561	/// Hash of the new value
562	new_hash: u64,
563	},
564	/// A node was inserted in tree B
565	Insert {
566	/// The path where the node was inserted
567	path: Path,
568	/// Hash of the inserted value
569	hash: u64,
570	},
571	/// A node was deleted from tree A
572	Delete {
573	/// The path where the node was deleted
574	path: Path,
575	/// Hash of the deleted value
576	hash: u64,
577	},
578	/// A node was moved from one location to another
579	Move {
580	/// The original path
581	old_path: Path,
582	/// The new path
583	new_path: Path,
584	/// Hash of the moved value
585	hash: u64,
586	},
587	}
588
589	/// Phase 4: Generate edit script from matching
590	pub fn generate_edit_script(tree_a: &Tree, tree_b: &Tree, matching: &Matching) -> Vec<EditOp> {	2✔
591	let mut ops = Vec::new();	2✔
592
593	// Deletions: nodes in A that are not matched
594	for a_node in tree_a.nodes() {	6✔
595	if !matching.contains_a(a_node.id) {	6✔
596	ops.push(EditOp::Delete {	2✔
597	path: a_node.path.clone(),	2✔
598	hash: a_node.hash,	2✔
599	});	2✔
600	}	4✔
601	}
602
603	// Insertions: nodes in B that are not matched
604	for b_node in tree_b.nodes() {	6✔
605	if !matching.contains_b(b_node.id) {	6✔
606	ops.push(EditOp::Insert {	2✔
607	path: b_node.path.clone(),	2✔
608	hash: b_node.hash,	2✔
609	});	2✔
610	}	4✔
611	}
612
613	// Updates and Moves: matched nodes where something changed
614	for (a_id, b_id) in matching.pairs() {	4✔
615	let a_node = tree_a.get(a_id);	4✔
616	let b_node = tree_b.get(b_id);	4✔
617
618	// Check if path changed (move)
619	if a_node.path != b_node.path {	4✔
NEW 620	ops.push(EditOp::Move {	×
NEW 621	old_path: a_node.path.clone(),	×
NEW 622	new_path: b_node.path.clone(),	×
NEW 623	hash: b_node.hash,	×
NEW 624	});	×
NEW 625	}	×
626	// Check if hash changed (update) - note: if subtrees matched by hash, they're identical
627	// But if matched by similarity, content may differ
628	else if a_node.hash != b_node.hash {	4✔
NEW 629	ops.push(EditOp::Update {	×
NEW 630	path: a_node.path.clone(),	×
NEW 631	old_hash: a_node.hash,	×
NEW 632	new_hash: b_node.hash,	×
NEW 633	});	×
634	}	4✔
635	}
636
637	ops	2✔
638	}	2✔
639
640	/// Compute the tree diff between two values
641	pub fn tree_diff<'a, 'f, A: facet_core::Facet<'f>, B: facet_core::Facet<'f>>(	2✔
642	a: &'a A,	2✔
643	b: &'a B,	2✔
644	) -> Vec<EditOp> {	2✔
645	let peek_a = Peek::new(a);	2✔
646	let peek_b = Peek::new(b);	2✔
647
648	let tree_a = TreeBuilder::build(peek_a);	2✔
649	let tree_b = TreeBuilder::build(peek_b);	2✔
650
651	let mut matching = top_down_match(&tree_a, &tree_b);	2✔
652	bottom_up_match(&tree_a, &tree_b, &mut matching);	2✔
653
654	generate_edit_script(&tree_a, &tree_b, &matching)	2✔
655	}	2✔
656
657	#[cfg(test)]
658	mod tests {
659	use super::*;
660	use facet::Facet;
661
662	#[derive(Debug, Clone, PartialEq, Facet)]
663	struct Person {
664	name: String,
665	age: u32,
666	}
667
668	#[test]
669	fn test_identical_trees() {	1✔
670	let a = Person {	1✔
671	name: "Alice".into(),	1✔
672	age: 30,	1✔
673	};	1✔
674	let b = a.clone();	1✔
675
676	let ops = tree_diff(&a, &b);	1✔
677	assert!(ops.is_empty(), "Identical trees should have no edits");	1✔
678	}	1✔
679
680	#[test]
681	fn test_simple_update() {	1✔
682	let a = Person {	1✔
683	name: "Alice".into(),	1✔
684	age: 30,	1✔
685	};	1✔
686	let b = Person {	1✔
687	name: "Alice".into(),	1✔
688	age: 31,	1✔
689	};	1✔
690
691	let ops = tree_diff(&a, &b);	1✔
692	// Should have some update operations
693	assert!(!ops.is_empty(), "Changed values should have edits");	1✔
694	}	1✔
695
696	#[test]
697	fn test_tree_building() {	1✔
698	let person = Person {	1✔
699	name: "Alice".into(),	1✔
700	age: 30,	1✔
701	};	1✔
702
703	let peek = Peek::new(&person);	1✔
704	let tree = TreeBuilder::build(peek);	1✔
705
706	// Should have root + 2 fields
707	assert!(tree.len() >= 3, "Tree should have root and field nodes");	1✔
708	}	1✔
709	}

facet-rs / facet / 20074615249

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous