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