• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1# Copyright 2023 The Pigweed Authors
2#
3# Licensed under the Apache License, Version 2.0 (the "License"); you may not
4# use this file except in compliance with the License. You may obtain a copy of
5# the License at
6#
7#     https://www.apache.org/licenses/LICENSE-2.0
8#
9# Unless required by applicable law or agreed to in writing, software
10# distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11# WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12# License for the specific language governing permissions and limitations under
13# the License.
14"""Utilities for manipulating GN configs."""
15
16from __future__ import annotations
17
18from collections import deque
19from json import loads as json_loads, dumps as json_dumps
20from typing import Any, Deque, Iterable, Iterator, Set
21
22from pw_build.gn_utils import GnLabel, MalformedGnError
23
24GN_CONFIG_FLAGS = [
25    'asmflags',
26    'cflags',
27    'cflags_c',
28    'cflags_cc',
29    'cflags_objc',
30    'cflags_objcc',
31    'defines',
32    'include_dirs',
33    'inputs',
34    'ldflags',
35    'lib_dirs',
36    'libs',
37    'precompiled_header',
38    'precompiled_source',
39    'rustenv',
40    'rustflags',
41    'swiftflags',
42    'testonly',
43]
44
45_INTERNAL_FLAGS = ['nested', 'public_defines']
46
47
48def _get_prefix(flag: str) -> str:
49    """Returns the prefix used to identify values for a particular flag.
50
51    Combining all values in a single set allows methods like `exact_cover` to
52    analyze configs for patterns, but the values also need to be able to be
53    separated out again. This prefix pattern is chosen as it is guaranteed not
54    to be a valid source-relative path or label in GN or Bazel. It is
55    encapsulated into its own function to encourage consistency and
56    maintainability.
57
58    Args:
59        flag: The flag to convert to a prefix.
60    """
61    return f'{flag}::'
62
63
64class GnConfig:
65    """Represents a GN config.
66
67    Attributes:
68        label: The GN label of this config.
69        values: A set of config values, prefixed by type. For example, a C
70            compiler flag might be 'cflag::-foo'.
71    """
72
73    def __init__(self, public: bool = False, json: str | None = None) -> None:
74        """Create a GN config object.
75
76        Args:
77            public: Indicates if this is a `public_config`.
78            json: If provided, populates this object from a JSON string.
79        """
80        self.label: GnLabel | None = None
81        self.values: Set[str] = set()
82        self._public: bool = public
83        self._usages: int = 0
84        if json:
85            self._from_json(json)
86
87    def __lt__(self, other: GnConfig) -> bool:
88        """Compares two configs.
89
90        A config is said to be "less than" another if it comes before the other
91        when ordered according to the following rules, evaluated in order:
92            * Public configs come before regular configs.
93            * More frequently used configs come before those used less.
94            * Shorter configs (in terms of values) come before longer ones.
95            * Configs whose label comes before the other's comes first.
96            * If all else fails, the configs are converted to strings and
97              compared lexicographically.
98        """
99        if self._public != other.public():
100            return not self._public and other.public()
101        if self._usages != other._usages:
102            return self._usages < other._usages
103        if len(self.values) != len(other.values):
104            return len(self.values) < len(other.values)
105        if self.label != other.label:
106            return str(self.label) < str(other.label)
107        return str(self) < str(other)
108
109    def __eq__(self, other) -> bool:
110        return (
111            isinstance(other, GnConfig)
112            and self._public == other.public()
113            and self._usages == other._usages
114            and self.values == other.values
115            and self.label == other.label
116        )
117
118    def __hash__(self) -> int:
119        return hash((self._public, self._usages, str(self)))
120
121    def __str__(self) -> str:
122        return self.to_json()
123
124    def __bool__(self) -> bool:
125        return bool(self.values)
126
127    def _from_json(self, data: str) -> None:
128        """Populates this config from a JSON string.
129
130        Args:
131            data: A JSON representation of a config.
132        """
133        obj = json_loads(data)
134        if 'label' in obj:
135            self.label = GnLabel(obj['label'])
136        for flag in GN_CONFIG_FLAGS + _INTERNAL_FLAGS:
137            if flag in obj:
138                self.add(flag, *obj[flag])
139        if 'public' in obj:
140            self._public = bool(obj['public'])
141        if 'usages' in obj:
142            self._usages = int(obj['usages'])
143
144    def to_json(self) -> str:
145        """Returns a JSON representation of this config."""
146        obj: dict[str, Any] = {}
147        if self.label:
148            obj['label'] = str(self.label)
149        for flag in GN_CONFIG_FLAGS + _INTERNAL_FLAGS:
150            if self.has(flag):
151                obj[flag] = list(self.get(flag))
152        if self._public:
153            obj['public'] = self._public
154        if self._usages:
155            obj['usages'] = self._usages
156        return json_dumps(obj)
157
158    def has(self, flag: str) -> bool:
159        """Returns whether this config has values for the given flag.
160
161        Args:
162            flag: The flag to check for.
163        """
164        return any(v.startswith(_get_prefix(flag)) for v in self.values)
165
166    def add(self, flag: str, *values: str) -> None:
167        """Adds a value to this config for the given flag.
168
169        Args:
170            flag: The flag to add values for.
171        Variable Args:
172            values: Strings to associate with the given flag.
173        """
174        if flag not in GN_CONFIG_FLAGS and flag not in _INTERNAL_FLAGS:
175            raise MalformedGnError(f'invalid flag: {flag}')
176        self.values |= {f'{_get_prefix(flag)}{v}' for v in values}
177
178    def get(self, flag: str) -> Iterator[str]:
179        """Iterates over the values for the given flag.
180
181        Args:
182            flag: the flag to look up.
183        """
184        prefix = _get_prefix(flag)
185        for value in self.values:
186            if value.startswith(prefix):
187                yield value[len(prefix) :]
188
189    def take(self, flag: str) -> Iterable[str]:
190        """Extracts and returns the set of values for the given flag.
191
192        Args:
193            flag: The flag to remove and return values for.
194        """
195        prefix = _get_prefix(flag)
196        taken = {v for v in self.values if v.startswith(prefix)}
197        self.values = self.values - taken
198        return [v[len(prefix) :] for v in taken]
199
200    def deduplicate(self, *configs: GnConfig) -> Iterator[GnConfig]:
201        """Removes values found in the given configs.
202
203        Values are only removed if all of the values in a config are present.
204        Returns the configs which resulte in values being removed.
205
206        Variable Args:
207            configs: The configs whose values should be removed from this config
208
209        Raises:
210            ValueError if any of the given configs do not have a label.
211        """
212        matching = []
213        for config in configs:
214            if not config.label:
215                raise ValueError('config has no label')
216            if not config:
217                continue
218            if config.values <= self.values:
219                matching.append(config)
220        matching.sort(key=lambda config: len(config.values), reverse=True)
221        for config in matching:
222            if config.values & self.values:
223                self.values = self.values - config.values
224                yield config
225
226    def within(self, config: GnConfig) -> bool:
227        """Returns whether the values of this config are a subset of another.
228
229        Args:
230            config: The config whose values are checked.
231        """
232        return self.values <= config.values
233
234    def count_usages(self, configs: Iterable[GnConfig]) -> int:
235        """Counts how many other configs this config is within.
236
237        Args:
238            configs: The set of configs which may contain this object's values.
239        """
240        self._usages = sum(map(self.within, configs))
241        return self._usages
242
243    def public(self) -> bool:
244        """Returns whether this object represents a public config."""
245        return self._public
246
247    def extract_public(self) -> GnConfig:
248        """Extracts and returns the set of values that need to be public.
249
250        'include_dirs' and public 'defines' for a GN target need to be forwarded
251        to anything that depends on that target.
252        """
253        public = GnConfig(public=True)
254        public.add('include_dirs', *(self.take('include_dirs')))
255        public.add('defines', *(self.take('public_defines')))
256        return public
257
258    def generate_label(self, label: GnLabel, index: int) -> None:
259        """Creates a label for this config."""
260        name = label.name().replace('-', '_')
261        name = f'{name}_' or ''
262        public = 'public_' if self._public else ''
263        self.label = GnLabel(f'{label.dir()}:{name}{public}config{index}')
264
265
266def _exact_cover(*configs: GnConfig) -> Iterator[GnConfig]:
267    """Returns the exact covering set of configs for a given set of configs.
268
269    An exact cover of a sequence of sets is the smallest set of subsets such
270    that each element in the union of sets appears in exactly one subset. In
271    other words, the subsets are disjoint and every set in the original sequence
272    equals some union of subsets.
273
274    As a side effect, this also separates public and regular flags, as GN
275    targets have separate lists for `public_configs` and `configs`.
276
277    Variables Args:
278        configs: The set of configs to produce an exact cover for.
279    """
280    pending: Deque[Set[str]] = deque([config.values for config in configs])
281    intermediate: Deque[Set[str]] = deque()
282    disjoint: Deque[Set[str]] = deque()
283    while pending:
284        config_a = pending.popleft()
285        if not config_a:
286            continue
287        ok = True
288        while disjoint:
289            intermediate.append(disjoint.popleft())
290        while intermediate:
291            config_b = intermediate.popleft()
292            ok = False
293            if config_a == config_b:
294                disjoint.append(config_b)
295                break
296            if config_a < config_b:
297                pending.append(config_b - config_a)
298                disjoint.append(config_a)
299                break
300            if config_a > config_b:
301                pending.append(config_a - config_b)
302                disjoint.append(config_b)
303                break
304            config_c = config_a & config_b
305            if config_c:
306                pending.append(config_a - config_c)
307                pending.append(config_b - config_c)
308                pending.append(config_c)
309                break
310            ok = True
311            disjoint.append(config_b)
312        if ok:
313            disjoint.append(config_a)
314
315    for values in disjoint:
316        config = GnConfig()
317        config.values = values
318        public = config.extract_public()
319        if public:
320            yield public
321        if config:
322            yield config
323
324
325def _filter_by_usage(
326    covers: Iterator[GnConfig], extract_public: bool, *configs: GnConfig
327) -> Iterable[GnConfig]:
328    """Filters configs to only include public or those used at least 3 times.
329
330    Args:
331        covers: A set of configs that is an exact cover for `configs`.
332        extract_public: If true, all public configs are yielded.
333
334    Variable Args:
335        configs: A set of configs being conslidated.
336    """
337    for cover in covers:
338        if cover.count_usages(configs) > 2 or (
339            extract_public and cover.public()
340        ):
341            yield cover
342
343
344def consolidate_configs(
345    label: GnLabel, *configs: GnConfig, **kwargs
346) -> Iterator[GnConfig]:
347    """Extracts and returns the most common sub-configs across a set of configs.
348
349    See also `_exact_cover`. An exact cover of configs can be used to find the
350    most common sub-configs. These sub-configs are given labels, and then
351    replaced in the original configs.
352
353    Callers may optionally set the keyword argument of `extract_public` to
354    `True` if all public configs should be extracted, regardless of usage count.
355    Flags like `include_dirs` must be in a GN `public_config` to be forwarded,
356    so this is useful for the first consolidation of configs corresponding to a
357    Bazel package. Subsequent consolidations, i.e. for a group of Bazel
358    packages, may want to avoid pulling public configs out of packages and omit
359    this parameter.
360
361    Args:
362        label: The base label to use for generated configs.
363
364    Variable Args:
365        configs: Configs to examine for common, interesting shared sub-configs.
366
367    Keyword Args:
368        extract_public: If true, always considers public configs "interesting".
369    """
370    extract_public = kwargs.get('extract_public', False)
371    covers = list(
372        _filter_by_usage(_exact_cover(*configs), extract_public, *configs)
373    )
374    covers.sort(reverse=True)
375    public_i = 1
376    config_j = 1
377    for cover in covers:
378        if cover.public():
379            cover.generate_label(label, public_i)
380            public_i += 1
381        else:
382            cover.generate_label(label, config_j)
383            config_j += 1
384        yield cover
385