Unreliable Dependecies resolution

Description

Running same command to install packages >2 times yields different results:
first run:

$ aurman -S nsis 
~~ initializing aurman...
~~ calculating solutions...

!! While searching for solutions the following errors occurred:
:: Conflicts between: mingw-w64-winpthreads-5.0.4-1, mingw-w64-headers-bootstrap-5.0.3-1
While trying to install mingw-w64-winpthreads, the needed dependency mingw-w64-gcc has been removed
Way to package mingw-w64-winpthreads-5.0.4-1: nsis-3.03-1 -> mingw-w64-gcc-8.2.0-1 -> mingw-w64-winpthreads-5.0.4-1
Way to package mingw-w64-headers-bootstrap-5.0.3-1: nsis-3.03-1 -> mingw-w64-gcc-8.2.0-1 -> mingw-w64-winpthreads-5.0.4-1 -> mingw-w64-gcc-base-8.2.0-1 -> mingw-w64-headers-bootstrap-5.0.3-1

!! we could not find a solution
!! if you think that there should be one, rerun aurman with the --deep_search flag

Second run:

$ aurman -S nsis
~~ initializing aurman...
~~ calculating solutions...

:: The following 8 package(s) are getting installed:
   core/gcc-ada               /  ->  8.2.0-2
   aur/mingw-w64-binutils     /  ->  2.31.1-1
   aur/mingw-w64-crt          /  ->  5.0.4-1
   aur/mingw-w64-gcc          /  ->  8.2.0-1
   aur/mingw-w64-headers      /  ->  5.0.4-2
   aur/mingw-w64-winpthreads  /  ->  5.0.4-1
   aur/mingw-w64-zlib         /  ->  1.2.11-1
   aur/nsis                   /  ->  3.03-1

~~ The following will be done:
   Install   : mingw-w64-binutils
   Install   : mingw-w64-headers
   Install   : mingw-w64-winpthreads
   Install   : gcc-ada
   Install   : mingw-w64-gcc
   Install   : mingw-w64-crt
   Install   : mingw-w64-zlib
   Install   : nsis

?? Do you want to continue? Y/n:

Third run

$ aurman -S nsis --solution_way
~~ initializing aurman...
~~ calculating solutions...

:: The following 13 package(s) are getting installed:
   aur/cloog                  /  ->  0.19.0-1
   core/gcc-ada               /  ->  8.2.0-2
   extra/glpk                 /  ->  4.65-2
   aur/isl                    /  ->  0.20-4
   aur/mingw-w64-binutils     /  ->  2.31.1-1
   aur/mingw-w64-crt          /  ->  5.0.4-1
   aur/mingw-w64-gcc          /  ->  8.2.0-1
   aur/mingw-w64-headers      /  ->  5.0.4-2
   aur/mingw-w64-winpthreads  /  ->  5.0.4-1
   aur/mingw-w64-zlib         /  ->  1.2.11-1
   aur/nsis                   /  ->  3.03-1
   aur/osl                    /  ->  0.9.2-2
   community/ppl              /  ->  1.2-2

~~ The following will be done:
   Install   : gcc-ada
   Install   : mingw-w64-binutils
   Install   : mingw-w64-headers
   Install   : osl
   Install   : isl
   Install   : cloog
   Install   : mingw-w64-winpthreads
   Install   : glpk, ppl
   Install   : mingw-w64-gcc-base
   Install   : mingw-w64-crt
   Remove    : mingw-w64-gcc-base
   Install   : mingw-w64-gcc
   Install   : mingw-w64-zlib
   Install   : nsis

?? Do you want to continue? Y/n:

