[pacman-dev] [PATCH] Fix bug 9395 by allowing pacman to remove unresolvable packages from a transaction

[Bryan Ischo]

Nagy Gabor wrote:
> Oh, I see that I totally misinterpreted something here. If we allow 
> pacman to remove targets from the list, we cannot get any unresolved 
> dependencies, right? So just forget what I said earlier. (But problem 
> [1] is still interesting.) But your method for collecting unresolvable 
> dependencies is still not good. Just put the dependency into data list 
> when it turns out that the dependency (locally) not resolvable. (When 
> resolvedep returns with NULL.) This should be identical to the old 
> behavior, if user doesn't let pacman remove targets. If user resolve 
> this problem by removing some targets, you can free this list.

Yes, the technique that I use removes all unresolvable dependencies from 
the list altogether; the effect is as if the user hadn't actually 
requested that any packages be upgraded which could not be resolved, and 
so the remaining list is 'clean' of unresolvable dependencies.

I don't think the simplification you propose will work.  What if we have:

packageA-1.0-1 depends on packageB-1.0-1
packageB-1.01 depends on packageC-1.0-1

User has packageC in their IgnorePkg list.

User does pacman -S packageA and new packages are available:

packageA-2.0-1 depends on packageB-2.0-1
packageB-2.0-1 depends on packageC-2.0-1

The resolve for packageA looks for packageB-2.0-1 and finds it.  The 
resolve for packageB-2.0-1 looks for packageC-2.0-1 but *does not* find 
it because packageC is in the IgnorePkg list.

Now with my change, the resolve step will determine that packageA and 
packageB cannot be installed due to missing dependencies, and will 
prompt the user to ask if they want to remove packageA from the 
transaction.  If they say that they do, it removes packageA and all 
packages which it depends on (except those packages which are also 
depended on by packages that are remaining in the transaction, which in 
this example, is none), which is packageA and packageB.  If they say 
they do not, then it returns an error in the same way that the 
pre-existing code returned an error at the moment that the unresolvable 
packages was detected.

What you are suggesting, I think, is that we simply put packageC on a 
separate list of unresolvable packages, and then at the end, ask the 
user some question (I'm not sure exactly what question since you're not 
keeping track of which top-level packages are unresolvable - probably 
you'd ask "packageC is not resolvable, remove from transaction?", which 
I think would be confusing, since the user never said anything about 
packageC), and if they want to remove unresolvable packages, just remove 
packageC from the transaction.  However, you're then left with a 
transaction including packageA and packageB, which *cannot* be 
completed, because packageB has an unresolvable dependency.

Did I understand your suggestion correctly?

Let me try to explain the algorithm and data structures I am using, it 
may help clear up confusion.  But first, here's the old algorithm:

- While resolving dependencies, if a required package is found to be in 
IgnorePkg, then prompt the user to see if they want to include the 
package in this transaction anyway
- If they did not, then consider the dependency to be unresolvable
- If they did, then put the package in the transaction and proceed as if 
it wasn't ever in IgnorePkg
- Any unresolvable package immediately fails the resolve step and returns 1

Now here's my algorithm:

- While resolving dependencies, if a required package is found to be in 
IgnorePkg, or otherwise cannot be found, then keep this information in 
an internal dependency graph but don't ask the user anything, just 
proceed to the end of the resolve step
- At the end of the resolve step, if any packages were not resolvable, 
compute which top-level packages were unresolvable (which could be due 
to any package in their dependency subtree being unresolvable)
- Ask the user if they want to remove these unresolvable top-level 
packages from the transaction
- If they do, remove the unresolvable top-level packages and all of 
their dependencies from the transaction (except for those dependencies 
which were also required by a resolvable top-level package too), and 
return a success code from the resolve step
- If they do not, fail the resolve step by returning 1

The data structures are:

- Well there's only one really.  It's a structure holding the 
"back-pointers" from packages to the packages which depend on them.  It 
also holds a few values which are computed during the resolve operation.

It's possible that what I'm trying to do could be done in a simpler way; 
but I don't think that your suggestion accomplishes that.  I think the 
part you might be missing is the case where there is a deep dependency 
chain and only the bottom package cannot be resolved; there has to be 
some way to detect that all packages which depend on this package also 
cannot be resolved.

Thanks,
Bryan