Abstract
Dependency solving is a hard (NP-complete) problem in all non-trivial component models due to either mutually incompatible versions of the same packages or explicitly declared package conflicts. As such, software upgrade planning needs to rely on highly specialized dependency solvers, lest falling into pitfalls such as incompleteness - a combination of package versions that satisfy dependency constraints does exist, but the package manager is unable to find it. In this paper we look back at proposals from dependency solving research dating back a few years. Specifically, we review the idea of treating dependency solving as a separate concern in package manager implementations, relying on generic dependency solvers based on tried and tested techniques such as SAT solving, PBO, MILP, etc. By conducting a census of dependency solving capabilities in state-of-the-art package managers we conclude that some proposals are starting to take off (e.g., SAT-based dependency solving) while - with few exceptions - others have not (e.g., outsourcing dependency solving to reusable components). We reflect on why that has been the case and look at novel challenges for dependency solving that have emerged since.
Original language | English |
---|---|
Title of host publication | 2020 IEEE 27th International Conference on Software Analysis, Evolution and Reengineering (SANER) |
Subtitle of host publication | Proceedings |
Editors | Kostas Kontogiannis, Foutse Khomh, Alexander Chatzigeorgiou, Marios-Eleftherios Fokaefs, Minghui Zhou |
Publisher | IEEE |
Pages | 547-551 |
Number of pages | 5 |
ISBN (Electronic) | 978-1-7281-5143-4 |
ISBN (Print) | 978-1-7281-5144-1 |
DOIs | |
Publication status | Published - 2020 |
Event | 27th IEEE International Conference on Software Analysis, Evolution, and Reengineering, SANER 2020 - London, Canada Duration: 18 Feb 2020 → 21 Feb 2020 |
Conference
Conference | 27th IEEE International Conference on Software Analysis, Evolution, and Reengineering, SANER 2020 |
---|---|
Country/Territory | Canada |
City | London |
Period | 18/02/20 → 21/02/20 |
Keywords
- dependency solving
- package manager
- SAT solving
- separation of concerns
- software components