layer_conform_core/
tsed.rs

1//! TSED — Type Structure Edit Distance score.
2//!
3//! Normalizes APTED distance to a 0..1 similarity:
4//!   score = max(0.0, 1.0 - distance / `max(size_a`, `size_b`))
5
6use crate::apted::{edit_distance, AptedOptions};
7use crate::tree::TreeNode;
8
9pub fn tsed(a: &TreeNode, b: &TreeNode) -> f64 {
10    tsed_with(a, b, AptedOptions::default())
11}
12
13pub fn tsed_with(a: &TreeNode, b: &TreeNode, opts: AptedOptions) -> f64 {
14    let max_size = u32::max(a.subtree_size, b.subtree_size);
15    if max_size == 0 {
16        return 1.0;
17    }
18    let d = edit_distance(a, b, opts);
19    let score = 1.0 - d / f64::from(max_size);
20    score.max(0.0).min(1.0)
21}
22
23#[cfg(test)]
24mod tests {
25    use super::*;
26    use crate::tree::{NodeKind, TreeNode};
27
28    fn finalized(mut t: TreeNode) -> TreeNode {
29        t.finalize();
30        t
31    }
32
33    #[test]
34    fn identical_trees_score_one() {
35        let a = finalized(TreeNode::branch(
36            NodeKind::Block,
37            vec![TreeNode::leaf(NodeKind::Identifier, Some("x".into()))],
38        ));
39        let b = finalized(TreeNode::branch(
40            NodeKind::Block,
41            vec![TreeNode::leaf(NodeKind::Identifier, Some("x".into()))],
42        ));
43        assert!((tsed(&a, &b) - 1.0).abs() < 1e-9);
44    }
45
46    #[test]
47    fn fully_different_trees_score_low() {
48        let a = finalized(TreeNode::leaf(NodeKind::Identifier, Some("x".into())));
49        let b = finalized(TreeNode::leaf(NodeKind::Literal, Some("y".into())));
50        let s = tsed(&a, &b);
51        assert!(s <= 0.01, "expected near 0, got {s}");
52    }
53
54    #[test]
55    fn partial_overlap_is_in_between() {
56        let a = finalized(TreeNode::branch(
57            NodeKind::Block,
58            vec![
59                TreeNode::leaf(NodeKind::Identifier, Some("x".into())),
60                TreeNode::leaf(NodeKind::Identifier, Some("y".into())),
61            ],
62        ));
63        let b = finalized(TreeNode::branch(
64            NodeKind::Block,
65            vec![TreeNode::leaf(NodeKind::Identifier, Some("x".into()))],
66        ));
67        let s = tsed(&a, &b);
68        assert!(s > 0.6 && s < 0.7, "expected ~0.667, got {s}");
69    }
70}
layer_conform_core/tsed.rs

layer_conform_core/
tsed.rs
