veridian_kernel/pkg/
resolver.rs

1//! Dependency Resolution
2//!
3//! Implements SAT-based dependency resolution for package management.
4//! Uses a DPLL solver with unit propagation, pure literal elimination,
5//! and backtracking for conflict resolution.
6
7use alloc::{
8    collections::{BTreeMap, BTreeSet},
9    format,
10    string::String,
11    vec,
12    vec::Vec,
13};
14
15use super::{Dependency, PackageId, PackageMetadata, Version};
16
17// ============================================================================
18// Resolver Error Type
19// ============================================================================
20
21/// Errors from dependency resolution
22#[derive(Debug, Clone, PartialEq, Eq)]
23pub enum ResolverError {
24    /// Package not found in any repository
25    PackageNotFound { name: String },
26    /// No version satisfies the given requirement
27    NoSatisfyingVersion {
28        package: String,
29        requirement: String,
30    },
31    /// Version conflict between requirements
32    VersionConflict {
33        package: String,
34        required: String,
35        existing: String,
36    },
37    /// Missing metadata for a package version
38    MissingMetadata { package: String, version: String },
39    /// No satisfying assignment found by SAT solver
40    Unsatisfiable,
41    /// Two packages conflict with each other
42    Conflict {
43        package: String,
44        conflicting: String,
45    },
46    /// No provider for a virtual package
47    NoProvider { virtual_package: String },
48}
49
50impl core::fmt::Display for ResolverError {
51    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
52        match self {
53            Self::PackageNotFound { name } => write!(f, "Package not found: {}", name),
54            Self::NoSatisfyingVersion {
55                package,
56                requirement,
57            } => {
58                write!(
59                    f,
60                    "No suitable version found for {} (requirement: {})",
61                    package, requirement
62                )
63            }
64            Self::VersionConflict {
65                package,
66                required,
67                existing,
68            } => {
69                write!(
70                    f,
71                    "Version conflict for {}: need {}, have {}",
72                    package, required, existing
73                )
74            }
75            Self::MissingMetadata { package, version } => {
76                write!(f, "Missing metadata for {} {}", package, version)
77            }
78            Self::Unsatisfiable => {
79                write!(f, "No satisfying assignment found for dependencies")
80            }
81            Self::Conflict {
82                package,
83                conflicting,
84            } => {
85                write!(f, "Conflict: {} conflicts with {}", package, conflicting)
86            }
87            Self::NoProvider { virtual_package } => {
88                write!(f, "No provider for virtual package: {}", virtual_package)
89            }
90        }
91    }
92}
93
94// ============================================================================
95// Version Requirement
96// ============================================================================
97
98/// Version requirement supporting exact, range, caret, and tilde expressions
99#[derive(Debug, Clone, PartialEq, Eq)]
100pub enum VersionReq {
101    /// Exact version
102    Exact(Version),
103    /// Minimum version (>=)
104    AtLeast(Version),
105    /// Maximum version (<=)
106    AtMost(Version),
107    /// Range (>= min, < max)
108    Range(Version, Version),
109    /// Caret range: ^1.2.3 means >=1.2.3, <2.0.0
110    Caret(Version),
111    /// Tilde range: ~1.2.3 means >=1.2.3, <1.3.0
112    Tilde(Version),
113    /// Any version
114    Any,
115    /// Compound requirement: all sub-requirements must be satisfied
116    Compound(Vec<VersionReq>),
117}
118
119impl VersionReq {
120    /// Parse version requirement from string.
121    ///
122    /// Supports:
123    /// - `*` or empty: any version
124    /// - `1.2.3`: exact version
125    /// - `>=1.2.3`: minimum version
126    /// - `<=1.2.3`: maximum version
127    /// - `^1.2.3`: compatible with (same major for major > 0)
128    /// - `~1.2.3`: approximately (same major.minor)
129    /// - `>=1.2.0, <2.0.0`: compound range (comma-separated)
130    pub fn parse(s: &str) -> Self {
131        let trimmed = s.trim();
132        if trimmed == "*" || trimmed.is_empty() {
133            return VersionReq::Any;
134        }
135
136        // Check for compound expressions (comma-separated)
137        if trimmed.contains(',') {
138            let parts: Vec<VersionReq> = trimmed
139                .split(',')
140                .map(|part| Self::parse_single(part.trim()))
141                .collect();
142            if parts.len() == 1 {
143                return parts.into_iter().next().unwrap_or(VersionReq::Any);
144            }
145            return VersionReq::Compound(parts);
146        }
147
148        Self::parse_single(trimmed)
149    }
150
151    /// Parse a single (non-compound) version requirement
152    fn parse_single(s: &str) -> Self {
153        let trimmed = s.trim();
154
155        if let Some(rest) = trimmed.strip_prefix('^') {
156            if let Some(v) = Self::parse_version_flexible(rest) {
157                return VersionReq::Caret(v);
158            }
159        }
160
161        if let Some(rest) = trimmed.strip_prefix('~') {
162            if let Some(v) = Self::parse_version_flexible(rest) {
163                return VersionReq::Tilde(v);
164            }
165        }
166
167        if let Some(rest) = trimmed.strip_prefix(">=") {
168            if let Some(v) = Self::parse_version(rest) {
169                return VersionReq::AtLeast(v);
170            }
171        }
172
173        if let Some(rest) = trimmed.strip_prefix("<=") {
174            if let Some(v) = Self::parse_version(rest) {
175                return VersionReq::AtMost(v);
176            }
177        }
178
179        if let Some(rest) = trimmed.strip_prefix('<') {
180            // Strict less-than: convert to range 0.0.0..<version
181            if let Some(v) = Self::parse_version(rest) {
182                return VersionReq::Range(Version::new(0, 0, 0), v);
183            }
184        }
185
186        if let Some(rest) = trimmed.strip_prefix('>') {
187            // Strict greater-than: >=next_patch
188            if let Some(v) = Self::parse_version(rest) {
189                let next = Version::new(v.major, v.minor, v.patch + 1);
190                return VersionReq::AtLeast(next);
191            }
192        }
193
194        if let Some(v) = Self::parse_version(trimmed) {
195            return VersionReq::Exact(v);
196        }
197
198        VersionReq::Any
199    }
200
201    /// Parse version from string (major.minor.patch)
202    fn parse_version(s: &str) -> Option<Version> {
203        let parts: Vec<&str> = s.trim().split('.').collect();
204        if parts.len() != 3 {
205            return None;
206        }
207
208        let major = parts[0].parse().ok()?;
209        let minor = parts[1].parse().ok()?;
210        let patch = parts[2].parse().ok()?;
211
212        Some(Version::new(major, minor, patch))
213    }
214
215    /// Parse version flexibly: `1` -> `1.0.0`, `1.2` -> `1.2.0`, `1.2.3` ->
216    /// `1.2.3`
217    fn parse_version_flexible(s: &str) -> Option<Version> {
218        let parts: Vec<&str> = s.trim().split('.').collect();
219        if parts.is_empty() || parts.len() > 3 {
220            return None;
221        }
222
223        let major: u32 = parts[0].parse().ok()?;
224        let minor: u32 = parts.get(1).and_then(|p| p.parse().ok()).unwrap_or(0);
225        let patch: u32 = parts.get(2).and_then(|p| p.parse().ok()).unwrap_or(0);
226
227        Some(Version::new(major, minor, patch))
228    }
229
230    /// Check if version satisfies this requirement
231    pub fn satisfies(&self, version: &Version) -> bool {
232        match self {
233            VersionReq::Exact(v) => version == v,
234            VersionReq::AtLeast(v) => version >= v,
235            VersionReq::AtMost(v) => version <= v,
236            VersionReq::Range(min, max) => version >= min && version < max,
237            VersionReq::Caret(v) => satisfies_caret(version, v),
238            VersionReq::Tilde(v) => satisfies_tilde(version, v),
239            VersionReq::Any => true,
240            VersionReq::Compound(reqs) => reqs.iter().all(|r| r.satisfies(version)),
241        }
242    }
243}
244
245/// Check if `version` satisfies caret requirement `^base`.
246///
247/// - `^1.2.3` means `>=1.2.3, <2.0.0` (major > 0)
248/// - `^0.2.3` means `>=0.2.3, <0.3.0` (major == 0, minor > 0)
249/// - `^0.0.3` means `>=0.0.3, <0.0.4` (major == 0, minor == 0)
250fn satisfies_caret(version: &Version, base: &Version) -> bool {
251    if version < base {
252        return false;
253    }
254    if base.major > 0 {
255        version.major == base.major
256    } else if base.minor > 0 {
257        version.major == 0 && version.minor == base.minor
258    } else {
259        version.major == 0 && version.minor == 0 && version.patch == base.patch
260    }
261}
262
263/// Check if `version` satisfies tilde requirement `~base`.
264///
265/// - `~1.2.3` means `>=1.2.3, <1.3.0`
266fn satisfies_tilde(version: &Version, base: &Version) -> bool {
267    version >= base && version.major == base.major && version.minor == base.minor
268}
269
270/// Check if a version satisfies a range expression string.
271///
272/// Convenience function that parses and evaluates in one step.
273pub fn satisfies_range(version: &Version, range_expr: &str) -> bool {
274    VersionReq::parse(range_expr).satisfies(version)
275}
276
277// ============================================================================
278// SAT Solver Types
279// ============================================================================
280
281/// A literal is a SAT variable with polarity (positive = include, negative =
282/// exclude). Variables are identified by 1-based integer indices.
283#[derive(Debug, Clone, PartialEq, Eq)]
284struct Literal {
285    /// Variable index (1-based)
286    var_index: usize,
287    /// True if positive (package is selected), false if negated
288    positive: bool,
289}
290
291impl Literal {
292    fn new(var_index: usize, positive: bool) -> Self {
293        Self {
294            var_index,
295            positive,
296        }
297    }
298}
299
300/// A CNF clause is a disjunction (OR) of literals.
301#[derive(Debug, Clone)]
302struct SatClause {
303    literals: Vec<Literal>,
304}
305
306impl SatClause {
307    fn new(literals: Vec<Literal>) -> Self {
308        Self { literals }
309    }
310}
311
312/// Assignment state for a variable during DPLL solving.
313#[derive(Debug, Clone, Copy, PartialEq, Eq)]
314enum Assignment {
315    /// Variable is assigned true
316    True,
317    /// Variable is assigned false
318    False,
319    /// Variable is unassigned
320    Unassigned,
321}
322
323/// DPLL-based SAT solver for dependency resolution.
324struct SatSolver {
325    /// Number of variables
326    num_vars: usize,
327    /// CNF clauses
328    clauses: Vec<SatClause>,
329    /// Current variable assignments (index 0 is unused, 1-based)
330    assignments: Vec<Assignment>,
331}
332
333impl SatSolver {
334    fn new(num_vars: usize) -> Self {
335        Self {
336            num_vars,
337            clauses: Vec::new(),
338            assignments: vec![Assignment::Unassigned; num_vars + 1],
339        }
340    }
341
342    fn add_clause(&mut self, clause: SatClause) {
343        self.clauses.push(clause);
344    }
345
346    /// Run DPLL solving algorithm.
347    ///
348    /// Returns `Some(assignments)` if satisfiable, `None` if not.
349    fn solve(&mut self) -> Option<Vec<bool>> {
350        // Reset assignments
351        self.assignments = vec![Assignment::Unassigned; self.num_vars + 1];
352        if self.dpll() {
353            let result = (1..=self.num_vars)
354                .map(|i| self.assignments[i] == Assignment::True)
355                .collect();
356            Some(result)
357        } else {
358            None
359        }
360    }
361
362    /// Core DPLL algorithm with unit propagation and pure literal elimination.
363    fn dpll(&mut self) -> bool {
364        // Unit propagation
365        if !self.unit_propagate() {
366            return false;
367        }
368
369        // Pure literal elimination
370        self.pure_literal_eliminate();
371
372        // Check if all clauses are satisfied
373        if self.all_clauses_satisfied() {
374            return true;
375        }
376
377        // Check for empty clause (conflict)
378        if self.has_empty_clause() {
379            return false;
380        }
381
382        // Choose an unassigned variable (first unassigned, prefer lower index)
383        let var = match self.choose_variable() {
384            Some(v) => v,
385            None => return self.all_clauses_satisfied(),
386        };
387
388        // Try assigning true first (prefer selecting the package)
389        let saved = self.assignments.clone();
390        self.assignments[var] = Assignment::True;
391        if self.dpll() {
392            return true;
393        }
394
395        // Backtrack and try false
396        self.assignments = saved;
397        self.assignments[var] = Assignment::False;
398        self.dpll()
399    }
400
401    /// Unit propagation: if a clause has only one unassigned literal (and all
402    /// others are false), force that literal's value.
403    ///
404    /// Returns false if a conflict is detected (empty clause under current
405    /// assignments).
406    fn unit_propagate(&mut self) -> bool {
407        let mut changed = true;
408        while changed {
409            changed = false;
410            for clause_idx in 0..self.clauses.len() {
411                let mut unassigned_lit: Option<Literal> = None;
412                let mut unassigned_count = 0;
413                let mut clause_satisfied = false;
414
415                for lit in &self.clauses[clause_idx].literals {
416                    match self.assignments[lit.var_index] {
417                        Assignment::True => {
418                            if lit.positive {
419                                clause_satisfied = true;
420                                break;
421                            }
422                        }
423                        Assignment::False => {
424                            if !lit.positive {
425                                clause_satisfied = true;
426                                break;
427                            }
428                        }
429                        Assignment::Unassigned => {
430                            unassigned_count += 1;
431                            unassigned_lit = Some(lit.clone());
432                        }
433                    }
434                }
435
436                if clause_satisfied {
437                    continue;
438                }
439
440                if unassigned_count == 0 {
441                    // All literals are falsified -- conflict
442                    return false;
443                }
444
445                if unassigned_count == 1 {
446                    // Unit clause -- force the remaining literal
447                    if let Some(lit) = unassigned_lit {
448                        self.assignments[lit.var_index] = if lit.positive {
449                            Assignment::True
450                        } else {
451                            Assignment::False
452                        };
453                        changed = true;
454                    }
455                }
456            }
457        }
458        true
459    }
460
461    /// Pure literal elimination: if a variable appears only positively (or only
462    /// negatively) across all unsatisfied clauses, assign it accordingly.
463    fn pure_literal_eliminate(&mut self) {
464        let mut appears_pos = vec![false; self.num_vars + 1];
465        let mut appears_neg = vec![false; self.num_vars + 1];
466
467        for clause in &self.clauses {
468            // Skip already-satisfied clauses
469            if self.clause_satisfied(clause) {
470                continue;
471            }
472            for lit in &clause.literals {
473                if self.assignments[lit.var_index] == Assignment::Unassigned {
474                    if lit.positive {
475                        appears_pos[lit.var_index] = true;
476                    } else {
477                        appears_neg[lit.var_index] = true;
478                    }
479                }
480            }
481        }
482
483        for var in 1..=self.num_vars {
484            if self.assignments[var] != Assignment::Unassigned {
485                continue;
486            }
487            if appears_pos[var] && !appears_neg[var] {
488                self.assignments[var] = Assignment::True;
489            } else if !appears_pos[var] && appears_neg[var] {
490                self.assignments[var] = Assignment::False;
491            }
492        }
493    }
494
495    /// Check if a single clause is satisfied under current assignments.
496    fn clause_satisfied(&self, clause: &SatClause) -> bool {
497        clause
498            .literals
499            .iter()
500            .any(|lit| match self.assignments[lit.var_index] {
501                Assignment::True => lit.positive,
502                Assignment::False => !lit.positive,
503                Assignment::Unassigned => false,
504            })
505    }
506
507    /// Check if all clauses are satisfied under current assignments.
508    fn all_clauses_satisfied(&self) -> bool {
509        self.clauses.iter().all(|c| self.clause_satisfied(c))
510    }
511
512    /// Check if any clause is falsified (all its literals are assigned false).
513    fn has_empty_clause(&self) -> bool {
514        for clause in &self.clauses {
515            let all_falsified =
516                clause
517                    .literals
518                    .iter()
519                    .all(|lit| match self.assignments[lit.var_index] {
520                        Assignment::True => !lit.positive,
521                        Assignment::False => lit.positive,
522                        Assignment::Unassigned => false,
523                    });
524            if all_falsified && !clause.literals.is_empty() {
525                return true;
526            }
527        }
528        false
529    }
530
531    /// Choose an unassigned variable for branching.
532    fn choose_variable(&self) -> Option<usize> {
533        (1..=self.num_vars).find(|&i| self.assignments[i] == Assignment::Unassigned)
534    }
535}
536
537// ============================================================================
538// Package Resolution Candidate
539// ============================================================================
540
541/// Package resolution candidate
542///
543/// Phase 4 (package ecosystem) -- used by the SAT resolver internally.
544/// Fields `package_id`, `version`, and `provides` are stored for metadata
545/// lookup and virtual-package resolution during dependency encoding.
546#[derive(Debug, Clone)]
547#[allow(dead_code)] // SAT resolver internal state -- fields used during dependency encoding
548struct Candidate {
549    package_id: PackageId,
550    version: Version,
551    dependencies: Vec<Dependency>,
552    conflicts: Vec<PackageId>,
553    /// Virtual packages this candidate provides (e.g., "mail-server")
554    provides: Vec<PackageId>,
555}
556
557// ============================================================================
558// Dependency Resolver
559// ============================================================================
560
561/// Dependency resolver with DPLL-based SAT solving.
562///
563/// Supports:
564/// - Greedy resolution (fast path for simple dependency trees)
565/// - SAT-based resolution for complex conflict scenarios
566/// - Virtual packages via `provides`
567/// - Upgrade computation
568pub struct DependencyResolver {
569    /// Available packages
570    available: BTreeMap<PackageId, Vec<Version>>,
571    /// Package metadata (dependencies, conflicts, provides)
572    metadata: BTreeMap<(PackageId, Version), Candidate>,
573    /// Virtual package providers: virtual_name -> [(real_pkg, version)]
574    virtual_providers: BTreeMap<PackageId, Vec<(PackageId, Version)>>,
575}
576
577impl DependencyResolver {
578    pub fn new() -> Self {
579        Self {
580            available: BTreeMap::new(),
581            metadata: BTreeMap::new(),
582            virtual_providers: BTreeMap::new(),
583        }
584    }
585
586    /// Register a package version
587    pub fn register_package(
588        &mut self,
589        package_id: PackageId,
590        version: Version,
591        dependencies: Vec<Dependency>,
592        conflicts: Vec<PackageId>,
593    ) {
594        self.register_package_full(package_id, version, dependencies, conflicts, Vec::new());
595    }
596
597    /// Register a package version with virtual provides
598    pub fn register_package_full(
599        &mut self,
600        package_id: PackageId,
601        version: Version,
602        dependencies: Vec<Dependency>,
603        conflicts: Vec<PackageId>,
604        provides: Vec<PackageId>,
605    ) {
606        // Add to available versions
607        self.available
608            .entry(package_id.clone())
609            .or_insert_with(Vec::new)
610            .push(version.clone());
611
612        // Sort versions in descending order (prefer newer)
613        if let Some(versions) = self.available.get_mut(&package_id) {
614            versions.sort_by(|a, b| b.cmp(a));
615        }
616
617        // Register virtual provides
618        for virt in &provides {
619            self.virtual_providers
620                .entry(virt.clone())
621                .or_insert_with(Vec::new)
622                .push((package_id.clone(), version.clone()));
623        }
624
625        // Store metadata
626        self.metadata.insert(
627            (package_id.clone(), version.clone()),
628            Candidate {
629                package_id,
630                version,
631                dependencies,
632                conflicts,
633                provides,
634            },
635        );
636    }
637
638    /// Resolve dependencies for a package using greedy algorithm.
639    ///
640    /// Returns a topologically sorted list of packages to install.
641    /// Falls back to SAT solving on conflict.
642    pub fn resolve(
643        &self,
644        dependencies: &[Dependency],
645    ) -> Result<Vec<(PackageId, Version)>, ResolverError> {
646        // Try greedy resolution first (fast path)
647        match self.resolve_greedy(dependencies) {
648            Ok(solution) => Ok(solution),
649            Err(_) => {
650                // Fall back to SAT-based resolution on conflict
651                self.resolve_sat(dependencies)
652            }
653        }
654    }
655
656    /// Greedy dependency resolution (original algorithm).
657    fn resolve_greedy(
658        &self,
659        dependencies: &[Dependency],
660    ) -> Result<Vec<(PackageId, Version)>, ResolverError> {
661        let mut solution = BTreeMap::new();
662        let mut visited = BTreeSet::new();
663
664        for dep in dependencies {
665            self.resolve_dependency(dep, &mut solution, &mut visited)?;
666        }
667
668        self.check_conflicts(&solution)?;
669
670        let mut result: Vec<(PackageId, Version)> = solution.into_iter().collect();
671        result.reverse();
672
673        Ok(result)
674    }
675
676    /// SAT-based dependency resolution using DPLL solver.
677    ///
678    /// Encodes the dependency problem as a boolean satisfiability problem
679    /// in conjunctive normal form (CNF) and solves it.
680    fn resolve_sat(
681        &self,
682        dependencies: &[Dependency],
683    ) -> Result<Vec<(PackageId, Version)>, ResolverError> {
684        // Collect all relevant packages and versions
685        let mut relevant = BTreeSet::new();
686        self.collect_relevant_packages(dependencies, &mut relevant)?;
687
688        if relevant.is_empty() {
689            return Ok(Vec::new());
690        }
691
692        // Assign variable indices to each (package, version) pair
693        let mut var_map: BTreeMap<(PackageId, Version), usize> = BTreeMap::new();
694        let mut var_list: Vec<(PackageId, Version)> = Vec::new();
695        let mut idx = 1usize;
696        for (pkg, ver) in &relevant {
697            var_map.insert((pkg.clone(), ver.clone()), idx);
698            var_list.push((pkg.clone(), ver.clone()));
699            idx += 1;
700        }
701        let num_vars = var_list.len();
702
703        let mut solver = SatSolver::new(num_vars);
704
705        // Encode constraints as CNF clauses
706        self.encode_dependencies(dependencies, &var_map, &relevant, &mut solver)?;
707        self.encode_at_most_one_version(&var_map, &mut solver);
708        self.encode_conflicts(&var_map, &mut solver);
709
710        // Solve
711        let solution = solver.solve().ok_or(ResolverError::Unsatisfiable)?;
712
713        // Decode solution
714        self.decode_solution(&solution, &var_list)
715    }
716
717    /// Collect all packages transitively reachable from the given dependencies.
718    fn collect_relevant_packages(
719        &self,
720        dependencies: &[Dependency],
721        relevant: &mut BTreeSet<(PackageId, Version)>,
722    ) -> Result<(), ResolverError> {
723        let mut work_queue: Vec<PackageId> = dependencies.iter().map(|d| d.name.clone()).collect();
724        let mut visited_pkgs = BTreeSet::new();
725
726        while let Some(pkg) = work_queue.pop() {
727            if visited_pkgs.contains(&pkg) {
728                continue;
729            }
730            visited_pkgs.insert(pkg.clone());
731
732            // Resolve virtual packages
733            let real_pkg = if self.available.contains_key(&pkg) {
734                pkg.clone()
735            } else if let Some(providers) = self.virtual_providers.get(&pkg) {
736                if let Some((real, _)) = providers.first() {
737                    real.clone()
738                } else {
739                    return Err(ResolverError::NoProvider {
740                        virtual_package: pkg,
741                    });
742                }
743            } else {
744                return Err(ResolverError::PackageNotFound { name: pkg });
745            };
746
747            if let Some(versions) = self.available.get(&real_pkg) {
748                for ver in versions {
749                    relevant.insert((real_pkg.clone(), ver.clone()));
750                    // Add transitive dependencies
751                    if let Some(candidate) = self.metadata.get(&(real_pkg.clone(), ver.clone())) {
752                        for dep in &candidate.dependencies {
753                            work_queue.push(dep.name.clone());
754                        }
755                    }
756                }
757            }
758        }
759
760        Ok(())
761    }
762
763    /// Encode dependency constraints as CNF clauses.
764    ///
765    /// For each required dependency D with version requirement R:
766    ///   at least one version of D satisfying R must be selected.
767    fn encode_dependencies(
768        &self,
769        dependencies: &[Dependency],
770        var_map: &BTreeMap<(PackageId, Version), usize>,
771        relevant: &BTreeSet<(PackageId, Version)>,
772        solver: &mut SatSolver,
773    ) -> Result<(), ResolverError> {
774        // Top-level dependencies: at least one satisfying version must be true
775        for dep in dependencies {
776            let clause = self.build_dependency_clause(dep, var_map)?;
777            if clause.literals.is_empty() {
778                return Err(ResolverError::NoSatisfyingVersion {
779                    package: dep.name.clone(),
780                    requirement: dep.version_req.clone(),
781                });
782            }
783            solver.add_clause(clause);
784        }
785
786        // Transitive dependencies: if package@version is selected,
787        // then its dependencies must also be satisfied.
788        // Encoding: NOT(pkg@ver) OR dep_ver1 OR dep_ver2 OR ...
789        for (pkg, ver) in relevant {
790            if let Some(&var_idx) = var_map.get(&(pkg.clone(), ver.clone())) {
791                if let Some(candidate) = self.metadata.get(&(pkg.clone(), ver.clone())) {
792                    for dep in &candidate.dependencies {
793                        let mut lits = vec![Literal::new(var_idx, false)];
794
795                        let dep_pkg = self.resolve_virtual(&dep.name);
796                        let req = VersionReq::parse(&dep.version_req);
797
798                        if let Some(versions) = self.available.get(&dep_pkg) {
799                            for dep_ver in versions {
800                                if req.satisfies(dep_ver) {
801                                    if let Some(&dep_var) =
802                                        var_map.get(&(dep_pkg.clone(), dep_ver.clone()))
803                                    {
804                                        lits.push(Literal::new(dep_var, true));
805                                    }
806                                }
807                            }
808                        }
809
810                        // If no satisfying version exists, the implication clause
811                        // reduces to NOT(pkg@ver) -- package cannot be selected
812                        solver.add_clause(SatClause::new(lits));
813                    }
814                }
815            }
816        }
817
818        Ok(())
819    }
820
821    /// Encode at-most-one-version constraint for each package.
822    ///
823    /// For each pair of versions (v1, v2) of the same package:
824    ///   NOT(pkg@v1) OR NOT(pkg@v2)
825    fn encode_at_most_one_version(
826        &self,
827        var_map: &BTreeMap<(PackageId, Version), usize>,
828        solver: &mut SatSolver,
829    ) {
830        for (pkg, versions) in &self.available {
831            let vars: Vec<usize> = versions
832                .iter()
833                .filter_map(|v| var_map.get(&(pkg.clone(), v.clone())).copied())
834                .collect();
835
836            // Pairwise exclusion
837            for i in 0..vars.len() {
838                for j in (i + 1)..vars.len() {
839                    solver.add_clause(SatClause::new(vec![
840                        Literal::new(vars[i], false),
841                        Literal::new(vars[j], false),
842                    ]));
843                }
844            }
845        }
846    }
847
848    /// Encode conflict constraints as negative clauses.
849    ///
850    /// If package A conflicts with package B:
851    ///   NOT(A@vN) OR NOT(B@vM) for all version combinations.
852    fn encode_conflicts(
853        &self,
854        var_map: &BTreeMap<(PackageId, Version), usize>,
855        solver: &mut SatSolver,
856    ) {
857        for ((pkg, ver), candidate) in &self.metadata {
858            if let Some(&pkg_var) = var_map.get(&(pkg.clone(), ver.clone())) {
859                for conflict in &candidate.conflicts {
860                    let conflict_pkg = self.resolve_virtual(conflict);
861                    if let Some(conflict_versions) = self.available.get(&conflict_pkg) {
862                        for cv in conflict_versions {
863                            if let Some(&cv_var) = var_map.get(&(conflict_pkg.clone(), cv.clone()))
864                            {
865                                solver.add_clause(SatClause::new(vec![
866                                    Literal::new(pkg_var, false),
867                                    Literal::new(cv_var, false),
868                                ]));
869                            }
870                        }
871                    }
872                }
873            }
874        }
875    }
876
877    /// Build a disjunctive clause for a dependency requirement.
878    fn build_dependency_clause(
879        &self,
880        dep: &Dependency,
881        var_map: &BTreeMap<(PackageId, Version), usize>,
882    ) -> Result<SatClause, ResolverError> {
883        let mut lits = Vec::new();
884        let req = VersionReq::parse(&dep.version_req);
885
886        let pkg_name = self.resolve_virtual(&dep.name);
887        if let Some(versions) = self.available.get(&pkg_name) {
888            for ver in versions {
889                if req.satisfies(ver) {
890                    if let Some(&var_idx) = var_map.get(&(pkg_name.clone(), ver.clone())) {
891                        lits.push(Literal::new(var_idx, true));
892                    }
893                }
894            }
895        }
896
897        Ok(SatClause::new(lits))
898    }
899
900    /// Decode a SAT solution back into a package list.
901    fn decode_solution(
902        &self,
903        solution: &[bool],
904        var_list: &[(PackageId, Version)],
905    ) -> Result<Vec<(PackageId, Version)>, ResolverError> {
906        let mut result = Vec::new();
907
908        for (i, selected) in solution.iter().enumerate() {
909            if *selected {
910                result.push(var_list[i].clone());
911            }
912        }
913
914        // Topological sort based on dependency edges
915        let sorted = self.topological_sort(&result)?;
916        Ok(sorted)
917    }
918
919    /// Simple topological sort of selected packages based on dependency edges.
920    fn topological_sort(
921        &self,
922        packages: &[(PackageId, Version)],
923    ) -> Result<Vec<(PackageId, Version)>, ResolverError> {
924        let pkg_set: BTreeSet<PackageId> = packages.iter().map(|(p, _)| p.clone()).collect();
925
926        // Build adjacency: dep -> [dependents]
927        let mut in_degree: BTreeMap<PackageId, usize> = BTreeMap::new();
928        let mut adj: BTreeMap<PackageId, Vec<PackageId>> = BTreeMap::new();
929
930        for (pkg, ver) in packages {
931            in_degree.entry(pkg.clone()).or_insert(0);
932            adj.entry(pkg.clone()).or_insert_with(Vec::new);
933
934            if let Some(candidate) = self.metadata.get(&(pkg.clone(), ver.clone())) {
935                for dep in &candidate.dependencies {
936                    let dep_pkg = self.resolve_virtual(&dep.name);
937                    if pkg_set.contains(&dep_pkg) {
938                        adj.entry(dep_pkg)
939                            .or_insert_with(Vec::new)
940                            .push(pkg.clone());
941                        *in_degree.entry(pkg.clone()).or_insert(0) += 1;
942                    }
943                }
944            }
945        }
946
947        // Kahn's algorithm
948        let mut queue: Vec<PackageId> = in_degree
949            .iter()
950            .filter(|(_, &deg)| deg == 0)
951            .map(|(pkg, _)| pkg.clone())
952            .collect();
953        queue.sort();
954
955        let mut order = Vec::new();
956        while let Some(pkg) = queue.pop() {
957            order.push(pkg.clone());
958            if let Some(dependents) = adj.get(&pkg) {
959                for dep in dependents {
960                    if let Some(deg) = in_degree.get_mut(dep) {
961                        *deg = deg.saturating_sub(1);
962                        if *deg == 0 {
963                            queue.push(dep.clone());
964                            queue.sort();
965                        }
966                    }
967                }
968            }
969        }
970
971        // Map back to (PackageId, Version)
972        let pkg_ver_map: BTreeMap<PackageId, Version> = packages
973            .iter()
974            .map(|(p, v)| (p.clone(), v.clone()))
975            .collect();
976        let result: Vec<(PackageId, Version)> = order
977            .into_iter()
978            .filter_map(|p| pkg_ver_map.get(&p).map(|v| (p, v.clone())))
979            .collect();
980
981        Ok(result)
982    }
983
984    /// Resolve a package name, returning the real package if it is virtual.
985    fn resolve_virtual(&self, name: &PackageId) -> PackageId {
986        if self.available.contains_key(name) {
987            return name.clone();
988        }
989        if let Some(providers) = self.virtual_providers.get(name) {
990            if let Some((real, _)) = providers.first() {
991                return real.clone();
992            }
993        }
994        name.clone()
995    }
996
997    /// Resolve an upgrade: given currently installed packages and a set of
998    /// packages to upgrade, compute the minimal set of packages to install.
999    ///
1000    /// `installed` maps package names to their currently installed versions.
1001    /// `upgrade_targets` lists packages to upgrade (empty means upgrade all).
1002    ///
1003    /// Returns the list of (package, new_version) pairs that should be
1004    /// installed to satisfy the upgrade.
1005    pub fn resolve_upgrade(
1006        &self,
1007        installed: &BTreeMap<PackageId, Version>,
1008        upgrade_targets: &[PackageId],
1009    ) -> Result<Vec<(PackageId, Version)>, ResolverError> {
1010        // Determine which packages to upgrade
1011        let targets: Vec<PackageId> = if upgrade_targets.is_empty() {
1012            installed.keys().cloned().collect()
1013        } else {
1014            upgrade_targets.to_vec()
1015        };
1016
1017        // Build dependencies: each target needs newest available version,
1018        // all other installed packages must remain satisfiable.
1019        let mut deps = Vec::new();
1020
1021        for target in &targets {
1022            deps.push(Dependency {
1023                name: target.clone(),
1024                version_req: String::from("*"),
1025            });
1026        }
1027
1028        // Add non-target installed packages as exact version constraints
1029        for (pkg, ver) in installed {
1030            if !targets.contains(pkg) {
1031                deps.push(Dependency {
1032                    name: pkg.clone(),
1033                    version_req: Self::version_to_string(ver),
1034                });
1035            }
1036        }
1037
1038        // Resolve the full set
1039        let solution = self.resolve(&deps)?;
1040
1041        // Filter to only packages that changed
1042        let mut upgrades = Vec::new();
1043        for (pkg, new_ver) in &solution {
1044            match installed.get(pkg) {
1045                Some(old_ver) if new_ver > old_ver => {
1046                    upgrades.push((pkg.clone(), new_ver.clone()));
1047                }
1048                None => {
1049                    // New dependency pulled in by upgrade
1050                    upgrades.push((pkg.clone(), new_ver.clone()));
1051                }
1052                _ => {} // Same or downgrade -- skip
1053            }
1054        }
1055
1056        Ok(upgrades)
1057    }
1058
1059    /// Resolve a single dependency recursively (greedy algorithm).
1060    fn resolve_dependency(
1061        &self,
1062        dep: &Dependency,
1063        solution: &mut BTreeMap<PackageId, Version>,
1064        visited: &mut BTreeSet<PackageId>,
1065    ) -> Result<(), ResolverError> {
1066        // Check for circular dependencies
1067        if visited.contains(&dep.name) {
1068            return Ok(()); // Already being resolved
1069        }
1070
1071        // Resolve virtual packages
1072        let real_name = self.resolve_virtual(&dep.name);
1073
1074        // Check if already resolved
1075        if solution.contains_key(&real_name) {
1076            let existing_version = &solution[&real_name];
1077            let req = VersionReq::parse(&dep.version_req);
1078
1079            if !req.satisfies(existing_version) {
1080                return Err(ResolverError::VersionConflict {
1081                    package: dep.name.clone(),
1082                    required: dep.version_req.clone(),
1083                    existing: Self::version_to_string(existing_version),
1084                });
1085            }
1086            return Ok(());
1087        }
1088
1089        visited.insert(real_name.clone());
1090
1091        // Find suitable version
1092        let version = self.find_suitable_version(&real_name, &dep.version_req)?;
1093
1094        // Get candidate metadata
1095        let candidate = self
1096            .metadata
1097            .get(&(real_name.clone(), version.clone()))
1098            .ok_or_else(|| ResolverError::MissingMetadata {
1099                package: real_name.clone(),
1100                version: Self::version_to_string(&version),
1101            })?;
1102
1103        // Resolve transitive dependencies
1104        for trans_dep in &candidate.dependencies {
1105            self.resolve_dependency(trans_dep, solution, visited)?;
1106        }
1107
1108        // Add to solution
1109        solution.insert(real_name.clone(), version);
1110
1111        visited.remove(&real_name);
1112
1113        Ok(())
1114    }
1115
1116    /// Find a suitable version for a package given version requirement
1117    fn find_suitable_version(
1118        &self,
1119        package_id: &PackageId,
1120        version_req_str: &str,
1121    ) -> Result<Version, ResolverError> {
1122        let versions =
1123            self.available
1124                .get(package_id)
1125                .ok_or_else(|| ResolverError::PackageNotFound {
1126                    name: package_id.clone(),
1127                })?;
1128
1129        let req = VersionReq::parse(version_req_str);
1130
1131        // Find first (newest) version that satisfies requirement
1132        for version in versions {
1133            if req.satisfies(version) {
1134                return Ok(version.clone());
1135            }
1136        }
1137
1138        Err(ResolverError::NoSatisfyingVersion {
1139            package: package_id.clone(),
1140            requirement: String::from(version_req_str),
1141        })
1142    }
1143
1144    /// Check for conflicts in solution
1145    fn check_conflicts(
1146        &self,
1147        solution: &BTreeMap<PackageId, Version>,
1148    ) -> Result<(), ResolverError> {
1149        for (pkg_id, version) in solution {
1150            if let Some(candidate) = self.metadata.get(&(pkg_id.clone(), version.clone())) {
1151                for conflict in &candidate.conflicts {
1152                    let resolved = self.resolve_virtual(conflict);
1153                    if solution.contains_key(&resolved) {
1154                        return Err(ResolverError::Conflict {
1155                            package: format!("{} {}", pkg_id, Self::version_to_string(version)),
1156                            conflicting: conflict.clone(),
1157                        });
1158                    }
1159                }
1160            }
1161        }
1162        Ok(())
1163    }
1164
1165    /// Convert version to string
1166    fn version_to_string(version: &Version) -> String {
1167        alloc::format!("{}.{}.{}", version.major, version.minor, version.patch)
1168    }
1169
1170    /// Get the latest available version for a package.
1171    pub fn latest_version(&self, package_id: &str) -> Option<Version> {
1172        self.available
1173            .get(package_id)
1174            .and_then(|versions| versions.first().cloned())
1175    }
1176
1177    /// Search available packages by name substring.
1178    ///
1179    /// Returns matching (package_id, latest_version) pairs.
1180    pub fn search(&self, query: &str) -> Vec<(PackageId, Version)> {
1181        let query_lower = query.to_lowercase();
1182        self.available
1183            .iter()
1184            .filter(|(name, _)| name.to_lowercase().contains(&query_lower))
1185            .filter_map(|(name, versions)| versions.first().map(|v| (name.clone(), v.clone())))
1186            .collect()
1187    }
1188
1189    /// Get metadata for a package (returns the latest version's metadata).
1190    pub fn get_package_metadata(&self, package_id: &str) -> Option<PackageMetadata> {
1191        let versions = self.available.get(package_id)?;
1192        let latest = versions.first()?;
1193        let candidate = self
1194            .metadata
1195            .get(&(String::from(package_id), latest.clone()))?;
1196
1197        Some(PackageMetadata {
1198            name: candidate.package_id.clone(),
1199            version: candidate.version.clone(),
1200            author: String::from("unknown"),
1201            description: String::new(),
1202            license: String::new(),
1203            dependencies: candidate.dependencies.clone(),
1204            conflicts: candidate.conflicts.clone(),
1205        })
1206    }
1207}
1208
1209impl Default for DependencyResolver {
1210    fn default() -> Self {
1211        Self::new()
1212    }
1213}
1214
1215#[cfg(test)]
1216mod tests {
1217    use super::*;
1218
1219    #[test]
1220    fn test_version_req_parsing() {
1221        let req = VersionReq::parse("1.2.3");
1222        assert!(matches!(req, VersionReq::Exact(_)));
1223
1224        let req = VersionReq::parse(">=1.0.0");
1225        assert!(matches!(req, VersionReq::AtLeast(_)));
1226
1227        let req = VersionReq::parse("*");
1228        assert!(matches!(req, VersionReq::Any));
1229    }
1230
1231    #[test]
1232    fn test_version_satisfies() {
1233        let v123 = Version::new(1, 2, 3);
1234        let v100 = Version::new(1, 0, 0);
1235
1236        let req = VersionReq::Exact(v123.clone());
1237        assert!(req.satisfies(&v123));
1238        assert!(!req.satisfies(&v100));
1239
1240        let req = VersionReq::AtLeast(v100.clone());
1241        assert!(req.satisfies(&v123));
1242        assert!(req.satisfies(&v100));
1243    }
1244
1245    #[test]
1246    fn test_simple_resolution() {
1247        let mut resolver = DependencyResolver::new();
1248
1249        resolver.register_package(String::from("pkg-a"), Version::new(1, 0, 0), vec![], vec![]);
1250
1251        let deps = vec![Dependency {
1252            name: String::from("pkg-a"),
1253            version_req: String::from("1.0.0"),
1254        }];
1255
1256        let result = resolver.resolve(&deps);
1257        assert!(result.is_ok());
1258        let packages = result.unwrap();
1259        assert_eq!(packages.len(), 1);
1260    }
1261
1262    #[test]
1263    fn test_caret_version_req() {
1264        let req = VersionReq::parse("^1.2.3");
1265        assert!(req.satisfies(&Version::new(1, 2, 3)));
1266        assert!(req.satisfies(&Version::new(1, 9, 0)));
1267        assert!(!req.satisfies(&Version::new(2, 0, 0)));
1268        assert!(!req.satisfies(&Version::new(1, 2, 2)));
1269    }
1270
1271    #[test]
1272    fn test_caret_zero_major() {
1273        let req = VersionReq::parse("^0.2.3");
1274        assert!(req.satisfies(&Version::new(0, 2, 3)));
1275        assert!(req.satisfies(&Version::new(0, 2, 9)));
1276        assert!(!req.satisfies(&Version::new(0, 3, 0)));
1277        assert!(!req.satisfies(&Version::new(1, 0, 0)));
1278    }
1279
1280    #[test]
1281    fn test_tilde_version_req() {
1282        let req = VersionReq::parse("~1.2.3");
1283        assert!(req.satisfies(&Version::new(1, 2, 3)));
1284        assert!(req.satisfies(&Version::new(1, 2, 9)));
1285        assert!(!req.satisfies(&Version::new(1, 3, 0)));
1286        assert!(!req.satisfies(&Version::new(2, 0, 0)));
1287    }
1288
1289    #[test]
1290    fn test_compound_version_req() {
1291        let req = VersionReq::parse(">=1.2.0, <2.0.0");
1292        assert!(req.satisfies(&Version::new(1, 2, 0)));
1293        assert!(req.satisfies(&Version::new(1, 9, 9)));
1294        assert!(!req.satisfies(&Version::new(2, 0, 0)));
1295        assert!(!req.satisfies(&Version::new(1, 1, 9)));
1296    }
1297
1298    #[test]
1299    fn test_satisfies_range_function() {
1300        assert!(satisfies_range(&Version::new(1, 5, 0), "^1.2"));
1301        assert!(!satisfies_range(&Version::new(2, 0, 0), "^1.2"));
1302        assert!(satisfies_range(&Version::new(1, 2, 5), "~1.2.3"));
1303    }
1304
1305    #[test]
1306    fn test_conflict_detection() {
1307        let mut resolver = DependencyResolver::new();
1308
1309        resolver.register_package(
1310            String::from("pkg-a"),
1311            Version::new(1, 0, 0),
1312            vec![],
1313            vec![String::from("pkg-b")],
1314        );
1315        resolver.register_package(String::from("pkg-b"), Version::new(1, 0, 0), vec![], vec![]);
1316
1317        let deps = vec![
1318            Dependency {
1319                name: String::from("pkg-a"),
1320                version_req: String::from("*"),
1321            },
1322            Dependency {
1323                name: String::from("pkg-b"),
1324                version_req: String::from("*"),
1325            },
1326        ];
1327
1328        let result = resolver.resolve(&deps);
1329        assert!(result.is_err());
1330    }
1331
1332    #[test]
1333    fn test_transitive_dependencies() {
1334        let mut resolver = DependencyResolver::new();
1335
1336        resolver.register_package(
1337            String::from("app"),
1338            Version::new(1, 0, 0),
1339            vec![Dependency {
1340                name: String::from("lib-a"),
1341                version_req: String::from(">=1.0.0"),
1342            }],
1343            vec![],
1344        );
1345        resolver.register_package(
1346            String::from("lib-a"),
1347            Version::new(1, 2, 0),
1348            vec![Dependency {
1349                name: String::from("lib-b"),
1350                version_req: String::from("^1.0"),
1351            }],
1352            vec![],
1353        );
1354        resolver.register_package(String::from("lib-b"), Version::new(1, 1, 0), vec![], vec![]);
1355
1356        let deps = vec![Dependency {
1357            name: String::from("app"),
1358            version_req: String::from("*"),
1359        }];
1360
1361        let result = resolver.resolve(&deps);
1362        assert!(result.is_ok());
1363        let packages = result.unwrap();
1364        assert_eq!(packages.len(), 3);
1365    }
1366
1367    #[test]
1368    fn test_virtual_package_provides() {
1369        let mut resolver = DependencyResolver::new();
1370
1371        // "postfix" provides "mail-server"
1372        resolver.register_package_full(
1373            String::from("postfix"),
1374            Version::new(3, 5, 0),
1375            vec![],
1376            vec![],
1377            vec![String::from("mail-server")],
1378        );
1379
1380        // "webapp" depends on "mail-server" (virtual)
1381        resolver.register_package(
1382            String::from("webapp"),
1383            Version::new(1, 0, 0),
1384            vec![Dependency {
1385                name: String::from("mail-server"),
1386                version_req: String::from("*"),
1387            }],
1388            vec![],
1389        );
1390
1391        let deps = vec![Dependency {
1392            name: String::from("webapp"),
1393            version_req: String::from("*"),
1394        }];
1395
1396        let result = resolver.resolve(&deps);
1397        assert!(result.is_ok());
1398        let packages = result.unwrap();
1399        // Should include webapp and postfix
1400        assert_eq!(packages.len(), 2);
1401        assert!(packages.iter().any(|(p, _)| p == "postfix"));
1402    }
1403
1404    #[test]
1405    fn test_resolve_upgrade() {
1406        let mut resolver = DependencyResolver::new();
1407
1408        resolver.register_package(String::from("pkg-a"), Version::new(1, 0, 0), vec![], vec![]);
1409        resolver.register_package(String::from("pkg-a"), Version::new(2, 0, 0), vec![], vec![]);
1410        resolver.register_package(String::from("pkg-b"), Version::new(1, 0, 0), vec![], vec![]);
1411
1412        let mut installed = BTreeMap::new();
1413        installed.insert(String::from("pkg-a"), Version::new(1, 0, 0));
1414        installed.insert(String::from("pkg-b"), Version::new(1, 0, 0));
1415
1416        let upgrades = resolver
1417            .resolve_upgrade(&installed, &[String::from("pkg-a")])
1418            .unwrap();
1419
1420        assert_eq!(upgrades.len(), 1);
1421        assert_eq!(upgrades[0].0, "pkg-a");
1422        assert_eq!(upgrades[0].1, Version::new(2, 0, 0));
1423    }
1424
1425    #[test]
1426    fn test_sat_conflict_resolution() {
1427        let mut resolver = DependencyResolver::new();
1428
1429        // pkg-a@1 depends on lib@1
1430        resolver.register_package(
1431            String::from("pkg-a"),
1432            Version::new(1, 0, 0),
1433            vec![Dependency {
1434                name: String::from("lib"),
1435                version_req: String::from("1.0.0"),
1436            }],
1437            vec![],
1438        );
1439        // pkg-a@2 depends on lib@2
1440        resolver.register_package(
1441            String::from("pkg-a"),
1442            Version::new(2, 0, 0),
1443            vec![Dependency {
1444                name: String::from("lib"),
1445                version_req: String::from("2.0.0"),
1446            }],
1447            vec![],
1448        );
1449        resolver.register_package(String::from("lib"), Version::new(1, 0, 0), vec![], vec![]);
1450        resolver.register_package(String::from("lib"), Version::new(2, 0, 0), vec![], vec![]);
1451
1452        // Request pkg-a (any version) -- SAT solver should pick a consistent
1453        // set
1454        let deps = vec![Dependency {
1455            name: String::from("pkg-a"),
1456            version_req: String::from("*"),
1457        }];
1458
1459        let result = resolver.resolve(&deps);
1460        assert!(result.is_ok());
1461        let packages = result.unwrap();
1462        assert_eq!(packages.len(), 2);
1463
1464        // Verify consistency: pkg-a version matches lib version
1465        let pkg_a_ver = packages.iter().find(|(p, _)| p == "pkg-a").unwrap();
1466        let lib_ver = packages.iter().find(|(p, _)| p == "lib").unwrap();
1467        assert_eq!(pkg_a_ver.1.major, lib_ver.1.major);
1468    }
1469
1470    #[test]
1471    fn test_flexible_version_parsing() {
1472        // ^1 should parse as ^1.0.0
1473        let req = VersionReq::parse("^1");
1474        assert!(req.satisfies(&Version::new(1, 5, 0)));
1475        assert!(!req.satisfies(&Version::new(2, 0, 0)));
1476
1477        // ~1.2 should parse as ~1.2.0
1478        let req = VersionReq::parse("~1.2");
1479        assert!(req.satisfies(&Version::new(1, 2, 5)));
1480        assert!(!req.satisfies(&Version::new(1, 3, 0)));
1481    }
1482}
veridian_kernel/pkg/resolver.rs

veridian_kernel/pkg/
resolver.rs
