cinereus/
lib.rs

1//! # Cinereus
2//!
3//! GumTree-style tree diffing with Chawathe edit script generation.
4//!
5//! Named after *Phascolarctos cinereus* (the koala), which lives in gum trees.
6//!
7//! ## Algorithm Overview
8//!
9//! Cinereus implements a tree diff algorithm based on:
10//! - **GumTree** (Falleri et al., ASE 2014) for node matching
11//! - **Chawathe algorithm** (1996) for edit script generation
12//!
13//! The algorithm works in phases:
14//!
15//! 1. **Top-down matching**: Match identical subtrees by hash (Merkle-tree style)
16//! 2. **Bottom-up matching**: Match remaining nodes by structural similarity (Dice coefficient)
17//! 3. **Edit script generation**: Produce INSERT, DELETE, UPDATE, MOVE operations
18//! 4. **Simplification**: Consolidate redundant operations (e.g., subtree moves)
19//!
20//! ## Usage
21//!
22//! ```ignore
23//! use cinereus::{Tree, tree_diff};
24//!
25//! // Build trees from your data structure
26//! let tree_a = Tree::build(/* ... */);
27//! let tree_b = Tree::build(/* ... */);
28//!
29//! // Compute the diff
30//! let edit_script = tree_diff(&tree_a, &tree_b);
31//!
32//! for op in edit_script {
33//!     println!("{:?}", op);
34//! }
35//! ```
36
37#![warn(missing_docs)]
38#![warn(clippy::std_instead_of_core)]
39
40pub use indextree;
41
42mod chawathe;
43mod matching;
44mod simplify;
45mod tree;
46
47pub use chawathe::*;
48pub use matching::*;
49pub use simplify::*;
50pub use tree::*;
51
52use core::hash::Hash;
53
54/// Compute a simplified diff between two trees.
55///
56/// This is the main entry point for tree diffing. It:
57/// 1. Computes a matching between nodes using GumTree's two-phase algorithm
58/// 2. Generates an edit script using Chawathe's algorithm
59/// 3. Simplifies the script to remove redundant operations
60///
61/// # Example
62///
63/// ```
64/// use cinereus::{Tree, NodeData, diff_trees, MatchingConfig};
65///
66/// let mut tree_a: Tree<&str, String> = Tree::new(NodeData::new(100, "root"));
67/// tree_a.add_child(tree_a.root, NodeData::leaf(1, "leaf", "hello".to_string()));
68///
69/// let mut tree_b: Tree<&str, String> = Tree::new(NodeData::new(100, "root"));
70/// tree_b.add_child(tree_b.root, NodeData::leaf(2, "leaf", "world".to_string()));
71///
72/// let ops = diff_trees(&tree_a, &tree_b, &MatchingConfig::default());
73/// // ops contains the edit operations to transform tree_a into tree_b
74/// ```
75pub fn diff_trees<K, L>(
76    tree_a: &Tree<K, L>,
77    tree_b: &Tree<K, L>,
78    config: &MatchingConfig,
79) -> Vec<EditOp<K, L>>
80where
81    K: Clone + Eq + Hash,
82    L: Clone + Eq,
83{
84    let matching = compute_matching(tree_a, tree_b, config);
85    let ops = generate_edit_script(tree_a, tree_b, &matching);
86    simplify_edit_script(ops, tree_a, tree_b)
87}
cinereus/lib.rs

cinereus/
lib.rs
