Reimplement dependency order handling to solve a performance issue. iruotsal
authorIlpo Ruotsalainen <ilpo.ruotsalainen@movial.fi>
Fri, 12 Dec 2008 13:18:47 +0000 (15:18 +0200)
committerIlpo Ruotsalainen <ilpo.ruotsalainen@movial.fi>
Fri, 12 Dec 2008 13:18:47 +0000 (15:18 +0200)
matrix/build.py
matrix/components.py

index 4817d65..bc52f0f 100644 (file)
@@ -19,29 +19,15 @@ def build(targets):
                selected = set([components.by_name[i] for i in targets])
        except KeyError, e:
                raise Error("Component " + i + " not found")
-       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(compare_name)
-
-               print 'Building components:'
-               for c in l:
-                       print '\t' + c.name
-
-               del l
+       components.fill_in_depends(selected)
 
-       del flat
+       print 'Calculating dependencies...',
+       sys.stdout.flush()
+       count = analyze_build(selected)
+       print 'done, rebuilding', count, 'components'
 
-       Builder(roots, count).run()
+       Builder(selected, count).run()
 
        unbuilt = []
        for c in selected:
@@ -74,65 +60,28 @@ def build_only(targets):
 
        Builder(all, count).run()
 
-def initial_roots(selected):
-       return [c for c in selected if not c.get_depends()]
-
-def uncached_roots(old_roots):
-       roots = set()
-       count = [0]
-
-       def add_roots(c):
-               if not config.debug:
-                       count[0] += 1
-                       print '\rChecking cache:', count[0],
-                       sys.stdout.flush()
-
-               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)
-
-       try:
-               for c in old_roots:
-                       add_roots(c)
-       finally:
-               if not config.debug:
-                       print
+def analyze_build(targets):
+       count = 0
 
-       return list(roots)
+       for c in targets:
+               if c.rebuild_checked:
+                       continue
 
-def init_weights(rdepends):
-       total = 0
+               count += analyze_build(c.get_depends())
 
-       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
-
-def compare_name(a, b):
-       return cmp(a.name, b.name)
-
-def compare_weight(a, b):
-       return cmp(a.weight, b.weight)
+               if count or not cache.contains(c):
+                       c.needs_rebuild = True
+                       count += 1
+       
+               c.rebuild_checked = True
+       
+       return count
 
 class Builder(object):
-       def __init__(self, roots, count):
+       def __init__(self, components, count):
                self.jobs = {}
 
-               self.wait_build = roots
-               self.wait_build.sort(compare_weight)
+               self.components = components
 
                self.wait_install = []
                self.in_install = None
@@ -176,7 +125,9 @@ class Builder(object):
                        self.in_install = c
 
                while self.can_start_build():
-                       c = self.wait_build.pop()
+                       c = self.find_build_job(self.components)
+                       if not c:
+                               break
                        self.start_build(c)
 
                if self.jobs:
@@ -186,16 +137,29 @@ class Builder(object):
                        return False
 
        def can_start_build(self):
-               return (not self.error or config.keep_going) and \
-                      self.wait_build and self.can_start_job()
+               return (not self.error or config.keep_going) and self.can_start_job()
 
        def can_start_install(self):
-               return not self.in_install and self.wait_install and \
-                      self.can_start_job()
+               return not self.in_install and self.wait_install
 
        def can_start_job(self):
                return len(self.jobs) < config.jobs
 
+       def find_build_job(self, components):
+               for c in components:
+                       if c.state or not c.needs_rebuild:
+                               continue
+
+                       dep_job = self.find_build_job(c.get_depends())
+
+                       if dep_job:
+                               return dep_job
+
+                       return c
+
+               return None
+                               
+
        def start_build(self, c):
                if not c.source.exists():
                        c.source.clone()
@@ -251,17 +215,6 @@ class Builder(object):
 
                        cache.update(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(compare_weight)
-
                elif c.state != 'killed':
                        raise InternalError('Unexpected state: %s' % c.state)
 
index 72f7217..bd9c970 100644 (file)
@@ -16,11 +16,11 @@ class Component(object):
        __dirty = None
 
        cached = None
-
-       rdepends = None
-       weight = None
        state = None
 
+       rebuild_checked = False
+       needs_rebuild = False
+
        def __init__(self, name, branch=None, flags=[], rank=0):
                self.name = name
 
@@ -72,19 +72,6 @@ class Component(object):
        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."""
@@ -287,8 +274,3 @@ def fill_in_depends(components):
                                        depends.add(dep)
 
                components |= depends
-
-def init_rdepends(components):
-       for c in components:
-               for dep in c.get_depends():
-                       dep.add_rdepend(c)