Dependency resolver in Conan is not smart? Version conflict

[ilya-lavrenov]

What is your question?

I have a conantxt.file with the following content:

...
opencl-icd-loader/[>=2022.09.30]
opencl-clhpp-headers/[>=2022.09.30]
opencl-headers/[>=2022.09.30]
...

And during conan install I have:

Requirements
    ...
    opencl-clhpp-headers/2023.04.17#7c62fcc7ac2559d4839150d2ebaac5c8 - Downloaded (conancenter)
    opencl-headers/2022.09.30#ee45fce3f75c8803089c3b2546362187 - Downloaded (conancenter)
    opencl-icd-loader/2022.09.30#a757c4732c2aba4ab729746ed129c611 - Downloaded (conancenter)
    ...
Resolved version ranges
    ...
    opencl-clhpp-headers/[>=2022.09.30]: opencl-clhpp-headers/2023.04.17
    opencl-icd-loader/[>=2022.09.30]: opencl-icd-loader/2022.09.30
    ...
ERROR: Version conflict: opencl-clhpp-headers/2023.04.17->opencl-headers/2023.04.17, None->opencl-headers/2022.09.30.

We can see in CCI that OpenCL C and C++ headers have versions up to 2023.04.17, while latest version for OpenCL ICD loader is 2022.09.30. I expect that conan can understand that he should download all 3 packages of version 2022.09.30. But instead, it downloaded all the dependencies with latest versions and faced with version conflict because opencl-icd-loader requires old version of opencl-headers than opencl-clhpp-headers package.

Is it a bug? If no, what is the goal of having ranges in dependencies if conan cannot resolve them?

Have you read the CONTRIBUTING guide?

• [X] I've read the CONTRIBUTING guide

[memsharded]

Hi @ilya-lavrenov

The dependency resolver in Conan is not a full SAT solver that resolves for the joint compatibility of multiple different version ranges. There are a few reasons for this, but one of the main ones is that such solver is NP-complete, and the necessary backtracking can easily require the evaluation of many more hypothesis, and as every hypothesis might need to be found in the server, downloaded, unzipped, loaded, interpreted by Python and then evaluated, this quickly becomes intractable in practice.

So the algorithm is partially greedy, resolving depth-first, while also trying to reconcile some diamond structures, overrides and other version ranges, but up to a limit.

The recommendation is to have the version ranges consistent. In this case, the problem is that ConanCenter has not allowed version-ranges until now (we are just introducing version ranges for openssl and cmake, to evaluate things). But the real solution is that recipes in ConanCenter contain a consistent version range for opencl-headers/2023.04.17, in that way they will naturally resolve to it without conflicts. Up to our knowledge, enterprise users have been doing this with success for a while, it was just in ConanCenter that we had some infrastructure limitation (the necessary search to resolve version ranges was very slow, even doing timeouts), so we couldn't introduce version ranges earlier.

[DoDoENT]

I just stumbled upon the same issue, but with my local packages, none of them are from Conan Center.

In conan v1 we avoided using version ranges because lockfiles were very complicated. Instead, every internal package had a concrete version of all its dependencies and possibly overrode some upstream dependencies. Updating packages was very cumbersome because the developer needed to manually update versions to the latest possible while still retaining the combination that works, i.e. it wasn't just possible to "update everything to latest" due to the same issue as happened now in Conan Center: some low-level utility package moved to version e.g. 3.0, while some mid-level package v2.3 still wasn't updated to work with low-level v3.0, and then on high-level, the developer needed to know this details and be careful not to use low-level v3.0 until mid-level is updated to work with it. Add dozens of packages with such complex interdependencies and you end up with entire developer-week spent on solving package satisfiability manually by, usually junior, developers. I'm not kidding - this is so a serious issue for us that some people are trying to move us back to using monorepo and ditch conan altogether 😱 . Their rationale is that they would rather have longer build times than spend countless hours trying to find a "working combination" of packages.

Currently, I'm experimenting with Conan v2 and one of the promises I've given is to ease the pain of updating dependencies in complex graphs. Switching from semantic versioning to minor mode helped with that, but I kinda expected that by using version ranges in combination with v2 lockfiles and minor mode for the versioning scheme, I'll be able to define constraints in the high-level package by defining version ranges of packages I need, and conan lock create will resolve the dependency graph in a way that all latest possible packages are used, as long as constraints are satisfied.

