diff options
Diffstat (limited to 'python/mozbuild/dumbmake')
| -rw-r--r-- | python/mozbuild/dumbmake/__init__.py | 0 | ||||
| -rw-r--r-- | python/mozbuild/dumbmake/dumbmake.py | 122 | ||||
| -rw-r--r-- | python/mozbuild/dumbmake/test/__init__.py | 0 | ||||
| -rw-r--r-- | python/mozbuild/dumbmake/test/test_dumbmake.py | 106 |
4 files changed, 228 insertions, 0 deletions
diff --git a/python/mozbuild/dumbmake/__init__.py b/python/mozbuild/dumbmake/__init__.py new file mode 100644 index 000000000..e69de29bb --- /dev/null +++ b/python/mozbuild/dumbmake/__init__.py diff --git a/python/mozbuild/dumbmake/dumbmake.py b/python/mozbuild/dumbmake/dumbmake.py new file mode 100644 index 000000000..5457c8b0a --- /dev/null +++ b/python/mozbuild/dumbmake/dumbmake.py @@ -0,0 +1,122 @@ +# 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 absolute_import, unicode_literals + +from collections import OrderedDict +from itertools import groupby +from operator import itemgetter +from os.path import dirname + +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 all the dependencies of |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: + 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 get_components(path): + """Take a path and return all the components of the path.""" + paths = [path] + while True: + parent = dirname(paths[-1]) + if parent == "": + break + paths.append(parent) + + paths.reverse() + return paths + +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). + + """ + all_targets = OrderedDict() # Used as an ordered set. + make_dirs = OrderedDict() # Used as an ordered set. + + 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: + # Generate dependencies for all components of a path. + # Given path a/b/c, examine a, a/b, and a/b/c in that order. + paths = get_components(pair[1]) + # For each component of a path, find and add all dependencies + # to the final target list. + for target in paths: + if target not in all_targets: + yield pair[0], target + all_targets[target] = True + continue + + # Add extra dumbmake dependencies to simple directory targets. + for make_dir, _ in group: + if make_dir not in make_dirs: + yield make_dir, None + make_dirs[make_dir] = True + + all_components = [] + for make_dir in make_dirs.iterkeys(): + all_components.extend(get_components(make_dir)) + + for i in all_dependencies(*all_components, dependency_map=dependency_map): + if i not in make_dirs: + yield i, None diff --git a/python/mozbuild/dumbmake/test/__init__.py b/python/mozbuild/dumbmake/test/__init__.py new file mode 100644 index 000000000..e69de29bb --- /dev/null +++ b/python/mozbuild/dumbmake/test/__init__.py diff --git a/python/mozbuild/dumbmake/test/test_dumbmake.py b/python/mozbuild/dumbmake/test/test_dumbmake.py new file mode 100644 index 000000000..1172117aa --- /dev/null +++ b/python/mozbuild/dumbmake/test/test_dumbmake.py @@ -0,0 +1,106 @@ +# 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), []) + self.assertEqual(all_dependencies("b", dependency_map=dm), ["a"]) + self.assertEqual(all_dependencies("c", "a", "b", dependency_map=dm), ["b", "a"]) + self.assertEqual(all_dependencies("d", dependency_map=dm), ["a"]) + self.assertEqual(all_dependencies("d", "f", "c", dependency_map=dm), ["b", "a"]) + self.assertEqual(all_dependencies("a", "b", dependency_map=dm), ["a"]) + self.assertEqual(all_dependencies("b", "b", dependency_map=dm), ["a"]) + + def test_missing_entry(self): + # a depends on b, which is missing + dm = {"a": ["b"]} + self.assertEqual(all_dependencies("a", dependency_map=dm), ["b"]) + self.assertEqual(all_dependencies("a", "b", dependency_map=dm), ["b"]) + self.assertEqual(all_dependencies("b", dependency_map=dm), []) + + 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), ["c"]) + # ... but relative order is preserved. + self.assertEqual(all_dependencies("b", "a", dependency_map=dm), ["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), ["b", "c", "d"]) + self.assertEqual(all_dependencies("c", "a", dependency_map=dm), ["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), (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), (None, "package"), + (None, "install"), ("c", None), ("d", None)]) + +if __name__ == '__main__': + main() |