wowlab_engine_domain/rotation/validate/
dependency_graph.rs

1use wowlab_types::sim::FastMap;
2
3use super::{Action, Condition, MAX_EXPANDED_ACTIONS, Rotation};
4
5fn condition_variable_names(root: &Condition) -> Vec<&str> {
6    let mut names = Vec::new();
7
8    root.walk(&mut |condition| {
9        if let Condition::Var { name } = condition {
10            names.push(name.as_str());
11        }
12    });
13
14    names
15}
16
17pub(super) fn variable_dependency_graph(
18    variables: &FastMap<String, Condition>,
19) -> FastMap<&str, Vec<&str>> {
20    variables
21        .iter()
22        .map(|(name, condition)| {
23            (
24                name.as_str(),
25                condition_variable_names(condition)
26                    .into_iter()
27                    .filter(|dependency| variables.contains_key(*dependency))
28                    .collect(),
29            )
30        })
31        .collect()
32}
33
34pub(super) fn action_list_dependency_graph(
35    lists: &FastMap<String, Vec<Action>>,
36) -> FastMap<&str, Vec<&str>> {
37    lists
38        .iter()
39        .map(|(name, actions)| {
40            let dependencies = actions
41                .iter()
42                .filter(|action| action.enabled())
43                .filter_map(|action| match action {
44                    Action::Call { list, .. } | Action::Run { list, .. }
45                        if lists.contains_key(list) =>
46                    {
47                        Some(list.as_str())
48                    }
49                    _ => None,
50                })
51                .collect();
52
53            (name.as_str(), dependencies)
54        })
55        .collect()
56}
57
58/// Returns dependencies before consumers, or the first directed cycle.
59pub(super) fn dependency_postorder<'a>(
60    graph: &FastMap<&'a str, Vec<&'a str>>,
61) -> Result<Vec<&'a str>, Vec<String>> {
62    const VISITING: u8 = 1;
63    const COMPLETE: u8 = 2;
64
65    let mut states: FastMap<&str, u8> = FastMap::default();
66    let mut postorder = Vec::with_capacity(graph.len());
67    let mut path = Vec::with_capacity(graph.len());
68    let mut stack = Vec::with_capacity(graph.len());
69
70    for start in graph.keys().copied() {
71        if states.contains_key(start) {
72            continue;
73        }
74
75        states.insert(start, VISITING);
76        path.clear();
77        path.push(start);
78        stack.clear();
79        stack.push((start, 0_usize));
80
81        while let Some(&(node, next_index)) = stack.last() {
82            let next = graph
83                .get(node)
84                .and_then(|dependencies| dependencies.get(next_index))
85                .copied();
86            let Some(dependency) = next else {
87                stack.pop();
88                path.pop();
89                states.insert(node, COMPLETE);
90                postorder.push(node);
91                continue;
92            };
93
94            if let Some(frame) = stack.last_mut() {
95                frame.1 += 1;
96            }
97
98            match states.get(dependency).copied() {
99                Some(VISITING) => return Err(dependency_cycle(&path, dependency)),
100                Some(COMPLETE) => {}
101                None => {
102                    states.insert(dependency, VISITING);
103                    path.push(dependency);
104                    stack.push((dependency, 0));
105                }
106                Some(_) => unreachable!("dependency state is an internal two-value enum"),
107            }
108        }
109    }
110
111    Ok(postorder)
112}
113
114fn dependency_cycle(path: &[&str], dependency: &str) -> Vec<String> {
115    let mut cycle: Vec<String> = path
116        .iter()
117        .copied()
118        .skip_while(|candidate| *candidate != dependency)
119        .map(str::to_owned)
120        .collect();
121
122    cycle.push(dependency.to_owned());
123
124    cycle
125}
126
127fn expanded_action_count(actions: &[Action], list_costs: &FastMap<&str, usize>) -> usize {
128    let overflow = MAX_EXPANDED_ACTIONS + 1;
129    let mut total = 0_usize;
130
131    for action in actions {
132        total = total.saturating_add(1).min(overflow);
133
134        if !action.enabled() {
135            continue;
136        }
137
138        if let Action::Call { list, .. } | Action::Run { list, .. } = action {
139            total = total
140                .saturating_add(list_costs.get(list.as_str()).copied().unwrap_or_default())
141                .min(overflow);
142        }
143    }
144
145    total
146}
147
148pub(super) fn expanded_rotation_action_count(rotation: &Rotation, postorder: &[&str]) -> usize {
149    let mut list_costs = FastMap::default();
150
151    for &name in postorder {
152        let Some(actions) = rotation.lists.get(name) else {
153            continue;
154        };
155
156        list_costs.insert(name, expanded_action_count(actions, &list_costs));
157    }
158
159    expanded_action_count(&rotation.actions, &list_costs)
160}
wowlab_engine_domain/rotation/validate/dependency_graph.rs

wowlab_engine_domain/rotation/validate/
dependency_graph.rs
