From patchwork Wed Jan 2 17:08:48 2013 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Thomas Petazzoni X-Patchwork-Id: 209109 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Received: from hemlock.osuosl.org (hemlock.osuosl.org [140.211.166.133]) by ozlabs.org (Postfix) with ESMTP id 653802C0040 for ; Thu, 3 Jan 2013 04:09:17 +1100 (EST) Received: from localhost (localhost [127.0.0.1]) by hemlock.osuosl.org (Postfix) with ESMTP id 5BCEFA006A; Wed, 2 Jan 2013 17:09:16 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Amavis-Alert: BAD HEADER SECTION, Duplicate header field: "References" Received: from hemlock.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id 8g08FXS67Gt9; Wed, 2 Jan 2013 17:09:09 +0000 (UTC) Received: from ash.osuosl.org (ash.osuosl.org [140.211.166.34]) by hemlock.osuosl.org (Postfix) with ESMTP id DFBDBA00B1; Wed, 2 Jan 2013 17:09:07 +0000 (UTC) X-Original-To: buildroot@lists.busybox.net Delivered-To: buildroot@osuosl.org Received: from whitealder.osuosl.org (whitealder.osuosl.org [140.211.166.138]) by ash.osuosl.org (Postfix) with ESMTP id C7ED88F74B for ; Wed, 2 Jan 2013 17:09:09 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by whitealder.osuosl.org (Postfix) with ESMTP id C777680AEE for ; Wed, 2 Jan 2013 17:09:03 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Amavis-Alert: BAD HEADER SECTION, Duplicate header field: "References" Received: from whitealder.osuosl.org ([127.0.0.1]) by localhost (.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id XrrBWH+qoBK7 for ; Wed, 2 Jan 2013 17:09:03 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.7.6 Received: from mail.free-electrons.com (mail.free-electrons.com [94.23.32.191]) by whitealder.osuosl.org (Postfix) with ESMTP id B2754805C9 for ; Wed, 2 Jan 2013 17:09:02 +0000 (UTC) Received: by mail.free-electrons.com (Postfix, from userid 106) id AA1CE26F; Wed, 2 Jan 2013 18:09:02 +0100 (CET) Received: from localhost (unknown [37.160.51.71]) by mail.free-electrons.com (Postfix) with ESMTPSA id C25D917B for ; Wed, 2 Jan 2013 18:09:01 +0100 (CET) From: Thomas Petazzoni To: buildroot@busybox.net Date: Wed, 2 Jan 2013 18:08:48 +0100 Message-Id: X-Mailer: git-send-email 1.7.9.5 In-Reply-To: References: In-Reply-To: References: Subject: [Buildroot] [PATCH 1/6] graph-depends: remove redundant dependencies X-BeenThere: buildroot@busybox.net X-Mailman-Version: 2.1.14 Precedence: list List-Id: Discussion and development of buildroot List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , MIME-Version: 1.0 Errors-To: buildroot-bounces@busybox.net Sender: buildroot-bounces@busybox.net When doing a full graph of the dependencies, graph-depends starts by doing a "make show-targets", which lists all the packages registered in the $(TARGETS) variable. This variable contains all packages that are enabled according to the .config file. Then, for each of those packages, we used to create a "all" -> "package" dependency, even if in fact most of some packages are already dependencies of other packages. This creates a needlessly complex dependency graph. This patch modifies graph-depends so that it filters out the unneeded "all" -> "package" dependencies when "package" is already the dependency of another package. For example, if you have a configuration with libpng (which selects zlib), "make show-targets" displays "libpng zlib", so graph-depends used to create the following dependencies: (all -> libpng, all -> zlib, libpng -> zlib). However, the (all -> zlib) dependency is not really needed, as zlib is already the dependency of libpng. Those dependencies are now filtered out. Signed-off-by: Thomas Petazzoni --- For an example of the difference on a bigger configuration, see: http://free-electrons.com/~thomas/pub/buildroot/graph-depends-before-redundant-removal.pdf http://free-electrons.com/~thomas/pub/buildroot/graph-depends-after-redundant-removal.pdf --- support/scripts/graph-depends | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+) diff --git a/support/scripts/graph-depends b/support/scripts/graph-depends index 409c123..c80a65a 100755 --- a/support/scripts/graph-depends +++ b/support/scripts/graph-depends @@ -119,6 +119,37 @@ def get_all_depends(pkg): def pkg_node_name(pkg): return pkg.replace("-","") +# Helper function for remove_redundant_deps(). This function tells +# whether package "pkg" is the dependency of another package that is +# not the special "all" package. +def has_redundant_deps(deps, pkg): + for dep in deps: + if dep[0] != "all" and dep[1] == pkg: + return True + return False + +# This function removes redundant dependencies of the special "all" +# package. This "all" package is created to reflect the origin of the +# selection for all packages that are not themselves selected by any +# other package. So for example if you enable libpng, zlib is enabled +# as a dependency. But zlib being selected by libpng, it also appears +# as a dependency of the "all" package. This needlessly complicates +# the generated dependency graph. So when we have the dependency list +# (all -> zlib, all -> libpn, libpng -> zlib), we get rid of the 'all +# -> zlib' dependency, because zlib is already a dependency of a +# regular package. +def remove_redundant_deps(deps): + newdeps = [] + for dep in deps: + if dep[0] != "all": + newdeps.append(dep) + continue + if not has_redundant_deps(deps, dep[1]): + newdeps.append(dep) + continue + sys.stderr.write("Removing redundant dep all -> %s\n" % dep[1]) + return newdeps + # In full mode, start with the result of get_targets() to get the main # targets and then use get_all_depends() for each individual target. if mode == FULL_MODE: @@ -144,6 +175,8 @@ if mode == FULL_MODE: elif mode == PKG_MODE: dependencies = get_all_depends(rootpkg) +dependencies = remove_redundant_deps(dependencies) + # Start printing the graph data print "digraph G {"