Implement a Dependency Resolver with Semantic Versioning

""" Dependency resolver with SemVer support (exact, ^, ~). Implements backtracking to select the highest possible version per package consistent with all constraints, detects circular deps, missing packages/versions, and conflicts. API: resolve_dependencies(available_packages, target_name, target_spec) - available_packages: dict mapping package name -> list of versions, where each version is a dict {"version": "1.2.3", "dependencies": {"pkg-B": "^1.0.0", ...}} - target_name: package name string - target_spec: version spec string (exact like "1.2.3", or "^1.2.3", or "~1.2.3") Returns: list of {"name": pkg, "version": ver} in topological order (dependencies before dependents) Raises exceptions: NotFoundError, ConflictError, CircularDependencyError with descriptive messages. Example usage with the sample data in the prompt is provided at the bottom under `if __name__ == '__main__'`. """ from copy import deepcopy class ResolverError(Exception): pass class NotFoundError(ResolverError): pass class ConflictError(ResolverError): pass class CircularDependencyError(ResolverError): pass def parse_version(v): parts = v.split('.') if len(parts) != 3: raise ValueError(f"Unsupported version format: {v}") try: return tuple(int(p) for p in parts) except Exception: raise ValueError(f"Unsupported version number in: {v}") def cmp_version(a, b): return (a > b) - (a < b) def satisfies_spec(version_str, spec): v = parse_version(version_str) if spec.startswith('^'): base = parse_version(spec[1:]) # ^1.2.3 => >=1.2.3 <2.0.0 min_v = base max_v = (base[0] + 1, 0, 0) return v >= min_v and v < max_v elif spec.startswith('~'): base = parse_version(spec[1:]) # ~1.2.3 => >=1.2.3 <1.3.0 min_v = base max_v = (base[0], base[1] + 1, 0) return v >= min_v and v < max_v else: # exact base = parse_version(spec) return v == base def filter_versions(available_version_list, specs): # available_version_list: list of version strings (e.g. ["1.1.0","1.0.5"]) or list of version dicts # specs: list of spec strings # Return list of version dicts that satisfy all specs result = [] for verobj in available_version_list: ver_str = verobj['version'] ok = True for s in specs: if not satisfies_spec(ver_str, s): ok = False break if ok: result.append(verobj) # sort descending highest first result.sort(key=lambda vd: parse_version(vd['version']), reverse=True) return result def build_versions_index(available_packages): # Normalize and sort available versions descending idx = {} for pkg, versions in available_packages.items(): # ensure each item has 'version' and 'dependencies' vlist = [] for v in versions: deps = v.get('dependencies', {}) if isinstance(v, dict) else {} vlist.append({'version': v['version'], 'dependencies': deps}) vlist.sort(key=lambda vd: parse_version(vd['version']), reverse=True) idx[pkg] = vlist return idx def resolve_dependencies(available_packages, target_name, target_spec): """ Main resolver function. Returns list of {"name": pkg, "version": ver} in topological order. Raises NotFoundError, ConflictError, CircularDependencyError. """ versions_idx = build_versions_index(available_packages) # Ensure target package exists if target_name not in versions_idx: raise NotFoundError(f"Package '{target_name}' not found in available packages") # constraints: package -> list of spec strings that must all be satisfied initial_constraints = {target_name: [target_spec]} chosen = {} # package -> chosen version string # recursion stack for cycle detection stack = [] def resolve_pkg(pkg_name, constraints, chosen, stack): if pkg_name in stack: cycle = stack[stack.index(pkg_name):] + [pkg_name] raise CircularDependencyError(f"Circular dependency detected: {' -> '.join(cycle)}") if pkg_name not in versions_idx: raise NotFoundError(f"Package '{pkg_name}' required but not found") # If already chosen, check it satisfies all current constraints specs = constraints.get(pkg_name, []) if pkg_name in chosen: chosen_ver = chosen[pkg_name] for s in specs: if not satisfies_spec(chosen_ver, s): raise ConflictError(f"Chosen version {pkg_name}@{chosen_ver} does not satisfy new constraint '{s}'") # already resolved and satisfies constraints return # Get candidate versions for this package by filtering available by all specs candidates = filter_versions(versions_idx[pkg_name], specs) if not candidates: # no available version satisfies constraints raise NotFoundError(f"No available version for package '{pkg_name}' satisfies constraints: {specs}") # Try candidates in descending order (highest first) stack.append(pkg_name) last_error = None for cand in candidates: cand_ver = cand['version'] # pick this candidate and try to resolve its dependencies chosen[pkg_name] = cand_ver # prepare new constraints for dependencies new_constraints = deepcopy(constraints) # add dependency constraints deps = cand.get('dependencies', {}) or {} failed = False try: for dep_name, dep_spec in deps.items(): # append dep_spec to new_constraints[dep_name] new_constraints.setdefault(dep_name, []) new_constraints[dep_name].append(dep_spec) # resolve dependency resolve_pkg(dep_name, new_constraints, chosen, stack) # all dependencies resolved for this candidate stack.pop() return except ResolverError as e: # record the error and try next candidate last_error = e failed = True # cleanup chosen for this pkg and continue if pkg_name in chosen: del chosen[pkg_name] # continue to next candidate continue # exhausted candidates if stack: stack.pop() if last_error: # propagate the most recent error (could be Conflict/NotFound/Circular) raise ConflictError(f"Unable to resolve '{pkg_name}': tried versions {[c['version'] for c in candidates]}. Last error: {last_error}") else: raise ConflictError(f"Unable to resolve '{pkg_name}' due to unknown conflict") # Start resolution resolve_pkg(target_name, initial_constraints, chosen, stack) # At this point chosen contains all packages and their selected versions # Build dependency graph for topological sort graph = {pkg: set() for pkg in chosen.keys()} # pkg -> set of dependency package names for pkg, ver in chosen.items(): # find the version object in versions_idx ver_objs = [v for v in versions_idx[pkg] if v['version'] == ver] if not ver_objs: raise NotFoundError(f"Selected version {pkg}@{ver} not found in available list") deps = ver_objs[0].get('dependencies', {}) or {} for d in deps.keys(): if d in chosen: # only include edges for packages in the final chosen set graph[pkg].add(d) # topological sort (dependencies before dependents) - Kahn's algorithm # reverse edges: want order where deps come first, so edges from node -> its deps # We'll invert to compute in-degree where edge dep <- pkg indegree = {pkg: 0 for pkg in graph} for pkg, deps in graph.items(): for d in deps: indegree[d] += 1 # nodes with indegree 0 are leaves (no other package depending on them), but we want dependencies first - # Because our edge direction is pkg -> deps, nodes with indegree 0 are packages that nobody depends on -> can be installed last. # To obtain dependencies before dependents, we should output in reversed topological order of this graph. # Simpler: perform DFS postorder to ensure deps before dependents. visited = set() order = [] def dfs_topo(n): if n in visited: return visited.add(n) for dep in graph.get(n, []): dfs_topo(dep) order.append(n) for node in graph.keys(): dfs_topo(node) # order now has dependencies before dependents result = [] for pkg in order: result.append({'name': pkg, 'version': chosen[pkg]}) # It's possible that some packages were required but had no edges in graph; dfs_topo covers all keys return result # Example usage and simple tests if __name__ == '__main__': sample = { "pkg-A": [ {"version": "1.0.0", "dependencies": {"pkg-B": "~1.0.0"}}, {"version": "1.1.0", "dependencies": {"pkg-B": "^1.1.0"}} ], "pkg-B": [ {"version": "1.0.0", "dependencies": {}}, {"version": "1.0.5", "dependencies": {}}, {"version": "1.1.0", "dependencies": {}}, {"version": "2.0.0", "dependencies": {}} ], "pkg-C": [ {"version": "1.0.0", "dependencies": {"pkg-A": "^1.0.0", "pkg-B": "^1.0.0"}} ], "pkg-D": [ {"version": "1.0.0", "dependencies": {"pkg-D": "^1.0.0"}} ], "pkg-E": [ {"version": "1.0.0", "dependencies": {"pkg-F": "^1.0.0"}} ], "pkg-F": [ {"version": "1.0.0", "dependencies": {"pkg-E": "^1.0.0"}} ] } # Example 1: resolve pkg-C ^1.0.0 try: res = resolve_dependencies(sample, 'pkg-C', '^1.0.0') print('Resolved pkg-C:^1.0.0 ->', res) except ResolverError as e: print('Error resolving pkg-C:', e) # Example 2: circular self-dependency pkg-D try: res = resolve_dependencies(sample, 'pkg-D', '^1.0.0') print('Resolved pkg-D:^1.0.0 ->', res) except ResolverError as e: print('Error resolving pkg-D:', e) # Example 3: mutual cycle pkg-E -> pkg-F -> pkg-E try: res = resolve_dependencies(sample, 'pkg-E', '^1.0.0') print('Resolved pkg-E:^1.0.0 ->', res) except ResolverError as e: print('Error resolving pkg-E:', e) # Example 4: missing package try: res = resolve_dependencies(sample, 'pkg-Unknown', '^1.0.0') print('Resolved pkg-Unknown:^1.0.0 ->', res) except ResolverError as e: print('Error resolving pkg-Unknown:', e) # Example 5: conflict example - create conflict where two dependents require incompatible versions conflict_sample = deepcopy(sample) conflict_sample['pkg-X'] = [ {"version": "1.0.0", "dependencies": {"pkg-B": "^1.0.0"}}, {"version": "2.0.0", "dependencies": {"pkg-B": "^2.0.0"}} ] conflict_sample['pkg-Y'] = [ {"version": "1.0.0", "dependencies": {"pkg-B": "^1.0.0", "pkg-X": "1.0.0"}} ] try: # Request X@2.0.0 and Y@1.0.0 indirectly may conflict on pkg-B res = resolve_dependencies(conflict_sample, 'pkg-Y', '^1.0.0') print('Resolved conflict sample ->', res) except ResolverError as e: print('Error resolving conflict sample:', e) # You can integrate this module into another system by importing resolve_dependencies.

