michael@0: # This Source Code Form is subject to the terms of the Mozilla Public
michael@0: # License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0: # file, You can obtain one at http://mozilla.org/MPL/2.0/.
michael@0: 
michael@0: from __future__ import unicode_literals
michael@0: 
michael@0: from collections import OrderedDict
michael@0: from itertools import groupby
michael@0: from operator import itemgetter
michael@0: from os.path import dirname
michael@0: 
michael@0: WHITESPACE_CHARACTERS = ' \t'
michael@0: 
michael@0: def indentation(line):
michael@0:     """Number of whitespace (tab and space) characters at start of |line|."""
michael@0:     i = 0
michael@0:     while i < len(line):
michael@0:         if line[i] not in WHITESPACE_CHARACTERS:
michael@0:             break
michael@0:         i += 1
michael@0:     return i
michael@0: 
michael@0: def dependency_map(lines):
michael@0:     """Return a dictionary with keys that are targets and values that
michael@0:     are ordered lists of targets that should also be built.
michael@0: 
michael@0:     This implementation is O(n^2), but lovely and simple!  We walk the
michael@0:     targets in the list, and for each target we walk backwards
michael@0:     collecting its dependencies.  To make the walking easier, we
michael@0:     reverse the list so that we are always walking forwards.
michael@0: 
michael@0:     """
michael@0:     pairs = [(indentation(line), line.strip()) for line in lines]
michael@0:     pairs.reverse()
michael@0: 
michael@0:     deps = {}
michael@0: 
michael@0:     for i, (indent, target) in enumerate(pairs):
michael@0:         if not deps.has_key(target):
michael@0:             deps[target] = []
michael@0: 
michael@0:         for j in range(i+1, len(pairs)):
michael@0:             ind, tar = pairs[j]
michael@0:             if ind < indent:
michael@0:                 indent = ind
michael@0:                 if tar not in deps[target]:
michael@0:                     deps[target].append(tar)
michael@0: 
michael@0:     return deps
michael@0: 
michael@0: def all_dependencies(*targets, **kwargs):
michael@0:     """Return a list containing all the dependencies of |targets|.
michael@0: 
michael@0:     The relative order of targets is maintained if possible.
michael@0: 
michael@0:     """
michael@0:     dm = kwargs.pop('dependency_map', None)
michael@0:     if dm is None:
michael@0:         dm = dependency_map(targets)
michael@0: 
michael@0:     all_targets = OrderedDict() # Used as an ordered set.
michael@0: 
michael@0:     for target in targets:
michael@0:         if target in dm:
michael@0:             for dependency in dm[target]:
michael@0:                 # Move element back in the ordered set.
michael@0:                 if dependency in all_targets:
michael@0:                     del all_targets[dependency]
michael@0:                 all_targets[dependency] = True
michael@0: 
michael@0:     return all_targets.keys()
michael@0: 
michael@0: def get_components(path):
michael@0:     """Take a path and return all the components of the path."""
michael@0:     paths = [path]
michael@0:     while True:
michael@0:         parent = dirname(paths[-1])
michael@0:         if parent == "":
michael@0:             break
michael@0:         paths.append(parent)
michael@0: 
michael@0:     paths.reverse()
michael@0:     return paths
michael@0: 
michael@0: def add_extra_dependencies(target_pairs, dependency_map):
michael@0:     """Take a list [(make_dir, make_target)] and expand (make_dir, None)
michael@0:     entries with extra make dependencies from |dependency_map|.
michael@0: 
michael@0:     Returns an iterator of pairs (make_dir, make_target).
michael@0: 
michael@0:     """
michael@0:     all_targets = OrderedDict() # Used as an ordered set.
michael@0:     make_dirs = OrderedDict() # Used as an ordered set.
michael@0: 
michael@0:     for make_target, group in groupby(target_pairs, itemgetter(1)):
michael@0:         # Return non-simple directory targets untouched.
michael@0:         if make_target is not None:
michael@0:             for pair in group:
michael@0:                 # Generate dependencies for all components of a path.
michael@0:                 # Given path a/b/c, examine a, a/b, and a/b/c in that order.
michael@0:                 paths = get_components(pair[1])
michael@0:                 # For each component of a path, find and add all dependencies
michael@0:                 # to the final target list.
michael@0:                 for target in paths:
michael@0:                     if target not in all_targets:
michael@0:                         yield pair[0], target
michael@0:                         all_targets[target] = True
michael@0:             continue
michael@0: 
michael@0:         # Add extra dumbmake dependencies to simple directory targets.
michael@0:         for make_dir, _ in group:
michael@0:             if make_dir not in make_dirs:
michael@0:                 yield make_dir, None
michael@0:                 make_dirs[make_dir] = True
michael@0: 
michael@0:     all_components = []
michael@0:     for make_dir in make_dirs.iterkeys():
michael@0:         all_components.extend(get_components(make_dir))
michael@0: 
michael@0:     for i in all_dependencies(*all_components, dependency_map=dependency_map):
michael@0:         if i not in make_dirs:
michael@0:             yield i, None