GSoC 15 - Dependency Calculation using SAT

[Jackson Isaac]

On Fri, Mar 20, 2015 at 4:09 AM, Mihai Moldovan <ionic at macports.org> wrote:
> On 19.03.2015 11:16 AM, Jackson Isaac wrote:
>> On Thu, Mar 19, 2015 at 3:25 AM, Clemens Lang <cal at macports.org> wrote:
>>> Hi,
>>>
>>> ----- On 17 Mar, 2015, at 14:43, Jackson Isaac jacksonisaac2008 at gmail.com wrote:
>>>
>>>> As you know the application period has started. Can you please help me
>>>> out with some things regarding the proposal.
>>> Certainly, I'd be happy to :)
>>>
>>>
>>>> I have built the latest Macports (i.e 2.3.99 from source) and as you
>>>> said I can see the confirmation before installing dependencies and
>>>> also it looks much cleaner now.
>>>>
>>>> Also I went through the source code. The dependency is build in
>>>> src/macports1.0/macports.tcl src/macports1.0/portdepends.tcl and
>>>> src/macports1.0/macports_dlist.tcl if I am not wrong or missing out
>>>> anything else.
>>> Nope, that's correct. The code is old, but works fine.
>>>
>>>
>>>> I have also gone through the CUDF at
>>>> http://www.mancoosi.org/cudf/primer/ and also
>>>> http://docs.codehaus.org/display/MAVEN/SAT+Based+Dependency+Resolution.
>>>>
>>>> Does using CUDF mean that our portfile format will have to be modified
>>>> (there is not much syntax difference, we might be able to interpret
>>>> the old portfiles to a cudf file format while running dependency
>>>> check.
>>> I'm not particularly attached to actually using CUDF. I sounded like a
>>> good idea when I last checked it, but it largely depends on the SAT
>>> solver we'd use in the end. I'm not sure the current CUDF-solvers have
>>> good support for specifying your own objective function to optimize.
>>>
>>> But anyway, regardless of the format we actually use for the SAT solver,
>>> a problem that might come up is actually converting Portfiles into a
>>> representation that can be used. As you correctly stated, the results
>>> of both formats are equivalent enough so that the actual conversion
>>> isn't hard. However, to generate accurate dependency information, we'd
>>> usually have to execute the Portfiles, and that can really slow the
>>> whole process down quite a bit, which we should avoid. From what I've
>>> seen, dependency resolution methods based on SAT solving expect the
>>> complete universe of available packages and their dependency relations
>>> plus a list of packages that should be installed after the current
>>> action finished. Generating the complete list with accurate dependency
>>> info by executing the Portfiles would take ~15 minutes and is thus
>>> out of the question.
>>>
>>> We do have a cache of the information, which we call the port index.
>>> However, since Portfiles can execute arbitrary code, some Portfiles
>>> may currently depend on the behavior that they are being evaluated
>>> during dependency calculation (e.g. by changing their depends_lib
>>> depending on the variant selection the user has given). We should
>>> figure out a solution for that, for example by
>>>  (a) somehow adding the effect of a variant on dependency relations
>>>      to the portindex, so we could tell what the dependencies of
>>>      foobar +bar +baz were without actually running the Portfile.
>> By variant do you mean the packages that are required by the package
>> that we want to install.
>
> No, variants in MacPorts world are used for disabling or enabling
> features within a package.
>
> Variants can add or remove dependencies, but need not.
>
> Please see https://guide.macports.org/chunked/using.variants.html for a
> general description of variants and
> https://trac.macports.org/browser/trunk/dports/multimedia/mplayer-devel/Portfile
> for an example Portfile with a lot of variants.
>
> The problem with these is that currently, like for so many other things,
> Portfiles must be completely evaluated (that is, the TCL code executed)
> in order to have a complete list of dependencies -- and this "complete
> list" isn't static but depends on the deactivated or activated variants,
> the platform(!!! -- like darwin, linux, freebsd) ... and subplatform
> (like macosx) and their specific versions.
>
>
>> Do you mean like in Portfile we have:
>
> Did you mean PortIndex instead of Portfile?
>

Yes, I meant PortIndex. Sorry for the typo.

>
>> packagename somenumber (I don't know what this number means) and
>> followed by description.
>>
>> So here itself we add/cache the dependencies when we fetch the
>> portfiles (or maybe when we are trying to install to keep reference
>> for future).
>
> The problem is that this is not static. See above. There are 2^n*
> different states for n variants. For a port like mplayer-devel (or my
> own ports, mpv and audacious-plugins), the amount of variant
> combinations is *very* high and for each combination the dependencies
> differ.
>
> You do NOT want to record this in PortIndex, which is supposed to be
> fast cache.
>

So we will have to calculate the dependency tree while we install.
Since there can be many variants possible and each will have different
dependencies.

Currently, we are fetching the dependencies from the Portfile correct?
based on the dependencies defined by the maintainer of the port.

Using SAT method we will be defining minimal dependencies and these
dependencies will be further checked for their dependencies or we need
to still define all the dependencies for each package?

Eg. x depends on y. so in portfile of x say it depends on y. Now we
will check if y depends on any a,b,c further. Like this compute
different possible combinations and select the best course and also
taking the variant into account (using Boolean).

What if while the port files are indexed we also create another file
where these dependency trees are pre-computed and can be checked when
the package needs to be installed. It would save computation time
during installation. But also question about space that would be
needed for this arises.

>
>
> Mihai
>
> *) Math is not my strength, this statement may be off by one or a million...
>



-- 
Jackson Isaac
S6 B.Tech CSE
Amrita Vishwa Vidyapeetham
jacksonisaac.wordpress.com
Github/JacksonIsaac