Merge DependencyResolver into ArtifactResolver.

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()