from typing import Dict, List, Set, Tuple, Optional from dataclasses import dataclass import re @dataclass class Package: name: str version: str @dataclass class ResolutionResult: success: bool packages: List[Package] error: Optional[str] = None def parse_version(version_str: str) -> Tuple[int, int, int]: """Parse semantic version string to tuple of integers.""" match = re.match(r'^(\d+)\.(\d+)\.(\d+)$', version_str) if not match: raise ValueError(f"Invalid version format: {version_str}") return tuple(map(int, match.groups())) def version_satisfies(version: str, constraint: str) -> bool: """Check if a version satisfies a constraint.""" v = parse_version(version) if constraint.startswith('^'): spec = constraint[1:] spec_v = parse_version(spec) major = spec_v[0] return v >= spec_v and v[0] == major elif constraint.startswith('~'): spec = constraint[1:] spec_v = parse_version(spec) major, minor = spec_v[0], spec_v[1] return v >= spec_v and v[0] == major and v[1] == minor else: spec_v = parse_version(constraint) return v == spec_v def find_best_version(package_name: str, constraint: str, available_packages: Dict) -> Optional[str]: """Find the highest version that satisfies the constraint.""" if package_name not in available_packages: return None versions = [pkg['version'] for pkg in available_packages[package_name]] matching = [v for v in versions if version_satisfies(v, constraint)] if not matching: return None return max(matching, key=parse_version) def resolve_dependencies(available_packages: Dict, target_package: str, version_constraint: str) -> ResolutionResult: """Resolve dependencies for a package with semantic versioning support.""" # Check if target package exists if target_package not in available_packages: return ResolutionResult(False, [], f"Package '{target_package}' not found") # Find best version for target best_version = find_best_version(target_package, version_constraint, available_packages) if best_version is None: return ResolutionResult(False, [], f"No version of '{target_package}' satisfies '{version_constraint}'") # Track resolved packages and constraints resolved: Dict[str, str] = {} # package_name -> version constraints: Dict[str, Set[str]] = {} # package_name -> set of constraints visiting: Set[str] = set() # For cycle detection visited: Set[str] = set() def get_package_info(name: str, version: str) -> Optional[Dict]: """Get package info for a specific version.""" if name not in available_packages: return None for pkg in available_packages[name]: if pkg['version'] == version: return pkg return None def dfs(package_name: str, constraint: str) -> bool: """DFS to resolve dependencies. Returns True if successful.""" # Check for circular dependency if package_name in visiting: return False if package_name in visited: # Already resolved, check if current constraint is satisfied if package_name in resolved: if not version_satisfies(resolved[package_name], constraint): return False return True visiting.add(package_name) # Track constraint if package_name not in constraints: constraints[package_name] = set() constraints[package_name].add(constraint) # Find best version satisfying all constraints all_constraints = constraints[package_name] best_version = None if package_name not in available_packages: visiting.remove(package_name) return False versions = [pkg['version'] for pkg in available_packages[package_name]] for v in sorted(versions, key=parse_version, reverse=True): if all(version_satisfies(v, c) for c in all_constraints): best_version = v break if best_version is None: visiting.remove(package_name) return False resolved[package_name] = best_version # Get dependencies pkg_info = get_package_info(package_name, best_version) if pkg_info is None: visiting.remove(package_name) return False dependencies = pkg_info.get('dependencies', {}) # Resolve dependencies for dep_name, dep_constraint in dependencies.items(): if not dfs(dep_name, dep_constraint): visiting.remove(package_name) return False visiting.remove(package_name) visited.add(package_name) return True # Start resolution if not dfs(target_package, version_constraint): if target_package in visiting: return ResolutionResult(False, [], f"Circular dependency detected involving '{target_package}'") return ResolutionResult(False, [], f"Unable to resolve dependencies for '{target_package}@{version_constraint}'") # Topological sort def topological_sort() -> List[Package]: in_degree = {pkg: 0 for pkg in resolved} graph = {pkg: [] for pkg in resolved} for pkg_name, version in resolved.items(): pkg_info = get_package_info(pkg_name, version) if pkg_info: for dep_name in pkg_info.get('dependencies', {}): if dep_name in resolved: graph[dep_name].append(pkg_name) in_degree[pkg_name] += 1 queue = [pkg for pkg in resolved if in_degree[pkg] == 0] result = [] while queue: pkg = queue.pop(0) result.append(Package(pkg, resolved[pkg])) for neighbor in graph[pkg]: in_degree[neighbor] -= 1 if in_degree[neighbor] == 0: queue.append(neighbor) return result sorted_packages = topological_sort() return ResolutionResult(True, sorted_packages) # Example usage if __name__ == "__main__": packages = { "pkg-A": [ {"version": "1.0.0", "dependencies": {"pkg-B": "~1.0.0"}}, {"version": "1.1.0", "dependencies": {"pkg-B": "^1.1.0"}} ], "pkg-B": [ {"version": "1.0.0", "dependencies": {}}, {"version": "1.0.5", "dependencies": {}}, {"version": "1.1.0", "dependencies": {}}, {"version": "2.0.0", "dependencies": {}} ], "pkg-C": [ {"version": "1.0.0", "dependencies": {"pkg-A": "^1.0.0", "pkg-B": "^1.0.0"}} ], "pkg-D": [ {"version": "1.0.0", "dependencies": {"pkg-D": "^1.0.0"}} ], "pkg-E": [ {"version": "1.0.0", "dependencies": {"pkg-F": "^1.0.0"}} ], "pkg-F": [ {"version": "1.0.0", "dependencies": {"pkg-E": "^1.0.0"}} ] } result = resolve_dependencies(packages, "pkg-C", "^1.0.0") print(f"Success: {result.success}") print(f"Packages: {[(p.name, p.version) for p in result.packages]}") if result.error: print(f"Error: {result.error}")