compi 0.5.0

A build system written in Rust.
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
153
154

use std::collections::{HashMap, HashSet, VecDeque, hash_map::Entry::Occupied};

use super::Task;
use crate::error::{CompiError, Result};

pub fn sort_topologically(tasks: &[Task]) -> Vec<String> {
    let mut in_degrees: HashMap<&str, usize> = HashMap::new();

    for task in tasks {
        in_degrees.insert(&task.id, task.dependencies.len());
    }

    let mut queue: VecDeque<&str> = VecDeque::new();
    for (task_id, &in_degree) in &in_degrees {
        if in_degree == 0 {
            queue.push_back(task_id);
        }
    }

    let mut sorted_tasks: Vec<String> = Vec::new();

    while let Some(task_id) = queue.pop_front() {
        sorted_tasks.push(task_id.to_string());

        for dependent in tasks {
            if !dependent.dependencies.iter().any(|dep| dep == task_id) {
                continue;
            }

            let entry = in_degrees.entry(&dependent.id).and_modify(|c| *c -= 1);

            if let Occupied(entry) = entry {
                if *entry.get() == 0 {
                    queue.push_back(&dependent.id);
                }
            }
        }
    }

    sorted_tasks
}

pub fn validate_tasks(tasks: &[Task]) -> Result<()> {
    let task_ids: HashSet<&str> = tasks.iter().map(|t| t.id.as_str()).collect();

    for task in tasks {
        for dep_id in &task.dependencies {
            if dep_id == &task.id {
                return Err(CompiError::Dependency(format!(
                    "Task '{}' depends on itself",
                    task.id
                )));
            }
            if !task_ids.contains(dep_id.as_str()) {
                return Err(CompiError::Dependency(format!(
                    "Task '{}' depends on '{}' which doesn't exist",
                    task.id, dep_id
                )));
            }
        }
    }

    detect_cycles(tasks)?;
    Ok(())
}

pub fn get_required_tasks(tasks: &[Task], target_task_id: &str) -> Result<Vec<String>> {
    let task_map: HashMap<&str, &Task> = tasks.iter().map(|t| (t.id.as_str(), t)).collect();

    if !task_map.contains_key(target_task_id) {
        return Err(CompiError::Task(format!(
            "Task '{}' not found",
            target_task_id
        )));
    }

    let mut needed_tasks = HashSet::new();
    let mut queue = VecDeque::new();

    queue.push_back(target_task_id);

    while let Some(current_task_id) = queue.pop_front() {
        if needed_tasks.contains(current_task_id) {
            continue;
        }

        needed_tasks.insert(current_task_id);

        if let Some(task) = task_map.get(current_task_id) {
            for dep in &task.dependencies {
                if !needed_tasks.contains(dep.as_str()) {
                    queue.push_back(dep);
                }
            }
        }
    }

    let filtered_tasks: Vec<Task> = tasks
        .iter()
        .filter(|task| needed_tasks.contains(task.id.as_str()))
        .cloned()
        .collect();

    Ok(sort_topologically(&filtered_tasks))
}

fn detect_cycles(tasks: &[Task]) -> Result<()> {
    let task_map: HashMap<&str, &Task> = tasks.iter().map(|t| (t.id.as_str(), t)).collect();

    for task in tasks {
        let mut visited = HashSet::new();
        let mut path = Vec::new();

        if has_cycle(&task.id, &task_map, &mut visited, &mut path) {
            path.push(task.id.clone());
            return Err(CompiError::Dependency(format!(
                "Circular dependency: {}",
                path.join(" -> ")
            )));
        }
    }

    Ok(())
}

fn has_cycle(
    task_id: &str,
    task_map: &HashMap<&str, &Task>,
    visited: &mut HashSet<String>,
    path: &mut Vec<String>,
) -> bool {
    if path.iter().any(|id| id == task_id) {
        return true;
    }

    if visited.contains(task_id) {
        return false;
    }

    visited.insert(task_id.to_string());
    path.push(task_id.to_string());

    if let Some(task) = task_map.get(task_id) {
        for dep in &task.dependencies {
            if has_cycle(dep, task_map, visited, path) {
                return true;
            }
        }
    }

    path.pop();

    false
}