Bug 677452 - Add smartmake-like functionality to |mach build DIR|. r=gps
authorNick Alexander <nalexander@mozilla.com>
Wed, 01 May 2013 15:36:05 -0700
changeset 141503 e5d90d0479ccd39c8f571d63300e8ecd16df7abc
parent 141502 08d7cf75697baeaa08ac7b9e319f67c899572e01
child 141504 210b52cdd7ebf57603f51abbb2a1d5c2e7dd5b7d
push id2579
push userakeybl@mozilla.com
push dateMon, 24 Jun 2013 18:52:47 +0000
treeherdermozilla-beta@b69b7de8a05a [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgps
bugs677452
milestone23.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 677452 - Add smartmake-like functionality to |mach build DIR|. r=gps
build/dumbmake-dependencies
python/Makefile.in
python/mozbuild/dumbmake/README.rst
python/mozbuild/dumbmake/__init__.py
python/mozbuild/dumbmake/dumbmake.py
python/mozbuild/dumbmake/test/__init__.py
python/mozbuild/dumbmake/test/test_dumbmake.py
python/mozbuild/mozbuild/mach_commands.py
new file mode 100644
--- /dev/null
+++ b/build/dumbmake-dependencies
@@ -0,0 +1,52 @@
+toolkit/library
+  ipc
+  netwerk/build
+    netwerk
+  storage/build
+    storage
+  xpcom
+    chrome
+  extensions
+  docshell/build
+    docshell
+    uriloader
+  modules
+  widget
+  gfx
+  toolkit/components/build
+    toolkit/components
+  security/build
+  security/manager
+  security/dbm
+  security/nss
+  accessible/build
+    accessible
+  dom
+  content
+  layout
+  editor
+  parser
+  js/src
+    js/xpconnect
+      js/xpconnect/loader
+    mfbt
+  view
+  caps
+  xpfe/appshell
+  xpfe/components
+  js
+  toolkit
+  rdf/build
+  embedding
+  hal
+  image/build
+    image
+  intl/build
+    intl
+  media
+  profile
+  services
+  startupcache
+browser
+  toolkit/mozapps/extensions
+  toolkit/content
--- a/python/Makefile.in
+++ b/python/Makefile.in
@@ -11,15 +11,16 @@ include $(DEPTH)/config/autoconf.mk
 
 test_dirs := \
   mozbuild/mozbuild/test \
   mozbuild/mozbuild/test/backend \
   mozbuild/mozbuild/test/controller \
   mozbuild/mozbuild/test/compilation \
   mozbuild/mozbuild/test/frontend \
   mozbuild/mozpack/test \
+  mozbuild/dumbmake/test \
   $(NULL)
 
 PYTHON_UNIT_TESTS := $(foreach dir,$(test_dirs),$(wildcard $(srcdir)/$(dir)/*.py))
 
 include $(topsrcdir)/config/rules.mk
 
 
new file mode 100644
--- /dev/null
+++ b/python/mozbuild/dumbmake/README.rst
@@ -0,0 +1,38 @@
+dumbmake
+========
+
+*dumbmake* is a simple dependency tracker for make.
+
+It turns lists of make targets into longer lists of make targets that
+include dependencies.  For example:
+
+    netwerk, package
+
+might be turned into
+
+    netwerk, netwerk/build, toolkit/library, package
+
+The dependency list is read from the plain text file
+`topsrcdir/build/dumbmake-dependencies`.  The format best described by
+example:
+
+    build_this
+        when_this_changes
+
+Interpret this to mean that `build_this` is a dependency of
+`when_this_changes`.  More formally, a line (CHILD) indented more than
+the preceding line (PARENT) means that CHILD should trigger building
+PARENT.  That is, building CHILD will trigger building first CHILD and
+then PARENT.
+
+This structure is recursive:
+
+    build_this_when_either_change
+        build_this_only_when
+            this_changes
+
+This means that `build_this_when_either_change` is a dependency of
+`build_this_only_when` and `this_changes`, and `build_this_only_when`
+is a dependency of `this_changes`.  Building `this_changes` will build
+first `this_changes`, then `build_this_only_when`, and finally
+`build_this_when_either_change`.
new file mode 100644
new file mode 100644
--- /dev/null
+++ b/python/mozbuild/dumbmake/dumbmake.py
@@ -0,0 +1,93 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this
+# file, You can obtain one at http://mozilla.org/MPL/2.0/.
+
+from __future__ import unicode_literals
+
+from collections import OrderedDict
+from itertools import groupby
+from operator import itemgetter
+
+WHITESPACE_CHARACTERS = ' \t'
+
+def indentation(line):
+    """Number of whitespace (tab and space) characters at start of |line|."""
+    i = 0
+    while i < len(line):
+        if line[i] not in WHITESPACE_CHARACTERS:
+            break
+        i += 1
+    return i
+
+def dependency_map(lines):
+    """Return a dictionary with keys that are targets and values that
+    are ordered lists of targets that should also be built.
+
+    This implementation is O(n^2), but lovely and simple!  We walk the
+    targets in the list, and for each target we walk backwards
+    collecting its dependencies.  To make the walking easier, we
+    reverse the list so that we are always walking forwards.
+
+    """
+    pairs = [(indentation(line), line.strip()) for line in lines]
+    pairs.reverse()
+
+    deps = {}
+
+    for i, (indent, target) in enumerate(pairs):
+        if not deps.has_key(target):
+            deps[target] = []
+
+        for j in range(i+1, len(pairs)):
+            ind, tar = pairs[j]
+            if ind < indent:
+                indent = ind
+                if tar not in deps[target]:
+                    deps[target].append(tar)
+
+    return deps
+
+def all_dependencies(*targets, **kwargs):
+    """Return a list containing |targets| and all the dependencies of
+    those targets.
+
+    The relative order of targets is maintained if possible.
+
+    """
+    dm = kwargs.pop('dependency_map', None)
+    if dm is None:
+        dm = dependency_map(targets)
+
+    all_targets = OrderedDict() # Used as an ordered set.
+
+    for target in targets:
+        all_targets[target] = True
+        if target in dm:
+            for dependency in dm[target]:
+                # Move element back in the ordered set.
+                if dependency in all_targets:
+                    del all_targets[dependency]
+                all_targets[dependency] = True
+
+    return all_targets.keys()
+
+def add_extra_dependencies(target_pairs, dependency_map):
+    """Take a list [(make_dir, make_target)] and expand (make_dir, None)
+    entries with extra make dependencies from |dependency_map|.
+
+    Returns an iterator of pairs (make_dir, make_target).
+
+    """
+    for make_target, group in groupby(target_pairs, itemgetter(1)):
+        # Return non-simple directory targets untouched.
+        if make_target is not None:
+            for pair in group:
+                yield pair
+            continue
+
+        # Add extra dumbmake dependencies to simple directory targets.
+        make_dirs = [make_dir for make_dir, _ in group]
+        new_make_dirs = all_dependencies(*make_dirs, dependency_map=dependency_map)
+
+        for make_dir in new_make_dirs:
+            yield make_dir, None
new file mode 100644
new file mode 100644
--- /dev/null
+++ b/python/mozbuild/dumbmake/test/test_dumbmake.py
@@ -0,0 +1,108 @@
+# This Source Code Form is subject to the terms of the Mozilla Public
+# License, v. 2.0. If a copy of the MPL was not distributed with this file,
+# You can obtain one at http://mozilla.org/MPL/2.0/.
+from __future__ import unicode_literals
+
+import unittest
+
+from mozunit import (
+    main,
+)
+
+from dumbmake.dumbmake import (
+    add_extra_dependencies,
+    all_dependencies,
+    dependency_map,
+    indentation,
+)
+
+class TestDumbmake(unittest.TestCase):
+    def test_indentation(self):
+        self.assertEqual(indentation(""), 0)
+        self.assertEqual(indentation("x"), 0)
+        self.assertEqual(indentation(" x"), 1)
+        self.assertEqual(indentation("\tx"), 1)
+        self.assertEqual(indentation(" \tx"), 2)
+        self.assertEqual(indentation("\t x"), 2)
+        self.assertEqual(indentation(" x  "), 1)
+        self.assertEqual(indentation("\tx\t"), 1)
+        self.assertEqual(indentation("  x"), 2)
+        self.assertEqual(indentation("    x"), 4)
+
+    def test_dependency_map(self):
+        self.assertEqual(dependency_map([]), {})
+        self.assertEqual(dependency_map(["a"]), {"a": []})
+        self.assertEqual(dependency_map(["a", "b"]), {"a": [], "b": []})
+        self.assertEqual(dependency_map(["a", "b", "c"]), {"a": [], "b": [], "c": []})
+        # indentation
+        self.assertEqual(dependency_map(["a", "\tb", "a", "\tc"]), {"a": [], "b": ["a"], "c": ["a"]})
+        self.assertEqual(dependency_map(["a", "\tb", "\t\tc"]), {"a": [], "b": ["a"], "c": ["b", "a"]})
+        self.assertEqual(dependency_map(["a", "\tb", "\t\tc", "\td", "\te", "f"]), {"a": [], "b": ["a"], "c": ["b", "a"], "d": ["a"], "e": ["a"], "f": []})
+        # irregular indentation
+        self.assertEqual(dependency_map(["\ta", "b"]), {"a": [], "b": []})
+        self.assertEqual(dependency_map(["a", "\t\t\tb", "\t\tc"]), {"a": [], "b": ["a"], "c": ["a"]})
+        self.assertEqual(dependency_map(["a", "\t\tb", "\t\t\tc", "\t\td", "\te", "f"]), {"a": [], "b": ["a"], "c": ["b", "a"], "d": ["a"], "e": ["a"], "f": []})
+        # repetitions
+        self.assertEqual(dependency_map(["a", "\tb", "a", "\tb"]), {"a": [], "b": ["a"]})
+        self.assertEqual(dependency_map(["a", "\tb", "\t\tc", "b", "\td", "\t\te"]), {"a": [], "b": ["a"], "d": ["b"], "e": ["d", "b"], "c": ["b", "a"]})
+        # cycles are okay
+        self.assertEqual(dependency_map(["a", "\tb", "\t\ta"]), {"a": ["b", "a"], "b": ["a"]})
+
+    def test_all_dependencies(self):
+        dm = {"a": [], "b": ["a"], "c": ["b", "a"], "d": ["a"], "e": ["a"], "f": []}
+        self.assertEqual(all_dependencies("a", dependency_map=dm), ["a"])
+        self.assertEqual(all_dependencies("b", dependency_map=dm), ["b", "a"])
+        self.assertEqual(all_dependencies("c", "a", "b", dependency_map=dm), ["c", "b", "a"])
+        self.assertEqual(all_dependencies("d", dependency_map=dm), ["d", "a"])
+        self.assertEqual(all_dependencies("d", "f", "c", dependency_map=dm), ["d", "f", "c", "b", "a"])
+        self.assertEqual(all_dependencies("a", "b", dependency_map=dm), ["b", "a"])
+        self.assertEqual(all_dependencies("b", "b", dependency_map=dm), ["b", "a"])
+
+    def test_missing_entry(self):
+        # a depends on b, which is missing
+        dm = {"a": ["b"]}
+        self.assertEqual(all_dependencies("a", dependency_map=dm), ["a", "b"])
+        self.assertEqual(all_dependencies("a", "b", dependency_map=dm), ["a", "b"])
+        self.assertEqual(all_dependencies("b", dependency_map=dm), ["b"])
+
+    def test_two_dependencies(self):
+        dm = {"a": ["c"], "b": ["c"], "c": []}
+        # suppose a and b both depend on c.  Then we want to build a and b before c...
+        self.assertEqual(all_dependencies("a", "b", dependency_map=dm), ["a", "b", "c"])
+        # ... but relative order is preserved.
+        self.assertEqual(all_dependencies("b", "a", dependency_map=dm), ["b", "a", "c"])
+
+    def test_nested_dependencies(self):
+        # a depends on b depends on c depends on d
+        dm = {"a": ["b", "c", "d"], "b": ["c", "d"], "c": ["d"]}
+        self.assertEqual(all_dependencies("b", "a", dependency_map=dm), ["a", "b", "c", "d"])
+        self.assertEqual(all_dependencies("c", "a", dependency_map=dm), ["a", "b", "c", "d"])
+
+    def test_add_extra_dependencies(self):
+        # a depends on b depends on c depends on d
+        dm = {"a": ["b", "c", "d"], "b": ["c", "d"], "c": ["d"]}
+        # Edge cases.
+        self.assertEqual(list(add_extra_dependencies([], dependency_map=dm)),
+                         [])
+        self.assertEqual(list(add_extra_dependencies([(None, "package")], dependency_map=dm)),
+                         [(None, "package")])
+        # Easy expansion.
+        self.assertEqual(list(add_extra_dependencies([("b", None)], dependency_map=dm)),
+                         [("b", None), ("c", None), ("d", None)])
+        # Expansion with two groups -- each group is handled independently.
+        self.assertEqual(list(add_extra_dependencies([("b", None),
+                                                      (None, "package"),
+                                                      ("c", None)], dependency_map=dm)),
+                         [("b", None), ("c", None), ("d", None),
+                          (None, "package"),
+                          ("c", None), ("d", None)])
+        # Two groups, no duplicate dependencies in each group.
+        self.assertEqual(list(add_extra_dependencies([("a", None), ("b", None),
+                                                      (None, "package"), (None, "install"),
+                                                      ("c", None), ("d", None)], dependency_map=dm)),
+                         [("a", None), ("b", None), ("c", None), ("d", None),
+                          (None, "package"), (None, "install"),
+                          ("c", None), ("d", None)])
+
+if __name__ == '__main__':
+    main()
--- a/python/mozbuild/mozbuild/mach_commands.py
+++ b/python/mozbuild/mozbuild/mach_commands.py
@@ -16,18 +16,20 @@ from mach.decorators import (
     Command,
 )
 
 from mozbuild.base import MachCommandBase
 
 
 BUILD_WHAT_HELP = '''
 What to build. Can be a top-level make target or a relative directory. If
-multiple options are provided, they will be built serially. BUILDING ONLY PARTS
-OF THE TREE CAN RESULT IN BAD TREE STATE. USE AT YOUR OWN RISK.
+multiple options are provided, they will be built serially. Takes dependency
+information from `topsrcdir/build/dumbmake-dependencies` to build additional
+targets as needed. BUILDING ONLY PARTS OF THE TREE CAN RESULT IN BAD TREE
+STATE. USE AT YOUR OWN RISK.
 '''.strip()
 
 FINDER_SLOW_MESSAGE = '''
 ===================
 PERFORMANCE WARNING
 
 The OS X Finder application (file indexing used by Spotlight) used a lot of CPU
 during the build - an average of %f%% (100%% is 1 core). This made your build
@@ -41,17 +43,20 @@ Preferences.
 
 
 @CommandProvider
 class Build(MachCommandBase):
     """Interface to build the tree."""
 
     @Command('build', help='Build the tree.')
     @CommandArgument('what', default=None, nargs='*', help=BUILD_WHAT_HELP)
-    def build(self, what=None):
+    @CommandArgument('-X', '--disable-extra-make-dependencies',
+                     default=False, action='store_true',
+                     help='Do not add extra make dependencies.')
+    def build(self, what=None, disable_extra_make_dependencies=None):
         # This code is only meant to be temporary until the more robust tree
         # building code in bug 780329 lands.
         from mozbuild.compilation.warnings import WarningsCollector
         from mozbuild.compilation.warnings import WarningsDatabase
         from mozbuild.util import resolve_target_to_make
 
         warnings_path = self._get_state_filename('warnings.json')
         warnings_database = WarningsDatabase()
@@ -82,25 +87,47 @@ class Build(MachCommandBase):
 
         if what:
             top_make = os.path.join(self.topobjdir, 'Makefile')
             if not os.path.exists(top_make):
                 print('Your tree has not been configured yet. Please run '
                     '|mach build| with no arguments.')
                 return 1
 
+            # Collect target pairs.
+            target_pairs = []
             for target in what:
                 path_arg = self._wrap_path_argument(target)
 
                 make_dir, make_target = resolve_target_to_make(self.topobjdir,
                     path_arg.relpath())
 
                 if make_dir is None and make_target is None:
                     return 1
 
+                target_pairs.append((make_dir, make_target))
+
+            # Possibly add extra make depencies using dumbmake.
+            if not disable_extra_make_dependencies:
+                from dumbmake.dumbmake import (dependency_map,
+                                               add_extra_dependencies)
+                depfile = os.path.join(self.topsrcdir, 'build',
+                                       'dumbmake-dependencies')
+                with open(depfile) as f:
+                    dm = dependency_map(f.readlines())
+                new_pairs = list(add_extra_dependencies(target_pairs, dm))
+                self.log(logging.DEBUG, 'dumbmake',
+                         {'target_pairs': target_pairs,
+                          'new_pairs': new_pairs},
+                         'Added extra dependencies: will build {new_pairs} ' +
+                         'instead of {target_pairs}.')
+                target_pairs = new_pairs
+
+            # Build target pairs.
+            for make_dir, make_target in target_pairs:
                 status = self._run_make(directory=make_dir, target=make_target,
                     line_handler=on_line, log=False, print_directory=False,
                     ensure_exit_code=False)
 
                 if status != 0:
                     break
         else:
             status = self._run_make(srcdir=True, filename='client.mk',