• Home
  • Features
  • Pricing
  • Docs
  • Announcements
  • Sign In

facet-rs / facet / 20109439374

10 Dec 2025 06:37PM UTC coverage: 57.724% (-0.8%) from 58.573%
20109439374

push

github

fasterthanlime
fix: resolve clippy and cargo doc lints

- Fix assign_op_pattern lint in theme.rs: use *= instead of manual assignment
- Fix broken-intra-doc-link in diff.rs: escape square brackets in doc comment

1 of 1 new or added line in 1 file covered. (100.0%)

852 existing lines in 5 files now uncovered.

28569 of 49492 relevant lines covered (57.72%)

808.57 hits per line

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

74.75
/facet-diff/src/tree.rs
1
//! Tree diffing for Facet types using the cinereus algorithm.
2
//!
3
//! This module provides the bridge between facet-reflect's `Peek` and
4
//! cinereus's tree diffing algorithm.
5

6
use core::hash::Hasher;
7
use std::borrow::Cow;
8
use std::hash::DefaultHasher;
9

10
use cinereus::{EditOp as CinereusEditOp, MatchingConfig, NodeData, Tree, diff_trees};
11
use facet_core::{Def, StructKind, Type, UserType};
12
use facet_diff_core::{Path, PathSegment};
13
use facet_reflect::{HasFields, Peek};
14

