[bug] Semantic versioning with tilde sign fails

stevn commented 1 year ago

I have a dependency tree which I want to realise using semantic versioning:

semver_a/1.0.0 -> semver_b/1.0.0 -> semver_super/1.0.0
semver_a/1.1.0 --------------------------^

But when I specify dependencies in the requirements() function using version ranges like [~1.0.0] instead of [>=1.0.0 <2], I get an error.

Environment Details (include every applicable attribute)

Operating System+version: MacOS 12.6.1
Compiler+version: Apple Clang 14.0.0
Conan version: 1.54.0
Python version: 3.10.6

Steps to reproduce (Include if Applicable)

Please see repo at:

https://github.com/stevn/conan-semver-trial

Logs (Executed commands with output) (Include/Attach if Applicable)

WARN: semver_b/1.0.0: requirement semver_a/[~1.0.0] overridden by semver_super/1.0.0 to semver_a/1.1.0
ERROR: Version range '~1.0.0' required by 'semver_b/1.0.0' not valid for downstream requirement 'semver_a/1.1.0'

memsharded commented 1 year ago

Hi @stevn

Are you completely sure that when you use the [>=1.0.0 <2] the error goes away? Could you please double check?

The thing is that it doesn't seem an issue in the semver resolution, but it is a result of how Conan resolves version ranges. Let me clarify a bit how it works:

Conan dependency resolution is "greedy", it evaluates, depth-first the dependencies as they come. Version ranges in this depth-first are resolved to the according range.
If later, another branch of the graph with a different version range produces a diamond structure to a resolved one, it might not be valid anymore. This also means that the order of declaration of requires also matter, as the depth-first expands first the first declared require
Finding a jointly compatible set of dependencies that satisfies all version ranges is known to be a NP-hard problem (SAT), that requires backtracking, and we have estimated that with the cost of every hypothesis (that typically involves downloading a recipe, unzipping, loading the file, parsing it with Python, evaluating the Conanfile), it will become very easily intractable in practice for even quite small problems.

So Conan 2.0 has improved a bit how version-ranges are resolved, and tries to achieve a better resolution of version ranges in parallel branches of the graph, but still it is not a full SAT resolution, so it is expected that some version ranges will still not be able to avoid some conflicts.

Please let me know if the [>=1.0.0 <2] really works, then, we probably need to investigate this a bit more.

stevn commented 1 year ago

Yes I've double checked. Just checkout my repo and call build.py to reproduce.

It doesn't work in my "main" branch, where tilde is used.

It DOES work in my "workaround" branch, where [>=1.0.0 <2] is used.

stevn commented 1 year ago

@memsharded Thanks for your explanation.

I have installed Conan 2.0 (Conan version 2.0.0-beta5) via python3 -m pip install conan --pre and am now getting the following error for my "main" branch (where tilde is used):

-------- Computing dependency graph --------
Graph root
    virtual
Requirements
    semver_a/1.1.0#04537e5835ebe3654c2ff4ce91d45796 - Cache
    semver_b/1.0.0#2d4cbb13d8d7c03f066d1cd2d6bbdd4c - Cache
    semver_super/1.0.0#6460aaf85517ae9e8211b51f44e19579 - Cache
Resolved version ranges
    semver_a/[~1.1.0]: semver_a/1.1.0
    semver_b/[~1.0.0]: semver_b/1.0.0
Graph error
    Version conflict: semver_b/1.0.0->semver_a/[~1.0.0], None->semver_a/1.1.0.
ERROR: Version conflict: semver_b/1.0.0->semver_a/[~1.0.0], None->semver_a/1.1.0.

In my "workaround" branch (which uses greater-than instead of tilde), however, the build works OK with Conan 2.0-beta5 - as with Conan v1.54.0.

So this semver problem seems to behave in the same way in Conan 1.54 as in Conan 2.0-beta5.

On the other hand, you mentioned that the order of requires() may be relevant. So I checked out the "broken" main branch again (which uses tilde). There, when I switch the order of requires() in the super/conanfile.py, I get a similar error:

