crawler.py

"""
Copyright (c) 2018, salesforce.com, inc.
All rights reserved.
SPDX-License-Identifier: BSD-3-Clause
For full license text, see the LICENSE file in the repo root or https://opensource.org/licenses/BSD-3-Clause


Crawls Bazel BUILD file dependencies and builds a DAG.
"""
from collections import defaultdict
from common import logger
from crawl import artifactgenctx
from crawl import dependency
from crawl import bazel
from crawl import pomparser
from crawl.releasereason import ReleaseReason
import difflib


class Node:
    """
    A single node in the DAG, based on references in BUILD files.
    Each Bazel target gets its own Node instance. Typically, there is one 
    target per bazel package.
    """

    def __init__(self, parent, artifact_def, dependency):
        assert artifact_def is not None, "artifact_def cannot be None"
        assert dependency is not None, "dependency cannot be None"

        # the parent Nodes
        self.parents = [] if parent is None else [parent]
        # parsed metadata (BUILD.pom etc) files
        self.artifact_def = artifact_def
        # the dependency pointing to this target
        self.dependency = dependency
        # all direct child nodes
        self.children = []

    def pretty_print(self):
        self._pretty_print(self, 0)

    def _pretty_print(self, node, indent):
        print("%s%s:%s" % (' '*indent, node.artifact_def.group_id, node.artifact_def.artifact_id))
        for child in node.children:
            self._pretty_print(child, indent+2)


class CrawlerResult:
    """
    Useful bits and pieces that are the outcome of crawling Bazel BUILD files.
    """
    def __init__(self, genctxs, nodes, crawled_bazel_packages):

        # artifactgenctx.ArtifactGenerationContext instances
        self.artifact_generation_contexts = genctxs

        # list of root nodes
        self.nodes = nodes

        # set of Dependency instances, for all crawled bazel packages
        self.crawled_bazel_packages = crawled_bazel_packages


