Bug 833538

Summary: YUM dependency resolution algorithm bug
Product: Red Hat Enterprise Linux 5 Reporter: Sergio Freire <sergio-s-freire>
Component: yumAssignee: James Antill <james.antill>
Status: CLOSED NOTABUG QA Contact: BaseOS QE Security Team <qe-baseos-security>
Severity: unspecified Docs Contact:
Priority: unspecified    
Version: 5.5CC: nmo.marques, sergio-s-freire
Target Milestone: rc   
Target Release: ---   
Hardware: Unspecified   
OS: Linux   
Whiteboard:
Fixed In Version: Doc Type: Bug Fix
Doc Text:
Story Points: ---
Clone Of: Environment:
Last Closed: 2012-06-19 14:19:23 EDT Type: Bug
Regression: --- Mount Type: ---
Documentation: --- CRM:
Verified Versions: Category: ---
oVirt Team: --- RHEL 7.3 requirements from Atomic Host:
Attachments:
Description Flags
spec files and yum output of success and fail none

Description Sergio Freire 2012-06-19 13:22:27 EDT
Created attachment 593021 [details]
spec files and yum output of success and fail

Description of problem:
yum seems not to be able to resolve dependencies correctly, even if their dependencies are in theory fully solvable.

Lets consider a yum repository we have the following packages:
 - rubygem-thor-0.14.6-1.ptin.el5.noarch
 - rubygem-thor-0.15.2-1.ptin.el5.noarch
 - pacote-a-1.0-1.ptin.el5.x86_64
 - pacote-b-1.0-1.ptin.el5.x86_64
 - pacote-c-1.0-1.ptin.el5.x86_64
 - pacote-d-1.0-1.ptin.el5.x86_64


Unsolvable Case
===============
Say we have a package named "terceiro" which depends on two other ("pacote-a" and "pacote-b").
"pacote-a" requires rubygem(thor)< 1.0 and rubygem(thor) >= 0.14.
"pacote-b" requires rubygem(thor)< 0.15.0 and rubygem(thor) >= 0.14.6.
We are unable to install "terceiro" using yum since it says the "rubygem(thor) < 0.15.0" dependency is missing.

Solvable Case
=============
Say we have a package named "quarto" (similar to "terceiro") which depends on two other ("pacote-c" and "pacote-d"). We copied the contents of pacote-a.spec to pacote-d.spec and pacote-b.spec to pacote-c.spec, respectively. We are basically changing artificially the order during yum dependency resolution, but maintaining the contents/dependencies.
So now,
"pacote-c" requires rubygem(thor)< 0.15.0 and rubygem(thor) >= 0.14.6.
"pacote-d" requires rubygem(thor)< 1.0 and rubygem(thor) >= 0.14.

Thus, we are ABLE to install "quarto", although the dependencies are exactly the same.


Version-Release number of selected component (if applicable):
yum-3.2.22-26.el5

How reproducible: always


Steps to Reproduce:
1. build the "pacote-[abcd]", "terceiro" and "quarto" RPMs using the provided spec files, and upload them to a YUM repository
2. have two RPMs rubygem-thor, as mentioned above, in a YUM repository
3. yum -d 10 install terceiro
3. yum -d 10 install quarto
  
Actual results:
only when dependencies are in the correct order, when the first dependency resolution chooses the "correct" package, the final resolution is OK.
in the first case, since rubygem-thor (0.15.2) is chosen then it does not comply with the dependency rubygem(thor) < 0.15.0 of "pacote-b".

Expected results:
packages ("terceiro" and "quarto") should always be able to install, using the rubygem-thor (0.14.6) dependency.

Additional info:
Note that we are using multiple "Requires" lines in order to limit the version of the dependency.
See yum logs attached of the two yum attempts, with debug enabled.
Comment 1 James Antill 2012-06-19 14:19:23 EDT
> Say we have a package named "terceiro" which depends on two other ("pacote-a" and "pacote-b").
> "pacote-a" requires rubygem(thor)< 1.0 and rubygem(thor) >= 0.14.
> "pacote-b" requires rubygem(thor)< 0.15.0 and rubygem(thor) >= 0.14.6.

 This kind of thing is just never going to work before RHEL-8 ... and it is very unlikely to work _well_ even then, you can test Hawkeye/DNF in rawhide now and provide feedback.

 The reason it doesn't work now is because the current depsolver just tries to solve each "prco" as it gets to it ... and it almost never looks at downgrades. It does try to sort them so that it'll look at "<" before ">=" so in the above case if it hits "foo < 15" it'll probably choose a package that satisfies all 4 requirements ... but that's mostly luck.

 The reason it can't easily work well in general is because even if you install "foo-0.14.5" when "foo-0.18" is available ... there is no good way to communicate that information into the update logic. So everytime something asks "are there updates" yum will respond "sure, foo-0.18 is available and updates foo-0.14.5" ... then it'll try to actually do it and fail.

 In short ... don't do that.