Depcheck is one of those things which is deceptively complicated. On the surface, it's such a simple thing: "figure out if the dep tree is broken" but reality makes the problem much more difficult and messy. We've recently deployed a rewrite of the old depcheck tool from AutoQA and while I think it's a huge step forward in terms of maintainability and coherant output, it does have some known shortcomings.
For the sake of everyones' sanity, I'm limiting this to the depcheck algorithm(s) and the ability to find certain types of depsolving errors. There are other fun bits about depcheck (timing and determining fault are two examples) which I'm not going to touch on here for the sake of complexity and brevity.
As the discussion about how to start using the output of Taskotron to start gating builds and updates is resurfacing, I wanted to write a higher-level overview of depcheck, what it can do and more importantly, what it can't do. My goals in doing this are:
- Clearly, from a higher level, discuss what depcheck can and cannot do
- Discussion of the possible solutions I've found to plug the existing holes in depcheck to answer the question of whether or not it's worth spending the resources to plug them.
- Get ideas for other feasible solutions I haven't thought of
What is Depcheck?
The overarching idea behind depcheck is to verify that incoming builds or updates won't cause problems in existing repos and identify the packages involved in any discovered depsolving errors.
The simplest way to put it is that we want to discover depsolving errors early on so that users of the stable updates repository don't get errors like this:
Setting up Update Process
Resolving Dependencies
--> Running transaction check
--> Processing Dependency: libedataserverui-1.2.so.10()(64bit) for package: gnome-panel-2.31.90-4.fc14.x86_64
---> Package evolution-data-server.x86_64 0:2.32.0-1.fc14 set to be updated
---> Package nautilus-sendto.x86_64 1:2.32.0-1.fc14 set to be updated
--> Finished Dependency Resolution
Error: Package: gnome-panel-2.31.90-4.fc14.x86_64 (@updates-testing)
Requires: libedataserverui-1.2.so.10()(64bit)
Removing: evolution-data-server-2.31.5-1.fc14.x86_64 (@fedora/$releasever)
libedataserverui-1.2.so.10()(64bit)
Updated By: evolution-data-server-2.32.0-1.fc14.x86_64 (updates-testing)
Not found
You could try using --skip-broken to work around the problem
You could try running: rpm -Va --nofiles --nodigest
The Example
As a trivial example let's look at an example scenario
In this scenario, our stable repository contains foo-0.1-1.fc19 which provides libfoo and bar-0.1-1.fc19 which requires libfoo. Our proposed updates repository contains foo-0.2-1.fc19 and there's been a change in the package so that it now provides libfooplus instead of libfoo and there's no obsoletes: libfoo.
Obviously, this is a problem situation but that's why it serves as a good example to show what depcheck can and can't do.
Depcheck Run
From a high level, depcheck works by importing all relevant repos and verifying that all incoming packages are installable. To put our example into pseudocode:
import_repo(stable)
import_repo(updates)
for package in updates.packages:
try_install(package)
In this example, all of the dependencies for foo-0.2-1.fc19 are satisfied and this is a pass. Since we're only looking at the update packages, depcheck completely ignores any potential issues with already-installed packages. In this case, if a user had bar-0.1-1.fc19 installed, dnf/yum would complain about removing foo-0.1-1.fc19 because that leaves bar-0.1-1.fc19 without one of its requirements (libfoo).
Old Depcheck's Solution
The old version of depcheck didn't have this problem because it was written in a different way than new depcheck. Old depcheck's solution was to trick yum into believing that all packages in existing repos were installed and simulate installation of the update packages.
While this sounds good on paper, in practice it causes about as many false alarms as it does catch actual problems. The primary issue is in the setup - by tricking yum into believing that all packages are installed, the usual installation process is skipped and you end up with everything installed, regardless of conflicts. If anything in a dep chain has an explicit conflict, it's already invalid and depcheck falsely identifies the incoming package as failing.
Possible New(-ish) Solutions
At this point, I've outlined what our current depcheck isn't checking and made a case for why the exact approach taken by old depcheck isn't a good solution but haven't identified any better solutions.
I've spent quite a bit of time thinking about and doing research on how to solve the depcheck problem in Fedora and I've been able to come up with two approaches which I think are the most promising.
Old Depcheck, Modified
One way to summarize the problem with old depcheck's method is that it was trying to do all the checking in one pass. If we broke the check up into multiple passes for at least the depchains which involve explicit conflicts, we could avoid the problems from old depcheck's solution.
The problem, however, is in determining how those multiple passes should be structured. The naive, brute-force approach would be to simulate installation of all incoming packages over all possible combinations of conflicting packages such that any combination doesn't have two conflicting packages installed at the same time. This approach would involve a lot of extra computation which isn't needed in almost all cases.
An obvious optimization here is to be bit smarter about determining the pre-installed package sets and limiting the runs to sets which could be affected by the new packages under test through analysis of the repos before running depcheck or by carefully handling error conditions and adding additional runs if the error is due to packages with explicit conflicts.
Note that this solution is predicated on being able to make libsolv think that at least most packages are already installed and I don't yet know if this is possible.
- Good
- No new dependencies
- Overall strategy has worked in the past
- Less abstraction of the actual problem
- Bad
- Requires mucking around with libsolv
- Increases code complexity with extra depcheck passes
- Not sure if it's even possible given the way that depcheck is currently written
A More Formal Approach
Instead of just saying "we want to find any potential problems in our repos", let's define what that is a bit better.
Given a set of repos, each consisting of a set of packages: are there any valid (not explicitly conflicting) sets of packages which are not installable?
An interesting approach to answering this question is discussed in Solving package dependencies: from EDOS to Mancoosi where the installability problem is transformed into a boolean satisfiability (SAT) problem. While I don't agree with some of the simplifications they make (specifically, ignoring versioned dependencies), their general approach seems sound.
Looking at an example, say a conflicts with b and depends on c, and either d or e. To represent this in terms which could be used in a boolean SAT solver, we create boolean variables to represent whether or not a package is installed. In the unversioned case, this can be represented as:
If this was the entire SAT problem, we would look for values of a, b, c, d and e such that the entire expression evaluates as True. If we expand all package dependencies in the input repositories and packages under test, we have a representation of all the installability constraints in the domain we're interested in. Granted, it would be a huge boolean expression but fortunately, there is an entire class of algorithms designed to solve such problems as efficiently as possible.
Using an existing SAT solver, we can find out whether or not there are package sets which allow for out new packages to be installed but this isn't quite the problem that we're looking to solve. What we're looking for is pretty much the opposite - sets of packages which don't allow for the updates to be installed. For this, we need something slightly different from a SAT solver - a Minimally Unsatisfiable Subformula (MUS) extractor.
There don't seem to be quite as many MUS extractors as there are SAT solvers but I've been able to find one that is appropriately licensed for our uses which is an implementation of the algorithm discussed in MUSer2: An Efficient MUS Extractor.
I was able to compile the code for muser-2 without any problems and it did correctly solve a trivial problem which I constructed as a test. However, I haven't spent enough time on this to know whether it'll end up being a good, maintainable solution yet.
- Good
- Doesn't involve hacking at libsolv
- Based on more proven algorithms
- Heavy algorithmic lifting already done
- Bad
- Construction of the SAT problem isn't trivial
- Involves the use of external code which may or may not be maintained long term
Conclusion
If you've made it this far, congratulations! I hope that this has at least been instructive on what depcheck can/can't do and some potential approaches we could take to improve it. If you have ideas, comments, constructive criticism or want to help work on QA tools, I'd very much like to hear from you! Disqus comments, irc (#fedora-qa on Freenode) or the qa-devel list are good ways to find me.