The new architecture of pkgng solver

[Vsevolod Stakhov]

Matthew,

On 25/07/13 16:33, Matthew Seaman wrote:
> On 25/07/2013 16:02, Vsevolod Stakhov wrote:
>> Hello,
>>
>> At the moment I plan to do the following:
>>
<skip>
>> 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)
>>
<skip>
>>
>
> 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.

With my GSoC project I've introduced both provides and conflicts. 
Conflicts are generated automatically during repository creation (by pkg 
repo -l) and exported during 'pkg update'. Provides are not generated 
but they could be specified in a manifest and therefore generated by ports.

Here is my idea about provides:
- if a package A provides virtual package B (for instance perl5.10 
provides perl5 package) then it provides B of version x.x.
- if a package C depends on B of any compatible version (e.g. version >= 
x.x) than package A installed satisfies this dependency.

> shlibs provides/requires is handy because it can be automatically
> generated.

Not really, as these dependencies are plain as well, and I think we 
should follow the cudf scenario for this purposes:
<quote>
package formulae, boolean formulae over versioned package predicates:

     python-minimal: any package called python-minimal
     libedac1 = 1: version 1 of package libedac1
     libxft2 > 1: any version of libxft2 greater than 1
     haskell-doc <= 2: any version of haskell-doc less than or equal to 2
     libz-dev != 3: any version of libz-dev other than 3
     postfix > 2 | exim4-base: either a version of postfix greater than 
2, or any version of exim4-base
     ocaml-nox, libc6 >= 6: both (any version of) ocaml-nox and a 
version of libc6 greater than 6
     php4, apache | httpd: both (any version of) php4 and one among: 
(any version of) apache and (any version of) httpd
</quote>

With this abstraction we won't need explicit 'requires' - just an 
advanced package dependencies:

dependency ::= <dep_rule> | <dep_rules>
dep_rules ::= <dep_rule> "|" <dep_rule> | <dep_rules>
dep_rule ::= <name> <type> <operation> <version>

name ::= <the name of dependency>
type ::= origin (for direct deps) | shlib | virtual (for provides)
operation ::= compassion operation: < | > | = | != | >= | <= | any
version ::= <version value>

However, this change is not literally compatible with ports. Especially 
this is true for conflicts as from my point of view it is nearly 
impossible to convert from
CONFLICTS= somepkg1.*

to a reasonable formulae presented above.

> 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.

Yes, but now these conflicts are generated when a repo is created, so we 
have this information already without any requirement of files 
rescanning (as it is quite an expensive operation).

> But I think a lot of this
> is going to need some sort of manually specified
> 'PROVIDES/REQUIRES/CONFLICTS' data within each port.

Yes, but remove requires, they are not needed as we already have a 
dependency definition :)

-- 
Vsevolod Stakhov