セマンティックバージョニングを用いた依存関係リゾルバを実装する

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}")