more sophisticated build loop
authorTimo Savola <tsavola@movial.fi>
Sun, 6 Apr 2008 13:27:00 +0000 (16:27 +0300)
committerTimo Savola <tsavola@movial.fi>
Sun, 6 Apr 2008 13:42:13 +0000 (16:42 +0300)
* excludes cached components from build beforehand for more accurate
  progress information.

* builds components with largest number of dependents first in hope of
  avoiding bottlenecks during parallel builds.

matrix/build.py
matrix/components.py
matrix/matrix.py

index bde1197..f31c540 100644 (file)
@@ -6,25 +6,101 @@ import signal
 from sets import Set as set
 
 import cache
+import components
 import config
 import log
-import matrix
 
 Error = RuntimeError
+InternalError = Exception
+
+def build(targets, build_jobs=1, make_jobs=1):
+       selected = set([config.components[i] for i in targets])
+       components.fill_in_depends(selected)
+       components.init_rdepends(selected)
+
+       roots = initial_roots(selected)
+       roots = uncached_roots(roots)
+       init_weights(roots)
+
+       flat = flatten(roots)
+       count = len(flat)
+
+       if config.debug:
+               l = list(flat)
+               l.sort(key=lambda c: c.name)
+
+               print 'Building components:'
+               for c in l:
+                       print '\t' + c.name
+
+               del l
+
+       del flat
+
+       Builder(roots, count, build_jobs, make_jobs).run()
+
+       unbuilt = []
+       for c in selected:
+               if c.state != 'done' and not cache.contains(c):
+                       unbuilt.append(c.name)
+
+       if unbuilt:
+               raise Error('Components not built (dependency cycles?): ' + \
+                           ' '.join(unbuilt))
+
+       if not count:
+               print 'Nothing to build'
+
+def initial_roots(selected):
+       return [c for c in selected if not c.get_depends()]
+
+def uncached_roots(old_roots):
+       roots = set()
+
+       def add_roots(c):
+               if cache.contains(c):
+                       for child in c.get_rdepends():
+                               if child.remove_depend(c):
+                                       add_roots(child)
+
+                       c.clear_rdepends()
+               else:
+                       roots.add(c)
+
+       for c in old_roots:
+               add_roots(c)
+
+       return list(roots)
+
+def init_weights(rdepends):
+       total = 0
+
+       for c in rdepends:
+               c.weight = 1 + init_weights(c.get_rdepends())
+               total += c.weight
+
+       return total
+
+def flatten(rdepends, all=set()):
+       for c in rdepends:
+               all.add(c)
+               flatten(c.get_rdepends(), all)
+
+       return all
 
 class Builder(object):
-       def __init__(self, components, max_jobs, max_make_jobs):
+       def __init__(self, roots, count, max_jobs, max_make_jobs):
                self.max_jobs = max_jobs
                self.max_make_jobs = max_make_jobs
 
                self.jobs = {}
 
-               self.wait_build = set(components)
+               self.wait_build = roots
                self.wait_install = []
                self.in_install = None
 
                self.progress_now = 0
-               self.progress_total = len(components) * 2
+               self.progress_total = count * 2
 
                self.error = False
 
@@ -57,32 +133,17 @@ class Builder(object):
                        self.in_install = c
 
                while self.can_start_build():
-                       found = False
-
-                       for c in self.wait_build:
-                               if self.is_buildable(c):
-                                       found = True
-
-                                       if not self.try_cache(c):
-                                               matrix.clone_component(c)
-                                               self.start_build(c)
-
-                                       self.wait_build.remove(c)
-                                       break
-
-                       if not found:
-                               break
+                       c = self.wait_build.pop()
+                       self.start_build(c)
 
                if self.jobs:
                        self.wait()
                        return True
                else:
-                       if self.wait_build and not self.error:
-                               raise Error('Circular dependencies?')
                        return False
 
-       def progress(self, increment=1):
-               self.progress_now += increment
+       def progress(self):
+               self.progress_now += 1
 
        def message(self, arg1, arg2=None):
                if arg2 is None:
@@ -91,41 +152,12 @@ class Builder(object):
                        message = '%-10s %s' % (arg1, arg2)
 
                progress = '%3d%%' % \
-                          (self.progress_now *100 / self.progress_total)
+                          (self.progress_now * 100 / self.progress_total)
 
                print progress, message
 
-       def is_buildable(self, c):
-               if c.state:
-                       if config.debug:
-                               self.message('Component %s is in state: %s' % \
-                                       (c.name, c.state))
-                       return False
-
-               for dep in c.depends:
-                       if config.components[dep.name].state != 'done':
-                               if config.debug:
-                                       self.message('Component %s depends ' \
-                                               'on uninstalled %s' % \
-                                               (c.name, dep.name))
-                               return False
-
-               return True
-
-       def try_cache(self, c):
-               if not cache.contains(c):
-                       return False
-
-               c.state = 'done'
-               self.progress(2)
-
-               if config.debug:
-                       self.message('Cached', c.repo.path)
-
-               return True
-
        def can_start_build(self):
