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

["Michael D Kinney" <michael.d.kinney@intel.com>]

Ray,

Yes.  More features can be added.  Can you add to the BZ some
examples of the output you would like to see.

https://bugzilla.tianocore.org/show_bug.cgi?id=2161

Thanks,

Mike

> -----Original Message-----
> From: Ni, Ray <ray.ni@intel.com>
> Sent: Monday, December 16, 2019 12:41 AM
> To: devel@edk2.groups.io; Ni, Ray <ray.ni@intel.com>;
> Kinney, Michael D <michael.d.kinney@intel.com>
> 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,
> 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.Ignor
> eDirectory)) != 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.Ignor
> eDirectory)) != 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
> >
> >
> >