class Crawler:

    def __init__(self, workspace, pom_template, verbose=False):
        self.workspace = workspace
        self.pom_template = pom_template
        self.verbose = verbose # verbose logging
        self.package_to_artifact = {} # bazel package -> artifact def instance
        self.library_to_artifact = defaultdict(list) # library root path -> list of its artifact def instances
        self.library_to_nodes = defaultdict(list) # library root path -> list of its DAG Node instances
        self.target_to_node = {} # bazel target -> Node for that target
        self.target_to_dependencies = {} # bazel_target -> target's deps

        self.genctxs = [] # ArtifactGenerationContext instances
        self.leafnodes = [] # all leafnodes discovered while crawling

    def crawl(self, packages, follow_references=True, force_release=False):
        """
        Crawls Bazel BUILD file dependencies, starting at the specified
        Bazel packages.

        Builds up a DAG of Node instances based on the references in BUILD
        files.
        
        Arguments:

        follow_references: 
            If False, this crawler will not crawl BUILD file references, 
            only processing the packages passed into this method

            This is typically only used for debugging.

        force_release:
            Mark all artifacts as requiring to be released

        Returns a CrawlerResult instance.
        """


        # first we build the initial DAG, by starting with one or more packages
        # and traversing references expressed in BUILD files, specifically
        # deps and runtime deps of single java_library target.
        # there must be only one java_library target defined in each processed
        # bazel package/BUILD file
        nodes = self._crawl_packages(packages, follow_references)
        if self.verbose:
            self._print_debug_output(nodes, "After initial crawl")


        # a library (LIBRARY.root) may have more than one artifact (Bazel
        # package with a BUILD.pom file). since we always release all artifacts
        # belonging to a library together, we need to make sure to gather all
        # artifacts for all libraries referenced. gathering artifacts may drag
        # in more artifacts in different libraries, so we continue until there
        # are no artifacts left to process
        if follow_references:
            missing_packages = self._get_unprocessed_packages()
            if len(missing_packages) > 0:
                while len(missing_packages) > 0:
                    if self.verbose:
                        logger.debug("Discovered additional packages %s" % missing_packages)
                    nodes += self._crawl_packages(missing_packages, follow_references)
                    missing_packages = self._get_unprocessed_packages()

                if self.verbose:
                    self._print_debug_output(nodes, "After adding missing packages")
            else:
                if self.verbose:
                    self._print_debug_banner("No missing packages found")


        # crawling is complete at this point, now process the nodes
        
        # for bazel targets that do not generate a pom 
        # (pom_generation_mode=skip), we still need to handle dependencies;
        # this is the "import bundle" use case.
        # push the dependencies up to the closest parent node that does
        # generate a pom
        self._push_transitives_to_parent()


        # computing the set of dependencies for each Node is done

        # now compute the transitive closure of deps for each node
        target_to_transitive_closure_deps = self._compute_transitive_closures_of_deps()


        # add discovered deps to artifact generation contexts
        self._register_dependencies(target_to_transitive_closure_deps)


        # for each artifact, if its manifest (for ex pom.xml) has changed since
        # the last release (tracked by pom.xml.released), mark the artifact as
        # requiring to be released
        self._check_for_artifact_manifest_changes()


        # figure out whether artifacts need to be released because a transitive
        # dependency needs to be released
        self._calculate_artifact_release_flag(force_release)


        # include only contexts for artifacts that need to be released
        # included in the result
        ctxs = [ctx for ctx in self.genctxs if ctx.artifact_def.requires_release]

        crawled_bazel_packages = self._get_crawled_packages_as_deps()

        return CrawlerResult(ctxs, nodes, crawled_bazel_packages)

    def _register_dependencies(self, target_to_transitive_closure_deps):
        """
        This method sets dependency lists on generaton contexts:

        - the direct dependencies of the artifact
        - the transitive closure of the direct dependenices
        - the transitive closure of the library's dependencies
        """
        for ctx in self.genctxs:
            target_key = self._get_target_key(
                ctx.artifact_def.bazel_package, ctx.dependency)
            directs = self.target_to_dependencies[target_key]
            ctx.register_artifact_directs(directs)
            transitive_closure = target_to_transitive_closure_deps[target_key]
            ctx.register_artifact_transitive_closure(transitive_closure)
            lib_transitive_closure = self\
                ._get_deps_transitive_closure_for_library(
                    ctx.artifact_def.library_path,
                    target_to_transitive_closure_deps)
            ctx.register_library_transitive_closure(lib_transitive_closure)

    def _get_deps_transitive_closure_for_library(self, library_path,
                                                 target_to_transitive_closure_deps):
        all_deps = set()

        nodes = self.library_to_nodes[library_path]
        for n in nodes:
            target_key = self._get_target_key(n.artifact_def.bazel_package, n.dependency)
            all_deps.update(target_to_transitive_closure_deps[target_key])

        # also include every artifact that is part of this library
        # (we have already collected them above if they all reference each
        # other, but these references are not guaranteed)
        artifacts = self.library_to_artifact[library_path]
        for art_def in artifacts:
            all_deps.add(dependency.new_dep_from_maven_artifact_def(art_def))
        return all_deps

    def _get_crawled_packages_as_deps(self):
        deps = [dependency.new_dep_from_maven_artifact_def(art_def) for art_def in self.package_to_artifact.values()]
        deps = set(self._filter_non_artifact_referencing_deps(deps))
        return deps

    def _get_unprocessed_packages(self):
        """
        For each crawled library, ensure we have included all its packages 
        (each package with a BUILD.pom file is a single maven artifact)
        
        Returns a list of strings, the paths to the packages that need to be
        handled.
        """
        all_packages_already_processed = set(self.package_to_artifact.keys())
        processed_libraries = set()
        all_artifacts = list(self.package_to_artifact.values())
        missing_packages = []
        for artifact_def in all_artifacts:
            library_path = artifact_def.library_path
            if library_path not in processed_libraries:
                processed_libraries.add(library_path)
                all_library_packages = set(bazel.query_all_artifact_packages(self.workspace.repo_root_path, library_path))
                missing_packages += all_library_packages.difference(all_packages_already_processed)
        return missing_packages

    def _check_for_artifact_manifest_changes(self):
        """
        For each artifact def not flagged as needing to be released, check 
        whether its current manifest (for ex pom.xml) is different the
        previously released manifest. If it has changed, mark the artifact def
        as needing to be released.
        """
        for ctx in self.genctxs:
            art_def = ctx.artifact_def
            if not art_def.requires_release and art_def.released_pom_content is not None:
                # TODO pomparser
                current_manifest = pomparser.format_for_comparison(ctx.gen_goldfile_manifest())
                previous_manifest = pomparser.format_for_comparison(art_def.released_pom_content)
                manifest_changed = current_manifest != previous_manifest
                if manifest_changed:
                    art_def.requires_release = True
                    # TODO release reason
                    art_def.release_reason = ReleaseReason.POM

                    if self.verbose:
                        logger.debug("pom diff %s %s" % (art_def, art_def.bazel_package))
                        diff = difflib.unified_diff(previous_manifest.splitlines(True), current_manifest.splitlines(True))
                        logger.raw(''.join(diff))
                        logger.debug("%s computed manifest:" % art_def)
                        logger.raw(current_manifest)
                        logger.debug("%s released manifest:" % art_def)
                        logger.raw(previous_manifest)


    def _compute_transitive_closures_of_deps(self):
        """
        For every target, compute its full transitive closure of deps.
        
        Returns a dictionary: target -> iterable of deps (transitive closure)

        For example, with targets:
        A->B->C, each target referencing also some other (3rd party) 
        dependencies, the deps returns for A include the deps of B and C.

        Algorithm: we just walk up from the leafnodes to parents, accumulating
        deps along the way.

        Note that this method requires the target_to_dependencies dictionary
        to be up-to-date.
        """
        target_to_all_dependencies = {}
        for node in self.leafnodes:
            accumulated_deps = []
            self._accumulate_deps_and_walk(node, accumulated_deps,
                                           target_to_all_dependencies)
        return target_to_all_dependencies

    def _accumulate_deps_and_walk(self, node, accumulated_deps,
                                  target_to_all_dependencies):
        """
        node: the current node to process
        accumulated_deps: a list of deps, each node's deps are added to to it
        target_to_all_dependencies: the result dictionary being built
        """
        package = node.artifact_def.bazel_package
        target_key = self._get_target_key(package, node.dependency)
        this_node_deps = self.target_to_dependencies[target_key]

        processed_deps = set() # to remove duplicate deps

        this_node_all_deps = [] # the list we are building in this method

        processed_deps.update(this_node_deps)

        depmd = self.workspace.dependency_metadata
        for dep in this_node_deps:
            # add each dep that is explicitly listed in the BUILD file
            this_node_all_deps.append(dep)
            # for each explicitly listed dep, we add the transitive closure of
            # Maven deps
            # this is an extra lookup because these may not be listed in the
            # BUILD file
            transitives = depmd.get_transitive_closure(dep)
            for transitive in transitives:
                if transitive not in processed_deps:
                    # only add the transitive if it isn't explicitly listed
                    # in the BUILD file and if it wasn't already a handled
                    # transitive from a previous dep
                    this_node_all_deps.append(transitive)
                    processed_deps.add(transitive)


        # when encountering a duplicate dep, we keep this order:
        # 1) current deps from target
        # 2) previous transitive closure computation
        # 3) accumulated deps from child

        this_node_current_transitives = target_to_all_dependencies.get(target_key, ())
        this_node_all_deps += [d for d in this_node_current_transitives if d not in processed_deps]
        processed_deps.update(this_node_all_deps)

        this_node_all_deps += [d for d in accumulated_deps if d not in processed_deps]
        processed_deps.update(this_node_all_deps)

        target_to_all_dependencies[target_key] = this_node_all_deps

        for parent in node.parents:
            accumulated_deps = this_node_all_deps + [d for d in accumulated_deps if d not in processed_deps]
            self._accumulate_deps_and_walk(parent, accumulated_deps,
                                           target_to_all_dependencies)

    def _push_transitives_to_parent(self):
        """
        For special pom generation modes that do not actually produce
        maven artifacts (pom_generation_mode="skip"):
        Given artifacts A->B->C->D, if B and C have "skip" generation mode,
        their deps need to be pushed up to A, so that they are included in
        A's pom.xml. So the final poms generated will be: A->D
        """
        for node in self.leafnodes:
            processed_nodes = set() # Node instances that were already handled
            collected_dep_lists = [] # list of list of deps
            self._push_transitives_and_walk(node, collected_dep_lists, 
                                            processed_nodes)

    def _push_transitives_and_walk(self, node, collected_dep_lists, 
                                   processed_nodes):
        package = node.artifact_def.bazel_package
        target_key = self._get_target_key(package, node.dependency)
        deps = self.target_to_dependencies[target_key]
        if node.artifact_def.pom_generation_mode.produces_artifact:
            if len(collected_dep_lists) > 0:
                deps = self.target_to_dependencies[target_key]
                collected_dep_lists.append(deps)
                deps = self._process_collected_dep_lists(collected_dep_lists)
                self.target_to_dependencies[target_key] = deps
                collected_dep_lists = []
        else:
            if node not in processed_nodes:
                processed_nodes.add(node)
                collected_dep_lists.append(deps)
        for parent in node.parents:
            # important: for each recursive call, we create a copy of
            # collected_dep_lists, because otherwise updates to this list
            # from recursive calls are visible here
            self._push_transitives_and_walk(parent, list(collected_dep_lists),
                                            processed_nodes)

    def _process_collected_dep_lists(self, collected_dep_lists):
        deps = reversed(collected_dep_lists)
        deps = self._flatten_and_dedupe(deps)
        deps = self._filter_non_artifact_referencing_deps(deps)
        return deps

    def _flatten_and_dedupe(self, list_of_lists):
        flattened = []
        processed = set()
        for li in list_of_lists:
            for item in li:
                if item not in processed:
                    flattened.append(item)
                    processed.add(item)
        return flattened

    def _filter_non_artifact_referencing_deps(self, deps):
        return [d for d in deps if d.references_artifact]

    def _calculate_artifact_release_flag(self, force_release):
        """
        Given libraries A->B->C->D, if only C changed, we need to also mark
        the reverse transitive deps as having changed, so that we end up
        releasing A, B and C.

        If force_release is set, all artifacts are marked as requiring 
        releasing.
        """
        # we start with a leafnode, and walk up (the leaf nodes represent
        # packages/maven artifacts, not libraries)
        for node in self.leafnodes:
            if self.verbose:
                print("Propagating release state, starting at leaf node", node.artifact_def.bazel_package)
            processed_nodes = set()
            self._propagate_req_rel(node,
                                    transitive_dep_requires_release=False,
                                    force_release=force_release,
                                    processed_nodes=processed_nodes)

    def _propagate_req_rel(self, node, transitive_dep_requires_release, force_release, processed_nodes):
        if node in processed_nodes:
            return
        processed_nodes.add(node)
        art_def = node.artifact_def
        library_path = art_def.library_path
        all_artifact_defs = self.library_to_artifact[library_path]
        assert len(all_artifact_defs) > 0, "expected some artifact defs"
        sibling_artifact_requires_release, sibling_release_reason = self._any_artifact_requires_releasing(all_artifact_defs)
        if (force_release or
            sibling_artifact_requires_release or
            transitive_dep_requires_release):
            if self.verbose:
                if force_release:
                    print("Library", library_path, "requires release because force is enabled")
                elif sibling_artifact_requires_release:
                    print("Library", library_path, "requires release because", sibling_release_reason, "propagating to parent lib(s)")
                elif transitive_dep_requires_release:
                    print("Library", library_path, "requires release because a child lib requires to be released")
                else:
                    assert False, "bug"
            # update all artifacts belonging to the library at once
            updated_artifact_defs = []
            for artifact_def in all_artifact_defs:
                if force_release or not artifact_def.requires_release:
                    artifact_def.requires_release = True
                    updated_artifact_defs.append(artifact_def)
                    if force_release:
                        artifact_def.release_reason = ReleaseReason.ALWAYS
                    else:
                        if sibling_artifact_requires_release:
                            artifact_def.release_reason = sibling_release_reason
                        elif transitive_dep_requires_release:
                            artifact_def.release_reason = ReleaseReason.TRANSITIVE
                        else:
                            raise Exception("release_reason not set on artifact - this is a bug")
        else: # release not required
            if self.verbose:
                print("Library", library_path, "does not required to be released")
        # process all artifact nodes belonging to the current library, 
        # otherwise we may miss some references to other libraries
        all_artifact_nodes = self.library_to_nodes[library_path]
        for n in all_artifact_nodes:
            for parent in n.parents:
                if parent.artifact_def.library_path == n.artifact_def.library_path:
                    # no need to crawl within the same library
                    continue
                if n.artifact_def.requires_release and not force_release:
                    transitive_dep_requires_release = True
                self._propagate_req_rel(parent,
                                        transitive_dep_requires_release,
                                        force_release,
                                        processed_nodes)

    def _crawl_packages(self, packages, follow_references):
        """
        Returns a list of Node instances, one for each of the specified Bazel
        packages (directories). Each package must have a BUILD.pom file,
        as well as a LIBRARY.root file, either in the same directory as the 
        BUILD.pom file or in a parent directory (for libraries with more than
        one artifact).
        
        follow_references: 
            If False, this method doesn't follow BUILD file references.
        """
        nodes = []
        for package in packages:
            n = self._crawl(package, dep=None, parent_node=None, 
                            follow_references=follow_references)
            nodes.append(n)
        return nodes
    
    def _crawl(self, package, dep, parent_node, follow_references):
        """
        For the specified package, crawl BUILD file dependencies, unless
        follow_references is False.

        The dependency instance is the dependency pointing at this package.

        Returns a Node instance for the crawled package.
        """
        artifact_def = self.workspace.parse_maven_artifact_def(package)
        if artifact_def is None:
            raise Exception("No artifact defined at package %s" % package)
        target_key = self._get_target_key(package, dep, artifact_def)
        if target_key in self.target_to_node:
            # if we have already processed this target, we can re-use the
            # children we discovered previously
            # for example: A -> B -> C is how we found B, and now we got here
            # through another path: A -> Z -> B -> C
            # the parent is different, but the children have to be the same
            cached_node = self.target_to_node[target_key]
            if self.verbose:
                logger.debug("Skipping re-crawling of artifact [%s] with target key [%s]" % (cached_node.artifact_def, target_key))
            # also add the new parent to the cached_node - this is important
            # because we have logic that traverses the nodes from children to
            # parent nodes
            if parent_node is not None:
                assert parent_node not in cached_node.parents
                cached_node.parents.append(parent_node)
                if self.verbose:
                    logger.debug("Adding new parent [%s] to cached node [%s]" % (parent_node.artifact_def.bazel_package, cached_node.artifact_def.bazel_package))
            return cached_node
        else:
            if self.verbose:
                logger.info("Processing [%s]" % target_key)
            
            self.package_to_artifact[package] = artifact_def
            self.library_to_artifact[artifact_def.library_path].append(artifact_def)
            if dep is None:
                # make a real dependency instance here
                # this is a bootstrapping problem: the root
                # artifacts (that we start with) have nothing pointing at them
                dep = dependency.new_dep_from_maven_artifact_def(artifact_def)
            artifactctx = artifactgenctx.ArtifactGenerationContext(
                self.workspace, self.pom_template, artifact_def, dep)
            self.genctxs.append(artifactctx)
            source_deps, all_deps = self._discover_dependencies(artifact_def, dep)
            self.target_to_dependencies[target_key] = all_deps
            if self.verbose:
                logger.debug("Determined deps for artifact: [%s] with target key [%s]" % (artifact_def, target_key))
                logger.debug("Source deps: %s" % "\n".join([str(d) for d in source_deps]))
                logger.debug("All deps: %s" % "\n".join([str(d) for d in all_deps]))
            node = Node(parent_node, artifact_def, dep)
            if follow_references:
                # crawl BUILD file dependencies
                for source_dep in source_deps:
                    child_node = self._crawl(source_dep.bazel_package,
                                             source_dep, node, 
                                             follow_references)
                    node.children.append(child_node)
            self.target_to_node[target_key] = node
            self.library_to_nodes[node.artifact_def.library_path].append(node)
            self._store_if_leafnode(node)
            return node

    def _discover_dependencies(self, artifact_def, dep):
        """
        Discovers the dependencies of the given artifact (bazel target).

        This method returns a tuple of 2 lists of Dependency instances:
            (l1, l2)
            l1: all source dependencies (== references to other bazel packages)
            l2: l1 + all external dependencies
        """
        assert artifact_def is not None
        assert dep is not None, "dep is None for artifact %s" % artifact_def
        all_deps = ()
        if artifact_def.deps is not None:
            all_deps = self.workspace.parse_dep_labels(artifact_def.deps)
        if artifact_def.has_build_file:
            all_deps += self._query_dependencies(artifact_def, dep)

        source_dependencies = []
        ext_dependencies = []
        for dep in all_deps:
            if dep.bazel_package is None:
                ext_dependencies.append(dep)
            else:
                source_dependencies.append(dep)
        
        return (tuple(source_dependencies), tuple(all_deps))

    # this method delegates to bazel query to get the value of a bazel target's 
    # "deps" and "runtime_deps" attributes
    def _query_dependencies(self, artifact_def, dependency):
        if not artifact_def.include_deps:
            return ()
        else:
            assert artifact_def.bazel_package is not None
            assert dependency.bazel_target is not None
            assert len(dependency.bazel_target) > 0
            label = "%s:%s" % (artifact_def.bazel_package, dependency.bazel_target)
            try:
                # the rule attributes to query for dependencies, typically
                # "deps" and "runtime_deps"
                attrs = artifact_def.pom_generation_mode.dependency_attributes
                dep_labels = bazel.query_java_library_deps_attributes(
                    self.workspace.repo_root_path, label, attrs,
                    self.workspace.verbose)
                deps = self.workspace.parse_dep_labels(dep_labels)
                return self.workspace.normalize_deps(artifact_def, deps)
            except Exception as e:
                msg = e.message if hasattr(e, "message") else type(e)
                raise Exception("Error while processing dependencies: %s %s caused by %s\nOne possible cause for this error is that the java_libary rule that builds the jar artifact is not the default bazel package target (same name as dir it lives in)" % (msg, artifact_def, repr(e)))

    @classmethod
    def _get_target_key(clazz, package, dep, artifact_def=None):
        if dep is None:
            # initial bootstrap - we start a bazel package and we don't
            # have a dep pointing here
            assert artifact_def is not None
            target = artifact_def.bazel_target
        else:
            target = dep.bazel_target
        assert target is not None, "Target is None for package %s" % package
        return "%s:%s" % (package, target)

    def _store_if_leafnode(self, node):
        if len(node.children) == 0:
            self.leafnodes.append(node)

    def _any_artifact_requires_releasing(self, artifact_defs):
        """
        Returns whether at least one of the specified artifacts requires
        releasing, and its release_reason, as a tuple.
        """
        for art_def in artifact_defs:
            if art_def.requires_release:
                return (True, art_def.release_reason)
        return (False, None)

    def _print_debug_output(self, nodes, msg):
        """
        Debugging only - verbose output about the specified nodes.
        """
        self._print_debug_banner(msg)
        logger.raw("Top level nodes\n")
        for node in nodes:
            logger.raw("   %s\n" % node.artifact_def.bazel_package)
        logger.raw("\nCrawling children\n")
        leaf_nodes = []
        for node in nodes:
            self._debug_crawl_children(node, indent=0, leaf_nodes=leaf_nodes)
        logger.raw("\nLeaf nodes (without children)\n")
        for node in leaf_nodes:
            logger.raw("  %s\n" % node.artifact_def.bazel_package)
        logger.raw("\nCrawling parents (starting at leaf nodes)\n")
        for node in leaf_nodes:
            self._debug_crawl_parents(node, indent=0)
        logger.raw("\n")

    def _debug_crawl_children(self, node, indent, leaf_nodes):
        logger.raw("%s%s\n" % ("  "*indent, node.artifact_def.bazel_package))
        if len(node.children) == 0:
            if node.artifact_def.bazel_package not in [n.artifact_def.bazel_package for n in leaf_nodes]:
                leaf_nodes.append(node)
        else:
            for child in node.children:
                self._debug_crawl_children(child, indent+1, leaf_nodes)

    def _debug_crawl_parents(self, node, indent):
        logger.raw("%s%s\n" % ("  "*indent, node.artifact_def.bazel_package))
        for parent in node.parents:
            self._debug_crawl_parents(parent, indent+1)

    def _print_debug_banner(self, msg):
        sep = "========================================="
        logger.raw("%s\n" % sep)
        logger.raw("    %s\n" % msg)
        logger.raw("%s\n\n" % sep)