Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

[SR-4400] Resolver is doing too much work #5054

Closed
swift-ci opened this issue Mar 28, 2017 · 4 comments
Closed

[SR-4400] Resolver is doing too much work #5054

swift-ci opened this issue Mar 28, 2017 · 4 comments
Labels
bug

Comments

@swift-ci
Copy link
Contributor

Previous ID SR-4400
Radar rdar://problem/31498610
Original Reporter carlb (JIRA User)
Type Bug
Status Resolved
Resolution Invalid

Attachment: Download

Environment

Tried on Darwin Carls-MacBook-Pro.local 16.4.0 Darwin Kernel Version 16.4.0: Thu Dec 22 22:53:21 PST 2016; root:xnu-3789.41.3~3/RELEASE_X86_64 x86_64
and Linux swift-testbuilds01.ibmswift.com 4.4.0-53-generic #74-Ubuntu SMP Fri Dec 2 15:59:10 UTC 2016 x86_64 x86_64 x86_64 GNU/Linux

Additional Detail from JIRA
Votes 6
Component/s Package Manager
Labels Bug
Assignee None
Priority Medium

md5: 2fa673f5f312efe231ab4168f54763b4

is duplicated by:

  • SR-4399 swift package fetch spins with invalid tags
  • SR-4476 Selecting a higher binding sends the resolver in recursion
  • SR-5956 Some repos cannot be fetched
  • SR-6318 Swift Package manager hanging
  • SR-6389 Swift Package Manager hangs indefinitely, doesn't provide any feedback on what's gone wrong.

relates to:

  • SR-4399 swift package fetch spins with invalid tags
  • SR-4476 Selecting a higher binding sends the resolver in recursion

Issue Description:

Running `swift package fetch` on the repo https://github.com/carlbrown/Blitter/tree/spm_infinite_loop gives me:

```
error: The dependency graph could not be satisfied (https://github.com/IBM-Swift/BlueSocket.git)
```

with SPM on Swift 3.0.2 and a seemingly infinite loop when running the same command on Swift 3.1. `swift package -v fetch` log attached.
@ankitspd
Copy link
Member

ankitspd commented Apr 7, 2017

Looks like the problem is not recursion but resolver having to do a lot of work, which depends on the number of dependencies and the eligible versions for each constraint that is encountered.

I created a mock test to demonstrate this: https://github.com/aciidb0mb3r/swift-package-manager/blob/fix-long-wait/Tests/PackageGraphTests/DependencyResolverTests.swift#L618
A valid solution is possible but the resolver iterates all 50 versions of the BlueSocket dependency before reaching the solution. This resolves pretty quickly in the mock test but in real world, it means having to parse all 50 manifests and their tools-version. Tweaking the input constraints makes this resolve quicker because the wrong versions are never iterated. Here are some logs that I placed in the test:

$ st -s PackageGraphTests.DependencyResolverTests/testComplex
Test Suite 'Selected tests' started at 2017-04-07 16:31:28.247
Test Suite 'SwiftPMPackageTests.xctest' started at 2017-04-07 16:31:28.247
Test Suite 'DependencyResolverTests' started at 2017-04-07 16:31:28.247
Test Case '-[PackageGraphTests.DependencyResolverTests testComplex]' started.
Trying to merge Kassandra @ 0.2.3
Trying to merge BlueSocket @ 0.12.49
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.48
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.47
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.46
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.45
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.44
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.43
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.42
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.41
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.40
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.39
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.38
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.37
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.36
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.35
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.34
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.33
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.32
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.31
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.30
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.29
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.28
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.27
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.26
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.25
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.24
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.23
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.22
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.21
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.20
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.19
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.18
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.17
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.16
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.15
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.14
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.13
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.12
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.11
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.10
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.9
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.8
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.7
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.6
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.5
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.4
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.3
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.2
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.1
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge BlueSocket @ 0.12.0
Trying to merge Kitura @ 1.0.0
Unabled to merge:
[BlueSocket @ 0.11.0..<0.12.0]
into
[Kassandra @ 0.2.0..<0.3.0, Kitura @ 1.0.0..<1.1.0, BlueSocket @ 0.12.0..<0.13.0, ]
==========
Trying to merge Kassandra @ 0.2.2
Trying to merge BlueSocket @ 0.11.49
Trying to merge Kitura @ 1.0.0
Trying to merge BlueSocket @ 0.11.49
[(container: "Kassandra", binding: 0.2.2), (container: "Kitura", binding: 1.0.0), (container: "BlueSocket", binding: 0.11.49)]
Test Case '-[PackageGraphTests.DependencyResolverTests testComplex]' passed (0.099 seconds).
Test Suite 'DependencyResolverTests' passed at 2017-04-07 16:31:28.346.
     Executed 1 test, with 0 failures (0 unexpected) in 0.099 (0.099) seconds
Test Suite 'SwiftPMPackageTests.xctest' passed at 2017-04-07 16:31:28.346.
     Executed 1 test, with 0 failures (0 unexpected) in 0.099 (0.099) seconds
Test Suite 'Selected tests' passed at 2017-04-07 16:31:28.346.
     Executed 1 test, with 0 failures (0 unexpected) in 0.099 (0.099) seconds

@ankitspd
Copy link
Member

ankitspd commented Apr 7, 2017

@swift-ci create

@swift-ci
Copy link
Contributor Author

Comment by Mathäus Zingerle (JIRA)

Any update on this one? Especially for "beginners" it's hard to know why the SPM hangs and it can be frustrating because you might just think that it takes some time and only after some research you find out that it might be that dependencies can't be resolved. Other package managers immediately give you that feedback and stop with an error.

@ankitspd
Copy link
Member

SwiftPM has adopted a new dependency resolution implementation (in Swift 5.2) and such issues should no longer happen.

@swift-ci swift-ci transferred this issue from apple/swift-issues Apr 25, 2022
@shahmishal shahmishal transferred this issue from apple/swift May 4, 2022
This issue was closed.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
2 participants
@ankitspd @swift-ci