From: Michael Tremer <michael.tremer@ipfire.org>
Date: Fri, 7 Apr 2017 11:04:02 +0000 (+0100)
Subject: pakfire: Fix dependency resolver
X-Git-Tag: v2.19-core111~23^2~6^2~1
X-Git-Url: http://git.ipfire.org/?p=ipfire-2.x.git;a=commitdiff_plain;h=621dcd8609a26ffe98fcb7fff05202bf5eb41112

pakfire: Fix dependency resolver

The old algorithm could potentially lock itself in an endless
recursion when there were packages with circular dependencies.

This version does not do this and is also faster.

Reported-by: Arne Fitzenreiter <arne.fitzenreiter@ipfire.org>
Signed-off-by: Michael Tremer <michael.tremer@ipfire.org>
---

diff --git a/config/rootfiles/core/110/filelists/files b/config/rootfiles/core/110/filelists/files
index 4a7d710d76..f903fbd400 100644
--- a/config/rootfiles/core/110/filelists/files
+++ b/config/rootfiles/core/110/filelists/files
@@ -3,6 +3,7 @@ etc/issue
 etc/httpd/conf/server-tuning.conf
 etc/rc.d/init.d/unbound
 etc/sysctl.conf
+opt/pakfire/lib/functions.pl
 srv/web/ipfire/cgi-bin/entropy.cgi
 srv/web/ipfire/cgi-bin/hardwaregraphs.cgi
 srv/web/ipfire/cgi-bin/index.cgi
diff --git a/src/pakfire/lib/functions.pl b/src/pakfire/lib/functions.pl
index 11b1e37d58..c347916d80 100644
--- a/src/pakfire/lib/functions.pl
+++ b/src/pakfire/lib/functions.pl
@@ -541,7 +541,7 @@ sub dblist {
 	}
 }
 
-sub resolvedeps {
+sub resolvedeps_one {
 	my $pak = shift;
 	
 	getmetafile("$pak");
@@ -553,7 +553,7 @@ sub resolvedeps {
 	close(FILE);
 	
 	my $line;
-	my (@templine, @deps, @tempdeps, @all);
+	my (@templine, @deps, @all);
 	foreach $line (@file) {
 		@templine = split(/\: /,$line);
 		if ("$templine[0]" eq "Dependencies") {
@@ -568,30 +568,41 @@ sub resolvedeps {
 		  	message("PAKFIRE RESV: $pak: Dependency is already installed: $_");
 		  } else {
 		  	message("PAKFIRE RESV: $pak: Need to install dependency: $_");
-				push(@tempdeps,$_);
 				push(@all,$_);
 			} 
 		}
 	}
 
-	foreach (@tempdeps) {
-		if ($_) {
-			my @newdeps = resolvedeps("$_");
-			foreach(@newdeps) {
-				unless (($_ eq " ") || ($_ eq "")) {
-					my $return = &isinstalled($_);
-					if ($return eq 0) {
-						message("PAKFIRE RESV: $pak: Dependency is already installed: $_");
-					} else {
-						message("PAKFIRE RESV: $pak: Need to install dependency: $_");
-						push(@all,$_);
-					}
-				}
+	return @all;
+}
+
+sub resolvedeps {
+	my $pak = shift;
+	my @all;
+
+	# Resolve all not yet installed dependencies of $pak
+	my @deps = &resolvedeps_one($pak);
+	push(@all, @deps);
+
+	# For each dependency, we check if more dependencies exist
+	while (@deps) {
+		my $dep = pop(@deps);
+
+		my @subdeps = &resolvedeps_one($dep);
+		foreach my $subdep (@subdeps) {
+			# Skip the package we are currently resolving for
+			next if ($pak eq $subdep);
+
+			# If the package is not already to be installed,
+			# we add it to the list (@all) and check if it has
+			# more dependencies on its own.
+			unless (grep {$_ eq $subdep} @all) {
+				push(@deps, $subdep);
+				push(@all, $subdep);
 			}
 		}
 	}
-	message("");
-	chomp (@all);
+
 	return @all;
 }