Unfortunately, conan is not that smart, as already mentioned, and even fails on a simple example as this one:

Consider three packages: low-level, mid-level, and high-level.

The recipe for low-level is as simple as:

from conan import ConanFile

class lowRecipe(ConanFile):
    name = "low-level"

Let's create versions v1.0 and v1.5:

$ conan create . --version=1.0
$ conan create . --version=1.5

The recipe for mid-level would first be

from conan import ConanFile

class midRecipe(ConanFile):
    name = "mid-level"
    requires = "low-level/[<2.0]"

Let's call it "v1.1":

$ conan create . --version=1.1

Now, let's imagine that some functions in low-level have been renamed, so we bump the major version to indicate that packages that use it need to be adapted (their source changed):

# in low-level folder
$ conan create . --version=2.0

Then, the maintainer of the mid-level package then updates their package to work with the renamed function, but the API of the mid-level package is not changed, so there is no need for major version bump. However, they update the package's recipe to reflect that low-level/2.0 or newer is now required:

from conan import ConanFile

class midRecipe(ConanFile):
    name = "mid-level"
    requires = "low-level/[>=2.0]"

... and creates a new version of mid-level package:

# in mid-level folder
$ conan create . --version=1.2

The state of the cache is now:

$ conan list low-level
Local Cache
  low-level
    low-level/1.0
    low-level/1.5
    low-level/2.0
$ conan list mid-level
Local Cache
  mid-level
    mid-level/1.1
    mid-level/1.2

Completely unaware of these changes, some developer of the high-level package still expects their package with the following conanfile to work:

[requires]
low-level/[<2.0]
mid-level/[>=1.0]

[layout]
cmake_layout

However, if they try to create a lock file, conan fails:

$ conan lock create .

======== Computing dependency graph ========
Graph root
    conanfile.txt: /Users/dodo/Desktop/test-conan2-lock/high-level/conanfile.txt
Requirements
    low-level/1.5#65d13d92bb6abd0443d99146a4d5932b - Cache
    mid-level/1.2#df3dbe252af2534f60940252ea0e57a4 - Cache
Resolved version ranges
    low-level/[<2.0]: low-level/1.5
    mid-level/[>=1.0]: mid-level/1.2
ERROR: Version conflict: mid-level/1.2->low-level/[>=2.0], None->low-level/1.5.

This is not a good experience. The developer of the high-level package expects the conan lock create to resolve to mid-level/1.1 and low-level/1.5, even though mid-level/1.2 and low-level/2.0 exist.

I understand that conan can't be a full SAT solver by default, but maybe there could be an "opt-in" option, at least for lockfile creation, in order to solve issues as I described above. The alternative is to always manually resolve conflicts that are slow and cumbersome, especially on several dozen packages. I think it would be beneficial to the way a couple of minutes for conan lock create to complete rather than spend multiple hours on discovering the combination of packages/versions that work together.

[DoDoENT]

Maybe an off-the-shelf SAT solver, such as PySAT could be integrated into Conan to resolve these more complex constraints.

[memsharded]

The problem is not the SAT solver per-se, but that evaluating each hypothesis in the solver requires locating, downloading from the server, unzipping, copying, python-loading and interpreting, and Conan evaluation (injection of profile, computing the relevant configure(), requirements() etc methods), of the hypothesis (with back tracking over all versions and recipe revisions). The result is that for real life dependency graphs (average ones are in the range of 100-200 packages easily), the typical resolution would take easily many many hours, we are not talking about a couple of minutes. Not viable.

Note that there is another reason besides technical viability: not everyone agrees that mid-level/1.1 should be the right solution to the problem above. From what we have talked with many users, a lot of them prefer the conflict to be raised. This is because once that mid-level/1.2 has been released, using the improved low-level/2.0 major version, the expectations from users that do requires = "mid-level/[>=1.0]" is that it will be using it ("it 1.2 is there, it is released, it is included in my defined range, it must be either used, or fail"). As sometimes this is not in the final consumer, it might not be that evident, and the final result is that the old mid-level/1.1 with the older low-level/1.5 that has been already replaced by low-level/2.0 is not being used in the release of my final project to my customers, because the dependency manager decided to use an older mid-level/1.1 version to avoid some conflict with other constraint elsewhere in my 200 packages dependency graph. Not good. So there are functional reasons to fail explicitly instead of backtracking to older versions.

