Crate cinereus 

Cinereus

GumTree-style tree diffing with Chawathe edit script generation.

Named after Phascolarctos cinereus (the koala), which lives in gum trees.

Algorithm Overview

Cinereus implements a tree diff algorithm based on:

• GumTree (Falleri et al., ASE 2014) for node matching
• Chawathe algorithm (1996) for edit script generation

The algorithm works in phases:

1. Top-down matching: Match identical subtrees by hash (Merkle-tree style)
2. Bottom-up matching: Match remaining nodes by structural similarity (Dice coefficient)
3. Edit script generation: Produce INSERT, DELETE, UPDATE, MOVE operations
4. Simplification: Consolidate redundant operations (e.g., subtree moves)

Usage

use cinereus::{Tree, tree_diff};

// Build trees from your data structure
let tree_a = Tree::build(/* ... */);
let tree_b = Tree::build(/* ... */);

// Compute the diff
let edit_script = tree_diff(&tree_a, &tree_b);

for op in edit_script {
    println!("{:?}", op);
}

Re-exports

pub use indextree;

Structs

Matching

A bidirectional mapping between nodes in two trees.

MatchingConfig

Configuration for the matching algorithm.

NodeData

Data stored in each tree node.

Tree

A tree structure for diffing.

Enums

EditOp

An edit operation in the diff.

Functions

compute_matching

Compute the matching between two trees using the GumTree algorithm.

diff_trees

Compute a simplified diff between two trees.

generate_edit_script

Generate an edit script from a matching between two trees.

simplify_edit_script

Simplify an edit script by consolidating subtree operations.