waxpkg 0.15.9

Fast Homebrew-compatible package manager
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

use crate::api::Formula;
use crate::error::{Result, WaxError};
use std::collections::{HashMap, HashSet, VecDeque};
use tracing::{debug, instrument};

pub fn find_installed_reverse_dependencies(
    package_name: &str,
    formulae: &[Formula],
    installed: &HashSet<String>,
) -> Vec<String> {
    let mut reverse_deps = Vec::new();
    for formula in formulae {
        if !installed.contains(&formula.name) {
            continue;
        }
        if let Some(deps) = &formula.dependencies {
            if deps.iter().any(|d| d == package_name) {
                reverse_deps.push(formula.name.clone());
            }
        }
    }
    reverse_deps.sort();
    reverse_deps
}

#[derive(Debug, Clone)]
pub struct DependencyGraph {
    nodes: HashMap<String, Vec<String>>,
}

impl DependencyGraph {
    pub fn new() -> Self {
        Self {
            nodes: HashMap::new(),
        }
    }

    pub fn add_node(&mut self, name: String, deps: Vec<String>) {
        self.nodes.insert(name, deps);
    }

    #[instrument(skip(self))]
    pub fn topological_sort(&self) -> Result<Vec<String>> {
        debug!("Performing topological sort on dependency graph");

        let mut in_degree: HashMap<String, usize> = HashMap::new();
        let mut adj_list: HashMap<String, Vec<String>> = HashMap::new();

        for (node, deps) in &self.nodes {
            in_degree.entry(node.clone()).or_insert(0);

            for dep in deps {
                in_degree.entry(dep.clone()).or_insert(0);
                adj_list.entry(dep.clone()).or_default().push(node.clone());
            }
        }

        for (node, deps) in &self.nodes {
            let count = deps.len();
            *in_degree.entry(node.clone()).or_insert(0) = count;
        }

        let mut queue: VecDeque<String> = in_degree
            .iter()
            .filter(|(_, &count)| count == 0)
            .map(|(node, _)| node.clone())
            .collect();

        let mut result = Vec::new();

        while let Some(node) = queue.pop_front() {
            result.push(node.clone());

            if let Some(neighbors) = adj_list.get(&node) {
                for neighbor in neighbors {
                    if let Some(count) = in_degree.get_mut(neighbor) {
                        *count -= 1;
                        if *count == 0 {
                            queue.push_back(neighbor.clone());
                        }
                    }
                }
            }
        }

        if result.len() != in_degree.len() {
            return Err(WaxError::DependencyCycle(
                "Circular dependency detected".to_string(),
            ));
        }

        debug!("Topological sort result: {:?}", result);
        Ok(result)
    }
}

impl Default for DependencyGraph {
    fn default() -> Self {
        Self::new()
    }
}

#[instrument(skip(formulae))]
pub fn resolve_dependencies(
    formula: &Formula,
    formulae: &[Formula],
    installed: &HashSet<String>,
) -> Result<Vec<String>> {
    debug!("Resolving dependencies for {}", formula.name);

    let mut graph = DependencyGraph::new();
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();

    queue.push_back(formula.name.clone());

    while let Some(name) = queue.pop_front() {
        if visited.contains(&name) || installed.contains(&name) {
            continue;
        }
        visited.insert(name.clone());

        let f = formulae
            .iter()
            .find(|f| f.name == name)
            .ok_or_else(|| WaxError::FormulaNotFound(name.clone()))?;

        let deps = f.dependencies.clone().unwrap_or_default();

        graph.add_node(name.clone(), deps.clone());

        for dep in deps {
            if !installed.contains(&dep) {
                queue.push_back(dep);
            }
        }
    }

    let sorted = graph.topological_sort()?;

    let to_install: Vec<String> = sorted
        .into_iter()
        .filter(|name| !installed.contains(name))
        .collect();

    debug!("Packages to install: {:?}", to_install);
    Ok(to_install)
}