diff options
-rw-r--r-- | morphlib/artifact.py | 13 | ||||
-rw-r--r-- | morphlib/artifact_tests.py | 25 | ||||
-rw-r--r-- | morphlib/artifactresolver.py | 263 | ||||
-rw-r--r-- | morphlib/artifactresolver_tests.py | 520 | ||||
-rw-r--r-- | morphlib/dependencyresolver.py | 158 | ||||
-rw-r--r-- | morphlib/dependencyresolver_tests.py | 867 |
6 files changed, 742 insertions, 1104 deletions
diff --git a/morphlib/artifact.py b/morphlib/artifact.py index 9403f081..830ee1ac 100644 --- a/morphlib/artifact.py +++ b/morphlib/artifact.py @@ -20,8 +20,21 @@ class Artifact(object): self.source = source self.name = name self.cache_key = cache_key + self.dependencies = [] + self.dependents = [] + + def add_dependency(self, artifact): + '''Add ``artifact`` to the dependency list.''' + if artifact not in self.dependencies: + self.dependencies.append(artifact) + artifact.dependents.append(self) + + def depends_on(self, artifact): + '''Do we depend on ``artifact``?''' + return artifact in self.dependencies def __str__(self): # pragma: no cover return '%s.%s.%s' % (self.cache_key, self.source.morphology['kind'], self.name) + diff --git a/morphlib/artifact_tests.py b/morphlib/artifact_tests.py index 49f8e17f..faeef879 100644 --- a/morphlib/artifact_tests.py +++ b/morphlib/artifact_tests.py @@ -46,6 +46,8 @@ class ArtifactTests(unittest.TestCase): self.artifact_name = 'chunk-runtime' self.artifact = morphlib.artifact.Artifact( self.source, self.artifact_name, self.cache_key) + self.other = morphlib.artifact.Artifact( + self.source, self.artifact_name, self.cache_key) def test_constructor_sets_source(self): self.assertEqual(self.artifact.source, self.source) @@ -55,3 +57,26 @@ class ArtifactTests(unittest.TestCase): def test_constructor_sets_cache_key(self): self.assertEqual(self.artifact.cache_key, self.cache_key) + + def test_sets_dependencies_to_empty(self): + self.assertEqual(self.artifact.dependencies, []) + + def test_sets_dependents_to_empty(self): + self.assertEqual(self.artifact.dependents, []) + + def test_does_not_depend_on_other_initially(self): + self.assertFalse(self.artifact.depends_on(self.other)) + + def test_adds_dependency(self): + self.artifact.add_dependency(self.other) + self.assertEqual(self.artifact.dependencies, [self.other]) + self.assertEqual(self.other.dependents, [self.artifact]) + self.assertTrue(self.artifact.depends_on(self.other)) + + def test_does_not_add_dependency_twice(self): + self.artifact.add_dependency(self.other) + self.artifact.add_dependency(self.other) + self.assertEqual(self.artifact.dependencies, [self.other]) + self.assertEqual(self.other.dependents, [self.artifact]) + self.assertTrue(self.artifact.depends_on(self.other)) + 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() diff --git a/morphlib/artifactresolver_tests.py b/morphlib/artifactresolver_tests.py index e31f58d5..68a2c886 100644 --- a/morphlib/artifactresolver_tests.py +++ b/morphlib/artifactresolver_tests.py @@ -95,8 +95,6 @@ class ArtifactResolverTests(unittest.TestCase): def setUp(self): self.cache_key_computer = FakeCacheKeyComputer() - self.dependency_resolver = \ - morphlib.dependencyresolver.DependencyResolver() self.resolver = morphlib.artifactresolver.ArtifactResolver( self.cache_key_computer) @@ -120,6 +118,8 @@ class ArtifactResolverTests(unittest.TestCase): self.assertEqual(artifacts[0].source, source) self.assertEqual(artifacts[0].name, 'chunk') self.assertEqual(artifacts[0].cache_key, 'CHUNK') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, []) def test_resolve_single_chunk_with_one_artifact(self): pool = morphlib.sourcepool.SourcePool() @@ -135,6 +135,8 @@ class ArtifactResolverTests(unittest.TestCase): self.assertEqual(artifacts[0].source, source) self.assertEqual(artifacts[0].name, 'chunk-runtime') self.assertEqual(artifacts[0].cache_key, 'CHUNK') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, []) def test_resolve_single_chunk_with_two_artifact(self): pool = morphlib.sourcepool.SourcePool() @@ -151,10 +153,58 @@ class ArtifactResolverTests(unittest.TestCase): self.assertEqual(artifacts[0].source, source) self.assertEqual(artifacts[0].name, 'chunk-devel') self.assertEqual(artifacts[0].cache_key, 'CHUNK') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, []) self.assertEqual(artifacts[1].source, source) self.assertEqual(artifacts[1].name, 'chunk-runtime') self.assertEqual(artifacts[1].cache_key, 'CHUNK') + self.assertEqual(artifacts[1].dependencies, []) + self.assertEqual(artifacts[1].dependents, []) + + def test_resolve_a_single_empty_stratum(self): + pool = morphlib.sourcepool.SourcePool() + + morph = morphlib.morph2.Morphology( + ''' + { + "name": "foo", + "kind": "stratum" + } + ''') + stratum = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'foo.morph') + pool.add(stratum) + + artifacts = self.resolver.resolve_artifacts(pool) + + self.assertEqual(artifacts[0].source, stratum) + self.assertEqual(artifacts[0].name, 'foo') + self.assertEqual(artifacts[0].cache_key, 'FOO') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, []) + + def test_resolve_a_single_empty_system(self): + pool = morphlib.sourcepool.SourcePool() + + morph = morphlib.morph2.Morphology( + ''' + { + "name": "foo", + "kind": "system" + } + ''') + system = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'foo.morph') + pool.add(system) + + artifacts = self.resolver.resolve_artifacts(pool) + + self.assertEqual(artifacts[0].source, system) + self.assertEqual(artifacts[0].name, 'foo') + self.assertEqual(artifacts[0].cache_key, 'FOO') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, []) def test_resolve_stratum_and_chunk_with_no_subartifacts(self): pool = morphlib.sourcepool.SourcePool() @@ -170,8 +220,6 @@ class ArtifactResolverTests(unittest.TestCase): 'repo', 'ref', 'sha1', morph, 'stratum.morph') pool.add(stratum) - self.dependency_resolver.resolve_dependencies(pool) - artifacts = self.resolver.resolve_artifacts(pool) self.assertEqual(len(artifacts), 2) @@ -179,10 +227,14 @@ class ArtifactResolverTests(unittest.TestCase): self.assertEqual(artifacts[0].source, stratum) self.assertEqual(artifacts[0].name, 'stratum') self.assertEqual(artifacts[0].cache_key, 'STRATUM') + self.assertEqual(artifacts[0].dependencies, [artifacts[1]]) + self.assertEqual(artifacts[0].dependents, []) self.assertEqual(artifacts[1].source, chunk) self.assertEqual(artifacts[1].name, 'chunk') self.assertEqual(artifacts[1].cache_key, 'CHUNK') + self.assertEqual(artifacts[1].dependencies, []) + self.assertEqual(artifacts[1].dependents, [artifacts[0]]) def test_resolve_stratum_and_chunk_with_two_subartifacts(self): pool = morphlib.sourcepool.SourcePool() @@ -201,8 +253,6 @@ class ArtifactResolverTests(unittest.TestCase): 'repo', 'ref', 'sha1', morph, 'stratum.morph') pool.add(stratum) - self.dependency_resolver.resolve_dependencies(pool) - artifacts = self.resolver.resolve_artifacts(pool) self.assertEqual(len(artifacts), 3) @@ -210,14 +260,21 @@ class ArtifactResolverTests(unittest.TestCase): self.assertEqual(artifacts[0].source, stratum) self.assertEqual(artifacts[0].name, 'stratum') self.assertEqual(artifacts[0].cache_key, 'STRATUM') + self.assertEqual(artifacts[0].dependencies, + [artifacts[1], artifacts[2]]) + self.assertEqual(artifacts[0].dependents, []) self.assertEqual(artifacts[1].source, chunk) self.assertEqual(artifacts[1].name, 'chunk-devel') self.assertEqual(artifacts[1].cache_key, 'CHUNK') + self.assertEqual(artifacts[1].dependencies, []) + self.assertEqual(artifacts[1].dependents, [artifacts[0], artifacts[2]]) self.assertEqual(artifacts[2].source, chunk) self.assertEqual(artifacts[2].name, 'chunk-runtime') self.assertEqual(artifacts[2].cache_key, 'CHUNK') + self.assertEqual(artifacts[2].dependencies, [artifacts[1]]) + self.assertEqual(artifacts[2].dependents, [artifacts[0]]) def test_resolve_stratum_and_chunk_with_one_used_subartifacts(self): pool = morphlib.sourcepool.SourcePool() @@ -235,8 +292,6 @@ class ArtifactResolverTests(unittest.TestCase): 'repo', 'ref', 'sha1', morph, 'stratum.morph') pool.add(stratum) - self.dependency_resolver.resolve_dependencies(pool) - artifacts = self.resolver.resolve_artifacts(pool) self.assertEqual(len(artifacts), 2) @@ -244,10 +299,14 @@ class ArtifactResolverTests(unittest.TestCase): self.assertEqual(artifacts[0].source, stratum) self.assertEqual(artifacts[0].name, 'stratum') self.assertEqual(artifacts[0].cache_key, 'STRATUM') + self.assertEqual(artifacts[0].dependencies, [artifacts[1]]) + self.assertEqual(artifacts[0].dependents, []) self.assertEqual(artifacts[1].source, chunk) self.assertEqual(artifacts[1].name, 'chunk-runtime') self.assertEqual(artifacts[1].cache_key, 'CHUNK') + self.assertEqual(artifacts[1].dependencies, []) + self.assertEqual(artifacts[1].dependents, [artifacts[0]]) def test_resolving_two_different_chunk_artifacts_in_a_stratum(self): pool = morphlib.sourcepool.SourcePool() @@ -271,8 +330,6 @@ class ArtifactResolverTests(unittest.TestCase): 'repo', 'ref', 'sha1', morph, 'stratum.morph') pool.add(stratum) - self.dependency_resolver.resolve_dependencies(pool) - artifacts = self.resolver.resolve_artifacts(pool) self.assertEqual(len(artifacts), 3) @@ -280,14 +337,21 @@ class ArtifactResolverTests(unittest.TestCase): self.assertEqual(artifacts[0].source, stratum) self.assertEqual(artifacts[0].name, 'stratum') self.assertEqual(artifacts[0].cache_key, 'STRATUM') + self.assertEqual(artifacts[0].dependencies, + [artifacts[1], artifacts[2]]) + self.assertEqual(artifacts[0].dependents, []) self.assertEqual(artifacts[1].source, foo_chunk) self.assertEqual(artifacts[1].name, 'foo') self.assertEqual(artifacts[1].cache_key, 'FOO') + self.assertEqual(artifacts[1].dependencies, []) + self.assertEqual(artifacts[1].dependents, [artifacts[0], artifacts[2]]) self.assertEqual(artifacts[2].source, bar_chunk) self.assertEqual(artifacts[2].name, 'bar') self.assertEqual(artifacts[2].cache_key, 'BAR') + self.assertEqual(artifacts[2].dependencies, [artifacts[1]]) + self.assertEqual(artifacts[2].dependents, [artifacts[0]]) def test_resolving_artifacts_for_a_chain_of_two_strata(self): pool = morphlib.sourcepool.SourcePool() @@ -302,33 +366,88 @@ class ArtifactResolverTests(unittest.TestCase): 'repo', 'ref', 'sha1', morph, 'stratum2.morph') pool.add(stratum2) - self.dependency_resolver.resolve_dependencies(pool) - artifacts = self.resolver.resolve_artifacts(pool) self.assertEqual(len(artifacts), 2) - self.assertEqual(artifacts[0].source, stratum2) - self.assertEqual(artifacts[0].name, 'stratum2') - self.assertEqual(artifacts[0].cache_key, 'STRATUM2') + self.assertEqual(artifacts[0].source, stratum1) + self.assertEqual(artifacts[0].name, 'stratum1') + self.assertEqual(artifacts[0].cache_key, 'STRATUM1') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, [artifacts[1]]) - self.assertEqual(artifacts[1].source, stratum1) - self.assertEqual(artifacts[1].name, 'stratum1') - self.assertEqual(artifacts[1].cache_key, 'STRATUM1') + self.assertEqual(artifacts[1].source, stratum2) + self.assertEqual(artifacts[1].name, 'stratum2') + self.assertEqual(artifacts[1].cache_key, 'STRATUM2') + self.assertEqual(artifacts[1].dependencies, [artifacts[0]]) + self.assertEqual(artifacts[1].dependents, []) - def test_resolving_artifacts_for_a_system_with_two_strata(self): + def test_resolving_with_a_stratum_and_chunk_dependency_mix(self): pool = morphlib.sourcepool.SourcePool() - + morph = FakeStratumMorphology('stratum1') stratum1 = morphlib.source.Source( - 'repo', 'ref', 'sha1', morph, 'stratum1.morph') + 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') pool.add(stratum1) - morph = FakeStratumMorphology('stratum2', [], ['stratum1']) + morph = FakeStratumMorphology( + 'stratum2', [ + ('chunk1', 'chunk1', 'repo', 'original/ref'), + ('chunk2', 'chunk2', 'repo', 'original/ref') + ], ['stratum1']) stratum2 = morphlib.source.Source( - 'repo', 'ref', 'sha1', morph, 'stratum2.morph') + 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') pool.add(stratum2) + morph = FakeChunkMorphology('chunk1') + chunk1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') + pool.add(chunk1) + + morph = FakeChunkMorphology('chunk2') + chunk2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') + pool.add(chunk2) + + artifacts = self.resolver.resolve_artifacts(pool) + + self.assertEqual(len(artifacts), 4) + + self.assertEqual(artifacts[0].source, stratum1) + self.assertEqual(artifacts[0].name, 'stratum1') + self.assertEqual(artifacts[0].cache_key, 'STRATUM1') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, + [artifacts[1], artifacts[2], artifacts[3]]) + + self.assertEqual(artifacts[1].source, stratum2) + self.assertEqual(artifacts[1].name, 'stratum2') + self.assertEqual(artifacts[1].cache_key, 'STRATUM2') + self.assertEqual(artifacts[1].dependencies, + [artifacts[0], artifacts[2], artifacts[3]]) + self.assertEqual(artifacts[1].dependents, []) + + self.assertEqual(artifacts[2].source, chunk1) + self.assertEqual(artifacts[2].name, 'chunk1') + self.assertEqual(artifacts[2].cache_key, 'CHUNK1') + self.assertEqual(artifacts[2].dependencies, [artifacts[0]]) + self.assertEqual(artifacts[2].dependents, [artifacts[1], artifacts[3]]) + + self.assertEqual(artifacts[3].source, chunk2) + self.assertEqual(artifacts[3].name, 'chunk2') + self.assertEqual(artifacts[3].cache_key, 'CHUNK2') + self.assertEqual(artifacts[3].dependencies, + [artifacts[0], artifacts[2]]) + self.assertEqual(artifacts[3].dependents, [artifacts[1]]) + + def test_resolving_artifacts_for_a_system_with_two_strata(self): + pool = morphlib.sourcepool.SourcePool() + + morph = FakeStratumMorphology('stratum1') + stratum1 = morphlib.source.Source( + 'repo', 'ref', 'sha1', morph, 'stratum1.morph') + pool.add(stratum1) + morph = morphlib.morph2.Morphology( ''' { @@ -344,27 +463,116 @@ class ArtifactResolverTests(unittest.TestCase): 'repo', 'ref', 'sha1', morph, 'system.morph') pool.add(system) - self.dependency_resolver.resolve_dependencies(pool) + morph = FakeStratumMorphology('stratum2', [], ['stratum1']) + stratum2 = morphlib.source.Source( + 'repo', 'ref', 'sha1', morph, 'stratum2.morph') + pool.add(stratum2) artifacts = self.resolver.resolve_artifacts(pool) - self.assertEqual(len(artifacts), 4) + self.assertEqual(len(artifacts), 3) - self.assertEqual(artifacts[0].source, system) - self.assertEqual(artifacts[0].name, 'system') - self.assertEqual(artifacts[0].cache_key, 'SYSTEM') + self.assertEqual(artifacts[0].source, stratum1) + self.assertEqual(artifacts[0].name, 'stratum1') + self.assertEqual(artifacts[0].cache_key, 'STRATUM1') + self.assertEqual(artifacts[0].dependencies, []) + self.assertEqual(artifacts[0].dependents, [artifacts[1], artifacts[2]]) - self.assertEqual(artifacts[1].source, stratum1) - self.assertEqual(artifacts[1].name, 'stratum1') - self.assertEqual(artifacts[1].cache_key, 'STRATUM1') + self.assertEqual(artifacts[1].source, system) + self.assertEqual(artifacts[1].name, 'system') + self.assertEqual(artifacts[1].cache_key, 'SYSTEM') + self.assertEqual(artifacts[1].dependencies, + [artifacts[0], artifacts[2]]) + self.assertEqual(artifacts[1].dependents, []) self.assertEqual(artifacts[2].source, stratum2) self.assertEqual(artifacts[2].name, 'stratum2') self.assertEqual(artifacts[2].cache_key, 'STRATUM2') + self.assertEqual(artifacts[2].dependencies, [artifacts[0]]) + self.assertEqual(artifacts[2].dependents, [artifacts[1]]) - self.assertEqual(artifacts[3].source, stratum1) - self.assertEqual(artifacts[3].name, 'stratum1') - self.assertEqual(artifacts[3].cache_key, 'STRATUM1') + def test_resolving_stratum_with_explicit_chunk_dependencies(self): + pool = morphlib.sourcepool.SourcePool() + + morph = morphlib.morph2.Morphology( + ''' + { + "name": "stratum", + "kind": "stratum", + "sources": [ + { + "name": "chunk1", + "repo": "repo", + "ref": "original/ref", + "build-depends": [] + }, + { + "name": "chunk2", + "repo": "repo", + "ref": "original/ref", + "build-depends": [] + }, + { + "name": "chunk3", + "repo": "repo", + "ref": "original/ref", + "build-depends": [ + "chunk1", + "chunk2" + ] + } + ] + } + ''') + stratum = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') + pool.add(stratum) + + morph = FakeChunkMorphology('chunk1') + chunk1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') + pool.add(chunk1) + + morph = FakeChunkMorphology('chunk2') + chunk2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') + pool.add(chunk2) + + morph = FakeChunkMorphology('chunk3') + chunk3 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk3.morph') + pool.add(chunk3) + + artifacts = self.resolver.resolve_artifacts(pool) + + self.assertEqual(len(artifacts), 4) + + self.assertEqual(artifacts[0].source, stratum) + self.assertEqual(artifacts[0].name, 'stratum') + self.assertEqual(artifacts[0].cache_key, 'STRATUM') + self.assertEqual(artifacts[0].dependencies, + [artifacts[1], artifacts[2], artifacts[3]]) + self.assertEqual(artifacts[0].dependents, []) + + self.assertEqual(artifacts[1].source, chunk1) + self.assertEqual(artifacts[1].name, 'chunk1') + self.assertEqual(artifacts[1].cache_key, 'CHUNK1') + self.assertEqual(artifacts[1].dependencies, []) + self.assertEqual(artifacts[1].dependents, + [artifacts[0], artifacts[3]]) + + self.assertEqual(artifacts[2].source, chunk2) + self.assertEqual(artifacts[2].name, 'chunk2') + self.assertEqual(artifacts[2].cache_key, 'CHUNK2') + self.assertEqual(artifacts[2].dependencies, []) + self.assertEqual(artifacts[2].dependents, [artifacts[0], artifacts[3]]) + + self.assertEqual(artifacts[3].source, chunk3) + self.assertEqual(artifacts[3].name, 'chunk3') + self.assertEqual(artifacts[3].cache_key, 'CHUNK3') + self.assertEqual(artifacts[3].dependencies, + [artifacts[1], artifacts[2]]) + self.assertEqual(artifacts[3].dependents, [artifacts[0]]) def test_detection_of_invalid_chunk_artifact_references(self): pool = morphlib.sourcepool.SourcePool() @@ -382,8 +590,248 @@ class ArtifactResolverTests(unittest.TestCase): 'repo', 'ref', 'sha1', morph, 'stratum.morph') pool.add(stratum) - self.dependency_resolver.resolve_dependencies(pool) - self.assertRaises( morphlib.artifactresolver.UndefinedChunkArtifactError, self.resolver.resolve_artifacts, pool) + + def test_detection_of_mutual_dependency_between_two_strata(self): + pool = morphlib.sourcepool.SourcePool() + + morph = FakeStratumMorphology('stratum1', [], ['stratum2']) + stratum1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') + pool.add(stratum1) + + morph = FakeStratumMorphology('stratum2', [], ['stratum1']) + stratum2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') + pool.add(stratum2) + + self.assertRaises(morphlib.artifactresolver.MutualDependencyError, + self.resolver.resolve_artifacts, pool) + + def test_detection_of_mutual_dependency_between_consecutive_chunks(self): + pool = morphlib.sourcepool.SourcePool() + + morph = FakeStratumMorphology( + 'stratum1', [ + ('chunk1', 'chunk1', 'repo', 'original/ref'), + ('chunk2', 'chunk2', 'repo', 'original/ref') + ], []) + stratum1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') + pool.add(stratum1) + + morph = FakeStratumMorphology( + 'stratum2', [ + ('chunk2', 'chunk2', 'repo', 'original/ref'), + ('chunk1', 'chunk1', 'repo', 'original/ref') + ], ['stratum1']) + stratum2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') + pool.add(stratum2) + + morph = FakeChunkMorphology('chunk1') + chunk1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') + pool.add(chunk1) + + morph = FakeChunkMorphology('chunk2') + chunk2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') + pool.add(chunk2) + + self.assertRaises(morphlib.artifactresolver.MutualDependencyError, + self.resolver.resolve_artifacts, pool) + + def test_graceful_handling_of_self_dependencies_of_chunks(self): + pool = morphlib.sourcepool.SourcePool() + + morph = morphlib.morph2.Morphology( + ''' + { + "name": "stratum", + "kind": "stratum", + "sources": [ + { + "name": "chunk", + "repo": "repo", + "ref": "original/ref" + }, + { + "name": "chunk", + "repo": "repo", + "ref": "original/ref" + }, + { + "name": "chunk", + "repo": "repo", + "ref": "original/ref", + "build-depends": [ + "chunk" + ] + } + ] + } + ''') + stratum = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') + pool.add(stratum) + + morph = FakeChunkMorphology('chunk') + chunk = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk.morph') + pool.add(chunk) + + artifacts = self.resolver.resolve_artifacts(pool) + + self.assertEqual(len(artifacts), 2) + + self.assertEqual(artifacts[0].source, stratum) + self.assertEqual(artifacts[0].name, 'stratum') + self.assertEqual(artifacts[0].cache_key, 'STRATUM') + self.assertEqual(artifacts[0].dependencies, [artifacts[1]]) + self.assertEqual(artifacts[0].dependents, []) + + self.assertEqual(artifacts[1].source, chunk) + self.assertEqual(artifacts[1].name, 'chunk') + self.assertEqual(artifacts[1].cache_key, 'CHUNK') + self.assertEqual(artifacts[1].dependencies, []) + self.assertEqual(artifacts[1].dependents, [artifacts[0]]) + + def test_detection_of_cyclic_chunk_dependency_chain(self): + pool = morphlib.sourcepool.SourcePool() + + morph = morphlib.morph2.Morphology( + ''' + { + "name": "stratum1", + "kind": "stratum", + "sources": [ + { + "name": "chunk1", + "repo": "repo", + "ref": "original/ref" + }, + { + "name": "chunk2", + "repo": "repo", + "ref": "original/ref", + "build-depends": [ + "chunk1" + ] + }, + { + "name": "chunk3", + "repo": "repo", + "ref": "original/ref", + "build-depends": [ + "chunk2" + ] + } + ] + } + ''') + stratum1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') + pool.add(stratum1) + + morph = FakeStratumMorphology( + 'stratum2', [ + ('chunk3', 'chunk3', 'repo', 'original/ref'), + ('chunk1', 'chunk1', 'repo', 'original/ref') + ], ['stratum1']) + stratum2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') + pool.add(stratum2) + + morph = FakeChunkMorphology('chunk1') + chunk1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') + pool.add(chunk1) + + morph = FakeChunkMorphology('chunk2') + chunk2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') + pool.add(chunk2) + + morph = FakeChunkMorphology('chunk3') + chunk3 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk3.morph') + pool.add(chunk3) + + self.assertRaises( + morphlib.artifactresolver.CyclicDependencyChainError, + self.resolver.resolve_artifacts, pool) + + def test_detection_of_chunk_dependencies_in_invalid_order(self): + pool = morphlib.sourcepool.SourcePool() + + morph = morphlib.morph2.Morphology( + ''' + { + "name": "stratum", + "kind": "stratum", + "sources": [ + { + "name": "chunk1", + "repo": "repo", + "ref": "original/ref", + "build-depends": [ + "chunk2" + ] + }, + { + "name": "chunk2", + "repo": "repo", + "ref": "original/ref" + } + ] + } + ''') + stratum = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') + pool.add(stratum) + + morph = FakeChunkMorphology('chunk1') + chunk1 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') + pool.add(chunk1) + + morph = FakeChunkMorphology('chunk2') + chunk2 = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') + pool.add(chunk2) + + self.assertRaises(morphlib.artifactresolver.DependencyOrderError, + self.resolver.resolve_artifacts, pool) + + def test_detection_of_invalid_build_depends_format(self): + pool = morphlib.sourcepool.SourcePool() + + morph = morphlib.morph2.Morphology( + ''' + { + "name": "stratum", + "kind": "stratum", + "sources": [ + { + "name": "chunk", + "repo": "repo", + "ref": "original/ref", + "build-depends": "whatever" + } + ] + } + ''') + stratum = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') + pool.add(stratum) + + morph = FakeChunkMorphology('chunk') + chunk = morphlib.source.Source( + 'repo', 'original/ref', 'sha1', morph, 'chunk.morph') + pool.add(chunk) + + self.assertRaises(morphlib.artifactresolver.DependencyFormatError, + self.resolver.resolve_artifacts, pool) diff --git a/morphlib/dependencyresolver.py b/morphlib/dependencyresolver.py deleted file mode 100644 index 0bf18ded..00000000 --- a/morphlib/dependencyresolver.py +++ /dev/null @@ -1,158 +0,0 @@ -# Copyright (C) 2012 Codethink Limited -# -# This program is free software; you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation; version 2 of the License. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License along -# with this program; if not, write to the Free Software Foundation, Inc., -# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - - -import cliapp -import collections - - -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, 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, chunk)) - - -class DependencyResolver(object): - - def resolve_dependencies(self, source_pool): - queue = collections.deque(source_pool) - while queue: - source = queue.popleft() - - if source.morphology['kind'] == 'system': - self._resolve_system_dependencies(source, queue, source_pool) - elif source.morphology['kind'] == 'stratum': - self._resolve_stratum_dependencies(source, queue, source_pool) - - self._detect_cyclic_dependencies(source_pool) - - def _resolve_system_dependencies(self, system, queue, source_pool): - for stratum_name in system.morphology['strata']: - stratum = source_pool.lookup( - system.repo, - system.original_ref, - '%s.morph' % stratum_name) - - system.add_dependency(stratum) - queue.append(stratum) - - def _resolve_stratum_dependencies(self, stratum, queue, source_pool): - strata = [] - - if stratum.morphology['build-depends']: - for stratum_name in stratum.morphology['build-depends']: - other_stratum = source_pool.lookup( - stratum.repo, - stratum.original_ref, - '%s.morph' % stratum_name) - strata.append(other_stratum) - - if other_stratum.depends_on(stratum): - raise MutualDependencyError(stratum, other_stratum) - - stratum.add_dependency(other_stratum) - queue.append(other_stratum) - - chunks = [] - processed_chunks = [] - name_to_processed_chunk = {} - - for info in stratum.morphology['sources']: - chunk = source_pool.lookup( - info['repo'], - info['ref'], - '%s.morph' % info['morph']) - chunks.append(chunk) - - stratum.add_dependency(chunk) - - for other_stratum in strata: - chunk.add_dependency(other_stratum) - - build_depends = info.get('build-depends', None) - - if build_depends is None: - for earlier_chunk in processed_chunks: - if earlier_chunk is chunk: - continue - if earlier_chunk.depends_on(chunk): - raise MutualDependencyError(chunk, earlier_chunk) - chunk.add_dependency(earlier_chunk) - elif isinstance(build_depends, list): - for name in build_depends: - other_chunk = name_to_processed_chunk.get(name, None) - if other_chunk is chunk: - continue - if other_chunk: - chunk.add_dependency(other_chunk) - else: - raise DependencyOrderError(stratum, info['name'], name) - else: - raise DependencyFormatError(stratum, info['name']) - processed_chunks.append(chunk) - name_to_processed_chunk[info['name']] = chunk - - def _detect_cyclic_dependencies(self, source_pool): - # 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 source in source_pool: - if len(source.dependents) == 0: - roots.append(source) - parent[source] = None - - stack = collections.deque(roots) - while stack: - source = stack.popleft() - visited.add(source) - - for dependency in source.dependencies: - if not (source, dependency) in explored: - explored.add((source, dependency)) - parent[dependency] = source - if not dependency in visited: - stack.appendleft(dependency) - else: - raise CyclicDependencyChainError() diff --git a/morphlib/dependencyresolver_tests.py b/morphlib/dependencyresolver_tests.py deleted file mode 100644 index c2d95cd1..00000000 --- a/morphlib/dependencyresolver_tests.py +++ /dev/null @@ -1,867 +0,0 @@ -# Copyright (C) 2012 Codethink Limited -# -# This program is free software; you can redistribute it and/or modify -# it under the terms of the GNU General Public License as published by -# the Free Software Foundation; version 2 of the License. -# -# This program is distributed in the hope that it will be useful, -# but WITHOUT ANY WARRANTY; without even the implied warranty of -# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -# GNU General Public License for more details. -# -# You should have received a copy of the GNU General Public License along -# with this program; if not, write to the Free Software Foundation, Inc., -# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. - - -import unittest - -import morphlib - - -class DependencyResolverTests(unittest.TestCase): - - def setUp(self): - self.resolver = morphlib.dependencyresolver.DependencyResolver() - - def test_create_empty_build_order_for_empty_pool(self): - pool = morphlib.sourcepool.SourcePool() - self.resolver.resolve_dependencies(pool) - - def test_with_a_single_chunk(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "foo", - "kind": "chunk", - "artifacts": { - "foo-runtime": [ "usr/bin" ], - "foo-devel": [ "usr/lib" ] - } - } - ''') - chunk = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'foo.morph') - pool.add(chunk) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(chunk.dependencies, []) - self.assertEqual(chunk.dependents, []) - - def test_with_a_single_empty_stratum(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "foo", - "kind": "stratum" - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'foo.morph') - pool.add(stratum) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(stratum.dependencies, []) - self.assertEqual(stratum.dependents, []) - - def test_with_a_single_empty_system(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "foo", - "kind": "system" - } - ''') - system = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'foo.morph') - pool.add(system) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(system.dependencies, []) - self.assertEqual(system.dependents, []) - - def test_with_a_one_chunk_stratum(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum", - "kind": "stratum", - "sources": [ - { - "name": "chunk", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') - pool.add(stratum) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk", - "kind": "chunk", - "artifacts": { - "foo-runtime": [ "usr/bin" ], - "foo-devel": [ "usr/lib" ] - } - } - ''') - chunk = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk.morph') - pool.add(chunk) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(chunk.dependencies, []) - self.assertEqual(chunk.dependents, [stratum]) - self.assertEqual(stratum.dependencies, [chunk]) - self.assertEqual(stratum.dependents, []) - - def test_with_a_one_chunk_artifact_stratum(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum", - "kind": "stratum", - "sources": [ - { - "name": "chunk-runtime", - "morph": "chunk", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') - pool.add(stratum) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk", - "kind": "chunk", - "artifacts": { - "foo-runtime": [ "usr/bin" ], - "foo-devel": [ "usr/lib" ] - } - } - ''') - chunk = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk.morph') - pool.add(chunk) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(chunk.dependencies, []) - self.assertEqual(chunk.dependents, [stratum]) - self.assertEqual(stratum.dependencies, [chunk]) - self.assertEqual(stratum.dependents, []) - - def test_with_stratum_and_implicit_dependencies(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum", - "kind": "stratum", - "sources": [ - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref" - }, - { - "name": "chunk2", - "repo": "repo", - "ref": "original/ref" - }, - { - "name": "chunk3", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') - pool.add(stratum) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk1", - "kind": "chunk" - } - ''') - chunk1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') - pool.add(chunk1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk2", - "kind": "chunk" - } - ''') - chunk2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') - pool.add(chunk2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk3", - "kind": "chunk" - } - ''') - chunk3 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk3.morph') - pool.add(chunk3) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(chunk1.dependencies, []) - self.assertEqual(chunk1.dependents, [stratum, chunk2, chunk3]) - self.assertEqual(chunk2.dependencies, [chunk1]) - self.assertEqual(chunk2.dependents, [stratum, chunk3]) - self.assertEqual(chunk3.dependencies, [chunk1, chunk2]) - self.assertEqual(chunk3.dependents, [stratum]) - self.assertEqual(stratum.dependencies, [chunk1, chunk2, chunk3]) - self.assertEqual(stratum.dependents, []) - - def test_with_explicit_dependencies(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum", - "kind": "stratum", - "sources": [ - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref", - "build-depends": [] - }, - { - "name": "chunk2", - "repo": "repo", - "ref": "original/ref", - "build-depends": [] - }, - { - "name": "chunk3", - "repo": "repo", - "ref": "original/ref", - "build-depends": [ - "chunk1", - "chunk2" - ] - } - ] - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') - pool.add(stratum) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk1", - "kind": "chunk" - } - ''') - chunk1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') - pool.add(chunk1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk2", - "kind": "chunk" - } - ''') - chunk2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') - pool.add(chunk2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk3", - "kind": "chunk" - } - ''') - chunk3 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk3.morph') - pool.add(chunk3) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(chunk1.dependencies, []) - self.assertEqual(chunk1.dependents, [stratum, chunk3]) - self.assertEqual(chunk2.dependencies, []) - self.assertEqual(chunk2.dependents, [stratum, chunk3]) - self.assertEqual(chunk3.dependencies, [chunk1, chunk2]) - self.assertEqual(chunk3.dependents, [stratum]) - self.assertEqual(stratum.dependencies, [chunk1, chunk2, chunk3]) - self.assertEqual(stratum.dependents, []) - - def test_with_stratum_dependencies(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum1", - "kind": "stratum" - } - ''') - stratum1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') - pool.add(stratum1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum2", - "kind": "stratum", - "build-depends": [ - "stratum1" - ] - } - ''') - stratum2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') - pool.add(stratum2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum3", - "kind": "stratum", - "build-depends": [ - "stratum2" - ] - } - ''') - stratum3 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum3.morph') - pool.add(stratum3) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(stratum1.dependencies, []) - self.assertEqual(stratum1.dependents, [stratum2]) - self.assertEqual(stratum2.dependencies, [stratum1]) - self.assertEqual(stratum2.dependents, [stratum3]) - self.assertEqual(stratum3.dependencies, [stratum2]) - self.assertEqual(stratum3.dependents, []) - - def test_with_stratum_and_chunk_dependencies(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum1", - "kind": "stratum" - } - ''') - stratum1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') - pool.add(stratum1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum2", - "kind": "stratum", - "build-depends": [ - "stratum1" - ], - "sources": [ - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref" - }, - { - "name": "chunk2", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') - pool.add(stratum2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk1", - "kind": "chunk" - } - ''') - chunk1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') - pool.add(chunk1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk2", - "kind": "chunk" - } - ''') - chunk2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') - pool.add(chunk2) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(stratum1.dependencies, []) - self.assertEqual(stratum1.dependents, [stratum2, chunk1, chunk2]) - self.assertEqual(chunk1.dependencies, [stratum1]) - self.assertEqual(chunk1.dependents, [stratum2, chunk2]) - self.assertEqual(chunk2.dependencies, [stratum1, chunk1]) - self.assertEqual(chunk2.dependents, [stratum2]) - self.assertEqual(stratum2.dependencies, [stratum1, chunk1, chunk2]) - self.assertEqual(stratum2.dependents, []) - - def test_with_a_system_and_two_strata(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum1", - "kind": "stratum" - } - ''') - stratum1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') - pool.add(stratum1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum2", - "kind": "stratum" - } - ''') - stratum2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') - pool.add(stratum2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "system", - "kind": "system", - "strata": [ - "stratum1", - "stratum2" - ] - } - ''') - system = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'system.morph') - pool.add(system) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(stratum1.dependencies, []) - self.assertEqual(stratum1.dependents, [system]) - self.assertEqual(stratum2.dependencies, []) - self.assertEqual(stratum2.dependents, [system]) - self.assertEqual(system.dependencies, [stratum1, stratum2]) - self.assertEqual(system.dependents, []) - - def test_detection_of_mutual_dependency_between_two_strata(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum1", - "kind": "stratum", - "build-depends": [ - "stratum2" - ] - } - ''') - stratum1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') - pool.add(stratum1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum2", - "kind": "stratum", - "build-depends": [ - "stratum1" - ] - } - ''') - stratum2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') - pool.add(stratum2) - - self.assertRaises(morphlib.dependencyresolver.MutualDependencyError, - self.resolver.resolve_dependencies, pool) - - def test_graceful_handling_of_self_dependencies_of_chunks(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum1", - "kind": "stratum", - "sources": [ - { - "name": "chunk-runtime", - "repo": "repo", - "morph": "chunk", - "ref": "original/ref" - }, - { - "name": "chunk-devel", - "repo": "repo", - "morph": "chunk", - "ref": "original/ref" - }, - { - "name": "chunk-doc", - "repo": "repo", - "morph": "chunk", - "ref": "original/ref", - "build-depends": [ - "chunk-runtime" - ] - } - ] - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') - pool.add(stratum) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk", - "kind": "chunk", - "artifacts": { - "chunk-runtime": [ "usr/lib" ], - "chunk-devel": [ "usr/include" ], - "chunk-doc": [ "usr/share/doc" ] - } - } - ''') - chunk = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk.morph') - pool.add(chunk) - - self.resolver.resolve_dependencies(pool) - - self.assertEqual(chunk.dependencies, []) - self.assertEqual(chunk.dependents, [stratum]) - self.assertEqual(stratum.dependencies, [chunk]) - self.assertEqual(stratum.dependents, []) - - def test_detection_of_mutual_dependency_between_consecutive_chunks(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum1", - "kind": "stratum", - "sources": [ - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref" - }, - { - "name": "chunk2", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') - pool.add(stratum1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum2", - "kind": "stratum", - "build-depends": [ - "stratum1" - ], - "sources": [ - { - "name": "chunk2", - "repo": "repo", - "ref": "original/ref" - }, - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') - pool.add(stratum2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk1", - "kind": "chunk" - } - ''') - chunk1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') - pool.add(chunk1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk2", - "kind": "chunk" - } - ''') - chunk2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') - pool.add(chunk2) - - self.assertRaises(morphlib.dependencyresolver.MutualDependencyError, - self.resolver.resolve_dependencies, pool) - - def test_detection_of_cyclic_chunk_dependency_chain(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum1", - "kind": "stratum", - "sources": [ - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref" - }, - { - "name": "chunk2", - "repo": "repo", - "ref": "original/ref", - "build-depends": [ - "chunk1" - ] - }, - { - "name": "chunk3", - "repo": "repo", - "ref": "original/ref", - "build-depends": [ - "chunk2" - ] - } - ] - } - ''') - stratum1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum1.morph') - pool.add(stratum1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum2", - "kind": "stratum", - "build-depends": [ - "stratum1" - ], - "sources": [ - { - "name": "chunk3", - "repo": "repo", - "ref": "original/ref" - }, - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum2.morph') - pool.add(stratum2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk1", - "kind": "chunk" - } - ''') - chunk1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') - pool.add(chunk1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk2", - "kind": "chunk" - } - ''') - chunk2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') - pool.add(chunk2) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk3", - "kind": "chunk" - } - ''') - chunk2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk3.morph') - pool.add(chunk2) - - self.assertRaises( - morphlib.dependencyresolver.CyclicDependencyChainError, - self.resolver.resolve_dependencies, pool) - - def test_detection_of_chunk_dependencies_in_invalid_order(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum", - "kind": "stratum", - "sources": [ - { - "name": "chunk1", - "repo": "repo", - "ref": "original/ref", - "build-depends": [ - "chunk2" - ] - }, - { - "name": "chunk2", - "repo": "repo", - "ref": "original/ref" - } - ] - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') - pool.add(stratum) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk1", - "kind": "chunk" - } - ''') - chunk1 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk1.morph') - pool.add(chunk1) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk2", - "kind": "chunk" - } - ''') - chunk2 = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk2.morph') - pool.add(chunk2) - - self.assertRaises(morphlib.dependencyresolver.DependencyOrderError, - self.resolver.resolve_dependencies, pool) - - def test_detection_of_invalid_build_depends_format(self): - pool = morphlib.sourcepool.SourcePool() - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "stratum", - "kind": "stratum", - "sources": [ - { - "name": "chunk", - "repo": "repo", - "ref": "original/ref", - "build-depends": "whatever" - } - ] - } - ''') - stratum = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'stratum.morph') - pool.add(stratum) - - morph = morphlib.morph2.Morphology( - ''' - { - "name": "chunk", - "kind": "chunk" - } - ''') - chunk = morphlib.source.Source( - 'repo', 'original/ref', 'sha1', morph, 'chunk.morph') - pool.add(chunk) - - self.assertRaises(morphlib.dependencyresolver.DependencyFormatError, - self.resolver.resolve_dependencies, pool) |