1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
//! Style dependency ordering and circular-inheritance detection.
//!
//! Builds a topological ordering of styles based on their parent references and
//! detects circular inheritance via depth-first search before resolution.
use super::{AnalysisOptions, StyleAnalyzer};
use crate::{
analysis::styles::validation::{StyleConflict, StyleInheritance},
parser::Style,
};
use alloc::{collections::BTreeMap, collections::BTreeSet, vec::Vec};
impl<'a> StyleAnalyzer<'a> {
/// Build dependency order for styles using topological sort
/// Returns None if circular dependency is detected
pub(super) fn build_dependency_order(
&mut self,
styles: &'a [Style<'a>],
) -> Option<Vec<&'a Style<'a>>> {
// Create style map for quick lookup
let style_map: BTreeMap<&str, &Style> = styles.iter().map(|s| (s.name, s)).collect();
// Build adjacency list (child -> parent)
let mut dependencies: BTreeMap<&str, BTreeSet<&str>> = BTreeMap::new();
let mut in_degree: BTreeMap<&str, usize> = BTreeMap::new();
// Initialize all styles
for style in styles {
dependencies.insert(style.name, BTreeSet::new());
in_degree.insert(style.name, 0);
}
// Build dependency graph
for style in styles {
if let Some(parent_name) = style.parent {
if style_map.contains_key(parent_name) {
dependencies
.get_mut(style.name)
.unwrap()
.insert(parent_name);
*in_degree.get_mut(parent_name).unwrap() += 1;
// Track inheritance for analysis
if self.config.options.contains(AnalysisOptions::INHERITANCE) {
if let Some(inheritance) = self.inheritance_info.get_mut(style.name) {
inheritance.set_parent(parent_name);
} else {
let mut inheritance = StyleInheritance::new(style.name);
inheritance.set_parent(parent_name);
self.inheritance_info.insert(style.name, inheritance);
}
}
} else {
// Parent style not found - add warning conflict
self.conflicts
.push(StyleConflict::missing_parent(style.name, parent_name));
}
} else if self.config.options.contains(AnalysisOptions::INHERITANCE) {
// Style has no parent
self.inheritance_info
.insert(style.name, StyleInheritance::new(style.name));
}
}
// Check for circular dependencies using DFS
if Self::has_circular_dependency(&dependencies) {
self.conflicts.push(StyleConflict::circular_inheritance(
dependencies.keys().copied().collect(),
));
return None;
}
// Perform topological sort
let mut result = Vec::new();
let mut queue: Vec<&str> = Vec::new();
// Find all nodes with no dependencies
for (name, degree) in &in_degree {
if *degree == 0 {
queue.push(name);
}
}
while let Some(current) = queue.pop() {
if let Some(style) = style_map.get(current) {
result.push(*style);
}
// Update in-degrees
for (child, parents) in &dependencies {
if parents.contains(current) {
if let Some(degree) = in_degree.get_mut(child) {
*degree = degree.saturating_sub(1);
if *degree == 0 {
queue.push(child);
}
}
}
}
}
// Check if all styles were processed
if result.len() == styles.len() {
Some(result)
} else {
// Not all styles processed - circular dependency exists
None
}
}
/// Check for circular dependencies using DFS
fn has_circular_dependency(dependencies: &BTreeMap<&str, BTreeSet<&str>>) -> bool {
let mut visited = BTreeSet::new();
let mut rec_stack = BTreeSet::new();
for node in dependencies.keys() {
if !visited.contains(node)
&& Self::dfs_has_cycle(node, dependencies, &mut visited, &mut rec_stack)
{
return true;
}
}
false
}
/// DFS helper for cycle detection
fn dfs_has_cycle<'b>(
node: &'b str,
dependencies: &BTreeMap<&'b str, BTreeSet<&'b str>>,
visited: &mut BTreeSet<&'b str>,
rec_stack: &mut BTreeSet<&'b str>,
) -> bool {
visited.insert(node);
rec_stack.insert(node);
if let Some(neighbors) = dependencies.get(node) {
for neighbor in neighbors {
if !visited.contains(neighbor) {
if Self::dfs_has_cycle(neighbor, dependencies, visited, rec_stack) {
return true;
}
} else if rec_stack.contains(neighbor) {
return true;
}
}
}
rec_stack.remove(node);
false
}
}