memscope_rs/analysis/relation_inference/
graph_builder.rs

1//! Graph Builder — main pipeline for relation inference.
2//!
3//! Orchestrates HeapScanner, UTI Engine, and all relation detectors
4//! to produce a complete `RelationGraph` from active allocations.
5
6use crate::analysis::heap_scanner::HeapScanner;
7use crate::analysis::relation_inference::clone_detector::{detect_clones, CloneConfig};
8use crate::analysis::relation_inference::pointer_scan::{detect_owner, InferenceRecord};
9use crate::analysis::relation_inference::shared_detector::detect_shared;
10use crate::analysis::relation_inference::slice_detector::detect_slice;
11use crate::analysis::relation_inference::{RangeMap, RelationGraph};
12use crate::analysis::unsafe_inference::{
13    MemoryView, OwnedMemoryView, TypeKind, UnsafeInferenceEngine,
14};
15use crate::snapshot::types::ActiveAllocation;
16
17/// Configuration for the relation graph builder.
18///
19/// This struct controls the behavior of the relation inference pipeline,
20/// allowing fine-tuning of detection thresholds and parameters.
21///
22/// # Example
23///
24/// ```ignore
25/// use memscope_rs::analysis::relation_inference::{
26///     GraphBuilderConfig, CloneConfig,
27/// };
28///
29/// // Default configuration
30/// let config = GraphBuilderConfig::default();
31///
32/// // Custom configuration for stricter clone detection
33/// let config = GraphBuilderConfig {
34///     clone_config: CloneConfig {
35///         min_similarity: 0.95,  // Require 95% content match
36///         max_time_diff_ns: 5_000_000,  // 5ms window
37///         ..Default::default()
38///     },
39/// };
40///
41/// let graph = RelationGraphBuilder::build(&allocations, Some(config));
42/// ```
43///
44/// # Fields
45///
46/// * `clone_config` - Controls clone detection behavior. See [`CloneConfig`]
47///   for details on similarity thresholds and time windows.
48#[derive(Debug, Clone, Default)]
49pub struct GraphBuilderConfig {
50    /// Configuration for clone detection.
51    ///
52    /// Controls how the system identifies cloned allocations based on:
53    /// - Content similarity ratio (`min_similarity`)
54    /// - Maximum time difference between allocations (`max_time_diff_ns`)
55    /// - Number of bytes to compare (`compare_bytes`)
56    ///
57    /// Default values are tuned for typical Rust workloads:
58    /// - 80% similarity threshold
59    /// - 10ms time window
60    /// - 64 bytes comparison
61    pub clone_config: CloneConfig,
62}
63
64/// Builds a relation graph from active allocations.
65///
66/// # Pipeline
67///
68/// ```text
69/// ActiveAllocation[]
70///     │
71///     ▼
72/// HeapScanner → ScanResult[]
73///     │
74///     ▼
75/// UTI Engine → InferenceRecord[]
76///     │
77///     ▼
78/// RangeMap + Owner/Slice/Clone detectors
79///     │
80///     ▼
81/// RelationGraph
82/// ```
83pub struct RelationGraphBuilder;
84
85impl RelationGraphBuilder {
86    /// Build a relation graph from a list of active allocations.
87    ///
88    /// # Arguments
89    ///
90    /// * `allocations` - List of active allocations from a snapshot.
91    /// * `config` - Builder configuration (optional, uses defaults if None).
92    ///
93    /// # Returns
94    ///
95    /// A `RelationGraph` containing all inferred relationships.
96    pub fn build(
97        allocations: &[ActiveAllocation],
98        config: Option<GraphBuilderConfig>,
99    ) -> RelationGraph {
100        let config = config.unwrap_or_default();
101
102        if allocations.is_empty() {
103            return RelationGraph::new();
104        }
105
106        // Step 1: Scan heap memory for all allocations.
107        let scan_results = HeapScanner::scan(allocations);
108
109        // Step 2: Run UTI Engine on each allocation.
110        let records: Vec<InferenceRecord> = scan_results
111            .into_iter()
112            .enumerate()
113            .map(|(id, scan)| {
114                let (type_kind, confidence) = if let Some(ref memory) = scan.memory {
115                    let view = MemoryView::new(memory);
116                    let guess = UnsafeInferenceEngine::infer_single(&view, scan.size);
117                    (guess.kind, guess.confidence)
118                } else {
119                    (TypeKind::Unknown, 0)
120                };
121
122                InferenceRecord {
123                    id,
124                    ptr: scan.ptr,
125                    size: scan.size,
126                    memory: scan.memory.map(OwnedMemoryView::new),
127                    type_kind,
128                    confidence,
129                    call_stack_hash: allocations[id].call_stack_hash,
130                    alloc_time: allocations[id].allocated_at,
131                }
132            })
133            .collect();
134
135        // Step 3: Build RangeMap for address → allocation lookup.
136        let range_map = RangeMap::new(allocations);
137
138        // Step 4: Run relation detectors.
139        let mut graph = RelationGraph::new();
140
141        // Owner detection: scan each allocation's memory for pointers.
142        for record in &records {
143            let edges = detect_owner(record, &range_map);
144            graph.add_edges(edges);
145        }
146
147        // Slice detection: check if each allocation points into another's interior.
148        let slice_edges = detect_slice(&records, allocations, &range_map);
149        graph.add_edges(slice_edges);
150
151        // Clone detection: batch comparison by (type, size, stack_hash).
152        let clone_edges = detect_clones(&records, &config.clone_config);
153        graph.add_edges(clone_edges);
154
155        // Shared detection: find Arc/Rc shared ownership via Owner graph analysis.
156        let shared_edges = detect_shared(&records, &graph.edges);
157        graph.add_edges(shared_edges);
158
159        graph
160    }
161}
162
163#[cfg(test)]
164mod tests {
165    use super::*;
166    use crate::analysis::relation_inference::Relation;
167
168    fn make_alloc(ptr: usize, size: usize) -> ActiveAllocation {
169        ActiveAllocation {
170            ptr,
171            size,
172            allocated_at: 1000,
173            var_name: None,
174            type_name: None,
175            thread_id: 0,
176            call_stack_hash: None,
177        }
178    }
179
180    #[test]
181    fn test_build_empty() {
182        let graph = RelationGraphBuilder::build(&[], None);
183        assert_eq!(graph.edge_count(), 0);
184    }
185
186    #[test]
187    fn test_build_basic_owner_relationship() {
188        // Use real heap allocations via Vec to ensure addresses are valid.
189        let buf1 = [0u8; 24];
190        let buf2 = vec![0u8; 1024];
191        let ptr1 = buf1.as_ptr() as usize;
192        let ptr2 = buf2.as_ptr() as usize;
193
194        let allocs = vec![make_alloc(ptr1, 24), make_alloc(ptr2, 1024)];
195        let graph = RelationGraphBuilder::build(&allocs, None);
196
197        // Graph should be built without panicking.
198        // The content is all zeros so no Owner relationships will be found.
199        assert_eq!(graph.edge_count(), 0);
200    }
201
202    #[test]
203    fn test_build_with_real_vec_metadata() {
204        // Create a real Vec-like metadata pattern: [ptr, len, cap]
205        let inner = vec![42u8; 256];
206        let ptr = inner.as_ptr() as usize;
207        let len = inner.len();
208        let cap = inner.capacity();
209
210        let mut metadata = [0u8; 24];
211        metadata[0..8].copy_from_slice(&ptr.to_le_bytes());
212        metadata[8..16].copy_from_slice(&len.to_le_bytes());
213        metadata[16..24].copy_from_slice(&cap.to_le_bytes());
214
215        let meta_ptr = metadata.as_ptr() as usize;
216        let inner_ptr = inner.as_ptr() as usize;
217
218        let allocs = vec![make_alloc(meta_ptr, 24), make_alloc(inner_ptr, 256)];
219        let graph = RelationGraphBuilder::build(&allocs, None);
220
221        // Should not crash. Actual edge depends on whether metadata is readable
222        // at meta_ptr (it's on the heap, so should be).
223        assert!(graph.edge_count() <= 2);
224    }
225
226    #[test]
227    fn test_build_single_allocation() {
228        let allocs = vec![make_alloc(0x1000, 64)];
229        let graph = RelationGraphBuilder::build(&allocs, None);
230
231        // Single allocation should not produce any relationships.
232        assert_eq!(graph.edge_count(), 0);
233    }
234
235    #[test]
236    fn test_builder_with_default_config() {
237        let allocs = vec![make_alloc(0x1000, 64)];
238        let graph = RelationGraphBuilder::build(&allocs, Some(GraphBuilderConfig::default()));
239        assert_eq!(graph.edge_count(), 0);
240    }
241
242    #[test]
243    fn test_graph_node_count() {
244        let mut graph = RelationGraph::new();
245        graph.add_edge(0, 1, Relation::Owner);
246        graph.add_edge(1, 2, Relation::Slice);
247
248        let nodes = graph.all_nodes();
249        assert_eq!(nodes, vec![0, 1, 2]);
250    }
251}
memscope_rs/analysis/relation_inference/graph_builder.rs

memscope_rs/analysis/relation_inference/
graph_builder.rs
