パッケージ依存関係リゾルバを実装する

def resolve(requirements, package_index): """ 初期の要件とパッケージインデックスが与えられたときに、パッケージのバージョンを解決します。 requirements: "A>=1.2.0" や "B" のような要件文字列のリスト package_index: パッケージ -> { バージョン文字列: [依存関係の要件文字列] } の辞書 戻り値: パッケージ -> 解決されたバージョン文字列 をマッピングする辞書 競合が発生した場合は説明付きで ValueError を送出します。 """ import copy import re OPS = ["==", "!=", ">=", "<=", ">", "<"] def parse_version(v): # セマンティックバージョンを整数のタプルに解析します（major, minor, patch, ...） parts = tuple(int(p) for p in v.split('.')) return parts def version_cmp_key(v): return parse_version(v) def parse_requirement(req): req = req.strip() # 演算子が存在するか探す for op in OPS: if op in req: name, ver = req.split(op, 1) name = name.strip() ver = ver.strip() return name, op, ver # 演算子がない場合は任意のバージョンを意味します name = req return name.strip(), None, None def satisfies_one(ver_str, op, ver_req_str): if op is None: return True left = parse_version(ver_str) right = parse_version(ver_req_str) if op == '==': return left == right if op == '!=': return left != right if op == '>=': return left >= right if op == '<=': return left <= right if op == '>': return left > right if op == '<': return left < right return False def satisfies_all(ver_str, constraints): # constraints: op が None である可能性がある (op, ver_str) のリスト return all(satisfies_one(ver_str, op, vreq) for (op, vreq) in constraints) # 初期制約辞書を構築: パッケージ -> (op, ver) のリスト constraints = {} def add_constraint(constraints_map, pkg, op, ver): if pkg not in constraints_map: constraints_map[pkg] = [] # 同一の重複する制約を避ける if (op, ver) not in constraints_map[pkg]: constraints_map[pkg].append((op, ver)) # トップレベルの要件から初期化 for req in requirements: name, op, ver = parse_requirement(req) if name not in package_index: raise ValueError(f"パッケージ '{name}' が必要ですが、パッケージインデックスに見つかりません") add_constraint(constraints, name, op, ver) # あるパッケージの制約の下で許容されるバージョンの一覧を計算するヘルパー def allowed_versions(pkg, constraints_map): if pkg not in package_index: raise ValueError(f"パッケージ '{pkg}' がパッケージインデックスに見つかりません") cons = constraints_map.get(pkg, []) versions = list(package_index[pkg].keys()) # フィルタリング filtered = [v for v in versions if satisfies_all(v, cons)] # バージョンで降順にソート（最新を先頭） filtered.sort(key=version_cmp_key, reverse=True) return filtered # バックトラック探索 def search(resolved, constraints_map): # 制約のあるすべてのパッケージが解決済みなら、終了 to_resolve = [p for p in constraints_map.keys() if p not in resolved] if not to_resolve: return resolved # 分岐を最小化するため、候補数の最も少ないパッケージを選択 candidate_info = [] # (pkg, candidates) のリスト for pkg in to_resolve: try: cand = allowed_versions(pkg, constraints_map) except ValueError as e: # パッケージが存在しない場合 raise if not cand: # 競合: このパッケージの制約を満たすバージョンがない # 読みやすい制約文字列を構築 cons = constraints_map.get(pkg, []) cons_str = ", ".join([(op + v) if op else "any" for (op, v) in cons]) raise ValueError(f"パッケージ '{pkg}' のいかなるバージョンも次の制約を満たしません: {cons_str}") candidate_info.append((pkg, cand)) # 候補数で昇順にソート candidate_info.sort(key=lambda x: len(x[1])) pkg, candidates = candidate_info[0] # 各候補を試す（既に最新順） for ver in candidates: new_resolved = dict(resolved) new_resolved[pkg] = ver # 次のレベルのために制約をクローン new_constraints = copy.deepcopy(constraints_map) # pkg=ver を設定したとき、pkg に対する既存の制約が満たされていることを確認する必要がある if not satisfies_all(ver, new_constraints.get(pkg, [])): # 候補はフィルタ済みなので起こらないはずだが、念のためチェック continue # その依存関係を制約に追加 deps = package_index[pkg].get(ver, []) conflict = False conflict_msg = None for dep_req in deps: dep_name, dep_op, dep_ver = parse_requirement(dep_req) if dep_name not in package_index: conflict = True conflict_msg = f"'{pkg}=={ver}' は存在しないパッケージ '{dep_name}' を必要とします" break add_constraint(new_constraints, dep_name, dep_op, dep_ver) # もし dep が既に解決済みなら、一貫性を確認 if dep_name in new_resolved: assigned = new_resolved[dep_name] if not satisfies_all(assigned, new_constraints.get(dep_name, [])): conflict = True conflict_msg = (f"競合: {pkg}=={ver} は {dep_req} を必要としますが、既に解決された {dep_name}=={assigned} と互換性がありません") break if conflict: # 次の候補を試す continue # また、これらの制約を追加することで未解決の他のパッケージが候補ゼロになる可能性がある # それは再帰呼び出しで allowed_versions を計算する際に検出され、例外が発生します。 try: result = search(new_resolved, new_constraints) return result except ValueError as e: # 次の候補を試す last_err = e continue # すべての候補が失敗した場合は競合を送出します。情報的なメッセージを提供するようにする。 # pkg に対する制約の説明を作る cons = constraints_map.get(pkg, []) cons_str = ", ".join([(op + v) if op else "any" for (op, v) in cons]) raise ValueError(f"制約 {cons_str} の下でパッケージ '{pkg}' を解決できません") # 探索を開始 resolved = {} result = search(resolved, constraints) return result # Example usage (uncomment to run quick test): # if __name__ == '__main__': # index = { # "A": { # "1.0.0": ["B<2.0.0"], # "1.1.0": ["B<3.0.0"], # "1.2.0": ["C==1.0.0"] # }, # "B": { # "1.5.0": [], # "2.5.0": [] # }, # "C": { # "1.0.0": ["B>=2.0.0"], # "1.1.0": [] # } # } # print(resolve(["A>=1.1.0"], index))

