Dependency resolution takes hours for multiple python version markers

[rootcss]

• I am on the latest Poetry version.
• I have searched the issues of this repo and believe that this is not a duplicate.
• If an exception occurs when executing a command, I executed it again in debug mode (-vvv option).

• OS version and name: macOS Big Sur 11.4
• Poetry version: 1.1.11

Issue

My project requires to use multiple python versions. Some of the packages are not compatible for both of those python versions, for which I'm using multiple-constraints-dependencies as shown below. Without this, the poetry lock --no-update -vvv command took just 10 seconds. However, after adding this it takes forever to run the dependency resolution. Below is the pyproject.toml file.

[tool.poetry]
name = "some-service"
version = "0.1.0"

[build-system]
requires = ["poetry-core>=1.0.0"]
build-backend = "poetry.core.masonry.api"

[tool.poetry.dependencies]
python = "3.6.10 || 3.9.5"
numpy = "1.19.3"
dropbox = [
    {version = "7.1.0", python = "3.6.10"},
    {version = "9.5.0", python = "3.9.5"}
]
gevent = [
    {version = "1.2.2", python = "3.6.10"},
    {version = "21.1.2", python = "3.9.5"}
]
guppy3 = [
    {version = "3.0.9", python = "3.6.10"},
    {version = "3.1.1", python = "3.9.5"}
]
Markdown = [
    {version = "2.6.6", python = "3.6.10"},
    {version = "3.3.4", python = "3.9.5"}
]
pexpect = [
    {version = "4.1.0", python = "3.6.10"},
    {version = "4.8.0", python = "3.9.5"}
]
scikit-learn = [
    {version = "0.20.4", python = "3.6.10"},
    {version = "0.24.2", python = "3.9.5"}
]
scipy = [
    {version = "1.5.4", python = "3.6.10"},
    {version = "1.7.1", python = "3.9.5"}
]
psycopg2 = [
    {version = "2.7.3.2", python = "3.6.10"},
    {version = "2.9.1", python = "3.9.5"}
]

[tool.poetry.dev-dependencies]
coverage = "4.4.1"

I observed that the time for resolution keeps increasing as the number of constraints increase. I'm suspecting it builds and resolves multiple dependency trees, causing it to take so long. In the logs, I saw it performed 510 overrides: 0: Complete version solving took 256.095 seconds with 510 overrides which seem to be permutations of above-mentioned constraints.

Is this expected behavior?

[radoering]

I stumbled upon the same behavior. Poetry tries all combinations for multiple-constraints-dependencies, even if markers exclude each other, which means that the concerning combination is not relevant. I am not sure if it is expected behavior, but in my opinion, it definitely is a weakness. Sometimes this weakness leads not only to a longer runtime, but also to the fact that the dependencies cannot be resolved (see #3367 for example). (However, I must add to this that I do not know any dependency management tool for python that can handle multi-constraints-dependencies even as good as poetry.)

Investigating #3367, I dived a little into the code. In general, changing the behavior of poetry in a way that only combinations whose intersection of markers is not empty are considered is not that difficult. However, there is at least one challenge that seems non-trivial (at least to me 😉 considering the current design of poetry):

If only combinations whose intersection is not empty are considered, libraries that are only required for a specific marker (e.g. one python version) might be discarded erroneously. E.g., in the following example the constraint for lib2 for python 3.8 would be ignored if combinations with an empty intersection of markers were discarded.

lib1= [
    {version = "1.0", python = "~3.6"},
    {version = "2.0", python = "~3.7"}
]
lib2 = [
    {version = "1.0", python = "~3.6"},
    {version = "2.0", python = "~3.7"},
    {version = "3.0", python = "~3.8"}
]

[radoering]

I think, I found a solution for this issue. With the changes in PR #4695, I get the same lock file and the following output 0: Complete version solving took 2.496 seconds with 24 overrides Not perfect, but a lot better.

[wcn00]

Just a me too comment. I've had python lock runs as long as 8 hrs.

[maciejskorski]

Just letting know that this PR for pre-filtering markers also can help here. If we know the target system in advance, e.g. python = 3.9, we avoid getting into exponentially many combinations.

[tool.poetry.target_env]
python_full_version = "3.9.5"

[github-actions]

This issue has been automatically locked since there has not been any recent activity after it was closed. Please open a new issue for related bugs.