Bug#614249: britney2: insufficient removal checks

["Adam D. Barratt" <adam@adam-barratt.org.uk>]

On Wed, March 2, 2011 06:40, Adam D. Barratt wrote:
> Making the necessary changes to correctly loop over all the reverse
> dependencies isn't particularly involved, but does take quite a bit
> longer than b1 when checking debianutils; my initial testing last night
> suggests it's in the order of a few minutes per architecture, producing
> a combined list of approximately 11,000 cumulative reverse dependencies
> each time.

Updated patch attached, which takes a few seconds to build the list across
all architectures, producing the same results as the previous version
(just far more efficiently).

I'm planning on pushing this to master in the near future together with a
few other patches I've accumulated recently.

Regards,

Adam

diff --git a/britney.py b/britney.py
index 5970d8a..120f7c0 100755
--- a/britney.py
+++ b/britney.py
@@ -2034,9 +2046,24 @@ class Britney:
                     # save the old binary for undo
                     undo['binaries'][p] = binaries[parch][0][binary]
                     # all the reverse dependencies are affected by the change
-                    for j in binaries[parch][0][binary][RDEPENDS]:
-                        key = (j, parch)
-                        if key not in affected: affected.append(key)
+                    # recursively loop through the reverse dependencies
+                    rev_deps = set(binaries[parch][0][binary][RDEPENDS])
+                    seen = set()
+                    while len(rev_deps) > 0:
+                        # mark all of the current iteration of packages as affected
+                        affected.extend( [ (x, parch) for x in rev_deps ] )
+                        # and as processed
+                        seen |= rev_deps
+                        # generate the next iteration, which is the reverse-dependencies of
+                        # the current iteration
+                        new_rev_deps = [ binaries[parch][0][x][RDEPENDS] for x in rev_deps \
+                                         if x in binaries[parch][0] ]
+                        # flatten the list-of-lists, filtering out already handled packages
+                        # in the process
+                        rev_deps = set([ package for sublist in new_rev_deps \
+                                         for package in sublist if package not in seen ])
+                    # remove duplicates from the list of affected packages
+                    affected = list(set(affected))
                     # remove the provided virtual packages
                     for j in binaries[parch][0][binary][PROVIDES]:
                         key = j + "/" + parch