diff options
author | Jannis Pohlmann <jannis.pohlmann@codethink.co.uk> | 2012-04-16 17:03:53 +0100 |
---|---|---|
committer | Jannis Pohlmann <jannis.pohlmann@codethink.co.uk> | 2012-04-16 17:04:20 +0100 |
commit | 9a0976b32c8362de0ad70283f5d4ab3675706564 (patch) | |
tree | b42e2d1a9a928ed47518135cd17e87fd26d446be /morphlib/artifactresolver.py | |
parent | 31b887e4fa73920ea2c0c95160eabdc758f4fde0 (diff) | |
download | morph-9a0976b32c8362de0ad70283f5d4ab3675706564.tar.gz |
Merge DependencyResolver into ArtifactResolver.
Diffstat (limited to 'morphlib/artifactresolver.py')
-rw-r--r-- | morphlib/artifactresolver.py | 263 |
1 files changed, 220 insertions, 43 deletions
diff --git a/morphlib/artifactresolver.py b/morphlib/artifactresolver.py index 5ad6dcac..f8ae4399 100644 --- a/morphlib/artifactresolver.py +++ b/morphlib/artifactresolver.py @@ -20,6 +20,37 @@ import collections import morphlib +class MutualDependencyError(cliapp.AppException): + + def __init__(self, a, b): + cliapp.AppException.__init__( + self, 'Cyclic dependency between %s and %s detected' % (a, b)) + + +class CyclicDependencyChainError(cliapp.AppException): + + def __init__(self): + cliapp.AppException.__init__( + self, 'Cyclic dependency chain detected') + + +class DependencyOrderError(cliapp.AppException): + + def __init__(self, stratum, chunk, dependency_name): + cliapp.AppException.__init__( + self, 'In stratum %s, chunk %s references its dependency %s ' + 'before it is defined' % + (stratum.source, chunk, dependency_name)) + + +class DependencyFormatError(cliapp.AppException): + + def __init__(self, stratum, chunk): + cliapp.AppException.__init__( + self, 'In stratum %s, chunk %s uses an invalid ' + 'build-depends format' % (stratum.source, chunk)) + + class UndefinedChunkArtifactError(cliapp.AppException): '''Exception raised when non-existent artifacts are referenced. @@ -31,8 +62,8 @@ class UndefinedChunkArtifactError(cliapp.AppException): def __init__(self, parent, reference): cliapp.AppException.__init__( - self, 'Undefined chunk artifact "%s" referenced in %s' % - (reference, parent)) + self, 'Undefined chunk artifact "%s" referenced in ' + 'stratum %s' % (reference, parent)) class ArtifactResolver(object): @@ -48,69 +79,215 @@ class ArtifactResolver(object): def __init__(self, cache_key_computer): self.cache_key_computer = cache_key_computer + self._cached_artifacts = None + self._added_artifacts = None + self._source_pool = None def resolve_artifacts(self, source_pool): + self._source_pool = source_pool + self._cached_artifacts = {} + self._added_artifacts = set() + + artifacts = self._resolve_artifacts_recursively() + self._detect_cyclic_dependencies(artifacts) + return artifacts + + def _resolve_artifacts_recursively(self): artifacts = [] - roots = [x for x in source_pool if not x.dependents] - queue = collections.deque(roots) + + queue = self._create_initial_queue() while queue: source = queue.popleft() + cache_key = self.cache_key_computer.compute_key(source) + if source.morphology['kind'] == 'system': - artifact = morphlib.artifact.Artifact( + artifact = self._get_artifact( source, source.morphology['name'], cache_key) - artifacts.append(artifact) - for dependency in source.dependencies: - queue.append(dependency) + + if not artifact in self._added_artifacts: + artifacts.append(artifact) + self._added_artifacts.add(artifact) + + resolved_artifacts = self._resolve_system_dependencies( + artifact, queue) + + for artifact in resolved_artifacts: + if not artifact in self._added_artifacts: + artifacts.append(artifact) + self._added_artifacts.add(artifact) elif source.morphology['kind'] == 'stratum': - artifact = morphlib.artifact.Artifact( + artifact = self._get_artifact( source, source.morphology['name'], cache_key) - artifacts.append(artifact) - for dependency in source.dependencies: - if dependency.morphology['kind'] == 'stratum': - queue.append(dependency) - elif dependency.morphology['kind'] == 'chunk': - chunk_artifacts = self._find_required_chunk_artifacts( - source, dependency, source_pool) - artifacts.extend(chunk_artifacts) + + if not artifact in self._added_artifacts: + artifacts.append(artifact) + self._added_artifacts.add(artifact) + + resolved_artifacts = self._resolve_stratum_dependencies( + artifact, queue) + + for artifact in resolved_artifacts: + if not artifact in self._added_artifacts: + artifacts.append(artifact) + self._added_artifacts.add(artifact) elif source.morphology['kind'] == 'chunk': names = self._chunk_artifact_names(source) for name in names: - artifact = morphlib.artifact.Artifact( - source, name, cache_key) - artifacts.append(artifact) + artifact = self._get_artifact(source, name, cache_key) + if not artifact in self._added_artifacts: + artifacts.append(artifact) + self._added_artifacts.add(artifact) return artifacts - def _find_required_chunk_artifacts(self, stratum, chunk, source_pool): + def _create_initial_queue(self): + if all([x.morphology['kind'] == 'chunk' for x in self._source_pool]): + return collections.deque(self._source_pool) + else: + sources = [x for x in self._source_pool + if x.morphology['kind'] != 'chunk'] + return collections.deque(sources) + + def _get_artifact(self, source, name, cache_key): + info = (source, name, cache_key) + if info in self._cached_artifacts: + return self._cached_artifacts[info] + else: + artifact = morphlib.artifact.Artifact(info[0], info[1], info[2]) + self._cached_artifacts[info] = artifact + return artifact + + def _resolve_system_dependencies(self, system, queue): artifacts = [] - for source in stratum.morphology['sources']: - if self._source_matches_chunk(stratum, source, chunk, source_pool): - cache_key = self.cache_key_computer.compute_key(chunk) - artifact = morphlib.artifact.Artifact( - chunk, source['name'], cache_key) - artifacts.append(artifact) - return artifacts - def _source_matches_chunk(self, stratum, source, chunk, source_pool): - source_from_pool = source_pool.lookup( - source['repo'], - source['ref'], - '%s.morph' % source['morph']) + for stratum_name in system.source.morphology['strata']: + source = self._source_pool.lookup( + system.source.repo, + system.source.original_ref, + '%s.morph' % stratum_name) + + cache_key = self.cache_key_computer.compute_key(source) + stratum = self._get_artifact(source, stratum_name, cache_key) - if source_from_pool is not chunk: - return False + system.add_dependency(stratum) + queue.append(source) - chunk_names = self._chunk_artifact_names(chunk) + artifacts.append(stratum) - if source['name'] not in chunk_names: - raise UndefinedChunkArtifactError(stratum, source['name']) + return artifacts + + def _resolve_stratum_dependencies(self, stratum, queue): + artifacts = [] + + strata = [] + + if stratum.source.morphology['build-depends']: + for stratum_name in stratum.source.morphology['build-depends']: + other_source = self._source_pool.lookup( + stratum.source.repo, + stratum.source.original_ref, + '%s.morph' % stratum_name) + + cache_key = self.cache_key_computer.compute_key(other_source) + other_stratum = self._get_artifact( + other_source, stratum_name, cache_key) + + strata.append(other_stratum) + + artifacts.append(other_stratum) + + if other_stratum.depends_on(stratum): + raise MutualDependencyError(stratum, other_stratum) - return True + stratum.add_dependency(other_stratum) + queue.append(other_source) - def _chunk_artifact_names(self, chunk): - if 'artifacts' in chunk.morphology: - return sorted(chunk.morphology['artifacts'].keys()) + chunk_artifacts = [] + processed_artifacts = [] + name_to_processed_artifact = {} + + for info in stratum.source.morphology['sources']: + chunk_source = self._source_pool.lookup( + info['repo'], + info['ref'], + '%s.morph' % info['morph']) + + possible_names = self._chunk_artifact_names(chunk_source) + if not info['name'] in possible_names: + raise UndefinedChunkArtifactError(stratum.source, info['name']) + + cache_key = self.cache_key_computer.compute_key(chunk_source) + + chunk_artifact = self._get_artifact( + chunk_source, info['name'], cache_key) + chunk_artifacts.append(chunk_artifact) + + artifacts.append(chunk_artifact) + + stratum.add_dependency(chunk_artifact) + + for other_stratum in strata: + chunk_artifact.add_dependency(other_stratum) + + build_depends = info.get('build-depends', None) + + if build_depends is None: + for earlier_artifact in processed_artifacts: + if earlier_artifact is chunk_artifact: + continue + if earlier_artifact.depends_on(chunk_artifact): + raise MutualDependencyError( + chunk_artifact, earlier_artifact) + chunk_artifact.add_dependency(earlier_artifact) + elif isinstance(build_depends, list): + for name in build_depends: + other_artifact = name_to_processed_artifact.get(name, None) + if other_artifact is chunk_artifact: + continue + if other_artifact: + chunk_artifact.add_dependency(other_artifact) + else: + raise DependencyOrderError( + stratum, info['name'], name) + else: + raise DependencyFormatError(stratum, info['name']) + processed_artifacts.append(chunk_artifact) + name_to_processed_artifact[info['name']] = chunk_artifact + + return artifacts + + def _chunk_artifact_names(self, source): + if 'artifacts' in source.morphology: + return sorted(source.morphology['artifacts'].keys()) else: - return [chunk.morphology['name']] + return [source.morphology['name']] + + def _detect_cyclic_dependencies(self, artifacts): + # FIXME This is not well tested and might be incorrect. Better + # something based on + # http://stackoverflow.com/questions/546655/finding-all-cycles-in-graph + + visited = set() + explored = set() + parent = {} + + roots = [] + for artifact in artifacts: + if len(artifact.dependents) == 0: + roots.append(artifact) + parent[artifact] = None + + stack = collections.deque(roots) + while stack: + artifact = stack.popleft() + visited.add(artifact) + for dependency in artifact.dependencies: + if not (artifact, dependency) in explored: + explored.add((artifact, dependency)) + parent[dependency] = artifact + if not dependency in visited: + stack.appendleft(dependency) + else: + raise CyclicDependencyChainError() |