• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1#!/usr/bin/env python3
2#
3# Copyright 2019 The Chromium Authors
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
49import action_helpers  # build_utils adds //build to sys.path.
50
51
52def _ModuleLibrariesPair(arg):
53  pos = arg.find(',')
54  assert pos > 0
55  return (arg[:pos], arg[pos + 1:])
56
57
58def _DepPair(arg):
59  parent, child = arg.split(':')
60  return (parent, child)
61
62
63def _PathFromRoot(module_tree, module):
64  """Computes path from root to a module.
65
66  Parameters:
67    module_tree: Dictionary mapping each module to its parent.
68    module: Module to which to compute the path.
69
70  Returns:
71    Path from root the the module.
72  """
73  path = [module]
74  while module_tree.get(module):
75    module = module_tree[module]
76    path = [module] + path
77  return path
78
79
80def _ClosestCommonAncestor(module_tree, modules):
81  """Computes the common ancestor of a set of modules.
82
83  Parameters:
84    module_tree: Dictionary mapping each module to its parent.
85    modules: Set of modules for which to find the closest common ancestor.
86
87  Returns:
88    The closest common ancestor.
89  """
90  paths = [_PathFromRoot(module_tree, m) for m in modules]
91  assert len(paths) > 0
92  ancestor = None
93  for level in zip(*paths):
94    if len(set(level)) != 1:
95      return ancestor
96    ancestor = level[0]
97  return ancestor
98
99
100def _AllotLibraries(module_tree, libraries_map):
101  """Allot all libraries to a module.
102
103  Parameters:
104    module_tree: Dictionary mapping each module to its parent. Modules can map
105      to None, which is considered the root of the tree.
106    libraries_map: Dictionary mapping each library to a set of modules, which
107      depend on the library.
108
109  Returns:
110    A dictionary mapping mapping each module name to a set of libraries allotted
111    to the module such that libraries with multiple dependees are allotted to
112    the closest ancestor.
113
114  Raises:
115    Exception if some libraries can only be allotted to the None root.
116  """
117  allotment_map = collections.defaultdict(set)
118  for library, modules in libraries_map.items():
119    ancestor = _ClosestCommonAncestor(module_tree, modules)
120    if not ancestor:
121      raise Exception('Cannot allot libraries for given dependency tree')
122    allotment_map[ancestor].add(library)
123  return allotment_map
124
125
126def main(args):
127  parser = argparse.ArgumentParser()
128  parser.add_argument(
129      '--libraries',
130      action='append',
131      type=_ModuleLibrariesPair,
132      required=True,
133      help='A pair of module name and GN list of libraries a module depends '
134      'on. Can be specified multiple times.')
135  parser.add_argument(
136      '--output',
137      required=True,
138      help='A JSON file with a key for each module mapping to a list of '
139      'libraries, which should be packaged into this module.')
140  parser.add_argument(
141      '--dep',
142      action='append',
143      type=_DepPair,
144      dest='deps',
145      default=[],
146      help='A pair of parent module name and child module name '
147      '(format: "<parent>:<child>"). Can be specified multiple times.')
148  options = parser.parse_args(build_utils.ExpandFileArgs(args))
149  options.libraries = [(m, action_helpers.parse_gn_list(l))
150                       for m, l in options.libraries]
151
152  # Parse input creating libraries and dependency tree.
153  libraries_map = collections.defaultdict(set)  # Maps each library to its
154  #                                               dependee modules.
155  module_tree = {}  # Maps each module name to its parent.
156  for module, libraries in options.libraries:
157    module_tree[module] = None
158    for library in libraries:
159      libraries_map[library].add(module)
160  for parent, child in options.deps:
161    if module_tree.get(child):
162      raise Exception('%s cannot have multiple parents' % child)
163    module_tree[child] = parent
164    module_tree[parent] = module_tree.get(parent)
165
166  # Allot all libraries to a module such that libraries with multiple dependees
167  # are allotted to the closest ancestor.
168  allotment_map = _AllotLibraries(module_tree, libraries_map)
169
170  # The build system expects there to be a set of libraries even for the modules
171  # that don't have any libraries allotted.
172  for module in module_tree:
173    # Creates missing sets because of defaultdict.
174    allotment_map[module] = allotment_map[module]
175
176  with open(options.output, 'w') as f:
177    # Write native libraries config and ensure the output is deterministic.
178    json.dump({m: sorted(l)
179               for m, l in allotment_map.items()},
180              f,
181              sort_keys=True,
182              indent=2)
183
184
185if __name__ == '__main__':
186  sys.exit(main(sys.argv[1:]))
187