Re: [edk2-devel] [Patch 1/1] BaseTools/Scripts: Add package dependency graphing tool

["Ni, Ray" <ray.ni@intel.com>]

Mike,
This pkg dep tool can tell through weight when a module depends on a new pkg.
But it cannot tell when a module depends on another PCD/Protocol/Guid/Ppi/Library which belongs to an already-depended pkg.

Failure to tell such information may make a bad module (that violates the dependency rules) worse (wrongly depend on more interfaces).

Do you think that the tool can be enhanced in future to detect the case?

Thanks,
Ray

> -----Original Message-----
> From: devel@edk2.groups.io <devel@edk2.groups.io> On Behalf Of Ni, Ray
> Sent: Monday, December 16, 2019 1:57 PM
> To: Kinney, Michael D <michael.d.kinney@intel.com>; devel@edk2.groups.io
> Cc: Feng, Bob C <bob.c.feng@intel.com>; Gao, Liming
> <liming.gao@intel.com>; Sean Brogan <sean.brogan@microsoft.com>; Bret
> Barkelew <Bret.Barkelew@microsoft.com>
> Subject: Re: [edk2-devel] [Patch 1/1] BaseTools/Scripts: Add package
> dependency graphing tool
> 
> Mike,
> 2 minor comments regarding the help string in below.
> 
> > -----Original Message-----
> > From: Kinney, Michael D <michael.d.kinney@intel.com>
> > Sent: Saturday, December 14, 2019 3:45 AM
> > To: devel@edk2.groups.io
> > Cc: Ni, Ray <ray.ni@intel.com>; Feng, Bob C <bob.c.feng@intel.com>; Gao,
> > Liming <liming.gao@intel.com>; Sean Brogan
> <sean.brogan@microsoft.com>;
> > Bret Barkelew <Bret.Barkelew@microsoft.com>
> > Subject: [Patch 1/1] BaseTools/Scripts: Add package dependency graphing
> > tool
> >
> > https://bugzilla.tianocore.org/show_bug.cgi?id=2161
> >
> > Add python script that recursively scans a directory for EDK II
> > packages and generates GraphViz dot input that is used to render
> > a graph of package dependencies in SVG format.
> >
> > Detects following error/warning conditions:
> > * Ambiguous dependencies (multiple matches)
> > * Unresolved dependencies
> > * Circular dependencies
> > * Nested packages
> >
> > usage: PackageDependencyGraph [-h] [-w WORKSPACE] [-p
> PACKAGESPATH]
> >                               [-d DOTOUTPUTFILE] [-o SVGOUTPUTFILE]
> >                               [-g IGNOREDIRECTORY] [-k SKIPPACKAGE]
> >                               [-s] [-u] [-l] [-f] [-b] [-v] [-q]
> >                               [--debug [0-9]]
> >
> > Recursively scan a directory for EDK II packages and generate GraphViz dot
> > input that is used to render a graph of package dependencies in SVG
> format.
> > Copyright (c) 2019, Intel Corporation. All rights reserved.
> >
> > optional arguments:
> >   -h, --help            show this help message and exit
> >   -w WORKSPACE, --workspace WORKSPACE
> >                         Directory to recursively scan for EDK II packages.
> >                         Default is current directory.
> >   -p PACKAGESPATH, --packages-path PACKAGESPATH
> >                         List of directories to recursively scan for EDK II
> >                         packages.
> >   -d DOTOUTPUTFILE, --dot-output DOTOUTPUTFILE
> >                         DOT output filename.
> >   -o OUTPUTFILE, --output OUTPUTFILE
> >                         SVG output filename.
> >   -g IGNOREDIRECTORY, --ignore-directory IGNOREDIRECTORY
> >                         Name of directory to ignore. Option can be repeated
> >                         to ignore multiple directories.
> 
> 1. Name of directory to ignore when scanning for EDKII Module INFs.
> 
> >   -k SKIPPACKAGE, --skip-package SKIPPACKAGE
> >                         Name of EDK II Package DEC file to skip. Option can
> >                         be repeated to skip multiple EDK II packages.
> 
> 2. Name of EDK II Package DEC file (including .DEC suffix) to skip. Option can
> Be repeated to skip multiple EDK II packages.
> 
> >   -s, --self-dependency
> >                         Include self links in dependency graph. Default is
> >                         disabled.
> >   -u, --unresolved      Include unresolved EDK II packages in dependency
> >                         graph. Default is disabled.
> >   -l, --label           Label links with the number of EDK II package
> >                         dependencies. Default is disabled.
> >   -f, --full-paths      Label package nodes with full path to EDK II
> >                         package.  Default is disabled.
> >   -b, --web-browser     Display SVG output file in default web browser.
> >                         Default is disabled.
> >   -v, --verbose         Increase output messages
> >   -q, --quiet           Reduce output messages
> >   --debug [0-9]         Set debug level
> >
> > Cc: Ray Ni <ray.ni@intel.com>
> > Cc: Bob Feng <bob.c.feng@intel.com>
> > Cc: Liming Gao <liming.gao@intel.com>
> > Cc: Sean Brogan <sean.brogan@microsoft.com>
> > Cc: Bret Barkelew <Bret.Barkelew@microsoft.com>
> > Signed-off-by: Michael D Kinney <michael.d.kinney@intel.com>
> > ---
> >  BaseTools/Scripts/PackageDependencyGraph.py | 296
> > ++++++++++++++++++++
> >  1 file changed, 296 insertions(+)
> >  create mode 100644 BaseTools/Scripts/PackageDependencyGraph.py
> >
> > diff --git a/BaseTools/Scripts/PackageDependencyGraph.py
> > b/BaseTools/Scripts/PackageDependencyGraph.py
> > new file mode 100644
> > index 0000000000..b3c8e41774
> > --- /dev/null
> > +++ b/BaseTools/Scripts/PackageDependencyGraph.py
> > @@ -0,0 +1,296 @@
> > +# @file
> > +# Recursively scan a directory for EDK II packages and generate GraphViz
> > dot
> > +# input that is used to render a graph of package dependencies in SVG
> > format.
> > +#
> > +# Copyright (c) 2019, Intel Corporation. All rights reserved.<BR>
> > +# SPDX-License-Identifier: BSD-2-Clause-Patent
> > +#
> > +##
> > +
> > +import os
> > +import sys
> > +import argparse
> > +import subprocess
> > +import webbrowser
> > +import networkx as nx
> > +from edk2toollib.uefi.edk2.parsers.inf_parser import InfParser
> > +
> > +#
> > +# Globals for help information
> > +#
> > +__prog__        = 'PackageDependencyGraph'
> > +__copyright__   = 'Copyright (c) 2019, Intel Corporation. All rights
> reserved.'
> > +__description__ = '''Recursively scan a directory for EDK II packages and
> > +generate GraphViz dot input that is used to render a graph of package
> > +dependencies in SVG format.'''
> > +
> > +if __name__ == '__main__':
> > +
> > +    #
> > +    # Create command line argument parser object
> > +    #
> > +    parser = argparse.ArgumentParser (prog = __prog__,
> > +                                      description = __description__ + '\n' + __copyright__,
> > +                                      conflict_handler = 'resolve')
> > +    parser.add_argument ("-w", "--workspace", dest = 'Workspace', default
> =
> > os.curdir,
> > +                         help = "Directory to recursively scan for EDK II packages.
> > Default is current directory.")
> > +    parser.add_argument ("-p", "--packages-path", dest = 'PackagesPath',
> > default = None,
> > +                         help = "List of directories to recursively scan for EDK II
> > packages.")
> > +    parser.add_argument ("-d", "--dot-output", dest = 'DotOutputFile',
> > +                         help = "DOT output filename.")
> > +    parser.add_argument ("-o", "--output", dest = 'SvgOutputFile',
> > +                         help = "SVG output filename.")
> > +    parser.add_argument ("-g", "--ignore-directory", dest =
> 'IgnoreDirectory',
> > action='append', default=[],
> > +                         help = "Name of directory to ignore.  Option can be repeated
> to
> > ignore multiple directories.")
> > +    parser.add_argument ("-k", "--skip-package", dest = 'SkipPackage',
> > action='append', default=[],
> > +                         help = "Name of EDK II Package DEC file to skip.  Option can
> be
> > repeated to skip multiple EDK II packages.")
> > +    parser.add_argument ("-s", "--self-dependency", dest =
> > 'SelfDependency', action = "store_true", default = False,
> > +                         help = "Include self links in dependency graph.  Default is
> > disabled.")
> > +    parser.add_argument ("-u", "--unresolved", dest = 'Unresolved', action
> =
> > "store_true", default=False,
> > +                         help = "Include unresolved EDK II packages in dependency
> > graph.  Default is disabled.")
> > +    parser.add_argument ("-l", "--label", dest = 'Label', action =
> "store_true",
> > default=False,
> > +                         help = "Label links with the number of EDK II package
> > dependencies.  Default is disabled.")
> > +    parser.add_argument ("-f", "--full-paths", dest = 'FullPaths', action =
> > "store_true", default=False,
> > +                         help = "Label package nodes with full path to EDK II package.
> > Default is disabled.")
> > +    parser.add_argument ("-b", "--web-browser", dest = 'WebBrowser',
> > action = "store_true", default=False,
> > +                         help = "Display SVG output file in default web browser.
> Default
> > is disabled.")
> > +    parser.add_argument ("-v", "--verbose", dest = 'Verbose', action =
> > "store_true",
> > +                         help = "Increase output messages")
> > +    parser.add_argument ("-q", "--quiet", dest = 'Quiet', action =
> > "store_true",
> > +                         help = "Reduce output messages")
> > +    parser.add_argument ("--debug", dest = 'Debug', type = int, metavar =
> > '[0-9]', choices = range (0, 10), default = 0,
> > +                         help = "Set debug level")
> > +
> > +    #
> > +    # Parse command line arguments
> > +    #
> > +    args = parser.parse_args ()
> > +
> > +    #
> > +    # Find all EDK II package DEC files
> > +    #
> > +    Components = {}
> > +    SearchPaths = [args.Workspace]
> > +    if args.PackagesPath:
> > +        SearchPaths += args.PackagesPath.split(os.pathsep)
> > +    SearchPaths = [os.path.realpath(x) for x in SearchPaths]
> > +    for SearchPath in SearchPaths:
> > +        for root, dirs, files in os.walk (SearchPath):
> > +            for name in files:
> > +                FilePath = os.path.join (root, name)
> > +                if
> > set(FilePath.split(os.sep)).intersection(set(args.IgnoreDirectory)) != set():
> > +                    if args.Verbose:
> > +                        print ('IGNORE:' + FilePath)
> > +                    continue
> > +                if os.path.splitext(FilePath)[1].lower() in ['.dec']:
> > +                    DecFile = os.path.realpath (FilePath)
> > +                    if os.path.split(DecFile)[1] in args.SkipPackage:
> > +                        if args.Verbose:
> > +                            print ('SKIP:' + DecFile)
> > +                        continue
> > +                    if DecFile not in Components:
> > +                        if args.Verbose:
> > +                            print ('PACKAGE:' + DecFile)
> > +                        Components[DecFile] = {}
> > +
> > +    #
> > +    # Find EDK II component INF files in each EDK II package
> > +    #
> > +    PackageLabels = {}
> > +    UnresolvedPackages = []
> > +    AmbiguousDependencies = []
> > +    for DecFile in Components:
> > +        DecPath = os.path.split (DecFile)[0]
> > +        if DecFile not in PackageLabels:
> > +            PackageLabels[DecFile] = (DecFile.replace(os.path.sep,'\\n'), 'white')
> > +            if not args.FullPaths:
> > +                PackagePath = os.path.relpath(DecFile, os.path.split(DecPath)[0])
> > +                PackageLabels[DecFile] = (PackagePath.replace(os.path.sep,'\\n'),
> > 'white')
> > +        for root, dirs, files in os.walk (DecPath):
> > +            for name in files:
> > +                FilePath = os.path.join(root, name)
> > +                if
> > set(FilePath.split(os.sep)).intersection(set(args.IgnoreDirectory)) != set():
> > +                    if args.Verbose:
> > +                        print ('IGNORE:' + FilePath)
> > +                    continue
> > +                if os.path.splitext(FilePath)[1].lower() in ['.inf']:
> > +                    InfFile = os.path.realpath (FilePath)
> > +                    Inf = InfParser ()
> > +                    Inf.ParseFile (InfFile)
> > +                    DependentPackages = []
> > +                    for Dependency in Inf.PackagesUsed:
> > +                        Dependency = os.path.normpath(Dependency)
> > +                        if os.path.split(Dependency)[1] in args.SkipPackage:
> > +                            if args.Verbose:
> > +                                print ('SKIP:' + Dependency)
> > +                            continue
> > +                        Found = False
> > +                        for SearchPath in SearchPaths:
> > +                            PackagePath = os.path.realpath(os.path.join(SearchPath,
> > Dependency))
> > +                            if os.path.exists(PackagePath):
> > +                                DependentPackages.append(PackagePath)
> > +                                if not args.FullPaths:
> > +                                    PackageLabels[PackagePath] =
> > (Dependency.replace(os.path.sep,'\\n'), 'white')
> > +                                Found = True
> > +                                break
> > +                        if not Found:
> > +                            Count = 0
> > +                            Match = ''
> > +                            for DecFile2 in Components:
> > +                                if DecFile2.endswith(Dependency):
> > +                                    if Count == 0:
> > +                                        Match = DecFile2
> > +                                    Count = Count + 1
> > +                            if Count > 1:
> > +                                AmbiguousDependencies.append (Dependency)
> > +                            if Count == 1:
> > +                                DependentPackages.append(Match)
> > +                                if not args.FullPaths:
> > +                                    PackageLabels[Match] =
> > (Dependency.replace(os.path.sep,'\\n'), 'white')
> > +                                Found = True
> > +                        if not Found and args.Unresolved:
> > +                            if args.Verbose:
> > +                                print ('WARNING: Dependent package not found ' +
> > Dependency)
> > +                            DependentPackages.append(Dependency)
> > +                            UnresolvedPackages.append(Dependency)
> > +                            PackageLabels[Dependency] =
> > (Dependency.replace(os.path.sep,'\\n'), 'white')
> > +                    Components[DecFile][InfFile] = DependentPackages
> > +    if AmbiguousDependencies:
> > +        for Dependency in set(AmbiguousDependencies):
> > +            print ('ERROR: MULTIPLE:   ' + Dependency)
> > +        print ('Use --packages-path to provide search priority.')
> > +        sys.exit(1)
> > +
> > +    #
> > +    # Generate GraphViz dot input file contents.
> > +    # Use networkx to detect circular dependencies.
> > +    #
> > +    MaxWeight = 0
> > +    MaxWeightDecFile = list(Components.keys())[0]
> > +    Graph = nx.DiGraph()
> > +    Edges = []
> > +    for DecFile in Components:
> > +        if args.Verbose:
> > +            print ('PACKAGE DEPENDENCIES:' + DecFile)
> > +        AllDependencies = []
> > +        Dependencies = set()
> > +        for InfFile in Components[DecFile]:
> > +            AllDependencies += Components[DecFile][InfFile]
> > +            Dependencies = Dependencies.union(Components[DecFile][InfFile])
> > +        if not args.SelfDependency:
> > +            Dependencies = Dependencies.difference(set([DecFile]))
> > +        for Dependency in Dependencies:
> > +            Weight = AllDependencies.count(Dependency)
> > +            if Weight > MaxWeight:
> > +                MaxWeight = Weight
> > +                MaxWeightDecFile = DecFile
> > +            if args.Verbose:
> > +                print ('  DEPENDENCY: Weight(' + str(Weight) + ') ' + Dependency)
> > +            Edges.append('  "{Package}" -> "{Dependency}" [label =
> > "{Weight}"];'.format(
> > +                Package    = DecFile,
> > +                Dependency = Dependency,
> > +                Weight     = str(Weight) if args.Label else ''
> > +                ))
> > +            Graph.add_edge(DecFile, Dependency)
> > +    Edges.sort()
> > +
> > +    #
> > +    # Set fill color to yellow if a packages is part of a circular dependency
> > +    #
> > +    for Node in set([x for y in list(nx.simple_cycles(Graph)) for x in y]):
> > +        PackageLabels[Node] = (PackageLabels[Node][0], 'yellow')
> > +        print ('ERROR: CIRCULAR:   ' + Node)
> > +
> > +    #
> > +    # Set fill color to pink if a package that is nested inside another package.
> > +    # Set fill color to orange if a package is nested inside another package
> and
> > +    # is part of a circular dependency.
> > +    #
> > +    for DecFile in Components:
> > +        DecPath = os.path.split (DecFile)[0]
> > +        for DecFile2 in Components:
> > +            if DecFile2 == DecFile:
> > +                continue
> > +            if os.path.commonpath ([DecPath, DecFile2]) != DecPath:
> > +                continue
> > +            if len(DecFile2) < len(DecPath):
> > +                DecFile2 = DecFile
> > +            print ('ERROR: NESTED:     ' + DecFile2)
> > +            if PackageLabels[DecFile2][1] == 'yellow':
> > +                PackageLabels[DecFile2] = (PackageLabels[DecFile2][0], 'orange')
> > +            else:
> > +                PackageLabels[DecFile2] = (PackageLabels[DecFile2][0], 'pink')
> > +
> > +    #
> > +    # Set fill color to red for nodes that are unresolved
> > +    #
> > +    for Node in set(UnresolvedPackages):
> > +        PackageLabels[Node] = (PackageLabels[Node][0], 'red')
> > +        print ('ERROR: UNRESOLVED: ' + Node)
> > +
> > +    #
> > +    # Add node statements to set node label and fill color
> > +    #
> > +    Nodes = []
> > +    for Package in PackageLabels:
> > +        Nodes.append('  "{Package}"
> [label="{Label}",fillcolor={Color}];'.format(
> > +            Package = Package,
> > +            Label = PackageLabels[Package][0],
> > +            Color = PackageLabels[Package][1]
> > +            ))
> > +    Nodes.sort()
> > +
> > +    #
> > +    # Generate dot file from Nodes and Edges and add a Legend at top of
> > graph
> > +    #
> > +    Dot = []
> > +    Dot.append('digraph {')
> > +    Dot.append('  rankdir=BT;')
> > +    Dot.append('  node [shape=Mrecord,style=filled];')
> > +    Dot.append('')
> > +    Dot = Dot + Nodes
> > +    Dot.append('')
> > +    Dot = Dot + Edges
> > +    Dot.append('')
> > +    Dot.append('  subgraph legend {')
> > +    Dot.append('    rank=sink;')
> > +    Dot.append('    Unresolved     [label="Unresolved Dependency",
> > fillcolor=red];')
> > +    Dot.append('    Circular       [label="Circular Dependency",
> > fillcolor=yellow];')
> > +    Dot.append('    Nested         [label="Nested Package",
> > fillcolor=pink];')
> > +    Dot.append('    NestedCircular [label="Nested Package with Circular
> > Dependency",fillcolor=orange];')
> > +    Dot.append('  }')
> > +    if MaxWeightDecFile:
> > +        Dot.append('  Unresolved->"' + MaxWeightDecFile + '" [style=invis];')
> > +    Dot.append('}')
> > +
> > +    if args.DotOutputFile:
> > +        #
> > +        # Write GraphViz dot file contents to DotOutputFile
> > +        #
> > +        with open(os.path.realpath(args.DotOutputFile), 'w') as File:
> > +            File.write('\n'.join(Dot))
> > +    if args.SvgOutputFile:
> > +        #
> > +        # Use GraphViz 'dot' command to generate SVG output file
> > +        #
> > +        args.SvgOutputFile = os.path.realpath(args.SvgOutputFile)
> > +        try:
> > +            Process = subprocess.Popen('dot -Tsvg',
> > +              stdin=subprocess.PIPE,
> > +              stdout=open(args.SvgOutputFile, 'w'),
> > +              stderr=subprocess.PIPE,
> > +              shell=True
> > +              )
> > +            Process.stdin.write ('\n'.join(Dot).encode())
> > +            Process.communicate()
> > +            if Process.returncode != 0:
> > +                print ("ERROR: Can not run GraphViz 'dot' command.  Check install
> > and path.")
> > +                sys.exit(Process.returncode)
> > +        except:
> > +            print ("ERROR: Can not run GraphViz 'dot' command.  Check install
> and
> > path.")
> > +            sys.exit(1)
> > +        #
> > +        # Display SVG file in default web browser
> > +        #
> > +        if args.WebBrowser:
> > +            webbrowser.open(args.SvgOutputFile)
> > --
> > 2.21.0.windows.1
> 
> 
>