-               return self.can_start_job()
+               return self.wait_build and self.can_start_job()
 
        def can_start_install(self):
                return not self.in_install and self.wait_install and \
@@ -135,6 +167,9 @@ class Builder(object):
                return not self.error and len(self.jobs) < self.max_jobs
 
        def start_build(self, c):
+               if not c.repo.exists():
+                       c.repo.clone()
+
                self.message('Building', c.repo.path)
                self.start_job(c, 'build_matrix_component', 'in-build')
 
@@ -143,9 +178,9 @@ class Builder(object):
                self.start_job(c, 'install_matrix_component', 'in-install')
 
        def start_job(self, c, make_target, state):
+               c.state = state
                pid = spawn_make(c, self.max_make_jobs, make_target)
                self.jobs[pid] = c
-               c.state = state
 
        def wait(self):
                pid, status = os.wait()
@@ -168,6 +203,17 @@ class Builder(object):
                        c.state = 'wait-install'
                        self.wait_install.append(c)
 
+                       wait_build_changed = False
+                       for child in c.get_rdepends():
+                               if child.remove_depend(c):
+                                       self.wait_build.append(child)
+                                       wait_build_changed = True
+
+                       c.clear_rdepends()
+
+                       if wait_build_changed:
+                               self.wait_build.sort(key=lambda c: c.weight)
+
                elif c.state == 'in-install':
                        assert c == self.in_install
 
@@ -180,10 +226,11 @@ class Builder(object):
 
                        c.state = 'done'
                        self.in_install = None
+
                        cache.update(c)
 
                elif c.state != 'killed':
-                       raise Error('Unexpected state: %s' % c.state)
+                       raise InternalError('Unexpected state: %s' % c.state)
 
 def spawn_make(c, jobs, target):
        board = config.boards[config.board]
index 89e0d16..03523df 100644 (file)
@@ -15,6 +15,8 @@ Error = RuntimeError
 class Component(object):
        cached = None
 
+       rdepends = None
+       weight = None
        state = None
 
        def __init__(self, name, tag='master', tags={}, flags=[]):
@@ -40,6 +42,29 @@ class Component(object):
                self.packages = {}
                self.depends = set()
 
+       def add_depend(self, c):
+               self.depends.add(c)
+
+       def remove_depend(self, c):
+               self.depends.remove(c)
+               return not self.depends
+
+       def get_depends(self):
+               return self.depends
+
+       def add_rdepend(self, c):
+               if self.rdepends is None:
+                       self.rdepends = set()
+
+               self.rdepends.add(c)
+
+       def get_rdepends(self):
+               return self.rdepends or ()
+
+       def clear_rdepends(self):
+               if self.rdepends:
+                       del self.rdepends
+
 class PlatformProvidedComponent(Component):
        """A Component that is provided by the platform.
           The sources will not be built during install."""
@@ -133,7 +158,7 @@ def init_depends(packages):
                        if deppkg.component == pkg.component:
                                continue
 
-                       pkg.component.depends.add(deppkg.component)
+                       pkg.component.add_depend(deppkg.component)
 
        fail = False
        for pkg in packages.itervalues():
@@ -151,3 +176,20 @@ def init_depends(packages):
 
        if fail:
                raise Error('Invalid component tree')
+
+def fill_in_depends(components):
+       depends = True
+       while depends:
+               depends = set()
+
+               for c in components:
+                       for dep in c.get_depends():
+                               if dep not in components:
+                                       depends.add(dep)
+
+               components |= depends
+
+def init_rdepends(components):
+       for c in components:
+               for dep in c.get_depends():
+                       dep.add_rdepend(c)
index 0534127..a4bf3c6 100644 (file)
@@ -13,7 +13,7 @@ import components
 import config
 import git
 import log
-from build import Builder
+from build import build
 from rootfs import RootFS
 
 Error = RuntimeError
@@ -202,32 +202,6 @@ def clone_component(c, overwrite=False):
        if not have_meta:
                c.meta.clone()
 
-def build(targets, build_jobs=1, make_jobs=1):
-       selected = set([config.components[i] for i in targets])
-
-       depends = None
-       while depends is None or depends:
-               depends = set()
-
-               for c in selected:
-                       for dep in c.depends:
-                               if dep not in selected:
-                                       depends.add(dep)
-
-               selected |= depends
-
-       if config.debug:
-               print 'Building components:'
-
-               sorted = list(selected)
-               sorted.sort(key=lambda c: c.name)
-
-               for c in sorted:
-                       print '\t' + c.name
-
-       builder = Builder(selected, build_jobs, make_jobs)
-       builder.run()
-
 def clean(targets):
        for name in targets:
                c = config.components[name]