-------- Computing dependency graph --------
Graph root
    virtual
Requirements
    semver_a/1.0.0#8fa0b1e45959a43a85b4381e6e81a4b4 - Cache
    semver_b/1.0.0#2d4cbb13d8d7c03f066d1cd2d6bbdd4c - Cache
    semver_super/1.0.0#b65293810bbb2ed416fc1d0fec90ca52 - Cache
Resolved version ranges
    semver_a/[~1.0.0]: semver_a/1.0.0
    semver_b/[~1.0.0]: semver_b/1.0.0
Graph error
    Version conflict: semver_super/1.0.0->semver_a/[~1.1.0], None->semver_a/1.0.0.
ERROR: Version conflict: semver_super/1.0.0->semver_a/[~1.1.0], None->semver_a/1.0.0.

So the problem seems to boil down to the question of the definition of how Conan resolves version ranges using tilde.

memsharded commented 1 year ago

Thanks for the details. I have been able to reproduce with this unit test:

def test_version_range():
    # https://github.com/conan-io/conan/issues/12519
    c = TestClient()
    c.save({"pkga/conanfile.py": GenConanfile("pkga"),
            "pkgb/conanfile.py": GenConanfile("pkgb", "1.0").with_requires("pkga/[~1.0.0]"),
            "pkgc/conanfile.py": GenConanfile("pkgc", "1.0").with_requires("pkga/[~1.1.0]",
                                                                           "pkgb/[~1.0.0]")
            })
    c.run("create pkga 1.0.0@")
    c.run("create pkga 1.1.0@")
    c.run("create pkgb")
    c.run("create pkgc", assert_error=True)
    assert "ERROR: Version range '~1.0.0' required by 'pkgb/1.0' "\
           "not valid for downstream requirement 'pkga/1.1.0'" in c.out

    # This looks the same, but apparently it isn't
    c.save({"pkga/conanfile.py": GenConanfile("pkga"),
            "pkgb/conanfile.py": GenConanfile("pkgb", "1.0").with_requires("pkga/[>=1.0.0 <2]"),
            "pkgc/conanfile.py": GenConanfile("pkgc", "1.0").with_requires("pkga/[~1.1.0]",
                                                                           "pkgb/[~1.0.0]")
            })
    c.run("create pkga 1.0.0@")
    c.run("create pkga 1.1.0@")
    c.run("create pkgb")
    c.run("create pkgc")
    assert "pkga/1.1.0" in c.out

    # This is equivalent
    c.save({"pkga/conanfile.py": GenConanfile("pkga"),
            "pkgb/conanfile.py": GenConanfile("pkgb", "1.0").with_requires("pkga/[~1]"),
            "pkgc/conanfile.py": GenConanfile("pkgc", "1.0").with_requires("pkga/[~1.1.0]",
                                                                           "pkgb/[~1.0.0]")
            })
    c.run("create pkga 1.0.0@")
    c.run("create pkga 1.1.0@")
    c.run("create pkgb")
    c.run("create pkgc")
    assert "pkga/1.1.0" in c.out

The reasons seems to be that indeed [~1.0.0] is not equivalent to [>=1.0.0 <2]. To get a pattern that could match 1.1.0, it would be necessary to use [~1]

This seems aligned with https://jubianchi.github.io/semver-check/#/~1.0.0/1.1.0, and the specification of semver. We did not implement semver ourselves, but using a third party dependency for it in 1.X, then we implemented it in 2.0, but we used the same rules and behavior.

stevn commented 1 year ago

@memsharded Thanks for the update! I will read up on semver and get back to you...

stevn commented 1 year ago

@memsharded I've checked https://github.com/npm/node-semver and now understand. I had misunderstood the meaning of tilde semver version ranges (I basically had the meaning of caret version ranges in mind). I have updated my repo and retested this with Conan 1.54 and Conan 2.0-beta5. It now works as expected in both versions, thanks!

memsharded commented 1 year ago

Excellent! Thanks for the feedback!

conan-io / conan