In practice Conan 2.0 is a big leap forward in this regard (with things like fast evaluation of version ranges in the server, that was a major investment of time, remember that used to take a few minutes for every call, and even timeout), and from what we have seen in users, some communication over what are the expected version ranges ("hey, team, we are starting to use breaking major low-level/2.0 new package with incompatible api, please start requiring low_level/[>=2.0]") should reduce the issue in practice to one or two orders of magnitude less than in Conan 1.X. So with a little discipline in the use and aligning of the version-ranges, the speed of integrating new versions is greatly reduced, while keeping conflicts really to a minimum. and much easier to solve than in 1.X. But still the discipline and communication of version ranges, specially when there are important changes, is necessary.

I hope this helps clarifying why a full SAT solver is not planned at this moment.

[DoDoENT]

From what we have talked with many users, a lot of them prefer the conflict to be raised.

I'd also prefer the conflict to be raised. But this is just a first step. After that, the conflict needs to be resolved. And here, it'd be great to have an opt-in option that would find a package combination that satisfies all constraints, even if it takes a couple of hours. This would still be faster than doing the same manually. It should up to the developer to choose whether they want to invest time into changing their codebase to work with latest versions of dependencies, change the constraints so that the current dependency resolver is satisfied or run the full SAT solver to find a combination of packages so that they are as latest as possible, but still satisfying all constraints imposed by the conanfile.

As sometimes this is not in the final consumer, it might not be that evident, and the final result is that the old mid-level/1.1 with the older low-level/1.5 that has been already replaced by low-level/2.0 is not being used in the release of my final project to my customers, because the dependency manager decided to use an older mid-level/1.1 version to avoid some conflict with other constraint elsewhere in my 200 packages dependency graph. Not good.

Well, that depends on how you look at it. I completely agree with you in case when new feature development is taking place. However, when you checkout old commit to backport a fix, you may only want to update certain packages that brought the fix. For example, low-level/1.5 contains the fix, while keeping the same API. If the developer of high-level package knows that, they can simply manually add low-level/1.5 requirement directly to their lockfile, using the approach that documentation says is not recommended.