So I decided to run with `--deep_search and here what i've got from 2 runs:

$ aurman -S nsis --solution_way --deep_search
~~ initializing aurman...
~~ calculating solutions...

:: The following 8 package(s) are getting installed:
   core/gcc-ada               /           ->  8.2.0-2
   aur/mingw-w64-binutils     /           ->  2.31.1-1
   aur/mingw-w64-crt          /           ->  5.0.4-1
   aur/mingw-w64-gcc          /           ->  8.2.0-1
   aur/mingw-w64-headers      /           ->  5.0.4-2
   aur/mingw-w64-winpthreads  /           ->  5.0.4-1
   aur/mingw-w64-zlib         /           ->  1.2.11-1
   aur/nsis                   /           ->  3.03-1

~~ The following will be done:
:: You are using --deep_search, hence --needed is active.
:: That means packages to be reinstalled will not actually be reinstalled.
   Reinstall : filesystem, gcc-libs, glibc, iana-etc, linux-api-headers, tzdata
   Install   : mingw-w64-headers
   Reinstall : zlib
   Install   : mingw-w64-binutils
   Install   : mingw-w64-winpthreads
   Reinstall : bash, binutils, gcc, gmp, libmpc, mpfr, ncurses, readline
   Install   : gcc-ada
   Install   : mingw-w64-gcc
   Install   : mingw-w64-crt
   Install   : mingw-w64-zlib
   Reinstall : bzip2, db, e2fsprogs, expat, gdbm, keyutils, krb5, libffi, libldap, libnsl, libsasl, libtirpc, libutil-linux, openssl, perl, python2, scons, sqlite
   Install   : nsis

?? Do you want to continue? Y/n:

and

$ aurman -S nsis --solution_way --deep_search                         
~~ initializing aurman...
~~ calculating solutions...

:: The following 13 package(s) are getting installed:
   aur/cloog                     /                     ->  0.19.0-1
   core/gcc-ada                  /                     ->  8.2.0-2
   extra/glpk                    /                     ->  4.65-2
   aur/isl                       /                     ->  0.20-4
   aur/mingw-w64-binutils        /                     ->  2.31.1-1
   aur/mingw-w64-crt             /                     ->  5.0.4-1
   aur/mingw-w64-gcc             /                     ->  8.2.0-1
   aur/mingw-w64-headers         /                     ->  5.0.4-2
   aur/mingw-w64-winpthreads     /                     ->  5.0.4-1
   aur/mingw-w64-zlib            /                     ->  1.2.11-1
   aur/nsis                      /                     ->  3.03-1
   aur/osl                       /                     ->  0.9.2-2
   community/ppl                 /                     ->  1.2-2

~~ The following will be done:
:: You are using --deep_search, hence --needed is active.
:: That means packages to be reinstalled will not actually be reinstalled.
   Reinstall : bash, filesystem, gcc-libs, glibc, gmp, iana-etc, libmpc, linux-api-headers, mpfr, ncurses, readline, tzdata, zlib
   Install   : mingw-w64-binutils
   Install   : mingw-w64-headers
   Install   : glpk, ppl
   Install   : mingw-w64-winpthreads
   Install   : osl
   Reinstall : acl, attr, bzip2, ca-certificates, ca-certificates-cacert, ca-certificates-mozilla, ca-certificates-utils, cairo, coreutils, cracklib, curl, db, e2fsprogs, expat, findutils, fontconfig, freetype2, gd, gdbm, giflib, git, glib2, graphite, grep, harfbuzz, harfbuzz-icu, icu, keyutils, krb5, lcms2, libcap, libffi, libgcrypt, libgpg-error, libice, libidn2, libjpeg-turbo, libldap, libnghttp2, libpaper, libpng, libpsl, libsasl, libsigsegv, libsm, libssh2, libsynctex, libsystemd, libtasn1, libtiff, libtirpc, libunistring, libutil-linux, libwebp, libx11, libxau, libxaw, libxcb, libxdmcp, libxext, libxmu, libxpm, libxrender, libxt, lz4, lzo, nspr, nss, openjpeg2, openssl, p11-kit, pam, pambase, pcre, pcre2, perl, perl-error, perl-mailtools, perl-timedate, pixman, poppler, potrace, run-parts, shadow, sqlite, t1lib, texlive-bin, texlive-core, xcb-proto, xorgproto, xz, zziplib
   Install   : isl
   Install   : cloog
   Install   : mingw-w64-gcc-base
   Install   : mingw-w64-crt
   Reinstall : binutils, gcc
   Install   : gcc-ada
   Remove    : mingw-w64-gcc-base
   Install   : mingw-w64-gcc
   Install   : mingw-w64-zlib
   Reinstall : libnsl, python2, scons
   Install   : nsis

?? Do you want to continue? Y/n:

Expected Behavior

Solution for package dependencies must be same for each run since there is no changes in packages installed between tries.

Version of `aurman` you are using

$ aurman -V 
:: 2.18-1

Distro - Arch

The cause is, that data structures are being used by the dependency solver which do not preserve the order, since they are only used for "is it inside?" and "is it not inside?".

Normally that's not a problem, but with this mingw-w64-* packages it is. As you can see, when the dependency solver tries to find a solution when using the mingw-w64-headers-bootstrap-5.0.3-1 dependency, there is no such solution. When not using it, there is a solution.

Unfortunate, but I guess I'll never change anything about it, because the real problem is the package. "Fixing" it is not even really possible, I could "fix" the consistency of aurman but that does not really help, since it is still quite impossible to detect which packages to use in order to find a solution.

This looks like a serious flaw in aurman.

To be honest: It is not. I do not feel like explaining why this is the case, because you have to look deep into the algorithm. Trust me with it or do not, I am nevertheless not going to change anything here

The equivalent of this behavior is if the AUR RPC would send the dependencies in a different order. You have to start "somewhere" when solving dependencies, and you can do that at the first item. The result is going to change then, if you are dealing with e. g. this mingw fuckery

Thanks! Will look into mingw packages then

Looks to me as yet another case of unnecessary complex implementation that results in naughty side effects - solving the mingw bootstrap issue that ends up breaking the solver, or whatever issue you tried to solve in the first place.

And what we obtain is an unreliable dependency solver, with the very same action resulting in different predicted packages. But sure, let's agree to disagree.

Nothing is broken. Absolutely nothing.

Nothing is broken. Absolutely nothing.

Look, I understand that constantly dealing with crappy users tends to put you on the defensive when dealing with criticism - I've been there before. However, it doesn't mean the dev is always right - and I've myself observed this many times before.

Having cases that can't be handled? That's fine, every helper has difficulty in a situation or another. But having cases that produce different results with the same input - while the AUR RPC data doesn't change - is a flaw. There is something to fix here, either by handling the case correctly or by stopping the process with an error message.

Regardless of the implemented algorithm, the solver is unreliable. From an user point of view, the question that naturally arises is "When can I trust aurman and when can I not?"
As of now, it is difficult to answer this question, and I certainly wouldn't claim that aurman has a reliable solver.

Something is certainly broken, yes.

However, it doesn't mean the dev is always right - and I've myself observed this many times before.

I've never said that the dev is always right. Anyway: I think that I am right in this case, let me explain in detail what is going on and why I have no intention to change anything.

In order to be able to build/install a package, all dependencies of that package need to be fulfilled. There is no such thing as "ordered" dependencies, a dependency is fulfilled or it is not. If there are all dependencies fulfilled, you may build/install, otherwise you may not.

The logical mathematical representation for dependencies is thus a set, which does not represent any kind of ordering. In fact, aurman uses sets at many points in the sourcecode when dealing with dependencies because of the O(1) lookup time, to check if a dependency is inside a set or not.

Now back to our problem. aurman -S nsis yields different results when executing multiple times. What happens is the following:

aurman fetches the needed dependencies and puts them into a set. At this point the ordering gets lost. You may iterate over a set, but the order for iterating is almost likely a different order than the order in which you put the dependencies into the set. When trying to solve the dependency problem, aurman iterates over the set, to fulfill the dependencies one by one, until all of them are fulfilled. With normal packages, that simply leads to a valid solution. NOTICE: The order in which the packages appear in the intern aurman solution may also be different here during different executions, but it really does not matter, as long as the packages are topologically sorted, the concrete order does not matter, as long as it is correct.

The mingw-w64-* packages however are different, you may not simply fulfill the dependencies, just look it up yourself, try to solve the problem with a pencil and paper and you'll see what happens. aurman supports the kind of bootstrapping, however the nsis package leads to even more fuckery than the normal mingw-w64-gcc package. It in fact matters, in which order the dependency solver of aurman tries to fulfill the dependencies, to find a valid solution. If the solver gets the mingw-w64-headers-bootstrap dependency before the mingw-w64-headers dependency, a solution cannot be found. Vice versa the solution can be found. This is quite impossible to detect programmatically, the only sensible thing to do would be to calculate the possible permutations of the dependencies (O(n!)) and try to solve the problem for all such permutations. This is clearly insane and nothing one should ever do.

Leaves us with: "But it is inconsistent", to which the answer is "Yes, but it does not matter unless your package is garbage". I could make it consistent by e.g. ordering all dependencies alphabetically when working with them, but that is complete nonsense. It leads to consistency but without any rational benefit. The correct mathematical representation is a set, changing this just for consistency without any other kind of benefit does not make any sense in my opinion, which is why I am not going to change anything here. By the way: The answer to the question

When can I trust aurman and when can I not?

Always, if aurman finds a solution, it is valid. The inconsistency in finding solutions does not mean, that there are invalid solutions which can be found by aurman mistakenly.

Always, if aurman finds a solution, it is valid.

With due respect, a solver that doesn't succeed when a solution exists, or that finds different solutions to the same input (sometime valid and sometimes not) is the opposite of "reliable" - by definition. I guess we have a very different definition of "reliable solver".

I understand what aurman tries to do, but it seems to aims at a tree in an over-engineered way but eventually miss the forest. When I see the simpler algo implemented in the deprecated pacaur actually achieves consistent and good results at the same issue, I can't do anything but roll my eyes.

But yes, solving dependencies is indeed a complex problem, and there is much progress to do among helpers here. I'm however not sure how you could claim aurman has a reliable solver - it's clearly not. Maybe because of your design that bring other advantages at the table, but it's inhenrently not reliable.

When I see the simpler algo implemented in the deprecated pacaur actually achieves consistent and good results at the same issue, I can't do anything but roll my eyes.

pacaur is able to install mingw-w64-gcc?

or that finds different solutions to the same input (sometime valid and sometimes not)

I explicitly stated that aurman does not find invalid solutions

Anyway: I made my point, unless you provide technical/mathematical arguments on how to solve this in an appropriate way, that's it. You saying: "I do not like it" without any constructive feedback on how to actually do it, does not help anyone. Saying: "It is wrong, fix it" is easy, but if you want to help me, provide useful feedback on how to do it. Everything else is useless

@AladW

Anyway: I do not feel like I want to develop this project as of now with feedback via GitHub issues anymore.

There are some valid reports like this one, but I am seriously too tired of all the nonsense which I have to discuss. aurman is working for me, my semester break is almost over and I want to focus on my degree. There is likely one aurman rewrite as my bachelors thesis, but currently I feel like I need a break from the whole AUR "community". Going to deactivate the issues later today, guess I'll ask @AladW to remove aurman from the AUR helper page, too. Not interested in new users, current users may migrate to yay.

I explicitly stated that aurman does not find invalid solutions

Which isn't the problem...

Anyway, if you want to look at a reliable solver, check out libsolv from SUSE - they use a satisfiability
algorithm - I guess it's at least in part similar to what aurman does, but with better constraints. They provide python bindings too, and have support for Arch repo (but not AUR).

Anyway: I do not feel like I want to develop this project as of now with feedback via GitHub issues anymore.

Very well - that I can understand.

@polygamma

@polygamma on the constructive side of things, in case it was an honest question and an answer might be useful. If you want the algo to be deterministic, use a sorted set for example. It's a set, you cannot have duplicates there and checking for existence is O(ln(n)) (not O(1) BTW). But it is also an ordered set, so you can always take a "lesser" element from it. Successful resolving will be deterministic as well (order of built packages).

Another alternative is to have a linear queue and an additional set I guess. Use the set to check existence, otherwise add to the linear queue. You don't need to remove deps, so I guess that works too.

Most importantly, enjoy your contributions and have fun.:) Don't mean to pressure, just throw in some technical answers to questions mentioned.

// If you'd ask me, I'd say the implementation looks like a "reliable" solver, but not "deterministic". Without determinism users aren't happy though :shrugs:.

In the end I wonder what's the point in having a dependency solver that rivals pacman itself in terms of complexity. (All pacman wrappers I know of which use pacman -U fall into this trap, eventually).

…

On Wed, Aug 21, 2019 at 12:31:41AM -0700, Vasili Novikov wrote: // If you'd ask me, I'd say the implementation looks like a "reliable" solver, but not "reproducible". Without reproducibility users aren't happy though :shrugs:. -- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: #259 (comment)

Navigation Menu

Repository navigation

Unreliable Dependecies resolution #259

Description

Expected Behavior

Version of `aurman` you are using

Distro - Arch

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Unreliable Dependecies resolution #259

Description

Description

Expected Behavior

Version of aurman you are using

Distro - Arch

Activity

polygamma commented on Aug 21, 2018

rmarquis commented on Aug 21, 2018

polygamma commented on Aug 21, 2018

polygamma commented on Aug 21, 2018

osleg commented on Aug 21, 2018

rmarquis commented on Aug 21, 2018

polygamma commented on Aug 21, 2018

rmarquis commented on Aug 21, 2018

polygamma commented on Aug 21, 2018

rmarquis commented on Aug 21, 2018

polygamma commented on Aug 21, 2018

polygamma commented on Aug 21, 2018

rmarquis commented on Aug 21, 2018

vn971 commented on Aug 21, 2019

vn971 commented on Aug 21, 2019

AladW commented on Aug 21, 2019

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions

Version of `aurman` you are using