[8pt][SPIKE]Use backtracking for "latest" recommendation types

[fridex]

Problem statement

Some requirements fail to be resolved from time to time even though a resolution for the given set of requirements exists. This is caused by the nature of the algorithm used when resolving "latest". It might be worth experimenting with other algorithms to have more deterministic resolution - the adviser could use backtracking if resolving "latest" versions of software packages similarly as pip does and leave the algorithm based on TD-learning solely when resolving other recommendation types. Otherwise, it might be worth checking if we can adjust the heuristics of the "latest" predictor for selecting a specific version.

[mayaCostantini]

/sig stack-guidance

[goern]

/priority critical-urgent

[mayaCostantini]

https://pip.pypa.io/en/stable/topics/dependency-resolution/

[mayaCostantini]

/assign @mayaCostantini

[harshad16]

The documentation also has details on limitation
https://pip.pypa.io/en/stable/topics/dependency-resolution/#possible-ways-to-reduce-backtracking

Maybe we would have to use them for a smooth resolution report.

[mayaCostantini]

/lifecycle active

[codificat]

For anecdotal evindence, just adding a couple of instances where I think the advice provided with latest looks strange / unexpected:

• Downgrading packages and introducing already-fixed CVEs: Auto generated update ps-cv#45 (review)
• Downgrading from a released version to an older pre-release version: Auto generated update ps-cv#43 (review)
• Downgrading to a 4+ years old version: Auto generated update python#480 (review)

[KPostOffice]

If we do decide to use backtracking, couldn't we use pip directly as it already does backtracking with latest versions? This makes me wonder what the benefit of adviser for someone who needs latest recommendations is. What benefit does latest advise offer over a simple pip install or pipenv install?

[harshad16]

Great question. The reason could be to have advise report containing information if there is additional CVE, security concern, or any other information related to the latest stack. As this kinda information is not available from pip or pipenv, users might have to go over a varied number of places to gather this information.
Though it is valid on pip vs thamos on the latest the behavior is to get the latest package, if we don't have any information about the package version, then it is same as pip installed package, we should have consensus on this behaviour and which way to move towards.