Skip to main content

source_mesh_core/graph/
cycle_report.rs

1use std::fmt::Write as _;
2use std::num::NonZeroUsize;
3
4use anyhow::Context as _;
5use anyhow::Result;
6
7use super::markdown::inline_code;
8use crate::cycle_presentation::group_color;
9use crate::cycles::CycleAnalysis;
10use crate::model::FileNode;
11use crate::model::FolderNode;
12
13pub const NO_CYCLES_FOUND: &str = "No cycles found.";
14
15pub fn folder_report(analysis: &CycleAnalysis<FolderNode>, limit: NonZeroUsize) -> Result<String> {
16    Ok(format!(
17        "# Folder dependency cycles\n\n\
18        These cycles belong to the final folder graph, after root filtering and depth folding. \
19        Folder aggregation can introduce cycles even when the file graph is acyclic.\n\n{}",
20        render_cycles(analysis, limit, |node| Ok(node.label().as_str()))?
21    ))
22}
23
24pub fn file_report(analysis: &CycleAnalysis<FileNode>, limit: NonZeroUsize) -> Result<String> {
25    Ok(format!(
26        "# File dependency cycles\n\n\
27        These cycles belong to the file graph before folder aggregation; folder depth does not apply. \
28        Paths are relative to the indexed project, including their complete folder hierarchy.\n\n{}",
29        render_cycles(analysis, limit, |node| node.path().to_str().context("Cycle file path is not UTF-8"))?
30    ))
31}
32
33fn render_cycles<Node: Clone + Ord>(
34    analysis: &CycleAnalysis<Node>,
35    limit: NonZeroUsize,
36    label: impl Fn(&Node) -> Result<&str>,
37) -> Result<String> {
38    let listing = analysis.bounded_cycles(limit);
39    if listing.cycles().is_empty() {
40        return Ok(format!("{NO_CYCLES_FOUND}\n"));
41    }
42    let mut output = String::new();
43    if listing.truncated() {
44        write!(
45            output,
46            "> **Warning: cycle listing truncated at {} chains.** More cycles exist; \
47            the total cycle count was not computed. Complete cycle group count: {}.\n\n",
48            listing.cycles().len(),
49            analysis.group_count(),
50        ).unwrap_or_else(|_| unreachable!("Formatting a cycle warning into a String cannot fail"));
51    }
52    let mut previous_group = None;
53    for cycle in listing.cycles() {
54        let group = cycle.group();
55        if previous_group != Some(group) {
56            if previous_group.is_some() {
57                output.push('\n');
58            }
59            let color = group_color(group, analysis.group_count());
60            write!(output, "## C{} ({color})\n\n", group.number())
61                .unwrap_or_else(|_| unreachable!("Formatting a cycle heading into a String cannot fail"));
62            previous_group = Some(group);
63        }
64        output.push_str("- ");
65        for (index, node) in cycle.nodes().iter().enumerate() {
66            if index != 0 {
67                output.push_str(" -> ");
68            }
69            output.push_str(&inline_code(label(node)?));
70        }
71        output.push('\n');
72    }
73    Ok(output)
74}
75
76#[cfg(test)]
77mod tests {
78    use std::collections::BTreeMap;
79    use std::collections::BTreeSet;
80    use std::num::NonZeroUsize;
81    use std::path::Path;
82
83    use anyhow::Context as _;
84    use anyhow::Result;
85    use assertables::assert_contains;
86    use assertables::assert_not_contains;
87    use claims::assert_ok;
88    use claims::assert_some;
89    use nonzero_ext::nonzero;
90    use pretty_assertions::assert_eq;
91    use rstest::rstest;
92
93    use super::NO_CYCLES_FOUND;
94    use super::file_report;
95    use super::folder_report;
96    use crate::SourcePath;
97    use crate::cycle_presentation::group_color;
98    use crate::cycles::analyze_files;
99    use crate::cycles::analyze_folders;
100    use crate::model::DependencyCount;
101    use crate::model::DependencyKind;
102    use crate::model::FileEdge;
103    use crate::model::FileGraph;
104    use crate::model::FileNode;
105    use crate::model::FolderEdge;
106    use crate::model::FolderGraph;
107    use crate::model::FolderNode;
108
109    #[test]
110    fn test_cycle_group_diagram_colors() {
111        let nodes = BTreeSet::from([FolderNode::new("api".into()), FolderNode::new("storage".into())]);
112        let dependencies: BTreeMap<_, _> = nodes.iter().map(|node| {
113            let edge = FolderEdge::new(node.clone(), node.clone(), DependencyKind::Production);
114            (edge, DependencyCount::new(1))
115        }).collect();
116        let fixture = FolderGraph::new(nodes, dependencies);
117        let fixture = assert_ok!(fixture, "Independent self-loop folders must form a valid graph");
118        let analysis = analyze_folders(&fixture);
119        let analysis = assert_ok!(analysis, "Independent self-loop folders must support cycle analysis");
120        let system_under_test = folder_report;
121
122        let output = system_under_test(&analysis, NonZeroUsize::MAX);
123        let output = assert_ok!(output, "Cycle report must render independent self-loop groups");
124
125        let cycles = analysis.cycles(NonZeroUsize::MAX);
126        let cycles = assert_ok!(cycles, "Both independent self-loop cycles must be enumerable");
127        for cycle in cycles {
128            let group = cycle.group();
129            let color = group_color(group, analysis.group_count()).to_string();
130            let heading = format!("## C{} ({color})", group.number());
131            assert_contains!(output, &heading, "Cycle report color differs from the diagram palette");
132            assert!(color.starts_with('#') && color.len() == 7, "Cycle report color must use six-digit hexadecimal RGB");
133        }
134    }
135
136    enum ReportKind {
137        Folder,
138        File,
139    }
140
141    fn folder_fixture(dependencies: &[(&str, &str)]) -> Result<FolderGraph> {
142        let nodes = dependencies.iter().flat_map(|&(source, target)| {
143            [FolderNode::new(source.into()), FolderNode::new(target.into())]
144        }).collect();
145        let edges = dependencies.iter().map(|&(source, target)| {
146            let source = FolderNode::new(source.into());
147            let edge = FolderEdge::new(source, FolderNode::new(target.into()), DependencyKind::Production);
148            (edge, DependencyCount::new(1))
149        }).collect();
150        FolderGraph::new(nodes, edges)
151    }
152
153    fn file_fixture(dependencies: &[(&FileNode, &FileNode)]) -> Result<FileGraph> {
154        let nodes = dependencies.iter().flat_map(|&(source, target)| [source.clone(), target.clone()]).collect();
155        let edges = dependencies.iter().map(|&(source, target)| {
156            FileEdge::new(source.clone(), target.clone(), DependencyKind::Production)
157        }).collect();
158        FileGraph::new(nodes, edges)
159    }
160
161    fn overlapping_folder_fixture() -> Result<FolderGraph> {
162        folder_fixture(&[("api", "domain"), ("domain", "api"), ("domain", "storage"), ("storage", "api")])
163    }
164
165    fn report_chains(report: &str) -> Result<Vec<Vec<String>>> {
166        let cycle_lines = report.lines().filter(|line| line.starts_with("- "));
167        cycle_lines.map(|line| {
168            let cycle_markup = format!("<cycle>{line}</cycle>");
169            let cycle = roxmltree::Document::parse(&cycle_markup)?;
170            let nodes = cycle.descendants().filter(|node| node.has_tag_name("code"));
171            nodes.map(|node| Ok(node.text().context("Cycle node label is missing")?.to_owned())).collect()
172        }).collect()
173    }
174
175    fn assert_report_completeness(report: &str, group_count: usize, truncated: bool) {
176        if truncated {
177            let chain_count = report.lines().filter(|line| line.starts_with("- ")).count();
178            let warning = format!("Warning: cycle listing truncated at {chain_count} chains.");
179            assert_contains!(report, &warning, "Report is missing the truncation warning: {warning}");
180            assert_contains!(report, "More cycles exist", "Report is missing the notice that more cycles exist");
181            assert_contains!(report, "total cycle count was not computed", "Report omits the notice that no total was computed");
182            let group_summary = format!("Complete cycle group count: {group_count}.");
183            assert_contains!(report, &group_summary, "Report is missing the group summary: {group_summary}");
184        } else {
185            assert_not_contains!(report, "Warning:", "Complete report contains an unexpected warning");
186            assert_not_contains!(report, "truncated", "Complete report contains unexpected truncation text");
187        }
188    }
189
190    #[rstest]
191    #[case::self_loop(
192        &[("api", "api")],
193        "- <code>api</code> -> <code>api</code>",
194    )]
195    #[case::two_nodes(
196        &[("api", "domain"), ("domain", "api")],
197        "- <code>api</code> -> <code>domain</code> -> <code>api</code>",
198    )]
199    #[case::three_nodes(
200        &[("api", "domain"), ("domain", "storage"), ("storage", "api")],
201        "- <code>api</code> -> <code>domain</code> -> <code>storage</code> -> <code>api</code>",
202    )]
203    fn test_cycle_chain_separators(#[case] dependencies: &[(&str, &str)], #[case] expected: &str) {
204        let fixture = folder_fixture(dependencies);
205        let fixture = assert_ok!(fixture, "Cycle-chain dependencies must form a valid folder graph");
206        let analysis = analyze_folders(&fixture);
207        let analysis = assert_ok!(analysis, "Cycle-chain graph must support analysis");
208        let system_under_test = folder_report;
209
210        let output = system_under_test(&analysis, NonZeroUsize::MAX);
211        let output = assert_ok!(output, "Cycle-chain report must render every node and separator");
212        let chains: Vec<_> = output.lines().filter(|line| line.starts_with("- ")).collect();
213
214        assert_eq!(chains, vec![expected], "Arrows must separate every adjacent node, including the cycle closure");
215    }
216
217    #[test]
218    fn test_folder_closed_chains_on_separate_lines() {
219        let fixture = overlapping_folder_fixture();
220        let fixture = assert_ok!(fixture, "Overlapping folder cycles must form a valid graph");
221        let analysis = analyze_folders(&fixture);
222        let analysis = assert_ok!(analysis, "Overlapping folder cycles must support analysis");
223        let system_under_test = folder_report;
224
225        let output = system_under_test(&analysis, NonZeroUsize::MAX);
226        let output = assert_ok!(output, "Report must render every overlapping folder cycle");
227        let chains = report_chains(&output);
228        let chains = assert_ok!(chains, "Overlapping-cycle report must contain parseable node labels");
229
230        assert_eq!(
231            vec![
232                vec![String::from("api"), String::from("domain"), String::from("api")],
233                vec![String::from("api"), String::from("domain"), String::from("storage"), String::from("api")],
234            ],
235            chains,
236            "Report did not preserve both complete closed chains: {chains:?}"
237        );
238        assert_eq!(1, output.lines().filter(|line| line.starts_with("## ")).count(), "Connected cycles must share one group");
239    }
240
241    #[test]
242    fn test_cycle_group_sections() {
243        let fixture = folder_fixture(&[("api", "domain"), ("domain", "api"), ("queue", "storage"), ("storage", "queue")]);
244        let fixture = assert_ok!(fixture, "Two independent cycle groups must form a valid folder graph");
245        let analysis = analyze_folders(&fixture);
246        let analysis = assert_ok!(analysis, "Independent folder cycles must support analysis");
247        let system_under_test = folder_report;
248
249        let output = system_under_test(&analysis, NonZeroUsize::MAX);
250        let output = assert_ok!(output, "Report must render both independent cycle groups");
251        let sections = output.split_once("## C2 (");
252        let (first_section, last_section) = assert_some!(sections, "Report must contain a second cycle group");
253        let first_chains = report_chains(first_section);
254        let first_chains = assert_ok!(first_chains, "First cycle-group section must contain parseable labels");
255        let last_chains = report_chains(last_section);
256        let last_chains = assert_ok!(last_chains, "Second cycle-group section must contain parseable labels");
257
258        assert_contains!(first_section, "## C1 (", "First cycle group is missing");
259        let first_expected = vec![vec![String::from("api"), String::from("domain"), String::from("api")]];
260        assert_eq!(first_expected, first_chains, "First group contains incorrect chains");
261        let last_expected = vec![vec![String::from("queue"), String::from("storage"), String::from("queue")]];
262        assert_eq!(last_expected, last_chains, "Second group contains incorrect chains");
263    }
264
265    #[rstest]
266    #[case(
267        "unsafe`<>&\n\r\t",
268        "unsafe&#96;&lt;&gt;&amp;&#92;n&#92;r&#92;t",
269    )]
270    #[case(
271        "unsafe*[link]_\\~|",
272        "unsafe&#42;&#91;link&#93;&#95;&#92;&#126;&#124;",
273    )]
274    #[case(
275        "unsafe\n## injected\n<script>alert(1)</script>",
276        "unsafe&#92;n## injected&#92;n&lt;script&gt;alert(1)&lt;/script&gt;",
277    )]
278    fn test_folder_label_markdown_escaping(#[case] label: &str, #[case] escaped: &str) {
279        let fixture = folder_fixture(&[(label, "safe"), ("safe", label)]);
280        let fixture = assert_ok!(fixture, "Folder labels containing Markdown must be valid graph labels");
281        let analysis = analyze_folders(&fixture);
282        let analysis = assert_ok!(analysis, "Markdown in folder labels must not prevent cycle analysis");
283        let system_under_test = folder_report;
284
285        let output = system_under_test(&analysis, NonZeroUsize::MAX);
286        let output = assert_ok!(output, "Report must render escaped folder labels");
287        let chains = report_chains(&output);
288        let chains = assert_ok!(chains, "Escaped folder labels must remain parseable report markup");
289
290        assert_contains!(output, &format!("<code>{escaped}</code>"), "Folder label escaped incorrectly: {output}");
291        assert_eq!(1, chains.len(), "A label changed the number of cycle lines");
292        assert_eq!(1, output.lines().filter(|line| line.starts_with("## ")).count(), "A label injected a group heading");
293        assert_not_contains!(output, "<script>", "A label injected HTML markup");
294    }
295
296    #[rstest]
297    #[case::folder(ReportKind::Folder, NonZeroUsize::MIN)]
298    #[case::file(ReportKind::File, NonZeroUsize::MAX)]
299    fn test_empty_cycle_report(#[case] kind: ReportKind, #[case] limit: NonZeroUsize) {
300        let system_under_test = match kind {
301            ReportKind::Folder => {
302                let analysis = analyze_folders(&FolderGraph::default());
303                let analysis = assert_ok!(analysis, "Cycle analysis failed for the empty folder graph");
304                folder_report(&analysis, limit)
305            }
306            ReportKind::File => {
307                let analysis = FileGraph::new(BTreeSet::new(), BTreeSet::new()).and_then(|graph| analyze_files(&graph));
308                let analysis = assert_ok!(analysis, "Building and analyzing the empty file graph failed");
309                file_report(&analysis, limit)
310            }
311        };
312        let output = assert_ok!(system_under_test, "Cycle report generation failed for an empty graph");
313
314        assert_eq!(Some(NO_CYCLES_FOUND), output.lines().last(), "Empty report did not end with the no-cycles message");
315        let has_cycles = output.lines().any(|line| line.starts_with("- ") || line.starts_with("## "));
316        assert!(!has_cycles, "Empty report contains a cycle chain or group");
317        assert_report_completeness(&output, 0, false);
318    }
319
320    #[test]
321    fn test_file_cycle_complete_project_paths() {
322        let service_path = SourcePath::new(Path::new("src").join("api").join("deep").join("service.rs"));
323        let service_path = assert_ok!(service_path, "Nested service path must be a valid source path");
324        let service = FileNode::new(service_path);
325        let database_path = SourcePath::new(Path::new("src").join("storage").join("database.rs"));
326        let database_path = assert_ok!(database_path, "Database path must be a valid source path");
327        let database = FileNode::new(database_path);
328        let fixture = file_fixture(&[(&service, &database), (&database, &service)]);
329        let fixture = assert_ok!(fixture, "Service/database cycle must form a valid file graph");
330        let analysis = analyze_files(&fixture);
331        let analysis = assert_ok!(analysis, "Service/database graph must support cycle analysis");
332        let service_path_text = service.path().to_str();
333        let service_path_text = assert_some!(service_path_text, "Service fixture path must be UTF-8");
334        let database_path_text = database.path().to_str();
335        let database_path_text = assert_some!(database_path_text, "Database fixture path must be UTF-8");
336        let expected_chain = vec![service_path_text.to_owned(), database_path_text.to_owned(), service_path_text.to_owned()];
337        let system_under_test = file_report;
338
339        let output = system_under_test(&analysis, NonZeroUsize::MAX);
340        let output = assert_ok!(output, "File cycle report must render complete project-relative paths");
341        let chains = report_chains(&output);
342        let chains = assert_ok!(chains, "File cycle report must contain parseable paths");
343
344        assert_eq!(vec![expected_chain], chains, "File report changed project-relative source paths or omitted cycle closure");
345    }
346
347    #[test]
348    fn test_file_path_markdown_escaping() {
349        let service_path = SourcePath::new(Path::new("src").join("unsafe`<>&\n.rs"));
350        let service_path = assert_ok!(service_path, "Markdown characters must be allowed in a lexical source path");
351        let service = FileNode::new(service_path);
352        let database_path = SourcePath::new(Path::new("src").join("database.rs"));
353        let database_path = assert_ok!(database_path, "Database fixture path must be valid");
354        let database = FileNode::new(database_path);
355        let fixture = file_fixture(&[(&service, &database), (&database, &service)]);
356        let fixture = assert_ok!(fixture, "Files with Markdown characters must form a valid graph");
357        let analysis = analyze_files(&fixture);
358        let analysis = assert_ok!(analysis, "Markdown in file paths must not prevent cycle analysis");
359        let system_under_test = file_report;
360
361        let output = system_under_test(&analysis, NonZeroUsize::MAX);
362        let output = assert_ok!(output, "File report must render escaped Markdown characters");
363        let chains = report_chains(&output);
364        let chains = assert_ok!(chains, "Escaped file paths must remain parseable report markup");
365
366        assert_contains!(output, "unsafe&#96;&lt;&gt;&amp;&#92;n.rs</code>", "File path markup or newline was not escaped");
367        assert_eq!(1, chains.len(), "File path introduced another report line");
368    }
369
370    #[rstest]
371    #[case(None, vec![])]
372    #[case(Some(1), vec![vec!["api", "domain", "api"]])]
373    fn test_folder_aggregation_cycle_without_file_cycle(#[case] depth: Option<usize>, #[case] expected_chains: Vec<Vec<&str>>) {
374        let service_path = SourcePath::new(Path::new("src").join("api").join("service.rs"));
375        let service_path = assert_ok!(service_path, "Service fixture path must be valid");
376        let service = FileNode::new(service_path);
377        let request_path = SourcePath::new(Path::new("src").join("domain").join("deep").join("request.rs"));
378        let request_path = assert_ok!(request_path, "Nested request fixture path must be valid");
379        let request = FileNode::new(request_path);
380        let rules_path = SourcePath::new(Path::new("src").join("domain").join("rules.rs"));
381        let rules_path = assert_ok!(rules_path, "Rules fixture path must be valid");
382        let rules = FileNode::new(rules_path);
383        let response_path = SourcePath::new(Path::new("src").join("api").join("response.rs"));
384        let response_path = assert_ok!(response_path, "Response fixture path must be valid");
385        let response = FileNode::new(response_path);
386        let fixture = file_fixture(&[(&service, &request), (&rules, &response)]);
387        let fixture = assert_ok!(fixture, "Acyclic file dependencies must form a valid graph");
388        let folders = fixture.folders(Path::new("src"), depth, false);
389        let folders = assert_ok!(folders, "Folder aggregation must succeed at depth {depth:?}");
390        let folder_analysis = analyze_folders(&folders);
391        let folder_analysis = assert_ok!(folder_analysis, "Aggregated folders must support cycle analysis");
392        let file_analysis = analyze_files(&fixture);
393        let file_analysis = assert_ok!(file_analysis, "Original file graph must support cycle analysis");
394        let system_under_test = folder_report;
395
396        let folder_output = system_under_test(&folder_analysis, NonZeroUsize::MAX);
397        let folder_output = assert_ok!(folder_output, "Aggregated folder cycle report must render");
398        let file_output = file_report(&file_analysis, NonZeroUsize::MAX);
399        let file_output = assert_ok!(file_output, "Original file cycle report must render");
400        let folder_chains = report_chains(&folder_output);
401        let folder_chains = assert_ok!(folder_chains, "Aggregated folder report must contain parseable labels");
402        let expected_chains = expected_chains.into_iter().map(|chain| chain.into_iter().map(str::to_owned).collect());
403        let expected_chains: Vec<Vec<String>> = expected_chains.collect();
404
405        assert_eq!(expected_chains, folder_chains, "Folder report did not reflect the aggregation depth");
406        assert_eq!(Some(NO_CYCLES_FOUND), file_output.lines().last(), "File report inherited a folder-aggregation cycle");
407    }
408
409    #[rstest]
410    #[case::within_group(nonzero!(1_usize), true)]
411    #[case::group_boundary(nonzero!(2_usize), true)]
412    #[case::exact_limit(nonzero!(3_usize), false)]
413    #[case::below_limit(nonzero!(4_usize), false)]
414    fn test_cycle_report_listing_limit(
415        #[values(ReportKind::Folder, ReportKind::File)] kind: ReportKind,
416        #[case] limit: NonZeroUsize,
417        #[case] truncated: bool,
418    ) {
419        let system_under_test = match kind {
420            ReportKind::Folder => {
421                let analysis = folder_fixture(&[
422                    ("api", "domain"), ("domain", "api"), ("domain", "storage"), ("storage", "domain"), ("queue", "queue"),
423                ]).and_then(|graph| analyze_folders(&graph));
424                let analysis = assert_ok!(analysis, "Building and analyzing the folder report fixture failed");
425                folder_report(&analysis, limit)
426            }
427            ReportKind::File => {
428                let [api, domain, storage, queue] = ["api", "domain", "storage", "queue"].map(|name| {
429                    let file = SourcePath::new(name.into()).map(FileNode::new);
430                    assert_ok!(file, "Source path creation failed for the cycle-report fixture")
431                });
432                let analysis = file_fixture(&[
433                    (&api, &domain), (&domain, &api), (&domain, &storage), (&storage, &domain), (&queue, &queue),
434                ]).and_then(|graph| analyze_files(&graph));
435                let analysis = assert_ok!(analysis, "Building and analyzing the file report fixture failed");
436                file_report(&analysis, limit)
437            }
438        };
439        let output = assert_ok!(system_under_test, "Bounded cycle report generation failed");
440        let chains = report_chains(&output);
441        let chains = assert_ok!(chains, "Parsing cycle chains from the bounded report failed");
442        let expected: Vec<_> = [
443            vec!["api", "domain", "api"], vec!["domain", "storage", "domain"], vec!["queue", "queue"],
444        ].into_iter().take(limit.get()).collect();
445
446        assert_eq!(chains, expected, "Reported cycle chains differed from the expected bounded listing");
447        assert_report_completeness(&output, 2, truncated);
448        let groups = output.lines().filter(|line| line.starts_with("## ")).count();
449        assert_eq!(groups, if truncated { 1 } else { 2 }, "Cycle group section count differed from the expected value");
450    }
451
452    #[cfg(any(unix, windows))]
453    #[test]
454    fn test_file_path_encoding_error() {
455        use std::ffi::OsString;
456
457        #[cfg(unix)]
458        let file_name = {
459            use std::os::unix::ffi::OsStringExt as _;
460            OsString::from_vec(vec![0xff])
461        };
462        #[cfg(windows)]
463        let file_name = {
464            use std::os::windows::ffi::OsStringExt as _;
465            OsString::from_wide(&[0xd800])
466        };
467        let source_path = SourcePath::new(file_name.into());
468        let source_path = assert_ok!(source_path, "A non-UTF-8 filename must still be a valid lexical source path");
469        let file = FileNode::new(source_path);
470        let fixture = file_fixture(&[(&file, &file)]);
471        let fixture = assert_ok!(fixture, "A non-UTF-8 file self-loop must form a valid graph");
472        let analysis = analyze_files(&fixture);
473        let analysis = assert_ok!(analysis, "A non-UTF-8 file path must not prevent cycle analysis");
474        let system_under_test = file_report;
475
476        let result = system_under_test(&analysis, NonZeroUsize::MIN);
477
478        assert!(result.is_err(), "A non-UTF-8 cycle path must remain a report encoding error");
479    }
480}