Date: Thu, 25 Jul 2013 16:33:42 +0100 From: Matthew Seaman <matthew@freebsd.org> To: freebsd-pkg@freebsd.org Subject: Re: The new architecture of pkgng solver Message-ID: <51F14556.9040605@freebsd.org> In-Reply-To: <51F13DF0.5040209@FreeBSD.org> References: <51F13DF0.5040209@FreeBSD.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On 25/07/2013 16:02, Vsevolod Stakhov wrote: > Hello, > > At the moment I plan to do the following: > > 1) > - introduce 'the universe' structure, which contains all deps (for > install/fetch/upgrade), rdeps (for deinstall), conflicts and their rdeps > (for install); > - add request list - a list of packages to install, remove or upgrade > - write universal solver code that takes universe and a request list and > then either produces cudf output or uses an internal SAT solver; > - results are written into two lists: packages to add/upgrade and > packages to remove (e.g. due to conflicts). > > 2) > Plan 'provides' logic that means that a dependency can be provided by a > number of (potentially conflicting) packages. It is implemented as pkg > field but it is not used by solver. > > 3) > Internal solver should work based on the following procedure: > > 1. Iterate over the universe and create a boolean problem: > * A depends on B that is provided by B1, B2 or B3 is transferred to a > set of rules: (!A | B1 | B2 | B3) > * A conflicts between B1, B2 and B3 is transferred to the following: > (!B1 | !B2) & (!B1 | !B2) & (!B1 | !B3) > or in case of conflict to a provided feature if A conflicts with B > provided by B1, B2 or B3: > (!A | !B1) & (!A | !B2) & (!A | !B3) > > 2. Explicit requests for install or remove are written as: > (A) - install A > (!A) - remove A > > 3. For all explicit request (e.g. install A) set the value of these > requests either to true (for packages to install) or false (for packages > to deinstall). > > 4. Iterate over the record and set all unary rules to true, for example > (A) & (!A | B1 | B2 | B3) & (!A | !C) which means that A depends on (B1 > or B2 or B3) and conflicts with C. After this step we set A to TRUE as > it is unary rule. > > 5. For all other rules perform propagation procedure, substitute > variables to make a rule as true. For example in the previous example: > * (A) & (!A | B1 | B2 | B3) & (!A | !C) - A is TRUE; > * (!A | !C) - !C should be TRUE as !A is FALSE and C thus is FALSE; > * (!A | B1 | B2 | B3) - !A is FALSE, so one of B1/B2/B3 should be TRUE. > > 6. For the last step there is a choice, what to select. I'd suggest to > follow this logic: > * try installed packages first; > * do not install any packages that are not needed (e.g. set all > available alternatives to FALSE); > > 7. Check the overall expression and if it is FALSE try to reassign the > last assigned variable from the previous step. > > 8. 6 and 7 till the expression is either TRUE or there is no way to > reassign variables (unsolvable solution). > > With this logic we have only a single problematic point - how to convert > the packages universe and request to a SAT problem. On the other hand, > with this architecture we have a *universal* solution for all procedures > (install/remove/upgrade). Moreover, it is compatible with CUDF format, > therefore I suggest to rework the current jobs architecture to this one. > > I'll do it if there are no objections. > > (And, well, we need to think eventually what to do with share libraries > dependencies and flexible dependencies, e.g. Depends: libsomething (>1.4)) > In (1) you say: * A depends on B that is provided by B1, B2 or B3 At the moment, strictly the only data we have about 'B that is provided by B1, B2 or B3' *is* the shlib provides/requires data. All the dependency relationships between pkgs other than that are based on 'package X-N.NN.NN requires package Y-M.MM.MM' where Y-M.MM.MM was the version of the package for Y on the system at the point when package X was built. ie. there are no alternatives visible for the solver to work with. shlibs provides/requires is handy because it can be automatically generated. There are a few other similar sorts of relationships that could be extracted automatically -- for instance dependencies between perl modules -- and we can generate 'conflicts' data based on packages wanting to install files to the same place. But I think a lot of this is going to need some sort of manually specified 'PROVIDES/REQUIRES/CONFLICTS' data within each port. Cheers, Matthew
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?51F14556.9040605>