1#!/usr/bin/env python3
2
3# Copyright 2022 gRPC authors.
4#
5# Licensed under the Apache License, Version 2.0 (the "License");
6# you may not use this file except in compliance with the License.
7# You may obtain a copy of the License at
8#
9#     http://www.apache.org/licenses/LICENSE-2.0
10#
11# Unless required by applicable law or agreed to in writing, software
12# distributed under the License is distributed on an "AS IS" BASIS,
13# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14# See the License for the specific language governing permissions and
15# limitations under the License.
16
17import argparse
18import collections
19from doctest import SKIP
20import multiprocessing
21import os
22import re
23import sys
24
25import run_buildozer
26
27# find our home
28ROOT = os.path.abspath(os.path.join(os.path.dirname(sys.argv[0]), '../..'))
29os.chdir(ROOT)
30
31vendors = collections.defaultdict(list)
32scores = collections.defaultdict(int)
33avoidness = collections.defaultdict(int)
34consumes = {}
35no_update = set()
36buildozer_commands = []
37original_deps = {}
38original_external_deps = {}
39skip_headers = collections.defaultdict(set)
40
41# TODO(ctiller): ideally we wouldn't hardcode a bunch of paths here.
42# We can likely parse out BUILD files from dependencies to generate this index.
43EXTERNAL_DEPS = {
44    'absl/algorithm/container.h':
45        'absl/algorithm:container',
46    'absl/base/attributes.h':
47        'absl/base:core_headers',
48    'absl/base/call_once.h':
49        'absl/base',
50    # TODO(ctiller) remove this
51    'absl/base/internal/endian.h':
52        'absl/base',
53    'absl/base/thread_annotations.h':
54        'absl/base:core_headers',
55    'absl/container/flat_hash_map.h':
56        'absl/container:flat_hash_map',
57    'absl/container/flat_hash_set.h':
58        'absl/container:flat_hash_set',
59    'absl/container/inlined_vector.h':
60        'absl/container:inlined_vector',
61    'absl/cleanup/cleanup.h':
62        'absl/cleanup',
63    'absl/debugging/failure_signal_handler.h':
64        'absl/debugging:failure_signal_handler',
65    'absl/debugging/stacktrace.h':
66        'absl/debugging:stacktrace',
67    'absl/debugging/symbolize.h':
68        'absl/debugging:symbolize',
69    'absl/flags/flag.h':
70        'absl/flags:flag',
71    'absl/flags/marshalling.h':
72        'absl/flags:marshalling',
73    'absl/flags/parse.h':
74        'absl/flags:parse',
75    'absl/functional/any_invocable.h':
76        'absl/functional:any_invocable',
77    'absl/functional/bind_front.h':
78        'absl/functional:bind_front',
79    'absl/functional/function_ref.h':
80        'absl/functional:function_ref',
81    'absl/hash/hash.h':
82        'absl/hash',
83    'absl/memory/memory.h':
84        'absl/memory',
85    'absl/meta/type_traits.h':
86        'absl/meta:type_traits',
87    'absl/numeric/int128.h':
88        'absl/numeric:int128',
89    'absl/random/random.h':
90        'absl/random',
91    'absl/random/distributions.h':
92        'absl/random:distributions',
93    'absl/random/uniform_int_distribution.h':
94        'absl/random:distributions',
95    'absl/status/status.h':
96        'absl/status',
97    'absl/status/statusor.h':
98        'absl/status:statusor',
99    'absl/strings/ascii.h':
100        'absl/strings',
101    'absl/strings/cord.h':
102        'absl/strings:cord',
103    'absl/strings/escaping.h':
104        'absl/strings',
105    'absl/strings/match.h':
106        'absl/strings',
107    'absl/strings/numbers.h':
108        'absl/strings',
109    'absl/strings/str_cat.h':
110        'absl/strings',
111    'absl/strings/str_format.h':
112        'absl/strings:str_format',
113    'absl/strings/str_join.h':
114        'absl/strings',
115    'absl/strings/str_replace.h':
116        'absl/strings',
117    'absl/strings/str_split.h':
118        'absl/strings',
119    'absl/strings/string_view.h':
120        'absl/strings',
121    'absl/strings/strip.h':
122        'absl/strings',
123    'absl/strings/substitute.h':
124        'absl/strings',
125    'absl/synchronization/mutex.h':
126        'absl/synchronization',
127    'absl/synchronization/notification.h':
128        'absl/synchronization',
129    'absl/time/clock.h':
130        'absl/time',
131    'absl/time/time.h':
132        'absl/time',
133    'absl/types/optional.h':
134        'absl/types:optional',
135    'absl/types/span.h':
136        'absl/types:span',
137    'absl/types/variant.h':
138        'absl/types:variant',
139    'absl/utility/utility.h':
140        'absl/utility',
141    'address_sorting/address_sorting.h':
142        'address_sorting',
143    'ares.h':
144        'cares',
145    'fuzztest/fuzztest.h': ['fuzztest', 'fuzztest_main'],
146    'google/api/monitored_resource.pb.h':
147        'google/api:monitored_resource_cc_proto',
148    'google/devtools/cloudtrace/v2/tracing.grpc.pb.h':
149        'googleapis_trace_grpc_service',
150    'google/logging/v2/logging.grpc.pb.h':
151        'googleapis_logging_grpc_service',
152    'google/logging/v2/logging.pb.h':
153        'googleapis_logging_cc_proto',
154    'google/logging/v2/log_entry.pb.h':
155        'googleapis_logging_cc_proto',
156    'google/monitoring/v3/metric_service.grpc.pb.h':
157        'googleapis_monitoring_grpc_service',
158    'gmock/gmock.h':
159        'gtest',
160    'gtest/gtest.h':
161        'gtest',
162    'opencensus/exporters/stats/stackdriver/stackdriver_exporter.h':
163        'opencensus-stats-stackdriver_exporter',
164    'opencensus/exporters/trace/stackdriver/stackdriver_exporter.h':
165        'opencensus-trace-stackdriver_exporter',
166    'opencensus/trace/context_util.h':
167        'opencensus-trace-context_util',
168    'opencensus/trace/propagation/grpc_trace_bin.h':
169        'opencensus-trace-propagation',
170    'opencensus/tags/context_util.h':
171        'opencensus-tags-context_util',
172    'opencensus/trace/span_context.h':
173        'opencensus-trace-span_context',
174    'openssl/base.h':
175        'libssl',
176    'openssl/bio.h':
177        'libssl',
178    'openssl/bn.h':
179        'libcrypto',
180    'openssl/buffer.h':
181        'libcrypto',
182    'openssl/crypto.h':
183        'libcrypto',
184    'openssl/digest.h':
185        'libssl',
186    'openssl/engine.h':
187        'libcrypto',
188    'openssl/err.h':
189        'libcrypto',
190    'openssl/evp.h':
191        'libcrypto',
192    'openssl/hmac.h':
193        'libcrypto',
194    'openssl/pem.h':
195        'libcrypto',
196    'openssl/rsa.h':
197        'libcrypto',
198    'openssl/sha.h':
199        'libcrypto',
200    'openssl/ssl.h':
201        'libssl',
202    'openssl/tls1.h':
203        'libssl',
204    'openssl/x509.h':
205        'libcrypto',
206    'openssl/x509v3.h':
207        'libcrypto',
208    're2/re2.h':
209        're2',
210    'upb/arena.h':
211        'upb_lib',
212    'upb/base/string_view.h':
213        'upb_lib',
214    'upb/collections/map.h':
215        'upb_collections_lib',
216    'upb/def.h':
217        'upb_lib',
218    'upb/json_encode.h':
219        'upb_json_lib',
220    'upb/mem/arena.h':
221        'upb_lib',
222    'upb/text_encode.h':
223        'upb_textformat_lib',
224    'upb/def.hpp':
225        'upb_reflection',
226    'upb/upb.h':
227        'upb_lib',
228    'upb/upb.hpp':
229        'upb_lib',
230    'xxhash.h':
231        'xxhash',
232    'zlib.h':
233        'madler_zlib',
234}
235
236INTERNAL_DEPS = {
237    "test/core/event_engine/fuzzing_event_engine/fuzzing_event_engine.h":
238        "//test/core/event_engine/fuzzing_event_engine",
239    "test/core/event_engine/fuzzing_event_engine/fuzzing_event_engine.pb.h":
240        "//test/core/event_engine/fuzzing_event_engine:fuzzing_event_engine_proto",
241    'google/api/expr/v1alpha1/syntax.upb.h':
242        'google_type_expr_upb',
243    'google/rpc/status.upb.h':
244        'google_rpc_status_upb',
245    'google/protobuf/any.upb.h':
246        'protobuf_any_upb',
247    'google/protobuf/duration.upb.h':
248        'protobuf_duration_upb',
249    'google/protobuf/struct.upb.h':
250        'protobuf_struct_upb',
251    'google/protobuf/timestamp.upb.h':
252        'protobuf_timestamp_upb',
253    'google/protobuf/wrappers.upb.h':
254        'protobuf_wrappers_upb',
255    'grpc/status.h':
256        'grpc_public_hdrs',
257    'src/proto/grpc/channelz/channelz.grpc.pb.h':
258        '//src/proto/grpc/channelz:channelz_proto',
259    'src/proto/grpc/core/stats.pb.h':
260        '//src/proto/grpc/core:stats_proto',
261    'src/proto/grpc/health/v1/health.upb.h':
262        'grpc_health_upb',
263    'src/proto/grpc/lb/v1/load_reporter.grpc.pb.h':
264        '//src/proto/grpc/lb/v1:load_reporter_proto',
265    'src/proto/grpc/lb/v1/load_balancer.upb.h':
266        'grpc_lb_upb',
267    'src/proto/grpc/reflection/v1alpha/reflection.grpc.pb.h':
268        '//src/proto/grpc/reflection/v1alpha:reflection_proto',
269    'src/proto/grpc/gcp/transport_security_common.upb.h':
270        'alts_upb',
271    'src/proto/grpc/gcp/handshaker.upb.h':
272        'alts_upb',
273    'src/proto/grpc/gcp/altscontext.upb.h':
274        'alts_upb',
275    'src/proto/grpc/lookup/v1/rls.upb.h':
276        'rls_upb',
277    'src/proto/grpc/lookup/v1/rls_config.upb.h':
278        'rls_config_upb',
279    'src/proto/grpc/lookup/v1/rls_config.upbdefs.h':
280        'rls_config_upbdefs',
281    'src/proto/grpc/testing/xds/v3/csds.grpc.pb.h':
282        '//src/proto/grpc/testing/xds/v3:csds_proto',
283    'xds/data/orca/v3/orca_load_report.upb.h':
284        'xds_orca_upb',
285    'xds/service/orca/v3/orca.upb.h':
286        'xds_orca_service_upb',
287    'xds/type/v3/typed_struct.upb.h':
288        'xds_type_upb',
289}
290
291
292class FakeSelects:
293
294    def config_setting_group(self, **kwargs):
295        pass
296
297
298num_cc_libraries = 0
299num_opted_out_cc_libraries = 0
300parsing_path = None
301
302
303# Convert the source or header target to a relative path.
304def _get_filename(name, parsing_path):
305    filename = '%s%s' % (
306        (parsing_path + '/' if
307         (parsing_path and not name.startswith('//')) else ''), name)
308    filename = filename.replace('//:', '')
309    filename = filename.replace('//src/core:', 'src/core/')
310    filename = filename.replace('//src/cpp/ext/filters/census:',
311                                'src/cpp/ext/filters/census/')
312    return filename
313
314
315def grpc_cc_library(name,
316                    hdrs=[],
317                    public_hdrs=[],
318                    srcs=[],
319                    select_deps=None,
320                    tags=[],
321                    deps=[],
322                    external_deps=[],
323                    proto=None,
324                    **kwargs):
325    global args
326    global num_cc_libraries
327    global num_opted_out_cc_libraries
328    global parsing_path
329    assert (parsing_path is not None)
330    name = '//%s:%s' % (parsing_path, name)
331    num_cc_libraries += 1
332    if select_deps or 'nofixdeps' in tags:
333        if args.whats_left and not select_deps and 'nofixdeps' not in tags:
334            num_opted_out_cc_libraries += 1
335            print("Not opted in: {}".format(name))
336        no_update.add(name)
337    scores[name] = len(public_hdrs + hdrs)
338    # avoid_dep is the internal way of saying prefer something else
339    # we add grpc_avoid_dep to allow internal grpc-only stuff to avoid each
340    # other, whilst not biasing dependent projects
341    if 'avoid_dep' in tags or 'grpc_avoid_dep' in tags:
342        avoidness[name] += 10
343    if proto:
344        proto_hdr = '%s%s' % ((parsing_path + '/' if parsing_path else ''),
345                              proto.replace('.proto', '.pb.h'))
346        skip_headers[name].add(proto_hdr)
347
348    for hdr in hdrs + public_hdrs:
349        vendors[_get_filename(hdr, parsing_path)].append(name)
350    inc = set()
351    original_deps[name] = frozenset(deps)
352    original_external_deps[name] = frozenset(external_deps)
353    for src in hdrs + public_hdrs + srcs:
354        for line in open(_get_filename(src, parsing_path)):
355            m = re.search(r'^#include <(.*)>', line)
356            if m:
357                inc.add(m.group(1))
358            m = re.search(r'^#include "(.*)"', line)
359            if m:
360                inc.add(m.group(1))
361    consumes[name] = list(inc)
362
363
364def grpc_proto_library(name, srcs, **kwargs):
365    global parsing_path
366    assert (parsing_path is not None)
367    name = '//%s:%s' % (parsing_path, name)
368    for src in srcs:
369        proto_hdr = src.replace('.proto', '.pb.h')
370        vendors[_get_filename(proto_hdr, parsing_path)].append(name)
371
372
373def buildozer(cmd, target):
374    buildozer_commands.append('%s|%s' % (cmd, target))
375
376
377def buildozer_set_list(name, values, target, via=""):
378    if not values:
379        buildozer('remove %s' % name, target)
380        return
381    adjust = via if via else name
382    buildozer('set %s %s' % (adjust, ' '.join('"%s"' % s for s in values)),
383              target)
384    if via:
385        buildozer('remove %s' % name, target)
386        buildozer('rename %s %s' % (via, name), target)
387
388
389def score_edit_distance(proposed, existing):
390    """Score a proposed change primarily by edit distance"""
391    sum = 0
392    for p in proposed:
393        if p not in existing:
394            sum += 1
395    for e in existing:
396        if e not in proposed:
397            sum += 1
398    return sum
399
400
401def total_score(proposal):
402    return sum(scores[dep] for dep in proposal)
403
404
405def total_avoidness(proposal):
406    return sum(avoidness[dep] for dep in proposal)
407
408
409def score_list_size(proposed, existing):
410    """Score a proposed change primarily by number of dependencies"""
411    return len(proposed)
412
413
414def score_best(proposed, existing):
415    """Score a proposed change primarily by dependency score"""
416    return 0
417
418
419SCORERS = {
420    'edit_distance': score_edit_distance,
421    'list_size': score_list_size,
422    'best': score_best,
423}
424
425parser = argparse.ArgumentParser(description='Fix build dependencies')
426parser.add_argument('targets',
427                    nargs='*',
428                    default=[],
429                    help='targets to fix (empty => all)')
430parser.add_argument('--score',
431                    type=str,
432                    default='edit_distance',
433                    help='scoring function to use: one of ' +
434                    ', '.join(SCORERS.keys()))
435parser.add_argument('--whats_left',
436                    action='store_true',
437                    default=False,
438                    help='show what is left to opt in')
439parser.add_argument('--explain',
440                    action='store_true',
441                    default=False,
442                    help='try to explain some decisions')
443parser.add_argument(
444    '--why',
445    type=str,
446    default=None,
447    help='with --explain, target why a given dependency is needed')
448args = parser.parse_args()
449
450for dirname in [
451        "",
452        "src/core",
453        "src/cpp/ext/gcp",
454        "test/core/backoff",
455        "test/core/uri",
456        "test/core/util",
457        "test/core/end2end",
458        "test/core/event_engine",
459        "test/core/filters",
460        "test/core/promise",
461        "test/core/resource_quota",
462        "test/core/transport/chaotic_good",
463        "fuzztest",
464        "fuzztest/core/channel",
465]:
466    parsing_path = dirname
467    exec(
468        open('%sBUILD' % (dirname + '/' if dirname else ''), 'r').read(), {
469            'load': lambda filename, *args: None,
470            'licenses': lambda licenses: None,
471            'package': lambda **kwargs: None,
472            'exports_files': lambda files, visibility=None: None,
473            'bool_flag': lambda **kwargs: None,
474            'config_setting': lambda **kwargs: None,
475            'selects': FakeSelects(),
476            'python_config_settings': lambda **kwargs: None,
477            'grpc_cc_binary': grpc_cc_library,
478            'grpc_cc_library': grpc_cc_library,
479            'grpc_cc_test': grpc_cc_library,
480            'grpc_fuzzer': grpc_cc_library,
481            'grpc_fuzz_test': grpc_cc_library,
482            'grpc_proto_fuzzer': grpc_cc_library,
483            'grpc_proto_library': grpc_proto_library,
484            'select': lambda d: d["//conditions:default"],
485            'glob': lambda files: None,
486            'grpc_end2end_tests': lambda: None,
487            'grpc_upb_proto_library': lambda name, **kwargs: None,
488            'grpc_upb_proto_reflection_library': lambda name, **kwargs: None,
489            'grpc_generate_one_off_targets': lambda: None,
490            'grpc_package': lambda **kwargs: None,
491            'filegroup': lambda name, **kwargs: None,
492            'sh_library': lambda name, **kwargs: None,
493        }, {})
494    parsing_path = None
495
496if args.whats_left:
497    print("{}/{} libraries are opted in".format(
498        num_cc_libraries - num_opted_out_cc_libraries, num_cc_libraries))
499
500
501def make_relative_path(dep, lib):
502    if lib is None:
503        return dep
504    lib_path = lib[:lib.rfind(':') + 1]
505    if dep.startswith(lib_path):
506        return dep[len(lib_path):]
507    return dep
508
509
510if args.whats_left:
511    print("{}/{} libraries are opted in".format(
512        num_cc_libraries - num_opted_out_cc_libraries, num_cc_libraries))
513
514
515# Keeps track of all possible sets of dependencies that could satify the
516# problem. (models the list monad in Haskell!)
517class Choices:
518
519    def __init__(self, library, substitutions):
520        self.library = library
521        self.to_add = []
522        self.to_remove = []
523        self.substitutions = substitutions
524
525    def add_one_of(self, choices, trigger):
526        if not choices:
527            return
528        choices = sum([self.apply_substitutions(choice) for choice in choices],
529                      [])
530        if args.explain and (args.why is None or args.why in choices):
531            print("{}: Adding one of {} for {}".format(self.library, choices,
532                                                       trigger))
533        self.to_add.append(
534            tuple(
535                make_relative_path(choice, self.library) for choice in choices))
536
537    def add(self, choice, trigger):
538        self.add_one_of([choice], trigger)
539
540    def remove(self, remove):
541        for remove in self.apply_substitutions(remove):
542            self.to_remove.append(make_relative_path(remove, self.library))
543
544    def apply_substitutions(self, dep):
545        if dep in self.substitutions:
546            return self.substitutions[dep]
547        return [dep]
548
549    def best(self, scorer):
550        choices = set()
551        choices.add(frozenset())
552
553        for add in sorted(set(self.to_add), key=lambda x: (len(x), x)):
554            new_choices = set()
555            for append_choice in add:
556                for choice in choices:
557                    new_choices.add(choice.union([append_choice]))
558            choices = new_choices
559        for remove in sorted(set(self.to_remove)):
560            new_choices = set()
561            for choice in choices:
562                new_choices.add(choice.difference([remove]))
563            choices = new_choices
564
565        best = None
566
567        def final_scorer(x):
568            return (total_avoidness(x), scorer(x), total_score(x))
569
570        for choice in choices:
571            if best is None or final_scorer(choice) < final_scorer(best):
572                best = choice
573        return best
574
575
576def make_library(library):
577    error = False
578    hdrs = sorted(consumes[library])
579    # we need a little trickery here since grpc_base has channel.cc, which calls grpc_init
580    # which is in grpc, which is illegal but hard to change
581    # once EventEngine lands we can clean this up
582    deps = Choices(library, {'//:grpc_base': ['//:grpc', '//:grpc_unsecure']}
583                   if library.startswith('//test/') else {})
584    external_deps = Choices(None, {})
585    for hdr in hdrs:
586        if hdr in skip_headers[library]:
587            continue
588
589        if hdr == 'systemd/sd-daemon.h':
590            continue
591
592        if hdr == 'src/core/lib/profiling/stap_probes.h':
593            continue
594
595        if hdr.startswith('src/libfuzzer/'):
596            continue
597
598        if hdr == 'grpc/grpc.h' and library.startswith('//test:'):
599            # not the root build including grpc.h ==> //:grpc
600            deps.add_one_of(['//:grpc', '//:grpc_unsecure'], hdr)
601            continue
602
603        if hdr in INTERNAL_DEPS:
604            dep = INTERNAL_DEPS[hdr]
605            if isinstance(dep, list):
606                for d in dep:
607                    deps.add(d, hdr)
608            else:
609                if not ('//' in dep):
610                    dep = '//:' + dep
611                deps.add(dep, hdr)
612            continue
613
614        if hdr in vendors:
615            deps.add_one_of(vendors[hdr], hdr)
616            continue
617
618        if 'include/' + hdr in vendors:
619            deps.add_one_of(vendors['include/' + hdr], hdr)
620            continue
621
622        if '.' not in hdr:
623            # assume a c++ system include
624            continue
625
626        if hdr in EXTERNAL_DEPS:
627            if isinstance(EXTERNAL_DEPS[hdr], list):
628                for dep in EXTERNAL_DEPS[hdr]:
629                    external_deps.add(dep, hdr)
630            else:
631                external_deps.add(EXTERNAL_DEPS[hdr], hdr)
632            continue
633
634        if hdr.startswith('opencensus/'):
635            trail = hdr[len('opencensus/'):]
636            trail = trail[:trail.find('/')]
637            external_deps.add('opencensus-' + trail, hdr)
638            continue
639
640        if hdr.startswith('envoy/'):
641            path, file = os.path.split(hdr)
642            file = file.split('.')
643            path = path.split('/')
644            dep = '_'.join(path[:-1] + [file[1]])
645            deps.add(dep, hdr)
646            continue
647
648        if hdr.startswith('google/protobuf/') and not hdr.endswith('.upb.h'):
649            external_deps.add('protobuf_headers', hdr)
650            continue
651
652        if '/' not in hdr:
653            # assume a system include
654            continue
655
656        is_sys_include = False
657        for sys_path in [
658                'sys',
659                'arpa',
660                'gperftools',
661                'netinet',
662                'linux',
663                'android',
664                'mach',
665                'net',
666                'CoreFoundation',
667        ]:
668            if hdr.startswith(sys_path + '/'):
669                is_sys_include = True
670                break
671        if is_sys_include:
672            # assume a system include
673            continue
674
675        print("# ERROR: can't categorize header: %s used by %s" %
676              (hdr, library))
677        error = True
678
679    deps.remove(library)
680
681    deps = sorted(
682        deps.best(lambda x: SCORERS[args.score](x, original_deps[library])))
683    external_deps = sorted(
684        external_deps.best(lambda x: SCORERS[args.score]
685                           (x, original_external_deps[library])))
686
687    return (library, error, deps, external_deps)
688
689
690def main() -> None:
691    update_libraries = []
692    for library in sorted(consumes.keys()):
693        if library in no_update:
694            continue
695        if args.targets and library not in args.targets:
696            continue
697        update_libraries.append(library)
698    with multiprocessing.Pool(processes=multiprocessing.cpu_count()) as p:
699        updated_libraries = p.map(make_library, update_libraries, 1)
700
701    error = False
702    for library, lib_error, deps, external_deps in updated_libraries:
703        if lib_error:
704            error = True
705            continue
706        buildozer_set_list('external_deps', external_deps, library, via='deps')
707        buildozer_set_list('deps', deps, library)
708
709    run_buildozer.run_buildozer(buildozer_commands)
710
711    if error:
712        sys.exit(1)
713
714
715if __name__ == "__main__":
716    main()
717