import re from functools import cmp_to_key def parse_requirement(req_str): """ Parse a requirement string like 'A>=1.2.0', 'B', 'C==1.0.0' Returns (name, operator, version) where operator and version may be None. """ req_str = req_str.strip() match = re.match(r'^([A-Za-z0-9_\-\.]+)\s*(==|!=|>=|<=|>|<)\s*([0-9][A-Za-z0-9\.\-]*)$', req_str) if match: return match.group(1), match.group(2), match.group(3) # No specifier match2 = re.match(r'^([A-Za-z0-9_\-\.]+)$', req_str) if match2: return match2.group(1), None, None raise ValueError(f"Cannot parse requirement: {req_str!r}") def parse_version(version_str): """Parse a version string into a tuple of integers for comparison.""" parts = [] for part in version_str.split('.'): try: parts.append(int(part)) except ValueError: parts.append(part) return tuple(parts) def version_satisfies(version_str, operator, constraint_version_str): """Check if version_str satisfies the constraint operator+constraint_version_str.""" if operator is None: return True v = parse_version(version_str) c = parse_version(constraint_version_str) if operator == '==': return v == c elif operator == '!=': return v != c elif operator == '>=': return v >= c elif operator == '<=': return v <= c elif operator == '>': return v > c elif operator == '<': return v < c return False def get_sorted_versions(package_name, package_index): """Return versions of a package sorted from latest to oldest.""" if package_name not in package_index: return [] versions = list(package_index[package_name].keys()) versions.sort(key=lambda v: parse_version(v), reverse=True) return versions def resolve(requirements, package_index): """ Resolve package dependencies. Args: requirements: List of requirement strings (e.g., ["A>=1.2.0", "B"]) package_index: Dict mapping package names to dicts of version->dependencies Returns: Dict mapping package names to resolved version strings. Raises: ValueError: If no valid resolution exists. """ # We'll use a backtracking approach. # State: a dict of {package_name: resolved_version} # We maintain a queue of requirements to process. def backtrack(resolved, pending_requirements, visited_states=None): """ resolved: dict of {pkg_name: version_str} - already resolved packages pending_requirements: list of (name, operator, version) tuples to satisfy Returns resolved dict or raises ValueError. """ if visited_states is None: visited_states = set() # Deduplicate and check pending requirements if not pending_requirements: return resolved # Take the first pending requirement name, op, ver = pending_requirements[0] rest = pending_requirements[1:] # Check if already resolved if name in resolved: # Verify the resolved version satisfies this constraint if version_satisfies(resolved[name], op, ver): return backtrack(resolved, rest, visited_states) else: # Conflict with already resolved version raise ValueError( f"Conflict: {name}=={resolved[name]} does not satisfy {name}{op or ''}{ver or ''}" ) # Package not yet resolved - try versions from latest to oldest if name not in package_index: raise ValueError(f"Package {name!r} not found in package index") sorted_versions = get_sorted_versions(name, package_index) # Filter versions that satisfy the current constraint candidate_versions = [ v for v in sorted_versions if version_satisfies(v, op, ver) ] if not candidate_versions: raise ValueError( f"No version of {name} satisfies constraint {name}{op or ''}{ver or ''}" ) # Also filter against all other pending requirements for the same package # Collect all constraints for this package from pending_requirements same_pkg_constraints = [(n2, o2, v2) for n2, o2, v2 in rest if n2 == name] # Filter candidates against all known constraints for this package filtered_candidates = [] for v in candidate_versions: if all(version_satisfies(v, o2, v2) for n2, o2, v2 in same_pkg_constraints): filtered_candidates.append(v) if not filtered_candidates: raise ValueError( f"No version of {name} satisfies all constraints: " f"{[(name + (o2 or '') + (v2 or '')) for _, o2, v2 in same_pkg_constraints + [(name, op, ver)]]}" ) # Remove same-package constraints from rest since we'll handle them now rest_without_same = [(n2, o2, v2) for n2, o2, v2 in rest if n2 != name] last_error = None for candidate in filtered_candidates: # Try this candidate version new_resolved = dict(resolved) new_resolved[name] = candidate # Get dependencies of this version deps = package_index[name][candidate] new_pending = [] for dep_str in deps: dep_name, dep_op, dep_ver = parse_requirement(dep_str) new_pending.append((dep_name, dep_op, dep_ver)) # Add remaining requirements new_pending.extend(rest_without_same) try: result = backtrack(new_resolved, new_pending, visited_states) return result except ValueError as e: last_error = e continue if last_error: raise ValueError( f"Could not resolve {name}: tried all candidates. Last error: {last_error}" ) raise ValueError(f"Could not resolve {name}: no candidates available") # Parse initial requirements parsed_reqs = [] for req_str in requirements: name, op, ver = parse_requirement(req_str) parsed_reqs.append((name, op, ver)) return backtrack({}, parsed_reqs) # Example usage and testing if __name__ == '__main__': package_index = { "A": { "1.0.0": ["B<2.0.0"], "1.1.0": ["B<3.0.0"], "1.2.0": ["C==1.0.0"] }, "B": { "1.5.0": [], "2.5.0": [] }, "C": { "1.0.0": ["B>=2.0.0"], "1.1.0": [] } } # Test 1: A>=1.1.0 should resolve to A=1.2.0, C=1.0.0, B=2.5.0 result = resolve(["A>=1.1.0"], package_index) print("Test 1:", result) assert result == {'A': '1.2.0', 'C': '1.0.0', 'B': '2.5.0'}, f"Expected A=1.2.0, C=1.0.0, B=2.5.0, got {result}" # Test 2: A==1.1.0 should resolve to A=1.1.0, B=2.5.0 (latest B < 3.0.0) result2 = resolve(["A==1.1.0"], package_index) print("Test 2:", result2) assert result2 == {'A': '1.1.0', 'B': '2.5.0'}, f"Expected A=1.1.0, B=2.5.0, got {result2}" # Test 3: Conflict - A==1.2.0 needs C==1.0.0 which needs B>=2.0.0, but also B<2.0.0 try: result3 = resolve(["A==1.2.0", "B<2.0.0"], package_index) print("Test 3 (should have failed):", result3) except ValueError as e: print("Test 3 (expected conflict):", e) print("All tests passed!")