blob: 978b173403707148f2d7d1fbcb764a8e22946f5a [file] [log] [blame]
#!/usr/bin/env python3
# Copyright 2019 The Chromium Authors. All rights reserved.
# Use of this source code is governed by a BSD-style license that can be
# found in the LICENSE file.
"""Allots libraries to modules to be packaged into.
All libraries that are depended on by a single module will be allotted to this
module. All other libraries will be allotted to the closest ancestor.
Given the module dependency structure
/ \
b d
/ \
a e
and libraries assignment
a: ['']
e: ['', '']
will make the allotment decision
c: ['']
e: ['']
The above example is invoked via:
./allot_native_libraries \
--libraries 'a,[""]' \
--libraries 'e,["", ""]' \
--dep c:b \
--dep b:a \
--dep c:d \
--dep d:e \
--output <output JSON>
import argparse
import collections
import json
import sys
from util import build_utils
def _ModuleLibrariesPair(arg):
pos = arg.find(',')
assert pos > 0
return (arg[:pos], arg[pos + 1:])
def _DepPair(arg):
parent, child = arg.split(':')
return (parent, child)
def _PathFromRoot(module_tree, module):
"""Computes path from root to a module.
module_tree: Dictionary mapping each module to its parent.
module: Module to which to compute the path.
Path from root the the module.
path = [module]
while module_tree.get(module):
module = module_tree[module]
path = [module] + path
return path
def _ClosestCommonAncestor(module_tree, modules):
"""Computes the common ancestor of a set of modules.
module_tree: Dictionary mapping each module to its parent.
modules: Set of modules for which to find the closest common ancestor.
The closest common ancestor.
paths = [_PathFromRoot(module_tree, m) for m in modules]
assert len(paths) > 0
ancestor = None
for level in zip(*paths):
if len(set(level)) != 1:
return ancestor
ancestor = level[0]
return ancestor
def _AllotLibraries(module_tree, libraries_map):
"""Allot all libraries to a module.
module_tree: Dictionary mapping each module to its parent. Modules can map
to None, which is considered the root of the tree.
libraries_map: Dictionary mapping each library to a set of modules, which
depend on the library.
A dictionary mapping mapping each module name to a set of libraries allotted
to the module such that libraries with multiple dependees are allotted to
the closest ancestor.
Exception if some libraries can only be allotted to the None root.
allotment_map = collections.defaultdict(set)
for library, modules in libraries_map.items():
ancestor = _ClosestCommonAncestor(module_tree, modules)
if not ancestor:
raise Exception('Cannot allot libraries for given dependency tree')
return allotment_map
def main(args):
parser = argparse.ArgumentParser()
help='A pair of module name and GN list of libraries a module depends '
'on. Can be specified multiple times.')
help='A JSON file with a key for each module mapping to a list of '
'libraries, which should be packaged into this module.')
help='A pair of parent module name and child module name '
'(format: "<parent>:<child>"). Can be specified multiple times.')
options = parser.parse_args(build_utils.ExpandFileArgs(args))
options.libraries = [(m, build_utils.ParseGnList(l))
for m, l in options.libraries]
# Parse input creating libraries and dependency tree.
libraries_map = collections.defaultdict(set) # Maps each library to its
# dependee modules.
module_tree = {} # Maps each module name to its parent.
for module, libraries in options.libraries:
module_tree[module] = None
for library in libraries:
for parent, child in options.deps:
if module_tree.get(child):
raise Exception('%s cannot have multiple parents' % child)
module_tree[child] = parent
module_tree[parent] = module_tree.get(parent)
# Allot all libraries to a module such that libraries with multiple dependees
# are allotted to the closest ancestor.
allotment_map = _AllotLibraries(module_tree, libraries_map)
# The build system expects there to be a set of libraries even for the modules
# that don't have any libraries allotted.
for module in module_tree:
# Creates missing sets because of defaultdict.
allotment_map[module] = allotment_map[module]
with open(options.output, 'w') as f:
# Write native libraries config and ensure the output is deterministic.
json.dump({m: sorted(l)
for m, l in allotment_map.items()},
if __name__ == '__main__':