15
/// The kind of a node in the tree (for type-based matching).
16
#[derive(Debug, Clone, PartialEq, Eq, Hash)]
17
pub enum NodeKind {
18
    /// A struct with the given type name
19
    Struct(&'static str),
20
    /// An enum variant
21
    EnumVariant(&'static str, &'static str), // (enum_name, variant_name)
22
    /// A list/array/slice
23
    List(&'static str),
24
    /// A map
25
    Map(&'static str),
26
    /// An option
27
    Option(&'static str),
28
    /// A scalar value
29
    Scalar(&'static str),
30
}
31

32
/// Label for a node (the actual value for leaves).
33
#[derive(Debug, Clone, PartialEq, Eq)]
34
pub struct NodeLabel {
35
    /// The path to this node from the root.
36
    pub path: Path,
37
}
38

39
/// An edit operation in the diff.
40
#[derive(Debug, Clone, PartialEq, Eq)]
41
#[non_exhaustive]
42
pub enum EditOp {
43
    /// A value was updated (matched but content differs).
44
    Update {
45
        /// The path to the updated node
46
        path: Path,
47
        /// Hash of the old value
48
        old_hash: u64,
49
        /// Hash of the new value
50
        new_hash: u64,
51
    },
52
    /// A node was inserted in tree B.
53
    Insert {
54
        /// The path where the node was inserted
55
        path: Path,
56
        /// Hash of the inserted value
57
        hash: u64,
58
    },
59
    /// A node was deleted from tree A.
60
    Delete {
61
        /// The path where the node was deleted
62
        path: Path,
63
        /// Hash of the deleted value
64
        hash: u64,
65
    },
66
    /// A node was moved from one location to another.
67
    Move {
68
        /// The original path
69
        old_path: Path,
70
        /// The new path
71
        new_path: Path,
72
        /// Hash of the moved value
73
        hash: u64,
74
    },
75
}
76

77
/// A tree built from a Peek value, ready for diffing.
78
pub type FacetTree = Tree<NodeKind, NodeLabel>;
79

80
/// Build a cinereus tree from a Peek value.
81
pub fn build_tree<'mem, 'facet>(peek: Peek<'mem, 'facet>) -> FacetTree {
5✔
82
    let mut builder = TreeBuilder::new();
5✔
83
    let root_id = builder.build_node(peek, Path::new());
5✔
84
    Tree {
5✔
85
        arena: builder.arena,
5✔
86
        root: root_id,
5✔
87
    }
5✔
88
}
5✔
89

90
struct TreeBuilder {
91
    arena: cinereus::indextree::Arena<NodeData<NodeKind, NodeLabel>>,
92
}
93

94
impl TreeBuilder {
95
    fn new() -> Self {
5✔
96
        Self {
5✔
97
            arena: cinereus::indextree::Arena::new(),
5✔
98
        }
5✔
99
    }
5✔
100

101
    fn build_node<'mem, 'facet>(
15✔
102
        &mut self,
15✔
103
        peek: Peek<'mem, 'facet>,
15✔
104
        path: Path,
15✔
105
    ) -> cinereus::indextree::NodeId {
15✔
106
        // Compute structural hash
107
        let mut hasher = DefaultHasher::new();
15✔
108
        peek.structural_hash(&mut hasher);
15✔
109
        let hash = hasher.finish();
15✔
110

111
        // Determine the node kind
112
        let kind = self.determine_kind(peek);
15✔
113

114
        // Create node data
115
        let data = NodeData {
15✔
116
            hash,
15✔
117
            kind,
15✔
118
            label: Some(NodeLabel { path: path.clone() }),
15✔
119
        };
15✔
120

121
        // Create the node
122
        let node_id = self.arena.new_node(data);
15✔
123

124
        // Build children based on type
125
        self.build_children(peek, node_id, path);
15✔
126

127
        node_id
15✔
128
    }
15✔
129

130
    fn determine_kind<'mem, 'facet>(&self, peek: Peek<'mem, 'facet>) -> NodeKind {
15✔
131
        match peek.shape().ty {
15✔
132
            Type::User(UserType::Struct(_)) => NodeKind::Struct(peek.shape().type_identifier),
5✔
133
            Type::User(UserType::Enum(_)) => {
UNCOV
134
                if let Ok(e) = peek.into_enum()
×
UNCOV
135
                    && let Ok(variant) = e.active_variant()
×
136
                {
UNCOV
137
                    return NodeKind::EnumVariant(peek.shape().type_identifier, variant.name);
×
UNCOV
138
                }
×
UNCOV
139
                NodeKind::Scalar(peek.shape().type_identifier)
×
140
            }
141
            _ => match peek.shape().def {
10✔
142
                Def::List(_) | Def::Array(_) | Def::Slice(_) => {
UNCOV
143
                    NodeKind::List(peek.shape().type_identifier)
×
144
                }
UNCOV
145
                Def::Map(_) => NodeKind::Map(peek.shape().type_identifier),
×
UNCOV
146
                Def::Option(_) => NodeKind::Option(peek.shape().type_identifier),
×
147
                _ => NodeKind::Scalar(peek.shape().type_identifier),
10✔
148
            },
149
        }
150
    }
15✔
151

152
    fn build_children<'mem, 'facet>(
15✔
153
        &mut self,
15✔
154
        peek: Peek<'mem, 'facet>,
15✔
155
        parent_id: cinereus::indextree::NodeId,
15✔
156
        path: Path,
15✔
157
    ) {
15✔
158
        match peek.shape().ty {
15✔
159
            Type::User(UserType::Struct(_)) => {
160
                if let Ok(s) = peek.into_struct() {
5✔
161
                    for (field, field_peek) in s.fields() {
10✔
162
                        // Skip metadata fields
163
                        if field.is_metadata() {
10✔
UNCOV
164
                            continue;
×
165
                        }
10✔
166
                        let child_path = path.with(PathSegment::Field(Cow::Borrowed(field.name)));
10✔
167
                        let child_id = self.build_node(field_peek, child_path);
10✔
168
                        parent_id.append(child_id, &mut self.arena);
10✔
169
                    }
UNCOV
170
                }
×
171
            }
172
            Type::User(UserType::Enum(_)) => {
UNCOV
173
                if let Ok(e) = peek.into_enum()
×
UNCOV
174
                    && let Ok(variant) = e.active_variant()
×
175
                {
UNCOV
176
                    let variant_path = path.with(PathSegment::Variant(Cow::Borrowed(variant.name)));
×
UNCOV
177
                    for (i, (field, field_peek)) in e.fields().enumerate() {
×
UNCOV
178
                        let child_path = if variant.data.kind == StructKind::Struct {
×
UNCOV
179
                            variant_path.with(PathSegment::Field(Cow::Borrowed(field.name)))
×
180
                        } else {
UNCOV
181
                            variant_path.with(PathSegment::Index(i))
×
182
                        };
UNCOV
183
                        let child_id = self.build_node(field_peek, child_path);
×
UNCOV
184
                        parent_id.append(child_id, &mut self.arena);
×
185
                    }
186
                }
×
187
            }
188
            _ => {
189
                match peek.shape().def {
10✔
190
                    Def::List(_) | Def::Array(_) | Def::Slice(_) => {
UNCOV
191
                        if let Ok(list) = peek.into_list_like() {
×
UNCOV
192
                            for (i, elem) in list.iter().enumerate() {
×
UNCOV
193
                                let child_path = path.with(PathSegment::Index(i));
×
194
                                let child_id = self.build_node(elem, child_path);
×
UNCOV
195
                                parent_id.append(child_id, &mut self.arena);
×
196
                            }
×
197
                        }
×
198
                    }
199
                    Def::Map(_) => {
UNCOV
200
                        if let Ok(map) = peek.into_map() {
×
UNCOV
201
                            for (key, value) in map.iter() {
×
UNCOV
202
                                let key_str = format!("{:?}", key);
×
UNCOV
203
                                let child_path = path.with(PathSegment::Key(Cow::Owned(key_str)));
×
UNCOV
204
                                let child_id = self.build_node(value, child_path);
×
UNCOV
205
                                parent_id.append(child_id, &mut self.arena);
×
UNCOV
206
                            }
×
UNCOV
207
                        }
×
208
                    }
209
                    Def::Option(_) => {
UNCOV
210
                        if let Ok(opt) = peek.into_option()
×
UNCOV
211
                            && let Some(inner) = opt.value()
×
UNCOV
212
                        {
×
UNCOV
213
                            // For options, the child keeps the same path
×
UNCOV
214
                            let child_id = self.build_node(inner, path);
×
215
                            parent_id.append(child_id, &mut self.arena);
×
UNCOV
216
                        }
×
217
                    }
218
                    _ => {
10✔
219
                        // Scalar/leaf node - no children
10✔
220
                    }
10✔
221
                }
222
            }
223
        }
224
    }
15✔
225
}
226

227
/// Compute the tree diff between two Facet values.
228
pub fn tree_diff<'a, 'f, A: facet_core::Facet<'f>, B: facet_core::Facet<'f>>(
2✔
229
    a: &'a A,
2✔
230
    b: &'a B,
2✔
231
) -> Vec<EditOp> {
2✔
232
    let peek_a = Peek::new(a);
2✔
233
    let peek_b = Peek::new(b);
2✔
234

235
    let tree_a = build_tree(peek_a);
2✔
236
    let tree_b = build_tree(peek_b);
2✔
237

238
    let config = MatchingConfig::default();
2✔
239
    let cinereus_ops = diff_trees(&tree_a, &tree_b, &config);
2✔
240

241
    // Convert cinereus ops to our EditOp format, filtering out no-op moves
242
    cinereus_ops
2✔
243
        .into_iter()
2✔
244
        .map(|op| convert_op(op, &tree_a, &tree_b))
3✔
245
        .filter(|op| {
3✔
246
            // Filter out MOVE operations where old and new paths are the same
247
            // (these are no-ops from the user's perspective)
248
            if let EditOp::Move {
249
                old_path, new_path, ..
1✔
250
            } = op
3✔
251
            {
252
                old_path != new_path
1✔
253
            } else {
254
                true
2✔
255
            }
256
        })
3✔
257
        .collect()
2✔
258
}
2✔
259

260
fn convert_op(
3✔
261
    op: CinereusEditOp<NodeKind, NodeLabel>,
3✔
262
    tree_a: &FacetTree,
3✔
263
    tree_b: &FacetTree,
3✔
264
) -> EditOp {
3✔
265
    match op {
3✔
266
        CinereusEditOp::Update {
267
            node_a,
×
UNCOV
268
            node_b,
×
UNCOV
269
            old_label,
×
270
            new_label: _,
271
        } => {
UNCOV
272
            let path = old_label.map(|l| l.path).unwrap_or_else(Path::new);
×
UNCOV
273
            EditOp::Update {
×
UNCOV
274
                path,
×
UNCOV
275
                old_hash: tree_a.get(node_a).hash,
×
UNCOV
276
                new_hash: tree_b.get(node_b).hash,
×
UNCOV
277
            }
×
278
        }
279
        CinereusEditOp::Insert { node_b, label, .. } => {
1✔
280
            let path = label.map(|l| l.path).unwrap_or_else(Path::new);
1✔
281
            EditOp::Insert {
1✔
282
                path,
1✔
283
                hash: tree_b.get(node_b).hash,
1✔
284
            }
1✔
285
        }
286
        CinereusEditOp::Delete { node_a } => {
1✔
287
            let data = tree_a.get(node_a);
1✔
288
            let path = data
1✔
289
                .label
1✔
290
                .as_ref()
1✔
291
                .map(|l| l.path.clone())
1✔
292
                .unwrap_or_default();
1✔
293
            EditOp::Delete {
1✔
294
                path,
1✔
295
                hash: data.hash,
1✔
296
            }
1✔
297
        }
298
        CinereusEditOp::Move { node_a, node_b, .. } => {
1✔
299
            let old_path = tree_a
1✔
300
                .get(node_a)
1✔
301
                .label
1✔
302
                .as_ref()
1✔
303
                .map(|l| l.path.clone())
1✔
304
                .unwrap_or_default();
1✔
305
            let new_path = tree_b
1✔
306
                .get(node_b)
1✔
307
                .label
1✔
308
                .as_ref()
1✔
309
                .map(|l| l.path.clone())
1✔
310
                .unwrap_or_default();
1✔
311
            EditOp::Move {
1✔
312
                old_path,
1✔
313
                new_path,
1✔
314
                hash: tree_b.get(node_b).hash,
1✔
315
            }
1✔
316
        }
317
    }
318
}
3✔
319

320
#[cfg(test)]
321
mod tests {
322
    use super::*;
323
    use facet::Facet;
324

325
    #[derive(Debug, Clone, PartialEq, Facet)]
326
    struct Person {
327
        name: String,
328
        age: u32,
329
    }
330

331
    #[test]
332
    fn test_identical_trees() {
1✔
333
        let a = Person {
1✔
334
            name: "Alice".into(),
1✔
335
            age: 30,
1✔
336
        };
1✔
337
        let b = a.clone();
1✔
338

339
        let ops = tree_diff(&a, &b);
1✔
340
        assert!(ops.is_empty(), "Identical trees should have no edits");
1✔
341
    }
1✔
342

343
    #[test]
344
    fn test_simple_update() {
1✔
345
        let a = Person {
1✔
346
            name: "Alice".into(),
1✔
347
            age: 30,
1✔
348
        };
1✔
349
        let b = Person {
1✔
350
            name: "Alice".into(),
1✔
351
            age: 31,
1✔
352
        };
1✔
353

354
        let ops = tree_diff(&a, &b);
1✔
355
        assert!(!ops.is_empty(), "Changed values should have edits");
1✔
356
    }
1✔
357

358
    #[test]
359
    fn test_tree_building() {
1✔
360
        let person = Person {
1✔
361
            name: "Alice".into(),
1✔
362
            age: 30,
1✔
363
        };
1✔
364

365
        let peek = Peek::new(&person);
1✔
366
        let tree = build_tree(peek);
1✔
367

368
        // Should have root + 2 fields (at minimum)
369
        let node_count = tree.arena.count();
1✔
370
        assert!(
1✔
371
            node_count >= 3,
1✔
372
            "Tree should have root and field nodes, got {}",
373
            node_count
374
        );
375
    }
1✔
376
}
STATUS · Troubleshooting · Open an Issue · Sales · Support · CAREERS · ENTERPRISE · START FREE · SCHEDULE DEMO
ANNOUNCEMENTS · TWITTER · TOS & SLA · Supported CI Services · What's a CI service? · Automated Testing

© 2026 Coveralls, Inc