<div dir="ltr">Hello Everyone!<br><br>I had previously sent a mail on this list, stating that I would like to work on pip's dependency resolution for my GSoC 2017. I now have drafted a proposal for the same; with help from my mentors - Donald Stufft and Justin Cappos. I'd also take this opportunity to thank them for agreeing to be my mentors for this GSoC.<br><br>I would like to request for comments on my proposal for GSoC - it is hosted at <a href="https://gist.github.com/pradyunsg/5cf4a35b81f08b6432f280aba6f511eb">https://gist.github.com/pradyunsg/5cf4a35b81f08b6432f280aba6f511eb</a>.<br><br>Please find trailing a MarkDown version of the proposal.<br><br>Thanks,<br>Pradyun Gedam<br><br>-----<br><br># Adding Proper Dependency Resolution to pip<br><br>- **Name:** Pradyun S. Gedam<br>- **Email:** [<a href="mailto:pradyunsg@gmail.com">pradyunsg@gmail.com</a>][mailto-email]<br>- **Github:** [pradyunsg][github-profile]<br>- **University:** [VIT University, Vellore, India][vit-homepage]<br>- **Course:** Bachelor of Technology in Computer Science and Engineering<br>- **Course Term:** 2016/17 - 2019/20 (4 Year)<br>- **Timezone:** IST (GMT +5:30)<br>- **GSoC Blog RSS Feed URL:** <<a href="https://pradyunsg.github.io/gsoc-2017/feed.xml">https://pradyunsg.github.io/gsoc-2017/feed.xml</a>><br><br>[github-profile]: <a href="http://github.com/pradyunsg/">http://github.com/pradyunsg/</a><br>[vit-homepage]: <a href="http://vit.ac.in/">http://vit.ac.in/</a><br>[mailto-email]: mailto:<a href="mailto:pradyunsg@gmail.com">pradyunsg@gmail.com</a><br><br>## About Me<br><br>I was introduced to Python about five years ago, through "Core Python<br>Programming" by Weasley J Chun. After the initial struggle with Python 2/3, the<br>ball was set rolling and hasn't stopped since. I have fiddled around with<br>Game Programming (PyGame), Computer Vision (OpenCV), Data Analytics (Pandas,<br>SciPy, NumPy), transcompilers (Py2C) and more.<br><br>As a high school student, I did internship at Enthought in 2013 and 2014.<br>The two summers that I spent at Enthought were a great learning experience and<br>I thoroughly enjoyed the environment there.<br><br>Other than Python, I have also used C, C++, Web Technologies (JavaScript, HTML,<br>CSS) and preprocessors (Pug, TypeScript, LESS/SASS/SCSS), Java and Bash/Zsh for<br>some other projects.<br><br>Curious to understand how pip works, I began looking into pip's source code.<br>I started contributing to pip in May 2016. I am now fairly familiar with the<br>design of pip and have a fair understanding of how it works, due to the various<br>contributions I have made to pip in the past year.<br><br>## Mentors<br><br>- Donald Stufft (@dstufft on GitHub)<br>- Justin Cappos (@JustinCappos on GitHub)<br><br>Communication with the mentors will be done mostly on issues and pull requests<br>on pip's GitHub repository. If at any point in time, a real time discussion is<br>to be done with the mentors, it would be done over IRC or Skype. Email can also<br>be used if needed.<br><br>## Proposal<br><br>This project is regarding improving dependency resolution performed within pip<br>by implementing a dependency resolver within it.<br><br>### Abstract<br><br>Currently, pip does not resolve dependencies correctly when there are<br>conflicting requirements. The lack of dependency resolution has caused<br>hard-to-debug bugs/failures due to the installation of incompatible packages.<br>The lack of a dependency resolver is also a blocker for various other features -<br>adding an upgrade-all functionality to pip and properly determining build-time<br>dependencies for packages are two such features.<br><br>### Deliverables<br><br>At the end of this project, pip will have the ability to:<br><br>- detect requirement conflicts<br>- resolve conflicting dependency requirements where possible<br><br>### Implementation<br><br>The implementation language will be Python. The code will maintain the<br>compatibility requirements of pip - the same source code will support the<br>multiple Python implementations and version, including but not limited to,<br>CPython 2.7, CPython 3.3+, PyPy 2, PyPy3.<br><br>New Tests for the functionality introduced will be added to pip's current test<br>suite.<br><br>User documentation would not be a major part of this project. The only changes<br>would be to mention pip can now resolve dependencies properly. There are certain<br>sections that might need updating.<br><br>#### Overview<br><br>The project will be composed of the following stages:<br><br>1. Refactor the dependency resolution logic of pip into a separate module.<br>1. Implement dependency information caching in pip.<br>1. Implement a backtracking dependency resolver to resolve the dependencies.<br><br>Every stage depends on the previous ones being completed. This step-wise<br>approach would make incremental improvements so that there is a constant<br>feedback on the work being done as well as making it easy to change course<br>without losing existing work; if needed for some unforeseen reason.<br><br>#### Discussion<br><br>There is a class in pip - `RequirementSet`, which is currently a God class. It<br>is responsible for the following:<br><br>  1. Holding a list of things to be installed<br>  1. Downloading Files<br>  1. Dependency Resolution<br>  1. Unpacking downloaded files (preparation for installation)<br>  1. Uninstalling packages<br>  1. Installing packages<br><br>This is clearly a bad situation since this is most of the heavy lifting<br>involved in pip. These responsibilities need to be separated and moved out into<br>their independent modules/classes, to allow for simplification of<br>`RequirementSet` while providing a clean platform for the remaining work.<br>This is the most tricky portion of this project, given the complexity of<br>`RequirementSet` as it stands today.<br><br>There are two kinds of distributions that may be used to install a package -<br>wheels (binary) and sdists (source). When installing a package, pip builds a<br>wheel from an sdist and then proceeds to install the wheel. The difference<br>between the two formats of distribution relevant to this project is - wheels<br>store the information about dependencies within them statically; sdists do not.<br><br>Determining the dependencies of a wheel distribution is merely the matter of<br>fetching the information from a METADATA file within the `.whl` file. The<br>dependency information for an sdist, on the other hand, can only be determined<br>after running its `setup.py` file on the target system. This means that<br>dependencies of an sdist depend on how its `setup.py` behaves which can change<br>due to variations on target systems or could even contain through random<br>choices.<br><br>Computation of an sdist's dependencies on the target system is a time-consuming<br>task since it potentially involves fetching a package from PyPI and executing<br>it's setup.py to get the dependency information. In order to improve<br>performance, once an sdist's dependencies are computed, they would be stored in<br>a cache so that during dependency resolution, the dependencies of an sdist are<br>not computed every time they are needed. Further, pip caches wheels it<br>downloads or builds meaning that any installed package or downloaded wheel's<br>dependency information would available statically, without the need to go<br>through the sdist dependency cache.<br><br>Like the wheel cache, sdist-dependency-cache will be a file system based cache.<br>The sdist-dependency-cache would only be used if the corresponding sdist is<br>being used.<br><br>Since sdist dependencies are non-deterministic, the cached dependency<br>information is potentially incorrect - in certain corner cases such as using<br>random choices in setup.py files. Such uses are not seen as important enough to<br>cater to, compared the benefits of having a cache. Further, this is already the<br>case with the information in the wheel cache.<br><br>SAT solver based resolution is not feasible for pip since a SAT solver needs<br>the entire set of packages and their dependencies to compute a solution, which<br>cannot be generated due to the aforementioned non-deterministic behaviour of<br>setup.py file. Computing dependency information for all of PyPI on a target<br>system for installing a package is simply not feasible.<br><br>The most reasonable approach is using a backtracking solver. Such a solver can<br>be incrementally provided information about the dependencies of a package and<br>would only need dependency information about packages in the dependency graph<br>of the current system.<br><br>There is a need to keep a cache of visited packages during dependency<br>resolution. A certain package-version combination may be reached via multiple<br>paths and it is an inefficient use of computation time to re-compute that<br>whether it is indeed going to satisfy the requirements or not. By storing<br>information about which package-version combinations have been visited and do<br>(or do not) satisfy the constraints, it is possible to speedup the resolution.<br><br>Consider the following example:<br><br>```<br>A-1.0 (depends: B)<br>A-2.0 (depends: B and E-1.0)<br>B-1.0 (depends: C and D)<br>C-1.0 (depends: D)<br>D-1.0<br>D-1.1 (depends: E-2.0)<br>E-1.0<br>E-2.0<br>```<br><br>If an installation of A is required, either A-2.0 or D-1.1 should not be<br>installed because they have a conflicting requirement - E. While there are<br>multiple possible solutions to this situation, the "most obvious" one us to use<br>the D-1.0, instead of not installing A-2.0. Further, as multiple packages<br>depend on D, the algorithm would "reach it" multiple times. By maintaining a<br>cache for the visited packages, it is possible to achieve a speedup in such a<br>scenario.<br><br>#### Details<br><br>Pull requests would be made on a regular basis during the project to ensure<br>that the feedback loop is quick. This also reduces the possibilities of<br>conflicts due to unrelated changes in pip.<br><br>All the code will be tested within pip's existing testing infrastructure. It<br>has everything needed to write tests related to all the changes to be made.<br>Every PR made to pip as a part of this project will contain new tests or<br>modifications to existing ones as needed.<br><br>##### Stage 1<br><br>Initially, some abstractions will be introduced to the pip codebase to improve<br>the reuse of certain common patterns within the codebase. This includes cleaner<br>temporary directory management through a `TempDirectory` class.<br><br>`RequirementSet.prepare_files` and `RequirementSet._prepare_file` are<br>downloading, unpacking packages as well as doing what pip does as dependency<br>resolution. Taking these functions apart neatly is going to be a tricky task.<br><br>The following is a listing of the final modules that will be responsible for<br>the various tasks that are currently being performed by `RequirementSet`:<br><br>- `pip.resolve` - Dependency Resolution<br>- `pip.download` - Downloading Files & Unpacking downloaded files<br>- `pip.req.req_set` - Holding a list of things to be installed / uninstalled<br>- `pip.operations.install` - Installing Packages (preparation for installation)<br>- `pip.operations.uninstall` - Uninstalling Packages<br><br>To be able to proceed to the next step, only the dependency resolution related<br>code needs to be refactored into a separate module. Other portions of<br>`RequirementSet` are not required to be refactored but the same will be tackled<br>as optional deliverables. In other words, only `pip.resolve` needs to be<br>completed to be able to proceed to the next stage in this project. This is<br>needed since in Stage 3, the resolver would be written in `pip.resolve`,<br>independent of the rest of the codebase.<br><br>##### Stage 2<br><br>A new module `pip.cache` will be created. Within this module, all the caching<br>will be handled. Thus, the code for the current wheel cache would be moved.<br>The new code for a dependency cache for sdists would also be written here.<br><br>The new cache would hold all of an sdist's egg-info. The information will be<br>stored on the file-system in a sub directory structure much like that of the<br>wheel cache, in a directory structure based on hash of the sdist file holding<br>the egg-info at the end. This will be done in a class named `EggInfoCache`.<br><br>`EggInfoCache` cache will be used only if a corresponding wheel for an sdist is<br>not available. Installing an sdist results in the creation of a wheel which<br>contains the dependency information, which would be used over the information<br>available in the `EggInfoCache`.<br><br>To be able to proceed to the next step, it is required that `EggInfoCache` is<br>implemented.<br><br>##### Stage 3<br><br>The module `pip.resolve` will be modified and a class named<br>`BacktrackingResolver` will be added to it. The class does what you expect it<br>to do - it would resolve dependencies with recursive backtracking. As described<br>above, there will be some global state stored about the packages that have been<br>explored. Other than the maintenance of global state, in the form of the cache,<br>the rest of the algorithm will essentially follow the same structure as any<br>backtracking algorithm.<br><br>The project would be complete when the aforementioned resolver is implemented.<br><br>#### Existing Work<br><br>There is existing work directly related to dependency resolution in pip, done by<br>multiple individuals.<br><br>- Robert Collins (un-merged closed pull request on pypa/pip)<br><br>  This has an incomplete backtracking dependency resolver and dependency<br>  caching.<br><br>- Sebastien Awwad (branch on a separate fork)<br><br>  This was used for the depresolve project, to investigate the state of<br>  Dependency Resolution in PyPI/pip ecosystem.<br><br>- `pip-compile` (separate project)<br><br>  This has a backtracking dependency resolver implemented to overcome pip's<br>  inablity to resolve dependencies.<br><br>Their work would be used for reference, where appropriate, during the course of<br>the project. Further, there are many package managers which implement dependency<br>resolution, which would also be looked into.<br><br>### Tentative Timeline<br><br>- Community Bonding Period: **5 May - 29 May**<br><br>  - Clean up and finalize my existing pull requests.<br>  - Read existing literature regarding dependency resolution.<br>  - Inspect existing implementations of dependency resolvers.<br><br>  GOAL: Be ready for the work coming up.<br><br>- Week 1: **30 May - 5 June**<br><br>  - Introduce abstractions across pip's codebase to make refactoring<br>    `RequirementSet` easier.<br>  - Begin breaking down `RequirementSet.prepare_file`.<br><br>- Week 2: **6 June - 12 June**<br><br>  - Continue working on the refactor of `RequirementSet`.<br><br>- Week 3: **13 June - 19 June**<br><br>  - Continue working on the refactor of `RequirementSet`.<br>  - Finish and polish `pip.resolve`.<br><br>  GOAL: `pip.resolve` module will be ready, using the current resolution<br>        strategy.<br><br>- Week 4: **20 June - 26 June**<br><br>  - Finish and polish all work on the refactor of `RequirementSet`.<br><br>- Week 5: **27 June - 3 July**<br><br>  - Move code for `WheelCache` into a new `pip.cache` module.<br>  - Write tests for `pip.cache.EggInfoCache`, based on `WheelCache`.<br>  - Begin implementation of `pip.cache.EggInfoCache`.<br><br>- Week 6: **4 July - 10 July**<br><br>  - Finish and polish `pip.cache.EggInfoCache`.<br><br>  GOAL: A cache for storing dependency information of sdists would be ready to<br>        add to pip.<br><br>- Week 7: **10 July - 16 July**<br><br>  - Create a comprehensive set of tests for the dependency resolver.<br>    (in `tests/unit/test_resolve.py`)<br>  - Begin implementation on the backtracking algorithm.<br><br>  GOAL: A comprehensive test bed is ready for testing the dependency resolver.<br><br>- Week 8: **17 July - 24 July**<br><br>  - Complete a rough implementation of the backtracking algorithm<br><br>  GOAL: An implementation of a dependency resolver to begin running tests on<br>  and work on improving.<br><br>- Week 9: **25 July - 31 July**<br><br>  - Fixing bugs in dependency resolver<br><br>- Week 10: **1 August - 6 August**<br><br>  - Finish and polish work on dependency resolver<br><br>  GOAL: A ready-to-merge PR adding a backtracking dependency resolver for pip.<br><br>- Week 11: **6 August - 13 August**<br><br>  Buffer Week.<br><br>- Week 12: **13 August - 21 August**<br><br>  Buffer Week. Finalization of project for evaluation.<br><br>If the deliverable is achieved ahead of schedule, the remaining time will be<br>utilized to resolve open issues on pip's repository in the order of priority as<br>determined under the guidance of the mentors.<br><br>#### Other Commitments<br><br>I expect to not be able to put in 40 hour/week for at most 3 weeks throughout<br>the working period, due to the schedule of my university.<br><br>I will have semester-end examinations - from 10th May 2017 to 24th May 2017 -<br>during the Community Bonding Period. My university will re-open for my third<br>semester on 12 July 2017. I expect mid-semester examinations to be held in my<br>University around 20th August 2017. During these times, I would not be able to<br>put in full 40 hour weeks due to the academic workload.<br><br>I might take a 3-4 day break during this period, regarding which I would be<br>informing my mentor around a week in advance.<br><br>I will be completely free from 30th May 2017 to 11 July 2017.<br><br>### Future Work<br><br>There seems to be some interest in being able to reuse the above dependency<br>resolution algorithm in other packaging related tools, specifically from the<br>buildout project. I intend to eventually move the dependency resolution code<br>that would come out of this project into a separate library to allow for reuse<br>by installer projects - pip, buildout and other tools.<br><br>## Previous Contributions to pip<br><br>(As on 12th March 2017)<br><br>### Issues<br><br>Authored:<br><br>- #3785 - Prefering wheel-based installation over source-based installation (Open)<br>- #3786 - Make install command upgrade packages by default (Closed)<br>- #3787 - Check if pip broke the dependency graph and warn the user (Open)<br>- #3807 - Tests fail since change on PyPI (Closed)<br>- #3809 - Switch to TOML for configuration files (Open)<br>- #3871 - Provide a way to perform non-eager upgrades (Closed)<br>- #4198 - Travis CI - pypy broken dues to dependency change in pycrypto (Closed)<br>- #4282 - What's the release schedule? (Closed)<br><br>Participated:<br><br>- #59 - Add "upgrade" and "upgrade-all" commands (Open)<br>- #988 - Pip needs a dependency resolver (Open)<br>- #1056 - pip install -U does not remember whether a package was installed with --user (Open)<br>- #1511 - ssl certificate hostname mismatch errors presented badly (Open)<br>- #1668 - Default to --user  (Open)<br>- #1736 - Create a command to make it easy to access the configuration file (Open)<br>- #1737 - Don't tell the user what they meant, just do what they meant (Open)<br>- #2313 - Automated the Creation and Upload of Release Artifacts (Open)<br>- #2732 - pip install hangs with interactive setup.py setups (Open)<br>- #3549 - pip -U pip fails (Open)<br>- #3580 - Update requests/urllib3 (Closed)<br>- #3610 - pip install from package from github, with github dependencies  (Open)<br>- #3788 - `pip` version suggested is older than the version which is installed (Closed)<br>- #3789 - Error installing Mayavi in Mac OS X  (Closed)<br>- #3798 - On using python -m pip install -upgrade pip.. its throwing an error like the one below (Closed)<br>- #3811 - no matching distribution found for install (Closed)<br>- #3814 - pip could not find a version that satisfies the requirement oslo.context (Closed)<br>- #3876 - support git refs in @ syntax (Open)<br>- #4021 - Will you accept PRs with pep484 type hints?  (Open)<br>- #4087 - pip list produces error (Closed)<br>- #4149 - Exception thrown when binary is already linked to /usr/local/bin (Open)<br>- #4160 - Pip does not seem to be handling deep requirements correctly (Open)<br>- #4162 - Let --find-links be context aware to support github, gitlab, etc. links (Open)<br>- #4170 - pip list |head raises BrokenPipeError (Open)<br>- #4182 - pip install should install packages in order to avoid ABI incompatibilities in compiled  (Open)<br>- #4186 - IOError: [Errno 13] Permission denied: '/usr/local/bin/pip' (Open)<br>- #4206 - Where on Windows 10 is pip.conf or pip.ini located? (Closed)<br>- #4221 - Feature request: Check if user has permissions before downloading files (Closed)<br>- #4229 - "pip uninstall" is too noisy (Open)<br><br>#### Pull Requests<br><br>Authored:<br><br>- #3806 - Change install command's default behaviour to upgrade packages by default (Closed, superseded by #3972)<br>- #3808 - Fix Tests (Merged)<br>- #3818 - Improve UX and tests of check command (Merged)<br>- #3972 - Add an upgrade-strategy option (Merged)<br>- #3974 - [minor] An aesthetic change to wheel command source (Merged)<br>- #4192 - Move out all the config code to a separate module (Merged)<br>- #4193 - Add the ability to autocorrect a user's command (Open)<br>- #4199 - Fix Tests for Travis CI (Merged)<br>- #4200 - Reduce the API exposed by the configuration class (Merged)<br>- #4232 - Update documentation to mention upgrade-strategy (Merged)<br>- #4233 - Nicer permissions error message (Open)<br>- #4240 - [WIP] Add a configuration command (Open)<br><br>Participated:<br><br>- #2716 - Issue #988: new resolver for pip (Closed)<br>- #2975 - Different mock dependencies based on Python version (Merged)<br>- #3744 - Add a "Upgrade all local installed packages" (Open)<br>- #3750 - Add a `pip check` command. (Merged)<br>- #3751 - tox.ini: Add "cover" target (Open)<br>- #3794 - Use the canonicalize_name function for finding .dist-info (Merged)<br>- #4142 - Optionally load C dependencies based on platform (Open)<br>- #4144 - Install build dependencies as specified in PEP 518 (Open)<br>- #4150 - Clarify default for --upgrade-strategy is eager (Merged)<br>- #4194 - Allow passing a --no-progress-bar to the install script to surpress progress bar (Merged)<br>- #4201 - Register req_to_install for cleanup sooner (Merged)<br>- #4202 - Switch to 3.6.0 final as our latest 3.x release (Merged)<br>- #4211 - improve message when installing requirements file (#4127) (Merged)<br>- #4241 - Python 3.6 is supported (Merged)<br><br>## References<br><br>1. [pypa/pip#988](<a href="https://github.com/pypa/pip/issues/988">https://github.com/pypa/pip/issues/988</a>)<br><br>   Tracking issue for adding a proper dependency resolver in pip. Contains<br>   links to various useful resources.<br><br>1. [pypa/pip#2716](<a href="https://github.com/pypa/pip/issues/2716">https://github.com/pypa/pip/issues/2716</a>)<br><br>   Prior work by Robert Collins for adding a proper dependency resolver in pip.<br><br>1. [Python Dependency Resolution](<a href="https://docs.google.com/document/d/1x_VrNtXCup75qA3glDd2fQOB2TakldwjKZ6pXaAjAfg/edit?usp=sharing">https://docs.google.com/document/d/1x_VrNtXCup75qA3glDd2fQOB2TakldwjKZ6pXaAjAfg/edit?usp=sharing</a>)<br><br>   A writeup by Sebastian Awwad on the current state of dependency resolution<br>   in pip and PyPI in general.<br><br>1. [PSF Application Template](<a href="https://wiki.python.org/moin/SummerOfCode/ApplicationTemplate2017">https://wiki.python.org/moin/SummerOfCode/ApplicationTemplate2017</a>)<br><br>   For guidance on how to write the application and what information is needed.<br><br>1. [Stork: Secure Package Management for VM Environments](<a href="http://isis.poly.edu/~jcappos/papers/cappos_stork_dissertation_08.pdf">http://isis.poly.edu/~jcappos/papers/cappos_stork_dissertation_08.pdf</a>)<br><br>   A Paper by Justin Cappos about Stork, used for reference regarding<br>   Backtracking Resolution<br><br></div>