However, the developer can't know if simply adding low-level/1.5 will work against already locked dependencies of low-level. Maybe upgrading low-level to 1.5 requires updating some lower-level to some version in order to have it built (let's say to v3.9), and so on. In the world with perfect information, all packages would have correct version ranges and such change would trigger a version conflict in conan. Unfortunately, in real world, the developer of low-level/1.5 never tested that their code builds against lower-level/3.4, which was locked in high-level package - they only tested against the latest lower-level/3.9 that was the latest at that time, and thought that it would work with any lower-level/[~3] (ideally, they would set dependency to lower-level/[>=3.9], but they didn't).

The build error that developer of high-level package would get would be completely incomprehensible to them, especially if they don't know the details of low-level package. But, even if the developer of low-level/1.5 correctly specified dependency to lower-level/[>=3.9], the developer of high-level package would still get an error, although a nicer one - the conan version conflict. After that, they need to manually debug and discover the combination of packages that will work for their constraints (notably, setting lower-level to 3.9 in this example). And this is slow and manual work.

Wouldn't it be great if the developer of high-level would invoke a tool that will do that work for them? Namely, find the combination of packages that satisfy their constraints or inform them that no such combination exists. Then, the developer could more easily estimate how much time they need to invest in upgrading dependencies to provide the bugfix release and inform the customer. WIth the current process, you can never know how much work you need to do before you find a working combination, and that ends up with a lot of frustration.

I think the full dependency SAT solver should never be the default. However, if implemented, I think it would bring value as an opt-in option.

I'll investigate if I can implement that as a conan custom command (I'm not sure at the moment that Conan's public API provides everything needed for this)...

[memsharded]

I'd also prefer the conflict to be raised. But this is just a first step. After that, the conflict needs to be resolved. And here, it'd be great to have an opt-in option that would find a package combination that satisfies all constraints, even if it takes a couple of hours. This would still be faster than doing the same manually

We hope that the work being done in the graph html output regarding to conflict representation will help to track much, much faster the origin of conflicts and how to solve them, see https://github.com/conan-io/conan/pull/13946#issuecomment-1588159878

[DoDoENT]

We hope that the work being done in the graph html output regarding to conflict representation will help to track much, much faster the origin of conflicts and how to solve them, see https://github.com/conan-io/conan/pull/13946#issuecomment-1588159878

Great to see this work being done. Hopefully, it will help with visualizing all problematic conflicts so that humans will have an easier time resolving them. I'm looking forward to it.

[samuel-emrys]

I'd also like to express interest in an opt-in full dependency SAT solver. This was a big part of our justification for moving to a package manager, but we haven't yet reached maturity to be able to exercise this and didn't realise this wasn't a conan feature. Finding out it wasn't was a bit alarming. The improvements in graph visualisation will certainly help, but I'm still interested in an opt-in full dependency SAT solver.

[ilya-lavrenov]

We have the following conanfile.txt in our repository https://github.com/openvinotoolkit/openvino/blob/master/conanfile.txt It lists onnx as well as protobuf with exact versions.

Each time when onnx recipe is updated with new version of protobuf, we have the following issues on our CI:

Resolved version ranges
    ittapi/[>=3.23.0]: ittapi/3.24.0
    onetbb/[>=2021.2.1]: onetbb/2021.9.0
    pugixml/[>=1.10]: pugixml/1.13
    snappy/[>=1.1.7]: snappy/1.1.10
    xbyak/[>=6.62]: xbyak/6.73
ERROR: Version conflict: Conflict between protobuf/3.21.12 and protobuf/3.21.9 in the graph.
Conflict originates from onnx/1.13.1

How can we resolve it without dependency resolver in Conan itself?

I would treat the issue as Conan bug, because it does not provide usable functionality - users cannot have reproducible results, because someone can update existing conan-center-index recipes and they will conflict with users recipes. The same would be inside Conan-center-repo, when we submit our recipe there - multiple recipes must be synchronized because they list the same requirement.

Possible solution from conda-forge: they have pinning repo https://github.com/conda-forge/conda-forge-pinning-feedstock where common libraries versions are pinned, so they are aligned across multiple feedstocks (recipes).

[samuel-emrys]

I would treat the issue as Conan bug, because it does not provide usable functionality - users cannot have reproducible results, because someone can update existing conan-center-index recipes and they will conflict with users recipes. The same would be inside Conan-center-repo, when we submit our recipe there - multiple recipes must be synchronized because they list the same requirement.

Possible solution from conda-forge: they have pinning repo https://github.com/conda-forge/conda-forge-pinning-feedstock where common libraries versions are pinned, so they are aligned across multiple feedstocks (recipes).

It doesn't make sense to pin versions/revisions at the recipe level; every graph is different and everyone has different requirements. You can do this at the consumer level with lock files though. Check out the docs on lockfiles for more context, but it allows you to specify the revision of a recipe so that upstream changes don't affect you, allowing reproducibility.

The presence of a SAT solver is more around constructing a valid dependency tree in the first instance or when upgrades are required.

[memsharded]

Yes, using lockfiles is recommended for this use case. We have started to document these things in the new "Devops guide" section: https://docs.conan.io/2/devops/using_conancenter.html

[samuel-emrys]

I'd also prefer the conflict to be raised. But this is just a first step. After that, the conflict needs to be resolved. And here, it'd be great to have an opt-in option that would find a package combination that satisfies all constraints, even if it takes a couple of hours. This would still be faster than doing the same manually. It should up to the developer to choose whether they want to invest time into changing their codebase to work with latest versions of dependencies, change the constraints so that the current dependency resolver is satisfied or run the full SAT solver to find a combination of packages so that they are as latest as possible, but still satisfying all constraints imposed by the conanfile.

@memsharded is it possible to consider an opt-in full sat solver? We're already coming up against this problem when we have sufficiently complex graphs, and having a mechanism to have conan search for and find a solution infrequently would be very useful, even if it takes a long time.

[memsharded]

This is not planned at the moment, there are many other higher priorities. In any case, the "very long time" for mid or big size graphs, is not a couple of minutes. It could easily be hours, something it is known that would render the attempt useless, and it would still be way more effective to do a conan graph info --format=html and inspect the graph, now with the conflict representation in the graph, it should be way easier to detect and solve.