From nobody Fri May 3 06:51:31 2024 Delivered-To: importer@patchew.org Received-SPF: pass (zohomail.com: domain of groups.io designates 66.175.222.12 as permitted sender) client-ip=66.175.222.12; envelope-from=bounce+27952+52212+1787277+3901457@groups.io; helo=web01.groups.io; Authentication-Results: mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of groups.io designates 66.175.222.12 as permitted sender) smtp.mailfrom=bounce+27952+52212+1787277+3901457@groups.io; dmarc=fail(p=none dis=none) header.from=intel.com ARC-Seal: i=1; a=rsa-sha256; t=1576266293; cv=none; d=zohomail.com; s=zohoarc; b=LYueC9cqeTeJAJSJmRMbD5DSzJTOrck4LP8iZ86i/90hlRqE/eHVn2K3lCmaD15lb7Aj8s0FhwHFzxPx3AaEHe9JSNlZMukFp0l+1V64Omr7Ux/ct5kWtqbKk3gXaD9oyLK8Nb9CW5h9AGfsYNXaOiCJAdSjdTAMjIGsq99Ir7w= ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=zohomail.com; s=zohoarc; t=1576266293; h=Content-Transfer-Encoding:Cc:Date:From:In-Reply-To:List-Id:List-Unsubscribe:MIME-Version:Message-ID:Reply-To:References:Sender:Subject:To; bh=uZo/nXuaiF4G5vG6gbWBFfmNJ6CRSB1/LLbfD7F1OTo=; b=gSw9o8YV6hNQDWWsVvPnYU8Mey5CdVTxgRcrr3M5WNIRGprFx0Dd6kiJ7CTvh0mvVuUIZ88K2mgqmq3hoO6rOXWmAHmSaUiCNb2mhvUJNED0qef1fSJX/yas8ar2vexEFfB5wgxn5Ut4mvNhYO2YFiq/dG4IW4PvkIzanF2m0L4= ARC-Authentication-Results: i=1; mx.zohomail.com; dkim=pass; spf=pass (zohomail.com: domain of groups.io designates 66.175.222.12 as permitted sender) smtp.mailfrom=bounce+27952+52212+1787277+3901457@groups.io; dmarc=fail header.from= (p=none dis=none) header.from= Received: from web01.groups.io (web01.groups.io [66.175.222.12]) by mx.zohomail.com with SMTPS id 1576266293344182.28474024853097; Fri, 13 Dec 2019 11:44:53 -0800 (PST) Return-Path: X-Received: by 127.0.0.2 with SMTP id dMQKYY1788612xQjwNBcIIX1; Fri, 13 Dec 2019 11:44:52 -0800 X-Received: from mga03.intel.com (mga03.intel.com []) by mx.groups.io with SMTP id smtpd.web10.1043.1576266291545149985 for ; Fri, 13 Dec 2019 11:44:52 -0800 X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False X-Received: from orsmga002.jf.intel.com ([10.7.209.21]) by orsmga103.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 13 Dec 2019 11:44:51 -0800 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.69,309,1571727600"; d="scan'208";a="226375822" X-Received: from unknown (HELO mdkinney-MOBL2.amr.corp.intel.com) ([10.241.98.74]) by orsmga002.jf.intel.com with ESMTP; 13 Dec 2019 11:44:50 -0800 From: "Michael D Kinney" To: devel@edk2.groups.io Cc: Ray Ni , Bob Feng , Liming Gao , Sean Brogan , Bret Barkelew Subject: [edk2-devel] [Patch 1/1] BaseTools/Scripts: Add package dependency graphing tool Date: Fri, 13 Dec 2019 11:44:49 -0800 Message-Id: <20191213194449.7036-2-michael.d.kinney@intel.com> In-Reply-To: <20191213194449.7036-1-michael.d.kinney@intel.com> References: <20191213194449.7036-1-michael.d.kinney@intel.com> MIME-Version: 1.0 Precedence: Bulk List-Unsubscribe: Sender: devel@edk2.groups.io List-Id: Mailing-List: list devel@edk2.groups.io; contact devel+owner@edk2.groups.io Reply-To: devel@edk2.groups.io,michael.d.kinney@intel.com X-Gm-Message-State: Gyp5XRSZX4jpMiyoQ31Zmcnex1787277AA= Content-Transfer-Encoding: quoted-printable DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=groups.io; q=dns/txt; s=20140610; t=1576266292; bh=1llSANJeTuXq+TLWSGM7621GdPnk6x3EjO9MPWpEOyM=; h=Cc:Date:From:Reply-To:Subject:To; b=RWBQo0gl82N3f+H86XbHL9hnWAzKJ/L0Y4wKKBNZpG/mI5DIILWGT2GoZ5vkby5WMcZ EI5kazrtZj10ggcSrkW2kcmP0cl32YA4P11XrlYQTT5wDfXFOAJJ0mubckeXOUmL8D6bD LrG11J7Vng05Bc/NFw1MpVxesiP5XtoUV5k= X-ZohoMail-DKIM: pass (identity @groups.io) Content-Type: text/plain; charset="utf-8" https://bugzilla.tianocore.org/show_bug.cgi?id=3D2161 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. -k SKIPPACKAGE, --skip-package SKIPPACKAGE Name of EDK II Package DEC file 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 Cc: Bob Feng Cc: Liming Gao Cc: Sean Brogan Cc: Bret Barkelew Signed-off-by: Michael D Kinney --- 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/Script= s/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 d= ot +# input that is used to render a graph of package dependencies in SVG form= at. +# +# Copyright (c) 2019, Intel Corporation. All rights reserved.
+# 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__ =3D 'PackageDependencyGraph' +__copyright__ =3D 'Copyright (c) 2019, Intel Corporation. All rights res= erved.' +__description__ =3D '''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__ =3D=3D '__main__': + + # + # Create command line argument parser object + # + parser =3D argparse.ArgumentParser (prog =3D __prog__, + description =3D __description__ + '\= n' + __copyright__, + conflict_handler =3D 'resolve') + parser.add_argument ("-w", "--workspace", dest =3D 'Workspace', defaul= t =3D os.curdir, + help =3D "Directory to recursively scan for EDK I= I packages. Default is current directory.") + parser.add_argument ("-p", "--packages-path", dest =3D 'PackagesPath',= default =3D None, + help =3D "List of directories to recursively scan= for EDK II packages.") + parser.add_argument ("-d", "--dot-output", dest =3D 'DotOutputFile', + help =3D "DOT output filename.") + parser.add_argument ("-o", "--output", dest =3D 'SvgOutputFile', + help =3D "SVG output filename.") + parser.add_argument ("-g", "--ignore-directory", dest =3D 'IgnoreDirec= tory', action=3D'append', default=3D[], + help =3D "Name of directory to ignore. Option ca= n be repeated to ignore multiple directories.") + parser.add_argument ("-k", "--skip-package", dest =3D 'SkipPackage', a= ction=3D'append', default=3D[], + help =3D "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 =3D 'SelfDependen= cy', action =3D "store_true", default =3D False, + help =3D "Include self links in dependency graph.= Default is disabled.") + parser.add_argument ("-u", "--unresolved", dest =3D 'Unresolved', acti= on =3D "store_true", default=3DFalse, + help =3D "Include unresolved EDK II packages in d= ependency graph. Default is disabled.") + parser.add_argument ("-l", "--label", dest =3D 'Label', action =3D "st= ore_true", default=3DFalse, + help =3D "Label links with the number of EDK II p= ackage dependencies. Default is disabled.") + parser.add_argument ("-f", "--full-paths", dest =3D 'FullPaths', actio= n =3D "store_true", default=3DFalse, + help =3D "Label package nodes with full path to E= DK II package. Default is disabled.") + parser.add_argument ("-b", "--web-browser", dest =3D 'WebBrowser', act= ion =3D "store_true", default=3DFalse, + help =3D "Display SVG output file in default web = browser. Default is disabled.") + parser.add_argument ("-v", "--verbose", dest =3D 'Verbose', action =3D= "store_true", + help =3D "Increase output messages") + parser.add_argument ("-q", "--quiet", dest =3D 'Quiet', action =3D "st= ore_true", + help =3D "Reduce output messages") + parser.add_argument ("--debug", dest =3D 'Debug', type =3D int, metava= r =3D '[0-9]', choices =3D range (0, 10), default =3D 0, + help =3D "Set debug level") + + # + # Parse command line arguments + # + args =3D parser.parse_args () + + # + # Find all EDK II package DEC files + # + Components =3D {} + SearchPaths =3D [args.Workspace] + if args.PackagesPath: + SearchPaths +=3D args.PackagesPath.split(os.pathsep) + SearchPaths =3D [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 =3D os.path.join (root, name) + if set(FilePath.split(os.sep)).intersection(set(args.Ignor= eDirectory)) !=3D set(): + if args.Verbose: + print ('IGNORE:' + FilePath) + continue + if os.path.splitext(FilePath)[1].lower() in ['.dec']: + DecFile =3D 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] =3D {} + + # + # Find EDK II component INF files in each EDK II package + # + PackageLabels =3D {} + UnresolvedPackages =3D [] + AmbiguousDependencies =3D [] + for DecFile in Components: + DecPath =3D os.path.split (DecFile)[0] + if DecFile not in PackageLabels: + PackageLabels[DecFile] =3D (DecFile.replace(os.path.sep,'\\n')= , 'white') + if not args.FullPaths: + PackagePath =3D os.path.relpath(DecFile, os.path.split(Dec= Path)[0]) + PackageLabels[DecFile] =3D (PackagePath.replace(os.path.se= p,'\\n'), 'white') + for root, dirs, files in os.walk (DecPath): + for name in files: + FilePath =3D os.path.join(root, name) + if set(FilePath.split(os.sep)).intersection(set(args.Ignor= eDirectory)) !=3D set(): + if args.Verbose: + print ('IGNORE:' + FilePath) + continue + if os.path.splitext(FilePath)[1].lower() in ['.inf']: + InfFile =3D os.path.realpath (FilePath) + Inf =3D InfParser () + Inf.ParseFile (InfFile) + DependentPackages =3D [] + for Dependency in Inf.PackagesUsed: + Dependency =3D os.path.normpath(Dependency) + if os.path.split(Dependency)[1] in args.SkipPackag= e: + if args.Verbose: + print ('SKIP:' + Dependency) + continue + Found =3D False + for SearchPath in SearchPaths: + PackagePath =3D os.path.realpath(os.path.join(= SearchPath, Dependency)) + if os.path.exists(PackagePath): + DependentPackages.append(PackagePath) + if not args.FullPaths: + PackageLabels[PackagePath] =3D (Depend= ency.replace(os.path.sep,'\\n'), 'white') + Found =3D True + break + if not Found: + Count =3D 0 + Match =3D '' + for DecFile2 in Components: + if DecFile2.endswith(Dependency): + if Count =3D=3D 0: + Match =3D DecFile2 + Count =3D Count + 1 + if Count > 1: + AmbiguousDependencies.append (Dependency) + if Count =3D=3D 1: + DependentPackages.append(Match) + if not args.FullPaths: + PackageLabels[Match] =3D (Dependency.r= eplace(os.path.sep,'\\n'), 'white') + Found =3D True + if not Found and args.Unresolved: + if args.Verbose: + print ('WARNING: Dependent package not fou= nd ' + Dependency) + DependentPackages.append(Dependency) + UnresolvedPackages.append(Dependency) + PackageLabels[Dependency] =3D (Dependency.repl= ace(os.path.sep,'\\n'), 'white') + Components[DecFile][InfFile] =3D 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 =3D 0 + MaxWeightDecFile =3D list(Components.keys())[0] + Graph =3D nx.DiGraph() + Edges =3D [] + for DecFile in Components: + if args.Verbose: + print ('PACKAGE DEPENDENCIES:' + DecFile) + AllDependencies =3D [] + Dependencies =3D set() + for InfFile in Components[DecFile]: + AllDependencies +=3D Components[DecFile][InfFile] + Dependencies =3D Dependencies.union(Components[DecFile][InfFil= e]) + if not args.SelfDependency: + Dependencies =3D Dependencies.difference(set([DecFile])) + for Dependency in Dependencies: + Weight =3D AllDependencies.count(Dependency) + if Weight > MaxWeight: + MaxWeight =3D Weight + MaxWeightDecFile =3D DecFile + if args.Verbose: + print (' DEPENDENCY: Weight(' + str(Weight) + ') ' + Depe= ndency) + Edges.append(' "{Package}" -> "{Dependency}" [label =3D "{Wei= ght}"];'.format( + Package =3D DecFile, + Dependency =3D Dependency, + Weight =3D 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 depende= ncy + # + for Node in set([x for y in list(nx.simple_cycles(Graph)) for x in y]): + PackageLabels[Node] =3D (PackageLabels[Node][0], 'yellow') + print ('ERROR: CIRCULAR: ' + Node) + + # + # Set fill color to pink if a package that is nested inside another pa= ckage. + # Set fill color to orange if a package is nested inside another packa= ge and + # is part of a circular dependency. + # + for DecFile in Components: + DecPath =3D os.path.split (DecFile)[0] + for DecFile2 in Components: + if DecFile2 =3D=3D DecFile: + continue + if os.path.commonpath ([DecPath, DecFile2]) !=3D DecPath: + continue + if len(DecFile2) < len(DecPath): + DecFile2 =3D DecFile + print ('ERROR: NESTED: ' + DecFile2) + if PackageLabels[DecFile2][1] =3D=3D 'yellow': + PackageLabels[DecFile2] =3D (PackageLabels[DecFile2][0], '= orange') + else: + PackageLabels[DecFile2] =3D (PackageLabels[DecFile2][0], '= pink') + + # + # Set fill color to red for nodes that are unresolved + # + for Node in set(UnresolvedPackages): + PackageLabels[Node] =3D (PackageLabels[Node][0], 'red') + print ('ERROR: UNRESOLVED: ' + Node) + + # + # Add node statements to set node label and fill color + # + Nodes =3D [] + for Package in PackageLabels: + Nodes.append(' "{Package}" [label=3D"{Label}",fillcolor=3D{Color}= ];'.format( + Package =3D Package, + Label =3D PackageLabels[Package][0], + Color =3D PackageLabels[Package][1] + )) + Nodes.sort() + + # + # Generate dot file from Nodes and Edges and add a Legend at top of gr= aph + # + Dot =3D [] + Dot.append('digraph {') + Dot.append(' rankdir=3DBT;') + Dot.append(' node [shape=3DMrecord,style=3Dfilled];') + Dot.append('') + Dot =3D Dot + Nodes + Dot.append('') + Dot =3D Dot + Edges + Dot.append('') + Dot.append(' subgraph legend {') + Dot.append(' rank=3Dsink;') + Dot.append(' Unresolved [label=3D"Unresolved Dependency", = fillcolor=3Dred];') + Dot.append(' Circular [label=3D"Circular Dependency", = fillcolor=3Dyellow];') + Dot.append(' Nested [label=3D"Nested Package", = fillcolor=3Dpink];') + Dot.append(' NestedCircular [label=3D"Nested Package with Circular = Dependency",fillcolor=3Dorange];') + Dot.append(' }') + if MaxWeightDecFile: + Dot.append(' Unresolved->"' + MaxWeightDecFile + '" [style=3Dinvi= s];') + 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 =3D os.path.realpath(args.SvgOutputFile) + try: + Process =3D subprocess.Popen('dot -Tsvg', + stdin=3Dsubprocess.PIPE, + stdout=3Dopen(args.SvgOutputFile, 'w'), + stderr=3Dsubprocess.PIPE, + shell=3DTrue + ) + Process.stdin.write ('\n'.join(Dot).encode()) + Process.communicate() + if Process.returncode !=3D 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 inst= all and path.") + sys.exit(1) + # + # Display SVG file in default web browser + # + if args.WebBrowser: + webbrowser.open(args.SvgOutputFile) --=20 2.21.0.windows.1 -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D- Groups.io Links: You receive all messages sent to this group. View/Reply Online (#52212): https://edk2.groups.io/g/devel/message/52212 Mute This Topic: https://groups.io/mt/68538496/1787277 Group Owner: devel+owner@edk2.groups.io Unsubscribe: https://edk2.groups.io/g/devel/unsub [importer@patchew.org] -=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-=3D-