1#!/usr/bin/env python 2# 3# Copyright 2019 The Chromium Authors. All rights reserved. 4# Use of this source code is governed by a BSD-style license that can be 5# found in the LICENSE file. 6 7"""Allots libraries to modules to be packaged into. 8 9All libraries that are depended on by a single module will be allotted to this 10module. All other libraries will be allotted to the closest ancestor. 11 12Example: 13 Given the module dependency structure 14 15 c 16 / \ 17 b d 18 / \ 19 a e 20 21 and libraries assignment 22 23 a: ['lib1.so'] 24 e: ['lib2.so', 'lib1.so'] 25 26 will make the allotment decision 27 28 c: ['lib1.so'] 29 e: ['lib2.so'] 30 31 The above example is invoked via: 32 33 ./allot_native_libraries \ 34 --libraries 'a,["1.so"]' \ 35 --libraries 'e,["2.so", "1.so"]' \ 36 --dep c:b \ 37 --dep b:a \ 38 --dep c:d \ 39 --dep d:e \ 40 --output <output JSON> 41""" 42 43import argparse 44import collections 45import json 46import sys 47 48from util import build_utils 49 50 51def _ModuleLibrariesPair(arg): 52 pos = arg.find(',') 53 assert pos > 0 54 return (arg[:pos], arg[pos + 1:]) 55 56 57def _DepPair(arg): 58 parent, child = arg.split(':') 59 return (parent, child) 60 61 62def _PathFromRoot(module_tree, module): 63 """Computes path from root to a module. 64 65 Parameters: 66 module_tree: Dictionary mapping each module to its parent. 67 module: Module to which to compute the path. 68 69 Returns: 70 Path from root the the module. 71 """ 72 path = [module] 73 while module_tree.get(module): 74 module = module_tree[module] 75 path = [module] + path 76 return path 77 78 79def _ClosestCommonAncestor(module_tree, modules): 80 """Computes the common ancestor of a set of modules. 81 82 Parameters: 83 module_tree: Dictionary mapping each module to its parent. 84 modules: Set of modules for which to find the closest common ancestor. 85 86 Returns: 87 The closest common ancestor. 88 """ 89 paths = [_PathFromRoot(module_tree, m) for m in modules] 90 assert len(paths) > 0 91 ancestor = None 92 for level in zip(*paths): 93 if len(set(level)) != 1: 94 return ancestor 95 ancestor = level[0] 96 return ancestor 97 98 99def _AllotLibraries(module_tree, libraries_map): 100 """Allot all libraries to a module. 101 102 Parameters: 103 module_tree: Dictionary mapping each module to its parent. Modules can map 104 to None, which is considered the root of the tree. 105 libraries_map: Dictionary mapping each library to a set of modules, which 106 depend on the library. 107 108 Returns: 109 A dictionary mapping mapping each module name to a set of libraries allotted 110 to the module such that libraries with multiple dependees are allotted to 111 the closest ancestor. 112 113 Raises: 114 Exception if some libraries can only be allotted to the None root. 115 """ 116 allotment_map = collections.defaultdict(set) 117 for library, modules in libraries_map.items(): 118 ancestor = _ClosestCommonAncestor(module_tree, modules) 119 if not ancestor: 120 raise Exception('Cannot allot libraries for given dependency tree') 121 allotment_map[ancestor].add(library) 122 return allotment_map 123 124 125def main(args): 126 parser = argparse.ArgumentParser() 127 parser.add_argument( 128 '--libraries', 129 action='append', 130 type=_ModuleLibrariesPair, 131 required=True, 132 help='A pair of module name and GN list of libraries a module depends ' 133 'on. Can be specified multiple times.') 134 parser.add_argument( 135 '--output', 136 required=True, 137 help='A JSON file with a key for each module mapping to a list of ' 138 'libraries, which should be packaged into this module.') 139 parser.add_argument( 140 '--dep', 141 action='append', 142 type=_DepPair, 143 dest='deps', 144 default=[], 145 help='A pair of parent module name and child module name ' 146 '(format: "<parent>:<child>"). Can be specified multiple times.') 147 options = parser.parse_args(build_utils.ExpandFileArgs(args)) 148 options.libraries = [(m, build_utils.ParseGnList(l)) 149 for m, l in options.libraries] 150 151 # Parse input creating libraries and dependency tree. 152 libraries_map = collections.defaultdict(set) # Maps each library to its 153 # dependee modules. 154 module_tree = {} # Maps each module name to its parent. 155 for module, libraries in options.libraries: 156 module_tree[module] = None 157 for library in libraries: 158 libraries_map[library].add(module) 159 for parent, child in options.deps: 160 if module_tree.get(child): 161 raise Exception('%s cannot have multiple parents' % child) 162 module_tree[child] = parent 163 module_tree[parent] = module_tree.get(parent) 164 165 # Allot all libraries to a module such that libraries with multiple dependees 166 # are allotted to the closest ancestor. 167 allotment_map = _AllotLibraries(module_tree, libraries_map) 168 169 # The build system expects there to be a set of libraries even for the modules 170 # that don't have any libraries allotted. 171 for module in module_tree: 172 # Creates missing sets because of defaultdict. 173 allotment_map[module] = allotment_map[module] 174 175 with open(options.output, 'w') as f: 176 # Write native libraries config and ensure the output is deterministic. 177 json.dump({m: sorted(l) 178 for m, l in allotment_map.items()}, 179 f, 180 sort_keys=True, 181 indent=2) 182 183 184if __name__ == '__main__': 185 sys.exit(main(sys.argv[1:])) 186