rez_lsp_server/resolver/
resolver_impl.rs

1//! Dependency resolver implementation.
2
3use async_trait::async_trait;
4use std::collections::{HashMap, HashSet};
5use tracing::{debug, info};
6
7use crate::core::{
8    ContextMetadata, DependencyResolver, Package, PlatformInfo, Requirement, ResolutionStats,
9    ResolvedContext, ResolverError, Result, Version, VersionConstraint,
10};
11
12/// Implementation of the dependency resolver.
13pub struct DependencyResolverImpl {
14    /// Available packages indexed by name
15    packages: HashMap<String, Vec<Package>>,
16    /// Resolution cache for performance
17    resolution_cache: HashMap<Vec<Requirement>, Option<ResolvedContext>>,
18}
19
20impl DependencyResolverImpl {
21    /// Create a new dependency resolver.
22    pub fn new() -> Self {
23        Self {
24            packages: HashMap::new(),
25            resolution_cache: HashMap::new(),
26        }
27    }
28
29    /// Set the available packages for resolution.
30    pub fn set_packages(&mut self, packages: HashMap<String, Vec<Package>>) {
31        self.packages = packages;
32        self.resolution_cache.clear(); // Clear cache when packages change
33    }
34
35    /// Find the best version of a package that satisfies the constraint.
36    fn find_best_version(&self, name: &str, constraint: &VersionConstraint) -> Option<&Package> {
37        let versions = self.packages.get(name)?;
38
39        // Filter versions that satisfy the constraint
40        let mut candidates: Vec<&Package> = versions
41            .iter()
42            .filter(|pkg| constraint.satisfies(&pkg.version))
43            .collect();
44
45        if candidates.is_empty() {
46            return None;
47        }
48
49        // Sort by version (highest first)
50        candidates.sort_by(|a, b| b.version.cmp(&a.version));
51
52        candidates.first().copied()
53    }
54
55    /// Check for conflicts between requirements.
56    fn check_conflicts(&self, requirements: &[Requirement]) -> Vec<String> {
57        let mut conflicts = Vec::new();
58        let mut package_constraints: HashMap<String, Vec<&Requirement>> = HashMap::new();
59
60        // Group requirements by package name
61        for req in requirements {
62            package_constraints
63                .entry(req.name.clone())
64                .or_default()
65                .push(req);
66        }
67
68        // Check for conflicts within each package
69        for (package_name, reqs) in package_constraints {
70            if reqs.len() > 1 {
71                // Check if all constraints can be satisfied simultaneously
72                if let Some(versions) = self.packages.get(&package_name) {
73                    let satisfying_versions: Vec<&Package> = versions
74                        .iter()
75                        .filter(|pkg| {
76                            reqs.iter().all(|req| {
77                                if req.conflict {
78                                    !req.constraint.satisfies(&pkg.version)
79                                } else {
80                                    req.constraint.satisfies(&pkg.version)
81                                }
82                            })
83                        })
84                        .collect();
85
86                    if satisfying_versions.is_empty() {
87                        conflicts.push(format!(
88                            "No version of '{}' satisfies all constraints: {}",
89                            package_name,
90                            reqs.iter()
91                                .map(|r| r.to_string())
92                                .collect::<Vec<_>>()
93                                .join(", ")
94                        ));
95                    }
96                }
97            }
98
99            // Check for explicit conflicts
100            for req in &reqs {
101                if req.conflict {
102                    // This is a conflict requirement - check if any version would be selected
103                    if let Some(best_version) =
104                        self.find_best_version(&req.name, &VersionConstraint::Any)
105                    {
106                        if req.constraint.satisfies(&best_version.version) {
107                            conflicts.push(format!(
108                                "Conflict: package '{}' version '{}' is explicitly forbidden",
109                                req.name, best_version.version
110                            ));
111                        }
112                    }
113                }
114            }
115        }
116
117        conflicts
118    }
119
120    /// Resolve dependencies recursively.
121    fn resolve_recursive(
122        &self,
123        requirements: &[Requirement],
124        resolved: &mut HashMap<String, Package>,
125        visited: &mut HashSet<String>,
126    ) -> Result<()> {
127        for req in requirements {
128            if req.conflict {
129                // Skip conflict requirements in resolution
130                continue;
131            }
132
133            if visited.contains(&req.name) {
134                // Circular dependency detection
135                return Err(ResolverError::CircularDependency(format!(
136                    "Circular dependency detected involving package '{}'",
137                    req.name
138                ))
139                .into());
140            }
141
142            if resolved.contains_key(&req.name) {
143                // Already resolved, check compatibility
144                let existing = &resolved[&req.name];
145                if !req.constraint.satisfies(&existing.version) {
146                    return Err(ResolverError::Conflict(format!(
147                        "Version conflict for package '{}': existing version '{}' does not satisfy constraint '{}'",
148                        req.name, existing.version, req.constraint
149                    )).into());
150                }
151                continue;
152            }
153
154            // Find the best version for this requirement
155            let package = self
156                .find_best_version(&req.name, &req.constraint)
157                .ok_or_else(|| {
158                    ResolverError::PackageNotFound(format!(
159                        "No version of package '{}' satisfies constraint '{}'",
160                        req.name, req.constraint
161                    ))
162                })?;
163
164            debug!("Resolved '{}' to version '{}'", req.name, package.version);
165
166            // Add to visited set to detect circular dependencies
167            visited.insert(req.name.clone());
168
169            // Recursively resolve dependencies of this package
170            self.resolve_recursive(&package.requires, resolved, visited)?;
171
172            // Remove from visited set
173            visited.remove(&req.name);
174
175            // Add to resolved packages
176            resolved.insert(req.name.clone(), package.clone());
177        }
178
179        Ok(())
180    }
181}
182
183impl Default for DependencyResolverImpl {
184    fn default() -> Self {
185        Self::new()
186    }
187}
188
189#[async_trait]
190impl DependencyResolver for DependencyResolverImpl {
191    async fn resolve(&self, requirements: &[Requirement]) -> Result<ResolvedContext> {
192        let start_time = std::time::Instant::now();
193        info!(
194            "Starting dependency resolution for {} requirements",
195            requirements.len()
196        );
197
198        // Check for obvious conflicts first
199        let conflicts = self.check_conflicts(requirements);
200        if !conflicts.is_empty() {
201            return Err(ResolverError::Conflict(conflicts.join("; ")).into());
202        }
203
204        let mut resolved = HashMap::new();
205        let mut visited = HashSet::new();
206
207        // Resolve all requirements
208        self.resolve_recursive(requirements, &mut resolved, &mut visited)?;
209
210        let resolution_time = start_time.elapsed();
211        let packages: Vec<Package> = resolved.into_values().collect();
212        let packages_count = packages.len();
213
214        info!(
215            "Dependency resolution completed: {} packages resolved in {:?}",
216            packages_count, resolution_time
217        );
218
219        Ok(ResolvedContext {
220            packages,
221            metadata: ContextMetadata {
222                timestamp: chrono::Utc::now(),
223                resolver_version: env!("CARGO_PKG_VERSION").to_string(),
224                platform: PlatformInfo {
225                    os: std::env::consts::OS.to_string(),
226                    arch: std::env::consts::ARCH.to_string(),
227                    platform: format!("{}-{}", std::env::consts::OS, std::env::consts::ARCH),
228                },
229                stats: ResolutionStats {
230                    packages_considered: self.packages.values().map(|v| v.len()).sum(),
231                    packages_resolved: packages_count,
232                    resolution_time_ms: resolution_time.as_millis() as u64,
233                    conflicts: conflicts.len(),
234                },
235            },
236        })
237    }
238
239    async fn can_resolve(&self, requirements: &[Requirement]) -> Result<bool> {
240        match self.resolve(requirements).await {
241            Ok(_) => Ok(true),
242            Err(_) => Ok(false),
243        }
244    }
245
246    async fn find_conflicts(
247        &self,
248        requirements: &[Requirement],
249    ) -> Result<Vec<crate::core::DependencyConflict>> {
250        let conflicts = self.check_conflicts(requirements);
251        Ok(conflicts
252            .into_iter()
253            .map(|description| crate::core::DependencyConflict {
254                package: "unknown".to_string(), // TODO: Extract package name from description
255                requirements: requirements.to_vec(),
256                description,
257            })
258            .collect())
259    }
260
261    async fn get_latest_version(
262        &self,
263        name: &str,
264        constraint: &VersionConstraint,
265    ) -> Result<Option<Version>> {
266        Ok(self
267            .find_best_version(name, constraint)
268            .map(|pkg| pkg.version.clone()))
269    }
270}
271
272#[cfg(test)]
273mod tests {
274    use super::*;
275    use crate::core::{Package, Requirement, Version, VersionConstraint};
276    use std::collections::HashMap;
277    use std::path::PathBuf;
278
279    fn create_test_package(name: &str, version: &str, requires: Vec<Requirement>) -> Package {
280        Package {
281            name: name.to_string(),
282            version: Version::new(version),
283            description: Some(format!("Test package {}", name)),
284            authors: vec!["Test Author".to_string()],
285            requires,
286            tools: vec![],
287            variants: vec![],
288            path: PathBuf::from("/test"),
289            metadata: HashMap::new(),
290        }
291    }
292
293    #[tokio::test]
294    async fn test_simple_resolution() {
295        let mut resolver = DependencyResolverImpl::new();
296
297        // Set up test packages
298        let mut packages = HashMap::new();
299        packages.insert(
300            "python".to_string(),
301            vec![create_test_package("python", "3.9.0", vec![])],
302        );
303
304        resolver.set_packages(packages);
305
306        // Test resolution
307        let requirements = vec![Requirement::new("python", VersionConstraint::Any)];
308        let result = resolver.resolve(&requirements).await;
309
310        assert!(result.is_ok());
311        let context = result.unwrap();
312        assert_eq!(context.packages.len(), 1);
313        assert_eq!(context.packages[0].name, "python");
314    }
315
316    #[tokio::test]
317    async fn test_version_constraint() {
318        let mut resolver = DependencyResolverImpl::new();
319
320        // Set up test packages with multiple versions
321        let mut packages = HashMap::new();
322        packages.insert(
323            "python".to_string(),
324            vec![
325                create_test_package("python", "3.7.0", vec![]),
326                create_test_package("python", "3.8.0", vec![]),
327                create_test_package("python", "3.9.0", vec![]),
328            ],
329        );
330
331        resolver.set_packages(packages);
332
333        // Test resolution with version constraint
334        let requirements = vec![Requirement::new(
335            "python",
336            VersionConstraint::GreaterEqual(Version::new("3.8")),
337        )];
338        let result = resolver.resolve(&requirements).await;
339
340        assert!(result.is_ok());
341        let context = result.unwrap();
342        assert_eq!(context.packages.len(), 1);
343        assert_eq!(context.packages[0].version, Version::new("3.9.0")); // Should pick the latest
344    }
345
346    #[tokio::test]
347    async fn test_conflict_detection() {
348        let mut resolver = DependencyResolverImpl::new();
349
350        // Set up test packages
351        let mut packages = HashMap::new();
352        packages.insert(
353            "python".to_string(),
354            vec![create_test_package("python", "3.9.0", vec![])],
355        );
356
357        resolver.set_packages(packages);
358
359        // Test conflicting requirements
360        let requirements = vec![
361            Requirement::new("python", VersionConstraint::Exact(Version::new("3.9.0"))),
362            Requirement::new("python", VersionConstraint::Exact(Version::new("3.8.0"))),
363        ];
364
365        let result = resolver.resolve(&requirements).await;
366        assert!(result.is_err());
367    }
368}
rez_lsp_server/resolver/resolver_impl.rs

rez_lsp_server/resolver/
resolver_impl.rs
