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 4a7d710d76f0e4bd68ffd487262c55fd10f896e9..f903fbd400686354177484bcbff3ce8a479812a6 100644 (file)
--- 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 11b1e37d583382cdef82e21a220131545865beec..c347916d80cd5f6bb8eae23406c1bb4f42de1bd5 100644 (file)
--- 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;
 }