Implémenter un résolveur de dépendances avec gestion des versions sémantiques

Résolveur de dépendances avec prise en charge de SemVer (exact, ^, ~). Implémente le backtracking pour sélectionner la version la plus élevée possible par package, cohérente avec toutes les contraintes, détecte les dépendances circulaires, les packages/versions manquants et les conflits. API : resolve_dependencies(available_packages, target_name, target_spec) - available_packages : dictionnaire mappant nom du package -> liste de versions, où chaque version est un dictionnaire {"version": "1.2.3", "dependencies": {"pkg-B": "^1.0.0", ...}} - target_name : nom du package (chaîne de caractères) - target_spec : spécification de version (chaîne de caractères, ex: "1.2.3", "^1.2.3", ou "~1.2.3") Retourne : liste de {"name": pkg, "version": ver} dans l'ordre topologique (dépendances avant les dépendants) Lève des exceptions : NotFoundError, ConflictError, CircularDependencyError avec des messages descriptifs. Un exemple d'utilisation avec les données d'exemple dans l'invite est fourni en bas sous `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"Format de version non pris en charge : {v}") try: return tuple(int(p) for p in parts) except Exception: raise ValueError(f"Numéro de version non pris en charge dans : {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 : liste de chaînes de versions (ex: ["1.1.0","1.0.5"]) ou liste de dictionnaires de versions # specs : liste de chaînes de spécifications # Retourne la liste des dictionnaires de versions qui satisfont toutes les spécifications 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) # trier par ordre décroissant, le plus élevé en premier result.sort(key=lambda vd: parse_version(vd['version']), reverse=True) return result def build_versions_index(available_packages): # Normaliser et trier les versions disponibles par ordre décroissant idx = {} for pkg, versions in available_packages.items(): # s'assurer que chaque élément a 'version' et '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): """ Fonction principale du résolveur. Retourne une liste de {"name": pkg, "version": ver} dans l'ordre topologique. Lève NotFoundError, ConflictError, CircularDependencyError. """ versions_idx = build_versions_index(available_packages) # S'assurer que le package cible existe if target_name not in versions_idx: raise NotFoundError(f"Package '{target_name}' introuvable dans les packages disponibles") # contraintes : package -> liste de chaînes de spécifications qui doivent toutes être satisfaites initial_constraints = {target_name: [target_spec]} chosen = {} # package -> version choisie (chaîne de caractères) # pile de récursion pour la détection de cycle 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"Dépendance circulaire détectée : {' -> '.join(cycle)}") if pkg_name not in versions_idx: raise NotFoundError(f"Package '{pkg_name}' requis mais introuvable") # Si déjà choisi, vérifier qu'il satisfait toutes les contraintes actuelles 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"La version choisie {pkg_name}@{chosen_ver} ne satisfait pas la nouvelle contrainte '{s}'") # déjà résolu et satisfait les contraintes return # Obtenir les versions candidates pour ce package en filtrant les disponibles par toutes les spécifications candidates = filter_versions(versions_idx[pkg_name], specs) if not candidates: # aucune version disponible ne satisfait les contraintes raise NotFoundError(f"Aucune version disponible pour le package '{pkg_name}' ne satisfait les contraintes : {specs}") # Essayer les candidats par ordre décroissant (le plus élevé en premier) stack.append(pkg_name) last_error = None for cand in candidates: cand_ver = cand['version'] # choisir ce candidat et essayer de résoudre ses dépendances chosen[pkg_name] = cand_ver # préparer les nouvelles contraintes pour les dépendances new_constraints = deepcopy(constraints) # ajouter les contraintes de dépendance deps = cand.get('dependencies', {}) or {} failed = False try: for dep_name, dep_spec in deps.items(): # ajouter dep_spec à new_constraints[dep_name] new_constraints.setdefault(dep_name, []) new_constraints[dep_name].append(dep_spec) # résoudre la dépendance resolve_pkg(dep_name, new_constraints, chosen, stack) # toutes les dépendances résolues pour ce candidat stack.pop() return except ResolverError as e: # enregistrer l'erreur et essayer le candidat suivant last_error = e failed = True # nettoyer 'chosen' pour ce package et continuer if pkg_name in chosen: del chosen[pkg_name] # continuer vers le candidat suivant continue # tous les candidats épuisés if stack: stack.pop() if last_error: # propager l'erreur la plus récente (pourrait être Conflict/NotFound/Circular) raise ConflictError(f"Impossible de résoudre '{pkg_name}' : a essayé les versions {[c['version'] for c in candidates]}. Dernière erreur : {last_error}") else: raise ConflictError(f"Impossible de résoudre '{pkg_name}' en raison d'un conflit inconnu") # Démarrer la résolution resolve_pkg(target_name, initial_constraints, chosen, stack) # À ce stade, 'chosen' contient tous les packages et leurs versions sélectionnées # Construire le graphe de dépendances pour le tri topologique graph = {pkg: set() for pkg in chosen.keys()} # pkg -> ensemble des noms de packages dépendants for pkg, ver in chosen.items(): # trouver l'objet version dans versions_idx ver_objs = [v for v in versions_idx[pkg] if v['version'] == ver] if not ver_objs: raise NotFoundError(f"Version sélectionnée {pkg}@{ver} introuvable dans la liste disponible") deps = ver_objs[0].get('dependencies', {}) or {} for d in deps.keys(): if d in chosen: # inclure uniquement les arêtes pour les packages dans l'ensemble choisi final graph[pkg].add(d) # tri topologique (dépendances avant les dépendants) - algorithme de Kahn # inverser les arêtes : on veut un ordre où les dépendances viennent en premier, donc les arêtes du nœud -> ses dépendances # Nous allons inverser pour calculer le degré entrant où l'arête dep <- pkg indegree = {pkg: 0 for pkg in graph} for pkg, deps in graph.items(): for d in deps: indegree[d] += 1 # les nœuds avec un degré entrant de 0 sont des feuilles (personne ne dépend d'eux), mais nous voulons les dépendances en premier - # Parce que notre direction d'arête est pkg -> deps, les nœuds avec un degré entrant de 0 sont des packages dont personne ne dépend -> peuvent être installés en dernier. # Pour obtenir les dépendances avant les dépendants, nous devons sortir dans l'ordre topologique inversé de ce graphe. # Plus simple : effectuer un post-ordre DFS pour s'assurer que les dépendances sont avant les dépendants. 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' contient maintenant les dépendances avant les dépendants result = [] for pkg in order: result.append({'name': pkg, 'version': chosen[pkg]}) # Il est possible que certains packages aient été requis mais n'aient pas d'arêtes dans le graphe ; dfs_topo couvre toutes les clés return result # Exemple d'utilisation et tests simples 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"}} ] } # Exemple 1 : résoudre pkg-C ^1.0.0 try: res = resolve_dependencies(sample, 'pkg-C', '^1.0.0') print('Résolu pkg-C:^1.0.0 ->', res) except ResolverError as e: print('Erreur lors de la résolution de pkg-C :', e) # Exemple 2 : dépendance circulaire auto pkg-D try: res = resolve_dependencies(sample, 'pkg-D', '^1.0.0') print('Résolu pkg-D:^1.0.0 ->', res) except ResolverError as e: print('Erreur lors de la résolution de pkg-D :', e) # Exemple 3 : cycle mutuel pkg-E -> pkg-F -> pkg-E try: res = resolve_dependencies(sample, 'pkg-E', '^1.0.0') print('Résolu pkg-E:^1.0.0 ->', res) except ResolverError as e: print('Erreur lors de la résolution de pkg-E :', e) # Exemple 4 : package manquant try: res = resolve_dependencies(sample, 'pkg-Unknown', '^1.0.0') print('Résolu pkg-Unknown:^1.0.0 ->', res) except ResolverError as e: print('Erreur lors de la résolution de pkg-Unknown :', e) # Exemple 5 : exemple de conflit - créer un conflit où deux dépendants exigent des versions incompatibles 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: # Demander X@2.0.0 et Y@1.0.0 indirectement peut entrer en conflit sur pkg-B res = resolve_dependencies(conflict_sample, 'pkg-Y', '^1.0.0') print('Échantillon de conflit résolu ->', res) except ResolverError as e: print('Erreur lors de la résolution de l échantillon de conflit :', e) # Vous pouvez intégrer ce module dans un autre système en important 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}")