diff options
author | Jannis Pohlmann <jannis.pohlmann@codethink.co.uk> | 2012-01-18 18:40:43 +0000 |
---|---|---|
committer | Jannis Pohlmann <jannis.pohlmann@codethink.co.uk> | 2012-01-19 12:07:46 +0000 |
commit | 749948736178b7df4e8c52a3dddf16f83359dcfc (patch) | |
tree | abe1b191ca0a18d4976ec59896ca60bddb65febd /morphlib | |
parent | 85069b20d623b93154fb3858eaae0e978fd6a2e6 (diff) | |
download | morph-749948736178b7df4e8c52a3dddf16f83359dcfc.tar.gz |
Apply code review changes and fix a bug when clearing dependencies.
Diffstat (limited to 'morphlib')
-rw-r--r-- | morphlib/blobs.py | 15 | ||||
-rw-r--r-- | morphlib/builddependencygraph.py | 93 | ||||
-rw-r--r-- | morphlib/builder.py | 25 |
3 files changed, 80 insertions, 53 deletions
diff --git a/morphlib/blobs.py b/morphlib/blobs.py index 70cd1f90..6ddcaf0c 100644 --- a/morphlib/blobs.py +++ b/morphlib/blobs.py @@ -16,15 +16,18 @@ class Blob(object): - def __init__(self, parent, morph): - self.parent = parent + def __init__(self, morph): + self.parents = [] self.morph = morph - self.dependencies = set() - self.dependents = set() + self.dependencies = [] + self.dependents = [] + + def add_parent(self, parent): + self.parents.append(parent) def add_dependency(self, other): - self.dependencies.add(other) - other.dependents.add(self) + self.dependencies.append(other) + other.dependents.append(self) def remove_dependency(self, other): self.dependencies.remove(other) diff --git a/morphlib/builddependencygraph.py b/morphlib/builddependencygraph.py index 8fc85c20..9623a4f0 100644 --- a/morphlib/builddependencygraph.py +++ b/morphlib/builddependencygraph.py @@ -22,39 +22,46 @@ import morphlib class BuildDependencyGraph(object): # pragma: no cover - '''This class constructs a build dependency graph from an input morphology - and provides ways to traverse this graph. It also provides a method to - transform the dependency graph into groups of items that are independent - and can be built in parallel.''' + '''This class constructs a build dependency graph from an input morphology. + + Given a chunk, stratum or system morphology, this class constructs a build + dependency graph and provides ways to traverse it. It also provides a + method to transform the dependency graph into groups of items that are + independent and can be built in parallel. + + ''' def __init__(self, loader, morph): self.loader = loader self.morph = morph self.blobs = set() - def create_blob(self, morph, parent=None): - '''Creates a blob from a morphology. The optional parent is used to - associate chunks with their containing stratum.''' + def create_blob(self, morph): + '''Creates a blob from a morphology.''' if morph.kind == 'stratum': - return morphlib.blobs.Stratum(parent, morph) + return morphlib.blobs.Stratum(morph) elif morph.kind == 'chunk': - return morphlib.blobs.Chunk(parent, morph) + return morphlib.blobs.Chunk(morph) else: - return morphlib.blobs.System(parent, morph) + return morphlib.blobs.System(morph) def resolve(self): - '''Constructs the dependency graph by resolving dependencies - recursively.''' + '''Constructs the graph by resolving dependencies recursively.''' self.cached_blobs = {} self._resolve_strata() self._resolve_chunks() def build_order(self): - '''Computes a topological sorting of the dependency graph and - generates a deque of groups, each of which contains a set - of items that are independent and can be built in parallel.''' + '''Returns a queue of build groups in a valid order. + + This function computes a topological sorting of the dependency graph + and generates a deque of groups, each of which contains a set of items + that are independent and can be built in parallel. The items in each + group are guaranteed to depend only on items in previous groups. + + ''' sorting = self._compute_topological_sorting() groups = collections.deque() @@ -79,22 +86,29 @@ class BuildDependencyGraph(object): # pragma: no cover # return the set of blobs and the build groups return set(self.blobs), groups - def _get_blob(self, info, parent=None): + def _get_blob(self, info): '''Takes a (repo, ref, filename) tuple and looks up the blob for it. - It loads the corresponding morphology and blob on-demand if it is - not cached yet.''' + + Loads the corresponding morphology and blob on-demand if it is + not cached yet. + + ''' blob = self.cached_blobs.get(info, None) if not blob: morphology = self.loader.load(info[0], info[1], info[2]) - blob = self.create_blob(morphology, parent) + blob = self.create_blob(morphology) self.cached_blobs[info] = blob return blob def _resolve_strata(self): - '''This method recursively generates a dependency graph of strata - for the input morphology using breadth-first search. It loads - morphologies and blobs on demand.''' + '''Generates a dependency graph of strata recursively. + + It starts with the input morphology and attempts to resolve all its + build dependencies recursively using breadth-first search. Morphologies + and blobs are loaded from disk on demand. + + ''' if self.morph.kind == 'stratum': # turn the morphology into a stratum object @@ -134,9 +148,13 @@ class BuildDependencyGraph(object): # pragma: no cover % stratum) def _resolve_chunks(self): - '''Starting with a dependency graph of strata, this method fills the - graph with all contained chunks and creates dependencies where - appropriate. Chunk morphologies and blobs are loaded on demand.''' + '''Resolves all chunks of the strata and inserts them into the graph. + + Starting with a dependency graph of strata, this method fills the + graph with all contained chunks and creates dependencies where + appropriate. Chunk morphologies and blobs are loaded on demand. + + ''' if self.morph.kind == 'chunk': blob = self.create_blob(self.morph) @@ -167,7 +185,8 @@ class BuildDependencyGraph(object): # pragma: no cover info = (repo, ref, filename) # load the chunk on demand - chunk = self._get_blob(info, stratum) + chunk = self._get_blob(info) + chunk.add_parent(stratum) # store (name -> chunk) association to avoid loading the chunk twice name_to_chunk[source['name']] = chunk @@ -210,20 +229,26 @@ class BuildDependencyGraph(object): # pragma: no cover chunk.add_dependency(dependency) # clear the dependencies of the stratum - stratum.dependencies = set() + for dependency in set(stratum.dependencies): + stratum.remove_dependency(dependency) # make the stratum depend on all its chunks for chunk in stratum_chunks: stratum.add_dependency(chunk) def _compute_topological_sorting(self): - '''Computes a topological sorting of the dependency graph. A topological - sorting basically is the result of a series of breadth-first searches - starting at each leaf node (blobs with no dependencies). Blobs are - added to the sorting as soon as all their dependencies have been - added (which means that by then, all dependencies are satisfied). - - http://en.wikipedia.org/wiki/Topological_sorting.''' + '''Computes a topological sorting of the dependency graph. + + A topological sorting basically is the result of a series of + breadth-first searches starting at each leaf node (blobs with no + dependencies). Blobs are added to the sorting as soon as all their + dependencies have been added (which means that by then, all + dependencies are satisfied). + + For more information, see + http://en.wikipedia.org/wiki/Topological_sorting. + + ''' # map blobs to sets of satisfied dependencies. this is to detect when # we can actually add blobs to the BFS queue. rather than dropping diff --git a/morphlib/builder.py b/morphlib/builder.py index 222e884c..ff5fc3f6 100644 --- a/morphlib/builder.py +++ b/morphlib/builder.py @@ -90,7 +90,7 @@ class BlobBuilder(object): # if not all build items are in the cache, rebuild the blob if not all(os.path.isfile(builds[name]) for name in builds): with self.build_watch('overall-build'): - built_items += self.do_build() + self.do_build() # check again, fail if not all build items were actually built if not all(os.path.isfile(builds[name]) for name in builds): @@ -99,11 +99,13 @@ class BlobBuilder(object): # install all build items to the staging area for name, filename in builds.items(): - self.msg('Using cached %s %s at %s' % (self.blob.morph.kind, - name, filename)) + self.msg('Fetching cached %s %s from %s' % + (self.blob.morph.kind, name, filename)) self.install_chunk(name, filename) self.dump_memory_profile('after installing chunk') + built_items.append((name, filename)) + return built_items def filename(self, name): @@ -217,7 +219,7 @@ class ChunkBuilder(BlobBuilder): 'FAKEROOTKEY', 'FAKED_MODE', 'FAKEROOT_FD_BASE', - ], None) + ]) for name in copied_vars: copied_vars[name] = self.ex.env.get(name, None) @@ -523,11 +525,8 @@ class Builder(object): # second pass: build group by group, item after item ret = [] - while len(build_order) > 0: - group = build_order.popleft() - while len(group) > 0: - blob = group.pop() - + for group in build_order: + for blob in group: self.msg('Building %s' % blob) self.indent_more() @@ -546,12 +545,12 @@ class Builder(object): built_items = builders[blob].build() - if blob.parent: + for parent in blob.parents: for item, filename in built_items: - self.msg('Marking %s to be staged for %s' % - (item, blob.parent)) + self.msg('Marking %s to be staged for %s' + % (item, parent)) - parent_builder = builders[blob.parent] + parent_builder = builders[parent] parent_builder.stage_items += built_items self.indent_less() |